Learned Indexes for a Google-scale Disk-based Database

• URL: http://arxiv.org/abs/2012.12501v1
• Date: Wed, 23 Dec 2020 05:56:45 GMT
• Title: Learned Indexes for a Google-scale Disk-based Database
• Authors: Hussam Abu-Libdeh, Deniz Alt{\i}nb\"uken, Alex Beutel, Ed H. Chi, Lyric Doshi, Tim Kraska, Xiaozhou (Steve) Li, Andy Ly, Christopher Olston
• Abstract summary: We show how a learned index can be integrated in a distributed, disk-based database system: Google's Bigtable. Our results show that integrating learned index significantly improves the end-to-end read latency and throughput for Bigtable.
• Score: 23.93643265060042
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: There is great excitement about learned index structures, but understandable skepticism about the practicality of a new method uprooting decades of research on B-Trees. In this paper, we work to remove some of that uncertainty by demonstrating how a learned index can be integrated in a distributed, disk-based database system: Google's Bigtable. We detail several design decisions we made to integrate learned indexes in Bigtable. Our results show that integrating learned index significantly improves the end-to-end read latency and throughput for Bigtable.

Related papers

• Annotative Indexing [8.684302613224338]
  Annotative indexing is a novel framework that unifies and generalizes traditional inverted indexes, column stores, object stores, and graph databases. Annotative indexing can provide the underlying indexing framework for databases that support knowledge graphs, entity, semi-structured data, and ranked.
  arXiv  Detail & Related papers  (2024-11-09T19:07:58Z)
• 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)
• How to Index Item IDs for Recommendation Foundation Models [49.425959632372425]
  Recommendation foundation model utilizes large language models (LLM) for recommendation by converting recommendation tasks into natural language tasks. To avoid generating excessively long text and hallucinated recommendations, creating LLM-compatible item IDs is essential. We propose four simple yet effective solutions, including sequential indexing, collaborative indexing, semantic (content-based) indexing, and hybrid indexing.
  arXiv  Detail & Related papers  (2023-05-11T05:02:37Z)
• End-to-End Learning to Index and Search in Large Output Spaces [95.16066833532396]
  Extreme multi-label classification (XMC) is a popular framework for solving real-world problems. In this paper, we propose a novel method which relaxes the tree-based index to a specialized weighted graph-based index. ELIAS achieves state-of-the-art performance on several large-scale extreme classification benchmarks with millions of labels.
  arXiv  Detail & Related papers  (2022-10-16T01:34:17Z)
• LSI: A Learned Secondary Index Structure [24.324528705706104]
  We introduce Learned Secondary Index (LSI), a first attempt to use learned indexes for indexing unsorted data. We show that LSI achieves comparable lookup performance to state-of-the-art secondary indexes while being up to 6x more space efficient.
  arXiv  Detail & Related papers  (2022-05-11T20:49:44Z)
• 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)
• 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)
• 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)
• 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)
• 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.