{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:13Z","timestamp":1759638073260},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_11","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T01:36:30Z","timestamp":1373506590000},"page":"121-132","source":"Crossref","is-referenced-by-count":11,"title":["Better Space Bounds for Parameterized Range Majority and Minority"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","unstructured":"Barbay, J., Claude, F., Gagie, T., Navarro, G., Nekrich, Y.: Efficient fully-compressed sequence representations. Algorithmica (to appear)"},{"key":"11_CR2","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. ACM Transactions on Algorithms (to appear)"},{"key":"11_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1007\/978-3-642-23719-5_63","volume-title":"Algorithms \u2013 ESA 2011","author":"D. Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 748\u2013759. Springer, Heidelberg (2011)"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-642-33090-2_17","volume-title":"Algorithms \u2013 ESA 2012","author":"D. Belazzougui","year":"2012","unstructured":"Belazzougui, D., Navarro, G.: New lower and upper bounds for representing sequences. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 181\u2013192. Springer, Heidelberg (2012)"},{"key":"11_CR5","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":"11_CR6","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. In: Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 290\u2013301 (2012)"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-31155-0_26","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 295\u2013306. Springer, Heidelberg (2012)"},{"key":"11_CR8","unstructured":"Cormode, G., Muthukrishnan, S.: Data stream methods. Lecture 3 of Rutger\u2019s 198:671 Seminar on Processing Massive Data Sets (2003), \n                  \n                    http:\/\/www.cs.rutgers.edu\/~muthu\/198-3.pdf"},{"key":"11_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/3-540-45749-6_33","volume-title":"Algorithms - ESA 2002","author":"E.D. Demaine","year":"2002","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Frequency estimation of internet packet streams with limited space. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 348\u2013360. Springer, Heidelberg (2002)"},{"key":"11_CR10","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. Information and Computation\u00a0222, 169\u2013179 (2013)","journal-title":"Information and Computation"},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-642-25591-5_17","volume-title":"Algorithms and Computation","author":"A. Elmasry","year":"2011","unstructured":"Elmasry, A., He, M., Munro, J.I., Nicholson, P.K.: Dynamic range majority data structures. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 150\u2013159. Springer, Heidelberg (2011)"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms\u00a03(2) (2007)","DOI":"10.1145\/1240233.1240243"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-12200-2_16","volume-title":"LATIN 2010: Theoretical Informatics","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 158\u2013169. Springer, Heidelberg (2010)"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-24583-1_29","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2011","unstructured":"Gagie, T., He, M., Munro, J.I., Nicholson, P.K.: Finding frequent elements in compressed 2D arrays and strings. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 295\u2013300. Springer, Heidelberg (2011)"},{"key":"11_CR15","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)"},{"issue":"1","key":"11_CR16","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/762471.762473","volume":"28","author":"R.M. Karp","year":"2003","unstructured":"Karp, R.M., Shenker, S., Papadimitriou, C.H.: A simple algorithm for finding frequent elements in streams and bags. ACM Transactions on Database Systems\u00a028(1), 51\u201355 (2003)","journal-title":"ACM Transactions on Database Systems"},{"key":"11_CR17","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":"1","key":"11_CR18","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 Journal of Computing\u00a012(1), 1\u201317 (2005)","journal-title":"Nordic Journal of Computing"},{"issue":"3","key":"11_CR19","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.jda.2007.10.001","volume":"6","author":"Y.K. Lai","year":"2008","unstructured":"Lai, Y.K., Poon, C.K., Shi, B.: Approximate colored range and point enclosure queries. Journal of Discrete Algorithms\u00a06(3), 420\u2013432 (2008)","journal-title":"Journal of Discrete Algorithms"},{"issue":"2","key":"11_CR20","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"},{"key":"11_CR21","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proceedings of the 13th Symposium on Discrete Algorithms (SODA), pp. 657\u2013666 (2002)"},{"key":"11_CR22","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)"},{"issue":"4","key":"11_CR23","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 Letter\u00a0109(4), 225\u2013228 (2009)","journal-title":"Information Processing Letter"},{"key":"11_CR24","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":"11_CR25","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. Journal of Discrete Algorithms\u00a05(1), 12\u201322 (2007)","journal-title":"Journal of Discrete Algorithms"},{"key":"11_CR26","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":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T14:23:01Z","timestamp":1557930181000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}