Algorithms and lower bounds for sublinear processing of long sequences and large data

随着越来越多的应用程序生成和存储海量数据，海量数据的处理在许多领域变得至关重要。在这项提议中，我们感兴趣的是在存在资源限制的情况下处理大量数据。特别是，我们希望在性能测试、流和传感器网络聚合模型中开发算法，允许输入的时间和/或空间大小为次线性。显然，如此严格的限制意味着我们的算法提供的解决方案在许多情况下不是完全准确的；我们的目标之一是探索这些模型中精度和效率之间的权衡。我们将专注于与序列性质相关的问题，但随着我们开发更多的技术，我们将探索其他领域。

As more and more applications are generating and storing massive amounts of data, the processing of large data is becoming crucial in many fields. In this proposal we are interested in processing large amounts of data in the presence of resource constraints. In particular, we would like to develop algorithms in the property testing, streaming, and sensor network aggregation models, allowing time and/or space sublinear in the size of the input. Clearly, such tight restrictions imply that the solutions provided by our algorithms cannot be fully accurate in many cases; one of our goals is to explore the tradeoff between accuracy and efficiency in these models. We will focus on problems related to properties of sequences, but will explore other areas as we develop more techniques.