---
_id: '17332'
abstract:
- lang: eng
  text: 'Tree data structures, such as red-black trees, quad trees, treaps, or tries,
    are fundamental tools in computer science. A classical problem in concurrency
    is to obtain expressive, efficient, and scalable versions of practical tree data
    structures. We are interested in concurrent trees supporting range queries, i.e.,
    queries that involve multiple consecutive data items. Existing implementations
    with this capability can list keys in a specific range, but do not support aggregate
    range queries: for instance, if we want to calculate the number of keys in a range,
    the only choice is to retrieve a whole list and return its size. This is suboptimal:
    in the sequential setting, one can augment a balanced search tree with counters
    and, consequently, perform these aggregate requests in logarithmic rather than
    linear time.In this paper, we propose a generic approach to implement a broad
    class of range queries on concurrent trees in a way that is wait-free, asymptotically
    efficient, and practically scalable. The key idea is a new mechanism for maintaining
    metadata concurrently at tree nodes, which can be seen as a wait-free variant
    of hand-over-hand locking (which we call hand-over-hand helping). We did a preliminary
    implementation of the wait-free binary search tree and preliminary experiments
    have indicated the soundness of our approach.'
acknowledgement: We thank Trevor Brown and Yuanhao Wei for the discussion and anonymous
  reviewers for helping us to improve the paper. Also, we thank JetBrains and Huawei
  for their support.
article_processing_charge: No
arxiv: 1
author:
- first_name: Ilya
  full_name: Kokorin, Ilya
  last_name: Kokorin
- first_name: Victor
  full_name: Yudov, Victor
  last_name: Yudov
- first_name: Vitaly
  full_name: Aksenov, Vitaly
  last_name: Aksenov
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
citation:
  ama: 'Kokorin I, Yudov V, Aksenov V, Alistarh D-A. Wait-free trees with asymptotically-efficient
    range queries. In: <i>2024 IEEE International Parallel and Distributed Processing
    Symposium</i>. IEEE; 2024:169-179. doi:<a href="https://doi.org/10.1109/IPDPS57955.2024.00023">10.1109/IPDPS57955.2024.00023</a>'
  apa: 'Kokorin, I., Yudov, V., Aksenov, V., &#38; Alistarh, D.-A. (2024). Wait-free
    trees with asymptotically-efficient range queries. In <i>2024 IEEE International
    Parallel and Distributed Processing Symposium</i> (pp. 169–179). San Francisco,
    CA, United States: IEEE. <a href="https://doi.org/10.1109/IPDPS57955.2024.00023">https://doi.org/10.1109/IPDPS57955.2024.00023</a>'
  chicago: Kokorin, Ilya, Victor Yudov, Vitaly Aksenov, and Dan-Adrian Alistarh. “Wait-Free
    Trees with Asymptotically-Efficient Range Queries.” In <i>2024 IEEE International
    Parallel and Distributed Processing Symposium</i>, 169–79. IEEE, 2024. <a href="https://doi.org/10.1109/IPDPS57955.2024.00023">https://doi.org/10.1109/IPDPS57955.2024.00023</a>.
  ieee: I. Kokorin, V. Yudov, V. Aksenov, and D.-A. Alistarh, “Wait-free trees with
    asymptotically-efficient range queries,” in <i>2024 IEEE International Parallel
    and Distributed Processing Symposium</i>, San Francisco, CA, United States, 2024,
    pp. 169–179.
  ista: 'Kokorin I, Yudov V, Aksenov V, Alistarh D-A. 2024. Wait-free trees with asymptotically-efficient
    range queries. 2024 IEEE International Parallel and Distributed Processing Symposium.
    IPDPS: International Parallel and Distributed Processing Symposium, 169–179.'
  mla: Kokorin, Ilya, et al. “Wait-Free Trees with Asymptotically-Efficient Range
    Queries.” <i>2024 IEEE International Parallel and Distributed Processing Symposium</i>,
    IEEE, 2024, pp. 169–79, doi:<a href="https://doi.org/10.1109/IPDPS57955.2024.00023">10.1109/IPDPS57955.2024.00023</a>.
  short: I. Kokorin, V. Yudov, V. Aksenov, D.-A. Alistarh, in:, 2024 IEEE International
    Parallel and Distributed Processing Symposium, IEEE, 2024, pp. 169–179.
conference:
  end_date: 2024-05-31
  location: San Francisco, CA, United States
  name: 'IPDPS: International Parallel and Distributed Processing Symposium'
  start_date: 2024-05-27
corr_author: '1'
date_created: 2024-07-28T22:01:11Z
date_published: 2024-07-08T00:00:00Z
date_updated: 2025-09-08T08:29:45Z
day: '08'
department:
- _id: DaAl
doi: 10.1109/IPDPS57955.2024.00023
external_id:
  arxiv:
  - '2310.05293'
  isi:
  - '001270389600078'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2310.05293
month: '07'
oa: 1
oa_version: Preprint
page: 169-179
publication: 2024 IEEE International Parallel and Distributed Processing Symposium
publication_identifier:
  eissn:
  - 1530-2075
  isbn:
  - '9798350337662'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Wait-free trees with asymptotically-efficient range queries
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
_id: '11851'
abstract:
- lang: eng
  text: The minimum cut problem for an undirected edge-weighted graph asks us to divide
    its set of nodes into two blocks while minimizing the weighted sum of the cut
    edges. In this paper, we engineer the fastest known exact algorithm for the problem.
    State-of-the-art algorithms like the algorithm of Padberg and Rinaldi or the algorithm
    of Nagamochi, Ono and Ibaraki identify edges that can be contracted to reduce
    the graph size such that at least one minimum cut is maintained in the contracted
    graph. Our algorithm achieves improvements in running time over these algorithms
    by a multitude of techniques. First, we use a recently developed fast and parallel
    inexact minimum cut algorithm to obtain a better bound for the problem. Afterwards,
    we use reductions that depend on this bound to reduce the size of the graph much
    faster than previously possible. We use improved data structures to further lower
    the running time of our algorithm. Additionally, we parallelize the contraction
    routines of Nagamochi et al. . Overall, we arrive at a system that significantly
    outperforms the fastest state-of-the-art solvers for the exact minimum cut problem.
article_number: '8820968'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Alexander
  full_name: Noe, Alexander
  last_name: Noe
- first_name: Christian
  full_name: Schulz, Christian
  last_name: Schulz
citation:
  ama: 'Henzinger M, Noe A, Schulz C. Shared-memory exact minimum cuts. In: <i>33rd
    International Parallel and Distributed Processing Symposium</i>. Institute of
    Electrical and Electronics Engineers; 2019. doi:<a href="https://doi.org/10.1109/ipdps.2019.00013">10.1109/ipdps.2019.00013</a>'
  apa: 'Henzinger, M., Noe, A., &#38; Schulz, C. (2019). Shared-memory exact minimum
    cuts. In <i>33rd International Parallel and Distributed Processing Symposium</i>.
    Rio de Janeiro, Brazil: Institute of Electrical and Electronics Engineers. <a
    href="https://doi.org/10.1109/ipdps.2019.00013">https://doi.org/10.1109/ipdps.2019.00013</a>'
  chicago: Henzinger, Monika, Alexander Noe, and Christian Schulz. “Shared-Memory
    Exact Minimum Cuts.” In <i>33rd International Parallel and Distributed Processing
    Symposium</i>. Institute of Electrical and Electronics Engineers, 2019. <a href="https://doi.org/10.1109/ipdps.2019.00013">https://doi.org/10.1109/ipdps.2019.00013</a>.
  ieee: M. Henzinger, A. Noe, and C. Schulz, “Shared-memory exact minimum cuts,” in
    <i>33rd International Parallel and Distributed Processing Symposium</i>, Rio de
    Janeiro, Brazil, 2019.
  ista: 'Henzinger M, Noe A, Schulz C. 2019. Shared-memory exact minimum cuts. 33rd
    International Parallel and Distributed Processing Symposium. IPDPS: International
    Parallel and Distributed Processing Symposium, 8820968.'
  mla: Henzinger, Monika, et al. “Shared-Memory Exact Minimum Cuts.” <i>33rd International
    Parallel and Distributed Processing Symposium</i>, 8820968, Institute of Electrical
    and Electronics Engineers, 2019, doi:<a href="https://doi.org/10.1109/ipdps.2019.00013">10.1109/ipdps.2019.00013</a>.
  short: M. Henzinger, A. Noe, C. Schulz, in:, 33rd International Parallel and Distributed
    Processing Symposium, Institute of Electrical and Electronics Engineers, 2019.
conference:
  end_date: 2019-05-24
  location: Rio de Janeiro, Brazil
  name: 'IPDPS: International Parallel and Distributed Processing Symposium'
  start_date: 2019-05-20
date_created: 2022-08-16T07:25:23Z
date_published: 2019-05-01T00:00:00Z
date_updated: 2024-11-06T12:17:43Z
day: '01'
doi: 10.1109/ipdps.2019.00013
extern: '1'
external_id:
  arxiv:
  - '1808.05458'
language:
- iso: eng
main_file_link:
- url: https://arxiv.org/abs/1808.05458
month: '05'
oa_version: Preprint
publication: 33rd International Parallel and Distributed Processing Symposium
publication_identifier:
  eisbn:
  - 978-1-7281-1246-6
  eissn:
  - 1530-2075
  isbn:
  - 978-1-7281-1247-3
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
related_material:
  record:
  - id: '11851'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Shared-memory exact minimum cuts
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...