Two-Dimensional Block Trees
Nieves Brisaboa, Travis Gagie, Adrián Gómez-Brandón
and Gonzalo Navarro
The Block Tree (BT) is a novel compact data structure designed to compress
sequence collections. It obtains compression ratios close to Lempel-Ziv and
supports efficient direct access to any substring. The BT divides the text
recursively into fixed-size blocks and those appearing earlier are represented
with pointers. On repetitive collections, a few blocks can represent all the
others, and thus the BT reduces the size by orders of magnitude. In this paper
we extend the BT to two dimensions, to exploit repetitiveness in collections
of images, graphs, and maps. This two-dimensional Block Tree divides the image
regularly into subimages and replaces some of them by pointers to other
occurrences thereof.
We develop a specific variant aimed at compressing the adjacency matrices of
Web graphs, obtaining space reductions of up to 50% compared with the
k2-tree, which is the best alternative supporting direct and reverse
navigation in the graph.