The Bit Probe Model for Membership Queries: Non-Adaptive Bit Queries
dc.contributor.advisor | Gasarch, William | en_US |
dc.contributor.author | Blue, Ryan | en_US |
dc.contributor.department | Computer Science | en_US |
dc.contributor.publisher | Digital Repository at the University of Maryland | en_US |
dc.contributor.publisher | University of Maryland (College Park, Md.) | en_US |
dc.date.accessioned | 2009-10-06T06:39:44Z | |
dc.date.available | 2009-10-06T06:39:44Z | |
dc.date.issued | 2009 | en_US |
dc.description.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. | en_US |
dc.format.extent | 325961 bytes | |
dc.format.mimetype | application/pdf | |
dc.identifier.uri | http://hdl.handle.net/1903/9649 | |
dc.language.iso | en_US | |
dc.subject.pqcontrolled | Computer Science | en_US |
dc.subject.pquncontrolled | bit probe data structure | en_US |
dc.subject.pquncontrolled | complexity theory | en_US |
dc.subject.pquncontrolled | space bounds | en_US |
dc.title | The Bit Probe Model for Membership Queries: Non-Adaptive Bit Queries | en_US |
dc.type | Thesis | en_US |
Files
Original bundle
1 - 1 of 1