A Statistical Analysis and Interpretation of the HyperLogLog Algorithm

Graduate Thesis Or Dissertation

Public Deposited

Citeable URL: https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/2f75rg754

Descriptions

Attribute Name	Values
Creator	Chick, Alexander
Abstract	The HyperLogLog (HLL) algorithm is used to estimate the cardinality of large sets. This thesis gives a novel analysis of the HyperLogLog algorithm by using techniques from statistics and probability. Initially, closed form bounds for the mean and variance of the max of n independent and identically distributed geometric random variables are developed. Surprisingly, the beta, digamma and trigamma functions show up in integral ways in the bounds discovered. These bounds and other techniques from probability are used to investigate the asymptotic behavior of the estimator associated with the HyperLogLog algorithm. The maximum likelihood estimator of the HyperLogLog algorithm is also derived and compared to the original HyperLogLog algorithm. Finally, some preliminary work is included that abstracts the idea of random interval subdivision to random area splitting for triangular regions. This is a generalization of the Kakutani-splitting process.
License	All rights reserved
Resource Type	Dissertation
Date Issued	2021-06-04
Degree Level	Doctoral
Degree Name	Doctor of Philosophy (Ph.D.)
Degree Field	Mathematics
Degree Grantor	Oregon State University
Commencement Year	2021
Advisor	Ossiander, Mina
Committee Member	Gitelman, Alix Hailemariam, Temesgen Koslicki, David Dray, Tevian
Academic Affiliation	Mathematics
Rights Statement	In Copyright
Publisher	Oregon State University
Peer Reviewed	No
Language	English [eng]

Parents:

This work has no parents.

In Collection:

Thumbnail	Title	Date Uploaded	Visibility	Actions
	ChickAlexander2021.pdf	2021-06-10	Public	Download