Fast Computation of Persistent Homology with Data Reduction and Data Partitioning
Fast Computation of Persistent Homology with Data Reduction and Data Partitioning
复制标题
DOI：
10.1109/bigdata47090.2019.9006572
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Nicholas O. Malott;P. Wilsey
中科院分区：
文献类型：
--
作者：
Nicholas O. Malott;P. Wilsey
持久同调是一种基于拓扑学数学领域的数据分析方法。不幸的是，与计算持久同源性相关的运行时和内存复杂性阻碍了大数据分析的普遍使用。例如，目前用于计算持久同源性的最佳工具只能处理$\ mathm {R}^{3}$中的几千个数据点。一些研究建议使用抽样或数据简化方法来突破这一限制。虽然这些方法能够在更大的数据集上计算持久同源性，但这些方法是近似的。此外，虽然它们在很大程度上保留了大型拓扑特征的结果，但它们通常会错过报告数据集中存在的小拓扑特征的信息。虽然这种抽象在很多情况下是有用的，但也有一些数据分析需要，其中较小的特征也很重要（例如，脑动脉分析）。本文探讨了数据约简和数据分区的结合，以计算大数据上的持久同源性，从而能够从输入数据集中识别大小拓扑特征。为了减少通常伴随持久同构的数据缩减的近似误差，所描述的方法还包括一种“升级”数据的机制，该机制限制了从采样数据中计算的大型拓扑特征。设计的实验方法为提高持续同源性的尺度提供了重要的结果。
Persistent homology is a method of data analysis that is based in the mathematical field of topology. Unfortunately, the run-time and memory complexities associated with computing persistent homology inhibit general use for the analysis of big data. For example, the best tools currently available to compute persistent homology can process only a few thousand data points in $\mathrm{R}^{3}$. Several studies have proposed using sampling or data reduction methods to attack this limit. While these approaches enable the computation of persistent homology on much larger data sets, the methods are approximate. Furthermore, while they largely preserve the results of large topological features, they generally miss reporting information about the small topological features that are present in the data set. While this abstraction is useful in many cases, there are data analysis needs where the smaller features are also significant (e.g., brain artery analysis). This paper explores a combination of data reduction and data partitioning to compute persistent homology on big data that enables the identification of both large and small topological features from the input data set. To reduce the approximation errors that typically accompany data reduction for persistent homology, the described method also includes a mechanism of “upscaling” the data circumscribing the large topological features that are computed from the sampled data. The designed experimental method provides significant results for improving the scale at which persistent homology can be performed.