[SPARK-21624] Optimize communication cost of RF/GBT/DT

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Incomplete
• Affects Version/s: 2.3.0
• Component/s: ML, MLlib
• Labels: bulk-closed
• Assignee: Unassigned
• Reporter: Peng Meng
• Created: 03/Aug/17 07:31
• Updated: 08/Oct/19 05:44
• Resolved: 08/Oct/19 05:44

Description

The implementation of RF is bound by either the cost of statistics computation on workers or by communicating the sufficient statistics.

The statistics are stored in allStats:

  /**
   * Flat array of elements.
   * Index for start of stats for a (feature, bin) is:
   *   index = featureOffsets(featureIndex) + binIndex * statsSize
   */
  private var allStats: Array[Double] = new Array[Double](allStatsSize)

The size of allStats maybe very large, and it can be very sparse, especially on the nodes that near the leave of the tree.

I have changed allStats from Array to SparseVector, my tests show the communication is down by about 50%.

Issue Links

• links to: [Github] Pull Request #18904 (mpjlu)