A paging scheme for pointer-based quadtrees

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.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science and Applications

Department dc:contributor.department

Computer Science and Applications

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

1992

Author dc:creator

• Brown, Patrick R.

Chair dc:contributor.committeechair

• Shaffer, Clifford A.

Committee members dc:contributor.committeemember

• Abrams, Marc
• Heath, Lenwood S.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Dc Identifier Other

etd-10062009-020024

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/45001