# Skyline Operators and Regret Minimization Techniques for Managing User
Preferences in the Query Process

Giulio Talarico  Politecnico di Milano
Milan, Italy
<EMAIL_ADDRESS>
###### Abstract

The problem of selecting the most representative tuples from a dataset has led
to the development of powerful tools, among which Skyline and Ranking (or
Top-$k$) queries stand out for their ability to support the optimization of
multiple criteria in the query process. This paper surveys the remarkable
efforts made towards the extension of the aforementioned tools to overcome
their limitations, respectively the explosion of the output result and the
difficulty of query formulation. Moreover, we explore the application of these
state-of-the-art techniques as preference-based query frameworks, proposing a
comparison of their query personalization capabilities, the ability to control
the output size and their flexibility with respect to the user input
preferences.

Keywords: skyline, ranking, regret-minimization, preference

##  1 Introduction

During the last twenty years, since the introduction of the Skyline operator
[1], numerous powerful tools have been proposed in the realm of database
systems with the aim of assisting multi-criteria decision making, namely to
provide the user with the most useful results with respect to a set of input
preferences.

Managing user preferences in the query process has been proved to be
fundamental when dealing with large scale databases, where the user can get
lost in a mare magnum of potentially interesting data. Some representative
scenarios where user-centered information retrieval is indeed requisite are:
(i) recommender systems [2], where user input preferences, extrapolated for
instance from clickstream data, are used to restrict the output of proposed
products only to those of significant value with respect to the user profile;
(ii) UX design, where both quantity and quality of the elements which the user
can interact with are key aspects which influence the ease and the speed of
the user’s decision making [3]; (iii) product search [4, 5], where the output
result has to take into account a set of search criteria that not always the
user is able to provide in a complete, consistent and quantitative manner,
considering the investigative nature of a search with respect to unfamiliar
domains.

In such complex scenarios, traditional approaches to multi-objective
optimization, among which we refer to Skyline and Ranking (or Top-$k$)
queries, suffer respectively from poor personalization capabilities, because
of the ceteris paribus semantics, and the lack of flexibility with respect to
user input preferences, because of the need of a scoring function as a mean of
defining user preferences; furthermore, both approaches are doomed by the
curse of dimensionality, that makes the output of a skyline query often too
big to handle (with the risk of paralyzing the decision making process of the
user) and the weights used to compute the score of a high-dimensional tuple
too hard to define in the first place. The aim of this survey is to compare
different techniques developed to overcome such limitations, focusing on their
ability of satisfying three hard requirements for user preference management
[6]: (1) personalization, (2) control over the output size, (3) flexibility of
the specified preferences.

In section 2 we summarize the state-of-the-art of tools and methodologies that
improved the capabilities of traditional Skyline and Ranking queries, namely
Flexible Skylines, Skyline Ranking and Regret Minimization queries. In section
3 we explore the application of these tools as frameworks for handling user
preferences in the query process. Finally, in section 4, we briefly review and
discuss the big picture of multi-objective query optimization approaches
depicted in this survey.

##  2 State of the art

Despite their ability to capture the most interesting objects of a dataset
with respect to a set of user preferences, the Skyline operator and Ranking
queries both present some limitations:

  * •

the core concept behind Skyline queries is the Pareto improvement principle,
which is the reason behind the simplicity of the Skyline semantics: the user
is only asked to state his absolute preferences about each individual
attribute without taking into account its relative importance with respect to
the other attributes of the examined schema. In fact, Skyline queries will
output the set of non-dominated tuples: a tuple $p$ is said to dominate a
tuple $p^{\prime}$ when $p$ is nowhere worse and better at least in one
dimension (no matter which) than $p^{\prime}$. In principle, this approach
provides considerable summarization power, since the output of the Skyline
query will be the set of potentially interesting tuples, although there are
some major drawbacks not only because all attributes are considered equally
important, but also because it is more unlikely for a tuple to be dominated as
the number of dimensions increases, hence the size of the Skyline will become
too big to bring the user useful results: experimental evidence in [7] shows
that the output size of a skyline query can be exponential in the number of
attributes;

  * •

in order to apply ranking algorithms [8] so that only a predetermined number
of relevant results is evaluated, the user is required to provide a scoring
function which represents his query preferences: this is typically expressed
in the form of an aggregation function of partial scores defined for each
attribute, thus allowing one to give different attributes different importance
and, since a global comparison criterion is established, to select the desired
number of tuples among the most relevant ones. On the other hand, specifying a
scoring function is not always straightforward and it makes the preference
elicitation process much more complex since the user typically has to assign a
numerical weight to each attribute; besides, small variations of the weights
may lead to significant variations of the query results, therefore reducing
the level of confidence of its relevance.

In the following sections we summarize, to the best of our knowledge, the main
ideas behind some of the methods developed to combine the most effective
characteristics of the aforementioned techniques, namely the simplicity of
formulation and the finer control both over the output size and over the
importance contribution of each attribute in the query process. For the
purpose of this survey, three main categories are identified: Flexible
Skylines, Skyline Ranking and Regret Minimization Queries.

###  2.1 Flexible Skylines

The flexibility introduced by this category of techniques comes from the fact
that the user is not required to formulate a detailed scoring function:
instead, different approaches are embraced to integrate user preferences in a
more general, but still representative way, into the Skyline framework,
providing broader control over the query constraints, such as the possibility
of expressing relative importance between attributes, introducing qualitative
trade-offs, taking into account inaccuracies in the process of preference
formulation and, accordingly, also reducing the query output size.

####  2.1.1 R-Skylines

Restricted Skylines [9] combine the notion of dominance and the notion of
ranking introducing the concept of $\mathcal{F}$-dominance: given a set of
monotone scoring functions $\mathcal{F}$, a tuple t $\mathcal{F}$-dominates
another tuple $s\neq t$, denoted by $t\prec_{\mathcal{F}}s$, iff $\forall
f\in\mathcal{F}.\ f(t)\leq f(s)$. Defining a family of scoring functions
allows the user to specify a set of constraints over the weight space rather
than explicitly set exact weight values for each attribute, as it is done
instead in ranking queries: for instance in a 2-dimensional schema with
attribute $A_{1}$ being price and attribute $A_{2}$ being mileage we may
express a set of constraintc $C=\\{w_{1}\geq w_{2}\\}$ for a family
$\mathcal{F}$ of e.g. linear scoring functions to express the preference of
price over mileage.

The R-Skyline coincides with the traditional skyline if $\mathcal{F}$ is the
family of all the monotone scoring functions, whereas, as it is further
analyzed in [10], when finite sets of scoring functions are taken into
account, R-Skylines incorporate the characteristics of dynamic skylines [11].
The unique query potential of R-Skylines stands out when infinite sets of
scoring functions are considered: in fact, experimental results demonstrate a
considerable reduction of the query output size with respect to the result
obtained using the traditional Skyline operator, suggesting that there is some
correlation between the increase of the dominance region, caused by the
introduction of constraints over the weight space, and the reduction of output
tuples, where the dominance region of a tuple $p$ is defined as the set of all
points dominated by $p$.

####  2.1.2 Uncertain Top-k Queries

A similar concept of flexibility is used in [12] to define Uncertain Top-k
Queries (UTK): the weight vector (directly provided by the user or
computationally inferred) is extended to a region in order to take into
consideration the inherent uncertainty of the weight values provided by the
user, hence computing results also for query preferences (weight vectors) that
are similar (close) to the user defined preference profile (seed vector); this
is implemented in the definition of r-dominance: given a region $R$ in the
preference domain and a linear scoring function $S$, a tuple $p$ r-dominates
another tuple $p^{\prime}$ when $S(p)\geq S(p^{\prime})$ for any weight vector
in $R$, and there is at least a weight vector in $R$ for which
$S(p)>S(p^{\prime})$. Specifying a region $R$ introduces an extra measure to
break ties between incomparable tuples according to the traditional notion of
dominance, since it suffices to check whether the vertices of $R$ are all
inside or all outside the half-space $S(p)\geq S(p^{\prime})$, which
determines a region where $p$ r-dominates $p^{\prime}$ and another one where
$p$ is r-dominated instead. UTK result contains tuples that are dominated by
fewer than $k$ others, i.e. the r-skyband of the dataset.

UTK capabilities are further extended in [6] introducing the concept of
$\rho$-dominance, that only considers vectors that are within a distance
$\rho$ from the seed. This particular technique allows the user to specify not
only a dominance parameter $k$, but also the desired output size $m$, which is
used to tune the distance parameter $\rho$ such that it is the minimum
distance that produces exactly $m$ tuples as a result, hence the closest to
the user’s preference profile. It is worth noting that when $\rho=0$ this is
equivalent to performing a top-k query, whereas when $\rho=\infty$ the output
will be a k-skyband.

####  2.1.3 P-Skylines

Prioritized Skylines [13] allow one to express relative importance between
attributes through the use of p-expressions: with this kind of approach user
preferences are handled using a more complex preference framework that makes
use of preference formulas, introduced in [14]. A p-expression $\pi$ is the
composition of attribute preference relations, used to express an absolute
preference over the values of a single attribute (e.g. price: the lower the
better), with & (prioritized accumulation) and $\otimes$ (Pareto accumulation)
operators, used to define the relative importance of attribute preferences:
$\pi_{1}\ \&\ \pi_{2}$ means that $\pi_{1}$ has higher importance than
$\pi_{2}$, whereas $\pi_{1}\ \otimes\ \pi_{2}$ means that the two operands
have the same importance. The composition of such relations is represented as
a hierarchical structure using a p-graph, which is then used to test the
dominance of a tuple with respect to another one, hence to compute the most
preferred tuple in a set.

In order to elicit user preferences and construct the corresponding
p-expressions, the authors propose a feedback-based approach that identifies
superior and inferior examples, i.e. desirable and undesirable tuples,
bypassing the pairwise comparison of all attributes; this provides even more
flexibility to the query process, since the user may be directly or indirectly
involved: for instance, in a web centered scenario, one could take advantage
of profiling information such as click-through rate to determine superior
examples.

A similar technique, where user-specified qualitative partial preferences in
the form of a graph guide the query process, is Telescope [15].

####  2.1.4 Trade-off Skylines

Trade-off Skylines [16] deal with the introduction of flexibility in the query
process integrating user preferences in the form of qualitative trade-offs:
the idea is that a user may be willing to sacrifice the goodness of some
attribute in favor of the improvement of some other attribute (e.g.
willingness to pay up to 5$ more on a pizza order to get extra cheese,
sacrificing price in favor of tastiness). Compensation semantics are
formalized in [17] through the notion of amalgamated preferences and
amalgamated equivalences: the user can extend the Pareto semantics with
additional domination relationships in order to obtain the so called
generalized skyline.

This enhancement brings to light some new difficulties: the additional trade-
off semantics makes the dominance check among tuples more complex since the
amalgamation of attribute domains breaks the property of separability of
traditional skylines, which normally allows for a simple attribute-based
comparison as dominance check criterion, thus the authors provide a tree-based
algorithm to represent trade-offs and optimize the dominance check process, so
that compromises can be efficiently taken into account in the skyline query
process.

###  2.2 Skyline Ranking

The common objective of Skyline Ranking techniques is to select from the
points of a skyline only the $k$ most useful ones, where the output size
constraint $k$ is defined by the user. This is not trivial, since, by
definition, all the points in a skyline are equally important and, since
during the skyline query process the user is not required to provide any
preference function that ranks each tuple accordingly, different criteria may
be used to select exactly $k$ objects as a result; the following techniques
will take into account structural characteristics of the skyline set to rank
its items.

####  2.2.1 Skyline Ordering

The Skyline Ordering [18] technique focuses on the possibility of specifying
arbitrary query size constraints, i.e. a query output size parameter $k$ that
is not known a priori to be smaller or larger than the actual size $s$ of the
skyline. This is achieved by combining pointwise ranking and set-wide
maximization, two popular approaches used to reduce the size of the skyline:
the former defines a total ordering among the skyline points using a scoring
function, although it is not really suitable in the context of skyline queries
since it is not only hard to formulate because of the sensitivity of the query
results with respect to the function weights, but also tends to select points
with similar features, since they will have similar scores, thus limiting the
variety of the query results; the latter determines a subset of $k$
interesting data points by maximizing a collective property of the set, such
as the total number of distinct points dominated by the points in the subset,
although it is constrained to an output parameter $k<s$.

The algorithm to compute the skyline order $S=\\{S_{1},S_{2},...,S_{n}\\}$
proceeds by iteratively computing each $S_{i}$, the so-called skyline subset,
as the skyline of $P\setminus\bigcup_{j=1}^{i-1}S_{j}$, where $P$ is the set
of all points and $S_{1}$ is the skyline of $P$, until all points belong to a
subset: thus, points in $P$ are partially ranked and partitioned in skyline
layers that are then used to select the top-k points; in fact each skyline
subset is sequentially checked and merged into the output set $S$ if its
cardinality is less than the requested size $k$, until the remaining points
have to be selected from the last skyline subset using a set-wide maximization
technique.

####  2.2.2 k-Representative Skyline

The idea behind k-Representative Skyline is to quantify the descriptive power
of points in a skyline set so that the user is able to make accurate decisions
even though only a small sample of $k$ representative points of the dataset
have been analyzed. The approach described in [19] builds up a definition of
representativeness based on the dominance properties of the skyline points: in
particular, $k$ points are selected such that the number of points dominated
by one of the points in the set is maximized.

The same concept is proposed in [20], although with a different definition of
representativeness in order to capture more efficiently and more concisely the
contour of the skyline: $k$ points are selected such that the maximum distance
between a non-representative point and its closest representative is
minimized. Experimental results show that the latter approach provides a more
adequate summary of the dataset, with better precision as the parameter $k$
increases.

####  2.2.3 SKYRANK

The SKYRANK framework [21] exploits the idea of link-based ranking to select
the most interesting tuples from a skyline set. In order to do that, a graph-
based structure is built, called skyline graph, where nodes are all the
skyline points and edges are the subspace dominance relationships, which are
used to determine the interestingness of the skyline points: given a dataset
$D$ a point $p\in D$ is said to dominate another point $q\in D$ on subspace
$U$, denoted as $p\prec_{q}q$ if (1) on every dimension $d_{i}\in U$,
$p_{i}\leq q_{i}$ and (2) on at least one dimension $d_{j}\in U$,
$p_{j}<q_{j}$. This approach integrates both the concept of k-dominance [22],
which is introduced to increase the probability of a point to be dominated by
simply relaxing the notion of dominance to a subset of dimensions, thus
decreasing the skyline size, and the concept of skyline frequency [23], which
takes into account how often tuples are returned as a result of a skyline
query when different dimensions are considered.

By construction, the SKYRANK framework also supports personalized Top-k
Skyline queries, since it is able to take into account user preferences in the
form of a particular subset of dimensions $PRF=\\{U_{1},...,U_{m}\\}$ used to
compute the subspace dominance relationships between skyline points, where
each dimension represent a specific attribute of interest of the user’s query.

###  2.3 Regret Minimization Queries

This category of techniques approaches the problem of multi-criteria decision
making with a different perspective: an unknown scoring function is assumed,
as in the traditional Skyline scenario, therefore, in order to select the most
interesting tuples from the skyline set a regret measure is taken into
account, i.e. the disappointment of the user seeing the k-regret result set
with respect to the result he would have expected from the whole dataset. A
thorough survey on regret minimization queries is proposed in [24], here we
summarize some of the most interesting techniques.

####  2.3.1 k-Representative Regret Minimization

The k-regret operator [25] computes a subset of $k$ skyline points by
minimizing the so called maximum regret ratio: given a dataset $D$, a subset
of points $S\subseteq D$ and a scoring function $f$, the regret ratio is
computed as

$rr_{D}(S,f)=\frac{gain(D,f)-gain(S,f)}{gain(D,f)}$

where the gain of a set is the maximum score obtained through the specified
utility function $f$ by some point belonging to that set; in this particular
scenario though, the scoring function $f$ is not known, hence the maximum
regret ratio is introduced, which takes into account a class of scoring
functions $\mathcal{F}$. In particular, the authors demonstrate that for non-
decreasing linear scoring functions, which in practice are good models of
human reasoning for preference assignment, both a lower and an upper bound can
be found as a function of the output parameter $k$ and the dimensionality $d$:
this makes the k-regret operator not only scale-invariant but also stable,
i.e. adding unimportant tuples in the dataset will not change the output
result.

The concept of regret minimization here described focuses on the minimization
of the user’s regret while guaranteeing the query output size to be $k$,
although there exist some other studies [26, 27] which take on the same
problem focusing on the minimization of the output size while guaranteeing a
specified happiness ratio $\alpha$.

####  2.3.2 k-Regret Minimizing Set

The authors of [28] base their research on the k-regret operator proposed in
[25]: in particular they relax the criterion for determining user happiness by
generalizing the regret ratio, which considers the theoretical best point of a
subset, to a k-regret ratio which measures how far from the $k$-th best point
is the best point; thus, given a dataset $D$, a subset of points $S\subseteq
D$ and a weight vector $w$, the k-regret ratio is computed as

$k\text{-}regratio(S,w)=\frac{max(0,kgain(D,w)-1gain(S,w))}{kgain(D,w)}$

where the kgain represents the score of the $k$-ranked point in $S$, hence
1gain corresponds to the definition of gain previously introduced in [25]. The
maximum k-regret ratio is computed taking into account all possible weight
vectors $w$. This new regret definition does not require to include in the
query result the user’s top choice in order to make him happy. Since $k$ is
used as a rank parameter, the parameter that constrains the output size is now
$r$, and an algorithm is presented to compute the k-regret minimizing set of
order $r$ both for 2 dimensional datasets and, even though not optimal, for
more than 2 dimensions.

An interesting extension of the k-regret operator is introduced in [29], where
an additional set of binary constraints provided by the user is taken into
consideration: this particular technique aims at selecting points that not
only minimize the maximum regret ratio, but also maximize the satisfaction of
a set of binary constraints $C=\\{c_{1},...,c_{r}\\}$, where a generic $c_{i}$
is a true/false condition.

####  2.3.3 ReDi

The purpose of ReDi [30] is to combine the principle of regret minimization
with the one of diversity maximization; these two approaches share the
objective of identifying a representative set of tuples among the full
dataset, even though they serve very different needs: the former aims at
determining a subset of data that satisfies the user the most, the latter at
providing data that has good coverage on the dataset and low redundancy.
Nevertheless, as the authors point out, typically the user is able to provide
query preferences only for a subset of attributes, expecting to get some more
insights about the attributes that have not been taken into consideration from
the result itself: hence the need of capturing diverse objects that summarize
the unsolicited part of information that is stored in the dataset. This is
achieved with the definition of a hybrid cost function:

$\mathcal{F}(S,G,P,\lambda)=\lambda\frac{\sum_{i=1}^{k}\sum_{j>i}^{k}d(p_{i},p_{j})}{\max\limits_{p_{i},p_{j}\in
P}d(p_{i},p_{j})}+(1-\lambda)\frac{k(k-1)}{2}(1-rr_{P}(S,G))$

where $P$ is a query result, $S\subseteq P$ is a subset of representative
points, $G$ is a class of scoring functions and $\lambda$ is the parameter
used to balance the tradeoff between the maximization of diversity and the
minimization of the regret-ratio.

##  3 Managing user preferences

Data-driven systems have emerged as a very profitable business model during
the last decade, thriving on the systematic organization of data to better
serve customers’ needs. Although the aspects related to modeling, integration
and visualization of data definitely play a crucial role in the data-driven
paradigm, it is indeed required to take into consideration the query
capabilities of these systems, hence the implementation of appropriate tools
that make possible the extraction of useful information from the data. As
already stated in section 1, the process of information retrieval largely
benefits from a user-centered approach which specifically adjust the query
result to the user’s preference profile, relying on a set of directly or
indirectly determined input preferences. In this section we summarize the
capabilities of the previously introduced query techniques to act as
preference management frameworks, hence their ability to personalize the query
process, control the output size, relax and adapt preference criteria.

###  3.1 Preferential query answering

The integration of user preferences in the query process is a critical aspect
to take into account in many scenarios based on human-computer interaction,
particularly in the web domain, where product search or recommender systems
are two representative examples, but also in apparently distant domains such
as cache management [31] or publish/subscribe systems [32]. The first step is
preference representation: this can be done in a qualitative manner, for
instance using binary predicates to compare tuples, or in a quantitative
manner, using scoring functions to express a degree of interest.

| Representation | Processing
---|---|---
|  |  Qualitative |  Quantitative |  Attribute space |  Support data structures
FLEXIBLE SKYLINES |  R-Skylines [9] |  | ✓ | ✓ |
Uncertain top-k queries [12] |  | ✓ | ✓ |
P-Skylines [13] | ✓ |  |  | ✓
Trade-off Skylines [16] | ✓ |  | ✓ | ✓
SKYLINE RANKING |  Skyline ordering [18] | – | – | ✓ |
k-Representative Skylines [19] | – | – | ✓ |
SKYRANK [21] | ✓ |  | ✓ | ✓
REGRET MINIMIZATION QUERIES |  k-Representative regret minimization [25] |  | ✓ | ✓ |
k-Regret Minimizing Sets [28] |  | ✓ | ✓ |
ReDi [30] |  | ✓ | ✓ |
Table 1: Comparison of strategies used to support preferential query answering

Typically, preferences are stored in a user profile, which is then used to
select, based on context information, the query preferences to adopt during
the processing step. As shown in Table 1, most techniques rely on a
quantitative representation of the user preferences, be it a class of scoring
functions or a region surrounding a preference vector. Few other techniques
instead make use of a qualitative representation using preference formulas
(P-Skylines, Trade-off Skylines) or preference dimensions sets (SKYRANK).

Skyline Ranking techniques, except for SKYRANK, do not take into consideration
user query preferences, instead they rely on the properties of the skyline
set, such as the maximum number of dominated points or the maximum distance
between a non-representative point and its closest representative, without
having a specific user in mind.

As far as the processing is concerned, practically all the examined techniques
exploit the geometry of the multi-criteria optimization problem to compute the
query result. It is worth highlighting few exceptions, P-Skylines, Trade-off
Skylines and SKYRANK, which adopt a graph-based approach to test dominance
relationships.

###  3.2 Controlling output size

The ability to formulate constraints over the query output size is crucial for
the interestingness of the result, since the user might be only interested in
a limited number of objects to choose from or in getting the gist of the
information that resides in the dataset: if the output size is unmanageable,
the decision-making process of the user can be compromised.

|  |  Relaxation of dominance |  User preferences integration |  Representative identification |  Restriction to attribute subspaces
---|---|---|---|---|---
FLEXIBLE SKYLINES |  R-Skylines [9] | ✓ | ✓ |  |
Uncertain top-k queries [12] | ✓ | ✓ |  |
P-Skylines [13] |  | ✓ |  |
Trade-off Skylines [16] | ✓ | ✓ |  |
SKYLINE RANKING |  Skyline ordering [18] |  |  | ✓ |
k-Representative Skylines [19] |  |  | ✓ |
SKYRANK [21] | ✓ | ✓ | ✓ | ✓
REGRET MINIMIZATION QUERIES |  k-Representative regret minimization [25] |  |  | ✓ |
k-Regret Minimizing Sets [28] |  |  | ✓ |
ReDi [30] |  |  | ✓ | ✓
Table 2: Comparison of strategies used to reduce query output size

The reduction of the output size, as it is summarized in Table 2, can be
achieved using various approaches: Skyline Ranking and Regret Minimization
queries rely on the identification of representative tuples, whereas Flexible
Skylines tackle the problem by relaxing the traditional definition of
dominance; the former approach aims at filtering the output set using a
measure of “representativeness” which characterize the descriptive power of a
tuple with respect to the full dataset, hence the use of a regret-ratio which
measures how happy the user would be if he was given this filtered output in
Regret Minimization queries, or the exploitation of skyline properties to find
the most dominant (hence the most likely to be interesting) tuples in Skyline
Ranking: such a filtering approach allows the user to specify a parameter $k$
that represent the expected number of tuples to see as a result; the latter
approach instead focuses on the extension of the dominance region (hence to
the reduction of non-dominated tuples) by molding the “skyscrapers” of the
skyline into “pyramids” with the use of a more general set of input
preferences given by the user, or alternatively by restricting the dominance
check to a specific region around the user’s preference vector, as shown in
Figure 1: in this case the result size cannot be specified a priori, although
it is worth noting that the more user’s preference information is used in the
query process, the more the output set is expected to decrease in size. A
thorough analysis about how the problem of controlling the output size can be
addressed in the context of skyline queries is proposed in [33].

Figure 1: Techniques used in Flexible Skylines to reduce query output size,
from left to right: traditional Skyline, R-Skyline, Uncertain top-k queries

###  3.3 Input preferences flexibility

As previously discussed, preferential query answering is vital for finding
results that best satisfy the user’s requirements, yet it is a very delicate
matter because of a fundamental issue, discussed in [2]: the user is required
to be the decision maker despite the exploratory nature of its query, hence it
is necessary to deal with preference inconsistencies and lack of information.
This particular problem is at the core of Flexible Skylines, which deal with
it by overcoming the need of specifying a scoring function, thus relieving the
user from the responsibility of determining exact scores for each attribute:
this is achieved either by exploiting the geometry of the attribute weight
space (R-Skylines, Uncertain Top-k queries) or by allowing a qualitative
preference formulation (P-Skylines, Trade-off Skylines); the former method
aims at generalizing the weight vector into a broader region in order to take
into account possible variations of the provided weights: R-Skylines do that
by asking the user a more general set of constraints that can also be more
easily elicited (e.g. price cannot be more than 3 times the mileage), whereas
Uncertain Top-k queries start from a weight vector (which can be
computationally inferred) and expand it into a region so that all the
surrounding weight vectors are considered in the query process as well; the
latter tackle the flexibility issue upstream, by using a different method not
only to represent user preferences but also to extract them: P-Skylines for
instance use a feedback based approach that directly or indirectly involve the
user for the identification of desirable and undesirable tuples, which will be
used to build its preference profile.

Skyline Ranking and Regret Minimization queries techniques on the other hand,
although they also do not require the user to specify a scoring function,
provide no flexibility at all, since they only allow to specify the size
parameter $k$ (or a happiness ratio parameter $\alpha$).

##  4 Discussion

In this survey we examine various techniques to take on the problem of multi-
objective optimization in the context of preference-based queries. We discuss
about preference representation and not only how, but also with which degree
of flexibility user preferences are integrated in the query process: it
emerges that a quantitative representation that makes use of scoring functions
is the preferred approach, although qualitative representations are also used
to take into account trade-offs or binary constraints over attributes;
preferences are mostly processed directly inside the attribute space as linear
constraints on attribute weights, making the dominance test a linear
programming problem, despite few exceptions where a graph-based approach is
used, exploiting link-based ranking techniques. We highlight the benefits on
the size of the output set derived from the integration of user preference
information in the query process, and we show the different control
capabilities over the size parameter.

## References

  * [1] S. Börzsönyi, D. Kossmann, and K. Stocker, “The skyline operator,” in Proceedings of the 17th International Conference on Data Engineering, April 2-6, 2001, Heidelberg, Germany (D. Georgakopoulos and A. Buchmann, eds.), pp. 421–430, IEEE Computer Society, 2001.
  * [2] P. Pu and L. Chen, “User-involved preference elicitation for product search and recommender systems,” AI Mag., vol. 29, no. 4, pp. 93–103, 2008\.
  * [3] W. E. Hick, “On the rate of gain of information,” Quarterly Journal of Experimental Psychology, vol. 4, no. 1, pp. 11–26, 1952.
  * [4] J. Chomicki, “Querying with intrinsic preferences,” in Advances in Database Technology - EDBT 2002, 8th International Conference on Extending Database Technology, Prague, Czech Republic, March 25-27, Proceedings (C. S. Jensen, K. G. Jeffery, J. Pokorný, S. Saltenis, E. Bertino, K. Böhm, and M. Jarke, eds.), vol. 2287 of Lecture Notes in Computer Science, pp. 34–51, Springer, 2002.
  * [5] R. Agrawal and E. L. Wimmers, “A framework for expressing and combining preferences,” SIGMOD Rec., vol. 29, p. 297–306, may 2000.
  * [6] K. Mouratidis, K. Li, and B. Tang, “Marrying top-k with skyline queries: Relaxing the preference input while producing output of controllable size,” in SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021 (G. Li, Z. Li, S. Idreos, and D. Srivastava, eds.), pp. 1317–1330, ACM, 2021.
  * [7] P. Godfrey, R. Shipley, and J. Gryz, “Maximal vector computation in large data sets,” in Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 - September 2, 2005 (K. Böhm, C. S. Jensen, L. M. Haas, M. L. Kersten, P. Larson, and B. C. Ooi, eds.), pp. 229–240, ACM, 2005.
  * [8] R. Fagin, A. Lotem, and M. Naor, “Optimal aggregation algorithms for middleware,” in Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 21-23, 2001, Santa Barbara, California, USA (P. Buneman, ed.), ACM, 2001\.
  * [9] P. Ciaccia and D. Martinenghi, “Reconciling skyline and ranking queries,” Proc. VLDB Endow., vol. 10, no. 11, pp. 1454–1465, 2017.
  * [10] P. Ciaccia and D. Martinenghi, “Flexible skylines: Dominance for arbitrary sets of monotone functions,” ACM Trans. Database Syst., vol. 45, no. 4, pp. 18:1–18:45, 2020.
  * [11] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “Progressive skyline computation in database systems,” ACM Trans. Database Syst., vol. 30, no. 1, pp. 41–82, 2005.
  * [12] K. Mouratidis and B. Tang, “Exact processing of uncertain top-k queries in multi-criteria settings,” Proc. VLDB Endow., vol. 11, no. 8, pp. 866–879, 2018.
  * [13] D. Mindolin and J. Chomicki, “Preference elicitation in prioritized skyline queries,” VLDB J., vol. 20, no. 2, pp. 157–182, 2011.
  * [14] J. Chomicki, “Preference formulas in relational queries,” ACM Trans. Database Syst., vol. 28, no. 4, pp. 427–466, 2003.
  * [15] J. Lee, G. You, and S. Hwang, “Telescope: Zooming to interesting skylines,” in Advances in Databases: Concepts, Systems and Applications, 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9-12, 2007, Proceedings (K. Ramamohanarao, P. R. Krishna, M. K. Mohania, and E. Nantajeewarawat, eds.), vol. 4443 of Lecture Notes in Computer Science, pp. 539–550, Springer, 2007.
  * [16] C. Lofi, U. Güntzer, and W. Balke, “Efficient computation of trade-off skylines,” in EDBT 2010, 13th International Conference on Extending Database Technology, Lausanne, Switzerland, March 22-26, 2010, Proceedings (I. Manolescu, S. Spaccapietra, J. Teubner, M. Kitsuregawa, A. Léger, F. Naumann, A. Ailamaki, and F. Özcan, eds.), vol. 426 of ACM International Conference Proceeding Series, pp. 597–608, ACM, 2010.
  * [17] W. Balke, U. Güntzer, and C. Lofi, “Incremental trade-off management for preference-based queries,” Int. J. Comput. Sci. Appl., vol. 4, no. 2, pp. 75–91, 2007.
  * [18] H. Lu, C. S. Jensen, and Z. Zhang, “Flexible and efficient resolution of skyline query size constraints,” IEEE Trans. Knowl. Data Eng., vol. 23, no. 7, pp. 991–1005, 2011.
  * [19] X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang, “Selecting stars: The k most representative skyline operator,” in Proceedings of the 23rd International Conference on Data Engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey, April 15-20, 2007 (R. Chirkova, A. Dogac, M. T. Özsu, and T. K. Sellis, eds.), pp. 86–95, IEEE Computer Society, 2007\.
  * [20] Y. Tao, L. Ding, X. Lin, and J. Pei, “Distance-based representative skyline,” in Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29 2009 - April 2 2009, Shanghai, China (Y. E. Ioannidis, D. L. Lee, and R. T. Ng, eds.), pp. 892–903, IEEE Computer Society, 2009.
  * [21] A. Vlachou and M. Vazirgiannis, “Ranking the sky: Discovering the importance of skyline points through subspace dominance relationships,” Data Knowl. Eng., vol. 69, no. 9, pp. 943–964, 2010.
  * [22] C. Y. Chan, H. V. Jagadish, K. Tan, A. K. H. Tung, and Z. Zhang, “Finding k-dominant skylines in high dimensional space,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, USA, June 27-29, 2006 (S. Chaudhuri, V. Hristidis, and N. Polyzotis, eds.), pp. 503–514, ACM, 2006.
  * [23] C. Y. Chan, H. V. Jagadish, K. Tan, A. K. H. Tung, and Z. Zhang, “On high dimensional skylines,” in Advances in Database Technology - EDBT 2006, 10th International Conference on Extending Database Technology, Munich, Germany, March 26-31, 2006, Proceedings (Y. E. Ioannidis, M. H. Scholl, J. W. Schmidt, F. Matthes, M. Hatzopoulos, K. Böhm, A. Kemper, T. Grust, and C. Böhm, eds.), vol. 3896 of Lecture Notes in Computer Science, pp. 478–495, Springer, 2006.
  * [24] M. Xie, R. C. Wong, and A. Lall, “An experimental survey of regret minimization query and variants: bridging the best worlds between top-k query and skyline query,” VLDB J., vol. 29, no. 1, pp. 147–175, 2020.
  * [25] D. Nanongkai, A. D. Sarma, A. Lall, R. J. Lipton, and J. J. Xu, “Regret-minimizing representative databases,” Proc. VLDB Endow., vol. 3, no. 1, pp. 1114–1124, 2010.
  * [26] M. Xie, R. C. Wong, P. Peng, and V. J. Tsotras, “Being happy with the least: Achieving $\alpha$-happiness with minimum number of tuples,” in 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020, pp. 1009–1020, IEEE, 2020.
  * [27] P. K. Agarwal, N. Kumar, S. Sintos, and S. Suri, “Efficient algorithms for k-regret minimizing sets,” in 16th International Symposium on Experimental Algorithms, SEA 2017, June 21-23, 2017, London, UK (C. S. Iliopoulos, S. P. Pissis, S. J. Puglisi, and R. Raman, eds.), vol. 75 of LIPIcs, pp. 7:1–7:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [28] S. Chester, A. Thomo, S. Venkatesh, and S. Whitesides, “Computing k-regret minimizing sets,” Proc. VLDB Endow., vol. 7, no. 5, pp. 389–400, 2014\.
  * [29] Q. Dong, J. Zheng, X. Qiu, and X. Huang, “Efficient approximate algorithms for k-regret queries with binary constraints,” in Web Information Systems and Applications - 15th International Conference, WISA 2018, Taiyuan, China, September 14-15, 2018, Proceedings (X. Meng, R. Li, K. Wang, B. Niu, X. Wang, and G. Zhao, eds.), vol. 11242 of Lecture Notes in Computer Science, pp. 421–433, Springer, 2018.
  * [30] Z. Hussain, H. A. Khan, and M. A. Sharaf, “Diversifying with few regrets, but too few to mention,” in Proceedings of the Second International Workshop on Exploratory Search in Databases and the Web, ExploreDB 2015, Melbourne, VIC, Australia, May 31 - June 04, 2015 (G. Koutrika, L. V. S. Lakshmanan, M. Riedewald, and K. Stefanidis, eds.), pp. 27–32, ACM, 2015.
  * [31] M. Cherniack, E. F. Galvez, M. J. Franklin, and S. B. Zdonik, “Profile-driven cache management,” in Proceedings of the 19th International Conference on Data Engineering, March 5-8, 2003, Bangalore, India (U. Dayal, K. Ramamritham, and T. M. Vijayaraman, eds.), pp. 645–656, IEEE Computer Society, 2003.
  * [32] A. K. Dey, “Understanding and using context,” Pers. Ubiquitous Comput., vol. 5, no. 1, pp. 4–7, 2001.
  * [33] C. Lofi and W. Balke, “On skyline queries and how to choose from pareto sets,” in Advanced Query Processing, Volume 1: Issues and Trends (B. Catania and L. C. Jain, eds.), vol. 36 of Intelligent Systems Reference Library, pp. 15–36, Springer, 2013.