{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:09:43Z","timestamp":1764936583817},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T00:00:00Z","timestamp":1308355200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,7]]},"DOI":"10.1007\/s00453-011-9535-0","type":"journal-article","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T02:52:59Z","timestamp":1308365579000},"page":"707-730","source":"Crossref","is-referenced-by-count":71,"title":["Lightweight Data Indexing and Compression in External Memory"],"prefix":"10.1007","volume":"63","author":[{"given":"Paolo","family":"Ferragina","sequence":"first","affiliation":[]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[]},{"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,6,18]]},"reference":[{"key":"9535_CR1","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/978-3-540-68552-4_16","volume-title":"Proc. 7th International Workshop on Experimental Algorithms","author":"D. Ajwani","year":"2008","unstructured":"Ajwani, D., Malinger, I., Meyer, U., Toledo, S.: Characterizing the performance of flash memory storage devices and its impact on algorithm design. In: Proc. 7th International Workshop on Experimental Algorithms. LNCS, 5038, pp. 208\u2013219. Springer, Berlin (2008)"},{"key":"9535_CR2","first-page":"39","volume-title":"Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science","author":"P. Albert","year":"2008","unstructured":"Albert, P., Mayordomo, E., Moser, P., Perifel, S.: Pushdown compression. In: Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science, vol. 1, pp. 39\u201348. Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, Germany (2008)"},{"issue":"8","key":"9535_CR3","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1002\/spe.587","volume":"34","author":"P. Boldi","year":"2004","unstructured":"Boldi, P., Codenotti, B., Santini, M., Vigna, S.: Ubicrawler: A scalable fully distributed web crawler. Softw. Pract. Exp. 34(8), 711\u2013726 (2004)","journal-title":"Softw. Pract. Exp."},{"key":"9535_CR4","unstructured":"Burrows, M., Wheeler, D.: A block-sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, (1994)"},{"key":"9535_CR5","first-page":"139","volume-title":"Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Y.-J. Chiang","year":"1995","unstructured":"Chiang, Y.-J., Goodrich, M., Grove, E., Tamassia, R., Vengroff, D., Vitter, J.: External-memory graph algorithms. In: Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 139\u2013149 (1995)"},{"issue":"1","key":"9535_CR6","doi-asserted-by":"crossref","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"},{"key":"9535_CR7","doi-asserted-by":"crossref","unstructured":"Dementiev, R., K\u00e4rkk\u00e4inen, J., Mehnert, J., Sanders, P.: Better external memory suffix array construction. ACM J. Exp. Algorithmics 12 (2008)","DOI":"10.1145\/1227161.1402296"},{"issue":"6","key":"9535_CR8","doi-asserted-by":"crossref","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"},{"key":"9535_CR9","doi-asserted-by":"crossref","DOI":"10.1201\/9781420036275.pt8","volume-title":"String Search in External Memory: Data Structures and Algorithms","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P.: String Search in External Memory: Data Structures and Algorithms. Chapman and Hall, London (2005). Chap. 35"},{"key":"9535_CR10","unstructured":"Ferragina, P., Navarro, G.: (2007). The Pizza&Chili Corpus Home Page. http:\/\/pizzachili.dcc.uchile.cl\/ or http:\/\/pizzachili.di.unipi.it\/"},{"key":"9535_CR11","series-title":"LNCS","first-page":"756","volume-title":"Proc. 14th European Symposium on Algorithms (ESA)","author":"P. Ferragina","year":"2006","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G.: The engineering of a compression boosting library: theory vs practice in BWT compression. In: Proc. 14th European Symposium on Algorithms (ESA), LNCS, vol.\u00a04168, pp. 756\u2013767. Springer, Berlin (2006)"},{"key":"9535_CR12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/978-3-540-73420-8_47","volume-title":"Proc. of International Colloquium on Automata and Languages (ICALP)","author":"G. Franceschini","year":"2007","unstructured":"Franceschini, G., Muthukrishnan, S.: In-place suffix sorting. In: Proc. of International Colloquium on Automata and Languages (ICALP), LNCS,\u00a0vol.\u00a04596, pp. 533\u2013545. Springer, Berlin (2007)"},{"key":"9535_CR13","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/978-3-642-02441-2_7","volume-title":"Proceedings of the 20th Symposium on Combinatorial Pattern Matching","author":"T. Gagie","year":"2009","unstructured":"Gagie, T.: On the value of multiple read\/write streams for data compression. In: Proceedings of the 20th Symposium on Combinatorial Pattern Matching, LNCS,\u00a0vol.\u00a05577, pp. 68\u201377. Springer, Berlin (2009)"},{"key":"9535_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/978-3-540-74456-6_20","volume-title":"Proc. 32nd Symp. on Mathematical Foundations of Computer Science (MFCS \u201907)","author":"T. Gagie","year":"2007","unstructured":"Gagie, T., Manzini, G.: Space-conscious compression. In: Proc. 32nd Symp. on Mathematical Foundations of Computer Science (MFCS \u201907), LNCS,\u00a0vol.\u00a04708, pp. 206\u2013217. Springer, Berlin (2007)"},{"key":"9535_CR15","first-page":"66","volume-title":"Information Retrieval: Data Structures and Algorithms","author":"G.H. Gonnet","year":"1992","unstructured":"Gonnet, G.H., Baeza-Yates, R.A., Snider, T.: New indices for text: PAT trees and PAT arrays. In: Frakes, B., Baeza-Yates, R.A. (eds.) Information Retrieval: Data Structures and Algorithms, pp. 66\u201382. Prentice-Hall, New York (1992). Chap.\u00a05"},{"key":"9535_CR16","doi-asserted-by":"crossref","first-page":"2162","DOI":"10.1137\/070685373","volume":"38","author":"W.-K. Hon","year":"2009","unstructured":"Hon, W.-K., Sadakane, K., Sung, W.-K.: Breaking a time-and-space barrier in constructing full-text indices. SIAM J. Comput. 38, 2162\u20132178 (2009)","journal-title":"SIAM J. Comput."},{"key":"9535_CR17","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/978-3-642-13509-5_24","volume-title":"Proc. of the 21st Symposium on Combinatorial Pattern Matching (CPM \u201910)","author":"W.-K. Hon","year":"2010","unstructured":"Hon, W.-K., Shah, R., Vitter, J.: Compression, indexing, and retrieval for massive string data. In: Proc. of the 21st Symposium on Combinatorial Pattern Matching (CPM \u201910), LNCS,\u00a0vol.\u00a06129, pp. 260\u2013274. Springer, Berlin (2010)"},{"issue":"1","key":"9535_CR18","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s00453-006-1228-8","volume":"48","author":"W.-K. Hon","year":"2007","unstructured":"Hon, W.-K., Lam, T.W., Sadakane, K., Sung, W.-K., Yiu, S.-M.: A space and time efficient algorithm for constructing compressed suffix arrays. Algorithmica 48(1), 23\u201336 (2007)","journal-title":"Algorithmica"},{"key":"9535_CR19","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/j.tcs.2007.07.018","volume":"387","author":"J. K\u00e4rkk\u00e4inen","year":"2007","unstructured":"K\u00e4rkk\u00e4inen, J.: Fast BWT in small space by blockwise suffix sorting. Theor. Comput. Sci. 387, 249\u2013257 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"9535_CR20","doi-asserted-by":"crossref","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"},{"key":"9535_CR21","series-title":"The Art of Computer Programming","first-page":"780","volume-title":"Sorting and Searching","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: Sorting and Searching, 2nd edn. The Art of Computer Programming, vol. 3, p. 780. Addison-Wesley, Reading (1998)","edition":"2"},{"key":"9535_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-49820-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"2008","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"issue":"5","key":"9535_CR23","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0020-0190(02)00512-4","volume":"86","author":"S. Mantaci","year":"2003","unstructured":"Mantaci, S., Restivo, A., Sciortino, M.: Burrows-Wheeler transform and Sturmian words. Inf. Process. Lett. 86(5), 241\u2013246 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9535_CR24","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1007\/s00224-010-9267-6","volume":"48","author":"E. Mayordomo","year":"2011","unstructured":"Mayordomo, E., Moser, P., Perifel, S.: Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable. Theory Comput. Syst. 48(4), 731\u2013766 (2011)","journal-title":"Theory Comput. Syst."},{"key":"9535_CR25","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"J.I. Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.: Selection and sorting with limited storage. Theor. Comput. Sci. 12, 315\u2013323 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"9535_CR26","series-title":"Foundations and Trends in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1561\/9781933019604","volume-title":"Data Streams: Algorithms and Applications","author":"S. Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science, vol. 1:2. Now Publishers, Hanover (2005)"},{"key":"9535_CR27","first-page":"127","volume":"386","author":"J.C. Na","year":"2007","unstructured":"Na, J.C., Park, K.: Alphabet-independent linear-time construction of compressed suffix arrays using o(nlog\u2009n)-bit working space. Theor. Comput. Sci. 386, 127\u2013136 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9535_CR28","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys 39(1) (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"9535_CR29","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/978-3-642-03784-9_9","volume-title":"Proc. 16th Int. Symp. on String Processing and Information Retrieval (SPIRE \u201909)","author":"D. Okanohara","year":"2009","unstructured":"Okanohara, D., Sadakane, K.: A linear-time Burrows-Wheeler transform using induced sorting. In: Proc. 16th Int. Symp. on String Processing and Information Retrieval (SPIRE \u201909), LNCS, vol.\u00a05721, pp. 90\u2013101. Springer, Berlin (2009)"},{"key":"9535_CR30","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-642-03784-9_7","volume-title":"Proc. 16th Int. Symp. on String Processing and Information Retrieval (SPIRE \u201909)","author":"J. Sir\u00e9n","year":"2009","unstructured":"Sir\u00e9n, J.: Compressed suffix arrays for massive data. In: Proc. 16th Int. Symp. on String Processing and Information Retrieval (SPIRE \u201909), LNCS, vol.\u00a05721, pp. 63\u201374. Springer, Berlin (2009)"},{"key":"9535_CR31","series-title":"Foundations and Trends in Theoretical Computer Science","volume-title":"Algorithms and Data Structures for External Memory","author":"J. Vitter","year":"2008","unstructured":"Vitter, J.: Algorithms and Data Structures for External Memory. Foundations and Trends in Theoretical Computer Science, vol. 2:4. Now Publishers, Hanover (2008)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9535-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9535-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9535-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T09:49:44Z","timestamp":1592646584000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9535-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,18]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["9535"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9535-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,18]]}}}