Adaptive web crawling using a statistical model

• US 7,328,401 B2
• Filed: 12/22/2004
• Issued: 02/05/2008
• Est. Priority Date: 01/28/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Obata, Kenji C, Meyerzon, Dmitriy
• Primary Examiner(s): Bashore; William
• Assistant Examiner(s): Nguyen; Maikhanh
• Application Number:
  US11/022,054
• Publication Number:
  US 20050165778A1
• Time in Patent Office: 1,140 Days
• Field of Search: 715/500, 715/501.1, 715/513, 715/526, 707/1, 707/3, 707/200, 709/203
• US Class Current: 715/205
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A computer based system and method of retrieving information pertaining to documents on a computer network is disclosed. The method includes selecting a set of documents to be accessed during a Web crawl by utilizing a statistical model to determine which previously retrieved documents are most likely to have changed since last accessed. The statistical model is continuously improving its accuracy by training internal probability distributions to reflect the actual experience with change rate patterns of the documents accessed. The decision made whether to access the document is based on the probability of change compared against a desired synchronization level, random selections, maximum limits on the amount of time since the document was last accessed, and other criterion. Once the decision to access is made, the document is checked for changes and this information is used to train the statistical model.

Claims

1. A computer-implemented method for selectively accessing a document during a current crawl of a server computer, the document being identified by a document address specification, the document having been retrieved during a previous crawl, the method comprising:

(a) determining whether to access the document during the current crawl with the aid of a probabilistic model that is based on the probability that the document has changed since the previous crawl, wherein determining whether to access the document with the aid of a probabilistic model comprises computing a probability that the document has changed since the document was retrieved during the previous crawl, and wherein computing the probability that the document has changed comprises;

(i) calculating, based on the experience with the document during a plurality of previous crawls, a discrete random variable distribution that includes a plurality of training probabilities, wherein the training probabilities are calculated using a Poisson process, the Poisson process including a Poisson equation (e^(−

r*dt)) and a complementary Poisson equation (1−

e^(r*dt));

(ii) selecting an active probability indicative of a proportion of documents in a plurality of documents that are changing at various change rates, the plurality of documents including the document;

(iii) training the active probability to reflect experience with the document during the plurality of previous crawls; and

(iv) using the trained active probability to compute the probability that the document has changed; and

b) accessing the document if the determination produces an instruction indicative that the document at the document address specification should be accessed during the current crawl.

2. The method of claim 1, further comprising:

selecting the probability that the document has changed from the previous crawl as the active probability in the current crawl; and

repeating the method of claim 1 for the current crawl.

3. The method of claim 1, wherein training the active probability includes multiplying the active probability indicative of a change in the document by a training probability calculated using the probabilistic model.

4. The method of claim 1, further comprising:

training a document probability distribution corresponding to the document address specification to reflect experience with the document during the plurality of previous crawls, the document probability distribution including a plurality of probabilities;

determining from the document probability distribution a probability that the document has changed; and

making a determination of whether to access the document in the current crawl based on the probability that the document has changed.

5. The method of claim 4, further comprising:

calculating, based on the experience with the document during a plurality of previous crawls, a discrete random variable distribution that includes a plurality of training probabilities; and

multiplying each probability in the document probability distribution by a corresponding training probability from the discrete random variable distribution.

6. The method of claim 1, wherein the experience with the document during the plurality of previous crawls is derived from historical information associated with the document address specification.

7. A computer-readable medium having computer-executable instructions for retrieving one document in a plurality of documents from a remote server, which when executed comprise:

maintaining historical information associated with changes to the one document;

initiating a crawl procedure for retrieving particular documents in the plurality of documents; and

determining whether to access the one document from the remote server based on a probabilistic analysis of the historical information associated with the changes to the one document, said probabilistic analysis of the historical information being based on the probability that the one document has changed since a previous crawl, wherein the probabilistic analysis comprises computing a probability that the one document has changed since the one document was last retrieved from the remote server, and wherein computing the probability that the one document has changed since the one document was last retrieved from the remote server comprises, beginning with a probability that a pre-defined proportion of documents in the plurality of documents has changed, training the probability that the pre-defined proportion of documents has changed using the historical information associated with the one document to achieve the probability that the one document has changed, wherein computing the probability that the one document has changed also comprises;

calculating, based on the experience with the document during a plurality of previous crawls, a discrete random variable distribution that includes a plurality of training probabilities, wherein the training probabilities are calculated using a Poisson process, the Poisson process including a Poisson equation (e^(−

r*dt)) and a complementary Poisson equation (1−

e^(−

r*dt)).

8. The computer-readable medium of claim 7, further comprising making a random decision to retrieve the one document wherein the random decision is biased by the probability that the one document has changed.

9. The computer-readable medium of claim 8, wherein the random decision is further biased by a synchronization level configured to influence the random decision based on a predetermined degree of tolerance for not retrieving the one document if the document is likely to have changed.

10. The computer-readable medium of claim 8, wherein the random decision is made by a software routine adapted to simulate a flip of a coin.

11. The computer-readable medium of claim 7, wherein:

the historical information associated with changes to the one document includes a time stamp for the one document, the time stamp being indicative of the time that the one document was last modified when the one document was last retrieved from the remote server; and

the probabilistic analysis includes a comparison of the time stamp included in the historical information with another time stamp associated with the one document stored on the remote server.

12. The computer-readable medium of claim 11, further comprising:

if the time stamp included in the historical information does not match the other time stamp associated with the one document stored on the remote server, identifying the one document for retrieval during the crawl procedure.

13. The computer-readable medium of claim 7, wherein:

the historical information associated with changes to the one document includes a hash value associated with the one document, the hash value being a representation of the one document; and

the probabilistic analysis includes a comparison of the hash value included in the historical information with another hash value calculated from information retrieved from the one document stored on the remote server.

14. The computer-readable medium of claim 13, if the hash value included in the historical information does not match the other hash value associated with the one document stored on the remote server, identifying the one document for retrieval during the crawl procedure.