In order to gain maximal efficiency of the concurrent use of search trees the number of nodes to be locked at a time should be as small aa possible, and the locks should be released aa soon aa possible.We propose a new rebalancing method for binary search treea that allows rebalancing to be uncoupled from updating, so as to make updating faster.The trees we use are obtained by relaxing the balance conditions of red-black trees.When not involved with updating, the rebalancing task can be performed as a shadow process being active all the time, or it can be performed outside rush hours, at night, for example.1.

Abstract Language processor generators are systems that produce various language processors (including compilers) on the basis of a high‐level specification. The design of language processor generators is discussed on the basis of experiments with a traditional compiler writing system (HLP78) employing pore LALR parsing and general attribute grammars. It is argued that these methods are too primitive from the practical point of view. The design of a new language processor generator, HLP84, is based on this view. This system is an attempt to provide high‐level tools for a restricted class of applications (one‐pass analysis). The syntactic facilities include regular expressions on the right‐hand sides of productions, a disambiguating mechanism that is integrated with regular expressions, and a mechanism for using semantic information to aid parsing. The semantic facilities include automatic support for semantic error handling and for symbol tables. Early experiences with the new system show that in spite of the general overhead caused by the higher automation level, the system allows the generation of reasonably efficient processors.

We consider the separation of rebalancing from updates in several database structures, such as B-trees for external and AVL-trees for internal structures. We show how this separation can be implemented such that rebalancing is performed by local background processes. Our solution implies that even simple locking schemes (without additional links and copies of certain nodes) for concurrency control are efficient in the sense that at any time only a small constant number of nodes must be locked.

Given a point set in plane and a fixed planar region (window) a window query consists of enumerating the points in a translate of the region. A recently presented result shows that a static data structure of optimal size enables window queries for convex regions in optimal time. We show that if the windows are (maybe non-convex) polygons another data structure of optimal size supports not only window queries in optimal time but also allows updating of the point set in optimal time.

Given two points a=(a1,a2,…,ad) and b=(b1,b2,…,bd) in d-dimensional space, a dominates b if a≠b and for each i=1…d holds ai≥bi. The direct dominance problem consists of computing a relation of minimal size on a given set of n points such that the transitive closure of the relation gives all the dominances in the set. We present an Ο(n log n +k) time and Ο(n) space algorithm for the problem of two-dimensional space. The algorithm is optimal within a constant factor. Further, we show that the three-dimensional problem can be solved in Ο((n+k) log2n) time and space, or alternatively in Ο((n+k) log3n) time and Ο((n+k)log n) space.