Optimization of Position Finding Step of PCM-oMaRS Algorithm with Statistical Information

Ammar Balouch

Department of Computer Science, University of Rostock, Germany

Abstract: The PCM-oMaRS algorithm guarantees the maximal reduction steps of the computation of the exact median in distributed datasets and proved that we can compute the exact median effectively with reduction of blocking time and without needing the usage of recursive or iterative methods anymore. This algorithm provided more efficient execution not only in distributed datasets even in local datasets with enormous data. We cannot reduce the steps of PCM-oMaRS algorithm any more but we have found an idea to optimize one step of it. The most important step of this algorithm is the step in which the position of exact median will be determinate. For this step, we have development a strategy to achieve more efficiency in determination of position of exact median. Our aim in this paper to maximize the best cases of our algorithm and this was achieved through dividing the calculation of number of all value that smaller than or equal to temporary median in two groups: The first one contains only the values that smaller than the temporary median and the second group contains the values that equal to the temporary median. In this dividing we achieve other best cases of PCM-oMaRS algorithm and reducing the number of values that are required to compute the exact median. The complexity cost of this algorithm will be discussed more in this article. In addition some statistical information depending on our implementation tests of this algorithm will be given in this paper.

 Keywords: Median, parallel computation, algorithm, optimization, big data, evaluation, analysis, complexity costs

 Received June 11, 2015; accepted October 18, 2015