Systems and Methods for Efficient Data Searching, Storage and Reduction

• US 20090234855A1
• 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: Aronovich, Lior, Bitner, Haim, Asher, Ron, Hirsch, Michael, Klein, Shmuel T., Bachmat, Eitan
• Granted Patent: US 9,400,796 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-59. -59. (canceled)

60. A method of searching a repository of binary uninterpretted data for a location of common data to an input data comprising:

analyzing segments of each of the repository and input data to determine a repository segment that is similar to an input segment, the analyzing step including searching an index of representation values of the repository data for matching representation values of the input in a time independent of a size of the repository and linear in a size of the input data; and

analyzing the similar repository segment with respect to the input segment to determine their common data sections while utilizing at least some of the matching representation values for data alignment, in a time linear in a size of the input segment.

63. The method of claim 60, wherein the index is stored in a memory faster than a memory storing the repository itself.

64. The method of claim 63, wherein the searching involves only the faster memory.

65. The method of claim 60, wherein the searching time and memory are substantially independent of repository size.

66. The method of claim 60, wherein the representation values are such that the number of matches indicates a degree of similarity.

67. The method of claim 60, where in the similarity searching includes a threshold number of matching representation values for a declared similarity.

68. The method of claim 67, wherein the threshold varies in response to a statistical analysis of prior results of the searching step.

69. The method of claim 67, including a step of verifying the declared similarity.

70. The method of claim 60, wherein the index includes a location within the repository of the similarity matched segment.

71. The method of claim 67, including a step of acting upon a declared similarity by matching the similar data repository data.

72. The method of claim 60, including a step of data compression.

73. The method of claim 60, including a step of updating the repository and the index.

61-62. -62. (canceled)

74-186. -186. (canceled)