Sampling-Based Estimation of Jaccard Containment and Similarity

Pranav Joshi

REVIEW 4 major objections 5 minor 14 references

Sampling-Based Estimation of Jaccard Containment and Similarity

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that a binomial model for the overlap of two random samples yields a low-bias estimator of Jaccard containment with explicit error bounds and sample-size requirements.

desk verdict A useful estimator and a genuinely new exact likelihood, but the posterior MSE bounds and sample-size formulas are wrong as stated; the paper needs correction before the guarantees can be trusted. read the letter →

arxiv 2507.10019 v3 pith:XX2HUSAA submitted 2025-07-14 stat.CO cs.DBstat.ML

Pranav Joshi This is my paper · ORCID

classification stat.COcs.DBstat.ML MSC 62D0562F1562G05

keywords JaccardcontainmentsimilarityrandomsamplingwithoutreplacementbinomialapproximationintersectionestimationposteriorerrorboundssamplecomplexityMinHash

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that, when the full sizes of two sets are known but only small uniform samples of each are available, the overlap between the samples is well described by a binomial distribution. It proposes estimating the true intersection size by taking the observed sample overlap and scaling it up by the ratio of the set sizes to the sample sizes. The paper argues that this estimator has low bias and variance in the sparse-sampling regime, provides upper bounds on its posterior mean squared error, and translates those bounds into explicit sample-size requirements for a desired accuracy and confidence. It also extends the same model to Jaccard similarity and to batched MinHash sketches, giving error bounds that scale with the inverse square root of the observed overlap. A sympathetic reader would care because these are the conditions faced in large database systems that can access only partial data and need containment or similarity estimates without full sketches.

What carries the argument

The load-bearing object is the Cartesian product $A\times B$ with its $I$ diagonal matching pairs, and the assumption that the sampled subgrid $P\times Q$ sees each such pair independently with probability $I/(N_1N_2)$. This turns the observed overlap $x$ into a binomial count, which is tractable enough to derive an estimator, a Beta posterior, Chernoff-based validity conditions, and sample-complexity formulas. The exact likelihood derived by summing over a five-tuple decomposition is used only as ground truth because its nested sums are intractable for large sets.

What would settle it

Simulate two sets of known sizes and intersection, draw samples at a rate where $M_1M_2$ is not negligible relative to $N_1N_2$ (for example $\alpha_1=\alpha_2=0.2$), and compare the empirical distribution of $x$ with the binomial $P_b(x\mid I)$; if the observed mean or variance deviates from binomial predictions by more than the paper's posterior MSE bound, or if $\hat{I}_b$ shows bias exceeding the stated bound, the independence approximation fails in that regime.

Watch

Extended reading notes

Core claim

The central claim is that the likelihood for the observed number $x$ of matching elements in two uniform samples is, in the sparse regime, $P_b(x\mid I)=\binom{M_1M_2}{x}\left(\frac{I}{N_1N_2}\right)^x\left(1-\frac{I}{N_1N_2}\right)^{M_1M_2-x}$, where $M_1,M_2$ are the sample sizes and $N_1,N_2$ the set sizes. This leads to the estimator $\hat{I}_b = x\frac{N_1N_2}{M_1M_2}$ for the intersection size and $\hat{\phi}=x\frac{N_2}{M_1M_2}$ for the containment $\phi=I/N_1$. The paper reports that this binomial likelihood matches the exact sampling distribution closely in experiments, while a union-based likelihood from earlier work overestimates the overlap dramatically. Under a uniform prior on $I$, the posterior is Beta-like and yields the MSE bound $\mathrm{MSE} < x(N_1N_2)^2/(M_1M_2)^2$; enforcing estimator validity tightens this to $N_2/(M_1M_2)$, and combining the two conditions gives the sampling-rate requirement $\alpha_1\alpha_2 \ge \max\{1/(\delta^2 N_1),\, 2\ln(1/\epsilon)/((1-\phi)^2 N_1)\}$ for containment error below $\delta$ with confidence at least $1-\epsilon$.

Load-bearing premise

The estimator and all error bounds rest on treating the $M_1M_2$ sampled pairs as independent matching events with common probability $I/(N_1N_2)$, ignoring that the samples are drawn without replacement; the paper assumes the sparse regime $M_1M_2 \ll N_1N_2$ makes this dependence negligible.

Editorial extensions

If this is right

With known $N_1,N_2$ and sparse sampling, containment can be estimated as $\hat{\phi}=x N_2/(M_1M_2)$, and the paper's bounds say this estimate has MSE below $xN_2^2/(M_1M_2)^2$, tightening to $N_2/(M_1M_2)$ when the estimator is valid.
To guarantee containment RMSE below $\delta$ with probability at least $1-\epsilon$, sampling rates must satisfy $\alpha_1\alpha_2 \ge \max\{1/(\delta^2 N_1),\, 2\ln(1/\epsilon)/((1-\phi)^2 N_1)\}$; symmetric sampling needs $M_1\ge \sqrt{N_1}/\delta$.
For Jaccard similarity, the fractional error of $\hat{J}$ scales as $O(1/\sqrt{x})$, so the required product of sample sizes grows like $1/(\delta^2 I)$ rather than $1/(\delta^2 N_1)$.
Batched MinHash over sampled subsets yields a containment estimate whose RMSE is bounded by $\sqrt{2M N_2/(k M_1M_2)}$ (or $(N_2/M_2)\sqrt{(m_1+m_2)/(kM_1)}$ for unequal batches), and stratified batching restores the independence the binomial model assumes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the binomial approximation holds, the same product-of-samples logic could extend to weighted or duplicate-rich collections, but the without-replacement correction would need to be quantified before trusting the bounds.
The paper's sample-complexity formulas imply an allocation rule for asymmetric set sizes: when $N_2\gg N_1$, symmetric sampling forces $M_2$ to scale with $N_2/N_1$, so a practitioner should instead choose $M_2$ based on the desired observed overlap rather than a fixed fraction of $N_2$.
The small negative bias noted in the batch MinHash experiments, left unexplained in the paper, may come from a second-order without-replacement effect or from the Jensen-type gap in converting sampled Jaccard estimates; a bias-correction study would be a direct test.
Because the Jaccard fractional-error bound decreases as $1/\sqrt{x}$, a system could keep drawing samples until the observed overlap crosses the threshold $c=4/\delta^2$, which the paper's lower-tail bound directly addresses.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The useful part of this paper is the core idea: model the observed sample overlap x as binomial with parameter I/(N1N2), then estimate I by Ihat = x N1N2/(M1M2). The estimator is simple, unbiased, and works fine in the sparse regime M1M2 << N1N2. The exact combinatorial likelihood in Section 3.3 is genuinely new and a nice reference; the 5-tuple decomposition with the nested sum looks correct. The empirical comparison against the union-based likelihood is convincing: the union model is indeed the wrong distribution for x.

The trouble is that all the theoretical guarantees built on the posterior analysis are broken. Section 5 claims MSE_p(I)(Ihat) < Var_B[I] < ... . The first inequality is backwards. Ihat is not the posterior mean. Under the paper's own Beta approximation, the posterior mean is about N1N2(x+1)/(M1M2+2), not N1N2 x/(M1M2). The squared difference is positive unless M1M2 = 2x, so MSE = Var + bias^2 > Var. The Beta variance simplification also goes the wrong direction: the exact scaled variance is larger than the simplification in the small-x regime. So the MSE upper bounds, the sufficiency condition on alpha, and the sample-size guidance in Section 6 do not follow. Section 6 also uses alpha = 0.001 after stating alpha >= 0.01 for its own example. The MinHash error propagation in Section 9.1 has a derivative that does not match the chain rule.

The point estimator survives; it is unbiased and the binomial model is reasonable. But the advertised tight error bounds and explicit sample size requirements are not established until the posterior analysis is corrected. The paper also never compares against Henzinger's small-sample intersection estimator, which is the closest prior work and should be cited and contrasted.

Who is this for? Someone working on set similarity estimation in databases might use the exact likelihood and the estimation idea, but only after the error guarantees are fixed. I would not cite the quantitative claims as they stand. It deserves a serious referee, but the referee should be told to verify the posterior MSE section carefully; it will need major revision.

Recommendation: send back for major revision, not desk reject. The core model is sound; the guarantees are not.

Referee Report

4 major / 5 minor

Summary. The paper studies estimation of Jaccard containment φ = |A∩B|/|A| and Jaccard similarity J = |A∩B|/|A∪B| from uniform random samples P ⊆ A and Q ⊆ B, assuming the set sizes N1, N2 and sample sizes M1, M2 are known. The author derives an exact combinatorial likelihood for the observed overlap x = |P∩Q|, proposes a binomial approximation Pb(x|I) based on treating the M1M2 pairs in P×Q as independent matches with probability I/(N1N2), and compares this approximation with a union-based likelihood from prior work. The paper then derives an estimator Îb = x N1N2/(M1M2), claims posterior MSE bounds and sample-size requirements under a uniform prior, extends the estimator to Jaccard similarity, and proposes batch-MinHash schemes for sampled data. The paper includes empirical validation on synthetic data and a GitHub repository with code.

Significance. If the central claims were sound, the paper would offer a practically relevant framework for containment and similarity estimation in settings where only samples of large sets are available and set sizes are known. The unconditional estimator Îb is unbiased, the exact likelihood derivation in Section 3.3 is a useful reference, and the empirical comparison against the union-based model is informative. The paper is clearly written and ships reproducible code. However, the posterior MSE analysis in Section 5 is directionally incorrect: the claimed inequality MSE < posterior variance is impossible for an estimator that is not the posterior mean, and the variance simplification is in the wrong direction in the sparse regime. Because Sections 6 and 7 build directly on these bounds, the advertised error guarantees and sample-size recommendations are not established.

major comments (4)

[Section 5, 'Bounding Posterior MSE'] The displayed chain 'MSE_p(I)(Îb) < Var_B[I] < (N1N2)^2 · x(M1M2−x)/((M1M2)^2(M1M2+1))' is wrong in both inequalities. For any posterior, MSE equals posterior variance plus squared bias of the estimator relative to the posterior mean. Under the stated uniform prior and binomial likelihood, the approximate posterior mean of I is C(x+1)/(n+2) with C = N1N2 and n = M1M2, whereas Îb = Cx/n, giving a squared bias of C^2(n−2x)^2/(n^2(n+2)^2), which is positive unless n = 2x. Thus MSE is strictly greater than the posterior variance, not less. Additionally, the exact Beta variance with parameters (x+1, n−x+1) is (x+1)(n−x+1)/((n+2)^2(n+3)), which in the sparse small-x regime is larger than the paper's expression x(n−x)/(n^2(n+1)); for example at x = 1, n = 100 the exact variance is approximately 1.87×10^-4 while the paper's expression is approximately 9.80×10^-5. Hence the simplification is a lower bound, not an upper bound. The subsequent bound MSE_p(I)(Îb) < x(N1N2)^2/(M1M2)^2 and all sample-size conditions derived from it are therefore unsupported.
[Section 6, 'Practicality in Real-World Regimes'] The numerical example is internally inconsistent. The paper states that for δ = 0.01 and N1 = 10^8 the accuracy condition requires α ≥ 1/(δ√N1) = 0.01, and the validity condition gives α ≥ 0.000403, so the binding constraint is α ≥ 0.01. The example then says 'we use α = 0.001' and reports M1 = 10^5, M2 = 5×10^5. This value of α is ten times smaller than the paper's own required minimum, so the example does not demonstrate feasibility under the stated conditions. The sample-size guidance in this section needs to be recomputed consistently after correcting the error bounds.
[Section 7, 'Posterior Error Bounds'] The fractional-error bound for the Jaccard estimator depends on the Section 5 bound MSE_p(I)(Îb) < x(N1N2)^2/(M1M2)^2 and therefore inherits the failure of that bound. In addition, the propagation step writes 1 + I/(N1+N2−I) ≈ 1 + N1/N2, which requires I ≈ N1, i.e., containment near 1; this condition is not stated or justified. Consequently the claimed O(1/√x) fractional-error guarantee for J is not established for the general parameter range the paper targets.
[Section 4, 'Experimental Setup' and 'Distributional Comparison'] The empirical validation of the binomial approximation against the exact distribution is performed at a single parameter configuration (N1 = 10^6, N2 = 2×10^6, I = 5×10^5, M1 = 3×10^4, M2 = 4×10^4). The paper does not report experiments that vary the sampling rate ratio M1M2/(N1N2) or approach the boundary of the sparse regime, even though the abstract and conclusion claim accuracy 'when sample sizes are small compared to the original sets.' Since the theoretical posterior-MSE support is flawed, this single-point validation is insufficient to substantiate the central claim of practical accuracy across the stated regime.

minor comments (5)

[Section 3.1] The phrase 'a special subset of size I ⊆ F' is notational misuse: I is an integer, not a set. It should read 'a special subset S ⊆ F with |S| = I' or similar.
[Section 5, 'Estimator Validity'] The displayed Chernoff-bound condition for α1α2 appears garbled due to the layout; the formula 'α1α2 ≥ ln(1/ε)/N1 · (2+φ)/(1−φ) / (1−φ)' should be rewritten unambiguously, and the numeric example (760/N1) should be checked against the corrected formula.
[Section 7] The phrase 'with an arbitarily high confidence' contains a typo ('arbitarily' should be 'arbitrarily').
[Section 8.4] The sentence 'Forturnately, it's easy to do' contains a typo ('Forturnately' should be 'Fortunately').
[Section 9.2] The phrase 'emperical distribution' contains a typo ('emperical' should be 'empirical').

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the binomial likelihood is an independent approximation validated against the exact sampling distribution, and no self-citation or fitted parameter is load-bearing.

full rationale

The paper's central derivation is self-contained. The binomial likelihood is obtained by an explicit independence ansatz over the Cartesian product of the two samples, not by defining it in terms of the quantity it is meant to predict. The estimator for the intersection size follows by moment matching from that likelihood, and it is not a fitted parameter renamed as a prediction. The paper validates the approximation against a separately derived exact combinatorial distribution, treating that exact distribution as ground truth, and against synthetic data generated by uniform sampling without replacement. The empirical check is therefore external to the binomial model rather than a reuse of its own output. The posterior analysis starts from the stated uniform prior and the Beta posterior, and the references cited for Beta variance and concentration inequalities are standard external results; no self-citation carries a load-bearing premise. The Section 5 claim that the posterior MSE of the estimator is bounded by the Beta variance would require the estimator to be the posterior mean, which is not established and appears mathematically incorrect; however, that is a correctness or proof gap, not a circularity, because the bound does not reduce to the model's inputs by construction. Consequently no circular step is exhibited.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new physical or conceptual entities. Its free parameter count is zero because the binomial model has no fitted constants; the user-chosen sample sizes and hyperparameters such as a, b, k, delta, and epsilon are not fitted to data.

assumptions (6)

domain assumption Samples P and Q are drawn uniformly at random without replacement from A and B, with set sizes N1 and N2 known.
This is the problem setup in Section 2; the exact likelihood and all estimators depend on it.
domain assumption The sparse sampling regime M1M2 << N1N2, x << I, and M_i - x << N_i - I holds.
Section 2 states this regime; the binomial approximation ignores without-replacement dependence and is only justified here.
ad hoc to paper Each of the M1M2 pairs in P times Q is independently a matching pair with probability I/(N1N2).
This is the binomial approximation in Section 3.1; it is not exact because a row or column can contain at most one match.
domain assumption Uniform prior p(I) = 1/N1 on [0, N1] for posterior inference.
Section 5 uses this prior to derive the Beta posterior and MSE bounds.
ad hoc to paper In the batch-MinHash scheme, the batch overlap counts xi,j are independent and follow Bin(xi,j | phi/N2, M^2).
Section 8.4 asserts independence is achieved by capping sampling rates at 0.1; this is an approximation, not an exact property of without-replacement sampling.
standard math MinHash estimate of Jaccard has RMSE sqrt(J(1-J)/k).
Used in Sections 8 and 9 for MinHash error; standard result but not proven in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sampling-Based Estimation of Jaccard Containment and Similarity." pith.science (2026). https://pith.science/paper/XX2HUSAA

@misc{pith2026250710019,
  author       = {Pith},
  title        = {Pith review of: Sampling-Based Estimation of Jaccard Containment and Similarity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XX2HUSAA}},
  note         = {Machine review of arXiv:2507.10019}
}

read the original abstract

This paper addresses the problem of estimating the containment and similarity between two sets using only random samples from each set, without relying on sketches of full sets. The study introduces a binomial model for predicting the overlap between samples, demonstrating that it is both accurate and practical when sample sizes are small compared to the original sets. The paper compares this model to previous approaches and shows that it provides better estimates under the considered conditions. It also analyzes the statistical properties of the estimator, including error bounds and sample size requirements needed to achieve a desired level of accuracy and confidence. The framework is extended to estimate set similarity, and the paper provides guidance for applying these methods in large scale data systems where only partial or sampled data is available.

Figures

Figures reproduced from arXiv: 2507.10019 by the authors.

**Figure 1.** Matching pairs in the N1 × N2 grid. When the grid is sparse and the subgrid is small, the presence of one match does not significantly influence the others, motivating the use of the binomial approximation. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 2.** Characterisation of (P, Q) pair as 5-tuple. The number of valid configurations for a fixed a, b, x is: n(a, b, x | I) = I x I − x a + b a + b a N1 − I M1 − x − a N2 − I M2 − x − b . 6 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Empirical distribution of x (blue) vs. binomial approximation. Red lines denote ±1 standard deviation. In contrast, the union-based likelihood performs poorly in this setting: 8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Empirical vs. union-based likelihood distribution for [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

**Figure 5.** Figure 5: Distribution of estimators: binomial and union-based. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]

**Figure 6.** Figure 6: Zoomed-in view of ˆIb estimator distribution. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]

**Figure 7.** Figure 7: Distribution of Jˆ and its Z-score 24 [PITH_FULL_IMAGE:figures/full_fig_p024_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

[1]

K. Bai, C. Li, and Y. Li. Improved Consistent Weighted Sampling Revisited (I 2CWS). arXiv preprint arXiv:1706.01172, 2017

work page Pith review arXiv 2017
[2]

C. Ertl. SuperMinHash: A New Minwise Hashing Algorithm for Jaccard Similarity Estimation. arXiv preprint arXiv:1706.05698, 2017

work page Pith review arXiv 2017
[3]

Talwar and D

K. Talwar and D. Panigrahy. Consistent Sampling with Replacement. Technical Report, 2006. Available at http://kunaltalwar.org/papers/wtdjacc.pdf

work page 2006
[4]

Henzinger

M. Henzinger. Estimating Set Intersection Using Small Samples. In Random Structures and Algorithms, 2006

work page 2006
[5]

A. Z. Broder, S. C. Glassman, M. S. Manasse, and G. Zweig. On the Resemblance and Containment of Documents. In Proc. of the 1997 IEEE SEQUOIA Workshop, 1997

work page 1997
[6]

Rajaraman and J

A. Rajaraman and J. D. Ullman. Selectivity Estimation on Set Containment Search. In Mining of Massive Datasets, Springer. https://link.springer.com/article/10.1007/ s41019-019-00104-1

work page
[7]

Hoeffding

W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13–30, 1963

work page 1963
[8]

Boucheron, G

S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013

2013

Show all 14 references

[9]

A. M. Mood, F. A. Graybill, and D. C. Boes. Introduction to the Theory of Statistics. McGraw- Hill, 3rd edition, 1974

1974
[10]

Casella and R

G. Casella and R. L. Berger. Statistical Inference. Duxbury Press, 2nd edition, 2001

2001
[11]

D. P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009

2009
[12]

Avail- able at: https://asktom.oracle.com/ords/f?p=100:11:0::NO::P11_QUESTION_ID: 26043356526642

Oracle Corporation, Ask TOM: ORA HASH Function Performance , 2005. Avail- able at: https://asktom.oracle.com/ords/f?p=100:11:0::NO::P11_QUESTION_ID: 26043356526642. Accessed: July 20, 2025

2005
[13]

Avail- able at: https://docs.oracle.com/en/database/oracle/oracle-database/21/netag/ optimizing-performance.html

Oracle Corporation, Oracle Net Services Administrator’s Guide - Optimizing Per- formance (Example Using 100 Mbps Link) , Oracle Database 21c, 2021. Avail- able at: https://docs.oracle.com/en/database/oracle/oracle-database/21/netag/ optimizing-performance.html. Accessed: July 20, 2025

2021
[14]

Available at: https://makejavafaster.blogspot.com/2015/06/ jdbc-fetch-size-performance.html

Jacek Marchwicki, JDBC Fetch-Size Performance , Make Java Faster Blog, June 2015. Available at: https://makejavafaster.blogspot.com/2015/06/ jdbc-fetch-size-performance.html . Accessed: July 20, 2025. 29

2015

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

K. Bai, C. Li, and Y. Li. Improved Consistent Weighted Sampling Revisited (I 2CWS). arXiv preprint arXiv:1706.01172, 2017

work page Pith review arXiv 2017

[2] [2]

C. Ertl. SuperMinHash: A New Minwise Hashing Algorithm for Jaccard Similarity Estimation. arXiv preprint arXiv:1706.05698, 2017

work page Pith review arXiv 2017

[3] [3]

Talwar and D

K. Talwar and D. Panigrahy. Consistent Sampling with Replacement. Technical Report, 2006. Available at http://kunaltalwar.org/papers/wtdjacc.pdf

work page 2006

[4] [4]

Henzinger

M. Henzinger. Estimating Set Intersection Using Small Samples. In Random Structures and Algorithms, 2006

work page 2006

[5] [5]

A. Z. Broder, S. C. Glassman, M. S. Manasse, and G. Zweig. On the Resemblance and Containment of Documents. In Proc. of the 1997 IEEE SEQUOIA Workshop, 1997

work page 1997

[6] [6]

Rajaraman and J

A. Rajaraman and J. D. Ullman. Selectivity Estimation on Set Containment Search. In Mining of Massive Datasets, Springer. https://link.springer.com/article/10.1007/ s41019-019-00104-1

work page

[7] [7]

Hoeffding

W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13–30, 1963

work page 1963

[8] [8]

Boucheron, G

S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013

2013