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.

该项目的目标是通过利用预测，例如从机器学习方法获得的预测，为现实世界的问题开发改进的算法和数据结构。 传统的标准算法是基于最坏情况下的性能进行分析的;一个考虑最坏的可能输入的最坏的可能运行时间。如果算法被给予适当的提示或预测，例如从确定输入属性的扫描器，它可能能够避免实践中的最坏情况。 例如，如果一个算法可以预测人们排队等待服务的时间，谁只需要很短的时间，谁需要很长的时间，它可以命令排队的人加快服务速度，避免一个人阻碍整个排队等待的人的情况。 鉴于机器学习技术的普遍成功，将机器学习预测纳入标准算法框架可能会在现实世界的性能方面产生重要的收益，同时仍然提供严格的性能保证。该项目的其他组成部分包括开发材料，使这项研究的结果可以包括在计算机科学课程中，将学生的工作纳入研究，并通过扩大教育和研究机会来扩大参与计算，以培养下一代研究人员。标准算法和数据结构分析是基于最坏情况下的性能。 使用额外信息（例如机器学习方法的预测）来改善可以严格证明的性能的想法只得到了非常少的研究。 确定如何使用这些额外的信息提供了一种通常称为超越最坏情况分析的新方法，该方法致力于将算法分析扩展到传统的最坏情况方法之外。 最终目标是提供一个框架，利用机器学习的力量，根据输入数据提供良好的预测，同时保持传统算法的鲁棒性和理论保证的优势。 特别是，即使预测是错误的，性能仍然应该是可以理解和可接受的;例如，在某些情况下，目标可能是使用预测时性能永远不会更差，即使预测是以相反的方式提供的。 这一研究领域旨在揭示长期存在的算法和数据结构，以及需要开发新的分析技术。 研究人员认为，这种形式的算法和数据结构很可能在现实世界的系统中变得无处不在，因此对它们的理论理解对于描述其风险和回报非常重要。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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

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

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

DRIVE: One-bit Distributed Mean Estimation

• 发表时间: 2021-05
• 期刊: ArXiv
• 作者: S. Vargaftik;Ran Ben Basat;Amit Portnoy;Gal Mendelson;Y. Ben-Itzhak;M. Mitzenmacher