Worst-Case Optimal BGPs on Temporal Graphs
2026-07-22 • Databases
DatabasesData Structures and Algorithms
AI summaryⓘ
The authors study how to efficiently search patterns in graphs where connections have specific time periods when they are valid. They propose a way to query these temporal graphs using a flexible language that includes time constraints, and they design an index structure that uses space proportional to the graph size. This index supports fast queries that find all valid matches over time, improving upon previous methods by being worst-case optimal. Their approach also works for related temporal queries and shows good performance on real datasets.
temporal graphsbasic graph patternsworst-case optimalLeapfrog Triejoinquery evaluationtemporal validityindex structuresnapshot queriesversion queries
Authors
Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, Juan Reutter
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.