{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T11:36:23Z","timestamp":1778585783279,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2016,9,15]],"date-time":"2016-09-15T00:00:00Z","timestamp":1473897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EU Project","award":["248481 (PEPPHER) ICT-2009.3.6"],"award-info":[{"award-number":["248481 (PEPPHER) ICT-2009.3.6"]}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["SPP 1307"],"award-info":[{"award-number":["SPP 1307"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2016,11,4]]},"abstract":"<jats:p>We consider full text index construction in external memory (EM). Our first contribution is an inducing algorithm for suffix arrays in external memory, which runs in sorting complexity. Practical tests show that this algorithm outperforms the previous best EM suffix sorter [Dementiev et al., JEA 2008] by a factor of about two in time and I\/O volume. Our second contribution is to augment the first algorithm to also construct the array of longest common prefixes (LCPs). This yields a new internal memory LCP array construction algorithm and the first EM construction algorithm for LCP arrays. The overhead in time and I\/O volume for this extended algorithm over plain suffix array construction is roughly two. Our algorithms scale far beyond problem sizes previously considered in the literature (text size of 80GiB using only 4GiB of RAM in our experiments).<\/jats:p>","DOI":"10.1145\/2975593","type":"journal-article","created":{"date-parts":[[2016,9,16]],"date-time":"2016-09-16T19:47:47Z","timestamp":1474055267000},"page":"1-27","source":"Crossref","is-referenced-by-count":11,"title":["Inducing Suffix and LCP Arrays in External Memory"],"prefix":"10.1145","volume":"21","author":[{"given":"Timo","family":"Bingmann","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Fischer","sequence":"additional","affiliation":[{"name":"Technical University of Dortmund, Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vitaly","family":"Osipov","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,9,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1155-5"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 15th Australasian Workshop Combinatorial Algorithms (AWOCA). 148--156","author":"Ryan P. J.","year":"2004","unstructured":"Antonitio, P. J. Ryan , William F. Smyth , Andrew Turpin , and Xiaoyang Yu . 2004 . New suffix array algorithms\u2014Linear but not fast? In Proceedings of the 15th Australasian Workshop Combinatorial Algorithms (AWOCA). 148--156 . Antonitio, P. J. Ryan, William F. Smyth, Andrew Turpin, and Xiaoyang Yu. 2004. New suffix array algorithms\u2014Linear but not fast? In Proceedings of the 15th Australasian Workshop Combinatorial Algorithms (AWOCA). 148--156."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1021-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258647"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.08.010"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1869421.1869423"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33122-0_26"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790158.2790166"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700370539"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1402296"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1361730.1361733"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-9-11"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355547"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394373.2394417"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9535-0"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12200-2_16"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033190.2033222"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2399256.2399297"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779759"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790248.2790251"},{"key":"e_1_2_1_22_1","volume-title":"Information Retrieval: Data Structures and Algorithms, William B","author":"Gonnet Gaston H.","unstructured":"Gaston H. Gonnet , Ricardo A. Baeza-Yates , and Tim Snider . 1992. New indices for text: PAT trees and PAT arrays . In Information Retrieval: Data Structures and Algorithms, William B . Frakes and Ricardo A. Baeza-Yates (Eds.). Prentice-Hall , Chapter 3, 66--82. Gaston H. Gonnet, Ricardo A. Baeza-Yates, and Tim Snider. 1992. New indices for text: PAT trees and PAT arrays. In Information Retrieval: Data Structures and Algorithms, William B. Frakes and Ricardo A. Baeza-Yates (Eds.). Prentice-Hall, Chapter 3, 66--82."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/519452.830768"},{"key":"e_1_2_1_24_1","volume-title":"Puglisi","author":"K\u00e4rkk\u00e4inen Juha","year":"2009","unstructured":"Juha K\u00e4rkk\u00e4inen , Giovanni Manzini , and Simon J . Puglisi . 2009 . Permuted longest-common-prefix array. In Proceedings of the CPM (LNCS), Vol. 5577 . Springer , 181--192. Juha K\u00e4rkk\u00e4inen, Giovanni Manzini, and Simon J. Puglisi. 2009. Permuted longest-common-prefix array. In Proceedings of the CPM (LNCS), Vol. 5577. Springer, 181--192."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89097-3_3"},{"key":"e_1_2_1_26_1","first-page":"943","article-title":"Simple linear work suffix array construction","volume":"2719","author":"K\u00e4rkk\u00e4inen Juha","year":"2003","unstructured":"Juha K\u00e4rkk\u00e4inen and Peter Sanders . 2003 . Simple linear work suffix array construction . Proceedings of the ICALP 2719 (2003), 943 -- 955 . Juha K\u00e4rkk\u00e4inen and Peter Sanders. 2003. Simple linear work suffix array construction. Proceedings of the ICALP 2719 (2003), 943--955.","journal-title":"Proceedings of the ICALP"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/647820.736222"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.002"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1278374"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_32"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1094-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2010.188"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2005.87"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242471.1242472"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384249"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1228668.1228672"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376683"},{"key":"e_1_2_1_40_1","volume-title":"Entwurf und Implementierung Eines Generischen Substring-Index. Master\u2019s thesis","author":"Weese David","unstructured":"David Weese . 2006. Entwurf und Implementierung Eines Generischen Substring-Index. Master\u2019s thesis . Humboldt University Berlin . Retrieved from http:\/\/www.seqan.de\/publications\/weese06.pdf. David Weese. 2006. Entwurf und Implementierung Eines Generischen Substring-Index. Master\u2019s thesis. Humboldt University Berlin. Retrieved from http:\/\/www.seqan.de\/publications\/weese06.pdf."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2975593","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2975593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:18Z","timestamp":1750218618000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2975593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,15]]},"references-count":39,"alternative-id":["10.1145\/2975593"],"URL":"https:\/\/doi.org\/10.1145\/2975593","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,15]]}}}