Skip navigation
Please use this identifier to cite or link to this item:
Authors: Suh, John
Advisors: Lloyd, Wyatt
Department: Computer Science
Certificate Program: None
Class Year: 2020
Abstract: Development of efficient caching systems is an important problem with the ubiquitous connectivity in the modern day. Most research in the field of web caching have approached the problem from improving the performance of the system through sophisticated eviction policies. However, there have been recent research that introduced the idea of admission policies that have shown to be effective in improving the performance of the underlying base eviction policies. We provide a new algorithm for applying Bloom filters on caching algorithms named insert-on-second-hit which showed miss ratio improvement for most algorithms on the traces tested, including 6% to 10% additional byte miss ratio improvement on LRU for theWikipedia trace compared to an existing algorithm. We find that sizing the Bloom filter can be optimized for the miss ratio; the optimal parameterization provides 1.3x to 5x traffic reduction compared to an infinite Bloom filter on LRU for a trace from Wikipedia’s CDN. We also find that Bloom filter’s effectiveness is not limited to LRU and byte miss ratio and extends to most classical and research algorithms across cache sizes. In addition to the analysis of Bloom filter, we introduce a simpler version of AdaptSize that simply leverages the percentile of sizes given a sliding window that showed comparable results for small cache sizes, showing 40% improvement over the base LRU caching algorithm.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Computer Science, 1988-2022

Files in This Item:
File SizeFormat 
SUH-JOHN-THESIS.pdf1.59 MBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.