The Use of Database Techniques in the Implementation of a Syntactic Pattern Recognition Task on a Parallel Reconfigurable Machine.

摘要

Use of syntactic pattern recognition has been shown to be an effective technique for picture processing; it is, however, computationally time-consuming. The way in which a paralled SIMD/MIMD machine, PASM, can be used to decrease the processing time of these tasks is examined. Paralled machines have been used predominantly for decreasing the processing time of numerical problems in which the data is frequently well-ordered. In contrast, a syntactic pattern recognition task would use a parallel machine to perform multiple search, comparison, and string manipulator operations on some relatively complex data structures. A solution to the problem of implementing a specific parallel syntactic pattern recognition task, a parallel tree automaton, through the use of a relational database and relational language is proposed. Use of a CODASYL database and database language is also investigated. Two algorithms for implementing the parallel tree automaton are described. The problem of obtaining a reasonable processor and data allocation scheme for the two algorithms and for the two relational programs derived from the two algorithms is discussed. A comparison of the different problems posed by each algorithm is made.