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.

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

项目成果

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