Item Details

Print View

Q0-Trees: A Dynamic Structure for Accessing Spatial Objects With Arbitrary Shapes

Orlandic, Ratko; Pfaltz, John
Format
Report
Author
Orlandic, Ratko
Pfaltz, John
Abstract
The items in a spatial database have location, extent, and shape with respect to a spatial coordinate system. Simple approximations to these attributes, say by bounding rectangles, are storage efficient and easy to manipulate. But effective spatial retrieval (on either location, extent, or shape) require a more precise representation of these attributes. In this report, we describe a highly compressed quadtree representation, called a Q0 - tree, which supports spatial queries without false drops or unnecessary storage accesses. This access structure is dynamic. Moreover, because it is an exact representation of the spatial configuration, the spatial operators union, intersection, and difference can be coded with respect to the Q0 - tree itself without needing a separate representation of the configuration, and, in worst case, exhibit linear performance. We discuss quadtrees, octtrees, grid files, R - trees, cell trees, and zkd B - trees; and provide a more detailed qualitative comparison between the latter two and Q0 - trees, contrasting both storage and processing overhead. Note: Abstract extracted from PDF file via OCR
Language
English
Date Received
2012-10-30
Published
University of Virginia, Institute for Parallel Computation, 1991
Published Date
1991
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online