Communication Efficient Construction of Decision Trees over Heterogeneously Distributed Data

We present an algorithm designed to efficiently construct a decision tree over heterogeneously distributed data without centralizing. We compare our algorithm against a standard centralized decision tree implementation in terms of accuracy as well as the communication complexity. Our experimental results show that by using only 20 % of the communication cost necessary to centralize the data we can achieve trees with accuracy at least 80 % of the trees produced by the centralized version