The use of compression modeling techniques to track access patterns and prefetch data was first examined by Vitter, Krishnan and Curewitz [25]. They proved that for a Markov source such techniques converge to an optimal on-line algorithm, and then tested this work for memory access patterns in an object-oriented database and a CAD System. Chen et al. [8] examine the use of FMOCM type models for use in branch prediction. Griffioen and Appleton [6] were the first to propose a graph-based model that has seen use across several other applications [23,21]. Lei and Duchamp [18] have pursued modifying a UNIX file system to monitor a process' use of fork and exec to build a tree that represents the processes execution and access patterns. Kuenning et al. [17] have developed the concept of a semantic distance and used this to drive an automated hoarding system to keep files on the local disks of mobile computers. Madhyastha et al. [19] used hidden Markov models and neural networks to classify I/O access patterns within a file.
Several researchers are exploring methods for cache resource management given application-provided hints. Patterson et al. [24] present an informed prefetching model that applies cost-benefit analysis to allocate resources. Cao et al. [4] examine caching and prefetching in combination and present four rules for successfully combining the two techniques and evaluate several prefetching algorithms including an aggressive prefetch algorithm. Kimbrel et al. [10] present an algorithm that has the advantages of both informed prefetching and aggressive prefetch while avoiding their limitations.