CSD: Discriminance with Conic Section for Improving Reverse k Nearest Neighbors Queries

Yang Li, Gang Liu, Mingyuan Bai, Junbin Gao, Lixin Ye, Zi MingarXiv 2020 · OpenReview

Abstract

Reverse $k$ Nearest Neighbor (RkNN) queries are fundamental in spatial data analysis, answering the question: "For which points is the query point $q$ one of their $k$ closest neighbors?" Despite their utility, RkNN queries are computationally expensive due to a bottleneck in the verification phase. This paper presents CSD, an algorithm that utilizes the geometric properties of conic sections—specifically ellipses and hyperbolas—to prune the search space. By reducing the verification complexity from $O(k)$ to $O(\sqrt{k})$, CSD demonstrates a significant performance leap, outperforming existing state-of-the-art methods by up to 90% in query processing time.

Introduction

In spatial databases, the Reverse $k$ Nearest Neighbor (RkNN) query is a critical operation for applications ranging from business location planning to pattern recognition. Unlike a standard $k$NN query, which identifies the $k$ closest neighbors to a query point $q$, an RkNN query identifies all points $p$ in a dataset such that $q$ is among the $k$ nearest neighbors of $p$.

The primary challenge in executing RkNN queries efficiently is the high cost of verification. Most existing algorithms employ a filter-and-refine framework. While the filtering stage can quickly identify a set of candidate points, the refinement (or verification) stage traditionally requires a full $k$NN search for every candidate to confirm its status. This paper introduces a novel approach that breaks the traditional $O(k)$ verification barrier using geometric discriminance based on conic sections.

The Verification Bottleneck

The verification phase has long been the primary bottleneck in RkNN query processing. Previous research, including the SLICE algorithm, operated under the assumption that the number of verifications could not be significantly smaller than the size of the result set. Verifying a single candidate point $p$ involves checking if the distance $dist(p, q)$ is less than or equal to the distance to its $k$-th nearest neighbor. Performing this check for every candidate leads to substantial computational overhead, especially as $k$ or the dataset size increases.

Geometric Innovation: Conic Sections

The CSD algorithm introduces a set of geometric lemmas that allow for $O(1)$ verification of many candidates by comparing them to a small "Determine Set" of points.

Positive and Negative Determine Regions

The algorithm defines two types of regions based on conic sections:

  1. Positive Determine Region (Ellipses): If a point $p^+$ is already verified as an RkNN of $q$, the algorithm defines an elliptical region around $p^+$ and $q$. Any candidate point $p$ falling within this ellipse is guaranteed to be an RkNN, eliminating the need for a $k$NN search.
  2. Negative Determine Region (Hyperbolas): Conversely, if a point $p^-$ is known not to be an RkNN, a hyperbolic region is defined. Candidates falling within this region can be immediately discarded.
The Positive Determine Region uses elliptical bounds to verify candidate points without exhaustive search.

By using these tighter geometric bounds, CSD can "auto-verify" a large portion of the candidate set, drastically reducing the number of expensive $k$NN queries.

The CSD Algorithm and VoR-tree

To implement these geometric shortcuts, the authors utilize a VoR-tree, a hybrid structure combining R-trees with Voronoi diagrams. The algorithm dynamically maintains a "Determine Set" of points, which is approximately $7.1\sqrt{k}$ in size.

Voronoi diagrams (a) and Delaunay triangulations (b) provide the spatial structure for matching candidates to determine points.

The Voronoi diagram is used to efficiently match candidate points to their nearest "determine points." Because the expected number of Voronoi neighbors in a 2D plane is constant (typically no more than 6), the search for a determine point's influence zone is highly efficient. This integration allows the algorithm to achieve an overall complexity of $O(k^{1.5} \cdot \log k)$.

Experimental Evaluation

The authors tested CSD against two leading algorithms: VR-RkNN and SLICE. The evaluation used both synthetic uniform datasets and real-world geographic data from the US National Register of Historic Places (49,601 points).

Key Results

  • Performance Gain: CSD consistently outperformed SLICE by 84% to 90% on large datasets.
  • Scalability: The advantage of CSD becomes more pronounced as $k$ increases. For $k=10,000$, CSD was nearly an order of magnitude faster than SLICE.
  • Verification Efficiency: The number of full $k$NN searches required was reduced from thousands to just a few hundred, validating the theoretical $O(\sqrt{k})$ complexity.

Conclusion

The CSD algorithm represents a significant advancement in spatial query processing. By moving beyond one-by-one verification and leveraging the collective geometric information of the dataset through conic sections, it effectively removes the primary bottleneck of RkNN queries. While currently optimized for 2D spaces, future work may explore extensions to higher dimensions and the impact of highly dynamic data updates on Voronoi-based indexing.

Summary updated

BibTeX
@misc{li2020csd,
  author = {Yang Li and Gang Liu and Mingyuan Bai and Junbin Gao and Lixin Ye and Zi Ming},
  title = {{CSD: Discriminance with Conic Section for Improving Reverse k Nearest Neighbors Queries}},
  year = {2020},
  url = {https://openreview.net/forum?id=JZI3uD8CE8G},
}
Figure