METHODS AND APPARATUS FOR CONTENT-AWARE DATA PARTITIONING

• US 20100161685A1
• Filed: 12/18/2009
• Published: 06/24/2010
• 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
• Granted Patent: US 8,589,455 B2
• Time in Patent Office: Days
• 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 digital data comprising:

determining a format of the digital data;

identifying a source logical object within the digital data, wherein the identification of the source logical object is accomplished at least in part by applying knowledge about the format of the digital data;

based on the determined format, performing one or more of the following operations to create a resulting object;

removing position-dependent data from the source logical object,

removing instance-dependent data from the source logical object,

removing one or more format-specific headers or footers from the source logical object, and

removing format-specific transformations from the source logical object;

determining whether the resulting object has already been stored; and

storing the resulting object if the resulting object has not already been stored.

2. The method of claim 1, wherein the digital data is at least one of a digital file, block based storage, binary large object (BLOB), and a data stream.

3. The method of claim 2, wherein the digital data includes a compound file, and the source logical object is stored in a file within the compound file.

4. The method of claim 3, wherein the compound file includes one of a .zip, .pst, .cab, .a, Exchange Database, Microsoft SQL Server database, Lotus Notes mailbox, SharePoint Repository, and EMC Documentum file.

5. The method of claim 1, further comprising assembling the source logical object in a contiguous form based on an instance of the source logical object that is stored across multiple storage blocks.

6. The method of claim 1, wherein at least one of the format-specific transformations includes at least one of compression and encryption of the source logical object.

7. The method of claim 1, wherein the position-dependent data comprises at least one of a page number, a slide number, a paragraph number, and a Microsoft Excel cell number.

8. The method of claim 1, wherein the position-dependent data is removed from around the source logical object or is removed from within the source logical object.

9. The method of claim 1, wherein the instance-dependent data comprises at least one of author name, modified date/time, revision, total editing time, number of pages, number of characters, number of lines, number of paragraphs, and number of words.

10. The method of claim 1, wherein the partitioning is accomplished in the absence of ancestor information about the digital data.

11. The method of claim 1, wherein at least two of the operations are performed for the determined format.

12. The method of claim 1, further comprising:

storing additional data, wherein the additional data comprises one or more of the position-dependent, instance-dependent, format-specific headers or footers, and information indicative of the format-specific transformations; and

associating the additional data with the resulting object; and

using the stored resulting object and the associated additional data to recreate the digital data.

13. The method of claim 1, wherein determining whether the resulting object has already been stored is based at least in part on determining an identifier associated with the resulting object and determining whether the identifier has already been stored.

14. The method of claim 13, wherein determining an identifier associated with the resulting object is based on determining a checksum or hash of the resulting object.

15. The method of claim 1, further comprising transmitting the resulting object.

16. A system comprising:

a memory capable of storing data; and

a processor configured for;

determining a format of digital data;

identifying a source logical object within the digital data, wherein the identification of the source logical object is accomplished at least in part by applying knowledge about the format of the digital data;

based on the determined format, performing one or more of the following operations to create a resulting object;

removing position-dependent data from the source logical object,

removing instance-dependent data from the source logical object,

removing one or more format-specific headers or footers from the source logical object, and

removing format-specific transformations from the source logical object,

determining whether the resulting object has already been stored in the memory, and

storing the resulting object in the memory if the resulting object has not already been stored.

17. The system of claim 16, wherein the digital data is at least one of a digital file, block based storage, binary large object, and a data stream.

18. The system of claim 17, wherein the digital data is a compound file, and the source logical object is stored in a file within the compound file.

19. The system of claim 18, wherein the compound file includes one of a .zip, .pst, .cab, .a, Exchange Database, Microsoft SQL Server database, Lotus Notes mailbox, SharePoint Repository, and EMC Documentum file.

20. The system of claim 16, further comprising assembling the source logical object in a contiguous form based on an instance of the source logical object that is stored across multiple storage blocks.

21. The system of claim 16, wherein at least one of the format-specific transformations includes at least one of compression and encryption of the source logical object.

22. The system of claim 16, wherein the position-dependent data comprises at least one of a page number, a slide number, a paragraph number, and a Microsoft Excel cell number.

23. The system of claim 16, wherein the position-dependent data is removed from around the source logical object or is removed from within the source logical object.

24. The system of claim 16, wherein the instance-dependent data comprises at least one of author name, modified date/time, revision, total editing time, number of pages, number of characters, number of lines, number of paragraphs, and number of words.

25. The system of claim 16, wherein the partitioning is accomplished in the absence of ancestor information about the digital data.

26. The system of claim 16, wherein at least two of the operations are performed for the determined format.

27. The system of claim 16, further comprising:

storing additional data, wherein the additional data comprises one or more of the position-dependent, instance-dependent, format-specific headers or footers, and information indicative of the format-specific transformations;

associating the additional data with the resulting object; and

using the stored resulting object and the associated additional data to recreate the digital data.

28. The system of claim 16, wherein determining whether the resulting object has already been stored is based at least in part on determining an identifier associated with the resulting object and determining whether the identifier has already been stored.

29. The system of claim 28, wherein determining an identifier associated with the resulting object is based on determining a checksum or hash of the resulting object.

30. The system of claim 16, further comprising transmitting the resulting object.

31. A computer-implemented method for partitioning digital data comprising:

determining a format of the digital data;

identifying a source logical object within the digital data, wherein the identification of the source logical object is accomplished at least in part by applying knowledge about the format of the digital data;

determining whether the resulting object has already been stored;

storing the resulting object if the resulting object has not already been stored;

storing additional data, wherein the additional data comprises one or more of information indicative of the original position of the logical object within the digital data, position-dependent information, instance-dependent information, format-specific headers or footers, and information indicative of format-specific transformations;

associating the additional data with the resulting object; and

using the stored resulting object and the associated additional data to recreate the digital data.

32. A system comprising:

a memory capable of storing data; and

a processor configured for;

determining a format of digital data,

identifying a source logical object within the digital data, wherein the identification of the source logical object is accomplished at least in part by applying knowledge about the format of the digital data,

determining whether the resulting object has already been stored,

storing the resulting object if the resulting object has not already been stored,

storing additional data, wherein the additional data comprises one or more of information indicative of the original position of the logical object within the digital data, position-dependent information, instance-dependent information associating the additional data with the resulting object, and

using the stored resulting object and the associated additional data to recreate the digital data.