Reverse Approximate Nearest Neighbor (RANN) query relaxes the RkNN definition of influence, where a user u can be influenced by not only its closest facility but also by every other facility that is almost as close to u as its closest facility is. In this paper, we study the continuous monitoring of RANN queries on road network. Existing continuous RANN algorithms on Euclidean space cannot be extended to continuously monitor RANN queries on road network. We propose two different methods to efficiently monitor RANN queries. We conduct an extensive experiment on different real data sets and demonstrate that our both proposed algorithms are significantly better than the competitor

Given a set of facilities and a set of users, a reverse nearest neighbors (RNN) query retrieves every user$u$for which the query facility$q$is its closest facility. Since$q$is the closest facility to$u$, the user$u$is said to be influenced by$q$. In this paper, we propose arelaxeddefinition of influence where a user$u$is said to be influenced by not only its closest facility but also every other facility that isalmostas close to$u$as its closest facility is. Based on this definition of influence, we propose reverse approximate nearest neighbors (RANN) queries. Formally, given a value$x>1$, an RANN query$q$returns every user$u$for which$dist(u,q) \leq x\times NNDist(u)$where$NNDist(u)$denotes the distance between a user$u$and its nearest facility, i.e.,$q$is an approximate nearest neighbor of$u$. In this paper, we study bothsnapshotandcontinuousversions of RANN queries. In a snapshot RANN query, the underlying data sets do not change and the results of a query are to be computed only once. In the continuous version, the users continuously change their locations and the results of RANN queries are to be continuously monitored. Based on effective pruning techniques and several non-trivial observations, we propose efficient RANN query processing algorithms for both the snapshot and continuous RANN queries. We conduct extensive experiments on both real and synthetic data sets and demonstrate that our algorithm for both snapshot and continuous queries are significantly better than the competitors.