Árbol simplex

En el análisis topológico de datos , un árbol simplex es un tipo de trie que se utiliza para representar de forma eficiente cualquier complejo simplicial general . A través de sus nodos, esta estructura de datos representa explícitamente todos los símplices. Su estructura flexible permite la implementación de muchas operaciones básicas útiles para el cálculo de la homología persistente . Esta estructura de datos fue inventada por Jean-Daniel Boissonnat y Clément Maria en 2014, en el artículo «The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes» ^{[ 1 ]} . Esta estructura de datos ofrece operaciones eficientes sobre complejos simpliciales dispersos. Para símplices densos o máximos, se utilizan representaciones Skeleton-Blocker ^{[ 2 ]} o Toplex Map ^{[ 3 ] .}

Muchos investigadores en análisis topológico de datos consideran que el árbol simplex es la estructura de datos basada en simplex más compacta para complejos simpliciales, y una estructura de datos que permite una comprensión intuitiva de los complejos simpliciales debido al uso integrado de sus propiedades matemáticas. ^{[ 1 ] [ 3 ] [ 4 ]}

Si bien los árboles simplex no son las estructuras de datos más eficientes en cuanto a espacio para la representación de complejos simpliciales, sus operaciones con datos dispersos se consideran de vanguardia. Aquí, presentamos los límites de diferentes operaciones útiles posibles mediante esta representación. Existen numerosas implementaciones de estas operaciones. ^{[ 1 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ]}

Primero introducimos la notación. Consideremos${\displaystyle s}$es un simplex dado,${\displaystyle \sigma }$es un nodo dado que corresponde al último vértice de${\displaystyle s}$,${\displaystyle l}$es la etiqueta asociada a ese nodo,${\displaystyle j}$es la profundidad de ese nodo,${\displaystyle k}$es la dimensión del complejo simplicial,${\displaystyle D_{\sigma }}$es el número máximo de operaciones a acceder${\displaystyle \sigma }$en un diccionario (si el diccionario es un árbol rojo-negro,${\displaystyle D_{\sigma }=O(log(deg(\sigma )))}$es la complejidad). Considere${\displaystyle C_{s}}$es el número de co-caras de${\displaystyle s}$, y${\displaystyle N_{l}^{>j}}$es el número de nodos del árbol simplex que termina con la etiqueta${\displaystyle l}$a una profundidad mayor que${\displaystyle j}$. Aviso${\displaystyle N_{l}^{>j}\leq C_{s}}$.

1. La búsqueda , inserción y eliminación de palabras se realizan en${\displaystyle O(jD_{\sigma })}$. ^{[ 1 ]}
2. La inserción y extracción de un simplex completo se realiza en${\displaystyle O(2^{j}D_{\sigma })}$. ^{[ 1 ]}
3. El cálculo de la homología persistente , o de una manera más compleja, el cálculo de los números de Betti , utilizando un árbol simplex de la forma más eficiente, sigue siendo un problema abierto; sin embargo, los algoritmos actuales para esta tarea en complejos simpliciales dispersos alcanzan un rendimiento de vanguardia. ^{[ 4 ]}
4. La estructura de los árboles simplex permite el colapso elemental de los símplices colapsables; sin embargo, se desconocen los límites de esta operación en el caso general. ^{[ 1 ] [ 5 ] [ 7 ]}
5. Un subcaso del colapso elemental es la contracción de aristas . La contracción de aristas puede ser

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

1. La localización de co-caras de un simplex dado se puede lograr en${\displaystyle O(kN_{l}^{>j})}$. ^{[ 1 ]}
2. La localización de cofacetas de un simplex dado se puede lograr en${\displaystyle O(j^{2}D_{\sigma })}$. ^{[ 1 ]}

En cuanto a la construcción, como se observa en la definición constructiva, la construcción es proporcional al número y la complejidad de los símplices en el complejo simplicial. Esto puede resultar especialmente costoso si el complejo simplicial es denso. Sin embargo, existen algunas optimizaciones para complejos simpliciales particulares, incluidos los complejos Flag , Rips y Witness. ^{[ 1 ] [ 8 ]}

Los árboles simplex son eficientes en complejos simpliciales dispersos. Por ello, muchos algoritmos de homología persistente que se centran en datos reales de alta dimensión (a menudo dispersos) utilizan árboles simplex. Si bien los árboles simplex no son tan eficientes como las matrices de incidencia, su estructura basada en simplex les permite ser útiles y eficientes para el almacenamiento de complejos simpliciales dentro de los algoritmos de homología persistente. ^{[ 9 ]}