DBScholar

Back to papers

Similarity Search in High Dimensions via Hashing

Summary: Hashing-based scheme for approximate nearest neighbor in high-dimensional data, exploiting higher collision probability for nearby points. Experiments show substantial speedups over hierarchical-tree methods and scalability beyond 50 dimensions, addressing the curse of dimensionality. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h033990b362ea7be3
Venue
VLDB
Year
1999
Pagerank
0.00057568153
Overall Rank
20 | 99.87%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{gionis_vldb99,
        title = {{Similarity Search in High Dimensions via Hashing}},
        author = {Gionis, Aristides and Indyk, Piotr and Motwani, Rajeev},
        journal = {PVLDB},
        series = {{VLDB} '99},
        pages = {518--529},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 135 citing papers.

Rank Citing Paper Year Venue Pagerank
74 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00037091678
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027163517
194 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.00025636725
280 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.0002230467
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
341 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020539791
360 Efficient Parallel Set-Similarity Joins Using MapReduce 2010 SIGMOD 0.00020009936
457 Distributed Representations of Tuples for Entity Resolution 2018 VLDB 0.00017907103
478 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017631293
555 SageDB: A Learned Database System 2019 CIDR 0.00016506678
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
674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00014886692
713 Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan 2016 VLDB 0.00014571977
894 Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms 2019 VLDB 0.00013212578
927 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013025904
929 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013020115
992 Bayesian Locality Sensitive Hashing for Fast Similarity Search 2012 VLDB 0.00012646771
1,225 ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data 2024 SIGMOD 0.00011444398
1,462 Manu: A Cloud Native Vector Database Management System 2022 VLDB 0.0001058099
1,485 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB 0.00010523759
1,625 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 0.0001004502
1,737 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.7494976e-05
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6235776e-05
1,840 Towards Effective Partition Management for Large Graphs 2012 SIGMOD 9.5291859e-05
1,852 Semantics-aware Dataset Discovery from Data Lakes with Contextualized Column-based Representation Learning 2023 VLDB 9.5004635e-05
2,033 FREDDY: Fast Word Embeddings in Database Systems 2018 SIGMOD 9.1556118e-05
2,085 SingleStore-V: An Integrated Vector Database System in SingleStore 2024 VLDB 9.0709364e-05
2,176 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 8.9159001e-05
2,448 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4494625e-05
2,503 FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems 2017 SIGMOD 8.3786151e-05
2,505 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.3779738e-05
2,513 An Empirical Evaluation of Set Similarity Join Techniques 2016 VLDB 8.3679178e-05
2,568 Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science 2018 VLDB 8.2870435e-05
2,871 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.9229231e-05
2,872 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.9228762e-05
2,921 Leveraging Set Relations in Exact Set Similarity Join 2017 VLDB 7.8519256e-05
2,969 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.8000797e-05
3,230 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.5056037e-05
3,255 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4890984e-05
3,290 Vexless: A Serverless Vector Data Management System Using Cloud Functions 2024 SIGMOD 7.4528093e-05
3,470 Automatic Discovery of Attributes in Relational Databases 2011 SIGMOD 7.2765721e-05
3,501 An Efficient Filter for Approximate Membership Checking 2008 SIGMOD 7.2531528e-05
3,507 Approximate Embedding-Based Subsequence Matching of Time Series 2008 SIGMOD 7.2494536e-05
3,574 Scalable Discovery of Best Clusters on Large Graphs 2010 VLDB 7.1944056e-05
3,596 Overlap Set Similarity Joins with Theoretical Guarantees 2018 SIGMOD 7.1790375e-05
3,611 LEMP: Fast Retrieval of Large Entries in a Matrix Product 2015 SIGMOD 7.1628753e-05
3,750 NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic 2010 VLDB 7.0527908e-05
3,809 On the Complexity of Inner Product Similarity Join 2016 PODS 7.0089846e-05
Previous Page 1 / 3 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank Cited Paper Year Venue Pagerank
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.0004503446
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027134723
252 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023050233
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
353 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00020222998
519 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016942879
811 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013745617
2,079 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.0775779e-05
2,405 Multidimensional Access Methods: Trees Have Grown Everywhere 1997 VLDB 8.5170801e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,113 What is the nearest neighbor in high dimensional spaces? 2000 VLDB
2 674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD
3 4,856 Neighbor-Sensitive Hashing 2016 VLDB
4 5,796 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS
5 2,505 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD
6 562 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB
7 650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB
8 576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
9 45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB
10 8,818 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD