Optimal Joins using Compact Data Structures

Gonzalo Navarro; Javiel Rojas-Ledesma; Juan L. Reutter

REVIEW 3 major objections 3 minor 23 references

Optimal Joins using Compact Data Structures

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Full multiway joins can be evaluated in worst-case optimal time directly from a compact quadtree representation of each relation, with roughly two extra words per tuple and no separate indexing layer.

desk verdict A genuinely new worst-case optimal join algorithm on compact quadtrees, with a fixable proof gap in the leaf-level bound of Theorem 3.6. read the letter →

arxiv 1908.01812 v2 pith:KEH3ME6Y submitted 2019-08-05 cs.DB cs.CGcs.DS

Gonzalo Navarro , Juan L. Reutter , Javiel Rojas-Ledesma This is my paper · ORCID

classification cs.DBcs.CGcs.DS MSC 68P1568P0568W40

keywords joinalgorithmsworst-caseoptimalcompactdatastructuresquadtreesqdagAGMboundrelationalalgebralazyevaluation

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

Worst-case optimal join algorithms typically assume an extra indexing layer: B+-trees, hash tables, or a chosen attribute order, all of which consume additional space. This paper claims that a full multiway join can be evaluated in worst-case optimal time using only a compact quadtree representation of each relation, with roughly two extra words per tuple and no separate index. The enabling construction is the qdag, an implicit quadtree that extends a low-dimensional quadtree to the full attribute set without materializing cross products, together with an And operation that intersects the extended trees in one synchronized traversal. The same ideas are lifted to relational algebra queries with union and complement through lazy qdags (lqdags), which keep worst-case optimality when no relation appears in the formula both positively and negatively. If correct, this makes worst-case optimal joins run directly on compressed data and removes the standard overhead of materialized indexes.

What carries the argument

The base machinery is the compact quadtree: a relation $R(A')$ is interpreted as a point set in a $|A'|$-dimensional grid, stored as an MX-quadtree in a levelwise bitvector that supports parent-child navigation in constant time (Observation 2.1). The central new object is the qdag, a pair $(Q,M)$ in which $Q$ is such a quadtree over a $d'$-dimensional grid and $M$ maps each child index $0 \le i < 2^d$ to a child index $M[i] < 2^{d'}$; the qdag implicitly represents a $d$-dimensional quadtree whose completion repeats subtrees of $Q$ according to $M$. The Extend operation builds the mapping that turns $R(A')$ into $R(A') \times \mathrm{All}(A\setminus A')$, and the And operation intersects $n$ completions by synchronized traversal, pruning subgrids that become empty. For relational algebra, lqdags augment quadtrees with full leaves and functor nodes (QTREE, NOT, AND, OR, EXTEND), and their Value and ChildAt operations use a special value $\Diamond$ to delay decisions until children are inspected. Optimality is proved by bounding the maximum number of nodes per level of the non-pruned intersection and trimming the input quadtrees at that level to exhibit a database whose output has that many tuples.

What would settle it

Implement the compact quadtree representation of Observation 2.1 and measure the cost of the navigation operations (descending from parent to child and reading a node's value) as the grid side $\ell$ grows while the number of points $p$ stays fixed; if the per-operation time grows with $\log\ell$, then the constant-time assumption behind Theorem 3.6 fails and the stated join bound is not achievable by this construction.

Watch

Extended reading notes

Core claim

The paper's central result, Theorem 3.6, is that a full join $J = R_1 \bowtie \dots \bowtie R_n$ over a database with $d$ attributes, domains $[0,\ell-1]$, and total input size $N$ can be answered in $O(2^{\rho^*(J,D)} \cdot 2^d n \log\min(\ell,N)) = \tilde{O}(2^{\rho^*(J,D)})$ time after storing each relation $R_i$ in $\sum_i (|A_i|+2+o(1))|R_i|\log\ell + O(n\log d)$ bits. Since storing the tuples themselves costs $|A_i||R_i|\log\ell$ bits, the representation adds about two words per tuple beyond the raw data. The method views each relation as a set of grid points, stores one compact quadtree per relation, wraps it in a qdag to extend it to the full query dimension, and intersects the extensions. A second theorem (Theorem 4.3) extends worst-case optimality to relational algebra formulas built from joins, unions, and complements; the algorithm evaluates such formulas lazily and provably matches the worst-case output size when the formula's atomic operands are all distinct.

Load-bearing premise

The load-bearing premise is that the compact quadtree representation of Observation 2.1 supports the navigation operations ChildAt, Value, and leaf tests in constant time with the stated space; that fact is cited from prior work, and the And and Extend algorithms invoke these operations at every node, so any super-constant navigation cost would break the claimed $\tilde{O}(2^{\rho^*})$ time bound.

Editorial extensions

If this is right

A full join can be answered in $\tilde{O}(2^{\rho^*(J,D)})$ time with no per-query index construction, using only the compact quadtrees already stored for the relations.
The storage overhead beyond the tuples themselves is roughly two words per tuple, independent of the number of attributes, instead of the linear extra space of B+-tree or hash indexes.
A single quadtree per relation supports every query and every attribute order; order-based worst-case optimal algorithms require a separate index for each attribute ordering.
Relational algebra queries combining joins, union, and complement are evaluated in worst-case optimal time whenever the formula does not use the same relation both positively and under NOT.
Query outputs can be returned as compact quadtrees or as lazy lqdags, so intermediate results can be cached, materialized as views, or shared as common subexpressions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The clustered-data analysis sketched in the appendix suggests a route to output-sensitive join processing: on inputs whose points lie in few small clusters, the running time can approach the AGM bound at the cluster scale rather than the full grid scale, which an implementation could exploit directly.
Using lqdags with symbolic projections could yield a compact, worst-case optimal treatment of acyclic and treewidth-bounded queries, where the authors note that materializing and then re-extending projections cancels the benefit.
The space savings translate to a testable systems hypothesis: for a fixed database, the quadtree representation may fit in main memory or in a single machine's RAM when a heavily indexed representation does not, changing join performance through memory-hierarchy effects rather than through asymptotic query complexity.

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.

Desk Editor's Note

read the letter

Colleague,

The paper is worth your time. It shows that a full join can be answered in time roughly proportional to the AGM bound using only a few extra bits per tuple, by representing relations as compact quadtrees and introducing qdags—a mapping that lifts a relation to a higher-dimensional grid without materializing the cross product. The Extend/And framework is elegant, and the lqdag extension to union and complement is honestly scoped, with the antijoin limitation stated explicitly. The proof for internal levels of the intersection tree is sound: the trimming construction correctly bounds the number of internal nodes at any given level by the AGM bound.

The soft spot is the leaf-level case in the proof of Theorem 3.6. The paper claims that when the maximum node count M is reached at the deepest level, M is bounded by the AGM bound because each 1-leaf is an output tuple. But the non-pruned tree Q+ also has 0-leaves at that level—cells where every relation has some point in the prefix but not the actual cell. If R and S each have one tuple in different cells of a 2x2 grid, the join is empty, AGM=1, yet Q+ has four leaves. So M can be as large as 2^d times the AGM bound. The correct statement is M <= 2^d * 2^{rho*}, which changes the time bound to O(2^{rho*} * 2^{2d} n log l). Since d is a query constant, the paper's headline claim of Õ(AGM) time still stands, but Theorem 3.6 as written is too strong.

I don't think this is a fatal flaw. The algorithm remains worst-case optimal in data complexity, and the extra 2^d factor is actually consistent with the paper's own remark that the 2^d factor is "the price to pay for using so little space." The authors should correct the leaf-level argument, either by using the 2^d * AGM bound or by a more careful amortization.

Who is this for? Anyone working on worst-case optimal joins or compact data structures. The citation pattern is fair, the external dependency on Benoit et al.'s compact tree representation is standard, and the main idea is novel. It deserves a serious referee. I would send it to review, expecting a minor revision to fix the proof of Theorem 3.6.

Referee Report

3 major / 3 minor

Summary. The paper proposes compact quadtree-based representations of relations and shows that worst-case optimal join processing can be performed directly on these representations, without the multiple B+-tree or hash indexes used by earlier worst-case optimal join algorithms. The main technical device is the qdag, a sharing-based extension of a quadtree that implicitly represents products R(A') × All(A\A'), and the And/Extend operations that support a simple recursive algorithm for full joins. Theorem 3.6 claims that any full join J can be evaluated in time O(2^{ρ*(J,D)} · 2d n log min(𝓁,N)) = Õ(2^{ρ*(J,D)}) on a representation using only ∑_i (|A_i|+2+o(1))|R_i| log 𝓁 + O(n log d) bits. The paper further introduces lqdags, a lazy variant equipped with NOT, AND, OR, and EXTEND, and claims in Theorem 4.3 that relational algebra queries with joins, union, and complement, under a no-repeated-atomic-expression condition, can also be evaluated in worst-case optimal time.

Significance. If the full-join theorem is correct, it is a significant result: it gives worst-case optimal joins with a single compact index, only a constant number of extra bits per tuple over the raw data, and no dependence on a chosen attribute order. The proof of Theorem 3.6 is coherent: the level-by-level bound on the non-pruned intersection tree against the AGM bound via the prefix-trimming construction is sound, and the dependency on the cited compact cardinal-tree representation of Benoit et al. is standard and explicitly identified. The contribution is also practically motivated, since compact indexes can reside in faster memory than heavily indexed alternatives. However, the paper's advertised extension to relational algebra queries is not established by the proof as written; the lower-bound construction in Lemma 4.2 has a specific technical flaw that undermines Theorem 4.3. The paper also overstates the scope of the extension in the abstract.

major comments (3)

[§4.2, Lemma 4.2 and the paragraph starting 'However, for atomic expressions of the type A_i = (NOT, Q_i)'] The construction of Q''_i for NOT atomic expressions is not correct. The proof negates the values at the (j−1)-th level of Q'_i, but this does not preserve the completion of the NOT expression at nodes where the original quadtree has leaf values 0 or 1 at that level. Concretely, for the formula F = AND((QTREE,Q1),(NOT,Q2)), suppose at a countably relevant level j−1 the node of Q1 is internal (value ½) while Q2 has a leaf 0 at the same subgrid. In the original Q+_F this node has value ½ and is counted toward M/2^d; after the proposed trimming, Q'_1 becomes 1, Q'_2 becomes 0 and then Q''_2 becomes 1, so (NOT,Q''_2) is 0 and the AND evaluates to 0, not 1. Thus the claimed statement that the nodes with value 1 in Q+_F' are precisely the nodes with value 1 or ½ in Q+_F fails, and the lower bound Ω(M/2^d) on the output of the constructed database does not follow.
[§4.2, Lemma 4.2, sentence 'the size of the relation represented by Q''_i cannot be larger than 2^d |Q_i|'] This size claim is false for the generalized quadtrees with full leaves used in Section 4.1. Negating all level-(j−1) values of Q'_i turns every empty leaf 0 at that level into a leaf 1; the number of such leaves can be as large as the total number of cells in the trimmed grid, which is not bounded by 2^d times the number of internal nodes of Q_i. An empty relation has |Q_i|=0, yet the negated trimmed relation can represent a full grid. Since Lemma 4.2 is the sole support for Theorem 4.3, the proof of worst-case optimality for lqdags is not sound as written. The theorem may be repairable, but the current argument needs a substantial revision, for example a case analysis that treats internal nodes and leaves separately or a different lower-bound database.
[Abstract and Theorem 4.3] The abstract claims worst-case optimality for 'more expressive queries from relational algebra' without the caveat stated only later in Theorem 4.3 and Section 4.2: the number of different atomic expressions must equal the number of different relations, a condition that excludes repeated relations and antijoins. The paper itself acknowledges that antijoins and repeated occurrences are not covered. The abstract should state this limitation explicitly.

minor comments (3)

[Observation 2.1] The statement says integer coordinates in the interval [0, log 𝓁 − 1], but the grid has side 𝓁, so the coordinates should be in [0, 𝓁 − 1].
[Theorem 3.6, proof of the case log N = o(log 𝓁)] The padded tuple is written as 0^{log 𝓁 − j} pre(c_1, j), which places the j-bit prefix in the least significant positions. To keep the prefix as the leading bits of the coordinate, the string should be pre(c_1, j) followed by 0^{log 𝓁 − j}; as written, the notation does not match the intended 'keeping the first j bits' construction.
[Definition 3.4 and the display before Section 3.1] The symbol '\' is used where intersection is clearly meant (the And operation computes the intersection of relations, not set difference). If this is not a rendering artifact of the submission, the notation should be corrected to ∩.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: Theorem 3.6 and the lqdag optimality proof derive their bounds from external benchmarks (AGM bound, Benoit et al. compact trees) and standard lower-bound constructions, with no fitted parameter renamed as a prediction.

full rationale

The paper's central claim is that full joins can be answered in time O(2^{rho*(J,D)} polylog) using compact quadtree representations. The derivation chain is self-contained against genuinely external benchmarks. The space bound in Theorem 3.6 follows from Observation 2.1, which cites Benoit et al. [3, Thm. 4.3] for high-arity cardinal trees; that is an independent external result, not a self-citation. The time bound is proved by bounding the maximum per-level node count M of the non-pruned intersection tree Q+. The argument that M is at most the AGM bound constructs a database D' by trimming tuples to the first j bits; each relation R'_i has at most |R_i| tuples, and the trimmed join output contains one distinct tuple per level-j node of Q+, so M <= 2^{rho*(J,D')} <= 2^{rho*(J,D)}. This is a standard adversary/lower-bound construction, not a reduction of the result to its own assumptions. No parameter is fitted to data and then renamed as a prediction. The lqdag optimality proof (Lemma 4.2 and Theorem 4.3) uses the same trimming technique, including a negated-level construction for NOT operands, to show that any algorithm must spend time proportional to the maximum possible output over databases of comparable size; again this is a standard lower-bound argument. Self-citations do appear (e.g., [4], [5], [1], [7] include author Navarro), but they are used for implementation details such as an 'internal node with all zero children' encoding or for motivating clustered-data refinements, not as load-bearing justification of the optimality theorems. Observation 2.1, the main external dependency, is attributed to Benoit et al., not to the authors' own prior work. The only caveat is scope: the abstract's phrase 'more expressive queries from relational algebra' is qualified by Theorem 4.3's condition that atomic expressions refer to different relations, and the paper itself notes that antijoins and acyclic-query improvements are not covered. That is a scope limitation and a correctness-risk observation, not circular reasoning. No step in the derivation reduces, by the paper's own equations, to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The paper rests on two external pillars: the compact cardinal-tree representation of Benoit et al. (for the space of quadtrees) and the AGM bound of Atserias et al. (for the optimality benchmark). The framework's novel structures (qdags, lqdags) are self-contained with explicit definitions and proofs. No free parameters are fitted to data.

assumptions (5)

standard math High-arity cardinal trees can be represented in (d+2+o(1)) p log 𝓁 + O(log d) bits with constant-time navigation (Benoit et al., Thm 4.3).
Used as Observation 2.1 to bound the space of compact quadtrees; an external published theorem, not re-derived here.
standard math The AGM bound (Atserias, Grohe, Marx) is the maximum output size of a join query over databases with given relation cardinalities.
Serves as the external benchmark for worst-case optimality in Theorem 3.6 and the lqdag extension.
domain assumption The domain of every attribute is [0, 𝓁-1] with 𝓁 a power of 2.
Stated at the start of Sections 2 and 3; the paper notes this is a simplifying assumption, with standard padding or value re-encoding available for other domains.
domain assumption Relations are sets of distinct tuples, and a relation over attributes A is represented by the point set of its tuples in the |A|-dimensional grid.
The quadtree representation models tuples as grid points; duplicate tuples are not handled.
domain assumption For the relational algebra extension, each relation appears in exactly one atomic expression of the formula after pushing negations down (no relation appears both negated and non-negated).
This condition limits Theorem 4.3; the paper explicitly notes that antijoin fails the condition and is not worst-case optimal in its framework.

invented entities (2)

qdag
purpose: Implicitly represents d-dimensional quadtrees that are Cartesian products R(A') × All(A\A') without materializing the expanded relation; used by the Extend and And operations for worst-case optimal joins.
Introduced as Definition 3.1. The paper proves its navigation and space properties theoretically, but no implementation or external empirical validation is provided.
lqdag
purpose: Lazy quadtree with functor nodes for QTREE, NOT, AND, OR, EXTEND, plus a fourth value ♦ to defer evaluation; enables worst-case optimal evaluation of restricted relational algebra formulas.
Introduced as Definition 4.1. The theoretical analysis covers its complexity, but again no external validation or implementation is shipped.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal Joins using Compact Data Structures." pith.science (2026). https://pith.science/paper/KEH3ME6Y

@misc{pith2026190801812,
  author       = {Pith},
  title        = {Pith review of: Optimal Joins using Compact Data Structures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KEH3ME6Y}},
  note         = {Machine review of arXiv:1908.01812}
}

abstract

Worst-case optimal join algorithms have gained a lot of attention in the database literature. We now count with several algorithms that are optimal in the worst case, and many of them have been implemented and validated in practice. However, the implementation of these algorithms often requires an enhanced indexing structure: to achieve optimality we either need to build completely new indexes, or we must populate the database with several instantiations of indexes such as B$+$-trees. Either way, this means spending an extra amount of storage space that may be non-negligible. We show that optimal algorithms can be obtained directly from a representation that regards the relations as point sets in variable-dimensional grids, without the need of extra storage. Our representation is a compact quad tree for the static indexes, and a dynamic quadtree sharing subtrees (which we dub a qdag) for intermediate results. We develop a compositional algorithm to process full join queries under this representation, and show that the running time of this algorithm is worst-case optimal in data complexity. Remarkably, we can extend our framework to evaluate more expressive queries from relational algebra by introducing a lazy version of qdags (lqdags). Once again, we can show that the running time of our algorithms is worst-case optimal.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

\'A lvarez-Garc \' a, N

S. \'A lvarez-Garc \' a, N. Brisaboa, J. Fern \'a ndez, M. Mart \' nez-Prieto, and G. Navarro. Compressed vertical partitioning for efficient RDF management. Knowledge and Information Systems , 44(2):439--474, 2015

work page 2015
[2]

Atserias, M

A. Atserias, M. Grohe, and D. Marx. Size bounds and query plans for relational joins. SIAM Journal on Computing , 42(4):1737--1767, 2013

work page 2013
[3]

Benoit, E

D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman, and S. S. Rao. Representing trees of higher degree. Algorithmica , 43(4):275--292, 2005

work page 2005
[4]

N. R. Brisaboa, S. Ladra, and G. Navarro. Compact representation of W eb graphs with extended functionality. Information Systems , 39(1):152--174, 2014

work page 2014
[5]

de Bernardo, S

G. de Bernardo, S. Alvarez-Garc \' a, N. Brisaboa, G. Navarro, and O. Pedreira. Compact querieable representations of raster data. In Proc. 20th International Symposium on String Processing and Information Retrieval (SPIRE) , pages 96--108, 2013

work page 2013
[6]

R. A. Finkel and J. L. Bentley. Quad T rees: A data structure for retrieval on composite keys. Acta Informatica , 4:1--9, 1974

work page 1974
[7]

Gagie, J

T. Gagie, J. Gonz \'a lez-Nova, S. Ladra, G. Navarro, and D. Seco. Faster compressed quadtrees. In Proc. 25th Data Compression Conference (DCC) , pages 93--102, 2015

work page 2015
[8]

Hogan, C

A. Hogan, C. Riveros, C. Rojas, and A. Soto. Extending sparql engines with multiway joins. In Proc. 18th International Semantic Web Conference (ISWC) , 2019. To appear

work page 2019

Show all 23 references

[9]

M. A. Khamis, H. Q. Ngo, C. R \'e , and A. Rudra. Joins via geometric resolutions: Worst case and beyond. ACM Transactions on Database Systems , 41(4):22, 2016

2016
[10]

M. A. Khamis, H. Q. Ngo, and A. Rudra. Faq: Questions asked frequently. In Proc. 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) , pages 13--28, 2016

2016
[11]

M. A. Khamis, H. Q. Ngo, and D. Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In Proc. 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) , pages 429--444, 2017

2017
[12]

G. M. Morton. A computer oriented geodetic data base; and a new technique in file sequencing. Technical report, IBM Ltd., 1966

1966
[13]

G. Navarro. Compact Data Structures -- A practical approach . Cambridge University Press, 2016

2016
[14]

H. Q. Ngo. Worst-case optimal join algorithms: Techniques, results, and open problems. In Proc. 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) , pages 111--124, 2018

2018
[15]

H. Q. Ngo, D. T. Nguyen, C. Re, and A. Rudra. Beyond worst-case analysis for joins with minesweeper. In Proc. 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) , pages 234--245, 2014

2014
[16]

H. Q. Ngo, C. R \'e , and A. Rudra. Skew strikes back: New developments in the theory of join algorithms. ACM SIGMOD Record , 42(4):5--16, 2014

2014
[17]

Worst-case optimal join algorithms

Hung Q Ngo, Ely Porat, Christopher R \'e , and Atri Rudra. Worst-case optimal join algorithms. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems , pages 37--48. ACM, 2012

2012
[18]

Nguyen, M

D. Nguyen, M. Aref, M. Bravenboer, G. Kollias, H. Q. Ngo, C. R \'e , and A. Rudra. Join processing for graph patterns: An old dog with new tricks. In Proc. 3rd International Workshop on Graph Data Management Experiences and Systems (GRADES) , pages 2:1--2:8, 2015

2015
[19]

H. Samet. Foundations of Multidimensional and Metric Data Structures . Morgan Kaufmann, 2006

2006
[20]

D. Suciu. Communication cost in parallel query evaluation: A tutorial. In Proc. 36th ACM Symposium on Principles of Database Systems (PODS) , pages 319--319, 2017

2017
[21]

T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proc. 17th International Conference on Database Theory (ICDT) , pages 96--106, 2014

2014
[22]

D. S. Wise and J. Franco. Costs of quadtree representation of nondense matrices. Journal of Parallel and Distributed Computing , 9(3):282--296, 1990

1990
[23]

Yannakakis

M. Yannakakis. Algorithms for acyclic database schemes. In Proc. 7th International Conference on Very Large Databases (VLDB) , pages 82--94, 1981

1981

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

\'A lvarez-Garc \' a, N

S. \'A lvarez-Garc \' a, N. Brisaboa, J. Fern \'a ndez, M. Mart \' nez-Prieto, and G. Navarro. Compressed vertical partitioning for efficient RDF management. Knowledge and Information Systems , 44(2):439--474, 2015

work page 2015

[2] [2]

Atserias, M

A. Atserias, M. Grohe, and D. Marx. Size bounds and query plans for relational joins. SIAM Journal on Computing , 42(4):1737--1767, 2013

work page 2013

[3] [3]

Benoit, E

D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman, and S. S. Rao. Representing trees of higher degree. Algorithmica , 43(4):275--292, 2005

work page 2005

[4] [4]

N. R. Brisaboa, S. Ladra, and G. Navarro. Compact representation of W eb graphs with extended functionality. Information Systems , 39(1):152--174, 2014

work page 2014

[5] [5]

de Bernardo, S

G. de Bernardo, S. Alvarez-Garc \' a, N. Brisaboa, G. Navarro, and O. Pedreira. Compact querieable representations of raster data. In Proc. 20th International Symposium on String Processing and Information Retrieval (SPIRE) , pages 96--108, 2013

work page 2013

[6] [6]

R. A. Finkel and J. L. Bentley. Quad T rees: A data structure for retrieval on composite keys. Acta Informatica , 4:1--9, 1974

work page 1974

[7] [7]

Gagie, J

T. Gagie, J. Gonz \'a lez-Nova, S. Ladra, G. Navarro, and D. Seco. Faster compressed quadtrees. In Proc. 25th Data Compression Conference (DCC) , pages 93--102, 2015

work page 2015

[8] [8]

Hogan, C

A. Hogan, C. Riveros, C. Rojas, and A. Soto. Extending sparql engines with multiway joins. In Proc. 18th International Semantic Web Conference (ISWC) , 2019. To appear

work page 2019