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)

Paper ID: 1973
Venue: PODS
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,351 | 27.99%
DOI: 10.1145/3725239

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
4,172	The Adversarial Robustness of Sampling	2020	PODS	6.3879072e-05
4,403	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.2194225e-05
8,763	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	4.456315e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
867	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015792021
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05
9,303	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB	4.358026e-05
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
605	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.000193396
3,938	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB	6.6155909e-05
562	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020091752
5,224	Neighbor-Sensitive Hashing	2016	VLDB	5.6197981e-05