Research map / Label-efficient and robust learning / OOD and anomaly detection
Online Isolation Forest
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Online-iForest, a streaming anomaly detector that maintains an ensemble of data-dependent multi-resolution histograms (online-iTrees) updated by learning new points and forgetting old ones via a sliding window.
Problem
Anomaly detection on endless data streams under single-pass and memory constraints, where offline methods go stale and existing online methods rely on periodic retraining.
Approach
Each tree is a d-dimensional histogram whose bins split when they reach a height threshold (eta*2^depth) and merge when they fall below it, with a sliding window supplying both learning and forgetting updates per sample; anomaly scores use IFOR-style average leaf depth normalized by a window-dependent constant.
Key results
- Online-iForest achieves the lowest execution time on all datasets, e.g., 29.95 s median versus 142.57 s for iForestASD and 1274.45 s for RRCF across 11 datasets.
- Median ROC AUC of 0.866 for Online-iForest versus 0.863 for iForestASD; iForestASD has the best mean rank (1.583 vs 2.167), and the Nemenyi test finds it statistically better in AUC.
- On Mulcross, HST achieves an AUC of 0.011 while Online-iForest achieves 0.995, attributed to anomaly clusters being dense and large.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Online-iForest instead of competing methods | Online anomaly detection on stationary datasets · 11 stationary datasets | execution time (seconds): 29.95 vs 142.57 median | Helped |
| Use Online-iForest instead of the strongest AUC-performing alternatives | Online anomaly detection · 11 stationary datasets | ROC AUC: 0.866 vs 0.863 median | Mixed |
| Use Online-iForest under distribution changes | Online anomaly detection · INSECTS | ROC AUC | Mixed |
Surprising findings
- HST's AUC collapses to 0.011 on Mulcross, below chance, because anomaly clusters are large and as dense as genuine ones.
- Online-iForest is not statistically better than RRCF in AUC despite being much faster, and iForestASD has the top mean rank in AUC.
Limitations
- Relies on a sliding window of size omega, so the window must be stored in memory and the method is not fully window-free.
- The split threshold eta must be set by the user and is not automatically selected.
- Under concept drift on INSECTS, all tested methods are affected similarly and none consistently maintains performance after a change.
Experimental setup
Datasets: Donors Http ForestCover fraud Mulcross Smtp Shuttle Mammography nyc_taxi_shingle Annthyroid Satellite INSECTS
Benchmarks: Donors Http ForestCover fraud Mulcross Smtp Shuttle Mammography nyc_taxi_shingle Annthyroid Satellite INSECTS
Metrics: ROC AUC execution time
Baselines: iForestASD Half Space Trees Robust Random Cut Forest LODA
Builds on: Isolation Forest Half Space Trees LODA Robust Random Cut Forest
Closest papers by meaning
- Online Adaptive Anomaly Thresholding with Confidence Sequences (ICML 2024 · similarity 0.85)
- SEAD: Unsupervised Ensemble of Streaming Anomaly Detectors (ICML 2025 · similarity 0.84)
- MoniTor: Exploiting Large Language Models with Instruction for Online Video Anomaly Detection (NeurIPS 2025 · similarity 0.83)
- A Comprehensive Augmentation Framework for Anomaly Detection (AAAI 2024 · similarity 0.82)
- AR-Pro: Counterfactual Explanations for Anomaly Repair with Formal Properties (NeurIPS 2024 · similarity 0.81)
- Graph Anomaly Detection as Dynamical Transport: Training-Free Scoring via Empirical Bayes (NeurIPS 2026 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.