{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:52:07Z","timestamp":1725688327637},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311543"},{"type":"electronic","value":"9783642311550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_26","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"295-306","source":"Crossref","is-referenced-by-count":12,"title":["Linear-Space Data Structures for Range Minority Query in Arrays"],"prefix":"10.1007","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephane","family":"Durocher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Skala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bryan T.","family":"Wilkinson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA Problem Revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"26_CR2","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., An, H.-C., 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)"},{"issue":"24","key":"26_CR3","doi-asserted-by":"publisher","first-page":"2588","DOI":"10.1016\/j.tcs.2010.05.003","volume":"412","author":"G.S. Brodal","year":"2011","unstructured":"Brodal, G.S., Gfeller, B., J\u00f8rgensen, A.G., Sanders, P.: Towards optimal range medians. Theor. Comp. Sci.\u00a0412(24), 2588\u20132601 (2011)","journal-title":"Theor. Comp. Sci."},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Persistent predecessor search and orthogonal point location on the word RAM. In: Proc. ACM-SIAM SODA, pp. 1131\u20131145 (2011)","DOI":"10.1137\/1.9781611973082.85"},{"key":"26_CR5","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: Proc. STACS, vol. 14, pp. 291\u2013301 (2012)"},{"issue":"3","key":"26_CR6","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: A new approach to query-answering. SIAM J. Comp.\u00a015(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comp."},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-642-02927-1_29","volume-title":"Automata, Languages and Programming","author":"E.D. Demaine","year":"2009","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian Trees and Range Minimum Queries. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 341\u2013353. Springer, Heidelberg (2009)"},{"key":"26_CR8","unstructured":"Durocher, S.: A simple linear-space data structure for constant-time range minimum query. CoRR, abs\/1109.4460 (2011)"},{"key":"26_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-22006-7_21","volume-title":"Automata, Languages and Programming","author":"S. Durocher","year":"2011","unstructured":"Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range Majority in Constant Time and Linear Space. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 244\u2013255. Springer, Heidelberg (2011)"},{"key":"26_CR10","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":"26_CR11","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":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-03784-9_1","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2009","unstructured":"Gagie, T., Puglisi, S.J., Turpin, A.: Range Quantile Queries: Another Virtue of Wavelet Trees. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 1\u20136. Springer, Heidelberg (2009)"},{"key":"26_CR13","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, Part I. LNCS, vol.\u00a06198, pp. 605\u2013616. Springer, Heidelberg (2010)"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, A.G., Larsen, K.D.: Range selection and median: Tight cell probe lower bounds and adaptive data structures. In: Proc. ACM-SIAM SODA, pp. 805\u2013813 (2011)","DOI":"10.1137\/1.9781611973082.63"},{"key":"26_CR15","unstructured":"Karpinski, M., Nekrich, Y.: Searching for frequent colors in rectangles. In: Proc. CCCG, pp. 11\u201314 (2008)"},{"key":"26_CR16","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 J. Computing\u00a012, 1\u201317 (2005)","journal-title":"Nordic J. Computing"},{"key":"26_CR17","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":"26_CR18","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. Proc. Let.\u00a0109, 225\u2013228 (2009)","journal-title":"Inf. Proc. Let."},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proc. ACM-SIAM SODA, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:48:33Z","timestamp":1620128913000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}