A paging scheme for pointer-based quadtrees
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.
Collections
- Masters Theses [19643]