SEARCH PHRASE REFINEMENT BY SEARCH TERM REPLACEMENT

• US 20080091670A1
• Filed: 08/28/2007
• Published: 04/17/2008
• Est. Priority Date: 10/11/2006
• Status: Active Grant

• Current Assignee: Collarity Incorporated
• Original Assignee: Collarity Incorporated
• Inventors: Ismalon, Emil
• Granted Patent: US 7,756,855 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence

Abstract

A computer-implemented method is provided, which includes receiving a plurality of first search queries, each of which comprises one or more first query terms. At least one association graph is constructed that includes at least a portion of the first query terms as vertices. A second search query is received from a user, which comprises a plurality of second query terms. One or more suggested replacement terms for one or more of the second query terms are identified, using the at least one association graph. The suggested replacement terms are presented to the user. Responsively to a selection of one of the suggested replacement terms by the user, the selected suggested replacement term is substituted for the corresponding one of the second query terms, to generate a refined search query. Search results are presented to the user responsively to the refined search query. Other embodiments are also described.

Claims

1. A computer-implemented method comprising:

receiving a plurality of first search queries, each of which comprises one or more first query terms;

constructing at least one association graph that includes at least a portion of the first query terms as vertices;

receiving from a user a second search query comprising a plurality of second query terms;

using the at least one association graph, identifying one or more suggested replacement terms for one or more of the second query terms;

presenting the suggested replacement terms to the user;

responsively to a selection of one of the suggested replacement terms by the user, substituting the selected suggested replacement term for the corresponding one of the second query terms, to generate a refined search query; and

presenting search results to the user responsively to the refined search query.

2. The method according to claim 1, wherein identifying the suggested replacement terms for the one or more of the second query terms comprises identifying the suggested replacement terms for exactly one of the second query terms.

3. The method according to claim 1, wherein identifying the suggested replacement terms for the one or more of the second query terms comprises identifying at least one first suggested replacement term for a first one of the one or more of the second query terms, and at least one second suggested replacement term for a second one of the one or more of the second query terms.

4. The method according to claim 1, wherein presenting the one or more suggested replacement terms comprises presenting one or more candidate replacement queries, each of which includes at least one of the suggested replacement terms and the plurality of second query terms other than the second query terms that respectively correspond to the at least one of the suggested replacement terms.

5. The method according to claim 1, wherein presenting the one or more suggested replacement terms comprises presenting each of the one or more suggested replacement terms in association with the one of the second query terms that corresponds to the suggested replacement term.

6. The method according to claim 1, wherein receiving the plurality of first search queries comprises receiving the plurality of first search queries from the user, and wherein constructing the at least one association graph comprises constructing a personal association graph (PAG) for the user that represents interactions of the plurality of first search queries with a respective plurality of search result documents presented to the user in response to the first search queries.

7. The method according to claim 1, wherein receiving the plurality of first search queries comprises receiving the plurality of first search queries conducted within a single topic, from a plurality of users including the user, and wherein constructing the at least one association graph comprises constructing a topic association graph (TAG) that represents interactions of the plurality of first search queries with a respective plurality of search result documents presented to the users in response to the first search queries.

8. The method according to claim 1, wherein receiving the plurality of first search queries comprises receiving the plurality of first search queries from a plurality of users including the user, and wherein constructing the at least one association graph comprises constructing a global association graph (GAG) that represents interactions of the plurality of first search queries with a respective plurality of search result documents presented to the users in response to the first search queries.

9. The method according to claim 1, wherein identifying the one or more suggested replacement terms for the one or more of the second query terms comprises identifying synonyms of the one or more of the second query terms as the one or more suggested replacement terms.

10. The method according to claim 9, wherein identifying the synonyms comprises:

using the at least one association graph, calculating respective strengths of association of each of the identified synonyms with the plurality of second query terms other than the one of the second query terms corresponding to the identified synonym; and

responsively to the calculated strengths of association, selecting as the suggested replacement terms a portion of the identified synonyms including one or more of the identified synonyms.

11. The method according to claim 10, wherein calculating the respective strengths of association comprises calculating a strength of association of at least two of the identified synonyms with the plurality of second query terms other than the at least two of the second query terms respectively synonymous with the identified synonyms.

12. The method according to claim 9, wherein identifying the synonyms of the one or more of the second query terms comprises:

retrieving, from a lexical database, respective measures of strength of synonymy between each of the synonyms and its synonymous second query term; and

selecting only the synonyms having the greatest measures of strength as the identified synonyms.

13. The method according to claim 1, wherein identifying the one or more suggested replacement terms comprises:

designating one or more of the second query terms as anchor terms, and the remaining second query terms as non-anchor terms; and

identifying the one or more suggested replacement terms for one or more of the non-anchor terms and not for any of the anchor terms.

14. The method according to claim 13, wherein designating as the anchor terms comprises determining a part of speech of each of the second query terms, and considering for designation as the anchor terms only those of the second query terms that are a particular part of speech.

17. The method according to claim 13, wherein designating as the anchor terms comprises designating as the anchor terms responsively to respective association scores of each of the second query terms within the at least one association graph.

18. The method according to claim 1, wherein receiving the initial search second query comprises receiving from the user an indication of a desired level of personalization of the suggested replacement terms, and wherein identifying the suggested replacement terms comprises selecting the at least one association graph for use at least in part responsively to the indication.

19. The method according to claim 18, wherein receiving the indication of the desire level of personalization comprises presenting to the user a range of levels of personalization, including a personalized level, a global level that is not personalized, and a community level between the personalized level and the global level, and receiving from the user the indication of a desired one of the levels.

15. -16. (canceled)

20. A computer-implement method comprising:

receiving from a user an initial search query comprising a plurality of query terms;

designating one or more of the query terms as anchor terms, and the remaining query terms as non-anchor terms;

identifying one or more suggested replacement terms for one or more of the non-anchor terms and not for any of the anchor terms;

presenting the suggested replacement terms to the user;

responsively to a selection of one of the suggested replacement terms by the user, substituting the selected suggested replacement term the corresponding one of the query terms, to generate a refined search query; and

presenting search results to the user responsively to the refined search query.

21. The method according to claim 20, wherein identifying the suggested replacement terms for the one or more of the query terms comprises identifying the suggested replacement terms for exactly one of the query terms.

22. The method according to claim 20, wherein identifying the suggested replacement terms for the one or more of the query terms comprises identifying at least one first suggested replacement term for a first one of the one or more of the query terms, and at least one second suggested replacement term for a second one of the one or more of the query terms.

26. The method according to claim 20, wherein designating as the anchor terms comprises determining how many synonyms each of the query terms has in a lexical database, and designating as the anchor terms one or more of the query terms having the fewest synonyms.

27. The method according to claim 20, wherein designating as the anchor terms comprises designating as the anchor terms responsively to respective association scores of each of the query terms within at least one association graph that includes as vertices respective previous query terms.

28. The method according to claim 20, wherein designating as the anchor terms comprises determining a part of speech of each of the query terms, and considering for designation as the anchor terms only those of the query terms that are a particular part of speech.

23. -25. (canceled)

29. (canceled)

30. Apparatus comprising:

an interface; and

a processor, which is configured to receive a plurality of first search queries, via the interface, each of which comprises one or more first query terms;

construct at least one association graph that includes at least a portion of the first query terms as vertices;

receive from a user, via the interface, a second search query comprising a plurality of second query terms;

using the at least one association graph, identify one or more suggested replacement terms for one or more of the second query terms;

present the suggested replacement terms to the user, via the interface;

responsively to a selection of one of the suggested replacement terms by the user, substitute the selected suggested replacement term for the corresponding one of the second query terms, to generate a refined search query; and

present, via the interface, search results to the user responsively to the refined search query.

31. -58. (canceled)

59. A computer software product, comprising a tangible computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to receive a plurality of first search queries, each of which comprises one or more first query terms;

construct at least one association graph that includes at least a portion of the first query terms as vertices;

receive from a user a second search query comprising a plurality of second query terms;

using the at least one association graph, identify one or more suggested replacement terms for one or more of the second query terms;

present the suggested replacement terms to the user;

responsively to a selection of one of the suggested replacement terms by the user, substitute the selected suggested replacement term for the corresponding one of the second query terms, to generate a refined search query; and

present search results to the user responsively to the refined search query.

60. -87. (canceled)