ACCEPTED FOR PUBLICATION: IEEE TRANS. ON KNOWLEDGE AND DATA ENG., VOL. 13, NO. 6, 2001, (IN PRESS)

1

A Query Model to Synthesize Answer Intervals
from Indexed Video Units
Sujeet Pradhan, Member, IEEE , Keishi Tajima, and Katsumi Tanaka, Member, IEEE

I. Introduction

C

ONTINUITY is one of the most distinctive featuresof video data that makes it diﬀerent from other kindsof data. A video data is a seamless continuous sequenceof frames. By this nature of video data, any arbitrary
subsequences of these frames may be meaningful units forindexing as well as for querying. However, there are practical diﬃculties in identifying all such units, which generally causes indexing to be limited to a certain number ofunits only. Traditional frameworks for query processing
thus cannot be applied to video databases. A traditional
database storing non-continuous data, in general, is a setof discrete data. An answer to a query on such a databaseis a subset of the data that satisﬁes the query conditions.
A video database, on the other hand, is a set of video intervals, i.e. a set of continuous sequences. An answer toa query on a video database, in general, is a set of only

Sujeet Pradhan is with the Department of Computer Science and Mathematics, Kurashiki University of Science andthe Arts, 2640 Nishinoura, Tsurajima-cho, Kurashiki, 7128505 Japan.
Phone: +81 86 440–1089, fax: +81 86 440–1062,
e-mail: sujeet@soft.kusa.ac.jp This work was performed while theauthor was with the Graduate School of Science and Technology,
Kobe University, Japan.
Keishi Tajima is with the Department of Computer Science andEngineering, Kobe University, 1-1 Rokkodai-cho, Nada-ku, Kobe
657-8501, Japan. Phone: +81 78 803–6234, fax: + 78 803–6234,
e-mail: tajima@db.cs.kobe-u.ac.jp
Katsumi Tanaka is with the Graduate School of Science andTechnology, Kobe University, 1-1 Rokkodai-cho, Nada-ku, Kobe
657-8501, Japan. Phone: +81 78 803–6226, fax: +81 78 803–6390,
e-mail: tanaka@db.cs.kobe-u.ac.jp

Raw Video Data{

Text Recognition

Some keywords can be extracted from scenarios and closed captions
from Scenarios,
using the latest techniques such as automatic text recognition.

Closed Captions{k1,k2,k3} {k2}{k3}

{k1,k3}{k2,k4}

Speech Recognition
from Audio Data{k5,k6}{k6}{k7,k8}

{k5}
{k8}

k1
k2
k3
k4
k5
k6
k7
k8

ManualAnnotation}

Fragmentary Video
Data Units Augmented
with Keywords

Index Terms—video database, video retrieval, continuous
data, indexing units, interval query, interval operations

certain portions of those continuous sequences.
Generally, there are two diﬀerent approaches to parsing
raw video data into smaller units for indexing. Indexing
schemes which rely largely on automatic parsing decomposes the raw video data into automatically detected shots[4], [29]. On the other hand, works by [8], [18], [27], which
are based on manual annotation, choose arbitrary video intervals deﬁned by so-called semantic boundaries as indexing units. In either of these approaches, the problem that
end-users often face is that the intervals they are hoping
to ﬁnd may not have been deﬁned as answer units in the
database. Automatically detected shots may not be appropriate units for answering a query. On the other hand,deﬁning all semantic boundaries and having all meaningful units ready in the database manually can be hardly
achieved. It is because there is no common consensus onwhat semantic boundaries are. As a result, what is meaningful unit to an annotator may not be meaningful to theuser who issues the query. Therefore, manual indexing islabor intensive and yet may never be complete. All thesethings suggest that there is bound to be discrepancies in
granularity between the indexed units and the intervals tobe retrieved.

Keyword Extraction

Abstract—While a query result in a traditional databaseis a subset of the database, in a video database, it is aset of subintervals extracted from the raw video sequence.
It is very hard, if not impossible, to predetermine all thequeries that will be issued in future, and all the subintervals that will become necessary to answer them. As a result,conventional query frameworks are not applicable to video
databases. In this paper, we propose a new video querymodel that computes query results by dynamically synthesizing needed subintervals from fragmentary indexed intervals in the database. We introduce new interval operations
required for that computation. We also propose methods
to compute relative relevance of synthesized intervals to agiven query. A query result is a list of synthesized intervals
sorted in the order of their degree of relevance.

Fig. 1. Various techniques for keyword extractionc2000
IEEE. Personal use of this material is permitted. However,
permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale orredistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

In order to solve this basic problem, which is highly
prevalent in video databases, we propose a query framework where query results are dynamically synthesized fromthe video units deﬁned in the database. In our framework,

c 2000 IEEE
1041–4347/01$10.00 2

ACCEPTED FOR PUBLICATION: IEEE TRANS. ON KNOWLEDGE AND DATA ENG., VOL. 13, NO. 6, 2001, (IN PRESS)

we assume that keyword information are associated withfragmentary video units in the database. It should be
noted here that such information can be not only added
manually but also can be extracted automatically (seeFig. 1). For example, speech recognizers can automaticallytranscribe video soundtracks [6]. The current state-of-art
also allows one to automatically recognize text captions.
Some video data even have scenarios or textual description added during the production time. Natural language
processing technique can automatically transform all suchtextual information into a set of descriptive keywords [26].
Our framework allows users to formulate queries declaratively by listing a keywords with some quantiﬁers. The
queries thus speciﬁed are transformed into algebraic expressions which will include the query keywords and therespective interval operators. Each query keyword ismatched with the keywords associated with the indexed
video units to produce intermediate result sets. Final answer intervals are then composed by performing interval
operations on the sets of matched video units. Since such a
set of answers may contain plenty of intervals, answers will
be ranked in the order of relative relevance to the query.
The main goal of our research is to design a query mechanism which will enable us to dynamically compute answer
intervals that exist in the raw video data, even though suchintervals are not indexed as answer units in the database.
In order to achieve this goal, we
1. deﬁne new interval operations required to computeanswers,
2. provide a framework for query formulation in whichambiguity in query semantics can be avoided with thehelp of quantiﬁed keywords, and3. present methodologies to rank answers.
The rest of the paper is organized as follows: In Section II, we present some motivating examples behind ourwork. Section III presents comparisons of our work withother related work. Some basic deﬁnitions of indexed video
units and video database are presented in Section IV.
In Section V, we explain our query mechanism in detail. First, we formally deﬁne the syntax of our declarative query. We then deﬁne various interval operations,and show how our declarative queries are transformed into
expressions with those interval operations to compute thequery result. In Section VI, we discuss a couple of methods
to calculate the degree of relevance so that answers can beranked and presented to users in order. Query approximation is presented in Section VII. Finally, in Section VIII
we summarize the main contributions of this paper andpresent some prospects for our further research.
II. Motivation
In the past, query models for video data have been developed with particular annotation models [8], [9], [18],[27] in consideration. The usual approach is to assign attributes or descriptions to arbitrary video units and thendeﬁne several interval operations such as interval union,interval intersection, and interval concatenation in order
to compute video intervals as query results. The opera-

tions proposed in those research works, however, cannot
always produce appropriate intervals that users intend toﬁnd in the ﬁrst place.
Raw Video Data

man
dog

{
{

}
}

Interval1
Interval2
Interval3

Fig. 2. What does a user expect?

For example, consider a query “retrieve video intervals
that show a dog running after a man.” In conventional approaches, a query result is computed by simply taking theintersection between those video units with an attributevalue ‘man’ and those with an attribute value ‘dog’. An
actual scene of ‘a dog running after a man’, however, usually involve lots of camera movements, zooming, and panning. It rarely happens that every frame in that scene
contains both a ‘dog’ and a ‘man’ (see Fig. 2). Some ofthem may show only either of them, and there may be evenframes showing none of them but the road between them.
Therefore, the user who issues this query in the ﬁrst placedoes not necessarily expects a video interval that shows‘dog’ and ‘man’ in every frame throughout its play. Suchan informally phrased query thus can be interpreted in a
number of ways:• Does it mean that the user wishes to ﬁnd contiguousintervals consisting of frames showing either a dog ora man? (See Fig. 2 — Interval 1)• Or does it mean that the user wants to ﬁnd intervals
which start with a frame in which either a man or adog ﬁrst appears and end with the ﬁnal frame in which
either one of them emerges? (See Fig. 2 — Interval 2)• Or does it mean that the user is focusing on the dog,
and his intention may be intervals with a dog in every frame and a man in some frames? (See Fig. 2 —Interval 3)
Producing appropriate intervals from the actual video
data for even what seems to be such a simple query asks
for new interval operations. Our goal is to develop sucha set of operations that can compute answers to queries
on a video database. For example, in order to generate ananswer such as Interval 2 (See Fig. 2), we deﬁne a novel
operation called extended union. It should be noted herethat the usual union operation can produce the Interval 1
but not the Interval 2.
Specifying a query using those operations on video intervals, however, is not what an end-user would like to do.
We therefore deﬁne a framework where end-users can formulate their queries by simply specifying a list of keywords
with some quantiﬁers. This list of keywords with quantiﬁers declaratively speciﬁes the condition for the query re-PRADHAN ET AL.: A QUERY MODEL TO SYNTHESIZE ANSWER INTERVALS FROM INDEXED VIDEO UNITS

sult. For example, the Interval 3 can be obtained by specifying the query as ((dog)∀ ∧(man)∃ ). Our query mechanism
translates the keywords into appropriate query expressions
composed of our interval operations.
One problem in applying such a query framework is theexistence of noise or the frames that cannot be matchedwith a query. For example, suppose we want to ﬁnd acontiguous interval consisting of frames showing either aman or a dog. In the actual video, however, as we mentioned above, there may be a short sequence of frames
showing only the road between them. If we strictly interpret the semantics of the query, an interval that includes
those frames inside it, is not considered contiguous, andtherefore will not be included in the query result. In practical applications of video databases, however, such a strict
interpretation of the query semantics makes little sense.
Raw Video Data

man {
dog

}
}

{

Interval1

Interval2

Interval3

Fig. 3. Three unequal video interval answers

Consider the video data shown in Fig. 3 where arbitrary
video units are indexed by the keywords ‘man’ and ‘dog’.
Suppose there are actually three diﬀerent scenes of the dog
running after the man. Then for a query “retrieve videointervals that show either a dog or a man”, if we follow
the strict semantics of the query, then it is clear that only
the ﬁrst two video intervals can be taken as the deﬁnite
answer to this query. If, however, we relax the semantics of the query, then many intervals can be considered as
possible answers. Intuitively, one can say that not all ofthese answers will be equally important to the user. Considering the three most relevant intervals as shown in theFig. 3, one can intuitively say that the ﬁrst video interval
is preferable to the second and the second is preferable tothe third one. However, such reasoning without any theoretical background is not suﬃcient to estimate the query
response. We need to develop these intuitive notions into
a consistent, useful methodology for query formulation,
query processing, estimating relevance among the answers,
and ranking output for presentation to a user.
Another problem that normally arises is from the discrepancy between the user who submits the query and theannotations that are actually stored in the database. For
this discrepancy, it is often the case in video databasesthat there does not exist any answer intervals that exactly
match with a given query formula even though there may
be intervals that conceptually fulﬁll the users’ purpose. We
thus propose a query evaluation method based on approximation. When a query is issued and the result would bean empty set, the condition given in the query is relaxed3

and reformulated.
III. Related Work
There is now growing interest in querying the large resources of digital video data. Allen’s work on temporal intervals [1] laid the foundation for many researches
concerned with time intervals [14], [15]. He showed that
there are 13 distinct temporal relationships that can exist between two arbitrary time intervals. Video datais also temporal although not in the traditional sense[7]. Some researches on video databases have thus been
greatly inﬂuenced by Allen’s temporal model. In [14],temporal-interval-based models have been presented fortime-dependent multimedia data such as video. Our work,
however, has mainly focussed on the operations for synthesizing new intervals but not on the relationship between
given intervals. Therefore, our work and those work on
interval relationships are orthogonal. As we saw in the example above, in any meaningful video interval, the same
keyword may emerge for an indeﬁnite number of times inno particular order. Some further investigation is requiredin order to integrate the condition speciﬁcations based on
their temporal relationships and the interval operations
into one query language. This issue will be considered in
our future work.
Over the past few years, researchers around the world
have developed systems which are capable of providing
database support to video data [7], [9], [18], [27]. We review some of them brieﬂy below. It should be noted herethat none of the systems described below have deﬁned operations that can synthesize possible answer intervals to aquery from the existing video units.
A. OVID
Object Video Database (OVID) [18] is an instance-based
video database system. In OVID, an arbitrary set ofcontiguous intervals can be deﬁned as a meaningful entity, which they call a video object. Inheritable and noninheritable attributes can be assigned to those video objects. Inheritable attributes are shared between objects on
the basis of interval-inclusion relationship between them.
The basic idea is to let video objects share inheritable attributes with their parent video object and relieve someburden of the manual annotation process.
Our objective is diﬀerent from that of OVID. In OVID, a
special emphasis has been put on annotation model rather
than on query model. It also assumes that all meaningfulinterval units are predeﬁned manually and stored in the
database. However, as stated above, what is meaningful
to a person who annotates the video data may not necessarily be meaningful to the one who issues the query.
Furthermore, the operations deﬁned in OVID cannot compute contiguous intervals if two input intervals are neither
overlapping nor adjacent.
B. Algebraic Video
Algebraic video data model [27] is based on stratiﬁcation
approach [23]. Unlike simple stratiﬁcation, however, in the

4

ACCEPTED FOR PUBLICATION: IEEE TRANS. ON KNOWLEDGE AND DATA ENG., VOL. 13, NO. 6, 2001, (IN PRESS)

algebraic video model, they can deﬁne the hierarchical relationship between descriptions that are associated withthe same video data. Parent nodes in the hierarchy represent the context of their child nodes. By this hierarchy,
they can attach multiple views with diﬀerent context tothe same video data.
Their work also focuses on an annotation model rather
than on a query model. Annotation should be done very
carefully in order to ensure that answers are available forany kind of query. It also puts an extra burden on annotators to deﬁne relationships between descriptions. Deﬁning
all possible interval answers in advance in the indexing
scheme, however, is not our approach in the ﬁrst place.
C. VideoSTAR
VideoSTAR [8] is another video database project developed at Norwegian Institute of Technology. A genericmodel to support both the structural indexing and contents indexing has been proposed. Various interval-based
and set-based operations have been deﬁned as well. Three
diﬀerent kinds of descriptions — basic, primary and secondary — based on the context in which they appear canbe associated with a video data. Video documents canbe composed from various sources of video data and only
those descriptions that are contextually related will be inherited by the newly composed documents. Their work isalso focussed more on building a perfect annotation model
for indexing which makes the system even more complex.
As far as the query processing is concerned, no operations
have been deﬁned to compute contiguous intervals fromtwo non-contiguous and non-overlapping intervals.
D. VIQSVideo Query System of VIQS [9] also deﬁnes a SQL-typeof query language. It includes operations for determining
whether two intervals of video overlap each other. Other
operations include union, complement and intersection operations. Set iteration operations such as FORALL and
FOREACH can also be performed. Users can provide parameters to choose whether to see a single frame, a frameof certain length or the complete sequence of frames. The
answer presentation module is provided to merge diﬀerent
video-segments that are retrieved as answers to a query.
This work also lacks the algebraic operations required forour purpose.
E. Informedia
Informedia project [26] uses techniques such as image processing, speech recognition, text recognition and language
understanding to automatically parse visual, audio andtextual information contained in video data. Video paragraphs are the units that are returned as answers to any
query. Key frames are dynamically generated on the basisof query terms for answer presentation. Full text information retrieval (IR) system based on well-known techniqueof tf/idf (term frequency/inverse document frequency) has
been used for keyword-based queries.

In an another IR-based approach, [22] has proposed aninteractive retrieval process of video and still images using term weighting, relevance feedback and result ranking.
Most of the studies that have been conducted in the ﬁeldof information retrieval are concerned with textual documents. Unlike textual documents, however, there is nocommon consensus on basic indexing units for video documents in general. This is the main reason why IR models
cannot be directly adapted to video data. In video databases, keywords can be associated with only fragmentary
video units, and that makes it necessary to dynamicallysynthesize video intervals from those fragmentary intervals
to answer queries.
IV. Video Indexing
There are two general approaches to associate descriptive
information about the contents of video data — segmentation approach and stratiﬁcation approach. The segmentation approach [13], [22], [24], [29] physically divides the raw
video data into shots, scenes etc. Annotation models basedon this approach are focussed speciﬁcally on the structural
information of video data. This approach is straightforward and query processing is rather easy. There, however,
have been many criticisms of this approach for its inﬂexibility and inability to segment the contextual information[18], [23], [27] contained in video data.
The stratiﬁcation approach, on the other hand, is basedon a layered annotation representation model which segments contextual information of the video [23]. The basic
idea is not to segment video data but to segment descriptions. Each description is called a stratum that refers toa sequence of video frames. The strata may overlap or
totally encompass each other. There already exist many
annotation models based on this approach [18], [19], [27] .
Various information such as closed caption, the resultof speech recognition, and manual annotation can be combined and used as the source of annotation information as
illustrated in Fig. 1. No matter whether such information
are extracted automatically or added manually, we believe,
they can be associated with only fragmentary video units.
However, these units may not be the ones what end-users
are hoping to retrieve. As a result, meaningful intervals,
which are not necessarily deﬁned in the database, need tobe computed in demand with the help of available indexed
units. This will allow us to compute interval answers, thatmay possibly exist in the raw video data, even though suchanswer units are not indexed in the database.
Before we deﬁne and discuss our query mechanism, here
we deﬁne the model of video annotations and video databases that we use as the base of our development. A video
database, in general, is a collection of raw video streams.
For the sake of simplicity, here we consider a single raw
video stream.
Definition 1: A video stream F is a nonempty ﬁnite
set of frames f1 , f2 , . . . , fn , which is a totally ordered set
with respect to < as f1 < f2 < . . . < fn .
Definition 2: If fs , fe ∈ F and fs < fe , then a videointerval I[fs , fe ] over F is the set of frames {fk ∈ F | fs ≤

PRADHAN ET AL.: A QUERY MODEL TO SYNTHESIZE ANSWER INTERVALS FROM INDEXED VIDEO UNITS

fk ≤ fe }.
fs and fe of I[fs , fe ] are the starting frame and the ending
frame, and they are denoted by start(I) and end(I) respectively. A video interval is thus a stream of contiguous
frames and is uniquely deﬁned by its start frame fs andend frame fe . An interval is denoted by I[fs , fe ] or simply
by I wherever [fs , fe ] can be omitted. I(F ) denotes theset of all intervals over F .
Definition 3: An interval I1 ∈ I(F ) is said to be
identical to another interval I2 ∈ I(F ), iﬀ start(I1 ) =start(I2 ) ∧ end(I1 ) = end(I2 ).
We denote I1 = I2 to denote I1 is identical to I2 . We also
denote I1 = I2 to denote I1 is not identical to I2 .
Definition 4: An interval I  ∈ I(F ) is said to be subinterval of another interval I ∈ I(F ), if (start(I  ) ≥start(I) ∧ end(I  ) ≤ end(I)) ∧ (I  = I).
We denote I  ⊂ I to denote I  is a sub-interval of I.
Now a video description database VD for a video F isdeﬁned as a set of video descriptions for F and has thefollowing form:
VD = {(k1 , I1 ), (k2 , I2 ), . . . , (kn , In )}where each (ki , Ii ) is a unit video description for a video
F . Each k in a unit description is a single keyword and I
is an element of I(F ). Intuitively, here we denote (k, I) tosuggest that the information described by the keyword kemerges everywhere throughout the video interval I[fs , fe ],that is:(k, I) means ∀f ∈ I[fs , fe ].(k emerges in f )V. Query Mechanism
Querying a video database is diﬀerent from querying a traditional database. The semantics of query mechanism in a
traditional database are obvious. Query conditions are deﬁned by using primitive predicates and boolean operations(and, or, not), and the answer of the query is a set ofdata items satisfying the given condition. Even when someconstructors are used for creating new data structure, they
are simply evaluated for all combinations of those selected
data items. It does not add any complexity to the phaseof data item selection. The answer of the query is thus
always uniquely deﬁned, and no ranking is necessary because the data items in the answer are equally important.
However, this is not the case when we are dealing withvideo database query processing. One particular reason isthat there may not exist any predeﬁned units of video intervals that can be directly returned as answers to a user.
As a result, the answers to a query need to be synthesized
dynamically using the fragmentary video units annotatedwith the pieces of information. In some cases, however, nointervals can be claimed as the best answer to a query. In
those cases, the best we can do is to return a set of intervals which are likely to satisfy the users’ need. In such aquery result, all the intervals may not be equally relevant
since some intervals may satisfy the query condition moreclosely than others. A ranking strategy thus must be applied in order to present the answers to a user in the best
possible manner.

5

Query Formulation(in a declarative way)a list of keywords with quantifiers

Query Transformation(algebraic expressions)
keywords and interval operators

Answer Generation(keywords matching and operations)a set of intervals

Ranking(calculation of relevance)
a list of ranked intervals

Fig. 4. A framework for our query mechanism

Our query mechanism can be summarized as shown in
the Fig. 4. Users formulate queries by listing a keywords
with quantiﬁers in a declarative way. The queries thus
speciﬁed are transformed into algebraic expressions. These
expressions will include the original keywords and the respective interval operators which we are going to deﬁnelater in this paper. The keywords speciﬁed in the query
are matched with the keywords associated with the indexed video units. Interval operations are performed on
the matched video units in order to generate answer intervals. The answers thus computed are ﬁnally ranked forpresentation to the users.
A. Query Formulation
We assume that users are interested in retrieving contiguous video intervals having some contextual meaning rather
than bits and pieces of frames, or concatenation of shortintervals collected from diﬀerent parts of the video. We
also assume that the most likely form of users request is“find me contiguous video intervals in which a cyborg isfighting with a monster ”. This kind of user’s request canbe represented in the following query form:
Cyborg ∧ Fight ∧ Monster
However, a user’s intention, as mentioned in the Section II,
is ambiguous in this form of query. The simplest interpretation may be the intersection of intervals with those keywords. In an actual video database, however, there may exist no video units in which all of the three keywords appear
together at all. Even if there does exist such units, they
may have lost the context of the actual scene since such
units are usually fragmentary. Therefore, the more likelyinterpretation of the above query will be “video intervals

6

ACCEPTED FOR PUBLICATION: IEEE TRANS. ON KNOWLEDGE AND DATA ENG., VOL. 13, NO. 6, 2001, (IN PRESS)

in which each keyword cyborg, fight, monster emerges
somewhere at least once”, or “contiguous video intervals
in which at least one of these keywords emerge in every
frame.
In order to allow users to specify their intention clearlyand declaratively in queries, we introduce new operatorsand deﬁne a new query syntax as follows:q ::= (k1 • k2 • . . . • kn )∃ | (k1 + k2 + . . . + kn )∀ | q ∧ q | q ∨ q∧ and ∨ are the usual logical conjunction and disjunction.
The meanings of the other two constructs are as follows:
1. (k1 • k2 • . . . • kn )∃ — this means that all keywords ki
must emerge simultaneously somewhere in the answer
interval. That is, this query speciﬁcation requires thatan answer interval I[fs , fe ] should satisfy the following
condition:∃f ∈ I[fs , fe ].∀i ∈ {1, . . . , n}.(ki emerges in f )2. (k1 + k2 + . . . + kn )∀ — this means that at least
one of k1 , . . . , kn must emerge everywhere, i.e. in every frame, in the answer interval. That is, this query
speciﬁcation requires that an answer interval I[fs , fe ]should satisfy the following condition:∀f ∈ I[fs , fe ].∃i ∈ {1, . . . , n}.(ki emerges in f )Readers may think that (k1 •. . .•kn )∀ and (k1 +. . . +kn )∃are also necessary. However, they are not needed because
the following equivalence holds:(k1 • . . . • kn )∀(k1 + . . . + kn )∃≡≡(k1 )∀ ∧ . . . ∧ (kn )∀(k1 )∃ ∨ . . . ∨ (kn )∃The equivalence above is obvious because they correspondto the following theorem in the predicate logic:∀x.P (x) ∧ Q(x) ≡∃x.P (x) ∨ Q(x) ≡(∀x.P (x)) ∧ (∀x.Q(x))(∃x.P (x)) ∨ (∃x.Q(x))

Readers may also notice that both • and ∧ mean conjunction, and both + and ∨ disjunction. In this paper, however,
we use diﬀerent symbols depending upon whether they areused inside or outside of the quantiﬁers ∃ and ∀ . The reason is, as we explain later, they need diﬀerent processing
during the answer computation.
As a result, the general form of the query composed ofthose constructs can be expressed as below:∨∨(k • . . . • k)∃ ∧ . . . ∧ (k • . . . • k)∃ ∧(k + . . . + k)∀ ∧ . . . ∧ (k + . . . + k)∀∃(k • . . . • k) ∧ . . . ∧ (k • . . . • k)∃ ∧(k + . . . + k)∀ ∧ . . . ∧ (k + . . . + k)∀..
.
(k • . . . • k)∃ ∧ . . . ∧ (k • . . . • k)∃ ∧(k + . . . + k)∀ ∧ . . . ∧ (k + . . . + k)∀

As in usual expressions with ∧ and ∨, we consider that ∧has priority to ∨ during the evaluation.
Let us consider some example queries:

1. (Cyborg)∃ ∧ (Fight)∃ ∧ (Monster)∃
2. (Cyborg • Monster)∃ ∧ (Mountain) ∀3. (Cyborg + Monster)∀ ∧ (Cyborg • Shoot)∃
4. (Cyborg)∃ ∧ (Fight)∃ ∧ (Mountain) ∀5. (Cyborg)∀ ∧ (Monster) ∀ ∨ (Fight)∀
Intuitively, these queries can be interpreted as follows
respectively:
1. “find me video intervals in which each cyborg andmonster appears somewhere and fighting is taking
place somewhere”.
2. “find me video intervals in which the mountain appears throughout the scene and somewhere in the scene
cyborg and monster appear together”.
3. “find me video intervals in which either the cyborg
or the monster appear everywhere and somewhere in
the scene cyborg is seen shooting”.
4. “find me video intervals in which the mountains appear everywhere and the cyborg and the monster appear somewhere but not necessarily together”.
5. “find me video intervals in which both cyborg andmonster appear throughout the scene or fighting hastaken place throughout the scene”.
B. Interval Operations
To formally deﬁne the operational semantics of the queries
speciﬁed by a user, we ﬁrst need to deﬁne video operations
on intervals and sets of intervals. These operations deﬁned
below will eventually be used to compute the interval answers from video units indexed in the database.
As stated before, a video interval is represented by aset of frames. Therefore, the set-theoretic operations canbe applied to video intervals. Previous works on video
databases have also deﬁned variants of such set operations[7], [18]. However, some operations have been modiﬁed
and some additional operations that will be relevant toour query mechanism will be introduced as well.
For the sake of clarifying the motivation behind ourwork, we have been using the term video units to referto the stored intervals and answer intervals to refer to thecomputed answers to a video query. Hereafter, unless such
distinction is necessary, we will simply use the term interval to refer to any video data whether they are the stored
video units, the intermediate results yielded by interval
operations or the resulting ﬁnal answers to a query.
B.1 Interval Set Union
Given two sets of video intervals X and Y such that X ⊆I(F ) and Y ⊆ I(F ), the operation interval union () on
these sets yields a single set of video interval S as follows:
X  Y = {I[fs , fe ] | (∀f ∈ I.∃I  ∈ X ∪ Y.f ∈ I  )∧(∀I  ∈ X ∪ Y.fs−1 ∈ I  ∧ fe+1 ∈ I  )}This operation takes input from two sets of intervals, which
may contain overlapping and several adjacent intervals,
and produces a single set of non-overlapping contiguousintervals. Adjacent intervals are concatenated to produce
a single contiguous interval. Thus supposing there are twoPRADHAN ET AL.: A QUERY MODEL TO SYNTHESIZE ANSWER INTERVALS FROM INDEXED VIDEO UNITS

sets of video intervals X = {I1 [10, 20], I2[30, 40]} and Y ={I3 [15, 35], I4[45, 55]}, then X Y = {I5 [10, 40], I6 [45, 55]}.
B.2 Extended Union
Given two video intervals I1 and I2 over I(F ), the operation extended union (⊕) on these two video intervals yields
a single video interval I as follows:
I1 ⊕ I2 = I[fs , fe ] where
fs = min(start(I1 ), start(I2 )) andfe = max(end(I1 ), end(I2 )).
This operation takes two intervals as input and produce asingle contiguous interval. The resulting interval will be
contiguous no matter whether the input intervals are adjacent , overlapping, or nonoverlapping and nonadjacent. Weemphasize here that the various interval operations deﬁned
in [7], [9], [18], [27] are unable to do that. Thus supposing
there are two video intervals I1 [10, 20] and I2 [30, 40] thenI1 ⊕ I2 = I[10, 40].
B.3 Set Extended Union
This is the set variant of the extended union operation.
Given two sets of video
 intervals X and Y , the operation
set extended union ( ) returns a set of video intervals
yielded by the pairwise extended union (⊕) between theelements of the two input sets.

X Y = {x ⊕ y | x ∈ X, y ∈ Y }
where {i1 , i2 , . . . , in } = i1 ⊕ . . . ⊕ in .
This deﬁnition can be expanded as:
X Y = (X Y ) ∪ (X X Y ) ∪ (X Y Y ) ∪  (X X X Y ) ∪  (X X Y Y ) ∪  (X Y Y Y ) ∪..
.
Suppose we have two sets of intervals X = {x1 , x2 , x3 } andY = {y1 , y2 } with three and two elements respectively as
shown at the top of the Fig. 6. Intervals I2 ,. . . ,I7 , shown at
the bottom of the ﬁgure, are yielded by applying extended
union to diﬀerent pairs of intervals — each pair consistingof one element from X and one from Y . The same operation yields interval I1 when performed on an interval set
consisting of the two rightmost elements x2 and x3 fromX and one element y2 from Y . Interval I8 is yielded when
performed on another interval set that consists of at least
two extreme elements x1 and x3 from X and either one
or both of the elements from Y . We may also consider
other combinations but the result will be one of the eightintervals I1 , . . . , I8 .

Fig. 5 shows an example of the operation. Supposing
we have two sets of intervals X = {x1 , x2 , x3 } and Y ={y1 , y2 } with three and two elements respectively as shownin the top of the ﬁgure, X ⊕ Y yields a set of six intervals
I1 , . . . , I6 as shown at the bottom of the ﬁgure.

X ={
Y ={

X⊕Y=

x1

x2

y1

y2

{

I1
I2
I3
I4
I5
I6

x3

}
}

}

Fig. 5. Set Extended Union

B.4 Powerset Extended Union
Given two sets of video intervals
X and Y , the operation
powerset extended union ( ) returns a set of video intervals. These intervals are yielded by applying extended
union (⊕) to an arbitrary number (but not 0) of elements
in X and Y . Formally, it is deﬁned as follows:
X Y = { (X  ∪ Y  ) |X  ⊆ X, Y  ⊆ Y, X  = ∅, Y  = ∅}

7

X ={
Y ={

X⊗Y=

x1

x2

y1

y2

{

I1
I2
I3
I4
I5
I6
I7
I8

x3

}
}

}

Fig. 6. Powerset Extended Union of X and Y

Although the powerset extended union seems to be acomplex operation, its excellent property allows us to establish a simpler and more eﬃcient deﬁnition. A closer
study reveals that the same operation can be computed by
the formula below.
  
X Y = (X X) (Y Y )The transformation of the powerset extended union into
three pairwise extended union operations is possible because both extended union and pairwise extended union
hold certain algebraic properties. Readers are suggested
to refer to our more recent publication for the details ofthese properties [21]. Here we give only an intuitive explanation. Since extended union operation between two
intervals returns the minimal interval that contains both

8

ACCEPTED FOR PUBLICATION: IEEE TRANS. ON KNOWLEDGE AND DATA ENG., VOL. 13, NO. 6, 2001, (IN PRESS)of the input intervals, any other intervals encompassed by
the two input intervals will also be contained in the resulting interval. As a result, when an interval set 
performs set
extended union operation on itself such as X
X, the resulting set will have already contained all the intervals thatwould have been yielded by performing the same operation
inﬁnitesameinterval
 numberof times
 on the set. Formally,
X
X =
X
X
X = X
X
. . . X. This alsomeans X
X will yield all the intervals that extended
union can yield when applied on one or
moreelements
in X.
We
can
also
prove
that
both
(X
Y ) and   X(XYY ) are subsetsof (X X YY ). Therefore, the operation (XX) (YY ) produces
 thesame set of intervals as would be produced byXY.
In Fig.7, the operations (X X) and (Y Y ) produce
two sets consisting six and three intervals respectively. Further set extended union operation on these two sets yields
eight intervals I1 , . . . , I8 which is the same set of resultsthat is obtained using its original deﬁnition (See Fig.6).

X ={
Y=

x1

x2

y1

y2

x3

}

{

}

{

}

Y⊕Y=

(X ⊕ X) ⊕ (Y ⊕ Y) =Fig. 7. Property of Powerset Extended Union

B.5 Interval Intersection
Given two video intervals I1 and I2 over I(F ), the twovideo intervals I1 and I2 are said to be intersecting iﬀ∃f.f ∈ I1 ∧ f ∈ I2 , that is, max(start(I1 ), start(I2 )) ≤min(end(I1 ), end(I2 )). The operation interval intersection() on any two arbitrary video intervals yields a single
video interval I as follows:
I1  I2 I[fs , fe ]=
undeﬁned

This is the set-variant of interval intersection operation.
The interval set intersection ( ) operation on two setsof video intervals X and Y returns a set of video intervals constituting of the pairwise interval intersection ()between the elements of the two input sets.

X Y = {x  y | x ∈ X, y ∈ Y, x and y intersect}
B.7 Intersect Test
The intersect test operation () on two sets of video intervals X and Y returns a subset of X including only intervals
in X that intersect with at least one interval in Y .
XY = {x ∈ X | {x} Y = ∅}

X ={
Y ={

x1
y1

x2
y2

x2
y3

}
}

}

{

X⊕X=

B.6 Interval Set Intersection

if I1 and I2 are intersecting
otherwise

where fs = max(start(I1 ), start(I2 )) and fe =min(end(I1 ), end(I2 )). Thus supposing there are two videointervals I1 [10, 20] and I2 [15, 40] then I1  I2 = I[15, 20].
However, for I1 [10, 20] and I2 [25, 40], I1  I2 does not produce any interval.

XΘY=

{

}

x1
x2

Fig. 8. Intersect Test between X and Y

For example, in Fig. 8, both X and Y has three elements{x1 , x2 , x3 } and {y1 , y2 , y3 } respectively. However, X  Ywill include only two intervals x1 and x2 , because x3 does
not intersect with any of the intervals y1 , y2 or y3 in Y .
C. Query Semantics
Having deﬁned a set of video operations, now we formallydeﬁne the operational semantics of the queries. Intuitively(but not strictly), the semantics of a query is deﬁned on
the basis of the following policies. The answer to a query
includes those intervals such that:
1. they satisfy the condition speciﬁed in the query, and2. they are as short as possible, that is, no other subintervals contain the same number of indexed video
units associated with the keywords given in the query.
Next we deﬁne the semantics of queries step by step
starting from a simple query, and ﬁnally showing the semantics of queries in general form.
C.1 Single Term Queries
Single term queries are those that contain only a single
term with a single quantiﬁer. As explained before, there
are two kinds of simple queries.
1. (k + . . . + k)∀
2. (k• . . . •k)∃
The answer to simple queries are deﬁned as follows. In thefollowing deﬁnitions, [[q]] denotes the answer to a query q.
[[(k)∀ ]] =[[(k1 + . . . + kn )∀ ]] ={I|∃(k, I) ∈ VD}[[k1 ]]  . . .  [[kn ]]PRADHAN ET AL.: A QUERY MODEL TO SYNTHESIZE ANSWER INTERVALS FROM INDEXED VIDEO UNITS(k1, I1[50,150])(k1, I2[210,350])(k2, I3[100,200])

S1 =(k2, I4[300,400])

I2[210,350]

I1[50,150]{

9I5[50,350]}

Intermediate Sets of Intervals

S2 =I3[100,200]{

I4[300,400]
I6[100,400]}

IA [50,200]1
IA [100,350]
2
IA [50,350]
3
IA [100,400]
4
IA [210,400]
5
IA [50,400]
6

Final Result Set

Fig. 9. An example of a conjunctive query[[(k)∃ ]][[(k1 • . . . •kn )∃ ]]= {I|∃(k, I) ∈ VD}= [[k1 ]] . . . [[kn ]]In the deﬁnition above, we simply write [[k]] instead of[[(k)∀ ]] or [[(k)∃ ]] whenever no distinction is necessary between them, i.e. [[(k)∀ ]] = [[(k)∃ ]].
C.2 Conjunctive Queries(k2 , I3 [100, 200])(k2 , I4 [300, 400])
Intervals I1 , . . . , I4 are shown at the top of Fig. 9. Let us
consider the query “find me video intervals in which both k1
and k2 appear somewhere”. The query can be formulatedas:Q = (k1 )∃ ∧ (k2 )∃ .

Conjunctive queries are the ones which contain multiple
terms listed with conjunctions. First we deﬁne the operational semantics of conjunctive queries including only
either existential quantiﬁers or universal quantiﬁers.

Then [[(k1 )∃ ]] and [[(k2 )∃ ]] can be given as follows:[[(k11 + . . . + k1m1 )∀ ∧ . . .
∧(kn1 + . . . + knmn )∀ ]] = [[(k11 + . . . + k1m1 )∀ ]] . . .
 1[[(kn + . . . + knmn )∀ ]]m1 ∃1[[(k1 • . . . • k1 ) ∧ . . .
∧(kn1 • . . . • knmn )∃ ]] = [[(k11 • . . . • k1m1 )∃ ]] . . .
 1[[(kn • . . . • knmn )∃ ]]Next we need to perform powerset extended union ( )between the two sets [[(k1 )∃ ]] and [[(k2 )∃ ]].
As explained before, it can be computed by using set
extended union operations as below:

The following two examples will clarify the semantics ofoperations performed on video intervals to synthesize answers.
Example 1: Let us take an illustrative example. Suppose we have the following information stored in the database.
(k1 , I1 [50, 150])(k1 , I2 [210, 350])[[(k1 )∃ ]] = {I1 [50, 150]), I2[210, 350]}[[(k2 )∃ ]] = {I3 [100, 200]), I4[300, 400]}[[(k1 )∃ ]] [[(k2 )∃ ]] =([[(k1 )∃ ]] [[(k1 )∃ ]]) ([[(k2 )∃ ]] [[(k2 )∃ ]])The set extended union operation ( ) on each of these setswith itself will produce the following two sets of intervals.
S1
S2

=
=
=
=


[[(k1 )∃ ]] [[(k1 )∃ ]]{I1 [50, 150], I2[210, 350], I5[50, 350]}
[[(k2 )∃ ]] [[(k2 )∃ ]]{I3 [100, 200], I4[300, 400], I6[100, 400]}

10ACCEPTED FOR PUBLICATION: IEEE TRANS. ON KNOWLEDGE AND DATA ENG., VOL. 13, NO. 6, 2001, (IN PRESS)S1 and S2 are shown in the middle of Fig. 9. Performing theset extended union operation further on these two resulting
sets will produce the following set of interval answers.
[[Q]] = S1 S2= {IA1 [50, 200], IA2[100, 350], IA3[50, 350],
IA4 [100, 400], IA5[210, 400], IA6[50, 400]}
These intervals are shown at the bottom of Fig. 9.
Example 2: Let us take a more realistic example. Suppose we have the following information stored in the database.
(cyborg, I1 )(cyborg, I2 )(monster, I3 )(shoot, I4 )I1 , . . . , I4 are intervals as shown in Fig. 10. Let us con-(monster)∀

I3
I1(cyborg)∀

I2

I5

S1 =
S2 =

{ (
{

·

cyborg monster)∀·(cyborg

I6·(cyborg shoot)∀IA1

monster)∃^

IA1 is shown at the bottom of Fig. 10.
The semantics of general form of conjunctive queries including both existential quantiﬁers and universal quantiﬁers are deﬁned as below:[[(q1 )∀ ∧ . . . ∧ (qm )∀ ∧ (qm+1 )∃ ∧ . . . ∧ (qn )∃ ]]



∀
∀

 [[(q1 ) ]] . . .∃ [[(qm ) ]] ∃[[(qm+1 ) ]] . . . [[(qn ) ]] if m = 0
=


 

if m = 0[[(qm+1 )∃ ]] . . . [[(qn )∃ ]]Next we show an example of a complex query consistingof both kinds of quantiﬁers. Suppose intervals I1 and I2
associated with keyword k1 and k2 respectively, and intervals I3 and I4 associated with keyword k3 as illustrated at
the top of the Fig. 11. Then for a user wanting to ﬁnd out
an interval where there appears k3 throughout the intervaland each k1 and k2 appears somewhere in the interval, thequery is formulated as below:
Q

I4(shoot)∀where I5 and I6 are the intervals shown in the middle ofFig. 10. Finally, the following set of intervals are returned
as the answer.
[[Q]] = S1 S2 = {IA1 }

}
}

·

=

(k1 )∃ ∧ (k2 )∃ ∧ (k3 )∀ .

For this query, the computation deﬁned above will returnI8 (shown at the bottom of the Fig. 11) as an answer but
not I7 because the operation [[k1 ]] eliminates I7 .

(k1, I1[100,150])(k2, I2[200,250])(cyborg shoot)∃(k3, I3[80,260])

Fig. 10. Conjunctive query consisting of a pair of simultaneous queryterms

sider the query “find me video intervals in which cyborg
and monster together appear somewhere and somewherein the scene cyborg is seen shooting ”. The query can beformulated as:
Q = (cyborg • monster) ∃ ∧ (cyborg • shoot)∃.
The operations given below are obvious.
[[(cyborg • monster) ∃]] = {I5 }[[(cyborg • shoot)∃]] = {I6 }
S1
S2

=
=
=
=


[[(cyborg • monster) ∃]] [[(cyborg • monster) ∃]]{I5 }[[(cyborg • shoot)∃]] [[(cyborg • shoot)∃]]{I6 }(k3, I4[225,375])

I5[100,250]
I7[225,375]
I6[80,260]

I8[80,260]

Fig. 11. A complex conjunctive query

C.3 Disjunctive Queries
Finally, the semantics of disjunctive queries is simply deﬁned by the usual set union.
[[q1 ∨ . . . ∨ qn ]] = [[q1 ]] ∪ . . . ∪ [[q1 ]]PRADHAN ET AL.: A QUERY MODEL TO SYNTHESIZE ANSWER INTERVALS FROM INDEXED VIDEO UNITS

11

VI. Degree of Relevance and Ranking
As stated before, because of their relaxed semantics, certain types of queries when submitted against a video database, may produce answer intervals having unequal degreeof relevance. It should be noted that a conjunctive querywith existential quantiﬁers of type (q1 )∃ ∧(q2 )∃ ∧. . .∧(qn )∃ ,in particular, may yield an answer set that may contain alarge number of elements. It is because of the way theanswer intervals are computed by the powerset extended
union operation applied for such queries. Not all of thoseelements may be equally relevant to a user who submits thequery. It is important that the system be able to present
the answers in the best possible manner to a user. The
most common way to present a large number of unequal
answers is to rank them in order.
Ranking strategy is important in any information retrieval systems [16], [22]. Its importance is even greater,
especially in video databases in which query answer units
are not predeﬁned in the database but rather computed
dynamically using the available information. There aremany kinds of video resources such as TV News, movies,
animations etc. and these resources are widely used in different video applications such as Video On Demand, NewsOn Demand, education, video documentation, researchoriented programme etc. [3], [8]. Having such a wide variety of data and numerous kinds of applications, it is very
diﬃcult to make deﬁnite unique choices on how to computerelevance since relevance largely depends on the nature of
the applications and the nature of the query itself.
However, we believe a relevant answer to any video data
query, in general, should be an interval which intuitively,
1. should satisfy all the query conditions,
2. should be short enough in such a way that it does notcontain too much unnecessarily lengthy scenes, and3. should be long enough in such a way that it doesn’t
break out of the context.
We propose two diﬀerent ways to compute the degree of
relevance of a video interval against a given query.
A. Weighted Terms
Supposing there are n terms in the query q = (k1 )∃ ∧(k2 )∃ ∧ . . . ∧ (kn )∃ , and suppose an answer I has L number of frames. Then the answer
 I’s degree of relevance tothe query q is computed asli /L, where li is the lengthof frames in which the term ki emerge. This strategy ischosen under the assumption that the keywords relevant
to a query statement are clustered within a certain rangeof video interval. It is also assumed that two contextuallyrelated keywords in a meaningful video interval are, in general, close to each other. The basic idea is that the more
the video units in which the query terms appear to overlap,
the more signiﬁcance the resulting interval will have.
Consider an example with four intervals I1 , . . . , I4 shownat the top of the Fig. 12. Then supposing for a queryq = (k1 )∃ ∧ (k2 )∃ , four answer intervals IA1 , . . . , IA4 arecomputed as shown at the bottom of the Fig. 12. The
average length of frames, which is computed by the formulali /L stated above, in which the query terms are(k1,I1[50,150])(k2,I3[100,200])(k1,I2[350,440])(k2,I4[340,440])

IA [340,440]
1
IA [50,200]2
IA [100,440]
3
IA [50,440]
4

1.900
1.333
1.000
1.000

Fig. 12. Ranking based on weighted terms

clustered determines the relevance of an answer. For example, for the answer interval IA1 , it is ((440 − 350) +(440 − 340))/(440 − 340) = 190/100 = 1.900. The numbers
shown at the bottom right side in Fig. 12 indicate eachanswer interval’s respective degree of relevance.
B. Maximal Length of Allowable NoiseGiven a query q = (k1 )∃ ∧ (k2 )∃ ∧ . . . ∧ (kn )∃ , noise issaid to exist in a video interval if and only if there exists
a frame in which none of the term present in the query
would emerge. Otherwise, the interval is called noise-free
for the query q.
The ranking strategy described above cannot be justiﬁed when two keywords are separated too far. It is highly
unlikely that a gap of an hour between two keywords canstill preserve the context in which they appear. In suchcases, whether a noise is allowable or not depends largelyon the absolute length of that noise and not on the relative
length.
In most TV dramas and movies, we often see that two
persons appear for some time, then other things are shown
for a very short moment, and those two persons appear
again. In such cases, it can be assumed that the entire interval including the noise (the short interval of time whenboth of the persons do not appear at all) composes a single scene, because such short intervals do not break thecontextual ﬂow of the scene. On the other hand, if thelength of such noise is ﬁve minutes in an interval with similar contents, then its possibility of being just a sequenceof frames breaking two independent scenes is quite high.
Therefore, in such cases, a diﬀerent strategy must be taken
into consideration.
The second method considers the maximum length ofcontiguous noise frames that may be irrelevant to a given
query. The basic idea is the farther the keywords are separated, the less likely the interval’s relevance for the given
query will be. Consider again an example, with four intervals I1 , . . . , I4 shown at the top of the Fig. 13. Then supposing for a query q = (k1 )∃ ∧ (k2 )∃ , four answer intervals
IA1 , . . . , IA4 are computed as shown at the bottom of theFig. 13. In the ﬁgure, white rectangles indicate the noise

12

ACCEPTED FOR PUBLICATION: IEEE TRANS. ON KNOWLEDGE AND DATA ENG., VOL. 13, NO. 6, 2001, (IN PRESS)

portions and the negative numbers shown at the right side
are the measures of the respective maximum noise present
in each answer interval.

(k1,I1[50,200])(k2,I3[50,200])(k1,I2[470,550])(k2,I4[350,450])

IA [50,200]1
IA [350,550]
2
IA [50,450]
3
IA [50,550]
4-0 (2.000)-20 (0.900)-150 (1.000)-150 (0.960)

Noise

Fig. 13. Ranking based on the absolute length of noise

The answer interval IA2 ranked higher than IA3 because
IA2 includes shorter length of noise than IA3 or IA4 andtherefore can be considered more likely to be an independent scene. It is important to note that when the same
set of intervals are ranked according to the weighted terms
strategy, IA2 is ranked last, that is after IA3 and IA4 .
In the ﬁgure, this diﬀerent ranking order is denoted inside
the parenthesis shown at the rightmost side of each answer
interval.
VII. Query Approximation
Video data may not have been described in the way a user
may have expected. It is diﬃcult to imagine that the expressions used by end-users will always conform with theannotations associated with video units [20]. As a result,sometimes no video intervals may be exactly matched withthe users’ speciﬁcation. We provide a query evaluation
based on approximation for dealing with empty answers in
our query mechanism.
Approximative answers have been studied by many researchers in the past. Approximation is necessary usuallywhen a database system has only partial information [12],[16] about the real world. In [11], several constructs havebeen deﬁned for various kinds of partial information. In [2],it is argued that even when two systems have complete information about two separate worlds, the information thatthey possess may be insuﬃcient to answer certain queries.
They have shown how answers can be approximated for
dealing with such queries. [25] proposes a query processor
that makes approximate answers available when there is
not enough time to produce an exact answer. As manyof these researchers have pointed out there are some advantages to use approximation-based query evaluation. An
approximate answer is quicker to evaluate and could be anintermediate answer so that user interaction could be allowed during the query processing. If there is no precise
answer to a query, an approximate answer, even though it

is not exact, will be returned.
Our query evaluation based on approximation can besummarized as follows. First we deﬁne two diﬀerent kindsof orderings among video intervals. The ﬁrst ordering isdeﬁned on the basis of how well two diﬀerent annotations
can describe the same video interval. The second ordering is deﬁned between a video interval and its subintervals
according to the goodness of the information contained inthem. This will let us deﬁne ordering on a set of queries
according to how speciﬁc or how general the conditions
speciﬁed in the queries are. We then describe some strategies for re-formulating the original query in such a way thatintervals that can be approximated to the original queryare returned as answers.
A. Ordering based on Annotations
There are many diﬀerent ways to interpret a video interval.
All ‘Bill Clinton’, ‘American President’, ‘Politician’ can be
keyword interpretations of a video interval showing ‘Bill
Clinton’. Those keywords, however, are not equal to eachother. Some of them are more speciﬁc than others.
In order to deﬁne ordering among the annotations associated with a video interval, we ﬁrst deﬁne a value generalization hierarchy which is a partial order where values
are ordered on the basis of a more-specific () relationship. We assume this relationship to be reﬂexive, transitive and anti-symmetric. An expression such as k  k  denotes that a value k  is more-specific than another value k.
politician  Bill Clinton thus indicates that the value
Bill Clinton is more-specific than the value politician.
Then we also deﬁne the relation  for interval annotation in a natural way as follows:(k, I)  (k , I) iﬀ k  k [19] has presented a more ambitious annotation modelin which descriptive keywords supplemented by quantiﬁers
such as somewhere, everywhere and simultaneous can beprovided to arbitrarily chosen video intervals. The detailed
explanation is beyond the scope of this paper. For such an
ideally described video data, the ordering on annotations
can be extended in such a way that((k)∃ , I)  ((k)∀ , I)and((k1 )∃ ∧ (k2 )∃ , I)  ((k1 • k2 )∃ , I)

Furthermore, a set of annotations containing more descriptive keywords is more-informative than one containing a
lesser number of keywords.
((k1 )∃ ∧ (k2 )∃ , I)  ((k1 )∃ ∧ (k2 )∃ ∧ (k3 )∃ , I)
B. Ordering based on Interval-Subinterval RelationshipOrdering can be also deﬁned between a video interval andits subintervals according to the goodness of the information contained in them. For two intervals I and I  having
a relationship of I  ⊂ I, interval I  is said to be a moreinformative interval than I, if I  contains at least as much

PRADHAN ET AL.: A QUERY MODEL TO SYNTHESIZE ANSWER INTERVALS FROM INDEXED VIDEO UNITS

information as I plus some extra information. Intuitively,
if I and I  both contains a keyword k partially (that issomewhere within the interval) and I  is a subinterval of I,
then I  is considered more-informative. This judgment ismade on the basis that compared to I, I  has less numberof frames where k does not appear. In other words, I  hasrelatively less partial information and hence provides usricher information about the whole data in general. Again
we use I  I  to denote I  is more-informative than I.
More formally,((k)∃ , I)  ((k)∃ , I  ) for each I  ⊂ I
and((k1 • k2 )∃ , I)  ((k1 • k2 )∃ , I  ) for each I  ⊂ I.
However it should be noted that((k)∀ , I  )  ((k)∀ , I) for each I  ⊂ I.
C. Query Reformulation
Given a query Q , if no answer intervals are found, thenthe query can be reformulated into Q such that Q  Q .
Here, the original query Q is more speciﬁc than the reformulated query Q. It should be noted here that if [[(Q )]]and [[(Q)]] represents the set of answers for the query Q
and Q respectively, then [[(Q )]] ⊂ [[(Q)]].
The following strategies explain the query reformulationin general.
C.1 Universal Approximation
If a query (q)∀ is issued but there is no interval that satisﬁes
the condition speciﬁed by q throughout its play, then thequery can be reformulated to (q)∃ .
C.2 Simultaneity Approximation
If a query (q1 • q2 )∃ is issued but there is no interval inwhich q1 and q2 appear simultaneously, then the query
can be reformulated to (q1 )∃ ∧ (q2 )∃ , i.e. a query retrieving
intervals in which both q1 and q2 appear but at diﬀerent
places within the intervals.
C.3 Generalization Approximation
If a query (k)∃ is issued but there is no interval in which kemerges, then the query can be reformulated to (k  )∃ withsome keyword k  that is less-speciﬁc than k.
It should be noted that a single query statement Q may
have many approximations. The query should be reformulated in such a way that the closest answers to the onethat would have been found by the original query should
be returned. Thus, if Q2  Q1  Q, then Q1 shouldbe the immediate choice as the reformulated query for Q.
However, there may not be just one such closest candidate
because there are several ways to make a query less speciﬁc as explained above. When there are multiple closest
candidates, we need to select only one of them on the basisof some criteria. However, this issue will not be discussed
further in this paper.

13

VIII. Conclusion and Future Works
In any video database system, end-users often have difﬁculty in retrieving the intervals that they desire to see.
This is because the intervals they are hoping to ﬁnd may
not have been deﬁned as answer units in the database.
Whether indexing units are extracted automatically or
identiﬁed manually, descriptive information about video
data can be associated with only fragmentary video units.
As a result, the problem will deﬁnitely arise when users
issue queries to look for undeﬁned intervals. In such cases,
intervals need to be computed dynamically from the indexed units that currently exist in the database. We havepresented a new video query model which attempts to ﬁnd
a set of possible interval answers from such a video database. The model has not been designed with one particularindexing scheme in mind.
In order to compute interval answers, we deﬁned a new
set of operations for queries that are most likely to be submitted on a video database. We also presented a framework in which users can specify their queries declaratively
by simply listing keywords with quantiﬁers. The semantics of these query speciﬁcations are obvious, which makequery interpretation easy. The answers to those declarative queries are computed by transforming those queries
into algebraic query expressions and by evaluating them.
These expressions contain speciﬁed keywords and respective operations. To present the answers in the best possible manner, we discussed some ranking strategies thatare relevant to video databases. We also discussed howquery approximation can be realized in case no answers toa query can be computed.
Algebraic operations such as union, intersection, concatenation does not always produce the desired answers
since these operations do not consider the presence of noise
in a meaningful unit, which is highly natural and common
in video data. The main contribution of this paper is thedeﬁnitions of interval extended union operation and its set
variants. Given a query, these operations let us computeall the possible boundaries for interval answers from a setof stored video units. In other words, meaningful units canbe computed from a source of fragmentary units which may
or may not be meaningful in their original forms. It should
be noted here that these operations can be extended to any
continuous data whose semantic boundaries for meaningful units can be deﬁned in numerous ways. As a matter offact, the idea of synthesizing answer intervals from indexed
video units can even be implemented in a hybrid systemsuch as QBIC [5] [10].
There are many open issues that need additional investigation. The ranking strategies presented here may not
be the best ones and therefore need further study. In [17],various methodologies for benchmarking multimedia databases are proposed. They have classiﬁed retrieval techniques into four categories according to the nature of dataand query. Precise vs imprecise data and well-formulated
vs ill-formulated queries are discussed. In our case, although the data in itself may be precise, it may be incomplete to answer even precise queries. Hence, there is a pos-

14

ACCEPTED FOR PUBLICATION: IEEE TRANS. ON KNOWLEDGE AND DATA ENG., VOL. 13, NO. 6, 2001, (IN PRESS)

sibility of imprecise answers being computed and returned.
A new methodology needs to be considered to benchmark
the retrieval of continuous media such as video.
The extended union operation produces plenty of intervals most of which might be irrelevant to the user. In
real applications, however, such answer overloading is ineﬃcient and undesirable. As we discussed in Section VI
also, there exists certain temporal constraints in a videointerval to make it a single meaningful unit. In [28], timeconstrained policy is used as an aid for clustering video
shots. This notion can be applied to evaluate whether thesimilar keywords that emerge within a time interval forma single meaningful unit or not. In order to reduce answer
overloading, other explicitly speciﬁed temporal constraints
need to be considered as well. We have been working onthese issues and so far the results have been promising.
Acknowledgements
This work is partly supported by the Japanese Ministryof Education under Grant-in-Aid for Scientiﬁc Research
on Priority Area: “Advanced Databases”, No. 08244103.
This work is also partly supported by Research for the Future Program of Japan Society for the Promotion of Science under the Project “Researches on Advanced Multimedia Contents Processing”. We would like to thank allanonymous referees for their invaluable comments which
helped us improve the overall contents of our manuscript.
References[1]

J.F. Allen. “Maintaining Knowledge about Temporal Intervals”.
Communications of the ACM, 26(11):832–843, 1983.
[2] P. Buneman, S. Davidson, and A. Watters. “A Semantics forComplex Objects and Approximate Queries”. Journal of Computer and System Sciences, 43(1):170–218, August 1991.
[3] A.K. Elmagarmid, H. Jiang, A.A. Helal, A. Joshi, and
M. Ahmed. “Video Database Systems: Issues and Products
and Applications”. Kluwer Academic Publishers, 1997.
[4] C. Faloutsos and K. Lin. “FastMap: A Fast Algorithm for Indexing and Data-Mining and Visualization of Traditional andMultimedia Datasets”. SIGMOD Record, 24(2):163–174, 1995.
[5] M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang,
B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele,
and P. Yanker. “Query by Image and Video Content: The QBIC
System”. IEEE Computer, 28(9):23–32, September 1995.
[6] A. Hauptmann and M.A. Smith. “Text and Speech and Vision
for Video Segmentation: The Informedia Project”. In AAAI
Fall 1995 Symposium on Computational Models for Integrating
Language and Vision (http://informedia.cs.cmu.edu/), 1995.
[7] R. Hjelsvold, R. Midtstraum, and O. Sandst. “A Temporal
Foundation of Video Databases”. Recent Advances in Temporal Databases. Proceedings of the International Workshop on
Temporal Databases and Zurich and Switzerland, 1995.
[8] R. Hjelsvold, R. Midtstraum, and O. Sandst. “Searching and
Browsing a Shared Video Database”. Multimedia Database Systems. Design and Implementation Strategies. chapter 4. Kluwer
Academic Publishers, 1996.
[9] E.J. Hwang and V.S. Subrahmanian. “Querying Video Libraries”. Journal of Visual Communications and Image Representation, 7(1):44–60, March 1996.
[10] W. Li, K. Selçuk Candan, K. Hirata, and Y. Hara. “A Hybrid Approach to Multimedia Database Systems through Integration of Semantics and Media-based Search”. Lecture Notes
in Computer Science – Worldwide Computing and Its Applications, 1274:182–197, August 1997.
[11] L. Libkin. “Aspects of Partial Information in Databases”. PhD
thesis, University of Pennsylvania, 1994.

[12] W. Lipski.
“On Semantic Issues Connected with Incomplete Information Databases”. ACM Trans. Database Systems,
4(3):262–296, September 1979.
[13] T.D.C. Little, G. Ahanger, R.J. Folz, J.F. Gibbon, F.W. Reeve,
D.H. Schelleng, and D. Venkatesh. “A Digital On-Demand Video
Service Supporting Content-Based Queries”. In Proc. of ACM
Multimedia 93 and California and USA, pages 427–436, 1993.
[14] T.D.C. Little and A. Ghafoor. “Interval-Based Conceptual Models for Time-Dependent Multimedia Data”. IEEE Transactions on Knowledge and Data Engineering, 5(4):551–563, August 1993.
[15] N.A. Lorentzos and Y.G. Mitsopoulos. “SQL Extension for Intervals Data”. IEEE Transactions on Knowledge and Data Engineering, 9(3):480–499, May/June 1997.
[16] J.M. Morrissey. “Imprecise Information and Uncertainty in Information Systems”. ACM Transactions on Information Systems, 8(2):159–180, 1990.
[17] A.D. Narasimhalu, M.S. Kankanhalli, and J. Wu. “Benchmarking Multimedia Databases”. Multimedia Tools and Applications,
4(3):333–356, May 1997.
[18] E. Oomoto and K. Tanaka. “OVID: Design and Implementationof a Video-Object Database System”. IEEE Transactions on
Knowledge and Data Engineering, 5(4):629–643, August 1993.
[19] S. Pradhan, K. Tajima, and K. Tanaka. “Using Prototype Objects and Powerdomains to Support Public Authoring of Video
Databases”. In Proc. of Int’l Symposium on Cooperative Database Systems for Advanced Applications, pages 210–217. World
Scientiﬁc, 1996.
[20] S. Pradhan, K. Tajima, and K. Tanaka. “Querying Video Databases based on Description Substantiality and Approximations”.
In Proc. of the IPSJ Int’l Symposium on Information Systems
and Technologies for Network Society, pages 183–190. World
Scientiﬁc, 1997.
[21] S. Pradhan, K. Tajima, and K. Tanaka. “A New Algebraic Approach to Retrieve Meaningful Video Intervals from Fragmentarily Indexed Video Shots”. In Advances in Visual Information
Management: Visual Database Systems 5 (VDB5), pages 11–
30. Kluwer Academic Publisher, May 2000.
[22] B. Simonnot and M. Smail. “Model for Interactive Retrievalof Videos and Still Images”. In Multimedia Database Systems.
Design and Implementation Strategies, chapter 10. Kluwer Academic Publishers, 1996.
[23] T.G. Aguierre Smith and G. Davenport. “The Stratiﬁcation
System: A Design Environment for Random Access Video”. In
Proc. 3rd Int’l Workshop on Network and Operating System
Support for Digital Audio and Video, pages 250–261, 1992.
[24] D. Swanberg, C. Shu, and R. Jain. “Architecture of Multimedia Information System for Content-based Retrieval”. In Audio
Video Workshop and San Diego and CA and USA, Novemberand 1992.
[25] S.V. Vrbsky and J.W.S. Liu. “An Object-Oriented Query Processor that Produces Monotonically Improving Approximate
Answers”. In Proceedings of the 7th IEEE Conf. on Data Engineering and Kobe and Japan, pages 472–81, April 1991.
[26] H.D. Wactlar, T. Kanade, M.A. Smith, and S.M. Stevens. “Intelligent Access to Digital Video: Informedia Project”. IEEE
Computer, 29(5):46–52, May 1996.
[27] R. Weiss, A. Duda, and D. Giﬀord. “Composition and Searchwith a Video Algebra”. IEEE MultiMedia, 2(1):12–25, Spring
1995.
[28] M. Yeung, B.L. Yeo, and B. Liu. “Extracting Story Units fromLong Programs for Video Browsing and Navigation”. In International Conference on Multimedia Computing and Systems,
pages 296–305, June 1996.
[29] H.J. Zhang, C.Y. Low, S.W. Smoliar, and J.H. Wu. “Video Parsing and Retrieval and Browsing: An Integrated and Contentbased Solution”. In Multimedia 95 Proceedings, pages 15–24,
November 1995.

PRADHAN ET AL.: A QUERY MODEL TO SYNTHESIZE ANSWER INTERVALS FROM INDEXED VIDEO UNITS
Sujeet Pradhan received a BE in MechanicalEngineering from the University of Rajasthan,India in 1988, an MS in Instrumentation Engineering in 1995 and a Ph.D. in Intelligence
Science in 1999 from Kobe University, Japan.
Since 1999 May, he is a lecturer of the Department of Computer Science and Mathematics at
Kurashiki University of Science and the Arts,
Japan. He was a Colombo Plan scholar during 1984–1988 and a Mombusho scholar during
1995–1997. A JSPS (Japan Society for the Promotion of Science) Research Fellow during the period between 1997
and 1999, his research interests include video databases, multimedia authoring, prototype-based languages and semi-structured databases. Dr. Pradhan is a member of IEEE Computer Society andInformation Processing Society of Japan.

Keishi Tajima received the B.Sc., M.Sc., and
D.Sc. degrees in information science from the
University of Tokyo, in 1991, 1993, and 1996
respectively. In 1996, he joined the Departmentof Computer and Systems Engineering at Kobe
University, as a research associate. His researchinterests include data model for non-traditional
database applications, database programming
languages, and security in database systems.

Katsumi Tanaka received the B.S., M.S., andPh.D degrees in information science from Kyoto University, in 1974, 1976, and 1981 respectively. In 1986, he joined the Department ofInstrumentation Engineering at Kobe University, as an associate professor. Since 1994, heis a professor of the Department of Computerand Systems Engineering and since 1997, he isa professor of Division of Information and Media Sciences of Graduate School of Science andTechnology at Kobe University. His researchinterests include object-oriented databases, video databases, historical database models, and hypermedia systems. Dr. Tanaka is amember of the ACM, IEEE Computer Society and the Information
Processing Society of Japan.

15