Sketch-Based Cardinality Estimation Algorithms

Abstract

The cardinality estimation problem, also known as the count-distinct problem, is the problem of finding the number of distinct elements in a data stream that may contain repeated elements. This problem has many real world applications, such as counting the number of unique visitors to a website, estimating the number of elements in a large database, and network security monitoring. The naive solution uses space linear in the number of distinct elements, which becomes impractical in applications where the number of distinct elements is large. Many algorithms have been devised to address the problem of estimating the number of distinct elements in a data stream using sublinear memory. This thesis considers the subset of these algorithms that are sketch-based, that is, they operate by hashing each element in the stream into a sketch and using the sketch to estimate the number of distinct elements at query time. In this thesis, we review the major sketch-based cardinality estimation algorithms proposed in the last three decades, and survey past empirical comparison studies of cardinality estimation algorithms.