AF: Small: Sublinear Algorithms for Real Data

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

• 批准号: 1832228
• 负责人: Sofya Raskhodnikova
• 金额: $ 13.59万
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-24 至 2019-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1832228&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.数据访问的新模式。