Pith. sign in

REVIEW 3 major objections 5 minor 57 references

Worst-Case Optimal BGPs on Temporal Graphs

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

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

Pith's one-line read An O(N)-space index evaluates any temporal basic graph pattern in worst-case-optimal time O(Q* m log N), simulating Leapfrog Triejoin on the implicit point-based representation.

desk verdict Genuinely new linear-space wco temporal join construction, but the stress-test is likely right: Algorithm 4 has a concrete indexing bug that must be fixed before the main theorem is trustworthy. read the letter →

arxiv 2607.20356 v1 pith:2PRNKXNF submitted 2026-07-22 cs.DB cs.DS

Diego Arroyuelo , Aidan Hogan , Gonzalo Navarro , Juan Reutter This is my paper
classification cs.DBcs.DS
keywords temporalgraphsworst-caseoptimaljoinsLeapfrogTriejoinversionedbinarytriespoint-basedrepresentationbasicgraphpatternslinear-spaceindexwaveletmatrix
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

Temporal graphs, where every edge carries a validity interval, are normally queried either by ignoring time and filtering later (join-first) or by sweeping every time instant (time-first); both pay for far more work than the answers require. This paper claims a middle path: index the graph once, in O(N) space, so that time is just another join attribute whose values are compressed intervals. It proves that with this index, every temporal basic graph pattern — quads (s,p,o,t) with constants, variables, and order constraints on time — can be evaluated in worst-case-optimal time O(Q* m log N), for any variable elimination order, where Q* is the maximum number of solutions obtainable from any temporal graph whose point-based representation has the same size as the given graph's implicit one. The same index answers point-in-time and interval queries with worst-case bounds measured against the sliced graph only, and lists validity intervals of matching triples. If correct, this gives the first linear-space, worst-case-optimal engine for temporal graph pattern matching.

What carries the argument

The key object is a pointer-free, versioned binary trie ('event trie') that encodes, for each node of each of the 24 LTJ tries, the entire history of insertions and deletions of its child values across time. Instead of storing a new branch per version, the structure keeps a single binary trie of update paths, with two per-node bitvectors: B_d records whether each timestamped update goes left or right at depth d, and E_d records whether the node actually exists at that timestamp. Storing these bitvectors levelwise and navigating by rank operations (the wavelet-matrix layout) removes all pointers, giving O(N) space; a top-down walk with a local offset p simulates the version of the trie at tim

What would settle it

Implement the Section 6.2 structure for a tiny temporal graph, maintain a straightforward pointer-based versioned binary trie as ground truth, and after each insertion/deletion event compare the two structures: the set of leaves reachable at that timestamp must be identical, and leap must return the same successor. The first timestamp where the bitvector-descent reaches a different node, or leap returns a different value, falsifies Theorem 4's data structure as specified. Equivalently, run both against a brute-force join on random small graphs and query pairs and compare the output sets.

Watch

Extended reading notes

Core claim

The central claim is Theorem 4: for any temporal graph G with N tuples there is an O(N)-space data structure that, given any temporal basic graph pattern Q of m tuple patterns (with order constraints between time variables), returns all satisfying assignments in worst-case-optimal time O(Q* m log N). The bound Q* is the worst-case output cardinality bound adapted to temporal graphs: it is the maximum number of solutions of Q over any temporal graph whose point-based representation — the expansion of every interval into one quad per valid instant — has no more tuples than the given graph's point-based representation. The paper further claims the structure can simulate the Leapfrog Triejoin al

Load-bearing premise

The argument assumes that reducing every global update timestamp to a subtree-local offset via rank operations, and checking existence via the E_d bitvectors, gives exactly the versioned trie that a pointer-based construction would produce at every timestamp; if this simulation ever deviates, both the O(log N) leap time and the O(N) space bound collapse. The section containing this invariant (6.2) closes with 'This completes the proof of Theorem 4' after illustrating the mech

Editorial extensions

If this is right

  • Any temporal BGP — including queries with several time variables connected by order constraints — is evaluated in worst-case-optimal time O(Q* m log N) in O(N) space, under any variable elimination order, so query planners are free to bind time early, late, or in the middle.
  • Point-in-time and interval queries inherit stronger guarantees: answers valid at a single instant t, or somewhere inside [t1,t2), are computed in worst-case-optimal time with respect to the sliced graphs G_t and G_t1,t2, which can be much smaller than the whole graph.
  • A single triple pattern can be reported together with all maximal intervals of validity in O(log N) per occurrence, enabling efficient version-difference tracking between two timestamps.
  • Queries that require answers to persist over at least delta time units are handled in worst-case-optimal time with respect to the subgraph of long-lived tuples.
  • Experimental results on real-world datasets show the index answers realistic queries in sub-millisecond to millisecond times, while using about 240–250 bytes per edge; the ability to bind time anywhere is consistently faster than forcing time-first or join-first strategies.

Reading between the lines

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

  • If the pointer-free navigation invariant holds in full generality, the same event-trie/bitvector trick could be applied to any versioned data structure, not just LTJ tries — any sequence of insertions and deletions over a static alphabet becomes a linear-space 'timeline trie' with O(log N) navigation per step.
  • The paper's simulation of the quadratic point-based representation inside linear space suggests a general recipe: design wco algorithms for the 'materialized' form, then compress the materialization with a versioned trie; other implicit blow-ups (e.g., interval joins in relational systems) may admit the same treatment.
  • The static index already supports appending new events at increasing timestamps in O(log N) time (Appendix G); a streaming variant could unlock worst-case-optimal temporal joins on dynamic graphs, though the authors do not claim this as a main result.
  • The paper's conclusion notes that beyond-wco guarantees via generalized hypertree decomposition are a natural next step; the main obstacle is representing intermediate results in compact time-interval form, and solving that would make the approach a drop-in engine under GHD-style plans.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proposes a compact data structure for temporal labeled graphs, where each edge has an interval of validity, and claims to evaluate temporal basic graph patterns (tBGPs) in worst-case-optimal (wco) time O(Q* m log N) using O(N) space, where Q* is an AGM-style bound on the point-based representation. The approach adapts Leapfrog Triejoin by representing all snapshots through versioned binary tries, stored in a pointer-free levelwise bitvector form that supports leap via rank queries. The paper also claims stronger guarantees for point-in-time, point-in-interval, and duration queries, and reports experiments on Wikidata, Divvy, Yellow, and Caida.

Significance. If the main result is correct, it is significant: it would bring worst-case-optimal join evaluation to temporal BGPs with arbitrary variable elimination orders and with the time attribute placed anywhere in the order, while using only linear space, and it would improve on join-first and time-first strategies. The authors make the construction concrete by giving pseudocode for the key primitives, provide an artifact link, and evaluate on real datasets with reproducible experimental details. These are real strengths. However, the central technical claim is currently not established: the leap routine in Algorithm 4 has a concrete correctness bug in an edge case, and the navigation invariant underlying Theorem 4 is asserted via examples rather than proved. The result is therefore promising but not yet sound as written.

major comments (3)
  1. [§6.2, Algorithm 4 (Appendix B)] The right-child fallback in the else branch is incorrect when p'=0 and r>0. The guard `if r=0 or E_{d+1}[e-r+p']=0` uses p'=rank(B_d,s,s+p). If p'=0, then e-r+p'=e-r, which is the last position of the left child's segment, not a position in the right child. If the left child exists at the queried timestamp, that E bit is 1, the guard passes, and `leftmost(d+1, e-r+1, e, p'-1=-1, h-1)` is called with a negative local offset. This contradicts the §6.2 claim that "p cannot become negative"; it is exactly p'-1 that becomes negative. The recursive leftmost can then access positions belonging to the left child's segment (e.g., E_{d+2}[s_v-1]) and return a value that does not exist at the queried timestamp. This breaks leap for any historical query before the first right-going update of a node, and thus Theorem 4 is not established. A guard `if p'=0 then return +inf` appears necessary, accompan
  2. [§6.2, proof of Theorem 4] The paper's main theorem rests on a navigation invariant: local-offset rank arithmetic is claimed to simulate the versioned trie at timestamp p_l. This invariant is only illustrated by Examples 12–14 and then followed by "This completes the proof of Theorem 4." No formal induction is supplied for the invariant, for the null-detection via E_d, for the left/right offset updates, or for the leftmost fallback; the non-redundancy normal form of Definition 1 is not used in the proof. Even after fixing the p'=0 bug, this is a load-bearing omission. The proof of Theorem 4 must be written out in full and must cover all branches of Algorithm 4.
  3. [Appendix C, Algorithm 5] The interval version of leap, used for Theorem 6, is not checkable as written. The first guard contains an undefined variable `p` (`if s+p not in [s,e] ...`), while the parameters are `p1` and `p2`. The right-child existence checks similarly use p1' and p2' without addressing the case where one of them is 0; the note about `rank(E,i,i-1)` does not repair the undefined variable. Since Theorem 6 depends on this algorithm, the pseudocode must be corrected and the interval invariant stated and proved, including the p1=p2 special case.
minor comments (5)
  1. [§3.2, Definition 6] The notation `Q* := max{|Q(G')|, |\hat G'| <= |\hat G|}` is unusual; please define the set over which the maximum is taken. The abstract's phrase "same number of instants of edge validity" should be aligned with Definition 6.
  2. [§5.3 / Theorem 4] Please clarify the output mode. The algorithm reports time ranges, while Definition 3 defines solutions at individual instants of T_G. State explicitly that the compact interval output can be expanded at no extra asymptotic cost, or adjust the statement of Theorem 4 accordingly.
  3. [§6.1] The text says every update induces 2bℓ+1 bits and then computes L·2bℓ bits; the missing +1 is harmless but should be made consistent to avoid confusion.
  4. [Appendix A, Proposition 16] The homomorphism argument is terse. In particular, the step "we also need to map the atom mapping w to the fifth position" needs a clearer explanation of why the same atom cannot satisfy both requirements in the constructed instances G1 and G2.
  5. [Table 2 footnote] The hardware-speed claim rests on an informal "Gemini" estimate. Please replace it with a measurable benchmark or a citable source, or remove the conjecture.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the wco bound is defined against an explicit point-based benchmark and the derivation is self-contained; self-citations are implementation-level.

full rationale

I traced the derivation of Theorem 4 back to Definition 6. The AGM bound Q* is defined independently of the proposed algorithm as the maximum number of solutions over any temporal graph whose point-based representation has at most |G-hat| quads; the theorem then claims an algorithm running in O(Q* m log N). This is the standard wco yardstick, not a quantity fitted from the algorithm's output. The proof route is to simulate LTJ [51] on the point-based representation without materializing it; LTJ is an external, well-known algorithm, and the simulation's correctness is argued from the VBT navigation invariants. No parameter is fitted to a subset of data and then reported as a prediction; no empirical result is used to define the complexity bound. The self-citations ([7,8] for compact tries / trie switching) are used only in the implementation section to reduce constant factors and do not carry the O(N)-space or O(Q* m log N) theorem; those rest on the bitvector/rank construction citing external rank-support results [17,43]. The paper does not invoke an author-generated uniqueness theorem to force its design, nor does it adopt an ansatz solely through self-citation. The closest thing to a concern is that the navigation invariant in Section 6.2 is demonstrated by Examples 12-14 and then concluded with 'This completes the proof of Theorem 4'; if the invariant is wrong (as a skeptical reading of Algorithm 4 suggests), that is a correctness gap, not a circular definition or fitted-input prediction, and therefore does not raise the circularity score. Overall, the central complexity claim is self-contained against an explicit benchmark and I find no circular step.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No numbers are fitted to data for the central claim; the only free choices are structural (trie height 4, bit width l = ceil(log2 U), b levels after time), which are parameters of the construction rather than fitted values. The versioned binary trie / levelwise bitvector structure is a data structure, not a hypothesized physical entity, and it has a falsifiable handle in the shipped code and experiments. All other inputs are standard results (LTJ, rank/select, wavelet matrices) and stated domain assumptions (non-redundancy, acyclic time clauses, AGM defined over the point expansion).

assumptions (6)
  • standard math Leapfrog Triejoin is worst-case-optimal on conjunctive queries over tries when leap is O(log N) (Veldhuizen [51]).
    Core building block: the temporal result inherits the LTJ complexity framework, including the O(Q*·m·log) accounting used in the bound of Theorem 4.
  • standard math Bitvector rank (and select) can be answered in O(1) with o(|B|) extra bits [17,43]; levelwise concatenation of bitvectors is valid as in wavelet matrices [18].
    Used in Section 6.2 for pointer-free navigation of the linear-space structure; these are established succinct-data-structure results.
  • domain assumption Temporal graphs have no redundant tuples: intervals of the same triple are disjoint (Definition 1).
    Guarantees a unique representation and that each tuple generates exactly two events (insert at ti, delete at tf), which is the basis of the O(N) space accounting. Real data may violate it, but it is a normal form that can be enforced by merging overlapping intervals.
  • domain assumption The comparison clauses w1 <= w2 in tBGPs are satisfiable and acyclic (Section 3.1).
    Cyclic constraints are excluded by fiat; acyclicity is what allows the algorithm to bind one temporal variable and then restrict the other to a range while remaining wco.
  • ad hoc to paper The navigation invariant of Section 6.2: local-offset rank arithmetic (p - rank(B_d, s_v, s_v+p) left; rank - 1 right) correctly simulates the versioned trie state at timestamp p_l, and the E_d bitvectors correctly indicate node existence.
    Load-bearing for both the O(log N) leap and the O(N) space claim of Theorem 4; asserted with Examples 12-14 and no formal proof in this version, with details deferred to the extended version.
  • domain assumption The AGM bound is defined w.r.t. the point-based representation G-hat (Definitions 5-6): Q* = max |Q(G')| over graphs with |G-hat'| <= |G-hat|.
    This definitional choice is what makes O(Q*·m·log N) the correct wco target. It is stated explicitly, but the reader should note the bound is against the (possibly quadratic) point expansion, not the N interval tuples directly.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Worst-Case Optimal BGPs on Temporal Graphs." pith.science (2026). https://pith.science/paper/2PRNKXNF

@misc{pith2026260720356,
  author       = {Pith},
  title        = {Pith review of: Worst-Case Optimal BGPs on Temporal Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2PRNKXNF}},
  note         = {Machine review of arXiv:2607.20356}
}
read the original abstract

We study how to evaluate basic graph patterns (BGPs) in a worst-case-optimal (wco) manner over {\em temporal} labeled graphs, where edges have an interval of temporal validity. We adopt a flexible query language in which users specify m quads of the form (subject, property, object, time), using constants or variables. The time component denotes the instant at which a particular edge is valid, and users may also include order relations between temporal constants or variables. The answer is the set of all valid variable assignments, including time. We describe an index structure that, for a temporal graph with N edges, requires O(N) space and can evaluate extended BGPs in wco time O(Q* m log N), where Q* represents the maximum number of solutions for query Q over any temporal graph with the same number of instants of edge validity. We use our index to adapt Leapfrog Triejoin to the temporal graph setting under any variable evaluation ordering. Our index further yields wco guarantees for related query types, including snapshot evaluation, version queries, and other temporal variants. Experiments on real-world datasets show that our approach answers realistic queries in milliseconds with low space overhead.

Figures

Figures reproduced from arXiv: 2607.20356 by the authors.

Figure 1
Figure 1. A toy temporal graph about trips on buses. For simplicity the timestamps show only hours during some day. Example 1. As a motivating example, consider a graph describing the bus trips over a year in a big city, with quads (𝑎, trip, 𝑏, [ti, tf)) indicating that person 𝑎 was on bus 𝑏 during time interval [ti, tf) [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. As explained, we need not consider other times in the [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 2
Figure 2. Point-based representation of the graph of [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figures from the paper (8 more)
Figure 3
Figure 3. Figure 3: The LTJ trie of order pos for the graph of [PITH_FULL_IMAGE:figures/full_fig_p005_3.png]
Figure 4
Figure 4. Figure 4: At the top, three consecutive versions of an LTJ [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: The otps trie corresponding to the graph of [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 6
Figure 6. Figure 6: On the left, the two final levels of an LTJ trie node rooted at [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 7
Figure 7. Figure 7: On the top, the BTs of six consecutive timestamps, corresponding to inserting [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]
Figure 8
Figure 8. Figure 8: Left: Boxplots of runtimes in msec. Right: number [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]
Figure 9
Figure 9. Figure 9: Left: boxplots of runtimes in msec for the query with clause 𝑡1 ≤ 𝑡2. Right: comparison with Hu et al. [30] for point-in-time queries on WikiT. another. Our LC strategy is on average twice as fast as JF and orders of magnitude faster than TF. The boxplots of LC and JF …
Figure 10
Figure 10. Figure 10: The meta-trie of all the LTJ tries we need to build. [PITH_FULL_IMAGE:figures/full_fig_p020_10.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

57 extracted references · 2 linked inside Pith

  1. [1]

    Emptyheaded: A relational engine for graph processing

    Christopher R Aberger, Andrew Lamb, Susan Tu, Andres Nötzli, Kunle Olukotun, and Christopher Ré. Emptyheaded: A relational engine for graph processing. ACM Transactions on Database Systems, 42(4):1–44, 2017

    2017

  2. [2]

    The complexity of boolean conjunctive queries with intersection joins

    Mahmoud Abo Khamis, George Chichirim, Antonia Kormpa, and Dan Olteanu. The complexity of boolean conjunctive queries with intersection joins. InProc. 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 53–65, 2022

    2022

  3. [3]

    What do Shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? InProc

    Mahmoud Abo Khamis, Hung Q Ngo, and Dan Suciu. What do Shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? InProc. 36th ACM Symposium on Principles of Database Systems (PODS), pages 429–444, 2017

    2017

  4. [4]

    Index maintenance for time-travel text search

    Avishek Anand, Srikanta Bedathur, Klaus Berberich, and Ralf Schenkel. Index maintenance for time-travel text search. InProc. 35th International ACM Confer- ence on Research and Development in Information Retrieval (SIGIR), pages 235–244, 2012

    2012

  5. [5]

    Foundations of modern query languages for graph databases

    Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč. Foundations of modern query languages for graph databases. ACM Computing Surveys, 50(5):1–40, 2017

    2017

  6. [6]

    Temporal regular path queries

    Marcelo Arenas, Pedro Bahamondes, Amir Aghasadeghi, and Julia Stoyanovich. Temporal regular path queries. In2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 2412–2425. IEEE, 2022

    2022

  7. [7]

    CompactLTJ: Space & time efficient Leapfrog Triejoin on graph databases.The Very Large Databases Journal, 34:article 67, 2025

    Diego Arroyuelo, Daniela Campos, Adrián Gómez-Brandón, Yuval Linker, Gon- zalo Navarro, Carlos Rojas, and Domagoj Vrgoc. CompactLTJ: Space & time efficient Leapfrog Triejoin on graph databases.The Very Large Databases Journal, 34:article 67, 2025

    2025

  8. [8]

    Reutter, Javiel Rojas-Ledesma, and Adriá Soto

    Diego Arroyuelo, Adrián Gómez-Brandón, Aidan Hogan, Gonzalo Navarro, Juan L. Reutter, Javiel Rojas-Ledesma, and Adriá Soto. The Ring: Worst-case optimal joins in graph databases using (almost) no extra space.ACM Transactions on Database Systems, 29(2):article 5, 2024

    2024

Show all 57 references
  1. [9]

    Size bounds and query plans for relational joins.SIAM Journal on Computing, 42(4):1737–1767, 2013

    Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins.SIAM Journal on Computing, 42(4):1737–1767, 2013

    2013

  2. [10]

    A time machine for text search

    Klaus Berberich, Srikanta Bedathur, Thomas Neumann, and Gerhard Weikum. A time machine for text search. InProc. 30th Annual International ACM Conference on Research and Development in Information Retrieval (SIGIR), pages 519–526, 2007

    2007

  3. [11]

    Temporal statement modifiers.ACM Transactions on Database Systems, 25(4):407–456, 2000

    Michael H Böhlen, Christian S Jensen, and Richard Thomas Snodgrass. Temporal statement modifiers.ACM Transactions on Database Systems, 25(4):407–456, 2000

    2000

  4. [12]

    Demaine, J

    Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, and Robert Sedgewick. Resizable arrays in optimal time and space. InProc. 6th International Symposium on Algorithms and Data Structures (W ADS), pages 37–48, 1999

    1999

  5. [13]

    Temporal knowledge graph completion: A survey.arXiv preprint arXiv:2201.08236, 2022

    Borui Cai, Yong Xiang, Longxiang Gao, He Zhang, Yunfeng Li, and Jianxin Li. Temporal knowledge graph completion: A survey.arXiv preprint arXiv:2201.08236, 2022

    2022 arXiv

  6. [14]

    A survey on temporal knowledge graph: Representation learning and applications

    Li Cai, Xin Mao, Yuhao Zhou, Zhaoguang Long, Changxu Wu, and Man Lan. A survey on temporal knowledge graph: Representation learning and applications. arXiv preprint arXiv:2403.04782, 2024

    2024 arXiv

  7. [15]

    Indexing temporal relations for range-duration queries

    Matteo Ceccarello, Anton Dignös, Johann Gamper, and Christina Khnaisser. Indexing temporal relations for range-duration queries. InProceedings of the 35th International Conference on Scientific and Statistical Database Management, pages 1–12, 2023

    2023

  8. [16]

    Chan, Kasper G

    Timothy M. Chan, Kasper G. Larsen, and Mihai Pătraşcu. Orthogonal range searching on the RAM, revisited. InProc. 27th ACM Symposium on Computational Geometry (SoCG), pages 1–10, 2011

    2011

  9. [17]

    Clark.Compact PAT Trees

    David R. Clark.Compact PAT Trees. PhD thesis, University of Waterloo, Canada, 1996

    1996

  10. [18]

    The wavelet matrix: An efficient wavelet tree for large alphabets.Information Systems, 47:15–32, 2015

    Francisco Claude, Gonzalo Navarro, and Alberto Ordóñez. The wavelet matrix: An efficient wavelet tree for large alphabets.Information Systems, 47:15–32, 2015

    2015

  11. [19]

    On completeness of historical relational data models

    Albert Croker and James Clifford. On completeness of historical relational data models. NYU Working Paper No. IS-89-002, 1989

    1989

  12. [20]

    Versioned queries over RDF archives: All you need is SPARQL? InMEPDaW@ ISWC, pages 43–52, 2020

    Ignacio Cuevas and Aidan Hogan. Versioned queries over RDF archives: All you need is SPARQL? InMEPDaW@ ISWC, pages 43–52, 2020

    2020

  13. [21]

    Temporal alignment

    Anton Dignös, Michael H Böhlen, and Johann Gamper. Temporal alignment. In Proc. ACM International Conference on Management of Data (SIGMOD), pages 433–444, 2012

    2012

  14. [22]

    A researcher’s digest of GQL

    Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. A researcher’s digest of GQL. InProc. 26th International Conference on Database Theory (ICDT), pages 1:1–1:22, 2023

    2023

  15. [23]

    Freitag, Maximilian Bandle, Tobias Schmidt, Alfons Kemper, and Thomas Neumann

    Michael J. Freitag, Maximilian Bandle, Tobias Schmidt, Alfons Kemper, and Thomas Neumann. Adopting worst-case optimal joins in relational database systems.Proceedings of the VLDB Endowment, 13(11):1891–1904, 2020

    1904

  16. [24]

    Time-respecting flow graph pattern matching on temporal graphs.IEEE Trans- actions on Knowledge and Data Engineering, 33(10):3453–3467, 2020

    Yunjun Gao, Tianming Zhang, Linshan Qiu, Qingyuan Linghu, and Gang Chen. Time-respecting flow graph pattern matching on temporal graphs.IEEE Trans- actions on Knowledge and Data Engineering, 33(10):3453–3467, 2020

    2020

  17. [25]

    Eventkg: A multilingual event-centric temporal knowledge graph

    Simon Gottschalk and Elena Demidova. Eventkg: A multilingual event-centric temporal knowledge graph. InEuropean semantic web conference, pages 272–287. Springer, 2018

    2018

  18. [26]

    Multi-temporal RDF ontology versioning

    Fabio Grandi et al. Multi-temporal RDF ontology versioning. InIWOD@ ISWC, 2009

    2009

  19. [27]

    T-SPARQL: A TSQL2-like temporal query language for RDF

    Fabio Grandi et al. T-SPARQL: A TSQL2-like temporal query language for RDF. InADBIS (local proceedings), volume 639, pages 21–30, 2010

    2010

  20. [28]

    A worst-case optimal join algorithm for SPARQL

    Aidan Hogan, Cristian Riveros, Carlos Rojas, and Adrián Soto. A worst-case optimal join algorithm for SPARQL. InProc. 18th International Semantic Web Conference (ISWC), pages 258–275, 2019

    2019

  21. [29]

    An efficient and scalable graph database with built-in temporal support: J

    Jiamin Hou, Zhanhao Zhao, Wei Lu, Shiming Yang, Shuang Liu, Quanqing Xu, Chuanhui Yang, and Xiaoyong Du. An efficient and scalable graph database with built-in temporal support: J. hou et al.The VLDB Journal, 34(4):53, 2025

    2025

  22. [30]

    Agarwal, and Jun Yang

    Xiao Hu, Stavros Sintos, Junyang Gao, Pankaj K. Agarwal, and Jun Yang. Com- puting complex temporal join queries efficiently. InProc. International Conference on Management of Data (SIGMOD), pages 2076–2090, 2022

  23. [31]

    TeMatch: A fast temporal sub- graph matching framework with temporal-aware subgraph matching algorithms

    Chengying Huan, Heng Zhang, Yongchao Liu, Likang Chen, Xuran Wang, Yongchun Jiang, Shaonan Ma, and Yanjun Wu. TeMatch: A fast temporal sub- graph matching framework with temporal-aware subgraph matching algorithms. In2025 IEEE 41st International Conference on Data Engineering ...

    2025

  24. [32]

    Space-efficient static trees and graphs

    Guy Jacobson. Space-efficient static trees and graphs. InProc. 30th IEEE Sympo- sium on Foundations of Computer Science (FOCS), pages 549–554, 1989

    1989

  25. [33]

    Khamis, Hung Q

    Mahmoud A. Khamis, Hung Q. Ngo, Cristopher Ré, and Atri Rudra. Joins via geometric resolutions: Worst case and beyond.ACM Transactions on Database Systems, 41(4):22, 2016

    2016

  26. [34]

    Storing and analyzing historical graph data at scale

    Udayan Khurana and Amol Deshpande. Storing and analyzing historical graph data at scale. InInternational Conference on Extending Database Technology. OpenProceedings. org, 2016

    2016

  27. [35]

    Modeling and querying metadata in the semantic sensor web: The model stRDF and the query language stSPARQL

    Manolis Koubarakis and Kostis Kyzirakos. Modeling and querying metadata in the semantic sensor web: The model stRDF and the query language stSPARQL. InProc. Extended Semantic Web Conference, pages 425–439, 2010

    2010

  28. [36]

    Managing intervals effi- ciently in object-relational databases

    Hans-Peter Kriegel, Marco Pötke, and Thomas Seidl. Managing intervals effi- ciently in object-relational databases. InVLDB, volume 20, page 0, 2000

    2000

  29. [37]

    Temporal features in SQL: 2011.ACM Sigmod Record, 41(3):34–43, 2012

    Krishna Kulkarni and Jan-Eike Michels. Temporal features in SQL: 2011.ACM Sigmod Record, 41(3):34–43, 2012

    2011

  30. [38]

    Durable subgraph matching on tem- poral graphs.IEEE Transactions on Knowledge and Data Engineering, 35(5):4713– 4726, 2022

    Faming Li, Zhaonian Zou, and Jianzhong Li. Durable subgraph matching on tem- poral graphs.IEEE Transactions on Knowledge and Data Engineering, 35(5):4713– 4726, 2022

    2022

  31. [39]

    Temporal multi-query subgraph matching in cybersecurity.Technologies, 13(8):335, 2025

    Min Lu, Qianzhen Zhang, and Xianqiang Zhu. Temporal multi-query subgraph matching in cybersecurity.Technologies, 13(8):335, 2025

    2025

  32. [40]

    Getting the most out of Wikidata: Semantic technology usage in Wikipedia’s knowledge graph

    Stanislav Malyshev, Markus Krötzsch, Larry González, Julius Gonsior, and Adrian Bielefeldt. Getting the most out of Wikidata: Semantic technology usage in Wikipedia’s knowledge graph. InProc. 17th International Semantic Web Confer- ence (ISWC), pages 376–394, 2018

    2018

  33. [41]

    Optimizing subgraph queries by combin- ing binary and worst-case optimal joins.Proceedings of the VLDB Endowment, 12(11):1692–1704, 2019

    Amine Mhedhbi and Semih Salihoglu. Optimizing subgraph queries by combin- ing binary and worst-case optimal joins.Proceedings of the VLDB Endowment, 12(11):1692–1704, 2019

    2019

  34. [42]

    Temporal graph algebra

    Vera Zaychik Moffitt and Julia Stoyanovich. Temporal graph algebra. InProc. 16th International Symposium on Database Programming Languages, pages 1–12, 2017

    2017

  35. [43]

    Ian Munro

    J. Ian Munro. Tables. InProc. 16th Conference on Foundations of Software Tech- nology and Theoretical Computer Science (FSTTCS), pages 37–42, 1996

    1996

  36. [44]

    Hung Q. Ngo. Worst-case optimal join algorithms: Techniques, results, and open problems. InProc. 37th Symposium on Principles of Database Systems (PODS), pages 111–124, 2018

    2018

  37. [45]

    Ngo, Ely Porat, Cristopher Ré, and Atri Rudra

    Hung Q. Ngo, Ely Porat, Cristopher Ré, and Atri Rudra. Worst-case optimal join algorithms. InProc. 31st Symposium on Principles of Database Systems (PODS), pages 37–48, 2012

    2012

  38. [46]

    Motifs in temporal networks

    Ashwin Paranjape, Austin R Benson, and Jure Leskovec. Motifs in temporal networks. InProc. 10th ACM International Conference on Web Search and Data Mining (WSDM), pages 601–610, 2017

    2017

  39. [47]

    GLENDA: Querying RDF archives with full SPARQL

    Olivier Pelgrin, Ruben Taelman, Luis Galárraga, and Katja Hose. GLENDA: Querying RDF archives with full SPARQL. InProc. European Semantic Web Conference (ESWC), pages 75–80, 2023

    2023

  40. [48]

    SPARQL-st: Extending SPARQL to support spatiotemporal queries

    Matthew Perry, Prateek Jain, and Amit P Sheth. SPARQL-st: Extending SPARQL to support spatiotemporal queries. InGeospatial Semantics and the Semantic Web: Foundations, Algorithms, and Applications, pages 61–86. Springer, 2011

    2011

  41. [49]

    Top-𝑘 durable graph pattern queries on temporal graphs.IEEE Transactions on Knowledge and Data Engineer- ing, 31(1):181–194, 2018

    Konstantinos Semertzidis and Evaggelia Pitoura. Top-𝑘 durable graph pattern queries on temporal graphs.IEEE Transactions on Knowledge and Data Engineer- ing, 31(1):181–194, 2018

    2018

  42. [50]

    The temporal query language TQuel.ACM Transactions on Database Systems, 12(2):247–298, 1987

    Richard Snodgrass. The temporal query language TQuel.ACM Transactions on Database Systems, 12(2):247–298, 1987

    1987

  43. [51]

    Veldhuizen

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

    2014

  44. [52]

    Wikidata: a free collaborative knowl- edgebase.Commun

    Denny Vrandecic and Markus Krötzsch. Wikidata: a free collaborative knowl- edgebase.Commun. ACM, 57(10):78–85, 2014

    2014

  45. [53]

    ADOPT: Adaptively optimizing attribute orders for worst-case optimal join algorithms 13 via reinforcement learning.Proceedings of the VLDB Endowment, 16(11):2805– 2817, 2023

    Jialing Wang, Immanuel Trummer, Ahmet Kara, and Dan Olteanu. ADOPT: Adaptively optimizing attribute orders for worst-case optimal join algorithms 13 via reinforcement learning.Proceedings of the VLDB Endowment, 16(11):2805– 2817, 2023

    2023

  46. [54]

    Free Join: Unifying worst-case optimal and traditional joins.Proceedings of the ACM on Management of Data (SIGMOD), 1(2):150:1–150:23, 2023

    Yisu Remy Wang, Max Willsey, and Dan Suciu. Free Join: Unifying worst-case optimal and traditional joins.Proceedings of the ACM on Management of Data (SIGMOD), 1(2):150:1–150:23, 2023

    2023

  47. [55]

    Path problems in temporal graphs.Proceedings of the VLDB Endowment, 7(9):721–732, 2014

    Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path problems in temporal graphs.Proceedings of the VLDB Endowment, 7(9):721–732, 2014

    2014

  48. [56]

    Algorithms for acyclic database schemes

    Mihalis Yannakakis. Algorithms for acyclic database schemes. InProc. 7th International Conference on Very Large Databases (VLDB), pages 82–94, 1981

    1981

  49. [57]

    join-first

    Kaijie Zhu, George Fletcher, and Nikolay Yakovets. Leveraging temporal and topological selectivities in temporal-clique subgraph query processing. InProc. 37th IEEE International Conference on Data Engineering (ICDE), pages 672–683, 2021. 14 A ON THE EXPRESSIVE POWER OF TBGPS ...

    2021

Pith tools

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