道路网络环境下的近似反k最近邻查询算法

Approximation Reverse k-nearest Neighbor Queries in Road Network

针对欧式空间中基于R树索引结构的反最近邻查询技术不适用于道路网环境,利用任意度量空间中的M树索引结构代替R树索引结构,进行道路网络中的反最近邻查询处理.然而,由于网络距离的计算代价高的问题,使得基于M树索引的反k最近邻查询效率很低.因此,采用道路网络嵌入技术,映射道路网络到高维向量空间,简单的L∞距离准确近似计算网络距离.在此基础上,提出道路网中近似反k最近邻查询的ARkNN算法,并对本文L∞距离近似网络距离的质量、k-中心聚类算法选取参考点的有效性和ARkNN算法的查询效率进行了实验验证.

Current work which focuses on R-tree in Euclidean space for reverse nearest neighbor queries cannot be applied to road network environment,so the R-tree index is replaced by the M-tree index which is capable of indexing data in any metric space for reverse nearest neighbor queries in road network.However,network distance in road network would cause large computation cost,it is too slow to allow the M-Tree to operate efficiently on reverse k-nearest neighbor queries.The road network embedding maps the network into a higher dimensional space where L∞ metric can be used to efficiently compute an accurate approximation of network distance.Based on it,the approximation reverse k-nearest neighbor queries algorithm in road network is presented,furthermore,the quality of the distance approximations、the effectiveness of k-center clustering algorithm to select the reference point and the efficiency of ARkNN algorithm are proved by experiments.