A comparison of non-point spatial data indexing methodologies
Loading...
Files
Date
1990
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The general objective of this research is to compare the performance of several spatial indexing methods. In order to do so, we built spatial indices for two-dimensional nonzero size objects and performed range searches on those objects. There are two ways to create an index: 1) use the spatial data support in commercially available databases such as Oracle 8i and O2, and 2) create the spatial data-indexing scheme directly using spatial data structures such as the R-tree or Grid file. A new data structure based on the binaryradix bucket-region (BR2) grid file was created for non-point objects.
Two sets of data from the National Topological Database were used to perform the experimental comparisons. We performed two different types of range search: search based on the bounding box of the objects only (primary) and search based on the real data (secondary). Testing was performed with query window areas= 1%, 4%, 9%, 16%, 25%, 36%, 49%, 64%, 81%, and I 00% of the data extent.
For secondary range search, the R-tree and the modified grid file took the least amount of time (0.497 seconds and 0.628 seconds respectively) on average to report (out of a test set of 20,000 objects) the objects in range for a query window area= 49% of the original data extent. The Oracle 8i Spatial object-relational, and the Oracle 8i Spatial relational methods required, on average, 220, and 400 times more time for the same search, respectively. Significant difficulties were encountered in getting the commercially available databases to perform range searches on the test data.