Perfect Lp Sampling in a Data Stream
Rajesh Jayaram, David P. Woodruff · 2018
In this paper, we resolve the one-pass space complexity of Lpsampling for p ∈ (0, 2). Given a stream of updates (insertions and deletions) to the coordinates of an underlying vector f ∈ ℝn, a perfect Lp sampler must output an index i with probability |fi|p/||f||pp, and is allowed to fail with some probability δ. So far, for p > 0 no algorithm has been shown to solve the problem exactly using poly(log n)-bits of space. In 2010, Monemizadeh and Woodruff introduced an approximate Lpsampler, which outputs i with probability (1 ± ν)|fi|p/||f||pp, using space polynomial in ν-1and log(n). The space complexity was later reduced by Jowhari, Saglam, and Tardos to roughly O(ν-plog2n log δ-1) for p ∈ (0, 2), which tightly matches the Ω(log2n log δ-1) lower bound in terms of n and δ, but is loose in terms of ν. Given these nearly tight bounds, it is perhaps surprising that no lower bound at all exists in terms of ν-not even a bound of Ω(ν-1) is known. In this paper, we explain this phenomenon by demonstrating the existence of an O(log2n log δ-1)-bit perfect Lpsampler for p ∈ (0, 2). This shows that ν need not factor into the space of an Lpsampler, which completely closes the complexity of the problem for this range of p. For p = 2, our bound is O(log3n log δ-1)-bits, which matches the prior best known upper bound of O(ν-2log3n log δ-1), but has no dependence on ν. Finally, we show that a (1 ± ε) relative error estimate of the frequency fiof the sampled index i can be obtained using an additional O(ε-plog n)-bits of space for p-2log2n) bits for p = 2, which was possible before only by running the prior algorithms with ν = ε.