Optimal sampling from sliding windows

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

zbMATH Keywords

random sampling; data streams; sliding windows

Mathematics Subject Classification ID

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