Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Data Structures for Dynamic Queries: An Analytical and Experimental Evaluation

    Thumbnail
    View/Open
    TR_93-73.pdf (1.168Mb)
    No. of downloads: 452

    Date
    1993
    Author
    Jian, Vinit
    Shneiderman, Ben
    Metadata
    Show full item record
    Abstract
    Dynamic Queries is a querying technique for doing range search on multi-keydata sets. It is a direct manipulation mechanism where the query is formulatedusing graphical widgets and the results are displayed graphically in real time.<P>This paper evaluates four data structures, the multilist, the gridfile, k-d tree and the quad tree used to organize data in high speed storage for dynamic queries. The effect of factors like size, distribution and dimensionality of data on the storage overhead and the speed of search is explored. A way of estimating the storage and the search overheads using analytical models is presented. These models are verified to be correct by empirical data.<P>Results indicate that multilists are suitable for small (few thousandpoints) data sets irrespective of the data distribution. For large data sets the grid files are excellent for uniformly distributed data, and trees are good for skewed data distributions. These was no significant difference in performance between the tree structures.
    URI
    http://hdl.handle.net/1903/5417
    Collections
    • Institute for Systems Research Technical Reports

    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