Finding Near Neighbors Through Cluster Pruning

Summary: Cluster pruning: pick random leaders, partition points by nearest leader, and search only the clusters of the closest leader(s) (with optional recursion) to obtain approximate nearest neighbors. Formalizes cost–accuracy tradeoffs, gives provable guarantees under generalized Gaussian-mixtures, and demonstrates orders-of-magnitude query speedups with modest quality loss, outperforming p-spheres in RAM and external-memory settings. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1420
Venue: PODS
Year: 2007
Pagerank: 6.4506806e-05
Overall Rank: 4,096 | 71.54%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
942	Framework for Evaluating Clustering Algorithms in Duplicate Detection	2009	VLDB	0.00015143877
2,012	ATLAS: A Probabilistic Algorithm for High Dimensional Similarity Search	2011	SIGMOD	9.8007613e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
301	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028396714
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713
707	Near Neighbor Search in Large Metric Spaces	1995	VLDB	0.00017770532
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016
3,062	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.6348035e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,549	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9792126e-05
6,865	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.9002126e-05
4,721	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9647585e-05
1,927	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	0.00010062395
1,180	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455619
7,080	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.8353058e-05
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
10,073	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.1905499e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016