Homology, Homotopy and Applications

Volume 14 (2012)

Number 1

A fast algorithm for constructing topological structure in large data

Pages: 221 – 238

DOI: http://dx.doi.org/10.4310/HHA.2012.v14.n1.a11

Authors

Xu Liu (Department of Mathematics and Systems Science, National University of Defense Technology, Changsha, Hunan, China)

Zheng Xie (Department of Mathematics and Systems Science, National University of Defense Technology, Changsha, Hunan, China)

Dongyun Yi (Department of Mathematics and Systems Science, National University of Defense Technology, Changsha, Hunan, China)

Abstract

Discovering and constructing the topological structure in data has attracted the attention within the community of data analysis. However, most methods developed so far are unsuitable for very large sets of data because of their computational difficulties. This paper presents a fast algorithm for constructing the inherent topological structure in large sets of data that might be noisy in order to enhance the MAPPER algorithm introduced by Singh, Mémoli and Carlsson. The limitation of our method, as shown by our experiments, lies with the storage in the main memory rather than the computing time.

Keywords

data analysis, topological structure, complex network, clustering, Betti number

2010 Mathematics Subject Classification

11F23, 62H30, 68U05

Full Text (PDF format)