The Bit Probe Model for Membership Queries: Non-Adaptive Bit Queries
The Bit Probe Model for Membership Queries: Non-Adaptive Bit Queries
Files
Publication or External Link
Date
2009
Authors
Blue, Ryan
Advisor
Gasarch, William
Citation
DRUM DOI
Abstract
A common problem in computer science is how to efficiently store sets: when given a set, how do you store it so that you do not use much space and membership queries can be done quickly? One popular method is to use bit vectors. We use a model data structure that is a variant of bit vectors, the bit probe data structure, to demonstrate lower and upper bounds for bit vectors and similar structures. This thesis presents a survey of known results from literature, contributes some new proofs that have not appeared before, and gives complete proofs of known results that are missing from literature.