{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T08:27:15Z","timestamp":1773304035930,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-0910940"],"award-info":[{"award-number":["CCF-0910940"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,11,2]]},"abstract":"<jats:p>Locality sensitive hashing (LSH) is a key algorithmic tool that is widely used both in theory and practice. An important goal in the study of LSH is to understand which similarity functions admit an LSH, that is, are LSHable. In this article, we focus on the class of transformations such that given any similarity that is LSHable, the transformed similarity will continue to be LSHable. We show a tight characterization of all such LSH-preserving transformations: they are precisely the probability generating functions, up to scaling.<\/jats:p>\n          <jats:p>\n            As a concrete application of this result, we study which set similarity measures are LSHable. We obtain a complete characterization of similarity measures between two sets\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            that are ratios of two linear functions of \u2223\n            <jats:italic>A<\/jats:italic>\n            \u2229\n            <jats:italic>B<\/jats:italic>\n            \u2223, \u2223\n            <jats:italic>A<\/jats:italic>\n            \u25b5\n            <jats:italic>B<\/jats:italic>\n            \u2223, \u2223\n            <jats:italic>A<\/jats:italic>\n            \u222a\n            <jats:italic>B<\/jats:italic>\n            \u2223: such a measure is LSHable if and only if its corresponding distance is a metric. This result generalizes the well-known LSH for the Jaccard set similarity, namely, the minwise-independent permutations, and obtains LSHs for many set similarity measures that are used in practice. Using our main result, we obtain a similar characterization for set similarities involving radicals.\n          <\/jats:p>","DOI":"10.1145\/2816813","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T17:09:35Z","timestamp":1446484175000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["LSH-Preserving Functions and Their Applications"],"prefix":"10.1145","volume":"62","author":[{"given":"Flavio","family":"Chierichetti","sequence":"first","affiliation":[{"name":"Sapienza University, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Google, Mountain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-003-0418-7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"G. E. Andrews R. Askey and R. Roy. 1999. Special Functions. Cambridge University Press.  G. E. Andrews R. Askey and R. Roy. 1999. Special Functions. Cambridge University Press.","DOI":"10.1017\/CBO9781107325937"},{"key":"e_1_2_1_5_1","first-page":"649","article-title":"Produit tensoriel, distances extr\u00e9males et r\u00e9alisation de covariances","volume":"288","author":"Assouad P.","year":"1979","unstructured":"P. Assouad . 1979 . Produit tensoriel, distances extr\u00e9males et r\u00e9alisation de covariances . Compt\u00e9s Rendus de l'Acad\u00e9mie des Sciences de Paris 288 (1979), 649 -- 652 , 675--677. P. Assouad. 1979. Produit tensoriel, distances extr\u00e9males et r\u00e9alisation de covariances. Compt\u00e9s Rendus de l'Acad\u00e9mie des Sciences de Paris 288 (1979), 649--652, 675--677.","journal-title":"Compt\u00e9s Rendus de l'Acad\u00e9mie des Sciences de Paris"},{"key":"e_1_2_1_6_1","volume-title":"S\u00e9minaire Choquet (Initiation \u00e1 l'Analyse)","author":"Assouad P.","unstructured":"P. Assouad . 1980. Plongements isom\u00e9triques dans &ell;1: Aspect analytique . In S\u00e9minaire Choquet (Initiation \u00e1 l'Analyse) , Vol. 14 . Universite' Paris VI , 1--23. P. Assouad. 1980. Plongements isom\u00e9triques dans &ell;1: Aspect analytique. In S\u00e9minaire Choquet (Initiation \u00e1 l'Analyse), Vol. 14. Universite' Paris VI, 1--23."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01563654"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Compression and Complexity of Sequences (SEQUENCES). IEEE Computer Society, 21--29","author":"Broder A.","year":"1997","unstructured":"A. Broder . 1997 . On the resemblance and containment of documents . In Proceedings of the Compression and Complexity of Sequences (SEQUENCES). IEEE Computer Society, 21--29 . A. Broder. 1997. On the resemblance and containment of documents. In Proceedings of the Compression and Complexity of Sequences (SEQUENCES). IEEE Computer Society, 21--29."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00031-7"},{"key":"e_1_2_1_11_1","volume-title":"\u00dcber den variabilit\u00e4tsbereich der fourierschen konstanten von positiven harmonischen funktionen. Rendiconti del Circolo Matematico di Palermo 32, 1","author":"Carath\u00e9odory C.","year":"1911","unstructured":"C. Carath\u00e9odory . 1911. \u00dcber den variabilit\u00e4tsbereich der fourierschen konstanten von positiven harmonischen funktionen. Rendiconti del Circolo Matematico di Palermo 32, 1 ( 1911 ), 193--217. DOI:http:\/\/dx.doi.org\/10.1007\/BF03014795 10.1007\/BF03014795 C. Carath\u00e9odory. 1911. \u00dcber den variabilit\u00e4tsbereich der fourierschen konstanten von positiven harmonischen funktionen. Rendiconti del Circolo Matematico di Palermo 32, 1 (1911), 193--217. DOI:http:\/\/dx.doi.org\/10.1007\/BF03014795"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1078--1094","author":"Chierichetti F.","unstructured":"F. Chierichetti and R. Kumar . 2012. LSH-preserving functions and their applications . In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1078--1094 . F. Chierichetti and R. Kumar. 2012. LSH-preserving functions and their applications. In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1078--1094."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"M. M. Deza and M. Laurent. 1997. Geometry of Cuts and Metrics. Springer-Verlag Berlin.  M. M. Deza and M. Laurent. 1997. Geometry of Cuts and Metrics. Springer-Verlag Berlin.","DOI":"10.1007\/978-3-642-04295-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2686-4_8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01896809"},{"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\/258533.258656"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000791.2000795"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/1968466"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1938-1501980-0"},{"key":"e_1_2_1_24_1","volume-title":"The Laplace Transform","author":"Widder D. V.","unstructured":"D. V. Widder . 1946. The Laplace Transform . Princeton University Press , Princeton, NJ . D. V. Widder. 1946. The Laplace Transform. Princeton University Press, Princeton, NJ."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2816813","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2816813","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:19Z","timestamp":1750225699000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2816813"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":22,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,11,2]]}},"alternative-id":["10.1145\/2816813"],"URL":"https:\/\/doi.org\/10.1145\/2816813","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2013-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}