Optimal sampling from sliding windows
From MaRDI portal
Publication:414877
DOI10.1016/j.jcss.2011.04.004zbMath1242.68081MaRDI QIDQ414877
Rafail Ostrovsky, Carlo Zaniolo, Vladimir Braverman
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
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
