Exploiting Indifference for Customization of Partial Order Skylines

Unlike numerical preferences, preferences on attribute values do not show an inherent total order, but skyline computation has to rely on partial orderings explicitly stated by the user. In such orders many object values are incomparable, hence skylines sizes become unpractical. However, the Pareto semantics can be modified to benefit from indifferences: skyline result sizes can be essentially reduced by allowing the user to declare some incomparable values as equally desirable. A major problem of adding such equivalences is that they may result in intransitivity of the aggregated Pareto order and thus efficient query processing is hampered. In this paper we analyze how far the strict Pareto semantics can be relaxed while always retaining transitivity of the induced Pareto aggregation. Extensive practical tests show that skyline sizes can indeed be reduced about two orders of magnitude when using the maximum possible relaxation still guaranteeing the consistency with all user preferences

1. Introduction

Retrieval techniques taking human preferences into account play an essential role in today's information systems. As a result, database retrieval has moved beyond pure SQL-style retrieval, i.e. exact matches, towards more powerful ranked retrieval techniques. All of these techniques involve scoring hits according to the users' preferences. As these are expressed with respect to a set of predicates, query processing becomes a multi-objective optimization problem. For instance, top-k approaches use a numerical utility function to compensate between (individually weighted) query predicates. However, practical applications show that such numerical compensation often causes problems in the querying process. This is because users cannot sensibly decide a-priori for a suitable function or the most adequate weightings to express their information needs, i.e. without having at least an overview over the contents of the database.