US6128701A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive and predictive cache refresh policy
Assignee: CA Inc
•
Filing: 1997-10-28
•
Granted: 2000-10-03
•
Expires: 2017-10-28
Abstract
Abstract The invention provides a system and system for automatically refreshing documents in a cache, so that each particular document is refreshed no more often and no less often than needed. For each document, the cache estimates a probability distribution of times for client requests for that document and a probability distribution of times for server changes to that document. Times for refresh are selected for each particular document in response to both the estimated probability distribution of times for client requests and the estimated probability distribution of times for server changes. The invention also provides a system and system for objectively estimating the value the cache is providing for the system including the cache. The cache estimates for each document a probability distribution of times for client requests for that document, and determines a cumulative probability distribution which reflects the estimated marginal hit rate at the storage limit of the cache and the marginal advantage of adding storage to the cache.
Inventors
- 👤 Michael Malcolm
- 👤 Ian Telford
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 01:12
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/957; G06F16/9574
Claims Analysis
Total Claims: 68
Claim 1
Independent Claim
146 words
A method of operating a cache, including steps of: automatically refreshing a set of objects maintained in said cache in response to an estimate for each particular object in said set that said object is stale wherein aid step of automatically refreshing includes the steps of: for each said object, estimating a probability that said object will be next requested and will also be stale; automatically refreshing a first object in response to said probability that said object will be next requested and will also be stale; wherein said step of estimating includes the steps of: estimating a first probability distribution of client requests for said object; estimating a second probability distribution of server changes to said object; and estimating said probability that said object will be next requested and will also be stale in response to said first probability distribution and said second probability distribution.
Claim 2
Independent Claim
146 words
A method of operating a cache, including steps of: automatically refreshing a set of objects maintained in said cache in response to an estimate for each particular object in said set that said object is stale wherein aid step of automatically refreshing includes the steps of: for each said object, estimating a probability that said object will be next requested and will also be stale; automatically refreshing a first object in response to said probability that said object will be next requested and will also be stale; wherein said step of estimating includes the steps of: estimating a first probability distribution of client requests for said object; estimating a second probability distribution of server changes to said object; and estimating said probability that said object will be next requested and will also be stale in response to said first probability distribution and said second probability distribution.
Claim 3
Dependent Claim
28 words
A method as in claim 1, wherein said step of automatically refreshing is responsive to an estimate for said particular object that said object will be requested soon.
Claim 4
Dependent Claim
27 words
A method as in claim 1, wherein said first object has a largest said probability that said object will be next requested and will also be stale.
Claim 5
Dependent Claim
40 words
A method as in claim 1, wherein said step of estimating said probability that said object will be next requested and will also be stale is responsive to a product of said first probability distribution and said second probability distribution.
Claim 6
Dependent Claim
29 words
A method as in claim 1, wherein said step of estimating includes updating an estimated probability distribution for each object in response to a request history for said object.
Claim 7
Dependent Claim
45 words
A method as in claim 5, wherein said step of updating includes the steps of determining an initial estimated probability distribution of client requests for said object; and updating said estimated probability distribution of client requests for said object in response to said request history.
Claim 8
Dependent Claim
62 words
A method as in claim 5, wherein said step of updating includes the steps of determining an initial estimated probability distribution of client requests for said object; determining a new estimated probability distribution of client requests for said object in response to said request history; and determining a composite value of said initial estimated probability distribution and said new estimated probability distribution.
Claim 9
Dependent Claim
41 words
A method as in claim 1, wherein said step of estimating said probability that said object will be next requested and will also be stale includes updating said probability for each object in response to an update history or said object.
Claim 10
Dependent Claim
45 words
A method as in claim 8, wherein said step of updating includes the steps of determining an initial estimated probability distribution of server changes to said object; and updating said estimated probability distribution of server changes to said object in response to said update history.
Claim 11
Dependent Claim
36 words
A method as in claim 8, wherein said step of updating includes determining an initial estimated probability distribution of server changes to said object in espouse to information provided with said object by a server device.
Claim 12
Dependent Claim
62 words
A method as in claim 8, wherein said step of updating includes the steps of determining an initial estimated probability distribution of server changes to said object; determining a new estimated probability distribution of server changes to said object in response to said update history; and determining a composite value of said initial estimated probability distribution and said new estimated probability distribution.
Claim 13
Independent Claim
118 words
A method of operating a cache, including the steps of: determining, for each object in a set of objects maintained in said cache, a probability of client requests for said object and an expected load duration for said object; selecting particular object for removal in response to said probability of client requests for said object and said expected load duration for said object, wherein the step of determining includes steps of: determining an initial estimated probability distribution of client requests for said object; and updating said estimated probability distribution of client requests for said object in response to a request history whereby said probability for each object is updated in response to said request history for said object.
Claim 14
Independent Claim
118 words
A method of operating a cache, including the steps of: determining, for each object in a set of objects maintained in said cache, a probability of client requests for said object and an expected load duration for said object; selecting particular object for removal in response to said probability of client requests for said object and said expected load duration for said object, wherein the step of determining includes steps of: determining an initial estimated probability distribution of client requests for said object; and updating said estimated probability distribution of client requests for said object in response to a request history whereby said probability for each object is updated in response to said request history for said object.
Claim 15
Dependent Claim
32 words
A method as in claim 12, wherein said step of selecting is responsive to a product of load duration per unit size and said probability of client requests for each said object.
Claim 16
Independent Claim
137 words
A method of operating a cache, including the steps of: determining, for each object in a set of objects maintained in said cache a probability of client requests for said object and an expected load duration for said objects; and selecting a particular object for removal in response to said probability of client requests for said object and said expected load duration for said object; wherein the step of determining includes steps of: determining an initial estimated probability distribution of client requests for said object; determining a new estimated probability distribution of client requests for said object in response to a request history; and determining a composite value of said initial estimated probability distribution an said new estimated probability distribution whereby said probability for each object is updated in response to said request history for said object.
Claim 17
Independent Claim
137 words
A method of operating a cache, including the steps of: determining, for each object in a set of objects maintained in said cache a probability of client requests for said object and an expected load duration for said objects; and selecting a particular object for removal in response to said probability of client requests for said object and said expected load duration for said object; wherein the step of determining includes steps of: determining an initial estimated probability distribution of client requests for said object; determining a new estimated probability distribution of client requests for said object in response to a request history; and determining a composite value of said initial estimated probability distribution an said new estimated probability distribution whereby said probability for each object is updated in response to said request history for said object.
Claim 18
Dependent Claim
34 words
A method as in claim 12, wherein said step of determining said probability of client requests includes updating said expected load duration for each objects in response to said request history for said object.
Claim 19
Dependent Claim
39 words
A method as in claim 15, wherein said step of updating includes the steps of determining an initial expected load duration for said object; and updating said expected load duration for said object in response to said request history.
Claim 20
Dependent Claim
56 words
A method as in claim 15, wherein said step of updating includes the steps of estimating an initial expected load duration for said object; estimating a new expected load duration for said object in response to said request history; and determining a composite value of said initial expected load duration and said new expected load duration.
Claim 21
Dependent Claim
30 words
A method as in claim 15, wherein said step of updating includes the step of updating said expected load duration for a particular object when said particular object is reloaded.
Claim 22
Independent Claim
153 words
A system, including a cache; and means for automatically refreshing a set of objects maintained in said cache in response to an estimate for each particular object in said set that said object is stale; wherein said means for automatically refreshing includes: means for estimating for each said object, a probability that said object will be next requested and will also be stale; means for automatically refreshing a first object in response to said probability that said object will be next requested and will also be stale and wherein said means for estimating includes: memory storing an estimate of a first probability distribution of client requests for said object; memory storing estimate of a second probability distribution of server changes to said object; and means for estimating said probability that said object will be next requested and will also be stale in response to said first probability distribution and said second probability distribution.
Claim 23
Independent Claim
153 words
A system, including a cache; and means for automatically refreshing a set of objects maintained in said cache in response to an estimate for each particular object in said set that said object is stale; wherein said means for automatically refreshing includes: means for estimating for each said object, a probability that said object will be next requested and will also be stale; means for automatically refreshing a first object in response to said probability that said object will be next requested and will also be stale and wherein said means for estimating includes: memory storing an estimate of a first probability distribution of client requests for said object; memory storing estimate of a second probability distribution of server changes to said object; and means for estimating said probability that said object will be next requested and will also be stale in response to said first probability distribution and said second probability distribution.
Claim 24
Dependent Claim
28 words
A system as in claim 19, wherein said means for automatically refreshing is responsive to an estimate for said particular object that said object will be requested soon.
Claim 25
Dependent Claim
27 words
A system as in claim 19, wherein said first object has a largest said probability that said object will be next requested and will also be stale.
Claim 26
Dependent Claim
40 words
A system as in claim 19, wherein said means for estimating said probability that said object will be next requested and will also be stale is responsive to a product of said first probability distribution and said second probability distribution.
Claim 27
Dependent Claim
31 words
A system as in claim 19, wherein said means for estimating includes means for updating an estimated probability distribution for each object in response to a request history for said object.
Claim 28
Dependent Claim
45 words
A system as in claim 23, wherein said means for updating includes memory storing an initial estimated probability distribution of client requests for said object; and means for updating said estimated probability distribution of client requests for said object in response to said request history.
Claim 29
Dependent Claim
65 words
A system as in claim 23, wherein said means for updating includes means to determining an initial estimated probability distribution of client requests for said object; means for determining a new estimated probability distribution of client requests for sat object in response to said request history; and means for determining a composite value of said initial estimated probability distribution and said new estimated probability distribution.
Claim 30
Dependent Claim
43 words
A system as in claim 19, wherein said means for estimating said probability that said object will be next requested and will also be stale includes means for updating said probability for each object in response to an update history or said object.
Claim 31
Dependent Claim
46 words
A system as in claim 26, wherein said means for updating includes means for determining an initial estimated probability distribution of server changes to said object; and means for updating said estimated probability distribution of server changes to said object in response to said update history.
Claim 32
Dependent Claim
38 words
A system as in claim 26, wherein said means for updating includes means for estimating an initial estimated probability distribution of server changes to said object in response to information provided with said object by a server device.
Claim 33
Dependent Claim
65 words
A system as in claim 26, wherein said means for updating includes means for determining an initial estimated probability distribution of server changes to said object; means for determining a new estimated probability distribution of server changes to said object in response to said update history; and means for determining a composite value of said initial estimated probability distribution and said new estimated probability distribution.
Claim 34
Independent Claim
109 words
A system for operating a cache, including means for determining, for each object in a set of objects maintained in said cache, a probability of client requests for said object and an expected load duration for said object; means for updating said probability for each object in response to a request history for said object; and means for selecting a particular object for removal in response to said probability of client requests for said object and said expected load duration for said object, wherein said means for selecting is responsive to a product of load duration per unit size and said probability of client requests for each said object.
Claim 35
Independent Claim
109 words
A system for operating a cache, including means for determining, for each object in a set of objects maintained in said cache, a probability of client requests for said object and an expected load duration for said object; means for updating said probability for each object in response to a request history for said object; and means for selecting a particular object for removal in response to said probability of client requests for said object and said expected load duration for said object, wherein said means for selecting is responsive to a product of load duration per unit size and said probability of client requests for each said object.
Claim 36
Dependent Claim
46 words
A system as in claim 30, wherein said means for updating includes means for determining an initial estimated probability distribution of client requests for said object; and means for updating said estimated probability distribution of client requests for said object in response to said request history.
Claim 37
Dependent Claim
65 words
A system as in claim 30, wherein said means for updating includes means for determining an initial estimated probability distribution of client requests for said object; means for determining a new estimated probability distribution of client requests for said object in response to said request history; and means for determining a composite value of said initial estimated probability distribution and said new estimated probability distribution.
Claim 38
Dependent Claim
27 words
A system as in claim 30, further including means for updating said expected load duration for each object in response to said request history for said object.
Claim 39
Dependent Claim
44 words
A system as in claim 3, wherein said means for updating said expected load duration includes means for estimating an initial expected load duration for said object; and means for updating said expected load duration for said object in response to said request history.
Claim 40
Dependent Claim
62 words
A system as in claim 33, wherein said means for updating said expected load duration includes means to estimating an initial expected load duration for said object; means for estimating a new expected load duration for said object in response to request history; and means for determining a composite value of said initial expected load duration and aid new expected load duration.
Claim 41
Dependent Claim
32 words
A system as in claim 33, wherein said means for updating sad expected load duration includes means for updating said expected load duration for a particular object when said object is reloaded.
Claim 42
Independent Claim
170 words
A system, including a cache; a cache refresh mechanism configured to automatically refresh a set of objects maintained in said cache in response to an estimate for each particular object in said set that said object is stale; wherein said cache refresh mechanism includes: a first probability determination mechanism configured to estimate, for each said object a probability that said object will be next requested and will also be stale; a refresh mechanism configured to automatically refresh a first object in response to said probability that said object will be next requested and will also be stale; and wherein said first probability determination mechanism includes: memory storing an estimate of a first probability distribution of clients requests for said object; memory storing an estimate of a second probability distribution of server changes to said object; and a second probability determination mechanism configured to estimate said probability that said object will be next requested and will also be stale in response to said first probability distribution and said second probability distribution.
Claim 43
Independent Claim
170 words
A system, including a cache; a cache refresh mechanism configured to automatically refresh a set of objects maintained in said cache in response to an estimate for each particular object in said set that said object is stale; wherein said cache refresh mechanism includes: a first probability determination mechanism configured to estimate, for each said object a probability that said object will be next requested and will also be stale; a refresh mechanism configured to automatically refresh a first object in response to said probability that said object will be next requested and will also be stale; and wherein said first probability determination mechanism includes: memory storing an estimate of a first probability distribution of clients requests for said object; memory storing an estimate of a second probability distribution of server changes to said object; and a second probability determination mechanism configured to estimate said probability that said object will be next requested and will also be stale in response to said first probability distribution and said second probability distribution.
Claim 44
Dependent Claim
27 words
A system as in claim 37, wherein said cache refresh mechanism is responsive to an estimate for said particular object that said object will be requested soon.
Claim 45
Dependent Claim
27 words
A system as in claim 37, wherein said first object has a largest said probability that said object will be next requested and will also be stale.
Claim 46
Dependent Claim
27 words
A system as in claim 37, wherein said first probability determination mechanism is responsive to a product of said first probability distribution and said second probability distribution.
Claim 47
Dependent Claim
35 words
A system as in claim 37, wherein said first probability determination mechanism includes an update mechanism configured to update an estimated probability distribution for each object in response to a request history for said object.
Claim 48
Dependent Claim
48 words
A system as in claim 41, wherein said update mechanism includes memory storing an initial estimated probability distribution of client requests for said object; and a second update mechanism configured to update said estimated probability distribution of client requests for said object in response to said request history.
Claim 49
Dependent Claim
78 words
A system as in claim 41, wherein said update mechanism includes an initial probability determination mechanism configured to determine an initial estimated probability distribution of client requests for said object; a new probability determination mechanism configured to determine a new estimated probability distribution of client requests for said object in response to said request history; and a composite determination mechanism configured to determine a composite value of said initial estimated probability distribution and said new estimated probability distribution.
Claim 50
Dependent Claim
33 words
A system as in claim 37, wherein said first probability determination mechanism includes an update mechanism configured to update said probability for each object in response to an update history for said object.
Claim 51
Dependent Claim
55 words
A system as in claim 44, wherein said update mechanism includes an initial probability determination mechanism configured to determine an initial estimated probability distribution of server changes to said object; and a probability distribution update mechanism configured to update said estimated probability distribution of server changes to said object in response to said update history.
Claim 52
Dependent Claim
42 words
A system as in claim 44, wherein said update mechanism includes an initial probability distribution mechanism configured to determine an initial estimated probability distribution of server changes to said object in response to information provided with said object by a server device.
Claim 53
Dependent Claim
78 words
A system as in claim 44, wherein said update mechanism includes an initial probability determination mechanism configured to determine an initial estimated probability distribution of server changes to said object; a new probability determination mechanism configured to determine a new estimated probability distribution of server changes to said object in response to said update history; and a composite determination mechanism configured to determine a composite value of said initial estimated probability distribution and said new estimated probability distribution.
Claim 54
Independent Claim
140 words
A system for operating a cache, including a first probability determination mechanism configured to determine, for each object in a set of objects maintained in said cache, a probability of client requests for said object and an expected load duration for each said object; and a selection mechanism configured to select a particular object for removal in response to said probability of client requests for said object and said expected load duration for said object; wherein said first probability determination mechanism includes: a determination mechanism configured to determine an initial estimated probability distribution of client requests for said object; and a first update mechanism configured to update said estimated probability distribution of client requests for said object in response to a request history whereby said probability for each object is updates in response to said request history for said object.
Claim 55
Independent Claim
140 words
A system for operating a cache, including a first probability determination mechanism configured to determine, for each object in a set of objects maintained in said cache, a probability of client requests for said object and an expected load duration for each said object; and a selection mechanism configured to select a particular object for removal in response to said probability of client requests for said object and said expected load duration for said object; wherein said first probability determination mechanism includes: a determination mechanism configured to determine an initial estimated probability distribution of client requests for said object; and a first update mechanism configured to update said estimated probability distribution of client requests for said object in response to a request history whereby said probability for each object is updates in response to said request history for said object.
Claim 56
Dependent Claim
31 words
A system as in claim 48, wherein said selection mechanism is responsive to a product of load duration per unit size and said probability of client requests for each said object.
Claim 57
Independent Claim
165 words
A system for operating a cache including: a first probability determination mechanism configured to determine, for each object in a set of objects maintained in said cache, a probability of client requests for said object and an expected load duration for said object; and a selection mechanism configured to select a particular object for removal in response to said probability of client requests for said object and said expected load duration for said object; wherein said first probability determination mechanism includes: an initial probability determination mechanism configured to determine an initial estimated probability distribution of client requests for said object; a new probability determination mechanism configured to determine a new estimated probability distribution of client requests for said object in response to a request history; and a composite determination mechanism configured to determine a composite value of said initial estimated probability distribution and said new estimated probability distribution whereby said probability for each object is updated in response to said request history for said object.
Claim 58
Independent Claim
165 words
A system for operating a cache including: a first probability determination mechanism configured to determine, for each object in a set of objects maintained in said cache, a probability of client requests for said object and an expected load duration for said object; and a selection mechanism configured to select a particular object for removal in response to said probability of client requests for said object and said expected load duration for said object; wherein said first probability determination mechanism includes: an initial probability determination mechanism configured to determine an initial estimated probability distribution of client requests for said object; a new probability determination mechanism configured to determine a new estimated probability distribution of client requests for said object in response to a request history; and a composite determination mechanism configured to determine a composite value of said initial estimated probability distribution and said new estimated probability distribution whereby said probability for each object is updated in response to said request history for said object.
Claim 59
Dependent Claim
36 words
A system as in claim 48, wherein said first probability determination mechanism includes a second update mechanism configured to update said expected load duration for each object in response to said request history for said object.
Claim 60
Dependent Claim
50 words
A system as in claim 51, wherein said second update mechanism includes an initial duration determination mechanism configured to estimate an initial expected load duration for said object; and a probability distribution update mechanism configured to update said expected load duration for said object in response to said request history.
Claim 61
Dependent Claim
73 words
A system as in claim 51, wherein said second update mechanism includes an initial load determination mechanism configured to estimate an initial expected load duration for said object; a new load determination mechanism configured to determine a new expected load duration for said object in response to said request history; and a composite determination mechanism configured to determine a composite value of said initial expected load duration and said new expected load duration.
Claim 62
Dependent Claim
32 words
A system as in claim 51, wherein said second update, mechanism includes a load adjustment mechanism configured to update said expected load duration for a particular object when said object is reloaded.
Claim 63
Dependent Claim
169 words
A computer program product including: a computer storage medium having computer readable code embodied therein for causing a computer to automatically refresh cached objects, said computer readable code including: computer readable program code configured to cause said computer to effect a cache; and computer readable program code configured to cause said computer to effect a cache refresh mechanism configured to automatically refresh a set of objects maintained in said cache in response to an estimate for each particular object in said set that said object is stale; wherein said cache refresh mechanism includes: computer readable program code configured to cause said computer to effect a first probability determination mechanism configured to estimate, for each said object, a probability that said object will be next requested and will also be stale; and computer readable program code configured to cause said computer to effect a refresh mechanism configured to automatically refresh a first object in response to said probability that said object will be next requested and will also be stale.
Claim 64
Dependent Claim
169 words
A computer program product including: a computer storage medium having computer readable code embodied therein for causing a computer to automatically refresh cached objects, said computer readable code including: computer readable program code configured to cause said computer to effect a cache; and computer readable program code configured to cause said computer to effect a cache refresh mechanism configured to automatically refresh a set of objects maintained in said cache in response to an estimate for each particular object in said set that said object is stale; wherein said cache refresh mechanism includes: computer readable program code configured to cause said computer to effect a first probability determination mechanism configured to estimate, for each said object, a probability that said object will be next requested and will also be stale; and computer readable program code configured to cause said computer to effect a refresh mechanism configured to automatically refresh a first object in response to said probability that said object will be next requested and will also be stale.
Claim 65
Dependent Claim
29 words
A computer program product as in claim 55, wherein said cache refresh mechanism is responsive to an estimate for said particular object that said object will be requested soon.
Claim 66
Dependent Claim
48 words
A computer program product as in claim 55, wherein said first probability determination mechanism includes computer readable program code configured to cause said computer to effect an update mechanism configured to update an estimated probability distribution for each object in response to a request history for said object.
Claim 67
Dependent Claim
46 words
A computer program product as in claim 55, wherein said first probability determination mechanism includes computer readable program code configured to cause said computer to effect an update mechanism configured to update said probability for each object in response to an update history for said object.
Claim 68
Dependent Claim
113 words
A computer program product as in claim 58, wherein said update mechanism includes computer readable program code configured to cause said computer to effect an initial probability determination mechanism configured to determine an initial estimated probability distribution of server changes to said object; computer readable program code configured to cause said computer to effect a new probability determination mechanism configured to determine a new estimated probability distribution of server changes to said object in response to said update history; and computer readable program code configured to cause said computer to effect a composite determination mechanism configured to determine a composite value of said initial estimated probability distribution and said new estimated probability distribution.
References Cited (Backward Citations)
US5649154A
Cited
US5452447A
Cited
US5892937A
Cited
US5452440A
Cited
US5946682A
Cited
US5802292A
Cited
US5860106A
Cited
US5752022A
Cited
US5964830A
Cited
US5954795A
Cited
US5948062A
Cited
US5819045A
Cited
US5905999A
Cited
US5896506A
Cited
US5870769A
Cited
US5787470A
Cited
US5884046A
Cited
US5852717A
Cited
US5913033A
Cited
US5961602A
Cited
US5878218A
Cited
US5887151A
Cited
US5950205A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-03 | 2004-04-03 | 2004-10-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-03 | 2008-04-03 | 2008-10-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-03 | 2012-04-03 | 2012-10-03 | $7700.00 | Window Closed / Lapsed |