AF: Small: Algorithms and Data Structures with Predictions

AF：小：具有预测的算法和数据结构

• 批准号: 2101140
• 负责人: Michael Mitzenmacher
• 金额: $ 40万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-15 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2101140&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Data; Structures

The goal of this project is to develop improved algorithms and data structures for real-world problems by making use of predictions, such as predictions obtained from machine-learning methods. Traditional standard algorithms are analyzed based on worst-case performance; one considers the worst possible running time on the worst possible input. If an algorithm is given a suitable hint, or prediction, such as from a scanner that determines properties of the input, it may be able to avoid the worst case in practice. For example, if an algorithm could predict when people were waiting in line for service who would only need a small amount of time and who would need a long amount of time, it could order people in line to speed up how quickly people were served, avoiding situations where one person held up the entire line of waiting people. Given the general success of machine-learning techniques, bringing machine-learning predictions into standard algorithmic frameworks may yield important gains in real-world performance, while still providing rigorous performance guarantees. Additional components of this project involve developing materials so that the results of this research can be included in computer science courses, incorporating student work in the research, and broadening participation in computing through expanding educational and research opportunities for developing the next generation of researchers.Standard algorithms and data-structure analysis is based on worst-case performance. The idea of using additional information, such as predictions from machine-learning methods, to improve what can be rigorously proved about performance has been only very sparsely studied. Determining how to use such additional information provides a new method of what is commonly called beyond worst-case analysis, which strives to expand algorithmic analysis beyond the traditional worst-case methods. The ultimate goal is to provide frameworks that take advantage of the power of machine learning to provide good predictions based on the input data, while maintaining the advantages of the robustness and theoretical guarantees available from traditional algorithms. In particular, performance should still remain understandable and acceptable even if predictions are wrong; for example, in some settings, a goal could be that performance should never be much worse when using predictions, even if the predictions are provided adversarially. This area of study is intended to shed new light on long-existing algorithms and data structures, as well as require development of new analysis techniques. The investigator believes that algorithms and data structures of this form are likely to become ubiquitous in real-world systems, and thus theoretical understanding of them is important to characterize their risks and rewards.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.

该项目的目的是通过利用预测来开发改进的现实问题算法和数据结构，例如从机器学习方法获得的预测。 基于最差的性能分析了传统的标准算法；人们认为在最糟糕的输入中，最糟糕的运行时间。如果给出算法的适当提示或预测，例如从确定输入属性的扫描仪中，它可以避免在实践中避免最坏情况。 例如，如果算法可以预测人们何时排队等待服务，而服务只需要少量时间，并且需要长时间的时间，那么它可以命令人们加快人们的速度，以避免人们避开整个等待人的情况。 鉴于机器学习技术的一般成功，将机器学习预测带入标准算法框架可能会带来实际的性能中的重要增长，同时仍提供严格的性能保证。该项目的其他组成部分涉及开发材料，以便可以将这项研究的结果包括在计算机科学课程中，将学生的工作纳入研究中，并通过扩大发展下一代研究人员的教育和研究机会来扩展计算的参与。Standard算法和数据结构分析基于最差的表现。 使用其他信息（例如机器学习方法的预测）来改善对性能的严格证明的想法仅经过非常稀疏的研究。 确定如何使用此类附加信息提供了一种新方法，即除了最坏情况分析之外通常所谓的通常所谓的内容，该方法旨在将算法分析扩展到传统的最坏情况之外。 最终目标是提供利用机器学习力量的框架，以根据输入数据提供良好的预测，同时保持稳健性和传统算法可用的理论保证的优势。 特别是，即使预测是错误的，绩效仍然可以保持可理解和可接受。例如，在某些设置中，一个目标可能是使用预测时的性能永远不会更糟，即使对对手提供了预测。 该研究领域旨在为长期存在的算法和数据结构提供新的启示，并需要开发新的分析技术。 研究人员认为，这种形式的算法和数据结构可能在现实世界中变得无处不在，因此对它们的理论理解对于表征其风险和奖励很重要。该奖项反映了NSF的法定任务，并通过使用该基金会的智力功能和广泛的影响来评估CRITERIA CRITERIA CRITERIA。

项目成果

The Supermarket Model with Known and Predicted Service Times

• DOI: 10.1109/tpds.2022.3146195
• 发表时间: 2019-05
• 期刊: IEEE Transactions on Parallel and Distributed Systems
• 影响因子: 5.3
• 作者: M. Mitzenmacher;Matteo Dell'Amico

SNARF: A Learning-Enhanced Range Filter

• DOI: 10.14778/3529337.3529347
• 发表时间: 2022-04
• 期刊: Proc. VLDB Endow.
• 作者: Kapil Vaidya;Tim Kraska;Subarna Chatterjee;Eric R. Knorr;M. Mitzenmacher;Stratos Idreos

Algorithmic Tools for Understanding the Motif Structure of Networks

• DOI: 10.1007/978-3-031-26390-3_1
• 发表时间: 2022
• 作者: Tianyi Chen;Brian Matejek;M. Mitzenmacher;Charalampos E. Tsourakakis

Zero-CPU Collection with Direct Telemetry Access

• DOI: 10.1145/3484266.3487366
• 发表时间: 2021-10
• 期刊: Proceedings of the 20th ACM Workshop on Hot Topics in Networks
• 作者: Jonatan Langlet;Ran Ben Basat;Sivaramakrishnan Ramanathan;G. Oliaro;M. Mitzenmacher;Minlan Yu;G. Antichi

Uniform Bounds for Scheduling with Job Size Estimates

使用作业规模估计进行调度的统一界限

• DOI: 10.4230/lipics.itcs.2022.114
• 发表时间: 2022
• 期刊: ITCS
• 作者: Scully, Z;Grosof, I.;Mitzenmacher, M.
• 通讯作者: Mitzenmacher, M.