### Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 123-126 |

Number of pages | 4 |

Journal | Proceedings of the International Conference on Scientific and Statistical Database Management, SSDBM |

Volume | 16 |

State | Published - Oct 25 2004 |

Event | Proceedings - 16th International Conference on Scientific and Statistical Databse Management, SSDBM 2004 - Santorini Island, Greece Duration: Jun 21 2004 → Jun 23 2004 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Applied Mathematics