Generating sketches sensitive to high-overlap estimation

• US 8,572,092 B2
• Filed: 12/16/2011
• Issued: 10/29/2013
• Est. Priority Date: 12/16/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.), Samsung Electronics Co. Ltd.
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Bern, Marshall W.
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US13/328,901
• Publication Number:
  US 20130159352A1
• Time in Patent Office: 683 Days
• Field of Search: 707/747
• US Class Current: 707/747
• CPC Class Codes: G06F 16/184 implemented as replicated file system

Abstract

A versioning system determines an amount by which a first collection and a second collection of data objects overlap. The system divides the first collection of data objects into m possibly overlapping groups of average size s and computes one combined hash result for each group. The system then constructs a first sketch vector with n elements based on the combined hash results. A respective element of the first sketch vector is selected, using a selection function, from the combined hash results that are computed with the hash function corresponding to the element'"'"'s index. Next, the system receives a second sketch vector for the second collection of data objects, and determines a sketch-vector overlap between the first and second sketch vectors. The system then computes a data-object overlap between the first and second collections of data objects based on the sketch-vector overlap.

Claims

1. A computer-implemented method comprising:

dividing, by a computer, a first collection of data objects into m groups of average size s, wherein a data object of the first collection is assigned to one or more of the m groups;

computing a combined hash result for all members of a respective group, for each hash function in n hash functions;

constructing a first sketch vector with n elements, wherein a respective element is selected, using a selection function, from the combined hash results computed with the hash function corresponding to the element'"'"'s index;

receiving a second sketch vector for a second collection of data objects;

determining a sketch-vector overlap between the first and second sketch vectors; and

computing a data-object overlap between the first and second collections of data objects based on the sketch-vector overlap, wherein computing the data-object overlap comprises entering the sketch-vector overlap into a conversion function;

data-object overlap=(sketch-vector overlap)^1/s;

wherein s indicates an average number of data objects per group.

2. The method of claim 1, wherein dividing the first collection of data objects comprises using a hash function to map each of the first collection of data objects into one of the m groups.

3. The method of claim 1, wherein computing a combined hash result for a group involves:

computing a hash result for each of the data objects corresponding to the group; and

computing a combined hash result for the group based on the hash results.

4. The method of claim 1, wherein the first sketch vector and the second sketch vector have a matching length.

5. The method of claim 4, wherein determining the sketch-vector overlap comprises determining a fraction of corresponding vector elements between the first and second sketch vectors that have matching values.

6. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method comprising:

dividing a first collection of data objects into m groups of average size s, wherein a data object of the first collection is assigned to one or more of the m groups;

computing a combined hash result for all members of a respective group, for each hash function in n pair-wise independent hash functions;

constructing a first sketch vector with n elements, wherein a respective element is selected, using a selection function, from the combined hash results computed with the hash function corresponding to the element'"'"'s index;

receiving a second sketch vector for a second collection of data objects;

determining a sketch-vector overlap between the first and second sketch vectors; and

computing a data-object overlap between the first and second collections of data objects based on the sketch-vector overlap, wherein computing the data-object overlap comprises entering the sketch-vector overlap into a conversion function;

data-object overlap=(sketch-vector overlap)^1/s;

wherein s indicates an average number of data objects per group.

7. The storage medium of claim 6, wherein dividing the first collection of data objects comprises using a hash function to map each of the first collection of data objects into one of the m groups.

8. The storage medium of claim 6, wherein computing a combined hash result for a group involves:

computing a hash result for each of the data objects corresponding to the group; and

computing a combined hash result for the group based on the hash results.

9. The storage medium of claim 6, wherein the first sketch vector and the second sketch vector have a matching length.

10. The storage medium of claim 9, wherein determining the sketch-vector overlap comprises determining a fraction of corresponding vector elements between the first and second sketch vectors that have matching values.

11. An apparatus comprising:

a processor;

a memory;

a data-grouping mechanism to divide a first collection of data objects into m groups of average size s, wherein a data object of the first collection is assigned to one or more of the m groups;

a hashing mechanism to compute a combined hash result for all members of a respective group, for each hash function in n pair-wise independent hash functions;

a sketch-generating mechanism to construct a first sketch vector with n elements, wherein a respective element is selected, using a selection function, from the combined hash results computed with the hash function corresponding to the element'"'"'s index;

a communication mechanism to receive a second sketch vector for a second collection of data objects;

a comparison mechanism to determine a sketch-vector overlap between the first and second sketch vectors; and

a computing mechanism to compute a data-object overlap between the first and second collections of data objects based on the sketch-vector overlap, wherein while computing the data-object overlap, the computing mechanism is further configured to enter the sketch-vector overlap into a conversion function;

data-object overlap=(sketch-vector overlap)^1/s;

wherein s indicates an average number of data objects per group.

12. The apparatus of claim 11, wherein while dividing the first collection of data objects, the data-grouping mechanism is further configured to use a hash function to map each of the first collection of data objects into one of the m groups.

13. The apparatus of claim 11, wherein while computing a combined hash result for a group, the hashing mechanism is further configured to:

compute a hash result for each of the data objects corresponding to the group; and

compute a combined hash result for the group based on the hash results.

14. The apparatus of claim 11, wherein the first sketch vector and the second sketch vector have a matching length.

15. The apparatus of claim 14, wherein while determining the sketch-vector overlap, the comparison mechanism is further configured to determine a fraction of corresponding vector elements between the first and second sketch vectors that have matching values.