We are happy to announce that our paper The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds has been published in the Proceedings of the VLDB Endowment, Volume 13, Issue 8.
The PGM-index is the first learned index that supports predecessor, range queries and updates within provably efficient time and space bounds using orders of magnitude less space than traditional data structures. We have released an open-source implementation on GitHub and created a website for the PGM-index project. Also have a look at our survey on learned indexes.
Cite as: Paolo Ferragina and Giorgio Vinciguerra. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. PVLDB, 13(8): 1162-1175, 2020.
@article{Ferragina:2020pgm,
Author = {Paolo Ferragina and Giorgio Vinciguerra},
Title = {The {PGM-index}: a fully-dynamic compressed learned index with provable worst-case bounds},
Year = {2020},
Volume = {13},
Number = {8},
Pages = {1162--1175},
Doi = {10.14778/3389133.3389135},
Url = {https://pgm.di.unipi.it},
Issn = {2150-8097},
Journal = {{PVLDB}}}