General Algorithms for Mining Closed Flexible
Patterns under Various Equivalence Relations
Tomohiro I, Yuki Enokuma, Hideo Bannai, and Masayuki Takeda
Department of Informatics, Kyushu University, Fukuoka 819-0395, Japan{tomohiro.i, bannai, takeda}@inf.kyushu-u.ac.jp
yuki.enokuma@i.kyushu-u.ac.jp

Abstract. We address the closed pattern discovery problem in sequential databases for the class of flexible patterns. We propose two techniques of coarsening existing equivalence relations on the set of patterns
to obtain new equivalence relations. Our new algorithm GenCloFlex isa generalization of MaxFlex proposed by Arimura and Uno (2007) thatwas designed for a particular equivalence relation. GenCloFlex can copewith existing, as well as new equivalence relations, and we investigate
the computational complexities of the algorithm for respective equivalence relations. Then, we present an improved algorithm GenCloFlex+
based on new pruning techniques, which improve the delay time per output for some of the equivalence relations. By computational experimentson synthetic data, we show that most of the redundancies in the minedpatterns are removed using the proposed equivalence relations.

1

Introduction

Discovering frequent patterns in sequence databases has great importance in awide-range of areas, including analysis of customer purchasing histories, Web
click streams, DNA/RNA sequences, natural language texts, and so on. Recent
decades have seen the series of studies; Agrawal and Srikant [1] was one of thepioneering works on sequential pattern mining, and many studies followed [3,11,
14].
In practical applications of pattern mining, a typical tradeoff to be considered
is: On one hand, we would like to consider for the mining task, a rich set ofpatterns and a relatively low minimum support threshold so that we may discoverinteresting, possibly subtle information buried in the data. On the other hand,by choosing such a search space, a mining algorithm may give us a tremendous
number of patterns as output, which will definitely be a bottle neck when the
results are examined by domain experts. To deal with this problem, an important
technique in reducing the number of patterns output without sacrificing theirdiversity, is to introduce an appropriate equivalence relation ≡ on the patternset Π, and to output only closed patterns, where a pattern P is closed if it ismaximal in the equivalence class [P ]≡ to which P belongs under ≡. This problem
is referred to as closed pattern discovery and has been studied extensively [2, 5–
8, 10, 12, 13, 15, 16, 19–21].

In this paper, we consider the closed pattern discovery problem for the classof flexible patterns. The main features of our work are: (1) We focus on the classof flexible patterns. (2) We employ occurrence-based equivalence relations. (3)We propose two techniques of coarsening existing equivalence relations. (4) We
develop a general algorithm GenCloFlex to handle several equivalence relations,and an improved algorithm GenCloFlex+. The algorithms have polynomial delay
time and space guarantees.
(1) Mining flexible patterns: A flexible pattern is of the form "w1 "· · · " wk " where w1 , . . . , wk (k ≥ 1) are constant strings and " is a gap symbolthat can match any string of any length. Most studies to date target the classof subsequence patterns [1, 3, 5–16, 20, 21]. A subsequence pattern is a special
case of flexible patterns, having the form "a1 " · · · " ak " (k ≥ 1) where eachai (1 ≤ i ≤ k) must be a single character. Thus, flexible patterns are more
descriptive and enable us to capture some features that may not be discoveredby subsequence patterns. For example, suppose we obtained "l " o " v " e" asan output of frequent subsequence pattern mining. Since the lengths of gaps
between each character is not considered, the pattern does not distinguish its
occurrences in texts “love” and “low velocity”, and we cannot know fromthe pattern alone, whether the phrase “love” is actually frequent or not. An
output of frequent flexible pattern mining may give us the phrase “"love"” or“"lo " ve"” in which case this information would be apparent. Thus mining
flexible patterns would be appreciated especially for languages which do nothave an explicit delimiter between words such as Japanese and Chinese. Also,
the information of consecutive characters in a pattern connected without gaps
is very important for bio-sequences [18]. To the best of our knowledge, miningof closed flexible patterns with this definition has only been considered in [2]. A
different version of closed flexible patterns is proposed in [19], but the definitions
are significantly different and incompatible with ours.
(2) Occurrence-based equivalence relations: The definition of closed
patterns depends on which equivalence relation to use, that is, which patterns weregard as the same. An equivalence relation is finer if less patterns are considered
to be the same: i.e. more attention is paid to differences. An equivalence relationis coarser if more patterns are considered to be the same: i.e. less attention ispaid to differences.
Most of the existing research on closed pattern mining traditionally use theequivalence relation on Π which is based on the document occurrence. Namely,
two patterns are equivalent if the sets of strings in sequential database S containing occurrences of the patterns are identical. If a string T in database S contains
an occurrence of P , we regard it as just one occurrence even if it contains two
or more occurrences of P . For example, consider the occurrences of patterns
P1 = "a " b " cd" and P2 = "a " cd" in string T = ......a...b..cd...a...cd...., where“.” denotes any symbol other than a, b, c. We note that P1 is a super-pattern of
P2 and therefore every occurrence of P1 implies an occurrence of P2 , independently of strings in sequential database S. Suppose that every other string in
S containing P2 has an occurrence of P1 . Then the document-occurrence-based2equivalence relation regards P1 and P2 equivalent. In this case, however, notethat the rightmost occurrence of P2 is not accompanied by an occurrence of
P1 . In other words, if we consider the minimal occurrence intervals of the respective patterns, P1 occurs twice while P2 occurs only once within T . In some
applications, we would like to distinguish between patterns which have different
occurrences in such a way. In this paper we pay attention to respective occurrences of patterns, and use occurrence-based equivalence relations.
B

Arimura and Uno [2] defined their equivalence relation ≡S on pattern set Π
based on the equality on the sets of beginning positions of pattern occurrences.
For example, consider the occurrences of P = "a " b" in T1 = ...a.b...a...b..a....
The occurrence positions of P are the two occurrence positions of “a”, excluding
the rightmost one. However, we have four occurrence positions of P in T2 =...a...a...a...a...b... while we have only one occurrence position of P in T3 =...a...b...b...b...b.... Such a non-symmetric feature is usually not desirable.
M

Mannila et al. [9] defined their equivalence relation ≡S on the subsequence
pattern set based on the minimal intervals within which patterns occur. In theprevious example, the pattern P has only one occurrence in respective strings.
M
In this paper we consider the closed pattern discovery problem mainly under ≡S
MX
MXG
extended to the flexible pattern set and its coarsened variants ≡S and ≡ S .
It should be emphasized that occurrence-based equivalence relations such as
B
M≡S and ≡S are finer than the document-occurrence-based equivalence relation.
This means that using such equivalence relations may increase the number ofmined closed patterns. Thus it is important to coarsen the equivalence relations.
On the other hand, the goodness of an equivalence relation may vary depending on the nature of the data, the application domain and the goal of patternmining. For this reason, it is desirable to develop a general, efficient closed pattern mining algorithm for various equivalence relations.
(3) Definition of support: Note that the choice of equivalence relation
does not imply a particular definition for the frequency, or support, of a pattern.
There are several definitions of support of a pattern P in a sequential database S.
One definition is the so-called document frequency, which is the number of strings
in S that contain at least one occurrence of P . A lot of work on closed patternmining employ this definition. Another definition is the sum of the numbers ofminimal intervals in respective strings in S that contain at least one occurrenceof P . This definition has been used, for example, in [9] and [22]. Yet anotherdefinition can be found in [9], which is the number of windows of a given width
in respective strings in S that contain at least one occurrence of P .
Throughout this paper we assume the document frequency. However, ouralgorithms can be easily modified to cope with the other definitions above whenMMXMXG
the underlying equivalence relation is in the M family (≡S , ≡S and ≡ S ).
(4) Polynomial delay time and space: Even in closed frequent patternmining, the size of the output can be exponentially large, and we cannot hopefor an algorithm running in polynomial time with respect to the input size. On
the other hand, an enumeration algorithm with polynomial delay time, is an3algorithm in which the time between each consecutive output is bounded by apolynomial with respect to the size of the input. Such characteristics can bevery useful and important for mining algorithms, since it guarantees that thealgorithm runs in polynomial time with respect to the size of the output. Thismeans that the time complexity of the algorithm is small when the output size,i.e., the number of closed frequent patterns is small. Even when the output sizeis large, we can still expect that the next output can be received in a reasonableamount of time. Without this guarantee, we may find out – after waiting for avery long time – that there are no more frequent patterns to be discovered.
Space complexity of the mining algorithm is also clearly an important issue.
Arimura and Uno [2] addressed the closed pattern discovery problem for the classof flexible patterns and presented the first algorithm MaxFlex with polynomial
time delay and polynomial space. Our algorithms also achieve polynomial timedelay and polynomial space.
For closed pattern mining under document-based equivalence relations, algorithms such as BIDE [16,17], proposed for subsequence patterns, seem to achievepolynomial space complexity. However, as far as we know, no time delay guarantees have been shown, which may be a consequence of the document-based
equivalence relation.
Contributions of this paper: We reiterate the main contributions of thispaper: For the frequent closed flexible pattern enumeration problem, we focus
Mon the equivalence relation ≡S of [9], and extended it to the class of flexible
patterns. We also propose two new equivalence relations by coarsening it. We
show GenCloFlex, an algorithm which generalizes the algorithm MaxFlex [2], sothat it can cope with existing, as well as new equivalence relations, and investigate its computational complexities for respective equivalence relations. Then we
present an improved algorithm GenCloFlex+, based on new pruning techniques
which improve the delay time per output for some of the equivalence relations.
By computational experiments on synthetic data, we prove that the proposed
equivalence relations drastically remove redundancies in the mined patterns.

2Preliminaries

Let Σ be a non-empty, finite set of symbols. A string over Σ is a finite sequenceof symbols from Σ. Let Σ ∗ denote the set of strings over Σ. Strings x, y andz are said to be a prefix, substring and suffix of string w = xyz. The length ofa string w is the number of symbols in w and denoted by |w|. The string oflength 0 is called the empty string and denoted by ε. Let Σ + = Σ ∗ − {ε}. The
i-th symbol of a string w is denoted by w[i] for 1 ≤ i ≤ |w|. The substring of astring w that begins at position i and ends at position j is denoted by w[i..j] for1 ≤ i ≤ j ≤ |w|. That is, w[i..j] = w[i] · · · w[j]. For convenience, let w[i..j] = ε
for j < i. The reversal wrev of a string w = w[1..n] is defined to be w[n] · · · w[1].
For a finite set S of strings, let %S% denote the total length of strings in S and
let S rev = {wrev | w ∈ S}.
4

An interval is an ordered pair [i, j] of integers with i ≤ j which represents
the set of integers k with i ≤ k ≤ j. Let I be a set of intervals. Let Beg(I) = {i |[i, j] ∈ I} and End(I) = {j | [i, j] ∈ I}, and let Min(I) denote the set of intervals
in I which are minimal! w.r.t. ⊆. For" any set I#of intervals and for any integers
h, k, let I ⊕ )h, k* = [i + h, j + k]! " [i, j]" ∈ I . #Also, for any set J of integers
and for any integer k, let J ⊕ k = j + k " j ∈ J .
2.1

Equivalence relation

Let A be a set. A binary relation on A is a subset of A × A. For binary relations
R1 , R2 on A, let R1 R2 = {)a, c* | )a, b* ∈ R1 ∧ )b, c* ∈ R2 }. Let IA = {)a, a* |a ∈ A}. For a binary relation R on A, let$R0 = IA and Rn =$RRn−1 (n > 0),∞∞and let R−1 = {)b, a* | )a, b* ∈ R}, R+ = n=1 Rn and R∗ = n=0 Rn .
A binary relation R on A is said to be reflexive if IA ⊆ R; symmetric if
R−1 ⊆ R; and transitive if R+ ⊆ R. An equivalence relation on A is a binary
relation on A which is reflexive, symmetric and transitive. For a binary relation
R, we often write aRb when )a, b* ∈ R.
Let ≡ be an equivalence relation on A. The equivalence class of an element
x of A under ≡ is {y ∈ A | x ≡ y} and denoted by [x]≡ . An equivalence relation≡ on A is said to be finer than another equivalence relation ≡% on A if%≡⊆≡% .
For any set R = {≡i | i ∈ Λ} of equivalence relations on A, let ∧R = i∈Λ ≡i&$'+and ∨R =. The equivalence closure of a binary relation R on A,i∈Λ ≡idenoted by EC(R), is the smallest superset of R that is an equivalence relation
on A. For any binary relation R on A, it is known that EC(R) = (R ∪ R−1 )∗ .
2.2

Pattern and embedding

Let " be a special symbol not in Σ, called the gap. A pattern is of the form
"w1 ". . ."wk " where k ≥ 1 and w1 , . . . , wk ∈ Σ + . Let Π be the set of patterns, andlet Π0 be the set of strings over Σ ∪{"} where the "’s do not occur consecutively.
We note that Π ⊂ Π0 . The size of a pattern P , denoted by size(P ), is the numberof symbols in P other than ". The reversal of a pattern P , denoted by P rev , isdefined in the same way as in the string case. The degree of a pattern P is thenumber of occurrences of " in P and denoted by deg(P ).
For example, let Σ = {a, b, c}. P = "ab " a " cb" is a flexible pattern.
size(P ) = 5, deg(P ) = 4 and P rev = "bc " a " ba".
A substitution of degree d is a d-tuple )π1 , . . . , πd * such that π1 , . . . , πd ∈
Π0 . A substitution )π1 , . . . , πd * is said to be ground if π1 , . . . , πd ∈ Σ ∗ . For
any pattern P ∈ Π and a substitution θ = )π1 , . . . , πd * with d = deg(P ), theapplication of θ to P , denoted by P θ, is the pattern obtained by replacing thei-th occurrence of " in P with πi for every i = 1, . . . , d. For any i = 1, . . . , d,let Θdi be the set of substitutions θ = )π1 , . . . , πd * such that (1) πi 0= " and (2)$dπj = " for every j with 1 ≤ j ≤ d and j 0= i. Let Θd = i=1 Θdi . A substitution)", . . . , ", π, ", . . . , "* ∈ Θdi is said to be primitive if π ∈ {ε} ∪ {"a" | a ∈ Σ}.
A primitive substitution )", . . . , ", π, ", . . . , "* is said to be erasing if π = ε, and5

non-erasing if π = "a" for some a ∈ Σ. For any P, Q ∈ Π, Q is said to be aright-extension of P if there exists a substitution θ ∈ Θdd such that Q = P θ,
where d = deg(P ).
An embedding of P ∈ Π0 into Q ∈ Π0 is a substitution θ such that P θ = Q.
defDefinition 1. P ! Q ⇐⇒ there is an embedding of P into Q that is primitive.

Let !∗ be a partial-order on Π0 s.t. P !∗ Q ⇐⇒ there is an embedding of P
into Q. For any P ∈ Π and T ∈ Σ + , P is said to occur in T if P !+ T .
For example, "ab " a " c " ! " ab " d " a " c" due to a non-erasing primitive)", "d", ", "* ∈ Θ4 , "ab"a"c"!"ab"ac" due to an erasing primitive )", ", ε, "* ∈
Θ4 , and "ab " a " c " !∗ " ab " d " ac" due to a substitution )", "d", ε, "*.
For an equivalence relation ≡ on Π, a pattern P ∈ Π is said to be closed
under ≡ if it is maximal in [P ]≡ w.r.t. !∗ .
2.3

Existing equivalence relations on Π

Let S be a finite subset of Σ + . Intuitively, equivalence relations on Π are designed so that P and Q are equivalent if: Every time P occurs in S, Q also occurs
at the same location. Difference between equivalence relations comes from thedifference in definitions of same location here. Below, we describe several existing
equivalence relations on Π.
An occurrence interval of a pattern P ∈ Π in T ∈ Σ + is an interval [|w1 | +1, |T | − |wd |] such that there is a ground embedding θ = )w1 , . . . , wd * of P into
T . Let Int T (P ) be the set of all occurrence intervals of P in T . We give thedefinitions of four existing equivalence relations. Let S be a finite subset of Σ + .
I

M

B

E

Definition 2 (≡S , ≡S , ≡S , ≡S ). For any patterns P, Q ∈ Π, let
I

def

M

def

B

def

E

def

P ≡S Q ⇐⇒ ∀T ∈ S, Int T (P ) = Int T (Q),P ≡S Q ⇐⇒ ∀T ∈ S, Min(Int T (P )) = Min(Int T (Q)),
P ≡S Q ⇐⇒ ∀T ∈ S, Beg(Int T (P )) = Beg(Int T (Q)),

P ≡S Q ⇐⇒ ∀T ∈ S, End(Int T (P )) = End(Int T (Q)).
The algorithm MaxFlex [2] enumerates all closed flexible patterns in polynoB
B
E
B
E
mial space and linear-time delay under ≡S . ≡S , ≡S and ≡S ∨ ≡S are naturalextensions of the well-known equivalence relations introduced by Blumer et al. [4]for the class of substring patterns, which are recognized as the basis of index
BE
structures for text data, e.g., the suffix trees (≡S ), the DAWGs (≡S ), and theBEM
compact DAWGs (≡S ∨ ≡S ). ≡S is an extension of the equivalence relation
introduced by Mannila et al. [9] for the class of subsequence patterns.
Equivalence relation function: We note that the equivalence relations
above vary depending on S. An equivalence relation (ER) function is a functionthat maps finite subsets S of Σ + to equivalence relations ≡S on Π. The reversalof an ER function Φ is defined by: )P, Q* ∈ Φrev (S) ⇐⇒ )P rev , Qrev * ∈ Φ(S rev ).
6

We say that an ER function Φ is symmetric if Φrev (S) = Φ(S) for every S. The
I
M
B
E
B
E
ER functions for ≡S , ≡S , ≡S ∨ ≡S and ≡S ∧ ≡S are symmetric, while the reversalBEof the ER function for ≡S is the ER function for ≡S , and vice versa.
Monotonicity of equivalence relations on Π: An equivalence relation≡ on Π is said to be monotone if !+ ∩ ≡ = (!∩ ≡)+ . If ≡ is monotone, thenP1 !+ P2 and P1 ≡ P2 implies that ∀Q ∈ Π, (P1 !∗ Q !∗ P2 =⇒ P1 ≡ Q ≡ P2 ).
Monotonicity of equivalence relations is a very helpful property for closedness
check of a pattern, i.e., for any monotone equivalence relation ≡, a pattern P isclosed iff there is no primitive substitution θ such that P θ ≡ P . We will discuss
general and efficient algorithms based on monotonicity in Section 4. We remark
I
M
B
E
that ≡S , ≡S , ≡S and ≡S are monotone.

3

Coarsening Existing Equivalence Relations
M

Since we prefer symmetric equivalence relations, we focus on ≡S that is symmetric. It is, however, still too fine and we want a coarser one. In this section,
MX
MXG
M
we define two new equivalence relations ≡S and ≡ S by coarsening ≡S . WithI
B
one of the techniques, we also coarsen the other equivalence relations ≡S , ≡S
E
IX
BX
EX
and ≡S . and introduce ≡S , ≡S and ≡S .
For any pattern P = "w1 " · · · " wk " ∈ Π, let P = w1 " · · · " wk , and thusM
P = "P ". One technique of coarsening ≡S is to extend as long as possible theconstant strings at pattern ends to the outward without decreasing occurrences.
Here we remark that the next proposition does hold.
Proposition 1. For any P ∈ Π and any substitution θ ∈ (Θd1 ∪ Θdd ) with d =deg(P ), |Min(Int T (P ))| ≥ |Min(Int T (P θ))| for every T ∈ S.
def

Definition 3. P !MXS Q ⇐⇒ there exists a ∈ Σ such that
– Q = "P a" and Min(Int T (Q)) = Min(Int T (P )) ⊕ )0, 1* for every T ∈ S; or– Q = "aP " and Min(Int T (Q)) = Min(Int T (P )) ⊕ )−1, 0* for every T ∈ S.
MX

MX

M

Definition 4 (≡S ). Let ≡S = EC(≡S ∪!MXS ).
Proposition 2. For any P ∈ Π, there uniquely exists a pair of strings u, v ∈ Σ ∗MXMXsuch that Q = "uP v" is closed under ≡S and P ≡S Q.
Take an example S which consists of a single string T1 = acbmdcacbndcaca,
and a pattern P = "b " d". There are two minimal occurrences of P in T1 , andwe see they are preceded by “ac” and followed by “cac” without gap. Thus forany combinations of a suffix u of “ac” and a prefix v of “cac”, uP v ("cb " dcac"
MX
for example) is equivalent to P under ≡S .
M
Another technique of coarsening ≡S is to add pattern fragments including
gaps to the pattern ends without decreasing occurrences.
7

defDefinition 5. P !MXG
S Q ⇐⇒ Q ∈ {"a " P ", "P " a"} with some a ∈ Σ and|Min(Int T (P ))| = |Min(Int T (Q))| for every T ∈ S.
MXG

MXG

M

Definition 6 ( ≡ S ). Let ≡ S = EC(≡S ∪!MXG
S ).

Take an example S which consists of a single string T1 = acbmdcagcbnddcaca,
and a pattern P = "b " d". The number of minimal occurrences of P in T1 is 2.
MXG
There are several patterns that are equivalent to P under ≡ S , but not underM
MX≡S and ≡S , such as "P " c", "a " cP " ca " c " a" and "a " cP " d". Note thatMXG
Q = "P " d " c" is not equivalent to P under ≡ S because the number of minimal
occurrences of Q is 1.
MX
MXG
We can prove that ≡S and ≡ S are monotone from Proposition 1. Also, theMX
MXG
ER functions for ≡S and ≡ S are symmetric. It follows from Definitions 4 and6 that the next inclusion relation holds.
M

MX

MXG

Theorem 1. ≡S ⊆ ≡S ⊆ ≡ S .

MX

I

B

E

The technique used in defining ≡S extends ≡S , ≡S and ≡S as below.
defDefinition 7. P !IX
S Q ⇐⇒ there exists a ∈ Σ such that

– Q = "P a" and Int T (Q) = Int T (P ) ⊕ )0, 1* for every T ∈ S; or– Q = "aP " and Int T (Q) = Int T (P ) ⊕ )−1, 0* for every T ∈ S.
def

Definition 8. P !BX
S Q ⇐⇒ there exists a ∈ Σ such that Q = "aP " andBeg(Int T (Q)) = Beg(Int T (P )) ⊕ (−1) for every T ∈ S.
def

Definition 9. P !EXS Q ⇐⇒ there exists a ∈ Σ such that Q = "P a" andEnd(Int T (Q)) = End(Int T (P )) ⊕ 1 for every T ∈ S.
IX

BX

EX

IX

I

BX

B

BX
Definition 10 (≡S , ≡S , ≡S ). Let ≡S = EC(≡S ∪!IX
S ), ≡S = EC(≡S ∪!S ) andEX
E≡S = EC(≡S ∪!EX
S ).
IX

BX

EX

We note that ≡S , ≡S , ≡S are not monotone.

4

Algorithms for Enumerating Frequent Closed Patterns

Let Freq S (P ) denote the number of strings in S in which P occurs.
Problem 1 (FreqCloPatEnum w.r.t. ≡). Given a finite subset S of Σ + anda non-negative integer σ, enumerate all the patterns P closed under ≡ without
duplicates such that Freq S (P ) ≥ σ.
Theorem 2 (MaxFlex [2]). For a finite alphabet Σ, there exists an algorithm
Bthat solves FreqCloPatEnum w.r.t. ≡S in O(|Σ|%S%) time delay and O(%S%d)
space, where d is the maximum number of gaps in the output patterns.
In this section, we consider methods for efficiently solving the problem for the
M
MX
MXG
I
IX
E
EX
M family (≡S , ≡S , ≡ S ), the I family (≡S , ≡S ), and the E family (≡S , ≡S ). In
B
BX
the sequel, we exclude the descriptions for the B family (≡S , ≡S ), since they aresimply the reversal of the E family.
84.1

Outline of GenCloFlex

A pattern P ∈ Π is said to be i-th-gap-closed under ≡ if P 0≡ P θ for everyθ ∈ Θdi , where 1 ≤ i ≤ d and d = deg(P ). For convenience, we say that P isleftmost-gap-closed for i = 1 and rightmost-gap-closed for i = deg(P ). A patternP ∈ Π is said to be inner-gap-closed if it is i-th-gap-closed under ≡ for every iwith 1 < i < deg(P ).
An equivalence relation ≡ on Π is said to be rightmost-gap-independent if
any P ∈ Π satisfies the following condition: For every i with 1 ≤ i < deg(P ),if P is not i-th-gap-closed under ≡, then every right-extension P % of P is noti-th-gap-closed under ≡. We remark that the M, I and E families are rightmostgap-independent.
As a generalization of MaxFlex [2], we describe GenCloFlex, an algorithm forsolving FreqCloPatEnum w.r.t. any equivalence relation that is rightmostgap-independent. We define a rooted search-tree ST over Π ∪ {⊥} by:– For any a ∈ Σ, the parent of "a" is ⊥.
– For any a ∈ Σ and for any w1 , . . . , wk ∈ Σ + , the parent of "w1 " · · · " wk a"and "w1 " · · · " wk " a" is "w1 " · · · " wk ".
Lemma 1. For any P, Q ∈ Π, P !∗ Q implies Freq S (P ) ≥ Freq S (Q).
Lemma 2 (general pruning rule). Let ≡ be any rightmost-gap-independent
equivalence relation on Π. Under ≡, if P ∈ Π is not i-th-gap-closed for some iwith 1 ≤ i < deg(P ), then no descendant of P in ST is closed.
Algorithm 1 outlines a general algorithm for FreqCloPatEnum under any
rightmost-gap-independent equivalence relation. The algorithm performs a depthfirst-traversal of ST, with pruning based on Lemmas 1 and 2. We note that thealgorithm does not build ST actually.
4.2

Closedness tests

We now consider how to realize the inner-, the leftmost- and the rightmostclosedness tests. An equivalence relation ≡ on Π is said to be inner-gap-monotone
if for any P ∈ Π and any θ ∈ Θd − (Θd1 ∪ Θdd ) with d = deg(P ), P ≡ P θ implies
that ∀Q ∈ Π, (P !∗ Q !∗ P θ =⇒ P ≡ Q ≡ P θ). We remark that the M, I andE families are all inner-gap-monotone.
Lemma 3 (inner-gap-closedness test). Let ≡ be any inner-gap-monotone
equivalence relation on Π. Let P ∈ Π. Then, for any i with 1 < i < deg(P ), P
is i-th-gap-closed under ≡ if P 0≡ P θ for every primitive substitution θ in Θdi .
For a monotone equivalence relation ≡, the leftmost- (resp. rightmost-) gapclosedness of P ∈ Π can also be tested by checking whether P 0≡ P θ for every
IXEX
non-erasing primitive substitution θ in Θd1 (resp. Θdd ). For ≡S and ≡S that are
not monotone, we have the following lemma:9Algorithm 1: General Algorithm GenCloFlex for FreqCloPatEnum
Input: a finite subset S of Σ + and a non-negative integer σ.
Output: non-duplicate list of patterns P with Freq S (P ) ≥ σ that are closed
under a rightmost-gap-independent equivalence relation ≡.
1 foreach a ∈ Σ do Expand(#a#);procedure Expand(P );let d := deg(P );2 if Freq S (P ) < σ then return ;3 if (P is not leftmost-gap-closed) or (P is not inner-gap-closed) then4
return; // Pruning
1// Now P is leftmost-gap-closed and inner-gap-closed
if P is rightmost-gap-closed then // P is closed
6
report P ;5foreach a ∈ Σ do
Expand(#P # a#);9
Expand(#P a#);7
8

Table 1. Time complexities of the leftmost-, the Table 2. Delay time per outrightmost- and the inner-gap-closedness tests for re- put for respective equivalence relations.
spective equivalence relations.

I

≡S
IX

≡S
M

≡S
MX

≡S

MXG

≡S

E

≡S
EX

≡S

leftmost-gapclosedness(always true)

rightmost-gapclosedness(always true)

inner-gapclosedness
O($S$d)O($S$)

O($S$)

O($S$d)(always true)(always true)

O($S$d)O($S$)

O($S$)

O($S$d)O($S$)

O($S$)

O($S$d)O($S$)(always true)

O($S$)

O($S$)

O($S$)

O($S$)

GenCloFlex

GenCloFlex+≡S O(|Σ|$S$d)

O(|Σ|$S$d)

I

IX≡S O(|Σ|$S$2 d) O(|Σ|$S$d)
M≡S O(|Σ|$S$d)

O(|Σ|$S$d)

MX≡ S O(|Σ|$S$2 d) O(|Σ|$S$d)

MXG≡ S O(|Σ|$S$2 d) O(|Σ|$S$2 d)

E≡S O(|Σ|$S$) [2] O(|Σ|$S$)
EX≡S O(|Σ|$S$2 )O(|Σ|$S$)

IX

EX

MX

Lemma 4 (leftmost-, rightmost-gap-closedness tests for ≡S , ≡S , ≡S ).
IX
EXMXLet ≡∈ {≡S , ≡S , ≡S } and P ∈ Π. P is leftmost-gap-closed under ≡ if P 0≡ "aP "for every a ∈ Σ. P is rightmost-gap-closed under ≡ if P 0≡ "P a" for every a ∈ Σ.
Lemma 5. The time complexities of the leftmost-, the rightmost- and the innergap-closedness tests for P ∈ Π with d = deg(P ) are summarized in Table 1.
I

M

Proof. The leftmost- and the rightmost-gap-closedness tests for ≡S and ≡S andE
the rightmost-gap-closedness test for ≡S are unnecessary by their definitions.
E
The leftmost-gap-closedness test for ≡S takes O(%S%) time as shown in [2]. By
Lemma 4 the leftmost-gap-closedness test (resp. the rightmost-gap-closednessMXtest) for ≡S can be performed simply by checking whether all minimal occurrences of P are directly preceded by (resp. followed by) a same symbol. This10

EX

takes O(%S%) time. Similarly, the rightmost-gap-closedness test for ≡S and theIXleftmost- and the rightmost-gap-closedness test for ≡S take O(%S%) time. Now
MXG
we consider the rightmost-gap-closedness test for ≡ S . What we have to do
is to check whether there exists a non-erasing primitive substitution θ in Θddwhich preserves |Min(Int T (P ))| in every T ∈ S. Let e1 , . . . , em be the increasing sequence of ending positions of Min(Int T (P )). Let Ii = [e1 + 1, ei+1 ] fori = 1, . . . , m − 1 and let Im = [em + 1, |T |]. We can build the list of symbols common to the substrings of T implied by I1 , . . . , Im in O(|T |) time. The test thus
takes O(%S%) time. The leftmost-gap-closedness test also takes O(%S%) time.
We now suppose d > 2 for the inner-gap-closedness test. For the E family, it
suffices to determine whether P θ occurs within the leftmost occurrence intervalof P . This can be done in O(%S%) time independently of d by using an auxiliary
data structure of size O(%S%d) as shown in [2]. For the M family, we have to checkit over all minimal occurrence intervals of P , and the same technique cannot beapplied. This takes O(%S%d) time and space. For the I family, we basically checkit over all occurrence intervals of P . For the erasing primitive substitution θ in
Θd2 (resp. Θdd−1 ), it suffices to check whether P θ begins (resp. ends) at every
beginning (resp. ending) positions of occurrence intervals of P . For the othererasing primitive substitutions or for the non-erasing primitive substitutions, itsuffices to consider only the minimal occurrence intervals.
67
4.3

Improved algorithms for respective equivalence relations

We introduce new efficient pruning techniques based on common extensions.
MX
IX
EX
Especially, the techniques improve the time complexity for ≡S , ≡S and ≡S , asshown in Table 2.
M
MX
MXG
I
IX
E
EX
Let ≡∈ {≡S , ≡S , ≡ S , ≡S , ≡S , ≡S , ≡S }. The longest common extension ofP ∈ Π under ≡ is the longest string v ∈ Σ ∗ such that for every T ∈ S,
M

MX

MXG

– Min(Int T ("P v")) = Min(Int T (P )) ⊕ )0, |v|* when ≡ ∈ {≡S , ≡S , ≡ S };
I
IX
E
EX
– Int T ("P v") = Int T (P ) ⊕ )0, |v|* when ≡ ∈ {≡S , ≡S , ≡S , ≡S }.
When v 0= ε, c = v[1] is said to be the common extension of P under ≡.
The following lemmas help us to skip unnecessary closedness tests.
Lemma 6 (skipping leftmost- and inner-gap-closedness tests). Let ≡∈
M
MX
MXG
I
IX
E
EX
{≡S , ≡S , ≡ S , ≡S , ≡S , ≡S , ≡S } and let c ∈ Σ be the common extension of P ∈ Πunder ≡. If P is leftmost- and inner-gap-closed under ≡, "P c" is also leftmostand inner-gap-closed under ≡.
MX

MXG

Lemma 7 (skipping rightmost-gap-closedness tests). Let ≡ ∈ {≡S , ≡ S
IX
EX, ≡S , ≡S } and let c ∈ Σ be the common extension of P ∈ Π under ≡. Then P
is not rightmost-gap-closed under ≡.
For the M family, we can utilize the following lemma for pruning.
11

M

MX

MXG

Lemma 8 (pruning for the M family). Let ≡∈ {≡S , ≡S , ≡ S } and let c ∈ Σ
be the common extension of P ∈ Π under ≡. Then among the descendants of P
in ST, only descendants of "P c" can be closed under ≡.

Proof. Since Min(Int T ("P c")) = Min(Int T (P )) ⊕ )0, 1* for every T ∈ S, "P"c" isnot closed due to "P "c" ≡ "P c". Since )"P " a", "P c " a"* ∈ !+ ∩ ≡, "P " a" isnot closed for any a ∈ Σ − {c}. Let P = "w1 " · · · " wk ", where w1 , . . . , wk ∈ Σ + .
Let P % = "w1 " · · · " wk−1 " b " wk a", where b is the first symbol of wk . Since)"P a", P % * ∈ !+ ∩ ≡, "P a" is not closed for any a ∈ Σ − {c}. Since ≡ ismonotone, the lemma holds.
6
7
For the I and E families, we can utilize the following lemmas for pruning.
I

IX

E

EX

Lemma 9 (pruning for the I and E families). Let ≡∈ {≡S , ≡S , ≡S , ≡S }and let c ∈ Σ be the common extension of P ∈ Π under ≡. Then among thedescendants of P in ST, only descendants of "P c" and of "P "c" can be closed
under ≡.

Proof. "P a" does not occur in S for any a ∈ Σ − {c}. Since )"P "a", "P c"a"* ∈!+ ∩ ≡, "P "a" is not inner-gap-closed for any a ∈ Σ − {c}. Since ≡ is innergap-monotone, the lemma holds.
6
7
I

IX

E

EX

Lemma 10. Let ≡∈ {≡S , ≡S , ≡S , ≡S } and let c ∈ Σ be the common extensionof P ∈ Π under ≡. |End(Int T (P ))| = |{i | min{End(Int T (P ))} < i ≤ |T |, T [i] =c}| for every T ∈ S ⇐⇒ "P "c" ≡ "P c".

Proof. Since c is the common extension of P under ≡, Int T ("P c") = Int T (P ) ⊕)0, 1* for every T ∈ S. Adding to this, the left-hand condition implies thatInt T ("P"c") = Int T ("P c") for every T ∈ S. Hence the =⇒ statement holds. The⇐= statement follows from the fact that |End(Int T ("P"c"))| > |End(Int T ("P c"))|for some T ∈ S if the left-hand condition does not hold.
6
7
M

MX

MXG

I

IX

E

EX

For any ≡∈ {≡S , ≡S , ≡ S , ≡S , ≡S , ≡S , ≡S } and P ∈ Π, the common extension c of P under ≡ is said to make a branch if "P " c" 0≡ "Pc". Clearly from
Lemma 8, any common extension does not make a branch for the M family. For
the I and E families, it follows from Lemma 10 that a common extension c makes
a branch iff |End(Int T (P ))| < |{i | min{End(Int T (P ))} < i ≤ |T |, T [i] = c}| forsome T ∈ S.
The algorithm based on Lemmas 6, 7, 8, 9 and 10 can be summarized as
Algorithm 2. We remark that the longest common extension v can be represented
in constant space, by the pair of a pointer to some position in T ∈ S where v
occurs and length |v|.
4.4

Time complexities

Theorem 3 (GenCloFlex,GenCloFlex+). For a finite alphabet Σ, Algorithms 1
and 2 solve FreqCloPatEnum for respective equivalence relations with timedelay shown in Table 2 and O(%S%d) space, where d is the maximum number ofgaps in the output patterns.
12

Algorithm 2: Improved Algorithm GenCloFlex+ for FreqCloPatEnum
Input: a finite subset S of Σ + and a non-negative integer σ.
Output: non-duplicate list of patterns P with Freq S (P ) ≥ σ that are closed
M

MX

MXG

I

IX

E

EX

under ≡ ∈ {≡S , ≡ S , ≡ S , ≡S , ≡S , ≡S , ≡S }.
1 foreach a ∈ Σ do CheckExtension(#a#);procedure ExpandWithCommonExtension(P , v);
if P is rightmost-gap-closed then // When |v| > 0, use Lemma 72report P ;1

if |v| > 0 thenlet c := v[1];5ExpandWithCommonExtension(#P c#, v[2..|v|]);
6
if c makes a branch then
7
CheckExtension(#P # c#);
3
4

else
foreach a ∈ Σ do
10
CheckExtension(#P # a#);11
CheckExtension(#P a#);8
9

procedure CheckExtension(P );if Freq S (P ) < σ then return ;2 if (P is not leftmost-gap-closed) or (P is not inner-gap-closed) then3
return; // Pruning
1// Now P is leftmost-gap-closed and inner-gap-closed
compute the longest common extension v of P under ≡;5 ExpandWithCommonExtension(P , v);
4

Proof. Let CT ≡ denote the cost of the closedness test under ≡, i.e., CT ≡ ∈O(%S%) if ≡ is the E family, CT ≡ ∈ O(%S%d) if ≡ is the M or I family.
M

I

E

For GenCloFlex: For ≡S , ≡S and ≡S , the rightmost-gap-closedness test is
unnecessary and therefore the condition of the if -statement at Line 5 is always
satisfied and pattern P is always reported. As a result, the delay time per output
MX
MXG
IX
EX
is obtained by O(|Σ| × CT ≡ ). On the other hand, for ≡S , ≡ S , ≡S and ≡S ,pattern P is reported only when the condition is satisfied. Nevertheless, we canfind a frequent closed pattern after going down ST at most %S% unreported
patterns, and hence, the delay for output is O(|Σ|%S% × CT ≡ ).
For GenCloFlex+: At Line 4 of Procedure CheckExtension(P ), we computethe longest common extension$ of P under ≡. It is equivalent to compute thelongestcommonprefixofT ∈S {T [j + 1..|T |] | j ∈ End(Min(Int T (P )))} (resp.
$
{T
[j
+
1..|T
|]
|
j
∈
End(Int
T (P ))}) for the M family (resp. for the I and E
T ∈S
families), and hence, is done in O(%S%) time.
In the case of the I or E family, we also compute the positions where thecommon extension makes a branch as follows.
For every T ∈ S in which P occurs, do the following:13

1. Compute F (a) = |{i | min{End(Int T (P ))} < i ≤ |T |, T [i] = a}| for any
symbol a used in v.
2. For each j = 1, . . . , |v| in increasing order, do the following:(a) If |End(Int T (P ))| < F (v[j]) then v[j] makes a branch.
(b) Decrement F (v[j]) by 1.
Thus we can compute the branching positions in v in O(%S%) time.
MX
IX
EX
Here we estimate the delay time per output for ≡∈ {≡S , ≡S , ≡S }. Let us
consider the call CheckExtension(P ) such that P is not rightmost-gap-closed,
MX
IX
EXi.e., there exists c ∈ Σ with P ≡ "P c". From the definition of ≡S , ≡S and ≡S ,"P v" is closed, where v is the longest common extension of P under ≡. Since v
can be computed in O(%S%) time and the closedness test for P takes O(CT ≡ )time, we can output "P v" in O(CT ≡ ) time just after CheckExtension(P ) is
executed. Hence the delay from a previous output to "P v" is O(|Σ| × CT ≡ ). 67
MXG

The closedness checks for ≡ S take a constant factor more time than those forMX≡S and ≡S . However, it should be noted that the total theoretical asymptotic
MXG
M
worst case time complexities for ≡ S is equal to or smaller than those for ≡S
MX
MXG
MXG
and ≡S , due to the smaller search space for ≡ S in ST. Hence, ≡ S never falls
MMX
far behind ≡S and ≡S , and can be much faster.
M

5Computational Experiments

We implemented our algorithms for I, M and E families in the C language. Recall
B
E
E
that ≡S is just the reversal of ≡S , and thus, GenCloFlex ≡S can essentiallybe regarded as MaxFlex [2]. Considering the trade-off in implementation, weused naive matching to compute the longest common extensions, and did not
implement the pruning technique based on Lemma 10. All the computational
experiments were carried out on Apple Xserve with two Quad-Core Intel Xeon
at 2.93GHz (8 CPU x 2 HT), with 24GB Memory 1066MHz DDR3.
We carried out experiments on synthetic data. To create data sets for examining flexible pattern mining algorithms, we modified IBM sequence generator [1], which is widely used in the subsequence pattern mining researcharea [3, 5–8, 13, 20]. The original program generates random sequences of item
sets and embeds copies of some item set sequence as a pattern which is randomly corrupted. Although, originally, each item set is sorted and represented
as a sorted integer sequence, we use the unsorted sequence representation. Each
such sequence in the pattern is considered as a segment of the flexible pattern.
In this way, we are able to generate a data set of integer strings in which someflexible patterns are embedded, where each segment is damaged in the samemanner as the original program (See [1] for more details).
There are several parameters: [D] number of generated strings in 1000s, [C]average length of strings, [N] alphabet size in 1000s, [P] number of patterns, [L]average number of segments of patterns and [S] average length of segments of14

Table 3. Experiments on Synthetic Data Sets (threshold value is fixed to σ = 10)
algorithm/equiv
GenCloFlex

D5C40N1P500L4S2
patterns
seconds

I≡S 271,412
I

GenCloFlex+ ≡S 271,412

1155

D5C40N1P500L4S4
patterns
seconds
216,5131105 (96%) 216,513

1119

D5C40N1P500L4S6
patterns
seconds
201,746967 (86%) 201,746

972
800 (82%)

IX

GenCloFlex+ ≡S 255,910 (94%) 1104 (96%) 182,868 (84%) 970 (87%) 159,898 (79%) 777 (80%)
GenCloFlex

M≡S 294,183
M

GenCloFlex+ ≡S 294,183

1225

285,9541161 (95%) 285,954

1434

305,8931116 (78%) 305,893

1360

948 (70%)

MX

GenCloFlex+ ≡ S 253,928 (86%) 1075 (88%) 180,576 (63%) 928 (65%) 162,658 (53%) 781 (57%)
MXG

GenCloFlex+ ≡ S 247,036 (84%) 1060 (87%) 165,175 (58%) 874 (61%) 143,930 (47%) 731 (54%)
GenCloFlex

E≡S 311,526
E

GenCloFlex+ ≡S 311,526

1380

328,368

1266 (92%) 328,368

1717

341,138

1368 (80%) 341,138

1545

1100 (71%)

EX

GenCloFlex+ ≡S 270,511 (87%) 1180 (86%) 209,971 (64%) 1146 (67%) 184,289 (54%) 904 (59%)

patterns. We omitted scalability tests since we clearly showed time complexitiesof our algorithms. Instead we are interested in how the parameter [S] affects
efficiency of our algorithms, and therefore experimented on three data sets withparameters D5C40N1P500L4S2, D5C40N1P500L4S4 and D5C40N1P500L4S6.
In Table 3, we compare the number of output closed patterns and computational time, where xx% is the relative ratio compared to GenCloFlex of respective
families. The result shows that redundant output patterns which can be removed
by our coarsened equivalence relations increase as the average length of frequent
segments embedded in a data set becomes longer. Thus our algorithms withcoarsened equivalence relations would be effective especially for data which is
expected to contain long frequent segments such as bio-sequences.

6

Conclusion

We addressed the closed pattern discovery problem for the class of flexible patterns. We focused on the minimal-occurrence-interval based equivalence relation
M≡S on the set of patterns introduced by Mannila et al. [9], and proposed two
new equivalence relations by coarsening it. We investigated the properties of
equivalence relations on the patterns from viewpoints of closed pattern enumeration, and as a generalization of the algorithm proposed by Arimura andUno [2], we showed a general algorithm for enumerating closed patterns forexisting and newly proposed equivalence relations of various kinds. Then we
accelerated the algorithm by a set of new pruning techniques. Computational
experiments on synthetic data implied that the proposed equivalence relations
successfully remove some redundancy in the output patterns compared to theexisting equivalence relations. Finally, although the results are not shown due
to space limitation, we applied our algorithm on real data: Waka poems – traditional Japanese poetry with over 1300-year history – and confirmed that ouralgorithms with coarsened equivalence relations output reasonable amounts ofmined patterns and increase their readability.
15

References
1. Agrawal, R., Srikant, R.: Mining sequential patterns. In: ICDE. pp. 3–14 (1995)
2. Arimura, H., Uno, T.: Mining maximal flexible patterns in a sequence. In: JSAI’07.
pp. 307–317 (2008)
3. Ayres, J., Flannick, J., Gehrke, J., Yiu, T.: Sequential pattern mining using abitmap representation. In: KDD. pp. 429–435 (2002)
4. Blumer, A., Blumer, J., Haussler, D., McConnell, R., Ehrenfeucht, A.: Complete
inverted files for efficient text retrieval and analysis. J. ACM 34(3), 578–595 (1987)
5. Ding, B., Lo, D., Han, J., Khoo, S.C.: Efficient mining of closed repetitive gapped
subsequences from a sequence database. In: ICDE. pp. 1024–1035 (2009)
6. Lo, D., Cheng, H., Lucia: Mining closed discriminative dyadic sequential patterns.
In: EDBT. pp. 21–32 (2011)
7. Lo, D., Ding, B., Lucia, Han, J.: Bidirectional mining of non-redundant recurrent
rules from a sequence database. In: ICDE. pp. 1043–1054 (2011)
8. Lo, D., Khoo, S.C., Li, J.: Mining and ranking generators of sequential patterns.
In: SDM. pp. 553–564 (2008)
9. Mannila, H., Toivonen, H., Verkamo, I.A.: Discovery of frequent episodes in event
sequences. Data Mining and Knowledge Discovery 1(3), 259–289 (1997)
10. Parida, L., Rigoutsos, I., Floratos, A., Platt, D.E., Gao, Y.: Pattern discovery on
character sets and real-valued data: linear bound on irredundant motifs and an
efficient polynomial time algorithm. In: Proc. SODA. pp. 297–308 (2000)
11. Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., Hsu, M.: Prefixspan: Mining sequential patterns by prefix-projected growth. In: ICDE. pp. 215–224(2001)
12. Pisanti, N., Crochemore, M., Grossi, R., Sagot, M.F.: A basis of tiling motifs
for generating repeated patterns and its complexity for higher quorum. In: Proc.
MFCS. pp. 622–631 (2003)
13. Raı̈ssi, C., Calders, T., Poncelet, P.: Mining conjunctive sequential patterns. In:
ECML/PKDD (1). p. 19 (2008)
14. Srikant, R., Agrawal, R.: Mining sequential patterns: Generalizations and performance improvements. In: EDBT. pp. 3–17 (1996)
15. Tatti, N., Cule, B.: Mining closed strict episodes. In: ICDM. pp. 501–510 (2010)
16. Wang, J., Han, J.: BIDE: Efficient mining of frequent closed sequences. In: ICDE.
pp. 79–90 (2004)
17. Wang, J., Han, J., Li, C.: Frequent closed sequence mining without candidate
maintenance. IEEE Transactions on Knowledge and Data Engineering 19(8), 1042–
1056 (2007)
18. Wang, K., Xu, Y., Yu, J.X.: Scalable sequential pattern mining for biological sequences. In: CIKM. pp. 178–187 (2004)
19. Wu, H.W., Lee, A.J.: Mining closed flexible patterns in time-series databases. Expert Systems with Applications 37(3), 2098 – 2107 (2010)
20. Yan, X., Han, J., Afshar, R.: CloSpan: Mining closed sequential patterns in large
databases. In: SDM (2003)
21. Zaki, M.J.: Spade: An efficient algorithm for mining frequent sequences. Machine
Learning 42(1/2), 31–60 (2001)
22. Zhou, W., Liu, H., Cheng, H.: Mining closed episodes from event sequences efficiently. In: PAKDD. pp. 301–318 (2010)16