Optimized algorithms for predictive range and KNN queries on moving objects

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 ar...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHANG, Rui, JAGADISH, H.V., Bing Tian DAI, RAMAMOHANARAO, Kotagiri
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2010
Subjects:
kNN
Online Access:https://ink.library.smu.edu.sg/sis_research/3302
https://ink.library.smu.edu.sg/context/sis_research/article/4304/viewcontent/OptimizedAlgorPredicRangeKNN_2010_InfoSys_pp.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary: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.