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: 3503
Venue: SIGMOD
Year: 2003
Pagerank: 0.0001492934
Overall Rank: 690 | 95.27%
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
332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020920444
369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019945234
580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016157635
581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016153395
705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014829964
1,430	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.0001080902
2,359	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.698016e-05
2,652	Comparing and Aggregating Rankings with Ties	2004	PODS	8.291138e-05
3,279	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.5711218e-05
3,610	Merging the Results of Approximate Match Operations	2004	VLDB	7.2593873e-05
4,622	Context-Sensitive Ranking	2006	SIGMOD	6.6014783e-05
4,657	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.5830079e-05
4,970	Permutation Search Methods are Efficient, Yet Faster Search is Possible	2015	VLDB	6.4197336e-05
6,483	Similarity Search: A Matching Based Approach	2006	VLDB	5.8667204e-05
6,717	Rank aggregation with ties: Experiments and Analysis	2015	VLDB	5.795458e-05
6,746	Flexible Aggregate Similarity Search	2011	SIGMOD	5.7850397e-05
11,738	Fast Algorithm for Anchor Graph Hashing	2021	VLDB	5.093636e-05
12,552	Discovering Bucket Orders from Full Rankings	2008	SIGMOD	5.093636e-05
12,794	Efficiency-Quality Tradeoffs for Vector Score Aggregation	2004	VLDB	5.093636e-05
13,765	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.0010828372
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
466	Automated Ranking of Database Query Results	2003	CIDR	0.00018014467
3,017	Joining Ranked Inputs in Practice	2002	VLDB	7.8483041e-05
3,282	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.5667715e-05
5,963	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	6.0267197e-05

Semantically Similar Papers

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