US5889993A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Predictive event tracking method
Assignee: University of California
•
Filing: 1996-10-15
•
Granted: 1999-03-30
•
Expires: 2016-10-15
Abstract
Abstract A method of tracking events and their sequences in a computer system and predicting the probability of future events using a data structure that represents the predictive nature of the system after an initial event correlating to an object in the system. The invention reduces memory requirements and computational complexity by partitioning a trie into subtries where each subtrie represents a set of sequences of events, statically limiting the size of the partitions by limiting the number of descendants below the node defining the partition, and refreshing parts of the set of children and releasing slots occupied by particular descendants when additional space is needed. In addition, each partition can be attached to the object which it represents and moved in and out of memory with that object. In this way, data structures which would otherwise grow as large as NO and which have a computational complexity of predictions on the order of OxN, where N is the number of objects modeled and O is the model order, will be limited in size to N which, in turn, limits the computational complexity to order O.
Inventors
- 👤 Thomas M. Kroeger
- 👤 Darrell D. E. Long
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 21:58
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0862; G06F16/00; G06F16/10; G06F12/0866; G06F12/12; G06F12/121; G06F2212/00; G06F2212/60; G06F2212/6024; G06F2212/6026
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
179 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure having a plurality of substructures wherein each said substructure is associated with a distinct initial event and wherein each said substructure contains elements corresponding to events occurring after said associated initial event, wherein said data structure comprises a trie, wherein said substructures comprise subtries, and wherein said events are recorded as nodes in said trie; (c) limiting the number of elements in each said substructure; (d) designating a node as a current context when that node is recorded in the trie; (e) maintaining a count associated with each node in the trie; and (f) incrementing the count associated with a node and designating that node as a new current context if a new event is the same as a previous event represented by that node and that node is a child of a node that is a current context.
Claim 2
Dependent Claim
179 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure having a plurality of substructures wherein each said substructure is associated with a distinct initial event and wherein each said substructure contains elements corresponding to events occurring after said associated initial event, wherein said data structure comprises a trie, wherein said substructures comprise subtries, and wherein said events are recorded as nodes in said trie; (c) limiting the number of elements in each said substructure; (d) designating a node as a current context when that node is recorded in the trie; (e) maintaining a count associated with each node in the trie; and (f) incrementing the count associated with a node and designating that node as a new current context if a new event is the same as a previous event represented by that node and that node is a child of a node that is a current context.
Claim 3
Dependent Claim
22 words
A method as recited in claim 1, further comprising the step of periodically refreshing said substructures by releasing elements in said substructures.
Claim 4
Dependent Claim
33 words
A method as recited in claim 1, further comprising the steps of attaching each substructure to its corresponding object being manipulated and moving said substructure in and out of memory with the object.
Claim 5
Dependent Claim
74 words
A method as recited in claim 1, further comprising the steps of: (g) for each node that is designated as a new current context, (i) dividing the count associated with a child of said node by the count associated with said node less one to obtain a probability estimate, and (ii) storing the input/output object associated with the event represented by said child in a memory cache as a function of said probability estimate.
Claim 6
Dependent Claim
39 words
A method as recited in claim 1, further comprising the steps of adding a child to a current context and designating the child as a new current context if no child of said current context represents said new event.
Claim 7
Dependent Claim
201 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure representing the predictive nature of the system after an initial event associated with each object in the system; (c) organizing said elements in a plurality of substructures wherein each said substructure is associated with a distinct initial event and wherein each said substructure contains elements corresponding to events occurring after said associated initial event, wherein said data structure comprises a trie, wherein said substructures comprise subtries, and wherein said events are recorded as nodes in said trie; (d) limiting the number of elements in each said substructure; (e) desicinating a node as a current context when that node is recorded in the trie; (f) maintaining a count associated with each node in the trie; and (g) incrementing the count associated with a node and designating that node as a new current context if a new event is the same as a previous event represented by that node and that node is a child of a node that is a current context.
Claim 8
Dependent Claim
201 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure representing the predictive nature of the system after an initial event associated with each object in the system; (c) organizing said elements in a plurality of substructures wherein each said substructure is associated with a distinct initial event and wherein each said substructure contains elements corresponding to events occurring after said associated initial event, wherein said data structure comprises a trie, wherein said substructures comprise subtries, and wherein said events are recorded as nodes in said trie; (d) limiting the number of elements in each said substructure; (e) desicinating a node as a current context when that node is recorded in the trie; (f) maintaining a count associated with each node in the trie; and (g) incrementing the count associated with a node and designating that node as a new current context if a new event is the same as a previous event represented by that node and that node is a child of a node that is a current context.
Claim 9
Dependent Claim
22 words
A method as recited in claim 6, further comprising the step of periodically refreshing said substructures by releasing elements in said substructures.
Claim 10
Dependent Claim
33 words
A method as recited in claim 6, further comprising the steps of attaching each substructure to its corresponding object being manipulated and moving said substructure in and out of memory with the object.
Claim 11
Dependent Claim
74 words
A method as recited in claim 6, further comprising the steps of: (h) for each node that is designated as a new current context, (i) dividing the count associated with a child of said node by the count associated with said node less one to obtain a probability estimate, and (ii) storing the input/output object associated with the event represented by said child in a memory cache as a function of said probability estimate.
Claim 12
Dependent Claim
39 words
A method as recited in claim 6, further comprising the steps of adding a child to a current context and designating the child as a new current context if no child of said current context represents said new event.
Claim 13
Dependent Claim
197 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure, said data structure having a root, said data structure having a first order node that corresponds to an initial event, said data structure having a plurality of descendants corresponding to events occurring after said initial event, wherein said first order node extends from said root and said descendants extend from said first order node, wherein said data structure comprises a trie and wherein said events are recorded as nodes in said trie; (c) limiting the number of descendants of said first order node; (d) designating a node as a current context when that node is recorded in the trie; (e) maintaining a count associated with each node in the trie; and (f) incrementing the count associated with a node and designating that node as a new current context if a new event is the same as a previous event represented by that node and that node is a child of a node that is a current context.
Claim 14
Dependent Claim
197 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure, said data structure having a root, said data structure having a first order node that corresponds to an initial event, said data structure having a plurality of descendants corresponding to events occurring after said initial event, wherein said first order node extends from said root and said descendants extend from said first order node, wherein said data structure comprises a trie and wherein said events are recorded as nodes in said trie; (c) limiting the number of descendants of said first order node; (d) designating a node as a current context when that node is recorded in the trie; (e) maintaining a count associated with each node in the trie; and (f) incrementing the count associated with a node and designating that node as a new current context if a new event is the same as a previous event represented by that node and that node is a child of a node that is a current context.
Claim 15
Dependent Claim
24 words
A method as recited in claim 11, further comprising the step of periodically refreshing said data structure by replacing descendants in said data structure.
Claim 16
Dependent Claim
42 words
A method as recited in claim 11, further comprising the steps of attaching said first order node and its descendants to the corresponding object being manipulated and moving said first order node and descendants in and out of memory with the object.
Claim 17
Dependent Claim
74 words
A method as recited in claim 11, further comprising the steps of: (g) for each node that is designated as a new current context, (i) dividing the count associated with a child of said node by the count associated with said node less one to obtain a probability estimate, and (ii) storing the input/output object associated with the event represented by said child in a memory cache as a function of said probability estimate.
Claim 18
Dependent Claim
39 words
A method as recited in claim 11, further comprising the steps of adding a child to a current context and designating the child as a new current context if no child of said current context represents said new event.
Claim 19
Dependent Claim
255 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure having a plurality of substructures wherein each said substructure is associated with a distinct initial event and wherein each said substructure contains elements corresponding to events occurring after said associated initial event, wherein said data structure comprises a trie, wherein said substructures comprise subtries, and wherein said events are recorded as nodes in said trie; (c) limiting the number of elements in each said substructure; (d) designating a node as a current context when that node is recorded in the trie; (e) maintaining a count associated with each node in the trie; (f) for each new event, examining the children of a current context and determining if a child represents the event, and (i) if such a child exists, designating the child as a current context and incrementing its count; (ii) if such a child does not exist, adding a child to the current context and designating the child as a new current context; and (g) for each new current context, (i) dividing the count of a child associated with the new current context by the count of new current context less one to obtain a probability estimate, and (ii) storing the input/output objects associated with the sequence of events represented by said child in a memory cache as a function of said probability estimate.
Claim 20
Dependent Claim
255 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure having a plurality of substructures wherein each said substructure is associated with a distinct initial event and wherein each said substructure contains elements corresponding to events occurring after said associated initial event, wherein said data structure comprises a trie, wherein said substructures comprise subtries, and wherein said events are recorded as nodes in said trie; (c) limiting the number of elements in each said substructure; (d) designating a node as a current context when that node is recorded in the trie; (e) maintaining a count associated with each node in the trie; (f) for each new event, examining the children of a current context and determining if a child represents the event, and (i) if such a child exists, designating the child as a current context and incrementing its count; (ii) if such a child does not exist, adding a child to the current context and designating the child as a new current context; and (g) for each new current context, (i) dividing the count of a child associated with the new current context by the count of new current context less one to obtain a probability estimate, and (ii) storing the input/output objects associated with the sequence of events represented by said child in a memory cache as a function of said probability estimate.
Claim 21
Dependent Claim
278 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure representing the predictive nature of the system after an initial event associated with each object in the system; (c) organizing said elements in a plurality of substructures wherein each said substructure is associated with a distinct initial event and wherein each said substructure contains elements corresponding to events occurring after said associated initial event, wherein said data structure comprises a trie, wherein said substructures comprise subtries, and wherein said events are recorded as nodes in said trie; (d) limiting the number of elements in each said substructure; (e) designating a node as a current context when that node is recorded in the trie; (f) maintaining a count associated with each node in the trie; and (g) for each new event, examining the children of a current context and determining if a child represents the event, and (i) if such a child exists, designating the child as a current context and incrementing its count; (ii) if such a child does not exist, adding a child to the current context and designating the child as a new current context; and (h) for each new current context, (i) dividing the count of a child associated with the new current context by the count of new current context less one to obtain a probability estimate, and (ii) storing the input/output objects associated with the sequence of events represented by said child in a memory cache as a function of said probability estimate.
Claim 22
Dependent Claim
278 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure representing the predictive nature of the system after an initial event associated with each object in the system; (c) organizing said elements in a plurality of substructures wherein each said substructure is associated with a distinct initial event and wherein each said substructure contains elements corresponding to events occurring after said associated initial event, wherein said data structure comprises a trie, wherein said substructures comprise subtries, and wherein said events are recorded as nodes in said trie; (d) limiting the number of elements in each said substructure; (e) designating a node as a current context when that node is recorded in the trie; (f) maintaining a count associated with each node in the trie; and (g) for each new event, examining the children of a current context and determining if a child represents the event, and (i) if such a child exists, designating the child as a current context and incrementing its count; (ii) if such a child does not exist, adding a child to the current context and designating the child as a new current context; and (h) for each new current context, (i) dividing the count of a child associated with the new current context by the count of new current context less one to obtain a probability estimate, and (ii) storing the input/output objects associated with the sequence of events represented by said child in a memory cache as a function of said probability estimate.
Claim 23
Dependent Claim
274 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure, said data structure having a root, said data structure having a first order node that corresponds to an initial event, said data structure having a plurality of descendants corresponding to events occurring after said initial event, wherein said first order node extends from said root and said descendants extend from said first order node, wherein said data structure comprises a trie and wherein said events are recorded as nodes in said trie; (c) limiting the number of descendants of said first order node; (d) designating a node as a current context when that node is recorded in the trie; (e) maintaining a count associated with each node in the trie; and (f) for each new event, examining the children of a current context and determining if a child represents the event, and (i) if such a child exists, designating the child as a current context and incrementing its count; (ii) if such a child does not exist, adding a child to the current context and designating the child as a new current context; and (g) for each new current context, (i) dividing the count of a child associated with the new current context by the count of new current context less one to obtain a probability estimate, and (ii) storing the input/output objects associated with the sequence of events represented by said child in a memory cache as a function of said probability estimate.
Claim 24
Dependent Claim
274 words
A predictive event tracking method, comprising the steps of: (a) monitoring a plurality of events in a computer system, wherein each said event is associated with an object being manipulated; (b) recording said events as elements in a data structure, said data structure having a root, said data structure having a first order node that corresponds to an initial event, said data structure having a plurality of descendants corresponding to events occurring after said initial event, wherein said first order node extends from said root and said descendants extend from said first order node, wherein said data structure comprises a trie and wherein said events are recorded as nodes in said trie; (c) limiting the number of descendants of said first order node; (d) designating a node as a current context when that node is recorded in the trie; (e) maintaining a count associated with each node in the trie; and (f) for each new event, examining the children of a current context and determining if a child represents the event, and (i) if such a child exists, designating the child as a current context and incrementing its count; (ii) if such a child does not exist, adding a child to the current context and designating the child as a new current context; and (g) for each new current context, (i) dividing the count of a child associated with the new current context by the count of new current context less one to obtain a probability estimate, and (ii) storing the input/output objects associated with the sequence of events represented by said child in a memory cache as a function of said probability estimate.
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) | 2002-03-29 | 2002-09-28 | 2003-03-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-29 | 2006-09-28 | 2007-03-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-29 | 2010-09-28 | 2011-03-30 | $7700.00 | Window Closed / Lapsed |