Multi-criteria query optimization in the presence of result size and quality tradeoffs

Lakshmi Priya Mahalingam, Kasim Candan

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In this paper, we present novel multi-criteria query optimization techniques for performing query optimization in databases, such as multimedia and web databases, which rely on imperfect access mechanisms and top-k predicates. We present an optimization model that (1) takes into account different binding patterns associated with query predicates, (2) considers the variations in the expected query result sizes as a function of query execution plans, and (3) considers the expected result qualities of the execution orders. We address the complexity and the well-known NP-complete nature of the query optimization problem by adaptively reducing the granularity of the search space. For this purpose, unlike the data histograms which capture the data distribution, we propose opt-histograms that capture the distribution of sub-query-plan values over many optimization tasks.

Original languageEnglish (US)
Pages (from-to)167-183
Number of pages17
JournalMultimedia Tools and Applications
Issue number3
StatePublished - Aug 2004


  • Multi-criteria optimization
  • Multimedia databases
  • Quality-based optimization
  • Query optimization
  • Similarity-based optimization
  • Top-k retrieval

ASJC Scopus subject areas

  • Software
  • Media Technology
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this