University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    Blue_umd_0117N_10703.pdf (318.3Kb)
    No. of downloads: 547

    Date
    2009
    Author
    Blue, Ryan
    Advisor
    Gasarch, William
    Metadata
    Show full item record
    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
    Collections
    • Computer Science Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility