The complexity of massive data set computations
The complexity of massive data set computations
复制标题
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Ziv Bar-Yossef;C. Papadimitriou
中科院分区：
文献类型：
--
作者：
Ziv Bar-Yossef;C. Papadimitriou
在过去的几年中，已经出现了许多大量数据集，从互联网流量到超市交易的日志不等。他们的大小和通常限制对它们的限制访问需要新的计算模型。本文研究了三个这样的模型：抽样计算，数据流计算和草图计算。尽管以前的大多数工作都集中在新模型中设计算法，但本文围绕模型的局限性进行了围绕。我们开发了一组较低技术的套件，这些技术表征了这些模型中功能的复杂性，表明在其中有效解决哪些问题。我们为多种实际问题提供了特定的界限，这是由于数据库，网络和信息检索的应用而引起的，例如频率统计，选择功能，统计矩和距离估计。我们提出了对采样模型的一般，功能强大且易于使用的下限技术。这些技术适用于所有功能，并解决遗忘和自适应采样。它们经常为广泛的功能产生最佳界限。它们是根据函数的新组合和统计特性所陈述的，这些函数易于计算。我们通过单向和同时通信复杂性获得数据流的下限，并为模型绘制模型。我们通过通信复杂性的新信息理论来为后者开发下界。这项工作的亮点是重要的多方设定与连接问题的最佳同时通信复杂性下限。最后，我们提出了一种证明一般通信复杂性的下限的强大方法。该方法基于用于通信复杂性协议的新复杂性量度的直接总和属性以及通信复杂性的新颖统计观点。我们使用该技术来获得改进的通信复杂性和数据流下限，以解决多个问题，包括多方设定界限，频率矩和LP距离估计。这些结果解决了Alon，Matias和Szegedy以及Saks and Sun的开放问题。
Numerous massive data sets, ranging from flows of Internet traffic to logs of supermarket transactions, have emerged during the past few years. Their overwhelming size and the typically restricted access to them call for new computational models. This thesis studies three such models: sampling computations, data stream computations, and sketch computations. While most of the previous work focused on designing algorithms in the new models, this thesis revolves around the limitations of the models. We develop a suite of lower bound techniques that characterize the complexity of functions in these models, indicating which problems can be solved efficiently in them. We derive specific bounds for a multitude of practical problems, arising from applications in database, networking, and information retrieval, such as frequency statistics, selection functions, statistical moments, and distance estimation. We present general, powerful, and easy to use lower bound techniques for the sampling model. The techniques apply to all functions and address both oblivious and adaptive sampling. They frequently produce optimal bounds for a wide range of functions. They are stated in terms of new combinatorial and statistical properties of functions, which are easy to calculate. We obtain lower bounds for the data stream and sketch models through one-way and simultaneous communication complexity. We develop lower bounds for the latter via a new information-theoretic view of communication complexity. A highlight of this work is an optimal simultaneous communication complexity lower bound for the important multi-party set-disjointness problem. Finally, we present a powerful method for proving lower bounds for general communication complexity. The method is based on a direct sum property of a new measure of complexity for communication complexity protocols and on a novel statistical view of communication complexity. We use the technique to obtain improved communication complexity and data stream lower bounds for several problems, including multi-party set-disjointness, frequency moments, and Lp distance estimation. These results solve open problems of Alon, Matias, and Szegedy and of Saks and Sun.