Efficient calculation of similarity search values and digest block boundaries for data deduplication
AssigneeInternational Business Machines Corporation
InventorsShay H. AKIRAV, Lior ARONOVICH, Shira BEN-DOR, Michael HIRSCH, Ofer LENEMAN
Life of this patent
Estimating the term…
Abstract
For efficient calculation of both similarity search values and boundaries of digest blocks in data deduplication, input data is partitioned into chunks, and for each chunk a set of rolling hash values is calculated. A single linear scan of the rolling hash values is used to produce both similarity search values and boundaries of the digest blocks of the chunk. The rolling hash values are used to contribute to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.
Claims18
A method for efficient calculation of both similarity search values and boundaries of digest blocks in a data deduplication system using a processor device in a computing environment, comprising:
- partitioning input data into data chunks;
- calculating a set of rolling hash values for each of the data chunks;
- using a single linear scan of the rolling hash values for producing both the similarity search values and the boundaries of the digest blocks;
- and
- using each of the rolling hash values to contribute to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.
A system for efficient calculation of both similarity search values and boundaries of digest blocks in a data deduplication system of a computing environment, the system comprising:
- the data deduplication system;
- a repository in the computing environment in communication with the data deduplication system;
- at least one processor device operable in the computing storage environment for controlling the data deduplication system, wherein the at least one processor device:
- partitions input data into data chunks,
- calculates a set of rolling hash values for each of the data chunks,
- uses a single linear scan of the rolling hash values for producing both the similarity search values and the boundaries of the digest blocks, and
- uses each of the rolling hash values to contribute to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.
A computer program product for efficient calculation of both similarity search values and boundaries of digest blocks in a data deduplication system using a processor device in a computing environment, the computer program product comprising a computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:
- an executable portion that partitions input data into data chunks;
- an executable portion that calculates a set of rolling hash values for each of the data chunks;
- an executable portion that uses a single linear scan of the rolling hash values for producing both the similarity search values and the boundaries of the digest blocks;
- and
- an executable portion that uses each of the rolling hash values to contribute to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.
Dependencies are inferred from the claim text.