Here is the technique I've been using. This is fairly preliminary but seems to give extremely good results, at least for my use case, where it has reduced the amount of data I need to parse by several orders of magnitude. The general technique seems quite sound and scalable to arbitrary size.
This turned out to be much longer than expected - probably too long for a StackExchange post, but not long enough to be an entire description of all the nuances of this problem. Whatever: the purpose of this is just to ask does this already exist? Are people doing this? What is it called?
If anyone knows any literature references where people are doing things like this, I would love to see them! It seems like a very basic idea but so far it doesn't seem well-known; if it isn't maybe I'll write this up properly and put it on arXiv or something, as it seems to be thousands of times faster than just using MinHash naively (for large data sets).
TL;DR: Suppose you want to measure the Jaccard Similarity of two sets $A$ and $B$ of equal size $N$, with some desired error rate $\epsilon$. Then simply take one sample from each, which I'll call $S_A$ and $S_B$. The magic sample size you want, assuming $\epsilon$ is somewhere between $0.5%$ and $10%$ and $N$ is somewhere between 100,000 and 1 billion, is:
$$
|S_A| = |S_B| = \frac{0.6325}{\epsilon}\sqrt{N}
$$
where that 0.6325 value is something I've just measured empirically from a lot of Monte Carlo sampling.
Simply take one sample of this size from each set, and measure the size of the sample intersection $|S_A \cup S_B|$ using any method that is precise enough that the error is negligible (e.g. "Good enough MinHash"). Then, the magic formula to estimate the size of the true set intersection from this is:
$$
\frac{|S_A \cup S_B| \epsilon^2 N}{0.4}
$$
And from there you can estimate the Jaccard similarity or whatever else.
I'll just leave these spooky looking magic values here for now and just say that this really works: you can run your own simulations and see it for yourself. However, most notably, note that the sample size scales with the square root of $N$. So if your sets have 1 billion items each, and you want 2% precision, you only need to take a sample size of 1 million items each -- this is three orders of magnitude less data than processing the entire thing. If your sets have 10 million items each, your sample size needs to only be about 316,000 things. And so on.
I will also note that, at least from preliminary testing, this algorithm "plays nice" with MinHash. That is, if you use this with MinHash, there are two sources of approximation error: the error from MinHash itself, and the sampling error. The goal is to minimize the total number of hashes done for some given amount of error, and to do this, we want to balance "how much error" is introduced from MinHash and how much from sampling (given that MinHash's required number of hashes is inversely quadratic in the error, whereas this seems to be inversely linear in the sample size). In general, there seems to be a nontrivial minimum value for this! But we'll leave that for another time: for now, the point is that this idea of running MinHash on the samples can speed things up very significantly for a similar amount of error.
OK, that's the basic intro. Again, would appreciate some pointers if anyone has seen this before. Let's look at how it works.
The basic idea: suppose we have two sets that really are identical. Then, through sheer random chance, two different random samples, one drawn from each set, will share some expected amount of items. You can think of this as a phenomenon related to the birthday paradox, if you like; the point is that it's more items than you'd expect.
Now, they're expected to share that number of items only if the sets really are identical. On the other hand, if the two sets are totally distinct, then we expect the two samples to share no items at all. If the two sets are somewhere in between, we expect the two samples to share some intermediate amount of items.
Thus, the sample intersection can be used to estimate the size of the true intersection, for a sample that is much smaller than the actual data set: as we will see, the sample size scales with the square root of the data size (for a certain level of precision).
Let's put some figures to this with a typical situation:
- Suppose you have two sets $A$ and $B$ of 1 billion items each, and you take independent random samples $S_A$ and $S_B$ from each with 1 million items each.
- If the sets are identical, it so happens that we expect $|S_A \cap S_B| ≈ 1000$.
- If the sets are totally distinct, we expect $|S_A \cap S_B| = 0$.
- If the sets are somewhere in between, then the quantity $|A \cap B|/|A| = |A \cap B|/|B| = I$, then it turns out that we expect $|S_A \cap S_B| ≈ 1000*I$.
- Thus, it turns out, that as a very basic estimate, we can estimate the true intersection size as $|A \cap B| ≈|S_A \cap S_B|/1000 * |A|$.
- To evaluate how precise this estimate is, we can use our intersection size estimate to compute the Jaccard Similarity $|A \cap B|/|A \cup B|$ between the two sets, and then measure the expected error from the estimated similarity to the true similarity (which seems to be a reasonably well-used benchmark). If we do this, and assuming the true intersection size is uniformly distributed (and could thus be anything), this yields about 2% relative error when estimating the Jaccard Similarity.
- These expressions were all determined empirically, e.g. by running Monte Carlo simulations. We will leave the details of a rigorous analytic proof for the future, but for now anyone can do their own Monte Carlo simulations and see that these figures are basically correct.
This is ridiculously good! We've gotten something to within 2% precision and we only needed to read 2 million items to do it. That is three orders of magnitude less data than the original algorithm. And, somewhat amazingly, given this level of precision, the sample size seems to only need to increase with the square root of the data size. In other words, if we like our 2% level of precision, and we want similar results comparing two data sets of 10 billion items, we only need to take two samples of about 3.16 million to get the same level of precision. Similarly, if we only care about 100 million items, a sample size of 316,227 will give the same results.
There are a few improvements we can make on the above:
- The standard deviation of the error using our naive method is about the same as the error itself. We can try various ways to improve this (although this seems to be alright). So far, the best way to improve it seems to just be to increase the size of the sample (doubling the sample size seems to halve both the expected error and the standard deviation of the error).
- We can use a better estimator than the naive one used above, where we just scale the relative proportion up - this can even lead to us estimating the true intersection size to be larger than the size of the sets. Instead, we could use a maximum-likelihood estimator, or perhaps make some simple adjustment to the naive estimator to improve things a bit.
- We also note that the expected error depends on the distribution of true intersection sizes. If there is a uniform distribution on the set of possibilities regarding what the intersection size could be, then the figures are (again, empirically measured) what I put above. If the true intersection size is 0, on the other hand, this will always give the correct result as it will always estimate 0. And if the two sets are identical, the error will tend to a maximum. So, in the example above, while the average error was 2%, the average error if the sets really are identical is about 4.8%.
- We note that this method above assumes that we've measured the true sample intersection, rather than estimating that with another probabilistic estimator (e.g. MinHash). However, of course, the ultimate goal is to use something like MinHash to estimate the size of the sample intersection as well, as long as you're willing to add a bit more relative error to the end result. The question of how much precision you should try to get from MinHash, vs from the sampling, and how to balance these two things, seems very interesting.
Actually making this rigorous and deriving these expressions in closed form requires a bunch of fairly tedious statistics algebra, although straightforward. Since I've spent enough time on this for now, I will just leave it that anyone can run their own simulations to verify these results seem to be correct (for now assuming both sets are equal in size):
- If you want ~2% precision, you should try to choose your sample size so that if the two sets are identical, the two samples are expected to share about 1000 elements (as a very basic guideline).
- The magic sample size that gives this result for 2% seems to be $\sqrt{1000 * N}$ (again, assuming $N = |A| = |B|$ for now. So if $N = 10^9$, then the sample size should be $10^6$; if $N = 10^6$ then you want $31623$, etc.
- From this baseline, if you want to halve the expected error, then the sample size should increase by a factor of two. (This is, of course, approximate, but seems to be a decent guideline within this precision range.)
Putting it all together, if $\epsilon$ is the error rate you want (somewhere around 2%, let's say), and $N$ is the number of items in both of your sets, the sample size you want seems to be determined using this formula:
$$
\frac{0.6325}{\epsilon}\sqrt{N}
$$
which, again, is determined empirically, and gives a decent ballpark estimate for $\epsilon$ in the range of 0.5% to 10% and $N$ in the range 100000 to 1 billion. And then our estimator corresponds to this:
$$
\frac{|S_A \cup S_B| \epsilon^2 N}{0.4}
$$
