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

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 124 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,731	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	5.966659e-05
4,808	On the Complexity of Inner Product Similarity Join	2016	PODS	5.908896e-05
4,862	Vexless: A Serverless Vector Data Management System Using Cloud Functions	2024	SIGMOD	5.8707776e-05
5,179	SilkMoth: An Efficient Method for Finding Related Sets with Maximum Matching Constraints	2017	VLDB	5.6428428e-05
5,224	Neighbor-Sensitive Hashing	2016	VLDB	5.6197981e-05
5,433	"Amnesia" - A Selection of Machine Learning Models That Can Forget User Data Very Fast	2020	CIDR	5.5051607e-05
5,469	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	5.4898192e-05
5,536	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	5.4532734e-05
5,622	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	5.4060403e-05
5,707	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	5.3611041e-05
6,074	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	5.2242306e-05
6,082	Query-Sensitive Embeddings	2005	SIGMOD	5.2205711e-05
6,376	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0916875e-05
6,399	Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories	2010	SIGMOD	5.0818596e-05
6,547	Flexible Aggregate Similarity Search	2011	SIGMOD	5.0183532e-05
7,204	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	4.8015761e-05
7,215	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	4.7985991e-05
7,316	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	4.7640297e-05
7,522	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD	4.7180617e-05
7,606	Tribase: A Vector Data Query Engine for Reliable and Lossless Pruning Compression using Triangle Inequalities	2025	SIGMOD	4.6967106e-05
7,635	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	4.6908858e-05
7,654	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	4.687476e-05
7,669	Incorporating String Transformations in Record Matching	2008	SIGMOD	4.6833751e-05
7,700	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	4.6744372e-05
7,837	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	4.6379694e-05
7,843	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	4.6367909e-05
8,137	Customizable and Scalable Fuzzy Join for Big Data	2019	VLDB	4.5774794e-05
8,175	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.5676289e-05
8,193	WarpGate: A Semantic Join Discovery System for Cloud Data Warehouses	2023	CIDR	4.5618596e-05
8,209	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	4.5581054e-05
8,245	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	4.5514956e-05
8,375	Fast Neural Ranking on Bipartite Graph Indices	2022	VLDB	4.5326207e-05
8,635	Bidirectionally Densifying LSH Sketches with Empty Bins	2021	SIGMOD	4.4801584e-05
8,693	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.466142e-05
8,712	ANN Softmax: Acceleration of Extreme Classification Training	2022	VLDB	4.4626362e-05
8,763	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	4.456315e-05
8,889	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB	4.4278238e-05
8,997	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	4.4120041e-05
9,025	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4072367e-05
9,096	Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases	2008	VLDB	4.3974472e-05
9,100	Who Tags What? An Analysis Framework	2012	VLDB	4.3965818e-05
9,283	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB	4.3631652e-05
9,460	The Battleship Approach to the Low Resource Entity Matching Problem	2023	SIGMOD	4.3366491e-05
10,022	In-context Clustering-based Entity Resolution with Large Language Models: A Design Space Exploration	2026	SIGMOD	4.1945683e-05
10,039	VecFlow: A High-Performance Vector Data Management System for Filtered-Search on GPUs	2026	SIGMOD	4.1945683e-05
10,073	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.1945683e-05
10,141	Honeybee: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning	2026	SIGMOD	4.1945683e-05
10,146	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,150	Curator: Efficient Vector Search with Low-Selectivity Filters	2026	SIGMOD	4.1945683e-05
10,160	Efficient Vector Index Merging in Vector Databases	2026	SIGMOD	4.1945683e-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
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028994728
330	The Query By Image Content (QBIC) System	1995	SIGMOD	0.00027229588
530	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00020803682
825	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016228517
1,811	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010467197
1,945	Multidimensional Access Methods: Trees Have Grown Everywhere	1997	VLDB	0.00010001003

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,107	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5330494e-05
5,224	Neighbor-Sensitive Hashing	2016	VLDB	5.6197981e-05
709	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017768547
8,763	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	4.456315e-05
867	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015792021
3,056	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.6432146e-05
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
8,647	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4768766e-05