Authors: Aye Thida Hlaing, Htoo Htoo, Yutaka Ohsawa
Tags: 2014, conceptual modeling
Reverse k-nearest neighbor (RkNN) queries in road network distances require long processing time in most conventional algorithms because these require kNN search on every visited node. In this paper, we propose a fast RkNN search algorithm that runs using a simple materialized path view (SMPV). In addition, we adopt the incremental Euclidean restriction (IER) strategy for fast kNN queries. In the SMPV used in our proposed algorithm, distance tables are constructed only inside of an individual partitioned subgraph, therefore the amount of data is drastically reduced in comparison with the conventional materialized path view (MPV). According to our experimental results using real road network data, our proposed method showed 100 times faster in processing time than conventional approaches when POIs are sparsely distributed on the road network.Read the full paper here: https://link.springer.com/chapter/10.1007/978-3-319-12256-4_22
