Is Low Similarity Threshold A Bad Idea in Delta Compression?

Delta compression attracts many researchers' interest for its high efficiency in eliminating redundant data. It identifies a similar block for the incoming block and stores only the differences between them. The key challenge lies in detecting suitable similar blocks. Existing approaches have their limitations. Hash-based solutions like NTransform miss many similar blocks due to the high similarity detection threshold, while complex-threshold solutions like DeepSketch and Palantir have high computation overhead.

This paper explores whether a lower detection threshold can help delta compression. We propose new criteria to identify those wrongly recognized similar blocks and prevent their harm to the compression ratio. Moreover, using lower detection thresholds with a base block extension can effectively utilize potential duplicate data adjacent to the base block and achieve a higher compression ratio. Preliminary evaluation with six datasets shows that our approach, on average, improves the overall compression ratio (including deduplication and lossless compression) by 15.1% and finds 29.6% more similar blocks over the state-of-the-art approach Odess, with a throughput degradation of 3.7%.

© 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.