--- res: bibo_abstract: - "The design and implementation of efficient concurrent data structures have\r\nseen significant attention. However, most of this work has focused on\r\nconcurrent data structures providing good \\emph{worst-case} guarantees. In real\r\nworkloads, objects are often accessed at different rates, since access\r\ndistributions may be non-uniform. Efficient distribution-adaptive data\r\nstructures are known in the sequential case, e.g. the splay-trees; however,\r\nthey often are hard to translate efficiently in the concurrent case.\r\n In this paper, we investigate distribution-adaptive concurrent data\r\nstructures and propose a new design called the splay-list. At a high level, the\r\nsplay-list is similar to a standard skip-list, with the key distinction that\r\nthe height of each element adapts dynamically to its access rate: popular\r\nelements ``move up,'' whereas rarely-accessed elements decrease in height. We\r\nshow that the splay-list provides order-optimal amortized complexity bounds for\r\na subset of operations while being amenable to efficient concurrent\r\nimplementation. Experimental results show that the splay-list can leverage\r\ndistribution-adaptivity to improve on the performance of classic concurrent\r\ndesigns, and can outperform the only previously-known distribution-adaptive\r\ndesign in certain settings.@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Vitaly foaf_name: Aksenov, Vitaly foaf_surname: Aksenov - foaf_Person: foaf_givenName: Dan-Adrian foaf_name: Alistarh, Dan-Adrian foaf_surname: Alistarh foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0003-3650-940X - foaf_Person: foaf_givenName: Alexandra foaf_name: Drozdova, Alexandra foaf_surname: Drozdova - foaf_Person: foaf_givenName: Amirkeivan foaf_name: Mohtashami, Amirkeivan foaf_surname: Mohtashami bibo_doi: 10.4230/LIPIcs.DISC.2020.3 bibo_volume: 179 dct_date: 2020^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/1868-8969 - http://id.crossref.org/issn/9783959771689 dct_language: eng dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@ dct_title: 'The splay-list: A distribution-adaptive concurrent skip-list@' ...