{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:28Z","timestamp":1740109288626,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T00:00:00Z","timestamp":1581897600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T00:00:00Z","timestamp":1581897600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"CONICYT Chile","award":["Fondecyt grant 1-171058","Basal Funds FB0001"],"award-info":[{"award-number":["Fondecyt grant 1-171058","Basal Funds FB0001"]}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Millennium Science Initiative, Chile","award":["Millenium Institute for Foundational Research on Data"],"award-info":[{"award-number":["Millenium Institute for Foundational Research on Data"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00453-020-00687-6","type":"journal-article","created":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T12:04:57Z","timestamp":1581941097000},"page":"2063-2086","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Compressed Dynamic Range Majority and Minority Data Structures"],"prefix":"10.1007","volume":"82","author":[{"given":"Travis","family":"Gagie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meng","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,17]]},"reference":[{"issue":"6","key":"687_CR1","doi-asserted-by":"crossref","first-page":"1488","DOI":"10.1137\/S009753970240481X","volume":"32","author":"L Arge","year":"2003","unstructured":"Arge, L., Vitter, J.S.: Optimal external memory interval management. SIAM J. Comput. 32(6), 1488\u20131508 (2003)","journal-title":"SIAM J. Comput."},{"key":"687_CR2","doi-asserted-by":"crossref","unstructured":"Beame, P., Jayram, T.S., Rudra, A.: Lower bounds for randomized read\/write stream algorithms. In: Proceedings 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 689\u2013698 (2007)","DOI":"10.1145\/1250790.1250891"},{"key":"687_CR3","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Gagie, T., Navarro, G.: Better space bounds for parameterized range majority and minority. In: Proceedings 12th Annual Workshop on Algorithms and Data Structures (WADS), pp. 121\u2013132 (2013)","DOI":"10.1007\/978-3-642-40104-6_11"},{"issue":"4","key":"687_CR4","doi-asserted-by":"crossref","DOI":"10.1145\/2629339","volume":"11","author":"D Belazzougui","year":"2015","unstructured":"Belazzougui, D., Navarro, G.: Optimal lower and upper bounds for representing sequences. ACM Trans. Algorithms 11(4), 31 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"687_CR5","unstructured":"Belazzougui, D., Gagie, T., Munro, J.I., Navarro, G., Nekrich, Y.: Range majorities and minorities in arrays. CoRR arXiv:1606.04495 (2016)"},{"key":"687_CR6","volume-title":"Text Compression","author":"TC Bell","year":"1990","unstructured":"Bell, T.C., Cleary, J., Witten, I.H.: Text Compression. Prentice Hall, Englewood Cliffs (1990)"},{"issue":"4","key":"687_CR7","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1007\/s00224-013-9455-2","volume":"55","author":"TM Chan","year":"2014","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. Theory Comput. Syst. 55(4), 719\u2013741 (2014)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"687_CR8","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1007\/s00453-014-9881-9","volume":"72","author":"TM Chan","year":"2015","unstructured":"Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. Algorithmica 72(4), 901\u2013913 (2015)","journal-title":"Algorithmica"},{"key":"687_CR9","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Frequency estimation of internet packet streams with limited space. In: Proceedings 10th Annual European Symposium on Algorithms (ESA), pp. 348\u2013360 (2002)","DOI":"10.1007\/3-540-45749-6_33"},{"key":"687_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.ic.2012.10.011","volume":"222","author":"S Durocher","year":"2013","unstructured":"Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. Inf. Comput. 222, 169\u2013179 (2013)","journal-title":"Inf. Comput."},{"key":"687_CR11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.tcs.2016.07.039","volume":"647","author":"A Elmasry","year":"2016","unstructured":"Elmasry, A., He, M., Munro, J.I., Nicholson, P.K.: Dynamic range majority data structures. Theor. Comput. Sci. 647, 59\u201373 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"687_CR12","unstructured":"Fang, M., Shivakumar, N., Garcia-Molina, H., Motwani, R., Ullman, J.D.: Computing iceberg queries efficiently. In: Proceedings 24rd International Conference on Very Large Data Bases (VLDB), pp. 299\u2013310 (1998)"},{"issue":"1","key":"687_CR13","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. Theor. Comput. Sci. 372(1), 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"687_CR14","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"key":"687_CR15","doi-asserted-by":"crossref","unstructured":"Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: Proceedings 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 345\u2013354 (1989)","DOI":"10.1145\/73007.73040"},{"key":"687_CR16","doi-asserted-by":"crossref","unstructured":"Gagie, T., He, M., Navarro, G.: Compressed dynamic range majority data structures. In: Proceedings 27th Data Compression Conference (DCC), pp. 260\u2013269 (2017)","DOI":"10.1109\/DCC.2017.9"},{"key":"687_CR17","doi-asserted-by":"crossref","unstructured":"Gagie, T., He, M., Munro, J.I., Nicholson, P.K.: Finding frequent elements in compressed 2d arrays and strings. In: Proceedings 18th International Symposium on String Processing and Information Retrieval (SPIRE), pp. 295\u2013300 (2011)","DOI":"10.1007\/978-3-642-24583-1_29"},{"key":"687_CR18","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Nicholson, P.K.: Optimal query time for encoding range majority. In: Proceedings 15th International Symposium on Algorithms and Data Structures (WADS), pp. 409\u2013420 (2017)","DOI":"10.1007\/978-3-319-62127-2_35"},{"key":"687_CR19","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Nicholson, P.K.: Optimal query time for encoding range majority. CoRR arXiv:1704.06149 (2017)","DOI":"10.1007\/978-3-319-62127-2_35"},{"key":"687_CR20","doi-asserted-by":"crossref","unstructured":"Greve, M., J\u00f8rgensen, A.G., Larsen, K.D., Truelsen, J.: Cell probe lower bounds and approximations for range mode. In: Proceedings 37th International Colloquium on Automata, Languages and Programming (ICALP), pp. 605\u2013616 (2010)","DOI":"10.1007\/978-3-642-14165-2_51"},{"key":"687_CR21","doi-asserted-by":"crossref","unstructured":"He, M., Munro, J.I.: Succinct representations of dynamic strings. In: Proceedings 17th International Symposium on String Processing and Information Retrieval (SPIRE). LNCS, vol. 6393, pp. 334\u2013346 (2010)","DOI":"10.1007\/978-3-642-16321-0_35"},{"issue":"3","key":"687_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":"687_CR23","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/762471.762473","volume":"28","author":"RM Karp","year":"2003","unstructured":"Karp, R.M., Shenker, S., Papadimitriou, C.H.: A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 28, 51\u201355 (2003)","journal-title":"ACM Trans. Database Syst."},{"key":"687_CR24","unstructured":"Karpinski, M., Nekrich, Y.: Searching for frequent colors in rectangles. In: Proceedings 20th Canadian Conference on Computational Geometry (CCCG), pp. 11\u201314 (2008)"},{"issue":"2","key":"687_CR25","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","volume":"2","author":"J Misra","year":"1982","unstructured":"Misra, J., Gries, D.: Finding repeated elements. Sci. Comput. Program. 2(2), 143\u2013152 (1982)","journal-title":"Sci. Comput. Program."},{"key":"687_CR26","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Nekrich, Y.: Compressed data structures for dynamic sequences. In: Proceedings 23rd Annual European Symposium on Algorithms (ESA), pp. 891\u2013902 (2015)","DOI":"10.1007\/978-3-662-48350-3_74"},{"issue":"3","key":"687_CR27","doi-asserted-by":"crossref","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"},{"issue":"3","key":"687_CR28","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.1007\/s00453-015-9987-8","volume":"74","author":"G Navarro","year":"2016","unstructured":"Navarro, G., Thankachan, S.V.: Optimal encodings for range majority queries. Algorithmica 74(3), 1082\u20131098 (2016)","journal-title":"Algorithmica"},{"issue":"1","key":"687_CR29","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/11084128X","volume":"43","author":"M Patrascu","year":"2014","unstructured":"Patrascu, M., Roditty, L.: Distance oracles beyond the Thorup\u2013Zwick bound. SIAM J. Comput. 43(1), 300\u2013311 (2014)","journal-title":"SIAM J. Comput."},{"key":"687_CR30","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct dynamic data structures. In: Proceedings 7th International Workshop on Algorithms and Data Structures (WADS), pp. 426\u2013437 (2001)","DOI":"10.1007\/3-540-44634-6_39"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00687-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00687-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00687-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T23:49:15Z","timestamp":1613692155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00687-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,17]]},"references-count":30,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["687"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00687-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,2,17]]},"assertion":[{"value":"21 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}