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.

基于哈希的数据结构和算法目前是Internet中蓬勃发展的行业，特别是对于与测量，监视和安全性有关的应用程序。 哈希表和相关结构（例如布卢姆过滤器）每天使用数十亿次，而新用途不断增强。 但是，这些结构的理论设计与分析与实践中的使用和实施之间仍然存在很大的差距。 这项研究旨在弥合利用哈希的算法和数据结构的理论和实践之间的差距，重点是网络应用程序。 这项研究的结果将包括将理论结果转化为现实环境的工具和框架，对现有算法和数据结构的更好分析和实施以及对新算法和数据结构的开发和分析。 相关的教育工作将集中于使本科生，研究生和专业网络社区的方法更加了解基于哈希的方法的潜在和力量，从而扩大了该领域理论工作的影响力和影响力。