重要なデータ構造である木の並列計算機上での処理を考える。ノード間の リンクによる素朴な内部表現に基づく既存のアプローチでは、現代のコンピュー タアーキテクチャのキャッシュ機構にうまく適合しないなどの理由により実用的 な性能が得られにくかった。本論文では木構造を整列化したものを内部表現とし て用いることで導ける、より効率的な木の並列縮約アルゴリズムを2つ提案して いる。1つ目はリスト準同型のアプローチ[2]から自然に導かれるものであり、良 好なスケーラビリティを示すものの計算量が木の深さに依存してしまう。2つ目 は縮約の演算について追加の条件を加えた上で導かれるものであり、計算量は木 の深さに非依存である。

[1]]K. Kakehi, K. Matsuzaki, K. Emoto, and Z. Hu. An Practicable Framework for Tree Reductions under Distributed Memory Environments. Technical Report METR 2006-64, Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, December 2006.
[2]S. Gorlatch. Constructing List Homomorphisms. Technical Report MIP-9512, Fakult?t f?r Informatik und Mathematik, Universit?t Passau, August 1995.