Distinct elements and moment estimation
Kent Quanrud · 74:26
This lecture develops two streaming algorithms: a relatively recent adaptive-sampling method that estimates the number of distinct elements \(F0\) to \((1\pm\varepsilon)\) using \(O(\log n/\varepsilon^2)\) IDs, and th...