US 6,263,364 B1 · Web crawler system using plurality of parallel priority level queues having distinct associated download priority levels for prioritizing document downloading and maintaining document freshness

Abstract

A web crawler downloads documents from among a plurality of host computers. The web crawler enqueues document addresses in a data structure called the Frontier. The Frontier generally includes a set of queues, with all document addresses sharing a respective common host component being stored in a respective common one of the queues. Multiple threads substantially concurrently process the document addresses in the queues. The Frontier includes a set of parallel “priority queues,” each associated with a distinct priority level. Queue elements for documents to be downloaded are assigned a priority level, and then stored in the corresponding priority queue. Queue elements are then distributed from the priority queues to a set of underlying queues in accordance with their relative priorities. The threads then process the queue elements in the underlying queues. When performing a continuous crawl, the web crawler reinserts the queue element for a downloaded document into the Frontier in accordance with a download priority level associated with the downloaded document. For example, the download priority level may be determined as a function of an expiration date and time associated with document whose document address is denoted by the queue element.

Claims30

Dependent claims

A method of performing a continuous crawl for locating and downloading documents from among a plurality of host computers, comprising:

(a) obtaining at least one referring document set that includes addresses of one or more referred documents;
each referred document address including a host component;
(b) enqueuing queue elements in a plurality of queues, each queue element denoting one of the referred document addresses;
(c) substantially concurrently operating a plurality of threads;
(d) while operating each thread, repeatedly performing steps of:
(d1) identifying a queue element in a selected one of the queues, downloading a referred document corresponding to a referred document address in the identified queue element, and dequeuing the identified queue element;
and
(d2) executing at least one application program for processing the downloaded document;
the plurality of queues including a plurality of parallel priority level queues, each having a distinct associated download priority level, the download priority level corresponding to a probability of the queue elements enqueued in the associated priority level queue therein being processed by the threads;
and
step (d) including determining a download priority level for maintaining freshness of the downloaded document and re-enqueuing the queue element for the downloaded document in one of the parallel priority level queues in accordance with the determined download priority level.

8 more elements

A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

an enqueuing module that, when executed by the computer system, obtains at least one referring document that includes addresses of one or more referred documents, each referred document address including a host component corresponding to a host computer, and enqueues queue elements in a plurality of queues, each queue element denoting one of the referred document addresses;
and
a dequeuing module that is substantially concurrently executed by each of a plurality of threads so as to process the referred document addresses in the queues;
the dequeuing module including instructions that, when executed by a respective one of the threads, repeatedly perform the functions of:
(a1) identifying a queue element in a selected one of the queues, downloading a referred document corresponding to a referred document address in the identified queue element, and dequeuing the identified queue element;
(a2) executing at least one application program for processing the downloaded document;
and
(a3) determining a download priority level for maintaining freshness of the downloaded document;
the plurality of queues including a plurality of parallel priority level queues, each having a distinct associated download priority level, the download priority level corresponding to a probability of the queue elements enqueued in the associated priority level queue therein being processed by the threads;
and
the dequeuing module including instructions for re-enqueuing the queue element for the downloaded document in one of the parallel priority level queues in accordance with the download priority level determined for the queue element.

8 more elements

an enqueuing module that, when executed by the computer system, obtains at least one referring document that includes addresses of one or more referred documents, each referred document address including a host component corresponding to a host computer, and enqueues queue elements in a plurality of queues, each queue element denoting one of the referred document addresses;
and
a dequeuing module that is substantially concurrently executed by each of a plurality of threads so as to process the referred document addresses in the queues;
the dequeuing module including instructions that, when executed by a respective one of the threads, repeatedly perform the functions of:
(a1) identifying a queue element in a selected one of the queues, downloading a referred document corresponding to a referred document address in the identified queue element, and dequeuing the identified queue element;
and
(a2) executing at least one application program for processing the downloaded document;
the plurality of queues including a plurality of parallel priority level queues, each having a distinct associated download priority level, the download priority level corresponding to a probability of the queue elements enqueued in the associated priority level queue therein being processed by the threads;
and
the enqueuing module including instructions for determining a download priority level for each queue element and enqueuing the queue element in one of the parallel priority level queues in accordance with the determined download priority level.

7 more elements

A web crawler for downloading documents from among a plurality of host computers, comprising:

at least one central processing unit;
a plurality of threads of execution that are executed by the at least one central processing unit;
memory for storing a plurality of queues;
an enqueuing module that, when executed by the computer system, obtains at least one referring document that includes addresses of one or more referred documents, each referred document address including a host component corresponding to a host computer, and enqueues queue elements in the plurality of queues;
and
a dequeuing module that is substantially concurrently executed by each of a plurality of threads so as to process the referred document addresses in the queues;
the dequeuing module including instructions that, when executed by a respective one of the threads, repeatedly perform the functions of:
(a1) identifying a queue element in a selected one of the queues, downloading a referred document corresponding to a referred document address in the identified queue element, and dequening the identified queue element;
(a2) executing at least one application program for processing the downloaded document;
and
(a3) determining a download priority level for maintaining freshness of the downloaded document;
the plurality of queues including a plurality of parallel priority level queues, each having a distinct associated download priority level, the download priority level corresponding to a probability of the queue elements enqueued in the associated priority level queue therein being processed by the threads;
and
the dequeuing module including instructions for re-enqueuing the queue element for the downloaded document in one of the parallel priority level queues in accordance with the download priority level determined for the queue element.

11 more elements

Dependencies are inferred from the claim text.

Web crawler system using plurality of parallel priority level queues having distinct associated download priority levels for prioritizing document downloading and maintaining document freshness

Life of this patent

Web crawler system using plurality of parallel priority level queues having distinct associated download priority levels for prioritizing document downloading and maintaining document freshness

Life of this patent

Abstract

Claims30