{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:41:36Z","timestamp":1725493296969},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662518"},{"type":"electronic","value":"9783540484813"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48481-7_20","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T19:49:40Z","timestamp":1193514580000},"page":"224-235","source":"Crossref","is-referenced-by-count":4,"title":["On Constructing Suffix Arrays in External Memory"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Crauser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Ferragina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,1,14]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"L. Arge, P. Ferragina, R. Grossi and J. S. Vitter. On sorting Strings in External Memory. In ACM Symp. on Theory of Computing, pp. 540\u2013548, 1997.","DOI":"10.1145\/258533.258647"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1145\/77600.77615","volume":"2","author":"R. Ahuja","year":"1990","unstructured":"R. Ahuja, K. Mehlhorn, J. B. Orlin and R. E. Tarjan. Faster Algorithms for the Shortest Path Problem. Journal of the ACM (2), pp. 213\u2013223, 1990.","journal-title":"Journal of the ACM"},{"issue":"25","key":"20_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1002\/spe.4380250203","volume":"2","author":"A. Andersson","year":"1995","unstructured":"A. Andersson and S. Nilsson. Efficient implementation of Suffix Trees. Software Practice and Experience, 2(25): 129\u2013141, 1995.","journal-title":"Software Practice and Experience"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"S. Burkhard, A. Crauser, P. Ferragina, H. Lenhof, E. Rivals and M. Vingron. q-gram based database searching using a suffix array (QUASAR). International Conference on Computational Molecular Biology, 1999.","DOI":"10.1145\/299432.299460"},{"key":"20_CR5","unstructured":"D. R. Clark and J. I. Munro. Efficient Suffix Trees on Secondary Storage. In ACM-SIAM Symp. on Discrete Algorithms, pp.383\u2013391, 1996."},{"key":"20_CR6","unstructured":"A. Crauser, P. Ferragina and U. Meyer. Practical and Efficient Priority Queues for External Memory. Technical Report MPI, see WEB pages of the authors."},{"key":"20_CR7","unstructured":"A. Crauser and K. Mehlhorn. LEDA-SM: A Library Prototype for Computing in Secondary Memory. Technical Report MPI, see WEB pages of the authors."},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/4078.4080","volume":"17","author":"C. Faloutsos","year":"1985","unstructured":"C. Faloutsos. Access Methods for text. ACM Computing Surveys, 17, pp.49\u201374, March 1985.","journal-title":"ACM Computing Surveys"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"M. Farach. Optimal suffix tree construction with large alphabets. In IEEE Foundations of Computer Science, pp. 137\u2013143, 1997.","DOI":"10.1109\/SFCS.1997.646102"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"M. Farach, P. Ferragina and S. Muthukrishnan. Overcoming the Memory Bottleneck in Suffix Tree Construction. In IEEE Foundations of Computer Science, 1998.","DOI":"10.1109\/SFCS.1998.743441"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"C. L. Feng. PAT-Tree-Based Keyword Extraction for Chinese Information Retrieval. ACM SIGIR, pp. 50\u201358, 1997.","DOI":"10.1145\/278459.258534"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"P. Ferragina and R. Grossi. A Fully-Dynamic Data Structure for External Substring Search. In ACM Symp. Theory of Computing, pp. 693\u2013702, 1995. Also Journal of the ACM (to appear).","DOI":"10.1145\/225058.225287"},{"key":"20_CR13","unstructured":"G. H. Gonnet, R. A. Baeza-Yates and T. Snider. Newindices for text:PAT trees and PAT arrays. In Information Retrieval-Data Structures and Algorithms,W. B. Frakes and R. BaezaYates Editors, pp. 66\u201382, Prentice-Hall, 1992."},{"key":"20_CR14","unstructured":"D. E. Knuth. The Art of Computer Programming: Sorting and Searching. Vol. 3, Addison-Wesley Publishing Co. 1973."},{"key":"20_CR15","unstructured":"S. Kurtz. Reducing the Space Requirement of SuffixTrees. Technical Report 98-03, University of Bielefeld, 1998."},{"issue":"5","key":"20_CR16","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"U. Manber and G. Myers. Suffix arrays: a new method for on-line string searches. SIAM Journal of Computing 22, 5,pp. 935\u2013948, 1993.","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"20_CR17","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E. M. McCreight","year":"1976","unstructured":"E. M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM 23, 2,pp. 262\u2013272, 1976.","journal-title":"Journal of the ACM"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"G. Navarro, J. P. Kitajima, B. A. Ribeiro-Neto and N. Ziviani. Distributed Generation of Suffix Arrays. In Combinatorial Pattern Matching Conference, pp. 103\u2013115, 1997.","DOI":"10.1007\/3-540-63220-4_54"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"S. N\u00e4her and K. Mehlhorn. LEDA:A Platform for Combinatorial and Geometric Computing. Communications of the ACM (38), 1995.","DOI":"10.1145\/204865.204889"},{"issue":"3","key":"20_CR20","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/2.268881","volume":"27","author":"C. Ruemmler","year":"1994","unstructured":"C. Ruemmler and J. Wilkes. An introduction to disk drive modeling. IEEE Computer, 27(3):17\u201329, 1994.","journal-title":"IEEE Computer"},{"issue":"2-3","key":"20_CR21","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/BF01185207","volume":"12","author":"E. A. Shriver","year":"1994","unstructured":"E. A. Shriver and J. S. Vitter. Algorithms for parallel memory I: two-level memories. Algorithmica, 12(2-3), pp. 110\u2013147, 1994.","journal-title":"Algorithmica"},{"key":"20_CR22","unstructured":"D. E. Vengroff and J. S. Vitter. I\/O-efficient scientific computing using TPIE. In IEEE Symposium on Parallel and Distributed Computing, 1995."},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"J. Vitter. External memory algorithms. Invited Tutorial in 17th Ann. ACMSymp. on Principles of Database Systems (PODS\u2019 98), 1998. Also Invited Paper in European Symposium on Algorithms (ESA\u2019 98), 1998.","DOI":"10.1145\/275487.275501"},{"issue":"3","key":"20_CR24","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/234889.234891","volume":"25","author":"J. Zobel","year":"1996","unstructured":"J. Zobel, A. Moffat and K. Ramamohanarao. Guidelines for presentation and comparison of indexing techniques. SIGMAD Record 25, 3:10\u201315, 1996.","journal-title":"SIGMAD Record"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA\u2019 99"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48481-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T22:20:52Z","timestamp":1556922052000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48481-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662518","9783540484813"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-48481-7_20","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}