A feature-based intelligent deduplication compression system with extreme resemblance detection

Figures & data

Figure 1. An overview of FIDCS-ERD. fp means the fingerprint representing an identifier of a chunk, which is used to identify the duplicate chunk. Sketch is a Bloom filter-based array, which is compared to find the similar chunk.

Figure 2. The processing flow in FIDCS-ERD.

Table 1. Description of notations.

Notation	Description
$\mathbf{B}$	A data stream which is a set of integers $\{B_0,\dots ,B_{n-1}\}$, $B_i\in [0,255]$
w	The size of the sliding window
α	The average size of the chunk
p	The primer to compute Rabin function
β	The minimal size of the chunk
γ	The maximal size of the chunk
$\mathcal{H}$	A set of independent hash functions $\{h_1,\dots ,h_k\}$
ℓ	The number of bits of each hash function $h_i$
m	The number of bits of sketch
τ	The threshold of common bits over two sketches
z	The number of chosen Rabin fingerprints for sketch

Figure 3. The influence of the average size of a chunk on duplicate and resemblance detection. D, S and N represent the duplicate, the similar, and the unique chunk, respectively.

Figure 4. Basic operations of Bloom filter.

Figure 5. The process of compression and decompression of a similar chunk.

Table 2. An overview of datasets.

Dataset	Size	Description
Glibc	10 GB	67 versions of glibc and glibc-ports. Each version is packaged as a tar file.
Email	25 GB	Email files from 10 users.
Image	20 GB	Life photos from 6 users. The format consists of jpg and png.

Figure 6. Results of dataset Glibc. (a) $\mathsf{C}\mathsf{R}$ with α. (b) $\mathsf{D}\mathsf{C}\mathsf{R}\mathsf{p}\mathsf{C}$ with α. (c) $\mathsf{T}\mathsf{P}$ with α. (d) $\mathsf{C}\mathsf{R}$ with β and γ. (e) $\mathsf{D}\mathsf{C}\mathsf{R}\mathsf{p}\mathsf{C}$ with β and γ. (f) $\mathsf{T}\mathsf{P}$ with β and γ. (g) $\mathsf{C}\mathsf{R}$ with k for DD. (h) $\mathsf{C}\mathsf{R}$ with k for RD. (i) $\mathsf{T}\mathsf{P}$ with k for RD.

Figure 7. Results of dataset email. (a) $\mathsf{C}\mathsf{R}$ with α. (b) $\mathsf{D}\mathsf{C}\mathsf{R}\mathsf{p}\mathsf{C}$ with α. (c) $\mathsf{T}\mathsf{P}$ with α.

Figure 8. Results of image. (a) $\mathsf{C}\mathsf{R}$ with α. (b) $\mathsf{D}\mathsf{C}\mathsf{R}\mathsf{p}\mathsf{C}$ with α. (c) $\mathsf{T}\mathsf{P}$ with α.