Continuous k-nearest neighbor search for moving objects

Yifan Li, Jiong Yang, Jiawei Han

Research output: Contribution to journalConference article


The paper describes a new method of continuously monitoring the k nearest neighbors of a given object in the mobile environment. Instead of monitoring all k nearest neighbors, we choose to monitor the k-th (nearest) neighbor since the necessary condition of changes in the KNN is the change of the k-th neighbor. In addition, rather than in the original 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 k-th neighbor, which enables us to maintain 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 k or n (the total number of objects) is large.

Original languageEnglish (US)
Pages (from-to)123-126
Number of pages4
JournalProceedings of the International Conference on Scientific and Statistical Database Management, SSDBM
StatePublished - Oct 25 2004
EventProceedings - 16th International Conference on Scientific and Statistical Databse Management, SSDBM 2004 - Santorini Island, Greece
Duration: Jun 21 2004Jun 23 2004


ASJC Scopus subject areas

  • Software
  • Applied Mathematics

Cite this