- Titel
- Non-uniformity issues and workarounds in bounded-size sampling
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-831165
- Quellenangabe
- The VLDB Journal
Erscheinungsjahr: 2013
Jahrgang: 22
Heft: 6
Seiten: 753-772
E-ISSN: 0949-877X - Erstveröffentlichung
- 2013
- Abstract (EN)
- A variety of schemes have been proposed in the literature to speed up query processing and analytics by incrementally maintaining a bounded-size uniform sample from a dataset in the presence of a sequence of insertion, deletion, and update transactions. These algorithms vary according to whether the dataset is an ordinary set or a multiset and whether the transaction sequence consists only of insertions or can include deletions and updates. We report on subtle non-uniformity issues that we found in a number of these prior bounded-size sampling schemes, including some of our own. We provide workarounds that can avoid the non-uniformity problem; these workarounds are easy to implement and incur negligible additional cost. We also consider the impact of non-uniformity in practice and describe simple statistical tests that can help detect non-uniformity in new algorithms.
- Andere Ausgabe
- Link zum Artikel der zuerst in der Zeitschrift 'The VLDB Journal' bei Springer Link erschienen ist.
DOI: 10.1007/s00778-013-0307-0 - Freie Schlagwörter (DE)
- Datenbank-Probenahme, Reservoir-Probenahme, Bernoulli-Probenahme, Probenpflege
- Freie Schlagwörter (EN)
- Database sampling, Reservoir sampling, Bernoulli sampling, Sample maintenance
- Klassifikation (DDC)
- 004
- Verlag
- Springer, Berlin [u. a.]
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-831165
- Veröffentlichungsdatum Qucosa
- 27.01.2023
- Dokumenttyp
- Artikel
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
