Alphabet-independent optimal parallel search for three-dimensional patterns

AbstractWe give an alphabet-independent optimal parallel algorithm for the searching phase of three-dimensional pattern matching. All occurrences of a three-dimensional pattern P of shape m × m × m in a text T of shape n × n × n are to be found. Our algorithm works in log m time with O(N/ log(m)) processors on a CREW PRAM, where N = n3. Some ideas from [3] are used. We explore classification of two-dimensional periodicities of faces of the cubic pattern. Some projection techniques are developed to deal with three dimensions. The nonperiodicity implies some sparseness properties, while periodicity implies other special useful properties (i.e., monotonicity) of the set of occurrences. Both types of properties are used in deriving our algorithm. The advantage of our approach is that it is essentially two-dimensional, no special properties related to three dimensions and no new complicated data structures are considered, the resulting algorithm is rather simple.The search phase is preceded by the preprocessing phase (computation of the witness table). Our main results concern the searching phase, however, we present shortly a new approach to the second phase also. Usefulness of the dictionaries of basic factors (DBFs, see [9]), in the computation of the three-dimensional witness table is presented.Our algorithms can be easily adjusted to the case of unequally sided patterns