Parallelization of Change Point Detection

Nancy Song, Haw Yang

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

The change point detection method (Watkins, L. P.; Yang, H. J. Phys. Chem. B 2005, 109, 617) allows the objective identification and isolation of abrupt changes along a data series. Because this method is grounded in statistical tests, it is particularly powerful for probing complex and noisy signals without artificially imposing a kinetics model. The original algorithm, however, has a time complexity of O(N2), where N is the size of the data and is, therefore, limited in its scalability. This paper puts forth a parallelization of change point detection to address these time and memory constraints. This parallelization method was evaluated by applying it to changes in the mean of Gaussian-distributed data and found that time decreases superlinearly with respect to the number of processes (i.e., parallelization with two processes takes less than half of the time of one process). Moreover, there was minimal reduction in detection power. These results suggest that our parallelization algorithm is a viable scheme that can be implemented for other change point detection methods.

Original languageEnglish (US)
Pages (from-to)5100-5109
Number of pages10
JournalJournal of Physical Chemistry A
Volume121
Issue number27
DOIs
StatePublished - Jul 13 2017

All Science Journal Classification (ASJC) codes

  • Physical and Theoretical Chemistry

Fingerprint Dive into the research topics of 'Parallelization of Change Point Detection'. Together they form a unique fingerprint.

  • Cite this