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.
Description:
edgments
This study was partially supported by the
Japanese Ministry of Education, Science, Sports and
Culture (Grant-in-Aid Science Research (C)
24500107).