AF: Small: Collaborative Research: Maintaining Order

AF：小：协作研究：维持秩序

• 批准号: 1617618
• 负责人: Michael Bender
• 金额: $ 21.03万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2021-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617618&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Maintaining

This project investigates "order structures," that is, data structures for maintaining total orders on dynamic data sets. Order structures are applicable in surprisingly diverse settings. The PIs aim to answer fundamental theoretical questions relating to order structures. The investigation takes place in the context of two high-impact application areas: (1) tools for debugging parallel programs and (2) data structures used in databases and file systems to organize data on disk or SSDs. As part of the project, the PIs will develop publicly available educational materials and reference implementations on order structures to be incorporated into courses at their institutions and shared openly on the web.The order structures addressed in this project are order-maintenance data structures, sparse tables, and data structures for incremental topological ordering. The investigation comprises (1) new algorithms with good worst-case guarantees, (2) algorithms with strong common-case guarantees, i.e., optimized for common input distributions, (3) provably good concurrent algorithms, (4) algorithms that leverage randomization in surprising ways (e.g., to achieve history independence), and (5) robust lower bounds that also apply to the randomized setting. In the context of the target applications, the PIs will design and use order structures to implement race detectors, which uncover determinacy races in parallel programs. The PIs will also use orders structures to build external-memory key-value stores to make databases and file systems run faster.

该项目研究了“订单结构”，即用于维持动态数据集的总订单的数据结构。 订单结构适用于令人惊讶的不同设置。 PI旨在回答与秩序结构有关的基本理论问题。调查发生在两个高影响应用程序领域的背景下：（1）调试并行程序的工具以及（2）数据库和文件系统中使用的数据结构，以组织磁盘或SSD上的数据。 作为项目的一部分，PI将开发公开可用的教育材料，并参考有关将要纳入其机构的订单结构并在网络上公开共享的订单结构。该项目中涉及的订单结构是订单维护数据结构，稀疏表和数据结构，用于增量拓扑订购。 该研究包括（1）具有良好最差保证的新算法，（2）具有强大的共同保证的算法，即针对共同输入分布进行了优化，（3）可证明并发算法，（4）在以惊人的方式（例如，在历史独立性的情况下）以随机的方式利用随机性的随机性（例如，以及（5）稳定的独立性），以及（5）较低的算法（5）。在目标应用程序的背景下，PI将设计和使用订单结构来实现种族探测器，该赛车探测器在并行程序中揭示了确定性种族。 PI还将使用订单结构来构建外部内存键值商店，以使数据库和文件系统运行速度更快。