Files in this item

FilesDescriptionFormat

application/pdf

application/pdfZHOU-THESIS-2016.pdf (1MB)
(no description provided)PDF

Description

Title:Per-flow cardinality estimation based on virtual LogLog sketching
Author(s):Zhou, Zeyu
Advisor(s):Hajek, Bruce
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):Network traffic measurement
Per-flow cardinality estimation
Maximum-likelihood estimator
Virtual LogLog sketch
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 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.
Issue Date:2016-08-12
Type:Thesis
URI:http://hdl.handle.net/2142/95257
Rights Information:Copyright 2016 Zeyu Zhou
Date Available in IDEALS:2017-03-01
Date Deposited:2016-12


This item appears in the following Collection(s)

Item Statistics