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
8786
Venue
VLDB
Year
1999
Pagerank
0.00056760516
Overall Rank
21 | 99.86%
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 129 citing papers.

Rank Citing Paper Year Venue Pagerank
93 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00034701237
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.0002743469
286 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.00022357911
287 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022323585
332 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00020920444
356 Efficient Parallel Set-Similarity Joins Using MapReduce 2010 SIGMOD 0.00020303289
369 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00019945234
406 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00019054532
468 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017986163
489 Distributed Representations of Tuples for Entity Resolution 2018 VLDB 0.0001761456
568 SageDB: A Learned Database System 2019 CIDR 0.0001641553
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
690 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.0001492934
805 Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan 2016 VLDB 0.00013891999
911 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013283031
990 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00012796562
991 Bayesian Locality Sensitive Hashing for Fast Similarity Search 2012 VLDB 0.00012793339
1,066 Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms 2019 VLDB 0.00012333161
1,515 ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data 2024 SIGMOD 0.00010521317
1,546 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB 0.00010407159
1,589 Manu: A Cloud Native Vector Database Management System 2022 VLDB 0.00010264469
1,701 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.9707165e-05
1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.7769047e-05
1,803 Towards Effective Partition Management for Large Graphs 2012 SIGMOD 9.724402e-05
1,934 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 9.4561907e-05
2,075 FREDDY: Fast Word Embeddings in Database Systems 2018 SIGMOD 9.2132247e-05
2,137 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 9.110238e-05
2,192 Semantics-aware Dataset Discovery from Data Lakes with Contextualized Column-based Representation Learning 2023 VLDB 8.9767241e-05
2,501 An Empirical Evaluation of Set Similarity Join Techniques 2016 VLDB 8.4975661e-05
2,541 Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science 2018 VLDB 8.4500033e-05
2,572 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4027322e-05
2,673 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.2730112e-05
2,920 SingleStore-V: An Integrated Vector Database System in SingleStore 2024 VLDB 7.9628307e-05
2,938 FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems 2017 SIGMOD 7.942728e-05
3,037 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.8275859e-05
3,040 Leveraging Set Relations in Exact Set Similarity Join 2017 VLDB 7.8262287e-05
3,193 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.649474e-05
3,240 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.6071649e-05
3,279 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.5711218e-05
3,310 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.5363562e-05
3,364 Vexless: A Serverless Vector Data Management System Using Cloud Functions 2024 SIGMOD 7.4796687e-05
3,440 Approximate Embedding-Based Subsequence Matching of Time Series 2008 SIGMOD 7.4142918e-05
3,442 An Efficient Filter for Approximate Membership Checking 2008 SIGMOD 7.4122197e-05
3,456 Automatic Discovery of Attributes in Relational Databases 2011 SIGMOD 7.3998323e-05
3,511 Scalable Discovery of Best Clusters on Large Graphs 2010 VLDB 7.3556982e-05
3,676 LEMP: Fast Retrieval of Large Entries in a Matrix Product 2015 SIGMOD 7.2094091e-05
3,722 NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic 2010 VLDB 7.1726862e-05
3,724 Overlap Set Similarity Joins with Theoretical Guarantees 2018 SIGMOD 7.1715735e-05
3,806 On the Complexity of Inner Product Similarity Join 2016 PODS 7.108802e-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
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
168 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027541029
261 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023097188
277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022537944
353 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00020370587
508 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00017275873
797 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013927251
2,101 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.1657486e-05
2,421 Multidimensional Access Methods: Trees Have Grown Everywhere 1997 VLDB 8.6033032e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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