Database Paper Browser

Back to papers

Reverse kNN Search in Arbitrary Dimensionality

Summary: Exact reverse kNN (RkNN) processing for arbitrary k on dynamic multidimensional data, delivering true exact results. Uses a conventional data-partitioning index with no pre-computation and outperforms 2D-only, approximate, or non-updatable methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9183
Venue
VLDB
Year
2004
Pagerank
0.00010038508
Overall Rank
1,933 | 86.56%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
1,513 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00011593275
2,454 Efficient Computation of Reverse Skyline Queries 2007 VLDB 8.778281e-05
2,711 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 8.2492925e-05
3,272 Progressive Computation of the Min-Dist Optimal-Location Query 2006 VLDB 7.2958583e-05
3,632 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 6.9009547e-05
4,070 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.4784181e-05
4,960 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 5.7987607e-05
5,917 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 5.2739511e-05
5,946 Reverse Top-k Search using Random Walk with Restart 2014 VLDB 5.2616887e-05
6,045 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 5.2372658e-05
6,946 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 4.8909775e-05
7,540 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 4.7159549e-05
8,359 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 4.5372925e-05
8,557 Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN 2009 VLDB 4.4937074e-05
9,025 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 4.4072367e-05
9,121 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 4.3922853e-05
9,309 Reverse k Nearest Neighbors Query Processing: Experiments and Analysis 2015 VLDB 4.3571035e-05
12,268 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB 4.1945683e-05
12,563 Database-Inspired Search 2005 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
47 Nearest Neighbor Queries 1995 SIGMOD 0.0007015885
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
601 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00019375875
1,172 Processing Queries By Linear Constraints 1997 PODS 0.00013505441
1,528 A Model for the Prediction of R-tree Performance 1996 PODS 0.00011497734
1,682 Discovery of Influence Sets in Frequently Updated Databases 2001 VLDB 0.00010923103
2,702 Reverse Nearest Neighbor Aggregates Over Data Streams 2002 VLDB 8.2725214e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,960 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 5.7987607e-05
2,107 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5330494e-05
601 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00019375875
7,239 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.792836e-05
3,579 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9502303e-05
6,946 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 4.8909775e-05
12,268 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB 4.1945683e-05
9,309 Reverse k Nearest Neighbors Query Processing: Experiments and Analysis 2015 VLDB 4.3571035e-05
9,025 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 4.4072367e-05
4,070 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.4784181e-05