CCF-BSF: AF: SMALL: COLLABORATIVE RESEARCH: THE DICTIONARY PROBLEM CONSIDERED

The performance of databases, file systems, and other data-storage systems depends on how the data is organized on disk. The data-organization parts of these systems are called dictionaries. Even though dictionaries have been studied for decades, some very basic questions remain unanswered. This grant will support research to address several of these questions. This research has the potential to improve performance of data-storage systems and applications based on these systems in many environments, including large-scale data analysis and high-performance computing. Dictionaries are so fundamental that theoretical advances in dictionaries are quickly picked up by practitioners, and thus this research has strong potential for tech transfer. Specifically, the project will tackle foundational problems in dictionaries using techniques in write-optimization pioneered by the PIs. How are systems of dictionaries different than individual dictionaries? How can dictionaries take advantage of variations in the rate of queries and updates? How can one comprehensively compare dictionary data structures? How can one bring the benefits of write-optimization to dictionaries on more complex data types? Write-optimized dictionaries have fundamentally changed the landscape of databases, and this research will improve our understanding of the complexity of operations on such systems.