Systems and methods for efficient data searching, storage and reduction

• US 9,430,486 B2
• Filed: 03/19/2009
• Issued: 08/30/2016
• Est. Priority Date: 09/15/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hirsch, Michael, Bitner, Haim, Aronovich, Lior, Asher, Ron, Bachmat, Eitan, Klein, Shmuel T.
• Primary Examiner(s): WILLOUGHBY, ALICIA M
• Application Number:
  US12/407,782
• Publication Number:
  US 20090228453A1
• Time in Patent Office: 2,721 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Systems and methods enabling search of a repository for the location of data that is similar to input data, using a defined measure of similarity, in a time that is independent of the size of the repository and linear in a size of the input data, and a space that is proportional to a small fraction of the size of the repository. The similar data segments thus located are further analyzed to determine their common (identical) data sections, regardless of the order and position of the common data sections in the repository and input, and in a time that is linear in the segment size and in constant space.

Claims

1. A method in repository data for data that are similar to an input data, wherein the repository data comprises a plurality of repository data chunks and the input data comprises a plurality of input data chunks, the method comprising:

for each repository data chunk, generating a corresponding set of repository distinguishing characteristics (RDCs);

for each input data chunk, generating a corresponding set of input distinguishing characteristics (IDCs); and

searching for data in the repository data that is similar to the input data by comparing the IDC sand RDCs,

wherein each set of RDCs and IDCs is generated by;

applying a hash function to the respective input data chunk or repository data chunk to generate a plurality of hashes, each hash comprising a hash value and a hash position within the data chunk;

applying a first function to the plurality of generated hashes to identify a first subset of hashes distributed across the data chunk;

applying a second function to the hash positions of the hashes of the first subset to identify a second subset of the plurality of generated hashes; and

defining the second subset of hashes as the set of respective IDCs or RDCs.

2. The method of claim 1, wherein applying the second function comprises:

determining other hash positions as a fiinction of the hash positions of the hashes of the first subset; and

defining the hashes at the other hash positions as the second subset of hashes.

3. The method of claim 1, wherein the first function comprises one or more of:

selecting a number of the largest hash values;

selecting a number of the smallest hash values;

selecting a number of the hash values closest to a median value of the generated hash values for the corresponding data chunk;

selecting a number of the hash values closest to a constant value; and

selecting a number of the hash values closest to a percentile value of the generated hash values for the corresponding data chunk.

4. The method of claim 3, wherein the second function comprises:

applying a constant value to each hash position corresponding to each of the hashes of the first subset.

5. The method of claim 4, wherein:

an absolute value of the constant value is 1.

6. The method of claim 1, wherein:

in the step of comparing IDCs and RDCs, the number of RDCs in a set is less than the number of IDCs in a set.

7. The method of claim 1, wherein:

the searching is conducted by comparing less than all of the IDCs to the RDCs.

8. The method of claim 1, further comprising:

maintaining a searchable index of RDCs for the comparing step.

9. The method of claim 1, further comprising:

determining that a similarity exists if a similarity threshold is met.

10. The method of claim 1, wherein the comparing is conducted in a time independent of a size of the repository data and linear in a size of the input data.

11. The method of claim 1, further comprising:

determining at least one of the common and noncommon sections of the input data chunk and the repository data chunk determined to be similar using matching distinguishing characteristics to define corresponding intervals in the input data chunk and similar repository data chunk.

12. The method of claim 11, wherein the comparing is conducted in a time independent of a size of the repository data and linear in a size of the input data.

13. The method of claim 11, further comprising:

storing the noncommon sections of the input data in the repository.

14. A non-transitory computer-readable medium encoded with computer executable instructions that cause a computer to perform a method of searching in repository data for data that are similar to an input data, wherein the repository data is divided into one or more repository data chunks and the input data comprises a plurality of input data chunks, the medium comprising:

program code for generating a corresponding set of repository distinguishing characteristics (RDCs) for each repository data chunk;

program code for generating a set of input distinguishing characteristics (IDCs) for each input data chunk;

and program code for searching for data in the repository data that is similar to the input data by comparing the IDCs and RDCs,

wherein the program code for generating each set of IDCs and the program code for generating each set of RDCs comprises;

program code for applying a hash function to the respective input data chunk or repository data chunk to generate a plurality of hashes, each hash comprising a hash value and a hash position within the data chunk;

program code for applying a first function to the plurality of generated hashes to identify a first subset of hashes distributed across the data chunk;

program code for applying a second function to the hash positions of the hashes of the first subset to identify a second subset of the plurality of generated hashes;

and program code for defining the second subset of hashes as the set of respective IDCs or RDCs.

15. The computer-readable medium of claim 14, wherein the program code for applying the second function comprises:

program code for determining other hash positions as a function of the hash positions of the hashes of the first subset; and

program code for defining the hashes at the other hash positions as the second subset of hashes.

16. The computer-readable medium of claim 14, wherein the program code for applying the first function comprises one or more of:

program code for selecting a number of the largest hash values;

program code for selecting a number of the smallest hash values;

program code for selecting a number of the hash values closest to a median value of the generated hash values for the corresponding data chunk;

program code for selecting a number of the hash values closest to a constant value; and

program code for selecting a number of the hash values closest to a percentile value of the generated hash values for the corresponding data chunk.

17. The computer-readable medium of claim 16, wherein the program code for applying the second function comprises:

program code for applying a constant value to each hash position corresponding to each of the hashes of the first subset.

18. The computer-readable medium of claim 17, wherein:

an absolute value of the constant value is 1.

19. The computer-readable medium of claim 14, wherein:

in the program code for searching, the number of RDCs in a set is less than the number of IDCs in a set.

20. The computer-readable medium of claim 14, wherein:

the program code for searching for data in the repository data comprises program code for comparing less than all of the IDCs to the RDCs.

21. The computer-readable medium of claim 14, further comprising:

program code for maintaining a searchable index of RDCs.

22. The computer-readable medium of claim 14, further comprising:

program code for determining a similarity exists if a similarity threshold is met.

23. The computer-readable medium of claim 14, wherein the comparing is conducted in a time independent of a size of the repository data and linear in a size of the input data.

24. The computer-readable medium of claim 14, further comprising:

program code for determining at least one of common and noncommon sections of the input data chunk and the repository data chunk determined to be similar using the matching distinguishing characteristics to define corresponding intervals in the input data chunk and similar repository data chunk.

25. The computer-readable medium of claim 24, further comprising:

program code for storing the noncommon sections of the input data in the repository.

26. A system for searching in repository data for data that are similar to an input data, wherein the repository data is divided into one or more repository data chunks and the input data comprises a plurality of input data chunks, the system comprising:

a mechanism for, for each repository data chunk, generating a corresponding set of repository distinguishing characteristics (RDCs);

a mechanism for generating a corresponding set of input distinguishing characteristics (IDCs) for each input data chunk; and

a mechanism for searching for data in the repository data that is similar to the input data by comparing the IDCs and RDCs,

wherein the mechanism for generating the IDCs and the mechanism for generating the RDCs each comprises;

a mechanism for applying a hash function to the respective input data chunk or repository data chunk to generate a plurality of hashes, each hash comprising a hash value and a hash position within the data chunk;

a mechanism for applying a first function to the plurality of generated hashes to identify a first subset of hashes distributed across the data chunk;

a mechanism for applying a second function to the hash positions of the hashes of the first subset to identify a second subset of the plurality of generated hashes; and

a mechanism for defining the second subset of hashes as the set of respective IDCs or RDCs.

27. The system of claim 26, wherein the mechanism for applying the second function comprises:

mechanism for determining other hash positions as a function of the hash positions of the hashes of the first subset; and

mechanism for defining the hashes at the other hash positions as the second subset of hashes.

28. The system of claim 26, wherein the first function comprises one or more of:

selecting a number of the largest hash values;

selecting a number of the smallest hash values;

selecting a number of the hash values closest to a median value of the generated hash values for the corresponding data chunk;

selecting a number of the hash values closest to a constant value; and

selecting a number of the hash values closest to a percentile value of the generated hash values for the corresponding data chunk.

29. The system of claim 28, wherein the second function comprises:

applying a constant value to each hash position corresponding to each of the hashes of the first subset.

30. The system of claim 29, wherein:

an absolute value of the constant value is 1.

31. The system of claim 26, wherein:

in the mechanism for searching, the number of RDCs in a set is less than the number of IDCs in a set.

32. The system of claim 26, wherein:

the mechanism for searching for data in the repository data comprises mechanism for comparing less than all of the IDCs to the RDCs.

33. The system of claim 26, further comprising:

mechanism for maintaining an index of RDCs and the corresponding repository data chunk.

34. The system of claim 26, further comprising:

mechanism for determining that a similarity exists if a similarity threshold is met.

35. The system of claim 26, wherein the comparing is conducted in a time independent of a size of the repository data and linear in a size of the input data.

36. The system of claim 26, further comprising:

mechanism for determining at least one of common and noncommon sections of the input data chunk and the repository data chunk determined to be similar using the matching distinguishing characteristics to define corresponding intervals in the input data chunk and similar repository data chunk.

37. The system of claim 36, further comprising:

mechanism for storing the noncommon sections in the repository.