Pith. sign in

REVIEW 3 major objections 6 minor 58 references

Depth-first layouts of k²-trees improve compression and matrix-operation performance over classical level-wise storage.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 16:44 UTC pith:L7XCWCPG

load-bearing objection Solid systems paper: depth-first k²-tree layouts plus SA/LCP subtree compression are a real practical alternative, with honest mixed results and usable code. the 3 major comments →

arxiv 2607.28136 v1 pith:L7XCWCPG submitted 2026-07-30 cs.DS cs.IRcs.PF

Extended Depth-First Representations of k²-trees

Gabriel Carmona , Paolo Ferragina , Giovanni Manzini , Francesco Tosoni This is my paper
classification cs.DS cs.IRcs.PF
keywords k2-treesdepth-first traversalsuccinct data structurestree compressioncache efficiencygraph compressionmatrix operations
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Classical k²-trees store nodes level by level, so nodes that belong to the same subtree sit far apart in memory and whole-matrix work (matrix-vector products, sums, multiplications) pays a heavy cache cost. This paper replaces that layout with four depth-first formats: an enriched plain depth-first bitstring (EDF-1), a balanced-parenthesis encoding (BP), and the two versions that further replace repeated subtrees by pointers (CEDF and CBP). Identical or interchangeable subtrees are found in linear time with suffix and LCP arrays. On Web-graph, Wikidata, and random binary matrices the new layouts are competitive or better: CEDF usually records the smallest disk footprint, EDF-1 and CEDF consistently cut peak memory, and runtime winners change with density and operation. The practical claim is that depth-first k²-trees are ready drop-in alternatives that improve both space and computational efficiency for static graph adjacency matrices.

Core claim

Depth-first representations of k²-trees—plain enriched (EDF-1), balanced parentheses (BP), and their subtree-compressed forms CEDF and CBP—together with a linear-time suffix/LCP method that detects and shares identical subtrees, form a practical alternative to classical level-wise k²-trees and DFUDS layouts. They improve disk compression in most tested settings, reduce peak memory on matrix operations, and often improve running time, with the best layout depending on matrix density and on whether the workload is matrix-vector multiplication, matrix-matrix sum, or matrix-matrix multiplication.

What carries the argument

Four depth-first k²-tree layouts (EDF-1 with skip values for large subtrees, BP with excess-block navigation, and the compressed CEDF/CBP variants). Subtrees stay contiguous, full traversals become sequential scans, and maximal identical or interchangeable subtrees are replaced by pointers discovered via suffix and LCP arrays.

Load-bearing premise

That the chosen matrices, the fixed skip threshold near the square root of the tree size, and the fixed excess/rank block sizes are representative enough for the observed locality and subtree-repetition gains to hold on other graphs and workloads.

What would settle it

Re-run the same three matrix operations on a held-out collection of large sparse graphs that contain few repeated submatrices or that force many random single-entry accesses; if CEDF no longer leads in bits per nonzero and EDF-1/CEDF no longer reduce peak memory, the practicality claim fails.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • CEDF is the default choice when the disk footprint of a static binary matrix is the binding constraint.
  • EDF-1 is typically fastest for matrix-vector multiplication because the work reduces to a left-to-right scan plus cheap all-1s shortcuts.
  • Depth-first layout lets matrix-matrix sum and multiply copy whole subtrees directly, cutting the peak-memory queues required by level-wise merging.
  • Subtree compression via suffix/LCP arrays is linear-time and pays off on large, moderately sparse real graphs that contain repeated submatrices.
  • No single k²-tree layout dominates; the best choice depends on density regime and on the concrete linear-algebra kernel.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same contiguous-subtree layout could lower energy use of graph kernels by cutting cache misses—an effect the paper only lists as future measurement.
  • Applying the same SA/LCP pruning to the DFUDS baseline could combine its constant-time child navigation with CEDF-style space savings.
  • If identical subtrees are memoized across multiplications, whole subproducts could be reused, turning structural repetition into arithmetic savings.
  • Graph stores that already expose a k²-tree API could swap the physical layout without changing query interfaces, gaining memory headroom on path queries and ranking kernels.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies static, computation-friendly lossless encodings of binary matrices via k²-trees, arguing that classical level-wise layouts have weak locality for full-tree operations (matrix–vector, matrix–matrix sum/product). It proposes four depth-first layouts—plain enriched DF (EDF-1), balanced parentheses (BP), and their subtree-compressed forms (CEDF, CBP)—plus a linear-time SA/LCP method to detect and replace interchangeable/identical subtrees. Space and traversal bounds are stated in Lemmas 1–7. Experiments on WebGraph, Wikidata-derived, and random matrices compare disk bits/nonzero, peak memory, and runtime against the canonical level-wise k²-tree and a concurrent DFUDS layout, reporting that CEDF often wins on disk, EDF-1/CEDF consistently reduce peak memory, and runtime winners vary by operation and density.

Significance. This is a solid experimental-algorithms contribution that extends a conference version with fuller theory, more operations, and improved BP implementations. The central claim is comparative and empirical rather than a dominance theorem; the paper is appropriately honest that DFUDS or the classical layout win in some sparse regimes. Strengths include public baselines and datasets, released code, an explicit m_τ sensitivity grid, SUB vs SUB+DYN variants, and coherent space/time lemmas matching the constructions. If the results hold under the stated regimes (k=2, the chosen skip/excess/rank parameters), depth-first k²-tree layouts are a practical alternative for compressed graph linear algebra, especially when peak memory and disk footprint matter.

major comments (3)
  1. [§3, Lemma 1] Lemma 1 (end of §3) is misstated: the surrounding text summarises the canonical level-wise representation, but the lemma body claims the “Enriched Depth-First format” and constant-time subtree traversal. Canonical navigation is via rank on T (constant time, t+ℓ+o(t+ℓ) bits); EDF traversal is O(τ) (Lemma 2). As written, Lemma 1 both misnames the structure and attributes the wrong time bound. Please correct the lemma statement to match §3 (and check cross-references).
  2. [§5.2, Lemma 7] Lemma 7 (§5.2) states that the compressed plain/enriched DF structure is “represented using balanced parentheses” and gives a t_c+4p+ℓ_c+o(·) bound. The construction in §5.2 is the 0000-marker + R_c pointer scheme on the DF bitstring P/P′, not BP. The bound itself is plausible for CEDF, but the wording is a copy-paste error from the BP lemmas and should be fixed so the theoretical summary is self-consistent.
  3. [§6.7, Tables 15–17] Tables 15–17 are labelled and introduced as “Matrix-matrix sum” while the columns are M1×M2 products and the surrounding §6.7 text is matrix–matrix multiplication (times in minutes, consistent with mult). This is load-bearing for interpreting the Database mult results; retitle/recaption so sum vs mult cannot be confused.
minor comments (6)
  1. [Abstract, §1] Abstract and §1 say “often superior than”; prefer “superior to”.
  2. [§4.2] §4.2 sets τ=√N and writes “k=4” when discussing overhead, while the paper assumes k=2 elsewhere; clarify that k²=4 (children) is intended, not radix k=4.
  3. [Figure 1] Figure 1 / colour-coded levels are hard to parse in greyscale print; consider patterns or explicit level labels in the bitstrings.
  4. [§6.3] §6.3: K2-BP/K2-CBP are dropped on Database as “non-competitive”; a one-line quantitative note (e.g., bits/nz or a failed build) would make the exclusion easier to audit.
  5. [§6.6–6.7] Several table headers use “Matrix-matrix sum” wording inside the mult subsection even outside Tables 15–17; sweep captions for consistency with §6.5–6.7.
  6. [§7] Future-work bullet on energy/cache (§7) is welcome; if any hardware counter (cache misses) was collected even on a subset, a brief remark would strengthen the locality narrative.

Circularity Check

0 steps flagged

No significant circularity: empirical data-structure paper with self-contained space lemmas and external benchmarks.

full rationale

The paper defines four depth-first k²-tree layouts (EDF-1, BP, CEDF, CBP), proves standard space/traversal bounds (Lemmas 1–4, 6–7) directly from those definitions, and evaluates them experimentally against the classical level-wise k²-tree and a concurrent DFUDS baseline on public WebGraph, Wikidata, and synthetic matrices. Compression and runtime claims are measured outcomes, not algebraic restatements of fitted parameters. The linear-time subtree-compression algorithm via SA/LCP is a standard string technique applied to the new layouts; it does not presuppose the experimental wins. Self-citation to the conference version [42] is ordinary incremental publication and is not load-bearing for any uniqueness or forced-choice argument. No step reduces a claimed prediction or first-principles result to its own inputs by construction.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 2 invented entities

The work rests on standard succinct-tree and string-algorithm primitives, the classical k²-tree definition, and several implementation thresholds chosen for the experiments. No new physical entities; the 'invented' pieces are engineering data-structure variants.

free parameters (4)
  • m_τ skip-threshold multipliers = 0.5…0.01 × √N
    Grid {0.5, 0.2, 0.1, 0.05, 0.02, 0.01} times √N controls which subtrees store skip values; results and space/time tradeoffs depend on this hand-chosen grid (§4.2, §6.3).
  • excess block size e and rank block size b = e=256, b=4096
    e=256 for excess arrays in BP/CBP; b=4096 for rank(()()) and related structures; fixed without systematic sensitivity study (§4.3.2, §6.3).
  • LCP ignore threshold for small subtrees = 32
    Interchangeable subtrees with LCP≤32 (or similar) are ignored as not worth pointer replacement (§5.1).
  • DFUDS parameter b=1024 = 1024
    Taken from the baseline paper for fair comparison (§6.3).
axioms (5)
  • domain assumption k²-tree model with k constant (experiments fix k=2) and n padded to a power of k so height is ⌈log_k n⌉
    Standard k²-tree construction (§3); padding assumed not to change asymptotics.
  • standard math rank/select and findclose on bitvectors/parentheses supported in O(1) with o(n) extra bits
    Invoked throughout §§2–5 via classical succinct DS results [20,52,53].
  • standard math Suffix array and LCP of a string of length N computable in O(N) time
    Used for linear-time identical-subtree detection (§5; cites [48–51]).
  • ad hoc to paper Interchangeable BP subtrees (Def. 1) may ignore last-level leaf bits stored in L′
    Defines what CBP is allowed to collapse; correctness of navigation then needs extra leaf-count/pointer arrays (§5.1).
  • domain assumption Operations of interest are full or near-full tree traversals (matvec, matsum, matmul), so O(τ) subtree skip is acceptable
    Stated motivation in §1 and §4.3.2; random single-cell access is deprioritized.
invented entities (2)
  • EDF-1 / CEDF enriched depth-first k²-tree layouts independent evidence
    purpose: Contiguous DF bit layout with optional skip values and 0000-pointer subtree compression
    Engineering encodings of an existing tree, not new ontological objects; independent evidence is the shipped implementations and experiments.
  • BP / CBP balanced-parenthesis k²-tree layouts with last-level L′ and (()()) pruned markers independent evidence
    purpose: DF parenthesis encoding optimized for k²-trees plus interchangeable-subtree compression
    Specializations of classical BP trees to k² structure; validated experimentally on some datasets, dropped on Database as non-competitive.

pith-pipeline@v1.2.0-daily-grok45 · 44602 in / 3593 out tokens · 69599 ms · 2026-07-31T16:44:09.856747+00:00 · methodology

0 comments
read the original 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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

58 extracted references · 16 canonical work pages

  1. [1]

    Sakr, S., Bonifati, A., Voigt, H., Iosup, A., Ammar, K., Angles, R., Aref, W., Arenas, M., Besta, M., Boncz, P.A., Daudjee, K., Valle, E.D., Dumbrava, S., Hartig, O., Haslhofer, B., Hegeman, T., Hidders, J., Hose, K., Iamnitchi, A., Kalavri, V., Kapp, H., Martens, W., ¨Ozsu, M.T., Peukert, E., Plantikow, S., Ragab, M., Ripeanu, M.R., Salihoglu, S., Schulz...

    2021

  2. [2]

    Communications of the ACM62 (8), 36–43 (2019)

    Noy, N., Gao, Y., Jain, A., Narayanan, A., Patterson, A., Taylor, J.: Industry- scale knowledge graphs: Lessons and challenges. Communications of the ACM62 (8), 36–43 (2019)

    2019

  3. [3]

    In: Proceedings of the 24th ACM SIGKDD International Conference on Knowl- edge Discovery & Data Mining

    Dong, X.L.: Challenges and innovations in building a product knowledge graph. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowl- edge Discovery & Data Mining. KDD ’18, p. 2869. Association for Comput- ing Machinery, New York, NY, USA (2018). https://doi.org/10.1145/3219819. 3219938 .https://doi.org/10.1145/3219819.3219938

    arXiv 2018

  4. [4]

    In: Proceedings of the 10th International 38 Conference on Knowledge Capture

    Jaradeh, M.Y., Oelen, A., Farfar, K.E., Prinz, M., D’Souza, J., Kismih´ ok, G., Stocker, M., Auer, S.: Open research knowledge graph: Next generation infrastruc- ture for semantic scholarly knowledge. In: Proceedings of the 10th International 38 Conference on Knowledge Capture. K-CAP ’19, pp. 243–246. Association for Computing Machinery, New York, NY, USA...

    arXiv 2019

  5. [5]

    Ley, M.: Dblp: some lessons learned. Proc. VLDB Endow.2(2), 1493–1500 (2009) https://doi.org/10.14778/1687553.1687577

    arXiv 2009

  6. [6]

    ACM Comput

    Scharpf, P., Breitinger, C., Spitz, A., Meuschke, N., Greiner-Petter, A., Schubotz, M., Gipp, B.: Entity linking with wikidata: A systematic literature review. ACM Comput. Surv.58(9) (2026) https://doi.org/10.1145/3795134

    doi:10.1145/3795134 2026

  7. [7]

    In: Companion Proceedings of the ACM Web Conference 2023

    Vrandeˇ ci´ c, D., Pintscher, L., Kr¨ otzsch, M.: Wikidata: The making of. In: Companion Proceedings of the ACM Web Conference 2023. WWW ’23 Companion, pp. 615–624. Association for Computing Machinery, New York, NY, USA (2023). https://doi.org/10.1145/3543873.3585579 . https://doi.org/10.1145/3543873.3585579

    arXiv 2023

  8. [8]

    https://enterprise.wikimedia.com/blog/ wikidata-api-endpoints-wikimedia-enterprise/

    Wikimedia Enterprise Team: Wikidata API Endpoints Now Avail- able in Wikimedia Enterprise. https://enterprise.wikimedia.com/blog/ wikidata-api-endpoints-wikimedia-enterprise/. Accessed: April 15, 2026 (2026)

    2026

  9. [9]

    Dagstuhl Reports12(9), 60–120 (2023) https://doi.org/10.4230/DagRep.12.9.60

    Groth, P., Simperl, E., Erp, M., Vrandeˇ ci´ c, D.: Knowledge Graphs and their Role in the Knowledge Engineering of the 21st Century (Dagstuhl Seminar 22372). Dagstuhl Reports12(9), 60–120 (2023) https://doi.org/10.4230/DagRep.12.9.60

    work page doi:10.4230/dagrep.12.9.60 2023

  10. [10]

    ACM Comput

    Angles, R., Gutierrez, C.: Survey of graph database models. ACM Comput. Surv. 40(1), 1–1139 (2008) https://doi.org/10.1145/1322432.1322433

    arXiv 2008

  11. [11]

    ACM Comput

    Liang, W., Meo, P.D., Tang, Y., Zhu, J.: A survey of multi-modal knowledge graphs: Technologies and trends. ACM Comput. Surv.56(11), 273–127341 (2024) https://doi.org/10.1145/3656579

    work page doi:10.1145/3656579 2024

  12. [12]

    In: Proceedings of the 2022 International Conference on Management of Data

    Deutsch, A., Francis, N., Green, A., Hare, K., Li, B., Libkin, L., Lindaaker, T., Marsault, V., Martens, W., Michels, J., Murlak, F., Plantikow, S., Selmer, P., Rest, O., Voigt, H., Vrgoˇ c, D., Wu, M., Zemke, F.: Graph pattern match- ing in gql and sql/pgq. In: Proceedings of the 2022 International Conference on Management of Data. SIGMOD ’22, pp. 2246–2...

    arXiv 2022

  13. [13]

    ACM Trans

    Peng, B., Zhu, Y., Liu, Y., Bo, X., Shi, H., Hong, C., Zhang, Y., Tang, S.: Graph retrieval-augmented generation: A survey. ACM Trans. Inf. Syst.44(2) (2025) https://doi.org/10.1145/3777378

    doi:10.1145/3777378 2025

  14. [14]

    In: Pro- ceedings of the 13th International Conference on World Wide Web

    Boldi, P., Vigna, S.: The webgraph framework i: compression techniques. In: Pro- ceedings of the 13th International Conference on World Wide Web. WWW ’04, pp. 595–602. Association for Computing Machinery, New York, NY, USA (2004). 39 https://doi.org/10.1145/988672.988752 .https://doi.org/10.1145/988672.988752

    arXiv 2004

  15. [15]

    In: Chua, T., Ngo, C., Lee, R.K., Kumar, R., Lauw, H.W

    Fontana, T., Vigna, S., Zacchiroli, S.: Webgraph: The next generation (is in rust). In: Chua, T., Ngo, C., Lee, R.K., Kumar, R., Lauw, H.W. (eds.) Companion Proceedings of the ACM on Web Conference 2024, WWW 2024, Singapore, Singa- pore, May 13-17, 2024, pp. 686–689. ACM, ??? (2024). https://doi.org/10.1145/ 3589335.3651581 .https://doi.org/10.1145/358933...

    arXiv 2024

  16. [16]

    IEEE Access8, 219233–219243 (2020) https://doi.org/ 10.1109/ACCESS.2020.3040673

    Versari, L., Comsa, I.-M., Conte, A., Grossi, R.: Zuckerli: A new compressed representation for graphs. IEEE Access8, 219233–219243 (2020) https://doi.org/ 10.1109/ACCESS.2020.3040673

    arXiv 2020

  17. [17]

    Ferragina, P., Manzini, G., Gagie, T., K¨ oppl, D., Navarro, G., Striani, M., Tosoni, F.: Improving matrix-vector multiplication via lossless grammar-compressed matrices. Proc. VLDB Endow.15(10), 2175–2187 (2022) https://doi.org/10. 14778/3547305.3547321

    arXiv 2022

  18. [18]

    Information Systems39(1), 152–174 (2014)

    Brisaboa, N., Ladra, S., Navarro, G.: Compact representation of web graphs with extended functionality. Information Systems39(1), 152–174 (2014)

    2014

  19. [19]

    In: Proceedings of the 16th International Symposium on String Processing and Information Retrieval

    Brisaboa, N.R., Ladra, S., Navarro, G.: k2-trees for compact web graph represen- tation. In: Proceedings of the 16th International Symposium on String Processing and Information Retrieval. SPIRE ’09, pp. 18–30. Springer, Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03784-9 3

    work page doi:10.1007/978-3-642-03784-9 2009

  20. [20]

    Navarro, G.: Compact Data Structures, p. 570. Cambridge University Press, 40 W. 20th St., New York, NY, USA (2016). https://doi.org/10.1017/ CBO9781316588284 .https://doi.org/10.1017/CBO9781316588284

    doi:10.1017/cbo9781316588284 2016

  21. [21]

    IEEE Access 13, 56756–56779 (2025) https://doi.org/10.1109/ACCESS.2025.3555119

    Tosoni, F., Bille, P., Brunacci, V., Angelis, A.d., Ferragina, P., Manzini, G.: Toward greener matrix operations by lossless compressed formats. IEEE Access 13, 56756–56779 (2025) https://doi.org/10.1109/ACCESS.2025.3555119

    arXiv 2025

  22. [22]

    SN Computer Science3(3), 193 (2022) https: //doi.org/10.1007/s42979-022-01084-2

    Francisco, A.P., Gagie, T., K¨ oppl, D., Ladra, S., Navarro, G.: Graph compression for adjacency-matrix multiplication. SN Computer Science3(3), 193 (2022) https: //doi.org/10.1007/s42979-022-01084-2

    work page doi:10.1007/s42979-022-01084-2 2022

  23. [23]

    The VLDB Journal34(1) (2024) https://doi

    Arroyuelo, D., G´ omez-Brand´ on, A., Navarro, G.: Evaluating regular path queries on compressed adjacency matrices. The VLDB Journal34(1) (2024) https://doi. org/10.1007/s00778-024-00885-6

    work page doi:10.1007/s00778-024-00885-6 2024

  24. [24]

    Elgohary, A., Boehm, M., Haas, P.J., Reiss, F.R., Reinwald, B.: Compressed linear algebra for large-scale machine learning. Proc. VLDB Endow.9(12), 960–971 (2016) https://doi.org/10.14778/2994509.2994515

    arXiv 2016

  25. [25]

    Elgohary, A., Boehm, M., Haas, P.J., Reiss, F.R., Reinwald, B.: Compressed linear algebra for declarative large-scale machine learning. Commun. ACM62(5), 83–91 40 (2019) https://doi.org/10.1145/3318221

    work page doi:10.1145/3318221 2019

  26. [26]

    In: Proceedings of the 34th Interna- tional Conference on Neural Information Processing Systems

    Abboud, A., Backurs, A., Bringmann, K., K¨ unnemann, M.: Impossibility results for grammar-compressed linear algebra. In: Proceedings of the 34th Interna- tional Conference on Neural Information Processing Systems. NIPS ’20. Curran Associates Inc., Red Hook, NY, USA (2020)

    2020

  27. [27]

    In: 2025 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp

    Alves, J.N.F., Moustafa, S., Benkner, S., Francisco, A.P., Gansterer, W.N., Russo, L.M.S.: Accelerating graph neural networks using a novel computation-friendly matrix compression format. In: 2025 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1091–1103 (2025). https://doi.org/10.1109/ IPDPS64566.2025.00100

    arXiv 2025

  28. [28]

    Baunsgaard, S., Boehm, M.: Aware: Workload-aware, redundancy-exploiting lin- ear algebra. Proc. ACM Manag. Data1(1) (2023) https://doi.org/10.1145/ 3588682

    2023

  29. [29]

    In: Proceedings of the 20th IEEE/ACM International Symposium on Code Generation and Optimization

    Donenfeld, D., Chou, S., Amarasinghe, S.: Unified compilation for lossless compression and sparse computing. In: Proceedings of the 20th IEEE/ACM International Symposium on Code Generation and Optimization. CGO ’22, pp. 205–216. IEEE Press, ??? (2022). https://doi.org/10.1109/CGO53902.2022. 9741282 .https://doi.org/10.1109/CGO53902.2022.9741282

    arXiv 2022

  30. [30]

    IEEE Access11, 106103–106125 (2023) https://doi.org/10.1109/ACCESS.2023.3317293

    Marin` o, G.C., Furia, F., Malchiodi, D., Frasca, M.: Efficient and compact rep- resentations of deep neural networks via entropy coding. IEEE Access11, 106103–106125 (2023) https://doi.org/10.1109/ACCESS.2023.3317293

    arXiv 2023

  31. [31]

    In: Bilgin, A., Marcellin, M.W., Serra- Sagrist` a, J., Storer, J.A

    Brisaboa, N.R., Bernardo, G., Guti´ errez, G., Ladra, S., Penabad, M.R., Troncoso, B.A.: Efficient set operations over k2-trees. In: Bilgin, A., Marcellin, M.W., Serra- Sagrist` a, J., Storer, J.A. (eds.) 2015 Data Compression Conference, DCC 2015, Snowbird, UT, USA, April 7-9, 2015, pp. 373–382. IEEE, ??? (2015). https://doi. org/10.1109/DCC.2015.9

    work page doi:10.1109/dcc.2015.9 2015

  32. [32]

    In: 2014 Data Compression Conference, pp

    Garc ´ ıa, S.A., Brisaboa, N.R., Bernardo, G.d., Navarro, G.: Interleaved k2- tree: Indexing and navigating ternary relations. In: 2014 Data Compression Conference, pp. 342–351 (2014). https://doi.org/10.1109/DCC.2014.56

    work page doi:10.1109/dcc.2014.56 2014

  33. [33]

    In: Proceedings of the 2018 International Conference on Management of Data

    Francis, N., Green, A., Guagliardo, P., Libkin, L., Lindaaker, T., Marsault, V., Plantikow, S., Rydberg, M., Selmer, P., Taylor, A.: Cypher: An evolving query lan- guage for property graphs. In: Proceedings of the 2018 International Conference on Management of Data. SIGMOD ’18, pp. 1433–1445. Association for Comput- ing Machinery, New York, NY, USA (2018)...

    arXiv 2018

  34. [34]

    In: Proceedings of the Fourth International Workshop on Graph Data 41 Management Experiences and Systems

    Rest, O., Hong, S., Kim, J., Meng, X., Chafi, H.: Pgql: a property graph query language. In: Proceedings of the Fourth International Workshop on Graph Data 41 Management Experiences and Systems. GRADES ’16. Association for Comput- ing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2960414. 2960421 .https://doi.org/10.1145/2960414.2960421

    arXiv 2016

  35. [35]

    In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

    Deutsch, A., Xu, Y., Wu, M., Lee, V.E.: Aggregation support for modern graph analytics in tigergraph. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. SIGMOD ’20, pp. 377–392. Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/ 3318464.3386144 .https://doi.org/10.1145/3318464.3386144

    arXiv 2020

  36. [36]

    ACM Comput

    Angles, R., Arenas, M., Barcel´ o, P., Hogan, A., Reutter, J., Vrgoˇ c, D.: Founda- tions of modern query languages for graph databases. ACM Comput. Surv.50(5) (2017) https://doi.org/10.1145/3104031

    doi:10.1145/3104031 2017

  37. [37]

    In: The World Wide Web Conference

    Bonifati, A., Martens, W., Timm, T.: Navigating the maze of wikidata query logs. In: The World Wide Web Conference. WWW ’19, pp. 127–138. Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/ 3308558.3313472 .https://doi.org/10.1145/3308558.3313472

    arXiv 2019

  38. [38]

    In: The Semantic Web – ISWC 2018: 17th International Semantic Web Conference, Monterey, CA, USA, October 8–12, 2018, Proceedings, Part II, pp

    Malyshev, S., Kr¨ otzsch, M., Gonz´ alez, L., Gonsior, J., Bielefeldt, A.: Getting the most out of wikidata: Semantic technology usage in wikipedia’s knowl- edge graph. In: The Semantic Web – ISWC 2018: 17th International Semantic Web Conference, Monterey, CA, USA, October 8–12, 2018, Proceedings, Part II, pp. 376–394. Springer, Berlin, Heidelberg (2018)....

    work page doi:10.1007/978-3-030-00668-6 2018

  39. [39]

    ACM Trans

    Claude, F., Navarro, G.: Fast and compact web graph representations. ACM Trans. Web4(4) (2010) https://doi.org/10.1145/1841909.1841913

    arXiv 2010

  40. [40]

    Journal of Computer and System Sciences131, 86–104 (2023) https: //doi.org/10.1016/j.jcss.2022.09.001

    de Bernardo, G., Gagie, T., Ladra, S., Navarro, G., Seco, D.: Faster compressed quadtrees. Journal of Computer and System Sciences131, 86–104 (2023) https: //doi.org/10.1016/j.jcss.2022.09.001

    work page doi:10.1016/j.jcss.2022.09.001 2023

  41. [41]

    Information Systems72, 179–204 (2017) https: //doi.org/10.1016/j.is.2017.10.007

    Ladra, S., Param´ a, J.R., Silva-Coira, F.: Scalable and queryable compressed stor- age structure for raster data. Information Systems72, 179–204 (2017) https: //doi.org/10.1016/j.is.2017.10.007

    work page doi:10.1016/j.is.2017.10.007 2017

  42. [42]

    In: Badkobeh, G., Radoszewski, J., Tonellotto, N., Baeza-Yates, R

    Carmona, G., Manzini, G.: Depth first representations ofk 2-trees. In: Badkobeh, G., Radoszewski, J., Tonellotto, N., Baeza-Yates, R. (eds.) String Processing and Information Retrieval, pp. 28–44. Springer, Cham

  43. [43]

    In: Badkobeh, G., Radoszewski, J., Tonellotto, N., Baeza-Yates, R

    Fari˜ na, A., G´ omez-Brand´ on, A., G´ omez-Colomer, A., Navarro, G.: Cache- friendly compressed boolean matrices. In: Badkobeh, G., Radoszewski, J., Tonellotto, N., Baeza-Yates, R. (eds.) String Processing and Information Retrieval - 32nd International Symposium, SPIRE 2025, London, UK, September 8-11, 2025, Proceedings. Lecture Notes in Computer Scienc...

    doi:10.1007/978-3-032-05228-5 2025

  44. [44]

    In: Proc

    Boldi, P., Vigna, S.: The WebGraph framework I: Compression techniques. In: Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), pp. 595–601. ACM Press, Manhattan, USA (2004)

    2004

  45. [45]

    In: Proceedings of the 20th International Conference on World Wide Web

    Boldi, P., Rosa, M., Santini, M., Vigna, S.: Layered label propagation: A multires- olution coordinate-free ordering for compressing social networks. In: Proceedings of the 20th International Conference on World Wide Web. ACM Press, ??? (2011)

    2011

  46. [46]

    In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms

    Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’90, pp. 319–327. Society for Industrial and Applied Mathematics, USA (1990). https://doi.org/10.5555/320176.320218 . https://doi.org/10.5555/320176.320218

    arXiv 1990

  47. [47]

    Cambridge University Press, Cambridge (2023)

    Ferragina, P.: Pearls of Algorithm Design: A Practical Guide to Compact Data Structures. Cambridge University Press, Cambridge (2023). https://doi.org/10. 1017/9781009128933 .https://doi.org/10.1017/9781009128933

    work page doi:10.1017/9781009128933 2023

  48. [48]

    K¨ arkk¨ ainen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM53(6), 918–936 (2006) https://doi.org/10.1145/1217856.1217858

    arXiv 2006

  49. [49]

    In: Kucherov, G., Ukkonen, E

    K¨ arkk¨ ainen, J., Manzini, G., Puglisi, S.J.: Permuted longest-common-prefix array. In: Kucherov, G., Ukkonen, E. (eds.) Combinatorial Pattern Match- ing, pp. 181–192. Springer, Berlin, Heidelberg (2009). https://doi.org/10.1007/ 978-3-642-02441-2 17

    2009

  50. [51]

    In: Proceedings of the 14th Annual Conference on Combinatorial Pat- tern Matching

    Kim, D.K., Sim, J.S., Park, H., Park, K.: Linear-time construction of suffix arrays. In: Proceedings of the 14th Annual Conference on Combinatorial Pat- tern Matching. CPM’03, pp. 186–199. Springer, Berlin, Heidelberg (2003). https: //doi.org/10.5555/1756553.1756567 .https://doi.org/10.5555/1756553.1756567

    arXiv 2003

  51. [52]

    In: Chandru, V., Vinay, V

    Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) Foundations of Soft- ware Technology and Theoretical Computer Science, pp. 37–42. Springer, Berlin, Heidelberg (1996). https://doi.org/10.1007/3-540-62034-6 35

    work page doi:10.1007/3-540-62034-6 1996

  52. [53]

    SIAM Journal on Computing31(3), 762–776 (2002) https://doi.org/ 10.1137/S0097539799364092

    Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM Journal on Computing31(3), 762–776 (2002) https://doi.org/ 10.1137/S0097539799364092

    work page doi:10.1137/s0097539799364092 2002

  53. [54]

    The 43 Morgan Kaufmann Series in Computer Graphics and Geometric Modeling

    Samet, H.: Foundations of Multidimensional and Metric Data Structures. The 43 Morgan Kaufmann Series in Computer Graphics and Geometric Modeling. Mor- gan Kaufmann Publishers Inc., San Francisco (2005). https://doi.org/10.5555/ 1076819 .https://doi.org/10.5555/1076819

    work page doi:10.5555/1076819 2005

  54. [55]

    Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Computing31, 762–776 (2001)

    2001

  55. [56]

    ACM Transactions on Algorithms (TALG)10(3), 1–39 (2014)

    Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Transactions on Algorithms (TALG)10(3), 1–39 (2014)

    2014

  56. [57]

    Theoretical Computer Science368(3), 231–246 (2006) https://doi.org/10.1016/j.tcs.2006.09.014

    Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal represen- tation for balanced parentheses. Theoretical Computer Science368(3), 231–246 (2006) https://doi.org/10.1016/j.tcs.2006.09.014 . Combinatorial Pattern Match- ing

    work page doi:10.1016/j.tcs.2006.09.014 2006

  57. [58]

    Brisaboa, N.R., Gagie, T., G´ omez-Brand´ on, A., Navarro, G.: Two-dimensional block trees. Comput. J.67(1), 391–406 (2024) https://doi.org/10.1093/ COMJNL/BXAC182

    2024

  58. [59]

    In: SODA, vol

    Jansson, J., Sadakane, K., Sung, W.-K.: Ultra-succinct representation of ordered trees. In: SODA, vol. 7, pp. 575–584 (2007) 44

    2007