Efficiently monitoring reverse k-nearest neighbors in spatial networks

Shenlu Wang, Muhammad Aamir Cheema, Xuemin Lin

Research output: Contribution to journalArticleResearchpeer-review

8 Citations (Scopus)


Given a set of clients C, a set of facilities F and a query q∈F, a reverse k-nearest neighbor (RκNN) query retrieves every client c∈C for which q is one of the κ closest facilities. In the past few years, RkNN queries have received significant research attention due to their wide range of applications. In this paper, we study the problem of continuous monitoring of RκNN queries in road networks. The state-of-the-art technique is sensitive toward the movement of clients, e.g. whenever a client that is inside the so-called unpruned region changes its location, the existing technique requires expensive verification of whether the client is an RκNN of q or not. To address this problem, we utilize the novel concept of influence zone, which is a region in the network such that a client c is the RκNN if and only if it lies inside this zone. This significantly improves performance because the problem of continuously monitoring RκNN queries is reduced to the problem of continuously monitoring the clients that are inside this zone. Based on several non-trivial observations, we present an efficient algorithm to compute the influence zone. Our extensive experimental study demonstrates that our algorithm is more than an order of magnitude faster than the state-of-the-art algorithm.
Original languageEnglish
Pages (from-to)40-56
Number of pages17
JournalComputer Journal
Issue number1
Publication statusPublished - 2015
Externally publishedYes


  • spatial networks
  • RkNN queries
  • continuous monitoring
  • spatial queries

Cite this