Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1995 Copyright 1995 University of Bonn, Department of Computer Science, Abt. V
85139

Alphabet Independent Optimal Parallel Search for Three-Dimensional Patterns (Revised Version)
Marek Karpinski, Wojciech Rytter
[Download PostScript] [Download PDF]

We 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 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 (DBF's), 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. A preliminary version of this paper was presented in [15].

Last Change: 07/26/04 at 11:47:37
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V