Stanford InfoLab Publication Server

Optimizing Queries over Multimedia Repositories

Chaudhuri, S. and Gravano, L. (1996) Optimizing Queries over Multimedia Repositories. In: SIGMOD '96.




Repositories of multimedia objects having multiple types of attributes (e.g., image, text) are becoming increasingly common. A selection on these attributes will typically produce not just a set of objects, as in the traditional relational query model (filteringbut also a grade of match associated with each object, indicating how well the object matches the selection condition (rankingAlso, multimedia repositories may allow access to the attributes of each object only through indexes. We investigate how to optimize the processing of queries over multimedia repositories. A key issue is the choice of the indexes used to search the repository. We define an execution space that is searchminimal, i.e., the set of indexes searched is minimal. Although the general problem of picking an optimal plan in the search-minimal execution space is NP-hard, we solve the problem effciently when the predicates in the query are independent. We also show that the problem of optimizing queries that ask for a few top-ranked objects can be viewed, in many cases, as that of evaluating selection conditions. Thus, both problems can be viewed together as an extended filtering problem.

Item Type:Conference or Workshop Item (Paper)
Subjects:Computer Science > Digital Libraries
Computer Science > Query Processing
Projects:Digital Libraries
Related URLs:Project Homepage
ID Code:198
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:08 Dec 2008 15:12

Download statistics

Repository Staff Only: item control page