Unlocking Fractional Moments in Delphic Set Streams

Abstract

We consider estimation of non-integer frequency moments $F_k$ and related Bernstein-type statistics in the Delphic set stream model under a bounded-frequency assumption: every universe element appears at most $\tau$ times. The main challenge of this model is to keep space low while also keeping update time low, which is not trivial because the sets can be exponential in size compared to their representations. Our core insight is that by sampling the stream at different rates and observing the resulting distinct-counts, we can 'probe' the frequency distribution and numerically integrate these probes to reconstruct a broad class of statistics. Building on that, we crucially observe that the distinct-count of a randomly sampled substream, viewed as a function of the sampling rate, is a single analytic object whose evaluations determine a broad class of statistics via a complementary Laplace-type integral. Algorithmically we exploit this by: 1. estimating those evaluations using only standard $F_0$ (distinct-count) algorithms on sampled substreams and 2. recovering target statistics by controlled numerical integration on a judiciously chosen grid. For $F_k$ with $k\in (0,1)$ we obtain the first one-pass streaming algorithms for Delphic set streams whose space and per-set update time are $\mathrm{poly}(\log|\Omega|,\log m,\varepsilon^{-1},\log(1/\delta))$ in the practically relevant regime $\tau=\mathrm{polylog}(|\Omega|,m)$; in general the bounds are polynomial in $\tau$ and $\varepsilon^{-1}$ and logarithmic in $\delta^{-1}$. We also give a complexity-theoretic barrier explaining why lower bounds for removing the bounded-frequency assumption appear difficult: ruling out polylogarithmic algorithms for unrestricted Delphic $F_k$ would imply a linear-space threshold-counting separation.