You are here

Theory and Practice of Bloom Filters for Distributed Systems

TitleTheory and Practice of Bloom Filters for Distributed Systems
Publication TypeJournal Article
Year of Publication2012
AuthorsTarkoma, S, Rothenberg, CE, Lagerspetz, E
JournalCommunications Surveys Tutorials, IEEE
Volume14
Pagination131-155
Date PublishedFirst
ISSN1553-877X
KeywordsArrays, Bismuth, bloom filters, distributed systems, Filtering theory, filters, Fingerprint recognition, forwarding, information processing, measurement data summarization, networking costs, overlay networks, Peer to peer computing, peer-to-peer computing, Peer-to-peer systems, Probabilistic logic, probabilistic structures, probabilistic techniques, probability, routing, telecommunication network routing
Abstract

Many network solutions and overlay networks utilize probabilistic techniques to reduce information processing and networking costs. This survey article presents a number of frequently used and useful probabilistic techniques. Bloom filters and their variants are of prime importance, and they are heavily used in various distributed systems. This has been reflected in recent research and many new algorithms have been proposed for distributed systems that are either directly or indirectly based on Bloom filters. In this survey, we give an overview of the basic and advanced techniques, reviewing over 20 variants and discussing their application in distributed systems, in particular for caching, peer-to-peer systems, routing and forwarding, and measurement data summarization.

DOI10.1109/SURV.2011.031611.00024