JUCS - Journal of Universal Computer Science 11(6): 830-849, doi: 10.3217/jucs-011-06-0830
A Provably Efficient Computational Model For Approximate Spatiotemporal Retrieval
expand article infoVasilis Delis‡, Christos Makris§, Spyros Sioutas§
‡ Computer Technology Institute, Patras, Greece§ Computer Engineering and Informatics Department, University of Patras and Computer Technology Institute, Patras, Greece

Corresponding author: Vasilis Delis ( delis@cti.gr )

© Vasilis Delis, Christos Makris, Spyros Sioutas.
This article is freely available under the J.UCS Open Content License.
Citation: Delis V, Makris C, Sioutas S (2005) A Provably Efficient Computational Model For Approximate Spatiotemporal Retrieval. JUCS - Journal of Universal Computer Science 11(6): 830-849. https://doi.org/10.3217/jucs-011-06-0830
Open Access
Abstract
The paper is concerned with the effective and efficient processing of spatiotemporal selection queries under varying degrees of approximation. Such queries may employ operators like overlaps, north, during, etc., and their result is a set of entities standing approximately in some spatiotemporal relation with respect to a query object X. The contribution of the present work is twofold: i) it presents a formal mathematical framework for representing multidimensional relations at varying granularity levels, modelling relation approximation through the concept of relation convexity, ii) it subsequently exploits the proposed framework for developing approximate spatiotemporal retrieval mechanisms, combining a set of existing as well as new main memory and secondary memory data structures that achieve either optimal or the best known performance in terms of time and space complexity, for both the static and the dynamic setting.
Keywords
spatiotemporal databases, spatiotemporal data modeling, spatiotemporal data structures, range queries of high dimensionality