There have been many studies on management of moving objects recently. Most of them try to optimize the performance of predictive window queries. However, not much attention is paid to two other important query types: the predictive range query and the predictive k nearest neighbor query. In this article, we focus on these two types of queries. The novelty of our work mainly lies in the introduction of the Transformed Minkowski Sum, which can be used to determine whether a moving bounding rectangle intersects a moving circular query region. This enables us to use the traditional tree traversal algorithms to perform range and kNN searches. We theoretically show that our algorithms based on the Transformed Minkowski Sum are optimal in terms of the number of tree node accesses. We also experimentally verify the effectiveness of our technique and show that our algorithms outperform alternative approaches.
Transformed Minkowski Sum, Spatio-temporal databases, Moving objects, Range query, Nearest neighbor query, kNN
Computer Sciences | Theory and Algorithms
Data Management and Analytics
ZHANG, Rui; JAGADISH, H.V.; Bing Tian DAI; and RAMAMOHANARAO, Kotagiri.
Optimized algorithms for predictive range and KNN queries on moving objects. (2010). Information Systems. 35, (8), 911-932. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3302
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.