Near-Duplicate Text Alignment under Weighted Jaccard Similarity

vldb26-1829 · Regular Research · Yuheng Zhang, Miao Qiao, Zhencan Peng, Deng Dong
Abstract

Near-duplicate text alignment is the task of identifying, among the texts in a corpus, all the subsequences (\ie substrings) 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. Recent methods leverage min-hash techniques under the following hash-based framework: index by grouping all the subsequences using their min-hash, and for any query, use the index to find all the min-hash sketches that are similar to the query's sketch. These methods guarantee to report all the subsequences whose estimated \textit{unweighted} Jaccard similarity with the query exceeds a user-provided threshold and are efficient. However, they fail to account for token importance, or even token frequency, which limits their applicability in real-world scenarios where tokens carry weights, such as TF-IDF. To overcome this limitation, in this paper, we propose \mono, an approach that supports near-duplicate text alignment under \textit{weighted} Jaccard similarity using consistent weighted sampling. \mono achieves optimality within the above hash-based framework. For example, when token weights are proportional to their frequencies, \mono generates $O(n + n\log f_T)$ groups (in expectation due to hashing) for a text of length $n$, where $f_T$ is the maximum token frequency in the text. Each group takes $O(1)$ space and represents a few subsequences sharing the same consistent weighted sampling. We further prove that this bound is asymptotically tight: any algorithm must produce $\Omega(n + n \log f_T)$ groups in expectation in the worst case. Such an optimality over a wide range of weight functions is achieved based on multiple key insights into the hashing structure under consistent weighted sampling and is thus non-trivial. Extensive experiments demonstrate that \mono outperforms the state-of-the-art by up to $26\times$ in index construction time, reduces index size by up to $30\%$, and improves query latency by up to $3\times$, while exhibiting superior scalability.

Assigned reviewers

No reviewers assigned yet.

Candidates from the panel ranked by taxonomy affinity

#ReviewerMatchLoadWhy