論文

動的情報メデ ィエータのための知的情報収集手法
北村 泰彦y

野田智哉yy

辰巳 昭治yAn Intelligent Information Gathering Techinique for Dynamic Information Mediator
Yasuhiko KITAMURA , Tomoya NODA , and Shoji TATSUMI
y

yy

y

あらまし
今日，インターネットは社会に急速に普及し ，われわれの生活に欠かすことのできない基盤の１つになりつつある．中でも，WWW は個人の情報発信，学術研究，企業活動や電子商取引など 様々な目的で利用され ，発信される情報量は急速に増えつづけている．これらのイン ターネット情報源は単独で使用されることが一般的であったが，複数の情報源を組み合わせて利用することができればその価値をより高めることができるので，インター
ネット上に分散した情報を統合する情報メデ ィエータが注目されている．本稿では，統合すべき情報源が頻繁か
つ非同期に更新されるという前提のもとで，利用者のクエリに対して，許容時間内に情報源を適切にアクセスして解を導き出すという情報収集技法を提案する．本方式では，キャッシュ内データの信頼性と導出すべき解の質を考慮して，適切な情報アクセスと解の提示ができる．本方式の評価としては，実世界の WWW サイトからの情報を用いた航空情報メディエータを構築し ，従来の FIFO 型キャッシュ手法と比較して，より効率よく情報ア
クセスを行っていることを明らかにし た．
キーワード

1.

インターネット，WWW，情報メディエータ，キャッシュ，情報統合

かし ながらこれらの手段は，関連するページの集合をはじ めに提供するだけであり，ページの収集，必要な情報の抽今日インターネットは社会に急速に浸透し ，我々の生活に欠かすことのできないインフラストラクチャの出，抽出された情報の統合といったことは自動的には行われない．そこで，複数の WWW 情報源から発信１つになりつつある．中でも WWW は，電子商取引

される情報を組み合わせて，問題解決に利用する情報をはじめとし た企業活動，学術研究，コミュニティ形

統合技術が重要になる．

情報源はそれぞれ単独で利用するのが一般的であるが，システムが考えられ る．日本の主要な航空会社は，運これらを組み合わせて利用することができれば，その行スケジュールと空席状況を検索できるサービ スを成など 様々な目的で利用されている．これらの WWW

利用価値が高められ る．

WWW 情報統合の例とし ては，航空機の空席照会

WWW で提供している．このサービスでは搭乗日，出

このための手段とし て，リンク集やポータルサイ

発地，目的地など を入力すると，該当する便の便名，連結させることで関連付けを行っている．また，サーれる．しかしながら複数の航空会社が同一経路を運行

チエンジンは，利用者が 入力し たキーワード を含 むしている場合には，それぞれの航空会社のサイトにア

トでは，関連した WWW 情報源をハイパーリンクで

WWW ページの一覧を動的に作成して表示する．し運行スケジュール，空席状況などが結果として表示さクセスする必要がある．また乗り継ぎ情報が必要な場
合も繰り返しサイトにアクセスする必要が生じ る．そy 大阪市立大学工学部，大阪市

Faculty of Engineering, Osaka City University, Sugimoto 33-138, Sumiyoshi-ku, Osaka, 558-8585 Japanyy NTT コムウェア，札幌市
NTT Comware, Ohdohrinishi 7-3, Chuo-ku, Sapporo, 0600042 Japan
電子情報通信学会論文誌

X

こで，複数の航空会社の提供するサービ スの結果を統合して出力する空席照会システムを実現できれば，利用者はこのようなわずらわしさから解放される．

Vol. Jxx{X

しかし ながら WWW 情報統合を実現するには以下
No. xxpp. 1{8xxxx

年 xx 月1

電子情報通信学会論文誌 'xx/xx Vol. Jxx{X No. xx

た時間内でいかに適切に情報収集を行うかが重要な課
題となる．
WWW site

user

query
answersubquery

内にキャッシュし つつ，利用者のクエリが来た後に必WWW page

mediator

そこで，本稿では，過去に得た情報を メディエータ
要な情報の再検索を効率良く行うことで，適切な解のuser

WWW siteuser

WWW site

提示を行 う手法を提案する．そのために，キャッシュ
した情報の信頼性と質を考慮して再検索すべき情報を

図2

図1

メディエータによる情報統合

Infromation integration through a mediator.

決定し，ネットワークへのアクセス回数が限定された
状況下においてもできるだけ適切な解を提示する情報
収集アルゴ リズムを提案する．

の問題点がある．

(1) 自律分散した WWW 情報源： WWW 情報源は

2 章では我々の提案するアルゴ リズムについて説明
し，3 章では実験によって我々のアルゴ リズムの有効性を示す．4 章で関連研究に ついて述べ，5 章でまとインターネット上に分散して存在し ，それぞれが独立めと今後の課題とする．

して管理，運営されている．そのため分散している情報源から，関連し ている情報を収集し なければ ならない．

2.

知的情報収集アルゴリズム

本稿では WWW 情報統合を実現するために図 1 に(2) アクセスコスト： WWW 情報源へのアクセスは示したメディエータを採用する．メディエータは利用

インターネットを介するので時間がかか る．また有料者からのクエリに対して，利用者の代わりに必要であの情報源へのアクセスは費用がかかる．特に，WWW

情報統合では多くのの WWW ページを収集する場合

れば 複数の WWW サイトにアクセスし ，その情報を抽出，統合することで得られた解を利用者に提示する．

もあり，アクセスにかか る時間やコストはさらに大きメデ ィエータのアクセスコストを軽減するために，一くなる．

度得たデータはメディエータ内にキャッシュされる．し(3) 動的な WWW 情報源： WWW 情報源の中にはかし ながら，情報源のデ ータが頻繁に更新される場合

頻繁にに情報の更新がおこなわれるものがある．また，には，一度キャッシュしたデ ータであっても，再検索更新の頻度はそれぞれの情報源で異なり，非同期に行する必要が生じ る．一方，利用者に対してはある許容

われ るので，更新されたかど うかは実際にアクセスし時間以内に何らかの解を返す必要があり，再検索はこてみないと分からない．

の許容時間内に行う必要がある．すなわち，ど の情報(1) の問題に対処するために ，本稿では図 1 に示す源に対して再アクセスするかが 重要な課題となる．

よ うに 分散し ている情報を 統合する情報 メディエー

本節では，キャッシュするデータの信頼度と質を考受け取ると， メデ ィエータは複数の WWW 情報源に

ゴ リズムについて述べる．このアルゴ リズムでは，許タ [15] を採用している．利用者からクエリ (query) をアクセスして必要な情報を抽出する．そして得られた情報を用いて，利用者のクエリに 対する解 (answer)

を求め，利用者に返す．次に (2) に対してはキャッシュ
用いることで対処する．一度得た情報を収集してキャッ

シュしておくと，WWW 情報源にアクセスする回数が減るので，応答時間を短縮することができる．

しかし （， 3) に示されるように， WWW 情報源の発慮して再検索するデータを決定する知的情報収集アル
容時間内でデータの再検索を繰り返し行い，得られたデータの内容によって次に再検索するデータを動的に
決定する．
2. 1

事

実

メディエータは WWW ページを収拾し，そこから必要なデ ータを抽出する．ここでは抽出される原子的な情報を事実 (fact) と呼ぶ．単一の WWW ページか信する情報は頻繁に更新される可能性がある．そのたら複数の事実が抽出されることもある．例えば図 3 でめ，キャッシュした情報が古くなってし まうと正しい示されるような飛行経路を扱う空席照会システムでは，解を提示できなくなってし まう．一方，キャッシュを事実として図 4 のような運行スケジュールと空席状況

利用しなければ，大量の情報収集を必要するときには，が抽出される．メデ ィエータは事実を抽出すると，そ解の提示に長時間を要してし まう．そのため，限られれをキャッシュしておく．

2

論文／動的情報メディエータのための知的情報収集手法

事実の信頼度は長時間一定である．

Sapporo

信頼度関数をここではJAL529r(f ) = 1 +1 wt

JAL124tとし て近似する．ここで ， はキャッシュし てか らのJAS311
Haneda

経過時間，w は事実のタイプに 依存する重みである．
w を大きくすると信頼度は早く減少し，小さくすると

Itami
ANA217

ゆっくりと減少する．

ANA101

本稿では，更新される事実を動的な事実 (dynamicfact)，更新されない事実を静的な事実 (static fact) とJAS315
Kagoshima

呼んでいる．実世界において絶対に更新されない事実

図3 飛行経路
Fig. 3 Flight connection.

というのはわずかだと考えられ るが，扱う問題に応じて，更新されないとみなしても支障のない事実を静的

Fact

Reliability

flight(JAL529,Sapporo,Haneda,0700,0800)

1flight(ANA217,Itami,Kagoshima,1000,1200)

1flight(JAS315,Itami,Kagoshima,1300,1500)

1flight(JAS311,Haneda,Itami,0830,0930)

1

flight(ANA101,Narita,Kagoshima,0930,1100)1

flight(JAL124,Sapporo,Itami,0800,0900)

1

availability(JAL124,1999/12/16,Yes)

0.90

availability(ANA217,1999/12/16,Yes)

0.60

availability(JAS315,1999/12/16,No)

0.30

availability(JAL529,1999/12/16,Yes)

0.70

availability(JAS311,1999/12/16,Yes)

1.00

availability(ANA101,1999/12/16,No)0.60

図 4 空席照会システムにおける事実

Fig. 4 Facts for ight information service.
2. 2

な事実とする．例えば空席照会システムであれば，非常に 頻繁に 更新され る空席状況が動的な事実になる．
一方，ほとんど 変更されない運行スケジュールは静的な事実とみなせる．静的な事実は一度キャッシュすると，再検索する必要はなく，再検索の対象は動的な事
実にしぼられる．
2. 3

解

利用者からクエリを受け 取ると，メディエータはキャッシュしている事実を用いて，利用者のクエリに対する解 (answer) を導出する．具体的な導出方法は問題によって異なるが ，例えば 以下のよ うに Prolog

的なルール表現できる．

事実の信頼度

情報源の発信する情報が頻繁に更新される場合には，時間がたつとともに メデ ィエータがキャッシュした事
実と，もともとの情報源の情報に食い違いが生じる可能性が大きくなる．そこで，メディエータがキャッシュした事実に対し，その事実がどの程度信頼できるかを表すために ，0 から 1 の値をとる信頼度

r(f ) を定義する．信頼度は情報源から事実を抽出してキャッシュ
した直後が最も値が高く，時間が経つにつれてその事
実の信頼度は低下する．そのため

r(f ) は，事実 f をキャッシュしてからの経過時間に対して，1 から 0 に収束する単調減少関数になる．

それぞれの事実ごとに 更新頻度は異なるため，信頼度関数のふるまいはそれぞれの事実に依存する．例えば，航空機の空席状況，株価や為替相場のように非常に頻繁に更新される事実であれば，その信頼度はすぐに低下する．一方，航空機の運行スケジュールのようにまれにしか更新されない事実も存在し ，このような(R1) query($A; $B) : ;$fact($A; $B):
(R2) query($A; $B) : ;$fact($A; $C); query($C; $B):
ここで$fact($A,$B) はキャッシュされている事実であり，$A と$B は変数である．(R1),(R2) を繰り返し適用することでクエリを満たす事実の集合が得られる．一般に解は複数個存在する．

空席照会システムであれば，解を導出する手続きは，
以下のように表現できる．

(R3) query($P1; $P2; $Date; $T1; $T2) : ;$flight($Number; $P1; $P2; $Dep; $Arr);$availability($Number; $Date; $Status);$Dep >= $T1;
$T2 >= $Arr:3電子情報通信学会論文誌 'xx/xx Vol. Jxx{X No. xx(R4) query($P1; $P2; $Date; $T1; $T2) : ;を取ることにより定義している．
$flight($Number; $P1; $P3; $Dep; $Arr);
Q(A) = QS (A)  QD (A):$availability($Number; $Date; $Status);
例えば ，図 5 より，札幌から鹿児島に行くルートは$Dep >= $T1;
5 種類存在し ，到着時刻は 11:00，12:00，15:00 の 3$T2 >= $Arr;
種類が存在する．もし 利用者が 16:00 までに 鹿児島にquery($P3; $P2; $Date; $Arr; $T2):
着きたいならば ，A1 の静的な質は

QS (A1 ) = 1 ; 1624; 8 = 0:67

(R3) は日付 Date に時刻 T1 以降に空港 P1 を出発

し ，空港 P2 に 時刻 T2 までに 到着する直行便を表す．

(R4) は空港 P3 を経由するルートである．例えば，札幌

から鹿児島にいく旅程 query(Sapporo,Kagoshima,
1999/12/16,0600,1600) を利用者が要求した場合には，図 4 で示されるキャッシュされたデータから，図5 で示される解が導かれ る．
2. 4

解 の

質

解の質 (quality) は，その解がど の程度利用者のクとなる．動的な質は JAL124 と ANA217 がともに空席があるので， 1 である．

A2 の静的な質は A1 と同じであるが，動的な質は JAS315 が満席であることから，0 となる．したがって解全体の質はQ(A2 ) = 0 となる．
2. 5

Q(A1 ) = 0:67，

解の信頼度

メディエータは，自身のキャッシュしている事実をエリを満たしているかを表す．質は，再検索する事実用いて解を求めるが，解の導出の用いた事実の信頼度

や，利用者に提示する解を決定するために 使用されが低いと，その解の信頼度も低いと言える．そこで，る．解の質は解を構成する事実から計算され，動的な解の信頼度

質 (dynamic quality) と静的な質 (static quality) にR(A) を以下のように定義する．
R(A) = min
r(f )
f 2A

分けられる．動的な質は動的な事実に関する質であり，静的な質は静的な事実に関する質である．
それぞれの質の具体的な評価方法は，扱う問題に

例えば ，解よって異なる．空席照会システムでは，運行スケジュー

R(A1 ) = minf0:90; 0:60g = 0:60:

ルと空席状況が事実になるので，これらを用いて質を評価する．利用者の希望する経路の飛行時間が 短く，かつ用いるすべての便に空席があれば，良い解といえ，そのような解の質は高くすればよい．この例では静的な質は飛行スケジュールに関するものなので，解Aの静的な質は以下のように定義できる．

QS (A) =(1 ; ta ; td
024

0  ta ; td  24;otherwise,

A1 の信頼度は以下のように計算される．

2. 6

アルゴ リズ ム

解は メディエータのキャッシュする事実の集合を用いて導出するが，WWW 情報源の発信する情報は更新されている可能性があり，解の信頼度は低下する．解の信頼度を向上させるには WWW 情報源より再検索すればよいが，それは利用者の許容時間内で行う必要がある．したがって，再検索する事実の決定方法が重ta は希望する到着時刻，td は最初のフラ イトの出発時刻である．すなわち 24 時間以内の旅行時間

A に対して，再検索する事実を決S (A)，利用者に提示する順序を決定するための提示スコア P (A) を定義し ，こで，それが短いものほど 質が高いといえる．それ以外

れらの関数を用いて，再検索を行う事実や利用者に提ここでの質は 0 と定義されている．

動的な質は空席に関するものなので，以下のように

QD (A) =10

if 全てのフライトに空席がある,
otherwise.

解全体の質は以下のように静的な質と動的な質の積4

示する解を決定する．図 6 にそのアルゴ リズムを示す．
アルゴ リズムについて説明する．最初に，利用者からクエリ (query) を受け取ると，キャッシュされた事定義できる．

(

要になる．そこで解定するための再検索スコア

実を用いて解を導出する (1 行目)．（ 注 1）次に，できる

1（注 ）：ここでは全ての事実はあらかじめキャッシュされており，静的な事実と動的な事実の信頼度はそれぞれ と に設定されていると仮定
している．

1

0

論文／動的情報メディエータのための知的情報収集手法

AnswerFacts

A1

flight(JAL124,Sapporo,Itami,0800,0900), availability(JAL124,1999/12/16,Yes),

A2

flight(JAL124,Sapporo,Itami,0800,0900), availability(JAL124,1999/12/16,Yes),

A3
A4
A5

flight(ANA217,Itami,Kagoshima,1000,1200), availability(ANA217,1999/12/16,Yes).
flight(JAS315,Itami,Kagoshima,1300,1500), availability(JAS315,1999/12/16,No).
flight(JAS529,Sapporo,Haneda,0700,0800), availability(JAS529,1999/12/16,Yes),
flight(JAS311,Haneda,Itami,0830,0930), availability(JAS311,1999/12/16,No),
flight(ANA217,Itami,Kagoshima,1000,1200), availability(ANA217,1999/12/16,Yes).
flight(JAS529,Sapporo,Haneda,0700,0800), availability(JAS529,1999/12/16,Yes),
flight(JAS311,Haneda,Itami,0830,0930), availability(JAS311,1999/12/16,No),
flight(JAS315,Itami,Kagoshima,1300,1500), availability(JAS315,1999/12/16,No).
flight(JAS529,Sapporo,Haneda,0700,0800), availability(JAS529,1999/12/16,Yes),
flight(ANA101,Narita,Kagoshima,0930,1100), availability(ANA101,1999/12/16,Yes).

図5

query(Sapporo,Kagoshima,1999/12/16,0600,1600) に対する解の集合

Fig. 5 A complete set of answers to query(Sapporo,Kagoshima,1999/12/16,0600,1600).

1: construct answers fA1 ;A2 ;   g to a user's query by using cached facts
2: repeat until query time expires f
3: select Ai where S (Ai ) = maxfS (A1 ); S (A2 );   g
4: select fm where r(fm ) = minfn 2Ai r(fn )5: reload a WWW page and update fm g
6: sort answers by P ()7: return the best answer to the user
図 6 情報収集アルゴ リズム
Fig. 6 Information gathering algorithm.

S 値が最も大きA2 が選択される．A2 には現在，満席のフライト

だけ 正しいな解を提示するために， メデ ィエータは予を示そう．最初に 5 つの候補の中からめ指定された時間が経過するまで，事実の再検索を行い解う (2-5 行目)．繰り返しの中では，更新すべき事実を選択する (3 行目)．それは各解

Ai に対して，

その事実はすでに 更新され ているかもし れない ．しS (Ai ) = QS (Ai )  (1 ; R(Ai ))たがって， availability(JAS315,1999/12/16,No)を計算する．この式により，静的な質が大きく，信頼度の低い解を選択することができる．そのような解は更新されれば ，信頼度と質がともに高い解に至る可能性が高い．一方，静的な質の低い解は更新されたとしても，質は高くないので考慮する必要はない．ここでは質に関しては静的なもののみを考慮しているが，動的な質は検索するまでその値が未知であるからである．
次に選択された解の中から，最も信頼度の低い事実が選択され (4 行目)，最終的にその事実を更新するた

めに WWW サイトから関係するページ を再検索し ，事実の更新を行う (5 行目)．

再検索の時間が過ぎると，メディエータは解をによりランク付けする．

P (Ai ) はP (Ai)P (Ai) = Q(Ai )  R(Ai )とし て定義され，信頼度と質の高い解を反映するようにし ている (6,7 行目)．

JAS315 が含まれている (図 5 参照) が，図 4 に示されるようにその信頼度 (Reliability) は低い (0.30) ので，

ここで表 1 を用いてど のように事実が更新されるかが 更 新 の た め に 選 択 さ れ る ．こ こ で こ の 事 実 がavailability(JAS315,1999/12/16,Yes) に 更 新されているとしよう．このとき，その信頼度は 1 になり，

A2 と A4 が更新される．
2 回目の更新の際には S 値が最大になる A1 が選択さこの事実を含む解れ，これまでと同様に availability(ANA217,1999/12/16,Yes)が更新される．今度は availability(ANA217,1999/12/16,No)になったと仮定しよう．このときA1 と A3 の Q 値が0 になる．この時点で更新時間が過ぎたとすると，最大のP 値をもつ解 A2 が選択され ，利用者に提示さ

れる．
3.

評価実験

理想的なメデ ィエータは最適な解を短い時間で返すことができると考えられ る．そこで，ランダムに作成したクエリをメデ ィエータに送り，再検索の回数のを変化に応じて， メデ ィエータの提示する解と最適解が一致する確率 (成功率) がど のよ うに変化するかを測定した

5電子情報通信学会論文誌 'xx/xx Vol. Jxx{X No. xx
表 1 事実の更新に応じた各関数値の変化
Table 1 Changes of function values according to the number of updates
Ai Qs
No update
1st update
2nd update

Q R P S Q R P S Q R P S
A1 0.67 0.67 0.60 0.40 0.27 0.67 0.60 0.40 0.27 0.00 0.90 0.00 0.07
A2 0.67 0.00 0.30 0.00 0.47 0.67 0.90 0.60 0.07 0.67 0.90 0.60 0.07
A3 0.63 0.63 0.60 0.38 0.25 0.63 0.60 0.38 0.25 0.00 0.70 0.00 0.19
A4 0.63 0.00 0.30 0.00 0.44 0.63 0.70 0.44 0.19 0.63 0.70 0.44 0.19
A5 0.63 0.00 0.60 0.00 0.25 0.00 0.60 0.00 0.25 0.00 0.60 0.00 0.25
比較対象には，キャッシュした事実の質を考慮せず率は向上している．おおまかに 述べると，一つのクエに，キャッシュの信頼度のみを再検索する事実の決定

リーに対して 8 回のアクセスで提案手法 (IIGA) は最

これは，最も古くキャッシュされた事実から再検索をクセスが必要であることがわかる．これは FIFO が解行う方法である．これは提案アルゴ リズムに おいて，の信頼度のみを考慮して，再検索する事実を選択して再検索スコアをいるのに 対して，提案手法では解の信頼度と質をともに用いる FIFO(First-In First-Out) 法（注 2）を用いた．

SFIFO (A) = 1 ; R(A)

適解を得ることができる．一方 FIFO は約 18 回のアに考慮していることによるものである．この評価実験
では，実世界の環境でも評価可能なように問題の規模をかなり小さくしている．乗り継ぎの回数を 1 に制限とし た場合と等価である．

評価実験は実世界の航空会社の WWW サイトからの情報を統合する空席照会システムの上で行った．これらの WWW サイトは JAL (Japan Air Line)（ 注 3）,

ANA (All Nippon Airways) 4 , JAS (Japan Air
Systems) 5 により提供されているものである．ここ
（注 ）

（注 ）

では運行スケジュールを静的な事実，空席情報を動的な事実と見なし ており，2 節で述べたように解や事実の質と信頼度を計算している．

評価実験では，1999 年 12 月 18 日に，札幌，羽田，伊丹，関西，福岡，那覇空港を離発着する JAL，JAS，

ANA の便を対象とした．1999 年 12 月 8 日から，12
月 18 日まで，出発地と到着地をランダ ムに作成したクエリーを１時間間隔で送り，最適解を提示する確率(成功率) を測定した． 6 乗り継ぎの回数は 1 回に制（注 ）限した．これは実世界でも実行可能なように問題の規模を小さくするためである．最適解を得ることのできしているので，解を構成する事実の数は高々4 （静的な事実と動的な事実がそれぞれ 2 ）である．さらに，航空会社の提供する WWW サイトでは一つのクエリーに対して多数の事実を含むページを返すことが 多く，これも全体的に WWW アクセスを減らす要因にもなっている．（ 注 7）しかし ながら問題の規模をさらに拡大するならば ，提案手法の優位性はより顕著なものになると予想される．
4.

関連研究

情報統合の研究はデ ータベースや人工知能の分野において盛んに行われている．[4],[7], [10], [16] データ

ベースからの代表的な事例とし て，米国 Stanford 大
学の Tsimmis プロジェクトは WWW 情報源に 限らずネットワーク上に分散している様々な異種情報源を柔軟に 統合することを目的としている [2]．このプ ロる比率を図 7 に示す．横軸は更新の回数を表し，縦軸ジェクトの特徴は従来の分散データベースでとられたは最適解を得た比率を表している．

れの自立的情報源の出力結果をメデ ィエータ (medi-

両手法ともに更新の回数が増えるにし たが って成功

2
Used)

LRU(Least Recently（注 ）：他のよく知られたキャッシュ戦略としてはがあるが，これは静的な情報源を前提としており，本論文で対象となっている動的な情報源のためのキャッシュ更新アルゴ リズムとしては適さないので，比較の対象とはしなかった．
（注 ）
：
（注 ）
：
（注 ）
：
（注 ）
：全部で
のクエリーを送ったが，サイトの障害のために，そのうちのクエリーに対してメディエータは何らかの解を導出した．

ように情報源のレベルで統合するのではなく，それぞator) [15],[17] により統合する点である．本研究においても メディエータを情報統合の手段として採用している．また人工知能からのアプ ローチとしては，情報エージェントとファシリテータを ACL(Agent Com-

3 http://www.5971.jal.co.jp/cgi-bin/db2www/avail.d2w/report munication Language) [3] 用いて統合する連邦アーキ
4 http://rps.ana.co.jp/drs/vacant1.cgi
テクチャ [6] がある．
5 http://www.jas.co.jp/kusektop.htm
6264(=2411)
WWW213（ 注 7）：例えば，ANA のサイトでは単一のクエリーに対する応答のページから 22 の事実を抽出することができた．

6

論文／動的情報メディエータのための知的情報収集手法

100
IIGA
FIFO
95

Success ratio(%)

90

85

80

75

70

65

60
0

5

10

図7

15

20

25

30

Number of updatesExperimental Result

従 来の WWW 情報統合は 主に WWW 情 報源の構造化 [11]，WWW 情報源か らの 情 報抽出 [8] や収集 [5],[13]，情報マッチメイキング [12] といった話題

得られ，時間をかければかけるほど 良い解が得られ るというエニータイムアルゴ リズム [14] の性質も兼ね備えている．

が中心に議論されてきた．しかしながらこれらの研究

は文献 [1] を除いて，情報源が頻繁に更新され るような前提では議論されてこなかった．文献 [1] では分散
メデ ィエータシステムにおけるキャッシュと最適化の問題を扱っている．ここでは主に，通信オーバヘッド，
情報源の応答時間，経費，障害など を考慮して，ど の情報サイトにアクセスすべきか ，またキャッシュすべ
きかについて議論している．それに対して本論文では，
通信路やサイトの性能には特に着目せず，解の信頼性と質を考慮して，限られた時間の中でできるだけ良い解を提示するための情報収集アルゴ リズムを議論している．view maintenance [18] の研究では 複数の情報源からの情報を無矛盾に統合しようとし ている．しかしながら分散している大量の情報を無矛盾に保つためには大量の通信が必要になると考えられ ，また情報源が頻繁に更新される場合にはそれを行うことは不可能に近くなる．本論文の手法は限られた検索時間内でできるだけキャッシュの内容を無矛盾にするような半矛

盾的 (semi-consistent) なアプ ローチを取っているといえる．
ここで提案されたアルゴ リズムは常に何らかの解が

5.

ま

と

め

WWW 情報統合の問題点とし て情報源の更新の問
題に対処する方法を提案した．メデ ィエータは限られた時間内に適切に情報を収集し ，適切な解を利用者に提示する必要がある．ここではキャッシュ内のデータの信頼度と解の質を考慮し，再検索すべき事実を選択する知的情報収集アルゴ リズムを提案し た．従来のFIFO では信頼度ののみしか考慮していなかったのに対して，この手法では解の質を考慮するために，FIFO
よりも優れた性能を示すことを空席照会システムという現実問題に応用することで示した．ここでは具体的な応用事例とし て航空機の空席照会システムを取り上げたが，本手法は頻繁に更新されるような情報源の統合に有効であると考えられる．株価情報システムや電子オークションなど の他の領域への応用も検討してゆきたい．
謝辞
本研究の一部は，新エネルギ ー・産業技術総合開発

機構 (NEDO) の委託事業「 シニア支援システムの開発」によるものである．

7

電子情報通信学会論文誌 'xx/xx Vol. Jxx{X No. xx

文献[1] Adali, S., Candan, K.S., Papakonstantinou, Y., andSubrahmanian, V.S.: Query Caching and Optimization in Distributed Mediator Systems, SIGMOD-96(1996) 137{148[2] Chawathe, S., Garcia-Molina, H., Hammer, J., Ireland, K., Papakonstantinou, Y., Ullman, J. andWidom, J.: The TSIMMIS Project: Integration of
Heterogeneous Information Sources. Proceedings of
IPSJ Conference (1994) 7{18[3] Finin, T., Labrou, Y., and May eld J.: KQML asan Agent Communication Language. Bradshow, J.M.
(ed.): Software Agents. AAAI Press (1997) 291{316[4] Florescu, D., Levy, A., and Mendelzon, A.: Database
Techniques for the World-Wide Web: A Survey. SIGMOD Record, 27(3) (1998)[5] Friedman, M., Levy, A. and Millstein. T.: Navigational Plans for Data Integration. AAAI-99 (1999)
67{73[6] Genesereth, M.: An Agent-Based Framework forInteroperability. Bradshaw, J.M. (ed.): Software
Agents. AAAI Press (1997) 315{345[7] Hearst, M.: Information Integration. IEEE Intelligent Systems 13(5) (1998) 12{24[8] Hsu, J.Y. and Yih, W.: Template-based Information
Mining from HTML Documents. AAAI-97 (1997)
256{262[9] Kitamura, Y., Noda, T., and Tatsumi, S.: Singleagent and Multi-agent Approaches to WWW Information Integration. Ishida, T. (Ed.): Multiagent
Platforms, Lecture Notes in Arti cial Intelligence,Vol. 1599, Springer-Verlag. (1999) 133{147[10] Klusch, M. (Ed.): Intelligent Information Agents.
Springer-Verlag (1999)[11] Knoblock, C.A., Minton, S., Ambite, J.L., Ashish,N., Modi, P.J., Muslea, I., Philpot, A.G., and Tejada, S.: Modeling Web Sources for Information Integration. AAAI-98 (1998) 211{218[12] Kuokka, D. and Harada, L.: Integrating Information
via Matchmaking. Journal of Intelligent Information
Systems 6 (1996) 261{279[13] Kwok, C.T. and Weld, D.S.: Planning to Gather Information. AAAI-96 (1996) 32{39[14] Russell, S.J. and Norvig, P.: Arti cial Intelligence:
A Modern Approach. Prentice-Hall, Inc. (1995) 844[15] Wiederhold, G.: Mediators in the Architecture of
Future Information Systems. IEEE Computer, 25(3)(1992) 38{49[16] Wiederhold, G. (Ed.): Intelligent Integration of Information. Kluwer Academic Publishers (1996)[17] Wiederhold, G. and Genesereth, M.: The Conceptual Basis for Mediation Services. IEEE Expert, 12(5)(1997) 38{47[18] Zhuge, Y., Garcia-Molina, H., Hammer, J., andWidom, J.: View Maintenance in a Warehousing En8

vironment. SIGMOD-95 (1995).