SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index

Summary: Introduces c-ANN methods for high-dimensional Euclidean space using a single tiny index, beating LSH on space. Provides probabilistic guarantees, supports exact NN at a user-defined probability, and scales to 1B points on commodity hardware. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10980
Venue: VLDB
Year: 2015
Pagerank: 0.00015792021
Overall Rank: 867 | 93.98%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 46 of 46 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
562	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020091752
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
1,269	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00012930432
1,757	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00010660932
1,971	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.893198e-05
2,181	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.3451821e-05
2,324	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	9.0326444e-05
2,435	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	8.8252237e-05
2,725	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.2294908e-05
2,811	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	8.0806307e-05
3,225	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.3463484e-05
3,400	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	7.1405533e-05
3,629	The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art	2019	VLDB	6.902069e-05
4,243	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.32976e-05
4,278	Similarity Query Processing for High-Dimensional Data	2020	VLDB	6.2953764e-05
4,551	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	6.092287e-05
4,598	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	6.0586236e-05
4,731	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	5.966659e-05
5,184	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	5.6406991e-05
5,224	Neighbor-Sensitive Hashing	2016	VLDB	5.6197981e-05
5,233	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	5.6131833e-05
5,456	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	5.4976692e-05
5,569	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.4290942e-05
5,996	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.2415551e-05
6,074	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	5.2242306e-05
6,360	High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings	2020	SIGMOD	5.0961051e-05
6,376	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0916875e-05
7,095	Dumpy: A Compact and Adaptive Index for Large Data Series Collections	2023	SIGMOD	4.8350023e-05
7,204	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	4.8015761e-05
7,239	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	4.792836e-05
7,700	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	4.6744372e-05
7,843	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	4.6367909e-05
8,175	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.5676289e-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
9,822	DIDS: Double Indices and Double Summarizations for Fast Similarity Search	2024	VLDB	4.2757088e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.1945683e-05
10,124	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	4.1945683e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
10,166	FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
10,237	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.1945683e-05
10,260	JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search	2026	VLDB	4.1945683e-05
10,602	Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates	2025	VLDB	4.1945683e-05
10,703	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1945683e-05
11,412	ONe Index for All Kernels (ONIAK): A Zero Re-Indexing LSH Solution to ANNS-ALT (After Linear Transformation)	2022	VLDB	4.1945683e-05
11,541	Fast Algorithm for Anchor Graph Hashing	2021	VLDB	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
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
400	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002427237
605	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.000193396
709	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017768547
1,305	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012687101
2,870	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB	7.9799783e-05
3,275	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2897998e-05
6,399	Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories	2010	SIGMOD	5.0818596e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,763	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	4.456315e-05
4,243	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.32976e-05
2,107	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5330494e-05
1,971	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.893198e-05
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
2,181	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.3451821e-05
1,229	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013157271
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
562	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020091752