Per-flow cardinality estimation based on virtual LogLog sketching

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 LogLog algorithm proposed recently by Xiao, Chen, Chen and Ling estimates the cardinalities of a large number of flows with a compact memory. The purpose of this thesis is to explore two new perspectives on the estimation process of this algorithm. Firstly, we propose and investigate a family of estimators that generalizes the original vHLL estimator and evaluate the performance of the vHLL estimator compared to other estimators in this family. Secondly, we propose an alternative solution to the estimation problem by deriving a maximum-likelihood estimator. Empirical evidence from both perspectives suggests the near-optimality of the vHLL estimator for per-flow estimation, analogous to the near-optimality of the HLL estimator for single-flow estimation.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2017

Author dc:creator

• Zhou, Zeyu

Contributors dc:contributor

• Hajek, Bruce

• Network traffic measurement
• Per-flow cardinality estimation
• Maximum-likelihood estimator
• Virtual LogLog sketch

Statement dc:rights

• Copyright 2016 Zeyu Zhou

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/95257

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/95257