SimPattern: A Novel Byte-Pattern Matching based Chunk Similarity Detection for Post-Deduplication

Abstract

Delta compression is a crucial technique in cloud storage systems that reduces storage overhead by identifying matching byte sequences across data chunks. A key challenge in delta compression is similarity detection, i.e., determining whether two chunks are sufficiently similar to be compressed with a delta. Existing similarity detection approaches typically rely on either super-feature representations or learning-based models, both of which are highly sensitive to byte-level insertions, deletions, and local reordering, thereby reducing the efficiency of delta compression. These approaches often fail to robustly capture similarity that may manifest as unaligned blocks, fragmented regions, or reordered content. In this paper, we propose SimPattern, a similarity detection method motivated by the characteristics of delta compression. SimPattern maps each possible byte value to a unique vector through a randomly initialized byte2vec dictionary, and represents each chunk by averaging the vectors of its constituent bytes. The similarity between chunks is then evaluated using cosine similarity in the resulting vector space. To efficiently select suitable reference chunks in high-dimensional space, SimPattern employs an approximate nearest-neighbor search-based reference selection scheme. Experimental results on real-world datasets demonstrate that SimPattern enables more fine-grained similarity detection and substantially improves the effectiveness of delta compression, reducing the final storage size by up to 42.68% compared with state-of-the-art methods. Its lightweight design makes SimPattern well-suited for deployment in parallel data-reduction pipelines without degrading system throughput.