AF: Small: Sublinear Algorithms for Real Data

AF：小：真实数据的次线性算法

• 批准号: 1422975
• 负责人: Sofya Raskhodnikova
• 金额: $ 45万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-06-01 至 2018-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422975&HistoricalAwards=false
• 关键词: AF; Small; Sublinear; Algorithms; Real

The area of sublinear algorithms aims to establish algorithmic foundations for processing big data. What global properties of the data can we understand while reading only a small portion of it? What if the data is noisy? Can we quickly restore a corrupted data point while ensuring some global property of the data? This project focuses specifically on sublinear algorithms for real-valued numeric data and on real-world challenges associated with it.Effectively exploiting big data can provide significant societal benefits. This project has the potential to change how real-valued data is processed and analyzed, and how privacy of sensitive datasets is handled. In addition, this project includes educational activities designed to ensure the work's broader impact and to improve workforce training. They include advising and mentoring graduate students; continuing to build a strong theoretical foundations group at Penn State; including the results of the proposed research in the PI's graduate course on sublinear algorithms; widely disseminating the results of this research and, more broadly, algorithmic and computational ideas via talks and publications; and fostering diversity by providing mentoring and educational activities targeted at women in computer science and mathematics.While there are established and successful lines of research in sublinear algorithms and property testing on Boolean functions, codes (and, more generally, algebraic properties), graphs, and discrete distributions, several recent applications of sublinear algorithms require working with real data. These include the study of Lipschitz functions with applications to data privacy and the study of submodular functions with applications to economics. To achieve their full potential, sublinear algorithms need to be able to handle real-valued data. The aim of this project is to lay the foundations for this area of study. This will require the development of new tools and will open up new connections and new areas of application. The research activities are grouped into three parts: 1. testing and local reconstruction of Lipschitz functions with applications to data privacy; 2. new measures for accuracy guarantees, with the focus on L_p metrics; and 3. new models for data access.

次线性算法领域旨在为处理大数据建立算法基础。当我们只读取数据的一小部分时，我们能理解数据的哪些全局属性？如果数据有噪声怎么办？我们能否快速恢复损坏的数据点，同时确保数据的一些全局属性？该项目特别侧重于实值数值数据的次线性算法以及与之相关的现实挑战。有效利用大数据可以提供显著的社会效益。该项目有可能改变实值数据的处理和分析方式，以及敏感数据集的隐私处理方式。此外，该项目还包括旨在确保工作产生更广泛影响和改善劳动力培训的教育活动。其中包括为研究生提供咨询和指导；继续在宾夕法尼亚州立大学建立一个强大的理论基础小组；包括PI关于次线性算法的研究生课程的拟议研究结果；通过讲座和出版物广泛传播这项研究的结果，更广泛地传播算法和计算思想；并通过在计算机科学和数学领域为女性提供指导和教育活动来促进多样性。虽然在次线性算法和布尔函数、代码（以及更普遍的代数性质）、图和离散分布的性质测试方面已经建立了成功的研究路线，但次线性算法的一些最新应用需要处理真实数据。这些研究包括应用于数据隐私的Lipschitz函数的研究和应用于经济学的子模块函数的研究。为了充分发挥其潜力，次线性算法需要能够处理实值数据。这个项目的目的是为这一研究领域奠定基础。这将需要开发新的工具，并将开辟新的联系和新的应用领域。本文的研究活动分为三个部分：1。Lipschitz函数的测试与局部重构及其在数据隐私中的应用2. 新的准确性保证措施，重点是L_p指标；和3。数据访问的新模型。