{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:36:15Z","timestamp":1742992575816,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319587400"},{"type":"electronic","value":"9783319587417"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-58741-7_17","type":"book-chapter","created":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T12:59:28Z","timestamp":1494507568000},"page":"162-174","source":"Crossref","is-referenced-by-count":8,"title":["Flexible Indexing of Repetitive Collections"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[]},{"given":"Fabio","family":"Cunial","sequence":"additional","affiliation":[]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[]},{"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[]},{"given":"Mathieu","family":"Raffinot","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/s00453-010-9443-8","volume":"62","author":"D Arroyuelo","year":"2012","unstructured":"Arroyuelo, D., Navarro, G., Sadakane, K.: Stronger Lempel-Ziv based compressed text indexing. Algorithmica 62, 54\u2013101 (2012)","journal-title":"Algorithmica"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Belazzougui, D.: Linear time construction of compressed text indices in compact space. In: Proceedings of the STOC, pp. 148\u2013193 (2014)","DOI":"10.1145\/2591796.2591885"},{"key":"17_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-319-19929-0_3","volume-title":"Combinatorial Pattern Matching","author":"D Belazzougui","year":"2015","unstructured":"Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M.: Composite repetition-aware data structures. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 26\u201339. Springer, Cham (2015). doi: 10.1007\/978-3-319-19929-0_3"},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A Blumer","year":"1987","unstructured":"Blumer, A., et al.: Complete inverted files for efficient text retrieval and analysis. JACM 34, 578\u2013595 (1987)","journal-title":"JACM"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u0103tra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proceediings of the SoCG, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"key":"17_CR6","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/978-3-662-07675-0_9","volume-title":"Handbook of Formal Languages","author":"M Crochemore","year":"1997","unstructured":"Crochemore, M., Hancart, C.: Automata for matching patterns. In: Rozenberg, G., et al. (eds.) Handbook of Formal Languages, pp. 399\u2013462. Springer, Heidelberg (1997)"},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/3-540-63220-4_55","volume-title":"Combinatorial Pattern Matching","author":"M Crochemore","year":"1997","unstructured":"Crochemore, M., V\u00e9rin, R.: Direct construction of compact directed acyclic word graphs. In: Apostolico, A., Hein, J. (eds.) CPM 1997. LNCS, vol. 1264, pp. 116\u2013129. Springer, Heidelberg (1997). doi: 10.1007\/3-540-63220-4_55"},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1145\/321892.321899","volume":"22","author":"P Elias","year":"1975","unstructured":"Elias, P., Flower, R.A.: The complexity of some simple retrieval problems. JACM 22, 367\u2013379 (1975)","journal-title":"JACM"},{"issue":"4","key":"17_CR9","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed texts. JACM 52(4), 552\u2013581 (2005)","journal-title":"JACM"},{"key":"17_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/978-3-642-54423-1_63","volume-title":"LATIN 2014: Theoretical Informatics","author":"T Gagie","year":"2014","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: LZ77-based self-indexing with faster pattern matching. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 731\u2013742. Springer, Heidelberg (2014). doi: 10.1007\/978-3-642-54423-1_63"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-07959-2_28","volume-title":"Experimental Algorithms","author":"S Gog","year":"2014","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326\u2013337. Springer, Cham (2014). doi: 10.1007\/978-3-319-07959-2_28"},{"key":"17_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"key":"17_CR13","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Lempel-Ziv parsing and sublinear-size index structures for string matching. In: Proceedings of the WSP, pp. 141\u2013155 (1996)"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Kreft, S.: Self-index based on LZ77. Master\u2019s thesis, Department of Computer Science, University of Chile (2010)","DOI":"10.1007\/978-3-642-21458-5_6"},{"key":"17_CR15","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","volume":"483","author":"S Kreft","year":"2013","unstructured":"Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. TCS 483, 115\u2013133 (2013)","journal-title":"TCS"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/11496656_5","volume-title":"Combinatorial Pattern Matching","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol. 3537, pp. 45\u201356. Springer, Heidelberg (2005). doi: 10.1007\/11496656_5"},{"key":"17_CR17","first-page":"281","volume":"17","author":"V M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., et al.: Storage and retrieval of highly repetitive sequence collections. JCB 17, 281\u2013308 (2010)","journal-title":"JCB"},{"key":"17_CR18","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"DR Morrison","year":"1968","unstructured":"Morrison, D.R.: PATRICIA \u2013 practical algorithm to retrieve information coded in alphanumeric. JACM 15, 514\u2013534 (1968)","journal-title":"JACM"},{"key":"17_CR19","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2002","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31, 762\u2013776 (2002)","journal-title":"SIAM J. Comput."},{"key":"17_CR20","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0020-0190(01)00152-1","volume":"80","author":"M Raffinot","year":"2001","unstructured":"Raffinot, M.: On maximal repeats in strings. IPL 80, 165\u2013169 (2001)","journal-title":"IPL"},{"key":"17_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-540-89097-3_17","volume-title":"String Processing and Information Retrieval","author":"J Sir\u00e9n","year":"2008","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V., Navarro, G.: Run-length compressed indexes are superior for highly repetitive sequence collections. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 164\u2013175. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-89097-3_17"},{"key":"17_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-38851-9_22","volume-title":"Experimental Algorithms","author":"D Valenzuela","year":"2016","unstructured":"Valenzuela, D.: CHICO: a compressed hybrid index for repetitive collections. In: Goldberg, A.V., Kulikov, A.S. (eds.) SEA 2016. LNCS, vol. 9685, pp. 326\u2013338. Springer, Cham (2016). doi: 10.1007\/978-3-319-38851-9_22"},{"key":"17_CR23","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space $$\\theta (n)$$ . IPL 17, 81\u201384 (1983)","journal-title":"IPL"},{"key":"17_CR24","first-page":"337","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE TIT 23, 337\u2013343 (1977)","journal-title":"IEEE TIT"}],"container-title":["Lecture Notes in Computer Science","Unveiling Dynamics and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-58741-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T08:47:14Z","timestamp":1569314834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-58741-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319587400","9783319587417"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-58741-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}