An optimal parallel algorithm for merging using multiselection
type: Item
instance of: scholarly article
title: An optimal parallel algorithm for merging using multiselection
zbMATH Open document ID: 0808.68062
DOI: 10.1016/0020-0190(94)00009-3
author: Narsingh Deo
author: Muralidhar Medidi
author: Amit Kumar Jain
published in: Information Processing Letters
publication date: 1994-06-09T00:00:00Z
review text: This paper presents an optimal parallel algorithm for the construction of \((a,b)\)-trees -- a generalization of 2-3 trees, 2-3--4 trees, and \(B\)- trees. The authors show the existence of a canonical form for \((a,b)\)- trees, with a very regular structure, which allows them to obtain a scalable parallel algorithm for the construction of a minimum-height \((a,b)\)-tree with \(N\) keys in \(O(N/p + \log \log N)\) time using \(p \leq N/ \log \log N\) processors on the EREW-PRAM model, and \(O(N/p)\) time using \(p \leq N\) processors on the CREW-model. It is shown that the average memory utilization for the canonical form is at least 50\% better than that for the worst-case and is also better than that for a random \((a,b)\)-tree. A significant feature of the proposed parallel algorithm is that its time-complexity depends neither on \(a\) nor on \(b\), and hence this general algorithm is superior to earlier algorithms for parallel construction of \(B\)-trees.
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 562523
zbMATH Keywords: optimal parallel algorithm
zbMATH Keywords: scalable parallel algorithm
reviewed by: Naokant Deo
MaRDI profile type: MaRDI publication profile
full work available at URL: 0020-0190(94)00009-3
OpenAlex ID: W2044031350
cites work: Parallel approximation algorithms for bin packing
cites work: Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
cites work: Parallel Merge Sort
cites work: The complexity of selection and ranking in X+Y and matrices with sorted columns
cites work: Optimal merging and sorting on the EREW PRAM
cites work: Q4023519
cites work: Q3313267
cites work: Finding the maximum, merging, and sorting in a parallel computation model
cites work: Parallel merging: Algorithm and implementation results
Recommended article: Cost-optimal parallel algorithms for constructing B-trees
Recommended article: Q3719845
Recommended article: A unified approach to the parallel construction of search trees
Recommended article: Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree
description: scientific article; zbMATH DE number 562523