Abstract:

The k-nearest neighbor （kNN） query over moving objects is one of the important research topics in Location-Based Service （LBS）. Unlike kNN queries with a single query point， when a large number of query points issue query requests simultaneously， the same moving object may appear in the query results of multiple query points. This situation is called query result conflict， and multiple kNN queries involved in such conflicts are called conflict-aware kNN queries. In practical applications， the same moving object involved in query result conflicts cannot be assigned to multiple queries simultaneously. Instead， each query must retrieve k moving objects that differ from the results of other queries. Therefore， a globally optimized algorithm for conflict-aware kNN queries named RBCS-KNN （Road-Based Conflict Sensitive K Nearest Neighbor query algorithm） was proposed for road networks. Firstly， a two-layer index structure was built on the basis of the road network subgraphs after dividing. Secondly， by subgraph expansion and pruning strategies， the candidate conflicting query points were screened rapidly. Thirdly， kNN for the candidate query points were computed， and a sufficient number of candidate objects were expanded， while all conflicting query points were grouped dynamically. Finally， an optimal assignment solution was determined via an improved assignment strategy by which the sum of the distance from every query point to its k moving objects was minimized. Experimental results on multiple real-world datasets show that RBCS-KNN reduces the total query distance by 10% compared to the GLAD （Grid based LAbelling with scheDuling） algorithm， demonstrating its correctness and good performance.

Key words: k-Nearest Neighbor (kNN) query, moving object, Location-Based Service (LBS), road network, spatial-temporal data processing

摘要：

移动对象k近邻（kNN）查询是基于位置服务（LBS）的重要研究课题之一。不同于单查询点的kNN查询，当多个查询点同时发起查询请求时，可能出现同一个移动对象同时是多个查询点查询结果的情况。这种情况被称为查询结果冲突，查询结果冲突的多个kNN查询被称为冲突kNN查询。在实际应用中，无法将查询结果冲突的同一个移动对象同时分配给多个查询，而是需要为每个查询分别查找不同于其他查询结果的k个移动对象。因此，提出一种路网环境下的全局最优化的移动对象冲突kNN查询算法RBCS-KNN（Road-Based Conflict Sensitive K Nearest Neighbor query algorithm）。首先，在路网划分子图的基础上构建双层索引结构；其次，利用子图拓展和剪枝策略快速筛选出可能发生冲突的候选冲突查询点；再次，计算候选冲突查询点的kNN并拓展足量的候选对象，同时将所有冲突查询点动态分组；最后，利用改进的分配策略计算最优的分配方案，使所有查询点到它分配的k个移动对象的距离之和最小。在多个真实数据集上的实验结果表明，与GLAD（Grid based LAbelling with scheDuling）算法相比，RBCS-KNN的查询总距离减少了10%，验证了所提算法的正确性和良好的性能。

关键词: k近邻查询, 移动对象, 基于位置的服务, 道路网络, 时空数据处理