Prefetching and caching documents according to probability ranked need S list

• US 6,098,064 A
• Filed: 05/22/1998
• Issued: 08/01/2000
• Est. Priority Date: 05/22/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Pirolli, Peter L., Pitkow, James E.
• Primary Examiner(s): Robertson, David L.
• Application Number:
  US09/083,645
• Time in Patent Office: 802 Days
• Field of Search: 707/2, 707/5, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/53 using third party service providers
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method is presented for determining whether to prefetch and cache documents on a computer. In one embodiment, documents are prefetched and cached on a client computer from servers located on the Internet in accordance with their computed need probability. Those document with a higher need probability are prefetched and cached before documents with lower need probabilities. The need probability for a document is computed using both a document context factor and a document history factor. The context factor of the need probability of a document is determined by computing the correlation between words in the document and a context Q of the operating environment. The history factor of the need probability of a document is determined by integrating both the recency of document use and the frequency of document use.

Claims

1. A method for determining with a computer whether to prefetch and cache documents, comprising the steps of:

recording context data and history data of the documents in a needs list stored in a memory of the computer;

said recording step being performed each time a document request is received by the computer;

computing a need probability for the documents recorded in the needs list stored in the memory;

said computing step computing the need probability for the documents as a function of the recorded context data and history data of the documents; and

identifying those documents in the needs list with the greatest computed need probability to be prefetched and cached in the memory of the computer.

2. The method according to claim 1, wherein said step of recording history data further comprises the steps of:

recording in the needs list how recently each document is referenced; and

recording in the needs list how frequently each document is referenced.

3. The method according to claim 2, wherein said step of recording context data further comprises the steps of:

recording keywords of each document referenced in the needs list; and

recording links of each document referenced in the needs list.

4. The method according to claim 3, wherein said computing step further comprises the steps of:

estimating a history factor for predicting how likely each document recorded in the needs list is to be needed; and

estimating a context factor for predicting how relevant each document in the needs list is given a context Q of an operating environment.

5. The method according to claim 4, wherein said computing step computes the need probability for each document in the needs list by summing the weighted logarithms of the estimated history factor and the estimated context factor.

6. The method according to claim 4, wherein said estimating step estimates the history factor according to the following equation:

##EQU4## where, ##EQU5## sets forth a predicted needs odds for a document per day;

D_i sets forth how many days since a document was last accessed;

F_i sets forth how frequently a document is accessed over a period of days; and

α

β

γ

set forth parameters that are estimated from a population of documents.

7. The method according to claim 4, further comprising the step specifying the context Q using a pre-identified set of documents.

8. The method according to claim 7, further comprising the step of expanding the context Q using a set of documents defined by those documents which are within a specified link radius of all documents in the set of pre-identified documents.

9. The method according to claim 4, further comprising the step of specifying the context Q for a sever by computing a union set of individual client contexts.

10. The method according to claim 4, wherein said estimating step estimates the context factor by computing correlation between the context Q and the recorded keywords of a document.

11. The method according to claim 1, further comprising the steps of:

fetching from a server documents in the needs list, beginning with those documents having the highest computed need probability; and

responsive to said fetching step, storing the fetched document in the memory of the computer.

12. The method according to claim 11, wherein said fetching step is performed before disconnecting the computer from a network.

13. The method according to claim 1, wherein said recording step is performed by a client computer while retrieving documents stored on servers coupled to a network.

14. The method according to claim 1, further comprising the steps of:

identifying documents stored in the memory of the computer that are no longer necessary; and

relegating those identified documents to a server on a network to increase memory available for storing documents on the computer.

15. A method for determining with a computer whether to prefetch and cache documents, comprising the steps of:

recording frequency data and recency data of the documents in a needs list stored in a memory of the computer;

said recording step recording in the needs list how recently the document is referenced and how frequently the document is referenced when a document request is received by the computer;

computing a need probability for the documents recorded in the needs list;

said computing step computing the need probability for the documents as a function of the recorded frequency data and recency data; and

identifying those documents in the needs list with the greatest computed need probability to be prefetched and cached in the memory of the computer.

16. The method according to claim 15, further comprising the step of recording context data for predicting relevancy of each document in the needs list.

17. The method according to claim 15, wherein said computing step computes the need probability for each document in the needs list using the following equation:

##EQU6## where, ##EQU7## sets forth a predicted needs odds for a document per day;

D_i sets forth how many days since a document was last accessed;

F_i sets forth how frequently a document is accessed over a period of days; and

α

β

γ

set forth parameters that are estimated from a population of documents.

18. An apparatus for determining whether to prefetch and cache documents, comprising:

a memory for storing a needs list of documents;

means for recording context data and history data of the documents in the needs list;

said recording means recording the context data and the history data when a document request is received;

means for computing a need probability for the documents recorded in the needs list;

said computing means computing the need probability for the documents as a function of the recorded context data and history data of the documents; and

means for identifying those documents in the needs list with the greatest computed need probability to be prefetched and cached in said memory.

19. The apparatus according to claim 18, wherein said recording means further comprises:

means for recording, in the needs list, how recently each document is referenced; and

means for recording, in the needs list, how frequently each document is referenced.

20. The apparatus according to claim 18, wherein said recording means further comprises:

means for recording, in the needs list, keywords of each document referenced; and

means for recording, in the needs list, links of each document referenced.