  Recent advances in Computer Vision and Deep Learning made possible the
efficient extraction of a schema from frames of streaming video. As such, a
stream of objects and their associated classes along with unique object
identifiers derived via object tracking can be generated, providing unique
objects as they are captured across frames. In this paper we initiate a study
of temporal queries involving objects and their co-occurrences in video feeds.
For example, queries that identify video segments during which the same two red
cars and the same two humans appear jointly for five minutes are of interest to
many applications ranging from law enforcement to security and safety. We take
the first step and define such queries in a way that they incorporate certain
physical aspects of video capture such as object occlusion. We present an
architecture consisting of three layers, namely object detection/tracking,
intermediate data generation and query evaluation. We propose two
techniques,MFS and SSG, to organize all detected objects in the intermediate
data generation layer, which effectively, given the queries, minimizes the
number of objects and frames that have to be considered during query
evaluation. We also introduce an algorithm called State Traversal (ST) that
processes incoming frames against the SSG and efficiently prunes objects and
frames unrelated to query evaluation, while maintaining all states required for
succinct query evaluation. We present the results of a thorough experimental
evaluation utilizing both real and synthetic data establishing the trade-offs
between MFS and SSG. We stress various parameters of interest in our evaluation
and demonstrate that the proposed query evaluation methodology coupled with the
proposed algorithms is capable to evaluate temporal queries over video feeds
efficiently, achieving orders of magnitude performance benefits.
