A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees

An indexing data structure maintains a set $S$ of $n$ distinct integers from a universe $𝒰$. Let $\text{RANK}:S\to [n]$ be the function mapping each $s\in S$ to its index in the sorted order of $S$. The objective is to support the following indexing queries:

• $\mathrm{■}$

  member($q$) returns true if $q\in S$.

• $\mathrm{■}$

  predecessor($q$) returns . (We allow $q\notin S$.)

• $\mathrm{■}$

  rank($q$) returns $\text{RANK}(\text{predecessor}(q))+1$. (We allow $q\notin S$.)

Additionally, we consider range queries, where $k$ denotes the output size:

• $\mathrm{■}$

  range($q$, $t$) returns $S\cap [q,t]$. (We allow $q,t\notin S$.)

Static indexing data structures fall into three broad categories: Tree-based solutions store $S$ in a sorted array $A$, requiring no additional space but incurring logarithmic query costs. Tree traversals enable predecessor, rank, and member queries in $O(\log n)$ time and range queries in $O(\log n+k)$ time [1, 3, 32, 37]. Map-based solutions store $S$ in sorted order and maintain a hash map $H:S\to [n]$ mapping each element to its rank [4, 23, 31]. This enables constant-time support for member, predecessor, and rank queries if queries are restricted to elements of $S$, and $O(k)$ time for range queries when both endpoints lie in $S$. The additional space is $O(n)$. A third category use what are called learned indices, a recently introduced term [24, 20, 16, 22, 8]. Given an integer parameter $\epsilon$, a learned index is a function $h_{\epsilon }:𝒰\to [0,n]$ such that

The function $h_{\epsilon }$ is learned from $S$ and used to guide search in a sorted array $A$ storing $S$. Ferragina and Vinciguerra [16] interpret $h_{\epsilon }$ geometrically: each $s\in S$ maps to a point $(\text{RANK}(s),s)$ in the plane, and $h_{\epsilon }$ is learned as a piecewise-linear approximation to $F_S$.

A notable instance of learned indices is the PGM index [16], where $h_{\epsilon }$ is a $y$-monotone piecewise-linear function made of segments, with the property that each point in $F_S$ lies within an $\epsilon$-wide horizontal strip around some segment. Let $|h_{\epsilon }|$ denote the number of segments. The data structure supports indexing queries in $O(\epsilon +\log |h_{\epsilon }|)$ time and range queries in $O(\epsilon +k+\log |h_{\epsilon }|)$ time. They also show how to construct a PGM index in linear time, such that there exists no PGM index $h_{\epsilon }^{\prime }$ with $|h_{\epsilon }|>2|h_{\epsilon }^{\prime }|$. Ferragina and Vinciguerra argue that learned indices are the “best of both worlds” since:

• $\mathrm{■}$

  the supported queries are as general as those supported by tree-based solutions,

• $\mathrm{■}$

  the solution uses only $O(|h_{\epsilon }|)$ additional space, and

• $\mathrm{■}$

  $O(\epsilon +\log |h_{\epsilon }|)$ is, for an appropriate choice of $\epsilon$, efficient in practice.

Their performance has been empirically benchmarked in several studies [15, 24, 38, 37].

Due to their fundamental role, dynamic indexing structures have received extensive theoretical and practical attention. When $S$ is dynamic, maintaining a sorted array becomes inefficient. Tree-based structures can be updated in $O(\log n)$ time with tree rotations. Map-based approaches allow constant-time member updates but are typically not extended to support other indexing queries. Learned indices offer a promising direction by exploiting structural properties of $S$, akin to parametrised algorithms. However, just as parametrised algorithms, data structures based on learned indices are not always efficient: if $S$ lacks exploitable structure or access patterns are skewed, traditional indexing data structures are preferred [33, 26]. Experimental studies have examined properties of learned indices [14, 13, 26, 33], in an effort to classify when they are appropriate to use. As a brief summary, learned indices pay a price in updates [26], and traditional indices are preferred if $S$ or the access pattern is complex or skewed, or if concurrency is possible [33]. If there is sufficient structure, both space usage and access times can benefit from learned indices [13, 14], subject to the strategy employed by the learned index.

The logarithmic method of Overmars [29] provides an amortised way to maintain learned indices. $S$ is partitioned into $\lceil \log n\rceil$ buckets $B_i$, each of size $2^i$. Each bucket is either full or empty, and stores its contents in an array $A_i$ in sorted order and maintains a learned index $h_{\epsilon }^i$ over $A_i$.

Let the learned index $h_{\epsilon }$ have a construction time of $T(n)$. This data structure can be maintained insertion-only in amortised $O(T(n)\log n)$ time. An insertion inserts a new value into $B_0$. Let $j$ be the maximum integer such that all $B_i$ for $i\in [0,j-1]$ are full. This approach empties these buckets, fills $B_j$ in sorted order, and constructs $(A_j,h_{\epsilon }^j)$ in $O(T(2^j))$ time. Whenever we delete some $s\in S$, this approach instead inserts a tombstone $s^{\ast }$, which is a special copy of $s$. If an insertion fills a new bucket $B_j$, it first iterates over all elements. If $B_j$ contains both $s$ and $s^{\ast }$, it removes both elements. It then constructs $(A_j,h_{\epsilon }^j)$ twice. Once on all “normal” values, and once on all tombstones in $B_j$. This way, deletions take the same time as insertions do. In this paper, we consider the following open question:

“Can a learned index be dynamically be maintained with worst-case guarantees?”

The interpretation of learned indices by Ferragina and Vinciguerra [16] translates to a geometric problem where the goal is to (approximately) cover a monotone set of two-dimensional points by a set of line segments. Using the logarithmic method, and the static algorithm of O’Rourke [27] to approximately points, they dynamically maintain an $\epsilon$-cover: a set of lines that are guaranteed to be within an $\epsilon$ horizontal distance from each point. We consider the problem of maintaining dynamic $\epsilon$-covers to be an interesting geometric problem in its own right.

Under the logarithmic method, indexing queries decompose naturally across the buckets:

• $\mathrm{■}$

  For $\text{member}(q)$, $q\in S$ if and only if there exists an $i\in [\lceil \log n\rceil ]$ with $q\in B_i$.

• $\mathrm{■}$

  For $\text{predecessor}(q)$, the output is the maximum predecessor across $B_i$ for $i\in [\lceil \log n\rceil ]$.

• $\mathrm{■}$

  For $\text{rank}(q)$, the rank is the sum of all ranks of $q$ in $B_i$ for $i\in [\lceil \log n\rceil ]$.

• $\mathrm{■}$

  For $\text{range}(q,t)$, the reported range is the union of all ranges in $B_i$ for $i\in [\lceil \log n\rceil ]$.

This way, indexing queries require only an additional factor $O(\log n)$ time. Indexing queries can be answered by combining queries to both the normal and tombstone structures. E.g., $\text{rank}(q)$ is the rank of $q$ in the “normal” data structure minus the rank of $q$ in the tombstone structure. This approach has two downsides:

• $\mathrm{■}$

  First, approach has an amortised update time.

• $\mathrm{■}$

  Second, this approach does not support output-sensitive range queries – as there may be $O(n)$ values $s$ that (together with their tombstones $s^{\ast }$) lie in between a query pair $(q,t)$.

This leads to the following open question:

“Can a dynamic learned index be converted into an output-sensitive dynamic indexing data structure with worst-case guarantees?”

We propose maintaining a dynamic $\epsilon$-cover (and thereby a dynamic learned index) via dynamic convex hull techniques. Section 3 shows that deciding whether $S$ admits an $\epsilon$-cover of complexity 1 is equivalent to convex hull intersection testing (Figure 2). Section 4 shows a robust algorithm to compute the intersection between two convex hulls in $O(\log n)$ time. We adapt our algorithm to output a separating line (which is a learned index of complexity $1$) in the negative case. Section 5 combines these with dynamic convex hull data structures to yield a dynamic learned index worst-case $O({\log }^{2}n)$ update time. We empirically compare our learned index to the PGM index from [16].

Section 6 introduces a novel hashing-based approach to convert learned indices into dynamic indexing data structures, using $O({\epsilon }^{-1})$ additional expected overhead. We compare our dynamic indexing structure to the amortised PGM index of [16] in terms of update time and index complexity. We do not benchmark against traditional indexing data structures – since the relation between learned and traditional indices is previously studied [33]. Instead, our goal is to push the theoretical limits and worst-case guarantees of learned indices.

We dynamically maintain an $\epsilon$-cover $f$ of $S$ of approximately minimum complexity. To this end, we use a result by Overmars and van Leeuwen [30] to dynamically maintain for all $[a,b]\in \mathrm{\Lambda }(f)$ the convex hull of $F_{S[a,b]}$. For any point set $F$, denote by $CH(F)$ their convex hull. The data structure in [30] is a balanced binary tree over $F$, which at its root maintains a balanced binary tree over the edges $CH(F)$ in their cyclical ordering. It uses $O(n)$ space and has worst-case $O({\log }^{2}n)$ update time.

For any update in $S$, up to $n$ values in $F_S$ may change their $x$-coordinate. This complicates the maintenance of a dynamic data structure over $F$. Gæde, Gørtz, van Der Hoog, Krogh, and Rotenberg [17] observe that all algorithmic logic in [30] requires only the relative $x$-coordinates between points. They adapt [30] to give an efficient and robust implementation of what they call a rank-based convex hull data structure $T(S)$ with $O({\log }^{2}n)$ update time. For ease of exposition, we overly simplify their functionality:

For each $[a,b]\in \mathrm{\Lambda }(f)$, we store $S[a,b]$ in $T(S[a,b])$. $T(S[a,b])$ maintains a balanced binary tree $\gamma (S[a,b])$ storing the edges of $\text{CH}(F_{S[a,b]})$ in their cyclical ordering. We use this data structure as a black box, using the following functions that take at most $O({\log }^{2}n)$ time:

• $\mathrm{■}$

  $T(S[a,b])$.get_hull() returns the tree $\gamma (S[a,b])$.

• $\mathrm{■}$

  $T(S[a,b])$.split($v$) returns, for $v\in [a,b]$, $T(S[a,v])$ and $T(S[v,b])$.

• $\mathrm{■}$

  $T(S[a,b])$.split($T([S[b,c])$) returns $T(S[a,c])$.

• $\mathrm{■}$

  $T(S[a,b])$.update($v$) updates, for $v\in [a,b]$, the set $S$ (deleting or inserting $v$).

Any line with positive slope lies above $(\mathrm{\infty },-\mathrm{\infty })$ and below $(-\mathrm{\infty },\mathrm{\infty })$. Consider a point $p\in F_S$ and the two corresponding points $l\in L$ and $u\in U$ and denote by $C$ an axis-aligned square of radius $\epsilon$ centred at $p$. If $\mathrm{\ell }$ lies below $l$ then all points on $\mathrm{\ell }$ left of $l$ lie below $C$. If $\mathrm{\ell }$ lies above $u$ then all points on $\mathrm{\ell }$ right of $u$ lie above $C$. If $\mathrm{\ell }$ lies above $l$ and below $u$ then because $\mathrm{\ell }$ has positive slope, it must intersect $C$. The statement follows. $◀$

Given $\text{CH}(F_S)$, we can extract $\text{CH}(L)$ and $\text{CH}(U)$ in $O(\log n)$ time. Chazelle and Dobkin [6, Section 4.2] remark that, in the negative case, convex hull intersection testing can be modified to produce a separating line. In our setting, the hulls consist of segments with slope at least 1, and any such separator corresponds to an $\epsilon$-cover. Thus, our problem reduces to the classical convex hull intersection problem and we are seemingly done.

However, the history of convex hull intersection testing is long and intricate. Both Chazelle and Dobkin [6] and Dobkin and Kirkpatrick [10] independently proposed the first $O(\log n)$-time algorithms. In 1987, Chazelle and Dobkin [5] presented a more detailed description of their method. Dobkin and Kirkpatrick revisited their own work in 1990 [11], proposing a unified $O({\log }^{2}n)$-time algorithm for polyhedron intersection, which O’Rourke later identified as incorrect [28]. He corrected the argument and provided a $C$-implementation. Further work by Dobkin and Souvaine [9] noted that earlier implementations lacked robustness. More recently, Barba and Langerman [2] observed that the community still lacked a complete, robust algorithm for polyhedral intersection. They proposed an alternative $O(\log n)$ algorithm based on polar transformations. Walther’s master’s thesis [35], supervised by Afshani and Brodal, implemented both this and earlier methods, but the source code is no longer available.

This 35-year history highlights the complexity and subtlety of convex hull intersection testing. Despite its history, no robust and modern $O(\log n)$-time implementation is available. Moreover, no published algorithm explicitly computes a separating line in the negative case.

In the full version, we present a robust $O(\log n)$-time algorithm for convex hull intersection testing. Our algorithm is specialised to convex hulls composed of positively sloped segments and including the points $(\mathrm{\infty },-\mathrm{\infty })$ and $(-\mathrm{\infty },\mathrm{\infty })$. We formally prove its correctness and adapt it to compute a separating line in the negative case, thereby constructing an $\epsilon$-cover of complexity 1 when it exists. The later adaption and its analysis are nontrivial, and arguably (partly) fill a gap in the existing literature on convex hull intersection testing.

Our algorithms use on three predicates for their decision making:

• $\mathrm{■}$

  slope. Given positive segments $(\alpha ,\beta )$, output whether .

• $\mathrm{■}$

  lies_right. Given two positive segments $\alpha$ and $\beta$ with different slopes, output whether the first vertex of $\beta$ lies right of $line(\alpha )\cap line(\beta )$.

• $\mathrm{■}$

  wedge. Consider a pair of positive segments $(\alpha ,\gamma )$ that share a vertex and define $W$ as the cone formed by their supporting halflines containing $(\mathrm{\infty },-\mathrm{\infty })$. Given a positive segment $\beta$ outside of $W$, output whether $line(\beta )$ intersects $W$.

The segments are given by points with integer coordinates. The slopes of these segments (and thereby any representation of their supporting line) are often not integer. A naive way to compute these predicates is to represent slopes using doubles. However, this is both computationally slow and prone to rounding errors (and thus, robustness errors).

If we insist on correct output, one can use an algebraic type instead. This type represents values using algebraic expressions. E.g., the slope of a positive segment $(a,b)$ is the quotient: $\frac{b.y-a.y}{b.x-a.x}$ and so, in our case, it can be represented as a pair of integers. Algebraic types can subsequently be accurately compared to each other. Indeed, if we want to verify whether we may robustly verify whether using only integers. Exact (algebraic type) comparisons are frequently implemented, and present in the CGAL CORE library [12].

However, exact comparisons are expensive. Our implementation of slope requires two integer multiplications, which is still relatively efficient. Evaluating more complex expressions requires too much time. As a rule of thumb, we want to avoid compounding algebraic types to maintain efficiency. Naïvely, lies_right compounds two quotients and wedge compounds three. We give robust implementations of these functions by invoking three subfunctions. These compare slopes, or whether a point lies above or below a supporting halfplane:

We can create lies_right from our robust predicates (see Figure 3 (a)):

Suppose that . Then $c$ lies right of $line(\alpha )\cap line(\beta )$ if and only if $c$ lies above the halfplane bounded from above by $line((a,b))$. That happens if and only if $(a,b,c)$ are collinear or make a counter-clockwise turn. This in turn occurs if and only if the determinant if the matrix is zero or more. If $slope(\alpha )>slope(\beta )$ the determinant must be negative instead. $◀$

Similarly, we can create wedge from our robust predicates. We note for the reader that explain our equations in words in the proof of the lemma:

The predicate is a case distinction of three mutually exclusive cases.

If the first vertex of $\beta$ lies below the supporting line of $\gamma$ then $line(\beta )$ intersects $W$ if and only if it intersects $\overleftarrow{\alpha }$. This happens if and only if one of two conditions hold: either $b$ lies below the supporting line of $b$, or, .

If the second vertex of $\beta$ lies below $line(\alpha )$ then the argument is symmetric.

If neither of those cases apply then both endpoints of $\beta$ must lie in the open green area. In this case, whenever , the supporting line of $\beta$ always intersects $W$. Whenever , the supporting line of $\beta$ always intersects $W$. Whenever $\text{slope}(\alpha )\ge \text{slope}(\beta )\ge \text{slope}(\gamma )$, the supporting line of $\beta$ cannot intersect $W$. $◀$

The proof is illustrated by Figure 4. For any $s,t\in \mathbb{Z}$ with $s\le t$, we say that $S[s,t]$ is blocked if there exists no $\epsilon$-cover of $S[s,t]$ of size $1$. We maintain an $\epsilon$-cover $f$ where for all consecutive intervals $[a,b],[c,d]\in \mathrm{\Lambda }(f)$, $S[a,d]$ is blocked. Thereby, $|f|\le 2|f^{\prime }|$ for any $\epsilon$-cover $f^{\prime }$ of $S$ (we give a proof of this fact in the full version).

We consider inserting a value $s$ into $S$; deletions are handled analogously. We query $B(f)$ in $O(\log n)$ time for an interval $[a,b]$ that contains $s$. If no such interval exists, set $[a,b]=[s,s]$. We search $T(S[a,b])$ and test whether $s\in S$. If so, we reject the update.

Otherwise, we remove $[a,b]$ from $\mathrm{\Lambda }(f)$ and insert the intervals $([a,s],[s,s],[s,b]$). We obtain $T(S[a,s])$, $T(S[s,s])$ and $T(S[s,b])$ through the split operation.

Let $([w,x],[y,z],[a,s],[s,s],[s,b],[c,d],[e,f])$ be consecutive intervals in $\mathrm{\Lambda }(f)$ and denote $I=([y,z],[a,s],[s,s],[s,b],[c,d])$ (see Figure 4 (c) ). For each $(s,t)\in I$, we have access to $T(S[s,t])$. For any consecutive pair $([s,t],[q,r])$ in $I$, we may join the trees $T(S[s,t])$ and $T(S[q,r])$ in $O({\log }^{2}n)$ time to obtain $T([s,r])$. We invoke $T([s,r])$.get_hull() and apply Theorem 8 to test in $O({\log }^{2}n)$ total time whether $S[s,r]$ is blocked. If it is not, we replace $[s,t]$ and $[q,r]$ by $[s,r]$. Otherwise, we keep $T(S[s,r])$ and a complexity-1 $\epsilon$-cover of $S[s,r]$.

By recursively merging pairs in $I$, we obtain in $O({\log }^{2}n)$ time a sequence $I^{\prime }$ of intervals $([y,\beta ],\mathrm{\dots },[\gamma ,d])$ where consecutive intervals are blocked. Since $[y,z]\subseteq [y,\beta ]$, $([w,x],[y,\beta ])$ is blocked. Similarly, $([\gamma ,d],[e,f])$ must be blocked. We remove the line segments corresponding to $I$ from $f$ and replace them with line segments derived from $I^{\prime }$ in constant time. As a result, we maintain our $\epsilon$-cover $f$ and our data structure in $O({\log }^{2}n)$ total time. $◀$

In the full version, we define a data structure independent of the learned index $h_{\epsilon }$ (we illustrate our approach in Figure 5 (a) + (b)). A page $p$ is an integer with a vector that stores all $s\in S$ where $\lfloor \frac{s}{\epsilon }\rfloor =p$, in order. We store all non-empty pages $P$ in an unordered vector $A$. We maintain a hash map $H:P\to [|A|]$, where $A[H(p)]$ contains the page $p$. We additionally maintain a doubly linked list over all pages in $P$, arranged in sorted order.

We restrict our learned index $h_{\epsilon }$ to a vertical $\epsilon$-cover. I.e., $h_{\epsilon }$ is a $y$-monotone collection of line segments such that for all points $p\in F_S$, a vertical line segment of height $2\epsilon$ centred at $p$ intersects a segment in $h_{\epsilon }$. We compute $h_{\epsilon }$ oblivious of our paging structure.

Given $q\in 𝒰$, we project $q$ onto $h_{\epsilon }$ (Figure 5 (d)). We project to the $x$-axis, floor the value, and project back to $h_{\epsilon }$. We prove that the resulting $y$-value corresponds to the page $p$ containing predecessor($q$). This way, we answer predecessor using $O(\epsilon +\log |h_{\epsilon }|)$ time.

As a result, we dynamically maintain a learned index $h_{\epsilon }$ and a data structure that updates in $O(\epsilon +{\log }^{2}n)$ and supports indexing queries in $O(\epsilon +\log |h_{\epsilon }|)$ expected time (Theorem 12).

We compare the quality of the learned indices based the complexity of $h_{\epsilon }$, in a dynamic setting. We use the same choice of $\epsilon =64$ as in [16] across our experiments. For performance of the indexing structures, we measure their time per operation in a dynamic scenarios with a range of query to update ratios. We note that logarithmic PGM is by default equipped with an optimisation that avoids building a PGM for data below a certain size. In this case, it instead only uses an underlying sorted array without additional search structure. In order to properly compare the performances, this optimisation has been disabled.

Finally, we considered the following question:

“Can a dynamic learned index be converted into a dynamic indexing data structure?”

To this end, we designed a hybrid technique combining hashing-based fast-access data structures with a doubly linked list to support indexing queries. Our method offers output-sensitive worst-case guarantees, even in the presence of deletions. As it is known that traditional indexing structures currently outperform learned indices in the general dynamic setting [33], we focused our comparisons on improving the theoretical and practical performance within the class of learned approaches.

In practice, the contiguous memory access of the logarithmic PGM index offsets its overhead from querying multiple structures, making it faster in all scenarios, except for an adversarial one. This means that the lower complexity of our learned index does not immediately translate to improved efficiency in the indexing data structure. This raises an interesting open question of whether memory-access efficient fully dynamic approaches to convert a learned index into a dynamic indexing structure can exist.

While we acknowledge that our update-times are slow in comparison with state-of-the art, our approach does illustrate that it brings worst-case guarantees: as it has an advantage when the query-to-update ratio is large and the index has undergone sufficiently many deletions. In adversarial workloads with frequent deletions followed by range queries, we have seen our structure outperform the logarithmic approach – highlighting the value of worst-case guarantees even in specialised settings.

We showed what we believe is an interesting connection between the geometric learned index by Ferragina and Vinciguerra, and dynamic convex hulls from computational geometry. We subsequently provided an implementation of a dynamic learned index that relies on the state-of-the-art dynamic convex hull maintenance algorithms. Our empirical analysis shows that the complex tree rebalancing that is used to dynamically maintain a convex hull currently brings considerable operational overhead compared to low-memory techniques under the logarithmic method. Our experiments, though not uniformly favourable, offer interesting insights into the current barriers and adversarial tradeoffs between worst-case dynamic algorithms and memory-efficient amortised rebuilding schemes.