Reverse kNN Query Algorithm on Road Network Distance

Abstract

This paper proposed a reverse k nearest neighbor (RkNN) query algorithm in road network distance by using the simple materialization path view (SMPV) data structure.When a set of interest objects P and a query point q are given, RkNN query retrieves reverse nearest neighbors of q from the set P. Two types of RNN, monochromatic (MRNN) and bichromatic (BRNN)are classified in the literature. In conventional approaches for RNN query on a road network distance, it takes very long processing time becausekNN search algorithm is invoked on every visited node. Using SMPV in combination with incremental Euclidean restriction (IER) framework reduces processing time in kNN search significantly. This paper studied for both types of RNN comparing with the conventional method, Eager algorithm. With extensive experiments, the proposed method outperformed Eager algorithm in term of processing time especially when the k value is large.