Optimal sampling from sliding windows
From MaRDI portal
Publication:414877
DOI10.1016/j.jcss.2011.04.004zbMath1242.68081MaRDI QIDQ414877
Carlo Zaniolo, Vladimir Braverman, Rafail Ostrovsky
Publication date: 11 May 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.04.004
68P05: Data structures
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Unnamed Item, Derandomization for sliding window algorithms with strict correctness, Perfect $L_p$ Sampling in a Data Stream, Unnamed Item, Secure sampling with sublinear communication, Symmetric norm estimation and regression on sliding windows, Optimal Random Sampling from Distributed Streams Revisited, Unnamed Item, Parallel Streaming Random Sampling
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Distributed streams algorithms for sliding windows
- Size-estimation framework with applications to transitive closure and reachability
- Computing diameter in the streaming and sliding-window models
- Testing and spot-checking of data streams
- Data streams. Models and algorithms.
- The DLT priority sampling is essentially optimal
- Sequential reservoir sampling with a nonuniform distribution
- Sampling lower bounds via information theory
- Optimal approximations of the frequency moments of data streams
- Streaming and sublinear approximation of entropy and information distances
- Maintaining significant stream statistics over sliding windows
- Simpler algorithm for estimating frequency moments of data streams
- Random sampling with a reservoir
- Reservoir-sampling algorithms of time complexity O ( n (1 + log( N / n )))
- Sampling algorithms
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Database Theory - ICDT 2005
- Sampling in dynamic data streams and applications
- Summarizing data using bottom-k sketches
- Estimating Entropy and Entropy Norm on Data Streams
- Computing and Combinatorics
- When Random Sampling Preserves Privacy