Year: 2021

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 . However, existing learned index methods adopt a fixed for all the learned segments, neglecting the diverse characteristics of different data localities. In this paper, we propose a mathematically-grounded learned index framework with dynamic , which is efficient and pluggable to existing learned index methods. We theoretically analyze prediction error bounds that link with data characteristics for an illustrative learned index method. Under the guidance of the derived bounds, we learn how to vary and improve the index performance with 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.

heading: 1 INTRODUCTION
text: Data indexing (Graefe & Kuno, 2011; Wang et al., 2018; Luo & Carey, 2020; Zhou et al., 2020), which stores keys and corresponding payloads with designed structures, supports efficient query operations over data and benefits various data retrieval applications. Recently, Machine Learning (ML) models have been incorporated into the design of index structure, leading to substantial improvements in terms of both storage space and querying efficiency (Kipf et al., 2019; Ferragina & Vinciguerra, 2020a; Mitzenmacher, 2018; Vaidya et al., 2021). The key insight behind this trending topic of “learned index” is that the data to be indexed contain useful distribution information and such information can be utilized by trainable ML models that map the keys to their stored positions. State-of-the-art learned index methods (Galakatos et al., 2019; Kipf et al., 2020; Ferragina & Vinciguerra, 2020b; Ferragina et al., 2020) adopt piece-wise linear segments to approximate the data distribution and introduce an important pre-defined parameter . 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 , various space-time preferences from users can be met. For example, a relatively large can result in a small index size while having large prediction errors, and on the other hand, a relatively small provides with small prediction errors 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., 2020), we present novel analysis about the prediction error bounds of each segment that link 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 -learner module, which learns to predict the impact of on the index performance and adaptively choose a suitable to achieve a better space-time trade-off.
We apply the proposed framework to several state-of-the-art (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 , our dynamic versions achieve significant index performance improvements with better space-time trade-offs. We also conduct various experiments to verify the necessity and effectiveness of the proposed framework, and provide both ablation study and case study to understand how the proposed framework works.

heading: 2 BACKGROUND

heading: 2.1 -BOUNDED LEARNED INDEX
text: Given a dataset D = {(x, y)|x ∈ X , y ∈ Y}, X is the set of keys over a universe U such as reals or integers, and Y is the set of positions where the keys and corresponding payloads are stored. The index such as B+-tree (Abel, 1984) aims to build a compact structure to support efficient query operations over D. Typically, the keys are assumed to be sorted in ascending order to satisfy the key-position monotonicity, i.e., for any two keys, xi > xj iff their positions yi > yj , such that the range query (X ∩ [xlow, xhigh]) can be handled. Recently, learned index methods (Kraska et al., 2018; Li et al., 2019; Tang et al., 2020; Dai et al., 2020; Crotty, 2021) leverage ML models to mine useful distribution information from D, and incorporate such information to boost the index performance. To look up a given key x, the learned index first predicts position ŷ using the learned models, and subsequently finds the stored true position y based on ŷ with a binary search or exponential search. Thus the querying time consists of the inference time of the learned models and the search time in O(log(|ŷ − y|)). By modeling the data distribution information, learned indexes achieve faster query speed than traditional B+-tree index, meanwhile using several orders-of-magnitude smaller storage space (Ding et al., 2020; Galakatos et 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 to provides a worst-case preciseness guarantee and a tunable knob to meet various space-time trade-off preferences. Here we briefly introduce the SOTA -bounded learned index methods that are most closely to our work, and refer to the review chapter of (Ferragina & Vinciguerra, 2020a) for details of other methods. Specifically, 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. (2020) introduce a radix structure to organize the learned segments. Ferragina et al. (2020) adopt a 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 ∈ Z>1. In 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 considering the diversity of different data localities.

heading: 2.2 MEAN EXIT TIME (MET) ALGORITHM
text: 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 (xi − xi−1) is drawn according to a random process {Gi}i∈N, where Gi is a positive independent and identically distributed (i.i.d.) random variable whose mean is µ and variance is σ2. The MET algorithm learns linear segments S = [S1, ..., Si, ..., SN ] in one pass, where Si : y = aix+ bi is the learnable linear segment and N is the total number of learned segments. The learning process is as follows: The current linear segment fixes the slope ai = 1/µ and goes through the first available data point, thus bi is also determined. Then the segment covers as many data points as possible until a data point, say (x′, y′) achieves the prediction error larger than . The violation of triggers a new linear segment, and the data point (x′, y′) will be the first available data point, and the process repeats until no data point is 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 -bounded learned index methods such as FITing-Tree (Galakatos et al., 2019), PGM (Ferragina & Vinciguerra, 2020b) and Radix-Spline (Kipf et al., 2020) learn linear segments in a similar manner while having different mechanisms to determine the parameters of {Si}. Ferragina et al. (2020) reveal the relationship
between and index size performance based on MET. In Section 3.3, we present novel analysis about the impact of on not only the index size, but also the index preciseness and a comprehensive trade-off quantity, which facilitates the proposed dynamic adjustment.

heading: 3 LEARN TO VARY

heading: 3.1 PROBLEM FORMULATION AND MOTIVATION
text: Before introducing the proposed framework, we first formulate the task of learning index from data with guarantee, and provide some discussions about why we need to vary . Given a dataset D to be indexed and an -bounded learned index algorithm A, we aim to learn segments S = [S1, ..., Si..., SN ] as index structure such that the size of S and ∑N i=1 MAE(Di|Si) are both small, where Si is the i-th learned linear segment with the parameter i, MAE is the mean absolute prediction error, and Di ⊂ D is the data whose keys are covered by Si. For the remaining data D \ ⋃ j<iDj , the algorithm A repeatedly checks whether the prediction error of new data point violates the given i, and outputs the learned segment Si that covers Di. When all the is for i ∈ [N ] take the same value, the problem becomes the one that existing learned index methods are dealing with.
Now let’s examine the effect of parameter . To query a specific data point, say (x, y), we first need to find the specific segment S′ that covers x, and then search its true position y based on the estimated one ŷ = S′(x). For the first step, we can find S′ from S in O(log(N)); for the second step, the search of y based on ŷ can be done in O(log(|ŷ − y|)). In summary, we can find the true position of the queried data point in O(log(N) + log(|ŷ − y|)) 1. From here, we can see that the parameter plays an important role to trade off two contradictory performance terms, i.e., the size of the learned index N , and MAE of the whole data MAE(D|S). If we adopt a small , the maximal prediction error constraint is more frequently violated, leading to a large N ; meanwhile, the preciseness of learned index is improved, leading to a small MAE(D|S). On the other hand, with a large , we will get a more compact learned index (i.e., a small N ) with larger prediction errors (i.e., a large MAE(D|S)). Thus these two inversely changed terms jointly impact the querying efficiency.
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 we use piece-wise linear segments to fit the data, and determines the partition and the fitness of the segments. By varying , 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 consider the quantity SegErri that is defined as the total prediction error within a segment Si, i.e., SegErri = ∑ (x,y)∈Di |y − Si(x)|, which is also the product of the number of covered keys Len(Di) and the mean absolute error MAE(Di|Si). Note that a large Len(Di) leads to a small N since |D| = ∑N i=1 Len(Di). From this view, the quantity SegErri internally reflects the space-error trade-off. Later we will show how to leverage this quantity to dynamically adjust .

heading: 3.2 OVERALL FRAMEWORK
text: In practice, it is intractable to directly solve the problem formulated in Section 3.1. With a given i, the one-pass algorithm A determines Si and Di until the error bound i is violated. In other words, it is unknown what the data partition {Di} will be a priori, which makes it impossible to solve the problem by searching among all the possible { i}s and learning index with a set of given { i}. In this paper, we investigate how to efficiently find an approximate solution to this problem via the introduced -learner module. Instead of heuristically adjusting , the -learner learns to predict the impact of on the index structure and adaptively adjusts in a principled way. Meanwhile, the introducing of -learner should not sacrifice the efficiency of the original one-pass learned index algorithms, which is important for real-world practical applications.
These two design considerations establish our dynamic framework as shown in Figure 1. The -learner is based on an estimation function SegErr = f( , µ, σ) that depicts the mathematical relationships among , SegErri and the characteristics µ, σ 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 will internally transform the ̃ into another
1In Appendix C, we link the absolute prediction error and specific searching algorithms in further details.
proxy quantity ˜SegErr, which reflects the expected prediction error for each segment if we set i = ̃. This transformation also links the adjustment of and data characteristics together, which enables the data-dependent adjustment of . Beginning with ̃, the -learner chooses a suitable i according to current data characteristics, then learn a segment Si using A, and finally enhance the -learner with the rewarded ground-truth SegErri of each segment. To make the introduced adjustment efficient, we propose to only sample a small Look-ahead data D′ to estimate the characteristics (i.e., µ and σ) of the following data locality. The learning and adjusting processes are repeatedly conducted and also in an efficient one-pass manner.
Note that the proposed framework provides users the same interface as the ones used by original learned index methods. That is, we add no 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 . The is an intuitive, easy-to-set and method-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 in querying process is O(log(|ŷ − y|)). On the other hand, is easier to estimate than the other quantities such as index size and querying time, which are dependent on specific algorithms, data layouts, implementations and experimental platforms. Our pluggable framework retains the benefits of existing learned index methods, such as the aforementioned usability of and the ability to handle dynamic update case (Galakatos et al., 2019; Ferragina & Vinciguerra, 2020b).
We have seen how determines index performance and how SegErri embeds the space-error tradeoff in Section 3.1. In Section 3.3, we will further theoretically analyze the relationship among , SegErri, and data characteristics µ, σ at different localities. Based on the analysis, we elaborate the details of -learner and the internal transformation between and SegErri in Section 3.4.

heading: 3.3 PREDICTION ERROR ESTIMATION
text: In this section, we will theoretically study the impact of on the prediction error SegErri of each learned segment Si. Specifically, for the MET algorithm, we can prove the following theorem to bound the expectation of SegErri with and the key interval distribution of the data to be indexed. Theorem 1. Given a dataset D to be indexed and an where ∈ Z>1, consider the setting of the MET algorithm (Ferragina et al., 2020), in which key intervals ofD are drawn from a random process consisting of positive i.i.d. random variables with mean µ and variance σ2, and σ/µ. For a learned segment Si and its covered data Di, denote SegErri = ∑ (x,y)∈Di |y − Si(x)|. Then the expectation of SegErri satisfies:√ 1
π
µ σ 2 < E[SegErri] < 2 3
√ 2
π ( 5 3 ) 3 4 ( µ σ )2 3.
This theorem reveals that the prediction error SegErri depends on both and the data characteristics (µ and σ). Recall that CV = σ/µ 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 = µ/σ 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 to achieve precise predictions. On the other hand, when µ/σ 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 SegErri for different learned segments consistent and achieve a better space-error trade-off. This analysis also confirms the motivation of
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 -learner module (Section 3.4), we will take the derived closed-form relationships among SegErri, and data statistic µ/σ into account.
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. 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 a learned segment Si : y = aix+ bi, we can calculate the expectation of SegErri for this segment as:
E[SegErri] = aiE (j∗−1)∑ j=0 |Zj |  = ai ∞∑ n=1 E n−1∑ j=0 |Zj | Pr(j∗ = n), (1) where Zj is the j-th position of a transformed random walk {Zj}j∈N, j∗ = max{j ∈ N| − /ai ≤ Zj ≤ /ai} is the random variable indicating the maximal position when the random walk is within the strip of boundary ± /ai, and the last equality is due to the definition of expectation. Under the MET algorithm setting where ai = 1/µ and σ/µ, we can show that the increments of the transformed random walk {Zj} have zero mean and variance σ2, 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 σ2zj = jσ
2, and thus |Zj | follows the folded normal distribution with expectation E(|Zj |) = √ 2/πσ √ j. Thus Eq. (1) can be written as
1
µ ∞∑ n=1 E n−1∑ j=0 |Zj | Pr(j∗ = n) < 1 µ ∞∑ n=1 n−1∑ j=0 E [|Zj |] Pr(j∗ = n) = σ µ √ 2 π ∞∑ n=1 n−1∑ j=0 √ j Pr(j∗ = n).
Using E[j∗] = µ2
σ2 2 and V ar[j∗] =
2
3
µ4 σ4 4 as derived in (Ferragina et al., 2020), we get E[(j∗)2] =
5
3
µ4 σ4 4. With the inequality ∑n−1 j=0 √ j < 23n √ n and E[X 34 ] ≤ (E[X]) 3 4 , we get the upper bound:
E[SegErri] < 2
3
√ 2
π
σ µ E[(j∗) 3 2 ] ≤ 2 3
√ 2
π
σ
µ
( E[(j∗)2] ) 3 4 = 2
3
√ 2
π ( 5 3 ) 3 4 ( µ σ )2 3.
For the lower bound, applying the triangle inequality into Eq. (1), we can get E[SegErri] > 1 µ ∑∞ n=1 E [|Z|] Pr(j∗ = n), where Z = ∑n−1 j=0 Zj , and Z follows the normal distribution since Zj ∼ N(0, σ2zj). We can prove that |Z| follows the folded normal distribution whose expectation E[|Z|] > σ(n− 1)/ √ π. Thus the lower bound is:
E[SegErri] > σ
µ
√ 1
π ∞∑ n=1 (n− 1) Pr(j∗ = n) = σ µ
√ 1
π E [j∗ − 1] =
√ 1
π ( µ σ 2 − σ µ ).
Since σµ , we can omit the right term √
1/π · σ/µ 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 , µ/σ and SegErri are still applicable to other -bounded methods, and further prove 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 -bounded methods, and how effectively the proposed framework works for them on real-world datasets (Section 4.2).

heading: 3.4 -LEARNER
text: Now given an , we have obtained the closed-form bounds of the SegErr in Theorem 1, and both the upper and lower bounds are in the form of w1(µσ )
w2 w3 , 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:
SegErr = f( , µ, σ) =w1( µ
σ )w2 w3 ,
s.t.
√ 1
π ≤ w1 ≤
2
3
√ 2
π ( 5 3 ) 3 4 , 1 ≤ w2 ≤ 2, 2 ≤ w3 ≤ 3.
(2)
With this learnable estimator, we feed data characteristic µ/σ of the look-ahead data and the transformed ˜SegErr into it and find a suitable ∗ as ( ˜SegErr/w1(µσ ) w2 )1/w3 . We will discuss the
look-ahead data and the transformed ˜SegErr in the following paragraphs. Now let’s discuss the reasons for how this adjustment can achieve better index performance. Actually, the -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 to ∗, 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 µ/σ is large, the local data has clear linearity, and thus we can adjust 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, 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.
Look-ahead Data. To make the training and inference of the -learner light-weight, we propose to look ahead a few data D′ to reflect the characteristics of the following data localities. Specifically, we leverage a small subset D′ ⊂ D \ ⋃ j<iDj to estimate the value µ/σ for the following data.
In practice, we set the size of D′ to be 404 when learning the first segment as initialization, and( 1 (i−1) ∑i−1 j=1 Len(Dj) ) · ρ for the other following segments. Here ρ is a pre-defined parameter indicating the percentage that is relative to the average number of covered keys for learned segments, considering that the distribution of µ/σ can be 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 a coefficient of variance σ/µ ≤ 0.2.
˜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 -learner can choose suitable ∗ to meet users’ preference while achieving better space-error trade-off. Specifically, we make the value of ˜SegErr updatable, and update it to be ˜SegErr = w1(µ̂/σ̂)w2 ̃w3 once a new segment is learned, where µ̂/σ̂ 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 ˜SegErr. As for the optimization of the f( , µ, σ), we 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 to track a few statistics and learn the estimator in an efficient one-pass manner. The overall adjustment algorithm is summarized in Appendix D.

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENTAL SETTINGS
text: Baselines. We apply our framework into several SOTA -bounded learned index methods that use different mechanisms to determine the parameters of segments {Si}. Among them, MET (Ferragina et al., 2020) fixes the segment slope as the reciprocal of the expected key interval. FITing-Tree (Galakatos et al., 2019) and Radix-Spline (Kipf et al., 2020) adopt a 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 (Kraska et al., 2018; Galakatos et al., 2019; Ferragina & Vinciguerra, 2020b; Li et al., 2021). Weblogs and IoT contain about 715M log entries from a university web server and 26M event entries from different IoT 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 · latitude of about 1.8M places. Lognormal is a synthetic dataset whose key intervals follow the lognormal distribution. We generate 20M keys with 40 partitions
having different generation parameters to simulate the varied data characteristics 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 1|D| ∑ (x,y)∈D |y − 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 space-error curve (AUSEC) where the x-axis and y-axis indicate N and MAE respectively. For AUSEC metric, the smaller, the better.

heading: 4.2 OVERALL INDEX PERFORMANCE
text: Space-Error Trade-off Improvements. In Table 1, 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 version while the red curves are for dynamic . 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 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), 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-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.
Querying Time Improvements. Recall that the querying time of each data point is in O(log(N) + log(|y − ŷ|) as we mentioned in Section 3.1, where N and |y − ŷ| are inversely impacted by . To examine whether the performance improvements w.r.t. space-error trade-off (i.e., Table 1) can lead to better querying efficiency in real-world systems, we show the averaged total querying time per
query and the actual learned index size in bytes for two scenarios in Figure 3. We can observe that the dynamic versions indeed gain faster querying speed, since we improve both the term N as well as the term |y − ŷ| 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 can flexibly set the expected ̃ to meet various space-time preferences just as they set in the original learned index methods.
Index Building Cost. Comparing with the original learned index methods that adopt a fixed , our framework introduces extra computation to dynamically adjust 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 as the original methods (both inO(|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-world applications.

heading: 4.3 ABLATION STUDY OF DYNAMIC
text: To gain further insights about how the proposed dynamic framework works, we compare the proposed one with three dynamic variants: (1) Random 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( ) = θ1 θ2 where θ1 and θ2 are trainable parameters; (3) Least Square Learner differs our framework with an optimal (but very costly) strategy to learn f( , µ, σ) with the least square regression.
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 framework, showing the necessity and effectiveness of learning the impact of . (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 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, it has higher computational complexity and pays the cost of much larger building times, e.g., 14× and 50× 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.

heading: 4.4 THEORETICAL RESULTS VALIDATION
text: We study the impact of on SegErri for the MET algorithm in Theorem 1, where the derivations are based on the setting of the slope condition ai = 1/µ. To confirm that the proposed framework also works well with other -bounded learned index methods, we analyze the learned slopes of other -bounded methods in Appendix. In summary, we prove that for a segment Si : y = aix+ bi whose
0 1 2 3 4 1/µi ×103
0
1
2
3
4
a i
×103 Map Dataset ai = 1/µi
FITing-Tree RadixSpline PGM
Figure 4: Learned slopes. 100 200 300 400
0
5
10
15
20
25
30
35
40
45
L o g (S
e g E
rr )
Lognormal µ = 1 σ = 0.5 MET Upper Bound
MET MET Lower Bound
PGM RadixSpline FITing-Tree
100 200 300 400
0
5
10
15
20
25
30
35
40
L o g (S
e g E
rr )
Lognormal µ = 1 σ = 1 MET Upper Bound
MET MET Lower Bound
PGM RadixSpline FITing-Tree
Figure 5: Illustration of the derived bounds.
covered data is Di and the expected key interval of Di is µi, then ai concentrates on 1/µi within 2 /(E[Len(Di)]− 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 ai = 1/µi, showing the close connections among these methods and confirming that the proposed framework can work well with other -bounded learned index methods.
We further compare the theoretical bounds with the actual SegErri 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 SegErri within the derived bounds, verifying the correctness of the Theorem 1. Besides, the other -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 -learner also works well with them.
4.5 CASE STUDY
We visualize the partial learned segments for FITing-Tree with fixed and dynamic on IoT dataset in Figure 6, where the N and∑ SegErri indicates the number of learned segments and the total prediction error for the shown segments respectively. The −−→ µ/σ indicates the characteristics of covered data {Di}. We can see that our dynamic framework helps the learned index gain both smaller space (7 v.s. 4) and smaller total prediction errors (48017 v.s. 29854). Note that s within −→ i are diverse due to the diverse linearity of different data localities: For the data whose positions are within about [30000, 30600] and [34700, 35000], the proposed framework chooses large s as their µ/σs 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 µ/σs, and thus the proposed framework adjusts as 19 and 10 that are smaller than 32 to achieve better precision. These experimental observations are consistent with our analysis in the paragraph under Eq. (2),
and clearly confirm that the proposed framework adaptively adjusts based on data characteristics.

heading: 5 CONCLUSIONS
text: 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 SegErri for each learned segment, which is 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 framework that leverages an -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 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. 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 are used while still requiring space-error trade-off, such as similarity search and lossy compression for time series data (Chen et al., 2007; Xie et al., 2014; Buragohain et al., 2007; O’Rourke, 1981).
REPRODUCIBILITY STATEMENT
For the Theorem 1 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 E. More detailed description of the adopted datasets is included in Appendix F. To facilitate the reproducibitlity, we share downloadable source codes and IPython notebooks, and attach binary files of the public experimental datasets in the anonymous link 2.

heading: A PROOF OF THEOREM 1
text: Given a learned segment Si : y = aix+ bi, denote ci as the stored position of the last covered data for the (i− 1)-th segment (c1 = 0 for the first segment). We can write the expectation of SegErri for the segment Si as the following form:
E[SegErri] = E (j∗−1)∑ j=0 |aiXj + bi − (j + ci + 1)|  , where j∗ indicates the length of the segment, and Xj indicates the j-th key covered by the segment Si. As studied in Ferragina et al. (2020), the linear-approximation problem with guarantee can be modeled as random walk processes. Specifically, Xj = X0 + ∑j k=0Gk (for j ∈ Z>0) where Gk is the key increment variable whose mean and variance is µ and σ2 respectively. Denote the Zj = Xj − j/ai + (bi − ci − 1)/ai as the j-th position of the transformed random walk {Zj}j∈N, and j∗ = max{j ∈ N| − /ai ≤ Zj ≤ /ai} as the random variable indicating the maximal position when the random walk is within the strip of boundary ± /ai. The expectation can be rewritten as
E (j∗−1)∑ j=0 |aiXj − j + (bi − ci − 1)|  =aiE (j∗−1)∑ j=0 |Zj |  =ai
∞∑ n=1 E n−1∑ j=0 |Zj | Pr(j∗ = n). (3)
The last equality in Eq. (3) is due to the definition of expectation. Following the MET algorithm that the Si goes through the point (X0, Y0 = ci + 1), we get bi = −aiX0 + ci + 1 and we can rewrite Zj as the following form:
Z0 = 0, Zj j>0 = Xj −X0 − j/ai = j∑ k=1 Gk − j/ai = j∑ k=1 (Gk − 1/ai) = j∑ k=1 (Wk),
where Wk is the walk increment variable of Zj , E[Wk] = µ − 1/ai and V ar[Wk] = σ2. Under the MET algorithm setting where ai = 1/µ and ε σ/µ, the transformed random walk {Zj} has increments with zero mean and variance σ2, and many steps are necessary to reach the random walk boundary. With the Central Limit Theorem, we can assume that Zj follows the normal distribution with mean µzj and variance σ2zj , and thus |Zj | follows the folded normal distribution:
Zj ∼ N ( (µ− 1/ai)j, jσ2 ) ,
E(|Zj |) = µzj [1− 2Φ(− µzj/σzj)] + σzj √ 2/π exp(−µ2zj/2σ2zj),
where Φ is the normal cumulative distribution function. For the MET algorithm, ai = 1/µ and thus the µzj = 0, σzj = σ √ j, and E(|Zj |) = √ 2/πσ √ j. Then the Eq. (3) can be written as
1
µ ∞∑ n=1 E n−1∑ j=0 |Zj | Pr(j∗ = n) < 1 µ ∞∑ n=1 n−1∑ j=0 E [|Zj |] Pr(j∗ = n)
= σ
µ
√ 2
π ∞∑ n=1 n−1∑ j=0 √ j Pr(j∗ = n).
(4)
For the inner sum term in Eq. (4), we have ( ∑n−1 j=0 √ j) < 23n √ n since
n−1∑ j=0 √ j < n−1∑ j=0 √ j + √ n 2 < ∫ n 0 √ x dx = 2 3 n √ n,
then the result in Eq. (4) becomes
E[SegErri] < 2
3
√ 2
π
σ
µ ∞∑ n=1 n √ nPr(j∗ = n)
= 2
3
√ 2
π
σ µ E[(j∗) 3 2 ] = 2 3
√ 2
π
σ µ E [( (j∗)2 ) 3 4 ] ≤ 2 3 √ 2 π σ µ ( E[(j∗)2] ) 3 4 ,
where the last inequality holds due to the Jensen inequality E[X 34 ] ≤ (E[X]) 3 4 . Using E[j∗] =
µ2 σ2 2
and V ar[j∗] = 2
3
µ4 σ4 4 derived in MET algorithm Ferragina et al. (2020), we get E[(j∗)2] = 5 3 µ4 σ4 4,
which yields the following upper bound:
E[SegErri] < 2
3
√ 2
π ( 5 3 ) 3 4 ( µ σ )2 3.
For the lower bound, applying the triangle inequality into the Eq. (3), we have
1
µ ∞∑ n=1 E n−1∑ j=0 |Zj | Pr(j∗ = n) > 1 µ ∞∑ n=1 E | n−1∑ j=0 Zj | Pr(j∗ = n) = 1
µ ∞∑ n=1 E [|Z|] Pr(j∗ = n),
(5)
where Z = ∑n−1 j=0 Zj . Since Zj ∼ N(0, σ2zj), the Z follows the normal distribution:
Z ∼ N ( µZ = 0, σ 2 Z = n−1∑ j=0 σ2zj + n−1∑ j=0 n−1∑ k=0,k 6=j rjkσzjσzk ) ,
where rjk is the correlation between Zj and Zk. Since µZ = 0, the |Z| follows the folded normal distribution with E[|Z|] = σZ √ 2/π. Since the random walk {Zj} is a process with i.i.d. increments, the correlation rjk ≥ 0. With σzj = σ √ j > 0 and rjk ≥ 0, we have
E[|Z|] > √ 2
π n−1∑ j=0 σzj > σ √ n(n− 1)/π > σ(n− 1)√ π ,
and the result in Eq. (5) becomes:
E[SegErri] > 1
µ ∞∑ n=1 E | n−1∑ j=0 Zj | Pr(j∗ = n) > σ
µ
√ 1
π ∞∑ n=1 (n− 1) Pr(j∗ = n)
= σ
µ
√ 1
π E [j∗ − 1] =
√ 1
π ( µ σ 2 − σ µ ).
Since σµ , we can omit the right term √ 1 π σ µ and finish the proof.

heading: B LEARNED SLOPES OF OTHER -BOUNDED METHODS
text: As shown in Theorem 1, we have known how impacts the SegErri of each segment learned by the MET algorithm, where the theoretical derivations largely rely on the slope condition ai = 1/µ. Here we prove that for other -bounded methods, the learned slope of each segment (i.e., ai of Si) concentrates on the reciprocal of the expected key interval as shown in the following Theorem.
Theorem 2. Given an ∈ Z>1 and an -bounded learned index algorithm A. For a linear segment Si : y = aix + bi learned by A, denote its covered data and the number of covered keys as Di and Len(Di) respectively. Assuming the expected key interval of Di is µi, the learned slope ai concentrates on ã = 1/µi with bounded relative difference:
(1− 2 E[Len(Di)]− 1 )ã ≤ E[ai] ≤ (1 + 2 E[Len(Di)]− 1 )ã.
Proof. For the learned linear segment Si, denote its first predicted position and last predicted position as y′0 and y ′ n respectively, we have its slope ai = y′n−y ′ 0 xn−x0 . Notice that y0 − ≤ y ′ 0 ≤ y0 + and yn − ≤ y′n ≤ yn + due to the guarantee, we have yn − y0 − 2 ≤ y′n − y′0 ≤ yn − y0 + 2 and the expectation of ai can be written as
E[ yn − y0 + 2 xn − x0 ] ≤ E[ai] = y′n − y′0 xn − x0 ≤ E[yn − y0 + 2 xn − x0 ].
Note that for any learned segment Si whose first covered data is (x0, y0) and last covered data is (xn, yn), we have E[xn−x0yn−y0 ] = µi and thus the inequalities become
1 µ − E[ 2 xn − x0 ] ≤ E[ai] ≤ 1 µ + E[ 2 xn − x0 ].
Since ã = 1/µi and E[xn − x0] = (E[Len(Di)]− 1)µi, we finish the proof.
The Theorem 2 shows that the relative deviations between learned slope ai and ã are within 2 /(E[Len(Di)] − 1). For the MET and PGM learned index methods, we have the following corollary that depicts preciser deviations without the expectation term E[Len(Di)]. Corollary 2.1. For the MET method Ferragina et al. (2020) and the optimal -bounded linear approximation method that learns the largest segment length used in PGM Ferragina & Vinciguerra (2020b), the slope relative differences are at O(1/ ).
Proof. We note that the segment length of a learned segment is at O( 2) for the MET algorithm, which is proved in the Theorem 1 of Ferragina et al. (2020). Since PGM achieves the largest learned segment length that is larger than the one of the MET algorithm, we finish the proof.

heading: C CONNECTING PREDICTION ERROR WITH SEARCHING STRATEGY
text: As we mentioned in Section 3.1, we can find the true position of the queried data point in O(log(N)+ log(|ŷ − y|)) where N is the number of learned segments and |ŷ − y| is the absolute prediction error. A binary search or exponential search can be used to finds the stored true position y based on ŷ. It is worth noting out that the searching cost in terms of searching range |ŷ − y| of binary search strategy corresponds to the maximum absolute prediction error , whereas the one of exponential search corresponds to the mean absolute prediction error (MAE). In this paper, we decouple the quantity SegErri as the product of Len(Di) and MAE(Di|Si) in the derivation of Theorem 1. Built upon the theoretical analysis, we adopt exponential search in experiments to better leverage the predictive models.
To clarify, let’s consider a learned segment Si with its covered dataDi. Denote the absolute prediction error of k-th data point covered by this segment as |ŷk − yk|, the maximum absolute prediction error as i where |ŷk − yk| ≤ i for all k ∈ [len(Di)].
• The binary search is conducted within the searching range [ŷk ± i] for each data point 3, thus the mean search range is ∑len(Di) k=1 1 len(Di)2 i = O( i), which is independent of the
preciseness of the learned segment and an upper bound of MAE(Di|Si). 3The lower bound and upper bounds of searching ranges should be constricted to 0 and len(Di) respectively. For brevity, we omit the corner cases when comparing these two searching strategies as they both need to handle the out-of-bounds scenario.
• The exponential search first finds the searching range where the queried data may present by centering around the ŷ, repeatedly doubling the range [ŷ ± 2q] where the integer q grows from 0, and comparing the queried data with the data points at positions ŷ±2q . After finding the specific range such that a qk satisfies 2log(qk)−1 ≤ |ŷk − yk| ≤ 2dlog(qk)e for the k-th data, an binary search is conducted to find the exact location. In this way, the mean search range is ∑len(Di) k=1 1 len(Di) (2 dlog(qk)e+1) = O ( MAE(Di|Si) ) , which can be much smaller
than O( i) especially for strong predictive models and the datasets having clear linearity.

heading: D THE ALGORITHM OF DYNAMIC ADJUSTMENT
text: Algorithm Dynamic Adjustment with Pluggable Learner Input: D: Data to be indexed, A: Learned index algorithm, ̃: Expected , ρ: Length percentage
for look-ahead data Output: S: Learned segments with varied s
1: initial parameters w1,2,3 of the learned function: f( , µ, σ) = w1(µσ ) w2 ̃w3 2: initial mean length of learned segments so far: Len(DS)← 404 3: S← ∅, (µ̂/σ̂)← 0 4: repeat 5: (µ/σ)← lookahead(D, Len(DS) · ρ) /* get data statistic */
6: ∗ ← ( ˜SegErr/w1(µσ ) w2 )1/w3
/* adjust based on the learner */
7: [Si,Di]← A(D, ∗) /* learn new segment Si using adjusted ∗ */ 8: S← S ∪ Si 9: D ← D \ Di, DS ← DS ∪ Di
10: Len(DS)← running-mean ( Len(DS), Len(Di) ) /* online update Len(DS) */
11: (µ̂/σ̂)← running-mean ( (µ̂/σ̂), (µ/σ) ) 12: w1,2,3 ← optimize(f, Si, SegErri) /* train the learner with ground-truth */ 13: ˜SegErr ← w1(µ̂/σ̂)w2 ̃w3 14: until D = ∅
In Section 3.4, we provide detailed description about the initialization and adjustment sub-procedures. The lookahead() and optimize() 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. FITing-Tree (Galakatos et al., 2019) adopts a greedy shrinking cone algorithm and the learned segments are organized with a B+-tree. Here we use the stx::btree (v0.9) implementation (Bingmann, 2013) and set the filling factors of inner nodes and leaf nodes as 100%, i.e., we adopt the full-paged filling manner. Radix-Spline (Kipf et al., 2020) adopts a greedy spline interpolating algorithm to learn spline points, and the learned spline segments are organized with a flat radix table. We set the number of radix bits as r = 16 for the Radix-Spline method, which means that the leveraged radix table contains 216 entries. PGM (Ferragina & Vinciguerra, 2020b) adopts a convex hull based algorithm to achieve the minimum number of learned segments, and the segments can be organized with the help of binary search, CSS-Tree (Rao & Ross, 1999) and recursive structure. Here we implement the recursive version since it beats the other two variants in terms of indexing performance.
We then describe a few additional details of the proposed framework in terms of the -learner initialization and the hyper-parameter setting. For the w1,2,3 of the -learner shown in the Eq. (2), at the beginning, we learn the first five segments with the sequence [ 14 ̃, 1 2 ̃, ̃, 2̃, 4̃], then track their rewarded SegErri and update the parameters w1,2,3 using least square regression. We empirically
found that this light-weight initialization leads to better index performance compared to the versions with random parameter initialization, and it benefits the exploration of diverse ∗, i.e., leading to the larger variance of the dynamic sequence [ 1, . . . , i, . . . , N ]. As for the hyper-parameter ρ (described in the Section 3.4), we conduct grid search over ρ ∈ [0.1, 0.4, 0.7, 1.0] on Map an IoT datasets. We found that all the ρs achieve better space-error trade-off (i.e., smaller AUSEC results) than the fixed versions. Since the setting ρ = 0.4 achieves averagely best results on the two datasets, we set ρ to be 0.4 for the other datasets.

heading: F DATASET DETAILS
text: Our framework is verified on several widely adopted datasets having different data scales and distributions. Weblogs Kraska et al. (2018); Galakatos et al. (2019); Ferragina & Vinciguerra (2020b) contains about 715M log entries for the requests to 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 IoT sensors in a building and the keys are recording timestamps. Map dataset Kraska et al. (2018); 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 OpenStreetMap 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: ln(Gi) ∼ N (µlg, σ2lg). To simulate the varied data characteristics among different localities. We generate 20M keys with 40 partitions by setting µlg = 1 and setting σlg with a random number within [0.1, 1] for each partition.
We normalize the positions of stored data into the range [0, 1], and thus the key-position distribution can be modeled as Cumulative Distribution Function (CDF). We plot the CDFs and zoomed-in CDFs of experimental datasets in Figure 7 and Figure 8 respectively, which intuitively illustrate the diversity of the adopted datasets.

heading: G ADDITIONAL EXPERIMENTAL RESULTS
text: 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 tradeoff curves in Figure 9 and querying time results in Figure 10. Recall that the 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 a constant factor, e.g., the size of a segment can be 128bit if it consists of two
double-precision float parameters (slope and intercept); (2) the querying operation can be done in O(log(N) + log(|y − ŷ|) as we mentioned in Section 3.1, thus a better N -MAE trade-off indicates a better querying efficiency. From these figures, we can see that the dynamic versions of all the baseline methods achieve better space-error trade-off and better querying efficiency, verifying the effectiveness and the wide applicability of the proposed framework.
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 FITing-Tree method. Here we demonstrate the AUSEC relative changes for the Radix-Spline method with the same three variants in Table 4 and similar conclusions can be drawn.
Theoretical Validation. In Section 4.4, we show that all the learned index baseline methods learn similar segment slopes on the Map dataset. Here we illustrate the learned slope results on the IoT, Weblogs and Lognormal datasets in Figure 11, which supports the Theorem 2 that the learned segment slopes concentrate on the 1/µi with a bounded relative difference.
Besides, for the comparison between the theoretical bounds and the actual SegErri 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 SegErri within the bounds, verifying the correctness of the Theorem 1 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 SegErri, and µ/σ, and hence the -learner can effectively learn the estimator and adaptively choose suitable .

Review summaries:
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.    The 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.  An 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.

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.