Achievement

Kang, J.M. et al. (2010). Incremental and General Evaluation of Reverse Nearest Neighbors, IEEE Transactions on Knowledge and Data Engineering (TKDE).

We present a novel algorithm for Incremental and General Evaluation of continuous Reverse Nearest neighbor queries (IGERN). Previous algorithms for monochromatic continuous reverse nearest neighbor queries rely mainly on monitoring at the worst case of six pie regions, whereas IGERN takes a radical approach by monitoring only a single region around the query object. We also propose a new optimization for the monochromatic IGERN to reduce the number of nearest neighbor searches. Furthermore, a filter and refine approach for IGERN (FR-IGERN) is proposed for the continuous evaluation of bichromatic reverse nearest neighbor queries (an optimized version of our previous approach). Extensive experimental analysis using synthetic and real datasets shows that IGERN and FR-IGERN is efficient, scalable and outperforms previous algorithms.