{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:57:48Z","timestamp":1742925468458,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031389054"},{"type":"electronic","value":"9783031389061"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-38906-1_43","type":"book-chapter","created":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:05:14Z","timestamp":1690473914000},"page":"644-659","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Space-Efficient Functional Offline-Partially-Persistent Trees with Applications to\u00a0Planar Point Location"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9054-915X","authenticated-orcid":false,"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3989-123X","authenticated-orcid":false,"given":"Casper Moldrup","family":"Rysgaard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9915-7061","authenticated-orcid":false,"given":"Jens Kristian Refsgaard","family":"Schou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9903-4651","authenticated-orcid":false,"given":"Rolf","family":"Svenning","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,28]]},"reference":[{"key":"43_CR1","first-page":"1259","volume":"3","author":"GM Adel\u2019son-Vel-skii","year":"1962","unstructured":"Adel\u2019son-Vel-skii, G.M., Landis, E.M.: An algorithm for the organization of information. Soviet Math. Doklady 3, 1259\u20131263 (1962)","journal-title":"Soviet Math. Doklady"},{"issue":"5","key":"43_CR2","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.ipl.2015.12.009","volume":"116","author":"M Amani","year":"2016","unstructured":"Amani, M., Lai, K.A., Tarjan, R.E.: Amortized rotation cost in AVL trees. Inf. Process. Lett. 116(5), 327\u2013330 (2016). https:\/\/doi.org\/10.1016\/j.ipl.2015.12.009","journal-title":"Inf. Process. Lett."},{"key":"43_CR3","doi-asserted-by":"publisher","unstructured":"Aragon, C.R., Seidel, R.: Randomized search trees. In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October\u20131 November 1989, pp. 540\u2013545. IEEE Computer Society (1989). https:\/\/doi.org\/10.1109\/SFCS.1989.63531","DOI":"10.1109\/SFCS.1989.63531"},{"issue":"8","key":"43_CR4","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1145\/359576.359579","volume":"21","author":"J Backus","year":"1978","unstructured":"Backus, J.: Can programming be liberated from the von Neumann style? A functional style and its algebra of programs. Commun. ACM 21(8), 613\u2013641 (1978). https:\/\/doi.org\/10.1145\/359576.359579","journal-title":"Commun. ACM"},{"key":"43_CR5","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BF00289509","volume":"1","author":"R Bayer","year":"1972","unstructured":"Bayer, R.: Symmetric binary B-trees: data structure and maintenance algorithms. Acta Informatica 1, 290\u2013306 (1972). https:\/\/doi.org\/10.1007\/BF00289509","journal-title":"Acta Informatica"},{"issue":"6","key":"43_CR6","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1017\/S095679680000201X","volume":"6","author":"GS Brodal","year":"1996","unstructured":"Brodal, G.S., Okasaki, C.: Optimal purely functional priority queues. J. Funct. Program. 6(6), 839\u2013857 (1996). https:\/\/doi.org\/10.1017\/S095679680000201X","journal-title":"J. Funct. Program."},{"issue":"3","key":"43_CR7","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1006\/jagm.1995.1020","volume":"18","author":"AL Buchsbaum","year":"1995","unstructured":"Buchsbaum, A.L., Tarjan, R.E.: Confluently persistent deques via data-structural bootstrapping. J. Algorithms 18(3), 513\u2013547 (1995). https:\/\/doi.org\/10.1006\/jagm.1995.1020","journal-title":"J. Algorithms"},{"issue":"2","key":"43_CR8","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/0196-6774(86)90004-0","volume":"7","author":"R Cole","year":"1986","unstructured":"Cole, R.: Searching and storing similar lists. J. Algorithms 7(2), 202\u2013220 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90004-0","journal-title":"J. Algorithms"},{"key":"43_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-540-69903-3_16","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Langerman, S., Price, E.: Confluently persistent tries for efficient version control. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol. 5124, pp. 160\u2013172. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-69903-3_16"},{"issue":"2","key":"43_CR10","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D Dobkin","year":"1976","unstructured":"Dobkin, D., Lipton, R.J.: Multidimensional searching problems. SIAM J. Comput. 5(2), 181\u2013186 (1976). https:\/\/doi.org\/10.1137\/0205015","journal-title":"SIAM J. Comput."},{"key":"43_CR11","doi-asserted-by":"publisher","unstructured":"Dobkin, D.P., Munro, J.I.: Efficient uses of the past. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science, SFCS 1980, pp. 200\u2013206. IEEE Computer Society, USA (1980). https:\/\/doi.org\/10.1109\/SFCS.1980.18","DOI":"10.1109\/SFCS.1980.18"},{"key":"43_CR12","doi-asserted-by":"publisher","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC 1986, pp. 109\u2013121. Association for Computing Machinery, New York (1986). https:\/\/doi.org\/10.1145\/12130.12142","DOI":"10.1145\/12130.12142"},{"issue":"2","key":"43_CR13","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317\u2013340 (1986). https:\/\/doi.org\/10.1137\/0215023","journal-title":"SIAM J. Comput."},{"key":"43_CR14","doi-asserted-by":"publisher","unstructured":"Hughes, J.: Why functional programming matters. In: Turner, D.A. (ed.) Research Topics in Functional Programming. The UT Year of Programming Series, pp. 17\u201342. Addison-Wesley (1990). https:\/\/doi.org\/10.1093\/comjnl\/32.2.98","DOI":"10.1093\/comjnl\/32.2.98"},{"issue":"11","key":"43_CR15","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/368996.369025","volume":"5","author":"AB Kahn","year":"1962","unstructured":"Kahn, A.B.: Topological sorting of large networks. Commun. ACM 5(11), 558\u2013562 (1962). https:\/\/doi.org\/10.1145\/368996.369025","journal-title":"Commun. ACM"},{"key":"43_CR16","doi-asserted-by":"publisher","unstructured":"Kaplan, H., Tarjan, R.E.: Persistent lists with catenation via recursive slow-down. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 93\u2013102 (1995). https:\/\/doi.org\/10.1145\/225058.225090","DOI":"10.1145\/225058.225090"},{"issue":"1","key":"43_CR17","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM J. Comput. 12(1), 28\u201335 (1983). https:\/\/doi.org\/10.1137\/0212002","journal-title":"SIAM J. Comput."},{"key":"43_CR18","doi-asserted-by":"publisher","unstructured":"Okasaki, C.: Purely functional random-access lists. In: Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture, FPCA 1995, pp. 86\u201395. Association for Computing Machinery, New York (1995). https:\/\/doi.org\/10.1145\/224164.224187","DOI":"10.1145\/224164.224187"},{"key":"43_CR19","volume-title":"Purely Functional Data Structures","author":"C Okasaki","year":"1999","unstructured":"Okasaki, C.: Purely Functional Data Structures. Cambridge University Press, Cambridge (1999)"},{"issue":"4","key":"43_CR20","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1017\/s0956796899003494","volume":"9","author":"C Okasaki","year":"1999","unstructured":"Okasaki, C.: Red-black trees in a functional setting. J. Funct. Program. 9(4), 471\u2013477 (1999). https:\/\/doi.org\/10.1017\/s0956796899003494","journal-title":"J. Funct. Program."},{"key":"43_CR21","unstructured":"Overmars, M.H.: Searching in the past II: general transforms. Technical report. RUU (1981)"},{"key":"43_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014927","volume-title":"The Design of Dynamic Data Structures","author":"MH Overmars","year":"1983","unstructured":"Overmars, M.H.: The Design of Dynamic Data Structures. LNCS, vol. 156. Springer, Heidelberg (1983). https:\/\/doi.org\/10.1007\/BFb0014927"},{"key":"43_CR23","doi-asserted-by":"publisher","unstructured":"Pippenger, N.: Pure versus impure lisp. In: Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 1996, pp. 104\u2013109. Association for Computing Machinery, New York (1996). https:\/\/doi.org\/10.1145\/237721.237741","DOI":"10.1145\/237721.237741"},{"issue":"7","key":"43_CR24","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM 29(7), 669\u2013679 (1986). https:\/\/doi.org\/10.1145\/6138.6151","journal-title":"Commun. ACM"},{"key":"43_CR25","volume-title":"An Introduction to the Analysis of Algorithms","author":"R Sedgewick","year":"1996","unstructured":"Sedgewick, R., Flajolet, P.: An Introduction to the Analysis of Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston (1996)"},{"issue":"1","key":"43_CR26","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0925-7721(91)90012-4","volume":"1","author":"R Seidel","year":"1991","unstructured":"Seidel, R.: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. 1(1), 51\u201364 (1991). https:\/\/doi.org\/10.1016\/0925-7721(91)90012-4","journal-title":"Comput. Geom."},{"issue":"2","key":"43_CR27","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Amortized computational complexity. SIAM J. Algebraic Discret. Methods 6(2), 306\u2013318 (1985). https:\/\/doi.org\/10.1137\/0606031","journal-title":"SIAM J. Algebraic Discret. Methods"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-38906-1_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:09:39Z","timestamp":1690474179000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-38906-1_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031389054","9783031389061"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-38906-1_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"28 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Algorithms and Data Structures Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montreal, QC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}