Finding all nearest smaller values on a distributed memory machine
Author:Jyrki Katajainen
Published in:Proceedings of the Computing: The 2nd Australasian Theory Symposium, Australian Computer Science Communications 18,3, Computer Science Association (Australia) (1996), 100-107
Full text:<ps.gif>PS (165 kB)  
Abstract:Let A = [aj]j=1n be a sequence of n elements drawn from some totally ordered set. In the all nearest smaller values problem the task is to find for each aj, j ∈ {1, 2,…, n}, the elements ai and ak such that i = max{h ∈ {1,…, j} ∣ ah < aj} and k = min{h ∈ {j,…, n} ∣ ah < aj}, if such elements exist. In this paper it is shown that this problem can be solved in O(n / q) time and O(n) space with q processors on a distributed memory machine, provided that q ∈ {1, 2,…, O(n / log2 n)}. More precisely, the machine considered consists of q processors and q memory modules connected by a communication network, which allows every processor to access any memory module in constant time if only every memory module is accessed by at most one processor at a time. The result proved complements the earlier known results showing that, on a CREW PRAM, Ω(log2 n) is a lower bound for the time complexity of the problem with any number of processors and that, on a hypercube, any O(log2 n) algorithm must use Ω(n) processors.
Related:<html.gif>HTML (Technical report)  
  author = {Jyrki Katajainen},
  title = {Finding all nearest smaller values on a distributed memory machine},
  booktitle = {Proceedings of the Computing: The 2nd Australasian Theory
  series = {Australian Computer Science Communications},
  volume = {18},
  number = {3},
  publisher = {Computer Science Association (Australia)},
  year = {1996},
  pages = {100--107},
This page was generated by Jyrki Katajainen <> on 31.12.2011.