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.