Determining quality measures for web objects based on searcher behavior

• US 8,290,986 B2
• Filed: 06/27/2007
• Issued: 10/16/2012
• Est. Priority Date: 06/27/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Popescul, Alexandrin, Zimak, Nadav A., Tsioutsiouliklis, Kostas, Brunk, Clifford A.
• Primary Examiner(s): Jalil, Neveen Abel
• Assistant Examiner(s): KINSAUL, DANIEL W
• Application Number:
  US11/769,641
• Publication Number:
  US 20090006357A1
• Time in Patent Office: 1,938 Days
• Field of Search: None
• US Class Current: 707/798
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations

Abstract

Techniques are provided for generating quality measures for items, including web pages, based on a “random searcher” behavior model. The random searcher behavior model takes into account “implicit” links between items, instead of or in addition to the explicit links. After identifying the implicit links between items, the implicit links may be used as the basis for generating quality measures for the items to which the implicit links point. A variety of types of implicit links are described. To facilitate the generation of quality measures for items based on implicit links, a graph of the implicit links may be constructed in a manner similar to a webgraph.

Claims

1. A method for measuring quality of web objects, the method comprising the computer-implemented steps of:

storing behavior data based on how users interact with a search engine;

generating one or more graphs that include nodes that represent web objects;

wherein at least some edges within said one or more graphs represent implicit links derived from said behavior data;

wherein at least one implicit link, of said implicit links, is represented in said one or more graphs by an edge from a first node, which represents a first web object, to a second node that represents a first query, wherein said first web object was clicked on before said first query was made; and

for each web object in a set of web objects that are represented by nodes in said one or more graphs, generating a quality measure for said each web object based on edges within said one or more graphs that lead to the node that represents said each web object, wherein the quality measure is based at least in part, on how much time users spend viewing the web objects;

wherein generating said quality measure for said each web object in the set of web objects includes generating at least one measure based on said edge that represents said at least one implicit link within said one or more graphs;

wherein the method is performed by one or more computing devices.

2. The method of claim 1 wherein the web objects that are represented by the nodes in the one or more graphs include items that (a) appear on search results pages presented by the search engine, and (b) can be clicked on by a user.

3. The method of claim 1 further comprising using said quality measures to improve search results generated by said search engine.

4. The method of claim 1 further comprising using said quality measures to improve content matching performed by said search engine.

5. The method of claim 1 wherein:

at least some nodes of the one or more graphs represent queries submitted to the search engine; and

the implicit links include at least one implicit link that is established from a first query to a second query in response to determining, from the behavior data, that a user submitted the second query after submitting the first query.

6. The method of claim 1 wherein:

at least some nodes of the one or more graphs represent queries submitted to the search engine; and

the implicit links include at least one implicit link that is established from a query to a web object in response to a determining, from the behavior data, that a user clicked on a link to the web object that was presented in search results provided by the search engine for the query.

7. The method of claim 1 wherein:

the implicit links include at least one implicit link that is established from a first web object to a second web object in response to a determining, from the behavior data, that a user;

clicked on a first link to the first web object, and then

clicked on a second link to the second web object;

both the first link and the second link were presented to the user in a search results page for a particular query submitted to the search engine.

8. The method of claim 1 wherein:

at least some nodes of the one or more graphs represent queries submitted to the search engine;

the implicit links include at least one implicit link that is established from a web object to a particular query in response to a determining, from the behavior data, that a user submitted the particular query after the user clicked on a link to the web object; and

the link to the web object was presented in search results provided by the search engine for another query that the user submitted to the search engine before said particular query.

9. The method of claim 1 wherein said one or more graphs include a web-query-click graph.

10. The method of claim 1 wherein said one or more graphs include a web-query-click-sponsored graph.

11. The method of claim 1 wherein:

said set of web objects includes a particular web page;

a particular web object is a web object that is generated for inclusion in search results;

said particular web page is a web object to which no other web page explicitly points; and

the implicit links include at least one implicit link from another web object to said particular web object.

12. The method of claim 11 wherein said at least one implicit link is generated in response to determining, from the behavior data, that a user selecting a link to said web object that was presented in search results for a particular query.

13. The method of claim 1 wherein said one or more graphs include a web-query-click-sponsored sequential graph.

14. The method of claim 1 wherein said one or more graphs include a graph with edges that reflect entire paths of searches and clicks that are recorded in said behavior data.

15. The method of claim 14 wherein said graph also includes edges that reflect implicit links (a) from nodes that represent web objects that were visited by users (b) to nodes that represent searches submitted by the users immediately after visiting said web objects.

16. The method of claim 1 wherein said one or more graphs include a query graph.

17. The method of claim 1 wherein said one or more graphs include a graph that includes both edges that correspond to implicit links, and edges that correspond to explicit links.

18. The method of claim 1 further comprising determining how to rank search results that include web objects based, at least in part, on said quality measures generated for said web objects.

19. The method of claim 18 wherein the step of determining how to rank search results includes determining how to rank one or more of sponsored results, images, or media.

20. The method of claim 1 wherein:

said set of web objects includes sponsored results; and

the method comprises determining which sponsored results to include with search results based, at least in part, on said quality measures generated for said sponsored results.

21. The method of claim 1 wherein the set of web objects includes queries submitted to the search engine.

22. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

23. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

24. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

25. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

26. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

27. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

28. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

29. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

30. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

31. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

32. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

33. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

34. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

35. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

36. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

37. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

38. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

39. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 18.

40. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 19.

41. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 20.

42. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 21.

43. The method of claim 1 wherein the first web object was in the previous query search results.

44. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 43.