Scheduler for Search Engine Crawler

• US 20100241621A1
• Filed: 05/25/2010
• Published: 09/23/2010
• Est. Priority Date: 07/03/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Keith H. Randall
• Inventors: Randall, Keith H.
• Granted Patent: US 8,161,033 B2
• Time in Patent Office: Days
• US Class Current: 707/709
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A scheduler for a search engine crawler includes a history log containing document identifiers (e.g., URLs) corresponding to documents (e.g., web pages) on a network (e.g., Internet). The scheduler is configured to process each document identifier in a set of the document identifiers by determining a content change frequency of the document corresponding to the document identifier, determining a first score for the document identifier that is a function of the determined content change frequency of the corresponding document, comparing the first score against a threshold value, and scheduling the corresponding document for indexing based on the results of the comparison.

Claims

1. A method of scheduling document indexing, comprising:

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

retrieving a number of document identifiers, each document identifier identifying a corresponding document on a network; and

for each retrieved document identifier and its corresponding document,

determining a query-independent score indicative of a rank of the corresponding document relative to other documents in a set of documents;

determining a content change frequency of the corresponding document by comparing information stored for successive downloads of the corresponding document;

determining a first score for the document identifier that is a function of both the determined query-independent score and the determined content change frequency of the corresponding document;

comparing the first score against a threshold value; and

conditionally scheduling the document for indexing based on the result of the comparison.

2. The method of claim 1, wherein generating the first score includes generating the first score from the product of the square of the query-independent score and the determined content change frequency.

3. The method of claim 1, wherein the scheduling of a document for indexing includes scheduling the document for a particular index segment indicated by a segment identifier associated with the document identifier.

4. The method of claim 1, wherein the content change frequency for a respective document identifier is determined by comparing content checksums stored in a history log for successive downloads of the document corresponding to the document identifier.

5. The method of claim 1, wherein the first score is determined from a content checksum stored in a history log.

6. The method of claim 1, wherein the threshold value is determined using a score computed for each document identifier in a sample set of document identifiers.

7. The method of claim 6, wherein the threshold value is further determined using a target size of a set of documents to be crawled.

8. The method of claim 1, wherein determining the first score uses a function of the determined query-independent score, the determined content change frequency of the corresponding document, and the age of the corresponding document.

9. A scheduler system for a search engine crawler, comprising:

a computer;

a history log containing document identifiers corresponding to documents on a network previously indexed by the search engine crawler, wherein each document identifier has a corresponding document; and

a scheduler, executed by the computer, and configured to process each document identifier in a set of the document identifiers in the history log by determining a query-independent score indicative of a rank of the corresponding document relative to other documents on the network, determining a content change frequency of the document corresponding to the document identifier by comparing information stored for successive downloads of the corresponding document, determining a first score for the document identifier that is a function of both the query-independent score and the determined content change frequency of the corresponding document, comparing the first score against a threshold value, and conditionally scheduling the corresponding document for indexing based on the results of the comparison,

wherein the history log and scheduler are stored on computer-readable media.

10. The scheduler system of claim 9, wherein the scheduler is configured to generate the first score from the product of the square of the query-independent score and the determined content change frequency.

11. The scheduler system of claim 9, wherein the document is scheduled for a particular index segment indicated by a segment identifier in the history log.

12. The scheduler system of claim 9, wherein the scheduler is configured to determine the content change frequency for a respective document identifier by comparing content checksums stored in the history log for successive downloads of the document corresponding to the document identifier.

13. The scheduler system of claim 9, wherein the scheduler is configured to determine the content change frequency from a content checksum stored in a history log.

14. The scheduler system of claim 9, wherein the threshold value is determined using a score computed for each document identifier in a sample set of document identifiers.

15. The scheduler system of claim 14, wherein the threshold value is further determined using a target size of a set of documents to be crawled.

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

retrieving a number of document identifiers, each document identifier identifying a corresponding document on a network;

for each retrieved document identifier,

determining a query-independent score indicative of a rank of the corresponding document relative to other documents in a set of documents;

determining a content change frequency of the corresponding document identifier by comparing information stored for successive downloads of the corresponding document and determining a first score for the document identifier that is a function of both the query-independent score and the determined content change frequency of the corresponding document;

comparing the first score against a threshold value; and

conditionally scheduling the document for indexing based on the result of the comparison.

17. A computer-readable storage medium of claim 16, wherein generating the first score includes generating the first score from the product of the square of the query-independent score and the determined content change frequency.

18. A computer-readable storage medium of claim 16, wherein the scheduling of a document for indexing includes scheduling the document for a particular index segment indicated by a segment identifier associated with the document identifier.

19. A computer-readable storage medium of claim 16, wherein determining the content change frequency for a respective document identifier includes comparing content checksums stored in a history log for successive downloads of the document corresponding to the document identifier.

20. A computer-readable storage medium of claim 16, wherein determining the content change frequency for a respective document identifier comprises determining the content change frequency from a content checksum stored in a history log.

21. A computer-readable storage medium of claim 16, wherein the threshold value is determined using a score computed for each document identifier in a sample set of document identifiers.

22. A computer-readable storage medium of claim 21, wherein the threshold value is further determined using a target size of a set of documents to be crawled.