{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:23:58Z","timestamp":1777965838615,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743305","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"525-539","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Parallel Batch Queries on Dynamic Trees: Algorithms and Experiments"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-7072-7989","authenticated-orcid":false,"given":"Humza","family":"Ikram","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6117-013X","authenticated-orcid":false,"given":"Andrew","family":"Brady","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5853-0472","authenticated-orcid":false,"given":"Daniel","family":"Anderson","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0224-9187","authenticated-orcid":false,"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323196"},{"key":"e_1_3_2_1_2_1","volume-title":"European Symposium on Algorithms (ESA).","author":"Acar Umut A","year":"2020","unstructured":"Umut A Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. 2020. Parallel Batch-dynamic Trees via Change Propagation. In European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_3_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Acar Umut A","year":"2004","unstructured":"Umut A Acar, Guy E Blelloch, Robert Harper, Jorge L Vittes, and Shan Leung Maverick Woo. 2004. Dynamizing static algorithms, with applications to dynamic trees and history independence. In ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_4_1","unstructured":"Umut A Acar Guy E Blelloch and Jorge L Vittes. 2005. An experimental analysis of change propagation in dynamic trees. In Algorithm Engineering and Experiments (ALENEX)."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3565557"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659976"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.3113\/JSOA.2021.0226"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400241"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80002-9"},{"key":"e_1_3_2_1_11_1","unstructured":"Guy E. Blelloch. 1993. Prefix Sums and Their Applications. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400254"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3610940"},{"key":"e_1_3_2_1_17_1","unstructured":"CMUParlay. 2024. ParlayHash: A Header-Only Concurrent Hash Map. https:\/\/github.com\/cmuparlay\/parlayhash"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.10"},{"key":"e_1_3_2_1_19_1","volume-title":"Johnson","author":"Demetrescu Camil","year":"2008","unstructured":"Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson. 2008. Implementation Challenge for Shortest Paths. Springer US, Boston, MA, 395--398."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804339"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226825"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0835"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320229"},{"key":"e_1_3_2_1_25_1","volume-title":"Intl. Colloq. on Automata, Languages and Programming (ICALP).","author":"Gawrychowski Pawe\u0142","year":"2020","unstructured":"Pawe\u0142 Gawrychowski, Shay Mozes, and Oren Weimann. 2020. Minimum Cut in O (m log2 n) Time. In Intl. Colloq. on Automata, Languages and Programming (ICALP)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-5511-3_9"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210393"},{"key":"e_1_3_2_1_28_1","volume-title":"Nearly Work-Efficient Parallel DFS in Undirected Graphs. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Ghaffari Mohsen","year":"2023","unstructured":"Mohsen Ghaffari, Christoph Grunau, and Jiahao Qu. 2023. Nearly Work-Efficient Parallel DFS in Undirected Graphs. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_29_1","volume-title":"IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Gil J.","unstructured":"J. Gil, Y. Matias, and U. Vishkin. 1991. Towards a theory of nearly constant time parallel algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_30_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Gu Yan","unstructured":"Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch. 2015. A Top-Down Parallel Semisort. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225269"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327209"},{"key":"e_1_3_2_1_33_1","unstructured":"Jacob Holm and Kristian de Lichtenberg. 1998. Top-trees and dynamic graph algorithms. Master's thesis. Citeseer."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Humza Ikram Andrew Brady Daniel Anderson and Guy Blelloch. 2025. Parallel Batch Queries on Dynamic Trees: Algorithms and Experiments. (2025). arXiv:2506.16477","DOI":"10.1145\/3694906.3743305"},{"key":"e_1_3_2_1_36_1","volume-title":"Introduction to Parallel Algorithms","author":"JaJa J.","unstructured":"J. JaJa. 1992. Introduction to Parallel Algorithms. Addison-Wesley Professional."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1992.223028"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02526037"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00050-1"},{"key":"e_1_3_2_1_43_1","volume-title":"Parallel Tree Contraction and Its Application. In IEEE Symposium on Foundations of Computer Science (FOCS). IEEE.","author":"Gary","unstructured":"Gary L. Miller and John H. Reif. 1985. Parallel Tree Contraction and Its Application. In IEEE Symposium on Foundations of Computer Science (FOCS). IEEE."},{"key":"e_1_3_2_1_44_1","volume-title":"Motifs in Temporal Networks. In International Conference on Web Search and Data Mining (WSDM)","author":"Paranjape Ashwin","year":"2017","unstructured":"Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. 2017. Motifs in Temporal Networks. In International Conference on Web Search and Data Mining (WSDM) (Cambridge, United Kingdom). Association for Computing Machinery, New York, NY, USA, 601--610."},{"key":"e_1_3_2_1_45_1","unstructured":"Margaret Reid-Miller Gary L. Miller and Francesmary Modugno. 1993. List Ranking and Parallel Tree Contraction. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_3_2_1_49_1","volume-title":"Annals of Discrete Mathematics.","author":"Tarjan Robert Endre","unstructured":"Robert Endre Tarjan. 1978. Complexity of monotone networks for computing conjunctions. In Annals of Discrete Mathematics. Vol. 2. Elsevier, 121--133."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Robert Endre Tarjan. 1983. Data structures and network algorithms. SIAM.","DOI":"10.1137\/1.9781611970265"},{"key":"e_1_3_2_1_52_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Tarjan Robert E","year":"2005","unstructured":"Robert E Tarjan and Renato F Werneck. 2005. Self-adjusting top trees. In ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_53_1","article-title":"Dynamic trees in practice","author":"Tarjan Robert E.","year":"2010","unstructured":"Robert E. Tarjan and Renato F. Werneck. 2010. Dynamic trees in practice. J. Experimental Algorithmics 14, Article 5 (Jan. 2010).","journal-title":"J. Experimental Algorithmics 14, Article 5"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975499.8"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"key":"e_1_3_2_1_56_1","volume-title":"SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)","author":"Yang Jaewon","year":"2012","unstructured":"Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. In SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (Beijing, China). Association for Computing Machinery, New York, NY, USA, Article 3."}],"event":{"name":"SPAA '25: 37th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Portland OR USA","acronym":"SPAA '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694906.3743305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:20:21Z","timestamp":1777922421000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":56,"alternative-id":["10.1145\/3694906.3743305","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743305","relation":{},"subject":[],"published":{"date-parts":[[2025,7,16]]},"assertion":[{"value":"2025-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}