{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:42Z","timestamp":1759637682123},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_21","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T03:44:05Z","timestamp":1308541445000},"page":"244-255","source":"Crossref","is-referenced-by-count":9,"title":["Range Majority in Constant Time and Linear Space"],"prefix":"10.1007","author":[{"given":"Stephane","family":"Durocher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meng","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick K.","family":"Nicholson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Skala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(03)00186-0","volume":"137","author":"M. Aigner","year":"2004","unstructured":"Aigner, M.: Variants of the majority problem. Discrete Applied Mathematics\u00a0137, 3\u201325 (2004)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"21_CR2","first-page":"1","volume":"4","author":"L. Alonso","year":"2008","unstructured":"Alonso, L., Reingold, E.M.: Determining plurality. ACM Transactions on Algorithms\u00a04(3), 26:1\u201326:19 (2008)","journal-title":"ACM Transactions on Algorithms"},{"key":"21_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/978-3-540-31856-9_31","volume-title":"STACS 2005","author":"P. Bose","year":"2005","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Approximate range mode and range median queries. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 377\u2013388. Springer, Heidelberg (2005)"},{"key":"21_CR4","series-title":"Automated Reasoning Series","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-94-011-3488-0_5","volume-title":"Automated Reasoning: Essays in Honor of Woody Bledsoe","author":"R.S. Boyer","year":"1991","unstructured":"Boyer, R.S., Moore, J.S.: MJRTY - A fast majority vote algorithm. In: Boyer, R.S. (ed.) Automated Reasoning: Essays in Honor of Woody Bledsoe. Automated Reasoning Series, pp. 105\u2013117. Kluwer, Dordrecht (1991)"},{"issue":"1","key":"21_CR5","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms\u00a055(1), 58\u201375 (2005)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"21_CR6","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(80)90057-2","volume":"12","author":"D. Dobkin","year":"1980","unstructured":"Dobkin, D., Munro, J.I.: Determining the mode. Theoretical Computer Science\u00a012(3), 255\u2013263 (1980)","journal-title":"Theoretical Computer Science"},{"key":"21_CR7","unstructured":"Durocher, S., Morrison, J.: Linear-space data structures for range mode query in arrays (2011), arXiv:1101.4068v1"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/978-3-642-14165-2_51","volume-title":"Automata, Languages and Programming","author":"M. Greve","year":"2010","unstructured":"Greve, M., J\u00f8rgensen, A.G., Larsen, K.D., Truelsen, J.: Cell probe lower bounds and approximations for range mode. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 605\u2013616. Springer, Heidelberg (2010)"},{"key":"21_CR9","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. of the 14th Symposium on Discrete Algorithms, pp. 841\u2013850 (2003)"},{"key":"21_CR10","unstructured":"Karpinski, M., Nekrich, Y.: Searching for frequent colors in rectangles. In: Proc. of the 20th Canadian Conference on Computational Geometry, pp. 11\u201314 (2008)"},{"key":"21_CR11","first-page":"1","volume":"12","author":"D. Krizanc","year":"2005","unstructured":"Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. Nordic Journal of Computing\u00a012, 1\u201317 (2005)","journal-title":"Nordic Journal of Computing"},{"issue":"2","key":"21_CR12","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. Science of Computer Programming\u00a02(2), 143\u2013152 (1982)","journal-title":"Science of Computer Programming"},{"issue":"1","key":"21_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0205001","volume":"5","author":"J.I. Munro","year":"1976","unstructured":"Munro, J.I., Spira, M.: Sorting and searching in multisets. SIAM Journal on Computing\u00a05(1), 1\u20138 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/978-3-540-77566-9_36","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H. Petersen","year":"2008","unstructured":"Petersen, H.: Improved bounds for range mode and range median queries. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 418\u2013423. Springer, Heidelberg (2008)"},{"key":"21_CR15","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. Information Processing Letters\u00a0109, 225\u2013228 (2009)","journal-title":"Information Processing Letters"},{"key":"21_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-070-4","volume-title":"The Algorithm Design Manual","author":"S. Skiena","year":"2008","unstructured":"Skiena, S.: The Algorithm Design Manual, 2nd edn. Springer, Heidelberg (2008)","edition":"2"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T03:03:09Z","timestamp":1553828589000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}