Dimensional Testing for Reverse k-Nearest Neighbor Search

Summary: Dimensional testing uses intrinsic dimensionality to guide pruning and termination in approximate reverse k-nearest neighbor search. Compatible with any incremental NN index; reduces preprocessing while improving time/accuracy tradeoffs versus prior approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11759
Venue: VLDB
Year: 2017
Pagerank: 5.3101672e-05
Overall Rank: 9,165 | 37.13%
DOI: 10.14778/3067421.3067426

Incoming Non-self Citations Over Time

Authors

1. Guillaume Casanova (National Office for Aerospace Studies and Research)
2. Elias Englmeier (Ludwig Maximilian University of Munich)
3. Michael E. Houle (National Institute of Informatics)
4. Peer Kröger (Ludwig Maximilian University of Munich)
5. Michael Nett (Google)
6. Erich Schubert (Heidelberg University)
7. Arthur Zimek (University of Southern Denmark)

BibTeX Citation

@article{casanova_vldb17,
        title = {{Dimensional Testing for Reverse k-Nearest Neighbor Search}},
        author = {Casanova, Guillaume and Englmeier, Elias and Houle, Michael E. and Kröger, Peer and Nett, Michael and Schubert, Erich and Zimek, Arthur},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {7},
        pages = {769--780},
        doi = {10.14778/3067421.3067426},
        url = {https://doi.org/10.14778/3067421.3067426},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,376	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	5.6298131e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
546	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016734556
1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010218134
2,761	On Computing Top-t Most Influential Spatial Sites	2005	VLDB	8.154319e-05
3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	7.1780127e-05
5,664	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	6.1289238e-05
5,843	A Framework for Clustering Uncertain Data	2015	VLDB	6.068841e-05

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	705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB
3	6,133	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB
4	9,356	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB
5	12,463	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
6	3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
7	6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
8	2,158	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
9	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
10	1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB