(57)【要約】【課題】個々のＷｅｂサーバに及ぼすアクセス負荷を抑えつつ、収集Ｗｅｂページの網羅性・収集頻度の制御を可能にするＷｅｂページ再収集方式を得る。【解決手段】ハッシュ値の比較に基づいてダウンロードしたＷｅｂページの更新の有無を検知し、ダウンロード時刻と更新の有無を履歴データとして記憶部２に記憶させ、履歴データに基づいて当該Ｗｅｂページが次に更新されると期待される時刻を次回ダウンロード時刻として設定して記憶部２に記憶させるＷｅｂページ再アクセススケジューリング手段６と、同一Ｗｅｂサーバに属する複数のＷｅｂページのそれぞれのアクセス間隔を用いて、当該Ｗｅｂサーバに及ぼすアクセス負荷指標を計算し、アクセス負荷指標が所定許容値を超えない場合にアクセス負荷指標に基づいて当該Ｗｅｂサーバに対するアクセス間隔を設定するＷｅｂサーバアクセススケジューリング手段７とを備える。【選択図】図１
2008186157.tif 000002
【特許請求の範囲】
【請求項１】
Ｗｅｂサーバから前回ダウンロードしたＷｅｂページの内容またはＷｅｂページのハッシュ値を前回内容情報として記憶部に記憶させ、当該Ｗｅｂページを再度ダウンロードした際のＷｅｂページの内容情報と、前記記憶部に記憶された前記前回内容情報とを比較して当該Ｗｅｂページの更新の有無を検知し、ダウンロード時刻と前記更新の有無を対応付けたデータを履歴データとしてダウンロードを行うごとに前記記憶部にさらに記憶させ、前記履歴データに基づいて当該Ｗｅｂページが次に更新されると期待される時刻を次回ダウンロード時刻として設定して前記記憶部に記憶させるＷｅｂページ再アクセススケジューリング手段と、
同一Ｗｅｂサーバに属する複数のＷｅｂページについて、前記Ｗｅｂページ再アクセススケジューリング手段の有する前記記憶部に記憶された前記前回ダウンロード時刻と前記次回ダウンロード時刻との差分から求まるそれぞれのアクセス間隔を用いて、当該Ｗｅｂサーバに及ぼすアクセス負荷指標を計算し、前記アクセス負荷指標が所定許容値を超えない場合に前記アクセス負荷指標に基づいて当該Ｗｅｂサーバに対するアクセス間隔を設定するＷｅｂサーバアクセススケジューリング手段と
を備えることを特徴とするＷｅｂページ再収集方式。
【請求項２】
請求項１に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、前記所定許容値をＷｅｂサーバに属するＷｅｂページの数に応じて切り替えることを特徴とするＷｅｂページ再収集方式。
【請求項３】
請求項１または２に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、前記アクセス負荷指標が前記所定許容値を超えた場合には、Ｗｅｂサーバに属するそれぞれのＷｅｂページの前記アクセス間隔に対して一律の定数を乗算して次回ダウンロード時刻を再設定することを特徴とするＷｅｂページ再収集方式。
【請求項４】
請求項１ないし３のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、前記アクセス負荷指標が前記所定許容値を超えた場合には、Ｗｅｂサーバに属するそれぞれのＷｅｂページの前記アクセス間隔に対して一律の定数を加算して次回ダウンロード時刻を再設定することを特徴とするＷｅｂページ再収集方式。
【請求項５】
請求項１ないし４のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、前記アクセス負荷指標が前記所定許容値を超えた場合には、当該Ｗｅｂサーバに属するＷｅｂページのうち、共通する部分文字列をＵＲＩに含むＷｅｂページ群の一部を次回以降のダウンロード対象から除外し、除外されていないＷｅｂページに対して次回ダウンロード時刻を再設定することを特徴とするＷｅｂページ再収集方式。
【請求項６】
請求項５に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、ＵＲＩ文字列をディレクトリ単位で末尾から削除したものを前記部分文字列として用いることを特徴とするＷｅｂページ再収集方式。
【請求項７】
請求項５に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、パラメータとして符号？とそれに続く１つ以上のパラメータ名およびパラメータ値を含むＵＲＩに対して符号？以前の文字列とパラメータ名の組を前記部分文字列として用いることを特徴とするＷｅｂページ再収集方式。
【請求項８】
請求項５に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、ＵＲＩ文字列をディレクトリ単位で末尾から削除するとともに、パラメータとして符号？とそれに続く１つ以上のパラメータ名およびパラメータ値を含むＵＲＩに対しては符号？以前の文字列とパラメータ名の組を前記部分文字列として用いることを特徴とするＷｅｂページ再収集方式。
【請求項９】
請求項５ないし８のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、共通部分文字列が長いＷｅｂページ群を優先的に除外対象とすることを特徴とするＷｅｂページ再収集方式。
【請求項１０】
請求項５ないし８のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、前記アクセス間隔が短いＷｅｂページを多く含むＷｅｂページ群を優先的に除外対象とすることを特徴とするＷｅｂページ再収集方式。
【請求項１１】
請求項５ないし８のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、共通部分文字列以外のＵＲＩ文字列が数字のみ、または同一文字数の特徴を有するＷｅｂページ群を優先的に除外対象とすることを特徴とするＷｅｂページ再収集方式。
【請求項１２】
請求項５ないし８のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、内容またはそのハッシュ値が共通するものが多いＷｅｂページ群を優先的に除外対象とすることを特徴とするＷｅｂページ再収集方式。
【請求項１３】
請求項５ないし１２のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、内容またはそのハッシュ値が重複するＷｅｂページをダウンロード対象から除外することを特徴とするＷｅｂページ再収集方式。
【請求項１４】
請求項５ないし１３のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、ＵＲＩの文字列順に編成されたＷｅｂページの順番に基づいて除外対象となるＷｅｂページを選択することを特徴とするＷｅｂページ再収集方式。
【請求項１５】
請求項５ないし１３のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、前記アクセス間隔の短い順に編成されたＷｅｂページの順番に基づいて除外対象となるＷｅｂページを選択することを特徴とするＷｅｂページ再収集方式。
【請求項１６】
請求項１ないし１５のいずれか１項に記載のＷｅｂページ再収集方式において、
前記Ｗｅｂサーバアクセススケジューリング手段は、同一Ｗｅｂサーバに属する複数のＷｅｂページのアクセス間隔の逆数の総和を当該Ｗｅｂサーバの前記アクセス負荷指標として用いることを特徴とするＷｅｂページ再収集方式。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｗｅｂ検索サービスにおいて、個々のＷｅｂサーバに及ぼすアクセス負荷を軽減するＷｅｂページ再収集方式に関する。
【背景技術】
【０００２】
Ｗｅｂ検索サービスにおいては、クローラプログラムにより、ある時点でのＷｅｂの状態を網羅的に収集し、記載内容の断片からＷｅｂページの名前（ＵＲＩ：Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｉｄｅｎｔｉｆｉｅｒ）を検索するための索引を生成する従来技術がある。
【０００３】
一括型と呼ばれる通常のクローラは、最初に与えたいくつかのＵＲＩを起点とし、収集したＷｅｂページに含まれるハイパーリンクが指すＷｅｂページを再帰的に収集していく。このため、Ｗｅｂの広い範囲を網羅するには、例えば、１ヶ月というような時間を要する。そこで、時々刻々と変化するＷｅｂの状態を、より忠実に捉えるためのインクリメンタルクローラが開発されている。
【０００４】
インクリメンタルクローラは、一度収集したＷｅｂページを適当な期間を置いて、再度収集する。このインクリメンタルクローラは、Ｗｅｂページ毎に独立したタイミングで収集を行う。このため、Ｗｅｂ全体を網羅するのを待つことなく、一部のＷｅｂページの収集を繰り返すことができる。
【０００５】
再収集までの期間は、当該Ｗｅｂページの過去の更新傾向等に基づき、次の更新時期を予測することで決定される。例えば、Ｗｅｂページの変更回数、変更の規模、ＷｅｂページのＵＲＩや内容などの特徴に基づいて、当該Ｗｅｂページが最終アクセス後に更新されている確率を求め、クローリングの優先順位であるスコアに反映する方法がある（例えば、特許文献１参照）。
【０００６】
【特許文献１】特開２００５−２２８３４３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来技術には次のような課題がある。
クローラは、他者が運用するＷｅｂサーバに対してアクセスを繰り返すため、Ｗｅｂサーバ本来の目的である一般利用者への情報提供を妨げないよう、十分な間隔を空けてアクセスするなどの配慮が必要である。こうしたＷｅｂサーバアクセス間隔への配慮は、インクリメンタルクローラにおけるＷｅｂページ再収集のスケジューリングとは相容れず、Ｗｅｂページ収集時期やＷｅｂページ収集範囲が不適切なものになってしまう可能性がある。
【０００８】
特許文献１に記載されている従来技術では、クローラが動作するコンピュータおよび通信回線の性能で定まるクローリング容量に基づいて、収集Ｗｅｂページ数を決定する処理ステップが開示されている。しかしながら、この処理は、以下の２点の問題点を有している。
【０００９】
第１の問題点は、クローラには、高速な通信回線を接続するのが一般的であり、クローラの容量以下であっても、個々のＷｅｂサーバに対しては、過大な負荷をかけてしまう可能性があることである。また、アクセス間隔への配慮の結果生じるＷｅｂサーバへの負荷の上限値は、物理的な回線容量よりも大幅に小さいのが普通である。
【００１０】
第２の問題点は、クローリング容量のあふれがＷｅｂページの再収集時期に及ぼす影響を考慮しておらず、あふれが発生していない場合に対して収集時期がどのくらい遅延するか、あるいは全く収集できなくなるＷｅｂページがどのくらい発生するかなどを把握しないまま動作するという点である。
【００１１】
本発明は上述のような課題を解決するためになされたもので、個々のＷｅｂサーバに及ぼすアクセス負荷を抑えつつ、収集Ｗｅｂページの網羅性・収集頻度の制御を可能にするＷｅｂページ再収集方式を得ることを目的とする。
【課題を解決するための手段】
【００１２】
本発明に係るＷｅｂページ再収集方式は、Ｗｅｂサーバから前回ダウンロードしたＷｅｂページの内容またはＷｅｂページのハッシュ値を前回内容情報として記憶部に記憶させ、当該Ｗｅｂページを再度ダウンロードした際のＷｅｂページの内容情報と、記憶部に記憶された前回内容情報とを比較して当該Ｗｅｂページの更新の有無を検知し、ダウンロード時刻と更新の有無を対応付けたデータを履歴データとしてダウンロードを行うごとに記憶部にさらに記憶させ、履歴データに基づいて当該Ｗｅｂページが次に更新されると期待される時刻を次回ダウンロード時刻として設定して記憶部に記憶させるＷｅｂページ再アクセススケジューリング手段と、同一Ｗｅｂサーバに属する複数のＷｅｂページについて、Ｗｅｂページ再アクセススケジューリング手段の有する記憶部に記憶された前回ダウンロード時刻と次回ダウンロード時刻との差分から求まるそれぞれのアクセス間隔を用いて、当該Ｗｅｂサーバに及ぼすアクセス負荷指標を計算し、アクセス負荷指標が所定許容値を超えない場合にアクセス負荷指標に基づいて当該Ｗｅｂサーバに対するアクセス間隔を設定するＷｅｂサーバアクセススケジューリング手段とを備えるものである。
【発明の効果】
【００１３】
本発明によれば、同一Ｗｅｂサーバに含まれるＷｅｂページのアクセス間隔を考慮して求めたＷｅｂサーバ毎のアクセス負荷指標に基づいて、それぞれのＷｅｂサーバに対する最適なアクセスタイミングを設定することより、個々のＷｅｂサーバに及ぼすアクセス負荷を抑えつつ、収集Ｗｅｂページの網羅性・収集頻度の制御を可能にするＷｅｂページ再収集方式を得ることができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明のＷｅｂページ再収集方式の好適な実施の形態につき図面を用いて説明する。
【００１５】
実施の形態１．
図１は、本発明の実施の形態１におけるＷｅｂページ再収集方式の構成図である。本実施の形態１におけるＷｅｂページ再収集方式は、Ｗｅｂサーバ状態記憶手段１、Ｗｅｂページ状態記憶手段２、Ｗｅｂページ内容記憶手段３、ディスパッチ手段４、Ｗｅｂページダウンロード手段５、Ｗｅｂページ再アクセススケジューリング手段６、Ｗｅｂサーバアクセススケジューリング手段７、およびハイパーリンク抽出手段８で構成される。
【００１６】
ここで、Ｗｅｂサーバ状態記憶手段１、Ｗｅｂページ状態記憶手段２、およびＷｅｂページ内容記憶手段３は、記憶部に相当する。また、このような構成を有するＷｅｂページ再収集方式は、図１に示したように、インターネット９に接続された複数のＷｅｂサーバ１０ａ〜１０ｃから、所望のＷｅｂページをダウンロードできる構成となっている。
【００１７】
まず始めに、個々の構成要素の機能について説明する。
Ｗｅｂサーバ状態記憶手段１は、Ｗｅｂサーバ状態テーブルを記憶する記憶部である。図２は、本発明の実施の形態１におけるＷｅｂサーバ状態記憶手段１に記憶されるＷｅｂサーバ状態テーブル１１の形式を示す図である。
【００１８】
Ｗｅｂサーバ状態テーブル１１は、Ｗｅｂサーバ毎にＷｅｂサーバ名１２、Ｗｅｂサーバ状態１３、ダウンロード開始時刻１４、およびＷｅｂサーバ負荷指標１５を含むデータ構造を有し、Ｗｅｂサーバ状態記憶手段１に記憶されている。
【００１９】
Ｗｅｂサーバ名は、図１におけるＷｅｂサーバ１０ａ〜１０ｃに相当する名称である。次に、Ｗｅｂサーバ状態１３は、「休止」、「ダウンロード待ち」、および「ダウンロード中」の３つの状態のいずれかを取る。「休止」は、当該Ｗｅｂサーバに対応する収集対象Ｗｅｂページがない状態を示している。
【００２０】
また、「ダウンロード待ち」は、収集対象Ｗｅｂページは存在するが、Ｗｅｂページダウンロード手段５、Ｗｅｂページ再アクセススケジューリング手段６、Ｗｅｂサーバアクセススケジューリング手段７がいずれも起動されていない状態を示している。
【００２１】
さらに、「ダウンロード中」は、収集対象Ｗｅｂページに対して、Ｗｅｂページダウンロード手段５、Ｗｅｂページ再アクセススケジューリング手段６、Ｗｅｂサーバアクセススケジューリング手段７のいずれかが起動されている状態を示している。
【００２２】
また、Ｗｅｂサーバ状態１３は、通常、「ダウンロード待ち」と「ダウンロード中」の２つの状態間を遷移する。しかしながら、Ｗｅｂページが消失してダウンロードが失敗するようになるなどしたことにより収集対象から除外され、収集対象のＷｅｂページがなくなると、「休止」状態に遷移する。「休止」状態のＷｅｂサーバや未知のＷｅｂサーバに属するＷｅｂページへのハイパーリンクが発見されると、当該Ｗｅｂサーバの状態は、「ダウンロード待ち」となる。
【００２３】
また、ダウンロード開始時刻１４は、Ｗｅｂサーバ状態１３が「ダウンロード待ち」であるＷｅｂサーバについてのみ意味を持ち、現在時刻よりダウンロード開始時刻１４が前の時刻を示していれば、当該Ｗｅｂサーバは、「ダウンロード中」に遷移する候補となる。
【００２４】
このダウンロード開始時刻１４は、現在時刻との比較が可能であれば、必ずしも実世界の日時と対応している必要はなく、コンピュータのタイマ割り込みによるティック値などを用いることもできる。また、精度は、秒またはそれ以下であることが望ましい。
【００２５】
また、Ｗｅｂサーバ負荷指標１５は、浮動小数点数であり、時間の逆数の次元（１／秒＝Ｈｚ）を持つ。このような負荷指標に関しては、詳細を後述する。
【００２６】
次に、Ｗｅｂページ状態記憶手段２は、Ｗｅｂページ状態テーブルを記憶する記憶部である。図３は、本発明の実施の形態１におけるＷｅｂページ状態記憶手段２に記憶されるＷｅｂページ状態テーブル２１の形式を示す図である。
【００２７】
Ｗｅｂページ状態テーブル２１は、Ｗｅｂページ毎にＵＲＩ２２、次回アクセス時刻２３、アクセス回数２４、最終ハッシュ値２５、最終アクセス時刻２６、最終アクセス状態２７、および第２アクセス時刻２８（２）、第２アクセス状態２９（２）〜第Ｎアクセス時刻２８（Ｎ）、第Ｎアクセス状態２９（Ｎ）までのＮ−１個のアクセス時刻とアクセス状態の対からなる履歴データのそれぞれを含むデータ構造を有し、Ｗｅｂページ状態記憶手段２に記憶されている。
【００２８】
ＵＲＩ２２は、それぞれのＷｅｂページの名前に相当する。また、次回アクセス時刻２３は、対応するＷｅｂページを次回アクセスする時刻であり、後述するＷｅｂページ再アクセススケジューリング手段６により計算され書き込まれる値である。また、アクセス回数２４は、対応するＷｅｂページを現時点までにアクセスした回数を示しており、Ｗｅｂページ再アクセススケジューリング手段６により書き込まれる値である。
【００２９】
また、最終ハッシュ値２５は、前回ダウンロードしたＷｅｂページの内容にハッシュ関数を適用して得られる固定長のビット列を表す。ここで用いるハッシュ関数としては、公知のＭＤ５（１２８ビット）やＳＨＡ２５６（２５６ビット）などが挙げられる。
【００３０】
これらのハッシュ関数は、異なるＷｅｂページ内容に対して高い確率で異なるハッシュ値を生成すると期待できる。従って、前回ダウンロード時のハッシュ値である最終ハッシュ値２５と、最新のダウンロード時のハッシュ値とを比較することにより、最新のＷｅｂページの内容が前回ダウンロード時のＷｅｂページの内容と同一であるか否かを判断することができる。
【００３１】
このようなハッシュ値は、Ｗｅｂページの内容の一致度を判断するための内容情報に相当する。なお、この最終ハッシュ値２５は、後述する最終アクセス状態２７が「エラー」以外の場合に意味を持つ値である。
【００３２】
また、最終アクセス時刻２６は、当該Ｗｅｂページをアクセスした最近の時刻、すなわち前回アクセスした際のアクセス時刻を表し、最終アクセス状態２７には、その時のダウンロードの結果を「更新検知」、「更新非検知」、および「エラー」の３つの状態のいずれかとして記憶している。
【００３３】
「更新検知」は、Ｗｅｂページのダウンロードが成功し、かつ、内容情報の比較結果により、直前の取得内容と異なる内容が得られた際（または初回ダウンロード）に用いる。また、「更新非検知」は、Ｗｅｂページのダウンロードが成功し、かつ、内容情報の比較結果により、直前の取得内容と同一の内容が得られた際に用いる。さらに、「エラー」は、Ｗｅｂページのダウンロードが失敗し、内容が取得できなかったことを表す。
【００３４】
また、第２アクセス時刻２８（２）および第２アクセス状態２９（２）は、当該Ｗｅｂページに対する最近のアクセスの直前のアクセス（すなわち、２回前のアクセス）におけるアクセス時刻とアクセス状態をそれぞれ表す。以降、第３アクセス〜第Ｎアクセスまで順次遡ってアクセス時刻とアクセス状態を保持する。これらの履歴データは、当該Ｗｅｂページの更新傾向を判断するのに用いられ、次回アクセス時刻２３を決定する手掛かりとなる。
【００３５】
また、先に説明したアクセス回数２４の値ｍがＮより小さい場合には、第ｍ＋１アクセス〜第Ｎアクセスに対応するアクセス時刻およびアクセス状態は、無効であることを表す。
【００３６】
次に、Ｗｅｂページ内容記憶手段３は、ダウンロードしたＷｅｂページの内容をＷｅｂページのＵＲＩと対応付けて記憶する記憶部である。
【００３７】
次に、ディスパッチ手段４は、Ｗｅｂサーバ状態記憶手段１に記憶された情報に基づいて適切なタイミングでＷｅｂサーバからのダウンロードを起動する。
【００３８】
次に、Ｗｅｂページダウンロード手段５は、インターネット９を介してＷｅｂサーバ１０ａ〜１０ｃのいずれかのＷｅｂサーバから当該Ｗｅｂページをダウンロードして、その内容をＷｅｂページ内容記憶手段３に格納する。
【００３９】
次に、Ｗｅｂページ再アクセススケジューリング手段６は、Ｗｅｂページダウンロード手段５により起動され、Ｗｅｂページダウンロードの結果に基づいてＷｅｂページ状態記憶手段２に記憶されたＷｅｂページ状態テーブル２１を更新し、当該Ｗｅｂページの再収集時期を決定する。
【００４０】
次に、Ｗｅｂサーバアクセススケジューリング手段７は、Ｗｅｂページ再アクセススケジューリング手段６により起動され、Ｗｅｂサーバ状態記憶手段１に記憶されたＷｅｂサーバ状態テーブル１１とＷｅｂページ状態記憶手段２に記憶されたＷｅｂページ状態テーブル２１に基づき、当該Ｗｅｂサーバの負荷に応じて次回アクセスまでの間隔を決定する。
【００４１】
なお、Ｗｅｂページダウンロード手段５、Ｗｅｂページ再アクセススケジューリング手段６、およびＷｅｂサーバアクセススケジューリング手段７の組は、Ｗｅｂサーバ毎に複数存在してもよい。複数存在することにより、Ｗｅｂサーバ１０ａ〜１０ｃから並行してダウンロードを行うことができ、単位時間当たりのダウンロードページ数を向上させることができる。
【００４２】
次に、ハイパーリンク抽出手段８は、Ｗｅｂページ内容記憶手段３に追加された新たなＷｅｂページからハイパーリンクを抽出し、その内容に応じてＷｅｂサーバ状態記憶手段１に記憶されたＷｅｂサーバ状態テーブル１１とＷｅｂページ状態記憶手段２に記憶されたＷｅｂページ状態テーブル２１を更新する。
【００４３】
なお、上述したＷｅｂサーバ状態記憶手段１〜ハイパーリンク抽出手段８の８つの構成要素は、プロセッサ、バス、メモリ、固定ディスクインタフェース、固定ディスク装置、およびネットワークインタフェースを備えた一般的なコンピュータを用いることができる。より具体的には、Ｗｅｂサーバ状態記憶手段１〜Ｗｅｂページ内容記憶手段３の記憶部を固定ディスク装置で実現し、ディスパッチ手段４〜ハイパーリンク抽出手段８の各手段をメモリに格納されプロセッサで実行されるプログラムとして実現することができる。
【００４４】
次に、ディスパッチ手段４〜ハイパーリンク抽出手段８の各手段の具体的な動作を、フローチャートを用いて説明する。図４は、本発明の実施の形態１におけるディスパッチ手段４の動作を示すフローチャートである。ディスパッチ手段４は、ステップＳ４０１において、Ｗｅｂサーバ状態記憶手段１に記憶されたＷｅｂサーバ状態テーブル１１の内容を読み出し、全てのＷｅｂサーバについてＷｅｂサーバ状態１３が「休止」であるかどうかを判断する。
【００４５】
条件が成り立つ場合は、収集対象のＷｅｂページが全く存在しない（全て消失した）ことを表しているので、停止する。条件が成り立たない場合は、ステップＳ４０２において、Ｗｅｂサーバ状態１３が「ダウンロード待ち」であり、かつダウンロード開始時刻１４が現在時刻より前の時刻を示しているＷｅｂサーバが存在するかどうかを判定する。このようなＷｅｂサーバが存在しない場合は、ステップＳ４０１に戻り、存在する場合は、ステップＳ４０３に進む。
【００４６】
ステップＳ４０３において、Ｗｅｂサーバ状態１３が「ダウンロード待ち」であり、かつダウンロード開始時刻１４が現在時刻より前の時刻を示しているＷｅｂサーバを１つ選択する。続くステップＳ４０４において、Ｗｅｂサーバ状態テーブル１１における当該ＷｅｂサーバのＷｅｂサーバ状態１３を「ダウンロード中」に変更する。さらに、ステップＳ４０５において、当該Ｗｅｂサーバに対するＷｅｂページダウンロード手段５の処理を起動し、最初のステップＳ４０１に戻って処理を繰り返す。
【００４７】
ここでは、単純化のため、Ｗｅｂサーバ状態テーブル１１から条件を満たすＷｅｂサーバを検索するものとして説明した。しかしながら、効率的な実現のため、Ｗｅｂサーバ状態テーブル１１とは別に優先順位キューを用意し、「ダウンロード待ち」のＷｅｂサーバをダウンロード開始時刻の順に格納しておくこともできる。このような実現方式については、例えば、特開２００３−２７１６７０の図２に述べられている。
【００４８】
また、ステップＳ４０２において、条件が不成立の場合に直ちにステップＳ４０１に戻ると、間断なく条件判定を繰り返すことになる。そこで、セマフォや条件変数などの並行処理同期プリミティブを用いて、Ｗｅｂサーバ状態テーブル１１の内容が変化するまで待機するようにしてもよい。
【００４９】
なお、図１の説明において図示しているように、Ｗｅｂページダウンロード手段５〜Ｗｅｂサーバアクセススケジューリング手段７は、Ｗｅｂサーバ毎に複数並行的に動作することも可能である。このような並列駆動を行う場合、ステップＳ４０５の処理は、マルチスレッドプログラミング環境において、Ｗｅｂサーバ毎に実行スレッドを生成する、あるいは、イベント駆動型プログラミング環境においてＷｅｂサーバ毎にイベントを生成することによって実現される。
【００５０】
次に、図５は、本発明の実施の形態１におけるＷｅｂページダウンロード手段５の動作を示すフローチャートである。ステップＳ５０１において、Ｗｅｂページ状態テーブル２１の内容を読み出し、ダウンロード対象のＷｅｂサーバに属するＷｅｂページの中で、次回アクセス時刻２３が最小のものを１つ選択する。
【００５１】
ＵＲＩ２２は、先頭部分にＷｅｂサーバ名を含むので、Ｗｅｂページ状態テーブル２１をＵＲＩ２２の文字列順に編成することなどにより、容易にＷｅｂサーバに対応するＷｅｂページを検索することができる。また、例えば、特開２００３−２７１６７０の図１５におけるＵＲＬインデックスと同様の補助的なデータ構造を用いて、ＷｅｂページのＵＲＩをＷｅｂサーバ名と次回アクセス時刻の順に格納しておいてもよい。
【００５２】
次に、ステップＳ５０２において、当該Ｗｅｂサーバにアクセスし、当該Ｗｅｂページのダウンロードを行う。このステップは、ＤＮＳプロトコルによるＷｅｂサーバ名からＩＰアドレスへの変換や、ＨＴＴＰプロトコルによるＵＲＩの指定および内容の取得を含む。続いて、ステップＳ５０３において、ダウンロードしたＷｅｂページの内容をＵＲＩと対応付けて、Ｗｅｂページ内容記憶手段３に格納する。
【００５３】
ステップＳ５０２のＤＮＳやＨＴＴＰ通信においてエラーが発生した場合には、当該エラーを記録する。さらに、ステップＳ５０４において、当該Ｗｅｂページに対するＷｅｂページ再アクセススケジューリング手段６の処理を起動する。
【００５４】
図６は、本発明の実施の形態１におけるＷｅｂページ再アクセススケジューリング手段６の動作を示すフローチャートである。Ｗｅｂページ再アクセススケジューリング手段６は、ステップＳ６０１において、処理対象Ｗｅｂページに対応するＷｅｂページ状態テーブル２１の項目の内、アクセス時刻およびアクセス状態の対からなるアクセスの履歴データを１段シフトし、アクセス回数２４に１を加える。
【００５５】
アクセス履歴のシフトは、アクセス回数２４の元の値ｍがＮより小さい場合は、第ｍ＋１アクセス時刻と第ｍ＋１アクセス状態にそれぞれ第ｍアクセス時刻と第ｍアクセス状態を、第ｍアクセス時刻と第ｍアクセス状態にそれぞれ第ｍ−１アクセス時刻と第ｍ−１アクセス状態を、・・・、第２アクセス時刻２８（２）と第２アクセス状態２９（２）にそれぞれ最終アクセス時刻２６と最終アクセス状態２７を設定することにより実現される。
【００５６】
ただし、ｍが０の場合は、何もしない。また、アクセス回数２４の元の値ｍがＮに等しいか、それより大きい場合は、第Ｎアクセス時刻２８（Ｎ）と第Ｎアクセス状態２９（Ｎ）にそれぞれ第Ｎ−１アクセス時刻２８（Ｎ−１）と第Ｎ−１アクセス状態２９（Ｎ−１）を、・・・、第２アクセス時刻２８（２）と第２アクセス状態２９（２）にそれぞれ最終アクセス時刻２６と最終アクセス状態２７を設定する。
【００５７】
次に、ステップＳ６０２において、最終アクセス時刻２６に現在時刻を設定する。さらにステップＳ６０３において、ダウンロードしたＷｅｂページの内容にハッシュ関数を適用して求めたハッシュ値と最終ハッシュ値２５を比較し、両者が一致しなければ「更新検知」を、一致すれば「更新非検知」を最終アクセス状態２７に設定し、求めたハッシュ値を最終ハッシュ値２５に設定する。
【００５８】
ただし、初回アクセス後は（エラーが発生しなかった場合は）、最終アクセス状態２７を「更新検知」とし、ダウンロードがエラーとなった場合は、最終アクセス状態２７を「エラー」に設定する。
【００５９】
続くステップＳ６０４では、新たなアクセス履歴による予測に基づいて、次回アクセス時刻２３を設定する。一般に、Ｗｅｂページの更新は、ポアソン過程などの確率事象としてモデル化できることが知られている（例えば、文献“Ｅｓｔｉｍａｔｉｎｇ  ｆｒｅｑｕｅｎｃｙ  ｏｆ  ｃｈａｎｇｅ”、ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｔｅｒｎｅｔ  Ｔｅｃｈｎｏｌｏｇｙ、ｖｏｌ．３、ｎｏ．３、２５６−２９０頁など）。
【００６０】
ポアソン過程に基づく最も単純なＷｅｂページ更新間隔の推定法は、期間をその間に発生したＷｅｂページ更新回数で割るというものである。具体的には、アクセス回数２４がＮに等しいか、それより大きい場合は、最終アクセス時刻２６と第Ｎアクセス時刻２８（Ｎ）の差を最終アクセス状態２７から第Ｎアクセス状態２９（Ｎ）の内、「更新検知」となっているものの数で割ったものとなる。
【００６１】
アクセス回数２４の値ｍがＮより小さい場合は、第ｍアクセス時刻および第ｍアクセス状態までを用いればよい。また、これ以外にも、前掲文献の付録Ｃに述べられているような最尤法に基づく推定を用いることもできる。次回アクセス時刻２３は、当該Ｗｅｂページの更新間隔推定値を現在時刻に加えた値などとして設定する。
【００６２】
なお、最近のアクセス状態において「エラー」が一定回数以上続いた場合は、当該Ｗｅｂページが消失するなどしてアクセスできなくなったものと判断し、以降、アクセス対象から除外するために、次回アクセス時刻２３に∞（無限大）を設定する。
【００６３】
最後に、ステップＳ６０５において、Ｗｅｂページ再アクセススケジューリング手段６は、処理対象Ｗｅｂページが属するＷｅｂサーバに対してＷｅｂサーバアクセススケジューリング手段７の処理を起動する。
【００６４】
次に、図７は、本発明の実施の形態１におけるＷｅｂサーバアクセススケジューリング手段７の動作を示すフローチャートである。はじめに、ステップＳ７０１において、処理対象Ｗｅｂサーバに属する全てのＷｅｂページについて（ただし、アクセス回数２４が０のものは除く）Ｗｅｂページ状態テーブル２１から次回アクセス時刻２３と最終アクセス時刻２６を読み出す。さらに、次回アクセス時刻２３と最終アクセス時刻２６との差であるアクセス間隔の逆数の総和を計算し、その値をＷｅｂサーバ状態テーブル１１の当該Ｗｅｂサーバに対応するＷｅｂサーバ負荷指標１５に設定する。
【００６５】
毎回全てのＷｅｂページに関する総和を計算する代わりに、Ｗｅｂページ再アクセススケジューリング手段６の起動前後における次回アクセス時刻２３と最終アクセス時刻２６の差を用い、Ｗｅｂサーバ負荷指標１５から次回アクセス時刻２３と最終アクセス時刻２６の差の古い値の逆数を引き、次回アクセス時刻２３と最終アクセス時刻２６の差の新しい値の逆数を加えることで、Ｗｅｂサーバ負荷指標１５を更新しても良い。また、次回アクセス時刻２３に∞が設定されているＷｅｂページに関しては、次回アクセス時刻２３と最終アクセス時刻２６の差の逆数は、０に設定することとする。
【００６６】
続いて、ステップＳ７０２において、更新後のＷｅｂサーバ負荷指標１５の値を０と比較し、０に等しければステップＳ７０３に進み、そうでなければステップＳ７０４に進む。ステップＳ７０３に進む場合は、当該Ｗｅｂサーバに属する全てのＷｅｂページについて、次回アクセス時刻２３が∞であり、収集対象のＷｅｂページが残っていないことを意味する。従って、この場合は、Ｗｅｂサーバ状態テーブル１１の当該Ｗｅｂサーバに対するダウンロード開始時刻１４を∞に、Ｗｅｂサーバ状態１３を「休止」に設定し、停止する。
【００６７】
一方、ステップＳ７０４に進んだ場合においては、当該Ｗｅｂサーバに属する全てのＷｅｂページについて、次回アクセス時刻２３の最小値を求め、現在時刻にあらかじめ決められた所定の定数であるＷｅｂサーバアクセス間隔下限値を加えた値と比較する。前者が小さければステップＳ７０６に進み、そうでなければステップＳ７０５に進む。
【００６８】
Ｗｅｂサーバアクセス間隔下限値は、アクセス負荷への配慮の観点から設定するルールであり、例えば、１０秒に設定すると、同一Ｗｅｂサーバに対する異なるＷｅｂページのアクセスは、１０秒以上間隔を空けるということを意味する。この値は、全てのＷｅｂサーバに対して共通の値を用いてもよく、また、Ｗｅｂサーバに属するＷｅｂページの数に応じて、いくつかの値を切り替えて用いてもよい。
【００６９】
ステップＳ７０５に進む場合には、Ｗｅｂページ再アクセススケジューリングに従うことでＷｅｂサーバアクセス間隔への配慮が自動的になされることを意味している。従って、当該Ｗｅｂサーバに関する次回アクセス時刻２３の最小値をＷｅｂサーバ状態テーブル１１のダウンロード開始時刻１４に設定し、ステップＳ７０９に進む。
【００７０】
一方、ステップＳ７０６に進んだ場合には、さらに、Ｗｅｂサーバ負荷指標１５の逆数とＷｅｂサーバアクセス間隔下限値との比較を行い、前者が小さければステップＳ７０８に、そうでなければステップＳ７０７に進む。
【００７１】
ステップＳ７０７に進む場合は、個々のＷｅｂページの次回アクセス時刻は、正確に守られないものの、個々のＷｅｂページの最適なアクセス間隔に従うことは可能であり、次第にＷｅｂページ再アクセススケジューリングとの乖離を小さくできることを示している。ここでは、現在時刻にＷｅｂサーバ負荷指標１５の逆数を加えたものを、Ｗｅｂサーバ状態テーブル１１のダウンロード開始時刻１４に設定し、ステップＳ７０９に進む。
【００７２】
一方、ステップＳ７０８に進む場合は、当該Ｗｅｂサーバが過負荷状態であり、Ｗｅｂサーバのアクセス間隔への配慮と個々のＷｅｂページの最適なアクセス間隔の実現が両立しないことを表している。ここでは、アクセス間隔への配慮を優先し、現在時刻にＷｅｂサーバアクセス間隔下限値を加えたものを、Ｗｅｂサーバ状態テーブル１１のダウンロード開始時刻１４に設定し、ステップＳ７０９に進む。
【００７３】
そして、最終的に、ステップＳ７０９では、当該Ｗｅｂサーバに対応するＷｅｂサーバ状態テーブル１１のＷｅｂサーバ状態１３を「ダウンロード待ち」に設定し、停止する。
【００７４】
次に、本願発明の技術的特徴の１つであるＷｅｂサーバ負荷指標について具体的に説明する。図８は、本発明の実施の形態１におけるＷｅｂサーバ負荷指標１５の意味付けを説明するための概念図である。説明を簡略化するために、図８においては、あるＷｅｂサーバｉに４つのＷｅｂページｉ１〜ｉ４が属している場合を示しており、各Ｗｅｂページの推定更新間隔をＴｉ１〜Ｔｉ４として示している。
【００７５】
ある長い期間Ｔを考えると、この期間にＷｅｂサーバアクセス間隔下限値ｃｉでＷｅｂサーバｉにアクセスした時にダウンロード可能な延べＷｅｂページ数Ｍは、下式（１）で与えられる。
【００７６】
【数１】
2008186157.tif 000003
【００７７】
一方、この期間の各Ｗｅｂページｉｊ（図８においてはｊ＝１〜４に相当）の更新回数をｍｉｊとすると、全てのＷｅｂページの更新内容をダウンロードするには、下式（２）で示される回数のダウンロードが必要である。
【００７８】
【数２】
2008186157.tif 000004
【００７９】
上式（２）で、過負荷状態においては、上式（２）の右辺として求まる値がダウンロード可能な延べＷｅｂページ数Ｍを上回るので、下式（３）の関係となる。
【００８０】
【数３】
2008186157.tif 000005
【００８１】
上式（３）における（  ）内の値は、Ｗｅｂサーバｉに含まれる全てのＷｅｂページのアクセス間隔の逆数の総和を示している。従って、上述したＷｅｂサーバｉのＷｅｂサーバ負荷指標１５を表していることとなり、先のステップＳ７０６に示す判定により過負荷状態を検出できることとなる。ここで、上式（１）あるいは（３）におけるＷｅｂサーバアクセス間隔下限値ｃｉの逆数１／ｃｉは、Ｗｅｂサーバに対するアクセス間隔の過負荷状態を判断するための所定許容値に相当する。
【００８２】
次に、図９は、本発明の実施の形態１におけるハイパーリンク抽出手段８の動作を示すフローチャートである。はじめに、ステップＳ９０１で、Ｗｅｂページ内容記憶手段３に新たなＷｅｂページ内容が追加されるのを待つ。
【００８３】
新たなＷｅｂページ内容が追加されると、ステップＳ９０２において、当該Ｗｅｂページ内容からＨＴＭＬのＡ（アンカー）タグなどで記述されたハイパーリンクを抽出する。次に、ステップＳ９０３では、当該Ｗｅｂページ内容から抽出された全てのハイパーリンクが処理されたかどうか判定し、全て処理済みであれば、ステップＳ９０１に戻り、未処理のものがあれば、ステップＳ９０４以下の処理を適用する。
【００８４】
ステップＳ９０４において、ハイパーリンクが指すＵＲＩに対応するＷｅｂページが既にＷｅｂページ状態テーブル２１に存在しているかどうかを判断する。存在している場合は、ステップＳ９０３に戻って残りのハイパーリンクの処理を行う。
【００８５】
Ｗｅｂページ状態テーブル２１に存在していない新規ＵＲＩについては、ステップＳ９０５で、新たなエントリをＷｅｂページ状態テーブル２１に追加する。追加するエントリにおいては、ＵＲＩ２２を当該ＵＲＩに、次回アクセス時刻２３を現在時刻に、アクセス回数２４を０に、それぞれ設定する。
【００８６】
続いて、ステップＳ９０６で、当該ＵＲＩが属するＷｅｂサーバが既にＷｅｂサーバ状態テーブル１１に存在しているかどうかを判断する。存在している場合は、ステップＳ９０８に進む。
【００８７】
一方、存在していない場合は、ステップＳ９０７において、新たなエントリをＷｅｂサーバ状態テーブル１１に追加してステップＳ９０８に進む。追加するエントリにおいては、Ｗｅｂサーバ名１２を当該Ｗｅｂサーバの名前に、Ｗｅｂサーバ状態１３を「休止」に、Ｗｅｂサーバ負荷指標１５を０に、それぞれ設定する。
【００８８】
次に、ステップＳ９０８においては、当該ＷｅｂサーバのＷｅｂサーバ状態１３が「休止」であるかどうか判定する。Ｗｅｂサーバ状態１３が「休止」でなければ、ステップＳ９０３に戻って、残りのハイパーリンクの処理を続ける。一方、Ｗｅｂサーバ状態１３が「休止」であれば、ステップＳ９０９に進み、Ｗｅｂサーバ状態１３を「ダウンロード待ち」に、ダウンロード開始時刻１４を現在時刻に設定して、ステップＳ９０３に戻る。
【００８９】
以上のように、実施の形態１によれば、同一のＷｅｂサーバに含まれる複数のＷｅｂページのそれぞれのアクセス間隔に基づいて、Ｗｅｂサーバ毎の負荷指標を計算するので、クローラ側の性能に余裕がある場合でも、個々のＷｅｂサーバに過大なアクセス負荷を及ぼさないようにすることができる。
【００９０】
さらに、過負荷状態を防ぐために、Ｗｅｂサーバアクセス間隔の下限値を増加させる場合と比べると、過負荷状態にないＷｅｂサーバには影響が及ばないので、適切な間隔でＷｅｂページの再収集を行うことができる。
【００９１】
実施の形態２．
本実施の形態２では、先の実施の形態１における図７のステップＳ７０８に先立ち、新たな処理を追加する場合について説明する。図１０は、本発明の実施の形態２におけるＷｅｂサーバアクセススケジューリング手段７の新たな処理動作を示すフローチャートである。
【００９２】
図１０のステップＳ１００１は、図７のステップＳ７０６の条件が真となった場合、すなわち、当該Ｗｅｂサーバが過負荷状態と判定された場合に、Ｗｅｂサーバアクセススケジューリング手段７により実行される。ここでは、当該Ｗｅｂサーバに属する全てのＷｅｂページについて、Ｗｅｂページ状態テーブル２１の次回アクセス時刻２３を修正する。
【００９３】
より具体的には、Ｗｅｂページアクセス間隔、すなわち、次回アクセス時刻２３と最終アクセス時刻２６との差に対して、一律の定数をかけて修正を施す。ここでは、一例として、この一律の定数を、Ｗｅｂサーバアクセス間隔下限値とＷｅｂサーバ負荷指標との積である下式（４）とする。
【００９４】
【数４】
2008186157.tif 000006
【００９５】
続いて、ステップＳ１００２において、修正された次回アクセス時刻２３を用いてＷｅｂサーバ負荷指標１５を再度計算し、設定する。その後の処理は、図７のステップＳ７０８以降と同様である。再度計算された新たなＷｅｂサーバ負荷指標１５は、Ｗｅｂサーバアクセス間隔下限値の逆数と等しくなる。
【００９６】
すなわち、ステップＳ１００１で一律の定数を掛けて、Ｗｅｂページアクセス間隔を一様に広げることにより、Ｗｅｂサーバ負荷指標の逆数がＷｅｂサーバアクセス間隔下限値と等しくなるようにし、過負荷状態の解消を図っている。ただし、上記の定数に上限を設けても良い。この場合は、Ｗｅｂサーバ負荷指標１５は、Ｗｅｂサーバアクセス間隔下限値の逆数より大きくなり、過負荷状態はこの時点では解消されていないこととなる。
【００９７】
以上のように、実施の形態２によれば、過負荷状態のＷｅｂサーバに対して、それぞれのＷｅｂページのアクセス間隔を、一律の定数を掛けて一様に修正し、過負荷状態を解消する手段を備える。この結果、例えば、各Ｗｅｂページの更新を１回置きに収集するなど、各Ｗｅｂページのアクセス間隔を一様に定数倍して長くすることにより過負荷状態の解消を図ることができ、過負荷状態にあるＷｅｂサーバからのＷｅｂページ再収集が無秩序になるのを防ぐことができる。
【００９８】
実施の形態３．
本実施の形態３では、先の実施の形態１における図７のステップＳ７０８に先立ち、上述の実施の形態２とは異なる新たな処理を追加する場合について説明する。図１１は、本発明の実施の形態３におけるＷｅｂサーバアクセススケジューリング手段７の新たな処理動作を示すフローチャートである。
【００９９】
図１１のステップＳ１１０１は、図７のステップＳ７０６の条件が真となった場合、すなわち、当該Ｗｅｂサーバが過負荷状態と判定された場合に、Ｗｅｂサーバアクセススケジューリング手段７により実行される。ここでは、当該Ｗｅｂサーバに属する全てのＷｅｂページについて、Ｗｅｂページ状態テーブル２１の次回アクセス時刻２３に一定値を加える修正を行う。
【０１００】
加える値としては、例えば、１日などを用いる。先の実施の形態２のステップＳ１００１においては、各Ｗｅｂページのアクセス間隔を定数倍して一様に修正したが、本実施の形態３では、各Ｗｅｂページの次回アクセスを一律の一定時間だけそれぞれ延期する。
【０１０１】
これにより、Ｗｅｂサーバ負荷指標への影響が大きい小アクセス間隔のＷｅｂページには大きな修正が働く一方で、大きなアクセス間隔を持つＷｅｂページへの影響を抑えることができる。このような修正は、例えば、更新された状態がより長く存続するＷｅｂページにおいては、１回の更新を見逃すことの影響が大きいと考えられる場合があるために施される。
【０１０２】
続いて、ステップＳ１１０２において、修正された次回アクセス時刻２３を用いてＷｅｂサーバ負荷指標１５を再度計算し、設定する。先の実施の形態２と異なり、修正後のＷｅｂサーバ負荷指標を特定の値にすることは困難である。このため、続くステップＳ１１０３で、Ｗｅｂサーバ負荷指標が十分小さな値になり、過負荷状態が解消されたかどうかを判断する。
【０１０３】
Ｗｅｂサーバ負荷指標の目標値としては、例えば、Ｗｅｂサーバアクセス間隔下限値の逆数やそれに近い値を用いることができる。過負荷状態が解消された場合は、図７のステップＳ７０８以降の処理に進む。一方、過負荷状態が解消されていない場合は、ステップＳ１１０１に戻り、さらに、次回アクセスを延期した後に、ステップＳ１１０２、Ｓ１１０３の処理を再度行う。
【０１０４】
以上のように、実施の形態３によれば、過負荷状態のＷｅｂサーバに対して、それぞれのＷｅｂページの次回アクセス時刻を、アクセス間隔に一律の一定時間を加算することにより一様に修正し、過負荷状態を解消する手段を備える。この結果、例えば、１日毎に更新されるＷｅｂページを１日延ばして２日毎に収集しつつ、１月毎に更新されるＷｅｂページは、２月ごとに収集するのではなく、１月＋１日のアクセス間隔として漏れなく収集するなど、過負荷状態にあるＷｅｂサーバからのＷｅｂページ再収集が無秩序になり収集結果の質が低下するのを防ぐことができる。
【０１０５】
実施の形態４．
本実施の形態４では、先の実施の形態１における図７のステップＳ７０８に先立ち、上述の実施の形態２、３とは異なる新たな処理を追加する場合について説明する。図１２は、本発明の実施の形態４におけるＷｅｂサーバアクセススケジューリング手段７の新たな処理動作を示すフローチャートである。
【０１０６】
図１２のステップＳ１２０１は、図７のステップＳ７０６の条件が真となった場合、すなわち、当該Ｗｅｂサーバが過負荷状態と判定された場合に、Ｗｅｂサーバアクセススケジューリング手段７により実行される。ここでは、当該Ｗｅｂサーバに属する全てのアクセス対象Ｗｅｂページについて、Ｗｅｂページ状態テーブル２１のＵＲＩ２２から部分文字列を取り出し、出現頻度が高いものを上位から抽出する。
【０１０７】
ここで、アクセス対象Ｗｅｂページとは、次回アクセス時刻２３が∞でないものを指す。また、ＵＲＩの部分文字列とは、例えば、ｈｔｔｐ：／／Ｗｅｂサーバ名／ディレクトリ名１／ディレクトリ名２／ファイル名で与えられるＵＲＩに対して、ｈｔｔｐ：／／Ｗｅｂサーバ名／ディレクトリ名１／やｈｔｔｐ：／／Ｗｅｂサーバ名／ディレクトリ名１／ディレクトリ名２／など、末尾文字列をディレクトリ単位で除去したものを指す。
【０１０８】
あるディレクトリ下に多数のファイルやサブディレクトリがある場合、それらに対応するＵＲＩは、共通の部分文字列を持つため、当該共通部分文字列の出現頻度は高くなる。ただし、ディレクトリ名２までが高い頻度で出現する場合、その上位のディレクトリ名１も、それ以上の頻度で出現することになるため、なるべく長い共通部分文字列を抽出するようにする。
【０１０９】
この処理は、Ｗｅｂページ状態テーブル２１をＵＲＩ２２の文字列順に編成しておくことで、Ｗｅｂページ状態テーブル２１の順次スキャンにより容易に実現することができる。また、アクセス間隔の短い順に編成されたＷｅｂページの順番に基づいて除外対象となるＷｅｂページを選択することにより、Ｗｅｂサーバ負荷への影響が大きいＷｅｂページに対し、優先的にアクセス対象からの除外を実施することができる。
【０１１０】
続いて、ステップＳ１２０２において、上位の高頻度部分文字列として抽出された部分文字列がＵＲＩ２２に含まれるＷｅｂページについて、一部を除いて次回アクセス時刻２３に∞を設定し、アクセス対象から除外する。これにより、形式が類似するファイルが多数置かれたディレクトリ等に対し、その全てを収集するのではなく、一部を代表例として収集するようにすることができる。この結果、収集対象Ｗｅｂページ数自体を低減し、Ｗｅｂサーバ負荷指標の抑制を図ることができる。
【０１１１】
例えば、ｎｅｗｓディレクトリ下に日付をファイル名に含む多数のファイルが置かれている場合は、過去の全てのニュースを収集する代わりに、最近のニュース、すなわち、文字列順で後方に位置するＵＲＩだけを残すことで、Ｗｅｂサーバ負荷の抑制と収集情報の有用性を両立することができる。
【０１１２】
次に、ステップＳ１２０３において、修正された次回アクセス時刻２３を用いてＷｅｂサーバ負荷指標１５を再度計算し、設定する。修正後のＷｅｂサーバ負荷指標を特定の値にすることは困難であるため、先の実施の形態３と同様に、続くステップＳ１２０４で、Ｗｅｂサーバ負荷指標が十分小さな値になり、過負荷状態が解消されたかどうかを判断する。
【０１１３】
過負荷状態が解消された場合は、図７のステップＳ７０８以降の処理に進む。一方、過負荷状態が解消されていない場合は、ステップＳ１２０１に戻り、ステップＳ１２０２〜Ｓ１２０４の処理を再度行う。
【０１１４】
以上のように、実施の形態４によれば、過負荷状態のＷｅｂサーバに対して類似のＵＲＩを持つ多数のＷｅｂページを出現頻度の高い代表例に絞り、残りを収集対象から除外することで過負荷状態を解消する手段を備える。この結果、過負荷状態を起こさない規模で最適なアクセス間隔でのＷｅｂページ再収集を実施することができ、収集結果の有用性を高めることができる。
【０１１５】
なお、以上の実施の形態４では、ＵＲＩの部分文字列としてディレクトリ単位での分割を説明したが、符号？に続き、符号＆で区切られた「パラメータ名＝値」の形式のパラメータを含むＵＲＩに対しては、パラメータ名毎の出現頻度を用いることも有効である。これにより、例えば、製品番号などがパラメータ値に対応している場合に、その一部をサンプルとして収集するという効果が得られる。
【０１１６】
また、こうしたパラメータの一部には、Ｗｅｂサイト側で利用者の状態を管理するためにＷｅｂサーバへの接続毎に付与されるセッションＩＤなども含まれる。クローラは、アクセス間隔を空けてＷｅｂサーバに接続するため、毎回異なるセッションＩＤが付与され、内容が同一であるにも関わらず異なるＵＲＩが生成されることがあり得る。
【０１１７】
セッションＩＤは、ＵＲＩの形式上、容易に判別できるものもあるが、そうでないものも多い。このような場合には、セッションＩＤの一部のみをサンプルとして残すことで、同様の内容を多数収集することを避けることができる。
【０１１８】
また、図１２では、ＵＲＩ文字列の情報のみを用いたが、部分文字列の出現頻度を、対応するＷｅｂページのアクセス間隔で重み付けしてもよい。これにより、アクセス間隔が短いＷｅｂページを多く含み、Ｗｅｂサーバ負荷への影響が大きいＷｅｂページ群に対し、優先的にアクセス対象からの除外を実施することができる。
【０１１９】
また、共通部分文字列以外のＵＲＩ文字列が数字のみ、または同一文字数などの特徴を有するＷｅｂページ群に対し、優先的にアクセス対象からの除外を実施することもできる。
【０１２０】
また、内容またはそのハッシュ値が共通するものが多いＷｅｂページ群に対し、優先的にアクセス対象からの除外を実施することもできる。あるいは、内容またはそのハッシュ値が重複するＷｅｂページをダウンロード対象から除外することもできる。
【０１２１】
また、上述の実施の形態２〜４は、組み合わせて実現することも可能である。例えば、実施の形態３と実施の形態４との組み合わせでは、図１１のステップＳ１１０３において、Ｗｅｂサーバ負荷指標がＷｅｂサーバアクセス間隔下限値の逆数に達する前にループを打ち切り、図１２のステップＳ１２０１に進むことが考えられる。これにより、小さな範囲で次回アクセス時刻の遅延を適用し、それでも過負荷状態が解消しなかった場合には、Ｗｅｂページの除外を実施することで、Ｗｅｂページ再収集間隔とＷｅｂ再収集範囲への影響を制御することが可能となる。
【図面の簡単な説明】
【０１２２】
【図１】本発明の実施の形態１におけるＷｅｂページ再収集方式の構成図である。
【図２】本発明の実施の形態１におけるＷｅｂサーバ状態記憶手段に記憶されるＷｅｂサーバ状態テーブルの形式を示す図である。
【図３】本発明の実施の形態１におけるＷｅｂページ状態記憶手段に記憶されるＷｅｂページ状態テーブルの形式を示す図である。
【図４】本発明の実施の形態１におけるディスパッチ手段の動作を示すフローチャートである。
【図５】本発明の実施の形態１におけるＷｅｂページダウンロード手段の動作を示すフローチャートである。
【図６】本発明の実施の形態１におけるＷｅｂページ再スケジューリング手段の動作を示すフローチャートである。
【図７】本発明の実施の形態１におけるＷｅｂサーバアクセススケジューリング手段の動作を示すフローチャートである。
【図８】本発明の実施の形態１におけるＷｅｂサーバ負荷指標の意味付けを説明するための概念図である。
【図９】本発明の実施の形態１におけるハイパーリンク抽出手段の動作を示すフローチャートである。
【図１０】本発明の実施の形態２におけるＷｅｂサーバアクセススケジューリング手段の新たな処理動作を示すフローチャートである。
【図１１】本発明の実施の形態３におけるＷｅｂサーバアクセススケジューリング手段の新たな処理動作を示すフローチャートである。
【図１２】本発明の実施の形態４におけるＷｅｂサーバアクセススケジューリング手段の新たな処理動作を示すフローチャートである。
【符号の説明】
【０１２３】
１  Ｗｅｂサーバ状態記憶手段、２  Ｗｅｂページ状態記憶手段、３  Ｗｅｂページ内容記憶手段、４  ディスパッチ手段、５  Ｗｅｂページダウンロード手段、６  Ｗｅｂページ再アクセススケジューリング手段、７  Ｗｅｂサーバアクセススケジューリング手段、８  ハイパーリンク抽出手段。
【図１】
2008186157.tif 000007
【図２】
2008186157.tif 000008
【図３】
2008186157.tif 000009
【図４】
2008186157.tif 000010
【図５】
2008186157.tif 000011
【図６】
2008186157.tif 000012
【図７】
2008186157.tif 000013
【図８】
2008186157.tif 000014
【図９】
2008186157.tif 000015
【図１０】
2008186157.tif 000016
【図１１】
2008186157.tif 000017
【図１２】
2008186157.tif 000018