Succinct representation of dynamic trees

We study the problem of maintaining a dynamic ordered tree succinctly under updates of the following form: insertion or deletion of a leaf, insertion of a node on an edge (edge subdivision) or deletion of a node with only one child (the child becomes a child of its former grandparent). We allow satellite data of a fixed size to be associated to the nodes of the tree.We support update operations in constant amortized time and support access to satellite data and basic navigation operations in worst-case constant time; the basic navigation operations include parent, first/last-child, previous/next-child. These operations are moving from a node to its parent, leftmost/rightmost child, and its previous and next child respectively.We demonstrate that to efficiently support more extended operations, such as determining the i-th child of a node, rank of a child among its siblings, or size of the subtree rooted at a node, one requires a restrictive pattern for update strategy, for which we propose the finger-update model. In this model, updates are performed at the location of a finger that is only allowed to crawl on the tree between a child and a parent or between consecutive siblings. Under this model, we describe how the named extended operations are performed in worst-case constant time.Previous work on dynamic succinct trees (Munro et al., 2001 [17]; Raman and Rao, 2003 [19]) is mainly restricted to binary trees and achieves poly-logarithmic (Munro et al., 2001 [17]) or “poly-log-log” (Raman and Rao, 2003 [19]) update time under a more restricted model, where updates are performed in traversals starting at the root and ending at the root and queries can be answered when the traversal is completed. A previous result on ordinal trees achieves only sublinear amortized update time and “poly-log-log” query time (Gupta et al., 2007 [11]). More recently, the update time has been improved to O(logn/loglogn) while queries can be performed in O(logn/loglogn) time (Sadakane and Navarro, 2010 [20]).     

Relaxed Balance Using Standard Rotations

Abstract. In search trees with relaxed balance, rebalancing transformations need not be connected with updates, but may be delayed. For standard AVL tree rebalancing, we prove that even though the rebalancing operations are uncoupled from updates, their total number is bounded by O(M log (M+N)) , where M is the number of updates to an AVL tree of initial size N . Hence, relaxed balancing of AVL trees comes at no extra cost asymptotically. Furthermore, our scheme differs from most other relaxed balancing schemes in an important aspect: No rebalancing transformation can be done in the wrong direction, i.e., no performed rotation can make the tree less balanced. Moreover, each performed rotation indeed corresponds to a real imbalance situation in the tree. Finally, and perhaps most importantly, our structure is capable of forgetting registered imbalance if later updates happen to improve the situation. Our results are of theoretical interest and have possible sequential and parallel applications.     

Amortized constant relaxed rebalancing using standard rotations

The idea of relaxed balance is to uncouple the rebalancing in search trees from the updating in order to speed up request processing in main-memory databases. This paper defines the first relaxed binary search tree with amortized constant rebalancing using only standard single or double rotations. Received: 22 April 1997 / 21 April 1998     

Relaxed Balance Using Standard Rotations

Abstract. In search trees with relaxed balance, rebalancing transformations need not be connected with updates, but may be delayed. For standard AVL tree rebalancing, we prove that even though the rebalancing operations are uncoupled from updates, their total number is bounded by O(M log (M+N)) , where M is the number of updates to an AVL tree of initial size N . Hence, relaxed balancing of AVL trees comes at no extra cost asymptotically. Furthermore, our scheme differs from most other relaxed balancing schemes in an important aspect: No rebalancing transformation can be done in the wrong direction, i.e., no performed rotation can make the tree less balanced. Moreover, each performed rotation indeed corresponds to a real imbalance situation in the tree. Finally, and perhaps most importantly, our structure is capable of forgetting registered imbalance if later updates happen to improve the situation. Our results are of theoretical interest and have possible sequential and parallel applications.     

Updating a balanced search tree in O(1) rotations

Olivié has recently introduced the class of ‘half-balanced’ binary search trees, which have O(log n) access time but require only a constant number of single rotations for rebalancing after an insertion or a deletion. In this paper we show that a well-known class of balanced binary trees, the ‘symmetric binary B-trees’ of Bayer, have the same properties. This is not surprising, for Bayer's class and Oliviés class contain exactly the same binary trees.     

Decremental 2- and 3-connectivity on planar graphs

We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log² n) time. This givesO(log² n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.This work was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Project ALCOM II (contract No. 7141) and Project ASMICS. A preliminary version of this paper appears in [12].Partially supported by a CNR Fellowship. Work done while the author was visiting Columbia University.On leave from IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, USA.     

Adjacency queries in dynamic sparse graphs

We deal with the problem of maintaining a dynamic graph so that queries of the form “is there an edge between u and v?” are processed fast. We consider graphs of bounded arboricity, i.e., graphs with no dense subgraphs, like, for example, planar graphs. Brodal and Fagerberg [G.S. Brodal, R. Fagerberg, Dynamic representations of sparse graphs, in: Proc. 6th Internat. Workshop on Algorithms and Data Structures (WADS'99), in: Lecture Notes in Comput. Sci., vol. 1663, Springer, Berlin, 1999, pp. 342-351] described a very simple linear-size data structure which processes queries in constant worst-case time and performs insertions and deletions in O(1) and O(logn) amortized time, respectively. We show a complementary result that their data structure can be used to get O(logn) worst-case time for query, O(1) amortized time for insertions and O(1) worst-case time for deletions. Moreover, our analysis shows that by combining the data structure of Brodal and Fagerberg with efficient dictionaries one gets O(logloglogn) worst-case time bound for queries and deletions and O(logloglogn) amortized time for insertions, with size of the data structure still linear. This last result holds even for graphs of arboricity bounded by O(logkn), for some constant k.     

Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects

The data structure that is probably most used in the pattern recognition and image processing of geometric objects is the segment tree and its optimized variant, the “layered segment tree”. In all the versions currently known, except the work of Vaishnavi and Wood described later, these data structures do not operate in real time. Even in the latter scheme, although the structure can be implemented in real time and in an on-line fashion, the operation of insertion involves the sorting of the representations of the line segments in the tree. In essence, for all the reported algorithms, there is no known strategy to insert the segments one by one, other than the trivial strategy of processing them all together as in a batched-mode. In this paper, we present a strategy in which all the operations done on the tree can be done efficiently. Indeed, by improving the bottleneck, we prove that an arbitrary horizontal segment can be inserted into this data structure without invoking an expensive sorting process. We show that while this is accomplished by maintaining the same space and query complexity of the best-known algorithm, the version presented here is applicable to on-line real-time processing of line segments. The paper thus has applications in all areas of pattern recognition and image processing involving geometric objects.     

Rehabilitation of an unloved child: semi‐splaying

Splay trees are widely considered as the classic examples of self‐adjusting binary search trees and are part of most courses on data structures and algorithms. Already in the first seminal paper on splay trees (J. Assoc. Comput. Mach. 1985; 32(3):652–686) alternative operations were introduced, among which is semi‐splaying. On the one hand, the analysis of semi‐splaying gives a smaller constant for the amortized complexity, but on the other hand the authors write: Whether any version of semi‐splaying is an improvement over splaying depends on the access sequence. Semi‐splaying may be better when the access pattern is stable, but splaying adapts much faster to changes in usage. Maybe this sentence was the reason that nobody seriously ran tests to compare the performance of semi‐splaying and splaying. Semi‐splaying is conceptually simpler than splaying, has the same asymptotic amortized complexity and, as will be clear from empirical data presented in this paper, the practical performance is better for a very broad variety of access patterns. Therefore, its efficiency is a good reason to use semi‐splaying for applications instead of its more prominent brother. Moreover, its simplicity also makes it very attractive for teaching purposes. Copyright © 2008 John Wiley & Sons, Ltd.     

Dynamic Generation of Discrete Random Variates

We present and analyze efficient new algorithms for generating a random variate distributed according to a dynamically changing set of N weights. The base version of each algorithm generates the discrete random variate in O(log ^* N) expected time and updates a weight in O(2^{log^* N}) expected time in the worst case. We then show how to reduce the update time to O(log ^* N) amortized expected time. We finally show how to apply our techniques to a lookup-table technique in order to obtain expected constant time in the worst case for generation and update. We give parallel algorithms for parallel generation and update having optimal processor—time product. Besides the usual application in computer simulation, our method can be used to perform constant-time prediction in prefetching applications. We also apply our techniques to obtain an efficient dynamic algorithm for maintaining an approximate heap of N elements, in which each query is required to return an element whose value is within an ɛ multiplicative factor of the maximal element value. For ɛ= 1/polylog (N), each query, insertion, or deletion takes O(log log log N) time.     

A compact data structure for representing a dynamic multiset

We develop a data structure for maintaining a dynamic multiset that uses bits and O(1) words, in addition to the space required by the n elements stored, supports searches in worst-case time and updates in amortized time. Compared to earlier data structures, we improve the space requirements from O(n) bits to bits, but the running time of updates is amortized, not worst-case.     

Lower Bounds for Fully Dynamic Connectivity Problems in Graphs

We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of (log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems. Received January 1995; revised February 1997.     

Optimal point removal in closed-2PM labeling

An optimal labeling where labels are disjoint axis-parallel equal-size squares is called 2PM labeling if the labels have maximum length each attached to its corresponding point on the middle of one of its horizontal edges. In a closed-2PM labeling, no two edges of labels containing points should intersect. Removing one point and its label, makes free room for its adjacent labels and may cause a global label expansion. In this paper, we construct several data structures in the preprocessing stage, so that any point removal event is handled efficiently. We present an algorithm which decides in O(lgn) amortized time whether a label removal leads to label expansion in which case a new optimal labeling for the remaining points is generated in O(n) amortized time.     

Relaxed balance for search trees with local rebalancing

Search trees with relaxed balance were introduced with the aim of facilitating fast updating on shared-memory asynchronous parallel architectures. To obtain this, rebalancing has been uncoupled from the updating, so extensive locking in connection with updates is avoided. Rebalancing is taken care of by background processes, which do only a constant amount of work at a time before they release locks. Thus, the rebalancing and the associated locks are very localized in time as well as in space. In particular, there is no exclusive locking of whole paths. This means that the amount of parallelism possible is not limited by the height of the tree. Search trees with relaxed balance have been obtained by adapting standard sequential search trees to this new paradigm; clearly using similar techniques in each case, but no general result has been obtained. We show how any search tree with local bottom-up rebalancing can be used in a relaxed variant, preserving the complexity of the rebalancing from the sequential case. Additionally, we single out the one high level locking mechanism that a parallel implementation must provide in order to guarantee cons istency. Though the ideas have come from search trees, the result presented here applies to tree structures in general, where operations initiated at the leaves progress towards the root in constant-sized steps. Received: 10 September 1999 / 9 April 2001     

On-line algorithms for polynomially solvable satisfiability problems

Given a propositional Horn formula, we show how to maintain on-line information about its satisfiability during the insertion of new clauses. A data structure is presented which answers each satisfiability question in O(1) time and inserts a new clause of length q in O(q) amortized time. This significantly outperforms previously known solutions of the same problem. This result is extended also to a particular class of non-Horn formulae already considered in the literature, for which the space bound is improved. Other operations are considered, such as testing whether a given hypothesis is consistent with a satisfying interpretation of the given formula and determining a truth assignment which satisfies a given formula. The on-line time and space complexity of these operations is also analyzed.     

The relaxed min-max heap

A data structure that implements a mergeable double-ended priority queue, namely therelaxed min-max heap, is presented. A relaxed min-max heap ofn items can be constructed inO(n) time. In the worst case, operationsfind_min() andfind_max() can be performed in constant time, while each of the operationsmerge(),insert(),delete_min(),delete_max(),decrease_key(), anddelete_key() can be performed inO(logn) time. Moreover,insert() hasO(1) amortized running time. If lazy merging is used,merge() will also haveO(1) worst-case and amortized time. The relaxed min-max heap is the first data structure that achieves these bounds using only two pointers (puls one bit) per item.This research was carried out in summer 1991 when the author was with Florida International University     

Chromatic binary search trees

We propose a new rebalancing method for binary search trees that allows rebalancing and updating to be uncoupled. In this way we obtain fast updates and, whenever the search tree is accessed by multiple users, a high degree of concurrency. The trees we use are obtained by relaxing the balance conditions ofred-black trees. The relaxed red-black trees, calledchromatic trees, contain information of possible imbalance such that the rebalancing can be done gradually as a shadow process, or it can be performed separately when no urgent operations are present.     

Average-Case Analysis of Dynamic Graph Algorithms

We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., not random. We use our technique to analyze existing and new dynamic algorithms for the following problems: maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity, k -edge connectivity, k -vertex connectivity, and bipartiteness. Given a random graph G with m ₀ edges and n vertices and a sequence of l update operations such that the graph contains m _i edges after operation i , the expected time for performing the updates for any l is in the case of minimum spanning forests, connectivity, 2-edge connectivity, and bipartiteness. The expected time per update operation is O(n) in the case of maximum matching. We also give improved bounds for k -edge and k -vertex connectivity. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case O(n) amortized time per insertion. Received June 11, 1995; revised March 8, 1996.     

Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

Improved approximation of the largest common subtree of two unordered trees of bounded height

We present a polynomial time 1.5h-approximation algorithm for the problem of finding the largest common subtree between two rooted, labeled, and unordered trees of height at most h, where a tree S is called a subtree of a tree T if S is obtained from T by deletion of some nodes in T. This result improves the previous 2h-approximation algorithm.