More Like this

1. Cluster-based Data Reduction for Persistent Homology

   https://doi.org/10.1109/BigData.2018.8622440  

   Moitra, Anindya; Malott, Nicholas O.; Wilsey, Philip A. (December 2018, 2018 IEEE International Conference on Big Data)

   Persistent homology is used for computing topological features of a space at different spatial resolutions. It is one of the main tools from computational topology that is applied to the problems of data analysis. Despite several attempts to reduce its complexity, persistent homology remains expensive in both time and space. These limits are such that the largest data sets to which the method can be applied have the number of points of the order of thousands in R^3. This paper explores a technique intended to reduce the number of data points while preserving the salient topological features of the data. The proposed technique enables the computation of persistent homology on a reduced version of the original input data without affecting significant components of the output. Since the run time of persistent homology is exponential in the number of data points, the proposed data reduction method facilitates the computation in a fraction of the time required for the original data. Moreover, the data reduction method can be combined with any existing technique that simplifies the computation of persistent homology. The data reduction is performed by creating small groups of \emph{similar} data points, called nano-clusters, and then replacing the points within each nano-cluster with its cluster center. The persistence homology of the reduced data differs from that of the original data by an amount bounded by the radius of the nano-clusters. The theoretical analysis is backed by experimental results showing that persistent homology is preserved by the proposed data reduction technique. 

   more » « less
2. Topology Preserving Data Reduction for Computing Persistent Homology

   https://doi.org/10.1109/BigData50022.2020.9378216  

   Malott, Nicholas O.; Sens, Aaron M.; Wilsey, Philip A. (December 2020, International Workshop on Big Data Reduction)

   An emerging method for data analysis is called Topological Data Analysis (TDA). TDA is based in the mathematical field of topology and examines the properties of spaces under continuous deformation. One of the key tools used for TDA is called persistent homology which considers the connectivity of points in a d-dimensional point cloud at different spatial resolutions to identify topological properties (holes, loops, and voids) in the space. Persistent homology then classifies the topological features by their persistence through the range of spatial connectivity. Unfortunately the memory and run-time complexity of computing persistent homology is exponential and current tools can only process a few thousand points in R3. Fortunately, the use of data reduction techniques enables persistent homology to be applied to much larger point clouds. Techniques to reduce the data range from random sampling of points to clustering the data and using the cluster centroids as the reduced data. While several data reduction approaches appear to preserve the large topological features present in the original point cloud, no systematic study comparing the efficacy of different data clustering techniques in preserving the persistent homology results has been performed. This paper explores the question of topology preserving data reductions and describes formally when and how topological features can be mischaracterized or lost by data reduction techniques. The paper also performs an experimental assessment of data reduction techniques and resilient effects on the persistent homology. In particular, data reduction by random selection is compared to cluster centroids extracted from different data clustering algorithms. 

   more » « less
3. Distributed Computation of Persistent Homology from Partitioned Big Data

   https://doi.org/10.1109/Cluster48925.2021.00050  

   Malott, Nicholas O.; Verma, Rishi R.; Singh, Rohit P.; Wilsey, Philip A. (September 2021, IEEE International Conference on Cluster Computing)

   Topological Data Analysis is a machine learning method that summarizes the topological features of a space. Persistent Homology (PH) can identify these topological features as they persist within a point cloud; persisting in respect to the connectedness of the point cloud at increasing distances. The utility of PH is apparent in several fields including bioinformatics, network security, and object classification. However, the memory complexity of PH limits the application to relatively small point clouds for low-dimensional topological feature identification. For this reason, numerous approaches to optimize and approximate the PH have been introduced for providing results over large point clouds. One solution, Partitioned Persistent Homology (PPH), has shown favorable approximation on a single node with significant performance improvement. However, the single-node approach is limited by the available system memory, leading to the need for a distributed approach for additional (especially memory) resources. This paper studies a distributed version of PPH for use with large point clouds over a high-performance compute cluster. Experimental results of the distributed algorithm against previous studies is presented along with scalability of the distributed library. 

   more » « less
4. Data Reduction and Feature Isolation for Computing Persistent Homology on High Dimensional Data

   https://doi.org/10.1109/BigData52589.2021.9671839  

   Verma, Rishi R.; Malott, Nicholas O.; Wilsey, Philip A. (December 2021, Workshop on Applications of Topological Data Analysis to "Big Data")

   Persistent Homology (PH) is computationally expensive and is thus generally employed with strict limits on the (i) maximum connectivity distance and (ii) dimensions of homology groups to compute (unless working with trivially small data sets). As a result, most studies with PH only work with H0 and H1 homology groups. This paper examines the identification and isolation of regions of data sets where high dimensional topological features are suspected to be located. These regions are analyzed with PH to characterize the high dimensional homology groups contained in that region. Since only the region around a suspected topological feature is analyzed, it is possible to identify high dimension homologies piecewise and then assemble the results into a scalable characterization of the original data set. 

   more » « less
5. Persistent Topological Laplacians—A Survey

   https://doi.org/10.3390/math13020208  

   Wei, Xiaoqi; Wei, Guo-Wei (January 2025, Mathematics)

   Persistent topological Laplacians constitute a new class of tools in topological data analysis (TDA). They are motivated by the necessity to address challenges encountered in persistent homology when handling complex data. These Laplacians combine multiscale analysis with topological techniques to characterize the topological and geometrical features of functions and data. Their kernels fully retrieve the topological invariants of corresponding persistent homology, while their non-harmonic spectra provide supplementary information. Persistent topological Laplacians have demonstrated superior performance over persistent homology in the analysis of large-scale protein engineering datasets. In this survey, we offer a pedagogical review of persistent topological Laplacians formulated in various mathematical settings, including simplicial complexes, path complexes, flag complexes, digraphs, hypergraphs, hyperdigraphs, cellular sheaves, and N-chain complexes. 

   more » « less