Earticle

Finding k nearest neighbours to one query point on road network is the typical kNN problem, and attracts lots of research interests in recent years with the development of mobile technologies. In this paper, we study a variant of the kNN problem, namely mkNN, which returns k objects for m query points. We firstly propose a baseline algorithm, which solves the mkNN problem in naive way. We then propose an optimized algorithm, which avoids the redundant computation of the baseline algorithm by organizing objects using index to firstly get candidate objects, such that to reduce the number of visited nodes of the given road network. Our third algorithm further improves the performance by using a tighter threshold to greatly reduce the number of visited nodes. We make detailed comparison between the three algorithms and show their benefits w.r.t. the mkNN problem.