Resilient Pattern Mining

Pengxin Bian, Panagiotis Charalampopoulos, Lorraine A. K. Ayad, Manal Mohamed, Solon P. Pissis, Grigorios Loukides · 2025

Read Resilient Pattern Mining by Pengxin Bian, Panagiotis Charalampopoulos, Lorraine A. K. Ayad, Manal Mohamed, Solon P. Pissis, Grigorios Loukides (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-04935.txt.

Introduction

Pengxin Bian and five co-authors pose a tougher version of a classic data mining problem in a twenty twenty-five paper. The classic task finds substrings that occur often in a long string. Real data, though, gets edited, and a pattern that breaks under a few letter swaps may be of little use.

Their resilient version asks for substrings that stay frequent even if any k letters in the string are swapped out. They give an exact algorithm that runs fast and uses modest memory. On large real data sets, resilient patterns proved more useful for genome work than plain frequent ones, and the method beat a baseline by a wide margin.

Catalog record

CREATORPengxin Bian, Panagiotis Charalampopoulos, Lorraine A. K. Ayad, Manal Mohamed, Solon P. Pissis, Grigorios Loukides
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-04935

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Resilient Pattern Mining Pengxin Bian, Panagiotis Charalampopoulos, Lorraine A. K. Ayad, Manal Mohamed, Solon P. Pissis, Grigorios Loukides 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 S of length n n that occur at least τ \tau times in S S , for some integer τ ∈ [ 1 , n ] \tau\in[1,n] . We introduce a resilient version of this classic problem, which we term the ( τ , k ) (\tau,k) -Resilient Pattern Mining ( RPM ) problem. Given a string S S of length n n and two integers τ , k ∈ [ 1 , n ] \tau,k\in[1,n] , RPM asks for the set of substrings of S S that occur at least τ \tau times in S S , even when the letters at any k k positions of S S are substituted by other letters. Unlike frequent substrings, resilient ones account for the fact that changes to string S S are often expensive to handle or are unknown. We propose an exact 𝒪 ⁡ ( n ​ log ⁡ n ) \mathcal{O}(n\log n) -time and 𝒪 ⁡ ( n ) \mathcal{O}(n) -space algorithm for RPM , which employs advanced data structures and combinatorial insights. We then present experiments on real large-scale datasets from different domains demonstrating that: (I) The notion of resilient substrings is useful in analyzing genomic data and is more powerful than that of frequent substrings, in scenarios where resilience is required, such as in the case of versioned datasets; (II) Our algorithm is several orders of magnitude faster and more space-efficient than a baseline algorithm that is based on dynamic programming; and (III) Clustering based on resilient substrings is effective. 1 Introduction Given a string S=S[0\mathinner{.\,.}n-1] of length n and an integer \tau\in[1,n] , the classic frequent pattern mining (FPM) problem [ FHK05 , FHK06 , DPT12 ] asks for the set of substrings of S that occur at least \tau times in S . These substrings are referred to as \tau -frequent . We introduce a resilient version of FPM, which we term the (\tau,k) -Resilient Pattern Mining ( RPM ) problem. Informally stated, given a string S of length n and integers \tau,k\in[1,n] , RPM asks for the set of substrings of S that occur at least \tau times in S , even when any k positions of S undergo letter substitutions. Clearly, RPM is a generalization of the FPM problem; it corresponds to the (\tau,0) -RPM case. Example 1 . Let S=\texttt{aaabaaaabbaaa} , \tau=2 , and k=1 . The output of (\tau,k) -Resilient Pattern Mining is \{\texttt{aaa},\texttt{aa},\texttt{a},\texttt{b}\} . Each such substring is (2,1) -resilient as it has (at least) two occurrences in S even after the letter in any single position of S is substituted. For example, the substring aaa of S is 2 -frequent in S^{\prime}=\texttt{\lx@text@underline{aaa}ba{\color[rgb]{1,0,0}b}aabb\lx@text@underline{aaa}} , as even when letter b substitutes a at position 5 of S , two occurrences of aaa (those underlined in S^{\prime} ) still exist. Here, we consider RPM under letter substitutions; considering other edit operations is an intriguing research direction. Motivation. Unlike frequent substrings, resilient ones account for the fact that changes to a string are often expensive to handle (e.g., we may need to perform FPM on the new string from scratch even if it is highly similar to the original one) or are unknown (e.g., when caused by adversaries [ CRB99 ] or they occur in the future). RPM is motivated by applications in: 1. Bioinformatics: In this application domain, there are large collections of very similar strings (also referred to as repetitive ) [ Nav21 ] . For example, conserved regions in DNA are stretches of nucleotides that remain relatively unchanged across different individuals, species, or time periods, indicating that these regions likely play essential biological roles [ KSS05 ] . However, even in conserved regions, there may be slight variations due to mutations, sequencing errors, or other factors [ KSS05 , SFR+99 ] . Similarly, a pangenome is a collection of DNA sequences each corresponding to the same part of DNA of a different individual [ Con18 ] . To find conserved regions in a DNA sequence collection, or motifs of interest in a pangenome, a straightforward approach is to solve FPM in each sequence of the collection and then output only the substrings that are frequent in all sequences. This, however, takes time proportional to the size of the collection, which can be in the order of TBs [ BGT+21 , TST+18 ] . An alternative approach is to exploit the fact that a bound on the number of changes (letter substitutions) of the strings in the collection is known or can be estimated [ Nav21 , PHD00 ] and apply RPM into any of these strings. This approach is much faster and approximates the set of patterns that are frequent in all strings remarkably well, as shown in Example 2 . Example 2 . Consider the collection \mathcal{C} of 143,588 SARS-CoV-2 DNA sequences from [ fBI24 ] with total length 4.176\cdot 10^{9} . Fig. 1(a) shows that mining (\tau,k) -resilient substrings from an arbitrarily selected sequence in \mathcal{C} is more than four orders of magnitude times faster on average than mining the \tau -frequent substrings that appear in all sequences in \mathcal{C} . Fig. 1(b) shows the Jaccard Similarity [ BCD16 ] J_{R} between the set of \tau -frequent substrings in all sequences in \mathcal{C} and the set of (\tau,k) -resilient substrings. J_{R} is 0.96 on average, implying that the set of (\tau,k) -resilient substrings approximates the set of \tau -frequent ones very well (i.e., the former substrings are frequent in almost all sequences in \mathcal{C} ). Fig. 1(b) also shows the Jaccard Similarity J_{F} between the set of \tau -frequent substrings in all sequences and the set of \tau -frequent substrings in an arbitrarily selected sequence from \mathcal{C} . J_{F} is 0.5 on average and no more than 0.68 , implying that the latter substrings are not frequent in most of the sequences in \mathcal{C} . (a) (b) Figure 1 : (a) Running time and (b) Jaccard similarity. 2. Text Analytics: Text data representing webpages [ Hen06 ] , tweets [ TAH+13 ] , or code in software repositories [ KG05 ] often undergo changes due to updates, leading to slightly different versions of the same text [ GKK+18 ] . Such updates may increase or decrease the substring frequencies. Applying RPM to a given version of the data ensures that the output substrings remain frequent even after k letter substitutions may occur in later versions. This is useful when outsourcing frequent substrings [ LZL+15 ] or using them in downstream analyses [ HKP11 ] , as (\tau,k) -resilient substrings remain truthful for longer in these datasets. 3. Recommender Systems: String letters are often substituted by adversaries to force a recommender that is trained on the string to favor their items [ THL+24 ] . Frequent substrings mined from such modified strings may be spurious and others that are indeed frequent may be missed, as letter substitutions can increase or decrease substring frequencies

Read the complete text