Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Winblad, Kjell http://www.dagstuhl.de/oasics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-84492
URL:

Faster Concurrent Range Queries with Contention Adapting Search Trees Using Immutable Data

pdf-format:


Abstract

The need for scalable concurrent ordered set data structures with linearizable range query support is increasing due to the rise of multicore computers, data processing platforms and in-memory databases. This paper presents a new concurrent ordered set with linearizable range query support. The new data structure is based on the contention adapting search tree and an immutable data structure. Experimental results show that the new data structure is as much as three times faster compared to related data structures. The data structure scales well due to its ability to adapt the sizes of its immutable parts to the contention level and the sizes of the range queries.

BibTeX - Entry

@InProceedings{winblad:OASIcs:2018:8449,
  author =	{Kjell Winblad},
  title =	{{Faster Concurrent Range Queries with Contention Adapting Search Trees Using Immutable Data}},
  booktitle =	{2017 Imperial College Computing Student Workshop (ICCSW 2017)},
  pages =	{7:1--7:13},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-059-0},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{60},
  editor =	{Fergus Leahy and Juliana Franco},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8449},
  URN =		{urn:nbn:de:0030-drops-84492},
  doi =		{10.4230/OASIcs.ICCSW.2017.7},
  annote =	{Keywords: linearizability, concurrent data structures, treap}
}

Keywords: linearizability, concurrent data structures, treap
Seminar: 2017 Imperial College Computing Student Workshop (ICCSW 2017)
Issue date: 2018
Date of publication: 2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI