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
Year2007
Month1
Day1
Volume Number19
Issue Number1
PublisherInstitute of Electrical and Electronics Engineers
Place of PublicationUnited States
Pages96 - 110
ISSN1041-4347
eISSN1558-2191
LanguagesEnglish-United Kingdom
KeywordsSampling, Selectivity estimation

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