The Group Access Bounds for Binary Search Trees
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2024-07
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Leibniz International Proceedings in Informatics, LIPIcs ; Volume 297
Abstract
The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees (BSTs) that implies interesting consequences such as static optimality, static finger, and working set property on any access sequence X = (x1, x2, . . ., xm). However, there are known corollaries of the dynamic optimality that cannot be derived via the access lemma, such as the dynamic finger, and any o(log n)-competitive ratio to the optimal BST where n is the number of keys. In this paper, we introduce the group access bound that can be defined with respect to a reference group access tree. Group access bounds generalize the access lemma and imply properties that are far stronger than those implied by the classical access lemma. For each of the following results, there is a group access tree whose group access bound 1. Is O(√log n)-competitive to the optimal BST. 2. Achieves the k-finger bound with an additive term of O(m log k log log n) (randomized) when the reference tree is an almost complete binary tree. 3. Satisfies the unified bound with an additive term of O(m log log n). 4. Matches the unified bound with a time window k with an additive term of O(m log k log log n) (randomized). Furthermore, we prove the simulation theorem: For every group access tree, there is an online BST algorithm that is O(1)-competitive with its group access bound. In particular, any new group access bound will automatically imply a new BST algorithm achieving the same bound. Thereby, we obtain an improved k-finger bound (reference tree is an almost complete binary tree), an improved unified bound with a time window k, and matching the best-known bound for Unified bound in the BST model. Since any dynamically optimal BST must achieve the group access bounds, we believe our results provide a new direction towards proving o(log n)-competitiveness of the Splay tree and Greedy, two prime candidates for the dynamic optimality conjecture.Description
Publisher Copyright: © Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai. | openaire: EC/H2020/759557/EU//ALGOCom
Keywords
Binary Search Tree, Dynamic Optimality, Online Algorithm
Other note
Citation
Chalermsook, P, Gupta, M, Jiamjitrak, W, Pareek, A & Yingchareonthawornchai, S 2024, The Group Access Bounds for Binary Search Trees . in K Bringmann, M Grohe, G Puppis & O Svensson (eds), 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024 ., 38, Leibniz International Proceedings in Informatics, LIPIcs, vol. 297, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Colloquium on Automata, Languages, and Programming, Tallinn, Estonia, 08/07/2024 . https://doi.org/10.4230/LIPIcs.ICALP.2024.38