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

Learned Index with Dynamic c
Anonymous Author(s)
Affiliation Address email
Abstract
Index structure is 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 no more than a pre-defined c. However, existing learned index methods adopt fixed for all the learned segments, neglecting the diverse characteristics of different data localities. In this paper, we propose
2
6
learned index framework with dynamic e, which is efficient and pluggable to existing learned index methods. We theoretically analyze prediction error bounds that link with data characteristies for an illustrative learned index method. Under the guidance of the derived bounds, learn how vary and improve the index performance with better space-time trade-off. Experiments with real-world datasets and several state-of-the-at methods demonstrate the efficiency, effectiveness and usability of the proposed framework.
cethhemmtiicllyygroonee
10
12
13
Introduction
14
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
Data indexing 15 32
16
18 to substantial improvements in terms of both storage space and querying efficiency [T] 24 31
19
The key insight behind this trending topic of "learned index" is that the data be indexed contain useful distribution information and such information can be utilized by trainable ML models that
20
21
map the keys (5) to their stored positions (y)-
22 To approximate the data distribution, state-of the-art (SOTA) learned index methods 14 18
23 propose to learn piece-wise linear segments S = [St, ..., St .... Sv], where S;
0₂ + b; 24 is the linear segment parameterized by (a,, b,) and N the total number of learned segments. These methods introduce important pre-defined parameter E 2>1 and adopt the following online learning process: Beginning from the first available data point, the current linear segment adjusts (a,, b,) and covers as many data points as possible until data point, say (x', v/) achieves
26
28 the prediction error [S,(z') - y'1 e. The violation e triggers a new linear segment, and the data point (x', y²) will be the first available data point. The process repeats until no data point is available 30 and as a result, the worst-case preciseness can be guarantced with e.
31 By tuning e, various space-time preferences from users can be met. For example, a relatively large
32 result in small index size while having large prediction errors, and the other hand, relatively
33 small e provides users with small prediction errors while having more learned segments and thus a
34 large index size. However, existing learned index methods implicitly assume that the whole dataset to
35 be indexed contains the same characteristics for different localities and thus adopt the same e for all
36 the learned segments, leading sub-optimal index performance. More importantly, the impact of
37 on index performance is intrinsically linked to data characteristics, which are not fully explored and
38 utilized by existing learned index methods.
39 Motivated by these, in this paper, we theoretically analyze the impact of e on index performance, and link the characteristics of data localities with the dynamic adjustments of Based the derived
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

41 theoretical results, we propose an efficient and pluggable learned index framework that dynamically
42 adjusts e in a principled way. To be specific, under the setting of an illustrative learned index method MET [TO], we present novel analysis about the prediction error bounds of each segment that link
48
44 6 with the mean and variance of data localities. The segment-wise prediction error embeds the 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 to fully explore diverse data localities with e-learner module, which learns to predict the impact of on the index performance and adaptively choose a suitable to achieve a better space-time time trade-off.
45
46
47
48
50
We apply the proposed framework to several SOTA learned index methods, and conduct a series of experiments on three widely adopted real-world datasets. Comparing with the original learned index methods with fixed e, our dynamic e 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:
51
52
59
54
56
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 a broad class of piece-wise approximation algorithms.
57
58
59
We provide theoretical analysis for proxy task modeling the index space-time trade-off, which establishes our e-learner based on the data characteristies and the derived bounds.
60
61
We achieve significant index performance improvements over several SOTA learned index methods on real-world datasets. To facilitate further studies, we make our codes and datasets public at
62
63
2
Background
64
65
Learned Index. Given a dataset D = {(x, v)lı E X.y E y). X' is 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 -tee [I] aims to build a compact structure to support efficient query operations over D. Typically, the keys are assumed to be sorted in ascending order satisfy the key-posiiiinn monotonicity, ie.,, for any two keys, I2 > 2; iff their positions y/ > Vj. such that the range query (2' n [Flow; Thigh) ) can be handled.
66
67
68
69
71
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 y based ý with binary search exponential search. Thus the querying
Recently, learned index methods 19 20
30 7
72
73
74
75 time consists of the inference time of the learned models and the search time in Ollg((p) - yy)) By modeling the data distribution information, learned indexes achieve faster query speed than traditional
77
B -tree index, meanwhile using several pnders-of-magniuus smaller storage space 9 14 12 I8 23)
78
e-bunddd Linear Approximation. 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 to provide a worst-case preciseness guarantee and a tunable knob to meet 82 various space-time trade-off preferences. Here we briefly introduce the SOTA e-bounded learned
80
81
83 index methods that are most closely to our work, and refer to the review chapter of [[] for details of other methods. We first describe an illustrative learned index algorithm MET IC Specifically, for any two consecutive keys of DD suppose their key interval (x; x;- is drawn according to a random process (NN, where G; a positive independent and identically distributed (i.i.d.) random variable whose mean is and variance is o². MET learns linear segments (S; : a, } via a simple deterministic strategy: the current segment fixes the slope a; = 1/p. goes through the first available data point and thus by is determined. Then S; covers the remaining data points one by one until a data point (x', a/) gains the prediction error larger than e. The violation triggers a new linear segment that begins from (a'; vv) and the process repeats until 'D has been traversed
84
85
86
87
88
89
90
91
92
Other c-bounded learned index methods learn linear segments in a similar manner to MET while having different mechanisms to determine the parameters of {. FITing- Tree [14] uses a greedy shrinking cone algorithm. PGM [12 adopts another one-pass algorithm that achieves the optimal
93
94
95 number of learned segments. Radix-Spline [18] introduces a radix structure to organize the learned
96 segments. However, existing methods constrain all learned segments with the same 6. All of these piece-wise segments based approaches attempt to improve performance by changing the way
2

---

98
segments are learned or organized, but ignore the optimization potential of dynamically varying e. In this paper, we will discuss the impact of e in more depth and investigate how to enhance existing learned index methods from a new perspective: dynamic adjustment of e accounting for the diversity of different data localities. Besides, different from [T]] that reveals the relationship between c and
99
100
101
102
index size performance based on MET. In Section 3. we present novel analysis about the impact of
103
e on not only the index size, but also the index preciseness and a comprehensive trade-off quantity,
which facilitates the proposed dynamic adjustment.
105
3
Learn to Vary 6
106
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. we aim to learn linear segments 109
107
108
110
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 \ AU D). 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 EjS for E [NV] take the same value, the problem becomes the one that existing learned index methods are dealing with.
S [S,,.., S...., SN] with segment-wise varied [<)]ee(n) such that a better trade-off between
111
112
113
114
115
116
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 MAE(D:]S:), ), which affected and upper-bounded by eG. 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, e.g., the size of segment can be 128bit if it consists of two double-precision float parameters (slope and intercept); (2) When using exponential search, the querying complexity is (log + log (M (S)). in which the first term indicates the finding process of the specific segment S' that covers the key x for a queried data point (I. y), and the second term indicates the search range |/ - yl for true position y based on the estimated one S' (zz). In this paper, we adopt exponential search as search algorithm since it better than binary search for exploiting the predictive ability of learned models. In Appendix C, we show that the search range of exponential search is O (MA)((D)) (.)). 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 in [.
117
118
119
120
121
122
123
124
125
126
127
128
130
Now let's examine how the parameter affects the -MMAE 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 6, the prediction error constraint is more frequently violated, leading to large N; meanwhile, the preciseness of learned index is improved, leading to small MAE of the whole data MA)( On the other hand, with a large e, we will get a more compact learned index (i.e., a small N) with larger prediction errors (i.e., large MA)(D
132
133
134
136
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 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 Err, that is defined as the total prediction error within a segment St, Le., ErgErr; A (x,))) y - S((x)), which is also the product of the number of covered keys Len(DD and the mean absolute error MAE(D, (St). Note that large Len(D:) leads to a small N since| [D] ΣN, (en(D.). From this view, the quantity Seg internally reflects the N-MAE trade-off. Later we will show how to leverage this quantity to dynamically adjust
137
138
139
140
141
142
143
144
145
146
3.2
Overall Framework
In practice, it is intractable to directly solve the problem formulated in Section With given 6,, the one-pas algorithm A determines S, and D, until the error bound e, 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 {<:}s and learning index with a set of given (4).
148
150
151 In this paper, we investigate how to efficiently find an approximate solution to this problem via the
152
introduced e-learner module. Instead of heuristically adjusting e, the e-learner learns to predict
3

---

153 the impact of e on the index structure and adaptively adjusts e in principled way. Meanwhile, the 154 introducing of e-learner should not sacrifice the efficiency of the original one one-pass learned index algorithms, which is important for real-world practical applications.
155
User
Expected
① init SégErr
LeLarner Kepoo)
T upditte SegBrr
Data Peines
Learned Segmenas (aaxy-
@ lookahead oyt
reward Segtrr, (R.
@ predict &
Bi Piasl
D
① learn index
A (D, 6)
[s)
(D, G(1)
Way
Figure 1: The dynamic framework. We !) transform ė into the proxy prediction error Seg Err, then 2 sample a small look-ahead data D' to estimate the data characteristics o). 3 The e-learner predicts suitable e; accordingly, and 4 we learn new segment S; using A (e.g., PGM) with e;. 2 Once S; triggers the violation of 6, the e-learner is updated and enhanced with the rewarded ground-truth. Steps ② 5 repeat an online manner to approximate the distribution of D.
156
These two design considerations establish our dynamic e framework as shown in Figure |I The e-learner is based on an estimation function Ser [(e, J4, a) that depicts the mathematical relationships among 6, Fer, and the characteristics 14, a of the data to be indexed. As a start, users can provide an expected é that indicates various preferences under space-sensitive or time-sensitive applications. To meet the user requirements, afterwards, we internally transform the é into another
157
158
159
180
161
proxy quantity Seg which reflects the expected prediction error for each segment if we set e; = ē. This transformation also links the adjustment of c and data characteristics together, which enables the data-dependent adjustment of c. Beginning with ?, the c-learner chooses suitable 6; according to current data characteristics, then learns a segment S; using A, and finally enhances the c-learner with the rewarded ground-truth Seg Err; of each segment. To make the introduced adjustment efficient, we propose to only sample a small Look-ahead data D' to estimate the characteristics (μ, or) of the following data locality. The learning process repeats and is also in an efficient one-pass manner.
162
163
164
165
166
167
188
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 as they use the original methods with given c. The is an intuitive, meaningful, easy-to-set and methoc-agnostic quantity for users. On the one hand, we can easily impose restrictions on the worst-case querying cases with as the data accessing number querying process Olog((i y))). On the other hand, is easier to estimate specific
189
170
171
172
173
than the other quantities such as index size and querying time, which are dependent 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.
175
176
177
178
We have seen how determines index performance and how Seg embeds the N-MAE trade-off in Section 3.1 In Section 3.3 we further theoretically analyze the relationship among e, Seg and data characteristics μ,, at different localities. Based on the analysis, we elaborate the details of llarrer and the internal transformation between c and Seg,rr; in Section 3.4
179
180
181
182
3.3
Prediction Error Estimation
183
In this section, we theoretically study the impact of e on the prediction error Seg of each learned segment S,. The derived closed-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 SegErr; with and the key interval distribution of D.
184
185
186
187
Theorem 1. Given dataset D to be indexed and an e where E Z,,, consider the setting of the MET algorithm AIO) in which key intervals of DD are drawn from a random process consisting of positive i.i.d. random variables with mean i and variance o², and 2> a a/p. For a learned segment
188
St and its covered data D., denote SegErr; = E(E))ED by - S,(x).. Then the expectation of
180
We discuss how to extend existing works in more details in Appendix E.
4

---

191
Erg, satisfies
V 1 T22 <[SeggErr] < x
2 2 5, 3V x 3
182
This theorem reveals that the prediction error EegErr, depends both e and the data characteristics (n, σ). Recall that CV=o/p is is 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 / is large, the data is easy-to-fit with linear segments, and thus we can choose a small c
193
194
195
196
197
to achieve precise predictions. On the other hand, when ju/ar is small, it becomes harder to fit the data using a linear segment, and thus c 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 N-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 and leverage the data distribution better.
196
199
200
202
203
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 Appendix A. The main idea is to model the learning process of linear approximation with guarantee as 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, + d;, we can calculate the expectation of Ser, for this segment as:
204
207
( Σ
E[segErr]] = a,E
2
E
Pr(j = n))
(I)
where Z, is the j-th position of a transformed random walk (Zz J" = max E N| e/a S 208
2j < e/a;} is the random variable indicating the maximal position when the random walk is within the strip of boundary =e/o;. and the last cquality is due to the definition of expectation.
210
211
Under the MET algorithm setting where a; = 1/p 1 and 6 >> o/ μl, 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 Zj follows normal distribution with mean μzj = 0 and variance o2 jo² and thus |2,1 follows the folded normal distribution with expectation E((Zz)) = 12/Ta VJ. Thus Eq. 1 can be written as
212
213
214
215
PT(j" = =)<< 1 n-1
R
E PZZIII n)
VJPr(j = n).
22 ²² and Varlj*] 2 n
ft e 3 o
216
Using [[]"]
σ²
3 E as derived in 10. we get E[("'}]
With the
inequality ΣØ=0 VJ < /n and E| & (E(X)),,
3 we get the upper bound:
217
20 E((
2/ 3 क
2
2a (BG)))
a 2
2 2
E[SegErr] 3V π 1
For the lower bound, applying the triangle inequality into Eq. D. we can get E[SegErri >
и En [| Pr(j" n). where Z Σj=o Zj. and Z follows the normal distribution since
219
Z3 ~ 02) We can prove that |Z| follows the folded normal distribution whose expectation
220
221
B| > an - 1)/v Thus the lower bound is:
I Σ (n- 1)) =n) =n)= a -E [ 3) V
BrSegErr,]
-1] -1
1
222 Since E >>>>>>> 2 we can omit the right term VTT a 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, 1/aa and Seg are still applicable to other e-bounded methods, and further prove that the learned segment slopes of other methods are close to the reciprocal of expected key intervals in Appendix B. For the another independence assumption adopted by the MET algorithm, the authors discussed that the Central Limit Theorem holds for non-i.i.d. variables and the theorems can be
a:
223
225
227
extended accordingly IT.. We empirically show that the proposed framework is robust to these assumptions and works well for several SOTA methods on the real-worke datasets (Section
229
5

---

230 3,4 e-Learner
231
Now given an 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 wi (#) ) where 2,,2. 2,3 are some coefficients. As
233
the concrete values of these coefficients can be different for different datasets and different methods,
234
we propose to learn the following trainable estimator to make the error prediction preciser:
SegErr (L) =wi 1 1
T s. I wh - 3
2 2 2)
2
3\
SSWSS 25 W/ S 3.
236
With this learnable estimator, we feed data characteristic w/a of the look-ahead data and the trans- formed SegErr into it and find a suitable e* as (SegErr/wu ( 1/ws We will discuss the
237
238
look-ahead data and the transformed SrgErr 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., E. (D)) and calculates the
240
241
tolerated SegErr 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 -MM off To be specific, when p/or 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 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, c 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.
242
243
244
245
246
247
248
249
Look-ahead Data. To make the training and inference of the e-learner light-weight, propose to look ahead a few data D' to reflect the characteristics of the following data localities. Specifically, leverage a small subset D' C 'D \ Ujes Dj to estimate the value jı/or for the following data. In practice, we set the size of D'' be 404 when learning the first segment as initialization, and 254
252
(11) Σj= Len(D)) p for the other following segments. Here p pre-defined parameter 255
256
indicating the percentage that is relative to the average number of covered keys for learned segments, considering that the distribution of u/o can be quite different to various datasets. As for the first segment, according to the literature []]. the sample size 404 can provide a 90% confidence intervals
258
259
for coefficient of variance a/ o/1= S 0.2.
260
Err and Optimization. As aforementioned, taking the user-expected E as input, we aim to reflect the impact of ē with transformed proxy quantity SegErr such that the e-learner choose suitable e* to meet users' preference while achieving better N-MAE trade-off. Specifically, we make
262
"> once a new segment 254 is learned, where ăz/ō is the mean value of all the processed data so far. This strategy enables
263
the value of SegErr updatable, and update it to be Seg w1 (A/d)">zuu
285 us to promptly incorporate both the user preference and the data distribution into the calculation
286 of SegErr. As for the optimization of the hight-weight model, i.e., [(, Jr, (7) that contains only three learnable parameters W1, 21,,,3, we adopt the projected gradient descent 4 g with the parameter constraints in Eq. In this way, we only need to track few statistics and learn the estimator in an efficient one-pass manner. The overall algorithm is summarized in Appendix D.
267
269
Experiments
270
4.1
Experimental Settings
272
Baselines. We apply our framework into several SOTA e-bounded learned index methods that use different mechanisms to determine the parameters of segments {St). Among them, MET 10 fixes the segment slope as the reciprocal of the expected key interval. FlTing-Tree Tree (44 and Radix-Spline 18 adopt a greedy shrinking cone algorithm and a spline interpolating algorithm respectively. PGM adopts a convex hull based algorithm to achieve the minimum number of learned segments. More introduction and implementation details are in Appendix F.
273
274
275
278
277

---

278
Datasets.
We use several widely adopted datasets that differ in data scales and distributions 21. Weblogs and IoT contain 715M log entries from a university web server and 26M event entries from different IoT sensors respectively, in which the keys are log timestamps. Map dataset contains location coordinates around the world (5), and the keys are longitudes of 200M
279
19
281
282
places. Lognormal is synthetic dataset whose key intervals follow the lognormal distribution. We
283
generate 20M keys with 40 partitions having different generation parameters to simulate the varied data characteristics among different localities. More details and visualization are in Appendix G.
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 Toi D(ay))D ly S(x)], 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 a quantitative comparison w.r.t the trade-off improvements, we calculate the Area Under the N-M AE Curve (AUNEC) where the x-ax and y-axis indicate N and MAE respectively. For AUNEC metric, the smaller, the better.
286
288
289
290
291
282
4.2
Overall Index Performance
293
N-MAE Trade-off Improvements. In Table I we summarize the 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 where the blue curves indicate the results achieved by fixed version while the red curves are for dynamic c. Other baselines and datasets yield similar curves, which we include in Appendix H 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 (-15.66% to - 22.61% % averaged improvements as smaller AUNEC 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 N N-MAE trade-off. Here the Map dataset has significant non- non-linearity caused by spatial characteristics, and it is hard to fit using linear segments (all baseline methods learn linear segments), thus relatively small improvements are achieved.
294
295
296
297
298
300
302
304
306
Table 1: The AUNEC relative improvements for learned index methods with dynamic c.
Weblogs
loT
Map
Lognormal
Average
MET FITing-Tres Tree
-25.87%
-7.66%
-7.63%
-21.48%
-15.66% -22.48%
-31.18%
-25.56%
-4.94%
-28.24%
Radix-Spline PGM
-28.37%
-24.59%
-6.14%
-31.32%
-22.61%
-22.42%
-25.01%
-7.18%
-6.52%
-15.28%
Lognormal Dalaset
1oT Datuset
Weblogs Dataset
200
HadisSplino, Otiginal
RadisSpline, Original
PCM, Original
RadisSplline Dynamic
150
RadixSpline, Dynamic c
15
PGM, Dynamic
258
MAE
300
132
50-
10000
20000
30000
20000
40000
60000
0
1000
200
300
400
N
Figure 2: The N trade-off curves for learned index methods.
Weblogs Dataset
2000
Prtngg Original
Teer Origiaal
Hodes (839
Pffiig Tree. Dysack
1:c0
1.40
Dynanic
1,20
Ke16
2004
Quayingg Taneron
Figure 3: Improvements in terms of querying time for learned index methods with dynamic e.
Querying Time Improvements. Recall that the querying time of each data point is in O(og((N) (N) +
308
log(ly - rl) as we mentioned in Section 3.1 where N and ly - - are inversely impacted by e. To examine whether the performance improvements w.r.t. N-MAE trade-off (i.e., Table [ can lead
7

---

310
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 Figure ]]
311
We also mark the 99th percentile (P99) latency as the right bar. We can observe that the dynamic versions indeed
312
313
gain faster average querying speed, since we improve both the term N as well as the term ly - 5l via adaptive adjustment of 6. Besides, we find that the dynamic version achieves comparable or even better P99 results than the static version, due to the fact that our method effectively adjust e based on the expected and data characteristic, making the {ei} fluctuated within a moderate range and leading to a good robustness. The similar conclusion can be drawn from other baselines and datasets, and we present their results in Appendix H. Another thing to note is that, this experiment
314
315
317
319
also verifies the usability of our framework in which users can flexibly set the expected é to meet various space-time time preferences just as they set in the original learned index methods.
321
Index Building Cost. Comparing with the original learned index methods that adopt a fixed e, we introduces extra computation to dynamically adjust in the index building stage. Does this affect the efficiency of original methods? Here we report the relative increments of building times in Table 2 From it, can observe that the proposed dynamic e framework achieves comparable building times
322
323
324
325
to all the original learned index methods on all the datasets, showing the efficiency of our framework
326
since it retains the online learning manner with the same complexity the original methods (both in
327
((D))) Note that we only need to pay this extra cost once, i.e., building the index once, and then
328
the index structures can accelerate the frequent data querying operations for real-world applications.
Table 2: Building time increments in percentage for learned index methods with dynamic
Weblogs
1oT
Map
Lognormal
Average
MET
10.54%
5.14%
8.33%
5.26%
7.32%
FITing-TTee Tree 10.70%
1.88%
5.35%
5.23%
5.79%
Radix-Spline PGM 16.76%
10.19%
1.64%
3,85%
8,96%
6.16%
2.20%
1.28%
21.29%
10.38%
329
4.3
Ablation Study of Dynamic
330
To gain further insights about how the proposed dynamic e framework works, we compare the proposed one with three dynamic variants: (1) Random e is a vanilla version that randomly choose from [0, 26] when learning each new segment; (2) Polynomial Learner differs our framework with another polynomial function SrgErr(e) = e where 0₃ and 02 are trainable parameters; (3) Least
331
332
334
Square Learner differs our framework with an optimal (but very costly) strategy to learn p4,
335
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 Polynomial Learner
+70.94%
16%
+53.29%
+73.38%
+66.45%
+49.32%
+40.57%
+7.71%
+42.77%
+35.09%
Least Square Learner +4.44%
+9.32%
+2.04%
- -17.63%
-0.46%
336
We summarize the AUNEC changes in percentage compared to the proposed framework in Table 3 Here we only report the results for FITing-Tree due 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 c framework, showing the necessity and effectiveness of learning the impact of
337
338
339
340
341
(2) The Polynomial Learner achieves better results than the Random version while still have a 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.
343
344
(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 53 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.
345
347
349
4.4
Theoretical Results Validation
350 We study the impact of e on SegErr; for the MET algorithm in Theorem U where the derivations based on the setting of the slope condition a, 1/p. To confirm that the proposed framework
8

---

ToT Dataset
Lognormal J
Lognormal /
46-
aam 1/pr
40
Uyga Doadd
PGMd Hasting
MEB Upper Dinnd
PGM Rediinghe
PiZteg Tiee
X
Radiciplioe
Loue/SegBrer
30-
1..
20-
11.4
0.3
0.4
0.6
1.0
1000
200 500
4000
100
2000 300
1/14.
Figure 4: Learned slopes.
Figure 5: Illustration of the derived bounds.
352
also works well with other e-bounded learned index methods, we analyze the learned slopes of other e-bounded methods in Appendix B. In summary, we prove that for segment S; y a,z + b, whose covered data is D, and the expected key interval of D; is 14; then a, concentrates on 1/p, 1) relative deviations. Here we plot the learned slopes of baseline learned index methods in Figure 4 We can see that the learned slopes of other methods indeed center along the line a; 1/j4, showing the close connections among these methods and confirming that the proposed framework can work well with other e-bounded learned index methods.
354
within 2e/ 2//1 (E[Tee((D)
355
356
358
We further compare the theoretical bounds with the actual SegErr; for all the adopted learned index methods. In Figure 5 we only show the results on Lognormal dataset due to space limitation. As expected, we can see that the MET method has the actual Seg,rr, within the derived bounds, verifying the correctness of the Theorem || Besides, the other e- 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 c-learner also works well with them.
360
382
364
365
4.5
Case Study
Fixed:
T. E, SegErrs 46017
386
We visualize the partial learned segments for FlTing-Tree -Teee with fixed and dynamic on IoT dataset in Figure C where the N and
35000
Leazzed Segnuctoo
34000-
387
31000
388
Σ Erg indicates the number of learned segments and the
369
total prediction error for the shown segments respectively. The
a indicates the characteristics of covered data [D:). We can
370
see that our dynamic framework helps the learned index gain both smaller space (7 v.s. 4) and smaller total prediction errors (45017 v.s. 29854). Note that es within E are diverse due to the diverse linearity of different data localities: For the data whose positions within about [30000, 30600] and [34700, 35000], the proposed framework chooses large es as their pa/ors os are small, and by doing so, 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
Dynamic: N 4, SegErr: 29854
Ney
+1.15133-11
372
Learmeed Seguennc Ortiinal Datt
34000
374
53000
52000
F 47, 10,52 W7
376
Koy
1.1. 11--060-.1100
378
Figure 6: Visualization of the learned index (partial) on IoT for FiTing-Tree with fixed e 32 and dynamic version (é 32).
379
380
32 to achieve better precision. These experimental observations 381
are consistent with our analysis in the paragraph under Eq. (
382
383
and clearly confirm that the proposed framework adaptively adjusts based on data characteristics.
Conclusions
384
305
Existing learned index methods introduce an important hyper-parameed to provide a worst-case preciseness guarantee and meet various space-time user preferences. In this paper, we provide formal analysis about the relationships among e, data local characteristics and the introduced quantity Seg 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 e-learner to data-dependently adjust and achieve better index performance in terms of space-time trade-off. A series of experiments verify the effectiveness, efficiency and usability of the proposed framework.
387
389
391
393
We believe that our work contributes 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
394
395
397
6 are used while still requiring space-time trade-off, such as similarity search and lossy compression
for time series data
5
3 t 26

---

References
399
400
[1] D. Abel. A B+-tree strueture for large quadtrees. Computer Vision, Graphics, and Image Processing, 27(1):1-31, 1984.
[2] T. Bingmann. Stx b+ tree. httpss//bbaueee....////00//22222
2013.
[3] C. Buragohain, N. Shrivastava, and S. Suri. Space efficient streaming algorithms for the maximum error histogram. In IEEE 23rd International Conference on Data Engineering, pages 1026-1035, 2007.
404
405
408
[4] H. Calamai and J. J. Moré. Projected gradient methods for linearly constrained problems. Mathematical programming, 39(1)933-11, 1987.
407
408
[5] Q. Chen, L. Chen, X. Lian, Y. Liu, and J. X. Yu. Indexable pla for efficient similarity search.
409
In Proceedings of the 33rd international conference on Very large data bases, pages 435-446, 2007.
410
[6] A. Crotty. Hist-tree: Those who ignore it are doomed to learn. In 11th Conference on Innovative Data Systems Research, 2021.
412
415
[7] Y. Dai, Y. Xu, A. Ganesan, R. Alagappan, B. Kroth, A. Arpaci-Dusseau and R. Arpaci-Dusseal From wisckey to bourbon: A learned index for log-structured merge trees. In 14th USENIX
415
Symposium on Operating Systems Design and Implementation, pages 155-171, 2020.
416
[8] D. den Hertog and C. Roos. A survey of search directions in interior point methods for linear programming. Mathematical Programming, 52(1): (2(1):48-550) 1991.
[9] J. Ding, U. Minhas, H. Zhang. Y. Li, C. Wang. B. Chandramouli, J. Gehrke, D. Kossmann, and D. B. Lomet. Alex: An updatable adaptive learned index. In Proceedings of the ACM SIGMOD International Conference Management of Data, page 969-984, 2020.
419
[10] P. Ferragina, F. Lillo, and G. Vinciguerra. Why are learned indexes so effective? In International Conference on Machine Learning, pages 3123-3132, 2020.
422
423
[11] P. Ferragina and G. Vinciguerra. Learned data structures. In Recent Trends in Learning From Data, pages 5-41. 2020.
424
425
[12] Ferragina and Vinciguerra. The PGM-Index: A fully- compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment, 13(8):1
426
427
2020.
428
[13] A. Galakatos, A. Crotty, E. Zgraggen, C. Binning and T. Kraska. Revisiting reuse for approximate query processing. volume 10, pages 1142-1153, 2017.
[14] A. Galakatos, M. Markovitch, C. Binnig, R. Fonseca, and T. Kraska. FlTing-Tree: A data-aware index structure, In Proceedings of the International Conference on Management of Data, page 1189-1206, 2019.
431
[15] G. Graefe and H. Kuno. Modern b-tree techniques. In 27th International Conference Data Engineering, pages 1370-1373, 2011.
434
435
[16] K. Kelley. Sample size planning for the coefficient of variation from the accuracy in parameter estimation approach. Behavior Research Methods, 39(4):555-766, 2007.
436
437
[17] A. Kipf, T. Kipf, B. Radke, V. Leis, P. A. Bonez, and A. Kemper. Learned cardinalities: Estimating correlated joins with deep learning. In 9th Biennial Conference on Innovative Data Systems Research, 2019.
438
439
440
[18] A. Kipf. R. Marcus, A. van Renen, M. Stoian, Kemper, T. Kraska, and T. Neumann. Radixspline: A single-pass learned index. In Proceedings of the Third International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, 2020.
442
443
[19] Kraska, A. Beutel, F. H. Chi, J. Dean, and N. Polyzotis. The case for learned index structures. In Proceedings of the International Conference Management of Data, page 489-504, 2018.
10

---

445
[20] X. Li, and X. Wang, Asim: Adaptive single layer model for learned index. In International Conference on Database Systems for Advanced Applications, pages 80-95. Springer, 2019.
448
447
[21] Y. Li, D. Chen, B. Ding, K. Zeng, and J. Zhou, A pluggable learned index method via sampling and gap insertion. arXiv preprint arXiv:2101.00800 2021.
[22] C. Luo and M. Carey. Lsm-based storage techniques: survey. The VLDB Journal, 29(1)3393-
450
418, 2020.
451
[23] R. Marcus, A. Kipf, A. van Renen, M. Stoian, S. Misra, A. Kemper, T. Neumann, and T. Kraska.
452
Benchmarking learned indexes. Proceedings of the VLDB Endowment, 14(1):1-13, 2020.
453
[24] M. Mitzenmacher. A model for learned bloom filters, and optimizing by sandwiching. In
454
Proceedings of the 32nd International Conference on Neural Information Processing Systems, page 462-471, 2018.
455
496
[25] OpenStreenMap contributors. Planet dump retrieved from https://planet.osm.org /ww..openstreetmappp org 2017.
https
[26] J. O'Ruukee, An on-line algorithm for fitting straight lines between data ranges. Communications of the ACM, 24(9):574 578, 1981.
459
480
[27] M. H. Overmars. The design of dynamic data structures, volume 156. Springer Science & Business Media, 1987.
462
[28] O'Neil, E. Cheng. Gawlick, and E. O'Neil. The log-structured merge-tree (Ism-tree). Acta Informatica, 3314)3551-385 1996.
[29] J. Rao and K. A. Ross. Cache conscious indexing for decision-support in main memory. In Proceedings of the 25th International Conference on Very Large Data Bases, page 78-89, 1999.
465
486
[30] C. Tang, Y. Wang, Z. Dong, G. Hu, Z. Wang. M. Wang. and H. Chen. Xindex: a scalable learned index for multicore data storage. In Proceedings of the 25th ACM SIGPLAN Symposium Principles and Practice of Parallel Programming, pages 308-320, 2020.
488
489
[3]] K. Vaidya, E. Knorr, M. Mitzenmacher, and T. Kraska. Partitioned learned bloom filters. In International Conference on Learning Representations, 2021.
470
[32] Wang, T. Zhang, j. song, N. Sebe, and Shen. A survey on learning to hash. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(4))769-790, 2018.
[33] Q Xie, C. Pang, X. Zhou, X. Zhang, and K. Deng. Maximum error-bounded piecewise linear
474
representation for online stream approximation. The VLDB journal. 23(6):915-937, 2014.
475
[34] X. Zhou, C. Chai, G. Li, and J. Sun. Database meets artificial intelligence: survey. IEEE
Transactions Knowledge and Data Engineering, 2020.

---

Checklist
477
478
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes]
480
481
(b) Did you describe the limitations of your work? [Yes] Please see the last paragraph in the Section [x
482
483
(c) Did you discuss any potential negative societal impacts of your work? [No] For the studied theoretical analyses and the proposed learned index framework, we have not
485
seen direct paths to negative societal impacts.
486
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
488
2. If you are including theoretical results...
489
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Please see the Theorem
490
481
(b) Did you include complete proofs of theoretical results? [Yes] Please see the supplementary material, and we also provide proof sketch in Section 3.
493
3. If you ran experiments...
494
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Please see the
486
URL in the final part of the Introduction.
497
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Please see the URL and the Appendix F.
498
499
(c) Did you report error bars (c.g., with respect to the random seed after running ex- periments multiple times)? [N/A] The experimental learned index methods are all deterministic algorithms.
501
502
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] Please the Appendix F.
503
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
505
(a) If your work uses existing assets, did you cite the creators? [Yes] Please see the Section
506
4
507
(b) Did you mention the license of the assets? [N/A]
508
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
509
510
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
513
514
5. If you used crowdsourcing or conducted research with human subjects...
515
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
516
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
518
519
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
520
12


Reviews:
[{"review_id": "rwDrLdCafUX", "reviewer": "Reviewer_X1hc", "summary": "This paper proposes a pluggable method that learns a dynamic prediction error bound \\epsilon for some error-bounded learned indexes. With the proposed method, the learned index can make a better trade-off between space and time. Experiments on real world data show the efficacy of applying the proposed method on existing learned indexes.", "questions": "1. How does your dynamic \\epsilon framework with SOTA \\epsilon-bounded learned indexes compare to these works in terms of indexing performance?\n2. When the distribution shifts, does the learned \\epsilon still fit?", "limitations": "There is no negative societal impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strength:\n1. The paper is well-organized and the motivation is easy to follow.\n2. The idea is easy to understand and interesting.\n\nweakness:\n1. In the motivation, the authors explain why the parameter \\epsilon affects the N-MAE trade-off, thus affects the performance of the learned index in terms of the index size and indexing speed. It not clear that how much the parameter \\epsilon affects the indexing performance compared to other aspects (e.g., data layout) of the learned index. The motivation should provide more preliminary results on different \\epsilon to show the impact is significant and learning \\epsilon is worthy, since the Figure 3 and Figure 10 show the maximum improvement on the index size and query time is only about 1MB and less 100ns.\n2. The \\epsilon-Learner requires users input an expected \\epsilon before it starts to learn the \\epsilon. This requirement is not reasonable enough which conflicts with the semantics of the dynamic \\epsilon framework. The prediction errors which related to \\epsilon only indirectly reflects the indexes' performance. To obtain a good performance (faster indexing and smaller index size), users still have to try different \\epsilon to know the quantitive relations between \\epsilon and indexing speed or size. For example, if users expect that the query time of FITing-Tree is less than 900 ns, they need to try different \\epsilon until they find the fact that \\epsilon should be smaller than 16 (Figure 3).\n3. Recent works, e.g., ALEX, LIPP, have achieved a better performance compared to that of PGM-index, FITing-Tree. These works doesn't need a \\epsilon to bound and have shown that the performance of learned indexes can be significantly improved with a better data layout. It seems not necessary to for the more advanced learned index to include the dynamic \\epsilon.\n4. In the results of index building cost, the paper claims the extra cost is only paied once. However, the paper lacks the experiments of the impact of updates on \\epsilon-Learner. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SBgDRYMO8Mh", "reviewer": "Reviewer_o36M", "summary": "This paper focuses on learning index with dynamic prediction error. The major contribution of this paper is proposing an efficient, pluggable d learned index framework that is adaptive to dynamic prediction error. ", "questions": "The motivation of dynamic $\\epsilon$:\n\nAn intuition of dynamic $\\epsilon$ is that we can have flexible computational overhead to fit the budget. Does the running time of proposed the framework in query varies with dynamic $\\epsilon$? If so, what is the saving if we have relaxed $\\epsilon$?\n\nThe running time analysis:\n\n1. Is there any extra overhead we should pay to enjoy the adaptivity over different $\\epsilon$?\n\n2.  A naive approach for dynamic $\\epsilon$  is to maintain a multi-level set of indices, and each is for different $\\epsilon$. What is the advantages of the proposed approach to this naive approach in terms of running time and memory?\n\nRobustness to adaptive queries:\n\nAs mentioned before, one advantage of dynamic $\\epsilon$ is that we can design robust data structures over adversaries. From this point of view, is the current framework allow adaptive queries?  Does the theoretical analysis on the query procedure assume the queries are independent? ", "limitations": "This paper is trying to solve a problem with practical significance. The current presentation can be improved with answers to the questions in the previous sections. Specifically, a better connection between the dynamic $\\epsilon$  setting to practical problems would help the understanding from a broader audience.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. Problem setting: this paper studies an interesting problem in learning to index. In the practical deployment of indexing data structure, the approximation error can vary due to the computation budget. Moreover, the dynamic approximation error would benefit the robustness of the index over the adversary.\n\n2. Method: the proposed method have a solid mathematical foundation. The workflow of theoretical analysis makes sense to the reviewer. \n\n3. Evaluation: the experiment presented in this paper is extensive, making this paper more convincing. A highlight of contribution would be the simulation of different $\\epsilon$ patterns in Sec 4.3\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HDnOapxtKjC", "reviewer": "Reviewer_ky4v", "summary": "The paper presents a method to learn a variable error bound $\\varepsilon_i$ to use when building piecewise linear segments for learned indices for databases.\nThis additional learned component is based on an estimation function that uses a sample to estimate the mean and the variance of the remaining data which will be covered by the next linear segment.\nThere is an analysis of the prediction error, making some not-so-strong-but-not-weak assumptions about the data distribution.\nThe experimental evaluation shows that the additional component greatly improve the space/error trade-off, does not cost too much in terms of indexi building cost, and has similar query costs as existing methods.", "questions": "I'm wondering about the appropriateness of using a sample over the whole \"leftover\" part of the Data to estimate $\\mu$ and $\\sigma$ (if I'm understanding correctly, a new estimation is taken before building each segment). The estimates are, I assume, the sample mean and sample stddev, but I wonder whether one should be using a more refined model by, e.g., fitting a curve on the sample, or something similar, to get a better approximation of the behavior of the next data points, which should allow to get a better estimates for the parameters, thus for $\\varepsilon_i$. Can you please comment on possible different choices for this step, which seems crucial?", "limitations": "I would have liked to see more discussion/evaluation of the limitations of the proposed approach. For example, what happens when the assumptions on the distributions are not satisfied.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strenghts\n\n* Good idea, and well executed\n\n* Complete experimental evaluation, and convincing.\n\n* Very clear presentation\n\n## Weaknesses\n\n* The whole presentation relies a lot on the MET algorithm, but, as correctly stated and evaluated, the proposed approach can be used with other methods for learning indices. Perhaps the presentation could be reworked to be more generic.\n\n* I found the presentation of the proof sketch not really enlightening, despite being someone who regularly performs similar analysis. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject