Cost-Optimal Parallel Algorithms for Constructing B-Trees.
Journal
Inf. Sci.
Journal Volume
81
Journal Issue
1-2
Pages
55-72
Date Issued
1994
Author(s)
Wang, Biing-Feng
Abstract
In this paper two cost-optimal parallel algorithms are presented for constructing a B-tree for a sorted list of N keys. These two parallel algorithms are designed on the shared-memory SIMD computer: one, based on the EREW model, uses N loglog N processors and requires O(loglog N) time; the other, based on the CREW model, uses N processors and requires O(1) time. © 1994.
Other Subjects
Computational complexity; Data storage equipment; Data structures; Mathematical models; Optimal systems; Parallel processing systems; Program processors; Trees (mathematics); B trees; Cost optimal parallel algorithms; Algorithms
Type
journal article