On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space
Summary: Adversarial robustness of LSH in Hamming space under adaptive queries. The adversary, under mild dataset assumptions, provably finds hard queries that break the approximate NN structure, exponentially faster than random sampling. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Michael Kapralov (EPFL)
- 2. Mikhail Makarov (EPFL)
- 3. Christian Sohler (University of Cologne)
BibTeX Citation
@inproceedings{kapralov_pods25,
address = {New York, NY, USA},
series = {{PODS} '25},
title = {{On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space}},
url = {https://dl.acm.org/doi/10.1145/3725239},
doi = {10.1145/3725239},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Kapralov, Michael and Makarov, Mikhail and Sohler, Christian},
year = {2025}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 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 |
| 4,211 | The Adversarial Robustness of Sampling | 2020 | PODS | 6.8299006e-05 |
| 4,291 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.7786745e-05 |
| 5,666 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS | 6.1285141e-05 |
| 6,583 | Distance-Sensitive Hashing | 2018 | PODS | 5.8359922e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 580 | SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index | 2015 | VLDB |
| 2 | 11,751 | On the I/O Complexity of the k-Nearest Neighbors Problem | 2020 | PODS |
| 3 | 9,493 | MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances | 2023 | VLDB |
| 4 | 5,666 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS |
| 5 | 3,279 | Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring | 2020 | SIGMOD |
| 6 | 369 | Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting | 2012 | SIGMOD |
| 7 | 3,389 | Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond | 2017 | VLDB |
| 8 | 332 | Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search | 2016 | VLDB |
| 9 | 6,583 | Distance-Sensitive Hashing | 2018 | PODS |
| 10 | 4,927 | Neighbor-Sensitive Hashing | 2016 | VLDB |