New Analytical Methods for Online Binary Search Trees
| dc.contributor | Aalto-yliopisto | fi |
| dc.contributor | Aalto University | en |
| dc.contributor.advisor | Chalermsook, Parinya, Asst. Prof., Aalto University, Department of Computer Science, Finland | |
| dc.contributor.author | Jiamjitrak, Wanchote Po | |
| dc.contributor.department | Tietotekniikan laitos | fi |
| dc.contributor.department | Department of Computer Science | en |
| dc.contributor.lab | Combinatorics of Efficient Computations | en |
| dc.contributor.school | Perustieteiden korkeakoulu | fi |
| dc.contributor.school | School of Science | en |
| dc.contributor.supervisor | Chalermsook, Parinya, Asst. Prof., Aalto University, Department of Computer Science, Finland | |
| dc.date.accessioned | 2023-05-16T09:00:05Z | |
| dc.date.available | 2023-05-16T09:00:05Z | |
| dc.date.defence | 2023-05-29 | |
| dc.date.issued | 2023 | |
| dc.description.abstract | This thesis aims to analyze the costs of various binary search tree (BST) algorithms. BST is one of the most fundamental data structures. The long-standing dynamic optimality conjecture states that there exists an online self-adjusting BST algorithm such that, starting with any initial tree, its access cost on any sequence X is O(OPT(X)+n) where OPT(X) is the cost of serving X on an offline optimal algorithm and n is the number of keys. Despite attempts from many groups of researchers, we believe that it is still far from being proven, primarily due to the lack of systematic techniques on the analytical side of algorithms. To address this, we explore the power of two analyzing methods in the context of binary search trees: potential functions and extremal combinatorics. In the first part, we focus on the potential function method, which is widely used but mysterious in how it works. We introduce new charging schemes based on inversion counting, a popular potential function for list updates that has not been used in a BST context. An inversion potential function is arguably the most natural potential function, as it captures the difference between the states of two different algorithms. We illustrate our techniques in the context of both list updates and BSTs: (1) systematically deriving many known list update results and (2) unifying, strengthening, and deriving new bounds for BSTs. In the second part, we explore and extend the use of extremal combinatorics in an amortized analysis of BSTs. The technique exploits the specific structures of the input of BSTs. This method encodes the execution log of BSTs in the form of a matrix and applies powerful theorems from forbidden matrix literature to upper-bound the cost. We propose an extra preprocessing step that decomposes the matrix into several simpler submatrices. We show the applications of the BST Greedy algorithm, one of the most promising candidates for being dynamically optimal, including deriving improved bounds for long-standing conjectures such as preorder traversal, postorder traversal, and path conjectures. | en |
| dc.format.extent | 112 | |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.isbn | 978-952-64-1283-2 (electronic) | |
| dc.identifier.isbn | 978-952-64-1282-5 (printed) | |
| dc.identifier.issn | 1799-4942 (electronic) | |
| dc.identifier.issn | 1799-4934 (printed) | |
| dc.identifier.issn | 1799-4934 (ISSN-L) | |
| dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/120799 | |
| dc.identifier.urn | URN:ISBN:978-952-64-1283-2 | |
| dc.language.iso | en | en |
| dc.opn | Munro, James Ian, Prof., University of Waterloo, Canada | |
| dc.opn | Kozma, László, Asst. Prof., Freie Universität Berlin, Germany | |
| dc.publisher | Aalto University | en |
| dc.publisher | Aalto-yliopisto | fi |
| dc.relation.ispartofseries | Aalto University publication series DOCTORAL THESES | en |
| dc.relation.ispartofseries | 77/2023 | |
| dc.rev | Munro, James Ian, Prof., University of Waterloo, Canada | |
| dc.rev | Kozma, László, Asst. Prof., Freie Universität Berlin, Germany | |
| dc.subject.keyword | online algorithms | en |
| dc.subject.keyword | data structures | en |
| dc.subject.keyword | binary search trees | en |
| dc.subject.keyword | list updates | en |
| dc.subject.keyword | extremal combinatorics | en |
| dc.subject.other | Computer science | en |
| dc.title | New Analytical Methods for Online Binary Search Trees | en |
| dc.type | G5 Artikkeliväitöskirja | fi |
| dc.type.dcmitype | text | en |
| dc.type.ontasot | Doctoral dissertation (article-based) | en |
| dc.type.ontasot | Väitöskirja (artikkeli) | fi |
| local.aalto.acrisexportstatus | checked 2023-06-02_0922 | |
| local.aalto.archive | yes | |
| local.aalto.formfolder | 2023_05_16_klo_08_39 |
