{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:39Z","timestamp":1740109299347,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:00:00Z","timestamp":1616112000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:00:00Z","timestamp":1616112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["268324"],"award-info":[{"award-number":["268324"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ANID, Chile"},{"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":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00453-021-00799-7","type":"journal-article","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T13:04:49Z","timestamp":1616159089000},"page":"1707-1733","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Range Majorities and Minorities in Arrays"],"prefix":"10.1007","volume":"83","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","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"}]},{"given":"Yakov","family":"Nekrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,19]]},"reference":[{"issue":"1","key":"799_CR1","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/s00453-012-9726-3","volume":"69","author":"J Barbay","year":"2014","unstructured":"Barbay, J., Claude, F., Gagie, T., Navarro, G., Nekrich, Y.: Efficient fully-compressed sequence representations. Algorithmica 69(1), 232\u2013268 (2014)","journal-title":"Algorithmica"},{"issue":"3","key":"799_CR2","first-page":"2","volume":"16","author":"D Belazzougui","year":"2011","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Theory and practice of monotone minimal perfect hashing. ACM J. Exp. Algorithm. 16(3), 2 (2011)","journal-title":"ACM J. Exp. Algorithm."},{"issue":"2","key":"799_CR3","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/3381417","volume":"16","author":"D Belazzougui","year":"2020","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Linear-time string indexing and analysis in small space. ACM Trans. Algorithm. 16(2), 17:1-17:54 (2020)","journal-title":"ACM Trans. Algorithm."},{"key":"799_CR4","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Gagie, T., Navarro, G.: Better space bounds for parameterized range majority and minority. In: Proceedings of the 12th Annual Workshop on Algorithms and Data Structures (WADS), LNCS 8037, pp. 121\u2013132 (2013)","DOI":"10.1007\/978-3-642-40104-6_11"},{"issue":"4","key":"799_CR5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/2635816","volume":"10","author":"D Belazzougui","year":"2014","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. ACM Trans. Algorithm. 10(4), 23 (2014)","journal-title":"ACM Trans. Algorithm."},{"issue":"4","key":"799_CR6","doi-asserted-by":"publisher","first-page":"31","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. Algorithm. 11(4), 31 (2015)","journal-title":"ACM Trans. Algorithm."},{"key":"799_CR7","doi-asserted-by":"crossref","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Approximate range mode and range median queries. In: Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), pp. 377\u2013388 (2005)","DOI":"10.1007\/978-3-540-31856-9_31"},{"key":"799_CR8","doi-asserted-by":"crossref","unstructured":"Boyer, R.S., Moore, J.S.: MJRTY\u2013a fast majority vote algorithm. In: Automated Reasoning, pp. 105\u2013117. Springer, Berlin (1991)","DOI":"10.1007\/978-94-011-3488-0_5"},{"issue":"4","key":"799_CR9","doi-asserted-by":"publisher","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":"799_CR10","doi-asserted-by":"publisher","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":"799_CR11","doi-asserted-by":"crossref","unstructured":"Cormode, G.: Misra-Gries summaries. In: Encyclopedia of Algorithms, pp. 1334\u20131337. Springer, Berlin (2016)","DOI":"10.1007\/978-1-4939-2864-4_572"},{"key":"799_CR12","unstructured":"Cormode, G., Muthukrishnan, S.: Data stream methods. http:\/\/www.cs.rutgers.edu\/~muthu\/198-3.pdf, 2003. Lecture 3 of Rutger\u2019s 198:671 Seminar on Processing Massive Data Sets"},{"key":"799_CR13","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.\u00a0I.: Frequency estimation of internet packet streams with limited space. In: Proceedings of the 10th European Symposium on Algorithms (ESA), pp. 348\u2013360 (2002)","DOI":"10.1007\/3-540-45749-6_33"},{"key":"799_CR14","doi-asserted-by":"publisher","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."},{"issue":"1","key":"799_CR15","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/s00453-014-9947-8","volume":"74","author":"S Durocher","year":"2016","unstructured":"Durocher, S., Shah, R., Skala, M., Thankachan, S.V.: Linear-space data structures for range frequency queries on arrays and trees. Algorithmica 74(1), 344\u2013366 (2016)","journal-title":"Algorithmica"},{"key":"799_CR16","doi-asserted-by":"publisher","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. Theoret. Comput. Sci. 647, 59\u201373 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"799_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1240233.1240243","volume":"3","author":"P Ferragina","year":"2007","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Algorithm. 3(2), 1\u201322 (2007)","journal-title":"ACM Trans. Algorithm."},{"issue":"1","key":"799_CR18","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"371","author":"P Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theoret. Comput. Sci. 371(1), 115\u2013121 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"799_CR19","doi-asserted-by":"publisher","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":"799_CR20","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 of the 18th Symposium on String Processing and Information Retrieval (SPIRE), pp. 295\u2013300 (2011)","DOI":"10.1007\/978-3-642-24583-1_29"},{"issue":"7","key":"799_CR21","doi-asserted-by":"publisher","first-page":"2063","DOI":"10.1007\/s00453-020-00687-6","volume":"82","author":"T Gagie","year":"2020","unstructured":"Gagie, T., He, M., Navarro, G.: Compressed dynamic range majority and minority data structures. Algorithmica 82(7), 2063\u20132086 (2020)","journal-title":"Algorithmica"},{"key":"799_CR22","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Nicholson, P.K.: Optimal query time for encoding range majority. In: Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS), pp. 409\u2013420 (2017). Extended version in CoRR abs\/1704.06149","DOI":"10.1007\/978-3-319-62127-2_35"},{"key":"799_CR23","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 of the 37th International Colloquium on Automata, Languages and Programming (ICALP), pp. 605\u2013616 (2010)","DOI":"10.1007\/978-3-642-14165-2_51"},{"key":"799_CR24","unstructured":"Grossi, R., Orlandi, A., Raman, R., Srinivasa Rao, S.: More haste, less waste: Lowering the redundancy in fully indexable dictionaries. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 517\u2013528 (2009)"},{"key":"799_CR25","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Vitter, J.: Space-efficient framework for top-$$k$$ string retrieval problems. In: Proceedings of the 50th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 713\u2013722 (2009)","DOI":"10.1109\/FOCS.2009.19"},{"issue":"1","key":"799_CR26","doi-asserted-by":"publisher","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(1), 51\u201355 (2003)","journal-title":"ACM Trans. Database Syst."},{"key":"799_CR27","unstructured":"Karpinski, M., Nekrich, Y.: Searching for frequent colors in rectangles. In: Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG), pp. 11\u201314 (2008)"},{"issue":"3","key":"799_CR28","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1137\/S0097539797331105","volume":"29","author":"R Kosaraju","year":"2000","unstructured":"Kosaraju, R., Manzini, G.: Compression of low entropy strings with Lempel-Ziv algorithms. SIAM J. Comput. 29(3), 893\u2013911 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"799_CR29","first-page":"1","volume":"12","author":"D Krizanc","year":"2005","unstructured":"Krizanc, D., Morin, P., Smid, M.H.M.: Range mode and range median queries on lists and trees. Nordic J. Comput. 12(1), 1\u201317 (2005)","journal-title":"Nordic J. Comput."},{"issue":"3","key":"799_CR30","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.jda.2007.10.001","volume":"6","author":"YK Lai","year":"2008","unstructured":"Lai, Y.K., Poon, C.K., Shi, B.: Approximate colored range and point enclosure queries. J. Discrete Algorithm. 6(3), 420\u2013432 (2008)","journal-title":"J. Discrete Algorithm."},{"issue":"2","key":"799_CR31","doi-asserted-by":"publisher","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."},{"issue":"2","key":"799_CR32","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/s00453-019-00637-x","volume":"82","author":"JI Munro","year":"2020","unstructured":"Munro, J.I., Navarro, G., Nekrich, Y.: Fast compressed self-indexes with deterministic linear-time construction. Algorithmica 82(2), 316\u2013337 (2020)","journal-title":"Algorithmica"},{"key":"799_CR33","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proceedings of the 13th Symposium on Discrete Algorithms (SODA), pp. 657\u2013666 (2002)"},{"issue":"3","key":"799_CR34","doi-asserted-by":"publisher","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"},{"key":"799_CR35","doi-asserted-by":"crossref","unstructured":"Petersen, H.: Improved bounds for range mode and range median queries. In: Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pp. 418\u2013423 (2008)","DOI":"10.1007\/978-3-540-77566-9_36"},{"issue":"4","key":"799_CR36","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.ipl.2008.10.007","volume":"109","author":"H Petersen","year":"2009","unstructured":"Petersen, H., Grabowski, S.: Range mode and range median queries in constant time and sub-quadratic space. Inf. Process. Lett. 109(4), 225\u2013228 (2009)","journal-title":"Inf. Process. Lett."},{"key":"799_CR37","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS), pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"issue":"1","key":"799_CR38","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithm. 5(1), 12\u201322 (2007)","journal-title":"J. Discrete Algorithm."},{"key":"799_CR39","doi-asserted-by":"crossref","unstructured":"Wei, Z., Yi, K.: Beyond simple aggregates: indexing for summary queries. In: Proceedings of the 30th Symposium on Principles of Database Systems (PODS), pp. 117\u2013128 (2011)","DOI":"10.1145\/1989284.1989299"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00799-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00799-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00799-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T10:07:12Z","timestamp":1621937232000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00799-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,19]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["799"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00799-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,3,19]]},"assertion":[{"value":"16 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}