{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T03:54:45Z","timestamp":1769658885839,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T00:00:00Z","timestamp":1769558400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["2403235"],"award-info":[{"award-number":["2403235"]}]},{"name":"NSF","award":["2317194"],"award-info":[{"award-number":["2317194"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,1,28]]},"DOI":"10.1145\/3774934.3786431","type":"proceedings-article","created":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T15:25:57Z","timestamp":1769613957000},"page":"109-122","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-1321-9590","authenticated-orcid":false,"given":"Quinten","family":"De Man","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4469-1997","authenticated-orcid":false,"given":"Atharva","family":"Sharma","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6573-9445","authenticated-orcid":false,"given":"Kishen N","family":"Gowda","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0685-064X","authenticated-orcid":false,"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,1,28]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"European Symposium on Algorithms (ESA).","author":"Acar Umut","year":"2020","unstructured":"Umut Acar and Daniel Anderson. 2020. Parallel Batch-Dynamic Trees via Change Propagation. In European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_2_1","volume-title":"Parallel Batch-Dynamic Graph Connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM.","author":"Acar Umut A.","year":"2019","unstructured":"Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. 2019. Parallel Batch-Dynamic Graph Connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM."},{"key":"e_1_3_2_1_3_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). 531\u2013540","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). 531\u2013540. isbn:089871558X"},{"key":"e_1_3_2_1_4_1","first-page":"596","volume-title":"Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX \/ANALCO). 41\u201354","author":"Acar Umut A.","unstructured":"Umut A. Acar, Guy E. Blelloch, and Jorge L. Vittes. 2005. An Experimental Analysis of Change Propagation in Dynamic Trees. In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX \/ANALCO). 41\u201354. isbn:0-89871-596-2"},{"key":"e_1_3_2_1_5_1","volume-title":"Parallel Batch-Dynamic Algorithms Dynamic Trees, Graphs, and Self-Adjusting Computation. Ph. D. Dissertation","author":"Anderson Daniel","unstructured":"Daniel Anderson. 2023. Parallel Batch-Dynamic Algorithms Dynamic Trees, Graphs, and Self-Adjusting Computation. Ph. D. Dissertation. Carnegie Mellon University."},{"key":"e_1_3_2_1_6_1","volume-title":"Deterministic and Low-Span Work-Efficient Parallel Batch-Dynamic Trees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 247\u2013258","author":"Anderson Daniel","year":"2024","unstructured":"Daniel Anderson and Guy E Blelloch. 2024. Deterministic and Low-Span Work-Efficient Parallel Batch-Dynamic Trees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 247\u2013258."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"N. S. Arora R. D. Blumofe and C. G. Plaxton. 2001. Thread Scheduling for Multiprogrammed Multiprocessors. Theory of Computing Systems (TOCS) 34 2 (2001) 01 Apr.","DOI":"10.1007\/s002240011004"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(96)00089-8"},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201906)","author":"Backstrom Lars","year":"2006","unstructured":"Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan. 2006. Group formation in large social networks: membership, growth, and evolution. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201906). Association for Computing Machinery, New York, NY, USA. 44\u201354. isbn:1595933395"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400254"},{"key":"e_1_3_2_1_11_1","volume-title":"Brady","author":"Blelloch Guy E.","year":"2025","unstructured":"Guy E. Blelloch and Andrew C. Brady. 2025. Parallel Batch-Dynamic Maximal Matching with Constant Work per Update. arxiv:2503.09908."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259471"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 13th International Conference on World Wide Web (WWW \u201904)","author":"Boldi P.","unstructured":"P. Boldi and S. Vigna. 2004. The webgraph framework I: compression techniques. In Proceedings of the 13th International Conference on World Wide Web (WWW \u201904). Association for Computing Machinery, New York, NY, USA. 595\u2013602. isbn:158113844X"},{"key":"e_1_3_2_1_15_1","first-page":"202","article-title":"Isomorphism Testing and Display of Symmetries in Dynamic Trees","volume":"96","author":"Cheng Siu-Wing","year":"1996","unstructured":"Siu-Wing Cheng and Moon-Pun Ng. 1996. Isomorphism Testing and Display of Symmetries in Dynamic Trees.. In SODA. 96, 202\u2013211.","journal-title":"SODA."},{"key":"e_1_3_2_1_16_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd edition). MIT Press.","edition":"3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3694906.3743315"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3712221.3712250"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.18141137"},{"key":"e_1_3_2_1_20_1","unstructured":"Quinten De Man Atharva Sharma Kishen N. Gowda and Laxman Dhulipala. 2026. UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees. arxiv:2601.10706. arxiv:2601.10706"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659973"},{"key":"e_1_3_2_1_22_1","volume-title":"Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. In ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Dhulipala Laxman","year":"2020","unstructured":"Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun. 2020. Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. In ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226825"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0835"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_3_2_1_27_1","volume-title":"Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Ghaffari Mohsen","year":"2025","unstructured":"Mohsen Ghaffari and Jaehyun Koo. 2025. Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_28_1","volume-title":"Parallel Dynamic Maximal Matching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Ghaffari Mohsen","year":"2024","unstructured":"Mohsen Ghaffari and Anton Trygub. 2024. Parallel Dynamic Maximal Matching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_29_1","volume-title":"Towards a theory of nearly constant time parallel algorithms. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. 698\u2013710","author":"Gil Joseph","unstructured":"Joseph Gil, Yossi Matias, and Uzi Vishkin. 1991. Towards a theory of nearly constant time parallel algorithms. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. 698\u2013710."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755597"},{"key":"e_1_3_2_1_31_1","volume-title":"ACM Symposium on Theory of Computing (STOC). 519\u2013527","author":"Henzinger Monika Rauch","year":"1995","unstructured":"Monika Rauch Henzinger and Valerie King. 1995. Randomized dynamic graph algorithms with polylogarithmic time per operation. In ACM Symposium on Theory of Computing (STOC). 519\u2013527. isbn:0897917189"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977585.ch28"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3694906.3743305"},{"key":"e_1_3_2_1_35_1","volume-title":"Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. 1131\u20131142","author":"Kapron Bruce M","year":"2013","unstructured":"Bruce M Kapron, Valerie King, and Ben Mountjoy. 2013. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. 1131\u20131142."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_2_1_37_1","volume-title":"Asian Symposium on Programming Languages and Systems. 244\u2013265","author":"Leijen Daan","year":"2019","unstructured":"Daan Leijen, Benjamin Zorn, and Leonardo De Moura. 2019. Mimalloc: Free list sharding in action. In Asian Symposium on Programming Languages and Systems. 244\u2013265."},{"key":"e_1_3_2_1_38_1","first-page":"47","article-title":"Parallel Tree Contraction Part 1: Fundamentals","volume":"5","author":"Miller Gary L","year":"1989","unstructured":"Gary L Miller and John H Reif. 1989. Parallel Tree Contraction Part 1: Fundamentals.. Adv. Comput. Res., 5 (1989), 47\u201372.","journal-title":"Adv. Comput. Res."},{"key":"e_1_3_2_1_39_1","unstructured":"OpenStreetMap contributors. 2017. Planet dump retrieved from https:\/\/planet.osm.org. https:\/\/www.openstreetmap.org"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297144"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Thomas Tseng Laxman Dhulipala and Guy Blelloch. 2019. Batch-Parallel Euler Tour Trees. In Algorithm Engineering and Experiments (ALENEX). 92\u2013106.","DOI":"10.1137\/1.9781611975499.8"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538584"},{"key":"e_1_3_2_1_45_1","unstructured":"Yiqiu Wang Shangdi Yu Yan Gu and Julian Shun. 2020. A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem. CoRR arxiv:2010.02379. arxiv:2010.02379"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms. 1757\u20131769","author":"Wulff-Nilsen Christian","year":"2013","unstructured":"Christian Wulff-Nilsen. 2013. Faster deterministic fully-dynamic graph connectivity. In Proceedings of the twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms. 1757\u20131769."},{"key":"e_1_3_2_1_47_1","unstructured":"Rahul Yesantharao Yiqiu Wang Laxman Dhulipala and Julian Shun. 2021. Parallel Batch-Dynamic k-d Trees. arXiv preprint arXiv:2112.06188."}],"event":{"name":"PPoPP '26: 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming","location":"Sydney NSW Australia","acronym":"PPoPP '26","sponsor":["SIGHPC ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing","SIGPLAN ACM Special Interest Group on Programming Languages"]},"container-title":["Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774934.3786431","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774934.3786431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T15:28:36Z","timestamp":1769614116000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774934.3786431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,28]]},"references-count":47,"alternative-id":["10.1145\/3774934.3786431","10.1145\/3774934"],"URL":"https:\/\/doi.org\/10.1145\/3774934.3786431","relation":{},"subject":[],"published":{"date-parts":[[2026,1,28]]},"assertion":[{"value":"2026-01-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}