Static optimality and dynamic search-optimality in lists and trees

ABSTRACT

Adaptive data structures form a central topic of on-line algorithms research, beginning with the results of Sleator and Tarjan showing that splay trees achieve static optimality for search trees, and that Move-to-Front is constant competitive for the list update problem [ST85a, ST85b]. This paper is inspired by the observation that one can in fact achieve a 1 + ε ratio against the best static object in hindsight for a wide range of data structure problems via "weighted experts" techniques from Machine Learning, if computational decision-making costs are not considered.In this paper, we give two results. First, we show that for the case of lists, we can achieve a 1 + ε ratio with respect to the best static list in hindsight, by a simple efficient algorithm. This algorithm can then be combined with existing results to simultaneously achieve good static and dynamic bounds. Second, for trees, we show a (computationally inefficient) algorithm that achieves what we call "dynamic search optimality": dynamic optimality if we allow the online algorithm to make free rotations after each request. We hope this to be a step towards solving the longstanding open problem of achieving true dynamic optimality for trees.

REFERENCES

• 1: P. Auer , N. Cesa-Bianchi , Y. Freund , R. E. Schapire, Gambling in a rigged casino: The adversarial multi-armed bandit problem, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.322, October 23-25, 1995
• 2: Susanne Albers , Bernhard von Stengel , Ralph Werchner, A combined BIT and TIMESTAMP algorithm for the list update problem, Information Processing Letters, v.56 n.3, p.135-139, Nov. 10, 1995 [doi>10.1016/0020-0190(95)00142-Y]
• 3: {Bur00} C. Burch. Machine learning in metrical task systems and other on-line problems. CMU Tech Report CMU-CS-00-135, May 2000.
• 4: Avrim Blum , Carl Burch, On-line Learning and the Metrical Task System Problem, Machine Learning, v.39 n.1, p.35-58, April 2000 [doi>10.1023/A:1007621832648]
• 5: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 6: Deepak Chawla , Lin Li , Stephen Scott, Efficiently Approximating Weighted Sums with Exponentially Many Terms, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.82-98, July 16-19, 2001
• 7: Yoav Freund , Robert E. Schapire, Game theory, on-line prediction and boosting, Proceedings of the ninth annual conference on Computational learning theory, p.325-332, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238163]
• 8: A. Kalai , S. Vempala, Efficient algorithms for universal portfolios, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.486, November 12-14, 2000
• 9: {Luc88} Joan M. Lucas. Canonical forms for competitive binary search tree algorithms. Technical Report DCS-TR-250, Rutgers University, 1988.
• 10: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 11: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 12: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 13: Boris Teia, A lower bound for randomized list update algorithms, Information Processing Letters, v.47 n.1, p.5-9, Aug. 9, 1993 [doi>10.1016/0020-0190(93)90150-8]
• 14: R. Wilber, Lower bounds for accessing binary search trees with rotations, SIAM Journal on Computing, v.18 n.1, p.56-67, Feb. 1989 [doi>10.1137/0218004]