Learning-Augmented Skip Lists

arXiv:2402.10457v1 Announce Type: cross
Abstract: 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 …

abstract advice arxiv construct cs.ds cs.lg data design integration list lists machine machine learning oracle queries search set study type