10
$\begingroup$

I'm working on an algorithm which needs to calculate the size of a set generated by the intersections of at least 2 sets. More specifically:

$$ z = \left |A_0 \cap \ldots \cap A_n \right | $$

The sets that are intersected are generated by SQL queries, and in an effort to keep things fast, I get a count of each query ahead of time, then take the set with the lowest count ($A_0$) and use those IDs as bounds on the rest of the big queries, so the intersection effectively becomes:

$$ z = \left |\left ( A_0 \cap A_1 \right ) \cap \ldots \cap \left ( A_0 \cap A_n \right ) \right | $$

Even this strategy leaves me with some pretty big queries to run, since $\left | A_0 \right |$ can sometimes be large. My idea for dealing with that is taking a random sample of $A_0$ and intersecting it with the rest of the sets before extrapolating back to a proper estimate of $z$. My question is: what is the best way to go about sampling and then extrapolating to get back to a value of $z$ that is, if not entirely accurate, has a predictable error range?


Here's what I've tried so far (in pseudocode, sort of):

sample_threshold := 10000
factor := 1
if (len(A0) > sample_treshold) {
    factor = sample_threshold / len(A0)
}

// Take a random sample of size 10000 from A0

// Intersect all the other sets with the A0 sample, then with each other
working_set := A0
for i, a := range A {
    a = intersect(A0, a)
    working_set = intersect(working_set, a)
}

z := len(working_set) * (1 / factor)

This code works, but seems to consistently overestimate z, with a lower sample size yielding a higher estimate. Additionally, I'm not sure how this would scale with more than two sets to intersect.

I hope this question makes sense, let me know if I can clarify anything further. Also, if this question is off topic or belongs somewhere else, please let me know and I'm happy to move it.


Per Bill's comment, I ran some quick trials to show sample size vs. error. Each sample size bucket was run 20 times, and as you can see there's a pretty clear trend:

Plot

$\endgroup$
7
  • $\begingroup$ I think simple random sampling without replacement should work. I'm baffled that you are getting overestimates. This looks like it maps exactly to estimating a population mean using the sample mean from a random sample. You are trying to estimate the population probability that an element of $A_0$ is in the intersection of the other $A$s. I've noodled with a simple example, and it works fine. How sure are you that you are consistently overestimating? Has it happened like 15 times out of 20 or like 150 times out of 200? Is the sample really random? $\endgroup$
    – Bill
    May 9, 2014 at 21:39
  • 1
    $\begingroup$ @Bill I added a plot of sample size vs. error that illustrates what I'm seeing. It's more like 20 times out of 20. As for the random sample, it's as random as ORDER BY RAND(), which isn't perfect but should be suitable for this task. $\endgroup$ May 12, 2014 at 14:25
  • $\begingroup$ @JimmySawczuk Wouldn't it be better to simply intersect the "working set" with "a" directly, instead of "intersect(A0, a)"? Because "A0" will presumably be larger than the current "working set" in the algorithm after the first run... Am I understanding this correctly? $\endgroup$
    – user45240
    May 14, 2014 at 17:26
  • $\begingroup$ Can you confirm that you actually mean sets and not multisets (i.e., that there are no duplicates in the sets)? Because, if there are, it is easy to overestimate the size of the "intersection" by your method. (Consider the case where $A_0$ is a just 100 copies of the same element and you sampled half of them.) $\endgroup$
    – Innuo
    May 14, 2014 at 17:41
  • $\begingroup$ Also can I ask if the size of the intersection, relative to the size of the original sets, is extremely small? If so, I feel like that would explain your problem. I have run some simulations (with smaller sets) and I'm also getting a fairly consistent, albeit small, overestimation. $\endgroup$
    – user45240
    May 14, 2014 at 17:46

2 Answers 2

3
+50
$\begingroup$

If your set $A_0$ has repeated elements (i.e., it is actually a multiset), the size of the intersection will be overestimated by your procedure because your scaling factor uses the number of elements sampled and not the number of unique "types" sampled. You can correct the estimate by computing the factor as the ratio of the number unique elements in your random sample to the number of unique elements in the full set $A_0$.

$\endgroup$
0
$\begingroup$

As Innuo points out, my problem was because of duplicates in my sampled set $A_0$, which caused factor in my pseudocode to be to low, which in turn caused the final extrapolation of z to be too high because it was generated via the inverse of factor. Removing duplicates solved this problem, and now the algorithm generates a delta vs. sample size plot more along the lines of what I'd expect (the lines indicate the margin of error at a 95% confidence level for that sample size against the total population):

Plot

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.