计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2011年
z2期
533-540
,共8页
朱良%孙未未%荆一楠%杜江帆
硃良%孫未未%荊一楠%杜江帆
주량%손미미%형일남%두강범
道路网络%Voronoi图%k聚集最近邻居节点查询
道路網絡%Voronoi圖%k聚集最近鄰居節點查詢
도로망락%Voronoi도%k취집최근린거절점사순
道路网络中的k最近邻居节点(k-NN)查询及其变种越来越受到研究者们的关注.其中,k聚集最近邻居节点(k-ANN)查询能为多个查询点返回聚集距离最小的前k个被查对象,因此具有较高的研究价值及广阔的应用前景.目前解决该查询问题的主要方法是根据A*算法在路网上通过逐步扩展来搜寻结果,这样会导致响应时间很长,不能满足用户的需求.利用基于Voronoi图的路网可以提供解决这种查询的一种新方法.该方法利用Voronoi图预计算的优势,极大提高了用户的查询效率.实验结果表明提出的方法很大程度上减少了用户的响应时间和页面访问量.
道路網絡中的k最近鄰居節點(k-NN)查詢及其變種越來越受到研究者們的關註.其中,k聚集最近鄰居節點(k-ANN)查詢能為多箇查詢點返迴聚集距離最小的前k箇被查對象,因此具有較高的研究價值及廣闊的應用前景.目前解決該查詢問題的主要方法是根據A*算法在路網上通過逐步擴展來搜尋結果,這樣會導緻響應時間很長,不能滿足用戶的需求.利用基于Voronoi圖的路網可以提供解決這種查詢的一種新方法.該方法利用Voronoi圖預計算的優勢,極大提高瞭用戶的查詢效率.實驗結果錶明提齣的方法很大程度上減少瞭用戶的響應時間和頁麵訪問量.
도로망락중적k최근린거절점(k-NN)사순급기변충월래월수도연구자문적관주.기중,k취집최근린거절점(k-ANN)사순능위다개사순점반회취집거리최소적전k개피사대상,인차구유교고적연구개치급엄활적응용전경.목전해결해사순문제적주요방법시근거A*산법재로망상통과축보확전래수심결과,저양회도치향응시간흔장,불능만족용호적수구.이용기우Voronoi도적로망가이제공해결저충사순적일충신방법.해방법이용Voronoi도예계산적우세,겁대제고료용호적사순효솔.실험결과표명제출적방법흔대정도상감소료용호적향응시간화혈면방문량.