{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T05:45:42Z","timestamp":1748670342586,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_48","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"593-604","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max"],"prefix":"10.1007","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick K.","family":"Nicholson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"48_CR1","unstructured":"OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Number of Baxter permutations of length $$n$$ (2011). http:\/\/oeis.org\/A001181 (Accessed 24 September 2014)"},{"issue":"2","key":"48_CR2","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"MA Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. Journal of Algorithms 57(2), 75\u201394 (2005)","journal-title":"Journal of Algorithms"},{"issue":"24","key":"48_CR3","doi-asserted-by":"publisher","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. Theoretical Computer Science 412(24), 2588\u20132601 (2011)","journal-title":"Theoretical Computer Science"},{"key":"48_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Wilkinson, B.T.: Adaptive and approximate orthogonal range counting. In: Proc. of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 241\u2013251. SIAM (2013)","DOI":"10.1137\/1.9781611973105.18"},{"issue":"2016","key":"48_CR5","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1098\/rsta.2013.0131","volume":"372","author":"P Davoodi","year":"2014","unstructured":"Davoodi, P., Navarro, G., Raman, R., Rao, S.: Encoding Range Minima and Range Top-2 Queries. Phil. Trans. R. Soc. A 372(2016), 1471\u20132962 (2014)","journal-title":"Phil. Trans. R. Soc. A"},{"issue":"2","key":"48_CR6","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1215\/S0012-7094-47-01423-3","volume":"14","author":"A Dvoretzky","year":"1947","unstructured":"Dvoretzky, A., Motzkin, T.: A problem of arrangements. Duke Mathematical Journal 14(2), 305\u2013313 (1947)","journal-title":"Duke Mathematical Journal"},{"issue":"2","key":"48_CR7","doi-asserted-by":"publisher","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":"48_CR8","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. 5721, pp. 1\u20136. Springer, Heidelberg (2009)"},{"key":"48_CR9","unstructured":"Gawrychowski, P., Nicholson, P.K.: Optimal Encodings for Range Min-Max and Top-k. CoRR abs\/1411.6581 (2014). http:\/\/arxiv.org\/abs\/1411.6581"},{"key":"48_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/978-3-642-40450-4_47","volume-title":"Algorithms \u2013 ESA 2013","author":"R Grossi","year":"2013","unstructured":"Grossi, R., Iacono, J., Navarro, G., Raman, R., Rao, S.S.: Encodings\u00a0for\u00a0range\u00a0selection\u00a0and\u00a0top-k\u00a0queries. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 553\u2013564. Springer, Heidelberg (2013)"},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proc. of the 30th Annual Symposium on Foundations of Computer Science, pp. 549\u2013554. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"48_CR12","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, A.G., Larsen, K.G.: Range selection and median: tight cell probe lower bounds and adaptive data structures. In: Proc. of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 805\u2013813. SIAM (2011)","DOI":"10.1137\/1.9781611973082.63"},{"issue":"3","key":"48_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Computational Geometry 2(3), 169\u2013186 (1992)","journal-title":"Computational Geometry"},{"issue":"4","key":"48_CR14","first-page":"52","volume":"46","author":"G Navarro","year":"2013","unstructured":"Navarro, G.: Spaces, trees, and colors: The algorithmic landscape of document retrieval on sequences. ACM Comput. Surv. 46(4), 52 (2013)","journal-title":"ACM Comput. Surv."},{"key":"48_CR15","unstructured":"Navarro, G., Raman, R., Satti, S.R.: asymptotically optimal encodings for range selection. In: Proc. 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs, vol. 29, pp. 291\u2013301. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)"},{"issue":"1","key":"48_CR16","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 5(1), 12\u201322 (2007)","journal-title":"Journal of Discrete Algorithms"},{"key":"48_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-642-40273-9_21","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"M Skala","year":"2013","unstructured":"Skala, M.: Array range queries. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 333\u2013350. Springer, Heidelberg (2013)"},{"issue":"4","key":"48_CR18","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Communications of the ACM 23(4), 229\u2013239 (1980)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T15:24:53Z","timestamp":1674228293000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}