Utilizing Approximate Counting in Distributed Caching and Content Delivery

12/19/2013
Speaker(s) : Roy Friedman (Technion, Israel)
Approximate counting schemes, also known as sketching, offer space efficient data structures for counting the number of occurrences of individual items in a very large multi-set of items. These schemes trade-off the accuracy of counting in order to gain significant storage space reductions. In this talk I will introduce this area and show how approximate counting can be used to boost distributed caching performance and P2P routing protocols. In particular, for caching, I will demonstrate a novel cache admission policy enabled by approximate counting. The scheme, called TinyLFU, brings the cache hit-rate close to its optimal value regardless of the eviction policy employed by the cache while consuming very little storage and computation overhead. In the content delivery example, I will show an improved Kademlia protocol called Shades, which also benefits from approximate counting ideas.
Bio: Roy Friedman is an associate professor in the department of Computer Science at the Technion. His research interests include Distributed Systems with emphasis on Mobile Computing, Middleware for Mobile Ad-Hoc Networks, Fault-Tolerance and High Availability, and Peer-to-Peer computing. He has published over 100 papers on these topics and he holds two patents. Formerly, Roy Friedman was an academic specialist at INRIA (France) and a researcher at Cornell University (USA). He is a founder of PolyServe Inc. (acquired by HP) and holds a Ph.D. and a B.Sc. from the Technion.