Efficient computation of sketches

• US 9,348,797 B2
• Filed: 08/05/2013
• Issued: 05/24/2016
• Est. Priority Date: 04/11/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Li, Kai, Zhu, Ming Benjamin
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US13/959,450
• Publication Number:
  US 20140040341A1
• Time in Patent Office: 1,023 Days
• Field of Search: 708/422
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

Determining a summary feature set is disclosed. A plurality of subsegments of a first segment are selected. For each subsegment, a plurality of values by applying a set of functions to each subsegment are computed. From all the values computed for all the subsegments, a first subset of values is selected.

Claims

1. A system for resemblance compression comprising:

a processor configured to;

divide a data stream into a plurality of segments;

for a segment of the plurality of segments;

compute a summary feature set for the segment;

determine whether the segment resembles a stored segment using the summary feature set; and

in the event that the segment resembles the stored segment, store the segment as a composite of the stored segment and one or more deltas, wherein the stored segment corresponds to a base segment and the one or more deltas at least correspond to a difference between two different segments.

2. A system as in claim 1, wherein determining whether the segment resembles a stored segment comprises selecting a plurality of subsegments of the segment.

3. A system as in claim 2, wherein determining whether the segment resembles a stored segment comprises computing a plurality of values by applying a set of functions to each subsegment.

4. A system as in claim 3, wherein the set of functions comprise a set of linear functions.

5. A system as in claim 3, wherein the set of functions comprise m_kx_k+a_k wherein m_k and a_k are predetermined values for k=1 to n, and wherein x_k comprises a function of the subsegment values for k=1 to n.

6. A system as in claim 3, wherein the set of functions comprise m_kx+a_k wherein m_k and a_k are predetermined values for k=1 to n and wherein x comprises a function of the subsegment values.

7. A system as in claim 6, wherein the function of the subsegment values comprises one or more of the following:

SHA-1, MD5, RIPEMD-160, a Rabin hash, and a hash function.

8. A system as in claim 3, wherein from all the values computed for all the subsegments, selecting a first subset of values.

9. A system as in claim 8, wherein selecting the first subset of values comprises selecting one or more of the following:

a plurality of extrema values of the function results, a plurality of minima values of the function results, a plurality of maxima values of the function results, and a plurality of minima and maxima values of the function results.

10. A system as in claim 8, wherein the first subset of values are used in determining resemblance between the first segment and a second segment.

11. A system as in claim 1, further comprising hashing a plurality of underlying segments corresponding to the first subset of values to a second subset of values.

12. A system as in claim 11, wherein the second subset of values is used in determining resemblance between the first segment and a second segment.

13. A system as in claim 1, further comprising the step of composing a third subset of values based on the first subset of values.

14. A system as in claim 13, wherein the third subset of values is used in determining resemblance between the first segment and a second segment.

15. A system as in claim 13, wherein the order of composing the third subset of values is pre-determined and independent of the values in the first subset.

16. A system as in claim 13, further comprising composing a fourth subset of values based on the second subset of values.

17. A system as in claim 16, wherein the fourth subset of values is used in determining resemblance between the first segment and a second segment.

18. A system as in claim 16, wherein the order of composing the fourth subset of values is pre-determined and independent of the values in the second subset.

19. A computer program product for resemblance compression, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:

dividing a data stream into a plurality of segments;

for a segment of the plurality of segments;

computing a summary feature set for the segment;

determining whether the segment resembles a stored segment using the summary feature set; and

in the event that the segment resembles the stored segment, storing the segment as a composite of the stored segment and one or more deltas, wherein the stored segment corresponds to a base segment and the one or more deltas at least correspond to a difference between two different segments.

20. A method for resemblance compression comprising:

dividing, by a processor, a data stream into a plurality of segments;

for a segment of the plurality of segments;

computing, by the processor, a summary feature set for the segment;

determining whether the segment resembles a stored segment using the summary feature set; and

in the event that the segment resembles the stored segment, storing in a memory coupled to the processor the segment as a composite of the stored segment and one or more deltas, wherein the stored segment corresponds to a base segment and the one or more deltas at least correspond to a difference between two different segments.