Perfect Lₚ Sampling in a Data Stream

In this paper, we resolve the one-pass space complexity of perfect Lₚ sampling for p ∈ (0,2) in a stream. Given a stream of updates (insertions and deletions) to the coordinates of an underlying vector f ∈ Rⁿ, a perfect Lₚ sampler must output an index i with probability |fᵢ|ᵖ/\|f\|ₚᵖ 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 Lₚ sampler which, given an approximation parameter ν, outputs i with probability (1 ± ν)|fᵢ|ᵖ /\|f\|ₚᵖ, using space polynomial in ν⁻¹ and log(n). The space complexity was later reduced by Jowhari, Sağlam, and Tardos to roughly O(ν⁻ᵖ log² n log δ⁻¹) for p ∈ (0,2), which matches the general p≥ 0 lower bound of Ω(log² n log δ⁻¹) in terms of n and δ, but is loose in terms of ν. Given these nearly tight bounds, it is perhaps surprising that no lower bound exists in terms of ν---not even a bound of Ω(ν⁻¹) is known. In this paper, we explain this phenomenon by demonstrating the existence of an O(log² n log δ⁻¹)-bit perfect Lₚ sampler for p ∈ (0,2). This shows that ν need not factor into the space of an Lₚ sampler, which closes the complexity of the problem for this range of p. For $p=2$, our bound is O(log³ n log δ⁻¹)-bits, which matches the prior best known upper bound of O(ν⁻²log³n log δ⁻¹), but has no dependence on ν. Note that there is still a log n gap between our upper bound and the lower bound for $p=2$, the ution of which we leave as an open problem. For $p<2$, our bound holds in the random oracle model, matching the lower bounds in that model. However, we show that our algorithm can be derandomized with only a O((log log n)²) blow-up in the space (and no blow-up for $p=2$). Our derandomization technique is quite general, and can be used to derandomize a large class of linear sketches, including the more accurate count-sketch variant of Minton and Price [Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2014, pp. 669--686], resolving an open question in that paper. Finally, we show that a (1±ε) relative error estimate of the frequency fᵢ of the sampled index i can be obtained using an additional O(ε⁻ᵖ log n)-bits of space for $p < 2$, and O( ε⁻² log² n) bits for $p=2$, which was possible before only by running the prior algorithms with ν = ε.