{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T17:06:02Z","timestamp":1709831162688},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,3,21]],"date-time":"2015-03-21T00:00:00Z","timestamp":1426896000000},"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":[[2016,3]]},"DOI":"10.1007\/s00453-015-9987-8","type":"journal-article","created":{"date-parts":[[2015,3,20]],"date-time":"2015-03-20T17:11:27Z","timestamp":1426871487000},"page":"1082-1098","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Encodings for Range Majority Queries"],"prefix":"10.1007","volume":"74","author":[{"given":"Gonzalo","family":"Navarro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,3,21]]},"reference":[{"key":"9987_CR1","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Gagie, T., Navarro, G.: Better space bounds for parameterized range majority and minority. In: Proc. 11th Annual Workshop on Algorithms and Data Structures (WADS), pp. 121\u2013132 (2013)","DOI":"10.1007\/978-3-642-40104-6_11"},{"issue":"2","key":"9987_CR2","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O Berkman","year":"1993","unstructured":"Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comput. 22(2), 221\u2013242 (1993)","journal-title":"SIAM J. Comput."},{"key":"9987_CR3","doi-asserted-by":"crossref","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Approximate range mode and range median queries. In: Proc. 22nd International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 377\u2013388 (2005)","DOI":"10.1007\/978-3-540-31856-9_31"},{"key":"9987_CR4","doi-asserted-by":"crossref","unstructured":"Brodal, G., Fagerberg, R., Greve, M., L\u00f3pez-Ortiz, A.: Online sorted range reporting. In: Proc. 20th Annual International Symposium on Algorithms and Computation (ISAAC), pp. 173\u2013182 (2009)","DOI":"10.1007\/978-3-642-10631-6_19"},{"key":"9987_CR5","unstructured":"Chan, T., Durocher, S., Larsen, K., Morrison, J., Wilkinson, B.: Linear-space data structures for range mode query in arrays. In: Proc. 29th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 290\u2013301 (2012)"},{"key":"9987_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T., Durocher, S., Skala, M., Wilkinson, B.: Linear-space data structures for range minority query in arrays. In: Proc. 13th Scandinavian Symposium on Algorithmic Theory (SWAT), pp. 295\u2013306 (2012)","DOI":"10.1007\/978-3-642-31155-0_26"},{"key":"9987_CR7","doi-asserted-by":"crossref","unstructured":"Chan, T., Wilkinson, B.: Adaptive and approximate orthogonal range counting. In: Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 241\u2013251 (2013)","DOI":"10.1137\/1.9781611973105.18"},{"key":"9987_CR8","unstructured":"Clark, D.: Compact PAT trees. Ph.D. thesis, University of Waterloo, Canada (1996)"},{"key":"9987_CR9","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.ic.2012.10.011","volume":"222","author":"S Durocher","year":"2013","unstructured":"Durocher, S., He, M., Munro, I., Nicholson, P., Skala, M.: Range majority in constant time and linear space. Inform. Comput. 222, 169\u2013179 (2013)","journal-title":"Inform. Comput."},{"key":"9987_CR10","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM 21, 246\u2013260 (1974)","journal-title":"J. ACM"},{"key":"9987_CR11","unstructured":"Fano, R.: On the number of bits required to implement an associative memory. Memo 61, Computer Structures Group, Project MAC, MA (1971)"},{"issue":"2","key":"9987_CR12","doi-asserted-by":"crossref","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":"9987_CR13","doi-asserted-by":"crossref","unstructured":"Gagie, T., He, M., Munro, I., Nicholson, P.: Finding frequent elements in compressed 2d arrays and strings. In: Proc. 18th International Symposium on String Processing and Information Retrieval (SPIRE), pp. 295\u2013300 (2011)","DOI":"10.1007\/978-3-642-24583-1_29"},{"key":"9987_CR14","doi-asserted-by":"crossref","unstructured":"Greve, M., J\u00f8rgensen, A., Larsen, K.D., Truelsen, J.: Cell probe lower bounds and approximations for range mode. In: Proc. 37th International Colloquium on Automata, Languages and Programming (ICALP), pp. 605\u2013616 (2010)","DOI":"10.1007\/978-3-642-14165-2_51"},{"key":"9987_CR15","doi-asserted-by":"crossref","unstructured":"Grossi, R., Iacono, J., Navarro, G., Raman, R., Satti, S.R.: Encodings for range selection and top-k queries. In: Proc. 21st Annual European Symposium on Algorithms (ESA), pp. 553\u2013564 (2013)","DOI":"10.1007\/978-3-642-40450-4_47"},{"key":"9987_CR16","unstructured":"Karpinski, M., Nekrich, Y.: Searching for frequent colors in rectangles. In: Proc. 20th Canadian Conference on Computational Geometry (CCCG), pp. 11\u201314 (2008)"},{"key":"9987_CR17","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Nekrich, Y.: Top-k color queries for document retrieval. In: Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 401\u2013411 (2011)","DOI":"10.1137\/1.9781611973082.32"},{"key":"9987_CR18","unstructured":"Navarro, G., Raman, R., Rao, S.S.: Asymptotically optimal encodings for range selection. In: Proc. 34th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 291\u2013302 (2014)"},{"key":"9987_CR19","doi-asserted-by":"crossref","unstructured":"Navarro, G., Thankachan, S.: Encodings for range majority queries. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P.A. (eds.) Proc. 25th Annual Symposium on Combinatorial Pattern Matching CPM. LNCS 8486, pp. 262\u2013272, (2014)","DOI":"10.1007\/978-3-319-07566-2_27"},{"key":"9987_CR20","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: Proc. 9th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 60\u201370 (2007)","DOI":"10.1137\/1.9781611972870.6"},{"issue":"4","key":"9987_CR21","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. Inform. Process. Lett. 109(4), 225\u2013228 (2009)","journal-title":"Inform. Process. Lett."},{"key":"9987_CR22","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. CoRR (2008). arXiv:cs\/0603043v1","DOI":"10.1007\/978-0-387-30162-4_298"},{"key":"9987_CR23","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"9987_CR24","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4) Article 43 (2007)","DOI":"10.1145\/1290672.1290680"},{"key":"9987_CR25","doi-asserted-by":"crossref","unstructured":"Ru\u017ei\u0107, M.: Constructing efficient dictionaries in close to sorting time. In: Aceto, L., Damg\u00e5rd, I., Ann Goldberg, L., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) Proc. 35th International Colloquium on Automata, Languages and Programming ICALP. LNCS 5125, pp. 84\u201395 (part I) (2008)","DOI":"10.1007\/978-3-540-70575-8_8"},{"key":"9987_CR26","doi-asserted-by":"crossref","unstructured":"Skala, M.: Array range queries. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola A. (eds.) Space-Efficient Data Structures, Streams, and Algorithms. LNCS, pp. 333\u2013350. Springer (2013)","DOI":"10.1007\/978-3-642-40273-9_21"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9987-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9987-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9987-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T05:41:07Z","timestamp":1566452467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9987-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,21]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["9987"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9987-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,21]]}}}