Technical Report PHD-2015-02

Title: Approximate Compact Data Structures and Applications
Authors: Gil Einziger
Supervisors: Roy Friedman
Abstract: This thesis introduces two novel data structures: TinySet is optimized for the approximate set problem and TinyTable deals with the approximate counting problem. We show that both suggestions require less space than a variety of previous approaches. We also show that their operation speed can be faster than that of Bloom filters, especially for query operations.

We then present two novel cache management techniques:TinyLFU and Shades. In TinyLFU, approximate counting is used in order to estimate the recent frequency of encountered items. That estimation is then used to implement an approximate LFU admission policy. It is shown that TinyLFU signi cantly improves the hitrates of caches under a variety of real life workloads.

Shades utilizes a novel routing and caching approach in order to shorten both the average and median searches in Kademlia. Shades routing technique enables many TinyLFU augmented caches to work together in order to achieve high hit rates. We show that Shades indeed shortens both the average and median lookup, without additional message and bandwidth overheads.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2015
To the main CS technical reports page

Computer science department, Technion