๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An efficient parallel algorithm for multiselection

โœ Scribed by S. Olariu; Z. Wen

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
211 KB
Volume
17
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

โœฆ Synopsis

Olariu, S. and Z. Wen, An efficient parallel algorithm for multiselection, Parallel Computing 17 (1991) 689-693.

The problem of multiselection arises frequently in databases. Here, given an unordered set S of n records and a sequence of m integers 1 ~< ql < q2 < .--< qm ~< n we are interested in answering queries of the type 'find the qAh smallest elements in S', the problem is to answer all these queries as fast as possible. We propose an efficient parallel algorithm for multiselection, running in O(n/p log2m) time using p processors with 1 ~< p ~< In/log n log* n], in the EREW-PRAM model.

๐Ÿ“œ SIMILAR VOLUMES

An efficient algorithm for parallel inte
An efficient algorithm for parallel integer multiplication
โœ Benjamin Singer; George Saon ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 67 KB

In this paper we propose an efficient algorithm to implement parallel integer multiplication by a combination of parallel additions, shifts and reads from a memoryresident lookup table dedicated to squares. Such an operator called PIM (parallel integer multiplication) is in fact microprogrammed at t

An efficient parallel sorting algorithm
An efficient parallel sorting algorithm
โœ Xiaoqing Liu; Junguk L. Kim ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 130 KB
An efficient clustering algorithm for pa
An efficient clustering algorithm for partitioning parallel programs
โœ Piyush Maheshwari; Hong Shen ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 254 KB

This paper presents a clustering algorithm that partitions node-labelled and edge-labelled ลฝ . directed acyclic precedence graphs APG into clusters such that all the clusters have balanced amount of computation load and there is only one communication path between any pair of clusters. The algorithm