Skip to main content
USENIX
  • Conferences
  • Students
Sign in

connect with us


  •  Twitter
  •  Facebook
  •  LinkedIn
  •  Google+
  •  YouTube

twitter

Tweets by @usenix

usenix conference policies

  • Event Code of Conduct
  • Conference Network Policy
  • Statement on Environmental Responsibility Policy

You are here

Home ยป Using Full Reference History for Efficient Document Replacement in Web Caches
Tweet

connect with us

Using Full Reference History for Efficient Document Replacement in Web Caches

Abstract: 

With the increase in popularity of the World Wide Web, the research community has recently seen a proliferation of Web caching algorithms. This paper presents a new such algorithm, that is efficient and robust, called Least Unified-Value (LUV). LUV evaluates a Web document based on its cost normalized by the likelihood of it being re-referenced. This results in a normalized assessment of the contribution to the value of a document, leading to a fair replacement policy. LUV can conform to arbitrary cost functions of Web documents, so it can optimize any particular performance measure of interest, such as the hit rate, the byte hit rate, or the delay-savings ratio. Unlike most existing algorithms, LUV exploits complete reference history of documents, in terms of reference frequency and recency, to estimate the likelihood of being re-referenced. Nevertheless, LUV allows for an efficient implementation in both space and time complexities. The space needed to maintain the reference history of a document is only a few bytes and furthermore, the time complexity of the algorithm is O(log2n), where n is the number of documents in the cache. Trace-driven simulations show that the LUV algorithm outperforms existing algorithms for various performance measures for a wide range of cache configurations.

Hyokyung Bahn, Seoul National University

Sam H. Noh, Hong-Ik University

Kern Koh, Seoul National University

Sang Lyul Min, Seoul National University

BibTeX
@inproceedings {271499,
author = {Hyokyung Bahn and Sam H. Noh and Kern Koh and Sang Lyul Min},
title = {Using Full Reference History for Efficient Document Replacement in Web Caches},
booktitle = {Second USENIX Symposium on Internet Technologies \& Systems (USITS 99)},
year = {1999},
address = {Boulder, CO },
url = {https://www.usenix.org/conference/usits-99/using-full-reference-history-efficient-document-replacement-web-caches},
publisher = {USENIX Association},
month = oct,
}
Download

Links

Paper: 
http://usenix.org/publications/library/proceedings/usits99/full_papers/bahn/bahn.pdf
Paper (HTML): 
http://usenix.org/publications/library/proceedings/usits99/full_papers/bahn/bahn_html/
  • Log in or    Register to post comments

© USENIX

  • Privacy Policy
  • Contact Us