1. Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity.
- Author
-
Huang, Yuan-Ko, Chen, Chao-Chun, and Lee, Chiang
- Subjects
- *
TEMPORAL databases , *NEAREST neighbor analysis (Statistics) , *QUERY languages (Computer science) , *SPEED , *ALGORITHM research - Abstract
One of the most important queries in spatio-temporal databases that aim at managing moving objects efficiently is the continuous K-nearest neighbor (C KNN) query. A C KNN query is to retrieve the K-nearest neighbors ( KNNs) of a moving user at each time instant within a user-given time interval [ t s , t e ]. In this paper, we investigate how to process a C KNN query efficiently. Different from the previous related works, our work relieves the past assumption, that an object moves with a fixed velocity, by allowing that the velocity of the object can vary within a known range. Due to the introduction of this uncertainty on the velocity of each object, processing a C KNN query becomes much more complicated. We will discuss the complications incurred by this uncertainty and propose a cost-effective P2 KNN algorithm to find the objects that could be the KNNs at each time instant within the given query time interval. Besides, a probability-based model is designed to quantify the possibility of each object being one of the KNNs. Comprehensive experiments demonstrate the efficiency and the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF