数理解析研究所講究録 1325 巻 2003 年 81-86

81
頻出順序木パターンを見つけるオンラインアルゴリズム
Online Algorithms for Discovering Frequent Substructures from
Semi-structured Data Strealn
浅井達哉

Tatsuya Asai

安部賢治

Kenji Abe

有村博紀

川副真治

Hiroki Arimura

Shinji Kawasoe

有川節夫

Setsuo Arikawa

九州大学大学院システム情報科学府・研究院
Department of Informatics,Kyushu University

1

はじめに

データマイニングとは, データベースに蓄積された大量のデータから, 自明でない規則性やパターンを半自動的にとりだす方法についての科学的研究であり,ビジネス分野や科学技術分野などのさまざまな対象分
野で, その適用が盛んに行なわれている. また, 高速
なネットワークと安価な大容量記憶装置の発達によって, ウェブページや XML 文書に代表される半構造デー
タ $[2, 18]$ がネットワーク上に蓄積されており, 大規模
半構造データを対象としたデータマイニング (半構造データマイニング) に関する研究が盛んに行なわれつつある [1, 5, 9, 12, 14, 19, 21].
一方, 高速ネットワークとウェブ技術の発達によって, 近年, 電子商取引やウェブサイト管理など, 新しい

形態のネットワーク上の応用プログラム普及し始めている. これらの応用プログラムでは, データは静的なレコードの集合ではなく, 膨大な半構造データがネッ
トワーク上を流れ続けるデータストリームの形態をしていることが特徴である. 今後, このような大規横半構造データストリームを対象とした, 効率のよいデー

タマイニング手法の重要性が増すものと予想される.
本稿で考察する半構造データストリームは,

1. 膨大な量のデータが,2. 時間的に変化しながら,
3. 連続して流れ続ける
4. 高速なデータストリー\Delta
であることが特徴である. よって, このような大規模
半構造データストリームを対象とするアルゴリズムは,制限された計算資源しか使わずに長時間働き続け, 任
意の時点で有益な近似解を提供できることが望ましい.
このアルゴリズムが実現すれば, ネットワークログからの異常検出や XML データストリームからのトレンド検出などへの応用が期待できる.
我々は, 半構造データとパターンのモデルとしてラベルつき順序木を採用し, 先に開発した順序木の効率よい枚挙法 [5] を用いて, 半構造データストリームをラベルつき順序木の節点列として定式化する. これは,データストリーム上を, 巨大な XML データが連続的に配送される場合をモデル化している. そして, 半構
連絡先:浅井達哉, 〒 812-8581 福岡市東区箱崎 6-10-1, 九州大学大学院システム情報科学府情報理学専攻, Phone: 092-642-2697,
FAX: 092 642 2698. Mail: t-asai\copyright i .
.jp$\mathrm{k}\mathrm{y}\mathrm{u}\mathrm{s}\mathrm{h}\mathrm{u}-\mathrm{u}.\mathrm{a}\mathrm{c}$造データストリームに対する頻出パターン発見アルゴ
リズム StreamT を開発する [6]. このアルゴリズムでは, 掃木枝上のボトム出現を逐次的に更新することにより, パターンの出現位置を漸増的に計算している.
この手法と Hidber [11] による候補集合の管理戦略を組み合わせることにより, アルゴリズムは無限のデー

タストリームに対して有限の資源しか用いずに効率的に働く.
本稿の構成は次のとおりである. 2 節で, 半構造デー
タストリームからのオンラインマイニング問題の定式化を与え, 3 節では, それを解くオンラインアルゴリ.

$\mathrm{f}\mathrm{f}\mathrm{l}\iota\sim.\text{実験を}\uparrow\mathrm{A}_{l\mathrm{u}\backslash \mathrm{f}\mathrm{f}\mathrm{l}\text{型}\grave{\text{ア}}J\mathrm{s}3’J\text{ズ}\grave{\text{ム}の有効}\mathrm{E}\text{を}\ovalbox{\tt\small REJECT}}^{\backslash \mathrm{t}},\mathrm{x}^{\backslash }\text{ム_{}\mathrm{a}}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{m}\mathrm{T}[_{\frac{6]}{\mathrm{T}}}^{1_{\llcorner}^{-\text{つ}\mathrm{A}^{\mathrm{a}}\text{て_{}\grave{1}’}1\grave{\grave{\text{へ}}る}.4\mathrm{f}\mathrm{f}\mathrm{l}\mathrm{i}\text{て^{}\backslash }|\mathrm{h}\text{実}\vec{\tau}_{l}-\text{タを}}}$価する. 最後に 5 節で本稿をまとめる.

1J

関連研究

半構造データベース $[2, 18]$ の普及にともない, 半
構造データマイニングの研究が盛んに行なわれるようになってきた [5, 9, 12, 14, 19, 21]. これらの多くは,Apriori [3] 風にパターンの探索を行なっている. それに対して, Zaki [21] と Asai ら [5] は, それぞれ独立に, 半構造データからの効率的な順序木パターン探索
法 (最右拡張) を開発した. これは, Bayardo [7] による集合枚挙木を用いたアイテムセット探索法の自然な拡張である. 本稿で提案するアルゴリズムは, 部分的に最右拡張の概念を用いるものの, 上述 $[5, 21]$ の半構
造データマイニング手法とはまったく異なることに注意されたい.
最近, オンライン型データマイニングの研究が盛んになってきている [10, 13, 16]. Hidber [11] は, トラ

ンザクションデータのストリームに対するオンラオ
ン型の相関規則マイニングアルゴリズムを開発した.
Parthasarathy ら [15] は, 時系列パターンを発見する
オンラインマイニングアルゴリズムを与えている. また, Mannila ら [13] は, エピソードと呼ばれる特殊な時系列パターンの発見問題を考察している. Yamanisbi ら [20] は, 効率的なオンライン異常検出システム

SmartSifter を開発した. このシステムはネットワーク
への侵入検出などに応用されている.

82
22

ラベルつき順序木のストリーム表現

本節では, ラベルつき順序木の記号列による表現を導入する. この表現は, データストリームから XML 文
書が, テキスト順に順次読み出される場合に対応する.

定義 1

上のラベルつき順序木 $T$ の深さ・ラベル対のこ表現とは, 記号列 $s(T)=((d_{1}, \ell_{1}),$
は, $T$ のプリオーとである. ここに,ダー順で 番目の節点 の深さとラベルの組であり,$k=|T|$ である.

図 1: データ木 $D$ とパターン木 $T$$\mathcal{L}$$\ldots,$$(d_{k}, \ell_{k}))$$(d_{t}, \ell_{i})\in \mathrm{N}\mathrm{x}\mathcal{L}$

$i$

2

定式化

21

半構造データとラベルつき順序木

例えば, 図 1 のデータ木 $D$ に対する深さ.
$=$$((0, R),$ $(1, A),$ $(2, A)$ ,ラベル対表現は $s(D)$,$(2, B)$ $(2, A),$ $(2, B),$ $(1, A),$ $(2,A),$ $(2,A),$ $(2, B))$

本稿では, XML 文書などの半構造データ [2] をラベ
ルつき順序木 [4] でモデル化する.
をラベノレのラベノレつき順序木
有限集合とする. 半構造データベースとパターンの形
式的なモデルとして, ラベルつき順序木を用いる. ラベ
ルは半構造データの属性名, タグつきテキストのタグに対応する. 順序木とは子供の集合に順序が付けられた木
上のラペルつき順序木を次の五である. 形式的には,
項組 $T=(V, E, B,L,v_{1})$ で定義する. $G=(V, E,v_{1})$はを根とする木である. $V$ は節点の集合を,
は親子関係を表す. $L:Varrow \mathcal{L}$ はラベル関数を, 二項
は $G$ における兄弟関係を表す.
関係$\mathcal{L}=\{\ell, \ell_{0}, \ell_{1}, \ldots\}$$\mathcal{L}$$E\subseteq V^{2}$$v_{1}$

ラベルつき順序木 $T$ の大きさを, 節点数 $|T|=|V|$からと定義する. 節点 $v\in V$ の深さを, 根節点への経路に含まれる辺の数と定義する. $T$ の節点集合
は $V\tau=\{1, \ldots, k\}$ であり $(k=|T|)$ , これらは $T$ の) で番号付けられてい前置順巡回 (pmrder
ると仮定する. このとき, $T$ の根は $v_{1}=1$ であり,
番右の葉 (最右 aeJ $rml(T)$ は $rml(T)=k$ となることに注意されたい. $T$ の最右枝を $RME(T)$ であらわす.

とな[5] を用いることにより,任意のラベルつき順序木 $T$ に対して, その深さ・ラベル対表現 $s(T)$ が一意に定まることが分かる.
る. 次で定義する最右拡張

定義 2 $S$ を大きさ $k-1$ のラベノレつき順序木, $”\geq 0$
を $S$ の最右葉 $v_{k-1}=k-1$ の深さとする. 任意の自に対し
然数 O\leq d\leq dm。a+l と任意のラベノレをもつ新たな節て, $S$ の $(d,\ell)$ 拡張とは, $S$ にラベ
点 $v_{k}=k$ を追加して得られるラベルつき順序木 $T$ である. ただし, $S$ の最右葉 $v_{k-1}$ の先祖で深さ力 1 $d-1$の一番右のであるような節点を とするとき,子として追加する.
$\ell\in \mathcal{L}$$J\mathrm{s}\ell$$v_{k}\mathrm{F}\mathrm{h}z$$z$$B\subseteq V^{2}$

が $S$ の $(d,\ell)$ 拡張であるとする. このとき,の前者とい , $S$ を $T$ の後者という.

$T$

$T$
$S$

を

$\mathrm{A}\mathrm{a}$$v$$v_{1}$$\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{v}\epsilon \mathrm{r}\mathrm{s}\mathrm{a}\mathrm{l}$$T$ と $D$ を上の順序木とする.
バターンの出現$T$をパターン木, $D$ をデータ木と呼ぶことにここで.
する. 以下の条件を満たす関数 : $V\tauarrow V_{D}$ が存在するとき, $T$ が $D$ に出現すると定義する :(i) は単は親子関係, 兄弟関係とラベルの値射であり, (ii)を保存する. ただし, パターン木 $T$ 中で隣接する兄弟が, それらの出現先で隣接する必要はない. この を,$\mathcal{L}$$\varphi$$\varphi$$\varphi$$\varphi$$T$$v_{\dot{\mathrm{t}}}$2.3

データマイニング問題

集合 $A$ に対して, A

Δ $A$ 上のすべての無限列をあらわす.
$D$ の深さは有限であると仮$D$ をデータ木とする.
定する (幅は無限であってもよい). $D$ に対する半構造データストリームとは, 無限列 $S=s(D)=$のことである. ここ$D$ の番目の節点 $v:=i$ の深さ.に, $v:=(d:$ ,\ell
ラペル対表現である. このとき, : を $S$ の 番日の節点と呼ぶことにする. 我々は節点 $v:=i$ と時刻 を同一視する.
我々のデータマイニング問題を以下に記す.
$(v_{1}, v_{2}, \ldots, v_{\dot{l}}, \ldots)\in(\mathrm{N}\mathrm{x}\mathcal{L})^{\infty}$

$i$

$v$

$i$

$i$

から $D$ へのマッチング関数と呼ぶ.
$\underline{\frac{*\hslash \mathrm{f}\mathrm{f}\vec{\tau}-\text{タ}\lambda \text{ト^{}\mathrm{l}}/-\mathrm{A}l1\grave{\mathrm{b}}\emptyset}{\mathrm{r}\grave{J}\overline{7}4_{\grave{r}’}\#\alpha \mathrm{f}\mathrm{f}\mathrm{l}/\mathrm{s}\text{タ}-}\nearrow^{\backslash }*\mathrm{R}b\mathrm{H}}$以後, パターン木 $T$ を単にパターンと呼ぶ.
$k$$\varphi$$\varphi$$\varphi(T)\subseteq V_{D}$$\varphi$$\varphi$

例として, 図 1 のデータ木 $D$ とパターン $T$ を考える. 図中の矢印は,への埋め込みが $E\tau=\{7,8,10\}$となるようなマッチング関数 を表している. $T$ の $D$
への全ルート出現は節点 2 と節点 7 の 2 種類であり,最右葉出現は節点 4, 6, 10 の 3 種類である.
$D$$\varphi$

力:

半構造データストリーム, 実数 $0<\sigma\leq 1$ .
岡題 : 時刻 で : が入力されると仮定する $(i\geq 1)$ .
このとき, 出現頻度が 以上となるような頻出パター$\lambda$

を $T$ かをデータ木, $T$ を大きさ のパターン,に関する $T$ の $D$
ら $D$ へのマッチング関数とする.
と定義
による $T$ の像への埋め込みを,に関する j レート出現を $roc(\varphi)=\varphi(1)$する. また,と, 最右葉出現を $rmo(\varphi)=\varphi(k)$ と定義する.
$D$

$S$

$=$

$(v_{1},v_{2}, \ldots, v:, \ldots)$
$i$

$v$

$\sigma$

各時刻 において出力せよ.
オンライン型マイニングアルゴリズムの目標は, 無

ン $T$ を,$i$限のデータストリームに対して有限の資源しか用いずに半永久的に働き, 任意の時点で利用者の質問に迅速に応えることである.
パターンの出現頻度として, 我々は以下の 2 つのモ.
デノレを定義する. ただし, $1\leq j\leq i$ に対して,$hit_{j}^{(1)}$

83
Algorithm StreamT$(\mathcal{L}, S, \sigma)$\lambda 力: ラベル集合 , データ木 $D$ に対応する半構造データ
ストリーム $S=s(D)=(v_{1}, v_{2,}\ldots., v_{i}, \ldots)$ , 最小サ
ポート $0<\sigma\leq 1$
出力: パターン集合の列 ( , F2, ...,
) $(i\geq 1)$ . た
だし, 任意の $j\geq 1$ に対してろ
.
$L$

.

$F_{j},$$\mathcal{F}_{1}$$\ldots$$\subseteq \mathcal{T}$変数:, 掃木枝スタック $B$ $=$候補集合$B$ [Top]).
( $B[0],$手法:
1. を大きさ 1 の全パターンの集合とする;$B:=\emptyset,$$Top:=-1$ $i:=1_{j}$2. 次の節点 $v:=(d,\ell)$ が存在するかぎり. 以下を行なう :$C$$\subseteq$

図 3: 時刻$\tau$

における掃木枝$i$.

$SB_{1}$$\ldots,$.

$C$

2-(a) W 木枝スタックのバケット $B[0],$ $\ldots[B[d-1]$ を更新する :$(d,\ell)$ ,:);$(B, EXP)$ :=Up 出訛 eB(B,とバケット
2-(b) 候補集合
B 同を更新する :;$\mathrm{C},$$C$$(B,C):=\mathrm{U}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{C}(EXP, B,C, (d,\ell),i)$以上の頻度をもつ頻出パターンの集合 .
を出力する.
データストリームから継続的に頻出パターンを計算するために, アルゴリズ\Delta はデータ木 $D$ の上で掃木枝(sweep branch) と呼ばれる $D$ の根 から現在の節点. への経路を右へずらしていき, 掃木枝と交わるすべてのパターンを探索する. これを実現するために, アルゴリズ はステージごとに以下の情報を更新する :$\subseteq \mathcal{T}$$v_{1}$$v_{*}$$\text{ム}$2-(c) $\mathcal{F}_{\dot{*}}=\{T\in C|freq:(T)\geq\sigma\}$ を出力する;$i=i+1$ ;図 2: オンライン型半構造データマイニングアルゴリズム$\mathcal{F}_{1}$$\sigma$・候補集合.
・掃木枝スタック $B=(B[0], B[1], \ldots, B[T\varphi])$ .
$C\subseteq \mathcal{T}$中のルート
任意の候補パターン $T\in C$ は, $T$ の
出現数 cnnt(T) をもつ. また, 深さ の最新のルート出現 $Rto\tau[r]$ を, 深さごとに保持する.
$D_{i}$$r$は次のように定義される関数である. もし. へのルート出現ならばの$T$それ以外のときは $hit_{j}^{(1)}.(T)=0$が$v_{\mathrm{j}}\in\gamma_{D}$であり,$hit_{\mathrm{j}}^{(\dot{l})}(T)=1$$D_{*}$.

3.2

定義 3 $T$ を任意のパターン, $S$ を半構造データスト
リームとする. このとき, 時刻 d こおける $T$ の頻度
freq:(T) を, 以下のように定義する.
へ
碁本型 このモデルでは, 時刻 における $T$ の$i$$D_{\dot{1}}$の異なるルート出現数 $c\sigma unt_{i}(T)$ を数える.

.

(1)$f \mathrm{r}eq_{\dot{l}}(T)=\frac{1}{\dot{|}}count\cdot(|T)=\frac{1}{i}\sum \mathrm{j}_{=1}hit_{j}^{(1)}.(T)$

これは, 過去のデータの影響力を, 過ぎ去った時間に対して指数的に逓減させるモデルである [20].
$0<\gamma<1$ を実数 (忘却定数) とし,

忘却型$Z. \cdot=\sum_{j=1}^{1}.\gamma^{\dot{*}-\mathrm{j}}$

掃木枝を用いた漸増的なパターン発見

候補パターンの出現位置を見つけるために, パター
ンの埋め込みを完全に保持する必要はない. アルゴリ
ズムは, 掃木枝を $D$ 上で右へ走らせて, パターン $T$と掃木枝の交差をステージごとに更の埋め込み新しながら保持し, 漸増的に候補パターンの出現を計算する. パターン $T$ の埋め込みと掃木枝の交差に関して, 次の性質が成り立つ.
$\varphi(T)$.ををパターン $T$ の任意の埋め込み,
補題 1
の最右枝と
時刻 の掃木枝とする. このとき.
. との交差 $I_{T}=RMB(\varphi(T))\cap SB.\cdot$ が空集合でなの根を含む.
は $D$ の経路となり,ければ,$SB_{1}$$\varphi(T)$$\varphi(T)$$i$$SB_{1}$

とおく.

$\varphi(T)$$I_{T}$$freq_{7^{1}}^{\mathrm{f}\mathrm{g}}, \cdot(T)=\frac{1}{z_{*}}$.

$\sum \mathrm{j}_{=1}\gamma^{:-j}hit_{j}^{(\dot{*})}(T)$.

(2)$\square$

この補題にしたがい, 次の定義を与える. パターン $T$と $SB$:の埋め込み \mbox{\boldmath $\varphi$}(T)、と掃木枝 $SB_{1}$. に対して,の交差を $I_{T}=RMB(\varphi(T))\cap SB_{1}$. とする (図 4). こと深い節点 を,中でもっとも浅い節点のとき,のルート出現, ボトム出現と
それぞれ
に関する
$\varphi(T)$$I_{T}$

3$SB_{\dot{l}}$オンラインマイニング手法呼ぶ.

本節では, 基本型モデルに対するオンライン半構造
データマイニングアルゴリズム StreamT を与える.

3.1$I\tau$$v_{r}$のルート出現は$\varphi$

一致することに注意せよ.
が成り立つときは,$v_{b}$$I_{T}$$I\tau$に関する $T$ のルート出現とまた,.

$RMB(\varphi(T))\subseteq SB_{1}$のボトム出現と$\varphi$に関する $T$の最右葉出現は一致する.
次の補題は, 最右葉出現の漸増的な特徴づけを与える.

アルゴリズ A の概要

我々の提案するアノレゴリズム Stre mT を, 図 2 に示す. このアノレゴリズムは, 各ステージ $i=1,2,$において, 半構造データストリー $S$ から節点 . =(d:,\ellを受け取り, 候補パターンの頻度を計算する. アルゴ
リズムは, 利用者からの要請に応じて, ステージ で$\ldots$$\text{ム}$$v_{*}$$i$

補題 2 $T$ を大きさ $k>1$ のパターンとする. 時刻 において, $T$ が現在の節点 を最右葉出現にもつことの必要十分条件は, 次の (i),(ii) を満たす大きさ $k-1$ のパターン $S$ が存在することである. (i) $S$ はボトム出現の親節点をもち, (ii) $T$ は $S$ のとして$i$$v_{\dot{*}}$$v_{b}$$v_{\dot{*}}$$(d-\mathrm{r}, \ell)$

84$Bi\cdot 1$

$Bi$

図 4:

$SB_{1}$.

に関する $T$ のルート出現とボトム出現

$r$

.

$b$

は $S$ のノレートの深さ,は拡張である. ここに,口のラベノレである
.
は
の深さ,
出現
:
$d$

$\ell$$v$

図 5: 時刻 $i-1$ と時刻$i$における掃木枝スタツク

$r$

$v$

$v_{r}$

この補題により. 候補パターン $T\in C$ のすべての最右葉出現を, $T$ の後者 のボトム出現を用いて計算できることが分かる. 我々のアルゴリズム StreamT は,掃木枝スタツク $B=(B[0], B[1], \ldots, B[T\varphi])$ を管理す$S$

ることにより, パターンの埋め込みと掃木枝の交差を記録する. ここで, 掃木枝スタツクの任意の要素 (バケットと呼ぶ) $B[b]$ は. $(T,r, b)$ の形の三項組を保持.にと は, $T$ のする. $T\in C$ は候補パターン.
とボトム出現 の深さである.
関するルート出現
掃木枝スタック $B=(B[0], B[1], \ldots,B[T\varphi])$ が以で下の条件 (i),(ii) を満足するとき, $B$ は
date であるという. (i) スタツク $B$ の長さが掃木枝の長さと一致, すなわち $T\varphi=|SB:|$ が成り立ち, (ii)
任意の $0\leq h\leq T\varphi$ に対して, $B$ の 番目のバケットのうちでボ$B[h]$ は, 三項組
トム出現が $b=h$ となるものをすべて含む.
次の補題は, 時刻 における掃木枝スタツク . の各$r$$SB_{1}$$b$$v_{b}$$v_{r}$$\mathfrak{B}^{1\mathrm{J}}$$i$

補集合 , 節点 $v$
$C$

$h$

$\tau=(T,r, b)\in \mathcal{T}\mathrm{x}\mathrm{N}\mathrm{x}\mathrm{N}$$B_{1}$

バケットに関する再帰的な特徴づけを与える.

$B_{:}$

1. 任意の $0\leq b<d-1$ に対して,$\tau\in B_{\dot{\iota}}[b]$の必要十分条件は $\tau\in B_{:-1}[b]$ である.

2. $b=d-1$ のとき, $\tau=(T,r, d-1)\in B_{1}.[d-1]$ の必要十分条件は, 以下の (i),(ii) のどちらかが成り立つことである.
が存在し,$B_{i-1}[d]\cup\cdots\cup B:-1[T\varphi:-1]$$\cdot$$(T, r, h)\in$

$i$

.

.候

-REMOVE $:=\{(T, r,b)\in BELOW|r\geq d1j$
-CHANGE $:=\{(T,r, b)\in BELOW|r\leq d-1\}$ ;$-B[d-1]:=B[d-1]\cup\{(T,r, d-1)|(T,r, b)\in$

CHANGE};

2. ラベルの 1-パターン$\ell$$\{(T_{\ell}, d, d)\}$$T_{p}$;

に対して, $EXP$$:=$

3. 任意の $(S,\mathrm{r},d-1)\in B[d-1]$ に対して以下を行なう :$-S$ の $(d-r, \ell)$ 拡張 $T$ に対して, $EXP:=EXP\cup$$\{(T, r, d)\}$;4. { $B,$ $EXP)$ を出力する;
図 6: 掃木枝スタツク更新アルゴリズム

これに基づき, 掃木枝スタックを再帰的に更新するア
ノレゴリズム UpdateB を, 図 6 に示す. このアノレゴリズ\Delta
は, 任意の時刻 において, 古い掃木枝スタツク $B_{:-1}$ と現在の節点 $v:=(d,\ell)$ を受け取り, 新しい掃木枝スタツ$B_{i}[d-1]$
クの中で最初の 個のバケット $B_{i}[0],$を出力する.
次の系は, 補題 3 よりただちに示される.
$i$

$d$

$B_{:}$$\ldots,$における while) レー
プが時刻 \sim こて発動したと仮定する. このとき, アルは, 以下の (i),(ii) をゴリズム出力する. (i) 番目のバケット $B[d]$ を除くすべてのバケット $B[0],$$B[d-1]$ が時刻 で up-tO-date であるような掃木枝スタック $B$ , (ii) 時刻 でであるような 番目のバケット $B[d]$系 4 図 2 のアノレゴリズ$2-(\mathrm{i}\mathrm{i}2-(\mathrm{i}\}r\tau\leq d.\cdot\leq h^{f}\in B_{-1}[d1]s\text{る}\dot{\mathrm{g}}\text{数}h$, 現在の時刻-BELOW:=B[司 $\cup\ldots\cup B[T\varphi];T\varphi=d-1$ ;$\mathrm{g}$

このとが共に uptO-date でき, 掃木枝スタック $B_{:-1}$ とあると仮定すると, 次の 1-4 が成り立つ.

$=(d,\ell)$$EXP\subseteq \mathcal{T}\mathrm{x}\mathrm{N}\mathrm{x}$補
3 $v,\cdot=(d,\ell)$ をデータストリーム $S$ における現在の節点, $B_{k}=(B_{k}[0],B_{k}[1], \ldots, B_{k}[T\varphi_{k}])$ を時刻$k\in\{i-1,:\}$ における掃木枝スタックとする.

.

N.
出力 : 三項組の集合
手法 :1. もし $d\leq T\varphi$ ならば. 以下を行なう :$\mathrm{u}\mathrm{p}- \mathrm{t}\triangleright$$SB.\cdot$$i$Algorithm UpdateB(B, $C,$ $(d,\ell)$ ,:)\lambda 力 : 掃木枝スタック $B=(B[0],B[1], \ldots, B[T\varphi])$$\text{ム}$$\mathrm{S}\mathrm{t}\prime \mathrm{e}\mathrm{a}\mathrm{m}\mathrm{T}$$\cup \mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{B}(B,C, (d, \ell),\dot{*})$

$d$

を満たす.

$i$

3. $b=d$ のとき, $\prime r=(T, r, d)\in B_{1}.[d]$ の必要十分条
件は, 以下の条件 (i),(ii) のどちらかが成り立つことである.
$3-(\mathrm{i}\mathrm{i}3-(\mathrm{i}\}$$\overline{\mathit{7}}\dot{\text{へ}}J\mathrm{s}\mathfrak{G}(S,r,d-1)\in B_{\dot{\iota}}[d-1]\ell \text{をもつ大きさ}1\emptyset$

三項
は $S$ の $(d-r,\ell)$ 拡張である.

4. 任意の $b>d$ に対して,$B_{:}[b]$が存在し,$\ldots,$3.3は未定義である.

$B_{\dot{*}-1}$$\mathrm{u}\mathrm{p}- \mathrm{t}\mathrm{o}- \mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}\square$.

候補集合の管理

本節では, 候補集合 の管理法について述べる.
, 候補集合 を管理するアノレゴリズム
図を示す. 我々のアルゴリズムは, Hidber[11] と同様に, 候補パターンとして頻出パターン集合の n り ative$C$$7|_{\llcorner}^{-}$$\}_{\llcorner}^{-}$$i$$\text{る_{}T}$$\square$

図 5 , 補題 3 に基づいて掃木枝スタツク
更新する様子を示す.

.

$d$

を

$C$

$\cup \mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{C}$border [15] (後者パターンが頻出となるような非頻出85
Algorithm UpdateC $(EXP_{\mathrm{f}}B_{:}C. (d, \ell).i)$
入力 :三項組の集合 $EXP$ , 掃木枝スタック $B$ $=$
候補集合
番目の節点
$v_{\iota}=(d,l)$ ,現在の時刻 .
$(B[0]_{:}B[1]\ldots.iB[Top])$ ,$C,$

デルにおける $T$ の頻度きることが分かる.

$freq_{\gamma,i}^{\mathrm{f}\mathrm{g}}(T)$を効率よく計算で$i$$i$

出力 : 更新後の掃木枝スタックと候補集合 (B. ).
$C$

手法 :

35

アルゴリズムの解析

におけるアノレゴリズム StreamT の計算量は以下のとおりである.
とする. このと時刻 H こおける掃木枝スタックをき, ステージ におけるアノレゴリズム UpdateB とdateC の時間計算量は, それぞれ $O(\Sigma_{j=d-1}^{To^{p}}|B_{i-1}[j]|)$
時間, $O(kC+D)$ 時間となる. ここに,は時刻 のはパターンの最大サイズ, $C$ は
入力節点 : の深さ,に最右葉出現をもつ候補パターン数, $D$ はステージで削除された候補パターンの数である. また, ステー
ジ における領域計算量は,領域である.
したがって, 我々のアルゴリズムは, 掃木枝スタックと候補集合の大きさ程度の時間と領域しか使用しない.
ステージ

1. 任意の三項組 $(T_{:}r_{:}b)\in EXP$ に対して, そのルート出現$\rho$

が $\rho\neq Rto_{T}[r]$ を満たすならば以下を行なう:$-Rto_{T}[r].--\rho$ ;$B_{i}$$i$$-T\in C$ ならば,count(T) $:=count(T)+1$ ;$-T\not\in C$ かつ $T$ の後者が頻出ならば,
かつ $C:=C\cup\{T\}$ ;count(T)$\cup \mathrm{p}-$$d$$:=\mathrm{c}r$

非行な出うな後者をもつパターン$v_{i}$$i$$O( \sum_{\mathrm{j}=1}^{To^{\rho}}|B_{i}\mathrm{U}^{\cdot}]|+k|C|)$$i$;

4. 任意の三項組 $(T, r, b)\in EXP$ に対して, 以下を行なう :$-T\in C$ ならば $B[d]:=B[d]\cup\{(T_{:}r, b)\}j$

$i$

$k$

$v$

2. $B[d]==\emptyset;Top:=djfreq_{i}(T);=count(T)/i$ ;$T\in C$ に対して, 以下を
3.
$-C=C\backslash \{T\}$$i$

5. $(B_{l}C)$ を出力する;

4

図 7: 候補集合の更新アルゴリズム

実験
我々は, 基本型と忘却型のアルゴリズムを SAX と上で実験を行った. 実験には, 以パターン) までを保持する. 候補集合の管理は, 以下Java で実装し,の 4 つの手順で行われる.

下のスペックのマシンを用いた.

初期化

大きさ 1 の全パターンを候補集合

$C$

に入れ

これは StreamT (図 2) の最初に行なわれる.

る.

インクリメント 現在の節点 が最右葉出現となる
候補パタ– ン $T\in C$ に対して, count(T) を 1 増やす.
挿入 パターン $T\not\in C$ がストリームに出現したとを加える.
き’ その後者 $P\in C$ が頻出ならば,削除 頻出な候補パターン $T\in C$ が非頻出になった$T$ のすべての前者(最右拡張) を から削除する.
ら–,
ただし, 大きさ 1 のパターンは削除しないものとする.
$v_{i}$.

.

$\mathrm{P}\mathrm{C}$PcntiumlII lGHz, 1500 mcgabytes RAM,WindOws2000 (4.2 節規模耐性実験), 1000 megabytes RAM,
PcntiumlII
WindOws2000 (4.3 節アルゴリズムの比較実験)$1.2\mathrm{G}\mathrm{H}\mathrm{z}$$C[]^{-}\llcorner T$

$C$

3.4

忘却モデルへの拡張

4.1

データ

我々は, 実験データとして, 2 種類のデータセット
dblp と $wsw$ を用意した.
dblp は計算機科学分野の論文目録サイト DBLP
で公開されている XML データ dblp.ml
であり, 対応する半構造データストリームの節点数は3,185,138, 異なるタグ数は 22 である. このデータは,
42 節の規模耐性実験に用いる.
もう 1 つのデータセット $wsw$ は, [17] で提供されている XML データ.xml.xml とを, $w,s,w$ の順に結合して得られた節点数 22,830 のデータである. $w$ と に含まれるタグの種類は, それ
ぞれ 13 種類と 11 種類であり, 双方に共通するタグは存在しない. このように, データセット $wsw$ は, 時間$[8_{\mathrm{J}}^{1}$$(130\mathrm{M}\mathrm{B})$

本節では, アルゴリズム

を, 定義 3 の忘却モデルに適用する方法を示す.
忘却モデルにおけるパターン $T$ の頻度は, 定義 3 の(2) 式で定義される. すなわち, 忘却モデルでは, 時
刻 における頻度は各々のルート出現が発見された時
刻 に関するすべての重みに依存する.
$\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{e}\ovalbox{\tt\small REJECT} \mathrm{m}\mathrm{T}$$i$$\gamma^{i-j}$$j$, hitj ffl
記する. また,
におけるパターン $T$ が最後に出現した時間を $lt(i)$ とする. このとき, 次の補題が成り立つ.
$freq_{\gamma,i}^{\mathrm{f}^{\mathrm{g}}}(T)\text{と}hit^{(i)}.(T)\text{を},$$\text{と}$$\text{そ}t\iota \text{そ^{}\backslash }\backslash \mathrm{k}1f_{\Gamma}\mathrm{i}$$\text{時_{}A}\emptyset \mathrm{J}_{i}$補題 5 任意のパターン $T$ と時刻 H こ対して, 以下の漸化式が成り立つ.
$fr_{0}$$=$$fr_{i}$$=$.

$w=\mathrm{w}\mathrm{e}\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{g}$$s=\mathrm{s}\mathrm{o}\mathrm{a}\mathrm{p}$$s$

変化する半構造データストリームを意図して人工的に作成されたデータである. このデータは, 43 節のア
ルゴリズムの比較実験に使用する.

0,)$[perp]_{i}lt\cdot.$$\dot{.}-\gamma\iota t(i)fr\iota t(i)+\frac{1}{i}$

hiti

42

$(i>0)$
口

この補題から,$lt(i)$ を保持することにより,

忘却モ

規模耐性

最初に, 大規模な XML データを用いた規模耐性実験を行い, アルゴリズム StreamT の性能を評価する.

86

.

5

図 8: 規模耐性実験

おわりに$b^{\backslash }\mathrm{b}l\mathrm{J}\mathfrak{l}^{-}$

本稿では, 半構造データストリームからのオンライ
ンデータマイニングを考察し, 効率よいオンライン半
構造データマイニングアルゴリズム StreamT を与えた. アルゴリズムに忘却の概念を導入した結果, 過去の影響を受けずにデータの時間変化に柔軟に追従することを実証した.
今後は, 半構造データストリームからの異常検出やトレンド発見などに, 提案手法を応用していきたい.

参考文献[1] K. Abe, S. Kawasoe, T. Asai, H. Arimura, and$\S\dot{\mathrm{t}}\mathrm{r}\mathrm{u}6\mathrm{s}\mathrm{A}1_{\dot{\mathrm{D}}\mathrm{a}}^{\mathrm{o}}\mathrm{U}\mathrm{i}’\ovalbox{\tt\small REJECT}\rho_{PKDD}\mathrm{b}\S \mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{u}\rho 1_{-14}^{6\mathrm{C}\mathrm{O}\mathrm{V}6},\mathrm{U}_{\mathrm{A}12}^{\mathrm{o}\mathrm{r}\mathrm{S}}\ovalbox{\tt\small REJECT}[$

Springer, 2002.
[2] S. Abiteboul P. Buneman, D. Suciu, Data on
Morgan Kaufmann, 2000.
[,$3p=\mu_{1\mathrm{n}Pw^{\mathrm{I}}c.th\epsilon}^{\mathrm{s}\mathrm{r}\mathrm{i}\mathrm{h}\mathrm{n}\mathrm{t}\mathrm{F}\mathrm{a}\mathrm{s}\mathrm{t}}$[4]彦$\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}\mathrm{V}\mathrm{L}D\mathrm{B}$,$th\epsilon$

Web,

.

$\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{A}*487-499,1994$$\mathrm{A}\mathrm{h}\mathrm{o},$$\mathrm{A}.\mathrm{V}.\mathrm{H}\mathrm{o}\mathrm{p}\mathrm{c}\mathrm{r}\mathrm{o}\mathrm{f}\mathrm{t},\mathrm{J}\mathrm{E}\mathrm{U}11\mathrm{m}\mathrm{a}\mathrm{n},\mathrm{J}.\mathrm{D},Datatu|\epsilon sa\mathrm{r}\mathrm{t}dAlgo\mathrm{r}\dot{\mathrm{z}}thm\epsilon,\dot{\mathrm{A}}\mathrm{d}\mathrm{d}\mathrm{i}’\S \mathrm{o}\mathrm{n}-\mathrm{W}\mathrm{e}\mathrm{a}1\mathrm{e}\mathrm{y},19\dot{8}3.St|\mathrm{u}\mathrm{c}-$[5] T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Sakamoto,

図 9: 基本型

史叉儼$\mathrm{S}\mathrm{e}\mathrm{m}\mathrm{i}-\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}\mathrm{S}.\mathrm{A}\mathrm{r}\mathrm{i}\mathrm{k}\mathrm{a}\mathrm{w}\mathrm{a},\mathrm{E}\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{e}\mathrm{n}\mathrm{t},\mathrm{S}$音[6] T. Asai, H. Arimura,

S. Aribwa.

この実験では, dblp データに対して最小サボートを$\sigma=1$ (%) に固定し,データストリームの節点が 2000

個処理されるごとにアルゴリズムの計算時間を測定した. 実験結果を図 8 に示す.
実験より, アルゴリズム StreamT は, 入カサイズに対してほぼ線形時間で動作する. この結果は, 提案するオンラインアルゴリズムが. 高速に流れ続ける大規
模な半構造データストリームに対して, 効率よく働き続けることを示している.

$\mathrm{P},\mathrm{u}.\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}$$\mathrm{D}\mathrm{i}\epsilon \mathrm{c}\mathrm{o}\mathrm{v}\mathrm{e}BndSIA\mathrm{k}$on Data Mining $(SDMBO\theta B),$ $158-174$ ,2002.
\S tructured[7]’$ln_{t’lC}^{\mathrm{m}\mathrm{L}}\{$

K. Abe, S. Kawasoe, and$\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{m}1\mathrm{n}Pm\mathrm{c}theB\theta \mathit{0}\ell lB\mathrm{s}_{EInt\overline{\eta}}^{\mathrm{S}\mathrm{e}\mathrm{m}\mathrm{i}}\mathrm{o}\mathrm{n}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{A}1\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}\mathrm{s}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{M}i\mathrm{n}\mathrm{i}\mathrm{n}$Conf. on Data

$M\dot{\iota}n\dot{m}g[ICDM’\mathit{0}sj,$$27-34$ ,2002.

.

$\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{a}\mathrm{S}\mathrm{e}\mathrm{S},\mathrm{I}\mathrm{n}p_{roc.SIGM\delta_{D\mathit{9}\mathit{8},8}5_{-93,1998}^{\mathrm{L}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{f}\mathrm{o}\mathrm{m}}}’\mathrm{a}\mathrm{y}\mathrm{a}\mathrm{r}\mathrm{o}.\mathrm{E}\mathrm{f}\mathrm{f}\mathrm{l}\mathrm{c}\mathrm{i}\mathrm{e}\mathrm{n}\mathrm{t}1\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{n}$.uni-trier.
[81 DBLP, http:, R. D. King, Finding Frequent
, H.
[9]L.
Substructures in Chemical Compound\S , $\ln Pm.$ KDD$30-36$ ,1998.
[10]$//\mathrm{d}\mathrm{b}\mathrm{l}\mathrm{p}$$\mathrm{d}\mathrm{e}/$$7\mathrm{b}\mathrm{i}\mathrm{v}\mathrm{o}\mathrm{n}\mathrm{e}\mathrm{n}$$\mathrm{D}\mathrm{e}\mathrm{h}\mathrm{a}\epsilon \mathrm{p}\mathrm{e}$$\mathit{9}S,$$\mathrm{M}\mathrm{a}\mathrm{a}\mathrm{e}\mathrm{j}\mathrm{v}\mathrm{e}\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}\mathrm{B}.\mathrm{G}\mathrm{i}\mathrm{b}\mathrm{b}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{Y}.\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{a},\mathrm{S}\mathrm{y}\S_{\mathrm{e}\mathrm{t}\S,\mathrm{I}\mathrm{n}Ext\mathrm{e}mdff_{emo\nu vAlgo\dot{n}thm\epsilon,\mathrm{D}1-}^{\mathrm{i}\mathrm{a}\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}s\mathrm{f}\mathrm{o}\mathrm{r}}}\mathrm{n}\circ$

MACS Series in Discr. Math. and Theor. C 化 mpt. Sci.,,2000.
Vol. 50, AMS,
[111 C. Hidber,
Onfine Association Rule,1999.
In Proc. SIGMO D
An Apriori[I2] A. Inokucht, T. \sim 珂 asb..o, H. Motoda,$3\triangleright 70$$\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}_{\mathrm{I}}$$\mathit{9}\mathit{9},145-156$,
Springer, 2000.
[13] H. Mannila, H. Toivonen. A. I. Verkamo, Discovering
Frequent Episode in Sequences, In Proc. KDD-95,$8=_{\mathrm{D}\mathrm{a}}^{\mathrm{A}1\mathrm{g}\circ\backslash \ovalbox{\tt\small REJECT}^{\mathrm{r}}=^{\mathrm{n}}\mathrm{m}_{D}\circ \mathrm{n}\mathrm{t}\mathrm{S}\mathrm{u}\mathrm{b}\mathrm{s}}(\mathrm{b}^{\mathrm{u}}zooo,\mathrm{t}\ovalbox{\tt\small REJECT}_{\mathrm{L}\mathrm{N}\mathrm{A}1}^{\mathrm{r}\mathrm{o}\mathrm{e}\mathrm{k}\mathrm{o}\mathrm{m}}$43

アルゴリズ A の比較

本節では, 基本型と忘却型のアルゴリズムを実験により比較し, 忘却の有無がアルゴリズムの実際の振る舞いに与える影響を検証する. 本節の実験では, デー
タセット $wsw$ を用いた.
図 9 に, 最小サポートを $\sigma=5(\%)$ に固定して, 基

本型アルゴリズムと, 忘却定数 $\gamma=0\cdot 99$ に対する忘却型アルゴリズムが, 各時刻にそれぞれ計算した候補パ
ターン数を示す.
この結果から, 忘却型のアルゴリズムは, データス
トリームの傾向が変わると, 速やかに過去のパターンを削除し, 代わりに現在のパターンを候補集合に加えることが分かる. これは, 忘却型のアルゴリズムが,過去に出現したパターンの出現頻度を指数的に逓減させるからである.
このように, 忘却型アルゴリズムは, 基本型アルゴ

リズムよりストリームデータの時間変化に柔軟に対応
する. したがって, 忘却の手法は, 異常検出やトレン
ド変化検出などの応用に有効である.

$211\vdash$$215,1995$ .

.

[14] T. Miyahara, Y. Suzuki, T. Shoudai, T. Uchida, K. qhka$\mathrm{i}\mathrm{n}\mathrm{S}_{6\mathrm{I}}\mathrm{n}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{W}\epsilon \mathrm{b}\mathrm{h}\mathrm{a}\S \mathrm{h}\mathrm{i},\mathrm{H}.\mathrm{U}\mathrm{e}\mathrm{d}\mathrm{a},\mathrm{D}\mathrm{i}\mathrm{s}_{\ _{\mathrm{c}\mathrm{u}\mathrm{m}6\mathrm{n}\mathrm{t}\mathrm{s},\mathrm{I}\mathrm{n}\mathit{5}_{1vc.PAKDD-}}^{\mathrm{o}\mathrm{f}\mathrm{R}\epsilon \mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{t}?\mathrm{h}\mathrm{k}\mathrm{e}\epsilon \mathrm{P}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\epsilon}}\mathrm{c}\mathrm{o}\mathrm{v}\mathrm{e}$zooa 341-355, 2002.
$[15]\simeq=arrow^{\mathrm{a}}=\mathrm{M}.\mathrm{J}.\mathrm{Z}\mathrm{a}\mathrm{k}\mathrm{i},\mathrm{M}\mathrm{O}\mathrm{g}\mathrm{i}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{a},$$\mathrm{S}\mathrm{D}\mathrm{w}\mathrm{a}\mathrm{r}\mathrm{k}\mathrm{a}\mathrm{d}\mathrm{a}\mathrm{s}\mathrm{l}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{a}c\mathrm{t}\mathrm{i}\mathrm{v}\epsilon\dot{\mathrm{S}}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}\dot{{\rm Min}}\mathrm{i}\mathrm{n}\mathrm{g},\mathrm{I}\mathrm{n}$$\mathrm{m}\mathrm{c}$16]. ClKM’$gg,$’$251-258$ ,1999.

$\mathrm{M}i\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{a}\mathrm{S}\mathrm{t}\mathrm{o}\mathrm{g}\mathrm{i},\mathrm{S}\mathrm{i}\mathrm{n}\mathrm{g}1\mathrm{e}- \mathrm{P}.\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{A}[\^{\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}\mathrm{s}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{Q}\mathrm{u}\mathrm{e}}mc.\cdot SDM\mathit{2}OOZ\#^{\mathrm{n}}.or\#_{shop}^{\mathrm{a}\mathrm{n}\mathrm{d}}HDM\theta B_{\mathrm{I}}43-48,2002\mathrm{F}^{\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{m}\mathrm{s},1\mathrm{n}}$Software Solution, Inc., XML benchmark,http:, Extensive Markup Language (XML) 10(Sec18]
ond Edition), $WSC$ Recomrnendation, 06 October 2000.
http:$17]\mathrm{S}\infty \mathrm{n}\mathrm{o}\mathrm{s}\mathrm{k}\mathrm{i}$$//\mathrm{W}1[] \mathrm{w}.\mathrm{s}\mathrm{o}\mathrm{s}\mathrm{n}\mathrm{o}\cdot \mathrm{k}\mathrm{l}.\mathrm{e}\mathrm{o}\mathrm{n}/\circ \mathrm{p}\cdot \mathrm{n}*\mathrm{r}\mathrm{e}/\mathrm{x}\mathrm{m}\mathrm{l}\mathrm{b}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{h}/$$\mathrm{W}3\mathrm{C}$$//\mathrm{w}\mathrm{w}.\mathrm{w}3.\circ \mathrm{r}\mathrm{g}/\mathrm{T}\mathrm{R}/\mathrm{R}\mathrm{E}\mathrm{G}-\mathrm{x}\mathrm{n}\mathrm{l}$19] K. Waog, H. Liu, Discovering Structural Association of
Semistructured Data, TKDE, 12(2), 35$-371, 2000.
[20]K. Yamanishi, J. Takeuchi, AUnifying Framework=哨$=rightarrow_{\mathrm{a}}\backslash \mathrm{T}\mathrm{B}_{m\mathrm{c}.SIGKDD}^{\mathrm{e}\mathrm{P}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}\epsilon \mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m}}l\mathit{0}\mathit{0}l\mathrm{N}\mathrm{o}\mathrm{n}-$,.aForest,$1^{21]\mathrm{M}\cdot \mathrm{J}\cdot \mathrm{Z}\mathrm{a}\mathrm{k}1\mathrm{E}\mathrm{f}\mathrm{f}\mathrm{l}\mathrm{c}\mathrm{i}\mathrm{e}\mathrm{n}\mathrm{t}1^{\mathrm{y}}{\rm Min} \mathrm{i}\mathrm{n}}\ln Pm\mathrm{c}\cdot\dot{S}IGKDDl\theta\theta l\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{i}^{\mathrm{F}\mathrm{f}\mathrm{f}}2\Re^{\mathrm{u}_{2}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{n}}|’$