Parallel Construction Of (A, B)-Trees

    Authors

    N. Deo; A. Jain;M. Medidi

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    J. Parallel Distrib. Comput.

    Keywords

    B-TREES; ALGORITHMS; OPERATIONS; 2, 3-TREES; Computer Science, Theory & Methods

    Abstract

    We present an optimal parallel algorithm for the construction of(a, b)-trees-a generalization of 2-3 trees, 2-3-4 trees, and B-trees. We show the existence of a canonical form for (a, b)-trees, with a very regular structure, which allows us 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 less than or equal to N/log log N processors on the EREW-PRAM model, and in O(N/p) time using p less than or equal to N processors on the CREW model. We show 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 our general algorithm is superior to earlier algorithms for parallel construction of B-trees. (C) 1994 Academic Press, Inc.

    Journal Title

    Journal of Parallel and Distributed Computing

    Volume

    23

    Issue/Number

    3

    Publication Date

    1-1-1994

    Document Type

    Note

    Language

    English

    First Page

    442

    Last Page

    448

    WOS Identifier

    WOS:A1994PU61700016

    ISSN

    0743-7315

    Share

    COinS