Selectivity Estimation of Reverse k-Nearest Neighbor Queries

This paper explores different heuristics to estimate the selectivity of a reverse k-nearest neighbor query. The proposed methods approximate the number of results for a given RkNN query, providing a key ingredient of common (relational) query optimizers. A range of experiments evaluate the quality of these estimates compared to the true number of results on both real and synthetic data, analyzing the potentials of the proposed approximations to make accurate predictions that can be used to generate efficient query execution plans.