From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees
We introduce BOURBON, a log-structured merge (LSM) tree that utilizes machine learning to provide fast lookups. We base the design and implementation of BOURBON on empirically-grounded principles that we derive through careful analysis of LSM design. BOURBON employs greedy piecewise linear regression to learn key distributions, enabling fast lookup with minimal computation, and applies a cost-benefit strategy to decide when learning will be worthwhile. Through a series of experiments on both synthetic and real-world datasets, we show that BOURBON improves lookup performance by 1.23x-1.78x as compared to state-of-the-art production LSMs.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees
In this paper, we introduce DobLIX, a dual-objective learned index specifically designed for Log-Structured Merge(LSM) tree-based key-value stores. Although traditional learned indexes focus exclusively on optimizing ind…
LearnedKV: Integrating LSM and Learned Index for Superior Performance on Storage
We present LearnedKV, a novel tiered key-value store that seamlessly integrates a Log-Structured Merge (LSM) tree with a Learned Index to achieve superior read and write performance on storage systems. While existing app…
BlockingUpLIF: An Updatable Self-Tuning Learned Index Framework
The emergence of learned indexes has caused a paradigm shift in our perception of indexing by considering indexes as predictive models that estimate keys' positions within a data set, resulting in notable improvements in…
Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis
A growing trend in the database and system communities is to augment conventional index structures, such as B+-trees, with machine learning (ML) models. Among these, error-bounded Piecewise Linear Approximation ($\epsilo…
Automatic Extraction of Verb Paradigms in Regional Languages: the case of the Linguistic Crescent varieties
Language documentation is crucial for endangered varieties all over the world. Verb conjugation is a key aspect of this documentation for Romance varieties such as those spoken in central France, in the area of the Lingu…