{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,4]],"date-time":"2025-04-04T01:47:29Z","timestamp":1743731249917},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642283314"},{"type":"electronic","value":"9783642283321"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28332-1_21","type":"book-chapter","created":{"date-parts":[[2012,2,29]],"date-time":"2012-02-29T09:45:36Z","timestamp":1330508736000},"page":"240-251","source":"Crossref","is-referenced-by-count":49,"title":["A Faster Grammar-Based Self-index"],"prefix":"10.1007","author":[{"given":"Travis","family":"Gagie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yakov","family":"Nekrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u01cetra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proceedings of the 27th Symposium on Computational Geometry (SoCG), pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"7","key":"21_CR2","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 Transactions on Information Theory\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"key":"21_CR3","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: Proceedings of the Data Compression Conference (DCC), pp. 252\u2013261 (2008)","DOI":"10.1109\/DCC.2008.67"},{"key":"21_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-03816-7_21","volume-title":"Mathematical Foundations of Computer Science 2009","author":"F. Claude","year":"2009","unstructured":"Claude, F., Navarro, G.: Self-indexed Text Compression Using Straight-Line Programs. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 235\u2013246. Springer, Heidelberg (2009)"},{"key":"21_CR5","unstructured":"Claude, F., Navarro, G.: Improved grammar-based self-indexes. Tech. Rep. 1110.4493, arxiv.org (2011)"},{"key":"21_CR6","unstructured":"Do, H.H., Jansson, J., Sadakane, K., Sung, W.K.: Indexing strings via textual substitutions from a reference, manuscript"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time. In: Proceedings of the 16th Symposium on Foundations of Computer Science (FOCS), pp. 75\u201384 (1975)","DOI":"10.1109\/SFCS.1975.26"},{"issue":"4","key":"21_CR8","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 text. Journal of the ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"Journal of the ACM"},{"issue":"8-9","key":"21_CR9","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/j.ipl.2010.02.010","volume":"110","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Wee LCP. Information Processing Letters\u00a0110(8-9), 317\u2013320 (2010)","journal-title":"Information Processing Letters"},{"issue":"22","key":"21_CR10","doi-asserted-by":"publisher","first-page":"2451","DOI":"10.1016\/j.tcs.2011.01.036","volume":"412","author":"J. Fischer","year":"2011","unstructured":"Fischer, J.: Combined data structure for previous- and next-smaller-values. Theoretical Computer Science\u00a0412(22), 2451\u20132456 (2011)","journal-title":"Theoretical Computer Science"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the 16th Symposium on Theory of Computing (STOC), pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"key":"21_CR12","unstructured":"Gagie, T., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A compressed self-index for genomic databases. Tech. Rep. 1110.1355, arxiv.org (2011)"},{"key":"21_CR13","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the 14th Symposium on Discrete Algorithms (SODA), pp. 841\u2013850 (2003)"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-03784-9_8","volume-title":"String Processing and Information Retrieval","author":"W.-K. Hon","year":"2009","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: On Entropy-Compressed Text Indexing in External Memory. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 75\u201389. Springer, Heidelberg (2009)"},{"key":"21_CR15","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":"21_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-21458-5_6","volume-title":"Combinatorial Pattern Matching","author":"S. Kreft","year":"2011","unstructured":"Kreft, S., Navarro, G.: Self-indexing Based on LZ77. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 41\u201354. Springer, Heidelberg (2011)"},{"key":"21_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-16321-0_20","volume-title":"String Processing and Information Retrieval","author":"S. Kuruppu","year":"2010","unstructured":"Kuruppu, S., Puglisi, S.J., Zobel, J.: Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 201\u2013206. Springer, Heidelberg (2010)"},{"key":"21_CR18","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":"2","key":"21_CR19","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E.M. McCreight","year":"1985","unstructured":"McCreight, E.M.: Priority search trees. SIAM Journal on Computing\u00a014(2), 257\u2013276 (1985)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"21_CR20","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D.R. Morrison","year":"1968","unstructured":"Morrison, D.R.: PATRICIA - Practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM\u00a015(4), 514\u2013534 (1968)","journal-title":"Journal of the ACM"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys\u00a039(1) (2007)","DOI":"10.1145\/1216370.1216372"},{"issue":"1-3","key":"21_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. Theoretical Computer Science\u00a0302(1-3), 211\u2013222 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"21_CR23","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 Transactions on Information Theory\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28332-1_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,24]],"date-time":"2019-06-24T14:23:46Z","timestamp":1561386226000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28332-1_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642283314","9783642283321"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28332-1_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}