Abstract
Monitoring of streamed data to detect abnormal behaviour (variously known as event detection, anomaly detection, change detection, or outlier detection) underlies many applications of the Internet of Things. There, one often collects data from a variety of sources, with asynchronous sampling, and missing data. In this setting, one can predict abnormal behavior using low-rank techniques. In particular, we assume that normal observations come from a low-rank subspace, prior to being corrupted by a uniformly distributed noise. Correspondingly, we aim to recover a representation of the subspace, and perform event detection by running point-to-subspace distance query for incoming data. In particular, we use a variant of low-rank factorisation, which considers interval uncertainty sets around "known entries", on a suitable flattening of the input data to obtain a low-rank model. On-line, we compute the distance of incoming data to the low-rank normal subspace and update the subspace to keep it consistent with the seasonal changes present. For the distance computation, we suggest to consider subsampling. We bound the one-sided error as a function of the number of coordinates employed using techniques from learning theory and computational geometry. In our experimental evaluation, we have tested the ability of the proposed algorithm to identify samples of abnormal behavior in induction-loop data from Dublin, Ireland.
Introduction
The Internet of Things (IoT) generates a massive "firehose" of information. In smart city applications, thousands of traffic sensors pulse at high frequencies, creating a data stream that is often voluminous, high-velocity, and "messy"—characterized by missing values and measurement noise. Traditional anomaly detection methods often struggle to scale or handle the inherent sparsity of this data. A key challenge is detecting events, such as accidents or equipment failures, in real-time without being overwhelmed by the dimensionality of the feature space.
The MODULoR Framework
The proposed framework, MODULoR (MOnitoring Distributed systems Using Low-Rank methods), addresses these challenges by modeling "normal" system behavior as a low-rank subspace. The approach consists of three primary stages:
- Data Flattening: Raw, asynchronous sensor streams are organized into a large matrix where each row represents a system "snapshot" (e.g., one day of traffic).
- Matrix Factorization with Interval Uncertainty: Instead of point estimates, the model assumes the "true" value of a sensor reading lies within an interval $[M_{ij} - \Delta, M_{ij} + \Delta]$. This robust factorization identifies the "normal" subspace while accounting for uniform noise and missing data.
- Subsampled Proximity Testing: To determine if new data is anomalous, its distance to the learned subspace is measured. Crucially, this test uses only a small random subset $s$ of coordinates, formulated as a Linear Programming (LP) feasibility problem.
Theoretical Guarantees
A significant contribution of this work is the proof that the number of samples $s$ required for a reliable proximity test depends on the rank ($r$) of the subspace and the desired error margin ($\epsilon$), but is independent of the total number of sensors ($n$). Using techniques from computational geometry and PAC (Probably Approximately Correct) learning, the authors demonstrate that the subsampled test has a bounded one-sided error. This independence from ambient dimension allows the system to monitor tens of thousands of sensors with the same computational efficiency as a much smaller network.
Experimental Evaluation and Results
The framework was evaluated using induction-loop traffic data from Dublin, Ireland, featuring 3,432 sensors over nearly a year. The system successfully handled 42% data sparsity without pre-imputation.
Performance and Adaptation
In high-dimensional tests (over 299,000 dimensions), the subsampled proximity test executed in approximately 0.009 seconds. The model also incorporates online adaptation, allowing the "normal" subspace to evolve with seasonal changes. As shown in the performance metrics, online factorization methods can maintain or even improve reconstruction accuracy as more samples are processed compared to static offline models.
The system achieved near-perfect F1-scores (1.0) for moderate noise levels, demonstrating high precision in distinguishing events from normal fluctuations even under synthetic noise injection.
Conclusion
MODULoR provides a scalable, robust solution for IoT event detection by leveraging low-rank structures and randomized subsampling. By decoupling detection complexity from the total number of sensors and providing theoretical guarantees on error bounds, it offers a path forward for real-time monitoring of massive-scale distributed systems.
Reference: Marecek, J., Maroulis, S., Kalogeraki, V., & Gunopoulos, D. (2021). Low-Rank Methods in Event Detection and Subsampled Point-to-Subspace Proximity Tests. arXiv:1802.03649v3.
Summary updated