DBScholar

Back to papers

Reverse kNN Search in Arbitrary Dimensionality

Summary: Introduces exact reverse-kNN algorithms supporting arbitrary k and dimensionality on dynamic datasets. They use conventional data-partitioning indexes without precomputation, enabling updates and outperforming prior restricted or approximate methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h2df562061f0b305a
Venue
VLDB
Year
2004
Pagerank
0.00010164216
Overall Rank
1,574 | 89.46%
DOI
10.1016/B978-012088469-8.50066-8

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{tao_vldb04,
        title = {{Reverse kNN Search in Arbitrary Dimensionality}},
        author = {Tao, Yufei and Papadias, Dimitris and Lian, Xiang},
        journal = {PVLDB},
        series = {{VLDB} '04},
        volume = {30},
        pages = {744--755},
        doi = {10.1016/B978-012088469-8.50066-8},
        url = {https://doi.org/10.1016/B978-012088469-8.50066-8},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank Citing Paper Year Venue Pagerank
1,661 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 9.9409992e-05
1,905 Efficient Computation of Reverse Skyline Queries 2007 VLDB 9.3819594e-05
2,819 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 7.953478e-05
3,203 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.5227628e-05
3,452 Progressive Computation of the Min-Dist Optimal-Location Query 2006 VLDB 7.2720334e-05
3,784 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.0012942e-05
4,821 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.3876508e-05
5,360 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 6.1498141e-05
5,537 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.075858e-05
5,928 Reverse Top-k Search using Random Walk with Restart 2014 VLDB 5.9281079e-05
6,123 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 5.8633884e-05
7,519 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.4892692e-05
7,960 Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN 2009 VLDB 5.4014706e-05
8,382 Reverse k Nearest Neighbors Query Processing: Experiments and Analysis 2015 VLDB 5.3266895e-05
8,391 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3248747e-05
9,364 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 5.1726938e-05
9,465 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.1590473e-05
10,833 RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem 2026 VLDB 4.9605343e-05
12,803 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB 4.9605343e-05
13,094 Database-Inspired Search 2005 VLDB 4.9605343e-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.0019892478
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011386412
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051134355
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
547 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016545689
1,241 Processing Queries By Linear Constraints 1997 PODS 0.00011373551
1,412 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010725178
1,704 Discovery of Influence Sets in Frequently Updated Databases 2001 VLDB 9.806015e-05
2,643 Reverse Nearest Neighbor Aggregates Over Data Streams 2002 VLDB 8.1688309e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,129 What is the nearest neighbor in high dimensional spaces? 2000 VLDB
2 547 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD
3 6,256 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB
4 10,833 RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem 2026 VLDB
5 3,330 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD
6 6,123 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB
7 12,803 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB
8 8,382 Reverse k Nearest Neighbors Query Processing: Experiments and Analysis 2015 VLDB
9 9,364 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB
10 3,784 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD