Computer Science Department
School of Computer Science, Carnegie Mellon University
Compact Data Structures with Fast Queries
Daniel K. Blandford
This thesis describes compact representations of several types of data structures including variable-bit-length arrays and dictionaries, separable graphs, ordered sets, text indices, and meshes. All of the representations support fast queries; most support fast updates as well. Several structures come with strong theoretical results. All of the structures come with experimental results showing good compression results. The compressed data structures are usually close to as fast as their uncompressed counterparts, and sometimes are faster due to caching effects.