The cost of offline binary search tree algorithms and the complexity of the request sequence. (English) Zbl 1136.68020
Summary: In evaluating the performance of online algorithms for search trees, one wants to compare them to the best offline algorithm available. In this paper we lower bound the cost of an optimal offline binary search tree using the Kolmogorov complexity of the request sequence. We obtain several applications for this result. First, any offline binary search tree algorithm can be at most a constant factor away from the entropy of the process producing the request sequence. Second, for a fraction \(1-1/2^m\) of request sequences of length \(m\) on \(n\) items the cost of any offline algorithm is \(\Omega (m(\log n-1))\). Third, the expected cost of splay trees is within a constant factor of the expected cost of an optimal offline binary search tree algorithm in a subset of Markov chains.
MSC:
| 68P10 | Searching and sorting |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |
References:
| [1] | S. Albers, L.M. Favrholdt, O. Giel, On paging with locality of reference, in: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM Press, 2002, pp. 258-267; S. Albers, L.M. Favrholdt, O. Giel, On paging with locality of reference, in: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM Press, 2002, pp. 258-267 · Zbl 1192.68271 |
| [2] | Blum, A.; Chawla, S.; Kalai, A., Static optimality and dynamic search-optimality in lists and trees, Algorithmica, 36, 3, 249-260 (2003) · Zbl 1045.68045 |
| [3] | Cole, R., On the dynamic finger conjecture for splay trees. Part II: The proof, SIAM Journal on Computing, 30, 1, 44-85 (2000) · Zbl 0959.68031 |
| [4] | Cole, R.; Mishra, B.; Schmidt, J.; Siegel, A., On the dynamic finger conjecture for splay trees. part I: Splay sorting \(\log n\)-block sequences, SIAM Journal on Computing, 30, 1, 1-43 (2000) · Zbl 0959.68030 |
| [5] | Cover, T.; Thomas, J., Elements of Information Theory (1991), John Wiley & Sons · Zbl 0762.94001 |
| [6] | Culik II, K.; Wood, D., A note on some tree similarity measures, Information Processing Letters, 15, 1, 39-42 (1982) · Zbl 0489.68058 |
| [7] | Demaine, E. D.; Harmon, D.; Iacono, J.; Paˇtraşcu, M., Dynamic optimality — almost, (Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004), IEEE Computer Society Press), 484-490 |
| [8] | Grünwald, P.; Vitányi, P., Kolmogorov complexity and information theory, with an interpretation in terms of questions and answers, Journal of Logic, Language, and Information, 12, 4, 497-529 (2003) · Zbl 1034.68051 |
| [9] | J. Iacono, Alternatives to splay trees with \(O ( \log n )\); J. Iacono, Alternatives to splay trees with \(O ( \log n )\) · Zbl 0987.68023 |
| [10] | Knuth, D. E., The Art of Computer Programming (1978), Addison-Wesley Longman Publishing Co., Inc.: Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA · Zbl 0191.17903 |
| [11] | Li, M.; Vitányi, P., An Introduction to Kolmogorov Complexity and Its Applications (1997), Springer Verlag · Zbl 0866.68051 |
| [12] | J.M. Lucas, Canonical forms for competitive binary search tree algorithms, Technical Report DCS-TR-250, Computer Science Department, Rutgers University, 1988; J.M. Lucas, Canonical forms for competitive binary search tree algorithms, Technical Report DCS-TR-250, Computer Science Department, Rutgers University, 1988 |
| [13] | Munro, J. I., Competitiveness of linear search, (Paterson, Mike, ESA 2000, Proceedings of the 8th Annual European Symposium. ESA 2000, Proceedings of the 8th Annual European Symposium, Lecture Notes in Computer Science, vol. 1879 (2000), Springer), 338-345 · Zbl 0974.68536 |
| [14] | Sleator, D. D.; Tarjan, R. E., Self-adjusting binary search trees, Journal of the ACM, 32, 3, 652-686 (1985) · Zbl 0631.68060 |
| [15] | Sleator, D. D.; Tarjan, R. E.; Thurston, W. P., Rotation distance, triangulations, and hyperbolic geometry, Journal of the American Mathematical Society, 1, 3, 647-681 (1988) · Zbl 0653.51017 |
| [16] | Wilber, R., Lower bounds for accessing binary search trees with rotations, SIAM Journal on Computing, 18, 1, 56-67 (1989) · Zbl 0674.68014 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
