US 5,990,810 A · Method for partitioning a block of data into subblocks and for storing and communcating such subblocks

Abstract

This invention provides a method and apparatus for detecting common spans within one or more data blocks by partitioning the blocks (FIG. 4) into subblocks and searching the group of subblocks (FIG. 12) (or their corresponding hashes (FIG. 13)) for duplicates. Blocks can be partitioned into subblocks using a variety of methods, including methods that place subblock boundaries at fixed positions (FIG. 3), methods that place subblock boundaries at data-dependent positions (FIG. 3), and methods that yield multiple overlapping subblocks (FIG. 6). By comparing the hashes of subblocks, common spans of one or more blocks can be identified without ever having to compare the blocks or subblocks themselves (FIG. 13). This leads to several applications including an incremental backup system that backs up changes rather than changed files (FIG. 25), a utility that determines the similarities and differences between two files (FIG. 13), a file system that stores each unique subblock at most once (FIG. 26), and a communications system that eliminates the need to transmit subblocks already possessed by the receiver (FIG. 19).

Claims30

Dependent claims

A method for organizing a block b of digital data for storage, communication, or comparison, comprising the step of:

partitioning said block b into a plurality of subblocks at at least one position k.vertline.k+1 within said block,
for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and
wherein A and B are natural numbers.

Dependencies are inferred from the claim text.

Method for partitioning a block of data into subblocks and for storing and communcating such subblocks

Life of this patent

Method for partitioning a block of data into subblocks and for storing and communcating such subblocks

Life of this patent

Abstract

Claims30