論文

DBSJ Letters Vol. 6, No. 1(forward axes) のみと限定している．これに対して，最近パストライを用いた高速軽量な 方向軸
では先祖軸 (ancestor axes), 兄弟軸 (sibling axes) にも対応したストリーム処理手法が提案されている [4] が，順方向軸のみに限定しXML 文書フィルタリングた手法に比べ規模耐性，処理速度等を犠牲にしている．本論文で提案する手法は，扱う軸は順方向軸のみで，オートマトンを用いて XML データを走査する点では YFilter や XMLTK と同様であるが，XML データに前処理を施すことによって高速化・軽量化を可能とした点で異なる．
御手洗 秀一∗ 石野 明† 竹田 正幸‡ §YFilter は，XFilter [2] のパス照合処理を改良したもので，質問
Shuichi MITARAI Akira ISHINO Masayuki TAKEDA 式毎に非決定性有限オートマトン (NFA) を構築するのではなく，質問式全体の共通接頭辞パスを共通の状態として束ねたもので，XML データに極めて単純な前処理を施すことで，質問数の増 XFilter よりも質問数に関して規模耐性があり，高速に動作する．
大に頑健な XML フィルタリング方式を開発した．その手法は， しかしながら，NFA は同時に複数の状態遷移を処理しなければな
データ配信側で XML データを事前に走査し，根から葉へ向かう らないため，決定性オートマトン (DFA) と比較して照合速度は遅パスに沿ったタグ名の列全体を表すパストライと，バイナリデー い．NFA を等価な DFA に変換すると，一般に状態数が指数的にタを作成する。質問式に現れるパスパターンの照合は，パストラ 増大する．そこで，XMLTK では，XML データ走査中に必要に応イを対象として行う．パストライは XML データに比べ非常に小 じて NFA を部分的に DFA に変換する Lazy-DFA [3] と呼ばれる手さいため，高速に処理を完了することが可能である．パスパター 法を採用している．XMLTK は，質問数に関して規模耐性がありンの照合結果はバイナリ XML データ走査時に参照することがで 高速であるが，一方，DFA の状態数が増大し大量のメモリを必要き，これをテキスト節点を対象としたキーワード照合の結果と結 とするという欠点がある．
本論文で提案する前処理手法は，XML データをパストライと合させることで質問処理は完了する．代表的なストリーム型 XMLプロセッサである XMLTK との比較において，実行速度で 2〜6 バイナリ XML データの対に変換する．パストライは，XML デー倍高速であり，メモリ使用量は 1/6 程度であることが判明した． タ中の根から葉へ向かうパスに沿って現れるタグ名の列全体を表すトライである．また，バイナリ XML データは，XML データ中
This paper proposes a scalable XML filtering basing on prepro- の開始タグと終了タグを各々特殊コードで置き換えたもので，開cessing of XML data. XML data is preprocessed and transformed 始タグを表すコードの直後に，タグ名を表す番号ではなく，対応
into a pair of a path trie and a binary XML data. The path trie するパストライ節点を識別するための番号（以下，パストライ節
is the trie representing the set of strings of tag names along with 点番号）を埋め込んでいる．データ送信サーバは，このパストラ
root-to-leaf paths. Path pattern matching is performed against the イとバイナリ XML データを対として送信する．データ受信側でpath trie. Since the path trie is much smaller than the XML data, は，まず，パストライを対象にパス照合を行い，その結果をパス
a drastic speedup is possible. Query pattern processing is done トライの節点に付加する．これにより，バイナリ XML データの走by combining the keyword occurrences found in scanning of the 査時にはもはやパス照合の必要はなく，バイナリ XML データ中
binary XML data with the information added to path trie node に埋め込まれたパストライ節点番号を頼りにパス照合の結果を参
implied by node IDs embeded in the binary XML data.
照することが可能となる．一般に，パストライは XML データ全
Experimental results show that, the processing time and mem- 体の木に比べて十分小さいため，処理速度は劇的に向上する．まory requirement of our method are, respectively, 1/6–1/2 and 1/6 たパストライは，DataGuide と呼ばれるデータ構造の一種である．
compared with XMLTK, a state-of-the-art streaming XML pro- XML データ処理の効率化のために DataGuide を用いるアイデアはcessor.
新しくないが，本論文のような用い方は，著者らの知る限り，これまで存在していない．

Light-weight Acceleration For Streaming XML
Document Filtering

1. はじめにインターネット上のニュース記事や広告等のメディア，日々観測 2. パストライを用いた高速なフィルタ処理
されるセンサー情報や株価表示器など，膨大な量の情報が絶え間
石野ら [9] では XQuery の部分族をパスプルーニングと DFA をなく生成されている．これらの情報を有効に活用するための技術が 用いて効率的に処理する手法を提案した．その手法は，まず入力強く求められている．SDI (Selective Dissemination of Information) となる XML データを事前に調べてパストライを得る．このパストは，そのようなサービスの一つであり，日々生成される大量の機 ライを用いることで，質問式に含まれるパスパターン中の//や*を械可読文書を購読者が選択的に，かつ，リアルタイムに取得する 展開し，これによって DFA の状態爆発を抑えるというものであっことができるこのような publish/subscribe 型のデータ配送システ た．本論文では，石野らの手法をさらに発展させ，パスパターン
ムは，従来，キーワードや “bag-of-words” に基づくフィルタリン 照合をデータ走査時に実行するのではなく，質問式を得た段階でグによる比較的単純なものであった．
完了させておくことによってより高速なフィルタ処理を実現する
しかし近年，XML (eXtensible Markup Language) の台頭により， ことに成功した．
XPath を用いたより高度なフィルタリングが可能となった．XPath
以下では用語を定義したあと，フィルタ処理に必要な問題を定は，W3C の勧告による，XML 文書の特定の部分 (要素，属性，テ 式化し，本手法のアルゴリズムを紹介する．
キストなど) を指定するための言語で，事実上の標準となっている．
2.1 定義代表的な XML データストリーム処理器である YFilter [5] やΣ を文字の有限集合とし，N をタグ名から成る集合とする．XML
XMLTK [3] は，非常に高速に XPath を処理できるが，扱う軸は順
木とは，N のタグ名を内部節点のラベルとし，Σ 上の文字列を葉∗ 正会員 九州大学情報基盤研究開発センター mitarai@cc.kyushu-u.ac.jp(テキスト節点) のラベルとするようなラベル付き順序木をいう．¶† 正会員 東北大学大学院情報科学研究科システム情報科学専攻

ishino@ecei.tohoku.ac.jp‡ 九州大学大学院システム情報科学研究院情報理学部門

takeda@i.kyushu-u.ac.jp§ 科学技術振興機構 戦略的創造研究推進事業

1¶ 本論文では，“name=value” に対応する属性節点は，“value” をラベルとする葉を唯一の子とし，“@name” というラベルをもつ内部節点として扱う．

日本データベース学会 Letters Vol 6, No.1

論文

DBSJ Letters Vol. 6, No. 1

単純パスパターンとは N のタグ名と特殊な記号 “*” から成る記号列をいい，各々の記号は “/” または “//” で区切られているものとする．ここで，“/” と “//” は，それぞれ，親子関係，先祖-子孫関係に対応する．単純パスパターン π が XML 木のパスにマッチするとは，“*” を任意のタグ名にマッチするワイルドカー
ド，“//” を任意のタグ名列にマッチする可変長ワイルドカードとみなした際に，π がそのパスに沿ったタグ名の列に合致するときをいう．
パスパターンとは単純パスパターン π1 ，π2 の順序対であり，π1 [π2 ] と表す．XML 木の任意の節点 x とその子孫 y（x = y の場合も含む）に対し，パスパターン π1 [π2 ] が位置 (x, y) に出現するとは，π1 ，π2 が，それぞれ，根から x へのパスと x′ から y へのパスにマッチするときをいう．ここで，x′ は，根から y へ向かうパスに沿った x の子節点である．
e = e(w1 , . . . , wm ) を，Σ 上の空でない文字列 w1 , . . . , wm の生起の有無に関する論理式であるとする．Σ 上のテキスト d が論理式 e を充足するとは，d におけるキーワード w1 , . . . , wm の生起に対応した真偽値割り当て (truth assignment) のもとで e が真となるときをいう．
XPattern とは，パスパターン π1 [π2 ] と論理式 e の組をいい，
π1 [π2 : e] と表す．XPattern π1 [π2 : e] が XML 木の節点 x に出現するとは，x の子孫 y が存在して，パスパターン π1 [π2 ] が位置 (x, y) に出現し，かつ，y の子であるテキスト節点の少なくとも一つが e を充足するときをいう．この定義より，パスパターン
π1 [π2 ] は，XPattern π1 [π2 : true] と見なすことができる．
本論文では，以下の問題に取り組む．
定義 1
Given: XML データ T .
Query: XPattern P1 , . . . , Pℓ .
Answer: 各 i = 1, . . . , ℓ に対し，T に対応する XML 木においてPi が生起する節点 x を返せ．
ここで，入力として与えられる XML データ T は，複数の XML文書の系列（XML 木の系列）となっていることを仮定している．

2.2 パストライとバイナリデータ

Input XML file<a><b><c>...</c></b><b><d>...</d>
</b>
<b>
<c>
<d>...</d><b><d>...</d></b>
</c>
</b>
</a>

abbbcdcdbd

Binary XML file

Path trie
1a[1[2[3...]2][2[4...]b3][24c[35[5...][6[7...]]dd6b7d]]]

図 1. XML データと前処理で作成されるパストラ
イ，バイナリ XML データ

Fig.1. Preprocessing of XML data.

本手法では XML データに対して一度だけ前処理を行い，パス T 中の開始タグの個数を表し，|N | はタグ集合の要素数を，|T |トライと，バイナリ XML ファイルを作成する．XML データと前 は XML データのサイズを表す．また，XML データと生成される処理によって作成されるパストライ及びバイナリ XML データとデータサイズの関係を表 1, 2 に示す．このことから，パストライの関係を図 1 に示す．図 1 右上は XML 木を示しており，四角の節は，XML 木に対して十分に小さく，バイナリ XML データに関し点はテキスト節点を表している．また，この XML データから前処ても入力ファイルサイズの 76%と小さくなっていることが分かる．
理を経て生成されるバイナリ XML データとパストライをそれぞれ，左下と右下に示した．パストライの節点の傍にある数は，そ 2.3 パスパターンの照合の節点の ID（パストライ節点番号）である．バイナリ XML デー
本論文では，XML 木に対するパスパターン照合の問題を，パタにおいて，開始タグと終了タグはそれぞれ，特殊記号 “[” と “]” ストライに対するパスパターン照合に置き換える．に置き換えられ，“[” の直後にはタグを表す番号ではなく，根から
図 1 で示した XML データを例にとり，XML 木中，および，パのパスに沿ったラベルの列を表すパストライ節点番号が埋め込ま ストライ中におけるパスパターン P1 = a//b[//d] の生起の様子をれていることに注意されたい．
図 2 に示した．
このことによって，パスパターン照合はパストライを対象としこの例では，パスパターン P1 = a//b[//d] は XML 木中の位置たパターン照合を行うだけで良く，パストライが XML データに (x, y) = (4, 5), (6, 8), (6, 10), (9, 10) で生起している．これらの比べ非常に小さいため，高速に処理を完了することが可能となる． 位置は，図右に示したパストライの節点に付加された情報からこの前処理に要する時間は O(n log |N | + |T |) であり，表 2 に 得ることができる．一方，パストライ中においては，生起位置は示すとおり高速な処理が可能である．ここで，n は XML データ (x, y) = (2, 5), (2, 7), (6, 7), (2, 4) である．そこで，パストライ中2

表 1. DBLP [6] と xmlgen [7] によってランダムに生成された入力 XML データの大きさ

表 2. 前処理で構築されるバイナリ XML データとパストライのサイズ及びその構築時間

Table 1. Characteristics of two input XML data.
XML データ
サイズ (MB)
節点数
タグ数
DBLP
352
8,632,81235
random111
1,666,310
74

Table 2. Sizes of the binary XML data and the path tries.
バイナリ XML データ パストライ CPU 時間
サイズ (MB)
節点数(sec)
DBLP
208138100.41
random8451573.26

日本データベース学会 Letters Vol 6, No.1

論文

DBSJ Letters Vol. 6, No. 1

2 b3c2
3a4 b5d2

16 b74もし e が真ならば，Q[depth − d][q] を真と設定する．depthを 1 デクリメントする．M の状態を初期状態に戻す．

Hit!

18dca22bHit!

334c95• c がそれ以外のバイトコードであるとき．M を文字 c で状態遷移させる．もし遷移先の状態が出力をもつならば生起したキーワードに対応して Occ[depth][1 . . . m] を更新する．

b10d675d<P1, 2>

d<P1, 1>6b7d<P1, 1>, <P1, 3>

図 2. パストライ・XML 木の関係と，パスパターン P1 = a//b[//d] の照合結果

Fig.2. Path-pattern matching using path trie.の生起位置 (x, y) の節点 y にパスパターンの番号と節点 x, y の深さの差の情報を付加する．すると，XML 木中の生起位置は，パストライに付加された情報から得ることができる．たとえば，XML木中の位置 (6, 8) における P1 の生起は，パストライの節点 5 のもつ出力 ⟨P1 , 2⟩ から得ることができる．すなわち，バイナリ XML
データ中において，XML 木の節点 y = 8 に対応する箇所にはパストライ節点番号 5 が埋め込まれており，パストライの節点 5 に付加された情報 ⟨P1 , 2⟩ によって，y から 2 つ上の先祖である節点x = 6 が得られる．
次に，パストライに対するパスパターン照合の手法について述べる．質問式に含まれる各パスパターンに対し，パストライ中の出現位置 (x, y) をすべて求めなければならない．このために，竹田ら [8] が XML 木に対するパスパターン照合に用いた方法を採用する．
本手法を用いることで，バイナリ XML データ走査時のパスパターン照合処理は不要となり，XML データ走査時にパスパターンの照合を行っている YFilter や XMLTK と比べ，処理時間を大幅に短縮することができる．

2.4 バイナリ XML データ走査アルゴリズム

3. 実装実験実験に用いた計算機環境は，RedHat Linux Advanced Server 2.1,CPU 2.4GHz Intel Pentium4, 2.0GB RAM で，入力に用いた XML
データは，xmlgen [7] によって生成されたランダムデータでサイズは111MB である．質問式は，XMLTK が任意の位置ステップ (locationstep) での述語の使用を許していないため，単純パスパターンを用いた．パスは，YFilter によって提供されている pathgenerator [1] によってランダムに生成され，//，*の生起確率はそれぞれ (1%, 1%)，(10%, 10%) としている．

3.1 パスパターン照合に要する時間


Processing time (msec)

1Hit!



Path patterns
Simple path patterns










Number of queries



図 3. パストライとパスパターン照合に要する時間

Fig.3. Times for path-pattern matching against path trie.
図 3 は，質問数を変化させたときのパスパターン照合に要する時間を測定したものである．NFA の構築に要する時間も含んでいる．この結果より，質問数が多くなっても実際にバイナリ XML
データを走査する時間 (表 4) と比較して，ほとんど無視できる時間であることが分かる．これは，パストライのサイズが入力 XML
木の節点数 1,666,310 個に対して 515 個と小さい（表 2 参照）ことと，ビット並列化技術による NFA の構築・照合がきわめて高速に動作することによる．

バイナリ XML データを走査してキーワード照合を行い，その結果とパスパターン照合の結果を結合して質問処理を行うアルゴ
リズムの概略を以下に示す．
与えられた XPattern P1 , . . . , Pℓ の論理式 e 中に含まれるキー
3.2 XMLTK および YFilter との性能比較ワードからなる集合を W = w1 , . . . , wm とする．W から Aho表 3 は，質問数が 10,000, 100,000 のときのメモリ使用量 (//, *Corasick(AC) 機械 M を構築する．バイナリ XML ファイル先頭かの生起確率は(1%, 1%), (10%, 10%) の 2 通り) 表している．メモらの位置を表す変数 oﬀset と，入力を XML 木として見たときのリ使用量は，論理空間上にどれだけメモリを確保したのかではな
節点の深さを表す変数 depth を用意する．ブール値を格納する 2次元配列 Occ と Q を用意する．配列 Occ は，現在巡回している く，プログラム実行中に実際に物理メモリにアクセスしたサイズ
深さ d の節点の子であるテキスト節点にキーワード wi が生起す の最大値を測定している．
質問数が 100,000 のとき，YFilter は本計算機環境では，メモリるときに Occ[d][i] の値が真となるというものであり，配列 Q は，枯渇により動作不能となった．質問数が10,000 のとき (//, *の生
現在巡回している深さ d の節点に XPattern Pq が出現するときに起確率は10%)を見ると，本手法が4,925KBであるのに対して，Q[d][q] の値が真となる．本アルゴリズムは，バイナリ XML ファ
イルを 1 バイトずつ走査し，読み込んだバイト c に対して以下を実行する．
表 3. メモリ使用量の比較• c が開始タグを表す特殊記号 “[” であるとき．パストライ節
点番号 v を読み込み，(v, oﬀset) をスタック S にプッシュする．depth を 1 インクリメントする．Occ[depth][1 . . . m] とQ[depth][1 . . . l] を偽に初期化する．M の状態を初期状態に設定する．
• c が終了タグを表す特殊記号 “]” であるとき．スタック S より (v, oﬀset) をポップする．もしパストライのノード v が出力をもっていたら，それぞれの ⟨q, d⟩ に対して，XPattern Pqの論理式 e を，Occ[depth][1 . . . m] の値に基づいて計算し，

3

Table 3. Memory usage comparison.
質問数

メモリ使用量 (KB)
本手法YFilter
XMLTK
単純パスパターン10,0003,320 1,169,975
30,2881%
100,000 18,632
285,328
単純パスパターン10,0004,952 1,494,845
34,412100,000 28,543
318,560
10%※空欄はメモリ枯渇のため，実施不能であったことを示す．

日本データベース学会 Letters Vol 6, No.1

論文

DBSJ Letters Vol. 6, No. 1

XMLTK 34,412KB, YFilter 1,494,845KB と優に 6 倍以上であることが分かる．
次に，表 4 は，単純パスパターンを 1〜100,000 個ランダムに与えたときの実行時間を測定したものである．この結果より，本手法が YFilter，XMLTK と比較して圧倒的に高速であることが分かる．また，質問数が 100,000 のときに，本手法と XMLTK の処理時間が大幅に遅くなっているのは，マッチする節点数が多くな
りすぎて，出力依存の要因が全体の処理時間の大半を占めるようになっているためで，マッチする節点数の増加率と実行時間の増加率はほぼ一致することを確認している．
表 4. 実行時間の比較

Table 4. Execution time comparison.
質問数

経過時間 (sec)
本手法 YFilter XMLTK
10.57
39.24
2.27
100.5742.54
2.57
1000.57
45.22
3.09
0.67
61.30
4.14
1, 00010, 000
1.85 155.30
11.83
100, 000 142.04
270.81※空欄はメモリ枯渇のため，実施不能であったことを示す．

3.3 SIX による高速化検証

うに，SDI サービスにおいて大量のクライアントが質問式をサーバに登録するような大規模 SDI システムの構築も可能である．また，質問式が少ない際は，SIX によりさらにフィルタリング性能を向上させることができる．
また，配信するべきクライアント数が急増し，単一計算機で処理をまかなえなくなるような場合でも，同じ XML データを複数の計算機に重複して担当させることで対応可能である．この場合，バイナリ XML データは配信元となるマスターサーバーでただ一度作成するだけでよく，前処理の時間は問題にならない．
今後の課題としては，(1) 単一計算機環境におけるフィルタ処理をさらに高速化する手法を検討することと，(2) 本論文の成果をもとに，前処理を施さない XML データをそのまま扱うタイプのフィルタリング手法を開発すること，(3) 分岐パターン (twig pattern) や親軸・先祖軸などへの対応が挙げられる．

［文献］[1] : Filtering and Transformation for High-Volume XML Message
Brokering, http://yfilter.cs.berkeley.edu/code release.htm.
[2] Altinel, M. and Franklin, M.: Efficient filtering of XML documents for selective dissemination, VLDB’00, pp. 53–64 (2000).
[3] Avila-Campillo, I., Green, T. J., Gupta, A., Onizuka, M., Raven,
D. and Suciu, D.: XMLTK: An XML Toolkit for Scalable XMLProcessing, PLANX’02 (2002).

[4] Barton, C., Charles, P., Goyal, D., Raghavachari, M., Josifovski,
本手法をさらに高速化させるための技法として，Stream IndeX
V. and Fontoura, M.: Streaming XPath processing with forward(SIX) [3] がある．SIX とは，開始タグとそれに対応した終了タグ
and backward axes, ICDE, pp. 455–466 (2003).の位置情報の組から成る集合であり，本手法もこのデータ構造を[5] Diao, Y., Altinel, H., Franklin, M. J., Zhang, H. and Fischer,用いることで，関係のない部分木を読み飛ばすことが可能である．
P. M.: Path Sharing and Predicate Evaluation for HighPerfor表 5 が表 4 で示した実験に SIX を追加したときの実行時間であmance, ACMTOD (2003).
る．この結果より，質問数が少ないときには 1.6〜7.2 倍高速化されており，たとえ質問数が多くほとんど読み飛ばしができない場 [6] Ley, M.: DBLP Computer Science Bibliography, http://dblp.unitrier.de/.
合であっても性能劣化がないことが分かる．また，表 4 との比較
より，同じ入力データを用いているにも関わらず XMLTK に比べ， [7] Schmidt, A., Waas, F., Kersten, M. L., Carey, M. J., Manolescu, I.
SIX による効果が高いことが分かる．これは，XMLTK が//や*にand Busse, R.: XMark: A benchmark for XML data management,相当する状態に遷移した後，どのようなタグが現れてもその状態
VLDB’02, pp. 974–985 (2002).
から抜けない限り読み飛ばせるか否かの判断がつかないのに対し，[8] 竹田正幸，石野 明，辻 寿嗣，宮本 哲：ストリーム指向
本手法ではそれらをパストライにより予め展開しており，任意のの高速 XML データ処理技法について，DBWeb2003 (2003).
タグで判別可能であるためと考える．
[9] 石野 明，竹田正幸：パスプルーニングによる決定性有限オー
トマトンを用いた XQuery 処理の提案，日本データベース学
表 5. SIX による高速化の比較
会 Letters，Vol. 4, No. 4 (2006).
Table 5. Comparison of speedups with SIX.
質問数1101001, 00010, 000
100, 000

経過時間 (sec)
本手法 XMLTK
0.00
0.14
0.07
1.53
0.18
2.49
0.39
4.37
1.81
12.25
139.62275.74

御手洗 秀一Shuichi MITARAI

九州大学情報基盤研究開発センター特任助教．2002 九州大学大学
院システム情報科学府情報理学専攻修士課程修了．修士（理学）．
半構造データベースに関する研究と開発に従事．日本データベース学会会員．

石野 明

Akira ISHINO

4. まとめと今後の課題

東北大学大学院情報科学研究科助教．1999 北海道大学大学院工学研究科電子情報工学専攻博士課程修了．博士（工学）．半構造デー
タベース，自律型ロボットに関する研究と開発に従事．日本デー
タベース学会会員．

本論文では，パストライ上のパス照合処理と AC 法を用いたキーワード照合処理を結合したストリーム型のフィルタリング技法を提案した．XPath の複数の質問式を同時に処理する手法について述べ，節 3 で示したとおり，一連の実験によって，パストライがフィルタ処理の高速化に寄与することを示し，本手法が YFilter やXMLTK と比較して高い性能を有することが判明した．
また，本手法が効率的に大量の質問式を同時に処理することができることを実験により確認した．これにより，節 1 で述べたよ九州大学大学院システム情報科学研究院情報理学部門教授．科学技術振興機構戦略的創造研究推進事業．1989 九州大学大学院総合理工学研究科情報システム学専攻修士課程修了．博士（工学）．系
列データの高速パターン照合処理，大規模系列データからの知識発見に関する研究と開発に従事．情報処理学会創立 40 周年記念論文賞，山下記念研究賞などを受賞．

4

竹田 正幸

Masayuki TAKEDA

日本データベース学会 Letters Vol 6, No.1