Belga B-Trees
Part of the Lecture Notes in Computer Science book series (LNCS, volume 11532)
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129995 |
| _version_ | 1811079193064112128 |
|---|---|
| author | Demaine, Erik D Iacono, John Koumoutsos, Grigorios Langerman, Stefan |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D Iacono, John Koumoutsos, Grigorios Langerman, Stefan |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | Part of the Lecture Notes in Computer Science book series (LNCS, volume 11532) |
| first_indexed | 2024-09-23T11:11:20Z |
| format | Article |
| id | mit-1721.1/129995 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:11:20Z |
| publishDate | 2021 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1299952021-03-17T07:18:01Z Belga B-Trees Demaine, Erik D Iacono, John Koumoutsos, Grigorios Langerman, Stefan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Part of the Lecture Notes in Computer Science book series (LNCS, volume 11532) We revisit self-adjusting external memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distribution of queries. Our approach is analogous to undergoing efforts in the BST model, where Tango Trees (Demaine et al. 2007) were shown to be O(loglogN) -competitive with the runtime of the best offline binary search tree on every sequence of searches. Here we formalize the B-Tree model as a natural generalization of the BST model. We prove lower bounds for the B-Tree model, and introduce a B-Tree model data structure, the Belga B-tree, that executes any sequence of searches within a O(loglogN) factor of the best offline B-tree model algorithm, provided B= log[superscript O(1)]N. We also show how to transform any static BST into a static B-tree which is faster by a Θ(log B) factor; the transformation is randomized and we show that randomization is necessary to obtain any significant speedup. Belgian National Foundation for Scientific Research ( Grant MISU F 6001 1) National Science Foundation (U.S.) (Grant CCF-1533564) 2021-02-24T19:58:09Z 2021-02-24T19:58:09Z 2019-03 2020-12-07T19:38:18Z Article http://purl.org/eprint/type/ConferencePaper 0302-9743 https://hdl.handle.net/1721.1/129995 Demaine, Erik D. et al. “Belga B-Trees.” 14th International Computer Science Symposium, Lecture Notes in Computer Science, 11532, Springer, 2019, 93-105. © 2019 The Author(s) en 10.1007/978-3-030-19955-5_9 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing arXiv |
| spellingShingle | Demaine, Erik D Iacono, John Koumoutsos, Grigorios Langerman, Stefan Belga B-Trees |
| title | Belga B-Trees |
| title_full | Belga B-Trees |
| title_fullStr | Belga B-Trees |
| title_full_unstemmed | Belga B-Trees |
| title_short | Belga B-Trees |
| title_sort | belga b trees |
| url | https://hdl.handle.net/1721.1/129995 |
| work_keys_str_mv | AT demaineerikd belgabtrees AT iaconojohn belgabtrees AT koumoutsosgrigorios belgabtrees AT langermanstefan belgabtrees |