License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.57
URN: urn:nbn:de:0030-drops-71936
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7193/
Go to the corresponding LIPIcs Volume Portal

Kerber, Michael ; Schreiber, Hannah

Barcodes of Towers and a Streaming Algorithm for Persistent Homology

pdf-format:
LIPIcs-SoCG-2017-57.pdf (0.6 MB)

Abstract

A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower. Experimental evaluations show that our approach can efficiently handle towers with billions of complexes.

BibTeX - Entry

@InProceedings{kerber_et_al:LIPIcs:2017:7193,
  author =	{Michael Kerber and Hannah Schreiber},
  title =	{{Barcodes of Towers and a Streaming Algorithm for Persistent Homology}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{57:1--57:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7193},
  URN =		{urn:nbn:de:0030-drops-71936},
  doi =		{10.4230/LIPIcs.SoCG.2017.57},
  annote =	{Keywords: Persistent Homology, Topological Data Analysis, Matrix reduction,  Streaming algorithms, Simplicial Approximation}
}

Keywords: Persistent Homology, Topological Data Analysis, Matrix reduction, Streaming algorithms, Simplicial Approximation
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI