License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.28
URN: urn:nbn:de:0030-drops-128944
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12894/
Chalermsook, Parinya ;
Jiamjitrak, Wanchote Po
New Binary Search Tree Bounds via Geometric Inversions
Abstract
The long-standing dynamic optimality conjecture postulates the existence of a dynamic binary search tree (BST) that is O(1)-competitive to all other dynamic BSTs. Despite attempts from many groups of researchers, we believe the conjecture is still far-fetched. One of the main reasons is the lack of the "right" potential functions for the problem: existing results that prove various consequences of dynamic optimality rely on very different potential function techniques, while proving dynamic optimality requires a single potential function that can be used to derive all these consequences. In this paper, we propose a new potential function, that we call extended (geometric) inversion. Inversion is arguably the most natural potential function principle that has been used in competitive analysis but has never been used in the context of BSTs. We use our potential function to derive new results, as well as streamlining/strengthening existing results.
First, we show that a broad class of BST algorithms (including Greedy and Splay) are O(1)-competitive to Move-to-Root algorithm and therefore have simulation embedding property - a new BST property that was recently introduced and studied by Levy and Tarjan (SODA 2019). This result, besides substantially expanding the list of BST algorithms having this property, gives the first potential function proof of the simulation embedding property for BSTs (thus unifying apparently different kinds of results). Moreover, our analysis is the first where the costs of two dynamic binary search trees are compared against each other directly and systematically. Secondly, we use our new potential function to unify and strengthen known BST bounds, e.g., showing that Greedy satisfies the weighted dynamic finger property within a multiplicative factor of (5+o(1)).
BibTeX - Entry
@InProceedings{chalermsook_et_al:LIPIcs:2020:12894,
author = {Parinya Chalermsook and Wanchote Po Jiamjitrak},
title = {{New Binary Search Tree Bounds via Geometric Inversions}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {28:1--28:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12894},
URN = {urn:nbn:de:0030-drops-128944},
doi = {10.4230/LIPIcs.ESA.2020.28},
annote = {Keywords: Binary Search Tree, Potential Function, Inversion, Data Structures, Online Algorithms}
}
|
Keywords: |
|
Binary Search Tree, Potential Function, Inversion, Data Structures, Online Algorithms |
|
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
