ITR: Sublinear Algorithms for Massive Data Sets

ITR：海量数据集的次线性算法

• 批准号: 0220280
• 负责人: Shanmugavelayu Muthukrishnan
• 金额: $ 39万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-08-15 至 2007-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0220280&HistoricalAwards=false
• 关键词: ITR; Sublinear; Algorithms; Massive; Data

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.

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