The Group Access Bounds for Binary Search Trees

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.