EUVIMEDEUVIMED entdecken
Crossref

Two-Dimensional Block Trees

Nieves R Brisaboa, Travis Gagie, Adrián Gómez-Brandón, Gonzalo Navarro

The Computer Journal · 17.01.2024 · 67 (1) · 391-406

DOI: 10.1093/comjnl/bxac182 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Computer Journal, online erschienen am 21.12.2022. Verfasst von Nieves R Brisaboa und 3 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 25 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 $k^2$-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 $k^2$-tree, while being 30% faster to three times slower when accessing cells.

Zitieren

APA

Brisaboa, N. R., Gagie, T., Gómez-Brandón, A., & Navarro, G. (2024). Two-Dimensional Block Trees. The Computer Journal, 67(1), 391-406. https://doi.org/10.1093/comjnl/bxac182

Vancouver

Brisaboa NR, Gagie T, Gómez-Brandón A, Navarro G. Two-Dimensional Block Trees. The Computer Journal. 2024;67(1):391-406. doi:10.1093/comjnl/bxac182

BibTeX
@article{Brisaboa2024,
  author = {Brisaboa, Nieves R and Gagie, Travis and Gómez-Brandón, Adrián and Navarro, Gonzalo},
  title = {Two-Dimensional Block Trees},
  journal = {The Computer Journal},
  year = {2024},
  volume = {67},
  number = {1},
  pages = {391--406},
  doi = {10.1093/comjnl/bxac182}
}
Kostenlos starten →