Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-93-152

Optimal parallel string algorithms: sorting, merching and computing the minimum

Hagerup, Torben

MPI-I-93-152. 1993, 25 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We study fundamental comparison problems on
strings of characters, equipped with the usual
lexicographical ordering.
For each problem studied, we give a parallel algorithm
that is optimal with respect to at least one
criterion for which no optimal
algorithm was previously known.
Specifically, our main results are:
%
\begin{itemize}
\item Two sorted sequences of strings, containing
altogether $n$~characters, can be merged in
$O(\log n)$ time using $O(n)$ operations
on an EREW PRAM.
This is optimal as regards both the running time
and the number of operations.

\item A sequence of strings, containing altogether
$n$~characters represented by integers of size
polynomial in~$n$, can be sorted
in $O({{\log n}/{\log\log n}})$ time
using $O(n\log\log n)$ operations on
a CRCW PRAM.
The running time is optimal for any
polynomial number of processors.

\item The minimum string in a sequence of strings
containing altogether $n$ characters can be
found using (expected) $O(n)$ operations in
constant expected time on a randomized
CRCW PRAM, in $O(\log\log n)$ time on a
deterministic CRCW PRAM with a program depending on~$n$,
in $O((\log\log n)^3)$ time on a
deterministic CRCW PRAM with a program
not depending on~$n$,
in $O(\log n)$ expected time on a randomized
EREW PRAM, and in $O(\log n\log\log n)$ time
on a deterministic EREW PRAM.
The number of operations is optimal, and
the running time is optimal for the randomized algorithms
and, if the number of processors is limited to~$n$,
for the nonuniform deterministic CRCW
PRAM algorithm as wel
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-93-152.pdfMPI-I-93-152.pdf14191 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-152
Hide details for BibTeXBibTeX
@TECHREPORT{Hagerup93,
  AUTHOR = {Hagerup, Torben},
  TITLE = {Optimal parallel string algorithms: sorting, merching and computing the minimum},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-93-152},
  YEAR = {1993},
  ISSN = {0946-011X},
}