SDU
IMADA

Search Trees with Relaxed Balance Home Page

http://www.imada.sdu.dk/~kslarsen/RelBal/

Last updated May 14, 2002.

This page contains information relevant to the subject Search Trees with Relaxed Balance. Updates, corrections, and pointers to additional information can be sent to the following address; preferably via e-mail.

Kim S. Larsen
Department of Mathematics and Computer Science
University of Southern Denmark, Odense
Campusvej 55
DK-5230 Odense M
Denmark

kslarsen@imada.sdu.dk
phone (direct): +45 6550 2328
phone (secretary): +45 6550 2387
fax: +45 6550 2325

Table of Content

What is Relaxed Balance?

Relaxed balance is the term used for search trees where the rebalancing has been uncoupled from the updating. Normally, in balanced search trees, rebalancing is tightly coupled to the updating: as soon as an update has been performed, rebalancing operations are applied until the given balance constraints are again fulfilled. In search trees with relaxed balance, updating and rebalancing are processes which can be controlled separately. Typically, this means that balance constraints must be relaxed such that an update can leave the tree in a well-defined state. Thus, the assumptions under which rebalancing is carried out are changed. This poses the problem of still carrying out the rebalancing efficiently.

Why is Relaxed Balance Interesting?

Relaxed balance deals with a fundamental question concerning one of the most important classes of data structures in computer science, the balanced search trees. It is therefore important to obtain as full an understanding of the issue as possible. Additionally, there are practical applications for this line of work.

In standard search trees, the rebalancing part of an update is the more time-consuming part of the whole update. If search and update requests come in bursts (possibly from several external sources), the search tree may occasionally be unable to process the requests as fast as desirable. In search trees with relaxed balance, rebalancing can be "turned off" for a short period of time in order to speed up the request processing. When the burst is over, the tree can be rebalanced again, while searching and updating still continue at a slower pace. Of course, if rebalancing is postponed for too long, the tree can become completely unbalanced.

A different motivation comes from using search trees on shared-memory architectures. If rebalancing is carried out in connection with updates, either top-down or bottom-up, this creates a congestion problem at the root in particular, and all the locking involved seriously limits the amount of parallelism possible in the system. In search trees with relaxed balance, rebalancing operations can be carried out such that they, and their associated locks, are very localized in time as well as in space. In particular, exclusive locking of whole paths or step-wise exclusive locking down paths can be avoided. This means that the amount of parallelism possible is not limited by the height of the tree. To what extent these properties can be exploited by present or future architectures is still an open question.

Published Papers

Papers are listed in reverse chronological order.
Relaxed Balance using Standard Rotations
Kim S. Larsen, Eljas Soisalon-Soininen, Peter Widmayer
Algorithmica 31(4): 501-512, 2001.
Abstract.

Complexity of Layered Binary Search Trees with Relaxed Balance
Lars Jacobsen, Kim S. Larsen
Seventh Italian Conference on Theoretical Computer Science, Lecture Notes in Computer Science 2202: 269-284, Springer-Verlag, 2001.
Abstract.

Relaxed Balance for Search Trees with Local Rebalancing
Kim S. Larsen, Thomas Ottmann, Eljas Soisalon-Soininen
Acta Informatica 37(10): 743-763, 2001.
Abstract.

Variants of (a,b)-Trees with Relaxed Balance
Lars Jacobsen, Kim S. Larsen
International Journal of Foundations of Computer Science 12(4): 455-478, 2001.
Abstract.

Search Trees with Relaxed Balance and Near-Optimal Height
Rolf Fagerberg, Rune E. Jensen, Kim S. Larsen
Seventh International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 2125: 414-425, Springer-Verlag, 2001.
Abstract.

Relaxed Multi-Way Trees with Group Updates
Kim S. Larsen
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 93-101, ACM Press, 2001.
Abstract.

AVL Trees with Relaxed Balance
Kim S. Larsen
Journal of Computer and System Sciences 61(3): 508-522, 2000.
Abstract.

Group Updates for Red-Black Trees
Sabine Hanke, Eljas Soisalon-Soininen
Proceedings of the 4th Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science 1767: 253-262, Springer-Verlag, 2000.
Abstract.

Group Updates for Relaxed Height-Balanced Trees
Lauri Malmi, Eljas Soisalon-Soininen
Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 358-367, 1999.

The Performance of Concurrent Red-Black Tree Algorithms
Sabine Hanke
Proceedings of the 3rd International Workshop on Algorithm Engineering, Lecture Notes in Computer Science 1668: 286-300, Springer-Verlag, 1999.
Abstract.

Amortized Constant Relaxed Rebalancing using Standard Rotations
Kim S. Larsen
Acta Informatica, 35(10):859-874, 1998.
Abstract.

Concurrent Rebalancing on HyperRed-Black Trees
Joaquim Gabarró, Xavier Messeguer, Daniel Riu
Proceedings of the 17th International Conference of the Chilean Computer Science Society, pp. 93-104, IEEE Computer Society Press, 1997.
Abstract.

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues
Joan Boyar, Rolf Fagerberg, Kim S. Larsen
Journal of Computer and System Sciences 55(3): 504-521, 1997.
Abstract.

Concurrent Rebalancing of AVL Trees: A Fine-Grained Approach
Luc Bougé, Joaquim Gabarró, Xavier Messeguer, Nicolas Schabanel
Proceedings of the Third Annual European Conference on Parallel Processing, Lecture Notes in Computer Science 1300: 421-429, Springer-Verlag, 1997.
Abstract.

Relaxed Balance through Standard Rotations
Kim S. Larsen, Eljas Soisalon-Soininen, Peter Widmayer
Fifth International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 1272: 450-461, Springer-Verlag, 1997.
Abstract.

Relaxed Balance for Search Trees with Local Rebalancing
Kim S. Larsen, Thomas Ottmann, Eljas Soisalon-Soininen
Fifth Annual European Symposium on Algorithms, Lecture Notes in Computer Science 1284: 350-363, Springer-Verlag, 1997.
Abstract.

Relaxed Balancing in Search Trees
Eljas Soisalon-Soininen, Peter Widmayer
Advances in Algorithms, Languages, and Complexity, pp. 267-283, Kluwer Academic Publishers, 1997.

Relaxed Balanced Red-Black Trees
S. Hanke, T. Ottmann, E. Soisalon-Soininen
Proceedings of the 3rd Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science 1203: 193-204, 1997.
Abstract.

Concurrency Control in B-Trees with Batch Updates
Kerttu Pollari-Malmi, Eljas Soisalon-Soininen, Tatu Ylönen
IEEE Transactions on Knowledge and Data Engineering 8(6): 975-984, 1996.

A New Method for Updating and Rebalancing Tree-Type Main Memory Dictionaries
L. Malmi
Nordic Journal of Computing 3(2): 111-130, 1996.
Abstract.

Chromatic Binary Search Trees - A Structure for Concurrent Rebalancing
Otto Nurmi, Eljas Soisalon-Soininen
Acta Informatica 33(6): 547-557, 1996.

Efficient Rebalancing of B-Trees with Relaxed Balance
Kim S. Larsen, Rolf Fagerberg
International Journal of Foundations of Computer Science 7(2): 169-186, 1996.
Abstract.

Relaxed AVL Trees, Main-Memory Databases and Concurrency
Otto Nurmi, Eljas Soisalon-Soininen, Derick Wood
International Journal of Computer Mathematics 62: 23-44, 1996.

B-Trees with Relaxed Balance
Kim S. Larsen, Rolf Fagerberg
Proceedings of the 9th International Parallel Processing Symposium, pp. 196-202, IEEE Computer Society Press, 1995.
Abstract.

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues
Joan Boyar, Rolf Fagerberg, Kim S. Larsen
Fourth International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 955: 270-281, Springer-Verlag, 1995.
Abstract.

AVL Trees with Relaxed Balance
Kim S. Larsen
Proceedings of the 8th International Parallel Processing Symposium, pp. 888-893, IEEE Computer Society Press, 1994.
Abstract.

Efficient Rebalancing of Chromatic Search Trees
Joan Boyar, Kim S. Larsen
Journal of Computer and System Sciences, 49(3): 667-682, 1994.
Abstract.

Efficient Rebalancing of Tree-Type Main Memory Dictionaries
Lauri Malmi
Fifth Australian-Asian Database Conference, pp. 227-246, 1993.

Efficient Rebalancing of Chromatic Search Trees
Joan Boyar, Kim S. Larsen
Proceedings of the Third Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 621: 151-164, Springer-Verlag, 1992.
Abstract.

Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees
Otto Nurmi, Eljas Soisalon-Soininen
Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 192-198, 1991.

Concurrency Control in Database Structures with Relaxed Balance
O. Nurmi, E. Soisalon-Soininen, D. Wood
Proceedings of the 6th ACM Symposium on Principles of Database Systems, pp. 170-176, 1987.

Technical Reports

We only list technical reports which do not appear in the list above.
HyperChromatic trees: a fine-grained approach to distributed algorithms on RedBlack trees
Xavier Messeguer, Borja Valles
Technical Report LSI-98-13-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, 1998.
Abstract. Paper.

Chromatic Search Trees Revisited
Sabine Hanke
Technical Report 90, Institut für Informatik, Universität Freiburg, 1997.
Abstract. Paper.

Relaxed Balancing Made Simple
Th. Ottmann, E. Soisalon-Soininen
Technical Report 71, Institut für Informatik, Universität Freiburg, 1995.
Abstract. Paper. Talk.

Concurrent Perfect Balancing of Binary Search Trees
Jürgen Eckerle, Otto Nurmi
Technical Report 50, Institut für Informatik, Universität Freiburg, 1994.
Abstract. Paper.

Dissertations

Rot-Schwarz-Bäume in Mehrbenutzerumgebungen
Sabine Hanke
Institut für Informatik, Universität Freiburg, 2000.
Abstract. Thesis.

On Updating and Balancing Relaxed Balanced Search Trees in Main Memory
Lauri Malmi
Laboratory of Information Processing Science Helsinki University of Technology, 1997.

Authors

Referencing Papers on this Page

Entries for all references on this page are available in BibTeX and pdf.

Related Information

The relaxed balance page of Universität Freiburg.

A relaxed balance animation.

Relaxed balance used as an example:

Tools And Services For Authoring On The Fly
Christian Bacher, Thomas Ottmann
Proceedings of ED-MEDIA'96, Boston, Mass., USA, June 17-22, 1996.
Talk.

For more general information and references to other topic home pages, see Comp.Theory FAQ.


SDU IMADA
Last modified: May 3, 2003.
Kim Skak Larsen (kslarsen@imada.sdu.dk)