Predictive Event-Tracking Method

BACKGROUND: With the rapid increase of processor speeds, the bottleneck of input/output (I/O) and network system latency has become a critical issue in computer system performance. Standard least-recently-used (LRU)-based caching techniques offer some assistance, but by ignoring relationships that exist between system events, they fail to make full use of the information available. Event modeling techniques, such as those from the data compression field, have much success in supporting caching. However, memory requirements and computational complexity make such models difficult or impractical in real systems with a large number of possible events, such as modern file systems or the world wide web.

DESCRIPTION: Researchers have developed an efficient method for tracking sequences of events and predicting the probability of future events to improve caching disables such as prefetching replacement and writing. The result of such improved caching techniques is significantly higher cache hit ratios. Simulations have found that using this event model to augment an LRU cache with a predictive prefetching policy enabled a 4-megabyte cache to receive as many hits as a 90-megabyte LRU cache. The details of this study were published in the proceedings of the "Usenix 1996 Annual Technical Conference".

APPLICATIONS: The invention provides a predictive model that improves I/O efficiency in file caching, distributed system events such as http requests, and low-level I/O events, and offers a method for data compression as well.

ADVANTAGES: By exploiting the highly related nature of events, the predictive caching method of the invention reduces I/O system latency and improves overall system performance. This methodology provides a predictive cache with averaged hit ratios better than an LRU cache that is 20 times its size. Compared to current event-prediction techniques, the UC method:

* Works in fixed amount of space that is significantly smaller, resulting in lower memory requirements and faster execution;
* Adapts quickly to changes in predictive relationships;
* Maintains predictive models that can last indefinitely.

REFERENCE: 1996-285

Patents:
US 5,889,993   [MORE INFO]

Type of Offer: Licensing



« More Computer Science Patents

Share on      


CrowdSell Your Patent