View source for Tree contraction

In [[Computer science|computer science]], '''parallel tree contraction''' is a broadly applicable technique for the parallel solution of a large number of [[Tree (graph theory)|tree]] problems, and is used as an algorithm design technique for the design of a large number of parallel [[Graph (discrete mathematics)|graph]] algorithms.  Parallel tree contraction was introduced by [[Biography:Gary Miller (computer scientist)|Gary L. Miller]] and John H. Reif,<ref name="Miller89book">Gary L. Miller and John H. Reif, Parallel Tree Contraction--Part I: Fundamentals., 1989</ref>  and has subsequently been modified to improve efficiency by X. He and Y. Yesha,<ref>X. He and Y. Yesha, "[https://www.sciencedirect.com/science/article/pii/0196677488900077 Binary tree algebraic computation and parallel algorithms for simple graphs].", Journal of Algorithms, 1988, pp 92-113</ref> Hillel Gazit, Gary L. Miller and Shang-Hua Teng<ref>Hillel Gazit, Gary L. Miller and Shang-Hua Teng, [https://link.springer.com/chapter/10.1007/978-1-4684-5511-3_9 Optimal tree contraction in the EREW model], Springer, 1988</ref> and many others.<ref>Karl Abrahamson and et al., "[http://www.academia.edu/download/45795098/0196-6774_2889_2990017-520160519-30523-rbfq65.pdf A simple parallel tree contraction algorithm]{{dead link|date=July 2022|bot=medic}}{{cbignore|bot=medic}}.", Journal of Algorithms, 1989, pp 287-302</ref>
Tree contraction has been used in designing many efficient parallel algorithms, including [[Expression (mathematics)|expression]] evaluation, finding [[Lowest common ancestor|lowest common ancestors]], tree isomorphism, [[Graph isomorphism|graph isomorphism]], maximal subtree isomorphism, [[Common subexpression elimination|common subexpression elimination]], computing the 3-connected components of a graph, and finding an explicit planar embedding of a [[Planar graph|planar graph]]<ref name="Reif94dynamic">John H. Reif and Stephen R. Tate, [https://users.cs.duke.edu/~reif/paper/tate/dyntree/dyntree.pdf Dynamic parallel tree contraction], Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures (ACM), 1994</ref>

Based on the research and work on parallel tree contraction, various algorithms have been proposed targeting to improve the efficiency or simplicity of this topic. This article hereby focuses on a particular solution, which is a variant of the algorithm by Miller and Reif, and its application.

==Introduction==
Over the past several decades there has been significant research on deriving new parallel algorithms for a variety of problems, with the goal of designing highly parallel (polylogarithmic depth), work-efficient (linear in the sequential running time) algorithms.<ref name="Miller89book" /> For some problems, tree turns out to be a nice solution. Addressing these problems, we can sometimes get more parallelism simply by representing our problem as a tree.

Considering a generic definition of a tree, there is a root vertex, and several child vertices attached to the root.<ref>[[Biography:Thomas H. Cormen|Thomas H. Cormen]], [[Biography:Charles E. Leiserson|Charles E. Leiserson]], Ronald L. Rivest, and [[Biography:Clifford Stein|Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7}} . Section 10.4: Representing rooted trees, pp.&nbsp;214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp.&nbsp;253–320.</ref> And the child vertices might have children themselves, and so on so forth. Eventually, the paths come down to leaves, which are defined to be the terminal of a tree. Then based on this generic tree, we can further come up with some special cases: (1) balanced binary tree; (2) linked list.<ref>[[Biography:Donald Knuth|Donald Knuth]]. ''[[The Art of Computer Programming]]: Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89683-4}} . Section 2.3: Trees, pp.&nbsp;308–423.</ref> A balanced binary tree has exactly two branches for each vertex except for leaves. This gives a O(log n) bound on the depth of the tree.<ref>{{citation
 | contribution = Chapter 6. Bounded height trees and tree-depth
 | doi = 10.1007/978-3-642-27875-4
 | isbn = 978-3-642-27874-7
 | location = Heidelberg
 | mr = 2920058
 | pages = 115–144
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Sparsity: Graphs, Structures, and Algorithms
 | volume = 28
 | year = 2012 }}.</ref> A linked list is also a tree where every vertex has only one child. We can also achieve O(log n) depth using [[Symmetry breaking|symmetry breaking]].<ref>Andrew Goldberg, Serge Plotkin, and Gregory Shannon, [https://apps.dtic.mil/dtic/tr/fulltext/u2/a198233.pdf Parallel symmetry-breaking in sparse graphs], Proceedings of the nineteenth annual ACM symposium on Theory of computing (ACM), 1987</ref>

Given the general case of a tree, we would like to keep the bound at O(log n) no matter it is unbalanced or list-like or a mix of both. To address this problem, we make use of an algorithm called [[Prefix sum|prefix sum]] by using the [[Euler tour technique]].<ref>[http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf Euler tour trees] - in Lecture Notes in Advanced Data Structures. Prof. Erik Demaine; Scribe: Katherine Lai.</ref> With the Euler tour technique, a tree could be represented in a flat style, and thus prefix sum could be applied to an arbitrary tree in this format. In fact, prefix sum can be used on any set of values and binary operation which form a group: the binary operation must be associative, every value must have an inverse, and there exists an identity value.

With a bit of thought, we can find some exceptional cases where prefix sum becomes incapable or inefficient. Consider the example of multiplication when the set of values includes 0. Or there are some commonly desired operations are max() and min() which do not have inverses. The goal is to seek an algorithm which works on all trees, in expected O(n) work and O(log n) depth. In the following sections, a Rake/Compress algorithm will be proposed to fulfill this goal.<ref name="Miller85app">Gary L. Miller and John H. Reif, [https://apps.dtic.mil/dtic/tr/fulltext/u2/a171219.pdf Parallel tree contraction and its application], Defense Technical Information Center, 1985</ref>

==Definitions==

[[File:Rake-1.png|480x360px|thumbnail|right|Fig. 1: Rake Operation]]
[[File:Compress-1.png|480x360px|thumbnail|right|Fig. 2: Compress Operation]]
Before going into the algorithm itself, we first look at a few terminologies that will be used later.

* '''Rake'''<ref name="cmutrees">[https://www.cs.cmu.edu/afs/cs/academic/class/15499-s09/www/scribe/lec11/lec11.pdf Parallel Algorithms: Tree Operations], Guy Blelloch, Carnegie Mellon University, 2009</ref> – Rake step joins every left leaf of binary nodes to the parent. By join, we mean that it undergoes a functional process which achieves the operation we want to make. An example of rake is given in Figure 1.
* '''Compress'''<ref name="cmutrees" /> – Compress step is actually a sequence of several events: (1) Find an independent set of unary nodes. (Independence here is defined such that no two are neighbors, meaning no parent to child relation) (2) Join each node in independent set with its child (Note that independent set is not unique). An example of compress is given in Figure 2.

And in order to solve actual problems using tree contraction, the algorithm has a structure:

<pre>
Repeat until tree becomes a unary node
{
    Rake;
    Compress;
}
</pre>


==Analysis==
For the moment, let us assume that all nodes have less than three children, namely binary. Generally speaking, as long as the degree is bounded, the bounds will hold.<ref>MORIHATA, Akimasa, and Kiminori MATSUZAKI, [https://www.researchgate.net/profile/Kiminori_Matsuzaki/publication/242467141_MATHEMATICAL_ENGINEERING_TECHNICAL_REPORTS_A_Parallel_Tree_Contraction_Algorithm_on_Non-Binary_Trees/links/5513ed230cf2eda0df30336f/MATHEMATICAL-ENGINEERING-TECHNICAL-REPORTS-A-Parallel-Tree-Contraction-Algorithm-on-Non-Binary-Trees.pdf A Parallel Tree Contraction Algorithm on Non-Binary Trees], MATHEMATICAL ENGINEERING
TECHNICAL REPORTS, 2008</ref> But we will analyze the binary case for simplicity. In the two “degenerate” cases listed above, the rake is the best tool for dealing with balanced binary trees, and compress is the best for linked lists. However, arbitrary trees will have to require a combination of these operations. By this combination, we claim a theorem that
* '''Theorem''': After O(log n) expected rake and compress steps, a tree is reduced to a single node.
Now rephrase the tree contraction algorithm as follows:
* Input: A binary tree rooted at r
* Output: A single node
* Operation:  A sequence of contraction steps, each consisting of a rake operation and a compress operation (in any order). The rake operation removes all the leaf nodes in parallel. The compress operation finds an [[Independent set (graph theory)|independent set]] of unary nodes and splice out the selected nodes.
To approach the theorem, we first take a look at a property of a binary tree. Given a binary tree T, we can partition the nodes of T into 3 groups: {{tmath|T_0}} contains all leaf nodes, {{tmath|T_1}} contains all nodes with 1 child, and {{tmath|T_2}} contains all nodes with 2 children. It is easy to see that: <math>V(T) = T_0  \cup T_1 \cup T_2</math>. Now we propose:
* Claim: <math>|T_0| = |T_2|  + 1</math>
This claim can be proved by strong induction on the number of nodes. It is easy to see that the base case of n=1 trivially holds. And we further assume the claim also holds for any tree with at most n nodes. Then given a tree with n+1 nodes rooted at r, there appears to be two cases:
# If r has only one subtree, consider the subtree of r. We know that the subtree has the same number of binary nodes and the same number of leaf nodes as the whole tree itself. This is true since the root is a unary node. And based the previous assumption, a unary node does not change either {{tmath|T_0}} or {{tmath|T_2}}.
# If r has two subtrees, we define {{tmath|T_0^L, T_2^L}} to be the leaf nodes and binary nodes in the left subtree, respectively. Similarly, we define the same {{tmath|T_0^R, T_2^R}} for the right subtree. From previous, there is <math>|T_0^L| = |T_2^L| + 1</math> and <math>|T_0^R| = |T_2^R| + 1</math>. Also we know that T has <math>|T_0^L| + |T_0^R|</math> leaf nodes and <math>|T_2^L| + |T_2^R| + 1</math> binary nodes. Thus, we can derive:

:<math>|T_0^L| + |T_0^R| = |T_2^L| + 1 + |T_2^R| + 1 = (|T_2^L| + |T_2^R| + 1) + 1</math>

which proves the claim.

Following the claim, we then prove a lemma, which leads us to the theorem.
* Lemma: The number of nodes of after a contraction step is reduced by a constant factor in expectation.
Assume the number of nodes before the contraction to be m, and m' after the contraction. By definition, the rake operation deletes all {{tmath|T_0}} and the compress operation deletes at least 1/4 of {{tmath|T_1}} in expectation. All {{tmath|T_2}} remains. Therefore, we can see:

:<math>E[m'] \leq |T_2| + \tfrac{3}{4}*|T_1| \leq \tfrac{3}{4} + \tfrac{3}{4}*|T_1| + \tfrac{3}{2}*|T_2| = \tfrac{3}{4}(1 + |T_1| + 2*|T_2|) = \tfrac{3}{4}(|T_0| + |T_1| + |T_2|) = \tfrac{3}{4}m</math>

Finally, based on this lemma, we can conclude that if the nodes are reduced by a constant factor in each iteration, after {{tmath|O(\log n)}}, there will be only one node left.<ref>[https://www.cs.cmu.edu/afs/cs/academic/class/15492-f07/www/scribe/lec9/lecture9.pdf Parallel Algorithms: Analyzing Parallel Tree Contraction], Guy Blelloch, 2007</ref>

==Applications==

===Expression Evaluation===
To evaluate an expression given as a binary tree (this problem also known as [[Binary expression tree|binary expression tree]]),<ref>S Buss, [https://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean3/paper.pdf Algorithms for boolean formula evaluation and for tree contraction], Arithmetic, Proof Theory, and Computational Complexity, 1993, pp. 96-115</ref> consider that:
An arithmetic expression is a tree where the leaves have values from some domain and each internal vertex has two children and a label from {+, x, %}. And further assume that these binary operations can be performed in constant time.

We now show the evaluation can be done with parallel tree contraction.<ref>Bader, David A., Sukanya Sreshta, and Nina R. Weisse-Bernstein, [http://www.academia.edu/download/14538/2g8zid9t1h19jif8w63n.pdf Evaluating arithmetic expressions using tree contraction: A fast and scalable parallel implementation for symmetric multiprocessors (SMPs)]{{dead link|date=July 2022|bot=medic}}{{cbignore|bot=medic}}, High Performance Computing—HiPC 2002. Springer Berlin Heidelberg, 2002, pp. 63-75.</ref>
* Step 1. Assign expressions to every node. The expression of a leaf is simply the value that it contains. Write L + R, L − R, or L × R for the operators, where L and R are the values of the expressions in the left and right subtrees, respectively.
* Step 2. When a left (right) child with 0 children is merged into an operator, replace L (R) with the value of the child.
* Step 3. When a node has 1 child, it has an expression that is a function of one variable. When a left (right) child with 1 child is merged into an operator, replace L (R) with the expression and change the variable in the expression to L (R) if appropriate.

In a node with 2 children, the operands in the expression are f(L) and g(R), where f and g are linear functions, and in a node with 1 child, the expression is h(x), where h is a linear function and x is either L or R. We prove this invariant by induction. At the beginning, the invariant is clearly satisfied. There are three types of merges that result in a not fully evaluated expression. (1) A 1-child node is merged into a 2-children node. (2) A leaf is merged into a 2-children node. (3) A 1-child node is merged into a 1-child node. All three types of merges do not change the invariant. Therefore, every merge simply evaluates or composes linear functions, which takes constant time <ref>[http://math.mit.edu/~rpeng/18434/applicationsParallelTreeContraction.pdf Applications of Parallel Tree Contraction], Samuel Yeom, 2015</ref>

==References==
{{Reflist}}
{{refbegin}}
{{refend}}

==External links==
* [http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf 6.851: Advanced Data Structures] by Prof. Erik Demaine

{{CS-Trees}}

[[Category:Parallel computing]]
[[Category:Trees (data structures)]]
de:Baum (Graphentheorie)

{{Sourceattribution|Tree contraction}}