{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:07Z","timestamp":1781077807243,"version":"3.54.1"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,3,1]],"date-time":"2014-03-01T00:00:00Z","timestamp":1393632000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Sloan and Okawa"},{"name":"BSF","award":["2008477"],"award-info":[{"award-number":["2008477"]}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0747250, CCF-0915893"],"award-info":[{"award-number":["CCF-0747250, CCF-0915893"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2014,3]]},"abstract":"\n We study lower bounds for Locality-Sensitive Hashing (LSH) in the strongest setting: point sets in {0,1}\n d<\/jats:sup>\n under the Hamming distance. Recall that H is said to be an (\n r<\/jats:italic>\n ,\n cr<\/jats:italic>\n ,\n p<\/jats:italic>\n ,\n q<\/jats:italic>\n )-sensitive hash family if all pairs\n x<\/jats:italic>\n ,\n y<\/jats:italic>\n \u2208 {0,1}\n d<\/jats:sup>\n with dist(\n x<\/jats:italic>\n ,\n y<\/jats:italic>\n ) \u2264\n r<\/jats:italic>\n have probability at least\n p<\/jats:italic>\n of collision under a randomly chosen\n h<\/jats:italic>\n \u2208 H, whereas all pairs\n x<\/jats:italic>\n ,\n y<\/jats:italic>\n \u2208 {0, 1}\n d<\/jats:sup>\n with dist(\n x<\/jats:italic>\n ,\n y<\/jats:italic>\n ) \u2265\n cr<\/jats:italic>\n have probability at most\n q<\/jats:italic>\n of collision. Typically, one considers\n d<\/jats:italic>\n \u2192 \u221e, with\n c<\/jats:italic>\n > 1 fixed and\n q<\/jats:italic>\n bounded away from 0.\n <\/jats:p>\n \n For its applications to approximate nearest-neighbor search in high dimensions, the quality of an LSH family H is governed by how small its\n \u03c1<\/jats:italic>\n parameter<\/jats:italic>\n \u03c1<\/jats:italic>\n = ln(1\/\n p<\/jats:italic>\n )\/ln(1\/\n q<\/jats:italic>\n ) is as a function of the parameter\n c<\/jats:italic>\n . The seminal paper of Indyk and Motwani [1998] showed that for each\n c<\/jats:italic>\n \u2265 1, the extremely simple family H = {\n x<\/jats:italic>\n \u21a6\n x<\/jats:italic>\n i<\/jats:sub>\n :\n i<\/jats:italic>\n \u2208 [\n d<\/jats:italic>\n ]} achieves\n \u03c1<\/jats:italic>\n \u2264 1\/\n c<\/jats:italic>\n . The only known lower bound, due to Motwani et al. [2007], is that\n \u03c1<\/jats:italic>\n must be at least (\n e<\/jats:italic>\n 1\/c<\/jats:sup>\n - 1)\/(\n e<\/jats:italic>\n 1\/c<\/jats:sup>\n + 1) \u2265 .46\/\n c<\/jats:italic>\n (minus\n o<\/jats:italic>\n d<\/jats:sub>\n (1)). The contribution of this article is twofold. (1) We show the \u201coptimal\u201d lower bound for\n \u03c1<\/jats:italic>\n : it must be at least 1\/\n c<\/jats:italic>\n (minus\n o<\/jats:italic>\n d<\/jats:sub>\n (1)). Our proof is very simple, following almost immediately from the observation that the noise stability of a boolean function at time\n t<\/jats:italic>\n is a log-convex function of\n t<\/jats:italic>\n . (2) We raise and discuss the following issue: neither the application of LSH to nearest-neighbor search nor the known LSH lower bounds hold as stated if the\n q<\/jats:italic>\n parameter is tiny. Here, \u201ctiny\u201d means\n q<\/jats:italic>\n = 2\n -\u0398(d)<\/jats:sup>\n , a parameter range we believe is natural.\n <\/jats:p>","DOI":"10.1145\/2578221","type":"journal-article","created":{"date-parts":[[2014,4,1]],"date-time":"2014-04-01T13:06:54Z","timestamp":1396357614000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)"],"prefix":"10.1145","volume":"6","author":[{"given":"Ryan","family":"O\u2019Donnell","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yi","family":"Wu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuan","family":"Zhou","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109690"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.5.419"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908981"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242610"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases.","author":"Gionis A.","unstructured":"A. Gionis , P. Indyk , and R. Motwani . 1999. Similarity search in high dimensions via hashing . In Proceedings of the 25th International Conference on Very Large Data Bases. A. Gionis, P. Indyk, and R. Motwani. 1999. Similarity search in high dimensions via hashing. In Proceedings of the 25th International Conference on Very Large Data Bases."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_10_1","volume-title":"Handbook of Discrete and Computational Geometry, Discrete Mathematics and Its Applications","author":"Indyk P.","unstructured":"P. Indyk . 2004. Nearest neighbors in high-dimensional spaces . In Handbook of Discrete and Computational Geometry, Discrete Mathematics and Its Applications , Chapman and Hall\/CRC , 877--892. P. Indyk. 2004. Nearest neighbors in high-dimensional spaces. In Handbook of Discrete and Computational Geometry, Discrete Mathematics and Its Applications, Chapman and Hall\/CRC, 877--892."},{"key":"e_1_2_1_11_1","unstructured":"P. Indyk. 2009. Personal communication. P. Indyk. 2009. Personal communication."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646858"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873695"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109688"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.68"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.3115\/1219840.1219917"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 9th IEEE International Conference on Computer Vision. Citeseer, 750","author":"Shakhnarovich G.","unstructured":"G. Shakhnarovich , P. Viola , and T. Darrell . 2003. Fast pose estimation with parameter-sensitive hashing . In Proceedings of the 9th IEEE International Conference on Computer Vision. Citeseer, 750 . G. Shakhnarovich, P. Viola, and T. Darrell. 2003. Fast pose estimation with parameter-sensitive hashing. In Proceedings of the 9th IEEE International Conference on Computer Vision. Citeseer, 750."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 10th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science","volume":"4619","author":"Terasawa K.","unstructured":"K. Terasawa and Y. Tanaka . 2007. Spherical LSH for approximate nearest neighbor search on unit hypersphere . In Proceedings of the 10th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science , vol. 4619 , Springer-Verlag, Berlin Heidelberg, 27--38. K. Terasawa and Y. Tanaka. 2007. Spherical LSH for approximate nearest neighbor search on unit hypersphere. In Proceedings of the 10th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 4619, Springer-Verlag, Berlin Heidelberg, 27--38."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2578221","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2578221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:49Z","timestamp":1750234189000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2578221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["10.1145\/2578221"],"URL":"https:\/\/doi.org\/10.1145\/2578221","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3]]},"assertion":[{"value":"2013-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}