{'fraction_non_alphanumeric': 0.03315304097435698, 'fraction_numerical': 0.008638468422895833, 'mean_word_length': 4.594753455970393, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
THIA: Accelerating Video Analytics using Early Inference and Fine-Grained Query Planning

To efficiently process visual data at scale, researchers have proposed two techniques for lowering the computational overhead associated with the underlying deep learning models. The first approach consists of leveraging a specialized, lightweight model to directly answer the query. The second approach focuses on filtering irrelevant frames using a lightweight model and processing the filtered frames using a heavyweight model. These techniques suffer from two limitations. With the first approach, the specialized model is unable to provide accurate results for hard-to-detect events. With the second approach, the system is unable to accelerate queries focusing on frequently occurring events as the filter is unable to eliminate a significant fraction of frames in the video. In this paper, we present THIA, a video analytics system for tackling these limitations. The design of THIA is centered around three techniques. First, instead of using a cascade of models, it uses a single object detection model with multiple exit points for short-circuiting the inference. This early inference technique allows it to support a range of throughput-accuracy tradeoffs. Second, it adopts a fine-grained approach to planning and processes different chunks of the video using different exit points to meet the user's requirements. Lastly, it uses a lightweight technique for directly estimating the exit point for a chunk to lower the optimization time. We empirically show that these techniques enable THIA to outperform two state-of-the-art video analytics systems by up to 6.5X, while providing accurate results even on queries focusing on hard-to-detect events.


Introduction
Researchers have proposed systems for quickly processing visual data with a tolerable drop in accuracy [3, 4, 7, 8, 10-13, 16, 23, 24]. These systems detect objects in videos using deep neural networks (DNNs) [5,17]. The key challenge that these systems tackle is the computational overhead of the underlying object detection model.
Prior Work. To efficiently process visual data at scale, researchers have proposed two techniques. The first approach, presented in BlazeIt [10], consists of leveraging a specialized, lightweight model to directly answer the query. The second approach, introduced in PP [13], focuses on filtering irrelevant frames using a lightweight model. The frames that pass through the filtering model are then processed by the heavyweight object detection model (illustrated in Figure 2). So, these systems accelerate query processing by not processing a subset of video frames using the heavyweight model. However, these techniques suffer from two limitations. With the first approach, the specialized model is unable to provide accurate results for hard-to-detect events. With the second approach, the system is unable to accelerate queries focusing on frequently occurring events. This is because the filter is unable to eliminate a significant fraction of frames in the video.
Another line of research, illustrated in Tahoma [1], focuses on leveraging a collection of differently sized models to process the frames based on the complexity of the event. However, using such a cascade of models comes with two limitations. First, switching from one model to another in the GPU is expensive. This switching overhead is further exacerbated if we seek to frequently change the model to process different subsets (i.e., chunks) of the video to maximize performance. For instance, loading a Faster-RCNN model in PyTorch on an NVIDIA Titan Xp GPU takes 2 s (including framework initialization and model loading). Second, using a collection of models to support different throughput-accuracy tradeoffs does not scale well due to the large GPU memory footprint of these models.
Prior efforts have mostly focused on altering the design of the inference pipeline. However, they do not elaborate on how to adapt this pipeline (e.g., when to use a particular model) based on the chunk. They choose a single plan for the entire video based on the profiling results obtained on a set of sampled frames. Such a coarsegrained approach to query planning does not leverage the variation in the frequency and detection difficulty of different events in a video. If objects are difficult to detect, this approach leads to less accurate results. On the other hand, if objects are easier to detect, a conservative coarse-grained query plan significantly increases the query processing time (but returns correct results). We defer a detailed discussion of these limitations to §3.
Our Approach. In this paper, we present Thia, a video analytics system for tackling the limitations highlighted above. Thia leverages three techniques to accelerate queries over visual data.
First, it uses a single object detection model with multiple points for short-circuiting the inference. These exit points (EPs) offer a set of throughput-accuracy tradeoffs. While processing the query, Thia uses a shallow EP to quickly process frames that are irrelevant or contain easy-to-detect events. If the frames contain hard-to-detect events, then Thia falls back to a deeper EP in the model to deliver higher accuracy. This Early Inference technique eliminates the switching overhead and lowers the GPU memory footprint of Thia.
Second, Thia adopts a fine-grained approach to planning. It processes different chunks of the video using different EPs to meet both the performance and accuracy requirements (elaborated in §6.1). This Fine-Grained Planning technique increases the optimization time of a query. To lower this overhead, we present a third technique to quickly decide which EP to use for a given chunk. Thia uses a shallow model for Exit Point Estimation instead of running inference on the sampled frames. We evaluate a set of queries focusing on events with different levels of frequency and detection difficulty on two traffic surveillance datasets: UA-DeTrac [21] and Jackson Town [10]. On all of the queries, Thia outperforms the state-of-the-art video analytics systems by up to 6.5× with a tolerable drop in accuracy.
Contributions. Our research makes the following contributions: • We present the Early Inference technique to construct a single model that offers a set of throughput-accuracy tradeoffs for challenging vision tasks like object detection. • We propose a Fine-Grained Planning technique that works in tandem with the Early Inference technique. • We present the Exit Point Estimation technique to reduce the optimization overhead of the Fine-Grained Planning technique. • We implement all of these techniques in Thia and show that it outperforms two state-of-the-art video analytics systems on a wide range of queries.

Background
We now present an overview of object detection and sampling techniques used in video analytics systems ( §2.1 and §2.2). We later discuss the key techniques used in state-of-the-art systems ( §2.3).

Object Detection
Object detection models usually contain three components: (1) backbone network, (2) region proposal network (RPN), and (3) region of interests network (ROI), as illustrated in Figure 1. The backbone network extracts the high-level features from a frame. Then, the RPN and ROI networks determine the location and type of objects detected in the frame. Data flows from the backbone network to RPN, and ROI returns the final prediction results (object category, location within the frame, and confidence score). In machine learning literature, the oracle model returns the correct answer to all queries. However, in practice, there is no ground truth for unseen data. Similar to prior efforts, we assume that the most accurate model, which also tends to be the most computeintensive model, is the oracle model [9-11, 13, 24].

Sampling
Sampling is a frequently used technique for processing visual data at scale. By processing only a subset of frames using the object detection model, a video analytics system lowers the overall query processing time. For example, BlazeIt [10] uses uniformly random sampling to process aggregate queries (e.g., counting the average number of cars within a given period of time).  Figure 2: Architecture of Video Analytics Systems -Architecture of two state-of-the-art video analytics systems: (1) PP [13] and (2) BlazeIt [10]. Thia uses sampling for a different purpose (elaborated in §6). A chunk is a continuous segment of frames within a video. Thia's Optimizer constructs plans at chunk-level granularity (instead of video-level granularity) to lower the query processing time. Query processing time consists of two components: (1) optimization time, and (2) execution time. During the optimization phase, Thia generates a plan for each chunk. During the execution phase, it runs these plans. Table 1 lists the key characteristics of several state-of-the-art video analytics systems: (1) PP [13], (2) BlazeIt [10] (3) Miris [2], (4) Tahoma [1], and (5) Panorama [24]. We present the benefits and limitations of the first two systems in §1. Their architectures are illustrated in Figure 2.

State-of-the-Art Systems
Miris [2] is a video analytics system that focuses on multi-object tracking. It uses coarse-grained sampling to gain a high-level perspective of the video and then gradually increases the sampling rate to improve the accuracy of tracking. Thia differs from Miris in two ways. First, it is tailored for object detection. Second, it only samples for query planning (not for query execution). In §7.7, we illustrate the benefits of other optimizations in Thia by comparing it against a variant of Thia that only uses Fine-Grained Planning (Thia-Single in Table 1).
Tahoma [1] is another closely related analytics system. It constructs a model cascade by combining a chain of image classification models and determines when to short-circuit the inference based on   Table 1), instead of a single Early Inference model 1 .

Rare Hard
Panorama [24] is another state-of-the-art video video analytics system that uses a single model to solve the unbounded vocabulary problem in object recognition. While this system also offers a set of throughput-accuracy tradeoffs similar to Thia, it is geared towards comparing embeddings from two input frames. So, it selects the EP based on the delta between two embeddings while extracting the embeddings. Lastly, it clusters these embeddings to recognize the objects in the input frames. In contrast, Thia uses Early Inference in the object detection model itself and seeks to reduce optimization time using the Exit Point Estimation technique.

Motivation
In this section, we discuss the limitations of PP and BlazeIt to motivate the need for Thia. We focus on the four queries described in Table 2. These queries differ in: (1) frequency of appearance of target objects in the video, and (2) level of difficulty in providing a correct answer to a query. Limitation I -model specialization overhead. Both PP and BlazeIt rely on specialized models. PP uses a specialized model as a filter. Since each filter detects only one object category, it needs to train multiple lightweight models (i.e., filters) during runtime to support different object categories. BlazeIt uses a specialized model to directly return the results. A model may directly return the count of cars in an image, so it must maintain multiple models for different predicates (e.g., Count(Car) is a predicate). With this 1 Thia-Multi delivers better performance than a naive model cascade due to the Fine-Grained Planning technique. With a naive model cascade, the system cannot directly process frames with the optimal model. It must use all the smaller models before stopping the inference at the optimal model.  model specialization technique, these systems need to train and maintain models for different objects and predicates, respectively. We seek to reduce model maintenance overhead by offering a range of accuracy and query execution time tradeoffs in a single model.

Difficulty Precision Recall Throughput
Limitation II -freqent events. The filtering technique used in the PP system [13] relies on data reduction by the filter to achieve speedup. Let's assume the system is processing frames and that the fraction of frames that is filtered and discarded by the filter is . Let the costs of running the filter and running the object detector be and per frame, respectively. To obtain a speedup, the data reduction rate must satisfy this constraint: This constraint is not met by frequent events (e.g., Q1 in Section 3). In this case, since is small, the filter slows down the overall pipeline since it adds additional overhead. As a result, PP is slower than Naive (i.e., naively running object detector on every frame) for frequent queries like Q1. PP only provides a 0.93× speedup compared to Naive in this case. Instead, for rare queries like Q3, PP is able to provide a 1.44× speedup compared to Naive. We seek to dynamically adjust the query execution pipeline based on the estimated frequency of the event.
Limitation III -difficult-to-detect objects. BlazeIt [10] uses a specialized model to directly return aggregates (e.g., number of cars in an image). This approach does not generalize to complex visual datasets. The reasons are twofold. First, the specialized model is designed to be shallow for fast execution. So, it is unable to learn complex patterns. Second, it relies on an ad-hoc subset of videos for training, so the lack of positive examples greatly affects the quality of the model. As shown in Table 3, BlazeIt returns precise answers for easy-toanswer queries. However, it has a lower recall metric. For hard-toanswer queries (e.g., Q3), the specialized model does not offer useful results. So, the system instead falls back to the object detection model. In this case, BlazeIt runs the specialized model, resulting in lower performance than Naive. In contrast, Thia is capable of selecting an optimal plan with good accuracy and performance metrics.
Our Approach. In Figure 3, we show two prediction results from our Early Inference technique (the oracle object detection EP and a shallow EP, respectively). We observe that the faster EP is still able to capture the presence of cars, but it is less accurate in two ways. First, the bounding boxes are not accurate, so multiple bounding boxes are returned for the same object. Second, it tends to miss hard-to-detect objects (e.g., objects far away or objects with lights). If a user queries for an image with exactly four cars, Thia uses the oracle exit point to satisfy the precision requirement. However,    if the user is only interested in images with cars, Thia uses the faster exit point to obtain a 6× speedup. We design Thia so that it carefully chooses the optimal query execution plan for every chunk of the video to deliver higher accuracy and speedup. Figure 4 illustrates the architecture of Thia. ❶ Fine-Grained Planning. When the system gets a query, the Optimizer uses the Fine-Grained Planning technique to construct a query execution plan. It first splits the entire video into a set of small chunks. The size of a chunk is determined dynamically at runtime (covered in §6). For each chunk, the Optimizer chooses the optimal plan (i.e., when to stop inference in the model). Such a fine-grained query plan enables Thia to deliver higher accuracy and throughput compared to a coarse-grained plan for the entire video. A naive technique for picking the plan consists of running the model on a set of sampled frames from the chunk. While the fine-grained plan reduces the query execution time (Thia-EI in Table 1), it increases the query optimization time, which hurts the overall query processing time (discussed in §7.5). To reduce the optimization time, Thia instead leverages a more lightweight Exit Point Estimation technique. ❷ Exit Point Estimation. Thia uses Exit Point Estimation and Fine-Grained Planning techniques in tandem to reduce the overhead of the Optimizer. The Optimizer uses a shallow neural network to directly estimate when to short-circuit the inference in an Early Inference model. It trains an EP estimator for every unique query executed in the system. We discuss how Thia obtains data for training the Exit Point Estimation model in §6. ❸ Early Inference. The fine-grained query plan constructed by the Optimizer consists of a list of chunks and the model chosen for each chunk. For example, Thia may skip frames 0 through 100, run EP-1 on frames 101 through 300, and evaluate the oracle EP (i.e., EP-3) on frames 300 through 500. The Execution Engine takes this query plan and uses the Early Inference technique to deliver different accuracy-performance tradeoffs with a single model.

Early Inference
In this section, we present the Early Inference technique. We first provide an overview of this technique in §5.1. We then illustrate its utility using a case study with Faster-RCNN [17] in §5.2.

Overview
We seek to construct a single model with multiple exit points wherein the inference may be short-circuited to improve performance at the expense of accuracy. We do not want to construct a collection of models to accomplish this goal. The Optimizer dynamically adjusts the EP based on the query. If the query is relatively easy to answer, Thia delivers higher speedup by stopping the inference earlier (while returning accurate results). We discuss how Thia estimates the correct EP for a chunk in §6. In this section, we focus on how we construct a model with multiple EPs. As discussed in §2.1, object detection models usually rely on a backbone network that is based on a state-of-the-art image classification model (e.g., ResNet-50 [6] and VGG-16 [18]). Since these classification models are tailored for high accuracy, they consist of a stack of compute-intensive layers that lead to lower inference throughput. The layers in a backbone network are sequentially connected to each other. Our key idea is to provide faster detection results with lower accuracy by using the features from earlier layers in the backbone network.
Model Cascading vs Early Inference: Researchers have proposed model cascades for face recognition [19,20]. Similar to Early Inference, in a model cascade, the features from earlier layers in the backbone network are used for face recognition. However, these techniques differ in two ways. First, face recognition is a binary classification task (i.e., face exists in the image or not). So, the additional classification layers are only instrumented in this approach. Second, these efforts propose a bespoke architecture to construct the cascade. We instead seek to support early inference in widely used object detection models.  To support Early Inference with a general-purpose object detection model, we introduce additional RPN and ROI units in the earlier layers of the backbone network. We modify the number of parameters in these units so that they operate on the feature tensor emitted by the backbone network. As shown in Figure 5, for a given input, Optimizer may choose to short-circuit the inference using the newly added units to speed up inference.

Case Study: Faster-RCNN
Faster-RCNN is a state-of-the-art object detector [17]. We now discuss how we extend this model to support Early Inference. We next describe how to generalize the training process to other models.
Faster-RCNN with Early Inference: The backbone network of Faster-RCNN is the ResNet-50 [6] model. ResNet-50 consists of five stacked compute blocks, so we extend this model to support five EPs (we could support fewer or additional EPs if needed by instrumenting other layers of the backbone network). The default output of the model corresponds to the fifth EP. We add four additional EPs that provide a wide set of throughput-accuracy tradeoffs (i.e., EP-1, EP-2, EP-3, and EP-4 in Figure 5). We refer to EP-5 as the oracle (since it is the output of the original model). We preserve the structure of RPN and ROI units as is the case of the oracle. However, we modify the first layer in these units to work with the output tensors of the early EPs that vary in size. Table 4 lists the layer configuration of each EP 2 .
Top-down training: We adopt a novel top-down training technique for constructing models that support early inference. We start the training process with the following multi-loss function: represents the set of exit points (including the oracle). denotes the object detection loss function used in Faster-RCNN [17]. This training step tunes all EPs.
represents all possible object detection EPs, including the oracle EP. We begin with the oracle EP. The reasons for doing this are twofold. First, the oracle gets the features emitted by the last stage of the backbone network, so training this EP ensures that all layers   converge to the optimal state. Second, we seek to ensure that the oracle EP in the Early Inference model delivers the same accuracy as that of the original model. After training the oracle EP, we freeze all the layer parameters in the backbone network. This ensures that fine-tuning the shallow EPs later does not affect the previously tuned EPs. We gradually fine-tune the RPN and ROI units starting from EP-4 through EP-1.
Throughput-Accuracy Tradeoffs. Table 4 lists the speedup of shallow EPs with respect to the the oracle EP. For a given video frame, this Early Inference model offers up to a 6.9× speedup when we stop the inference at the first EP. Table 4 also summarizes the true positive and false negative percentage of each EP on the training dataset with respect to the oracle EP. These metrics are averaged across all categories. Shallower EPs return more false negatives and fail to return a few true positives. In other words, they are more likely to not return a positive frame instead of misclassifying a negative frame. If the system were to use a shallow EP for the entire video or sequence of images, the impact on query accuracy would be significant. Instead, it must use the oracle EP on some difficult chunks of the video. We cover this Fine-Grained Planning technique in §6. In §7, we demonstrate that Thia has a tolerable accuracy loss using both Early Inference and Fine-Grained Planning techniques.
Generalization. The Early Inference technique generalizes to other models (e.g., VGG-16 [18]) and other vision tasks (e.g., image classification). This is because most of these deep learning models contain similar backbone networks that benefit from the Early Inference technique. Furthermore, the number of EPs may be increased or decreased based on the complexity of the model.  Figure 6 illustrates another Early Inference model based on VGG-16 for an image classification task that is trained on the Flower-102 dataset [14]. Here, EP-1 provides a 4.7× speedup compared to EP-8 (i.e., the oracle EP). By using all the eight EPs together, the system achieves a 2.7× speedup compared to the oracle EP with minimal accuracy loss.

Query Planning
We present the Fine-Grained Planning technique in this section. In §6.1, we make the case for Fine-Grained Planning. In §6.2, we discuss how Thia samples frames and constructs chunks to apply this technique. Lastly, in §6.3, we introduce the Exit Point Estimation technique for reducing the optimization time.

Motivation
As we discussed in §5.2, the Early Inference model contains a set of EPs. The goal of the Optimizer is to choose an optimal (accurate and fast) EP for every fine-grained chunk of the video at runtime. Our key observation is that the optimal EP changes at chunk granularity. Figure 7 illustrates the chunk-level query plan for Q4 in Section 3. The triangles in Figure 7 represent the fastest (but still accurate enough) EP for every chunk in the video. This example shows that the optimal EP constantly changes. So, it is essential to dynamically adjust the query plan at runtime to achieve both good accuracy and performance.
State-of-the-art systems (e.g., BlazeIt [10] and PP [13]) take a coarse-grained approach to planning. They choose a single plan for the entire video based on the accuracy of the model on a set of sampled frames. The limitations of this technique are twofold.
Performance degradation. Positive events tend to not appear in every chunk of the video (i.e., selectivity of the predicate is typically high). If we pick a static plan for the entire video, video chunks that are less likely to contain positive events or that contain easy-to-detect events are passed to a more compute-intensive EP. Thus, the system does not leverage the opportunity to further improve performance by either skipping those chunks or using less compute-intensive EPs for those chunks. With Fine-Grained Planning, Thia uses a faster EP or directly skips the entire chunk (❶ in Figure 7). Accuracy loss. The distribution of the target event and the accuracy of the model vary across the video. A statically selected, shallow EP will hurt accuracy by missing hard-to-detect events. As shown in Figure 7, some chunks require deeper EPs to make Algorithm 1: Fine-grained query planning.
Input : V -Video data.
EP-List -The list of EPs in the Early Inference model. P -Precision constraint of the query. R -Recall constraint of the query. Output : Return a list of fine-grained plans. 1 video_length ← Length(V) // estimate initial sampling rate.

Chunking Algorithm
When Thia gets a query, it first splits the given video into a set of chunks. It then samples a set of frames from each chunk and then evaluates the accuracy of all the EPs in the Early Inference model on these sampled frames. Using these results, the system selects the best EP for each chunk. Lastly, it executes the query using the selected plan. The key components of the algorithm that Thia uses for chunking videos are as follows: ❶ Hierarchical Chunking. The two key decisions made by the Optimizer are: (1) chunk size, and (2) sampling rate (i.e., the number of frames to pick from a chunk). The system delivers higher accuracy with a higher sampling rate since more samples allow it to better estimate the optimal EP for each chunk. However, this hurts throughput since the system must evaluate the model's behavior on more frames, thereby increasing optimization time. Choosing the chunk size is also a challenging task. This is because the duration of an event varies based on the video, so Thia must dynamically adjust the chunk size at runtime. To tackle these challenges, Thia takes a hierarchical approach for picking the chunk size and the sampling rate for each chunk. It initially uses a large chunk size and a low sampling rate. This allows the Optimizer to gain a rough understanding of the contents of the video based on the inference results collected using the sampled frames. Based on this knowledge, it recursively adjusts the chunk size and sampling rate.
Algorithm 1 presents the hierarchical, recursive technique used by the Optimizer. As shown in Line 9, the recursive algorithm stops when the chunk size is smaller than a threshold or if the fastest EP has been chosen for a given chunk that contains enough positive frames. In Line 8, the PickBestEP function returns the rate of positive frames in a chunk (i.e., posi_ratio) that is obtained from the oracle EP. It is important to ensure that the chunk has sufficient positive frames, since the calculated precision and recall metrics of the EPs do not generalize well without sufficient positive frames. These constraints bound the optimization time. As shown in Line 11, if there are very few positive frames, then Thia skips the entire chunk to reduce both optimization time and execution time. Lastly, it gradually reduces the chunk size and increases the sampling rate, as shown in Line 15. The intuition is that if the system is not able to select a plan based on its coarse-grained understanding of the chunk, it must sample more frames from that chunk in the next iteration. By using a small chunk size, the Optimizer is able to adjust the plans quickly to transient events. ❷ Sampling Rate Bounds. The Optimizer gradually increases the sampling rate to improve the quality of its plan. However, this increases the optimization time and may hurt the overall throughput obtained with the plan. This is because the decrease in the query execution time is not sufficient to justify the increase in the optimization time. To overcome this limitation, the Optimizer uses the following constraint to bound the initial sampling rate (Line 2): Here, we assume that chunks must contain at least 100 frames and we seek to bound the final sampling rate to 0.1 even in the worst-case setting. The maximum depth of the recursive algorithm is ⌈log | | 100 ⌉ (sampling rate is doubled in each iteration). ❸ Memoization of Inference Results. In Line 7, the newly picked samples could be different from those that have already been evaluated. Evaluating all the EPs on a sample is expensive. To reduce this overhead, the Optimizer memoizes the inference results and reuses the results of nearby frames. This technique is illustrated in Figure 8. Without memoization, the results for the second and fourth frames must be obtained again when the sampling rate is increased in the next iteration. Thia instead reuses the results of nearby frames within the same chunk. With memoization, it picks the cached results for the third frame instead of running inference on the fourth frame. Thus, it evaluates only the EPs on the second frame. ❹ Evaluation-Based EP selection. To select the best EP, as shown in Line 8, Thia evaluates all the EPs on the sampled frames and compares them with the oracle EP. It picks the fastest EP that provides 0.8 precision and 0.8 recall. These constraints empirically offer maximal speedup with minimal accuracy loss ( §7.2). Even with all of these optimizations, evaluating the EPs on a frame comes with non-trivial optimization time. We next present the Exit Point Estimation technique for further reducing the optimization time.

Exit Point Estimation
We seek to reduce the optimization time associated with the Early Inference technique. As we present in §7.5, it is important to balance the tradeoff between optimization time and execution time to improve the overall query processing time.
The Exit Point Estimation technique consists of using a shallow, two-layer neural network instead of the evaluation step in query planning. The neural network directly returns the optimal EP based on the backbone features. This allows the Optimizer to eliminate compute-intensive evaluation of all EPs. For example, with Faster-RCNN, the inputs to the Exit Point Estimation model are the features emitted by the fifth stage of the Early Inference model.
To train this neural network, Optimizer uses 200 images from the training dataset of the Early Inference model along with the associated EP decision. For robust results, Thia must train a separate Exit Point Estimation model for each query. However, the overhead of training this model is tolerable because: (1) it is a one-time overhead for each query; and (2) training time for the Exit Point Estimation model is negligible compared to total query processing time due to the simple structure of the model. We defer an empirical analysis of this optimization to §7.6.
Estimation-Based EP selection. Since the Exit Point Estimation model directly estimates the optimal EP for a video frame, it does not return precision and recall metrics for all the EPs. So, the Optimizer extrapolates these metrics based on the estimated EP. We next discuss how this extrapolation is done.
Let us split the set of sampled frames into two subsets: (1) those that contain positive events as reported by the oracle EP (Line 9 in Algorithm 1), and (2) those that do not contain positive events. We define those two subsets as and , respectively. For a given video frame , let us denote the EP estimation model that outputs the optimal EP for that frame by ( ). The Optimizer estimates the number of true positives (TP), false positives (FP), and false negatives (FN) for any EP in the Early Inference as: Our intuition is that a shallow EP is less accurate than a deep EP. So, for a video frame , the estimated optimal EP (i.e., ( )) returns correct results. Then, all EPs after the estimated optimal EP (i.e., k ≥ ( )) should also return correct results, and vice versa. Hence, in the case of positive events, a deeper EP than the estimated optimal EP provides true positive prediction. On the other hand, a shallower EP than the estimated optimal EP provides false negative prediction. In the case of negative events, shallower EP than the estimated optimal EP likely results a false positive. With these projected metrics, the Optimizer derives the precision and recall metrics for an EP as: Lastly, the Optimizer picks the fastest EP that meets the precision and recall constraints (e.g., 0.8), as discussed earlier.

Experimental Evaluation
We seek to answer the following questions in our evaluation:

Experiment Setup
Evaluated Systems. Table 1 lists all the video analytics systems that we compare in our analysis (including the variants of Thia). In the Naive system, we apply the oracle EP on every frame. We normalize the accuracy metrics of other systems against those of the Naive system. We reimplement two other state-of-the-art systems in our framework for comparative analysis: (1) PP [13], and (2) BlazeIt [10]. In our implementation, the PP system uses ResNet-34 [6] to filter out unrelated frames. The BlazeIt system uses a specialized model (ResNet-34) to accelerate queries. To better understand the performance of Thia, we examine three variants of our system: (1) Thia-Single uses only the Fine-Grained Planning method with the oracle EP. (2) Thia-Multi also uses the Fine-Grained Planning method along with multiple EPs. Specifically, we use Faster-RCNN models with three backbone networks: ResNet-18, ResNet-34, and ResNet-50 [6] as three EPs.
(3) Thia-EI is the closest variant of Thia. It uses the Fine-Grained Planning along with the Early Inference technique (but does not use the Exit Point Estimation technique).
Datasets. We evaluate these systems on two datasets: (1) UA-DeTrac [21], and (2) Jackson-Town dataset from [10]. Both datasets are obtained from traffic surveillance cameras. We focus on four vehicle categories in both datasets: Car, Truck, Bus, and Others.
Evaluation metrics. Similar to other video analytics systems [1,[9][10][11]13], our evaluation normalizes the results with respect to the oracle model (Faster-RCNN model backed by ResNet-50). So, we provide the F-1 score calculated relative to the results of the oracle model. We also report separate precision and recall metrics for each query. This is important since a user might require fine-grained accuracy requirements (e.g., low precision and high recall). We assume that the decoded video is present on disk.
Queries. To evaluate these systems, we use the four queries listed in Table 2. Based on the predicate, the frequency of true positive events and the difficulty of detecting those events vary.
Software and Hardware. We implement Thia with the Detec-tron2 [22] framework in PyTorch [15]. We evaluate these systems on a server with 44 CPU cores and 256 GB memory along with one Titan Xp GPU with 12 GB memory.
Model Training. As discussed in §5.2, we construct the Early Inference model based on Faster-RCNN. We split the UA-DeTrac dataset into two parts: training and validation subsets. We train the Early Inference model on the the training subset. We warm up the training process for 1 epoch, and then each EP in Early Inference model is trained for 10 epochs in a top-down manner. Since the Jackson-Town dataset does not have ground-truth labels, we directly apply the Early Inference model, which is tailored for the UA-DeTrac dataset. For Thia-Multi, we train three models: Faster-RCNN based on ResNet-18, Faster-RCNN based on ResNet-34, and Faster-RCNN based on ResNet-50. Each model is trained for 10 epochs.
To train the Exit Point Estimation model, we use 1000 images from the UA-DeTrac training set. We split these images into training (200 images) and validation subsets. We construct the training so that the distribution of different EPs is balanced. The training data for this model consists of backbone features for those video frames, and the output is the fastest EP that is accurate enough. We quickly train this shallow network for 20 epochs.

Impact of Early Inference
In this experiment, we compare the query processing time of Thia-EI to that of other video analytics systems. The results are shown in Figure 9. The bottom right corner represents the ideal case (faster execution with accurate predictions).
Thia-EI. The most notable observation is that Thia-EI outperforms other systems on most queries. Thia-EI uses both Early Inference and Fine-Grained Planning. On Q1 and Q2, since the fraction of frames filtered out is limited, using an extra specialized model before the object detector adds additional execution overhead. Thia-EI consistently reduces the total runtime and also delivers a higher F-1 score compared to other systems. In particular, it is 2 -6× faster than Naive with a tolerable drop in F-1 score.
BlazeIt. On Q1, BlazeIt outperforms other systems with respect to query processing time. However, as we discussed in §3, its specialized model delivers a lower F-1 score. On other queries, since the F-1 score of the specialized model is too low to be useful, BlazeIt falls back to the oracle model. Even though the specialized model is not effective, BlazeIt still evaluates the query with the specialized model, so the processing time of BlazeIt is higher than that of Naive for Q2, Q3, and Q4.
PP. PP reduces the processing time on Q3 and Q4. This is because these two queries focus on relatively rare events. So, the model in PP is able to filter out a significant fraction of frames to accelerate query processing.

Ablation Study
We next examine how the EPs in a model are used by Thia-EI while processing queries.  Figure 11: Ablation study -Contribution of Fine-Grained Planning and Early Inference techniques to the performance of Thia-EI.
in Figure 10. To better understand the contribution of each technique to the performance of Thia-EI, we also conduct an ablation study. We measure the execution time of Thia-Single and Thia-EI to illustrate the benefits of Fine-Grained Planning and Early Inference techniques, respectively. The results of this study are illustrated in Figure 11.
These two experiments demonstrate that: (1) Fine-Grained Planning is able to adaptively choose the appropriate EP for each chunk based on the query and video frames, and (2) Fine-Grained Planning and Early Inference techniques have significant impact for rare events; but, in the case of frequent events, the speedup mainly comes from Early Inference.
On Q1, since positive events appear in majority of the video frames, the impact of Fine-Grained Planning is minimal. When we add in the Early Inference technique, Thia-EI delivers higher speedup by using shallow EPs for easy-to-detect events, as shown in Figure 10. Q1 demonstrates an extreme scenario wherein the first EP (EP-1) provides correct predictions on all video frames. In contrast, in the case of Q2, Thia-EI must use multiple EPs due to harder-to-detect events. Here, the Optimizer reduces the execution time by carefully choosing the EPs to use. As shown in Figure 10, while some frames are assigned to the oracle EP, other frames are assigned to shallow EPs to reduce execution time. By reducing the execution time, Thia-EI delivers a 4× speedup over Naive.
Unlike queries focusing on frequent events, the Fine-Grained Planning technique provides more performance benefits in the case of queries related to rare events, because the Optimizer decides to skip some chunks during execution (Line 11). On Q3 and Q4, as shown in Figure 11, Fine-Grained Planning leads to a 5× speedup. Nevertheless, the Early Inference technique is still useful for these queries. Thia-EI carefully assigns certain video frames to shallow EPs to improve the performance without losing accuracy. The system is thus accelerated further by 3× when the Early Inference technique enabled.

Impact of Fine-Grained Planning
We demonstrate the benefits of Fine-Grained Planning by comparing Thia-EI against a system that uses coarse-grained planning with the same Early Inference model. With coarse-grained planning, we evaluate all EPs on 10% of the sampled video frames and pick the EP that meets the precision and recall constraints. We show a breakdown of the query processing time in Figure 12. On all queries, Fine-Grained Planning provides a better query plans than coarse-grained planning so that the execution time is consistently lower. Moreover, with optimizations like sampling rate bounds and memoization in Fine-Grained Planning, it does  not incur higher optimization time than the naive coarse-grained planning approach. We next measure the distribution of query execution time over the fraction of the video being analysed in Figure 13. An even distribution (e.g., Q1 and Q2) suggests that the same query plan is used for a large chunk. In contrast, an uneven distribution (e.g., Q3 and Q4) suggests that the plan changes frequently across the video.

Processing Time Breakdown
We now provide a breakdown of the processing time of Thia-EI and its variants and compare it against Naive. Recall that all systems except for Naive use the Fine-Grained Planning technique. Though Thia-Single is only able to use the oracle EP, it is able to skip frames with no relevant events using Fine-Grained Planning.
The results are shown in Figure 14. Access to a set of EPs allows both Thia-EI and Thia-Multi to reduce execution time in comparison to Thia-Single and Naive. The reduction in execution time is more prominent compared to Thia-Single for queries focusing on more frequent events. While Thia-Multi supports multiple EPs similar to Thia-EI, Thia-EI supports multiple EPs in a single model. So, it has a lower GPU memory footprint, as shown in Figure 18. In addition to that, Thia-EI offers more flexibility in terms of creating and selecting different EPs. On Q2, due to the limited flexibility of Thia-Multi, it has lower execution time and also lower accuracy than Thia-EI.
The cons of using multiple EPs with Fine-Grained Planning is the increase in optimization time. This is because the Optimizer has to evaluate all EPs to choose an optimal EP. As illustrated in Figure 14, the optimization time of Thia-EI and Thia-Multi is consistently higher than that of Thia-Single. Increasing this flexibility (i.e., adding more EPs) leads to higher sampling overhead. Thus, Thia-EI has higher optimization time than Thia-Multi and both have higher optimization time than Thia-Single. This motivates the need for reducing the optimization time.

Impact of Exit Point Estimation
Training Time. Since the Optimizer needs to train an estimation model for every unique query, we first quantify the training overhead of the Exit Point Estimation technique. Figure 15 shows the variation in validation accuracy over training time. The model quickly converges since the Thia uses a small training set (200 samples) and a two-layer neural network for Exit Point Estimation. It takes less than 5 seconds (0.1% of total processing time) to train each of these models for all queries.
optimization time. We next investigate the efficacy of the Exit Point Estimation technique in reducing the optimization time.
We integrate the Exit Point Estimation technique into Thia-EI to construct Thia. Using the Exit Point Estimation technique, Thia is able to directly predict an appropriate EP to use for a chunk.
In contrast, Thia-EI runs inference using all EPs during optimization phase to select the EP. As shown in Figure 14, Thia cuts the optimization time in half. Recall that Thia uses the object detection EPs for Fine-Grained Planning. So, the Exit Point Estimation technique uses the backbone features for choosing a plan for each chunk. We also measure the overhead of using Exit Point Estimation. This technique introduces a minimal additional overhead (18 s) even under the highest sampling rate (processing time is in order of thousands of seconds).
execution time. Lastly, we discuss the impact of the Exit Point Estimation technique on planning accuracy (i.e., choosing the optimal EP) and execution time. We measure the planning accuracy relative to Thia-EI. In Table 5, Under and Over represent the percentage of chunks for which the Exit Point Estimation technique returns a shallower EP and a deeper EP than that returned by Thia-EI. While shallower estimates hurt query accuracy, deeper estimates increase execution time. As shown in Figure 14, execution time increases only negligibly for all queries except for Q1. Since the Exit Point Estimation technique reduces optimization time, the total processing time of Thia is lower than that of Thia-EI on all queries except for Q1. This is because Q1 can be accurately answered using the first EP (Figure 10), so deeper estimates increase execution time. We discuss the impact on query accuracy in §7.7.

End-to-End Comparison
We report the speedup, precision, and recall metrics with respect to other state-of-the-art systems in Figure 16. The bars on the left side represent three systems: (1) Naive, (2) BlazeIt, and (3)   latter two video analytics systems use specialized models. The bars on the right side represent variants of Thia that use one or more techniques presented in this paper. The most notable observation is that systems that have access to a set of EPs deliver higher performance than those that have access to a single EP. Unlike Thia-Multi, which maintains a collection of separate models, the Early Inference technique offers more flexibility in choosing the optimal EP. However, this technique increases the optimization time. We overcome this limitation using the Exit Point Estimation technique.
Thia consistently delivers higher speedup than other systems. Due to the inaccuracy of the Exit Point Estimation technique, Thia has a minimal drop in accuracy. The drop in recall is more prominent because shallow EPs are unable to recognize hard-todetect events, which leads to more false negatives. In contrast, the drop in precision is minimal. On Q1, Thia improves both precision and recall. This is because the Optimizer augmented with the Exit Point Estimation technique overestimates the EPs for this query, leading to an improvement in accuracy.

Model Cascade vs. Early Inference
As we mentioned in §2.3, Thia-Multi uses a model cascade [1]. It differs from the naive model cascade technique in that it uses Fine-Grained Planning to select EPs. In contrast, a naive approach determines whether to stop at an EP based on the a confidence score of the prediction from the previous EP. Thia-Multi outperforms the naive approach since shallower EPs in the model cascade are always executed with the latter technique. As a result, our Early Inference based systems (i.e., Thia-EI and Thia) outperform the model cascade approach. Since it is challenging to construct a confidence-score based system in the case of object detection, we show the projected performance of the model cascade approach compared to Thia-EI and Thia in Figure 17. The Early Inference based system delivers 2× speedup compared to model cascade.
Using multiple models to construct model cascade also increases the memory footprint of the system. As shown in Figure 18, the realtime memory usage of a model cascade increases when we increase the number of EPs. It has a 5 GB memory footprint with 5 EPs. In contrast, since the Early Inference model shares parameters and inference features, it only incurs a 2 GB memory footprint for the same number of EPs.

Optimality of Fine-Grained Planning
We now examine the quality of the query plans relative to the optimal plan by comparing the execution speedup. The optimal plan is constructed using a brute-force EP selection on every frame (i.e., chunk size = 1). The optimal plan is un-achievable in reality because the brute-force selection on every frame significantly increases optimization time. The results are shown in Figure 19. The plans constructed by the Optimizer are 0.3× slower than the optimal plan. So, there is still potential for improving the quality of the query plans. We plan to explore techniques for doing so with a tolerable impact on optimization time in the future.

Limitations
Accuracy of Exit Point Estimation model. The Exit Point Estimation technique uses a simple neural network to model the optimal EPs distribution. However, the inaccuracy of this model leads to a minimal drop in overall query accuracy. We plan to study other techniques to reduce the optimization time in the future. For example, instead of using a deep learning model, a lightweight statistical estimator may be sufficient. A challenge with this approach is that this estimator must accurately map all of the parameters returned by the object detection model (e.g., a set of bounding boxes and confidence scores) to the appropriate EP.
Query Support. Currently, Thia supports a limited set of queries. To support general-purpose video analytics, we will need to add support for additional types of queries (e.g., aggregate queries). We plan to integrate the Early Inference and Fine-Grained Planning techniques into the query execution engine and the query optimizer of a full-featured video analytics system in the future.

Related Work
Model Cascade. Researchers in the area of face detection have proposed models that support a set of EPs that are geared for different accuracy and speed trade-offs [19,20]. These models return a binary decision and a confidence score (i.e., whether a face exists). Based on the confidence score, the model chooses the appropriate EP. In contrast, Thia uses the estimator to directly pick the EP.
Query planning. The authors of Chameleon [9] observe that an appropriate query plan is critical to gain high performance and accuracy. Similar to the Fine-Grained Planning technique, it adjusts the execution plan at runtime. To reduce the cost of picking the correct plan, it exploits temporal locality of nearby frames in the video, thereby reducing the profiling cost. To further reduce this cost, it uses a clustering algorithm to explore correlation across videos. Thia instead uses a shallow neural network to directly estimate the optimal EP to use for a chunk.

Conclusion
We presented, Thia, a video analytics system for efficiently processing visual data at scale. Thia leverages the early inference technique to support a range of throughput-accuracy tradeoffs. It then adopts a fine-grained approach to query planning and processes different chunks of the video with different exit points to meet the user's requirements. Lastly, Thia uses a lightweight technique for directly estimating the exit point using a shallow deep learning model to lower the optimization time. We empirically show that these techniques enable Thia to outperform two state-of-the-art video analytics systems by up to 6.5×, while providing accurate results even on queries focusing on hard-to-detect events.