Order-Preserving Multiple Pattern Matching in Parallel

Abstract

The order-preserving multiple pattern matching problem is to find all substrings of T whose relative orders are the same for any pattern in a set of patterns. Various sequential algorithms have been studied for the order-preserving multiple pattern matching problems. In this paper, we propose two parallel algorithms, each of which uses Aho–Corasick automata and fingerprint tables, respectively. We also present experimental results of comparing the execution times of each parallel algorithm on various types of time-series data.

Keywords

• string matching
• order-preserving multiple pattern matching
• parallel algorithms
• time-series data analysis