User-sensitive pagerank

• US 20080010281A1
• Filed: 06/22/2006
• Published: 01/10/2008
• Est. Priority Date: 06/22/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Tomkins, Andrew, Fayyad, Usama M., Berkhin, Pavel, Raghavan, Prabhakar
• Granted Patent: US 7,624,104 B2
• Time in Patent Office: Days
• US Class Current: 707/7
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Techniques are described for generating an authority value of a first one of a plurality of documents. A first component of the authority value is generated with reference to outbound links associated with the first document. The outbound links enable access to a first subset of the plurality of documents. A second component of the authority value is generated with reference to a second subset of the plurality of documents. Each of the second subset of documents represents a potential starting point for a user session. A third component of the authority value is generated representing a likelihood that a user session initiated by any of a population of users will end with the first document. The first, second, and third components of the authority value are combined to generate the authority value. At least one of the first, second, and third components of the authority value is computed with reference to user data relating to at least some of the outbound links and the second subset of documents.

Claims

1. A computer-implemented method for generating an authority value of a first one of a plurality of documents, comprising:

generating a first component of the authority value with reference to outbound links associated with the first document, the outbound links enabling access to a first subset of the plurality of documents;

generating a second component of the authority value with reference to a second subset of the plurality of documents, each of the second subset of documents representing a potential starting point for a user session;

generating a third component of the authority value representing a likelihood that a user session initiated by any of a population of users will end with the first document; and

combining the first, second, and third components of the authority value to generate the authority value;

wherein at least one of the first, second, and third components of the authority value is computed with reference to user data relating to at least some of the outbound links and the second subset of documents.

2. The method of claim 1 wherein generating the first component of the authority value comprises assigning a weight to each of the outbound links, each of the weights being derived with reference to a portion of the user data representing a frequency with which the corresponding outbound link was selected by a population of users.

3. The method of claim 2 wherein the plurality of documents may be represented by a graph, and each of the weights represents a likelihood that a user will traverse a directed edge of the graph associated with the corresponding outbound link.

4. The method of claim 2 wherein the population of users corresponds to a segment of a superset of users, the segment being selected from the superset of users with reference to at least one of demographic data and behavior data.

5. The method of claim 4 wherein the demographic and behavior data relate to any of user importance, user recency, user tenure, and user time spent.

6. The method of claim 2 wherein each of the weights includes a constant nonzero component derived with reference to a number of the outbound links.

7. The method of claim 2 wherein each of the weights is further derived with reference to a probabilistic distribution associated with the population of users.

8. The method of claim 1 wherein generating the second component of the authority value comprises generating a teleportation distribution which includes a term for each of the second subset of documents, each of the terms being derived with reference to a portion of the user data representing relevance of the corresponding document among a population of users.

9. The method of claim 8 wherein the relevance of the corresponding document is determined with reference to a frequency with which the corresponding document began a user session initiated by any of a population of users.

10. The method of claim 8 wherein the population of users corresponds to a segment of a superset of users, the segment being selected from the superset of users with reference to at least one of demographic data and behavior data.

11. The method of claim 10 wherein the demographic and behavior data relate to any of user importance, user recency, user tenure, and user time spent.

12. The method of claim 8 wherein each of the terms includes a constant nonzero component derived with reference to a number of the second subset of documents.

13. The method of claim 8 wherein each of the terms is further derived with reference to a probabilistic distribution associated with the population of users.

14. The method of claim 1 wherein the population of users corresponds to a segment of a superset of users, the segment being selected from the superset of users with reference to at least one of demographic data and behavior data.

15. The method of claim 14 wherein the demographic and behavior data relate to any of user importance, user recency, user tenure, and user time spent.

16. The method of claim 1 wherein the third component of the authority value comprises a teleportation coefficient which includes a constant nonzero component.

17. The method of claim 1 wherein the third component of the authority value comprises a teleportation coefficient derived with reference to a probabilistic distribution associated with the population of users.

18. The method of claim 1 wherein each of the first, second, and third components of the authority value is generated with reference to the user data.

19. The method of claim 1 wherein both of the first and second components of the authority value are generated with reference to the user data.

20. The method of claim 1 wherein the first document comprises any of a page, a file, a site, a host, a domain.

21. The method of claim 1 further comprising ranking the first document among a plurality of search results with reference to the authority value.

22. The method of claim 1 further comprising facilitating decision making by a web crawling application with reference to the authority value.

23. The method of claim 1 further comprising periodically regenerating the authority value to reflect changes in the user data.

24. A computer-implemented method for generating an authority value of a first one of a plurality of documents, comprising:

identifying text associated with each of a plurality of inbound links enabling access to the first document;

assigning a weight to the text associated with each of the inbound links, each of the weights being derived with reference to user data representing a frequency with which the corresponding inbound link was selected by a population of users; and

generating the authority value with reference to the weights.

25. The method of claim 24 wherein the plurality of documents may be represented by a graph, and each of the weights represents a likelihood that a user will traverse a directed edge of the graph associated with the corresponding inbound link.

26. The method of claim 24 wherein the population of users corresponds to a segment of a superset of users, the segment being selected from the superset of users with reference to at least one of demographic data and behavior data.

27. The method of claim 26 wherein the demographic and behavior data relate to any of user importance, user recency, user tenure, and user time spent.

28. The method of claim 24 wherein each of the weights is further derived with reference to a probabilistic distribution associated with the population of users.

29. The method of claim 24 wherein the first document comprises any of a page, a file, a site, a host, a domain.

30. The method of claim 24 further comprising ranking the first document among a plurality of search results with reference to the authority value.

31. The method of claim 24 further comprising periodically regenerating the authority value to reflect changes in the user data.