Continuous Evaluation of Monochromatic and Bichromatic
Reverse Nearest Neighbors
James M. Kang, Mohamed F. Mokbel, Shashi Shekhar, Tian Xia, Donghui Zhang
Abstract
This paper presents a novel algorithm for Incremental
and General Evaluation of continuous Reverse Nearest
neighbor queries (IGERN, for short). The IGERN algorithm
is general as it is applicable for both the monochromatic
and bichromatic reverse nearest neighbor queries. The incremental
aspect of IGERN is achieved through determining
only a small set of objects to be monitored. While previous
algorithms for monochromatic queries rely mainly on
monitoring six pie regions, IGERN takes a radical approach
by monitoring only a single region around the query object.
The IGERN algorithm clearly outperforms the state-of-theart
algorithms in monochromatic queries. In addition, the
IGERN algorithm presents the first attempt for continuous
evaluation of bichromatic reverse nearest neighbor queries.
The computational complexity of IGERN is presented in
comparison to the state-of-the-art algorithms in the monochromatic
case and to the use of Voronoi diagrams for the
bichromatic case. In addition, the correctness of IGERN in
both the monochromatic and bichromatic cases are proved.
Extensive experimental analysis shows that IGERN is efficient,
is scalable, and outperforms previous techniques for
continuous reverse nearest neighbor queries.