Imperial College
Londona.croquevielle22@imperial.ac.ukhttps://orcid.org/0009-0002-0101-4431
Imperial College
Londonguang.yang15@imperial.ac.ukhttps://orcid.org/0000-0001-6456-9077
Imperial College
Londonliang.liang20@imperial.ac.ukhttps://orcid.org/0000-0002-4566-6178
Imperial College
Londonali.hadian@gmail.comhttps://orcid.org/0000-0003-2010-0765 Luis
Croquevielle, Guang Yang, Liang Lian, Ali Hadian and Thomas Heinis Imperial
College Londont.heinis@imperial.ac.ukhttps://orcid.org/0000-0002-7470-2123
[100]Theory of computation Predecessor queries

# Upper Bounds for Complexity of Asymptotically Optimal Learned Indexes

Luis Alberto Croquevielle  Guang Yang  Liang Liang  Ali Hadian  Thomas Heinis

###### Abstract

Learned indexes leverage machine learning models to accelerate query answering
in databases, showing impressive practical performance. However, theoretical
understanding of these methods remains incomplete. Existing research suggests
that learned indexes have superior asymptotic complexity compared to their
non-learned counterparts, but these findings have been established under
restrictive probabilistic assumptions. Specifically, for a sorted array with
$n$ elements, it has been shown that learned indexes can find a key in
$O(\log(\log n))$ expected time using at most linear space, compared with
$O(\log n)$ for non-learned methods.

In this work, we prove $O(1)$ expected time can be achieved with at most
linear space, thereby establishing the tightest upper bound so far for the
time complexity of an asymptotically optimal learned index. Notably, we use
weaker probabilistic assumptions than prior work, meaning our results
generalize previous efforts. Furthermore, we introduce a new measure of
statistical complexity for data. This metric exhibits an information-
theoretical interpretation and can be estimated in practice. This
characterization provides further theoretical understanding of learned
indexes, by helping to explain why some datasets seem to be particularly
challenging for these methods.

###### keywords:

Learned Indexes, Expected Time, Stochastic Processes, Rényi Entropy.

###### category:

##  1 Introduction

Query answering is of central importance in database systems, and developing
efficient algorithms for this task is a key research problem. These algorithms
often use an index structure to access records faster, at the cost of higher
space usage to store the index. Arguably, the most common scenario in query
answering involves point queries, where the aim is to retrieve all tuples
where an attribute has an exact value [12, 20]. Also common are range queries,
which ask for all tuples where an attribute is within a given interval.

Solutions based on hash tables can answer point queries efficiently [5], but
are ineffective in handling range queries. To generalize well to these cases,
the relevant attribute is usually stored as a sorted array $A$. In this
configuration, answering point and range queries essentially comes down to
finding an element in a sorted array. A point query for value $q$ can be
answered by finding the position of $q$ in the array if it exists. A range
query matching an interval $[q,q^{\prime}]$ can be answered by finding the
first element bigger than or equal to $q$, and then scanning the array $A$
from that position until an element greater than $q^{\prime}$ is found, or the
array ends.

Since the array $A$ is sorted, binary search can be used to find $q$ or the
first element greater than $q$. If $A$ has $n$ elements (also called keys),
binary search takes $O(\log n)$ operations. This is asymptotically optimal in
a random-access machine (RAM) model of computation, for comparison-based
searching [16]. However, other index structures such as B+Trees [13, 18] are
preferred in practice. They have the same asymptotic complexity but make use
of hardware and cache properties to improve performance.

It was suggested by [17] that classical index structures can be understood as
models that take a key as an input and predict its position in the sorted
array. From this perspective, indexes such as B+Tree are potentially
suboptimal because they do not take advantage of patterns in the data to
improve performance. This has led to the introduction of learned indexes [17,
15, 9], which use machine learning models to predict the position of a key.

Learned indexes usually combine predictive and corrective steps, as
illustrated in Figure 1. In the predictive step, a machine learning model is
used to estimate the position of a key. Since this estimation may be wrong, a
corrective step is needed to find the exact position. Usually, this is done by
searching around the position estimated by the model. Intuitively, the
improvement in performance comes from searching over a small range, determined
by the prediction error, rather than searching over the whole array. If the
prediction error is small, a learned index can improve upon classical methods.
Most learned indexes stick to simple machine learning models, such as
piecewise linear functions, which are fast to compute.

Figure 1: Predictive and corrective steps of a learned index.

While learned indexes exhibit impressive experimental performance [7, 11, 14,
15], their theoretical understanding is still at an early stage. Existing
research shows that specific learned indexes can achieve better asymptotic
space or time complexity than traditional structures [30, 8], but these
results rely on disparate and potentially restrictive assumptions.
Furthermore, some datasets are notoriously challenging for learned indexes
[21], and no theoretical analysis has yet offered an adequate explanation for
this.

In this work, we analyze the asymptotic expected complexity of learned
indexes. Specifically, we prove that learned indexes can achieve constant
expected query time using at most linear space, which constitutes the best
upper bound so far for the performance of an asymptotically optimal learned
index. Our proof is constructive, meaning we can provide a specific index that
achieves this asymptotic complexity. Compared to previous work, our complexity
bounds hold under a more general probabilistic model, and in particular, our
results do not require any independence assumptions for the data generating
process.

We also address the question of why certain datasets are challenging for
learned indexes. It has been suggested that, for those cases, the data
distribution is inherently hard to learn [21], and different metrics have been
introduced to capture this difficulty [30, 8]. We introduce a new measure of
data complexity $\rho_{\scriptscriptstyle f}$ with better mathematical
properties. Our metric is related to Rényi entropy in information theory,
helping to provide a theoretical grounding for $\rho_{\scriptscriptstyle f}$.
Also, $\rho_{\scriptscriptstyle f}$ can be statistically estimated, making it
potentially useful in practice to predict a priori how well a learned index
will perform. Our experiments support this idea.

##  2 Preliminaries

###  2.1 Data

Learned indexes use statistical models. Therefore, theoretical analysis of
learned indexes is done under a probabilistic model of some kind [30, 8]. In
general, keys are assumed to come from a data generating process with
specified properties. For instance, in [30] it is assumed that the $n$ keys
are independent and identically distributed, while [8] uses a completely
different model. We strive to generalize the probabilistic setting as much as
possible.

Formally, we model a database attribute $X$ as a stochastic process
$X=\\{X_{i}\\}_{i\in\mathbb{N}}$. We assume all random variables $X_{i}$ have
the same cumulative distribution function $F$. For any time $n\in\mathbb{N}$,
we can observe the data $X_{1},X_{2},\ldots,X_{n}$ generated so far. Sorting
the $\\{X_{i}\\}_{i=1}^{n}$ gives rise to a new set of random variables,
usually called the order statistics [6], which we denote
$X_{(1)},X_{(2)},\ldots,X_{(n)}$. We consider the array $A$ at time $n$ to be
formed by this last group of random variables, such that $A[i]=X_{(i)}$ for
all $i=1,\ldots,n$. Duplicate keys are possible in principle, and do not
constitute a problem. In that case, $X_{(i+1)}=X_{(i)}$ for some $i$ and all
analysis remains the same.

That way, in our setting there is a stochastic process generating the data in
attribute $X$. For each $n\in\mathbb{N}$, there is a sorted array $A$ with $n$
keys originated from this process, and a learned index can be constructed to
search this array. For now, we do not assume anything about $F$. Also, we do
not assume independence of the $\\{X_{i}\\}_{i=1}^{n}$ variables. In Sections
3 and 4, we analyze our results under certain probabilistic assumptions. In
Section 5, we compare our model with that of previous work.

###  2.2 Learning Problem

Assume array $A$ has $n$ keys. The learning problem can be formalized by the
introduction of a $\mathbf{rank}$ function. For any number $q\in\mathbb{R}$,
$\mathbf{rank}_{A}(q)$ is defined as the number of elements in $A$ that are
smaller than or equal to $q$, that is

$\mathbf{rank}_{A}(q)=\sum_{i=1}^{n}\mathbf{1}_{X_{(i)}\leq q},$

where $\mathbf{1}$ is the indicator function. We omit the subscript $A$ if it
is clear from context. For a point query with value $q$, $\mathbf{rank}(q)$
gives the position of $q$ in the array if it exists. For a range query
matching an interval $[q,q^{\prime}]$, the relevant records are found by
scanning the array $A$, starting at position $\mathbf{rank}(q)$ and ending
when an element greater than $q^{\prime}$ is found. Since $\mathbf{rank}$ is
sufficient to answer these queries, we focus on the problem of learning the
$\mathbf{rank}$ function, under certain probabilistic assumptions.

###  2.3 Model of Computation

The model of computation we use is the Random Access Machine (RAM) under the
uniform cost criterion [1]. In this model, each instruction requires one unit
of time and each register (storing an arbitrary integer) uses one unit of
space. This is in contrast to part of the existing literature. [30] uses a
computation model where $O(\log n)$ space units are needed to store an integer
$n$. On the other hand, [8] considers an I/O model of computation [19], which
assumes the existence of an external memory (e.g., disk) from which data is
read and written to. Under this model, time complexity consists only of the
number of I/O operations.

We argue the RAM model under the uniform cost criterion is better suited for
analysing learned indexes than either of these two. On the one hand, numbers
are usually represented as data types with a fixed number of bits (e.g., long
int in C++). On the other hand, most learned indexes work in main memory and
avoid the use of disk storage. To make results comparable, in Section 5 we
restate all previous complexity results using our RAM model.

Regarding space complexity, we take the standard approach of only counting the
redundant space introduced by the index, and not the space necessary to store
the array $A$ in the first place [9]. Regarding time complexity, we do not
consider the time needed to train the model, just for finding the keys. We
focus the asymptotic analysis on expected time, where the expectation is taken
over the realizations of the stochastic process and the choice of query.

For any $n\in\mathbb{N}$, let $R_{n}$ be a procedure that takes the sorted
array $A=[X_{(1)},\ldots,X_{(n)}]$ as input, and outputs an index structure
$R_{n}(A)$. Denote by $S(R_{n}(A))$ the space overhead of $R_{n}(A)$. Also,
for any $q\in\mathbb{R}$ denote by $T(R_{n}(A),q)$ the query time for $q$ over
array $A$ when using the index $R_{n}(A)$. We are interested in bounds for $S$
and $T$ that do not depend on $A$ or $q$. With that in mind, we denote

$\overline{S}_{n}=\sup_{A=[X_{(1)},\ldots,X_{(n)}]}S(R_{n}(A)),\quad\overline{T}_{n}=\mathbb{E}\left[T(R_{n}(A),q)\right].$

In the next section, we prove asymptotic results for $\overline{S}_{n}$ and
$\overline{T}_{n}$.

##  3 Main Results and ESPC Index

###  3.1 Complexity Bounds

We mentioned above that all the $X_{i}$ share the same cumulative
distribution. Formally, we consider that the $X_{i}$ are defined in a
probability space $(\Omega,\mathcal{F},\mathbb{P})$, such that
$F_{X_{i}}(x)\coloneqq\mathbb{P}\left(X_{i}\leq x\right)$ is the same for all
$i$, and is denoted by $F$. Now, assume $F$ can be characterized by a square-
integrable density function $f$ and define $\rho_{\scriptscriptstyle f}$ as:

$\rho_{\scriptscriptstyle f}=\lVert
f\rVert_{2}^{2}=\int_{\mathbb{R}}f^{2}(x)dx.$

The main complexity results are stated in Theorems 3.1 and 3.2. Both are
attained by the ESPC index, which we introduce in Section 3.2. Both theorems
assume that the query parameter follows the same probability distribution as
the keys. In Section 4.3.1 we prove that the result can be generalized to
include the case when that assumption does not hold.

######  Theorem 3.1.

There is a procedure $R_{n}$ for building learned indexes such that
$\overline{S}_{n}=O(n)$ and $\overline{T}_{n}=O(\rho_{\scriptscriptstyle f})$.
In other words, for any array $A$ with $n$ keys a learned index can be built
with space overhead $O(n)$ and expected query time $O(\rho_{\scriptscriptstyle
f})$. Since $\rho_{\scriptscriptstyle f}$ is independent of $n$, expected time
is asymptotically $O(1)$.

######  Theorem 3.2.

There is a procedure $R_{n}$ for building learned indexes such that
$\overline{S}_{n}=O\big{(}\frac{n}{\log n}\big{)}$ and
$\overline{T}_{n}=O(\log(\rho_{\scriptscriptstyle f}\log n))$. In other words,
for any array $A$ with $n$ keys a learned index can be built with space
overhead $O\big{(}\frac{n}{\log n}\big{)}$ and expected query time
$O(\log(\rho_{\scriptscriptstyle f}\log n))$. Since $\rho_{\scriptscriptstyle
f}$ is independent of $n$, expected time is asymptotically $O(\log(\log n))$.

Theorems 3.1 and 3.2 are corollaries of a more general result for the ESPC
index proved in Section 4. The specific versions in Theorems 3.1 and 3.2 are
used to facilitate comparison with previous results. This comparison is
presented in detail in Section 5, but one point is worth mentioning here.
Theorems 3.1 and 3.2 do not require any independence assumptions. This is in
direct contrast with previous work, where either the keys [30] or the gaps
$X_{i+1}-X_{i}$ between keys [8] are assumed to be independent.

###  3.2 Equal-Split Piecewise Constant Index

All the complexity results from Section 3.1 are achieved by the Equal-Split
Piecewise Constant (ESPC) index, which we describe here. As explained in
Section 1, learned indexes usually combine predictive and corrective steps.
The ESPC index follows this general pattern, and is remarkably simple to
define and implement.

The general idea is to learn a function $\mathbf{\hat{r}}$ to approximate the
$\mathbf{rank}$ function up to some error. Then $\mathbf{rank}$ can be
computed exactly by first evaluating $\mathbf{\hat{r}}$ and then correcting
the error by use of an exponential search algorithm [2]. If the prediction
error is small, this gives a procedure for computing $\mathbf{rank}$ exactly
in low expected time. The approximator function $\mathbf{\hat{r}}$ is built as
a piecewise constant function defined over equal-length subintervals. This
equal-length property ensures that $\mathbf{\hat{r}}$ can be evaluated in
constant time.

Without loss of generality, we assume that the density $f$ has bounded support
$[a,b]$ for some $a,b\in\mathbb{R}$. That is, $f(x)=0$ for any
$x\not\in[a,b]$. This assumption is only made for ease of presentation, and
our results can be extended with the exact same form to the case of $f$ with
unbounded support (see Section 4.2). We now describe how the piecewise
approximator $\mathbf{\hat{r}}$ is defined. Take an array $A$ formed by the
sorted keys $X_{(1)},\ldots,X_{(n)}$. For a positive integer $K$, divide the
range $[a,b]$ into $K$ subintervals of equal length. We denote these $K$
subintervals as $\\{I_{k}\\}_{k=1}^{K}$. Figure 2 illustrates this type of
partition for a dataset with 40 keys and $K=4$. Notice that all intervals have
the same length, but not necessarily the same number of keys. Formally, for
each $k=1,\ldots,K$ the $k$-th subinterval is defined as
$I_{k}=[t_{k-1},t_{k}]$ where

$t_{k}=a+k\delta\>\text{ with }\>\delta=\frac{b-a}{K}.$

Figure 2: Partition of key range into four equal-length intervals, with
constant approximator of $\mathbf{rank}$ for each interval.

We want $\mathbf{\hat{r}}$ to be defined as a piecewise constant function. If
$q\in\mathbb{R}$ does not belong to any $I_{k}$, this means that with
probability $1$ either $q<a\leq X_{(1)}$ or $q>b\geq X_{(n)}$, so that
$\mathbf{rank}(q)=0$ or $\mathbf{rank}(q)=n$, respectively. On the other hand,
for each subinterval $I_{k}$ the ESPC index stores a constant value
$\hat{r}_{k}$, which is used to approximate $\mathbf{rank}$ over $I_{k}$.
Combining these ideas, we define the piecewise constant approximator
$\mathbf{\hat{r}}$ as

$\mathbf{\hat{r}}(q)=\begin{cases}0&\text{if }q<a\\\ \hat{r}_{1}&\text{if
}q\in I_{1}\vspace{-5pt}\\\ &\vbox{\hbox{.}\hbox{.}\hbox{.}\kern-3.24pt}\\\
\hat{r}_{K}&\text{if }q\in I_{K}\\\ n&\text{if }q>b.\end{cases}$

Figure 2 represents this type of piecewise approximator over equal-length
subintervals. It remains to define the $\\{\hat{r}_{k}\\}$ values. By
definition, it can be seen that $\mathbf{rank}$ is an increasing function.
That means that for all $q\in I_{k}$, it holds that
$\mathbf{rank}(t_{k-1})\leq\mathbf{rank}(q)\leq\mathbf{rank}(t_{k})$. This
motivates a natural candidate for $\hat{r}_{k}$ in the form of

$\hat{r}_{k}=\frac{1}{2}\left(\mathbf{rank}(t_{k-1})+\mathbf{rank}(t_{k})\right)=\mathbf{rank}(t_{k-1})+\frac{n_{k}}{2},$

where $n_{k}=\mathbf{rank}(t_{k})-\mathbf{rank}(t_{k-1})$ is the number of
keys in $I_{k}$. As we prove in Section 4.1, this means that $\hat{r}_{k}$ can
approximate $\mathbf{rank}(q)$ for any $q\in I_{k}$ with error at most
$n_{k}/2$, so that the quality of $\mathbf{\hat{r}}$ as an approximator
depends on the expected number of keys per interval. Algorithm 1 details the
index construction, based on our definitions for $\\{I_{k}\\}$ and
$\\{\hat{r}_{k}\\}$.

Input: Sorted array $A$, positive integer $K$

Output: ESPC index for $A$ with $K$ equal-length subintervals

1 $n\leftarrow\text{length}(A)$

2 $\delta\leftarrow(b-a)/K$

3 $N\leftarrow\text{array of length }K$ with all zeros

4 // Compute number of keys in each subinterval, store in $N$

5 for  _$i=1$ to $n$_ do

6 $k\leftarrow\left\lceil\frac{1}{\delta}(A[i]-a)\right\rceil$

7 $N[k]\leftarrow N[k]+1$

end for

8$r\leftarrow\text{array of length }K$

9 $r[1]\leftarrow\frac{1}{2}N[1]$

10 // Compute rank estimator $\hat{r}_{k}$ for each subinterval, store in $r$

11 for  _$k=2$ to $K$_ do

12 $r[k]\leftarrow r[k-1]+\frac{1}{2}N[k]$

end for

13return _$R=(r,\delta)$_

Algorithm 1 Construction of ESPC index

The $\mathbf{rank}$ approximator $\mathbf{\hat{r}}$ can be evaluated in
constant time for any $q\in\mathbb{R}$. If $q<a$ then $\mathbf{\hat{r}}(q)=0$,
and if $q>b$ then $\mathbf{\hat{r}}(q)=n$. If neither condition is true, then
$q$ belongs to some interval $I_{k}$. In that case,
$\mathbf{\hat{r}}(q)=\hat{r}_{k}$ where $k$ is given by $k=\left\lceil
K\frac{q-a}{b-a}\right\rceil=\left\lceil\frac{1}{\delta}(q-a)\right\rceil.$ To
find $\mathbf{rank}(q)$ exactly, the ESPC index then performs an exponential
search on array $A$ around position
$\left\lceil\mathbf{\hat{r}}(q)\right\rceil$. We prove in Section 4 that the
expected approximation error $|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|$ is low
enough to establish the results of Section 3.1. Algorithm 2 formalizes this
evaluation process. It assumes the existence of a procedure
ExponentialSearch$(A,i,q)$ which uses exponential search around index $i$ to
find the position of $q$ in array $A$. If $q$ is not in $A$, it returns the
position of the greatest key lower than $q$.

Input: Sorted array $A$, $q\in\mathbb{R}$, ESPC index $R=(r,\delta)$

Output: Exact value of $\mathbf{rank}(q)$

1 if  _$q <a$_ then return _$0$_ ;

2 else if  _$q >b$_ then return _$n$_ ;

3 else

4 $k\leftarrow\left\lceil\frac{1}{\delta}(q-a)\right\rceil$

5 $i\leftarrow\left\lceil r[k]\right\rceil$

6 return _ExponentialSearch $(A,i,q)$_

end if

Algorithm 2 Evaluation of ESPC index

##  4 Complexity Proofs and Analysis

###  4.1 Preliminary Results

We now turn to an analysis of the space and time complexity of the ESPC index.
In the following, assume the sorted array $A$ has $n$ elements and the index
is built with $K$ subintervals $\\{I_{k}\\}_{k=1}^{K}$. As seen from Algorithm
1, an ESPC index can be represented as a tuple $R=(r,\delta)$ where $r$ is an
array of length $K$ storing the approximators $\\{\hat{r}_{k}\\}_{k=1}^{K}$.
For $q\in\mathbb{R}$ recall that $\mathbf{\hat{r}}(q)$ denotes the
approximation for $\mathbf{rank}(q)$ before the exponential search (see
Algorithm 2).

For the RAM model under the uniform cost criterion, each stored value uses $1$
unit of space. Hence, the total space used to store an ESPC index
$R=(r,\delta)$ is $K+1=O(K)$. On the other hand, as seen from Algorithm 2, the
evaluation for any $q\in\mathbb{R}$ takes constant time, plus the time needed
for the exponential search. An exponential search takes time
$O(2\log\varepsilon)=O(\log\varepsilon)$ [2], where $\varepsilon$ is the
difference between the starting position and the correct position. This is
summarized in the following result.

######  Proposition 4.1.

Let $A$ be a sorted array with $n$ entries, and $R$ be an ESPC index for $A$
with $K$ subintervals. Then, $R$ uses $O(K)$ space and given $q\in\mathbb{R}$,
the ESPC index $R$ can be used to find $\mathbf{rank}(q)$ in
$O(\log\varepsilon)$ time, where
$\varepsilon=|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|$.

In light of Proposition 4.1, a way to estimate the time complexity of the ESPC
index is to bound the expected value of $\varepsilon$ as a function of $K$.
Hence, our focus is on finding an expression for the approximation error
$\varepsilon=|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|$. We start with the
following result, which was mentioned in Section 3.2.

######  Lemma 4.2.

Let $k\in\\{1,\ldots,K\\}$ and $q\in I_{k}$. Then, it holds that
$|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|\leq n_{k}/2$ where $n_{k}$ is the
number of keys that fall on interval $I_{k}$.

######  Proof 4.3.

Since $q$ belongs to subinterval $I_{k}=[t_{k-1},t_{k}]$, we know that
$\mathbf{\hat{r}}(q)=\hat{r}_{k}$. Also, since $\mathbf{rank}$ is an
increasing function, it holds that
$\mathbf{rank}(t_{k-1})\leq\mathbf{rank}(q)\leq\mathbf{rank}(t_{k})$.
Subtracting $\hat{r}_{k}$ from this inequality, we get

$\mathbf{rank}(t_{k-1})-\hat{r}_{k}\leq\mathbf{rank}(q)-\hat{r}_{k}\leq\mathbf{rank}(t_{k})-\hat{r}_{k}.$
(1)

It can be seen directly from the definition of $\mathbf{rank}$ that
$\mathbf{rank}(t_{k})$ is equal to $\mathbf{rank}(t_{k-1})+n_{k}$. On the
other hand, as described in Section 3.2, $\hat{r}_{k}$ can be written as
$\hat{r}_{k}=\mathbf{rank}(t_{k-1})+n_{k}/2$. This means that
$\mathbf{rank}(t_{k-1})-\hat{r}_{k}=-n_{k}/2$, and similarly

$\mathbf{rank}(t_{k})-\hat{r}_{k}=\mathbf{rank}(t_{k-1})+n_{k}-\hat{r}_{k}=\frac{n_{k}}{2}.$

Substituting into equation (1), we get the desired result:

$-\frac{n_{k}}{2}\leq\mathbf{rank}(q)-\hat{r}_{k}\leq\frac{n_{k}}{2}.$

###  4.2 Main Probabilistic Bound

Recapping, by Proposition 4.1 the ESPC index time complexity for input $q$
depends on the approximation error
$\varepsilon=|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|$. By Lemma 4.2, the error
$\varepsilon$ critically depends on the number of keys in the subintervals
$\\{I_{k}\\}$. We now state and prove the key results which provide bounds for
the approximation error.

We start by introducing the remaining necessary notation. When a set of
subintervals $\\{I_{k}\\}_{k=1}^{K}$ is established, a discrete random
variable is implicitly defined. This random variable models how the
$\\{X_{i}\\}_{i=1}^{n}$ are distributed among the subintervals. For this
distribution, the main parameter can be denoted as $(p_{1},\ldots,p_{K})$ such
that $p_{k}=$. Notice that $p_{k}$ is not indexed by $i$ because all $X_{i}$
follow the same distribution. In this context, the core of the time complexity
analysis is contained in the following theorem.

######  Theorem 4.4.

Let $A$ be an array consisting of the $\\{X_{i}\\}_{i=1}^{n}$ sorted in
ascending order. Let $\mathbf{\hat{r}}$ be the approximator of the ESPC index
with $K$ subintervals, as described in Section 3.2, and denote the
approximation error for $q\in\mathbb{R}$ as
$\varepsilon(q)=|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|$. Then, if the query
parameter $q$ has the same density function $f$ as the $\\{X_{i}\\}$, it holds
that
$\mathbb{E}\left[\varepsilon\right]\leq\frac{n}{2}\sum_{k=1}^{K}p_{k}^{2}$.

######  Proof 4.5.

We know that
$\mathbb{E}\left[\varepsilon\right]=\mathbb{E}\left[\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]\right]$,
by the tower property for conditional expectation. The random nature of the
error depends on both the choice of $q$ and the values of
$\\{X_{i}\\}_{i=1}^{n}$. To see this, recall that the variables
$X_{1},\ldots,X_{n}$ determine the value of both $\mathbf{rank}$ and
$\mathbf{\hat{r}}$. The inner expected value gives

$\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]=\int_{\mathbb{R}}\varepsilon(q)f(q)dq=\int_{a}^{b}\varepsilon(q)f(q)dq,$

where the last equality comes from the fact that $\varepsilon(q)=0$ if
$q\notin[a,b]$. Replacing
$\varepsilon(q)=|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|$ and noticing that the
$\\{I_{k}\\}$ form a partition of $[a,b]$:

$\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]=\sum_{k=1}^{K}\int_{I_{k}}|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|f(q)dq$

By Lemma 4.2 we can bound the error within each $I_{k}$:

$\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]\leq\frac{1}{2}\sum_{k=1}^{K}n_{k}\int_{I_{k}}f(q)dq=\frac{1}{2}\sum_{k=1}^{K}n_{k}p_{k}.$

This means that
$\mathbb{E}\left[\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]\right]\leq\frac{1}{2}\sum_{k=1}^{K}p_{k}\mathbb{E}\left[n_{k}\right]$.
On the other hand, we have

$\mathbb{E}\left[n_{k}\right]=\mathbb{E}\left[\sum_{i=1}^{n}\mathbf{1}_{X_{i}\in
I_{k}}\right]=\sum_{i=1}^{n}\mathbb{E}\left[\mathbf{1}_{X_{i}\in
I_{k}}\right]=\sum_{i=1}^{n}$ Problem 2

Replacing in the expression for $\mathbb{E}\left[\varepsilon\right]$, we get
the desired result:

$\mathbb{E}\left[\varepsilon\right]=\mathbb{E}\left[\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]\right]\leq\frac{1}{2}\sum_{k=1}^{K}p_{k}\mathbb{E}\left[n_{k}\right]=\frac{n}{2}\sum_{k=1}^{K}p_{k}^{2}.$

Theorem 4.4 is the key tool for proving our results. We now clarify some
points about it.

##### Unbounded support

Theorem 4.4 can be extended to $f$ with unbounded support. In that case, we
know there exist values of $a,b$ such that . Moreover, such values of $a,b$
can often be derived by using concentration inequalities. For instance, for
finite expectation $\mu$ and variance $\sigma^{2}$, we can set $a=\mu-\sigma
n^{1/4}$ and $b=\mu+\sigma n^{1/4}$ to guarantee via Chebyshev’s inequality.

Now, for any positive integer $K$, the ESPC index can be built in the same way
as before, with the addition of two new subintervals $I_{0}=(-\infty,a]$ and
$I_{K+1}=[b,\infty)$. The approximator $\mathbf{\hat{r}}$ is built as
described in Section 3.2, that is, by defining
$\hat{r}_{k}=\frac{1}{2}\left(\mathbf{rank}(t_{k-1})+\mathbf{rank}(t_{k})\right)$.
The approximators $\hat{r}_{0}$, $\hat{r}_{K+1}$ for intervals $I_{0}$,
$I_{K+1}$ are defined in the same way using $\mathbf{rank}(-\infty)\coloneqq
0$ and $\mathbf{rank}(\infty)\coloneqq n$. The space overhead of the index is
$O(K)$ as before, and $\mathbf{\hat{r}}$ can still be evaluated in constant
time. Moreover, Lemma 4.2 holds with the same form. This means that the proof
of Theorem 4.4 can be repeated exactly to yield

$\mathbb{E}\left[\varepsilon\right]\leq\frac{n}{2}\sum_{k=0}^{K+1}p_{k}^{2}=\underbrace{\frac{n}{2}(p_{0}^{2}+p_{K+1}^{2})}_{\leq\frac{1}{2}\>\>(\star)}+\frac{n}{2}\sum_{k=1}^{K}p_{k}^{2}\leq\frac{1}{2}+\frac{n}{2}\sum_{k=1}^{K}p_{k}^{2}$

where $(\star)$ is due to the fact that $1-p_{0}-p_{K+1}=$. So for the case of
unbounded support, the index uses a fixed interval $[a,b]$ which concentrates
most of the probability, and we get essentially the same bound for the
expected error. The extra $\frac{1}{2}$ term is negligible and does not change
the asymptotic analysis.

##### Fixed data

It is natural to consider what happens when the keys $\\{X_{i}\\}_{i=1}^{n}$
are given and only $q$ is modeled as a random variable. This essentially
corresponds to an analysis of the conditional expected error
$\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]$. As seen in the
proof of Theorem 4.4, this expression can be upper bounded by
$\frac{1}{2}\sum_{k=1}^{K}n_{k}p_{k}$. If the data is given and the
$\\{p_{k}\\}$ can be estimated, then this bound can be computed exactly,
essentially corresponding to a weighted average of the $\\{n_{k}\\}$.

###  4.3 Proof of Asymptotic Complexity

We now use Theorem 4.4 to prove the results stated in Section 3.1. For this,
we need to relate the error bound in Theorem 4.4 with
$\rho_{\scriptscriptstyle f}=\lVert f\rVert_{2}^{2}$. For this, notice that

$p_{k}=\int_{I_{k}}f(x)dx\leq\sup_{x\in
I_{k}}f(x)(t_{k}-t_{k-1})=\frac{1}{K}\sup_{x\in I_{k}}f(x).$

Substituting this in the error bound from Theorem 4.4 we obtain

$\displaystyle\mathbb{E}\left[\varepsilon\right]$
$\displaystyle\leq\frac{n}{2}\sum_{k=1}^{K}p_{k}^{2}\leq\frac{n}{2K}\sum_{k=1}^{K}\left(\sup_{x\in
I_{k}}f(x)\right)^{2}\frac{1}{K}$ (2) Since $f$ is square-integrable:
$\displaystyle\mathbb{E}\left[\varepsilon\right]$
$\displaystyle\leq\frac{n}{2K}\left(\int_{\mathbb{R}}f^{2}(x)dx+\delta(K)\right),$
(3)

where $\delta(K)=o(1)$. Here, $\delta(K)$ represents the difference between
the Riemann Sum in (2) and the integral in (3). It is $o(1)$ because the
Riemann sum converges as $K\rightarrow\infty$, but the rate of convergence
cannot be estimated without additional assumptions. For instance, if $f$ is
Lipschitz continuous then the difference between the Riemann sum and its
integral is $O(1/K)$. In any case, the specific rate of convergence does not
change the main result.

######  Proposition 4.6.

Under the conditions of Theorem 4.4, it holds

$\mathbb{E}\left[\varepsilon\right]\leq\frac{n}{2K}\left(\rho_{\scriptscriptstyle
f}+\delta(K)\right)\>\text{ where }\>\delta(K)=o(1).$

The main complexity results introduced in Section 3.1 are essentially
corollaries of Proposition 4.6. The proofs for both theorems are included in
Appendix A. In Section 5, we present further analysis of our findings and
provide a comparison to previous results.

####  4.3.1 Distribution of query parameter

As can be seen from the statement of Theorem 4.4, we have assumed that $q$ has
the same probability density function $f$ as the $\\{X_{i}\\}$. We believe
this to be a reasonable approximation in many contexts, but our analysis can
be extended to $q$ otherwise distributed, which constitutes an important
generalization with respect to previous work [30].

######  Proposition 4.7.

Assume the conditions of Theorem 4.4. Additionally, suppose the search
parameter $q$ distributes according to a density function $g$. Further suppose
that $g$ is square-integrable and denote $\rho_{g}=\lVert g\rVert_{2}^{2}$.
Then, it holds that

$\mathbb{E}\left[\varepsilon\right]\leq\frac{n}{2K}\left(\sqrt{\rho_{\scriptscriptstyle
f}\rho_{g}}+\delta(K)\right)\>\text{ where }\>\delta(K)=o(1).$

The proof of this result is in Appendix B. As can be seen, for the general
case where $q$ does not distribute according to $f$, we get a result with
essentially the same form. For ease of presentation, all our analyses from
this point on assume the case where $g=f$. By Proposition 4.7 we know this
does not result in any loss of generality. All results hold with the same form
for the case of $q$ otherwise distributed, by substituting
$\sqrt{\rho_{\scriptscriptstyle f}\rho_{g}}$ in place of
$\rho_{\scriptscriptstyle f}$.

##  5 Analysis and Benchmarking

We now take a careful look at the expected time complexity and
$\rho_{\scriptscriptstyle f}$. Let $A$ be a sorted array with $n$ keys and let
an ESPC index be built with $K$ subintervals. Then, by Theorem 4.4 and
Jensen’s inequality:

$\mathbb{E}\left[\log\varepsilon\right]\leq\log\mathbb{E}\left[\varepsilon\right]\leq\log\left(\frac{n}{2}\sum_{k=1}^{K}p_{k}^{2}\right)=\log\left(\frac{n}{2}\right)+\log\left(\sum_{k=1}^{K}p_{k}^{2}\right)$
(4)

where $p_{k}=$. Recall that $(p_{1},\ldots,p_{K})$ constitutes an induced
discrete probability distribution, describing the probabilities of the
$\\{X_{i}\\}$ falling on the different subintervals.

###  5.1 Analysis of alternative index design

As detailed below in Section 5.2.2,
$\log\big{(}\sum_{k=1}^{K}p_{k}^{2}\big{)}$ is related to a notion of entropy
and is minimized when $(p_{1},\ldots,p_{K})$ is a uniform distribution. Hence,
we could conceivably get better performance with an alternative design where
the $\\{I_{k}\\}$ subintervals are defined so as to enforce $p_{k}=1/K$ for
all $k$. This would refine the intervals where data is more concentrated,
which seems to be a reasonable strategy. However, there is a trade-off.

Choosing the $\\{I_{k}\\}$ so that $p_{k}=1/K$ for all $k$ means that the
subintervals will not be equal-length, unless the $\\{X_{i}\\}$ distribute
uniformly. Consequently, for a given query parameter $q$, we can no longer
find its subinterval in constant time, as we did before with
$k\leftarrow\left\lceil\frac{1}{\delta}\big{(}q-a\big{)}\right\rceil$. This
version of the index would need a new strategy to find the relevant
subinterval $I_{k}$ such that $q\in I_{k}$.

A standard strategy would be to create a new array $A^{\prime}$ formed by the
left endpoints of the $\\{I_{k}\\}$, that is,
$A^{\prime}=[t_{0},\ldots,t_{k-1}]$. Now, for a given search parameter $q$ we
can find the relevant subinterval $I_{k}$ by using
$k=\mathbf{rank}_{A^{\prime}}(q)$. After computing $k$, we can use
$\hat{r}_{k}$ to predict the position of $q$ and use exponential search to
correct the error. Notice that the index is now hierarchical, with
$A^{\prime}$ at the top and $A$ (segmented into the $I_{k}$) at the bottom. We
can analyze the time complexity involved. Following equation (4), the expected
time at the bottom layer is dominated by

$\mathbb{E}\left[\log\varepsilon_{\text{bot}}\right]\leq\log\left(\frac{n}{2}\sum_{k=1}^{K}p_{k}^{2}\right)=\log\left(\frac{n}{2}\sum_{k=1}^{K}\frac{1}{K^{2}}\right)=\log\left(\frac{n}{2K}\right).$

On the other hand, the top layer has $K$ keys $\\{t_{0},\ldots,t_{k-1}\\}$.
Since the subintervals $\\{I_{k}\\}$ are chosen such that $p_{k}=1/K$, this
means that $F(t_{i})=i/k$. As a consequence, the keys in $A^{\prime}$
approximately follow the distribution characterized by $F$, with a better
approximation as $K\to\infty$. Suppose we use an ESPC index with $K^{\prime}$
subintervals to speed up computation of $\mathbf{rank}_{A^{\prime}}$. By
Proposition 4.6 the expected time at the top layer will be dominated by
$\mathbb{E}\left[\log\varepsilon_{\text{top}}\right]\lesssim\log\left((K\rho_{\scriptscriptstyle
f})/(2K^{\prime})\right)$ and the total expected time can be bounded as

$\mathbb{E}\left[\log\varepsilon_{\text{bot}}\right]+\mathbb{E}\left[\log\varepsilon_{\text{top}}\right]\lesssim\log\left(\frac{n}{2K}\right)+\log\left(\frac{K\rho_{\scriptscriptstyle
f}}{2K^{\prime}}\right)=\log\left(\frac{n\rho_{\scriptscriptstyle
f}}{4K^{\prime}}\right).$

Notice that $\rho_{\scriptscriptstyle f}$ is still present in this expression.
Now, for instance, taking $K=K^{\prime}=n$ we get twice the space usage
compared to Theorem 3.1 and a constant additive improvement in expected time.
This type of trade-off may be of interest for practical index design, and
tree-like structures are common in learned indexes [17, 9]. However, the
asymptotic complexity remains the same, so the basic ESPC index gives a
simpler proof for our results.

###  5.2 Bounds for Expected Query Time

####  5.2.1 Complexity due to number of keys

Equation (4) provides an interesting insight. We see that the expected log-
error (and hence, the expected query time) can be decomposed into two separate
sources of complexity. The first is due exclusively to the number of keys $n$,
which suggests that the query problem gets increasingly difficult when new
keys are inserted, even if the underlying distribution of the data remains the
same. This helps to explain why learned indexes evidence a need for updating
[29, 24] in the face of new keys arriving, even when the same dataset is used
to simulate the initial keys and the subsequent arrivals.

####  5.2.2 Information-theoretical considerations

The sum $\sum_{k=1}^{K}p_{k}^{2}$ is related to the concept of Rényi entropy
[22]. For a discrete random variable $P$ with possible outcomes ${1,\ldots,K}$
with correspondent probabilities $\\{p_{k}\\}_{k=1}^{K}$, the Rényi entropy of
order $\alpha$ is defined as

$H_{\alpha}(P)=\frac{1}{1-\alpha}\log\textstyle{\left(\sum_{k=1}^{K}p_{k}^{\alpha}\right)}.$

for any $\alpha>0,\alpha\neq 1$. The cases $\alpha=0,1,\infty$ are defined as
limits. In particular, $\lim_{\alpha\to 1}H_{\alpha}(P)$ gives the Shannon
entropy of $P$ [22]. The Rényi entropy can be understood as a generalization
of the Shannon entropy which preserves most of its properties, including its
additive nature. In our case, $P$ is the random variable describing the
probabilities for a key $X_{i}$ of falling on the different subintervals
$\\{I_{k}\\}$. As a consequence, starting from equation (4) we can write

$\mathbb{E}\left[\log\varepsilon\right]\leq\log\left(\frac{n}{2}\right)-H_{2}(P).$
(5)

$H_{2}(P)$ is close to the Shannon entropy but it is more influenced by events
of larger probability. Due to its relationship with the collision probability
$\sum_{k=1}^{K}p_{k}^{2}$, it has found use in cryptography [4, 25, 3]. Same
as the Shannon entropy, $H_{2}$ is maximized by the uniform distribution [25],
that is, when $p_{k}=1/K$ for all $k$.

As explained in Section 5.1, maximizing the entropy at the bottom layer
implies that the $\\{I_{k}\\}$ are not equal-length, which make it necessary
to train further machine learning models and gives rise to hierarchical
structures [9, 30]. This explains why negative entropy might be a good measure
of statistical complexity for learned indexes, beyond the specific ESPC index.
It essentially captures a notion of statistical distance to the uniform
distribution $U$, which is easy to learn for the type of simple models
commonly used in learned indexes. This notion of distance can be formalized by
writing $-H_{2}(P)=D_{2}(P||U)-\log K$, where $D_{2}(P||U)$ is the Rényi
divergence of order 2, defined analogously to the KL divergence [27].

####  5.2.3 Characterization via the stochastic process

There is a similar insight using the density function $f$. By Proposition 4.6,
we know

$\mathbb{E}\left[\log\varepsilon\right]\lesssim\log\left(\frac{n}{2K}\right)+\log\rho_{\scriptscriptstyle
f}=\log n-\log(2K)-h_{2}(X_{i}),$

where we use $h_{\alpha}(X)=\frac{1}{1-\alpha}\log(\lVert
f\rVert_{\alpha}^{\alpha})$ to define the Rényi entropy for continuous random
variables [28], similar to how differential entropy is defined in analogy to
the Shannon entropy. This last expression provides a useful bound for the
expected log-error, by separating the effect of the number $n$ of keys, the
number $K$ of subintervals (which represent space usage), and an inherent
characteristic $h_{2}(X_{i})$ of the stochastic process. As can be seen, for
$K=1$ subintervals the expected query time is $O(\log n)$, consistent with
binary search and other non-learned methods.

###  5.3 Comparison with Existing Methods

In this section, we compare our probabilistic model and complexity bounds to
previous work. All results are stated in terms of our RAM model. Table 1
summarizes the main points.

Method | Space | Expected time | Parameters | Probabilistic Model
---|---|---|---|---
B+Tree | $O\left(\frac{n}{b}\right)$ | $O(\log n)$ |  Branching factor $b$ | None
PGM-index | $O\left(\frac{n}{\varepsilon^{2}}\right)$ | $O(\log n)$ |  Maximum error $\varepsilon$ |  Gaps $\\{X_{i+1}-X_{i}\\}$ i.i.d. with finite mean $\mu$ and variance $\sigma^{2}$, $\varepsilon\gg\sigma/\mu$
PCA Index | $O\left(\rho_{1}^{1+\delta}n^{1+\frac{\delta}{2}}\right)$ | $O\left(\log\frac{1}{\delta}\right)$ | $\delta>0$ |  $\\{X_{i}\\}$ i.i.d. with density $f$, $f(x)\leq\rho_{1}<\infty$ for all $x$
RDA Index | $O\left(\frac{\rho_{1}}{\rho_{2}}n\right)$ | $O(\log(\log n))$ | None |  Same as PCA Index, plus $0<\rho_{2}\leq f(x)$ for all $x$
ESPC index |  $O(n)$ $O\left(\frac{n}{\log n}\right)$ |  $O\big{(}\rho_{\scriptscriptstyle f}\big{)}$ $O(\log(\rho_{\scriptscriptstyle f}\log n))$ |  $K$ intervals |  Variables $\\{X_{i}\\}$ have same density $f$, $\rho_{\scriptscriptstyle f}=\lVert f\rVert_{2}^{2}<\infty$
Table 1: Space and expected time complexity for learned indexes. The non-
learned B+Tree index is also included for comparison. The probabilistic
assumptions are not necessary for the index to work, but they are necessary to
guarantee the stated performance.

####  5.3.1 Non-learned methods

There are many classical algorithms for searching an array. They tend to be
comparison-based and none achieve expected time lower than $O(\log n)$, unless
very strong assumptions are made (e.g., interpolation search uses $O(\log(\log
n))$ time on average if the keys are uniformly distributed [16]). We use
B+Tree as a representative for our analysis.

A B+Tree has space overhead $O(n/b)$ where $b$ is the branching factor. Since
$b$ does not depend on $n$, asymptotically this is just $O(n)$. The number of
comparisons required to find a key is $O(\log n)$. This represents both worst-
case and average-case complexity. No probabilistic assumptions are needed to
guarantee this performance.

####  5.3.2 PGM-index

In the absence of probabilistic assumptions, space overhead of the PGM-index
is $O(n/\varepsilon)$ and expected time is $O(\log n)$. Here, $\varepsilon$ is
a hyperparameter of the method and is independent of $n$, so this constitutes
the same asymptotic complexity as B+Trees. Under certain assumptions, space
overhead can be strengthened to $O(n/\varepsilon^{2})$ [8], representing a
constant factor improvement (i.e., same asymptotic space complexity).

In contrast to [30] and our work, the assumptions in [8] concern the gaps
between keys. Specifically, the $\\{X_{i+1}-X_{i}\\}$ are assumed to be
independent and identically distributed (i.i.d.), with finite mean $\mu$ and
variance $\sigma^{2}$. It is also assumed that $\varepsilon\gg\sigma/\mu$.
This setting is not directly comparable to ours, in the sense that neither is
a particular instantiation of the other. However, the assumptions described
above are very strong in our view and seem hard to justify for most practical
applications. Also, the $\varepsilon\gg\sigma/\mu$ condition constrains the
choice of this key hyperparameter.

####  5.3.3 PCA Index and RDA Index

In [30] several indexes are presented. The two most relevant for comparison
are the PCA and RDA indexes. The PCA Index is essentially identical to the
ESPC index defined in Section 3.2. The RDA Index is similar to the Recursive
Model Index (RMI) from [17]. All results below are stated in terms of the RAM
model under the uniform cost criterion.

For any $\delta>0$, there is a PCA Index with space overhead
$O(\rho_{1}^{1+\delta}n^{1+\delta/2})$ and expected time complexity
$O(\log\frac{1}{\delta})$. Here, $\rho_{1}$ is an upper bound for $f$. Since
it is independent of $n$, space overhead is asymptotically
$O(n^{1+\delta/2})$. A direct comparison to the ESPC index is possible through
Theorem 3.1, which provides a strictly stronger result, with expected constant
time and truly linear space overhead.

On the other hand, the RDA Index has space overhead
$O({\scriptstyle\frac{\rho_{1}}{\rho_{2}}}n)$, where $\rho_{2}$ is a lower
bound for $f$ and $\rho_{1}$ is an upper bound (as before). Asymptotically in
$n$, this is $O(n)$. Expected query time in this case is $O(\log(\log n))$. A
direct comparison to the ESPC index is possible through Theorem 3.2, which
provides a strictly stronger result, with $O(\log(\log n))$ expected time and
sublinear space overhead.

Even as we improve the complexity bounds, we also generalize the domain of
application for our result. As part of the probabilistic model for the PCA and
RDA indexes, it is assumed that the $\\{X_{i}\\}$ are i.i.d. with density $f$.
PCA index assumes $f$ is upper bounded, that is, there exists some fixed
$\rho_{1}<\infty$ such that $f(x)\leq\rho_{1}$ for all $x$. Notice that this
condition implies that $f$ is square-integrable:

$\rho_{\scriptscriptstyle
f}=\int_{\mathbb{R}}f^{2}(x)dx\leq\rho_{1}\int_{\mathbb{R}}f(x)dx=\rho_{1}<\infty.$

The RDA index further assumes that $f$ is bounded away from $0$, that is,
there exists some $\rho_{2}>0$ such that $f(x)\geq\rho_{2}$. This is not true
of many standard distributions, such as normal or exponential. The case of $f$
with unbounded support is only considered for sub-exponential distributions.
In conclusion, our results hold more generally, since we do not need the
$\\{X_{i}\\}$ to be independent, and the condition on $f$ is only that it be
square-integrable.

##  6 Experimental Findings

We implement the ESPC index and evaluate the results in light of the
theoretical analysis.

###  6.1 Data

In our experiments, we use four datasets from the Searching on Sorted Data
(SOSD) benchmark [21], which has become standard in testing learned indexes
[26]. Each dataset consists of a sorted array of keys, which can be used to
build an index and simulate queries. Two of the datasets we use (usparse,
normal) are synthetically generated. The other two (amzn, osm) come from real-
world data. In particular, osm is known to be challenging for learned indexes
[21].

###  6.2 Experimental Design

Our complexity bounds (Theorems 3.1 and 3.2) are corollaries of Propositions
4.1 and 4.6, which are the key results to validate empirically. We do this in
the following way. Each dataset consists of a sorted array of $20\times
10^{7}$ keys. We use a subsample of $n=10^{7}$ keys, so that experiments run
faster and we can test more configurations. For a fixed subsample, we take
different values of $K$ and for each:

  1. 1.

We build the ESPC index with $K$ subintervals. We estimate the space overhead
by reporting the amount of memory used by the index. From Proposition 4.1,
this should be $O(K)$. In terms of experiments, we expect to see a linear
relationship when we report memory overhead versus $K$.

  2. 2.

We sample $Q$ keys from $A$. We compute $\mathbf{rank}$ for these keys using
the index and measure the prediction error. We then average these values to
estimate the expected error. From Proposition 4.6, this should be smaller than
$\frac{n}{2K}\big{(}\hat{\rho}_{f}+\delta(K)\big{)}$ where $\delta(K)=o(1)$.
For experiments, we plot the average prediction error alongside
$(n\hat{\rho}_{f})/(2K)$, as functions of $K$. We expect the average error
curve to be below $(n\hat{\rho}_{f})/(2K)$. Here, $\hat{\rho}_{f}$ is an
estimate for $\rho_{\scriptscriptstyle f}$ (see Section 6.4).

We use $Q=30\times 10^{6}$. For $K$ we use values of $10^{3},5\times
10^{3},10^{4},5\times 10^{4},10^{5}$ and $2\times 10^{5}$.

###  6.3 Results

In terms of storage, our experiments show a perfect linear relationship
between memory overhead and $K$, where $\texttt{memory overhead}=32K\texttt{
bytes}$. This result is in accordance to the $O(K)$ estimate in Proposition
4.1. The agreement between experiments and theory is to be expected here,
because the space overhead of the ESPC index does not depend on probabilistic
factors.

On the other hand, Figure 3 shows how the prediction error changes with the
number of subintervals $K$. We plot the average experimental error along with
the theoretical bound for the expected error. In accordance with Proposition
4.6, this theoretical bound is given by $(n\hat{\rho}_{f})/(2K)$. As expected,
for all datasets this expression serves as an upper bound for the average
experimental error, and both curves have a similar shape. The results show
that Proposition 4.6 has good predictive power, even for real-world data.

Figure 3: Average experimental error and theoretical bound for expected error,
as functions of the number $K$ of subintervals. Top row shows synthetic
datasets, bottom row shows real-world datasets. The plots use a logarithmic
scale for both axes, which prevents clustering of the points.

###  6.4 Analysis of $\rho_{\scriptscriptstyle f}$

As seen in Figure 3, the average experimental error follows the overall shape
described by the theoretical bound in Proposition 4.6. According to the
theory, the constants involved (e.g., the intercept of the curves) should
depend on $\rho_{\scriptscriptstyle f}$. Hence, it is crucial to have
estimates available for this metric. In Appendix C we describe a procedure
that can provide an estimate $\hat{\rho}_{f}$ of $\rho_{\scriptscriptstyle
f}$. The values computed with this method are (usparse, 1.20), (normal, 3.89),
(amzn, 1.72), (osm, 32.57). The value of $\hat{\rho}_{f}$ for the osm dataset
is an order of magnitude greater than the rest, meaning it is farther away
from the uniform distribution as measured by the Rényi divergence, and helping
to explain why it is challenging. The dataset with the lowest value is
usparse. Since its underlying distribution is uniform, this is consistent with
the analysis in Section 5.2.2. Figure 3 shows that higher values of
$\hat{\rho}_{f}$ result in a higher experimental error.

##  7 Conclusions

Theoretical understanding of learned indexes has not kept up with their
practical development. We narrow this gap by proving that learned indexes
exhibit strong theoretical guarantees under a very general probabilistic
model. In particular, we prove learned indexes can achieve $O(1)$ expected
query time with at most linear space. We introduce a specific index that
achieves this performance, and we find a general bound for the expected time
in terms of the number of keys and the Rényi entropy of the distribution. From
this result, we derive a metric $\rho_{\scriptscriptstyle f}$ that can be used
to characterize the difficulty of learning the data. We describe a procedure
for estimating $\rho_{\scriptscriptstyle f}$ for real data, and we show that
the complexity bounds hold in practice. Our results help explain the good
experimental performance of learned indexes, under the most general conditions
considered so far in the literature. As future work, it is theoretically
important to prove lower bounds for expected query time. We believe this type
of result may hinge on information-theoretical properties, which our analysis
shows are relevant for learned indexes. Also, it is important to extend our
analysis to the case of dynamic datasets, where the probability distribution
may exhibit drift over time. This is an important case in applications, and
has not been considered in theoretical analysis.

## References

  * [1] Alfred V. Aho and John E. Hopcroft.  The Design and Analysis of Computer Algorithms.  Addison-Wesley Longman Publishing Co., Inc., USA, 1st edition, 1974.
  * [2] Jon Louis Bentley and Andrew Chi-Chih Yao.  An almost optimal algorithm for unbounded searching.  Information Processing Letters, 5(3):82–87, 1976.  URL: https://www.sciencedirect.com/science/article/pii/0020019076900715, doi:10.1016/0020-0190(76)90071-5.
  * [3] Serdar Boztas.  Entropies, guessing, and cryptography.  Department of Mathematics, Royal Melbourne Institute of Technology, Tech. Rep, 6:2–3, 1999.
  * [4] Christian Cachin.  Entropy measures and unconditional security in cryptography.  PhD thesis, ETH Zurich, 1997.
  * [5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  Introduction to Algorithms, Third Edition.  The MIT Press, 3rd edition, 2009.
  * [6] H.A. David and H.N. Nagaraja.  Order Statistics.  Wiley Series in Probability and Statistics. John Wiley & Sons, 2004.  URL: https://books.google.co.uk/books?id=bdhzFXg6xFkC.
  * [7] Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, David Lomet, and Tim Kraska.  Alex: An updatable adaptive learned index.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD ’20, page 969–984, New York, NY, USA, 2020. Association for Computing Machinery.  doi:10.1145/3318464.3389711.
  * [8] Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra.  Why are learned indexes so effective?  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 3123–3132. PMLR, 13–18 Jul 2020.  URL: https://proceedings.mlr.press/v119/ferragina20a.html.
  * [9] Paolo Ferragina and Giorgio Vinciguerra.  The pgm-index: A fully-dynamic compressed learned index with provable worst-case bounds.  Proc. VLDB Endow., 13(8):1162–1175, apr 2020.  doi:10.14778/3389133.3389135.
  * [10] David Freedman and Persi Diaconis.  On the histogram as a density estimator: L 2 theory.  Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 57(4):453–476, 1981.
  * [11] Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska.  Fiting-tree: A data-aware index structure.  In Proceedings of the 2019 International Conference on Management of Data, SIGMOD ’19, page 1189–1206, New York, NY, USA, 2019. Association for Computing Machinery.  doi:10.1145/3299869.3319860.
  * [12] Rodrigo González, Szymon Grabowski, Veli Mäkinen, and Gonzalo Navarro.  Practical implementation of rank and select queries.  In Poster Proc. Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA), pages 27–38. CTI Press and Ellinika Grammata Greece, 2005.
  * [13] Goetz Graefe et al.  Modern B-tree techniques.  Foundations and Trends in Databases, 3(4):203–402, 2011.
  * [14] Ali Hadian and Thomas Heinis.  Shift-table: A low-latency learned index for range queries using model correction.  In Yannis Velegrakis, Demetris Zeinalipour-Yazti, Panos K. Chrysanthis, and Francesco Guerra, editors, Proceedings of the 24th International Conference on Extending Database Technology, EDBT 2021, Nicosia, Cyprus, March 23 - 26, 2021, pages 253–264. OpenProceedings.org, 2021.  URL: https://doi.org/10.5441/002/edbt.2021.23, doi:10.5441/002/EDBT.2021.23.
  * [15] Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann.  Radixspline: A single-pass learned index.  In Proceedings of the Third International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM ’20, New York, NY, USA, 2020. Association for Computing Machinery.  doi:10.1145/3401071.3401659.
  * [16] Donald E. Knuth.  The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching.  Addison Wesley Longman Publishing Co., Inc., USA, 1998.
  * [17] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis.  The case for learned index structures.  In Proceedings of the 2018 International Conference on Management of Data, SIGMOD ’18, page 489–504, New York, NY, USA, 2018. Association for Computing Machinery.  doi:10.1145/3183713.3196909.
  * [18] Justin J. Levandoski, David B. Lomet, and Sudipta Sengupta.  The bw-tree: A b-tree for new hardware platforms.  In Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013), ICDE ’13, page 302–313, USA, 2013. IEEE Computer Society.  doi:10.1109/ICDE.2013.6544834.
  * [19] Ling Liu and M Tamer Özsu.  Encyclopedia of database systems, volume 6.  Springer New York, NY, USA:, 2009.
  * [20] Scott Lloyd and Maya Gokhale.  Near memory key/value lookup acceleration.  In Proceedings of the International Symposium on Memory Systems, MEMSYS ’17, page 26–33, New York, NY, USA, 2017. Association for Computing Machinery.  doi:10.1145/3132402.3132434.
  * [21] Ryan Marcus, Andreas Kipf, Alexander van Renen, Mihail Stoian, Sanchit Misra, Alfons Kemper, Thomas Neumann, and Tim Kraska.  Benchmarking learned indexes.  Proc. VLDB Endow., 14(1):1–13, sep 2020.  doi:10.14778/3421424.3421425.
  * [22] Alfréd Rényi.  On measures of entropy and information.  In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, volume 4, pages 547–562. University of California Press, 1961.
  * [23] D.W. Scott.  Multivariate Density Estimation: Theory, Practice, and Visualization.  Wiley Series in Probability and Statistics. Wiley, 2015.  URL: https://books.google.cl/books?id=pIAZBwAAQBAJ.
  * [24] Amirhesam Shahvarani and Hans-Arno Jacobsen.  Parallel index-based stream join on a multicore cpu.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD ’20, page 2523–2537, New York, NY, USA, 2020. Association for Computing Machinery.  doi:10.1145/3318464.3380576.
  * [25] Maciej Skórski.  Shannon entropy versus renyi entropy from a cryptographic viewpoint.  In Jens Groth, editor, Cryptography and Coding, pages 257–274, Cham, 2015. Springer International Publishing.
  * [26] Zhaoyan Sun, Xuanhe Zhou, and Guoliang Li.  Learned index: A comprehensive experimental evaluation.  Proc. VLDB Endow., 16(8):1992–2004, apr 2023.  doi:10.14778/3594512.3594528.
  * [27] Tim van Erven and Peter Harremos.  Rényi divergence and kullback-leibler divergence.  IEEE Transactions on Information Theory, 60(7):3797–3820, 2014.  doi:10.1109/TIT.2014.2320500.
  * [28] Susana Vinga and Jonas S Almeida.  Rényi continuous entropy of dna sequences.  Journal of theoretical biology, 231(3):377–388, 2004.
  * [29] Guang Yang, Liang Liang, Ali Hadian, and Thomas Heinis.  FLIRT: A fast learned index for rolling time frames.  In Julia Stoyanovich, Jens Teubner, Nikos Mamoulis, Evaggelia Pitoura, Jan Mühlig, Katja Hose, Sourav S. Bhowmick, and Matteo Lissandrini, editors, Proceedings 26th International Conference on Extending Database Technology, EDBT 2023, Ioannina, Greece, March 28-31, 2023, pages 234–246. OpenProceedings.org, 2023.  URL: https://doi.org/10.48786/edbt.2023.19, doi:10.48786/EDBT.2023.19.
  * [30] Sepanta Zeighami and Cyrus Shahabi.  On distribution dependent sub-logarithmic query time of learned indexing.  In Proceedings of the 40th International Conference on Machine Learning, ICML’23. JMLR.org, 2023.

##  Appendix A Proofs of Main Complexity Bounds

######  Proof A.1 (Proof of Theorem 3.1).

Let $n\in\mathbb{N}$ and consider the following procedure $R_{n}$ for
generating an index: given a sorted array $A=[X_{(1)},\ldots,X_{(n)}]$, the
output $R_{n}(A)$ consists of an ESPC index built with $K=n$ subintervals.
This means that space overhead is $S(R_{n}(A))=O(K)=O(n)$. As this is
independent of the specific values stored in $A$, we have
$\overline{S}_{n}=O(n)$.

On the other hand, by Theorem 4.4 and Proposition 4.6

$\mathbb{E}\left[\varepsilon\right]\leq\frac{n}{2n}\left(\rho_{\scriptscriptstyle
f}+\delta(n)\right)=\frac{\rho_{\scriptscriptstyle
f}}{2}+\frac{\delta(n)}{2},$

where $\delta(n)=o(1)$. This means that
$\mathbb{E}\left[\varepsilon\right]=O(1)$. Furthermore, Jensen’s inequality
implies

$\mathbb{E}\left[\log\varepsilon\right]\leq\log\mathbb{E}\left[\varepsilon\right]=O(1).$

By Proposition 4.1, we know query time for $q$ for the ESPC index is
$O(\log\varepsilon(q))$. Accordingly, the expected query time is
$\overline{T}_{n}=O(\mathbb{E}\left[\log\varepsilon\right])=O(1)$. This
concludes the proof.

######  Proof A.2 (Proof of Theorem 3.2).

We use the same argument as the proof for Theorem 3.1, but using
$K=\frac{n}{\log n}$ subintervals instead of $K=n$.

##  Appendix B Proof of Proposition 4.7

######  Proof B.1 (Proof of Proposition 4.7).

The proof follows closely the argument used to prove Theorem 4.4 and
Proposition 4.6. By the tower property for conditional expectation,

$\displaystyle\mathbb{E}\left[\varepsilon\right]=\mathbb{E}\left[\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]\right].$

The inner expected value gives

$\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]=\int_{\mathbb{R}}\varepsilon(q)g(q)dq=\int_{a}^{b}\varepsilon(q)g(q)dq.$

where the last equality comes from the fact that for $q\notin[a,b]$ we know
the exact value of $\mathbf{rank}(q)$, which is either $0$ or $n$, and hence
we have that $\varepsilon(q)=0$. Replacing
$\varepsilon(q)=|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|$ and noticing that the
$\\{I_{k}\\}$ form a partition of $[a,b]$:

$\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]=\sum_{k=1}^{K}\int_{I_{k}}|\mathbf{rank}(q)-\mathbf{\hat{r}}(q)|g(q)dq$

By Lemma 4.2 we can bound the error within each $I_{k}$:

$\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]\leq\frac{1}{2}\sum_{k=1}^{K}n_{k}\int_{I_{k}}g(q)dq=\frac{1}{2}\sum_{k=1}^{K}n_{k}q_{k}.$

Here, $q_{k}$ is defined as for each $k=1\ldots K$, analogously to how the
$p_{k}$ are defined as . This last expression means that
$\mathbb{E}\left[\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]\right]\leq\frac{1}{2}\sum_{k=1}^{K}q_{k}\mathbb{E}\left[n_{k}\right]$.
By writing $n_{k}$ as a sum of indicator functions we get

$\mathbb{E}\left[n_{k}\right]=\mathbb{E}\left[\sum_{i=1}^{n}\mathbf{1}_{X_{i}\in
I_{k}}\right]=\sum_{i=1}^{n}\mathbb{E}\left[\mathbf{1}_{X_{i}\in
I_{k}}\right]=\sum_{i=1}^{n}$ Problem 9

Replacing in the expression for $\mathbb{E}\left[\varepsilon\right]$, we
obtain:

$\displaystyle\mathbb{E}\left[\varepsilon\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\varepsilon\>|\>X_{1},\ldots,X_{n}\right]\right]$
$\displaystyle\leq\frac{1}{2}\sum_{k=1}^{K}q_{k}\mathbb{E}\left[n_{k}\right]$
$\displaystyle=\frac{n}{2}\sum_{k=1}^{K}q_{k}p_{k}$
$\displaystyle\leq\frac{n}{2}\left(\sum_{k=1}^{K}q_{k}^{2}\right)^{1/2}\left(\sum_{k=1}^{K}p_{k}^{2}\right)^{1/2},$

where the last part is due to Cauchy–Schwarz inequality. Now, since both $f$
and $g$ are square-integrable functions, the same argument from Proposition
4.6 can be used to prove that

$\displaystyle\sum_{k=1}^{K}q_{k}^{2}$
$\displaystyle\leq\frac{1}{K}\left(\int_{\mathbb{R}}g^{2}(x)dx+\delta_{1}(K)\right),\>\text{and}$
$\displaystyle\sum_{k=1}^{K}p_{k}^{2}$
$\displaystyle\leq\frac{1}{K}\left(\int_{\mathbb{R}}f^{2}(x)dx+\delta_{2}(K)\right),$

where $\delta_{1}(K)$ and $\delta_{2}(K)$ are $o(1)$. Putting everything
together:

$\displaystyle\mathbb{E}\left[\varepsilon\right]$
$\displaystyle\leq\frac{n}{2K}\left(\int_{\mathbb{R}}g^{2}(x)dx+\delta_{1}(K)\right)^{1/2}\left(\int_{\mathbb{R}}f^{2}(x)dx+\delta_{2}(K)\right)^{1/2}$
$\displaystyle=\frac{n}{2K}\left(\rho_{g}+\delta_{1}(K)\right)^{1/2}\left(\rho_{\scriptscriptstyle
f}+\delta_{2}(K)\right)^{1/2}$
$\displaystyle=\frac{n}{2K}\left(\sqrt{\rho_{\scriptscriptstyle
f}\rho_{g}}+\delta(K)\right),$

where $\delta(K)=o(1)$. This concludes the proof.

##  Appendix C Estimation of $\rho_{\scriptscriptstyle f}$ metric

As the key measure of statistical complexity for the data generating process,
$\rho_{\scriptscriptstyle f}$ can help explain the experimental differences in
the performance of the ESPC index for different datasets. In that sense, it is
important to have an estimate for this metric. Notice that

$\rho_{\scriptscriptstyle
f}=\int_{\mathbb{R}}f^{2}(x)dx=\int_{\mathbb{R}}f(x)f(x)dx=\mathbb{E}\left[f\right],$

that is, $\rho_{\scriptscriptstyle f}$ is equal to the expected value of the
density function. In other words, if we can

  1. 1.

Sample $J$ values $z_{1},\ldots,z_{J}$ from the probability distribution
defined by $f$, and

  2. 2.

Evaluate $f(z_{j})$ for all $j\in\\{1,\ldots,J\\}$,

then we can get an unbiased estimator for $\rho_{\scriptscriptstyle f}$ via

$\hat{\rho}_{f}=\frac{1}{J}\sum_{j=1}^{J}f(z_{j}).$

If the $\\{z_{j}\\}$ are sampled independently, this corresponds to a Monte
Carlo estimator and we know its variance goes to $0$ as $J\rightarrow\infty$.

We can adapt this procedure for real datasets. On the one hand, Step (1) can
be simulated by sampling keys at random from array $A$. On the other hand,
since $f$ is usually not known, for Step (2) we use an estimate $\hat{f}$ of
the density $f$. This estimate can be derived via several methods (e.g.,
kernel density estimation [23]) with different properties in terms of mean
squared or uniform error.

We mostly use the histogram method, which under mild assumptions can be shown
to have vanishing bias as the bin width goes to $0$ [10]. For this method, the
mean squared error is minimized with $\Omega(n^{-1/3})$ bin width, where $n$
is the number of keys. One robust option in practice is to choose the bin
width using the Freedman–Diaconis rule [10]. For most datasets, generated from
either synthetic (usparse, normal) or real-world data (amzn), this method
exhibits the convergence expected from Monte Carlo estimation as the number of
samples increases. Figure 4 exemplifies this with the normal and amzn
datasets.

Figure 4: $\hat{\rho}_{f}$ estimate for normal, amzn and osm datasets as
number of samples $n$ increases. The estimation process uses the histogram
method to approximate the density $f$.

For the osm dataset, this convergent behavior is not observed, as Figure 4
shows. It may be that the variance of the estimator is higher and more samples
are needed to get an accurate estimate with this method. In light of this, we
calculate $\hat{\rho}_{f}$ by using a kernel density estimator for the density
$f$, which seems to be more robust than the histogram estimator.

Table 2 shows the estimates $\hat{\rho}_{f}$ obtained through the use of our
method. As can be seen, most datasets exhibit low values for this metric,
consistent with the good performance that learned indexes have in general.
Among these datasets, osm has the highest value of $\hat{\rho}_{f}$,
consistent with the fact that it is considered a challenging benchmark for
learned indexes.

Dataset | $\hat{\rho}_{f}$
---|---
usparse | $1.20$
normal | $3.89$
amzn | $1.72$
osm | $32.57$
Table 2: Estimate $\hat{\rho}_{f}$ for each dataset used in our experiments.
Most have low values, consistent with good performance of learned indexes. The
osm dataset exhibits a high value of $\hat{\rho}_{f}$, an order of magnitude
greater than the rest, helping to explain why it is considered challenging.