Measurement of the production cross-section of a single top-quark in
association with a $Z$ boson at 13 TeV with the ATLAS detector

Irina Cioară111Speaker, on behalf of the ATLAS Collaboration

Physikalisches Institut
Rheinische Friedrich-Wilhelms-Universität Bonn, GERMANY

> The production of a top quark in association with a $Z$ boson is studied in
> the trilepton channel. The data collected by the ATLAS experiment at the LHC
> in 2015 and 2016 at a centre-of-mass energy of $\sqrt{s}=13\,\text{TeV}$ are
> used, corresponding to an integrated luminosity of $36.1\,\text{fb}^{-1}$.
> Events containing three identified leptons (electron and/or muon) and two
> jets, one of which is identified as a $b$-quark jet are selected. The major
> backgrounds come from diboson, $t\bar{t}$ and $Z\text{\,+\,jets}$
> production. A neural network is used to improve the background rejection and
> extract the signal. The resulting significance of the signal is $4.2\sigma$
> in the data and the expected significance is $5.4\sigma$. The measured
> cross-section is $600\pm 170\text{(stat)}\pm 140\text{(syst)}\,\text{fb}$.

> PRESENTED AT
>
>
>
>
> $10^{th}$ International Workshop on Top Quark Physics
> Braga, Portugal, September 17–22, 2017

##  1 Introduction

Since its discovery in 1995, the top quark has been studied extensively using
hadron collision data. With the latest increase in energy and instantaneous
luminosity, the Large Hadron Collider (LHC) has made it possible to study top-
quark processes that have a very low production cross-section. One of them is
the associated production of a top quark and a $Z$ boson ($tZq$ production)
[1]. This occurs through the radiation of a $Z$ boson from any of the quark
lines of $t$-channel, single top-quark production or through a three-boson
coupling. Example Feynman diagrams of the lowest-order amplitudes are shown in
Figure 1. Hence, this channel is sensitive to both the coupling of the top to
the $Z$, as well as the $WWZ$ coupling. This document presents a search for
such rare events [2], performed using 2015-2016 collision data collected by
the ATLAS detector [3] at a centre-of-mass energy of
$13\text{\,}\mathrm{TeV}$. The predicted production cross-section for $tZq$
events at next-to-leading order (NLO) in QCD is
$\sigma_{tZq}^{\text{pred.}}=800^{+6.1\%}_{-7.4\%}\text{ fb}$.

|
---|---
Figure 1: Example Feynman diagrams of the lowest-order amplitudes for the
$tZq$ process. In the four-flavour scheme, the $b$-quark originates from gluon
splitting [2].

##  2 Analysis strategy

The final state that offers the best potential for discovery (and highest
signal to background ratio) is the one in which both the $Z$ boson and the $W$
boson coming from the top quark decay leptonically. This results in three
leptons, two jets, one of which has to be identified as coming from a $b$
quark ($b$-tagged), and missing transverse momentum. Based on that, cuts are
applied in order to define a signal region (SR) enriched in $tZq$ events. The
number of signal events is estimated using a Monte Carlo (MC) simulated sample
that is generated at leading order (LO) in QCD that is then normalised to the
NLO predicted cross-section.

The backgrounds coming from other sources that can result in similar final
states are estimated either from MC samples or using data-driven methods. The
modelling of these backgrounds is checked in dedicated validation regions
(VR).

Multivariate analysis techniques are used to construct a single discriminant
that separates signal from background. This distribution is then fitted using
a binned likelihood fit in order to extract the measured $tZq$ cross-section.

###  2.1 Event Selection and background estimation

The cuts applied in order to select events that match the $tZq$ signature
target the trileptonic final state described above and are summarised in Table
1. Out of the three isolated leptons required, two of them must form an
opposite sign, same flavour (OSSF) pair with a mass within a
$10\text{\,}\mathrm{GeV}$ window around the $Z$ boson mass. One of the two
selected jets must pass $b$-tagging criteria and be reconstructed in the
central region of the detector ($|\eta|<2.5$), while the remaining light jet,
that is expected to go mostly in the forward direction, can have $|\eta|$ up
to $4.5\text{\,}$.

Common selections
---
Exactly 3 leptons with $|\eta|<2.5$ and $p_{T}>$15\text{\,}\mathrm{GeV}$$
$p_{T}(\ell_{1})>$28\text{\,}\mathrm{GeV}$$,
$p_{T}(\ell_{2})>$25\text{\,}\mathrm{GeV}$$,
$p_{T}(\ell_{3})>$15\text{\,}\mathrm{GeV}$$
$p_{T}(\text{jet})>$30\text{\,}\mathrm{GeV}$$
$m_{T}(\ell_{W},\nu)>$20\text{\,}\mathrm{GeV}$$
SR | Diboson VR / CR |  $t\bar{t}$ VR
$\geq$ 1 OSSF pair |  $\geq$ 1 OSOF pair |  $\geq$ 1 OSOF pair
$|m_{ll}-m_{Z}|<$10\text{\,}\mathrm{GeV}$$ |  $|m_{ll}-m_{Z}|<$ $10\text{\,}\mathrm{GeV}$ | $|m_{ll}-m_{Z}|>$10\text{\,}\mathrm{GeV}$$
2 jets, $|\eta|<$ 4.5 | 1 jet, $|\eta|<$ 4.5 | 2 jets, $|\eta|<$ 4.5
1 $b$jet, $|\eta|<$ 2.5 | — | 1 $b$-jet, $|\eta|<$ 2.5
— | VR/CR: $m_{T}(\ell_{W},\nu)>20/$60\text{\,}\mathrm{GeV}$$ | —
Table 1: Overview of the selection applied in the signal, validation and
diboson control region.

There are two different types of background sources for this analysis:
processes resulting in final states with three real leptons, such as diboson
production (mostly consisting of $WZ$ events), associated top-quark pair
production with additional bosons ($ttV+ttH$) and $tWZ$, or events in which
one of the leptons is non-prompt or is a jet misidentified as a lepton. For
the first category (with three real leptons), the background contributions are
estimated from MC simulations and normalised by their predicted SM cross-
sections. Additionally, the diboson normalisation is corrected by a scale
factor derived in a dedicated control region (Diboson CR) that is selected as
presented in Table 1.

The main sources of events with a non-prompt lepton are the top-quark pair
production ($t\bar{t}$) and $Z$ boson production with additional jets. For
estimating the correct number of $t\bar{t}$ events, the MC simulation is
corrected using a data-MC scale factor derived in a dedicated control region.
The $t\bar{t}$ CR is defined using the same cuts as the SR but requiring only
one opposite sign, opposite flavour lepton pair and not allowing any OSSF
lepton pair, ensuring that there is no contamination from $Z$+jets events. The
derived scale factor is $1.21\pm 0.51$.

For estimating the number of $Z$+jets events, the fake factor method is used.
This is a data-driven technique that relies on calculating fake factors in a
region enriched in events containing non-prompt leptons. This region has the
same definition as the signal region but $m_{T}(W)$ is required to be
$20\text{\,}\mathrm{G}\mathrm{e}\mathrm{V}$. The fake factors are defined as
the ratio between events that have all three reconstructed leptons passing
tight isolation criteria and events with two tight leptons and one passing
looser isolation cuts. These factors, that are derived with respect to the
$p_{T}$ of the lepton associated to the $W$ boson, are then applied to events
that pass the SR selection but that have one of the leptons passing looser
identification criteria. This is done separately for non-prompt electrons and
muons and results in a total $Z$+jets contribution of 37 events, with a $40\%$
assigned uncertainty.

The modelling of all backgrounds is checked by looking at kinematic variables
in validation regions enriched in diboson and $t\bar{t}$ events that are
defined using the cuts included in 1. Good agreement between the data and MC
is observed in all distributions.

###  2.2 Neural network training and signal extraction

In order to separate between signal and background, an artificial neural
network (NN) is used to combine the separation power of several observables
into a single discriminant. The NN is trained in the SR to separate signal
against all backgrounds except for $t\bar{t}$ production (that is discarded
due to low statistics in the MC sample, after applying the SR selection). The
first variables selected by the network are the $|\eta|$ and $p_{T}$ of the
untagged jet.

Figure 2: Post-fit NN output distribution in the SR. Signal and backgrounds
are normalised to the expected number of events after the fit. The uncertainty
band includes both the statistical and systematic uncertainties as obtained by
the fit [2].

The $tZq$ cross-section is extracted by performing a binned likelihood fit of
the NN output distribution in the SR. Several sources of systematic
uncertainties are taken into account and included as additional nuissance
parameters in the fit. The dominant systematic uncertainty is related to the
amount of additional radiation in the signal sample. This is evaluated by
considering additional samples in which the hard-scatter scales and the scales
in the parton shower are simultaneously varied. The result is also affected by
large statistical uncertainty (amounting to $28\%$), while the total
systematic error is $23\%$.

In total, $141$ events are observed after applying the SR selection. The total
pre-fit number of predicted events for all backgrounds and signal is $162$,
with $35$ coming from $tZq$ production. The post-fit number of signal events
is $26$. Figure 2 shows the NN discriminant after normalising the signal and
background to the fitted number of expected events. Very good agreement
between data and MC is observed.

##  3 Results

The analysis investigating the production of a single top-quark in association
with a $Z$ boson was performed using $36.1\text{\,}{\mathrm{fb}}^{-1}$ of
proton-proton collision data at a centre-of-mass energy of
$13\text{\,}\mathrm{TeV}$. The measured cross-section: $\sigma_{tZq}=600\pm
170\text{(stat.)}\pm 140\text{(syst.) fb}$ is in good agreement with the NLO
SM prediction. Evidence for the signal is found with a 4.2 (5.4) $\sigma$
observed (expected) significance.

## References

  * [1] John Campbell, R. Ellis and Raoul Röntsch  “Single top production in association with a Z boson at the LHC”  In _Phys. Rev. D_ 87, 2013, pp. 114006  DOI: 10.1103/PhysRevD.87.114006
  * [2] ATLAS Collaboration  “Measurement of the production cross-section of a single top quark in association with a $Z$ boson in proton–proton collisions at 13 TeV with the ATLAS detector”, 2017  arXiv:1710.03659 [hep-ex]
  * [3] ATLAS Collaboration  “The ATLAS Experiment at the CERN Large Hadron Collider”  In _JINST_ 3, 2008, pp. S08003  DOI: 10.1088/1748-0221/3/08/S08003


# A Fully Dynamic Algorithm for k-Regret Minimizing Sets
††thanks: 1This research was mostly done when Yanhao Wang worked at National
University of Singapore (NUS).

Yanhao Wang1, Yuchen Li2,5, Raymond Chi-Wing Wong3, Kian-Lee Tan4  1University
of Helsinki 2Singapore Management University 3The Hong Kong University of
Science and Technology
4National University of Singapore 5Alibaba-Zhejiang University Joint Research
Institute of Frontier Technologies
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Selecting a small set of representatives from a large database is important in
many applications such as multi-criteria decision making, web search, and
recommendation. The $k$-regret minimizing set ($k$-RMS) problem was recently
proposed for representative tuple discovery. Specifically, for a large
database $P$ of tuples with multiple numerical attributes, the $k$-RMS problem
returns a size-$r$ subset $Q$ of $P$ such that, for any possible ranking
function, the score of the top-ranked tuple in $Q$ is not much worse than the
score of the $k$th-ranked tuple in $P$. Although the $k$-RMS problem has been
extensively studied in the literature, existing methods are designed for the
static setting and cannot maintain the result efficiently when the database is
updated. To address this issue, we propose the first fully-dynamic algorithm
for the $k$-RMS problem that can efficiently provide the up-to-date result
w.r.t. any tuple insertion and deletion in the database with a provable
guarantee. Experimental results on several real-world and synthetic datasets
demonstrate that our algorithm runs up to four orders of magnitude faster than
existing $k$-RMS algorithms while providing results of nearly equal quality.

###### Index Terms:

regret minimizing set; dynamic algorithm; set cover; top-k query; skyline

##  I Introduction

In many real-world applications such as multi-criteria decision making [1],
web search [2], recommendation [3, 4], and data description [5], it is crucial
to find a succinct representative subset from a large database to meet the
requirements of various users. For example, when a user queries for a hotel on
a website (e.g., booking.com and expedia.com), she/he will receive thousands
of available options as results. The website would like to display the best
choices in the first few pages from which almost all users could find what
they are most interested in. A common method is to rank all results using a
utility function that denotes a user’s preference on different attributes
(e.g.,  _price_ , _rating_ , and _distance to destination_ for hotels) and
only present the top-$k$ tuples with the highest scores according to this
function to the user. However, due to the wide diversity of user preferences,
it is infeasible to represent the preferences of all users by any single
utility function. Therefore, to select a set of highly representative tuples,
it is necessary to take all (possible) user preferences into account.

A well-established approach to finding such representatives from databases is
the _skyline_ operator [6] based on the concept of _domination_ : a tuple $p$
dominates a tuple $q$ iff $p$ is as good as $q$ on all attributes and strictly
better than $q$ on at least one attribute. For a given database, a skyline
query returns its _Pareto-optimal_ subset which consists of all tuples that
are not dominated by any tuple. It is guaranteed that any user can find
her/his best choice from the skyline because the top-ranked result according
to any monotone function must not be dominated. Unfortunately, although
skyline queries are effective for representing low-dimensional databases,
their result sizes cannot be controlled and increase rapidly as the
dimensionality (i.e., number of attributes in a tuple) grows, particularly so
for databases with anti-correlated attributes.

Recently, the $k$-regret minimizing set ($k$-RMS) problem [1, 7, 8, 9, 10, 11,
12, 13] was proposed to alleviate the deficiency of skyline queries.
Specifically, given a database $P$ of tuples with $d$ numeric attributes, the
$k$-RMS problem aims to find a subset $Q\subseteq P$ such that, for any
possible utility function, the top-$1$ tuple in $Q$ can approximate the
top-$k$ tuples in $P$ within a small error. Here, the _maximum $k$-regret
ratio_ [8] ($\mathtt{mrr}_{k}$) is used to measure how well $Q$ can represent
$P$. For a utility function $f$, the $k$-regret ratio ($\mathtt{rr}_{k}$) of
$Q$ over $P$ is defined to be $0$ if the top-$1$ tuple in $Q$ is among the
top-$k$ tuples in $P$ w.r.t. $f$, or otherwise, to be one minus the ratio
between the score of the top-$1$ tuple in $Q$ and the score of the $k$th-
ranked tuple in $P$ w.r.t. $f$. Then, the _maximum $k$-regret ratio_
($\mathtt{mrr}_{k}$) is defined by the maximum of $\mathtt{rr}_{k}$ over a
class of (possibly infinite) utility functions. Given a positive integer $r$,
a $k$-RMS on a database $P$ returns a subset $Q\subseteq P$ of size $r$ to
minimize $\mathtt{mrr}_{k}$. As an illustrative example, the website could run
a $k$-RMS on all available hotels to pick a set of $r$ candidates from which
all users can find at least one close to her/his top-$k$ choices.

The $k$-RMS problem has been extensively studied recently. Theoretically, it
is NP-hard [8, 9, 10] on any database with $d\geq 3$. In general, we
categorize existing $k$-RMS algorithms into three types. The first type is
dynamic programming algorithms [11, 8, 10] for $k$-RMS on two-dimensional
data. Although they can provide optimal solutions when $d=2$, they are not
suitable for higher dimensions due to the NP-hardness of $k$-RMS. The second
type is the greedy heuristic [1, 7, 8], which always adds a tuple that
maximally reduces $\mathtt{mrr}_{k}$ at each iteration. Although these
algorithms can provide high-quality results empirically, they have no
theoretical guarantee and suffer from low efficiency on high-dimensional data.
The third type is to transform $k$-RMS into another problem such as
$\varepsilon$-kernel [13, 12, 9, 10], discretized matrix min-max [11], hitting
set [12, 9], and $k$-medoid clustering [14], and then to utilize existing
solutions of the transformed problem for $k$-RMS computation. Although these
algorithms are more efficient than greedy heuristics while having theoretical
bounds, they are designed for the static setting and cannot process database
updates efficiently. Typically, most of them precompute the skyline as an
input to compute the result of $k$-RMS. Once a tuple insertion or deletion
triggers any change in the skyline, they are unable to maintain the result
without re-running from scratch. Hence, existing $k$-RMS algorithms become
very inefficient in highly dynamic environments where tuples in the databases
are frequently inserted and deleted. However, dynamic databases are very
common in real-world scenarios, especially for online services. For example,
in a hotel booking system, the _prices_ and _availabilities_ of rooms are
frequently changed over time. As another example, in an IoT network, a large
number of sensors may often connect or disconnect with the server. Moreover,
sensors also update their statistics regularly. Therefore, it is essential to
address the problem of maintaining an up-to-date result for $k$-RMS when the
database is frequently updated.

In this paper, we propose the first fully-dynamic $k$-RMS algorithm that can
efficiently maintain the result of $k$-RMS w.r.t. any tuple insertion and
deletion in the database with both theoretical guarantee and good empirical
performance. Our main contributions are summarized as follows.

  * •

We formally define the notion of _maximum $k$-regret ratio_ and the _$k$
-regret minimizing set_ ($k$-RMS) problem in a fully-dynamic setting. (Section
II)

  * •

We propose the first fully-dynamic algorithm called FD-RMS to maintain the
$k$-RMS result over tuple insertions and deletions in a database. Our basic
idea is to transform _fully-dynamic $k$-RMS_ into a _dynamic set cover_
problem. Specifically, FD-RMS computes the (approximate) top-$k$ tuples for a
set of randomly sampled utility functions and builds a set system based on the
top-$k$ results. Then, the $k$-RMS result can be retrieved from an approximate
solution for _set cover_ on the set system. Furthermore, we devise a novel
algorithm for dynamic set cover by introducing the notion of _stable solution_
, which is used to efficiently update the $k$-RMS result whenever an insertion
or deletion triggers some changes in top-$k$ results as well as the set
system. We also provide detailed theoretical analyses of FD-RMS. (Section III)

  * •

We conduct extensive experiments on several real-world and synthetic datasets
to evaluate the performance of FD-RMS. The results show that FD-RMS achieves
up to four orders of magnitude speedup over existing $k$-RMS algorithms while
providing results of nearly equal quality in a fully dynamic setting. (Section
IV)

##  II Preliminaries

In this section, we formally define the problem we study in this paper. We
first introduce the notion of maximum $k$-regret ratio. Then, we formulate the
$k$-regret minimizing set ($k$-RMS) problem in a fully dynamic setting.
Finally, we present the challenges of solving fully-dynamic $k$-RMS.

Figure 1: A two-dimensional database of 8 tuples.

###  II-A Maximum K-Regret Ratio

Let us consider a database $P$ where each tuple $p\in P$ has $d$ nonnegative
numerical attributes $p[1],\ldots,p[d]$ and is represented as a point in the
nonnegative orthant $\mathbb{R}_{+}^{d}$. A user’s preference is denoted by a
utility function $f:\mathbb{R}_{+}^{d}\rightarrow\mathbb{R}^{+}$ that assigns
a positive score $f(p)$ to each tuple $p$. Following [1, 7, 8, 11, 13], we
restrict the class of utility functions to _linear functions_. A function $f$
is linear if and only if there exists a $d$-dimensional vector
$u=(u[1],\ldots,u[d])\in\mathbb{R}_{+}^{d}$ such that $f(p)=\langle
u,p\rangle=\sum_{i=1}^{d}u[i]\cdot p[i]$ for any $p\in\mathbb{R}_{+}^{d}$.
W.l.o.g., we assume the range of values on each dimension is scaled to $[0,1]$
and any utility vector is normalized to be a unit111The normalization does not
affect our results because the maximum $k$-regret ratio is _scale-invariant_
[1]., i.e., $\|u\|=1$. Intuitively, the class of linear functions corresponds
to the nonnegative orthant of $d$-dimensional unit sphere
$\mathbb{U}=\\{u\in\mathbb{R}_{+}^{d}\,:\,\lVert u\rVert=1\\}$.

We use $\varphi_{j}(u,P)$ to denote the tuple $p\in P$ with the $j$th-largest
score w.r.t. vector $u$ and $\omega_{j}(u,P)$ to denote its score. Note that
multiple tuples may have the same score w.r.t. $u$ and any consistent rule can
be adopted to break ties. For brevity, we drop the subscript $j$ from the
above notations when $j=1$, i.e., $\varphi(u,P)=\arg\max_{p\in P}\langle
u,p\rangle$ and $\omega(u,P)=\max_{p\in P}\langle u,p\rangle$. The top-$k$
tuples in $P$ w.r.t. $u$ is represented as
$\Phi_{k}(u,P)=\\{\varphi_{j}(u,P):1\leq j\leq k\\}$. Given a real number
$\varepsilon\in(0,1)$, the $\varepsilon$-approximate top-$k$ tuples in $P$
w.r.t. $u$ is denoted as $\Phi_{k,\varepsilon}(u,P)=\\{p\in P\,:\,\langle
u,p\rangle\geq(1-\varepsilon)\cdot\omega_{k}(u,P)\\}$, i.e., the set of tuples
whose scores are at least $(1-\varepsilon)\cdot\omega_{k}(u,P)$.

For a subset $Q\subseteq P$ and an integer $k\geq 1$, we define the _$k$
-regret ratio_ of $Q$ over $P$ for a utility vector $u$ by
$\mathtt{rr}_{k}(u,Q)=\max\big{(}0,1-\frac{\omega(u,Q)}{\omega_{k}(u,P)}\big{)}$,
i.e., the relative loss of replacing the $k$th-ranked tuple in $P$ by the top-
ranked tuple in $Q$. Since it is required to consider the preferences of all
possible users, our goal is to find a subset whose $k$-regret ratio is small
for an arbitrary utility vector. Therefore, we define the _maximum $k$-regret
ratio_ of $Q$ over $P$ by
$\mathtt{mrr}_{k}(Q)=\max_{u\in\mathbb{U}}\mathtt{rr}_{k}(u,Q)$. Intuitively,
$\mathtt{mrr}_{k}(Q)$ measures how well the top-ranked tuple of $Q$
approximates the $k$th-ranked tuple of $P$ in the worst case. For a real
number $\varepsilon\in(0,1)$, $Q$ is said to be a $(k,\varepsilon)$-regret set
of $P$ iff $\mathtt{mrr}_{k}(Q)\leq\varepsilon$, or equivalently,
$\varphi(u,Q)\in\Phi_{k,\varepsilon}(u,P)$ for any $u\in\mathbb{U}$. By
definition, it holds that $\mathtt{mrr}_{k}(Q)\in[0,1]$.

######  Example 1.

Fig. 1 illustrates a database $P$ in $\mathbb{R}^{2}_{+}$ with $8$ tuples
$\\{p_{1},\ldots,p_{8}\\}$. For utility vectors $u_{1}=(0.42,0.91)$ and
$u_{2}=(0.91,0.42)$, their top-$2$ results are
$\Phi_{2}(u_{1},P)=\\{p_{1},p_{2}\\}$ and
$\Phi_{2}(u_{2},P)=\\{p_{2},p_{4}\\}$, respectively. Given a subset
$Q_{1}=\\{p_{3},p_{4}\\}$ of $P$,
$\mathtt{rr}_{2}(u_{1},Q_{1})=1-\frac{0.749}{0.98}\approx 0.236$ as
$\omega(u_{1},Q_{1})=\langle u_{1},p_{3}\rangle=0.749$ and
$\omega_{2}(u_{1},P)=\langle u_{1},p_{2}\rangle=0.98$. Furthermore,
$\mathtt{mrr}_{2}(Q_{1})\approx 0.444$ because $\mathtt{rr}_{2}(u,Q_{1})$ is
the maximum when $u=(0.0,1.0)$ with
$\mathtt{rr}_{2}(u,Q_{1})=1-\frac{5}{9}\approx 0.444$. Finally,
$Q_{2}=\\{p_{1},p_{2},p_{4}\\}$ is a $(2,0)$-regret set of $P$ since
$\mathtt{mrr}_{2}(Q_{2})=0$.

###  II-B K-Regret Minimizing Set

Based on the notion of _maximum $k$-regret ratio_, we can formally define the
$k$-_regret minimizing set_ ($k$-RMS) problem in the following.

######  Definition 1 ($k$-Regret Minimizing Set).

Given a database $P\subset\mathbb{R}_{+}^{d}$ and a size constraint
$r\in\mathbb{Z}^{+}$ ($r\geq d$), the $k$-regret minimizing set ($k$-RMS)
problem returns a subset $Q^{*}\subseteq P$ of at most $r$ tuples with the
smallest _maximum $k$-regret ratio_, i.e., $Q^{*}=\arg\min_{Q\subseteq
P\,:\,|Q|\leq r}\mathtt{mrr}_{k}(Q)$.

For any given $k$ and $r$, we denote the $k$-RMS problem by
$\mathtt{RMS}(k,r)$ and the _maximum $k$-regret ratio_ of the optimal result
$Q^{*}$ for $\mathtt{RMS}(k,r)$ by $\varepsilon^{*}_{k,r}$. In particular, the
$r$-regret query studied in [7, 11, 13, 1] is a special case of our $k$-RMS
problem when $k=1$, i.e., $1$-RMS.

######  Example 2.

Let us continue with the example in Fig. 1. For a query $\mathtt{RMS}(2,2)$ on
$P$, we have $Q^{*}=\\{p_{1},p_{4}\\}$ with
$\varepsilon^{*}_{2,2}=\mathtt{mrr}_{2}(Q^{*})\approx 0.05$ because
$\\{p_{1},p_{4}\\}$ has the smallest maximum $2$-regret ratio among all
size-$2$ subsets of $P$.

In this paper, we focus on the fully-dynamic $k$-RMS problem. We consider an
initial database $P_{0}$ and a (possibly countably infinite) sequence of
operations $\Delta=\langle\Delta_{1},\Delta_{2},\ldots\rangle$. At each
timestamp $t$ ($t\in\mathbb{Z}^{+}$), the database is updated from $P_{t-1}$
to $P_{t}$ by performing an operation $\Delta_{t}$ of one of the following two
types:

  * •

Tuple insertion $\Delta_{t}=\langle p,+\rangle$: add a new tuple $p$ to
$P_{t-1}$, i.e., $P_{t}\leftarrow P_{t-1}\cup\\{p\\}$;

  * •

Tuple deletion $\Delta_{t}=\langle p,-\rangle$: delete an existing tuple $p$
from $P_{t-1}$, i.e., $P_{t}\leftarrow P_{t-1}\setminus\\{p\\}$.

Note that the update of a tuple can be processed by a deletion followed by an
insertion, and thus is not discussed separately in this paper. Given an
initial database $P_{0}$, a sequence of operations $\Delta$, and a query
$\mathtt{RMS}(k,r)$, we aim to keep track of the result $Q^{*}_{t}$ for
$\mathtt{RMS}(k,r)$ on $P_{t}$ at any time $t$.

Fully-dynamic $k$-RMS faces two challenges. First, the $k$-RMS problem is NP-
hard [10, 8, 9] for any $d\geq 3$. Thus, the optimal solution of $k$-RMS is
intractable for any database with three or more attributes unless P=NP in both
static and dynamic settings. Hence, we will focus on maintaining an
approximate result of $k$-RMS in this paper. Second, existing $k$-RMS
algorithms can only work in the static setting. They must recompute the result
from scratch once an operation triggers any update in the skyline (Note that
since the result of $k$-RMS is a subset of the skyline [1, 8], it remains
unchanged for any operation on non-skyline tuples). However, frequent
recomputation leads to significant overhead and causes low efficiency on
highly dynamic databases. Therefore, we will propose a novel method for fully-
dynamic $k$-RMS that can maintain a high-quality result for
$\mathtt{RMS}(k,r)$ on a database w.r.t. any tuple insertion and deletion
efficiently.

##  III The FD-RMS Algorithm

Figure 2: An illustration of FD-RMS

In this section, we present our FD-RMS algorithm for $k$-RMS in a fully
dynamic setting. The general framework of FD-RMS is illustrated in Fig. 2. The
basic idea is to transform _fully-dynamic $k$-RMS_ to a _dynamic set cover_
problem. Let us consider how to compute the result of $\mathtt{RMS}(k,r)$ on
database $P_{t}$. First of all, we draw a set of $m$ random utility vectors
$\\{u_{1},\ldots,u_{m}\\}$ from $\mathbb{U}$ and maintain the
$\varepsilon$-approximate top-$k$ result of each $u_{i}$ ($i\in[1,m]$) on
$P_{t}$, i.e., $\Phi_{k,\varepsilon}(u_{i},P_{t})$. Note that $\varepsilon$
should be given as an input parameter of FD-RMS and we will discuss how to
specify its value at the end of Section III. Then, we construct a set system
$\Sigma=(\mathcal{U},\mathcal{S})$ based on the approximate top-$k$ results,
where the universe $\mathcal{U}=\\{u_{1},\ldots,u_{m}\\}$ and the collection
$\mathcal{S}$ consists of $n_{t}$ sets ($n_{t}=|P_{t}|$) each of which
corresponds to one tuple in $P_{t}$. Specifically, for each tuple $p\in
P_{t}$, we define $S(p)$ as a set of utility vectors for which $p$ is an
$\varepsilon$-approximate top-$k$ result on $P_{t}$. Or formally,
$S(p)=\\{u\in\mathcal{U}:p\in\Phi_{k,\varepsilon}(u,P_{t})\\}$ and
$\mathcal{S}=\\{S(p):p\in P_{t}\\}$. After that, we compute a result $Q_{t}$
for $\mathtt{RMS}(k,r)$ on $P_{t}$ using an (approximate) solution for set
cover on $\Sigma$. Let $\mathcal{C}\subseteq\mathcal{S}$ be a set-cover
solution of $\Sigma$, i.e., $\bigcup_{S(p)\in\mathcal{C}}S(p)=\mathcal{U}$. We
use the set $Q_{t}$ of tuples corresponding to $\mathcal{C}$, i.e.,
$Q_{t}=\\{p\in P_{t}:S(p)\in\mathcal{C}\\}$, as the result of
$\mathtt{RMS}(k,r)$ on $P_{t}$. Given the above framework, there are still two
challenges of updating the result of $k$-RMS in a fully dynamic setting.
Firstly, because the size of $Q_{t}$ is restricted to $r$, it is necessary to
always keep an appropriate value of $m$ over time so that $|\mathcal{C}|\leq
r$. Secondly, the updates in approximate top-$k$ results triggered by tuple
insertions and deletions in the database lead to the changes in the set
collection $\mathcal{S}$. Therefore, it is essential to maintain the set-cover
solution $\mathcal{C}$ over time for the changes in $\mathcal{S}$. In fact,
both challenges can be treated as a _dynamic set cover_ problem that keeps a
set-cover solution w.r.t. changes in both $\mathcal{U}$ and $\mathcal{S}$.
Therefore, we will first introduce the background on _dynamic set cover_ in
Section III-A. After that, we will elaborate on how FD-RMS processes $k$-RMS
in a fully dynamic setting using the _dynamic set cover_ algorithm in Section
III-B.

###  III-A Background: Dynamic Set Cover

Given a set system $\Sigma=(\mathcal{U},\mathcal{S})$, the _set cover_ problem
asks for the smallest subset $\mathcal{C}^{*}$ of $\mathcal{S}$ whose union
equals to the universe $\mathcal{U}$. It is one of Karp’s 21 NP-complete
problems [15], and cannot be approximated to $(1-o(1))\cdot\ln{m}$
($m=|\mathcal{U}|$) unless P=NP [16]. A common method to find an approximate
set-cover solution is the greedy algorithm. Starting from
$\mathcal{C}=\varnothing$, it always adds the set that contains the largest
number of uncovered elements in $\mathcal{U}$ to $\mathcal{C}$ at each
iteration until $\bigcup_{S\in\mathcal{C}}S=\mathcal{U}$. Theoretically, the
solution $\mathcal{C}$ achieves an approximation ratio of $(1+\ln{m})$, i.e.,
$|\mathcal{C}|\leq(1+\ln{m})\cdot|\mathcal{C}^{*}|$. But obviously, the greedy
algorithm cannot dynamically update the set-cover solution when the set system
$\Sigma$ is changed.

Recently, there are some theoretical advances on covering and relevant
problems (e.g., vertex cover, maximum matching, set cover, and maximal
independent set) in dynamic settings [17, 18, 19, 20]. Although these
theoretical results have opened up new ways to design dynamic set cover
algorithms, they cannot be directly applied to the update procedure of FD-RMS
because of two limitations. First, existing dynamic algorithms for set cover
[19, 18] can only handle the update in the universe $\mathcal{U}$ but assume
that the set collection $\mathcal{S}$ is not changed. But in our scenario, the
changes in top-$k$ results lead to the update of $\mathcal{S}$. Second, due to
the extremely large constants introduced in their analyses, the solutions
returned may be far away from the optima in practice.

Therefore, we devise a more practical approach to dynamic set cover that
supports any update in both $\mathcal{U}$ and $\mathcal{S}$. Our basic idea is
to introduce the notion of _stability_ to a set-cover solution. Then, we prove
that any stable solution is $O(\log{m})$-approximate ($m=|\mathcal{U}|$) for
set cover. Based on this result, we are able to design an algorithm to
maintain a set-cover solution w.r.t. any change in $\Sigma$ by guaranteeing
its _stability_.

We first formalize the concept of _stability_ of a set-cover solution. Let
$\mathcal{C}\subseteq\mathcal{S}$ be a set-cover solution on
$\Sigma=(\mathcal{U},\mathcal{S})$. We define an assignment $\phi$ from each
element $u\in\mathcal{U}$ to a _unique_ set $S\in\mathcal{C}$ that contains
$u$ (or formally, $\phi:\mathcal{U}\rightarrow\mathcal{C}$). For each set
$S\in\mathcal{C}$, its cover set $\mathtt{cov}(S)$ is defined as the set of
elements assigned to $S$, i.e.,
$\mathtt{cov}(S)=\\{u\in\mathcal{U}\,:\,\phi(u)=S\\}$. By definition, the
cover sets of different sets in $\mathcal{C}$ are _mutually disjoint_ from
each other. Then, we can organize the sets in $\mathcal{C}$ into hierarchies
according to the numbers of elements covered by them. Specifically, we put a
set $S\in\mathcal{C}$ in a higher level if it covers more elements and vice
versa. We associate each level $\mathcal{L}_{j}$ ($j\in\mathbb{N}$) with a
range of cover number222Here, the base $2$ may be replaced by any constant
greater than 1. $[2^{j},2^{j+1})$. Each set $S\in\mathcal{C}$ is assigned to a
level $\mathcal{L}_{j}$ if $2^{j}\leq|\mathtt{cov}(S)|<2^{j+1}$. We use
$A_{j}$ to denote the set of elements assigned to any set in
$\mathcal{L}_{j}$, i.e.,
$A_{j}=\\{u\in\mathcal{U}\,:\,\phi(u)\in\mathcal{L}_{j}\\}$. Moreover, the
notations $\mathcal{L}$ with subscripts, i.e., $\mathcal{L}_{>j}$ or
$\mathcal{L}_{\geq j}$ and $\mathcal{L}_{<j}$ or $\mathcal{L}_{\leq j}$,
represent the sets in all the levels above (excl. or incl.) and below
$\mathcal{L}_{j}$ (excl. or incl.), respectively. The same subscripts are also
used for $A$. Based on the above notions, we formally define the _stability_
of a set-cover solution in Definition 2 and give its approximation ratio in
Theorem 1.

######  Definition 2 (Stable Set-Cover Solution).

A solution $\mathcal{C}$ for _set cover_ on $\Sigma=(\mathcal{U},\mathcal{S})$
is stable if:

  1. 1.

For each set $S\in\mathcal{L}_{j}$, $2^{j}\leq|\mathtt{cov}(S)|<2^{j+1}$;

  2. 2.

For each level $\mathcal{L}_{j}$, there is no $S\in\mathcal{S}$ s.t. $|S\cap
A_{j}|\geq 2^{j+1}$.

######  Theorem 1.

If a set-cover solution $\mathcal{C}$ is stable, then it satisfies that
$|\mathcal{C}|\leq O(\log m)\cdot|\mathcal{C}^{*}|$.

###### Proof.

Let $\mathtt{OPT}=|\mathcal{C}^{*}|$, $\rho^{*}=\frac{m}{\mathtt{OPT}}$, and
$j^{*}$ be the level index such that $2^{j^{*}}\leq\rho^{*}<2^{j^{*}+1}$.
According to Condition (1) of Definition 2, we have $|\mathtt{cov}(S)|\geq
2^{j^{*}}$ for any $S\in\mathcal{L}_{\geq j^{*}}$. Thus, it holds that
$|\mathcal{L}_{\geq j^{*}}|\leq\frac{|A_{\geq
j^{*}}|}{2^{j^{*}}}\leq\frac{m}{2^{j^{*}}}\leq\frac{\rho^{*}}{2^{j^{*}}}\cdot\mathtt{OPT}\leq
2\cdot\mathtt{OPT}$. For some level $\mathcal{L}_{j}$ with $j<j^{*}$,
according to Condition (2) of Definition 2, any $S\in\mathcal{S}$ covers at
most $2^{j+1}$ elements in $A_{j}$. Hence, $\mathcal{S}^{*}$ needs at least
$\frac{|A_{j}|}{2^{j+1}}$ sets to cover $A_{j}$, i.e.,
$\mathtt{OPT}\geq\frac{|A_{j}|}{2^{j+1}}$. Since $|\mathtt{cov}(S)|\geq 2^{j}$
for each $S\in\mathcal{L}_{j}$, it holds that
$|\mathcal{L}_{j}|\leq\frac{|A_{j}|}{2^{j}}\leq 2\cdot\mathtt{OPT}$. As
$1\leq|\mathtt{cov}(S)|\leq m$, the range of level index is $[0,\log_{2}{m}]$.
Thus, the number of levels below $\mathcal{L}_{j^{*}}$ is at most
$\log_{2}{m}$. To sum up, we prove that

$\textstyle|\mathcal{C}|=|\mathcal{L}_{\geq
j^{*}}|+|\mathcal{L}_{<j^{*}}|\leq(2+2\log_{2}{m})\cdot\mathtt{OPT}$

and conclude the proof. ∎

Input : Set system $\Sigma$, set operation $\sigma$

Output : Stable set-cover solution $\mathcal{C}$

/* compute an initial solution $\mathcal{C}$ on $\Sigma$ */

1 $\mathcal{C}\leftarrow$ Greedy$(\Sigma)$;

/* update $\mathcal{C}$ for $\sigma=(u,S,\pm)$ or $(u,\mathcal{U},\pm)$ */

2 if  _$\sigma=(u,S,-)$ and $u\in\mathtt{cov}(S)$_ then

3 $\mathtt{cov}(S)\leftarrow\mathtt{cov}(S)\setminus\\{u\\}$;

4 $\mathtt{cov}(S^{+})\leftarrow\mathtt{cov}(S^{+})\cup\\{u\\}$ for
$S^{+}\in\mathcal{S}$ s.t. $u\in S^{+}$;

5 ReLevel$(S)$ and ReLevel$(S^{+})$;

6

7 else if  _$\sigma=(u,\mathcal{U},+)$_ then

8 $\mathtt{cov}(S^{+})\leftarrow\mathtt{cov}(S^{+})\cup\\{u\\}$ for
$S^{+}\in\mathcal{S}$ s.t. $u\in S^{+}$;

9 ReLevel$(S^{+})$;

10

11 else if  _$\sigma=(u,\mathcal{U},-)$_ then

12 $\mathtt{cov}(S^{-})\leftarrow\mathtt{cov}(S^{-})\setminus\\{u\\}$ if
$u\in\mathtt{cov}(S^{-})$;

13 ReLevel$(S^{-})$;

14

15Stabilize$(\mathcal{C})$;

16 Function  _Greedy $(\Sigma)$_

17 $I\leftarrow\mathcal{U}$, $\mathcal{L}_{j}\leftarrow\varnothing$ for every
$j\geq 0$;

18 while  _$I\neq\varnothing$_ do

19 $S^{*}\leftarrow\arg\max_{S\in\mathcal{S}}|I\cap S|$,
$\mathtt{cov}(S^{*})\leftarrow I\cap S^{*}$;

20 Add $S^{*}$ to $\mathcal{L}_{j}$ s.t.
$2^{j}\leq|\mathtt{cov}(S^{*})|<2^{j+1}$;

21 $I\leftarrow I\setminus\mathtt{cov}(S^{*})$;

22

23 return _$\mathcal{C}\leftarrow\bigcup_{j\geq 0}\mathcal{L}_{j}$_ ;

24

25Function  _ReLevel $(S)$_

26 if  _$\mathtt{cov}(S)=\varnothing$_ then

27 $\mathcal{C}\leftarrow\mathcal{C}\setminus\\{S\\}$;

28

29 else

30 Let $\mathcal{L}_{j}$ be the current level of $S$;

31 if  _$|\mathtt{cov}(S)| <2^{j}$ or $|\mathtt{cov}(S)|\geq 2^{j+1}$_ then

32 Let $j^{\prime}$ be the index s.t.
$2^{j^{\prime}}\leq|\mathtt{cov}(S)|<2^{j^{\prime}+1}$;

33 Move $S$ from $\mathcal{L}_{j}$ to $\mathcal{L}_{j^{\prime}}$;

34

35

36

37Function  _Stabilize $(\mathcal{C})$_

38 while  _$\exists S\in\mathcal{S}$ and $\mathcal{L}_{j}$ s.t. $|S\cap
A_{j}|\geq 2^{j+1}$_ do

39 $\mathtt{cov}(S)\leftarrow\mathtt{cov}(S)\cup(S\cap A_{j})$, ReLevel($S$);

40 while  _$\exists
S^{\prime}\in\mathcal{C}:\mathtt{cov}(S)\cap\mathtt{cov}(S^{\prime})\neq\varnothing$_
do

41
$\mathtt{cov}(S^{\prime})\leftarrow\mathtt{cov}(S^{\prime})\setminus\mathtt{cov}(S)$,
ReLevel($S^{\prime}$);

42

43

44

Algorithm 1 Dynamic Set Cover

We then describe our method for _dynamic set cover_ in Algorithm 1. First of
all, we use Greedy to initialize a set-cover solution $\mathcal{C}$ on
$\Sigma$ (Line 1). As shown in Lines 1–1, Greedy follows the classic greedy
algorithm for set cover, and the only difference is that all the sets in
$\mathcal{C}$ are assigned to different levels according to the sizes of their
cover sets. Then, the procedure of updating $\mathcal{C}$ for set operation
$\sigma$ is shown in Lines 1–1. Our method supports four types of set
operations to update $\Sigma$ as follows: $\sigma=(u,S,\pm)$, i.e., to
add/remove an element $u$ to/from a set $S\in\mathcal{S}$;
$\sigma=(u,\mathcal{U},\pm)$, i.e., to add/remove an element $u$ to/from the
universe $\mathcal{U}$. We identify three cases in which the assignment of $u$
must be changed for $\sigma$. When $\sigma=(u,S,-)$ and $\phi(u)=S$, it will
reassign $u$ to another set containing $u$; For $\sigma=(u,\mathcal{U},\pm)$,
it will add or delete the assignment of $u$ accordingly. After that, for each
set with some change in its cover set, it calls ReLevel (e.g., Lines 1, 1, and
1) to check whether the set should be moved to a new level based on the
updated size of its cover set. The detailed procedure of ReLevel is given in
Lines 1–1. Finally, Stabilize (Line 1) is always called for every $\sigma$ to
guarantee the stability of $\mathcal{C}$ since $\mathcal{C}$ may become
unstable due to the changes in $\Sigma$ and $\phi(u)$. The procedure of
stabilization is presented in Lines 1–1. It finds all sets that violate
Condition (2) of Definition 2 and adjust $\mathcal{C}$ for these sets until no
set should be adjusted anymore.

Theoretical Analysis: Next, we will analyze Algorithm 1 theoretically. We
first show that a set-cover solution returned by Greedy is stable. Then, we
prove that Stabilize converges to a stable solution in finite steps.

######  Lemma 1.

The solution $\mathcal{C}$ returned by Greedy is stable.

###### Proof.

First of all, it is obvious that each set $S\in\mathcal{C}$ is assigned to the
correct level according to the size of its cover set and Condition (1) of
Definition 2 is satisfied. Then, we sort the sets in $\mathcal{C}$ as
$S^{*}_{1},\ldots,S^{*}_{|\mathcal{C}|}$ by the order in which they are added.
Let $S^{*}_{i}$ be the set s.t. $|\mathtt{cov}(S^{*}_{i})|<2^{j+1}$ and
$|\mathtt{cov}(S^{*}_{i^{\prime}})|\geq 2^{j+1}$ for any $i^{\prime}<i$, i.e.,
$S^{*}_{i}$ is the first set added to level $\mathcal{L}_{j}$. We have $|I\cap
S^{*}_{i}|=|\mathtt{cov}(S^{*}_{i})|<2^{j+1}$ where $I$ is the set of
uncovered elements before $S^{*}_{i}$ is added to $\mathcal{C}$. If there were
a set $S\in\mathcal{S}$ such that $|S\cap A_{j}|>2^{j+1}$, we would acquire
$|I\cap S|\geq|S\cap A_{j}|>2^{j+1}$ and $|I\cap S|>|I\cap S^{*}_{i}|$, which
contradicts with Line 1 of Algorithm 2. Thus, $\mathcal{C}$ must satisfy
Condition (2) of Definition 2. To sum up, $\mathcal{C}$ is a stable solution.
∎

######  Lemma 2.

The procedure Stabilize converges to a stable solution in $O(m\log{m})$ steps.

###### Proof.

For an iteration of the while loop (i.e., Lines 1–1) that picks a set $S$ and
a level $\mathcal{L}_{j}$, the new level $\mathcal{L}_{j^{\prime}}$ of $S$
always satisfies $j^{\prime}>j$. Accordingly, all the elements in
$\mathtt{cov}(S)$ are moved from $A_{\leq j}$ to $A_{j^{\prime}}$. At the same
time, no element in $A_{\geq j^{\prime}}$ is moved to lower levels. Since each
level contains at most $m$ elements ($|A_{j}|\leq m$), Stabilize moves at most
$m$ elements across $O(\log m)$ levels. Therefore, it must terminate in
$O(m\log m)$ steps. Furthermore, after termination, the set-cover solution
$\mathcal{C}$ must satisfy both conditions in Definition 2. Thus, we conclude
the proof. ∎

The above two lemmas can guarantee that the set-cover solution provided by
Algorithm 1 is always stable after any change in the set system. In the next
subsection, we will present how to use it for fully-dynamic $k$-RMS.

###  III-B Algorithmic Description

Next, we will present how FD-RMS maintains the $k$-RMS result by always
keeping a _stable_ set-cover solution on a dynamic set system built from the
approximate top-$k$ results over tuple insertions and deletions.

Input : Query $\mathtt{RMS}(k,r)$, initial database $P_{0}$, parameters
$\varepsilon\in(0,1)$ and $M\in\mathbb{Z}^{+}$ ($M>r$)

Output : Result $Q_{0}$ of $\mathtt{RMS}(k,r)$ on $P_{0}$

1 Draw $M$ vectors $\\{u_{i}\in\mathbb{U}:i\in[1,M]\\}$ where the first $d$
are the standard basis of $\mathbb{R}^{d}_{+}$ and the remaining are uniformly
sampled from $\mathbb{U}$;

2 Compute $\Phi_{k,\varepsilon}(u_{i},P_{0})$ of every $u_{i}$ where
$i\in[1,M]$;

3 $L\leftarrow r$, $H\leftarrow M$, $m\leftarrow(L+H)/2$;

4 while  _$\mathtt{true}$_ do

5 foreach  _$p\in P_{0}$_ do

6 $S(p)\leftarrow\\{u_{i}\,:\,i\in[1,m]\wedge
p\in\Phi_{k,\varepsilon}(u_{i},P_{0})\\}$;

7

8 $\Sigma=(\mathcal{U},\mathcal{S})$ where $\mathcal{U}=\\{u_{i}:i\in[1,m]\\}$
and $\mathcal{S}=\\{S(p):p\in P_{0}\\})$;

9 $\mathcal{C}\leftarrow$ Greedy$(\Sigma)$;

10 if  _$|\mathcal{C}| <r$_ then

11 $L\leftarrow m+1$, $m\leftarrow(L+H)/2$;

12

13 else if  _$|\mathcal{C}| >r$_ then

14 $H\leftarrow m-1$, $m\leftarrow(L+H)/2$;

15

16 else if  _$|\mathcal{C}|=r$ or $m=M$_ then

17 break;

18

19

20return _$Q_{0}\leftarrow\\{p\in P_{0}\,:\,S(p)\in\mathcal{C}\\}$_ ;

Algorithm 2 Initialization

Initialization: We first present how FD-RMS computes an initial result $Q_{0}$
for $\mathtt{RMS}(k,r)$ on $P_{0}$ from scratch in Algorithm 2. There are two
parameters in FD-RMS: the approximation factor of top-$k$ results
$\varepsilon$ and the upper bound of sample size $M$. The lower bound of
sample size is set to $r$ because we can always find a set-cover solution of
size equal to the size of the universe (i.e., $m$ in FD-RMS). First of all, it
draws $M$ utility vectors $\\{u_{1},\ldots,u_{M}\\}$, where the first $d$
vectors are the standard basis of $\mathbb{R}^{d}_{+}$ and the remaining are
uniformly sampled from $\mathbb{U}$, and computes the
$\varepsilon$-approximate top-$k$ result of each vector. Subsequently, it
finds an appropriate $m\in[r,M]$ so that the size of the set-cover solution on
the set system $\Sigma$ built on $\mathcal{U}=\\{u_{1},\ldots,u_{m}\\}$ is
exactly $r$. The detailed procedure is as presented in Lines 2–2.
Specifically, it performs a binary search on range $[r,M]$ to determine the
value of $m$. For a given $m$, it first constructs a set system $\Sigma$
according to Lines 2–2. Next, it runs Greedy in Algorithm 1 to compute a set-
cover solution $\mathcal{C}$ on $\Sigma$. After that, if $|\mathcal{C}|\neq r$
and $m<M$, it will refresh the value of $m$ and rerun the above procedures;
Otherwise, $m$ is determined and the current set-cover solution $\mathcal{C}$
will be used to compute $Q_{0}$ for $\mathtt{RMS}(k,r)$. Finally, it returns
all the tuples whose corresponding sets are included in $\mathcal{C}$ as the
result $Q_{0}$ for $\mathtt{RMS}(k,r)$ on $P_{0}$ (Line 2).

Input : Query $\mathtt{RMS}(k,r)$, database $P_{t-1}$, operation $\Delta_{t}$,
set-cover solution $\mathcal{C}$

Output : Result $Q_{t}$ for $\mathtt{RMS}(k,r)$ on $P_{t}$

1 Update $P_{t-1}$ to $P_{t}$ w.r.t. $\Delta_{t}$;

2 for  _$i\leftarrow 1,\ldots,M$_ do

3 Update $\Phi_{k,\varepsilon}(u_{i},P_{t-1})$ to
$\Phi_{k,\varepsilon}(u_{i},P_{t})$ w.r.t. $\Delta_{t}$;

4

5Maintain $\Sigma$ based on $\Phi_{k,\varepsilon}(u_{i},P_{t})$;

6 if  _$\Delta_{t}=\langle p,+\rangle$_ then

7 foreach  _$u\in S(p)$_ do

8 if  _$u\in\mathtt{cov}(S(p^{\prime}))$ and $u\notin S(p^{\prime})$_ then

9 Update $\mathcal{C}$ for $\sigma=(u,S(p^{\prime}),-)$;

10

11

12

13 else if  _$\Delta_{t}=\langle p,-\rangle$_ then

14 Delete $S(p)$ from $\mathcal{C}$ if $S(p)\in\mathcal{C}$;

15 foreach  _$u\in\mathtt{cov}(S(p))$_ do

16 Update $\mathcal{C}$ for $\sigma=(u,S(p),-)$;

17

18

19if  _$|\mathcal{C}|\neq r$_ then

20 $m,\mathcal{C}\leftarrow$ UpdateM$(\Sigma)$;

21

22return _$Q_{t}\leftarrow\\{p\in P_{t}\,:\,S(p)\in\mathcal{C}\\}$_ ;

Algorithm 3 Update

(a) Dataset

(b) Initial construction

(c) Add tuple $p_{9}$

(d) Delete tuple $p_{1}$

Figure 3: An example of using FD-RMS to process a $k$-RMS with $k=1$ and $r=3$

Update: The procedure of updating the result of $\mathtt{RMS}(k,r)$ w.r.t.
$\Delta_{t}$ is shown in Algorithm 3. First, it updates the database from
$P_{t-1}$ to $P_{t}$ and the approximate top-$k$ result from
$\Phi_{k,\varepsilon}(u_{i},P_{t-1})$ to $\Phi_{k,\varepsilon}(u_{i},P_{t})$
for each $u_{i}$ w.r.t. $\Delta_{t}$ (Lines 3–3). Then, it also maintains the
set system $\Sigma$ according to the changes in approximate top-$k$ results
(Line 3). Next, it updates the set-cover solution $\mathcal{C}$ for the
changes in $\Sigma$ as follows.

  * •

Insertion: The procedure of updating $\mathcal{C}$ w.r.t. an insertion
$\Delta_{t}=\langle p,+\rangle$ is presented in Lines 3–3. The changes in
top-$k$ results lead to two updates in $\Sigma$: (1) the insertion of $S(p)$
to $\mathcal{S}$ and (2) a series of deletions each of which represents a
tuple $p^{\prime}$ is deleted from $\Phi_{k,\varepsilon}(u,P_{t})$ due to the
insertion of $p$. For each deletion, it needs to check whether $u$ is
previously assigned to $S(p^{\prime})$. If so, it will update $\mathcal{C}$ by
reassigning $u$ to a new set according to Algorithm 1 because $u$ has been
deleted from $S(p^{\prime})$.

  * •

Deletion: The procedure of updating $\mathcal{C}$ w.r.t. a deletion
$\Delta_{t}=\langle p,-\rangle$ is shown in Lines 3–3. In contrast to an
insertion, the deletion of $p$ leads to the removal of $S(p)$ from
$\mathcal{S}$ and a series of insertions. Thus, it must delete $S(p)$ from
$\mathcal{C}$. Next, it will reassign each $u\in\mathtt{cov}(S(p))$ to a new
set according to Algorithm 1.

Then, it checks whether the size of $\mathcal{C}$ is still $r$. If not, it
will update the sample size $m$ and the universe $\mathcal{U}$ so that the
set-cover solution $\mathcal{C}$ consists of $r$ sets. The procedure of
updating $m$ and $\mathcal{U}$ as well as maintaining $\mathcal{C}$ on the
updated $\mathcal{U}$ is shown in Algorithm 4. When $|\mathcal{C}|<r$, it will
add new utility vectors from $u_{m+1}$, and so on, to the universe and
maintain $\mathcal{C}$ until $|\mathcal{C}|=r$ or $m=M$. On the contrary, if
$|\mathcal{C}|>r$, it will drop existing utility vectors from $u_{m}$, and so
on, from the universe and maintain $\mathcal{C}$ until $|\mathcal{C}|=r$.
Finally, the updated $m$ and $\mathcal{C}$ are returned. After all above
procedures, it also returns $Q_{t}$ corresponding to the set-cover solution
$\mathcal{C}$ on the updated $\Sigma$ as the result of $\mathtt{RMS}(k,r)$ on
$P_{t}$.

Output : Updated sample size $m$ and solution $\mathcal{C}$ on $\Sigma$

1 if  _$|\mathcal{C}| <r$_ then

2 while  _$m <M$ and $|\mathcal{C}|<r$_ do

3 $m\leftarrow m+1$, $\mathcal{U}\leftarrow\mathcal{U}\cup\\{u_{m}\\}$;

4 foreach  _$p\in\Phi_{k,\varepsilon}(u_{m},P_{t})$_ do

5 $S(p)\leftarrow S(p)\cup\\{u_{m}\\}$;

6

7 Update $\mathcal{C}$ for $\sigma=(u_{m},\mathcal{U},+)$;

8

9

10 else if  _$|\mathcal{C}| >r$_ then

11 while  _$|\mathcal{C}| >r$_ do

12 $\mathcal{U}\leftarrow\mathcal{U}\setminus\\{u_{m}\\}$;

13 foreach  _$p\in\Phi_{k,\varepsilon}(u_{m},P_{t})$_ do

14 $S(p)\leftarrow S(p)\setminus\\{u_{m}\\}$;

15

16 Update $\mathcal{C}$ for $\sigma=(u_{m},\mathcal{U},-)$;

17 $m\leftarrow m-1$;

18

19

20return _$m,\mathcal{C}$_ ;

Algorithm 4 UpdateM$(\Sigma)$

######  Example 3.

Fig. 3 illustrates an example of using FD-RMS to process a $k$-RMS with $k=1$
and $r=3$. Here, we set $\varepsilon=0.002$ and $M=9$. In Fig. 3(b), we show
how to compute $Q_{0}$ for $\mathtt{RMS}(1,3)$ on
$P_{0}=\\{p_{1},\ldots,p_{8}\\}$. It first uses $m=(3+9)/2=6$ and runs Greedy
to get a set-cover solution $\mathcal{C}=\\{S(p_{1}),S(p_{2}),S(p_{4})\\}$.
Since $|\mathcal{C}|=3$, it does not change $m$ anymore and returns
$Q_{0}=\\{p_{1},p_{2},p_{4}\\}$ for $\mathtt{RMS}(1,3)$ on $P_{0}$. Then, the
result of FD-RMS after the update procedures for $\Delta_{1}=\langle
p_{9},+\rangle$ as Algorithm 3 is shown in Fig. 3(c). For $\mathtt{RMS}(1,3)$
on $P_{1}=\\{p_{1},\ldots,p_{9}\\}$, the result $Q_{1}$ is updated to
$\\{p_{1},p_{4},p_{9}\\}$. Finally, after the update procedures for
$\Delta_{2}=\langle p_{1},-\rangle$, as shown in Fig. 3(d), $m$ is updated to
$4$ and the result $Q_{2}$ for $\mathtt{RMS}(1,3)$ on $P_{2}$ is
$\\{p_{4},p_{7},p_{9}\\}$.

Theoretical Bound: The theoretical bound of FD-RMS is analyzed as follows.
First of all, we need to verify the set-cover solution $\mathcal{C}$
maintained by Algorithms 2–4 is always stable. According to Lemma 1, it is
guaranteed that the set-cover solution $\mathcal{C}$ returned by Algorithm 2
is stable. Then, we need to show it remains stable after the update procedures
of Algorithms 3 and 4. In fact, both algorithms use Algorithm 1 to maintain
the set-cover solution $\mathcal{C}$. Hence, the stability of $\mathcal{C}$
can be guaranteed by Lemma 2 since Stabilize is always called after every
update in Algorithm 1.

Next, we indicate the relationship between the result of $k$-RMS and the _set-
cover_ solution and provide the bound on the maximum-$k$ regret ratio of
$Q_{t}$ returned by FD-RMS on $P_{t}$.

######  Theorem 2.

The result $Q_{t}$ returned by FD-RMS is a
$\big{(}k,O(\varepsilon^{*}_{k,r^{\prime}}+\delta)\big{)}$-regret set of
$P_{t}$ with high probability where $r^{\prime}=O(\frac{r}{\log{m}})$ and
$\delta=O(m^{-\frac{1}{d}})$.

###### Proof.

Given a parameter $\delta>0$, a $\delta$-net [9] of $\mathbb{U}$ is a finite
set $U\subset\mathbb{U}$ where there exists a vector $\overline{u}$ with
$\|u-\overline{u}\|\leq\delta$ for any $u\in\mathbb{U}$. Since a random set of
$O(\frac{1}{\delta^{d-1}}\log\frac{1}{\delta})$ vectors in $\mathbb{U}$ is a
$\delta$-net with probability at least $\frac{1}{2}$ [9], one can generate a
$\delta$-net of size $O(\frac{1}{\delta^{d-1}}\log\frac{1}{\delta})$ with high
probability by random sampling from $\mathbb{U}$ in $O(1)$ repeated trials.

Let $B$ be the standard basis of $\mathbb{R}^{d}_{+}$ and $U$ be a
$\delta$-net of $\mathbb{U}$ where $B=\\{u_{1},\ldots,u_{d}\\}\subset U$.
Since $p\in P_{t}$ is scaled to $p[i]\leq 1$ for $i\in[1,d]$, we have
$\|p\|\leq\sqrt{d}$. According to the definition of $\delta$-net, there exists
a vector $\overline{u}\in U$ such that $\|\overline{u}-u\|\leq\delta$ for
every $u\in\mathbb{U}$. Hence, for any tuple $p\in P_{t}$,

$|\langle\overline{u},p\rangle-\langle
u,p\rangle|=|\langle\overline{u}-u,p\rangle|\leq\|\overline{u}-u\|\cdot\|p\|\leq\delta\cdot\sqrt{d}$
(1)

Moreover, as $Q_{t}$ corresponds to a set-cover solution $\mathcal{C}$ on
$\Sigma$, there exists a tuple $q\in Q_{t}$ such that
$\langle\overline{u},q\rangle\geq(1-\varepsilon)\cdot\omega_{k}(\overline{u},P_{t})$
for any $\overline{u}\in U$. We first consider a basis vector $u_{i}\in U$ for
some $i\in[1,d]$. We have
$\omega(u_{i},Q_{t})\geq(1-\varepsilon)\cdot\omega_{k}(u_{i},P_{t})$ and thus
$\omega(u_{i},Q_{t})\geq(1-\varepsilon)\cdot c$ where
$c=\min_{i\in[1,d]}\omega_{k}(u_{i},P_{t})$. Since $\|u\|=1$, there must exist
some $i$ with $u[i]\geq\frac{1}{\sqrt{d}}$ for any $u\in\mathbb{U}$.
Therefore, it holds that
$\omega(u,Q_{t})\geq\omega(u_{i},Q_{t})\cdot\frac{1}{\sqrt{d}}\geq(1-\varepsilon)\cdot\frac{c}{\sqrt{d}}$
for any $u\in\mathbb{U}$.

Next, we discuss two cases for $u\in\mathbb{U}$ separately.

  * •

Case 1 ($\omega_{k}(u,P_{t})\leq\frac{c}{\sqrt{d}}$): In this case, there
always exists $q\in Q_{t}$ such that $\langle
u,q\rangle\geq(1-\varepsilon)\cdot\omega_{k}(u,P_{t})$.

  * •

Case 2 ($\omega_{k}(u,P_{t})>\frac{c}{\sqrt{d}}$): Let $\overline{u}\in U$ be
the utility vector such that $\|\overline{u}-u\|\leq\delta$. Let
$\Phi_{k}(u,P_{t})=\\{p_{1},\ldots,p_{k}\\}$ be the top-$k$ results of $u$ on
$P_{t}$. According to Equation 1, we have
$\langle\overline{u},p_{i}\rangle\geq\langle
u,p_{i}\rangle-\delta\cdot\sqrt{d}$ for all $i\in[1,k]$ and thus
$\langle\overline{u},p_{i}\rangle\geq\omega_{k}(u,P_{t})-\delta\cdot\sqrt{d}$.
Thus, there exists $k$ tuples in $P_{t}$ with scores at least
$\omega_{k}(u,P_{t})-\delta\cdot\sqrt{d}$ for $\overline{u}$. We can acquire
$\omega_{k}(\overline{u},P_{t})\geq\omega_{k}(u,P_{t})-\delta\cdot\sqrt{d}$.
Therefore, there exists $q\in Q_{t}$ such that

$\displaystyle\langle u,q\rangle$
$\displaystyle\geq\langle\overline{u},q\rangle-\delta\cdot\sqrt{d}\geq(1-\varepsilon)\cdot\omega_{k}(\overline{u},P_{t})-\delta\cdot\sqrt{d}$
$\displaystyle\geq(1-\varepsilon)\cdot\big{(}\omega_{k}(u,P_{t})-\delta\cdot\sqrt{d}\big{)}-\delta\cdot\sqrt{d}$
$\displaystyle\geq\big{(}1-\varepsilon-\frac{(1-\varepsilon)d\delta}{c}-\frac{d\delta}{c}\big{)}\cdot\omega_{k}(u,P_{t})$
$\displaystyle\geq(1-\varepsilon-\frac{2d\delta}{c})\cdot\omega_{k}(u,P_{t})$

Considering both cases, we have
$\omega(u,Q_{t})\geq(1-\varepsilon-\frac{2d\delta}{c})\cdot\omega_{k}(u,P_{t})$
for any $u\in\mathbb{U}$ and thus $\mathtt{mrr}_{k}(Q_{t})$ over $P_{t}$ is at
most $\varepsilon+\frac{2d\delta}{c}$. In all of our experiments, the value of
$c$ is always between $0.5$ and $1$, and thus we regard $c$ as a constant in
this proof. Therefore, $Q_{t}$ is a
$\big{(}k,O(\varepsilon+\delta)\big{)}$-regret set of $P_{t}$ with high
probability for any $c,d=O(1)$. Moreover, since FD-RMS uses $m$ utility
vectors including $B$ to compute $Q_{t}$ and
$m=O(\frac{1}{\delta^{d-1}}\log\frac{1}{\delta})$, we can acquire
$\delta=O(m^{-\frac{1}{d}})$.

Finally, because any $(k,\varepsilon)$-regret set of $P_{t}$ corresponds to a
set-cover solution on $\Sigma$ (otherwise, the regret ratio is larger than
$\varepsilon$ for some utility vector) and the size of the optimal set-cover
solution on $\Sigma$ is $O(\frac{r}{\log{m}})$ according to Theorem 1, the
maximum $k$-regret ratio of any size-$r^{\prime}$ subset of $P_{t}$ is at
least $\varepsilon$ where $r^{\prime}=O(\frac{r}{\log{m}})$, i.e.,
$\varepsilon^{*}_{k,r^{\prime}}\geq\varepsilon$. Therefore, we conclude that
$Q_{t}$ is a $\big{(}k,O(\varepsilon^{*}_{k,r^{\prime}}+\delta)\big{)}$-regret
set of $P_{t}$ with high probability. ∎

Finally, the upper bound of the maximum $k$-regret ratio of $Q_{t}$ returned
by FD-RMS on $P_{t}$ is analyzed in the following corollary derived from the
result of Theorem 2.

######  Corollary 1.

It satisfies that $\mathtt{mrr}_{k}(Q_{t})=O(r^{-\frac{1}{d}})$ with high
probability if we assume $\varepsilon=O(m^{-\frac{1}{d}})$.

###### Proof.

As indicated in the proof of Theorem 2, $\mathcal{U}=\\{u_{1},u_{2},$
$\ldots,u_{m}\\}$ is a $\delta$-net of $\mathbb{U}$ where
$\delta=O(m^{-\frac{1}{d}})$ with high probability. Moreover, we have
$\mathtt{mrr}_{k}(Q_{t})=O(\varepsilon+\delta)$ and thus
$\mathtt{mrr}_{k}(Q_{t})=O(m^{-\frac{1}{d}})$ if
$\varepsilon=O(m^{-\frac{1}{d}})$. In addition, at any time, $\mathcal{U}$
must have at least $r$ utility vectors, i.e., $m\geq r$. Thus, we have
$\mathtt{mrr}_{k}(Q_{t})=O(r^{-\frac{1}{d}})$ since $m^{-\frac{1}{d}}\leq
r^{-\frac{1}{d}}$ for any $d>1$ and conclude the proof. ∎

Since $\varepsilon$ is tunable in FD-RMS, by trying different values of
$\varepsilon$, we can always find an appropriate one such that
$\varepsilon=O(m^{-\frac{1}{d}})$. Hence, from Corollary 1, we show that the
upper bound of FD-RMS is slightly higher than that of Cube [1] and Sphere [13]
(i.e., $O(r^{-\frac{1}{d-1}}$)) under a mild assumption.

Complexity Analysis: First, we use tree-based methods to maintain the
approximate top-$k$ results for FD-RMS (see Section III-C for details). Here,
the time complexity of each top-$k$ query is $O(n_{0})$ where $n_{0}=|P_{0}|$
because the size of $\varepsilon$-approximate top-$k$ tuples can be
$O(n_{0})$. Hence, it takes $O(M\cdot n_{0})$ time to compute the top-$k$
results. Then, Greedy runs $O(r)$ iterations to get a set-cover solution. At
each iteration, it evaluates $O(n_{0})$ sets to find $S^{*}$ in Line 1 of
Algorithm 1. Thus, the time complexity of Greedy is $O(r\cdot n_{0})$. FD-RMS
calls Greedy $O(\log{M})$ times to determine the value of $m$. Therefore, the
time complexity of computing $Q_{0}$ on $P_{0}$ is $O\big{(}(M+r\log{M})\cdot
n_{0}\big{)}$. In Algorithm 3, the time complexity of updating the top-$k$
results and set system $\Sigma$ is $O\big{(}\mathtt{u}(\Delta_{t})\cdot
n_{t}\big{)}$ where $\mathtt{u}(\Delta_{t})$ is the number of utility vectors
whose top-$k$ results are changed by $\Delta_{t}$. Then, the maximum number of
reassignments in cover sets is $|S(p)|$ for $\Delta_{t}$, which is bounded by
$O(\mathtt{u}(\Delta_{t}))$. In addition, the time complexity of Stabilize is
$O(m\log{m})$ according to Lemma 2. Moreover, the maximum difference between
the old and new values of $m$ is bounded by $O(m)$. Hence, the total time
complexity of updating $Q_{t}$ w.r.t. $\Delta_{t}$ is
$O\big{(}\mathtt{u}(\Delta_{t})\cdot n_{t}+m^{2}\log{m}\big{)}$.

###  III-C Implementation Issues

Index Structures: As indicated in Line 2 of Algorithm 2 and Line 3 of
Algorithm 3, FD-RMS should compute the $\varepsilon$-approximate top-$k$
result of each $u_{i}$ ($i\in[1,M]$) on $P_{0}$ and update it w.r.t.
$\Delta_{t}$. Here, we elaborate on our implementation for top-$k$
maintenance. In order to process a large number of (approximate) top-$k$
queries with frequent updates in the database, we implement a _dual-tree_ [21,
22, 23] that comprises a tuple index $\mathtt{TI}$ and a utility index
$\mathtt{UI}$.

The goal of $\mathtt{TI}$ is to efficiently retrieve the
$\varepsilon$-approximate top-$k$ result $\Phi_{k,\varepsilon}(u,P_{t})$ of
any utility vector $u$ on the up-to-date $P_{t}$. Hence, any space-
partitioning index, e.g., _k-d tree_ [24] and _Quadtree_ [25], can serve as
$\mathtt{TI}$ for top-$k$ query processing. In practice, we use _k-d tree_ as
$\mathtt{TI}$. We adopt the scheme of [26] to transform a top-$k$ query in
$\mathbb{R}^{d}$ into a $k$NN query in $\mathbb{R}^{d+1}$. Then, we implement
the standard top-down methods to construct $\mathtt{TI}$ on $P_{0}$ and update
it w.r.t. $\Delta_{t}$. The branch-and-bound algorithm is used for top-$k$
queries on $\mathtt{TI}$.

The goal of $\mathtt{UI}$ is to cluster the sampled utility vectors so as to
efficiently find each vector whose $\varepsilon$-approximate top-$k$ result is
updated by $\Delta_{t}$. Since the top-$k$ results of linear functions are
merely determined by directions, the basic idea of $\mathtt{UI}$ is to cluster
the utilities with high _cosine similarities_ together. Therefore, we adopt an
angular-based binary space partitioning tree called _cone tree_ [21] as
$\mathtt{UI}$. We generally follow Algorithms 8–9 in [21] to build
$\mathtt{UI}$ for $\\{u_{1},\ldots,u_{M}\\}$. We implement a top-down approach
based on Section 3.2 of [22] to update the top-$k$ results affected by
$\Delta_{t}$.

Parameter Tuning: Now, we discuss how to specify the values of $\varepsilon$,
i.e., the approximation factor of top-$k$ queries, and $M$, i.e., the upper
bound of $m$, in FD-RMS. In general, the value of $\varepsilon$ has direct
effect on $m$ as well as the efficiency and quality of results of FD-RMS. In
particular, if $\varepsilon$ is larger, the $\varepsilon$-approximate top-$k$
result of each utility vector will include more tuples and the set system
built on top-$k$ results will be more dense. As a result, to guarantee the
result size to be exactly $r$, FD-RMS will use more utility vectors (i.e., a
larger $m$) for a larger $\varepsilon$. Therefore, a smaller $\varepsilon$
leads to higher efficiency and lower solution quality due to smaller $m$ and
larger $\delta$, and vice versa. In our implementation, we use a trial-and-
error method to find appropriate values of $\varepsilon$ and $M$: For each
query $\mathtt{RMS}(k,r)$ on a dataset, we test different values of
$\varepsilon$ chosen from $[0.0001,\ldots,0.1024]$ and, for each value of
$\varepsilon$, $M$ is set to the smallest one chosen from
$[2^{10},\ldots,2^{20}]$ that always guarantees $m<M$. If the result size is
still smaller than $r$ when $m=M=2^{20}$, we will not use larger $M$ anymore
due to efficiency issue. The values of $\varepsilon$ and $M$ that strike the
best balance between efficiency and quality of results will be used. In Fig.
5, we present how the value of $\varepsilon$ affects the performance of FD-RMS
empirically.

##  IV Experiments

In this section, we evaluate the performance of FD-RMS on real-world and
synthetic datasets. We first introduce the experimental setup in Section IV-A.
Then, we present the experimental results in Section IV-B.

###  IV-A Experimental Setup

Algorithms: The algorithms compared are listed as follows.

  * •

Greedy: the greedy algorithm for $1$-RMS in [1].

  * •

Greedy∗: the randomized greedy algorithm for $k$-RMS when $k>1$ proposed in
[8].

  * •

GeoGreedy: a variation of Greedy for $1$-RMS in [7].

  * •

DMM-RRMS: a discretized matrix min-max based algorithm for $1$-RMS in [11].

  * •

$\varepsilon$-Kernel: computing an $\varepsilon$-kernel coreset as the $k$-RMS
result [9, 10] directly.

  * •

HS: a hitting-set based algorithm for $k$-RMS in [9].

  * •

Sphere: an algorithm that combines $\varepsilon$-Kernel with Greedy for
$1$-RMS in [13].

  * •

URM: a $k$-medoid clustering based algorithm for $1$-RMS in [14]. Following
[14], we use DMM-RRMS to compute an initial solution for URM.

  * •

FD-RMS: our fully-dynamic $k$-RMS algorithm proposed in Section III.

The algorithms that only work in two dimensions are not compared. All the
above algorithms except FD-RMS and URM333 The original URM in [14] is also a
static algorithm. We extend URM to support dynamic updates as described in
Algorithm 5 of Appendix B-C. cannot directly work in a fully dynamic setting.
In our experiments, they rerun from scratch to compute the up-to-date $k$-RMS
result once the skyline is updated by any insertion or deletion. In addition,
the algorithms that are not applicable when $k>1$ are not compared for the
experiments with varying $k$. Since $\varepsilon$-Kernel and HS are proposed
for min-size $k$-RMS that returns the smallest subset whose maximum $k$-regret
ratio is at most $\varepsilon$, we adapt them to our problem by performing a
binary search on $\varepsilon$ in the range $(0,1)$ to find the smallest value
of $\varepsilon$ that guarantees the result size is at most $r$.

Our implementation of FD-RMS and URM is in Java 8 and published on
GitHub444https://github.com/yhwang1990/dynamic-rms. We used the C++
implementations of baseline algorithms published by authors and followed the
default parameter settings as described in the original papers. All the
experiments were conducted on a server running Ubuntu 18.04.1 with a 2.3GHz
processor and 256GB memory.

Datasets: The datasets we use are listed as follows.

  * •

BB555www.basketball-reference.com is a basketball dataset that contains
$21,961$ tuples, each of which represents one player/season combination with
$5$ attributes such as _points_ and _rebounds_.

  * •

AQ666archive.ics.uci.edu/ml/datasets/Beijing+Multi-Site+Air-Quality+Data
includes hourly air-pollution and weather data from 12 monitoring sites in
Beijing. It has $382,168$ tuples and each tuple has $9$ attributes including
the concentrations of $6$ air pollutants like $\text{PM}_{\text{2.5}}$, as
well as $3$ meteorological parameters like _temperature_.

  * •

CT777archive.ics.uci.edu/ml/datasets/covertype contains the cartographic data
of forest covers in the Roosevelt National Forest of northern Colorado. It has
$581,012$ tuples and we choose $8$ numerical attributes, e.g., _elevation_ and
_slope_ , for evaluation.

  * •

Movie888grouplens.org/datasets/movielens is the tag genome dataset published
by MovieLens. We extract the relevance scores of $13,176$ movies and $12$ tags
for evaluation. Each tuple represents the relevance scores of $12$ tags to a
movie.

  * •

Indep is generated as described in [6]. It is a set of uniform points on the
unit hypercube where different attributes are independent of each other.

  * •

AntiCor is also generated as described in [6]. It is a set of random points
with anti-correlated attributes.

TABLE I: Statistics of datasets Dataset | $n$ | $d$ | _#skylines_ |  _updates_ (%)
---|---|---|---|---
BB | $21,961$ | $5$ | $200$ | $1.07$
AQ | $382,168$ | $9$ | $21,065$ | $5.60$
CT | $581,012$ | $8$ | $77,217$ | $13.4$
Movie | $13,176$ | $12$ | $3,293$ | $26.5$
Indep |  $100$K–$1$M |  $2$–$10$ |  see Fig. 4
AntiCor |  $100$K–$1$M |  $2$–$10$ |  see Fig. 4

Figure 4: Sizes and update rates of the skylines of synthetic datasets

The statistics of datasets are reported in Table I. Here, $n$ is the number of
tuples; $d$ is the dimensionality; _#skylines_ is the number of tuples on the
skyline; and _updates_ (%) is the percentage of tuple operations that trigger
any update on the skyline. Note that we generated several Indep and AntiCor
datasets by varying $n$ from $100$K to $1$M and $d$ from $2$ to $10$ for
scalability tests. By default, we used the ones with $n=100$K and $d=6$. The
sizes and update rates of the skylines of synthetic datasets are shown in Fig.
4.

Workloads: The workload of each experiment was generated as follows: First, we
randomly picked $50\%$ of tuples as the initial dataset $P_{0}$; Second, we
inserted the remaining $50\%$ of tuples one by one into the dataset to test
the performances for insertions; Third, we randomly deleted $50\%$ of tuples
one by one from the dataset to test the performances for deletions. It is
guaranteed that the orders of operations kept the same for all algorithms. The
$k$-RMS results were recorded $10$ times when $10\%,20\%,\ldots,100\%$ of the
operations were performed.

Performance Measures: The efficiency of each algorithm was measured by
_average update time_ , i.e., the average wall-clock time of an algorithm to
update the result of $k$-RMS for each operation. For the static algorithms, we
only took the time for $k$-RMS computation into account and ignored the time
for skyline maintenance for fair comparison. The quality of results was
measured by the _maximum $k$-regret ratio_ ($\mathtt{mrr}_{k}$) for a given
size constraint $r$, and, of course, the smaller $\mathtt{mrr}_{k}$ the
better. To compute $\mathtt{mrr}_{k}(Q)$ of a result $Q$, we generated a test
set of $500$K random utility vectors and used the maximum regret value found
as our estimate. Since the $k$-RMS results were recorded $10$ times for each
query, we reported the average of the maximum $k$-regret ratios of $10$
results for evaluation.

###  IV-B Experimental Results

(a) BB

(b) AQ

(c) CT

(d) Movie

(e) Indep

(f) AntiCor

Figure 5: Performance of FD-RMS with varying $\varepsilon$ ($k=1$; $r=20$ for
BB and $r=50$ for other datasets). Note that the red line represents the
update time and the blue bars denote the maximum regret ratios.

(a) BB

(b) AQ

(c) CT

(d) Movie

(e) Indep

(f) AntiCor

Figure 6: Update time and maximum regret ratios with varying the result size
$r$ ($k=1$)

Effect of parameter $\varepsilon$ on FD-RMS: In Fig. 5, we present the effect
of the parameter $\varepsilon$ on the performance of FD-RMS. We report the
update time and maximum regret ratios of FD-RMS for $k=1$ and $r=50$ on each
dataset (except $r=20$ on BB) with varying $\varepsilon$. We use the method
described in Section III-C to set the value of $M$ for each value of
$\varepsilon$. First of all, the update time of FD-RMS increases significantly
with $\varepsilon$. This is because both the time to process an
$\varepsilon$-approximate top-$k$ query and the number of top-$k$ queries
(i.e., $M$) grow with $\varepsilon$, which requires a larger overhead to
maintain both top-$k$ results and set-cover solutions. Meanwhile, the quality
of results first becomes better when $\varepsilon$ is larger but then could
degrade if $\varepsilon$ is too large. The improvement in quality with
increasing $\varepsilon$ is attributed to larger $m$ and thus smaller
$\delta$. However, once $\varepsilon$ is greater than the maximum regret ratio
$\varepsilon^{*}_{k,r}$ of the optimal result (whose upper bound can be
inferred from practical results), e.g., $\varepsilon=0.0512$ on BB, the result
of FD-RMS will contain less than $r$ tuples and its maximum regret ratio will
be close to $\varepsilon$ no matter how large $m$ is. To sum up, by setting
$\varepsilon$ to the one that is slightly lower than $\varepsilon^{*}_{k,r}$
among $[0.0001,\ldots,0.1024]$, FD-RMS performs better in terms of both
efficiency and solution quality, and the values of $\varepsilon$ in FD-RMS are
decided in this way for the remaining experiments.

Effect of result size $r$: In Fig. 6, we present the performance of different
algorithms for $1$-RMS (a.k.a. $r$-regret query) with varying $r$. In
particular, $r$ is ranged from $10$ to $100$ on each dataset (except BB where
$r$ is ranged from $5$ to $25$). In general, the update time of each algorithm
grows while the maximum regret ratios drop with increasing $r$. But, for FD-
RMS, it could take less update time when $r$ is larger in some cases. The
efficiency of FD-RMS is positively correlated with $m$ but negatively
correlated with $\varepsilon$. On a specific dataset, FD-RMS typically chooses
a smaller $\varepsilon$ when $r$ is large, and vice versa. When $\varepsilon$
is smaller, $m$ may decrease even though $r$ is larger. Therefore, the update
time of FD-RMS decreases with $r$ in some cases because a smaller
$\varepsilon$ is used. Among all algorithms tested, Greedy is the slowest and
fails to provide results within one day on AQ, CT, and AntiCor when $r>80$.
GeoGreedy runs much faster than Greedy while having equivalent quality on low-
dimensional data. However, it cannot scale up to high dimensions (i.e., $d>7$)
because the cost of finding _happy points_ grows significantly with $d$. DMM-
RRMS suffers from two drawbacks: (1) it also cannot scale up to $d>7$ due to
huge memory consumption; (2) its solution quality is not competitive when
$r\geq 50$ because of the sparsity of space discretization. The solution
quality of $\varepsilon$-Kernel is generally inferior to any other algorithm
because the size of an $\varepsilon$-kernel coreset is much larger than the
size of the minimum $(1,\varepsilon)$-regret set. Although HS provides results
of good quality in most cases, it runs several orders of magnitude slower than
FD-RMS. Sphere demonstrates better performance than other static algorithms.
Nevertheless, its efficiency is still much lower than FD-RMS, especially on
datasets with large skyline sizes, e.g., CT and AntiCor, where FD-RMS runs up
to three orders of magnitude faster. URM shows good performance in both
efficiency and solution quality for small $r$ (e.g., $r\leq 20$) and skyline
sizes (e.g., on BB and Indep). However, it scales poorly to large $r$ and
skyline sizes because the convergence of k-medoid becomes very slow and the
number of linear programs for regret computation grows rapidly when $r$ and
and skyline sizes increase. In addition, URM does not provide high-quality
results in many cases since k-medoid cannot escape from local optima. To sum
up, FD-RMS outperforms all other algorithms for fully-dynamic $1$-RMS in terms
of efficiency. Meanwhile, the maximum regret ratios of the results of FD-RMS
are very close (the differences are less than $0.01$ in almost all cases) to
the best of static algorithms.

(a) BB

(b) AQ

(c) CT

(d) Movie

(e) Indep

(f) AntiCor

Figure 7: Update time and maximum regret ratios with varying $k$ ($r=10$ for
BB and Indep; $r=50$ for other datasets)

(a) Indep, varying $d$

(b) AntiCor, varying $d$

(c) Indep, varying $n$

(d) AntiCor, varying $n$

Figure 8: Scalability with varying the dimensionality $d$ and dataset size $n$
($k=1,\;r=50$)

Effect of $k$: The results for $k$-RMS with varying $k$ from $1$ to $5$ are
illustrated in Fig. 7. We only compare FD-RMS with Greedy∗,
$\varepsilon$-Kernel, and HS because other algorithms are not applicable to
the case when $k>1$. We set $r=10$ for BB and Indep and $r=50$ for the other
datasets. The results of Greedy∗ for $k>1$ are only available on BB and Indep.
For the other datasets, Greedy∗ fails to return any result within one day when
$k>1$. We can see all algorithms run much slower when $k$ increases. For FD-
RMS, lower efficiencies are caused by higher cost of maintaining top-$k$
results. HS and $\varepsilon$-Kernel must consider all tuples in the datasets
instead of only skylines to validate that the maximum $k$-regret ratio is at
most $\varepsilon$ when $k>1$. For Greedy∗, the number of linear programs to
compute $k$-regret ratios increases drastically with $k$. Meanwhile, the
maximum $k$-regret ratios drop with $k$, which is obvious according to its
definition. FD-RMS achieves speedups of up to four orders of magnitude than
the baselines on all datasets. At the same time, the solution quality of FD-
RMS is also better on all datasets except Movie and CT, where the results of
HS are of slightly higher quality in some cases.

Scalability: Finally, we evaluate the scalability of different algorithms
w.r.t. the dimensionality $d$ and dataset size $n$. To test the impact of $d$,
we fix $n=100$K, $k=1$, $r=50$, and vary $d$ from $2$ to $10$. The performance
with varying $d$ is shown in Fig. 8(a)–8(b). Both the update time and maximum
regret ratios of all algorithms increase dramatically with $d$. Although
almost all algorithms show good performance when $d=2,3$, most of them quickly
become very inefficient in high dimensions. Nevertheless, FD-RMS has a
significantly better scalability w.r.t. $d$: It achieves speedups of at least
$100$ times over any other algorithm while providing results of equivalent
quality when $d\geq 7$.

To test the impact of $n$, we fix $d=6$, $k=1$, $r=50$, and vary $n$ from
$100$K to $1$M. The update time with varying $n$ is shown in Fig. 8(c)–8(d).
For static algorithms, we observe different trends in efficiency on two
datasets: The update time slightly drops on Indep but keeps steady on AntiCor.
The efficiencies are determined by two factors, i.e., _the number of tuples on
the skyline_ and _the frequency of skyline updates_. As shown in Fig. 4, when
$n$ is larger, the number of tuples on the skyline increases but the frequency
of skyline updates decreases. On Indep, the benefits of lower update
frequencies outweigh the cost of more skyline tuples; on AntiCor, two factors
cancel each other. FD-RMS runs slower when $n$ increases due to higher cost of
maintaining top-$k$ results on Indep. But, on AntiCor, the update time keeps
steady with $n$ because of smaller values of $\varepsilon$ and $m$, which
cancel the higher cost of maintaining top-$k$ results. We can observe that the
maximum regret ratios of most algorithms are not not significantly affected by
$n$. The solution quality of FD-RMS is close to the best of static algorithms.
Generally, FD-RMS always outperforms all baselines for different values of
$n$.

##  V Related Work

There have been extensive studies on the $k$-regret minimizing set ($k$-RMS)
problem (see [27] for a survey). Nanongkai et al. [1] first introduced the
notions of _maximum regret ratio_ and _$r$ -regret query_ (i.e., maximum
$1$-regret ratio and $1$-RMS in this paper). They proposed the Cube algorithm
to provide an upper-bound guarantee for the maximum regret ratio of the
optimal solution of $1$-RMS. They also proposed the Greedy heuristic for
$1$-RMS, which always picked a tuple that maximally reduced the maximum regret
ratio at each iteration. Peng and Wong [7] proposed the GeoGreedy algorithm to
improve the efficiency of Greedy by utilizing the geometric properties of
$1$-RMS. Asudeh et al. [11] proposed two discretized matrix min-max (DMM)
based algorithms for $1$-RMS. Xie et al. [13] designed the Sphere algorithm
for $1$-RMS based on the notion of $\varepsilon$-kernel [28]. Shetiya et al.
[14] proposed a unified algorithm called URM based on $k$-Medoid clustering
for $l^{p}$-norm RMS problems, of which $1$-RMS was a special case when
$p=\infty$. The aforementioned algorithms cannot be used for $k$-RMS when
$k>1$. Chester et al. [8] first extended the notion of $1$-RMS to $k$-RMS.
They also proposed a randomized Greedy∗ algorithm that extended the Greedy
heuristic to support $k$-RMS when $k>1$. The min-size version of $k$-RMS that
returned the minimum subset whose maximum $k$-regret ratio was at most
$\varepsilon$ for a given $\varepsilon\in(0,1)$ was studied in [9, 12]. They
proposed two algorithms for min-size $k$-RMS based on the notion of
$\varepsilon$-kernel [28] and hitting-set, respectively. However, all above
algorithms are designed for the static setting and very inefficient to process
database updates. To the best of our knowledge, FD-RMS is the first $k$-RMS
algorithm that is optimized for the fully dynamic setting and efficiently
maintains the result for dynamic updates.

Different variations of regret minimizing set problems were also studied
recently. The $1$-RMS problem with nonlinear utility functions were studied in
[29, 30, 31]. Specifically, they generalized the class of utility functions to
_convex functions_ [29], _multiplicative functions_ [30], and _submodular
functions_ [31], respectively. Asudeh et al. [32] proposed the rank-regret
representative (RRR) problem. The difference between RRR and RMS is that the
regret in RRR is defined by ranking while the regret in RMS is defined by
score. Several studies [33, 34, 14] investigated the _average regret
minimization_ (ARM) problem. Instead of minimizing the maximum regret ratio,
ARM returns a subset of $r$ tuples such that the average regret of all
possible users is minimized. The problem of _interactive regret minimization_
that aimed to enhance the regret minimization problem with user interactions
was studied in [35, 36]. Xie et al. [37] proposed a variation of min-size RMS
called $\alpha$-happiness query. Since these variations have different
formulations from the original $k$-RMS problem, the algorithms proposed for
them cannot be directly applied to the $k$-RMS problem. Moreover, these
algorithms are still proposed for the static setting without considering
database updates.

##  VI Conclusion

In this paper, we studied the problem of maintaining $k$-regret minimizing
sets ($k$-RMS) on dynamic datasets with arbitrary insertions and deletions of
tuples. We proposed the first fully-dynamic $k$-RMS algorithm called FD-RMS.
FD-RMS was based on transforming fully-dynamic $k$-RMS to a dynamic set cover
problem, and it could dynamically maintain the result of $k$-RMS with a
theoretical guarantee. Extensive experiments on real-world and synthetic
datasets confirmed the efficiency, effectiveness, and scalability of FD-RMS
compared with existing static approaches to $k$-RMS. For future work, it would
be interesting to investigate whether our techniques can be extended to
$k$-RMS and related problems on higher dimensions (i.e., $d>10$) or with
nonlinear utility functions (e.g., [29, 30, 31]) in dynamic settings.

## Acknowledgment

We thank anonymous reviewers for their helpful comments to improve this
research. Yanhao Wang has been supported by the MLDB project of Academy of
Finland (decision number: 322046). The research of Raymond Chi-Wing Wong is
supported by HKRGC GRF 16219816.

## References

  * [1] D. Nanongkai, A. D. Sarma, A. Lall, R. J. Lipton, and J. Xu, “Regret-minimizing representative databases,” _PVLDB_ , vol. 3, no. 1, pp. 1114–1124, 2010.
  * [2] J. Stoyanovich, K. Yang, and H. V. Jagadish, “Online set selection with fairness and diversity constraints,” in _EDBT_ , 2018, pp. 241–252.
  * [3] Y. Wang, Y. Li, and K. Tan, “Efficient representative subset selection over sliding windows,” _IEEE Trans. Knowl. Data Eng._ , vol. 31, no. 7, pp. 1327–1340, 2019.
  * [4] N. N. Liu, X. Meng, C. Liu, and Q. Yang, “Wisdom of the better few: cold start recommendation via representative based rating elicitation,” in _RecSys_ , 2011, pp. 37–44.
  * [5] Y. Wang, Y. Li, and K. Tan, “Coresets for minimum enclosing balls over sliding windows,” in _KDD_ , 2019, pp. 314–323.
  * [6] S. Börzsönyi, D. Kossmann, and K. Stocker, “The skyline operator,” in _ICDE_ , 2001, pp. 421–430.
  * [7] P. Peng and R. C. Wong, “Geometry approach for k-regret query,” in _ICDE_ , 2014, pp. 772–783.
  * [8] S. Chester, A. Thomo, S. Venkatesh, and S. Whitesides, “Computing k-regret minimizing sets,” _PVLDB_ , vol. 7, no. 5, pp. 389–400, 2014.
  * [9] P. K. Agarwal, N. Kumar, S. Sintos, and S. Suri, “Efficient algorithms for k-regret minimizing sets,” in _SEA_ , 2017, pp. 7:1–7:23.
  * [10] W. Cao, J. Li, H. Wang, K. Wang, R. Wang, R. C. Wong, and W. Zhan, “K-regret minimizing set: Efficient algorithms and hardness,” in _ICDT_ , 2017, pp. 11:1–11:19.
  * [11] A. Asudeh, A. Nazi, N. Zhang, and G. Das, “Efficient computation of regret-ratio minimizing set: A compact maxima representative,” in _SIGMOD_ , 2017, pp. 821–834.
  * [12] N. Kumar and S. Sintos, “Faster approximation algorithm for the k-regret minimizing set and related problems,” in _ALENEX_ , 2018, pp. 62–74.
  * [13] M. Xie, R. C. Wong, J. Li, C. Long, and A. Lall, “Efficient k-regret query algorithm with restriction-free bound for any dimensionality,” in _SIGMOD_ , 2018, pp. 959–974.
  * [14] S. Shetiya, A. Asudeh, S. Ahmed, and G. Das, “A unified optimization algorithm for solving “regret-minimizing representative” problems,” _PVLDB_ , vol. 13, no. 3, pp. 239–251, 2019.
  * [15] R. M. Karp, “Reducibility among combinatorial problems,” in _Complexity of Computer Computations_ , 1972, pp. 85–103.
  * [16] U. Feige, “A threshold of ln _n_ for approximating set cover,” _J. ACM_ , vol. 45, no. 4, pp. 634–652, 1998.
  * [17] S. Bhattacharya, M. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” _SIAM J. Comput._ , vol. 47, no. 3, pp. 859–887, 2018.
  * [18] A. Gupta, R. Krishnaswamy, A. Kumar, and D. Panigrahi, “Online and dynamic algorithms for set cover,” in _STOC_ , 2017, pp. 537–550.
  * [19] A. Abboud, R. Addanki, F. Grandoni, D. Panigrahi, and B. Saha, “Dynamic set cover: improved algorithms and lower bounds,” in _STOC_ , 2019, pp. 114–125.
  * [20] N. Hjuler, G. F. Italiano, N. Parotsidis, and D. Saulpic, “Dominating sets and connected dominating sets in dynamic graphs,” in _STACS_ , 2019, pp. 35:1–35:17.
  * [21] P. Ram and A. G. Gray, “Maximum inner-product search using cone trees,” in _KDD_ , 2012, pp. 931–939.
  * [22] A. Yu, P. K. Agarwal, and J. Yang, “Processing a large number of continuous preference top-k queries,” in _SIGMOD_ , 2012, pp. 397–408.
  * [23] R. R. Curtin, A. G. Gray, and P. Ram, “Fast exact max-kernel search,” in _SDM_ , 2013, pp. 1–9.
  * [24] J. L. Bentley, “Multidimensional binary search trees used for associative searching,” _Commun. ACM_ , vol. 18, no. 9, pp. 509–517, 1975.
  * [25] R. A. Finkel and J. L. Bentley, “Quad trees: A data structure for retrieval on composite keys,” _Acta Inf._ , vol. 4, pp. 1–9, 1974.
  * [26] Y. Bachrach, Y. Finkelstein, R. Gilad-Bachrach, L. Katzir, N. Koenigstein, N. Nice, and U. Paquet, “Speeding up the xbox recommender system using a euclidean transformation for inner-product spaces,” in _RecSys_ , 2014, pp. 257–264.
  * [27] 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.
  * [28] P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan, “Approximating extent measures of points,” _J. ACM_ , vol. 51, no. 4, pp. 606–635, 2004.
  * [29] T. K. Faulkner, W. Brackenbury, and A. Lall, “K-regret queries with nonlinear utilities,” _PVLDB_ , vol. 8, no. 13, pp. 2098–2109, 2015.
  * [30] J. Qi, F. Zuo, H. Samet, and J. C. Yao, “K-regret queries using multiplicative utility functions,” _ACM Trans. Database Syst._ , vol. 43, no. 2, pp. 10:1–10:41, 2018.
  * [31] T. Soma and Y. Yoshida, “Regret ratio minimization in multi-objective submodular function maximization,” in _AAAI_ , 2017, pp. 905–911.
  * [32] A. Asudeh, A. Nazi, N. Zhang, G. Das, and H. V. Jagadish, “RRR: Rank-regret representative,” in _SIGMOD_ , 2019, pp. 263–280.
  * [33] S. Zeighami and R. C. Wong, “Finding average regret ratio minimizing set in database,” in _ICDE_ , 2019, pp. 1722–1725.
  * [34] S. Storandt and S. Funke, “Algorithms for average regret minimization,” in _AAAI_ , 2019, pp. 1600–1607.
  * [35] D. Nanongkai, A. Lall, A. D. Sarma, and K. Makino, “Interactive regret minimization,” in _SIGMOD_ , 2012, pp. 109–120.
  * [36] M. Xie, R. C. Wong, and A. Lall, “Strongly truthful interactive regret minimization,” in _SIGMOD_ , 2019, pp. 281–298.
  * [37] 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 _ICDE_ , 2020, pp. 1009–1020.

TABLE II: Frequently used notations Symbol |  Description
---|---
$P_{t}$ |  the database at time $t$ ($t\geq 0$)
$p$ |  a tuple in database $P_{t}$
$d$ |  the dimensionality of $P_{t}$
$n_{t}$ |  the number of tuples in $P_{t}$
$\Delta$ |  a sequence $\langle\Delta_{1},\Delta_{2},\ldots\rangle$ of operations for database update
$\Delta_{t}$ |  an operation $\langle p,+\rangle$ or $\langle p,-\rangle$ at time $t$ to update the database from $P_{t-1}$ to $P_{t}$ by adding/deleting tuple $p$
$\mathbb{U}$ |  the space of all nonnegative utility vectors
$u$ |  a utility vector in $\mathbb{U}$
$\varphi(u,P_{t})$ |  the top-ranked tuple in $P_{t}$ w.r.t. $u$
$\omega(u,P_{t})$ |  the score of $\varphi(u,P_{t})$ w.r.t. $u$
$\varphi_{j}(u,P_{t})$ |  the $j$th-ranked tuple in $P_{t}$ w.r.t. $u$
$\omega_{j}(u,P_{t})$ |  the score of $\varphi_{j}(u,P_{t})$ w.r.t. $u$
$\Phi_{k}(u,P_{t})$ |  the set of top-$k$ results of $P_{t}$ w.r.t. $u$, i.e., $\Phi_{k}(u,P_{t})=\\{\varphi_{j}(u,P_{t}):1\leq j\leq k\\}$
$\Phi_{k,\varepsilon}(u,P_{t})$ |  the set of $\varepsilon$-approximate top-$k$ results of $P_{t}$ w.r.t. $u$, i.e., $\Phi_{k,\varepsilon}(u,P_{t})=\\{p\in P_{t}:\langle u,p\rangle\geq(1-\varepsilon)\cdot\omega_{k}(u,P)\\}$
$\mathtt{rr}_{k}(u,Q)$ |  the $k$-regret ratio of a subset $Q\subseteq P_{t}$ w.r.t. $u$
$\mathtt{mrr}_{k}(Q)$ |  the maximum $k$-regret ratio of a subset $Q\subseteq P_{t}$
$\mathtt{RMS}(k,r)$ |  a $k$-RMS problem with size constraint $r\in\mathbb{Z}^{+}$ and $r\geq d$
$Q^{*}_{t}$ |  the optimal result of $\mathtt{RMS}(k,r)$ on $P_{t}$
$\varepsilon^{*}_{k,r}$ |  the (optimal) maximum $k$-regret ratio of $Q^{*}_{t}$ over $P_{t}$
$Q_{t}$ |  the result of $\mathtt{RMS}(k,r)$ on $P_{t}$ returned by FD-RMS
$\Sigma=(\mathcal{U},\mathcal{S})$ |  a set system with the universe $\mathcal{U}$ and the collection $\mathcal{S}$ of sets. When $\Sigma$ is built on the approximate top-$k$ results of $m$ utility vectors on $P_{t}$, we have $m=|\mathcal{U}|$ and $n_{t}=|\mathcal{S}|$.
$\sigma$ |  an operation $\langle u,S,\pm\rangle$ or $\langle u,\mathcal{U},\pm\rangle$ to update the set system $\Sigma$ by adding/removing $u$ to/from $S\in\mathcal{S}$ or adding/removing $u$ to/from $\mathcal{U}$
$S(p)$ |  a set in $\mathcal{S}$ that contains all utility vectors in $\mathcal{U}$ where $p$ is an approximate top-$k$ result on $P_{t}$
$\mathcal{C}^{*}$ |  the optimal solution for set cover on $\Sigma$
$\mathcal{C}$ |  an approximate solution for set cover on $\Sigma$
$\mathtt{cov}(S)$ |  the cover set of $S$ in $\mathcal{C}$
$\varepsilon$ |  an input parameter to specify the approximation factor of top-$k$ queries in FD-RMS
$M$ |  an input parameter to provide the upper bound of the number $m$ of utility vectors used in FD-RMS
$\mathtt{u}(\Delta_{t})$ |  the number of utility vectors whose approximate top-$k$ results are changed by $\Delta_{t}$

##  Appendix A Frequently Used Notations

A list of frequently used notations in this paper is summarized in Table II.

##  Appendix B Additional Experimental Evaluation

###  B-A Extension of Greedy for Dynamic Updates

In Section IV, all algorithms (except FD-RMS and URM) we compare are static
algorithms that recompute the results each time when the skyline is updated.
In fact, it is possible to extend a static algorithm, e.g., Greedy [1], to
support dynamic updates as follows: Initially, it computes a $k$-regret
minimizing set of size $r^{\prime}=r+\Delta_{r}$ (where $\Delta_{r}$ is an
integer parameter) using Greedy. Among this set, a set of $r$ tuples is
reported as the result. The result is recomputed whenever (1) $\Delta_{r}$
tuples from the $k$-regret minimizing set of size $r^{\prime}$ are deleted (in
which case it recomputes a $k$-regret minimizing set of size $r^{\prime}$);
(2) there are a total of $\Delta_{s}$ number of insertions into the skyline
where $\Delta_{s}$ is another parameter. We refer to this extension of Greedy
as the Dynamic Greedy (DG) algorithm.

In this subsection, we compare the Dynamic Greedy (DG) algorithm with Greedy
and FD-RMS. Specifically, we test four sets of parameters
$\Delta_{s},\Delta_{r}$, namely DG-1 with $\Delta_{s}=10,\Delta_{r}=0.25r$,
DG-2 with $\Delta_{s}=25,\Delta_{r}=0.5r$, DG-3 with
$\Delta_{s}=50,\Delta_{r}=0.75r$, and DG-4 with $\Delta_{s}=100,\Delta_{r}=r$.
The original Greedy is a special case of DG with $\Delta_{s}=1,\Delta_{r}=0$.
The experimental results are shown in Fig. 9. First of all, when $\Delta_{s}$
and $\Delta_{r}$ increase, DG runs faster because the recomputation is
executed at lower frequencies. But unfortunately, DG still runs much slower
than FD-RMS even when $\Delta_{s}=100,\Delta_{r}=r$ because of the huge gap in
the efficiency of Greedy and FD-RMS. Meanwhile, the maximum regret ratios of
the results of DG increase with $\Delta_{s}$ and $\Delta_{r}$, and become
significantly higher than those of FD-RMS when $\Delta_{s}$ and $\Delta_{r}$
are large. This is because the results of DG could often be obsolete w.r.t.
up-to-date datasets. In general, DG is significantly inferior to FD-RMS in
terms of both efficiency and quality of results for different parameters.
Nevertheless, DG might be used to accelerate Greedy in dynamic settings if the
requirement for quality is not so strict.

###  B-B Effect of Update Patterns

In Section IV, we consider the updates to datasets consist of all insertions
first followed by all deletions to test the performance of different
algorithms for tuple insertions and deletions separately. In this subsection,
we evaluate the performance of FD-RMS in two update patterns: (1) First all
insertions followed by all deletions as Section IV (I+D); (2) A random mixture
of insertions and deletions (Mixed). We note that the efficiency and solution
quality of a static algorithm are not influenced by update patterns because
the update rates of skylines are similar for tuple insertions and deletions,
and it reruns from scratch for each skyline update. The update time of FD-RMS
in two update patterns is shown in Fig. 10. We can see that the update time is
nearly indifferent to update patterns. In addition, we also confirm that the
results returned by FD-RMS remain the same in almost all cases regardless of
the orders of tuple operations.

In addition, we show the update time of FD-RMS with varying $r$ for tuple
insertions and deletions in Fig. 11. The update time for deletions is slightly
longer than that for insertions on all datasets. This is mainly attributed to
the difference in the update of approximate top-$k$ results. For insertions,
the dual-tree can incrementally update the current top-$k$ result using the
utility index only; but for deletions, the dual-tree must retrieve the new
top-$k$ result from scratch on the tuple index once a top-$k$ tuple is
deleted.

###  B-C Extension of URM for Dynamic Updates

Input : Initial database $P_{0}$, set of operations $\Delta$

Output : Result $Q_{t}$ for $1$-RMS on $P_{t}$ at time $t$

/* compute an initial result $Q_{0}$ on $P_{0}$ */

1 run DMM-RRMS to get an initial result $S_{0}$;

2 run $k$-medoid from $S_{0}$ until convergence as $Q_{0}$;

/* update $Q_{t-1}$ to $Q_{t}$ for $\Delta_{t}=\langle p,\pm\rangle$ */

3 Update $P_{t-1}$ to $P_{t}$ w.r.t. $\Delta_{t}$;

4 if  _$\Delta_{t}=\langle p,+\rangle$_ then

5 if  _there exists $p^{\prime}\in Q_{t-1}$ such that the max regret ratio of
$p$ in the region $R(p^{\prime})$ of $p^{\prime}$ is lower than $p^{\prime}$_
then

6 $S^{\prime}\leftarrow Q_{t-1}\setminus\\{p^{\prime}\\}\cup\\{p\\}$;

7 run $k$-medoid from $S^{\prime}$ until convergence as $Q_{t}$;

8 else

9 $Q_{t}\leftarrow Q_{t-1}$;

10

11

12 else

/* for a deletion $\Delta_{t}=\langle p,-\rangle$ */

13 if  _$p\in Q_{t-1}$_ then

14 $S^{\prime}\leftarrow Q_{t-1}\setminus\\{p\\}\cup\\{p^{\prime}\\}$ where
$p^{\prime}\notin Q_{t-1}$ is top-ranked for at least one utility vector in
the region $R(p)$ of $p$;

15 run $k$-medoid from $S^{\prime}$ until convergence as $Q_{t}$;

16 else

17 $Q_{t}\leftarrow Q_{t-1}$;

18

19

Algorithm 5 Dynamic URM

Unlike other static algorithms, the URM algorithm [14] adopts an iterative
framework based on the $k$-medoid clustering for RMS computation. It is
intuitive to extend the iterative framework to support dynamic updates. The
high-level idea of updating the result of URM for tuple operations without
fully recomputation is as follows: If an operation does not affect the
convergence of the current result, then skip it directly; Otherwise, first
adjust the result for this operation and then run the iterative framework
starting from the new result until it converges again. The detailed procedures
of (dynamic) URM are presented in Algorithm 5.

(a) BB ($r=10$)

(b) Movie ($r=50$)

(c) Indep ($d=6,r=50$)

Figure 9: Performance of the Dynamic Greedy (DG) algorithm in comparison with
Greedy and FD-RMS ($k=1$). Parameter settings for DG are listed as follows:
DG-1 – $\Delta_{s}=10,\Delta_{r}=0.25r$; DG-2 –
$\Delta_{s}=25,\Delta_{r}=0.5r$; DG-3 – $\Delta_{s}=50,\Delta_{r}=0.75r$; DG-4
– $\Delta_{s}=100,\Delta_{r}=r$.

(a) BB

(b) AQ

(c) CT

(d) Movie

(e) Indep ($d=6$)

(f) AntiCor ($d=6$)

Figure 10: Update time of FD-RMS in different update patterns ($k=1$)

(a) BB

(b) AQ

(c) CT

(d) Movie

(e) Indep

(f) AntiCor

Figure 11: Update time of FD-RMS for tuple insertion and deletion ($k=1$). The
red line denotes the average update time for all tuple operations.