Systems and Methods for Efficient Data Searching, Storage and Reduction

• US 20090234821A1
• Filed: 03/19/2009
• Published: 09/17/2009
• Est. Priority Date: 09/15/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bitner, Haim, Asher, Ron, Aronovich, Lior, Hirsch, Michael, Klein, Shmuel T., Bachmat, Eitan
• Granted Patent: US 8,275,755 B2
• Time in Patent Office: Days
• 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-30. -30. (canceled)

31. A method enabling lossless data reduction by partitioning version data into:

a) data already stored in a repository; and

b) data not already stored in the repository;

wherein, each of the repository data and the version data comprise a plurality of data chunks, and wherein the method comprises;

storing in an index a plurality of n distinguishing characteristics (RDCs) and a position in the repository of each of a plurality of repository chunks, where n is substantially smaller than size m of the repository chunk; and

for each version chunk

determining a plurality of k distinguishing characteristics (IDCs) of the version chunk, where k is greater than or equal to n;

determining whether a similar repository chunk exists based on a plurality of matching distinguishing characteristics in the version chunk and similar repository chunk, wherein the similarity determination includes searching for each of the k distinguishing characteristics of the version chunk in the index until at most n matches are found;

determining that one or more similar repository chunks exist where the number of matches satisfies a threshold;

determining differences between the version chunk and similar repository chunk by comparing the full data of the respective chunks; and

storing the differences in the repository.

33. The method of claim 31, wherein the determining differences step includes use of a method selected from the group consisting of binary difference and byte-wise factoring.

36. The method of claim 31, wherein the index includes a location in the repository of the distinguishing characteristics of the repository chunk.

39. The method of claim 31, where in the determining similar repository chunk step includes searching until at least two matching distinguishing characteristics are found for the version chunk and one or more repository chunks.

40. The method of claim 31, wherein the distinguishing characteristics are determined by a hash function.

41. The method of claim 40, wherein the distinguishing characteristics are determined by a rolling hash function.

42. The method of claim 41, wherein the distinguishing characteristics are determined by a modular hash function.

43. The method of claim 31, wherein the index is stored as a binary tree, a B tree, a sorted list, or a hash table.

44. The method of claim 43, wherein the index is stored as a hash table.

45. The method of claim 31, wherein pointers are provided to data of the version chunk already stored in the repository.

46. The method of claim 31, wherein the repository and version chunks each comprise a plurality of seeds, each seed being a consecutive sequence of base elements and having the same seed size s, and wherein the distinguishing characteristics are hash values of a selected subset of the seeds of the respective chunk.

47. The method of claim 46, wherein the seeds comprise overlapping seeds.

48. The method of claim 31, wherein the method is used for data factoring.

49. The method of claim 31, wherein the method is used for data backup.

50. The method of claim 31, wherein the method is used for data backup with a data repository of a size for storing up to one or more petabytes of data.

51. The method of claim 31, wherein the determining similar repository chunk step is conducted in a time independent of a size of the repository and linear in a size of the version data.

52. The method of claim 31, wherein a ratio of space needed to store the repository chunk to space needed to store the distinguishing characteristics of the repository chunk is up to 250,000:

1.

54. The method of claim 31, wherein the method includes modifying the index to include a selected n of the k distinguishing characteristics of the version chunk.

55. The method of claim 54, wherein the method includes modifying the repository to include the differences.

32. (canceled)

34-35. -35. (canceled)

37-38. -38. (canceled)

53. (canceled)

56-186. -186. (canceled)