Massive Data Streams: Algorithms and Complexity

摘要：海量数据集在观测科学、产品营销以及大型系统的监控和运行等诸多应用中发挥着越来越重要的作用。在网络操作中，原始数据通常到达流，并且必须由算法做出决策，每个流生成一个逾越节，丢弃大部分原始数据，并生成“概要”或“草图”以供进一步处理。此外，网络生成的海量数据集通常是分布式的：几个不同的、物理上分离的网络元素可能会接收或生成数据流，这些数据流一起组成一个逻辑数据集。对感兴趣的数据集的巨大规模、分布式性质和一次处理要求必须通过新的算法技术来解决。针对海量数据集的两种编程范式是“采样”和“流”。抽样算法提取一个小的随机样本并对其进行计算，而不是花时间去读取一个庞大的数据集。相比之下，流算法需要时间来读取所有输入，但时间和总空间都很少。流算法的输入是一个项目序列；流算法按顺序给出项目，缺乏空间来记录超过少量的输入，并且需要快速执行每个项目的处理，以跟上未缓冲的输入。研究人员继续研究大规模数据流的基本算法。感兴趣的具体问题包括但不限于证明数据流属性的复杂性，构建大规模图属性的一次性测试器，以及聚类的流空间复杂性。

Title: "Massive Data Streams: Algorithms and Complexity"Investigators: Joan Feigenbaum and Sampath KannanAbstract: Massive data sets are increasingly important in many applications,including observational sciences, product marketing, and monitoring andoperations of large systems. In network operations, raw data typically arrivein streams, and decisions must be made by algorithms that make one passover each stream, throw much of the raw data away, and produce ``synopses''or ``sketches'' for further processing. Moreover, network-generated massivedata sets are often distributed: Several different, physically separatednetwork elements may receive or generate data streams that, together, compriseone logical data set. The enormous scale, distributed nature, and one-pass processing requirement on the data sets of interest must be addressed with new algorithmic techniques. Two programming paradigms for massive data sets are "sampling" and"streaming." Rather than take time even to read a massive dataset, a sampling algorithm extracts a small random sample and computeson it. By contrast, a streaming algorithm takes time to read all the input, but little more time and little total space. Input to a streaming algorithm is a sequence of items; the streaming algorithm is given the items in order, lacks space to record more than a small amount of the input, and is requiredto perform its per-item processing quickly in order to keep up withthe unbuffered input. The investigators continue the study of fundamental algorithms for massive data streams. Specific problems ofinterest include but are not limited to the complexity of proving properties of data streams, the construction of one-pass testers of properties of massive graphs, and the streaming space complexity of clustering.