{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:45Z","timestamp":1760202645858},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642359255"},{"type":"electronic","value":"9783642359262"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-35926-2_29","type":"book-chapter","created":{"date-parts":[[2012,12,21]],"date-time":"2012-12-21T04:32:11Z","timestamp":1356064331000},"page":"274-279","source":"Crossref","is-referenced-by-count":22,"title":["Indexing Highly Repetitive Collections"],"prefix":"10.1007","author":[{"given":"Gonzalo","family":"Navarro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-3-642-34109-0_5","volume-title":"String Processing and Information Retrieval","author":"A. Abeliuk","year":"2012","unstructured":"Abeliuk, A., Navarro, G.: Compressed Suffix Trees for Repetitive Texts. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.\u00a07608, pp. 30\u201341. Springer, Heidelberg (2012)"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Bille, P., Landau, G., Raman, R., Sadakane, K., Rao Satti, S., Weimann, O.: Random access to grammar-compressed strings. In: Proc. 22nd SODA, pp. 373\u2013389 (2011)","DOI":"10.1137\/1.9781611973082.30"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Chan, T., Larsen, K., Patrascu, M.: Orthogonal range searching on the RAM, revisited. In: Proc. 27th SoCG, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Rasala, A., Sahai, A., Shelat, A.: Approximating the smallest grammar: Kolmogorov complexity in natural models. In: Proc. 34th STOC, pp. 792\u2013801 (2002)","DOI":"10.1145\/510019.510021"},{"issue":"7","key":"29_CR5","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theo.\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theo."},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Claude, F., Fari\u00f1a, A., Mart\u00ednez-Prieto, M., Navarro, G.: Compressed q-gram indexing for highly repetitive biological sequences. In: Proc. 10th BIBE, pp. 86\u201391 (2010)","DOI":"10.1109\/BIBE.2010.22"},{"key":"29_CR7","doi-asserted-by":"crossref","unstructured":"Claude, F., Fari\u00f1a, A., Mart\u00ednez-Prieto, M., Navarro, G.: Indexes for highly repetitive document collections. In: Proc. 20th CIKM, pp. 463\u2013468 (2011)","DOI":"10.1145\/2063576.2063646"},{"key":"29_CR8","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":"29_CR9","doi-asserted-by":"crossref","unstructured":"Do, H.-H., Jansson, J., Sadakane, K., Sung, W.-K.: Fast relative Lempel-Ziv self-index for similar sequences. In: Proc. FAW-AAIM, pp. 291\u2013302 (2012)","DOI":"10.1007\/978-3-642-29700-7_27"},{"issue":"51","key":"29_CR10","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. Theor. Comp. Sci.\u00a0410(51), 5354\u20135364 (2009)","journal-title":"Theor. Comp. Sci."},{"key":"29_CR11","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":"29_CR12","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th SODA, pp. 841\u2013850 (2003)"},{"issue":"2","key":"29_CR13","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R. Grossi","year":"2006","unstructured":"Grossi, R., Vitter, J.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comp.\u00a035(2), 378\u2013407 (2006)","journal-title":"SIAM J. Comp."},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-14355-7_19","volume-title":"Algorithmic Aspects in Information and Management","author":"S. Huang","year":"2010","unstructured":"Huang, S., Lam, T.W., Sung, W.K., Tam, S.L., Yiu, S.M.: Indexing Similar DNA Sequences. In: Chen, B. (ed.) AAIM 2010. LNCS, vol.\u00a06124, pp. 180\u2013190. Springer, Heidelberg (2010)"},{"key":"29_CR15","unstructured":"K\u00e4rkk\u00e4inen, J.: Repetition-Based Text Indexing. PhD thesis, Dept of Comp. Sci., Univ. of Helsinki, Finland (1999)"},{"key":"29_CR16","unstructured":"Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. Theor. Comp. Sci. (to appear, 2012); Earlier versions in Proc. DCC 2010 and Proc. CPM 2011"},{"issue":"3","key":"29_CR17","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., V\u00e4lim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. J. Comp. Biol.\u00a017(3), 281\u2013308 (2010)","journal-title":"J. Comp. Biol."},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"Manber, U., Myers, E.: Suffix arrays: a new method for on-line string searches. SIAM J. Comp., 935\u2013948 (1993)","DOI":"10.1137\/0222058"},{"issue":"3","key":"29_CR19","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G. Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM\u00a048(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"key":"29_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/978-3-642-24583-1_39","volume-title":"String Processing and Information Retrieval","author":"S. Maruyama","year":"2011","unstructured":"Maruyama, S., Nakahara, M., Kishiue, N., Sakamoto, H.: ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 398\u2013409. Springer, Heidelberg (2011)"},{"issue":"1","key":"29_CR21","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G. Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comp. Surv.\u00a039(1), article 2 (2007)","journal-title":"ACM Comp. Surv."},{"issue":"1-3","key":"29_CR22","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theo. Comp. Sci.\u00a0302(1-3), 211\u2013222 (2003)","journal-title":"Theo. Comp. Sci."},{"issue":"2","key":"29_CR23","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 functionalities of the compressed suffix arrays. J. Alg.\u00a048(2), 294\u2013313 (2003)","journal-title":"J. Alg."},{"issue":"3","key":"29_CR24","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theo.\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theo."},{"issue":"5","key":"29_CR25","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theo.\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theo."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35926-2_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:33:52Z","timestamp":1620135232000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35926-2_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642359255","9783642359262"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35926-2_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}