Accession Number : ADA213065

Title :   Novel Graph Searching Methods for Image Analysis.

Descriptive Note : Final rept.

Corporate Author : LNK CORP RIVERDALE MD

PDF Url : ADA213065

Report Date : Aug 1989

Pagination or Media Count : 60

Abstract : A generalization of the Artificial search algorithm, SSS*, is given, allowing it to handle incomplete and inconsistent data. A parallel formulation of the generalized SSS* is developed and implemented on a BBN Butterfly Plus parallel processor. In order to make the parallel version of SSS* as efficient as possible, a concurrent heap data structure (based on the work of Nageshwara and Kumar) is utilized. Theoretical speedup due to the use of the concurrent heap is shown. An automatic tree generator is developed to allow the testing of parallel SSS* on multiple trees. Empirical results are given for testing SSS* on 1 to 40 processors. Speedup proportional to the number of processors for up to 24 processors is achieved depending on the size of the search space. A procedure for achieving rapid output of solutions by using a tradeoff between the estimated complexity and quality of solutions was developed. Finally, future directions for research are presented. (RH)

Descriptors :   *ALGORITHMS, *AUTOMATIC, *GRAPHS, *IMAGE PROCESSING, *SEARCHING, *TREES, ESTIMATES, FORMULATIONS, GENERATORS, OUTPUT, PARALLEL ORIENTATION, QUALITY, SOLUTIONS(GENERAL), TRADE OFF ANALYSIS

Subject Categories : Computer Programming and Software
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE