A Safe Exit Approach for Continuous Monitoring of Reverse K-Nearest Neighbors in Road Networks

作者：Attique Muhammad^*; Hailu Yared; GudetaAyele Sololia; Cho Hyung Ju; Chung Tae Sun

来源：International Arab Journal of Information Technology, 2015, 12(6): 540-549.

• Continuous monitoring
• reverse nearest neighbor query
• safe exit algorithm
• road network

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 RKNNs. 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.

• 出版日期2015-11