Back to Search
Start Over
CSD-RkNN: reverse k nearest neighbors queries with conic section discriminances.
- Source :
- International Journal of Geographical Information Science; Oct2023, Vol. 37 Issue 10, p2175-2204, 30p
- Publication Year :
- 2023
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- CONIC sections
VORONOI polygons
CONSUMERS
Subjects
Details
- Language :
- English
- ISSN :
- 13658816
- Volume :
- 37
- Issue :
- 10
- Database :
- Complementary Index
- Journal :
- International Journal of Geographical Information Science
- Publication Type :
- Academic Journal
- Accession number :
- 171997969
- Full Text :
- https://doi.org/10.1080/13658816.2023.2249521