Integrating the Results of Multimedia Sub-Queries Using Qualitative Preferences

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.