{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T20:45:31Z","timestamp":1777581931278,"version":"3.51.4"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T00:00:00Z","timestamp":1649635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-2103483, CCF-1901381, CCF-1910030, and CCF-1919223"],"award-info":[{"award-number":["CCF-2103483, CCF-1901381, CCF-1910030, and CCF-1919223"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            In this article, we show how a single function,\n            <jats:italic>join<\/jats:italic>\n            , can be used to implement parallel\n            <jats:bold>balanced binary search trees<\/jats:bold>\n            (\n            <jats:bold>BSTs<\/jats:bold>\n            ) simply and efficiently. Based on\n            <jats:italic>join<\/jats:italic>\n            , our approach applies to multiple balanced tree data structures, and a variety of functions for ordered sets and maps. We describe our technique as an algorithmic framework called\n            <jats:italic>join-based algorithms<\/jats:italic>\n            . We show that the\n            <jats:italic>join<\/jats:italic>\n            function fully captures what is needed for rebalancing trees for a variety of tree algorithms, as long as the balancing scheme satisfies certain properties, which we refer to as\n            <jats:italic>joinable<\/jats:italic>\n            trees. We discuss four balancing schemes that are joinable: AVL trees, red-black trees, weight-balanced trees, and treaps. We present a variety of tree algorithms that apply to joinable trees, including\n            <jats:italic>insert<\/jats:italic>\n            ,\n            <jats:italic>delete<\/jats:italic>\n            ,\n            <jats:italic>union<\/jats:italic>\n            ,\n            <jats:italic>intersection<\/jats:italic>\n            ,\n            <jats:italic>difference<\/jats:italic>\n            ,\n            <jats:italic>split<\/jats:italic>\n            ,\n            <jats:italic>range<\/jats:italic>\n            ,\n            <jats:italic>filter<\/jats:italic>\n            , and so on, most of them also parallel. These algorithms are generic across balancing schemes. Many algorithms are optimal in the comparison model, and we provide a general proof to show the efficiency in work for joinable trees. The algorithms are highly parallel, all with polylogarithmic span (parallel dependence). Specifically, the set-set operations\n            <jats:italic>union<\/jats:italic>\n            ,\n            <jats:italic>intersection<\/jats:italic>\n            , and\n            <jats:italic>difference<\/jats:italic>\n            have work\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( O(m\\log (\\frac{n}{m}+1)) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and polylogarithmic span for input set sizes\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( m\\le n \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            .\n          <\/jats:p>\n          <jats:p>\n            We implemented and tested our algorithms on the four balancing schemes. In general, all four schemes have quite similar performance, but the weight-balanced tree slightly outperforms the others. They have the same speedup characteristics, getting around 73\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\times \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            speedup on 72 cores (144 hyperthreads). Experimental results also show that our implementation outperforms existing parallel implementations, and our sequential version achieves close or much better performance than the sequential merging algorithm in C++ Standard Template Library (STL) on various input sizes.\n          <\/jats:p>","DOI":"10.1145\/3512769","type":"journal-article","created":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T10:19:12Z","timestamp":1649672352000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Joinable Parallel Balanced Binary Trees"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0224-9187","authenticated-orcid":false,"given":"Guy","family":"Blelloch","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Ferizovic","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3212-0934","authenticated-orcid":false,"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,4,11]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"[n. d.]. TPC Benchmarks. ([n. d.]). Retrieved April 2019 from http:\/\/tpc.org\/."},{"key":"e_1_3_2_3_2","volume-title":"Implementing Sets Effciently in a Functional Language","author":"Adams Stephen","year":"1992","unstructured":"Stephen Adams. 1992. Implementing Sets Effciently in a Functional Language. Technical Report CSTR 92-10. University of Southampton."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000885"},{"key":"e_1_3_2_5_2","first-page":"263","article-title":"An algorithm for the organization of information","volume":"145","author":"Adelson-Velsky Georgy","year":"1962","unstructured":"Georgy Adelson-Velsky and E. M. Landis. 1962. An algorithm for the organization of information. USSR Academy of Sciences 145 (1962), 263\u2013266. In Russian, English translation by Myron J. Ricci, Soviet Doklady 3 (1962), 1259\u20131263.","journal-title":"USSR Academy of Sciences"},{"key":"e_1_3_2_6_2","first-page":"84","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201914)","author":"Agrawal Kunal","year":"2014","unstructured":"Kunal Agrawal, Jeremy T. Fineman, Kefu Lu, Brendan Sheridan, Jim Sukha, and Robert Utterback. 2014. Provably good scheduling for parallel programs that use data structures through implicit batching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201914). 84\u201395."},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","unstructured":"Kunal Agrawal Seth Gilbert and Wei Quan Lim. 2018. Parallel working-set search structures in Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA\u201918) .","DOI":"10.1145\/3210377.3210390"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2016.042"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178489"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018761"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289509"},{"key":"e_1_3_2_12_2","volume-title":"ACM Symposium on Parallel Algorithms and Architectures (SPAA\u201919)","author":"Ben-David Naama","year":"2019","unstructured":"Naama Ben-David, Guy Blelloch, Yihan Sun, and Yuanhao Wei. 2019. Multiversion concurrency with bounded delay and precise garbage collection. In ACM Symposium on Parallel Algorithms and Architectures (SPAA\u201919)."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"e_1_3_2_14_2","article-title":"Parallel ordered sets using join","author":"Blelloch Guy","year":"2016","unstructured":"Guy Blelloch, Daniel Ferizovic, and Yihan Sun. 2016. Parallel ordered sets using join. arXiv preprint:1602.02120.","journal-title":"arXiv preprint:1602.02120"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935768"},{"key":"e_1_3_2_16_2","article-title":"Optimal parallel algorithms in the binary-forking model","volume":"1903","author":"Blelloch Guy E.","year":"2019","unstructured":"Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. 2019. Optimal parallel algorithms in the binary-forking model. CoRR abs\/1903.04650 (2019). arxiv:1903.04650, http:\/\/arxiv.org\/abs\/1903.04650.","journal-title":"CoRR"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277660"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90018-3"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259471"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693488"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322127"},{"key":"e_1_3_2_24_2","unstructured":"Trevor Brown. 2016. Lock-free Chromatic Trees in C++. Retrieved April 2019 from https:\/\/bitbucket.org\/trbot86\/implementations\/src\/."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35476-2_3"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555267"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555267"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90053-K"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_3_2_31_2","volume-title":"ACM Symposium on Principles of Distributed Computing","author":"Ellen Faith","year":"2010","unstructured":"Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. 2010. Non-blocking binary search trees. In ACM Symposium on Principles of Distributed Computing. See also Technical Report CSE-2010-04, EECS Department, York University, 2010."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_10"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323197"},{"key":"e_1_3_2_34_2","first-page":"49","volume-title":"Euro-Par 2007 Workshops: Parallel Processing, HPPC 2007, UNICORE Summit 2007, and VHPC 2007","author":"Frias Leonor","year":"2007","unstructured":"Leonor Frias and Johannes Singler. 2007. Parallelization of bulk operations for STL dictionaries. In Euro-Par 2007 Workshops: Parallel Processing, HPPC 2007, UNICORE Summit 2007, and VHPC 2007. 49\u201358."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/978-3-642-03367-4_31","volume-title":"Workshop on Algorithms and Data Structures","author":"Haeupler Bernhard","year":"2009","unstructured":"Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan. 2009. Rank-balanced trees. In Workshop on Algorithms and Data Structures. Springer, 351\u2013362."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796811000104"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201004"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/133889"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/263580.263614"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237865"},{"key":"e_1_3_2_42_2","volume-title":"Proceedings of Computer Science Conference","author":"Katajainen J.","year":"1994","unstructured":"J. Katajainen. 1994. Efficient parallel algorithms for manipulating sorted sets. In Proceedings of Computer Science Conference. University of Canterbury."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55599-4_79"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/320613.320619"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1705"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933349.2933352"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168855"},{"key":"e_1_3_2_49_2","article-title":"Haskell 2010 language report","author":"Marlow Simon","year":"2010","unstructured":"Simon Marlow et\u00a0al. 2010. Haskell 2010 language report. Available online http:\/\/www.haskell.org\/(May 2011).","journal-title":"Available online http:\/\/www.haskell.org\/(May 2011)"},{"key":"e_1_3_2_50_2","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn Kurt","year":"1999","unstructured":"Kurt Mehlhorn and Stefan N\u00e4her. 1999. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, New York, NY."},{"key":"e_1_3_2_51_2","volume-title":"STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library","author":"Musser David R.","year":"2009","unstructured":"David R. Musser, Gillmer J. Derge, and Atul Saini. 2009. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library. Addison-Wesley Professional."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555256"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF03036462"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00287-5"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036940"},{"key":"e_1_3_2_57_2","doi-asserted-by":"crossref","unstructured":"Raimund Seidel and Celcilia R. Aragon. 1996. Randomized search trees. Algorithmica 16 (1996) 464\u2013497.","DOI":"10.1007\/BF01940876"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_2_59_2","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1007\/978-3-642-32037-8_9","volume-title":"Trends in Functional Programming","author":"Straka Milan","year":"2012","unstructured":"Milan Straka. 2012. Adams\u2019 trees revisited. In Trends in Functional Programming. Springer, 130\u2013145."},{"key":"e_1_3_2_60_2","article-title":"The PAM Library","author":"Sun Yihan","year":"2018","unstructured":"Yihan Sun, Guy Blelloch, and Daniel Ferizovic. 2018. The PAM Library. https:\/\/github.com\/cmuparlay\/PAM.","journal-title":"https:\/\/github.com\/cmuparlay\/PAM"},{"key":"e_1_3_2_61_2","first-page":"159","volume-title":"SIAM Symposium on Algorithm Engineering and Experiments (ALENEX\u201919)","author":"Sun Yihan","year":"2019","unstructured":"Yihan Sun and Guy E. Blelloch. 2019. Parallel range, segment and rectangle queries with augmented maps. In SIAM Symposium on Algorithm Engineering and Experiments (ALENEX\u201919). 159\u2013173."},{"key":"e_1_3_2_62_2","article-title":"On supporting efficient snapshot isolation for hybrid workloads with multi-versioned indexes","author":"Sun Yihan","year":"2020","unstructured":"Yihan Sun, Guy E. Blelloch, Andrew Pavlo, and Wan Shen Lim. 2020. On supporting efficient snapshot isolation for hybrid workloads with multi-versioned indexes. PVLDB (2020).","journal-title":"PVLDB"},{"key":"e_1_3_2_63_2","volume-title":"ACM Symposium on Principles and Practice of Parallel Programming (PPoPP\u201918)","author":"Sun Yihan","year":"2018","unstructured":"Yihan Sun, Daniel Ferizovic, and Guy E. Blelloch. 2018. PAM: Parallel augmented maps. In ACM Symposium on Principles and Practice of Parallel Programming (PPoPP\u201918)."},{"key":"e_1_3_2_64_2","first-page":"156","volume-title":"Workshop on Languages and Compilers for Parallel Computing (LCPC\u201907)","author":"Tanase Gabriel","year":"2007","unstructured":"Gabriel Tanase, Chidambareswaran Raman, Mauro Bianco, Nancy M. Amato, and Lawrence Rauchwerger. 2007. Associative parallel containers in STAPL. In Workshop on Languages and Compilers for Parallel Computing (LCPC\u201907). 156\u2013171."},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.5555\/3485"},{"key":"e_1_3_2_66_2","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1007\/978-3-030-24766-9_41","volume-title":"Workshop on Algorithms and Data Structures","author":"Tarjan Robert E.","year":"2019","unstructured":"Robert E. Tarjan, Caleb C. Levy, and Stephen Timmel. 2019. Zip trees. In Workshop on Algorithms and Data Structures. Springer, 566\u2013577."},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196895"},{"key":"e_1_3_2_68_2","volume-title":"Efficient Implementation of Red-black Trees with Split and Catenate Operations","author":"Wein Ron","year":"2005","unstructured":"Ron Wein. 2005. Efficient Implementation of Red-black Trees with Split and Catenate Operations. Technical Report. Tel-Aviv University."},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210413"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512769","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3512769","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3512769","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:29Z","timestamp":1750183769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512769"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,11]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3512769"],"URL":"https:\/\/doi.org\/10.1145\/3512769","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,11]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}