AF : Small : The Theory and Practice of Hash-Based Algorithms and Data Structures

AF：小：基于哈希的算法和数据结构的理论与实践

• 批准号: 0915922
• 负责人: Michael Mitzenmacher
• 金额: $ 44.2万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915922&HistoricalAwards=false
• 关键词: AF; Small; Theory; Practice; Hash

Hash-based data structures and algorithms are currently a booming industry in the Internet, particularly for applications related to measurement, monitoring, and security. Hash tables and related structures such as Bloom filters are used billions of times a day, and new uses keep proliferating. There remain, however, large gaps between the theoretical design and analysis of these structures and their use and implementation in practice. This research aims to bridge the gap between the theory and practice of algorithms and data structures that utilize hashing, with an emphasis on networking applications. The outcomes of this research will include tools and frameworks for translating theoretical results into real-world settings, better analyses and implementations of existing algorithms and data structures, and the development and analysis of new algorithms and data structures. Related educational efforts will focus on methods to make undergraduate students, graduate students, and the professional networking community more aware of the potential and power of hash-based approaches, thereby expanding the reach and influence of theoretical work in the area.

基于散列的数据结构和算法目前在互联网上是一个蓬勃发展的行业，特别是在与测量、监控和安全相关的应用程序中。哈希表和相关结构，如布卢姆过滤器，每天被使用数十亿次，新的使用不断激增。然而，这些结构的理论设计和分析与其在实践中的使用和实施之间仍有很大差距。这项研究旨在弥合利用哈希的算法和数据结构的理论和实践之间的差距，重点是联网应用。这项研究的结果将包括将理论结果转化为现实世界环境的工具和框架，更好地分析和实施现有算法和数据结构，以及开发和分析新的算法和数据结构。相关的教育工作将集中在如何让本科生、研究生和专业网络社区更多地意识到基于哈希的方法的潜力和力量，从而扩大该领域理论工作的覆盖范围和影响。