Abstract
Approximate string matching has been widely applied in various research and application domains including computational biology, information retrieval, and voice recognition. For an input text, the approximate string matching technique finds all positions of substrings that are approximately matched by a given pattern. Online approximate string matching, the searching without preprocessing the text, has been studied during recent decades. In these years, several researchers focused on accelerating approximate string matching using parallel computing; however, these works only applied a straightforward parallel approach and have room for improvement. As the complexity of information rapidly increase, the matching algorithm demands for better performance. In this work, we propose a novel parallel algorithm called high-density parallelism for online approximate string matching. The main idea of high-density parallelism is to distribute many light-weight threads on every character to perform the matching. Under such parallel architecture, we develop several strategies to decrease the workload of threads, including making the memory usage independent of pattern size. Experiments show that the proposed parallel algorithm reduces the matching runtime much better than traditional parallel approach, especially for large patterns. Based on the state-of-the-art serial algorithms and different parallel approaches, we provide a comprehensive parallel study for online approximate string matching.