シンプレックスツリー

上部は、2つの正四面体、1つの三角形、1つの線、および1つの点から構成され、緩やかに接続されている。下部は、対応する単体木である。 — 単体複体の例と、それに対応する単体木データ構造を示します。最も低い2つのノードは、ノードへのパスが4であることに注目してください。これは、それぞれ4つの頂点からなる2つの3次元単体を示しています。

トポロジカルデータ解析では、シンプレックスツリーは、任意の一般的な単体複体を効率的に表現するために使用されるトライ木の一種です。このデータ構造は、そのノードを通じて、特にすべての単体を明示的に表現します。その柔軟な構造により、パーシステントホモロジーの計算に役立つ多くの基本操作を実装できます。このデータ構造は、2014 年に Jean-Daniel Boissonnat と Clément Maria によって、論文「The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes」で考案されました。^[¹^]このデータ構造は、疎な単体複体に対して効率的な操作を提供します。密な単体または最大単体には、Skeleton-Blocker ^[²^]表現または Toplex Map ^[³^]表現が使用されます。

定義

トポロジカルデータ解析の多くの研究者は、単体木を単体複体のための最もコンパクトな単体ベースのデータ構造であり、その数学的性質を統合的に使用することで単体複体を直感的に理解できるデータ構造であると考えている。^{[ 1 ]}^{[ 3 ]}^{[ 4 ]}

ヒューリスティック定義

任意の単体複体は、位相空間内の点（0次元）、線分（1次元）、三角形（2次元）、およびそれらのn次元対応物（n単体と呼ばれる）から構成される集合であると考える。単体の数学的性質により、任意のn単体は複数の $(n-1)$ n-単体。したがって、線は点、三角形は線、四面体は三角形で構成されます。上位レベルごとに、n-単体の頂点に 1 つの頂点が追加されることに注意してください。データ構造は単体ベースであるため、単体を定義する点によってすべての単体を一意に表現する必要があります。これを実現する簡単な方法は、各単体をその点によってソートされた順序で定義することです。

させて $\mathrm {K}$ k次元の単体複体である。 $V$ その頂点集合、頂点は1から $\left\vert V\right\vert$ そしてそれに応じて順序付けします。次に、辞書のサイズを構築します $\left\vert V\right\vert$ すべての頂点ラベルを順番に含む。これは 0 次元単体を表す。次に、初期辞書の各エントリの初期辞書へのパスに対して、現在の頂点セットに完全接続されているすべての頂点を子辞書として追加する。これらの頂点はすべて、ラベルがより大きい。 $l$ このステップをkレベルで表現します。明らかに、最初の辞書を深さ0とすると、深さのエントリは $\displaystyle \tau }$ このデータ構造内のどの辞書も一意に表現します $\displaystyle \tau }$ -単体内 $\mathrm {K}$ 完全性を保つため、初期辞書へのポインタは空の単体の表現とみなされます。操作の実用性を考慮して、同じレベルで繰り返されるラベルはリンクされ、ループされたリンクリストを形成します。最後に、子辞書には、祖先への高速アクセスを可能にする親辞書へのポインタも含まれています。^{[ 1 ]}

構成的定義

させて $\mathrm {K}$ k次元の単体複体とする。まず、単体複体を互いに排他的な単体に分解する。これは、単体複体が空になるまで、単体複体から最高次の単体を繰り返し取り除くという貪欲法で実現できる。次に、各頂点に1から番号を付ける必要がある。 $\left\vert V\right\vert$ そして、各単体を対応する「単語」、つまりラベルによる頂点の順序付きリストに関連付けます。ラベルを順序付けすることで、単体を記述する方法は1つしかないため、単体ツリーに重複がないことを保証します。まず、ヌル単体を表すヌルルートから始めます。次に、すべての単体と、各単体単語の各ラベルを順に処理します。ラベルが現在のルートの子として利用可能な場合は、その子を挿入プロセスの一時的なルートにします。そうでない場合は、子用に新しいノードを作成し、それを新しい一時的なルートにして、単語の残りの処理を続けます。この処理中、k個の辞書がすべてのラベルとともに維持され、対応するラベルのノードのアドレスが挿入されます。辞書のその場所にアドレスが既に存在する場合は、古いノードから新しいノードへのポインタが作成されます。処理が完了すると、各ノードのすべての子が辞書に入力され、すべてのポインタがループしてループされたリンクリストが作成されます。ここではハッシュテーブルなど、さまざまな辞書を適用できますが、一部の操作ではエントリの順序付き走査の可能性を前提としているため、ほとんどの実装では赤黒木または辞書を使用します。^{[ 1 ]}

業務

単体木は単体複素数表現のための最もスペース効率の良いデータ構造ではありませんが、疎データに対するその操作は最先端であると考えられています。ここでは、この表現を通して可能なさまざまな有用な操作の境界を示します。これらの操作の多くの実装が利用可能です。^{[ 1 ]}^{[ 4 ]}^{[ 5 ]}^{[ 6 ]}^{[ 7 ]}

まず、表記法を導入します。 $s$ は与えられた単体であり、 $\sigma$ は、最後の頂点に対応する与えられたノードです。 $s$ 、 $l$ そのノードに関連付けられたラベルは、 $j$ これはそのノードの深さです。 $k$ は単体複体の次元であり、 $D_{\sigma }$ アクセスする操作の最大数 $\sigma$ 辞書では（辞書が赤黒木である場合、 $D_{\sigma }=O(log(deg(\sigma )))$ （複雑さ）を考えてみましょう。 $C_{s}$ は、 $s$ 、そして $N_{l}^{>j}$ は、ラベルで終わる単体木のノードの数です。 $l$ より深い場所で $j$ 。知らせ $N_{l}^{>j}\leq C_{s}$ 。

検索、挿入、削除は $O(jD_{\sigma })$ [ ¹^]
単体全体を挿入および削除するには、 $O(2^{j}D_{\sigma })$ [ ¹^]
パーシステントホモロジーを計算すること、あるいはより複雑な方法でベッチ数を計算することを、単体木を最も効率的に使用することは未解決の問題であるが、疎な単体複体に対するこのタスクの現在のアルゴリズムは最先端のパフォーマンスを達成している。^{[ 4 ]}
単体木構造により、折りたたみ可能な単体の基本的折りたたみが可能になりますが、一般の場合のこの操作の境界は不明です。^{[ 1 ]}^{[ 5 ]}^{[ 7 ]}
基本的な崩壊のサブケースはエッジ収縮である。エッジ収縮は

達成 $O(kN_{l}^{>j}+C_{s}D_{\sigma })$ [ ¹^]

与えられた単体の共面の位置を特定するには、 $O(kN_{l}^{>j})$ [ ¹^]
与えられた単体の共面の位置を特定するには、 $O(j^{2}D_{\sigma })$ [ ¹^]

構成に関しては、構成的定義に見られるように、構成は単体複体の単体の数と複雑さに比例します。単体複体が密である場合は、特にコストがかかる可能性があります。ただし、フラグ複体、リップス複体、ウィットネス複体などの特定の単体複体に対する最適化がいくつかあります。^{[ 1 ]}^{[ 8 ]}

アプリケーション

単体木は疎な単体複体において効率的です。この目的のために、高次元実データ（多くの場合疎）に焦点を当てた多くのパーシステントホモロジーアルゴリズムでは、これらのアルゴリズム内で単体木を使用しています。単体木は接続行列ほど効率的ではありませんが、単体ベースの構造により、パーシステントホモロジーアルゴリズム内で単体複体の格納に有用かつ効率的です。^{[ 9 ]}

参考文献

1 2 3 4 5 6 7 8 9 10 11 12 Boissonnat , Jean-Daniel; Maria, Clément (2014 年 11 月). "The Simplex Tree: an Efficient Data Structure for General Simplicial Complexes". Algorithmica . 70 (3): 406– 427. arXiv : 2001.02581 . doi : 10.1007/s00453-014-9887-3 . ISSN 0178-4617 . S2CID 15335393 .
↑サリナス、デイビッド（2020年2月7日）。「スケルトンブロッカー」。高次元における幾何学の理解。 2021年12月9日取得。
1 2 Godi, Francois (2020年2月7日). "Toplex Map" . Geometry Understanding in Higher Dimensions . 2021年12月9日取得。
1 2 3ボワソナ、ジャン＝ダニエル。「単体木リファレンスマニュアル」。高次元における幾何学の理解。 2021年12月9日取得。
1 2マット・ピーケンブロック（2020年9月13日）。"simplex_tree: シンプレックスツリー"。rdrr.io 。2021 年12 月 9 日に取得。
↑ナンダ、ヴィディット。「パーシステントホモロジーソフトウェア、Perseus」。パーシステントホモロジーの高速計算のためのPerseusソフトウェアプロジェクト。 2021年12月9日取得。
1 2モロゾフ、ドミトリー (2019)。「基本」。ディオニュソス 2。2021年12 月 9 日に取得。
↑モロゾフ、ドミトリー (2019)。「ヴィエトリス・リップス複合体」。ディオニュソス 2 ．2021 年12 月 9 日に取得。
↑ Mandal, Sayan (2020). "Applications of Persistent Homology and Cycles" .オハイオ州立大学. 博士論文.

[:0-1] 1 2 3 4 5 6 7 8 9 10 11 12 Boissonnat , Jean-Daniel; Maria, Clément (2014 年 11 月). "The Simplex Tree: an Efficient Data Structure for General Simplicial Complexes". Algorithmica . 70 (3): 406– 427. arXiv : 2001.02581 . doi : 10.1007/s00453-014-9887-3 . ISSN 0178-4617 . S2CID 15335393 .

[2] サリナス、デイビッド（2020年2月7日）。「スケルトンブロッカー」。高次元における幾何学の理解。 2021年12月9日取得。

[:1-3] 1 2 Godi, Francois (2020年2月7日). "Toplex Map" . Geometry Understanding in Higher Dimensions . 2021年12月9日取得。

[:2-4] 1 2 3ボワソナ、ジャン＝ダニエル。「単体木リファレンスマニュアル」。高次元における幾何学の理解。 2021年12月9日取得。

[:3-5] 1 2マット・ピーケンブロック（2020年9月13日）。"simplex_tree: シンプレックスツリー"。rdrr.io 。2021 年12 月 9 日に取得。

[6] ナンダ、ヴィディット。「パーシステントホモロジーソフトウェア、Perseus」。パーシステントホモロジーの高速計算のためのPerseusソフトウェアプロジェクト。 2021年12月9日取得。

[:4-7] 1 2モロゾフ、ドミトリー (2019)。「基本」。ディオニュソス 2。2021年12 月 9 日に取得。

[8] モロゾフ、ドミトリー (2019)。「ヴィエトリス・リップス複合体」。ディオニュソス 2 ．2021 年12 月 9 日に取得。

[9] Mandal, Sayan (2020). "Applications of Persistent Homology and Cycles" .オハイオ州立大学. 博士論文.

[

[ 6 ]

[ 8 ]

[ 9 ]