The DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Optimal Detection of Changepoints With a Linear Computational Cost
Open accessAbstract
In this article, we consider the problem of detecting multiple changepoints in large datasets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example, in genetics as we analyze larger regions of the genome, or in finance as we observe time series over longer periods. We consider the common approach of detecting changepoints through minimizing a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalized likelihood and minimum description length. We introduce a new method for finding the minimum of such cost functions and hence the optimal number and location of changepoints that has a computational cost, which, under mild conditions, is linear in the number of observations. This compares favorably with existing methods for the same problem whose computational cost can be quadratic or even cubic. In simulation studies, we show that our new method can be orders of magnitude faster than these alternative exact methods. We also compare with the binary segmentation algorithm for identifying changepoints, showing that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data. This article has supplementary materials available online.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A new look at the statistical model identification
Akaike, H. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100705 · Cited by 51,879
Estimating the Dimension of a Model
Schwarz, G. (1978) · The Annals of Statistics · doi:10.1214/aos/1176344136 · Cited by 47,033
Holland, J. H. (1992) · The MIT Press eBooks · doi:10.7551/mitpress/1090.001.0001 · Cited by 47,002
A Cluster Analysis Method for Grouping Means in the Analysis of Variance
Scott, A. J., & Knott, M. (1974) · Biometrics · doi:10.2307/2529204 · Cited by 2,770
Circular binary segmentation for the analysis of array-based DNA copy number data
Olshen, A. B., Venkatraman, E. S., Lucito, R., & Wigler, M. (2004) · Biostatistics · doi:10.1093/biostatistics/kxh008 · Cited by 2,325
Freimer, M., Bellman, R. E., & Dreyfus, S. E. (1964) · Journal of the American Statistical Association · doi:10.2307/2282884 · Cited by 2,153
Bellman, R. E., & Dreyfus, S. E. (1962) · Princeton University Press eBooks · doi:10.1515/9781400874651 · Cited by 1,971
Use of Cumulative Sums of Squares for Retrospective Detection of Changes of Variance
Inclán, C., & Tiao, G. C. (1994) · Journal of the American Statistical Association · doi:10.1080/01621459.1994.10476824 · Cited by 1,156
Volatility in Emerging Stock Markets
Aggarwal, R., Inclan, C., & Leal, R. (1999) · The Journal of Financial and Quantitative Analysis · doi:10.2307/2676245 · Cited by 734
Parametric Statistical Change Point Analysis: With Applications to Genetics, Medicine, and Finance
Chen, J., & Gupta, A. K. (2012) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4801-5 · Cited by 596
Cited by
Selective review of offline change point detection methods
Truong, C., Oudre, L., & Vayatis, N. (2020) · Signal Processing · doi:10.1016/j.sigpro.2019.107299 · Cited by 1,338
changepoint : An R Package for Changepoint Analysis
Killick, R., & Eckley, I. A. (2014) · Journal of Statistical Software · doi:10.18637/jss.v058.i03 · Cited by 1,330
Self-citationCicero predicts cis-regulatory DNA interactions from single-cell chromatin accessibility data
Pliner, H. A., Packer, J. S., McFaline-Figueroa, J. L., Cusanovich, D. A., Daza, R. M., Aghamirzaie, D., Srivatsan, S., Qiu, X., Jackson, D., Minkina, A., et al. (2018) · Molecular Cell · doi:10.1016/j.molcel.2018.06.044 · Cited by 789
Wild binary segmentation for multiple change-point detection
Fryzlewicz, P. (2014) · The Annals of Statistics · doi:10.1214/14-aos1245 · Cited by 566
A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data
Matteson, D. S., & James, N. A. (2014) · Journal of the American Statistical Association · doi:10.1080/01621459.2013.849605 · Cited by 542
Tracking vegetation phenology across diverse North American biomes using PhenoCam imagery
Richardson, A. D., Hufkens, K., Milliman, T., Aubrecht, D. M., Chen, M., Gray, J. M., Johnston, M. R., Keenan, T. F., Klosterman, S. T., Kosmala, M., et al. (2018) · Scientific Data · doi:10.1038/sdata.2018.28 · Cited by 535
Characterizing genetic intra-tumor heterogeneity across 2,658 human cancer genomes
Dentro, S. C., Leshchiner, I., Haase, K., Tarabichi, M., Wintersinger, J., Deshwar, A. G., Yu, K., Rubanova, Y., Macintyre, G., Demeulemeester, J., et al. (2021) · Cell · doi:10.1016/j.cell.2021.03.009 · Cited by 533
Classification of electrophysiological and morphological neuron types in the mouse visual cortex
Gouwens, N. W., Sorensen, S. A., Berg, J., Lee, C., Jarsky, T., Ting, J., Sunkin, S. M., Feng, D., Anastassiou, C. A., Barkan, E., et al. (2019) · Nature Neuroscience · doi:10.1038/s41593-019-0417-0 · Cited by 456
The histone mark H3K36me2 recruits DNMT3A and shapes the intergenic DNA methylation landscape
Weinberg, D. N., Papillon-Cavanagh, S., Chen, H., Yue, Y., Chen, X., Rajagopalan, K. N., Horth, C., McGuire, J. T., Xu, X., Nikbakht, H., et al. (2019) · Nature · doi:10.1038/s41586-019-1534-3 · Cited by 524
Slater, L. J., Anderson, B., Buechel, M., Dadson, S., Han, S., Harrigan, S., Kelder, T., Kowal, K., Lees, T., Matthews, T., et al. (2021) · Hydrology and Earth System Sciences · doi:10.5194/hess-25-3897-2021 · Cited by 357
Multiscale Change Point Inference
Frick, K., Munk, A., & Sieling, H. (2014) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/rssb.12047 · Cited by 320
Widespread drying of European peatlands in recent centuries
Swindles, G. T., Morris, P. J., Mullan, D. J., Payne, R. J., Roland, T. P., Amesbury, M. J., Lamentowicz, M., Turner, T. E., Gallego-Sala, A., Sim, T., et al. (2019) · Nature Geoscience · doi:10.1038/s41561-019-0462-z · Cited by 279
Wang, Z., Locantore, N., Haldar, K., Ramsheh, M. Y., Beech, A. S., Ma, W., Brown, J. R., Tal-Singer, R., Barer, M. R., Bafadhel, M., et al. (2021) · American Journal of Respiratory and Critical Care Medicine · doi:10.1164/rccm.202009-3448oc · Cited by 274
Valdez, D., ten Thij, M., Bathina, K., Rutter, L. A., & Bollen, J. (2020) · Journal of Medical Internet Research · doi:10.2196/21418 · Cited by 270
Edelhoff, H., Signer, J., & Balkenhol, N. (2016) · Movement Ecology · doi:10.1186/s40462-016-0086-5 · Cited by 262
Towards a new approach to reveal dynamical organization of the brain using topological data analysis
Saggar, M., Sporns, O., Gonzalez-Castillo, J., Bandettini, P. A., Carlsson, G., Glover, G., & Reiss, A. L. (2018) · Nature Communications · doi:10.1038/s41467-018-03664-4 · Cited by 253
On the co‐evolution of surface oxygen levels and animals
Cole, D. B., Mills, D. B., Erwin, D. H., Sperling, E. A., Porter, S. M., Reinhard, C. T., & Planavsky, N. J. (2020) · Geobiology · doi:10.1111/gbi.12382 · Cited by 141
Landgren, O., Hofmann, J. N., McShane, C. M., Santo, L., Hultcrantz, M., Korde, N., Mailankody, S., Kazandjian, D., Murata, K., Thoren, K., et al. (2019) · JAMA Oncology · doi:10.1001/jamaoncol.2019.1568 · Cited by 103
Cohen, A., Naslund, J. A., Chang, S., Nagendra, S., Bhan, A., Rozatkar, A., Thirthalli, J., Bondre, A., Tugnawat, D., Reddy, P. V., et al. (2023) · Schizophrenia · doi:10.1038/s41537-023-00332-5 · Cited by 90
Cortical–hippocampal coupling during manifold exploration in motor cortex
Kim, J., Joshi, A., Frank, L., & Ganguly, K. (2023) · Nature · doi:10.1038/s41586-022-05533-z · Cited by 77
The endless frontier? The recent increase of R&D productivity in pharmaceuticals
Pammolli, F., Righetto, L., Abrignani, S., Pani, L., Pelicci, P. G., & Rabosio, E. (2020) · Journal of Translational Medicine · doi:10.1186/s12967-020-02313-z · Cited by 77
Effectiveness of Localized Lockdowns in the COVID-19 Pandemic
Li, Y., Undurraga, E. A., & Zubizarreta, J. R. (2020) · doi:10.1101/2020.08.25.20182071 · Cited by 58
Stylometric Detection of AI-Generated Text in Twitter Timelines
Kumarage, T., Garland, J., Bhattacharjee, A., Trapeznikov, K., Ruston, S., & Liu, H. (2023) · arXiv · doi:10.48550/arxiv.2303.03697 · Cited by 25
“In this work, we used the Pruned Exact Linear Time (PELT) algorithm [13] for detecting change points in our data.”
MethodChromatin accessibility dynamics of myogenesis at single cell resolution
Pliner, H. A., Packer, J., McFaline-Figueroa, J. L., Cusanovich, D. A., Daza, R., Srivatsan, S., Qiu, X., Jackson, D., Minkina, A., Adey, A., et al. (2017) · doi:10.1101/155473 · Cited by 16
Brain Activity Associated with Breakthrough Food Preoccupation in an Individual on Tirzepatide
Choi, W., Nho, Y.-H., Qiu, L., Chang, A., Campos, G., Seilheimer, R. L., Wilent, W. B., Bakalov, D., Firdous, N., Kerr, M., et al. (2025) · Nature Medicine · doi:10.1038/s41591-025-04035-5 · Cited by 10
Deep Learning for Skeleton-Based Human Activity Segmentation: An Autoencoder Approach
Hossen, M. A., Naim, A. G., & Abas, P. E. (2024) · Technologies · doi:10.3390/technologies12070096 · Cited by 7
Butt, A. H., Zambrana, C., Idelsohn-Zielonka, S., Claramunt-Molet, M., Ugartemendia-Etxarri, A., Rovini, E., Moschetti, A., Molleja, C., Martin, C., Salleras, E. O., et al. (2019) · 2019 IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB) · doi:10.1109/cibcb.2019.8791470 · Cited by 6
Strategic Response of News Publishers to Generative AI
Zhao, H., & Berman, R. (2025) · arXiv · doi:10.48550/arxiv.2512.24968 · Cited by 6
Metadata
- Authors
- Killick, R., Fearnhead, P., & Eckley, I. A.
- Venue
- Journal of the American Statistical Association
- Publisher
- Informa UK Limited
- Published
- 2012-10-17
- Volume
- 107
- Issue
- 500
- Pages
- 1590-1598
- ISSN
- 0162-1459 (ISSN-L)
- 1537-274X
- OpenAlex
- W1975684011
- Cited by
- 2,548
- References
- 29
- FWCI
- 46.70
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.