© 2000 by British Computer Society
Overlapping Linear Quadtrees and Spatio-Temporal Query Processing
1 Laboratory of Data Engineering, Department of Informatics, Aristotle University, 54006 Thessaloniki, Greece Email: theo@delab.csd.auth.gr 2 Parts of this work have been presented at the 6th ACM Symposium on Advances in Geographic Information Systems (ACM-GIS'98) and at the 3rd East-European Conference on Advanced Databases and Information Systems (ADBIS'99).
In this paper, indexing in spatio-temporal databases by using the technique of overlapping is investigated. Overlapping has been previously applied in various access methods to combine consecutive structure instances into a single structure, without storing identical sub-structures. In this way, space is saved without sacrificing time performance. A new access method, overlapping linear quadtrees is introduced. This structure is able to store consecutive historical raster images, a database of evolving images. Moreover, it can be used to support query processing in such a database. Five such spatio-temporal queries along with the respective algorithms that take advantage of the properties of the new structure are introduced. The new access method was implemented and extensive experimental studies for space efficiency and query processing performance were conducted. A number of results of these experiments are presented. As far as space is concerned, these results indicate that, in the case of similar consecutive images, considerable storage is saved in comparison to independent linear quadtrees. In the case of query processing, the results indicate that the proposed algorithmic approaches outperform the respective straightforward algorithms, in most cases. The region data sets used in experiments were real images of meteorological satellite views and synthetic random images with specified aggregation.
Received 25 February, 2000. Revised 21 August, 2000.