User-sensitive PageRank

• US 9,495,452 B2
• Filed: 10/09/2009
• Issued: 11/15/2016
• 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: Berkhin, Pavel, Fayyad, Usama M., Raghavan, Prabhakar, Tomkins, Andrew
• Primary Examiner(s): Richardson, James E
• Application Number:
  US12/576,679
• Publication Number:
  US 20100023513A1
• Time in Patent Office: 2,594 Days
• Field of Search: 707/727, 707/751, 707/723, 707/726, 707732-734, 707/748, 707/999.003, 707/999.107
• 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

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, comprising:

identifying text associated with each of a plurality of inbound links enabling access to a first document of a plurality of documents, wherein each of the plurality of inbound links is a link from another document to the first document, wherein the text is anchor text;

assigning a text weight to the text associated with each of the plurality of inbound links, each of the text weights being derived with reference to user data, a first portion of the user data representing a frequency with which the corresponding inbound link was selected by a population of a plurality of users, the population of the plurality of users having a set of user characteristics, and a second portion of the user data including user weights assigned to users in the population of users, the user weights being based, at least in part, upon an age range distribution, the user characteristics including one or more demographics, the one or more demographics including age;

generating an authority value of the first document based, at least in part, upon the text weights assigned to the text associated with each of the plurality of inbound links;

receiving a search query; and

ranking the first document among a plurality of search results with reference to the authority value.

2. The method of claim 1 wherein the plurality of documents are represented by a graph, and the text weight associated with each of the inbound links represents a likelihood that a user will traverse a directed edge of the graph associated with the corresponding inbound link.

3. The method of claim 1 wherein the population of users corresponds to a particular 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.

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

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

6. The method of claim 1, wherein the authority value represents a likelihood that a user session initiated by a user will include accessing the first document.

7. The method of claim 1, wherein the authority value represents a likelihood that a user session initiated by any of the population of users will include accessing the first document.

8. The method of claim 1, wherein each of the text weights indicates a likelihood that a user will browse from another page to the first document.

9. The method of claim 1, wherein each of the text weights indicates a likelihood that any of the population of users will browse from another page to the first document.

10. The method of claim 1, wherein the plurality of inbound links are not search results.

11. The method of claim 1, wherein the user characteristics comprise the demographics.

12. The method of claim 1, wherein the demographics comprise age such that different user weights are assigned to different users based upon their age.

13. The method of claim 1, wherein ranking is further performed based, at least in part, on the anchor text associated with each of the plurality of inbound links.

14. The method of claim 1, wherein the plurality of search results are identified in response to receiving a search query received from a user in the population of users.

15. The method of claim 1, wherein the one or more demographics further comprise gender.

16. A system, comprising:

one or more computing devices comprising

at least one processor, and

at least one memory,

wherein the at least one processor or the at least one memory is configured to;

identify text associated with each of a plurality of inbound links enabling access to a first document of a plurality of documents, wherein each of the plurality of inbound links is a link from another document to the first document, wherein the text is anchor text;

assign a text weight to the text associated with each of the plurality of inbound links, each of the text weights being derived with reference to user data, a first portion of the user data representing a frequency with which the corresponding inbound link was selected by a population of a plurality of users, the population of the plurality of users having a set of user characteristics, and a second portion including user weights assigned to users in the population of users, the user weights being based, at least in part, upon an age range distribution the user characteristics including one or more demographics, the one or more demographics including age; and

generate an authority value of the first document based, at least in part, upon the text weights assigned to the text associated with each of the plurality of inbound links;

receive a search query; and

rank the first document among a plurality of search results with reference to the authority value.

17. The system of claim 16 wherein the plurality of documents is represented by a graph, and the text weight associated with each of the inbound links represents a likelihood that a user will traverse a directed edge of the graph associated with the corresponding inbound link.

18. The system of claim 16 wherein the population of users corresponds to a particular 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.

19. The system of claim 16 wherein each of the text weights is further derived with reference to a probabilistic distribution associated with the population of users.

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

21. A computer program product comprising at least one non-transitory computer-readable storage medium having computer instructions stored therein that are configured to cause one or more computing devices to:

identify text associated with each of a plurality of inbound links enabling access to a first document of a plurality of documents, wherein each of the plurality of inbound links is a link from another document to the first document, wherein the text is anchor text;

assign a text weight to the text associated with each of the plurality of inbound links, each of the text weights being derived with reference to user data, a first portion of the user data representing a frequency with which the corresponding inbound link was selected by a population of a plurality of users, the population of the plurality of users having a set of user characteristics, and a second portion of the user data including user weights assigned to users in the population of users, the user weights being based, at least in part, upon an age range distribution, the user characteristics including one or more demographics, the one or more demographics including age;

generate an authority value of the first document based, at least in part, upon the text weights assigned to the text associated with each of the plurality of inbound links;

receive a search query; and

rank the first document among a plurality of search results with reference to the authority value.

22. The computer program product of claim 21 wherein the plurality of documents is represented by a graph, and the text weight associated with each of the inbound links represents a likelihood that a user will traverse a directed edge of the graph associated with the corresponding inbound link.

23. The computer program product of claim 21 wherein the population of users corresponds to a particular 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.

24. The computer program product of claim 21 wherein each of the text weights is further derived with reference to a probabilistic distribution associated with the population of users.

25. The computer program product of claim 21 wherein the first document comprises any of a page, a file, a site, a host, a domain.