Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity
Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity
复制标题
DOI：
10.1007/s10707-007-0041-0
复制
发表时间：
2009-03-01
期刊：
影响因子：
2
通讯作者：
Lee, Chiang
中科院分区：
文献类型：
--
作者：
Huang, Yuan-Ko;Chen, Chao-Chun;Lee, Chiang
连续K近邻查询是时空数据库中有效管理移动对象的重要查询之一。CKNN查询是在用户给定的时间间隔[t（s），t（e）]内的每个时刻检索移动用户的K-最近邻（KNN）。在本文中，我们研究如何有效地处理CKNN查询。与以往的相关工作不同，我们的工作解除了过去的假设，即一个对象以固定的速度移动，通过允许对象的速度可以在一个已知的范围内变化。由于在每个对象的速度上引入了这种不确定性，处理CKNN查询变得更加复杂。我们将讨论这种不确定性所引起的并发症，并提出一种具有成本效益的P-2 KNN算法，以找到可能是KNN在给定的查询时间间隔内的每个时刻的对象。此外，一个基于概率的模型被设计来量化的可能性，每个对象是一个KNN。实验结果表明了该方法的有效性。
One of the most important queries in spatio-temporal databases that aim at managing moving objects efficiently is the continuous K-nearest neighbor (CKNN) query. A CKNN 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 CKNN 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 CKNN query becomes much more complicated. We will discuss the complications incurred by this uncertainty and propose a cost-effective P-2 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.