JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16]


Journal of Information Science and Engineering, Vol. 32 No. 4, pp. 969-993


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


HYUNG-JU CHO1 AND JINSEOK CHAE2,+ 
1Department of Software 
Kyungpook National University 
Sangju, 37224 South Korea 
E-mail: hyungju@knu.ac.kr 
2Department of Computer Science and Engineering 
Incheon National University 
Incheon, 22012 South Korea 
E-mail: jschae@inu.ac.kr


    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.


Keywords: moving k nearest neighbor query, directed and dynamic spatial network, safe region, safe exit point, influential region

  Retrieve PDF document (JISE_201604_09.pdf)