Learned Index with Dynamic $\epsilon$
Authors: Daoyuan Chen
Wuchao Li
Yaliang Li
Bolin Ding
Kai Zeng
Defu Lian
Jingren Zhou
Venue: ICLR 2022 Submitted (2022)
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.

Under review as a conference paper at ICLR 2022
LEARNED INDEX WITH DYNAMIC
Anonymous authors
Paper under double-blind review
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 eπror is no more than a pre-defined e. However, existing learned index methods adopt a fixed e for all the learned segments, neglecting the diverse characteristics of different data localities. In this paper, we propose mathematically gygouuudd learned index framework with dynamic E, which is efficient and pluggable to existing learned index methods. We theoretically analyze prediction error bounds that link e with data characteristics for an illustrative learned index method. Under the guidance of the derived bounds, we learn how to vary e and improve the index performance with a better space-time time trade-off. Experiments with real-world datasets and several state-of- of-the--rt methods demonstrate the efficiency, effectiveness and usability of the proposed framework.
INTRODUCTION
Data indexing (Graeee& & Kuno 201 Wang al. 2018 Luo & Carcy] 2020 Zhou 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 (Kipf et al.) 2019 Ferragina & Vinciguerra) 2020a Mitzenmacher 2018 Vaidya et al.) (02T). The key insight behind this trending topic of "learned index" is that the data to be indeeed contain useful distribution information and such information can be utilized by trainable MI. models that map the keys to their stored positions. State-of toite--of-hh-aatt learned index methods (Galakatos et al.) 2019 Kipf al., 2020 Ferragina Vinciguerra, 2020b] |erragina et al. 2020) adopt piece-wise linear segments to approximate the data distribution and introduce an important pre-defined parameter e. These methods ensure that the maximal prediction error of each learned segment is no more than and provide a worst-case guarantee of querying efficiency.
By tuning e, various space-time preferences from users can be met. For example, a relatively large can result in small index size while having large prediction emrors, and on the other hand, relatively small e provides with small prediction eтrors while having more learned segments and thus a large index size. However, 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 for all the learned segments, leading to sub-optimal index performance. 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 theoretically analyze the impact of on index performance, and link the characteristics of data localities with the dynamic adjustments of Based on the derived theoretical results, we propose an efficient and pluggable learned index framework that dynamically adjusts in a principled way. To be specific, under the setting of an illustrative learned index method MET (Ferragina et al.] (020)), we present novel analysis about the prediction error bounds of each segment that link e with the mean and variance of data localities. The segment-wise prediction error embeds the space-error 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 to fully explore diverse data localities with an e-learner module, which learns to predict the impact of e on the index performance and adaptively choose a suitable achieve better space-time trade-off.

---

Under review as a conference paper at ICLR 2022
We apply the proposed framework to several -tate-of-the-art (SOTA) learned index methods, and conduct a series of experiments on three widely adopted real-world datasets. Comparing with dynamic versions achieve significant index
the original learned index methods with fixed 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.
2
BACKGROUND
2.1 C-BOUNDED LEARNED INDEX
Given a dataset D {(x, le E N E )}. i' the set of keys over a universe U such 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 compact structure to support efficient query operations over 'D. Typically, the keys are assumed to be sorted in ascending order to satisfy the key-position monotonicity, i..., for any two keys, Iy > 23 iff their positions y/- Vj. such that the range query (X n [Zlow: Thigh) can be handled.
Recently, learned index methods (Kraska al. 2018 Li et al. 2019 Tang al.) 2020 Dai et al. 2020 Crotty 202T) leverage ML models to mine useful distribution information from D, and incorporate such information to boost the index performance. To look up given key x. the learned index first predicts position á using the learned models, and subsequently finds the stored true position based on with binary search or exponential search. Thus the querying time consists of the inference time of the learned models and the search time in (log((l - vl)). By modeling the data distribution information, learned indexes achieve faster query speed than traditional ---eree index, meanwhile using several inders-of-magnitud smaller storage space (Ding et al. 2020 Galakatos al., 2019
Ferragina & Vinciguerra, 2020b, Kipf et al. 2020 Marcus et al. 2020).
Many existing learned index methods adopt piece-wise linear segments to approximate the distribution of 'D due to their effectiveness and low computing cost, and introduce the parameter e to provides a worst-case preciseness guarantee and tunable knob to meet various space-time time trade-off preferences. Here we briefly introduce the SOTA e-bounded Icarned index methods that are most closely to our work, and refer the review chapter of (Ferragina & Vinciguerra 2020a for details of other methods. Specifically, SpecificallyGGalaaattoo Galakatos et al. (2019) greedily learn a set of piece- wise linear segments in a one-pass manner. Ferragina & Vinciguerra (2020b) adopt another one-pass algorithm that achieves the optimal number of learned segments. Kipf et al. (020) introduce a radix structure to organize the learned segments. |Ferragina et al. (2020) adopt fixed slope setting for all learned segments. Existing methods constraint all learned segments with the same i.e., the learning process ensures that the maximum prediction error is within a pre-defined where e E Z this paper, we will discuss the impact of in more depth and invistigate how to enhance existing learned index methods from a new perspective: dynamic adjustment of e considering the diversity of different data localities.
2.2 MEAN EXIT TIME (MET) ALGORITHM
Here we describe an illustrative learned index algorithm MET (Ferragina et al. 2020 Specifically, for any two consecutive keys of D, suppose their key interval (z; 2;-1) is drawn according to a random process [ie, where G; is a positive independent and identically distributed (i.i.d.) random variable whose mean is μ and variance is _² The MET algorithm learns linear segments s= ..., S₁ ..., SN] in one pass, where S, = a, + by is the learnable linear segment and N is the total number learned segments. The learning process as follows: The current linear segment fixes the slope a = 1/P and goes through the first available data point, thus b, is also determined. Then the segment covers as many data points as possible until a data point, say (a', y/) achieves the prediction error larger than c. The violation of triggers a new linear segment, and the data point (x',3') will be the first available data point, and the process repeats until no data point available. Although the MET algorithm adopts a simple learning mechanism, it makes the theoretical analysis convenient by modeling the learning process as a random walk process. Other e-bounded learned index methods such as TTTing-Tree (Galakatos et al. 2019), PGM (Ferragina & Vinciguerral 2020b) and Radix- -Spiine (Kipf et al.) (2020) learn linear segments in a similar manner while having different mechanisms to determine the parameters of (S.). Ferragina et al. (2020) reveal the relationship
2

---

Under review as a conference paper at ICLR 2022
between and index size performance based MET. In Section 3 about the impact of e on not only the index size, but also the index preciseness and a comprehensive trade-off off quantity, which facilitates the proposed dynamic adjustment.
present novel analysis
3 LEARN TO VARY
3.1 PROBLEM FORMULATION AND MOTIVATION
Before introducing the proposed framework, we 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 an e-bounded learned index algorithm A, aim to learn segments S [Si,... St..., SN] as index structure such that the size of S and Σi= MAF(D;]S.) are both small, where S; is the i-th learned linear segment with the parameter eg. MAE is the mean absolute prediction error, and D, C Di is the data whose keys are covered by S, For the remaining data D \ ÚUzZ Dj. the algorithm A repeatedly checks whether the prediction error of new data point violates the given eg. and outputs the learned segment S; that covers D. When all the 6,8 for i E [N] take the same value, the problem becomes the one that existing learned index methods are dealing with.
Now let's 's examine the effect of parameter e. To query specific data point, say (z,z),, we first need to find the specific segment S" that covers 2, and then search its true position y based on the estimated one أ 5" (z:). For the first step, we find S' from S in O(log(N)): for the second step, the search of y based on ÿ can be done in O(log(1 - yD). In summary, we can find the true position of y))) From here, we can see that the parameter plays an important role to trade off two contradictory performance terms, Le., the size of the learned index N, and MAE of the whole data MAE(D|S). we adopt small e, the maximal prediction error constraint is more frequently violated, leading to large N; meanwhile, the preciseness of learned index improved, leading small MAE(D|S). On the other hand, with large e, we will get a more compact learned index (i.e., small N) with larger prediction errors (i.e., a large MAE(D Thus these two inversely changed terms jointly impact the querying efficiency.
the queried data point in (log(N) + log(lū
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 that the linearity degree varies in different data localities. Recall that we use piece-wise linear segments to fit the data, and e determines the partition and the fitness of the segments. By varying e. 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 Seg SegErr; that is defined as the total prediction error within a segment S,, i..., Brg:Er:
E(r,))E, y S.(x)), which is also the product of the number of covered keys (e,) and the mean absolute error MAE(D, (S.). Note that a large Len(D:) leads to a small N since [D] = En" Len(D:). From this view, the quantity Erg,rr; internally reflects the space-error trade-off. Later we will show how 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 given es, the one-pass algorithm A determines S; and D; until the error bound 6, is violated. In other words, 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 {<r}s and learning index with a set of given {c}).
In this paper, we investigate how to efficiently find approximate solution this problem via the introduced c-learner module. Instead of heuristically adjusting c, the c-learner learns to predict the impact of on the index structure and adaptively adjusts c in principled way. Meanwhile, the introducing of e-learne 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 framework as shown in Figure | The c-learner is based on an estimation function SegErr f(,, μu, .)) that depicts the mathematical relationships among Seg,rr, and the characteristics μ. a of the data to 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, afterwards, we will internally transform the ? into another
In Appendix C we link the absolute prediction error and specific searching algorithms in further details.
3

---

Under review as a conference paper at ICLR 2022
D
User
(p(,a)
c Learner f(E.pa))
Expected SegErr
Expected
lookahead
shouse
Tupdate
Bey
[5,, Dil
reward
(R.) SegErr,
Prints
Inference
eleaaeer Learning
(Maxyyyy
Index Learningg
Figure 1: Dynamic framework with the c-learner module.
proxy quantity Eeg which reflects the expected prediction error for each segment if we set e; = E. This transformation also links the adjustment of and data characteristies together. which enables the deteadeennddnt adjustment of c. Beginning with é, the e-learner chooses suitable e; according to current data characteristics, then learn segment S; using A, and finally enhance the e-learner with the rewarded ground-truth Seg Err; of each segment. To make the introduced adjustment efficient, we propose to only sample small Look-ahead data D' estimate the characteristics (i.e., μ and o) of the following data locality. The learning and adjusting processes are repeatedly conducted and also 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 add no any additional cost the users' experience, and users can smoothly and painlessly use our framework with given é just as they use the original methods with given e. The an intuitive, easy-to-set and method-agnostic quantity for users. On the one hand, we can easily impose restrictions number in querying process is O [0 - y))). On the other hand, e is easier to estimate than the other quantities such index size and querying time, which are dependent specific algorithms, data layouts, implementations and experimental platforms. Our pluggable framework retains the benefits of existing learned index methods, such the aforementioned usability of and the ability
the worst-case querying cases with as the data accessing
to handle dynamic update case (Galakatos et al. 2019 Ferragina & Vinciguerra (020b).
We have seen how determines index performance and how SegErr; embeds the space-error trade- off in Section 3.1 In Section 3.3, we will further theoretically analyze the relationship among 6, Seg Err,, and data characteristics pt, different localities. Based on the analysis, elaborate the details of e-learner and the internal transformation between and SegErr; in Section 3.4
3.3 PREDICTION ERROR ESTIMATION
In this section, we will theoretically study the impact of on the prediction error Seg of each learned segment S: Specifically, for the MET algorithm, we can prove the following theorem to bound the expectation of Seg with e and the key interval distribution the data to be indexed.
Theorem 1. Given dataset 'D to be indexed and where E Z consider the setting of the MET algorithm Ferragina et al. 22020), in which key intervals of are drawn from a random process consisting of positive i.i.d. random variables with mean p and variance o², and > o/p. For learned segment S; and its covered data D,, denote SegErr: Loneen yy S((x)). Then the expectation of SegErr, satisfies:
2 9 L ErSegErr 3
2
This theorem reveals that the prediction error SegErr, depends on both and the data characteristics (μ and σ). Recall that CV a/u /u the coefficient of variation, a classical statistical measure of the relative dispersion of data points. In the context of the linear approximation, the data statistic 1/CV = p/o in our bounds intrinsically corresponds to the linearity degree of the data. With this, we can find that when u/o is large, the data is easy-to-fit with linear segments, and thus we can choose small e to achieve precise predictions. On the other hand, when μ/a 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 SegErr, for different learned segments consistent and achieve better space-error trade-off. This analysis also confirms the motivation of
4

---

Under review as a conference paper at ICLR 2022
varying 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 design of the e-learner module (Section 3.4). will take the derived closed-form relationships among Seg Err;, 6 and data statistic ju/o into account.
In the rest of this section, we provide proof sketch of this theorem due to the space limitation. For detailed proof, please refer to our Appendix. 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 S, : y = a,z + b,, we can calculate the expectation of Erg, for this segment as:
G 1)
B[SegErri] a
Σ
E
2 Σ .i=0
Pr(j'=n), =n),
(1)
where Z, is the j-th position of a transformed random walk {Zy)ee j = max E N - -c/a S
Zj S e/a; is the random variable indicating the maximal position when the random walk is within the strip of boundary =e/a;, and the last equality is due to the definition of expectation.
Under the MET algorithm setting where a; = 1/p and >> a o/M, μt we can show that the increments of the transformed random walk } have zero mean and variance o², and many steps are necessary to reach the random walk boundary. With the Central Limit Theorem, we can assume the Z, follows normal distribution with mean μazj 0 and variance d² jo and thus |Z,] follows the folded
normal distribution with expectation E((2,)) = 22 vj. Thus Eq. ( can be written as
2
n-1
E
Pr(j = <
E Irl = n)
VJ = =)).
1 n=1j=0
1=
R=
j=0
n² 2 and Varlj"]
2 n
Using Eli")
4
as derived in (Ferragina et al.
2020 we get [((*)²²]=
3 0²
5
With the inequality Σj Vi nn and B[X S (EE[X]) 3
we get the upper bound:
3
2 2 E[segErri] 3/ T B(())} 2
V 2a क (B())) 2 2 3
3
For the lower bound, applying the triangle inequality into Eq. [.. we can get E[SegErri] > E0m E [|]]] Pr(j" = n). where 7 = Σド= Zj. and Z follows the normal distribution since Z, ~ N(0 (zy) ). We can prove that [Z] follows the folded normal distribution whose expectation |||Z|] > on - 1T. Thus the lower bound is:
E[SegErri P (n 1)Pr(" =
1n
T T - ED 1]
p V
2)
M VVA
Since e >>>>> 2 we can omit the right term /Tr o/u 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 c, uu/o and Seg that the learned segment slopes of other methods are close to the reciprocal of expected key intervals in Appendix. We will empirically show the links between MET and other SOTA e-bounded methods, and how effectively the proposed framework works for them on real-world datasets (Section 4.2b.
still applicable to other c-bounded methods, and further prove
3.4 e-LEARNER
Now given an e, we have obtained the closed-form bounds of the SegErr in Theorem I. and both the upper and lower bounds are in the form of w/ (#)" ) n where W1,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 to make the error prediction preciser:
Seg ((,, =w 1 22 uss
(2)
I wi
2 <
2 5
s.t.
V=
3V
3
15 w2 < 2,
2 25
w3 S 3.
π
π
5

---

Under review as a conference paper at ICLR 2022
With this learnable estimator, we feed data characteristic wı/o of the look-ahead data and the trans- formed SrgErr into it and find a suitable E* as (#))
1/w2
We will discuss the
look-ahead data and the transformed Eeg in the following paragraphs. Now let's discuss the rea- sons for how this adjustment can achieve better index performance. Actually, the e-learner proactively plans the allocations of the total prediction error indicated by user (i.e., é (D)) and calculates the
tolerated SegErr for the next segment. By adjusting current e to e", the following learned segment can fully utilize the distribution information of the data and achieve better performance in terms of space-error trade-off. To be specific, when j//or is large, the local data has clear linearity, and thus we can adjust a relatively small value gain precise predictions; although the number of 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 / 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-wise adjustment of improves the overall index performance by continually and data-dependently balancing the cost of space and preciseness.
To make the training and inference of the e-learner light- we propose to look ahead few data D' to reflect the characteristies of the following data localities. Specifically, we leverage a small subset DD' C 'D \ Ujci Dj to estimate the value /t/ for the following data. In practice, we set the size of D' to be 404 when learning the first segment as initialization, and (T-TT أj=1 1j= Len(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 intervals for coefficient of variance 0/ S 0.2.
Look-ahead Data.
SegErr and Optimization. As aforementioned, taking the user-expected as input, we aim to reflect the impact of with a transformed proxy quantity SegErr such that the e-learner can choose suitable ex to meet users' preference while achieving better space-error trade-off. Specifically, we make the value of Seg updatable, and update it to be Seg = w (f/ (A/6)=agu> once new segment is learned, where jí/ is the mean value of all the processed data so far. This strategy enables us to promptly incorporate both the user preference and the data distribution into the calculation of Eeg As for the optimization of the f(c, jr, rr), adopt the projected gradient descent (Calamai & More 1987 den Hertog & Roos, 1991) with the parameter constraints in Eq. (2). In this way, we only need track few statisties and learn the e estimator in an efficient one-pass manner. The overall adjustment algorithm is summarized in Appendix D
EXPERIMENTS
4.1 EXPERIMENTAL SETTINGS
Baselines. We apply our framework into several SOTA e-bounded learned index methods that use different mechanisms to determine the parameters of segments {S:]. Among them, MET (Ferraginal et al., 2020) fixes the segment slope as the reciprocal of the expected key interval. D7Ting-Tree GGalakatos et al., (019) and Radix- Spllie- (Kipf et al.) (220) adopt greedy shrinking cone algorithm and a spline interpolating algorithm respectively. PGM (Ferragina & Vinciguerra 2020b) adopts a convex hull based algorithm to achieve the minimum number of learned segments. Further introduction and implementation details can be found in Appendix.
Datasets. We use several widely adopted datasets with differing data scales and distributions (Kaskk et al. 2018 Galakatos et al. 2019 Ferragina & Vinciguerra 2020b Li et al. 2021). Weblogs and IoT contain about 715M log entries from university web server and 26M event entries from different loT sensors respectively, in which the keys are both log timestamps. Map dataset contains location coordinates that are collected around the world from the OpenStreetMap contributors (2017). and the keys are longitude + 90 lotitude of about 1.8M places. Lognormal is a synthetic dataset whose key intervals follow the lognormal distribution. We generate 20M keys with 40 partitions

---

Under review as a conference paper at ICLR 2022
having different generation parameters simulate the varied data characteristies among different localities. More dataset details and visualization are presented in Appendix F
Evaluation Metrics. We evaluate the index performance in terms of its size, prediction preciseness, and the total querying time. Specifically. we report the number of learned segments N, the index size in bytes, the MAE as TDi L(ry)e by/ ((r)], and the total querying time per query in ns (i.e., we 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 space-error curve (AUSEC) where the x-axis and y-axis indicate N and MAE respectively. For AUSEC metric, the smaller, the better.
4.2 OVERALL INDEX PERFORMANCE
Space-Error Trade-off Improvements. In Table we summarize the AUSEC improvements in percentage brought by the proposed framework of all the baseline methods on all the datasets. We also illustrate the space-error trade-off curves for some cases in Figure 2] where the blue curves indicate the results achieved by fixed e version while the red curves are for dynamic e. Other baselines and datasets yield similar curves, which we include in Appendix due to the space limitation. From these results, we can see that the dynamic e versions of all the baseline methods achieve much better error-space trade-off (-16.48% to -33.57% averaged improvements as smaller AUSEC indicates better performance), demonstrating the effectiveness and the 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 data-dependently adjust to fully utilize the distribution information of data localities and thus achieve better index performance in terms of space-error trade-off. Note that the Map dataset has significant non- non-linean -ineerty caused by spatial characteristics, and is hard to fit using linear segments (all baseline methods learn linear segments), thus relatively small improvements are achieved.
Table I: The AUSEC relative improvements for learned index methods with dynamic e.
Weblogs
loT
Map
Lognormal
Average
MET FITing- Tree -31.18%
-25.87%
-7.66%
-10.99%
-21.48%
-16.48% -2.55%%
-25.56%
-9.30%
-28.24%
Radix-Spline PGM
-28.37%
-24.59%
-8.77%
-31.32%
-23.26%
-22.42%
-25.01% %
-7.18%
-19.58%
-18.55%
Lognormal Dataset
ToT Dataset
Weblogs Dataset
150
RadixSpline, Dynamic
RedixSplize, Original
150
RedisSpline, Original
RodisSpliae, Dysomic
P&M, Driginal
PGM, Dynamic 4
100
MAR
1on
MAE
50
11
10000
20000
90000
20000
40000
80000
1000
Figure 2: The space-error trade-off curves for learned index methods.
Weblogs Dataset
Datnser
2,00
Kacia
Origind
XHT Original
todes Stze (885)
12
4ffling Vax, Dynanic
a Fitigg Dynanic
1.30
1a0
20
A:16
Calo
2-64
1000
1100 120
Queriing (es)
Querying Time
Figure 3: Improvements in terms of querying time for learned index methods with dynamic
Querying Time Improvements. Recall that the querying time of each data point is in Olog (N) log(ly il) mentioned in Section where N and ly El inversely impacted by e. To examine whether the performance improvements w.r.t. space-error trade-off (i.e., Table can lead to better querying efficiency in real-world systems, show the averaged total querying time per
7

---

Under review as a conference paper at ICLR 2022
query and the actual learned index size in bytes for two scenarios in Figure We observe that the dynamic e versions indeed gain faster querying speed, since we improve both the term N as well as the term ly/ ø1 via adaptive adjustment of The similar conclusion can be drawn from other baselines and datasets, and we present their results in Appendix. Another thing to note is that, this experiment also verifies the usability of our framework in which users flexibly set the expected ē to meet various space-time preferences just as they set e in the original learned index methods.
Comparing with the original learned index methods that adopt a fixed e, our framework introduces extra computation to dynamically adjust e in the index building stage. Does this affect the efficiency of original learned index methods? Here we report the relative increments of building times in Table 2 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 has the same complexity the original methods (both in ((D)) Also 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- wolld applications.
Index Building Cost.
Table 2: Building time increments in percentage for learned index methods with dynamic
Weblogs
loT
Map
Lognormal
Average
MET FITing-Tree -ree 10.7%
10.54%
5.14%
7.55%
5.26%
7.12%
1.88%
6.04%
5.23%
5.96%
Radix-Spline PGM 16.76%
10.19%
1.64%
3.56%
8.96%
6.09%
2.2%
1.07%
21.29%
10.33%
4.3 ABLATION STUDY OF DYNAMIC
To gain further insights about how the proposed dynamic framework works, we compare the proposed one with three dynamic variants: (1) Random e is a vanilla version that randomly choose from [0, 2ē] when learning each new segment; (2) Polynomial Learner differs our framework with another polynomial function SegErr(c) = 01c² where 02 and 02 are trainable parameters; (3) Least Square Learner differs our framework with an optimal (but very costly) strategy to learn fc. with the least square regression.
Table 3: The AUSEC relative changes of dynamic variants compared to the proposed framework.
Weblogs
IoT
Map
Lognormal
Average
Random
+70.94%
+68.
+51.73%
+73.38%
+66.06%
Polynomial Learner
+49.32%
+40.57%
+7.29%
+42.77%
+34.99%
Least Square Learner
+4.44%
+9.32%
+2.20%
-17.63%
-0.42%
We summarize the AUSEC changes in percentage compared to the proposed framework in Table 3 Here we only report the results for FiTing-Tree due to the space limitation and similar results can be observed for other methods. Recall that for AUSEC, the smaller, the better. From this table, we have the following observations: (1) The Random version achieves much worse results than the proposed dynamic e framework, showing the necessity and effectiveness learning the impact of (2) The Polynomial Learner achieves better results than the Random version while still have large performance gap compared to our proposed framework. This indicates the usefulness of the derived theoretical results that link the index performance, the and the data characteristics together. (3) For the Least Square Learner, we can see that it achieves similar AUSEC results compared with the proposed framework. However, has higher computational complexity and pays the cost of much larger building times, e.g., 14x and 50x longer building times on IoT and Map respectively. These results demonstrate the effectiveness and efficiency of the proposed framework that adjusts based on the theoretical results, which will be validated next.
4.4 THEORETICAL RESULTS VALIDATION
We study the impact of c on SegErr, for the MET algorithm in Theorem I where the derivations based on the setting of the slope condition a, 1/μ. To confirm that the proposed framework also works well with other e- e-bounded learned index methods, we analyze the learned slopes of other e-bounded methods in Appendix. In summary, prove that for segment S; y a,æ: + b, whose
8

---

Under review as a conference paper at ICLR 2022
10
Map Dataset
Lognormal / 1 1ozz 0.5
Lognormal / 1==1
40
- L/p.
35
X
PGM
RatieSpline
Fillag-bee
36- Draad
30
25
Lowe Dound
FiElag
8 2
20-
10-
k/mm
x
Figure 4: Learned slopes.
Figure 5: Illustration of the derived bounds.
covered data is D, and the expected key interval of DD is p4,, then a, concentrates on 1/14 within (B,)) 1) relative deviations. Here we plot the learned slopes of baseline learned index that the learned slopes of other methods indeed center along the line a, = 1//4,, showing the close connections among these methods and confirming that the proposed framework work well with other e-bounded learned index methods.
methods in Figure 4 We
We further compare the theoretical bounds with the actual Seg for all the adopted learned index methods. In Figure we only show the results Lognormal dataset due space limitation. As expected, we can see that the MET method has the actual SegErr; within the derived bounds, verifying the correctness of the Theorem [ Besides, the other e-bounded methods show the same trends with the MET method, providing the evidence that these methods have the same mathematical forms as we derived, and thus the e-learner also works well with them.
4.5
CASE STUDY
SegBrr,
18017
31000
Segreests
We visualize the partial learned segments for FITing- -Tre with fixed and dynamic e on loT dataset in Figure where the N and
34000
33000
Σ -.Sggrrr indicates the number of learned segments and the
12000
total prediction error for the shown segments respectively. The
u/o indicates the characteristics covered data {D:]. We can
Key
41 11-4443X110
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 ? are diverse due to the diverse linearity different data localities: For the data whose positions are within about [30000, 30600] and [34700, 35000], the proposed framework chooses large es as their /u/ as are small, and by doing it achieves smaller N than the fixed version by absorbing these non-linear localities; For the data at the middle part, they have clear linearity with large p/os,, and thus the proposed framework adjusts as 19 and 10 that are smaller than 32 achieve better precision. These experimental observations are consistent with our analysis in the paragraph under Eq. (2). and clearly confirm that the proposed framework adaptively adjusts e based on data characteristics.
Dynamic N = 4, SegErr, 20854
Learned Sogmeata Original Data
ssace
5200e
6 47, 19, 30,52
31300
Key
+1. +1-484633:10
Visualization of the learned index (partial) on loT for FITing-Tree -ree with fixed 32 and dynamic version (ट 32).
Figure 6:
CONCLUSIONS
Existing learned index methods introduce an important hyper-parameter 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 data local characteristics and the introduced quantity Seg for each learned segment, which the product of the number of covered keys and MAE, and thus embeds the space-error trade-off. Based on the derived mathematical relationships, we present a pluggable dynamic e framework that leverages an c-learner to data-dependently adjust and achieve better index performance in terms of space-error trade-off. A series of experiments verify the effectiveness, efficiency and usability of the proposed framework.
We believe that our work contributes deeper understanding of how the impacts the index perfor- mance, and enlightens the exploration of fine-graines 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 used while still requiring space-erro tra such similarity search and lossy compression for time series data (Chen et al. 2007 Xie et al. 2014 Buragohain et al. 2007: O O'Ruurke 1981).

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
For the Theorem presented in Section 3.3, we give a complete proof in Appendix A We introduce more implementation details of our method and baselines in Appendix More detailed description of the adopted datasets is included in Appendix [F] To facilitate the reproducibitlity, we share downloadable source codes and PPython notebooks, and attach binary files of the public experimental datasets in the anonymous link
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. htttps://panthmmm.neet ntt. bt.ree//ttteeeeee 2013.
Chiranjeeb Buragohain, Nisheeth Shrivastava, and Subhash Suri. Space efficient streaming algorithms for the maximum error histogram. In IEEE 23rd International Conference on Data Engineering, pp. 1026-1035, 2007.
Paul Calamai and Jorge Moré. Projected gradient methods for lincarly constrained problems. Mathematical programming, 39(1):93-116, 1987.
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 learn. In /1th Conference Innovative Data Systems Research, 2021.
Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea Arpaci- Dusseau, and Remzi Arpaci-Dusseau. From wisckey to bourbon: A learned index for log- log-structured merge trees. In 14th USENIX Symposium on Operating Systems Design and Implementation, pp- 155-171, 2020.
Dick den Hertog and Cees Roos. survey of search directions in interior point methods for linear programming. Mathematical Programming, 5281):4815509 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 on Management of Data, pp. 969-984, 2020.
Paolo Ferragina and Giorgio Vinciguerra. Learned data structures. In Recent Trends in Learning From Data, pp. 5-41. 2020a. doi: 10. 1007/997 10.1007797-33030-44333 0-77888-00--888----- 2.
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): 166-11175 2020b. ISSN 2150-8097.
Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. Why learned indexes effective? In International Conference on Machine Learning, pp. 3123-3132, 2020.
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. 1206, 2019.
Goetz Graefe and Harumi Kuno. Modern b-tree techniques. In 27th International Conference on Data Engineering, pp. 1370-1373, 2011.
ICT (CL.22-Paper997..ig
10

---

Under review as a conference paper at ICLR 2022
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 learned index. Proceedings of the Third International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, 2020.
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the International Conference on Management of Data, pp. 489-504, 2018.
Xin Li, Jingdong Li, and Xiaoling Wang. Aslm: International Conference on Database Systems for Advanced Applications, pp. 80-99 90-95. Springer, 2019.
Adaptive single layer model for learned index. In
Yaliang Li, Daoyuan Chen, Bolin Ding, Kai Zeng, and Jingren Zhou. A pluggable learned index method via sampling and gap insertion. arXiv preprint arXiv:2101.00 00000, 2021.
Chen Luo and Michael J Carey. Lsm-based storage techniques: a survey. The VLDB Journal, 29(1): 393-418, 2020.
Ryan Marcus, Andreas Kipf, Alexander van 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.
Michael Mitzenmacher. A model for learned bloom filters, and optimizing by sandwiching. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 462-471, 2018.
OpenStreetMap contributors. Planet dump retrieved from https://plantt.osm.ogg https://wwz opemstreetmap. org 2017.
Joseph O'Rourke. An on- on-line algorithm for fitting straight lines between data ranges. Communications of the ACM, 24(9):574-578 1981.
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.
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 learning to hash. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(4):769-790, 2018.
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.
Xuanhe Zhou, Chengliang Chai, Guoliang Li, and Ji Sun. Database meets artificial intelligence: A survey, IEEE Transactions on Knowledge and Data Engineering, 2020.
11

---

Under review as a conference paper at ICLR 2022
APPENDICES FOR THE SUBMISSION: LEARNED INDEX WITH DYNAMIC
A PROOF OF THEOREM
Given learned segment S. y a b; denote e₁ the stored position of the last covered data for the (i - 1 1) segment (c₁ = 0 for the first segment). We can write the expectation of Seg for the segment S, as the following form:
Erre E
Σ la;X; + bb - 1)
where jr indicates the length of the segment, and Xj indicates the j-th key covered by the segment S, As studied in Ferragina et al. (2020), the amprx-iaproo problem with guarantee can be modeled as random walk processes. Specifically, X; = Xo + Ek=p GR (for j E Z)) where Gg the key increment variable whose mean and variance is μ and o² respectively. Denote the = j/a; + (b, G 1)/a; the j-th position of the transformed random walk {Zj JeN, j"d mjx E N - c/a; S Zj S c/az} as the random variable indicating the maximal position when the random walk within the strip of boundary Ie/ ke/as (a.. The expectation can be rewritten
U Σ
G 1)
E
Ja,X, 1 + (b. ci -1)l
E
Σ
Zzj
j=0
(3)
E
[z
Pr(j n).
n=1
The last equality in Eq. (3) is due to the definition of expectation. Following the MET algorithm that the St goes through the point (Xu, Yo = G, 1), we get b, -a + C + 1 and we can rewrite Zj as the following form:
j E -G--1/a;) 1/a:)= E(w).. k=1
Zo 0,
Z3 120
X, Xo j-/a;=
Σ Gx - j/ai
k=1
k=1
where W, is the walk increment variable of Zy, E[WA] = 1 and Var[Wa] = a2. Under the MET algorithm setting where 0; = 1/p and a 14, the transformed random walk [Zz} has increments with zero boundary. With the Central Limit Theorem, we can assume that Z, follows the normal distribution with mean Paj and variance oz and thus |2y1 follows the folded normal distribution:
and variance 0², and many steps are necessary to reach the random walk
Zy (1 1/a)).30")
E(1Z)) Majl - 22 - -=s//zz)) 02 2/T expl 220
where & is the normal cumulative distribution function. For the MET algorithm, a; 1/p and thus the Maj = 0, ozj o o.J. and [E( 1 V2/Ta vj. Then the Eq. (3) can be written as
1
00
E
Σ
Zz1
Pr(j* n))
E
B
Pr(j" n)
(4)
2
VjPrl" =
11
π m= j=0
For the inner sum term in Eq. (4), we have (2)-0 Vj)= < 2 /n since
n Σ
Vi<
Σ Vj
/"
2 Vr dr
-
2
3
0=0
12

---

Under review as a conference paper at ICLR 2022
then the result in Eq. (4) becomes
2 2
Erry
nynPr(j =n)
3 T n=1
2 2 n ((*)
2 [())))]]]
2 S 33 T (BI0))9)²
3 3V π μ
3V z
where the last inequality holds due to the Jensen inequality B[x < [E[ $ Using [[i"]
0²
2 4 es derived in MET algorithm Ferragina et al. (2020), get ([ | 3 o4 which yields the following upper bound:
5 nr
and Varlj*|
3 3
2 2 3 π
Errg
33
For the lower bound, applying the triangle inequality into the Eq. (3), we have
E
Pr(j*
=) n)
E
Zz1
Pr(j* = n)
11
n=1
j=0
(5)
8c
Σ
E
|| Pr(j" = =)),
n=1
where 7 = En-1 Zy.. Since Z3 ~ N(O0, 22)). the follows the normal distribution:
n-1
Z B~N [uz 0, o2 Σ j=0
Σ
Tyk0=)00k))
j=
where ryk is the correlation between Z, and Zz. Since μzz 0, the |Z| follows the folded normal distribution with B[[Z]] oz 2/m. Since the random walk {Z is process with i.i.d. increments, the correlation rk 2 With J. / > 0 and ryk 2 0, we have
Ozj n(n 1)/T on 1)
E 2
Σ 1=
and the result in Eq. (5) becomes:
E{Seg Erra)
E
Zzj
Pr(j* nn)
11
1=0
0
1
(n - PI = n)
1
n=1
1 v
σ
EB 1|
#
π
Since é >> a we can omit the right term v [ and finish the proof.
B LEARNED SLOPES OF OTHER e- BOUUNDED METHODS
As shown in Theorem 1, we have known how e impacts the SegErr; of each segment learned by the MET algorithm, where the theoretical derivations largely rely on the slope condition a, = 1 1/p. Here we prove that for other c-bounded methods, the learned slope of each segment (i.e., a; of S,) concentrates on the reciprocal of the expected key interval shown in the following Theorem.
13

---

Under review as a conference paper at ICLR 2022
Theorem 2. Given Σ11 and an e-bounded learned index algorithm A. For linear segment S, : y = a, + by learned by A, denote its covered data and the number of covered keys as De and (Dn(D;) respectively. Assuming the expected key interval of Dj is pi, the learned slope a, concentrates on = 1/1s with bounded relative difference:
2 (1 Len -1 )a S
2
Elas]
S +11+ T (e.) )0.
Proof. For the learned linear segment S,, denote its first predicted position and last predicted position
have its slope 0; Yn - c S y S Y/ + due the e guarantee, we have yn yo 2c Vn 1/ S y/+ yo + 2e and the expectation of can be written as
as 1/ and yr, respectively,
v/- -% Notice that yo S 1/6 - yo + and
In =z0
+ 2E
V/2 V/
+ 2e
S
Ela:
E
Zn 20
In To
In Io
Note that for any learned segment S, whose first covered data (wo, yo! and last covered data is (In, Vr), we have EE]
En Vn.
μ4 and thus the inequalities become
vu-
2c
1
2c
E
Elag]
S
+
In
/
To
Since ā = 1/1, and Bizn- xol = (B]Len(D)) (D:)] ]] - 1)u4, we finish the proof.
The Theorem 2 shows that the relative deviations between learned slope a, and are within 2e/ [e/(ELen((D:] 1). For the MET and PGM learned index methods, we have the following corollary that depicts preciser deviations without the expectation term ([Len(Di)].
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 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.
C CONNECTING PREDICTION ERROR WITH SEARCHING STRATEGY
As we mentioned in Section 3.1, we can find the true position of the queried data point in O(log(NV + log(Iğ yl)) where N is the number of learned segments and |ø y/ is the absolute prediction error. binary search or exponential search can be used finds the stored true position y based on ÿ. is worth noting out that the searching cost in terms of searching range jú - y of binary search strategy corresponds the maximum absolute prediction error c, whereas the one of exponential search corresponds to the mean absolute prediction error (MAE). In this paper, we decouple the quantity Sey Err; as the product of (en(D,) and MAE(D, (S:) in the derivation of Theorem 1. Built upon the thcoretical 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, Denote the absolute prediction error of k--th data point covered by this segment as 1g ykl, the maximum absolute prediction error as e; where y0x Vkl < c, for all &s [Den(
The binary search conducted within the searching range [y c for each data point 3, O(ez), which is independent of the
thus the mean search range is Eler [e) 2e, preciseness of the learned segment and upper bound of MAE(D,
'The lower bound and upper bounds of searching ranges should be constricted to 0 and len respectively. For brevity, we omit the comner cases when comparing these two searching strategies as they both need to handle the out-of-hounds scenario.
14

---

Under review as a conference paper at ICLR 2022
The exponential search first finds the searching range where the queried data may present by centering around the D. repeatedly doubling the range [3 + 29] where the integer 9 grows from 0, and comparing the queried data with the data points positions f After finding the specific range such that qe satisfies 2 < 1 yas < 2 20og((e)) for the k-th data, an binary search is conducted to find the exact location. In this way, the mean search range is 2==1 Tex(D.) (2 [log((x)] 11+ (MAAF(D) (S.),, which can be much smaller
(e)n(D))
than ((4)) especially for strong predictive models and the datasets having clear linearity.
D THE ALGORITHM OF DYNAMIC ADJUSTMENT
Algorithm Dynamic Adjustment with Pluggable Learner
Input: D: Data be indexed, A: Learned index algorithm, ē: Expected e, p² Length percentage
for look-ahead data
Output: S: Learned segments with varied es
1: initial parameters W12,33 of the learned function: (.. w1(#)) (
2: initial mean length of learned segments so far: Len(Ds) 404
3: S x Ø. (p/ō)) +
4: repeat
5:
(u/O)) < -oookaheaddD Len(Ds) p) 1/we
1 get data statistic */ 1+ adjust e based on the learner */ 7 learn new segment S₁ using adjusted e* */
6:
6- SegErr/ (wn((")))
7:
[S, D. - A(D,E")
8:
S+SUS,
9:
D+ D
Len(Ds) running- meen Len(Ds), Len(D.)
online update Len (en(Ds) */
11:
(A/6) + moming--meat (A/a), (n/o))
12:
W1.23 5 optimize(f, Sr, Srg
1e train the learner with ground-truth */
SegErr w1//6))002
14:
until =
In Section 3.4, we provide detailed description about the initialization and adjustment sub-procedures. The lookahead() and optimizee) are in the Look-ahead Data and SegErr and Optimization paragraph respectively.
E IMPLEMENTATION DETAILS
All the experiments are conducted on a 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 al., 2019) adopts greedy shrinking cone algorithm and the learned segments are organized with a -tre.. Here we use the stx::btree (v0.9) implementation (Bingmann, 2013) and the filling factors of inner nodes and leaf nodes as 100%, i.e., we adopt the al., 2020) adopts greedy spline interpolating algorithm to learn spline points, and the learned spline segments are organized with flat radix table. We set the number of radix bits the Radix-Spline method, which means that the leveraged radix table contains 2 entries. PGM (Ferragina & Vinciguerra, 2020b) adopts convex hull based algorithm 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.
filling manner. Radix-Spline (Kipf
16 for
We then describe few additional details of the proposed framework in terms of the c-leamer initialization and the the beginning, we learn the first five segments with the e sequence [té, jē, 42], then track their rewarded Err; and update the parameters 21,2,3 using least square regression. We empirically
setting. For the W1,2.3 of the c-learner shown in the Eq. (2), at
15

---

Under review as a conference paper at ICLR 2022
found that this weight initialization leads better index performance compared to the versions with random parameter initialization, and it benefits the exploration of diverse e², i.e., leading to the larger variance of the dynamic sequence (eI,..., ................................ EN.. As for the hyper-paramette (described in the Section 3.4), we conduct grid search over p E [0.1, 0.4, 0.7, 1.0) on Map an loT datasets. We found that all the ps achieve better space-error trade-off (i.e., smaller AUSEC results) than the fixed e versions. Since the setting p = 0.4 achieves averagely best results on the two datasets, we set p to be 0.4 for the other datasets.
F DATASET DETAILS
Our framework 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 a university web server and the keys are log timestamps. IoT Galakatos et al. (2019); Ferragina & Vinciguerra (2020b) contains about 26M event entries from different IoTT sensors in building and the keys are recording timestamps. Map dataset Kraska al. (2018); 8); Galakatos et al. (2019); Ding et al. (2020); Ferragina & Vinciguerra (2020b): Li et al. (2021) contains location coordinates of 1.8M places that are collected around the world from the Open Street Map OppnStreetMap contributors (2017), and the keys are compound by coordinates as longitude + 90 latitude. Lognormal Ferragina & Vinciguerra (2020b) is a synthetic dataset whose key intervals follow the lognormal distribution: In(G,) ~ (j4g og To simulate the varied data characteristics among different localities. We generate 20M keys with 40 partitions by setting Alg = 1 and setting Flg with 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 CDFs of experimental datasets in Figure 7 and Figure 8 respectively, which intuitively illustrate the diversity of the adopted datasets.
Map
Leguormal
Ker
Ray
10x
Kay
Figure CDFs of adopted datasets.
Zeamedita in Wehlings
Zeomed- en ln!
Zoomee in Map
Zoomed is Leguomal
3.00
0/91
1.90
3.55
6650
0600
1.5
140
0/21
10881
14.0
1.27X
1471
1228
1.33
1xlf Tale sote' 4018
3050 288 2718 230
2.55
410
Kxy
Figure 8: Zoomed-in CDFs of adopted datasets.
G ADDITIONAL EXPERIMENTAL RESULTS
Overall Index Performance. For the space-error trade-off improvements and the actual querying efficiency improvements brought by the proposed framework, we illustrate more space-error trade- off curves in Figure 9 and querying time results in Figure 10. Recall that the N N-MAE 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 be 1 28bit if consists of two
16

---

Under review as a conference paper at ICLR 2022
couble-precision float parameters (slope and intercept); (2) the querying operation can be done in (log(NN) + (ly - 5l) as we mentioned in Section 3.1, thus a better .N-MAE tradc-off indicates better querying efficiency. From these figures, baseline methods achieve better space-error trade-off and better querying efficiency, verifying the effectiveness and the wide applicability of the proposed framework.
see that the dynamic versions of all the
Weblogs Dataset
1oT Dataset
Map Dataset
VITing Original
Wiiting Tree, Original
123
FTTing- Original
Filing Tree, Dyumai
PTTing Tree, Dyosuik
FTTing Trea, Dynamic
MAE
MAE
MAR
75
0-00
60-
128
50-
25-
25
0-
2000
40nn
Lognormal Dataset
Weblogs Dataset
Map Dataset
100
TTes Original
RidlisSpline, Original
RadisSpinee, Original
WTTing Teen, Dyname
RadiaSpline, Dynamic
Radiocipmmee Dynamite
MAR
10
MAB
60
1-5
128
20
10000
20000
30000
200
600
800
1000
9000
5000
10000
IoTT Dataset
Map Dataset
Lognormal Dataset
150
-55
PCM. Origina
PGM. Original Dynamic
150
PCM
PGM. Dynomic
PCM, Dynamic
253
MAE
1.00
120
MAE
60-
50
30
10000
20000
90000
40000
50000
1000
2000
3000
4000
5000
2000
4000
6000
8000
Weblogs Dataset
Map Dataset
Lognormal Dataset
12.5
MET. Otiginal
100
MET: Original MET, Dynotic
MET, Original
10.0
Dynamic
Dynsmic
7.8
MAF
80
5.0
60-
2.5
20-
25-
0.0
500
1000
1500
2000
4000
6000
8000
10000
10r000
20000
30000
N
N
N
Figure 9: The additional space-error trade-off curves for learned index methods.
Ablation Study. To examine the necessity and the effectiveness of the proposed framework, in Section 4.3, we compare the proposed framework with three dynamic variants for the FlTing-Tree Tree method. Here we demonstrate the AUSEC relative changes for the Radix-Spling method with the same three variants in Table 4 and similar conclusions can be drawn.
Table The AUSEC relative changes of dynamic e variants compared to the Radix-Spline method with the proposed framework.
Weblogs
loT
Map
Lognormal
Average
Random c
+81.23% +56.20%
+74.78%
+59.20%
+83.16%
+74.59%
Polynomial Learner
+53.28%
+7.01%
+55.01% %
+42.88%
Least Square Learner
-9.56%
+9.81%
+0.58%
-11.23%
-2.60%
Theoretical Validation. In Section 4.4, we show that all the learned index baseline methods learn similar segment slopes the Map dataset. Here we illustrate the learned slope results on the IoT, Weblogs and Lognormal datasets in Figure 11, which supports the Theorem that the learned segment slopes concentrate the 1/p4 with a bounded relative difference.
17

---

Under review as a conference paper at ICLR 2022
Besides, for the comparison between the theoretical bounds and the actual Seg, of all the adopted learned index methods, we show more results on another two datasets Gamma and Uniform in Figure 12. where the key intervals of the two datasets follow gamma distribution and uniform distribution respectively. These results show that the MET method gains actual Seg Err; within the bounds, verifying the correctness of the Theorem again. Here all the learned index methods also achieve the same trends, showing that these methods have the same mathematical forms w.r.t. the Seg e and p/o., and hence the e-learner can effectively learn the estimator and adaptively choose suitable e.
Weblogs Dataset
1oT Dutoset
2110
1,00
e:16
Inkes Sireakh)
1,70
1,00
Ongiral MIET. Dyranic
XMI Orgind
854
6-l
MME, Dynanis
todex
call
c-16
750
X
an82
500
C-64
Zul 7
1000
1000
1100
1530
1330
1900
Winn
1700
1901
150
Quersing Time (ms)
Quegingg Time (es)
Map Datnect
Legcomal Datiset
Inder Index S32e-K33
130
XMET. Origind
800
CH16
XMET.Orgind
-00
cm32 X
MET, Dyrazic
bodox St00
ANET, Dynasis
200
dnd 178
c=128
20256
30
34
rabil
138
1230
1221
Querying Time (ea)
Weblogs Dataset
Dutaset
2,000
1,000
1,000
x
#115
Xlladi Sptine Ongend
bidee Sire (630)
1001
Rais RRais-Spiac Dynanic
Taloo Stoe
1,20
Rado Splan, Dysanic
1,50
AsTS
Cx32
Cmc
4x
2o16
X
1.00
1,30
C-54
Co64
Gazad X
C-128
986
900
Querying
Quorying Timettes)
Map Dotaset
Lognomaal
Xe-16 #:18
Syline Origind A &tais, Dyserics
1220
Kitadi-Spttes, Origind
Ste
Sale
Altado Apriss Dyramic
dnd2
1,340
1200
C-125
CH04 am128 wx256
010 .00
190 <5
64256
6m
300
1900
tom 19a1 liv Querying Timetas)
Pund 24175A (-256.x
Qutrying Timetes)
Weblogs Datsset
loT Dinsset
wclb
Inies (13))
PGM. Origial
Indien Store (631
MINM Origod
PEMM Dysavic
#c
Dyranice
6-02
243
and4 12g AX
canse 4X55556
8-61
2-128
650
150
150
3030
1000
1250
150C
1350
1400
3400
1500
Querying Time (nd)
Qurrying Time (ns)
Map Datuset
Lognormal Datavet
10C
#:18
Inles Ston (03))
XPOM
Gales (KD)
2-16
XINM Orggina
X CH32
PUMM, Dynanic
Dyswrk
Po32
C-64
X
Pu12
co54
2=138
cH128
AX
1853
1iah
1307 T2
Querying Timeine)
Querying
Figure 10: Improvements in terms of querying time for learned index methods with dynamic e.
18

---

Under review as a conference paper at ICLR 2022
ToT Datause
Weblogs Dataset
Lognortnal Dataset
1.0
1/js FlTlngg Twoe
- 1/js
= 1/26 Viting RudisSiline PCM
Filtue Radiscpplis PCMM
0.8
RadisSppite
PGM
0.6
0.25
0.35
0.25
1/pu
Figure 11: Learned slopes on the IoT, Weblogs and Lognormal datasets.
Camma,
1.0
Camma,
0 3.0
Camma,
NRBT Upeer Boes
... PON
SEFT Opper Tead
PCH
34T Upper Barad
POM
tead
Killing
HIKT Ihaad 1rPing
23-
Logg
Lox
100
200
400
200
500
400
200
300
400
high
Uniformn, low 0.0, high 10.0
L.iiform,
10.0, high
40
35
30-
MET
85-
50
Logg
100
200
500
400
1000
200
300
400
100
200
800
400
Figure 12: Illustrations of the derived bounds on Gamma and Uniform datasets.
19


Reviews:
[{"review_id": "xqddCLjQp8-", "reviewer": "Reviewer_bkBs", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\n1. The paper is well-written and easy to follow. I can easily understand the idea of this paper. The author first gives their intuition which motivates their proposed method.\n2. This paper conducts extensive experiments on real-world datasets from different domains to show their improved performances, which is very reasonable and convincing to me.\n\nWeaknesses:\n1. There are some typos, in Table 3, the authors ignore the positive sign in the last column (compared to other columns),\n2. The author can incorporate more explanations on the experimental results. For example, ‘From these results, we can see that the dynamic versions of all the baseline methods achieve much better error-space trade-off (( 16.48% to 23.57% averaged improvements as smaller AUSEC indicates better performance’, why there are some negative improvements?\n3. There is one related reference, authors need to highlight their difference.", "summary_of_the_paper": "This paper mainly studies the index structure problem.  Existing learned index methods use a fixed value for all the learned segments. In this paper, the author contributes a deeper understanding of how the impacts the index performance, and enlightens the exploration of fine-grained trade-off adjustments by considering data local characteristics.  Experiments with real-world datasets and several state-of-the-art methods demonstrate the efficiency, effectiveness, and usability of the proposed framework.", "summary_of_the_review": "This paper is well-written and studies on the theoretical analysis of the database field, which focuses on an important and popular problem. ", "strength_and_weaknesses": "", "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": "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": "hv4xO7L2wL4", "reviewer": "Reviewer_Fjr7", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper can be improved in terms of both argumentation and design.\n\nThe paper claim to resolve several tradeoffs at the same time through the proposed ε-learning approach:\nIt claims that the proposed method improves a space-time tradeoff in index performance.\nAt the same time, it claims to improve another trade-off, that of space-error.\nYet it in never clear how these three trade-off quantifies, space, time, and error are not compared to each other for a given ε value.\nIn particular, Figure 2 presents what appears to be a view of the space-error tradeoff. Yet it is not clear what ε values are set for each measured data point in the figure, and it is not clear what querying time they require. Perhaps improvement on one trade-off come at a cost on another.\nSimilarly, Figure 3 presents a good picture in terms of index size and querying time, yet it is not clear what cost that entails in terms of error.\n\nOn the design side, it is not clear why there should be user-define ε at all. If a user is interested on some index feature and presumably goes not wish to have a fixed ε guarantee, then it would be reasonable to do away with a user-specified ε, and use the proposed approach in order to guarantee some observable index feature, e.g., size, while adjusting ε as seems fit. The semantics of a dynamic ε guarantee from the user's point of view are unclear.", "summary_of_the_paper": "This paper proposes a methodology, pluggable to any learned index method, that adjust the prediction error guarantee ε to data locality so as to achieve a given expected value of ε while improving index performance by some measure. Experiments with real world data show that the proposed approach can be plugged in several existing learned index method with improved results.", "summary_of_the_review": "The paper resolves two trade-offs with clarifying the relationship among them, and does not explain the meaningfulness of a dynamic ε", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UJ4ugiRMTXe", "reviewer": "Reviewer_it4h", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The main strength of this paper is the empirical study, which shows some interesting results.  However, I am not sure that the theoretical justification is sound.  Namely, the main justification for using a dynamic $\\epsilon$ seems flawed.  The authors argue that allowing for different $\\epsilon$'s between segments allows the algorithm to decrease the number of linear segments at the cost of increasing the mean absolute error of some of the segments.  In the analysis of the runtime, it seems that what matters is the maximum absolute error in the predicted indexes, not the mean absolute error, which can be much smaller.  Thus it seems natural to me that prior methods guarantee that the maximum error of each segment is at most $\\epsilon$.  Due to this, there seems to be a disconnect between the theoretical explanation of why the proposed method should work well and the method's improved empirical performance.  The proposed method seems to be able to trade-off between the number of segments and the mean absolute error within a segment, but not the maximum error which is what shows up in the runtime analysis.\n\nAdditionally, the overall presentation of the paper could be improved.  The paper could benefit from a more clear description of the $\\epsilon$ tuning algorithm.  Related to the comments above, the motivation in section 3.1 could be improved by directly connecting the running time to the mean absolute error in a segment, as right now it seems to be connected to the maximum error.  \n\nMinor comments:\n-  Use \\log inside of math environments to represent logarithms", "summary_of_the_paper": "This paper considers learning based methods for constructing index structures, a fundamental data structure.  Recent work has given learning based index structures which guarantee a maximum error of $\\epsilon$ in the predicted index.  At a high level, this is done by breaking up the data set into several segments, and then a linear function is fitted to each segment, while maintaining the $\\epsilon$ error guarantee.  \n\nThe main idea behind this paper is to allow $\\epsilon$ to vary across the different segments.  This is motivated by the fact that answering a query must first find the correct segment via a binary search, and then perform another binary search within the segment using the fitted linear function.  The runtime of the first step depends on the number of segments and the runtime of the second step depends on the prediction error.  By allowing the prediction error of some segments to go above $\\epsilon$, the number of segments can be decreased, allowing for better trade-offs in some cases.  The main conceptual contribution is a method for tuning $\\epsilon$ across different segments, which can be plugged directly into pre-existing learned index methods.    The authors give a theoretical analysis based on a stochastic analysis of the MET algorithm from prior work which is then leveraged to design their method for tuning $\\epsilon$ across different segments.\n\nAn empirical study of their algorithm is performed on standard datasets for this area, comparing to several baselines from recent work in this area which use a fixed $\\epsilon$.  The results show that the proposed $\\epsilon$ tuning method can improve several learned index methods from prior work.", "summary_of_the_review": "The paper provides some interesting experimental results on using dynamic $\\epsilon$ in learned index structures, but the theoretical justification does not seem to explain the improved empirical performance adequately.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a new learning based algorithm for constructing index structure. Existing learned index algorithm use a fixed value, in contrast the authors show that a more refined methods can be used to obtain higher quality solutions for the problem.

The reviewers, after discussion, found the paper interesting and the experimental results promising but they feel that the paper in the current form is not yet ready for publication.  In particular,
- in the current form the theoretical motivation and the experimental results are a bit detached

Overall, the paper is interesting and the results are promising but it probably would benefit from significant re-writing before being accepted.
Decision: Reject