AF: SMALL: Relational Algorithms

AF：小：关系算法

• 批准号: 2209654
• 负责人: Kirk Pruhs
• 金额: $ 25.08万
• 依托单位: University of Pittsburgh
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2209654&HistoricalAwards=false
• 关键词: AF; SMALL; Relational; Algorithms

The use of relational databases, which store data in relational form in multiple tables, is a ubiquitous technology among American businesses and organizations. The four most commonly used databases (Oracle, MySQL, Microsoft SQL Server, PostgreSQL) are all relational. The use of machine learning to glean competitive insights from their data is also a ubiquitous technology among American businesses and organizations. Thus machine-learning tasks on relational data are ubiquitous. However, essentially all standard machine-learning algorithms require the input be in the form of a single table, and thus these algorithms can not operate directly on data hat is stored in relational form. Further, it is far from obvious if and how one can adapt many of these machine-learning algorithms to efficiently operate on data in relational form. Thus the standard practice is to first join together multiple tables inside the relational database into a single larger table, and then export this table to a standard machine-learning package. Joining tables is a time-consuming operation, requiring exponential time and memory in the worst case. The goal of this project is to develop relational algorithms, which are efficient algorithms that work directly on the relational tables and thus avoid expensive join operations, for common machine-learning problems. More efficient algorithms for standard machine learning problems on relational data would allow American companies and organizations to more efficiently glean competitive insights from their relational data. There are four goals for this project. The first goal is to develop relational algorithms for basic geometric problems that underlie many common machine-learning problems. These algorithms can then be used as the building blocks to develop relational algorithms for more complicated machine-learning problems. The second goal is to develop relational algorithms for standard machine-learning problems. Plan A is to design a relational implementation of the standard algorithm, plan B is to design an alternate relational algorithm with the same performance guarantee as the standard algorithm, and plan C is to design a relational algorithm with an alternate reasonable performance guarantee. The third goal is to develop foundational algorithmic-design and -analysis techniques. The fourth goal is to understand the limitations of relational algorithms as there may well be problems where relational algorithms are not possible. The investigators will determine which of the myriad algorithmic tools in the standard algorithmic toolkit are of utility in developing relational algorithms. In some cases the application of a known technique will require some novelty. In some cases no existing algorithmic tool will do the job, and the investigators will invent new algorithmic-design and -analysis techniques. As is the norm in algorithmic foundations research, the recognition that a particular algorithm-design or -analysis technique is of wide applicability, and the understanding of the limitations of these techniques occurs naturally during the process of the design and analysis of algorithms for specific problems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

关系数据库将数据以关系形式存储在多个表中，这种技术在美国企业和组织中无处不在。最常用的四种数据库（Oracle, MySQL, Microsoft SQL Server, PostgreSQL）都是关系型数据库。在美国的企业和组织中，利用机器学习从数据中收集有竞争力的见解也是一项无处不在的技术。因此，基于关系数据的机器学习任务无处不在。然而，基本上所有标准的机器学习算法都要求输入是单个表的形式，因此这些算法不能直接操作以关系形式存储的数据。此外，是否以及如何调整这些机器学习算法来有效地操作关系形式的数据还远不明显。因此，标准做法是首先将关系数据库中的多个表连接到一个更大的表中，然后将这个表导出到一个标准的机器学习包中。连接表是一项耗时的操作，在最坏的情况下需要指数级的时间和内存。这个项目的目标是开发关系算法，这是直接在关系表上工作的高效算法，从而避免昂贵的连接操作，用于常见的机器学习问题。针对关系数据的标准机器学习问题，更有效的算法将使美国公司和组织能够更有效地从关系数据中收集竞争洞察。这个项目有四个目标。第一个目标是开发基本几何问题的关系算法，这些问题是许多常见机器学习问题的基础。然后，这些算法可以用作构建块，为更复杂的机器学习问题开发关系算法。第二个目标是为标准的机器学习问题开发关系算法。计划A是设计一个标准算法的关系实现，计划B是设计一个与标准算法具有相同性能保证的备用关系算法，计划C是设计一个具有合理的备用性能保证的关系算法。第三个目标是发展基本的算法设计和分析技术。第四个目标是了解关系算法的局限性，因为很可能存在关系算法无法解决的问题。研究人员将确定标准算法工具包中无数算法工具中的哪一个在开发关系算法中是实用的。在某些情况下，应用已知的技术需要一些新颖性。在某些情况下，现有的算法工具无法完成这项工作，研究人员将发明新的算法设计和分析技术。作为算法基础研究的规范，在为特定问题设计和分析算法的过程中，自然会认识到特定的算法设计或分析技术具有广泛的适用性，并了解这些技术的局限性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Resource Augmentation Analysis of the Greedy Algorithm for the Online Transportation Problem

在线交通问题贪心算法的资源增强分析

• 发表时间: 2023
• 期刊: Graphs and Optimization Symposium
• 作者: Stephen Arndt, Josh Ascher