Pairs from the buckets
A service looks for nearly identical files. For each file a MinHash signature has already been computed: k = b·r numbers. The signature is cut into b bands of r consecutive numbers: the first band is numbers 1 to r, the second r + 1 to 2r, and so on. Two files become a candidate pair if at least one band matches entirely, all r numbers in the same places.
Count how many distinct pairs of files became candidates. Then for each candidate compare the signatures in full: a pair is confirmed if the numbers match in at least half of the k places. How many candidates are confirmed? The tests include the signatures of 3093 files from the Go sources.
Input
The first line holds n, b and r (1 ≤ n ≤ 3·104, 1 ≤ b·r ≤ 48). Then n lines, the signatures: b·r integers each, from 0 to 65,535. If for each band the files are put into groups with the same band and the number of pairs within a group is summed over all groups of all bands, the result is at most 5·105.
Output
Two numbers: how many distinct pairs became candidates and how many of them are confirmed.
In the first example the first and fourth files match in all three bands, but it is one pair. The second and the first match only in the first band, two numbers of six, and that is a candidate the signature did not confirm.
Examples
Example 1
5 3 2 7 1 5 5 2 8 7 1 6 2 3 3 4 4 5 5 2 8 7 1 5 5 2 8 9 9 9 9 9 9
5 3
Example 2
4 3 1 4 8 15 4 8 16 23 8 15 42 42 42
3 2
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A pair of nearly identical files matches not in one band but in many. How many times will it land in buckets?
2The idea
For each band lay the files out in buckets, a dictionary “band values → list of files”. Each bucket of s files gives s(s − 1)/2 pairs. But the same pair can meet in several bands, and it must be counted once. So the pairs are collected in a set, for example as the number x·n + y with x < y. The work is the sum of pairs over all buckets, and the statement bounds exactly that.
3Walkthrough
In Python the key of a bucket is a tuple of r numbers, a slice of the signature; in Go a string of packed bytes or a fixed-length array. Once the candidates are collected, checking each is a pass over the k numbers of two signatures.
Why double counting is so dangerous can be seen on the tests from the Go sources. With 12 bands of 4 numbers the sum of pairs over buckets is 8799, while distinct pairs number 1848: nearly identical files match in almost five bands on average. With 24 bands of 2 the sum is 34,021 against 7457 distinct. 1478 and 1616 candidates are confirmed: with long bands there are fewer extra candidates, with short ones more, but more are confirmed with short ones, since short bands also catch pairs of similarity near the threshold. This is the same S-curve as in the article, only in integers.
Searching all pairs with a full comparison of signatures also gives the confirmed pairs, but not the candidates, and with 30,000 files that is 4.5·108 pairs of 16 comparisons each.
3+Solution
4Complexity
O(n·b) for laying out into buckets, O(P) for the pairs, where P is the sum of pairs over buckets, and O(C·k) for checking C candidates.
5Common mistakes
- Adding up pairs from all buckets. A pair that matched in several bands is counted several times; already in the first example it gives 9 instead of 5.
- Confirming by one band. A candidate is not a confirmed pair: a match of one band says nothing about the other numbers.
- Overlapping bands. The bands go one after another and do not overlap: the j-th band is the numbers from (j − 1)r + 1 to jr.
Algorithms behind it
O(K·S) for the signatures, O(n·b) for the buckets, plus checking candidates
2 problems
DS
Data structure
Hash table
Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell.
O(1) on average
2 problems