Skip to content
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.

    Representing and Querying Uncertain Data

    Thumbnail
    View/Open
    Sen_umd_0117E_10712.pdf (901.5Kb)
    No. of downloads: 576

    Date
    2009
    Author
    Sen, Prithviraj
    Advisor
    Getoor, Lise C
    Deshpande, Amol V
    Metadata
    Show full item record
    Abstract
    There has been a longstanding interest in building systems that can handle uncertain data. Traditional database systems inherently assume exact data and harbor fundamental limitations when it comes to handling uncertain data. In this dissertation, we present a probabilistic database model that can compactly represent uncertainty models in full generality. Our representation is associated with precise and intuitive semantics and we show that the answer to every user-submitted query can be obtained by performing probabilistic inference. To query large-scale probabilistic databases, we propose a number of techniques that help scale probabilistic inference. Foremost among these techniques is a novel lifted inference algorithm that determines and exploits symmetries in the uncertainty model to speed up query evaluation. For cases when the uncertainty model stored in the database does not contain symmetries, we propose a number of techniques that perform approximate lifted inference. Our techniques for approximate lifted inference have the added advantage of allowing the user to control the degree of approximation through a handful of tunable parameters. Besides scaling probabilistic inference, we also develop techniques that alter the structure of inference required to evaluate a query. More specifically, we show that for a restricted model of our probabilistic database, if each result tuple can be represented by a boolean formula with special characteristics, i.e., it is a read-once function, then the complexity of inference can be drastically reduced. We conclude the dissertation with a listing of directions for future work.
    URI
    http://hdl.handle.net/1903/9812
    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