RadixSpline: A Single-Pass Learned Index

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 req...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-05
Main Authors: Kipf, Andreas, Ryan, Marcus, Alexander van Renen, Stoian, Mihail, Kemper, Alfons, Kraska, Tim, Neumann, Thomas
Format: Article
Language:English
Subjects:
Performance evaluation
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422