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

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

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.