Utilizing Approximate Counting in Distributed Caching and Content Delivery
Jeudi 19 décembre 2013Roy 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.
maria.potop-butucaru (at) nulllip6.fr