Show simple item record

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

dc.contributor.authorVanichpun, Saruten_US
dc.contributor.authorMakowski, Armand M.en_US
dc.description.abstractWe 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>en_US
dc.format.extent242803 bytes
dc.relation.ispartofseriesISR; TR 2005-95en_US
dc.relation.ispartofseriesCSHCN; TR 2005-7en_US
dc.subjectGlobal Communication Systemsen_US
dc.titleModeling locality of reference via notions of positive dependence -- Some mixed news!en_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record