Modeling locality of reference via notions of positive dependence -- Some mixed news!

Abstract

We introduce the notion of Temporal Correlations (TC) ordering as a way to compare strength of temporal correlations in streams of requests. This notion is based on the supermodular ordering, a concept of positive dependence used for comparing dependence structures in sequences of rvs. We explore how the TC ordering captures the strength of temporal c 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 also show how the comparison in the TC ordering is compatible with comparisons of some well-known locality of reference metrics, namely, the working set size and the inter-reference time. 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 regarding this folk theorem under the HOMM and under the LRUSM. The validity of this folk theorem is also discussed for general input streams under the Working Set algorithm. <p>