Video data is increasingly becoming a prized commodity. Inexpensive large-scale video storage and advances in machine learning and computer vision have propelled the use of large video datasets with new applications including drone analytics [75,77], citywide traffic analytics [2,26], civil engineering [4,25], and many others [24,52,58,67,69]. Although video database management systems (VDBMSs) have recently re-emerged as an active research area to support these applications [3,5,17,23,39,40,49], existing systems fall short of supporting many use cases. ○ a video dataset, 2 ○ user-defined functions that extract semantic information from videos, and 3 ○ a few user-provided labels, EQUI-VOCAL synthesizes a query to find instances of an event of interest. It iteratively 4 ○ asks the user for more labels to reduce its uncertainty. Once synthesized, it 5 ○ executes the query to return matching events on unseen videos.
Consider a traffic analytics application: A traffic engineer may want to understand road hazards involving car and motorcycle interactions (e.g., motorcycles swerving abruptly in front of turning cars). Although many computer vision models exist that detect common objects (e.g., "cars" and "motorcycles") [78] and relate objects spatially (e.g., "bottom of", "left of", "near") [12], a specific classifier that identifies "a motorcycle swerving in front of a car, while the car is turning at an intersection" is unlikely to exist [80,82]. Worse, training one would require many hours of user effort in labeling for a single query. Given the relative rarity of most interesting events, finding sufficient positive instances further exacerbates these labeling requirements. In our example, there will be many instances of cars and motorcycles in intersections. Only rarely would a motorcycle swerve in front of a turning car.
Assuming that we can run existing computer vision models on videos to identify objects, extract attributes, and reason about their pairwise relationships, some recent video data management systems support users by providing an interface to express a declarative query as a composition of extracted information [7,11,14,23,49,54,80]. For example, a user might be able to query for an event using a specification that searches for video clips containing car and motorcycle objects, and specifying their desired relationships (near then front_of, etc.). These systems expect users to possess a level of database expertise to be able to express such queries. Additionally, real-world events can be difficult to express declaratively-even for experts. For example, there are multiple ways to express our sample query. The best way depends on the data (e.g., in a given video, motorcycles may be swerving from outside the frame, as illustrated in Figure 2, discussed later). Other similar systems ask users to sketch their events [10,14]; this is equally challenging for the same reason: an event of interest may deviate from the exact user-provided sketch.
In this paper, we present EQUI-VOCAL (Figure 1), a system that addresses the above challenge by synthesizing declarative queries on behalf of users from a small number of labeled video segments. Put another way, EQUI-VOCAL Evolves Queries for Users Iteratively and is part of our larger VOCAL system [19]. In our example, a user provides as few as two positive and ten negative examples containing the event of interest (see Section 5). EQUI-VOCAL then synthesizes a declarative query and executes it on the remaining large pool of video data to identify other examples of the desired event.
EQUI-VOCAL supports users' search for complex events without requiring any specific domain knowledge, with limited effort, and without requiring precise declarative specifications or sketches. Similar to other systems, we use the insight that while most user queries are new and unseen, they are usually composed of known, previously seen atoms. Computer vision models for common atoms already exist such as objects (e.g., "car", "backpack") and their spatial and semantic relationships (e.g., "left of", "holding"). Formally, such a composition of visual scenes is referred to as a scene graph in the computer vision community [35,43] and was developed from its cognitive grounding in human perception [8,46,83]. Key to EQUI-VOCAL's contribution is to encapsulate spatio-temporal scene graphs in its data model and use them to define a query language. A spatio-temporal scene graph conceptualizes the contents of a video as a sequence of graphs, each graph representing a single video frame. Each graph contains vertices, which represent objects in the frame; edges represent the relationships between those objects. Each object can possess a set of attributes that describe its properties (e.g., "red", "leather"). EQUI-VOCAL extracts relevant data from each video using user-provided functions: i.e., pre-existing detectors and classifiers; it synthesizes queries as a composition of extracted scene graph atoms. We show that EQUI-VOCAL's data model and query language, both based on the relational model, can express a variety of compositional queries.
Leveraging scene graphs, EQUI-VOCAL contributes a new query synthesis approach that finds user events with far fewer labeled examples than would be required to train a specialized machine learning model directly, and that works on noisy, video-scale data, and complex events. To support query synthesis in such environment, EQUI-VOCAL solves two technical challenges: it reduces computational effort and user effort.
EQUI-VOCAL reduces computational effort by limiting query search using scene graphs, by pruning search paths using beam search, and by avoiding expensive database operations. First, unlike prior query-by-example techniques that synthesize arbitrary SQL [22,48,59,70,73], EQUI-VOCAL reduces the search space by limiting the query search to sequences of scene graphs. Second, synthesizing queries over sequences of scene graphs can still be a computationally slow process to traverse the search space of possible queries. Existing query-by-example systems enumerate all possible queries; although pruning techniques like equivalence classes [71], over-approximation [73], and lifting projection operators [70] can be used to reduce the search space, these mechanisms are not sufficient to make exhaustive exploration tractable. Instead, EQUI-VOCAL adopts a beam search strategy to explore the query space efficiently. Beam search limits exploration to a subset of the most promising branches at each step. Third, executing the many candidate queries on the user examples is prohibitively expensive. Existing systems [70,73] evaluate candidate queries with many joins and thus do not scale well when the size of user examples becomes large. EQUI-VOCAL carefully generates efficient queries that avoid expensive operations such as recursive joins. EQUI-VOCAL comes with a set of optimizations to generate efficient SQL statements and uses the PostgreSQL database engine to execute them.
EQUI-VOCAL reduces user effort by using active learning and by being robust to noise. With active learning, EQUI-VOCAL reduces the number of labeled examples needed: Instead of asking a user to provide all examples up front, EQUI-VOCAL iteratively requests labels of carefully selected additional examples to reduce the uncertainty in query synthesis. Noise can naturally creep into systems that interface with user labeling, machine learning models, and potentially ambiguous real-world events. Distinct from other existing systems [54,70], EQUI-VOCAL searches for queries that best match potentially noisy data and input. It also retains imperfect query candidates at every iteration and uses regularization to prevent overfitting to noise or limited user input.
We evaluate our approach on synthetic and real datasets [5,81] and show that it outperforms two baselines [54,70]-in terms of F1 score, synthesis time, and robustness to data noise-and can flexibly synthesize complex queries that the baselines do not support. We also conduct a user study to show the performance of real users using EQUI-VOCAL.
Overall, EQUI-VOCAL is an important step toward making video database management systems more accessible to experts and nonexperts alike, by easing the task of expressing queries over videos.
This section describes EQUI-VOCAL's data model and query language, which we briefly introduced in our vision paper [19], but develop in depth here. Section 3 shows how EQUI-VOCAL synthesizes queries from user input using this data model.
For ease of presentation, we use a simplified, running example, where a traffic engineer seeks to find instances of "a car arriving from the left and passing a motorcycle at the intersection. " Figure 2 shows two representative frames from a video that contains such an event. We show other example queries in Section 5.
EQUI-VOCAL represents a video 𝑉 as a set of short, nonoverlapping video segments, 𝑣 ∈ 𝑉 (5-second segments in our prototype implementation). Each video segment is a sequence of 𝑁 frames {𝑓 1 , . . . , 𝑓 𝑁 }. The visual content of each frame is represented by a scene graph [43]: A scene graph 𝑔 𝑖 = (o 𝑖 , r 𝑖 ) contains the set of all objects o 𝑖 in a frame, along with a set of all relationships r 𝑖 between those objects. Often a scene graph contains more information than is necessary to identify an event, and so the literature also defines a region graph 𝑔 𝑖 𝑗 , which is a subgraph of 𝑔 𝑖 , i.e., 𝑔 𝑖 𝑗 ⊆ 𝑔 𝑖 . Figure 2 (left) shows an example frame and region graph.
We define an object in a frame as 𝑜 = (𝑣𝑖𝑑, 𝑓 𝑖 , 𝑜𝑖𝑑, 𝑐𝑖𝑑, 𝑏𝑏𝑜𝑥), where 𝑓 𝑖 is the sequence number of frame 𝑖 in video segment, 𝑣𝑖𝑑. 𝑜𝑖𝑑 is a unique identifier of the object in the video segment, 𝑐𝑖𝑑 is the identifier for the class of the object (e.g., "car", "motorcycle"), and 𝑏𝑏𝑜𝑥 is the bounding box containing the object in frame, 𝑓 𝑖 . A 𝑏𝑏𝑜𝑥 is represented by its upper-left and bottom-right coordinates, i.e., 𝑏𝑏𝑜𝑥 = (𝑥 1 , 𝑦 1 , 𝑥 2 , 𝑦 2 ).
Objects can have intra-frame relationships defined as 𝑟 = (𝑣𝑖𝑑, 𝑓 𝑖 , 𝑟𝑖𝑑, 𝑜𝑖𝑑 sub , 𝑝𝑖𝑑, 𝑜𝑖𝑑 tar ), where 𝑟𝑖𝑑 is a unique identifier of the relationship in frame, 𝑓 𝑖 . Subject, 𝑜 sub , is connected to target, 𝑜 tar , with the relationship class identifier, 𝑝𝑖𝑑 (e.g., "near" or "holds"). Both subject and target belong to frame 𝑓 𝑖 : i.e., 𝑜 sub , 𝑜 tar ∈ o 𝑖 .
Objects can have attributes 𝑎 = (𝑣𝑖𝑑, 𝑓 𝑖 , 𝑜𝑖𝑑, 𝑘, 𝑣), where 𝑘 is the name of the attribute, 𝑣 is the value of the attribute, 𝑣𝑖𝑑, 𝑓 𝑖 and 𝑜𝑖𝑑 identify the video segment, frame, and object. EQUI-VOCAL distinguishes state and property attributes. The former change over time and are typically computed from the bounding box of an object (e.g., "location=bottom"). The latter capture intrinsic properties of objects and are immutable (e.g., "color=red").
Finally, an event 𝑒 is a temporally ordered sequence of region graphs 𝑒 = (𝑒𝑖𝑑, {𝑔 1 , . . . , 𝑔 𝑘 }). Region graphs in an event do not need to be contiguous or distinct.
Example. Suppose that the two frames in Figure 2 are the 10th and 15th frames of a video segment V1, and that the motorcycle and car are the 7th and 9th objects detected in V1. Then, for the left frame, we generate the region graph 𝑔 1 = (o 1 , r 1 ), where: o 1 = {𝑜 11 , 𝑜 12 } represents the car 𝑜 11 = (V1, F10, OID9, car, 𝑏𝑏𝑜𝑥 1 ) and the motorcycle 𝑜 12 = (V1, F10, OID7, motorcycle, 𝑏𝑏𝑜𝑥 2 ) and r 1 = {𝑟 11 } contains a relationship 𝑟 11 = (V1, F10, RID1, OID9, leftOf, OID7). The car also has an attribute 𝑎 11 = (V1, F10, OID9, location, bottom). We can define the region graph 𝑔 2 for the right frame similarly. The only difference will be the relationship between the object will indicate that the car is now rightOf the motorcycle. Finally, the event 𝑒 = (EID1, {𝑔 1 , 𝑔 2 }) represents a car arriving from the left and passing a motorcycle at the intersection.
The relational schema in Table 1 captures the above data model. The benefit of using a relational schema is that we can execute relational queries to specify region graphs and find events of interest, which is flexible and follows the well-understood semantics of the relational model. For each video (or collection of related videos), EQUI-VOCAL creates a view with this schema. In Section 4 we describe when and how relations in the view are materialized. To populate each relation, EQUI-VOCAL uses available userdefined functions (Figure 1). User-defined functions can be provided by the user or be available publicly in the form of existing machine learning models, such as object detectors. Various user-defined functions can be declared in EQUI-VOCAL: (i) an object detector [62] that takes a video frame as input and outputs the set of objects and their bounding boxes, (ii) an object tracking algorithm [78] that takes objects in consecutive frames as input and, for each pair of objects, determines if they are the same, and (iii) a set of pretrained models (e.g., [12]) or rules that can take two objects in the same frame as input and determine their relationship (e.g., "near", "behind", "riding", "holding") or that can take one object as input and determine its attributes (e.g., "location=bottom", "color=red").
In our experiments, EQUI-VOCAL uses a general-purpose object detector [31] to locate objects and intrinsic attributes of objects to generate trajectories across frames [81].
EQUI-VOCAL could execute arbitrary relational queries on the view defined above. However, this would form an intractable search space, making query synthesis unusably slow for most real-world applications. Instead, we define a query language that is more restrictive, affording a smaller search space and therefore, faster synthesis. We constrain queries to (i) a temporally ordered sequence of region graphs, (ii) a set of predicates, (iii) a set of duration constraints, (iv) a window specification, and (v) to output video segment identifiers. Using Datalog and with some abuse of notation, a query in EQUI-VOCAL can be expressed as: 𝑞(𝑣𝑖𝑑) :-𝑔 1 , . . . , 𝑔 𝑘 , p, d, 𝑤, where:
• A temporally ordered sequence of region graphs 𝑔 1 , . . . , 𝑔 𝑘 specifies that a matching event consists of 𝑔 1 , followed by 𝑔 2 , followed by 𝑔 3 , etc. Each 𝑔 𝑖 is specified with a set of atoms: Objects, Relationships, and Attributes joined on a shared 𝑣𝑖𝑑 and 𝑓 𝑖𝑑. Moreover, each 𝑔 𝑖 can persist for multiple frames and there can be other frames between 𝑔 𝑖 and 𝑔 𝑖+1 . • A set of predicates p can be applied to objects, relationships, and attributes. In our example, predicates would specify that the query is looking for "car" and "motorcycle" objects, that the car needs to be "left of" then "right of" the motorcycle, and that the car should be at the "bottom" of the frame. • A set of duration constraints d can be applied to region graphs and define the minimum number of contiguous frames that a region graph 𝑔 𝑖 should be valid before transitioning to the next region graph 𝑔 𝑖+1 . • A window specification 𝑤 is the maximum number of frames that can separate 𝑔 1 from 𝑔 𝑘 .
For example, following the above restricted template, the event in Section 2.1 can be expressed with the following Datalog rules:foot_0 Caesar [49] STAR [14] VidCEP [80] CVQL [45] Quivr [54] Rekall [23] Ours
Query by example ✓ ✓ g1(vid, fid, oid1, oid2) :-Objects(vid, fid, oid1, 'car', _, _, _, _), Objects(vid, fid, oid2, 'motorcycle', _, _, _, _), Relationships(vid, fid, _, oid1, 'leftOf', oid2), Attributes(vid, fid, oid1, 'location', 'bottom'), oid1 != oid2.
The above rule will find frames in video segments that contain a car and a motorcycle, such that the car is on the left of the motorcycle, and the car is at the bottom of the frame, where the intersection is located. Next, the event will likely consist of a sequence of such frames, which can be captured with the following recursive rules: g1_star(vid, fid, fid, oid1, oid2) :-g1(vid, fid, oid1, oid2). g1_star(vid, fid_start, fid_end, oid1, oid2) :-g1_star(vid, fid_start, fid, oid1, oid2), g1(vid, fid_end, oid1, oid2), fid_end = fid + 1.
We could use equivalent rules to define g2 and g2_star. Finally, the query that returns matching video segments takes the form: q(vid) :-g1_star(vid, fid11, fid12, oid1, oid2), g2_star(vid, fid21, fid22, oid1, oid2), fid21 > fid12, fid22 -fid11 < 1800
The predicate 𝑓 𝑖𝑑21 > 𝑓 𝑖𝑑12 indicates that the second sequence of region graphs should follow the first one. The predicate allows for a gap between sequences, which may arise, for example, if something obstructs the vehicles from the camera's view. Finally, 𝑓 𝑖𝑑22 -𝑓 𝑖𝑑11 < 1800 puts a time constraint on the event (a 30second time-window, assuming 60 frames per second).
To summarize, EQUI-VOCAL's query language is a subset of Datalog with recursion, expressed on a specific schema. In Section 4, we explain how we avoid executing expensive recursive queries.
We compare the expressiveness of EQUI-VOCAL's data model against other compositional video analytics systems in Table 2. Among them, SVQ++ [11] only supports spatial relationships between two objects, Chen et al. [16] only supports temporal queries that count co-occurring objects. Caesar [49], STAR Retrieval [14], and VidCEP [80] lack the important feature of iteration that allows a region graph to persist for multiple frames and thus cannot support duration constraints. CVQL [45] does not track objects and all its predicates are defined at the object class level. Quivr [54] has similar expressiveness to us, but is limited to trajectory queries. Rekall [23] introduces a flexible Python library for video event specification, but requires that users manually write and refine queries.
Our data model currently does not support tertiary relationships between three objects, such as "a person hitting a ball with a bat". The closest approximation we have is "a person holding a bat" and "a bat hitting a ball". We also do not support disjunctions or negations. Several existing systems have support for these operators.
For example, Chen et al. [16] supports arbitrary CNF queries, Caesar [49] supports disjunctions, and Rekall [23] can flexibly support all three operators. However, the focus of these systems lies in query execution, rather than in learning query specifications from examples, which is the primary focus of this paper.
Datalog and scene graphs serve as the foundation of our query language. By building on the relational model and Datalog, we ensure that our queries have precise and well-understood semantics. By focusing on queries that specify a desired sequence of region graphs, we constrain the search space for queries, which accelerates synthesis, we are able to optimize the execution of those queries (compared with trying to support arbitrary recursive Datalog queries), and we are still able to capture events that occur in videos, where objects interact with each other in space and time.
With our data model and query language defined, we now formally present the query synthesis problem statement, then describe all the components of our proposed solution.
Following the aforementioned data model, a user would like to execute a query 𝑞 𝑢 on video database 𝐷 that returns a set of video segment identifiers, 𝑉 𝑜𝑢𝑡𝑝𝑢𝑡 = 𝑞 𝑢 (𝐷). Given the user's intended query, 𝑞 𝑢 , each video segment 𝑣 𝑖 can be seen as having a groundtruth label 𝑦 𝑖 ∈ {0, 1} indicating whether it matches 𝑞 𝑢 . Initially, both the ground-truth labels and 𝑞 𝑢 are unknown because the user is unable to specify 𝑞 𝑢 and can only label video segments as positive or negative instances. The goal of EQUI-VOCAL is to synthesize a target query, 𝑞 𝑡 ∈ 𝑄, that is the best approximation of 𝑞 𝑢 in its search space. When executed over database 𝐷, 𝑞 𝑡 should yield the best measure performance (e.g., F1 score):
EQUI-VOCAL can request a label from the user 𝑂: 𝑦 𝑖 ˆ= 𝑂 (𝑣 𝑖 ). Since user labels may be noisy, it is possible that 𝑦 𝑖 ˆ≠ 𝑦 𝑖 . Given that enumerative search is intractable, EQUI-VOCAL uses a heuristic approach to find an approximately-best query 𝑞 ˆ𝑡 to the objective, while reducing both user effort and query synthesis time.
Algorithm 1 provides an overview of EQUI-VOCAL's synthesis algorithm. It traverses the space of possible queries to synthesize a final target query that matches the user's intent. The algorithm takes as input the set of unlabeled video segments, 𝑈 , and a small set of labeled segments, 𝐿. 𝐿 is provided by the user and should include both positive and negative examples of the desired event.
In our experiments, we require as few as two positive and ten negative examples. While providing these examples requires extra work from the user, such a setting is common in query-by-example approaches [22,54,61]. We leave starting with zero examples for future work. The algorithm also takes as input a set of user-defined functions, 𝑃, comprised of indicator functions for object classes (e.g., "car"), relationships (e.g., "near"), and attribute key-value pairs Algorithm 1: Query synthesis algorithm that returns top-𝑘 synthesized queries matching user input.
Input :𝑈 -set of unlabeled video segments 𝐿 -set of labeled video segments 𝑃 -set of user-defined functions 𝑏, 𝑏𝑤, 𝑠 𝑞 , 𝑠 𝑣 , 𝑘 -hyperparameters Output :𝑄 𝑡 -set of top-𝑘 target queries
11 return 𝑄 𝑡 (e.g., "color=red"). Algorithm 1 enumerates 𝑃 when expanding its search space.
The algorithm returns a set of target queries, 𝑄 𝑡 , which is the top-𝑘 synthesized queries ranked by a performance measure (F1 score in our prototype implementation) and is updated regularly through the search process. The learned queries can be applied to unseen videos to find video segments containing the matching event. By default, EQUI-VOCAL returns the top-𝑘 queries but then executes the best one over unseen videos. The user can also randomly sample one query from 𝑄 𝑡 , execute multiple queries from 𝑄 𝑡 and aggregate the results, or manually examine 𝑄 𝑡 to pick the intended query. If the user is not satisfied with the synthesized query, they can edit it directly. The user can also restart the search with a larger number of initial examples by reusing the video segments labeled during the last session. Moreover, the user could provide a starter query to EQUI-VOCAL (e.g., a simple query or an earlier query) rather than starting from an empty query.
To populate 𝑄 𝑡 efficiently, EQUI-VOCAL synthesizes queries in a bottom-up fashion. It starts with an empty query, 𝑞 ∅ , and incrementally adds predicates to it, up to a certain complexity (ExpandQuery method on line 5 and Section 3.3). At each step, different predicates can be added to a query, expanding the search in multiple directions. To limit the size of the search space and ensure fast query synthesis, EQUI-VOCAL adopts a beam searchstyle strategy (SampleQueries method on line 8 and Section 3.4).
An important challenge for EQUI-VOCAL is that learning a query from a small number of user-provided examples is difficult.
To address this challenge, EQUI-VOCAL uses active learning to effectively guide the query synthesis process and identify good target queries with limited initial and additional user effort. Specifically, method PickNextSegments on line 7 and in Section 3.5 uses active learning to select additional video segments for the user to label in order to effectively differentiate between multiple candidate subqueries, and expand the search in the most promising directions.
At the end of each iteration, method RetainTopQueries (line 10 and Section 3.6) maintains a list of top-𝑘 queries seen so far, which is larger than the number of queries selected for additional expansion, in case a query seen earlier in the search ends up with the best score on the final labeled set of segments, or, as mentioned above, to give users options if they would like to try alternative, high-performing queries.
The algorithm has several hyperparameters, including a labeling budget 𝑏 (i.e., the maximum number of labels the user is willing to provide), the number of candidate queries to retain during exploration 𝑏𝑤 (i.e., the beam width), the number of candidate queries, 𝑠 𝑞 , and the number of candidate video segments, 𝑠 𝑣 , sampled during active learning, and the number of queries in the final answer 𝑘. Figure 3 illustrates the algorithm using the running example.
Existing query-by-example systems use sketch-based query synthesis approaches [54,70,73] to enumerate candidate queries. A sketch query is a query with unspecified parts in the form of holes and these approaches enumerate the search space by first generating high-level sketch queries and then filling them with low-level details. However, enumerative search is slow and memory-intensive. Inspired by execution-guided synthesis approaches [13,34], which treat a program as a sequence of manipulations and use the results of partial programs to guide the search, EQUI-VOCAL explores the search space based on the results of executing intermediate queries on the examples. Instead of synthesizing sketch queries with uninstantiated holes that cannot be executed directly, or directly applying techniques from [13,34], which require a large amount of data to train a neural synthesizer, EQUI-VOCAL expands queries by adding instantiated and executable constraints, executing partial queries to assess the promise of each explored path, and iteratively refining a query towards the target query.
In our synthesis algorithm, method ExpandQuery(𝑞, 𝑃) takes as input a query 𝑞 to expand, and a set of user-defined functions, 𝑃 to construct more complex queries. The function returns a set of expanded queries as illustrated in Figure 3(a).
Our query synthesis approach uses a compact query notation, which can be seen as a DSL. The DSL captures the logical structure of the queries to synthesize and key query parameters, but omits the details of the full, underlying SQL (or Datalog). This approach is important for several reasons: First, since we do not generate arbitrary SQL, but rather queries that conform to the structure presented in Section 2.2, the DSL captures that structure precisely, simplifying the search space and guiding synthesis toward the correctly-structured queries. Second, this approach helps to decouple the logical query specification from the details of the SQL queries that are ultimately executed. As we present in Section 4, critical optimizations are necesssary during the translation from our DSL to SQL to achieve efficient query execution.
In our DSL, we use a variable 𝑜 to represent an object in a query. Different variables represent objects with different 𝑜𝑖𝑑's. All predicates of a region graph are connected by commas and are represented with shorthand notations that specify only their key-value pairs (for property attributes, e.g., Color(𝑜 1 , 'cyan')), value (for state attributes, e.g., Bottom(𝑜 1 )), or class (for objects and relationships, e.g., Car(𝑜 1 )). Then, region graphs are connected in sequence with semicolons. For example, the query for the event from Section 2.1 can be represented as:
We further use the notation Duration(𝑔, 𝑑) to require that the region graph 𝑔 exist in at least 𝑑 consecutive frames. During query synthesis, EQUI-VOCAL expands queries written in our DSL. ExpandQuery takes any of the following three actions: As shown in Figure 3(a), EQUI-VOCAL starts with an empty query 𝑞 0 = 𝑞 ∅ . In iteration 1, EQUI-VOCAL takes action SC to expand 𝑞 0 . This results in 𝑞 1 to 𝑞 5 , each consisting of a single region graph with one predicate drawn from 𝑃. In iteration 2 of Figure 3(a), EQUI-VOCAL first expands 𝑞 1 = LeftOf(𝑜 1 , 𝑜 2 ). Performing action GC leads to 𝑞 6 = (LeftOf(𝑜 1 , 𝑜 2 ), Bottom(𝑜 1 )); SC leads to 𝑞 7 = LeftOf(𝑜 1 , 𝑜 2 ); Bottom(𝑜 1 ); and DR leads to 𝑞 8 = Duration(LeftOf(𝑜 1 , 𝑜 2 ), 5), assuming the granularity of Duration is 5 frames.
Deciding which actions to take to expand queries is an important design decision. We consider both a restrictive rule that constrains each query to have one construction path and a relaxed rule that allows each query to be generated through all possible permutations of actions with multiple construction paths. Our early experiments showed that the relaxed rule led to better performance. It is thus the approach that we use. Specifically, GC can add any predicates that are not already in the region graph (predicates from the same userdefined function but applied to different variables are considered as different); SC can insert a new region graph before or after any existing region graph; DR can increment the duration constraint of any existing region graph (more details in our technical report [84]).
When traversing the search space, we can greedily expand only the top query or exhaustively expand all. The former is quick to compute but may not find the target query, while the latter is optimal but comes with a prohibitive computational cost. EQUI-VOCAL uses beam search to balance query performance and synthesis efficiency. Beam search has a wide range of applications in problems with large search spaces [44,50,72]. The greedy approach can be viewed as a special case of the beam search with a beam width of one, and the exhaustive search is equivalent to having an infinitely large beam width. Beam search reduces runtime by limiting the number of explored branches at each iteration. However, the search outputs are not guaranteed to be optimal. Search quality depends on how branches are expanded, scored, and pruned. In our approach, method SampleQueries(𝑆 ′ , 𝐿, 𝑏𝑤) retains the top 𝑏𝑤 queries to expand by evaluating the F1 score of the 𝑆 ′ candidate queries on the set of labeled video segments 𝐿 (see Figure 3(c)). Prior work has analyzed the theoretical properties of beam search under certain assumptions (e.g., monotonicity of scoring functions [53], Bayes optimality of tree models under approximations [85]). While in this paper, we directly use the F1 score as the scoring function and to retain top queries, other more sophisticated scoring functions and pruning techniques can be used as alternatives [1,53,72]. We show the effectiveness of our synthesis algorithm empirically in Section 5.
One challenge with asking the user for only a handful of examples of the intended event is that we risk overfitting, but asking the user to find a larger number of initial examples is difficult. To address this challenge, we use active learning during query synthesis.
Many active learning methods have been proposed in the literature with the goal of labeling samples that maximally improve a model trained on those samples, e.g., uncertainty-based sampling [47], estimated error reduction [64], and core-set approach [66]. In our work, we use active learning to label samples that help us identify which candidate queries are better than others. To do so, we need to label samples where candidates disagree: Therefore, we use disagreement-based active learning [42]. At every iteration, EQUI-VOCAL asks the user for a handful of additional labels to differentiate between the 𝑏𝑤 queries retained from the previous iteration. Intuitively, this method picks the video segments where the retained queries disagree the most. A similar idea appears in the query-by-committee algorithm [68] and has been used in other program synthesis systems [36,54]. EQUI-VOCAL's contribution is to incorporate active learning in each iteration of the search process, ensuring an interaction-level labeling experience. Using active learning reduces the number of data points a user has to provide; additionally, we posit that it is easier for users to label system-selected examples than to come up with their own.
During each call to PickNextSegments(𝐿, 𝑈 , 𝑆 ′ ), EQUI-VOCAL computes a score for a sample of unlabeled video segments 𝑈 over the candidate queries 𝑆 ′ and then picks the video segments with the largest disagreement. The score of each sampled, unlabeled video segment is computed as the weighted disagreement between the candidate queries. The weight of each candidate query is set to its regularized performance over the labeled set 𝐿 (Section 3.7).
While the algorithm in [42] is designed for the setting where labeling candidates are streamed, EQUI-VOCAL instead maintains a pool of candidates. Therefore, for each call to PickNextSegments, EQUI-VOCAL computes the score for a sample of unlabeled video segments 𝑠 𝑣 over a sample of candidate queries 𝑠 𝑞 and then picks the best one. The function updates 𝐿 and 𝑈 given the new user labels. As shown in Figure 3(a), EQUI-VOCAL generates five candidate queries 𝑞 1 to 𝑞 5 in iteration 1. Among them, 𝑞 1 has the highest score 0.6, while 𝑞 2 and 𝑞 3 give the same second highest score 0.4. EQUI-VOCAL requests a new video segment to be labeled (Figure 3(b)), which distinguishes 𝑞 3 from 𝑞 2 (Figure 3(c)).
Before query synthesis begins, users can set the labeling budget as a hyperparameter. EQUI-VOCAL precomputes the number of iterations of query expansion it will perform and uniformly divides the labeling budget among iterations. At every iteration, EQUI-VOCAL asks for new labels only if it has a labeling budget left to do so; otherwise, it proceeds to synthesize queries without requesting new labels. EQUI-VOCAL precomputes the number of iterations by relying on the hyperparameters (Section 4) that bound the search process and the query expansion rules (Section 3.3), which increments the complexity of synthesized queries in each iteration.
At the end of each iteration, EQUI-VOCAL updates its list of candidate final queries in order to retain 𝑘 best performing ones, as measured by their F1 scores on the labeled dataset. RetainTopQueries(𝑄 𝑡 , 𝐿, 𝑘) evaluates all candidate queries 𝑄 𝑡 on labeled set 𝐿 and returns the top 𝑘. In Figure 3(d), at the end of iteration 1, EQUI-VOCAL stores 𝑞 1 in 𝑄 𝑡 because 𝑘=1, and 𝑞 1 has the highest score. When the algorithm terminates, EQUI-VOCAL returns 𝑞 𝑖 as the final query. In our evaluation, we set the default value of 𝑘 to 100 (and to 1000 for a more complex dataset), which ensures both low overhead and high-performing final queries.
EQUI-VOCAL retains top queries using their F1 scores on the smaller 𝐿 labeled set. This can lead to overfitting since there are likely too few training examples to accurately evaluate each candidate query. To prevent overfitting, we regularize the score of each candidate query by adding the term: 𝑠𝑐𝑜𝑟𝑒 reg (𝑞) = 𝑠𝑐𝑜𝑟𝑒 (𝑞)-𝜆•𝑅(𝑞), where 𝜆 controls the importance of the regularization term. 𝑅(𝑞) represents the complexity of the query 𝑞: 𝑅
. Here, 𝑘 is the number of region graphs in 𝑞, 𝑛 𝑝𝑖 is the number of predicates in the 𝑖th region graph 𝑔 𝑖 , and 𝑛 𝑑𝑖 denotes the scale of the duration constraint of 𝑔 𝑖 . 𝛼 1 , 𝛼 2 , and 𝛼 3 are hyperparameters that control the importance of each term.
As discussed in Section 3.3, we convert queries in our DSL into SQL and use a relational engine (PostgreSQL in our prototype) to execute them. In this section, we discuss important optimizations that we apply during this translation process. Query translation algorithm. In Section 2.2, we show that queries over videos are naturally recursive. Such queries, however, are slow to execute. To avoid recursion, we leverage the observation that those queries express the idea of iteratively matching a region graph in a contiguous sequence of frames, rather than arbitrary recursion. Therefore, we can express them using window functions instead of recursion. As a second optimization, we note that a query 𝑞 in our DSL (Section 3.3) takes as input a set of video segments 𝑉 and returns all segments in 𝑉 containing at least one event that matches 𝑞. Therefore, instead of finding all satisfying events for each video segment, the query execution needs to find only one. We leverage this observation to reduce intermediate result sizes by producing SQL that efficiently computes the earliest matching sequences for each region graph specification. This optimization applies to queries without window specifications and whose duration constraints are of the form ">" or ">=", which are the only types of queries that EQUI-VOCAL currently generates. Caching. We implement an application-level cache to reuse subquery results. EQUI-VOCAL generates SQL queries as described above to find matching region graphs in the sequence specified by the DSL query one by one. We cache the intermediate results of all prefixes on the set of video segments to allow other queries sharing the same sub-queries to reuse the results. For example, when executing the query 𝑞 = 𝑔 1 ; 𝑔 2 ; 𝑔 3 on video segments 𝑣 1 and 𝑣 2 , we cache the results of 𝑞 1 = 𝑔 1 , 𝑞 2 = 𝑔 1 ; 𝑔 2 , and 𝑞 3 = 𝑔 1 ; 𝑔 2 ; 𝑔 3 on 𝑣 1 and 𝑣 2 . Later, if a query 𝑞 ′ = 𝑔 1 ; 𝑔 2 ; 𝑔 4 is executed on 𝑣 1 and 𝑣 3 , EQUI-VOCAL will reuse the cached results of 𝑞 2 = 𝑔 1 ; 𝑔 2 on 𝑣 1 . Bounding the search space. EQUI-VOCAL synthesizes queries up to a certain maximum size to ensure that the synthesis algorithm eventually terminates. Assume the number of user-defined functions for object classes and attributes is 𝑚 1 and the number of user-defined functions for relationships is 𝑚 2 . We bound the query search space using a set of hyperparameters: the maximum number of region graphs (𝑛 𝑔 ) in a query, the maximum number of predicates (𝑛 𝑝 ) in the query, the number of possible values a duration constraint can take (𝑛 𝑑 ), and the number of unique objects allowed in a query (𝑛 𝑣 ). The size of the search space is then
). Predicate evaluation. The current implementation of EQUI-VOCAL populates the Objects relation and the property attributes in the Attributes relation before query synthesis (see Table 1), by executing ML models on all video frames. The Relationships relation and the state attributes in the Attributes relation are computed lazily during query execution since they do not require ML models in our prototype, and are thus inexpensive to compute. In general, optimizing what information is computed before query synthesis and what is computed lazily is not the focus of this paper.
To simplify SQL query generation, we implement all predicates (except for join predicates) in EQUI-VOCAL as user-defined functions that take attributes and bounding box coordinates as input and return boolean values. In our prototype, we use PostgreSQL and implement user-defined functions for state and relationship predicates that operate on bounding boxes, and for property predicates that operate on key-value pairs.
While EQUI-VOCAL provides the above user-defined functions, the user can also provide additional user-defined functions incrementally as they use the system, and they can be shared and reused across queries and users [76]. In practice, EQUI-VOCAL has to limit the number of user-defined functions to a reasonable amount to ensure the efficiency of query synthesis. Two objects are far apart for at least 5 frames, then they move close, then they are far again. 5.6% TQ2D Duration(LeftOf(𝑜 1 , 𝑜 2 ), 5); (Near(𝑜 1 , 𝑜 2 ), Top(𝑜 1 ));
Duration(RightOf(𝑜 1 , 𝑜 2 ), 5)
𝑜 1 is on the left of 𝑜 2 for at least 5 frames, then they move close to each other and 𝑜 1 is at the top, then 𝑜 1 is on the right of 𝑜 2 for at least 5 frames.
TQ3D Duration( (Frontof(𝑜 1 , 𝑜 2 ), Left(𝑜 1 )), 15);
𝑜 1 is in front of 𝑜 2 while 𝑜 1 is on the left for at least 15 frames, then 𝑜 1 moves to the right of 𝑜 2 while 𝑜 1 is at the top left for at least 5 frames.
We conduct an experimental evaluation of EQUI-VOCAL. First, we show that on both synthetic and real-world datasets, compared to existing systems, EQUI-VOCAL reduces the query synthesis time by 1-2 orders of magnitude, achieves comparable or better F1 scores under the same labeling budget, is more robust to noisy data, and explores and executes queries more efficiently. Second, we show that EQUI-VOCAL is capable of synthesizing more complex, flexible queries over arbitrary scene graphs, which existing systems cannot handle. Third, We conduct a user study to demonstrate the effectiveness and usability of EQUI-VOCAL. We further compare EQUI-VOCAL with a machine learning method and conduct an ablation study by varying the various design choices outlined earlier.
We defer the details of the ablation study to the technical report [84]. Baselines. To the best of our knowledge, there are no existing systems that can synthesize queries over scene graphs. The most similar system to EQUI-VOCAL is Quivr [54], which synthesizes queries over trajectories. Since object trajectories can be represented using scene graphs, we compare our system against Quivr. We also compare against PATSQL [70], which is a state-of-the-art query-by-example system for relational data. Predicates. For the synthetic dataset, we use 13 predicates in experiments: six relationship predicates (Near, Far, LeftOf, RightOf, FrontOf, and Behind), four state predicates (Left, Right, Top, Bottom), and three property predicates (Color, Material, and Shape). We consider eight colors, two materials, and three shapes. Property predicates are only used for the scene graphs dataset. For duration constraints, we consider three possible values: duration(𝑔) ≥ 5, 10, or 15 frames. Section 4 discussed how EQUI-VOCAL evaluates these predicates. For the real dataset, we use nine predicates: two relationship predicates (Faster, Near) and seven state predicates (LaneK, Stopped, HighAccel). LaneK detects whether a car is in lane K, and we identify five lanes in the video. Data. We evaluate our system on both synthetic and real-world datasets. We first evaluate on the CLEVRER dataset [81], which comprises synthetic videos of moving objects. This dataset includes a variety of geometric shapes interacting in space and time, and comes with ground truth data, facilitating testing queries with varying complexities. We create two benchmarks from this data: trajectories and scene graphs datasets. Trajectories dataset. We create a first dataset to test queries over trajectories, which baseline systems support. We extract 10,080 pairs of object trajectories that overlap in time from 500, 5-second video segments. Each trajectory pair is essentially a temporally ordered sequence of bounding box pairs 𝑏 = (𝑥 𝑎1 , 𝑦 𝑎1 , 𝑥 𝑎2 , 𝑦 𝑎2 , 𝑥 𝑏1 , 𝑦 𝑏1 , 𝑥 𝑏2 , 𝑦 𝑏2 ) representing two objects in a video segment. We manually generate a set of queries with varying complexities (Table 3). To generate ground truth labels, we run each target query on the dataset. We sample 500 trajectory pairs as training data (i.e., data used during query synthesis) and use the rest as test data (i.e., to measure the quality of synthesized queries). Scene graphs dataset. This more complex dataset contains scene graphs extracted from the CLEVRER dataset, which baseline systems do not support. We extract scene graphs from 10,000, 5-second video segments. For every frame of a video segment, we store the object track ID (𝑜𝑖𝑑), bounding box coordinates, and object attributes (shape, color, and material) of every object in the frame (the Objects and Attributes relations in Table 1). We sample 500 video segments as training data and use the rest as test data. We automatically generate three classes of queries with different complexities: easy, medium, and hard. Each generated query contains exactly three variables (i.e., three distinct objects). Easy queries have exactly three predicates on relationships and states, one property predicate, one region graph, and no duration constraints; medium queries have exactly five predicates on relationships and states, two property predicates, three region graphs, and no duration constraints; hard queries have the same complexity as medium queries but also include duration constraints with three possible values. Each class contains 40 queries. Real-world dataset. We test on a 50-minute traffic video from the YTStreams dataset [5]. The dataset comes with car trajectories, Table 5: Query synthesis time (median, in seconds) for each method to achieve at least 0.9 F1 scores. EQUI-VOCAL successfully learns all queries with at least 0.9 F1 scores and is faster than (or at least comparable to) the two baselines. (NA: not applicable, -: failed due to insufficient F1 score or timeout)
Normal TQ1 TQ2 TQ3 TQ4 TQ5 TQ6 TQ7 TQ8 TQ9 TQ1 TQ2 TQ3 TQ4 TQ5 TQ6 TQ7 TQ8 TQ9 TQ1D TQ2D TQ3D PATSQL 1.
54 -538 -4.00 1.93 552 --NA NA NA NA NA NA NA NA NA NA NA NA Quivr 10.5 5.77 27.9 94.2 13.5 4.36 47.7 16.7 -7228 7428 8185 -7839 3683 -8756 ----Ours 3.57 1.85 17.1 46.6 4.36 1.66 18.5 22.7 20.6 75.6 125 106 185 50.4 61.1 106 110 107 223 166 183
and we further extract the velocity and acceleration of each car trajectory as the object attributes, following the same procedure described in [54]. From the video, We create 72,159 pairs of overlapping car trajectories, using half of them as training data and the rest as test data. For our evaluation, We adopt 13 queries from [54], with some adjustments, including the use of a different in-lane detection method, removal of real-valued parameters from predicates, and expression of queries using scene graphs, and the introduction of additional queries with two scene graphs. These queries capture a wide range of car behaviors (Table 4).
Metrics. We report the F1 score and query synthesis time. We synthesize queries using the training set and report the F1 score of the query (or the median F1 score if there are multiple queries with the same best score on the training set) over the test set. Each experiment is run 20 times for the trajectories and real-world datasets and five times for the scene graphs dataset, and we report the median F1 score and query synthesis time over these runs. Implementation details. We implement our prototype in Python with PostgreSQL as the backend. We conduct all experiments except for the user study on a computing cluster with Intel Xeon Gold 6230R CPUs at 2.10GHz. When measuring runtimes, we request one node with one core and 100GB of RAM. Unless otherwise specified, we configure EQUI-VOCAL as follows. For the trajectories dataset and the real-world dataset, we search for queries with up to 5 predicates across up to 3 region graphs. We use beam width 𝑏𝑤 = 10, 𝜆 = 0.01 for regularization (with 𝛼 1 = 𝛼 2 = 1, and 𝛼 3 = 0.1, see Section 3.7), and we set 𝑘 = 100, 𝑠 𝑞 =100, and 𝑠 𝑣 = 100. For the scene graphs dataset, we search for queries with up to 7 predicates, 3 region graphs, and 3 objects. Since the dataset is more complex and challenging, we use a smaller 𝜆 (because the query complexity term, 𝑅(𝑞) has a greater absolute value) and a greater 𝑘. We use beam width 𝑏𝑤 = 10, 𝜆 = 0.001 for regularization (with 𝛼 1 = 𝛼 2 = 1, and 𝛼 3 = 0.1), and we set 𝑘 = 1000, 𝑠 𝑞 =100, and 𝑠 𝑣 = 100. The user study is conducted on an AWS EC2 c6id.4xlarge instance with 16 vCPUs and 32GB of RAM. We search for queries with up to 7 predicates, 3 region graphs, and 3 objects. For duration constraints, we consider three possible values, 25, 50, and 75 frames, which translate to 1, 2, and 3 seconds. To improve the interactivity of the system, we use a smaller beam width 𝑏𝑤 = 5 and a smaller sample of candidate queries 𝑠 𝑞 = 25 for active learning. We set 𝑠 𝑣 = 100, 𝜆 = 0.001 and 𝑘 = 100.
We consider two variants of Quivr. As per the original paper, we limit the number of atomic predicates in Quivr's queries to 5 and the depth of the nested constructs to 3, which leads to a similar search space as EQUI-VOCAL. When considering queries without duration constraints (e.g., TQ1-TQ9), we omit Kleene star operators from its search space. Otherwise (e.g., TQ1D-TQ3D), we include Kleene star in the query expansion and add one more predicate MinLength 𝜃 , which checks whether the duration of the input is at least 𝜃 frames. Quivr returns all queries that match the examples, so we select the queries with the simplest structure (which is determined by the number of atomic predicates, and, if the former is the same, by the depth) and report their median F1 score.
Because PATSQL requires that all user-provided input tables be used in the solution query, when comparing against PATSQL, we restrict all systems to only the candidate predicates that appear in the target query. Because PATSQL cannot handle large tables efficiently, we also downsample each trajectory by 75% (we keep one frame out of four) to reduce the size of the input tables. We refer to this configuration as simplified tasks.
We evaluate EQUI-VOCAL against the two baselines on the trajectories dataset and the set of queries in Table 3. We run each method as follows. For each target query, we randomly select 2 positive and 10 negative examples from the training set and use them as the input to the method. Each method then asks for 𝑏 additional examples during the search. For PATSQL, since it is not interactive, we simply sample 𝑏 more examples randomly from the remaining dataset and provide the 12 + 𝑏 examples to the system at the beginning. For Quivr and EQUI-VOCAL, we input the 12 initial examples, and each system actively requests more examples during the search process.
EQUI-VOCAL is faster than baselines and can find highperformant queries even for complex queries. Table 5 shows the query synthesis time of each query to achieve at least a 0.9 F1 score. For simplified tasks, EQUI-VOCAL outperforms baselines on 6 queries. PATSQL performs the best or close to the best when queries are simple (TQ1, 5, and 6) because these queries include only two predicates and PATSQL terminates once it finds one solution query. Quivr is slower than EQUI-VOCAL but comparable to it except for TQ9, in which case Quivr fails due to an insufficient F1 score of the synthesized queries. Under the normal setting, EQUI-VOCAL is significantly more efficient than Quivr and can find high-performance queries in hundreds of seconds even for complex queries with duration constraints, while Quivr cannot synthesize TQ4, TQ7, TQ9, and TQ1D-TQ3D within 4 hours due to the large number of queries that need to be explored in the enumerative search. EQUI-VOCAL achieves a faster synthesis time than Quivr by exploring fewer queries using beam search and by executing every query faster. For example, for TQ3 under the normal setting, Quivr explores 221K queries while EQUI-VOCAL only explores 1101 queries, and EQUI-VOCAL executes each query 4.7× faster. We include the detailed performance results in our technical report [84].
On simplified tasks, EQUI-VOCAL and QUIVR find queries with similar F1 scores and outperform PATSQL for the same labeling budget. Figure 4 shows the F1 score of each system when varying the user labeling budget on the simplified tasks (which all systems can perform). We assign an F1 score of 0 if a system fails to find a query in 1 hour. Across all labeling budgets tested, as above, PATSQL performs well when the target query is simplest (TQ1, 5, and 6). For other queries, PATSQL either fails to find a solution query within 1 hour or the solution query has low performance (below a 0.9 F1 score). When the budget is 30, we observe a decrease in F1 scores for TQ3, 7, 8, and 9, because PATSQL has a less constrained search space than EQUI-VOCAL and does not scale well when the size of input and output tables increases as more examples are provided. Quivr performs better than EQUI-VOCAL when no additional examples are requested (budget=12) because it enumerates the entire search space and finds all consistent queries using the initial examples, while EQUI-VOCAL prunes candidate queries at every iteration to ensure efficient query synthesis. With a larger labeling budget, EQUI-VOCAL can request more labels during the search process to select better paths to explore, thus it catches up with Quivr and outperforms it when the budget is 30. EQUI-VOCAL is more robust to noisy data and produces higher quality queries than Quivr. We compare the performance of Quivr and EQUI-VOCAL when the data is noisy. We do not compare against PATSQL since its performance on video queries is already low even with perfect data. We inject noise into the original dataset by randomly flipping a fraction of the labels. We vary the false negative rate from 0.1 to 0.5 and set the false positive rate to 0.1 the false negative one. Table 6 shows the percentage of runs when the system returned any queries for different : EQUI-VOCAL can synthesize high-quality queries within a reasonable budget, even for scene graph queries. noise rates. We evaluate the systems over 9 queries (TQ1-TQ9) in the simplified setting. For Quivr, we also report the range of the success rate besides the mean value. When the false negative rate is 0.1, Quivr has a 68% success rate, and this goes down to only 17% when the false negative rate is 0.5. In contrast, EQUI-VOCAL always returns 𝑘 queries. To demonstrate that EQUI-VOCAL also produces higher quality queries, Figure 5 shows the F1 score of EQUI-VOCAL and Quivr with a labeling budget of 20, under two different noise rates. When Quivr fails to return any queries, we assign an F1 score of 0. EQUI-VOCAL performs better than Quivr for different queries and different noise rates.
Next, we evaluate EQUI-VOCAL on the scene graphs dataset. Neither PATSQL nor Quivr support such flexible queries at video scale. Because the dataset is more complex, EQUI-VOCAL requires that the user provide a slightly larger (although still quite small) number of initial examples to avoid overfitting. We randomly select 15 positive and 15 negative examples from the training set as the initial examples. In the technical report [84], we discuss how varying the initial number of examples affects the system performance.
Figure 6 shows the F1 score of EQUI-VOCAL under different user labeling budgets. With a larger budget, EQUI-VOCAL can learn queries with higher F1 scores, and achieves a median F1 score of 1.0, 0.91, and 0.67 for easy, medium, and hard queries when the budget is 100. Results for a budget of 50 are nearly identical, which shows that EQUI-VOCAL can synthesize high-quality queries within a reasonable budget, even for complex queries.
EQUI-VOCAL does not learn good queries in all cases. We note that some queries are easier to synthesize than others, which results in the high variance of the F1 score in Figure 6. In particular, EQUI-VOCAL assumes that the ancestor queries of the target query are informative and leverages the performance of those queries to guide the search. However, if the ancestor queries cannot be distinguished from other queries in the same iteration (because they all have the same, typically low, F1 score), EQUI-VOCAL struggles with learning good queries. One direction of future work could explore other types of more fine-grained user feedback besides binary labels to help EQUI-VOCAL learn intermediate queries [65]. EQUI-VOCAL's query synthesis time on the scene graphs dataset is greater than on the trajectories dataset. It increases from tens of seconds (Table 5) to minutes. However, EQUI-VOCAL can easily be parallelized to reduce synthesis time, as executing queries in PostgreSQL is embarrassingly parallel. With eight cores, EQUI-VOCAL achieves a 3.03× speedup and query synthesis time reduces to 13 minutes for the hard, scene-graphs queries with a labeling budget of 50. The query synthesis time can be further reduced by using more cores, further decreasing the labeling budget, decreasing 𝑏𝑤, or decreasing 𝑘. We show more detailed performance graphs in our technical report [84].
We compare EQUI-VOCAL and Quivr on the real-world dataset and queries in Table 4. We randomly select 2 positive and 10 negative examples as initial examples. Since the target events are extremely rare in the dataset, we consider EQUI-VOCAL with two different 𝑠 𝑣 values, 100 and 500, to increase the number of sampled positive examples during active learning.
EQUI-VOCAL outperforms Quivr in terms of F1 scores and query synthesis time on the real-world dataset. Figure 7 shows the F1 score and query synthesis time of both systems under different labeling budgets. We only show 6 queries due to space constraints, but we include full results in the technical report [84]. The timeout is set to 4 hours for both systems. EQUI-VOCAL can synthesize all queries in hundreds of seconds with a labeling budget of 30, while Quivr suffers from a low success rate (as shown in Table 7) and, even when it succeeds, takes thousands of seconds to synthesize queries. EQUI-VOCAL performs poorly with a labeling budget of 12, but with some additional examples, EQUI-VOCAL can easily achieve higher F1 scores. In addition, sampling more candidate segments during active learning (𝑠 𝑣 =500) increases the F1 score in most cases but also slightly increases the synthesis time.
We conduct a user study to understand the effectiveness and usability of EQUI-VOCAL. We use internal validation since asking
UQ1 UQ2 UQ3 UQ4 UQ5 UQ6 4 8 12 16 Time (min) Total time System time (a) Task completion time. UQ1 UQ2 UQ3 UQ4 UQ5 UQ6 0.0 0.5 1.0 F1 score Perfect User Simulated Fixed (b) F1 score. participants to provide their own queries would make it difficult to compare across participants. Our goals include observing the system performance in the presence of user noise, measure task completion time, and collect qualitative feedback. We recruited 18 university students studying Computer Science. The study is conducted over the scene graphs dataset with six query tasks with different complexities, as shown in Table 8.
We started each session by explaining our definitions of predicates and walking through an example task with participants to get them familiar with the interface and the task. Each participant then completed three query tasks in sequence (either UQ1, 3, 5 or UQ2, 4, 6) with increasing complexity from easy, to medium, to hard. Each query task described the target complex event using natural language. In the user study, we provided the initial examples with ground-truth labels to EQUI-VOCAL so that participants could focus on interacting with the system during query synthesis. We randomly selected 10 positive and 10 negative examples for UQ1, 2 and 4 as the initial examples, and 15 for other queries to account for the increased query complexity. EQUI-VOCAL iteratively selected video segments to label, with a budget of 50 per task. After each task, participants reviewed the synthesized queries and provided subjective ratings and qualitative feedback via a questionnaire.
Participants are able to complete the task in a reasonable amount of time. Figure 8a shows the task completion time of each query. The median completion time of each task ranges between 8.6 and 12.3 minutes. The average time to label a video segment for each query task is 22, 16, 25, 20, 30, and 22 seconds, respectively. Also, the system time only takes a small portion of the total time, suggesting that EQUI-VOCAL is efficient.
EQUI-VOCAL is resilient to user noise, whereas Quivr is not. Figure 8b shows the F1 score of synthesized queries under different labeling scenarios: using the ground-truth labels (Perfect), using real user labels (User), using injected label noise with a false negative rate of 0.3 and a false positive rate of 0.03 (Fixed), and using injected label noise with the same noise rate as users for each query task (Simulated). Each experiment is run nine times. F1 scores of User lie between Perfect and Simulated. Due to the user noise, the query performance decreases compared to using perfect labels. Because the same error rate is used, Simulated's performance is worse or similar to User's, which justifies our expectations for the simulation experiment. For queries that EQUI-VOCAL can synthesize with high quality, participants can help to find them with at least 0.8 F1 scores. Not surprisingly, for queries (UQ5 & 6) that EQUI-VOCAL would fail even with perfect labels, participants cannot instruct the system to achieve better (Near(𝑜 1 , 𝑜 2 ), Top(𝑜 3 ), Right(𝑜 3 ))
A red object is far from a cylinder, then they get close while a third object is at the top right of the screen.
12.8% UQ4 (Color(𝑜 1 , 'purple'), Material(𝑜 1 , 'metal'), Behind(𝑜 1 , 𝑜 2 ), Bottom(𝑜 2 )); Top(𝑜 2 )
A purple metal object 𝑜 1 is behind another object 𝑜 2 at the bottom of the screen, then 𝑜 2 moves to the top.
12.8%
UQ5 Duration( (Color(𝑜 1 , 'red'), Shape(𝑜 2 , 'cylinder'), Far(𝑜 1 , 𝑜 2 )), 25); (Near(𝑜 1 , 𝑜 2 ), Top(𝑜 3 ), Right(𝑜 3 ))
A red object is far from a cylinder for at least a second, then they are near each other while a third object is at the top right of the screen.
UQ6 (Color(𝑜 1 , 'purple'), Material(𝑜 1 , 'metal'), Behind(𝑜 1 , 𝑜 2 ), Bottom(𝑜 2 )); Top(𝑜 2 ); Duration( (Bottom(𝑜 3 ), Right(𝑜 3 )), 25)
A purple metal object 𝑜 1 is behind another object 𝑜 2 at the bottom of the screen, then 𝑜 2 moves to the top, then a third object 𝑜 3 is at the bottom right for at least a second. performance using the current prototype. Interestingly, most video segments that EQUI-VOCAL selects for hard queries are negative examples, making it difficult to learn good queries. However, many participants consider some negative samples to be almost positive that fail to satisfy one predicate. This suggests that EQUI-VOCAL could potentially benefit from more fine-grained user feedback.
Participants would like EQUI-VOCAL to be more responsive. In the questionnaire, the average rating of system responsiveness is 3.53 out of 5. Although the average system time across all tasks is only 195 seconds, participants observe greater latency in early and middle iterations, since there are more branches to expand and more candidate queries to evaluate. Taking UQ1 as an example, the average wait time to receive the first video segment in the 5th iteration is 31 seconds, while in the 10th iteration, it is only 1.3 seconds. Other techniques can be used to further hide the latency of the system [20], which is not the focus of this work.
To determine whether a video segment contains an event of interest, EQUI-VOCAL's query synthesis approach could be substituted by training an ML model. However, this approach requires a large number of labeled examples and complicates interpretability [22]. We compare EQUI-VOCAL against an existing ML approach that builds domain-specific models for videos [20] on the scene graphs dataset. For EQUI-VOCAL, we adopt the same setting as outlined in Section 5.2, with a labeling budget of 50. The ML approach extracts features using pretrained video and image models and trains a linear model using the same set of user-labeled video segments selected by EQUI-VOCAL. We use both MViT [21] and CLIP [60] as the feature extractors. Table 9 shows that EQUI-VOCAL achieves higher F1 scores than the ML approach for all queries, even when using CLIP with all 500 training samples.
Video analytics systems. Many recent VDBMSs have been proposed and focus on a wide range of data management challenges, including fast inference over videos [3,5,39,51,55], storage optimization [18,27,79], efficient dataflow processing [58], preprocessing and indexing [6,32,41], exploration and organization [19], privacy [9], and tuning configurations [33,37,63]. Those techniques are orthogonal to our work.
Compositional query processing over videos. Several systems have explored compositional queries over videos [7, 11, 14-17, 23, 45, 49, 54, 80]. However, they either require that users express compositional queries explicitly [14,23,49], or train customized models for such events [7,11,17]. Instead, EQUI-VOCAL uses a query-by-example approach to minimize user effort and learn and refine a query specification iteratively from user feedback.
Accelerating query execution over visual data. Prior work has focused on accelerating queries by pre-filtering frames to avoid expensive computation [29,30,51], optimizing the sampling rate [5,55], and building specialized models [3,39]. EQUI-VOCAL currently extracts all objects in a video before the search process, but could leverage those existing techniques to avoid running expensive object detection and tracking algorithms on all frames.
Query by example. Many systems have been proposed for SQL queries over relational data [22,48,59,70,73]. EQUI-VOCAL focuses on learning queries for video events, with a more constrained form than general relational queries. Quivr [54] is most similar to our work, but it only operates over object trajectories and assumes noiseless inputs.
Program synthesis. Program synthesis has been used for a wide range of tasks, such as generating referring relational programs [34], authoring visualizations [57,74], learning relational data transformation [38], and synthesizing programs for string processing [56]. Unlike these systems, EQUI-VOCAL synthesizes queries in the video domain, which is significantly different in terms of the spatio-temporal complexity and the prevalence of noise.
Active learning. Model Picker [42] uses active learning to distinguish the best model from a set of pretrained classifiers. EQUI-VOCAL adapts this approach to select the most promising queries to explore. Quivr [54] also prunes candidate queries using active learning, but only after enumerating all candidates. In contrast, EQUI-VOCAL integrates active learning and labeling into the search process to ensure both synthesis efficiency and query performance.
In this paper, we presented EQUI-VOCAL, a new system that synthesizes compositional queries from examples. EQUI-VOCAL models compositional events as spatio-temporal scene graphs, explores the query search space using results of executing intermediate queries and beam search, leverages active learning to reduce user effort, and generates efficient SQL queries to reduce computational effort.
In this and the following examples we use English words instead of integers for 𝑐𝑖𝑑 and 𝑝𝑖𝑑 values to make the examples more readable