An example of simplicial complex, and the corresponding simplex tree data structure. Notice the two lowest nodes have a path of 4 to the node, indicating the 2 3-dimensional simplexes composed of 4 vertices each.

In topological data analysis, a simplex tree is a type of trie used to represent efficiently any general simplicial complex. Through its nodes, this data structure notably explicitly represents all the simplices. Its flexible structure allows implementation of many basic operations useful to computing persistent homology. This data structure was invented by Jean-Daniel Boissonnat and Clément Maria in 2014, in the article The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes.^[1] This data structure offers efficient operations on sparse simplicial complexes. For dense or maximal simplices, Skeleton-Blocker^[2] representations or Toplex Map^[3] representations are used.

Definitions

Many researchers in topological data analysis consider the simplex tree to be the most compact simplex-based data structure for simplicial complexes, and a data structure allowing an intuitive understanding of simplicial complexes due to integrated usage of their mathematical properties.^[1][3][4]

Operations

While simplex trees are not the most space efficient data structures for simplicial complex representation, their operations on sparse data are considered state-of-art. Here, we give the bounds of different useful operations possible through this representation. Many implementations of these operations are available.^{[1][4][5][6][7]}

We first introduce the notation. Consider ${\displaystyle s}$ is a given simplex, ${\displaystyle \sigma }$ is a given node corresponding to the last vertex of ${\displaystyle s}$, ${\displaystyle l}$ is the label associate to that node, ${\displaystyle j}$ is the depth of that node, ${\displaystyle k}$ is the dimension of the simplicial complex, ${\displaystyle D_{\sigma }}$ is the maximal number of operations to access ${\displaystyle \sigma }$ in a dictionary (if the dictionary is a red-black tree, ${\displaystyle D_{\sigma }=O(log(deg(\sigma )))}$ is the complexity) . Consider ${\displaystyle C_{s}}$ is the number of cofaces of ${\displaystyle s}$, and ${\displaystyle N_{l}^{>j}}$ is the number of nodes of the simplex tree ending with the label ${\displaystyle l}$ at depth greater than ${\displaystyle j}$. Notice ${\displaystyle N_{l}^{>j}\leq C_{s}}$.

1. Search, insert and remove words are done in ${\displaystyle O(jD_{\sigma })}$.^[1]
2. Insert and remove an entire simplex is done in ${\displaystyle O(2^{j}D_{\sigma })}$.^[1]
3. Computing persistent homology, or in a more involved way, computing Betti numbers, using a simplex tree most efficiently remains an open problem, however, current algorithms for this task on sparse simplicial complexes achieve state-of-art performance.^[4]
4. The structure of simplex trees allows for elementary collapse of collapsible simplexes, however the bounds of this operation in the general case are unknown.^[1][5][7]
5. A subcase of elementary collapse is edge-contraction. Edge contraction can be

achieved in ${\displaystyle O(kN_{l}^{>j}+C_{s}D_{\sigma })}$.^[1]

1. Locating cofaces of given simplex can be achieved in ${\displaystyle O(kN_{l}^{>j})}$.^[1]
2. Locating cofacets of given simplex can be achieved in ${\displaystyle O(j^{2}D_{\sigma })}$.^[1]

As for construction, as seeing in the constructive definition, construction is proportional to the number and complexity of simplexes in the simplicial complex. This can be especially expensive if the simplicial complex is dense. However, some optimizations for particular simplicial complexes, including for Flag complexes, Rips complexes and Witness complexes.^[1][8]

Applications

Simplex tree are efficient in sparse simplicial complexes. For this purpose, many persistent homology algorithms focusing on high-dimensional real data (often sparse) use simplex trees within these algorithms. While simplex trees are not as efficient as incidence matrix, their simplex-based structure allows them to be useful efficient for simplicial complex storage within persistent homology algorithms.^[9]

References