Database Paper Browser

Back to papers

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
3441
Venue
SIGMOD
Year
2003
Pagerank
0.00017768547
Overall Rank
709 | 95.07%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank Citing Paper Year Venue Pagerank
562 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00020091752
605 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.000193396
682 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018201541
867 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00015792021
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
1,757 VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning 2020 VLDB 0.00010660932
2,385 Comparing and Aggregating Rankings with Ties 2004 PODS 8.9247846e-05
2,599 Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? * 2005 CIDR 8.4702307e-05
3,529 Merging the Results of Approximate Match Operations 2004 VLDB 7.0059524e-05
4,090 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4577834e-05
4,243 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 6.32976e-05
4,637 Context-Sensitive Ranking 2006 SIGMOD 6.0303293e-05
5,352 Permutation Search Methods are Efficient, Yet Faster Search is Possible 2015 VLDB 5.5529869e-05
5,700 Rank aggregation with ties: Experiments and Analysis 2015 VLDB 5.365274e-05
6,164 Similarity Search: A Matching Based Approach 2006 VLDB 5.1733919e-05
6,547 Flexible Aggregate Similarity Search 2011 SIGMOD 5.0183532e-05
11,541 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.1945683e-05
12,359 Discovering Bucket Orders from Full Rankings 2008 SIGMOD 4.1945683e-05
12,601 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.1945683e-05
13,565 Corrigendum to "Efficient Similarity Search and Classification via Rank Aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (Proc. SIGMOD'03) 2008 SIGMOD -
Previous Page 1 / 1 Next

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
7 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0015496097
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
427 Automated Ranking of Database Query Results 2003 CIDR 0.0002352637
2,883 Joining Ranked Inputs in Practice 2002 VLDB 7.9656673e-05
3,061 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.6382127e-05
5,065 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.7247716e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,090 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4577834e-05
3,555 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9772546e-05
8,647 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4768766e-05
1,542 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011456321
12,601 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.1945683e-05
3,579 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9502303e-05
4,070 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.4784181e-05
6,547 Flexible Aggregate Similarity Search 2011 SIGMOD 5.0183532e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
2,107 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5330494e-05