Minimizing visibility of stale content in web searching including revising web crawl intervals of documents

• US 7,987,172 B1
• Filed: 08/30/2004
• Issued: 07/26/2011
• Est. Priority Date: 08/30/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Carver, Anton P. T.
• Primary Examiner(s): Lu; Charles E
• Application Number:
  US10/930,280
• Time in Patent Office: 2,521 Days
• Field of Search: 707/3, 707/104.1, 707/10, 707/709
• US Class Current: 707/709
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method and system is disclosed for associating an appropriate web crawl interval with a document so that the probability of the document'"'"'s stale content being used by a search engine is below an acceptable level when the search engine crawls the document at its associated web crawl interval. The web crawl interval of a document is determined through an iterative process and updated dynamically by the search engine after every visit to the document by a web crawler. A multi-tier data structure is employed for managing the web crawl order of billions of documents on the Internet. The search engine may move a document from one tier to another if its web crawl interval is changed significantly.

Claims

1. A method for scheduling documents to be crawled by a search engine in an appropriate order to reduce visibility of stale content in web searching, comprising:

on a computer system having one or more processors and memory storing one or more programs for execution by the one or more processors;

associating with each of a plurality of documents a respective initial web crawl interval, wherein the initial web crawl interval is determined based at least in part on a document'"'"'s importance metric;

retrieving each of the plurality of documents from a respective host at one or more times associated with each document'"'"'s respective initial web crawl interval;

associating a revised web crawl interval with a respective document of the plurality of documents based on the document'"'"'s respective initial web crawl interval and any changes to content of the document;

partitioning the plurality of documents into multiple tiers according to their respective web crawl intervals, each tier having a distinct associated range of web crawl intervals, including storing data for each tier identifying documents in the plurality of documents assigned to that tier in accordance with the documents'"'"' respective web crawl intervals;

for each tier of the multiple tiers, determining a web crawl order for the documents assigned to the tier in accordance with their respective revised web crawl interval; and

moving a respective document between tiers of the multiple tiers when the respective revised web crawl interval of the respective document is associated with a different tier of the multiple tiers than a previous web crawl interval of the respective document.

2. The method of claim 1, including updating the web crawl interval of a document after retrieving a new copy of the document'"'"'s content from its host and detecting content changes to the document based on the new copy.

3. The method of claim 1, further comprising:

determining for respective documents of the plurality of documents, content update rates of the respective documents, user click rates of the respective documents, and at least one document importance metric of the respective documents;

associating the revised web crawl interval with each document of the plurality of documents based on the document'"'"'s respective initial web crawl interval, any changes to content of the document, the user click rate of the document, and the at least one document importance metric of the document; and

downloading and recording new copies of at least a subset of the documents in accordance with the determined web crawl order.

4. The method of claim 2, including updating the web crawl interval of the document to be less than the initial web crawl interval when the document'"'"'s content has changed, and updating the web crawl interval to be more than the initial web crawl interval when the document'"'"'s content has not changed.

5. The method of claim 2, further comprising,

identifying a first average interval between times where the document'"'"'s content has not changed;

identifying a second average interval between times where the document'"'"'s content has changed; and

updating the web crawl interval of the document based on the first average interval and the second average interval.

6. The method of claim 5, wherein the web crawl interval is not updated if the first average interval is greater than the second average interval.

7. The method of claim 5, wherein the web crawl interval is updated in accordance with the first average interval if the first average interval is greater than the second average interval and the document'"'"'s content has not changed, and is updated in accordance with the second average interval if the document'"'"'s content has changed.

8. The method of claim 5, wherein the web crawl interval is updated in accordance with an average between the first average interval and the second average interval if the first average interval is less than the second average interval.

9. The method of claim 2, wherein the computer system considers critical content changes to the document and ignores all non-critical content changes to the document when updating the document'"'"'s web crawl interval.

10. The method of claim 1, wherein the initial web crawl interval of a document assigned to a respective tier is determined based at least in part on an average web crawl interval of all other documents assigned to the respective tier.

11. The method of claim 1, wherein the initial web crawl interval of the document is determined in accordance with a score corresponding to the document'"'"'s popularity.

12. The method of claim 1, wherein the revised web crawl interval of a document is smaller than the document'"'"'s content update interval and larger than half of the document'"'"'s content update interval.

13. The method of claim 12, wherein the search engine dynamically adjusts the revised web crawl interval of the document after a respective web crawler retrieves a new copy of the document'"'"'s content.

14. The method of claim 1, wherein the revised web crawl interval of a document is a time interval such that the search engine, on average, retrieves each unique version of document content at least twice according to the revised web crawl interval.

15. The method of claim 1, wherein the revised web crawl interval of a document is determined in accordance with the document'"'"'s user click interval when the document'"'"'s user click rate is larger than the document'"'"'s content update rate.

30. The method of claim 1, wherein the changes to the content of a document comprise critical content changes and non-critical content changes, and the computer system considers the critical content changes to the document and ignores the non-critical content changes to the document when associating a revised web crawl interval with the document.

16. A search engine system, for scheduling documents to be crawled by a search engine in an appropriate order to reduce visibility of stale content in web searching, comprising:

one or more central processing units for executing programs;

memory storing a web crawl order scheduler to be executed by the one or more central processing units;

the web crawl order scheduler comprising;

instructions for associating with each of a plurality of documents a respective initial web crawl interval, wherein the initial web crawl interval is determined based at least in part on a document'"'"'s importance metric;

instructions for retrieving each of the plurality of documents from a respective host at one or more times associated with each document'"'"'s respective initial web crawl interval;

instructions for associating a revised web crawl interval with a respective document of the plurality of documents based on the document'"'"'s respective initial web crawl interval and any changes to content of the document;

instructions for partitioning the plurality of documents into multiple tiers according to their respective web crawl intervals, each tier having a distinct associated range of web crawl intervals, including instructions for storing data for each tier identifying documents in the plurality of documents assigned to that tier in accordance with their respective web crawl intervals;

instructions for determining, for each tier of the multiple tiers, a web crawl order for the documents assigned to the tier in accordance with their respective revised web crawl intervals; and

instructions for moving a respective document between tiers of the multiple tiers when the respective revised web crawl interval of the respective document is associated with a different tier of the multiple tiers than a previous web crawl interval of the respective document.

17. The system of claim 16, wherein the search engine system'"'"'s web crawl order scheduler further comprises:

instructions for determining for respective documents of the plurality of documents, content update rates of the respective documents, user click rates of the respective documents, and at least one document importance metric of the respective documents;

instructions for associating the revised web crawl interval with each document of the plurality of documents based on the document'"'"'s respective initial web crawl interval, any changes to content of the document, the user click rate of the document, and the at least one document importance metric of the document; and

instructions for downloading and recording new copies of at least a subset of the documents in accordance with the determined web crawl order.

18. The system of claim 16, wherein the changes to the content of a document comprise critical content changes and non-critical content changes, and the search engine system considers the critical content changes to the document and ignores the non-critical content changes to the document when associating a revised web crawl interval with the document.

19. The system of claim 16, wherein the revised web crawl interval of a document is smaller than the document'"'"'s content update interval and larger than half of the document'"'"'s content update interval.

20. The system of claim 19, wherein the search engine system dynamically adjusts the revised web crawl interval of the document after retrieving a new copy of the document'"'"'s content from a respective host.

21. The system of claim 16, wherein the revised web crawl interval of a document is a time interval such that the search engine system retrieves each unique version of document content at least twice according to the revised web crawl interval.

22. The system of claim 16, wherein the revised web crawl interval of a document is determined in accordance with the document'"'"'s user click interval when the document'"'"'s user click interval is larger than the document'"'"'s content update interval.

31. The system of claim 16, wherein the search engine system'"'"'s web crawl order scheduler further comprises:

instructions for-updating the web crawl interval of a document after retrieving a new copy of the document'"'"'s content from its host and detecting content changes to the document based on the new copy.

32. The system of claim 31, including instructions for updating the web crawl interval of the document to be less than the initial web crawl interval when the document'"'"'s content has changed, and updating the web crawl interval to be more than the initial web crawl interval when the document'"'"'s content has not changed.

33. The system of claim 31, wherein the search engine system'"'"'s web crawl order scheduler further comprises:

instructions for identifying a first average interval between times where the document'"'"'s content has not changed;

instructions for identifying a second average interval between times where the document'"'"'s content has changed; and

instructions for updating the web crawl interval of the document based on the first average interval and the second average interval.

34. The system of claim 31, wherein the web crawl interval is not updated if the first average interval is greater than the second average interval.

35. The system of claim 31, wherein the web crawl interval is updated in accordance with the first average interval if the first average interval is greater than the second average interval and the document'"'"'s content has not changed, and is updated in accordance with the second average interval if the document'"'"'s content has changed.

36. The system of claim 31, wherein the web crawl interval is updated in accordance with an average between the first average interval and the second average interval if the first average interval is less than the second average interval.

37. The system of claim 31, wherein the search engine system considers critical content changes to the document and ignores all non-critical content changes to the document when updating the document'"'"'s web crawl interval.

38. The system of claim 16, wherein the initial web crawl interval of a document assigned to a respective tier is determined based at least in part on an average web crawl interval of all other documents assigned to the respective tier.

39. The system of claim 16, wherein the initial web crawl interval of the document is determined in accordance with a score corresponding to the document'"'"'s popularity.

23. A non-transitory computer readable storage medium, for scheduling documents to be crawled by a search engine in an appropriate order to reduce visibility of stale content in web searching, storing one or more programs to be executed by a computer system, wherein the computer system includes a search engine program, the one or more programs comprising:

instructions for associating with each of a plurality of documents a respective initial web crawl interval, wherein the initial web crawl interval is determined based at least in part on a document'"'"'s importance metric;

instructions for retrieving each of the plurality of documents from a respective host at one or more times associated with each document'"'"'s respective initial web crawl interval;

instructions for associating a revised web crawl interval with a respective document of the plurality of documents based on the document'"'"'s respective initial web crawl interval and any changes to content of the document;

instructions for partitioning the plurality of documents into multiple tiers according to their respective web crawl intervals, each tier having a distinct associated range of web crawl intervals, including instructions for storing data for each tier identifying documents in the plurality of documents assigned to that tier in accordance with their respective web crawl intervals;

instructions for determining, for each tier of the multiple tiers, a web crawl order for the documents assigned to the tier in accordance with their respective revised web crawl intervals; and

instructions for moving a respective document between tiers of the multiple tiers when the respective revised web crawl interval of the respective document is associated with a different tier of the multiple tiers than a previous web crawl interval of the respective document.

24. The computer readable storage medium of claim 23, wherein the one or more programs further comprise:

instructions for determining for respective documents of the plurality of documents, content update rates of the respective documents, user click rates of the respective documents, and at least one document importance metric of the respective documents;

instructions for associating the revised web crawl interval with each document of the plurality of documents based on the document'"'"'s respective initial web crawl interval, any changes to content of the document, the user click rate of the document, and the at least one document importance metric of the document; and

instructions for downloading and recording new copies of at least a subset of the documents in accordance with the determined web crawl order.

25. The computer readable storage medium of claim 23, wherein the changes to the content of a document comprise critical content changes and non-critical content changes, and the search engine program considers the critical content changes to the document and ignores the non-critical content changes to the document when associating a revised web crawl interval with the document.

26. The computer readable storage medium of claim 23, wherein the revised web crawl interval of a document is smaller than the document'"'"'s content update interval and larger than half of the document'"'"'s content update interval.

27. The computer readable storage medium of claim 23, wherein the one or more programs dynamically adjust the revised web crawl interval of the document after retrieving a new copy of the document'"'"'s content from a respective host.

28. The computer readable storage medium of claim 23, wherein the revised web crawl interval of a document is a time interval such that the search engine program retrieves each unique version of document content at least twice according to the revised web crawl interval.

29. The computer readable storage medium of claim 23, wherein the revised web crawl interval of a document is determined in accordance with the document'"'"'s user click interval when the document'"'"'s user click interval is larger than the document'"'"'s content update interval.

40. The computer readable storage medium of claim 23, wherein the one or more programs further comprise:

instructions for-updating the web crawl interval of a document after retrieving a new copy of the document'"'"'s content from its host and detecting content changes to the document based on the new copy.

41. The computer readable storage medium of claim 40, including instructions for updating the web crawl interval of the document to be less than the initial web crawl interval when the document'"'"'s content has changed, and updating the web crawl interval to be more than the initial web crawl interval when the document'"'"'s content has not changed.

42. The computer readable storage medium of claim 40, wherein the one or more programs further comprise:

instructions for identifying a first average interval between times where the document'"'"'s content has not changed;

instructions for identifying a second average interval between times where the document'"'"'s content has changed; and

instructions for updating the web crawl interval of the document based on the first average interval and the second average interval.

43. The computer readable storage medium of claim 40, wherein the web crawl interval is not updated if the first average interval is greater than the second average interval.

44. The computer readable storage medium of claim 40, wherein the web crawl interval is updated in accordance with the first average interval if the first average interval is greater than the second average interval and the document'"'"'s content has not changed, and is updated in accordance with the second average interval if the document'"'"'s content has changed.

45. The computer readable storage medium of claim 40, wherein the web crawl interval is updated in accordance with an average between the first average interval and the second average interval if the first average interval is less than the second average interval.

46. The computer readable storage medium of claim 40, wherein the one or more programs consider critical content changes to the document and ignore all non-critical content changes to the document when updating the document'"'"'s web crawl interval.

47. The computer readable storage medium of claim 40, wherein the initial web crawl interval of a document assigned to a respective tier is determined based at least in part on an average web crawl interval of all other documents assigned to the respective tier.

48. The computer readable storage medium of claim 40, wherein the initial web crawl interval of the document is determined in accordance with a score corresponding to the document'"'"'s popularity.