{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:50Z","timestamp":1781078210796,"version":"3.54.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,10,16]],"date-time":"2017-10-16T00:00:00Z","timestamp":1508112000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["4005-00267"],"award-info":[{"award-number":["4005-00267"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["4005-00267"],"award-info":[{"award-number":["4005-00267"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Det Frie Forskningsr\u00e5d (DK)","award":["DFF - 1323-00178"],"award-info":[{"award-number":["DFF - 1323-00178"]}]},{"name":"Det Frie Forskningsr\u00e5d (DK)","award":["DFF - 1323-00178"],"award-info":[{"award-number":["DFF - 1323-00178"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00453-017-0380-7","type":"journal-article","created":{"date-parts":[[2017,10,16]],"date-time":"2017-10-16T10:37:24Z","timestamp":1508150244000},"page":"3207-3224","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation"],"prefix":"10.1007","volume":"80","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anders Roy","family":"Christiansen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrick Hagge","family":"Cording","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frederik Rye","family":"Skjoldjensen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hjalte Wedel","family":"Vildh\u00f8j","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00f8ren","family":"Vind","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,10,16]]},"reference":[{"key":"380_CR1","unstructured":"Alstrup, S., Brodal, G. S., Rauhe, T.: Pattern matching in dynamic texts. In: Proceedings of 11th SODA, pp. 819\u2013828 (2000)"},{"issue":"2","key":"380_CR2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1240233.1240242","volume":"3","author":"A Amir","year":"2007","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Sokol, D.: Dynamic text and static pattern matching. ACM TALG 3(2), 19 (2007)","journal-title":"ACM TALG"},{"key":"380_CR3","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Fast prefix search in little space, with applications. In: Proceedings of 18th ESA, pp. 427\u2013438 (2010)","DOI":"10.1007\/978-3-642-15775-2_37"},{"issue":"1","key":"380_CR4","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s00224-013-9498-4","volume":"55","author":"P Bille","year":"2014","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Vind, S.: String indexing for patterns with wildcards. Theory Comput. Syst. 55(1), 41\u201360 (2014)","journal-title":"Theory Comput. Syst."},{"key":"380_CR5","doi-asserted-by":"crossref","unstructured":"Chern, B., Ochoa, I., Manolakos, A., No, A., Venkat, K., Weissman, T.: Reference based genome compression. In: IEEE ITW, pp. 427\u2013431 (2012)","DOI":"10.1109\/ITW.2012.6404708"},{"key":"380_CR6","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of 36th STOC, pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"380_CR7","doi-asserted-by":"crossref","unstructured":"Dietz, P. F.: Optimal algorithms for list indexing and subset rank. In: Proceedings of 1st WADS, pp. 39\u201346 (1989)","DOI":"10.1007\/3-540-51542-9_5"},{"key":"380_CR8","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.tcs.2013.07.024","volume":"532","author":"HH Do","year":"2014","unstructured":"Do, H.H., Jansson, J., Sadakane, K., Sung, W.-K.: Fast relative Lempel\u2013Ziv self-index for similar sequences. TCS 532, 14\u201330 (2014)","journal-title":"TCS"},{"issue":"3","key":"380_CR9","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1002\/spe.4380240306","volume":"24","author":"PM Fenwick","year":"1994","unstructured":"Fenwick, P.M.: A new data structure for cumulative frequency tables. Softw. Pract. Exp. 24(3), 327\u2013336 (1994)","journal-title":"Softw. Pract. Exp."},{"issue":"4","key":"380_CR10","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 text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"380_CR11","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Succinct representation of sequences. Technical report (2004)"},{"issue":"1","key":"380_CR12","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"372","author":"P Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. TCS 372(1), 115\u2013121 (2007)","journal-title":"TCS"},{"key":"380_CR13","doi-asserted-by":"crossref","unstructured":"Fischer, J., Gagie, T., Gawrychowski, P., Kociumaka, T.: Approximating lz77 via small-space multiple-pattern matching. In: Algorithms-ESA 2015, pp. 533\u2013544. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_45"},{"key":"380_CR14","doi-asserted-by":"crossref","unstructured":"Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: Proceedings of 21st STOC, pp. 345\u2013354 (1989)","DOI":"10.1145\/73007.73040"},{"issue":"3","key":"380_CR15","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"ML Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424\u2013436 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"380_CR16","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Lewenstein, M., Nicholson, P. K.: Weighted ancestors in suffix trees. In: Proceedings of 22nd ESA, pp. 455\u2013466 (2014)","DOI":"10.1007\/978-3-662-44777-2_38"},{"key":"380_CR17","doi-asserted-by":"crossref","unstructured":"Goswami, M., Gr\u00f8nlund, A., Larsen, K. G., Pagh, R.: Approximate range emptiness in constant time and optimal space. In: Proceedings of 26th SODA, pp. 769\u2013775 (2015)","DOI":"10.1137\/1.9781611973730.52"},{"key":"380_CR18","unstructured":"Grossi, R., Gupta, A., Vitter, J. S.: High-order entropy-compressed text indexes. In: Proceedings of 14th SODA, pp. 841\u2013850 (2003)"},{"issue":"2","key":"380_CR19","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"39","key":"380_CR20","doi-asserted-by":"crossref","first-page":"5176","DOI":"10.1016\/j.tcs.2011.05.023","volume":"412","author":"W-K Hon","year":"2011","unstructured":"Hon, W.-K., Sadakane, K., Sung, W.-K.: Succinct data structures for searchable partial sums with optimal worst-case performance. TCS 412(39), 5176\u20135186 (2011)","journal-title":"TCS"},{"issue":"3","key":"380_CR21","first-page":"265","volume":"5","author":"C Hoobin","year":"2011","unstructured":"Hoobin, C., Puglisi, S.J., Zobel, J.: Relative Lempel\u2013Ziv factorization for efficient storage and retrieval of web collections. PVLDB 5(3), 265\u2013273 (2011)","journal-title":"PVLDB"},{"issue":"3","key":"380_CR22","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1137\/S0097539701391592","volume":"32","author":"T Husfeldt","year":"2003","unstructured":"Husfeldt, T., Rauhe, T.: New lower bound techniques for dynamic partial sums and related problems. SIAM J. Comput. 32(3), 736\u2013753 (2003)","journal-title":"SIAM J. Comput."},{"key":"380_CR23","doi-asserted-by":"crossref","unstructured":"Husfeldt, T., Rauhe, T., Skyum, S.: Lower bounds for dynamic transitive closure, planar point location, and parentheses matching. In: Proceedings of 5th SWAT, pp. 198\u2013211 (1996)","DOI":"10.1007\/3-540-61422-2_132"},{"key":"380_CR24","doi-asserted-by":"crossref","unstructured":"Jansson, J., Sadakane, K., Sung, W.-K.: CRAM: compressed random access memory. In: Proceedings of 39th ICALP, pp. 510\u2013521 (2012)","DOI":"10.1007\/978-3-642-31594-7_43"},{"key":"380_CR25","volume-title":"The C Programming Language","author":"B Kernighan","year":"1978","unstructured":"Kernighan, B., Ritchie, D.: The C Programming Language, 1st edn. Prentice-Hall, Upper Saddle River (1978)","edition":"1"},{"key":"380_CR26","doi-asserted-by":"crossref","unstructured":"Kuruppu, S., Puglisi, S. J., Zobel, J.: Relative Lempel\u2013Ziv compression of genomes for large-scale storage and retrieval. In: Proceedings of 17th SPIRE, pp. 201\u2013206 (2010)","DOI":"10.1007\/978-3-642-16321-0_20"},{"key":"380_CR27","unstructured":"Kuruppu, S., Puglisi, S. J., Zobel, J.: Optimized relative Lempel\u2013Ziv compression of genomes. In: Proceedings of 34th ACSC, pp. 91\u201398 (2011)"},{"key":"380_CR28","unstructured":"Lewenstein, M., Nekrich, Y., Vitter, J. S.: Space-efficient string indexing for wildcard pattern matching. In: Proceedings of 31st STACS, pp. 506\u2013517 (2014)"},{"issue":"1","key":"380_CR29","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/298865.298867","volume":"4","author":"SY Liao","year":"1999","unstructured":"Liao, S.Y., Devadas, S., Keutzer, K.: A text-compression-based method for code size minimization in embedded systems. ACM Trans. Des. Autom. Electron. Syst. 4(1), 12\u201338 (1999)","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"issue":"1","key":"380_CR30","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1023\/A:1008803430710","volume":"3","author":"SY Liao","year":"1998","unstructured":"Liao, S.Y., Devadas, S., Keutzer, K., Tjiang, S.W.K., Wang, A.: Code optimization techniques in embedded DSP microprocessors. Des. Autom. Embed. Syst. 3(1), 59\u201373 (1998)","journal-title":"Des. Autom. Embed. Syst."},{"issue":"4","key":"380_CR31","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0020-0190(90)90022-P","volume":"35","author":"K Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4hler, S.: Bounded ordered dictionaries in $$O(\\log \\log N)$$ O ( log log N ) time and $$O(n)$$ O ( n ) space. Inf. Process. Lett. 35(4), 183\u2013189 (1990)","journal-title":"Inf. Process. Lett."},{"key":"380_CR32","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. In: Proceedings of 24th SODA, pp. 865\u2013876 (2013)","DOI":"10.1137\/1.9781611973105.62"},{"issue":"3","key":"380_CR33","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/2601073","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"380_CR34","unstructured":"P\u0103tra\u015fcu, M., Demaine, E. D.: Tight bounds for the partial-sums problem. In: Proceedings of 15th SODA, pp. 20\u201329 (2004)"},{"key":"380_CR35","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M., Thorup, M.: Dynamic integer sets with optimal rank, select, and predecessor search. In: Proceedings of 55th FOCS, pp. 166\u2013175 (2014)","DOI":"10.1109\/FOCS.2014.26"},{"key":"380_CR36","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S. S.: Succinct dynamic data structures. In: Proceedings of 7th WADS, pp. 426\u2013437 (2001)","DOI":"10.1007\/3-540-44634-6_39"},{"key":"380_CR37","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: Proceedings of 17th SODA, pp. 1230\u20131239 (2006)","DOI":"10.1145\/1109557.1109693"},{"key":"380_CR38","doi-asserted-by":"crossref","unstructured":"Storer, J. A., Szymanski, T. G.: The macro model for data compression. In: Proceedings of 10th STOC, pp. 30\u201339 (1978)","DOI":"10.1145\/800133.804329"},{"issue":"4","key":"380_CR39","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"JA Storer","year":"1982","unstructured":"Storer, J.A., Szymanski, T.G.: Data compression via textual substitution. J. ACM 29(4), 928\u2013951 (1982)","journal-title":"J. ACM"},{"key":"380_CR40","unstructured":"Stroustrup, B.: The C++ Programming Language: Special Edition, 3rd edn. Addison-Wesley (2000). First edition from 1985"},{"issue":"3","key":"380_CR41","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P Emde Baos van","year":"1977","unstructured":"van Emde Baos, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6(3), 80\u201382 (1977)","journal-title":"Inf. Process. Lett."},{"key":"380_CR42","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E., Zijlstra, E.: Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99\u2013127 (1977)","journal-title":"Math. Syst. Theory"},{"issue":"3","key":"380_CR43","doi-asserted-by":"crossref","first-page":"1030","DOI":"10.1137\/S0097539797322425","volume":"29","author":"DE Willard","year":"2000","unstructured":"Willard, D.E.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput. 29(3), 1030\u20131049 (2000)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0380-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0380-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0380-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T15:02:17Z","timestamp":1570201337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0380-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,16]]},"references-count":43,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["380"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0380-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,16]]}}}