Title :
Work-time optimal k-merge algorithms on the PRAM
Author :
Hayashi, Tatsuya ; Nakano, Koji ; Olariu, Stephan
Author_Institution :
Dept. of Electr. & Comput. Eng., Nagoya Inst. of Technol., Japan
Abstract :
The k-merge problem, given a collection of k, (2⩽k⩽n), sorted sequences of total length a asks to merge them into a new sorted sequence. The main contribution of the work is to propose simple and intuitive work-time optimal algorithms for the k-merge problem on two PRAM models. Specifically their k-merge algorithms perform O(nlogk) work and run in O(log n) time on the EREW-PRAM and in O (log log n+log k) time on the CREW-PRAM, respectively
Keywords :
computational complexity; merging; parallel algorithms; sequences; CREW-PRAM; EREW-PRAM; PRAM models; sorted sequences; time complexity; work complexity; work-time optimal k-merge algorithms; Artificial intelligence; Bridges; Computer science; Databases; Information retrieval; Merging; Parallel algorithms; Phase change random access memory; Query processing; Sorting;
Conference_Titel :
Parallel Processing Symposium, 1997. Proceedings., 11th International
Conference_Location :
Genva
Print_ISBN :
0-8186-7793-7
DOI :
10.1109/IPPS.1997.580913
