Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: strength:
1. The paper is well-organized and the motivation is easy to follow.
2. The idea is easy to understand and interesting.

weakness:
1. 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.
2. 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).
3. 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.
4. 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. 
questions: 1. How does your dynamic \epsilon framework with SOTA \epsilon-bounded learned indexes compare to these works in terms of indexing performance?
2. When the distribution shifts, does the learned \epsilon still fit?
limitations: There is no negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strength:

1. 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.

2. Method: the proposed method have a solid mathematical foundation. The workflow of theoretical analysis makes sense to the reviewer. 

3. 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


questions: The motivation of dynamic $\epsilon$:

An 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$?

The running time analysis:

1. Is there any extra overhead we should pay to enjoy the adaptivity over different $\epsilon$?

2.  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?

Robustness to adaptive queries:

As 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
This 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.
There is an analysis of the prediction error, making some not-so-strong-but-not-weak assumptions about the data distribution.
The 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.
strengths_and_weaknesses: ## Strenghts

* Good idea, and well executed

* Complete experimental evaluation, and convincing.

* Very clear presentation

## Weaknesses

* 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.

* I found the presentation of the proof sketch not really enlightening, despite being someone who regularly performs similar analysis. 
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.
review_title: null

Meta-review: metareview: All of the reviewers recommended acceptance, but the support was lukewarm, with the maximum score being “Weak Accept”. There were concerns about the limited applicability of the proposed method and lack of clarity of some of the arguments in the paper. Although the reviewers appreciated the mathematical foundations and experimental results, the negatives outweighed the positives. 
confidence: Less certain
Decision: Reject