Resumen:
Two-Dimensional Block Trees

Fecha

2019-09-02

Editor

Sistedes

Publicado en

Actas de las XXIV Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2019)

Licencia Creative Commons

Resumen

Brisaboa, N. R.; Gagie, T.; Gomez Brandon, A.; Navarro, G.: "Two-Dimensional Block Trees", en Proceedings of the 2018 Data Compression Conference (DCC 2018), IEEE Computer Society, Snowbird, Utah (Estados Unidos), 2018, pp. 227-236. GGS Class: 2 DOI: 10.1109/DCC.2018.00031 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.

Descripción

Acerca de Rodríguez Brisaboa, Nieves

Palabras clave

Compact Data Structures, Compression, Images, Web Graphs
Página completa del ítem
Notificar un error en este resumen
Mostrar cita
Mostrar cita en BibTeX
Descargar cita en BibTeX