Resilient Pattern Mining

Abstract

Frequent pattern mining is a flagship problem in data mining. In its most basic form, it asks for the set of substrings of a given string S of length n that occur at least τ times in S, for some integer τ ϵ[1,n]. We introduce a resilient version of this classic problem, which we term the (τ, k)-Resilient Pattern Mining (rpm) problem. Given a string S of length n and two integers τ, k in[1, n, RPM asks for the set of substrings of S that occur at least τ times in S, even when the letters at any k positions of S are substituted by other letters. Unlike frequent substrings, resilient ones account for the fact that changes to string S are often expensive to handle or are unknown. We make the following contributions. First, we present RPM-DP, a simple exact O(n³k n)-time and O(n²)-space algorithm for RPM that is based on an existing dynamic programming algorithm. Second, we propose RPM-ESA, an exact O(n log n) -time and O(n) -space algorithm for RPM, which employs advanced data structures and combinatorial insights. Third, we conduct experiments on real large-scale datasets from different domains demonstrating that: (I) The notion of resilient substrings is useful in analyzing genomic data and fundamentally different from that of frequent substrings, as frequent substrings are often not resilient and thus do not remain frequent for long in versioned datasets; (II) RPM-ESA is several orders of magnitude faster and more space-efficient than RPM-DP; and (III) Clustering based on resilient substrings is effective.