An efficient use of quadtrees in a geographical information system

Publisher Website
Google Scholar
Abstract
With the increase in volume of spatial data now available, more effective ways must be found of storing and processing these data. This paper presents a compacted version of the linear quadtree and a spatially-referenced index method that can significantly reduce the storage requirements of a set of images and the time taken to process spatial queries. The index acts as a high-level summary of a regular-sized portion of the underlying image and so can be used to avoid examining areas of the image where none of the required features is present. Some example results are given. A method for the optimization of spatial searches is presented which takes into account the area and distribution of features within an image. Finally, a method for directly associating the edges of features with the individual nodes of a quadtree is reported. This is important since the edges of objects are no longer explicitly present in linear quadtrees and so must be recalculated when they are required for part of a query. Recalculation of object edges or boundaries is expensive; it is best, therefore, to perform the operation once only, and then save the results.

This publication has 9 references indexed in Scilit: