# A Communication-Efficient Parallel Algorithm for Decision Tree

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2016.

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

- [Click-Through Rate Prediction in Online Advertising: A Literature Review](https://mlsanity.com/paper/2202.10462/) (2022)
- [Quantized Training of Gradient Boosting Decision Trees](https://mlsanity.com/paper/2207.09682/) (2022)
- [Diagnosis of COVID-19 Cases from Chest X-ray Images Using Deep Neural Network and LightGBM](https://mlsanity.com/paper/2203.14275/) (2022)
- [Cloud Collectives: Towards Cloud-aware Collectives forML Workloads with Rank Reordering](https://mlsanity.com/paper/2105.14088/) (2021)
- [Distributionally Robust Multi-Output Regression Ranking](https://mlsanity.com/paper/2109.12803/) (2021)
- [Predictive Modelling of Air Quality Index (AQI) Across Diverse Cities and States of India using Machine Learning: Investigating the Influence of Punjab's Stubble Burning on AQI Variability](https://mlsanity.com/paper/2404.08702/) (2024)
- [Gradient Boosting Decision Tree with LSTM for Investment Prediction](https://mlsanity.com/paper/2505.23084/) (2025)

## Abstract (arXiv)

Decision tree (and its extensions such as Gradient Boosting Decision Trees and Random Forest) is a widely used machine learning algorithm, due to its practical effectiveness and model interpretability. With the emergence of big data, there is an increasing need to parallelize the training process of decision tree. However, most existing attempts along this line suffer from high communication costs. In this paper, we propose a new algorithm, called Parallel Voting Decision Tree (PV-Tree), to tackle this challenge. After partitioning the training data onto a number of (e.g., M) machines, this algorithm performs both local voting and global voting in each iteration. For local voting, the top-k attributes are selected from each machine according to its local data. Then, globally top-2k attributes are determined by a majority voting among these local candidates. Finally, the full-grained histograms of the globally top-2k attributes are collected from local machines in order to identify the best (most informative) attribute and its split point. PV-Tree can achieve a very low communication cost (independent of the total number of attributes) and thus can scale out very well. Furthermore, theoretical analysis shows that this algorithm can learn a near optimal decision tree, since it can find the best attribute with a large probability. Our experiments on real-world datasets show that PV-Tree significantly outperforms the existing parallel decision tree algorithms in the trade-off between accuracy and efficiency.