{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T01:32:11Z","timestamp":1772242331552,"version":"3.50.1"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:p>The tree edit distance (TED) has been found in a wide spectrum of applications in artificial intelligence, bioinformatics, and other areas, which serves as a metric to quantify the dissimilarity between two trees. As applications continue to scale in data size, with a growing demand for fast response time, TED has become even more increasingly data- and computing-intensive. Over the years, researchers have made dedicated efforts to improve sequential TED algorithms by reducing their high complexity. However, achieving efficient parallel TED computation in both algorithm and implementation is challenging due to its dynamic programming nature involving non-trivial issues of data dependency, runtime execution pattern changes, and optimal utilization of limited parallel resources.<\/jats:p>\n          <jats:p>Having comprehensively investigated the bottlenecks in the existing parallel TED algorithms, we develop a massive parallel computation framework for TED and its implementation on GPU, which is called X-TED. For a given TED computation, X-TED applies a fast preprocessing algorithm to identify dependency relationships among millions of dynamic programming tables. Subsequently, it adopts a dynamic parallel strategy to handle various processing stages, aiming to best utilize GPU cores and the limited device memory in an adaptive and automatic way. Our intensive experimental results demonstrate that X-TED surpasses all existing solutions, achieving up to 42x speedup over the state-of-the-art sequential AP-TED, and outperforming the existing multicore parallel MC-TED by an average speedup of 31x.<\/jats:p>","DOI":"10.14778\/3654621.3654634","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T22:21:08Z","timestamp":1717107668000},"page":"1683-1696","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["X-TED: Massive Parallelization of Tree Edit Distance"],"prefix":"10.14778","volume":"17","author":[{"given":"Dayi","family":"Fan","sequence":"first","affiliation":[{"name":"The Ohio State University"}]},{"given":"Rubao","family":"Lee","sequence":"additional","affiliation":[{"name":"Freelance"}]},{"given":"Xiaodong","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Ohio State University"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3123976"},{"key":"e_1_2_1_2_1","volume-title":"Tree edit distance problems: Algorithms and applications to bioinformatics. IEICE transactions on information and systems 93, 2","author":"Akutsu Tatsuya","year":"2010","unstructured":"Tatsuya Akutsu. 2010. Tree edit distance problems: Algorithms and applications to bioinformatics. IEICE transactions on information and systems 93, 2 (2010), 208--218."},{"key":"e_1_2_1_3_1","volume-title":"Multi Core Tree Edit Distance. https:\/\/github.com\/aabyaneh\/MCTED Accessed on","author":"Abyaneh Alireza S.","year":"2020","unstructured":"Alireza S. Abyaneh. 2020. Multi Core Tree Edit Distance. https:\/\/github.com\/aabyaneh\/MCTED Accessed on July 1, 2020."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1670243.1670247"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608020.2608024"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751243"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.030"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381878"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1170"},{"key":"e_1_2_1_10_1","first-page":"291","article-title":"A comprehensive study of RNA secondary structure alignment algorithms","volume":"18","author":"Ho Chiu Jimmy Ka","year":"2017","unstructured":"Jimmy Ka Ho Chiu and Yi-Ping Phoebe Chen. 2017. A comprehensive study of RNA secondary structure alignment algorithms. Briefings in Bioinformatics 18, 2 (2017), 291--305.","journal-title":"Briefings in Bioinformatics"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkac1052"},{"key":"e_1_2_1_12_1","volume-title":"The Free Encyclopedia. https:\/\/en.wikipedia.org\/wiki\/Random_recursive_tree [Online","author":"Wikipedia","year":"2024","unstructured":"Wikipedia contributors. 2024. Random recursive tree --- Wikipedia, The Free Encyclopedia. https:\/\/en.wikipedia.org\/wiki\/Random_recursive_tree [Online; accessed 14-January-2024]."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00071"},{"key":"e_1_2_1_14_1","volume-title":"The dblp computer science bibliography. Monthly snapshot release of","author":"The","year":"2023","unstructured":"The dblp team. 2023. The dblp computer science bibliography. Monthly snapshot release of June 2023. https:\/\/dblp.org\/xml\/release\/dblp-2023-06-01.xml.gz"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644017"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2012.19"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2011.6152717"},{"key":"e_1_2_1_18_1","volume-title":"Analysis of Tree Edit Distance Algorithms","author":"Dulucq Serge","unstructured":"Serge Dulucq and H\u00e9l\u00e8ne Touzet. 2003. Analysis of Tree Edit Distance Algorithms. In Combinatorial Pattern Matching, Ricardo Baeza-Yates, Edgar Ch\u00e1vez, and Maxime Crochemore (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 83--95."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.018"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00092"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1053"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Henry Gilbert Michael Sandborn Douglas C. Schmidt Jesse Spencer-Smith and Jules White. 2023. Semantic Compression With Large Language Models. arXiv:2304.12512 [cs.AI]","DOI":"10.1109\/SNAMS60348.2023.10375400"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564725"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12021-009-9051-4"},{"key":"e_1_2_1_25_1","volume-title":"Highly efficient compensation-based parallelism for wavefront loops on gpus. In 2018 IEEE International parallel and distributed processing symposium (IPDPS)","author":"Hou Kaixi","unstructured":"Kaixi Hou, Hao Wang, Wu-chun Feng, Jeffrey S Vetter, and Seyong Lee. 2018. Highly efficient compensation-based parallelism for wavefront loops on gpus. In 2018 IEEE International parallel and distributed processing symposium (IPDPS). IEEE, 276--285."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528233.3530722"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00426"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565833"},{"key":"e_1_2_1_29_1","volume-title":"European Conference on Computer Vision. Springer, 498--517","author":"Kim Geewook","year":"2022","unstructured":"Geewook Kim, Teakgyu Hong, Moonbin Yim, Jeong Yeon Nam, Jinyoung Park, Jinyeong Yim, Wonseok Hwang, Sangdoo Yun, Dongyoon Han, and Seunghyun Park. 2022. Ocr-free document understanding transformer. In European Conference on Computer Vision. Springer, 498--517."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/647908.740125"},{"key":"e_1_2_1_31_1","unstructured":"Lambda Labs. 2024. Lambda Labs. https:\/\/lambdalabs.com\/. Accessed: 2024-01-10."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3383458"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476378"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590994"},{"key":"e_1_2_1_35_1","volume-title":"Tiling Optimization For Nested Loops On Gpus","author":"Yuanzhe Li.","unstructured":"Yuanzhe Li. 2020. Tiling Optimization For Nested Loops On Gpus. In Wayne State University Dissertations. 2362. https:\/\/doi.org\/oa_dissertations\/2362"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-020-00658-y"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE48619.2023.00110"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76837-1_19"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","unstructured":"Lixiang Luo Jack Edwards Hong Luo and Frank Mueller. 2015. Optimization of A Fine-grained BILU by CUDA Inter-block Synchronization. 10.2514\/6.2015-3055","DOI":"10.2514\/6.2015-3055"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2692916.2555264"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.914756"},{"key":"e_1_2_1_42_1","unstructured":"Xiao Mao. 2021. Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance. arXiv:2106.02026 [cs.DS]"},{"key":"e_1_2_1_43_1","volume-title":"LLM is Like a Box of Chocolates: the Non-determinism of ChatGPT in Code Generation. arXiv preprint arXiv:2308.02828","author":"Ouyang Shuyin","year":"2023","unstructured":"Shuyin Ouyang, Jie M Zhang, Mark Harman, and Meng Wang. 2023. LLM is Like a Box of Chocolates: the Non-determinism of ChatGPT in Code Generation. arXiv preprint arXiv:2308.02828 (2023)."},{"key":"e_1_2_1_44_1","volume-title":"Revisiting the tree edit distance and its backtracing: A tutorial. CoRR abs\/1805.06869","author":"Paa\u00dfen Benjamin","year":"2018","unstructured":"Benjamin Paa\u00dfen. 2018. Revisiting the tree edit distance and its backtracing: A tutorial. CoRR abs\/1805.06869 (2018). arXiv:1805.06869 http:\/\/arxiv.org\/abs\/1805.06869"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research), Jennifer Dy and Andreas Krause (Eds.)","volume":"80","author":"Paa\u00dfen Benjamin","year":"2018","unstructured":"Benjamin Paa\u00dfen, Claudio Gallicchio, Alessio Micheli, and Barbara Hammer. 2018. Tree Edit Distance Learning via Adaptive Symbol Embeddings. In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research), Jennifer Dy and Andreas Krause (Eds.), Vol. 80. PMLR, 3976--3985. https:\/\/proceedings.mlr.press\/v80\/paassen18a.html"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2095686.2095692"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.08.004"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412026"},{"key":"e_1_2_1_49_1","volume-title":"Synchromesh: Reliable code generation from pre-trained language models. arXiv:2201.11227 [cs.LG]","author":"Poesia Gabriel","year":"2022","unstructured":"Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2022. Synchromesh: Reliable code generation from pre-trained language models. arXiv:2201.11227 [cs.LG]"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3022671.2984041"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2017.44"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.42"},{"key":"e_1_2_1_53_1","volume-title":"A New Perspective on the Tree Edit Distance","author":"Schwarz Stefan","unstructured":"Stefan Schwarz, Mateusz Pawlik, and Nikolaus Augsten. 2017. A New Perspective on the Tree Edit Distance. In Similarity Search and Applications, Christian Beecks, Felix Borutta, Peer Kr\u00f6ger, and Thomas Seidl (Eds.). Springer International Publishing, Cham, 156--170."},{"key":"e_1_2_1_54_1","volume-title":"13th Innovations in Theoretical Computer Science Conference (ITCS","author":"Seddighin Masoud","year":"2022","unstructured":"Masoud Seddighin and Saeed Seddighin. 2022. 3+ \u03b5 Approximation of Tree Edit Distance in Truly Subquadratic Time. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigDataCongress.2015.32"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Jos\u00e9 Maria Sim\u00f5es Nuno Louren\u00e7o and Penousal Machado. 2023. All You Need is Sex for Diversity. In Genetic Programming Gisele Pappa Mario Giacobini and Zdenek Vasicek (Eds.). Springer Nature Switzerland Cham 276--291.","DOI":"10.1007\/978-3-031-29573-7_18"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","unstructured":"Vivek Sourabh Parth Pahariya Isha Agarwal Ankit Gautam and C. Ravindranath Chowdary. 2017. Parallel Implementation of Dynamic Programming Problems Using Wavefront and Rank Convergence with Full Resource Utilization. In 2017 18th International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT). 151--155. 10.1109\/PDCAT.2017.00033","DOI":"10.1109\/PDCAT.2017.00033"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2010.01.004"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2006.41"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/781498.781533"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2016.40"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510454.3516863"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295733"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350268"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407876"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470477"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442539"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510454.3516866"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066243"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536210"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00521-023-08609-7"},{"key":"e_1_2_1_73_1","volume-title":"Efficient parallel algorithms for tree editing problems","author":"Zhang Kaizhong","unstructured":"Kaizhong Zhang. 1996. Efficient parallel algorithms for tree editing problems. In Combinatorial Pattern Matching, Dan Hirschberg and Gene Myers (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 361--372."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809984"},{"key":"e_1_2_1_76_1","volume-title":"GPU-accelerated computation of Vietoris-Rips persistence barcodes. arXiv preprint arXiv:2003.07989","author":"Zhang Simon","year":"2020","unstructured":"Simon Zhang, Mengbai Xiao, and Hao Wang. 2020. GPU-accelerated computation of Vietoris-Rips persistence barcodes. arXiv preprint arXiv:2003.07989 (2020)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3654621.3654634","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T22:24:51Z","timestamp":1717107891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3654621.3654634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":76,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["10.14778\/3654621.3654634"],"URL":"https:\/\/doi.org\/10.14778\/3654621.3654634","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,3]]},"assertion":[{"value":"2024-05-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}