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: 11571
Venue: VLDB
Year: 2017
Pagerank: 4.4072367e-05
Overall Rank: 9,025 | 37.22%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,654	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	4.687476e-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.0032169493
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508
2,711	On Computing Top-t Most Influential Spatial Sites	2005	VLDB	8.2492925e-05
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
5,755	A Framework for Clustering Uncertain Data	2015	VLDB	5.3402052e-05
6,045	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	5.2372658e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,811	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	8.0806307e-05
7,239	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	4.792836e-05
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
9,309	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	4.3571035e-05
12,268	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1945683e-05
3,579	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9502303e-05
6,946	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.8909775e-05
2,107	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5330494e-05
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508