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.00010197322
Overall Rank
1,571 | 89.45%
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,650 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 9.9739794e-05
1,895 Efficient Computation of Reverse Skyline Queries 2007 VLDB 9.4125147e-05
2,807 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 7.9798533e-05
3,193 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.5476762e-05
3,439 Progressive Computation of the Min-Dist Optimal-Location Query 2006 VLDB 7.2960053e-05
3,776 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.0244572e-05
4,799 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.4084993e-05
5,348 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 6.1698901e-05
5,519 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.0941936e-05
5,918 Reverse Top-k Search using Random Walk with Restart 2014 VLDB 5.9465067e-05
6,109 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 5.8825187e-05
7,500 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.5071583e-05
7,945 Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN 2009 VLDB 5.4193905e-05
8,374 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3425405e-05
8,409 Reverse k Nearest Neighbors Query Processing: Experiments and Analysis 2015 VLDB 5.3362771e-05
9,338 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 5.1898547e-05
9,441 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.175852e-05
10,772 RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem 2026 VLDB 4.9769913e-05
12,760 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB 4.9769913e-05
13,052 Database-Inspired Search 2005 VLDB 4.9769913e-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.0019923528
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051292389
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034847854
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016599925
1,239 Processing Queries By Linear Constraints 1997 PODS 0.00011391184
1,405 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010759378
1,700 Discovery of Influence Sets in Frequently Updated Databases 2001 VLDB 9.8381262e-05
2,634 Reverse Nearest Neighbor Aggregates Over Data Streams 2002 VLDB 8.1957991e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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