Home
Scholarly Works
Exploitation of Different Types of Locality for...
Conference

Exploitation of Different Types of Locality for Web Caches

Abstract

Object access distribution in the Web is governed by Zipf's law, in general. This property leads to effective Web caches, which store the most popular objects and typically employ the LFU replacement policy, which achieves high, and often the highest, cache hit rates. However, Web cache design based only on Zipf's law has two main disadvan-tages: (i) it does not exploit the temporal and spatial locality of user accesses on a per session basis, and (ii) LFU implementation is costly and impractical in many environments, because it requires statistics on all objects accessed since the beginning of a cache's operation. We consider all parameters of locality of references in the Web (temporal, spatial and popularity) and draw an analogy with processor caches. Given cache replacement policies that address different locality characteristics, we argue that there exist replacement algorithms that combine these characteristics and achieve high performance at a low cost. We describe Window-LFU (W-LFU), a policy that combines LFU and LRU and achieves better performance than LFU at lower cost. W-LFU exploits both Zipf's law, and temporal locality by using the accesses in a recent time-window. Simulations with actual traces indicate that W-LFU provides better results than theoretically expected.

Authors

Karakostas G; Serpanos DN

Pagination

pp. 207-212

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Publication Date

January 1, 2002

DOI

10.1109/iscc.2002.1021680

Name of conference

Proceedings ISCC 2002 Seventh International Symposium on Computers and Communications
View published work (Non-McMaster Users)

Contact the Experts team