External Memory Stream Sampling
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractThis paper aims to understand the I/O-complexity of maintaining a big sample set-whose size exceeds the internal memory's capacity-on a data stream. We study this topic in a new computation model, named the external memory stream (EMS) model, that naturally extends the standard external memory model to stream environments. A suite of EMS-indigenous techniques are presented to prove matching lower and upper bounds for with-replacement (WR) and without-replacement (WoR) sampling on append-only and time-based sliding window streams, respectively. Our results imply that, compared to RAM, the EMS model is perhaps a more suitable computation model for studying stream sampling, because the new model separates different problems by their hardness in ways that could not be observed in RAM.
All Author(s) ListHu X., Qiao M., Tao Y.
Name of Conference34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2015
Start Date of Conference21/05/2015
End Date of Conference04/06/2015
Place of ConferenceMelbourne
Country/Region of ConferenceAustralia
Volume Number31
Pages229 - 239
LanguagesEnglish-United Kingdom
KeywordsI/O-Efficient Algorithms, Lower Bound, Sampling, Stream

Last updated on 2020-09-08 at 04:14