Stochastic petri nets for modelling and simulation
Peter J. Haas
WSC 2004
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. © 2013 Springer-Verlag Berlin Heidelberg.
Peter J. Haas
WSC 2004
Ahmed Elgohary, Matthias Boehm, et al.
VLDB 2016
Meena Nagarajan, Angela D. Wilkins, et al.
KDD 2015
Mohamed Y. Eltabakh, Yuanyuan Tian, et al.
VLDB