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: 10981
Venue: VLDB
Year: 2015
Pagerank: 0.00015833075
Overall Rank: 858 | 94.04%
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
596	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00019455943
1,013	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014632051
1,252	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00013023834
1,934	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00010047294
1,966	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.9130791e-05
2,160	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.4037759e-05
2,287	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	9.1004806e-05
2,434	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	8.8225986e-05
2,687	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.3079951e-05
2,772	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	8.1491893e-05
3,182	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.4280768e-05
3,403	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	7.1338786e-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
4,230	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.3337893e-05
4,273	Similarity Query Processing for High-Dimensional Data	2020	VLDB	6.2932217e-05
4,551	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	6.0864316e-05
4,600	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	6.0528015e-05
4,622	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	6.0356382e-05
4,869	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	5.8588434e-05
5,186	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	5.6352814e-05
5,218	Neighbor-Sensitive Hashing	2016	VLDB	5.6204105e-05
5,236	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	5.6077913e-05
5,577	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.423881e-05
6,000	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.2365238e-05
6,080	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	5.219249e-05
6,359	High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings	2020	SIGMOD	5.0912204e-05
6,375	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0868008e-05
7,090	Dumpy: A Compact and Adaptive Index for Large Data Series Collections	2023	SIGMOD	4.8318862e-05
7,198	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB	4.79852e-05
7,235	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	4.7882389e-05
7,698	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	4.6699546e-05
7,827	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.6379617e-05
7,848	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	4.6323445e-05
8,208	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	4.5537353e-05
8,239	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	4.5471319e-05
9,821	DIDS: Double Indices and Double Summarizations for Fast Similarity Search	2024	VLDB	4.2716118e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.1905499e-05
10,124	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	4.1905499e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,166	FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,237	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.1905499e-05
10,260	JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search	2026	VLDB	4.1905499e-05
10,610	Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates	2025	VLDB	4.1905499e-05
10,711	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1905499e-05
11,415	ONe Index for All Kernels (ONIAK): A Zero Re-Indexing LSH Solution to ANNS-ALT (After Linear Transformation)	2022	VLDB	4.1905499e-05
11,545	Fast Algorithm for Anchor Graph Hashing	2021	VLDB	4.1905499e-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.00076824554
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
399	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00024359304
579	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.0001982328
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016
1,299	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012712766
2,872	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB	7.9797548e-05
3,278	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2858181e-05
6,388	Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories	2010	SIGMOD	5.079988e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,759	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	4.4520434e-05
4,230	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.3337893e-05
2,099	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5429949e-05
1,966	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.9130791e-05
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
2,160	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.4037759e-05
1,225	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013182109
2,969	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7955562e-05
596	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00019455943