Show simple item record

Modeling strength of locality of reference via notions of positive dependence

dc.contributor.advisorMakowski, Armand M.en_US
dc.contributor.authorVanichpun, Saruten_US
dc.contributor.authorMakowski, Armand M.en_US
dc.description.abstractThe 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.en_US
dc.format.extent221633 bytes
dc.relation.ispartofseriesISR; TR 2005-77en_US
dc.relation.ispartofseriesCSHCN; TR 2005-1en_US
dc.subjectGlobal Communication Systemsen_US
dc.titleModeling strength of locality of reference via notions of positive dependenceen_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record