Home > Research > Publications & Outputs > Parallelization of a Common Changepoint Detecti...

Electronic data

  • ParallelCpts

    Accepted author manuscript, 2.55 MB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

Parallelization of a Common Changepoint Detection Method

Research output: Contribution to journalJournal articlepeer-review

Published

Standard

Parallelization of a Common Changepoint Detection Method. / Tickle, Sam; Eckley, Idris; Fearnhead, Paul; Haynes, Kaylea.

In: Journal of Computational and Graphical Statistics, Vol. 29, No. 1, 01.04.2020, p. 149-161.

Research output: Contribution to journalJournal articlepeer-review

Harvard

APA

Vancouver

Author

Tickle, Sam ; Eckley, Idris ; Fearnhead, Paul ; Haynes, Kaylea. / Parallelization of a Common Changepoint Detection Method. In: Journal of Computational and Graphical Statistics. 2020 ; Vol. 29, No. 1. pp. 149-161.

Bibtex

@article{0b3a003e47204f50a9796f6c8c55fb36,
title = "Parallelization of a Common Changepoint Detection Method",
abstract = "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.",
keywords = "Changepoint Detection, Dynamic programming, Parallelisation, PELT",
author = "Sam Tickle and Idris Eckley and Paul Fearnhead and Kaylea Haynes",
year = "2020",
month = apr,
day = "1",
doi = "10.1080/10618600.2019.1647216",
language = "English",
volume = "29",
pages = "149--161",
journal = "Journal of Computational and Graphical Statistics",
issn = "1061-8600",
publisher = "American Statistical Association",
number = "1",

}

RIS

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 -