The Bit Probe Model for Membership Queries: Non-Adaptive Bit Queries

dc.contributor.advisorGasarch, Williamen_US
dc.contributor.authorBlue, Ryanen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2009-10-06T06:39:44Z
dc.date.available2009-10-06T06:39:44Z
dc.date.issued2009en_US
dc.description.abstractA 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.extent325961 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/9649
dc.language.isoen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledbit probe data structureen_US
dc.subject.pquncontrolledcomplexity theoryen_US
dc.subject.pquncontrolledspace boundsen_US
dc.titleThe Bit Probe Model for Membership Queries: Non-Adaptive Bit Queriesen_US
dc.typeThesisen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Blue_umd_0117N_10703.pdf
Size:
318.32 KB
Format:
Adobe Portable Document Format