Lune

VLDB2024Top-tier venue

Optimizing Video Selection LIMIT Queries With Commonsense Knowledge

Wenjia He, Ibrahim Sabek, Yuze Lou, Michael J. Cafarella

Abstract

Video is becoming a major part of contemporary data collection. It is increasingly important to process video selection queries --- selecting videos that contain target objects. Advances in neural networks allow us to detect the objects in an image, and thereby offer query systems to examine the content of the video. Unfortunately, neural network-based approaches have long inference times. Processing this type of query through a standard scan would be time-consuming and would involve applying complex detectors to numerous irrelevant videos. It is tempting to try to improve query times by computing an index in advance. But unfortunately, many frames will never be beneficial for any query. Time spent processing them, whether at index time or at query time, is simply wasted computation.

We propose a novel index mechanism to optimize video selection queries with commonsense knowledge. Commonsense knowledge consists of fundamental information about the world, such as the fact that a tennis racket is a tool designed for hitting a tennis ball. To save computation, an inexpensive but lossy index can be intentionally created, but this may result in missed target objects and suboptimal query time performance. Our mechanism addresses this issue by constructing probabilistic models from commonsense knowledge to patch the lossy index and then prioritizing predicate-related videos at query time. This method can achieve significant performance improvements comparable to those of a full index while keeping the construction costs of a lossy index. We describe our prototype system, Paine, plus experiments on two video corpora. We show our best optimization method can process up to 97.79% fewer videos compared to baselines. Even the model constructed without any video content can yield a 75.39% improvement over baselines.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Jointly Optimizing Preprocessing and Inference for DNN-based Visual Analytics cites BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Approximating Opaque Top-k QueriesJiwon Chang, Fatemeh NargesianSIGMOD 2025 · 2 citations

Builds on13

  1. Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
  2. HowTo100M: Learning a Text-Video Embedding by Watching Hundred Million Narrated Video ClipsAntoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi et al.ICCV 2019 · 1,437 citations
  3. BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video AnalyticsDaniel Kang, Peter Bailis, Matei ZahariaVLDB 2020 · 103 citations
  4. MIRIS: Fast Object Track Queries in VideoFavyen Bastani, Songtao He, Arjun Balasingam, Karthik Gopalakrishnan et al.SIGMOD 2020 · 68 citations
  5. Jointly Optimizing Preprocessing and Inference for DNN-based Visual AnalyticsDaniel Kang, Ankit Mathur, Teja Veeramacheneni, Peter Bailis et al.VLDB 2021 · 50 citations

Related papers

  1. ExSample: Efficient Searches on Video Repositories through Adaptive SamplingOscar R. Moll, Favyen Bastani, Sam Madden, Mike Stonebraker et al.ICDE 2022 · 16 citations
  2. QaVA: Query-Aware Video Analysis Framework Based on Data Access PatternTianxiong Zhong, Zhiwei Zhang, Yihang Fu, Guo Lu et al.ICDE 2025 · 1 citation
  3. Joint Commonsense and Relation Reasoning for Image and Video CaptioningJingyi Hou, Xinxiao Wu, Xiaoxun Zhang, Yayun Qi et al.AAAI 2020 · 52 citations
  4. Commonsense for Zero-Shot Natural Language Video LocalizationMeghana Holla, Ismini LourentzouAAAI 2024 · 6 citations
  5. FiGO: Fine-Grained Query Optimization in Video AnalyticsJiashen Cao, Karan Sarkar, Ramyad Hadidi, Joy Arulraj et al.SIGMOD 2022 · 37 citations
Dusk over the sea between two cliffs drawn in fine vertical lines