2023/06/08 by Mridul Nandi, Nandi, Mridul, Srijita Paul +1
Computer Science · #Machine Learning and Algorithms #Data Stream Mining Techniques #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.2306.05243
In this research paper, we address the Distinct Elements estimation problem in the context of streaming algorithms. The problem involves estimating the number of distinct elements in a given data stream A = (a1, a2,…, am), where ai ∈ \1, 2, …, n\. Over the past four decades, the Distinct Elements problem has received considerable attention, theoretically and empirically, leading to the development of space-optimal algorithms. A recent sampling-based algorithm proposed by Chakraborty et al.[11] has garnered significant interest and has even attracted the attention of renowned computer scientist Donald E. Knuth, who wrote an article on the same topic [6] and called the algorithm CVM. In this paper, we thoroughly examine the algorithms (referred to as CVM1, CVM2 in [11] and DonD, DonD' in [6]. We first unify all these algorithms and call them cutoff-based algorithms. Then we provide an approximation and biasedness analysis of these algorithms.