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 48 of 48 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 |
|---|---|---|---|---|
| 20 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.0005758001 |
| 45 | A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces | 1998 | VLDB | 0.00045027197 |
| 278 | Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search | 2007 | VLDB | 0.00022310642 |
| 338 | Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting | 2012 | SIGMOD | 0.00020600264 |
| 674 | Efficient Similarity Search and Classification via Rank Aggregation | 2003 | SIGMOD | 0.00014886449 |
| 990 | Bayesian Locality Sensitive Hashing for Fast Similarity Search | 2012 | VLDB | 0.00012643446 |
| 2,363 | Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing | 2013 | VLDB | 8.572554e-05 |
| 3,254 | Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data | 2002 | SIGMOD | 7.487573e-05 |
| 6,650 | Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories | 2010 | SIGMOD | 5.7201875e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,798 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS |
| 2 | 2,955 | Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring | 2020 | SIGMOD |
| 3 | 2,114 | What is the nearest neighbor in high dimensional spaces? | 2000 | VLDB |
| 4 | 1,527 | LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index | 2016 | SIGMOD |
| 5 | 576 | Quality and Efficiency in High Dimensional Nearest Neighbor Search | 2009 | SIGMOD |
| 6 | 20 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB |
| 7 | 1,481 | PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search | 2020 | VLDB |
| 8 | 927 | SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search | 2014 | VLDB |
| 9 | 1,618 | Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces | 2023 | VLDB |
| 10 | 297 | Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search | 2016 | VLDB |