Learning-Augmented Search Data Structures

## Abstract

Abstract We study the integration of machine learning advice into the design of skip lists to improve upon traditional data structure design. Given access to a possibly erroneous oracle that outputs estimated fractional frequencies for search queries on a set of items, we construct a skip list that provably provides the optimal expected search time, within nearly a factor of two. In fact, our learning-augmented skip list is still optimal up to a constant factor, even if the oracle is only accurate within a constant factor. We show that if the search queries follow the ubiquitous Zipfian distribution, then the expected search time for an item by our skip list is only a constant, independent of the total number n 𝑛 n italic_n of items, i.e., 𝒪 ⁢ ( 1 ) 𝒪 1 \mathcal{O}(1) caligraphic_O ( 1 ) , whereas a traditional skip list will have an expected search time of 𝒪 ⁢ ( log ⁡ n ) 𝒪 𝑛 \mathcal{O}(\log n) caligraphic_O ( roman_log italic_n ) . We also demonstrate robustness by showing that our data structure achieves an expected search time that is within a constant factor of an oblivious skip list construction even when the predictions are arbitrarily incorrect. Finally, we empirically show that our learning-augmented skip list outperforms traditional skip lists on both synthetic and real-world datasets.

## 1 Introduction

As efficient data management has become increasingly crucial, the integration of machine learning (ML) has significantly improved the design and performance of traditional algorithms for many big data applications.
[] first showed that ML could be incorporated to create data structures that support faster look-up operations while also saving an order-of-magnitude of memory compared to optimized data structures oblivious to such ML heuristics.
Subsequently, *learning-augmented algorithms* [] have been shown to achieve provable worst-case guarantees beyond the limitations of oblivious algorithms for a wide range of settings.
For example, ML predictions have been utilized to achieve more efficient data structures [, ], algorithms with faster runtimes [, , ], mechanisms with better accuracy-privacy tradeoffs [], online algorithms with better performance than information-theoretic limits [, , , , , , , , , , , , , , , , , , , , ], streaming algorithms with better accuracy-space tradeoffs [, , , , , ], and polynomial-time algorithms beyond hardness-of-approximation limits, e.g., NP-hardness [, ].

In this paper, we focus on the consolidation of ML advice to improve data structures for the fundamental problem of searching for ordered elements among a large dataset.
For this purpose, tree-based structures stand out as a popular choice among other structures, particularly for their logarithmic average performance.
However, these structures often need to be balanced for optimal performance, and thus their effectiveness is often closely tied to the order of element insertions.
In contrast, skip lists, introduced by Pugh in 1990 [], maintain balance probabilistically, offering a simpler implementation while delivering substantial speed enhancements [].
Thus while binary search trees have been a long-standing choice for querying ordered elements, skip lists offer a simpler, more efficient, and in some cases necessary alternative.

#### Skip lists.

Skip lists are generally built iteratively in levels.
The bottom levels of the skip list is an ordinary-linked list, in which the items of the dataset are organized in order.
Each higher level serves to accelerate the search for the lower levels, by storing only a subset of the items in the lower levels, also as an ordered link list.
Traditional skip lists are built by promoting each item in a level to a higher level randomly with a fixed probability $p\in(0,1)$.

Querying for a target element begins at the first element in the highest level and continues by searching along the linked list in the highest level until finding an item whose value is at least that of the target element.
If the found item is greater than the target element, the process is repeated after returning to the previous element and dropping to a lower list.
It can be shown that the expected number of steps in the search is $\mathcal{O}\left(\frac{1}{p}\log_{1/p}n\right)$ so that $p$ serves as a trade-off parameter between the search time and the storage costs.

In many modern applications, skip lists are used because of their excellent search runtime and their space efficiency.
Skip lists are often preferred over binary search trees due to their simplicity of implementation, their support for efficient range query, and their amenability to concurrent processes [, ], high efficiency for dynamic datasets [, ], network routing [, ], and real-time analytics [, ].

### 1.1 Skip Lists and Applications

Traditional skip lists treat each element equally when promoting the elements to higher levels.
This balancing behavior facilitates good performance in expectation when a query to the skip list is equally likely to be any dataset element.
On the other hand, this behavior may limit the performance of the data structure when the incoming queries are from an unbalanced probability distribution.

Real-world applications can feature a diverse range of distribution patterns. One particularly common distribution is the Zipfian distribution, which is a probability distribution that is a discrete counterpart of the continuous Pareto distribution, and is characterized by the principle that a small number of events occur very frequently, while a large number of events occur rarely.

In a Zipfian distribution, the frequency of an event $N(k;\alpha,N)$ is inversely proportional to its rank $k$, raised to the power of $\alpha$ (where $\alpha$ is a positive parameter), in a dataset of $N$ elements. The formula is given by:

$$ $N(k;\alpha,N)=\frac{1/k^{\alpha}}{\sum_{n=1}^{N}(1/n^{\alpha})}$ $$

The value of $\alpha$ determines the steepness of the distribution. A smaller $\alpha$ (close to 0) makes it more uniform, while a larger $\alpha$ increases skewness.

Zipfian distributions provide a simple means for understanding phenomena in various fields involving rank and frequency, ranging from linguistics to economics, and from urban studies to information technology.
Indeed, they appear in many applications such as word frequencies in natural language [, ], city populations [, ], biological cellular distributions [], income distribution [], etc.

Unfortunately, although Zipfian distributions are common in practice, their properties are not leveraged by traditional skip lists, which are oblivious to any information about the query distributions.
To improve this performance bottleneck, we propose the augmentation of traditional skip lists with “learned” advice, which (possibly erroneously) informs the data structure in advance about some useful statistics on the incoming queries.
Although we model the data structure as having oracle access to the advice, in practice, such advice can often easily be realized from machine learning heuristics trained for these useful statistics.

### 1.2 Our Contributions

We propose the incorporation of ML advice into the design of skip lists to improve upon traditional data structure design.
In this setting, we assume the items that may appear either in the data set or the query set can be associated with an integer in $[n]:=\{1,\ldots,n\}$.
We allow the algorithm access to a possibly erroneous oracle that, for each $i\in[n]$, outputs a quantity $p_{i}$, which should be interpreted as an estimation for the proportion of search queries that will be made to the data structure for the item $i$.
Hence, for each $i\in[n]$, we assume that $p_{i}\in[0,1]$ and $p_{1}+\ldots+p_{n}=1$.
Note that these constraints can be easily enforced upon the oracle as a pre-processing step prior to designing the skip list data structure.
We also assume that the oracle is readily accessible so that there is no cost for each interaction with the oracle.
Consequently, we assume the algorithm has access to the predicted frequency $p_{i}$ by the oracle for all $i\in[n]$.
On the other hand, we view a sequence of queries as defining a probability distribution over the set of queries, so that $f_{i}$ is the true proportion of queries to item $i$, for each $i\in[n]$.
Although $f_{i}$ is the ground truth, our algorithms only have access to $p_{i}$, which may or may not accurately capture $f_{i}$.

#### Consistency for accurate oracles.

We describe a construction for a learning-augmented skip list, which gives expected search time at most $2C+2\sum_{i=1}^{n}f_{i}\cdot\min\left(\log\frac{1}{p_{i}},\log n\right)$, for some constant $C>0$.
On the other hand, we show that any skip list construction requires an expected search time of at least the entropy $H(f)$ of the probability vector $f$.
We recall that the entropy $H(f)$ is defined as $H(f)=\sum_{i=1}^{n}f_{i}\cdot\log\frac{1}{f_{i}}$.

Thus, our results indicate that within nearly a factor of two, our learning-augmented skip list is optimal for any distribution of queries, provided that the oracle is perfectly accurate.
Moreover, even if the oracle on each estimated probability $p_{i}$ is only accurate up to a constant factor, then our learning-augmented skip list is still optimal, up to a constant factor.

#### Implications to Zipfian distributions.

We describe the implications of our results to queries that follow a Zipfian distribution; analogous results hold for other skewed distributions, e.g., the geometric distribution.
It is known that if the $r$-th most common query/item has proportion $\frac{z}{r^{s}}$ for some $s>1$, then the entropy of the corresponding probability vector is a constant.
Consequently, if the set of queries follows a Zipfian distribution and the oracle is approximately accurate within a constant factor, then the expected search time for an item by our skip list is only a constant, independent of the total number of items, i.e., $\mathcal{O}\left(1\right)$.
By comparison, a traditional skip list will have expected search time $\mathcal{O}\left(\log n\right)$.

#### Robustness to erroneous oracles.

So far, our discussions have centered around an oracle that either produces estimated probabilities $p_{i}$ such that $p_{i}=f_{i}$ or $p_{i}$ is within a constant factor of $f_{i}$.
However, in some cases, the machine learning algorithm serving as the oracle can be completely wrong.
In particular, a model that is trained on a dataset before a distribution change, e.g., seasonal trends or other temporal shifts, can produce wildly inaccurate predictions.
We show that our skip list is robust to erroneous oracles.
Specifically, we show that our algorithm achieves an expected search time that is within a constant factor of an oblivious skip list construction when the predictions are incorrect.
Therefore, our data structure achieves both consistency, i.e., good algorithmic performance when the oracle is accurate, and robustness, i.e., standard algorithmic performance when the oracle is inaccurate.

#### Empirical evaluations.

Finally, we analyze our learning-augmented skip list on both synthetic and real-world datasets. Firstly, we compare the performance of traditional skip lists with our learning-augmented skip lists on synthetically generated data following Zipfian distributions with various tail parameters. The dataset is created using four distinct
$\alpha$ values ranging from 1.01 to 2, along with a uniform dataset. During the assessment, we query a specified number of $n$ items selectively chosen based on their frequency weights. Our results match our theory, showing that learning-augmented skip lists have faster query times, with an average speed-up factor ranging from 1.33 up to 7.76, depending on the different skewness parameters.

We then consider various datasets for internet traffic data, collected by AOL and by CAIDA, observed over various durations.
For each dataset, we split the overall observation time into an early period, which serves as the training set for the oracle, and a later period, which serves as the query set for the skip list. The oracle trained using the IP addresses in the early periods outputs the probability of the appearance of a given node, and then the position of each node is determined.

Our learning-augmented skip list outperforms traditional skip lists with an average speed-up factor of 1.45 for the AOL dataset and 1.63 for the CAIDA dataset.
Moreover, the insertion time of our learning-augmented skip list is comparable with that of traditional skip lists on both synthetic and real-world datasets.
We also observe that our history-based oracle demonstrates good robustness against temporal change, with little shift in the dominant element set. The adopted datasets show that the set of the top frequent elements does not change much across the time intervals in the datasets used herein.

### 1.3 Background on Skip Lists

The skip list data structure as discussed in Section 1.1 is a commonly adopted structure that that utilizes probabilistic attributes within the data to allow fast search within an ordered sequence of elements. Its efficiency stems from its layered structure, where each element is inserted into multiple sorted linked lists, with the top layers providing a fast path for traversing the list. Studies around skip lists have been focusing on techniques to improve their performance under specific use scenarios. [] proposed a layered framework structure to handle in-memory key-value indexing. They proposed an ensemble consisting of two layers, a cache-sensitive structure that maintains a few guard entries, and a Semi-Ordered Skip-List which supports high concurrency in insertions and offers fast lookup and range querying capabilities. This semi-ordered approach allows for efficient data handling, particularly beneficial for systems with heavy insertion workloads. [] also improved upon traditional skip lists on persistent memory indexing applications. They introduced a hierarchical and partitioned skip list design, which reduces the height of the skip list and improves access locality. The skip list is organized into a hierarchy of component structures, which effectively enhances data access efficiency. [] also utilizes a neural network oracle for intelligent guard entry selection based on data and query distribution. This innovation ensures that the indexing structure adapts to the specific data characteristics, optimizing performance for various datasets.
[] presents a novel skip list implementation to address the performance degradation issue with traditional skip lists in key-value stores (KVS) that use multi-version concurrency control (MVCC). [] reimagines a skip list by separating the per-key updates from the key indexing process, which reduces the overhead typically associated with MVCC in skip lists. Their evaluation demonstrates the efficiency improvements by up to 42% decrease in query latency in the context of RocksDB, making them more suitable for modern KVS environments.

To the best of our knowledge, this study is the first to extensively evaluate the performance of a learning augmented skip list with a novel implementation algorithm with a theoretical performance guarantee.

## 2 Learning-Augmented Skip Lists

In this section, we describe our construction for a learning-augmented skip list and show various consistency properties of the data structure.
In particular, we show that up to a factor of two, our algorithm is optimal, given a perfect oracle.
More realistically, if the oracle provides a constant-factor approximation to the probabilities of each element, our algorithm is still optimal up to a constant factor.

### 2.1 Algorithm

We first describe our learning-augmented skip list, which utilizes predictions $p_{i}$ for each item $i\in[n]$, from an oracle.
Similar to a traditional skip list, the bottom level of our skip list is an ordinary-linked list that contains the sorted items of the dataset.
As before, the purpose of each higher level is to accelerate the search for an item, but the process for promoting an item from a lower level to a higher level now utilizes the predictions.
Whereas traditional skip lists promote each item in a level to a higher level randomly with a fixed probability $p\in(0,1)$, we automatically promote the item $i$ to a level $\ell$ if its predicted frequency $p_{i}$ satisfies $p_{i}\geq\frac{2^{\ell}-1}{n}$.
Otherwise, we promote the item with probability $\frac{1}{2}$.
This adaptation ensures that items with high predicted query frequencies will be promoted to higher levels of the skip list and thus be more likely to be found quickly.
We give the full details in Algorithm 1.

It is worth noting that the implementation algorithm of the augmented skip lists has undergone several rounds of updates to eventually show its performance as shown herein. For example, in the first attempt of augmentation, the position with median probability is used as the pivot to promote elements to higher levels. This promotion scheme becomes problematic since the get median function could induce considerable time overhead for insertion operations. To resolve this issue, a separate threshold probability is set for each level so that only nodes with a probability higher than the corresponding threshold are promoted to the next level. This approach provides an alternative to the find_median function, which avoids the time overhead. Yet, this approach fails to cater to the diverse range of distributions and turns out to show unstable performance. To further resolve this issue, an ensemble promotion framework is proposed. The proposed framework first filters out the low-frequency elements, which remain on the bottom level. Then for each level of the promoted nodes, a threshold was determined dynamically according to the current level of the element, i.e., a threshold $\theta=f(level)$. A similar problem arises for the ensemble for extreme cases of distributions. For example, the ensemble may fail to level up the elements for a uniform distribution since all elements have the same probability, thus the dynamic threshold will fail to distinguish the elements to be promoted from those to remain. The strategy to solve this problem, which is proposed in our algorithm, is to add a guard for those elements that have been promoted from the bottom level. The guard ensures that those elements with higher probabilities will still have a chance of being promoted to higher levels even when their probability is less than the corresponding threshold. This updated ensemble framework is theoretically and experimentally guaranteed to perform at least as good as a vanilla skip list, and also outperform a vanilla skip list for specific types of distributions like a Zipfian distribution.

Figure: Algorithm 1 Learning-augmented skip list

We first show that each item is promoted to a higher level with probability at least $\frac{1}{2}$.

###### Lemma 2.1 .

For each item $i\in[n]$ at level $\ell$, the probability that $i$ is in level $\ell+1$ is at least $\frac{1}{2}$.

###### Proof.

Note that if $p_{i}\geq\frac{2^{\ell}}{n}$, then $i$ will be placed in level $\ell+1$.
Otherwise, conditioned on the item $i\in[n]$ being at level $\ell$, then Algorithm 1 places $i$ at level $\ell+1$ with probability $\frac{1}{2}$.
Thus, the probability that $i$ is in level $\ell+1$ is at least $\frac{1}{2}$.
∎

We next upper bound the expected search time for any item at any fixed level, where the randomness is over the construction of the skip list.

###### Lemma 2.2 .

In expectation, the search time for item $i\in[n]$ at level $\ell$ is at most $2$.

###### Proof.

Suppose item $i\in[n]$ is in level $\ell$.
Let $S^{\ell}_{<i}\subseteq[n]$ be the subset of items in level $\ell$ that are less than $i$.
Note that by Lemma 2.1, each item of $S^{\ell}_{\leq i}$ is promoted to level $\ell+1$ with probability at least $\frac{1}{2}$.
Thus, the search time for item $i$ at level $\ell$ is $t$ if and only if the previous $t$ items in $S^{\ell}_{\leq i}$ were all not promoted, which can only happen with probability at most $\frac{1}{2^{t}}$.
Hence, the expected search time $T$ for item $i\in[n]$ at level $\ell$ is at most

$$ $\mathbb{E}\left[T\right]\leq 1\cdot\frac{1}{2}+2\cdot\frac{1}{2^{2}}+\ldots+n \cdot\frac{1}{2^{n}}\leq\sum_{t=1}^{\infty}\frac{t}{2^{t}}\leq 2.$ $$

∎

We now show that each item $i$ must be contained at some level depending on the predicted frequency $p_{i}$ of the item.

###### Lemma 2.3 .

Each item $i$ is included in level $\max\left(0,1+{\left\lfloor\log(np_{i})\right\rfloor}\right)$.

###### Proof.

First, observe that all items are inserted at level 0 0.
Next, note that Algorithm 1 inserts item $i$ into level $\ell$ if $p_{i}\geq\frac{2^{\ell-1}}{n}$ or equivalently $\log(np_{i})\geq\ell-1$.
Thus, each item $i$ is included in level $\max\left(0,1+{\left\lfloor\log(np_{i})\right\rfloor}\right)$.
∎

We next analyze the expected search time for each item $i$.

###### Lemma 2.4 .

Suppose the total number of levels is at most $C+\log n$ for some constant $C>0$.
Then the expected search time for item $i$ is at most $2C+2\min\left(\log\frac{1}{p_{i}},\log n\right)$.

###### Proof.

By Lemma 2.3, item $i$ is included in level $\max\left(0,1+{\left\lfloor\log(np_{i})\right\rfloor}\right)$.
By Lemma 2.2 the expected search time at each level is at most $2$.
Thus, in expectation, the total search time is at most $2(C+\log n-\max\left(0,1+{\left\lfloor\log(np_{i})\right\rfloor}\right))\leq 2
C+2\min\left(\log\frac{1}{p_{i}},\log n\right)$.
∎

Finally, we analyze the expected search time across the true probability distribution $f_{i}$.

###### Lemma 2.5 .

Suppose the total number of levels is at most $C+\log n$ for some constant $C>0$.
For each $i\in[n]$, let $f_{i}$ be the proportional of queries to item $i$.
Then the expected search time at most $2C+2\sum_{i=1}^{n}f_{i}\cdot\min\left(\log\frac{1}{p_{i}},\log n\right)$.

###### Proof.

For each query, the probability that the query is item $i$ is $f_{i}$.
Conditioned on the total number of levels being at most $C+\log n$, then by Lemma 2.4, the expected search time for item $i$ is at most $2C+2\max\left(\log\frac{1}{p_{i}},\log n\right)$.
Thus, the expected search time at most

$$ $\displaystyle 2C(f_{1}$ $\displaystyle+\ldots+f_{n})+2f_{1}\min\left(\log\frac{1}{p_{1}},\log n\right)+ \ldots+2f_{n}\min\left(\log\frac{1}{p_{n}},\log n\right)$ $\displaystyle=2C+2\sum_{i=1}^{n}f_{i}\min\left(\log\frac{1}{p_{i}},\log n \right).$ $$

∎

###### Lemma 2.1 .

###### Proof.

###### Lemma 2.2 .

###### Proof.

###### Lemma 2.3 .

###### Proof.

###### Lemma 2.4 .

###### Proof.

###### Lemma 2.5 .

###### Proof.

### 2.2 Near-Optimality

We first recall the construction of a Huffman code, a type of variable-length code that is often used for data compression.
The encoding for a Huffman is known to be an optimal prefix code and can be represented by a binary tree, which we call the Huffman tree [].

To construct a Huffman code, we first create a min-heap priority queue that initially contains all the leaf nodes sorted by their frequencies, so that the least frequent items have the highest priority.
The algorithm then iteratively removes the two nodes with the lowest frequencies from the priority queue, which become the left and right children of a new internal node that is created to represent the sum of the frequencies of the two nodes.
This internal node is then added back to the priority queue.
This process is continued until there only remains a single node left in the priority queue, which is then the root of the Huffman tree.

A binary code is then assigned to the paths from the root to each leaf node in the Huffman tree, so that each movement along a left edge in the tree corresponds to appending a 0 to the codeword, and each movement along a right edge in the tree corresponds to appending a 1 to the codeword.
Thus, the resulting binary code for each item is the path from the root to the leaf node corresponding to the item.

Huffman coding is a type of symbol-by-symbol coding, where each individual item is separately encoded, as opposed to alternatives such as run-length encoding.
It is known that Huffman coding is optimal among symbol-by-symbol coding with a known input probability distribution [] and moreover, by Shannon’s source coding theorem, that the entropy of the probability distribution is an upper bound on the expected length of a codeword of a symbol-by-symbol coding:

###### Theorem 2.6 (Shannon’s source coding theorem) .

[]
Given a random variable $X\in[n]$ so that $X=i$ with probability $f_{i}$, let $L(X)$ denote the length of the codeword assigned to $X$ by a Huffman code.
Then $\mathbb{E}\left[L(x)\right]\geq H(f)$, where $H(f)$ is the entropy of $f$.

We now show a lower bound on the expected search time of an item drawn from a probability distribution $f$.

###### Theorem 2.7 .

Given a random variable $X\in[n]$ so that $X=i$ with probability $f_{i}$, let $T(X)$ denote the search time for $X$ in a skip list.
Then $\mathbb{E}\left[T(x)\right]\geq H(f)$, where $H(f)$ is the entropy of $f$.

###### Proof.

Let ${\mathcal{L}}$ be a skip list.
We build a symbol-by-symbol encoding using the search process in ${\mathcal{L}}$.
We begin at the top level.
At each step, we either terminate, move to the next item at the current level, or move down to a lower level.
Similar to the Huffman coding, we append a 0 to the codeword when we move down to a lower level, and we append a 1 to the codeword when we move to the next item at the current level.
Now, the search time for an item $x$ in ${\mathcal{L}}$ corresponds to the length of the codeword of $x$ in the symbol-by-symbol encoding.
By Theorem 2.6 and the optimality of Huffman codes among symbol-by-symbol encodings, we have that $\mathbb{E}\left[T(x)\right]\geq H(f)$, where $f$ is the probability distribution vector of $x$.
∎

###### Theorem 2.6 (Shannon’s source coding theorem) .

###### Theorem 2.7 .

###### Proof.

### 2.3 Zipfian Distribution

In this section, we briefly describe the implications of our data structure to Zipfian distributions.

We first recall the following entropy upper bound for a probability distribution with support at most $n$.

###### Theorem 2.8 .

[]
Let $f$ be a probability distribution on a support of size $[n]$.
Then $H(f)\leq\log n$.

We next upper bound the entropy of a probability vector that satisfies a Zipfian distribution with parameter $s$.

###### Lemma 2.9 .

Let $s,z>0$ be fixed constants and let $f$ be a frequency vector such that $f_{i}=\frac{z}{i^{s}}$ for all $i\in[n]$.
If $s>1$, then $H(f)=\mathcal{O}\left(1\right)$ and otherwise if $s\leq 1$, then $H(f)\leq\log n$.

###### Proof.

Since $f$ is a probability distribution on the support of size $[n]$, then by Theorem 2.8, we have that $H(f)\leq\log n$.
Thus, it remains to consider the case where $s>1$.
Since $z\leq 1$, we have

$$ $\displaystyle h(f)$ $\displaystyle=\sum_{i=1}^{n}\frac{z}{i^{s}}\log\frac{i^{s}}{z}$ $\displaystyle\leq s\sum_{i=1}^{n}\frac{\log i}{i^{s}}.$ $$

Note that there exists an integer $\gamma>0$ such that for $i>\gamma$, we have $\frac{\log i}{i^{s}}<\frac{1}{i^{(s+1)/2}}$.
Since $s>1$, then $\frac{s+1}{2}>1$ and thus

$$ $\sum_{i=\gamma}^{n}\frac{1}{i^{(s+1)/2}}\leq\sum_{i=1}^{\infty}\frac{1}{i^{(s+ 1)/2}}=\mathcal{O}\left(1\right).$ $$

Hence,

$$ $\displaystyle h(f)$ $\displaystyle\leq s\sum_{i=1}^{\gamma-1}\frac{\log i}{i^{s}}+s\sum_{\gamma}^{ \infty}\frac{\log i}{i^{s}}=\mathcal{O}\left(1\right).$ $$

∎

By Lemma 2.5 and Lemma 2.9, we have the following statement about the performance of our learning-augmented skip list on a set of search queries that follows a Zipfian distribution.

###### Corollary 2.10 .

With high probability, the expected search time on a set of queries with exponent $s$ is at most $\mathcal{O}\left(1\right)$ for $s>1$ and $\mathcal{O}\left(\log n\right)$ for $s\leq 1$.

###### Theorem 2.8 .

###### Lemma 2.9 .

###### Proof.

###### Corollary 2.10 .

## 3 Predictor Robustness

In this section, we modify our algorithm to be robust to arbitrarily inaccurate oracles, while still ensuring consistency when the oracle is accurate.

### 3.1 Noisy Robustness

Let $f$ be the true-scaled frequency vector so that for each $i\in[n]$, $f_{i}$ is the probability that a random query corresponds to $i$.
Let $p$ be the predicted frequency vector, so that for each $i\in[n]$, $p_{i}$ is the predicted probability that a random query corresponds to $i$.
For $\alpha,\beta\in(0,1)$, we call an oracle $(\alpha,\beta)$-noisy if for all $i\in[n]$, we have $p_{i}\geq\alpha\cdot f_{i}-\beta$.

###### Lemma 3.1 .

Let $\alpha$ be constant and $\beta<\frac{1}{2n}$.
A learning-augmented skip list with a set of $(\alpha,\beta)$-noisy predictions has performance that matches that of a learning-augmented learned with a perfect oracle, up to an additive constant.

###### Proof.

Suppose the total number of levels is at most $C+\log n$ for some constant $C>0$.
Note that this occurs with a high probability for a learning-augmented skip list with a set of $(\alpha,\beta)$-noisy predictions.
For each $i\in[n]$, let $f_{i}$ be the proportion of queries to item $i$ and let $p_{i}$ be the predicted proportion of queries to item $i$.
By Lemma 2.5, the expected search time at most

$$ $2C+2\sum_{i=1}^{n}f_{i}\cdot\min\left(\log\frac{1}{p_{i}},\log n\right).$ $$

Since the oracle is $(\alpha,\beta)$-noisy then we have $p_{i}\geq\alpha\cdot f_{i}-\beta$ for all $i\in[n]$.

We first note that in the expected search time for $i$ is proportional to $\min\left(\log\frac{1}{f_{i}},\log n\right)$.
Thus, for expected search time for item $i$, it suffices to assume $f_{i}>\frac{1}{2n}$ for all $i$.

Observe that for $f_{i}>\frac{1}{2n}$ and $\beta<\frac{\alpha}{4n}$, then $p_{i}\geq\alpha\cdot f_{i}-\beta$ implies

$$ $p_{i}\geq\alpha\cdot f_{i}-\beta\geq\alpha\cdot f_{i}-\frac{\alpha}{4n}\geq \alpha\cdot\frac{\alpha}{2}\cdot f_{i}.$ $$

Hence, we have $\frac{1}{p_{i}}\leq\frac{2}{\alpha}\cdot\frac{1}{f_{i}}$ so that the expected search time for item $i$ is at most

$$ $2C+2\cdot\min\left(\log\frac{1}{f_{i}}+\log\frac{2}{\alpha},\log n\right).$ $$

Therefore, the expected search time is at most

$$ $\displaystyle 2C+2\sum_{i=1}^{n}f_{i}\cdot\min\left(\log\frac{1}{p_{i}},\log n\right)$ $\displaystyle\leq 2C+2\sum_{i=1}^{n}\left(f_{i}\cdot\min\left(\log\frac{1}{f_{ i}},\log n\right)+f_{i}\cdot\log\frac{2}{\alpha}\right)$ $\displaystyle\leq 2C+2\log\frac{2}{\alpha}+2\sum_{i=1}^{n}f_{i}\cdot\min\left( \log\frac{1}{f_{i}},\log n\right).$ $$

Since the perfect oracle would achieve runtime $2C+2\sum_{i=1}^{n}f_{i}\cdot\min\left(\log\frac{1}{f_{i}},\log n\right)$, then it follows that a learning-augmented skip list with a set of $(\alpha,\beta)$-noisy predictions has performance that matches that of a learning-augmented learned with a perfect oracle, up to an additive constant.
∎

###### Lemma 3.1 .

###### Proof.

### 3.2 Consistency and Robustness

To ensure both robustness and consistency, we can provide the following adaptation.
We first build a learning-augmented skip list ${\mathcal{L}}_{1}$ using the procedure in Algorithm 1.
We then build a normal skip list for the items whose predicted values ${\mathcal{L}}_{2}$ are less than $\frac{1}{n}$, i.e., $p_{i}\leq\frac{1}{n}$.
We then append ${\mathcal{L}}_{2}$ below the first level in ${\mathcal{L}}_{1}$.

Figure: Algorithm 2 Robust learning-augmented skip list

We first show the consistency of our algorithm, i.e., good algorithmic performance when the oracle is accurate.

###### Lemma 3.2 .

Algorithm 2 achieves a constant factor runtime of the optimal skip list when the predictions are correct.

###### Proof.

We claim that when the predictions are correct, then Algorithm 2 will demonstrate the same performance as Algorithm 1.
This is because an instantiation of Algorithm 1 creates the skip list ${\mathcal{L}}_{1}$, which is then inserted at the top of Algorithm 2.
Because the predictions are correct, then the search process will terminate at the bottom level of ${\mathcal{L}}_{1}$, never needing to search through ${\mathcal{L}}_{2}$.
By Lemma 2.5, we know that the expected search time through ${\mathcal{L}}_{1}$ is a constant factor of the runtime of the optimal skip list.
Thus, the desired claim follows.
∎

We next show the robustness of our algorithm, i.e., standard algorithmic performance when the oracle is inaccurate.

###### Lemma 3.3 .

Algorithm 2 achieves a constant factor runtime of an oblivious skip list construction when the predictions are incorrect.

###### Proof.

We first note that ${\mathcal{L}}_{1}$ has height $\mathcal{O}\left(\log n\right)$.
Moreover, an oblivious skip list construction has expected search time $\mathcal{O}\left(\log n\right)$.
Since ${\mathcal{L}}_{2}$ is a standard skip list construction, then in expectation, the total search time is $\mathcal{O}\left(\log n\right)$, even when the predictions are incorrect.
Therefore, the desired statement holds.
∎

###### Lemma 3.2 .

###### Proof.

###### Lemma 3.3 .

###### Proof.

## 4 Empirical Evaluations

In this section, we perform empirical evaluations comparing the performance of our learning-augmented skip list to that of traditional skip lists, on both synthetic and real-world datasets.
Firstly, we compare the performance of traditional skip lists with our learning-augmented skip lists on synthetically generated data following Zipfian distributions.
The proposed learning augmented skip lists are evaluated empirically with both synthetic datasets and real-world internet flow datasets from the Center for Applied Internet Data Analysis (CAIDA) and AOL. In the synthetic datasets, a diverse range of element distributions, which are characterized by the skewness of the datasets, are evaluated to assess the effectiveness of the learning augmentation. In the CAIDA datasets, the $\alpha$ factor is calculated to reflect the skewness of the data distribution.

The metrics of performance evaluations include insertion time and query time, representing the total time it takes to insert all elements in the query stream and the time it takes to find all elements in the query stream using the data structure, respectively.

The computer used for benchmarking is a Lenovo Thinkpad P15 with an intel core i7-11800H@2.3GHz, 64GB RAM, and 1TB of Solid State Drive. The tests were conducted in a Ubuntu 22.04.3 LTS OS. GNOME version 42.9.

### 4.1 Synthetic Datasets

In the synthetic datasets, both the vanilla and augmented skip lists are tested against different element counts and $\alpha$ values. In terms of the distribution of the synthetic datasets, the uniform distribution and a Zipfian distribution of $\alpha$ between 1.01 and 2 with query counts up to 4 million are evaluated. It is worth noting that the number of unique element queries could vary for the same query count at different $\alpha$ values in the Zipfian distribution, which may affect the insertion time.

**Table 1: Speed up factor of augmented skip list over vanilla skip list under different synthetic distributions**
| Distribution | Query size of synthetic data (unit: thousand) |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0.5 | 10 | 100 | 500 | 1000 | 1500 | 2000 | 2500 | 3000 | 3500 | 4000 | Average |  |
| uniform | 3.02 | 0.84 | 1.01 | 1.05 | 1.11 | 1.14 | 1.17 | 1.21 | 1.22 | 1.42 | 1.4 | 1.33 |
| $\alpha$=1.01 | 3.63 | 2.6 | 1.04 | 1.24 | 1.03 | 1.21 | 1.2 | 1.14 | 1.3 | 1.18 | 1.3 | 1.53 |
| $\alpha$=1.25 | 3.28 | 3.74 | 5.87 | 2.89 | 2.47 | 3.21 | 2.95 | 3.34 | 3.55 | 3.16 | 3.12 | 3.42 |
| $\alpha$=1.5 | 2.42 | 8.97 | 6.93 | 6.54 | 7.99 | 5.83 | 4.65 | 3.8 | 4.92 | 5.34 | 5.93 | 5.76 |
| $\alpha$=1.75 | 12.43 | 10.4 | 5.76 | 9.78 | 6.76 | 7.13 | 7.31 | 7.09 | 6.63 | 5.07 | 6.98 | 7.76 |
| $\alpha$=2 | 8.19 | 2.5 | 5.56 | 10.1 | 4.47 | 3.91 | 7.26 | 5.33 | 9.29 | 7.65 | 5.55 | 6.35 |

**Table 2: Node count for each distribution configuration in the 4 million dataset**
| $\alpha$ | Unique node count |
| --- | --- |
| 1.01 | 2886467 |
| 1.25 | 259892 |
| 1.75 | 8386 |
| 2 | 2796 |

Table 1 shows the speed-up factor, defined as the time taken by the augmented skip list over the vanilla skip list for the same query stream. We can observe a progressive improvement in the performance of our augmented skip lists as the dataset skewness increases. It also suggests that our augmented skip list will perform at least as good as the traditional skip list and will outperform a traditional skip list by a factor of up to 7 times depending on the skewness of the datasets.

Figure 1 shows that the insertion time decreases with more skewed datasets for the same size of the query stream. This is attributed to the reduced number of nodes in the datasets, as shown in Table 2.

The query time of augmented skip lists is also reduced greatly compared to the vanilla skip lists as shown in Figure 2.

### 4.2 CAIDA Dataset

In the CAIDA datasets [], the receiver IP addresses from one minute of the internet flow data are extracted for testing, which contains around 650k unique IP addresses of the 30 million queries.

Given that the log-log plot of the frequency of all nodes in the CAIDA datasets follows approximately a straight line in Figure 3, the CAIDA datasets can be approximately characterized by an $\alpha$ factor of 1.37.

The insertion time is similar between vanilla and augmented skip lists, while the query time is greatly reduced according to Figure 4.

It is worth noting that the results presented above assume that the frequency of all items in the query stream is accurate, which means the probability vector that is used to build the skip list matches exactly the query stream. However, this can be challenging to achieve in dynamic datasets where the probability vector may change over time. We hereby demonstrate that our proposed algorithm still manages to outperform the vanilla skip list even when temporal change exists in the probability vector. We demonstrate this by comparing the query time for the same set of query elements with different probability vectors being used to guide the building of the structure. The results are presented in Figure 4(a).

In Figure 4(a), color bars indicate the different skip list structures being compared, namely the vanilla skip list, the skip list augmented by noisy probability vectors, and the skip list augmented by perfect learning. In the vanilla skip list, as explained earlier, all elements are promoted to higher levels with equal chance. For the skip list augmented by a noisy probability vector, the probability vector of elements during a period of T1 is used as the reference probability vector. The skip list being augmented by this probability vector has its own set of elements to be organized into the target skip list. Suppose the historic data from T1 contains a set of elements S1, and some future query stream contains a set of elements S2. For each element in our target set S2, if the element is present in S1, then the occurrence probability of this element from S1 will be used to build S2; otherwise, if the element has not shown up during T1 (i.e., in S1), then we assume its probability to be 0. After this, the probability vector is normalized to sum to 1, resulting in a predicted probability vector to be used to build a skip list based on the historic element frequency. The dict-type object which maps the element value to a probability value is also referred to as an oracle. Since there is temporal changes in the frequency of elements being queried, the predicted probability vector will show a discrepancy with the true probability vector. We show that even when the prediction is not perfect, the augmented skip list still performs better than a conventional skip list. The skip list with perfect learning means that the probability vector which is used to augment the skip list matches exactly the occurrence probability of queried items in the query stream.

The CAIDA datasets used in this study contain 12 minutes of internet flow data, which totals around 444 million queries. The indices on the x-axis in Figure 4(a) means:

- •
10_2: the first 10 minutes of data are used to create the reference (i.e., oracle) and the last 2 minutes are used to build and test the total query time using the former as reference.
- •
2_2: the 9th and 10th minutes data is used as reference and the last 2 minutes are used for testing.
- •
3_3: the 1st, 2nd and 3rd minutes of data are used to create reference and the 4th, 5th and 6th minutes of data are used for testing.
- •
6_6: the first 6 minutes are used to create the reference and the last 6 minutes are used for testing.

Figure 4(a) shows that the skip list with perfect learning shows the best performance, while the skip list augmented with noisy learning performs very close to the perfect learning scenario. It is also noted the closer the test data is to the reference data chronologically, the closer the noisy-augmented skip list will perform to the perfect learning skip list.

Further analysis of the temporal change of item frequency shows the reason behind the good performance of the history-based oracle. Figure 4(b) shows the change of intersection index between any 2 given minutes among the 12 minutes of CAIDA data. The intersection index is defined as the ratio of the number of shared queries to the total number of queries of any given 2 minutes of queries. Figure 4(b) shows that the number of intersects queries has decreased by about 6% after 12 minutes, which indicates that the probability of the majority of the elements will be predicted with good accuracy, resulting in good oracle performance.

### 4.3 AOL Dataset

The AOL dataset [] features around 20M web queries collected from 650k users over three months. The distribution of the queries is shown in Figure 6. The AOL dataset is a less skewed dataset than CAIDA with an alpha value of 0.75.

Figure 6 shows the distribution of the AOL queries with an estimated alpha value of 0.75. The AOL dataset resembles more to a slightly skewed uniform distribution with very few highly frequent items, which accounts for a lower improvement as in the case of AOL shown in Figure 7. The total number of queries for items with higher than 1000 frequency accounts for only 5% of the total number of queries for the AOL datasets. The learning-augmented skip list still outperforms the traditional skip list on this slightly skewed dataset. This result is also in line with the results from the synthetic data shown in Table 1 where lower alpha values have resulted in a lower speedup factor.

Figure: (a) Uniform Distribution
Refer to caption: extracted/5412172/images/Synthetic_Dataset/Uniform_Dist_Insert.png

Figure: (a) Uniform Distribution
Refer to caption: extracted/5412172/images/Synthetic_Dataset/Uniform_Dist_Query.png

Figure: (a) CAIDA data distribution
Refer to caption: extracted/5412172/images/Caida_Dataset/logx_caida.png

Figure: (a) Insert time on CAIDA
Refer to caption: extracted/5412172/images/Caida_Dataset/caida_cartesian_insert_time.png

Figure: (a) Robustness test on CAIDA datasets
Refer to caption: extracted/5412172/images/Caida_Dataset/oracle_test_query_time.png

Figure: (a) AOL data distribution
Refer to caption: extracted/5412172/images/AOL_Dataset/aol_data_logx.png

Figure: (a) Insert time on AOL
Refer to caption: extracted/5412172/images/AOL_Dataset/aol_insert.png

## 5 Conclusion

In this paper, we studied learning-augmented algorithms for data structure design.
In particular, we incorporated the learning-augmented paradigm into improving upon the traditional skip-list data structures.
We showed that given reasonably accurate advice on the ubiquitous Zipfian distribution, our data structure achieves significantly better performance than traditional skip lists.
Moreover, our data structure achieves both consistency and robustness, so that our algorithm does not overly suffer poor performance in the case that the advice is inaccurate.
We showed experimentally on both synthetic and real-world datasets that our learning-augmented skip list performs at least as well as a traditional random skip list, irrespective of the oracle’s accuracy and the nature of the input distribution.
Looking forward, there is potential for further exploration into skip list implementation that responds dynamically to dynamic datasets.
We hope our work inspires future studies to incorporate machine learning heuristics into provably better data structures.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: My main question is about the motivation of the kd tree setting as stated in the weaknesses section. 

Another question: Would the proposed skip list data structure be able to handle deletions? For instance, if we delete some elements after constructing the dataset, would it still have the property that for the remaining elements, the data structure is close to optimal wrt the adjusted relative query frequencies? It would be good to include some discussion of deletion in the paper.

Minor formatting comment: The font size used for plots needs to be made larger.
soundness: 2
strengths: The part on skip lists is a complete and meaningful contribution. The idea of promoting higher frequency elements to higher levels with more probability is both natural and easy to implement. Optimality as well as robustness of the proposed data structure is shown, and it is also shown to be superior in practice with both perfect and erroneous oracles.
summary: The paper considers the problem of augmenting search data structures like skip lists and kd trees with learning advice, in particular, an oracle that gives (possibly erroneous) estimates of the probability of query elements. When the oracle estimate is perfect, the search time for the proposed data structure is within a factor of 2 of the optimal expected search time (upto a constant additive slack). The estimator is also shown to be robust to errors in oracle estimates. For instance, even if the oracle is arbitrarily erroneous, the expected search time is still within a constant factor of the search time for the corresponding oblivious data structure. The superior performance of proposed data structures is also shown with experiments.

Some details of data structure construction: 

Skip lists: Skip lists are built in levels, with the bottom level as an ordered linked list. Higher levels store subsets of items to speed up search. Traditional skip lists promote items to higher levels randomly with a fixed probability (e.g., 1/2). In the proposed skip list, if an item's oracle probability exceeds a level dependent threshold, it is promoted up with probability 1 (this leads to faster access for more frequent items). For other items, they are still promoted up with a fixed probability (this leads to robustness to errors in oracle).

Kd tree: In traditional kd trees, each node splits the points according to the median across a selected dimension, iterating between different dimensions at different levels of the tree.  In the proposed data structure, one doesn't necessarily iterate between dimensions. The splitting point and dimension at any node is chosen such that the probability of the query being on either branch is as close to 0.5 as possible.
weaknesses: The part on kd trees felt rushed and left me confused about both the motivation and the details of the setting.

Motivation: In the paper, kd trees are considered for doing lookups for high dimensional points (as opposed to nearest neighbor search). But if one is just interested in lookups, it is unclear to me why we need kd trees. Why not just use something like the proposed skip lists after labeling the points from 1 to n? If we want to also support fast membership queries for frequent items not in the dataset, we can also add them to the skip list as is done in the current kd tree construction.

Setting: In the kd tree part, there is a big universe of items and a subset of it constitutes the dataset. The query can be any element in the universe. While in the skip list part, the  the query is always one of the dataset elements. Both settings seem reasonable but I was confused why different settings are considered in the two scenarios. It would be great if this can be clarified in the paper.

Details of the algorithm: It would be good to spend a paragraph discussing various algorithmic choices like was done in the skip list part (space doesn't seem to be a concern as the paper is already half page below the limit). For example, the motivation for handling low probability elements (prob less than 1/n^2) differently was unclear to me as there can be at most n of them. Also, if the authors can elaborate a bit more on how they are handling these points, that would be helpful.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. In the abstract, the paper claims that for Zipfian distribution, the expected search time for an item is constant, while the traditional skip list or KD tree has an expected search time of $O(\log n)$. However, I could not find a detailed explanation for this claim in the main text. Specifically, is there theoretical support for vanilla skip lists (without learning) showing that the expected search time is $\Omega(\log n)$ under a Zipfian input distribution?
2. In the abstract, the paper claims for arbitrarily incorrect predictions, the algorithm is within a constant factor. Does this exactly come from your $(\alpha,\beta)$-noisy definition?
2. The noise robustness measure is unconventional. I suggest using KL divergence to quantify the distance between the predicted and true frequency distributions, as it may provide a more standard and interpretable measure of prediction accuracy.
3. I suggest adding additional experiment comparisons with other learning-augmented algorithms.
soundness: 4
strengths: 1. The integration of learned frequencies into skip lists and KD trees is well-constructed and achieves optimal performance.
2. Experiments show that the proposed algorithm outperforms classical algorithms and is robust to noise.
3. The paper is clearly written and easy to read. The ideas are simple, yet novel and effective. I appreciate the clear comparison
summary: The paper proposes learning-augmented search data structures based on skip lists and KD trees. The authors achieve optimal expected search time and demonstrate robustness to inaccurate frequency predictors. Experimental results verify the effectiveness of the proposed algorithms.
weaknesses: 1. The authors slightly overstate their contributions. For example, the claim of constant expected search time under the Zipfian distribution holds only when the exponent $s>1$, which is due to the entropy being of constant order (Lemma 2.3). In other words, for any data structure that achieves optimality has the same property. Additionally, in the abstract, the claim on the robustness when predictions are arbitrarily incorrect is not what you describe later.
2. The noise robustness measure, denoted as $(\alpha,\beta)$-noisy, is somewhat unconventional and may lack generality.
3. The experiments do not include comparisons with other learning-augmented algorithms given frequency predictions.
4. A closely related work [1] is not discussed in the paper, where the authors propose learning-augmented search trees that achieve optimality for arbitrary input distributions.

[1] Cao X, Chen J, Chen L, et al. Learning-augmented b-trees[J]. arXiv preprint arXiv:2211.09251, 2022.

---

confidence: 3
contribution: 2
initial_rating: 8
presentation: 4
questions: - In the experiments, as I understood, simple history-based oracles were used. Is it the main use-case of the proposed method, or do we expect large oracles, such as deep learning models to be used as well?
- If the main use case will be using large machine learning oracles, I have the following question: for example, for image search, an oracle can be a neural network that takes an image and outputs expected query frequency; or for text search it could be a language model that outputs expected frequency of text or part of the text -- will the accuracy of real-world machine learning models be enough to guarantee improvement over conventional search structures?
- Would be nice to present graphs with theoretically expected improvement and actual improvement in various settings.
soundness: 3
strengths: - Provided approach is an elegant way to improve search data structure performance by considering probabilistic nature of the data. 
- Given the abundance of machine learning and statistical methods to serve as an oracle, proposed approach can be widely used in practice.
- New bounds were proven theoretically and experimental results partially support the theoretical findings.
summary: The  studies using machine learning models for improving other machine learning algorithms, namely search algorithms that use efficient data structures to organize data elements. 

The paper considers skip lists and KD-trees and augments them by adding an output of a learning algorithm. Skip lists organize data probabilistically in hierarchical and traversal is similar to binary search but with larger number of splits.

The paper consider unbalanced data distributions, mentioning that unbalanced distributions may result in suboptimal balancing behavior when underlying data structure construction algorithm expects balanced data. Authors propose to use an external machine learning algorithm that predicts statistics of the input data and provides an information to adjust the baseline search algorithm and data structure.

Proposed learning augmented skip list uses predicted probabilities to promote items to next levels with exponentially increasing required thresholds for predicted probabilities. 

While it may seem reasonable to use simple frequency estimation when number of possible items is not large, when number of items in the dataset is larger than number of encountered queries, having a machine learning oracle estimate expected frequency of previously unseen queries is a good idea. The work allows using such oracles to improve search data structures and proves better bounds on search time in general case and in case of an important and popular in real world datasets Zipfian distribution; and proves similar bounds for noisy oracle (representing real machine learning model with positive probability of incorrect guesses).

The idea behind learning augmented KD-tree is to make sure that each node or leaf has same probability on each tree height. Oracle predicted probabilities are used to ensure balanced splitting, improving search time if the oracle is usually correct. To limit algorithm complexity, low probability items are inserted into the tree using conventional approach. Similar bounds, as in case of skip lists, are proven for the augmented KD-tree.  

Empirically, the paper shows constant factor speedup of the augmented data structures, compared to the conventional approach
weaknesses: - From the paper it was not fully clear how to use proposed method with real machine learning oracle models (that non-trivially predict frequencies), instead of statistical oracles (that just calculate the table of frequencies).
- Some graphs, such as Figure 2, show a constant factor speed up. It would be nice to clarify what is theoretically predicted speedup in the cases of various datasets and parameters, and how theory aligns with practice.

---

confidence: 3
contribution: 2
initial_rating: 8
presentation: 3
questions: How do your methods and results compare to the learning-based data structures of Ailon et al. Cayton et al., and other works related to those? They seem to study very similar problems in related settings.

Ailon, N., Chazelle, B., Clarkson, K. L., Liu, D., Mulzer, W., & Seshadhri, C. (2011). Self-improving algorithms. SIAM Journal on Computing, 40(2), 350-375.

Cayton, L., & Dasgupta, S. (2007). A learning framework for nearest neighbor search. Advances in Neural Information Processing Systems, 20.
soundness: 3
strengths: The problems are interesting and relevant, the theoretical results seem solid, and the empirical results show improvement. It is overall a solid submission.
summary: The paper studies search data structures augmented with an "oracle" (some ML-based prediction) of query frequencies, which can be used to improve over the classical setting that assumes no foresight into the query distribution. It focuses specifically on skip lists and KD-trees. It develops ML-augmented analogs, proves bounds on their performance under perfect and imperfect predictions, and presents an empirical evaluation.
weaknesses: -- No related work section nor discussion, except for a couple of very specifically related recent/concurrent papers. No broader positioning in the literature; even though there is past work on very similar topics which goes unmentioned and unreferenced (like learning-augmented KD-trees in Cayton et al., see below). 

-- The font size in the figures is beyond excusable

Meta-review: The paper augments two classic data structures, skip lists and kd trees, with advice from an ML oracle. The proposed solution is near-optimal when the oracle is accurate, and is robust to errors of the oracle. The paper provides theoretical guarantees for their approach, and the experiments show its effectiveness. All the reviewers had positive assessments of the paper, and I recommend acceptance.

Decision: Accept (Poster)