Efficient Continuous Nearest Neighbor Query in Spatial Networks Using Euclidean Restriction

In this paper, we propose an efficient method to answer continuous

k

nearest neighbor (C

k

NN) queries in spatial networks. Assuming a moving query object and a set of data objects that make frequent and arbitrary moves on a spatial network with dynamically changing edge weights, C

k

NN continuously monitors the nearest (in network distance) neighboring objects to the query. Previous C

k

NN methods are inefficient and, hence, fail to scale in large networks with numerous data objects because: 1) they heavily rely on Dijkstra-based

blind expansion

for network distance computation that incurs excessively redundant cost particularly in large networks, and 2) they

blindly map

all object location updates to the network disregarding whether the updates are relevant to the C

k

NN query result. With our method, termed ER-C

k

NN (short for

Euclidian Restriction

based C

k

NN), we utilize ER to address both of these shortcomings. Specifically, with ER we enable 1)

guided search

(rather than blind expansion) for efficient network distance calculation, and 2)

localized mapping

(rather than blind mapping) to avoid the intolerable cost of redundant object location mapping. We demonstrate the efficiency of ER-C

k

NN via extensive experimental evaluations with real world datasets consisting of a variety of large spatial networks with numerous moving objects.