ITR: Sublinear Algorithms for Massive Data Sets

操作大规模数据源会导致问题什么是有效的算法。即使是线性时间算法在真正的海量数据上也可能太慢。类似地，当生成的输入数据过于庞大时，即使使用线性空间来存储数据也可能是不合理的。在这些限制是自然的情况下，应用程序比比皆是。例如，将互联网上的网页、所有电话记录或分子序列存档的数据存储是海量的，甚至处理它们的线性时间算法也被证明是缓慢的。数据源，如网络流量测量是大量的，很少得到存档;相反，它是可取的，以处理它们，因为它们产生，以获得合适的次线性空间表示。构建次线性算法的两种方法是采样和流。在采样中，算法检查输入的（小）子集，并在次线性时间内解决感兴趣的问题，通常是某种可证明的近似。虽然采样已经在概率和统计学中研究了几十年，但用于复杂任务（如聚类和构建傅立叶表示）的真正次线性算法直到最近才获得。这些算法应该有坚实的理论基础，并且应该能够使用严格的理论工具进行分析。然而，其中一些算法也将被实现并接受实验评估。预计在本项目背景下开发的算法将产生重大的实际影响。

Manipulating large scale data sources leads to question what are efficient algorithms. Even linear time algorithms may be much too slow on truly massive data. Similarly, even using linear spaceto store the data may be unreasonable when input data that is generated is far too voluminous. Applications abound where these constraints are natural. For example, data stores that archive web pages on the Internet, all telephone call records or molecular sequences are massive, and even linear time algorithms to process them prove slow. Data sources such as network traffic measurements are voluminous and rarely get archived; instead, it is desirable to process them as they are generated to obtain suitable sublinear space representations. Two approaches to building sublinear algorithms are sampling and streaming. In sampling, algorithms examine a (small) subset of input and solve problems of interest in sublinear time, typically to some provable approximation. While sampling has been studied in Probability and Statistics for decades, truly sublinear algorithms for sophisticated tasks such as clustering and building fourier representations have only recently been obtained. The algorithms should have solid theoretical foundations, and should be amenable to analysis using rigorous theoretical tools. However, some of the algorithms will be also implemented and subjected to experimental evaluation. It is expected that the algorithms developed in the context of this projectwill have significant practical impact.