{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T16:33:02Z","timestamp":1781713982821,"version":"3.54.5"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["2212629, 2152908"],"award-info":[{"award-number":["2212629, 2152908"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,10,1]]},"abstract":"<jats:p>\n                    This paper studies the near-duplicate text alignment problem under the constraint of Jaccard similarity. Specifically, given a collection of long texts and a short query text, this problem finds all the\n                    <jats:italic toggle=\"yes\">subsequences<\/jats:italic>\n                    in each text whose Jaccard similarities to the query are no smaller than a given threshold. Near-duplicate text alignment is computationally intensive. This is because there are O(n\n                    <jats:sup>2<\/jats:sup>\n                    ) subsequences in a text with\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    tokens. To remedy this issue, a few recent studies propose to first generate the min-hash sketch of every subsequence in each text and then find all the subsequences whose min-hash sketches are similar to that of the query. They introduce the concept of \"compact windows\" and show that the O(n\n                    <jats:sup>2<\/jats:sup>\n                    k) min-hashes in a text with\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    tokens can be losslessly compressed in compact windows using O(nk) space, where\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    is the sketch size. However, the space cost O(nk) is still too high for long texts, especially when the sketch size\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    is large. To address this issue, we propose to use One Permutation Hashing (OPH) to generate the min-hash sketch and introduce the concept of \"OPH compact windows\". Although the size of each sketch remains the same, which is O(k), we prove that all the O(n\n                    <jats:sup>2<\/jats:sup>\n                    k) min-hashes generated by OPH in a text with\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    tokens can be losslessly compressed in OPH compact windows using only O(n+k) space. Note the generation of OPH compact windows does not necessitate the enumeration of the O(n\n                    <jats:sup>2<\/jats:sup>\n                    k) min-hashes. Moreover, we develop an algorithm to find all the sketches in a text similar to that of the query directly from OPH compact windows, along with three optimizations.We conduct extensive experiments on three real-world datasets. Empirical results show our proposed algorithms significantly outperformed existing methods in terms of index cost and query latency and scaled well.\n                  <\/jats:p>","DOI":"10.1145\/3677136","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T17:41:44Z","timestamp":1727718104000},"page":"1-26","source":"Crossref","is-referenced-by-count":4,"title":["Near-Duplicate Text Alignment with One Permutation Hashing"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4182-0075","authenticated-orcid":false,"given":"Zhencan","family":"Peng","sequence":"first","affiliation":[{"name":"Rutgers University, Piscataway, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3798-0140","authenticated-orcid":false,"given":"Yuheng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4596-3850","authenticated-orcid":false,"given":"Dong","family":"Deng","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"SemEval-2016 Task 1: Semantic Textual Similarity, Monolingual and Cross-Lingual Evaluation","author":"Agirre Eneko","unstructured":"Eneko Agirre, Carmen Banea, Daniel M. Cer, Mona T. Diab, Aitor Gonzalez-Agirre, Rada Mihalcea, German Rigau, and Janyce Wiebe. 2016. SemEval-2016 Task 1: Semantic Textual Similarity, Monolingual and Cross-Lingual Evaluation. In SEMEVAL. The Association for Computer Linguistics, 497--511."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80360-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni and Piotr Indyk. 2006. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. In FOCS. 459--468.","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_2_1_4_1","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."},{"key":"e_1_2_1_5_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_6_1","doi-asserted-by":"crossref","unstructured":"Roberto J. Bayardo Yiming Ma and Ramakrishnan Srikant. 2007. Scaling up all pairs similarity search. In WWW. 131--140.","DOI":"10.1145\/1242572.1242591"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-842X.1972.tb00899.x"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223855"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/829502.830043"},{"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":"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). showeprint[arXiv]2202.07646 https:\/\/arxiv.org\/abs\/2202.07646"},{"key":"e_1_2_1_12_1","volume-title":"Multiple sequence alignment modeling: methods and applications. Briefings in bioinformatics","author":"Chatzou Maria","year":"2016","unstructured":"Maria Chatzou, Cedrik Magis, Jia-Ming Chang, Carsten Kemena, Giovanni Bussotti, Ionas Erb, and Cedric Notredame. 2016. Multiple sequence alignment modeling: methods and applications. Briefings in bioinformatics, Vol. 17, 6 (2016), 1009--1023."},{"key":"e_1_2_1_13_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_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.67"},{"key":"e_1_2_1_15_1","volume-title":"Mirrokni","author":"Datar Mayur","year":"2004","unstructured":"Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In SoCG. 253--262."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02603120"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457548"},{"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","volume-title":"Google Machine Translation Team","volume":"20","author":"Franz Alex","year":"2006","unstructured":"Alex Franz and Thorsten Brants. 2006. All our n-gram are belong to you. Google Machine Translation Team, Vol. 20 (2006)."},{"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--38.","journal-title":"C Users J."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Junhao Gan Jianlin Feng Qiong Fang and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In SIGMOD. 541--552.","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_22_1","unstructured":"Aristides Gionis Piotr Indyk and Rajeev Motwani. 1999. Similarity Search in High Dimensions via Hashing. In VLDB. 518--529."},{"key":"e_1_2_1_23_1","unstructured":"Aaron Gokaslan and Vanya Cohen. 2019. OpenWebText Corpus. http:\/\/Skylion007.github.io\/OpenWebTextCorpus."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 12th Language Resources and Evaluation Conference. 2440--2452","author":"Guo Mandy","year":"2020","unstructured":"Mandy Guo, Zihang Dai, Denny Vrandevci\u0107, and Rami Al-Rfou. 2020. Wiki-40b: Multilingual language model dataset. In Proceedings of the 12th Language Resources and Evaluation Conference. 2440--2452."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","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.","DOI":"10.1145\/1526709.1526719"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.10170"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604--613.","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_29_1","volume-title":"Search log analysis: What it is, what's been done, how to do it","author":"Jansen Bernard J","year":"2006","unstructured":"Bernard J Jansen. 2006. Search log analysis: What it is, what's been done, how to do it. Library & information science research, Vol. 28, 3 (2006), 407--432."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Jong Wook Kim K. Selccuk Candan and Jun'ichi Tatemura. 2009. Efficient overlap and content reuse detection in blogs and online news articles. In WWW. ACM 81--90.","DOI":"10.1145\/1526709.1526721"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989379"},{"key":"e_1_2_1_32_1","first-page":"253","article-title":"PASS-JOIN","volume":"5","author":"Li Guoliang","year":"2011","unstructured":"Guoliang Li, Dong Deng, Jiannan Wang, and Jianhua Feng. 2011. PASS-JOIN: A Partition-based Method for Similarity Joins. PVLDB, Vol. 5, 3 (2011), 253--264.","journal-title":"A Partition-based Method for Similarity Joins. PVLDB"},{"key":"e_1_2_1_33_1","volume-title":"Art B. Owen, and Cun-Hui Zhang","author":"Li Ping","year":"2012","unstructured":"Ping Li, Art B. Owen, and Cun-Hui Zhang. 2012. One Permutation Hashing. In NIPS. 3122--3130."},{"key":"e_1_2_1_34_1","volume-title":"Zhe Wang, Moses Charikar, and Kai Li.","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."},{"key":"e_1_2_1_35_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. USENIX Association, 1--10."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2303.03919"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/16.11.1046"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589324"},{"key":"e_1_2_1_40_1","volume-title":"Overview of the 2nd International Competition on Plagiarism Detection. In CLEF 2010 LABs and Workshops, Notebook Papers (CEUR Workshop Proceedings","author":"Potthast Martin","year":"2010","unstructured":"Martin Potthast, Alberto Barr\u00f3n-Cede no, Andreas Eiselt, Benno Stein, and Paolo Rosso. 2010. Overview of the 2nd International Competition on Plagiarism Detection. In CLEF 2010 LABs and Workshops, Notebook Papers (CEUR Workshop Proceedings, Vol. 1176). CEUR-WS.org."},{"key":"e_1_2_1_41_1","volume-title":"Overview of the 3rd International Competition on Plagiarism Detection. In CLEF 2011 Labs and Workshop, Notebook Papers (CEUR Workshop Proceedings","author":"Potthast Martin","year":"2011","unstructured":"Martin Potthast, Andreas Eiselt, Alberto Barr\u00f3n-Cede no, Benno Stein, and Paolo Rosso. 2011. Overview of the 3rd International Competition on Plagiarism Detection. In CLEF 2011 Labs and Workshop, Notebook Papers (CEUR Workshop Proceedings, Vol. 1177). CEUR-WS.org."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24027-5_42"},{"key":"e_1_2_1_43_1","volume-title":"Daniel Shawcross Wilkerson, and Alexander Aiken","author":"Schleimer Saul","year":"2003","unstructured":"Saul Schleimer, Daniel Shawcross Wilkerson, and Alexander Aiken. 2003. Winnowing: Local Algorithms for Document Fingerprinting. In SIGMOD. ACM, 76--85."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Jangwon Seo and W. Bruce Croft. 2008. Local text reuse detection. In SIGIR. ACM 571--578.","DOI":"10.1145\/1390334.1390432"},{"key":"e_1_2_1_45_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_46_1","volume-title":"International Conference on Machine Learning. PMLR, 557--565","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li. 2014. 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_47_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. 2014. Improved densification of one permutation hashing. arXiv preprint arXiv:1406.4784 (2014)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Yufei Tao Ke Yi Cheng Sheng and Panos Kalnis. 2009. Quality and efficiency in high dimensional nearest neighbor search. In SIGMOD. 563--576.","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806912"},{"key":"e_1_2_1_52_1","volume-title":"CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic acids research","author":"Thompson Julie D","year":"1994","unstructured":"Julie D Thompson, Desmond G Higgins, and Toby J Gibson. 1994. CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic acids research, Vol. 22, 22 (1994), 4673--4680."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","unstructured":"Mikkel Thorup. 2013. Bottom-k and priority sampling set similarity and subset sums with minimal independence. In STOC. ACM 371--380. https:\/\/doi.org\/10.1145\/2488608.2488655","DOI":"10.1145\/2488608.2488655"},{"key":"e_1_2_1_54_1","article-title":"The top 100 papers","volume":"514","author":"Noorden Richard Van","year":"2014","unstructured":"Richard Van Noorden, Brendan Maher, and Regina Nuzzo. 2014. The top 100 papers. Nature News, Vol. 514, 7524 (2014), 550.","journal-title":"Nature News"},{"key":"e_1_2_1_55_1","volume-title":"Koala: An Index for Quantifying Overlaps with Pre-training Corpora. arXiv preprint arXiv:2303.14770","author":"Vu Thuy-Trang","year":"2023","unstructured":"Thuy-Trang Vu, Xuanli He, Gholamreza Haffari, and Ehsan Shareghi. 2023. Koala: An Index for Quantifying Overlaps with Pre-training Corpora. arXiv preprint arXiv:2303.14770 (2023)."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915211"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099624"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","unstructured":"Zhizhi Wang Chaoji Zuo and Dong Deng. 2022. TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection. In SIGMOD. ACM 1146--1159. https:\/\/doi.org\/10.1145\/3514221.3526178","DOI":"10.1145\/3514221.3526178"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.3115\/992424.992434"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453957"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000825"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677136","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:10:36Z","timestamp":1774977036000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,1]]}},"alternative-id":["10.1145\/3677136"],"URL":"https:\/\/doi.org\/10.1145\/3677136","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,30]]}}}