Top-n query processing in spatial databases considering bi-chromatic reverse k-nearest neighbors

Highlights：

• We propose a new top-n query, which ranks and retrieves the top-n points according to the cardinalities of the corresponding BRkNN answer sets.

• To avoid computing the exact BRkNN answer set for each candidate point, we propose a mechanism to quickly compute the upper bounds of the cardinalities.

• We propose an algorithm based on the concepts of Voronoi Diagram, bisectors, and triangle inequality for efficiently computing the BRkNN answer set for candidates.

• We also solve an extended problem about coverage maximization, i.e., finding a set of n data points to maximize the union of their respective BRkNN answer sets.