Patent ID: 8442956

Claim:
A method for controlling a data de-duplication computer to selectively store or transmit a sub-block of data based on sub-block level sampling-based de-duplication, comprising: controlling the data de-duplication computer to select a number of locations in the sub-block to be sampled and positions for the locations to be sampled, where the selecting is based on one or more of whether an entropy measure associated with the sub-block exceeds an entropy threshold, whether a sub-block size associated with the sub-block exceeds a size threshold, and whether the sub-block was chunked using fixed boundaries or data dependent boundaries; controlling the data de-duplication computer to compute a sampling sequence for the sub-block of data, where the sampling sequence comprises data from the selected number of locations at the selected positions in the sub-block; controlling the data de-duplication computer to use the sampling sequence to locate a stored sub-block known to the data de-duplication computer, comprising locating an entry point to a set of sampling sequence related sub-blocks, where the entry point is identified in a sampling sequence keyed index; controlling the data de-duplication computer to determine a degree of similarity between the sub-block and the stored sub-block, where the degree of similarity is determined by one or more of: comparing a hash of at least a portion of the sub-block to a hash of at least a portion of the stored sub-block; comparing a delta hash associated with at least a portion of the sub-block to a delta hash associated with at least a portion of the stored sub-block; and comparing one or more additional sampling sequences associated with the sub-block to one or more additional sampling sequences associated with the stored sub-block; and based on the degree of similarity, controlling: whether the data de-duplication computer stores the sub-block and, when the sub-block is to be stored, identifying a storage format for the sub-block and controlling the data de-duplication computer to store the sub-block according to the identified storage format; whether the data de-duplication computer transmits the sub-block and, when the sub-block is to be transmitted, identifying a transmission procedure for the sub-block and controlling the data de-duplication computer to transmit the sub-block according to the identified transmission procedure; whether the data de-duplication computer updates a dedupe data structure and, when the dedupe structure is to be updated, identifying how the data de-duplication computer is to update the dedupe data structure and controlling the data de-duplication computer to update the dedupe data structure; and whether the data de-duplication computer updates the sampling sequence keyed index and, when the sampling sequence keyed index is to be updated, identifying how the data de-duplication computer is to update the sampling sequence keyed index and controlling the data de-duplication computer to update the sampling sequence keyed index.