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