Overview
Arithmetic Variable LogLog (AVLL) is presented as an advancement in cardinality estimation for data streams, specifically targeting improvements in the memory-variance tradeoff. This method reportedly surpasses ExaLogLog, a prior state-of-the-art technique, across various tested memory configurations. AVLL achieves this by implementing arithmetic encoding and a strategy to eliminate uncommon states, leading to more efficient memory utilization and a higher register density.
Research Context
Cardinality estimation, the process of counting distinct elements within a data stream, inherently involves balancing memory consumption with estimation accuracy. Previous work established ExaLogLog as a leading method in this area. ExaLogLog combined wide registers with a Fisher-information-optimal maximum likelihood (ML) estimator, achieving what was previously considered the best memory-variance product (MVP) among HyperLogLog variants.
Approach
AVLL employs several distinct methodological components to achieve its stated performance. Key among these are:
- Arithmetic Encoding and State Elimination: AVLL utilizes arithmetic encoding and eliminates uncommon states to ensure that 64-bit words are fully consumed, each accommodating 11 registers. This design yields a 5.5x register-count advantage compared to prior methods.
- Four-Component Blended Estimator (HLDLC): The HLDLC estimator, a four-component blended approach, leverages the density advantage provided by the register architecture. This allows AVLL to achieve accuracy comparable to or better than ExaLogLog's ML accuracy without requiring iterative solving processes.
- Inherited Early Exit Mechanism: AVLL integrates an early exit mechanism from DynamicLogLog. This mechanism filters the majority of elements before they interact with any register, contributing to operational efficiency.
- Memory Scaling: Similar to DynamicLogLog, AVLL stores relative NLZ (number of leading zeros) values with a shared offset. This design choice results in memory scaling as $O(B + \log \log C)$ where B is the number of registers and C is the maximum representable cardinality, decoupling the maximum representable cardinality from the register width, in contrast to $O(B \times \log \log C)$ for previous methods.
Findings
The evaluation of AVLL indicates several performance improvements and characteristics:
- Memory-Variance Product (MVP) and Accuracy: AVLL's empirical MVP is reported as 3.4. This value surpasses ExaLogLog's practical MVP of 3.78 and its theoretical optimum of 3.67. This performance advantage holds consistently across all tested sizes, ranging from 0.25 to 4 KB.
- Error Reduction: At a memory footprint of 1 KB, AVLL achieved a 1.63% width-weighted mean absolute error. This represents a 4.7% improvement compared to ExaLogLog's 1.71% error at the same memory point.
- Speed and Memory Bandwidth: Due to the reduced memory bandwidth facilitated by its early exit mechanism, AVLL operates 2.7-4.5 times faster than ExaLogLog when processing thousands of simultaneous sketches per thread.
- Data Distribution Robustness: The performance results for AVLL were observed under both high-complexity (all-unique elements) and low-complexity (non-uniformly high duplication rate) data distributions. The system exhibited zero accuracy degradation resulting from element duplication in these tests.
Potential Applications
AVLL is implemented as a single, self-contained Java class with all necessary correction formulas embedded. It is made available within the BBTools suite at https://bbmap.org.