时间依赖路网中反向k近邻查询  

Reverse k Nearest Neighbor Queries in Time-dependent Road Networks

作　　者：李佳佳 沈盼盼 夏秀峰 刘向宇 LI Jia-jia;SHEN Pan-pan;XIA Xiu-feng;LIU Xiang-yu(School of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学计算机学院,沈阳110136

出　　处：《计算机科学》2019年第1期232-237,共6页Computer Science

基　　金：国家自然科学基金(61502317);辽宁省自然科学基金(201602559;201602568)资助

摘　　要：在现存的反向k近邻查询方案中,比较高效的研究大多集中在欧氏空间或者静态路网,对时间依赖路网中的反向k近邻查询的研究相对较少。已有算法在兴趣点密度稀疏或者k值较大时,查询效率较低。对此,提出了基于子网划分的反向k近邻查询算法mTD-SubG。首先,将整个路网划分为大小相同的子网,通过子网的边界节点向其他子网进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后,利用已有时间依赖路网下的近邻查询算法,判定查找到的兴趣点是否为反向k近邻结果。实验中将mTD-SubG算法与已有算法mTD-Eager进行对比,结果表明mTD-SubG算法的响应时间比mTD-Eager算法减少了85.05%,遍历节点个数比mTD-Eager算法减少了51.40%。Most existing efficient algorithms for reverse k nearest neighbor query focus on the Euclidean space or static networks,and few of them study the reverse k nearest neighbor query in time-dependent networks.However,the existing algorithm is inefficient if the density of interest points is sparse or the value of k is large.To address these problems,this paper proposed a sub net division based reverse k nearest neighbor query algorithm mTD-SubG.Firstly,the entire road network is divided into subnets with the same size,and they are expanded to other subnets through the border nodes to speed up the search process for interest points.Secondly,the pruning technology is utilized to narrow the expansion range of road network.Finally,the existing nearest neighbor query algorithm of time-dependent road networks is used for each searched interest points to determine whether it belongs to the reverse k nearest neighbor results.Extensive experiments were conducted to compare the proposed algorithm mTD-SubG with the existing algorithm mTD-Eager.The results show that the response time of mTD-SubG is 85.05%less than that of mTD-Eager,and mTD-SubG reduces the number of traversed nodes by 51.40%compared with mTD-Eager.

关 键 词：时间依赖 路网 反向k近邻(RkNN) mTD-SubG算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]