# High sensitivity characterization of an ultra-high purity NaI(Tl) crystal
scintillator with the SABRE proof-of-principle detector

F. Calaprice  spokesperson<EMAIL_ADDRESS>Physics Department, Princeton
University, Princeton, NJ 08544, USA  S. Copello  Dipartimento di Fisica,
Università degli Studi di Genova and INFN Genova, Genova I-16146, Italy  I.
Dafinei  INFN - Sezione di Roma, Roma I-00185, Italy  D. D’Angelo  INFN -
Sezione di Milano, Milano I-20133, Italy  Dipartimento di Fisica, Università
degli Studi di Milano, Milano I-20133, Italy  G. D’Imperio  INFN - Sezione di
Roma, Roma I-00185, Italy  G. Di Carlo  INFN - Laboratori Nazionali del Gran
Sasso, Assergi (L’Aquila) I-67100, Italy  M. Diemoz  INFN - Sezione di Roma,
Roma I-00185, Italy  A. Di Giacinto  INFN - Laboratori Nazionali del Gran
Sasso, Assergi (L’Aquila) I-67100, Italy  A. Di Ludovico  Physics Department,
Princeton University, Princeton, NJ 08544, USA  A. Ianni  INFN - Laboratori
Nazionali del Gran Sasso, Assergi (L’Aquila) I-67100, Italy  M. Iannone  INFN
- Sezione di Roma, Roma I-00185, Italy  F. Marchegiani  INFN - Laboratori
Nazionali del Gran Sasso, Assergi (L’Aquila) I-67100, Italy  A. Mariani
corresponding author<EMAIL_ADDRESS>Gran Sasso Science Institute,
L’Aquila I-67100, Italy  S. Milana  INFN - Sezione di Roma, Roma I-00185,
Italy  S. Nisi  INFN - Laboratori Nazionali del Gran Sasso, Assergi (L’Aquila)
I-67100, Italy  F. Nuti  School of Physics, The University of Melbourne,
Melbourne, VIC 3010, Australia  D. Orlandi  INFN - Laboratori Nazionali del
Gran Sasso, Assergi (L’Aquila) I-67100, Italy  V. Pettinacci  INFN - Sezione
di Roma, Roma I-00185, Italy  L. Pietrofaccia  Physics Department, Princeton
University, Princeton, NJ 08544, USA  S. Rahatlou  INFN - Sezione di Roma,
Roma I-00185, Italy  Dipartimento di Fisica, Sapienza Università di Roma, Roma
I-00185, Italy  M. Souza  Physics Department, Princeton University, Princeton,
NJ 08544, USA  B. Suerfu  corresponding author<EMAIL_ADDRESS>University of California Berkeley, Department of Physics, Berkeley, CA 94720,
USA  C. Tomei  INFN - Sezione di Roma, Roma I-00185, Italy  C. Vignoli  INFN -
Laboratori Nazionali del Gran Sasso, Assergi (L’Aquila) I-67100, Italy  M.
Wada  AstroCeNT, Nicolaus Copernicus Astronomical Center of the Polish Academy
of Sciences, Warsaw, Poland  A. Zani  INFN - Sezione di Milano, Milano
I-20133, Italy

###### Abstract

We present new results on the radiopurity of a 3.4-kg NaI(Tl) crystal
scintillator operated in the SABRE proof-of-principle detector setup. The
amount of potassium contamination, determined by the direct counting of
radioactive 40K, is found to be $2.2\pm 1.5$ ppb, lowest ever achieved for
NaI(Tl) crystals. With the active veto, the average background rate in the
crystal in the 1-6 keV energy region-of-interest (ROI) is $1.20\pm 0.05$
counts/day/kg/keV, which is a breakthrough since the DAMA/LIBRA experiment.
Our background model indicates that the rate is dominated by 210Pb and that
about half of this contamination is located in the PTFE reflector. We discuss
ongoing developments of the crystal manufacture aimed at the further reduction
of the background, including data from purification by zone refining. A
projected background rate lower than $\sim$0.2 counts/day/kg/keV in the ROI is
within reach. These results represent a benchmark for the development of next-
generation NaI(Tl) detector arrays for the direct detection of dark matter
particles.

The existence of dark matter is widely accepted [1], yet the particle nature
of dark matter is still an open fundamental question. Over the last 25 years,
a series of experimental efforts have been made to search for the interaction
of dark matter particles with ordinary matter in underground laboratories [1].
However, almost all efforts yielded null results despite the impressive
progress in background reduction techniques and detector technologies [2, 3,
4, 5, 6, 7, 8, 9]. Experimental efforts have mainly focused on the search for
the so-called weakly-interacting massive particles (WIMPs) introduced in 1985
[10]. At present, the best sensitivity has been obtained with a ton-scale
liquid xenon time projection chamber: the spin-independent WIMP-nucleon
scattering cross section is estimated to be less than
$\sim$4$\times$$10^{-47}$ cm2 for a 30-GeV WIMP [2].

As an alternative way to probe particle dark matter, it was shown that the
motion of the Earth around the Sun in the dark matter halo can induce an
annual modulation in the dark matter interaction rate [11]. The modulation,
which is of the order of a few % in amplitude, has a specific phase that
allows to discriminate against other non-modulating and modulating
backgrounds. This approach has been exploited by the DAMA experiment (short
for DAMA/NaI and DAMA/LIBRA) [12], which has been observing a clear annual
modulation in its array of 250-kg extremely radiopure NaI(Tl) crystals. The
annual modulation is consistent with the dark matter hypothesis, but in the
standard WIMP framework, it is in tension with other more sensitive direct
detection experiments [2, 3, 4, 6, 8, 13]. Due to a potential target-
dependence of WIMP-nucleon interactions, a verification using the same target
material is indispensable.

To test the DAMA annual modulation, ANAIS [14] and COSINE [15] are currently
operating 112.5 kg and 106 kg of NaI(Tl) crystal scintillators, respectively.
However, they could not provide a definite answer to the longstanding
controversy due to their signal-to-noise ratio diminished by constant
radioactive backgrounds several times higher than that observed in the DAMA
crystals [16, 17]. Large fractions of the backgrounds come from radioactive
contaminants in the crystal, most notably 40K, 210Pb and 3H. This indicates
that the definitive test of the annual modulation claim has to be addressed by
next-generation experiments using NaI(Tl) crystals with radiopurity similar to
or below the DAMA level, such as in the proposed SABRE experiment [18].

In this article, we report a detailed study of the background components of an
ultra-high radiopurity crystal grown for the SABRE experiment. While
preliminary measurements on the same crystal had been performed on the surface
[19] and underground inside a passive shielding [20], this study was carried
out underground in the SABRE proof-of-principle (PoP) liquid scintillator
active veto shielding (Fig. 1) in the Hall C of Laboratori Nazionali del Gran
Sasso (LNGS), Italy [18].

This crystal—NaI-33—was grown using ultra-high purity NaI powder after a
series of R&D activities [21, 22]. The preparation of the powder and the
crucible were carried out at Princeton [22, 19] and the crystal growth was
done at Radiation Monitoring Devices (RMD) in Massachusetts using the vertical
Bridgman method [19, 23]. The crystal has a mass of 3.4 kg, and is wrapped
with ten layers of PTFE tape (about 1 mm) and optically coupled directly to
3-inch Hamamatsu R11065 photomultiplier tubes (PMTs) that features high
quantum efficiency and low radioactivity [19]. The crystal-PMT assembly is
sealed inside a 2-mm-thick, high-purity copper enclosure [20], whose inner
volume is constantly flushed with nitrogen gas to purge moisture and radon.
The enclosure is deployed vertically via a 2-mm-thick, 121-cm-long blind-end
copper tube into a 1.3-m-diameter, 1.5-m-long stainless steel veto vessel
[18]. The veto vessel is filled with 2 tonnes of pseudocumene (PC) liquid
scintillator and $2.86$ g/L of 2,5-diphenyloxazole (PPO) wavelength shifter,
and is instrumented with ten Hamamatsu R5912 8-inch PMTs to serve as active
veto to enhance background rejection [21, 22]. The inner surface of the veto
vessel is lined with reflective Lumirror foils to improve light collection
[22]. The light yield of the active veto is measured to be $0.52\pm 0.01$
photoelectrons/keV (phe/keV) at 2615 keV using a 228Th calibration source. The
veto vessel is further shielded from the cavern by an inner high-density
polyethylene (HDPE, 10 cm on the top and bottom and at least 40 cm on the
sides) and an outer gamma shielding ($\sim$90 cm of water on the sides and
top, and 15-cm of lead on the bottom) [18]. A PTFE tube is used to position
wire-mount calibration sources next to the copper enclosure.

Figure 1: Technical drawing of the PoP system. From the outer to the inner
region: water tanks (blue), HDPE layers (white), veto vessel (light grey), and
crystal enclosure (brown).

The DAQ system consists of a CAEN V1495 custom FPGA trigger and two CAEN V1720
ADC boards (12-bit, 250 MS/s) [22]. The data acquisition is triggered by the
logical AND between the two PMTs coupled to the crystal with a 125-ns
coincidence window irrespective of the status of the veto detector [22]. Upon
trigger, waveforms in the subsequent $3.5\text{\,}\mathrm{\SIUnitSymbolMicro
s}$ window in all PMTs are digitized and read out by a dedicated DAQ software
[24].

The light yield and FWHM resolution of NaI-33 crystal scintillator, measured
by fitting the 59.5-keV photopeak of an 241Am source, is determined to be
$12.1\pm 0.2$ phe/keV and 13.5%, respectively. The light yield is slightly
higher than that measured in [20]. To determine the background rate in the 1-6
keV ROI, data were taken between August 9, 2020 and September 5, 2020 for a
total exposure of 26.4 days. To reject coincident backgrounds, events with
energy larger than 50 keV in the veto are rejected with 42% veto rejection
power in the ROI. In addition, to reduce noise, the following cuts were
applied:

  * •

$\langle t\rangle_{600}=\frac{\sum\limits_{t_{i}<600\textrm{
ns}}h_{i}t_{i}}{\sum\limits_{t_{i}<600\textrm{ ns}}t_{i}}\in[140,270]$ ns;

  * •

Trigger time delay $\in[-36,36]$ ns;

  * •

No. of clusters in each PMT $\geq 2$;

  * •

$C_{(0,1000)}/h_{max}$ $>$ 50 ns;

  * •

$0.2<C_{(200,400)}/C_{(0,200)}<0.9$;

  * •

$0.1<C_{(400,600)}/C_{(200,400)}<0.9$.

where $h_{i}$ is the amplitude at time $t_{i}$ in ns, and $C_{(t_{i},t_{j})}$
is the pulse area between $t_{i}$ and $t_{j}$ in ns. These variables are
described in detail in [20]. Figure 2 shows the final acceptance rate as a
function of energy after these cuts. The average event acceptance in the ROI
is estimated to be 77.6% [25]. The energy spectrum after cuts and efficiency
correction is shown in Fig. 3 (black dots) up to 100 keV, and in Fig. 4 up to
20 keV. The measured rate in 1-6 keV (1-10 keV) is $1.20\pm 0.05$ cpd/kg/keV
($1.09\pm 0.04$ cpd/kg/keV).

Figure 2: Acceptance of crystal events after noise rejection cuts as a
function of energy, evaluated using a 228Th calibration source. Figure 3:
Energy spectrum from NaI-33 up to 100 keV with a spectral fit. The spectrum is
shown after selection cuts and efficiency correction. Figure 4: Energy
spectrum from NaI-33 below 20 keV with the spectral fit. The spectrum is shown
after selection cuts and efficiency-corrected.

A spectral analysis was performed to quantify the contribution of different
background components [25]. Predicted spectral shapes from different
background sources were calculated by Monte Carlo [26]. In the fit, the
activities of the following components were treated as free or semi-free
parameters: 40K, 210Pb, 3H, 226Ra, 232Th, 129I, 121mTe, 127mTe, and a flat
component which includes 87Rb and other internal and external background
contributions. In addition, 210Pb from the PTFE reflector wrapping the crystal
was included to reproduce the peak at $\sim$12 keV due to X-rays from 210Pb.
In the spectral fit, a Gaussian penalty was applied to 40K with mean equal to
$0.14\pm 0.01$ mBq/kg corresponding to the prediction from ICP-MS measurements
[19]. Assuming secular equilibrium for 226Ra and 232Th chain segments,
Gaussian penalties ($5.9\pm
0.6\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{Bq}\mathrm{/}\mathrm{k}\mathrm{g}$
for 226Ra and $1.6\pm
0.3\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{Bq}\mathrm{/}\mathrm{k}\mathrm{g}$
for 232Th) were implemented based on measurements from 214Bi-Po and 212Bi-Po
time-correlated events, respectively [20].

The result of the fit is shown in Fig. 3 and in Fig. 4. The p-value of the fit
is equal to 0.26 with $\chi^{2}/N_{dof}=96/88$. Table 1 summarises the
breakdown of the background components determined from the fit. The background
rate in the ROI, dominated by 210Pb in the bulk of the crystal and on the
surface of the PTFE reflector, is found to be conservatively equal to $1.16\pm
0.10$ cpd/kg/keV. The 40K activity is estimated to be $0.14\pm 0.01$ mBq/kg.
This value is consistent with an independent measurement of 40K using the
coincidence between 3.2-keV X-ray/auger electrons in the crystal and 1.46 MeV
gamma ray in the active veto, which yielded $0.07\pm 0.05$ mBq/kg ($2.2\pm
1.5$ ppb, or $<$ 4.7 ppb at 90% CL) despite limited statistics.

Table 1: Background components in NaI-33 from the spectral fit, current rate
in ROI (1-6 keV), and projected rate in ROI for future crystals. The future
rate assumes underground crystal production with zone-refining purification
and improved reflector radiopurity. The activity of 210Pb in the reflector is
normalized to the crystal mass for comparison with bulk activities. Upper
limits are given as one-sided 90% CL. Rates are conservatively calculated
using upper limits.

Source | Activity | Rate in ROI | Projected
---|---|---|---
| in NaI-33 | in NaI-33 | rate in ROI
| [mBq/kg] | [cpd/kg/keV] | [cpd/kg/keV]
40K | 0.14$\pm$0.01 | 0.018$\pm$0.001 |  $\leq$0.004
210Pb (bulk) | 0.41$\pm$0.02 | 0.28$\pm$0.01 |  $\leq$0.093$\pm$0.003
226Ra | 0.0059$\pm$0.0006 | 0.0044$\pm$0.0005 | 0.0044$\pm$0.0005
232Th | 0.0016$\pm$0.0003
3H | 0.012$\pm$0.007 |  $\leq$0.12 | –
129I | 1.34$\pm$0.04 | $\leq$0.011 | –
121mTe |  $\leq$0.084
127mTe | 0.016$\pm$0.006
210Pb (PTFE) | 0.32$\pm$0.06 | 0.63$\pm$0.09 |  $\leq$0.007
Other |  | 0.10$\pm$0.05 | 0.10$\pm$0.05
total |  | 1.16$\pm$0.10 | 0.21$\pm$0.05

The activity of bulk 210Pb is determined to be $0.41\pm 0.02$ mBq/kg,
consistent with earlier measurements using $\alpha$ counting of 210Po [19,
20]. Although this value is about one order of magnitude larger than that in
DAMA, it is smaller than those in ANAIS and COSINE, where on average the
activity is about 1 mBq/kg [27, 28].

The activity of 210Pb in the reflector is measured to be $1.1\pm 0.2$ mBq,
with the first $4\text{\,}\mathrm{\SIUnitSymbolMicro m}$ from the crystal
surface mostly responsible for background events. Although the commercial PTFE
tape was carefully cleaned by acid leach [22], this analysis indicates that
the cleaning procedure is not very effective in removing 210Pb impurities. The
210Pb radioactivity of PTFE has been studied by other experiments: the special
PTFE used in the CUORE-0 experiment has a 210Pb activity $\leq
123\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{Bq}\mathrm{/}\mathrm{k}\mathrm{g}_{\textrm{PTFE}}$
(90% CL) [29, 30]; in the DarkSide-50 experiment [31], 210Pb activity in PTFE
is measured to be $\leq 38$ mBq/kg${}_{\textrm{PTFE}}$ (90% CL) by
$\gamma$-spectroscopy [32] and $\leq 46$ mBq/kg${}_{\textrm{PTFE}}$ by 210Po
$\alpha$ counting [33]. These considerations imply that the background due to
the PTFE reflector can be reduced to a secondary component by custom or
special manufacturing of the PTFE tapes.

The activation rate of 3H in NaI is measured to be $83\pm 27$ cpd/kg by ANAIS
[34]. NaI-33 has undergone a 9-month surface exposure at sea level and a
12-month cooling underground. At the predicted activation rate, NaI-33 would
have seen a 3H activity of $37\pm
12\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{Bq}\mathrm{/}\mathrm{k}\mathrm{g}$.
The actual 3H activity is estimated to be $12\pm
7\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{Bq}\mathrm{/}\mathrm{k}\mathrm{g}$.
Although limited by statistics, the 3H production rate in NaI-33 seems to be
lower. One possibility is that the previously reported 3H rate is not entirely
due to cosmogenic 3H, and instead varying amount of 3H is introduced into the
crystal as NaOH impurity depending on the powder drying and crystal growth
method [22].

To further improve radiopurity of crystals to be grown in the future, we have
tested the zone refining of ultra-high purity NaI powder. Table 2, reproduced
from [35], shows that many impurities are greatly reduced in the first three
samples (about 50% of the ingot), and in particular 40K and 87Rb are reduced
to negligible levels.

Table 2: In the zone refining test, 53 zone passes were performed on 744 g of ultra-high purity NaI powder, and five samples were taken from different ingot locations and analyzed to determine the purification efficiency [35]. A few other elements are included to show effectiveness for other metallic impurities. Isotope | Impurity concentration (ppb)
---|---
| Powder | $S_{1}$ | $S_{2}$ | $S_{3}$ | $S_{4}$ | $S_{5}$
39K | 7.5 |  $<$0.8 |  $<$0.8 | 1 | 16 | 460
85Rb |  $<$0.2 |  $<$0.2 |  $<$0.2 |  $<$0.2 |  $<$0.2 | 0.7
208Pb | 1.0 | 0.4 | 0.4 |  $<$0.4 | 0.5 | 0.5
24Mg | 14 | 10 | 8 | 6 | 7 | 140
133Cs | 44 | 0.3 | 0.2 | 0.5 | 3.3 | 760
138Ba | 9 | 0.1 | 0.2 | 1.4 | 19 | 330

Quantitatively, the reduction of K and Rb depends on the segregation
coefficient $k$ and the fraction of the purified material to be reserved [22,
35]. The segregation coefficient of K is estimated to be 0.57 while for Rb it
is $<$ 0.59 at 90% CL [35]. Based on this, Table 3 lists the reduction of
impurity concentration for different combinations of number of zone passes and
fraction of the material reserved (Fig. 9 in [35]). Based on this, the purity
can be further improved by a factor of 10 with 25 zone passes (1-week
processing time) and at the cost of 20% of the initial material, or at the
same cost of material but with 50 zone passes (2-week processing time), the
average purity can be improved by a factor of 25. Therefore, for future NaI
crystals, the background due to 40K and 87Rb can be made subdominant compared
to the amplitude of the modulation.

Table 3:  Reduction of K for different numbers of passes and when different fractions of the ingot is reserved. No. of passes | Impurity reduction
---|---
Fraction of material retained
| 50% | 60% | 70% | 80% | 90%
10 | 0.3 | 0.36 | 0.42 | 0.48 | 0.56
25 | 0.03 | 0.050 | 0.07 | 0.11 | 0.25
50 | 0.001 | 0.0026 | 0.0086 | 0.037 | 0.18

Pb is more or less uniformly reduced by a factor of $\approx$3 without
following the typical impurity distribution of zone refining [35]. Although
one can still exploit this factor of 3, zone refining is not as efficient in
removing 210Pb. Thus we have started new R&D activity to explore alternative
purification methods and have achieved preliminary progress. Since the
analysis of data on the removal of Pb is still in progress, in this article,
we adopt the conservative reduction factor for 210Pb obtained from zone
refining alone.

With the aforementioned measures, a projected background rate of 0.21
cpd/kg/keV can be practically achieved in the future SABRE crystals (see Table
1). In this projection, we have assumed the contamination level of NaI-33 for
40K and bulk 210Pb scaled by the reduction factor of zone refining in Table 3.
For 210Pb in the reflector, we have assumed a contamination equal to the upper
limit for the PTFE measured in DarkSide-50. To suppress cosmogenic backgrounds
to a negligible level, we are also investigating the possibility of
establishing an underground crystal growth facility at the Canfranc Laboratory
in Spain [36].

To quantify the sensitivity to the dark matter-induced annual modulation, the
figure-of-merit (FoM) defined in [37] can be used where a small FoM indicates
a high sensitivity. In this framework, the DAMA/LIBRA phase II [38] has FoM
$=8\times 10^{-4}$ d-1kg-1keV-1. A similar value of FoM can be obtained with a
60 kg$\times$5 yr exposure and the predicted background rate of 0.21
cpd/kg/keV in Table 1. With the same exposure and background rate, the minimum
detectable rate [39] is expected to be $\leq(2\pm 1)\times 10^{-3}$ cpd/kg/keV
at 90% CL, which is about 5 times less than DAMA modulation amplitude of
$10.5\pm 1.1\times 10^{-3}$ cpd/kg/keV in 1-6 keV ROI [38]. On the other hand,
for the current generation of NaI(Tl) detector arrays, several decades are
needed to obtain the same FoM as DAMA/LIBRA phase II. Therefore, the present
results obtained from NaI-33 together with the planned improvements discussed
above will be fundamental for the next generation NaI-based dark matter
detectors.

The growth of NaI-33 and its characterization in the SABRE detector are a
breakthrough in the technology to support next-generation NaI experiments to
probe the long-standing DAMA result: the background rate in the 1-6 keV ROI is
determined to be $1.20\pm 0.05$ cpd/kg/keV, several times lower than all
presently running NaI-based experiments except DAMA. At present, the dominant
backgrounds are due to bulk 210Pb and 210Pb in the PTFE reflector. With a
combination of zone refining, special low-radioactivity PTFE tape, and
underground growth of crystals, the background in the ROI in future crystals
can be further reduced to $\leq 0.21$ cpd/kV/keV. This result marks a
significant improvement in the quest for testing the dark matter-induced
annual modulation, and paves the road to the next-generation NaI-based
experiments with higher sensitivities.

###### Acknowledgements.

This work has been supported by INFN funding and National Science Foundation
under the award number PHY-1242625, PHY-1506397 and PHY-1620085. We thank Ezio
Previtali, Andrea Giuliani, and Monica Sisti for discussions about PTFE
radiopurity in CUORE. We thank Fausto Ortica and Aldo Romani from Perugia
University for support in photospectrometric measurements. We thank the Gran
Sasso Laboratory for the support during the installation of the SABRE PoP
setup.

## References

  * Bertone and Hooper [2018] G. Bertone and D. Hooper, Reviews of Modern Physics 90, 045002 (2018).
  * Aprile  _et al._ [2018] E. Aprile, J. Aalbers, F. Agostini, M. Alfonsi, L. Althueser, F. Amaro, M. Anthony, F. Arneodo, L. Baudis, _et al._ , Physical Review Letters 121, 111302 (2018).
  * Akerib  _et al._ [2017] D. Akerib, S. Alsum, H. Araújo, X. Bai, A. Bailey, J. Balajthy, P. Beltrame, E. Bernard, A. Bernstein, T. Biesiadzinski, _et al._ , Physical Review Letters 118, 021303 (2017).
  * Cui  _et al._ [2017] X. Cui, A. Abdukerim, W. Chen, X. Chen, Y. Chen, B. Dong, D. Fang, C. Fu, K. Giboni, F. Giuliani, _et al._ , Physical Review Letters 119, 181302 (2017).
  * Agnes  _et al._ [2018a] P. Agnes, I. Albuquerque, T. Alexander, A. Alton, G. Araujo, M. Ave, H. Back, B. Baldin, G. Batignani, K. Biery, _et al._ , Physical Review D 98, 102006 (2018a).
  * Angloher  _et al._ [2012] G. Angloher, M. Bauer, I. Bavykina, A. Bento, C. Bucci, C. Ciemniak, G. Deuter, F. von Feilitzsch, D. Hauff, P. Huff, _et al._ , The European Physical Journal C 72, 1 (2012).
  * Aguilar-Arevalo  _et al._ [2020] A. Aguilar-Arevalo, D. Amidei, D. Baxter, G. Cancelo, B. C. Vergara, A. Chavarria, J. D’Olivo, J. Estrada, F. Favela-Perez, R. Gaior, _et al._ , Physical Review Letters 125, 241803 (2020).
  * Agnese  _et al._ [2018] R. Agnese, T. Aralis, T. Aramaki, I. Arnquist, E. Azadbakht, W. Baker, S. Banik, D. Barker, D. Bauer, T. Binder, _et al._ , Physical Review Letters 121, 051301 (2018).
  * Agnese  _et al._ [2019] R. Agnese, T. Aralis, T. Aramaki, I. Arnquist, E. Azadbakht, W. Baker, S. Banik, D. Barker, D. Bauer, T. Binder, _et al._ , Physical Review Letters 122, 069901 (2019).
  * Goodman and Witten [1985] M. W. Goodman and E. Witten, Physical Review D 31, 3059 (1985).
  * Drukier  _et al._ [1986] A. K. Drukier, K. Freese, and D. N. Spergel, Physical Review D 33, 3495 (1986).
  * Bernabei  _et al._ [2020] R. Bernabei _et al._ , Prog. Part. Nucl. Phys. 114, 103810 (2020).
  * Agnes  _et al._ [2018b] P. Agnes, I. Albuquerque, T. Alexander, A. Alton, G. Araujo, D. M. Asner, M. Ave, H. O. Back, B. Baldin, G. Batignani, _et al._ , Phys. Rev. Lett. 121, 081307 (2018b).
  * Amaré  _et al._ [2019a] J. Amaré, S. Cebrián, I. Coarasa, C. Cuesta, E. García, M. Martínez, M. Oliván, Y. Ortigoza, A. O. de Solórzano, J. Puimedón, _et al._ , The European Physical Journal C 79, 1 (2019a).
  * Adhikari  _et al._ [2018] G. Adhikari, P. Adhikari, E. B. de Souza, N. Carlin, S. Choi, W. Choi, M. Djamal, A. Ezeribe, C. Ha, I. Hahn, _et al._ , The European Physical Journal C 78, 1 (2018).
  * Amaré  _et al._ [2019b] J. Amaré, S. Cebrián, I. Coarasa, C. Cuesta, E. García, M. Martínez, M. Oliván, Y. Ortigoza, A. O. de Solórzano, J. Puimedón, _et al._ , Physical Review Letters 123, 031301 (2019b).
  * Adhikari  _et al._ [2019] G. Adhikari, P. Adhikari, E. B. de Souza, N. Carlin, S. Choi, M. Djamal, A. Ezeribe, C. Ha, I. Hahn, E. Jeon, _et al._ , Physical Review Letters 123, 031302 (2019).
  * Antonello  _et al._ [2019a] M. Antonello, E. Barberio, T. Baroncelli, J. Benziger, L. Bignell, I. Bolognino, F. Calaprice, S. Copello, D. D’angelo, G. D’imperio, _et al._ , The European Physical Journal C 79, 1 (2019a).
  * Suerfu  _et al._ [2020] B. Suerfu, M. Wada, W. Peloso, M. Souza, F. Calaprice, J. Tower, and G. Ciampi, Physical Review Research 2, 013223 (2020).
  * Antonello  _et al._ [2021] M. Antonello, I. Arnquist, E. Barberio, T. Baroncelli, J. Benziger, L. Bignell, I. Bolognino, F. Calaprice, S. Copello, I. Dafinei, _et al._ , The European Physical Journal C 81, 1 (2021).
  * Shields [2015] E. K. Shields,  _SABRE: A search for dark matter and a test of the DAMA/LIBRA annual-modulation result using thallium-doped sodium-iodide scintillation detectors_ , Ph.D. thesis, Princeton University (2015).
  * Suerfu [2018a] Suerfu,  _Developing Ultra-Low Background Sodium-Iodide Crystal Detector for Dark Matter Searches_ , Ph.D. thesis, Princeton University (2018a).
  * Bridgman [1925] P. Bridgman, in  _Proceedings of the American academy of arts and sciences_, Vol. 60 (JSTOR, 1925) pp. 305–383.
  * Suerfu [2018b] B. Suerfu, Journal of Instrumentation 13, T12004 (2018b).
  * Mariani [2021] A. Mariani,  _The Proof-of-Principle ot the SABRE experiment for the search of galactic dark matter through annual modulation_ , Ph.D. thesis, Gran Sasso Science Institute (2021).
  * Antonello  _et al._ [2019b] M. Antonello, E. Barberio, T. Baroncelli, J. Benziger, L. Bignell, I. Bolognino, F. Calaprice, S. Copello, D. D’Angelo, G. D’Imperio, _et al._ , Astroparticle Physics 106, 1 (2019b).
  * Amaré  _et al._ [2019c] J. Amaré, S. Cebrián, I. Coarasa, C. Cuesta, E. García, M. Martínez, M. Oliván, Y. Ortigoza, A. O. De Solórzano, J. Puimedón, _et al._ , The European Physical Journal C 79, 1 (2019c).
  * Adhikari  _et al._ [2021] G. Adhikari, P. Adhikari, E. B. de Souza, N. Carlin, J. Choi, S. Choi, M. Djamal, A. Ezeribe, L. Franca, C. Ha, _et al._ , arXiv preprint arXiv:2101.11377 (2021).
  * Alduino  _et al._ [2016] C. Alduino, K. Alfonso, D. Artusa, F. Avignone III, O. Azzolini, M. Balata, T. Banks, G. Bari, J. Beeman, F. Bellini, _et al._ , Journal of Instrumentation 11, P07009 (2016).
  * Alduino  _et al._ [2017] C. Alduino, K. Alfonso, D. Artusa, F. Avignone, O. Azzolini, T. Banks, G. Bari, J. Beeman, F. Bellini, A. Bersani, _et al._ , The European Physical Journal C 77, 1 (2017).
  * Agnes  _et al._ [2015] P. Agnes, T. Alexander, A. Alton, K. Arisaka, H. Back, B. Baldin, K. Biery, G. Bonfini, M. Bossa, A. Brigatti, _et al._ , Physics Letters B 743, 456 (2015).
  * Laubenstein and Meyer [2020] M. Laubenstein and P. Meyer, private communication (2020).
  * Zuzel  _et al._ [2017] G. Zuzel, K. Pelczar, and M. Wójcik, Applied Radiation and Isotopes 126, 165 (2017).
  * Amaré  _et al._ [2018] J. Amaré, J. Castel, S. Cebrián, I. Coarasa, C. Cuesta, T. Dafni, J. Galán, E. García, J. Garza, F. Iguaz, I. Irastorza, G. Luzón, M. Martínez, H. Mirallas, M. Oliván, Y. Ortigoza, A. Ortiz de Solórzano, J. Puimedón, E. Ruiz-Chóliz, M. Sarsa, J. Villar, and P. Villar, Astroparticle Physics 97, 96 (2018).
  * Suerfu  _et al._ [2021] B. Suerfu, F. Calaprice, and M. Souza, “Zone refining of ultra-high purity sodium iodide for low-background detectors,”  (2021), arXiv:2105.06431 [physics.ins-det] .
  * Ianni [2016] A. Ianni, Journal of Physics: Conference Series 675, 012002 (2016).
  * Coarasa  _et al._ [2019] I. Coarasa, J. Amaré, S. Cebrián, C. Cuesta, E. García, M. Martínez, M. Oliván, Y. Ortigoza, A. O. de Solórzano, J. Puimedón, _et al._ , The European Physical Journal C 79, 1 (2019).
  * Bernabei  _et al._ [2018] R. Bernabei, P. Belli, A. Bussolotti, F. Cappella, V. Caracciolo, R. Cerulli, C. Dai, A. d’Angelo, A. Di Marco, H. He, _et al._ , Nuclear Physics and Atomic Energy 19, 307 (2018).
  * Tsoulfanidis [2010] N. Tsoulfanidis,  _Measurement and detection of radiation_ (CRC press, 2010).


# I/O-Efficient Dynamic Planar Range Skyline Queries

Casper Kejlberg-Rasmussen
MADALGO
Department of Computer Science
Aarhus University, Denmark
<EMAIL_ADDRESS>Center for Massive Data Algorithmics - a Center of the
Danish National Research Foundation Konstantinos Tsakalidis
Computer Engineering and
Informatics Department
University of Patras, Greece
<EMAIL_ADDRESS>Kostas Tsichlas
Computer Science Department
Aristotle University
of Thessaloniki, Greece
<EMAIL_ADDRESS>
###### Abstract

We present the first fully dynamic worst case I/O-efficient data structures
that support planar orthogonal 3-sided range skyline reporting queries in
$\mathcal{O}(\log_{2B^{\epsilon}}n+\frac{t}{B^{1-\epsilon}})$ I/Os and updates
in $\mathcal{O}(\log_{2B^{\epsilon}}n)$ I/Os, using
$\mathcal{O}(\frac{n}{B^{1-\epsilon}})$ blocks of space, for $n$ input planar
points, $t$ reported points, and parameter $0\leq\epsilon\leq 1$. We obtain
the result by extending Sundar’s priority queues with attrition to support the
operations DeleteMin and CatenateAndAttrite in $\mathcal{O}(1)$ worst case
I/Os, and in $\mathcal{O}(1/B)$ amortized I/Os given that a constant number of
blocks is already loaded in main memory. Finally, we show that any pointer-
based static data structure that supports dominated maxima reporting queries,
namely the difficult special case of 4-sided skyline queries, in
$\mathcal{O}(\log^{\mathcal{O}(1)}n+t)$ worst case time must occupy
$\Omega(n\frac{\log n}{\log\log n})$ space, by adapting a similar lower
bounding argument for planar 4-sided range reporting queries.

##  1 Introduction

We study the problem of maintaining a set of planar points in external memory
subject to insertions and deletions of points in order to support planar
orthogonal 3-sided range skyline reporting queries efficiently in the worst
case. For two points $p,q\in\mathbb{R}^{d}$, we say that $p$ dominates $q$, if
and only if all the coordinates of $p$ are greater than those of $q$. The
skyline of a pointset $P$ consists of the maximal points of $P$, which are the
points in $P$ that are not dominated by any other point in $P$. Planar 3-sided
range skyline reporting queries that report the maximal points among the
points that lie

Skyline computation has been receiving increasing attention in the field of
databases since the introduction of the skyline operator for SQL [3]. Skyline
points correspond to the“interesting” entries of a relational database as they
are optimal simultaneously over all attributes. The considered variant of
planar skyline queries adds the capability of reporting the interesting
entries among those input entries whose attribute values belong to a given
3-sided range. Databases used in practical applications usually process
massive amounts of data in dynamic environments, where the data can be
modified by update operations. Therefore we analyze our algorithms in the I/O
model [1], which is commonly used to capture the complexity of massive data
computation. It assumes that the input data resides in the disk (external
memory) divided in blocks of $B$ consecutive words, and that computation
occurs for free in the internal memory of size $M$ words. An I/O-operation
(I/O) reads a block of data from the disk into the internal memory, or writes
a block of data to the disk. Time complexity is expressed in number of I/Os,
and space complexity in the number of blocks that the input data occupies on
the disk.

#### Previous Results

Different approaches have been proposed for maintaining the $d$-dimensional
skyline in external memory under update operations, assuming for example
offline updates over data streams [19, 13], only online deletions [20], online
average case updates [16], arbitrary online updates [8] and online updates
over moving input points [9]. The efficiency of all previous approaches is
measured experimentally in terms of disk usage over average case data.
However, even for the planar case, no I/O-efficient structure exists that
supports both arbitrary insertions and deletions in sublinear worst case I/Os.
Regarding internal memory, Brodal and Tsakalidis [4] present two linear space
dynamic data structures that support 3-sided range skyline reporting queries
in $\mathcal{O}(\log n+t)$ and $\mathcal{O}(\frac{\log n}{\log\log n}+t)$
worst case time, and updates in $\mathcal{O}(\log n)$ and
$\mathcal{O}(\frac{\log n}{\log\log n})$ worst case time in the pointer
machine and the RAM model, respectively, where $n$ is the input size and $t$
is the output size. They also present an $\mathcal{O}(n\log n)$ space dynamic
pointer-based data structure that supports 4-sided range skyline reporting
queries in $\mathcal{O}(\log^{2}n+t)$ worst case time and updates in
$\mathcal{O}(\log^{2}n)$ worst case time. Adapting these structures to the I/O
model attains $\mathcal{O}(\log^{\mathcal{O}(1)}_{B}n+t)$ query I/Os, which is
undesired since $\mathcal{O}(1)$ I/Os are spent per reported point.

Regarding the static variant of the problem, Sheng and Tao [17] obtain an
I/O-efficient algorithm that computes the skyline of a static $d$-dimensional
pointset in $\mathcal{O}(\frac{n}{B}\log^{d-2}_{\frac{M}{B}}\frac{n}{B})$
worst case I/Os, for $d\geq 3$, by adapting the internal memory algorithms of
[12, 2] to external memory.
$\mathcal{O}(\frac{n}{B}\log_{\frac{M}{B}}\frac{n}{B})$ I/Os can be achieved
for the planar case. There exist two $\mathcal{O}(n\log n)$ and
$\mathcal{O}(n\frac{\log n}{\log\log n})$ space static data structures that
support planar 4-sided range skyline reporting queries in $\mathcal{O}(\log
n+t)$ and $\mathcal{O}(\frac{\log n}{\log\log n}+t)$ worst case time, for the
pointer machine and the RAM, respectively [10, 7].

#### Our Results

In Section 3 we present the basic building block of the structures for dynamic
planar range skyline reporting queries that we present in Section 4. That is
pointer-based I/O-efficient catenable priority queues with attrition
(I/O-CPQAs) that support the operations DeleteMin and CatenateAndAttrite in
$\mathcal{O}(1/B)$ amortized I/Os and in $\mathcal{O}(1)$ worst case I/Os,
using $\mathcal{O}(\frac{n-m}{B})$ disk blocks, after $n$ calls to
CatenateAndAttrite and $m$ calls to DeleteMin. The result is obtained by
modifying appropriately a proposed implementation for priority queues with
attrition of Sundar [18].

In Section 4 we present our main result, namely I/O-efficient dynamic data
structures that support 3-sided range skyline reporting queries in
$\mathcal{O}(\log_{2B^{\epsilon}}n+\frac{t}{B^{1-\epsilon}})$ worst case I/Os
and updates in $\mathcal{O}(\log_{2B^{\epsilon}}n)$ worst case I/Os, using
$\mathcal{O}(\frac{n}{B^{1-\epsilon}})$ blocks, for a parameter
$0\leq\epsilon\leq 1$. These are the first fully dynamic skyline data
structures for external memory that support all operations in polylogarithmic
worst case time. The results are obtained by following the approach of
Overmars and van Leeuwen [14] for planar skyline maintainance and utilizing
confluently persistent I/O-CPQAs (implemented with functional catenable deques
[11]). Applying the same methodology to internal memory pointer-based CPQAs
yields alternative implementations for dynamic 3-sided reporting in the
pointer machine in the same bounds as in [4].

Finally, in Section 5 we prove that any pointer-based static data structure
that supports reporting the maximal points among the points that are dominated
by a given query point in $\mathcal{O}(\log^{\mathcal{O}(1)}n)$ worst case
time must occupy $\Omega(n\frac{\log n}{\log\log n})$ space, by adapting the
similar lower bounding argument of Chazelle [5] for planar 4-sided range
reporting queries to the considered dominated skyline reporting queries. These
queries are termed as dominating minima reporting queries. The symmetric case
of dominated maxima reporting queries is equivalent and comprises a special
case of rectangular visibilty queries [15] and 4-sided range skyline reporting
queries [4, 10]. The result shows that the space usage of the pointer-based
structures in [15, 4, 10] is optimal within a $\mathcal{O}(\log\log n)$
factor, for the attained query time.

##  2 Preliminaries

#### Priority Queues with Attrition

Sundar [18] introduces pointer-based _priority queues with attrition (PQAs)_
that support the following operations in $\mathcal{O}(1)$ worst case time on a
set of elements drawn from a total order: DeleteMin deletes and returns the
minimum element from the PQA, and InsertAndAttrite($e$) inserts element $e$
into the PQA and removes all elements larger than $e$ from the PQA. PQAs use
space linear to the number of inserted elements minus the number of elements
removed by DeleteMin.

#### Functional Catenable Deques

A dynamic data structure is persistent when it maintains its previous versions
as update operations are performed on it. It is fully persistent when it
permits accessing and updating the previous versions. In turn, it is called
confluently persistent when it is fully persistent, and moreover it allows for
two versions to be combined into a new version, by use of an update operation
that merges the two versions. In this case, the versions form a directed
acyclic version graph. A catenable deque is a list that stores a set of
elements from a total order, and supports the operations Push and Inject that
insert an element to the head and tail of the list respectively, Pop and Eject
that remove the element from the head and tail of the list respectively, and
Catenate that concatenates two lists into one. Kaplan and Tarjan [11] present
purely functional catenable deques that are confluently persistent and support
the above operations in $\mathcal{O}(1)$ worst case time.

#### Searching Lower Bound in the Pointer Machine

In the pointer machine model a data structure that stores a data set $S$ and
supports range reporting queries for a query set $\mathcal{Q}$, can be
modelled as a directed graph $G$ of bounded out-degree. In particular, every
node in $G$ may be assigned an element of $S$ or may contain some other useful
information. For a query range $Q_{i}\in\mathcal{Q}$, the algorithm navigates
over the edges of $G$ in order to locate all nodes that contain the answer to
the query. The algorithm may also traverse other nodes. The time complexity of
reporting the output of $Q_{i}$ is at least equal to the number of nodes
accessed in graph $G$ for $Q_{i}$. To prove a lower bound we need to construct
hard instances with particular properties, as discussed by Chazelle and Liu
[5, 6]. In particular, they define the graph $G$ to be
$(\alpha,\omega)$-effective, if a query is supported in $\alpha(t+\omega)$
time, where $t$ is the output size, $\alpha$ is a multiplicative factor for
the output size ($\alpha=\mathcal{O}(1)$ for our purposes) and $\omega$ is the
additive factor. They also define a query set $\mathcal{Q}$ to be
$(m,\omega)$-favorable for a data set $S$, if $|S\cap Q_{i}|\geq\omega,\forall
Q_{i}\in\mathcal{Q}$ and $|S\cap Q_{i_{1}}\cap\cdots\cap
Q_{i_{m}}|=\mathcal{O}(1),\forall i_{1}<i_{2}\cdots<i_{m}$. Intuitively, the
first part of this property requires that the size of the output is large
enough (at least $\omega$) so that it dominates the additive factor of
$\omega$ in the time complexity. The second part requires that the query
outputs have minimum overlap, in order to force $G$ to be large without many
nodes containing the output of many queries. The following lemma exploits
these properties to provide a lower bound on the minimum size of $G$.

######  Lemma 2.1.

[6, Lemma 2.3] For an $(m,\omega)$-favorable graph $G$ for the data set $S$,
and for an $(\alpha,\omega)$-effective set of queries $\mathcal{Q}$, $G$
contains $\Omega(|\mathcal{Q}|\omega/m)$ nodes, for constant $\alpha$ and for
any large enough $\omega$.

##  3 I/O-Efficient Catenable Priority Queues with Attrition

In this Section, we present I/O-efficient catenable priority queues with
attrition (I/O-CPQAs) that store a set of elements from a total order in
external memory, and support the following operations:

FindMin($Q$) returns the minimum element in I/O-CPQA $Q$.

DeleteMin($Q$) removes the minimum element $e$ from I/O-CPQA $Q$ and returns
element $e$ and the new I/O-CPQA $Q^{\prime}=Q\backslash\\{e\\}$.

CatenateAndAttrite($Q_{1},Q_{2}$) concatenates I/O-CPQA $Q_{2}$ to the end of
I/O-CPQA $Q_{1}$, removes all elements in $Q_{1}$ that are larger than the
minimum element in $Q_{2}$, and returns a new I/O-CPQA $Q^{\prime}_{1}=\\{e\in
Q_{1}|e<\min(Q_{2})\\}\cup Q_{2}$. We say that the removed elements have been
_attrited_.

InsertAndAttrite($Q,e$) inserts element $e$ at the end of $Q$ and attrites all
elements in $Q$ that are larger than the value of $e$.

All operations take $\mathcal{O}(1)$ worst case I/Os and $\mathcal{O}(1/b)$
amortized I/Os, given that a constant number of blocks is already loaded into
main memory, for a parameter $1\leq b\leq B$. To achieve the result, we modify
an implementation for the PQAs of Sundar [18].

An I/O-CPQA $Q$ consists of $k_{Q}+2$ deques of records, called the clean
deque $C(Q)$, the buffer deque $B(Q)$ and the dirty deques
$D_{1}(Q),\ldots,D_{k_{Q}}(Q)$, where $k_{Q}\geq 0$. A _record_ $r=(l,p)$
consists of a buffer $l$ of $[b,4b]$ elements of strictly increasing value and
a pointer $p$ to an I/O-CPQA. The ordering of $r$ is; first all elements of
$l$ and then all elements of the I/O-CPQA pointed to by $p$. We define the
queue order of $Q$ to be $C(Q)$, $B(Q)$ and $D_{1}(Q),\ldots,D_{k_{Q}}(Q)$. A
record is _simple_ when its pointer $p$ is _null_. The clean deque and the
buffer deque only contains simple records. See Figure 1 for an overview of the
structure.

$\ldots$$C(Q)$$\ldots$$B(Q)$$\ldots$$D_{1}(Q)$$\ldots$$D_{k_{Q}-1}(Q)$$\ldots$$D_{k_{Q}}(Q)$$\ldots$
Figure 1: A I/O CPQA $Q$ consists of $k_{Q}+2$ deques of records;
$C(Q),B(Q),D_{1}(Q),\ldots,D_{k_{Q}}(Q)$. The records in $C(Q)$ and $B(Q)$ are
simple, the records of $D_{1}(Q),\ldots,D_{k_{Q}}(Q)$ may contain pointers to
other I/O CPQA’s. Gray recordsare always loaded in memory.

Given a record $r=(l,p)$ the minimum and maximum elements in the buffers of
$r$, are denoted by $\min(r)=\min(l)$ and $\max(r)=\max(l)$, respectively.
They appear respectively first and last in the queue order of $l$, since the
buffer of $r$ is sorted by value. Henceforth, we do not distinguish between an
element and its value. Given a deque $q$ the first and the last record is
denoted by $\text{first}(q)$ and $\text{last}(q)$, respectively. Also
$\text{rest}(q)$ denotes all records of the deque $q$ excluding the record
$\text{first}(q)$. Similarly, $\text{front}(q)$ denotes all records for the
deque $q$ excluding the record $\text{last}(q)$. The size $|r|$ of a record
$r$ is defined to be the number of elements in its buffer. The size $|q|$ of a
deque $q$ is defined to be the number of records it contains. The size $|Q|$
of the I/O-CPQA $Q$ is defined to be the number of elements that $Q$ contains.
For an I/O-CPQA $Q$ we denote by $\text{first}(Q)$ and $\text{last}(Q)$, the
first and last of the records in $C(Q),B(Q),D_{1}(Q),\ldots,D_{k_{Q}}(Q)$ that
exists, respectively. By $\text{middle}(Q)$ we denote all records in $Q$ and
the records in the I/O-CPQAs pointed by $Q$, except for records
$\text{first}(Q)$ and $\text{last}(Q)$ and the I/O-CPQAs they point to. We
call an I/O-CPQA $Q$ _large_ if $|Q|\geq b$ and _small_ otherwise. The minimum
value of all elements stored in the I/O-CPQA $Q$ is denote by $\min(Q)$. For
an I/O-CPQA $Q$ we maintain the following invariants:

  1. I.1)

For every record $r=(l,p)$ where pointer $p$ points to I/O-CPQA $Q^{\prime}$,
$\max(l)<\min(Q^{\prime})$ holds.

  2. I.2)

In all deques of $Q$, where record $r_{1}=(l_{1},p_{1})$ precedes record
$r_{2}=(l_{2},p_{2})$, $\max(l_{1})<\min(l_{2})$ holds.

  3. I.3)

For the deques $C(Q),B(Q)$ and $D_{1}(Q)$,
$\max(\text{last}(C(Q)))<\min(\text{first}(B(Q)))<\min(\text{first}(D_{1}(Q)))$
holds.

  4. I.4)

Element $\min(\text{first}(D_{1}(Q)))$ has the minimum value among all the
elements in the dirty deques $D_{1}(Q),\ldots,D_{k}(Q)$.

  5. I.5)

All records in the deques $C(Q)$ and $B(Q)$ are simple.

  6. I.6)

$|C(Q)|\geq\sum_{i=1}^{k_{Q}}{|D_{i}(Q)|}+k_{Q}-1$.

  7. I.7)

$|\text{first}(C(Q))|<b$ holds, if and only if $|Q|<b$ holds.

  8. I.8)

$|\text{last}(D_{k_{Q}}(Q))|<b$ holds, if and only if record
$\text{last}(D_{k_{Q}}(Q))$ is simple. In this case $|r|\in[b,5b]$ holds.

From Invariants I.2, I.3 and I.4, we have that the minimum element $\min(Q)$
stored in the I/O-CPQA $Q$ is element $\min(\text{first}(C(Q)))$. We say that
an operation improves or aggravates by a parameter $c$ the inequality of
invariant I.6 for I/O-CPQA $Q$, when the operation increases or decreases
$\Delta(Q)=|C(Q)|-\sum_{i=1}^{k_{Q}}{|D_{i}(Q)|}-k_{Q}+1$ by $c$,
respectively. To argue about the $\mathcal{O}(1/b)$ amortized I/O bounds we
define the following potential functions for large and small I/O-CPQAs. In
particular, for large I/O-CPQAs $Q$, the potential $\Phi(Q)$ is defined as

$\Phi(Q)=\Phi_{F}(|\text{first}(Q)|)+|\text{middle}(Q)|+\Phi_{L}(|\text{last}(Q)|),$

where

$\begin{array}[]{ccc}{\Phi_{F}(x)=\left\\{\begin{array}[]{cl}3-\frac{x}{b},&b\leq
x<2b\\\ 1,&2b\leq x<3b\\\ \frac{2x}{b}-5,&3b\leq x\leq 4b\\\
\end{array}\right.}&\text{and}&{\Phi_{L}(x)=\left\\{\begin{array}[]{cl}0,&0\leq
x<4b\\\ \frac{3x}{b}-12,&4b\leq x\leq 5b\\\ \end{array}\right.}\end{array}$

For small I/O-CPQAs $Q$, the potential $\Phi(Q)$ is defined as

$\Phi(Q)=\frac{3|Q|}{b}$

The total potential $\Phi_{T}$ is defined as

$\Phi_{T}=\sum_{Q}{\Phi(Q)}+\sum_{Q|b\leq|Q|}{1},$

where the first sum is over all I/O-CPQAs $Q$ and the second sum is only over
all large I/O-CPQAs $Q$.

###  3.1 Operations

In the following, we describe the algorithms that implement the operations
supported by the I/O-CPQA $Q$. The operations call the auxiliary operation
Bias$(Q)$, which will be described last, that improves the inequality of
invariant I.6 for $Q$ by at least $1$. All operations take $\mathcal{O}(1)$
worst case I/Os. We also show that every operation takes $\mathcal{O}(1/b)$
amortized I/Os, where $1\leq b\leq B$.

####  FindMin($Q$)

returns the value $\min(\text{first}(C(Q)))$.

####  DeleteMin($Q$)

removes element $e=\min(\text{first}(C(Q)))$ from record
$(l,p)=\text{first}(C(Q))$. After the removal, if $|l|<b$ and $|Q|\geq b$
hold, we do the following. If $b\leq|\text{first}(\text{rest}(C(Q)))|\leq 2b$,
then we merge $\text{first}(C(Q))$ with $\text{first}(\text{rest}(C(Q)))$ into
one record which is the new first record. Else if
$2b<|\text{first}(\text{rest}(C(Q)))|\leq 3b$ then we take $b$ elements out of
$\text{first}(\text{rest}(C(Q)))$ and put them into $\text{first}(C(Q))$. Else
we have that $3b<|\text{first}(\text{rest}(C(Q)))|$, and as a result we take
$2b$ elements out of $\text{first}(\text{rest}(C(Q)))$ and put them into
$\text{first}(C(Q))$. If the inequality for $Q$ is aggravated by $1$ we call
Bias($Q$) once. Finally, element $e$ is returned.

Amortization: Only if the size of $\text{first}(C(Q))$ becomes
$|\text{first}(C(Q))|=b-1$ do we incur any I/Os. In this case
$r=\text{first}(Q)$ has a potential of $\Phi_{F}(|r|)=2$, and since we
increase the number of elements in $r$ by $b$ to $2b$ elements, the potential
of $r$ will then only be $\Phi_{F}(|r|)=1$. Thus, the total potential
decreases by $1$, which also pays for any I/Os including those incurred if
Bias$(Q)$ is invoked.

####  CatenateAndAttrite($Q_{1},Q_{2}$)

concatenates $Q_{2}$ to the end of $Q_{1}$ and removes the elements from
$Q_{1}$ with value larger than $\min(Q_{2})$. To do so, it creates a new
I/O-CPQA $Q^{\prime}_{1}$ by modifying $Q_{1}$ and $Q_{2}$, and by calling
Bias($Q^{\prime}_{1}$) and Bias($Q_{2}$).

If $|Q_{1}|<b$, then $Q_{1}$ is only one record $(l_{1},\cdot)$, and so we
prepend it into the first record $(l_{2},\cdot)=\text{first}(Q_{2})$ of
$Q_{2}$. Let $l_{1}^{\prime}$ be the non-attrited elements of $l_{1}$. We
perform the prepend as follows. If $|l_{1}^{\prime}|+|l_{2}|\leq 4b$, then we
prepend $l_{1}^{\prime}$ into $l_{2}$. Else, we take $2b-|l_{1}^{\prime}|$
elements out of $l_{2}$, and make them along with $l_{1}^{\prime}$ the new
first record of $Q_{2}$.

Amortization: If we simply prepend $l_{1}^{\prime}$ into $l_{2}$, then the
potential $\Phi_{S}(|l_{1}|)$ pays for the increase in potential of
$\Phi_{F}(|\text{first}(C(Q_{2}))|)$. Else, we take $2b-|l_{1}^{\prime}|$
elements out of $l_{2}$, and these elements along with $l_{1}^{\prime}$ become
the new first record of $Q_{2}$ of size $2b$. Thus, $\Phi_{F}(2b)=1$ and the
potential drops by $1$, which is enough to pay for the I/Os used to flush the
old first record of $C(Q_{2})$ to disk.

If $|Q_{2}|<b$, then $Q_{2}$ only consists of one record. We have two cases,
depending on how much of $Q_{1}$ is attrited by $Q_{2}$. Let $r_{1}$ be the
second last record for $Q_{1}$ and let $r_{2}=\text{last}(Q_{1})$ be the last
record. If $e$ attrites all of $r_{1}$, then we just pick the appropriate case
among (1–4) below. Else if $e$ attrites partially $r_{1}$, but not all of it,
then we delete $r_{2}$ and we merge $r_{1}$ and $Q_{2}$ into the new last
record of $Q_{1}$, which cannot be larger than $5b$. Otherwise if $e$ attrites
partially $r_{2}$, but not all of it, then we simply append the single record
of $Q_{2}$ into $r_{2}$, which will be the new last record of $Q_{1}$ and it
cannot be larger than $5b$.

Amortization: If $e$ attrites all of $r_{1}$, then we release at least $1$ in
potential, so all costs in any of the cases (1–4) are paid for. If $e$
attrites partially $r_{1}$, then the new record cannot contain more than $5b$
elements, and thus any increase in potential is paid for by the potential of
$Q_{2}$. Thus, the I/O cost is covered by the decrease of $1$ in potential,
caused by $r_{1}$. If $e$ attrites partially $r_{2}$, any increase in
potential is paid for by the potential of $Q_{2}$.

We have now dealt with the case where $Q_{1}$ is a small queue, so in the
following we assume that $Q_{1}$ is large. Let $e=\min(Q_{2})$.

  1. 1)

If $e\leq\min(\text{first}(C(Q_{1})))$, we discard I/O-CPQA $Q_{1}$ and set
$Q^{\prime}_{1}=Q_{2}$.

  2. 2)

Else if $e\leq\max(\text{last}(C(Q_{1})))$, we remove the simple record
$(l,\cdot)=\text{first}(C(Q_{2}))$ from $C(Q_{2})$, we set
$C(Q^{\prime}_{1})=\emptyset$, $B(Q^{\prime}_{1})=C(Q_{1})$ and
$D_{1}(Q^{\prime}_{1})=(l,p)$, where $p$ points to $Q_{2}$, if it exists. This
aggravates the inequality for $Q_{2}$ by at most $1$, and gives
$\Delta(Q^{\prime}_{1})=-1$. Thus, we call Bias$(Q_{2})$ once and
Bias$(Q^{\prime}_{1})$ once.

  3. 3)

Else if $e\leq\min(\text{first}(B(Q_{1})))$ or
$e\leq\min(\text{first}(D_{1}(Q_{1})))$ holds, we remove the simple record
$(l,\cdot)=\text{first}(C(Q_{2}))$ from $C(Q_{2})$, set
$D_{1}(Q^{\prime}_{1})=(l,p)$, and make $p$ point to $Q_{2}$, if it exists. If
$e\leq\min(\text{first}(B(Q_{1})))$, we set $B(Q_{1}^{\prime})=\emptyset$.
This aggravates the inequality for $Q_{2}$ by at most $1$, and aggravates the
inequality for $Q_{1}$ by at most $1$. Thus, we call Bias$(Q_{2})$ once and
Bias$(Q^{\prime}_{1})$ once.

  4. 4)

Else, let $(l_{1},\cdot)=\text{last}(D_{k_{Q_{1}}})$. We remove
$(l_{2},\cdot)=\text{first}(C(Q_{2}))$ from $C(Q_{2})$. If $|l_{1}|<b$, then
remove the record $(l_{1},\cdot)$ from $D_{k_{Q_{1}}}$. Let $l_{1}^{\prime}$
be the non-attrited elements under attrition by $e=\min(l_{2})$. If
$|l_{1}^{\prime}|+|l_{2}|\leq 4b$, then we prepend $l_{1}^{\prime}$ into
$l_{2}$ of record $r_{2}=(l_{2},p_{2})$, where $p_{2}$ points to $Q_{2}$.
Otherwise. we make a new simple record $r_{1}$ with $l_{1}^{\prime}$ and $2b$
elements taken out of $r_{2}=(l_{2},p_{2})$. Finally, we put the resulting one
or two records $r_{1}$ and $r_{2}$ into a new deque $D_{k_{Q_{1}}+1}(Q_{1})$.
This aggravates the inequality for $Q_{2}$ by at most $1$, and the inequality
for $Q_{1}$ by at most $2$. Thus, we call Bias$(Q_{2})$ once and
Bias$(Q^{\prime}_{1})$ twice.

Amortization: In all the cases (1–4) both $Q_{1}$ and $Q_{2}$ are large, hence
when we concatenate them we decrease the potential by at least $1$, as the
number of large I/O-CPQA’s decrease by one which is enough to pay for any Bias
operations.

####  InsertAndAttrite($Q$, $e$)

inserts an element $e$ into I/O-CPQA $Q$ and attrites the elements in $Q$ with
value larger than $e$. This is a special case of operation
CatenateAndAttrite($Q_{1}$,$Q_{2}$), where $Q_{1}=Q$ and $Q_{2}$ is an
I/O-CPQA that only contains one record with the single element $e$.

Amortization: Since creating a new I/O-CPQA with only one element and calling
CatenateAndAttrite only costs $\mathcal{O}(1/b)$ I/Os amortized, the operation
InsertAndAttrite also costs $\mathcal{O}(1/b)$ I/Os amortized.

$\ldots$$C(Q)$$\ldots$$D_{1}(Q)$$\ldots$$C(Q^{\prime})$$\ldots$$B(Q^{\prime})$$\ldots$$D_{1}(Q^{\prime})$$\ldots$$D_{k_{Q^{\prime}}}(Q^{\prime})$$\ldots$
Figure 2: In the case of Bias$(Q)$, where $B(Q)=\emptyset$ and $k_{Q}=1$, we
need to follow the pointer $p$ of $(l,p)=\text{first}(D_{1}(Q))$ that may
point to an I/O-CPQA $Q^{\prime}$. If so, we merge it into $Q$, taking into
account attrition of $Q^{\prime}$ by $e=\min(\text{first}(D_{1}(Q)))$.

#### Bias$(Q)$

improves the inequality in I.6 for $Q$ by at least $1$.

Amortization: Since all I/Os incurred by Bias$(Q)$ are already paid for by the
operation that called Bias$(Q)$, we only need to argue that the potential of
$Q$ does not increase due to the changes that Bias$(Q)$ makes to $Q$.

  1. 1)

$|B(Q)|>0$: We remove the first record $\text{first}(B(Q))=(l_{1},\cdot)$ from
$B(Q)$ and let $(l_{2},p_{2})=\text{first}(D_{1}(Q))$. Let $l_{1}^{\prime}$ be
the non-attrited elements of $l_{1}$ under attrition from $e=\min(l_{2})$.

    1. 1)

$0\leq|l_{1}^{\prime}|<b$: If $|l_{2}|\leq 2b$, then we just prepend
$l_{1}^{\prime}$ onto $l_{2}$. Else, we take $b$ elements out of $l_{2}$ and
append them to $l_{1}^{\prime}$.

    2. 2)

$b\leq|l_{1}^{\prime}|<2b$: If $|l_{2}|\leq 2b$, and if furthermore
$|l_{1}^{\prime}|+|l_{2}|\leq 3b$ holds, then we merge $l_{1}^{\prime}$ and
$l_{2}$. Else $|l_{1}^{\prime}|+|l_{2}|>3b$ holds, so we take $2b$ elements
out of $l_{1}^{\prime}$ and $l_{2}$ and put them into $l_{1}^{\prime}$,
leaving the rest in $l_{2}$.

Else $|l_{2}|>2b$ holds, so we take $b$ elements out of $l_{2}$ and put them
into $l_{1}^{\prime}$.

If we did not prepend $l_{1}^{\prime}$ onto $l_{2}$, we insert
$l_{1}^{\prime}$ along with any elements taken out of $l_{2}$ at the end of
$C(Q)$ instead. If $|l_{1}^{\prime}|<|l_{1}|$, we set $B(Q)=\emptyset$. Else,
we did prepend $l_{1}^{\prime}$ onto $l_{2}$, and then we just recursively
call Bias. Since $|B(Q)|=0$ we will not end up in this case again. As a
result, in all cases the inequality of $Q$ is improved by $1$.

Amortization: If $l_{1}=\text{first}(Q)$, then after calling Bias we ensure
that $2b\leq|\text{first}(Q)|\leq 3b$, and so the that potential of $Q$ does
not increase.

  2. 2)

$|B(Q)|=0$: When $|B(Q)|=0$ holds, we have two cases depending on the number
of dirty queues, namely cases $k_{Q}>1$ and $k_{Q}=1$.

    1. 1)

$k_{Q}>1$: Let $e=\min(\text{first}(D_{k_{Q}}(Q)))$. If
$e\leq\min(\text{last}(D_{k_{Q}-1}(Q)))$ holds, we remove the record
$\text{last}(D_{k_{Q}-1}(Q))$ from $D_{k_{Q}-1}(Q)$. This improves the
inequality of $Q$ by $1$.

Else, if
$\min(\text{last}(D_{k_{Q}-1}(Q)))<e\leq\max(\text{last}(D_{k_{Q}-1}(Q)))$
holds, we remove record $r_{1}=(l_{1},p_{1})=\text{last}(D_{k_{Q}-1}(Q))$ from
$D_{k_{Q}-1}(Q)$ and let $r_{2}=(l_{2},p_{2})=\text{first}(D_{k_{Q}}(Q))$. We
delete any elements in $l_{1}$ that are attrited by $e$, and let
$l_{1}^{\prime}$ denote the non-attrited elements.

      1. 1)

$0\leq|l_{1}^{\prime}|<b$: If $|l_{2}|\leq 2b$, then we just prepend
$l_{1}^{\prime}$ onto $l_{2}$. Otherwise, we take $b$ elements out of $l_{2}$
and append them to $l_{1}^{\prime}$.

      2. 2)

If $b\leq|l_{1}^{\prime}|<2b$: If $|l_{2}|\leq 2b$ and
$|l_{1}^{\prime}|+|l_{2}|\leq 3b$, then we merge $l_{1}^{\prime}$ and $l_{2}$.
Else, $|l_{1}^{\prime}|+|l_{2}|>3b$ holds, so we take $2b$ elements out of
$l_{1}^{\prime}$ and $l_{2}$ and put them into $l_{1}^{\prime}$, leaving the
rest in $l_{2}$.

Else $|l_{2}|>2b$, so we take $b$ elements out of $l_{2}$ and put them into
$l_{1}^{\prime}$.

If $r_{1}$ still exists, we insert it in the front of $D_{k_{Q}}(Q)$. Finally,
we concatenate $D_{k_{Q}-1}(Q)$ and $D_{k_{Q}}(Q)$ into one deque. This
improves the inequality of $Q$ by at least $1$.

Else $\max(\text{last}(D_{k_{Q}-1}(Q)))<e$ holds, and we just concatenate the
deques $D_{k_{Q}-1}(Q)$ and $D_{k_{Q}}(Q)$, which improves the inequality for
$Q$ by $1$.

Amortization: If not all of $l_{1}$ is attrited then we ensure that its record
$r_{1}$ has size between $2b$ and $3b$. Thus, if $r_{1}=\text{first}(Q)$
holds, we will not have increased the potential of $Q$. In the cases where all
or none of $l_{1}$ is attrited, the potential of $Q$ can only be decreased by
at least $0$.

    2. 2)

$k_{Q}=1$: In this case $Q$ contains only deques $C(Q)$ and $D_{1}(Q)$. We
remove the record $r=(l,p)=\text{first}(D_{1}(Q))$ and insert $l$ into a new
record at the end of $C(Q)$. This improves the inequality of $Q$ by at least
$1$. If $r$ is not simple, let $r$’s pointer $p$ point to I/O-CPQA
$Q^{\prime}$. We restore I.5 for $Q$ by merging I/O-CPQAs $Q$ and $Q^{\prime}$
into one I/O-CPQA. See Figure 2 for this case of operation Bias. In
particular, let $e=\min(\text{first}(D_{1}(Q)))$, we now proceed as follows:

If $e\leq\min(Q^{\prime})$, we discard $Q^{\prime}$. The inequality for $Q$
remains unaffected.

Else, if
$\min(\text{first}(C(Q^{\prime})))<e\leq\max(\text{last}(C(Q^{\prime}))$, we
set $B(Q)=C(Q^{\prime})$ and discard the rest of $Q^{\prime}$. The inequality
for $Q$ remains unaffected.

Else if
$\max(\text{last}(C(Q^{\prime}))<e\leq\min(\text{first}(D_{1}(Q^{\prime})))$,
we concatenate the deque $C(Q^{\prime})$ at the end of $C(Q)$. If moreover
$\min(\text{first}(B(Q^{\prime})))<e$ holds, we set $B(Q)=B(Q^{\prime})$.
Finally, we discard the rest of $Q^{\prime}$. This improves the inequality for
$Q$ by $|C(Q^{\prime})|$.

Else $\min(\text{first}(D_{1}(Q^{\prime})))<e$ holds. We concatenate the deque
$C(Q^{\prime})$ at the end of $C(Q)$, we set $B(Q)=B(Q^{\prime})$, we set
$D_{1}(Q^{\prime}),\ldots,D_{k_{Q^{\prime}}}(Q^{\prime})$ as the first
$k_{Q^{\prime}}$ dirty queues of $Q$ and we set $D_{1}(Q)$ as the last dirty
queue of $Q$. This improves the inequality for $Q$ by $\Delta(Q^{\prime})\geq
0$, since $Q^{\prime}$ satisfied I.6 before the operation.

If $r=\text{first}(Q)$ and $|l|\leq 2b$, then we remove $r$ and run Bias
recursively. Let $r^{\prime}=(l^{\prime},p^{\prime})=\text{first}(Q)$. If
$|l|+|l^{\prime}|>3b$, then we take the $2b$ first elements out and make them
the new first record of $C(Q)$. Else we merge $l$ into $l^{\prime}$, so that
$r$ is removed and $r^{\prime}$ is now $\text{first}(Q)$.

Amortization: Since $\text{first}(Q)$ is either untouched or left with $2b$ to
$3b$ elements, in which case its potential is $1$, and since all other changes
decrease the potential by at least $0$, we have that Bias does not increase
the potential of $Q$.

######  Theorem 3.1.

A set of $\ell$ I/O-CPQA’s can be maintained supporting the operations
FindMin, DeleteMin, CatenateAndAttrite and InsertAndAttrite in
$\mathcal{O}(1/b)$ I/Os amortized and $\mathcal{O}(1)$ worst case I/Os per
operation. The space usage is $\mathcal{O}(\frac{n-m}{b})$ blocks after
calling CatenateAndAttrite and InsertAndAttrite $n$ times and DeleteMin $m$
times, respectively. We require that $M\geq\ell b$ for $1\leq b\leq B$, where
$M$ is the main memory size and $B$ is the block size.

###### Proof.

The correctness follows by closely noticing that we maintain invariants
I.1–I.8, and from those we have that DeleteMin$(Q)$ and FindMin$(Q)$ always
returns the minimum element of $Q$.

The worst case I/O bound of $\mathcal{O}(1)$ is trivial as every operation
only touches $\mathcal{O}(1)$ records. Although Bias is recursive, we notice
that in the case where $|B(Q)|>0$, Bias only calls itself after making
$|B(Q)|=0$, so it will not end up in this case again. Similarly, if $|B(Q)|=0$
and $k_{Q}>1$ there might also be a recursive call to Bias. However, before
the call at least $b$ elements have been taken out of $Q$, and thus the
following recursive call to Bias will ensure at least $b$ more are taken out.
This is enough to stop the recursion, which will have depth at most $3$.

The $\mathcal{O}(1/b)$ amortized I/O bounds, follows from the potential
analysis made throughout the description of each operation. ∎

###  3.2 Concatenating a Sequence of I/O-CPQAs

We describe how to CatenateAndAttrite I/O-CPQAs $Q_{1},Q_{2},\ldots,Q_{\ell}$
into a single I/O-CPQA in $\mathcal{O}(1)$ worst case I/Os, given that
DeleteMin is not called in the sequence of operations. We moreover impose two
more assumptions. In particular, we say that I/O-CPQA $Q$ is in state
$x\in\mathbb{Z}$, if $|C(Q)|=\sum_{i=1}^{k_{Q}}{|D_{i}(Q)|}+k_{Q}-1+x$ holds.
Positive $x$ implies that Bias$(Q)$ will be called after the inequality for
$Q$ is aggravated by $x+1$. Negative $x$ implies that Bias$(Q)$ need to be
called $x$ operations times in order to restore inequality for $Q$. So, we
moreover assume that I/O-CPQAs $Q_{i},i\in[1,\ell]$ are at state at least
$+2$, unless $Q_{i}$ contains only one record in which case it may be in state
$+1$. We call a record $r=(l,p)$ in an I/O-CPQA $Q_{i}$ critical, if $r$ is
accessed at some time during the sequence of operations. In particular, the
critical records for $Q_{i}$ are
$\text{first}(C(Q_{i})),\text{first}(\text{rest}(C(Q_{i}))),\text{last}(C(Q_{i})),\text{first}(B(Q_{i})),\text{first}(D_{1}(Q_{i})),\text{last}(D_{k_{Q_{i}}}(Q_{i}))$,
and $\text{last}(\text{front}(D_{k_{Q_{i}}}(Q_{i})))$ if it exists. Otherwise,
record $\text{last}(D_{k_{Q_{i}}-1}(Q_{i}))$ is critical. So, we moreover
assume that the critical records for I/O-CPQAs $Q_{i},i\in[1,\ell]$ are loaded
into memory.

The algorithm considers I/O-CPQAs $Q_{i}$ in decreasing index $i$ (from right
to left). It sets $Q^{i}=Q_{\ell}$ and constructs the temporary I/O-CPQA
$Q^{i-1}$ by calling CatenateAndAttrite($Q_{i-1}$,$Q^{i}$). This yields the
final I/O-CPQA $Q^{1}$.

######  Lemma 3.1.

I/O-CPQAs $Q_{i},i\in[1,\ell]$ can be CatenateAndAttrited into a single
I/O-CPQA without any access to external memory, provided that:

  1. 1.

$Q_{i}$ is in state at least $+2$, unless it contains only one record, in
which case its state is at least $+1$,

  2. 2.

all critical records of all $Q_{i}$ reside in main memory.

###### Proof.

To avoid any I/Os during the sequence of CatenateAndAttrites, we ensure that
Bias is not called, and that the critical records are sufficient, and thus no
more records need to be loaded into memory.

To avoid calling Bias we prove by induction the invariant that the temporary
I/O-CPQAs $Q^{i},i\in[1,\ell]$ constructed during the sequence are in state at
least $+1$. Let the invariant hold of $Q^{i+1}$ and let $Q^{i}$ be constructed
by CatenateAndAttrite($Q_{i}$,$Q^{i+1}$). If $Q_{i}$ contains at most two
records, which both reside in dequeue $C(Q_{i})$, we only need to access
record $\text{first}(C(Q^{i+1}))$ and the at most two records of $Q_{i}$. The
invariant holds for $Q^{i}$, since it holds inductively for $Q^{i+1}$ and the
new records were added at $C(Q^{i+1})$. As a result, the inequality of I.6 for
$Q^{i+1}$ can only be improved. If $Q^{i+1}$ consists of only one record, then
either one of the following cases apply or we follow the steps described in
operation CatenateAndAttrite. In the second case, there is no aggravation for
the inequality of 6 and only critical records are used.

In the following, we can safely assume that $Q_{i}$ has at least three records
and its state is at least $+2$. We parse the cases of the CatenateAndAttrite
algorithm assumming that $e=\min(Q^{i+1})$.

  * Case 1

The invariant holds trivially since $Q_{i}$ is discarded and no change happens
to $Q^{i}=Q^{i+1}$. Bias is not called.

  * Cases 2,3

The algorithm checks whether the first two records of $C(Q_{i})$ are attrited
by $e$. If this is the case, we continue as denoted at the start of this
proof. Otherwise, case 2 of CatenateAndAttrite is applied as is. $Q^{i+1}$ is
in state $0$ after the concatenation and $Q^{i}$ is in state $+1$. Thus the
invariant holds, and Bias is not. Note that all changes take place at the
critical records of $Q_{i}$ and $Q^{i+1}$.

  * Case 4

The algorithm works exactly as in case 4 of CatenateAndAttrite, with the
following exception. At the end, $Q^{i}$ will be in state $0$, since we added
the deque $D_{k_{Q^{i+1}}+1}$ with a new record and the inequality of I.6 is
aggrevated by $2$. To restore the invariant we apply case 2(1) of Bias. This
step requires access to records $\text{last}(D_{k_{Q^{i}}-1})$ and
$\text{first}(D_{k_{Q^{i}}})$. These records are both critical, since the
former corresponds to $\text{last}(D_{k_{Q^{i+1}}})$ and the latter to
$\text{first}C(Q^{i+1})$. In addition, Bias$(Q^{i+1})$ need not be called,
since by the invariant, $Q^{i+1}$ was in state $+1$ before the removal of
$\text{first}C(Q^{i+1})$. In this way, we improve the inequality for $Q^{i}$
by $1$ and invariant holds.

∎

##  4 Dynamic Planar Range Skyline Reporting

In this Section we present dynamic I/O-efficient data structures that support
3-sided planar orthogonal range skyline reporting queries.

#### 3-Sided Skyline Reporting

We describe how to utilize I/O-CPQAs in order to obtain dynamic data
structures that support 3-sided range skyline reporting queries and arbitrary
insertions and deletions of points, by modifying the approach of [14] for the
pointer machine model. In particular, let $P$ be a set of $n$ points in the
plane, sorted by $x$-coordinate. To access the points, we store their
$x$-coordinates in an $(a,2a)$-tree $T$ with branching parameter $a\geq 2$ and
leaf parameter $k\geq 1$. In particular, every node has degree within $[a,2a]$
and every leaf contains at most $k$ consecutive by $x$-coordinate input
points. Every internal node $u$ of $T$ is associated with an I/O-CPQA whose
non-attrited elements correspond to the maximal points among the points stored
in the subtree of $u$. Moreover, $u$ contains a representative block with the
critical records of condition 2 in Lemma 3.1 for the I/O-CPQAs associated with
its children nodes.

To construct the structure, we proceed in a bottom up manner. First, we
compute the maximal points among the points contained in every leaf of $T$. In
particular for every leaf, we initialize an I/O-CPQA $Q$. We consider the
points $(p_{x},p_{y})$ stored in the block in increasing $x$-coordinate, and
call InsertAndAttrite($Q,-p_{y}$). In this way, a point $p$ in the block that
is dominated by another point $q$ in the block, is inserted before $q$ in $Q$
and has value $-p_{y}>-q_{y}$. Therefore, the dominated points in the block
correspond to the attrited elements in $Q$.

We construct the I/O-CPQA for an internal node $u$ of $T$ by concatenating the
already constructed I/O-CPQAs $Q_{i}$ at its children nodes $u_{i}$ of $u$,
for $i\in[1,a]$ in Section 3. Then we call Bias to the resulting I/O-CPQA
appropriately many times in order to satisfy condition 1 in Lemma 3.1. The
procedure ends when the I/O-CPQA is constructed for the root of $T$. Notice
that the order of concatenations follows implicitly the structure of the tree
$T$. To insert (resp. delete) a point $p=(p_{x},p_{y})$ to the structure, we
first insert (resp. delete) $p_{x}$ to $T$. This identifies the leaf with the
I/O-CPQA that contains $p$. We discard all I/O-CPQAs from the leaf to the root
of $T$, and recompute them in a bottom up manner, as described above.

To report the skyline among the points that lie within a given 3-sided query
rectangle $[x_{\ell},x_{r}]\times[y_{b},+\infty)$, it is necessary to obtain
the maximal points in a subtree of a node $u$ of $T$ by querying the I/O-CPQA
stored in $u$. Notice, however, that computing the I/O-CPQA of an internal
node of $T$ modifies the I/O-CPQAs of its children nodes. Therefore, we can
only report the skyline of all points stored in $T$, by calling DeleteMin at
the I/O-CPQA stored in the root of $T$. The rest of the I/O-CPQAs in $T$ are
not queriable in this way, since the corresponding nodes do not contain the
version of their I/O-CPQA, before it is modified by the construction of the
I/O-CPQA for their parent nodes. For this reason we render the involved
I/O-CPQAs confluently persistent, by implementing their clean, buffer and
dirty deques as purely functional catenable deques [11]. In fact, $T$ encodes
implicity the directed acyclic version graph of the confluently persistent
I/O-CPQAs, by associating every node of $T$ with the version of the I/O-CPQA
at the time of its construction. Every internal node of $T$ stores a
representative block with the critical records for the versions of the
I/O-CPQAs associated with its children nodes. Finally, the update operation
discards the I/O-CPQA of a node in $T$, by performing in reverse the
operations on the purely functional catenable deques involved in the
construction of the I/O-CPQA (undo operation).

With the above modification it suffices for the query operation to identify
the two paths $p_{\ell},p_{r}$ from the root to the leaves of $T$ that contain
the $x$-successor point of $x_{\ell}$ and the $x$-predecessor point of
$x_{r}$, respectively. Let $R$ be the children nodes of the nodes on the paths
$p_{\ell}$ and $p_{r}$ that do not belong to the paths themselves, and also
lie within the query $x$-range. The subtrees of $R$ divide the query $x$-range
into disjoint $x$-ranges. We consider the nodes of $R$ from left to right. In
particular, for every non-leaf node in $p_{\ell}\cup p_{r}$, we load into
memory the representative blocks of the versions of the I/O-CPQAs in its
children nodes that belong to $R$. We call CatenateAndAttrite on the loaded
I/O-CPQAs and on the resulting I/O-CPQAs for every node in $p_{\ell}\cup
p_{r}$, as decribed in Section 3. The non-attrited elements in the resulting
auxiliary I/O-CPQA correspond to the skyline of the points in the query
$x$-range, that are not stored in the leaves of $p_{\ell}$ and $p_{r}$. To
report the output points of the query in increasing $x$-coordinate, we first
report the maximal points within the query range among the points stored in
the leaf of $p_{\ell}$. Then we call DeleteMin to the auxiliary I/O-CPQA that
returns the maximal points in increasing $x$-coordinate, and thus also in
decreasing $y$-coordinate, and thus we terminate the reporting as soon as a
skyline point with $y$-coordinate smaller than $y_{b}$ is returned. If the
reporting has not terminated, we also report the rest of the maximal points
within the query range that are contained in the leaf of $p_{r}$.

######  Theorem 4.1.

There exist I/O-efficient dynamic data structures that store a set of $n$
planar points and support reporting the $t$ skyline points within a given
3-sided orthogonal range unbounded by the positive $y$-dimension in
$\mathcal{O}(\log_{2B^{\epsilon}}n+t/B^{1-\epsilon})$ worst case I/Os, and
updates in $\mathcal{O}(\log_{2B^{\epsilon}}n)$ worst case I/Os, using
$\mathcal{O}(n/B^{1-\epsilon})$ disk blocks, for a parameter
$0\leq\epsilon\leq 1$.

###### Proof.

We set the buffer size parameter $b$ of the I/O-CPQAs equal to the leaf
parameter $k$ of $T$, and we set the parameters $a=2B^{\epsilon}$ and
$k=B^{1-\epsilon}$ for $0\leq\epsilon\leq 1$. In this way, for a node of $T$,
the representative blocks for all of its children nodes can be loaded into
memory in $\mathcal{O}(1)$ I/Os. Since every operation supported by an
I/O-CPQA involves a $\mathcal{O}(1)$ number of deque operations, I/O-CPQAs can
be made confluently persistent without deteriorating their I/O and space
complexity. Moreover, the undo operation takes $\mathcal{O}(1)$ worst case
I/Os, since the purely functional catenable deques are worst case efficient.

Therefore by Theorem 3.1, an update operation takes
$\mathcal{O}(\log_{2B^{\epsilon}}\frac{n}{B^{1-\epsilon}})=\mathcal{O}(\log_{2B^{\epsilon}}n)$
worst case I/Os. Lemma 3.1 takes $\mathcal{O}(1)$ I/Os to construct the
temporary I/O-CPQAs for every node in the search paths, since they satisfy
both of its conditions. Moreover, by Theorem 3.1, it takes
$\mathcal{O}(\frac{\log_{2B^{\epsilon}}n}{B^{1-\epsilon}})$ I/Os to catenate
them together. Thus, the construction of the auxiliary query I/O-CPQA takes
$\mathcal{O}(\log_{2B^{\epsilon}}n)$ worst case I/Os in total. Moreover, it
takes $\mathcal{O}(1+t/B^{1-\epsilon})$ worst case I/Os to report the output
points. There are $\mathcal{O}(\frac{n}{B^{1-\epsilon}})$ internal nodes in
$T$, and every internal node contains $\mathcal{O}(1)$ blocks. ∎

#### 4-Sided Skyline Reporting

Dynamic I/O-efficient data structures for 4-sided range skyline reporting
queries can be obtained by following the approach of Overmars and Wood for
dynamic rectangular visibility queries [15]. In particular, 4-sided range
skyline reporting queries are supported in $\mathcal{O}(\frac{a\log^{2}n}{\log
a\log{2B^{\epsilon}}}+t/B^{1-\epsilon})$ worst case I/Os, using
$\mathcal{O}(\frac{n}{B^{1-\epsilon}}\log_{a}n)$ blocks, by employing our
structure for 3-sided range skyline reporting as a secondary structure on a
dynamic range tree with branching parameter $a$, built over the $y$-dimension.
Updates are supported in $\mathcal{O}(\frac{\log^{2}n}{\log
a\log{2B^{\epsilon}}})$ worst case I/Os, since the secondary structures can be
split or merged in $\mathcal{O}(\log_{2B^{\epsilon}}n)$ worst case I/Os.

######  Remark 4.1.

In the pointer machine, the above constructions attains the same complexities
as the existing structures for dynamic 3-sided and 4-sided range maxima
reporting [4], by setting the buffer size, branching and leaf parameter to
$\mathcal{O}(1)$.

##  5 Lower Bound for Dominating Minima Reporting

Let $S$ be a set of $n$ points in $\mathbb{R}^{2}$. Let
$\mathcal{Q}=\\{Q_{i}\\}$ be a set of $m$ orthogonal 2-sided query ranges
$Q_{i}\in\mathbb{R}^{2}$. Range $Q_{i}$ is the subspace of $\mathbb{R}^{2}$
that dominates a given point $q_{i}\in\mathbb{R}^{2}$ in the positive $x$\-
and $y$\- direction (the “upper-right” quadrant defined by $q_{i}$). Let
$S_{i}=S\cap Q_{i}$ be the set of all points in $S$ that lie in the range
$Q_{i}$. A dominating minima reporting query $Q_{i}$ contains the points
$\min(S_{i})\in S_{i}$ that do not dominate any other point in $S_{i}$. In
this section we prove that any pointer-based data structure that supports
dominating minima queries in $\mathcal{O}(\log^{\mathcal{O}(1)}{n}+t)$ time,
must use superlinear space. This separates the problem from the easier problem
of supporting dominating maxima queries and the more general 3-sided range
skyline reporting queries. The same trade-off also holds for the symmetric
dominated maxima reporting queries that are the simplest special case of
4-sided range skyline reporting queries that demands superlinear space.
Moreover, the lower bound holds trivially for the I/O model, if no address
arithmetic is being used. In particular, for a query time of
$\mathcal{O}(\frac{\log^{\mathcal{O}(1)}{n}}{B}+\frac{t}{B})$ the data
structure must definitely use
$\Omega(\frac{n}{B}\frac{\log{n}}{\log{\log{n}}})$ blocks of space. In the
following, we prove the lower bound for the dominating minima reporting
queries.

Henceforth, we use the terminology presented in Section 2. Without loss of
generality, we assume that $n=\omega^{\lambda}$, since this restriction
generates a countably infinite number of inputs and thus the lower bound is
general. In our case, $\omega=\log^{\gamma}{n}$ holds for some $\gamma\>0$,
$m=2$ and
$\lambda=\left\lfloor\frac{\log{n}}{1+\gamma\log{\log{n}}}\right\rfloor$. Let
$\rho_{\omega}(i)$ be the integer obtained by writing $0\leq i<n$ using
$\lambda$ digits in base $\omega$, by first reversing the digits and then
taking their complement with respect to $\omega$. In particular, if
$i=i^{(\omega)}_{0}i^{(\omega)}_{1}\ldots i^{(\omega)}_{\lambda-1}$ holds,
then

$\rho_{\omega}(i)=(\omega-i^{(\omega)}_{\lambda-1}-1)(\omega-i^{(\omega)}_{\lambda-2}-1)\ldots(\omega-i^{(\omega)}_{1}-1)(\omega-i^{(\omega)}_{0}-1)$

where $i^{(\omega)}_{j}$ is the $j$-th digit of number $i$ in base $\omega$.
We define the points of $S$ to be the set $\\{(i,\rho_{\omega}(i))|0\leq
i<n\\}$. Figure 3 shows an example with $\omega=4$, $\lambda=2$.

To define the query set $\mathcal{Q}$, we encode the set of points
$\\{\rho_{\omega}(i)|0\leq i<n\\}$ in a full trie structure of depth
$\lambda$. Recall that $n=\omega^{\lambda}$. Notice that the trie structure is
implicit and it is used only for presentation purposes. Input points
correspond to the leaves of the trie and their $y$ value is their label at the
edges of the trie. Let $v$ be an internal node at depth $d$ (namely, $v$ has
$d$ ancestors), whose prefix $v_{0},v_{1},\ldots,v_{d-1}$ corresponds to the
path from $v$ to the root $r$ of the trie. We take all points in its subtree
and sort them by $y$. From this sorted list we construct groups of size
$\omega$ by always picking each $\omega^{\lambda-d-1}$-th element starting
from the smallest non-picked element. Each such group corresponds to the
output of each query. See Figure 3 for an example. In this case, we say that
the query is associated to node $v$.

Figure 3: An example for $\omega=4$ and $\lambda=2$. Two examples of queries
are shown, out of the $8$ possible queries with different output. Connecting
lines represent points whose $L_{1}$ distance is $\omega^{k},1\leq
k\leq\lambda$. All $8$ possible queries can be generated by translating the
blue lines horizontally so that the answers of all $4$ queries are disjoint.
Similarly for the red lines with the exception that we translate them
vertically.

A node of with depth $d$ has $\frac{n}{\omega^{d}}$ points in its subtree and
thus it defines at most $\frac{n}{\omega^{d-1}}$ queries. Thus, the total
number of queries is:

$\left|\mathcal{Q}\right|=\sum_{d=0}^{\lambda-1}{\omega^{d}\frac{n}{\omega^{d+1}}}=\sum_{d=0}^{\lambda-1}{\frac{n}{\omega}}=\frac{\lambda
n}{\omega}$

This means that the total number of queries is

$|\mathcal{Q}|=\frac{\lambda
n}{\omega}=\frac{\log{n}}{1+\gamma\log{\log{n}}}\frac{1}{\log^{\gamma}{n}}n=\frac{n}{\log^{\gamma-1}{n}(1+\gamma\log{\log{n}})}$

The following lemma states that $\mathcal{Q}$ is appropriate for our purposes.

######  Lemma 5.1.

$\mathcal{Q}$ is $(2,\log^{\gamma}{n})$-favorable.

###### Proof.

First we prove that we can construct the queries so that they have output size
$\omega=\log^{\gamma}{n}$. Assume that we take a group of $\omega$ consecutive
points in the sorted order of points with respect to the $y$-coordinate at the
subtree of node $v$ at depth $d$. These have common prefix of length $d$. Let
the $y$-coordinates of these points be
$\rho_{\omega}(i_{1}),\rho_{\omega}(i_{2}),\ldots,\rho_{\omega}(i_{\omega})$
in increasing order, where
$\rho_{\omega}(i_{j})-\rho_{\omega}(i_{j-1})=\omega^{\lambda-d-1},1<j\leq\omega$.
This means that these numbers differ only at the $\lambda-d-1$-th digit. This
is because they have a common prefix of length $d$ since all points lie in the
subtree of $v$. At the same time they have a common suffix of length
$\lambda-d-1$ because of the property that
$\rho_{\omega}(i_{j})-\rho_{\omega}(i_{j-1})=\omega^{\lambda-d-1},1<j\leq\omega$
which comes as a result from the way we chose these points. By inversing the
procedure to construct these $y$-coordinates, the corresponding
$x$-coordinates $i_{j},1\leq j\leq\omega$ are determined. By complementing we
take the increasing sequence
$\bar{\rho}_{\omega}(i_{\omega}),\ldots,\bar{\rho}_{\omega}(i_{2}),\bar{\rho}_{\omega}(i_{1})$,
where $\bar{\rho}_{\omega}(i_{j})=\omega^{\lambda}-\rho_{\omega}(i_{j})-1$ and
$\bar{\rho}_{\omega}(i_{j-1})-\bar{\rho}_{\omega}(i_{j})=\omega^{\lambda-d-1},1<j\leq\omega$.
By reversing the digits we finally get the increasing sequence of
$x$-coordinates $i_{\omega},\ldots,i_{2},i_{1}$, since the numbers differ at
only one digit. Thus, the group of $\omega$ points are decreasing as the
$x$-coordinates increase, and as a result a query $q$ whose horizontal line is
just below $\rho_{\omega}(i_{1})$ and the vertical line just to the left of
$\rho_{\omega}(i_{\omega})$ will certainly contain this set of points in the
query. In addition, there cannot be any other points between this sequence and
the horizontal or vertical lines defining query $q$. This is because all
points in the subtree of $v$ have been sorted with respect to $y$, while the
horizontal line is positioned just below $\rho_{\omega}(i_{1})$, so that no
other element lies in between. In the same manner, no points to the left of
$\rho_{\omega}(i_{\omega})$ exist, when positioning the vertical line of $q$
appropriately. Thus, for each query $q\in\mathcal{Q}$, it holds that $|S\cap
q|=\omega=\log^{\gamma}{n}$.

It is enough to prove that for any two query ranges $p,q\in\mathcal{Q}$,
$|S\cap q\cap p|\leq 1$ holds. Assume that $p$ and $q$ are associated to nodes
$v$ and $u$, respectively, and that their subtrees are disjoint. That is, $u$
is not a proper ancestor or descendant of $v$. In this case, $p$ and $q$ share
no common point, since each point is used only once in the trie. For the other
case, assume without loss of generality that $u$ is a proper ancestor of $v$
($u\neq v$). By the discussion in the previous paragraph, each query contains
$\omega$ numbers that differ at one and only one digit. Since $u$ is a proper
ancestor of $v$, the corresponding digits will be different for the queries
defined in $u$ and for the queries defined in $v$. This implies that there can
be at most one common point between these sequences, since the digit that
changes for one query range is always set to a particular value for the other
query range. The lemma follows. ∎

Lemma 5.1 allows us to apply Lemma 2.1, and thus the query time of
$\mathcal{O}(\log^{\gamma}{n}+t)$, for output size $t$, can only be achieved
at a space cost of $\Omega\left(n\frac{\log{n}}{\log{\log{n}}}\right)$. The
following theorem summarizes the result of this section.

######  Theorem 5.1.

The dominating minima reporting problem can be solved with
$\Omega\left(n\frac{log{n}}{\log{\log{n}}}\right)$ space, if the query is
supported in $\mathcal{O}(\log^{\gamma}{n}+t)$ time, where $t$ is the size of
the answer to the query and parameter $\gamma=\mathcal{O}(1)$.

##  6 Conclusion

We presented the first dynamic I/O-efficient data structures for 3-sided
planar orthogonal range skyline reporting queries with worst case
polylogarithmic update and query complexity. We also showed that the space
usage of the existing structures for 4-sided range skyline reporting in
pointer machine is optimal within doubly logarithmic factors.

It remains open to devise a dynamic I/O-efficient data structure that supports
reporting all $m$ planar skyline points in $\mathcal{O}(m/B)$ worst case I/Os
and updatess in $\mathcal{O}(\log_{B}n)$ worst case I/Os. It seems that the
hardness for reporting the skyline in optimal time is derived from the fact
that the problem is dynamic. The dynamic indexability model of Yi [21] may be
useful to prove a lower bound towards the direction of rendering our structure
for 3-sided range skyline reporting I/O-optimal, as defined by Papadias et
al.[16]. Finally it remains open to obtain a
$\mathcal{O}(\frac{n}{B}\log_{B}n)$ space dynamic I/O-efficient data
structures for 4-sided range skyline reporting with
$\mathcal{O}(\log^{2}_{B}n)$ worst case query and update I/Os, regardless of
the I/O-complexity per reported point.

## References

  * [1] Alok Aggarwal and S. Vitter, Jeffrey.  The input/output complexity of sorting and related problems.  Commun. ACM, 31(9):1116–1127, 1988.
  * [2] Jon Louis Bentley.  Multidimensional divide-and-conquer.  Commun. ACM, 23(4):214–229, April 1980.
  * [3] Stephan Börzsönyi, Donald Kossmann, and Konrad Stocker.  The skyline operator.  In ICDE, pages 421–430, 2001.
  * [4] Gerth Brodal and Konstantinos Tsakalidis.  Dynamic planar range maxima queries.  In Luca Aceto, Monika Henzinger, and Jirí Sgall, editors, Automata, Languages and Programming, volume 6755 of Lecture Notes in Computer Science, pages 256–267. Springer Berlin / Heidelberg, 2011.  10.1007/978-3-642-22006-7_22.
  * [5] Bernard Chazelle.  Lower bounds for orthogonal range searching: I. the reporting case.  J. ACM, 37(2):200–212, April 1990.
  * [6] Bernard Chazelle and Ding Liu.  Lower bounds for intersection searching and fractional cascading in higher dimension.  Journal of Computer and System Sciences, 68(2):269 – 284, 2004\.  ¡ce:title¿Special Issue on STOC 2001¡/ce:title¿.
  * [7] Ananda Das, Prosenjit Gupta, Anil Kalavagattu, Jatin Agarwal, Kannan Srinathan, and Kishore Kothapalli.  Range aggregate maximal points in the plane.  In Md. Rahman and Shin-ichi Nakano, editors, WALCOM: Algorithms and Computation, volume 7157 of Lecture Notes in Computer Science, pages 52–63. Springer Berlin / Heidelberg, 2012.  10.1007/978-3-642-28076-4_8.
  * [8] Yu-Ling Hsueh, Roger Zimmermann, and Wei-Shinn Ku.  Efficient updates for continuous skyline computations.  In DEXA, pages 419–433, 2008.
  * [9] Zhiyong Huang, Hua Lu, Beng Chin Ooi, and Anthony K. H. Tung.  Continuous skyline queries for moving objects.  IEEE Trans. Knowl. Data Eng., 18(12):1645–1658, 2006.
  * [10] Anil Kishore Kalavagattu, Ananda Swarup Das, Kishore Kothapalli, and Kannan Srinathan.  On finding skyline points for range queries in plane.  In CCCG, 2011.
  * [11] Haim Kaplan and Robert E. Tarjan.  Purely functional, real-time deques with catenation.  J. ACM, 46(5):577–603, September 1999.
  * [12] H. T. Kung, Fabrizio Luccio, and Franco P. Preparata.  On finding the maxima of a set of vectors.  J. ACM, 22(4):469–476, 1975.
  * [13] Michael D. Morse, Jignesh M. Patel, and William I. Grosky.  Efficient continuous skyline computation.  Inf. Sci., 177(17):3411–3437, 2007.
  * [14] Mark H. Overmars and Jan van Leeuwen.  Maintenance of configurations in the plane.  Journal of Computer and System Sciences, 23(2):166 – 204, 1981\.
  * [15] Mark H. Overmars and Derick Wood.  On rectangular visibility.  J. Algorithms, 9(3):372–390, September 1988.
  * [16] Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger.  Progressive skyline computation in database systems.  ACM Trans. Database Syst., 30(1):41–82, 2005.
  * [17] Cheng Sheng and Yufei Tao.  On finding skylines in external memory.  In Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS ’11, pages 107–116, New York, NY, USA, 2011. ACM.
  * [18] Rajamani Sundar.  Worst-case data structures for the priority queue with attrition.  Inf. Process. Lett., 31:69–75, April 1989.
  * [19] Yufei Tao and Dimitris Papadias.  Maintaining sliding window skylines on data streams.  IEEE Trans. on Knowl. and Data Eng., 18(3):377–391, 2006.
  * [20] Ping Wu, Divyakant Agrawal, Ömer Egecioglu, and Amr El Abbadi.  Deltasky: Optimal maintenance of skyline deletions without exclusive dominance region generation.  In ICDE, pages 486–495, 2007.
  * [21] Ke Yi.  Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes.  In Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS ’09, pages 187–196, New York, NY, USA, 2009. ACM.