Efficient sampling of non-strict turnstile data streams
Efficient sampling of non-strict turnstile data streams
复制标题
非严格旋转栅门数据流的高效采样
DOI：
10.1016/j.tcs.2015.01.026
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Bar Shalem
中科院分区：
文献类型：
--
作者：
Neta Barkay;E. Porat;Bar Shalem
本文研究了由元素（i，v）组成的数据流S生成大样本的问题，其中i是正整数key，v是等于key i的个数的整数，样本由（i，Ci）对组成，其中Ci =∑（i，v）∈ Sv.我们考虑了严格旋转栅门流和一般的非严格旋转栅门流，其中Ci可以是负的.我们的样本对于近似正向和反向分布统计量都很有用，在加性误差ε和可证明的成功概率1− δ范围内。我们的采样方法提高了一个数量级的每个流元素，在数据流应用程序中的一个关键因素，已知的处理时间，从而提供了一个可行的解决方案的采样问题。例如，对于非严格流中的大小为O（− 2 log（1/δ））的样本，我们的解决方案需要每个流元素O（（log log（1/δ））2+（log log（1/δ））2）次操作，而之前的最佳解决方案需要每个元素O（− 2 log 2（1/δ））次完全独立的哈希函数计算。我们通过构建一个有效的K元素恢复结构来实现这一改进，从该结构中可以以1− δ的概率提取K个元素。我们的结构使我们的采样算法能够在分布式系统上运行，并提取流之间差异的统计信息。
We study the problem of generating a large sample from a data stream S of elements (i, v), where i is a positive integer key, v is an integer equal to the count of key i, and the sample consists of pairs (i, C i) for C i=∑(i, v)∈ S v. We consider strict turnstile streams and general non-strict turnstile streams, in which C i may be negative. Our sample is useful for approximating both forward and inverse distribution statistics, within an additive error ϵ and provable success probability 1− δ. Our sampling method improves by an order of magnitude the known processing time of each stream element, a crucial factor in data stream applications, thereby providing a feasible solution to the sampling problem. For example, for a sample of size O (ϵ− 2 log(1/δ)) in non-strict streams, our solution requires O ((log log(1/ϵ)) 2+(log log(1/δ)) 2) operations per stream element, whereas the best previous solution requires O (ϵ− 2 log 2(1/δ)) evaluations of a fully independent hash function per element. We achieve this improvement by constructing an efficient K-elements recovery structure from which K elements can be extracted with probability 1− δ. Our structure enables our sampling algorithm to run on distributed systems and extract statistics on the difference between streams.