Stochastic Streams: Sample Complexity vs. Space Complexity
Stochastic Streams: Sample Complexity vs. Space Complexity
复制标题
随机流：样本复杂性与空间复杂性
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
David P. Woodruff
中科院分区：
文献类型：
--
作者：
Michael S. Crouch;A. Mcgregor;G. Valiant;David P. Woodruff
我们解决处理大型数据集所需的计算资源与数据集可用的样本数量之间的权衡。具体而言，我们考虑以下抽象：我们从某些未知分布d中接收潜在的无限的IID样品流，并且负责计算某些函数f（d）。如果观察到时间t的流，则估计f（d）需要多少内存，s？我们将t称为样品复杂性，而s则称为空间复杂性。本文的主要重点是研究空间和样品复杂性之间的权衡。我们研究了在数据流模型中研究的几个规范问题的这些权衡：估计分布的碰撞概率的第二刻，决定是否连接了图并近似未知子空间的维度。我们的结果基于在此模型中模拟不同经典采样程序的技术，并在一系列IID样本中模拟随机步行，并利用通信有限协议和统计查询算法之间的表征。
We address the trade-off between the computational resources needed to process a large data set and the number of samples available from the data set. Specifically, we consider the following abstraction: we receive a potentially infinite stream of IID samples from some unknown distribution D, and are tasked with computing some function f(D). If the stream is observed for time t, how much memory, s, is required to estimate f(D)? We refer to t as the sample complexity and s as the space complexity. The main focus of this paper is investigating the trade-offs between the space and sample complexity. We study these trade-offs for several canonical problems studied in the data stream model: estimating the collision probability, i.e., the second moment of a distribution, deciding if a graph is connected, and approximating the dimension of an unknown subspace. Our results are based on techniques for simulating different classical sampling procedures in this model, emulating random walks given a sequence of IID samples, as well as leveraging a characterization between communication bounded protocols and statistical query algorithms.