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

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 ANN 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. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Information Science & Engineering is the property of Institute of Information Science, Academia Sinica and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)