Distributed Processing and A Parallel Algorithm for Merging Relaxed Min-Max Heaps


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 5, pp. 1162-1171, May. 1998
10.3745/KIPSTE.1998.5.5.1162,   PDF Download:

Abstract

This paper presents a data structure that implements a mergable double-ended priority queue : namely an improved relaxed min-max-pair heap. By means of this new data structure, we suggest a parallel algorithm to merge priority queues organized in two relaxed heaps of different sizes, n and k, respectively. This new data-structure eliminates the blossomed tree and the lazying method used to merge the relaxed min-max heaps in [9]. As a result, employing max(2^i-1,[(m 1/4)]) processors, this algorithm requires O(log(log(n/k))?log(k)) time. Also, on the MarPar machine, this method achieves a 35.205-fold speedup with 64 processors to merge 8 million data items which consist of two relaxed min-max heaps of different sizes.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
M. Y. Sik, "Distributed Processing and A Parallel Algorithm for Merging Relaxed Min-Max Heaps," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 5, no. 5, pp. 1162-1171, 1998. DOI: 10.3745/KIPSTE.1998.5.5.1162.

[ACM Style]
Min Yong Sik. 1998. Distributed Processing and A Parallel Algorithm for Merging Relaxed Min-Max Heaps. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 5, 5, (1998), 1162-1171. DOI: 10.3745/KIPSTE.1998.5.5.1162.