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

Claim 3

The method of claim 1 , wherein said enqueuing module is configured to use at least one of the downloaded referred documents as a new referring document.

Claim 4

The method of claim 1 , wherein the plurality of queues includes a front-end data structure and a back-end data structure, the front-end data structure including the plurality of parallel priority level queues, and the back-end data structure including a plurality of parallel first-in-first-out underlying queues; step (b) includes enqueuing at least a subset of the queue elements in the priority level queues, each such queue element being enqueued in one of the priority level queues in accordance with a priority level associated with the queue element; and step (d) includes transferring queue elements from the priority level queues to the underlying queues in accordance with the download priority levels of the priority level queues.

Claim 5

The method of claim 3 , wherein step (b) includes enqueuing those of the referred data set addresses sharing a respective common host address into a respective common one of the underlying queues.

Claim 6

The method of claim 4 , wherein referred data sets corresponding to referred data set addresses from different ones of the underlying queues are downloaded substantially concurrently, while referred data sets corresponding to referred data set addresses from any single one of the underlying queues are downloaded one at a time.

Claim 7

The method of claim 1 , wherein the download priority level for each of a subset of the queue elements is determined as a function of an expiration date and time associated with document whose document address is denoted by the queue element.

Claim 8

The method of claim 1 , wherein the download priority level for each of a subset of the queue elements is determined as a function of a host component of the document address denoted by the queue element.

Claim 9

The method of claim 1 , wherein the download priority level for each of a subset of the queue elements is determined as a function of a historical rate of change of the document whose address is denoted by the queue element.

Claim 12

The method of claim 9 , wherein the download priority level for each of a subset of the queue elements is determined as a function of the referred document address denoted by the queue element.

Claim 13

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.

Claim 14

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.

Claim 15

The computer program product of claim 11 , wherein said enqueuing module is configured to use at least one of the downloaded referred documents as a new referring document.

Claim 16

The computer program product of claim 11 , wherein the plurality of queues includes a front-end data structure and a back-end data structure, the front-end data structure including the plurality of parallel priority level queues, and the back-end data structure including a plurality of parallel first-in-first-out underlying queues; the enqueuing module includes instructions for enqueuing at least a subset of the queue elements in the priority level queues, each such queue element being enqueued in one of the priority level queues in accordance with a priority level associated with the queue element; and the dequeuing module includes instructions for transferring queue elements from the priority level queues to the underlying queues in accordance with the download priority levels of the priority level queues.

Claim 17

The computer program product of claim 13 , wherein the enqueuing module includes instructions for enqueuing those of the referred data set addresses sharing a respective common host address into a respective common one of the underlying queues.

Claim 18

The computer program product of claim 14 , wherein referred data sets corresponding to referred data set addresses from different ones of the underlying queues are downloaded substantially concurrently, while referred data sets corresponding to referred data set addresses from any single one of the underlying queues are downloaded one at a time.

Claim 19

The computer program product of claim 11 , wherein the download priority level for each of a subset of the queue elements is determined as a function of an expiration date and time associated with document whose document address is denoted by the queue element.

Claim 20

The computer program product of claim 11 , wherein the download priority level for each of a subset of the queue elements is determined as a function of a host component of the document address denoted by the queue element.

Claim 21

The computer program product of claim 11 , wherein the download priority level for each of a subset of the queue elements is determined as a function of a historical rate of change of the document whose address is denoted by the queue element.

Claim 22

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; 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.

Claim 23

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; 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.

Claim 24

The computer program product of claim 19 , wherein the download priority level for each of a subset of the queue elements is determined as a function of the referred document address denoted by the queue element.

Claim 25

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.

Claim 26

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.

Claim 27

The web crawler of claim 21 , wherein said enqueuing module is configured to use at least one of the downloaded referred documents as a new referring document.

Claim 28

The web crawler of claim 21 , wherein the plurality of queues includes a front-end data structure and a back-end data structure, the front-end data structure including the plurality of parallel priority level queues, and the back-end data structure including a plurality of parallel first-in-first-out underlying queues; the enqueuing module includes instructions for enqueuing at least a subset of the queue elements in the priority level queues, each such queue element being enqueued in one of the priority level queues in accordance with a priority level associated with the queue element; and the dequeuing module includes instructions for transferring queue elements from the priority level queues to the underlying queues in accordance with the download priority levels of the priority level queues.

Claim 29

The web crawler of claim 23 , wherein the enqueuing module includes instructions for enqueuing those of the referred data set addresses sharing a respective common host address into a respective common one of the underlying queues.

Claim 30

The web crawler of claim 24 , wherein referred data sets corresponding to referred data set addresses from different ones of the underlying queues are downloaded substantially concurrently, while referred data sets corresponding to referred data set addresses from any single one of the underlying queues are downloaded one at a time.

Claim 31

The web crawler of claim 21 , wherein the download priority level for each of a subset of the queue elements is determined as a function of an expiration date and time associated with document whose document address is denoted by the queue element.

Claim 32

The web crawler of claim 21 , wherein the download priority level for each of a subset of the queue elements is determined as a function of a host component of the document address denoted by the queue element.

Claim 33

The web crawler of claim 21 , wherein the download priority level for each of a subset of the queue elements is determined as a function of a historical rate of change of the document whose address is denoted by the queue element.

Claim 34

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 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.

Claim 35

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 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.

Claim 36

The web crawler of claim 29 , wherein the download priority level for each of a subset of the queue elements is determined as a function of the referred document address denoted by the queue element.