The splay-list: A distribution-adaptive concurrent skip-list
V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, ArXiv (n.d.).
Download (ext.)
Preprint
| Submitted
| English
Author
Aksenov, Vitaly;
Alistarh, Dan-AdrianIST Austria;
Drozdova, Alexandra;
Mohtashami, Amirkeivan
Department
Abstract
The design and implementation of efficient concurrent data structures have
seen significant attention. However, most of this work has focused on
concurrent data structures providing good \emph{worst-case} guarantees. In real
workloads, objects are often accessed at different rates, since access
distributions may be non-uniform. Efficient distribution-adaptive data
structures are known in the sequential case, e.g. the splay-trees; however,
they often are hard to translate efficiently in the concurrent case.
In this paper, we investigate distribution-adaptive concurrent data
structures and propose a new design called the splay-list. At a high level, the
splay-list is similar to a standard skip-list, with the key distinction that
the height of each element adapts dynamically to its access rate: popular
elements ``move up,'' whereas rarely-accessed elements decrease in height. We
show that the splay-list provides order-optimal amortized complexity bounds for
a subset of operations while being amenable to efficient concurrent
implementation. Experimental results show that the splay-list can leverage
distribution-adaptivity to improve on the performance of classic concurrent
designs, and can outperform the only previously-known distribution-adaptive
design in certain settings.
Publishing Year
Date Published
2020-08-03
Journal Title
arXiv
Article Number
2008.01009
IST-REx-ID
Cite this
Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. arXiv.
Aksenov, V., Alistarh, D.-A., Drozdova, A., & Mohtashami, A. (n.d.). The splay-list: A distribution-adaptive concurrent skip-list. arXiv.
Aksenov, Vitaly, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” ArXiv, n.d.
V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” arXiv. .
Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. arXiv, 2008.01009.
Aksenov, Vitaly, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” ArXiv, 2008.01009.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level

Export
Marked PublicationsOpen Data IST Research Explorer
Sources
arXiv 2008.01009