Algorithms for string searching on a Beowulf cluster
Kattamuri, Kishore Ramakrishna
MetadataShow full item record
String matching is a subject of both theoretical and practical interest in computer science. Theoretically, time and space complexity of the algorithms and on the practical side searching for keywords, names, phrases etc., is common. Searching for patterns in DNA (Deoxyribose Nucleic Acid) is one such application and is the ultimate area for this study. This study resulted in efficient parallel way to search for patterns, the program being operated on a parallel computer. This research provides basis for a further study and help in selecting the search algorithms for broader use. The algorithms proposed in this research try to solve the problem in both the single pattern and multiple pattern search areas. The outcome of this study was very encouraging and paved path for the possible future study. The algorithms were written in C using the MPI model on the Beowulf cluster of Florida Tech (Bluemarlin). The timings were compared against each other. The test data set used was kept uniform throughout the experiments. Though several ideas were formulated and were tried to be implemented in the search, only three algorithms (KTV, KTV2 and KPrime) were designed. Of these, KTV and KTV2 showed good results where as the KPrime took lot more time than expected. Investigation on the algorithm revealed a further tweaking which is left as a prt for future study.