A Provably Efficient Computational Model For Approximate Spatiotemporal Retrieval

Vasilis Delis (Computer Technology Institute, Greece)

Christos Makris (Computer Engineering and Informatics Department, University of Patras and Computer Technology Institute, Greece)

Spyros Sioutas (Computer Engineering and Informatics Department, University of Patras and Computer Technology Institute, Greece)

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: range queries of high dimensionality, spatiotemporal data modeling, spatiotemporal data structures, spatiotemporal databases

Categories: H.1.0, H.3.1, H.3.3