# VINS-Multi: A Robust Asynchronous Multi-camera-IMU State Estimator

Luqi Wang, Yang Xu and Shaojie Shen All authors are with the Department of
Electronic and Computer Engineering, Hong Kong University of Science and
Technology, Hong Kong, China. $\\{$lwangax<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

State estimation is a critical foundational module in robotics applications,
where robustness and performance are paramount. Although in recent years, many
works have been focusing on improving one of the most widely adopted state
estimation methods, visual inertial odometry (VIO), by incorporating multiple
cameras, these efforts predominantly address synchronous camera systems.
Asynchronous cameras, which offer simpler hardware configurations and enhanced
resilience, have been largely overlooked. To fill this gap, this paper
presents VINS-Multi, a novel multi-camera-IMU state estimator for asynchronous
cameras. The estimator comprises parallel front ends, a front end coordinator,
and a back end optimization module capable of handling asynchronous input
frames. It utilizes the frames effectively through a dynamic feature number
allocation and a frame priority coordination strategy. The proposed estimator
is integrated into a customized quadrotor platform and tested in multiple
realistic and challenging scenarios to validate its practicality.
Additionally, comprehensive benchmark results are provided to showcase the
robustness and superior performance of the proposed estimator.

##  I Introduction

State estimation serves as a fundamental component within robotic
applications, underpinning higher-level tasks with essential support.
Therefore, the robustness and concision of the system are required during
practice. A lot of recent research has concentrated on enhancing the
performance and resilience of visual-inertial odometry (VIO), one of the
predominant methods utilized for state estimation [1, 2, 3].

An intuitive and effective scheme for enhancing VIO involves the incorporation
of additional cameras to cover different directions, thereby acquiring more
information from the surrounding environment [4, 5, 6]. Most of the works
primarily investigated the use of synchronous cameras, which necessitate
auxiliary hardware triggering mechanisms. However, practically, numerous
cameras lack the hardware synchronization capability and systems reliant on
synchronous cameras often succumb to malfunctions induced by faulty trigger
signals or partial camera failures, which stem from design or technical
issues. Hence, during some real applications in demanding environments, for
instance wilderness and construction sites, deploying multiple asynchronous
cameras can be less cumbersome and offer superior robustness against failures.
Although [7] has explored the use of multiple asynchronous cameras on a
driving dataset, the approach combines asynchronous frames as multi-frame
batches and approximates the states by a B-spline trajectory for
interpolation, which typically loses degrees of freedom. To circumvent this
limitation, the incorporation of an inertial measurement unit (IMU), a
commonly adopted sensor in robotics, can be a simple and effective solution.
As a result, we propose the VINS-Multi, an asynchronous multi-camera-IMU state
estimator developed from our previous work [3, 8].

(a) Vent pipe case 1.

(b) Visualization of vent pipe case 1.

(c) Vent pipe case 2.

(d) Visualization of vent pipe case 2.

Figure 1:  The deployment of VINS-Multi in aerial vent pipe inspection
scenarios. The green lines are the estimated trajectory and the white arrows
indicate the estimated odometries. The maps are constructed during the flights
and the color code indicates the height.

The contributions of this paper are the following:

  1. 1.

We design a novel dynamic feature number allocation alongside a frame priority
coordination strategy to efficiently handle the asynchronous frame inputs.

  2. 2.

We combine a parallel front end and a front end coordinator based on the
proposed strategy, as well as a sliding window optimization module into a
robust multi-camera-IMU state estimator that can accommodate multiple
asynchronous cameras of mixed types.

  3. 3.

The estimator is integrated into a quadrotor platform for extensive
experiments in realistic and challenging scenarios, and the benchmark results
are presented.

Figure 2:  The system architecture of the proposed state estimator. Note that
the camera modules can be of mixed types.

##  II Methodology

The entire system architecture is depicted in Fig. 2. The images, accompanied
by depth if using RGBD cameras, are sent to the visual front ends and the
processed measurements are subsequently coordinated by the front end
coordinator. The coordinator dynamically redistributes the number of features
processed by each front end based on the collected features, as well as
determines whether the measurements are forwarded to the sliding window in the
back end optimization module according to the priority. The back end obtains
the visual and depth measurements, as well as the pre-integration results from
the raw IMU input to output the camera and IMU rate odometries at 30 and 500
Hz after optimization.

###  II-A Front End

The visual front end adheres to a standard procedure which includes feature
detection, tracking and outlier rejection, similar to the methodologies
established by VINS-Mono [3] and VINS-Fusion [8], while the front ends are
running in parallel with each front end thread handling a separate camera
module. The extracted visual measurements, along with the corresponding depth
measurements (when using RGBD cameras), are firstly sent to the front end
coordinator preceding the back end optimization. The IMU front end performs
pre-integration and directly outputs the high rate odometry based on the
latest optimization results.

###  II-B Front End Coordinator

####  II-B1 Feature Number Allocation

Considering the different feature qualities caused by the varying captured
scenes from cameras facing distinct directions , it is inefficient to treat
the cameras equally. To make effective use of the computation resources, the
maximum extracted feature number from images of each camera is dynamically
allocated according to the scene. In particular, given the total maximum
feature number $FN$ we allocate $fn_{i}$ features for camera $i$ according to
the tracked feature number from the last frame $tfn_{i}$:

$fn_{i}=\frac{tfn_{i}}{\sum\limits_{i=0}^{N}tfn_{i}}FN.$ (1)

Note that by dynamically adjusting the maximum feature number of each camera,
the feature tracking rate will converge to the same across the cameras,
meaning that when a front end has high feature tracking rate, larger maximum
feature number will be allocated to it.

####  II-B2 Frame Priority Coordinator

Since in some scenarios, not all the frames are necessary to be inserted into
the sliding window for optimization, for instance when a camera is obstructed,
or the time interval between two frames is excessive compared with others, a
frame priority coordinator is required to handle the priority among the
cameras so as to make efficient use of the computation resources. The priority
of a frame of camera $i$ depends on both the feature and time interval $\delta
t_{i}$ since the last frame from camera $i$ was received. The feature priority
$P_{fi}$ is determined by the ratio between the current maximum feature number
of camera $i$ $fn_{i}$ and the total maximum feature number $FN$ :

$P_{fi}=\frac{fn_{i}}{FN},$ (2)

and the frame time interval priority $P_{ti}$ is formulated as:

$P_{ti}=e^{-k\delta t_{i}},$ (3)

where $k$ is a positive constant. The coordinator waits for the frame with
either the highest feature priority to maintain consistent feature tracking
quality or the highest time priority to preclude camera failures and forwards
the corresponding measurements to the back end for optimization.

###  II-C Back End Optimization

Figure 3:  A schematic of the sliding window incorporating IMU data and visual
(including depth) data for optimization.

In the back end optimization, we extend the formulation from our previous work
[3, 8] to accommodate multiple asynchronous cameras. As depicted in Fig. 3,
the accepted frames from the cameras are chronologically ordered inside the
sliding window according to their time stamps for optimization with a full
state vector $\mathcal{X}$ defined as:

$\displaystyle\mathcal{X}$
$\displaystyle=\left[\mathbf{x}_{0},\mathbf{x}_{1},\cdots\mathbf{x}_{n},\lambda_{0},\lambda_{1},\cdots\lambda_{l},\mathbf{x}_{c_{0}},\mathbf{x}_{c_{1}},\cdots,\mathbf{x}_{c_{N-1}}\right]$
(4) $\displaystyle\mathbf{x}_{i}$
$\displaystyle=\left[\mathbf{p}_{i}^{w},\mathbf{v}_{i}^{w},\mathbf{R}_{i}^{w},\mathbf{b}_{a},\mathbf{b}_{g}\right],i\in[0,n]$
$\displaystyle\mathbf{x}^{c}_{k}$
$\displaystyle=\left[\mathbf{p}_{c_{k}}^{b},\mathbf{R}_{c_{k}}^{b},t_{d_{k}}\right],k\in[0,N-1],$

where $\mathbf{x}_{i}$ is the $i$-th IMU and camera states consists of
position, velocity, rotation as well as acceleration and gyroscope biases,
$\lambda_{j}$ denotes the inverse depth of the $j$-th feature upon its initial
observation, and $\mathbf{x}^{c}_{k}$ encompasses of the extrinsic
translation, rotation and the time offset relative to the IMU of the $k$-th
camera. The optimization objective is formulated similarly as the combination
of the prior factor, the IMU propagation factor and the visual (depth) factor:

$\displaystyle\min_{\mathcal{X}}\\{\underbrace{\left\|\mathbf{e}_{p}-\mathbf{H}_{p}\mathcal{X}\right\|^{2}}_{\text{prior
factor }}$
$\displaystyle+\underbrace{\sum_{k\in\mathcal{B}}\left\|\mathbf{e}_{\mathcal{B}}\left(\mathbf{z}_{k+1}^{k},\mathcal{X}\right)\right\|_{\mathbf{P}_{k+1}^{k}}^{2}}_{\text{IMU
propagation factor }}$ (5)
$\displaystyle+\underbrace{\sum_{(l,j)\in\mathcal{C}}\left\|\mathbf{e}_{\mathcal{C}}\left(\mathbf{z}_{l}^{j},\mathcal{X}\right)\right\|_{\mathbf{P}_{l}^{j}}^{2}}_{\text{visual
(depth) factor }}\\}.$

The detailed formulation can be found in [3], while a depth (re-projection)
error is integrated to facilitate RGBD cameras. The prior factor originates
from the marginalization of the frames, which follows a different strategy
from preceding research, as illustrated in Fig. 4. Upon the arrival of a new
frame from camera $i$, the last frame from camera $i$ is checked. If it is a
keyframe, the most outdated frame in the sliding window is marginalized,
regardless of the originating camera. Otherwise, the last frame from camera
$i$ is thrown. This strategy is able to handle uneven frames from multiple
cameras and cope with the malfunction of certain cameras.

Figure 4:  An illustration of the marginalization strategy.

##  III Experiment and Results

###  III-A Experiment Setup

(a) The custom-built quadrotor platform equipped with three RGBD cameras.

(b) Replace the top RGBD camera by a stereo camera.

Figure 5:  The quadrotor deployed in experiments. The system is compatible
with mixed types of monocular, RGBD, and stereo camera modules.

(a) Cover the top camera with a lid.

(b) Unplug the top camera.

(c) Plug the front camera.

(d) Trajectory result.

Figure 6:  The procedure and comparison of the trajectory results against the
ground truth during the camera failure and recovery scenario.

The evaluation of the proposed state estimator is conducted using a custom-
built quadrotor platform depicted in Fig. 5. The quadrotor is equipped with
three Intel Realsense L515 RGBD cameras, while in particular experiments, the
top RGBD camera is replaced with an Intel Realsense D435 stereo camera to
verify the performance on mixed types of cameras. The data from a BMI088 IMU
embedded in the NxtPX4 flight controller is adopted throughout the test
flights. All the computations are performed on an Nvidia Jetson Orin NX
onboard computer. The experiments are conducted in four scenarios: camera
failure and recovery shown in Fig. 6, wall inspection shown in Fig. 7(a),
flights employing mixed types of camera modules on the quadrotor in Fig. 5(b),
and vent pipe inspection shown in Fig. 1.

TABLE I: Benchmark results on the estimated trajectories Seq. | Multiple cameras | Single camera
---|---|---
Proposed | W/O feature allocation | Front | Top | Down
ATE(m) | RPE(m) | ATE(m) | RPE(m) | APE(m) | RPE(m) | ATE(m) | RPE(m) | ATE(m) | RPE(m)
failure & recovery | 0.07711 | 0.00042 | 2.45813 | 0.00160 | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
wall inspection | 0.08488 | 0.00070 | 0.28015 | 0.00077 | 0.44229 | 0.00284 | 3.57276 | 0.00065 | $\times$ | $\times$
mixed camera types | 0.07596 | 0.00076 | 2.02272 | 0.00306 | 0.17287 | 0.00094 | 0.11617 | 0.00102 | $\times$ | $\times$
$\times$: fail. Bold: best results. |  |  |  |  |  |  |  |  |

(a) Snapshot of the scenario with scarce features for stable tracking in the
marked areas.

(b) Trajectory result.

(c) Features from the front camera.

(d) Features from three cameras using the proposed method.

Figure 7:  The scene and the comparison of the trajectory results of the
proposed method using three cameras and using solely the front camera with the
ground truth and the features extracted at the circled position from the
front, top, and bottom images in the wall inspection scenario. The quantity of
allocated features is indicated on the lower left of each image, with the
feature point color gradient representing tracking duration from blue
(shortest) to red (longest).

###  III-B Result and Analysis

(a) Trajectory results.

(b) The features without feature allocation.

(c) The features using the proposed method.

Figure 8:  The comparison of the trajectory results of the proposed method and
the method without feature allocation with the ground truth and the features
extracted at the circled position on the front, top, and bottom images in the
mixed camera types configuration scenario. The quantity of allocated features
is indicated on the lower left of each image, with the feature point color
gradient representing tracking duration from blue (shortest) to red (longest).

During the failure and recovery scenario, the quadrotor first takes off with
only its top and bottom cameras. The robustness of the system is tested
through a sequence of procedures consisting of covering the top camera with a
lid, removing the lid, unplugging the top camera, and finally plugging the
front camera during the flight. As evidenced by Fig. 6(d), the proposed system
maintains functionality amid camera failures, exhibiting decent estimation
errors, and the recovered front camera can be successfully added into the
estimation, demonstrating the superior robustness, which is unattainable by
adopting single cameras.

The trajectory result and comparison with a solitary front camera during the
wall inspection scenario is shown in Fig. 7(b). When the single front camera
faces the black wall during take-off, we notice a conspicuous trajectory drift
of the estimated trajectory due to the lack of stable tracking features (see
Fig. 7(c)), while the proposed method using multiple cameras is capable of
handling this case with stable feature tracking using the top and bottom
cameras (as shown in Fig. 7(d)).

The trajectory result and comparison with the ablation of dynamic feature
allocation in flights with mixed camera types configuration is shown in Fig.
8(a). The method lacking dynamic feature allocation is prone to substantial
drift during rapid yaw movements, particularly apparent when wasting
unnecessary features on feature-poor walls (see Fig. 8(b)). Conversely, the
proposed method copes effectively with this challenging scenario buttressed by
its dynamic feature allocation strategy, as shown in Fig. 8(c).

The efficacy and robustness of the proposed method are further corroborated
during the complex task of aerial vent pipe inspection, as shown in Fig. 1,
reiterating its potential for various practical applications.

The benchmark trajectory estimation results for scenarios involving failure
and recovery, wall inspection, and mixed camera types are provided in Tab. I.
Examination of the table reveals that the proposed method outperforms single-
camera approaches in terms of accuracy across all three scenarios,
illustrating the advantage of employing multiple cameras. Additionally, the
proposed method surpasses the performance of the ablation of dynamic feature
allocation version in terms of accuracy, further proving the efficacy of the
strategy.

##  IV Conclusion

In this paper, we propose a robust feature-aware multi-camera-IMU state
estimator for asynchronous camera modules. The estimator encompasses parallel
front ends, a front end coordinator and a back end optimization. It makes
efficient use of input frames by implementing a dynamic feature number
allocation and a frame priority coordination strategy. The superior robustness
and performance of the estimator is validated through real-flight experiments
in various challenging scenarios.

## References

  * [1] C. Campos, R. Elvira, J. J. G. Rodríguez, J. M. Montiel, and J. D. Tardós, “Orb-slam3: An accurate open-source library for visual, visual–inertial, and multimap slam,” _IEEE Trans. Robot. (TRO)_ , vol. 37, no. 6, pp. 1874–1890, 2021.
  * [2] S. Leutenegger, S. Lynen, M. Bosse, R. Siegwart, and P. Furgale, “Keyframe-based visual–inertial odometry using nonlinear optimization,” _The International Journal of Robotics Research_ , vol. 34, no. 3, pp. 314–334, 2015.
  * [3] T. Qin, P. Li, and S. Shen, “Vins-mono: A robust and versatile monocular visual-inertial state estimator,” _IEEE Trans. Robot. (TRO)_ , vol. 34, no. 4, pp. 1004–1020, 2018.
  * [4] L. Zhang, D. Wisth, M. Camurri, and M. Fallon, “Balancing the budget: Feature selection and tracking for multi-camera visual-inertial odometry,” _IEEE Robot. Autom. Ltr. (RA-L)_ , vol. 7, no. 2, pp. 1182–1189, 2021\.
  * [5] J. Jaekel, J. G. Mangelson, S. Scherer, and M. Kaess, “A robust multi-stereo visual-inertial odometry pipeline,” in _Proc. of the IEEE/RSJ Intl. Conf. on Intell. Robots and Syst.(IROS)_. IEEE, 2020, pp. 4623–4630.
  * [6] Y. He, H. Yu, W. Yang, and S. Scherer, “Towards robust visual-inertial odometry with multiple non-overlapping monocular cameras,” in _Proc. of the IEEE/RSJ Intl. Conf. on Intell. Robots and Syst.(IROS)_. IEEE, 2022, pp. 9452–9458.
  * [7] A. J. Yang, C. Cui, I. A. Bârsan, R. Urtasun, and S. Wang, “Asynchronous multi-view slam,” in _Proc. of the IEEE Intl. Conf. on Robot. and Autom. (ICRA)_. IEEE, 2021, pp. 5669–5676.
  * [8] T. Qin, J. Pan, S. Cao, and S. Shen, “A general optimization-based framework for local odometry estimation with multiple sensors,” 2019.


SR wants to thank David Bertrand and the AIAO team at Stellantis for their work on the software and hardware infrastructure
used for this work.


Observe that each connected component of $\G_n(\mu \gamma c_n^{-1})$ is the union of connected components of $\G_n(0)$. More precisely, we have the equivalence relation $\sim_{\mu \gamma/c_n}$ on the connected components $\cC_n^0(j)$ and each connected component $\cC_n(i)$ is the union of sets in an equivalence class. A similar statement holds for the connected components of the larger graph $\overline{\G}_n(\mu\gamma c_n^{-1})$.

We turn this into two graphs as follows. Let $\sG_n = \sG_n(\mu)$ be the graph on $\N$ with $i\sim j$ if and only if $\cC_n^0(i)\sim_{\mu\gamma c_n^{-1}} \cC_n^0(j)$. Similarly, let $\overline{\sG}_n = \overline{\sG}_n(\mu)$ be the graph on $\N$ such that $i\sim j$ if and only if there is an edge a vertex in $\cC_n^{0}(i)$ and a vertex in $\cC_n^{(0)}(j)$ in the modified graph process $\overline{\G}_n(\mu\gamma c_n^{-1})$. We assign mass $X_{n,i}$ to the vertex $i$ of $\sG_n$ and $\overline{\sG}_n$. With this simplification, the ordered vector of component sizes $\ord(\#\cC_n(j);j\ge 1)$ (resp. $\ord(\#\overline{\cC}_n(j);j\ge1)$) of $\G_n(\mu\gamma c_n^{-1})$ (resp. $\overline{\G}_n(\mu\gamma c_n^{-1})$) is equal to the ordered vector of component masses of $\sG_n$ (resp. $\overline{\sG}_n)$).

Moreover, Lemma <ref> implies that

\begin{align*}
\PR(i\sim j\textup{ in }\overline{\sG}_n) = 1-\exp\left(- b_n^{-1} Y_{n,i} b_n^{-1}Y_{n,j} \mu (1+o(1))\right)
\end{align*}
and we can use the $\xi$-coupling to couple the graphs $\overline{\sG}_n$ over the index $n$. With this coupling, we then have

\begin{equation*}
\overline{\sG}_n\rightsquigarrow \sW^{G}(\bX,\bY,\mu).
\end{equation*}
Appealing to Lemma <ref> we see that the ordered vector of component masses, $\overline{\bZ}_n$, of $\overline{\sG}_n$ satisfies

\begin{equation*}
b_n^{-1} \overline{\bZ}_n\weakarrow \bZ \overset{d}{=} \MC_2(\bX,\bY,\mu).
\end{equation*}
where $\bZ$ is the component masses of $\sW^G(\bX,\bY,\mu)$. Finally, $\sG_n\subset \overline{\sG}_n$ and

\begin{equation*}
\PR(i\sim j\textup{ in } {\sG}_n) \longrightarrow 1-\exp(-Y_iY_j \mu) = \PR(i\sim j\textup{ in } \sW^G(\bX,\bY,\mu)).
\end{equation*}
Hence, Proposition <ref> implies the desired result.

§ PROOF OF (<REF>) IN LEMMA <REF>

Recall $M_n(t) = \frac{1}{a_n}\sum_{i=m+1}^n d_i^{(w)}\left(1_{[\eta_i\le t]} -\frac{d_i^{(w)}t}{\ell_n^{(w)}-2Tb_n} \right)$ and by <cit.> that $M_n$ is an $\F_l$ super-martingale starting from $M_n(0) = 0$. Using (<ref>), we have for all $n$ large and all $t\le Tb_n$

\begin{align*}
|\E&[M_n(t)]|= -\E[M_n(t) ] = \frac{1}{a_n} \sum_{i=m+1}^n d_i^{(w)}\left(\frac{d_i^{(w)} t}{\ell_n-2Tb_n} - \PR(\eta_i\le t)\right)\\
&\le \frac{t}{a_n}\sum_{i=m+1}^n d_i^{(w)}\left(\frac{d_i^{(w)} }{\ell_n-2Tb_n} - \frac{d_i^{(w)}}{\ell_n} + \frac{(d_i^{(w)})^2Tb_n}{\ell_n^2} \right)\\
&\le \frac{Tb_n}{a_n}\sum_{i=m+1}^n d_i^{(w)} \left(\frac{2Tb_n d_i^{(w)}}{\ell_n(\ell_n-2Tb_n)}+ \frac{(d_i^{(w)})^2Tb_n}{\ell_n^2} \right)\\
&\le \frac{2(Tb_n)^2}{a_n} \sum_{i=m+1}^n \frac{(d_i^{(w)})^2}{\ell_n(\ell_n-2Tb_n)}+ \frac{(d_i^{(w)})^3}{\ell_n^2},
\end{align*}

where in second to last line last line we used $t\le Tb_n$ and $\frac{1}{x}-\frac{1}{x-a} = \frac{a}{x(x-a)}$.
For all large $n$, $\ell_n - 2Tb_n > \frac{1}{2}\ell_n$, and so we can write

\begin{align*}
|\E[M_n(t)]|&\le \frac{4(Tb_n)^2}{a_n \ell_n^2} \sum_{i=m+1}^n \left((d_i^{(w)})^2 + (d_i^{(w)})^3\right).
\end{align*}

Using $\ell_n = \Theta(n) = \Theta(a_nb_n)$ under Assumption <ref>(<ref>), we have get $\frac{4T^2 b_n^2}{a_n\ell_n^2} = \Theta(a_n^{-3})$ and so Assumption <ref>(<ref>) implies

\begin{align}\label{eqn:EMno1}
|\E[M_n(t)]|&= \Theta\left({a_n^{-3}}\right)  \sum_{i=m+1}^n (d_i^{(w)})^2+ (d_i^{(w)})^3 = o(1).
\end{align}
Indeed, the $(d_i^{(w)})^2$ term is simply Assumption <ref>(<ref>). The $(d_i^{(w)})^2$ sum is also $o(1)$ as $n\to\infty$ because $\sum_{i=m+1}^n (d_i^{(w)})^2 = O(n)$ by Assumption <ref>(<ref>) and $a_n^3 = L(n) n^{{3}/({\tau-1})} \gg n$ as $\tau\in(3,4)$.

Recall (<ref>). Observe that by (<ref>) and Assumption <ref>(<ref>) that for all $n$ large and uniformly in $i\in[n]$ and $t\le Tb_n$

\begin{align*}
\Var&(1_{[\eta_i\le t]})  = \PR(\eta_i\le t) \le \left( \frac{d_i^{(w)}}{\ell_n-2Tb_n} + \frac{(d^{(w)}_i)^2}{(\ell_n-2Tb_n)^2} \right) t\\
&\le \frac{d_i^{(w)} t}{\ell_n-2Tb_n}  \left(1+\sup_{i} \frac{d_i^{(w)}}{\ell_n-2Tb_n}\right) = \Theta(1)\frac{d_i^{(w)}(Tb_n)}{n}(1+o(1))  \le \Theta(1)\frac{d_i^{(w)}}{a_n},
\end{align*}
where we used $a_nb_n = n$. We also have, using negative correlation of the Bernoulli random variables $1_{[\eta_i\le b_nt]}$, that for all $t\le Tb_n$

\begin{align}\label{eqn:varMno1}
\Var(M_n(t)) &\le \sum_{i=m+1}^n \frac{(d_i^{(w)})^2}{a_n^2} \Var(1_{[\eta\le t]})  = \Theta(1)\sum_{i = m+1}^n \frac{(d_i^{(w)})^3}{a_n^3}  =o(1),
\end{align}
where the last equality is by Assumption <ref>(<ref>).

Note that for any random variable $X$ with finite variance we have

\begin{equation*}
\E[|X|] \le \sqrt{\E[X^2]} = \sqrt{\Var(X)+ \E[X]^2} \le \sqrt{\Var(X)} + |\E[X]|.
\end{equation*}
In particular, since we have shown $\Var(M_n(t)) = o(1)$ in (<ref>) and $\E[M_n(t)] = o(1)$ in (<ref>) we get

\begin{equation*}
\E[|M_n(Tb_n)|] = o(1).
\end{equation*}

By Lemma 2.54.5 in [16] we can bound for any $\eps>0$

\begin{equation*}
\PR \left(\sup_{s\le Tb_n} |M_n(s)|>\eps \right) \le \frac{9}{\eps} \E[|M_n(Tb_n)|]  \longrightarrow 0.
\end{equation*}
This implies the stated result.

[1]
David Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, Ann. Probab. 25 (1997), no. 2, 812–854. 1434128

[2]
David Aldous and Vlada Limic, The entrance boundary of the multiplicative coalescent, Electron. J. Probab. 3 (1998), no. 3, 59. 1491528

[3]
Shankar Bhamidi, Nicolas Broutin, Sanchayan Sen, and Xuan Wang, Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős-Rényi random graph, arXiv e-prints (2014), arXiv:1411.3417.

[4]
Shankar Bhamidi, Souvik Dhara, Remco van der Hofstad, and Sanchayan Sen, Universality for critical heavy-tailed network models: metric structure of maximal components, Electron. J. Probab. 25 (2020), Paper No. 47, 57. 4092766

[5]
Ginestra Bianconi and Sergey Dorogovtsev, Multiple percolation transitions in a configuration model of a network of networks, Physical Review E 89 (2014), no. 6, 062814.

[6]
Patrick Billingsley, Convergence of Probability Measures, second ed., Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1999, A Wiley-Interscience Publication. 1700749

[7]
Nicolas Broutin, Thomas Duquesne, and Minmin Wang, Limits of multiplicative inhomogeneous random graphs and lévy trees: The continuum graphs, The Annals of Applied Probability 32 (2022), no. 4, 2448–2503.

[8]
David Clancy, Jr., Vitalii Konorovskyi, and Vlada Limic, Excursion representation for the degree-corrected stochastic blockmodel, In preperation.

[9]
Souvik Dhara, Remco van der Hofstad, Johan S. H. van Leeuwaarden, and Sanchayan Sen, Heavy-tailed configuration models at criticality, Ann. Inst. Henri Poincaré Probab. Stat. 56 (2020), no. 3, 1515–1558. 4116701

[10]
Souvik Dhara, Remco van der Hofstad, Johan S.H. van Leeuwaarden, and Sanchayan Sen, Critical window for the configuration model: finite third moment degrees, Electronic Journal of Probability 22 (2017), 1–33.

[11]
Jean Jacod and Albert Shiryaev, Limit Theorems for Stochastic Processes, vol. 288, Springer Science & Business Media, 2013.

[12]
Svante Janson, Susceptibility of random graphs with given vertex degrees, J. Comb. 1 (2010), no. 3-4, 357–387. 2799217

[13]
Adrien Joseph, The component sizes of a critical random graph with given degree sequence, Ann. Appl. Probab. 24 (2014), no. 6, 2560–2594. 3262511

[14]
Vitalii Konarovskyi and Vlada Limic, Stochastic block model in a new critical regime and the interacting multiplicative coalescent, Electron. J. Probab. 26 (2021), Paper No. 30, 23. 4235481

[15]
Ivan Kryven, Bond percolation in coloured and multiplex networks, Nature communications 10 (2019), no. 1, 404.

[16]
L. C. G. Rogers and David Williams, Diffusions, Markov processes, and martingales. Vol. 1, second ed., Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1994, Foundations. 1331599

[17]
Clara Stegehuis, Remco van der Hofstad, and Johan S.H. van Leeuwaarden, Epidemic spreading on complex networks with community structures, Scientific reports 6 (2016), no. 1, 29748.

[18]
, Power-law relations in random networks with communities, Physical Review E 94 (2016), no. 1, 012302.

[19]
Remco van der Hofstad, Johan S.H. van Leeuwaarden, and Clara Stegehuis, Mesoscopic scales in hierarchical configuration models, Stochastic processes and their applications 128 (2018), no. 12, 4246–4276.

[20]
Lutz Warnke, On Wormald's differential equation method, arXiv preprint arXiv:1905.08928 (2019).

[21]
Ward Whitt, Some useful functions for functional limit theorems, Mathematics of Operations Research 5 (1980), no. 1, 67–85.

[22]
Nicholas C Wormald, Differential equations for random processes and random graphs, The Annals of Applied Probability (1995), 1217–1235.


* [86] Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen tau Yih, Sinong Wang, and Jie Tang.  Blockwise self-attention for long document understanding, 2020.
  * [87] Gil D. Rabinovici.  Late-onset alzheimer disease.  Continuum (Minneapolis, Minn.), 25(1):14–33, Feb 2019.
  * [88] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners.  2019\.
  * [89] Jack W. Rae, Anna Potapenko, Siddhant M. Jayakumar, Chloe Hillier, and Timothy P. Lillicrap.  Compressive transformers for long-range sequence modelling.  In International Conference on Learning Representations, 2020.
  * [90] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He.  Zero: Memory optimizations toward training trillion parameter models.  In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’20. IEEE Press, 2020\.
  * [91] Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He.  Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’20, page 3505–3506, New York, NY, USA, 2020. Association for Computing Machinery.
  * [92] R. Reed.  Pruning algorithms-a survey.  IEEE Transactions on Neural Networks, 4(5):740–747, 1993.
  * [93] Aurko Roy*, Mohammad Taghi Saffar*, David Grangier, and Ashish Vaswani.  Efficient content-based sparse attention with routing transformers, 2020\.
  * [94] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf.  DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter.  In 5th Workshop on Energy Efficient Machine Learning and Cognitive Computing @ NeurIPS 2019, 2019.
  * [95] Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni.  Green ai.  Commun. ACM, 63(12):54–63, November 2020.
  * [96] Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li.  Efficient attention: Attention with linear complexities.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), pages 3531–3539, January 2021.
  * [97] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro.  Megatron-lm: Training multi-billion parameter language models using model parallelism, 2020.
  * [98] Avanti Shrikumar, Eva Prakash, and Anshul Kundaje.  GkmExplain: fast and accurate interpretation of nonlinear gapped k-mer SVMs.  Bioinformatics, 35(14):i173–i182, July 2019.
  * [99] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In ICLR, 2015.
  * [100] Emma Strubell, Ananya Ganesh, and Andrew McCallum.  Energy and policy considerations for deep learning in NLP.  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3645–3650, Florence, Italy, July 2019. Association for Computational Linguistics.
  * [101] Zhiqing Sun, Hongkun Yu, Xiaodan Song, Renjie Liu, Yiming Yang, and Denny Zhou.  MobileBERT: a compact task-agnostic BERT for resource-limited devices.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2158–2170, Online, July 2020. Association for Computational Linguistics.
  * [102] Ilya Sutskever, Oriol Vinyals, and Quoc V Le.  Sequence to sequence learning with neural networks.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  * [103] Mingxing Tan and Quoc Le.  EfficientNet: Rethinking model scaling for convolutional neural networks.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6105–6114. PMLR, 09–15 Jun 2019.
  * [104] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan.  Sparse Sinkhorn attention.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9438–9447. PMLR, 13–18 Jul 2020\.
  * [105] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Don Metzler.  Long range arena : A benchmark for efficient transformers.  In ICLR 2021, 2021.
  * [106] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler.  Long range arena : A benchmark for efficient transformers.  In International Conference on Learning Representations, 2021.
  * [107] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler.  Efficient transformers: A survey, 2020.
  * [108] Zoltán Tüske, George Saon, Kartik Audhkhasi, and Brian Kingsbury.  Single Headed Attention Based Sequence-to-Sequence Model for State-of-the-Art Results on Switchboard.  In Proc. Interspeech 2020, pages 551–555, 2020.
  * [109] Ramzan Kh. Umarov and Victor V. Solovyev.  Recognition of prokaryotic and eukaryotic promoters using convolutional deep learning neural networks.  PLOS ONE, 12(2):e0171410, February 2017.
  * [110] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [111] Alex Wang and Thomas Wolf.  Overview of the SustaiNLP 2020 shared task.  In Proceedings of SustaiNLP: Workshop on Simple and Efficient Natural Language Processing, pages 174–178, Online, November 2020. Association for Computational Linguistics.
  * [112] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma.  Linformer: Self-attention with linear complexity, 2020.  cite arxiv:2006.04768.
  * [113] Yu-Xiong Wang and Yu-Jin Zhang.  Nonnegative matrix factorization: A comprehensive review.  IEEE Transactions on Knowledge and Data Engineering, 25(6):1336–1353, 2013.
  * [114] Bryan Wilie, Karissa Vincentio, Genta Indra Winata, Samuel Cahyawijaya, Xiaohong Li, Zhi Yuan Lim, Sidik Soleman, Rahmad Mahendra, Pascale Fung, Syafri Bahar, and Ayu Purwarianti.  IndoNLU: Benchmark and resources for evaluating Indonesian natural language understanding.  In Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing, pages 843–857, Suzhou, China, December 2020. Association for Computational Linguistics.
  * [115] Genta Indra Winata.  Multilingual transfer learning for code-switched language and speech neural modeling.  arXiv preprint arXiv:2104.06268, 2021.
  * [116] Genta Indra Winata, Samuel Cahyawijaya, Zhaojiang Lin, Zihan Liu, and Pascale Fung.  Lightweight and efficient end-to-end speech recognition using low-rank transformer.  ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6144–6148, 2020.
  * [117] Genta Indra Winata, Samuel Cahyawijaya, Zhaojiang Lin, Zihan Liu, Peng Xu, and Pascale Fung.  Meta-transfer learning for code-switched speech recognition.  pages 3770–3776, July 2020.
  * [118] Genta Indra Winata, Samuel Cahyawijaya, Zihan Liu, Zhaojiang Lin, Andrea Madotto, and Pascale Fung.  Are multilingual models effective in code-switching?  In Proceedings of the Fifth Workshop on Computational Approaches to Linguistic Code-Switching, pages 142–153, Online, June 2021. Association for Computational Linguistics.
  * [119] Genta Indra Winata, Samuel Cahyawijaya, Zihan Liu, Zhaojiang Lin, Andrea Madotto, and Pascale Fung.  Are multilingual models effective in code-switching?  In Proceedings of the Fifth Workshop on Computational Approaches to Linguistic Code-Switching, pages 142–153, Online, June 2021. Association for Computational Linguistics.
  * [120] Genta Indra Winata, Samuel Cahyawijaya, Zihan Liu, Zhaojiang Lin, Andrea Madotto, Peng Xu, and Pascale Fung.  Learning Fast Adaptation on Cross-Accented Speech Recognition.  In Proc. Interspeech 2020, pages 1276–1280, 2020.
  * [121] Dongkuan Xu, Ian En-Hsu Yen, Jinxi Zhao, and Zhibin Xiao.  Rethinking network pruning – under the pre-train and fine-tune paradigm.  In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2376–2382, Online, June 2021. Association for Computational Linguistics.
  * [122] Qijin Yin, Mengmeng Wu, Qiao Liu, Hairong Lv, and Rui Jiang.  Deephistone: a deep learning approach to predicting histone modifications.  BMC Genomics, 20(2):193, Apr 2019.
  * [123] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed.  Big bird: Transformers for longer sequences.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17283–17297. Curran Associates, Inc., 2020.
  * [124] Wei Zhang, Lu Hou, Yichun Yin, Lifeng Shang, Xiao Chen, Xin Jiang, and Qun Liu.  TernaryBERT: Distillation-aware ultra-low bit BERT.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 509–521, Online, November 2020. Association for Computational Linguistics.
  * [125] Jian Zhou and Olga G Troyanskaya.  Predicting effects of noncoding variants with deep learning–based sequence model.  Nature Methods, 12(10):931–934, August 2015.
  * [126] Xiaopu Zhou, , Yu Chen, Kin Y. Mok, Timothy C. Y. Kwok, Vincent C. T. Mok, Qihao Guo, Fanny C. Ip, Yuewen Chen, Nandita Mullapudi, Paola Giusti-Rodríguez, Patrick F. Sullivan, John Hardy, Amy K. Y. Fu, Yun Li, and Nancy Y. Ip.  Non-coding variability at the APOE locus contributes to the alzheimer’s risk.  Nature Communications, 10(1), July 2019.


# Optimal Hashing in External Memory††thanks: Supported by NSF CCF 1637458,
NIH 1 U01 CA198952-01, a NetAPP Faculty Fellowship and a gift from Dell/EMC.

Alex Conway
Rutgers University
<EMAIL_ADDRESS>Martín Farach-Colton
Rutgers University
<EMAIL_ADDRESS>Philip Shilane
Dell EMC
<EMAIL_ADDRESS>
###### Abstract

Hash tables are a ubiquitous class of dictionary data structures. However,
standard hash table implementations do not translate well into the external
memory model, because they do not incorporate locality for insertions.

Iacono and Pătraşu established an update/query tradeoff curve for external
hash tables: a hash table that performs insertions in $O(\lambda/B)$ amortized
IOs requires $\Omega(\log_{\lambda}N)$ expected IOs for queries, where $N$ is
the number of items that can be stored in the data structure, $B$ is the size
of a memory transfer, $M$ is the size of memory, and $\lambda$ is a tuning
parameter.

They provide a hashing data structure that meets this curve for $\lambda$ that
is $\Omega(\log\log M+\log_{M}N)$. Their data structure, which we call an _IP
hash table_ , is complicated and, to the best of our knowledge, has not been
implemented.

In this paper, we present a new and much simpler optimal external memory hash
table, the _Bundle of Arrays Hash Table_ (BOA). BOAs are based on size-tiered
LSMs, a well-studied data structure, and are almost as easy to implement. The
BOA is optimal for a narrower range of $\lambda$. However, the simplicity of
BOAs allows them to be readily modified to achieve the following results:

  * •

A new external memory data structure, the _Bundle of Trees Hash Table_ (BOT),
that matches the performance of the IP hash table, while retaining some of the
simplicity of the BOAs.

  * •

The _cache-oblivious Bundle of Trees Hash Table_ (COBOT), the first cache-
oblivious hash table. This data structure matches the optimality of BOTs and
IP hash tables over the same range of $\lambda$.

##  1 Introduction

Dictionaries are among the most heavily used data structures. A dictionary
maintains a collection of key-value pairs
$\mathcal{S}\subseteq\mathcal{U}\times\mathcal{V}$, under operations111We do
not consider dictionaries that also support the succ$(x,\mathcal{S})$ and
pred$(x,\mathcal{S})$. succ$(x,\mathcal{S})$ return $\min\\{y|y>x\land
y\in\mathcal{S}\\}$ and pred$(x,\mathcal{S})$ is defined symmetrically.
insert$(x,v,\mathcal{S})$, delete$(x,\mathcal{S})$, and
query$(x,\mathcal{S})$, which returns the value corresponding to $x$ when
$x\in S$. When data fits in memory, there are many solutions to the dictionary
problem.

When data is too large to fit in memory, comparison-based dictionaries can be
quite varied. They include the Bε-tree [9], the write-optimized skip list [7],
and the cache-optimized look-ahead array (COLA) [5, 6, 4]. All of these data
structures have been deployed extensively, and their best variants are optimal
in the _external-memory comparison model_ in that they match the bound
established by Brodal and Fagerberg [9] who showed that for any dictionary in
this model, if insertions can be performed in
$O\left(\frac{\lambda\log_{\lambda}N}{B}\right)$ amortized IOs, then there
exists a query that requires at least $\Omega(\log_{\lambda}N)$ IOs. This
trade off has since been extended in several ways [1].

In this paper, we consider the dictionary problem without restriction to the
comparison model, and in particular, we consider external-memory hashing. This
allows for a better insertion/query trade off. Iacono and Pǎtraşcu showed:

######  Theorem 1 ([14]).

If insertions into an external memory dictionary can be performed in
$O\left(\lambda/B\right)$ amortized IOs, then queries require an expected
$\Omega(\log_{\lambda}N)$ IOs.

They further describe an external-memory hashing algorithm, which we refer to
here as the _IP hash table_ , that performs insertions in
$O\left(\frac{1}{B}\left(\lambda+\log_{\frac{M}{B}}N+\log\log N\right)\right)$
IOs and queries in $O(\log_{\lambda}N)$ IOs w.h.p. Therefore, for
$\lambda=\Omega\left(\log_{M/B}N+\log\log{N}\right)$, the IP hash table meets
the tradeoff curve of Theorem 1 and is thus optimal.

In external memory hashing, we can assume that keys are hashed, that is, that
they are uniformly distributed and satisfy some independence properties. The
IP hash table and the following results assume that the hash function (and
therefore the hashed keys) used is $\Theta(\log N)$-independent.

The base result of this paper is a simple external-memory hashing scheme, the
_Bundle of Arrays Hash Table_ (BOA), that meets the optimal Theorem 1 trade
off curve for large enough $\lambda$. Specifically, we show:

######  Theorem 2.

A BOA with growth factor $\lambda$ supports $N$ insertions with amortized per
entry insertion cost of
$O\left(\left(\lambda+\log_{\frac{M}{B}}N+\log_{\lambda}{N}\right)/B\right)$
IOs and query cost of $O(\log_{\lambda}{N})$ IOs w.h.p.

Thus BOAs are optimal for
$\lambda=\Omega(\log_{\frac{M}{B}}N+\log_{\lambda}{N})$. They are readily
modified to provide several variations, the most important of which is the
_Bundle of Trees Hash Table_ (BOT). BOTs are optimal for the same range of
$\lambda$ as the IP hash table:

######  Theorem 3.

A BOT with growth factor $\lambda$ supports $N$ insertions with amortized per
entry insertion cost of $O\left(\left(\lambda+\log_{\frac{M}{B}}N+\log\log
M\right)/B\right)$ IOs and a query cost of $O(\log_{\lambda}{N})$ IOs w.h.p.

We further introduce the first cache-oblivious hash table, the _Cache-
Oblivious Bundle of Trees Hash Table_ (COBOT), which matches the IO
performance of BOT and IP hash tables.

The remainder of the paper is organized as follows. Section 2.1 describes the
the properties of the hash function we use and Section 2.2 provides background
on size-tiered LSMs. Section 3 introduces the BOAs and Section 4 describes its
variant, the BOT. Section 5 adapts the BOT to the cache-oblivious model,
resulting in the COBOT.

##  2 Preliminaries

###  2.1 Fingerprints and Hashing

In order to achieve our bounds, we need $\Theta(\log N)$-wise independent hash
functions, which, once again matches IP hash tables. We note that a $k$-wise
independent hash function is also $k$-wise independent on individual bits.
Furthermore, the following Chernoff-type bound holds:

######  Lemma 1 ([21]).

Let $X_{1},X_{2},\ldots,X_{N}$ be $\lceil\mu\delta\rceil$-wise independent
binary random variables, $X=\sum_{i=1}^{N}X_{i}$ and $\mu=\textrm{E}[X]$. Then

$\textrm{Pr}(X>\mu\delta)=O\left(\frac{1}{\delta^{\mu\delta}}\right),$

for sufficiently large $\delta$.

In what follows, if the following, we use _fingerprint_ to refer to any key
that has been hashed using a $\Theta(\log N)$-wise independent hash
function.Such hash functions have a compact representation and can be
specified using $\Theta(\log N)$ words. The universe that is hashed into is
assumed to have size $\Theta(N^{k})$ for $k\geq 2$. We ignore collisions, but
these can be handled as in [15].

###  2.2 Log-structured Merge Trees

Log-structured merge trees (LSMs) are (a family of) external-memory dictionary
data structures. They come in two varieties: _level-tiered LSMs_ (LT-LSMs) and
_size-tiered LSMs_ (ST-LSMs). Both kinds are suboptimal in that they do not
meet the optimal insertion-query tradeoff [9], although the COLA [5] is an
optimal variant of the LT-LSMs. Both are popular in practice [11, 18, 20, 24,
22, 19, 13, 10, 17, 3].

An LSM consists of sets of either B-trees or sorted arrays called _runs_. In
this paper, we describe them in terms of runs, since we use runs below.

An LT-LSM consists of a cascade of levels, where each level consists of at
most one run. Each level has a _capacity_ that is $\lambda$ times greater than
the level below it, where $\lambda$ is called the _growth factor_.
222Sometimes this and related structures are analyzed with a growth factor of
$B^{\epsilon}$. The two are equivalent. We use $\lambda$ rather than
$\epsilon$ as the tuning parameter for consistency with the external-memory
hashing literature. When a level reaches capacity, it is merged into the next
level (perhaps causing a merge cascade). The amortized IO cost for insertions
is small because sequential merging is fast, although each item will
participate in $\lambda/2$ merges on average. The IO cost for a query is high
because a query must be performed indepdently on each of $O(\log_{\lambda}N)$
levels (although Bloom filters [8, 6] are used in practice to mitigate this
cost).

A ST-LSM further improves insertion IOs at the expense of queries. Each level
contains less than $\lambda$ runs. Every run on a given level has the same
size, which is $\lambda$ times larger than the runs on the level beneath it.
When $\lambda$ runs are present at a level, they are merged into one run and
placed at the next level. There are therefore $O(\log_{\lambda}N)$ levels.
Insertions are faster than in LT-LSMs because each item is only merged once on
each level. Queries are slower because each query must be perform $O(\lambda)$
times at each level, since the runs on each level are independent.

##  3 Bundle of Arrays Hashing

A _Bundle of Arrays Hash Table_ (BOA) is an external hash table based on ST-
LSMs. As a first step, we show that runs with uniformly distributed keys—for
example, hashed keys—can be searched quickly in external memory. This
immediately improves the query performance of ST-LSMs.

Interpolation search is not enough to achieve the needed improvement. We show
a balls-and-bins analysis that allows for the needed speedup.

######  Lemma 2 ([16]).

If $N$ balls are thrown into $Q=\Theta(N/\log{N})$ bins uniformly and i.i.d.,
then every bin has $\Theta(N/Q)=\Theta(\log{N})$ balls with high probability.

######  Lemma 3.

Let $A$ be a sorted array of $N$ uniformly distributed keys in the range
$[0,K)$, and assume $B=\Omega(\log N)$. Then $A$ can be written to external
memory using $O(N)$ space and $O(N/B)$ IOs so that membership in $A$ can be
determined in $O(1)$ IOs with high probability.

###### Proof.

Divide the range of keys into $N/B$ uniformly sized buckets; that is, bucket
$i$ contains keys in the range $[(i-1)KB/N,iKB/N)$. Because the keys in $A$
are distributed uniformly, and $B=\Omega(\log N)$, every bucket contains
$\Theta(B)$ keys with high probability by Lemma 2. Let $F$ be the number of
items in the fullest bucket, and write the keys in each bucket to disk in
order using $F$ space for each. Because $F=\Theta(B)$, this takes the desired
space and IOs.

Now, to find a key, compute which bucket it belongs to. A constant number of
IOs will fetch that bucket, whose address is known because all buckets have
the same size. ∎

When using a ST-LSM for hashing, we can use Lemma 3 to speed up queries:

######  Corollary 1.

If a ST-LSM contains uniformly distributed keys and has growth factor
$\lambda$, then by writing the levels as in Lemma 3, queries can be performed
in $O(\lambda\log_{\lambda}N)$ IOs. The insertion cost is unchanged:
$O\left(\frac{1}{B}\left(\log_{\lambda}N+\log_{\frac{M}{B}}N\right)\right)$
amortized IOs.

While the query performance has improved by a factor of $\log{N}$, the ST-LSM
is still off the optimal tradeoff curve of Theorem 1. In particular, setting
$\lambda^{\prime}=\log_{\lambda}N$ and assuming that
$\lambda^{\prime}=\Omega\log_{\frac{M}{B}}N$, we see that queries are at least
exponentially slower than optimal. The BOA will utilize additional structure
in order to reduce this query cost.

###  3.1 Routing Filters

The main result of this section is an auxiliary data structure, the _routing
filter_ that improves the query cost by a factor of $\lambda$ by further
exploiting the hashing of keys. From this point forward, we assume that all
keys in the data structure have already been hashed by a pairwise independent
hash function, and we refer to these hashed keys as _fingerprints_ to make
this distinction clear. This combination of techniques will yield a hashing
data structure that is optimal for some choices of $\lambda$. In subsequent
sections, we show how to achieve optimality for a wider range of $\lambda$.

The purpose of the routing filter is to indicate probabilistically, at each
level, which run contains the fingerprint we are looking for. Each level will
have its own routing filter, defined as follows. For each level $\ell$, let
$h_{\ell}$ be some number, to be specified below. It will be convenient for a
fingerprint $K$ to interpret the bits of $K$ as a string of $\log_{\lambda}$
bit characters, $K=K_{0}K_{1}K_{2}\cdots$. Let $P_{\ell}(K)=K_{0}\cdots
K_{h_{\ell}}$ be the $h_{\ell}$th prefix, the concatenation of the characters
of $K$ up to $K_{h_{\ell}}$. The routing filter $F_{\ell}$ for level $\ell$ is
a $\lambda^{h_{\ell}}$ character array, where $F_{\ell}[i]=j$ if the $j$th run
$R_{\ell,j}$ contains a fingerprint $K$ such that the $P_{\ell}(K)=i$, and no
later run $R_{\ell,j^{\prime}}$ (i.e. with $j^{\prime}>j$) contains such a
fingerprint.

We also modify each run $R_{\ell,j}$ during the merge so that each
fingerprint-value pair contains a _previous field_ of 1 additional character
used to specify the previous run containing a fingerprint with the same prefix
or $j$ to indicate no such run exists. Thus these fingerprint-value pairs now
form a singly linked list whose fingerprint share the same prefix, and the
routing filter points to the run containing the head.

During a query for a fingerprint $K$, first $F_{\ell}[P_{\ell}(K)]$ is checked
to find the latest run containing a fingerprint with a matching prefix. Once
that fingerprint-value pair is found, its previous field indicates the next
run which needs to be checked and so on until all fingerprints with matching
prefix in the level are found.

Such routing filters induce a space/cost tradeoff. The greater $h_{\ell}$ is,
the more space the table takes, but the less likely it is that many runs will
have fingerprints that collide on their prefixes. The rest of this section
shows that when $h_{\ell}$ is set to be the base $\lambda$ log of the capacity
of level $\ell$, then that yields an optimal external hash table.

Define $\beta$, the _routing table ratio_ , to be the ratio of the number of
buckets in the routing filter to the size of a run. The number of entries in a
run on level $\ell$ is $B\lambda^{\ell-1}$, so
$\beta=\lambda^{h_{\ell}}/B\lambda^{\ell-1}$. We analyze the per-level
insertion and query cost for a given $\beta$ and $\lambda$.

######  Lemma 4.

For a BOA with growth factor $\lambda$ and routing table ratio $\beta$, the
following hold:

  1. 1.

Merging a level incurs
$\Theta\left(\frac{1}{B}\left(1+\log_{\frac{M}{B}}\lambda+\beta\log_{N}{\lambda}\right)\right)$
IOs per fingerprint.

  2. 2.

Finding a fingerprint in a level takes
$\Theta\left(1+\frac{\lambda}{\beta}\right)$ IOs in expectation.

###### Proof.

  1. 1.

Merging a level requires merging together its runs as well as updating the
next level’s routing filter. Merging $\lambda$ sorted arrays takes
$\Theta\left(\frac{1}{B}\left(1+\log_{M/B}\lambda\right)\right)$ IOs per
fingerprint.

The routing filter is updated by iterating through it and the new run
sequentially. For each fingerprint $K$ appearing in the run,
$F_{\ell+1}[P_{h_{\ell+1}}(K)]$ is copied to the previous field in the run,
and $F_{\ell+1}[P_{h_{\ell+1}}(K)]$ is set to the number of the current run.
Each entry in the routing filter is a character, the routing filter has
$\beta$ characters for each new fingerprint, so it requires
$\Theta\left(\frac{\beta}{B}\log_{N}{\lambda}\right)$ IOs per fingerprint to
update sequentially.

  2. 2.

To query for a fingerprint $K$, first the routing filter is checked, which
takes $O(1)$ IOs, and then the runs with fingerprints matching the prefix of
$K$ are checked.

Given some enumeration of the fingerprints in level $\ell$, denote the $i$th
fingerprint by $K_{i}$. Let $X_{i}$ be the indicator random variable which is
1 if $P_{h_{\ell}}(K)=P_{h_{\ell}}(K_{i})$ and 0 otherwise. Because the hash
function is pairwise independent, $K$ and $K_{i}$ are uniformly distributed
and their bits are pairwise independent. Thus
$\mathrm{E}\left[X_{i}\right]\leq\frac{1}{\lambda^{h_{\ell}}}$. The expected
number of fingerprints in the level with prefix $P_{h_{\ell}}(K)$ is at most
$\sum_{i=1}^{B\lambda^{\ell}}\mathrm{E}\left[X_{i}\right]\leq\frac{B\lambda^{\ell}}{\lambda^{h_{\ell}}}=\frac{\lambda}{\beta}.$
By Lemma 3, each of these fingerprints can be found and checked in $O(1)$ IOs.
Thus, the expected per-level query cost is
$O\left(1+\frac{\lambda}{\beta}\right)$.

∎

######  Lemma 5.

A BOA with growth factor $\lambda$ and routing table ratio $\beta$ has
insertion cost
$O\left(\frac{1}{B}\left(\beta+\log_{\frac{M}{B}}N+\log_{\lambda}N\right)\right)$
and query cost
$O\left(\left(1+\frac{\lambda}{\beta}\right)\log_{\lambda}{N}\right)$.

###### Proof.

Because a BOA has $\log_{\lambda}N$ levels, this follows immediately from
Lemma 4. ∎

So for a fixed $\lambda$, there is no advantage to choosing
$\beta=\omega(\lambda)$. On the other hand, $\beta=o(\lambda)$ is suboptimal,
because then choosing $\beta^{\prime}=\lambda^{\prime}=\beta$ changes a linear
factor in the query cost to a logarithmic one. Therefore, it is optimal to
choose $\beta=\Theta(\lambda)$, and in what follows we will fix
$\beta=\lambda$. Now the main theorem follows immediately:

See 2

Thus, a BOA is optimal for large enough $\lambda$:

######  Corollary 2.

Let $B$ be a BOA with growth factor $\lambda$ containing $N$ entries. If
$\lambda=\Omega\left(\log_{\frac{M}{B}}{N}+\frac{\log{N}}{\log\log{N}}\right),$
then $B$ is an optimal unsorted dictionary.

Note that the condition that $\lambda=\Omega(\log_{M/B}{N})$ is related to the
permutation bound [2]. This is because BOAs and their variations support some
form of successor operation for the order of the fingerprints (the hashed
order of the keys).

##  4 Bundle of Trees Hashing

In order for a BOA to be an optimal dictionary, its growth factor $\lambda{}$
must be $\Omega(\log{N}/\log\log{N})$. Otherwise, the cost of insertion is
dominated by the cost of merging, which in slow because it effectively sorts
the fingerprints using a $\lambda$-ary merge sort. In this section, we present
the _Bundle of Trees Hash Table_ (BOT), which is a BOA-like structure. A BOT
stores the fingerprints in a log in the order in which they arrive. Each level
of the BOT is like a level of a BOA, where the bundle of arrays on each level
is replaced by an search structure on the log (the _routing tree_) and a data
structure needed to merge routing trees (the _character queue_). The character
queue performs a delayed sort on the characters needed at each level, thus
increasing the arity of the sort and decreasing the IOs.

A BOT has $s=\lceil\log_{\lambda}N/B\rceil$ levels, each of which consists of
at most one routing tree where the root has degree less than $\lambda$ and all
internal nodes have degree $\lambda$. Each node of a routing tree contains a
routing filter, which functions similarly to the routing filters in Section 3.
In a BOT, the routing filter takes as input a fingerprint and outputs a set of
pointers to the children which may contain it, though some of these may be
false positives. It also returns some auxiliary information discussed below,
which together with the child pointer is referred to as the _sketch_ of the
fingerprint.

Each leaf points to a block of $B\log_{\lambda}N$ fingerprints in the log; the
reason for using blocks of this size will be explained in Section 4.2. The
deepest level $s$ indexes the beginning of the fingerprint log with a tree of
depth $s$, the next level then indexes the next section and so forth.
Insertions are appended to the log until they form a block, at which point
they are added to the tree in the 1st level of the BOT.

Querying a BOT. A query to the BOT for a fingerprint $K$ is performed
indepedently at each level, beginning at the root of each routing tree. At a
routing node of height $h$ in a tree, the routing filter is queried. Whereas
the routing filter in a BOA returns only the last array containing a
fingerprint with a given prefix $P_{h}(K)$, BOTs use a _refined routing
filter_ that returns a full list of all the children with such a fingerprint.
The details of the refined routing filter are left for Section 4.1. The query
is then passed to each of these children, until it reaches a block of the log,
which is then searched in full. In this way queries are “routed” down the tree
on each level to the part of log where the fingerprint and its associated
value are. In addition, as queries descend the routing tree, they may generate
false positives which are likewise routed down towards the log.

An issue that arises from this querying algorithm is that if a query generates
a false positive in a node of height $h$, that is, there is a fingerprint
$K^{\prime}$ with $P_{h}(K)=P_{h}(K^{\prime})$, then in the child containing
$K^{\prime}$, the shorter prefixes will also match, i.e.
$P_{h-1}(K)=P_{h-1}(K^{\prime})$. Therefore false positives will always
propagate down the routing tree and at each subsequent node may in turn
generate more false positives. To prevent this, the routing filter of each
node of the routing tree keeps, for each fingerprint $K$, an additional _check
character_ taken from the tail of K. Positive queries must also match this
character, and nodes of different heights use different parts of the
fingerprint for the check characters so that the probabilities of two
fingerprints matching on different levels are independent. Check characters
are explained further in Section 4.1.

Inserting into a BOT. When a level $i$ in the BOT fills, its routing tree is
merged into the routing tree of level $i+1$, thus increasing the degree of the
target routing tree by 1 (and perhaps filling level $i+1$, which triggers a
merge of level $i+1$ into $i+2$, and so on). The merge of level $i$ into level
$i+1$ consists of adding the prefix-sketch pairs of the fingerprints from
level $i$ to the routing filter of the root on level $i+1$. The child pointers
of these pairs will point to the root of the formerly level-$i$ routing tree,
so it becomes a child of the root of the level $i+1$ routing tree, although it
isn’t moved or copied. In this way, a BOT resembles an LT-LSM, described in
Section 2.2.

In order to add a fingerprint $K$ from level $i$ to the root routing filter on
level $i+1$, the prefix $P_{i+1}(K)$ must be known. However, the root routing
filter on level $i$ only stores the prefix $P_{i}(K)$ for each fingerprint $K$
it contains, so that in particular the last character of $P_{i+1}(K)$ is
missing. As described in Section 4.2, each level has a character queue, which
provides this character, as well as the check characters, in order to merge
the routing trees efficiently.

By replacing the arrays of a BOA on each level by character queues, the BOT
can insert efficiently for a larger range of $\lambda{}$. Because the arrays
are no longer available to answer queries, BOTs instead use the recursively
constructed routing trees, which require some refinement over the routing
filters in BOAs. With these in place, however, query performance is optimal,
and the BOT becomes an optimal dictionary for a wider range of the parameter
$\lambda{}$, matching the range of the IP hash table [15].

###  4.1 BOT Queries

This section covers the routing tree structure in more detail. First, we cover
the specifics of check characters, and then we introduce the refined routing
filter and prove its performance characteristics.

As described above, in a BOT each false positive in a node of a routing tree
queries an additional child. Because the routing filter in the child has
shorter prefixes, that false positive will cause an entire path down the tree
to be accessed. Moreover, along the way more false positives can be generated.
Check characters are used to reduce the probability of false positives in BOTs
and short-circuit the paths that do occur.

The $i$th check character $C_{i}$ of a fingerprint $K$ is the $i$th character
from the end of the string representation of $K$. As described in Section 2.1,
we assume that the fingerprints are taken from a universe of size at least
$N^{2}$ so that the check characters do not overlap with the characters used
in the prefixes of the routing filters.

The routing filter of a node of height $h$ in a routing tree stores $C_{h}(K)$
in the sketch for each fingerprint $K$ in the filter, and when queried,
returns a list of the sketches of prefix-matching fingerprints in the order
that they appear in the log.

Now, the query only proceeds on those children whose check characters match
the check character $C_{h}(K)$. Since the characters of the fingerprint are
uniformly distributed, the check character of each false positive matches with
probability $1/\lambda$. Moreover, the characters of each level are non-
overlapping, so for fingerprints $K$, $K^{\prime}$ the event that
$V_{h}(K)=V_{h}(K^{\prime})$ is independent of the event that
$V_{h-1}(K)=V_{h-1}(K^{\prime})$. Therefore a false positive on a node of
height $h$ may still be eliminated in its child (of height $i-1$), short-
circuiting the paths that false positives would otherwise create.

While not strictly necessary, in order to simplify the analysis, we will
further arrange it so that false positives may only be created in the root of
the tree, and that at each level, only a $1/\lambda$ fraction of the false
positives survive in expectation. To prevent new false positives from being
generated when a query passes from a parent to a child, we also keep the _next
character_ of each fingerprint in its prefix-sketch pair stored in the routing
filter. For a fingerprint $K$ in a node of height $h$, the next character is
just the next character that follows the prefix, $P_{h}(K)$, so that its
prefix in the parent, $P_{h+1}(K)$, can be obtained. A false positive in the
children which is not in the parent will not match this next character and can
be eliminated.

When there are multiple prefix-matching fingerprints in both a parent and its
child, we would like to be able to align the lists returned by the routing
filters so that known false positives in the parent (either from check or next
characters) can be eliminated in the child. Otherwise the check character in
the child of a known false positive in the parent may match the queried
fingerprint, and therefore more than $1/\lambda$ of the false positives may
survive in expectation. To this end, we require the routing filter to return
the list of sketches of prefix-matching fingerprints in the order they appear
in the log. Then after the sketches in the child list whose next characters do
not match the parent are elimated, the remaining phrases will be in the same
order as in the parent. In this way, known false positives can also be
eliminated in the child.

Now because of the next characters, false positives may only be created in the
root of the routing tree. Each false positive in the root corresponds to a
fingerprint $K^{\prime}$ in the level. At each node on the path to
$K^{\prime}$’s location in the log, we use the ordering to determine which
returned sketch corresponds to $K^{\prime}$, so that the false positive
corresponding to $K^{\prime}$ is eliminated with probability $1/\lambda$. Thus
the query path for $K^{\prime}$ causes at most
$\sum_{i=1}^{h}1/\lambda^{i}=O\left(\frac{1}{\lambda}\right)$ node accesses.
This is independant of the number of false positives in the root. Since there
are $O(1)$ expected false positives in the root, we have shown:

######  Lemma 6.

During a query to a routing tree, the expected number of nodes accessed due to
false positives is at most $O\left(\frac{1}{\lambda}\right)$.

Refined Routing Filter.. A BOA routing filter handles prefix collisions by
returning only the last run containing the queried fingerprint and then
chaining in the runs. Because there are no longer arrays with which to chain,
the BOT routing filter, however, must handle prefix collisions itself and
return a complete ordered list of sketches for all prefix-matching
fingerprints, while having the same performance as in Section 3.1.

The idea behind the refined routing filter is to keep the prefix-sketch pairs
in a list, and use a hash table on prefixes to point queries to the
appropriate place. Each pointer may require as many as $\Omega(\log N)$ bits,
and we require the routing filter to have $O(1)$ characters per fingerprint,
so we require the hash table to use shorter prefixes so as to reduce the
number of buckets and thus reduce its footprint. In particular, it uses
prefixes which are $\log_{\lambda}\log_{\lambda}N$ characters shorter, which
we refer to as _pivot prefixes_.

The list _delta encodes_ the prefix $P_{h}(K)$ for each fingerprint $K$,
together with the sketch, $S_{h}(K)$. This means the difference between
$P_{h}(K)$ and the preceding prefix is stored, together with the sketch. In
addition, the first entry following each pivot prefix contains the full prefix
$P_{h}(K)$, rather then just the difference. Otherwise, when the hash table
routes a query to that place in the list, the full prefix wouldn’t be
computable.

We first analyze the space efficiency of a delta encoded list of a collection
of prefixes and then analyze the performance characteristics of refined
routing filters.

######  Lemma 7.

A list of delta-encoded prefixes with density $D$, that is there are $D$
prefixes in the list for every possible prefix, requires
$O(-\log_{\lambda}{D})$ characters per prefix.

###### Proof.

The average difference between consecutive prefixes is $1/D$. Because
logarithms are convex, the average number of characters required to represent
this difference is therefore $O(-\log_{\lambda}{D})$. ∎

Now we can prove:

######  Lemma 8.

A refined routing filter can be updated using
$O\left(\frac{\lambda\log\lambda{}}{B\log N}\right)$ IOs per new entry.

###### Proof.

Let $C$ be the capacity of the level. There are $\frac{C}{\log_{\lambda}N}$
pivot prefixes. For each pivot prefix, the hash table stores the bit position
in a list with at most $C$ entries, where $C\leq N$. Each entry is at most
$\log N$ bits, so this position can be written using $O(\log N)$ bits.

For each fingerprint in the node, the list contains $O(1)$ characters by Lemma
7, or $O(\log\lambda)$ bits. Additionally, each pivot prefix has to an initial
entry of length $O(\log N)$ bits, so the list all together uses
$O(C\log\lambda+\frac{C}{\log_{\lambda}N}\cdot\log N)=O(C\log\lambda{})$ bits.

When the refined routing filter is updated, the old version is read
sequentially and the new version is written out sequentially. $C/\lambda$
fingerprints are added at a time, so this incurs
$O\left(\frac{\lambda\log\lambda{}}{B}\right)$ IOs per entry. ∎

The refined routing filter also still performs constant IO lookups:

######  Lemma 9.

A refined routing filter performs lookups in $O(1)$ IOs in expectation.

###### Proof.

The pivot bit string of a fingerprint and its successor are accessed from the
hash table in $O(1)$ IOs. This return beginning and ending bit positions in
the list. Because the fingerprints are distributed uniformly and are pairwise
independent there are $O(\log_{\lambda}N)$ fingerprints matching the pivot
prefix in expectation. The list has $O(\log\lambda)$ bits per fingerprint, so
$O(1)$ words are fetched from the list in expectation, and hence $O(1)$ IOs. ∎

###  4.2 Character Queue

The purpose of the character queue is to store all the sketches of
fingerprints contained in a level $i$ that will be needed during a merge in
the future. When level $i$ is merged into level $i+1$, the character queue
outputs a sorted list of the delta-encoded prefix-sketch pairs of all the
fingerprints, which is used to update the root routing tree. The character
queue is then merged into the character queue on level $i+1$.

The character queue effectively performs a merge sort on the sketches. If it
were to merge all the sketches as soon as they are available, this would
consist of $\lambda$-ary merges. In order to increase the arity of the merges,
it defers merging sketches which are not needed immediately. The sketches are
collection of _series_ , by which we mean a collection of sorted runs. Each
series stores a continuous range of sketches
$S_{i}(K),S_{i+1}(K),\ldots,S_{i+j}(K)$ for each fingerprint $K$, together
with the prefix up to the first sketch, $P_{i-1}(K)$. These prefixes are delta
encoded in their run. Thus the size of an entry is determined by the number of
sketches in the range and the length of the prefix relative to the size of the
run (by Lemma 7).

The character queue tradeoff. We are faced with the following tradeoff. If the
character queue merges a series frequently, the delta encoding is more
efficent, which decreases the cost of the merging. However the arity is lower,
which increases it. The character queue uses a merging schedule which balances
this tradeoff and thus achieves optimal insertions.

The character queue merging schedule. The character queue on level $i$
contains the sketches $S_{i+1}(K),S_{i+2}(K),\ldots S_{s}(K)$ of each
fingerprint $K$ in the level. These characters are stored in a collection of
series $\\{\sigma_{j_{q}}\\}$, where $j_{q}$ is the smallest multiple of
$2^{q}$ greater than $i$. Series $\sigma_{j_{q}}$ contains the sketches
$S_{j_{q}}(K),\ldots,S_{j_{q+1}-1}(K)$. Each series consists of a collection
of sorted runs each of which stores the delta encoded prefix of each
fingerprint together with its sketches.

When level $i$ fills, the runs in the series $\sigma_{i+1}$ are merged, and
the character queue outputs the delta encoded prefix-sketch pairs,
$(P_{i+1}(K),S_{i+1}(K))$ to update the root routing filter on level $i+1$. If
$2^{\rho(i+q)}$ is the greatest power of 2 dividing $i+1$ ($\rho$ is sometimes
referred to as the _ruler function_ [23]), then $\sigma_{i+1}$ also contains
the next $2^{\rho(i+1)}-1$ sketches of each fingerprint. These are batched and
delta encoded to become runs in the series $\sigma_{j_{q}}$ for
$q=[0,\rho(i+1)]$.

This leads to the following merging pattern: $\sigma_{j}$ batches
$2^{\rho(j)}$ sketches, and has delta encoded prefixes of $2^{\rho}(j)$
characters on average, by Lemma 7. Therefore,

######  Lemma 10.

A series $\sigma_{j}$ in a character queue contains $O(2^{\rho(j)})$
characters per fingerprint.

This leads to a merging schedule where the characters per item merged on the
$j$th level is $O(2^{\rho(j)})$. Starting from 1 this is
$1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,\ldots$, which resemble the tick marks of a
ruler, hence the name ruler function.

We now analyze the cost of maintaining the character queues.

######  Lemma 11.

The total per-insertion cost to update the character queues in a BOT is
$\Theta\left(\frac{1}{B}\left(\log_{\frac{M}{B}}N+\log\log M\right)\right)$.

###### Proof.

When $\sigma_{j}$ is merged, $\lambda^{2^{\rho}(j)}$ runs are merged, which
has a cost of
$O\left(\frac{2^{\rho(j)}}{B}\left\lceil\log_{M/B}\left(\lambda^{2^{\rho}(j)}\right)\right\rceil\right)$
characters per fingerprint.

There are $\log_{\lambda}\frac{N}{B}=O(\log_{\lambda}N)$ levels, so this leads
to the following total cost in terms of characters:

$\displaystyle
O\left(\sum_{i=1}^{\log_{\lambda}N}2^{\rho(j)}\left\lceil\log_{\frac{M}{B}}\left(\lambda^{2^{\rho}(j)}\right)\right\rceil\right)$
$\displaystyle=O\left(\sum_{k=0}^{\log\log_{\lambda}N}\frac{\log_{\lambda}N}{2^{k}}\cdot
2^{k}\left\lceil\log_{\frac{M}{B}}\left(\lambda^{2^{k}}\right)\right\rceil\right)$
$\displaystyle=O\left(\log_{\lambda}N\left(\log\log M+\sum_{k=\log\log
M}^{\log\log_{\lambda}N}2^{k}\log_{\frac{M}{B}}\lambda\right)\right)$
$\displaystyle=O\left(\log_{\lambda}N\left(\log\log
M+\log_{\frac{M}{B}}N\right)\right),$

where the last equality is because the RHS sum is dominated by its last term.
Because there are $\log_{\lambda}N$ characters in a word, and all reads and
writes are performed sequentially in runs of size at lease $B$, the result
follows. ∎

The character queue is where we require that the blocks of the log have size
$B\log_{\lambda}N$, because we want the runs created when the block is added
to the first level to be at least size $B$.

###  4.3 Performance of the BOT

We can now prove Theorem 3:

See 3

###### Proof.

By Lemma 8, the cost of updating the routing filters is
$O\left(\frac{\lambda}{B}\right)$, since there are $O(\log_{\lambda}N)$
levels. This together with the cost of updating the character queues, given by
Lemma 11, is the insertion cost.

By Lemma 6, a query for fingerprint $K$ accesses an average of
$O\left(\frac{\log_{\lambda}N}{\lambda}\right)$ nodes across the routing trees
on all level due to false positives. Using Lemma 1 with $\delta=\lambda$, we
have that this is $O(\log_{\lambda}N)$ nodes w.h.p.

If $K$ is contained in the bot, then $O(\log_{\lambda}N)$ nodes are accessed
on its root-to-leaf path.

A block of the log is scanned at most once for a true positive and also
whenever a false positive from the level $i$ root survives $i$ times. The
expected number of such false positives for level $i$ is $1/\lambda^{i}$, so
the expected number across levels is $O\left(\frac{1}{\lambda}\right)$
Therefore by Lemma 1, the probability that $\omega(1)$ blocks are scanned due
to false positives is $O\left(\frac{1}{\lambda}\right)$. Each block can be
scanned in $O(\log_{\lambda}N)$ IOs, so this yields the result. ∎

It follows that:

######  Corollary 3.

Let $\mathcal{B}$ be a BOT with growth factor $\lambda$ containing $N$
entries. If $\lambda=\Omega\left(\log_{\frac{M}{B}}N+\log\log M\right)$, then
$\mathcal{B}$ is an optimal dictionary.

##  5 Cache-Oblivious BOTs

In this section, we show how to modify a BOT to be cache oblivious. We call
the resulting structure a cache-oblivious hash tree (COBOT).

Much of the structure of the BOT translates directly into the cache-oblivious
model. However, some changes are necessary. In particular, when the series of
character queues are merged, this merge must be performed cache-obliviously
using funnels [12], rather than with an (up to) $M/B$-way merge. Also, the log
cannot be buffered into sections of size $O(B\log_{\lambda}N)$, and so instead
they are buffered into sections of constant size, items are immediately added
to routing filter, and the extra IOs are eliminated by optimal caching.

When an insertion is made into a CO hash tree, its fingerprint-value pair is
appended to the log, and it is immediately inserted into level 1. Thus, the
leaves of the routing trees point to single entries in the log.

The series of the character queues must be placed more carefully as well. In
particular, for each $j$, the runs of series $\sigma_{j}$ must be laid out
back-to-back, so that even when they are short, they may be read efficiently
across the level.

The series are merged using a _partial funnelsort_. Funnelsort is a cache-
oblivious sorting algorithm that makes use of $K$-funnels [12]. A $K$-funnel
is a CO data structure that merges $K$ sorted lists of total length $N$. We
make use of the the following lemma.

######  Lemma 12 ([12]).

A $K$-funnel merges $K$ sorted lists of total length $N\geq K^{3}$ in
$O\left(\frac{N}{B}\log_{M/B}\frac{N}{B}+K+\frac{N}{B}\log_{K}\frac{N}{B}\right)$
IOs, provided the tall cache assumption that $M=\Omega(B^{2})$ holds.

The partial funnelsort used to merge $K$ runs of a series with total length
$L$ (in words) performs a single merge with a $K$-funnel if $L\geq K^{3}$ and
recursively merges the run in groups of $K^{1/3}$ runs otherwise.

######  Corollary 4.

A partial funnelsort merges $K$ runs of total word length $L$ in
$O\left(\frac{L}{B}\log_{M/B}\frac{L}{B}+\frac{L}{B}\log_{K}\frac{L}{B}\right)$
IOs, provided the tall cache assumption that $M=\Omega(B^{2})$ holds.

###### Proof.

The base case of the recursion occurs either when there is only 1 list
remaining or the remaining lists fit in memory. In any other case of the
recursion, since $L=\Omega(B^{2})$ by the tall cache assumption, the $K$ term
in Lemma 12 is dominated.

The recurrence is dominated by the cost of the funnel merges, which yields the
result. ∎

######  Theorem 4.

If $M=\Omega(B^{2})$, then a CO hash tree with $N$ entries and growth factor
$\lambda$ has amortized insertion cost
$\Theta\left(\frac{1}{B}\left(\lambda+\log\log M+\log_{M/B}N/B\right)\right)$
and query cost $\Theta\left(\log_{\lambda}N\right)$, w.h.p.

###### Proof.

We may assume that the caching algorithm sets aside enough memory that the
last $B$ items in the log, together with the subtree rooted at their least
common ancester, are cached. Thus the log is updated at a per-item cost of
$O(1/B)$.

The proof of Theorem 3 now carries over to the CO hash tree. The routing
filters are updated the same way, and the cost of updating the character
queues is unchanged, by Corollary 4.

Queries are performed as in Section 4.1, except that now the level 1 nodes
cover $O(1)$ fingerprints, but the depth of the tree is unchanged, so the cost
is the same. ∎

## References

  * [1] Peyman Afshani, Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Mayank Goswami, and Meng-Tsung Tsai.  Cross-referenced dictionaries and the limits of write optimization.  In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1523–1532. SIAM, 2017.
  * [2] Alok Aggarwal and Jeffrey Scott Vitter.  The input/output complexity of sorting and related problems.  Commun. ACM, 31(9):1116–1127, 1988.
  * [3] Apache.  Accumulo.  http://accumulo.apache.org, Last Accessed May 16, 2015, 2015.
  * [4] Michael A. Bender, Richard Cole, Erik D. Demaine, and Martin Farach-Colton.  Scanning and traversing: Maintaining data for traversals in a memory hierarchy.  In Rolf H. Möhring and Rajeev Raman, editors, Algorithms - ESA 2002, 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Proceedings, volume 2461 of Lecture Notes in Computer Science, pages 139–151. Springer, 2002.
  * [5] Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul, and Jelani Nelson.  Cache-oblivious streaming b-trees.  In Phillip B. Gibbons and Christian Scheideler, editors, SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Diego, California, USA, June 9-11, 2007, pages 81–92. ACM, 2007.
  * [6] Michael A. Bender, Martin Farach-Colton, Rob Johnson, Russell Kraner, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, and Erez Zadok.  Don’t thrash: How to cache your hash on flash.  PVLDB, 5(11):1627–1637, 2012.
  * [7] Michael A. Bender, Martin Farach-Colton, Rob Johnson, Simon Mauras, Tyler Mayer, Cynthia A. Phillips, and Helen Xu.  Write-optimized skip lists.  In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 69–78. ACM, 2017.
  * [8] Burton H. Bloom.  Space/time trade-offs in hash coding with allowable errors.  Commun. ACM, 13(7):422–426, 1970.
  * [9] Gerth Stølting Brodal and Rolf Fagerberg.  Lower bounds for external memory dictionaries.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 546–554. ACM/SIAM, 2003.
  * [10] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Michael Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber.  Bigtable: A distributed storage system for structured data.  ACM Trans. Comput. Syst., 26(2):4:1–4:26, 2008.
  * [11] Johnathan Ellis.  Leveled compaction in Apache Cassandra.  http://www.datastax.com/dev/blog/leveled-compaction-in-apache-cassandra, October 2011.  Viewed April 22, 2014.
  * [12] Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran.  Cache-oblivious algorithms.  In 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17-18 October, 1999, New York, NY, USA, pages 285–298. IEEE Computer Society, 1999.
  * [13] Apache HBase.  https://hbase.apache.org/.  Viewed April 14, 2014.
  * [14] John Iacono and Mihai Patrascu.  Using hashing to solve the dictionary problem (in external memory).  CoRR, abs/1104.2799, 2011.
  * [15] John Iacono and Mihai Patrascu.  Using hashing to solve the dictionary problem.  In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 570–582. SIAM, 2012.
  * [16] Norman Lloyd Johnson and Samuel Kotz.  Urn models and their application; an approach to modern discrete probability theory.  New York, NY (USA) Wiley, 1977.
  * [17] Avinash Lakshman and Prashant Malik.  Cassandra: a decentralized structured storage system.  Operating Systems Review, 44(2):35–40, 2010.
  * [18] LevelDB.  https://code.google.com/p/leveldb/.  Viewed April 14, 2014.
  * [19] Kai Ren and Garth A. Gibson.  TABLEFS: enhancing metadata efficiency in the local file system.  In Andrew Birrell and Emin Gün Sirer, editors, 2013 USENIX Annual Technical Conference, San Jose, CA, USA, June 26-28, 2013, pages 145–156. USENIX Association, 2013.
  * [20] RocksDB.  rocksdb.org, 2014.  Viewed April 19, 2014.
  * [21] Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan.  Chernoff-hoeffding bounds for applications with limited independence.  SIAM J. Discrete Math., 8(2):223–250, 1995.
  * [22] Russell Sears and Raghu Ramakrishnan.  blsm: a general purpose log structured merge tree.  In K. Selçuk Candan, Yi Chen, Richard T. Snodgrass, Luis Gravano, and Ariel Fuxman, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 217–228. ACM, 2012.
  * [23] Wikipedia.  Thomae’s function — Wikipedia, the free encyclopedia.  http://en.wikipedia.org/w/index.php?title=Thomae’s%20function&oldid=837510765, 2018\.  [Online; accessed 28-April-2018].
  * [24] WiredTiger.  wiredtiger.com.  Viewed April 14, 2014.