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: 11572
Venue: VLDB
Year: 2017
Pagerank: 4.4030177e-05
Overall Rank: 9,026 | 37.27%
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.6831082e-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.0032118946
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00051785122
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677
2,696	On Computing Top-t Most Influential Spatial Sites	2005	VLDB	8.279376e-05
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05
5,755	A Framework for Clustering Uncertain Data	2015	VLDB	5.3390219e-05
5,922	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	5.2678889e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,772	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	8.1491893e-05
7,235	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	4.7882389e-05
1,013	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014632051
9,309	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	4.3544778e-05
12,276	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1905499e-05
3,574	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9520978e-05
6,865	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.9002126e-05
2,099	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5429949e-05
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677