{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:28Z","timestamp":1759638088208},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,4,15]],"date-time":"2014-04-15T00:00:00Z","timestamp":1397520000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s00453-014-9881-9","type":"journal-article","created":{"date-parts":[[2014,4,14]],"date-time":"2014-04-14T11:25:11Z","timestamp":1397474711000},"page":"901-913","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Linear-Space Data Structures for Range Minority Query in Arrays"],"prefix":"10.1007","volume":"72","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","published-online":{"date-parts":[[2014,4,15]]},"reference":[{"key":"9881_CR1","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of LATIN, LNCS, vol. 1776, pp. 88\u201394. Springer, Berlin (2000)","DOI":"10.1007\/10719839_9"},{"key":"9881_CR2","doi-asserted-by":"crossref","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Approximate range mode and range median queries. In: Proceedings of STACS, LNCS, vol. 3404, pp. 377\u2013388. Springer, Berlin (2005)","DOI":"10.1007\/978-3-540-31856-9_31"},{"issue":"24","key":"9881_CR3","doi-asserted-by":"crossref","first-page":"2588","DOI":"10.1016\/j.tcs.2010.05.003","volume":"412","author":"GS Brodal","year":"2011","unstructured":"Brodal, G.S., Gfeller, B., J\u00f8rgensen, A.G., Sanders, P.: Towards optimal range medians. Theor. Comput. Sci. 412(24), 2588\u20132601 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9881_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Persistent predecessor search and orthogonal point location on the word RAM. In: Proceedings of ACM-SIAM SODA, pp. 1131\u20131145 (2011)","DOI":"10.1137\/1.9781611973082.85"},{"key":"9881_CR5","first-page":"291","volume":"14","author":"TM Chan","year":"2012","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. Proc. STACS 14, 291\u2013301 (2012)","journal-title":"Proc. STACS"},{"key":"9881_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. In: Proceedings of SWAT, LNCS, vol. 7357, pp. 295\u2013306. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-31155-0_26"},{"issue":"3","key":"9881_CR7","doi-asserted-by":"crossref","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. Comput. 15(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"9881_CR8","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian trees and range minimum queries. In: Proceedings of ICALP, LNCS, vol. 5555, pp. 341\u2013353. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-02927-1_29"},{"issue":"1","key":"9881_CR9","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"JR Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci. 38(1), 86\u2013124 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9881_CR10","doi-asserted-by":"crossref","unstructured":"Durocher, S.: A simple linear-space data structure for constant-time range minimum query. In: Proceedings of Conference on Space Efficient Data Structures, Streams and Algorithms, LNCS, vol. 8066, pp. 48\u201360. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-40273-9_5"},{"key":"9881_CR11","doi-asserted-by":"crossref","unstructured":"Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. In: Proceedings of ICALP, LNCS, vol. 6755, pp. 244\u2013255. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22006-7_21"},{"key":"9881_CR12","doi-asserted-by":"crossref","unstructured":"Elmasry, A., He, M., Munro, J.I., Nicholson, P.: Dynamic range majority data structures. In: Proceedings of ISAAC, LNCS, vol. 7074, pp. 150\u2013159. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-25591-5_17"},{"key":"9881_CR13","doi-asserted-by":"crossref","unstructured":"Gagie, T., He, M., Munro, J.I., Nicholson, P.: Finding frequent elements in compressed 2D arrays and strings. In: Proceedings of SPIRE, LNCS, vol. 7024, pp. 295\u2013300. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-24583-1_29"},{"key":"9881_CR14","doi-asserted-by":"crossref","unstructured":"Gagie, T., Puglisi, S.J., Turpin, A.: Range quantile queries: another virtue of wavelet trees. In: Proceedings of SPIRE, LNCS, vol. 5721, pp. 1\u20136. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-03784-9_1"},{"key":"9881_CR15","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 ICALP, LNCS, vol. 6198, pp. 605\u2013616. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-14165-2_51"},{"key":"9881_CR16","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: Proceedings of ACM-SIAM SODA, pp. 805\u2013813 (2011)","DOI":"10.1137\/1.9781611973082.63"},{"key":"9881_CR17","unstructured":"Karpinski, M., Nekrich, Y.: Searching for frequent colors in rectangles. In: Proceedings of CCCG, pp. 11\u201314 (2008)"},{"key":"9881_CR18","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. Comput. 12, 1\u201317 (2005)","journal-title":"Nordic J. Comput."},{"key":"9881_CR19","doi-asserted-by":"crossref","unstructured":"Petersen, H.: Improved bounds for range mode and range median queries. In: Proceedings of SOFSEM, LNCS, vol. 4910, pp. 418\u2013423. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-77566-9_36"},{"key":"9881_CR20","doi-asserted-by":"crossref","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. Lett. 109, 225\u2013228 (2009)","journal-title":"Inf. Proc. Lett."},{"key":"9881_CR21","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proceedings of ACM-SIAM SODA, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9881-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9881-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9881-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,9]],"date-time":"2019-08-09T10:10:32Z","timestamp":1565345432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9881-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,15]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9881"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9881-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4,15]]}}}