Method for Mutual Nearest Neighbor Query in Road Networks
The problem of mutual nearest neighbor(MNN) query in road networks is proposed in this paper.Given road networks G(V,E),a set P of objects,a query object q,two parameters k1 and k2,an MNN query returns from P,the set of objects that are among the k1 nearest neighbors of q;meanwhile,have q as one of their k2 nearest neighbors.To address this problem,firstly,the paper provides a fundamental algorithm that retrieves k1 nearest neighbors of q as candidate objects and then removes the false misses.Then,based on it,an optimal algorithm is proposed,which can remove some false misses directly according to the count of mark points which fall on the edge of shortest path between object and query.Finally,the experimental results show that the optimal algorithm is efficient and effective.