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

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

作　　者：陈国祥 于自强 赵浩宇 CHEN Guoxiang;YU Ziqiang;ZHAO Haoyu(School of Computer and Control Engineering,Yantai University,Yantai Shandong 264005,China)

机构地区：[1]烟台大学计算机与控制工程学院,山东烟台264005

出　　处：《计算机应用》2024年第11期3403-3410,共8页journal of Computer Applications

基　　金：国家自然科学基金资助项目(62172351)。

摘　　要：动态路网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.

关 键 词：动态道路网络 K近邻查询 分布式环境 基于位置的服务 时空数据处理 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]