A pruning algorithm for reverse nearest neighbors in directed road networks

In this paper, we studied the problem of reverse k nearest neighbors (RkNN) in directed road network, where a road segment can have a particular orientation. A RNN query returns a set of data objects that take query point as their nearest neighbor. Although, much research has been done for RNN in Euclidean and undirected network space, very less attention has been paid to directed road network, where network distances are not symmetric. In this paper, we provided pruning rules which are used to minimize the network expansion while searching for the result of a RNN query. Based on these pruning rules we provide an algorithm named SWIFT for answering RNN queries in static directed road network. We evaluated SWIFT on a real world road network and our experimental results show that SWIFT significantly outperforms the naïve algorithm in terms of computational cost.