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

• US 8,782,032 B2
• Filed: 03/22/2013
• Issued: 07/15/2014
• Est. Priority Date: 08/30/2004
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Carver, Anton P. T.
• Primary Examiner(s): Ly, Anh
• Application Number:
  US13/849,355
• Publication Number:
  US 20130226897A1
• Time in Patent Office: 480 Days
• Field of Search: 707/709, 707/706, 707/708, 707/710, 707/803, 707/E17.108, 707/E17.116, 707/E17.117, 709/217, 709/224
• US Class Current: 707/709
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method includes comparing a first instance with a second instance of a document in a plurality of documents. The first instance is obtained from a remote location at a specified time before the second instance is obtained from the remote location, and (i) the specified time is determined in accordance with a first crawl interval associated with the document, (ii) each document in the plurality of documents is assigned to a tier in a plurality of tiers, each tier having a distinct associated range of web crawl intervals, and (iii) the first crawl interval is assigned a first tier. The method also includes computing a second crawl interval for the document, which is a function of the document comparison; and determining whether the second crawl interval is in the first tier. When the second crawl interval is not, the first document is reassigned to another tier.

Claims

1. A method for scheduling a document crawl interval, comprising:

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

comparing a first instance of a document in a plurality of documents with a second instance of the document, thereby obtaining a document comparison, wherein the first instance of the document is obtained from a remote location at a specified time before the second instance of the document is obtained from the remote location and wherein

(i) the specified time is determined in accordance with a first crawl interval associated with the document,

(ii) each document in the plurality of documents is assigned to a crawl-scheduling tier in a plurality of crawl-scheduling tiers, each crawl-scheduling tier in the plurality of crawl-scheduling tiers having a distinct associated range of web crawl intervals, and

(iii) the first crawl interval is assigned a first crawl-scheduling tier in the plurality of crawl-scheduling tiers; and

computing a second crawl interval for the document, wherein the second crawl interval is a function of the document comparison; and

determining whether the second crawl interval is in the crawl-scheduling first tier, wherein, when the second crawl interval is not in the crawl-scheduling first tier, the first document is reassigned to a crawl-scheduling tier in the plurality of crawl-scheduling tiers other than the first crawl-scheduling tier.

2. The method of claim 1, wherein comparing the first instance with the second instance includes comparing a document fingerprint of the first instance with a document fingerprint of the second instance.

3. The method of claim 1, wherein the first instance of the document is unchanged with respect to the second instance of the document.

4. The method of claim 1, wherein the first instance of the document is changed compared to the second instance of the document.

5. The method of claim 1, wherein the first instance of the document is changed with respect to the second instance of the document and wherein the second crawl interval for the document is less than the first crawl interval.

6. The method of claim 1, wherein the document comparison produces a result corresponding to a change between the first instance and the second instance, and the result is one of:

no change, a critical change, and a non-critical change.

7. The method of claim 1, wherein the document includes a plurality of portions, each portion in the plurality of portions is associated with a comparison weight, and comparing the first instance of the document with the second instance of the document uses a comparison weight associated with a portion included in the document.

8. The method of claim 1, wherein the second crawl interval is also a function of the first crawl interval.

9. The method of claim 1, wherein computing the second crawl interval for the document includes:

in accordance with a determination that the document has changed, reindexing the document; and

computing the second crawl interval in accordance the document change.

10. The method of claim 1, wherein computing the second crawl interval for the document includes:

in accordance with a determination that the document has not changed, reusing the document; and

computing the second crawl interval in accordance the determination that the document has not changed.

11. The method of claim 1, wherein computing the second crawl interval for the document includes:

in accordance with a determination that the document has not changed, reusing the document; and

computing the second crawl interval in accordance the determination that the document has not changed.

12. The method of claim 1, wherein the second crawl interval for the document is associated with a lesser likelihood that a user will see stale content of the document.

13. The method of claim 1, wherein a crawl interval for the document is determined using a desired likelihood that a user will not see stale content of the document, a user view rate of the document, and a document update rate of the document.

14. The method of claim 13, wherein the user view rate of the document is determined using a user impression rate of the document, and a user click rate of the document.

15. The method of claim 14, wherein the user impression rate of the document corresponds to a rate at which at least a portion of the document is presented to the user, and the user click rate of the document corresponds to a rate at which the document is clicked by the user.

16. The method of claim 14, wherein the user click rate of the document is calculated using a number of redirects to the document from another application.

17. The method of claim 13, wherein the desired likelihood that a user will not see stale content of the document is calculated using the document'"'"'s page rank, the document'"'"'s user click rate, the document'"'"'s content update rate, the document'"'"'s desired crawl interval.

18. The method of claim 17, further comprising:

determining crawling order for the document in accordance with the desired likelihood that a user will not see stale content of the document.

19. The method of claim 1, wherein the steps recited in claim 1 are executed in response to obtaining a notification that the document has been updated.

20. The method of claim 1, further comprising:

in accordance with a first document comparison having a result that the document has not changed, and a second document comparison having a result that the document has not changed;

increasing crawl interval for the document.

21. The method of claim 20, wherein the first document comparison and the second document comparison are consecutive.

22. The method of claim 1, further comprising:

in accordance with a first document comparison having a result that the document has changed, and a second document comparison having a result that the document has not changed;

decreasing crawl interval for the document.

23. The method of claim 22, wherein the first document comparison and the second document comparison are consecutive.

24. The method of claim 1, further comprising:

increasing or decreasing crawl interval for the document in accordance with a Nyquist sampling law.

25. The method of claim 1, further comprising:

determining an initial crawl interval for the document in accordance with the document'"'"'s importance score.

26. The method of claim 1, further comprising:

determining a desired crawl interval for the document using;

(i) average interval between crawls where the document has not change and (ii) the average interval between crawls where the document has changed.

27. The method of claim 26, wherein the desired crawl interval for the document is the average of (i) average interval between crawls where the document has not changed and (ii) the average interval between crawls where the document has changed.

28. The method of claim 26, further comprising:

determining crawling order for the document in accordance with the document'"'"'s desired crawl interval.

29. The method of claim 24, further comprising:

determining crawling order for the document also in accordance with the document'"'"'s crawling priority.

30. The method of claim 1, wherein the document corresponds to a plurality of features, each feature in the plurality of features is associated with a feature change interval and a importance score;

and further comprising;

determining the document'"'"'s crawling interval using a respective feature'"'"'s feature change interval and importance score.

31. A computer system comprising:

one or more processors;

a memory storing one or more programs for execution by the one or more processors, wherein the one or more programs comprising instructions for;

comparing a first instance of a document in a plurality of documents with a second instance of the document, thereby obtaining a document comparison, wherein the first instance of the document is obtained from a remote location at a specified time before the second instance of the document is obtained from the remote location and wherein

(i) the specified time is determined in accordance with a first crawl interval associated with the document,

(ii) each document in the plurality of documents is assigned to a crawl-scheduling tier in a plurality of crawl-scheduling tiers, each crawl-scheduling tier in the plurality of crawl-scheduling tiers having a distinct associated range of web crawl intervals, and

(iii) the first crawl interval is assigned a first crawl-scheduling tier in the plurality of crawl-scheduling tiers; and

computing a second crawl interval for the document, wherein the second crawl interval is a function of the document comparison; and

determining whether the second crawl interval is in the crawl-scheduling first tier, wherein, when the second crawl interval is not in the crawl-scheduling first tier, the first document is reassigned to a crawl-scheduling tier in the plurality of crawl-scheduling tiers other than the first crawl-scheduling tier;

determining whether the second crawl interval is in the first tier, wherein, when the second crawl interval is not in the first tier, the first document is reassigned to a tier in the plurality of tiers other than the first tier.

32. A non-transitory computer readable storage medium storing one or more programs to be executed by a computer system, the one or more programs comprising instructions for:

comparing a first instance of a document in a plurality of documents with a second instance of the document, thereby obtaining a document comparison, wherein the first instance of the document is obtained from a remote location at a specified time before the second instance of the document is obtained from the remote location and wherein

(i) the specified time is determined in accordance with a first crawl interval associated with the document,

(ii) each document in the plurality of documents is assigned to a crawl-scheduling tier in a plurality of crawl-scheduling tiers, each crawl-scheduling tier in the plurality of crawl-scheduling tiers having a distinct associated range of web crawl intervals, and

(iii) the first crawl interval is assigned a first crawl-scheduling tier in the plurality of crawl-scheduling tiers; and

computing a second crawl interval for the document, wherein the second crawl interval is a function of the document comparison; and

determining whether the second crawl interval is in the crawl-scheduling first tier, wherein, when the second crawl interval is not in the crawl-scheduling first tier, the first document is reassigned to a crawl-scheduling tier in the plurality of crawl-scheduling tiers other than the first crawl-scheduling tier.