Methods and apparatus for content-aware data partitioning

• US 8,589,455 B2
• Filed: 12/18/2009
• Issued: 11/19/2013
• Est. Priority Date: 12/18/2008
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Copiun Incorporated (Blackberry Limited)
• Inventors: Jain, Sanjay, Chaudhry, Puneesh
• Primary Examiner(s): NGUYEN, KIM T
• Application Number:
  US12/642,033
• Publication Number:
  US 20100161685A1
• Time in Patent Office: 1,432 Days
• Field of Search: 707/812
• US Class Current: 707/812
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: Y10S 707/968 Partitioning
• CPC Class Codes: Y10S 707/969 Horizontal partitioning
• CPC Class Codes: Y10S 707/97 Vertical partitioning
• CPC Class Codes: Y10S 707/971 Federated
• CPC Class Codes: Y10S 707/972 Partitioning
• CPC Class Codes: Y10S 707/973 Horizontal partitioning
• CPC Class Codes: Y10S 707/974 Vertical partitioning

Abstract

The systems and methods partition digital data units in a content aware fashion without relying on any ancestry information, which enables one to find duplicate chunks in unrelated units of digital data even across millions of documents spread across thousands of computer systems.

Claims

1. A computer-implemented method for partitioning and storing a first file in a repository, said repository comprising a plurality of stored objects corresponding to a plurality of stored files, wherein each of said stored objects corresponds to one or more of said stored files, wherein said first file comprises a plurality of data objects and is different from each of said plurality of stored files, the method comprising:

determining a format of the first file;

identifying each of the data objects corresponding to the first file at least in part on the basis of the determined format; and

for each of said identified data objects;

processing said identified data object on the basis of the determined format in order to create a further data object, said processing comprising removing, at least in part, information relating to the identified format from said identified data object;

comparing the further data object with said plurality of stored objects in order to determine whether the further data object corresponds to one of said plurality of stored objects; and

storing the further data object in the repository in dependence on said comparison.

2. The method of claim 1, wherein the first file includes one of:

a compressed zip file;

a Personal Storage Table (PST) file;

a cabinet (cab) file;

an archive file;

an Exchange Database;

a Microsoft SQL Server database;

a Lotus Notes mailbox;

a SharePoint Repository and an EMC Documentum file.

3. The method of claim 1, further comprising assembling a first identified data object and a second identified data object in a contiguous form in dependence on said comparison.

4. The method of claim 1, wherein said processing of an identified first data object comprises the steps of decompressing and/or decrypting.

5. The method of claim 1, wherein said processing of an identified data object comprises the steps of removing data indicative of at least one of a page number, a slide number, a paragraph number, and a Microsoft Excel cell number.

6. The method of claim 1, wherein said processing of an identified data object comprises the steps of removing data indicative of a position of the identified data object in relation to the first file or in relation to a further identified data object.

7. The method of claim 1, wherein said processing of an identified data object comprises the steps of removing data indicative of at least one of:

an author name, a modified date/time, a revision identifier, total editing time, number of pages, number of characters, number of lines, number of paragraphs, and number of words.

8. The method of claim 1, the method comprising performing said comparison independently of information associating the plurality of stored blocks with the plurality of stored files.

9. The method of claim 1, further comprising storing data indicative of an association between a further data object and at least one of:

a position of the corresponding identified data object in relation to the first file, metadata associated with the first file or the determined format.

10. The method of claim 1, the method comprises generating an identifier associated with said further data object for use in said comparison.

11. The method of claim 10, wherein the identifier associated with the identified data object is generated on the basis of a checksum or a hash of the corresponding further data object.

12. The method of claim 1, further comprising transmitting data indicative of said further data object.

13. The method according to claim 1, wherein said processing of an identified data object comprises removing one or more of:

data indicative of position of the identified data object in relation to the first file;

metadata associated with the first file; and

data associated with the determined format.

14. A system comprising:

a memory comprising a plurality of stored objects corresponding to a plurality of stored files; and

a processor configured to;

determine a format of a first file, wherein said first file comprises a plurality of data objects and is different from each of said plurality of stored files;

identify each of the data objects corresponding to the first file at least in part on the basis of the determined format;

for each of said identified objects;

process said identified data object on the basis of the determined format in order to create a further data object, said processing comprising removing, at least in part, information relating to the identified format from said identified data object;

compare said identified data object with said plurality of stored objects in order to determine whether the further data object corresponds to one of said plurality of stored data objects; and

store the further data object in the memory in dependence on said comparison.

15. The system of claim 14, wherein the first file includes one of:

a compressed zip file;

a Personal Storage Table (PST) file;

a cabinet (cab) file;

an archive file;

an Exchange Database;

a Microsoft SQL Server database;

a Lotus Notes mailbox;

a SharePoint Repository and an EMC Documentum file.

16. The system of claim 14, further comprising assembling an identified data object and a second identified data object in a contiguous form in dependence on said comparison.

17. The system of claim 14, wherein said processing of an identified data object comprises the steps of decompressing and/or decrypting.

18. The system of claim 14, wherein said processing of an identified data object comprises the steps of removing data indicative of at least one of a page number, a slide number, a paragraph number, and a Microsoft Excel cell number.

19. The system of claim 14, wherein said processing of an identified data object comprises the steps of removing data indicative of a position of the identified data object in relation to the first file or in relation to a further identified data object.

20. The system of claim 14, wherein said processing of an identified data object comprises the steps of removing data indicative of at least one of:

an author name, a modified date/time, a revision identifier, total editing time, number of pages, number of characters, number of lines, number of paragraphs, and number of words.

21. The system of claim 14, the method comprising performing said comparison independently of information associating the plurality of stored blocks with the plurality of stored files, and performing said comparison independently of information associating the plurality of stored blocks with the plurality of stored files.

22. The system of claim 14, further comprising storing data indicative of an association between said further data object and at least one of:

a position of the corresponding identified data object in relation to the first file, metadata associated with the first file or the determined format.

23. The system of claim 14, wherein generating an identifier associated with a further data object for use in said comparison.

24. The system of claim 23, wherein the identifier associated with the further data object is generated on the basis of a checksum or a hash of the corresponding further data object.

25. The system of claim 14, further comprising transmitting data indicative of said further data object.

26. The system of claim 14, wherein said processing of an identified data object comprises removing one or more of:

data indicative of position of the identified data object in relation to the first file;

metadata associated with the first file; and

data associated with the determined format.

27. A computer-implemented method for partitioning and storing a first file in a repository, said repository comprising a plurality of stored objects corresponding to a plurality of stored files, wherein the first file comprises a plurality of data objects and is different from each of said plurality of stored files, the method comprising:

determining a format of the first file;

identifying each of the data objects corresponding to the first file at least in part on the basis of the determined format;

for each of said identified data objects;

processing said identified data object on the basis of the determined format in order to create a further data object, said processing comprising removing, at least in part, information relating to the identified format from said identified data object;

comparing the further data object with said plurality of stored objects in order to determine whether the further data object corresponds to one of said plurality of stored objects;

storing the further data object in the repository in dependence on said comparison; and

storing data indicative of an association between the further data object and the first file in the repository, said data indicative of said association comprising data indicative of at least one of;

a position of the identified data object corresponding to the further data object in relation to the first file, metadata associated with the first file and the determined format.

28. A system comprising:

a memory comprising a plurality of stored objects corresponding to a plurality of stored files; and

a processor configured to;

determine a format of a first file, wherein said first file comprises a plurality of data objects and is different from each of said plurality of stored files;

identify each of said data objects corresponding to the first file at least in part on the basis of the determined format;

for each of the identified data objects;

process the identified data object on the basis of the determined format in order to create a further data object, said processing comprising removing, at least in part, information relating to the identified format from said identified data object;

compare the further data object with said plurality of stored objects in order to determine whether the further data object corresponds to one of said plurality of stored data objects;

store the further data object in the repository in dependence on said comparison; and

store data indicative of an association between the further data object and the first file in the repository, said data indicative of said association comprising data indicative of at least one of;

a position of the identified data object corresponding to the further data object in relation to the first file, metadata associated with the first file and the determined format.