A Space Efficient Direct Access Data Structure

In previous work we have suggested a data structure based on pruning a Huffman shaped Wavelet tree according to the underlying skeleton Huffman tree. This pruned Wavelet tree was especially designed to support faster random access and save memory storage, at the price of less effective rank and select operations, as compared to the original Huffman shaped Wavelet tree. In this paper we improve the pruning procedure and give empirical evidence that when memory storage is of main concern, our suggested data structure outperforms other direct access techniques such as those due to Külekci, DACs and sampling, with a slowdown as compared to DACs and fixed length encoding.