next up previous
Next: An Algorithmic Framework for Up: DATA COMPRESSION Previous: Compressed Data Structures: Dictionaries

   
Compressed Dictionaries: Space Measures, Data Sets, and Experiments

A. Gupta, W.-K. Hon, R. Shah, and J. S. Vitter. ``Compressed Dictionaries: Space Measures, Data Sets, and Experiments,'' in Proceedings of the 5th International Workshop on Experimental Algorithms (WEA '06), Menorca, Spain, May 2006, 158-169.

Full text (Adobe pdf format)

We present an experimental study of the space-time tradeoffs for the dictionary problem. Our primary goal is to reduce the space requirement for storing a dictionary data structure. Many compression schemes have been developed for dictionaries, which fall generally in the categories of combinatorial encodings and data-aware methods and still support queries efficiently. We show that for many real-world datasets, data-aware methods lead to a worthwhile compression over combinatorial methods. Additionally, we design a new data-aware building block structure called BSGAP that presents improvements over other data-aware methods.



Jeff Vitter
2008-07-05