{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:34:13Z","timestamp":1773275653222,"version":"3.50.1"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319199283","type":"print"},{"value":"9783319199290","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19929-0_28","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T13:09:49Z","timestamp":1434373789000},"page":"329-342","source":"Crossref","is-referenced-by-count":25,"title":["Parallel External Memory Suffix Sorting"],"prefix":"10.1007","author":[{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"Kempa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"issue":"1","key":"28_CR1","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)","journal-title":"J. Discrete Algorithms"},{"issue":"5","key":"28_CR2","doi-asserted-by":"publisher","first-page":"1552","DOI":"10.1137\/S0097539797329889","volume":"30","author":"A Andersson","year":"2000","unstructured":"Andersson, A., Hagerup, T., H\u00e5stad, J., Petersson, O.: Tight bounds for searching a sorted array of strings. SIAM J. Comput. 30(5), 1552\u20131578 (2000)","journal-title":"SIAM J. Comput."},{"key":"28_CR3","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF01762122","volume":"3","author":"A Apostolico","year":"1988","unstructured":"Apostolico, A., Iliopoulos, C.S., Landau, G.M., Schieber, B., Vishkin, U.: Parallel construction of a suffix tree with applications. Algorithmica 3, 347\u2013365 (1988)","journal-title":"Algorithmica"},{"issue":"11","key":"28_CR4","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1109\/5.892709","volume":"88","author":"A Apostolico","year":"2000","unstructured":"Apostolico, A., Lonardi, S.: Off-line compression by greedy textual substitution. Proc. IEEE 88(11), 1733\u20131744 (2000)","journal-title":"Proc. IEEE"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Bingmann, T., Fischer, J., Osipov, V.: Inducing suffix and LCP arrays in external memory. In: Sanders, P., Zeh, N. (eds.) ALENEX 2013. pp. 88\u2013102. SIAM (2013)","DOI":"10.1137\/1.9781611972931.8"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Shun, J.: A simple parallel cartesian tree algorithm and its application to suffix tree construction. In: M\u00fcller-Hannemann, M., Werneck, R.F.F. (eds.) ALENEX 2011, pp. 48\u201358. SIAM (2011)","DOI":"10.1137\/1.9781611972917.5"},{"issue":"1","key":"28_CR7","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)","journal-title":"Algorithmica"},{"issue":"6","key":"28_CR8","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. Exper. 38(6), 589\u2013637 (2008)","journal-title":"Softw. Pract. Exper."},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Deo, M., Keely, S.: Parallel suffix array and least common prefix for the GPU. In: Nicolau, A., Shen, X., Amarasinghe, S.P., Vuduc, R.W. (eds.) PPoPP 2013, pp. 197\u2013206. ACM (2013)","DOI":"10.1145\/2517327.2442536"},{"issue":"6","key":"28_CR10","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)","journal-title":"J. ACM"},{"issue":"4","key":"28_CR11","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"issue":"3","key":"28_CR12","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)","journal-title":"Algorithmica"},{"key":"28_CR13","first-page":"66","volume-title":"Information Retrieval: Data Structures and Algorithms","author":"GH Gonnet","year":"1992","unstructured":"Gonnet, G.H., Baeza-Yates, R.A., Snider, T.: New indices for text: pat trees and pat arrays. In: Frakes, W.B., Baeza-Yates, R. (eds.) Information Retrieval: Data Structures and Algorithms, pp. 66\u201382. Prentice-Hall, Englewood Cliffs (1992)"},{"issue":"2","key":"28_CR14","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"28_CR15","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D.: Engineering a lightweight external memory suffix array construction algorithm. In: Iliopoulos, C.S., Langiu, A. (eds.) ICABD 2014, CEUR Workshop Proceedings, vol. 1146, pp. 53\u201360 (2014). \n                    CEUR-WS.org"},{"key":"28_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-642-38905-4_19","volume-title":"Combinatorial Pattern Matching","author":"J K\u00e4rkk\u00e4inen","year":"2013","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Linear time Lempel-Ziv factorization: simple, fast, small. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 189\u2013200. Springer, Heidelberg (2013)"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Lempel-Ziv parsing in external memory. In: Bilgin, A., Marcellin, M.W., Serra-Sagrist\u00e0, J., Storer, J.A. (eds.) DCC 2014, pp. 153\u2013162. IEEE (2014)","DOI":"10.1109\/DCC.2014.78"},{"key":"28_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/978-3-319-07566-2_24","volume-title":"Combinatorial Pattern Matching","author":"J K\u00e4rkk\u00e4inen","year":"2014","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: String range matching. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 232\u2013241. Springer, Heidelberg (2014)"},{"issue":"6","key":"28_CR19","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)","journal-title":"J. ACM"},{"issue":"9","key":"28_CR20","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)","journal-title":"Parallel Comput."},{"issue":"3","key":"28_CR21","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)","journal-title":"Genome Biol."},{"issue":"14","key":"28_CR22","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. Bioinformatics 25(14), 1754\u20131760 (2009)","journal-title":"Bioinformatics"},{"key":"28_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-38905-4_20","volume-title":"Combinatorial Pattern Matching","author":"FA Louza","year":"2013","unstructured":"Louza, F.A., Telles, G.P., Ciferri, C.D.D.A.: External memory generalized suffix and LCP arrays construction. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 201\u2013210. Springer, Heidelberg (2013)"},{"issue":"5","key":"28_CR24","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, G.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"28_CR25","unstructured":"Mori, Y.: libdivsufsort, a C library for suffix array construction. \n                    http:\/\/code.google.com\/p\/libdivsufsort\/"},{"issue":"4","key":"28_CR26","doi-asserted-by":"publisher","first-page":"1429","DOI":"10.3390\/a2041429","volume":"2","author":"R Nakamura","year":"2009","unstructured":"Nakamura, R., Inenaga, S., Bannai, H., Funamoto, T., Takeda, M., Shinohara, A.: Linear-time text compression by longest-first substitution. Algorithms 2(4), 1429\u20131448 (2009)","journal-title":"Algorithms"},{"issue":"1","key":"28_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2518175","volume":"32","author":"G Nong","year":"2014","unstructured":"Nong, G., Chan, W.H., Zhang, S., Guan, X.F.: Suffix array construction in external memory using d-critical substrings. ACM Trans. Inf. Syst. 32(1), 1 (2014)","journal-title":"ACM Trans. Inf. Syst."},{"key":"28_CR28","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)"},{"issue":"2","key":"28_CR29","doi-asserted-by":"publisher","first-page":"31","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), 31 (2007). Article 4","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"28_CR30","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1101\/gr.126953.111","volume":"22","author":"JT Simpson","year":"2012","unstructured":"Simpson, J.T., Durbin, R.: Efficient de novo assembly of large genomes using compressed data structures. Genome Res. 22(3), 549\u2013556 (2012)","journal-title":"Genome Res."},{"key":"28_CR31","unstructured":"Tischler, G.: Faster average case low memory semi-external construction of the Burrows-Wheeler transform. In: Iliopoulos, C.S., Langiu, A. (eds.) ICABD 2014, CEUR Workshop Proceedings, vol. 1146, pp. 61\u201368 (2014). \n                    CEUR-WS.org"},{"key":"28_CR32","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: SWAT 1973, pp. 1\u201311. IEEE (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"3","key":"28_CR33","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1093\/comjnl\/42.3.193","volume":"42","author":"HE Williams","year":"1999","unstructured":"Williams, H.E., Zobel, J.: Compressing integers for fast file access. Comput. J. 42(3), 193\u2013201 (1999)","journal-title":"Comput. J."},{"issue":"3","key":"28_CR34","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. Theor. 23(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theor."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19929-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T05:52:10Z","timestamp":1559195530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-19929-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319199283","9783319199290"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19929-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}