Online List Labeling with Predictions
Authors: Samuel McCauley
Benjamin Moseley
Aidin Niaparast
Shikha Singh
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Algorithms with Predictions
Data Structures
Learned Indices
Online List Labeling
Resource Allocation
Beyond Worst Case Analysis
TL;DR: This paper gives a theoretical analysis of a list labeling data structure in the learning augmented algorithm model.

Abstract: A growing line of work shows how learned predictions can be used to break through worst-case barriers to improve the running time of an algorithm. However, incorporating predictions into data structures with strong theoretical guarantees remains underdeveloped.  This paper takes a step in this direction by showing that predictions can be leveraged in the fundamental online list labeling problem. In the problem, $n$ items arrive over time and must be stored in sorted order in an array of size $\Theta(n)$.  The array slot of an element is its label and the goal is to maintain sorted order while minimizing the total number of elements moved (i.e., relabeled). We design a new list labeling data structure and bound its performance in two models.  In the worst-case learning-augmented model, we give guarantees in terms of the error in the predictions.  Our data structure provides strong guarantees: it is optimal for any prediction error and guarantees the best-known worst-case bound even when the predictions are entirely erroneous. We also consider a stochastic error model and bound the performance in terms of the expectation and variance of the error. Finally, the theoretical results are demonstrated empirically.  In particular, we show that our data structure has strong performance on real temporal data sets where predictions are constructed from elements that arrived in the past, as is typically done in a practical use case.

Online List Labeling with Predictions
Samuel McCauley Department Computer Science
Benjamin Moseley
Tepper School of Business Carnegie Mellon University
Williams College Williamstown, MA 01267 sam0cs. williams edu
Pittshurgh, PA 15213 moseleyb@andrew. cmu edu
Aidin Niaparast
Shikha Singh
Tepper School of Business Carnegie Mellon University
Department of Computer Science
Williams College
Pittsburgh, PA 15213 aniapara@andrev. cmu. edu
Williamstown, MA 01267 shikha@cs. www.wiilaa .du
Abstract
A growing line of work shows how learned predictions can be used to break through worst-cast barriers improve the running time of algorithm. However, incorporating predictions into data structures with strong theoretical guarantees remains underdeveloped. This paper takes step in this direction by showing that predictions can leveraged in the fundamental online list labeling problem. In the problem, items arrive time and must be stored in sorted order in array of size (nn). The array slot of an element is its label and the goal is to maintain sorted order while minimizing the total number of elements moved (i.e., relabeled). We design a new list labeling data structure and bound its performance two models. In the worst-case error in the predictions. Our data structure provides strong theoretical guarantees- it is optimal for any prediction error and guarantees the best-known worst-case bound even when the predictions are entirely erroneous. We also consider a stochastic error model and bound the performance terms of the expectation and variance of the error. Fimally, the theoretical results are demonstrated empirically. In particular, we show that our data structure performs well on numerous real datasets, including temporal datasets where predictions are constructed from elements that arrived in the past (as typically done in practical use case).
sorninng-uggmeter model, we give guarantees in terms of the
1 Introduction
A burgconing recent line of work has focused on coupling machine learning with discrete optimization algorithms. The area is known as algorithms with predictions, or alternatively, learning augmented algorithms 41 44 This area has developed framework for beyond-word -worst-case analysis that is generally applicable. In this framework an algorithm is given prediction that can be erroneous. The algorithm can use the prediction to tailor itself to the given problem instance and the performance is bounded terms of the error in the prediction.
Much prior work has focused on using this framework in the online setting where learned predictions are used cope with uncertainty [36]. This framework has been further used for warm-starting offline algorithms to improve the beyond worst-case running times of combinatorial optimization problems. This includes results on weighted bipartite matching (2T, maximum flows [[5]. shortest-palee [
and convex optimization [46]
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

A key question is to develop theoretical understanding of how to improve the performance of data structures using learning. Kraska et al. [35] jump-started this area by using learning to improve the performance of indexing problems. Follow up work on learned data structures (e.g. [8 47
have demonstrated their advantage over traditional worst-case variants both empirically and through improved bounds when the learned input follows a particular distribution; see Section 1.2
The theoretical foundation of using learned predictions in data structures remains underdeveloped. In particular, while there has been some initial work analyzing data structures with predictions there are no known analysis frameworks showing how the performance of learned data structures degrade as function of the error in prediction (as in i.e. [4.). In this paper, we take a step in this direction by showing how leverage the learning- -agmmneedd algorithms framework for the fundamental online list labeling problem. We bound its performance in terms of the error in the prediction and show that this performance the best possible for any error.
(i.e. [22 40
In the online list labeling problen D the goal is to efficiently store a list of dynamic elements in sorted order, which is a common primitive in many database systems. More formally, set of n elements arrive over time and must be stored in sorted order in an array of size en, where c >> is a constant. The array slot of an element (i.e. its position in the array) is referred to as its label. When new element arrives, it must be stored in the array between its predecessor and successor which may necessitate shifting (relabeling) other elements to make room. The goal of list labeling data structure is to minimize the number of elements moved; we refer to the number of element movements as the cost. The challenge is that the insertion order is online and adversarial, and the space is limited. A greedy approach, for example, might end up moving (2()) elements each insert.
List labeling algorithms have been studied extensively for over forty years, sometimes under different names such as sparse tables [30], packed memory arrays [4] 77, sequential file maintenance [51454], and order maintenance 19 We call any data structure that solves the list labeling problem a list labeling array (LLA). Itai et al. 30) gave the first LLA which moves Olog" n) elements average over all inserts. This has since been extended to guarantee O(log" n) elements are moved on any insert [52]. These results are tight as there is an 22oog" 2 n) lower bound on the amortized number of movements needed for any deterministic algorithm [10. A recent breakthrough result has shown that a randomized LLA can achieve an improved bound of Olog'// n) amortized movements B.
The LLA is basic building block in many applications, such cache-oblivious data structures 6 database indices 43 and joins (1., dynamic graph storage [88 42 50), and neighbor search in particle simulations 23 . Recently, LLAs have also been used in the design of dynamic learned
indices 200. which we describe in more detail in Section 1.2
Due to the their wide use, several prior works have attempted to improve LLAs using predictions heuristically. Bender et al. 7 introduced the adaptive packed memory array (APMA) which tries to adapt to non-wors case input sequences. The APMA uses hcuristic predictor predict future inserts. They show guarantees only for specific input instances, and Ieave open the question of improving performance more general inputs. Follow up data structures such as rewired PMA [17 and gapped arrays (20) also touch on this challenge-hool to adapt the performance cost of a deterministic LLA algorithm to non-wors' case inputs, while still maintaining Ollog" n.) worst case amortized cost.
A question that looms is whether one can extract improved performance guarantees using learned predictions on general inputs. An ideal algorithm can leverage accurate predictions give much stronger guarantees than the worst case. Further, the data structure should maintain an Olog" n) guarantee in the worst case even with completely erroneous predictions. Between, it would be ideal to have a natural trade-off between the quality of predictions and the performance guarantees.
1.1 Our Contributions
In this paper, we design a new data structure for list labeling which incorporates Iearned predictions and bound its performance by the error in the predictions. Our theoretical results show that high- quality predictions allow us to break through worst-case lower bounds and achieve asymptotically improved performance. As the error in the prediction grows, the data structure's 's performance degrades proportionally, which is never worse than the offte-ofthhe-- art LLAS Thus, the algorithm gives improvements with predictions at asymptotic cost. This is established in both worst-case
We use 'online list labeling' and 'list labeling' interchangeably; the problem is trivial in the offline setting.

---

and stochastic models. Our experiments show that these theoretical improvements are reflected in practice.
Prediction model. We define the model to state our results formally. Each element x has a rank Tz that is equal to the number of elements smaller than after all elements arrive. When an element arrives, a predicted rank Tr is given. The algorithm can use the predicted ranks when storing elements and the challenge is that the predictions may be incorrect. Define Th = F. Tal as x's prediction error. Let r max, 1 be the maximum error in the predictions.
Upper bounds. In Section 3 we present a new data structure, called a learnedLLA, which uses any list labeling array as a black box. We prove that it has the following theoretical guarantees.
Under arbitrary predictions, the rearnedLLA guarantees an amortized cost of Ologg n) per insertion when using a classic LLA 30 a black box. This implies that the algorithm has the best possible (1) cost when the predictions are perfect (or near perfect). Even when 17 = n2, the largest possible prediction error, the cost is O(log" 12), matching the lower bound on deterministic algorithms. Between, there is graceful degradation in performance that is logarithmic in terms of the error. In fact, these results are more general. Given a list labeling algorithm (deterministic or randomized) with an amortized cost of C(n), for a reasonable"
function C, our data structure guarantees performance C(n). This implies the new data structure can improve the performance of any known LLA. See Section 3.2
We also analyze the learnedLLA when the error 7> for each element is sampled indepen- dently from an unknown probability distribution D with average error ju and variance s². Under this setting, we show that the amortized cost is Ollgg" (Iul + x²)) in expectation. In- terestingly, the arrival order of elements can be adversarial and even depend on the sampled errors. This implies that for any distribution with constant mean and variance, we give the best possible (()) amortized cost. See Section 3.4
Lower bound. A natural next question is whether the learnedLLA is the best possible or if there is an LLA that uses the predictions in way that achieves stronger amortized cost. In Section 3.3 we show our algorithm is the best possible: for any n,, any deterministic algorithm must have amortized cost least (logg n)). matching our upper bound. Thus, our algorithm utilizes predictions optimally.
Empirical results. Finally, we show that the theory is predictive of empirical performance in Section 4 We demonstrate on real datasets that: (I) the learnedLLA outperforms state-of-the-ar baselines numerous instances. (2) when current LLAs perform well, the learnedLLA matches or even improves upon their performing, indicating minimal overhead from using predictions, (3) the LcarnedLLA is robust to prediction errors, (4) these results hold real-time-series datasets where the past is used to make predictions for the future (which is typically the use case in practice), and (5) we demonstrate that small amount of data is needed to construct useful predictions.
1.2
Related Work
See
44
for an overview of
algorithms in general.
Learned replacements of data structures. The seminal work on learning- augmeeteed algorithms by
[55] focus designing and analyzing a learned index, which replaces a traditional data structure like a B-tree and outperforms it empirically on practical datasets. Interestingly, the use of learned indices directly motivates the learned online list labeling problem. To apply learned indices on dynamic workloads, it is necessary to efficiently maintain the input in sorted order in an array. Prior work (20) attempted address this through a greedy list labeling structure, gapped array. A gapped array, however, can easily incur Q(n) element movements per insert even on non-worst case inputs. This bottleneck does not manifest itself in the theoretical or empirical performance of learned indices so far as the input is assumed to be randomly shuffled. Note that random order inserts are the best case for list labeling and incur (11) )) amortized cost in expectation [5] In contrast, our guarantees hold against inputs with adversarial order that can even depend on the prediction errors.
Kraska et al. [35), and several follow up papers (0 25 28
32
33
39
Besides learned indices replacing B-trees, other learned replacements of data structures include hash tables 24 45 and rank-and-select structures 9 26 27
PSpecifically, for admissible cost functions ((n) as defined in Detinition
3

---

Learned adaptations of data structures. In addition to approaches that use a trained neural net to replace a search tree or hash table, several learned variants of data structures which directly adapt to predictions have also been designed. These include learned treaps [2] 38 filters
and count-min sketch [22 29]. The performance bounds of most of these data structures assume perfect
g 40
47
49
predictions; when robustness to noise in predictions is analyzed (see e.g. (38)), the resulting bounds
revert to the worst case rather than degrading gracefully with error. The learnedLLA is unique in the landscape of learned data structure as it guarantees (a) optimal bounds for any error, and (b) best worst-case performance when the predictions are entirely erroneous.
Online list labeling data structures. The online list labeling problem is described in two different but equivalent ways: storing a dynamic list of n items in a sorted array of size m, or assigning labels from {I..... m) to these items where for each item z, the label {(x) is such that x < y = ((x) f(y).
We focus on the linear regime of the problem where m. cn, and c > is a constant.
If an LLA maintains that any two elements have (1)) empty slots between them, it is referred to as packed-memory array (PMAs) 4 PMAs are used as a subroutine in many algorithms: e.g. applied
graph algorithms []6 18 42
48 50)
and indexing data structures 4 20 (4).
A long standing open question about LLAs-whether randomized LLA algorithms can perform better than deterministic was resolved in a recent breakthrough. In particular, Bender et al. [3 extended the history independent LLA introduced in [ and showed that it guarantees O 3/2 n) amortized expected cost. The learnedL.LA LLA achieves Ollgg//2 n)) amortized cost when using this LLA a black box inheriting its strong performance; see Corollary 5
Bender and Hu 7 gave the first beyond- LLA, the adaptive PMA (APMA). The APMA has O(log n amortized cost on specialized sequences: sequential (increasing/ decreasing), hammer (repeatedly inserting the predecessor of an item) and random inserts. APMA also guarantees Ollgg" n) amortized cost in the worst case. Moreover, the APMA uses heuristics to attempt to improve performance on inputs outside of these specialized sequences. These heuristics do not have theoretical guarantees, but nonetheless, the APMA often performs better than classic one empirically 77) [6]. While the LearnedLLA bounds (based on prediction error) are incomparable with that of the APMA, our experiments show that the learneLLLA outperforms the APMA numerous datasets. In fact, if we combine our techniques by using an adaptive PMA as the black-box LLA of the learnedLLA, it performs better than both of them, reinforcing its power and versatility.
Preliminaries
In this section we formally define the list labeling problem, our prediction model, and the classic list labeling data structures we use as a building block in Section 3
Problem definition. In the online list labeling problem, the goal is to maintain a dynamic sorted list of n elements in an array of m = en slots for some constant > 1. We refer to n as the capacity of the array, m as the size, and n/m as the density. The label of an element is the array slot assigned to it. As new elements arrive, existing elements may have to be moved to make room for the new element. All elements come from an ordered universe of possible elements U. The list labeling structure maintains that the elements in the array must be stored in sorted order-for any I4, stored in the array, x; < I then the label of i; must be less than the label of xz
We refer to a data structure for this problem as a list labeling array (LLA). An element movement is said occur each time an element is assigned new label We use the term element movements and relabels interchangeably. The total cost of an LLA is the total number of element movements. The amortized cost of an LLA is the total cost during k insertions, divided by k. This cost function is standard both in the theory and practice of LLAs (see e.g. 2
30)..
Data structure model. We assume that the set S of n elements are drawn one-by-one adversarially from U and inserted into the LLA. We use existing LLAs (e.g. [+ R0) as black box in our data structure. We consider any (possibly randomized) LLA A which supports the following operations:
(N)ERT((): Inserts x in A. The slot storing ær must be after the slot storing its predecessor, and before the slot storing its successor.
This means that every element has at least one element movement when is inserted.

---

IS': Given an empty LLA A and given a (possibly-empty) set S' S U, insert all elements from S' in A.
Note that (S") can be performed using O((S')) element movements as all |S elements are available offline, they can be placed in A one by one.
For simplicity we assume that n is a power of 2; our results easily generalize to arbitrary n. All logarithms in this paper are base 2.
In this work, we do not explicitly discuss deletes. However, our data structure can be easily extended to support deletes as follows. We build a learnedLLA with capacity 2n. We split all operations into epocks of length n. During an epoch we ignore all deletes. After the epoch completes, we rebuild the data structure, removing all elements that were deleted during the epoch. This costs O(n), so the amortized cost is increased by ((1).
We parameterize the amortized cost of the learnedI by the amortized cost function of INSERT for a black-box LLA algorithm of density 1/2 For background on how classic LLA, the packed-memory array (PMA) [4, (30, works see the full version in the Supplementary Material of the paper. Let C(n') upper bound the amortized cost to insert into LLA with capacity n' and size 2n'.
Definition 1. We say that cost function C(-) is admissible if: (1) all i, with < 2j. C(i) O(C()), (2) C(n')= = 22loon n'), and (3) for all j. E C(2 = O((())
Both C(n) = Ologg n) (the optimal cost function for any deterministic LLA) and C(n) (llog//2 n)) (the best-known cost function for any randomized LLA B are admissible. There is an unconditional lower bound that any LLA must have amortized cost at least 22(log n') 11.
3 Our Data Structure: the learnedLLA
In this section we design and analyze our data structure, the learnedLLA, which uses any generic list labeling array as a black box. Due to space restrictions some proofs are deferred; they can be found the supplementary materials or the full version of the paper.
In Section we describe the learnedL.LA In Section 3.2 we analyze the learnedl. under arbitrary predictions. In Section 3.3] we show that the learned is optimal for deterministic solutions to list labeling. Finally, in Section 3.4. we bound the performance of the learneLLLA under stochastic predictions (with adversarial insert order).
Learned list-labeling array. Our learned list labeling data structure partitions its array into subarrays, each maintained as its own list labeling array. At a high level, when an element æ; is inserted with its predicted rank T; we use T; to help determine which LLA to insert into while maintaining sorted order. Intuitively, the performance comes from keeping these constituent LLAs small: if the predictions are good, it is easy to maintain small LLAs. But, if some element has large prediction error, its L.A grows large, making inserts into more expensive.
3.1 Data Structure Deseription
The learnedLLA with capacity n operates on an array of m = 6n slots. At all times, the learnedLLA
partitioned into actual LLAs P2.... Pe for some f. In particular, we partition the m array slots into contiguous subarrays; each subarray is handled by a black-box LLA. We maintain that for all i < j. all elements P; are less than all elements in P,.
We define a tree to help keep track of the actual LLAs Consider an implicit, static and complete binary tree T' over ranks {L.... n).. Each node in T has a set of assigned ranks and assigned slots. Specifically, the äth node at height h has 2d assigned ranks {2 (i 1) + 1, 2
+ 2, 2¹1).
and 6- 2 assigned slots (2h 6(i 1) + 1,2 6(i - 1) + 2, 24 Gi..
We use each actual LLA as a black box to handle how elements are moved within its assigned slots. To obtain the lea label for an element I; in actual LLA Ps. we sum the black-box label of I; in P3 and the value of the smallest slot assigned to P3 minus 1.
'If we initialize LLA P, with m' slots, we never store more than m' /2 elements in P.. However, this choice is for simplicity, and our results immediately generalize to LLAs using different parameter settings.
5

---

Every actual LLA has a set of assigned ranks and assigned slots; these ranks and slots must be from some node in T. We say that the LLA corresponds to this node in T. Each root-to-leaf path in T passes through exactly one node that corresponds to an actual I.I.. This means that the assigned ranks of the actual L.LAs partition (1..... n) into l contiguous subsets, and the assigned slots of the actual LLAs partition (1....,m) m into e contiguous subsets.
If a node in T' not assigned to an actual LLA, it is useful consider the assigned ranks and slots that would be used if a LLA assigned to u were to exist. We call such a LLA a potential LLA. Any actual LLA is also a potential LLA. The sibling, parent and descendants of a LLA P3 refer to the LLAs corresponding to the sibling, parent and descendant nodes respectively of Pjs node in the tree.
For any potential LLA P.. let Pyl denote the number of assigned ranks of P.- Initially & = n and P; is assigned the ith leaf of T, where 1 S i ك that is to say, the actual LLAs begin the leaves of T, each with one assigned rank. The parameter e changes over time as elements are inserted.
Each element is inserted into exactly one actual LLA. If an LLA has density more than 1/2, we merge with the (potential or actual) LLA of its sibling node in T. This process is described below.
Insertion algorithm. To insert an item r into the learnedl LAA, let ip and ig be the index of the LLA containing the predecessor and successor of x respectively. If the successor of x does not exist, let ig = l (the last actual LLA); if the predecessor does not exist let ip = 1. Finally, let iz be the LLA whose assigned ranks contain Fr. Call INSERT(*) on LLA P, where: if ip > iz then i = ip: i < lz then i gg. and otherwise i izz-
The black-box LLA P. updates its labels internally, and these updates are mirrored in the learnedLLA.
If the insert causes the density of P. to go above 1/2, we merge it with its sibling LLA. Specifically, let Pp be the parent of P: it must currently be potential LLA. We take all actual LLAs that descendants of Pp. and merge them into a single actual LLA. Let Sp be the set of elements currently stored in the slots assigned to P, in the learnedLLA; thus, Sp consists exactly of the contents of all actual LLAs that are descendants of Pp. We call (S,) on Pp. after which P, is an actual LLA; all of its descendants are no longer actual LLAs. Note that after a merge, the assigned ranks and assigned slots of the actual LLAs still partition [1.....n] ] and {1...., m] respectively.
3.2 Arbitrary Predictions
In this section, we analyze the learneLLLA when the input sequence and associated predictions can be arbitrary. The adversary chooses elements one by one from the universe U. For each element, the adversary assigns a predicted rank (which can be based on past insertions, past predictions, and even the learnedLLA algorithm being used) and inserts the element. We show that the Lea achieves amortized cost ((C())), where 17 is the maximum error and C(.) is the admissible cost function for the amortized cost of inserting into the black box LLA being used.
Our proof begins with several structural results, from which the analysis follows almost immediately.
First, we show that to determine the overall asymptotic cost it is sufficient to consider the set of actual LLAs after all inserts are completed relabels during merges are lower-order term.
Lemma 2. For any sequence of insertions, Pr is the set of actual LLAS after all operations are completed, and C(-) is an admissible cost function for the LLAs, then the total number of element movements incurred by the learnedLLA is O (EpeP, |P| (()))
Proof. For a LLA P E Py. consider all potential LLAs that are descendants of P in T. Every p that is ever an actual LLA must be descendant of exactly one P E Pr.
First, we analyze the cost of all merges in descendants of P. The total capacity of all LLAS that are descendant of is PI log Pl. Since a merge operation has linear cost, the total number of element movements during all merges is O(IP) log PP).
Now, we must bound the cost of all inserts to descendants of P. Consider all inserts into all LLAs Pi, P2.... .., Pa that are descendant of P. Let k; be the number of inserts into some such LLA P;; the total cost of these inserts is (kk;C((PP)) < O(k:C((P))). All inserts into descendants of P are ultimately stored in P; thus, E k S Pl. Then the total cost of all inserts into LLAs that are descendant of P is Σg_ O(kCC((P)) = 0 O(P(C((P)

---

Summing between the merge and insert cost, and using C((P)) + log |P|
((C(
because C()) admissible, we obtain a total number of element movements of O PEPpp [PI C(((((()))))))))))))) | (P)) S ( (PI-C(()))
Lemma 3. If P is an actual LLA, then there exists an element z stored in with nj 2 PP//2.
Proof. Since P was formed by merging its two children P. and Pk in T, the density of either P, or Pk must have been at least 1/2; without loss of generality assume it was P..
r1, r1 + ,....,,2 be the sequence of P: ranks assigned to P. Let 2s and my be the smallest and ri, largest items in P. respectively, with predicted ranks r. and Fr. We must have F; 2 ri ri-since the predecessor of is not in P., Fx must be placed in the LLA whose assigned ranks contain Fss or in the LLA containing its successor (if T is larger than any rank assigned to the LLA containing its successor). Similarly, Fi T2 Therefore, ft fo S [P.| 1. There are at least 3 P: items in P, as its density is at least 1/2. Thus, T7 Ts 2 3 P. - 1. Thus, either I - ral 2 Pa or Te rel 2 Pl.
Noting that [P: = PP//2, either 77, 2 Pl/2 ne 2 1P1/2.
Theorem 4. For any sequence of at most insertions a with maximum enror n, the learnedLLA using LLAs with admissible cost function C() incurs ((n((n)) total element movements.
Proof. By Lemma 3 any PE Pr must have element with error least LP|/2. Thus, any P E Pp must have |P| I 2n. The actual LLAs partition the ranks, so ΣpEPy IPI = n.
By Lemma 2 and since C() admissible, the total number of element movements over a O (EEp,, (PI-C((P)) S (EPEP, PP| C(2m)) S ((n((n)).
Corollary 5. Using the classic PMA as LLA 4 30), the learnedLLA is deterministic and achieves Olog" 7) amortized element movements. Using the best-known randomized LLA (3), the learnedLLA achieves Ologa/2 n) amortized element movements.
3.3 Optimality for Deterministic Learned List Labeling
The LearneLLLA is clearly optimal on the two extremes:
perfect predictions (17 = 0) and completely erroneous predictions (1) n.). When predictions are perfect, the leamneLLLA does not need move any element. When 77 = n, it is easy to create instances where the predictions give no information about the rank of each item (e.g. if each prediction is F. 1). Bulánek al. (10) showed that, without predictions, any deterministie LLA with (n) slots can be forced to perform M(log" n) amortized element movements. Thus, the learnedI LA is optimal when v) n.
However, it is not clear if the above idea extends to intermediate error. In this section, we show that for deterministic LLAs, the learnedLLA is in fact optimal for all r7.
The intuition behind our proof is to split the learned list labeling problem into a sequence of M(n/n) subproblems of size 77. each handled by its own LLA algorithm. The given predictions within each subproblem are only accurate to within n7 therrfooree an adversary can force each LLA to get no information about an element's 's position within the L.A,, and by [00 perform no better than 2(log" n) amortized element movements.
The challenge is that the LLAS for the subproblems are not actually separate: we can't force the data structure allocate O(n) space to each LLA and keep this allocation static throughout the execution. The data structure may move elements between adjacent LLAs or shift the number of slots available to each, ability that disrupts black-box lower bound.
Lower bound summary. First, we define a new problem, shifted list labeling, which generalizes online list labeling to allow labels that "shift" over time rather than be confined {1, (1...., m). We show that this generalization does not increase cost: a data structure for shifted list labeling implies a data structure for online list labeling with the same asymptotic space and amortized cost.
Then, we partition the universe into n/n blocks. The adversary only inserts an element from a block its elements are spread over at most O(n) slots. Thus, the labels of the elements inserted from a particular block form a solution to the shifted list labeling problem this addresses the challenge of handling separate LLA subproblems. We apply the lower bound of [10] to items inserted from each block; therefore, any block from which 7) items are inserted must have 2(n log" 17) amortized cost.
7

---

Finally, the adversary implements a cleanup step which inserts extra elements to ensure that the predictions of all elements are accurate within 77. We show that constant fraction of the blocks had 1 elements inserted adversarially before the cleanup step. Each of these blocks must have had Oog"og" 1) element movements; summing we obtain the following theorem.
Theorem 6. For any nt and n, there exists an adversary that inserts items, each with error at most n, such that any deterministic data structure for learned list labeling with capacity and m cn slots incurs ((nlog" 11) total element movements.
3.4 Stochastic Predictions with Adversarial Insert Order
In this section, we assume that each predicted rank is the result of adding random noise to the true rank. In particular, given an unknown distribution D, for any item zi, we have Fü = rr+e, where each e, is sampled independently from D. This means that the eπror of each item is essentially sampled from D. as Th = |e.l. The arrival order of the elements can still be chosen adversarially, with full knowledge of the predicted ranks. In particular, we can describe our input model with the following adversary. The adversary first chooses n elements of the set from the universe U. For each element T, E S, the error is then sampled from D. Finally, the adversary can look at the predicted ranks and choose any insert order of elements S. In this model, we prove the following.
Theorem 7. Consider learnedLLA data structure using a black box LLA algorithm with admissible cost C()) The total element movements incurred over a sequence of at most n. insertions with stochastic predictions is O (n C(([p] + ))))).
As in Corollary immediately obtain deterministie learnedLLA with O(log" + +)) expected amortized cost, and a randomized learnedLLA with Ologg (Iw) + 8)) expected amortized cost.
4 Experiments
This section presents experimental results on real data sets. The goal is to show that the theory is predictive of practice. In particular, the aim is to establish the following.
The learnedLLA improves performance over baseline data structures. Moreover, for the common use case of temporal data, learning from the past leads to future improvements. Predictions made on only small amount past data lead to improved performance. * The learnedLLA is robust to large errors in the predictions.
Experimental setup. We compare the performance of two strong baselines with our algorithm. The first baseline is the Packed- Memory Arry (PMA) 4 and the second is the Adaptive Packed- -Memory Packed-Memory
Array (APMA) 77. We tested Learnedl LLA with both of these LLAs as the black box LLA; we call these the Lea PMA and LearnedL.LA LLA + APMA. To ensure all algorithms have the same memory, we implemented the PMA (resp. APMA) as a LearnedI.LA using PMA (resp. APMA) as black box, placing each element into the first black box LLA.
We use datasets from SNAP Large Network Dataset Collection 37 All the datasets we use are temporal. The timestamp is used for the arrival order, and an element feature is used for the value.
To generate the predictions for LeamedLLA, we contiguous subsequence Luain of the input in temporal order as our training data. Our test data Lee is a contiguous subsequence of the input that comes right after Tarinn again in temporal order.
We use two different algorithms for obtaining predictions:
predictor, (Lriin Liss):: For each element E Lyest. this function first finds the rank of a in Lurin- and then it scales it by Lesss/ Lrain Finally, it returns these predictions.
predictor, ( Lurinn L:ss):: Let a be the slope of the best-fit line for points
1)) the i'th element in Lurinn for each 1 S < Lariil to obtain Liminn where d the difference between the starting points of training and test data in our input sequence. Then it returns predictor, (Naoinn Inea).
{(i, T (i)) ((l)))se)) 1i5s Emiil First, this function adds a- a--d++ i. Loall
Let T and T,2 T be the first and second halves of Tamans respectively. To obtain the final pre- dictions for LeA,nedLLA, we calculate the predictions P. == predictor; (L 2 ) for i 2,
8

---

and run LearnedLLA on Lainn with both of these predictions. If P.- performs better, we use predictor,- (Lirann Lest) the final predictions for Lest
Experimental results. See Table for performance on several real data sets. Due to limited space, we only include plots on one data set: Gowalla [14], a location- based social networking website where users share their locations by checking in. The latitudes of each user used elements in the input sequence, The remaining plots are given in the suppimentary materials and the full version of the paper.
Gowalla (LocationID)
Gowalla (Latitude)
MOOC
AskUbuntu
email-Eu-core
PMA APMA LearneLLAA PMA LearnedLLA + APMA
7.14
14.56
19.22
24.56
21.49
7.38
15.63
16.70
10.84
21.43
3.36
6.06
11.99
14.27
16.55
3.36
6.15
12.13
8.49
16.55
Table I: Amortized cost of LLAs several real datasets. In all cases, we use the first and second 2 131072 entries as training and test data, respectively.
Figure la shows the amortized cost versus the test data size. For several values for k, we use the first and second n = 2 portions of the input as training data and test data, respectively. Figure lb shows the performance versus the training data size to illustrate how long it takes for the Learned to learn. The x-axis is the ratio of the training data size to the test data size (in percentage). Figure Ic is robustness experiment showing performance versus the noise added to predictions, using half of the data as training. In this experiment, we first generate predictions by the algorithm described above, and then we sample t percent of the predictions uniformly at random and make their error large as possible (the predicted rank is modified to I or ni, whichever is farthest from the current calculated rank). We repeat the experiment five times, each time resampling the dataset, and report the mean and standard deviation of the results of these experiments.
Scaling Data
Scaling Training Data Size
Robustness
Aftin
Annortzenng CosE
sermeciia
Amortzzed
Lesre A.A.
PML
12
13
14
15
16
19
20
30
40
10 20 30
40
k= soloothl
Training Deta Se Perzentage
Percentage of Ead Predictions
(a)
(b)
(c)
Figure 1: Latitudes in the Gowalla dataset. In Fig. la we use the first and second n = 2 entries
as training data and test data (resp.) for several values of k. In Fig. [b the data has fixed size n 2d7 elements, and we increase the size of the training data. In Fig. Ic training data and test data have size 2 and increase the percentage of "bad" predictions. The lines are the means of the experiments, and the clouds around them show the standard deviation.
Discussion. Results Table that most cases, using even a simple algorithm to predict ranks can lead to significant improvements in the performance over the baselines; in some cases by over 50%. Whenever the APMA outperforms the PMA, the learnedLLA inherits this performance gain when using the APMA black box, showing its versatility. Furthermore, as illustrated in Figure a small amount of past data some cases as small as 5% is needed to see a significant separation between the performance of our method and the baseline LLAs. Finally, Figure Ic suggests that our algorithm is robust to bad predictions. In particular, large as possible and significant fraction of the input have errors in their ranks, yet the Lea still able to improve over baseline performance. We remark that when an enormous number of predictions completely erroneous, the method can have performance worse than baselines.
this experiment, the maximum error is as
In the supplementary materials and the full version of the paper, we include more details about the above experiments and datascts, well more experiments which further support our conclusions.

---

Conclusion
In this paper, we show how use learned predictions to build a learned list labeling array. We analyze our data structure using the learning-augmentee algorithms model. This is the first application of the model to bound the theoretical performance of a data structure. We show that the new data structure optimally makes use of the predictions. Moreover, our experiments establish that the theory is predictive of practical performance on real data.
An exciting line of work is to determine what other data structures can have improved theoretical performance using predictions. A feature of the list labeling problem that makes it amenable the Boarning-augment algorithms model is that its cost function and online nature is similar to the competitive analysis model, where predictions have been applied successfully many problems. Other data structure problems with similar structure are natural candidates to consider.
Acknowledgmen's and Disclosure of Funding
Samuel McCauley was supported in part by NSF CCF 2103813. Benjamin Moseley was supported in part by a Google Research Award, an Infor Research Award, Carnegie Bosch Junior Faculty Chair, National Science Foundation grants CCF-2121744 and CCF-1845144 and U. S. Office of Naval Research grant N00014-22-1-2700 Aidin Niaparast was supported in part by U. S. Office of Naval Research under award number N00014-21-1-22 1--122233 and the Air Force Office of Scientific Research under award number 149550-20-1-0080. Shikha Singh was supported in part by NSF CCF 1947789.
References
[1] Michael A. Bender, Jonathan W. Berry, Rob Johnson, Thomas M. Kroeger, Samuel McCaulcy, Cynthia A. Phillips, Bertrand Simon, Shikha Singh, and David Zage. Anti-persistence persistent storage: History- independent sparse tables and dictionaries. Proc. 35th ACM Symposium on Principles of Database Systems (PODS), pages 289-302, 2016.
[2] Michael A Bender, Richard Cole, Erik D Demaine, Martin Farach-Coltor and Jack Zito. Two simplified algorithms for maintaining order in a list. In Proc. 10th Annual European Symposium on Algorithms (ESA), pages 152-164. Springer, 2002.
[3] Michael A Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, and Nicole Wein. Online list labeling: Breaking the log barrier. In Proc. 63rd Anmual IEEE Symposium on Foundations of Computer Science (FOCS), pages 980-999 980-990. IEEE, 2022.
[4] Michael A Bender, Erik D Demaine, and Martin Farach-Coll Colton. Cache-oblivious B-trees. In Proc. 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 399 409, 2000.
[5] Michael A Bender, Martin Sarach-Collon, and Miguel A Mosteiro. Insertion sort is O(n log n). Theory of Computing Systems (TOCS), 39:391-397, 2006.
[6] Michael A Bender, Jeremy T Fineman, Seth Gilbert, and Bradley C Kuszmaul. Concurrent cache- obbivious B-trees. In Proc. of the 17th Annual ACM Sympostum Parallelism in Algorithums and Architectures (SPAA), pages 228-237, 2005.
Michael A Bender and Haodong Hu. An adaptive packed-memory array. ACM Transactions on Database Systems (TODS), (1:4:)6:1-22:43 2007.
[8] Ioana O Bercea, Jakob Bæk Tejs Houen, and Rasmus Pagh. Daisy bloom filters. arXiv preprint arXiv:2205. 148994 2022.
[9] Antonio Boffa, Paolo Ferragina, and Giorgio Vinciguerra. A learned approach to design compressed rank/select data structures. ACM Transactions Algorithms (TALG), 18(3):1288, 2022.
[10] Jan Bulánck, Michal Kouckj, and Michael Saks. Tight lower bounds for the online labeling problem. In Proc. 44th Annual ACM Symposiun on Theory of Computing (STOC), pages 1185-11991 2012.
[11] Jan Bulánck, Michal Koucky, and Michael Saks. On randomized online labeling with polynomially many labels. In Proc. 40th International Colloquiun Automata, Languages, and Progranming (ICALP), pages 291-302. Springer, 2013.
10

---

[12] Jingbang Chen and Li Chen. On the power of Gaaning-auggmentn BSTs, arXiv preprint www.i::211..0222222 2022.
[13] Justin Y. Chen. Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song. Csaba Szepesvári. Gang Niu, and Sivan Sabato, editors, Proc. 39th Annual International Conference on Machine Learning, (ICML), volume 162 of Proceedings of Machine Learning Research, pages 3583-3602. PMLR, 2022.
[14] Eunjoon Cho, Seth A Myers, and Jure Leskovec. Friendship and mobility: user movement in location- based social networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1082-1090, 2011.
[15] Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster ford-fulkerson. In Proc. 40th International Conference on Machine Learning, (ICML). PMLR, 2023.
[16] Dean De Leo and Peter Boncz. Fast concurrent reads and updates with pmas. Prov. 2nd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), pages I 1-8, 2019.
[17] Dean De Leo and Peter Boncz. Packed memory arrays-rewired. In Proc. 35th IEEE International Conference on Data Engineering (ICDE), pages 830-841, IEEE, 2019.
[18] Dean De Leo and Peter Boncz. Tesco and the analysis structural dynamic graphs. Proceedings of the VLDB Endowment, 1466):055-11666, 2021.
[19] Paul Dietz. Maintaining order linked list. In Proc. 14th Annual ACM Symposium on Theory of Computing (STOC), pages 122-127, 1982.
[20] Jialin Ding, Umar Farooq Minhas, Jia Yu, Chi Wang, Jaeyoung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, et al. ALEX: an updatable adaptive learned index. In Proc, 46th Annual ACM International Conference on Management of Data (SIGMOD), pages 969-9899 984, 2020.
[21] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Proc. 34th Annual Conference Neural Information Processing Systems (NeurIPS), pages 10393-10406,, 2021.
[22] Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Putting the "leamiig" into Saarning-augmenten algorithms frequency estimation. Proc. 38th Annual International Conference on Machine Learning (ICML), pages
PMLR, 2021.
[23] Marie Durand, Bruno Raffin, and François Faure. A packed memory array to keep moving particles sorted. In Proc. 9th Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS), pages 69-77. The Eurographics Association, 2012.
[24] Paolo Ferragina, Hans-Peter Lehmann, Peter Sanders, and Giorgio Vinciguerra. Learned monotone minimal perfect hashing. arXiv preprint arXiv: 100004/1111111 1012, 2023.
[25] Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. Why are learned indexes so effective? Proc. 37th International Conference on Machine Learning (ICML), pages 3123-3132. PMLR, 2020.
[26] Paolo Ferragina, Fabrizio Lillo, Giorgio Vinciguerra. the performance of learned data structures. Theoretical Computer Science (TCS), 871:107-120, 2021.
[27] Paolo Ferragina, Giovanni Manzini, Giorgio Vinciguerra. Repetition linearity aware rank/select dictionaries. In Proc. 32nd International Symposium on Algorithmss and Computation (ISAAC). Schloss Dagstuhl-Lcibniz--eener für Informatik, 2021.
[28] Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. FTTing-tree -tre: data-aware index structure. In Proc. of the 19th Annual International Conference on Management of Data (ICDM), pages 11 1189-1206, 2019.
[29] Chen- Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In Proc. 7th Annual International Conference on Learning Representations (ICLR), 2019.
[30] Alon Itai, Alan Konheim, and Michael Rodeh. A sparse table implementation of priority queues. Proc. 8th Annual International Colloquium on Automata, Languages, and Programming (ICALP), pages 417-431, 1981.
11

---

[31] Zubair Khayyat, William Lucia, Meghna Singh, Mourad Ouzzani. Paolo Papotti, Jorge-Arnulfo Quiané- Ruiz, Nan Tang, and Panos Kalnis. Fast and scalable inequality joins. The VLDB Journal, 26(1):125-150. 2017.
[32] Andreas Kipf. Ryan Marcus, Alexander van Renen, Mihail Stoian, Altons Kemper, Tim Kraska, and Thomas Neumann. Sosd: A benchmark for learned indexes, arXiv preprint arXiv:1911.1301: 2019.
[33] Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. Radixspline: single-pass learned index. Proc. 3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, pages 1-5, 2020.
[34] Tsvi Kopelowitz. On-line indexing for general alphabets via predecessor queries on subsets ordered list. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 283-292. IEEE, 2012.
[35] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein, editors, Proc. 44th Annual International Conference Management Data, (SIGMOD), pages 489-504. ACM, 2018.
[36] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Shuchi Chawla, editor, Proc. 31st amnual ACM Symposium Discrete Algorithms, (SODA), pages 1859- 1877. SIAM, 2020.
[37] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: //snap. sanap.stanfore edu/data June 2014.
[38] Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In Proc. 35th International Conference on Machine Learning (ICML), pages 13431-13440. PMLR, 2022.
[39] Ryan Marcus, Emily Zhang, and Tim Kraska. Cdfshop: Exploring and optimizing learned index structures. In Proc. 46th Annual International Conference on Management of Data (SIGMOD), pages 2789-2792, 2020.
[40] Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. Proc. 31st
Annual Conference on Neural Information Processing Systems (NeurIPS), 31, 2018.
[41] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM (CACM), 65(7):33-33 35, 2022.
[42] Prashant Pandey, Brian Wheatman, Helen Xu, and Aydin Buluc. Terrace: A hierarchical graph container for skewed dynamic graphs. In Proc. 21st International Conference on Management of Data (ICDM), pages 1372-1385, 2021.
[43] Vijayshankar Raman. Locality preserving dictionaries: theory & application to clustering in databases. In Proc. 18th ACM Symposium on Principles of Database Systems (PODS). pages 337-345, 1999.
[44] Tim Roughgarden. Beyond the worst-case analysis of algorithms. Cambridge University Press, 2021.
[45] Ibrahim Sabek, Kapil Vaidya, Dominik Hom, Andreas Kipf, Michael Mitzenmacher, and Tim Kraska. Can Iearned models replace hash functions? Proceedings of the VLDB Endowment, (6(3):532-445, 2022.
[46] Shinsaku Sakaue and Taihei Oki. saarrte-coovex--allli-----ae framework for warm-starting algorithms with predictions. In Proc. 35th Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
[47] Kapil Vaidya, Eric Knorr, Michael Mitzenmacher, and Tim Kraska. Partitioned learned bloom filters. In Proc. 9th Annual International Conference Learning Representations (ICLR), 2021.
[48] Brian Wheatman and Randal Burns. Streaming sparse graphs using efficient dynamic sets. In Proc. 7th IEEE International Conference on Big Data (BigData), pages 284-294. IEEF, 2021.
[49] Brian Wheatman and Helen Xu, Packed compressed sparse row: A dynamic graph representation. In Proc. 22nd IEEE High Performance Extreme Computing Conference (HPEC), pages 1-7. IEEE, 2018.
[50] Brian Wheatman and Helen Xu. A parallel packed memory array to store dynamic graphs. In Proc. 23rd Workshop on Algorithm Engincering and Experiments (ALENEX), pages 31-45. SIAM, 2021.
[51] Dan E Willard. Inserting and deleting records in blocked sequential files, Bell Labs Tech Reports, Tech. 1981.
Rep.
12

---

[52] Dan E Willard. Maintaining dense sequential files in a dynamic environment. In Proc. 14th Annual ACM Symposium Theory Computing (STOC), pages 114-121, 1982.
[53] Dan E Willard. Good worst-case algorithms for inserting and deleting records in dense sequential files. In ACM SIGMOD Record, volume 15:2, pages 251-260, 1986.
[54] Dan E Willard. A density control algorithm for doing insertions and deletions in sequentially ordered file in good worst-case time. Information and Computation, 50-24,550-204, 1992.
[55] Jiacheng Wu, Yong Zhang. Shimin Chen, Jin Wang. Yu Chen, and Chunxiao Xing. Updatable learned index with precise positions. Proceedings of the VLDB Endowment, 14(8):1276-1288. 2021.
13


Reviews:
[{"review_id": "HtTGi2jatX", "reviewer": "Reviewer_x3tY", "summary": "The paper considers the online list labelling problem: A set of $n$ elements arrive online and have to be inserted into an $c\\cdot n, c>1$ constant, large array while the array must at all times be sorted. Every time an already inserted element is \"shifted\" in order to maintain the order, it incurs a cost of $1$ and the goal is to minimize the total cost. The variant of the problem studied here, is the one where alongside the arrival of each element the algorithm obtains a possibly erroneous prediction on the rank of that element.\n\nThe paper presents an algorithm, that if the total error $\\eta$ is defined as the maximum error in the predictions, has an amortised cost of $O(\\log^2 \\eta)$ and thus only constant cost when $\\eta$ is almost zero. This bound is tight for any deterministic algorithm. These results are complemented with empirical evaluation.", "questions": "- You repeatedly use the term array slot. Although I understand what you mean, this is to my knowledge not common terminology, right?\n\n- How does your algorithm perform if one defines the error to be the average error in the individual predictions? Are there any lower bounds for *any* algorithm in that case?\n\n- L217: what is an \"actual LLA\"?", "limitations": "No limitations or potential negative societal impact anticipated. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "It is an interesting problem and data structures with predictions are indeed not as developed as online problems with predictions.", "weaknesses": "- The writing is at places not very precise and can be misleading. To give an example saying that the data structure is \"optimal for any prediction error\" is not true. For one I think the authors use \"optimal\" to mean \"best possible\" which differs from the convention that optimal refers to the offline optimal algorithm which knows the whole input in advance. Furthermore even \"best possible\" would not be completely accurate since it  can be up to a constant factor worse than the best previously known result with predictions. Perhaps \"tight up to a constant factor\" would be accurate? See also L80 \"improvement at no cost\", or L79 where \"proportionally\" I think is meant to be \"linearly\" etc.\n\n- The prediction error is not very natural: Consider the scenario where one prediction is off by a lot and all others are perfect. Considering the maximum error in the predictions over all elements is heavily unfair against such a scenario where the predictions are arguably quite good and one could easily obtain an optimal insertion of all elements without (or with barely) any shifting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful comments.  We address your questions below. \n\n\n**Question:**  saying that the data structure is \"optimal for any prediction error\" is not true. For one I think the authors use \"optimal\" to mean \"best possible\" which differs from the convention that optimal refers to the offline optimal algorithm which knows the whole input in advance. \n\n**Answer:**  Indeed, we meant best possible for online algorithms up to constant factors.  We will change the wording to reflect this.  \n\n**Question:** The prediction error is not very natural: Consider the scenario where one prediction is off by a lot and all others are perfect. Considering the maximum error in the predictions over all elements is heavily unfair against such a scenario where the predictions are arguably quite good and one could easily obtain an optimal insertion of all elements without (or with barely) any shifting.\n\n**Answer:** It is a fair observation that maximum error may be pessimistic for cases where a single element has large prediction error.   Due to this, we also analyze performance using a stochastic model and show that the algorithm has strong performance when the average error and variance is small.  We elaborate more on this below. Furthermore, we show the algorithm is robust empirically when even a constant fraction of the elements have the maximum possible error (so long as a constant fraction of the elements have reasonably good predictions).\n\n*Stochastic Model:* We assume each element has an error drawn from a probability distribution.  The distribution can be arbitrary.  We show that the amortized cost is $O(\\log(\\mu s^2))$ where $\\mu$ is the mean of the distribution and $s^2$ is the variance.  Intuitively, so long as the variance and mean error are reasonable, this guarantees much better than worst-case bounds. \n\n*Example in the Stochastic Model:* Say each elements error is drawn from a distribution where with probability $1-1/n^{1/2}$ there error is constant and with probability $1/\\sqrt{n}$ the error is huge, say $n^{1/4}$.  In this case, we expect a significant number of elements, $\\sqrt{n}$ to have large error $n^{1/4}$.   However, the mean and variance are $O(1)$ and our algorithm guarantees the best possible (up to constant factors) $O(1)$ amortized look-up.  This works even with a worst-case insert order of these elements.\n\n**Question:** You repeatedly use the term array slot. Although I understand what you mean, this is to my knowledge not common terminology, right?\n\n**Answer:** We will define this in the preliminaries as a position (i.e. index) in the array.\n\n\n**Question:** How does your algorithm perform if one defines the error to be the average error in the individual predictions? Are there any lower bounds for any algorithm in that case?\n\n**Answer:**  In the paper we give some bounds for this case in the stochastic error model (see above).  Another possibility is to consider a model where the average error is small *and* the error over the elements is chosen in a worst-case adversarial sense.  We do not know an algorithm with similar guarantees and we believe addressing this case will require new techniques. We leave it as an intriguing open question. \n\n"}, {"review_id": "92zjsWjOJ4", "reviewer": "Reviewer_p1qT", "summary": "Author study a fundamental online problem which is also important\nin practice: online list labeling.\nThe introduce rank predictions for this problem and define prediction error\nin a natural way. They achieve O(1) consistency and a robustness comparable\nwith the best possible classical online algorithm.\nThey show that the dependence of their competitive ratio on prediction error\nis the best possible. They also analyze the case where the prediction\nerror comes from some unknown distribution.\nGiven the importance of the problem and soundness of the results, I recommend\nthis paper to be accepted.\n", "questions": " ", "limitations": "* authors state their theoretical results formally, describing all assumptions.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* important problem\n* tight bounds, complete analysis", "weaknesses": "* consistency is O(1) but not really close to 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review.   \n\n**Question:** consistency is $O(1)$ but not really close to $1$.\n\n**Answer:** If the predictions are perfect, then every element is inserted and never moves. This gives consistency $1$.  We will clarify this in the paper.\n"}, {"review_id": "kQIohQwRBl", "reviewer": "Reviewer_QPB8", "summary": "The author presented a novel learning-augmented algorithm for the online list labeling problem, providing solid theoretical guarantees in terms of the error in the predictions. They also investigated the stochastic error model and bound the performance in terms of the expectation and variance of the error. Finally, they carried out an experimental evaluation of the proposed methods.\n", "questions": "What other data structures will likely benefit from an approach similar to the one you used in this work?", "limitations": "I cannot identify any restrictions or potential negative effects this work may have on society.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Although the problem studied, online list labeling, might be considered quite peculiar for this conference, I believe it can be a seminal work for learning augmented data structures. I like this work very much because they provide solid performance guarantees, showing that our algorithm utilizes predictions optimally because their cost upper bound matches a lower bound shown in Section 3.3 for any prediction error. They also show that their algorithm is optimal in the case of entirely erroneous predictions and that for deterministic LLAs, the learned LLA is optimal for all prediction errors.\nI also appreciated the study of the case in which the error for each element x is sampled independently from an unknown probability distribution with a given average and variance error.", "weaknesses": "The main weakness of this work is that the problem studied, online list labeling, is quite specific. It would be interesting to apply this methodology to other data structures to solve problems that are more common and known. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review.   \n\n**Question:** What other data structures will likely benefit from an approach similar to the one you used in this work?\n\n**Answer:**  We believe that the model and general algorithmic ideas will be useful for some other data structures.  We have initial results that binary search trees, heaps, and nearest neighbor indices benefit from (1) adapting the learning-augmented framework used in this paper and (2) leveraging the algorithmic idea of partitioning the input and assigning them to black-box data structures based on their predictions.   \n"}, {"review_id": "SZNzDFI8RT", "reviewer": "Reviewer_v8Wd", "summary": "This paper is about the classic Online List Labeling problem in the recent model of algorithms with predictions (a.k.a. learning-augmented algorithms).\n\nIn this problem n orderable items (say, integers) arrive over time. We need to keep them in the sorted order in an array of size c*n, for some constant c. When the i-th item arrives, we know its relative ordering only with respect to the i-1 items that arrived before, so we do not know where to put it, and we might need to reinsert it later at a different location (in order to have space for future items while maintaining the sorted order). Our goal is to minimize the number of such reinsertions.\n\nThere is already known a deterministic data structure with amortized cost O(log^2 n) per insert, and a randomized one with cost O(log^3/2 n).\n\nIn this paper the authors propose a data structure that together with each new item receives a prediction on what would be the final rank of that item among all n items.\n\nThe data structure uses internally as a black-box a classic (prediction-less) data structure for the problem. Denoting by f(n) the cost of this internal black-box data structure – so, f(n) = O(log^2 n) if we want a deterministic solution, and f(n) = O(log^3/2 n) if we are fine with a randomized one – and assuming all predicted ranks are within eta from the true ranks, the amortized cost of the new algorithm is O(f(eta)). Moreover, if prediction errors are distributed according to a Gaussian distribution with mean mu and variance var, the cost is O(f((mu + var)^2)).\n\nThe main idea of the data structure is to maintain a tree-like structure over the inserted items, and delegate maintaining items in non-overlapping subtrees of different sizes to instances of a classic data structure for the problem. Locations of items in the tree are guided by their predicted ranks. If a data structure corresponding to a subtree becomes overfull because of prediction errors, it gets merged with neighboring subtrees. This general idea was already present in the literature around the problem, but the details of implementation and analysis are very novel.\n\nThe authors also provide results of some simple experiments. What is nice (and always present in learning-augmented literature) is that the predictions are actually learned from training data, so the experiments can be considered end-to-end. The cost improvements observed over classic data structures are roughly 50%.", "questions": "Would it be feasible to prove bounds in terms of average L1 prediction error per item, instead of L_inf error? In other words, is it really the case that only a few items with terrible predictions can ruin performance of the whole data structure?\n\nI'd be very interested in seeing results of similar experiments but done in an online learning, rather than batch learning, fashion. That is, using all the data as test data, and predicting rank of item i based on its relative rank among the previous i-1 items (possibly with the linear interpolation trick that you employed and some learning-with-experts algorithm telling whether to use the trick or not).\n\nThe claim in line 37 (that there are no earlier works that analyze effect of errors on learning-augmented data structures) seems not very accurate – see, e.g., the section on robustness guarantees in [12]. Similarly, a similar claim in lines 403–404 seems unjustified.\n\nMinor remarks:\n\nLine 54: \"moves O(log^2 n) elements\" -> \"moves O(log^2 n) elements per insert\"\n\nLine 56: \"a \\Omega\" -> \"an \\Omega\"\n\nLine 67: \"a LLA\" -> \"an LLA\"\n\nLine 68: \"worst case\" – if the bounds are only amortized, this is misleading\n\nLines 146–150: you mention the randomized result very late, I think it should be mentioned already in line 57, where you talk about the deterministic result.\n\nLine 72: \"would ideal\" -> \"would be ideal\"\n\nLine 96: the footnote mark's location is unfortunate, it reads \"C squared\"\n\nLine 194: \"(PMA)[4,30]\" -> \"(PMA) [4,30]\"\n\nLine 220: it would be nice to mention that such idea of a tree-like data structure already appears in the classic PMA\n\nLine 243: \"i_p=\\ell\" -> \"i_s=\\ell\"\n\nLine 329: \"that inserts n items\" -> \"that, for any n, inserts n items\"\n\nLine 515 in the full version: \"lemma\" -> \"theorem\"", "limitations": "There are only some minor limitations to this work:\n\n1) The lower bound holds only against deterministic algorithms.\n\n2) The performance guarantees are using the L_infty error measure, so it is not clear how the algorithm behaves when there is one outlier item with huge error but all other items are predicted almost correctly. The natural distribution analysis gives some hints that the performance of the algorithm should be good in such a case, but there is no formal proof.\n\n3) There are only pretty basic proof-of-concept experiments.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1) The main algorithm is nontrivial, yet simple and with a clearly visible main idea.\n\n2) I like the additional analysis of the algorithm's performance under prediction errors coming from a Gaussian distribution (on top of the more standard analysis in terms of the maximum prediction error).\n\n3) The algorithm uses existing classic data structures in a black-box manner, so it should be easy to implement and can leverage already optimized implementations of these data structures.\n\n4) The authors provide a matching lower bound (albeit only for deterministic algorithms).\n\n5) The paper is well written and easy to follow.\n\nSimply speaking, it is one of the most interesting recent papers that I have read in this area.", "weaknesses": "1) The studied problem seems relevant in practice, but I am not sure how important it really is – however, even if it is not, I find the paper sufficiently appealing on purely theoretical grounds to merit acceptance.\n\n2) The experiments are of a proof-of-concept style – e.g., datasets are adapted from benchmarks for other problems that have not much to do with this one – but it is a common thing for papers in this area.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review.   We greatly appreciate your comments on writing and will incorporate them in the final version of the paper.\n\n**Question:** would it be feasible to prove bounds in terms of average L1 prediction error per item, instead of L_inf error? In other words, is it really the case that only a few items with terrible predictions can ruin performance of the whole data structure?\n\n**Answer:** The paper introduces a stochastic model to show the algorithm has strong performance when the average error and variance are small.  We elaborate more on this below. Furthermore, we show the algorithm is robust empirically to the case where even a constant fraction of the elements have the maximum possible error (so long as a constant fraction of the elements have reasonably good predictions).\n\n*Stochastic Model:* We assume each element has an error drawn from a probability distribution.  The distribution can be arbitrary.  We show that the amortized cost is $O(\\log(\\mu s^2))$ where $\\mu$ is the mean of the distribution and $s^2$ is the variance.  Intuitively, so long as the variance and mean error are reasonable, this guarantees much better than worst-case bounds. \n\n*Example in the Stochastic Model*: Say each elements error is drawn from a distribution where with probability $1-1/n^{1/2}$ there error is constant and with probability $1/\\sqrt{n}$ the error is huge, say $n^{1/4}$.  In this case, we expect a significant number of elements, $\\sqrt{n}$ to have a large error $n^{1/4}$.   However, the mean and variance are $O(1)$ and our algorithm guarantees the best possible (up to constant factors) $O(1)$ amortized look-up.  This works even with a worst-case insert order of these elements.\n\nA new and interesting direction is to consider a model where the average error is small *and* the error over the elements is chosen in a worst-case adversarial sense.  We do not know an algorithm with similar guarantees and we believe addressing this case will require new techniques. We leave it as an intriguing open question. \n\n**Question:** I'd be very interested in seeing results of similar experiments but done in an online learning, rather than batch learning, fashion. That is, using all the data as test data, and predicting rank of item i based on its relative rank among the previous i-1 items (possibly with the linear interpolation trick that you employed and some learning-with-experts algorithm telling whether to use the trick or not).\n\n**Answer:**  We did not consider this case.  This is an interesting direction and we appreciate this comment.  We will investigate this for the journal version of this paper. \n\n\n**Question:** The claim in line 37 (that there are no earlier works that analyze effect of errors on learning-augmented data structures) seems not very accurate – see, e.g., the section on robustness guarantees in [12]. Similarly, a similar claim in lines 403–404 seems unjustified.\n\n**Answer:**  This is a good point. We will rephrase and include a more detailed comparison to guarantees in prior work. \n"}]

Author rebuttal:

Meta-review: This paper studies the online list labeling problem in the learning-augmented setting where the algorithm is given a prediction about the rank of each element upon arrival. The results are very strong, this paper has the potential to have an important impact in the area of learning-augmented data structures. The results are tight for deterministic algorithms and nicely solve the problem studied. I recommended acceptance.
Decision: Accept (spotlight)