Approximation Reverse k-nearest Neighbor Queries in Road Network
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.