Search result ranking based on trust

• US 8,352,467 B1
• Filed: 09/02/2009
• Issued: 01/08/2013
• Est. Priority Date: 05/09/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Guha, Ramanathan V.
• Primary Examiner(s): Shmatov, Alexey
• Application Number:
  US12/552,956
• Time in Patent Office: 1,224 Days
• Field of Search: 707/999.1, 707/708, 707/754, 707/727
• US Class Current: 707/727
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A search engine system provides search results that are ranked according to a measure of the trust associated with entities that have provided labels for the documents in the search results. A search engine receives a query and selects documents relevant to the query. The search engine also determines labels associated with selected documents, and the trust ranks of the entities that provided the labels. The trust ranks are used to determine trust factors for the respective documents. The trust factors are used to adjust information retrieval scores of the documents. The search results are then ranked based on the adjusted information retrieval scores.

Claims

1. A method performed by a data processing apparatus, the method comprising:

determining one or more trust relationships between a user and one or more entities based on a frequency with which the user visits one or more resources associated with the one or more entities;

receiving a search query from the user;

identifying one or more resources responsive to the search query, wherein each of the resources is associated with one or more annotation label terms assigned by the one or more entities;

determining whether a query label term matches any of the one or more annotation label terms;

identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are assigned by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources;

determining a relevance score of each of one or more resources that have the annotation label term based on the respective trust rank, the relevance score indicating a degree of relevance between the respective resource and the query term;

ranking each of the one or more resources based on the respective relevance scores; and

providing the ranking.

2. The method of claim 1, further comprising:

annotating, with a name of the respective entity, indicia identifying each resource of the ranked search result set; and

providing the indicia in a response to the search query.

3. The method of claim 2, wherein annotating further comprises:

annotating, with the matching label term associated with each resource, the indicia identifying each resource of the ranked search result set.

4. The method of claim 1, wherein:

identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises;

calculating an aggregated trust rank based on two or more trust ranks; and

determining a relevance score of each of one or more resources that have the annotation label term based on the respective trust rank, the relevance score indicating a degree of relevance between the respective resource and the query term comprises;

determining the relevance score of each of the one or more resources that have the annotation label term based on the respective aggregated trust rank.

5. The method of claim 4, wherein calculating an aggregated trust rank comprises calculating an aggregated trust rank according to a weighing function, and the weighting function is one of a linear weighting function, an asymptotic weighting function, a decaying weighting function or a sigmoid weighting function.

6. The method of claim 1, further comprising altering a trust relationship in an entity based on passage of time;

wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises identifying a trust rank based on the altered trust relationship.

7. The method of claim 6, wherein altering the trust relationship in an entity based on passage of time comprises determining a strength of a trust relationship that has decayed over time.

8. The method of claim 1, wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises:

calculating, for each of the one or more annotation label terms matching the query label term, an aggregated topic-specific trust rank of the entity that associated the annotation label term with the resource based on topic-specific trust information for the entity for a plurality of different topics.

9. The method of claim 8, wherein:

the one or more entities have different topic-specific trust ranks for the plurality of different topics; and

calculating, for each of the one or more annotation label terms matching the query label term, the aggregated topic-specific trust rank of the entity that associated the annotation label term with the resource based on topic-specific trust information for the entity for a plurality of different topics comprises;

aggregating the different topic-specific trust ranks for the entity for the plurality of different topics according to one or more topical hierarchies.

10. The method of claim 1, wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises:

calculating, for an annotation label matching the query label term, an aggregated trust rank based on two or more topic-specific trust ranks of different entities that each associated the annotation label to the corresponding resource.

11. The method of claim 1, wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises:

identifying a component of an eigenvector for a matrix of trust relationship information, the component corresponding to the entity that associated the annotation label term with the resource.

12. The method of claim 1, wherein determining the one or more trust relationships between the user and the one or more entities based on the frequency with which the user visits the one or more resources associated with the one or more entities comprises:

determining that the user visits a website associated with a particular entity with a predetermined frequency; and

determining that the user trusts the particular entity based on determining that the user visits the website associated with the particular entity with the predetermined frequency.

13. The method of claim 1, further comprising determining a trust relationship between the user and a particular entity based on a link from a web page associated with the user to a web page associated with the particular entity.

14. The method of claim 1, further comprising determining a trust relationship between the user and a particular entity based on a vanity list that identifies the user and is associated with the particular entity.

15. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

determining one or more trust relationships between a user and one or more entities based on a frequency with which the user visits one or more resources associated with the one or more entities;

receiving a search query from the user;

identifying one or more resources responsive to the search query associated with the user, wherein each of the resources is associated with one or more annotation label terms assigned by the one or more entities;

determining whether a query label term matches any of the one or more annotation label terms;

identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are assigned by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources;

determining a relevance score of each of one or more resources that have the annotation label term based on the respective trust rank, the relevance score indicating a degree of relevance between the respective resource and the query term;

ranking each of the one or more resources based on the respective relevance scores; and

providing the ranking.

16. The system of claim 15, wherein the operations further comprise:

annotating, with a name of the respective entity, indicia identifying each resource of the ranked search result set; and

providing the indicia in a response to the search query.

17. The system of claim 16, wherein annotating further comprises:

annotating, with the matching label term associated with each resource, the indicia identifying each resource of the ranked search result set.

18. The system of claim 15, wherein:

identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises;

calculating an aggregated trust rank based on two or more trust ranks; and

determining a relevance score of each of one or more resources that have the annotation label term based on the respective trust rank, the relevance score indicating a degree of relevance between the respective resource and the query term comprises;

determining the relevance score of each of the one or more resources that have the annotation label term based on the respective aggregated trust rank.

19. The system of claim 18, wherein calculating an aggregated trust rank comprises calculating an aggregated trust rank according to a weighing function, and the weighting function is one of a linear weighting function, an asymptotic weighting function, a decaying weighting function or a sigmoid weighting function.

20. The system of claim 15, wherein the operations further comprise altering a trust relationship in an entity based on passage of time;

and

wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises identifying a trust rank based on the altered trust relationship.

21. The system of claim 20, wherein altering the trust relationship in an entity based on passage of time comprises determining a strength of a trust relationship that has decayed over time.

22. The system of claim 15, wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises:

calculating, for each of the one or more annotation label terms matching the query label term, an aggregated topic-specific trust rank of the entity that associated the annotation label term with the resource based on topic-specific trust information for the entity for a plurality of different topics.

23. The system of claim 22, wherein:

the one or more entities have different topic-specific trust ranks for the plurality of different topics; and

calculating, for each of the one or more annotation label terms matching the query label term, the aggregated topic-specific trust rank of the entity that associated the annotation label term with the resource based on topic-specific trust information for the entity for a plurality of different topics comprises;

aggregating the different topic-specific trust ranks for the entity for the plurality of different topics according to one or more topical hierarchies.

24. The system of claim 15, wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises:

calculating, for an annotation label matching the query label term, an aggregated trust rank based on two or more topic-specific trust ranks of different entities that each associated the annotation label to the corresponding resource.

25. The system of claim 15, wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises:

identifying a component of an eigenvector for a matrix of trust relationship information, the component corresponding to the entity that associated the annotation label term with the resource.

26. The system of claim 15, wherein determining the one or more trust relationships between the user and the one or more entities based on the frequency with which the user visits the one or more resources associated with the one or more entities comprises:

determining that the user visits a web page associated with a particular entity with a predetermined frequency; and

determining that the user trusts the particular entity based on determining that the user visits the web page associated with the particular entity with the predetermined frequency.

27. The system of claim 15, wherein the operations further comprise determining a trust relationship between the user and a particular entity based on a link from a web page associated with the user to a web page associated with the particular entity.

28. The system of claim 15, wherein the operations further comprise determining a trust relationship between the user and a particular entity based on a vanity list that identifies the user and is associated with the particular entity.

29. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

determining one or more trust relationships between a user and one or more entities based on a frequency with which the user visits one or more resources associated with the one or more entities;

receiving a search query from the user;

identifying one or more resources responsive to the search query associated with the user, wherein each of the resources is associated with one or more annotation label terms assigned by the one or more entities;

determining whether a query label term matches any of the one or more annotation label terms;

identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are assigned by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources;

determining a relevance score of each of one or more resources that have the annotation label term based on the respective trust rank, the relevance score indicating a degree of relevance between the respective resource and the query term;

ranking each of the one or more resources based on the respective relevance scores; and

providing the ranking.

30. The non-transitory computer storage medium of claim 29, further comprising:

annotating, with a name of the respective entity, indicia identifying each resource of the ranked search result set; and

providing the indicia in a response to the search query.

31. The non-transitory computer storage medium of claim 30, wherein annotating further comprises:

annotating, with the matching label term associated with each resource, the indicia identifying each resource of the ranked search result set.

32. The non-transitory computer storage medium of claim 29, wherein:

identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises;

calculating an aggregated trust rank based on two or more trust ranks; and

determining a relevance score of each of one or more resources that have the annotation label term based on the respective trust rank, the relevance score indicating a degree of relevance between the respective resource and the query term comprises;

determining the relevance score of each of the one or more resources that have the annotation label term based on the respective aggregated trust rank.

33. The non-transitory computer storage medium of claim 32, wherein calculating an aggregated trust rank comprises calculating an aggregated trust rank according to a weighing function, and the weighting function is one of a linear weighting function, an asymptotic weighting function, a decaying weighting function or a sigmoid weighting function.

34. The non-transitory computer storage medium of claim 29, wherein the operations further comprise altering a trust relationship in an entity based on passage of time;

wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises identifying a topic-specific trust rank based on the altered trust relationship.

35. The non-transitory computer storage medium of claim 34, wherein altering the trust relationship in an entity based on passage of time comprises determining a strength of a trust relationship that has decayed over time.

36. The non-transitory computer storage medium of claim 29, wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises:

calculating, for each of the one or more annotation label terms matching the query label term, an aggregated topic-specific trust rank of the entity that associated the annotation label term with the resource based on topic-specific trust information for the entity for a plurality of different topics.

37. The non-transitory computer storage medium of claim 36, wherein:

the one or more entities have different topic-specific trust ranks for the plurality of different topics; and

calculating, for each of the one or more annotation label terms matching the query label term, the aggregated topic-specific trust rank of the entity that associated the annotation label term with the resource based on topic-specific trust information for the entity for a plurality of different topics comprises;

aggregating the different topic-specific trust ranks for the entity for the plurality of different topics according to one or more topical hierarchies.

38. The non-transitory computer storage medium of claim 29, wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises:

calculating, for an annotation label matching the query label term, an aggregated trust rank based on two or more topic-specific trust ranks of different entities that each associated the annotation label to the corresponding resource.

39. The non-transitory computer storage medium of claim 29, wherein identifying, for each of the one or more annotation label terms matching the query label term, a trust rank of the entity that associated the annotation label term with the resource, each trust rank indicating a level of trust for annotation label terms that are associated by the entity, and each trust rank being based on the determined one or more trust relationships that are based on the frequency with which the user visits the one or more resources comprises:

identifying a component of an eigenvector for a matrix of trust relationship information, the component corresponding to the entity that associated the annotation label term with the resource.

40. The non-transitory computer storage medium of claim 29, wherein determining the one or more trust relationships between the user and the one or more entities based on the frequency with which the user visits the one or more resources associated with the one or more entities of the user comprises:

determining that the user visits a web page associated with a particular entity with a predetermined frequency; and

determining that the user trusts the particular entity based on determining that the user visits the web page associated with the particular entity with the predetermined frequency.

41. The non-transitory computer storage medium of claim 29, wherein the operations further comprise determining a trust relationship between the user and a particular entity based on a link from a web page associated with the user to a web page associated with the particular entity.

42. The non-transitory computer storage medium of claim 29, wherein the operations further comprise determining a trust relationship between the user and a particular entity based on a vanity list that identifies the user and is associated with the particular entity.