When similarity queries over multimedia databases are processed by splitting the overall query condition into a set of sub-queries, the problem of how to efficiently and effectively integrate the sub-queries’ results arises. The common approach is to use a (monotone) scoring function, like min and average, to compute an overall similarity score by aggregating the partial scores an object obtains on the sub-queries. In order to minimize the number of database accesses, a “middleware” algorithm is applied to return only the top k highest scored objects. In this paper we consider a more general approach, based on qualitative preferences, for the integration of partial scores. With qualitative preferences one can define arbitrary partial (rather than only linear) orders on database objects, which gives a larger flexibility in shaping what the user is looking for. For the purpose of efficient evaluation, we propose two integration algorithms, both able to work with any (monotone) partial order: MPO, which delivers objects one layer at a time, layers being defined by the specific partial order at hand, and iMPO, which is an incremental algorithm that delivers one object at a time, thus suitable for top k queries. Our analysis demonstrates that using qualitative preferences pays off. In particular, using Skyline and the new Region-prioritized Skyline preferences for queries on a real image database, we show that iMPO yields results whose quality is comparable to that obtainable from algorithms using scoring functions. However, iMPO performs faster, saving up to about 70% database accesses.

Integrating the Results of Multimedia Sub-Queries Using Qualitative Preferences

BARTOLINI, ILARIA;CIACCIA, PAOLO;
2004

Abstract

When similarity queries over multimedia databases are processed by splitting the overall query condition into a set of sub-queries, the problem of how to efficiently and effectively integrate the sub-queries’ results arises. The common approach is to use a (monotone) scoring function, like min and average, to compute an overall similarity score by aggregating the partial scores an object obtains on the sub-queries. In order to minimize the number of database accesses, a “middleware” algorithm is applied to return only the top k highest scored objects. In this paper we consider a more general approach, based on qualitative preferences, for the integration of partial scores. With qualitative preferences one can define arbitrary partial (rather than only linear) orders on database objects, which gives a larger flexibility in shaping what the user is looking for. For the purpose of efficient evaluation, we propose two integration algorithms, both able to work with any (monotone) partial order: MPO, which delivers objects one layer at a time, layers being defined by the specific partial order at hand, and iMPO, which is an incremental algorithm that delivers one object at a time, thus suitable for top k queries. Our analysis demonstrates that using qualitative preferences pays off. In particular, using Skyline and the new Region-prioritized Skyline preferences for queries on a real image database, we show that iMPO yields results whose quality is comparable to that obtainable from algorithms using scoring functions. However, iMPO performs faster, saving up to about 70% database accesses.
2004
Proceedings of the 10th International Workshop on Multimedia Information Systems (MIS 2004)
66
75
BARTOLINI I.; CIACCIA P.; ORIA V.; OZSU T.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/3487
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact