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.