# Upgrade of the ALICE ITS detector

F. Reidt
on behalf of the ALICE collaboration CERN, 1211 Geneva 23, Switzerland
<EMAIL_ADDRESS>
###### Abstract

The ALICE experiment at CERN has undergone a major upgrade during the Long
Shutdown 2 of the LHC during 2019-2021. A key element is the installation of
the new Inner Tracking System 2 (ITS2). The new ITS2 based on CMOS Monolithic
Active Pixel Sensors will significantly improve the impact parameter
resolution and the tracking efficiency, especially for particles with low
transverse momenta, as well as the readout-rate capability. In the following,
the upgrade and its commissioning status as well installation status will be
outlined.

###### keywords:

Silicon Pixel Detector , MAPS , ALPIDE , Vertex Detector

††journal: Nuclear Instruments and Methods A

##  1 Introduction

The ALICE experiment [1] has been upgrading its experimental apparatus during
the currently ongoing Long Shutdown 2 (LS2) of the LHC during 2019 to 2021.
This upgrade [2] rests on two pillars: the recording Pb–Pb collision data at
$50\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$ interaction rate to increase the
minimum-bias data sample by about a factor of one hundred, the increased
vertexing capabilities while maintaining previous particle identification
performance. This is motivated by high-precision measurements of rare probes
at low transverse momentum ($p_{\textrm{T}}$).

##  2 Inner Tracking System 2 (ITS2)

The upgraded Inner Tracking System 2 (ITS2) is a key element of upgrade of the
experimental apparatus of the ALICE experiment. The main goals of the ITS2
upgrade are to achieve an improved reconstruction of the primary vertex as
well as decay vertices originating from heavy-flavour hadrons, and an improved
performance for the detection of low-$p_{\textrm{T}}$ particles. The design
objectives of ITS2 are the following ones:

  1. 1.

The impact parameter resolution will improve by a factor of 3 and 5 in the
$r\varphi$ and $z$ coordinate, respectively, at a $p_{\textrm{T}}$ of
$500\text{\,}\mathrm{M}\mathrm{eV}\mathrm{/}\mathit{c}$ by three main changes:

     * (a)

moving the detector closer to the interaction point from previously
$39\text{\,}\mathrm{m}\mathrm{m}$ to $23\text{\,}\mathrm{m}$m for the
innermost layer;

     * (b)

reducing the material budget of the inner layers to
$0.35\text{\,}\mathrm{\char 37\relax}~{}\mathrm{X}_{0}$ compared to
$1.14\text{\,}\mathrm{\char 37\relax}~{}\mathrm{X}_{0}$ of its predecessor;

     * (c)

reducing the pixel size from $$50\text{\,}\mathrm{\SIUnitSymbolMicro
m}$\times$425\text{\,}\mathrm{\SIUnitSymbolMicro m}$$ to
$$29.24\text{\,}\mathrm{\SIUnitSymbolMicro
m}$\times$26.88\text{\,}\mathrm{\SIUnitSymbolMicro m}$$.

  2. 2.

The tracking efficiency and the $p_{\textrm{T}}$ resolution at low
$p_{\textrm{T}}$ will improve through the increased granularity of the 7
layer, fully pixelated detector.

  3. 3.

The readout rate will be increased from
$1\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$ up to
$100\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$ in Pb–Pb and
$200\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$ in pp collisions.

\begin{overpic}[width=216.81pt]{LayoutNewITS.jpg}
\put(0.0,100.0){\footnotesize Beam pipe} \put(810.0,490.0){\footnotesize Outer
layers} \put(750.0,420.0){\footnotesize Middle layers}
\put(780.0,320.0){\footnotesize Inner layers} \end{overpic} Figure 1: ITS2
layout, taken from [3].

The layout of the detector is depicted in Fig. 1. The radii of the concentric
layers range from $23\text{\,}\mathrm{mm}400\text{\,}\mathrm{mm}$. A total of
192 staves form an active silicon area of $10\text{\,}{\mathrm{m}}^{2}$
amounting to
$12.5\text{\times}{10}^{9}\text{\,}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{s}$.
The innermost three layers form the so-called Inner Barrel (IB) containing 48
staves of $27\text{\,}\mathrm{cm}$ length. The Outer Barrel (OB) consists of
the Middle Layers (MLs) and Outer Layers (OLs) which are assembled from 54 and
90 staves of $84\text{\,}\mathrm{cm}$ and $150\text{\,}\mathrm{cm}$,
respectively.

The principal component of the ITS2 is the ALPIDE chip [4], a Monolithic
Active Pixel Sensor (MAPS) fabricated in the TowerJazz
$180\text{\,}\mathrm{nm}$ CMOS Imaging Process. A deep p-well allows to employ
complex logic inside the pixel matrix without having the n-wells PMOS
transistors compete with the collection electrodes (cf. Fig. 2). Therefore,
ALPIDE features in-pixel amplification, shaping and discrimination as well
multiple-event buffers. A priority-encoder circuit is employed to read only
the addresses of hit-pixels and achieve in-matrix data-sparsification. The key
characteristics of ALPIDE are summarised in Tab. 1.

Table 1: ALPIDE pixel-chip characteristics. Parameter | Value
---|---
Chip dimensions |  $$15\text{\,}\mathrm{mm}$\times$30\text{\,}\mathrm{mm}$$ ($r\varphi\times z$)
Spatial resolution | $5\text{\,}\mathrm{\SIUnitSymbolMicro m}$
Detection efficiency |  $>$ $99\text{\,}\%$
Fake-hit rate |  $\ll$$1\text{\times}{10}^{-6}\text{\,}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{/}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}$
Power density |  $<$ $40\text{\,}\mathrm{m}\mathrm{W}\mathrm{/}\mathrm{c}\mathrm{m}\mathrm{{}^{2}}$
TID radiation hardness |  $>$$270\text{\,}\mathrm{k}\mathrm{r}\mathrm{a}\mathrm{d}$
NIEL radiation hardness |  $>$$1.7\text{\times}{10}^{12}\text{\,}$\mathrm{missing}\mathrm{revert_as}\mathrm{=}{presentation}\mathrm{]}{\text{\,}1\mathrm{M}\mathrm{e}\mathrm{V}~{}\mathrm{n}_{eq}\mathrm{/}\mathrm{c}\mathrm{m}\mathrm{{}^{2}}}{1\text{\,}\mathrm{M}\mathrm{e}\mathrm{V}~{}\mathrm{n}_{eq}\mathrm{/}\mathrm{c}\mathrm{m}\mathrm{{}^{2}}}$$
Figure 2: Schematic cross section of a pixel of a monolithic active silicon
pixel sensor using the TowerJazz CMOS Imaging process, taken from [3].

The ITS2 provides pseudo-rapidity coverage of $|\eta|<$1.22$$ for
$90\text{\,}\%$ of the most luminous beam interaction region. The radial
positions of the layers were optimised in order to achieve the best combined
performance in terms of pointing resolution, $p_{\textrm{T}}$ resolution and
tracking efficiency in Pb–Pb collisions at hit densities of about
$10\text{\,}\mathrm{c}\mathrm{m}^{-2}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}$
on average for minimum-bias events in the innermost layer. The ITS2 will be
operated at room temperature
($20\text{\,}\mathrm{\SIUnitSymbolCelsius}25\text{\,}\mathrm{\SIUnitSymbolCelsius}$)
using water cooling. The expected radiation load at the innermost layer
amounts to $270\text{\,}\mathrm{k}\mathrm{r}\mathrm{a}\mathrm{d}$ of Total
Ionising Dose (TID) and
$1.7\text{\times}{10}^{12}\text{\,}$\mathrm{missing}\mathrm{revert_as}\mathrm{=}{presentation}\mathrm{]}{\text{\,}1\mathrm{M}\mathrm{e}\mathrm{V}~{}\mathrm{n}_{eq}\mathrm{/}\mathrm{c}\mathrm{m}\mathrm{{}^{2}}}{1\text{\,}\mathrm{M}\mathrm{e}\mathrm{V}~{}\mathrm{n}_{eq}\mathrm{/}\mathrm{c}\mathrm{m}\mathrm{{}^{2}}}$$
of Non-Ionising Energy Loss (NIEL). In order to meet the material budget
requirements, the silicon sensors for the innermost layers are be thinned down
to $50\text{\,}\mathrm{\SIUnitSymbolMicro m}$.

The ITS2 system is schematically shown in Fig. 3. The detector staves are
connected to the Readout Units (RUs) via roughly
$6\text{\,}\mathrm{m}8\text{\,}\mathrm{m}$ long TwinAx copper cables providing
clock, control and data transport. In the IB, every ALPIDE chip transmits data
via a dedicated
$1.2\text{\,}\mathrm{G}\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{/}\mathrm{s}$
high-speed link. In the OB, seven ALPIDE chips share a
$400\text{\,}\mathrm{M}\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{/}\mathrm{s}$
link which is possible due to the lower occupancy in the middle and outer
layers. The RUs control the Power Boards (PBs) which supply the detector via
$6\text{\,}\mathrm{m}8\text{\,}\mathrm{m}$ long power cables. RUs and PBs are
located inside a magnetic field of $0.5\text{\,}\mathrm{T}$ and are exposed to
less than $10\text{\,}\mathrm{k}\mathrm{r}\mathrm{a}\mathrm{d}$ of TID. The
RUs are connected to the the upstream Common Readout Units (CRUs) by more than
600 GigaBitTransceiver (GBT) links. The CRUs are PCIe-based interface cards
located in the First-Level-Processing (FLP) servers. Trigger and timing
information is supplied to the RUs from the ALICE Central Trigger Processor
(CTP) via a single-mode fiber network employing passive optical splitting into
almost 200 GBT links. The main control path for the Detector Control System
(DCS) is via the CRU and the GBT links. CANbus serves as slow backup
communication interface which can be used to do status monitoring or control
the power towards the detector.

Figure 3: ITS2 system overview.

The detector construction and assembly started in December 2016 with the
ALPIDE mass production. A total of more than $72\,000$ ALPIDE chips were
assembled into roughly $2600$ Hybrid Integrated Circuits (HICs) consisting of
Flexible Printed Circuits and ALPIDE chips which in turn were mounted on
detector staves. An IB HIC combines nine ALPIDE chips which are mounted
together on a stave. In the OB, a stave consists of 8 or 14 HICs for
installation in ML and OL, respectively. An OB HIC combines two rows of seven
chips.

The full assembly of the detector half-barrels continued until the end of
2019. The ITS production is summarized e.g. in [5].

##  3 On-Surface Commissioning

With the availability of first IB half layers in May 2019, the commissioning
of the detector in a cleanroom on surface started and further components were
integrated step-by-step.

In order to provide testing with a system as final as possible, the services
to be used in the experiment, including cooling plant, power system and
computing system for detector control and data acquisition, were first
installed on the surface and then later moved together with the detector for
final integration and commissioning in ALICE. Throughout 2020, the full
detector was under commissioning on-surface with the half-barrels located next
to each other to facilitate step-wise integration.

Figure 4: ITS2 in the clean room during on-surface commissioning, in the
backfrom left to right OB top half-barrel, IB top half-barrel, IB bottom half-
barrel, OB bottom half-barrel; zoomed view of an OB half-barrel (left) and an
IB half-barrel (right).

During the on-surface commissioning, the performance of the detector was
thoroughly characterised with regard to its detection, noise and readout
performance. Furthermore, the charge threshold of the detector was calibrated
to achieve an average value of $100\text{\,}\mathrm{\text{ $e$ }}^{-}$ which
was used to obtain the results shown in this section. This working point
chosen for the operation of the ITS based on previous measurements [6].

### IB Readout Performance

The performance of the ALPIDE high-speed link was verified for various
combinations of occupancies and readout rates. The occupancy was generated by
pulsing clusters of eight pixels with a static pattern being repeated in every
event. The amount of clusters was varied from 32 to 512 clusters. In
comparison, the average occupancy from minimum bias Pb–Pb collisions is
expected to be below 32 clusters, and 64 clusters correspond to a most-central
Pb–Pb collision. An upper limit for the bit-error rate was set to
$1\text{\times}{10}^{-16}$ for an occupancy of 64 clusters up to a rate of
$247\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$. A comparable perfomance was
confirmed at a rate of $44.9\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$
increasing the occupancy of 512 clusters. This translates into a large margin
with respect to occupancy and readout rate and would allow for several tens of
hours of operation of the full system without any bit error at nominal
conditions.

Figure 5: The fake-hit rate of a IB Half-Barrel as function of the number of
masked pixels, colors indicate how often a pixel fired in
$15\text{\times}{10}^{6}\text{\,}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{s}$
acquired at a trigger rate of $50\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$
using a charge threshold of $100\text{\,}\mathrm{\text{ $e$ }}^{-}$ .

### IB Fake-Hit Rate

Figure 6: Superimposed hit-maps of 216 ALPIDEs amounting to 204 days of
exposure time (top) and photograph of an IB HIC (bottom), taken from [7].

In the IB, the fake-hit rate was found to be dominated by roughly hundred
pixels per half-barrel as shown in Fig. 5. Masking these pixels leads to a
fake-hit rate of
$1\text{\times}{10}^{-10}\text{\,}\mathrm{/}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}$.
This is significantly better than the required
$1\text{\times}{10}^{-6}\text{\,}\mathrm{/}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}$.
The majority of pixels which remains after this masking shows one or two hits,
which are compatible with the hypothesis of being hits from cosmic muons.
After subtraction of hits which can be associated to a track and overlaying
the hits of all chips on top of each other, the hit-map in Fig. 6 (top) was
obtained. By comparing the hit-map to a photograph of the IB HIC in Fig. 6
(bottom), one can clearly associate noise hit clusters to the position of the
decoupling capacitors. A dedicated study [7] showed these hits to originate
from electrons emitted in the decay chain of Pb-210 which was part of the
solder used to assemble the HICs.

### OB Fake-Hit Rate

Figure 7: OB fake-hit rate for different masking conditions.

The noise performance has also been confirmed for the Outer Barrel of the
ITS2. After masking of broken double columns, all chips show a fake-hit rate
below
$1\text{\times}{10}^{-6}\text{\,}\mathrm{/}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}$
(cf. Fig 7, solid grey). This figure is based on a minimum of twenty noise
acquisition runs of approximately one million events.

A realistic estimate of the performance of the online masking is given by
masking pixels which are noisy in all runs. This leads to a significant
reduction of the fake-hit rate and the vast majority of staves exhibits a
value below
$1\text{\times}{10}^{-8}\text{\,}\mathrm{/}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}$
(cf., Fig. 7, yellow). Compared to the required
$1\text{\times}{10}^{-6}\text{\,}\mathrm{/}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}$,
this represents a significant decrease of data volume from noise which
dominates in the outer layers and in particular for pp collisions. The reason
for the variation of which pixels are noisy over time is to be understood. A
small fraction of the noisy pixels could be simply showing thermal noise,
however, it is unlikely to explain the full extent. Another contribution could
be variations in the supply voltage which are particularly pronounced in the
OB as here up to 98 chips on a half-stave share the same return path.

Offline masking even allows one to obtain a fake-hit rate of
$1\text{\times}{10}^{-10}\text{\,}\mathrm{/}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}$
(cf.light blue), however, this can only be exploited during the processing of
the data.

### OB Tracking Efficiency

The excellent noise performance furthermore allows to efficiently acquire
cosmic muon tracks using continuous integration without employing a dedicated
trigger. For the OB, these tracks were used to study the detection efficiency.
The clusters of three layers were fitted with a straight line and extrapolated
to the fourth layer. Preliminary results are around $99\text{\,}\mathrm{\char
37\relax}$ for the detection efficiency of all four layers of the OB. This
study has been carried out without software alignment, relying on the
mechanical alignment of the detector mechanics.

##  4 Installation in the ALICE Experiment

At the beginning of 2021, the services were transferred from the on-surface
commissioning hall to the experimental cavern. In March 2021, the Outer Barrel
was installed around the interaction point. Figure 8 (top) shows Layer 3, and
in particular its power distribution bus shining golden, around the beam pipe.
After the installation, the detector was thoroughly verified before the Inner
Barrel was inserted into its final position in close vicinity of the beam
pipe. In Fig. 8 (bottom), the bottom half of the Inner Barrel is in its final
position at around $1\text{\,}\mathrm{m}\mathrm{m}$ distance from the beam
pipe.

Figure 8: OB surrounding the beam pipe with the Muon Forward Tracker (MFT) in
the background (top), ITS2 IB bottom half-barrel next to the beam pipe, OB and
MFT in the background.

ITS2 is installed on rails in the so-called cage hosting beam pipe, ITS2 and
MFT [8] inside the ALICE TPC [9]. Due to the small clearances and the fragile
nature of the detectors, the ITS2 installation was highly challenging.
Therefore, several insertion tests have been carried out on surface to
optimise the procedures and to spot potential interferences. For the final
installation inside the experimental apparatus, up to six cameras where used
to monitor key contact points. Furthermore, surveys were carried out to
determine the exact position of the detector elements and the beam pipe and
visualize them with the help of three-dimensional scans which had be carried
out before. During the insertion process moreover CAD models with increasing
insertion progress were compared to the camera images to verify the
positioning of the detector elements. The full detector was installed without
damaging any component.

##  5 First Results from ITS2 in the ALICE Experiment

After connection and verification of the detector and its services, the focus
was on the central system integration and on gaining experience with the final
framework for the operation of the detector.

Furthermore, first cosmic muon tracks like the one shown in Fig. 9 traversing
the full detector could be acquired using continuous integration without a
dedicated trigger signal. These tracks were found by matching three hit points
in the layers 4 to 6 of the OB and requiring another hit point in the IB. Such
tracks were observed at a rate of about $0.02\text{\,}\mathrm{H}\mathrm{z}$,
while tracks traversing only the OB were more frequent, with a rate of around
$0.5\text{\,}\mathrm{H}\mathrm{z}$. Figure 10 shows the so-called decision
value indicating the straightness of the seeding tracklet in layers 4 to 6 for
tracks passing through OB only (blue line) as well as tracks traversing both
IB and OB (red).

Figure 9: Cosmic muon traversing all layers of ITS2 twice, no magnetic field.
Figure 10: Track straightness based on hits in layers 4, 5 and 6 in the OB for
tracks passing only the OB (blue) as well as both IB and OB (red).

The study of these first tracks to determine detection efficiency and
alignment is currently ongoing. The residuals prior to alignment are found to
be of the order of $1\text{\,}\mathrm{mm}$ underlining the excellent
mechanical alignment and confirming the correctness of the mapping of the
detector channels in software

A first look at the noise performance using a coarse tuning of the charge
threshold was possible via the newly developed ITS2 Quality Control (QC). At
this stage of the commissioning inside the experimental apparatus, the
majority of IB staves showed already fake-hit rates around
$1\text{\times}{10}^{-8}\text{\,}\mathrm{/}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}$.
For the OB, most of the staves showed a fake-hit rate better than
$1\text{\times}{10}^{-6}\text{\,}\mathrm{/}\mathrm{p}\mathrm{i}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{/}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{t}$.

During the remaining commissioning time, the tools for calibration and
detector control will be finalised and the settings of the detector will be
optimised to match the performance observed during the on-surface
commissioning.

##  6 Summary

The upgrade Inner Tracking System, ITS2, has been installed in the
experimental apparatus. Results from the on-surface commissioning as well as
of the commissioning inside the experimental apparatus confirm the performance
of single ALPIDE chips with regard to fake-hit rate and detection efficiency.
The second half of 2021 is devoted to global commissioning together with the
ALICE sub-detectors and first data with beam provided by the LHC pilot beams
in October 2021 in preparation for the LHC Run 3 in 2022.

## References

  * [1] The ALICE Collaboration, The ALICE experiment at the CERN LHC, J. Instrum. 3 (2008) S08002.  doi:10.1088/1748-0221/3/08/S08002.
  * [2] The ALICE Collaboration, Upgrade of the ALICE Experiment: Letter Of Intent, J. Phys. G41 (2014) 087001.  doi:10.1088/0954-3899/41/8/087001.
  * [3] The ALICE Collaboration, Technical Design Report for the Upgrade of the ALICE Inner Tracking System, J. Phys. G41 (2014) 087002.  doi:10.1088/0954-3899/41/8/087002.
  * [4] G. Aglieri Rinella, The ALPIDE pixel sensor chip for the upgrade of the ALICE Inner Tracking System, Nucl. Instrum. Methods Phys. Res. A A845 (2017) 583–587.  doi:10.1016/j.nima.2016.05.016.
  * [5] G. Contin, The MAPS-based ITS Upgrade for ALICE, PoS Vertex2019 (2020) 003.  arXiv:2001.03042, doi:10.22323/1.373.0003.
  * [6] P. Martinengo, The new Inner Tracking System of the ALICE experiment, Nucl. Phys. A967 (2017) 900–903.  doi:10.1016/j.nuclphysa.2017.05.069.
  * [7] M. Mager, Noise performance of the ALPIDE-based ALICE Inner Tracking System, TIPP2021 (to be published).
  * [8] The ALICE Collaboration, Technical Design Report for the Muon Forward Tracker, Tech. Rep. CERN-LHCC-2015-001, CERN (2015).
  * [9] J. Adolfsson et al., The upgrade of the ALICE TPC with GEMs and continuous readout, J. Instrum. 16 (03) (2021) P03022.  arXiv:2012.09518, doi:10.1088/1748-0221/16/03/P03022.


* Doney (1997) R. Doney (1997): One–sided local large deviation and renewal theorems in the case of infinite mean.  Probability Theory and Related Fields 107:451–465.
  * Embrechts et al. (1979) P. Embrechts, C. Goldie and N. Veraverbeke (1979): Subexponentiality and infinite divisibility.  Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 49:335–347.
  * Foss et al. (2007) S. Foss, T. Konstantopoulos and S. Zachary (2007): The principle of a single big jump: discrete and continuous time modulated random walks with heavy-tailed increments.  Journal of Theoretical Probability 20:581–612.
  * Goldie and Resnick (1988) C. Goldie and S. Resnick (1988): Distributions that are both subexponential and in the domain of attraction of an extreme-value distribution.  Advances in Applied Probability 20:706–718.
  * Harris and Robbins (1953) T. Harris and H. Robbins (1953): Ergodic theory of Markov chains admitting an infinite invariant measure.  Proceedings of the National Academy of Sciences 39:860–864.
  * Kingman (1968) J. Kingman (1968): The ergodic theory of subadditive stochastic processes.  J. Roy. Statist. Soc. Ser. B 30:499–510.
  * Lacaux and Samorodnitsky (2016) C. Lacaux and G. Samorodnitsky (2016): Time-changed extremal process as a random sup measure.  Bernoulli 22:1979–2000.
  * Leadbetter (1983) M. Leadbetter (1983): Extremes and local dependence of stationary sequences.  Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 65:291–306.
  * Molchanov (2017) I. Molchanov (2017): Theory of Random Sets.  Springer, London, 2nd edition.
  * O’Brien et al. (1990) G. O’Brien, P. Torfs and W. Vervaat (1990): Stationary self-similar extremal processes.  Probability Theory and Related Fields 87:97–119.
  * Owada and Samorodnitsky (2015) T. Owada and G. Samorodnitsky (2015): Maxima of long memory stationary symmetric $\alpha$-stable processes, and self-similar processes with stationary max-increments.  Bernoulli 21:1575–1599.
  * Pitman (1980) E. Pitman (1980): Subexponential distribution functions.  Journal of Australian Mathematical Society, Series A 29:337–347.
  * Resnick (1987) S. Resnick (1987): Extreme Values, Regular Variation and Point Processes.  Springer-Verlag, New York.
  * Resnick (2007) S. Resnick (2007): Heavy-Tail Phenomena: Probabilistic and Statistical Modeling.  Springer, New York.
  * Resnick and Rubinovitch (1973) S. Resnick and M. Rubinovitch (1973): The structure of extremal processes.  Advances in Applied Probability 5:287–307.
  * Resnick et al. (2000) S. Resnick, G. Samorodnitsky and F. Xue (2000): Growth rates of sample covariances of stationary symmetric $\alpha$-stable processes associated with null recurrent Markov chains.  Stochastic Processes and Their Applications 85:321–339.
  * Samorodnitsky (2016) G. Samorodnitsky (2016): Stochastic Processes and Long Range Dependence.  Springer, Cham, Switzerland.
  * Samorodnitsky and Wang (2019) G. Samorodnitsky and Y. Wang (2019): Extremal theory for long range dependent infinitely divisible processes.  Annals of Prbability 47:2529–2562.
  * Sato (2013) K. Sato (2013): Lévy Processes and Infinitely Divisible Distributions.  Cambridge University Press, Cambridge, 2nd edition.
  * Spitzer (1964) F. Spitzer (1964): Principles of Random walk.  D. van Nostrand Company, Princeton.
  * Taylor and Wendel (1966) S. Taylor and J. G. Wendel (1966): The Exact Hausdorff Measure of the Zero Set of a Stable Process.  Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 6:170–180.
  * Whitt (1971) W. Whitt (1971): Weak convergence of first passage time processes.  J. Appl. Probability 8:417–422.
  * Whitt (2002) W. Whitt (2002): Stochastic-Process Limits. An Introduction to Stochastic-Process Limits and Their Applications to Queues.  Springer, New York.


Cornell University, Ithaca, NY 14853<EMAIL_ADDRESS>author’s
research is supported in part by NSF CCF 1947789. Williams College,
Williamstown MA 01267 USA and
<EMAIL_ADDRESS>author’s research is
supported in part by NSF CCF 2103813 Williams College, Williamstown MA 01267
USA and<EMAIL_ADDRESS>author’s
research is supported in part by NSF CCF 1947789. Williams College,
Williamstown MA 01267<EMAIL_ADDRESS>author’s research is
supported in part by NSF CCF 1947789. David Lee, Samuel McCauley, Shikha
Singh, and Max Stein <ccs2012> <concept>
<concept_id>10003752.10003809.10010031</concept_id> <concept_desc>Theory of
computation Data structures design and analysis</concept_desc>
<concept_significance>300</concept_significance> </concept> </ccs2012>
[300]Theory of computation Data structures design and analysis

# Telescoping Filter: A Practical Adaptive Filter

David J. Lee  Samuel McCauley  Shikha Singh  Max Stein

###### Abstract

Filters are small, fast, and approximate set membership data structures. They
are often used to filter out expensive accesses to a remote set
${\mathcal{S}}$ for negative queries (that is, filtering out queries
$x\notin{\mathcal{S}}$). Filters have one-sided errors: on a negative query, a
filter may say “present” with a tunable false-positive probability of
$\varepsilon$. Correctness is traded for space: filters only use
$\log(1/\varepsilon)+O(1)$ bits per element.

The false-positive guarantees of most filters, however, hold only for a single
query. In particular, if $x$ is a false positive, a subsequent query to $x$ is
a false positive with probability $1$, not $\varepsilon$. With this in mind,
recent work has introduced the notion of an adaptive filter. A filter is
adaptive if each query is a false positive with probability $\varepsilon$,
regardless of answers to previous queries. This requires “fixing” false
positives as they occur.

Adaptive filters not only provide strong false positive guarantees in
adversarial environments but also improve query performance on practical
workloads by eliminating repeated false positives.

Existing work on adaptive filters falls into two categories. On the one hand,
there are practical filters, based on the cuckoo filter, that attempt to fix
false positives heuristically without meeting the adaptivity guarantee. On the
other hand, the broom filter is a very complex adaptive filter that meets the
optimal theoretical bounds.

In this paper, we bridge this gap by designing the telescoping adaptive filter
(TAF), a practical, provably adaptive filter. We provide theoretical false-
positive and space guarantees for our filter, along with empirical results
where we compare its performance against state-of-the-art filters. We also
implement the broom filter and compare it to the TAF . Our experiments show
that theoretical adaptivity can lead to improved false-positive performance on
practical inputs, and can be achieved while maintaining throughput that is
similar to non-adaptive filters.

###### keywords:

Filters, approximate-membership query data structures (AMQs), Bloom filters,
quotient filters, cuckoo filters, adaptivity, succinct data structures

##  1 Introduction

A filter is a compact and probabilistic representation of a set
${\mathcal{S}}$ from a universe ${\mathcal{U}}$. A filter supports insert and
query operations on ${\mathcal{S}}$. On a query for an element
$x\in{\mathcal{S}}$, a filter returns “present” with probability $1$, i.e., a
filter guarantees no false negatives. A filter is allowed to have bounded
false positives—on a query for an element $x\notin{\mathcal{S}}$, it may
incorrectly return “present” with a small and tunable false-positive
probability $\varepsilon$.

Filters are used because they allow us to trade correctness for space. A
lossless representation of ${\mathcal{S}}\subseteq{\mathcal{U}}$ requires
$\Omega(n\log u)$ bits, where $n=|{\mathcal{S}}|$, $u=|{\mathcal{U}}|$, and
$n\ll u$. Meanwhile, an optimal filter with false-positive probability
$\varepsilon$ requires only $\Theta(n\log(1/\varepsilon))$ bits
[CarterFlGi78].

Examples of classic filters are the _Bloom filter_ [Bloom70], the _cuckoo
filter_ [FanAnKa14], and the _quotient filter_ [BenderFaJo12]. Recently,
filters have exploded in popularity due to their widespread applicability—many
practical variants of these classic filters have been designed to improve upon
throughput, space efficiency, or cache efficiency [PandeyBeJo17,
wang2019vacuum, breslow2018morton, graf2020xor, lang2019performance,
dillinger2021ribbon].

A filter’s small size allows it to fit in fast memory, higher in the memory
hierarchy than a lossless representation of ${\mathcal{S}}$ would allow. For
this reason, filters are frequently used to speed up expensive queries to an
external dictionary storing ${\mathcal{S}}$.

In particular, when a dictionary for ${\mathcal{S}}$ is stored remotely (on a
disk or across a network), checking a small and fast filter first can avoid
expensive remote accesses for a $1-\varepsilon$ fraction of negative queries.
This is the most common use case of the filter, with applications in LSM-based
key-value stores [o1996log, ChangDeGh08, matsunobu2020myrocks], databases
[DengRa06, EppsteinGoMi2017, CohenMa03], and distributed systems and networks
[TarkomaRoLa12, BroderMi04].

False positive guarantees and adaptivity. When a filter is used to speed up
queries to a remote set ${\mathcal{S}}$, its performance depends on its false-
positive guarantees: how often does the filter make a mistake, causing us to
access ${\mathcal{S}}$ unnecessarily?

Many existing filters, such as the Bloom, quotient and cuckoo filters, provide
poor false-positive guarantees because they hold only for a single query.
Because these filters do not adapt, that is, they do not “fix” any false
positives, querying a known false positive $x$ repeatedly can drive their
false-positive rate to $1$, rendering the filter useless.

Ideally, we would like a stronger guarantee: even if a query $x$ has been a
false positive in the past, a subsequent query to $x$ is a false positive with
probability at most $\varepsilon$. This means that the filter must “fix” each
false positive $x$ as it occurs, so that subsequent queries to $x$ are
unlikely to be false positives. This notion of adaptivity was formalized by
Bender et al. [bender2018bloom]. A filter is adaptive if it guarantees a false
positive probability of $\varepsilon$ for every query, regardless of answers
to previous queries. Thus, adaptivity provides security advantages against an
adversary attempting to degrade performance, e.g., in denial-of-service
attacks.

At the same time, fixing previous false positives leads to improved
performance. Many practical datasets do, in fact, repeatedly query the same
element—on such a dataset, fixing previous false positives means that a filter
only incurs one false positive per _unique_ query. Past work has shown that
simple, easy-to-implement changes to known filters can fix false positives
heuristically. Due to repeated queries, these heuristic fixes can lead to
reduction of several orders of magnitude in the number of incurred false
positives [MitzenmacherPo17, kopelowitz21, BruckGaJi06].

Recent efforts that tailor filters to query workloads by applying machine
learning techniques to optimize performance [rae2019meta,
mitzenmacher2018model, deeds2020stacked] reinforce the benefits achieved by
adaptivity.

Adaptivity vs practicality. The existing work on adaptivity represents a
dichotomy between simple filters one would want to implement and use in
practice but are not actually adaptive [MitzenmacherPo17, kopelowitz21], or
adaptive filters that are purely theoretical and pose a challenge to
implementation [bender2018bloom].

Mitzenmacher et al. [MitzenmacherPo17] provided several variants of the
adaptive cuckoo filter (ACF) and showed that they incurred significantly fewer
false positives (compared to a standard cuckoo filter) on real network trace
data. The data structures in [MitzenmacherPo17] use simple heuristics to fix
false positives with immense practical gains, leaving open the question of
whether such heuristics can achieve worst-case guarantees on adaptivity.

Recently, Kopelowitz et al. [kopelowitz21] proved that this is not true even
for a non-adversarial notion of adaptivity. In particular, they defined
support optimality as the adaptivity guarantee on “predetermined” query
workloads: that is, query workloads that are fixed ahead of time and not
constructed in response to a filter’s response on previous queries. They
showed that the filters in [MitzenmacherPo17] fail to be adaptive even under
this weaker notion—repeating $O(1)$ queries $n$ times may cause them to incur
$\Omega(n)$ false positives.

Kopelowitz et al. [kopelowitz21] proposed a simple alternative, the Cuckooing
ACF, that achieves support optimality by cuckooing on false positives
(essentially reinserting the element). Furthermore, they proved that none of
the cuckoo filter variants (including the Cuckooing ACF) are adaptive. They
showed that a prerequisite to achieving adaptivity is allocating a variable
number of bits to each stored element—that is, maintaining variable-length
fingerprints. All of the cuckoo filter variants use a bounded number of bits
per element.

The only known adaptive filter is the broom filter of Bender et al.
[bender2018bloom], so-named because it “cleans up” its mistakes. The broom
filter achieves adaptivity, while supporting constant-time worst-case query
and insert costs, using very little extra space—$O(n)$ extra bits in total.
Thus the broom filter implies that, in theory, adaptivity is essentially free.

More recently, Bender et al. [bender21] compared the broom filter
[bender2018bloom] to a static filter augmented with a comparably sized top-$k$
cache (a cache that stores the $k$ most frequent requests). They found that
the broom filter outperforms the cache-augmented filter on Zipfian
distributions due to “serendipitous corrections”—fixing a false positive
eliminates future false positives in addition to the false positive that
triggered the adapt operation. They noted that their broom filter simulation
is “quite slow,” and left open the problem of designing a practical broom
filter with performance comparable to that of a quotient filter.

In this paper, we present a practical and efficient filter which also achieves
worst-case adaptivity: the telescoping adaptive filter. The key contribution
of this data structure is a practical method to achieve worst-case adaptivity
using variable-length fingerprints.

Telescoping adaptive filter. The telescoping adaptive filter (TAF) combines
ideas from the heuristics used in the adaptive cuckoo filter
[MitzenmacherPo17], and the theoretical adaptivity of the broom filter
[bender2018bloom].

The TAF is built on a rank-and-select quotient filter (RSQF) [PandeyBeJo17] (a
space- and cache-efficient quotient filter [BenderFaJo12] variant), and
inherits its performance guarantees.

The telescoping adaptive filter is the first adaptive filter that can take
advantage of _any_ amount of extra space for adaptivity, even a fractional
number of bits per element. We prove that if the TAF uses
$\left(\frac{1}{e}+\frac{b}{(1-b)^{2}}\right)$ extra bits per element in
expectation, then it is is provably adaptive for any workload consisting of up
to $n/(b\sqrt{\varepsilon})$ unique queries (Section 4). Empirically, we show
that the TAF outperforms this bound: with only $0.875$ of a bit extra per
element for adaptivity, it is adaptive for larger query workloads. Since the
RSQF uses $2.125$ metadata bits per element, the total number of bits used by
the TAF is $(n/\alpha)(\log_{2}(1/\varepsilon)+3)$, where $\alpha$ is the load
factor.

The TAF stores these extra bits space- and cache-efficiently using a practical
implementation of a theoretically-optimal compression scheme: arithmetic
coding [cacm-arcd, brown-arcd]. Arithmetic coding is particularly well-suited
to the exponentially decaying probability distribution of repeated false
positives. While standard arithmetic coding on the unit interval can be slow,
we implement an efficient approximate integer variant.

The C code for our implementation can be found at
https://github.com/djslzx/telescoping-filter.

Our contributions. We summarize our main contributions below.

  * •

We present the first provably-adaptive filter, the telescoping adaptive
filter, engineered with space, cache-efficiency and throughput in mind,
demonstrating that adaptivity is not just a theoretical concept, and can be
achieved in practice.

  * •

As a benchmark for TAF, we also provide a practical implementation of the
broom filter [bender2018bloom]. We call our implementation of the broom filter
the extension adaptive filter (exAF). While both TAF and exAF use the near-
optimal $\Theta(n)$ extra bits in total to adapt on $\Theta(n)$ queries, the
telescoping adaptive filter is optimized to achieve better constants and eke
out the most _adaptivity per bit_. This is confirmed by our experiments which
show that given the same space for adaptivity $(0.875$ bits per element), the
TAF outperforms the false-positive performance of the exAF significantly on
both practical and adversarial workloads. Meanwhile, our experiments show that
the query performance of exAF is factor $2$ better than that of the TAF .
Thus, we show that there is a trade off between throughput performance and how
much adaptivity is gained from each bit.

  * •

We give the first empirical evaluation of how well an adaptive filter can fix
positives in practice. We compare the TAF with a broom filter implementation,
as well as with previous heuristics. We show that the TAF frequently matches
or outperforms other filters, while it is especially effective in fixing false
positives on “difficult” datasets, where repeated queries are spaced apart by
many other false positives. We also evaluate the throughput of the TAF and the
exAF against the vacuum filter [wang2019vacuum] and RSQF, showing for the
first time that adaptivity can be achieved while retaining good throughput
bounds.

##  2 Preliminaries

In this section, we provide background on filters and adaptivity, and describe
our model.

###  2.1 Background on Filters

We briefly summarize the structure of the filters discussed in this paper. For
a more detailed description, we refer the reader to the full version. All logs
in the paper are base $2$. We assume that $\varepsilon$ is an inverse power of
$2$.

The quotient filter and cuckoo filter are both based on the single-hash
function filter [PaghPaRa05]. Let the underlying hash function $h$ output
$\Theta(\log n)$ bits. To represent a set
${\mathcal{S}}\subseteq{\mathcal{U}}$, the filter stores a fingerprint $f(x)$
for each element $x\in{\mathcal{S}}$. The fingerprint $f(x)$ consists of the
first $\log n+\log(1/\varepsilon)$ bits of $h(x)$, where $n=|{\mathcal{S}}|$
and $\varepsilon$ is the false-positive probability.

The first $\log n$ bits of $f(x)$ are called the quotient $q(x)$ and are
stored implicitly; the remaining $\log(1/\varepsilon)$ bits are called the
remainder $r(x)$ and are stored explicitly in the data structure. Both filters
consist of an array of slots, where each slot can store one remainder.

Quotient filter. The quotient filter (QF) [BenderFaJo12] is based on linear
probing. To insert $x\in{\mathcal{S}}$, the remainder $r(x)$ is stored in the
slot location determined by the quotient $q(x)$, using linear probing to find
the next empty slot. A small number of metadata bits suffice to recover the
original slot for each stored element. A query for $x$ checks if the remainder
$r(x)$ is stored in the filter—if the remainder is found, it returns
“present”; otherwise, it returns “absent.” The rank-and-select quotient filter
(RSQF) [PandeyBeJo17] implements such a scheme using very few metadata bits
(only 2.125 bits) per element.

Broom filter. The broom filter of Bender et al. [bender2018bloom] is based on
the quotient filter. Initially, it stores the same fingerprint $f(x)$ as a
quotient filter. The broom filter uses the remaining bits of $h(x)$, called
adaptivity bits, to extend $f(x)$ in order to adapt on false positives.

On a query $y$, if there is an element $x\in{\mathcal{S}}$ such that $f(x)$ is
a prefix of $h(y)$, the broom filter returns “present.” If it turns out that
$y\notin{\mathcal{S}}$, the broom filter adapts by extending the fingerprint
$f(x)$ until it is no longer a prefix of $h(y)$.111These additional bits are
stored separately in the broom filter: groups of $\Theta(\log n)$ adaptivity
bits, corresponding to $\log n$ consecutive slots in the filter, are stored
such that accessing all the adaptivity bits of a particular element (during a
query operation) can be done in $O(1)$ time. Bender et al. show that, with
high probability, $O(n)$ total adaptivity bits of space are sufficient for the
broom filter to be adaptive on $\Theta(n)$ queries.

Cuckoo filters and adaptivity. The cuckoo filter resembles the quotient filter
but uses a cuckoo hash table rather than linear probing. Each element has two
fingerprints, and therefore two quotients. The remainder of each
$x\in{\mathcal{S}}$ must always be stored in the slot corresponding to one of
$x$’s two quotients.

The Cyclic ACF [MitzenmacherPo17], Swapping ACF [MitzenmacherPo17], and
Cuckooing ACF [kopelowitz21]222We use the nomenclature of [kopelowitz21] in
calling these the Cyclic ACF, Swapping ACF, and Cuckooing ACF. change the
function used to generate the remainder on a false positive. To avoid
introducing false negatives, a filter using this technique must somehow track
which function was used to generate each remainder so that the appropriate
remainders can be compared at query time.

The Cyclic ACF stores $s$ extra bits for each slot, denoting which of $2^{s}$
different remainders are used. The Swapping ACF, on the other hand, groups
slots into constant-sized bins, and has a fixed remainder function for each
slot in a bin. A false positive is fixed by moving some $x\in{\mathcal{S}}$ to
a different slot in the bin, then updating its remainder using the function
corresponding to the new slot. The Cuckooing ACF works in much the same way,
but both the quotient and remainder are changed by “cuckooing” the element to
its alternate position in the cuckoo table.

###  2.2 Model and Adaptivity

All filters that adapt on false positives [MitzenmacherPo17, kopelowitz21,
bender2018bloom] have access to the original set ${\mathcal{S}}$. This is
called the remote representation, denoted ${\mathbf{R}}$. The remote
representation does not count towards the space usage of the filter. On a
false positive, the filter is allowed to access the set ${\mathbf{R}}$ to help
fix the false positive.

The justification for this model is twofold. (This justification is also
discussed in [bender2018bloom, kopelowitz21, MitzenmacherPo17].) First, the
most common use case of filters is to filter out negative queries to
${\mathcal{S}}$—in this case, a positive response to a query accesses
${\mathbf{R}}$ anyway. Information to help rebuild the filter can be stored
alongside the set in this remote database. Second, remote access is necessary
to achieve good space bounds: Bender et al. [bender2018bloom] proved that any
adaptive filter without remote access to ${\mathcal{S}}$ requires
$\Omega(n\log\log u)$ bits of space.

Our filter can answer queries using only the local state ${\mathbf{L}}$. Our
filter accesses the remote state ${\mathbf{R}}$ in order to fix false
positives when they occur, updating its local state. This allows our filter to
be adaptive while using small (near optimal) space for the local state.

Adaptivity. The sustained false positive rate of a filter is the probability
with which a query is a false positive, _regardless of the filter’s answers to
previous queries_.

The sustained false positive rate must hold even if generated by an adversary.
We use the definition of Bender et al. [bender2018bloom], which is formally
defined by a game between an adversary and the filter, where the adversary’s
goal is to maximize the filter’s false positive rate. We summarize this game
next; for a formal description of the model see Bender et al.
[bender2018bloom].

In the adaptivity game, the adversary generates a sequence of queries
$Q=x_{1},x_{2},\ldots,x_{t}$. After each query $x_{i}$, both the adversary and
filter learn whether $x_{i}$ is a false positive (that is, $x_{i}\notin S$ but
a query on $x_{i}$ returns “present”). The filter is then allowed to adapt
before query $x_{i+1}$ is made by the adversary. The adversary can use the
information about whether queries $x_{1},\ldots,x_{i}$ were a false positive
or not, to choose the next query $x_{i+1}$.

At any time $t$, the adversary may assert that it has discovered a special
query $\tilde{x}_{t}$ that is likely to be a false positive of the filter. The
adversary “wins” if $\tilde{x}_{t}$ is in fact a false positive of the filter
at time $t$, and the filter “wins” if the adversary is wrong and
$\tilde{x}_{t}$ is not a false positive of the filter at time $t$.

The sustained false positive rate of a filter is the maximum probability
$\varepsilon$ with which the adversary can win the above adaptivity game. A
filter is adaptive if it can achieve a sustained false positive rate of
$\varepsilon$, for any constant $0<\varepsilon<1$.

Similar to [bender2018bloom], we assume that the adversary cannot find a
never-before-queried element that is a false positive of the filter with
probability greater than $\varepsilon$. Many hash functions satisfy this
property, e.g., if the adversary is a polynomial-time algorithm then one-way
hash functions are sufficient [NaorYo15]. Cryptographic hash functions satisfy
this property in practice, and it is likely that even simple hash functions
(like Murmurhash used in this paper) suffice for most applications.

Towards an adaptive implementation. Kopelowitz et al. [kopelowitz21] showed
that the Cyclic ACF (with any constant number of hash-selector bits), the
Swapping ACF, and the Cuckooing ACF are not adaptive. The key insight behind
this proof is that for all three filters, the state of an element—which slot
it is stored in, and which fingerprint function is used—can only have $O(1)$
values. Over $o(n)$ queries, an adversary can find queries that collide with
an element on all of these states. These queries can never be fixed.

Meanwhile, the broom filter avoids this issue by allowing certain elements to
have more than $O(1)$ adaptivity bits—up to $O(\log n)$, in fact. The broom
filter stays space-efficient by maintaining $O(1)$ adaptivity bits per element
_on average_.

Thus, a crucial step for achieving adaptivity is dynamically changing how much
space is used for the adaptivity of each element based on past queries. The
telescoping adaptive filter achieves this dynamic space allocation (hence the
name “telescoping”) using an arithmetic coding.

##  3 The Telescoping Adaptive Filter

In this section, we describe the high-level ideas behind the telescoping
adaptive filter.

Structure of the telescoping adaptive filter. Like the broom filter, the TAF
is based on a quotient filter where the underlying hash function $h$ outputs
$\Theta(\log n)$ bits. For any $x\in{\mathcal{S}}$, the first $\log n$ bits of
$h(x)$ are the quotient $q(x)$ (stored implicitly), and the next
$\log(1/\varepsilon)$ bits are the initial remainder $r_{0}(x)$, stored in the
slot determined by the quotient. We maintain each element’s original slot
using the strategy of the rank-and-select quotient filter [PandeyBeJo17],
which stores $2.125$ metadata bits per element.

The TAF differs from a broom filter in that, on a false positive, the TAF
_changes_ its remainder rather than lengthening it, similar to the Cyclic ACF.

For each element in the TAF, we store a hash-selector value. If an element $x$
has hash-selector value $i$, its remainder $r_{i}$ is the consecutive sequence
of $\log(1/\varepsilon)$ bits starting at the $(\log
n+i\log(1/\varepsilon))$th bit of $h(x)$. Initially, the hash-selector values
of all elements are $0$, and thus the remainder $r(x)$ is the first $\log
1/\varepsilon$ bits immediately following the quotient. When the hash-selector
value of an element $x\in S$ is incremented, its remainder “slides over” to
the next (non-overlapping) $\log 1/\varepsilon$ bits of the hash $h(x)$, as
shown in Figure 1. Thus, the fingerprint of $x$ is $f(x)=q(x)\circ r_{i}(x)$,
where $\circ$ denotes concatenation and $i$ is the hash-selector value of $x$.

Figure 1: The fingerprint of $x\in S$ is its quotient $q(x)$ followed by its
remainder $r_{i}(x)$, where $i$ is the hash-selector value of $x$.

On a false positive query $y\notin{\mathcal{S}}$, there must be some
$x\in{\mathcal{S}}$ with hash-selector value $i$, such that $q(x)=q(y)$ and
$r_{i}(x)=r_{i}(y)$. To resolve this false positive, we increment $i$. We
update the hash-selector value and the stored remainder accordingly.

We describe below how to store hash-selector values using an average $0.875$
bits per element. This means that the TAF with load factor $\alpha$ uses
$(n/\alpha)(\log(1/\varepsilon)+3)$ bits of space.

Difference between hash-selector and adaptivity bits. Using hash-selector
bits, rather than adaptivity bits (as in the broom filter), has some immediate
upsides and downsides.

If fingerprint prefixes $p(x)$ and $p(y)$ collide, they will still collide
with probability $1/2$ after each prefix has been lengthened by one bit. But
adding a bit also reduces the probability that $x$ will collide with any
_future_ queries by a factor of $1/2$. Such false positives that are fixed
(without being queried) are called serendipitous false positives [bender21].

On the other hand, incrementing the hash-selector value of an element
$x\in{\mathcal{S}}$ after it collides with an element $y\notin{\mathcal{S}}$
reduces the probability that $y$ will collide again with $x$ by a factor of
$\varepsilon\ll 1/2$. Thus, the TAF is more aggressive about fixing repeated
false positives. However, the probability that $x$ collides with future
queries that are different from $y$ remains unchanged. Thus, on average the
TAF does not fix serendipitous false positives.

Our experiments (Section LABEL:sec:eval) show that the gain of serendipitous
false positive fixes is short-lived; aggressively fixing false positives leads
to better false-positive performance.

Storing hash selectors in blocks. The TAF does not have a constant number of
bits per slot dedicated solely to storing its hash-selector value. Instead, we
group the hash-selector values associated with each $\Theta(\log n)$
contiguous slots (64 slots in our implementation) together in a block. We
allocate a constant amount of space for each such block. If we run out of
space, we rebuild by setting all hash-selector values in the block to $0$.
(After a rebuild, we still fix the false positive that caused the rebuild.
Therefore, there will often be one non-zero hash-selector value in the block
after a rebuild.)

Encoding hash-selector bits. To store the hash selectors effectively, we need
a code that satisfies the following requirements: the space of the code should
be very close to optimal; the code should be able to use $<1$ bits on average
per character encoded; and the encode and decode operations should be fast
enough to be usable in practice.

In Section 5, we give a new implementation of the arithmetic coding that is
tailored to our use case, specifically encoding characters from the
distribution given in . Our implementation uses only integers, and all
divisions are implemented using bit shifts, leading to a fast and reliable
implementation while still retaining good space bounds.

##  4 Telescoping Adaptive Filter: Analysis

In this section, we analyze the sustained false-positive rate, the hash-
selector probabilities, and the space complexity of the telescoping adaptive
filter.

We assume the TAF uses a uniform random hash function $h$ such that the hash
can be evaluated in $O(1)$ time. In our adaptivity analysis of the TAF
(Theorem 4.1), we first assume that the filter has sufficient space to store
all hash-selector values; that is, it does not rebuild. Then, in Theorem 4.7,
we give a bound on the number of unique queries that the TAF can handle (based
on its size) without the need to rebuild, thus maintaining adaptivity.

Adaptivity. We first prove that the telescoping adaptive filter is adaptive,
i.e., it guarantees a sustained false positive rate of $\varepsilon$.

We say a query $x$ has a soft collision with an element $y\in{\mathcal{S}}$ if
their quotients are the same: $q(x)=q(y)$. We say a query $x$ has a hard
collision with an element $y\in{\mathcal{S}}$ if both their quotients and
remainders are the same: $q(x)=q(y)$ and $r_{i}(x)=r_{i}(y)$, where $i$ is the
hash-selector value of $y$ at the time $x$ is queried (see Section 3).

######  Theorem 4.1.

Consider a telescoping adaptive filter storing a set ${\mathcal{S}}$ of size
$n$. For any adaptively generated sequence of $t$ queries
$Q=x_{1},x_{2},\ldots,x_{t}$ (possibly interleaved with insertions), where
each $x_{i}\notin{\mathcal{S}}$, the TAF has a sustained false-positive rate
of $\varepsilon$; that is, $\Pr[\text{$x_{i}$ is a false
positive}]\leq\varepsilon$ for all $1\leq i\leq t$.

######  Proof 4.2.

Consider the $i$-th query $x_{i}\in Q$. Query $x_{i}$ is a false positive if
there exists an element $y\in{\mathcal{S}}$ such that there is hard collision
between them. Let $h_{i}(y)=q(y)\circ r_{k}(y)$ denote the fingerprint of $y$
at time $i$, where $y$ has the hash-selector value $k$ at time $i$. Then,
$x_{i}$ and $y$ have a hard collision if and only if $h_{i}(x_{i})=h_{i}(y)$.

We show that for any $y$, regardless of answers to previous queries, $x_{i}$
and $y$ have a hard collision with probability $\varepsilon/n$; taking a union
bound over all elements gives the theorem.

We proceed in cases. First, if $x_{i}$ is a first-time query, that is,
$x_{i}\notin\\{x_{1},\ldots,x_{i-1}\\}$, then the probability that
$h_{i}(x_{i})=h_{i}(y)$ is the probability that both their quotient and
remainder match, which occurs with probability $2^{-(\log n+\log
1/\varepsilon)}=\varepsilon/n$.

Next, suppose that $x_{i}$ is a repeated query, that is,
$x_{i}\in\\{x_{1},\ldots,x_{i-1}\\}$. Let $j<i$ be the largest index where
$x_{i}=x_{j}$ was previously queried. If $x_{j}$ did not have a soft collision
with $y$, that is, $q(x_{j})\neq q(y)$, then $x_{i}$ cannot have a hard
collision with $y$. Now suppose that $q(x_{j})=q(y)$. We have two subcases.

  1. 1.

$y$’s hash-selector value has not changed since $x_{j}$ was queried. Note
that, in this case, $x_{j}$ must not have had a hard collision with $y$, as
that would have caused $y$’s hash-selector value, and thus its remainder, to
be updated. Thus, $h_{j}(y)=h_{i}(y)\neq h_{j}(x_{j})=h_{i}(x_{i})$.

  2. 2.

$y$’s hash-selector value has been updated since $x_{j}$ was queried. Such an
update could have been caused by a further query to $x_{j}$ having a hard
collision with $y$, or some other query $x_{k}\in x_{j},x_{j+1},\ldots,x_{i}$
having a hard collision with $y$. In either case, the probability that the new
remainder matches, i.e., $r_{i}(y)=r_{i}(x_{i})$, is $2^{-\log
1/\varepsilon}=\varepsilon$.

Therefore, the probability that $x_{i}$ has a hard collision with $y$ is at
most $\varepsilon\cdot\Pr[q(x_{j})=q(y)]=\varepsilon/n$. Finally, by a union
bound over $n$ possibilities for $y\in{\mathcal{S}}$, we obtain that
$\Pr[\text{$x_{i}$ is a false positive}]\leq\varepsilon$ for all $1\leq i\leq
t$, as desired.

Hash-selector probabilities. The telescoping adaptive filter increments the
hash-selector value of an element $y\in{\mathcal{S}}$ whenever a false
positive query collides with $y$. Here we analyze the probability of an
element having a given hash-selector value.

######  Lemma 4.3.

Consider a sequence $Q=x_{1},x_{2},\ldots,x_{t}$ of queries (interleaved with
inserts), where each $x_{i}\notin{\mathcal{S}}$ and $Q$ consists of $cn$
unique queries (with any number of repetitions), where $c<1/\varepsilon-1$.
Then for any $y\in{\mathcal{S}}$, if $v(y)$ is the hash-selector value of $y$
after all queries in $Q$ are performed, then:

$\Pr[v(y)=k]\left\\{\begin{array}[]{ll}=(1-\frac{\varepsilon}{n})^{cn}&\text{if
}k=0\\\ \leq\varepsilon^{k}(1-\varepsilon)\sum_{i=1}^{k}{cn\choose
i}\frac{1}{n^{i}}&\text{if }k>0\end{array}\right.$

######  Proof 4.4.

First, consider the case $k=0$: the hash-selector value of $y$ stays zero
after all the queries are made if and only if none of the queries have a hard
collision with $y$. Since there are $cn$ unique queries, and the probability
that each of them has a hard collision with $y$ is $\varepsilon/n$, the
probability that none of them collide with $y$ is $(1-\varepsilon/n)^{cn}$.

Now, consider the case $k\geq 1$. Given that the hash selector value of $y$ is
$k$, we know that there have been exactly $k$ hard collisions between queries
and $y$ (where some of these collisions may have been caused by the same
query). Suppose there are $i$ unique queries among all queries that have a
hard collision with $y$, where $1\leq i\leq k$. Let $k_{j}$ be the number of
times a query $j$ collides with $y$ causing an increment in its hash-selector
value, where $1\leq j\leq i$. Thus, $\sum_{j=1}^{i}k_{j}=k$.

For a query $x_{j}$, the probability that $x_{j}$ collides with $y$, the first
time $x_{j}$ is queried, is $\varepsilon/n$. Then, given that $x_{j}$ has
collided with $y$ once, the probability of any subsequent collision with $y$
is $\varepsilon$. (This is because the $\log 1/\varepsilon$ bits of the
remainder of $y$ are updated with each collision.) Thus, the probability that
$x_{j}$ collides with $y$ at least $k_{j}$ times is
$\frac{\varepsilon}{n}\cdot\varepsilon^{k_{j}-1}$.

The probability that a query $x_{j}$ collides with $y$ at least $k_{j}$ times,
is given by
$\prod_{j=1}^{i}\frac{\varepsilon}{n}\cdot\varepsilon^{k_{j}-1}=\frac{\varepsilon^{k}}{n^{i}}$.
There are $cn\choose i$ ways of choosing $i$ unique queries from $cn$, for
$1\leq i\leq k$, which gives us

$\Pr[v(y)\geq k]=\varepsilon^{k}\sum_{i=1}^{k}{cn\choose i}\frac{1}{n^{i}}$
(1)

Finally, using Inequality 1, we can upper bound the probability that a hash-
selector value is exactly $k$.

$\displaystyle\Pr[v(y)=k]$ $\displaystyle=\Pr[v(y)\geq k]-\Pr[v(y)\geq k+1]$
$\displaystyle=\varepsilon^{k}\left[\sum_{i=1}^{k}{cn\choose
i}\frac{1}{n^{i}}-\varepsilon\sum_{i=1}^{k+1}{cn\choose
i}\frac{1}{n^{i}}\right]$
$\displaystyle=\varepsilon^{k}\cdot(1-\varepsilon)\left[\sum_{i=1}^{k}{cn\choose
i}\frac{1}{n^{i}}-\frac{\varepsilon}{1-\varepsilon}{cn\choose
k+1}\frac{1}{n^{k+1}}\right]$
$\displaystyle\leq\varepsilon^{k}(1-\varepsilon)\sum_{i=1}^{k}{cn\choose
i}\frac{1}{n^{i}}$

We simplify the probabilities in Lemma 4.3 in . The probability bounds in
closely match the distribution of hash-selector frequencies we observe
experimentally.

######  Corollary 4.5.

Consider a sequence $Q=x_{1},x_{2},\ldots,x_{t}$ of queries (interleaved with
inserts), where each $x_{i}\notin{\mathcal{S}}$ and $Q$ consists of $cn$
unique queries (with any number of repetitions), where $c<1/\varepsilon-1$.
For any $y\in{\mathcal{S}}$, if $v(y)$ is the hash-selector value of $y$ after
all queries in $Q$ are performed, then:

$\Pr[v(y)=0]<\frac{1}{e^{c\varepsilon}},\text{ and
}\Pr[v(y)=k]<\varepsilon^{k}\sum_{i=1}^{k}\frac{c^{i}}{i!}\text{ for }k\geq
1.$

######  Proof 4.6.

To upper bound $\Pr[v(y)=0]$, we use the inequality $(1-1/x)^{x}\leq 1/e$ for
$x>1$. To upper bound $\Pr[v(y)=k]$, we upper bound:

${cn\choose
i}\frac{1}{n^{i}}\leq\frac{cn\cdot(cn-1)\cdots(cn-i)}{i!}\frac{1}{n^{i}}\leq\frac{c^{i}n^{i}}{i!n^{i}}=\frac{c^{i}}{i!}$

Space analysis. Up until now, we have assumed that we always have enough room
to store arbitrarily large hash selector values. Next, we give a tradeoff
between the space usage of the data structure and the number of unique queries
it can support.

We use the hash-selector probabilities derived above to analyze the space
overhead of storing hash-selector values. Theorem 4.7 assumes an optimal
arithmetic encoding: storing a hash-selector value $k$ that occurs with
probability $p_{k}$ requires exactly $\log(1/p_{k})$ bits. In our
implementation we use an approximate version of the arithmetic coding for the
sake of performance.

######  Theorem 4.7.

For any $\varepsilon<1/2$ and $b\geq 2$, given a sequence of
$n/(b\sqrt{\varepsilon})$ unique queries (with no restriction on the number of
repetitions of each), the telescoping adaptive filter maintains a sustained
false-positive rate of $\varepsilon$ using at most
$\left(\frac{1}{e}+\frac{b}{(b-1)^{2}}\right)$ bits of space in expectation
per element.

######  Proof 4.8.

Let $c=1/(b\sqrt{\varepsilon})$; thus, there are $cn$ unique queries. Consider
an arbitrary element $y\in{\mathcal{S}}$. The expected space used to store the
hash-selector value $v(y)$ of $y$ is $\sum_{k=0}^{\infty}p_{k}\log 1/p_{k}$,
where $p_{k}$ is the probability that $v(y)=k$.

We separate out the case where $k=0$, for which $p_{k}$ is the largest, and
upper bound the $p_{0}\log 1/p_{0}$ term below, using the probability derived
in Lemma 4.3.

$\displaystyle p_{0}\log 1/p_{0}$
$\displaystyle=(1-\varepsilon/n)^{cn}\log{\frac{1}{(1-\varepsilon/n)^{cn}}}\leq\frac{1}{e^{c\varepsilon}}\cdot\log({1+\frac{\varepsilon}{n})^{cn}}$
$\displaystyle=\frac{1}{e^{c\varepsilon}}\cdot
cn\log(1+\frac{\varepsilon}{n})\leq\frac{1}{e^{c\varepsilon}}\cdot
cn\frac{\varepsilon}{n}=\frac{c\varepsilon}{e^{c\varepsilon}}<\frac{1}{e}$ (2)

In step (2) above we use the fact that $x/e^{x}<1/e$ for all $x>0$.

We now upper bound the rest of the summation, that is,
$\sum_{k=1}^{\infty}p_{k}\log 1/p_{k}$ for $k\geq 1$. When upper bounding this
summation we will be using upper bounds on $p_{k}$—but this is a _lower_ bound
on $\log 1/p_{k}$. To deal with this, we observe that the function $x\log 1/x$
is monotonically increasing for $x<1/e$. Therefore, if we show that the bounds
in Corollary 4.5 never exceed $1/e$, we can substitute both terms in
$p_{k}\log 1/p_{k}$ in our analysis. We start by showing this upper bound. In
the following, we use $b\geq 2$ and $\varepsilon<1/2$.

$p_{k}<\varepsilon^{k}\sum_{i=1}^{k}\frac{c^{i}}{i!}<\varepsilon^{k}c^{k}\cdot
k<\varepsilon^{k}\cdot{\left(\frac{1}{b\sqrt{\varepsilon}}\right)}^{k}\cdot
k=\frac{k}{b^{k}}\cdot\varepsilon^{k/2}<k\cdot\frac{1}{2^{3k/2}}<\frac{1}{e}.$

We now upper bound the sum $\sum_{k=1}^{\infty}p_{k}\log 1/p_{k}$ by replacing
$p_{k}$ with its upper bound $\varepsilon^{k}c^{k}\cdot k$ (this replacement
is an upper bound because we showed
$\varepsilon^{k}\sum_{i=1}^{k}\frac{c^{i}}{i!}<1/e$ above).

$\displaystyle\sum_{k=1}^{\infty}p_{k}\log 1/p_{k}$
$\displaystyle\leq\sum_{k\geq
1}k\varepsilon^{k}c^{k}\log\frac{1}{\varepsilon^{k}c^{k}k}=\sum_{k=1}^{\infty}\frac{k}{b^{k}}\cdot\left(\varepsilon^{k/2}\cdot\log
1/\varepsilon^{k}\right)$ (3)
$\displaystyle<\sum_{k=1}^{\infty}\frac{k}{b^{k}}=\frac{b}{(b-1)^{2}}.$ (4)

We simplify step (3) above using the fact that $\sqrt{x}\log 1/x<1$ for all
$x\leq 1$; step (4) is a known identity.

Thus, $\sum_{k=0}^{\infty}p_{k}\log 1/p_{k}<1/e+b/(b-1)^{2}$, which is the
expected number of bits used to store the hash-selector value of $y$.

Theorem 4.7 implies that if the TAF is using a certain number of bits per
element in expectation to store hash-selector values, then there is a precise
bound on the number of unique queries it can handle in any query workload
while being provably adaptive. For example, if $\varepsilon=1/2^{8}$ and we
set $b=4$ in Theorem 4.7, then a telescoping adaptive filter that uses
$4/9+1/e\approx 0.812$ bits per element in expectation can handle $4n$ unique
queries without running out of space and having to rebuild. In Section
LABEL:sec:eval, the TAF outperforms this bound, retaining good performance
with $0.812$ bits per element for $A/S\leq 20$.

##  5 Implementation

In this section, we describe the implementation of the TAF and our
implementation of the broom filter [bender2018bloom], which we call the
extension adaptive filter (exAF).

Recall that adaptive filters have a local state ${\mathbf{L}}$ and a remote
representation ${\mathbf{R}}$.

Rank-and-select quotient filter. The local state ${\mathbf{L}}$ of both the
TAF and exAF is implemented as a rank-and-select quotient filter (RSQF)
[PandeyBeJo17]. The RSQF stores metadata bits—one

######  Definition 1.

occupied bit and one