
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1993  Copyright 1993 Universität Bonn, Institut für Informatik, Abt. V  
85101

AlphabetIndependent Optimal Parallel Search for ThreeDimensional Patterns
Marek Karpinski, Wojciech Rytter [Download PostScript] [Download PDF]
We give an alphabetindependent optimal parallel algorithm for the searching phase of threedimensional patternmatching. All occurrences of a three dimensional pattern P of shape $m \times m \times m$ in a text T of shape $n \times n \times n$ are to be found. Our algorithm works in $\log m$ time with ${\mathcal O}(N/\log(m))$ processors of a {\em CREW PRAM}, where $N = n^3$. The ideas from [3] are used. Surprisingly, the extension of the two dimensional matching to the three dimensional one is not a trivial modification. The searching phase in three dimensions explores classification of twodimensional periodicities of the cubic pattern. Some projection techniques are developed to deal with three dimensions. The periodicites of the patern with respect to its faces are investigated. The nonperiodicities imply some sparseness properties, while periodicities imply other special useful properties ({\it i.e.} monotonicity) of the set of occurrences. Both types of properties are useful in deriving an efficient algorithm. 

Last Change:
09/01/04 at 08:41:20
English 
Universität Bonn > Institut für Informatik > Abteilung V 