Efficient computation of sketches
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.
1. A system for determining a summary feature set comprising:
a processor configured to:
select a plurality of subsegments of a first segment, wherein the plurality of subsegments have variable lengths;
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; and
a memory coupled with the processor and configured to provide the processor with instructions.
2. A system as in claim 1 , wherein selecting a plurality of subsegments is based at least in part on one of the following: the values in the first segment, the weighted sum of the bytes in a first running window of fixed size for some bytes in the first segment, and the weighted sum of the bytes in a second running window of fixed size for some bytes in the first segments.
3. A system as in claim 1 , wherein the set of functions comprise a set of linear functions.
4. A system as in claim 1 , wherein the set of functions comprise m k x 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.
5. A system as in claim 4 , 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.
6. A system as in claim 1 , wherein the set of functions comprise m k x+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 1 , wherein selecting a 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.
8. A system as in claim 1 , wherein the first subset of values are used in determining resemblance between the first segment and a second segment.
9. 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.
10. A system as in claim 9 , wherein the second subset of values is used in determining resemblance between the first segment and a second segment.
11. A system as in claim 1 , further comprising the step of composing a third subset of values based on the first subset of values.
12. A system as in claim 11 , wherein the third subset of values is used in determining resemblance between the first segment and a second segment.
13. A system as in claim 11 , wherein the order of composing the third subset of values is pre-determined and independent of the values in the first subset.
14. A system as in claim 11 , further comprising composing a fourth subset of values based on the second subset of values.
15. A system as in claim 14 , wherein the fourth subset of values is used in determining resemblance between the first segment and a second segment.
16. A system as in claim 14 , wherein the order of composing the fourth subset of values is pre-determined and independent of the values in the second subset.
17. A computer program product for determining a summary feature set, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:
selecting a plurality of subsegments of a first segment, wherein the plurality of subsegments have variable lengths;
for each subsegment, computing, using a processor, 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.
18. A method for determining a summary feature set comprising:
selecting a plurality of subsegments of a first segment, wherein the plurality of subsegments have variable lengths;
for each subsegment, computing, using a processor, 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.