A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream
A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream
复制标题
一种用于分布式流随机采样的简单消息最优算法
DOI：
10.1109/tkde.2016.2518679
复制
发表时间：
2016
影响因子：
8.9
通讯作者：
David P. Woodruff
中科院分区：
文献类型：
--
作者：
Y. Chung;Srikanta Tirthapura;David P. Woodruff
我们提出了一个简单的，消息优化的算法，用于维护一个随机样本从一个大的数据流，其输入元素分布在多个站点，通过一个中央协调器进行通信。在任何时间点，协调器所持有的元素集合都代表了迄今为止所观察到的所有元素集合中的均匀随机样本。当与以前的工作相比，我们的算法渐近提高系统中发送的消息的总数。我们提出了一个匹配的下限，表明我们的协议发送的消息的最佳数量达到一个常数的因素，具有很大的概率。我们还考虑了重要的情况下，在不同的网站上的元素的分布是不均匀的，并表明，对于这样的输入，我们的算法显着优于以前的解决方案。
We present a simple, message-optimal algorithm for maintaining a random sample from a large data stream whose input elements are distributed across multiple sites that communicate via a central coordinator. At any point in time, the set of elements held by the coordinator represent a uniform random sample from the set of all the elements observed so far. When compared with prior work, our algorithms asymptotically improve the total number of messages sent in the system. We present a matching lower bound, showing that our protocol sends the optimal number of messages up to a constant factor with large probability. We also consider the important case when the distribution of elements across different sites is non-uniform, and show that for such inputs, our algorithm significantly outperforms prior solutions.
DOI：
10.1016/j.jcss.2007.07.005
发表时间：
2008-09
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Jeremy T. Bradley;S. Gilmore;J. Hillston
通讯作者：
Jeremy T. Bradley;S. Gilmore;J. Hillston