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.ESA.2016.35
URN: urn:nbn:de:0030-drops-63869
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6386/
Go to the corresponding LIPIcs Volume Portal

Dey, Tamal K. ; Shi, Dayu ; Wang, Yusu

SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse

pdf-format:
LIPIcs-ESA-2016-35.pdf (2 MB)

Abstract

In topological data analysis, a point cloud data P extracted from a metric space is often analyzed by computing the persistence diagram or barcodes of a sequence of Rips complexes built on P indexed by a scale parameter. Unfortunately, even for input of moderate size, the size of the Rips complex may become prohibitively large as the scale parameter increases. Starting with the Sparse Rips filtration introduced by Sheehy, some existing methods aim to reduce the size of the complex so as to improve the time efficiency as well. However, as we demonstrate, existing approaches still fall short of scaling well, especially for high dimensional data. In this paper, we investigate the advantages and limitations of existing approaches. Based on insights gained from the experiments, we propose an efficient new algorithm, called SimBa, for approximating the persistent homology of Rips filtrations with quality guarantees. Our new algorithm leverages a batch collapse strategy as well as a new sparse Rips-like filtration. We experiment on a variety of low and high dimensional data sets. We show that our strategy presents a significant size reduction, and our algorithm for approximating Rips filtration persistence is order of magnitude faster than existing methods in practice.

BibTeX - Entry

@InProceedings{dey_et_al:LIPIcs:2016:6386,
  author =	{Tamal K. Dey and Dayu Shi and Yusu Wang},
  title =	{{SimBa: An Efficient Tool for Approximating  Rips-Filtration Persistence via Simplicial Batch-Collapse}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6386},
  URN =		{urn:nbn:de:0030-drops-63869},
  doi =		{10.4230/LIPIcs.ESA.2016.35},
  annote =	{Keywords: Rips filtration, Homology groups, Persistence, Topological data analysis}
}

Keywords: Rips filtration, Homology groups, Persistence, Topological data analysis
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

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