Archiving de-duplicated data on tape storage media using graph partitions

摘要

Embodiments of the invention relate to data archiving on storage medium such as magnetic tapes based on graph partitioning. One aspect of the invention concerns a method that comprises representing a file system as a graph where each node of the graph represents a file and each edge represents file chunks common to the files corresponding to the nodes connected by the edge. The graph is repeatedly partitioned into disjoint sub-graphs. If the files and duplicate file chunks associated with a sub-graph fit into a data storage medium, then the files and duplicate file chunks are stored in the medium. Otherwise, the method may partition the sub-graph into smaller disjoint sub-graphs taking into consideration of degrees of connectivity of the nodes.