AN EREW-PRAM MULTIPLE SEARCHING AND MERGING ALGORITHM
Titel:
AN EREW-PRAM MULTIPLE SEARCHING AND MERGING ALGORITHM
Auteur:
Brown, Theodore Xiong, Renbing
Verschenen in:
International journal of parallel, emergent and distributed systems
Paginering:
Jaargang 3 (1994) nr. 1-2 pagina's 83-88
Jaar:
1994
Inhoud:
If we consider the knowledge of the insertion points of the items and one sorted sequence into another as solving the problem of merging two sequences, the merging of two sequences and the searching for multiple (sorted) values in a sequence can be considered as twin problems. Both, which we shall call the multiple ranking problem, can be phrased as determining the insertion or location point of one sequence in other In this paper we present a fast, easily implemented algorithm to solve the multiple ranking problem that is based on an EREW (exclusive read, exclusive write) PRAM model when the elements of each sequence are unique, i.e. when the sequences are in increasing order. Given two increasing sequences and p processors, our algorithm will solve the multiple ranking problem of B in A in O(⌈lg(m + n)⌉) where |A| = m, |B| = n, when p = n and in O(⌈lg(m + p/2)⌉ + (4n/p + 2n/p⌊lg(m/n)⌋) +c) when 1 < p < n ≤ m. The former is optimal when n = o(m) and the latter when p < 4n/lgm.
Tijdschrift beschrijving