{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:25:53Z","timestamp":1755998753263,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,1,23]],"date-time":"2022-01-23T00:00:00Z","timestamp":1642896000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Harvard PRISE Fellowship and a Herchel Smith Fellowship"},{"name":"Harvard PRISE Fellowship and a Herchel Smith Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            We show that approximate near neighbor search in high dimensions can be solved in a Las Vegas fashion (i.e., without false negatives) for \u2113\n            <jats:italic>\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            (1\u2264\n            <jats:italic>p<\/jats:italic>\n            \u2264 2) while matching the performance of optimal locality-sensitive hashing. Specifically, we construct a data-independent Las Vegas data structure with query time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>dn<\/jats:italic>\n            <jats:sup>\u03c1<\/jats:sup>\n            ) and space usage\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>dn<\/jats:italic>\n            <jats:sup>1+\u03c1<\/jats:sup>\n            ) for (\n            <jats:italic>r, c r<\/jats:italic>\n            )-approximate near neighbors in R\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            under the \u2113\n            <jats:italic>\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            norm, where \u03c1 = 1\/\n            <jats:italic>\n              c\n              <jats:sup>p<\/jats:sup>\n            <\/jats:italic>\n            +\n            <jats:italic>o<\/jats:italic>\n            (1). Furthermore, we give a Las Vegas locality-sensitive filter construction for the unit sphere that can be used with the data-dependent data structure of Andoni et\u00a0al. (SODA 2017) to achieve optimal space-time tradeoffs in the data-dependent setting. For the symmetric case, this gives us a data-dependent Las Vegas data structure with query time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>dn<\/jats:italic>\n            <jats:sup>\u03c1<\/jats:sup>\n            ) and space usage\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>dn<\/jats:italic>\n            <jats:sup>1+\u03c1<\/jats:sup>\n            ) for (\n            <jats:italic>r, c r<\/jats:italic>\n            )-approximate near neighbors in R\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            under the \u2113\n            <jats:italic>\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            norm, where \u03c1 = 1\/(2\n            <jats:italic>\n              c\n              <jats:sup>p<\/jats:sup>\n            <\/jats:italic>\n            - 1) +\n            <jats:italic>o<\/jats:italic>\n            (1).\n          <\/jats:p>\n          <jats:p>\n            Our data-independent construction improves on the recent Las Vegas data structure of Ahle (FOCS 2017) for \u2113\n            <jats:italic>\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            when 1 &lt;\n            <jats:italic>p<\/jats:italic>\n            \u2264 2. Our data-dependent construction performs even better for \u2113\n            <jats:italic>\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            for all p\u03b5 [1, 2] and is the first Las Vegas approximate near neighbors data structure to make use of data-dependent approaches. We also answer open questions of Indyk (SODA 2000), Pagh (SODA 2016), and Ahle by showing that for approximate near neighbors, Las Vegas data structures can match state-of-the-art Monte Carlo data structures in performance for both the data-independent and data-dependent settings and across space-time tradeoffs.\n          <\/jats:p>","DOI":"10.1145\/3461777","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T05:51:05Z","timestamp":1643003465000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Las Vegas Approximate Near Neighbors in\n            <i>\n              \u2113\n              <sub>p<\/sub>\n            <\/i>"],"prefix":"10.1145","volume":"18","author":[{"given":"Alexander","family":"Wei","sequence":"first","affiliation":[{"name":"UC Berkeley, Soda Hall, Berkeley, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,1,23]]},"reference":[{"volume-title":"It is NP-hard to Verify an LSF on the Sphere","year":"2017","author":"Ahle Thomas Dybdahl","key":"e_1_3_3_2_2"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.91"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/060673096"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a015"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150334.1150336"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.49"},{"volume-title":"Handbook of Discrete and Computational Geometry","year":"2017","author":"Andoni Alexandr","key":"e_1_3_3_8_2"},{"key":"e_1_3_3_9_2","first-page":"1225","volume-title":"Advances in Neural Information Processing Systems 28","author":"Andoni Alexandr","year":"2015"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.76"},{"key":"e_1_3_3_11_2","article-title":"Approximate nearest neighbor search in high dimensions","volume":"1806","author":"Andoni Alexandr","year":"2018","journal-title":"CoRR"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.4"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_3_3_14_2","first-page":"Article 9, 11 p","volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry (SoCG\u201916)","author":"Andoni Alexandr","year":"2016"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164206"},{"key":"e_1_3_3_16_2","doi-asserted-by":"crossref","unstructured":"Anja Becker L\u00e9o Ducas Nicolas Gama and Thijs Laarhoven. 2016. New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916) . 10\u201324. DOI:https:\/\/doi.org\/10.1137\/1.9781611974331.ch2","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00031-7"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.3"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055443"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217052"},{"key":"e_1_3_3_22_2","first-page":"Article 15, 9 p","volume-title":"Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA\u201918)","author":"Cohen Michael B.","year":"2018"},{"key":"e_1_3_3_23_2","first-page":"Article 11, 14","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Cohen Michael B.","year":"2016"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.17"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_3_29_2","first-page":"371","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Indyk Piotr","year":"2000"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_3_3_31_2","first-page":"Article 52, 17","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Karppa Matti","year":"2016"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798347177"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1057"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/050646858"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492475"},{"volume-title":"Algorithms for High Dimensional Data","year":"2014","author":"Nguyen Huy L.","key":"e_1_3_3_36_2"},{"issue":"1","key":"e_1_3_3_37_2","first-page":"Article 5, 13 p","article-title":"Optimal lower bounds for locality-sensitive hashing (except when q is tiny)","volume":"6","author":"O\u2019Donnell Ryan","year":"2014","journal-title":"ACM Trans. Comput. Theory"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch1"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983742"},{"key":"e_1_3_3_40_2","first-page":"Article 63, 12","volume-title":"Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917)","author":"Sankowski Piotr","year":"2017"},{"key":"e_1_3_3_41_2","article-title":"Improved approximate near neighbor search without false negatives for  \\ell _2","volume":"1709","author":"Wygocki Piotr","year":"2017","journal-title":"CoRR"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3461777","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3461777","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:06Z","timestamp":1750191426000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3461777"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,23]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3461777"],"URL":"https:\/\/doi.org\/10.1145\/3461777","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,1,23]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}