Per-Flow Cardinality Estimation Based On Virtual LogLog Sketching
Zeyu Zhou, Bruce Hajek · 2019
Flow cardinality estimation is the problem of estimating the number of distinct elements in a data flow, often with a stringent memory constraint. It has wide applications in network traffic measurement and in database systems. The virtual HyperLogLog (vHLL) algorithm proposed by Xiao, Chen, Chen and Ling [1] estimates the cardinalities of a large number of flows with a compact memory. This paper explores two new estimation algorithms based on the same compact memory used in [1]. Firstly, we propose and investigate a family of estimators that generalizes the original vHLL estimator. Secondly, we derive an approximate maximum-likelihood estimator. Empirical evidence suggests the near-optimality of the original vHLL estimator for per-flow estimation, analogous to the near-optimality of the HyperLogLog estimator for single-flow estimation. We also propose weighted square error, a single-value metric that quantifies the performance of an estimator.