|
DRUM >
Theses and Dissertations from UM >
UM Theses and Dissertations >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1903/9649
|
| Title: | The Bit Probe Model for Membership Queries: Non-Adaptive Bit Queries |
| Authors: | Blue, Ryan |
| Advisors: | Gasarch, William |
| Department/Program: | Computer Science |
| Type: | Thesis |
| Sponsors: | Digital Repository at the University of Maryland
University of Maryland (College Park, Md.) |
| Keywords: | 0984
Computer Science
bit probe data structure, complexity theory, space bounds |
| Issue Date: | 2009 |
| 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. |
| URI: | http://hdl.handle.net/1903/9649 |
| Appears in Collections: | UM Theses and Dissertations
Computer Science Theses and Dissertations
|
All items in DRUM are protected by copyright, with all rights reserved.
|
