CAREER: Sublinear Algorithms --- Theory and Applications

职业：次线性算法 --- 理论与应用

• 批准号: 0845701
• 负责人: Sofya Raskhodnikova
• 金额: $ 29.39万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0845701&HistoricalAwards=false
• 关键词: CAREER; Sublinear; Algorithms; Theory; Applications

The amount of existing and newly appearing data accumulated by scientific, governmental and business organizations around the world is daunting. As data of all types gets easier to obtain and cheaper to store, data sets are becoming increasingly large. Consequently, there is a need to perform computational tasks on massive data sets: comparing genomes, compressing media files, searching through and clustering large sets of documents, studying the Internet graph, and compiling census data, to name just a few. This research project has its roots in the following question, fundamental to several fields:* Can we still compute something useful about a data set when reading all of it is prohibitively expensive? In other words, what can we do in time sublinear in the length of the input?For most interesting problems, an exact algorithm provably has to read the entire input, and thus requires at least linear time. However, sublinear algorithms hold the promise of extremely efficient approximate computations.This award integrates research activities aimed at broadening the scope and extending the applicability of sublinear algorithms, with educational activities aimed at building a strong theoretical computer science group at Penn State and broadly disseminating new findings. It pursues three general directions for investigating the power of sublinear algorithms: (1) designing and analyzing new sublinear algorithms for concrete tasks that are used in a variety of applications and require new techniques, (2) building the foundations for a coherent theory of sublinear computation, with the focus on generic techniques for algorithm design and analysis, and new models for data access, (3) exploiting the special structure of problems solvable with sublinear-space algorithms in contexts (e.g., data privacy), where extreme efficiency is not a requirement per se, but helps to guarantee other properties, such a robustness to small changes in the data. A theme common to all three directions is to encompass new problems and models of practical relevance.

世界各地的科学、政府和商业组织积累的现有和新出现的数据数量令人生畏。随着所有类型的数据变得更容易获取和更便宜的存储，数据集变得越来越大。因此，需要在大量数据集上执行计算任务：比较基因组、压缩媒体文件、搜索和聚类大型文档集、研究互联网图和编译人口普查数据，等等。这个研究项目的根源在于以下几个领域的基本问题：*当读取所有数据集的成本过高时，我们还能计算出一些有用的数据集吗？换句话说，我们能在输入长度的时间下做什么？对于大多数有趣的问题，一个精确的算法显然必须读取整个输入，因此至少需要线性时间。然而，次线性算法有望实现极其高效的近似计算。该奖项整合了旨在扩大次线性算法范围和适用性的研究活动，以及旨在在宾夕法尼亚州立大学建立强大的理论计算机科学小组和广泛传播新发现的教育活动。它在研究次线性算法的能力方面追求三个一般方向：(1)设计和分析用于各种应用和需要新技术的具体任务的新次线性算法；(2)为次线性计算的连贯理论建立基础，重点是算法设计和分析的通用技术，以及数据访问的新模型；(3)利用次线性空间算法在上下文（例如，数据隐私）中可解决的问题的特殊结构；在这种情况下，极端的效率本身并不是必需的，但它有助于保证其他属性，例如对数据中的微小变化的鲁棒性。所有三个方向的共同主题是包含具有实际意义的新问题和模型。