Virginia Tech
    • Log in
    View Item 
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Masters Theses
    • View Item
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Masters Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    A paging scheme for pointer-based quadtrees

    Thumbnail
    View/Open
    LD5655.V855_1992.B768.pdf (3.150Mb)
    Downloads: 416
    Date
    1992-05-19
    Author
    Brown, Patrick R.
    Metadata
    Show full item record
    Abstract
    The quadtree is a family of data structures that organize spatial data using recursive subdivision. A pointer-based quadtree uses an explicit tree structure to represent the subdivision, while a linear quadtree holds a sorted list of records corresponding to the leaves of the tree structure. Small quadtrees are typically represented using pointers since this leads to simpler algorithms. However, linear quadtrees have been historically used to represent larger data sets. The primary reason is that linear quadtrees are easily organized on pages in disk files. In addition, linear quadtrees were thought to require less space than pointerbased quadtrees. Though pointer-based quadtrees have many other advantages, there has still been much interest in the linear quadtree. This thesis presents a pointer-based representation for quadtrees called the paged-pointer quadtree. The paged-pointer quadtree overcomes both of the historical advantages of the linear quadtree. It partitions the nodes of a pointer-based quadtree into pages, stores these nodes in order, and manages pages using B-tree techniques. In addition, a paged-pointer quadtree always requires less space than a corresponding linear quadtree. Our representation overcomes the performance problems associated with representing traditional pointer-based quadtrees on disk. As a result, our implementation produces better performance than highly optimized systems based on linear quadtrees.
    URI
    http://hdl.handle.net/10919/45001
    Collections
    • Masters Theses [19643]

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us
     

     

    VTechWorks

    AboutPoliciesHelp

    Browse

    All of VTechWorksCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Log inRegister

    Statistics

    View Usage Statistics

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us