DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees

• URL: http://arxiv.org/abs/2502.05369v1
• Date: Fri, 07 Feb 2025 22:48:14 GMT
• Title: DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees
• Authors: Alireza Heidari, Amirhossein Ahmadi, Wei Zhang,
• Abstract summary: DobLIX is a dual-objective learned index specifically designed for Log-Structured Merge(LSM) tree-based key-value stores. We show that DobLIX reduces indexing overhead and improves throughput by 1.19 to 2.21 times compared to state-of-the-art methods within RocksDB.
• Score: 4.077820670802213
• License:
• Abstract: 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 index lookups, they often overlook the impact of data access from storage, resulting in performance bottlenecks. DobLIX addresses this by incorporating a second objective, data access optimization, into the learned index training process. This dual-objective approach ensures that both index lookup efficiency and data access costs are minimized, leading to significant improvements in read performance while maintaining write efficiency in real-world LSM-tree systems. Additionally, DobLIX features a reinforcement learning agent that dynamically tunes the system parameters, allowing it to adapt to varying workloads in real-time. Experimental results using real-world datasets demonstrate that DobLIX reduces indexing overhead and improves throughput by 1.19 to 2.21 times compared to state-of-the-art methods within RocksDB, a widely used LSM-tree-based storage engine.

Related papers

• Clear Minds Think Alike: What Makes LLM Fine-tuning Robust? A Study of Token Perplexity [61.48338027901318]
  We show that fine-tuning with LLM-generated data improves target task performance and reduces out-of-domain degradation. This is the first mechanistic explanation for the superior OOD robustness conferred by LLM-generated training data.
  arXiv  Detail & Related papers  (2025-01-24T08:18:56Z)
• Efficient $k$-NN Search in IoT Data: Overlap Optimization in Tree-Based Indexing Structures [0.6990493129893112]
  The proliferation of interconnected devices in the Internet of Things (IoT) has led to an exponential increase in data. Efficient retrieval of this heterogeneous data demands a robust indexing mechanism for effective organization. We propose three innovatives designed to quantify and strategically reduce data space partition overlap.
  arXiv  Detail & Related papers  (2024-08-28T16:16:55Z)
• LearnedKV: Integrating LSM and Learned Index for Superior Performance on SSD [0.6774462529828165]
  We introduce LearnedKV, a novel tiered key-value store that seamlessly integrates a Log-Structured Merge (LSM) tree with a Learned Index. Our results show that LearnedKV outperforms state-of-the-art solutions by up to 1.32x in read requests and 1.31x in write performance.
  arXiv  Detail & Related papers  (2024-06-27T05:08:09Z)
• Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoning [53.241569810013836]
  We propose a novel framework that utilizes large language models (LLMs) to identify effective feature generation rules. We use decision trees to convey this reasoning information, as they can be easily represented in natural language. OCTree consistently enhances the performance of various prediction models across diverse benchmarks.
  arXiv  Detail & Related papers  (2024-06-12T08:31:34Z)
• Bidirectional Trained Tree-Structured Decoder for Handwritten Mathematical Expression Recognition [51.66383337087724]
  The Handwritten Mathematical Expression Recognition (HMER) task is a critical branch in the field of OCR. Recent studies have demonstrated that incorporating bidirectional context information significantly improves the performance of HMER models. We propose the Mirror-Flipped Symbol Layout Tree (MF-SLT) and Bidirectional Asynchronous Training (BAT) structure.
  arXiv  Detail & Related papers  (2023-12-31T09:24:21Z)
• Efficient Architecture Search via Bi-level Data Pruning [70.29970746807882]
  This work pioneers an exploration into the critical role of dataset characteristics for DARTS bi-level optimization. We introduce a new progressive data pruning strategy that utilizes supernet prediction dynamics as the metric. Comprehensive evaluations on the NAS-Bench-201 search space, DARTS search space, and MobileNet-like search space validate that BDP reduces search costs by over 50%.
  arXiv  Detail & Related papers  (2023-12-21T02:48:44Z)
• Constructing Tree-based Index for Efficient and Effective Dense Retrieval [26.706985694158384]
  JTR stands for Joint optimization of TRee-based index and query encoding. We design a new unified contrastive learning loss to train tree-based index and query encoder in an end-to-end manner. Experimental results show that JTR achieves better retrieval performance while retaining high system efficiency.
  arXiv  Detail & Related papers  (2023-04-24T09:25:39Z)
• A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
  LIMS is proposed to use data clustering and pivot-based data transformation techniques to build learned indexes. Machine learning models are developed to approximate the position of each data record on the disk. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of LIMS compared with traditional indexes.
  arXiv  Detail & Related papers  (2022-04-21T11:24:55Z)
• A Pluggable Learned Index Method via Sampling and Gap Insertion [48.900186573181735]
  Database indexes facilitate data retrieval and benefit broad applications in real-world systems. Recently, a new family of index, named learned index, is proposed to learn hidden yet useful data distribution. We study two general and pluggable techniques to enhance the learning efficiency and learning effectiveness for learned indexes.
  arXiv  Detail & Related papers  (2021-01-04T07:17:23Z)
• COAX: Correlation-Aware Indexing on Multidimensional Data with Soft Functional Dependencies [3.670422696827525]
  We present COAX, a learned index for multidimensional data that learns the correlations between attributes of the dataset. We show experimentally that by predicting correlated attributes in the data, we can improve the query execution time and reduce the memory overhead of the index.
  arXiv  Detail & Related papers  (2020-06-29T21:22:15Z)
• RadixSpline: A Single-Pass Learned Index [84.84747738666263]
  We introduce RadixSpline (RS), a learned index that can be built in a single pass over the data. RS achieves competitive results on all datasets, despite the fact that it only has two parameters.
  arXiv  Detail & Related papers  (2020-04-30T01:56:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.