Continuous K-Nearest Neighbor Search for Moving Objects

The paper describes a new method of continuously mon-itoring the nearest neighbors of a given object in the mo-bile environment. Instead of monitoring all nearest neigh-bors, we choose to monitor the -th (nearest) neighbor since the necessary condition of changes in the KNN is the change of the -th neighbor. In addition, rather than in the origi-nal space, we consider the moving objects in a transformed time-distance (TD) space, where each object is represented by a curve. A beach-line algorithm is developed to monitor the change of the -th neighbor, which enables us to main-tain the KNN incrementally. An extensive empirical study shows that the beach-line algorithm outperforms the most efficient existing algorithm by a wide margin, especially when or (the total number of objects) is large. 1