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

• US 20060059207A1
• Filed: 07/29/2005
• Published: 03/16/2006
• Est. Priority Date: 09/15/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Diligent Technologies Corporation (International Business Machines Corporation)
• Inventors: Bitner, Haim, Asher, Ron, Aronovich, Lior, Hirsch, Michael, Klein, Shmuel T., Bachmat, Eitan
• Granted Patent: US 8,725,705 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method, comprising:

at a first location, determining a set of distinguishing characteristics associated with the first data;

transmitting the determined set of first data distinguishing characteristics from the first location to a remote location;

at a remote location, comparing the determined set of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics to identify remote data stored at the remote location that is similar to the first data, wherein similarity is a function of a similarity threshold; and

determining one or more differences between the first data and the identified similar remote data,

wherein, once similar remote data has been identified, any differences between the first data and the identified similar remote data are determined 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.

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 1, wherein:

the first location is a first computer and the remote location is a remote computer different form 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.

5. 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.

6. 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 different from the remote location; and

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

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

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

8. The method of claim 6, 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.

9. The method of claim 6, 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.

10. The method of claim 1, wherein the similarity threshold is met when a predetermined number of the distinguishing characteristics in the set of first data distinguishing characteristics are found in a set of remote data distinguishing characteristics.

11. The method of claim 10, wherein determining a set of distinguishing characteristics comprises:

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

12. The method of claim 11, further comprising:

determining the k largest mathematical hash values in a set, k being a predetermined number;

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

determining a set of distinguishing characteristics to be the mathematical hash values of a next sequential data portion relative to each data portion corresponding to the k largest mathematical hash values.

13. A method, comprising:

receiving, at a remote location, a set of first data distinguishing characteristics from a first location, the set of first data distinguishing characteristics associated with first data as determined at the first location;

at the remote location, comparing the set of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics to identify remote data stored at the remote location that is similar to the first data, wherein similarity is a function of a similarity threshold; and

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

wherein, once similar remote data has been identified, the differences between the first data and the identified similar remote data are determined without all of the first data being received at the remote location.

14. The method of claim 13, wherein:

once similar remote data has been identified, 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.

15. The method of claim 13, wherein the similarity threshold is met when a predetermined number of the distinguishing characteristics in the set of first data distinguishing characteristics are found in a set of remote data distinguishing characteristics.

16. The method of claim 13, further comprising:

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

17. A method, comprising:

receiving, at a remote location, a set of first data distinguishing characteristics from a first location, the set of first data distinguishing characteristics associated with first data as determined at the first location;

at the remote location, comparing the set of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics to identify remote data stored at the remote location that is similar to the first data, wherein similarity is a function of a similarity threshold; and

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

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

19. The method of claim 17, wherein the similarity threshold is met when a predetermined number of the distinguishing characteristics in the set of first data distinguishing characteristics are found in a set of remote data distinguishing characteristics.

20. A system, comprising:

means for determining, at a first location, a set of distinguishing characteristics associated with the first data;

means for transmitting the determined set of first data distinguishing characteristics from the first location to a remote location;

means for comparing, at a remote location, the determined set of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics to identify remote data stored at the remote location that is similar to the first data, wherein similarity is a function of a similarity threshold; and

means for determining one or more differences between the first data and the identified similar remote data,

wherein, once similar remote data has been identified, any differences between the first data and the identified similar remote data are determined 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.

21. The system of claim 20, further comprising:

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

22. The system of claim 20, wherein the means for determining one or more differences between the first data and the identified similar remote data comprises:

means for determining a reference label for the identified similar remote data;

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

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

23. The system of claim 20, wherein:

the first location is a first computer and the remote location is a remote computer different form 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.

24. The system of claim 20, wherein the means for determining one or more differences between the first data and the identified similar remote data comprises means for operating a remote differencing procedure.

25. The system of claim 22, further comprising:

means for 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; and

means for recreating, at the second location, the first data as a function of the differing portions and the identified similar remote data.

26. The system of claim 25, wherein the means for recreating the first data comprises:

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

27. The system of claim 25, wherein the means for recreating the first data comprises:

means for 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.

28. The system of claim 25, 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.

29. The system of claim 20, wherein the similarity threshold is met when a predetermined number of the distinguishing characteristics in the set of first data distinguishing characteristics are found in a set of remote data distinguishing characteristics.

30. The system of claim 29, wherein the means for determining a set of data distinguishing characteristics comprises:

means for calculating a mathematical hash value of each portion of respective data.

31. The system of claim 30, further comprising:

means for determining the k largest mathematical hash values in a set, k being a predetermined number;

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

means for determining a set of distinguishing characteristics to be the mathematical hash values of a next sequential data portion relative to each data portion corresponding to the k largest mathematical hash values.

32. A system, comprising:

means for receiving, at a remote location, a set of first data distinguishing characteristics from a first location, the set of first data distinguishing characteristics associated with first data as determined at the first location;

means for comparing, at the remote location, the set of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics to identify remote data stored at the remote location that is similar to the first data, wherein similarity is a function of a similarity threshold; and

means for 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,

wherein, once similar remote data has been identified, the differences between the first data and the identified similar remote data are determined without all of the first data being received at the remote location.

33. The system of claim 32, wherein:

once similar remote data has been identified, 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.

34. The system of claim 32, wherein the similarity threshold is met when a predetermined number of the distinguishing characteristics in the set of first data distinguishing characteristics are found in a set of remote data distinguishing characteristics.

35. The system of claim 32, further comprising:

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

36. A system, comprising:

means for receiving, at a remote location, a set of first data distinguishing characteristics from a first location, the set of first data distinguishing characteristics associated with first data as determined at the first location;

means for comparing, at the remote location, the set of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics to identify remote data stored at the remote location that is similar to the first data, wherein similarity is a function of a similarity threshold; and

means for 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.

37. The system of claim 36, wherein the means for determining one or more differences between the first data and the identified similar remote data comprises means for operating a remote differencing procedure.

38. The system of claim 36, wherein the similarity threshold is met when a predetermined number of the distinguishing characteristics in the set of first data distinguishing characteristics are found in a set of remote data distinguishing characteristics.

39. 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;

receiving a set of first data distinguishing characteristics from a first location, the set of first data distinguishing characteristics associated with first data as determined at the first location;

comparing the set of first data distinguishing characteristics to one or more sets of local data distinguishing characteristics to identify local data stored in the local data repository that is similar to the first data, wherein similarity is a function of a similarity threshold; and

via communication with the first location, determining one or more differences between the first data and the identified similar local data,

wherein, once similar local data has been identified, the differences between the first data and the identified similar local data are determined without receiving all of the first data at the local data repository.

40. The system of claim 39, wherein:

once similar local data has been identified, 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.

41. The system of claim 39, wherein the similarity threshold is met when a predetermined number of the distinguishing characteristics in the set of first data distinguishing characteristics are found in a set of local data distinguishing characteristics.

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

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

43. A computer-readable medium encoded with a computer program that causes a computer to perform a method comprising:

receiving, at a local location, a set of first data distinguishing characteristics from a first location, the set of first data distinguishing characteristics associated with first data as determined at the first location;

comparing the set of first data distinguishing characteristics to one or more sets of local data distinguishing characteristics to identify local data stored at a local repository that is similar to the first data, wherein similarity is a function of a similarity threshold; and

determining, via communication with the first location, one or more differences between the first data and the identified similar local data,

wherein, once similar local data has been identified, the differences between the first data and the identified similar local data are determined without all of the first data being received at the local location.

44. The method of claim 43, wherein:

once similar local data has been identified, 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.

45. The method of claim 43, wherein the similarity threshold is met when a predetermined number of the distinguishing characteristics in the set of first data distinguishing characteristics are found in a set of local data distinguishing characteristics.

46. The method of claim 43, further comprising:

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