{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:22Z","timestamp":1759637722127},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642389047"},{"type":"electronic","value":"9783642389054"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38905-4_12","type":"book-chapter","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T23:28:54Z","timestamp":1368660534000},"page":"107-119","source":"Crossref","is-referenced-by-count":11,"title":["Document Listing on Repetitive Collections"],"prefix":"10.1007","author":[{"given":"Travis","family":"Gagie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kalle","family":"Karhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jouni","family":"Sir\u00e9n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1007\/978-3-642-23719-5_63","volume-title":"Algorithms \u2013 ESA 2011","author":"D. Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 748\u2013759. Springer, Heidelberg (2011)"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-34109-0_19","volume-title":"String Processing and Information Retrieval","author":"F. Claude","year":"2012","unstructured":"Claude, F., Navarro, G.: Improved grammar-based compressed indexes. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.\u00a07608, pp. 180\u2013192. Springer, Heidelberg (2012)"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-12200-2_16","volume-title":"LATIN 2010: Theoretical Informatics","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 158\u2013169. Springer, Heidelberg (2010)"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-28332-1_21","volume-title":"Language and Automata Theory and Applications","author":"T. Gagie","year":"2012","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A faster grammar-based self-index. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol.\u00a07183, pp. 240\u2013251. Springer, Heidelberg (2012)"},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-642-16321-0_7","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2010","unstructured":"Gagie, T., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 67\u201381. Springer, Heidelberg (2010)"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2011.12.002","volume":"426-","author":"T. Gagie","year":"2012","unstructured":"Gagie, T., Navarro, G., Puglisi, S.J.: New algorithms on wavelet trees and applications to information retrieval. Theor. Comp. Sci.\u00a0426-427, 25\u201341 (2012)","journal-title":"Theor. Comp. Sci."},{"key":"12_CR7","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. SODA, pp. 636\u2013645 (2003)"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Vitter, J.: Space-efficient framework for top-k string retrieval problems. In: Proc. FOCS, pp. 713\u2013722 (2009)","DOI":"10.1109\/FOCS.2009.19"},{"issue":"3","key":"12_CR9","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V. M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., Navarro, G., Sir\u00e9n, J., Valim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. J. Computational Biology\u00a017(3), 281\u2013308 (2010)","journal-title":"J. Computational Biology"},{"issue":"5","key":"12_CR10","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 J. Comput.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"12_CR11","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proc. SODA, pp. 657\u2013666 (2002)"},{"key":"12_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-642-20662-7_17","volume-title":"Experimental Algorithms","author":"G. Navarro","year":"2011","unstructured":"Navarro, G., Puglisi, S.J., Valenzuela, D.: Practical compressed document retrieval. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol.\u00a06630, pp. 193\u2013205. Springer, Heidelberg (2011)"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: Proc. ALENEX (2007)","DOI":"10.1137\/1.9781611972870.6"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M.: Succincter. In: Proc. FOCS, pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"issue":"1","key":"12_CR15","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. J. Disc. Alg.\u00a05(1), 12\u201322 (2007)","journal-title":"J. Disc. Alg."},{"issue":"6","key":"12_CR16","doi-asserted-by":"publisher","first-page":"1176","DOI":"10.1137\/0222070","volume":"22","author":"W. Szpankowski","year":"1993","unstructured":"Szpankowski, W.: A generalized suffix tree and its (un)expected asymptotic behaviors. SIAM J. Comput.\u00a022(6), 1176\u20131198 (1993)","journal-title":"SIAM J. Comput."},{"key":"12_CR17","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":"12_CR18","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. SAT, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"2","key":"12_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D. Willard","year":"1983","unstructured":"Willard, D.: Log-logarithmic worst-case range queries are possible in space \u03b8(n). Inf. Pr. Lett.\u00a017(2), 81\u201384 (1983)","journal-title":"Inf. Pr. Lett."}],"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-38905-4_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T21:59:25Z","timestamp":1557698365000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38905-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642389047","9783642389054"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38905-4_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}