Overlapping Linear Quadtrees and Spatio-Temporal Query Processing

Authors: Tzouramanis T.; Vassilakopoulos M.; Manolopoulos Y.

Source: Computer Journal, Volume 43, Number 4, 2000 , pp. 325-324(0)

Publisher: Oxford University Press

Abstract:

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.

Language: English

Document Type: Original article

Affiliations: 1: Laboratory of Data Engineering, Department of Informatics, Aristotle University, 54006 Thessaloniki, Greece Email: theo@delab.csd.auth.gr

Publication date: 2000-01-01

• The Computer Journal publishes research papers in a full range of subject areas, as well as regular feature articles and occasional themed issues to enable readers to easily access information outside their direct area of research. The journal provides a complete overview of developments in the field of Computer Science.

• In this: publication
• By this: publisher
• In this Subject: Computer Science
• By this author: Tzouramanis T. ;  Vassilakopoulos M. ;  Manolopoulos Y.

Website © Publishing Technology. Article copyright remains with the publisher, society or author(s) as specified within the article.

• Terms and conditions
• Privacy policy
• Information for advertisers