Efficient computation of sketches

• US 20070239947A1
• Filed: 04/11/2006
• Published: 10/11/2007
• Est. Priority Date: 04/11/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Li, Kai, Zhu, Ming
• Granted Patent: US 7,844,652 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• 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 method of determining a summary feature set comprising:

selecting a plurality of subsegments of a first segment;

for each subsegment, computing a plurality of values by applying a set of functions to each subsegment; and

from all the values computed for all the subsegments, selecting a first subset of values.

2. A method as in claim 1, wherein each subsegment is of a fixed length.

3. A method as in claim 1, wherein each subsegment is of variable length.

4. A method as in claim 1, wherein selecting a plurality of subsegments is based at least in part on the values in the first segment.

5. A method as in claim 1, wherein selecting a plurality of subsegments is based at least in part on the weighted sum of the bytes in a first running window of fixed size for some bytes in the first segment.

6. A method as in claim 3, wherein selecting a plurality of subsegments is based at least in part on the weighted sum of the bytes in a second running window of fixed size for some bytes in the first segments.

7. A method as in claim 1, wherein the set of functions comprise a set of linear functions.

8. A method as in claim 1, 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.

9. A method as in claim 1, 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.

10. A method as in claim 8, wherein the function of the subsegment values comprises SHA-1.

11. A method as in claim 8, wherein the function of the subsegment values comprises MD5.

12. A method as in claim 8, wherein the function of the subsegment values comprises RIPEMD-160.

13. A method as in claim 8, wherein the function of the subsegment values comprises a Rabin hash.

14. A method as in claim 8, wherein the function of the subsegment values comprises a hash function.

15. A method as in claim 1, wherein selecting a first subset of values comprises selecting a plurality of extrema values of the function results.

16. A method as in claim 1, wherein selecting a first subset of values comprises selecting a plurality of minima values of the function results.

17. A method as in claim 1, wherein selecting a first subset of values comprises selecting a plurality of maxima values of the function results.

18. A method as in claim 1, wherein selecting a first subset of values comprises selecting a plurality of minima and maxima values of the function results.

19. A method as in claim 1, wherein the first subset of values are used in determining resemblance between the first segment and a second segment.

20. A method 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.

21. A method as in claim 20, wherein the second subset of values is used in determining resemblance between the first segment and a second segment.

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

23. A method as in claim 22, wherein the third subset of values is used in determining resemblance between the first segment and a second segment.

24. A method as in claim 22, wherein the order of composing the third subset of values is pre-determined and independent of the values in the first subset.

25. A method as in claim 20, further comprising composing a fourth subset of values based on the second subset of values.

26. A method as in claim 25, wherein the fourth subset of values is used in determining resemblance between the first segment and a second segment.

27. A method as in claim 25, wherein the order of composing the fourth subset of values is pre-determined and independent of the values in the second subset.

28. A computer program product for determining a summary feature set, the computer program product being embodied in a computer readable medium and comprising computer instructions for:

selecting a plurality of fixed length subsegments of a first segment;

for each subsegment, computing a plurality of values by applying a set of functions to each subsegment; and

from all the values computed for all the subsegments, selecting a first subset of values.

29. A system for determining a summary feature set comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

select a plurality of fixed length subsegments of a first segment;

for each subsegment, compute a plurality of values by applying a set of functions to each subsegment; and

from all the values computed for all the subsegments, select a first subset of values.

30. A method of determining a summary feature set comprising:

selecting m subsegments of a first segment;

selecting n functions;

for function i, wherein i is a value from 1 to n,

computing m values f_i(subsegment_j) wherein j is a value from 1 to m;

selecting an i^th extrema value comprising a minimum or maximum value from the m values; and

selecting a first subset of values from the n extrema values.