Systems and methods for searching of storage data with reduced bandwidth requirements

• US 8,725,705 B2
• Filed: 07/29/2005
• Issued: 05/13/2014
• Est. Priority Date: 09/15/2004
• Status: Expired due to Fees

• 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): PHAM, KHANH B
• Application Number:
  US11/194,086
• Publication Number:
  US 20060059207A1
• Time in Patent Office: 3,210 Days
• Field of Search: 707/698
• US Class Current: 707/698
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/90344 by using string matching techniques

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. Additionally, remote operations are accomplished with significantly reduced system bandwidth by implementing remote differencing operations.

Claims

1. A computer-implemented method, comprising a similarity search followed by an identity comparison:

the similarity search comprising;

at a first location, using a first computer to determine a set of first data distinguishing characteristics associated with each of a plurality of first data chunks of first data stored at the first location, wherein determining the set of first data distinguishing characteristics associated with each first data chunk includes;

calculating a mathematical hash value of each portion of respective data;

determining a subset of k hash values from the calculated mathematical hash values, k being a predetermined number that is smaller than a total number of the calculated mathematical hash values calculated for each portion of the respective data;

identifying a respective data portion for each of the k hash values;

identifying a data portion shifted by a predetermined amount relative to each respective data portion corresponding to the k hash values;

determining a mathematical hash value for each shifted data portion from the calculated mathematical hash values; and

setting the set of first data distinguishing characteristics to be the mathematical hash values for each of the shifted data portions to obtain a more uniform probabilistic distribution than would be obtained using the data portions corresponding to the k hash values;

transmitting the determined sets of first data distinguishing characteristics from the first location to a remote location different than the first location;

at the remote location, using a remote computer to compare a plurality of the determined sets of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics, and to identify one or more remote data chunks of remote data stored at the remote location that are similar to the first data based on the comparison, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold; and

the identity comparison comprising;

using the determined similar data chunks, determining one or more differences between the first data and the identified similar remote data, without transmitting all of the first data to the remote location and without transmitting all of the identified similar remote data to the first location.

2. The method of claim 1, further comprising:

updating the remote location with the one or more determined differences, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced.

3. The method of claim 1, wherein determining one or more differences between the first data and the identified similar remote data comprises:

determining a reference label for the identified similar remote data;

identifying locations of one or more portions of the identified similar remote data that differ from the first data; and

determining a respective first data portion for each identified differing portion in the remote data.

4. The method of claim 3, further comprising:

transmitting the determined reference label, the locations of the differing portions and the respective first data portions from the first location to a second location that is different from the remote location and is also different from the first location; and

a third computer at the second location recreating the first data as a function of the differing portions and the identified similar remote data.

5. The method of claim 4, wherein recreating the first data comprises:

the second location retrieving the entire identified similar remote data from the remote location.

6. The method of claim 4, wherein recreating the first data comprises:

the second location retrieving from the remote location only those portions of the identified similar remote data that are the same as the first data.

7. The method of claim 4, the first and second computers being in networked communication with one another.

8. The method of claim 1, wherein:

the remote computer is different from the first computer, the first and remote computers being in networked communication with one another; and

the remote data is stored in a data repository accessed only through the remote computer.

9. The method of claim 1, wherein determining one or more differences between the first data and the identified similar remote data comprises operation of a remote differencing procedure.

10. The method of claim 1, wherein a number n of the first distinguishing characteristics in each subset is less than k.

11. The method of claim 1, wherein the subset of k hash values are selected based on:

k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values so that the set of distinguishing characteristics are robust and well spread over the first data chunk.

12. The method of claim 11, wherein each set of first data distinguishing characteristics associated with the associated first data chunk has no more than n distinguishing characteristics, wherein n<

k.

13. The method of claim 1, further comprising determining the one or more sets of remote data distinguishing characteristics, wherein determining each set of remote data distinguishing characteristics includes calculating a mathematical hash value of each portion of data in the remote data chunk, and selecting a subset of the calculated hash values as the set of distinguishing characteristics for the remote data chunk, the subset being less than all of the calculated mathematical hash values.

14. The method of claim 13, wherein the subset of hash values associated with the remote data are selected based on:

k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of remote data distinguishing characteristics associated with each remote data chunk has no more than n distinguishing characteristics, wherein n≦

k.

15. The method of claim 1, wherein the subset of hash values are selected based on at least one of maximum hash values, minimum hash values, hash values closest to a median of all the hash values, hash values closest to a predetermined constant, or a sum of pairs of hash values.

16. The method of claim 15, wherein the selection of the subset further includes applying a positional shift to the data positions of a first selected subset of hash values, to determine second data portions, wherein the hash values of the second data portions are the set of distinguishing characteristics.

17. A computer-implemented method comprising a similarity search followed by an identity comparison:

the similarity search comprising;

receiving, at a remote location, sets of first data distinguishing characteristics from a first location different than the remote location, the sets of first data distinguishing characteristics comprising a set of distinguishing characteristics associated with each of a plurality of first data chunks of first data stored at the first location;

at the remote location, using a remote computer to determine one or more sets of remote data distinguishing characteristics, wherein determining each set of remote data distinguishing characteristics includes;

calculating a mathematical hash value of each portion of data in the remote data chunk;

determining a subset of k hash values from the calculated mathematical hash values, k being a predetermined number that is smaller than a total number of the calculated mathematical hash values calculated for each portion of the respective data;

identifying a respective data portion for each of the k hash values;

identifying a data portion shifted by a predetermined amount relative to each respective data portion corresponding to the k hash values;

determining a mathematical hash value for each shifted data portion from the calculated mathematical hash values; and

setting the one or more sets of remote data distinguishing characteristics to be the mathematical hash values for each of the shifted data portions, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced;

at the remote location, using the remote computer to compare a plurality of the sets of first data distinguishing characteristics to the one or more sets of remote data distinguishing characteristics, and to identify one or more remote data chunks of remote data stored at the remote location that are similar to the first data based on the comparison, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold; and

the identity comparison comprising;

using the determined similar data chunks, determining via communication between the first location and the remote location, one or more differences between the first data and the identified similar remote data, without all of the first data being received at the remote location.

18. The method of claim 17, wherein:

the differences between the first data and the identified similar remote data are determined without transmitting all of the identified similar remote data from the remote location to the first location.

19. The method of claim 17, wherein the subset of hash values associated with the remote data are selected based on:

k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of remote data distinguishing characteristics associated with each remote data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the remote data.

20. The method of claim 17, further comprising:

updating the remote system with the one or more determined differences.

21. A computer-implemented method comprising a similarity search followed by an identity comparison:

the similarity search comprising;

receiving, at a remote location, sets of first data distinguishing characteristics from a first location different than the remote location, the sets of first data distinguishing characteristics comprising a set of distinguishing characteristics associated with each of a plurality of first data chunks of first data stored at the first location;

at the remote location, using a remote computer to determine one or more sets of remote data distinguishing characteristics, wherein determining each set of remote data distinguishing characteristics includes;

calculating a mathematical hash value of each portion of data in the remote data chunk;

determining a subset of k hash values from the calculated mathematical hash values, k being a predetermined number that is smaller than a total number of the calculated mathematical hash values calculated for each portion of the respective data;

identifying a respective data portion for each of the k hash values;

identifying a data portion shifted by a predetermined amount relative to each respective data portion corresponding to the k hash values;

determining a mathematical hash value for each shifted data portion from the calculated mathematical hash values; and

setting the one or more sets of remote data distinguishing characteristics to be the mathematical hash values for each of the shifted data portions, wherein a predetermined minimum geographic and/or positional spread between the distinguishing characteristics is enforced;

at the remote location, using the remote computer to compare a plurality of the sets of first data distinguishing characteristics to the one or more sets of remote data distinguishing characteristics, and to identify one or more remote data chunks of remote data stored at the remote location that are similar to the first data based on the comparison, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold,

wherein the subset of hash values associated with the remote data are selected based on;

k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values,

wherein each set of remote data distinguishing characteristics associated with each remote data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the remote data; and

the identity comparison comprising;

using the determined similar data chunks, determining via communication between the first location and the remote location, one or more differences between the first data and the identified similar remote data.

22. The method of claim 21, wherein determining one or more differences between the first data and the identified similar remote data comprises operation of a remote differencing procedure.

23. The method of claim 21, wherein the subset of k hash values are selected based on k maximum hash values or k minimum hash values.

24. The method of claim 21, wherein the set of distinguishing characteristics is a subset of hash values generated from the respective data.

25. The method of claim 24, wherein the subset comprises substantially uniformly distributed numbers on a range of numbers.

26. A computer-readable storage medium encoded with instructions that causes a computer to perform a method comprising a similarity search followed by an identity comparison:

the similarity search comprising;

determining, at a first location, a set of first data distinguishing characteristics associated with each of a plurality of first data chunks of first data, wherein determining each set of first data distinguishing characteristics includes;

calculating a mathematical hash value of each portion of data in the first data chunk;

determining a subset of k hash values from the calculated mathematical hash values, k being a predetermined number that is smaller than a total number of the calculated mathematical hash values calculated for each portion of the respective data;

identifying a respective data portion for each of the k hash values;

identifying a data portion shifted by a predetermined amount relative to each respective data portion corresponding to the k hash values;

determining a mathematical hash value for each shifted data portion from the calculated mathematical hash values; and

setting the set of first data distinguishing characteristics for the first data chunk to be the mathematical hash values for each of the shifted data portions, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced;

transmitting the determined sets of first data distinguishing characteristics from the first location to a remote location different than the first location;

comparing, at a remote location, a plurality of the determined sets of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics, and identifying one or more remote data chunks of remote data stored at the remote location that are similar to the first data based on the comparison, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold; and

the identity comparison comprising;

using determined similar data chunks, determining one or more differences between the first data and the identified similar remote data, without transmitting all of the first data to the remote location and without transmitting all of the identified similar remote data to the first location.

27. The medium of claim 26, further comprising:

updating the remote location with the one or more determined differences.

28. The medium of claim 26, wherein the determining one or more differences between the first data and the identified similar remote data comprises:

determining a reference label for the identified similar remote data;

identifying locations of one or more portions of the identified similar remote data that differ from the first data; and

determining a respective first data portion for each identified differing portion in the remote data.

29. The medium of claim 28, further comprising:

transmitting the determined reference label, the locations of the differing portions and the respective first data portions from the first location to a second location that is different from the remote location and is also different from the first location; and

recreating, using a third computer at the second location, the first data as a function of the differing portions and the identified similar remote data.

30. The medium of claim 29, wherein the recreating the first data comprises:

retrieving, at the second location, the entire identified similar remote data from the remote location.

31. The medium of claim 29, wherein the recreating the first data comprises:

retrieving, at the second location, from the remote location only those portions of the identified similar remote data that are the same as the first data.

32. The medium of claim 29, wherein the first location is a first computer and the second location is at a second computer different from the first computer, the first and second computers being in networked communication with one another.

33. The medium of claim 26, wherein the subset of hash values associated with the first data are selected based on:

k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of first data distinguishing characteristics associated with each first data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the first data.

34. The medium of claim 26, wherein the determining one or more differences between the first data and the identified similar remote data comprises operating a remote differencing procedure.

35. The medium of claim 26, wherein the set of distinguishing characteristics are robust and well spread over the chunk.

36. The medium of claim 26, wherein the subset of k hash values are selected based on k maximum hash values or k minimum hash values so that the set of distinguishing characteristics are robust and well spread over the first data chunk.

37. The medium of claim 26, wherein the subset of k hash values are selected based on:

k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values so that the set of distinguishing characteristics are robust and well spread over the first data chunk.

38. A computer-readable storage medium encoded with instructions that causes a computer to perform a method comprising a similarity search followed by an identity comparison:

the similarity search comprising;

receiving, at a remote location, sets of first data distinguishing characteristics from a first location, the sets of first data distinguishing characteristics comprising a set of distinguishing characteristics associated with each of the plurality of first data chunks of first data stored at the first location;

determining one or more sets of remote data distinguishing characteristics, wherein determining each set of remote data distinguishing characteristics includes;

calculating a mathematical hash value of each portion of data in the remote data chunk;

determining a subset of k hash values from the calculated mathematical hash values, k being a predetermined number that is smaller than a total number of the calculated mathematical hash values calculated for each portion of the respective data;

identifying a respective data portion for each of the k hash values;

identifying a data portion shifted by a predetermined amount relative to each respective data portion corresponding to the k hash values;

determining a mathematical hash value for each shifted data portion from the calculated mathematical hash values; and

setting the set of first data distinguishing characteristics for the remote data chunk to be the mathematical hash values for each of the shifted data portions, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced;

comparing, at the remote location using a remote computer, a plurality of the sets of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics, and identifying one or more remote data chunks of remote data stored at the remote location that are similar to the first data, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold; and

the identity comparison comprising;

using the determined similar data chunks, determining via communication between the first location and the remote location, one or more differences between the first data and the identified similar remote data, without all of the first data being received at the remote location.

39. The medium of claim 38, wherein:

the differences between the first data and the identified similar remote data are determined without transmitting all of the identified similar remote data from the remote location to the first location.

40. The medium of claim 38, wherein the subset of hash values associated with the remote data are selected based on:

k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of remote data distinguishing characteristics associated with each remote data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the remote data.

41. The medium of claim 38, further comprising:

updating the remote location with the one or more determined differences.

42. A system, comprising:

a processor;

a memory coupled to the processor; and

a local data repository coupled to the processor,

wherein the processor and the memory are configured to perform a method comprising a similarity search followed by an identity comparison;

the similarity search comprising;

receiving sets of first data distinguishing characteristics from a first location, the sets of first data distinguishing characteristics comprising a set of distinguishing characteristics associated with each of a plurality of first data chunks of first data stored at the first location;

determining one or more sets of local data distinguishing characteristics, wherein determining each set of local data distinguishing characteristics includes;

calculating a mathematical hash value of each portion of data in local data chunk;

determining a subset of k hash values from the calculated mathematical hash values, k being a predetermined number that is smaller than a total number of the calculated mathematical hash values calculated for each portion of the data in the local data chunk;

identifying a respective data portion for each of the k hash values;

identifying a data portion shifted by a predetermined amount relative to each respective data portion corresponding to the k hash values;

determining a mathematical hash value for each shifted data portion from the calculated mathematical hash values; and

setting the mathematical hash values for each of the shifted data portions to be the set of distinguishing characteristics for the local data chunk to obtain a more uniform probabilistic distribution than would be obtained using the data portions corresponding to the k hash values, wherein the one or more sets of local distinguishing characteristics are robust and well spread over the local data chunk;

comparing a plurality of the sets of first data distinguishing characteristics to one or more sets of the local data distinguishing characteristics to identify one or more local data chunks of local data stored in the local data repository that are similar to the first data, wherein the one or more local data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and local chunks which exceeds a similarity threshold; and

the identity comparison comprising;

using the determined similar data chunks, determining via communication with the first location, one or more differences between the first data and the identified similar local data without receiving all of the first data at the local data repository.

43. The system of claim 42, wherein:

the differences between the first data and the identified similar local data are determined without transmitting all of the identified similar local data to the first location.

44. The system of claim 42, wherein the subset of hash values associated with the local data are selected based on:

k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of local data distinguishing characteristics associated with each local data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the local data.

45. The system of claim 42, wherein the method further comprises:

updating the local data repository with the one or more determined differences.

46. A computer-readable storage medium encoded with instructions that causes a computer to perform a method comprising a similarity search followed by an identity comparison:

the similarity search comprising;

receiving, at a local location, sets of first data distinguishing characteristics from a first location, the sets of first data distinguishing characteristics comprising a set of distinguishing characteristics associated with each of a plurality first data chunks of first data stored at the first location;

determining one or more sets of local data distinguishing characteristics, wherein determining each set of local data distinguishing characteristics includes;

calculating a mathematical hash value of each portion of data in the local data chunk;

determining a subset of k hash values from the calculated mathematical hash values, k being a predetermined number that is smaller than a total number of the calculated mathematical hash values calculated for each portion of the data in the local data chunk;

identifying a respective data portion for each of the k hash values;

identifying a data portion shifted by a predetermined amount relative to each respective data portion corresponding to the k hash values;

determining a mathematical hash value for each shifted data portion from the calculated mathematical hash values; and

setting the mathematical hash values for each of the shifted data portions to be the set of data distinguishing characteristics for the local data chunk, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced;

comparing a plurality of the sets of first data distinguishing characteristics to one or more sets of local data distinguishing characteristics to identify one or more local data chunks of local data stored at a local repository that are similar to the first data, wherein the one or more local data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and local chunks which exceeds a similarity threshold; and

the identity comparison comprising;

using the determined similar data chunks determining via communication with the first location, one or more differences between the first data and the identified similar local data, all of the first data being received at the local location.

47. The medium of claim 46, wherein:

the differences between the first data and the identified similar local data are determined without transmitting all of the identified similar local data to the first location.

48. The medium of claim 46, wherein a more uniform probabilistic distribution is obtained than would be obtained using the data portions corresponding to the k hash values.

49. The medium of claim 46, further comprising:

updating the local repository with the one or more determined differences.