Predictive event tracking method

Details Predictive event tracking method Predictive event tracking method

1996-10-15

1999-03-30

Trammell, James P.

39518303, 39518315, G06F 1100

Patent

active

058899936

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 N.sup.O and which have a computational complexity of predictions on the order of O.times.N, 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.

REFERENCES:
patent: 4740349 (1988-04-01), Loftus et al.
patent: 5493504 (1996-02-01), Minato
patent: 5528701 (1996-06-01), Aref
patent: 5564119 (1996-10-01), Krawchuk et al.
patent: 5642478 (1997-06-01), Chen et al.
Kuenning et al., "An Analysis of Trace Data for Predictive File Caching in Mobile Computing", Proceedings of USENIX Summer Technical Conference, pp. 291-303, USENIX, 1994.
Kuenning et al., "The Design of the Seer Predictive Caching System", Workshop on Mobile Computing Systems and Applications, pp. 37-43, IEEE, Dec. 1994.
Cao et al., "Implementation of Performance of Integrated Application-Controlled Caching, Prefetching, and Disk Scheduling", Princeton University Technical Report TRCS95-493, 1995.
Baker et al., "Measurements of a Distributed File System", Proceedings of the 13th ACM Symposium on Operating Systems, Association for Computing Machinery SIGOPS, pp. 198-212, Oct. 13, 1991.
Vitter et al., "Optimal Prefetching via Data Compression", Brown University Technical Report CS-91-46, Jul. 1991.
Griffioen et al., "Performance Measurements of Automatic Prefetching", Parallel and Distributed Computing Systems, Orlando, FL 1995.
Krishnan et al., "Optimal Prediction for Prefetching in the Worst Case", Duke University Technical Report Duke-TR-1993-26, Jan. 1993.
Krishnan, P., "Online Prediction Algorithms for Databases and Operating Systems", Brown University, May 1995.
Curewitz et al., "Practical Prefetching Via Data Compression", Proceedings of 1993 ACM,pp. 257-266, May 1993.
Griffioen et al., "Improving File System Performance Via Predictive Caching", Parallel and Distributed Computing Systems '95, Sep. 21-23, 1995, pp. 165-170.
Griffioen et al., "Reducing File System Latency Using a Predictive Approach", Proceedings of USENIX Summer 1994 Technical Conference, pp. 197-207, Jun. 1994.

Affiliated with

Also associated with

Rating

Predictive event tracking method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Predictive event tracking method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Predictive event tracking method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1223627