Methods and apparatus for using resource transition probability models for pre-fetching resources

• US 6,088,718 A
• Filed: 01/15/1998
• Issued: 07/11/2000
• Est. Priority Date: 01/15/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Altschuler, Steven J., Ridgeway, Greg
• Primary Examiner(s): Harrell, Robert B.
• Application Number:
  US09/007,901
• Time in Patent Office: 908 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 709/200, 709/209, 709/219, 709/201, 709/202, 709/203
• US Class Current: 709/203
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Building resource (e.g., Internet content) and attribute transition probability models and using such models for pre-fetching resources, editing resource link topology, building resource link topology templates, and collaborative filtering.

Claims

1. In a system comprising:

a client having a resource requester;

a server having a storage area, containing stored resources, and a resource retriever for accessing the storage area and servicing requests for any of the stored resources; and

a network connected between the client and the server and for facilitating communication therebetween;

a method for pre-fetching resources comprising the steps of;

(A) in the server, providing to the client from the server, in response to a fetch request, issued by the resource requester, for a particular resource, the particular resource and a list specifying both at least one resource and a corresponding probability measure associated therewith, the probability measure defining a measure of probability of the user transitioning from the particular resource to a corresponding resource specified in the list;

(B) in the client computer, selecting, in response to the corresponding probability measures associated with all the resources in the list, a specific resource to be pre-fetched and issuing a pre-fetch request to the server for the specific resource; and

(C) in the server;

(C1) in response to the pre-fetch request, downloading the specific resource from the server to the client computer;

(C2) forming the list from a plurality of resources then specified in usage logs stored in the server; and

(C3) updating the usage logs in response to the fetch request but not in response to the pre-fetch request.

2. The method of claim 1 further comprising the step, performed in the client computer, of storing the specific resource, obtained in response to the pre-fetch request, in a cache storage area of the client.

3. The method of claim 2 further comprising the step of reporting a cache hit from the client computer to the server computer if the specific resource resides within the cache storage area.

4. The method of claim 3 further comprising a step, in the server computer, of updating the list in response to the cache hit.

5. The method of claim 1 further comprising the step of downloading the specific resource whenever communications resources between the client and the server are idle.

6. The method of claim 1 further comprising the steps of:

monitoring communications resources between the client and the server; and

downloading, in response to the monitoring step, the specific resource whenever the communications resources between the client and the server are idle.

7. In a system having:

(A) a server computer comprising;

(A1) a storage area, which stores resources and usage logs, and a resource requester for accessing the storage area and servicing requests for any of the stored resources, wherein the usage logs specify individual ones of the stored resources that have been accessed by a client computer; and

(A2) a usage log maintainer for subsequently updating the usage logs in response to one of the stored resources having been provided by the server computer to the client computer; and

(B) a network for permitting communications to and from the server; and

(C) the client computer comprising;

(C1) a resource requester;

(C2) an input/output interface unit, coupled with the network and the resource requester, for receiving requested resources, pre-fetched resources and resource transition probability lists and for sending, to the server computer, fetch resource requests, in response to resource requests from the resource requester, and pre-fetch resource requests;

(C3) a storage area for storing the resource transition probability lists received by the input/output interface unit, wherein each of the resource transition probability lists has a first resource name, at least one second resource name, and a separate corresponding probability measure, the probability measure defining a probability of a user transitioning from the resource identified by the first resource name to a corresponding one of the resources, in the list, identified by said one second resource name;

(C4) a cache storage area for storing pre-fetched resources received by the input/output interface unit; and

(C5) a resource renderer for rendering the requested resource to a user; and

(D) wherein;

(D1) in response to a fetch request, for a particular resource identified by the first resource name, issued by the resource requester in the client, the server computer provides the particular resource and a corresponding one of the resource transition probability lists, via the network, to the client;

(D2) in response to the probabilities contained in the corresponding list, the pre-fetch resource requester of the client then generates a pre-fetch request to the server computer for a specific resource set forth in the list;

(D3) in response to the pre-fetch request, the specific resource is downloaded from the server into the cache storage area; and

(D4) the corresponding list is formed from a plurality of resources then specified in the usage logs, wherein the usage log maintainer updates the usage logs in response to the fetch request but not in response to the pre-fetch request.

8. The client of claim 7 wherein the resource requester comprises:

a user interface for accepting a user resource selection made by a user;

a navigator, responsive to the user interface, for forming the fetch request for the particular resource based on the user selection;

a pre-fetcher for forming the pre-fetch request based on the corresponding resource transition probability list; and

a cache manager, operative in response to the user resource selections, for storing pre-fetched resources to the cache storage area and for retrieving pre-fetched and cached resources from the cache storage area.

9. The client of claim 8 wherein the pre-fetcher forms the pre-fetch request when communications resources between the client and the server are idle, and, thereafter, provides the pre-fetch request to the input/output interface unit.

10. The client of claim 8 further comprising a communications resource monitor for monitoring communications resources between the client and the server, wherein, whenever the communications resource monitor determines that communications resources between the client and the server are idle, the pre-fetcher forms a pre-fetch request and provides the pre-fetch request to the input/output interface unit.

11. The client of claim 8 wherein when the cache management process retrieves a pre-fetched and cached resource in response to a user resource selection, the cache management process forming a cache hit message which is reported to the server.

12. A system comprising:

(A) a client computer, coupled to a network, comprising;

(A1) a pre-fetch resource requester;

(A2) a cache storage area which contains stored pre-fetched resources;

(A3) a resource transition probability list storage area;

(A4) a resource requester for requesting resources in response to user selections;

(A5) a resource renderer for rendering resources, received by the client, to a user; and

(A6) a cache manager for managing the cache storage area; and

(B) a server computer, also coupled to the network, comprising;

(B1) a storage area which contains stored resources and stored usage logs, the usage logs specifying individual ones of the stored resources that have been accessed by the client computer;

(B2) a resource retriever for accessing the storage area and for servicing requests from the client computer for the stored resources;

(B3) a usage log maintainer for subsequently updating the usage logs in response to a resource having been provided by the server to a client computer; and

(B4) a storage area storing a list of resources and associated probabilities, each of said probabilities being a measure of probability of the user transitioning from a particular resource specified in a fetch request to a corresponding one of the resources specified in the list; and

(C) wherein;

(C1) in response to a fetch request for the particular resource issued by the resource requester in the client, the server provides the particular resource and the list, via the network, to the client;

(C2) in response to the probabilities contained in the list, the pre-fetch resource requester of the client then generates a pre-fetch request to the server for a specific resource set forth in the list;

(C3) in response to the pre-fetch request, the specific resource is downloaded from the server into the cache storage area; and

(C4) the list is formed from a plurality of resources then specified in the usage logs, wherein the usage log maintainer updates the usage logs in response to the fetch request but not in response to the pre-fetch request.

13. The system of claim 12 wherein:

the cache manager generates a hit report when a user selects a pre-fetched resource stored in the cache storage;

the client computer transmits the hit report to the server; and

the usage log maintainer updates the usage logs in response to the hit report.