TCS -TR-A-10-41

TCS Technical Report

Mining Approximate Patterns with Frequent Locally
Optimal OccurrencesbyAtsuyoshi Nakamura
Hisashi Tosaka
Mineichi Kudo

Division of Computer Science
Report Series A
March 1, 2010

Hokkaido University

Graduate School ofInformation Science and Technology
Email:

atsu@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-6806+81-011-706-7832

Mining Approximate Patterns with Frequent
Locally Optimal Occurrences

March 1, 2010
Abstract
We propose a novel frequent approximate pattern mining that suits estimation of occurrence regions. Given a string s, our mining enumerates its
substrings that locally optimally match many substrings of s. We show analgorithm for this problem in which candidate patterns are generated without
duplication using the suﬃx tree of s. This problem can be extended to the problem of enumerating approximate frequent subforests of a given ordered labeledtree T . Our mining was applied to the task of extraction of search result records
from a web page returned by a search engine, and had good performance forbenchmark data sets.

1

Introduction

Now, frequent mining is one of the most popular study areas in data mining. In
the area of frequent mining, strings and trees are popular objects that people areinterested in, and various problems on them have been studied so far in order to ﬁnd
useful patterns. Frequent contiguous exact patterns like substrings and bottom-up
subtrees can be enumerated easily, but such restriction on patterns is too strict toﬁnd useful patterns in real data.
Two approaches are there to overcome this problem. One approach is to remove
contiguous restriction, namely, to consider ﬂexible matching. In this approach, subsequences for strings [1], induced [2] and embedded [12] subtrees for trees were studied
in the context of frequent mining. The other approach is to remove exact restriction,
namely, to consider approximate patterns. As for frequent substring mining in thisapproach, a frequent mining that counts the number of similar substrings with respect
to Hamming distance was studied [15].
In this paper, we study frequent mining of the latter approach for strings andlabeled ordered trees. The problem considered here is to ﬁnd patterns frequently
appearing in one string or tree instead of a set of strings or trees. Applications ofsuch mining include impressive melody part extraction by ﬁnding frequent contiguous
1

2

Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

subsequences (substrings) in a melody sequence and data record extraction by ﬁnding
frequent subforests in a tag tree of a web page. In such applications, the region ofeach occurrence must be estimated because the purpose is not to ﬁnd patterns but toextract occurrences correctly.
In frequent approximate mining from one given string or tree, previous Hamming
distance approach is not suﬃcient because one insertion or deletion changes Hamming
distance drastically while it changes edit distance a little. However, edit distance approach makes a counting problem arise: essentially the same part may be counted
many times because a small change in range boundaries does not produce a big difference in edit distance. This is not a problem when frequency is counted by how
many strings contain occurrences of a pattern in a given set of strings. But, this is a
big problem when every occurrence in a string is counted. Furthermore, we are considering a problem of extracting occurrences correctly, which means that occurrence
boundaries must be estimated appropriately.
To overcome this problem, for each pattern, we count its locally optimal occurrences
in a given string, where a substring s[h..j] of s[1..n] is said to be a locally optimaloccurrence of pattern p[1..m] if the pair of s[h..j] and p[1..m] is locally optimal [6] assubstrings of s[1..n] and p[1..m]. Here, s[h..j] denotes the substring of s from positionh to position j. A locally optimal occurrence of pattern p has optimized boundaries
in the meaning that the boundaries are best ﬁtted to p in terms of alignment scorewhen one of the boundaries is ﬁxed. By counting locally optimal occurrences alone,
only the optimal one among occurrences with slightly diﬀerent boundaries is counted
and such an optimal occurrence is considered to be appropriate as an estimated occurrence region of a pattern. By restricting patterns to substrings in a given sting,and by generating all substring without duplication using the suﬃx tree of the string,approximate patterns with frequent locally optimal occurrences can be enumerated inO(n3 ) time and O(n3 ) space for a given string with length n. All locally optimal pairs
are known to be calculated by both forward and backward executions of a local alignment algorithm [9], and our algorithm is a harmonic combination of the algorithm
and pattern generation using a suﬃx tree.
Since a labeled ordered tree can be regarded as a layered strings by seeing thesequence of child subtrees for each internal node as a string, the problem and thealgorithm for a string can be extended to those for a labeled ordered tree, where child
subtrees for an internal node d are subtrees rooted by child nodes of d. As local
optimality, we add one more condition, upward-downward optimality, which requests
that an occurrence subforest has the best score among all the subforests containedin it or containing it. We show O(n4)-time O(n3 )-space algorithm for enumerating
subforest patterns in a given tree with n nodes. Compared to the algorithm for astring, its time complexity is O(n) factor larger, which is the time needed to checkupward-downward optimality. O(n4)-time seems too slow for practical use, but it took
about O(m1.73 ) only according to our experiments on search result record extraction,
where m is the total length of distinct child subtree sequences for all internal nodes,

Mining Approximate Patterns with Frequent Locally Optimal Occurrences3

which is at most n.
As an application of our algorithm for a labeled ordered tree, we propose a method
for search result record (SRR) extraction based on mining approximate subforest patterns with frequent locally optimal occurrences. One merit of using frequent mining
for this problem is to be able to extract SRRs even if any pair of SRRs does not appear
contiguously, which is impossible for popular methods [8, 10, 14] that detect contiguous occurrences to ﬁnd SRRs. This merit could be demonstrated in our experiments
using ViNTs data sets. According to our experimental comparison with ViNTs [14],which is a state-of-the-art system for SRR extraction, our method performed between
the two versions of ViNTs, a version using visual features and a version using nosuch feature, with respect to F-measure, namely, the harmonic average of precisionand recall. Considering performance improvement potential of our method by using
visual features, this result demonstrates eﬀectiveness of our method as a base methodof SRR extraction.

2

Mining Approximate Strings

2.1

Problem SettingLet Σ be a ﬁnite alphabet, whose elements are called letters. A string s is a sequenceof letters with ﬁnite length. The length of string s is the number of letters in s
which is denoted by |s|. We let s[i] denote the ith letter of s, so s is also expressedby s[1]s[2] · · · s[n] when |s| = n. We also use notation s[i..j] for j ≥ i − 1 whichis equal to s[i]s[i + 1] · · · s[j], namely, a substring of s that begins at the ith letterand ends at the jth letter. Note that s[i..i − 1] denotes a null (empty) string, which
is a substring of any string. Let ‘-’ denote the gap symbol which is assumed not tobelong to Σ. A pair (s1 , s2 ) of strings is said to be a (global) alignment of strings s1
and s2 if the following three conditions are satisﬁed: (1) s1 and s2 are made froms1 and s2 , respectively, by inserting gap symbols, (2) |s1 | = |s2 |, and (3) s1 [i] =s2 [i] =‘-’ for no i ∈ {1, 2, ..., |s1|}.A score function w(x, y) is a real-valued functionon (Σ ∪ {-}) × (Σ ∪ {-}) that have the following properties: w(x, y) = w(y, x) for all
x, y ∈ Σ ∪ {-} and w(x, -) < 0 < w(x, x) for all x ∈ Σ. For an alignment (s1 , s2 ) ofstrings s1 and s2 , its score SAL (s1 , s2 ) is deﬁned as

SAL (s1 , s2 ) =

|s1 |


w(s1[i], s2 [i])i=1

Let AL(s1 , s2 ) denote the set of all alignments of strings s1 and s2 . An alignment∗ ∗(s1 , s2 ) ∈ AL(s1 , s2 ) is said to be optimal if
SAL (s∗1 , s∗2 ) =We let SOPT (s1 , s2 ) denote

max

max

(s1 ,s2 )∈AL(s1 ,s2 )(s1 ,s2 )∈AL(s1 ,s2 )SAL (s1 , s2 ).

SAL (s1 , s2 ).

4Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

We deﬁne an approximate occurrence of a pattern p with locally optimal boundaries
in terms of alignment score.
Definition 1 A substring s[h..j] of s[1..n] is said to be a locally optimal occurrenceof string p[1..m] if the following conditions are satisﬁed:
CS1 SOPT (p[1..m], s[h..j]) > 0,
CS2 SOPT (p[1..m], s[h..j]) ≥ SOPT (p[g..m], s[h ..j]) for all 1 ≤ g ≤ m + 1, 1 ≤ h ≤j + 1, andCS3 SOPT (p[1..m], s[h..j]) ≥ SOPT (p[1..m ], s[h..j  ]) for all 0 ≤ m ≤ m, h − 1 ≤ j  ≤n.
Condition CS1 says that s[h..j] must be similar to p[1..m], and condition CS2(CS3)says that the left(right) end of s[h..j] is optimal when the right(left) ends of both s[h..j]and p[1..m] are ﬁxed. Note that the deﬁnition above can be also expressed using a
notion of a locally optimal pair introduced by Erickson and Sellers [6]: a substrings[h..j] of s[1..n] is said to be a locally optimal occurrence if a pair of s[h..j] and p[1..m]is locally optimal as substrings of s[1..n] and p[1..m]. The purpose of introducing a
new notion is to distinguish a pattern from an occurrence.
Example 1 Let p =”abca” and s=”abcaabcdabddacad”. Deﬁne score function w as
follows:(x = y, x, y ∈ Σ)
 2
w(x, y) = −2 (x = y, x, y ∈ Σ)

−1 (x = - or y = -)Then, locally optimal occurrences of p in s are the following four substrings of s: (Seethe left ﬁgure.)s[1..4]s[5..9]s[9..15]s[13..15]====“abca”“abcda”“abddaca”“abca”(SOPT (p, s[1..4]) = 8),(SOPT (p, s[5..9]) = 7),(SOPT (p, s[9..15]) = 5),(SOPT (p, s[13..15]) = 5).

p=abca
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

s=abcaabcdabddacad

optimalalignment:

abca

abc-a ab---ca abca

abca

abcda abddaca a-ca

Score:

87

5

5Note that String s[9..13] =”abdda” is nota locally optimal occurrence of p even ifs[14..15] =”ca” because 3 = SOPT (p, s[9..13]) <SOPT (p[1..2], s[9..10]) = 4, which violates CS3.

Mining Approximate Patterns with Frequent Locally Optimal Occurrences

5

As you can see from the above example, a locally optimal occurrence matches tothe pattern very well near boundaries, which reduces the number of occurrences foressentially the same parts comparing to the simple method counting all the substrings
whose edit distance from the pattern is at most a given threshold. Boundary ﬁtness
also seems desirable for region estimation.
Definition 2 A substring s[h..j] of s[1..n] is said to be a minimal locally optimaloccurrence of string p[1..m] if s[h..j] is a locally optimal occurrence of p[1..m] andsatisﬁes the following minimality conditions:
CS2M SOPT (p[1..m], s[h..j]) > SOPT (p[g..m], s[h ..j]) for all 1 ≤ g ≤ m + 1, h ≤ h ≤j + 1 but (g, h) = (1, h), andCS3M SOPT (p[1..m], s[h..j]) > SOPT (p[1..m ], s[h..j  ]) for all 0 ≤ m ≤ m, h − 1 ≤j  ≤ j but (m , j  ) = (m, j).
Note that there might be more than one locally optimal occurrences s[h..j] for eachh (for each j) but the minimal one s[h..j0 ] (s[h0 ..j]) is unique.
For computational eﬃciency, pattern strings are limited to substrings in a given
string s in this paper. We consider the following frequent mining problem.
Problem 1 Given a string s, a score function w and a natural number σ, enumeratedistinct substrings s[h..j] such that the number of minimal locally optimal occurrencesof s[h..j] in s is at least σ.
Example 2 Consider s and w deﬁned in Example 1. Then, the number of minimal
locally optimal occurrences of s[1..4] =“abca” is three because s[9..15] =“abddaca”
only is not minimal among its four locally optimal occurrences. Note that the set ofoccurrences becomes disjoint in this case by virtue of minimality introduction. Whenσ = 3, the solution of the mining problem deﬁned above is “a”, “b”, “c”, “d”, “ab”,“ac”, “ca”, “abc”, “aca”, “cda”, “abca”, “abcda”. Notice that frequent substrings do
not have anti-monotone property in this problem.

2.2

Algorithm

Given a pattern string p[1..m], the number of minimal locally optimal occurrencesof p[1..m] in s[1..n] can be obtained utilizing an algorithm for the local alignment
problem. Actually, all locally optimal pairs are known to be enumerated by runningsuch an algorithm in both backward and forward directions [9]. Here, we propose analgorithm into which this technique is incorporated together with eﬃcient generationof patterns without duplication using a suﬃx tree.

6

Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

EnumSubstrFLOO(s)Input:
s[1..n]: string

1: Make the suﬃx tree T of string s.
2: for j = 0 to n do (D[j], H[j]) ← (0, (j + 1, 1))
3: v ←the root node of T
4: Optimality Check(s, v, 0, D, H,‘F’)
5: Make the suﬃx tree T r of the reversed string sr .
6: for j = 0 to n do (D[j], H[j]) ← (0, (j + 1, 1))
7: vr ←the root node of T r
8: Optimality Check(sr , vr , 0, D, H,‘B’)
Optimality Check(s, v, l, D0 , H0 ,mode)
Input:
s[1..n]: (reversed) string
v: a node of the suﬃx tree of sl: the depth of node v
D0 : D0 [j] = D[l, j]
H0 : H0 [j] = H[l, j]

1: for each child node u of node v do
2: (f, t) ← label of edge (v, u)
3: for j = 0 to n do (D[j], H[j]) ← (D0 [j], H0 [j])4: for j = f to t do
5:
if mode=F then6:
Forward Check(s, s[f − l..j], D, H)
7:
else
8:
occ list← list stored at the position j of edge (v, u)
9:
if Backward Check(s, s[f − l..j], D, H, occ list) ≥ σ then10:
Print s[n−j +1..n−(f −l)+1] as one of the answers
11:
end if12:
end if
13: end for
14: EnumFreqPat(s, u, l + t − f + 1, D, H,mode)
15: end for

Figure 1: Algorithms EnumSubstrFLOO and Optimality Check
Let D[i, j] be the maximum score among the scores
SOPT (p[g..i], s[h..j]) for all 1 ≤ g ≤ i + 1, 1 ≤ h ≤ j + 1. This value is known to be
calculated by dynamic programming based on the following recursive formula:0
if i = 0 or j = 0,





and
otherwise,





0



D[i, j] ← D[i − 1, j] + w(p[i], -)



max


 D[i, j − 1] + w(-, s[j])








D[i − 1, j − 1] + w(p[i], s[j]).

From the deﬁnition of D[i, j], condition CS2 is satisﬁed for s[h..j] if and only if
SOPT (p[1..m], s[h..j]) = D[m, j].
Let H[i, j] be the largest pair (h, g) of starting indexes in lexicographical orderamong those (h, g) that satisﬁes
SOPT (p[g..i], s[h..j]) = D[i, j]:
H[i, j] = max{(h, g) : 1 ≤ h ≤ j + 1, 1 ≤ g ≤ i + 1,
SOPT (p[g..i], s[h..j]) = D[i, j]}.
The deﬁnition of H[i, j] implies that conditions CS2 and CS2M are satisﬁed for s[h..j]
if and only if H[m, j] = (h, 1).

Mining Approximate Patterns with Frequent Locally Optimal Occurrences

Forward Check(s,p,D,H)
Input:
s[1..n]: string,p[1..m]: pattern
Update: D: D[j] = D[m − 1, j] → D[m, j]
H: H[j] = H[m − 1, j] → H[m, j]
1: CalDH(s,p[m],D,H)
2: occ list←NULL
3: for j = 1 to n do
4: (h, g) ← H[j]5: if D[j] > 0 and g = 1 then6:
Add (h, j) to the head of occ list
7: end if
8: end for
9: Store occ list at an appropriate position of the edge corresponding to pr in the suﬃx tree T r
Backward Check(sr , pr , D, H,occ list)
Input:
sr [1..n]: reversed string,pr [1..m]: reversed pattern
Update: D: D[j] = D[m − 1, j] → D[m, j]
H: H[j] = H[m − 1, j] → H[m, j]
Output: f : number of minimal locally optimal occurrences of p
1: CalDH(sr , pr [m], D, H)
2: if occ list= NULL then return 0
3: f ← 0
4: (hF , jF ) ← the ﬁrst element of occ list
5: for j = 1 to n do
6: if j = n − hF + 1 then7:(h, g) ← H[j]8:
if D[j] > 0, g = 1 and h = n − jF + 1 then9:f ← f +1
10:
end if11:
if no next element in occ list then return f
12:(hF , jF ) ← the next element of occ list
13: end if
14: end for
CalDH(s,c,D,H)
Input:
s[1..n]: stringc: the last letter p[m] of pattern p[1..m]Update: D: D[j] = D[m − 1, j] → D[m, j]
H: H[j] = H[m − 1, j] → H[m, j]
1: (d∗ , (h∗ , g∗ )) ← (0, (1, 2))
2: for j = 1 to n do
3: (d−1 , (h−1 , g−1 )) ← (d∗ , (h∗ , g∗ ))4: (d∗ , (h∗ , g∗ )) ← max{(0, (j + 1, 2)),
(D[j] + w(c, -), H[j]),(d−1 + w(-, s[j]), (h−1 , g−1 )),(D[j − 1] + w(c, s[j]), H[j − 1])}
5: (D[j − 1], H[j − 1]) ← (d−1 , (h−1 , g−1 ))6: end for
7: (D[n], H[n]) ← (d∗ , (h∗ , g∗ ))Figure 2: Algorithms Forward Check, Backward Check and CalDH
Note that H[i, j] can be also calculated using the following recursive formula:H[i, j] ←(j + 1, 1) if i = 0
max J[i, j] otherwise,

where
J[i, j]= {(j + 1, i + 1) : D[i, j] = 0}∪{H[i − 1, j] : D[i, j] = D[i − 1, j] + w(p[i], -)}∪{H[i, j − 1] : D[i, j] = D[i, j − 1] + w(-, s[j])}∪{H[i − 1, j − 1] : D[i, j] = D[i − 1, j − 1] + w(p[i], s[j])}.

7

8

Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

Conditions CS3 and CS3M can be checked by doing the same thing for the reversestings of p and s. Let pr and sr be the reverse strings p and s, respectively. Let D r
and H r for pr and sr be the correspondences of D and H for p and s. Then, conditions
CS3 and CS3M are satisﬁed for s[h..j] if and only if H r [m, n − h + 1] = (n − j + 1, 1).
We use the suﬃx tree of s for generating all substrings of s as candidate patterns
without duplication. Suﬃx tree T of string s[1..n] is a labeled tree that has n leaves1 .
Each leaf is labeled by diﬀerent natural number i ∈ {1, 2, ..., n}, and the path fromthe root node to the leaf labeled i corresponds to suﬃx s[i..n]. Each edge (v, u) also
has label (f, t) ∈ {1, 2, ..., n} × {1, 2, ..., n} which represents string s[f..t]. Each suﬃx
s[i..n] is the concatenation of the sequence of strings represented by edge labels on
the path from the root node to the leaf node labeled i. It is well known that the suﬃx
tree of a string s[1..n] can be constructed in O(n) time [7].
Example 3 The suﬃx tree for the string s in Example 1 is shown below.
(17,17)

(1,1)
(8,8)
(5,17)
4

(2,2)
(3,3)

(16,17)(14,17)13
15(11,17)(4,17)(8,17)

1

5

9

(2,2)

(3,3)
(10,17)(3,3)(11,17)(4,17)(8,17)

2

6

8

10

17
(9,9)
(12,17) (17,17)
16(14,17) 11
12(8,17)(4,4)(5,17)(16,17)3

14

7

Our algorithm, named EnumSubstrFLOO (Enumerate Substrings with Frequent
Locally Optimal Occurrences), is shown in Figure 1. The algorithm is composed oftwo stages, forward stage (lines 1-4) and backward stage (lines 5-8). In forward stage,
all the occurrences that satisfy conditions CS1, CS2 and CS2M are listed for eachcandidate pattern string. In backward stage, in which the given string and candidate
patterns are reversed, all the occurrences that satisfy conditions CS1, CS3 and CS3M
are counted for each candidate pattern string if it also belongs to the list made in
the forward stage. When the count is at least the minimum support σ, the pattern isprinted out (line 10 in algorithm Optimal Check in Figure 1).
Our algorithm generates all the substrings of s (or its reversed string sr ) by depth
ﬁrst traversal of the suﬃx tree of s (or sr ). The traversal is done by algorithm Optimality Check. Given node v in a suﬃx tree, for each its child node u, the algorithm
generates all the substrings of s (or sr ) that are concatenations of the substring corresponding to the path from the root node to v and non-empty preﬁxes of the label
string of the edge (v, u) as candidate patterns (s[f − l..j] at lines 6 and 9) and calls
itself recursively for u.
If patterns’ preﬁxes with length l are the same, then D[i, j] and H[i, j] are thesame for all 0 ≤ l, 0 ≤ j ≤ n. Thus, we can use D and H calculated at a parent
node in the calculation for a child node. In the calculation of D[m, j] and H[m, j],
1

Precisely speaking, there are n + 1 leaves including the end mark.

Mining Approximate Patterns with Frequent Locally Optimal Occurrences9

the algorithm keeps only the last rows of table D and H, which is a popular techniqueto enhance space eﬃciency for alignment algorithms. Also note that, in algorithm
CalDH in Figure 2, the value (h, g) of H[m, j] is not calculated correctly but always
set to (h, 2) when g > 1 because the value g is not necessary in such a case. (See lines
1 and 4 in CalDH.)
Let us consider the time complexity of EnumSubstrFLOO. First, CalDH triviallyruns in O(n) time. Both Forward Check and Backward Check run in O(n) time
because not only CalDH but also other parts of the algorithm runs in O(n) time.
Forward Check and Backward Check are called at most O(n2 ) times because there
are n leaves and they are called at most n times for the path from the root to eachleaf. Thus, total computational time of them is O(n3 ). The inside of the for-loop
beginning at line 1 and ending at line 15 in algorithm Optimality Check is executedO(n) times in total, and the inside of the for-loop beginning at line 4 and ending atline 13 is executed O(n2 ) times in total by the above reason, so O(n3) time is needed
for all the executions of Optimal Check without the time needed for executions of
Forward Check and Backward Check. In algorithm EnumSubstrFLOO, other partsneeds only O(n) time, so it runs in O(n3 ) time totally. The space complexity is O(n3 )because O(n2 ) occurrence lists are saved and each of them is O(n).
Theorem 1 Algorithm EnumSubstrFLOO runs in O(n3 ) time and (n3 ) space.
Since frequent patterns do not have anti-monotone property, pruning of the search
space using the property cannot be applied. However, maximally possible frequency isthe number of H[j] with the second component g = 1, which can be used for pruning
the search space. In our experiments, we used an algorithm using such pruning.
Remark 1 Algorithm EnumSubstrFLOO is separated into two stages and all the
candidate occurrences must be kept at the beginning of the second(backward) stage.
This is why O(n3 ) space is needed instead of O(n2 ) space. Actually, we can achieveO(n2 ) space calculation by executing Backward Check right after each execution of Forward Check. However, time complexity becomes O(n4 ) by this modiﬁcation because D r
and H r must be calculated from the beginning in every execution of Backward Check.

3

Mining Approximate Forests

3.1

Problem Setting

Let T be a labeled ordered tree whose nodes are labeled a letter in an alphabet Σ.
Let n denote the number of nodes in T . The id of node v in T is deﬁned as d if v is
visited dth in the postorder traversal of T . We call the node with id d as node d.
The (bottom-up) subtree of T rooted by node d, which is denoted by Td , is thesubtree that is composed of all the descendants of node d. Child, ancestor and descendant subtrees of subtree Td are subtrees rooted by child, ancestor and descendant

10

Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

nodes of node d, respectively. Subtrees rooted by nodes whose parent is the samenode is said to be sibling subtrees. A subtree rooted by an internal node is called
an internal subtree. We regard all isomorphic subtrees as the same subtrees. Let
ρ(T ) denote the number of distinct subtrees in T , and let ρ1 (T ) denote the number ofdistinct internal subtrees. We deﬁne the id of each distinct (internal) subtree as q if
the subtree is the qth-appeared distinct (internal) subtree in the sequence of subtrees
T1 , T2 , ..., Tn , where Ti is the subtree rooted by node i, namely, the subtree rooted by
the node visited ith in the postorder traversal of T . We also call the (internal) subtreewith id q as (internal) subtree q.
A contiguous sibling subtrees of T is called a subforest of T . Every subforest except
T itself can be represented by a triple (d, h, j): subforest (d, h, j) of T is a subforestthat is composed of a child subtree sequence of Td from the hth one to the jth one.
Let ΣT denote the set of subtree ids of T , namely, {1, 2, ..., ρ(T )}. Any forest thatis composed of subtrees in T can be denoted by a string on ΣT . Let sq (= sq [1..nq ])denote the id sequence of the child subtrees of internal subtree q, where nq denotes thenumber of child subtrees of internal subtree q. A subforest (d, h, j) is also represented
by sq [h..j] when the internal subtree id of Td is q. A distinct subforest of T can be
uniquely represented by an id sequence of its component subtrees.
Example 4 Consider a labeled ordered tree T shown below.

T4s 2 =’’23’’ 2 4 c
s 1 =’’1’’ 1

2

2

b

b 9 6 s 6 =’’4538’’s 3 =’’213’’ 9 a 5 3
3

c
3

1

15

a
1

6
1 2 b

7

8

1

3

a c

5

14

c10
3

b 8 5 s 5 =’’67’’
11

b
6

13

a7

4

s 4 =’’3’’

12

a

c

1

3

Tree T contains 15 nodes, 9(= ρ(T )) distinct subtrees, and 6(= ρ1 (T )) distinct internal subtrees. A number written above each node is its node id, a circled number neareach node is the id of the subtree rooted by the node, and a boxed number near eachinternal node is the id of the internal subtree rooted by the node. Subforest (9, 1, 2) of
T is the forest that is composed of three nodes 5, 6, and 7. For each internal nodeq, sq deﬁned above is also shown near q. Subforest (9, 1, 2) is also represented bys3 [1..2] =“21”.
As a real-valued score function on (ΣT ∪ {-}) × (ΣT ∪ {-}), we consider a scorefunction wT based on tree mapping [11]. Let T 1 and T 2 be labeled ordered trees whose
nodes are labeled a letter in Σ. A tree mapping M from T 1 to T 2 is a set of nodepairs M ⊆ V (T 1 ) × V (T 2 ) satisfying u1 = u2 ⇔ v1 = v2 for any (u1 , v1 ), (u2 , v2 ) ∈ M,
where V (T i ) denotes the set of nodes in T i for i = 1, 2. The score of mapping M isdeﬁned asscore(M) =(u,v)∈Mw(l(u), l(v))

Mining Approximate Patterns with Frequent Locally Optimal Occurrences


+

11

w(l(u), -)u:u∈T1 ,{v:(u,v)∈M }=∅+w(-, l(v)),

v:v∈T2 ,{u:(u,v)∈M }=∅where l(u) and l(v) are labels of nodes u and v, and w is a score function on (Σ ∪{-}) × (Σ ∪ {-}). Let MMC (x, y) denote a set of tree mapping from subtree x of T
(or an empty tree ‘-’) to subtree y of T (or an empty tree ‘-’) satisfying a certain
condition MC. Then, a score function wT on (ΣT ∪ {-}) × (ΣT ∪ {-}) is deﬁned aswT (x, y) =max

M ∈MMC (x,y)

score(M).

As a condition MC, we adopt the condition that M must be a constrained Tai
mapping [13]. Tree Mapping is said to be a constrained Tai mapping if, for any(u1 , v1 ), (u2 , v2 ), (u3, v3 ) ∈ M, the following conditions are satisﬁed:
MC1 M must be Tai mapping [11], that is,(1) u2 is a proper ancestor of u1 ⇔ v2 is a proper ancestor of v1 ,(2) u2 is placed at the left of u1 in the sibling order ⇔ v2 is placed at the leftof v1 in the sibling order, andMC2 the least common ancestor of u1 and u2 is a proper ancestor of u3 ⇔ the least
common ancestor of v1 and v2 is a proper ancestor of v3 .
Note that the score function using Tai mapping condition only is known to correspond to general tree edit distance. However, the time complexity of the best
known algorithm calculating that score function is O(n3 ). On the other hand, thescore function using constrained Tai mapping condition can be calculated in O(n2 )time [13]. Furthermore, condition MC2 seems a reasonable constraint as a structure
correspondence.
We extend locally optimal occurrences of a pattern string to those of a patternforest represented by a string p[1..m] on ΣT .
Definition 3 Let p[1..m] a string on ΣT . Subforest (d, h, j) of T is said to be a
locally optimal occurrence of forest p[1..m] if the following conditions are satisﬁed forthe internal subtree id q of Td :CT1 (left-right optimality) substring sq [h..j] of sq is a locally optimal occurrence ofstring p[1..m].
CT2 (upward-downward optimality)
SOPT (p[1..m], sq [h..j]) ≥ SOPT (p[1..m], sq [h ..j  ]) for all q  (= q) that is the internal subtree id of an ancestor or descendant subtree of Td and for all 1 ≤ h ≤nq + 1, h − 1 ≤ j  ≤ nq .

12Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

Example 5 Let T be a labeled ordered tree considered in Example 4. Let score function w on (Σ∪{-})×(Σ∪{-}) be the same one deﬁned in Example 1. Then, the locally
optimal occurrences of forest “23” in T are subforests (4, 1, 2), (9, 1, 3) and (14, 1, 2).
(See the ﬁgure below.)
b
c
b
a

c

b

a
c

a
s 2[1..2]=’’23’’ (4,1,2)

b a ca(9,1,3)(15,2,3)

c

b
b

a
c

(14,1,2)Note that substring s6 [2..3] of s6 is a locally optimal occurrence of string “23” but
subforest (15, 2, 3) is not a locally optimal occurrence of forest “23” because 3 =SOPT (“23”, s6 [2..3]) < SOPT (“23”, s3 [1..3]) = 5 which means that CT2 does not holdfor subforest (15, 2, 3). Subforest (15, 2, 3) includes subforest (9, 1, 3) and only one ofthem is a locally optimal occurrence of forest “23” by virtue of the introduction of
upward-downward optimality.
We also extend minimality of a locally optimal occurrence deﬁned for a string
to that for a tree. Condition CT2M guarantees that no minimal locally optimaloccurrence contains other such occurrences.
Definition 4 Let p[1..m] a string on ΣT . Subforest (d, h, j) of T is said to be aminimal locally optimal occurrence of forest p[1..m] if (d, h, j) is a locally optimaloccurrence of p[1..m] and satisﬁes the following minimality conditions for the internal
subtree id q of Td :CT1M substring sq [h..j] of string sq is a minimal locally optimal occurrence of string
p[1..m]CT2M SOPT (p[1..m], sq [h..j]) > SOPT (p[1..m], sq [h ..j  ]) for all q  (= q) that is theinternal subtree id of a descendant subtree of Td and for all 1 ≤ h ≤ nq + 1, h −1 ≤ j  ≤ nq .
Problem 2 Given a labeled ordered tree T , a score function w and a natural numberσ, enumerate distinct subforests sq [h, j] of T such that the number of minimal locally
optimal occurrences of sq [h..j] in T is at least σ.
Example 6 Let a labeled ordered tree T and a score function w be those consideredin Example 5. When σ = 3, the solution of Problem 2 is the set of subforests s1 [1],s5 [1], s2 [2], s2 [1], s2 [1..2], s5 [1..2], namely, three height-0 subtrees composed of thenode labeled “a”,“b” or “c”, one height-1 subtree composed of two nodes labeled “b”
and “a”, and two height-1 subforests composed of three nodes labeled “a”, “b” and“c”.

Mining Approximate Patterns with Frequent Locally Optimal Occurrences

13

EnumSubforestFLOO(T )Input:
T : labeled ordered tree having n nodes

1: Calculate the subtree id and internal subtree id for each subtree of T
2: For all q = 1, 2, ..., ρ1 (T ),
N [q]

←

the number of internal subtrees q in T

I[q][k]←the root node id of the kth occurrence ofinternal subtree q for k = 1, 2, ..., N [q]3: For all 0 ≤ q ≤ r ≤ ρ(T ),wT (q, r) ← tree edit distance between subtree q and r.

4: For all q = 1, 2, ..., ρ1 (T ),sq ← subtree-id seq. of child subtrees of internal subtree q.

5: Make the generalized suﬃx tree T

for the set of strings {sq : q = 1, 2, ..., ρ1 (T )}.

6: for all 1 ≤ q ≤ ρ1 (T ), 0 ≤ j ≤ nq do
7: (Dq [j], Hq [j]) ← (0, (j + 1, 1))
8: end for
9: v ← the root node of T
10: Optimality Check T({sq }, v, 0, {Dq }, {Hq },‘F’)
11: srq ← reversed string of sρ1 (T )−q+1 for q = 1, 2, ..., ρ1 (T )12: Make the generalized suﬃx tree T r
for the set of reversed strings {srq : q = 1, 2, ..., ρ1 (T )}.

13: for all 1 ≤ q ≤ ρ1 (T ), 0 ≤ j ≤ nq do
14: (Dq [j], Hq [j]) ← (0, (j + 1, 1))
15: end for
16: vr ← the root node of T r
17: Optimality Check T({srq }, vr , 0, {Dq }, {Hq },‘B’)

Optimality Check T({sq }, v, l, {Dq0 }, {Hq0 },mode)
Input:{sq }: set of (reversed) strings
v: a node of the generalized suﬃx tree of {sq }l: the depth of node v{Dq0 }: Dq0 [j] = Dq [l, j]{Hq0 }: Hq0 [j] = Hq [l, j]

1: for each child node u of node v do
2: (q0 , (f, t)) ← label of edge (v, u)
3: for all 1 ≤ q ≤ ρ1 (T ), 0 ≤ j ≤ nq do
4:(Dq [j], Hq [j]) ← (Dq0 [j], Hq0 [j])5: end for
6: for j = f to t do
7:
if mode=F then8:
Forward Check T({sq }, sq0 [f − l..j], {Dq }, {Hq })
9:
else
10:
occ list← list stored at the position j of edge (v, u)
11:
if Backward Check T({sq }, sq0 [f − l..j], {Dq }, {Hq }, occ list) ≥ σ then12:
Print sq0 [n−j +1..n−(f −l)+1] as one of the answers
13:
end if14:
end if
15: end for
16: Optimality Check T({sq }, u, l+t−f +1, {Dq }, {Hq },mode)
17: end for

Figure 3: Algorithms EnumSubforestFLOO and Optimality Check T

3.2

Algorithm

Since the half of the conditions, CT1 and CT1M, that occurrences must satisfy
in Problem 2 are the same as conditions CS1-3 and CS2-3M in Problem 1, an algorithm for Problem 2 can be designed by extending EnumSubstrFLOO. The extended
algorithm is called EnumSubforestFLOO shown in Figure 3.

14

Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

The extensions are mainly the following two points.
E1 For a pattern forest which is represented by a string p[1..m] on ΣT , the number of
locally optimal occurrences of p[1..m] in string sq are summed up for all internal
subtree ids q = 1, 2, ..., ρ1 (T ). (Precisely speaking, the number of occurrencesin sq must be multiplied by N[q], where N[q] is the number of internal subtrees
q in T .)E2 Occurrences must also satisfy upward-downward optimality and minimality,
namely, CT2 and CT2M.
For extension E1, EnumSubforestFLOO makes the generalized suﬃx tree [7] for theset of strings {s1 , s2 , ..., sρ1 (T ) } in order to generate all candidate patterns eﬃciently
without duplication. (See lines 5 and 12 in EnumSubforestFLOO.) In the generalized
suﬃx tree, each edge label also contains the information of which string: edge label(q0 , (f, t)) means string sq0 [f..t]. (See line 2 in Optimality Check T in Figure 3.),2))(6,(2,5))))(5,(1,3
)
)
3
(2,
(5, )
)
5
,
,(4
(6

(6,(1,5

)) (2
,(2

))

,3

,(2

(2

))
,4

,(3
(3

(6,(3,5

6,1

2))

3,2

(2,

1,1

6,2

5,1

5,2

(1,

))

(1,(2,2))(1,(1,1
1))
(1,
(2,
))
(3,(2,4
3))
(2,
(2,
3,1
2,2
2,1
6,3

))

Example 7 The generalized suﬃx tree for the set of strings {s1 , s2 , s3 , s4 , s5 , s6 } ={“1”, “23”, “213”, “3”, “67”, “4538”}, which is the set of child subtree id sequencesof internal subtrees for T in Example 4, is shown below. Note that leaf label q, i
corresponds to sq [i..nq ].

6,4

1,2

For extension E2, downward optimality and minimality, which is described by
CT2M alone, are checked in Forward Check T and upward optimality of CT2 ischecked in Backward Check T.
In Forward Check T, which is shown in Figure 4, CT2M is checked using array E
after Dq [m, j] and Hq [m, j] are calculated for all q and j. The value to be stored in
E[i] is the maximum alignment score SOPT (p[1..m], sq [h, j]) among those for sq [h..j]such that internal subtree q  is a descendant subtree of internal subtree q (subtree i)and 1 ≤ h ≤ nq + 1, 0 ≤ j ≤ nq . Then, CT2M holds for subforest (d, h, j) of any
Td with internal subtree id q if and only if Dq [m, j] > E[sq [k]] for all h ≤ k ≤ j andHq [m, j] = (1, h), which are checked at lines 8 and 9 in Forward Check T. The valuesof E[i] for i = 1, 2, ..., ρ(T ) can be calculated in a bottom-up manner by propagating
the value for child subtrees of subtree i (line 14) and maximum score for forests
composed of those child subtrees (line 12) to subtree i. Note that E-values for child
subtrees are calculated before E-values for their parent subtrees in Forward Check T
because internal subtree ids are in node-id order of their root nodes, and node ids arein visit order by the postorder traversal of T .

Mining Approximate Patterns with Frequent Locally Optimal Occurrences

15

Forward Check T({sq }, p, {Dq }, {Hq })Input:{sq }: set of strings
p[1..m]: pattern
Update: {Dq }: Dq [j] = Dq [m − 1, j] → Dq [m, j]{Hq }: Hq [j] = Hq [m − 1, j] → Hq [m, j]
1: for q = 1 to ρ1 (T ) do CalDH(sq , p[m], Dq , Hq )2: for k = 1 to ρ(T ) do E(k) ← 0
3: occ list←NULL
4: for q = 1 to ρ1 (T ) do
5: i ← subtree id of internal subtree q
6: for j = 1 to nq do
7:(h, g) ← Hq [j]8:
if Dq [j] > 0 and g = 1 then9:
if Dq [j] > E[sq [k]] for all h ≤ k ≤ j then10:
Add (q, h, j) to the head of occ list
11:
end if
12:
if Dq [j] > E[i] then E[i] ← Dq [j]13:
end if14:
if E[sq [j]] > E[i] then E[i] ← E[sq [j]]15: end for
16: end for
17: Store occ list at an appropriate position of the edge corresponding to pr in the generalizes suﬃx tree T r
Backward Check T({srq }, pr , {Dq }, {Hq },occ list)
Input:{srq }: set of reversed strings
pr [1..m]: reversed pattern
Update: {Dq }: Dq [j] = Dq [m − 1, j] → Dq [m, j]{Hq }: Hq [j] = Hq [m − 1, j] → Hq [m, j]
Output: f : number of minimal locally optimal occurrences of p
1: for q = 1 to ρ1 (T ) do CalDH(srq , pr [m], Dq , Hq )2: if occ list= NULL then return 0
3: f ← 0
4: (qF , hF , jF ) ← the ﬁrst element of occ list
5: for k = 1 to n do F [k] ← 0
6: for q = 1 to ρ1 (T ) do
7: q ← ρ1 (T ) − q + 1
8: for k = 1 to N [q] do
9:for all child node d of node I[q][k] do
10:
if F [I[q][k]] > F [d] then F [d] ← F [I[q][k]]11:
end for
12: end for
13: for j = 1 to nq do
14:
if q = ρ1 (T ) − qF + 1 and j = nq − hF + 1 then15:(h, g) ← Hq [j]16:
if Dq [j] > 0, g = 1 and h = nq − jF + 1 then17:
for k = 1 to N [qF ] do
18:
if Dq [j] ≥ F [I[qF ][k]] then f ← f + 1
19:
end for20:
end if21:
if no next element in occ list then return f
22:(qF , hF , jF ) ← the next element of occ list
23:
end if24:
if Dq [j] > 0, g = 1 then25:
for k = 1 to N [q] do
26:
for d = (nq −j +1)th to (nq −h+1)th child node id of node I[q][k] do
27:
if Dq [j] > F [d] then F [d] ← Dq [j]28:
end for29:
end for30:
end if
31: end for
32: end for

Figure 4: Algorithms Forward Check T and Backward Check T
In Backward Check T, which is also shown in Figure 4, upward optimality of CT2 ischecked using array F after Dq [m, j] and Hq [m, j] for reversed strings srq are calculated
for all q and j. The value to be stored in F [d] for node d is the maximum alignment

16

Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudoscore SOPT (p[1..m], sq [h..j]) among those for sq [h..j] such that internal subtree q is an ancestor subtree of subtree Td with internal subtree id q. Then, the upward
optimality part of CT2 holds for subforest (d, h, j) of subtree Td with subtree id q
if and only if Dq [m, j] ≥ F [d] and Hq [m, j] = (1, h), which are checked at line 18
in Backward Check T. The value of F [d] for d = 1, 2, ..., n can be calculated in a
top-down manner by propagating the value of its parent subtree (lines 8-12) and the
maximum score for the substrings of sq that contains the correspondence of Td (lines
24-30) to subtree Td , where q is the internal subtree id of the parent subtree of Td .
Note that F -values for parent subtrees are calculated before F -values for their child
subtrees in Backward Check T because the order of reversed strings srq is also reversed.
(See line 11 in EnumSubforestFLOO.)
Let us consider the complexity of EnumSubforestFLOO. First, consider the preparation phase of EnumSubforestFLOO. Subtree ids can be calculated in O(n) time inaverage using hashing technique. Internal subtree ids can be calculated in O(n) timefrom subtree ids. It is easy to check that N and I can be calculated in O(n) time at line
2 in algorithm EnumSubforestFLOO. Score function wT (q, r) for all 0 ≤ q ≤ r ≤ σ(T )can be calculated in O(n2 ) time when constrained Tai mapping is adopted to deﬁne wT
because wT (q, r) for a pair of subtrees q and r can be calculated in O(nq nr ) time andwT (q, r) for all subtree pairs are calculated on the way to calculating wT (σ(T ), σ(T )),where nq and nr are number of nodes in subtrees q and r, respectively. All strings sq
can be set in O(n) time because the length sum of all strings is O(n). Unfortunately,
Forward Check T and Backward Check T run in O(n2 ) time in worst case because
pattern with length O(n) may occur O(n) times. (See line 9 of Forward Check T andline 26 of Backward check T.) Since complexity of the other parts is the same as thatfor EnumSubstrFLOO, the total time complexity is O(n4 ) in average and the spacecomplexity is (n3 ).
Theorem 2 Algorithm EnumSubforestFLOO runs in O(n4 ) time in average and O(n3 )space.

4

Application to SRR Extraction

In this section, we propose a method using algorithm EnumSubforestFLOO to extract search result records (SRRs) from result pages returned by search engines for
submitted keywords.

4.1

MethodGiven the tag trees of result pages of a search engine, our method outputs a frequent forest as a wrapper for the search engine. Then, SRR extraction is done byenumerating all minimal locally optimal occurrences of the wrapper forest.

Mining Approximate Patterns with Frequent Locally Optimal Occurrences17

In almost all search sites, SRRs appear as repetitions of almost the same tag
structure, namely, as occurrences of a frequent approximate pattern forest. Thus,
given an appropriate minimum support σ, an approximate pattern forest for SRRs is
contained in the set of frequent forests. However, it also contains approximate patternforests for the following ones:
1. SRRs with shifted boundaries,
2. SRRs with wrong unit size (connected SRRs),
3. other data records and4. popular small components.
First, candidate patterns are narrowed by removing patterns consisting of only one
node and patterns with overlapping occurrences. Most patterns of 2 and some patternsof 4 above are removed by this operation. Let C denote the narrowed candidate set.
Then, each candidate pattern p in C is evaluated from the following three measures:
ave sz(p) average number of nodes over all occurrences of p;
total text len(p) summed text length of all occurrences of p;ave text len(p) average text length over all occurrences of p.
The patterns of 1 above tend to have smaller total text len because its frequency is
one smaller when SRRs appears contiguously. The patterns of 3 above tend to havesmaller ave size and total text len in a search result page, and the patterns of 4 above
tend to have smaller ave text size. Each of these three measures is normalized by
dividing by its maximum value among those of all candidates in C, and weighted
combined score
total text len(p)ave sz(p)+ αmaxp ∈C ave sz(p )maxp ∈C total text len(p )ave text len(p)+ βmaxp ∈C ave text len(p )is calculated for each candidate p, where α and β are parameters to be speciﬁed. In
our experiments, we set α = 1.0 and β = 0.2. Finally, we select one candidate patternwith the maximum above score.
For performance improvement, the following three heuristics are incorporated into
our method.
• For utilizing a no result page when it is available, the score of a candidate patternthat has occurrences in a no result page is discounted by factor γ. We set γ to
0.7 in our experiment.

18

Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

• In result pages generated by some search engine, all appearances of a search
keyword are emphasized using tag <b> or tag <strong>, which causes low similarity of tag structure between two distinct SRRs. So, we added a preprocessing
in which every such emphasis tag and its corresponding end tag are removed
when non-space text appears between its last preceding tag and itself.
• When the variance on the number of nodes in a subforest corresponding toan SRR is large, pattern forest corresponding to a large SRR might not be sosimilar to subforests corresponding to small SRRs. In order to ﬁnd a patternforest that is similar to all the subforests corresponding to the SRRs in a given
tree, we ﬁnally select a pattern forest p with the largest total text len(p) among
those that is similar to the one with the maximum above score.

4.2

Experiments

We conducted experiments on SRR extraction to demonstrate eﬀectiveness of our
method proposed in Sec. 4.1.
4.2.1

Methodology

We used data set 1 and data set 2 collected for performance evaluation of ViNTs[14]. Data set 1 and 2 are composed of result pages of 100 and 101 search engines,
respectively. The data sets contain 11 pages for each search engine, the six pages ofthem are for training and the rest ﬁve pages are for test. One of the training pages
for each search engine is no result page. Here, the set of all the training pages in data
set x(= 1, 2) is called data set x TR, and the set of all the test pages is called data
set x TE.
As in the experiments conducted by Zao et al. [14], target SRRs are records ofjust the major section for each search result page. If more than 25 target SRRs arecontained in one result page, just 25 records are counted as target ones2 to avoid thatthe overall performance depends too much on the performance for the result pages
that contains many records.
We implemented our method using C++ language and ran our programs on Dell
Dimension 8200 (Pentium-4 2.20GHz, 512KB cache, 1GB memory) with Ubuntu 8.10.
For each search engine, we ﬁrst made a wrapper by our proposed method using all
the six training pages. Then, we extracted estimated SRRs from each training or test
page using the wrapper. Note that no result page contained in the training data set

2

In [14], they regarded the ﬁrst 25 records as the target ones, but if do so, the problem of how
to calculate precision measure arises. Without decreasing target records, we normalized the numberof extracted records and the number of correct records by multiplying them by 25/(the number oftarget records) in our evaluation.

Mining Approximate Patterns with Frequent Locally Optimal Occurrences

19

Table 1: Extraction performance comparison with ViNTs. FLOO stands for our
method and parenthesized numbers in ViNTs column are the performance of its NV
version.
#SRRs#Extracted#Correct
Recall(%)
Precision(%)
F-measure(%)

Data set 1 TR
FLOO
ViNTs
6940
6919
6883.06905(6833)
6832.06901(6722)
98.4
99.7(97.2)
99.3
99.9(98.4)
98.8
99.8(97.8)

Data set 1 TE
FLOO
ViNTs
6172
6219
6072.06169(6111)
6017.06164(6001)
97.5
99.1(96.5)
99.1
99.9(98.2)
98.3
99.5(97.3)

Data set 2 TR
FLOO
ViNTs
6980
6905
6909.86872(6465)
6702.06740(6283)
96.0
97.6(91.0)
97.0
98.1(97.2)
96.5
97.8(94.0)

Data set 2 TE
FLOO
ViNTs
5859
5822
5936.25801(5525)
5729.25673(5390)
97.8
97.4(92.6)
96.5
97.8(97.6)
97.1
97.6(95.0)

was used only for training and not for the SRR extraction. In wrapper construction,
minimum support σ was set to 25. We used the following score function w:
 2(x = y, x, y ∈ Σ)
w(x, y) = −6 (x = y, x, y ∈ Σ)

−3 (x = - or y = -)Note that the optimal alignment score of two trees deﬁned by this score function isat least 0 if and only if 75% of nodes in the two trees coincide.
We evaluated the extraction performance by recall and precision measures thatwere calculated by
Recall =#Correct#Correct, Precision =.
#SRRs#Extracted

F-measure, the harmonic mean of the above two measure, is also used for performance
evaluation:
2Precision · Recall
F-measure =Precision + Recall.
4.2.2

Results

Performance of our method is shown in Table 1 together with performance of ViNTs3 .
The most notable characteristic of ViNTs is use of visual (rendering) information, andits NV version of ViNTs is the one without such information use.
Our method performed worse than the normal version of ViNTs but better than its
NV version in terms of F-measure. Considering performance improvement potentialof our method by using visual information, this result demonstrates eﬀectiveness of
our method as a base method of SRR extraction.
To investigate computational eﬃciency of our method, we measured running timeof wrapper construction and SRR extraction for all data.
The average CPU times are shown below together with some measured values
indicating input data complexities.
3

The small diﬀerence on the number of target SRRs between our method and ViNTs is due tothe diﬀerence on interpretation between us and them because the data sets contain no description
about what are target SRRs.

20

Atsuyoshi Nakamura

phase#page per run
ave. #node
ave. #subtree
ave. len. of subtree seq.
ave. CPU time

Hisashi Tosaka

Mineichi Kudo

wrap. const. extraction
6
13710.4
622.0
153.8
91.4
633.6
269.0
0.88610.0202

According to the above table, wrapper construction takes less than one second in
average and SRR extraction takes about only 20 msec. This result for wrapper construction is surprising because it uses EnumSubforestFLOO as a subprocedure thatruns in O(n4 ) time for a tag tree with n nodes. See the left ﬁgure in Figure 5, whichis the log-log scale graph plotting the relation between the total length m of distinctρ(T )
subtree sequence of tree T , namely, m = q=1 |sq |, and the wrapper construction timefor T . (Precisely speaking, not a single tree but 6 trees are inputted to the algorithm
that is extended for such a input.) According to the log-log scale linear regression
Time (sec.)
100

Time (sec.)
0.09
0.08
0.07

10

0.06
0.05

1

0.04
data set 1 TR
data set 1 TEdata set 2 TR
data set 2 TE

0.03
0.1

0.01
100

data set 1 TR
data set 2 TR
f(x)=10^{-5.33} x^{1.73}

0.02
0.01
0

1000
Total length of distinct subtree sequences

0

1000

2000
3000
Number of nodes

4000

5000

Figure 5: Running times of wrapper construction phase (left) and extraction phase(right)analysis, wrapper construction takes only O(m1.73 ) time for our data sets. Note thatm is at most the number of nodes n and was about 1/6 of n in average for our training
data sets. (See ‘ave. len. of subtree seq.’ of the above table.) As for SRR extraction,
its running time looks linearly depending on the number of nodes according to theright ﬁgure in Figure 5.
4.2.3

Discussion

A strong point of using frequent mining to extract SRRs, or data records more generally, is to be able to extract SRRs even if none of them appears consecutively. This
could be demonstrated in our experiment using ViNTs data sets. The result pages
returned by ’health library’ search engine in data set 1 are composed of SRRs inseveral categories and SRRs in each category are displayed separately following thecategory name. (See Figure 6.) Our method extracted every SRRs separately without
extracting all the SRRs in one category together with its category name as one big

Mining Approximate Patterns with Frequent Locally Optimal Occurrences

21

Figure 6: A part of ‘care.htm,’ which is a result page by ’health library’ search engine.
The result of three categories are shown in this part.

SRR. Such extraction is basically impossible using methods that detect contiguous
occurrences such as MDR [8], ViPER [10] and ViNTs4 [14].
When the number of SSRs are smaller than given minimum support σ, a wrapper
for target SRRs cannot be constructed, which is one weak point of our method.
Development of a method that determines σ automatically is desired in the future.
In the case that variance on the size of subforests corresponding to SRRs is large,
some of them cannot be extracted by the methods using edit score or distance todetect repetitions. Such methods include not only our method but also MDR and
ViPER5 . For this case, methods that detect a record separator like ViNTs seem towork. Taking account of such a separator may improve our method.

4.3

Related Works

Representative methods on automatic data record extraction from web pages are themethod in [5], Omini [3], IEPAD [4], MDR [8], ViNTs [14] and ViPER [10]. IEPAD
applies string algorithms to a string representation of a web page and the others
applies tree algorithms to a tag tree of a web page. IEPAD enumerates maximal
4

In the experiments on ViNTs, SRRs including a categorical name might have been regarded ascorrect ones.
5
ViPER improves this weak point a little by calculating edit score so as to give no penalty to thecontiguous repetitions.

22

Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

frequent substrings as candidate wrapper patterns by means of exact matching, anduses multiple string alignment to generalize the patterns. It is NOT fully automatic
because the best pattern is selected by users. The other tree-algorithm-based methods
are classiﬁed into two categories. One is the methods of identifying record boundaries[5, 3, 14]. Omini and the method in [5] ﬁrst locate the subtree that contains the records
of interest and then ﬁnd a record separator using several heuristics. ViNTs ﬁrst ﬁnds
all candidates of a record separator and consecutive similar blocks separated by it, andthen selects the best scored separator among them using a heuristically designed scorefunction. The other is the methods of detecting consecutive repetitions [8, 10]. MDR
ﬁnds repetitions composed of similar forests with the same number of subtrees using
tree edit distance to measure the similarity between two subtrees. ViPER ﬁnds not
only such repetitions but also those composed of similar forests with variable numberof subtrees using a tree edit distance modiﬁed so as to make any repetitions of thesame forests match without any additional cost even if the numbers of repetitions are
diﬀerent.
Our method is neither a method of identifying record boundaries nor a methodof detecting consecutive repetitions. Our approach, which uses frequent mining toﬁnd a record structure common among all web pages in a target site, is the same as
IEPAD’s approach but our method is composed of only one stage to ﬁnd approximate
patterns while IEPAD is composed of two stages, a stage ﬁnding exact patterns anda stage generalizing them to approximate ones. Also note that our method is a fully
automatic. Our method uses edit distance to obtain approximate patterns like MDR
and ViPER but occurrences of a pattern do NOT need to appear consecutively.
According to the previous experimental results [8, 14, 10], ViNTs and ViPER,
which use rendering information, are the best performers among all previous systems
for SRR extraction task.

5

Concluding Remarks

Main stream of frequent mining on strings or trees is to ﬁnd patterns that are containedin many strings or trees belonging to a given set of strings or trees. Obtained patterns
by such mining can be used as features for classiﬁcation. In this paper, we proposed afrequent mining appropriate for another use of obtained patterns, namely, estimationof occurrence regions. We believe the importance of such mining and existence ofother applications of our mining method.

References[1] R. Agrawal and R. Srikant. Mining sequential patterns. In Proceedings of the
11th International Conference on Data Engineering (ICDE 1995), pages 3–14,
1995.

Mining Approximate Patterns with Frequent Locally Optimal Occurrences

23[2] T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Sakamoto, and S. Arikawa. Eﬃcient
substructure discovery from large semi-structured data. In Proceedings of the 2nd
SIAM International Conference on Data Mining (SDM 2002), pages 158–174,
2002.
[3] D. Buttler, L. Liu, and C. Pu. A fully automated object extraction system forthe world wide web. In Proceedings of the 21st IEEE International Conference
on Distributed Computing Systems (ICDCS’01), pages 361–370, 2001.
[4] C. Chang and S. Lui. Iepad: information extraction based on pattern discovery.
In Proceedings of the 10th international conference on World Wide Web, pages
681–688, 2001.
[5] D. Embley, Y. Jiang, and Y. Ng. Record-boundary discovery in web documents.
In Proceedings of the 1999 ACM SIGMOD international conference on Management of data, pages 467–478, 1999.
[6] B. W. Erickson and P. H. Sellers. Recognition of patterns in genetic sequences.
In D. Sankoﬀ and J. B. Kruskal, editors, Time Warps, String Edits, and Macromolecules : The Theory and Practice of Sequence Comparison, chapter 2, pages
55–91. Addison-Wesley, Reading, MA, 1983.
[7] D. Gusﬁeld. Algorithms on Strings, Trees, and Sequences: Computer Science andComputational Biology. Cambridge University Press, New York, 1997.
[8] B. Liu, R. L. Grossman, and Y. Zhai. Mining data records in web pages. In
Proceedings of the 9th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining (KDD 2003), pages 601–606, 2003.
[9] J. P. Schmidt. All hightest scoring paths in weighted grid graphs and their application to ﬁnding all approximate repeats in strings. SIAM Journal on Computing,27(4):972–992, 1998.
[10] K. Simon and G. Lausen. Viper: Augmenting automatic information extraction
with visual perceptions. In Proceedings of the 14th conference on Information
and Knowledge Management (CIKM 2005), pages 381–388, 2005.
[11] K.-C. Tai. The tree-to-tree correction problem. Journal of the Association for
Computing Machinery, 26(3):422–433, 1979.
[12] M. J. Zaki. Eﬃciently mining frequent trees in a forest: Algorithms and applications. IEEE Transaction on Knowledge and Data Engineering, 17(8):1021–1035,
2005.
[13] K. Zhang. Algorithms for the constrained editing distance between ordered labeled trees and related problems. Pattern Recognition, 28(3):463–474, 1995.

24

Atsuyoshi Nakamura

Hisashi Tosaka

Mineichi Kudo

[14] H. Zhao, W. Meng, Z. Wu, V. Raghavan, and C. Yu. Fully automatic wrapper
generation for search engines. In Proceedings of the 14th international conferenceon World Wide Web (WWW 2005), pages 66–75, 2005.
[15] F. Zhu, X. Yan, J. Han, and P. S. Yu. Eﬃcient discovery of frequent approximate
sequential patterns. In Proceedings of the 7th IEEE International Conference on
Data Mining (ICDM 2007), pages 751–756, 2007.