Optimal sampling from sliding windows

DOI10.1016/J.JCSS.2011.04.004zbMATH Open1242.68081OpenAlexW2031034601MaRDI QIDQ414877FDOQ414877

Authors: Vladimir Braverman, Carlo Zaniolo, 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

Recommendations

• Optimal sampling for density estimation in continuous time
• scientific article; zbMATH DE number 513151
• scientific article; zbMATH DE number 4084788
• scientific article; zbMATH DE number 2119720
• Optimal sampling strategies for multiscale stochastic processes
• Optimal sequential sampling from two populations.
• Random sampling in multi-window quasi shift-invariant spaces
• Efficient sampling in approximate dynamic programming algorithms

zbMATH Keywords

sliding windowsrandom samplingdata streams

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Data structures (68P05)

Cites Work

• Title not available (Why is that?)
• Data streams. Models and algorithms.
• The DLT priority sampling is essentially optimal
• Sampling lower bounds via information theory
• Optimal approximations of the frequency moments of data streams
• Random sampling with a reservoir
• Title not available (Why is that?)
• Sampling algorithms
• Sampling in dynamic data streams and applications
• Data streams: algorithms and applications.
• An information statistics approach to data stream and communication complexity
• Title not available (Why is that?)
• Computing and Combinatorics
• Size-estimation framework with applications to transitive closure and reachability
• Title not available (Why is that?)
• Summarizing data using bottom-k sketches
• Testing and spot-checking of data streams
• Computing diameter in the streaming and sliding-window models
• Title not available (Why is that?)
• Sequential reservoir sampling with a nonuniform distribution
• Title not available (Why is that?)
• 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
• Reservoir-sampling algorithms of time complexity O ( n (1 + log( N / n )))
• Title not available (Why is that?)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Database Theory - ICDT 2005
• Estimating Entropy and Entropy Norm on Data Streams
• Title not available (Why is that?)
• When Random Sampling Preserves Privacy
• Distributed streams algorithms for sliding windows

Cited In (13)

• Title not available (Why is that?)
• Sampling streaming data with replacement
• Perfect $L_p$ Sampling in a Data Stream
• Title not available (Why is that?)
• Distributed streams algorithms for sliding windows
• Parallel Streaming Random Sampling
• Optimal convergence rates of high order Parzen windows with unbounded sampling
• Secure sampling with sublinear communication
• Title not available (Why is that?)
• Derandomization for sliding window algorithms with strict correctness
• Optimal Random Sampling from Distributed Streams Revisited
• Title not available (Why is that?)
• Symmetric norm estimation and regression on sliding windows

This page was built for publication: Optimal sampling from sliding windows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414877)