Stratified random sampling (SRS) is a widely used sampling technique for
approximate query processing. We consider SRS on continuously arriving data
streams and statically stored data sets. We present a tight lower bound showing
that any streaming algorithm for SRS over the entire stream must have, in the
worst case, a variance that is $$\varOmega (r)$$ factor away from the optimal,
where r is the... hiện toàn bộ