CSD-RkNN: reverse k nearest neighbors queries with conic section discriminances

Abstract

The reverse k nearest neighbors (RkNN) query is a prominent yet time-consuming spatial query used in facility siting, influential domain analysis, potential customer analysis, etc. Its aim is to identify all points that consider the query point as one of their k closest points. However, when k is relatively large (e.g. k = 1000), existing RkNN techniques often struggle to provide acceptable response times (within a few seconds). To address this issue, we propose a verification approach called conic section discriminance (CSD). This method serves to determine whether points belong to the RkNN set. With CSD, only a small fraction of candidates require costly k nearest neighbors (kNN) queries for verification, while the rest can be rapidly verified with O(1) complexity. Furthermore, we propose a Voronoi-based candidate generation approach to curtail the candidate set size. By leveraging the VoR-tree structure, we integrate these two approaches to form a novel RkNN algorithm named CSD-RkNN. A comprehensive set of experiments is conducted to compare CSD-RkNN with Slice as the state-of-the-art RkNN algorithm, and VR-RkNN as the original RkNN algorithm on VoR-tree. The results indicate that CSD-RkNN consistently outperforms the other two algorithms, especially when k is relatively large.

Keywords:

• Spatial query
• facility location
• reverse k nearest neighbors
• conic section discriminance
• Voronoi diagram

Acknowledgements

We sincerely thank the editors and the four anonymous reviewers for their useful comments and suggestions that significantly strengthened this manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data and codes availability statement

The data and codes that support the findings of this study are available with the identifier at https://doi.org/10.6084/m9.figshare.23932518.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China (Grant No. 42171466 and Grant No. U1711267); and the Humanities and Social Science Fund of Ministry of Education of China (Grant No. 22YJC630107).

Notes on contributors

Yang Li

Yang Li is currently a post-doctor researcher at the School of Geography and Information Engineering, China University of Geosciences. His research interests include spatial indexing, spatial queries and evolutionary computation.

Mingyuan Bai

Mingyuan Bai is currently a post-doctor researcher at Tensor Learning Team, RIKEN AIP. Her research interests include adversarial defense, tensor learning and generative models.

Qingfeng Guan

Qingfeng Guan is a professor at the School of Geography and Information Engineering, China University of Geosciences. His research interests include spatial intelligence, parallel computing, cellular automata and remote sensing.

Zi Ming

Zi Ming is a lecturer at the School of Economics and Management, Hubei University of Technology. Her research interests include energy economy, sustainable development and spatial analysis.

Xun Liang

Xun Liang is a professor at the School of Geography and Information Engineering, China University of Geosciences. His research interests include land use simulation and spatio-temporal modeling.

Gang Liu

Gang Liu is a professor at the School of Compute Science, China University of Geosciences. His research interests include spatial database, spatial analysis and 3D geological modeling.

Junbin Gao

Junbin Gao is a professor at the University of Sydney Business School, the University of Sydney. His research interests include geometric deep learning, statistical learning and nonconvex optimization.