Negative associations for search results ranking and refinement

• US 8,442,972 B2
• Filed: 10/11/2007
• Issued: 05/14/2013
• Est. Priority Date: 10/11/2006
• Status: Active Grant

• Current Assignee: Collarity Incorporated
• Original Assignee: Collarity Incorporated
• Inventors: Ismalon, Emil
• Primary Examiner(s): DWIVEDI, MAHESH H
• Application Number:
  US11/870,999
• Publication Number:
  US 20080140643A1
• Time in Patent Office: 2,042 Days
• Field of Search: 707/721, 707/722, 707/713
• US Class Current: 707/722
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

A computer-implemented method is provided, including receiving a search query from a user during a search session, and presenting information to the user responsively to the search query. After an indication that the user takes an action related to the search session is received, a portion of the presented information is identified that the user did not select prior to taking the action, and respective scores are assigned to search results generated responsively to the search query, including lowering one or more of the scores of the respective search results that are characterized by the non-selected portion of the presented information. The search results are ranked according to the scores, and presented to the user. Other embodiments are also described.

Claims

1. A computer-implemented method comprising:

constructing an association graph that includes one or more terms as vertices linked by edges, which edges have respective edge scores that represent respective strengths of association of the respective vertices linked thereby;

receiving from a user a search query that comprises one or more of the terms of the association graph;

responsively to the search query, generating, using the association graph, refinement options that comprise respective terms of the association graph, and presenting information to the user, including the refinement options for optional addition to the search query;

identifying a portion of the refinement options, and corresponding terms, that the user did not select;

using the association graph, assigning respective ranking scores to search results generated responsively to the search query, including lowering one or more of the ranking scores of the respective search results that are characterized by the non-selected portion of the refinement options, by damping the edge score of an edge of the association graph between two of the vertices respectively representing two of the non-selected terms;

ranking the search results according to the ranking scores; and

presenting the ranked search results to the user.

2. The method according to claim 1, wherein identifying the non-selected portion comprises identifying the non-selected portion without receiving explicit feedback from the user regarding a level of interest of the user in the non-selected portion.

3. The method according to claim 1,

wherein receiving the search query comprises receiving a first search query from the user,

wherein presenting the information comprises presenting the information including first search results generated responsively to the first search query, and the refinement options,

wherein the method further comprises receiving a second search query from the user after receiving the first search query,

wherein assigning the respective ranking scores comprises assigning the respective ranking scores to second search results generated responsively to the second search query, including lowering one or more of the ranking scores of the respective second search results that are characterized by the non-selected portion of the refinement options,

wherein ranking the search results comprises ranking the second search results, and

wherein presenting the ranked search results comprises presenting the second ranked search results.

4. The method according to claim 3, wherein receiving the second search query comprises receiving the second search query during a search session during which the first query was received.

5. The method according to claim 3, wherein receiving the second search query comprises receiving the second search query during a later search session after a search session during which the first query was received.

6. The method according to claim 1, wherein the search query includes a first search query, wherein the user is a first user, wherein the ranking scores include first ranking scores, and wherein the search results include first search results, and comprising:

receiving a second search query from a second user;

assigning respective second ranking scores to second search results generated responsively to the second search query, including lowering one or more of the second ranking scores of the respective second search results that are characterized by the portion of the information presented to and not selected by the first user;

ranking the second search results according to the second ranking scores; and

presenting the ranked second search results to the second user.

7. The method according to claim 1, wherein lowering comprises attributing greater importance to the non-selection of the portion of the refinement options if the user views the non-selected portion for a longer amount of time.

8. The method according to claim 1, wherein lowering the ranking scores comprises attributing greater importance to the non-selection of the portion of the refinement options if the user selects another of the presented refinement options, rather than selecting none of the presented refinement options.

9. The method according to claim 1, wherein presenting the information to the user responsively to the search query comprises displaying the search results in real time as the query is entered by the user.

10. The method according to claim 1, wherein identifying the portion comprises after receiving an indication that the user takes an action related to the search session, identifying the portion of the refinement options that the user did not select prior to taking the action.

11. The method according to claim 10, wherein the action is selected from the group consisting of:

selecting one of the refinement options, selecting a portion of the information, submitting the search query, modifying the search query, and requesting additional search results for the search query.

12. The method according to claim 1, wherein generating the refinement options comprises selecting as the refinement options a portion of respective terms of the association graph directly linked to the terms of the search query by respective edges of the association graph.

13. The method according to claim 12,

wherein the refinement options comprise primary and secondary refinement options,

wherein generating the refinement options comprises:

selecting as the primary refinement options a portion of the respective terms of the association graph directly linked to the terms of the search query by respective edges of the association graph; and

for each of at least a portion of the primary refinement options, selecting as the secondary refinement options a portion of the respective terms of the association graph that are (a) directly linked to the terms of the search query by respective edges of the association graph, and (b) directly linked to the term of the primary refinement option by respective edges of the association graph, and

wherein presenting the refinement options comprises presenting the primary refinement options, and the secondary refinement options for the at least the portion of the primary refinement options.

14. The method according to claim 1, wherein the association graph comprises a personal association graph of the user, which represents interactions of a plurality of documents with the user during one or more searches conducted during one or more search sessions.

15. The method according to claim 1, wherein the association graph comprises a session association graph, which represents interactions of one or more documents with the user during one or more searches conducted by the user during a single search session.

16. The method according to claim 1,

wherein generating the refinement options comprises generating:

(a) primary refinement options that are most closely related to the search query, and (b) for at least a portion of the primary refinement options, secondary refinement options, which are more distantly related to the search query, and are also related to their associated primary refinement option, and

wherein presenting the refinement options comprises presenting the primary refinement options, and the secondary refinement options for the at least the portion of the primary refinement options.

17. Apparatus comprising:

an interface; and

a processor, which is configured to construct an association graph that includes one or more terms as vertices linked by edges, which edges have respective edge scores that represent respective strengths of association of the respective vertices linked thereby;

receive from a user, via the interface, a search query that comprises one or more of the terms of the association graph;

responsively to the search query, generate, using the association graph, refinement options that comprise respective terms of the association graph, and present, via the interface, information to the user, including refinement options for optional addition to the search query;

identify a portion of the refinement options, and corresponding terms, that the user did not select;

using the association graph, assign respective ranking scores to search results generated responsively to the search query, including lowering one or more of the ranking scores of the respective search results that are characterized by the non-selected portion of the refinement options, by damping the edge score of an edge of the association graph between two of the vertices respectively representing two of the non-selected terms;

rank the search results according to the ranking scores; and

present the ranked search results to the user, via the interface.

18. The apparatus according to claim 17, wherein the processor is configured to identify the non-selected portion without receiving explicit feedback from the user regarding a level of interest of the user in the non-selected portion.

19. The apparatus according to claim 17, wherein the processor is configured to identify the portion after receiving, via the interface, an indication that the user takes an action related to the search session, the action selected from the group consisting of:

selecting one of the refinement options, selecting a portion of the information, submitting the search query, modifying the search query, and requesting additional search results for the search query.

20. The apparatus according to claim 17, wherein the processor is configured to attribute greater importance to the non-selection of the portion of the refinement options if the user views the non-selected portion for a longer amount of time.

21. The apparatus according to claim 17, wherein the processor is configured to lower the ranking scores by attributing greater importance to the non-selection of the portion of the refinement options if the user selects another of the presented refinement options, rather than selecting none of the presented refinement options.

22. The apparatus according to claim 17, wherein the processor is configured to generate the refinement options by selecting as the refinement options a portion of respective terms of the association graph directly linked to the terms of the search query by respective edges of the association graph.

23. The apparatus according to claim 17, wherein the processor is configured to:

generate the refinement options by generating;

(a) primary refinement options that are most closely related to the search query, and (b) for at least a portion of the primary refinement options, secondary refinement options, which are more distantly related to the search query, and are also related to their associated primary refinement option, and

present the primary refinement options, and the secondary refinement options for the at least the portion of the primary refinement options.

24. A computer software product, comprising a non-transitory tangible computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to construct an association graph that includes one or more terms as vertices linked by edges, which edges have respective edge scores that represent respective strengths of association of the respective vertices linked thereby;

receive from a user a search query that comprises one or more of the terms of the association graph;

responsively to the search query, generate, using the association graph, refinement options that comprise respective terms of the association graph, and present information to the user, including refinement options for optional addition to the search query;

identify a portion of the refinement options, and corresponding terms, that the user did not select;

using the association graph, assign respective ranking scores to search results generated responsively to the search query, including lowering one or more of the ranking scores of the respective search results that are characterized by the non-selected portion of the refinement options, by damping the score of an edge of the association graph between two of the vertices respectively representing two of the non-selected terms;

rank the search results according to the ranking scores; and

present the ranked search results to the user.

25. The computer software product according to claim 24, wherein the instructions, when read by the computer, cause the computer to identify the non-selected portion without receiving explicit feedback from the user regarding a level of interest of the user in the non-selected portion.

26. The computer software product according to claim 24, wherein the instructions, when read by the computer, cause the computer to identify the portion after receiving an indication that the user takes an action related to the search session, the action selected from the group consisting of:

selecting one of the refinement options, selecting a portion of the information, submitting the search query, modifying the search query, and requesting additional search results for the search query.

27. The computer software product according to claim 24, wherein the instructions, when read by the computer, cause the computer to attribute greater importance to the non-selection of the portion of the refinement options if the user views the non-selected portion for a longer amount of time.

28. The computer software product according to claim 24, wherein the instructions, when read by the computer, cause the computer to lower the ranking scores by attributing greater importance to the non-selection of the portion of the refinement options if the user selects another of the presented refinement options, rather than selecting none of the presented refinement options.