Pith. sign in

REVIEW 3 major objections 6 minor 58 references

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

T0 review · 3 major / 6 minor · reviewed 2026-07-31 · grok-4.5

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

Pith's one-line read Depth-first layouts of k²-trees improve compression and matrix-operation performance over classical level-wise storage.

desk verdict 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. read the letter →

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

Gabriel Carmona , Paolo Ferragina , Giovanni Manzini , Francesco Tosoni This is my paper · ORCID
classification cs.DScs.IRcs.PF
keywords k2-treesdepth-firsttraversalsuccinctdatastructurestreecompressioncacheefficiencygraphmatrixoperations
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

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.

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

Extended reading notes

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.

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.

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, 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 · score 0.0 of 10

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.

Assumptions & free parameters 4 free parameters · 5 assumptions · 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).
assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Extended Depth-First Representations of $k^2$-trees." pith.science (2026). https://pith.science/paper/L7XCWCPG

@misc{pith2026260728136,
  author       = {Pith},
  title        = {Pith review of: Extended Depth-First Representations of $k^2$-trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L7XCWCPG}},
  note         = {Machine review of arXiv:2607.28136}
}
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). Continue with ORCID to comment.

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

Show all 58 references
  1. [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

    2023 doi

  2. [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

    2008

  3. [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

    2024 doi

  4. [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...

    2022

  5. [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

    2025 doi

  6. [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 .http...

    2004

  7. [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

  8. [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

    2020

  9. [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

    2022

  10. [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

  11. [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...

    2009 doi

  12. [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

    2016 doi

  13. [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

    2025

  14. [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

    2022 doi

  15. [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

    2024 doi

  16. [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

    2016

  17. [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

    2019 doi

  18. [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

  19. [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. 10...

    2025

  20. [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

  21. [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/...

    2022

  22. [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

    2023

  23. [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 doi

  24. [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

    2014 doi

  25. [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...

    2018

  26. [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...

    2016

  27. [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). ...

    2020

  28. [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

    2017 doi

  29. [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

    2019

  30. [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–1...

    2018 doi

  31. [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

    2010

  32. [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

    2023 doi

  33. [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

    2017 doi

  34. [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

  35. [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,...

    2025 doi

  36. [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

  37. [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

  38. [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.3202...

    1990

  39. [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

    2023 doi

  40. [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

    2006

  41. [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

  42. [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://d...

    2003

  43. [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

    1996 doi

  44. [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

    2002 doi

  45. [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

    2005 doi

  46. [55]

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

    2001

  47. [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

  48. [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

    2006 doi

  49. [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

  50. [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

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.