1 Search Results for "Drozdova, Alexandra"

Document
DOI: 10.4230/LIPIcs.DISC.2020.3
The Splay-List: A Distribution-Adaptive Concurrent Skip-List

Authors: Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good 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.
Cite as

Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. The Splay-List: A Distribution-Adaptive Concurrent Skip-List. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aksenov_et_al:LIPIcs.DISC.2020.3,
  author =	{Aksenov, Vitaly and Alistarh, Dan and Drozdova, Alexandra and Mohtashami, Amirkeivan},
  title =	{{The Splay-List: A Distribution-Adaptive Concurrent Skip-List}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.3},
  URN =		{urn:nbn:de:0030-drops-130818},
  doi =		{10.4230/LIPIcs.DISC.2020.3},
  annote =	{Keywords: Data structures, self-adjusting, concurrency}
}
  • Refine by Author
  • 1 Aksenov, Vitaly
  • 1 Alistarh, Dan
  • 1 Drozdova, Alexandra
  • 1 Mohtashami, Amirkeivan

  • Refine by Classification
  • 1 Theory of computation → Concurrent algorithms
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 Data structures
  • 1 concurrency
  • 1 self-adjusting

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact