New Approach to Continuous k-Nearest Neighbor Monitoring in a Directed Road Network
Tadesse Merkebu, Hyung-Ju Cho, Ha-Joo Song, Sungsoo Kim and Tae-Sun Chung
Moving nearest neighbor (NN) queries in road networks have been extensively studied in recent years. However, few algorithms exist for moving queries in directed road networks. In this study, we introduce a new directed safe exit algorithm (DSEA), which efficiently computes safe exit points of a moving NN query on directed road networks in which each road segment has a particular orientation. The safe region of a query is an area in which the query result remains unchanged if the query remains inside the safe region. At each safe exit point, the safe and unsafe regions of a query meet such that a set of safe exit points represents the border of the safe region. Before reaching a safe exit point, the client (i.e., the query object) is not required to request that the server re-evaluate the query. This substantially reduces server processing and communication costs between the server and moving clients.
Keywords: Directed road network, moving k-nearest neighbor query, safe region, safe exit point, continuous monitoring.