{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T02:45:13Z","timestamp":1725763513653},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450297"},{"type":"electronic","value":"9783642450303"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_38","type":"book-chapter","created":{"date-parts":[[2013,12,11]],"date-time":"2013-12-11T21:32:52Z","timestamp":1386797572000},"page":"405-412","source":"Crossref","is-referenced-by-count":3,"title":["Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers"],"prefix":"10.1007","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"38_CR1","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0220017","volume":"20","author":"P. Beame","year":"1991","unstructured":"Beame, P.: A general sequential time-space tradeoff for finding unique elements. SIAM Journal on Computing\u00a020(2), 270\u2013277 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR2","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., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences\u00a07, 448\u2013461 (1973)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR3","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A. Borodin","year":"1982","unstructured":"Borodin, A., Cook, S.A.: A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing\u00a011, 287\u2013297 (1982)","journal-title":"SIAM Journal on Computing"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Boyer, R.S., Moore, J.S.: MJRTY - A fast majority vote algorithm. In: Boyer, R.S. (ed.) Automated Reasoning: Essays in Honor of Woody Bledsoe. Automated Reasoning Series, pp. 105\u2013117. Kluwer (1991)","DOI":"10.1007\/978-94-011-3488-0_5"},{"key":"38_CR5","unstructured":"Chakrabarti, A., Jayram, T.S., P\u01cetra\u015fcu, M.: Tight lower bound for selection in randomly ordered streams. In: Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 720\u2013729 (2008)"},{"issue":"2","key":"38_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/1721837.1721842","volume":"6","author":"T.M. Chan","year":"2010","unstructured":"Chan, T.M.: Comparison-based time-space lower bounds for selection. ACM Transactions on Algorithms\u00a06(2), 26 (2010)","journal-title":"ACM Transactions on Algorithms"},{"key":"38_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/3-540-51542-9_5","volume-title":"Algorithms and Data Structures","author":"P.F. Dietz","year":"1989","unstructured":"Dietz, P.F.: Optimal algorithms for list indexing and subset rank. In: Dehne, F., Santoro, N., Sack, J.-R. (eds.) WADS 1989. LNCS, vol.\u00a0382, pp. 39\u201346. Springer, Heidelberg (1989)"},{"key":"38_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-642-38768-5_15","volume-title":"Computing and Combinatorics","author":"A. Elmasry","year":"2013","unstructured":"Elmasry, A., Juhl, D.D., Katajainen, J., Satti, S.R.: Selection from read-only memory with limited work space. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol.\u00a07936, pp. 147\u2013157. Springer, Heidelberg (2013)"},{"issue":"1","key":"38_CR9","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0022-0000(87)90002-X","volume":"34","author":"G. Frederickson","year":"1987","unstructured":"Frederickson, G.: Upper bounds for time-space trade-offs in sorting and selection. Journal of Computer and System Sciences\u00a034(1), 19\u201326 (1987)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences\u00a047, 424\u2013436 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR11","doi-asserted-by":"crossref","unstructured":"Greenwald, M., Khanna, S.: Space-efficient online computation of quantile summaries. In: Proceedings of ACM SIGMOD, pp. 58\u201366 (2001)","DOI":"10.1145\/376284.375670"},{"issue":"2","key":"38_CR12","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1145\/276305.276342","volume":"27","author":"G.S. Manku","year":"1998","unstructured":"Manku, G.S., Rajagopalan, S., Lindsay, B.G.: Approximate medians and other quantiles in one pass with limited memory. Proceedings of ACM SIGMOD\u00a027(2), 426\u2013435 (1998)","journal-title":"Proceedings of ACM SIGMOD"},{"key":"38_CR13","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"J.I. Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.: Selection and sorting with limited storage. Theoretical Computer Science\u00a012, 315\u2013323 (1980)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"38_CR14","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(95)00225-1","volume":"165","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I., Raman, V.: Selection from read-only memory and sorting with optimum data movement. Theoretical Computer Science\u00a0165(2), 311\u2013323 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"38_CR15","first-page":"162","volume":"6","author":"V. Raman","year":"1999","unstructured":"Raman, V., Ramnath, S.: Improved upper bounds for time-space tradeoffs for selection. Nordic Journal of Computing\u00a06(2), 162\u2013180 (1999)","journal-title":"Nordic Journal of Computing"},{"key":"38_CR16","doi-asserted-by":"crossref","unstructured":"Shrivastava, N., Buragohain, C., Agrawal, D., Suri, S.: Medians and beyond: new aggregation techniques for sensor networks. In: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, pp. 239\u2013249 (2004)","DOI":"10.1145\/1031495.1031524"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T06:50:01Z","timestamp":1558767001000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}