LSI: A Learned Secondary Index Structure

• URL: http://arxiv.org/abs/2205.05769v1
• Date: Wed, 11 May 2022 20:49:44 GMT
• Title: LSI: A Learned Secondary Index Structure
• Authors: Andreas Kipf, Dominik Horn, Pascal Pfeil, Ryan Marcus, Tim Kraska
• Abstract summary: 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.
• Score: 24.324528705706104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learned index structures have been shown to achieve favorable lookup performance and space consumption compared to their traditional counterparts such as B-trees. However, most learned index studies have focused on the primary indexing setting, where the base data is sorted. In this work, we investigate whether learned indexes sustain their advantage in the secondary indexing setting. We introduce Learned Secondary Index (LSI), a first attempt to use learned indexes for indexing unsorted data. LSI works by building a learned index over a permutation vector, which allows binary search to performed on the unsorted base data using random access. We additionally augment LSI with a fingerprint vector to accelerate equality lookups. We show that LSI achieves comparable lookup performance to state-of-the-art secondary indexes while being up to 6x more space efficient.

Related papers

• Differentially Private Learned Indexes [4.290415158471898]
  We address the problem of efficiently answering predicate queries on encrypted databases, those secured by Trusted Execution Environments (TEEs) A common strategy in modern databases to accelerate predicate queries is the use of indexes, which map attribute values (keys) to their corresponding positions in a sorted data array. Unfortunately, indexes cannot be directly applied to encrypted databases due to strong data dependent leakages. We propose leveraging learned indexes, a trending technique that repurposes machine learning models as indexing structures, to build more compact DP indexes.
  arXiv  Detail & Related papers  (2024-10-28T16:04:58Z)
• Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes? [62.57689536630933]
  We provide experimental results on the BEIR dataset using the open-source Lucene search library. Our results provide guidance for today's search practitioner in understanding the design space of dense and sparse retrievers.
  arXiv  Detail & Related papers  (2024-09-10T12:46:23Z)
• 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)
• 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)
• Bridging the Gap Between Indexing and Retrieval for Differentiable Search Index with Query Generation [98.02743096197402]
  Differentiable Search Index (DSI) is an emerging paradigm for information retrieval. We propose a simple yet effective indexing framework for DSI, called DSI-QG. Empirical results on popular mono-lingual and cross-lingual passage retrieval datasets show that DSI-QG significantly outperforms the original DSI model.
  arXiv  Detail & Related papers  (2022-06-21T06:21:23Z)
• 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)
• Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads [29.223401893397714]
  We introduce Tsunami, which achieves up to 6X faster query performance and up to 8X smaller index size than existing learned multi-dimensional indexes.
  arXiv  Detail & Related papers  (2020-06-23T19:25:51Z)

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.