Problems arising from the use of data structures in a concurrent environment are studied. Efficiency considerations require that the search paths of a data structure should be short and that operations should not block too large a part of the structure for too long a time. These two requirements conflict, since keeping the paths short after an update can, in a straightforward implementation, block too large a part of the structure. One would prefer that all operations reserve only a small, fixed-size part of a structure at all times.
An elegant solution for these problems with dictionary operations was proposed in 1987. The solution was based on the notion of relaxed balance in AVL and B-trees and the decoupling of updates and rebalancing. In 1991 the idea of relaxing the balance condition was applied to red-black trees, the most promising data structures for implementing a data base in main memory. The newest results on the area concern augmenting the structures with further operations such as batch updating, and tightening the balance conditions.
The research has been done in co-operation with Prof. D. Wood (University of London, Canada), J. Eckerle (Universität Freiburg, Germany), and a group at Helsinki University of Technology lead by Prof. E. Soisalon-Soininen.
Publications: [68].