Sampling time-based sliding windows in bounded space
Sampling time-based sliding windows in bounded space
复制标题
有界空间中基于时间的滑动窗口采样
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Wolfgang Lehner
中科院分区：
文献类型：
--
作者：
Rainer Gemulla;Wolfgang Lehner
随机采样是一种很有吸引力的方法来构建大型数据流的概要，因为随机样本可以用于广泛的分析任务。用户通常只对分析数据流的最新部分感兴趣，以避免过时的结果。在本文中，我们专注于从最近的时间间隔滑动窗口采样的采样方案，这样的窗口是一种流行的和高度理解的方法来模拟近因。在这种情况下，主要的挑战是保证样本的空间消耗的上限，同时有效地使用分配的空间。困难来自于窗口中的项目数量事先未知并且可能随时间显著变化的事实，使得采样分数必须动态调整。我们考虑均匀抽样方案，它产生相同大小的每个样本具有相等的概率，分层抽样方案，其中窗口被划分为更小的层和一个统一的样本是保持每层。对于均匀抽样，我们证明了在有界空间中不可能保证最小样本量。然后，我们介绍了一种新的采样方案称为有界优先级采样（BPS），它只需要有界的空间。我们推导出一个下界的预期样本大小，并表明BPS快速适应不断变化的数据速率。对于分层抽样，我们提出了一个合并为基础的分层方案（MBS），它保持阶层的大小大致相等。与朴素分层相比，MBS的优点是样本在窗口中均匀分布，因此窗口的任何部分都不会被过度代表或代表不足。最后，我们总结了我们的算法在大型现实世界的数据集上的可行性研究。
Random sampling is an appealing approach to build synopses of large data streams because random samples can be used for a broad spectrum of analytical tasks. Users are often interested in analyzing only the most recent fraction of the data stream in order to avoid outdated results. In this paper, we focus on sampling schemes that sample from a sliding window over a recent time interval; such windows are a popular and highly comprehensible method to model recency. In this setting, the main challenge is to guarantee an upper bound on the space consumption of the sample while using the allotted space efficiently at the same time. The difficulty arises from the fact that the number of items in the window is unknown in advance and may vary significantly over time, so that the sampling fraction has to be adjusted dynamically. We consider uniform sampling schemes, which produce each sample of the same size with equal probability, and stratified sampling schemes, in which the window is divided into smaller strata and a uniform sample is maintained per stratum. For uniform sampling, we prove that it is impossible to guarantee a minimum sample size in bounded space. We then introduce a novel sampling scheme called bounded priority sampling (BPS), which requires only bounded space. We derive a lower bound on the expected sample size and show that BPS quickly adapts to changing data rates. For stratified sampling, we propose a merge-based stratification scheme (MBS), which maintains strata of approximately equal size. Compared to naive stratification, MBS has the advantage that the sample is evenly distributed across the window, so that no part of the window is over- or underrepresented. We conclude the paper with a feasibility study of our algorithms on large real-world datasets.