論文 / 著書情報
Article / Book Information
論題(和文)

検索キーワード を含む最小XML 部分文書抽出のための索引手法

Title(English)

Indexing Methods to Extract MCTs from an XML Document Containing
Search Keywords

著者(和文)

三木健士, 横田治夫

Authors(English)

Takeshi MIKI, Haruo YOKOTA

掲載誌(和文)DEWS2007論文集

Citation(English)

Proceedings of DEWS2007

Vol, no, pages

Vol. , No. , pp. C1-4

発行日 / Pub. date2007, 3

URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2007 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2007 C1-4

検索キーワード を含む最小 XML 部分文書抽出のための索引手法
健士†

三木

横田

治夫††,†† 東京工業大学 大学院 情報理工学研究科 計算工学専攻 〒 1528552 東京都目黒区大岡山 2121†† 東京工業大学 学術国際情報センター 〒 1528550 東京都目黒区大岡山 2121
E-mail: †takeshi@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
あらまし近年，XML が普及する中、XML 文書の中から与えられた検索キーワード を全て含む部分文書を高速に抽出する処理が注目されている．我々は 、テキスト文書検索用索引に使われるスーパーインポーズド コード の手法を，
階層構造を持つ XML 文書に対して適用する手法を提案してきた．本論文では，XML 文書用のスーパーインポーズド
コード 手法とキーワード の B+木を組み合わせることによって，検索キーワード を全て含む最小 XML 部分文書を高速に取得する方法を提案する。XML 木の葉ノード 毎に生成したスーパーインポーズド コード を，XML 木の階層構造に従ってさらにスーパーインポーズして算出したビット列を，キーワードに対して構成した B+木の葉ノードに格納することで、フォールスド ロップの無い最小部分木抽出が可能となる．提案手法の有効性を示すために実験による評価を
行う．
キーワード

XML

、キーワード、索引、スーパーインポーズド コード、シグニチャ

Indexing Methods to Extract MCTs from an XML Document
Containing Search Keywords
Takeshi MIKI†

and Haruo YOKOTA††,†† Department of Computer Science, Graduate School of Information Science and Engineering,Tokyo Institute of Technology

Ookayama 2121, Meguro-ku, Tokyo, 1528552 Japan†† Global Scientic Information and Computing Center, Tokyo Institute of Technology
Ookayama 2121, Meguro-ku, Tokyo, 1528550 Japan
E-mail:Abstract†takeshi@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp

The functions for extracting XML subdocuments containing all search keywords from an XML docu-

ment are paid to attention recently. We have proposed methods applying superimposed code techniques to XML
documents to derive the lowest common ancestor nodes for the keywords.

In this paper, we enhance methods

to extract the minimum connecting trees of the XML subdocuments containing all search keywords without false
drops.

The proposed methods combine the superimposed code techniques with a B+tree structure containing

keywords. We estimate the processing costs of the proposed methods based on structural models. We also evaluate
them using Xmark benchmark.

The estimation and experimental results indicate that the proposed methods areffective comparing with an ordinary method.

e

Key words

XML , keyword ,index ,superimposed code, signature

1.

はじめに

XML

文書の中から必要な部分文書を XML の構造を考慮して抽出する要求が高まっている．そのひとつとして，与えられた
複数のキーワード を全て含む部分文書を効率よく抽出する方法

含む部分文書を検索する場合，その検索結果として一人の台詞から成る部分文書や，複数人の台詞から成る部分文書などが考
えられる．
XML

文書はラベル付木としてモデル化されることから，上記のような検索は，キーワード を含む葉の最低共通親 (Lowestが研究されている [1]．例えば，シェークスピアの作品を XML

Common Ancestors:化したものの中から，母，王，兄弟というキーワード を台詞にことができる．ただし ，実際には，最小最低共通親 (Smallest

LCAs) [2, 3]を 探す問題に 置き換え る 1 LCA) [3]や，最低最小接続木（ Lowest Minimum Connecting

Trees: Lowest MCTs[r,0] root
[r,0]
root
[c[c1,1],1](shakespeare)(shakespeare)[s[s1,1.1],1.1](play)(play)[p,1.1.1] (title)[p 1,1.1.1] (title)[a1,1.1.1.1] Hamlet[a1,1.1.1.1] Hamlet[p2,1.1.2](act1)[p ,1.1.2](act1)[a2,1.1.2.1]King,Mother[a2,1.1.2.1] King,Mother[p3,1.1.3](act2)[p ,1.1.3](act2)[a3,1.1.3.1] Brother[a3,1.1.3.1] Brother[s2,1.2](play)[s ,1.2](play) [p4,1.2.1](title)[p ,1.2.1](title) [a4,1.2.1.1] King,Lear[p5,1.2.2](act1)[a4,1.2.1.1] King,Lear[a5,1.2.2.1] Mother,Duke[p ,1.2.2](act1)[p6,1.2.3](act3)[a5,1.2.2.1] Mother,Duke[a6,1.2.3.1] King）を探す必要がある．最低最小接続木と1

1

は，Smallest LCA を根とし ，検索キーワード を含んだ葉ノー

1ド を持つ木である．[1] では，XML 木の Lowest MCT を抽出するために索引の付いた XML 木に対して入れ子ループを用い2る方法やスタックを用いる方法等について提案を行っている．

3

我々は，複数キーワード に対して MCT を効率良く求めるために，まず MCT の親である LCA を効率よく検索する手法と

2

4

して，スーパーインポーズド コード を利用した手法を提案してきた [4]． 一般に，スーパーインポーズド コード は，文書ファ

5

イル毎にキーワード のシグニチャファイルを用意することで，[p6,1.2.3](act3)

文書ファイルに対するキーワード 検索を高速に行うために使[a6,1.2.3.1] King

われる手法である [5, 6] が，これを XML 木 の LCA 検索に適図 1 例で使用する XML 文書ラベル付用する．XML 木の葉毎に割り当てた bit 列を階層構造でスーパーインポーズすることで，複数キーワード が全て含まれるLCAを判定することができる．さらに，木のノードに Dewey

Order [7]のラベルを付け，キーワード に対応する葉ノード の

Dewey Orderのラベル間の共通部分検出で共通親を探す方法である KBDL 手法，その手法とスーパーインポーズドコードを組み合わせた手法である KBSI 手法、スーパーインポーズド コー
ドに Bit Index で索引付けして効率を高めた方法である SIBI 手法を提案してきた．しかし，スーパーインポーズド コード を使用した手法では，フォールスド ロップを考慮していなかった．
また，ノード ラベルを有効利用して Lowest MCT を求める方
法を明らかにしていなかった．
本稿では，まず KBSI の効率の良いフォールスド ロップの解決方法を提案する．次に，複数のキーワード に対して MCT を高速に得る手法として，KBDL を用いて LCA を抽出した後，ノード ラベルを有効利用し Lowest MCT を抽出する KBDLM
手法と，フォールスド ロップを解決し た KBSI を用いて LCA

合わせキーワード 間の類似度を計算する枠組を提供しているのに過ぎず，検索対象をあらかじめシステム設計者が 決めている
点で汎用性に欠ける．汎用性を持たせるために，XML 部分文章の統計量を利用し検索対象である部分文章の絞り込みを行なう方法も提案されている [11]．これらの研究は，基本的に処理コスト削減のために検索対象の部分文書となりえないものを除去してから検索するフィルタリングが中心となっている．
また ，XML 文書の索引に 関し ては ，XPath [12] のよ うな
XMLの問合わせ言語を前提とした索引の研究が多数なされている [1315]．しかし，MCT の検索の場合にはそのまま適用することは難しい．
一方，文献 [1] では，MCT を求めているのではなく，MCTの表記法を変えた GDMCT を用い，利用者に与える必要最小限の情報としてや Lowest GDMCT を求めている．
3.

基本事項

を抽出した後，Lowest MCT を抽出する KBSIM 手法を提案する．さらに，既存手法である SA(Stack Algorithm) [1] と提案
手法の検索コストの見積もりと実験による比較を行う．
以下では，まず 2 節で本研究の関連する研究を紹介する．3
節は本稿で使用する XML 部分木の表記法やそれに関する用語の説明をし ，そして 4 節ではこれまで提案してきた LCA を求める手法を紹介する．5 節で，XML 木から XML 部分木を効率よく抽出するための索引手法の提案をし ，6 節では提案手法，
SAのコストの見積もりを行う．7 節では，提案手法の有効性を調べるために実験を行い，最後に 8 節では結論と今後の課題を
述べる．
2.

関連研究

部分文書検索としては，検索要求においてそれに類似した文書の一部分だけを検索するというパッセージ検索がある [8]．これを XML に適用し ，XML 文書検索で文書構造と文書の内容に基づく順位付けをし，あらかじめ検索対象を絞る手法が提案されている [9]．XIRQL [10] も同様に順位付けをし，検索対象

本節では，文献 [1] で用いられている XML 部分木の表記法を紹介する．
3. 1

Smallest LCA:Smallest Lowest Common Ancester

ラベル付木 T のノード v , . . . , vm の Smallest LCA は，次を1満たす．
（ 1 ） ノード v , . . . , vm の最低共通親 (LCA) である．
1（ 2 ） v , . . . , vm のすべて LCA の中で，互いに親子もしくは1

祖先子孫関係にない．
3. 2

MCT:Minimum Connecting Tree

ラベル付木 T のノード v , . . . , vm の最小接続木 (MCT) は ，
1

v1 , . . . , vm を接続する T の最小サイズの部分木 TM である．木
TM の根は，ノード v1 , . . . , vm の LCA である．

例えば，Dewey Order ラベルを付した XML 文書 (図 1) において，検索キーワード (King,Mother) の MCT は (1-6) となる．
c1

→

s1

→

p2

→

a2

&

s2

→

p4

→

a4

(1)

を絞る．この二つの研究の違いは順位付けの計算モデルの違いにある．しかし ，これらの研究は，単に XML 部分文書と問い
 2 

s2

c1

→

p5

→

a5

&

p4

→

a4

→

s2 →

&

s1

p2

GDMCT:Grouped Distance Minimum Connecting
Tree

(2)

木 T の Grouped DMCT は，ノード のリストと数字でラベル

→

p5

→

3. 4

→

付けされたラベル木である．DMCT:D と GDMCT:G とし ， f
a5

を D のノード，辺から G のノード，辺へのマッピングとする．
a2(3)

f は，次を満たす．

（ 1 ） nD は D のノード，nG は G のノード， f (nD ) = nG でa2(4)あるならば，nG のラベルは，nD の ID を含む．
（ 2 ） eD は D の辺，eG は G の辺， f (eD ) = eG であるならば，

c1

→

s1

→

p2

→

a2

&

s2

→

p6

→

a6

eD と eG のラベルは同じ数である．

例えば，GDMCT(13)，(14)，(15) は，DMCT(7,9,11)，(8,12)，
(5)
(11)

s2

3. 3

→

p5

→

a5

&

p6

→

a6

を表す．
c1

s2

,a ]

ラベル付木 T のノード v , . . . , vm を考える．ノード v , . . . , vm

2

[ a2

,a ,a ]

→

1

&

5

4

[ a4

,a ]

(14)

6

a2

ド ラベル，最小辺ラベルである．
（ 1 ） TD は，ノード v , . . . , vm を含む．
1

3. 5

（ 2 ） TD は，vi , v j ∈ v , . . . , vm であるノード の組 (vi , v j ) の1

1

1の距離とする．

(15)

Lowest GDMCTs:Lowest Grouped Distance Minimum Connecting Trees, . . . , uk を含む．

（ 3 ） 辺のラベルは，ノード n ∈ v , . . . , vm と n0 ∈ u , . . . , uk

木 T の Lowest GDMCTs は，T からノード ID のリストでラベル付けされたノード と数字でラベル付けされたラベル木の集合（ n, G ）である．検索キーワード k , k , . . . , km において，タプ
1

ここで ，例を 使って 説明をする．MCT(1-6) の DMCT は ，(7-12)(13)6[ a5 ]

2の MCT の Distance MCT:TD = d(TM ) は，次のような最小ノー

LCA:u1

[ a2

3

&

(6)

DMCT:Distance Minimum Connecting Tree
1

3

→

である．

2

ル（ n, G ）の集合は以下を満足する．
（ 1 ） n は，k , k , . . . , km の LCA である．
1

c1

3

→

a2

（ 3 ） 求める集合のすべての LCA3 n, n0 において， n が n'

3

&

a4

2

（ 2 ） G は，n を根とした GDMCT である．
(7)の祖先ではない．
例えば ，検索キーワード (King,Mother) の Lowest GDMCTs

s2

2

→

を以下のようである．

a5

2

&

a4

s2

(8)

2

→

[ a5 ]

2

&
c1

3

→

a5

[ a4

,a ]

(16)

6

a2

(17)

3

&

a2

(9)

4.
a2

LCA 抽出のための索引手法

ここで本提案の前提として，[4] で提案した LCA を効率よく(10)抽出するための索引手法を紹介する．
c1

3

→

4. 1

a2

KBDL: Keyword B+tree with Dewey order Label

KBDL

は，ノードラベル間の比較を行い単純に LCA を抽出す

3

&

a6

(11)

るための索引手法である．これは，XML 木のノードに Dewey
Order

s2

2

→

a5

問い合わせ時は，m 個の検索キーワード k , k , .., km に対し ，12&のラベルを付けてキーワードが出現するノード ラベルをキーワード B+tree の索引に格納する．

a6

(12)

B

2

+tree によりそれぞれのキーワード ノード KN , KN , ..., KNm
12を得る．検索キーワード ki と k j : 1 <= i, j <= m を含む XML 木のノードの共通の親は，KNi と KN j の Dewey Order のラベルを比 3 

· · · Lear· · ·· · · Hamlet· · ·· · · King· · ·· · · King· · ·· · · Duke· · ·

問い合わせ

問い合わせ

le-A

le-B

キーワード

シグニチャ

· · · mother· · ·King, brother

1100010

actual drop

actual drop

· · · brother· · ·· · · brother· · ·King, mother

0100110no match

actual drop

Lear, King

1100011

actual drop

false drop

図2

図3

le-A

le-B

図 8 問合わせとド ロップの例

Lear

1000001

キーワード

シグニチャ

Hamlet0100001

Lear

1000001King

0100010King

0100010Duke

0101000

Duke

0101000

mother

0100100

brother

1100000

brother

1100000

論理和

1101011

図 4 ワード シグニチャ

図5

le-A

のシグニチャ

Q ∧ Si = Q(18)

このような候補はド ロップと呼ばれる．ワード シグニチャの組
合わせにより，ド ロップの中には，実際には全てのキーワードが含まれないものもある．そのようなド ロップをフォールスド
ロップと呼ぶ．これに対して，実際に全てのキーワード を含むものをアクチュアルド ロップと呼ぶ．ド ロップ中からフォール

キーワード

シグニチャ

Hamlet0100001King

0100010mother

0100100

brother

1100000

論理和

1100111

図6

le-B

スド ロップを見分ける処理は，フォールスド ロップリゾリュー
ファイル名 シグニチャ
le-A

1101011

le-B

1100111

図 7 シグニチャファイル

のシグニチャ

ションと呼ばれる．
図 7 のシグニチャファイルに対して，いくつかのキーワードの組みに対する検索結果を図 8 に示す．
4. 3

SIXT: SuperImposed for XML Tree

SIXT

は，XML 木のノードにスーパーインポーズド コード を割り当てて，ノード シグニチャファイルを生成した索引手法である．XML 木の葉ノード に含まれるそれぞれのキーワード に較することで得ることができる．したがって，KN , KN , ..., KNn
1

2の中のキーワード の組みのラベルを順番に比較していくことで，すべてのキーワードを含む共通の親ノードを得ることができる．
4. 2

スーパーインポーズド コード

SIXTと KBSI の説明の前準備として，文書検索に利用される

スーパーインポーズド コード を用いたシグニチャファイルによる索引手法の概要を述べる．
4. 2. 1

シグニチャファイルの構成方法対応し たワード シグニチャの論理和演算を適用することで葉ノード のスーパーインポーズド コード を生成し ，XML 木の階層構造に従って論理和演算を適用することで上位ノード のスー
パーインポーズド コード を生成する．これは，詳しくは次によ
うにして求める．まず，XML 文書のキーワード 集合を K とす
る．葉ノード KNi に出現するキーワード k j ∈ K(1 <= j 5 |KNi |)とする．葉ノード のスーパーインポーズドコード Si は，以下の式で求める．

まず，シグニチャファイルを用いた索引では，全文書ファイ
Si = H (k1 ) ∧ H (k2 ) ∧ . . . ∧ H (k|KNi | )ルに出現するキーワード を抽出し，それぞれのキーワードに異る bit 列を割り当てる．これをワード シグニチャという．例として，二つのファイル（ 図 2，3 ）に出現するキーワード のワー
ド シグニチャを示す（ 図 4 ）．
次に，対象となる文書ファイル中に含まれるキーワード の
ワード シグニチャの論理和を取ることでその文書ファイルに対(19)

次に，上位ノード MNi のスーパーインポーズド コード si は，
MNi の子ノード MN(i−1)1 , MN(i−1)2 , . . . , MN(i−1)m のシグニチャ

を s i− , s i− , . . . , s i− m とし，以下の式で求める．
(

1)1

(

1)2

(

1)

si = s(i−1)1 ∧ s(i−1)2 ∧ . . . ∧ s(i−1)m(20)

するスーパーインポーズドコードを作成する (図 5,6)．このスーパーインポーズド コード を対応づけた表 (図 7) がシグニチャ

検索の際，文書ファイルの時と同様にまず問い合わせシグニ

ファイルである．

チャ(Q) を求め，そのシグニチャとノード シグニチャファイル

4. 2. 2

問い合わせ方法

問い合わせが与えられると，その問い合わせに含まれるキー
ワード の集合から問い合わせシグニチャと呼ばれる bit 列 (Q)のノード シグニチャ(NSi ) が以下の式を満たすか調べる．
Q ∧ NSi = Q(21)を作成する．問い合わせシグニチャは，問い合わせ中の各キー

その式が成り立つノード はその問い合わせキーワード を含む

ワード のワード シグニチャの論理和を取ることで生成できる．

ノード を子ノード として含む．つまり，すべての検索キーワー

次に，シグニチャファイル中の各ファイル (Fi ) に対応するシグ

ド を含む部分木の親を得ることができる． ただし，フォールス

ニチャ(Si ) との論理積を取り，その結果が問い合わせシグニチャ

ド ロップ リゾ リューションを行っていないので，求めた LCA（ Q ）と等しければ，つまり以下の式を満たせば，そのファイル

は，フォールスド ロップを含む可能性がある．

(Fi )は検索結果候補となる．

 4 

B

4. 4

KBSI: Keyword B+tree with SuperImposedcode

KBSIは，スーパーインポーズドコードとキーワードに対するgetLCAs(k1,…,km){
Q=H(k1) …H(km)For i=0,…,m do
NSi=getNodeSigniture(ki)+木を組み合わせた索引手法である．これは，XML 木のノー//

ノード に Dewey Order のラベルをつけ，キーワード に対する
B

+木に上記のスーパーインポーズド コード と格納することで，//L

リューションを行っていないので，求めた LCA は，フォール題

上記の手法の課題は，まず，すべての手法に関してあくまでLCA

getLCA_FolseDropLess (L1,…,Lm){
N.addAll(L1)
For i=1,…,|L1| do{
For t=2,…,m do{
For s=1,…,|Lt|do{if(L1(i)==Lt(s)){
break}if(t==|Li|){
N.remove (L1(i))
return N}を取得する手法であり，Lowest GDMCT を求めていな

い．次に，SIXT，KBSI 手法で得られる LCA は，フォールスド
ロップ リゾ リューションを行っていないのでフォールスド ロッ
プを含む可能性がある．これは，検索キーワード k . . . . , km を
1

含む L ∈ lca , . . . , lcan において，kt を含まず ki , . . . , ki j を含む
1

1

ような lcai ∈ L が存在する場合，そのノード lcai において次の式を満たす場合にフォールスド ロップが発生する．
kt ∧ (ki1 ∧ . . . ∧ ki j ) = ki

図 9 フォールスド ロップのない LCA の取得(22)

つまり，含まないキーワード のワード シグニチャが 他のキー
ワード のワード シグニチャの論理和によって算出されたシグニ
チャに含まれてしまうことが原因である．

"#%$'&(For i=0,…,|NS| doif(Q NS(i)=Q){
L.add(NS(i))}
return L}

スド ロップを含む可能性がある．
課

i

getResultSI(Q,NS){
L=nullスキャンのコストを減らす．ただし，フォールスド ロップリゾ

4. 5 B+  k    !

Li=getResultSI(Q,NSi)
return getLCA_FalseDropLess(L1,…,Lm)}

ド にスーパーインポーズド コード を付す．さらに，XML の各

i を 1 から m まで上記の処理を繰り返し，ノード ラベル集合
L1 , . . . , Lm を求める． L1 , . . . , Lm に入るノード ラベルを持つノード はそれぞれ必ず k , . . . , km のキーワード を含む．それぞれの
1

5.

提案手法

ノード ラベル集合に共通して現れるラベルを抽出した集合が N

本稿では，まず KBSI の課題であるフォールスドロップを解決

である．
フォールスド ロップリゾリューションのアルゴ リズムを，図方法を説明をする．続いて，KBDL 及びフォールスド ロップを解決した KBSI を用いて複数のキーワード に対して XML 木のLowest GDMCTs
KBSIM

5. 1

を効率よく検索する手法として，KBDLM，手法を提案する．

プを含む可能性がある．そこで，以下ではフォールスド ロップ

5. 2

Lowest GDMCT を求める手法

ここでは，Lowest GDMCT を効率よく求める手法として，と KBSIM の提案を行う．

それぞれの LCA の抽出方法は，KBDL とフォールスド ロップを解決した KBSI を利用する．Lowest GDMCT の根は，抽出した LCA のノード ラベル集合 L 3 l , . . . , ln において，ノード ラ
1

リゾリューションの説明をする．
は，任意のキーワード ki のキーワード ノード KNi に

ノードシグニチャKSi とノード ラベル NLi の組が格納されていることから，ki を含んでいることを保障されている．したがって，ノードシグニチャKSi をスキャンする際，ki 以外のキーワー
ド のフォールスド ロップが発生する可能性はあるが，キーワー
ド ki に対してのフォールスド ロップは起こらない．
この性質を利用して次のような方法で，フォールスド ロップ
リゾリューションを行った LCA 集合 N を得る．検索の際，検索キーワード k , . . . , km ごとのキーワード ノード に格納されて1いるノードシグニチャ集合 NS , . . . , NSm を抽出する．検索キー
1

ワードから生成した問い合わせシグニチャを Q とし，検索キー
ワード ki ∈ k , . . . , km で得られたノード シグニチャ集合 NSi の1

各要素のシグニチャsi j において，以下の式を満たす場合に対応するノード ラベル li j を Li に加える．
Q ∧ si j = Q(0 5 j 5 |NSi |)

に示す．

KBDLM

フォールスド ロップを解決した KBSI

小節 4.4 で述べた KBSI で求めた LCA は，フォールスド ロッ

KBSI

9

(23)

ベル比較により求めた Smallest LCA である．続いて，Lowest
GDMCTの葉ノード は ，検索キーワード k , . . . , km に 対する
1

キーワード ノード ラベル集合 KL , . . . , KLm の各要素ノード ラベ
1

ルと根のノード ラベル比較を行うことで求めるキーワード ノー
ド である．また，辺ラベルは，親と葉のノード ラベル長比較により求める．
求めた LCA から Lowest GDMCTs(n, G) の抽出するアルゴ
リズムを，図 10 に示す．
6.

コスト 見積り

ここでは，検索コスト比較として，既存手法 SA と提案手法
KBDLM，KBSIM の最悪の場合を見積り，比較を行う．

見積り使う XML 文書の XML 木を図 11 に表す．このときの見積りにおけるパラメタとして，以下を考える．

•

m:問い合わせキーワード 数•

K:全キーワード 種類数 5 

表1 実験環境

getLowetGDMCT(l1,…,ln, KL1,…,KLm ){L:L
G:G GDMCT
L=getMinimumLCA (l1,…,ln, KL1,…,KLm )For i=0,…,|L|
G=getG(l1,…,ln, KL1,…,KLm, L(i))
Return (L,G):Lowest GDMCT}
getMimimumLCA( l1,…,ln, KL1,…,KLm ){L=null //L
For i=0,…,n do
For t=0,…,n do
If(i!=t){
If(lt.substring(li)){ 

//lt

substringli

OSLinux version 2.6.9

小

1-10

database

PostgreSQL 8.1.3

中11-200

大200-

DRAILD

キーワード 数

1.5.0_07

KBDLM

lt

(25)

の検索コストは，次のようになる．

m × k × ([logk K] + 1) × n × B + F

m−1

F を N と K を用いて表すと，F =× d × B + N × m × F (26)wNKとなる．これを上式に代入した上で N に関するオーダーで考えると，第 2 項，第 3 項を考慮し， 

getG( KL1,…,KL m ,n){
G:G GDMCTFor i=0,…,m do
For t=0,…,|KLi| do
If(KLi(t).substring(n)){
G KLi(t) : G i}returtn G
}



出現数

N×m×F

break
}
If(t==n){L.add(li)}}return L //Minimum LCA
}



6G

JVM

  li

AMD Opteron2.2G

メモリ

DISC



表 2 キーワード の出現数

CPU

O((

!#"%$'&)(+*-,KLi(t)

wN
K

m−1

)

wN

+(

2

K

))

= O(Nm− + N )
1

2

(27)

となる．m 5 3 のとき O(N )，また m = 4 のとき O(Nm− ) ある．

.0/+1

2

6. 2

1

KBSIM

KBSIM

の LCA を求めるコストは，次の式になる．詳細は，[4]を参照されたい．
図 10

Lowest GDMCTを得るアルゴ リズム 

     

図 11 見積りにおける XML 文書木 図 12



KBDLM

(28)

しかし ，この LCA には，フォールスド ロップを含む可能性が  !"# $

あるのでフォールスド ロップリゾリューションのコストを求める．最悪の場合，LCA 数は，N である．その中でフォールスド ロップを見つけるコストは，(mに使用する構造•

k:B+木のファンアウト（ ノード のエントリ）数•N :XML 木の全葉ノード 数•

w:１ノード 当たりの平均キーワード 種類数•

F:１キーワード 当たりの平均ノード 数•

b:１ bit 比較コスト•

B:１ String 比較コスト•

r:ラベルの平均 String 数•

l:シグニチャのビット長•

n:検索キーワード の平均 String 長•

d:Dewey Oeder の平均ラベル長

6. 1

KBDLM

KBDLM

m × k × ([logk K] + 1) × n × B + b × l × (F − 1) × m

− 1)N

2

(29)

である．次は，Lowest GDMCT 木を求めるコストを求める．
すべてのキーワード のノード ラベルを比較するので以下の式に
なる．
N×m×F

(30)

以上より，検索コストは，次のようになる．
m × k × ([logk K] + 1) × n × B + (m − 1)N2+ b × l × (F − 1) × m + N × m × F(31)

N に関するオーダーは，第 2,3,4 項となり，F =

wN
K

を代入する

と，O(N ) となる．
2

6. 3
[1]

SA

より，コストは次のようである．

では，LCA を求めるコストは KBDL と同じなの
O(log2 N ∗ F

で以下の式になる．詳細は，[4] を参照されたい．
m × k × ([logk K] + 1) × n × B + F

m−1

×d×B

(24)

2m

)

= O(logN ∗ N m )2(32)

以上より，m > 2 の場合，KBSIM の検索コストが一番小さいということがわかる．

次は，Lowest GDMCT を求めるコストを求める．最悪の場合，
Lowest GDMCTの親の数は，XML 木の最下層のノード 数であるので N である．また，すべての検索キーワード のノード ラベルを比較するので次式になる．
 6 



 
43  
20 1  ./-, 
 
54
-2 3576
8:9<;=>
8:9 5@? 

01
./

687
9;:=<>
9;: 6? 






図 13




 "
 !$#&%'# () + *

出現数：小のキーワード 数を変えた比較

図 15

   
# 
" 
! 
76
354 
12
 
/0
 



 
2 
/ 01   -.  
+,  8:9;=<?>  ;=< 8,@ 




図 14

7.



!

$ 
!
% &(')&(*,+ .-



評価実験

本稿に おけ る評価実験の目的は ，KBSIM の有効性を 調べるために KBDLM と SA を様々なパラメタに基づき評価をす

出現数：大のキーワード 数を変えた比較  354
67 398;:





図 16

出現数：中のキーワード 数を変えた比較
!#"%$'&($')+* - ,


XML


! " #%$'&(*)

文書サイズを変えた比較

果とフォールスド ロップのない KBDLM，SA の検索結果との比較である．その結果，KBSIM の全ての検索結果にはフォー
ルスド ロップを含まないことが確認できた．
7. 2

検索キーワード 数による影響を調べる実験

る．実験に使用し た計算機および 環境を表 1 に示す．使用す検索キーワード 数による影響を調べるために，XML 文書サる XML 文書は，Xmark の XML 文書生成器 xmlgn [16] を用

イズを 10M に固定し 検索キーワード 数を変化させて検索時間

い規模変更因子を 0.01,0.05,0.1 とし て作成する．それぞれのを計った．併せて，検索キーワードは，各出現数において実験

サイズは，約 1M(1,161,652 バイト ), 約 5M(5,873,341 バイト ),を行った．

約 10M(11,875,066 バイト ) である．予め，SA に用いる索引と

まず，出現数が小である場合の実験結果を図 13 に示す．す手法を用いた索引を作成する．また，Lowest

べての手法で見られる傾向は，検索時間が検索キーワード 数の抽出する手法のパフォーマンスは，それぞれのアル増加に伴い増えている．しかし ，KBSIM は他 2 手法に比べ多ゴ リズムより共通して検索キーワード 数と XML 文書サイズに

少遅い．次に，出現数が中である場合の実験結果を図 14 に示KBDLM,KBSIMGDMCTs影響されることが予想される．したがって，パラメタを XML

す．検索速度の傾向は，検索キーワード 数の増加するに伴い増文書サイズ，検索キーワード 数とし ，さらに [1] と詳し く比較

えている． しかし ，検索キーワード 数に伴う KBSIM の検索するため検索キーワード の出現数を表 2 のように分けて実験を時間の増加率は，他の手法と比べ非常に小さいことがわかる．

行う．

続いて，出現数が大である場合の実験結果を図 15 に示す．た

評価方法は，検索キーワード を与えてから Lowest GDMCTs

だし，KBDLM の検索時間は，他 2 手法より非常に大きいのでを抽出するまでの検索時間とする．検索時間は，各出現数の検索キーワード 数を 4 までとしている．全体の傾向としては，

キーワード 群からランダムに検索キーワード を選択し ，100 回同様であるが，出現数が中の場合よりも顕著に特徴がはっきりの平均とする．さらに，95 ％の信頼区間を使用しグラフを記現れている．

した．検索キーワード 数および出現数を変えた実験結果は，図13,14,15に示す．また，XML 文書サイズを変えた実験結果は，

図 16 に示す．
7. 1

フォールスド ロップ

まず最初に，KBSIM のフォールスド ロップリゾリューション
が正常であることを確かめる．確認方法は，KBSIM の検索結

7. 3

XML 文書サイズによる影響を調べる実験

次に，XML 文書サイズによる影響を調べるために，検索キー
ワード 数を 4 に固定し XML 文書サイズを変えて実験をした (図16)．また，KBDLM では，他 2 手法より明らかに検索時間が大きかったため図に載せていない．
図 16 から明らかなように XML 文書サ イズの増加に伴い，

 7 

KBSIMは SA に比べ検索時間の増加率が小さいことがわかる．
考

7. 4

察

実験結果により検索時間は ，検索キーワード 数，出現数，XML

文書サイズに影響することがわかる．

謝

辞

また本研究の一部は，文部科学省科学研究費補助金特定領域
研究 (18049026)，独立行政法人科学技術振興機構戦略的創造研

まず検索キーワード 数の影響について考察をする．特に出現究推進事業 CREST および東京工業大学 21 世紀 COE プログラ

数が中及び大の場合，検索キーワード 数及び出現数の増加に伴ム「大規模知識資源の体系化と活用基盤構築」の助成により行い KBDLM と SA は大きく検索時間に影響を受けるのに対し ，

なわれた．

KBSIM

文

は他 2 手法に比べほぼ受けていないことがわかる．これは，処理コストの見積もりで示したように KBSIM のコスト

[1]

in XML Trees.

のオーダは N であり，検索キーワード 数 m に影響しないが，
2

SAと KBDLM は N の m 乗であるので，検索キーワード 数 m

KBDLM

[2]

537538, 2005.
[4]

三木健士, 横田治夫. スーパーインポーズド コーデ ィングを用いた XML 文書キーワード 索引. 情処学会研究会報告 DBS-140-25,
情報処理学会.

[5]

C. Faloutsos and S. Christodoulakis.

ffice ling. ACM

Transactions on Office Information Systems, No. 3, pp. 237257,

べて非常に小さいので，KBSIM の重大な欠点とは考えにくい．

July 1987.
[6]

Evaluation.
[7]

Signature Files: An Ac-

ACM Trans. Inf. Syst., No. 4, October 1984.

Igor Tatarinov, Stratis D. Viglas, Kevin Beyer, Jayavel Shanmigasundaram, Eugene Shekita, and Chun Zhang.

以上より，KBSIM は，SA と KBDLM と比べて XML 文書サIn Proc. ACM SIGMOD 2002, pp. 204215, 2002.
[8]

G. Salton, J. Allan, and C. Buckley.

Approaches to Passage

Retrieval in Full Text Information System.

8.

Storing andQuerying Ordered XML Using a Relational Database System.

イズ，検索キーワード 数，その出現数の増加に伴い効果的になると言える．

C. Faloutsos and S. Christodoulakis.

cess Method for Documents and Its Analytical Performance

書サイズの増加において SA に比べ検索時間の増加率が小さい
ことがわかる．

Descriptionand perfor-

mance analysis of signature le methods for o

さいため検索時間は，出現数が中及び大の場合の検索時間に比また，XML 文書サイズの影響に関して，KBSIM は，XML 文

fficient keyword search

Yu Xu and Yannis Papakonstantinou. E

for smallest lcas in xml databases. In SIGMOD Conference, pp.

間は，KBSIM が他 2 手法と比べて多少大きい．しかし ，すべての手法において Lowest GDMCT を求めるためのコストが小Yunyao Li, Cong Yu, and H. V. Jagadish. Schema-free xquery.
In VLDB, pp. 7283, 2004.

[3]

に対し早くなるが，検索キーワード 数が少ない場合には，KBDLM のほうが早い．一方，出現数が小の場合の検索時

IEEE Transaction on knowledge and data engineer-ing, No. 4, April 2006.

に影響するためだと考えられる．なお，SA と KBDLM の検索速度を比較した場合，検索キーワード 数が多いと SA のほうが献

Vagelis Hristidis and Nick Koudas. Keyword Proximity Search

おわりに

In Proc. of the Six-teenth Annual International ACM SIGIR Conference on Researchand Development in Information Retrieval, pp. 4958, June/July

本稿では，フォールスドロップを解決した KBSI と複数のキー
ワード に対して XML 部分木 (Lowest GDMCT) を高速に得る

1993.
[9]

Workshop on XML and Information Retrieval, pp. 204215, 2000.
[10]

International ACM SIGIR conference on Research and Development

らノード ラベルを有効利用し Lowest GDMCT を求める手法でin Information Retrieval, pp. 172180, 2001.
[11]

波多野賢治, 絹谷弘子, 吉川正俊, 植村俊亮. XML 文書検索システ
ムにおける文書内容の統計亮を利用した検索対象部分文章の決定. 電子情報通信学会論文誌, No. 3, pp. 422431, March 2006.

[12]

J. Clark and S.DeRose. XML path language (Xpath) version1.0,

提案手法と SA [1] に対して，いくつかのパラメタを設定しLowest GDMCTを抽出するコストの見積もりを行った結果，

1999.

検索キーワード 数が 3 以上において KBSIM のコストが最小で[13]あるとわかった．提案手法の有効性を示すために，パラメタをXMLを効率的に抽出できることが示せた．

[14]としたが，提案手法が様々な XML 部分文書にも有効であることを確認するため，Lowest GDMCTs 以外の XML 部分文

Praveen R. Raw and Bongki Moon. PRIX: Indexing and querying XML using prufer sequences. In Proc. of ICDE, pp. 288300,
March 2004.

[15]

Toshiyuki SHIMIZU and Masatoshi YOSHIKAWA. FULL-Text+-Tree. IEICE

and Structual Indexing of XML Documents on B

今後の課題として，今回は XML 部分文書を Lowest GDMCTs

In Proc.

of VLDB, pp. 436445, August 1997.

及びその出現数が増加すればするほど KBSIM 手法は，Lowest
GDMCTsR. Goldman and J. Widom. Dataguides: Enabling query formulation and optimization in semistructured databases.

文書サイズ，検索キーワード 数，およびその出現数とし，実験を行った．その結果，XML 文書サイズ，検索キーワード 数，

N.Fuhr and K. FroBjohann. XIRQL: A query language for information retrieval in XML document. In Proc. of 24th Annual

フォールスド ロップを解決した KBSI を利用し得られた LCA かある KBSIM を提案した．

Searching text-rich XML

documents with relevance ranking. In Proc. of ACM SIGIR 2000

手法とし て，KBDL の手法で求めた LCA から ノード ラベルを有効利用し Lowest GDMCTs を求める手法である KBDLM，

Y. Hayashi, J.Tomita, and G. Kikui.

TRANS. INF. & SYST., No. 1, January 2006.
[16]

The xml benchmark project.

//www.xml-benchmark.org

http:,2006.

書を求める必要がある．例えば，All GDMCTs [1] などがある．
ここでは考えなかった XML 文書の更新へのコストおよび対処などが課題として挙げられる．

 8 