{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T12:54:57Z","timestamp":1770814497667,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T00:00:00Z","timestamp":1710806400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T00:00:00Z","timestamp":1710806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Next Generation Converged Digital infrastructure","award":["EP\/R004935\/1"],"award-info":[{"award-number":["EP\/R004935\/1"]}]},{"name":"Next Generation Converged Digital infrastructure","award":["EP\/R004935\/1"],"award-info":[{"award-number":["EP\/R004935\/1"]}]},{"name":"StatScale: Statistical Scalability for Streaming Data","award":["EP\/N031938\/1"],"award-info":[{"award-number":["EP\/N031938\/1"]}]},{"name":"StatScale: Statistical Scalability for Streaming Data","award":["EP\/N031938\/1"],"award-info":[{"award-number":["EP\/N031938\/1"]}]},{"name":"StatScale: Statistical Scalability for Streaming Data","award":["EP\/N031938\/1"],"award-info":[{"award-number":["EP\/N031938\/1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Stat Comput"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Online changepoint detection algorithms that are based on (generalised) likelihood-ratio tests have been shown to have excellent statistical properties. However, a simple online implementation is computationally infeasible as, at time <jats:italic>T<\/jats:italic>, it involves considering <jats:italic>O<\/jats:italic>(<jats:italic>T<\/jats:italic>) possible locations for the change. Recently, the FOCuS algorithm has been introduced for detecting changes in mean in Gaussian data that decreases the per-iteration cost to <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\log T)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>T<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This is possible by using pruning ideas, which reduce the set of changepoint locations that need to be considered at time <jats:italic>T<\/jats:italic> to approximately <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\log T$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>T<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that if one wishes to perform the likelihood ratio test for a different one-parameter exponential family model, then exactly the same pruning rule can be used, and again one need only consider approximately <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\log T$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>T<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> locations at iteration <jats:italic>T<\/jats:italic>. Furthermore, we show how we can adaptively perform the maximisation step of the algorithm so that we need only maximise the test statistic over a small subset of these possible locations. Empirical results show that the resulting online algorithm, which can detect changes under a wide range of models, has a constant-per-iteration cost on average.<\/jats:p>","DOI":"10.1007\/s11222-024-10416-6","type":"journal-article","created":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T16:02:32Z","timestamp":1710864152000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A constant-per-iteration likelihood ratio test for online changepoint detection for exponential family models"],"prefix":"10.1007","volume":"34","author":[{"given":"Kes","family":"Ward","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7751-9017","authenticated-orcid":false,"given":"Gaetano","family":"Romano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9957-2460","authenticated-orcid":false,"given":"Idris","family":"Eckley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9386-2341","authenticated-orcid":false,"given":"Paul","family":"Fearnhead","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,19]]},"reference":[{"key":"10416_CR1","unstructured":"Adams RP, MacKay DJ (2007) Bayesian online changepoint detection. arXiv preprint arXiv:0710.3742"},{"issue":"5","key":"10416_CR2","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1002\/jae.684","volume":"17","author":"E Andreou","year":"2002","unstructured":"Andreou, E., Ghysels, E.: Detecting multiple breaks in financial market volatility dynamics. J. Appl. Economet. 17(5), 579\u2013600 (2002)","journal-title":"J. Appl. Economet."},{"key":"10416_CR3","doi-asserted-by":"crossref","unstructured":"Aue A, Kirch C (2024) The state of cumulative sum sequential change point testing seventy years after Page. Biometrika p To appear","DOI":"10.1093\/biomet\/asad079"},{"key":"10416_CR4","doi-asserted-by":"crossref","unstructured":"Barrett E, Bolz-Tereick CF, Killick R, et\u00a0al (2017) Virtual machine warmup blows hot and cold. In: Proceedings of the ACM on Programming Languages 1(OOPSLA), pp. 1\u201327","DOI":"10.1145\/3133876"},{"issue":"23","key":"10416_CR5","doi-asserted-by":"publisher","first-page":"9519","DOI":"10.1175\/JCLI-D-17-0863.1","volume":"31","author":"C Beaulieu","year":"2018","unstructured":"Beaulieu, C., Killick, R.: Distinguishing trends and shifts from memory in climate data. J. Clim. 31(23), 9519\u20139543 (2018)","journal-title":"J. Clim."},{"issue":"2","key":"10416_CR6","doi-asserted-by":"publisher","first-page":"1408","DOI":"10.3150\/15-BEJ782","volume":"23","author":"S Chakar","year":"2017","unstructured":"Chakar, S., Lebarbier, E., L\u00e9vy-Leduc, C., et al.: A robust approach for estimating change-points in the mean of an AR(1) process. Bernoulli 23(2), 1408\u20131447 (2017)","journal-title":"Bernoulli"},{"key":"10416_CR7","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1111\/rssb.12447","volume":"84","author":"Y Chen","year":"2022","unstructured":"Chen, Y., Wang, T., Samworth, R.J.: High-dimensional, multiscale online changepoint detection. J. Royal Stat. Soc. (Series B) 84, 234\u2013266 (2022)","journal-title":"J. Royal Stat. Soc. (Series B)"},{"issue":"1","key":"10416_CR8","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.matcom.2010.06.021","volume":"81","author":"Z Chen","year":"2010","unstructured":"Chen, Z., Tian, Z.: Modified procedures for change point monitoring in linear models. Math. Comput. Simul. 81(1), 62\u201375 (2010)","journal-title":"Math. Comput. Simul."},{"issue":"2","key":"10416_CR9","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1111\/rssb.12079","volume":"77","author":"H Cho","year":"2015","unstructured":"Cho, H., Fryzlewicz, P.: Multiple-change-point detection for high dimensional time series via sparsified binary segmentation. J. Royal Stat. Soc. Series B (Statistical Methodology) 77(2), 475\u2013507 (2015)","journal-title":"J. Royal Stat. Soc. Series B (Statistical Methodology)"},{"key":"10416_CR10","doi-asserted-by":"publisher","unstructured":"Cho, H. and Fryzlewicz, P. (2024), Multiple change point detection under serial dependence: Wild contrast maximisation and gappy Schwarz algorithm. J. Time Ser. Anal. https:\/\/doi.org\/10.1111\/jtsa.12722","DOI":"10.1111\/jtsa.12722"},{"issue":"3","key":"10416_CR11","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1093\/biomet\/82.3.603","volume":"82","author":"CSJ Chu","year":"1995","unstructured":"Chu, C.S.J., Hornik, K., Kaun, C.M.: MOSUM tests for parameter constancy. Biometrika 82(3), 603\u2013617 (1995)","journal-title":"Biometrika"},{"issue":"1","key":"10416_CR12","doi-asserted-by":"publisher","first-page":"526","DOI":"10.3150\/16-BEJ887","volume":"24","author":"B Eichinger","year":"2018","unstructured":"Eichinger, B., Kirch, C.: A mosum procedure for the estimation of multiple random change points. Bernoulli 24(1), 526\u2013564 (2018)","journal-title":"Bernoulli"},{"issue":"4","key":"10416_CR13","doi-asserted-by":"publisher","first-page":"2051","DOI":"10.1214\/18-AOS1740","volume":"47","author":"F Enikeeva","year":"2019","unstructured":"Enikeeva, F., Harchaoui, Z.: High-dimensional change-point detection under sparse alternatives. Ann. Stat. 47(4), 2051\u20132079 (2019)","journal-title":"Ann. Stat."},{"issue":"4","key":"10416_CR14","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1111\/j.1467-9868.2007.00601.x","volume":"69","author":"P Fearnhead","year":"2007","unstructured":"Fearnhead, P., Liu, Z.: On-line inference for multiple changepoint problems. J. R. Stat. Soc. Ser. B Stat Methodol. 69(4), 589\u2013605 (2007)","journal-title":"J. R. Stat. Soc. Ser. B Stat Methodol."},{"key":"10416_CR15","doi-asserted-by":"crossref","unstructured":"Hallgren KL, Heard NA, Adams NM (2021) Changepoint detection in non-exchangeable data. arXiv preprint arXiv:2111.05054","DOI":"10.1007\/s11222-022-10176-1"},{"issue":"427","key":"10416_CR16","first-page":"913","volume":"89","author":"C Inclan","year":"1994","unstructured":"Inclan, C., Tiao, G.C.: Use of cumulative sums of squares for retrospective detection of changes of variance. J. Am. Stat. Assoc. 89(427), 913\u2013923 (1994)","journal-title":"J. Am. Stat. Assoc."},{"key":"10416_CR17","doi-asserted-by":"crossref","unstructured":"Iwata T, Nakamura K, Tokusashi Y, et\u00a0al (2018) Accelerating online change-point detection algorithm using 10 GbE FPGA NIC. In: European Conference on Parallel Processing, Springer, pp 506\u2013517","DOI":"10.1007\/978-3-030-10549-5_40"},{"key":"10416_CR18","doi-asserted-by":"publisher","first-page":"3515","DOI":"10.1109\/TSP.2020.2990597","volume":"68","author":"N Keriven","year":"2020","unstructured":"Keriven, N., Garreau, D., Poli, I.: NEWMA: a new method for scalable model-free online change-point detection. IEEE Trans. Signal Process. 68, 3515\u20133528 (2020)","journal-title":"IEEE Trans. Signal Process."},{"issue":"82","key":"10416_CR19","first-page":"1","volume":"21","author":"H Keshavarz","year":"2020","unstructured":"Keshavarz, H., Michaildiis, G., Atchad\u00e9, Y.: Sequential change-point detection in high-dimensional Gaussian graphical models. J. Mach. Learn. Res. 21(82), 1\u201357 (2020)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"10416_CR20","doi-asserted-by":"publisher","first-page":"1579","DOI":"10.1214\/18-EJS1431","volume":"12","author":"C Kirch","year":"2018","unstructured":"Kirch, C., Weber, S., et al.: Modified sequential change point procedures based on estimating functions. Electron. J. Stat. 12(1), 1579\u20131613 (2018)","journal-title":"Electron. J. Stat."},{"issue":"4","key":"10416_CR21","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1111\/j.2517-6161.1995.tb02052.x","volume":"57","author":"TL Lai","year":"1995","unstructured":"Lai, T.L.: Sequential changepoint detection in quality control and dynamical systems. J. Roy. Stat. Soc.: Ser. B (Methodol.) 57(4), 613\u2013644 (1995)","journal-title":"J. Roy. Stat. Soc.: Ser. B (Methodol.)"},{"issue":"2","key":"10416_CR22","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1080\/07474941003741078","volume":"29","author":"TL Lai","year":"2010","unstructured":"Lai, T.L., Xing, H.: Sequential change-point detection when the pre-and post-change parameters are unknown. Seq. Anal. 29(2), 162\u2013175 (2010)","journal-title":"Seq. Anal."},{"issue":"1","key":"10416_CR23","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1111\/1467-9892.00172","volume":"21","author":"M Lavielle","year":"2000","unstructured":"Lavielle, M., Moulines, E.: Least-squares estimation of an unknown number of shifts in a time series. J. Time Ser. Anal. 21(1), 33\u201359 (2000)","journal-title":"J. Time Ser. Anal."},{"issue":"8","key":"10416_CR24","doi-asserted-by":"publisher","first-page":"1779","DOI":"10.1080\/00949655.2013.766737","volume":"84","author":"Z Li","year":"2014","unstructured":"Li, Z., Zou, C., Gong, Z., et al.: The computation of average run length and average time to signal: an overview. J. Stat. Comput. Simul. 84(8), 1779\u20131802 (2014)","journal-title":"J. Stat. Comput. Simul."},{"issue":"6","key":"10416_CR25","doi-asserted-by":"publisher","first-page":"1897","DOI":"10.1214\/aoms\/1177693055","volume":"42","author":"G Lorden","year":"1971","unstructured":"Lorden, G.: Procedures for reacting to a change in distribution. Ann. Math. Stat. 42(6), 1897\u20131908 (1971)","journal-title":"Ann. Math. Stat."},{"issue":"2","key":"10416_CR26","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1080\/00401706.1985.10488030","volume":"27","author":"JM Lucas","year":"1985","unstructured":"Lucas, J.M.: Counted data CUSUMs. Technometrics 27(2), 129\u2013144 (1985)","journal-title":"Technometrics"},{"issue":"2","key":"10416_CR27","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1093\/biomet\/asq010","volume":"97","author":"Y Mei","year":"2010","unstructured":"Mei, Y.: Efficient scalable schemes for monitoring a large number of data streams. Biometrika 97(2), 419\u2013433 (2010)","journal-title":"Biometrika"},{"issue":"3\/4","key":"10416_CR28","doi-asserted-by":"publisher","first-page":"523","DOI":"10.2307\/2333401","volume":"42","author":"E Page","year":"1955","unstructured":"Page, E.: A test for a change in a parameter occurring at an unknown point. Biometrika 42(3\/4), 523\u2013527 (1955)","journal-title":"Biometrika"},{"issue":"1\/2","key":"10416_CR29","doi-asserted-by":"publisher","first-page":"100","DOI":"10.2307\/2333009","volume":"41","author":"ES Page","year":"1954","unstructured":"Page, E.S.: Continuous inspection schemes. Biometrika 41(1\/2), 100\u2013115 (1954)","journal-title":"Biometrika"},{"key":"10416_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/01621459.2021.1909598","volume":"117","author":"G Romano","year":"2022","unstructured":"Romano, G., Rigaill, G., Runge, V., et al.: Detecting abrupt changes in the presence of local fluctuations and autocorrelated noise. J. Am. Stat. Assoc. 117, 1\u201316 (2022)","journal-title":"J. Am. Stat. Assoc."},{"key":"10416_CR31","doi-asserted-by":"publisher","unstructured":"Romano G., Eckley I. A., Fearnhead P.: A log-linear non-parametric online changepoint detection algorithm based on functional pruning. IEEE Trans. Signal Process., vol. 72, pp. 594\u2013606, (2024) https:\/\/doi.org\/10.1109\/TSP.2023.3343550","DOI":"10.1109\/TSP.2023.3343550"},{"issue":"81","key":"10416_CR32","first-page":"1","volume":"24","author":"G Romano","year":"2023","unstructured":"Romano, G., Eckley, I., Fearnhead, P., et al.: Fast online changepoint detection via functional pruning CUSUM statistics. J. Mach. Learn. Res. 24(81), 1\u201336 (2023)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"10416_CR33","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1080\/00224065.2012.11917887","volume":"44","author":"GJ Ross","year":"2012","unstructured":"Ross, G.J., Adams, N.M.: Two nonparametric control charts for detecting arbitrary distribution changes. J. Qual. Technol. 44(2), 102\u2013116 (2012). https:\/\/doi.org\/10.1080\/00224065.2012.11917887","journal-title":"J. Qual. Technol."},{"issue":"4","key":"10416_CR34","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1198\/TECH.2011.10069","volume":"53","author":"GJ Ross","year":"2011","unstructured":"Ross, G.J., Tasoulis, D.K., Adams, N.M.: Nonparametric monitoring of data streams for changes in location and scale. Technometrics 53(4), 379\u2013389 (2011). https:\/\/doi.org\/10.1198\/TECH.2011.10069","journal-title":"Technometrics"},{"key":"10416_CR35","doi-asserted-by":"crossref","unstructured":"Sakamoto Y, Fukui KI, Gama J, et\u00a0al (2015) Concept drift detection with clustering via statistical change detection methods. In: 2015 Seventh International Conference on Knowledge and Systems Engineering (KSE), IEEE, pp 37\u201342","DOI":"10.1109\/KSE.2015.19"},{"issue":"4","key":"10416_CR36","doi-asserted-by":"publisher","first-page":"1303","DOI":"10.1111\/rssa.12695","volume":"184","author":"SO Tickle","year":"2021","unstructured":"Tickle, S.O., Eckley, I., Fearnhead, P.: A computationally efficient, high-dimensional multiple changepoint procedure with application to global terrorism incidence. J. Royal Stat. Soc. Series A (Statistics in Society) 184(4), 1303\u20131325 (2021)","journal-title":"J. Royal Stat. Soc. Series A (Statistics in Society)"},{"key":"10416_CR37","doi-asserted-by":"crossref","unstructured":"Varghese B, Wang N, Barbhuiya S, et\u00a0al (2016) Challenges and opportunities in edge computing. In: 2016 IEEE International Conference on Smart Cloud (SmartCloud), pp 20\u201326, 10.1109\/SmartCloud.2016.18","DOI":"10.1109\/SmartCloud.2016.18"},{"key":"10416_CR38","doi-asserted-by":"publisher","unstructured":"Ward, K., Dilillo, G., Eckley, I., & Fearnhead, P. (2023). Poisson-FOCuS: An efficient online method for detecting count bursts with application to gamma ray burst detection. J. Am. Stat. Assoc., 1\u201313. https:\/\/doi.org\/10.1080\/01621459.2023.2235059","DOI":"10.1080\/01621459.2023.2235059"},{"key":"10416_CR39","doi-asserted-by":"publisher","unstructured":"Yu, Y., Madrid Padilla, O. H., Wang, D., & Rinaldo, A. (2023). A note on online change point detection. Sequential Analysis, 42(4), 438\u2013471. https:\/\/doi.org\/10.1080\/07474946.2023.2276170","DOI":"10.1080\/07474946.2023.2276170"}],"container-title":["Statistics and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-024-10416-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11222-024-10416-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-024-10416-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T11:08:51Z","timestamp":1716635331000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11222-024-10416-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,19]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["10416"],"URL":"https:\/\/doi.org\/10.1007\/s11222-024-10416-6","relation":{},"ISSN":["0960-3174","1573-1375"],"issn-type":[{"value":"0960-3174","type":"print"},{"value":"1573-1375","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,19]]},"assertion":[{"value":"9 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"99"}}