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 resemblance compression comprising:
a processor; and
a memory to store instructions, which when executed by the processor, cause the processor to perform operations of resemblance compression, the operations including
determining whether a logical segment that matches a current segment is stored;
retrieving a closest logical segment to the current segment from a segment store;
encoding the current segment based at least in part on the closest logical segment;
compressing the current segment; and
packing the current segment into a container to store in a container store.
2. The system of claim 1 , wherein the operations further comprise:
dividing a data stream into a plurality of segments; and
selecting the current segment from the plurality of segments, wherein the determining, retrieving, encoding, compressing and packing are performed iteratively for each of the plurality of segments.
3. The system of claim 1 , wherein determine whether a logical segment that matches a current segment is stored comprises:
computing a set of one or more functions to the current segment to generate a summary feature of the current segment; and
comparing the summary feature against summary features of a plurality of logical segments stored.
4. The system of claim 3 , wherein the closest logical segment is identified based on the comparison of the summary feature of the current segment and the closest logical segment.
5. The system of claim 3 , wherein the one or more functions comprise one or more non-linear functions.
6. The system of claim 3 , wherein the one or more functions comprise one or more of the following: SHA-1, MD5, RIPEMD-160, a Rabin hash, and a hash function.
7. The system of claim 1 , wherein encoding the current segment based at least in part on the closest logical segment comprises encoding the current segment based on a reference to the closest logical segment and a delta representing a difference between the current segment and the closest logical segment.
8. A computer-implemented method for resemblance compression, the method comprising:
determining, by a segment store of a restorer executed by a processor, whether a logical segment that matches a current segment is stored;
retrieving by the segment store a closest logical segment to the current segment from a segment store;
encoding by the segment store the current segment based at least in part on the closest logical segment;
compressing by the segment store the current segment; and
packing by the segment store the current segment into a container to store in a container store.
9. The method of claim 8 , further comprising:
dividing a data stream into a plurality of segments; and
selecting the current segment from the plurality of segments, wherein the determining, retrieving, encoding, compressing and packing are performed iteratively for each of the plurality of segments.
10. The method of claim 8 , wherein determine whether a logical segment that matches a current segment is stored comprises:
computing a set of one or more functions to the current segment to generate a summary feature of the current segment; and
comparing the summary feature against summary features of a plurality of logical segments stored.
11. The method of claim 10 , wherein the closest logical segment is identified based on the comparison of the summary feature of the current segment and the closest logical segment.
12. The method of claim 10 , wherein the one or more functions comprise one or more non-linear functions.
13. The method of claim 10 , wherein the one or more functions comprise one or more of the following: SHA-1, MD5, RIPEMD-160, a Rabin hash, and a hash function.
14. The method of claim 8 , wherein encoding the current segment based at least in part on the closest logical segment comprises encoding the current segment based on a reference to the closest logical segment and a delta representing a difference between the current segment and the closest logical segment.
15. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations of resemblance compression, the operations comprising:
determining whether a logical segment that matches a current segment is stored;
retrieving a closest logical segment to the current segment from a segment store;
encoding the current segment based at least in part on the closest logical segment;
compressing the current segment; and
packing the current segment into a container to store in a container store.
16. The machine-readable medium of claim 15 , wherein the operations further comprise:
dividing a data stream into a plurality of segments; and
selecting the current segment from the plurality of segments, wherein the determining, retrieving, encoding, compressing and packing are performed iteratively for each of the plurality of segments.
17. The machine-readable medium of claim 15 , wherein determine whether a logical segment that matches a current segment is stored comprises:
computing a set of one or more functions to the current segment to generate a summary feature of the current segment; and
comparing the summary feature against summary features of a plurality of logical segments stored.
18. The machine-readable medium of claim 17 , wherein the closest logical segment is identified based on the comparison of the summary feature of the current segment and the closest logical segment.
19. The machine-readable medium of claim 17 , wherein the one or more functions comprise one or more non-linear functions.
20. The machine-readable medium of claim 17 , wherein the one or more functions comprise one or more of the following: SHA-1, MD5, RIPEMD-160, a Rabin hash, and a hash function.
21. The machine-readable medium of claim 15 , wherein encoding the current segment based at least in part on the closest logical segment comprises encoding the current segment based on a reference to the closest logical segment and a delta representing a difference between the current segment and the closest logical segment.