7 + OR - 2 Criteria for Assessing and Comparing Spatial Data Structures
Abstract
Starting from the very early days, five major types of applications generated most of the known data structures. But the requirements of these applications do not include one that is basic to spatial data: That objects are embedded in Euclidian space, and access is most often determined by location in space. Six specifically geometric requirements are presented that must be addressed by spatial data structures: The mostly static aspects of how space is organized is discussed with how objects are represented and how they are embedded inspace; The dynamic aspects of how objects are processed is considered. We differentiate three types of processing, of increasing complexity, that call for different solutions: common geometric transformations such as translation and rotation, proximity search, and is considered traversal of the object by different types of algorithms. Together with the general requirement of effective implementability, these seven criteria provide a profile for assessing spatial data structures. This survey leads us to two main conclusions: 1) That the current emphasis on comparative search trees is perhaps unduly influenced by the great success balanced trees enjoyed as a solution to the requirements of earlier applications that rely on single-key access, and 2) that spatial data structures are increasingly of the 'metric' type based on radix partitions of space. Keywords: Data management systems; Data bases; Data structures; Geometric and solid modeling; Geometric computation; Spatial data.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1989
- Accession Number
- ADA214789
Entities
People
- Jurg Nievergelt
Organizations
- University of North Carolina at Chapel Hill