US6012052A
Expired / Lapsed
US
⏱️ 0.0 years remaining
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
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-01-15
•
Granted: 2000-01-04
•
Expires: 2018-01-15
Abstract
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.
Inventors
- 👤 Steven J. Altschuler
- 👤 Greg Ridgeway
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 03:52
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/957; G06F16/9574; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99941; Y10S707/99943; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 80
Claim 1
Independent Claim
107 words
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.
Claim 2
Independent Claim
107 words
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.
Claim 3
Dependent Claim
25 words
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.
Claim 4
Dependent Claim
28 words
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.
Claim 5
Dependent Claim
26 words
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.
Claim 6
Dependent Claim
44 words
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.
Claim 7
Dependent Claim
91 words
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.
Claim 8
Dependent Claim
28 words
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.
Claim 9
Dependent Claim
25 words
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.
Claim 10
Dependent Claim
21 words
The method of claim 6 wherein the transition probabilities between resources are determined independent of probabilities of transitions via intermediate resources.
Claim 11
Dependent Claim
95 words
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.
Claim 12
Dependent Claim
28 words
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.
Claim 13
Dependent Claim
25 words
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.
Claim 14
Dependent Claim
21 words
The method of claim 10 wherein the transition probabilities between resources are determined independent of probabilities of transitions via intermediate resources.
Claim 15
Dependent Claim
19 words
The method of claim 1 wherein the resource transition probabilities are determined based on a first order Markov process.
Claim 16
Dependent Claim
30 words
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.
Claim 17
Dependent Claim
61 words
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.
Claim 18
Dependent Claim
89 words
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.
Claim 19
Dependent Claim
18 words
The method of claim 17 wherein the first and second constants are non-negative parameters of a prior distribution.
Claim 20
Dependent Claim
15 words
The method of claim 17 wherein the first and second constants are prior belief estimates.
Claim 21
Dependent Claim
33 words
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.
Claim 22
Dependent Claim
21 words
The method of claim 1 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.
Claim 23
Independent Claim
102 words
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.
Claim 24
Independent Claim
102 words
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.
Claim 25
Dependent Claim
30 words
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.
Claim 26
Dependent Claim
61 words
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.
Claim 27
Dependent Claim
90 words
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.
Claim 28
Dependent Claim
18 words
The method of claim 25 wherein the first and second constants are non-negative parameters of a prior distribution.
Claim 29
Dependent Claim
15 words
The method of claim 25 wherein the first and second constants are prior belief estimates.
Claim 30
Dependent Claim
33 words
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.
Claim 31
Dependent Claim
21 words
The method of claim 22 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.
Claim 32
Independent Claim
127 words
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.
Claim 33
Independent Claim
127 words
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.
Claim 34
Dependent Claim
21 words
The method of claim 30 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.
Claim 35
Independent Claim
139 words
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.
Claim 36
Independent Claim
139 words
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.
Claim 37
Dependent Claim
19 words
The method of claim 32 wherein the first and second constant values are non-negative parameters of a prior distribution.
Claim 38
Dependent Claim
16 words
The method of claim 32 wherein the first and second constant values are prior belief estimates.
Claim 39
Dependent Claim
21 words
The method of claim 32 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.
Claim 40
Dependent Claim
117 words
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.
Claim 41
Dependent Claim
117 words
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.
Claim 42
Dependent Claim
19 words
The device of claim 36 wherein preprocessor includes a filter for filtering data based on the identification of users.
Claim 43
Dependent Claim
22 words
The device of claim 36 wherein the preprocessor includes a filter for filtering data based on the identification of the resources referenced.
Claim 44
Dependent Claim
21 words
The device of claim 36 wherein the preprocessor includes a filter for filtering data based on the identification of the times.
Claim 45
Dependent Claim
20 words
The device of claim 36 wherein the usage log generation unit is a process effected by a machine executing instructions.
Claim 46
Dependent Claim
17 words
The device of claim 36 wherein the preprocessor is a process effected by a machine executing instructions.
Claim 47
Dependent Claim
21 words
The device of claim 36 wherein the resource transition probabilities determining unit is a process effected by a machine executing instructions.
Claim 48
Dependent Claim
96 words
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.
Claim 49
Dependent Claim
19 words
The device of claim 43 wherein the first and second constant values are non-negative parameters of a prior distribution.
Claim 50
Dependent Claim
16 words
The device of claim 43 wherein the first and second constant values are prior belief estimates.
Claim 51
Dependent Claim
21 words
The device of claim 36 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.
Claim 52
Dependent Claim
112 words
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.
Claim 53
Dependent Claim
112 words
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.
Claim 54
Dependent Claim
20 words
The device of claim 47 wherein the preprocessor includes a filter for filtering data based on the identification of users.
Claim 55
Dependent Claim
22 words
The device of claim 47 wherein the preprocessor includes a filter for filtering data based on the identification of the resources referenced.
Claim 56
Dependent Claim
21 words
The device of claim 47 wherein the preprocessor includes a filter for filtering data based on the identification of the times.
Claim 57
Dependent Claim
17 words
The device of claim 47 wherein the preprocessor is a process effected by a machine executing instructions.
Claim 58
Dependent Claim
21 words
The device of claim 47 wherein the resource transition probabilities determining unit is a process effected by a machine executing instructions.
Claim 59
Dependent Claim
97 words
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.
Claim 60
Dependent Claim
19 words
The device of claim 53 wherein the first and second constant values are non-negative parameters of a prior distribution.
Claim 61
Dependent Claim
16 words
The device of claim 53 wherein the first and second constant values are prior belief estimates.
Claim 62
Dependent Claim
21 words
The device of claim 47 wherein referenced is an action selected from a group consisting of requested, retrieved, returned and rendered.
Claim 63
Dependent Claim
133 words
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.
Claim 64
Dependent Claim
133 words
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.
Claim 65
Dependent Claim
19 words
The system of claim 57 wherein the first and second constant values are non-negative parameters of a prior distribution.
Claim 66
Dependent Claim
16 words
The system of claim 57 wherein the first and second constant values are prior belief estimates.
Claim 67
Dependent Claim
21 words
The system of claim 57 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.
Claim 68
Dependent Claim
57 words
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.
Claim 69
Dependent Claim
57 words
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.
Claim 70
Dependent Claim
40 words
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.
Claim 71
Dependent Claim
36 words
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.
Claim 72
Dependent Claim
28 words
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.
Claim 73
Dependent Claim
95 words
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.
Claim 74
Independent Claim
93 words
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.
Claim 75
Independent Claim
93 words
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.
Claim 76
Dependent Claim
39 words
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.
Claim 77
Dependent Claim
22 words
The method of claim 67 wherein the sub-step of maximizing a likelihood function is performed in accordance with an expectation maximization algorithm.
Claim 78
Dependent Claim
32 words
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.
Claim 79
Dependent Claim
36 words
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.
Claim 80
Dependent Claim
21 words
The method of claim 66 wherein referenced is an action selected from a group consisting of requested, retrieved, returned, and rendered.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-03 | 2003-07-05 | 2004-01-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-03 | 2007-07-05 | 2008-01-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-03 | 2011-07-05 | 2012-01-04 | $7700.00 | Window Closed / Lapsed |