Abstract
Targeting in-memory one-dimensional search keys, we proposea novel DIstribution-driven Learned Index tree (DILI), where aconcise and computation-efficient linear regression model is usedfor each node. An internal node’s key range is equally divided by itschild nodes such that a key search enjoys perfect model predictionaccuracy to find the relevant leaf node. A leaf node uses machine learning models to generate searchable data layout and thus accurately predicts the data record position for a key. To construct DILI, we first build a bottom-up tree with linear regression models according to global and local key distributions. Using the bottom-up tree, we build DILI in a top-down manner, individualizing the fanouts for internal nodes according to local distributions. DILI strikes a good balance between the number of leaf nodes and the height of the tree, two critical factors of key search time. Moreover, wedesign flexible algorithms for DILI to efficiently insert and delete keys and automatically adjust the tree structure when necessary. Extensive experimental results show that DILI outperforms the state-of-the-art alternatives on different kinds of workloads.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Proceedings of the VLDB Endowment |
Vol/bind | 16 |
Udgave nummer | 9 |
Sider (fra-til) | 2212-2224 |
Antal sider | 13 |
ISSN | 2150-8097 |
DOI | |
Status | Udgivet - 2023 |
Begivenhed | 49th International Conference on Very Large Data Bases, VLDB 2023 - Vancouver, Canada Varighed: 28 aug. 2023 → 1 sep. 2023 |
Konference
Konference | 49th International Conference on Very Large Data Bases, VLDB 2023 |
---|---|
Land/Område | Canada |
By | Vancouver |
Periode | 28/08/2023 → 01/09/2023 |