{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:29:34Z","timestamp":1761611374396,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480953"},{"type":"electronic","value":"9783662480960"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48096-0_44","type":"book-chapter","created":{"date-parts":[[2015,7,24]],"date-time":"2015-07-24T06:16:03Z","timestamp":1437718563000},"page":"573-587","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Fast Parallel Suffix Array on the GPU"],"prefix":"10.1007","author":[{"given":"Leyuan","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sean","family":"Baxter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John D.","family":"Owens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,25]]},"reference":[{"key":"44_CR1","doi-asserted-by":"crossref","unstructured":"Davidson, A., Tarjan, D., Garland, M., Owens, J.D.: Efficient parallel merge sort for fixed and variable length keys. In: Proceedings of Innovative Parallel Computing, InPar 2012 (2012)","DOI":"10.1109\/InPar.2012.6339592"},{"key":"44_CR2","doi-asserted-by":"crossref","unstructured":"Deo, M., Keely, S.: Parallel suffix array and least common prefix for the GPU. In: Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2013, pp. 197\u2013206 (2013)","DOI":"10.1145\/2517327.2442536"},{"key":"44_CR3","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)","journal-title":"Theor. Comput. Sci."},{"key":"44_CR4","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, pp. 390\u2013398(2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"Green, O., McColl, R., Bader, D.A.: GPU merge path: a GPU mergingalgorithm. In: Proceedings of the 26th ACM International Conference on Supercomputing, ICS 2012, pp. 331\u2013340 (2012)","DOI":"10.1145\/2304576.2304621"},{"key":"44_CR6","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: Proceedings of the 30th International Conference on Automata, Languages and Programming, ICALP 2003, pp. 943\u2013955. Springer, Heidelberg (2003). http:\/\/dl.acm.org\/citation.cfm?id=1759210.1759301"},{"key":"44_CR7","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Miller, R.E., Rosenberg, A.L.: Rapid identification of repeated patterns in strings, trees and arrays. In: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing STOC 1972, pp. 125\u2013136 (1972)","DOI":"10.1145\/800152.804905"},{"issue":"3","key":"44_CR8","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.tcs.2007.07.017","volume":"387","author":"NJ Larsson","year":"2007","unstructured":"Larsson, N.J., Sadakane, K.: Faster suffix sorting. Theor. Comput. Sci. 387(3), 258\u2013272 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"44_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/MM.2008.31","volume":"28","author":"E Lindholm","year":"2008","unstructured":"Lindholm, E., Nickolls, J., Oberman, S., Montrym, J.: NVIDIA Tesla: a unified graphics and computing architecture. IEEE Micro 28(2), 39\u201355 (2008)","journal-title":"IEEE Micro"},{"key":"44_CR10","unstructured":"Liu, C.M., Luo, R., Lam, T.W.: GPU-accelerated BWT construction for large collection of short reads (2014). arXiv preprint arXiv:1401.7457"},{"key":"44_CR11","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319\u2013327. SODA \u201990 (1990)"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"Merrill, D., Grimshaw, A.: Revisiting sorting for GPGPU stream architectures. Technical report CS2010-03, Department of Computer Science, University of Virginia (2010)","DOI":"10.1145\/1854273.1854344"},{"key":"44_CR13","unstructured":"Mori, Y.: libdivsufsort, version 2.0.1 (2010). https:\/\/code.google.com\/p\/libdivsufsort\/wiki\/SACA_Benchmarks"},{"key":"44_CR14","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/1365490.1365500","volume":"6","author":"J Nickolls","year":"2008","unstructured":"Nickolls, J., Buck, I., Garland, M., Skadron, K.: Scalable parallel programming with CUDA. ACM Queue 6, 40\u201353 (2008)","journal-title":"ACM Queue"},{"key":"44_CR15","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)"},{"key":"44_CR16","unstructured":"Pantaleoni, J.: A massively parallel algorithm for constructing the BWT of large string sets, October 2014. arXiv.org abs\/1410.0562(1410.0562v1)"},{"key":"44_CR17","doi-asserted-by":"crossref","unstructured":"Patel, R.A., Zhang, Y., Mak, J., Owens, J.D.: Parallel lossless data compression on the GPU. In: Proceedings of Innovative Parallel Computing (2012)","DOI":"10.1109\/InPar.2012.6339599"},{"key":"44_CR18","doi-asserted-by":"crossref","unstructured":"Satish, N., Harris, M., Garland, M.: Designing efficient sorting algorithms for manycore GPUs. In: Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (2009)","DOI":"10.1109\/IPDPS.2009.5161005"}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2015: Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48096-0_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T16:59:51Z","timestamp":1748537991000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48096-0_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480953","9783662480960"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48096-0_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"25 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}