Scheduler for search engine crawler

• US 8,042,112 B1
• Filed: 06/30/2004
• Issued: 10/18/2011
• Est. Priority Date: 07/03/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gobioff, Howard Bradley, Zhu, Huican, Acharya, Anurag, Ibel, Maximilian
• Primary Examiner(s): Puente; Emerson
• Assistant Examiner(s): Truong; Camquy
• Application Number:
  US10/882,956
• Time in Patent Office: 2,666 Days
• Field of Search: 718/103, 718/102, 709/217
• US Class Current: 718/102
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A search engine crawler includes a distributed set of schedulers that are associated with one or more segments of document identifiers (e.g., URLs) corresponding to documents on a network (e.g., WWW). Each scheduler handles the scheduling of document identifiers (for crawling) for a subset of the known document identifiers. Using a starting set of document identifiers, such as the document identifiers crawled (or scheduled for crawling) during the most recent completed crawl, the scheduler removes from the starting set those document identifiers that have been unreachable in each of the last X crawls. Other filtering mechanisms may also be used to filter out some of the document identifiers in the starting set. The resulting list of document identifiers is written to a scheduled output file for use in a next crawl cycle.

Claims

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

a memory for storing a set of document identifiers corresponding to documents on a network and associated status data collected during one or more previous crawls by the search engine crawler; and

a plurality of schedulers configured to select a subset of the document identifiers for crawling, at least some of the schedulers configured to compute priority scores for the subset of document identifiers and to schedule for crawling at least a portion of the subset of document identifiers based on the priority scores and status data;

wherein the scheduling includes removing from the subset one or more document identifiers that were unreachable in a plurality of consecutive prior crawls or had download errors in a plurality of consecutive prior crawls; and

wherein at least some of the schedulers are configured to;

select one or more document identifiers whose corresponding documents will be reused based on historical status data; and

retrieve and index documents corresponding to the selected document identifiers, wherein the documents are retrieved from a repository distinct from web hosts corresponding to the document identifiers.

2. The system of claim 1, wherein the document identifiers stored in the memory are divided into multiple segments, and wherein each of a plurality of schedulers is configured to schedule a partition of the document identifiers that includes document identifiers assigned to each of the multiple segments.

3. The system of claim 1, further comprising an unscheduled document identifier file for storing the document identifiers not scheduled for crawling by one or more of the plurality of schedulers.

4. The system of claim 1, wherein each of the plurality of schedulers is configured to sort document identifiers by priority scores and schedule a predefined number N of the sorted document identifiers having highest priority scores.

5. The system of claim 1, wherein the priority scores are calculated using a priority function given by

Priority Score_i=page_importance_i*boost factor,

where the subscript i denotes an ith document identifier and the boost factor is a scalar that is used to demote or promote the priority score of the document identifier.

6. A method of scheduling a search engine crawler using a scheduler system, comprising:

at a server with one or more processors and memory, and one or more programs stored in the memory that execute on the one or more processors;

selecting a first subset of document identifiers from a set of document identifiers corresponding to documents on a network;

computing priority scores for the first subset of document identifiers;

forming a second subset of document identifiers based on the priority scores and status data collected during one or more previous crawls by the search engine crawler and by removing from the first subset one or more document identifiers identified as unreachable in a plurality of prior crawls or associated with download errors in a plurality of prior crawls;

scheduling for crawling the second subset of document identifiers;

selecting one or more document identifiers from the second subset whose corresponding documents will be reused based on historical status data and

retrieving and indexing documents corresponding to the selected document identifiers, wherein the documents are retrieved from a repository distinct from web hosts corresponding to the document identifiers.

7. The method of claim 6, further comprising:

applying at least one exception filter to at least a plurality of the document identifiers to identify document identifiers to be excluded from a next crawl.

8. The method of claim 6, further comprising:

removing document identifiers from the second subset in accordance with one or more scheduler limits.

9. The method of claim 6, further comprising:

storing unscheduled document identifiers for crawling at a later time.

10. The method of claim 6, further comprising:

sorting the first subset of document identifiers by priority scores; and

scheduling a portion of the sorted document identifiers to be crawled.

11. The method of claim 6, wherein the document identifiers are Uniform Resource Locators (URLs) and the documents are located on the World Wide Web (WWW).

12. The method of claim 6, wherein the priority scores are calculated using a priority function given by

Priority Score_i=page_importance_i*boost factor,

where the subscript i denotes an ith document identifier and the boost factor is a scalar that is used to demote or promote the priority score of the document identifier.

13. The method of claim 6, wherein the step of selecting document identifiers to be reused further comprises:

comparing scores computed for document identifiers against predetermined thresholds; and

selecting document identifiers whose corresponding documents will be reused based on the results of the comparison.

14. The method of claim 6, wherein the historical status data includes data indicating whether a particular document associated with a document identifier has changed during a predefined time period.

15. A non-transitory computer-readable medium having stored thereon instructions, which when executed by a processor in a scheduler system for a search engine crawler, cause the processor to perform the operations of:

selecting a first subset of document identifiers from a set of document identifiers corresponding to documents on a network;

computing priority scores for the first subset of document identifiers;

forming a second subset of document identifiers based on the priority scores and status data collected during one or more previous crawls by the search engine crawler and by removing from the first subset one or more document identifiers identified as unreachable in a plurality of prior crawls or associated with download errors in a plurality of prior crawls;

scheduling for crawling the second subset of document identifiers;

identifying one or more document identifiers from the second subset whose corresponding documents will be reused based on historical status data and

retrieving documents corresponding to the identified document identifiers, wherein the documents are retrieved from a repository distinct from web hosts corresponding to the document identifiers.

16. The computer-readable medium of claim 15, further comprising instructions for applying at least one exception filter to at least a plurality of the document identifiers to identify document identifiers to be excluded from a next crawl.

17. The computer-readable medium of claim 15, further comprising instructions for removing document identifiers from the second subset in accordance with one or more scheduler limits.

18. The computer-readable medium of claim 15, further comprising instructions for storing unscheduled document identifiers for crawling at a later time.

19. The computer-readable medium of claim 15, further comprising instructions for:

sorting the first subset of document identifiers by priority scores; and

scheduling a portion of the sorted document identifiers to be crawled.

20. The computer-readable medium of claim 15, wherein the document identifiers are Uniform Resource Locators (URLs) and the documents are located on the World Wide Web (WWW).

21. The computer-readable medium of claim 15, wherein the priority scores are calculated using a priority function given by

Priority Score_i=page_importance_i*boost factor,

where the subscript i denotes an ith document identifier and the boost factor is a scalar that is used to demote or promote the priority score of the document identifier.