基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理，提出了分布式移动对象更新策略以有效减少服务器计算代价，利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法，以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明，SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。

Processing of k Nearest Neighbor Queries Based on Shortest Path in Road Networks

To efficiently process k nearest neighbor queries in spatial road networks, this paper presented a distributed moving objects updating strategy to reduce the computing cost of server. In-memory spatial network adjacent matrix,shortest path matrix and hash table structures were introduced to describe the road network topology and store the moving objects. A shortest path based network expansion (SPNE) algorithm was proposed to decrease the processing cost of k nearest neighbor queries by reducing the search network space. Experimental results show that the SPNE algorithm outperforms existing algorithms including NE and MKNN algorithms.