{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:37:48Z","timestamp":1743039468408,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540877431"},{"type":"electronic","value":"9783540877448"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87744-8_42","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T09:20:52Z","timestamp":1220088052000},"page":"503-514","source":"Crossref","is-referenced-by-count":6,"title":["Range Medians"],"prefix":"10.1007","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"42_CR1","first-page":"154","volume":"12","author":"T. Altman","year":"1989","unstructured":"Altman, T., Yoshihide, I.: Roughly sorting: Sequential and parallel approach. Journal of Information Processing\u00a012(2), 154\u2013158 (1989)","journal-title":"Journal of Information Processing"},{"issue":"1","key":"42_CR2","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. Theo. Comp. Sci.\u00a0321(1), 5\u201312 (2004)","journal-title":"Theo. Comp. Sci."},{"issue":"4","key":"42_CR3","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Sys. Sci.\u00a07(4), 448\u2013461 (1973)","journal-title":"J. Comput. Sys. Sci."},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"Bent, S.W., John, J.W.: Finding the median requires 2n comparisons. In: Proc. 17th Annu. ACM Sympos. Theory Comput., pp. 213\u2013216 (1985)","DOI":"10.1145\/22145.22169"},{"key":"42_CR5","doi-asserted-by":"crossref","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Approximate range mode and range median queries. In: Proc. 22nd Internat. Sympos. Theoret. Asp. Comp. Sci., pp. 377\u2013388 (2005)","DOI":"10.1007\/978-3-540-31856-9_31"},{"issue":"5","key":"42_CR6","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1137\/S0097539795288611","volume":"28","author":"D. Dor","year":"1999","unstructured":"Dor, D., Zwick, U.: Selecting the median. SIAM J. Comput.\u00a028(5), 1722\u20131758 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"42_CR7","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/S0895480199353895","volume":"14","author":"D. Dor","year":"2001","unstructured":"Dor, D., Zwick, U.: Median selection requires (2\u2009+\u2009\u03b5)n comparisons. SIAM J. Discret. Math.\u00a014(3), 312\u2013325 (2001)","journal-title":"SIAM J. Discret. Math."},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Greenwald, M., Khanna, S.: Space-efficient online computation of quantile summaries. In: Proc. 2001 ACM SIGOD Conf. Mang. Data, pp. 58\u201366 (2001)","DOI":"10.1145\/375663.375670"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Greenwald, M., Khanna, S.: Power-conserving computation of order-statistics over sensor networks. In: Proc. 23rd ACM Sympos. Principles Database Syst., pp. 275\u2013285 (2004)","DOI":"10.1145\/1055558.1055597"},{"issue":"1","key":"42_CR10","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.\u00a012(1), 1\u201317 (2005)","journal-title":"Nordic J. Comput."},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Korn, F., Muthukrishnan, S., Zhu, Y.: Checks and balances: Monitoring data quality problems in network traffic databases. In: Proc. 29th Intl. Conf. Very Large Data Bases, pp. 536\u2013547 (2003)","DOI":"10.1016\/B978-012722442-8\/50054-9"},{"key":"42_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"issue":"2","key":"42_CR13","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/S0022-0000(76)80029-3","volume":"13","author":"A. Sch\u00f6nhage","year":"1976","unstructured":"Sch\u00f6nhage, A., Paterson, M., Pippenger, N.: Finding the median. J. Comput. Sys. Sci.\u00a013(2), 184\u2013199 (1976)","journal-title":"J. Comput. Sys. Sci."},{"key":"42_CR14","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Space-time tradeoff for answering range queries. In: Proc. 14th Annu. ACM Sympos. Theory Comput., pp. 128\u2013136 (1982)","DOI":"10.1145\/800070.802185"},{"issue":"2","key":"42_CR15","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A.C. Yao","year":"1985","unstructured":"Yao, A.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","Algorithms - ESA 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87744-8_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T05:18:11Z","timestamp":1715059091000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87744-8_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540877431","9783540877448"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87744-8_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}