{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T17:06:21Z","timestamp":1761843981432},"publisher-location":"Berlin, Heidelberg","reference-count":75,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135088"},{"type":"electronic","value":"9783642135095"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13509-5_24","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T09:19:57Z","timestamp":1277198397000},"page":"260-274","source":"Crossref","is-referenced-by-count":19,"title":["Compression, Indexing, and Retrieval for Massive String Data"],"prefix":"10.1007","author":[{"given":"Wing-Kai","family":"Hon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"24_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The Input\/Output complexity of sorting and related problems. Communications of the ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Communications of the ACM"},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-540-73437-6_11","volume-title":"Combinatorial Pattern Matching","author":"D. Arroyuelo","year":"2007","unstructured":"Arroyuelo, D., Navarro, G.: A Lempel-Ziv text index on secondary storage. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 83\u201394. Springer, Heidelberg (2007)"},{"key":"24_CR3","unstructured":"Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: Proc. ACM-SIAM Symp. on Discrete Algorithms, pp. 680\u2013689 (2007)"},{"issue":"1","key":"24_CR4","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/320521.320530","volume":"2","author":"R. Bayer","year":"1977","unstructured":"Bayer, R., Unterauer, K.: Prefix B-trees. ACM Transactions on Database Systems\u00a02(1), 11\u201326 (1977)","journal-title":"ACM Transactions on Database Systems"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Belazzougui, D.: Succinct dictionary matching with no slowdown. In: Proc. Symp. on Combinatorial Pattern Matching (June 2010)","DOI":"10.1007\/978-3-642-13509-5_9"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/11575832_10","volume-title":"String Processing and Information Retrieval","author":"I. Bialynicka-Birula","year":"2005","unstructured":"Bialynicka-Birula, I., Grossi, R.: Rank-sensitive data structures. In: Consens, M.P., Navarro, G. (eds.) SPIRE 2005. LNCS, vol.\u00a03772, pp. 79\u201390. Springer, Heidelberg (2005)"},{"key":"24_CR7","unstructured":"Burrows, M., Wheeler, D.: A block sorting data compression algorithm. Technical report, Digital Systems Research Center (1994)"},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Chan, H.L., Hon, W.K., Lam, T.W., Sadakane, K.: Compressed indexes for dynamic text collections. ACM Transactions on Algorithms\u00a03(2) (2007)","DOI":"10.1145\/1240233.1240244"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Chien, Y.-F., Hon, W.-K., Shah, R., Vitter, J.S.: Geometric Burrows-Wheeler transform: Linking range searching and text indexing. In: Proc. IEEE Data Compression Conf., pp. 252\u2013261 (2008)","DOI":"10.1109\/DCC.2008.67"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Chiu, S.-Y., Hon, W.-K., Shah, R., Vitter, J.S.: I\/O-efficient compressed text indexes: From theory to practice. In: Proc. IEEE Data Compression Conf., pp. 426\u2013434 (2010)","DOI":"10.1109\/DCC.2010.45"},{"key":"24_CR11","unstructured":"Dean, J., Ghemawat, S.: MapReduce: Simplified data processing on large clusters. In: Proc. Symp. on Operating Systems Design and Implementation. December 2004, pp. 137\u2013150, USENIX (2004)"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P. Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory\u00a0IT-21, 194\u2013203 (1975)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"8","key":"24_CR13","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1016\/j.ic.2008.12.010","volume":"207","author":"P. Ferragina","year":"2009","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G.: The myriad virtues of wavelet trees. Information and Computation\u00a0207(8), 849\u2013866 (2009)","journal-title":"Information and Computation"},{"issue":"4","key":"24_CR14","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1145\/1082036.1082043","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression in optimal linear time. Journal of the ACM\u00a052(4), 688\u2013713 (2005)","journal-title":"Journal of the ACM"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Gonz\u00e1lez, R., Navarro, G., Venturini, R.: Compressed text indexes: From theory to practice. ACM Journal of Experimental Algorithmics\u00a012, article\u00a01.12 (2008)","DOI":"10.1145\/1412228.1455268"},{"issue":"2","key":"24_CR16","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The String B-tree: A new data structure for string search in external memory and its applications. Journal of the ACM\u00a046(2), 236\u2013280 (1999)","journal-title":"Journal of the ACM"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Grossi, R., Gupta, A., Shah, R., Vitter, J.S.: On searching compressed string collections cache-obliviously. In: Proc. ACM Conf. on Principles of Database Systems, Vancouver, June 2008, pp. 181\u2013190 (2008)","DOI":"10.1145\/1376916.1376943"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: Proc. IEEE Symp. on Foundations of Computer Science, pp. 184\u2013196 (2005)","DOI":"10.1109\/SFCS.2005.69"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proc. IEEE Symp. on Foundations of Computer Science, November 2000, vol.\u00a041, pp. 390\u2013398 (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"issue":"4","key":"24_CR20","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed texts. Journal of the ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"Journal of the ACM"},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms\u00a03(2) (May 2007) Conference version in SPIRE 2004","DOI":"10.1145\/1240233.1240243"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Venturini, R.: Compressed permuterm index. In: Proc. ACM SIGIR Conf. on Res. and Dev. in Information Retrieval, pp. 535\u2013542 (2007)","DOI":"10.1145\/1277741.1277833"},{"issue":"51","key":"24_CR23","doi-asserted-by":"publisher","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","volume":"410","author":"J. Fischer","year":"2009","unstructured":"Fischer, J., M\u00e4kinen, V., Navarro, G.: Faster entropy-bounded compressed suffix trees. Theoretical Computer Science\u00a0410(51), 5354\u20135364 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"24_CR24","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1145\/1198513.1198521","volume":"2","author":"L. Foschini","year":"2004","unstructured":"Foschini, L., Grossi, R., Gupta, A., Vitter, J.S.: When indexing equals compression: Experiments on suffix arrays and trees. ACM Transactions on Algorithms\u00a02(4), 611\u2013639 (2004); Conference versions in SODA 2004 and DCC 2004","journal-title":"ACM Transactions on Algorithms"},{"key":"24_CR25","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. IEEE Symp. on Foundations of Computer Science, vol.\u00a040, pp. 285\u2013298 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"24_CR26","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: Information Retrieval: Data Structures And Algorithms, ch.\u00a05, pp. 66\u201382. Prentice-Hall, Englewood Cliffs (1992)"},{"key":"24_CR27","unstructured":"Gonz\u00e1lez, R., Navarro, G.: A compressed text index on secondary memory. In: Proc. Intl. Work. Combinatorial Algorithms, Newcastle, Australia, pp. 80\u201391. College Publications (2007)"},{"key":"24_CR28","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. ACM-SIAM Symp. on Discrete Algorithms (January 2003)"},{"key":"24_CR29","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: Nearly tight bounds on the encoding length of the Burrows-Wheeler transform. In: Proc. Work. on Analytical Algorithmics and Combinatorics (January 2008)"},{"key":"24_CR30","doi-asserted-by":"crossref","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In: Proc. ACM Symp. on Theory of Computing, May 2000, vol.\u00a032, pp. 397\u2013406 (2000)","DOI":"10.1145\/335305.335351"},{"issue":"32","key":"24_CR31","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 Journal on Computing\u00a035(32), 378\u2013407 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR32","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Lam, T.-W., Shah, R., Tam, S.-L., Vitter, J.S.: Compressed index for dictionary matching. In: Proc. IEEE Data Compression Conf., pp. 23\u201332 (2008)","DOI":"10.1109\/DCC.2008.62"},{"key":"24_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_104","volume-title":"Algorithms and Computation","author":"W.-K. Hon","year":"2009","unstructured":"Hon, W.-K., Lam, T.-W., Shah, R., Tam, S.-L., Vitter, J.S.: Succinct index for dynamic dictionary matching. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878. Springer, Heidelberg (2009)"},{"key":"24_CR34","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: On entropy-compressed text indexing in external memory. In: Hyyro, H. (ed.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 75\u201389. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03784-9_8"},{"key":"24_CR35","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Ordered pattern matching: Towards full-text retrieval. In: Purdue University Tech. Rept. (2006)"},{"key":"24_CR36","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Space-efficient framework for top-k string retrieval problems. In: Proc. IEEE Symp. on Foundations of Computer Science, Atlanta (October 2009)","DOI":"10.1109\/FOCS.2009.19"},{"key":"24_CR37","unstructured":"K\u00e4rkk\u00e4inen, J.: Repetition-Based Text Indexes. Ph.d., University of Helsinki (1999)"},{"key":"24_CR38","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-36574-5_7","volume-title":"Algorithms for Memory Hierarchies","author":"J. K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Rao, S.S.: Full-text indexes in external memory. In: Meyer, U., Sanders, P., Sibeyn, J. (eds.) Algorithms for Memory Hierarchies, ch.\u00a07, pp. 149\u2013170. Springer, Berlin (2003)"},{"key":"24_CR39","doi-asserted-by":"crossref","unstructured":"K\u00fclekci, M.O., Hon, W.-K., Shah, R., Vitter, J.S., Xu, B.: A parallel sparse index for read alignment on genomes (2010)","DOI":"10.1109\/BIBM.2010.5706648"},{"issue":"3","key":"24_CR40","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/s00453-007-9104-8","volume":"51","author":"T.-W. Lam","year":"2008","unstructured":"Lam, T.-W., Sung, W.-K., Wong, S.-S.: Improved approximate string matching using compressed suffix data structures. Algorithmica\u00a051(3), 298\u2013314 (2008)","journal-title":"Algorithmica"},{"key":"24_CR41","doi-asserted-by":"crossref","unstructured":"Langmead, B., Trapnell, C., Pop, M., Salzberg, S.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biology\u00a010(3), article\u00a0R25 (2009)","DOI":"10.1186\/gb-2009-10-3-r25"},{"issue":"15","key":"24_CR42","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","volume":"25","author":"R. Li","year":"2009","unstructured":"Li, R., Yu, C., Li, Y., Lam, T.-W., Yiu, S.-M., Kristiansen, K., Wang, J.: SOAP2: An improved ultrafast tool for short read alignment. Bioinformatics\u00a025(15), 1966\u20131967 (2009)","journal-title":"Bioinformatics"},{"issue":"21","key":"24_CR43","doi-asserted-by":"publisher","first-page":"2431","DOI":"10.1093\/bioinformatics\/btn416","volume":"24","author":"H. Lin","year":"2008","unstructured":"Lin, H., Zhang, Z., Zhang, M.Q., Ma, B., Li, M.: ZOOM: Zillions of oligos mapped. Bioinformatics\u00a024(21), 2431\u20132437 (2008)","journal-title":"Bioinformatics"},{"issue":"1","key":"24_CR44","first-page":"40","volume":"12","author":"V. M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nordic Journal of Computing\u00a012(1), 40\u201366 (2005)","journal-title":"Nordic Journal of Computing"},{"key":"24_CR45","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Navarro, G.: Position-restricted substring searching. In: Proc. Latin American Theoretical Informatics Symp., pp. 703\u2013714 (2006)","DOI":"10.1007\/11682462_64"},{"key":"24_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-540-75530-2_21","volume-title":"String Processing and Information Retrieval","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Implicit compression boosting with applications to self-indexing. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol.\u00a04726, pp. 229\u2013241. Springer, Heidelberg (2007)"},{"key":"24_CR47","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Navarro, G.: Dynamic entropy-compressed sequences and full-text indexes. ACM Transactions on Algorithms\u00a04(3), article\u00a012 (June 2008)","DOI":"10.1145\/1367064.1367072"},{"key":"24_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1007\/978-3-540-30551-4_59","volume-title":"Algorithms and Computation","author":"V. M\u00e4kinen","year":"2004","unstructured":"M\u00e4kinen, V., Navarro, G., Sadakane, K.: Advantages of backward searching\u2014efficient secondary memory and distributed implementation of compressed suffix arrays. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 681\u2013692. Springer, Heidelberg (2004)"},{"issue":"5","key":"24_CR49","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"#cr-split#-24_CR50.1","doi-asserted-by":"crossref","unstructured":"Manzini, G.: An analysis of the Burrows-Wheeler transform. Journal of the ACM??48(3) (2001);","DOI":"10.1145\/382780.382782"},{"key":"#cr-split#-24_CR50.2","unstructured":"Conference version in SODA 1999"},{"issue":"2","key":"24_CR51","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. Journal of the ACM\u00a023(2), 262\u2013272 (1976)","journal-title":"Journal of the ACM"},{"issue":"4","key":"24_CR52","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1145\/237496.237497","volume":"14","author":"A. Moffat","year":"1996","unstructured":"Moffat, A., Zobel, J.: Self-indexing inverted files for fast text retrieval. ACM Transactions on Information Systems\u00a014(4), 349\u2013379 (1996)","journal-title":"ACM Transactions on Information Systems"},{"key":"24_CR53","unstructured":"Muthukrishnan, S.: Efficient Algorithms for Document Retrieval Problems. In: Proc. ACM-SIAM Symp. on Discrete Algorithms, pp. 657\u2013666 (2002)"},{"key":"24_CR54","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science. now Publishers, Hanover (2005)","DOI":"10.1561\/0400000002"},{"key":"24_CR55","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys\u00a039(1), article\u00a02 (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"24_CR56","unstructured":"NCBI short read archive SRR001115, http:\/\/www.ncbi.nlm.nih.gov\/"},{"key":"24_CR57","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Succincter. In: Proc. IEEE Symp. on Foundations of Computer Science, pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"24_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/11880561_11","volume-title":"String Processing and Information Retrieval","author":"S.J. Puglisi","year":"2006","unstructured":"Puglisi, S.J., Smyth, W.F., Turpin, A.: Inverted files versus suffix arrays for locating patterns in primary memory. In: Crestani, F., Ferragina, P., Sanderson, M. (eds.) SPIRE 2006. LNCS, vol.\u00a04209, pp. 122\u2013133. Springer, Heidelberg (2006)"},{"issue":"4","key":"24_CR59","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R. Raman","year":"2007","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms\u00a03(4), article\u00a043 (2007)","journal-title":"ACM Transactions on Algorithms"},{"key":"24_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/978-3-540-78773-0_32","volume-title":"LATIN 2008: Theoretical Informatics","author":"L. Russo","year":"2008","unstructured":"Russo, L., Navarro, G., Oliveira, A.: Fully-compressed suffix trees. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 362\u2013373. Springer, Heidelberg (2008)"},{"key":"24_CR61","doi-asserted-by":"crossref","unstructured":"Sadakane, K.: Compressed text databases with efficient query algorithms based on the compressed suffix array. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol.\u00a01969, pp. 410\u2013421. Springer, Heidelberg (December 2000)","DOI":"10.1007\/3-540-40996-3_35"},{"issue":"2","key":"24_CR62","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K. Sadakane","year":"2003","unstructured":"Sadakane, K.: New text indexing functiionalities of the compressed suffix arrays. Journal of Algorithms\u00a048(2), 294\u2013313 (2003)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"24_CR63","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory of Computing Systems\u00a041(4), 589\u2013607 (2007)","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"24_CR64","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct Data Structures for Flexible Text Retrieval Systems. Journal of Discrete Algorithms\u00a05(1), 12\u201322 (2007)","journal-title":"Journal of Discrete Algorithms"},{"issue":"3","key":"24_CR65","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/MC.2010.75","volume":"43","author":"A.C. Sodan","year":"2010","unstructured":"Sodan, A.C., Machina, J., Deshmeh, A., Macnaughton, K., Esbaugh, B.: Parallelism via multithreaded and multicore CPUs. IEEE Computer\u00a043(3), 24\u201332 (2010)","journal-title":"IEEE Computer"},{"key":"24_CR66","doi-asserted-by":"crossref","unstructured":"Tam, A., Wu, E., Lam, T.W., Yiu, S.-M.: Succinct text indexing with wildcards. In: Proc. Intl. Symp. on String Processing Information Retrieval, August 2009, pp. 39\u201350 (2009)","DOI":"10.1007\/978-3-642-03784-9_5"},{"key":"24_CR67","unstructured":"Thankachan, S.V., Hon, W.-K., Shah, R., Vitter, J.S.: String retrieval for multi-pattern queries (2010)"},{"issue":"3","key":"24_CR68","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica\u00a014(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"24_CR69","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-73437-6_22","volume-title":"Combinatorial Pattern Matching","author":"N. V\u00e4lim\u00e4ki","year":"2007","unstructured":"V\u00e4lim\u00e4ki, N., M\u00e4kinen, V.: Space-Efficient Algorithms for Document Retrieval. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 205\u2013215. Springer, Heidelberg (2007)"},{"key":"24_CR70","unstructured":"Vitter, J.S.: Algorithms and Data Structures for External Memory. Foundations and Trends in Theoretical Computer Science. now Publishers, Hanover (2008)"},{"issue":"2\u20133","key":"24_CR71","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/BF01185207","volume":"12","author":"J.S. Vitter","year":"1994","unstructured":"Vitter, J.S., Shriver, E.A.M.: Algorithms for parallel memory I: Two-level memories. Algorithmica\u00a012(2\u20133), 110\u2013147 (1994)","journal-title":"Algorithmica"},{"key":"24_CR72","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. IEEE Symp. on Switching and Automata Theory, Washington, DC, vol.\u00a014, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"key":"24_CR73","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"I.H. Witten","year":"1999","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann, Los Altos (1999)","edition":"2"},{"key":"24_CR74","doi-asserted-by":"crossref","unstructured":"Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Computing Surveys\u00a038(2) (2006)","DOI":"10.1145\/1132956.1132959"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13509-5_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:39:10Z","timestamp":1606185550000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13509-5_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135088","9783642135095"],"references-count":75,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13509-5_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}