Consistent weighted sampling of multisets and distributions

• US 20080235201A1
• Filed: 03/22/2007
• Published: 09/25/2008
• Est. Priority Date: 03/22/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Talwar, Kunal, McSherry, Frank D., Manasse, Mark Steven
• Granted Patent: US 7,716,144 B2
• Time in Patent Office: Days
• US Class Current: 707/4
• CPC Class Codes: G06F 40/194 Calculation of difference between files

Abstract

Techniques are provided that identify near-duplicate items in large collections of items. A list of (value, frequency) pairs is received, and a sample (value, instance) is returned. The value is chosen from the values of the first list, and the instance is a value less than frequency, in such a way that the probability of selecting the same sample from two lists is equal to the similarity of the two lists.

Claims

1. A method of determining an element from a set of elements, comprising:

assigning a weight S(x) to each element x in the set of elements S; and

generating a sample in the form (x, y), wherein x is one of the elements in the set and y is a weight between 0 and the weight S(x) corresponding to that element.

2. The method of claim 1, wherein generating the sample comprises selecting the element x with a probability proportional to the weight S(x) corresponding to that element.

3. The method of claim 2, further comprising uniformly choosing y.

4. The method of claim 1, further comprising obtaining the set of elements in response to a search engine query.

5. The method of claim 1, further comprising outputting the sample.

6. The method of claim 1, further comprising generating a hash value for the sample.

7. The method of claim 1, further comprising repeating the generating to obtain a plurality of samples.

8. The method of claim 7, further comprising generating a hash value for each of the samples.

9. The method of claim 8, further comprising outputting the sample that has the greatest hash value.

10. A method of determining an element from a set of elements, comprising:

assigning a weight S(x) to each element x in the set of elements S;

generating a sample in the form (x, y), wherein x is one of the elements in the set and y is a weight between 0 and the weight S(x) corresponding to that element; and

determining a plurality of indices that potentially enclose the sample.

11. The method of claim 10, wherein determining the indices are based on intervals of powers of two.

12. The method of claim 11, further comprising determining which intervals are empty and avoiding determining the indices based on the empty intervals.

13. The method of claim 10, further comprising determining a lower index y and an upper index z that enclose the sample from the plurality of indices.

14. The method of claim 13, further comprising generating a hash value of the sample.

15. The method of claim 14, wherein the hash value is independent of y and consistent.

16. The method of claim 14, wherein generating the hash value comprises producing the hash value from a cumulative density function.

17. A method of determining an element from a set of elements, comprising:

assigning a weight S(x) to each element x in the set of elements S;

for each element,

determining a largest element y below, and a least element z above, the element x; and

generating a hash value for the element x; and

outputting the x and y corresponding to a maximum hash value.

18. The method of claim 17, wherein generating the hash value comprises producing the hash value from a cumulative density function based on z and a random number.

19. The method of claim 17, further comprising after generating the hash value, comparing the hash value to a previously stored maximum hash value, and if the hash value is greater than the previously stored hash value, then storing the hash value as the maximum hash value.

20. The method of claim 17, further comprising deferring the determination of y until immediately before outputting x and y.