There is now growing interest in organizing and querying large bodies
of video data. In this paper, we will develop a simple SQL-like video
language which can be used not only to identify videos in the library
that are of interest to the user, but which can also be used to extrac
t, from such a video in a video library, the relevant segments of the
video that satisfy the specified query condition. We investigate vario
us types of user requests and show how they are expressed using our qu
ery language. We also develop polynomial-time algorithms to process su
ch queries. Furthermore, we show how video presentations may be synthe
sized in response to a user query. We show how a standard relational d
atabase system can be extended in order to handle queries such as thos
e expressed in our language. Based on these principles, we have built
a prototype video retrieval system called VIQS. We describe the design
and implementation of VIQS and show some sample interactions with VIQ
S. (C) 1996 Academic Press, Inc.