{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:36:08Z","timestamp":1750221368307,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,6,16]],"date-time":"2018-06-16T00:00:00Z","timestamp":1529107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council under the European Unions 7th Framework Programme","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}]},{"name":"ERC","award":["614331"],"award-info":[{"award-number":["614331"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,7,31]]},"abstract":"<jats:p>\n            We consider a new construction of locality-sensitive hash functions for Hamming space that is\n            <jats:italic>covering<\/jats:italic>\n            in the sense that is it guaranteed to produce a collision for every pair of vectors within a given radius\n            <jats:italic>r<\/jats:italic>\n            . The construction is\n            <jats:italic>efficient<\/jats:italic>\n            in the sense that the expected number of hash collisions between vectors at distance\u00a0\n            <jats:italic>cr<\/jats:italic>\n            , for a given\n            <jats:italic>c<\/jats:italic>\n            &gt;1, comes close to that of the best possible data independent LSH without the covering guarantee, namely, the seminal LSH construction of Indyk and Motwani (STOC\u201998). The efficiency of the new construction essentially\n            <jats:italic>matches<\/jats:italic>\n            their bound when the search radius is not too large\u2014e.g., when\n            <jats:italic>cr<\/jats:italic>\n            =\n            <jats:italic>o<\/jats:italic>\n            (log (\n            <jats:italic>n<\/jats:italic>\n            )\/ log log\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the number of points in the dataset, and when\n            <jats:italic>cr<\/jats:italic>\n            = log (\n            <jats:italic>n<\/jats:italic>\n            )\/\n            <jats:italic>k<\/jats:italic>\n            , where\n            <jats:italic>k<\/jats:italic>\n            is an integer constant. In general, it differs by at most a factor ln (4) in the exponent of the time bounds. As a consequence, LSH-based similarity search in Hamming space can avoid the problem of false negatives at little or no cost in efficiency.\n          <\/jats:p>","DOI":"10.1145\/3155300","type":"journal-article","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T12:28:11Z","timestamp":1529324891000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["CoveringLSH"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1516-9306","authenticated-orcid":false,"given":"Rasmus","family":"Pagh","sequence":"first","affiliation":[{"name":"IT University of Copenhage, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2018,6,16]]},"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.2015.18"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634150"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039690"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164206"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007374"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856330"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.7169\/facm\/2016.55.2.3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.3180030404"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365720"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646513.695510"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA\u201900)","year":"2000","author":"Indyk Piotr","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","unstructured":"Piotr Indyk. 2015. Personal communication. (2015).  Piotr Indyk. 2015. Personal communication. (2015)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745761"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2005.12"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0195-6698(95)90087-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300004235"},{"volume-title":"Papert","year":"1987","author":"Minsky Marvin L.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2354409.2354813"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578221"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109688"},{"key":"e_1_2_1_27_1","unstructured":"Michal Parnas. 2015. Personal communication. (2015).  Michal Parnas. 2015. Personal communication. (2015)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983742"},{"volume-title":"Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917)","year":"2017","author":"Sankowski Piotr","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155300","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3155300","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:28Z","timestamp":1750213588000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155300"}},"subtitle":["Locality-Sensitive Hashing without False Negatives"],"short-title":[],"issued":{"date-parts":[[2018,6,16]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7,31]]}},"alternative-id":["10.1145\/3155300"],"URL":"https:\/\/doi.org\/10.1145\/3155300","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,6,16]]},"assertion":[{"value":"2016-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}