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.00057610161
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
75 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00037163157
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027077763
181 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.00026425782
281 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022262975
286 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00022090962
325 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020930941
339 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00020558018
359 Efficient Parallel Set-Similarity Joins Using MapReduce 2010 SIGMOD 0.00019963275
459 Distributed Representations of Tuples for Entity Resolution 2018 VLDB 0.00017863654
481 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017567157
550 SageDB: A Learned Database System 2019 CIDR 0.00016525249
562 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00016344855
578 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016079505
674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00014872783
710 Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan 2016 VLDB 0.00014598403
897 Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms 2019 VLDB 0.00013162662
925 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013026835
934 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00012973416
987 Bayesian Locality Sensitive Hashing for Fast Similarity Search 2012 VLDB 0.00012643645
1,229 ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data 2024 SIGMOD 0.00011420277
1,280 Manu: A Cloud Native Vector Database Management System 2022 VLDB 0.00011199537
1,460 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB 0.00010558941
1,618 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 0.00010045437
1,742 Semantics-aware Dataset Discovery from Data Lakes with Contextualized Column-based Representation Learning 2023 VLDB 9.7283207e-05
1,751 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.7128647e-05
1,797 SingleStore-V: An Integrated Vector Database System in SingleStore 2024 VLDB 9.6056634e-05
1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.5936926e-05
1,847 Towards Effective Partition Management for Large Graphs 2012 SIGMOD 9.5053324e-05
2,030 FREDDY: Fast Word Embeddings in Database Systems 2018 SIGMOD 9.1437256e-05
2,183 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 8.8973287e-05
2,293 FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems 2017 SIGMOD 8.6780858e-05
2,426 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4692316e-05
2,501 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.359489e-05
2,514 An Empirical Evaluation of Set Similarity Join Techniques 2016 VLDB 8.3446573e-05
2,570 Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science 2018 VLDB 8.2599759e-05
2,879 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.8951769e-05
2,885 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.8929868e-05
2,933 Leveraging Set Relations in Exact Set Similarity Join 2017 VLDB 7.827041e-05
2,968 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.7879589e-05
3,193 Vexless: A Serverless Vector Data Management System Using Cloud Functions 2024 SIGMOD 7.5325527e-05
3,244 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.479122e-05
3,254 LEMP: Fast Retrieval of Large Entries in a Matrix Product 2015 SIGMOD 7.4748207e-05
3,270 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4613275e-05
3,467 Automatic Discovery of Attributes in Relational Databases 2011 SIGMOD 7.2609187e-05
3,511 An Efficient Filter for Approximate Membership Checking 2008 SIGMOD 7.22602e-05
3,516 Approximate Embedding-Based Subsequence Matching of Time Series 2008 SIGMOD 7.2220655e-05
3,540 Scalable Discovery of Best Clusters on Large Graphs 2010 VLDB 7.1983141e-05
3,604 Overlap Set Similarity Joins with Theoretical Guarantees 2018 SIGMOD 7.1548073e-05
3,744 NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic 2010 VLDB 7.0372503e-05
3,774 On the Complexity of Inner Product Similarity Join 2016 PODS 7.0102162e-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.00044967652
171 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027063233
252 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023058622
282 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022250557
350 The Query By Image Content (QBIC) System 1995 SIGMOD 0.0002018411
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016918797
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013710393
2,080 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.058838e-05
2,404 Multidimensional Access Methods: Trees Have Grown Everywhere 1997 VLDB 8.4981451e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,129 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,873 Neighbor-Sensitive Hashing 2016 VLDB
4 5,814 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS
5 2,501 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 578 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,844 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD