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)
Incoming Non-self Citations Over Time
Authors
- 1. Yifang Sun (University of New South Wales)
- 2. Wei Wang (University of New South Wales)
- 3. Jianbin Qin (University of New South Wales)
- 4. Ying Zhang (University of Technology Sydney)
- 5. Xuemin Lin (University of New South Wales)
BibTeX Citation
@article{sun_vldb15,
title = {{SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index}},
author = {Sun, Yifang and Wang, Wei and Qin, Jianbin and Zhang, Ying and Lin, Xuemin},
journal = {PVLDB},
series = {{VLDB} '15},
volume = {8},
number = {1},
pages = {1--12},
doi = {10.14778/2735461.2735462},
url = {https://doi.org/10.14778/2735461.2735462},
year = {2015}
}Incoming Citations (Sorted by Pagerank)
Showing 47 of 47 citing papers.
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 21 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00056760516 |
| 46 | A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces | 1998 | VLDB | 0.00044853085 |
| 287 | Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search | 2007 | VLDB | 0.00022323585 |
| 369 | Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting | 2012 | SIGMOD | 0.00019945234 |
| 690 | Efficient Similarity Search and Classification via Rank Aggregation | 2003 | SIGMOD | 0.0001492934 |
| 991 | Bayesian Locality Sensitive Hashing for Fast Similarity Search | 2012 | VLDB | 0.00012793339 |
| 2,390 | Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing | 2013 | VLDB | 8.6438351e-05 |
| 3,217 | Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data | 2002 | SIGMOD | 7.6314544e-05 |
| 6,597 | Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories | 2010 | SIGMOD | 5.8280739e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,666 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS |
| 2 | 3,279 | Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring | 2020 | SIGMOD |
| 3 | 2,158 | What is the nearest neighbor in high dimensional spaces? | 2000 | VLDB |
| 4 | 1,572 | LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index | 2016 | SIGMOD |
| 5 | 581 | Quality and Efficiency in High Dimensional Nearest Neighbor Search | 2009 | SIGMOD |
| 6 | 21 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB |
| 7 | 1,546 | PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search | 2020 | VLDB |
| 8 | 990 | SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search | 2014 | VLDB |
| 9 | 1,934 | Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces | 2023 | VLDB |
| 10 | 332 | Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search | 2016 | VLDB |