Frequent Approximate Substring Pattern Mining Using Locally Optimal Occurrence Counting

We propose a novel frequent approximate pattern mining in which occurrences themselves are valuable regions to extract. Given a string s, our mining task is to enumerate its sub strings that locally optimally match many sub strings of s. We show an algorithm for this problem whose time and space complexities are O(n³) for a string with length n. According to our experiments using synthetic data, our algorithm can correctly extract embedded frequent patterns as both patterns and their occurrences even if the embedded patterns are corrupted by random edit operations.