Two-Dimensional Block Trees

被引：4

作者：

Brisaboa, Nieves R. ^{[1
]}

Gagie, Travis ^{[2
]}

Gomez-Brandon, Adrian ^{[3
]}

Navarro, Gonzalo ^{[4
]}

机构：

[1] Univ A Coruna, Fac Informat, CITIC, La Coruna 15071, Spain

[2] Dalhousie Univ, Fac Comp Sci, CeBiB, Halifax, NS, Canada

[3] Univ A Coruna, Fac Informat, CITIC, CeBiB, La Coruna 15071, Spain

[4] Univ Chile, Dept Comp Sci, CeBiB, Beauchef 851, Santiago, Chile

来源：

COMPUTER JOURNAL | 2024年 / 67卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Block Trees; k (2)-trees; graph compression; image compression; COMPRESSION; REPRESENTATIONS; WEB;

D O I：

10.1093/comjnl/bxac182

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：391 / 406

页数：16

共 25 条

[1] Lossless compression of large binary images in digital spatial libraries
Ageenko, E
Fränti, P
[J]. COMPUTERS & GRAPHICS-UK, 2000, 24 (01): : 91 - 98
[2] Quasi-distinct parsing and optimal compression methods
Amir, Amihood
Aumann, Yonatan
Levy, Avivit
Roshko, Yuri
[J]. THEORETICAL COMPUTER SCIENCE, 2012, 422 : 1 - 14
[3] Graph Compression by BFS
Apostolico, Alberto
Drovandi, Guido
[J]. ALGORITHMS, 2009, 2 (03) : 1031 - 1044
[4] TECHNIQUE FOR EXTENDING RAPID EXACT-MATCH STRING MATCHING TO ARRAYS OF MORE THAN ONE DIMENSION
BAKER, TP
[J]. SIAM JOURNAL ON COMPUTING, 1978, 7 (04) : 533 - 541
[5] Block trees
Belazzougui, Djamal
Caceres, Manuel
Gagie, Travis
Gawrychowski, Pawel
Kaerkkaeinen, Juha
Navarro, Gonzalo
Ordonez, Alberto
Puglisi, Simon J.
Tabei, Yasuo
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2021, 117 : 1 - 22
[6] Bille Philip, 2015, Language and Automata Theory and Applications. 9th International Conference, LATA 2015. Proceedings: LNCS 8977, P577, DOI 10.1007/978-3-319-15579-1_45
[7] Bird R. S., 1977, Information Processing Letters, V6, P168, DOI 10.1016/0020-0190(77)90017-5
[8] Boldi P., 2011, World Wide Web (WWW), P587, DOI [10.1145/1963405.1963488, DOI 10.1145/1963405.1963488]
[9] Boldi Paolo, 2004, P 13 INT C WORLD WID, P595, DOI DOI 10.1145/988672.988752
[10] Extending general compact querieable representations to GIS applications
Brisaboa, Nieves R.
Cerdeira-Pena, Ana
de Bernardo, Guillermo
Navarro, Gonzalo
Pedreira, Oscar
[J]. INFORMATION SCIENCES, 2020, 506 (506) : 196 - 216

← 1 2 3 →