Generation of refinement terms for search queries

• US 8,812,541 B2
• Filed: 03/12/2013
• Issued: 08/19/2014
• Est. Priority Date: 12/05/2005
• Status: Expired due to Fees

• Current Assignee: Collarity Incorporated
• Original Assignee: Collarity Incorporated
• Inventors: Ismalon, Emil
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US13/742,986
• Publication Number:
  US 20130173614A1
• Time in Patent Office: 525 Days
• Field of Search: 707/759, 707/769, 707/713, 709/201, 709/203, 709/213, 709/217
• US Class Current: 707/769
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/433 using audio data
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/487 using geographical or spatial information, e.g. location
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

A computer-implemented method includes receiving from a user, by a search system, a search query comprising terms. Using at least one association graph comprising terms, the search system generates a suggested replacement query by designating one or more of the terms of the search query as anchor terms, and the remaining terms of the search query as non-anchor terms, and replacing one or more of the non-anchor terms of the search query with one or more suggested replacement terms, to generate the suggested replacement query that includes the one or more anchor terms and the one or more suggested replacement terms. The suggested replacement query is presented to the user. Responsively to a selection of the suggested replacement query by the user, the search query received from the user is replaced with the suggested replacement query, and search results are generated responsively to the suggested replacement query and presented.

Claims

1. A computer-implemented method comprising:

receiving from a user, by a search system, a search query comprising terms, each of which comprises one or more keywords;

using at least one association graph comprising terms, each of which comprises one or more keywords, generating, by the search system, a suggested replacement query by;

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

replacing one or more of the non-anchor terms of the search query with one or more suggested replacement terms, to generate the suggested replacement query that includes the one or more anchor terms and the one or more suggested replacement terms;

presenting the suggested replacement query to the user; and

,

responsively to a selection of the suggested replacement query by the user, replacing the search query received from the user with the suggested replacement query, and presenting search results to the user generated responsively to the suggested replacement query.

2. The method according to claim 1, wherein receiving the search query comprises receiving the search query in a search field presented to the user, and wherein replacing the search query received from the user with the suggested replacement query comprises populating, by the search system, the search field with the suggested replacement query.

3. The method according to claim 1, wherein presenting the suggested replacement query to the user comprises presenting the suggested replacement query as a hyperlink, and wherein replacing comprises replacing responsively to the selection of the suggested replacement query made by the user clicking on the hyperlink.

4. The method according to claim 1, further comprising:

presenting to the user, in addition to the suggested replacement query, one or more keyword-addition refinement options; and

responsively to a selection of one of the keyword-addition refinement options by the user, adding the selected keyword-addition refinement option to the search query received from the user.

5. The method according to claim 1, wherein generating and presenting the suggested replacement query comprise generating and presenting a plurality of suggested replacement queries.

6. The method according to claim 5, wherein generating the suggested replacement queries comprises:

generating a plurality of candidate replacement queries including the suggested replacement queries;

calculating association scores of each of the candidate replacement queries within the at least one association graph; and

selecting top-scoring ones of the candidate replacement queries as the suggested replacement queries.

7. The method according to claim 1, wherein the at least one association graph includes terms of the search query as vertices.

8. The method according to claim 1, wherein designating the one or more of the terms as the anchor terms comprises designating the one or more of the terms as the anchor terms responsively to respective association scores of each of the terms of the search query within the at least one association graph.

9. The method according to claim 1, wherein replacing the one or more of the non-anchor terms comprises identifying, as the one or more suggested replacement terms, synonyms of the one or more of the non-anchor terms of the search query.

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 terms of the search query other than the one of the terms of the search query corresponding to the identified synonym; and

,

responsively to the calculated strengths of association, selecting as the one or more 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 terms of the search query other than the at least two of the terms of the search query respectively synonymous with the identified synonyms.

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

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

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

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

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

15. The method according to claim 1, wherein the at least one association graph comprises an association graph that represents interactions of previous user search queries with respective search result documents presented in response to the previous search queries.

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

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

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

19. The method according to claim 1, wherein receiving the search 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.

20. The method according to claim 19, 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.

21. The method according to claim 1, wherein replacing the one or more of the non-anchor terms comprises:

identifying a plurality of replacement terms;

using the at least one association graph, calculating respective strengths of association of each of the identified replacement terms with the terms of the search query other than the one of the terms of the search query corresponding to the identified replacement term; and

,

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

22. The method according to claim 1, wherein generating the suggested replacement query comprises:

generating a plurality of candidate replacement queries including the suggested replacement query;

calculating association scores of each of the candidate replacement queries within the at least one association graph; and

selecting as the suggested replacement query the top-scoring one of the candidate replacement queries.

23. Apparatus comprising:

an interface; and

a processor, which is configured to receive from a user, via the interface, a search query comprising terms, each of which comprises one or more keywords;

using at least one association graph comprising terms, each of which comprises one or more keywords, generate a suggested replacement query by;

(a) designating one or more of the terms of the search query as anchor terms, and the remaining terms of the search query as non-anchor terms, and (b) replacing one or more of the non-anchor terms of the search query with one or more suggested replacement terms, to generate the suggested replacement query that includes the one or more anchor terms and the one or more suggested replacement terms;

present, via the interface, the suggested replacement query to the user; and

, responsively to a selection of the suggested replacement query by the user, replace the search query received from the user with the suggested replacement query, and present, via the interface, search results to the user generated responsively to the suggested replacement query.

24. The apparatus according to claim 23, wherein the processor is configured to receive the search query in a search field presented to the user, and to replace the search query received from the user with the suggested replacement query by populating the search field with the suggested replacement query.

25. The apparatus according to claim 23, wherein the processor is configured to present the suggested replacement query as a hyperlink, and to replace responsively to the selection of the suggested replacement query made by the user clicking on the hyperlink.

26. The apparatus according to claim 23, wherein the processor is further configured to present to the user, via the interface, in addition to the suggested replacement query, one or more keyword-addition refinement options;

and, responsively to a selection of one of the keyword-addition refinement options by the user, to add the selected keyword-addition refinement option to the search query received from the user.

27. The apparatus according to claim 23, wherein the processor is configured to generate and present a plurality of suggested replacement queries.

28. The apparatus according to claim 27, wherein the processor is configured to generate the suggested replacement queries by:

generating a plurality of candidate replacement queries including the suggested replacement queries;

calculating association scores of each of the candidate replacement queries within the at least one association graph; and

selecting top-scoring ones of the candidate replacement queries as the suggested replacement queries.

29. The apparatus according to claim 23, wherein the at least one association graph includes terms of the search query as vertices.

30. The apparatus according to claim 23, wherein the processor is configured to designate the one or more of the terms as the anchor terms responsively to respective association scores of each of the terms of the search query within the at least one association graph.

31. The apparatus according to claim 23, wherein the processor is configured to replace the one or more of the non-anchor terms by identifying, as the one or more suggested replacement terms, synonyms of the one or more of the non-anchor terms of the search query.

32. The apparatus according to claim 31, wherein the processor is configured to identify the synonyms by:

using the at least one association graph, calculating respective strengths of association of each of the identified synonyms with the terms of the search query other than the one of the terms of the search query 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.

33. The apparatus according to claim 32, wherein the processor is configured to calculate the respective strengths of association by calculating a strength of association of at least two of the identified synonyms with the terms of the search query other than the at least two of the terms of the search query respectively synonymous with the identified synonyms.

34. The apparatus according to claim 31, wherein the processor is configured to identify the synonyms of the one or more of the terms of the search query by:

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

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

35. The apparatus according to claim 23, wherein the processor is configured to designate as the anchor terms by determining a part of speech of each of the terms of the search query, and considering for designation as the anchor terms only those of the terms of the search query that are a particular part of speech.

36. The apparatus according to claim 23, wherein the processor is configured to determine how many synonyms each of the second query terms has in a lexical database, and to designate as the anchor terms one or more of the second query terms having the fewest synonyms.

37. The apparatus according to claim 23, wherein the at least one association graph comprises an association graph that represents interactions of previous user search queries with respective search result documents presented in response to the previous search queries.

38. The apparatus according to claim 23, wherein the at least one association graph comprises a personal association graph (PAG) for the user that represents interactions of previous search queries of the user with respective search result documents presented to the user in response to the previous search queries.

39. The apparatus according to claim 23, wherein the at least one association graph comprises a topic association graph (TAG) that represents interactions of previous search queries of a plurality of users including the user, conducted within a single topic, with respective search result documents presented to the users in response to the previous search queries.

40. The apparatus according to claim 23, wherein the at least one association graph comprises a global association graph (GAG) that represents interactions of previous search queries of a plurality of users including the user with respective search result documents presented to the users in response to the previous search queries.

41. The apparatus according to claim 23, wherein the processor is configured to receive from the user an indication of a desired level of personalization of the suggested replacement terms, and to identify the suggested replacement terms by selecting the at least one association graph for use at least in part responsively to the indication.

42. The apparatus according to claim 41, wherein the processor is configured to present, via the interface, 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 to receive from the user the indication of a desired one of the levels.

43. The apparatus according to claim 23, wherein the processor is configured to replace the one or more of the non-anchor terms by:

identifying a plurality of replacement terms;

using the at least one association graph, calculating respective strengths of association of each of the identified replacement terms with the terms of the search query other than the one of the terms of the search query corresponding to the identified replacement term; and

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

44. The apparatus according to claim 23, wherein the processor is configured to generate the suggested replacement query by:

generating a plurality of candidate replacement queries including the suggested replacement query;

calculating association scores of each of the candidate replacement queries within the at least one association graph; and

selecting as the suggested replacement query the top-scoring one of the candidate replacement queries.

45. 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 from a user a search query comprising terms, each of which comprises one or more keywords;

using at least one association graph comprising terms, each of which comprises one or more keywords, generate a suggested replacement query by;

(a) designating one or more of the terms of the search query as anchor terms, and the remaining terms of the search query as non-anchor terms, and (b) replacing one or more of the non-anchor terms of the search query with one or more suggested replacement terms, to generate the suggested replacement query that includes the one or more anchor terms and the one or more suggested replacement terms;

present the suggested replacement query to the user; and

, responsively to a selection of the suggested replacement query by the user, replace the search query received from the user with the suggested replacement query, and present search results to the user generated responsively to the suggested replacement query.

46. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to receive the search query in a search field presented to the user, and to replace the search query received from the user with the suggested replacement query by populating the search field with the suggested replacement query.

47. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to present the suggested replacement query as a hyperlink, and to replace responsively to the selection of the suggested replacement query made by the user clicking on the hyperlink.

48. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to present to the user in addition to the suggested replacement query, one or more keyword-addition refinement options;

and, responsively to a selection of one of the keyword-addition refinement options by the user, to add the selected keyword-addition refinement option to the search query received from the user.

49. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to generate and present a plurality of suggested replacement queries.

50. The computer software product to claim 49, wherein the instructions, when read by the computer, cause the computer to generate the suggested replacement queries by:

generating a plurality of candidate replacement queries including the suggested replacement queries;

calculating association scores of each of the candidate replacement queries within the at least one association graph; and

selecting top-scoring ones of the candidate replacement queries as the suggested replacement queries.

51. The computer software product according to claim 45, wherein the at least one association graph includes terms of the search query as vertices.

52. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to designate the one or more of the terms as the anchor terms responsively to respective association scores of each of the terms of the search query within the at least one association graph.

53. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to replace the one or more of the non-anchor terms by identifying, as the one or more suggested replacement terms, synonyms of the one or more of the non-anchor terms of the search query.

54. The computer software product according to claim 53, wherein the instructions, when read by the computer, cause the computer to identify the synonyms by:

using the at least one association graph, calculating respective strengths of association of each of the identified synonyms with the terms of the search query other than the one of the terms of the search query 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.

55. The computer software product according to claim 54, wherein the instructions, when read by the computer, cause the computer to calculate the respective strengths of association by calculating a strength of association of at least two of the identified synonyms with the terms of the search query other than the at least two of the terms of the search query respectively synonymous with the identified synonyms.

56. The computer software product according to claim 53, wherein the instructions, when read by the computer, cause the computer to identify the synonyms of the one or more of the terms of the search query by:

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

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

57. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to designate as the anchor terms by determining a part of speech of each of the terms of the search query, and considering for designation as the anchor terms only those of the terms of the search query that are a particular part of speech.

58. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to determine how many synonyms each of the second query terms has in a lexical database, and to designate as the anchor terms one or more of the second query terms having the fewest synonyms.

59. The computer software product according to claim 45, wherein the at least one association graph comprises an association graph that represents interactions of previous user search queries with respective search result documents presented in response to the previous search queries.

60. The computer software product according to claim 45, wherein the at least one association graph comprises a personal association graph (PAG) for the user that represents interactions of previous search queries of the user with respective search result documents presented to the user in response to the previous search queries.

61. The computer software product according to claim 45, wherein the at least one association graph comprises a topic association graph (TAG) that represents interactions of previous search queries of a plurality of users including the user, conducted within a single topic, with respective search result documents presented to the users in response to the previous search queries.

62. The computer software product according to claim 45, wherein the at least one association graph comprises a global association graph (GAG) that represents interactions of previous search queries of a plurality of users including the user with respective search result documents presented to the users in response to the previous search queries.

63. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to receive from the user an indication of a desired level of personalization of the suggested replacement terms, and to identify the suggested replacement terms by selecting the at least one association graph for use at least in part responsively to the indication.

64. The computer software product according to claim 63, wherein the instructions, when read by the computer, cause the computer to present 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 to receive from the user the indication of a desired one of the levels.

65. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to replace the one or more of the non-anchor terms by:

identifying a plurality of replacement terms;

using the at least one association graph, calculating respective strengths of association of each of the identified replacement terms with the terms of the search query other than the one of the terms of the search query corresponding to the identified replacement term; and

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

66. The computer software product according to claim 45, wherein the instructions, when read by the computer, cause the computer to generate the suggested replacement query by:

generating a plurality of candidate replacement queries including the suggested replacement query;

calculating association scores of each of the candidate replacement queries within the at least one association graph; and

selecting as the suggested replacement query the top-scoring one of the candidate replacement queries.