{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T13:41:58Z","timestamp":1765806118839,"version":"3.44.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>\n            Locality-sensitive hashing (Indyk-Motwani'98) is a classical data structure for approximate nearest neighbor search. It allows, after a close to linear time preprocessing of the input dataset, to find an approximately nearest neighbor of any fixed query in sublinear time in the dataset size. The resulting data structure is randomized and succeeds with high probability for every fixed query independent of the randomness of the data structure. In many modern applications of nearest neighbor search the queries are, however, chosen\n            <jats:italic toggle=\"yes\">adaptively.<\/jats:italic>\n            In this paper, we study the robustness of locality-sensitive hashing in Hamming space to adaptive queries. We present a simple adversary that can, under mild assumptions on the initial point set, provably find a query to the approximate near neighbor search data structure that the data structure fails on. Crucially, our adaptive algorithm finds the hard query exponentially faster than random sampling.\n          <\/jats:p>","DOI":"10.1145\/3725239","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-24","source":"Crossref","is-referenced-by-count":1,"title":["On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-2882-0459","authenticated-orcid":false,"given":"Michael","family":"Kapralov","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-2425-1723","authenticated-orcid":false,"given":"Mikhail","family":"Makarov","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8990-3326","authenticated-orcid":false,"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[{"name":"University of Cologne, Cologne, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.91"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_2_1_3_1","volume-title":"Practical and Optimal LSH for Angular Distance. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015","author":"Andoni Alexandr","year":"2015","unstructured":"Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015. Practical and Optimal LSH for Angular Distance. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7--12, 2015, Montreal, Quebec, Canada, Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (Eds.). 1225--1233. https:\/\/proceedings.neurips.cc\/paper\/2015\/hash\/2823f4797102ce1a1aec05359cc16dd9-Abstract.html"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.76"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2023.8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196976"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520064"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498334"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387643"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Jack Breese David Heckerman and Carl Kadie. 1998. Anonymous Microsoft Web Data. UCI Machine Learning Repository. DOI: https:\/\/doi.org\/10.24432\/C5VS3Q.","DOI":"10.24432\/C5VS3Q"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_2_1_14_1","volume-title":"On Adaptive Distance Estimation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Cherapanamjeri Yeshwanth","year":"2020","unstructured":"Yeshwanth Cherapanamjeri and Jelani Nelson. 2020. On Adaptive Distance Estimation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6--12, 2020, virtual, Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/803ef56843860e4a48fc4cdb3065e8ce-Abstract.html"},{"key":"e_1_2_1_15_1","volume-title":"The Eleventh International Conference on Learning Representations, ICLR 2023","author":"Cherapanamjeri Yeshwanth","year":"2023","unstructured":"Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou. 2023. Robust Algorithms on Adaptive Inputs from Bounded Adversaries. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1--5, 2023. OpenReview.net. https:\/\/openreview.net\/forum?id=I29Kt0RwChs"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.3"},{"key":"e_1_2_1_17_1","volume-title":"International Conference on Machine Learning, ICML 2022","volume":"4140","author":"Cohen Edith","year":"2022","unstructured":"Edith Cohen, Xin Lyu, Jelani Nelson, Tam\u00e1s Sarl\u00f3s, Moshe Shechner, and Uri Stemmer. 2022. On the Robustness of CountSketch to Adaptive Inputs. In International Conference on Machine Learning, ICML 2022, 17--23 July 2022, Baltimore, Maryland, USA (Proceedings of Machine Learning Research, Vol. 162), Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesv\u00e1ri, Gang Niu, and Sivan Sabato (Eds.). PMLR, 4112--4140. https:\/\/proceedings.mlr.press\/v162\/cohen22a.html"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V37I6.25882"},{"key":"e_1_2_1_19_1","volume-title":"Mathias B\u00e6k Tejs Knudsen, and Mikkel Thorup","author":"Dahlgaard S\u00f8ren","year":"2017","unstructured":"S\u00f8ren Dahlgaard, Mathias B\u00e6k Tejs Knudsen, and Mikkel Thorup. 2017. Practical Hash Functions for Similarity Estimation and Dimensionality Reduction. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4--9, 2017, Long Beach, CA, USA, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds.). 6615--6625. https:\/\/proceedings.neurips.cc\/paper\/2017\/hash\/62dad6e273d32235ae02b7d321578ee8-Abstract.html"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00136"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488624"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3556972"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_25_1","volume-title":"Khandker Mushfiqul Islam, and Chidambaram Crushev","author":"Jafari Omid","year":"2021","unstructured":"Omid Jafari, Preeti Maurya, Parth Nagarkar, Khandker Mushfiqul Islam, and Chidambaram Crushev. 2021. A survey on locality sensitive hashing algorithms and their applications. arXiv preprint arXiv:2102.08942 (2021)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745761"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2017.53"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-006-0027-5"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798347177"},{"key":"e_1_2_1_30_1","unstructured":"Yann LeCun. 1998. The MNIST database of handwritten digits. http:\/\/yann.lecun.com\/exdb\/mnist\/ (1998)."},{"key":"e_1_2_1_31_1","volume-title":"Art B. Owen, and Cun-Hui Zhang","author":"Li Ping","year":"2012","unstructured":"Ping Li, Art B. Owen, and Cun-Hui Zhang. 2012. One Permutation Hashing. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3--6, 2012, Lake Tahoe, Nevada, United States, Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C. Burges, L\u00e9on Bottou, and Kilian Q. Weinberger (Eds.). 3122--3130. https:\/\/proceedings.neurips.cc\/paper\/2012\/hash\/eaa32c96f620053cf442ad32258076b9-Abstract.html"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--32512-0_53"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109688"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2008.4518093"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","unstructured":"UC Irvine Machine Learning Repository 1987. Mushroom. UCI Machine Learning Repository. DOI: https:\/\/doi.org\/10.24432\/C5959T.","DOI":"10.24432\/C5959T"},{"key":"e_1_2_1_37_1","volume-title":"VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24--27","author":"Schek Hans-J\u00f6rg","year":"1998","unstructured":"RogerWeber, Hans-J\u00f6rg Schek, and Stephen Blott. 1998. A Quantitative Analysis and Performance Study for Similarity- Search Methods in High-Dimensional Spaces. In VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24--27, 1998, New York City, New York, USA, Ashish Gupta, Oded Shmueli, and Jennifer Widom (Eds.). Morgan Kaufmann, 194--205. http:\/\/www.vldb.org\/conf\/1998\/p194.pdf"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461777"},{"key":"e_1_2_1_39_1","volume-title":"The Thirty-eighth Annual Conference on Neural Information Processing Systems.","author":"Woodruff David","year":"2024","unstructured":"David Woodruff and Samson Zhou. 2024. Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. In The Thirty-eighth Annual Conference on Neural Information Processing Systems."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00116"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Barry L Wulff. 1982. The Audubon Society Field Guide to North American Mushrooms by Gary Lincoff.","DOI":"10.2307\/4447563"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2015.11.018"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:19:02Z","timestamp":1755904742000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725239"],"URL":"https:\/\/doi.org\/10.1145\/3725239","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}