A Safe
Exit Approach for Continuous Monitoring of Reverse k Nearest Neighbors in
Road Networks
Muhammad Attique, Yared Hailu,
Sololia GudetaAyele, Hyung-Ju Cho and Tae-Sun Chung
Department of Computer Engineering, Ajou University, South Korea
Abstract: Reverse k Nearest Neighbor (RKNN) queries
in road networks have been studied extensively in recent years. However, at
present, there is still a lack of algorithms for moving queries in a road network.
In this paper, we study how to efficiently process moving queries. Existing
algorithms do not efficiently handle query movement. For instance, whenever a
query changes its location, the result of the query has to be recomputed. To
avoid this recomputation, we introduce a new technique that can efficiently
compute the safe exit points for continuous reverse k nearest neighbors. Within
these safe exit points, the query result remains unchanged and a request for
recomputation of the query does not have to be made to the server. This
significantly reduces server processing costs and the communication costs
between the server and moving clients. The results of extensive experiments
conducted using real road network data indicate that our proposed algorithm
significantly reduces communication and computation costs.
Keywords: continuous monitoring, reverse nearest neighbor
query, safe exit algorithm, road network