Learning-Augmented Skip Lists
<|reference_start|>Learning-Augmented Skip Lists: We study the integration of machine learning advice into the design of skip lists to improve upon traditional data structure design. Given access to a possibly erroneous oracle that outputs estimated fractional frequencies for search queries on a set of items, we construct a skip list that provably provides the optimal expected search time, within nearly a factor of two. In fact, our learning-augmented skip list is still optimal up to a constant factor, even if the oracle is only accurate within a constant factor. We show that if the search queries follow the ubiquitous Zipfian distribution, then the expected search time for an item by our skip list is only a constant, independent of the total number $n$ of items, i.e., $\mathcal{O}(1)$, whereas a traditional skip list will have an expected search time of $\mathcal{O}(\log n)$. We also demonstrate robustness by showing that our data structure achieves an expected search time that is within a constant factor of an oblivious skip list construction even when the predictions are arbitrarily incorrect. Finally, we empirically show that our learning-augmented skip list outperforms traditional skip lists on both synthetic and real-world datasets.<|reference_end|>
@article{fu2024learning-augmented,
    title={Learning-Augmented Skip Lists},
    author={Chunkai Fu, Jung Hoon Seo, Samson Zhou},
    journal={arXiv preprint arXiv:2402.10457},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10457},
    primaryClass={cs.DS cs.LG}
}