.png){kind=icon}
.png){kind=icon}
Return
Depth First Representations of k2-trees
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-05228-5_4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The k(2)- tree is a compact data structure designed to efficiently store sparse binary matrices leveraging both sparsity and clustering of nonzero elements. This representation efficiently supports navigational operations and complex binary operations, such as matrix-matrix multiplication, while maintaining space efficiency. The standard k(2)- tree follows a level-by-level representation, which, while effective, prevents further compression of identical subtrees and it is not cache friendly when accessing individual subtrees. In this work, we introduce some novel depth-first representations of the k(2)-tree and propose an efficient lineartime algorithm to identify and compress identical subtrees within these structures. Our experimental results show that the use of a depth-first representation is a strategy worth pursuing: for the adjacency matrix of web graphs exploiting the presence of identical subtrees does improve both compression ratio and peak memory usage, and for some matrices, depth-first representations turn out to be faster than the standard k(2)-tree in computing the matrix-matrix multiplication.
Keywords:
Web graphs
Sparse binary matrices
Succinct tree representations
Compact data structure
Journal
S
IF:
0
Papers:
22
Citations:
0