Tuple Set Bloom Filter:
Bloom Filter Extensions for Tuple Sets or Database Tables
Muhammad Mukarram Bin Tariq (mtariq AT cc
DOT gatech.edu)
Farhan Saleem Khan (farhan AT cc DOT gatech.edu)
Spring 2006
We have developed a novel data-structure to compactly represent
database tables, and to be able to perform membership queries on these
tables. We call this new data-structure Tuple Set Bloom Filter, or
TSBF. TSBF is an extension of traditional Bloom Filter, which is
a probabilistic set membership query data-structure. Our
contribution is that we allow the set members to be a tuple, i.e.,
contain two or more ordered components. Each of these components
can be the value for an attribute. Our data structure allows the
users to perform a membership query on the set of tuples, using a fully
or partially specified tuple in the query. The TSBF returns a
Boolean, Yes or No response. A ‘No’ response means that no tuple
in the set matching the specified tuple exists. A ‘Yes’ response means
that a tuple matching the one specified in the query exists with high
probability, but there is a slight probability that it may not exist.