Methods and apparatus for building resource transition probability models for use in pre-fetching resources, editing resource link topology, building resource link topology templates, and collaborative filtering

• US 6,012,052 A
• Filed: 01/15/1998
• Issued: 01/04/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): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/007,900
• Time in Patent Office: 719 Days
• Field of Search: 707/1-206
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

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 generating a resource transition probability model based on resources referenced, the method comprising steps of:

a) generating a usage log including information regarding (i) an identification of clients which requested the resources referenced, (ii) an identification of the resources referenced, and (iii) an identification of times when the resources were referenced,

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

c) determining resource transition probabilities based on the identification of clients, the identification of resources referenced, and the defined sessions, wherein the resource transition probability model is defined by the determined resource transition probabilities.

2. The method of claim 1 wherein the step of generating a usage log includes a sub-step of filtering data based on the identification of users.

3. The method of claim 1 wherein the step of generating a usage log includes a sub-step of filtering data based on the identification of the resources acted upon.

4. The method of claim 1 wherein the step of generating a usage log includes a sub-step of filtering data based on the identification of the times.

5. The method of claim 1 wherein the step of generating a usage log includes a sub-step of filtering data based on at least two of (A) the identification of users, (B) the identification of the resources referenced, and (C) the identification of the times.

6. The method of claim 1 wherein the step of determining resource transition probabilities based on the identification of users, the identification of resources, and the defined sessions includes sub-steps of:

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

ii) counting a number of times that a 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.

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

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

9. The method of claim 6 wherein the transition probabilities between resources are determined independent of probabilities of transitions via intermediate resources.

10. The method of claim 1 wherein the step of determining resource transition probabilities based on the identification of users, the identification of resources, and the defined sessions includes sub-steps of:

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

ii) counting a number of different sessions in which a 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.

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

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

13. The method of claim 10 wherein the transition probabilities between resources are determined independent of probabilities of transitions via intermediate resources.

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

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

16. The method of claim 15 wherein the probability is defined by:

a) counting a number of times the second resources 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.

17. The method of claim 15 wherein the 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) 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.

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

19. The method of claim 17 wherein the first and second constants are prior belief estimates.

20. The method of claim 1 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.

21. The method of claim 1 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.

22. A method for generating a resource transition probability model based on a usage log including information regarding (i) an identification of clients which requested resources referenced, (ii) an identification of the resources referenced, and (iii) an identification of times when the resources were referenced, the method comprising steps of:

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

b) determining resource transition probabilities based on the identification of clients, the identification of resources referenced, and the defined sessions, wherein the resource transition probability model is defined by the determined resource transition probabilities.

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

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

a) counting a number of times the second resources 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 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) adding the first count to a first constant to generate a first value; and

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

d) adding the second count to a second constant 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 22 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 22 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.

30. A method for determining resource transition probabilities based on usage trace data including information regarding (i) an identification of clients which requested resources, (ii) an identification of resources referenced, and (iii) 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) determining a number of times that a second resource is referenced after a first resource has been referenced to generate a first value;

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

c) dividing the first value by the second value to generate a resource transition probability from the first resource to the second resource.

31. The method of claim 30 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.

32. A method for determining resource transition probabilities based on usage trace data including information regarding (i) an identification of clients which requested resources, (ii) an identification of resources referenced, and (iii) 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) determining a number of times that a second resource is referenced after a first resource has been referenced, and adding a first constant value, to generate a first value;

b) determining a number of times the first resource has been referenced, and adding a second constant value, to generate a second value; and

c) dividing the first value by the second value to generate a resource transition probability from the first resource to the second resource.

33. The method of claim 32 wherein the first and second constant values are non-negative parameters of a prior distribution.

34. The method of claim 32 wherein the first and second constant values are prior belief estimates.

35. The method of claim 32 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.

36. In a system including a server for servicing requests for resources, a device for generating a resource transition probability model based on resources referenced, the device including:

a) a usage log generation unit for generating usage logs including information regarding (i) an identification of clients which requested the resources referenced, (ii) an identification of the resources referenced, and (iii) an identification of times when the resources were referenced;

b) a preprocessor for defining sessions based on the information regarding the identification of clients and the identification of the times; and

c) a resource transition probabilities determining unit for generating resource transition probabilities based on the identification of clients, the identification of resources retrieved, and the defined sessions.

37. The device of claim 36 wherein preprocessor includes a filter for filtering data based on the identification of users.

38. The device of claim 36 wherein the preprocessor includes a filter for filtering data based on the identification of the resources referenced.

39. The device of claim 36 wherein the preprocessor includes a filter for filtering data based on the identification of the times.

40. The device of claim 36 wherein the usage log generation unit is a process effected by a machine executing instructions.

41. The device of claim 36 wherein the preprocessor is a process effected by a machine executing instructions.

42. The device of claim 36 wherein the resource transition probabilities determining unit is a process effected by a machine executing instructions.

43. The device of claim 36 wherein the resource transition probabilities determining unit includes:

i) means for determining a number of times that a second resource is referenced after a first resource has been referenced, and adding a first constant value, to generate a first value;

ii) means for determining a number of times the first resource has been referenced, and adding a second constant value, to generate a second value; and

iii) means for dividing the first value by the second value to generate a resource transition probability from the first resource to the second resource.

44. The device of claim 43 wherein the first and second constant values are non-negative parameters of a prior distribution.

45. The device of claim 43 wherein the first and second constant values are prior belief estimates.

46. The device of claim 36 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.

47. In a system including a server for servicing requests for resources, and a usage log including information regarding (i) an identification of clients which requested resources referenced, (ii) an identification of resources referenced, and (iii) an identification of times when the resources were referenced, a device for generating a resource transition probability model based on resources referenced by the server, the device including:

a) a preprocessor for defining sessions based on the information regarding the identification of clients and the identification of the times; and

b) a resource transition probability determining unit for determining resource transition probabilities based on the identification of clients, the identification of resources referenced, and the defined sessions.

48. The device of claim 47 wherein the preprocessor includes a filter for filtering data based on the identification of users.

49. The device of claim 47 wherein the preprocessor includes a filter for filtering data based on the identification of the resources referenced.

50. The device of claim 47 wherein the preprocessor includes a filter for filtering data based on the identification of the times.

51. The device of claim 47 wherein the preprocessor is a process effected by a machine executing instructions.

52. The device of claim 47 wherein the resource transition probabilities determining unit is a process effected by a machine executing instructions.

53. The device of claim 47 wherein the resource transition probabilities determining unit includes:

i) means for determining a number of times that a second resource is referenced after a first resource has been acted upon, and adding a first constant value, to generate a first value;

ii) means for determining a number of times the first resource has been referenced, and adding a second constant value, to generate a second value; and

iii) means for dividing the first value by the second value to generate a resource transition probability from the first resource to the second resource.

54. The device of claim 53 wherein the first and second constant values are non-negative parameters of a prior distribution.

55. The device of claim 53 wherein the first and second constant values are prior belief estimates.

56. The device of claim 47 wherein referenced is an action selected from a group consisting of requested, retrieved, returned and rendered.

57. In a system including a server for servicing requests for resources, and usage trace data including information regarding (i) an identification of clients which requested the resources, (ii) an identification of the resources referenced, and (iii) an identification of sessions, a device for determining resource transition probabilities, the device comprising:

i) means for determining a number of times that a second resource is referenced after a first resource has been referenced, and adding a first constant value, to generate a first value;

ii) means for determining a number of times the first resource has been referenced, and adding a second constant value, to generate a second value; and

iii) means for dividing the first value by the second value to generate a resource transition probability from the first resource to the second resource.

58. The system of claim 57 wherein the first and second constant values are non-negative parameters of a prior distribution.

59. The system of claim 57 wherein the first and second constant values are prior belief estimates.

60. The system of claim 57 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.

61. In a system including a server for servicing requests, from a number of clients, for resources, device for generating resource transition probabilities, the device comprising:

a) a log generation unit for generating usage logs based on said requests; and

b) a resource transition probability generation unit for determining the resource transition probabilities based on the usage logs.

62. The device of claim 61 wherein the usage logs include information regarding (i) an identification of the clients which requested the resources, (ii) an identification of the resources referenced, and (iii) an identification of times when the resources were referenced.

63. The device of claim 62 wherein the server service requests for resources based on user selections and based on pre-fetch requests, and

wherein the log generation unit ignores requests for resources based on a pre-fetch request.

64. The device of claim 63 wherein the log generation unit recognizes requests for resources based on a pre-fetch request only after such resources are rendered at a client.

65. The device of claim 61 wherein the resource transition probability unit includes:

i) means for determining a number of times that a second resource is referenced after a first resource has been referenced, and adding a first constant value, to generate a first value;

ii) means for determining a number of times the first resource has been referenced, and adding a second constant value, to generate a second value; and

iii) means for dividing the first value by the second value to generate a resource transition probability from the first resource to the second resource.

66. A method for generating clusters of users, each having an associated resource transition probability model, based on a usage log including information regarding (i) an identification of clients which requested resources referenced, (ii) an identification of the resources referenced, and (iii) an identification of times when the resources were referenced, the method comprising steps of:

a) selecting a number of clusters; and

b) determining a resource transition probability model for each cluster based on the identification of clients, the identification of resources retrieved, and the identification of times when the resources were referenced.

67. The method of claim 66 wherein the step of determining the resource transition probability models includes a sub-step of maximizing a likelihood function that the resource transition probability models belong to the clusters in view of the usage log.

68. The method of claim 67 wherein the sub-step of maximizing a likelihood function is performed in accordance with an expectation maximization algorithm.

69. The method of claim 66 wherein the step of determining the resource transition probability models includes a sub-step of determining free parameters of a likelihood function in accordance with a Gibbs algorithm.

70. The method of claim 66 wherein the step of determining the resource transition probability models includes a sub-step of determining free parameters of a likelihood function in accordance with a hybrid expectation maximization and Gibbs algorithm.

71. The method of claim 66 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.