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.00010201796
Overall Rank
1,571 | 89.44%
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.9787032e-05
1,892 Efficient Computation of Reverse Skyline Queries 2007 VLDB 9.4166991e-05
2,806 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 7.9836326e-05
3,192 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.5512396e-05
3,439 Progressive Computation of the Min-Dist Optimal-Location Query 2006 VLDB 7.2994607e-05
3,774 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.0277477e-05
4,797 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.4113285e-05
5,342 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 6.1725496e-05
5,519 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.0968085e-05
5,914 Reverse Top-k Search using Random Walk with Restart 2014 VLDB 5.9490698e-05
6,108 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 5.8850424e-05
7,494 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.5095043e-05
7,941 Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN 2009 VLDB 5.4219572e-05
8,369 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3450708e-05
8,487 Reverse k Nearest Neighbors Query Processing: Experiments and Analysis 2015 VLDB 5.3322198e-05
9,329 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 5.1923126e-05
9,435 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.1780501e-05
10,762 RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem 2026 VLDB 4.9793485e-05
12,754 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB 4.9793485e-05
13,046 Database-Inspired Search 2005 VLDB 4.9793485e-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.001992968
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011405675
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051312804
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016607433
1,237 Processing Queries By Linear Constraints 1997 PODS 0.00011396286
1,405 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001076417
1,700 Discovery of Influence Sets in Frequently Updated Databases 2001 VLDB 9.8424892e-05
2,631 Reverse Nearest Neighbor Aggregates Over Data Streams 2002 VLDB 8.1996438e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,113 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,239 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB
4 10,762 RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem 2026 VLDB
5 3,325 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD
6 6,108 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB
7 12,754 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB
8 8,487 Reverse k Nearest Neighbors Query Processing: Experiments and Analysis 2015 VLDB
9 9,329 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB
10 3,774 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD