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

Harvard University, Cambridge MA

Investigators

Abstract

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.