{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:33Z","timestamp":1740109293289,"version":"3.37.3"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,5]],"date-time":"2019-07-05T00:00:00Z","timestamp":1562284800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,5]],"date-time":"2019-07-05T00:00:00Z","timestamp":1562284800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Research Grants Council, Hong Kong, China","award":["16200317"],"award-info":[{"award-number":["16200317"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00453-019-00604-6","type":"journal-article","created":{"date-parts":[[2019,7,5]],"date-time":"2019-07-05T10:03:02Z","timestamp":1562320982000},"page":"88-106","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Extensions of Self-Improving Sorters"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3557-9935","authenticated-orcid":false,"given":"Siu-Wing","family":"Cheng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lie","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,5]]},"reference":[{"issue":"2","key":"604_CR1","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/090766437","volume":"40","author":"N Ailon","year":"2011","unstructured":"Ailon, N., Chazelle, B., Clarkson, K.L., Liu, D., Mulzer, W., Seshadhir, C.: Self-improving algorithms. SIAM J. Comput. 40(2), 350\u2013375 (2011)","journal-title":"SIAM J. Comput."},{"key":"604_CR2","unstructured":"Cheng, S.-W., Yan, L.: Extensions of self-improving sorters. In: Proceedings of the 29th International Symposium on Algorithms and Computation, pp. 63:1\u201363:12 (2018)"},{"issue":"2","key":"604_CR3","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1137\/12089702X","volume":"43","author":"KL Clarkson","year":"2014","unstructured":"Clarkson, K.L., Mulzer, W., Seshadhri, C.: Self-improving algorithms for coordinatewise maxima and convex hulls. SIAM J. Comput. 43(2), 617\u2013653 (2014)","journal-title":"SIAM J. Comput."},{"key":"604_CR4","volume-title":"Elements of Information Theory","author":"TM Cover","year":"2006","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley, New York (2006)","edition":"2"},{"key":"604_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"JR Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci. 38, 86\u2013124 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"604_CR6","doi-asserted-by":"crossref","unstructured":"Fredman, M.L.: Two applications of a probabilistic search technique: sorting $$X+Y$$ and building balanced search trees. In: Proceedings of the 7th Symposium on Theory of Computing, pp. 240\u2013244 (1975)","DOI":"10.1145\/800116.803774"},{"key":"604_CR7","first-page":"5:1","volume-title":"Algorithms and Theory of Computation Handbook","author":"GF Italiano","year":"2009","unstructured":"Italiano, G.F., Raman, R.: Topics in data structures. In: Atallah, M.J., Blanton, M. (eds.) Algorithms and Theory of Computation Handbook, 2nd edn, pp. 5:1\u20135:29. Chapman & Hall, London (2009)","edition":"2"},{"key":"604_CR8","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF00264563","volume":"5","author":"K Mehlhorn","year":"1975","unstructured":"Mehlhorn, K.: Nearly optimal binary search trees. Acta Inf. 5, 287\u2013295 (1975)","journal-title":"Acta Inf."},{"key":"604_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804120","volume-title":"Computational Geometry in C","author":"Joseph O\u2019Rourke","year":"1998","unstructured":"O\u2019Rourke, Joseph: Computational Geometry in C, 2nd edn. Cambridge University Press, Cambridge (1998)","edition":"2"},{"key":"604_CR10","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P van Emde Boas","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99\u2013127 (1977)","journal-title":"Math. Syst. Theory"},{"key":"604_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8608-5","volume-title":"A First Course in Information Theory","author":"RW Yeung","year":"2002","unstructured":"Yeung, R.W.: A First Course in Information Theory. Kluwer Academic, Dordrecht (2002)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00604-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00604-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00604-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,3]],"date-time":"2020-07-03T23:09:03Z","timestamp":1593817743000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00604-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,5]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["604"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00604-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,7,5]]},"assertion":[{"value":"29 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}