ツリーの縮約

並列アルゴリズムの手法

コンピュータサイエンスにおいて、並列木縮約は、多数の木問題を並列に解くための広く適用可能な手法であり、多数の並列グラフアルゴリズムの設計のためのアルゴリズム設計手法として使用されています。並列木縮約は、 Gary L. MillerとJohn H. Reifによって導入され^[1]、その後、X. HeとY. Yesha、^[2]、Hillel Gazit、Gary L. Miller、Shang-Hua Teng ^[3]など多くの人々によって効率を向上させるために改良されてきました^[4]

ツリー収縮は、式の評価、最小共通祖先の探索、ツリー同型性、グラフ同型性、最大部分ツリー同型性、共通部分式の除去、グラフの3連結成分の計算、平面グラフの明示的な平面埋め込みの探索など、多くの効率的な並列アルゴリズムの設計に利用されてきた^[5]。

並列木縮約に関する研究と作業に基づき、このトピックの効率性や簡略性を向上させることを目的とした様々なアルゴリズムが提案されてきました。本稿では、ミラーとライフによるアルゴリズムの変種である特定の解決策とその応用に焦点を当てます。

はじめに

過去数十年にわたり、高度に並列（多重対数的深さ）で作業効率の高い（逐次実行時間が線形）アルゴリズムを設計することを目指し、様々な問題に対する新しい並列アルゴリズムを導出するための重要な研究が行われてきました。^[1]いくつかの問題では、木構造が優れた解決策となることが分かっています。これらの問題に対処するには、問題を木構造で表現するだけで、より多くの並列性を実現できる場合があります

木の一般的な定義を考えると、ルート頂点と、ルートに付随する複数の子頂点があります。^[6]そして、子頂点自体が子を持つ場合があり、以下同様に続きます。最終的に、パスは木の末端として定義される葉に到達します。次に、この一般的な木に基づいて、いくつかの特殊なケースを思いつくことができます。(1)平衡二分木、(2)連結リスト。^[7]平衡二分木は、葉を除いて各頂点に対してちょうど 2 つの枝を持ちます。これにより、木の深さに O(log n) の境界が与えられます。^{[8]連結リストも、すべての頂点が 1 つの子しか持たない木です。}対称性の破れを使用して O(log n) の深さを実現することもできます。^[9]

一般的なツリーの場合、不均衡であるかリスト状であるか、あるいはその両方の混合であるかに関係なく、境界を O(log n) に維持したいと考えています。この問題に対処するために、オイラー巡回技法^[10]を使用したプレフィックス和と呼ばれるアルゴリズムを使用します。オイラー巡回技法を使用すると、ツリーをフラットなスタイルで表現できるため、この形式の任意のツリーにプレフィックス和を適用できます。実際、プレフィックス和は、グループを形成する任意の値のセットと二項演算に使用できます。二項演算は結合的でなければならず、すべての値には逆があり、恒等値が存在します。

少し考えれば、プレフィックス和が不可能または非効率になる例外的なケースがいくつか見つかります。例えば、値の集合に0が含まれる場合の乗算を考えてみましょう。また、逆関数を持たないmax()やmin()といった、よく使われる演算もあります。目標は、すべての木に対して、期待されるO(n)の作業量とO(log n)の深さで動作するアルゴリズムを探すことです。以下のセクションでは、この目標を達成するためのRake/Compressアルゴリズムを提案します。^[11]

定義

アルゴリズム自体の説明に入る前に、まず後で使用するいくつかの用語を見てみましょう。

Rake ^[12] – Rakeステップは、バイナリノードのすべての左葉を親ノードに結合する。ここで言う結合とは、実行したい操作を実現する関数的な処理を実行することを意味する。Rakeの例を図1に示す。
圧縮^[12] – 圧縮ステップは実際には複数のイベントのシーケンスである。(1) 単項ノードの独立集合を見つける。(ここでの独立とは、2つのノードが隣接していないこと、つまり親子関係がないことを意味する) (2) 独立集合内の各ノードをその子ノードと結合する(独立集合は一意ではないことに注意)。圧縮の例を図2に示す。

そして、ツリー収縮を使用して実際の問題を解決するために、アルゴリズムは次のような構造を持ちます。

ツリーが単項ノードになるまで繰り返す
{
    レーキ
    圧縮
}

分析

ここでは、すべてのノードが3つ未満の子、つまり二分木を持つと仮定しよう。一般的に言えば、次数が有界である限り、この境界は成り立つ。^[13]しかし、ここでは簡単のために二分木の場合を分析する。上記の2つの「退化した」ケースでは、平衡二分木を扱うにはレーキが最適なツールであり、連結リストには圧縮が最適である。しかし、任意の木ではこれらの操作の組み合わせが必要となる。この組み合わせにより、我々は以下の定理を主張する。

定理: O(log n) 回の予想レーキおよび圧縮ステップの後、ツリーは単一のノードに縮小されます。

ここで、ツリー収縮アルゴリズムを次のように言い換えます。

入力: rを根とする二分木
出力: 単一ノード
操作: 一連の縮約ステップ。各ステップは、レーキ操作と圧縮操作（順序は任意）で構成されます。レーキ操作は、すべてのリーフノードを並列に削除します。圧縮操作は、独立した単項ノードの集合を見つけ、選択されたノードをスプライスします。

定理に近づくために、まず二分木の性質を見てみましょう。二分木Tが与えられたとき、Tのノードは3つのグループに分割できます。⁠ ⁠は $T_{0}$ すべての葉ノードを含み、⁠ ⁠ $T_{1}$ はすべての子ノードを1つ含み、⁠ ⁠ は $T_{2}$ すべての子ノードを2つ含みます。次の式から、次の式が成り立つことがわかります。そこで、次の式を提案します。 $V(T)=T_{0}\cup T_{1}\cup T_{2}$

主張： $|T_{0}|=|T_{2}|+1$

この主張は、ノード数に関する強い帰納法によって証明できます。n=1の基本ケースが自明に成り立つことは容易にわかります。さらに、この主張は最大でn個のノードを持つ任意の木にも成り立つと仮定します。すると、rを根とするn+1個のノードを持つ木が与えられた場合、次の2つのケースが考えられます

r に部分木が 1 つしかない場合、r の部分木を考えてみましょう。部分木には、木全体と同じ数のバイナリノードとリーフノードがあることが分かっています。これは、ルートが単項ノードであるためです。また、前述の仮定に基づくと、単項ノードは⁠ ⁠ $T_{0}$ も⁠ ⁠ $T_{2}$ も変化しません。
r に2つの部分木がある場合、それぞれ左部分木のリーフノードとバイナリノードを⁠ ⁠と定義します。同様に、右部分木についても同様の $T_{0}^{L},T_{2}^{L}$ ⁠ ⁠ $T_{0}^{R},T_{2}^{R}$ を定義します。前述のように、とが存在します。また、T にはリーフノードとバイナリノードがあることも分かっています。したがって、以下を導出できます。 $|T_{0}^{L}|=|T_{2}^{L}|+1$ $|T_{0}^{R}|=|T_{2}^{R}|+1$ $|T_{0}^{L}|+|T_{0}^{R}|$ $|T_{2}^{L}|+|T_{2}^{R}|+1$

|T_{0}^{L}|+|T_{0}^{R}|=|T_{2}^{L}|+1+|T_{2}^{R}|+1=(|T_{2}^{L}|+|T_{2}^{R}|+1)+1

それは主張を証明するものです。

この主張に従って、補題を証明し、定理を導きます。

補題: 縮小ステップ後のノードの数は、期待値の定数倍減少します。

縮約前のノード数をm、縮約後のノード数をm'と仮定します。定義により、rake操作はすべての⁠ ⁠ $T_{0}$ を削除し、compress操作は少なくとも⁠ ⁠ $T_{1}$ の1/4を削除します。すべての⁠ ⁠ $T_{2}$ が残ります。したがって、次の式が成り立ちます。

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

最後に、この補題に基づいて、各反復でノードが定数倍削減されると、⁠ ⁠ $O(\log n)$ 後には1つのノードだけが残ると結論付けることができます。^[14]

応用

式の評価

二分木（この問題は二分式木とも呼ばれます）として与えられた式を評価するには、^[15]で次の点を考慮してください。算術式とは、葉が何らかの定義域からの値を持ち、各内部頂点が2つの子と{+, x, %}からのラベルを持つ木です。さらに、これらの二分演算は定数時間で実行できると仮定します

ここでは、並列ツリー収縮によって評価を行うことができることを示す。^[16]

ステップ1. 各ノードに式を割り当てます。リーフの式とは、単にそのノードに含まれる値です。演算子はL + R、L − R、またはL × Rと書きます。ここで、LとRはそれぞれ左と右のサブツリーの式の値です。
ステップ 2. 子が 0 個ある左 (右) の子を演算子にマージする場合は、L (R) を子の値に置き換えます。
ステップ3. ノードに子が1つある場合、そのノードは1つの変数の関数である式を持ちます。子が1つある左（右）の子が演算子にマージされる場合は、L (R) を式に置き換え、式内の変数を必要に応じてL (R) に変更します。

2つの子ノードを持つノードでは、式のオペランドはf(L)とg(R)であり、fとgは線形関数である。1つの子ノードを持つノードでは、式はh(x)であり、hは線形関数で、xはLまたはRのいずれかである。この不変条件は帰納法によって証明する。最初は、不変条件は明らかに満たされている。完全に評価されない式になるマージには3つの種類がある。(1) 1子ノードが2子ノードにマージされる。(2) リーフが2子ノードにマージされる。(3) 1子ノードが1子ノードにマージされる。これら3種類のマージはいずれも不変条件を変更しない。したがって、すべてのマージは単に線形関数を評価または合成するだけで、定数時間かかる^[17]。

参考文献

^ ab ゲイリー・L・ミラー、ジョン・H・ライフ著、『並列ツリー収縮 - パートI：基礎』、1989年
^ X. HeとY. Yesha、「二分木代数計算と単純グラフの並列アルゴリズム」、Journal of Algorithms、1988年、92-113頁
^ Hillel Gazit、Gary L. Miller、Shang-Hua Teng、「EREWモデルにおける最適なツリー収縮」、Springer、1988
^ Karl Abrahamson他「単純な並列木縮約アルゴリズム^{[リンク切れ]}」Journal of Algorithms、1989年、287-302頁
^ John H. Reif と Stephen R. Tate、「動的並列ツリー収縮」、並列アルゴリズムとアーキテクチャに関する第 6 回 ACM シンポジウムの議事録 (ACM)、1994 年
^ Thomas H. Cormen、 Charles E. Leiserson、 Ronald L. Rivest、 Clifford Stein著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、2001年、 ISBN 0-262-03293-7セクション10.4：根付き木の表現、214～217ページ。第12章～14章（二分探索木、赤黒木、データ構造の拡張）、253～320ページ
^ ドナルド・クヌース著『コンピュータプログラミングの技法：基礎アルゴリズム』第3版、アディソン・ウェズレー、1997年、 ISBN 0-201-89683-4セクション2.3：木、308～423ページ
^ Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「第6章有界高さ木と木の深さ」、Sparsity: Graphs, Structures, and Algorithms 、Algorithms and Combinatorics、第28巻、ハイデルベルク：Springer、 115～ 144ページ、 doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058。
^ Andrew Goldberg、Serge Plotkin、Gregory Shannon、「疎グラフにおける並列対称性の破れ」、第19回ACMコンピューティング理論シンポジウム（ACM）の議事録、1987年
^ オイラーツアー木 - 高度なデータ構造の講義ノート。Erik Demaine教授、筆写者：Katherine Lai。
^ Gary L. MillerとJohn H. Reif、「並列ツリー収縮とその応用」、国防技術情報センター、1985年
^ ab 並列アルゴリズム：ツリー操作、ガイ・ブレロック、カーネギーメロン大学、2009年
^ 森畑明正、松崎公則、「非二分木における並列木縮約アルゴリズム」、数理工学技術報告、2008年
^ 並列アルゴリズム：並列ツリー収縮の分析、ガイ・ブレロック、2007年
^ S Buss, ブール式評価と木縮約アルゴリズム, 算術, 証明理論, 計算複雑性, 1993, pp. 96-115
^ Bader, David A.、Sukanya Sreshta、Nina R. Weisse-Bernstein、「ツリー収縮を使用した算術式の評価: 対称型マルチプロセッサ (SMP) 向けの高速かつスケーラブルな並列実装」^{[リンク切れ]}、High Performance Computing—HiPC 2002。Springer Berlin Heidelberg、2002 年、63-75 ページ。
^ 並列ツリー収縮の応用、サミュエル・ヨム、2015

外部リンク

6.851: エリック・ドゥメイン教授による高度なデータ構造

[Miller89book-1] ゲイリー・L・ミラー、ジョン・H・ライフ著、『並列ツリー収縮 - パートI：基礎』、1989年

[2] X. HeとY. Yesha、「二分木代数計算と単純グラフの並列アルゴリズム」、Journal of Algorithms、1988年、92-113頁

[3] Hillel Gazit、Gary L. Miller、Shang-Hua Teng、「EREWモデルにおける最適なツリー収縮」、Springer、1988

[4] Karl Abrahamson他「単純な並列木縮約アルゴリズム^{[リンク切れ]}」Journal of Algorithms、1989年、287-302頁

[Reif94dynamic-5] John H. Reif と Stephen R. Tate、「動的並列ツリー収縮」、並列アルゴリズムとアーキテクチャに関する第 6 回 ACM シンポジウムの議事録 (ACM)、1994 年

[6] Thomas H. Cormen、 Charles E. Leiserson、 Ronald L. Rivest、 Clifford Stein著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、2001年、 ISBN 0-262-03293-7セクション10.4：根付き木の表現、214～217ページ。第12章～14章（二分探索木、赤黒木、データ構造の拡張）、253～320ページ

[7] ドナルド・クヌース著『コンピュータプログラミングの技法：基礎アルゴリズム』第3版、アディソン・ウェズレー、1997年、 ISBN 0-201-89683-4セクション2.3：木、308～423ページ

[8] Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「第6章有界高さ木と木の深さ」、Sparsity: Graphs, Structures, and Algorithms 、Algorithms and Combinatorics、第28巻、ハイデルベルク：Springer、 115～ 144ページ、 doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058。

[9] Andrew Goldberg、Serge Plotkin、Gregory Shannon、「疎グラフにおける並列対称性の破れ」、第19回ACMコンピューティング理論シンポジウム（ACM）の議事録、1987年

[10] オイラーツアー木 - 高度なデータ構造の講義ノート。Erik Demaine教授、筆写者：Katherine Lai。

[Miller85app-11] Gary L. MillerとJohn H. Reif、「並列ツリー収縮とその応用」、国防技術情報センター、1985年

[cmutrees-12] 並列アルゴリズム：ツリー操作、ガイ・ブレロック、カーネギーメロン大学、2009年

[13] 森畑明正、松崎公則、「非二分木における並列木縮約アルゴリズム」、数理工学技術報告、2008年

[14] 並列アルゴリズム：並列ツリー収縮の分析、ガイ・ブレロック、2007年

[15] S Buss, ブール式評価と木縮約アルゴリズム, 算術, 証明理論, 計算複雑性, 1993, pp. 96-115

[16] Bader, David A.、Sukanya Sreshta、Nina R. Weisse-Bernstein、「ツリー収縮を使用した算術式の評価: 対称型マルチプロセッサ (SMP) 向けの高速かつスケーラブルな並列実装」^{[リンク切れ]}、High Performance Computing—HiPC 2002。Springer Berlin Heidelberg、2002 年、63-75 ページ。

[17] 並列ツリー収縮の応用、サミュエル・ヨム、2015