Efficient Similarity Search and Classification via Rank Aggregation

Summary: Rank-aggregation with independent voters projecting on random lines; median-rank rule yields a (1+ε)-approximate Euclidean NN. Very efficient: probes ~5% of data, no extra storage, DB-friendly fixed access order; extends to k-NN and classification. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf89ca347f79109bc
Venue: SIGMOD
Year: 2003
Pagerank: 0.00014886692
Overall Rank: 674 | 95.48%
DOI: 10.1145/872757.872795

Incoming Non-self Citations Over Time

Authors

1. Ronald Fagin (IBM)
2. Ravi Kumar (IBM)
3. D. Sivakumar (IBM)

BibTeX Citation

@inproceedings{fagin_sigmod03,
        title = {{Efficient Similarity Search and Classification via Rank Aggregation}},
        author = {Fagin, Ronald and Kumar, Ravi and Sivakumar, D.},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872795},
        url = {https://dl.acm.org/doi/10.1145/872757.872795},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021833987
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020585187
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016335405
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016121388
650	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00015149775
1,328	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00011003106
2,396	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.5278724e-05
2,709	Comparing and Aggregating Rankings with Ties	2004	PODS	8.1063128e-05
2,969	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.8000797e-05
3,593	Merging the Results of Approximate Match Operations	2004	VLDB	7.183446e-05
4,705	Context-Sensitive Ranking	2006	SIGMOD	6.4591302e-05
4,728	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4473669e-05
4,886	Permutation Search Methods are Efficient, Yet Faster Search is Possible	2015	VLDB	6.3694868e-05
6,610	Similarity Search: A Matching Based Approach	2006	VLDB	5.7350971e-05
6,850	Rank aggregation with ties: Experiments and Analysis	2015	VLDB	5.6654235e-05
6,868	Flexible Aggregate Similarity Search	2011	SIGMOD	5.6599382e-05
12,041	Fast Algorithm for Anchor Graph Hashing	2021	VLDB	4.9793485e-05
12,842	Discovering Bucket Orders from Full Rankings	2008	SIGMOD	4.9793485e-05
13,084	Efficiency-Quality Tradeoffs for Vector Score Aggregation	2004	VLDB	4.9793485e-05
14,076	Corrigendum to "Efficient Similarity Search and Classification via Rank Aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (Proc. SIGMOD'03)	2008	SIGMOD	-

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
474	Automated Ranking of Database Query Results	2003	CIDR	0.00017672562
3,049	Joining Ranked Inputs in Practice	2002	VLDB	7.7090549e-05
3,320	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.4302233e-05
6,032	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.9097667e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,728	Finding Near Neighbors Through Cluster Pruning	2007	PODS
2	3,887	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
3	1,635	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
4	8,818	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD
5	13,084	Efficiency-Quality Tradeoffs for Vector Score Aggregation	2004	VLDB
6	3,325	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
7	3,774	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
8	6,868	Flexible Aggregate Similarity Search	2011	SIGMOD
9	20	Similarity Search in High Dimensions via Hashing	1999	VLDB
10	2,113	What is the nearest neighbor in high dimensional spaces?	2000	VLDB