Optimal sampling from sliding windows
From MaRDI portal
Publication:414877
DOI10.1016/j.jcss.2011.04.004zbMath1242.68081OpenAlexW2031034601MaRDI 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
Data structures (68P05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (9)
Unnamed Item ⋮ Secure sampling with sublinear communication ⋮ Symmetric norm estimation and regression on sliding windows ⋮ Unnamed Item ⋮ Parallel Streaming Random Sampling ⋮ Unnamed Item ⋮ Derandomization for sliding window algorithms with strict correctness ⋮ Optimal Random Sampling from Distributed Streams Revisited ⋮ Perfect $L_p$ Sampling in a Data Stream
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
This page was built for publication: Optimal sampling from sliding windows
