Document ranking using word relationships

• US 7,996,379 B1
• Filed: 02/01/2008
• Issued: 08/09/2011
• Est. Priority Date: 02/01/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jain, Sharad
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US12/024,944
• Time in Patent Office: 1,285 Days
• Field of Search: 707/5, 707/6, 707/706, 709/204
• US Class Current: 707/706
• CPC Class Codes: G06F 16/33 Querying
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Methods, systems, and apparatus, including computer program products, for scoring documents. A plurality of documents with an initial ordering is received. Local term relationships between terms in the plurality of documents are identified, each local term relationship being a relationship between a pair of terms in a respective document. Relationships among the documents in the plurality of documents are determined based on the local term relationships and on the initial order of the documents. A respective score is determined for each document in the plurality of documents based on the document relationships.

Claims

1. A method comprising:

receiving a plurality of documents, the plurality of documents having an initial order;

identifying local term relationships between terms in the plurality of documents, each local term relationship being a relationship between a pair of terms in a respective document, wherein identifying local term relationships between terms in the documents comprises generating, for each of the documents in the plurality of documents, a local term relationships graph, the local term relationships graph representing the local term relationships in the respective document;

determining relationships among the documents in the plurality of documents based on the local term relationships and on the initial order of the documents, wherein determining relationships between the documents based on the local term relationships and the initial order of the documents within the plurality of documents comprises;

generating a global term relationships graph based on the local term relationships graphs; and

generating a document relationships graph based on the global term relationships graph; and

determining a respective score for each document in the plurality of documents based on the document relationships.

2. The method of claim 1, further comprising:

determining a score-based order of the documents based on the scores; and

presenting the documents in the score-based order.

3. The method of claim 2, wherein the plurality of documents satisfies a particular search query and the initial order is an order based on a measure of relevance of the respective documents to the particular search query.

4. The method of claim 1, wherein identifying local term relationships comprises identifying that a local term relationship exists between a pair of terms in a first document if each term in the pair of terms is located in a same paragraph within the first document.

5. The method of claim 1, further comprising, for a first local term relationship, determining a magnitude of the first local term relationship based on at least one of a difference between positions in the document of the pair of terms in the first local term relationship, and positions in the document of the pair of terms in the first local term relationship.

6. The method of claim 1, wherein determining relationships among the documents based on the local term relationships comprises:

selecting at least a subset of the local term relationships in accordance with predefined criteria; and

determining the document relationships using the selected local term relationships.

7. The method of claim 6, further comprising determining a magnitude for each of the identified local term relationships, wherein a magnitude for a respective local term relationship is determined based on at least one of a difference between positions in the document of the pair of terms in the respective local term relationship, and positions in the document of the pair of terms in the respective local term relationship;

and

wherein selecting at least a subset of the local term relationships in accordance with predefined criteria comprises selecting the subset of the local term relationships based on the magnitudes of the local term relationships.

8. The method of claim 1, further comprising determining a score-based order of the documents based on the document, relationships, wherein determining the score-based order comprises:

performing a link analysis of the document relationships graph;

determining respective scores for the documents based on the link analysis; and

ordering the documents by their respective scores.

9. The method of claim 1, wherein identifying local term relationships between terms in the documents comprises:

identifying a plurality of terms in a first document;

determining a score for each of the identified terms;

selecting a subset of the identified terms based on the scores of the identified terms; and

identifying local term relationships among the selected subset of terms.

10. The method of claim 9, wherein determining scores for the identified terms comprises determining a score for an identified term based on a number of occurrences of the identified term in the first document.

31. The method of claim 1, wherein each local term relationships graph includes nodes representing terms and edges representing relationships between terms.

34. The method of claim 1, wherein the global term relationships graph includes nodes representing terms and edges representing that nodes having a connecting edge in at least one of the local term relationships graphs.

37. The method of claim 1, wherein the document relationships graph includes nodes representing documents and edges representing relationships between documents based on shared semantics.

40. The method of claim 9, wherein selecting a subset of the identified terms based on the scores of the identified terms includes selecting terms having scores above a threshold.

41. The method of claim 9, wherein selecting a subset of the identified terms based on the scores of the identified terms includes selecting a number of the highest scoring terms.

11. A system, comprising:

a computer-readable medium;

one or more processors; and

instructions stored in the computer-readable medium and configured for execution by the one or more processors, the instructions comprising instructions to;

receive a plurality of documents, the plurality of documents having an initial order;

identify local term relationships between terms in the plurality of documents, each local term relationship being a relationship between a pair of terms in a respective document, wherein identifying local term relationships between terms in the documents comprises generating, for each of the documents in the plurality of documents, a local term relationships graph, the local term relationships graph representing the local term relationships in the respective document;

determine relationships among the documents in the plurality of documents based on the local term relationships and on the initial order of the documents, wherein determining relationships between the documents based on the local term relationships and the initial order of the documents within the plurality of documents comprises;

generating a global term relationships graph based on the local term relationships graphs; and

generating a document relationships graph based on the global term relationships graph; and

determine a respective score for each document in the plurality of documents based on the document relationships.

12. The system of claim 11, further comprising instructions to:

determine a score-based order of the documents based on the scores; and

present the documents in the score-based order.

13. The system of claim 12, wherein the plurality of documents satisfies a particular search query and the initial order is an order based on a measure of relevance of the respective documents to the particular search query.

14. The system of claim 11, further comprising instructions to identify that a local term relationship exists between a pair of terms in a first document if each term in the pair of terms is located in a same paragraph within the first document.

15. The system of claim 11, further comprising instructions to, for a first local term relationship, determine a magnitude of the first local term relationship based on at least one of a difference between positions in the document of the pair of terms in the first local term relationship, and positions in the document of the pair of terms in the first local term relationship.

16. The system of claim 11, further comprising instructions to:

select at least a subset of the local term relationships in accordance with predefined criteria; and

determine the document relationships using the selected local term relationships.

17. The system of claim 16, further comprising instructions to:

determine a magnitude for each of the identified local term relationships, wherein a magnitude for a respective local term relationship is determined based on at least one of a difference between positions in the document of the pair of terms in the respective local term relationship, and positions in the document of the pair of terms in the respective local term relationship; and

select the subset of the local term relationships based on the magnitudes of the local term relationships.

18. The system of claim 11, further comprising instructions to determine a score-based order of the documents based on the document relationships, including instructions to:

perform a link analysis of the document relationships graph;

determine respective scores for the documents based on the link analysis; and

order the documents by their respective scores.

19. The system of claim 11, further comprising instructions to:

identify a plurality of terms in a first document;

determine a score for each of the identified terms;

select a subset of the identified terms based on the scores of the identified terms; and

identify local term relationships among the selected subset of terms.

20. The system of claim 19, further comprising instructions to determining a score for an identified term based on a number of occurrences of the identified term in the first document.

32. The system of claim 11, wherein each local term relationships graph includes nodes representing terms and edges representing relationships between terms.

35. The system of claim 11, wherein the global term relationships graph includes nodes representing terms and edges representing that nodes having a connecting edge in at least one of the local term relationships graphs.

38. The system of claim 11, wherein the document relationships graph includes nodes representing documents and edges representing relationships between documents based on shared semantics.

42. The system of claim 19, wherein selecting a subset of the identified terms based on the scores of the identified terms includes selecting terms having scores above a threshold.

43. The system of claim 19, wherein selecting a subset of the identified terms based on the scores of the identified terms includes selecting a number of the highest scoring terms.

21. A computer program product, encoded on a computer-readable medium, operable to cause a data processing apparatus to perform operations comprising:

receiving a plurality of documents, the plurality of documents having an initial order;

identifying local term relationships between terms in the plurality of documents, each local term relationship being a relationship between a pair of terms in a respective document, wherein identifying local term relationships between terms in the documents comprises generating, for each of the documents in the plurality of documents, a local term relationships graph, the local term relationships graph representing the local term relationships in the respective document;

determining relationships among the documents in the plurality of documents based on the local term relationships and on the initial order of the documents, wherein determining relationships between the documents based on the local term relationships and the initial order of the documents within the plurality of documents comprises;

generating a global term relationships graph based on the local term relationships graphs; and

generating a document relationships graph based on the global term relationships graph; and

determining a respective score for each document in the plurality of documents based on the document relationships.

22. The computer program product of claim 21, further comprising:

determining a score-based order of the documents based on the scores; and

presenting the documents in the score-based order.

23. The computer program product of claim 22, wherein the plurality of documents satisfies a particular search query and the initial order is an order based on a measure of relevance of the respective documents to the particular search query.

24. The computer program product of claim 21, wherein identifying local term relationships comprises identifying that a local term relationship exists between a pair of terms in a first document if each term in the pair of terms is located in a same paragraph within the first document.

25. The computer program product of claim 21, the operations further comprising, for a first local term relationship, determining a magnitude of the first local term relationship based on at least one of a difference between positions in the document of the pair of terms in the first local term relationship, and positions in the document of the pair of terms in the first local term relationship.

26. The computer program product of claim 21, wherein determining relationships among the documents based on the local term relationships comprises:

selecting at least a subset of the local term relationships in accordance with predefined criteria; and

determining the document relationships using the selected local term relationships.

27. The computer program product of claim 26, the operations further comprising determining a magnitude for each of the identified local term relationships, wherein a magnitude for a respective local term relationship is determined based on at least one of a difference between positions in the document of the pair of terms in the respective local term relationship, and positions in the document of the pair of terms in the respective local term relationship;

and

wherein selecting at least a subset of the local term relationships in accordance with predefined criteria comprises selecting the subset of the local term relationships based on the magnitudes of the local term relationships.

28. The computer program product of claim 21, the operations further comprising determining a score-based order of the documents based on the document relationships, wherein determining the score-based order comprises:

performing a link analysis of the document relationships graph;

determining respective scores for the documents based on the link analysis; and

ordering the documents by their respective scores.

29. The computer program product of claim 21, wherein identifying local term relationships between terms in the documents comprises:

identifying a plurality of terms in a first document;

determining a score for each of the identified terms;

selecting a subset of the identified terms based on the scores of the identified terms; and

identifying local term relationships among the selected subset of terms.

30. The computer program product of claim 29, wherein determining scores for the identified terms comprises determining a score for an identified term based on a number of occurrences of the identified term in the first document.

33. The computer program product of claim 21, wherein each local term relationships graph includes nodes representing terms and edges representing relationships between terms.

36. The computer program product of claim 21, wherein the global term relationships graph includes nodes representing terms and edges representing that nodes having a connecting edge in at least one of the local term relationships graphs.

39. The computer program product of claim 21, wherein the document relationships graph includes nodes representing documents and edges representing relationships between documents based on shared semantics.

44. The computer program product of claim 29, wherein selecting a subset of the identified terms based on the scores of the identified terms includes selecting terms having scores above a threshold.

45. The computer program product of claim 29, wherein selecting a subset of the identified terms based on the scores of the identified terms includes selecting a number of the highest scoring terms.