Parallelization of Change Point Detection

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.