# US 8,751,462 B2 · Delta compression after identity deduplication > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,462 B2 - Document ID: US8751462B2 - Status: Granted - Kind: B2 - Application number: 12/291,998 - Filed: 2008-11-14 - Published: 2010-05-20 - Granted: 2014-06-10 - Earliest claimed: 2008-11-14 - Assignees: EMC Corporation - Applicants: Mark Huang; Edward K. Lee; Kai Li; Philip Shilane; Grant Wallace; Ming Benjamin Zhu - Inventors: Mark Huang; Edward K. Lee; Kai Li; Philip Shilane; Grant Wallace; Ming Benjamin Zhu - Web page: https://patentgrep.com/patent/US8751462B2 ## CPC - G06F 11/1453: {using de-duplication of the data} - H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction - H03M 7/3091: {Data deduplication} - G06F 11/1464: {for networked environments} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract Delta compression after identity deduplication is disclosed. A first data segment is determined to be identical to a first previous data segment. A second data segment, not determined to be identical to a second previous data segment, is then determined to be similar to a third previous data segment. ## Claims ### Claim 1 A system for processing data, comprising: a deduplicating system, wherein the deduplicating system comprises a processor and a storage unit, wherein the deduplicating system is configured for determining, using the processor, whether a first data segment is identical to a first previously stored data segment in the storage unit, wherein in the event that the first data segment is determined to be identical to the first previously stored data segment, a reference to the first data segment is stored in the storage unit; and a delta compression system is configured for determining, only in the event that the first data segment is determined not to be identical to the first previously stored data segment, whether the first data segment is similar to a second previously stored data segment, wherein the first data segment is determined to be similar to the second previously stored data segment using a sketch function and the sketch function comprises one or more functions that returns a same value for similar data segments; wherein in the event that the first data segment is determined to be similar to the second previously stored data segment, the delta compression system is further configured for computing an encoding of the first data segment, wherein the encoding comprises determining one or more differences between the first data segment and the second previously stored data segment, and storing, in the storage unit, the first data segment using a sequence comprising the one or more differences, one or more first sequence locations corresponding to each of the one or more differences, a reference to the second previously stored data segment, and one or more second sequence references, wherein the one or more second sequence references corresponding to a sequence of data from within the second previously stored segment identifying the subset of the second previously stored segment; and wherein in the event that the first data segment is not determined to be similar to the second previously stored data segment and that the first data segment is determined not to be identical to the first stored data segment, the delta compression system is further configured for storing the first data segment in the storage unit. ### Claim 2 (depends on 1) The system as in claim 1, wherein the deduplicating system receives a data stream or data block. ### Claim 3 (depends on 2) The system as in claim 2, wherein the deduplicating system breaks the data stream or data block into a plurality of data segments. ### Claim 4 (depends on 1) The system as in claim 1, wherein determining that the first data segment is identical comprises: determining a first data segment ID associated with the first data segment; determining whether the first data segment ID is identical to a previously stored ID in an ID index. ### Claim 5 (depends on 4) The system as in claim 4, where determining the first data segment ID associated with the first data segment uses one or more of the following: a fingerprint function, a hash function, a cryptographic hash function, and a digital signature. ### Claim 6 (depends on 1) The system as in claim 1, further comprising compressing the encoding of the first data segment in the event that the first data segment is determined to be similar to the second previously stored data segment. ### Claim 7 (depends on 1) The system as in claim 1, further comprising transmitting the encoding of the first data segment in the event that the first data segment is determined to be similar to the second previously stored data segment. ### Claim 8 (depends on 1) The system as in claim 1, further comprising replicating the encoding of the first data segment in the event that the first data segment is determined to be similar to the second previously stored data segment. ### Claim 9 (depends on 1) The system as in claim 1, wherein the encoding is based at least in part on the second previously stored data segment. ### Claim 10 (depends on 1) The system as in claim 1, wherein the encoding comprises an indication of a set of data blocks in the first data segment not present in the second previously stored data segment and an indication of a set of data blocks in the second previously stored data segment. ### Claim 11 (depends on 1) The system as in claim 1, wherein in the event that the first data segment is determined to be similar to the second previously stored data segment, the delta compression system further comprises determining whether the encoding is smaller than the first data segment. ### Claim 12 (depends on 1) The system as in claim 1, wherein the sketch function comprises a hash function. ### Claim 13 (depends on 1) The system as in claim 1, wherein the sketch function comprises a plurality of hash functions. ### Claim 14 (depends on 1) The system as in claim 1, wherein the sketch function comprises one or more functions that returns a similar value for similar data segments. ### Claim 15 (depends on 1) The system as in claim 1, wherein the sketch function comprises one or more functions that may return a same value for similar data segments. ### Claim 16 (depends on 1) The system as in claim 1, wherein the sketch function comprises one or more functions that may return a similar value for similar data segments. ### Claim 17 (depends on 16) The system as in claim 16, wherein sketch function values are determined to be similar based on one or more of the following methods: numeric difference, hamming distance, locality-sensitive-hashing, or nearest-neighbor-search. ### Claim 18 (depends on 1) The system as in claim 1, wherein in the event that the first data segment is determined to be similar to the second previously stored data segment, the delta compression system further comprises determining whether the first data segment is similar to one or more previously stored segments in addition to the second previously stored data segment. ### Claim 19 (depends on 18) The system as in claim 18, wherein in the event that the first data segment is determined to be similar to the one or more previously stored data segments, the encoding is based at least in part on the second previously stored data segment and the one or more additional similar previously stored data segments. ### Claim 20 (depends on 18) The system as in claim 18, wherein the one or more previously stored data segments and second previously stored data segment are identified based at least in part on one or more of the following: temporal locality, spatial locality, ease of access, expected compression, or frequency of selection for other compressed segments. ### Claim 21 (depends on 1) The system as in claim 1, wherein the second previously stored data segment was stored as an encoding of a third previously stored data segment. ### Claim 22 A method for processing data, comprising: determining, using a processor, whether a first data segment is identical to a first previously stored data segment, wherein in the event that the first data segment is determined to be identical to the first previously stored data segment, a reference to the first data segment is stored in a storage unit; and determining, only in the event that the first data segment is determined not to be identical to the first previously stored data segment, whether the first data segment is similar to a second previously stored data segment, wherein the first data segment is determined to be similar to the second previously stored data segment using a sketch function, wherein the sketch function comprises one or more functions that returns a same value for similar data segments; in the event that the first data segment is determined to be similar to the second previously stored data segment, computing an encoding of the first data segment, wherein the encoding comprises determining one or more differences between the first data segment and the second previously stored data segment, and storing, in the storage unit, the first data segment using a sequence comprising the one or more differences, one or more first sequence locations corresponding to each of the one or more differences, a reference to the second previously stored data segment, and one or more second sequence references, wherein the one or more second sequence references corresponding to a sequence of data from within the second previously stored segment identifying the subset of the second previously stored segment; and in the event that the first data segment is not determined to be similar to the second previously stored data segment and that the first data segment is determined not to be identical to the first stored data segment, storing the first data segment in the storage unit. ### Claim 23 (depends on 22) The method as in claim 22, further comprising receiving a data stream or data block. ### Claim 24 (depends on 22) The method as in claim 22, further comprising breaking the data stream or data block into a plurality of data segments. ### Claim 25 (depends on 22) The method as in claim 22, wherein determining that the first data segment is identical comprises: determining a first data segment ID associated with the first data segment; determining whether the first data segment ID is identical to a previously stored ID in an ID index. ### Claim 26 (depends on 25) The method as in claim 25, where determining the first data segment ID associated with the first data segment uses one or more of the following: a fingerprint function, a hash function, a cryptographic hash function, and a digital signature. ### Claim 27 (depends on 22) The method as in claim 22, further comprising compressing the encoding of the first data segment in the event that the first data segment is determined to be similar to the second previously stored data segment. ### Claim 28 (depends on 22) The method as in claim 22, further comprising transmitting the encoding of the first data segment in the event that the first data segment is determined to be similar to the second previously stored data segment. ### Claim 29 (depends on 22) The method as in claim 22, further comprising replicating the encoding of the first data segment in the event that the first data segment is determined to be similar to the second previously stored data segment. ### Claim 30 (depends on 22) The method as in claim 22, wherein the encoding is based at least in part on the second previously stored data segment. ### Claim 31 (depends on 22) The method as in claim 22, wherein the encoding comprises an indication of a set of data blocks in the first data segment not present in the second previously stored data segment and an indication of a set of data blocks in the second previously stored data segment. ### Claim 32 (depends on 22) The method as in claim 22, further comprising determining whether the encoding is smaller than the first data segment in the event that the first data segment is determined to be similar to the second previously stored data segment. ### Claim 33 (depends on 22) The method as in claim 22, wherein the sketch function comprises a hash function. ### Claim 34 (depends on 22) The method as in claim 22, wherein the sketch function comprises a plurality of hash functions. ### Claim 35 (depends on 22) The method as in claim 22, wherein the sketch function comprises one or more functions that returns a similar value for similar data segments. ### Claim 36 (depends on 22) The method as in claim 22, wherein the sketch function comprises one or more functions that may return the same value for similar data segments. ### Claim 37 (depends on 22) The method as in claim 22, wherein the sketch function comprises one or more functions that may return a similar value for similar data segments. ### Claim 38 (depends on 37) The method as in claim 37, wherein sketch function values are determined to be similar based on one or more of the following methods: numeric difference, hamming distance, locality-sensitive-hashing, or nearest-neighbor-search. ### Claim 39 (depends on 22) The method as in claim 22, wherein in the event that the first data segment is determined to be similar to the second previously stored data segment, determining whether the first data segment is similar to one or more previously stored segments in addition to the second previously stored data segment. ### Claim 40 (depends on 39) The method as in claim 39, wherein the encoding is based at least in part on the second previously stored data segment and the one or more additional similar previously stored data segments. ### Claim 41 (depends on 39) The method as in claim 39, wherein the one or more previously stored data segments and second previously stored data segment are identified based at least in part on one or more of the following: temporal locality, spatial locality, ease of access, expected compression, or frequency of selection for other compressed segments. ### Claim 42 (depends on 22) The method as in claim 22, wherein the second previously stored data segment was stored as an encoding of a third previously stored data segment. ### Claim 43 A computer program product for processing data, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for: determining, using a processor, whether a first data segment is identical to a first previously stored data segment, wherein in the event that the first data segment is determined to be identical to the first previously stored data segment, a reference to the first data segment is stored in a storage unit; and determining, only in the event that the first data segment is determined not to be identical to the first previously stored data segment, whether the first segment is similar to a second previously stored data segment, wherein the first data segment is determined to be similar to the second previously stored data segment using a sketch function and the sketch function comprises one or more functions that returns a same value for similar data segments; in the event that the first data segment is determined to be similar to the second previously stored data segment, computing an encoding of the first data segment, wherein the encoding comprises determining one or more differences between the first data segment and the second previously stored data segment, and storing, in the storage unit, the first data segment using a sequence comprising the one or more differences, one or more first sequence locations corresponding to each of the one or more differences, a reference to the second previously stored data segment, and one or more second sequence references, wherein the one or more second sequence references corresponding to a sequence of data from within the second previously stored segment identifying the subset of the second previously stored segment; and in the event that the first data segment is not determined to be similar to the second previously stored data segment and that the first data segment is determined not to be identical to the first stored data segment, storing the first data segment in the storage unit.