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.
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.
We have worked on obtaining relaxed variants of the most important standard search trees with the aim of matching the complexity results from the standard non-relaxed scenario. We have also focused on providing these results while at the same time restricting rebalancing operations to using standard single and double rotations, the motivation being that small operations require fewer locks in a concurrent environment. General as well as specialized results, which primarily contribute to our theoretical understanding of relaxed structures, have also been obtained. Recently, we have focused on practically motivated problems regarding B-tree like structures.
A significant focus for our research the last couple of years has been performance measures for on-line algorithms. On-line algorithms are algorithms which must respond to some requests in an on-line manner, i.e., before all future requests are known. The standard performance measure for on-line algorithms, the competitive ratio, has been criticized for being too pessimistic. With regards to performance measures for on-line algorithms, as well as standard worst-case complexity analyses, it is important to give algorithms as precise a "quality stamp" as possible, since decisions as to which algorithm should be chosen for a given problem relies on this.
Through a concrete problem, the seat reservation problem, we have defined and investigated a new measure, the accommodating ratio. The definition is similar to the competitive ratio, except that it is based on a smaller (and in some applications, more reasonable) set of request sequences. Informally, the idea is to only consider sequences which could be handled perfectly by an off-line algorithm.
Based on the experiences from this work, we have defined the performance measure the accommodating function, which comprises the competitive ratio and the accommodating ratio. The new measure can contain much more information about an on-line problem than any of the other two measures alone. In fact, we have proven that the two simpler measures sometimes give divergent results. Thus, the whole truth can only be obtained by a more general measure, such as the accommodating function.
Regarding concrete on-line problems, we have been working on the seat reservation problem, call control, fair and unfair variants of bin packing, scheduling problems, and packet bundling (dynamic TCP acknowledgment).
Relational algebra is the theoretical foundation on which modern query languages are based, and it is also closely related to the formalism in which execution plans are described. It consists of a collection of operators for manipulating relations over some domain values. Though it is often necessary to perform computations on domain values, strategies for this have not been built into relational algebra, but are often added in an ad-hoc manner. We have worked on incorporating computations on domain values in a more natural way by making a generalized version of the grouping operator a first class citizen of the formalism. In addition to incorporating computations on domain values, including aggregation, in to the formalism in a natural way, the expressiveness of the formalism is increased. These advantages are obtained without increasing the computational power of the formalism. The latter is of great importance with regards to the query optimization process.
Since one database query can often involve megabytes of data, it is crucial that an efficient strategy for the evaluation of a query is decided upon prior to the actual execution. We have designed methods focusing on avoiding some of the sorting which often accounts for a large part of the execution time. Parts of our work focuses on the optimization of unary queries, while parts are focused on optimization of sort-merge evaluations of general queries.
The search tree data structure is one of the most important, theoretically as well as in practice. In general in computer systems, it can be of interest to have the ability to investigate the past, exactly as it were at some earlier time. We have investigated this problem with regards to search trees, focusing on the problem of efficiently providing a chronological transcript of the information related to some fixed key.
For many years, regular expressions with back referencing have been used in a variety of software products in common use, including operating systems, editors, and programming languages. In these products, regular expressions have been extended with a naming construct. If a subexpression is named by some variable, whenever this subexpression matches some string, that string is assigned to the variable. Later occurrences of the same variable will then match the string assigned to it. This construction greatly increases the power of regular expressions and is useful in text searching as well as in text substitution in large documents. We have studied the nested usage of this operator, and proved that the power of the expressions increase with the number of nested levels that are allowed.
Zero-knowledge is a part of the area of Cryptology which focuses on the transfer of information which reveals nothing more than what is required. We have worked on bounds for the number of products of affine combinations which can be produced when elements can be arranged freely in matrices. This work is motivated by a technique for improving the communication complexity of zero-knowledge proofs.
Process languages form the theoretical basis for concurrent programming languages as well as the analysis of concurrent systems. We have studied the use of sets of labelled partial orders as denotational model for process algebras. More specifically, we study their capability to capture degrees of nonsequentiality (genuine concurrency) of processes. We have developed four full abstractness results. The operational equivalences are based on maximal action-sequences and step-sequences - defined for a very simple process language and its extension with a refinement combinator (change of atomicity). The denotational models are all expressed as abstractions of a standard association of sets of labelled partial orders with processes.
Concurrent systems are some times described using bisimulation formulas. The problem of checking or optimally simplifying bisimulation formulas is likely to be computationally very hard. We have taken a different view at the problem: we set out to define a very fast algorithm, and then see what we can obtain. Sometimes our algorithm can simplify a formula perfectly, sometimes it cannot. However, the algorithm is extremely fast and can, therefore, be added to formula-based bisimulation model checkers at practically no cost. When the formula can be simplified by our algorithm, this can have a dramatic positive effect on the better, but also more time consuming, theorem provers which will finish the job.