{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T20:34:08Z","timestamp":1770755648360,"version":"3.50.0"},"reference-count":58,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T00:00:00Z","timestamp":1754438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"publisher","award":["EP\/Z531327\/1, EP\/W522612\/1, and EP\/N031938\/1"],"award-info":[{"award-number":["EP\/Z531327\/1, EP\/W522612\/1, and EP\/N031938\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,2,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The increasing volume of data streams poses significant computational challenges for detecting changepoints online. Likelihood-based methods are effective, but a naive sequential implementation becomes impractical online due to high computational costs. We develop an online algorithm that exactly calculates the likelihood ratio test for a single changepoint in p-dimensional data streams by leveraging a fascinating connection with computational geometry. This connection straightforwardly allows us to exactly recover sparse likelihood ratio statistics: that is assuming only a subset of the dimensions are changing. Our algorithm is straightforward, fast, and apparently quasi-linear. A dyadic variant of our algorithm is provably quasi-linear, being O(nlog(n)p+1) for n data points and p less than 3, but slower in practice. These algorithms are computationally impractical when p is larger than 5, and we provide an approximate algorithm suitable for such p which is O(nplog(n)p~+1), for some user-specified p~\u22645. We derive statistical guarantees for the proposed procedures in the Gaussian case, and confirm the good computational and statistical performance, and usefulness, of the algorithms on both empirical data and NBA data.<\/jats:p>","DOI":"10.1093\/jrsssb\/qkaf046","type":"journal-article","created":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T11:32:04Z","timestamp":1753183924000},"page":"171-194","source":"Crossref","is-referenced-by-count":0,"title":["Online multivariate changepoint detection: leveraging links with computational geometry"],"prefix":"10.1093","volume":"88","author":[{"given":"Liudmila","family":"Pishchagina","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CNRS, Univ Evry, Laboratoire de Math\u00e9matiques et Mod\u00e9lisation d'Evry, 91037 Evry-Courcouronnes ,","place":["France"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7751-9017","authenticated-orcid":false,"given":"Gaetano","family":"Romano","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Lancaster University , Lancaster LA1 4YF ,","place":["UK"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9386-2341","authenticated-orcid":false,"given":"Paul","family":"Fearnhead","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Lancaster University , Lancaster LA1 4YF ,","place":["UK"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Runge","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CNRS, Univ Evry, Laboratoire de Math\u00e9matiques et Mod\u00e9lisation d'Evry, 91037 Evry-Courcouronnes ,","place":["France"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7176-7511","authenticated-orcid":false,"given":"Guillem","family":"Rigaill","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CNRS, Univ Evry, Laboratoire de Math\u00e9matiques et Mod\u00e9lisation d'Evry, 91037 Evry-Courcouronnes ,","place":["France"]},{"name":"Universit\u00e9 Paris-Saclay, CNRS, INRAE, Univ Evry, Institute of Plant Sciences Paris-Saclay (IPS2), 91405 Orsay ,","place":["France"]},{"name":"Universit\u00e9 Paris-Saclay, AgroParisTech, INRAE, UMR MIA Paris-Saclay, 91120 Palaiseau ,","place":["France"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2025,8,6]]},"reference":[{"issue":"1","key":"2026021010571927200_qkaf046-B1","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0377-0427(96)00167-7","article-title":"On stirling numbers and euler sums","volume":"79","author":"Adamchik","year":"1997","journal-title":"Journal of Computational and Applied Mathematics"},{"issue":"5","key":"2026021010571927200_qkaf046-B2","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1002\/jae.v17:5","article-title":"Detecting multiple breaks in financial market volatility dynamics","volume":"17","author":"Andreou","year":"2002","journal-title":"Journal of Applied Econometrics"},{"issue":"3","key":"2026021010571927200_qkaf046-B3","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1111\/j.1368-423X.2006.00190.x","article-title":"Change-point monitoring in linear models","volume":"9","author":"Aue","year":"2006","journal-title":"The Econometrics Journal"},{"issue":"1","key":"2026021010571927200_qkaf046-B4","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF02458835","article-title":"Algorithms for the optimal identification of segment neighborhoods","volume":"51","author":"Auger","year":"1989","journal-title":"Bulletin of Mathematical Biology"},{"key":"2026021010571927200_qkaf046-B5","author":"Avis"},{"issue":"1","key":"2026021010571927200_qkaf046-B6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/jae.659","article-title":"Computation and analysis of multiple structural change models","volume":"18","author":"Bai","year":"2003","journal-title":"Journal of Applied Econometrics"},{"issue":"4","key":"2026021010571927200_qkaf046-B7","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/235815.235821","article-title":"The quickhull algorithm for convex hulls","volume":"22","author":"Barber","year":"1996","journal-title":"ACM Transactions on Mathematical Software: Association for Computing Machinery"},{"issue":"2","key":"2026021010571927200_qkaf046-B8","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1016\/S1053-8119(03)00406-3","article-title":"Automatic change detection in multimodal serial MRI: Application to multiple sclerosis lesion evolution","volume":"20","author":"Bosc","year":"2003","journal-title":"NeuroImage"},{"key":"2026021010571927200_qkaf046-B9","author":"Bresler"},{"key":"2026021010571927200_qkaf046-B10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1148-8","volume-title":"An introduction to convex polytopes","author":"Brondsted","year":"1983"},{"issue":"1","key":"2026021010571927200_qkaf046-B11","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/321556.321564","article-title":"An algorithm for convex polytopes","volume":"17","author":"Chand","year":"1970","journal-title":"Journal of the ACM"},{"issue":"4","key":"2026021010571927200_qkaf046-B12","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF02573985","article-title":"An optimal convex hull algorithm in any fixed dimension","volume":"10","author":"Chazelle","year":"1993","journal-title":"Discrete & Computational Geometry"},{"issue":"1","key":"2026021010571927200_qkaf046-B13","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1111\/rssb.12447","article-title":"High-dimensional, multiscale online changepoint detection","volume":"84","author":"Chen","year":"2022","journal-title":"Journal of the Royal Statistical Society: Series B, Statistical Methodology"},{"issue":"5","key":"2026021010571927200_qkaf046-B14","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","article-title":"Applications of random sampling in computational geometry, ii","volume":"4","author":"Clarkson","year":"1989","journal-title":"Discrete & Computational Geometry"},{"issue":"9","key":"2026021010571927200_qkaf046-B15","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1002\/joc.v23:9","article-title":"Comparison of techniques for detection of discontinuities in temperature series","volume":"23","author":"Ducr\u00e9-Robitaille","year":"2003","journal-title":"International Journal of Climatology"},{"issue":"4","key":"2026021010571927200_qkaf046-B16","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1080\/00401706.1978.10489697","article-title":"The use of MOSUMS for quality control","volume":"20","author":"Eiauer","year":"1978","journal-title":"Technometrics: A Journal of Statistics for the Physical, Chemical, and Engineering Sciences"},{"issue":"6","key":"2026021010571927200_qkaf046-B17","doi-asserted-by":"publisher","first-page":"2243","DOI":"10.1214\/14-aos1245","article-title":"Wild binary segmentation for multiple change-point detection","volume":"42","author":"Fryzlewicz","year":"2014","journal-title":"Annals of Statistics"},{"issue":"6","key":"2026021010571927200_qkaf046-B18","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1007\/s10514-017-9619-z","article-title":"Multipolicy decision-making for autonomous driving via changepoint-based behavior prediction: Theory and experiment","volume":"41","author":"Galceran","year":"2017","journal-title":"Autonomous Robots"},{"key":"2026021010571927200_qkaf046-B19","author":"Garreau"},{"key":"2026021010571927200_qkaf046-B20","author":"Habel"},{"key":"2026021010571927200_qkaf046-B21","author":"Hert"},{"issue":"2","key":"2026021010571927200_qkaf046-B22","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1109\/LSP.2001.838216","article-title":"An algorithm for optimal partitioning of data on an interval","volume":"12","author":"Jackson","year":"2005","journal-title":"IEEE Signal Processing Letters"},{"issue":"4","key":"2026021010571927200_qkaf046-B23","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.1111\/rssb.12501","article-title":"Testing for a change in mean after changepoint detection","volume":"84","author":"Jewell","year":"2022","journal-title":"Journal of the Royal Statistical Society, Series B"},{"key":"2026021010571927200_qkaf046-B24","author":"Kabluchko"},{"key":"2026021010571927200_qkaf046-B25","author":"Kenwright"},{"issue":"500","key":"2026021010571927200_qkaf046-B26","doi-asserted-by":"publisher","first-page":"1590","DOI":"10.1080\/01621459.2012.737745","article-title":"Optimal detection of changepoints with a linear computational cost","volume":"107","author":"Killick","year":"2012","journal-title":"Journal of the American Statistical Association"},{"issue":"19","key":"2026021010571927200_qkaf046-B27","doi-asserted-by":"publisher","first-page":"3763","DOI":"10.1093\/bioinformatics\/bti611","article-title":"Comparative analysis of algorithms for identifying amplifications and deletions in array CGH data","volume":"21","author":"Lai","year":"2005","journal-title":"Bioinformatics"},{"issue":"1","key":"2026021010571927200_qkaf046-B28","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1111\/jtsa.2000.21.issue-1","article-title":"Least-squares estimation of an unknown number of shifts in a time series","volume":"21","author":"Lavielle","year":"2000","journal-title":"Journal of Time Series Analysis"},{"issue":"4","key":"2026021010571927200_qkaf046-B29","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1016\/j.sigpro.2004.11.012","article-title":"Detecting multiple change-points in the mean of Gaussian process by model selection","volume":"85","author":"Lebarbier","year":"2005","journal-title":"Signal Processing"},{"issue":"1","key":"2026021010571927200_qkaf046-B30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-021-04221-5","article-title":"Increased peak detection accuracy in over-dispersed ChIP-seq data with supervised segmentation models","volume":"22","author":"Liehrmann","year":"2021","journal-title":"BMC Bioinformatics"},{"issue":"2","key":"2026021010571927200_qkaf046-B31","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s11222-016-9636-3","article-title":"On optimal multiple changepoint algorithms for large data","volume":"27","author":"Maidstone","year":"2017","journal-title":"Statistics and Computing"},{"issue":"8","key":"2026021010571927200_qkaf046-B32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.18637\/jss.v097.i08","article-title":"mosum: A package for moving sums in change-point analysis","volume":"97","author":"Meier","year":"2021","journal-title":"Journal of Statistical Software"},{"issue":"1","key":"2026021010571927200_qkaf046-B33","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(87)90086-X","article-title":"On-line construction of the convex hull of a simple polyline","volume":"25","author":"Melkman","year":"1987","journal-title":"Information Processing Letters"},{"issue":"12","key":"2026021010571927200_qkaf046-B34","doi-asserted-by":"publisher","first-page":"1605","DOI":"10.1109\/12.9737","article-title":"Efficient parallel convex hull algorithms","volume":"37","author":"Miller","year":"1988","journal-title":"IEEE Transactions on Computers"},{"issue":"4","key":"2026021010571927200_qkaf046-B35","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1093\/biostatistics\/kxh008","article-title":"Circular binary segmentation for the analysis of array-based dna copy number data","volume":"5","author":"Olshen","year":"2004","journal-title":"Biostatistics"},{"key":"2026021010571927200_qkaf046-B36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804120.005","volume-title":"Convex hulls in three dimensions","author":"O\u2019Rourke","year":"1998"},{"issue":"1\u20132","key":"2026021010571927200_qkaf046-B37","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1093\/biomet\/41.1-2.100","article-title":"Continuous inspection schemes","volume":"41","author":"Page","year":"1954","journal-title":"Biometrika"},{"issue":"1","key":"2026021010571927200_qkaf046-B38","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1186\/1471-2105-6-27","article-title":"A statistical approach for array CGH data analysis","volume":"6","author":"Picard","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2026021010571927200_qkaf046-B39","doi-asserted-by":"publisher","author":"Pishchagina","DOI":"10.57750\/9vvx-eq57"},{"issue":"2","key":"2026021010571927200_qkaf046-B40","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/359423.359430","article-title":"Convex hulls of finite sets of points in two and three dimensions","volume":"20","author":"Preparata","year":"1977","journal-title":"Communications of the ACM"},{"issue":"1","key":"2026021010571927200_qkaf046-B41","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0304-3975(79)90055-0","article-title":"Finding the intersection of n half-spaces in time o(nlogn)","volume":"8","author":"Preparata","year":"1979","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"2026021010571927200_qkaf046-B42","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1109\/TIP.2004.838698","article-title":"Image change detection algorithms: A systematic survey","volume":"14","author":"Radke","year":"2005","journal-title":"IEEE Transactions on Image Processing"},{"issue":"4","key":"2026021010571927200_qkaf046-B43","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s10514-012-9273-4","article-title":"Pliss: Labeling places using online changepoint detection","volume":"32","author":"Ranganathan","year":"2012","journal-title":"Autonomous Robots"},{"issue":"6","key":"2026021010571927200_qkaf046-B44","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1175\/JAM2493.1","article-title":"A review and comparison of changepoint detection techniques for climate data","volume":"46","author":"Reeves","year":"2007","journal-title":"Journal of Applied Meteorology and Climatology"},{"issue":"4","key":"2026021010571927200_qkaf046-B45","first-page":"180","article-title":"A pruned dynamic programming algorithm to recover the best segmentations with 1 to k_max change-points","volume":"156","author":"Rigaill","year":"2015","journal-title":"Journal de la Soci\u00e9t\u00e9 Fran\u00e7aise de Statistique"},{"issue":"81","key":"2026021010571927200_qkaf046-B46","first-page":"1","article-title":"Fast online changepoint detection via functional pruning CUSUM statistics","volume":"24","author":"Romano","year":"2023","journal-title":"Journal of Machine Learning Research"},{"issue":"2","key":"2026021010571927200_qkaf046-B47","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s10957-020-01762-2","article-title":"Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?","volume":"187","author":"Runge","year":"2020","journal-title":"Journal of Optimization Theory and Applications"},{"key":"2026021010571927200_qkaf046-B48","doi-asserted-by":"publisher","author":"Rybach","year":"2009","DOI":"10.1109\/ICASSP.2009.4960554"},{"issue":"3","key":"2026021010571927200_qkaf046-B49","doi-asserted-by":"publisher","first-page":"507","DOI":"10.2307\/2529204","article-title":"A cluster analysis method for grouping means in the analysis of variance","volume":"30","author":"Scott","year":"1974","journal-title":"Biometrics"},{"key":"2026021010571927200_qkaf046-B50","author":"Seidel"},{"issue":"2","key":"2026021010571927200_qkaf046-B51","doi-asserted-by":"publisher","first-page":"229","DOI":"10.51387\/23-NEJSDS51","article-title":"E-detectors: A nonparametric framework for sequential change detection.","volume":"2","author":"Shin","year":"2024","journal-title":"The New England Journal of Statistics in Data Science"},{"issue":"1","key":"2026021010571927200_qkaf046-B52","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1214\/aos\/1176324466","article-title":"Using the generalized likelihood ratio statistic for sequential detection of a change-point","volume":"23","author":"Siegmund","year":"1995","journal-title":"Annals of Statistics"},{"issue":"3-4","key":"2026021010571927200_qkaf046-B53","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.physa.2004.10.026","article-title":"A new method for change-point detection developed for on-line analysis of the heart beat variability during sleep","volume":"349","author":"Staudacher","year":"2005","journal-title":"Physica A-Statistical Mechanics and Its Applications"},{"issue":"1","key":"2026021010571927200_qkaf046-B54","doi-asserted-by":"publisher","first-page":"e1628","DOI":"10.1002\/wics.1628","article-title":"Sequential change-point detection: Computation versus statistical performance","volume":"16","author":"Wang","year":"2024","journal-title":"Wiley Interdisciplinary Reviews: Computational Statistics"},{"issue":"549","key":"2026021010571927200_qkaf046-B55","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1080\/01621459.2023.2235059","article-title":"Poisson-focus: An efficient online method for detecting count bursts with application to gamma ray burst detection","volume":"120","author":"Ward","year":"2025","journal-title":"Journal of the American Statistical Association"},{"issue":"3","key":"2026021010571927200_qkaf046-B56","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s11222-024-10416-6","article-title":"A constant-per-iteration likelihood ratio test for online changepoint detection for exponential family models","volume":"34","author":"Ward","year":"2024","journal-title":"Statistics and Computing"},{"key":"2026021010571927200_qkaf046-B57","author":"Wikipedia"},{"issue":"4","key":"2026021010571927200_qkaf046-B58","doi-asserted-by":"publisher","first-page":"1434","DOI":"10.1214\/aos\/1176346802","article-title":"Estimation of a noisy discrete-time step function: Bayes and empirical Bayes approaches","volume":"12","author":"Yao","year":"1984","journal-title":"Annals of Statistics"}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/88\/1\/171\/63967648\/qkaf046.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/88\/1\/171\/63967648\/qkaf046.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T15:57:23Z","timestamp":1770739043000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/88\/1\/171\/8223216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,6]]},"references-count":58,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,8,6]]},"published-print":{"date-parts":[[2026,2,10]]}},"URL":"https:\/\/doi.org\/10.1093\/jrsssb\/qkaf046","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026,2]]},"published":{"date-parts":[[2025,8,6]]}}}