Extended Depth-First Representations of -trees
arXiv:2607.28136
The paper proposes depth‑first memory layouts for k²‑trees, including plain and balanced‑parentheses variants and compressed versions, and shows they improve cache performance, compression, and memory usage for graph matrix operations.
Abstract
In this paper, we study static, computation-friendly, lossless compression formats for graphs, focusing on memory locality and operational efficiency of -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 -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 -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 -trees provide a practical and efficient alternative to traditional layouts, improving both compression and computational performance in matrix operations.
44 pages, 7 figures, 18 tables