Generating sketches sensitive to high-overlap estimation

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.