Random sampling for continuous streams with arbitrary updates
Publication in refereed journal

Times Cited
Altmetrics Information

Other information
AbstractThe existing random sampling methods have at least one of the following disadvantages: they 1) are applicable only to certain update patterns, 2) entail large space overhead, or 3) incur prohibitive maintenance cost. These drawbacks prevent their effective application in stream environments (where a relation is updated by a large volume of insertions and deletions that may arrive in any order), despite the considerable success of random sampling in conventional databases. Motivated by this, we develop several fully dynamic algorithms for obtaining random samples from individual relations, and from the join result of two tables. Our solutions can handle any update pattern with small space and computational overhead. We also present an in-depth analysis that provides valuable insight into the characteristics of alternative sampling strategies and leads to precision guarantees. Extensive experiments validate our theoretical findings and demonstrate the efficiency of our techniques in practice. © 2007 IEEE.
All Author(s) ListYufei T., Xiang L., Papadias D., Hadjieleftheriou M.
Journal nameIEEE Transactions on Knowledge and Data Engineering
Volume Number19
Issue Number1
PublisherInstitute of Electrical and Electronics Engineers
Place of PublicationUnited States
Pages96 - 110
LanguagesEnglish-United Kingdom
KeywordsSampling, Selectivity estimation

Last updated on 2020-07-07 at 02:56