# Mondrian Forests: Efficient Online Random Forests

arXiv: https://arxiv.org/abs/1406.2673 · HTML: https://mlsanity.com/paper/1406.2673/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2014.

## Built on by (most cited first, 25 of 25)

- [Active learning for data streams: a survey](https://mlsanity.com/paper/2302.08893/) (2023)
- [Inference with Mondrian Random Forests](https://mlsanity.com/paper/2310.09702/) (2023)
- [BEDS-Bench: Behavior of EHR-models under Distributional Shift--A Benchmark](https://mlsanity.com/paper/2107.08189/) (2021)
- [Minimax Rates for High-Dimensional Random Tessellation Forests](https://mlsanity.com/paper/2109.10541/) (2021)
- [On Uncertainty Estimation by Tree-based Surrogate Models in Sequential Model-based Optimization](https://mlsanity.com/paper/2202.10669/) (2022)
- [Autoencoding Random Forests](https://mlsanity.com/paper/2505.21441/) (2025)
- [Reducing numerical precision preserves classification accuracy in Mondrian Forests](https://mlsanity.com/paper/2106.14340/) (2021)
- [Nonparametric Feature Selection by Random Forests and Deep Neural Networks](https://mlsanity.com/paper/2201.06821/) (2022)
- [Conditional Outcome Equivalence: A Quantile Alternative to CATE](https://mlsanity.com/paper/2410.12454/) (2024)
- [Learning Decision Trees as Amortized Structure Inference](https://mlsanity.com/paper/2503.06985/) (2025)
- [Efficient Adaptive Experimentation with Noncompliance](https://mlsanity.com/paper/2505.17468/) (2025)
- [Shape Modeling with Spline Partitions](https://mlsanity.com/paper/2108.02507/) (2021)
- [Mondrian Forest for Data Stream Classification Under Memory Constraints](https://mlsanity.com/paper/2205.07871/) (2022)
- [Filtration Surfaces for Dynamic Graph Classification](https://mlsanity.com/paper/2309.03616/) (2023)
- [TrIM: Transformed Iterative Mondrian Forests for Gradient-based Dimension Reduction and High-Dimensional Regression](https://mlsanity.com/paper/2407.09964/) (2024)
- [WildWood: a new Random Forest algorithm](https://mlsanity.com/paper/2109.08010/) (2021)
- [Extremely Simple Streaming Forest](https://mlsanity.com/paper/2110.08483/) (2021)
- [Dynamic Ensemble Size Adjustment for Memory Constrained Mondrian Forest](https://mlsanity.com/paper/2210.05704/) (2022)
- [Efficient Curriculum based Continual Learning with Informative Subset Selection for Remote Sensing Scene Classification](https://mlsanity.com/paper/2309.01050/) (2023)
- [TREE: Tree Regularization for Efficient Execution](https://mlsanity.com/paper/2406.12531/) (2024)
- [The Nah Bandit: Modeling User Non-compliance in Recommendation Systems](https://mlsanity.com/paper/2408.07897/) (2024)
- [The Uniformly Rotated Mondrian Kernel](https://mlsanity.com/paper/2502.04323/) (2025)
- [FraudFox: Adaptable Fraud Detection in the Real World](https://mlsanity.com/paper/2603.13014/) (2026)
- [CLeAN: Continual Learning Adaptive Normalization in Dynamic Environments](https://mlsanity.com/paper/2603.17548/) (2026)
- [Minimax Rates and Spectral Distillation for Tree Ensembles](https://mlsanity.com/paper/2605.11841/) (2026)

## Abstract (arXiv)

Ensembles of randomized decision trees, usually referred to as random forests, are widely used for classification and regression tasks in machine learning and statistics. Random forests achieve competitive predictive performance and are computationally efficient to train and test, making them excellent candidates for real-world prediction tasks. The most popular random forest variants (such as Breiman's random forest and extremely randomized trees) operate on batches of training data. Online methods are now in greater demand. Existing online random forests, however, require more training data than their batch counterpart to achieve comparable predictive performance. In this work, we use Mondrian processes (Roy and Teh, 2009) to construct ensembles of random decision trees we call Mondrian forests. Mondrian forests can be grown in an incremental/online fashion and remarkably, the distribution of online Mondrian forests is the same as that of batch Mondrian forests. Mondrian forests achieve competitive predictive performance comparable with existing online random forests and periodically re-trained batch random forests, while being more than an order of magnitude faster, thus representing a better computation vs accuracy tradeoff.