Compatibility and inclusion of similarity element resolutions

Patent metadata

Field	Value
Publication number	US-2015019509-A1
Application number	US-201313941999-A
Country	US
Kind code	A1
Filing date	Jul 15, 2013
Priority date	Jul 15, 2013
Publication date	Jan 15, 2015
Grant date	—

Abstract

For adaptive similarity search resolution in a data deduplication system using a processor device in a computing environment, multiple resolution levels are configured for a similarity search. Input similarity elements are calculated in one resolution level for a chunk of input data. The input similarity elements of the one resolution level are used to find similar data in a repository of data where similarity elements of the stored similar repository data are of the multiple resolution levels.

First claim

What is claimed is:

1 . A method for adaptive similarity search using compatibility and inclusion of similarity element resolutions in a data deduplication system using a processor device in a computing environment, comprising:
configuring a plurality of resolution levels for a similarity search; calculating input similarity elements in one resolution level for a chunk of input data; using the input similarity elements of the one resolution level to find similar data in a repository of data where similarity elements of the stored similar repository data are of the plurality of resolution levels.

2 . The method of claim 1 , further including performing one of:
defining the plurality of resolution levels to be between a highest resolution level and a lowest resolution level, and configuring the similarity elements of each one of the plurality of resolution levels to be a subset of the similarity elements of each one of the plurality of resolution levels which are higher than the one resolution level.

3 . The method of claim 2 , further including calculating the similarity elements based on one of maximum values and minimum values of rolling hash values calculated for chunks of input data.

4 . The method of claim 1 , further including calculating a resolution level for the similarity elements of an input chunk based on calculated sets of similarity element matches and on a calculated deduplication ratio.

5 . The method of claim 4 , further including storing the input similarity elements in the calculated resolution level in a similarity search structure, and using the similarity search structure to find similarity elements of similar repository data.

6 . The method of claim 4 , further including calculating an average size of the sets of similarity element matches, and using the average size to determine the resolution level of the input similarity elements.

7 . The method of claim 6 , further including performing one of:
calculating an aggregated deduplication ratio as a total size of portions of the input chunks covered by data matches out of the total size of the chunks, and using the aggregated deduplication ratio to determine the resolution level of the input similarity elements.

8 . The method of claim 7 , further including performing one of:
decreasing the similarity elements resolution level if the aggregated deduplication ratio is not lower than a predefined threshold and the average size of the sets of similarity element matches is not lower than two and the current resolution level is higher than the lowest resolution level; and increasing the similarity elements resolution level if the aggregated deduplication ratio is lower than a predefined threshold and the current resolution level is lower than the highest resolution level.

9 . A system for adaptive similarity search using compatibility and inclusion of similarity element resolutions in a data deduplication system of a computing environment, the system comprising:
the data deduplication system; a repository operating in the data deduplication system; a memory in the data deduplication system; a similarity search structure in association with the memory in the data deduplication system; and at least one processor device operable in the computing storage environment for controlling the data deduplication system, wherein the at least one processor device:
configuring a plurality of resolution levels for a similarity search,
calculating input similarity elements in one resolution level for a chunk of input data, and
using the input similarity elements of the one resolution level to find similar data in the repository of data where similarity elements of the stored similar repository data are of the plurality of resolution levels.

10 . The system of claim 9 , wherein the at least one processor device that performs one of:
defining the plurality of resolution levels to be between a highest resolution level and a lowest resolution level, and configuring the similarity elements of each one of the plurality of resolution levels to be a subset of the similarity elements of each one of the plurality of resolution levels which are higher than the one resolution level.

11 . The system of claim 10 , wherein the at least one processor device that calculates the similarity elements based on one of maximum values and minimum values of rolling hash values calculated for chunks of input data.

12 . The system of claim 9 , wherein the at least one processor device that calculates a resolution level for the similarity elements of an input chunk based on calculated sets of similarity element matches and on a calculated deduplication ratio.

13 . The system of claim 12 , wherein the at least one processor device that stores the input similarity elements in the calculated resolution level in the similarity search structure, and using the similarity search structure to find similarity elements of similar repository data.

14 . The system of claim 12 , wherein the at least one processor device that calculates an average size of the sets of similarity element matches, and using the average size to determine the resolution level of the input similarity elements.

15 . The system of claim 14 , wherein the at least one processor device that performs one of:
calculating an aggregated deduplication ratio as a total size of portions of the input chunks covered by data matches out of the total size of the chunks, and using the aggregated deduplication ratio to determine the resolution level of the input similarity elements.

16 . The system of claim 15 , wherein the at least one processor device that performs one of:
decreasing the similarity elements resolution level if the aggregated deduplication ratio is not lower than a predefined threshold and the average size of the sets of similarity element matches is not lower than two and the current resolution level is higher than the lowest resolution level; and increasing the similarity elements resolution level if the aggregated deduplication ratio is lower than a predefined threshold and the current resolution level is lower than the highest resolution level.

17 . A computer program product for adaptive similarity search using compatibility and inclusion of similarity element resolutions 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:
a first executable portion that configures a plurality of resolution levels for a similarity search; a second executable portion that calculates input similarity elements in one resolution level for a chunk of input data; and a third executable portion that uses the input similarity elements of the one resolution level to find similar data in a repository of data where similarity elements of the stored similar repository data are of the plurality of resolution levels.

18 . The computer program product of claim 17 , further including a fourth executable portion that performs one of:
defining the plurality of resolution levels to be between a highest resolution level and a lowest resolution level, and configuring the similarity elements of each one of the plurality of resolution levels to be a subset of the similarity elements of each one of the plurality of resolution levels which are higher than the one resolution level.

19 . The comp

Assignees

• IBM

Inventors

• Aronovich Lior

Classifications

• G06F2003/0695

  Physics · mapped topic

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F3/0673

  Single storage device · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title