Sequential Change-point Detection for High-dimensional and non-Euclidean Data

Abstract

In many applications, it is often of practical and scientific interest to detect anomaly events in a streaming sequence of high-dimensional or non-Euclidean observations. We study a non-parametric framework that utilizes nearest neighbor information among the observations to detect changes in an online setting. It can be applied to data in arbitrary dimension and non-Euclidean data as long as a similarity measure on the sample space can be defined. We consider new test statistics under this framework that can detect anomaly events more effectively than the existing test while keeping the false discovery rate controlled at a fixed level. Analytic formulas approximating the average run lengths of the new approaches are derived to make them fast applicable to modern datasets. Simulation studies are provided to support theoretical results. The proposed approach is illustrated with an analysis of the NYC taxi dataset.

References in corpus (7)

• Inferring change points in the COVID-19 spreading reveals the effectiveness of interventions
• Sequential multi-sensor change-point detection
• A new graph-based two-sample test for multivariate and object data
• Real-Time Nonparametric Anomaly Detection in High-Dimensional Settings
• Concept Drift and Anomaly Detection in Graph Streams
• A weighted edge-count two-sample test for multivariate and object data
• Large-Scale Multi-Stream Quickest Change Detection via Shrinkage Post-Change Estimation

Cited by in corpus (4)

• Online Change-Point Detection in High-Dimensional Covariance Structure with Application to Dynamic Networks
• Weighted-Graph-Based Change Point Detection
• Asymptotic Distribution-free Change-point Detection for Modern Data Based on a New Ranking Scheme
• Online network change point detection with missing values and temporal dependence