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: 8596
Venue: VLDB
Year: 1999
Pagerank: 0.00076824554
Overall Rank: 34 | 99.77%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 125 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
264	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00029950264
399	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00024359304
442	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00023095823
494	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00021769407
537	Fast Time Sequence Indexing for Arbitrary L_p Norms	2000	VLDB	0.00020650291
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
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016
730	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00017443615
740	Distributed Representations of Tuples for Entity Resolution	2018	VLDB	0.00017358024
796	SageDB: A Learned Database System	2019	CIDR	0.00016541749
858	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015833075
996	FREDDY: Fast Word Embeddings in Database Systems	2018	SIGMOD	0.00014729808
1,225	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013182109
1,232	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013133604
1,252	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00013023834
1,293	Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms	2019	VLDB	0.00012749902
1,299	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012712766
1,923	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010079134
1,927	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	0.00010062395
1,977	Towards Effective Partition Management for Large Graphs	2012	SIGMOD	9.8780062e-05
2,077	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.6038296e-05
2,160	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.4037759e-05
2,264	Manu: A Cloud Native Vector Database Management System	2022	VLDB	9.1587362e-05
2,525	ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data	2024	SIGMOD	8.5991468e-05
2,541	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB	8.5710863e-05
2,644	Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science	2018	VLDB	8.3849568e-05
2,681	NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic	2010	VLDB	8.319573e-05
2,842	Semantics-aware Dataset Discovery from Data Lakes with Contextualized Column-based Representation Learning	2023	VLDB	8.0366354e-05
2,969	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7955562e-05
3,019	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.699097e-05
3,182	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.4280768e-05
3,209	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	7.3793885e-05
3,297	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.2549403e-05
3,461	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.0696567e-05
3,612	SingleStore-V: An Integrated Vector Database System in SingleStore	2024	VLDB	6.9177653e-05
3,629	The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art	2019	VLDB	6.8997167e-05
3,779	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7709545e-05
3,780	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	6.7703467e-05
3,826	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	6.7204879e-05
3,869	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	6.6776679e-05
3,917	A Benchmarking Study of Embedding-based Entity Alignment for Knowledge Graphs	2020	VLDB	6.6268463e-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,247	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.3180334e-05
4,273	Similarity Query Processing for High-Dimensional Data	2020	VLDB	6.2932217e-05
4,350	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.2576191e-05
4,396	LEMP: Fast Retrieval of Large Entries in a Matrix Product	2015	SIGMOD	6.215279e-05

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
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
274	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029383266
301	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028396714
331	The Query By Image Content (QBIC) System	1995	SIGMOD	0.00027199905
531	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.0002079072
821	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016232579
1,808	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010476269
1,943	Multidimensional Access Methods: Trees Have Grown Everywhere	1997	VLDB	0.00010009557

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,099	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5429949e-05
5,218	Neighbor-Sensitive Hashing	2016	VLDB	5.6204105e-05
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016
8,759	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	4.4520434e-05
3,019	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.699097e-05
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
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
8,645	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4725847e-05