Weighted Reservoir Sampling from Distributed Streams
Weighted Reservoir Sampling from Distributed Streams
复制标题
从分布式流中进行加权水库采样
DOI：
10.1145/3294052.3319696
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Woodruff, David P.
中科院分区：
文献类型：
--
作者：
Jayaram, Rajesh;Sharma, Gokarna;Tirthapura, Srikanta;Woodruff, David P.
我们考虑从分布式流中进行消息有效的连续随机采样，其中样本中包含项目的概率与与该项目相关的权重成比例。未加权的版本，其中所有的权重是相等的，是很好的研究，并承认严格的上限和下限的消息复杂性。对于带替换的加权抽样，有一个简单的简化为带替换的未加权抽样。然而，在许多应用中，流可能只有几个重项目，当选择替换时，这些重项目可能主导随机样本。加权抽样不更换（加权SWOR）避免了这个问题，因为这样重的项目可以抽样最多一次。在这项工作中，我们提出了第一个消息优化算法加权SWOR从分布式流。我们的算法也有最佳的空间和时间复杂度。作为加权SWOR算法的一个应用，我们推导出了第一个具有残差的分布式流跟踪算法。这里的目标是识别流项目的贡献显着的剩余流，一旦最重的项目被删除。剩余重打击者推广了重打击者的概念，并且在具有偏斜权重分布的流中很重要。除了上限，我们还提供了消息复杂度的下限，该下限几乎接近于$$log（1/\eps）$因子。最后，我们使用我们的加权采样算法来提高分布式跟踪的消息复杂度，也称为计数跟踪，这是一个广泛研究的问题，在分布式流。我们还得到了一个紧密的消息下界，关闭这个基本问题的消息复杂性。
We consider message-efficient continuous random sampling from a distributed stream, where the probability of inclusion of an item in the sample is proportional to a weight associated with the item. The unweighted version, where all weights are equal, is well studied, and admits tight upper and lower bounds on message complexity. For weighted sampling with replacement, there is a simple reduction to unweighted sampling with replacement. However, in many applications the stream may have only a few heavy items which may dominate a random sample when chosen with replacement. Weighted samplingwithout replacement (weighted SWOR) eludes this issue, since such heavy items can be sampled at most once. In this work, we present the first message-optimal algorithm for weighted SWOR from a distributed stream. Our algorithm also has optimal space and time complexity. As an application of our algorithm for weighted SWOR, we derive the first distributed streaming algorithms for trackingheavy hitters with residual error. Here the goal is to identify stream items that contribute significantly to the residual stream, once the heaviest items are removed. Residual heavy hitters generalize the notion ofheavy hitters and are important in streams that have a skewed distribution of weights. In addition to the upper bound, we also provide a lower bound on the message complexity that is nearly tight up to a $łog(1/\eps)$ factor. Finally, we use our weighted sampling algorithm to improve the message complexity of distributedtracking, also known as count tracking, which is a widely studied problem in distributed streaming. We also derive a tight message lower bound, which closes the message complexity of this fundamental problem.
登录
查看更多内容
加权采样，无需从数据流中替换
影响因子：
0.5
作者：
V. Braverman;R. Ostrovsky;G. Vorsanger
通讯作者：
G. Vorsanger
一种用于分布式流随机采样的简单消息最优算法
影响因子：
8.9
作者：
Y. Chung;Srikanta Tirthapura;David P. Woodruff
通讯作者：
David P. Woodruff
DOI：
10.1145/1559795.1559819
发表时间：
2009-06
期刊：
Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
Radu Berinde;Graham Cormode;P. Indyk;M. Strauss
通讯作者：
Radu Berinde;Graham Cormode;P. Indyk;M. Strauss
有界空间中基于时间的滑动窗口采样
DOI：
--
发表时间：
2008
期刊：
SIGMOD Conference
影响因子：
--
作者：
Rainer Gemulla;Wolfgang Lehner
通讯作者：
Wolfgang Lehner
影响因子：
1.1
作者：
Jiecao Chen;Qin Zhang
通讯作者：
Qin Zhang