RadixSpline: A single-pass learned index

Andreas Kipf, Ryan Marcus, Alexander Van Renen, Mihail Stoian, Alfons Kemper, Tim Kraska, Thomas Neumann

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

65 Scopus citations

Abstract

Recent research has shown that learned models can outperform state-of-the-art index structures in size and lookup performance. While this is a very promising result, existing learned structures are often cumbersome to implement and are slow to build. In fact, most approaches that we are aware of require multiple training passes over the data. We introduce RadixSpline (RS), a learned index that can be built in a single pass over the data and is competitive with state-of-the-art learned index models, like RMI, in size and lookup performance. We evaluate RS using the SOSD benchmark and show that it achieves competitive results on all datasets, despite the fact that it only has two parameters.

Original languageEnglish
Title of host publicationProceedings of the 3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM 2020
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450380294
DOIs
StatePublished - 14 Jun 2020
Externally publishedYes
Event3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM 2020 - Portland, United States
Duration: 19 Jun 2020 → …

Publication series

NameProceedings of the 3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM 2020

Conference

Conference3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM 2020
Country/TerritoryUnited States
CityPortland
Period19/06/20 → …

Fingerprint

Dive into the research topics of 'RadixSpline: A single-pass learned index'. Together they form a unique fingerprint.

Cite this