A Safe Exit Algorithm for Moving k Nearest Neighbor Queries in Directed and Dynamic Spatial Networks

作者：Cho Hyung Ju; Chae Jinseok

来源：Journal of Information Science and Engineering, 2016, 32(4): 969-993.

• moving k nearest neighbor query
• directed and dynamic spatial network
• safe region
• safe exit point
• influential region

The process of moving k nearest neighbor (MkNN) queries has been studied extensively in spatial network databases. Existing state-of-the-art algorithms have focused primarily on handling MkNN queries in undirected and static spatial networks where every edge is undirected and its weight does not change over time. However, little attention has been paid to MkNN queries in directed and dynamic spatial networks where each edge has a particular orientation and its weight may change over time. In this study, we propose a Safe Exit Algorithm, named SEAD, for MkNN queries in Directed and Dynamic spatial networks. The safe region of a moving query object is an area where the movement of the query object does not cause the current kNN set to change. A safe exit point is the contact point between the safe and non-safe regions. Thus, the set of safe exit points constitutes the border of the safe region. Before reaching a safe exit point, the query object is not required to request that the server reevaluate the kNN query. This significantly reduces the communication and computational costs between the server and query objects. We also introduce the concept of influential region to guarantee the validity of safe regions in dynamic spatial networks. The results of our experiments using real-life road maps confirm the superiority of the proposed method.

• 出版日期2016-7