面向动态路网的移动对象分布式k近邻查询算法

Distributed k-nearest neighbor query algorithm for moving objects in dynamic road network

动态路网k近邻(kNN)查询是许多基于位置的服务(LBS)中的一个重要问题。针对该问题,提出一种面向动态路网的移动对象分布式kNN查询算法DkNN(Distributed kNN)。首先,将整个路网划分为部署于集群中不同节点中的多个子图;其次,通过并行地搜索查询范围所涉及的子图得到精确的kNN结果;最后,优化查询的搜索过程,引入查询范围剪枝策略和查询终止策略。在4个道路网络数据集上与3种基线算法进行了充分对比和验证。实验结果显示,与TEN~*-Index(Tree dEcomposition based kNN~*Index)算法相比,DkNN算法的查询时间减少了56.8%,路网更新时间降低了3个数量级。DkNN算法可以快速响应动态路网中的kNN查询请求,且在处理路网更新时具有较低的更新成本。

The k-Nearest Neighbor(kNN)query in dynamic road network is an important problem in many Location-Based Services(LBS).To address this problem,a distributed moving object kNN query algorithm named DkNN(Distributed k-Nearest Neighbor)was proposed for dynamic road networks.Firstly,the entire road network was divided into multiple subgraphs deployed in different nodes in the cluster.Then,the accurate kNN results were obtained by searching the subgraphs involved in the query range in parallel.Finally,the searching process of the query was optimized,and the query range pruning strategy as well as the query termination strategy was introduced.A full comparison and validation with three baseline algorithms on four road network datasets was performed.Experimental results show that the DkNN algorithm reduces the query time by 56.8%and the road network update time by 3 orders of magnitude compared to TEN*-Index(Tree dEcomposition based kNN*Index)algorithm.The DkNN algorithm can quickly respond to kNN query requests in dynamic road network and has a low update cost when dealing with road network updates.