# Giving the Right Answer: a Brief Overview on How to Extend Ranking and
Skyline Queries

Sergio  Politecnico di Milano
Milan, Italy
<EMAIL_ADDRESS>SC  Politecnico di Milano
Milan, Italy
<EMAIL_ADDRESS>Cuzzucoli  Politecnico di Milano
Milan, Italy
<EMAIL_ADDRESS>
###### Abstract

To retrieve the best results in a database we use Top-K queries and Skyline
queries but some problems arise. The formers rely too much on user
preferences, which are difficult to quantify and may skew the fetching of the
data, while the latters tend to output too much data. In this paper, we
explore three different branches of research that seek to overcome such
limitations: Flexible/Restricted Skylines, Skyline Ordering/Ranking, and
Regret Minimization. We analyze how they work and we make comparisons among
them to guide the reader to choose the approach that best fits their use
cases.

Keywords: top-k, Skyline, query, flexible, ordering, ranking, regret,
minimization

##  1 Introduction

In the last years databases have dramatically increased in size. Since users
want to find useful information in them, this has led to the problem of
understanding how to actually output the most interesting records when
queried. Think, for example, of a database $r$, populated by $N$ entries
($e_{i}$ with $i\epsilon[1,N]$) described by M attributes each ($m_{i}$ with
$i\epsilon[1,M]$).

One of the simplest approaches to return the most interesting tuples is by
using top-k queries (also called ranking queries). In this case a m-objective
problem is simplified into a single objective one: the user provides a list of
weight vector $w=<w_{1},w_{2}....,w_{m}>$, a score is then computed via the
use a scoring function f ( one of the simplest ones is the inner product
$f(e_{i})=\sum_{i=1}^{M}{w_{i}*k_{i}}$ ) for every entry. Out of all the
entries, the first $k$ ones with the highest scores are retrieved. Another
alternative are Skyline queries. They revolve around the idea of dominance
among points: given two entries (here called points) $p_{1}$ and $p_{2}$,
$p_{1}$ is said to dominate $p_{2}$ ($p_{1}\prec p_{2}$) iff $p_{1}$ is not
worse than $p_{2}$ in any attribute and better than $p_{2}$ in at least one of
them. In this case, the desired results are contained in the Skyline (SKY(R)),
that is the set of points not dominated by any other point.

The idea behind top-k queries is that the weight offered by the user are
personal, thus the result list is expected to contain the points which are of
actual interest to them. The size of the result list can be easily controlled,
making it manageable for the user to check and select its preferred entry.
Unfortunately, these queries are very dependent on the values of user
preferences (a slight change in the weights leads to totally different result)
and these are generally very difficult to quantify. Since they do not offer a
global view of the database, they may exclude feasible points because the user
has input the ”wrong” values. The user could expand the pool of tuples simply
trying different combinations of weights and hoping to find the best result
eventually but this is not only expensive in terms of time, it does not
guarantee success. On the other hand, Skyline queries do not require a weight
list nor a scoring function, leaving user preferences out of the equation.
They assure that there is no point not in the Skyline preferrable to the
output since every point not in the Skyline is outperformed by at least one
point in it. Their main drawback is that they are unable to control the size
of the result list which grows especially in case of high dimensionality or
when data is anticorrelated. Returning a considerable chunk of the database
and expecting the user to easily pick up their preferred point is not ideal.

Due to these limitations numerous new studies have been conducted and they
have led to the creation of new procedures and algorithms which seek to
overcome them. In this survey we will focus on those techniques which fall
under three different categories, namely those based on Flexible and/or
Restricted Skylines, Skyline Ordering and/or Ranking, and Regret Minimization.
The rest of the paper is organized as follows: Section 2 is dedicated to
explaining flexible and/or restricted Skylines and their underlying concepts,
Section 3 focuses on Skyline ordering and/or ranking, Section 4 revolves
around the regret minimization approach and its expansions, in Section 5 a
comparison is made among all these approaches and their pros and cons are
evalutated, while Section 6 contains all the final considerations of the
paper.

##  2 Flexible and/or Restricted Skylines

All the techniques contained in this section try to suppress or mitigate the
shortcomings of the methods we have already mentioned, simply generalizing
them or improving their flexibility via the introduction of new operators,
which may also combine properties from top-k and Skyline queries.

###  2.1 Flexible Skylines

The R-Skyline, first introduced in [2], stands on the idea of F-dominance:
given two points $p_{1}$ and $p_{2}$ and a family of scoring functions
$F\subset M$, where $M$ is the family of Monotonone Functions (functions which
are always either increasing or decreasing), $p_{1}$ F-dominates $p_{2}$
($p_{1}\prec_{F}p_{2}$) when the score of $p_{1}$ is equal to or better than
that $p_{2}$ using every function contained in F. R-Skylines output two non-
dominated restricted Skyline of r with respect to F ($ND(r,F)$), which
contains all the tuples non-F-dominated in the database r, and the potentially
optimal restricted Skyline of r with respect to F, $PO(r,F)$, populated by the
Potentially Optimal Tuples, namely those tuples which are part of the Skyline
of at least one of the functions of the $F$ family. Since $F$ can include not
only finite but also infinite set of scoring function, as highlighted in [5],
it allows to express more general constraints w.r.t top-k queries but which
are indeed powerful in filtering unwanted tuples. Think of someone who wants
to buy a new house in Milan, choosing among the values of a database which
lists also the distance between the house and the Linate Airport and the
distance to the nearest subway station, both expressed in metres. With the
flexible Skylines just presented, they would be able to express a constraint
$F=\\{w_{S}*Subway+w_{L}*Linate|w_{M}\geq w_{C}\\}$ which states that they
prefer to have a station nearby than to live near the airport. This is one
example of a very simple constraint, but the framework allows even more
precise ones such as ”attribute $a_{1}$ is more important that $a_{2}$ but not
three times as important”, so the user in question could be able to tweak
their choices in order to better balance these two values. Anyway, the results
retrieved using these techniques are obviously of lower cardinality than those
of the Skyline as they filter some uninteresting points, in this case homes
that could be greater in size but that are not well served by underground
transportation. The problems which are tied to the insertion of personal
preferences are still included but at least they are mitigated as the
algorithms allows to implement general more general constraints than those
used by Top-K queries. This paper does not intend to examine in depth the
implementation of these methods, so the reader who wants to inform on the
algorithms used to implement R-Skyline is advised to check [2][3][5] The same
authors have also offered a way to rank object in case of multiple sources and
partially specified weights, described by the use of FSA in [4]. FSA is based
on Fagin’s Algorithm (FA) and the Treshold Algorithm (TA) but, differently
from them, it requires that weights not be explicitly specified but rather
expressed via a set of constraints, using the concept of F-dominance already
seen and proving its power in more than a single set of problems.

###  2.2 Uncertain Top-K

Another way to tackle the problem is given by the Uncertain Top-K Query (UTK),
described in [9], which deals with the uncertainty in the definition of a
Top-K Query using two different version: $UTK_{1}$ and $UTK_{2}$. $UTK_{1}$
reports all the tuples that rank among the top-k in a certain region R
delimited by an approximate description of the weight values. In this case the
result is minimal, meaning that the user is returned a set which contains
points that belong to the top-k set for at least one weight vector in R.
$UTK_{2}$ expands these results by reporting the top-k for every possible
weight vector that lies inside the region, practically returning a partition
of R which specifies the Top-K Query for every sub-region. These results allow
the user to inspect the top-k results for similar preferences. The novelty of
this approach is that it does not deal with uncertain data but with uncertain
queries and there are no probabilities affecting its output. Using this method
the user gets a broader view of the database w.r.t that offered by simple
Top-K Query, thus they suffer less backlash in the choice of the weights. In
addition, $UTK_{1}$ inherits from ranking queries the convenience of knowing
the cardinality of the results aforehand.

###  2.3 Trade-offs in Skyline

One of the reasons one prefers Skyline queries to Top-K ones is that they do
not need user preferences, which are unfeasible to quantify precisely. In [7],
the authors discuss the introduction of trade-off (and user preferences
conversely) to enhanche Skyline queries. The reasoning behind these choice is
that users tend to compromise on some attributes of a given object in order to
obtain some other values, a nuance which is not considered when Skylines are
computed. In fairness, these are personal choice and, in the examples of the
paper, impossible to estimate without external inputs. This is why [7]
requests that users indicate their Trade-off are inserted in the equation. For
example, let us suppose we have the database of an e-commerce site which sells
only smartphones, of which we will be discussing only the attributes cost and
OS for the sake of simplicity. The user who inputs the tradeoff
$t_{1}=((1200,AppearOS)\triangleright(1000,RobotaOS))$ is saying that they
would rather prefer Phone A, equipped with AppearOS, even tough it costs 1200$
, to Phone B that is 1000$ but that does not have RobotaOS, as a result
(Happear8, 1200, AppearOS) now dominates (SunPhone, 1000, RobotaOS) even tough
the opposite would be true using Skylines. This is only a simple example and
in the paper the authors explain how to chain more examples to form more
complicated ones. It is trivial to say that these choice is not dictated by
some hard mathematical law, the reason someone preferes an OS or a feature
over other qualities are not written in stone. That is where the strength of
this paradigm lies: in its ability to capture nuances that would otherwise be
lost and without which the results would be different. Obviously this method
retains some problems, not only there is no explicit limitation on the size of
the output, but there is still the problem of correctly assessing user
preferences.

##  3 Skyline Ordering/Ranking

Ranking Skyline points in order to allow the user to retrieve those that they
would feel most confident about is another branch of research that has
interested scholars who want to overcome the limitations of Skylines. As the
name suggest, the set of techniques here presented combine concepts of Skyline
and Top-K Query to offer a better result to the users.

###  3.1 Top-K Dominating

One of the simplest examples of this is Top-K Dominating Queries [16], that
return an output made of K elements which rank the best according to a scoring
function, just like any Top-K Query would do. The elements in question are
Skyline points ranked using the function ($\mu(p)$) which computes the score
for every point based on the number of points dominated by it.

###  3.2 Skyrank

A similar concept is exploited in [14], ranking different points using the
idea of subspace domination. Subspaces are those spaces generated by selecting
only a part of the dimensions of the database, so it is entirely possible for
point $p_{1}$ to dominate point $p_{2}$ only on one subspace out of all the
combinations. SKYRANK is a link-based algorithm which uses the subspace-
dominance metric to assign a weight to every point in the Skyline. What this
does is it creates a graph which shows the (subspace-)dominance, giving the
heaviest weight to those point which dominate the most points in different
subspaces, favoring them over extreme points, AKA the Skyline points of the
1-dimentional subspaces, which would normally appear using Skylines. The
strength of this approach is that it allows the user to have a balanced view
of the database, pruning those points that outperform others only on a single
dimension, it returns intersting point user and it reduces the number of
tuples returned to them, while simultaneously not requiring a preference
function. In addition, the authors point out that the algorithm can be
extended to accomodate Top-K queries.

###  3.3 Size Constrained Skyline

When we talk about Skyline computation, the first problem we think of is the
excessive number of tuples it returns,the authors of [8] argue that the
inability to control the size of the result causes problems even in the case
where the size of the result list is too low. For example, if someone wants to
buy five used vans for a small shipping company with a low budget, they will
not be happy if the e-commerce they use returns only a Skyline of three vans.
The algorithm we are about to discuss solves this problem merging the
pointwise approach, which is giving a score to the points and sorting them,
and the set-wide maximization approach, which considers a group of points,
instead of single ones, and maximizes a target value. In this case all the
data is partitioned into $S=\\{S_{1},S_{2},...,S_{n}\\}$ partitions, where
$S_{1}$ is the Skyline of the database, every point of $S_{i+1}$ is dominated
by at least one point in $S_{i}$ (the viceversa does not hold), and the union
of all the $S_{i}$ return the entire database. Put it simply, the way this is
formed is by computing the Skyline of the database and removing the points
contained in the Skyline, iteratively, until we are left with a layered
structure that contains all the points of the database. When a user requests
the best $k$ tuples of the database, the system proceeds to output them
according to the scores computed using the scoring function of choice ( e.g
the number of dominated points or subspace Skyline frequency). If $k>|S_{1}|$,
the method outputs all the points from $S_{1}$ then goes to the next layer,
$S_{2}$, and so on, until $k$ elements are returned.

###  3.4 Skyline Ordering Using Partially Ordered Domains

So far we assumed that, when ordering Skylines, we were able to establish an
order for every attribute we were discussing (e.g lower the price, increase
the horse power). In reality is not possible to outline an univocal order for
every kind of attribute present on the database, simply because many times
there is not a value which is objectively better than another one, such as in
the case of nominal attributes. An Appear phone is not preferrable to a
RobotaOS phone per se but a user could reason this way. This is often not
discussed: user preferences can be used to sort the points inside a Skyline,
asking the user if they prefer a precise value over another allows us to
further filter the results to give back to them, considerably reducing the
size of the output. This is the intuition behind [15]. In this paper, the
Skyline Query is contained in the Ordered Skyline Tree, or better in its
compressed form which is the CST or Compressed Ordered Skyline Tree. What this
structure does is it splits the Skyline into the global Skyline point set
($G$) and the order-sensitive Skyline point set ($D^{\prime}$), basically
precomputing how to return different results to different users with different
tastes or interests. The former set contains all the point which are part of
the Skyline in any case, the latter is susceptible to user choices. In the
work examined, such choices are expressed as partial orderings, for example
the user who prefers an Appear phone over a RobotaOS one one will impose
$AppearOS\geq RobotaOS$ and they will get an output which contains Appear
phone, filtering the RobotaOS ones they are not interested in. The peculiarity
of this approach is that it exploits an often overlooked set of attributes and
it mitigates the problems strictly tied to Skyline queries. The word
”mitigate” here is not used casually, unfortunately the resulting tuples can
still be high in number as there is no hard constraints on their cardinality.
Suppose that Appear is considered a luxury brand and, even tough it has a
considerable share of the marketplace, its phones still are far below the 50%
of the pool of the smartphones in circulation, the other ones mounting
RobotaOS; if a user imposes the constraint ”RobotaOS over AppearOS”, they will
still be inundated with results if no other constraints are imposed. This
approach improves with more constraints.

##  4 Regret Minimization

The regret minimization query is an approach first introduced in [11].
Differently from what we have seen so far, its objective is not to maximize
the satisfaction of the user but rather to minimize their dissatisfaction.
Similarly to Ranking Queries, it returns a fixed amount of tuples and, as
Skyline Queries do, it does not require to input a precise scoring function.
Via the use of the k-regret operator, the k-regrets query returns a
representative set of the database, composed of k elements, which aims to
minimize the value of the maximum regret ratio of the user, where the regret
ratio is the percentage of dissatisfaction they would have choosing one point
belonging to the result instead of the best single point present in the
database. This hypothesis is relaxed in [1] where the regret ratio is computed
using the result of a Top-K Query run on the database as a comparison, instead
of the best single point. In any case the k-regret operator is scale
invariant, thus the scale of the dimensions of the database does not change
the solution (the result does not change if an attribute is expressed in
meters or in miles), and it is stable, which means that the addition of junk
points, points which are not of interest to the user, has no effect on the
final results. The stability of the operator could be a much appreciated
property, for example in the case of the database of an e-commerce open to
every seller, as it avoids that someone games the algorithm used by the system
by placing a great deal of knock-off objects hoping to influence the results
returned to the user. Actually, the results are influenced by the choice of
the utility function (a synonym for the scoring funcion), as it mimics the
behavior of the happiness of the user. Since there is no way to know the which
utility function to use beforehand, many people default to using linear
utility ones, see for example [11], [17], [10]. This choice is dictated by the
fact that not only this is one of the simplest class of functions, but it
models efficiently the behavior of the user in most of the cases (the same
intuition behind Top-K Queries). However, the question on whether linear ones
are the best among the utility functions is not trivial. Falkner, Brackenbury
and Lall [6] capture a nuance which can’t be modeled by linear functions,
which is diminishing marginal returns, or the idea that the user loses
interest in the increase of the value of an attribute as it grows. For
example, suppose that you want to buy a new camera and that you can choose
between Camera A with 12 Megapixels and Camera B with B with 22 Megapixels, if
you value Megapixels, you will surely prefer B over A by a large margin.
Suppose now that you have yet another choice which is Camera C with 25
Megapixels: probably you will prefer C over B but less strongly than how you
prefer B over A, as the last choice is between two cameras that already have
many Megapixels. That is an example of reasoning behind the proposal for the
use of concave, convex or Constant Elasticity of Substitution (CES) functions,
further detailed in [12], that allow to better model these types of phenomena.
Another important aspect of the regret minimization problem revolves on what
metric to minimize. As already stated, [11] proposes to reduce the maximum
regret ratio as much as possible, but that is not the only option. The authors
in [17] argue that this choice produces a worst-case guarantee on the regret
ratio of the user, but it is not effective in keeping low the regret ratio for
the average user, saying that it should be the priority, thus they provide a
framework where the problem is formulated using the average regret ratio as a
metric. Still, these are both particular cases, so in [13] a unified algorithm
is produced which, by the use of ”oracles”, decides which of the two metrics
to use for the problem at hand. Finally, it is possible to relax also the
assumption that to minimize the regret ratio of the user no interaction is
needed. In [10], the regret minimization algorithm is enhanched with
interaction with the user, obtained by asking the user questions before the
computation of the results. This questions are asked in rounds and they
consist in requiring the user to pick a tuple between a set. The tuples can
also not even be in the database, as they are used just to understand how the
users weighs the different dimensions of the element, but they should be at
least representative of the actual points, least there is the risk of
disappointment in the result. The user can decide to stop whenever he/she
wants and, when it happens, be prompted with the results. The authors claim
that only a small set of questions is necessary to improve the results so even
tough the user has to put some effort in the research, at least the task is
not cumbersome.

##  5 Comparison

Table 1: A brief recap of the properties of the techniques Property | Flexible/Restricted Skylines | Skyline Ordering | Regret Minimization
---|---|---|---
User Interaction | Yes | Possible | Possible
Output Cardinality | Reduced/Fixed | Reduced/Fixed | Fixed
Scale Invariance |  | Yes | Yes
Stability | Yes | Yes | Yes

We have different approaches to improve the basic queries used to satisfy the
user, but since each one of them is different from the others and it carries
its own benefits and drawbacks, we are now going to draw a comparison to
better understand when to use them. As pointed in 1, generally flexible and/or
restricted Skyline are best exploited when the user is able to personalize
their research. This kind of queries allows to correlate different attributes
either by imposing constraints in order to to use R-Skylines, or to define
some weights to compute Uncertain Top-K Query, without having to worry to much
about having to tinker their values to get the best results, or to impose some
trade-offs to shape a better Skyline. In the first two cases it is also
possible to accurately limit the cardinality of the results thus we are sure
not to overwhelm the user with excessive information. In case we want to ease
(or outright eliminate) user interaction while still limiting the number of
tuples returned from the system, one of the best choices is surely using
Skyline Ordering. In the first scenario, we can still have a fixed amount of
elements output, if we rely on Top-K Dominating Queries, Skyrank or Size
Constrained Skyline Queries, without even asking the user for interaction. On
the other hand, if we accept to not be able to predict exactly how many
elements the user will have to inspect in order to pick its favorite, we can
exploit nominal values while keeping the global view of the Skyline, at the
cost of some simple constraints to be imposed by the user, a much needed
feature when we have a database filled with information that can’t be ordered
otherwise. Using Regret Minimization techniques we have to withstand some
uncertainty in the results but we are able to better predict how much the user
will be interested in a set of fixed values while not having to even define a
precise scoring function in the process. Furthermore, if we want to reduce
said uncertainty, we can just enable some basic user interaction to refine the
results.

##  6 Conclusions

In this paper we have review how to go beyond the use of Top-K and Skyline
queries in order to avoid the complications and drawbacks they carry. We have
done so by splitting our analysis into three different families of approaches
and outling their pros and cons, finally we have tried to outline also some
scenarios in which to use one approach or the other. We came to the conclusion
that it is best to use Flexible and/or Restricted Skylines when there is no
problem in asking the user their scoring function. If the user has partial
knowledge of their preferences and they are willing to pick a point among
those we give them, ordering the Skyline is acceptable. In the case where the
user does not know how to impose an order, but they can possibly accept some
minor interaction and some imprecision in the result, regret minimization is
possible.

## References

  * [1] Sean Chester, Alex Thomo, S. Venkatesh, and Sue Whitesides.  Computing k-regret minimizing sets.  Proc. VLDB Endow., 7(5):389–400, 2014.
  * [2] Paolo Ciaccia and Davide Martinenghi.  Reconciling skyline and ranking queries.  Proc. VLDB Endow., 10(11):1454–1465, 2017.
  * [3] Paolo Ciaccia and Davide Martinenghi.  Beyond skyline and ranking queries: Restricted skylines (extended abstract).  In Sonia Bergamaschi, Tommaso Di Noia, and Andrea Maurino, editors, Proceedings of the 26th Italian Symposium on Advanced Database Systems, Castellaneta Marina (Taranto), Italy, June 24-27, 2018, volume 2161 of CEUR Workshop Proceedings. CEUR-WS.org, 2018.
  * [4] Paolo Ciaccia and Davide Martinenghi.  FA + TA <fsa: Flexible score aggregation.  In Alfredo Cuzzocrea, James Allan, Norman W. Paton, Divesh Srivastava, Rakesh Agrawal, Andrei Z. Broder, Mohammed J. Zaki, K. Selçuk Candan, Alexandros Labrinidis, Assaf Schuster, and Haixun Wang, editors, Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018, pages 57–66. ACM, 2018.
  * [5] Paolo Ciaccia and Davide Martinenghi.  Flexible skylines: Dominance for arbitrary sets of monotone functions.  ACM Trans. Database Syst., 45(4):18:1–18:45, 2020.
  * [6] Taylor Kessler Faulkner, Will Brackenbury, and Ashwin Lall.  k-regret queries with nonlinear utilities.  Proc. VLDB Endow., 8(13):2098–2109, 2015.
  * [7] Christoph Lofi, Ulrich Güntzer, and Wolf-Tilo Balke.  Efficient computation of trade-off skylines.  In Ioana Manolescu, Stefano Spaccapietra, Jens Teubner, Masaru Kitsuregawa, Alain Léger, Felix Naumann, Anastasia Ailamaki, and Fatma Özcan, editors, EDBT 2010, 13th International Conference on Extending Database Technology, Lausanne, Switzerland, March 22-26, 2010, Proceedings, volume 426 of ACM International Conference Proceeding Series, pages 597–608. ACM, 2010.
  * [8] Hua Lu, Christian S. Jensen, and Zhenjie Zhang.  Flexible and efficient resolution of skyline query size constraints.  IEEE Trans. Knowl. Data Eng., 23(7):991–1005, 2011.
  * [9] Kyriakos Mouratidis and Bo Tang.  Exact processing of uncertain top-k queries in multi-criteria settings.  Proc. VLDB Endow., 11(8):866–879, 2018.
  * [10] Danupon Nanongkai, Ashwin Lall, Atish Das Sarma, and Kazuhisa Makino.  Interactive regret minimization.  In K. Selçuk Candan, Yi Chen, Richard T. Snodgrass, Luis Gravano, and Ariel Fuxman, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 109–120. ACM, 2012.
  * [11] Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J. Lipton, and Jun (Jim) Xu.  Regret-minimizing representative databases.  Proc. VLDB Endow., 3(1):1114–1124, 2010.
  * [12] Jianzhong Qi, Fei Zuo, Hanan Samet, and Jia Cheng Yao.  K-regret queries using multiplicative utility functions.  ACM Trans. Database Syst., 43(2):10:1–10:41, 2018.
  * [13] Suraj Shetiya, Abolfazl Asudeh, Sadia Ahmed, and Gautam Das.  A unified optimization algorithm for solving ”regret-minimizing representative” problems.  Proc. VLDB Endow., 13(3):239–251, 2019.
  * [14] Akrivi Vlachou and Michalis Vazirgiannis.  Ranking the sky: Discovering the importance of skyline points through subspace dominance relationships.  Data Knowl. Eng., 69(9):943–964, 2010.
  * [15] Raymond Chi-Wing Wong, Jian Pei, Ada Wai-Chee Fu, and Ke Wang.  Online skyline analysis with dynamic preferences on nominal attributes.  IEEE Trans. Knowl. Data Eng., 21(1):35–49, 2009.
  * [16] Man Lung Yiu and Nikos Mamoulis.  Efficient processing of top-k dominating queries on multi-dimensional data.  In Christoph Koch, Johannes Gehrke, Minos N. Garofalakis, Divesh Srivastava, Karl Aberer, Anand Deshpande, Daniela Florescu, Chee Yong Chan, Venkatesh Ganti, Carl-Christian Kanne, Wolfgang Klas, and Erich J. Neuhold, editors, Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007, pages 483–494. ACM, 2007.
  * [17] Sepanta Zeighami and Raymond Chi-Wing Wong.  Finding average regret ratio minimizing set in database.  In 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019, pages 1722–1725. IEEE, 2019.


* Laor (1991) Laor, A. 1991, ApJ, 376, 90, doi: 10.1086/170257
  * Leighly (1999a) Leighly, K. M. 1999a, ApJS, 125, 297, doi: 10.1086/313277
  * Leighly (1999b) —. 1999b, ApJs, 125, 317, doi: 10.1086/313287
  * Liddle (2007) Liddle, A. R. 2007, Monthly Notices of the Royal Astronomical Society: Letters, 377, L74, doi: 10.1111/j.1745-3933.2007.00306.x
  * Longair (1992) Longair, M. S. 1992, High energy astrophysics. Vol.1: Particles, photons and their detection (Cambridge University Press)
  * Madsen et al. (2020) Madsen, K. K., Grefenstette, B. W., Pike, S., et al. 2020, arXiv e-prints, arXiv:2005.00569, doi: 10.48550/arXiv.2005.00569
  * Madsen et al. (2015) Madsen, K. K., Harrison, F. A., Markwardt, C. B., et al. 2015, ApJS, 220, 8, doi: 10.1088/0067-0049/220/1/8
  * Magdziarz et al. (1998) Magdziarz, P., Blaes, O. M., Zdziarski, A. A., Johnson, W. N., & Smith, D. A. 1998, MNRAS, 301, 179, doi: 10.1046/j.1365-8711.1998.02015.x
  * Magdziarz & Zdziarski (1995) Magdziarz, P., & Zdziarski, A. A. 1995, MNRAS, 273, 837, doi: 10.1093/mnras/273.3.837
  * Marin (2016) Marin, F. 2016, MNRAS, 460, 3679, doi: 10.1093/mnras/stw1131
  * Mathews (2021) Mathews, W. G. 2021, MNRAS, 506, 2030, doi: 10.1093/mnras/stab1745
  * Mathur (2000) Mathur, S. 2000, MNRAS, 314, L17, doi: 10.1046/j.1365-8711.2000.03530.x
  * Matsushita et al. (1998) Matsushita, K., Makishima, K., Ikebe, Y., et al. 1998, The Astrophysical Journal, 499, L13, doi: 10.1086/311339
  * Mazzarella & Balzano (1986) Mazzarella, J. M., & Balzano, V. A. 1986, ApJS, 62, 751, doi: 10.1086/191155
  * Merloni et al. (2024) Merloni, A., Lamer, G., Liu, T., et al. 2024, arXiv e-prints, arXiv:2401.17274, doi: 10.48550/arXiv.2401.17274
  * Minezaki et al. (2019) Minezaki, T., Yoshii, Y., Kobayashi, Y., et al. 2019, ApJ, 886, 150, doi: 10.3847/1538-4357/ab4f7b
  * Miniutti & Fabian (2004) Miniutti, G., & Fabian, A. C. 2004, MNRAS, 349, 1435, doi: 10.1111/j.1365-2966.2004.07611.x
  * Morganti (2017) Morganti, R. 2017, Frontiers in Astronomy and Space Sciences, 4, doi: 10.3389/fspas.2017.00042
  * Nandra et al. (1997) Nandra, K., George, I. M., Mushotzky, R. F., Turner, T. J., & Yaqoob, T. 1997, ApJ, 477, 602, doi: 10.1086/303721
  * Nandra et al. (2013) Nandra, K., Barret, D., Barcons, X., et al. 2013, arXiv e-prints, arXiv:1306.2307, doi: 10.48550/arXiv.1306.2307
  * Netzer (2013) Netzer, H. 2013, The Physics and Evolution of Active Galactic Nuclei. (Cambridge University Press).  https://search.ebscohost.com/login.aspx?direct=true&db=nlebk&AN=527870&site=ehost-live
  * O’Dea (1998) O’Dea, C. P. 1998, PASP, 110, 493, doi: 10.1086/316162
  * Oh et al. (2018) Oh, K., Koss, M., Markwardt, C. B., et al. 2018, ApJS, 235, 4, doi: 10.3847/1538-4365/aaa7fd
  * Osterbrock & Pogge (1985) Osterbrock, D. E., & Pogge, R. W. 1985, ApJ, 297, 166, doi: 10.1086/163513
  * Pan et al. (2019) Pan, X., Lu, H., Komossa, S., et al. 2019, ApJ, 870, 75, doi: 10.3847/1538-4357/aaf1bc
  * Pan et al. (2021) Pan, X., Zhou, H., Yang, C., et al. 2021, ApJ, 912, 118, doi: 10.3847/1538-4357/abf148
  * Park et al. (2006) Park, T., Kashyap, V. L., Siemiginowska, A., et al. 2006, ApJ, 652, 610, doi: 10.1086/507406
  * Parker et al. (2013) Parker, M. L., Marinucci, A., Brenneman, L., et al. 2013, Monthly Notices of the Royal Astronomical Society, 437, 721, doi: 10.1093/mnras/stt1925
  * Parker et al. (2014) Parker, M. L., Walton, D. J., Fabian, A. C., & Risaliti, G. 2014, MNRAS, 441, 1817, doi: 10.1093/mnras/stu712
  * Parma et al. (2007) Parma, P., Murgia, M., de Ruiter, H. R., et al. 2007, A&A, 470, 875, doi: 10.1051/0004-6361:20077592
  * Peterson (1997) Peterson, B. M. 1997, An Introduction to Active Galactic Nuclei (Cambridge University Press)
  * Peterson & Wandel (1999) Peterson, B. M., & Wandel, A. 1999, ApJ, 521, L95, doi: 10.1086/312190
  * Peterson et al. (2004) Peterson, B. M., Ferrarese, L., Gilbert, K. M., et al. 2004, ApJ, 613, 682, doi: 10.1086/423269
  * Ponti et al. (2012) Ponti, G., Papadakis, I., Bianchi, S., et al. 2012, A&A, 542, A83, doi: 10.1051/0004-6361/201118326
  * Pounds et al. (1995) Pounds, K. A., Done, C., & Osborne, J. P. 1995, MNRAS, 277, L5, doi: 10.1093/mnras/277.1.L5
  * Pounds et al. (2018) Pounds, K. A., Nixon, C. J., Lobban, A., & King, A. R. 2018, MNRAS, 481, 1832, doi: 10.1093/mnras/sty2359
  * Predehl et al. (2021) Predehl, P., Andritschke, R., Arefiev, V., et al. 2021, A&A, 647, A1, doi: 10.1051/0004-6361/202039313
  * Puchnarewicz et al. (1992) Puchnarewicz, E. M., Mason, K. O., Cordova, F. A., et al. 1992, MNRAS, 256, 589, doi: 10.1093/mnras/256.3.589
  * Ranalli et al. (2003) Ranalli, P., Comastri, A., & Setti, G. 2003, A&A, 399, 39, doi: 10.1051/0004-6361:20021600
  * Robertis et al. (1998) Robertis, M. M. D., Hayhoe, K., & Yee, H. K. C. 1998, The Astrophysical Journal Supplement Series, 115, 163, doi: 10.1086/313089
  * Rodríguez-Ardila & Mazzalay (2006) Rodríguez-Ardila, A., & Mazzalay, X. 2006, MNRAS: Letters, 367, L57, doi: 10.1111/j.1745-3933.2006.00139.x
  * Ross & Fabian (2005) Ross, R. R., & Fabian, A. C. 2005, MNRAS, 358, 211, doi: 10.1111/j.1365-2966.2005.08797.x
  * Ruschel-Dutra et al. (2016) Ruschel-Dutra, D., Rodríguez Espinosa, J. M., González Martán, O., Pastoriza, M., & Riffel, R. 2016, MNRAS, 466, 3353, doi: 10.1093/mnras/stw3276
  * Rybicki & Lightman (1979) Rybicki, G. B., & Lightman, A. P. 1979, Radiative processes in astrophysics (Wiley)
  * Sani et al. (2010) Sani, E., Lutz, D., Risaliti, G., et al. 2010, MNRAS, 403, 1246, doi: 10.1111/j.1365-2966.2009.16217.x
  * Seyfert (1943) Seyfert, C. K. 1943, ApJ, 97, 28, doi: 10.1086/144488
  * Shakura & Sunyaev (1973) Shakura, N. I., & Sunyaev, R. A. 1973, A&A, 500, 33
  * Smirnova-Pinchukova et al. (2022) Smirnova-Pinchukova, I., Husemann, B., Davis, T. A., et al. 2022, A&A, 659, A125, doi: 10.1051/0004-6361/202142011
  * Smith et al. (2001) Smith, R. K., Brickhouse, N. S., Liedahl, D. A., & Raymond, J. C. 2001, ApJ, 556, L91, doi: 10.1086/322992
  * Smith et al. (2019) Smith, R. K., Abraham, M., Baird, G., et al. 2019, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 11118, UV, X-Ray, and Gamma-Ray Space Instrumentation for Astronomy XXI, ed. O. H. Siegmund, 111180W, doi: 10.1117/12.2529499
  * Sugiura (1978) Sugiura, N. 1978, Communications in Statistics - Theory and Methods, 7, 13, doi: 10.1080/03610927808827599
  * Tan & Biswas (2012) Tan, M. Y. J., & Biswas, R. 2012, Monthly Notices of the Royal Astronomical Society, 419, 3292, doi: 10.1111/j.1365-2966.2011.19969.x
  * Tanaka et al. (2004) Tanaka, Y., Boller, T., Gallo, L., Keil, R., & Ueda, Y. 2004, PASJ, 56, L9, doi: 10.1093/pasj/56.3.L9
  * Tanaka et al. (2003) Tanaka, Y., Ueda, Y., & Boller, T. 2003, MNRAS, 338, L1, doi: 10.1046/j.1365-8711.2003.06110.x
  * Tanaka et al. (1995) Tanaka, Y., Nandra, K., Fabian, A. C., et al. 1995, Nature, 375, 659, doi: 10.1038/375659a0
  * Urry & Padovani (1995) Urry, C. M., & Padovani, P. 1995, PASP, 107, 803, doi: 10.1086/133630
  * Urry (2003) Urry, M. 2003, in Astronomical Society of the Pacific Conference Series, Vol. 290, Active Galactic Nuclei: From Central Engine to Host Galaxy, ed. S. Collin, F. Combes, & I. Shlosman, 3, doi: 10.48550/arXiv.astro-ph/0301309
  * Varglund et al. (2022) Varglund, I., Järvelä, E., Lähteenmäki, A., et al. 2022, A&A, 668, A91, doi: 10.1051/0004-6361/202244465
  * Virtanen et al. (2020) Virtanen, P., Gommers, R., Oliphant, T. E., et al. 2020, Nature Methods, 17, 261, doi: 10.1038/s41592-019-0686-2
  * Waddell & Gallo (2020) Waddell, S. G. H., & Gallo, L. C. 2020, MNRAS, 498, 5207, doi: 10.1093/mnras/staa2783
  * Waddell et al. (2019) Waddell, S. G. H., Gallo, L. C., Gonzalez, A. G., Tripathi, S., & Zoghbi, A. 2019, MNRAS, 489, 5398, doi: 10.1093/mnras/stz2518
  * Wilkins & Fabian (2012) Wilkins, D. R., & Fabian, A. C. 2012, MNRAS, 424, 1284, doi: 10.1111/j.1365-2966.2012.21308.x
  * Wilkins & Gallo (2015) Wilkins, D. R., & Gallo, L. C. 2015, MNRAS, 449, 129, doi: 10.1093/mnras/stv162
  * Wilkins et al. (2022) Wilkins, D. R., Gallo, L. C., Costantini, E., Brandt, W. N., & Blandford, R. D. 2022, MNRAS, 512, 761, doi: 10.1093/mnras/stac416
  * Wilkins et al. (2014) Wilkins, D. R., Kara, E., Fabian, A. C., & Gallo, L. C. 2014, Monthly Notices of the Royal Astronomical Society, 443, 2746, doi: 10.1093/mnras/stu1273
  * Willingale et al. (2013) Willingale, R., Starling, R. L. C., Beardmore, A. P., Tanvir, N. R., & O’Brien, P. T. 2013, MNRAS, 431, 394, doi: 10.1093/mnras/stt175
  * Wilms et al. (2000) Wilms, J., Allen, A., & McCray, R. 2000, ApJ, 542, 914, doi: 10.1086/317016
  * Xu et al. (2002) Xu, H., Kahn, S. M., Peterson, J. R., et al. 2002, ApJ, 579, 600, doi: 10.1086/342828
  * Zhang & Wu (2002) Zhang, T.-Z., & Wu, X.-B. 2002, Chinese J. Astron. Astrophys., 2, 487, doi: 10.1088/1009-9271/2/6/487
  * Zoghbi et al. (2010) Zoghbi, A., Fabian, A. C., Uttley, P., et al. 2010, MNRAS, 401, 2419, doi: 10.1111/j.1365-2966.2009.15816.x

##  Appendix A Swift spectral Data

Figure 16: Swift spectrum for observations detailed in Table 2. The data has
been binned into 10 bins to match the first principal component seen in Figure
6. The gray data represent the background for each Swift observation.

##  Appendix B Simulated PCA Principal Component 1

Figure 17: The first principal component for the sixteen simulated absorbers
described in Section 3.5. The absorbers are grouped by column density, with
the top panel showing those with ${N_{\rm H}}=22\times 10^{22}$
${\rm\thinspace cm}^{-2}\,$, the second panel showing those with ${N_{\rm
H}}=25\times 10^{22}$ ${\rm\thinspace cm}^{-2}\,$, the third panel showing
those with ${N_{\rm H}}=30\times 10^{22}$ ${\rm\thinspace cm}^{-2}\,$, and the
forth panel showing those with ${N_{\rm H}}=35\times 10^{22}$ ${\rm\thinspace
cm}^{-2}\,$. Each panel has absorbers with covering fractions of
$CF=95,\,98,\,99,$ and $99.5\%$. All simulated absorbers produced a first
principal component that was inconsistent with the first principal component
of the PN spectra.

##  Appendix C Simulated PN data

Figure 18: The observed PN spectra (green diamonds) compared to a simulated PN
spectra based on the best fit low-state model with no absorption. See section
4.3 for details.

##  Appendix D MCMC corner plots

Figure 19: The corner plots for the MCMC best fit for the soft band
components. Note that nh_soft is the column density of the absorber applied to
the apec component. Figure 20: The corner plots for the MCMC best fit for the
hard band components.Parameters that lack the subscript L or H denote values
that were linked between epochs, while parameters with the subscript L
indicate the low state value and parameters with subscript H indicate the high
state value. Note that nh_hard is the column density of the absorber applied
to the continuum components. Figure 21: The corner plots for the MCMC best fit
for the calibration constants. parameters with the subscript L indicate the
low state calibration constants while the parameter with the subscript H
indicates the high state calibration constant.