Back to results
US 8,078,593 B1Granted
Dictionary architecture and methodology for revision-tolerant data de-duplication
AssigneeInfineta Systems, Inc.
InventorKarempudi V. Ramarao
Life of this patent
Estimating the term…
Abstract
Redundant data is removed from a volume of data by partitioning the volume of data into fixed-length input segments and, for each of the input segments, traversing nodes of a search tree in accordance with the value of a fixed-size portion of the input segment to determine if the search tree contains a pointer to a matching fixed-sized portion of a segment within a dictionary. If the search tree contains the pointer, the input segment is compared with the segment within the dictionary pointed to by the pointer, and a token representative of the segment within the dictionary is substituted for at least part of the input segment determined to match the segment within the dictionary.
Claims18
A method of de-duplicating a volume of data, the method comprising:
- partitioning the volume of data into input segments;
- for each of the input segments, traversing nodes of a search tree in accordance with the value of a fixed-size portion of the input segment to determine if the search tree contains a pointer to a matching fixed-sized portion of a segment within a dictionary;
- if the search tree contains the pointer:
- comparing the input segment with the segment within the dictionary pointed to by the pointer;
- and
- substituting a token representative of the segment within the dictionary for at least part of the input segment determined to match the segment within the dictionary;
- and
- constructing the search tree based on fixed-size portions of multiple segments within the dictionary, wherein the search tree comprises at least a first search tree and a second search tree, and wherein adding branch nodes and leaf nodes within the search tree comprises:
- adding branch and leaf nodes within the first search tree corresponding to the fixed-size portions of data;
- associating respective code values with the leaf nodes within the first search tree;
- concatenating at least two of the code values to generate a synthesized value;
- and
- adding one or more branch nodes and a leaf node within the second search tree corresponding the synthesized value.
10 more elements
A data de-duplication apparatus comprising:
- segmentation logic to partition a volume of data into input segments;
- a storage component to store segments of data within a dictionary;
- and de-duplication logic to instantiate a search tree corresponding to the segments of data stored within the dictionary, and wherein, for each of the input segments, the de-duplication logic is adapted to traverse nodes of the search tree in accordance with the value of a fixed-size portion of the input segment to determine if the search tree contains a pointer to a matching fixed-sized portion of one of the segments of data within the dictionary, and, if the search tree contains the pointer, to compare the input segment with the segment within the dictionary pointed to by the pointer and to substitute a token representative of the segment within the dictionary for at least part of the input segment determined to match the segment within the dictionary, wherein the de-duplication logic to instantiate the search tree includes logic to instantiate the search tree based on fixed-size portions of the segments of data within the dictionary, the search tree including at least a first search tree and a second search tree, and wherein the logic to instantiate the search tree based on fixed-size portions of the segments of data within the dictionary includes logic to (i) add branch nodes and leaf nodes within the search tree corresponding to the fixed-size portions of the segments of data, (ii) associate respective code values with the leaf nodes within the first search tree, (iii) concatenate at least two of the code values to generate a synthesized value, and (iv) add one or more branch nodes and a leaf node within the second search tree corresponding to the synthesized value, and wherein the de-duplication logic is implemented at least in part by at least one of a programmed processor, application-specific integrated circuit (ASIC), or programmable gate array.
A data de-duplication apparatus comprising:
- means for partitioning the volume of data into a plurality of input segments;
- means for storing segments of data within a dictionary;
- means for traversing nodes of a search tree in accordance with the value of a fixed-size portion of each input segment of the plurality of input segments to determine if the search tree contains a pointer to a matching fixed-sized portion of one of the segments of data within the dictionary;
- means for comparing the input segment with the one of the segments of data within the dictionary pointed to by the pointer if the search tree contains the pointer;
- means for substituting a token representative of the one of the segments of data within the dictionary for at least part of the input segment determined to match the one of the segments of data within the dictionary if the search tree contains the pointer;
- and
- means for instantiating the search tree based on fixed-size portions of the segments of data within the dictionary, the search tree including at least a first search tree and a second search tree, and wherein the means for instantiating the search tree based on fixed-size portions of the segments of data within the dictionary includes (i) means for adding branch nodes and leaf nodes within the search tree corresponding to the fixed-size portions of the segments of data, (ii) means for associating respective code values with the leaf nodes within the first search tree, (iii) means for concatenating at least two of the code values to generate a synthesized value, and (iv) means for adding one or more branch nodes and a leaf node within the second search tree corresponding to the synthesized value.
4 more elements
A computer-readable storage medium having one or more sequences of instructions embodied therein which, when executed by a processing unit, cause the processing unit to:
- partition a volume of data into a plurality of input segments;
- store segments of data within a dictionary
- traverse nodes of a search tree in accordance with the value of a fixed-size portion of each input segment of the plurality input segments to determine if the search tree contains a pointer to a matching fixed-sized portion of one of the segments of data within the dictionary;
- compare the input segment with the one of the segments of data within the dictionary pointed to by the pointer if the search tree contains the pointer;
- substitute a token representative of the one of the segments of data within the dictionary for at least part of the input segment determined to match the one of the segments of data within the dictionary if the search tree contains the pointer;
- and
- instantiate the search tree based on fixed-size portions of the segments of data within the dictionary, the search tree including at least a first search tree and a second search tree, and wherein the one or more sequences of instructions that cause the processing unit to instantiate the search tree based on fixed-size portions of the segments of data within the dictionary include one or more sequences of instructions that cause the processing unit to (i) add branch nodes and leaf nodes within the search tree corresponding to the fixed-size portions of the segments of data, (ii) associate respective code values with the leaf nodes within the first search tree, (iii) concatenate at least two of the code values to generate a synthesized value, and (iv) add one or more branch nodes and a leaf node within the second search tree corresponding to the synthesized value.
4 more elements
Dependencies are inferred from the claim text.