Source-linked AI summary
Concord: A Video Relational Algebra for Cross-Modal Query Optimization
Sultan Muratbek, Charisse Ivana Yeung, Chanwut Kittivorawong, Alvin Cheung
TL;DR
Semantic video queries can require costly processing of entire videos for sparse evidence. Concord uses VRA to rewrite queries across media inputs, temporal extents, and processing granularities. Its case studies report improvements in narrated event localization and cross-camera association, with the latter improving F1 without MLLM calls.
Problem
Naive semantic video-query execution sends complete, temporally redundant videos to MLLMs, incurring high cost and latency when relevant evidence is sparse.
Source: §1 · p. 1Method
Results
Detect–Track–Join improves cross-camera F1 from .364 to .813 with no MLLM calls, while transcript-to-video queries improve the cost–quality frontier for narrated event localization.
Source: §1 · p. 1Takeaways & Limitations
Concord’s experiments demonstrate the promise of optimizing semantic video queries by exposing different modalities within one algebra.
Source: §6 · p. 6Approximate rewrites may improve or degrade result quality depending on whether the changed representation omits relevant evidence or removes irrelevant context.
Source: §4 · p. 3
Abstract
from arXiv · showhide
Semantic video queries let users embed natural language prompts and use multimodal large language models (MLLMs) to interpret the video. Such queries are increasingly popular for querying video data. However, their expressiveness comes at a steep cost: an MLLM may process hours of media to return only seconds of relevant output, making naive execution slow, expensive, and inaccurate. We propose Concord, a system for expressing and optimizing semantic video queries. We makes three contributions. First, we introduce Video Relational Algebra (VRA), a nested algebra over videos, transcripts, frames, and object tracks that captures common semantic video operations. Second, we derive a set of approximate optimizations that rewrite VRA queries to reduce MLLM usage while improving result quality. For narrated video, Concord either processes transcripts instead of video or uses them to identify video clips for MLLM processing. For cross-camera queries without narration, detection and tracking replace a whole-video MLLM join with a track-level relational join. Third, we evaluate Concord on real-world videos. Across 4.59 hours of soccer broadcasts and 3.92 hours of lectures, transcript-to-video queries send only 5.32% and 2.47% of source-video duration to the MLLM and reduce MLLM cost by up to 87%. In two five-second highway clips with 18 manually adjudicated cross-camera vehicles, a Detect-Track-Join query improves F1 from .364 to .813 while making no MLLM calls. See our project at https://concord-db.github.io/.
1 Introduction
Semantic video queries can be costly when MLLMs process entire videos despite sparse relevant evidence. Concord introduces an algebra and rewrites that change the media, temporal extent, or granularity supplied to semantic operations.
1 Introduction
- Naive execution sends complete, temporally redundant videos to an MLLM, incurring high cost and latency when relevant evidence is sparse.Narration can answer a query directly or identify candidate intervals for video inference.Source: §1 · p. 1
- For cross-camera association, Concord decomposes a whole-video semantic operation into Detect–Track–Join over entity-level records.The direct alternative asks an MLLM to discover vehicles, maintain identities, and associate them across camera views.Source: §1 · p. 1
- Concord provides Video Relational Algebra (VRA) and rewrites queries to use different media inputs, temporal extents, or processing granularities.Its query API covers records containing audio, video, transcripts, source-time views, frames, detections, and tracks.Source: §1 · p. 1
- Detect–Track–Join improves cross-camera F1 from .364 to .813 with no MLLM calls, while transcript-to-video queries improve the cost–quality frontier for narrated event localization.These are the reported outcomes of Concord’s query rewrites.Source: §1 · p. 1
- Concord’s case studies motivate making modality, temporal extent, and processing granularity explicit query choices subject to event- and entity-coverage constraints.The paper identifies a missing compact algebra for composing relational operators with media-specific representations.Source: §1 · p. 1
2 Background and Related Work
Prior systems optimize video inference or declarative semantic operators, while Concord focuses on composing media-derived representations within relational queries. Its distinction is to expose aligned media representations as query-visible values and relations.
Video DBMSs and semantic query systems
- Concord makes media-derived representations composable within a relational query, enabling alternatives that change the representation, temporal extent, or record granularity supplied to semantic computation.Prior video systems optimize which models, frames, or stored results are evaluated.Source: §2 · pp. 1–2
Declarative video and multimodal queries
- VRA represents aligned transcripts, temporal clips, detections, and tracks as query-visible values and relations that preserve source identity and time.VIVA instead uses relational hints to specify when one registered model may replace or filter another, including transcript search as a filter for visual recognition.Source: §2 · p. 2
Multimodal systems
- Concord focuses on algebraic rewrites that exchange or compose source-aligned media representations while preserving the query’s output schema.Other multimodal systems provide interfaces for natural-language predicates, query generation, unified multimodal relations, or semantic operators over unstructured data.Source: §2 · p. 2
3 Concord and Video Relational Algebra
Concord expresses semantic video workflows as VRA queries over relations and media-valued records. VRA provides operators and source-aligned representations for composing transformations at different granularities.
3 Concord and Video Relational Algebra
- Concord queries compose VRA operators, and rewrites may change input modality, temporal extent, or processing granularity while preserving query intent and output schema.Relational operators act on relations whose tuples may contain ordinary and media-valued attributes.Source: §3 · p. 2, §3.2 · p. 2
3.1 Media Data Model
- VRA relations can represent media as complete videos, clips, frames, detections, or tracks, with operators transforming both tuple values and processing granularity.Derived values retain source identity and source-time intervals, allowing results to be regrouped by source and mapped to the original timeline.Source: §3.1 · p. 2
3.2 VRA Operators
- Media operators apply tuple-wise, store results in designated attributes, and preserve other attributes; semantic functions pair natural-language instructions with structured output schemas and may invoke an MLLM.VRA also includes deterministic functions and relational operators such as Map, Filter, Reduce, Unnest, and Join.Source: §3.2 · p. 2
3.3 Example Queries
- The example queries cover soccer-goal localization, lecture-event localization requiring co-occurring audible and visible evidence, and cross-camera vehicle association.The cross-camera query returns structured association records that downstream relational operators can filter, group, join, and process.Source: §3.3 · pp. 2–3
4 Optimizing VRA Queries
VRA makes modality, temporal extent, and intermediate-record granularity explicit query choices. Concord uses approximate rewrites across these dimensions, preserving output schemas while potentially changing result quality.
4.1 O1: Modality Substitution
- O1 substitutes a schema-compatible function over another representation from the same source when it is cheaper and contains sufficient task evidence.For event localization, Concord uses transcripts instead of video; the rewrite also applies to classification, extraction, and summarization.Source: §4.1 · p. 3
4.2 O2: Cross-Modal Temporal Candidate Pushdown
- O2 uses source-aligned evidence to identify candidate intervals, processes materialized video clips, and reconciles their results by source video.It is suited to results with bounded temporal witnesses that can be reconciled; it does not apply when an answer depends on the entire video, such as whether an event never occurs.Source: §4.2 · p. 4
4.3 O3: Semantic Reduce–Unnest to Detect–Track–Join
- O3 decomposes whole-video association into explicit detection, tracking, candidate-matching, conflict-resolution, and trajectory-construction relations, eliminating MLLM calls.Its quality depends on entity coverage and on correct matches surviving candidate pruning and one-to-one resolution.Source: §4.3 · pp. 4–5
5 Evaluation
Concord is evaluated through transcript-assisted event localization and track-level cross-camera association on soccer, lecture, and highway videos. The results show lower MLLM use and improved localization and association quality, with a latency trade-off on the short highway sample.
5 Evaluation
- Evaluation used frozen prompts on three real-world workloads, excluded offline transcript construction from cold-start runtime, and scored event localization at stated timing thresholds.The datasets were soccer matches, lectures, and synchronized highway camera feeds.Source: §5 · p. 5, §5.1 · p. 5, §5.2 · p. 5
5.1 Soccer Goal Localization
- At 30-second tolerance, transcript-to-video raised F1 from .818 to .952 while reducing estimated MLLM cost by 85.0%; 13 windows covered all ten goals using 5.32% of source duration.The transcript-only query also reached .952 F1, but had less precise timestamps than transcript-to-video.Source: §5.1 · p. 5
5.2 Lecture Event Localization
- At tIoU ≥.3, transcript-to-video raised F1 from .500 to .889 and cut estimated MLLM cost by 87.2%, using 2.47% of source duration with full event coverage.The three candidate windows fully covered all four reference events.Source: §5.2 · p. 5
- Transcript-only lecture localization reached .286 F1 at the primary threshold because transcript evidence can identify broad discussion neighborhoods without precise visual boundaries or distinct occurrences.Video refinement improves temporal localization rather than merely detecting event presence; one soap-bubble prediction spanned about 57 seconds across two six-second events.Source: §5.2 · pp. 5–6
5.3 Cross-Camera Vehicle Trajectories
- On two five-second highway clips, Detect–Track–Join matched 13 of 18 vehicles and raised F1 from .364 to .813 (mean timeline IoU .576 to .762), but ran slower (99.6 s vs. 52.7 s).It eliminates MLLM calls by replacing whole-clip inference with explicit Detect, Track, and Join operators.Source: §5.3 · p. 6, Table 3 · p. 6
6 Conclusion
VRA exposes multiple video modalities in one algebra, letting users express queries and Concord optimize them. Experiments show the optimizations can reduce cost and execution time while improving accuracy.
6 Conclusion
- Concord combines multimodal video query processing with VRA, which supports query expression and optimization across video inputs.Experiments show its optimizations can reduce cost and query execution time while improving accuracy.Source: §6 · p. 6