Learned Index with Dynamic $\epsilon$
Authors: Daoyuan Chen
Wuchao Li
Yaliang Li
Bolin Ding
Kai Zeng
Defu Lian
Jingren Zhou
Venue: ICLR 2023 poster (2023)
Keywords: Learned Index
Dynamic $\epsilon$

Abstract: Index structure is a fundamental component in database and facilitates broad data retrieval applications. Recent learned index methods show superior performance by learning hidden yet useful data distribution with the help of machine learning, and provide a guarantee that the prediction error is no more than a pre-defined $\epsilon$. However, existing learned index methods adopt a fixed $\epsilon$ for all the learned segments, neglecting the diverse characteristics of different data localities. In this paper, we propose a mathematically-grounded learned index framework with dynamic $\epsilon$, which is efficient and pluggable to existing learned index methods. We theoretically analyze prediction error bounds that link $\epsilon$ with data characteristics for an illustrative learned index method. Under the guidance of the derived bounds, we learn how to vary $\epsilon$ and improve the index performance with a better space-time trade-off. Experiments with real-world datasets and several state-of-the-art methods demonstrate the efficiency, effectiveness and usability of the proposed framework.


LEARNED INDEX WITH DYNAMIC
Davyuan Chen', ; Wuchao Li²; Yaliang Li Bolin Ding, Kai Zeng" Defu Lian"! Jingren Zhou' Alibaba Group, University of Science and Technology of China, HHaawei
[dacyuanchen. cdy, yaliang. 1i, bolin. ding, jingren. Balobbbaabbb i wuchac@mail 1. ustc..eu..co kai. zengthuavei com, liandefuBusto.
ABSTRACT
Index structure is a fundamental component in database and facilitates broad data retrieval applications. Recent learned index methods show superior performance by learning hidden yet useful data distribution with the help of machine learning, and provide guarantee that the prediction error is no more than a pre-defined e. However, existing learned index methods adopt a fixed for all the learned segments, neglecting the diverse characteristics of different data localities. In this paper, we propose mathematically-ggounn dynamic 6, which is efficient and pluggable to existing learned index methods. We theoretically analyze prediction error bounds that link with data characteristics for an illustrative learned index method. Under the guidance of the derived bounds, we learn how to vary and improve the index performance with better space-time trade-off. Experiments with real-world datasets and several state-of-the- methods demonstrate the efficiency, effectiveness and usability of the proposed framework.
learned index framework with
INTRODUCTION
Data indexing (Graefe & Kuno, 2011 Wang et al. 2018 Luo & Carey) 2020; Zhou et al. 2020). which
stores keys and corresponding payloads with designed structures, supports efficient query operations over data and benefits various data retrieval applications. Recently, Machine Learning (ML) models have been incorporated into the design of index structure, leading to substantial improvements in terms of both storage space and querying efficiency (Kipl et al. 2019 Ferragina & Vinciguerra 2020a Vaidya et al.) 2021). The key insight behind this trending topic of "learned index" is that the data to be indexed contain useful distribution information and such information can be utilized by trainable ML models that map the keys {x) to their stored positions { To approximate the data distribution, state-of-the-ate (SOTA) learned index methods (Galakatos et al. 2019 Kipf et al. 2020 Ferragina & Vinciguerra) 2020b; Stoian et al., 202I) propose to learn piece- wise linear segments S = and N is the total number of learned segments. These methods introduce an important pre-defined parameter Σ to guarantee the worst-case preciseness: [5x(z)
S1, ..., St,... SN.. where St y a,æ b, is the linear segment parameterized by (a,, b,)
S c for E [N].
By tuning c, various space-time preferences from users can be met. For example, a relatively large e result in small index size while having large prediction errors, and on the other hand, relatively small e provides users with small prediction errors while having more learned segments and thus large index size. Existing learned index methods implicitly assume that the whole dataset to be indexed contains the same characteristics for different localities and thus adopt the same e for all the learned segments. However. the scenario where there is varied local data distribution, is very common, leading to sub-optimal index performance of existing methods. For example, the real-world Weblog dataset used in our experiment has typically non-linear temporal patterns caused by online campus transactions such as class schedule arrangements, weekends and holidays. More importantly, the impact of on index performance is intrinsically linked to data characteristics, which are not fully explored and utilized by existing learned index methods.
Motivated by these, in this paper, we thcoretically analyze the impact of on index performance, and link the characteristics of data localities with the dynamic adjustments of e. Based on the
* "The first two authors contributed equally to this work. conrespnniing author. Work was done Alibaba.

---

derived theoretical results, we propose efficient and pluggable learned index framework that dynamically adjusts e in a principled way. To be specific, under the setting of an illustrative learned index method MET (Ferragina et al. 2020). bounds of each segment that link e with the mean and variance of data localities. The segment-wise prediction error embeds the space-time trade-off as it is the product of the number of covered keys and mean absolute error, which determine the index size and preciseness respectively. The derived mathematical relationships enable our framework fully explore diverse data localities with an c-learner module, which learns to predict the impact of on the index performance and adaptively choose a suitable e achieve a better space-time time trade-off.
present novel analyses about the prediction error
We apply the proposed framework to several SOTA learned index methods, and conduct a series of experiments on three widely adopted real-world datasets. Compared with the original learned index methods with fixed 6, our dynamic versions achieve significant index performance improvements with better space-time trade-offs.. We also conduct various experiments to verify the necessity and effectiveness of the proposed framework, and provide both ablation study and case study to understand how the proposed framework works. Our contributions can be summarized as follows:
We make the first step to exploit the potential of dynamically adjusting for learned indexes, and propose an efficient and pluggable framework that can be applied to broad class of piece-wise approximation algorithms.
We provide theoretical analysis for a proxy task modeling the index space-time trade-off, which establishes our e-learner based on the data characteristics and the derived bounds.
We achieve significant index performance improvements over several SOTA learned index methods on real-world datasets. To facilitate further studies, we make codes and datasets public at
Iee---nndee--iiiiiee Dysamic-Essilon.
2 BACKGROUND
Learned Index. Given a dataset D = ()), E X,y y), X' is the set of keys over a universe u such as reals or integers, and y is the set of positions where the keys and corresponding payloads are stored. The index such as B -tree (Abel 1984) aims to build a compact structure to support efficient query operations over DD. Typically, the keys are assumed to be sorted in ascending order to satisfy the key-position monotonicity, i.e., for any two keys, D4 > Z, iff their positions y; >> yj. such that the range query (X' n [Toow,
can be handled.
Recently, learned index methods (Kraska et al. 2018 et al. 2019 Tang et al. 2020, Dai et al. 2020 Crotty 2021) leverage ML models to mine useful distribution information from D, and incorporate such information to boost the index performance. To look up a given key x, the learned index first predicts position ý using the learned models, and subsequently finds the stored true position y based on ÿ with a binary search or exponential search. By modeling the data distribution information, learned indexes achieve faster query speed and much smaller storage cost than B -treeee index traditional, with different optimization aspects such as on e-bounded linear approximation (Galakatos et al.
2019 Ferragina& & Vinciguerra 2020b Kipf et al., 2020 Marcus et al., 2020 Li et al.) (022b) and et al. 2021a)
data-layout (Ding et al. 2020 Wu et al. 2021 Zhang & Gao 2022
Wu et al.
c-bounded Linear Approximation. Many existing learned index methods adopt piece-wiss linear segments to approximate the distribution of D due to their effectiveness and low computing cost, and introduce the parameter to provide worst-case preciseness guarantee and tunable knob to meet various space-time trade-off preferences. Here we briefly introduce the SOTA e-bounded learned index methods that are most closely our work, and refer readers to the literature (Ferragina & Vinciguerra 2020a Marcus et al.) 2020 Stoian et al. (202I) for details of other methods. We first describe an illustrative learned index algorithm MET (Ferragina al. 2020). Specifically, for any two consecutive keys of DD suppose their key interval (z; 11;11 is drawn according to a random process (G.), where G; is positive independent and identically distributed (i.idd) random variable whose mean is μ and variance is o². MET learns linear segments (S: y a,æ + b.) via a simple deterministic strategy: the current segment fixes the slope a; = 1/14, goes through the first available data point and thus b; is determined. Then S, covers the remaining data points one by one until data point (a', g/) gains the prediction error larger than e. The violation triggers a new linear segment that begins from (x', y²) and the process repeats until D has been traversed.
2

---

Other c-bounded learned index methods learn linear segments in similar manner to MET while having different mechanisms to determine the parameters of { such as FITing- Tree Galakatos et al. 2019). PGM (Ferragina & Vinciguerra 2020b) and Radix- Audix-Spline (Kipf et al. 2020). However, they both constrain all learned segments with the same 6. In this paper, we study how to enhance existing learned index methods from new perspective: dynamic adjustment of accounting for diversity of different data localities, and present new theoretical results about the effect of e. In Appx. we provide more detailed description and comparison existing learned index methods.
3 LEARN TO VARY E
3.1 PROBLEM FORMULATION AND MOTIVATION
Before introducing the proposed framework, first formulate the task of learning index from data with e guarantee, and provide some discussions about why we need to vary e. Given a dataset D be indexed and e-bounded learned index algorithm A, aim to learn linear segments S = [S..... S...., Sw] with segment-wise varied [e)] such that a better trade-off between storage cost (size KB) and query efficiency (time in ns) can be achieved than the ones using fixed Let D; C 'D be the data whose keys are covered by S, for the remaining data D \ J, Dj. the algorithm A repeatedly checks whether the prediction error of new data point violates the given e; and outputs the learned segment S,.. When all the e, for E [N] take the same value, the problem becomes the one that existing learned index methods are dealing with.
To facilitate theoretical analysis, we focus on two proxy quantities for the target space-time trade-off: (1) the number of learned segments N and (2) the mean absolute prediction error MA:(D,)S;), which affected and upper-bounded by 65. We note that the improvements of N-MAE trade-off fairly and adequately reflect the improvements of the space-time trade-off: (1) The learned segments size in bytes and N are positively correlated and only different by a constant factor, egg. the size of a segment can be 128bit if it consists of two double-precision float parameters (slope and intercept); in
(2) When using exponential search, the querying complexity is (log(N) + which the first term indicates the finding process of the specific segment S' that covers the key x for a queried data point (x, y). and the second term indicates the search range 1 - yl for true position based on the estimated one ý = 5'(x:). In this paper, adopt exponential search search algorithm since it is better than binary search for exploiting the predictive ability of learned models. In Appx. B we show that the search range of exponential search O (MAE(DD; S.)). which can be much smaller than the one of binary search, O(E;), especially for strong predictive models and the datasets having clear linearity. Similar empirical support can be also found from (Ding et al., 2020)).
Now let's examine how the parameter affects the N-MAE trade-off. We can see that these two performance terms compete with each other and plays an important role to balance them. If we adopt small the prediction error constraint is more frequently violated, leading to large N; meanwhile, the preciseness of learned index is improved, leading to a small MAE of the whole data MA). On the other hand, with a large we will get a more compact learned index (i.e., a small N) with larger prediction errors (i.e., a large (DS)..
Actually, the effect of on index performance is intrinsically linked to the characteristic of the data to be indexed. For real-world datasets, an important observation is that the linearity degree varies in different data localities. Recall that use piece-wise linear segments to fit the data, and e determines the partition and the fitness of the segments. By varying 6, we can adapt to the local variations of 'D and adjust the partition such that each learned segment fits the data better. Formally, let's 's consider the quantity SegErr, that is defined as the total prediction error within a segment S,, ie., Err; A (x,))eD; y - St(x)), which is also the product of the number of covered keys Len ((,)) and the mean absolute error MAE(D, (S.). Note that large Len(D;) leads to a small N since |D] Σn= Len(D.). From this view, the quantity SegErr; internally reflects the N-MAE trade-off. Later we will show how to leverage this quantity to dynamically adjust e.
3.2 OVERALL FRAMEWORK
In practice, it is intractable to directly solve the problem formulated in Section 3.1 With a given &, the one-pass algorithm A determines S, and D, until the error bound 6 is violated. In other words,
3

---

User
Expected
①
Learrner f(E
5 update
Data Points
SegErr
I. SegErr
Learned Segments
Maxiy 91
2 lookahead D', D',(K o')
reward SegErr, ().
predict 6
16-
[S Divi
D
① learn index A
Praltoon
A
E
(D, E(+1)
(D,6)
10 91
60
20
10
Key
Figure 1: The dynamic e framework. We ① transform into the proxy prediction error Ser, then 2 sample small look-ahead data D' to estimate the data characteristics (n. a). (3) The e-learner predicts suitable 6 accordingly, and 4 we learn a new segment S; using (e.g., PGM) with q 3 Once S; triggers the violation of e,, the e-learner is updated and enhanced with the rewarded ground-truth. Steps 2 to 5 repeat an online manner to approximate the distribution of D.
it is unknown what the data partition {D:} will be a priori, which makes it impossible to solve the problem by searching among all the possible {e:}s and learning index with set of given {e:}.
In this paper, we investigate how to efficiently find an approximate solution to this problem via the introduced e-learner module. Instead of heuristically adjusting e, the e-learer learns to predict the impact of e on the index structure and adaptively adjusts e in principled way. Mcanwhile, the introducing of e-learner should not sacrifice the efficiency of the original one-pass learned index algorithms, which is important for real-world practical applications.
These two design considerations establish our dynamic c framework as shown in Figure I The c-learner is based on an estimation function Seg [(, Js, a)) that depicts the mathematical relationships among e, Seg Err; and the characteristics μ4, a of the data be indexed. As start, users can provide an expected that indicates various preferences under space-sensitive or time-sensitive applications. To meet the user requirements, afterward, we internally transform the غ into another
proxy quantity SegErr, which reflects the expected prediction error for each segment if set ē. This transformation also links the adjustment of e and data characteristics together, which enables the data-dependent adjustment of e. Beginning with é, the e-learner chooses suitable e; according to current data characteristics, then learns a segment S; using A, and finally enhances the e-learner with the rewarded ground-truth Eeg,rr, of each segment. To make the introduced adjustment efficient, we propose to only sample a small Look-ahead data D' to estimate the characteristics (n, a)) of the following data locality. The learning process repeats and is also in an efficient one-pass manner. [
Note that the proposed framework provides users the same interface as the ones used by original learned index methods. That is, we do not add any additional cost to the users' experience, and users can smoothly and painlessly use our framework with given é éjust they use the original methods with given e. The is an intuitive, meaningful, easy-to-set and method-agnostic quantity for users. On the one hand, can casily impose restrictions the worst-case querying cases with the data accessing number in querying process O (log(1ū y))) On the other hand, is casier to estimate than the other quantities such index size and querying time, which dependent specific algorithms, data layouts, implementations and experimental platforms. Our pluggable framework retains the benefits of existing learned index methods, such as the aforementioned usability of e, and the ability to handle dynamic update case and hard size requirement.
We have seen how determines index performance and how SegErr; embeds the N-MAE trade-off in Section 3.1 In Section 3.3) we further theoretically analyze the relationship among e, SegErr, and data characteristics μl, o at different localities. Based on the analysis, we elaborate on the details of ellearner and the internal transformation between and SegErr, in Section 3.4
For better readability, we summarize the notations in Appx. We discuss how to extend existing works in more detail in Appx.
4

---

3.3 PREDICTION ERROR ESTIMATION
In this section, we theoretically study the impact of E on the prediction error Seg,rr; of each learned segment S₁. The derived closed-form form relationships will be taken into account in the design of the proposed e-learner module (Section 3.4). Specifically, for the MET algorithm, we can prove the following theorem to bound the expectation of Feg,rr; with e and the key interval distribution of DD
Theorem 1. Given datasel 'D to be indexed and where E 2,,, consider the setting of the MET algorithm (Ferragina et al. 2020), in which key intervals of D' are drawn from a random process consisting of positive i.i.d. random variables with mean P and variance o², and e ?> a/p. For learned segment St and its covered data Di, denote SegErt: -(aaweD 8 - --.()))) Then the expectation of SegErr, satisfies:
V 1 E[SegErri n
2 2 < 3V 3
Note that the average length of segments obtained by the MET algorithm is ( We now get a constant |/2 / ( x 0.78 that is tighter than the trivial one with I corresponding to the case where each data point reaches the largest enror e. This theorem reveals that the prediction error SegErr; depends on both e and the data characteristics (μ, o). Recall that CV=0/H μ is the coefficiens of variation, a classical statistical measure of the relative dispersion of data points. In the context of the linear approximation, the data statistic 1/C /CV = ju/a in our bounds intrinsically corresponds to the linearity degree of the data. With this, we can find that when ///or is large, the data is easy-to- with linear segments, and thus we can choose a small c to achieve precise predictions. On the other hand, when p/ar is small, it becomes harder to fit the data using a linear segment, and thus should be increased to absorb some non-linear data localities. In this way, we can make the total prediction error for different learned segments consistent and achieve better --MAE trade-off. This analysis also confirms the motivation of varying e: The local linearity degrees of the indexed data can be diverse, and we should adjust according to the local characteristic of the data, such that the learned index can fit and leverage the data distribution better. In the rest of this section, we provide a proof sketch of this theorem due to the space limitation. For detailed proof, please refer to our Appx. D
TRANSFORMED RANDOM WALK. The main idea is to model the learning process of linear approximation with guarantee as a random walk process, and consider that the absolute prediction error of each data point follows folded normal distributions. Specifically, given learned segment a, + b,, we can calculate the expectation of Seg for this segment as:
S ::1 y
(G--1) 1)
ErreyErry] = a.E
Σ
1
a,
E
Σ
Zz
Pr(j" = n),
(1)
where Z, is the j-th position of transformed random walk {Zybjen. j max N/- e/a. S
Zj S c/a;} } is the random variable indicating the maximal position when the random walk is within the strip of boundary + az and the last equality is due to the definition of expectation.
PROOF OF UPPER BOUND. Under the MET setting where a; = 1/1 and 6 >> a/n, we find that the increments of the transformed random walk {2 have zero mean and variance 0², and many steps are necessary to reach the random walk boundary. With the Central Limit Theorem, we assume
the Z, follows normal distribution with mean [zzj = 0 and variance 02, = jo and thus |Zy follows
the folded normal distribution with expectation (1) = /2/Tav/ Thus Eq. becomes:
E
Σ
| 1=
Pr(j = = <
E EIZZ = n) n=1
VJPrD = n).
m=15=0
2 nst
Using EDj"1
and V Varlj*|
a as derived in Ferragina et al. (022)) we get B[(**}]=
3 1
5 1
e. With the inequality ΣØ=o VJ < / n and E < (E[x)) $
we get the upper bound:
3 04
20 E((') 3/ π M
2 (B())))))
2/ v
2
2 5 3 (
E[SegErr.]
3 T
5

---

Applying the triangle inequality into Eq. R[SegErr:] > " " E [| Pr(j* ni), where Z مド=0 Zj.. and Z follows the normal distribution since 2, ~ N(0 o oz)) We can prove that |Z] follows the folded normal distribution whose expectation - > a(n - IT. Thus the lower bound is:
PROOF OF LOWER BOUND.
get
1 π
(n 1)Pr(j" = = 1 - ED - 11
= 2 A
B[SegErn]] >
Since E >> f. we can omit the right term VITT o/P and finish the proof. Although the derivations are based on the MET algorithm whose slope is the reciprocal of μ. we found that the mathematical forms among e, ju/a a and Sey Err; still applicable to other e-bounded methods, and further prove that the learned segment slopes of these methods are similar with bounded differences in Appx. F
3.4 e-LEARNER
Now given an e, we have obtained the closed-form bounds of the SegErr in Theorem D and both the upper and lower bounds are in the form of wi ( where 21,2.3 are some coefficients. As the concrete values of these coefficients can be different for different datasets and different methods, we propose to learn the following trainable estimator make the error prediction more precise:
SegErr = f(E,140) =w
w2
(2)
T S w1 s.t.v
2 2
S 3 3V
ISu522 2 5 W/ S 3.
With this learnable estimator, we feed data characteristic 11/0 of the look-ahead data and the trans-
formed ErgErr into it and find suitable c* as (SegErr/wa (M)) 1/ws We will discuss the
look-ahead data and the transformed SegErr in the following paragraphs. Now let's discuss the sons for how this adjustment can achieve better index performance. Actually, the c-learner proactively plans the allocations of the total prediction error indicated by the user (i.e., E- (D) and calculates the
tolerated Seg for the next segment. By adjusting current to e", the following learned segment can fully utilize the distribution information of the data and achieve better performance in terms of N-MAE trade-off. To be specific, when p//o is large, the local data has clear linearity, and thus we can adjust e to a relatively small value to gain precise predictions; although the number data points covered by this segment may decrease and then the number of total segments increases, such cost paid in terms of space is not larger than the benefit we gain in terms of precise predictions. Similarly, when u/o is small, should be adjusted to a relatively large value to lower the learning difficulty and absorb some non-linear data localities; in this case, we gain in terms of space while paying some costs in terms of prediction accuracy. The segment-wisc adjustment of improves the overall index performance by continually and data-dependently balancing the cost of space and preciseness.
Look-ahead Data. To make the training and inference of the e-learner leigh, we propose to look ahead few data D' to reflect the characteristics of the following data localities. Specifically, we leverage a small subset DD' c 'D \ Ujcr D, to estimate the value 11/a for the following data. In practice, we set the size of D'' to be 404 when learning the first segment as initialization, and j== (D)) p for the other following segments. Here is pre-defined parameter indicating the percentage that is relative to the average number of covered keys for learned segments, considering that the distribution of u/o can quite different to various datasets. As for the first segment, according to the literature (Kelley 2007). the sample size 404 can provide a 90% confidence interval for a coefficient of variance 0 o/p 0.2.
Erg and Optimization. As aforementioned. taking the user-expected input, we aim to reflect the impact of ē with transformed proxy quantity SegErr such that the e-learner can choose suitable e to meet users' preference while achieving better -MMAF trade-off. Specifically, we make the value of Err updatable, and update it to be SegErr wi (ā/ō) /"2 once new segment is learned, where A/ō is the mean value of all the processed data so far. This strategy enables us to promptly incorporate both the preference and the data distribution into the calculation of

---

SegErr. As for the optimization of the light-weight model, i.e., [t,, M4, 0) that contains only three learnable parameters 21...3, we adopt the projected gradient descent den Hertog & Roos (1991) with
the parameter constraints in Eq. 2 In this way, we only need to track a few statistics and learn the e estimator in an efficient one-pass manner. The overall algorithm is summarized in Appx.
4
EXPERIMENTS
4.1 EXPERIMENTAL SETTINGS
Baselines and Metrics We apply our framework to several SOTA learned index methods, including MET (Ferragina al. 2020), Fffing-Tree (Galakatos al. 2019). Radix-Spline, and PGM (Ferragina & Viinciguerra 2020b). For evaluation, we consider the index performance in terms of its learned segments N, size in bytes, prediction preciseness MAE, and the total querying time in ns. For a quantitative comparison w.r.t. the trade-off improvements, we calculate the Area Under the N-M AE Curve (AUNEC) where the x-axis and y-axis indicate N and MAE respectively. For AUNEC metric, the smaller, the better. More introduction and implementation details are in Appx. H
Datasets. We use several widely adopted datasets that are from real-world applications and differ in data scales and distributions (Kaaska et al.) 20188; Galakatos al. 2019 Ding al., [0200] Ferragina & Vinciguerra, 2020b; Li et al. 20216). including Weblogs and loT (timestamp keys), Map (location coordinate keys), and Lognormal (synthetic keys). More details and visualization are in Appx.
4.2 OVERALL INDEX PERFORMANCE
N-MAE Trade-off Improvements. In Table 1 we summarize AUNEC improvements in percentage brought by the proposed framework of all the baseline methods on all the datasets. We also illustrate the N-MAE trade-off curves for some cases in Figure 2 where the blue curves indicate results achieved by fixed E version while the red curves are for dynamic Other baselines and datasets yield similar curves, which we include in Appx. J.I due to the space limitation. These results show that the dynamic e versions of all the baseline methods achieve much better N-MAE trade-off 1-15.6%% to -22.61% % averaged improvements as smaller AUNEC indicates better performance), demonstrating the effectiveness and wide applicability of the proposed framework. As discussed in previous sections, datasets usually have diverse key distributions at different data localities, and the proposed framework can feta-dependently adjust to fully utilize the distribution information of data localities and thus achieve better index performance in terms of N -MMA trade-off. Here the Map dataset has significant non-linearity caused by spatial characteristies, and it is hard to fit using linear segments (all baseline methods learn linear segments), thus relatively small improvements are achieved.
Table 1: The AUNEC relative improvements for learned index methods with dynamic e.
Weblogs
loT
Map
Lognormal
Average
MET FTTing-Treh Tree
-25.87%
-7.66%
-7.63%
-21.48%
-15.66%
-31.18%
-25.56%
-4.94%
-28.24%
-22.48%
Radix-Spline PGM
-28.37%
-24.59%
-6.14%
-31.32%
-22.61 %
-22.42%
-25.01%
-7.18%
-6.52%
-15.28%
Lognormal Dataset
1oT Datuset
Weblogs Dataset
RadisSpline, Original
RadixSpline, Original
PGM, Original
RadixSpline, Dynamic
150
RadixSpline, Dysamic
16.
PCM. Dymamic
MAE
100
115
50
0-
10000
30000
30000
30000
40000
60000
1.00
200
100
N
Figure 2: The -MAAE trade-off curves for learned index methods.
Querying Time Improvements. Recall that the querying time of each data point is in (log(NN
log(ly- il) mentioned in Section 3.1 where N and [y ől are inversely impacted by e. To
7

---

Weblogs Dataset
1oT Datizet
2081)
PTtay-TTee Oriyinal
(.80)
e016
110ex Ster
2x2
Pffing Tree. Dynaric
Instee Stze (000
1,20
1.20
Fitlig Time Dysakk
1000
2-16
2:33
col28
5-32
(-61
700
503
1030
1100
3000
180
125
1700
100
1530
140
1800
200
Querying (00]
Querying Time (o))
Figure 3: Improvements in terms of querying times for learned index methods with dynamic e.
examine whether the performance improvements w.r.t. N-MAE trade-off (i.e., Table D can lead to better querying efficiency in real-world systems, we show the averaged total querying time per query and the actual learned index size in bytes for two scenarios in Figure 3 We also mark the 99th percentile (P99) latency as the right bar. We can observe that the dynamic versions indeed gain faster average querying speed, since we improve both the term N as well as the term l - ÿ via adaptive adjustment of Besides, better P99 results than the static version, due to the fact that our method effectively adjusts based on the expected and data characteristic, making the { fluctuated within a moderate range and leading to good robustness. A similar conclusion can be drawn from other baselines and datasets, and we present their results in Appx. D.I Another thing to note is that, this experiment also verifies the usability of our framework in which users can flexibly set the expected è to meet various space-time preferences just as they set in the original learned index methods.
find that the dynamic version achieves comparable even
Index Building Cost. Compared with the original learned index methods that adopt a fixed e, we introduce extra computation to dynamically adjust in the index building stage. Does this affect the efficiency of the original methods? Here we report the relative increments of building times in Table From it, we can observe that the proposed dynamic framework achieves comparable building times to all the original learned index methods on all the datasets, showing the efficiency of our framework since it retains the online learning manner with the same complexity as the original methods (both in O(D))). Note that we only need to pay this extra cost once, i.e., building the index once, and then the index structures can accelerate the frequent data querying operations for real-world applications.
Table Building time increments percentage for learned index methods with dynamic c.
Weblogs
IoT
Map
Lognormal
Average
MET
10.54%
5.14%
8.33%
5.26%
7.32%
FITing- Tree
10.70%
1.88%
5.35%
5.23%
5.79%
Radix Spline PGM
10.19%
1.64%
3.85%
8.96%
6.16%
16.76%
2.20%
1.28%
21.29%
10.38%
4.3 ABLATION STUDY OF DYNAMIC 6
To gain further insights into how the proposed dynamic framework works, we compare the proposed one with three dynamic e variants: (1) Random e is a vanilla version that randomly choose from [0, 22] when learning each new segment; (2) Polynomial Learner differs our framework with another polynomial function Erccrr(c) = 0 ct where 0₃ and 6g are trainable parameters; (3) Least Square Learner differs our framework with an optimal (but very costly) strategy learn f(c. p,, σ) with the least square regression.
Table 3: The AUNEC relative changes of dynamic e variants compared to the proposed framework.
Weblogs
loT
Map
Lognormal
Average
Random e
+70.94%
+68.19%
+53,29%
+73.38%
+66.45%
Polynomial Learner
+49.32%
+40.57%
+7.71%
+42.77%
+35.09%
Least Square Learner +4.44%
49.32%
+2.04%
-17.63%
-0.46%
We summarize the AUNEC changes in percentage compared to the proposed framework Table 3 Here we only report the results for FITing-Tres due to the space limitation and similar results can be observed for other methods. Recall that for AUNEC, the smaller, the better. From this table, we have the following observations: (1) The Random version achieves much worse results than the proposed dynamic framework, showing the necessity and effectiveness of learning the impact of e.
(2) The Polynomial Learner achieves better results than the Random version while still having
8

---

large performance gap compared to our proposed framework. This indicates the usefulness of the derived theoretical results that link the index performance, the e, and the data characteristics together. (3) For the Least Square Learner, we can see that it achieves similar AUNEC results compared with the proposed framework. However, it has higher computational complexity and pays the cost of much larger building times, e-g-, 14x and 53x longer building times loT and Map respectively. These results demonstrate the effectiiveness and efficiency of the proposed framework that adjusts based on the theoretical results, which will be validated next.
4.4 CASE STUDY
Fixed: N 7. Σ SugEEr, 46017
We visualize the partial learned segments for FITing- -TTeng-Tree with fixed and dynamic c on loT dataset in Figure where the N and
Learned Segreencs
34000
Original Date
32000-
SegEEr:; indicates the number of learned segments and the
32000
total prediction error for the shown segments respectively. The
31000
u/a indicates the characteristics of covered data {D,}. We can see that our dynamic framework helps the learned index gain both smaller space (7 v.s. 4) and smaller total prediction errors (48017 v.s. 29854), Note that es within e, are diverse due to the diverse linearity of different data localities: For the data whose positions are within about [30000, 30600] and [34700, 35000], the proposed framework chooses large es as their p/as are small, and by doing so, it achieves smaller N than the fixed version by absorbing these non-linear localities; For the data in the middle part, they have clear linearity with large p//ss, and thus the proposed framework adjusts as 19 and 10 that are smaller than 32 to achieve better precision. These experimental observations are consistent with our analysis in the paragraph under Eq. ( and clearly confirm that the proposed framework adaptively adjusts based on data characteristics.
30000
4909
5000 ScyEErr
500e
Dynamic
N
298G4
aiaco
Seguurnts
54500
52000
S1800
m/d 0.68.5788 0.31,
0900
8300
5000
41.85433-10"
Figure 4: Visualization of the learned index (partial) IoT for FlTing-Tree with fixed E = 32 and dynamic version (? 32).
4.5
MORE EXPERIMENTS IN APPENDIX
Due to the space limitation, we provide further experiments and analysis in Appendix, including:
More results about the overall index performance (Appx J.I and ablation studies (Appx J.2)
other datasets and methods, which support similar conclusions in Sec 4.2 and Sec (4.
The theoretical validation (Appx J.3) for Theorem I that SegErr, is within the derived bounds. and Theorem 2 that the learned slopes of various e-bounded methods have the same trends and both concentrate on 1/μ with a bounded difference. This shows that baselines have the same mathematical forms as we derived, and the proposed c-learner works well with wide applicability.
The insights about which kinds of datasets will benefit from our dynamic adjustment (Appx with the help of an indicative quantity, the coefficient of variation value (a/j).
CONCLUSIONS
Existing learned index methods introduce an important hyper-parametee to provide a worst-case preciseness guarantee and meet various space-time user preferences. In this paper, we provide formal analyses about the relationships among e, data local characteristics, and the introduced quantity Err for each learned segment, which is the product of the number of covered keys and MAE, and thus embeds the space-time trade-off. Based on the derived bounds. we present a pluggable dynamic framework that leverages an learner to data-dependently adjust and achieve better index performance in terms of space-time trade-off. series of experiments verify the effectiveness, efficiency, and usability of the proposed framework.
We believe that our work contributes a deeper understanding of how the e impacts the index perfor- mance, and enlightens the exploration of fine-grained trade-off adjustments by considering data local characteristics. Our study also opens several interesting future works. For example, we can apply the proposed framework to other problems in which the piece-wise approximation algorithms with fixed e are used while still requiring space-time trade-off, such as similarity search and lossy compression for time series data (Chen et al. 2007 Xie et al. 2014 Buragohain et al. 2007 O'Rourke 1981).

---

REFERENCES
David J Abel. A B+-tree structure for large quadtrees. Computer Vision, Graphics, and Image Processing, 27(1))19-31, 1984.
Timo Bingmann. Stx b+ tree.
http///00//txbbbteeeee// 2013.
Chiranjeeb Buragohain, Nisheeth Shrivastava, and Subhash Suri. Space efficient streaming algorithms for the maximum error histogram. In IEEE 23rd International Conference Data Engineering, pp. 1026-1035, 2007.
Qiuxia Chen, Lei Chen, Xiang Lian, Yunhao Liu, and Jeffrey Xu Yu. Indexable pla for efficient similarity search. In Proceedings of the 33rd international conference on Very large data bases, pp- 435-446, 2007.
Andrew Crotty. Hist-tree: Those who ignore it are doomed to learn. In 11th Conference on Innovative Data Systems Research, 2021.
Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea Arpaci- Dusseau, and Remzi Arpaci-Dusseane From wisckey bourbon: A learned index for log- structured merge trees. In 14th USENIX Symposium Operating Systems Design and Implementation, pp. 155-171, 2020.
Dick den Hertog and Cees Roos. A survey of search directions in interior point methods for linear programming. Mathematical Programming, 52(1):481-509, 1991.
Jialin Ding, Umar Farooq Minhas, Hantian Zhang, Yinan Li, Chi Wang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, and David B. Lomet. Alex: An updatable adaptive learned index. In Proceedings of the ACM SIGMOD International Conference Management of Data, pp. 969-984, 2020.
Paolo Ferragina and Giorgio Vinciguerra. Learned data structures. In Recent Trends in Learning From Data, pp. 5-1. 2020a. doi: (00077977--3000-4388877
Paolo Ferragina and Giorgio Vinciguerra. The PGM-Index: A fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment, 13(8): 162-1175. 2020b. ISSN 2150-8097.
Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. Why are learned indexes effective? In International Conference on Machine Learning, pp. 3123-3132, 2020.
Alex Galakatos, Andrew Crotty, Emanuel Zgraggen, Carsten Binnig, and Tim Kraska. Revisiting reuse for approximate query processing. volume 10, pp. 1142-1153, 2017.
Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. FiTing- Tree: A data-aware index structure. In Proceedings of the International Conference on Management of Data, pp. 1189-1206. 2019.
Goetz Graefe and Harumi Kuno, Modern b-tree techniques. In 27th International Conference on Data Engineering, pp. 1370-1373, 2011.
Ken Kelley. Sample size planning for the coefficient of variation from the accuracy in parameter estimation approach. Behavior Research Methods, 39(4):755-766, 2007.
Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. Learned cardinalities: Estimating correlated joins with deep learning. In 9th Biennial Conference on Innovative Data Systems Research, 2019.
Andreas Kipf, Ryan Marcus, Alexander van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, and Thomas Neumann. Radixspline: A single-pass leamnd index. In Proceedings of the Third International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, 2020.
10

---

Tim Kraska, Alex Beutel, Ed H. Chi, Jeftrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the International Conference on Management of Data, pp. 489-504, 2018.
Pengfei Li, Yu Hua, Jingnan Jia, and Pengfei Zuo. Finedex: fine-grained learned index scheme for scalable and concurrent memory systems. Proceedings of the VLDB Endowment, 15(2):321-334, 2021a.
Xin Li, Jingdong Li, and Xiaoling Wang. Asim: Adaptive single layer model for learned index. In International Conference on Databuse Systems for Advanced Applications, pp. 80-95. Springer, 2019.
Yaliang Li, Daoyuan Chen, Bolin Ding, Kai Zeng, and Jingren Zhou. pluggable learned index method via sampling and gap insertion. arXiv preprint arXiv:2101.00800; 2021b.
Chen Luo and Michael Carey, Lsm-based storage techniques: survey. The VLDB Journal, 29(1): 393-418, 2020.
Ryan Marcus, Andreas Kipf, Alexander Renen, Mihail Stoian, Sanchit Misra, Alfons Kemper, Thomas Neumann, and Tim Kraska. Benchmarking learned indexes. Proceedings of the VLDB Endowment, 14(1):1-13, 2020.
OpenStreetMap
Planet dump retrieved from https://plantt.osm.org https://www openstrretmap, org 2017.
contributors. contribbut
Joseph O'Rourke. An on line algorithm for fitting straight lines between data ranges. Communications of the ACM, 24(9):574 578, 1981.
Mark H Overmars. The design of dynamic data structures, volume 156. Springer Science & Business Media, 1987.
Patrick O' Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. The log-structured merge-tree (Ism-tree). Acta Informatica, 33(4):351-38) 1996.
Jun Rao and Kenneth A. Ross. Cache conscious indexing for decision-support in main memory. In Proceedings of the 25th International Conference on Very Large Data Bases, pp. 78-89, 1999.
Mihail Stoian, Andreas Kipf, Ryan Marcus, and Tim Kraska. Plex: Towards practical learned indexing, 08 2021.
Chuzhe Tang, Youyun Wang, Zhiyuan Dong, Gansen Hu, Zhaoguo Wang. Minjie Wang, and Haibo Chen. Xindex: scalable learned index for multicore data storage. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 308-320, 2020.
Kapil Vaidya, Eric Knorr, Michael Mitzenmacher, and Tim Kraska. Partitioned learned bloom filters. In International Conference on Learning Representations, 2021.
Jingdong Wang, Ting Zhang, jingkuan song, Nicu Sebe, and Heng Tao Shen. A survey on learning to hash. IEEE Transactions Pattern Analysis and Machine Intelligence, 40(4):769-790, 2018.
Jiacheng Wu, Yong Zhang, Shimin Chen, Yu Chen, Jin Wang, and Chunxiao Xing. Updatable learned index with precise positions. Proc. VLDB Endow., 1276:1276- 2021.
Shangyu Wu, Yufei Cui, Jinghuan Yu, Xuan Sun, Tei-Wei Kuo, and Chun Jason Xue. Níl: Robust learned index via distribution transformation. Proc. VLDDB Endow. 25(10):1188-200) sep 2022.
Qing Xie, Chaoyi Pang, Xiaofang Zhou, Xiangliang Zhang, and Ke Deng. Maximum error-bounded piecewise linear representation for online stream approximation. The VLDB journal, 23(6): 915-937, 2014.
Jiaoyi Zhang and Yihan Gao. CARMI: cache-ane aware learned index with a cost-based construction algorithm. Proc. VLDB Endow. 15(11):225 (S(11):2679228 2691, 2022.

---

Zhou Zhang, Peiquan Jin, Xiao-Liang Wang, Yan-Qi Lv, Shouhong Wan, and Xike Xie. COLIN: A cache-conscious dynamic learned index with high read/write performance. Comput. Sci. 3
2021.
Xuanhe Zhou, Chengliang Chai, Guoliang Li, and Ji Sun. Database meets artificial intelligence: A survey. IEEE Transactions on Knowledge and Data Engineering, 2020.
12

---

APPENDIX FOR THE PAPER: LEARNED INDEX WITH DYNAMIC
E
Our appendix includes the following content:
A further descriptions and comparison about the related c-based learned index meth- ods and data layout optimization-base based methods.
See B the details of the binary search and exponential search, and the connections between prediction error and these specific searching strategies.
Sec the notations adopted in this paper.
the discussion about how the proposed framework inherits the good abilities of existing learned index methods.
Sec
D
Sec
E
the full proof of Theorem
See F
the analysis about the learned slopes of other e-bounded methods.
See
G
the summarized algorithm of the proposed method.
See the implementation details of experiments.
See T
the detailed descriptions and visualization of the adopted datasets.
See J
more experimental results including the overall index performance and ablation
study on other datasets and methods (Sec [S.. and Sec and the theoretical validation (..c..3). Besides, we explore an indicative quantity (the CV value) to provide further insight into the rationale of the proposed framework J.4c
A MORE DETAILS ABOUT RELATED WORKS
A.1 G-BOUNDED LINEAR APPROXIMATION METHODS
Besides the MET method mentioned Sec 2 we give more introduction to the related e-bounded linear approximation methods. FITing-Tree Tree Galakatos et al. 2019) uses greedy shrinking cone algorithm. PGM (Ferragina & Vinciguerra 2020b) adopts another one-pass algorithm that achieves the optimal number of learned segments. Radix Sppine (Kipf et al. 2020) introduces radix structure to organize learned segments. Here we use a toy dataset to demonstrate the workflow of the e-bounded linear approximation methods. Suppose we study every segment with demonstrative method in an online manner, which simplified from MET and expresses the general idea of the class of the e-bounded linear approximation methods: When new data point comes over, connect with the starting point of the segment as the linear function of this segment, and check whether there is data point whose prediction error is greater than so, the learning of this segment terminated, and the current data point will serve as the starting point for a new segment. The first two subfigures in Figure 5 show the learning process of the first segment, and the data point which terminates the process is taken as the starting point of the second segment. Subsequent subfigures show the learning process for the following segments just as the first segment. Existing works are different in determining linear functions and termination conditions, but they all follow similar flow like this.
Mey
Ker
Figure 5: Workflow of e-hounded linear approximation method.
However, existing methods constrain all learned segments with the same All of these wisce-wise segments based approaches attempt to improve performance by changing the way segments are learned organized, but ignore the optimization potential of dynamically varying In this paper, we discuss the impact of e in more depth and investigate how to enhance existing learned index methods from perspective: dynamic adjustment of accounting for the diversity of different
13

---

data localities, as shown in mathematical derivation linking the indexing performance, and data statistics / o (Sec. (.3) and the proposed e-learner (Sec. 3.4.. Besides, different from (Ferragina et al. 2020) which reveals the relationship between and index size performance based on MET. In Sec 3.3 we give novel analyses about the impact of e on not only index size, but also index preciseness and a comprehensive trade-off quantity, which facilitates the proposed dynamic adjustment.
A.2 DATA-LAYOUT-OPTMMIAATTIT BASED METHODS
In this paper, mainly focus on the e-hased learned index methods. In recent years, some data- aayout-ottmnizttion based methods also gain promising indexing performance. For example, ALEX (Ding et al. 2020) improves Recursive Model Index (RMI) Kraska et al.. (2018) by reserving gaps within arrays to enhance the ability to update indexing case (insert, delete, update, etc..). LIPP (Wu al. 2021 proposes to extend the tree structure with zero prediction error for update operations and proposes an adjustment strategy to provide a bounded height of the tree index. NFL (Wu et al. 2022) proposes to transform the complex key distribution into a near-uniform distribution. CARMI cost model to improve the data partitioning of tree nodes in learned indexes. FINEdex (Li et al., (021a) focuses on concurrent and independent model processing with the help of a fattened data structure. These two performance optimization perspectives are relatively orthogonal. Both types learned index methods have their pros and cons:
(Zhang & Gao 2022) leverages an entropy-basee
Worst-case guarantee. For the e-bounded methods (Ferragina & Vinciguerra 2020b Stoian et al.) 2021; Galakatos et al., 2019 Ferragina et al., 2020; Kipf' et al. 2020). the most important advantage
they provide is the worst-case guarantee in each segment. This property is fairly valuable in many realistic indexing applications such as financial databases and on-device intelligence. Also note that our approach still maintains comparable 99th percentile (P99) performance compared to static e baselines shown in the overall index performance comparison (Figure 3and and Figure 10).
Index Size. Data-layout-basee based approaches such as ALEX (Ding et al. 2020) do achieve better indexing performance in dynamic scenarios, but pays larger index size overhead because of the introduced gap insertion technique (reserving empty space for possibly inserted data). Empirically, we examine the performance of ALEX with our experimental settings and find that it gains comparable query time and larger index size than the learned index with dynamic as the following Table shows. where the Qtsme and index size are in ns and KB respectively. We adopt the default hyper-parameters of ALEX and the is 4, 32, 64, and 32 in these four datasets respectively for RadixSpline.
We note that the index size is still very important even with a large amount of memory available today, shown by the fact that almost all related learned index works examine this metric in their experiments. It is worth noting that index size can have a significant impact on latency indirectly, since the smaller the index, the more it can fit into the hierarchical high-speed CPU caches, and thus increase the hit rates to speed up the overall indexing performance Zhang & Gao (2022); Zhhng et al. (202T). Moreover, in some practical applications, the available memory can be relatively small such as in cases where users need to build indexes from multiple keys of the data, and need to use the index on loT devices for edge computation.
Dynamic Hyper-parameter. Moreover, our novel framework can be regarded as an automatic method that determines hyper-parameters (c) according to the varied local properties of the data. Although the data layout optimization goes beyond our scope, our insight can also contribute the ALEX approach, since it also introduces syper--arameters in local linear segments learning, the lower and upper density limits on each gapped array: di, dy e (0, 1]. The authors empirically set them to be 0.6 and 0.8 respectively. However, different gapped arrays may gain better performance with different density limitations, since the data distribution can be varied across different localities, as we have shown in experiments.
B CONNECTING PREDICTION ERROR WITH SEARCHING STRATEGY
As mentioned in Section 3.1, we find the true position of the queried data point in ((oog[NV + log(lş [g y!)) where N is the number of learned segments and |ø yl is the absolute prediction error. A binary search exponential search finds the stored true position y based on ÿ. It is worth pointing
14

---

Table 4: The indexing performance comparison between ALEX and RadixSpline with the proposed
dynamic e framework.
Weblogs
loT
Map
Lognormal
Qtime
size
Qtome
size
Qtime
size
@time
size
ALEX SpdixS, Dynamic
713
1428
1632
582
1321
602
995
974
1275
428
373
937
1085
out that the searching cost in terms of searching range 1 yl of binary search strategy corresponds to the maximum absolute prediction error e, whereas the one of exponential search corresponds to the mean absolute prediction error (MAE). In this paper, decouple the quantity Seg as the Built upon the theoretical product of (D;) and MAE(D, in the derivation of Theorem |
analysis, we adopt exponential search in experiments to better leverage the predictive models.
To clarify, let's consider learned segment S; with its covered data D, Let 19 y& be the absolute prediction error of k-th data point covered by this segment, and e; be the maximum absolute prediction error of S,, i.e., lik yk I for all & E [len(D:)).
The binary search is conducted within the searching range [yk + e,] for each data point thus the mean search range Ten(D.) Ekm1 Llen(D)) 2e; = O(e,), which is independent of the preciseness the learned segment and an upper bound of MAE(DD
The exponential search first finds the searching range where the queried data may exist by cen- tering around the y. repeatedly doubling the range lú 29] where the integer @ grows from O, and comparing the queried data with the data points at positions ÿ + 29. After finding the specific range such that q satisfies 21og(n=)-1 < 1 ya! S 2[ToR(a=]] for the k-th data, binary search conducted find the exact location. In this way, the mean search range is [en > [og(s)))+1) (MMAE(D,|S.). which can be much smaller than O(e;), espe- cially for strong predictive models and the datasets having clear linearity.
C NOTATIONS
We summarize the adopted notations in Table 5 for convenience.
Table 5: The adopted Notations
Notation
Description
N
The total number of segments The i-th segment of learned index The whole data to be indexed The data covered by the i-th segment Expected given user SegErr:
S,
D
D;
The maximum prediction error of segment The sum of the errors for the data covered by the i-th segment
SegErr
Expected segment eтror calculated based on
D
Sampled data to reflect the characteristics of the following data localities.
p
The hyperparameter to determine the size of D)
A
Mean of data intervals in D'
Standard deviation of data intervals in D' The learnable function for determine Learnable parameters of the epsilon-learner (f)
f())
W1; W2, u/3
'The lower bound and upper bounds of searching ranges should be constricted to 0 and len(D:) respectively. For brevity, we omit the corner cases when comparing these two searching strategies they both need to handle the out-of-hounds scenario.
15

---

D INHERITING THE ABILITIES OF EXISTING WORKS
In this Section, we discuss the benefits of our proposed framework brought by its pluggable property with two example scenarios, the dynamic data update and hard limitation on user-required index size.
We note that the data insert operation has been discussed in the adopted baseline methods, FITing- Tree Galakatos et al. 2019) and PGM Ferragina& & Vineiguerra (2020b). More importantly, neither of these two methods altered the notion of when dealing with the data insertion, and they still relied on their e-bounded picce-wing wise segmentation algorithms.. The proposed framework is still valid when using their respective solutions to handle data insertion. Specifically, FITing- Tree proposes to introduce a buffer for each learned segment, which is used to store the inserted keys, and when the buffer is full, the data covered by the segment will be re-segmented (see Section 5 in Galakatos et al. (2017)) PGM adopts a logarithmic method O' et al. (999);; Overmars (1987) that maintains a series of sorted sets (Sa, S1, ..... S where 6 b= 0(log' [D 1), and builds multiple PGM-INDEX models over the sets. When a key x is inserted, a new PGM-INDEX will be built over the merged sets (see Section 3 in Ferragina& & Vinciguerra (2020b)). In general, these solutions proposed by existing methods for inserting keys are based on re- re-indexing for a piece of data along with the inserted data, and the re-indexing processes are the same as the original piece-wise linear segmentation processes but for different data, therefore, we can still apply the proposed dynamic-c framework for these methods in insertion scenarios just like we adjust c and learn index according to the new data to be re-indexed.
For the hard size limitation case, we observe that the existing work PGM introduced a multi criti-c variant that auto-tunes itself with pre-defined hard size requirements from users. Our proposed framework is pluggable and still valid when using the PGM variant to handle the size requirement. Specifically, given a space constraint, the multi-criteria PGM proposes to iteratively estimate the relationship between& and size with learnable function size(e) ae b, and automatically outputs the index that minimizes its query time via different estimated cs. Given a size requirement, we can just do the same thing in dynamic scene by setting our ? as estimated by the original PGM method.
We present discussions how the proposed framework can inherit the ability handle the update case of existing works above. To show how the learned index with dynamic e performs under different dynamic scenarios, as an example here, we simply replace the static parameter in the segment-building process of updatable PGM into a dynamic one predicted by the proposed learner and keep the update processing of PGM unchanged.
We follow the read-heavy and write-heavy workloads setting similar to ALEX Ding et al. (220)), where the workloads are composed of lookup operations and insert operations with different ratios. Specifically, after building learned indexes with a random subset of the whole dataset with the percentage Remit E (0, 100%), we repetitively perform Noookup random lookup opera- tions and insertion operation in a batch. To simulate different workloads, we set Rinit to be [5%, 10%, 20%, 40%, 60%, 80%] and Niookup to be [1, 2, 4, 1,1.
Esalion Tpc Slatk Easiler
Epeloon Swetc Epr ken dynori opolice
Epelion Sype Sont apc kn Dynomi moclee
440003
400003
420003
500033
500003
Thee-ppu
000093
300002
200093
3200003
21
20
10
72
80
10
20
40
20
60
70
Loodtup Mur Alter a Willi
1nl. Doto Katoo (96
101 Dats Radio (96
Figure 6: Total throughput (ops/sec) and index size (KB) results of the PGM with static and dynamic e on two different read-write workloads.
We repeat the experiments 3 times and summarize the total throughput (operations/sec) and index size (KB) in Figure Generally speaking, compared with the PGM with static we can observe that PGM with the é adjustment achieves larger total throughput and smaller sizes in most cases, indicating the effectiveness of the proposed method. We also find that with larger ratios of write (i.e., smaller Noookup) and smaller ratios of initial building data ( (Rowit), the throughput improvements are less and the variances are larger. Note that the current modification with e-learner mostly impacts
16

---

the index building stage, and we do not design specific strategies in the insert stage to achieve more precise estimation for the data's ' local characteristics, which is a promising future direction to further optimize the index performance in update case.
E PROOF OF THEOREM 1
Given learned segment S; a,æ b; denote e; the stored position of the last covered data for the (i - 1 segment (C1 = 0 for the first segment). We can write expectation SegErr; for the segment S; the following form:
Err,
Ja,X, - 1)
where j indicates the length of the segment, and X, indicates the j-th key covered by the segment S₁. As studied in Ferragina et al. (2020), the theear-approxmmatie be modeled as random walk processes. Specifically, X; = Xo + Eknn GR (for Z where G3 is the key increment variable whose mean and variance is μ. and o² respectively. Denote the Zj X, j/a, + (b, C. 1)/a, the j-th position of the transformed random walk {Z, JeN. and max(j [j E N - e/a; S Zj S e/a:) as the random variable indicating the maximal position when the random walk within the strip of boundary t tt/as. The expectation can rewritten as:
problem with guarantee can
G 11
1)
Ja:X, - j (h. 1)1
Z
1=0
J=0
(3)
d;
E
Zzl
Pr(j" =n).
n=l
===
The last equality Eq. (3) is due to the definition of expectation. Following the MET algorithm that the St goes through the point (Xo, Yo = c, + 1), we get b, = ao + cs + 1 and we can rewrite Zj as the following form:
Zo 0,
Z,
120 X, Xu - jj/a.- Σ
G2 j/a:
k=1
Σ GG - 1/a,) ) = (Wk),
km
where W. is the walk increment variable of Zj. E[W1] the MET algorithm setting where a; = 1/μ and > a μ., the transformed random walk {Z,} has increments with zero boundary. With the Central Limit Theorem, we can assume that Z, follows the normal distribution with mean Pay and variance o² zg and thus |2y1 follows the folded normal distribution:
= 1/a, and Var o2. Under
and variance 0², and many steps are necessary reach the random walk
Z, ~ Nop - 1/ai)i.jo").
B(ZZ)) 12j - 2 May/ (uz//2z)) os / 2/ 2xp(-122/222
where d is the normal cumulative distribution function. For the MET algorithm, a; 1/μ and thus the Maj = 0, ..j = o /j. and [[ Z(( /2/To vj. Then the Eq. 3 can be written as
n-1
P
Σ
1 =)
n=1
(4)
2
VjPr(j"= =
π
1-0
17

---

For the inner sum term in Eq. 4., have (Ei= vJ) < f since
2 nnv vi < ( va dx =
Σ
Vi+
2
j=0
then the result in Eq. 44 becomes
2 2
Errel
nVTPr(jj =
T
2 2
2 -
-V T
2 [10)3)]]]
3V TM
3 V 2 (B67))*
42
where the last inequality holds due to the Jensen inequality E[x s (E[X))² 2 Using [Bj"1
0²
and Varlj* 2 u
5 1r²
3 04 ea derived in MET algorithm Ferragina et al. 2020), we get [(("*)
3 3 4
which yields the following upper bound:
2
5
Errg
3
π
For the lower bound, applying the triangle inequality into the Eq.
33
we have
E
Pr(j" = n)
1
--1
E
Pr(j" n))
(5)
mm
3=0
Pr(j"" =)),
where z= Σ5= Zz.. Since 2j N(O, 02) the 7 follows the normal distribution:
n-1
~~~ N uz 0, 0f o Σ
j=0 k=ū
where ryk is the correlation between Z, and Z5. Since μzz = 0, the |7| follows the folded normal distribution with E[|Z]] = oz 22/TT. /r. Since the random walk {Z, } is process with i.i.d. increments,
the correlation ryk 2 O. With T.j = o > 0 and ryk 2 O, we have
an
E |
Σ
Vnn 1)/x
VT
1=
and the result in Eq. becomes:
n-1 1
E(SegErri]
7
Pr(j* = n)
n=1
j=0
(n
Pr(j" =n)
11
π
T 1
v L
p2
ED
#
Since e >> 3. we can omit the right term v
Ie and finish the proof.
18

---

F LEARNED SLOPES OF OTHER E- C-BOUNDED METHODS
As shown Theorem I we have known how c impacts the SegErr; of each segment learned by the MET algorithm, where the theoretical derivations largely rely on the slope condition a, 1/p Here we prove that for other e-bounded methods, the learned slope of each segment (i.e. 0; of S:) concentrates on the reciprocal of the expected key interval as shown in the following Theorem.
Theorem 2. Given an ž and an c-bounded learned index algorithm A. For a linear segment S, a, + b, learned by A, denote its covered data and the number of covered keys D; and (D, respectively. Assuming the expected key interval of Dj pú, the learned slope as concentrates on 1/P; with bounded relative difference:
2c
2c
E (en) )
E[a:] & (11+
Len))(D.) )ā.
Proof. For the learned linear segment S, denote its first predicted position and last predicted position
-/h Notice that e S vó N + e and
as 1/ and y/2 respectively, we have its slope a;
Yn - S vn < Yn, + due to the e guarantee, we have Yn yo 2E S Vn, v/ S yr, + 2e and the expectation of ag can be written
Un 90 + 2E
16 In
3/
yo 2c
E
S
Ela,
<
E
Zn
20
20
Zp Io
Note that for any Iearned segment S. whose first covered data is (zo, yo) and last covered data is μ4 and thus the inequalities become
(Ens Vnd, we have EE
En [n= Un -9
2E
1
2c
E
I
ETa,]
+
In
10
1
T0
Since à 1/p; and B[z, zol (B[Len(D.)) 1)p4 we finish the proof.
The Theorem 2 shows that the relative deviations between learned slope a, and are within 2e/ (E[LLEL - 1). For the MET and PGM learned index methods, we have the following corollary that depicts more precise deviations without the expectation term E[Len(D:)].
Corollary 2.1. For the MET method Ferragina et al. 2020) and the optimal e-bounded linear approximation method that learns the largest segment length used in PGM Ferragina & Vinciguerra 2020b)) the slope relative differences are at O(1/e).
Proof. We note that the segment length of a learned segment is at O(e)) for the MET algorithm, which is proved the Theorem of Ferragina et al. (2020). Since PGM achieves the largest learned segment length that is larger than the one of the MET algorithm, we finish the proof.
G THE ALGORITHM OF DYNAMIC ADJUSTMENT
We summarize the proposed algorithm below. In Section 3.4 we provide detailed descriptions of the initialization and adjustment sub-procedures. The lookahead() and optimize() are in the "Look-ahead Data" and "SegErr and Optimization" paragraph respectively.
H IMPLEMENTATION DETAILS
Baselines. All the experiments are conducted on Linux server with an Intel Xeon Platinum 8163 2.50GHz CPU. We first introduce more details and the implementation of baseline learned index methods. MET (Ferragina et al. 2020) fixes the segment slope as the reciprocal of the expected key interval, and goes through the first available data point for each segment. FlTing-Tree (Galakatos) jet al. 2019) adopts a greedy shrinking cone algorithm and the learned segments are organized with B -tree. Here filling factors of inner nodes and leaf nodes as 100%, i.e., we adopt the pull-p filling manner. Radix-Spling (Kipf al. 2020) adopts greedy spline interpolating algorithm learn spline points,
the stx::btree (v0.9) implementation (Bingmann) 2013) and set the
19

---

Algorithm Dynamic Adjustment with Pluggable Learner
Input: D: Data be indexed, A: Learned index algorithm, é: Expected e, pi Length percentage for look-ahead data
Output: S: Learned segments with varied
I: initial parameters 21.3 of the learned function: f(c, μl, o) w1("" (1) "
2: initial mean length of learned segments so far: Len(Ds) <- 404
3: S <- Ø, (A/ō)= +
4: repeat
5: Get data statistic:
6:
(μ/o) - Lookahead(D, (en()))) p)
7:
Adjust based on the learner:
e" + (nnErr/wii())) 1/we
8:
9:
Learn new segment S; using adjusted c*:
10:
[S D
A(D,c")
11:
SUS
12:
D DiD, Ds +- 12+5sUU2 UDD
13:
Online update Len(Ds):
14:
(en(Ds) < running- meng (rean(Len/ie (Ds))Ds)...))))) LDn(
15:
(a/0) < runming-ment meng (A/ (ā/ (n/o))
16:
Train the learner with ground truth:
17:
W1,2,3 +- oplimize(J Si, Seg))
18:
Eeg < w1 (A/0) a
19:
until D= 0
and the learned spline segments are organized with flat radix table. We set the number radix bits as r 16 for the Radix-Spling method, which means that the leveraged radix table contains 2 entries. PGM (Ferragina & Vinciguerra, (220b) adopts a convex hull based algorithm to achieve the minimum number of learned segments, and the segments can be organized with the help of binary search, CSS-Tree (Rao & Ross 1999) and recursive structure. Here we implement the recursive version since it beats the other two variants in terms of indexing performance. For all the baselines and our method, we adopt exponential search to better leverage the predictive models since the query complexity using exponential search corresponds the preciseness of models (MAE) we analyzed in Appendix B
Evaluation Metrics. We evaluate the index performance in terms of its size, prediction preciseness, and total querying time. Specifically, we report the number of learned segments N, the index size in bytes, the MAE as D (a.y)e d ly S(x)), and the total querying time per query in (i.e., perform querying operations for all the indexed data, record the total time of getting the payloads given the keys, and report the time that is averaged over all the queries). For quantitative comparison w.r.t the trade-off improvements, we calculate the Area Under the N-M AE Curve (AUNEC) where the x-axis and y-axis indicate N and MAE respectively. For the AUNEC metric, the smaller, the better.
ppperr-prramters.. We describe a few additional details of the proposed framework in terms of the c-learner initialization and the hyper-parameter setting. For the W1,233 of the e-learner shown in the Eq. 2). We empirically found that this light-weight initialization leads to better index performance compared to the versions with random parameter initialization, and it benefits the exploration of diverse i.e., leading to the larger variance of the dynamic sequence [EI...., ......, , Ex). As for the hyper-parameter p (described in the Section 3.4p. we conduct a grid search over p E [0.1, 0.4, 0.7, 1.0] on Map and loT datasets. We found that all the ps achieve better N --MAE trade-off (i.e., smaller AUNEC results) than the fixed versions. Since the setting p = 0.4 achieves averagely best results on the two datasets, set be 0.4 for the other datasets.
20

---

I DATASET DETAILS
Our framework is verified on several widely adopted datasets having different data scales and distributions. Weblogs Kraska et al. (2018); Galakatos et al. (2019); Ferragina & Vinciguerra (2020b) contains about 715M log entries for the requests to university web server and the keys are log timestamps. loT Galakatos et al. [ & Vinciguerra (2020b) contains about 26M event entries from different IoT sensors in building and the keys are recording timestamps. Map dataset Kraska et al. (2018); Galakatos et al. (201)); Ding et al.] (2020); Ferragina & Vinciguerral (2020b): Li al. (2021b) contains location coordinates of 200M places that collected around the world from the Open Street Map OpenStreetMap contributors (017)) and the keys are the longitudes these places. Lognormal |eeraggiaa & Vinciguerra (2020b)
synthetic dataset whose key intervals follow the lognormal distribution: (n( ~ ~N (Hig. (g). To simulate the varied data characteristics among different localities. We generate 20M keys with 40 partitions by setting Mig and setting dig with
a random number within [0.1, 1] for each partition.
We normalize the positions of stored data into the range [0, 1). and thus the key-position distribution can be modeled as Cumulative Distribution Function (CDF), We plot the CDFs and zoomed-in in CDFs of experimental datasets in Figure 7 and Figure ( respectively, which intuitively illustrate the diversity of the adopted datasets. For example, the CDF visualization of the Map dataset shows that it has a fairly shifted distribution across different data localities, verifying of the necessity of dynamically adapting and adjusting the learned index algorithms just as we considered in this paper.
Widlegs
Map
Loguerma
04
Bey
vie
Jurr
305
+37
Figure 7: CDFs of adopted datasets.
Zacenedile in Woldinss
Zoomne IoT
Zoomed in Map
Zoomed- Lognormal
1.800
1,383
4.00
1465
1.52
0.50
14.
TURES
5.455
acto +1289x112
Kry
=10
Krr
Key
X38
Figure 8: Zoomed-in CDFs of adopted datasets.
J ADDITIONAL EXPERIMENTAL RESULTS
J.1 OVERALL INDEX PERFORMANCE.
For the N-MAE trade-off improvements and the actual querying efficiency improvements brought by the proposed framework, we illustrate more N-MAE trade-off curves in Figure 9 and querying time results in Figure I0 We also mark the 99th percentile (P99) latency as the right bar, which is useful metric in industril-scall practical systems. Recall that the -MMAE trade-off curve adequately reflects the index size and querying time: (1) the segment size in bytes and N are only different by constant factor, e.g., the size of segment can be 128bit if it consists of two double-precision float parameters (slope and intercept); (2) the querying operation can be done in (log + log(Iy - øl) as we mentioned in Section 3.1 thus better -MAAE trade-off indicates better querying efficiency. From these figures, we can see that the dynamic e versions of all the baseline methods achieve better N-MAE trade-off and better querying efficiency. verifying the effectiveness and the wide applicability of the proposed framework. Regards the p99 metrics, we can see that the dynamic version achieves comparable even better P99 results than the static version, showing that the proposed method not
21

---

Weblogs Dataset
1oT Dataset
Map Dataset
Tree, Origina
FiTing Tree, Original
125
PTTing/Tre Original
TrT,ng-Tro,, Dynamic
Prenng-Tres Dynamics
Filtin Tree, Dynomie
MAR
MAR
76
MAR
76
30
50
25
200
600
600
1000
20000
60000
60000
20000
40000
noonn
100000
Lognormad Dataset
Weblogs Dataset
Map Dataset
FiTtng Tree, Original
15
RadinSpliee, Original
200
RodixSplion Original
80
FTTing Dreo, Dynande
Radiddiime,, Dynamic
150
RadixSplino, Dymsakk
MAR
MAE
200
40
50
0
20000
400000
on000
Ronno
ToTT Dataset
Map Dataset
Lognormal Dataset
1.50
Original
Original
PCM
PGM, Dynamic
PGM. Dynamok
PGM, Dynamic e
MAB
100
bAAE
MAE
50000
2000
4000
5000
Weblogs Dataset
Map Dataset
Lognormal Dataset
4212
Dynamic
100
Dynamic
Original
Dynamic
Original
7.5
MAE
MAB
75
5.0
128
50
2.8
4-22
0.0
10in0o
20100
Figure 9: The additional N-MAE trade-off curves for learned index methods.
only improves the average lookup time, but also has good robustness. This is because our method can effectively adjust based the expected and data characteristic, making the {er} fluctuated within a moderate range.
J.2 ABLATION STUDY
To examine the necessity and the effectiveness of the proposed framework, in Section compare the proposed framework with three dynamic variants for the FITing-Tree method. Here we demonstrate the AUNEC relative changes for the Radix-Spline method with the same three variants in Table and similar conclusions can be drawn.
4.3 we
Table 6: The AUNEC relative changes of dynamic e variants compared to the Radix-Spline method with the proposed framework.
Polynomial Learner
Least Square Learner
Random
Weblogs loT Map Lognormal
+81.23%
+56.20%
-9.56%
+74.78%
+53.28%
+9.81%
+60.67%
+7.34%
+0.45%
+83.16%
+55.01%
-11.23%
Average
+74.96%
+42.96%
-2.63%
22

---

Weblogs Dulaset
1oT Datnset
Inder (801)
154
Orginsl
1,500
1,700
P:16
MET. Dycanie
MET. Origied
1.300
1,30
C-32
990
x
2:8
E254
C-16
24
(-256
cu256
1000
1100
7:00
1620
1500
1000
1000
2000
Querying Time (nc)
Query lng (nd)
1930
Map Dataset
Logsonsel Distaset
1900
4:15
MINT Original
6-16
Sue- 103-033
MET, Dysanic
101
MET, Dynarics
690
1833
6-53
c-61
Toles
6-32
28
en256
Caass ea256
Querying
Qserying Time(ta)
Weblings Dataset
3,300
1,000
M- Boiis Splin: Ougital
1,500
o-16
Hadis Splinc, Original
Indes Sheee 0635
1.01
Spline. Dynasi
Sire
3,300
1,300
6-16
Rplie, Dysasic
1,00
1,300
(e0
(954
500
Querying Time
Userying
Map Dataset
Lognormal Dataset
300
6-15
Splis-Spine,
c-1c
Radis Spiies Origial
(811
100
Radte Spiin, Dytamic
Iude Sooo (43)
1,40
Spliee, Dynani
90
1,40
120
2-64
e-128
1,40
o-22
100
6-02
25256
400
010
430
43
410
190
400
450
90
300
300
500
1920 1100
1200
1900
1400
1500
1000 2010
Querying Time (nd)
Quirying (hs)
Weblogs Dataset
2010
[oT Dataset
0K30
0-16
PGM. Dynanicc
PGM, Original
Inder Steee (N11)
A4g
680
(-16
c-16
PEM, Cheprra
642
6-32 AMM
P-32
cud4
2-1
140
2-64
2-128
28
e-055
950
3090
1900
Querying (ns)
Map
Lognommal Dataset
1000
2015
Inder (K01)
900
PCM, Original Dysamic
Index Sioe (KD)
301
/-16
POM, Origial
POM, Dysasic
300
2
500
CH32
300
6e64
1-128
5n32
2-128
10-128
1000
10900
1100
11:00
1000
1000
1200
1500
1020
1930
Querying Timeens)
Querying Time (ns)
Figure 10: Improvements in terms of querying times for learned index methods with dynamic e.
J.3 THEORETICAL RESULTS VALIDATION
We study the impact of e on Seg for the MET algorithm in Theorem I where the derivations are based on the setting of the slope condition 1/μu. To confirm that the proposed framework also works well with other e-bounded learned index methods, we analyze the learned slopes of other e-bounded methods in Theorem 2 In summary, we prove that for segment S; covered data is D; and the expected key interval of Dj is μ4, then a, concentrates on 1/H4 within 2 [E[ D:)] 1) relative deviations. Here we plot the learned slopes of baseline learned index methods in Figure [ (Map dataset) and in Figure [3 (IoT, Weblogs and Lognormal datasets). We see that the learned slopes of other methods indeed center along the line a; = 1/p4, showing the
a,æ + b, whose
23

---

IoTI Dataset
46
Lognormal / 1 0.5
40
Lognorinal /
Fifting RedicSpliae
Loow Boad
Boaad
Long Seetfee
30-
PGM
8
15-
0.6 4/p.
400
Figure 11: Learned slopes.
Figure 12: Illustration of the derived bounds.
close connections among these methods and confirming that the proposed framework can work well with other e-bounded learned index methods.
We further compare the theoretical bounds with the actual Seg for all the adopted learned index methods. We show the results on the Lognormal dataset in Figure [2] and the results on another two datasets Gammaa and Uniform in Figure 14 where the key intervals of the latter two datasets follow gamma distribution and uniform distribution respectively. As expected, we can see that the MET method has the actual Seg Err; within the derived bounds, verifying the correctness of the Theorem d Besides, the other e-bounded methods show the same trends with the MET method, providing evidence that these methods have the same mathematical forms derived, and thus the e-learner also works well with them.
X18
Map Dataset
Weblogs Dataset
Lognormal Dataset
VITing Thee RodixSpline PGM
3/p,
1.00
FITing- Tive
n. 1/ft
8. L/a. Fifing Haticcipitoo
Hathhiipiiee
PGM
PGM
0.25
0.55
0.00
0.95
1.00
0.35
0:30
0-35
1/
1/pL
1/p4
Figure 13: Learned slopes on the loT, Weblogs and Lognormal datasets.
3.0,
Cheer Boea
PON
NET
PGM
SET
Daaed
PGM
35
20
30
Long (uggee))
Lox (SooeEr))
10x
100
200
300
100
100
200
300
400
1000
900
360
400
Uniform, Lowe O.D. high
1.0
Uniforan, low = 0.O, high = 10.0
Lilffrm, Lown 10.0, high
100,D
40
IngiSeeftrr
Logi
Log
10
400
Figure 14: Illustrations of the derived bounds on Gamma and Uniform datasets.
24

---

J.4 CV AS AN INDICATIVE QUANTITY
The coefficient of variation (CV) value, i.e., CV=o/p. plays an important factor in our bounds to reflect the linearity degree of the data. We have that CV effective help dynamically adjust in our framework as shown in our experiments. Here we explore that whether the CV value can be an indicative quantity to shed light on what rypes of data will benefit from our dynamic adjustment. To be specific, we calculate the CV values of the experimental datasets and compare them with the trade-off improvements.
The global CV values of IoT, Map, Lognormal, and Weblogs are 65.24, 11.12, 0.85, and 0.013 respectively, while their AUNEC improved by 20.71%, 6.47%, 21.89% and 26.96% respectively. With the exception of IoT, the rest of the results show that the smaller the CV value is, the greater the trade-off improvement of dynamic e brings. We find that IoT a locally linear but globally fluctuant dataset. We then divide the data into 5000 segments and calculate their average CV values. The local CV values IoT, Map, Lognormal, and Weblogs are 0.95, 2.18, 0.63, and 0.005 respectively, which consistent with the improvement trends. Intuitively, when the local CV value is small, the local data hard-to-fit fit with a few linear segments if we adopt an improper c, and we need more fine-graines adjustment rather than the fixed setting. Thus this case. The calculation of actual CV values of real-worke datasets helps to validate our analysis based the CV values, and provides further insight into the scenarios where the proposed method has strong potential to outperform existing methods.
expect more performance improvements in
25


Reviews:
[{"review_id": "irmFKCazgP5", "reviewer": "Reviewer_apVD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper solves the problem that existing learned index methods adopt a fixed ε for all the learned segments, which neglecting the diverse characteristics of different data localities and propose a mathematically-grounded learned index framework with dynamic ε, which is efficient and pluggable to existing learned index methods. ", "summary_of_the_review": "This paper addresses an existing problem, but the solution is not innovative enough and does not perform much better.", "strength_and_weaknesses": "Strength\n1. A large number of formulas are derived in this paper, which provide theoretical basis for the proposed method.\n2. The comparative experiments in this paper are very rich, and several basic metrics of learned index are measured.\n3. Whether the method proposed in this paper is universal, that is, it performs well under any data distribution.\n\nWeaknesses\n1. This paper uses a large number of mathematical symbols and formulas, it is recommended to use a table to summarize for the convenience of readers.\n2. It is recommended to use examples in complex part, such as the flow of the entire framework.\n3. This paper addresses an existing problem, and it suggests implement other methods based on dynamic ε in experience.\n4. This paper has carried out several groups of comparative experiments, but the experimental results are not outstanding.\n5. There are some grammatical errors such as no subject.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RZZw50ZDrg", "reviewer": "Reviewer_QKCD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Recent learned indexes leverage the machine learning models to replace the traditional index structures to achieve a superior performance. However, existing learned indexes adopt a fixed prediction error threshold to build the index. This paper focus on the diverse characteristics of different data localities and propose a pluggable learned index framework to dynamically adjust the prediction error threshold. The experiments shows the proposed methods can achieve a better trade-off between space and time effiency.", "summary_of_the_review": "The paper proposes useful method for adaptive epsilon for learned index. The update is an important consideration for database. Before seeing more evaluations and comparisons, I would recommend a borderline score.", "strength_and_weaknesses": "Strength\n1. The paper present the comprehensive theoretical analysis and corresponding proofs.\n2. The proposed methods are easy to applied to all piece-wise-approximation-based learned index.\n\nWeakness:\n1. It would be clearer for readers to understand the learned index when discuss about the related work on the learned index from different optimization aspect, such as epsilon-bounded mechanism, index structure. New works should be also discussed here, such as LIPP [1] NFL [2], CARMI [3], FINEdex [4].\n\n2. The paper claims that the proposed framework has the ability to handle dynamic udpate case (Section 3.2) and the cost of the estimation for the epsilon is only paied once (Section 4.2 Indexing Building Cost). However, the experiments in the Section 4 or Appendix only includes the results on read-only workloads. The results on read-write workloads are missing. The update issues in indexing are complicated and includes several aspects of research directions. For example, to support updates, existing indexes such as LIPP [1], Alex, PGM often propose new operations to adjust the inner structure which may involve rebuilding parts of the structure. From this perspective, does the previous epsilons still fits? Or does the index need to pay the estimation cost again?\n\n3. The codes are incomplete and are all python codes. All existing learned index are implemented in C++ for obtaining the faster performance. The codes for implementing the framework or measuring the index's performance (latency or index size) are missing.\n\n[1] Jiacheng Wu, Yong Zhang, Shimin Chen, Yu Chen, Jin Wang, Chunxiao Xing. Updatable Learned Index with Precise Positions. Proc. VLDB Endow. 14(8): 1276-1288 (2021)\n[2] Shangyu Wu, Yufei Cui, Jinghuan Yu, Xuan Sun, Tei-Wei Kuo, Chun Jason Xue. NFL: Robust Learned Index via Distribution Transformation. Proc. VLDB Endow. 15(10): 2188-2200 (2022)\n[3] Jiaoyi Zhang, Yihan Gao. CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm. Proc. VLDB Endow. 15(11): 2679-2691 (2022)\n[4] Pengfei Li, Yu Hua, Jingnan Jia, Pengfei Zuo. FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems. Proc. VLDB Endow. 15(2): 321-334 (2021)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LpZGKfFNX1", "reviewer": "Reviewer_WrZf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the learned index problem and proposes a new approach. Unlike the previous approaches that fix the prediction error guarantee $\\epsilon$, the proposed approach dynamically adjusts the $\\\\epsilon$.  The paper also gives the corresponding theoretical analysis. Experiments also demonstrate the advantage of the proposed algorithm.", "summary_of_the_review": "Overall I think it is an interesting paper. However, I feel like the presentation of the paper can be further improved. I am not very familiar with the literature on the learned indexing problem and I am open to hearing feedback from other reviewers. ", "strength_and_weaknesses": "Strength\n\n1. The paper gives a deep understanding of the learned index problem and first uses a dynamic $\\epsilon$, which is interesting to me.\n2. The experimental result shows the advantage of the proposed algorithm.\n\nWeaknesses\n\n1. It is unclear to me why the theory results in this paper show that the dynamic $\\epsilon$ can be better than the previous results. Can the author explain that?\n2. I am not very familiar with the literature on leaned indexing, and I feel that the discussion of the literature is a little hard for me to follow. Maybe the authors can add more explanation in the next version. Also, the authors give some detailed explanations in the appendix, however, some of them seem not to be referred in the main content.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster