A Practical Approach to Succinct Dictionary Data Structures

Abstract

As the theoretical work on succinct dictionary data structures continues to advance, it is important to provide practical implementations to find potential use cases for such structures in solving complex data management problems in the real-world. This paper aims to take a step towards bridging this gap by providing a practical implementation of a static, succinct dictionary data structure provided by Bender et al. in their paper ”On the Optimal Time/Space Tradeoff for Hash Tables”. Other contributions of this paper include clear and concise descriptions of the theoretical data structures and algorithms provided by Bender et al., explanations regarding important design choices made in implementing the data structure, and transparent discussions of how the observed space and time tradeoffs of a practical implementation of a succinct dictionary data structure differ from their theoretical counterparts. The paper concludes with an evaluation of the observed space usage and runtimes of operations associated with the data structure to explore how closely the empirical results align with theoretical expectations proposed by Bender et al.