RS-Forest for anomaly detection

[MaxHalford]

See RS-Forest: A Rapid Density Estimator for Streaming Anomaly Detection. The authors say that they are more efficient than half-space trees, it might be worth a try!