Scaling stream-based decision trees on a distributed dataflow engine

In many modern applications, data is produced continuously at high rates, making it necessary to process and learn from observations online. Streaming Machine Learning (SML) addresses this setting by updating models incrementally under strict latency and memory constraints. Among SML methods, decision-tree learners are attractive due to their interpretability and strong performance. Designing scalable distributed implementations of these learners, however, is challenging: the statistical requirements of online learning must be reconciled with asynchrony, coordination costs, and state management in distributed execution. This thesis presents the design and implementation of a distributed Vertical Hoeffding Tree (VHT) learner on top of Renoir, a high-performance distributed dataflow runtime written in Rust. The system exploits vertical parallelism by partitioning expensive feature-wise statistics updates across parallel workers, while maintaining a centralized global model to preserve structural consistency. We address key challenges that emerge in high-rate streaming deployments through practical optimizations, including memory reclamation for obsolete state, efficient support for varied feature representations, and buffering/coordination mechanisms that reduce model staleness under asynchronous processing. Our experimental evaluation studies how architectural choices affect the tradeoff between throughput and predictive quality. Results show that the proposed implementation preserves predictive behavior comparable to a centralized learner while substantially improving throughput and scalability. Overall, this work demonstrates that complex, stateful online learning can be embedded effectively in a distributed dataflow system, achieving high scalability without sacrificing statistical correctness.

In molte applicazioni moderne, i dati vengono prodotti continuamente ad alto ritmo, rendendo necessario elaborarli e apprendere dalle osservazioni in modalità online. Lo Streaming Machine Learning (SML) si inserisce in questo contesto aggiornando i modelli in modo incrementale, sotto vincoli stringenti di latenza e memoria. Tra gli approcci SML, gli apprenditori basati su alberi decisionali sono particolarmente interessanti per la loro interpretabilità e per le buone prestazioni. Progettare implementazioni distribuite e scalabili di questi modelli, tuttavia, è complesso: i requisiti statistici dell’apprendimento online devono essere conciliati con l’asincronia, i costi di coordinamento e la gestione dello stato tipici dell’esecuzione distribuita. Questa tesi presenta la progettazione e l’implementazione di un apprenditore Vertical Hoeffding Tree (VHT) distribuito, realizzato su Renoir, un runtime dataflow distribuito ad alte prestazioni scritto in Rust. Il sistema sfrutta il parallelismo verticale partizionando tra worker paralleli gli aggiornamenti costosi delle statistiche per feature, mantenendo al contempo un modello globale centralizzato per preservare la consistenza strutturale dell’albero. Affrontiamo le principali sfide che emergono in scenari di streaming ad alto tasso di arrivo tramite ottimizzazioni pratiche, tra cui la reclamazione della memoria per stato obsoleto, il supporto efficiente a diverse rappresentazioni delle feature e meccanismi di buffering e coordinamento che riducono la staleness del modello in presenza di elaborazione asincrona. La nostra valutazione sperimentale analizza come le scelte architetturali influenzino il compromesso (trade-off) tra throughput e qualità predittiva. I risultati mostrano che l’implementazione proposta preserva un comportamento predittivo comparabile a quello di un apprenditore centralizzato, migliorando in modo sostanziale throughput e scalabilità. Nel complesso, questo lavoro dimostra che una logica di apprendimento online complessa e stateful può essere integrata efficacemente in un sistema dataflow distribuito, ottenendo elevata scalabilità senza sacrificare la correttezza statistica.