Perfect Lp Sampling with Polylogarithmic Update Time

Perfect $L_{p}$ sampling in a stream was introduced by Jayaram and Woodruff (FOCS 2018) as a streaming primitive which, given turnstile updates to a vector $x \in\{-\operatorname{poly}(n), \ldots, \operatorname{poly}(n)\}^{n}$, outputs an index $i^{*} \in\{1, 2, \ldots, n\}$ such that the probability of returning index i is exactly $\operatorname{Pr}\left[i^{*}=i\right]=\frac{\left|x_{i}\right|^{p}}{\|x\|_{p}^{p}} \pm \frac{1}{n^{C}}$, where $C\gt0$ is an arbitrarily large constant. Jayaram and Woodruff achieved the optimal $\tilde{O}\left(\log ^{2} n\right)$ bits of memory for $0(\lt)p(\lt)2$, but their update time is at least $n^{C}$ per stream update. Thus an important open question is to achieve efficient update time while maintaining optimal space. For $0(\lt)p(\lt)2$, we give the first perfect $L_{p}$-sampler with the same optimal amount of memory but with only poly $(\log n)$ update time. Crucial to our result is an efficient simulation of a sum of reciprocals of powers of truncated exponential random variables by approximating its characteristic function, using the Gil-Pelaez inversion formula, and applying variants of the trapezoid formula to quickly approximate it.

Authors

• William Swartworth
• David P. Woodruff
• Samson Zhou

Keywords

• Computer science
• Memory management
• Approximation algorithms
• Vectors
• Random variables
• Indexes
• Update Time
• Perfect Sample
• Exponential Distribution
• Statistical Tests
• High Probability
• Internet Of Things
• Total Distance
• Integrable
• Data Streams
• Poisson Process
• Integrand
• Independent Random Variables
• Order Statistics
• Cumulative Density Function
• Binary Search
• Gaussian Random Variables
• Converges In Distribution
• Random Bits
• Dominated Convergence Theorem
• Total Variation Distance
• Incomplete Gamma Function
• Stream Model
• Function Of Random Variables
• Random Oracle
• Probability Sampling
• Upper Bound
• Probability Of Failure
• Probability Density Function
• Asymptotic Distribution
• sketching
• streaming algorithms
• sublinear algorithms
• randomized algorithms
• sampling