2016 · 24 citations · 54 references
ComputingComputer EngineeringComputer ScienceComputational GeometryParallel AlgorithmsParallel ComputingData ParallelismDistributed Data ProcessingParallel Computational GeometryHistogramsJoin AlgorithmsLoad Balancing ModelsParallel Join AlgorithmsSkew MitigationTiling SchemesTiling Strategies
We address the problem of load balancing for parallel joins.We show that the distribution of input data received and the output data produced by worker machines are both important for performance. As a result, previous work, which optimizes either for input or output, stands ineffective for load balancing. To that end, we propose a multi-stage load-balancing algorithm which considers the properties of both input and output data through sampling of the original join matrix. To do this efficiently, we propose a novel category of equi-weight histograms. To build them, we exploit state-of-the-art computational geometry algorithms for rectangle tiling. To our knowledge, we are the first to employ tiling algorithms for join load-balancing. In addition, we propose a novel, join-specialized tiling algorithm that has drastically lower time and space complexity than existing algorithms. Experiments show that our scheme outperforms state-of-the-art techniques by up to a factor of 15.
54
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
Hung‐Chih Yang, Ali Dasdan, Ruey-Lung Hsiao et al. · 2007 · 717 citations
Sergey Melnik, Andrey Gubarev, Jing Jing Long et al. · Proceedings of the VLDB Endowment · 2010 · 709 citations