基于Voronoi图的路网k聚集最近邻居节点查询方法  

Voronoi-Based k-Aggregate Nearest Neighbor Query Processing in Road Networks

作　　者：朱良[1] 孙未未[1] 荆一楠[1] 杜江帆[1] 

机构地区：[1]复旦大学计算机科学与技术学院,上海201203

出　　处：《计算机研究与发展》2011年第S3期155-162,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61073001)

摘　　要：道路网络中的k最近邻居节点(k-NN)查询及其变种越来越受到研究者们的关注.其中,k聚集最近邻居节点(k-ANN)查询能为多个查询点返回聚集距离最小的前k个被查对象,因此具有较高的研究价值及广阔的应用前景.目前解决该查询问题的主要方法是根据A*算法在路网上通过逐步扩展来搜寻结果,这样会导致响应时间很长,不能满足用户的需求.利用基于Voronoi图的路网可以提供解决这种查询的一种新方法.该方法利用Voronoi图预计算的优势,极大提高了用户的查询效率.实验结果表明提出的方法很大程度上减少了用户的响应时间和页面访问量.道路网络中的k最近邻居节点(k-NN)查询及其变种越来越受到研究者们的关注.其中,k聚集最近邻居节点(k-ANN)查询能为多个查询点返回聚集距离最小的前k个被查对象,因此具有较高的研究价值及广阔的应用前景.目前解决该查询问题的主要方法是根据A*算法在路网上通过逐步扩展来搜寻结果,这样会导致响应时间很长,不能满足用户的需求.利用基于Voronoi图的路网可以提供解决这种查询的一种新方法.该方法利用Voronoi图预计算的优势,极大提高了用户的查询效率.实验结果表明提出的方法很大程度上减少了用户的响应时间和页面访问量.

关 键 词：道路网络 VORONOI图 k聚集最近邻居节点查询 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]