Two-Dimensional Block Trees
![Thumbnail](/dspace/bitstream/handle/2183/37827/Brisaboa_Nieves_R_2024_Two_dimensional_block_trees.pdf.jpg?sequence=4&isAllowed=y)
Non accesible ata 2025-01-01
Use este enlace para citar
http://hdl.handle.net/2183/37827Coleccións
- GI-LBD - Artigos [51]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Two-Dimensional Block TreesData
2024-01Cita bibliográfica
Nieves R. Brisaboa, Travis Gagie, Adrián Gómez-Brandón, Gonzalo Navarro, Two-Dimensional Block Trees, The Computer Journal, Volume 67, Issue 1, January 2024, Pages 391–406, https://doi.org/10.1093/comjnl/bxac182
Resumo
[Absctract]: The Block Tree is a data structure for representing repetitive sequences in compressed space, which reaches space comparable with that of Lempel–Ziv compression while retaining fast direct access to any position in the sequence. In this paper, we generalize Block Trees to two dimensions, in order to exploit repetitive patterns in the representation of images, matrices and other kinds of bidimensional data. We demonstrate the practicality of the two-dimensional Block Trees (2D-BTs) in representing the adjacency matrices of Web graphs, and raster images in GIS applications. For this purpose, we integrate our 2D-BT with the k2-tree—an efficient structure that exploits clustering and sparseness to compress adjacency matrices—so that it also exploits repetitive patterns. Our experiments show that this structure uses 60–80% of the space of the original k2-tree, while being 30% faster to three times slower when accessing cells.
Palabras chave
Block Trees
k2-trees
Graph compression
Image compression
k2-trees
Graph compression
Image compression
Versión do editor
ISSN
0010-4620
1460-2067
1460-2067