Frequency-aware resemblance detection for group compression
ACM Transactions on Storage · 06.11.2026
DOI: 10.1145/3857840 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Storage, online erschienen am 06.11.2026. Verfasst von Yulin Tao und 6 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben.
Abstract (Originalsprache)
Data deduplication and compression systems critically depend on accurately detecting and grouping similar data blocks to maximize storage efficiency. However, traditional resemblance detection techniques like MinHash, Rabin fingerprints, and Finesse treat all shingles equally, leading to suboptimal grouping because high-frequency shingles are already well-handled by intra-block compression (e.g., ZSTD). To address this misalignment between estimated similarity and true compressibility, we propose LF-Hash, a frequency-aware resemblance detection method tailored for group compression. LF-Hash filters out high-frequency shingles and prioritizes low-frequency shingles, especially single-occurrence ones, which more accurately reflect inter-block structural redundancies. It employs an efficient one-permutation locality-sensitive hashing scheme and constructs a weighted similarity graph, followed by a multilevel graph partitioning algorithm for scalable block grouping. Integrated with group compression, our method bypasses the limitations of base-dependent delta compression and allows fine-grained, inter-block redundancy elimination. Extensive experiments covering twelve real-world datasets of different types demonstrate that LF-Hash consistently outperforms state-of-the-art baselines, achieving up to 48% higher compression ratios on system/application workloads and up to 130% on enterprise datasets while maintaining competitive throughput, making it well-suited for modern storage, backup, and deduplication scenarios.
Zitieren
APA
Tao, Y., Xi, X., Sun, W., Li, J., Guo, J., Yang, Q., & Shao, J. (2026). Frequency-aware resemblance detection for group compression. ACM Transactions on Storage. https://doi.org/10.1145/3857840
Vancouver
Tao Y, Xi X, Sun W, Li J, Guo J, Yang Q, et al. Frequency-aware resemblance detection for group compression. ACM Transactions on Storage. 2026. doi:10.1145/3857840
BibTeX
@article{Tao2026,
author = {Tao, Yulin and Xi, Xuanzhi and Sun, Wenping and Li, Jingwei and Guo, Jinxia and Yang, Qinli and Shao, Junming},
title = {Frequency-aware resemblance detection for group compression},
journal = {ACM Transactions on Storage},
year = {2026},
doi = {10.1145/3857840}
}
EUVIMED