Methods and apparatus for building attribute transition probability models for use in pre-fetching resources

• US 6,195,622 B1
• Filed: 01/15/1998
• Issued: 02/27/2001
• 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): Teska, Kevin J.
• Assistant Examiner(s): Sergent, Douglas W.
• Application Number:
  US09/007,902
• Time in Patent Office: 1,139 Days
• Field of Search: 395/500.23, 709/203, 709/221, 709/223, 709/226-228, 709/240, 345/326, 345/335, 703/2
• US Class Current: 703/2
• 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. A method for building an attribute transition probability model based on attributes of resources referenced by a device, the method comprising steps of:

a) building a usage log, the usage log including information regarding an identification of attributes of resources referenced and regarding times at which the resources were referenced;

b) defining sessions based on the information regarding the times; and

c) determining attribute transition probabilities based on the information regarding an identification of the attributes of resources referenced and the defined sessions, wherein the attribute transition probability model is defined by the determined attribute transition probabilities and specifies probabilities associated with transitioning between first and second resources as a function of first and second attributes associated with said first and second resources, respectively, the first and second attributes being associated with and descriptive of corresponding first and second predefined intrinsic characteristics of the first and second resources, respectively, when the corresponding first or second resource is rendered, and wherein each of the first and second predefined characteristics specifies a predefined semantic-based classification into which content of the corresponding resource has been classified.

2. The method of claim 1 wherein the step of determining attribute transition probabilities includes sub-steps of:

i) counting a number of times that the first resource was referenced to generate a first count;

ii) counting a number of times that the second resource was referenced after the first resource was referenced to generate a second count; and

iii) determining a transition probability from the first resource to the second resource based on the first and second counts.

3. The method of claim 2 wherein the second count is decreased when a transition from the first resource to the second resource is possible but does not occur.

4. The method of claim 2 wherein the sub-step of determining a transition probability includes a step of dividing the second count by the first count.

5. The method of claim 1 wherein the step of determining attribute transition probabilities includes sub-steps of:

i) counting a number of different sessions in which the first resource was referenced to generate a first count;

ii) counting a number of different sessions in which the second resource was referenced after the first resource was referenced to generate a second count; and

iii) determining a transition probability from the first resource to the second resource based on the first and second counts.

6. The method of claim 5 wherein the second count is decreased when a transition from the first resource to the second resource is possible but does not occur.

7. The method of claim 5 wherein the sub-step of determining a transition probability includes a step of dividing the second count by the first count.

8. The method of claim 1 wherein the attribute transition probabilities are determined based on a first order Markov process.

9. The method of claim 1 wherein one of the attribute transition probabilities defines a probability that, within a session, the second resource will be referenced, after the first resource has been referenced.

10. The method of claim 9 wherein the one attribute transition probability is defined by:

a) counting a number of times the second resource is referenced after the first resource has been referenced to generate a first count;

b) counting a number of times the the first resource has been referenced to generate a second count; and

c) dividing the first count by the second count.

11. The method of claim 9 wherein the one attribute transition probability is defined by:

a) counting a number of times the first resource is referenced after the second resource has been referenced to generate a first count;

b) adding a first constant to the first count to generate a first value;

c) counting a number of times the first resource has been referenced to generate a second count;

d) adding a second constant to the second count to generate a second value; and

e) dividing the first value by the second value.

12. The method of claim 11 wherein the first and second constants are non-negative parameters of a prior distribution.

13. The method of claim 11 wherein the first and second constants are prior belief estimates.

14. The method of claim 1 wherein the sessions defined are based on a period of activity in which resources are requested, followed by a period of inactivity in which no resources are requested.

15. A method for building an attribute transition probability model based on a usage log including information regarding an identification of attributes of referenced and regarding times at which the resources were referenced, wherein acting upon includes an action selected from a group consisting of requesting a resource and rendering a resource, the method comprising steps of:

a) defining sessions based on the information regarding the times; and

b) determining attribute transition probabilities based on the information regarding an identification of the attributes of resources referenced and the defined sessions, wherein the attribute transition probability model is defined by the determined attribute transition probabilities and specifies probabilities associated with transitioning between first and second resources as a function of first and second attributes associated with said first and second resources, respectively, the first and second attributes being associated with and descriptive of corresponding first and second predefined intrinsic characteristics of the first and second resources, respectively, when the corresponding first or second resource is rendered, and wherein each of the first and second predefined characteristics specifies a predefined semantic-based classification into which content of the corresponding resource has been classified.

16. The method of claim 15 wherein the step of determining attribute transition probabilities includes sub-steps of:

i) counting a number of times that the first resource was referenced to generate a first count;

ii) counting a number of times that the second resource was referenced after the first resource was referenced to generate a second count; and

iii) determining a transition probability from the first resource to the second resource based on the first and second counts.

17. The method of claim 16 wherein the second count is decreased when a transition from the first resource to the second resource is possible but does not occur.

18. The method of claim 16 wherein the sub-step of determining a transition probability includes a step of dividing the second count by the first count.

19. The method of claim 15 wherein the step of determining attribute transition probabilities includes sub-steps of:

i) counting a number of different sessions in which the first resource was referenced to generate a first count;

ii) counting a number of different sessions in which the second resource was referenced after the first resource was referenced to generate a second count; and

iii) determining a transition probability from the first resource to the second resource based on the first and second counts.

20. The method of claim 19 wherein the second count is decreased when a transition from the first resource to the second resource is possible but does not occur.

21. The method of claim 19 wherein the sub-step of determining a transition probability includes a step of dividing the second count by the first count.

22. The method of claim 15 wherein the attribute transition probabilities are determined based on a first order Markov process.

23. The method of claim 15 wherein one of the attribute transition probabilities defines a probability that, within a session, the second resource will be referenced, after the first resource has been referenced.

24. The method of claim 23 wherein the one attribute transition probability is defined by:

a) counting a number of times the second resource is referenced after the first resource has been referenced to generate a first count;

b) counting a number of times the first resource has been referenced to generate a second count; and

c) dividing the first count by the second count.

25. The method of claim 23 wherein the one attribute transition probability is defined by:

a) counting a number of times the first resource is referenced after the second resource has been referenced to generate a first count;

b) adding a first constant to the first count to generate a first value;

c) counting a number of times the first resource has been referenced to generate a second count;

d) adding a second constant to the second count to generate a second value; and

e) dividing the first value by the second value.

26. The method of claim 25 wherein the first and second constants are non-negative parameters of a prior distribution.

27. The method of claim 25 wherein the first and second constants are prior belief estimates.

28. The method of claim 15 wherein the sessions defined are based on a period of activity in which resources are referenced, followed by a period of inactivity in which no resources are referenced.

29. The method of claim 15 wherein referencing either the first or second resource is an action selected from a group consisting of requesting, retrieving, returning, and rendering a resource.

30. A method for determining attribute transition probabilities based on usage trace data including information regarding (i) an identification of attributes of resources referenced, and (ii) an identification of sessions defined by a period of activity in which resources are referenced, followed by a period of inactivity in which no resources are referenced, the method comprising steps of:

a) counting a number of times that a first resource associated with a first attribute was referenced to generate a first count;

b) counting a number of times that a second resource associated with a second attribute was referenced after the first resource was referenced to generate a second count; and

c) determining a transition probability from the first resource to the second resource based on the first and second counts, wherein the first and second attributes are associated with and descriptive of associated first and second predefined intrinsic characteristics of the first and second resources, respectively, when the corresponding first or second resource is rendered, and wherein each of the first and second predefined characteristics specifies a predefined semantic-based classification into which content of the corresponding resource has been classified.

31. The method of claim 30 wherein the second count is decreased when a transition from the first resource to the second resource is possible but does not occur.

32. The method of claim 30 wherein the sub-step of determining a transition probability includes a step of dividing the second count by the first count.

33. The method of claim 30 wherein referencing either the first or second resource is an action selected from a group consisting of requesting, retrieving, returning, and rendering a resource.

34. A method for determining attribute transition probabilities based on usage trace data including information regarding (i) an identification of attributes of resources referenced, and (ii) an identification sessions defined by a period of activity in which resources are referenced, followed by a period of inactivity in which no resources are referenced, the method comprising steps of:

a) counting a number of different sessions in which a first resource associated with a first attribute was referenced to generate a first count;

b) counting a number of different sessions in which a second resource associated with a second attribute was referenced after the first resource was referenced to generate a second count; and

c) determining a transition probability from the first resource to the second resource based on the first and second counts, wherein the first and second attributes are associated with and descriptive of associated first and second predefined intrinsic characteristics of the first and second resources, respectively, when the corresponding first or second resource is rendered, and wherein each of the first and second predefined characteristics specifies a predefined semantic-based classification into which content of the corresponding resource has been classified.

35. The method of claim 34 wherein the second count is decreased when a transition from the first resource to the second resource is possible but does not occur.

36. The method of claim 34 wherein the sub-step of determining a transition probability includes a step of dividing the second count by the first count.

37. The method of claim 34 wherein referencing either the first or second resource is an action selected from a group consisting of requesting, retrieving, returning, and rendering a resource.

38. A method for determining attribute transition probabilities based on usage trace data including information regarding (i) an identification of attributes of resources referenced, and (ii) an identification sessions defined by a period of activity in which resources are referenced, followed by a period of inactivity in which no resources are referenced, the method comprising steps of:

a) counting a number of times a first resource associated with the first attribute is referenced after a second resource associated with the second attribute has been referenced to generate a first count, wherein the first and second attributes are associated with and descriptive of corresponding first and second predefined intrinsic characteristics of the first and second resources, respectively, when the corresponding first or second resource is rendered, and wherein each of the first and second predefined characteristics specifies a predefined semantic-based classification into which content of the corresponding resource has been classified;

b) adding a first constant to the first count to generate a first value;

c) counting a number of times the first resource has been referenced to generate a second count;

d) adding a second constant to the second count to generate a second value; and

e) dividing the first value by the second value.

39. The method of claim 38 wherein the first and second constants are non-negative parameters of a prior distribution.

40. The method of claim 38 wherein the first and second constants are prior belief estimates.

41. The method of claim 38 wherein referencing either the first or second resource is an action selected from a group consisting of requesting, retrieving, returning, and rendering.

42. A device comprising:

a) a resource requester;

b) a resource renderer;

c) a usage log storage area, wherein usage logs stored in the usage log storage area include information regarding an identification of attributes of resources referenced and times at which the resources were referenced;

d) an attribute transition probability model generator for building attribute transition probability models based on usage logs stored in the usage log storage area, wherein said attribute transition model generator includes;

i) a session definer for defining sessions based on information regarding the times; and

ii) a probability determiner for determining attribute transition probabilities based on the information regarding the identification of attributes and the defined sessions, wherein the attribute transition probability models are defined by the attribute transition probabilities and specifies probabilities associated with transitioning between first and second resources as a function of first and second attributes associated with said first and second resources, respectively, the first and second attributes being associated with and descriptive of corresponding first and second predefined intrinsic characteristics of the first and second resources, respectively, when the corresponding first or second resource is rendered, and wherein each of the first and second predefined characteristics specifies a predefined semantic-based classification into which content of the corresponding resource has been classified; and

e) a model storage area for storing the attribute transition probability models built by the means for building attribute transition probability models.

43. The device of claim 42 wherein the probability determiner of the attribute transition probability model generator includes:

i) means for counting a number of times that the first resource was referenced to generate a first count;

ii) means for counting a number of times that the second resource was referenced after the first resource was referenced to generate a second count; and

iii) means for generating a transition probability from the first resource to the second resource based on the first and second counts.

44. The device of claim 43 wherein the attribute transition probability model generator includes means for decreasing the second count when a transition from the first resource to the second resource is possible but does not occur.

45. The device of claim 43 wherein the means for generating of the attribute transition probability model generator include means for dividing the second count by the first count.

46. The device of claim 42 wherein the attribute transition probability model generator includes:

a) means for counting a number of times the first resource is referenced after the second resource has been referenced to generate a first count;

b) means for adding a first constant to the first count to generate a first value;

c) means for counting a number of times the first resource has been referenced to generate a second count;

d) means for adding a second constant to the second count to generate a second value; and

e) means for dividing the first value by the second value.

47. The method of claim 46 wherein the first and second constants are non-negative parameters of a prior distribution.

48. The method of claim 46 wherein the first and second constants are prior belief estimates.