Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions

We revisit the problem of estimating the profile (also known as the rarity) in the data stream model. Given a sequence of $m$ elements from a universe of size $n$, its profile is a vector $φ$ whose $i$-th entry $φ_i$ represents the number of distinct elements that appear in the stream exactly $i$ times. A classic paper by Datar and Muthukrishan from 2002 gave an algorithm which estimates any entry $φ_i$ up to an additive error of $\pm εD$ using $O(1/ε^2 (\log n + \log m))$ bits of space, where $D$ is the number of distinct elements in the stream. In this paper, we considerably improve on this result by designing an algorithm which simultaneously estimates many coordinates of the profile vector $φ$ up to small overall error. We give an algorithm which, with constant probability, produces an estimated profile $\hatφ$ with the following guarantees in terms of space and estimation error: - For any constant $τ$, with $O(1 / ε^2 + \log n)$ bits of space, $\sum_{i=1}^τ|φ_i - \hatφ_i| \leq εD$. - With $O(1/ ε^2\log (1/ε) + \log n + \log \log m)$ bits of space, $\sum_{i=1}^m |φ_i - \hatφ_i| \leq εm$. In addition to bounding the error across multiple coordinates, our space bounds separate the terms that depend on $1/ε$ and those that depend on $n$ and $m$. We prove matching lower bounds on space in both regimes. Application of our profile estimation algorithm gives estimates within error $\pm εD$ of several symmetric functions of frequencies in $O(1/ε^2 + \log n)$ bits. This generalizes space-optimal algorithms for the distinct elements problems to other problems including estimating the Huber and Tukey losses as well as frequency cap statistics.