{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:03:59Z","timestamp":1743041039211,"version":"3.40.3"},"publisher-location":"Cham","reference-count":213,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031215339"},{"type":"electronic","value":"9783031215346"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T00:00:00Z","timestamp":1674000000000},"content-version":"vor","delay-in-days":382,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We survey recent advances in scalable text index construction with a focus on practical algorithms in distributed, shared, and external memory.<\/jats:p>","DOI":"10.1007\/978-3-031-21534-6_14","type":"book-chapter","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:02:53Z","timestamp":1673985773000},"page":"252-284","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Scalable Text Index Construction"],"prefix":"10.1007","author":[{"given":"Timo","family":"Bingmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick","family":"Dinklage","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Fischer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Kurpicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enno","family":"Ohlebusch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,18]]},"reference":[{"issue":"5","key":"14_CR1","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1109\/71.224220","volume":"4","author":"B Abali","year":"1993","unstructured":"Abali, B., \u00d6zg\u00fcner, F., Bataineh, A.: Balanced parallel sort on hypercube multiprocessors. IEEE Trans. Parallel Distrib. Syst. 4(5), 572\u2013581 (1993). https:\/\/doi.org\/10.1109\/71.224220","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"14_CR2","doi-asserted-by":"publisher","unstructured":"Abdelhadi, A., Kandil, A.H., Abouelhoda, M.: Cloud-based parallel suffix array construction based on MPI. In: MECBME, pp. 334\u2013337 (2014). https:\/\/doi.org\/10.1109\/MECBME.2014.6783271","DOI":"10.1109\/MECBME.2014.6783271"},{"issue":"1","key":"14_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"MI Abouelhoda","year":"2004","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms 2(1), 53\u201386 (2004). https:\/\/doi.org\/10.1016\/S1570-8667(03)00065-0","journal-title":"J. Discrete Algorithms"},{"issue":"9","key":"14_CR4","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988). https:\/\/doi.org\/10.1145\/48529.48535","journal-title":"Commun. ACM"},{"issue":"6","key":"14_CR5","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1007\/s00778-014-0357-y","volume":"23","author":"A Alexandrov","year":"2014","unstructured":"Alexandrov, A., et al.: The stratosphere platform for big data analytics. VLDB J. 23(6), 939\u2013964 (2014). https:\/\/doi.org\/10.1007\/s00778-014-0357-y","journal-title":"VLDB J."},{"key":"14_CR6","unstructured":"Amarasinghe, S., et al.: Exascale software study: software challenges in extreme scale systems. DARPA IPTO, Air Force Research Labs, Technical report, pp. 1\u2013153 (2009)"},{"key":"14_CR7","doi-asserted-by":"publisher","unstructured":"Arge, L., Ferragina, P., Grossi, R., Vitter, J.S.: On sorting strings in external memory (extended abstract). In: STOC, pp. 540\u2013548. ACM (1997). https:\/\/doi.org\/10.1145\/258533.258647","DOI":"10.1145\/258533.258647"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/3-540-45749-6_12","volume-title":"Algorithms \u2014 ESA 2002","author":"L Arge","year":"2002","unstructured":"Arge, L., Procopiuc, O., Scott Vitter, J.: Implementing I\/O-efficient data structures using TPIE. In: M\u00f6hring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 88\u2013100. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45749-6_12"},{"key":"14_CR9","doi-asserted-by":"publisher","unstructured":"Arge, L., Rav, M., Svendsen, S.C., Truelsen, J.: External memory pipelining made easy with TPIE. In: BigData, pp. 319\u2013324. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/BigData.2017.8257940","DOI":"10.1109\/BigData.2017.8257940"},{"issue":"9","key":"14_CR10","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1016\/j.parco.2014.06.007","volume":"40","author":"D Arroyuelo","year":"2014","unstructured":"Arroyuelo, D., Bonacic, C., Costa, V.G., Mar\u00edn, M., Navarro, G.: Distributed text search using suffix arrays. Parallel Comput. 40(9), 471\u2013495 (2014). https:\/\/doi.org\/10.1016\/j.parco.2014.06.007","journal-title":"Parallel Comput."},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-319-67428-5_4","volume-title":"String Processing and Information Retrieval","author":"D Arroyuelo","year":"2017","unstructured":"Arroyuelo, D., C\u00e1novas, R., Navarro, G., Raman, R.: LZ78 compression in low main memory space. In: Fici, G., Sciortino, M., Venturini, R. (eds.) SPIRE 2017. LNCS, vol. 10508, pp. 38\u201350. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-67428-5_4"},{"key":"14_CR12","doi-asserted-by":"publisher","unstructured":"Aum\u00fcller, M., Dietzfelbinger, M.: Optimal partitioning for dual-pivot quicksort. ACM Trans. Algorithms 12(2), 18:1\u201318:36 (2016). https:\/\/doi.org\/10.1145\/2743020","DOI":"10.1145\/2743020"},{"key":"14_CR13","doi-asserted-by":"publisher","unstructured":"Axtmann, M.: Robust Scalable Sorting. Ph.D. thesis, Karlsruhe Institute of Technology, Germany (2021). https:\/\/doi.org\/10.5445\/IR\/1000136621","DOI":"10.5445\/IR\/1000136621"},{"key":"14_CR14","doi-asserted-by":"publisher","unstructured":"Axtmann, M., Bingmann, T., Sanders, P., Schulz, C.: Practical massively parallel sorting. In: SPAA, pp. 13\u201323. ACM (2015). https:\/\/doi.org\/10.1145\/2755573.2755595","DOI":"10.1145\/2755573.2755595"},{"key":"14_CR15","doi-asserted-by":"publisher","unstructured":"Axtmann, M., Sanders, P.: Robust massively parallel sorting. In: ALENEX, pp. 83\u201397. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974768.7","DOI":"10.1137\/1.9781611974768.7"},{"key":"14_CR16","doi-asserted-by":"publisher","unstructured":"Axtmann, M., Wiebigke, A., Sanders, P.: Lightweight MPI communicators with applications to perfectly balanced quicksort. In: IPDPS, pp. 254\u2013265. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/IPDPS.2018.00035","DOI":"10.1109\/IPDPS.2018.00035"},{"key":"14_CR17","doi-asserted-by":"publisher","unstructured":"Axtmann, M., Witt, S., Ferizovic, D., Sanders, P.: Engineering in-place (shared-memory) sorting algorithms. ACM Trans. Parallel Comput. 9(1), 2:1\u20132:62 (2022). https:\/\/doi.org\/10.1145\/3505286","DOI":"10.1145\/3505286"},{"key":"14_CR18","doi-asserted-by":"publisher","unstructured":"Babenko, M.A., Gawrychowski, P., Kociumaka, T., Starikovskaya, T.: Wavelet trees meet suffix trees. In: SODA, pp. 572\u2013591. SIAM (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.39","DOI":"10.1137\/1.9781611973730.39"},{"key":"14_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-030-32686-9_29","volume-title":"String Processing and Information Retrieval","author":"J Bahne","year":"2019","unstructured":"Bahne, J., et al.: SACABench: benchmarking suffix array construction. In: Brisaboa, N.R., Puglisi, S.J. (eds.) SPIRE 2019. LNCS, vol. 11811, pp. 407\u2013416. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-32686-9_29"},{"key":"14_CR20","doi-asserted-by":"publisher","unstructured":"Baier, U.: linear-time suffix sorting - a new approach for suffix array construction. In: CPM, pp. 23:1\u201323:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2016.23","DOI":"10.4230\/LIPIcs.CPM.2016.23"},{"issue":"4","key":"14_CR21","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1093\/bioinformatics\/btv603","volume":"32","author":"U Baier","year":"2016","unstructured":"Baier, U., Beller, T., Ohlebusch, E.: Graphical pan-genome analysis with compressed suffix trees and the Burrows-Wheeler transform. Bioinformatics 32(4), 497\u2013504 (2016). https:\/\/doi.org\/10.1093\/bioinformatics\/btv603","journal-title":"Bioinformatics"},{"key":"14_CR22","doi-asserted-by":"publisher","unstructured":"Baier, U., Beller, T., Ohlebusch, E.: Space-efficient parallel construction of succinct representations of suffix tree topologies. ACM J. Exp. Algorithmics 22 (2017). https:\/\/doi.org\/10.1145\/3035540","DOI":"10.1145\/3035540"},{"issue":"11","key":"14_CR23","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1002\/spe.960","volume":"40","author":"M Barsky","year":"2010","unstructured":"Barsky, M., Stege, U., Thomo, A.: A survey of practical algorithms for suffix tree construction in external memory. Softw. Pract. Exp. 40(11), 965\u2013988 (2010). https:\/\/doi.org\/10.1002\/spe.960","journal-title":"Softw. Pract. Exp."},{"key":"14_CR24","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2012.02.002","volume":"483","author":"MJ Bauer","year":"2013","unstructured":"Bauer, M.J., Cox, A.J., Rosone, G.: Lightweight algorithms for constructing and inverting the BWT of string collections. Theor. Comput. Sci. 483, 134\u2013148 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.02.002","journal-title":"Theor. Comput. Sci."},{"key":"14_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-319-38851-9_5","volume-title":"Experimental Algorithms","author":"D Belazzougui","year":"2016","unstructured":"Belazzougui, D., K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Lempel-Ziv decoding in external memory. In: Goldberg, A.V., Kulikov, A.S. (eds.) SEA 2016. LNCS, vol. 9685, pp. 63\u201374. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-38851-9_5"},{"key":"14_CR26","unstructured":"Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: SODA, pp. 360\u2013369. ACM\/SIAM (1997)"},{"issue":"3","key":"14_CR27","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1006\/jagm.1993.1018","volume":"14","author":"O Berkman","year":"1993","unstructured":"Berkman, O., Schieber, B., Vishkin, U.: Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. J. Algorithms 14(3), 344\u2013370 (1993). https:\/\/doi.org\/10.1006\/jagm.1993.1018","journal-title":"J. Algorithms"},{"key":"14_CR28","doi-asserted-by":"publisher","unstructured":"Bingmann, T.: Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools. Ph.D. thesis, Karlsruhe Institute of Technology, Germany (2018). https:\/\/doi.org\/10.5445\/IR\/1000085031","DOI":"10.5445\/IR\/1000085031"},{"key":"14_CR29","doi-asserted-by":"publisher","unstructured":"Bingmann, T., et al.: Thrill: high-performance algorithmic distributed batch data processing with C++. In: BigData, pp. 172\u2013183. IEEE Computer Society (2016). https:\/\/doi.org\/10.1109\/BigData.2016.7840603","DOI":"10.1109\/BigData.2016.7840603"},{"issue":"1","key":"14_CR30","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00453-015-0071-1","volume":"77","author":"T Bingmann","year":"2017","unstructured":"Bingmann, T., Eberle, A., Sanders, P.: Engineering parallel string sorting. Algorithmica 77(1), 235\u2013286 (2017). https:\/\/doi.org\/10.1007\/s00453-015-0071-1","journal-title":"Algorithmica"},{"key":"14_CR31","doi-asserted-by":"publisher","unstructured":"Bingmann, T., Fischer, J., Osipov, V.: Inducing suffix and LCP arrays in external memory. ACM J. Exp. Algorithmics 21(1), 2.3:1\u20132.3:27 (2016). https:\/\/doi.org\/10.1145\/2975593","DOI":"10.1145\/2975593"},{"key":"14_CR32","doi-asserted-by":"publisher","unstructured":"Bingmann, T., Gog, S., Kurpicz, F.: Scalable construction of text indexes with thrill. In: BigData, pp. 634\u2013643. IEEE (2018). https:\/\/doi.org\/10.1109\/BigData.2018.8622171","DOI":"10.1109\/BigData.2018.8622171"},{"key":"14_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-40450-4_15","volume-title":"Algorithms \u2013 ESA 2013","author":"T Bingmann","year":"2013","unstructured":"Bingmann, T., Sanders, P.: Parallel string sample sort. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 169\u2013180. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_15"},{"key":"14_CR34","doi-asserted-by":"publisher","unstructured":"Bingmann, T., Sanders, P., Schimek, M.: Communication-efficient string sorting. In: IPDPS, pp. 137\u2013147. IEEE (2020). https:\/\/doi.org\/10.1109\/IPDPS47924.2020.00024","DOI":"10.1109\/IPDPS47924.2020.00024"},{"key":"14_CR35","unstructured":"Blacher, M., Giesen, J., Sanders, P., Wassenberg, J.: Vectorized and performance-portable quicksort. CoRR abs\/2205.05982 (2022)"},{"key":"14_CR36","doi-asserted-by":"publisher","unstructured":"Blelloch, G.E., Anderson, D., Dhulipala, L.: Parlaylib - A toolkit for parallel algorithms on shared-memory multicore machines. In: SPAA, pp. 507\u2013509. ACM (2020). https:\/\/doi.org\/10.1145\/3350755.3400254","DOI":"10.1145\/3350755.3400254"},{"key":"14_CR37","unstructured":"Blelloch, G.E., Leiserson, C.E., Maggs, B.M., Plaxton, C.G., Smith, S.J., Zagha, M.: A comparison of sorting algorithms for the connection machine CM-2. Commun. ACM 39(12es), 273\u2013297 (1996)"},{"issue":"1","key":"14_CR38","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1006\/jpdc.1996.0107","volume":"37","author":"RD Blumofe","year":"1996","unstructured":"Blumofe, R.D., Joerg, C.F., Kuszmaul, B.C., Leiserson, C.E., Randall, K.H., Zhou, Y.: Cilk: an efficient multithreaded runtime system. J. Parallel Distributed Comput. 37(1), 55\u201369 (1996). https:\/\/doi.org\/10.1006\/jpdc.1996.0107","journal-title":"J. Parallel Distributed Comput."},{"key":"14_CR39","doi-asserted-by":"publisher","unstructured":"Borkar, S.: Exascale computing - A fact or a fiction? In: IPDPS, p. 3. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/IPDPS.2013.121","DOI":"10.1109\/IPDPS.2013.121"},{"key":"14_CR40","doi-asserted-by":"publisher","unstructured":"Boucher, C., Gagie, T., Kuhnle, A., Langmead, B., Manzini, G., Mun, T.: Prefix-free parsing for building big BWTs. Algorithms Mol. Biol. 14(1), 13:1\u201313:15 (2019). https:\/\/doi.org\/10.1186\/s13015-019-0148-5","DOI":"10.1186\/s13015-019-0148-5"},{"key":"14_CR41","doi-asserted-by":"crossref","unstructured":"Bramas, B.: A novel hybrid quicksort algorithm vectorized using AVX-512 on intel skylake. Int. J. Adv. Comput. Sci. Appl. 8(10) (2017). arXiv:1704.08579","DOI":"10.14569\/IJACSA.2017.081044"},{"key":"14_CR42","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm, Technical report (1994)"},{"issue":"3","key":"14_CR43","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1109\/JPROC.2015.2455551","volume":"105","author":"S Canzar","year":"2017","unstructured":"Canzar, S., Salzberg, S.L.: Short read mapping: an algorithmic tour. Proc. IEEE 105(3), 436\u2013458 (2017). https:\/\/doi.org\/10.1109\/JPROC.2015.2455551","journal-title":"Proc. IEEE"},{"issue":"12","key":"14_CR44","doi-asserted-by":"publisher","first-page":"1512","DOI":"10.1016\/j.jpdc.2006.08.004","volume":"66","author":"C Chen","year":"2006","unstructured":"Chen, C., Schmidt, B.: Constructing large suffix trees on a computational grid. J. Parallel Distributed Comput. 66(12), 1512\u20131523 (2006). https:\/\/doi.org\/10.1016\/j.jpdc.2006.08.004","journal-title":"J. Parallel Distributed Comput."},{"key":"14_CR45","doi-asserted-by":"publisher","unstructured":"Chim, H., Deng, X.: A new suffix tree similarity measure for document clustering. In: WWW, pp. 121\u2013130. ACM (2007). https:\/\/doi.org\/10.1145\/1242572.1242590","DOI":"10.1145\/1242572.1242590"},{"key":"14_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-540-89097-3_18","volume-title":"String Processing and Information Retrieval","author":"F Claude","year":"2008","unstructured":"Claude, F., Navarro, G.: Practical rank\/select queries over arbitrary sequences. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 176\u2013187. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-89097-3_18"},{"key":"14_CR47","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.is.2014.06.002","volume":"47","author":"F Claude","year":"2015","unstructured":"Claude, F., Navarro, G., Pereira, A.O.: The wavelet matrix: an efficient wavelet tree for large alphabets. Inf. Syst. 47, 15\u201332 (2015). https:\/\/doi.org\/10.1016\/j.is.2014.06.002","journal-title":"Inf. Syst."},{"key":"14_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-24583-1_19","volume-title":"String Processing and Information Retrieval","author":"F Claude","year":"2011","unstructured":"Claude, F., Nicholson, P.K., Seco, D.: Space efficient wavelet tree construction. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol. 7024, pp. 185\u2013196. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-24583-1_19"},{"issue":"2\u20134","key":"14_CR49","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/j.jda.2004.08.004","volume":"3","author":"R Clifford","year":"2005","unstructured":"Clifford, R.: Distributed suffix trees. J. Discrete Algorithms 3(2\u20134), 176\u2013197 (2005). https:\/\/doi.org\/10.1016\/j.jda.2004.08.004","journal-title":"J. Discrete Algorithms"},{"key":"14_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-44888-8_6","volume-title":"Combinatorial Pattern Matching","author":"R Clifford","year":"2003","unstructured":"Clifford, R., Sergot, M.: Distributed and paged suffix trees for large genetic databases. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol. 2676, pp. 70\u201382. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44888-8_6"},{"key":"14_CR51","doi-asserted-by":"publisher","unstructured":"Dutilh, B.E.: Consortium: Computational pan-genomics: status, promises and challenges. Briefings Bioinform. 19(1), 118\u2013135 (2018). https:\/\/doi.org\/10.1093\/bib\/bbw089","DOI":"10.1093\/bib\/bbw089"},{"issue":"1","key":"14_CR52","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-001-0051-5","volume":"32","author":"A Crauser","year":"2002","unstructured":"Crauser, A., Ferragina, P.: A theoretical and experimental study on the construction of suffix arrays in external memory. Algorithmica 32(1), 1\u201335 (2002). https:\/\/doi.org\/10.1007\/s00453-001-0051-5","journal-title":"Algorithmica"},{"issue":"1","key":"14_CR53","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/99.660313","volume":"5","author":"L Dagum","year":"1998","unstructured":"Dagum, L., Leonardo, R.: OpenMP: an industry-standard API for shared-memory programming. IEEE Comput. Sci. Eng. 5(1), 46\u201355 (1998). https:\/\/doi.org\/10.1109\/99.660313","journal-title":"IEEE Comput. Sci. Eng."},{"issue":"1","key":"14_CR54","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51(1), 107\u2013113 (2008). https:\/\/doi.org\/10.1145\/1327452.1327492","journal-title":"Commun. ACM"},{"issue":"11","key":"14_CR55","doi-asserted-by":"publisher","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","volume":"27","author":"AL Delcher","year":"1999","unstructured":"Delcher, A.L., Kasif, S., Fleischmann, R.D., Peterson, J., White, O., Salzberg, S.L.: Alignment of whole genomes. Nucleic Acids Res. 27(11), 2369\u20132376 (1999). https:\/\/doi.org\/10.1093\/nar\/27.11.2369","journal-title":"Nucleic Acids Res."},{"key":"14_CR56","doi-asserted-by":"publisher","unstructured":"Dementiev, R., K\u00e4rkk\u00e4inen, J., Mehnert, J., Sanders, P.: Better external memory suffix array construction. ACM J. Exp. Algorithmics 12, 3.4:1\u20133.4:24 (2008). https:\/\/doi.org\/10.1145\/1227161.1402296","DOI":"10.1145\/1227161.1402296"},{"issue":"6","key":"14_CR57","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1002\/spe.844","volume":"38","author":"R Dementiev","year":"2008","unstructured":"Dementiev, R., Kettner, L., Sanders, P.: STXXL: standard template library for XXL data sets. Softw. Pract. Exp. 38(6), 589\u2013637 (2008). https:\/\/doi.org\/10.1002\/spe.844","journal-title":"Softw. Pract. Exp."},{"key":"14_CR58","doi-asserted-by":"publisher","unstructured":"Dementiev, R., Sanders, P.: Asynchronous parallel disk sorting. In: SPAA, pp. 138\u2013148. ACM (2003). https:\/\/doi.org\/10.1145\/777412.777435","DOI":"10.1145\/777412.777435"},{"key":"14_CR59","doi-asserted-by":"publisher","unstructured":"Deo, M., Keely, S.: Parallel suffix array and least common prefix for the GPU. In: PPOPP, pp. 197\u2013206. ACM (2013). https:\/\/doi.org\/10.1145\/2442516.2442536","DOI":"10.1145\/2442516.2442536"},{"key":"14_CR60","doi-asserted-by":"publisher","unstructured":"DeWitt, D.J., Naughton, J.F., Schneider, D.A.: Parallel sorting on a shared-nothing architecture using probabilistic splitting. In: PDIS, pp. 280\u2013291. IEEE Computer Society (1991). https:\/\/doi.org\/10.1109\/PDIS.1991.183115","DOI":"10.1109\/PDIS.1991.183115"},{"key":"14_CR61","unstructured":"Dinklage, P.: Translating between wavelet tree and wavelet matrix construction. In: Stringology, pp. 126\u2013135. Czech Technical University in Prague, Faculty of Information Technology, Department of Theoretical Computer Science (2019)"},{"key":"14_CR62","doi-asserted-by":"publisher","unstructured":"Dinklage, P., Ellert, J., Fischer, J., K\u00f6ppl, D., Penschuck, M.: Bidirectional text compression in external memory. In: ESA, pp. 41:1\u201341:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.41","DOI":"10.4230\/LIPIcs.ESA.2019.41"},{"key":"14_CR63","doi-asserted-by":"publisher","unstructured":"Dinklage, P., Ellert, J., Fischer, J., Kurpicz, F., L\u00f6bel, M.: Practical wavelet tree construction. ACM J. Exp. Algorithmics 26 (2021). https:\/\/doi.org\/10.1145\/3457197","DOI":"10.1145\/3457197"},{"key":"14_CR64","doi-asserted-by":"publisher","unstructured":"Dinklage, P., Fischer, J., Kurpicz, F.: Constructing the wavelet tree and wavelet matrix in distributed memory. In: ALENEX, pp. 214\u2013228. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611976007.17","DOI":"10.1137\/1.9781611976007.17"},{"key":"14_CR65","doi-asserted-by":"publisher","unstructured":"Edelkamp, S., Wei\u00df, A.: Blockquicksort: avoiding branch mispredictions in quicksort. ACM J. Exp. Algorithmics 24(1), 1.4:1\u20131.4:22 (2019). https:\/\/doi.org\/10.1145\/3274660","DOI":"10.1145\/3274660"},{"key":"14_CR66","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.tcs.2013.10.009","volume":"525","author":"JA Edwards","year":"2014","unstructured":"Edwards, J.A., Vishkin, U.: Parallel algorithms for burrows-wheeler compression and decompression. Theor. Comput. Sci. 525, 10\u201322 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2013.10.009","journal-title":"Theor. Comput. Sci."},{"key":"14_CR67","doi-asserted-by":"publisher","unstructured":"Egidi, L., Louza, F.A., Manzini, G., Telles, G.P.: External memory BWT and LCP computation for sequence collections with applications. Algorithms Mol. Biol. 14(1), 6:1\u20136:15 (2019). https:\/\/doi.org\/10.1186\/s13015-019-0140-0","DOI":"10.1186\/s13015-019-0140-0"},{"key":"14_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/978-3-030-57675-2_21","volume-title":"Euro-Par 2020: Parallel Processing","author":"J Ellert","year":"2020","unstructured":"Ellert, J., Fischer, J., Sitchinava, N.: LCP-aware parallel string sorting. In: Malawski, M., Rzadca, K. (eds.) Euro-Par 2020. LNCS, vol. 12247, pp. 329\u2013342. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-57675-2_21"},{"key":"14_CR69","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/978-3-030-32686-9_28","volume-title":"String Processing and Information Retrieval","author":"J Ellert","year":"2019","unstructured":"Ellert, J., Kurpicz, F.: Parallel external memory wavelet tree and wavelet matrix construction. In: Brisaboa, N.R., Puglisi, S.J. (eds.) SPIRE 2019. LNCS, vol. 11811, pp. 392\u2013406. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-32686-9_28"},{"key":"14_CR70","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/11672142_4","volume-title":"STACS 2006","author":"R Fagerberg","year":"2006","unstructured":"Fagerberg, R., Pagh, A., Pagh, R.: External string sorting: faster and cache-oblivious. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 68\u201379. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11672142_4"},{"issue":"6","key":"14_CR71","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM 47(6), 987\u20131011 (2000). https:\/\/doi.org\/10.1145\/355541.355547","journal-title":"J. ACM"},{"issue":"3","key":"14_CR72","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/s00453-011-9535-0","volume":"63","author":"P Ferragina","year":"2012","unstructured":"Ferragina, P., Gagie, T., Manzini, G.: Lightweight data indexing and compression in external memory. Algorithmica 63(3), 707\u2013730 (2012). https:\/\/doi.org\/10.1007\/s00453-011-9535-0","journal-title":"Algorithmica"},{"issue":"8","key":"14_CR73","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1016\/j.ic.2008.12.010","volume":"207","author":"P Ferragina","year":"2009","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G.: The myriad virtues of wavelet trees. Inf. Comput. 207(8), 849\u2013866 (2009). https:\/\/doi.org\/10.1016\/j.ic.2008.12.010","journal-title":"Inf. Comput."},{"key":"14_CR74","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS, pp. 390\u2013398. IEEE Computer Society (2000). https:\/\/doi.org\/10.1109\/SFCS.2000.892127","DOI":"10.1109\/SFCS.2000.892127"},{"key":"14_CR75","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"J Fischer","year":"2007","unstructured":"Fischer, J., Heun, V.: A new succinct representation of RMQ-information and improvements in the enhanced suffix array. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol. 4614, pp. 459\u2013470. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74450-4_41"},{"key":"14_CR76","doi-asserted-by":"publisher","unstructured":"Fischer, J., I, T., K\u00f6ppl, D., Sadakane, K.: Lempel-Ziv factorization powered by space efficient suffix trees. Algorithmica 80(7), 2048\u20132081 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0333-1","DOI":"10.1007\/s00453-017-0333-1"},{"key":"14_CR77","unstructured":"Fischer, J., Kurpicz, F.: Dismantling divsufsort. In: Stringology, pp. 62\u201376. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague (2017)"},{"key":"14_CR78","doi-asserted-by":"publisher","unstructured":"Fischer, J., Kurpicz, F.: Lightweight distributed suffix array construction. In: ALENEX, pp. 27\u201338. SIAM (2019). https:\/\/doi.org\/10.1137\/1.9781611975499.3","DOI":"10.1137\/1.9781611975499.3"},{"key":"14_CR79","doi-asserted-by":"publisher","unstructured":"Fischer, J., Kurpicz, F., L\u00f6bel, M.: Simple, fast and lightweight parallel wavelet tree construction. In: ALENEX, pp. 9\u201320. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975055.2","DOI":"10.1137\/1.9781611975055.2"},{"key":"14_CR80","doi-asserted-by":"publisher","unstructured":"Fischer, J., Kurpicz, F., Sanders, P.: Engineering a distributed full-text index. In: ALENEX, pp. 120\u2013134. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974768.10","DOI":"10.1137\/1.9781611974768.10"},{"key":"14_CR81","doi-asserted-by":"publisher","unstructured":"Flick, P., Aluru, S.: Parallel distributed memory construction of suffix and longest common prefix arrays. In: SC, pp. 16:1\u201316:10. ACM (2015). https:\/\/doi.org\/10.1145\/2807591.2807609","DOI":"10.1145\/2807591.2807609"},{"key":"14_CR82","doi-asserted-by":"publisher","unstructured":"Flick, P., Aluru, S.: Parallel construction of suffix trees and the all-nearest-smaller-values problem. In: IPDPS, pp. 12\u201321. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/IPDPS.2017.62","DOI":"10.1109\/IPDPS.2017.62"},{"key":"14_CR83","doi-asserted-by":"publisher","unstructured":"Flick, P., Aluru, S.: Distributed enhanced suffix arrays: efficient algorithms for construction and querying. In: SC, pp. 72:1\u201372:17. ACM (2019). https:\/\/doi.org\/10.1145\/3295500.3356211","DOI":"10.1145\/3295500.3356211"},{"key":"14_CR84","doi-asserted-by":"publisher","unstructured":"da Fonseca, P.G.S., da Silva, I.B.F.: Online construction of wavelet trees. In: SEA, pp. 16:1\u201316:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2017.16","DOI":"10.4230\/LIPIcs.SEA.2017.16"},{"issue":"3","key":"14_CR85","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1007\/s10115-016-1000-6","volume":"51","author":"J Fuentes-Sep\u00falveda","year":"2017","unstructured":"Fuentes-Sep\u00falveda, J., Elejalde, E., Ferres, L., Seco, D.: Parallel construction of wavelet trees on multicore architectures. Knowl. Inf. Syst. 51(3), 1043\u20131066 (2017). https:\/\/doi.org\/10.1007\/s10115-016-1000-6","journal-title":"Knowl. Inf. Syst."},{"key":"14_CR86","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.tcs.2019.09.030","volume":"812","author":"J Fuentes-Sep\u00falveda","year":"2020","unstructured":"Fuentes-Sep\u00falveda, J., Navarro, G., Nekrich, Y.: Parallel computation of the burrows wheeler transform in compact space. Theor. Comput. Sci. 812, 123\u2013136 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.09.030","journal-title":"Theor. Comput. Sci."},{"key":"14_CR87","doi-asserted-by":"publisher","unstructured":"Furtak, T., Amaral, J.N., Niewiadomski, R.: Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms. In: SPAA, pp. 348\u2013357. ACM (2007). https:\/\/doi.org\/10.1145\/1248377.1248436","DOI":"10.1145\/1248377.1248436"},{"key":"14_CR88","unstructured":"Futamura, N., Aluru, S., Kurtz, S.: Parallel suffix sorting. In: Electrical Engineering and Computer Science, vol. 64 (2001)"},{"key":"14_CR89","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-540-30218-6_19","volume-title":"Recent Advances in Parallel Virtual Machine and Message Passing Interface","author":"E Gabriel","year":"2004","unstructured":"Gabriel, E., et al.: Open MPI: goals, concept, and design of a next generation MPI implementation. In: Kranzlm\u00fcller, D., Kacsuk, P., Dongarra, J. (eds.) EuroPVM\/MPI 2004. LNCS, vol. 3241, pp. 97\u2013104. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30218-6_19"},{"key":"14_CR90","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/978-3-642-54423-1_63","volume-title":"LATIN 2014: Theoretical Informatics","author":"T Gagie","year":"2014","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: LZ77-based self-indexing with faster pattern matching. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 731\u2013742. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54423-1_63"},{"key":"14_CR91","doi-asserted-by":"publisher","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Fully functional suffix trees and optimal text searching in BWT-runs bounded space. J. ACM 67(1), 2:1\u20132:54 (2020). https:\/\/doi.org\/10.1145\/3375890","DOI":"10.1145\/3375890"},{"issue":"9","key":"14_CR92","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1038\/nbt.4227","volume":"36","author":"E Garrison","year":"2018","unstructured":"Garrison, E., et al.: Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat. Biotechnol. 36(9), 875\u2013879 (2018). https:\/\/doi.org\/10.1038\/nbt.4227","journal-title":"Nat. Biotechnol."},{"key":"14_CR93","doi-asserted-by":"publisher","unstructured":"Gilchrist, J., Cuhadar, A.: Parallel lossless data compression based on the burrows-wheeler transform. In: AINA, pp. 877\u2013884. IEEE Computer Society (2007). https:\/\/doi.org\/10.1109\/AINA.2007.109","DOI":"10.1109\/AINA.2007.109"},{"key":"14_CR94","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-07959-2_28","volume-title":"Experimental Algorithms","author":"S Gog","year":"2014","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326\u2013337. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07959-2_28"},{"key":"14_CR95","unstructured":"Gonnet, G.H., Baeza-Yates, R.A., Snider, T.: New indices for text: Pat trees and pat arrays. In: Information Retrieval: Data Structures & Algorithms, pp. 66\u201382. Prentice-Hall (1992)"},{"issue":"2","key":"14_CR96","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/S0097539795294141","volume":"29","author":"MT Goodrich","year":"1999","unstructured":"Goodrich, M.T.: Communication-efficient parallel sorting. SIAM J. Comput. 29(2), 416\u2013432 (1999). https:\/\/doi.org\/10.1137\/S0097539795294141","journal-title":"SIAM J. Comput."},{"key":"14_CR97","unstructured":"Goto, K.: Optimal time and space construction of suffix arrays and LCP arrays for integer alphabets. In: Stringology, pp. 111\u2013125. Czech Technical University in Prague, Faculty of Information Technology, Department of Theoretical Computer Science (2019)"},{"issue":"6","key":"14_CR98","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/0167-8191(96)00024-5","volume":"22","author":"W Gropp","year":"1996","unstructured":"Gropp, W., Lusk, E.L., Doss, N.E., Skjellum, A.: A high-performance, portable implementation of the MPI message passing interface standard. Parallel Comput. 22(6), 789\u2013828 (1996). https:\/\/doi.org\/10.1016\/0167-8191(96)00024-5","journal-title":"Parallel Comput."},{"key":"14_CR99","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA, pp. 841\u2013850. ACM\/SIAM (2003)"},{"key":"14_CR100","doi-asserted-by":"publisher","unstructured":"Grossi, R., Vitter, J.S., Xu, B.: Wavelet trees: from theory to practice. In: CCP, pp. 210\u2013221. IEEE Computer Society (2011). https:\/\/doi.org\/10.1109\/CCP.2011.16","DOI":"10.1109\/CCP.2011.16"},{"issue":"8","key":"14_CR101","doi-asserted-by":"publisher","first-page":"2368","DOI":"10.1111\/j.1467-8659.2009.01542.x","volume":"28","author":"LK Ha","year":"2009","unstructured":"Ha, L.K., Kr\u00fcger, J.H., Silva, C.T.: Fast four-way parallel radix sorting on GPUs. Comput. Graph. Forum 28(8), 2368\u20132378 (2009). https:\/\/doi.org\/10.1111\/j.1467-8659.2009.01542.x","journal-title":"Comput. Graph. Forum"},{"key":"14_CR102","doi-asserted-by":"publisher","unstructured":"Hagerup, T.: Optimal parallel string algorithms: sorting, merging and computing the minimum. In: STOC, pp. 382\u2013391. ACM (1994). https:\/\/doi.org\/10.1145\/195058.195202","DOI":"10.1145\/195058.195202"},{"issue":"1","key":"14_CR103","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2020.102378","volume":"58","author":"LB Han","year":"2021","unstructured":"Han, L.B., Wu, Y., Nong, G.: Succinct suffix sorting in external memory. Inf. Process. Manag. 58(1), 102378 (2021). https:\/\/doi.org\/10.1016\/j.ipm.2020.102378","journal-title":"Inf. Process. Manag."},{"key":"14_CR104","doi-asserted-by":"publisher","unstructured":"Hayashi, S., Taura, K.: Parallel and memory-efficient burrows-wheeler transform. In: BigData, pp. 43\u201350. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/BigData.2013.6691757","DOI":"10.1109\/BigData.2013.6691757"},{"issue":"10","key":"14_CR105","doi-asserted-by":"publisher","first-page":"1425","DOI":"10.1006\/jpdc.2001.1741","volume":"61","author":"X He","year":"2001","unstructured":"He, X., Huang, C.: Communication efficient BSP algorithm for all nearest smaller values problem. J. Parallel Distributed Comput. 61(10), 1425\u20131438 (2001). https:\/\/doi.org\/10.1006\/jpdc.2001.1741","journal-title":"J. Parallel Distributed Comput."},{"issue":"1","key":"14_CR106","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jpdc.1998.1462","volume":"52","author":"DR Helman","year":"1998","unstructured":"Helman, D.R., Bader, D.A., J\u00e1J\u00e1, J.: A randomized parallel sorting algorithm with an experimental study. J. Parallel Distributed Comput. 52(1), 1\u201323 (1998). https:\/\/doi.org\/10.1006\/jpdc.1998.1462","journal-title":"J. Parallel Distributed Comput."},{"issue":"1","key":"14_CR107","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"CAR Hoare","year":"1962","unstructured":"Hoare, C.A.R.: Quicksort. Comput. J. 5(1), 10\u201315 (1962). https:\/\/doi.org\/10.1093\/comjnl\/5.1.10","journal-title":"Comput. J."},{"issue":"5","key":"14_CR108","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1109\/TPDS.2018.2789903","volume":"29","author":"K Hou","year":"2018","unstructured":"Hou, K., Wang, H., Feng, W.: A framework for the automatic vectorization of parallel sort on x86-based processors. IEEE Trans. Parallel Distrib. Syst. 29(5), 958\u2013972 (2018). https:\/\/doi.org\/10.1109\/TPDS.2018.2789903","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"14_CR109","doi-asserted-by":"publisher","unstructured":"Huang, B., Gao, J., Li, X.: An empirically optimized radix sort for GPU. In: ISPA, pp. 234\u2013241. IEEE Computer Society (2009). https:\/\/doi.org\/10.1109\/ISPA.2009.89","DOI":"10.1109\/ISPA.2009.89"},{"issue":"6","key":"14_CR110","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1002\/spe.1102","volume":"42","author":"H Inoue","year":"2012","unstructured":"Inoue, H., Moriyama, T., Komatsu, H., Nakatani, T.: A high-performance sorting algorithm for multicore single-instruction multiple-data processors. Softw. Pract. Exp. 42(6), 753\u2013777 (2012). https:\/\/doi.org\/10.1002\/spe.1102","journal-title":"Softw. Pract. Exp."},{"key":"14_CR111","doi-asserted-by":"publisher","unstructured":"Itoh, H., Tanaka, H.: An efficient method for in memory construction of suffix arrays. In: SPIRE\/CRIWG, pp. 81\u201388. IEEE (1999). https:\/\/doi.org\/10.1109\/SPIRE.1999.796581","DOI":"10.1109\/SPIRE.1999.796581"},{"key":"14_CR112","volume-title":"An Introduction to Parallel Algorithms","author":"J J\u00e1J\u00e1","year":"1992","unstructured":"J\u00e1J\u00e1, J.: An Introduction to Parallel Algorithms. Addison-Wesley, Boston (1992)"},{"issue":"2","key":"14_CR113","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(94)00263-0","volume":"154","author":"J J\u00e1J\u00e1","year":"1996","unstructured":"J\u00e1J\u00e1, J., Ryu, K.W., Vishkin, U.: Sorting strings and constructing digital search trees in parallel. Theor. Comput. Sci. 154(2), 225\u2013245 (1996). https:\/\/doi.org\/10.1016\/0304-3975(94)00263-0","journal-title":"Theor. Comput. Sci."},{"key":"14_CR114","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-030-00479-8_18","volume-title":"String Processing and Information Retrieval","author":"Y Kaneta","year":"2018","unstructured":"Kaneta, Y.: Fast wavelet tree construction in practice. In: Gagie, T., Moffat, A., Navarro, G., Cuadros-Vargas, E. (eds.) SPIRE 2018. LNCS, vol. 11147, pp. 218\u2013232. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00479-8_18"},{"key":"14_CR115","doi-asserted-by":"publisher","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D.: Faster external memory LCP array construction. In: ESA.,pp. 61:1\u201361:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.61","DOI":"10.4230\/LIPIcs.ESA.2016.61"},{"key":"14_CR116","doi-asserted-by":"publisher","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D.: LCP array construction in external memory. ACM J. Exp. Algorithmics 21(1), 1.7:1\u20131.7:22 (2016). https:\/\/doi.org\/10.1145\/2851491","DOI":"10.1145\/2851491"},{"issue":"2","key":"14_CR117","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s11786-016-0281-1","volume":"11","author":"J K\u00e4rkk\u00e4inen","year":"2017","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D.: Engineering a lightweight external memory suffix array construction algorithm. Math. Comput. Sci. 11(2), 137\u2013149 (2017). https:\/\/doi.org\/10.1007\/s11786-016-0281-1","journal-title":"Math. Comput. Sci."},{"key":"14_CR118","doi-asserted-by":"publisher","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D.: Engineering external memory LCP array construction: Parallel, in-place and large alphabet. In: SEA, pp. 17:1\u201317:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2017.17","DOI":"10.4230\/LIPIcs.SEA.2017.17"},{"key":"14_CR119","doi-asserted-by":"publisher","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D.: Better external memory LCP array construction. ACM J. Exp. Algorithmics 24(1), 1.3:1\u20131.3:27 (2019). https:\/\/doi.org\/10.1145\/3297723","DOI":"10.1145\/3297723"},{"key":"14_CR120","doi-asserted-by":"publisher","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Lempel-ziv parsing in external memory. In: DCC, pp. 153\u2013162. IEEE (2014). https:\/\/doi.org\/10.1109\/DCC.2014.78","DOI":"10.1109\/DCC.2014.78"},{"key":"14_CR121","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/978-3-319-19929-0_28","volume-title":"Combinatorial Pattern Matching","author":"J K\u00e4rkk\u00e4inen","year":"2015","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Parallel external memory suffix sorting. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 329\u2013342. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19929-0_28"},{"key":"14_CR122","doi-asserted-by":"publisher","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J., Zhukova, B.: Engineering external memory induced suffix sorting. In: ALENEX, pp. 98\u2013108. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974768.8","DOI":"10.1137\/1.9781611974768.8"},{"key":"14_CR123","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-540-89097-3_3","volume-title":"String Processing and Information Retrieval","author":"J K\u00e4rkk\u00e4inen","year":"2008","unstructured":"K\u00e4rkk\u00e4inen, J., Rantala, T.: Engineering radix sort for strings. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 3\u201314. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-89097-3_3"},{"issue":"6","key":"14_CR124","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918\u2013936 (2006). https:\/\/doi.org\/10.1145\/1217856.1217858","journal-title":"J. ACM"},{"key":"14_CR125","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T Kasai","year":"2001","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A. (ed.) CPM 2001. LNCS, vol. 2089, pp. 181\u2013192. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-48194-X_17"},{"key":"14_CR126","doi-asserted-by":"publisher","unstructured":"Kempa, D., Kociumaka, T.: String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. In: STOC, pp. 756\u2013767. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316368","DOI":"10.1145\/3313276.3316368"},{"key":"14_CR127","doi-asserted-by":"publisher","unstructured":"Kitajima, J.P., Navarro, G.: A fast distributed suffix array generation algorithm. In: SPIRE\/CRIWG, pp. 97\u2013105. IEEE (1999). https:\/\/doi.org\/10.1109\/SPIRE.1999.796583","DOI":"10.1109\/SPIRE.1999.796583"},{"key":"14_CR128","doi-asserted-by":"crossref","unstructured":"Kitajima, J.P., Ribeiro-Neto, B., Ziviani, N.: Network and memory analysis in distributed parallel generation of pat arrays. In: BSCA, pp. 192\u2013202 (1996)","DOI":"10.5753\/sbac-pad.1996.19827"},{"key":"14_CR129","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley (1973)"},{"key":"14_CR130","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-030-17083-7_10","volume-title":"Research in Computational Molecular Biology","author":"A Kuhnle","year":"2019","unstructured":"Kuhnle, A., Mun, T., Boucher, C., Gagie, T., Langmead, B., Manzini, G.: Efficient construction of a complete index for pan-genomics read alignment. In: Cowen, L.J. (ed.) RECOMB 2019. LNCS, vol. 11467, pp. 158\u2013173. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17083-7_10"},{"issue":"9","key":"14_CR131","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.parco.2007.06.004","volume":"33","author":"F Kulla","year":"2007","unstructured":"Kulla, F., Sanders, P.: Scalable parallel suffix array construction. Parallel Comput. 33(9), 605\u2013612 (2007). https:\/\/doi.org\/10.1016\/j.parco.2007.06.004","journal-title":"Parallel Comput."},{"key":"14_CR132","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2017.04.001","volume":"43","author":"J Labeit","year":"2017","unstructured":"Labeit, J., Shun, J., Blelloch, G.E.: Parallel lightweight wavelet tree, suffix array and FM-index construction. J. Discrete Algorithms 43, 2\u201317 (2017). https:\/\/doi.org\/10.1016\/j.jda.2017.04.001","journal-title":"J. Discrete Algorithms"},{"key":"14_CR133","doi-asserted-by":"publisher","unstructured":"Lan, Y., Mohamed, M.A.: Parallel quicksort in hypercubes. In: SAC, pp. 740\u2013746. ACM (1992). https:\/\/doi.org\/10.1145\/130069.130085","DOI":"10.1145\/130069.130085"},{"issue":"4","key":"14_CR134","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead, B., Salzberg, S.L.: Fast gapped-read alignment with bowtie 2. Nat. Meth. 9(4), 357 (2012). https:\/\/doi.org\/10.1038\/nmeth.1923","journal-title":"Nat. Meth."},{"issue":"3","key":"14_CR135","doi-asserted-by":"publisher","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead, B., Trapnell, C., Pop, M., Salzberg, S.L.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 10(3), R25 (2009). https:\/\/doi.org\/10.1186\/gb-2009-10-3-r25","journal-title":"Genome Biol."},{"issue":"7","key":"14_CR136","doi-asserted-by":"publisher","first-page":"3468","DOI":"10.1007\/s11227-018-2395-5","volume":"74","author":"B Lao","year":"2018","unstructured":"Lao, B., Nong, G., Chan, W.H., Pan, Y.: Fast induced sorting suffixes on a multicore machine. J. Supercomput. 74(7), 3468\u20133485 (2018). https:\/\/doi.org\/10.1007\/s11227-018-2395-5","journal-title":"J. Supercomput."},{"issue":"12","key":"14_CR137","doi-asserted-by":"publisher","first-page":"1737","DOI":"10.1109\/TC.2018.2842050","volume":"67","author":"B Lao","year":"2018","unstructured":"Lao, B., Nong, G., Chan, W.H., Xie, J.Y.: Fast in-place suffix sorting on a multicore computer. IEEE Trans. Comput. 67(12), 1737\u20131749 (2018). https:\/\/doi.org\/10.1109\/TC.2018.2842050","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"14_CR138","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1006\/jpdc.2001.1808","volume":"62","author":"S Lee","year":"2002","unstructured":"Lee, S., Jeon, M., Kim, D., Sohn, A.: Partitioned parallel radix sort. J. Parallel Distributed Comput. 62(4), 656\u2013668 (2002). https:\/\/doi.org\/10.1006\/jpdc.2001.1808","journal-title":"J. Parallel Distributed Comput."},{"issue":"22","key":"14_CR139","doi-asserted-by":"publisher","first-page":"3274","DOI":"10.1093\/bioinformatics\/btu541","volume":"30","author":"H Li","year":"2014","unstructured":"Li, H.: Fast construction of FM-index for long sequence reads. Bioinform. 30(22), 3274\u20133275 (2014). https:\/\/doi.org\/10.1093\/bioinformatics\/btu541","journal-title":"Bioinform."},{"issue":"14","key":"14_CR140","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H Li","year":"2009","unstructured":"Li, H., Durbin, R.: Fast and accurate short read alignment with burrows-wheeler transform. Bioinform. 25(14), 1754\u20131760 (2009). https:\/\/doi.org\/10.1093\/bioinformatics\/btp324","journal-title":"Bioinform."},{"key":"14_CR141","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-030-00479-8_22","volume-title":"String Processing and Information Retrieval","author":"Z Li","year":"2018","unstructured":"Li, Z., Li, J., Huo, H.: Optimal in-place suffix sorting. In: Gagie, T., Moffat, A., Navarro, G., Cuadros-Vargas, E. (eds.) SPIRE 2018. LNCS, vol. 11147, pp. 268\u2013284. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00479-8_22"},{"issue":"4","key":"14_CR142","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1089\/cmb.2005.12.407","volume":"12","author":"R Lippert","year":"2005","unstructured":"Lippert, R.: Space-efficient whole genome comparisons with Burrows Wheeler transforms. J. Comput. Biol. 12(4), 407\u2013415 (2005). https:\/\/doi.org\/10.1089\/cmb.2005.12.407","journal-title":"J. Comput. Biol."},{"issue":"3","key":"14_CR143","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1109\/TCBB.2015.2430314","volume":"13","author":"Y Liu","year":"2016","unstructured":"Liu, Y., Hankeln, T., Schmidt, B.: Parallel and space-efficient construction of burrows-wheeler transform and suffix array for big genome data. IEEE\/ACM Trans. Comput. Biol. Bioinform. 13(3), 592\u2013598 (2016). https:\/\/doi.org\/10.1109\/TCBB.2015.2430314","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"14_CR144","series-title":"SpringerBriefs in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-030-55108-7_3","volume-title":"Construction of Fundamental Data Structures for Strings","author":"FA Louza","year":"2020","unstructured":"Louza, F.A., Gog, S., Telles, G.P.: Induced suffix sorting. In: Construction of Fundamental Data Structures for Strings. SCS, pp. 23\u201340. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-55108-7_3"},{"key":"14_CR145","doi-asserted-by":"publisher","unstructured":"Louza, F.A., Telles, G.P., Hoffmann, S., de Aguiar Ciferri, C.D.: Generalized enhanced suffix array construction in external memory. Algorithms Mol. Biol. 12(1), 26:1\u201326:16 (2017). https:\/\/doi.org\/10.1186\/s13015-017-0117-9","DOI":"10.1186\/s13015-017-0117-9"},{"key":"14_CR146","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032886","volume-title":"Sorting: A Distribution Theory","author":"HM Mahmoud","year":"2000","unstructured":"Mahmoud, H.M.: Sorting: A Distribution Theory. John Wiley, Hoboken (2000)"},{"issue":"3","key":"14_CR147","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.tcs.2007.07.013","volume":"387","author":"V M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Rank and select revisited and extended. Theor. Comput. Sci. 387(3), 332\u2013347 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.07.013","journal-title":"Theor. Comput. Sci."},{"key":"14_CR148","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/978-3-540-30551-4_59","volume-title":"Algorithms and Computation","author":"V M\u00e4kinen","year":"2004","unstructured":"M\u00e4kinen, V., Navarro, G., Sadakane, K.: Advantages of Backward Searching \u2014 Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 681\u2013692. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30551-4_59"},{"issue":"2","key":"14_CR149","doi-asserted-by":"publisher","first-page":"585","DOI":"10.2298\/CSIS110606004M","volume":"9","author":"C Makris","year":"2012","unstructured":"Makris, C.: Wavelet trees: a survey. Comput. Sci. Inf. Syst. 9(2), 585\u2013625 (2012). https:\/\/doi.org\/10.2298\/CSIS110606004M","journal-title":"Comput. Sci. Inf. Syst."},{"issue":"5","key":"14_CR150","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993). https:\/\/doi.org\/10.1137\/0222058","journal-title":"SIAM J. Comput."},{"key":"14_CR151","doi-asserted-by":"publisher","unstructured":"Marchet, C., Boucher, C., Puglisi, S.J., Medvedev, P., Salson, M., Chikhi, R.: Data structures based on k-mers for querying large collections of sequencing datasets. bioRxiv (2020). https:\/\/doi.org\/10.1101\/866756","DOI":"10.1101\/866756"},{"issue":"1","key":"14_CR152","first-page":"5","volume":"6","author":"PM McIlroy","year":"1993","unstructured":"McIlroy, P.M., Bostic, K., McIlroy, M.D.: Engineering radix sort. Comput. Syst. 6(1), 5\u201327 (1993)","journal-title":"Comput. Syst."},{"key":"14_CR153","doi-asserted-by":"publisher","unstructured":"Menon, R.K., Bhat, G.P., Schatz, M.C.: Rapid parallel genome indexing with mapreduce. In: MapReduce, pp. 51\u201358 (2011). https:\/\/doi.org\/10.1145\/1996092.1996104","DOI":"10.1145\/1996092.1996104"},{"issue":"2","key":"14_CR154","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1142\/S0129626411000187","volume":"21","author":"D Merrill","year":"2011","unstructured":"Merrill, D., Grimshaw, A.S.: High performance and scalable radix sorting: a case study of implementing dynamic parallelism for GPU computing. Parallel Process. Lett. 21(2), 245\u2013272 (2011). https:\/\/doi.org\/10.1142\/S0129626411000187","journal-title":"Parallel Process. Lett."},{"key":"14_CR155","doi-asserted-by":"publisher","unstructured":"Metwally, A.A., Kandil, A.H., Abouelhoda, M.: Distributed suffix array construction algorithms: Comparison of two algorithms. In: CIBEC, pp. 27\u201330. IEEE (2016). https:\/\/doi.org\/10.1109\/CIBEC.2016.7836092","DOI":"10.1109\/CIBEC.2016.7836092"},{"issue":"4","key":"14_CR156","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"DR Morrison","year":"1968","unstructured":"Morrison, D.R.: PATRICIA - practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514\u2013534 (1968). https:\/\/doi.org\/10.1145\/321479.321481","journal-title":"J. ACM"},{"key":"14_CR157","doi-asserted-by":"publisher","unstructured":"Munro, J.I., Navarro, G., Nekrich, Y.: Space-efficient construction of compressed indexes in deterministic linear time. In: SODA, pp. 408\u2013424. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.26","DOI":"10.1137\/1.9781611974782.26"},{"key":"14_CR158","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.tcs.2015.11.011","volume":"638","author":"JI Munro","year":"2016","unstructured":"Munro, J.I., Nekrich, Y., Vitter, J.S.: Fast construction of wavelet trees. Theor. Comput. Sci. 638, 91\u201397 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2015.11.011","journal-title":"Theor. Comput. Sci."},{"key":"14_CR159","doi-asserted-by":"crossref","unstructured":"Musser, D.R.: Introspective sorting and selection algorithms. Softw. Pract. Exp. 27(8), 983\u2013993 (1997). https:\/\/doi.org\/10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-%23","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#"},{"key":"14_CR160","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2013.07.004","volume":"25","author":"G Navarro","year":"2014","unstructured":"Navarro, G.: Wavelet trees for all. J. Discrete Algorithms 25, 2\u201320 (2014). https:\/\/doi.org\/10.1016\/j.jda.2013.07.004","journal-title":"J. Discrete Algorithms"},{"key":"14_CR161","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/3-540-63220-4_54","volume-title":"Combinatorial Pattern Matching","author":"G Navarro","year":"1997","unstructured":"Navarro, G., Kitajima, J.P., Ribeiro-Neto, B.A., Ziviani, N.: Distributed generation of suffix arrays. In: Apostolico, A., Hein, J. (eds.) CPM 1997. LNCS, vol. 1264, pp. 102\u2013115. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63220-4_54"},{"key":"14_CR162","doi-asserted-by":"publisher","first-page":"69","DOI":"10.2197\/ipsjdc.4.69","volume":"4","author":"W Ng","year":"2008","unstructured":"Ng, W., Kakehi, K.: Merging string sequences by longest common prefixes. IPSJ Digital Courier 4, 69\u201378 (2008)","journal-title":"IPSJ Digital Courier"},{"key":"14_CR163","doi-asserted-by":"publisher","unstructured":"Nong, G., Chan, W.H., Hu, S.Q., Wu, Y.: Induced sorting suffixes in external memory. ACM Trans. Inf. Syst. 33(3), 12:1\u201312:15 (2015). https:\/\/doi.org\/10.1145\/2699665","DOI":"10.1145\/2699665"},{"issue":"10","key":"14_CR164","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1109\/TC.2010.188","volume":"60","author":"G Nong","year":"2011","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Two efficient algorithms for linear time suffix array construction. IEEE Trans. Comput. 60(10), 1471\u20131484 (2011). https:\/\/doi.org\/10.1109\/TC.2010.188","journal-title":"IEEE Trans. Comput."},{"key":"14_CR165","doi-asserted-by":"publisher","unstructured":"Obeya, O., Kahssay, E., Fan, E., Shun, J.: Theoretically-efficient and practical parallel in-place radix sorting. In: SPAA, pp. 213\u2013224. ACM (2019). https:\/\/doi.org\/10.1145\/3323165.3323198","DOI":"10.1145\/3323165.3323198"},{"key":"14_CR166","unstructured":"Ohlebusch, E.: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag (2013)"},{"key":"14_CR167","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.jda.2013.06.002","volume":"25","author":"E Ohlebusch","year":"2014","unstructured":"Ohlebusch, E., Beller, T., Abouelhoda, M.I.: Computing the burrows-wheeler transform of a string and its reverse in parallel. J. Discrete Algorithms 25, 21\u201333 (2014). https:\/\/doi.org\/10.1016\/j.jda.2013.06.002","journal-title":"J. Discrete Algorithms"},{"key":"14_CR168","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-642-16321-0_36","volume-title":"String Processing and Information Retrieval","author":"E Ohlebusch","year":"2010","unstructured":"Ohlebusch, E., Gog, S., K\u00fcgel, A.: Computing matching statistics and maximal exact matches on compressed full-text indexes. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 347\u2013358. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16321-0_36"},{"key":"14_CR169","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-642-34109-0_40","volume-title":"String Processing and Information Retrieval","author":"V Osipov","year":"2012","unstructured":"Osipov, V.: Parallel suffix array construction for shared memory architectures. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol. 7608, pp. 379\u2013384. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-34109-0_40"},{"key":"14_CR170","doi-asserted-by":"publisher","unstructured":"Patel, R.A., Zhang, Y., Mak, J., Davidson, A., Owens, J.D.: Parallel lossless data compression on the GPU. In: InPar, pp. 1\u20139. IEEE (2012). https:\/\/doi.org\/10.1109\/InPar.2012.6339599","DOI":"10.1109\/InPar.2012.6339599"},{"key":"14_CR171","doi-asserted-by":"publisher","unstructured":"Pockrandt, C.: Approximate String Matching: Improving Data Structures and Algorithms. Ph.D. thesis, Free University of Berlin, Dahlem, Germany (2019). https:\/\/doi.org\/10.17169\/refubium-2185","DOI":"10.17169\/refubium-2185"},{"issue":"2","key":"14_CR172","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/1242471.1242472","volume":"39","author":"SJ Puglisi","year":"2007","unstructured":"Puglisi, S.J., Smyth, W.F., Turpin, A.: A taxonomy of suffix array construction algorithms. ACM Comput. Surv. 39(2), 4 (2007). https:\/\/doi.org\/10.1145\/1242471.1242472","journal-title":"ACM Comput. Surv."},{"key":"14_CR173","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/945394.945401","volume":"6","author":"N Rahman","year":"2001","unstructured":"Rahman, N., Raman, R.: Adapting radix sort to the memory hierarchy. ACM J. Exp. Algorithmics 6, 7 (2001). https:\/\/doi.org\/10.1145\/945394.945401","journal-title":"ACM J. Exp. Algorithmics"},{"key":"14_CR174","volume-title":"Intel Threading Building Blocks - Outfitting C++ for Multi-core Processor Parallelism","author":"J Reinders","year":"2007","unstructured":"Reinders, J.: Intel Threading Building Blocks - Outfitting C++ for Multi-core Processor Parallelism. O\u2019Reilly, Newton (2007)"},{"key":"14_CR175","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.jbiotec.2017.07.017","volume":"261","author":"K Reinert","year":"2017","unstructured":"Reinert, K., et al.: The seqan c++ template library for efficient sequence analysis: a resource for programmers. J. Biotechnol. 261, 157\u2013168 (2017). https:\/\/doi.org\/10.1016\/j.jbiotec.2017.07.017","journal-title":"J. Biotechnol."},{"key":"14_CR176","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/3-540-40996-3_35","volume-title":"Algorithms and Computation","author":"K Sadakane","year":"2000","unstructured":"Sadakane, K.: Compressed text databases with efficient query algorithms based on the compressed suffix array. In: Goos, G., Hartmanis, J., van Leeuwen, J., Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol. 1969, pp. 410\u2013421. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-40996-3_35"},{"key":"14_CR177","unstructured":"Sadakane, K.: Succinct representations of lcp information and improvements in the compressed suffix arrays. In: SODA, pp. 225\u2013232. ACM\/SIAM (2002)"},{"key":"14_CR178","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-63138-0_2","volume-title":"Solving Irregularly Structured Problems in Parallel","author":"P Sanders","year":"1997","unstructured":"Sanders, P., Hansch, T.: Efficient massively parallel quicksort. In: Bilardi, G., Ferreira, A., L\u00fcling, R., Rolim, J. (eds.) IRREGULAR 1997. LNCS, vol. 1253, pp. 13\u201324. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63138-0_2"},{"key":"14_CR179","doi-asserted-by":"publisher","unstructured":"Sanders, P., Schlag, S., M\u00fcller, I.: Communication efficient algorithms for fundamental big data problems. In: BigData, pp. 15\u201323. IEEE (2013). https:\/\/doi.org\/10.1109\/BigData.2013.6691549","DOI":"10.1109\/BigData.2013.6691549"},{"key":"14_CR180","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1007\/978-3-540-30140-0_69","volume-title":"Algorithms \u2013 ESA 2004","author":"P Sanders","year":"2004","unstructured":"Sanders, P., Winkel, S.: Super scalar sample sort. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 784\u2013796. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30140-0_69"},{"key":"14_CR181","doi-asserted-by":"publisher","unstructured":"Satish, N., Harris, M.J., Garland, M.: Designing efficient sorting algorithms for manycore GPUs. In: IPDPS, pp. 1\u201310. IEEE (2009). https:\/\/doi.org\/10.1109\/IPDPS.2009.5161005","DOI":"10.1109\/IPDPS.2009.5161005"},{"issue":"2","key":"14_CR182","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1145\/321160.321170","volume":"10","author":"JC Shepherdson","year":"1963","unstructured":"Shepherdson, J.C., Sturgis, H.E.: Computability of recursive functions. J. ACM 10(2), 217\u2013255 (1963). https:\/\/doi.org\/10.1145\/321160.321170","journal-title":"J. ACM"},{"key":"14_CR183","doi-asserted-by":"publisher","unstructured":"Shun, J.: Fast parallel computation of longest common prefixes. In: SC, pp. 387\u2013398. IEEE (2014). https:\/\/doi.org\/10.1109\/SC.2014.37","DOI":"10.1109\/SC.2014.37"},{"key":"14_CR184","doi-asserted-by":"publisher","unstructured":"Shun, J.: Parallel wavelet tree construction. In: DCC, pp. 63\u201372. IEEE (2015). https:\/\/doi.org\/10.1109\/DCC.2015.7","DOI":"10.1109\/DCC.2015.7"},{"key":"14_CR185","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104516","volume":"273","author":"J Shun","year":"2020","unstructured":"Shun, J.: Improved parallel construction of wavelet trees and rank\/select structures. Inf. Comput. 273, 104516 (2020). https:\/\/doi.org\/10.1016\/j.ic.2020.104516","journal-title":"Inf. Comput."},{"key":"14_CR186","doi-asserted-by":"publisher","unstructured":"Shun, J., et al.: Brief announcement: the problem based benchmark suite. In: SPAA, pp. 68\u201370. ACM (2012). https:\/\/doi.org\/10.1145\/2312005.2312018","DOI":"10.1145\/2312005.2312018"},{"issue":"12","key":"14_CR187","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1093\/bioinformatics\/btq217","volume":"26","author":"JT Simpson","year":"2010","unstructured":"Simpson, J.T., Durbin, R.: Efficient construction of an assembly string graph using the FM-index. Bioinformatics 26(12), 367\u2013373 (2010). https:\/\/doi.org\/10.1093\/bioinformatics\/btq217","journal-title":"Bioinformatics"},{"key":"14_CR188","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1007\/978-3-540-74466-5_72","volume-title":"Euro-Par 2007 Parallel Processing","author":"J Singler","year":"2007","unstructured":"Singler, J., Sanders, P., Putze, F.: MCSTL: the multi-core standard template library. In: Kermarrec, A.-M., Boug\u00e9, L., Priol, T. (eds.) Euro-Par 2007. LNCS, vol. 4641, pp. 682\u2013694. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74466-5_72"},{"key":"14_CR189","unstructured":"Sinha, R., Zobel, J.: Efficient trie-based sorting of large sets of strings. In: ACSC, pp. 11\u201318. Australian Computer Society (2003)"},{"key":"14_CR190","doi-asserted-by":"publisher","unstructured":"Sir\u00e9n, J.: Indexing variation graphs. In: ALENEX, pp. 13\u201327. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974768.2","DOI":"10.1137\/1.9781611974768.2"},{"issue":"2","key":"14_CR191","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1093\/bioinformatics\/btz575","volume":"36","author":"J Sir\u00e9n","year":"2020","unstructured":"Sir\u00e9n, J., Garrison, E., Novak, A.M., Paten, B., Durbin, R.: Haplotype-aware graph indexes. Bioinformatics 36(2), 400\u2013407 (2020). https:\/\/doi.org\/10.1093\/bioinformatics\/btz575","journal-title":"Bioinformatics"},{"key":"14_CR192","doi-asserted-by":"publisher","unstructured":"Sohn, A., Kodama, Y.: Load balanced parallel radix sort. In: ICS, pp. 305\u2013312. ACM (1998). https:\/\/doi.org\/10.1145\/277830.277903","DOI":"10.1145\/277830.277903"},{"key":"14_CR193","doi-asserted-by":"publisher","unstructured":"Solomonik, E., Kal\u00e9, L.V.: Highly scalable parallel sorting. In: IPDPS, pp. 1\u201312. IEEE (2010). https:\/\/doi.org\/10.1109\/IPDPS.2010.5470406","DOI":"10.1109\/IPDPS.2010.5470406"},{"key":"14_CR194","doi-asserted-by":"publisher","unstructured":"Stehle, E., Jacobsen, H.: A memory bandwidth-efficient hybrid radix sort on GPUs. In: SIGMOD Conference, pp. 417\u2013432. ACM (2017). https:\/\/doi.org\/10.1145\/3035918.3064043","DOI":"10.1145\/3035918.3064043"},{"key":"14_CR195","doi-asserted-by":"publisher","unstructured":"Sun, W., Ma, Z.: Parallel lexicographic names construction with CUDA. In: ICPADS, pp. 913\u2013918. IEEE Computer Society (2009). https:\/\/doi.org\/10.1109\/ICPADS.2009.31","DOI":"10.1109\/ICPADS.2009.31"},{"key":"14_CR196","doi-asserted-by":"publisher","unstructured":"Sundar, H., Malhotra, D., Biros, G.: Hyksort: a new variant of hypercube quicksort on distributed memory architectures. In: ICS, pp. 293\u2013302. ACM (2013). https:\/\/doi.org\/10.1145\/2464996.2465442","DOI":"10.1145\/2464996.2465442"},{"key":"14_CR197","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-642-21458-5_19","volume-title":"Combinatorial Pattern Matching","author":"G Tischler","year":"2011","unstructured":"Tischler, G.: On wavelet tree construction. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 208\u2013218. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21458-5_19"},{"key":"14_CR198","doi-asserted-by":"publisher","unstructured":"Trinidad, J.F.M., Cumplido-Parra, R., Uribe, C.F.: An FPGA-based parallel sorting architecture for the burrows wheeler transform. In: ReConFig. IEEE Computer Society (2005). https:\/\/doi.org\/10.1109\/RECONFIG.2005.9","DOI":"10.1109\/RECONFIG.2005.9"},{"issue":"3","key":"14_CR199","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249\u2013260 (1995). https:\/\/doi.org\/10.1007\/BF01206331","journal-title":"Algorithmica"},{"issue":"8","key":"14_CR200","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990). https:\/\/doi.org\/10.1145\/79173.79181","journal-title":"Commun. ACM"},{"key":"14_CR201","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-319-20119-1_13","volume-title":"High Performance Computing","author":"H Wang","year":"2015","unstructured":"Wang, H., et al.: BWTCP: a parallel method for constructing BWT in large collection of genomic reads. In: Kunkel, J.M., Ludwig, T. (eds.) ISC High Performance 2015. LNCS, vol. 9137, pp. 171\u2013178. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-20119-1_13"},{"issue":"12","key":"14_CR202","doi-asserted-by":"publisher","first-page":"3466","DOI":"10.1002\/cpe.3867","volume":"28","author":"L Wang","year":"2016","unstructured":"Wang, L., Baxter, S., Owens, J.D.: Fast parallel skew and prefix-doubling suffix array construction on the GPU. Concurr. Comput. Pract. Exp. 28(12), 3466\u20133484 (2016). https:\/\/doi.org\/10.1002\/cpe.3867","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"14_CR203","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-642-23397-5_16","volume-title":"Euro-Par 2011 Parallel Processing","author":"J Wassenberg","year":"2011","unstructured":"Wassenberg, J., Sanders, P.: Engineering a multi-core radix sort. In: Jeannot, E., Namyst, R., Roman, J. (eds.) Euro-Par 2011. LNCS, vol. 6853, pp. 160\u2013169. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23397-5_16"},{"key":"14_CR204","doi-asserted-by":"publisher","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: SWAT (FOCS), pp. 1\u201311. IEEE (1973). https:\/\/doi.org\/10.1109\/SWAT.1973.13","DOI":"10.1109\/SWAT.1973.13"},{"key":"14_CR205","doi-asserted-by":"publisher","unstructured":"Wild, S., Nebel, M.E., Neininger, R.: Average case and distributional analysis of dual-pivot quicksort. ACM Trans. Algorithms 11(3), 22:1\u201322:42 (2015). https:\/\/doi.org\/10.1145\/2629340","DOI":"10.1145\/2629340"},{"key":"14_CR206","series-title":"Communications in Computer and Information Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-981-15-2767-8_29","volume-title":"Parallel Architectures, Algorithms and Programming","author":"Y Wu","year":"2020","unstructured":"Wu, Y., Lao, B., Ma, X., Nong, G.: An improved algorithm for building suffix array in external memory. In: Shen, H., Sang, Y. (eds.) PAAP 2019. CCIS, vol. 1163, pp. 320\u2013330. Springer, Singapore (2020). https:\/\/doi.org\/10.1007\/978-981-15-2767-8_29"},{"key":"14_CR207","doi-asserted-by":"publisher","unstructured":"Xiaochen, T., Rocki, K., Suda, R.: Register level sort algorithm on multi-core SIMD processors. In: IA3@SC, pp. 9:1\u20139:8. ACM (2013). https:\/\/doi.org\/10.1145\/2535753.2535762","DOI":"10.1145\/2535753.2535762"},{"key":"14_CR208","series-title":"Communications in Computer and Information Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-981-15-2767-8_30","volume-title":"Parallel Architectures, Algorithms and Programming","author":"JY Xie","year":"2020","unstructured":"Xie, J.Y., Lao, B., Nong, G.: In-place suffix sorting on a multicore computer with better design. In: Shen, H., Sang, Y. (eds.) PAAP 2019. CCIS, vol. 1163, pp. 331\u2013342. Springer, Singapore (2020). https:\/\/doi.org\/10.1007\/978-981-15-2767-8_30"},{"key":"14_CR209","doi-asserted-by":"publisher","unstructured":"Yin, Z., et al.: Efficient parallel sort on AVX-512-based multi-core and many-core architectures. In: HPCC\/SmartCity\/DSS, pp. 168\u2013176. IEEE (2019). https:\/\/doi.org\/10.1109\/HPCC\/SmartCity\/DSS.2019.00038","DOI":"10.1109\/HPCC\/SmartCity\/DSS.2019.00038"},{"key":"14_CR210","unstructured":"Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: Cluster computing with working sets. In: HotCloud. USENIX Association (2010)"},{"key":"14_CR211","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-642-38527-8_15","volume-title":"Experimental Algorithms","author":"D Zhou","year":"2013","unstructured":"Zhou, D., Andersen, D.G., Kaminsky, M.: Space-efficient, high-performance rank and select structures on uncompressed bit sequences. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 151\u2013163. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38527-8_15"},{"key":"14_CR212","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.parco.2019.06.002","volume":"87","author":"G Zhu","year":"2019","unstructured":"Zhu, G., Guo, C., Lu, L., Huang, Z., Yuan, C., Gu, R., Huang, Y.: DGST: efficient and scalable suffix tree construction on distributed data-parallel platforms. Parallel Comput. 87, 87\u2013102 (2019). https:\/\/doi.org\/10.1016\/j.parco.2019.06.002","journal-title":"Parallel Comput."},{"issue":"3","key":"14_CR213","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23(3), 337\u2013343 (1977). https:\/\/doi.org\/10.1109\/TIT.1977.1055714","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","Algorithms for Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-21534-6_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:04:33Z","timestamp":1673985873000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-21534-6_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031215339","9783031215346"],"references-count":213,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-21534-6_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"18 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}