Systems and Methods for Efficient Data Searching, Storage and Reduction

• US 20090228456A1
• Filed: 03/20/2009
• Published: 09/10/2009
• Est. Priority Date: 09/15/2004
• Status: Abandoned Application

• 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
• Application Number:
  US12/407,789
• Publication Number:
  US 20090228456A1
• 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-177. -177. (canceled)

178. A method of searching in repository data for data that are similar to an input data, wherein the repository data comprises a plurality of repository data chunks each having a corresponding set of repository distinguishing characteristics (RDCs), the method comprising:

calculating a set of input distinguishing characteristics (IDCs) for each input data chunk by;

selecting IDCs that are robust with respect to modifications of the corresponding input data chunk; and

ordering the selected IDCs in a first order;

determining a similarity threshold value N; and

for each set of IDCs;

determining, in the first order, if an IDC is found among the RDCs; and

when a number j of IDCs found among the RDCs is at least N, then determining that the input data chunk corresponding to the set of IDCs is similar to at least one repository data chunk in the repository.

179. The method of claim 178, further comprising:

calculating k IDCs in each set of IDCs, where k>

N; and

when the number j is at least N, stopping the determination even if not all k IDCs have been checked.

180. The method of claim 178, wherein a number k of IDCs is in each set of IDCs, the method further comprising:

if all k IDCs in the set have been checked and if the number j of IDCs found among the RDCs is less than N, then adding the corresponding input data chunk and its corresponding first N IDCs to the repository.

181. The method of claim 178, further comprising:

determining at least one of common and noncommon sections of the input data chunk and a 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.

182. The method of claim 178, wherein calculating a set of IDCs comprises:

selecting the first k IDCs as the set of IDCs, wherein k>

N.

183-186. -186. (canceled)