Modeling strength of locality of reference via notions of positive dependence

Abstract

The performance of demand-driven caching depends on the locality of reference exhibited by the stream of requests made to the cache. In spite of numerous efforts, no consensus has been reached on how to formally {em compare} streams of requests on the basis of their locality of reference. We take on this issue by introducing the notion of Temporal Correlations (TC) ordering for comparing strength of temporal correlations in streams of requests. This notion is based on the supermodular ordering, a concept of positive dependence which has been successfully used for comparing dependence structures in sequences of rvs. We explore how the TC ordering captures the strength of temporal correlations in several Web request models, namely, the higher-order Markov chain model (HOMM), the partial Markov chain model (PMM) and the Least-Recently-Used stack model (LRUSM). We establish a folk theorem to the effect that the stronger the temporal correlations, the smaller the miss rate for the PMM. Conjectures and simulations are offered as to when this folk theorem should hold under the HOMM and under the LRUSM. Lastly, we investigate the validity this folk theorem for general input streams under the Working Set algorithm.