General-purpose compression scheme for databases

Abstract

A new variant of the semi-static SEQUITUR algorithm, RAY, that reduces main-memory use and allows random-access to databases is described. RAY models repetition in sequences by progressively constructing a hierarchical grammar with multiple passes through the data. Experimental results show that RAY has a practical main-memory requirements and achieves better compression than an efficient Huffman scheme and popular adaptive compression techniques. Further, the scheme allows random access to data and is not restricted to database of text.