Kitsuregawa and Ogawa

• They have described following algorithms : (i) Bucket converging parallel hash join : A parallelization of the basic grace join. Relation R is partitioned into p buckets ( where p is much greater than k ). All of R is redistributed in this phase. Next size of each bucket is examined and if necessary enough buckets are redistributed such that sum of the buckets at every processor is balanced. This is repeated with relation S and in the last phase the local buckets are joined.
• (ii) Bucket spreading parallel hash: The first phase susceptible to RS . So the second bucket partitioning algorithm is forwarded wherein the buckets are partitioned horizontally across all available processors.During the second phase Omega network is used to redistribute the buckets onto the nodes for the local join operation.
• Result : Simulation results are presented for the AVS modeled using Zipfian distribution . - Uniformly distributed data has equal performance - Bucket spreading Algo reduces effective RS in the presence of increasing AVS. - In comparison to the WR and VP algos the above 2 algos have higher response time.