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.0005758001
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.00037145866
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027151132
189 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.0002585319
278 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022310642
297 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00021849337
338 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00020600264
339 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020561716
360 Efficient Parallel Set-Similarity Joins Using MapReduce 2010 SIGMOD 0.00020001237
457 Distributed Representations of Tuples for Entity Resolution 2018 VLDB 0.00017899824
479 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017623894
555 SageDB: A Learned Database System 2019 CIDR 0.0001650754
562 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00016350316
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016118297
674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00014886449
712 Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan 2016 VLDB 0.00014593534
894 Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms 2019 VLDB 0.00013206323
927 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013028642
929 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013014029
990 Bayesian Locality Sensitive Hashing for Fast Similarity Search 2012 VLDB 0.00012643446
1,225 ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data 2024 SIGMOD 0.00011447937
1,456 Manu: A Cloud Native Vector Database Management System 2022 VLDB 0.00010588868
1,481 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB 0.00010535847
1,618 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 0.00010053127
1,739 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.7448851e-05
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6212318e-05
1,843 Towards Effective Partition Management for Large Graphs 2012 SIGMOD 9.5247198e-05
1,854 Semantics-aware Dataset Discovery from Data Lakes with Contextualized Column-based Representation Learning 2023 VLDB 9.4961138e-05
1,979 SingleStore-V: An Integrated Vector Database System in SingleStore 2024 VLDB 9.271804e-05
2,031 FREDDY: Fast Word Embeddings in Database Systems 2018 SIGMOD 9.1561855e-05
2,175 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 8.918268e-05
2,444 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4556406e-05
2,498 FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems 2017 SIGMOD 8.3800917e-05
2,501 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.3781962e-05
2,513 An Empirical Evaluation of Set Similarity Join Techniques 2016 VLDB 8.3640659e-05
2,568 Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science 2018 VLDB 8.2839378e-05
2,870 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.919641e-05
2,872 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.9191725e-05
2,923 Leveraging Set Relations in Exact Set Similarity Join 2017 VLDB 7.8482459e-05
2,955 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.8111585e-05
3,232 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.5029541e-05
3,256 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4855571e-05
3,290 Vexless: A Serverless Vector Data Management System Using Cloud Functions 2024 SIGMOD 7.4493472e-05
3,470 Automatic Discovery of Attributes in Relational Databases 2011 SIGMOD 7.273555e-05
3,501 An Efficient Filter for Approximate Membership Checking 2008 SIGMOD 7.2497317e-05
3,507 Approximate Embedding-Based Subsequence Matching of Time Series 2008 SIGMOD 7.2460219e-05
3,577 Scalable Discovery of Best Clusters on Large Graphs 2010 VLDB 7.1909999e-05
3,598 Overlap Set Similarity Joins with Theoretical Guarantees 2018 SIGMOD 7.1756405e-05
3,612 LEMP: Fast Retrieval of Large Entries in a Matrix Product 2015 SIGMOD 7.1599588e-05
3,748 NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic 2010 VLDB 7.0523418e-05
3,811 On the Complexity of Inner Product Similarity Join 2016 PODS 7.0061203e-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.00045027197
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027126333
253 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023047482
281 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022303081
352 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00020218955
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016938992
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013744009
2,077 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.0758123e-05
2,403 Multidimensional Access Methods: Trees Have Grown Everywhere 1997 VLDB 8.5150958e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,114 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,852 Neighbor-Sensitive Hashing 2016 VLDB
4 5,798 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS
5 562 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB
6 2,501 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD
7 648 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,827 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD