{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T11:02:40Z","timestamp":1724670160142},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SPP 1736 ?Algorithms for Big Data?"],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"\n We present new sequential and parallel algorithms for wavelet tree construction based on a new\n bottom-up<\/jats:italic>\n technique. This technique makes use of the structure of the wavelet trees\u2014refining the characters represented in a node of the tree with increasing depth\u2014in an opposite way, by first computing the leaves (most refined), and then propagating this information upwards to the root of the tree. We first describe new sequential algorithms, both in RAM and external memory. Based on these results, we adapt these algorithms to parallel computers, where we address both shared memory and distributed memory settings.\n <\/jats:p>\n \n In practice, all our algorithms outperform previous ones in both time and memory efficiency, because we can compute all auxiliary information solely based on the information we obtained from computing the leaves. Most of our algorithms are also adapted to the wavelet\n matrix<\/jats:italic>\n , a variant that is particularly suited for large alphabets.\n <\/jats:p>","DOI":"10.1145\/3457197","type":"journal-article","created":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T15:06:22Z","timestamp":1625843182000},"page":"1-67","source":"Crossref","is-referenced-by-count":6,"title":["Practical Wavelet Tree Construction"],"prefix":"10.1145","volume":"26","author":[{"given":"Patrick","family":"Dinklage","sequence":"first","affiliation":[{"name":"TU Dortmund University, Germany"}]},{"given":"Jonas","family":"Ellert","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Germany"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-3384-597X","authenticated-orcid":false,"given":"Johannes","family":"Fischer","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Germany"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-2379-9455","authenticated-orcid":false,"given":"Florian","family":"Kurpicz","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Germany"}]},{"given":"Marvin","family":"L\u00f6bel","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Germany"}]}],"member":"320","published-online":{"date-parts":[[2021,7,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.39"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-38851-9_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2017.10.001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","volume-title":"Parallel Algorithms","author":"Casanova Henri","DOI":"10.1201\/9781584889465"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89097-3_18"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2014.06.002"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24583-1_19"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"Online construction of wavelet trees. In Proceedings of SEA (LIPIcs, Vol. 75)","volume":"16","author":"da Fonseca Paulo G. S.","year":"2017","journal-title":"Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1361730.1361733"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","volume-title":"Constructing the wavelet tree and wavelet matrix in distributed memory","author":"Dinklage Patrick","DOI":"10.1137\/1.9781611976007.17"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32686-9_28"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.12.010"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_16_1","volume-title":"fast and lightweight parallel wavelet tree construction","author":"Fischer Johannes"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-1000-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.04.008"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0475-9"},{"key":"e_1_2_1_21_1","volume-title":"High-order entropy-compressed text indexes","author":"Grossi Roberto"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCP.2011.16"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028575"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_25_1","volume-title":"An Introduction to Parallel Algorithms","author":"J\u00e1J\u00e1 Joseph"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00479-8_18"},{"key":"e_1_2_1_27_1","volume-title":"Puglisi","author":"K\u00e4rkk\u00e4inen Juha","year":"2009"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316368"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00097"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797331105"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2017.04.001"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.1923"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.013"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.2298\/CSIS110606004M"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of HotOS. USENIX Association.","author":"McSherry Frank","year":"2015"},{"key":"e_1_2_1_37_1","volume-title":"MPI: A Message-Passing Interface Standard.","author":"Interface Forum Message Passing","year":"1994"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.011"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.07.004"},{"key":"e_1_2_1_40_1","volume-title":"Compact Data Structures\u2014A Practical Approach","author":"Navarro Gonzalo"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2013.46"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24685-5_1"},{"key":"e_1_2_1_43_1","volume-title":"Data Structures, Sorting, Searching","author":"Sedgewick Robert"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.7"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104516"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21458-5_19"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-017-0296-2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2618791"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457197","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T20:21:55Z","timestamp":1672604515000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,9]]},"references-count":48,"alternative-id":["10.1145\/3457197"],"URL":"https:\/\/doi.org\/10.1145\/3457197","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,9]]}}}