A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection

Reuven Cohen, Liran Katzir, Aviv YehezkelKDD 2017 · DOI · arXiv

Abstract

Estimating the intersection size of massive data streams is a critical task in big data analytics, yet traditional heuristic-based methods often suffer from high variance. This paper presents a statistically optimal algorithm that applies Maximum Likelihood Estimation (MLE) to data sketches. By deriving a global log-likelihood function from min/max sketches and solving it using the Newton-Raphson method, the proposed estimator achieves the Cramer-Rao lower bound, providing the theoretical minimum possible variance for this class of problems.

Introduction

In modern network monitoring and database management, data often arrives as continuous, high-volume streams. Storing every element is infeasible, leading to the use of "sketches"—compact, lossy summaries of the data. While estimating the cardinality of a single set (e.g., using HyperLogLog) is well-understood, accurately estimating the intersection of two sets ($|A \cap B|$) remains challenging.

Existing approaches typically rely on the inclusion-exclusion principle or Jaccard similarity. However, these methods are often "hacks" that do not fully exploit the statistical information contained within the sketches, leading to inaccurate results with high variance. This research addresses the need for a mathematically optimal estimator that minimizes error without increasing memory overhead.

Methods

The researchers treat intersection estimation as a statistical inference problem rather than a simple algebraic one. The approach utilizes min/max sketches, where each element is hashed and only the maximum hash value is retained across $m$ independent hash functions.

To derive the estimator, the authors define the following notation for the cardinalities of interest:

Notation for set cardinalities and operations used in the ML estimator derivation.

The core innovation lies in the derivation of a likelihood function based on the relationship between the sketches of two sets, $A$ and $B$. For each hash function, three distinct outcomes are possible:

  1. The maximum hash value for $A$ equals that of $B$, suggesting the "winning" element is likely in the intersection.
  2. The maximum hash value of $A$ is less than that of $B$.
  3. The maximum hash value of $A$ is greater than that of $B$.

By aggregating these probabilities across all $m$ sketches, a global log-likelihood function is constructed. The Maximum Likelihood Estimate (MLE) for the intersection cardinality $n$ is then found using the Newton-Raphson method. Empirical testing shows that this iterative numerical technique typically converges in just three iterations, making it suitable for high-speed applications.

Experimental Setup

The estimator was rigorously evaluated using synthetic datasets to compare its performance against known ground truths.

  • Scale: Simulations involved sets with cardinalities of approximately $10^6$ elements.
  • Parameters: The study varied set size ratios and overlap ratios to test robustness across diverse data distributions.
  • Baselines: The ML estimator was compared against three established methods: the Inclusion-Exclusion method, a standard Jaccard-based method, and a modified Jaccard variant.

Results and Discussion

The ML estimator demonstrates significant improvements in precision over traditional heuristic schemes.

Statistical Optimality

The authors proved that their estimator asymptotically achieves the Cramer-Rao bound. In statistics, this bound represents the lowest possible variance an unbiased estimator can have. Consequently, the proposed method is the most precise tool possible for estimating intersection cardinality from these specific sketches.

Precision and Efficiency

In simulations, the ML approach consistently outperformed all baseline schemes. The "relative variance improvement" was particularly notable; in some scenarios, the ML estimator reduced variance by nearly 100% compared to the inclusion-exclusion principle. While the Newton-Raphson method adds a small computational overhead, its rapid convergence ensures it remains efficient for real-time big data processing.

Conclusion and Future Work

This work provides a robust mathematical foundation for set intersection estimation. By moving from heuristic formulas to a Maximum Likelihood framework, the researchers have developed a tool that extracts the maximum possible information from data sketches.

Current limitations include a dependency on initial cardinality estimates (often provided by HyperLogLog) and the specific focus on min/max sketches. Future research could extend this framework to other sketching techniques, such as Count-Min sketches, or explore hardware-level implementations in network ASICs and FPGAs to further optimize performance in memory-constrained environments.

Summary updated

BibTeX
@inproceedings{cohen2017minimal,
  author = {Reuven Cohen and Liran Katzir and Aviv Yehezkel},
  title = {{A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2017},
  doi = {10.1145/3097983.3097999},
}
Figure