[{"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2310.05293","open_access":"1"}],"author":[{"last_name":"Kokorin","full_name":"Kokorin, Ilya","first_name":"Ilya"},{"first_name":"Victor","full_name":"Yudov, Victor","last_name":"Yudov"},{"last_name":"Aksenov","full_name":"Aksenov, Vitaly","first_name":"Vitaly"},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"}],"citation":{"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>","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.","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>.","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>","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>.","short":"I. Kokorin, V. Yudov, V. Aksenov, D.-A. Alistarh, in:, 2024 IEEE International Parallel and Distributed Processing Symposium, IEEE, 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."},"language":[{"iso":"eng"}],"status":"public","date_published":"2024-07-08T00:00:00Z","year":"2024","corr_author":"1","doi":"10.1109/IPDPS57955.2024.00023","oa_version":"Preprint","conference":{"start_date":"2024-05-27","name":"IPDPS: International Parallel and Distributed Processing Symposium","end_date":"2024-05-31","location":"San Francisco, CA, United States"},"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."}],"publisher":"IEEE","article_processing_charge":"No","date_updated":"2025-09-08T08:29:45Z","isi":1,"arxiv":1,"type":"conference","publication_status":"published","department":[{"_id":"DaAl"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","day":"08","date_created":"2024-07-28T22:01:11Z","quality_controlled":"1","external_id":{"arxiv":["2310.05293"],"isi":["001270389600078"]},"publication_identifier":{"eissn":["1530-2075"],"isbn":["9798350337662"]},"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.","oa":1,"page":"169-179","publication":"2024 IEEE International Parallel and Distributed Processing Symposium","title":"Wait-free trees with asymptotically-efficient range queries","_id":"17332","month":"07","scopus_import":"1"},{"conference":{"location":"Rio de Janeiro, Brazil","end_date":"2019-05-24","name":"IPDPS: International Parallel and Distributed Processing Symposium","start_date":"2019-05-20"},"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."}],"oa_version":"Preprint","doi":"10.1109/ipdps.2019.00013","related_material":{"record":[{"relation":"later_version","id":"11851","status":"public"}]},"publisher":"Institute of Electrical and Electronics Engineers","article_processing_charge":"No","status":"public","language":[{"iso":"eng"}],"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>","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>.","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>","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.","short":"M. Henzinger, A. Noe, C. Schulz, in:, 33rd International Parallel and Distributed Processing Symposium, Institute of Electrical and Electronics Engineers, 2019.","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>."},"author":[{"first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H"},{"first_name":"Alexander","full_name":"Noe, Alexander","last_name":"Noe"},{"first_name":"Christian","full_name":"Schulz, Christian","last_name":"Schulz"}],"main_file_link":[{"url":"https://arxiv.org/abs/1808.05458"}],"extern":"1","year":"2019","date_published":"2019-05-01T00:00:00Z","publication_identifier":{"eisbn":["978-1-7281-1246-6"],"isbn":["978-1-7281-1247-3"],"eissn":["1530-2075"]},"external_id":{"arxiv":["1808.05458"]},"quality_controlled":"1","article_number":"8820968","scopus_import":"1","month":"05","_id":"11851","publication":"33rd International Parallel and Distributed Processing Symposium","title":"Shared-memory exact minimum cuts","type":"conference","arxiv":1,"date_updated":"2024-11-06T12:17:43Z","date_created":"2022-08-16T07:25:23Z","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published"}]