Simple parallel algorithms to compute interval maxima

✍ Scribed by Koji Nakano; Nobuki Tokura; Toshimitsu Masuzawa

• Book ID: 104591495
• Publisher: John Wiley and Sons
• Year: 1992
• Tongue: English
• Weight: 866 KB
• Volume: 23
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690230501

✦ Synopsis

Abstract

The interval maxima problem is a problem to compute each interval maximum max{in(s~i~), …, in(t~i~)} for given n data in(O), …, in(n ‐ 1) and a number of intervals [s~1~, t~1~], [s~2~, t~2~]. The following result is already known:.

(1) On the CRCW‐PRAM, each interval maximum can be computed using a single processor in O(1) time, after preprocessing using n/log log n processors in O(log log n) time.

The following two algorithms are shown in this paper.

(2) On the CRCW‐PRAM, each interval maximum can be computed using a single processor in O(log log n) time, after preprocessing using n/log log n processors in O(log log n) time.

(3) On the CRCW‐PRAM, each interval maximum can be computed using a single processor O(1) time, after preprocessing using n^1ϵ^ processors in O(1) time for every fixed ϵ > 0.

These two algorithms are simpler than the algorithm (1). The preprocessing time in algorithm (3) is shorter than in (1), although a larger number of processors are employed.