Extended Depth-First Representations of $k^2$-trees

Abstract

In this paper, we study static, computation-friendly, lossless compression formats for graphs, focusing on memory locality and operational efficiency of $k^2$-trees. We observe that their traditional level-wise layouts suffer from poor cache performance due to weak locality, especially in operations such as matrix-vector and matrix-matrix operations. To address this limitation, we propose four depth-first representations of $k^2$-trees: a plain depth-first layout (EDF-1), a balanced-parenthesis representation (BP), and their compressed variants (CEDF and CBP). We further introduce a linear-time compression method based on suffix and LCP arrays to identify and compress identical subtrees. We experimentally evaluate the execution time, the disk space, and the peak-memory usage of our approaches against classical level-wise $k^2$-trees and DFUDS-based representations across two real and one synthetic dataset (i.e., Web Graphs, Wikidata, and random adjacency matrices) over the above linear-algebra operations. Results show that our depth-first layouts are competitive and often superior than known approaches: CEDF achieves the best compression in most settings, EDF-1 and CEDF reduce the peak memory usage consistently, and performance varies by workload, with different layouts excelling in different operations and data regimes. Overall, this work demonstrates that depth-first layouts of $k^2$-trees provide a practical and efficient alternative to traditional layouts, improving both compression and computational performance in matrix operations.