Blue, RyanA 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.en-USThesisComputer Sciencebit probe data structurecomplexity theoryspace bounds