路网中基于预计算的跳跃式查询最近邻的算法

Pre-computing-based algorithm for nearest neighbors leaping query over road network

在空间网络数据库(SNDB)中,最近邻查询(NN)在基于位置的服务(LBS)中尤为关键.现有的查询处理方法大多依赖于路网的稀疏程度,其他处理方法如UNICONS等改进了该不足,但可能存在过计算的问题.针对后者,本文提出并证明了基于非交叉点路径中的预计算理论,同时基于该理论提出一种通用的基于SNDB的NN查询处理方法,该方法通过跳跃式查询交叉点的最近邻来降低预计算的代价.通过实验,验证了本文提出的处理方法在最近邻查询中的正确性和有效性,特别是在交叉点分布稀疏的路径上,性能优势尤为明显.

In Spatial Network Database（ SNDB）, Nearest Neighbor（NN） query is frequently used in Location-Based Services （LBS）. The majority of the existing works on NN queries are largely affected by the density of objects of interest, the other processing approaches such as UNICONS overcome these problems, yet there may be over-calculating problem. To overcome the problem, we propose and proof a pre-computation theory based on non-intersection path, and then to reduce the eomputational cost, we presented a novel versatile processing approach based on leaping for searching NNs of intersection points. Experimental results show that our processing approach in the NN query is correct and effective, especially the result is well performance when the intersection points sparsely distributed.