Analysis of a new Cardinality Estimator -- ExtendedHyperLogLog

Tal Ohayon, Aryeh KontorovicharXiv 2021 · arXiv

Abstract

We discuss the problem of counting distinct elements in a stream. A stream is usually considered as a sequence of elements that come one at a time. An exact solution to the problem requires memory space of the size of the stream. For many applications this solution is infeasible due to very large streams. The solution in that case, is to use a probabilistic data structure (also called sketch), from which we can estimate with high accuracy the cardinality of the stream. We present a new algorithm, ExtendedHyperLogLog (EHLL), which is based on the state-of-the-art algorithm, HyperLogLog (HLL). In order to achieve the same accuracy as HLL, EHLL uses 16% less memory. In recent years, a martingale approach has been developed. In the martingale setting we receive better accuracy at the price of not being able to merge sketches. EHLL also works in the martingale setting. Martingale EHLL achieves the same accuracy as Martingale HLL using 12% less memory.

Introduction

In the era of big data, counting distinct elements in massive streams—such as unique website visitors or distinct IP flows—is a critical task. Storing every unique item is often impossible as memory requirements scale linearly with the number of items. Consequently, probabilistic data structures, or "sketches," have become the standard solution, providing high-accuracy estimates with minimal, fixed memory footprints. While HyperLogLog (HLL) has long been the industry standard, the increasing scale of data demands even greater efficiency. This paper introduces ExtendedHyperLogLog (EHLL), a novel estimator that improves upon HLL by extracting more information from the same data stream.

Methodology: The ExtendedHyperLogLog (EHLL) Algorithm

EHLL is a hybrid approach combining elements of the original FM85 bitmap-based algorithm with the HLL structure. While HLL maintains an array of counters ($C_1$) storing the maximum position of the rightmost '1' in the hash of incoming data, EHLL introduces a secondary bit array ($C_2$).

This additional bit serves as a "look-behind" indicator: if the current maximum in a counter is $k$, the $C_2$ bit indicates whether the value $k-1$ has also been observed. By capturing this "near-leader" information, EHLL gains a more granular view of the stream's density. The researchers utilized advanced mathematical techniques, including Poissonization, Mellin transforms, and Laplace integrals, to derive the necessary bias correction constants for accurate estimation.

Performance Evaluation and Comparative Analysis

The efficiency of these sketches is measured using the Memory Variance Product (MVP), which accounts for the inherent trade-off between memory usage and estimation variance. A lower MVP indicates a more efficient algorithm. As shown in the comparative analysis below, EHLL achieves a significantly lower MVP than established algorithms like HLL and LogLog.

Comparison of Memory Variance Product (MVP) across different cardinality estimation sketches.

Empirical evaluations using 25,000 independent simulated streams of $10^6$ elements demonstrated that EHLL consistently outperforms HLL. Key results include:

  • Standard (Mergeable) Setting: EHLL achieves the same accuracy as HLL while using 16% less memory.
  • Martingale (Sequential) Setting: Martingale EHLL achieves the same accuracy as Martingale HLL using 12% less memory.
  • TailCut Variants: When compared to HLL-TailCut, the EHLL-TC variant still provides a 10% memory reduction for the same accuracy.

Conclusion and Future Work

ExtendedHyperLogLog represents a significant advancement in cardinality estimation, offering a more memory-efficient alternative to the current state-of-the-art. While EHLL introduces a slight increase in CPU overhead per update due to the management of the extra $C_2$ bit, the memory savings are substantial for large-scale applications. Future research should investigate the optimal balance between computational cost and memory reduction, particularly in high-speed networking environments where CPU cycles are a primary bottleneck.

Summary updated

Abstract

We discuss the problem of counting distinct elements in a stream. A stream is usually considered as a sequence of elements that come one at a time. An exact solution to the problem requires memory space of the size of the stream. For many applications this solution is infeasible due to very large streams. The solution in that case, is to use a probabilistic data structure (also called sketch), from which we can estimate with high accuracy the cardinality of the stream. We present a new algorithm, ExtendedHyperLogLog (EHLL), which is based on the state-of-the-art algorithm, HyperLogLog (HLL). In order to achieve the same accuracy as HLL, EHLL uses 16% less memory. In recent years, a martingale approach has bean developed. In the martingale setting we receive better accuracy at the price of not being able to merge sketches. EHLL also works in the martingale setting. Martingale EHLL achieves the same accuracy as Martingale HLL using 12% less memory.
BibTeX
@misc{ohayon2021analysis,
  author = {Tal Ohayon and Aryeh Kontorovich},
  title = {{Analysis of a new Cardinality Estimator -- ExtendedHyperLogLog}},
  year = {2021},
  eprint = {2106.06525},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.06525},
}

Loading related content...

Figure