Accepted author manuscript, 2.55 MB, PDF document
Available under license: CC BY: Creative Commons Attribution 4.0 International License
Final published version
Licence: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Parallelization of a Common Changepoint Detection Method
AU - Tickle, Sam
AU - Eckley, Idris
AU - Fearnhead, Paul
AU - Haynes, Kaylea
PY - 2020/4/1
Y1 - 2020/4/1
N2 - In recent years, various means of efficiently detecting changepoints have been proposed, with one popular approach involving minimizing a penalized cost function using dynamic programming. In some situations, these algorithms can have an expected computational cost that is linear in the number of data points; however, the worst case cost remains quadratic. We introduce two means of improving the computational performance of these methods, both based on parallelizing the dynamic programming approach. We establish that parallelization can give substantial computational improvements: in some situations the computational cost decreases roughly quadratically in the number of cores used. These parallel implementations are no longer guaranteed to find the true minimum of the penalized cost; however, we show that they retain the same asymptotic guarantees in terms of their accuracy in estimating the number and location of the changes. Supplementary materials for this article are available online.
AB - In recent years, various means of efficiently detecting changepoints have been proposed, with one popular approach involving minimizing a penalized cost function using dynamic programming. In some situations, these algorithms can have an expected computational cost that is linear in the number of data points; however, the worst case cost remains quadratic. We introduce two means of improving the computational performance of these methods, both based on parallelizing the dynamic programming approach. We establish that parallelization can give substantial computational improvements: in some situations the computational cost decreases roughly quadratically in the number of cores used. These parallel implementations are no longer guaranteed to find the true minimum of the penalized cost; however, we show that they retain the same asymptotic guarantees in terms of their accuracy in estimating the number and location of the changes. Supplementary materials for this article are available online.
KW - Changepoint Detection
KW - Dynamic programming
KW - Parallelisation
KW - PELT
U2 - 10.1080/10618600.2019.1647216
DO - 10.1080/10618600.2019.1647216
M3 - Journal article
VL - 29
SP - 149
EP - 161
JO - Journal of Computational and Graphical Statistics
JF - Journal of Computational and Graphical Statistics
SN - 1061-8600
IS - 1
ER -