The work reported here is based on the observation that lossless data compression methods implicitly or explicitly predict incoming source symbols and that similar predictions would be highly applicable to the problem of prefetching the data needed by a program. The authors selected a particular compression method due to Ziv and Lempel [1], LZ78, which is asymptotically optimal when the source data correspond to a kth-order Markov model. Consequently, the prefetching method based on LZ78 is also provably optimal when the stream of data references has an underlying kth-order Markov model.

The paper is mainly concerned with a theoretical analysis that develops the appropriate definitions of optimality and with proving that prefetching based on LZ78 is asymptotically optimal. Many practical issues are left unaddressed. Among these, the biggest questions are Can real programs be accurately modeled by kth-order Markov models for some reasonable value of k? and Can the prefetching strategy be implemented efficiently enough so as not to overshadow any gains achieved through prefetching?

The intended audience of the paper includes people interested in information theory and those who analyze the performance of operating systems. The work contains some novel and interesting ideas. It is a useful contribution to the literature.