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

1. Aristides Gionis (Stanford University)
2. Piotr Indyk (Stanford University)
3. Rajeev Motwani (Stanford University)

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 29 of 129 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,318	In-context Clustering-based Entity Resolution with Large Language Models: A Design Space Exploration	2026	SIGMOD	5.093636e-05
10,333	VecFlow: A High-Performance Vector Data Management System for Filtered-Search on GPUs	2026	SIGMOD	5.093636e-05
10,364	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	5.093636e-05
10,430	Honeybee: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning	2026	SIGMOD	5.093636e-05
10,435	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	5.093636e-05
10,439	Curator: Efficient Vector Search with Low-Selectivity Filters	2026	SIGMOD	5.093636e-05
10,449	Efficient Vector Index Merging in Vector Databases	2026	SIGMOD	5.093636e-05
10,456	FlashANNS: GPU-Driven Asynchronous I/O Pipelining for Eliminating Storage-Compute Bottlenecks in Billion-Scale Similarity Search	2026	SIGMOD	5.093636e-05
10,525	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	5.093636e-05
10,548	JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search	2026	VLDB	5.093636e-05
10,563	Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search	2026	VLDB	5.093636e-05
10,571	An Experimental Evaluation of Hybrid Querying on Vectors	2026	VLDB	5.093636e-05
10,601	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	5.093636e-05
11,149	Similarity Joins of Sparse Features	2024	SIGMOD	5.093636e-05
11,232	SeLeP: Learning Based Semantic Prefetching for Exploratory Database Workloads	2024	VLDB	5.093636e-05
11,274	Partition, Don’t Sort! Compression Boosters for Cloud Data Ingestion Pipelines	2024	VLDB	5.093636e-05
11,374	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS	5.093636e-05
11,376	Unsupervised Hashing with Semantic Concept Mining	2023	SIGMOD	5.093636e-05
11,576	Interactive Mining with Ordered and Unordered Attributes	2022	VLDB	5.093636e-05
11,643	Learning Algorithms for Automatic Data Structure Design	2021	SIGMOD	5.093636e-05
11,738	Fast Algorithm for Anchor Graph Hashing	2021	VLDB	5.093636e-05
11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	5.093636e-05
12,280	Efficiency and Security in Similarity Cloud Services	2013	VLDB	5.093636e-05
12,288	QuEval: Beyond high-dimensional indexing à la carte	2013	VLDB	5.093636e-05
12,371	Effective Data Co-Reduction for Multimedia Similarity Search	2011	SIGMOD	5.093636e-05
12,488	Similarity Caching	2009	PODS	5.093636e-05
12,550	The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects	2008	PODS	5.093636e-05
12,714	Indexing for Function Approximation	2006	VLDB	5.093636e-05
12,803	AIMS: An Immersidata Management System	2003	CIDR	5.093636e-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
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

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