OPTIMAL PREFETCHING VIA DATA-COMPRESSION

Caching and prefetching are important mechanisms for speeding up acces s time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms for caching . In this paper, we apply a form of the competitive philosophy for the first time to the problem of prefetching to develop an optimal univer sal prefetcher in terms of fault rate, with particular applications to large-scale databases and hypertext systems. Our prediction algorithm s for prefetching are novel in that they are based on data compression techniques that are both theoretically optimal and good in practice. Intuitively, in order to compress data effectively, you have to be abl e to predict future data well, and thus good data compressors should b e able to predict well for purposes of prefetching. We show for powerf ul models such as Markov sources and mth order Markov sources that the page fault rates incurred by our prefetching algorithms are optimal i n the limit for almost all sequences of page requests.