A General Framework for Dynamic Succinct and Compressed Data Structures

Succinct data structures are becoming ever-more popular in practice due to their low memory consumption. However, a feature that is currently lacking from most implementations of succinct data structures is dynamism. In this paper, we design, implement, and test a general framework that allows for practical dynamic succinct structures. Firstly, a key component of our approach is careful memory management, which is often overlooked in the succinct data structures literature. Indeed, most succinct data structures allocate and deallocate relatively small data blocks each time a modify, insert, or delete operation occurs. We demonstrate experimentally that, even for relatively small numbers of operations, the space costs of memory fragmentation can be over 25% for dynamic data structures of this type. Secondly, using our memory management approach, we describe implementations of compressed modifiable bit vectors, and extended compressed random access memory (recently proposed by Jansson, Sadakane, and Sung [ICALP 2012]). Finally, we implement and test our data structures using a wide variety of compression algorithms and both synthetic (for the compressed modifiable bit vector) and real-world data (for the extended compressed random access memory). Our data structures provide an easy to use interface that allows standard algorithms (in our example, BFS) to be run on top of the compressed data, providing a tradeoff between memory consumption and running time.