Estimate Jaccard similarity based on a sample

Question

The Jaccard similarity of two sets, $A$ and $B$, is defined as: $Jaccard(A,B)=\frac{A\cap{B}}{A\cup{B}}$.

Say that I only have a sample of $P\%$ of each of the sets: $A'$ and $B'$. What would be a good estimator for the Jaccard similarity of the original sets $A$ and $B$?

I'm especially interested in the case of small $P$s, say ~ 1%

EDIT - some more details and context in response to comments:

In my specific scenario the groups A and B are external data, which is inaccessible to me directly. However, the party hosting the data is able to sample the data and transfer the resulting samples to me.

A motivational example: say there are two websites, each keeping a set of all visitors at a given day (assume each user has a unique id which is common to both websites). These sets of user ids are A and B above. I do not have access to the entire data-set, but each website samples its data and sends over the resulting sample - these are A' and B'. The goal here is to estimate the amount of user overlap between the websites based on the samples.

The samples are generated by taking each element of the sampled group with a probability of P (so sampling without replacement, and sample size is not fixed); Sampling choices are independent.

The value of P is known and identical for both A and B, but the sizes of the original sets A and B are not directly known.

Typical set sizes in my case - before sampling - are between 10K to 1M.

(end of EDIT)

Numerical Example

Say that $A = \{1..1000\}, B = \{500..2500\}$. Then $Jaccard(A,B) =\frac{500}{2500}=0.2$.

Now we sample $P=10\%$ of each set, resulting with $A'$ with an expected size of $100$, and $B'$ with an expected size of $200$.

Based on simulations, $Jaccard(A',B')\approx0.017$, i.e. much lower than $0.2$

What I've tried

Naively, I thought that a reasonable estimator may be $\frac{1}{P}{\times}Jaccard(A',B')$. For the example above, it gives: $10*0.017=0.17$, which is pretty close.

However looking closely at this estimation (using simlations), it seems biased - the estimation is consistently lower than the actual value, and more so as P nears zero:

(Note that despite the linear trend I've added, the bias does not always look linear)

I had a feeling this may be related to the hypergeometric distribution (as there's some similarity to the capture/recapture problem), but couldn't substantiate that.

So, I'm looking for a better estimator. For extra karma, explain where the bias above arises from.

EDIT

Found a better (though not perfect) estimator:

The difference between this question and the classic capture/recapture problem, is that in the classical setting both samples are done from the same population, while here the first one samples some elements in A which do not exist in B, and vice versa. However, there is a subset of the data on which this assumption does hold: the overlapping part.

Denote $L=|A{\cap}B|$, which would be our "population" in a capture/recapture setting. The first sample ($P\%$ out of $A$) sampled $P\%$ of $L$ - and so did the second sample ($P\%$ out of $B$). Using the naive estimator (Lincoln–Petersen (see here)) for this setting, $L\approx\frac{mn}{k}=\frac{(PL)(PL)}{|A'{\cap}B'|}$, i.e. $L\approx\frac{|A'{\cap}B'|}{P^2}$.

Since the size of $A$ and $B$ can be derived from the size of the samples $|A'|, |B'|$ by dividing in $P$, and using the estimate for the overlap, we can estimate $A{\cup}B=|A|+|B|-L\approx\frac{|A'|}{P}+\frac{|B'|}{P}+L$, and the estimator would be: $est\_jaccard(A',B')=\frac{L}{\frac{|A'|}{P}+\frac{|B'|}{P}+L}$.

Comparing with the previous estimator, this looks much better - although still seems to underestimate close to zero:

EDIT 2: I've also tried another estimator (Chapman) but didn't get better results; so for now I'm using this one.

Still, better / other estimators would be appreciated, as well as any insights regarding the problem and its analysis, which may lead to better estimation.

Answer 1

I see this is an old thread, but for the benefit of others who run into this question, I found a good analysis in a paper titled "Estimating Set Intersection using Small Samples" by Henning Kohler published in Proc. 33rd Australasian Computer Science Conference (ACSC 2010), Brisbane, Australia. The paper is available here https://dl.acm.org/doi/pdf/10.5555/1862199.1862207.

Just to provide a quick summary: the author considers a generalized problem where the random samples $A'$ and $B'$ may be of different sizes and proportions. The first question is the probability of drawing the 2 samples with $x$ common items, $a$ items from A and $b$ items from B (so that A' has $a + x$ items and B' has $b + x$ items), given X = $|A \bigcap B|$. This is:

$$p(a, b, x | X) = \frac {\begin{pmatrix} {|A| - X}\cr a \end{pmatrix} \begin{pmatrix} {|B| - X}\cr b \end{pmatrix} \begin{pmatrix} {X}\cr x \end{pmatrix} } { \begin{pmatrix} {|A| + |B| - X}\cr {a + b + x} \end{pmatrix} } $$

The problem of estimating X is then solved using 2 different ways. Firstly, by minimizing the standard error $\sqrt {E((\hat X - X)^2)}$, which is the square root of: $$ \sum^{min(|A|, |B|)}_{X=0} {p(X).\sum_{a,b,x} p(a,b,x|X).(\hat X - X)^2} $$ The result of minimization (after a simplifying assumption that $p(X)$ is a constant) is:

$$ \hat X = \frac { \sum^{min(|A| - a, |B| - b}_{X=x} {p(a, b, x|X)*X} } { \sum^{min(|A| - a, |B| - b}_{X=x} {p(a, b, x|X)} } $$

Unfortunately this is expensive to compute. The author also provides a second way to estimate X - an MLE estimate based on maximizing $p(a, b, x | X)$ which has a closed form:

$C_1 = x.(|A| + |B| + 1 - (a + b + x))$

$C_2 = |A|.b.(|A|-a) + |B|.a.(|B|-b)$

$C_3 = |A|.b + |B|.a - a.b$

$a_0 = |A|.|B|.C_1 - C_2$

$a_1 = C_3 - C_2 - (|A| + |B|).C_1$

$a_2 = C_1 + C_3$

$\hat X = \frac {-a_1 \pm \sqrt {a_1^2 - 4.a_0.a_2}} {2.a_2}$