Extended Depth-First Representations of $k^2$-trees
Source: arXiv:2607.28136 · Published 2026-07-30 · By Gabriel Carmona, Paolo Ferragina, Giovanni Manzini, Francesco Tosoni
TL;DR
This paper addresses the challenge of improving memory locality and computational efficiency in lossless compression of sparse binary matrices using k2-trees. Traditional k2-trees lay out nodes level-by-level in breadth-first order, which leads to poor cache performance for matrix operations like multiplication due to scattered node data. The authors propose four new depth-first traversal-based layouts—two plain variants (EDF-1 and BP) and two compressed variants (CEDF and CBP)—which reorder the tree nodes so that subtrees are stored contiguously in memory. This enhances locality and enables subtree compression by detecting identical subtrees using suffix and LCP arrays. Experimental evaluation on real web graphs, Wikidata, and synthetic adjacency matrices shows these representations achieve better compression ratios, reduced peak memory usage, and improved or competitive execution times for matrix-vector and matrix-matrix operations compared to classical level-wise k2-trees and recent DFUDS-based layouts. Notably, CEDF often attains the best compression, while EDF-1 is fastest for matrix-vector multiplication. The paper extends prior work by detailed theoretical analysis and expanded experiments, consolidating depth-first k2-tree layouts as a practical alternative that balances compression and operational speed on large, sparse graphs.
Key findings
- CEDF (compressed enriched depth-first) achieves the best compression ratios in the majority of evaluated datasets and workloads.
- EDF-1 (plain depth-first) and CEDF consistently reduce peak memory usage compared to classical level-wise k2-trees.
- EDF-1 is generally the fastest among proposed layouts for matrix-vector multiplication tasks.
- DFUDS-based layout by Farina et al. excels in matrix-matrix addition but is not dominant in matrix-matrix multiplication.
- CBP (compressed balanced parenthesis) exploits repeated subtrees but is generally slower and requires more space than other proposed formats.
- Subtree detection and compression based on suffix and LCP arrays operates in linear time relative to k2-tree size.
- Storing skip sizes for subtrees larger than a threshold τ = Θ(√N) reduces navigation overhead with o(|P|) bit overhead.
- Performance benefits vary by matrix density and operation: classical level-wise layout favored on very sparse matrices, while depth-first layouts perform better on denser inputs.
Threat model
n/a — This work focuses on static data compression and efficient traversal of k2-trees without considering adversarial threats or attackers modifying the graphs.
Methodology — deep read
Threat Model & Assumptions: The adversary model is implicit—no active attacker is considered; focus is on static, lossless compression and efficient navigation of k2-trees representing sparse binary adjacency matrices. Assumptions include matrices of size power-of-k (k=2) with clustering properties enabling subtree repetition detection.
Data: The authors utilize three datasets: two real-world graph adjacency matrices representing Web Graphs and Wikidata and one synthetic dataset derived from random adjacency matrices. Matrix sizes and sparsity distributions vary, supporting experimental evaluation of compression and operational performance across different graph scenarios. Precise dataset sizes and splits are unspecified but include multiple scales.
Architecture / Algorithms: They design four novel k2-tree layouts:
- Plain Depth-First (EDF-1): Reorders nodes depth-first in a bit vector P containing concatenated k2-bit blocks of children.
- Enriched Depth-First (CEDF): Extends EDF-1 with auxiliary skip size vectors to enable subtree skipping during navigation, reducing traversal costs.
- Balanced Parenthesis (BP): Encodes internal nodes with parentheses and last-level leaves separately in vector L′. Supports subtree navigation via find-close queries on parentheses.
- Compressed Balanced Parenthesis (CBP): Further compresses BP by detecting repeated subtrees via suffix and longest common prefix (LCP) arrays, encoding identical subtree occurrences compactly.
They also describe integration and comparison with the DFUDS layout by Fariña et al. which uses a unary degree sequence with auxiliary bit flags.
Training Regime: Not applicable as this is an algorithmic/data-structural paper; implementations optimized for runtime and memory. Construction algorithms include linear-time subtree detection using suffix/LCP arrays. Parameter τ for skip size storage is set heuristically at τ = √N.
Evaluation Protocol: Evaluation metrics comprise disk space usage (bits), peak memory consumption during operations, and execution time for three operations: matrix-vector multiplication, matrix-matrix addition, and matrix-matrix multiplication. Baselines include classical level-wise k2-trees and the DFUDS-based k2-tree of Farina et al. Experiments run on multiple datasets with variation in sparsity and size, measuring performance trade-offs across data regimes.
Reproducibility: The paper does not explicitly state public code or dataset releases. Construction methods are detailed including suffix and LCP based compression. Algorithms rely on known data structures (rank/select, balanced parentheses) with references.
Technical innovations
- Four new depth-first k2-tree layouts (EDF-1, CEDF, BP, CBP) that improve memory locality by storing subtrees contiguously in bit vectors.
- A linear-time subtree compression method using suffix and LCP arrays to identify and compactly represent repeated subtrees.
- Enriched Depth-First representation (CEDF) enhances subtree traversal by storing skip sizes for large subtrees, enabling skipped traversal with minimal overhead.
- Balanced Parenthesis-based k2-tree encoding that separates internal node structure from leaf data to facilitate subtree compression while supporting efficient tree navigation.
Datasets
- Web Graphs — multiple scales — real web crawl datasets cited from [44, 45]
- Wikidata adjacency matrices — unspecified size — real knowledge graph data referenced via [23]
- Random adjacency matrices — synthetic — generated for baseline evaluation
Baselines vs proposed
- Classical level-wise k2-tree: peak memory usage higher than EDF-1 and CEDF; compression ratio worse than CEDF in most datasets.
- DFUDS-based layout (Farina et al.): fastest for matrix-matrix addition but slower than EDF-1 on matrix-vector multiplication; uses more disk space than CEDF.
- CBP: achieves subtree compression but generally slower and uses more space compared to CEDF and EDF-1.
- CEDF: consistently best or among best compression ratios, and lowest peak memory usage overall.
Limitations
- No adversarial evaluation or robustness against maliciously constructed graphs that might degrade subtree compression efficiency.
- Experiments only cover static graphs; dynamic updates or incremental constructions are not addressed.
- Evaluation limited to a few datasets; scalability to extremely large graphs (billions of nodes) is unclear.
- Random adjacency matrices may not fully represent real-world graph topology diversity.
- No reported public code or datasets, limiting ease of independent reproducibility.
- Accessing individual matrix entries in EDF-1 is less efficient due to depth-first traversal requirements.
Open questions / follow-ons
- How do depth-first k2-tree layouts perform on dynamic graphs with incremental updates?
- Can subtree compression techniques be extended or optimized for weighted or non-binary adjacency matrices?
- What is the impact of different threshold τ choices on compression and runtime, and can it be optimized adaptively?
- How do these layouts integrate into full graph database engines supporting complex query workloads?
Why it matters for bot defense
Although this paper is not focused on security or bot detection, the improvements in compressed graph representations and matrix operations have important implications for bot defense engineers working with large-scale knowledge graphs or adjacency matrices in backend systems. Enhanced compression and better cache locality of adjacency structures enable faster matrix-vector and matrix-matrix computations, which underpin algorithms for graph query acceleration, anomaly detection, or link prediction used in bot activity analysis. Efficient subtree compression also reduces peak memory usage, improving scalability of graph-based bot detection pipelines. However, practitioners must weigh the trade-offs: depth-first layouts may be more complex to implement and navigate individually, and performance gains vary by workload type and graph sparsity. Integrating these layouts into real-time bot detection systems requires empirical tuning and profiling on targeted graph datasets. Nonetheless, this work advances the state-of-the-art in succinct graph representations that enable computationally efficient analysis critical to scalable bot-defense infrastructure.
Cite
@article{arxiv2607_28136,
title={ Extended Depth-First Representations of $k^2$-trees },
author={ Gabriel Carmona and Paolo Ferragina and Giovanni Manzini and Francesco Tosoni },
journal={arXiv preprint arXiv:2607.28136},
year={ 2026 },
url={https://arxiv.org/abs/2607.28136}
}