AF:III:Small:Collaborative Research: New Frontiers in Join Algorithms: Optimality, Noise, and Richer Languages

AF:III:Small:协作研究：连接算法的新领域：最优性、噪声和更丰富的语言

• 批准号: 1356918
• 负责人: Christopher Re
• 金额: $ 17.39万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1356918&HistoricalAwards=false
• 关键词: AF; III; Small; Collaborative; Research

The relational join is central to relational database processing, which is the dominant way data is processed today. The join also models problems in biological and social networks, coding theory, compressed sensing, machine learning, and constraint satisfaction. Recently,  the investigators described the first ever worst-case optimal algorithm (the NPRR algorithm) for join queries.  These new results open a line of new tools to attack a diverse set of fundamental problems related to the join. This project aims to further exploit the new algorithmic techniques developed for NPRR to address the following three classes of problems:(1) Optimal Join algorithms. Developing algorithms that are instance optimal when the data are stored in either traditional database indexes or new indexing structures is a goal of this project. (2) Coping with and Leveraging Noise. This project will extend the latest work to handle and leverage both worst-case and statistical noise models, bridging to coding theory and compressed sensing.  (3) Expressive Query Languages. The project will explore a series of extensions to join queries that will pave the way to overcome challenges in motif finding, search, databases with functional dependencies, and more powerful classes of queries and join operations.If successful, the results of this grant will apply to a variety of pattern extraction problems in modern massive, dynamic, and noisy data sets, which have a wide range of applications in complex network analysis, coding theory, and compressive sensing.

关系连接是关系数据库处理的核心，关系数据库处理是当今处理数据的主要方式。加入还模型的问题，在生物和社交网络，编码理论，压缩传感，机器学习和约束满足。最近，研究人员描述了第一个最坏情况下的连接查询优化算法（NPRR算法）。这些新的结果打开了一系列新的工具来解决与连接相关的各种基本问题。本计画的目的是进一步利用NPRR所发展的新演算法技术来解决下列三种问题：（1）最佳连接演算法。本项目的一个目标是，当数据存储在传统的数据库索引或新的索引结构中时，开发实例最优的算法。(2)应对和利用噪音。这个项目将扩展最新的工作，以处理和利用最坏情况和统计噪声模型，桥接编码理论和压缩感知。（3）表达查询语言。该项目将探索一系列连接查询的扩展，这些扩展将为克服motif查找，搜索，具有函数依赖关系的数据库以及更强大的查询和连接操作类别的挑战铺平道路。如果成功，该资助的结果将适用于现代海量，动态和噪声数据集中的各种模式提取问题，其在复杂网络分析、编码理论和压缩感知中具有广泛的应用。