Perfect $L_p$ Sampling in a Data Stream
From MaRDI portal
Publication:5858643
DOI10.1137/18M1229912OpenAlexW3144249216MaRDI QIDQ5858643
David P. Woodruff, Rajesh Jayaram
Publication date: 14 April 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1808.05497
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal sampling from sliding windows
- Algorithms for next generation networks
- Pseudorandom generators for space-bounded computation
- Query size estimation by adaptive sampling
- Randomness is linear in space
- Selectivity and cost estimation for joins based on random sampling
- Algorithms and estimators for summarization of unaggregated data streams
- Sampling for passive internet measurement: a review
- Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
- Optimal Random Sampling from Distributed Streams Revisited
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- Random sampling with a reservoir
- The best constants in the Khintchine inequality
- Pseudorandomness via the Discrete Fourier Transform
- Internal DLA: Efficient Simulation of a Physical Growth Model
- Turnstile streaming algorithms might as well be linear sketches
- Beating CountSketch for heavy hitters in insertion streams
- Improved Concentration Bounds for Count-Sketch
- Continuous sampling from distributed streams
- Near-optimal private approximation protocols via a black box transformation
- Fast monte-carlo algorithms for finding low-rank approximations
- Elements of Information Theory
- Streaming Algorithms via Precision Sampling
- Exact sublinear binomial sampling
