CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm

• URL: http://arxiv.org/abs/2103.00858v1
• Date: Mon, 1 Mar 2021 09:20:53 GMT
• Title: CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm
• Authors: Jiaoyi Zhang and Yihan Gao
• Abstract summary: We propose a cache-aware learned index (CARMI) design to improve the efficiency of the Recursive Model Index (RMI) framework. We formulate the problem of finding the optimal design of a learned index as an optimization problem and propose a dynamic programming algorithm for solving it. Experiments show that our index construction strategy can construct indexes with significantly better performance compared to baselines.
• Score: 1.9798034349981157
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learned indexes, which use machine learning models to replace traditional index structures, have shown promising results in recent studies. However, our understanding of this new type of index structure is still at an early stage with many details that need to be carefully examined and improved. In this paper, we propose a cache-aware learned index (CARMI) design to improve the efficiency of the Recursive Model Index (RMI) framework proposed by Kraska et al. and a cost-based construction algorithm to construct the optimal indexes in a wide variety of application scenarios. We formulate the problem of finding the optimal design of a learned index as an optimization problem and propose a dynamic programming algorithm for solving it and a partial greedy step to speed up. Experiments show that our index construction strategy can construct indexes with significantly better performance compared to baselines under various data distribution and workload requirements. Among them, CARMI can obtain an average of 2.52X speedup compared to B-tree, while using only about 0.56X memory space of B-tree on average.

Related papers

• Semi-Parametric Retrieval via Binary Token Index [71.78109794895065]
  Semi-parametric Vocabulary Disentangled Retrieval (SVDR) is a novel semi-parametric retrieval framework. It supports two types of indexes: an embedding-based index for high effectiveness, akin to existing neural retrieval methods; and a binary token index that allows for quick and cost-effective setup, resembling traditional term-based retrieval. It achieves a 3% higher top-1 retrieval accuracy compared to the dense retriever DPR when using an embedding-based index and a 9% higher top-1 accuracy compared to BM25 when using a binary token index.
  arXiv  Detail & Related papers  (2024-05-03T08:34:13Z)
• Flexible Channel Dimensions for Differentiable Architecture Search [50.33956216274694]
  We propose a novel differentiable neural architecture search method with an efficient dynamic channel allocation algorithm. We show that the proposed framework is able to find DNN architectures that are equivalent to previous methods in task accuracy and inference latency.
  arXiv  Detail & Related papers  (2023-06-13T15:21:38Z)
• 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)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Cascaded Fast and Slow Models for Efficient Semantic Code Search [46.53530668938728]
  We propose an efficient and accurate semantic code search framework with cascaded fast and slow models. The proposed cascaded approach is not only efficient and scalable, but also achieves state-of-the-art results.
  arXiv  Detail & Related papers  (2021-10-15T02:23:35Z)
• Micro-architectural Analysis of a Learned Index [0.0]
  ALEX is a tree-based in-memory index structure that consists of a hierarchy of machine learned models. Our results show that ALEX exhibits fewer stalls and a lower cycles-per-instruction value across different workloads. On the other hand, the amount of instructions required to handle out-of-bound inserts in ALEX can increase the instructions needed per request significantly (10X)
  arXiv  Detail & Related papers  (2021-09-17T12:13:06Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  In this paper, we design an NNS algorithm for the Hamming space that has worst-case guarantees essentially matching that of theoretical algorithms. We evaluate the algorithm's ability to optimize for a given dataset both theoretically and practically. Our algorithm has a 1.8x and 2.1x better recall on the worst-performing queries to the MNIST and ImageNet datasets.
  arXiv  Detail & Related papers  (2021-08-11T20:21:30Z)
• iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradients [75.41173109807735]
  Differentiable ARchiTecture Search (DARTS) has recently become the mainstream of neural architecture search (NAS) We tackle the hypergradient computation in DARTS based on the implicit function theorem. We show that the architecture optimisation with the proposed method, named iDARTS, is expected to converge to a stationary point.
  arXiv  Detail & Related papers  (2021-06-21T00:44:11Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)

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.