LSHAlign: All-Pair Near-Duplicate Text Alignment via Locality-Sensitive Hashing
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-26
DOI: 10.1145/3802083 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Yuheng Zhang und 5 weiteren Autor:innen. Die Arbeit nennt 54 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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 O (|T| 2 |S| 2 k ) time even when estimating Jaccard similarity via min-hash with k independent hash functions. To overcome this limitation, we propose an efficient framework based on Locality-Sensitive Hashing (LSH), which employs m × L independent hash functions organized into L hash tables of m 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 is O ( nmL ). We further design a data structure to represent each group in O (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 O ((|T|+|S|) mL ), excluding the cost of outputting the pairs. This is significantly lower than the naive approach using the same number k = m × L 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.
Förderung
- National Science Foundation
Zitieren
APA
Zhang, Y., Peng, Z., Qiao, M., Zhang, W., Li, F., & Deng, D. (2026). LSHAlign: All-Pair Near-Duplicate Text Alignment via Locality-Sensitive Hashing. Proceedings of the ACM on Management of Data, 4(3), 1-26. https://doi.org/10.1145/3802083
Vancouver
Zhang Y, Peng Z, Qiao M, Zhang W, Li F, Deng D. LSHAlign: All-Pair Near-Duplicate Text Alignment via Locality-Sensitive Hashing. Proceedings of the ACM on Management of Data. 2026;4(3):1-26. doi:10.1145/3802083
BibTeX
@article{Zhang2026,
author = {Zhang, Yuheng and Peng, Zhencan and Qiao, Miao and Zhang, Wei and Li, Feifei and Deng, Dong},
title = {LSHAlign: All-Pair Near-Duplicate Text Alignment via Locality-Sensitive Hashing},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--26},
doi = {10.1145/3802083}
}
EUVIMED