{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T23:46:04Z","timestamp":1648511164851},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,6,27]],"date-time":"2020-06-27T00:00:00Z","timestamp":1593216000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,27]],"date-time":"2020-06-27T00:00:00Z","timestamp":1593216000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","award":["MISU F 6001 1"],"award-info":[{"award-number":["MISU F 6001 1"]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1533564"],"award-info":[{"award-number":["CCF-1533564"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s00224-020-09991-8","type":"journal-article","created":{"date-parts":[[2020,6,27]],"date-time":"2020-06-27T08:03:01Z","timestamp":1593244981000},"page":"541-558","update-policy":"https:\/\/linproxy.fan.workers.dev:443\/http\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Belga B-Trees"],"prefix":"10.1007","volume":"65","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[]},{"given":"Grigorios","family":"Koumoutsos","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,6,27]]},"reference":[{"key":"9991_CR1","first-page":"263","volume":"146","author":"GM Adelson-Velski\u0131\u0306","year":"1962","unstructured":"Adelson-Velski\u0131\u0306, G.M., Landis, E.M.: An algorithm for organization of information. Dokl. Akad. Nauk SSSR 146, 263\u2013266 (1962)","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"9","key":"9991_CR2","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1145\/48529.48535","journal-title":"Commun. ACM"},{"issue":"2","key":"9991_CR3","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2007.03.002","volume":"382","author":"M Badoiu","year":"2007","unstructured":"Badoiu, M., Cole, R., Demaine, E.D., Iacono, J.: A unified access bound on comparison-based dynamic dictionaries. Theor. Comput. Sci. 382(2), 86\u201396 (2007). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1016\/j.tcs.2007.03.002","journal-title":"Theor. Comput. Sci."},{"key":"9991_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.M.: Organization and maintenance of large ordered indices. Acta Inf. 1, 173\u2013189 (1972). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1016\/j.tcs.2007.03.002","journal-title":"Acta Inf."},{"key":"9991_CR5","unstructured":"Bose, P., Dou\u00efeb, K., Langerman, S.: Dynamic optimality for skip lists and b-trees. In: Symposium on Discrete Algorithms, SODA. https:\/\/linproxy.fan.workers.dev:443\/http\/dl.acm.org\/citation.cfm?id=1347082.1347203, pp 1106\u20131114 (2008)"},{"issue":"4","key":"9991_CR6","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1007\/s00453-016-0224-x","volume":"76","author":"P Bose","year":"2016","unstructured":"Bose, P., Dou\u00efeb, K., Iacono, J., Langerman, S.: The power and limitations of static binary search trees with lazy finger. Algorithmica 76(4), 1264\u20131275 (2016). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/s00453-016-0224-x","journal-title":"Algorithmica"},{"key":"9991_CR7","doi-asserted-by":"publisher","unstructured":"Bose, P., Howat, J., Morin, P.: A history of distribution-sensitive data structures. In: Brodnik et al. [8], 133\u2013149. https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/978-3-642-40273-9_10","DOI":"10.1007\/978-3-642-40273-9_10"},{"key":"9991_CR8","doi-asserted-by":"publisher","unstructured":"Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.): Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, Lecture Notes in Computer Science, vol. 8066. Springer, Berlin (2013). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/978-3-642-40273-9","DOI":"10.1007\/978-3-642-40273-9"},{"key":"9991_CR9","unstructured":"Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K., Saranurak, T.: The landscape of bounds for binary search trees. CoRR arXiv:1603.04892 (2016)"},{"key":"9991_CR10","doi-asserted-by":"publisher","unstructured":"Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K., Saranurak, T.: Multi-finger binary search trees. In: 29th International Symposium on Algorithms and Computation, ISAAC. https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.55, pp 55:1\u201355:26 (2018)","DOI":"10.4230\/LIPIcs.ISAAC.2018.55"},{"issue":"1","key":"9991_CR11","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1137\/S009753979732699X","volume":"30","author":"R Cole","year":"2000","unstructured":"Cole, R.: On the dynamic finger conjecture for splay trees. Part II: the proof. SIAM J. Comput. 30(1), 44\u201385 (2000). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1137\/S009753979732699X","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9991_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539797326988","volume":"30","author":"R Cole","year":"2000","unstructured":"Cole, R., Mishra, B., Schmidt, J.P., Siegel, A.: On the dynamic finger conjecture for splay trees. Part I: splay sorting log n-block sequences. SIAM J. Comput. 30(1), 1\u201343 (2000). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1137\/S0097539797326988","journal-title":"SIAM J. Comput."},{"key":"9991_CR13","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009). https:\/\/linproxy.fan.workers.dev:443\/http\/mitpress.mit.edu\/books\/introduction-algorithms","edition":"3rd edn."},{"issue":"1","key":"9991_CR14","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/S0097539705447347","volume":"37","author":"ED Demaine","year":"2007","unstructured":"Demaine, E.D., Harmon, D., Iacono, J., Patrascu, M.: Dynamic optimality\u2014almost. SIAM J. Comput. 37(1), 240\u2013251 (2007). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1137\/S0097539705447347","journal-title":"SIAM J. Comput."},{"key":"9991_CR15","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Harmon, D., Iacono, J., Kane, D.M., Patrascu, M.: The geometry of binary search trees. In: Symposium on Discrete Algorithms, SODA. https:\/\/linproxy.fan.workers.dev:443\/http\/dl.acm.org\/citation.cfm?id=1496770.1496825, pp 496\u2013505 (2009)","DOI":"10.1137\/1.9781611973068.55"},{"key":"9991_CR16","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., Iacono, J., Langerman, S., \u00d6zkan, \u00d6.: Combining binary search trees. In: ICALP 2013, Part I. https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/978-3-642-39206-1_33, pp 388\u2013399 (2013)","DOI":"10.1007\/978-3-642-39206-1_33"},{"issue":"2","key":"9991_CR17","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00453-013-9856-2","volume":"72","author":"ED Demaine","year":"2015","unstructured":"Demaine, E.D., Iacono, J., Langerman, S.: Worst-case optimal tree layout in external memory. Algorithmica 72(2), 369\u2013378 (2015). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/s00453-013-9856-2","journal-title":"Algorithmica"},{"issue":"4","key":"9991_CR18","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00236-013-0180-8","volume":"50","author":"A Elmasry","year":"2013","unstructured":"Elmasry, A., Farzan, A., Iacono, J.: On the hierarchy of distribution-sensitive properties for data structures. Acta Inf. 50(4), 289\u2013295 (2013). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/s00236-013-0180-8","journal-title":"Acta Inf."},{"key":"9991_CR19","doi-asserted-by":"publisher","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: Foundations of Computer Science (FOCS). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1109\/SFCS.1978.3, pp 8\u201321 (1978)","DOI":"10.1109\/SFCS.1978.3"},{"key":"9991_CR20","unstructured":"Howat, J., Iacono, J., Morin, P.: The fresh-finger property. CoRR arXiv:1302.6914 (2013)"},{"key":"9991_CR21","unstructured":"Iacono, J.: Alternatives to splay trees with o(log n) worst-case access times. In: Symposium on Discrete Algorithms (SODA). https:\/\/linproxy.fan.workers.dev:443\/http\/dl.acm.org\/citation.cfm?id=365411.365522, pp 516\u2013522 (2001)"},{"key":"9991_CR22","unstructured":"Iacono, J.: Distribution sensitive data structures. Ph.D. thesis, Ph.D. Thesis. Rutgers The State University of New Jersey (2001)"},{"key":"9991_CR23","doi-asserted-by":"publisher","unstructured":"Iacono, J.: In pursuit of the dynamic optimality conjecture. In: Brodnik et al. [8], 236\u2013250. https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/978-3-642-40273-9_16","DOI":"10.1007\/978-3-642-40273-9_16"},{"key":"9991_CR24","doi-asserted-by":"publisher","unstructured":"Iacono, J., Langerman, S.: Weighted dynamic finger in binary search trees. In: Symposium on Discrete Algorithms, SODA. https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1137\/1.9781611974331.ch49, pp 672\u2013691 (2016)","DOI":"10.1137\/1.9781611974331.ch49"},{"key":"9991_CR25","unstructured":"Lucas, J.M.: Canonical forms for competitive binary search tree algorithms. Tech. Rep. DCS-TR-250 Rutgers University (1988)"},{"issue":"1","key":"9991_CR26","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1006\/jagm.1995.1026","volume":"19","author":"M Sherk","year":"1995","unstructured":"Sherk, M.: Self-adjusting k-ary search trees. J. Algorithms 19(1), 25\u201344 (1995). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1006\/jagm.1995.1026","journal-title":"J. Algorithms"},{"issue":"2","key":"9991_CR27","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1145\/2786.2793","journal-title":"Commun. ACM"},{"issue":"3","key":"9991_CR28","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652\u2013686 (1985). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1145\/3828.3835","journal-title":"J. ACM"},{"issue":"4","key":"9991_CR29","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF02579253","volume":"5","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Sequential access in play trees takes linear time. Combinatorica 5 (4), 367\u2013378 (1985). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/BF02579253","journal-title":"Combinatorica"},{"key":"9991_CR30","doi-asserted-by":"crossref","unstructured":"Wang, C.C., Derryberry, J., Sleator, D.D.: O(log log n)-competitive dynamic binary search trees. In: Symposium on Discrete Algorithms, SODA. https:\/\/linproxy.fan.workers.dev:443\/http\/dl.acm.org\/citation.cfm?id=1109557.1109600, pp 374\u2013383 (2006)","DOI":"10.1145\/1109557.1109600"},{"issue":"1","key":"9991_CR31","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/0218004","volume":"18","author":"RE Wilber","year":"1989","unstructured":"Wilber, R.E.: Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. 18(1), 56\u201367 (1989). https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1137\/0218004","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09991-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/link.springer.com\/article\/10.1007\/s00224-020-09991-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09991-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T23:17:32Z","timestamp":1624749452000},"score":1,"resource":{"primary":{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/link.springer.com\/10.1007\/s00224-020-09991-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,27]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["9991"],"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/s00224-020-09991-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,27]]},"assertion":[{"value":"27 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}