Kim S. Larsen
ABSTRACT
Data structures with relaxed balance differ from standard structures in that rebalancing can be delayed and interspersed with updates. This gives extra flexibility in both sequential and parallel applications.
We study the version of multi-way trees called (a,b)-trees (which includes B-trees) with the operations insertion, deletion, and group insertion. The latter has applications in for instance document databases and WWW search engines. We prove that we obtain the optimal asymptotic rebalancing complexities of amortized constant time for insertion and deletion and amortized logarithmic time in the size of the group for group insertion. These results hold even for the relaxed version.
Our results also demonstrate that a binary tree scheme with the same complexities can be designed. This is an improvement over the existing results in the most interesting cases.
- 1.G. M. Adel'son-Vel'skii and E. M. Landis. An Algorithm for the Organisation of Information. Doklady Akadamii Nauk SSSR, 146:263-266, 1962. In Russian. English translation in Soviet Math. Doklady, 3:1259-1263, 1962.]]Google Scholar
- 2.R. Bayer. Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms. Acta Informatica, 1:290-306, 1972.]]Google ScholarDigital Library
- 3.R. Bayer and E. McCreight. Organization and Maintenance of Large Ordered Indexes. Acta Informatica, 1:173-189, 1972.]]Google ScholarDigital Library
- 4.L. Bougd, J. Gabarr6, X. Messeguer, and N. Schabanel. Concurrent Rebalancing of AVL Trees: A Fine-Grained Approach. In Proceedings of the Third Annual European Conference on Parallel Processing, volume 1300 of Lecture Notes in Computer Science, pages 421-429. Springer-Verlag, 1997.]] Google ScholarDigital Library
- 5.J. Boyar, R. Fagerberg, and K. S. Larsen. Amortization Results for Chromatic Search Trees, with an Application to Priority Queues. In Fourth International Workshop on Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, pages 270-281. Springer-Verlag, 1995.]] Google ScholarDigital Library
- 6.J. Boyar, R. Fagerberg, and K. S. Larsen. Amortization Results for Chromatic Search Trees, with an Application to Priority Queues. Journal of Computer and System Sciences, 55(3):504-521, 1997.]] Google ScholarDigital Library
- 7.J. F. Boyar and K. S. Lateen. Efficient Rebalancing of Chromatic Search Trees. In Proceedings of the Third Scandinavian Workshop on Algorithm Theory, volume 621 of Lecture Notes in Computer Science, pages 151-164. Springer-Verlag, 1992.]] Google ScholarDigital Library
- 8.J. F. Boyar and K. S. Lateen. Efficient Rebalancing of Chromatic Search Trees. Journal of Computer and System Sciences, 49(3):667-682, 1994.]] Google ScholarDigital Library
- 9.A. F. Cardenas. Analysis and Performance of Inverted Data Base Structures. Communications of the A CM, 18(5):253-263, 1975.]] Google ScholarDigital Library
- 10.C. Faloutsos and H. V. Jagadish. Hybrid Index Organizations for Text Databases. In Third International Conference on Extending Database Technology, volume 580 of Lecture Notes in Computer Science, pages 310-327, 1992.]] Google ScholarDigital Library
- 11.L. J. Guibas and R. Sedgewick. A Dichromatic Framework for Balanced Trees. In Proceedings of the 19th Annual IEEE Symposium on the Foundations of Computer Science, pages 8-21, 1978.]]Google ScholarDigital Library
- 12.S. Hanke. The Performance of Concurrent Red-Black Tree Algorithms. In Proceedings of the 3rd International Workshop on Algorithm Engineering, volume 1668 of Lecture Notes in Computer Science, pages 286-300. Springer-Verlag, 1999.]] Google ScholarDigital Library
- 13.S. Hanke, T. Ottmann, and E. Soisalon-Soininen. Relaxed Balanced Red-Black Trees. In Proceedings of the 3rd Italian Conference on Algorithms and Complexity, volume 1203 of Lecture Notes in Computer Science, pages 193-204. Springer-Verlag, 1997.]] Google ScholarDigital Library
- 14.S. Hanke and E. Soisalon-Soininen. Group Updates for Red-Black Trees. In Proceedings of the 4th Italian Conference on Algorithms and Complexity, volume 1767 of Lecture Notes in Computer Science, pages 253-262. Springer-Verlag, 2000.]] Google ScholarDigital Library
- 15.S. Huddleston and K. Mehlhorn. A New Data Structure for Representing Sorted Lists. Acta Informatica, 17:157-184, 1982.]]Google ScholarDigital Library
- 16.L. Jacobsen and K. S. Larsen. Variants of (a, b)-Trees with Relaxed Balance. International Journal of Foundations of Computer Science. To appear.]]Google Scholar
- 17.L. Jacobsen, K. S. Lateen, and M. N. Nielsen. On the Existence and Construction of Non-Extreme (a,b)-Trees. In preparation.]]Google Scholar
- 18.S.-D. Lang, J. R. Driscoll, and J. H. Jou. Batch Insertion for Tree Structured File Organizations--Improving Differential Database Representation. Information Systems, 11(2):167-175, 1986.]] Google ScholarDigital Library
- 19.K. S. Lateen. AVL Trees with Relaxed Balance. In Proceedings of the 8th International Parallel Processing Symposium, pages 888-893. IEEE Computer Society Press, 1994.]] Google ScholarDigital Library
- 20.K. S. Lateen. Amortized Constant Relaxed Rebalancing using Standard Rotations. Acta lnformatica, 35(10):859-874, 1998.]]Google ScholarCross Ref
- 21.K. S. Lateen. AVL Trees with Relaxed Balance. Journal of Computer and System Sciences, 61(3):508-522, 2000.]] Google ScholarDigital Library
- 22.K. S. Lateen and R. Fagerberg. B-Trees with Relaxed Balance. In Proceedings of the 9th International Parallel Processing Symposium, pages 196-202. IEEE Computer Society Press, 1995.]] Google ScholarDigital Library
- 23.K. S. Lateen and R. Fagerberg. Efficient Rebalancing of B-Trees with Relaxed Balance. International Journal of Foundations of Computer Science, 7(2):169-186, 1996.]]Google Scholar
- 24.K. S. Lateen, T. Ottmann, and E. Soisalon-Soininen. Relaxed Balance for Search Trees with Local Rebalancing. In Fifth Annual European Symposium on Algorithms, volume 1284 of Lecture Notes in Computer Science, pages 350-363. Springer-Verlag, 1997.]] Google ScholarDigital Library
- 25.K. S. Lateen, E. Soisalon-Soininen, and P. Widmayer. Relaxed Balance through Standard Rotations. In Fifth International Workshop on Algorithms and Data Structures, volume 1272 of Lecture Notes in Computer Science, pages 450-461. Springer-Verlag, 1997. To appear in Algorithmica.]] Google ScholarDigital Library
- 26.L. Malmi and E. Soisalon-Soininen. Group Updates for Relaxed Height-Balanced Trees. In Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 358-367. ACM Press, 1999.]] Google ScholarDigital Library
- 27.K. Mehlhorn. Sorting and Searching, volume 1 of Data Structures and Algorithms. Springer-Verlag, 1986.]]Google Scholar
- 28.K. Mehlhorn and A. Tsakalidis. An Amortized Analysis of Insertions into AVL-Trees. SIAM Journal on Computing, 15(1):22-33, 1986.]] Google ScholarDigital Library
- 29.O. Nurmi and E. Soisalon-Soininen. Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees. In Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 192-198, 1991.]] Google ScholarDigital Library
- 30.O. Nurmi and E. Soisalon-Soininen. Chromatic Binary Search Trees--A Structure for Concurrent Rebalaneing. Acta Informatica, 33(6):547-557, 1996.]]Google ScholarCross Ref
- 31.O. Nurmi, E. Soisalon-Soininen, and D. Wood. Concurrency Control in Database Structures with Relaxed Balance. In Proceedings of the 6th ACM Symposium on Principles of Database Systems, pages 170-176, 1987.]] Google ScholarDigital Library
- 32.O. Nurmi, E. Soisalon-Soininen, and D. Wood. Relaxed AVL Trees, Main-Memory Databases and Concurrency. International Journal of Computer Mathematics, 62:23-44, 1996.]]Google ScholarCross Ref
- 33.K. Pollari-Malmi, E. Soisalon-Soininen, and T. Y15nen. Concurrency Control in B-Trees with Batch Updates. IEEE Transactions on Knowledge and Data Engineering, 8(6):975-984, 1996.]] Google ScholarDigital Library
- 34.N. Sarnak and R. E. Tarjan. Planar Point Location Using Persistent Search Trees. Communications of the ACM, 29:669-679, 1986.]] Google ScholarDigital Library
- 35.E. Soisalon-Soininen and P. Widmayer. Relaxed Balancing in Search Trees. In Advances in Algorithms, Languages, and Complexity, pages 267-283. Kluwer Academic Publishers, 1997.]]Google ScholarCross Ref
- 36.R. E. Tarjan. Amortized Computational Complexity. SIAM Journal on Algebraic and Discrete Methods, 6(2):306-318, 1985.]]Google ScholarDigital Library
Index Terms
- Relaxed multi-way trees with group updates
Recommendations
Relaxed multi-way trees with group updates
Special issu on PODS 2001Data structures with relaxed balance differ from standard structures in that rebalancing can be delayed and interspersed with updates. This gives extra flexibility in both sequential and parallel, applications. We study the version of multi-way trees ...
Comments