Storing Video Scene Graphs as Relation Intervals for Corpus-Scale SPARQL

A video scene graph is a per-frame list of who is doing what to which object: "person holding cup," "person in front of sofa." When a detector produces these graphs for every frame of a video corpus, the result is enormous and highly redundant. A relation that lasts four seconds at 30 frames per second is written down 120 times, and detector flicker breaks it into fragments. We propose to store each relation once, as an interval with a start frame and an end frame. Each storage block also keeps a small summary of which relation-pairs occur in which temporal order inside it. Together these let a distributed RDF engine skip whole videos before it computes any join. RDF is the Resource Description Framework, which stores knowledge as subject–predicate–object triples. SPARQL is its query language.

The workload is corpus-level retrieval and question answering, for example "find every clip where someone holds a cup and afterwards opens a door," or the compositional programs behind AGQA questions. These queries are dominated by temporal "before/after/during" joins, not by multi-hop graph traversal. Our claim is that the real cost at this intersection comes from two sources. One is per-frame redundancy. The other is temporal-order joins that cannot be pruned with ordinary min/max column statistics. Graph partitioning is not the main cost, because videos are already natural disconnected components. If the claim holds, interval storage plus order summaries should cut stored triples by an order of magnitude and cut scanned bytes on temporal queries well beyond what time-bit identifier encodings achieve.

What exists and what is different

The closest system is DiStRDF. It packs a Hilbert-curve spatial cell and a discretized time interval into 64-bit RDF identifiers, so that Apache Parquet column files on Spark can skip non-matching chunks during the disk scan. On maritime trajectories this gave "roughly 20-25% speedup" over random encoding, and property tables ran in about 14 s versus 24 s for a single triples table. DiStRDF supplies our pushdown mechanism. It does not cover our problem: its entities are points with coordinates, and its time bits can answer "in window $[a,b]$" but not "relation A ends before relation B starts in the same video."

VGStore turns Visual Genome into RDF and adds virtual SPARQL predicates evaluated by Python middleware. It runs on static images on one machine, and its authors report that the middleware is a latency bottleneck. It motivates our work but has no time dimension.

GLENDA queries versioned RDF through snapshot-plus-delta chains. It acts as a constraint on our design. Treating every frame as a version would make delta chains thousands of entries long per video, which is why we reify relations as intervals rather than versioning the graph.

On the modeling side, Action Genome supplies the data model: spatial, attention and contact relations over time on 10,000 Charades videos. AGQA and AGQA 2.0 supply the query workload, because their questions are generated from programs over those graphs. Their findings motivate putting the symbolic step in a database rather than a network. The best AGQA model reaches 47.74% overall. In AGQA 2.0, visual input adds only 1-2% over blind baselines, and no model significantly exceeds 51% on binary questions.

RAVU builds a per-video graph memory and retrieves 5-10 frames per query. It shows that structured retrieval helps long-video QA, but it works one video at a time and has no storage layer.

The distributed RDF engines show how to avoid shuffles on static graphs:

  • SHAPE replicates $k$-hop neighborhoods. On SP2B Complex1 it was 7x faster than subject hashing.
  • Partout uses query logs to decide placement.
  • SPARQLGX splits storage into one file per predicate ("vertical partitioning") on Spark.

We reuse SPARQLGX's layout as the execution substrate. We argue that SHAPE-style replication is mostly unnecessary here, and we test that argument rather than assume it.

Core Claim

A relation episode is a node carrying (video, subject, predicate, object, start, end). Writing scene graphs this way, with a short-gap merge, should shrink dense detector output by roughly the mean episode length in frames, minus fragmentation. We further claim that a per-block Bloom filter of "precedence signatures" restores pruning power that interval min/max statistics lose. A Bloom filter is a compact probabilistic set that can say "definitely absent," and a precedence signature is a hashed triple of (relation-type A, relation-type B, Allen relation such as before or during). The query compiler extracts the signatures a query requires and skips any block whose filter rules them out.

The smoothing rule merges two episodes of the same triple separated by a gap of fewer than $g$ frames, and drops episodes shorter than $m$ frames. On ground-truth graphs we use $g=m=0$, which makes compression lossless with respect to the annotated frames. On predicted graphs, $(g,m)$ trade storage and pruning precision against answer fidelity, and we measure that trade-off directly.

Research Program

We will build the store on Spark and Parquet with SPARQLGX-style vertical partitioning, using one file per predicate. Episode identifiers carry video bits followed by start-frame bits, in the manner of DiStRDF. This layout clusters each video's episodes contiguously and in time order, so one Parquet row group covers a few videos. Each row group gets two kinds of statistics: ordinary min/max on start and end, and a precedence Bloom filter built at load time.

A compiler will translate AGQA's functional programs (filter by relation, temporal localization by before/after/while, and so on) into SPARQL over episodes. Temporal operators become interval-comparison filters. We will also derive corpus-level variants by unbinding the video variable, which turns each question into a retrieval query over the whole collection.

To obtain realistic volume, we will run an off-the-shelf video scene graph generator densely over all Charades videos. We will then scale to billions of triples by replaying perturbed copies of the corpus, with episode boundaries jittered and object identities reassigned. We will state plainly that this scaled data is synthetic and report results separately for the real and synthetic scales.

Baselines

The naive reference stores one triple per frame per relation in the same vertical-partitioning engine, with no temporal statistics beyond what Parquet records by default. This is roughly what one gets by loading detector output into SPARQLGX unchanged.

The strongest existing method is DiStRDF-style encoding applied to per-frame triples. Time-interval bits go into identifiers and window filters are pushed down. Its reported gain on its own domain is a 20-25% speedup over random encoding, and the property-table layout ran in about 14 s versus 24 s (DiStRDF). No reported result found on Lacuna for any RDF engine over video scene graphs, so we will rerun this baseline ourselves.

The third baseline is a plain Spark SQL table of intervals with standard min/max statistics, built from the same smoothed episodes and run on the same plans. It tests whether RDF or our summaries matter at all.

The fourth is per-video hash partitioning without replication, which tests whether locality-aware placement adds anything.

All systems run on the same cluster with identical executor memory and the same data. Each gets the same tuning budget: a fixed grid over row-group size and, for DiStRDF, time-bucket width, with the best setting reported. We count our method as beating a baseline if it reduces median and 95th-percentile latency and bytes scanned on temporal-order queries by at least 2x, with identical answers.

Two ablations isolate the ingredients. The first uses intervals without precedence filters. The second uses precedence filters on per-frame storage.

Why not just…?

Why not just use Spark SQL with an interval table? This is the most serious threat, and we partly concede it. Interval storage is engine-agnostic, so we run it in Spark SQL as a baseline. What Spark SQL's min/max statistics cannot express is order between two different relations inside a block. The precedence filter is the piece we expect to survive this comparison. If Spark SQL with intervals matches our full system, the contribution reduces to a representation result, and we will report it as one. The RDF layer then justifies itself only as a standard query interface and through compatibility with ontology-grounded vocabularies, as in VGStore.

Why not just partition by video and skip all the partitioning research? We expect this to be correct, which is why the proposal does not build a new partitioner. Within-video queries are already local under video hashing, so SHAPE-style $k$-hop replication (SHAPE) should buy little. The per-video hashing baseline will confirm or refute this. The remaining cost is scanning many videos for corpus-level queries, and that cost is what our pruning targets.

Why not just ask a video language model each question? For single-video QA this is a reasonable choice. For "find all clips where…" over thousands of videos, it requires a model pass over every clip, and the AGQA results above show that such models gain little from vision on compositional temporal questions. RAVU's retrieval of 5-10 frames per query (RAVU) still runs inside one video. Our store could serve as the candidate-retrieval stage for such a model, and we do not compete with it on single-video accuracy.

Proposed Experiments

The first experiment measures volume. We report triples and bytes for per-frame versus episode storage on Action Genome ground-truth graphs and on dense predicted graphs, across a sweep of $(g,m)$.

The second measures latency and bytes scanned. We test compiled AGQA programs, both per-video and corpus-level, at real scale and at synthetic 10x and 100x scale against all baselines. Queries are stratified by number of reasoning steps and by whether they contain a temporal-order operator.

The third checks correctness. On ground-truth graphs with $g=m=0$, every compiled program must return exactly the per-frame engine's answers; any mismatch is a compiler or encoding bug.

The fourth checks fidelity on predicted graphs. We measure how often answers change relative to per-frame evaluation as $(g,m)$ grow, and score both settings against AGQA labels. As context only, the best end-to-end AGQA model reaches 47.74% overall (AGQA) and HCRN reaches 36.34% on open-ended AGQA 2.0 questions (AGQA 2.0). The Action Genome gap between predicted and oracle graphs (44.3 vs 60.3 mAP) warns that perception noise, not storage, will cap accuracy.

The decisive check is the ablation on temporal-order queries. If precedence filters do not skip substantially more row groups than min/max statistics on interval data, the core pruning claim is false.