---
_id: '14485'
abstract:
- lang: eng
  text: "Batching is a technique that stores multiple keys/values in each node of
    a data structure. In sequential search data structures, batching reduces latency
    by reducing the number of cache misses and shortening the chain of pointers to
    dereference. Applying batching to concurrent data structures is challenging, because
    it is difficult to maintain the search property and keep contention low in the
    presence of batching.\r\nIn this paper, we present a general methodology for leveraging
    batching in concurrent search data structures, called BatchBoost. BatchBoost builds
    a search data structure from distinct \"data\" and \"index\" layers. The data
    layer’s purpose is to store a batch of key/value pairs in each of its nodes. The
    index layer uses an unmodified concurrent search data structure to route operations
    to a position in the data layer that is \"close\" to where the corresponding key
    should exist. The requirements on the index and data layers are low: with minimal
    effort, we were able to compose three highly scalable concurrent search data structures
    based on three original data structures as the index layers with a batched version
    of the Lazy List as the data layer. The resulting BatchBoost data structures provide
    significant performance improvements over their original counterparts."
alternative_title:
- LIPIcs
article_number: '35'
article_processing_charge: Yes
author:
- first_name: Vitaly
  full_name: Aksenov, Vitaly
  last_name: Aksenov
- first_name: Michael
  full_name: Anoprenko, Michael
  last_name: Anoprenko
- first_name: Alexander
  full_name: Fedorov, Alexander
  id: 2e711909-896a-11ed-bdf8-eb0f5a2984c6
  last_name: Fedorov
- first_name: Michael
  full_name: Spear, Michael
  last_name: Spear
citation:
  ama: 'Aksenov V, Anoprenko M, Fedorov A, Spear M. Brief announcement: BatchBoost:
    Universal batching for concurrent data structures. In: <i>37th International Symposium
    on Distributed Computing</i>. Vol 281. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik; 2023. doi:<a href="https://doi.org/10.4230/LIPIcs.DISC.2023.35">10.4230/LIPIcs.DISC.2023.35</a>'
  apa: 'Aksenov, V., Anoprenko, M., Fedorov, A., &#38; Spear, M. (2023). Brief announcement:
    BatchBoost: Universal batching for concurrent data structures. In <i>37th International
    Symposium on Distributed Computing</i> (Vol. 281). L’Aquila, Italy: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.DISC.2023.35">https://doi.org/10.4230/LIPIcs.DISC.2023.35</a>'
  chicago: 'Aksenov, Vitaly, Michael Anoprenko, Alexander Fedorov, and Michael Spear.
    “Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures.”
    In <i>37th International Symposium on Distributed Computing</i>, Vol. 281. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href="https://doi.org/10.4230/LIPIcs.DISC.2023.35">https://doi.org/10.4230/LIPIcs.DISC.2023.35</a>.'
  ieee: 'V. Aksenov, M. Anoprenko, A. Fedorov, and M. Spear, “Brief announcement:
    BatchBoost: Universal batching for concurrent data structures,” in <i>37th International
    Symposium on Distributed Computing</i>, L’Aquila, Italy, 2023, vol. 281.'
  ista: 'Aksenov V, Anoprenko M, Fedorov A, Spear M. 2023. Brief announcement: BatchBoost:
    Universal batching for concurrent data structures. 37th International Symposium
    on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol.
    281, 35.'
  mla: 'Aksenov, Vitaly, et al. “Brief Announcement: BatchBoost: Universal Batching
    for Concurrent Data Structures.” <i>37th International Symposium on Distributed
    Computing</i>, vol. 281, 35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2023, doi:<a href="https://doi.org/10.4230/LIPIcs.DISC.2023.35">10.4230/LIPIcs.DISC.2023.35</a>.'
  short: V. Aksenov, M. Anoprenko, A. Fedorov, M. Spear, in:, 37th International Symposium
    on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
conference:
  end_date: 2023-10-13
  location: L'Aquila, Italy
  name: 'DISC: Symposium on Distributed Computing'
  start_date: 2023-10-09
date_created: 2023-11-05T23:00:53Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2023-11-07T07:48:01Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
doi: 10.4230/LIPIcs.DISC.2023.35
file:
- access_level: open_access
  checksum: d9f8d2915cccdf2df5905b7cd1b4a560
  content_type: application/pdf
  creator: dernst
  date_created: 2023-11-06T11:45:21Z
  date_updated: 2023-11-06T11:45:21Z
  file_id: '14492'
  file_name: 2023_LIPIcs_Aksenov.pdf
  file_size: 646665
  relation: main_file
  success: 1
file_date_updated: 2023-11-06T11:45:21Z
has_accepted_license: '1'
intvolume: '       281'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '10'
oa: 1
oa_version: Published Version
publication: 37th International Symposium on Distributed Computing
publication_identifier:
  isbn:
  - '9783959773010'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: BatchBoost: Universal batching for concurrent data structures'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 281
year: '2023'
...