Browsing by Author "Blue, Ryan"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item The Bit Probe Model for Membership Queries: Non-Adaptive Bit Queries(2009) Blue, Ryan; Gasarch, William; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)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.