{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T18:12:37Z","timestamp":1725991957385},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030004781"},{"type":"electronic","value":"9783030004798"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-030-00479-8_22","type":"book-chapter","created":{"date-parts":[[2018,9,13]],"date-time":"2018-09-13T14:58:18Z","timestamp":1536850698000},"page":"268-284","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Optimal In-Place Suffix Sorting"],"prefix":"10.1007","author":[{"given":"Zhize","family":"Li","sequence":"first","affiliation":[]},{"given":"Jian","family":"Li","sequence":"additional","affiliation":[]},{"given":"Hongwei","family":"Huo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,14]]},"reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/3-540-45784-4_35","volume-title":"Algorithms in Bioinformatics","author":"MI Abouelhoda","year":"2002","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: The enhanced suffix array and its applications to genome analysis. In: Guig\u00f3, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol. 2452, pp. 449\u2013463. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45784-4_35"},{"issue":"1","key":"22_CR2","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. Discret. Algorithms 2(1), 53\u201386 (2004)","journal-title":"J. Discret. Algorithms"},{"issue":"4","key":"22_CR3","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1109\/TC.2005.56","volume":"54","author":"D Baron","year":"2005","unstructured":"Baron, D., Bresler, Y.: Antisequential suffix sorting for bwt-based data compression. IEEE Trans. Comput. 54(4), 385\u2013397 (2005)","journal-title":"IEEE Trans. Comput."},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-44888-8_5","volume-title":"Combinatorial Pattern Matching","author":"S Burkhardt","year":"2003","unstructured":"Burkhardt, S., K\u00e4rkk\u00e4inen, J.: Fast lightweight suffix array construction and checking. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol. 2676, pp. 55\u201369. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44888-8_5"},{"key":"22_CR5","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical report 124 (1994)"},{"key":"22_CR6","unstructured":"Clark, D.: Compact pat trees. Ph.D. thesis, University of Waterloo (1996)"},{"key":"22_CR7","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"22_CR8","unstructured":"Dhaliwal, J., Puglisi, S.J., Turpin, A.: Trends in suffix sorting: a survey of low memory algorithms. In: Proceedings of the Thirty-fifth Australasian Computer Science Conference, vol. 122, pp. 91\u201398. Australian Computer Society, Inc. (2012)"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 137\u2013143. IEEE (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"key":"22_CR10","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), pp. 390\u2013398. IEEE (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"22_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-540-73420-8_47","volume-title":"Automata, Languages and Programming","author":"G Franceschini","year":"2007","unstructured":"Franceschini, G., Muthukrishnan, S.: In-place suffix sorting. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 533\u2013545. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73420-8_47"},{"issue":"2","key":"22_CR12","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":"22_CR13","unstructured":"Hon, W.K., Sadakane, K., Sung, W.K.: Breaking a time-and-space barrier in constructing full-text indices. In: Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), pp. 251\u2013260. IEEE (2003)"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Huo, H., Chen, L., Vitter, J.S., Nekrich, Y.: A practical implementation of compressed suffix arrays with applications to self-indexing. In: Data Compression Conference (DCC), pp. 292\u2013301. IEEE (2014)","DOI":"10.1109\/DCC.2014.49"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Huo, H., et al.: CS2A: a compressed suffix array-based method for short read alignment. In: Data Compression Conference (DCC), pp. 271\u2013278. IEEE (2016)","DOI":"10.1109\/DCC.2016.58"},{"key":"22_CR16","unstructured":"Itoh, H., Tanaka, H.: An efficient method for in memory construction of suffix arrays. In: String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware, pp. 81\u201388. IEEE (1999)"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 549\u2013554. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"22_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/3-540-45061-0_73","volume-title":"Automata, Languages and Programming","author":"J K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 943\u2013955. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45061-0_73"},{"issue":"6","key":"22_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 (JACM) 53(6), 918\u2013936 (2006)","journal-title":"J. ACM (JACM)"},{"key":"22_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-540-24838-5_23","volume-title":"Experimental and Efficient Algorithms","author":"DK Kim","year":"2004","unstructured":"Kim, D.K., Jo, J., Park, H.: A fast algorithm for constructing suffix arrays for fixed-size alphabets. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA 2004. LNCS, vol. 3059, pp. 301\u2013314. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24838-5_23"},{"key":"22_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-44888-8_14","volume-title":"Combinatorial Pattern Matching","author":"DK Kim","year":"2003","unstructured":"Kim, D.K., Sim, J.S., Park, H., Park, K.: Linear-time construction of suffix arrays. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol. 2676, pp. 186\u2013199. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44888-8_14"},{"key":"22_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-44888-8_15","volume-title":"Combinatorial Pattern Matching","author":"P Ko","year":"2003","unstructured":"Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol. 2676, pp. 200\u2013210. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44888-8_15"},{"issue":"3","key":"22_CR23","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."},{"key":"22_CR24","unstructured":"Li, Z., Li, J., Huo, H.: Optimal in-place suffix sorting. arXiv preprint arXiv:1610.08305 (2016)"},{"key":"22_CR25","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 (SODA), pp. 319\u2013327. Society for Industrial and Applied Mathematics (1990)"},{"key":"22_CR26","unstructured":"Maniscalco, M.A., Puglisi, S.J.: Faster lightweight suffix array construction. In: Proceedings of International Workshop On Combinatorial Algorithms (IWOCA), pp. 16\u201329. Citeseer (2006)"},{"key":"22_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1227161.1278374","volume":"12","author":"MA Maniscalco","year":"2008","unstructured":"Maniscalco, M.A., Puglisi, S.J.: An efficient, versatile approach to suffix sorting. J. Exp. Algorithmics (JEA) 12, 1\u20132 (2008)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"22_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1007\/3-540-45749-6_61","volume-title":"Algorithms \u2014 ESA 2002","author":"G Manzini","year":"2002","unstructured":"Manzini, G., Ferragina, P.: Engineering a lightweight suffix array construction algorithm. In: M\u00f6hring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 698\u2013710. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45749-6_61"},{"issue":"2","key":"22_CR29","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"EM McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM (JACM) 23(2), 262\u2013272 (1976)","journal-title":"J. ACM (JACM)"},{"key":"22_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-30850-5_26","volume-title":"Experimental Algorithms","author":"G Navarro","year":"2012","unstructured":"Navarro, G., Providel, E.: Fast, small, simple rank\/select on bitmaps. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 295\u2013306. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-30850-5_26"},{"issue":"3","key":"22_CR31","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/2493175.2493180","volume":"31","author":"G Nong","year":"2013","unstructured":"Nong, G.: Practical linear-time O (1)-workspace suffix sorting for constant alphabets. ACM Trans. Inf. Syst. (TOIS) 31(3), 15 (2013)","journal-title":"ACM Trans. Inf. Syst. (TOIS)"},{"key":"22_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/978-3-540-73951-7_53","volume-title":"Algorithms and Data Structures","author":"G Nong","year":"2007","unstructured":"Nong, G., Zhang, S.: Optimal lightweight construction of suffix arrays for constant alphabets. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 613\u2013624. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73951-7_53"},{"key":"22_CR33","doi-asserted-by":"crossref","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Linear suffix array construction by almost pure induced-sorting. In: Data Compression Conference (DCC), pp. 193\u2013202. IEEE (2009)","DOI":"10.1109\/DCC.2009.42"},{"issue":"10","key":"22_CR34","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)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"22_CR35","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.H.: A taxonomy of suffix array construction algorithms. ACM Comput. Surv. (CSUR) 39(2), 4 (2007)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"22_CR36","unstructured":"Sadakane, K.: A fast algorithm for making suffix arrays and for burrows-wheeler transformation. In: Data Compression Conference (DCC), pp. 129\u2013138. IEEE (1998)"},{"issue":"4","key":"22_CR37","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/0196-6774(87)90050-2","volume":"8","author":"J Salowe","year":"1987","unstructured":"Salowe, J., Steiger, W.: Simplified stable merging tasks. J. Algorithms 8(4), 557\u2013571 (1987)","journal-title":"J. Algorithms"},{"issue":"3","key":"22_CR38","first-page":"309","volume":"37","author":"Klaus-Bernd Sch\u00fcrmann","year":"2007","unstructured":"Sch\u00fcrmann, K.B., Stoye, J.: An incomplex algorithm for fast suffix array construction. Softw.: Pract. Exp. 37(3), 309\u2013329 (2007)","journal-title":"Software: Practice and Experience"},{"issue":"5","key":"22_CR39","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory 24(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-00479-8_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,24]],"date-time":"2019-10-24T05:17:33Z","timestamp":1571894253000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-00479-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030004781","9783030004798"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-00479-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lima","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Peru","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 October 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/eventos.spc.org.pe\/spire2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"51","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"22","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"6","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"43% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"3.8","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}