Proxy server using a statistical model

• US 20050086583A1
• Filed: 11/05/2004
• Published: 04/21/2005
• Est. Priority Date: 01/28/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meyerzon, Dmitriy, Obata, Kenji C.
• Granted Patent: US 7,603,616 B2
• Time in Patent Office: Days
• US Class Current: 715/229
• 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 determining whether to re-fetch a previously retrieved document across a computer network is disclosed. The method utilizes a statistical model to determine whether the previously retrieved document likely 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 of 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 in response to a current retrieval request, the document being identified by a document address specification, the document having been retrieved during a previous retrieval request, the method comprising:

determining whether to access the document during the current retrieval request by identifying with the aid of a statistical model whether the document is likely to have changed since a previous retrieval; and

accessing the document if the determination produces an instruction indicative that the document at the document address specification should be accessed during the current retrieval request.

2. The method of claim 1, wherein determining whether to access the document further comprises computing a probability that the document has changed since the document was retrieved during the previous retrieval request.

3. The method of claim 2, wherein computing the probability that the document has changed further comprises:

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;

training the active probability to reflect an experience with the document during a plurality of previous document retrieval requests; and

using the trained active probability to compute the probability that the document has changed.

4. The method of claim 3, further comprising:

selecting the probability that the document has changed since the previous document retrieval request as the active probability in the current retrieval request; and

repeating the method of claim 3 for the current retrieval request.

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

6. The method of claim 1, wherein determining whether to access the document during the current retrieval request with the aid of a statistical model further comprises:

training a document probability distribution corresponding to the document address specification to reflect an experience with the document during a plurality of previous document retrieval requests, 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 a current document retrieval request based on the probability that the document has changed.

7. The method of claim 6, further comprising:

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

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

8. The method of claim 7, wherein the training probabilities are calculated using a Poisson process, the Poisson process including a Poisson equation (e{circumflex over ( 

)}(−

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

e{circumflex over ( 

)}(−

r*dt)).

9. The method of claim 8, wherein the experience with the document during the plurality of previous document retrieval requests is derived from historical information associated with the document address specification.

10. 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 representing prior changes to the one document at the remote server;

initiating a document retrieval request procedure for retrieving particular documents in the plurality of documents; and

determining whether to access the one document from the remote server based on an analysis of the historical information representing prior changes to the one document at the remote server.

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

if the determination to access the one document is positive, identifying the one document for retrieval during the document retrieval procedure.

12. The computer-readable medium of claim 10, wherein determining whether to retrieve the document further comprises:

computing a probability that the one document has changed since the one document was last retrieved from the remote server.

13. The computer-readable medium of claim 12, wherein computing the probability that the one document has changed further 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.

14. The computer-readable medium of claim 12, 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.

15. The computer-readable medium of claim 14, 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.

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

17. The computer-readable medium of claim 12, wherein:

the historical information representing prior changes to the one document comprises for the one document, a change count representing the number of times the one document has been modified, an access count representing the number of times the one document has been accessed, a first access time representing the time the one document was first accessed, and a last access time representing the time the one document was last accessed; and

wherein the step of training the probability comprises creating a timeline using the historical information, the timeline having representations thereon of no change intervals, change intervals, and no change chunk intervals.

18. The computer-readable medium of claim 17, wherein the step of training the probability further comprises:

training the document probability distribution for each no change interval;

training the document probability distribution for each change interval; and

training the document probability distribution for each no change chunk interval.

19. The computer-readable medium of claim 10, wherein:

the historical information representing prior 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

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

20. The computer-readable medium of claim 19, wherein 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, updating the historical information to identify that the one document changed.

21. A proxy server, comprising:

a cache comprising a plurality of documents, said plurality of documents having been previously retrieved across a network; and

at least one computer process, said at least one computer process operable to determine whether to retrieve a requested document from across a network using a statistical model to identify a likelihood the requested document has changed since a previous retrieval.

22. The proxy server of claim 21, wherein said at least one computer process computes a probability that the requested document has changed since the requested document was previously retrieved.

23. The proxy server of claim 21, further comprising:

a probability distribution comprising a plurality of probabilities, each said probability indicative that a document has changed at a particular rate; and

historical data relating to previous retrievals of said plurality of documents.

24. The proxy server of claim 23, wherein said at least one computer process computes a probability that the requested document has changed since the requested document was previously retrieved using said probability distribution and said historical data.

25. The proxy server of claim 23, wherein said at least one computer process is operable to perform the following:

select said probability distribution as an active probability indicative of a proportion of documents in a plurality of documents that are changing at various change rates,

modify said active probability distribution to reflect an experience with the requested document during a plurality of previous document retrieval requests, and

employ a modified active probability to compute a probability that the requested document has changed.

26. The proxy server of claim 25, wherein said at least one computer process modifies said active probability distribution by multiplying the active probability distribution by a training probability calculated using a statistical model.

27. The proxy server of claim 26, wherein said training probability is calculated using said historical data.

28. The proxy server of claim 23, wherein said at least one computer process modifies said probability distribution to reflect an experience with the requested document during a plurality of previous document retrieval requests as reflected in said historical data, and derives using the modified probability distribution a probability that the requested document has changed since a previous request.

29. The proxy server of claim 23, wherein said historical data comprises for each of said plurality of documents an identifier of the location of the document in the network, a hash value derived from a document, and data relating to changes made to a document during previous retrieval requests.

30. The proxy server of claim 21, wherein said at least one process is further operable to retrieve the requested document from said cache if the requested document is not likely to have changed since a previous request.