Comparing strength of locality of reference - popularity, majorization, and some folk theorems

The performance of demand-driven caching depends on the locality of reference exhibited by the stream of requests made to the cache. In particular, it is expected that the stronger the locality of reference, the smaller the miss rate of the cache. For the independent reference model, this amounts to a smaller miss rate when the popularity distribution of requested objects in the stream is more skewed. We formalize this "folk theorem" through the companion concepts of majorization and Schur-concavity. This folk theorem is established for caches operating under a random on-demand replacement algorithm (RORA). However, the result fails to hold in general under the (popular) LRU and CLIMB policies, but can he established when the input has a Zipf-like popularity pmf with large skewness parameter. In addition, we explore how the majorization of popularity distributions translates into comparisons of three well-known locality of reference metrics, namely the inter-reference time, the working set size and the stack distance.