RadixSpline: a single-pass learned index
© 2020 ACM. 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...
Main Authors: | , , , , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
ACM
2022
|
Online Access: | https://hdl.handle.net/1721.1/132294.2 |
_version_ | 1811075767882219520 |
---|---|
author | Kipf, Andreas Marcus, Ryan van Renen, Alexander Stoian, Mihail Kemper, Alfons Kraska, Tim Neumann, Thomas |
author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kipf, Andreas Marcus, Ryan van Renen, Alexander Stoian, Mihail Kemper, Alfons Kraska, Tim Neumann, Thomas |
author_sort | Kipf, Andreas |
collection | MIT |
description | © 2020 ACM. 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. |
first_indexed | 2024-09-23T10:11:34Z |
format | Article |
id | mit-1721.1/132294.2 |
institution | Massachusetts Institute of Technology |
language | English |
last_indexed | 2024-09-23T10:11:34Z |
publishDate | 2022 |
publisher | ACM |
record_format | dspace |
spelling | mit-1721.1/132294.22022-08-19T20:03:02Z RadixSpline: a single-pass learned index Kipf, Andreas Marcus, Ryan van Renen, Alexander Stoian, Mihail Kemper, Alfons Kraska, Tim Neumann, Thomas Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 2020 ACM. 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. 2022-07-18T14:38:09Z 2021-09-20T18:21:43Z 2022-07-18T14:38:09Z 2020 2021-01-11T18:20:43Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/132294.2 en 10.1145/3401071.3401659 Proceedings of the 3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM 2020 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/octet-stream ACM arXiv |
spellingShingle | Kipf, Andreas Marcus, Ryan van Renen, Alexander Stoian, Mihail Kemper, Alfons Kraska, Tim Neumann, Thomas RadixSpline: a single-pass learned index |
title | RadixSpline: a single-pass learned index |
title_full | RadixSpline: a single-pass learned index |
title_fullStr | RadixSpline: a single-pass learned index |
title_full_unstemmed | RadixSpline: a single-pass learned index |
title_short | RadixSpline: a single-pass learned index |
title_sort | radixspline a single pass learned index |
url | https://hdl.handle.net/1721.1/132294.2 |
work_keys_str_mv | AT kipfandreas radixsplineasinglepasslearnedindex AT marcusryan radixsplineasinglepasslearnedindex AT vanrenenalexander radixsplineasinglepasslearnedindex AT stoianmihail radixsplineasinglepasslearnedindex AT kemperalfons radixsplineasinglepasslearnedindex AT kraskatim radixsplineasinglepasslearnedindex AT neumannthomas radixsplineasinglepasslearnedindex |