A continuous nearest neighbor query retrieves the nearest neighbor (NN) of every point on a line segment (e.g., "find all my nearest gas stations during my route from point s to point e"). The result contains a set of <point, interval> tuples, such that point is the NN of all points in the corresponding interval. Existing methods for continuous nearest neighbor search are based on the repetitive application of simple NN algorithms, which incurs significant overhead. In this paper we propose techniques that solve the problem by performing a single query for the whole input segment. As a result the cost, depending on the query and dataset characteristics, may drop by orders of magnitude. In addition, we propose analytical models for the expected size of the output, as well as, the cost of query processing, and extend out techniques to several variations of the problem.
On the other hand, for a line segment and a set of points, Continuous Nearest Neighbor Search REF returns the nearest neighbor of each point on the line segment.
Continuous Nearest Neighbor Search
VLDB
Computer Science