{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T23:37:08Z","timestamp":1722987428311},"reference-count":29,"publisher":"Elsevier BV","issue":"24","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2015,5,27]],"date-time":"2015-05-27T00:00:00Z","timestamp":1432684800000},"content-version":"vor","delay-in-days":1487,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2011,5]]},"DOI":"10.1016\/j.tcs.2010.05.003","type":"journal-article","created":{"date-parts":[[2010,5,12]],"date-time":"2010-05-12T14:52:12Z","timestamp":1273675932000},"page":"2588-2601","source":"Crossref","is-referenced-by-count":30,"title":["Towards optimal range medians"],"prefix":"10.1016","volume":"412","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[]},{"given":"Beat","family":"Gfeller","sequence":"additional","affiliation":[]},{"given":"Allan Gr\u00f8nlund","family":"J\u00f8rgensen","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2010.05.003_br000005","series-title":"Proc. 39th Annual Symposium on Foundations of Computer Science","first-page":"534","article-title":"Marked ancestor problems","author":"Alstrup","year":"1998"},{"issue":"6","key":"10.1016\/j.tcs.2010.05.003_br000010","doi-asserted-by":"crossref","first-page":"1488","DOI":"10.1137\/S009753970240481X","article-title":"Optimal external memory interval management","volume":"32","author":"Arge","year":"2003","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"10.1016\/j.tcs.2010.05.003_br000015","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1006\/jcss.2002.1822","article-title":"Optimal bounds for the predecessor problem and related problems","volume":"65","author":"Beame","year":"2002","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/j.tcs.2010.05.003_br000020","doi-asserted-by":"crossref","unstructured":"Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan, Linear time bounds for median computations, in: 4th Annual Symp. on Theory of Computing, STOC, 1972, pp.\u00a0119\u2013124.","DOI":"10.1145\/800152.804904"},{"key":"10.1016\/j.tcs.2010.05.003_br000025","series-title":"Proc. 20th Annual International Symposium on Algorithms and Computation","article-title":"Data structures for range median queries","volume":"vol. 5878","author":"Brodal","year":"2009"},{"key":"10.1016\/j.tcs.2010.05.003_br000030","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01840440","article-title":"Fractional cascading: I. A data structuring technique","volume":"1","author":"Chazelle","year":"1986","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2010.05.003_br000035","unstructured":"David R. Clark, Compact Pat Trees. Ph.D. Thesis, University of Waterloo, 1988."},{"key":"10.1016\/j.tcs.2010.05.003_br000040","first-page":"281","article-title":"Fast 8-bit median filtering based on separability","volume":"5","author":"Cline","year":"2007","journal-title":"IEEE International Conference on Image Processing (ICIP)"},{"key":"10.1016\/j.tcs.2010.05.003_br000045","series-title":"Computational Geometry Algorithms and Applications","author":"de Berg","year":"2000"},{"key":"10.1016\/j.tcs.2010.05.003_br000050","series-title":"Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing","first-page":"135","article-title":"Scaling and related techniques for geometry problems","author":"Gabow","year":"1984"},{"key":"10.1016\/j.tcs.2010.05.003_br000055","series-title":"36th International Colloquium on Automata, Languages and Programming","first-page":"475","article-title":"Towards optimal range medians","volume":"vol. 5555","author":"Gfeller","year":"2009"},{"issue":"5","key":"10.1016\/j.tcs.2010.05.003_br000060","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1109\/34.211471","article-title":"Computing 2-d min, median, and max filters","volume":"15","author":"Gil","year":"1993","journal-title":"Pattern Analysis and Machine Intelligence, IEEE Transactions on"},{"key":"10.1016\/j.tcs.2010.05.003_br000065","series-title":"16th Annual European Symp. on Algorithms","first-page":"503","article-title":"Range medians","volume":"vol. 5193","author":"Har-Peled","year":"2008"},{"key":"10.1016\/j.tcs.2010.05.003_br000070","series-title":"19th International Symp. on Algorithms and Computation","first-page":"558","article-title":"Space-efficient and fast algorithms for multidimensional dominance reporting and counting","volume":"vol. 3341","author":"J\u00e1J\u00e1","year":"2004"},{"issue":"5","key":"10.1016\/j.tcs.2010.05.003_br000075","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1137\/0217055","article-title":"Deferred data structuring","volume":"17","author":"Karp","year":"1988","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"10.1016\/j.tcs.2010.05.003_br000080","first-page":"1","article-title":"Range mode and range median queries on lists and trees","volume":"12","author":"Krizanc","year":"2005","journal-title":"Nordic Journal of Computing"},{"issue":"4","key":"10.1016\/j.tcs.2010.05.003_br000085","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","article-title":"Orthogonal range searching in linear and almost-linear space","volume":"42","author":"Nekrich","year":"2009","journal-title":"Computational Geometry"},{"key":"10.1016\/j.tcs.2010.05.003_br000090","series-title":"4th Annual Symposium on Theory of Computing","first-page":"137","article-title":"Binary search trees of bounded balance","author":"Nievergelt","year":"1972"},{"key":"10.1016\/j.tcs.2010.05.003_br000095","doi-asserted-by":"crossref","unstructured":"Daisuke Okanohara, Kunihiko Sadakane, Practical entropy-compressed rank\/select dictionary. The Computing Research Repository, CoRR, abs\/cs\/0610001, 2006.","DOI":"10.1137\/1.9781611972870.6"},{"key":"10.1016\/j.tcs.2010.05.003_br000100","series-title":"Proc. 39th ACM Symposium on Theory of Computing","first-page":"40","article-title":"Lower bounds for 2-dimensional range counting","author":"Pa\u02c7tra\u015fcu","year":"2007"},{"key":"10.1016\/j.tcs.2010.05.003_br000105","doi-asserted-by":"crossref","unstructured":"Mihai Pa\u02c7tra\u015fcu, (Data) structures, in: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp.\u00a0434\u2013443.","DOI":"10.1109\/FOCS.2008.69"},{"key":"10.1016\/j.tcs.2010.05.003_br000110","doi-asserted-by":"crossref","unstructured":"Holger Petersen, Improved bounds for range mode and range median queries, in: 34th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM, 2008, pp.\u00a0418\u2013423.","DOI":"10.1007\/978-3-540-77566-9_36"},{"issue":"4","key":"10.1016\/j.tcs.2010.05.003_br000115","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.ipl.2008.10.007","article-title":"Range mode and range median queries in constant time and sub-quadratic space","volume":"109","author":"Petersen","year":"2009","journal-title":"Information Processing Letters"},{"issue":"9","key":"10.1016\/j.tcs.2010.05.003_br000120","doi-asserted-by":"crossref","first-page":"2389","DOI":"10.1109\/TIP.2007.902329","article-title":"Median filtering in constant time","volume":"16","author":"Perreault","year":"2007","journal-title":"IEEE Transactions on Image Processing"},{"key":"10.1016\/j.tcs.2010.05.003_br000125","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","article-title":"Design and implementation of an efficient priority queue","volume":"10","author":"van Emde Boas","year":"1977","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"10.1016\/j.tcs.2010.05.003_br000130","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0743-7315(91)90022-2","article-title":"Merging multiple lists on hierarchical-memory multiprocessors","volume":"12","author":"Varman","year":"1991","journal-title":"Jorunal of Parallel and Distributed Computing"},{"issue":"3","key":"10.1016\/j.tcs.2010.05.003_br000135","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1145\/1141911.1141918","article-title":"Fast median and bilateral filtering","volume":"25","author":"Weiss","year":"2006","journal-title":"ACM Transactions on Graphics"},{"key":"10.1016\/j.tcs.2010.05.003_br000140","unstructured":"Andrew Chi-Chih Yao, Space\u2013time tradeoff for answering range queries (extended abstract), in: 14th Annual Symposium on Theory of Computing, STOC, 1982, pp.\u00a0128\u2013136."},{"issue":"2","key":"10.1016\/j.tcs.2010.05.003_br000145","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0214022","article-title":"On the complexity of maintaining partial sums","volume":"14","author":"Yao","year":"1985","journal-title":"SIAM Journal on Computing"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397510002732?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397510002732?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T14:56:45Z","timestamp":1591282605000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397510002732"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":29,"journal-issue":{"issue":"24","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["S0304397510002732"],"URL":"http:\/\/dx.doi.org\/10.1016\/j.tcs.2010.05.003","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2011,5]]}}}
