Modifying ranking data based on document changes

• US 9,002,867 B1
• Filed: 12/30/2010
• Issued: 04/07/2015
• Est. Priority Date: 12/30/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Adams, Henele I., Kim, Hyung-Jin
• Primary Examiner(s): Yen, Syling
• Application Number:
  US12/982,633
• Time in Patent Office: 1,559 Days
• Field of Search: None
• US Class Current: 707/759
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media for determining a weighted overall quality of result statistic for a document. One method includes receiving quality of result data for a query and a plurality of versions of a document, determining a weighted overall quality of result statistic for the document with respect to the query including weighting each version specific quality of result statistic and combining the weighted version-specific quality of result statistics, wherein each quality of result statistic is weighted by a weight determined from at least a difference between content of a reference version of the document and content of the version of the document corresponding to the version specific quality of result statistic, and storing the weighted overall quality of result statistic and data associating the query and the document with the weighted overall quality of result statistic.

Claims

1. A computer-implemented method, comprising:

receiving a query and a current version of a document;

receiving quality of result data for a plurality of versions of the document and the query, the quality of result data specifying a respective version-specific quality of result statistic for each of the versions of the document with respect to the query;

calculating a weight for the version-specific quality of result statistics corresponding to each version of the document, wherein the weight for a particular version of the document is determined at least in part on an estimate of a difference between the particular version and the current version of the document, and wherein calculating the weight for a particular version of the document comprises;

obtaining a representation of the particular version of the document, wherein the representation is a first time distribution of shingles,

calculating a difference score by comparing the first time distribution of shingles representing the particular version of the document to a second time distribution of shingles representing the current version of the document, wherein each shingle is a contiguous subsequence of one or more tokens in the document, and wherein each shingle is associated with a particular time that the shingle is first observed in a version of the document such that a distribution of the times associated with the shingles in a version of the document corresponds to the representation of the version of the document, and

using the difference score to calculate a corresponding weight for the particular version of the document;

determining a weighted overall quality of result statistic for the document with respect to the query, wherein determining the weighted overall quality of result statistic comprises weighting each version-specific quality of result statistic with the calculated weight and combining the weighted version-specific quality of result statistics; and

associating the weighted overall quality of result statistic with the document.

2. The method of claim 1, wherein each of the plurality of versions of the document is stored at a same address at a different respective period of time.

3. The method of claim 2, wherein the address is a Uniform Resource Locator.

4. The method of claim 1, wherein the reference version of the document is a version of the document that was most-recently crawled by a web-crawler.

5. The method of claim 1, wherein determining the weighted overall quality of result statistic comprises:

determining a respective difference score for each of the plurality of versions of the document with reference to the reference version of the document, wherein the difference score for a particular version in the plurality of versions of the document and the reference version of the document measures a difference between a representation of the particular version and a representation of the reference version of the document; and

weighting each version-specific quality of result statistic by a weight derived from the difference score for the version of the document associated with the version-specific quality of result statistic.

6. The method of claim 5, wherein the representation of a version of the document comprises shingles extracted from the version of the document.

7. The method of claim 5, wherein the representation of a version of the document comprises a time distribution of shingles in the version of the document.

8. The method of claim 1, further comprising:

associating the document with a non-weighted overall quality of result statistic;

receiving the query, and in response to receiving the query, determining whether to select either the weighted overall quality of result statistic or the non-weighted overall quality of result statistic;

selecting either the weighted overall quality of result statistic or the non-weighted overall quality of result statistic in response to the determination; and

providing the selected overall quality of result statistic to a ranking engine implemented on one or more computers.

9. The method of claim 8, further comprising determining a difference score for the reference version of the document and a current version of the document, and wherein selecting either the weighted overall quality of result statistic or non-weighted overall quality of result statistic comprises selecting a statistic according to the difference score.

10. The method of claim 1, further comprising:

receiving an indication that the document has changed; and

updating the weighted overall quality of result statistic in response to the indication.

11. The method of claim 5, wherein the difference score is determined as an inverse of a similarity score, where the similarity score is defined as

12. The method of claim 5, wherein the difference score is determined as an inverse of a similarity score, where the similarity score is defined as

13. The method of claim 1, wherein calculating the weight further comprises calculating a number of times the document has changed as compared to a reference version of the document or an amount of time the reference version of the document was unchanged.

14. A system comprising:

one or more computers configured to perform operations, the operations comprising;

receiving a query and a current version of a document;

receiving quality of result data for a plurality of versions of the document and the query, the quality of result data specifying a respective version-specific quality of result statistic for each of the versions of the document with respect to the query;

calculating a weight for the version-specific quality of result statistics corresponding to each version of the document, wherein the weight for a particular version of the document is determined at least in part on an estimate of a difference between the particular version and the current version of the document, and wherein calculating the weight for a particular version of the document comprises;

obtaining a representation of the particular version of the document, wherein the representation is a first time distribution of shingles,

calculating a difference score by comparing the first time distribution of shingles representing the particular version of the document to a second time distribution of shingles representing the current version of the document, wherein each shingle is a contiguous subsequence of one or more tokens in the document, and wherein each shingle is associated with a particular time that the shingle is first observed in a version of the document such that a distribution of the times associated with the shingles in a version of the document corresponds to the representation of the version of the document, and

using the difference score to calculate a corresponding weight for the particular version of the document;

determining a weighted overall quality of result statistic for the document with respect to the query, wherein determining the weighted overall quality of result statistic comprises weighting each version-specific quality of result statistic with the calculated weight and combining the weighted version-specific quality of result statistics; and

associating the weighted overall quality of result statistic with the document.

15. The system of claim 14, wherein each of the plurality of versions of the document is stored at a same address at a different respective period of time.

16. The system of claim 15, wherein the address is a Uniform Resource Locator.

17. The system of claim 14, wherein the reference version of the document is a version of the document that was most-recently crawled by a web-crawler.

18. The system of claim 14, wherein determining the weighted overall quality of result statistic comprises:

determining a respective difference score for each of the plurality of versions of the document with reference to the reference version of the document, wherein the difference score for a particular version in the plurality of versions of the document and the reference version of the document measures a difference between a representation of the particular version and a representation of the reference version of the document; and

weighting each version-specific quality of result statistic by a weight derived from the difference score for the version of the document associated with the version-specific quality of result statistic.

19. The system of claim 18, wherein the representation of a version of the document comprises shingles extracted from the version of the document.

20. The system of claim 18, wherein the representation of a version of the document comprises a time distribution of shingles in the version of the document.

21. The system of claim 14, wherein the operations further comprise:

associating the document with a non-weighted overall quality of result statistic;

receiving the query, and in response to receiving the query, determining whether to select either the weighted overall quality of result statistic or the non-weighted overall quality of result statistic;

selecting either the weighted overall quality of result statistic or the non-weighted overall quality of result statistic in response to the determination; and

providing the selected overall quality of result statistic to a ranking engine implemented on one or more computers.

22. The system of claim 21, wherein the operations further comprise determining a difference score for the reference version of the document and a current version of the document, and wherein selecting either the weighted overall quality of result statistic or non-weighted overall quality of result statistic comprises selecting a statistic according to the difference score.

23. The system of claim 14, wherein the operations further comprise:

receiving an indication that the document has changed; and

updating the weighted overall quality of result statistic in response to the indication.

24. The system of claim 18, wherein the difference score is determined as an inverse of a similarity score, where the similarity score is defined as

25. The system of claim 18, wherein the difference score is determined as an inverse of a similarity score, where the similarity score is defined as

26. The system of claim 14, wherein calculating the weight further comprises calculating a number of times the document has changed as compared to a reference version of the document or an amount of time the reference version of the document was unchanged.

27. A computer-readable medium having instructions stored thereon, which, when executed by a processor, cause the processor to perform operations comprising:

receiving a query and a current version of a document;

receiving quality of result data for a plurality of versions of the document and the query, the quality of result data specifying a respective version-specific quality of result statistic for each of the versions of the document with respect to the query;

calculating a weight for the version-specific quality of result statistics corresponding to each version of the document, wherein the weight for a particular version of the document is determined at least in part on an estimate of a difference between the particular version and the current version of the document, and wherein calculating the weight for a particular version of the document comprises;

obtaining a representation of the particular version of the document, wherein the representation is a first time distribution of shingles,

calculating a difference score by comparing the first time distribution of shingles representing the particular version of the document to a second time distribution of shingles representing the current version of the document, wherein each shingle is a contiguous subsequence of one or more tokens in the document, and wherein each shingle is associated with a particular time that the shingle is first observed in a version of the document such that a distribution of the times associated with the shingles in a version of the document corresponds to the representation of the version of the document, and

using the difference score to calculate a corresponding weight for the particular version of the document;

determining a weighted overall quality of result statistic for the document with respect to the query, wherein determining the weighted overall quality of result statistic comprises weighting each version-specific quality of result statistic with the calculated weight and combining the weighted version-specific quality of result statistics; and

associating the weighted overall quality of result statistic with the document.

28. The computer-readable medium of claim 27, wherein each of the plurality of versions of the document is stored at a same address at a different respective period of time.

29. The computer-readable medium of claim 28, wherein the address is a Uniform Resource Locator.

30. The computer-readable medium of claim 27, wherein the reference version of the document is a version of the document that was most-recently crawled by a web-crawler.

31. The computer-readable medium of claim 27, wherein determining the weighted overall quality of result statistic comprises:

determining a respective difference score for each of the plurality of versions of the document with reference to the reference version of the document, wherein the difference score for a particular version in the plurality of versions of the document and the reference version of the document measures a difference between a representation of the particular version and a representation of the reference version of the document; and

weighting each version-specific quality of result statistic by a weight derived from the difference score for the version of the document associated with the version-specific quality of result statistic.

32. The computer-readable medium of claim 31, wherein the representation of a version of the document comprises shingles extracted from the version of the document.

33. The computer-readable medium of claim 31, wherein the representation of a version of the document comprises a time distribution of shingles in the version of the document.

34. The computer-readable medium of claim 27, further comprising:

associating the document with a non-weighted overall quality of result statistic;

receiving the query, and in response to receiving the query, determining whether to select either the weighted overall quality of result statistic or the non-weighted overall quality of result statistic;

selecting either the weighted overall quality of result statistic or the non-weighted overall quality of result statistic in response to the determination; and

providing the selected overall quality of result statistic to a ranking engine implemented on one or more computers.

35. The computer-readable medium of claim 34, further comprising determining a difference score for the reference version of the document and a current version of the document, and wherein selecting either the weighted overall quality of result statistic or non-weighted overall quality of result statistic comprises selecting a statistic according to the difference score.

36. The computer-readable medium of claim 27, further comprising:

receiving an indication that the document has changed; and

updating the weighted overall quality of result statistic in response to the indication.

37. The computer-readable medium of claim 31, wherein the difference score is determined as an inverse of a similarity score, where the similarity score is defined as

38. The computer-readable medium of claim 31, wherein the difference score is determined as an inverse of a similarity score, where the similarity score is defined as

39. The computer-readable medium of claim 27, wherein calculating the weight further comprises calculating a number of times the document has changed as compared to a reference version of the document or an amount of time the reference version of the document was unchanged.