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

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

Bougé, Luc, Laboratoire de l'Informatique du Parallélisme, Ecole Normale Supérieure de Lyon, France (Luc.Bouge@ens-lyon.fr).
Boyar, Joan F., Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark (joan@imada.sdu.dk).
Eckerle, Jürgen, Institut für Informatik, Universität Freiburg, Germany (eckerle@informatik.uni-freiburg.de).
Fagerberg, Rolf, Department of Computer Science, University of Aarhus, Denmark (rolf@daimi.au.dk).
Gabarró, Joaquim, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Spain (gabarro@lsi.upc.es).
Hanke, Sabine, Institut für Informatik, Universität Freiburg, Germany (hanke@informatik.uni-freiburg.de).
Jacobsen, Lars Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark (eljay@imada.sdu.dk).
Jensen, Rune E., ALOC Bonnier A/S, Denmark (runej@aloc.dk).
Larsen, Kim S., Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark (kslarsen@imada.sdu.dk).
Malmi, Lauri, Laboratory of Information Processing Science, Helsinki University of Technology, Finland (Lauri.Malmi@hut.fi).
Messeguer, Xavier, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Spain (peypoch@lsi.upc.es).
Nurmi, Otto, Department of Computer Science, University of Helsinki, Finland (Otto.Nurmi@cs.helsinki.fi).
Ottmann, Thomas, Institut für Informatik, Universität Freiburg, Germany (ottmann@informatik.uni-freiburg.de).
Pollari-Malmi, Kerttu, Department of Computer Science, University of Helsinki, Finland (pollari@cs.helsinki.fi).
Riu, Daniel, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Spain.
Schabanel, Nicolas, Laboratoire de l'Informatique du Parallélisme, Ecole Normale Supérieure de Lyon, (Nicolas.Schabanel@ens-lyon.fr).
Soisalon-Soininen, Eljas, Laboratory of Information Processing Science, Helsinki University of Technology, Finland (ess@cs.hut.fi).
Valles, Borja, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Spain (valles@lsi.upc.es).
Widmayer, Peter, Department of Computer Science, ETH Zürich, Switzerland (widmayer@inf.ethz.ch).
Wood, Derick, Computer Science Department, Hong Kong University of Science and Technology, Hong Kong (dwood@cs.ust.hk).
Ylönen, Tatu, Laboratory of Information Processing Science, Helsinki University of Technology, Finland (ylo@cs.hut.fi).

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.

Last modified: May 3, 2003.

Kim Skak Larsen (kslarsen@imada.sdu.dk)