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

• US 6,154,767 A
• Filed: 01/15/1998
• Issued: 11/28/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): Chan, Eddie P.
• Assistant Examiner(s): Encarnacion, Yamir
• Application Number:
  US09/007,898
• Time in Patent Office: 1,048 Days
• Field of Search: 711/137, 707/501, 709/223, 709/217, 709/218, 709/219, 709/203, 709/213, 709/216, 706/21
• 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 including

a client having:

a resource requester,

a resource cache storage area,

a cache manager for managing the resource cache storage area,

a client list storage area for storing a list of resources available for pre-fetching and corresponding attributes of the available resources,

an attribute transition probability model storage area, wherein the attribute transition probability model specifies probabilities associated with transitioning between first and second resources specified in the list as a function of the attribute associated with each of said first and second resources, the attribute being associated with and descriptive of a predefined characteristic, associated with the content, of an corresponding resource itself when the corresponding resource is rendered by the client, and

a pre-fetcher for generating a pre-fetch resource request based on contents of the list and the attribute transition probability model, and

a server having;

a resource storage area,

a server list storage area, and

a resource retriever for servicing requests for resources,

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

a) sending, in response to a resource request from the resource requester of the client, a list of resources available for pre-fetching and corresponding attributes of said available resources from the server list storage area to the client list storage area;

b) determining an attribute of a particular resource from the list to pre-fetch based on the attribute of a resource specified in the resource request and the attribute transition probability model; and

c) determining the particular resource to pre-fetch based on the attribute determined in step (b) and the list sent in step (a).

2. The method of claim 1 further comprising a step of:

d) generating a request to pre-fetch the particular resource determined in step (c).

3. The method of claim 1 further comprising steps of:

d) determining whether a communications path between the client and the server is idle; and

e) generating a request to pre-fetch the particular resource determined in step (c) if the communications path has been determined to be idle in step (d).

4. The method of claim 3 further comprising a step of:

f) sending, in response to the request to pre-fetch the particular resource generated in step (e), the particular resource from the resource storage area of the server to the client.

5. The method of claim 4 further comprising a step of:

g) storing the particular resource in the resource cache storage area of the client.

6. The method of claim 5 further comprising a step of:

h) reporting, in response to a request from the resource requester for the particular resource stored in the resource cache storage area of the client, a cache hit of the pre-fetched resource to the server.

7. The method of claim 6 further comprising a step of:

i) sending, in response to the cache hit of the pre-fetched resource report of step (h), a list of at least one attribute of at least one resource linked with the pre-fetched resource, to the client.

8. The method of claim 7 further comprising a step of:

j) storing the list sent in step (i) in the list storage area of the client.

9. The method of claim 1 wherein the list comprises attributes of resources linked with a resource of the request, and information for addressing of the resources specified in the list.

10. The method of claim 1 wherein the attribute transition probability model comprises a first group of at least one attribute, a second group of at least one attribute, and associated probabilities that a second resource having an attribute of the second group will be referenced after a first resource having an attribute of the first group has been referenced.

11. The method of claim 10 wherein the client, in referencing the first or second resource undertakes an action, with respect to the first or second resource, selected from a group consisting of requesting, retrieving, returning, and rendering the first or second resource, respectively.

12. The method of claim 9 wherein the attribute transition probability model comprises a first group of at least one attribute, a second group of at least one attribute, and associated probabilities that a second resource having an attribute of the second group will be referenced after a first resource having an attribute of the first group has been referenced.

13. The method of claim 12 wherein the client, in referencing the first or second resource undertakes an action, with respect to the first or second resource, selected from a group consisting of requesting, retrieving, returning, and rendering the first or second resource, respectively.

14. The method of claim 10 further comprising the steps of:

d) sending, in response to the resource request from the resource requester of the client, a resource specified in the request, from the resource storage area of the server to a resource renderer of the client; and

e) rendering the resource specified in the request.

15. The method of claim 14 wherein the attribute transition probability model is updated based on the resource rendered.

16. In a system comprising:

a server having;

a resource storage area,

a list storage area,

a resource retriever for servicing requests for resources, and

a server input/output interface unit for communicatively coupling the server to a network,

a client comprising;

a) a client input/output interface unit for communicatively coupling the client to the network;

b) a resource requester for generating a resource request, the resource requester being able to communicate with the client input/output interface unit;

c) a resource cache storage area;

d) a cache manager for managing the resource cache storage area, the cache manager being able to communicate with the client input/output interface unit;

e) a client list storage area for storing a list of resources available for pre-fetching and corresponding attributes of the resources;

f) an attribute transition probability model storage area which stores an attribute transition probability model, wherein the attribute transition probability model specifies probabilities associated with transitioning between first and second resources specified in the list as a function of the attribute associated with each of said first and second resources, the attribute being associated with and descriptive of a predefined characteristic, associated with the content, of an corresponding resource itself when the corresponding resource is rendered by the client; and

g) a pre-fetcher for generating a pre-fetch resource request based on contents of the list and the attribute transition probability model, the pre-fetcher being able to communicate with the client input/output interface unit.

17. The device of claim 16 wherein the client input/output interface unit receives, in response to a resource request from the resource requester of the client, the list from the server list storage area so as to define a received list, and

wherein the received list is provided to the client list storage area.

18. The device of claim 17 wherein the pre-fetcher comprises:

i) a first determiner for determining an attribute of a particular resource to pre-fetch based on an attribute of a resource specified in the resource request and the attribute transition probability model, and

ii) a second determiner for determining the resource to pre-fetch based on the attribute determined by the first determiner and the list provided to the client list storage area.

19. The device of claim 18 wherein the pre-fetcher further comprises:

iii) a generator for generating a request to pre-fetch the particular resource.

20. The device of claim 19 further comprising:

h) a monitor for determining whether a communications path between the client and the server is idle, wherein the generator generates a request to pre-fetch the particular resource if the communications path is idle.

21. The device of claim 20 wherein the client input/output interface receives, in response to the request to pre-fetch the particular resource, the particular resource from the resource storage area of the server.

22. The device of claim 21 wherein the resource cache storage area of the client stores the particular resource received by the client input/output interface unit.

23. The device of claim 22 wherein the cache manager, in response to a request for the particular resource from the resource requester, generates a cache hit report of a pre-fetched resource, wherein the cache hit is reported to the server.

24. The device of claim 23 wherein the client input/output interface unit receives, in response to the cache hit report sent to the server, a list of at least one attribute of at least one resource linked with a pre-fetched resource reported in the cache hit report.

25. The device of claim 24 wherein the client list storage area stores the list received by the client input/output interface unit.

26. The device of claim 17 wherein the list comprises attributes of resources linked with the particular resource specified in the request, and information for addressing the resources specified in the list.

27. The device of claim 16 wherein the attribute transition probability model comprises a first group of at least one attribute, a second group of at least one attribute, and associated probabilities that a second resource having an attribute of the second group will be referenced after a first resource having an attribute of the first group has been referenced.

28. The device of claim 27 wherein the client, in referencing the first or second resource undertakes an action, with respect to the first or second resource, selected from a group consisting of requesting, retrieving, returning, and rendering the first or second resource, respectively.

29. The device of claim 26 wherein the attribute transition probability model comprises a first group of at least one attribute, a second group of at least one attribute, and associated probabilities that a second resource having an attribute of the second group will be referenced after a first resource having an attribute of the first group has been referenced.

30. The device of claim 29 wherein the client, in referencing the first or second resource undertakes an action, with respect to the first or second resource, selected from a group consisting of requesting, retrieving, returning, and rendering the first or second resource, respectively.

31. The device of claim 16 further comprising:

i) a resource renderer, the resource renderer being able to communicate with the client input/output interface unit,

wherein the client input/output interface unit receives, in response to a resource request from the resource requester of the client, the particular resource, from the resource storage area of the server, and

wherein the particular resource is provided to the resource renderer.

32. The device of claim 27 further comprising:

j) an attribute transition probability model maintenance unit,

wherein the attribute transition probability model is updated based on the particular resource.

33. In a system comprising:

a client having;

a client input/output interface unit for communicatively coupling the client to a network;

a resource requester for generating a resource request, the resource requester being able to communicate with the client input/output interface unit;

a resource cache storage area;

a cache manager for managing the resource cache storage area, the cache manager being able to communicate with the client input/output interface unit;

a client list storage area for storing a list of resources available for pre-fetching and corresponding attributes of said available resources;

an attribute transition probability model storage area which stores an attribute transition probability model, wherein the attribute transition probability model specifies probabilities associated with transitioning between first and second resources specified in the list as a function of the attribute associated with each of said first and second resources, the attribute being associated with and descriptive of a predefined characteristic, associated with the content, of an corresponding resource itself when the corresponding resource is rendered by the client; and

a pre-fetcher for generating a pre-fetch resource request based on contents of the list and contents of the attribute transition probability model, the pre-fetcher being able to communicate with the client input/output interface unit, and

a server comprising;

a) a resource storage area for storing a plurality of resources, at least some of the resources stored therein having at least one attribute associated therewith;

b) a server list storage area for storing a plurality of lists, the lists including attributes of resources linked with the resources stored in the resource storage area;

c) a resource retriever for servicing requests for resources; and

d) a server input/output interface unit for communicatively coupling the server to the network.

34. The device of claim 33 wherein the resource retriever, in response to a resource request from the resource requester of the client, sends a selected one of the plurality of lists from the server list storage area to the client.

35. The device of claim 33 wherein the resource retriever, in response to a pre-fetch resource request, sends a given resource specified in the pre-fetch resource request from the resource storage area to the client.

36. The device of claim 33 wherein the resource retriever, in response to a received cache hit report from the client, sends a list of at least one attribute of at least one resource linked with a pre-fetched resource identified in the received cache hit report.

37. A system for use in an environment having a network, the system comprising:

a) a server having;

i) a server input/output interface unit for communicatively coupling the server to a network,

ii) a resource storage area,

iii) a server list storage area, and

iv) a resource retriever for servicing requests for resources, the resource retriever being able to communicate with the server input/output interface unit; and

b) a client having;

i) a client input/output interface unit for communicatively coupling the client to the network;

ii) a resource requester, the resource requester being able to communicate with the client input/output interface unit;

iii) a resource cache storage area;

iv) a cache manager for managing the resource cache storage area, the cache manager being able to communicate with the client input/output interface unit;

v) a client list storage area for storing a list of resources available for pre-fetching and corresponding attributes of said available resources

vi) an attribute transition probability model storage area which stores an attribute transition probability model, wherein the attribute transition probability model specifies probabilities associated with transitioning between first and second resources specified in the list as a function of the attribute associated with each of said first and second resources, the attribute being associated with and descriptive of a predefined characteristic associated with the content, of an corresponding resource itself when the corresponding resource is rendered by the client; and

vii) a pre-fetcher for generating a pre-fetch resource request based on contents of the list and the attribute transition probability model, the pre-fetcher being able to communicate with the client input/output interface unit.

38. The system of claim 37 wherein the resource retriever, in response to a resource request from the resource requester of the client, sends a list from the server list storage area to the client, and

wherein after the list is received by the client input/output interface unit, the list is provided to the client list storage area.

39. The system of claim 38 wherein the pre-fetcher comprises:

A) a first determiner for determining an attribute of a particular resource to pre-fetch based on an attribute of a resource specified in the resource request and the attribute transition probability model, and

B) a second determiner for determining the particular resource to pre-fetch based on the attribute determined by the first determiner and the list provided to the client list storage area.

40. (amended) The system of claim 39 wherein the pre-fetcher further comprises:

C) a generator for generating a request to pre-fetch the particular resource.

41. The system of claim 40 wherein the client further comprises:

vii) a monitor for determining whether a communications path between the client and the server is idle, wherein the generator generates a request to pre-fetch the particular resource if the communications path is idle.

42. The system of claim 41 wherein the resource retriever sends from the resource storage area of the server to the client input/output interface, in response to the pre-fetch request, the particular resource.

43. The system of claim 42 wherein the resource cache storage area of the client stores the particular resource received by the client input/output interface.

44. The system of claim 43 wherein the cache manager, in response to a request for the particular resource stored in the resource cache storage area of the client from the resource requester, generates a cache hit report of the pre-fetched resource, wherein a cache hit is reported to the server.

45. The system of claim 44 wherein the resource retriever sends to the client input/output interface unit, n response to the cache hit report sent to the server, a list of at least one attribute of at least one resource linked with a pre-fetched resource reported in the cache hit report.

46. The system of claim 45 wherein the client list storage area stores the list received by the client input/output interface unit.

47. The system of claim 38 wherein the list comprises attributes of resources linked with the particular resource specified in the request, and information for addressing the resources specified in the list.

48. The system of claim 37 wherein the attribute transition probability model comprises a first group of at least one attribute, a second group of at least one attribute, and associated probabilities that a second resource having an attribute of the second group will be referenced after a first resource having an attribute of the first group has been referenced.

49. The system of claim 48 wherein the client, in referencing the first or second resource undertakes an action, with respect to the first or second resource, selected from a group consisting of requesting, retrieving, returning, and rendering the first or second resource, respectively.

50. The system of claim 48 wherein the attribute transition probability model comprises a first group of at least one attribute, a second group of at least one attribute, and associated probabilities that a second resource having an attribute of the second group will be referenced after a first resource having an attribute of the first group has been referenced.

51. The system of claim 50 wherein the client, in referencing the first or second resource undertakes an action, with respect to the first or second resource, selected from a group consisting of requesting, retrieving, returning, and rendering the first or second resource, respectively.

52. The system of claim 37 wherein the client further comprises a resource renderer, the resource renderer being able to communicate with the client input/output interface unit,

wherein the resource retriever sends from the resource storage area of the server to the client input/output interface unit, in response to a resource request from the resource requester, the particular resource, and

wherein the particular resource is provided to the resource renderer.

53. The system of claim 52 wherein the client further comprises an attribute transition probability model maintenance unit,

wherein the attribute transition probability model is updated based on the particular resource.