{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:58:54Z","timestamp":1742979534707,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_40","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T08:37:10Z","timestamp":1246696630000},"page":"475-486","source":"Crossref","is-referenced-by-count":13,"title":["Towards Optimal Range Medians"],"prefix":"10.1007","author":[{"given":"Beat","family":"Gfeller","sequence":"first","affiliation":[]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"40_CR1","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"M.A. Bender","year":"2004","unstructured":"Bender, M.A., Farach-Colton, M.: The Level Ancestor Problem simplified. Theor. Comput. Sci.\u00a0321(1), 5\u201312 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Linear Time Bounds for Median Computations. In: 4th Annual Symp. on Theory of Computing (STOC), pp. 119\u2013124 (1972)","DOI":"10.1145\/800152.804904"},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: I. A data structuring technique. Algorithmica\u00a01, 133\u2013162 (1986)","journal-title":"Algorithmica"},{"key":"40_CR4","unstructured":"Clark, D.R.: Compact Pat Trees. PhD thesis, University of Waterloo (1988)"},{"key":"40_CR5","doi-asserted-by":"crossref","unstructured":"Cline, D., White, K.B., Egbert, P.K.: Fast 8-bit median filtering based on separability. In: IEEE International Conference on Image Processing (ICIP), vol.\u00a05, pp. 281\u2013284 (2007)","DOI":"10.1109\/ICIP.2007.4379820"},{"key":"40_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry Algorithms and Applications","author":"M. Berg de","year":"2000","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry Algorithms and Applications, 2nd edn. Springer, Heidelberg (2000)","edition":"2"},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"Gfeller, B., Sanders, P.: Towards optimal range medians. CoRR, abs\/0901.1761 (2009)","DOI":"10.1007\/978-3-642-02927-1_40"},{"issue":"5","key":"40_CR8","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1109\/34.211471","volume":"15","author":"J. Gil","year":"1993","unstructured":"Gil, J., Werman, M.: Computing 2-d min, median, and max filters. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a015(5), 504\u2013507 (1993)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"40_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/978-3-540-87744-8_42","volume-title":"Algorithms - ESA 2008","author":"S. Har-Peled","year":"2008","unstructured":"Har-Peled, S., Muthukrishnan, S.M.: Range Medians. In: Halperin, D., Mehlhorn, K. (eds.) Esa 2008. LNCS, vol.\u00a05193, pp. 503\u2013514. Springer, Heidelberg (2008)"},{"key":"40_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1007\/978-3-540-30551-4_49","volume-title":"Algorithms and Computation","author":"J. J\u00e1J\u00e1","year":"2004","unstructured":"J\u00e1J\u00e1, J., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 558\u2013568. Springer, Heidelberg (2004)"},{"issue":"1","key":"40_CR11","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. Nord. J. Comput.\u00a012(1), 1\u201317 (2005)","journal-title":"Nord. J. Comput."},{"key":"40_CR12","series-title":"Sorting and Searching","volume-title":"Data structures and algorithms","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data structures and algorithms. Sorting and Searching, vol.\u00a01. Springer, Berlin (1984)"},{"key":"40_CR13","first-page":"137","volume-title":"4th Annual Symp. on Theory of Computing (STOC)","author":"J. Nievergelt","year":"1972","unstructured":"Nievergelt, J., Reingold, E.M.: Binary Search Trees of Bounded Balance. In: 4th Annual Symp. on Theory of Computing (STOC), pp. 137\u2013142. ACM Press, New York (1972)"},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. The Computing Research Repository (CoRR), abs\/cs\/0610001 (2006)","DOI":"10.1137\/1.9781611972870.6"},{"key":"40_CR15","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":"40_CR16","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 Letters\u00a0109(4), 225\u2013228 (2009)","journal-title":"Information Processing Letters"},{"issue":"9","key":"40_CR17","doi-asserted-by":"publisher","first-page":"2389","DOI":"10.1109\/TIP.2007.902329","volume":"16","author":"S. Perreault","year":"2007","unstructured":"Perreault, S., H\u00e9bert, P.: Median filtering in constant time. IEEE Transactions on Image Processing\u00a016(9), 2389\u20132394 (2007)","journal-title":"IEEE Transactions on Image Processing"},{"key":"40_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/3-540-48224-5_39","volume-title":"Automata, Languages and Programming","author":"S. Roura","year":"2001","unstructured":"Roura, S.: A New Method for Balancing Binary Search Trees. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 469\u2013480. Springer, Heidelberg (2001)"},{"issue":"2","key":"40_CR19","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0743-7315(91)90022-2","volume":"12","author":"P.J. Varman","year":"1991","unstructured":"Varman, P.J., Scheufler, S.D., Iyer, B.R., Ricard, G.R.: Merging multiple lists on hierarchical-memory multiprocessors. J. Parallel Distrib. Comput.\u00a012(2), 171\u2013177 (1991)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"3","key":"40_CR20","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1145\/3828.3839","volume":"32","author":"D.E. Willard","year":"1985","unstructured":"Willard, D.E., Lueker, G.S.: Adding range restriction capability to dynamic data structures. J. ACM\u00a032(3), 597\u2013617 (1985)","journal-title":"J. ACM"},{"key":"40_CR21","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Space-time tradeoff for answering range queries (extended abstract). In: 14th Annual Symp. on Theory of Computing (STOC), pp. 128\u2013136 (1982)","DOI":"10.1145\/800070.802185"},{"issue":"2","key":"40_CR22","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A.C.-C. Yao","year":"1985","unstructured":"Yao, A.C.-C.: On the Complexity of Maintaining Partial Sums. SIAM J. Comput.\u00a014(2), 277\u2013288 (1985)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T07:18:22Z","timestamp":1589959102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}