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
3442
Venue
SIGMOD
Year
2003
Pagerank
0.00017727016
Overall Rank
710 | 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
579 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.0001982328
596 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00019455943
675 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018304179
858 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00015833075
1,013 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014632051
1,934 VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning 2020 VLDB 0.00010047294
2,384 Comparing and Aggregating Rankings with Ties 2004 PODS 8.9177815e-05
2,604 Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? * 2005 CIDR 8.4628537e-05
3,521 Merging the Results of Approximate Match Operations 2004 VLDB 7.0112669e-05
4,096 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4506806e-05
4,230 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 6.3337893e-05
4,637 Context-Sensitive Ranking 2006 SIGMOD 6.0246358e-05
5,349 Permutation Search Methods are Efficient, Yet Faster Search is Possible 2015 VLDB 5.5541926e-05
5,689 Rank aggregation with ties: Experiments and Analysis 2015 VLDB 5.3706419e-05
6,173 Similarity Search: A Matching Based Approach 2006 VLDB 5.1684255e-05
6,545 Flexible Aggregate Similarity Search 2011 SIGMOD 5.01361e-05
11,545 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.1905499e-05
12,367 Discovering Bucket Orders from Full Rankings 2008 SIGMOD 4.1905499e-05
12,610 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.1905499e-05
13,578 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
8 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0015436578
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
427 Automated Ranking of Database Query Results 2003 CIDR 0.0002350378
2,891 Joining Ranked Inputs in Practice 2002 VLDB 7.9577748e-05
3,062 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.6348035e-05
5,061 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.717245e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,096 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4506806e-05
3,549 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9792126e-05
1,535 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011461371
8,645 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4725847e-05
12,610 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.1905499e-05
3,574 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9520978e-05
4,035 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.5111577e-05
6,545 Flexible Aggregate Similarity Search 2011 SIGMOD 5.01361e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076824554
2,099 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5429949e-05