User-sensitive pagerank

• US 7,624,104 B2
• Filed: 06/22/2006
• Issued: 11/24/2009
• Est. Priority Date: 06/22/2006
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Richardson; James E
• Application Number:
  US11/474,195
• Publication Number:
  US 20080010281A1
• Time in Patent Office: 1,251 Days
• Field of Search: 707 2- 7
• US Class Current: 1/1
• 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

A first component of an authority value is generated with reference to outbound links associated with a document and corresponding to a first subset of a plurality of documents. A second component of the authority value is generated with reference to a second subset of the plurality of documents that represent potential starting points for user sessions. 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 document. 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 by assigning a weight to each of a plurality of 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 by generating a teleportation distribution which includes a term for each document in a second subset of the plurality of documents, each of the second subset of documents representing a potential user session staffing point;

generating a third component of the authority value comprising a likelihood that a user session initiated by any of a population of users will end with the first document, the user session comprising a document sequence defined by navigation via links embedded in successive documents in the document sequence; and

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

wherein one or more of the weights assigned to the plurality of outbound links, the terms included in the teleportation distribution, or the likelihood that a user session will end with the first document is computed with reference to user data relating to at least some of the outbound links and the second subset of documents, wherein at least some of the user data comprises session data representing navigation among the plurality of documents by the population of users.

2. The method of claim 1 wherein each of the weights is derived with reference to a portion of the user data representing a frequency with which the corresponding outbound link was selected by the population of users.

3. The method of claim 1 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 one or more of demographic data or behavior data.

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

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

7. The method of claim 1 wherein each of the terms of the teleportation distribution is derived with reference to a portion of the user data representing relevance of the corresponding document among the population of users.

8. The method of claim 7 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 the population of users.

9. The method of claim 7 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 one or more of demographic data or behavior data.

10. The method of claim 1 wherein each of the terms of the teleportation distribution includes a constant nonzero component derived with reference to a number of the second subset of documents.

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

12. 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 one or more of demographic data or behavior data.

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

14. 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.

15. 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.

16. 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.

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

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

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