(57)【要約】  【課題】  差分送信で同期をとることができなくなった場合にも少ないトラフィックで木構造データ間の同期をとる。  【解決手段】  収集拠点１０において巡回が開始されると、探索順序記憶部１０１の探索順序およびチェックポイント記憶部１０２のチェックポイントを参照して対象ノード決定部１０３が対象ノードを決定する。つぎにメンバリスト作成部１０５が対象ノードについて、リンクテーブルを参照してメンバリストをそれぞれ生成する。つぎにメンバリストがメンバリスト記憶部１０６に記憶されて、チェックポイントも更新される。巡回が終了すると、メンバリスト群がセンタ２０に送信される。センタ２０においては、巡回ごとにメンバリスト群を受信し、これに基づいて対応するサブ木構造の木構造データ部分を更新する。【選択図】  図１
2005310008.tif 000002
【特許請求の範囲】
【請求項１】
第１サイトにて保持され、または生成される木構造データに第２サイトに保持されている木構造データを同期させる木構造データ同期装置において、上記第１サイトにて保持され、または生成される木構造データの探索順序に従って当該木構造データを構成するノードの部分集合を選択し、選択した部分集合に含まれるノードの子ノード情報を、部分集合単位で上記第２サイトに伝送し、上記子ノード情報に基づいて上記第２サイトに保持されている木構造データを更新する木構造データ同期装置。
【請求項２】
上記第１サイトに保持されている木構造データの探索順序に従って当該木構造データの差分データを取得する第１の探索モードと、上記第１サイトに保持されている木構造データの探索順序に従って当該木構造データを構成するノードの部分集合を選択し、選択した部分集合に含まれるノードの子ノード情報を、部分集合単位で取得する第２の探索モードを実行し、上記第２の探索モードの前後で上記第１の探索モードを実行して、取得した差分情報および子ノード情報を上記第２サイトに伝送する請求項１記載の木構造データ同期装置。
【請求項３】
上記第１サイトに保持されている木構造データはハイパーテキスト構造から導出したものである請求項１または２記載の木構造データ同期装置。
【請求項４】
上記探索順序は幅優先探索法もしくは深さ優先探索法による請求項１、２または３記載の木構造データ同期装置。
【請求項５】
木構造データを保持または生成する第１情報処理装置と、上記第１情報処理装置が保持または生成する木構造データに同期させるべき木構造データを保持する第２情報処理装置との間で木構造データの同期をとる木構造データ同期装置において、
上記第１情報処理装置において、木構造データの探索順序に従って当該木構造データを構成するノードの部分集合を決定する対象ノード決定手段と、
上記第１情報処理装置において、上記対象ノード選択手段により選択された各ノードの子ノード情報を取得する子ノード情報取得手段と、
上記子ノード情報取得手段で取得した子ノード情報を上記第２情報処理装置に送信する子ノード情報送信手段とを有し、
上記第２情報処理装置は上記子ノード情報により上記第２情報処理装置に保持されている木構造データを更新し、上記対象ノード決定手段は上記部分集合の範囲を上記探索順序に従ってシフトしていくことを特徴とする木構造データ同期装置。
【請求項６】
木構造データを保持または生成する第１情報処理装置と、上記第１情報処理装置が保持または生成する木構造データに同期させるべき木構造データを保持する第２情報処理装置と、上記第１情報処理装置および上記第２情報処理装置の間で木構造データの同期をとる木構造データ同期装置とを具備する木構造データ処理システムにおいて、
上記第１情報処理装置において、木構造データの探索順序に従って当該木構造データを構成するノードの部分集合を決定する対象ノード決定手段と、
上記第１情報処理装置において、上記対象ノード選択手段により選択された各ノードの子ノード情報を取得する子ノード情報取得手段と、
上記子ノード情報取得手段で取得した子ノード情報を上記第２情報処理装置に送信する子ノード情報送信手段とを有し、
上記第２情報処理装置は上記子ノード情報により上記第２情報処理装置に保持されている木構造データを更新し、上記対象ノード決定手段は上記部分集合の範囲を上記探索順序に従ってシフトしていくことを特徴とする木構造データ処理システム。
【請求項７】
第１サイトにて保持され、または生成される木構造データに第２サイトに保持されている木構造データを同期させる木構造データ同期方法において、上記第１サイトにて保持され、または生成される木構造データの探索順序に従って当該木構造データを構成するノードの部分集合を選択し、選択した部分集合に含まれるノードの子ノード情報を、部分集合単位で上記第２サイトに伝送し、上記子ノード情報に基づいて上記第２サイトに保持されている木構造データを更新する木構造データ同期方法。
【請求項８】
第１サイトにて保持され、または生成される木構造データに第２サイトに保持されている木構造データを同期させる木構造データ同期用コンピュータプログラムにおいて、上記第１サイトに保持され、または生成される木構造データの探索順序に従って当該木構造データを構成するノードの部分集合を選択ステップと、選択した部分集合に含まれるノードの子ノード情報を、部分集合単位で上記第２サイトに伝送するステップとをコンピュータに実行させるために用いられ、上記子ノード情報に基づいて上記第２サイトに保持されている木構造データが更新されることを特徴とする木構造データ同期用コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数箇所に格納された同一の木構造データの同期をとる技術に関し、とくに、差分データによる同期では同一性が保持されなくなった場合に対処できるようにしたものである。
【背景技術】
【０００２】
本出願人は、拠点とセンターがあり、拠点では、ロボット（クローラ）で、階層構造に変換すべきウェブ文書を収集し、文書をノードとし参照やメンバシップをエッジとする木構造を構築し、収集の度に更新される前記木構造をセンターにも構築するために、前回送信したデータとの差分（削除、追加、更新）を送信することで、センターと拠点の双方で、矛盾のないように木構造を管理するシステムを提案している（特願２００３−３０５８８０。本件出願時、未公開）。この提案においては、クローリングして得られたハイパーリンク構造内を幅優先探索により各文書を探索し、文書の新規、更新、削除の状況を記述する文書テーブルとリンクの新規、継続存在、削除の状況等を記述するリンクテーブルとを生成し、この文書テーブルおよびリンクテーブルの異同に基づいて差分情報（更新、新規追加、削除等の操作と、その操作対象の文書のＩＤと親の文書のＩＤ）を生成し、これを同期先に転送して更新、新規追加、削除等の同期操作を行なうようにしている。この提案によれば、ウェブ文書に対応する木構造についても差分情報を取得することができ、同期に必要なトラフィックを削減することができる。
【０００３】
ところで、この提案を含む、差分情報に伝送による木構造データの同期処理において、差分情報の送信エラーが起きた場合や、木構造データのデータベースが破損し、過去のデータベースのスナップショットにリストアした場合に、双方の木構造に違いがおき、差分送信による木構造の同期ができなくなってしまう。
【０００４】
このような事態に少ない通信コストで対処することが望まれる。
【０００５】
なお、この発明と関連する特許文献としては以下のようなものがある。
【０００６】
特許文献１は、データベースの同期を取る際、マスターとスレーブの差異に相当する情報を一時保持するファイルを設け、スレーブ側で更新に失敗した場合はスレーブ側に書き込むべき情報を上記ファイルに書き込むことを提案している。この手法では、過去のデータベースのスナップショットからのリストアに起因する同期ずれに対処できない。
【０００７】
特許文献２は、スレーブ側に送信した情報を採番した上で記憶しておき、通信障害回復時にスレーブ側から最終受信情報番号を受け取り、それより後の情報を送信しなおすことを提案している。この手法でも、過去のデータベースのスナップショットからのリストアに起因する同期ずれに対処できない。また、送信側で送信データを記憶しておかねばならない。
【０００８】
特許文献３は、障害発生時、スレーブ側のデ−タをすべてマスター側に送信し、マスターで検出した差異をスレーブ側に送信することを提案している。この手法では、スレーブ側のデータを一時に全て送信しなければならないので、ネットワークの通信コストが高い。
【特許文献１】特開平５−８９０７２号公報
【特許文献２】特開２００１−４３１１９公報
【特許文献３】特第３２７４５９４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
この発明は、以上の事情を考慮してなされたものであり、差分データの伝送エラーやデータベースのリストアにより双方の木構造に違いがおき、差分送信による木構造の同期ができなくなってしまう場合でも確実に同期をとることができる木構造データ同期記述を提供することを目的としている。
【課題を解決するための手段】
【００１０】
この発明の構成例では、収集拠点において、所定の順序で、例えば幅優先探索法の順序で、更新されたノードの情報を送信する。送信するノードが、その順序において所定の順位数または座標（何番目）から所定数（何個）の範囲に該当するノードであった場合に、当該ノードの各々についてすべてのメンバのリストを送信する。センタは、メンバのリストを受信し、センタで管理する木構造またはグラフ構造と比較し、不足するメンバについては、該当する文書属性を追加する。更新が必要なメンバは更新し、余計なメンバは、削除する。所定のグラフ例えばハイパーテキスト構造のネットワークを木構造に変換して利用する場合に、もとのネットワークのグラフ構造を比較しても良い。
【００１１】
少しずつ、メンバの突合せを行うことで、過大な送信コストを消費せずに（本来の差分送信のねらいをはずさずに）、データベースの同期が狂ったときに、徐々に整合を可能にする。差分送信による同期方式に、メンバ全体の比較を少しずつ挿入して、突合せを行う。
【００１２】
この構成例では、差分送信により効率よく同期を図れるとともに、差分送信で対処できなくなった場合でもメンバ全体の同期を確実に実現できる。
【００１３】
さらに、この発明を説明する。
【００１４】
この発明の一側面によれば、上述の目的を達成するために、第１サイトに保持され、または生成される木構造データに第２サイトに保持されている木構造データを同期させる木構造データ同期装置において、上記第１サイトにて保持され、または生成される木構造データの探索順序に従って当該木構造データを構成するノードの部分集合を選択し、選択した部分集合に含まれるノードの子ノード情報を、部分集合単位で上記第２サイトに伝送し、上記子ノード情報に基づいて上記第２サイトに保持されている木構造データを更新するようにしている。
【００１５】
上記子ノード情報は孫ノード情報やさらに下位のノードの情報を含んでも良い。要するにサブ木構造を伝送できればよい。
【００１６】
なお、第１サイトでは、直接に木構造を管理するのではなく、例えば、ハイパーリンク構造の文書群等の、木構造以外のネットワーク、グラフ構造を管理し、これを木構造データに変換して第２サイトの木構造データと同期をとる場合もある。この発明は一時的に導出されて利用される木構造データにも適用がある。要するに、木構造データは、長期に渡り記憶管理されるものに限らず、一時的に生成されるものも含まれる。
【００１７】
この構成によれば、トラフィックに負担をかけることなく、差分送信で対処できなくなった場合でもメンバ全体の同期を確実に実現できる。
【００１８】
探索順序は例えば幅優先の順序であるが、これに限定されない。深さ優先の順序でも良いし、ノードの属性値でノード群をソートし、その順番によってもよい。但しあるノードＡについて、その子ノード情報を第２サイトに伝送し、第２サイト側で着き合わせを行う場合、そのノードＡについてはその突合せ以前に第２サイト側にも存在することが望ましいことを考慮すれば、木構造の親から子へ探索が行われる幅優先や深さ優先が探索順序としては望ましい。
【００１９】
部分集合は探索を行なうごとに少しずつシフトされる。前の探索の部分集合と後の探索の部分集合とが密に配置され、その間に何ら他のノードが入らないようにしても良いし、間を空けても良い。密に配置すれば、所定の探索が終了した後にはじめの部分集合の位置に選択部分集合が戻ってきたときにすべての木構造について満遍なく同期処理が行なわれたことを保証できる。
【００２０】
一度の探索で複数の部分集合を選択しても良い。
【００２１】
また、この構成において、上記第１サイトに保持されている木構造データの探索順序に従って当該木構造データの差分データを取得する第１の探索モードと、上記第１サイトに保持されている木構造データの探索順序に従って当該木構造データを構成するノードの部分集合を選択し、選択した部分集合に含まれるノードの子ノード情報を、部分集合単位で取得する第２の探索モードを実行し、上記第２の探索モードの前後で上記第１の探索モードを実行して、取得した差分情報および子ノード情報を上記第２サイトに伝送するようにしてもよい。
【００２２】
また、上記第１サイトに保持されている木構造データは、例えば、ハイパーテキスト構造から導出したものである。
【００２３】
なお、この発明は装置またはシステムとして実現できるのみでなく、方法としても実現可能である。また、そのような発明の一部をソフトウェアとして構成することができることはもちろんである。またそのようなソフトウェアをコンピュータに実行させるために用いるソフトウェア製品もこの発明の技術的な範囲に含まれることも当然である。
【００２４】
この発明の上述の側面および他の側面は特許請求の範囲に記載され以下実施例を用いて詳述される。
【発明の効果】
【００２５】
この発明によれば、差分送信による木構造の同期ができなくなってしまう場合でも確実に同期をとることができる。
【発明を実施するための最良の形態】
【００２６】
以下、この発明の実施例について説明する。
【実施例１】
【００２７】
まず、この発明の原理的な構成を採用する実施例１の木構造データ同期システムについて説明する。
【００２８】
図１は、実施例１の木構造データ同期システムを全体として示しており、図１において、収集拠点１０は、木構造データ１００を収集保持するものであり、この木構造データ１００にセンタ２０の木構造データ記憶部２０１の木構造データを同期させる。センタ２０はサーバ装置（図示しない）を保持し、内部または外部のクライアント装置（図示しない）からの木構造データ転送要求を受け付けて処理する。クライアント装置では、センタ２０から転送されてきた木構造データに基づいて木構造の表示を行い、ユーザにノード（例えば文書）の提示を行なう。なお、このシステムは典型的には例えば文書検索閲覧システムの一部として構成されるが、これに限定されない。
【００２９】
収集拠点１０が保持する木構造データ１００は、例えば、ハイパーテキスト構造の文書群（リンクの張られたウェブ文書群）を木構造に変換して管理するものであるが、ファイル管理システムの木構造であってもよい。以下では、便宜上、ハイパーテキスト構造の文書群を前提に説明する。
【００３０】
収集拠点１０には、探索順序記憶部１０１、チェックポイント記憶部１０２、対象ノード決定部１０３、チェックポイント更新部１０４、メンバリスト作成部１０５、メンバリスト記憶部１０６、メンバリスト送信部１０７が設けられている。
【００３１】
探索順序記憶部１０１は、木構造データ１００を幅優先探索方式で探索する場合、何番目にどのノードが探索されるかを記録したものである。探索順序記憶部に記憶される順序は、ウェブ文書群を木構造データに変換した後、図２に探索順序の矢印で示すように、上から下に探索を行なっていくことで得ることができる。幅優先探索は、端的にはつぎのようなものである。あるノードから始めて、そのノードに接続しているノードを全て調べてから、調べたノードに接続しているノードを次々に調べていく。一度探索したノードに出会ったら、そのノードは調査しない。
【００３２】
ウェブ文書のネットワークを木構造に変換する手法は、例えば、特開平６−３５６５７号公報に開示されているように、所定のノード（文書）、例えばウェブサーバのポータルの文書をルートに決定し、これに接続されるノードを子ノードとする。この際、所定のノードに到達するノードが複数ある場合、最初に到達したパスのノードとの関係でのみ子ノードとなり、それ以降に到達してパスのノードとの関係では参照ノードとなる。このように参照ノードを用いることによりハイパーテキスト構造のネットワークを木構造に変換できる。
【００３３】
このように変換された木構造データは例えば図３に示すようなリンクテーブルとして保持される。
【００３４】
チェックポイント記憶部１０２は前回の探索の終了時点のノードの位置（チェックポイントともいう）を保持するものである。
【００３５】
この例では、例えば、所定時刻の到来等のイベントの発生に基づいて探索を繰り返し、木構造情報を収集する。一回の探索では、ルートから順にすべてのノードまたは所定条件を満たすまでのノードを探索するのではなく、前回のチェックポイントから所定範囲のノードを探索する。所定範囲は例えば所定数であるが、所定時間に探索可能な個数でも良いし、要するに、一連の部分的なノードを探索するものであれば良い。
【００３６】
対象ノード決定部１０３はチェックポイント記憶部１０２のチェックポイントと探索順序記憶部１０１の探索順序とを参照して所定範囲のノードを決定する。例えば、図２にＰ０で示すチェックポイントから四角の範囲のノードを選択して探索対象とする。その次の探索では、チェックポイントはＰ１となり破線の四角で示す範囲が探索対象のノードとなる。以降順に探索対象を決定していき、最後の末端ノードの探索が終了したら、ルートにもどり探索を繰り返す。
【００３７】
チェックポイント更新部１０４は、探索ごとに最後の探索対象ノードの探索順序における位置を求め新たなチェックポイントとしてチェックポイント記憶部１０２に更新書き込みを行なう。
【００３８】
メンバリスト作成部１０５は、図３に示すリンクテーブルを参照し、探索中のノードをルートとするサブ木構造を表すメンバリストを生成する。メンバリストは、典型的には、図４に示すような注目ノード（探索中のノード）のＩＤとその子ノード（参照ノードも含む）のリストからなる。図４の例では１階層のサブ木構造であるが、２階層や３階層のサブ木構造でもよい。
【００３９】
メンバリスト作成部１０５は、当該探索の探索範囲分だけ作成されてメンバリスト記憶部１０６に記憶され、探索ごとにメンバリスト送信部１０７からセンタ２０のメンバリスト受信部２０３に送信される。
【００４０】
メンバリストは木構造全体のサブ木構造であり、探索ごとにチェックポイントをずらしてサブ木構造を作成して送信することにより、所定回数だけ探索を行なえば木構造全体の木構造データをセンタ２０に送信することができる。
【００４１】
なお、この例では、１回の探索の探索範囲と次の探索の探索範囲とが密に接続されているが、最終的に木構造全体を漏らすことなく探索できるのであれば、間隔を置いて探索範囲をシフトしていってもよい。また、前回の探索範囲の後端部分が今回の探索範囲の前端部分と一部重複しても良い。要するに少しずつ木構造データを送信できるような態様であればどのようなものでもよい。
【００４２】
センタ２０には、木構造データ記憶部２０１、木構造データ更新部２０２、メンバリスト受信部２０３が設けられている。メンバリスト受信部２０３は収集拠点１０のメンバリスト送信部１０７から一定範囲のノードのサブ木構造である複数のメンバリストを受け取る。木構造データ更新部２０２は、メンバリスト受信部２０３から複数のメンバリストを受け取り、木構造全体のうちの該当するサブ木構造を当該複数のメンバリスト（サブ木構造）で置き換えて木構造データを更新し、木構造データ記憶部２０１に記憶されている木構造データの該当部分に対して更新書き込みする。複数回の探索についてメンバリスト群を受け取ることにより木構造全体を更新することができる。
【００４３】
図５は実施例１の動作を説明するものであり、図５において、収集拠点１０において探索が開始されると、探索順序およびチェックポイントを参照して対象ノードが決定される（Ｓ０１）。つぎに対象ノードについてメンバリストがそれぞれ生成される（Ｓ０２）。つぎにメンバリストがメンバリスト記憶部１０６に記憶されて、チェックポイントも更新される（Ｓ０３、Ｓ０４）。この後、メンバリスト群がセンタ２０に送信される（Ｓ０５）。
【００４４】
センタ２０においては、探索ごとにメンバリスト群を受信し、これに基づいて対応するサブ木構造の木構造データ部分を更新する（Ｓ０６、Ｓ０７）。
【００４５】
この実施例によれば、探索ごとに差分データでなくサブ木構造のデータを小分けにして転送するようにしているので、伝送エラーやリストア後の木構造の同期に伴う問題が解消され、また、トラフィックを混雑させることがない。
【００４６】
例えば、図６に示す例で、ウェブ文書のクローリングの結果、文書２が更新され、文書５が削除されたことが判明したとすると、差分データによる同期システムでは収集拠点１０からセンタ２０へ、「文書２が更新された」、「文書５が削除された」という情報が送信されるが、この実施例では、「文書３のメンバには文書６と文書７が存在する」、「文書４のメンバは存在しない」という、メンバリストが送信される。但し対象ノードとして文書３と文書４が選択されたものとする。センタ２０側において文書３のメンバが文書６と文書８であった場合には、「文書３のメンバには文書６と文書７が存在する」にあわせるために文書７を追加し、文書８を削除する。
【実施例２】
【００４７】
つぎに実施例２について説明する。この実施例２は、本出願人が提案し、先に説明した差分データによる同期（特願２００３−３０５８８０）とこの発明のサブ木構造による同期とを併せて採用したものである。
【００４８】
図７は実施例２の木構造データ同期システムの適用環境を示すものであり、この図において、企業Ａ、Ｂ、Ｃの社内ネットワーク３４ａ、３４ｂ、３４ｃおよび木構造情報提供サーバ３２がインターネット等の通信ネットワーク３０を介して接続されている。企業Ａ，Ｂ、Ｃの社員等はクライアント端末を用いて木構造情報提供サーバ３２にアクセスしてそこに保持されている木構造データを利用する。社内ネットワーク３４ａ、３４ｂ、３４ｃのウェブ文書群の木構造データを社内ネットワーク３４ａ、３４ｂ、３４ｃの木構造情報収集装置３６が収集して木構造情報提供サーバ３２に転送する。木構造情報提供サーバ３２が直接に社内ネットワーク３４ａ、３４ｂ、３４ｃのウェブ文書群を取得するのはセキュリティ構成や通信コストの点で問題があるので、社内ネットワーク３４ａ、３４ｂ、３４ｃの木構造情報収集装置３６が木構造データを収集し、木構造情報収集装置３６の当該木構造データと木構造情報提供サーバ３２との間で同期をとるようにしている。
【００４９】
図８は、木構造情報提供サーバ３２および木構造情報収集装置３６を模式的に説明するものであり、この図において、木構造情報収集装置３６は収集部３６２、更新用データ作成部３６４、記憶部４００を含んで構成されている。記憶部４００は、探索順序４０２、前回文書テーブル４０４、前回リンクテーブル４０６、差分情報判定テーブル４０８、収集後文書テーブル４１０、収集後リンクテーブル４１２、チェックポイント４１４を記憶している。
【００５０】
更新用データ作成部３６４は、サブ木構造（メンバリスト）および差分データを作成して出力するものである。この例では、実施例１と同様に探索ごとに図２の実線や破線の矩形の範囲のノードについてメンバリストを作成して残りの部分については差分データを作成する。例えば、図２のルートあるいは所定位置から幅優先探索法で探索を開始し、ノードの差分データを作成していき、チェックポイントのノードに遭遇したら差分データの作成に代えてメンバリストの作成を行い、予め定められた所定範囲にわたりメンバリストの作成が終了したら、その位置から差分データの作成を再開する。適宜、探索の終了条件が満たされたら探索を終了して差分データやメンバリストを木構造情報提供サーバ３２側に同期のために伝送する。
【００５１】
更新用データは、メンバリストおよび差分データからなる。
【００５２】
木構造情報提供サーバ３２は、木構造データ３２４を記憶する木構造データ記憶部３２２、クライアントからの木構造データ送信要求等を処理するクライアント要求処理部３２６、木構造更新部３２８等を含んで構成されている。木構造更新部３２８は更新用データを木構造情報収集装置３６から受信して木構造データ３２４を更新する。更新用データの内メンバリストによる更新は実施例１と同様である。差分データを利用した更新については後述する。
【００５３】
クライアント装置３８から木構造要求３８０が木構造情報提供サーバ３２に送信されると、これに応じて木構造データが木構造情報提供サーバ３２からクライアント装置３８に転送される。
【００５４】
図９は、実施例２の動作を説明するものであり、この図において、木構造情報収集装置３６において巡回（クローリング）が開始され、文書およびリンクの収集を行なう（Ｓ１０）。収集結果を利用して更新用データ（メンバリストおよび差分データ）を作成して木構造情報提供サーバ３２に送信する（Ｓ１２、Ｓ１４）。巡回は、探索順序４０２を参照して行なわれ、更新用データのメンバリンクのモードと差分データのモードの切替はチェックポイントを参照して行なわれる。メンバリストは収集後リンクテーブル４１２を参照して作成され、差分データは、前回文書テーブル４０４、前回リンクテーブル４０６、収集後文書テーブル４１０、収集後リンクテーブル４１２、差分情報判定テーブル４０８を参照して作成される。
【００５５】
図１１は前回文書テーブル４０４を示し、図１２は収集後文書テーブル４１０を示す。その間を比較することにより、文書の削除、更新、新規追加を判別できる。
【００５６】
図１３は前回リンクテーブル４０６を示し、図１４は収集後リンクテーブル４１２を示す。なお、最短パスは実体のある子ノードである（それ以外は参照ノード、ショートカットである）。
【００５７】
差分データ作成部３６４は収集後リンクテーブル４１０に保持されたリンクをエッジとし、収集後文書テーブル４１２に保持された文書をノードとするハイパーリンク構造を幅優先探索で探索する。探索中はそれまでに探索した文書数をカウントする。探索中、このカウントした値がチェックポイント４１４にて定まるメンバリスト作成範囲内ならば、差分データ作成部はメンバリストのモードに入り、探索中の文書についてそのメンバリストを作成し更新用データとする。カウントした値がメンバリスト作成範囲外ならば、差分データ作成部は差分データモードに入り、次のように木構造の差分データを作成して更新用データとする。
【００５８】
図１５、図１６、図１７および図１８は差分情報判定テーブル（場合分けして各図ごとに示す）を示す。文書の状態変化およびリンクの状態変化を前回文書テーブル４０４、前回リンクテーブル４０６、収集後文書テーブル４１０、収集後リンクテーブル４１２から取得して、これを図１５、図１６、図１７および図１８の差分情報判定テーブルに当てはめて図１９に示す差分データを取得する。
【００５９】
木構造差分データを木構造情報提供サーバ３２に送信した後は、つぎの巡回に備えて、図２０の置き換え規則を収集後のテーブルに適用して、図２１および図２２にそれぞれ示すように、新たに前回文書テーブルおよび前回リンクテーブルを準備する。
【００６０】
この実施例によれば、１回の幅優先探索で差分データとメンバリストのモードとを切り替えることにより、差分更新による効率的な同期が可能となるとともに、送信エラーが起きた場合や、データベースが破損し、過去のデータベースのスナップショットにリストアした状態でも、差分更新によりデータベースの同期を行う際に、各ノードについて、双方のデータベースのメンバの突合せが少しずつ行なわれ、拠点側のデータベースに合わせる形で、センタ側の木構造が修復される。差分送信だけの場合に見られるような信頼性の低さを補い、かつ、全数送信に見られるような多大なトラフィックを要求することなく、効率的で、高速に収集対象サーバの更新情報を、センターに送信できる。
【００６１】
なお、この発明は上述の実施例に限定されるものではなくその趣旨を逸脱しない範囲で種々変更が可能である。例えば、上述の例では１回の探索に一まとまりのノードについてサブ木構造データを送信するようにしたが、複数のまとまりのサブ木構造データを１回の探索で送信するようにしても良い。また、逆に、各探索でサブ木構造データを送信するのではなく、複数の探索に１回の割合で、１つまたは複数のまとまりのサブ木構造データを伝送するようにしても良い。また、上述の例ではハイパーテキスト構造の文書群を前提に説明したが、広く木構造データの同期に適用できる。
【図面の簡単な説明】
【００６２】
【図１】この発明の実施例１の構成を全体として示すブロック図である。
【図２】実施例１の探索順の例を説明する図である。
【図３】実施例１のリンクテーブルの例を説明する図である。
【図４】実施例１のメンバリストを説明する図である。
【図５】実施例１の動作の概略を説明するフローチャートである。
【図６】実施例１による同期の例を説明する図である。
【図７】この発明に実施例２の適用環境を説明する図である。
【図８】実施例２の要部構成を示すブロック図である。
【図９】実施例２の動作の概略を説明するフローチャートである。
【図１０】実施例２の探索順序の例を説明する図である。
【図１１】実施例２の前回文書テーブルの例を説明する図である。
【図１２】実施例２の収集後文書テーブルの例を説明する図である。
【図１３】実施例２の前回リンクテーブルの例を説明する図である。
【図１４】実施例２の収集後リンクテーブルの例を説明する図である。
【図１５】実施例２の差分情報判定テーブルの一部の例を説明する図である。
【図１６】実施例２の差分情報判定テーブルの他の一部の例を説明する図である。
【図１７】実施例２の差分情報判定テーブルの更に他の一部の例を説明する図である。
【図１８】実施例２の差分情報判定テーブルの更に他の一部の例を説明する図である。
【図１９】実施例２の木構造差分データの例を説明する図である。
【図２０】実施例２の送信後の書き換え規則の例を説明する図である。
【図２１】実施例２の書き換え後の文書テーブルの例を説明する図である。
【図２２】実施例２の書き換え後のリンクテーブルの例を説明する図である。
【符号の説明】
【００６３】
１０      収集拠点
２０      センタ
３２      木構造情報提供サーバ
３４ａ      社内ネットワーク
３６      木構造情報収集装置
３８      クライアント装置
１００      木構造データ
１０１      探索順序記憶部
１０２      チェックポイント記憶部
１０３      対象ノード決定部
１０４      チェックポイント更新部
１０５      メンバリスト作成部
１０６      メンバリスト記憶部
１０７      メンバリスト送信部
２０１      木構造データ記憶部
２０２      木構造データ更新部
２０３      メンバリスト受信部
３２２      木構造データ記憶部
３２４      木構造データ
３２６      クライアント要求処理部
３２８      木構造更新部
３６２      収集部
３６４      更新用データ作成部
３８０      木構造要求
４００      記憶部
４０２      探索順序
４０４      前回文書テーブル
４０６      前回リンクテーブル
４０８      差分情報判定テーブル
４１０      収集後文書テーブル
４１２      収集後リンクテーブル
４１４      チェックポイント
【図１】
2005310008.tif 000003
【図２】
2005310008.tif 000004
【図３】
2005310008.tif 000005
【図４】
2005310008.tif 000006
【図５】
2005310008.tif 000007
【図６】
2005310008.tif 000008
【図７】
2005310008.tif 000009
【図８】
2005310008.tif 000010
【図９】
2005310008.tif 000011
【図１０】
2005310008.tif 000012
【図１１】
2005310008.tif 000013
【図１２】
2005310008.tif 000014
【図１３】
2005310008.tif 000015
【図１４】
2005310008.tif 000016
【図１５】
2005310008.tif 000017
【図１６】
2005310008.tif 000018
【図１７】
2005310008.tif 000019
【図１８】
2005310008.tif 000020
【図１９】
2005310008.tif 000021
【図２０】
2005310008.tif 000022
【図２１】
2005310008.tif 000023
【図２２】
2005310008.tif 000024