{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:07:37Z","timestamp":1779131257861,"version":"3.51.4"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T00:00:00Z","timestamp":1779062400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["2212629"],"award-info":[{"award-number":["2212629"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    The all-pair near-duplicate text alignment problem aims to identify all pairs of similar subsequences (i.e., contiguous token spans) between two long texts. This problem is central to many applications, including large-scale text deduplication, plagiarism detection, and bioinformatics. Given two input texts T and S, each represented as a sequence of tokens, the naive approach that compares every pair of subsequences between T and S is computationally infeasible, requiring\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (|T|\n                    <jats:sup>2<\/jats:sup>\n                    |S|\n                    <jats:sup>2<\/jats:sup>\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    ) time even when estimating Jaccard similarity via min-hash with\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    independent hash functions. To overcome this limitation, we propose an efficient framework based on Locality-Sensitive Hashing (LSH), which employs\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    \u00d7\n                    <jats:italic toggle=\"yes\">L<\/jats:italic>\n                    independent hash functions organized into\n                    <jats:italic toggle=\"yes\">L<\/jats:italic>\n                    hash tables of\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    hash functions each. Our key observation is that many subsequences in a text share identical LSH values, allowing us to group them by their LSH values. We prove that the expected number of such groups for a text of length\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    is\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">nmL<\/jats:italic>\n                    ). We further design a data structure to represent each group in\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (1) space. As a result, we develop an algorithm that reduces the expected time and space complexities of all-pair near-duplicate text alignment to\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    ((|T|+|S|)\n                    <jats:italic toggle=\"yes\">mL<\/jats:italic>\n                    ), excluding the cost of outputting the pairs. This is significantly lower than the naive approach using the same number\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    =\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    \u00d7\n                    <jats:italic toggle=\"yes\">L<\/jats:italic>\n                    of hash functions. Experiments on large real-world datasets show an order of magnitude speedups over state-of-the-art baselines while maintaining comparable alignment accuracy.\n                  <\/jats:p>","DOI":"10.1145\/3802083","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["LSHAlign: All-Pair Near-Duplicate Text Alignment via Locality-Sensitive Hashing"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3798-0140","authenticated-orcid":false,"given":"Yuheng","family":"Zhang","sequence":"first","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4182-0075","authenticated-orcid":false,"given":"Zhencan","family":"Peng","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8374-140X","authenticated-orcid":false,"given":"Miao","family":"Qiao","sequence":"additional","affiliation":[{"name":"University of Auckland, Auckland, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1417-7995","authenticated-orcid":false,"given":"Wei","family":"Zhang","sequence":"additional","affiliation":[{"name":"Alibaba Cloud Computing, Hangzhou, Zhejiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0770-5775","authenticated-orcid":false,"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Cloud Computing, Hangzhou, Zhejiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4596-3850","authenticated-orcid":false,"given":"Dong","family":"Deng","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80360-2"},{"key":"e_1_2_1_2_1","first-page":"459","article-title":"Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions","author":"Andoni Alexandr","year":"2006","unstructured":"Alexandr Andoni and Piotr Indyk. 2006. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. In FOCS. 459-468.","journal-title":"FOCS."},{"key":"e_1_2_1_3_1","first-page":"1225","article-title":"Practical and Optimal LSH for Angular Distance","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 NIPS. 1225-1233.","journal-title":"NIPS."},{"key":"e_1_2_1_4_1","volume-title":"Ribeiro-Neto","author":"Baeza-Yates Ricardo A.","year":"1999","unstructured":"Ricardo A. Baeza-Yates and Berthier A. Ribeiro-Neto. 1999. Modern Information Retrieval. ACM Press \/ Addison-Wesley. http:\/\/www.dcc.ufmg.br\/irbook\/"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-842X.1972.tb00899.x"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223855"},{"key":"e_1_2_1_7_1","first-page":"21","article-title":"On the resemblance and containment of documents","author":"Broder Andrei Z.","year":"1997","unstructured":"Andrei Z. Broder. 1997. On the resemblance and containment of documents. In SEQUENCES. IEEE, 21-29.","journal-title":"SEQUENCES. IEEE"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00031-7"},{"key":"e_1_2_1_9_1","volume-title":"Quantifying Memorization Across Neural Language Models. CoRR","author":"Carlini Nicholas","year":"2022","unstructured":"Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tram\u00e8r, and Chiyuan Zhang. 2022. Quantifying Memorization Across Neural Language Models. CoRR, Vol. abs\/2202.07646 (2022). arXiv:2202.07646 https:\/\/arxiv.org\/abs\/2202.07646"},{"key":"e_1_2_1_10_1","volume-title":"Specter: Document-level representation learning using citation-informed transformers. arXiv preprint arXiv:2004.07180","author":"Cohan Arman","year":"2020","unstructured":"Arman Cohan, Sergey Feldman, Iz Beltagy, Doug Downey, and Daniel S Weld. 2020. Specter: Document-level representation learning using citation-informed transformers. arXiv preprint arXiv:2004.07180 (2020)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Edith Cohen. 2016. Min-Hash Sketches.","DOI":"10.1007\/978-1-4939-2864-4_573"},{"key":"e_1_2_1_12_1","volume-title":"Introduction to Algorithms (3 ed.)","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3 ed.). MIT Press, Cambridge, MA."},{"key":"e_1_2_1_13_1","volume-title":"2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 663-671","author":"Dahlgaard S\u00f8ren","year":"2017","unstructured":"S\u00f8ren Dahlgaard, Mathias B\u00e6k Tejs Knudsen, and Mikkel Thorup. 2017. Fast similarity sketching. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 663-671."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_15_1","first-page":"3023","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Ding Hailun","year":"2021","unstructured":"Hailun Ding, Shenao Yan, Juan Zhai, and Shiqing Ma. 2021. ELISE: A storage efficient logging system powered by redundancy reduction and representation learning. In 30th USENIX Security Symposium (USENIX Security 21). 3023-3040."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457548"},{"key":"e_1_2_1_17_1","volume-title":"2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1190-1201","author":"Fernandez Raul Castro","year":"2019","unstructured":"Raul Castro Fernandez, Jisoo Min, Demitri Nava, and Samuel Madden. 2019. Lazo: A cardinality-based method for coupled estimation of jaccard similarity and containment. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1190-1201."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_19_1","article-title":"Academic Plagiarism Detection","volume":"52","author":"Folt\u00fdnek Tom\u00e1s","year":"2020","unstructured":"Tom\u00e1s Folt\u00fdnek, Norman Meuschke, and Bela Gipp. 2020. Academic Plagiarism Detection: A Systematic Literature Review. ACM Comput. Surv., Vol. 52, 6 (2020), 112:1-112:42.","journal-title":"A Systematic Literature Review. ACM Comput. Surv."},{"key":"e_1_2_1_20_1","first-page":"2","article-title":"A New Algorithm for Data Compression","volume":"12","author":"Gage Philip","year":"1994","unstructured":"Philip Gage. 1994. A New Algorithm for Data Compression. C Users J., Vol. 12, 2 (feb 1994), 23\u201338.","journal-title":"C Users J."},{"key":"e_1_2_1_21_1","first-page":"541","article-title":"Locality-sensitive hashing scheme based on dynamic collision counting","author":"Gan Junhao","year":"2012","unstructured":"Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In SIGMOD. 541-552.","journal-title":"SIGMOD."},{"key":"e_1_2_1_22_1","first-page":"518","article-title":"Similarity Search in High Dimensions via Hashing","author":"Gionis Aristides","year":"1999","unstructured":"Aristides Gionis, Piotr Indyk, and Rajeev Motwani. 1999. Similarity Search in High Dimensions via Hashing. In VLDB. 518-529.","journal-title":"VLDB."},{"key":"e_1_2_1_23_1","first-page":"61","article-title":"Detecting the origin of text segments efficiently","author":"Hamid Ossama Abdel","year":"2009","unstructured":"Ossama Abdel Hamid, Behshad Behzadi, Stefan Christoph, and Monika Rauch Henzinger. 2009. Detecting the origin of text segments efficiently. In WWW. ACM, 61-70.","journal-title":"WWW. ACM"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.10170"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_26_1","first-page":"604","article-title":"Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality","author":"Indyk Piotr","year":"1998","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604-613.","journal-title":"STOC."},{"key":"e_1_2_1_27_1","first-page":"81","article-title":"Efficient overlap and content reuse detection in blogs and online news articles","author":"Kim Jong Wook","year":"2009","unstructured":"Jong Wook Kim, K. Sel\u00e7uk Candan, and Jun'ichi Tatemura. 2009. Efficient overlap and content reuse detection in blogs and online news articles. In WWW. ACM, 81-90.","journal-title":"WWW. ACM"},{"key":"e_1_2_1_28_1","first-page":"8424","article-title":"Deduplicating Training Data Makes Language Models Better","author":"Lee Katherine","year":"2022","unstructured":"Katherine Lee, Daphne Ippolito, Andrew Nystrom, Chiyuan Zhang, Douglas Eck, Chris Callison-Burch, and Nicholas Carlini. 2022. Deduplicating Training Data Makes Language Models Better. In ACL. 8424-8445.","journal-title":"ACL."},{"key":"e_1_2_1_29_1","first-page":"3122","article-title":"One Permutation Hashing","author":"Li Ping","year":"2012","unstructured":"Ping Li, Art B. Owen, and Cun-Hui Zhang. 2012. One Permutation Hashing. In NIPS. 3122-3130.","journal-title":"NIPS."},{"key":"e_1_2_1_30_1","unstructured":"Xiaoyun Li and Ping Li. 2021. C-MinHash: Practically Reducing Two Permutations to Just One. arXiv:2109.04595 [cs.DS] https:\/\/arxiv.org\/abs\/2109.04595"},{"key":"e_1_2_1_31_1","first-page":"950","article-title":"Multi-Probe LSH","author":"Lv Qin","year":"2007","unstructured":"Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search. In VLDB. 950-961.","journal-title":"Efficient Indexing for High-Dimensional Similarity Search. In VLDB."},{"key":"e_1_2_1_32_1","first-page":"1","volume-title":"USENIX","author":"Manber Udi","year":"1994","unstructured":"Udi Manber. 1994. Finding Similar Files in a Large File System. In USENIX Winter 1994 Technical Conference, San Francisco, California, USA, January 17-21, 1994, Conference Proceedings. USENIX Association, 1-10. https:\/\/www.usenix.org\/conference\/usenix-winter-1994-technical-conference\/finding-similar-files-large-file-system"},{"key":"e_1_2_1_33_1","volume-title":"PAN 2014 Text Alignment Task. https:\/\/pan.webis.de\/clef14\/pan14-web\/text-alignment.html.","author":"PAN.","year":"2014","unstructured":"PAN. 2014. PAN 2014 Text Alignment Task. https:\/\/pan.webis.de\/clef14\/pan14-web\/text-alignment.html."},{"key":"e_1_2_1_34_1","unstructured":"PAN. 2025. PAN Datasets. https:\/\/pan.webis.de\/data.html."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589324"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677136"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872770"},{"key":"e_1_2_1_38_1","first-page":"571","article-title":"Local text reuse detection","author":"Seo Jangwon","year":"2008","unstructured":"Jangwon Seo and W. Bruce Croft. 2008. Local text reuse detection. In SIGIR. ACM, 571-578.","journal-title":"SIGIR. ACM"},{"key":"e_1_2_1_39_1","volume-title":"International Conference on Machine Learning. PMLR, 3154-3163","author":"Shrivastava Anshumali","year":"2017","unstructured":"Anshumali Shrivastava. 2017. Optimal densification for fast and accurate minwise hashing. In International Conference on Machine Learning. PMLR, 3154-3163."},{"key":"e_1_2_1_40_1","first-page":"2321","article-title":"Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li. 2014a. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In NIPS. 2321-2329.","journal-title":"NIPS."},{"key":"e_1_2_1_41_1","volume-title":"International Conference on Machine Learning. PMLR, 557-565","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li. 2014b. Densifying one permutation hashing via rotation for fast near neighbor search. In International Conference on Machine Learning. PMLR, 557-565."},{"key":"e_1_2_1_42_1","volume-title":"Improved densification of one permutation hashing. arXiv preprint arXiv:1406.4784","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li. 2014c. Improved densification of one permutation hashing. arXiv preprint arXiv:1406.4784 (2014)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277928"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_46_1","first-page":"563","article-title":"Quality and efficiency in high dimensional nearest neighbor search","author":"Tao Yufei","year":"2009","unstructured":"Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. 2009. Quality and efficiency in high dimensional nearest neighbor search. In SIGMOD. 563-576.","journal-title":"SIGMOD."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806912"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488655"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526178"},{"key":"e_1_2_1_50_1","unstructured":"Shuo Yang Wei-Lin Chiang Lianmin Zheng Joseph E. Gonzalez and Ion Stoica. 2023. Rethinking Benchmark and Contamination for Language Models with Rephrased Samples. arXiv:2311.04850 [cs.CL] https:\/\/arxiv.org\/abs\/2311.04850"},{"key":"e_1_2_1_51_1","unstructured":"Yuheng Zhang Zhencan Peng Miao Qiao Wei Zhang Feifei Li and Dong Deng. 2025. Near-Duplicate Text Alignment under Weighted Jaccard Similarity. https:\/\/github.com\/rutgers-db\/KMINSLSH\/raw\/main\/All-Pair_Near-Duplicate_Text_Alignment_via_LSH.pdf. Technical Report."},{"key":"e_1_2_1_52_1","unstructured":"Eric Zhu. 2025. datasketch: MinHash LSH Implementation. https:\/\/github.com\/ekzhu\/datasketch GitHub repository."},{"key":"e_1_2_1_53_1","volume-title":"Miller","author":"Zhu Erkang","year":"2019","unstructured":"Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Ren\u00e9e J. Miller. 2019. JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. In SIGMOD. 847-864."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994534"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802083","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802083","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:33:23Z","timestamp":1779129203000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802083"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802083"],"URL":"https:\/\/doi.org\/10.1145\/3802083","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}