## May 21, Spring Quarter 2010: Theory Seminar

### 1:00pm in ICS 243

#
Straggler Identification in Round-Trip Data Streams via Invertible
Bloom Filters

##
Arjun Biswas

Presenting a result
from a WADS 2007 paper by Eppstein and Goodrich

Abstract:
We introduce the straggler identification problem, in which an
algorithm must determine the identities of the remaining members of a
set after it has had a large number of insertion and deletion
operations performed on it, and now has relatively few remaining
members. The goal is to do this in o(n) space, where n is the total
number of identities. The straggler identification problem has
applications, for example, in determining the set of unacknowledged
packets in a high-bandwidth multicast data stream. We show that there
is a simple randomized solution using O(d log n log(1/epsilon)) bits
that can maintain a multiset and solve the straggler identification
problem, tolerating false deletions, where epsilon>0 is a
user-defined parameter bounding the probability of an incorrect
response. This randomized solution is based on a new type of Bloom
filter, which we call the invertible Bloom filter.