Proceedings of IEEE Symposium on Parallel and Distributed Processing
(SPDP'96), New Orleans, October 1996, pp. 496-503.
Ömer Egecioglu and Maximilian Ibel
Parallel Algorithms for Fast Computation of Normalized Edit Distances
Abstract.
We give work-optimal and polylogarithmic time parallel algorithms
for solving the normalized edit distance problem. The normalized
edit distance between two strings X and Y with lengths n >= m
is the minimum quotient of the sum of the costs of edit
operations transforming X into Y by the length of the edit path
corresponding to those edit operations. Marzal and Vidal proposed a
sequential algorithm with a time complexity of O(nm^2). We show
that this algorithm can be parallelized work-optimally on an array
of n (or m) processors, and on a mesh of n x m processors.
We then propose a sublinear time algorithm that is
almost work-optimal: using O(mn^{1.75}) processors, the time
complexity of the algorithm is O(n^{0.75} log n) and the total
number of operations is O(mn^{2.5}.log n). This algorithm
runs on a CREW PRAM, but is likely to work an weaker PRAM models
and hypercubes with minor modifications. Finally, we present a
polylogarithmic O(log^2 n) time algorithm based on matrix
multiplication which runs on a O(n^6/log n) processor hypercube.
omer@cs.ucsb.edu