AitF: FULL: Collaborative Research: Better Hashing for Applications: From Nuts & Bolts to Asymptotics

AitF：完整：协作研究：更好的应用程序哈希：来自坚果

• 批准号: 1535795
• 负责人: Michael Mitzenmacher
• 金额: $ 25万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1535795&HistoricalAwards=false
• 关键词: AitF; FULL; Collaborative; Research; Better

This project engages experts in systems and network algorithms from Carnegie Mellon University and Harvard University to improve hashing-based data structures for systems. Hashing is an approach that turns a variable length string into a small, fixed-length value. Hashing provides a short, consistent fingerprint used to identify larger pieces of data, for uses including storing and locating data items quickly and effectively. Hashing provides a key building block for sophisticated approaches to storing, measuring, and managing data. Hashing-based data structures have correspondingly become widely accepted, often key workhorses throughout systems and networking.This project will create synergies between theory and systems in the area of hashing, with various approaches for lasting broader impact. Prototype code will be released for new algorithms and data structures created in the course of the project. Curricular materials focused on project material will be developed and distributed. The project will offer a wide range of research opportunities at various levels of sophistication for graduate and undergraduate students at both universities.The team unites expertise with theoretical design and analysis with expertise in systems design and analysis, allowing ideas and insights to flow between the two sides. The work starts from the lowest level of what choice of what hash functions to use, through the design and analysis of general data structures, to the development of applications that utilize hashing-based data structures to provide top performance. Project goals include both improving existing structures such as Bloom filters and cuckoo hash tables in practical systems to developing new structures for related problems such as maintaining small structures for fast function evaluation on key sets and reconciliation of datasets.

该项目聘请了卡内基梅隆大学和哈佛大学的系统和网络算法专家，以改进系统的基于散列的数据结构。 散列是一种将可变长度字符串转换为小的固定长度值的方法。 散列提供了一个简短、一致的指纹，用于识别较大的数据，用于快速有效地存储和定位数据项。 散列为存储、测量和管理数据的复杂方法提供了一个关键的构建块。基于散列的数据结构已相应地被广泛接受，通常是整个系统和网络的关键主力。该项目将在散列领域的理论和系统之间产生协同作用，并采用各种方法产生持久的更广泛的影响。将为项目过程中创建的新算法和数据结构发布原型代码。 将编制和分发以项目材料为重点的课程材料。 该项目将为两所大学的研究生和本科生提供各种复杂程度的广泛研究机会。该团队将理论设计和分析方面的专业知识与系统设计和分析方面的专业知识结合起来，使双方的想法和见解能够相互交流。 这项工作从最低级别的选择使用什么样的哈希函数开始，通过设计和分析一般数据结构，到开发利用基于哈希的数据结构来提供最高性能的应用程序。 项目目标包括改进现有的结构，如Bloom过滤器和布谷鸟哈希表在实际系统中开发相关问题的新结构，如维护小结构的快速功能评估的关键集和协调的数据集。

项目成果

Gradient Disaggregation: Breaking Privacy in Federated Learning by Reconstructing the User Participant Matrix

• 发表时间: 2021-06
• 作者: Maximilian Lam;Gu-Yeon Wei;D. Brooks;V. Reddi;M. Mitzenmacher

Putting the "Learning" into Learning-Augmented Algorithms for Frequency Estimation

• 发表时间: 2021
• 作者: Elbert Du;Franklyn Wang;M. Mitzenmacher

Queues with Small Advice

带有小建议的队列

• 发表时间: 2021
• 期刊: SIAM Conference on Applied and Computational Discrete Algorithms
• 作者: Mitzenmacher, Michael