Harvard Theory of Computation Seminar
Beyond Bloom Filters: Approximate Representations of
Concurrent
State Machines (and a New Construction for Counting Bloom Filters)
Michael Mitzenmacher, Harvard University
Place and Time: Monday 5/8, Maxwell-Dworkin 319
Refreshments at 2:30, talk at 2:45.
ABSTRACT
Many networking applications require fast state lookups in a
concurrent
state machine, which tracks the state of a large number of flows
simultaneously. We consider the question of how to compactly represent
such
concurrent state machines. To achieve compactness, we consider data
structures for Approximate Concurrent State Machines
(ACSMs) that can return false positives, false negatives, or a ``don't
know'' response, a generalization of the standard notion of Bloom
Filters.
We describe three techniques based on Bloom filters and hashing, and
evaluate them using both theoretical analysis and simulation. Our
analysis
leads us to an extremely efficient hashing-based scheme with several
parameters that can be chosen to trade off space, computation, and the
impact of errors. Our hashing scheme can also be used to provide an
alternative structure with the same functionality and nearly the same
complexity as a counting Bloom filter but that uses much less space.
For
example, for a 1\% false positive rate, our structure uses roughly
half the
space of a counting Bloom filter. We explain how ACSMs can be used
for
applications such as video congestion control and real-time detection
of P2P
traffic.
Joint work with
Flavio Bonomi, Rina Panigrahy, Sushil Singh, George Varghe