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
9374
Venue
VLDB
Year
2004
Pagerank
0.00010218134
Overall Rank
1,612 | 88.95%
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 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
1,618 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00010207737
1,847 Efficient Computation of Reverse Skyline Queries 2007 VLDB 9.6252055e-05
2,761 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 8.154319e-05
3,139 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.7188328e-05
3,428 Progressive Computation of the Min-Dist Optimal-Location Query 2006 VLDB 7.4213355e-05
3,710 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.1780127e-05
4,711 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.5506926e-05
5,664 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 6.1289238e-05
5,815 Reverse Top-k Search using Random Walk with Restart 2014 VLDB 6.0777346e-05
5,875 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.0564961e-05
6,561 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 5.8389373e-05
7,350 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.6358517e-05
8,200 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.4677285e-05
8,760 Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN 2009 VLDB 5.3766157e-05
9,165 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 5.3101672e-05
9,261 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.2968259e-05
9,356 Reverse k Nearest Neighbors Query Processing: Experiments and Analysis 2015 VLDB 5.282937e-05
12,463 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB 5.093636e-05
12,756 Database-Inspired Search 2005 VLDB 5.093636e-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.0020210012
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
28 Nearest Neighbor Queries 1995 SIGMOD 0.00052102434
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
546 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016734556
1,219 Processing Queries By Linear Constraints 1997 PODS 0.00011620957
1,373 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001098638
1,681 Discovery of Influence Sets in Frequently Updated Databases 2001 VLDB 0.00010022485
2,587 Reverse Nearest Neighbor Aggregates Over Data Streams 2002 VLDB 8.3747444e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,735 High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations 2023 SIGMOD
2 2,158 What is the nearest neighbor in high dimensional spaces? 2000 VLDB
3 546 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD
4 6,133 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB
5 3,363 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD
6 6,561 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB
7 12,463 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB
8 9,356 Reverse k Nearest Neighbors Query Processing: Experiments and Analysis 2015 VLDB
9 9,165 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB
10 3,710 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD