Near-Duplicate Text Alignment under Weighted Jaccard Similarity
Yuheng Zhang 1 Miao Qiao 2 Zhencan Peng 1 Dong Deng 1 · 2025
Read Near-Duplicate Text Alignment under Weighted Jaccard Similarity by Yuheng Zhang 1 Miao Qiao 2 Zhencan Peng 1 Dong Deng 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00627.txt.
Introduction
Yuheng Zhang, with three co-authors, Miao Qiao, Zhencan Peng, and Dong Deng, addresses near-duplicate text alignment, finding all substrings in a corpus similar to a query. Older seeding methods lack accuracy guarantees and need many tuned settings, while min-hash methods ignore how important or frequent each token is.
Zhang and his co-authors propose MONO, which supports weighted Jaccard similarity, a similarity score that counts token weights, using consistent weighted sampling. They prove MONO is optimal within the hash-based framework and that its group count bound is tight. Experiments show index building up to twenty-six times faster, smaller indexes, and query times up to three times better than the prior leading method.
Catalog record
| CREATOR | Yuheng Zhang 1 Miao Qiao 2 Zhencan Peng 1 Dong Deng 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-00627
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Near-Duplicate Text Alignment under Weighted Jaccard Similarity Yuheng Zhang 1 Miao Qiao 2 Zhencan Peng 1 Dong Deng 1 Abstract . Near-duplicate text alignment is the task of identifying all subsequences (i.e., substrings) in a collection of texts that are similar to a given query. Traditional approaches rely on seeding–extension–filtering heuristics, which lack accuracy guarantees and require many hard-to-tune parameters. More recent methods leverage min-hash techniques. They propose to group all the subsequences in each text by their min-hash and index the groups. When a query arrives, they can use the index to find all the min-hash sketches that are similar to the query’s sketch and then return the corresponding subsequences as the results efficiently. Thus these methods guarantee to identify all subsequences whose estimated Jaccard similarity with the query exceed a user-provided threshold. However, these methods only support unweighted Jaccard similarity, which cannot capture token importance or frequency, limiting their effectiveness in real-world scenarios where tokens carry weights, such as TF-IDF. In this paper, we address this limitation by supporting weighted Jaccard similarity using consistent weighted sampling. We design an algorithm MonoActive to group all subsequences in a text by their consistent weighted sampling. We analyze the complexity of our algorithm. For raw count term frequency (where a token’s weight is proportional to its frequency in the text), we prove MonoActive generates O ( n + n log f ) O(n+n\log f) groups (each group occupies O ( 1 ) O(1) space) in expectation for a text with n n tokens, where f f is the maximum token frequency in the text. We further prove that our algorithm is optimal, meaning that any algorithm must generate Ω ( n + n log f ) \Omega(n+n\log f) groups in expectation. Extensive experiments show that MonoActive outperforms the state-of-the-art by up to 4.7 × \times in speed and reduces index size by up to 30%, with superior scalability. † † authors: . PVLDB Reference Format: PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at URL_TO_YOUR_ARTIFACTS . 1. Introduction This paper studies the near-duplicate text alignment problem ( DBLP:conf/clef/PotthastGHKMOTBGRS12 ; DBLP:conf/clef/PotthastHBBTRS14 ; allign ; txtalign ; DBLP:journals/pacmmod/PengZD24 ; llmalign ) . Given a collection of data texts, the task takes a short query text and returns all subsequences (i.e., substrings) of the data texts that are similar to the query. Near-duplicate text alignment has become increasingly important in the era of large language models (LLMs), with key applications in test set leakage (also known as data contamination) detection ( DBLP:conf/acl/Magar022 ) , training data deduplication ( betterlm ) , and memorization analysis ( quantifymemo ; DBLP:conf/emnlp/VuHHS23 ) . Beyond LLMs, this problem also plays a crucial role in domains such as bioinformatics ( ALTSCHUL1990403 ) , log analysis ( DBLP:conf/uss/DingZ0M23 ) , and plagiarism detection ( DBLP:conf/clef/PotthastHGTKRSS13 ; DBLP:conf/clef/PotthastBESR10 ) . Due to the high computational cost of near-duplicate text alignment, previous methods often adopt the seeding–extension–filtering heuristic ( DBLP:conf/clef/PotthastBESR10 ; DBLP:conf/usenix/Manber94 ; DBLP:journals/cn/BroderGMZ97 ; DBLP:conf/sigmod/SchleimerWA03 ; DBLP:conf/www/HamidBCH09 ; DBLP:conf/sigmod/BrinDG95 ; DBLP:conf/sigir/SeoC08 ; DBLP:conf/www/KimCT09 ; DBLP:books/aw/Baeza-YatesR99 ; DBLP:journals/jasis/HoadZ03 ; DBLP:conf/sigmod/WangXQWZI16 ) . However, these methods lack accuracy guarantees and often involve many hard-to-tune hyperparameters ( DBLP:journals/csur/FoltynekMG20 ) . To address these limitations, recent studies have proposed to use min-hash techniques ( minhash ; DBLP:conf/nips/0001OZ12 ) for near-duplicate text alignment. These approaches guarantee to retrieve all subsequences whose estimated Jaccard similarities with the query exceed a user-defined threshold ( allign ; txtalign ; llmalign ; DBLP:journals/pacmmod/PengZD24 ) . However, a key limitation is that they only support the unweighted Jaccard similarity, which treats all tokens equally—regardless of their frequency or importance (note depending on the tokenizer, a token can be a word ( whitespace_splitted_tokens ) , a q -gram ( n-gram ) , a byte-pair-encoding ( bpe ) , etc.). To highlight the issue of unweighted Jaccard similarity, consider \textnormal{Q}=\text{{AAAAAATTTTTTCCCCCC}} , \textnormal{T}=\text{{AAAAAATTTTTGCCCCCC}}, and \textnormal{S}=\text{{AATTGCC}.} Intuitively, Q is much more similar to T than to S . Yet, under unweighted Jaccard similarity (with each token as a 2-gram), both Q and T , as well as Q and S yield the same similarity score: 4/7 . In contrast, weighted Jaccard similarity correctly reflects the difference: when each token in a text is weighted by its frequency in the text, Q and T have a similarity of 0.8 , while Q and S only score 0.2 . Moreover, unweighted Jaccard similarity fails to distinguish between stop words and content words. For example, consider \textnormal{Q}=\text{``{I read about Einstein in a book}''} , \textnormal{T}=\text{``{I studied Einstein through a book}''} , \textnormal{S}=\text{``{I roamed about in a castle}''}. Semantically, Q is clearly closer to T than to S . However, the unweighted Jaccard similarity is the same for both: 4/9 (with each token as a word). If a meaningful token weighting scheme such as TF-IDF ( singhal2001modern ) is applied, then stop words, e.g., I, in, a, about, through , could have near-zero weight and the other words may have near-one weight, and thereby drawing clear distinctions. Under this scheme, the weighted Jaccard similarity between Q and T is around 0.5 , while that between Q and S drops to nearly zero. Existing Methods. Existing methods propose to group, as the indexing process, the subsequences in each data text based on their min-hash values. This way, when a query arrives, they use the index to identify all the min-hash sketches that are similar to the query’s min-hash sketch and then return the corresponding subsequences as the results efficiently ( allign ; llmalign ; DBLP:journals/pacmmod/PengZD24 ) . A key observation made by these methods is that the nearby subsequences of a text tend to share the same min-hash (this is because appending a token to a subsequence most likely would not change the min-hash of the subsequence). Given a text with n tokens, they group the O(n^{2}) subsequences in the text into O(n) groups while represent each group with a tuple of O(1) space. Limitations of Existing Methods. In many real-world scenarios, tokens are associated with weights, such as TF-IDF (term frequency-inverse document frequency) weights ( DBLP:conf/hicss/PasiB23 ) . Estimating weighted Jaccard similarity requires consistent weighted sampling (CWS) ( DBLP:conf/icdm/Ioffe10 ) , as standard min-hash ( minhash ) applies only to the unweighted case. Existing methods do not support CWS or weighted Jaccard similarity. The only exception is AllAlign ( allign ) which supports multi-set Jaccard, a special case of weighted Jaccard where each token’s weight is its frequency in the text. AllAlign is a greedy algorithm which groups the subsequences by their “multi-set min-hash”. However, it lacks a formal complexity analysis, including an upper bound on the number of groups generated and its time complexity. Due to its recursive nature, analyzing its complexity is particularly difficult. Our Approach.