Flexible integration of multimedia sub-queries with qualitative preferences

Ilaria Bartolini, Paolo Ciaccia, Vincent Oria, M. Tamer Özsu

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

Complex multimedia queries, aiming to retrieve from large databases those objects that best match the query specification, are usually processed by splitting them into a set of m simpler sub-queries, each dealing with only some of the query features. To determine which are the overall best-matching objects, a rule is then needed to integrate the results of such sub-queries, i.e., how to globally rank the m-dimensional vectors of matching degrees, or partial scores, that objects obtain on the m sub-queries. It is a fact that state-of-the-art approaches all adopt as integration rule a scoring function, such as weighted average, that aggregates the m partial scores into an overall (numerical) similarity score, so that objects can be linearly ordered and only the highest scored ones returned to the user. This choice however forces the system to compromise between the different sub-queries and can easily lead to miss relevant results. In this paper we explore the potentialities of a more general approach, based on the use of qualitative preferences, able to define arbitrary partial (rather than only linear) orders on database objects, so that a larger flexibility is gained in shaping what the user is looking for. For the purpose of efficient evaluation, we propose two integration algorithms able to work with any (monotone) partial order (thus also with scoring functions): MPO, which delivers objects one layer of the partial order at a time, and iMPO, which can incrementally return one object at a time, thus also suitable for processing top k queries. Our analysis demonstrates that using qualitative preferences pays off. In particular, using Skyline and Region-prioritized Skyline preferences for queries on a real image database, we show that the results we get have a precision comparable to that obtainable using scoring functions, yet they are obtained much faster, saving up to about 70% database accesses.

Original languageEnglish (US)
Pages (from-to)275-300
Number of pages26
JournalMultimedia Tools and Applications
Volume33
Issue number3
DOIs
StatePublished - Jan 1 2007

Fingerprint

Specifications
Processing
Object-oriented databases

All Science Journal Classification (ASJC) codes

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

Keywords

  • Incremental evaluation
  • Multimedia data integration
  • Qualitative preferences
  • Skyline
  • Strict partial orders

Cite this

Bartolini, Ilaria ; Ciaccia, Paolo ; Oria, Vincent ; Özsu, M. Tamer. / Flexible integration of multimedia sub-queries with qualitative preferences. In: Multimedia Tools and Applications. 2007 ; Vol. 33, No. 3. pp. 275-300.
@article{012c0a2437884da9abd64de48b066833,
title = "Flexible integration of multimedia sub-queries with qualitative preferences",
abstract = "Complex multimedia queries, aiming to retrieve from large databases those objects that best match the query specification, are usually processed by splitting them into a set of m simpler sub-queries, each dealing with only some of the query features. To determine which are the overall best-matching objects, a rule is then needed to integrate the results of such sub-queries, i.e., how to globally rank the m-dimensional vectors of matching degrees, or partial scores, that objects obtain on the m sub-queries. It is a fact that state-of-the-art approaches all adopt as integration rule a scoring function, such as weighted average, that aggregates the m partial scores into an overall (numerical) similarity score, so that objects can be linearly ordered and only the highest scored ones returned to the user. This choice however forces the system to compromise between the different sub-queries and can easily lead to miss relevant results. In this paper we explore the potentialities of a more general approach, based on the use of qualitative preferences, able to define arbitrary partial (rather than only linear) orders on database objects, so that a larger flexibility is gained in shaping what the user is looking for. For the purpose of efficient evaluation, we propose two integration algorithms able to work with any (monotone) partial order (thus also with scoring functions): MPO, which delivers objects one layer of the partial order at a time, and iMPO, which can incrementally return one object at a time, thus also suitable for processing top k queries. Our analysis demonstrates that using qualitative preferences pays off. In particular, using Skyline and Region-prioritized Skyline preferences for queries on a real image database, we show that the results we get have a precision comparable to that obtainable using scoring functions, yet they are obtained much faster, saving up to about 70{\%} database accesses.",
keywords = "Incremental evaluation, Multimedia data integration, Qualitative preferences, Skyline, Strict partial orders",
author = "Ilaria Bartolini and Paolo Ciaccia and Vincent Oria and {\"O}zsu, {M. Tamer}",
year = "2007",
month = "1",
day = "1",
doi = "https://doi.org/10.1007/s11042-007-0103-1",
language = "English (US)",
volume = "33",
pages = "275--300",
journal = "Multimedia Tools and Applications",
issn = "1380-7501",
publisher = "Springer Netherlands",
number = "3",

}

Flexible integration of multimedia sub-queries with qualitative preferences. / Bartolini, Ilaria; Ciaccia, Paolo; Oria, Vincent; Özsu, M. Tamer.

In: Multimedia Tools and Applications, Vol. 33, No. 3, 01.01.2007, p. 275-300.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Flexible integration of multimedia sub-queries with qualitative preferences

AU - Bartolini, Ilaria

AU - Ciaccia, Paolo

AU - Oria, Vincent

AU - Özsu, M. Tamer

PY - 2007/1/1

Y1 - 2007/1/1

N2 - Complex multimedia queries, aiming to retrieve from large databases those objects that best match the query specification, are usually processed by splitting them into a set of m simpler sub-queries, each dealing with only some of the query features. To determine which are the overall best-matching objects, a rule is then needed to integrate the results of such sub-queries, i.e., how to globally rank the m-dimensional vectors of matching degrees, or partial scores, that objects obtain on the m sub-queries. It is a fact that state-of-the-art approaches all adopt as integration rule a scoring function, such as weighted average, that aggregates the m partial scores into an overall (numerical) similarity score, so that objects can be linearly ordered and only the highest scored ones returned to the user. This choice however forces the system to compromise between the different sub-queries and can easily lead to miss relevant results. In this paper we explore the potentialities of a more general approach, based on the use of qualitative preferences, able to define arbitrary partial (rather than only linear) orders on database objects, so that a larger flexibility is gained in shaping what the user is looking for. For the purpose of efficient evaluation, we propose two integration algorithms able to work with any (monotone) partial order (thus also with scoring functions): MPO, which delivers objects one layer of the partial order at a time, and iMPO, which can incrementally return one object at a time, thus also suitable for processing top k queries. Our analysis demonstrates that using qualitative preferences pays off. In particular, using Skyline and Region-prioritized Skyline preferences for queries on a real image database, we show that the results we get have a precision comparable to that obtainable using scoring functions, yet they are obtained much faster, saving up to about 70% database accesses.

AB - Complex multimedia queries, aiming to retrieve from large databases those objects that best match the query specification, are usually processed by splitting them into a set of m simpler sub-queries, each dealing with only some of the query features. To determine which are the overall best-matching objects, a rule is then needed to integrate the results of such sub-queries, i.e., how to globally rank the m-dimensional vectors of matching degrees, or partial scores, that objects obtain on the m sub-queries. It is a fact that state-of-the-art approaches all adopt as integration rule a scoring function, such as weighted average, that aggregates the m partial scores into an overall (numerical) similarity score, so that objects can be linearly ordered and only the highest scored ones returned to the user. This choice however forces the system to compromise between the different sub-queries and can easily lead to miss relevant results. In this paper we explore the potentialities of a more general approach, based on the use of qualitative preferences, able to define arbitrary partial (rather than only linear) orders on database objects, so that a larger flexibility is gained in shaping what the user is looking for. For the purpose of efficient evaluation, we propose two integration algorithms able to work with any (monotone) partial order (thus also with scoring functions): MPO, which delivers objects one layer of the partial order at a time, and iMPO, which can incrementally return one object at a time, thus also suitable for processing top k queries. Our analysis demonstrates that using qualitative preferences pays off. In particular, using Skyline and Region-prioritized Skyline preferences for queries on a real image database, we show that the results we get have a precision comparable to that obtainable using scoring functions, yet they are obtained much faster, saving up to about 70% database accesses.

KW - Incremental evaluation

KW - Multimedia data integration

KW - Qualitative preferences

KW - Skyline

KW - Strict partial orders

UR - http://www.scopus.com/inward/record.url?scp=34247167483&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34247167483&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/s11042-007-0103-1

DO - https://doi.org/10.1007/s11042-007-0103-1

M3 - Article

VL - 33

SP - 275

EP - 300

JO - Multimedia Tools and Applications

JF - Multimedia Tools and Applications

SN - 1380-7501

IS - 3

ER -