Abstract
Advances in computing technologies have made multimedia databases
comprising large collections of images, video and sound possible.
In these applications, the queries are specified by giving the
target values of the attributes. An exact matching result is seldom
expected. A small set of objects whose attributes best match the
query attributes, are to be returned to the user in response to
his query. The result set presented is expected to be ordered
on the degree of match to the query attributes. There is increasing
interest in such problems by the database community such problems
have come into the main stream database research.
Often visual languages are used for querying and query by example
is the most common form of querying such databases. Query processing
is based on similarity matching between the query attributes and
the corresponding attributes of the database objects. Similarity
matching is based on computation of effective distance between
the attributes. High dimensional indexing structures such as R+-tree,
R*-tree, SS-tree, etc., are used finding the nearest objects.
From the processing point of view, we categorize queries into
four classes.
1. Single example object with single feature attribute.
2. Single example object with multiple feature attribute.
3. Multiple example object with single feature attribute.
4. Multiple example object with multiple feature attribute.
We first discuss simple query processing. Each feature is indexed
using high dimensional indexing structure. Algorithm such as K-nearest
neighbour queries and range queries are used to retrieve the most
similar images. We discuss the algorithms for processing queries
of type 2, which involves evaluation of combining functions. The
theoretical limitations of such evaluations as derived by Fagin
will be dealt with briefly. Processing queries of type 3. and
4. are more involved. We start with motivation for such queries
in multimedia databases. The new taxonomy we have developed for
such queries, and the resulting processing strategies will be
discussed.
Biography
Dr. Ramakrishna (rama@csse.monash.edu.au) obtained M.E. from
Indian Institute of Science, M.Math and Ph.D. in computer science
from University of Waterloo, Canada. He is at the School of
Computer Science and Software Engineering, Monash University,
Melbourne. Before joining Monash University, he was at the Department
of Computer Science, RMIT since 1994. Earlier he was working
at the Michigan State University, USA. His present research
is concerned with image and multimedia databases and file structures.
He is working on modeling, querying and indexing of image databases,
join algorithms, high dimensional indexing. His earlier work
on hashing and file structures is well recognized. He has published
over 30 technical papers in ACM TODS, IEEE TKDE, Comm. of ACM
etc. journals, and ACM SIGMOD, ACM PODS, IEEE ICDE etc. Conferences.
He is a Member of the Editorial Board of Journal of Database
Management. He has been on program committees of VLDB Conference(1995),
IEEE Data Engineering Conference(1990,91,93), International
Conference on Foundations of Data Organisation(1993).