Simplicial Homology's Fast Algorithm And Its Application On Massive Data Processing

An important feature of information age is that datum of various kinds are being produced at an unprecedented rate, with more complex relationships. One of the most crucial challenges is how to extract the internal structure and apply it to practice. The data analysis method based on topology is placed high hopes on, and in virtue of the characters such as insensitive to metric, good at analyzing relationships in data, capable of global perspective analysising of target information and etc. It seems to be a next revolutionary breakthrough in massive data analysis field, it has been applied for many fields such as biology, medical, computer science, intelligence analysis and nature image processing.This thesis aims at the processing of complex and massive information, take simplicial homology of topological data analysis as an example, which can be divided into two parts:Firstly, inorder to alleviate the computation complexity in dealing with massive data set, we propose an optimal approximation algorithm based on landmarks, which then used to produce the witness complex with the same persistent homology as the original data set. Besides, the additional operation of noise processing is joined to the algorithm for the data set with increasing noises;Secondly, as an engineering application, we consider the coverage problem in the wireless sensor network, including both the blind zone and redundant sensor detection. The simplicial homology of the commucation network of the sensors is used to detect the coverage of the target field. This approach does not involve intensive geometry computations and no location information are needed, and not only simplify the computation but also reduce the designing complexity.