Per-Flow Cardinality Estimation Based On Virtual LogLog Sketching

Zeyu Zhou, Bruce Hajek

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2019 53rd Annual Conference on Information Sciences and Systems, CISS 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728111513
DOIs
StatePublished - Apr 16 2019
Event53rd Annual Conference on Information Sciences and Systems, CISS 2019 - Baltimore, United States
Duration: Mar 20 2019Mar 22 2019

Publication series

Name2019 53rd Annual Conference on Information Sciences and Systems, CISS 2019

Conference

Conference53rd Annual Conference on Information Sciences and Systems, CISS 2019
CountryUnited States
CityBaltimore
Period3/20/193/22/19

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'Per-Flow Cardinality Estimation Based On Virtual LogLog Sketching'. Together they form a unique fingerprint.

  • Cite this

    Zhou, Z., & Hajek, B. (2019). Per-Flow Cardinality Estimation Based On Virtual LogLog Sketching. In 2019 53rd Annual Conference on Information Sciences and Systems, CISS 2019 [8692884] (2019 53rd Annual Conference on Information Sciences and Systems, CISS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CISS.2019.8692884