Continuous reverse k nearest neighbor monitoring on moving objects in road networks

Guohui Li, Yanhong Li, Jianjun Li, Lihchyun Shu, Fumin Yang

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)


Continuous reverse k nearest neighbor (CRkNN) monitoring in road networks has recently received increasing attentions. However, there is still a lack of efficient CRkNN algorithms in road networks up to now. In road networks, moving query objects and data objects are restricted by the connectivity of the road network and both the objectquery distance and objectobject distance updates affect the result of CRkNN queries. In this paper, we present a novel algorithm for continuous and incremental evaluation of CRkNN queries in road networks. Our method is based on a novel data structure called dual layer multiway tree (DLM tree) we proposed to represent the whole monitoring region of a CRkNN query q. We propose several lemmas to reduce the monitoring region of q and the number of candidate objects as much as possible. Moreover, by associating a variable NN-count with each candidate object, we can simplify the monitoring of candidate objects. There are a large number of objects roaming in a road network and many of them are irrelevant to a specific CRkNN query of a query object q. To minimize the processing extension, for a road in the network, we give an IQL list and an IQCL list to specify the set of query objects and data objects whose location updates should be maintained for CRkNN processing of query objects. Our CRkNN method consists of two phase: the initial result generating phase and incremental maintenance phase. In each phase, algorithms with high performance are proposed to make our CRkNN method more efficient. Extensive simulation experiments are conducted and the result shows that our proposed approach is efficient and scalable in processing CRkNN queries in road networks.

Original languageEnglish
Pages (from-to)860-883
Number of pages24
JournalInformation Systems
Issue number8
Publication statusPublished - 2010 Dec

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Continuous reverse k nearest neighbor monitoring on moving objects in road networks'. Together they form a unique fingerprint.

Cite this