(57)【要約】【課題】多様な特徴量を用いた効率的オブジェクト検索、負荷の均等化、ノードの追加・削除への対応ができるＰ２Ｐ環境におけるオブジェクトの登録検索方法を提供する。【解決手段】  ネットワークに接続されてそれぞれ自己を特定するノードＩＤを有する最大２ｎ個のノードに、それぞれシグネチャを利用した共通の登録方法に従って登録されているオブジェクトからシグネチャを利用した共通の検索方法を用いて所望のオブジェクトを検索する。登録方法及び検索方法の両方において、ロケータを生成する。ロケータに基づいてインデックスエントリを生成し、インデックスエントリをロケータにより指定された１個以上のノードに登録する。問合せロケータに基づいてインデックスエントリを収集して、問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを、検索作業を行うノードに送信する。【選択図】  図１０
2005071115.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークに接続されてそれぞれ自己を特定するノードＩＤを有する最大２ｎ個（ｎは正の整数）のノードに、それぞれシグネチャを利用した共通の登録方法に従って登録されているオブジェクトからシグネチャを利用した共通の検索方法を用いて所望のオブジェクトを検索するＰ２Ｐ環境におけるオブジェクトの登録検索方法であって、
前記登録方法が、
登録すべきオブジェクトの１個以上の特徴量を長さｍ（ｍは１以上の正の整数）のビット列からなるオブジェクトシグネチャとする第１の登録ステップと、
前記オブジェクトシグネチャの前記長さｍのビット列を長さｍ／ｐ（ｐは１以上の正の整数）のビット列からなるフレームシグネチャから構成されたｐ個の分割フレームに分割する第２の登録ステップと、
前記ｐ個の分割フレームをそれぞれ特定するビット列と、前記フレームシグネチャを構成する長さｍ／ｐのビット列とを合成して各分割フレームに対応する合成シグネチャを作成する第３の登録ステップと、
前記合成シグネチャを構成するビット列から長さｎのビット列からなるｐ個のロケータを生成する第４の登録ステップと、
登録作業を行っている前記ノードのノードＩＤと、登録作業を行っている前記ノード内で登録対象となっているオブジェクトを特定するローカルＩＤと、前記分割フレームを特定するデータと、前記フレームシグネチャとからなるインデックスエントリを前記ｐ個のロケータに対応して作成する第５の登録ステップと、
前記インデックスエントリを前記ロケータにより指定された１個以上の前記ノードに登録する第６の登録ステップとからなり、
前記検索方法が、
検索作業を行う前記ノードにおいて、検索すべきオブジェクトの１以上の特徴量を長さｍ（ｍは１以上の正の整数）のビット列からなる問合せシグネチャとして生成する第１の問合せエントリ生成ステップと、前記問合せシグネチャの前記長さｍのビット列を長さｍ／ｐ（ｐは１以上の正の整数）のビット列からなる問合せフレームシグネチャから構成されたｐ個の分割フレームに分割する第２の問合せエントリ生成ステップと、前記ｐ個の分割フレームをそれぞれ特定するビット列と、前記問合せフレームシグネチャを構成する長さｍ／ｐのビット列を合成して各分割フレームに対応する合成シグネチャを作成する第３の問合せエントリ生成ステップと、前記合成シグネチャを構成するビット列から長さｎのビット列からなるｐ個の問合せロケータを生成する第４の問合せエントリ生成ステップとを実行する第１の検索ステップと、
前記ｐ個の問合せロケータに基づいて定まる１以上の前記ノードにおいて前記問合せフレームシグネチャの条件を満たすインデックスエントリを収集し、最終的にインデックスエントリの収集を行う前記ノードから１以上の前記ノードにおいて収集した前記問合せフレームシグネチャの条件を満たすすべての前記インデックスエントリを前記検索作業を行うノードに送信する第２の検索ステップとからなることを特徴とするＰ２Ｐ環境におけるオブジェクトの登録検索方法。
【請求項２】
前記第４の登録ステップでは、前記合成シグネチャを構成するビット列の先頭から最大ｎ個のビットを用いて登録先のノードを特定するための前記ロケータを生成する請求項１に記載のオブジェクトの登録検索方法。
【請求項３】
前記第２の検索ステップが、
前記ｐ個の問合せロケータ中の最初の問合せロケータに基づいて検索対象とすべき前記ノードを定めるすべての検索対象ロケータを求めて検索対象ロケータ集合を生成し、前記検索作業を行うノードのノードＩＤ及びすべての前記問合せフレームシグネチャを含む問合せデータを前記検索対象ロケータ集合の最初の前記検索対象ロケータにより定まる前記ノードに送る第１のステップと、
前記最初のノードにおいて、前記最初の検索対象ロケータに対応する前記問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを取得して部分インデックスエントリ候補集合とする第２のステップと、
次の検索対象ロケータにより定まる次の前記ノードに前記問合せデータと前記インデックスエントリ候補を送る第３のステップと、
前記次のノードにおいて、前記次の検索対象ロケータに対応する前記問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを取得し且つ該インデックスエントリ集合と前記部分インデックスエントリ候補集合との和集合を取ってその結果を次の部分インデックスエントリ候補集合とする第４のステップと、
最後の前記検索対象ロケータに到るまで前記第３のステップ及び前記第４のステップを繰り返し最後の前記部分インデックスエントリ候補集合をインデックスエントリ候補集合とする第５のステップと、
前記ｐ個の問合せロケータ中の次の前記問合せロケータから前記検索対象ロケータ集合を生成し、前記問合せデータ及び前記インデックスエントリ候補集合を該検索対象ロケータ集合の最初の検索対象ロケータにより定まる次の前記ノードに送る第６のステップと、
前記次のノードからはじめて前記検索対象ロケータ集合の最後の検索対象ロケータに到るまで前記第２のステップ及び前記第３のステップ及び前記第４のステップ及び前記第５のステップを繰り返しその結果得られたインデックスエントリ候補集合と本ステップ開始時のインデックスエントリ候補集合の積集合をとってその結果を次のインデックスエントリ候補集合とする第７のステップと、
最後の前記問合せロケータに到るまで前記第６のステップ及び前記第７のステップを繰り返し、最終結果を前記検索作業を行うノードに送信する第８のステップとからなることを特徴とするＰ２Ｐ環境におけるオブジェクトの登録検索方法。
【請求項４】
前記問合せロケータにより定まる各前記ノードにおいて、前記第１の問合せエントリ生成ステップ乃至前記第４の問合せエントリ生成ステップが実行されて前記次の問合せロケータが定まることを特徴とする請求項２に記載のＰ２Ｐ環境におけるオブジェクトの登録検索方法。
【請求項５】
ネットワークに接続されてそれぞれ自己を特定するノードＩＤを有する最大２ｎ個のノードのコンピュータに、それぞれシグネチャを利用した共通の登録手順に従って登録し、且つ登録されているオブジェクトからシグネチャを利用した共通の検索手順を用いて所望のオブジェクトを検索するために用いられるＰ２Ｐ環境におけるオブジェクトの登録検索用プログラムであって、
前記登録手順が、
登録すべきオブジェクトの１個以上の特徴量を長さｍ（ｍは１以上の正の整数）のビット列からなるオブジェクトシグネチャとする第１の登録ステップと、
前記オブジェクトシグネチャの前記長さｍのビット列を長さｍ／ｐ（ｐは１以上の正の整数）のビット列からなるフレームシグネチャから構成されたｐ個の分割フレームに分割する第２の登録ステップと、
前記ｐ個の分割フレームをそれぞれ特定するビット列と、前記フレームシグネチャを構成する長さｍ／ｐのビット列とを合成して各分割フレームに対応する合成シグネチャを作成する第３の登録ステップと、
前記合成シグネチャを構成するビット列から長さｎのビット列からなるｐ個のロケータを生成する第４の登録ステップと、
登録作業を行っている前記ノードのノードＩＤと、登録作業を行っている前記ノード内で登録対象となっているオブジェクトを特定するローカルＩＤと、前記分割フレームを特定するデータと、前記フレームシグネチャとからなるインデックスエントリを前記ｐ個のロケータに対応して作成する第５の登録ステップと、
前記インデックスエントリを前記ロケータにより指定された１以上の前記ノードに登録する第６の登録ステップとからなり、
前記検索手順が、
検索作業を行う前記ノードにおいて、検索すべきオブジェクトの１以上の特徴量を長さｍ（ｍは１以上の正の整数）のビット列からなる問合せシグネチャとする第１の問合せエントリ生成ステップと、前記問合せシグネチャの前記長さｍのビット列を長さｍ／ｐ（ｐは１以上の正の整数）のビット列からなる問合せフレームシグネチャから構成されたｐ個の分割フレームに分割する第２の問合せエントリ生成ステップと、前記ｐ個の分割フレームをそれぞれ特定するビット列と、前記問合せフレームシグネチャを構成する長さｍ／ｐのビット列を合成して各分割フレームに対応する合成シグネチャを作成する第３の問合せエントリ生成ステップと、前記合成シグネチャを構成するビット列から長さｎのビット列からなるｐ個の問合せロケータを生成する第４の問合せエントリ生成ステップとを実行する第１の検索ステップと、
前記ｐ個の問合せロケータに基づいて定まる１以上の前記ノードにおいて前記問合せフレームシグネチャの条件を満たすインデックスエントリを収集し、最終的にインデックスエントリの収集を行う前記ノードから１以上の前記ノードにおいて収集した前記問合せフレームシグネチャの条件を満たすすべての前記インデックスエントリを前記検索作業を行うノードに送信する第２の検索ステップとからなり、
前記登録手順と前記検索手順とを実行させるためのＰ２Ｐ環境におけるオブジェクトの登録検索用プログラム。
【請求項６】
前記第２の検索ステップが、
前記ｐ個の問合せロケータ中の最初の問合せロケータに基づいて検索対象とすべき前記ノードを定めるすべての検索対象ロケータを求めて検索対象ロケータ集合を生成し、前記検索作業を行うノードのノードＩＤ及びすべての前記問合せフレームシグネチャを含む問合せデータを前記検索対象ロケータ集合の最初の前記検索対象ロケータにより定まる前記ノードに送る第１のステップと、
前記最初のノードにおいて、前記最初の検索対象ロケータに対応する前記問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを取得して部分インデックスエントリ候補集合とする第２のステップと、
次の検索対象ロケータにより定まる次の前記ノードに前記問合せデータと前記インデックスエントリ候補を送る第３のステップと、
前記次のノードにおいて、前記次の検索対象ロケータに対応する前記問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを取得し且つ該インデックスエントリ集合と前記部分インデックスエントリ候補集合との和集合を取ってその結果を次の部分インデックスエントリ候補集合とする第４のステップと、
最後の前記検索対象ロケータに到るまで前記第３のステップ及び前記第４のステップを繰り返し最後の前記部分インデックスエントリ候補集合をインデックスエントリ候補集合とする第５のステップと、
前記ｐ個の問合せロケータ中の次の前記問合せロケータから前記検索対象ロケータ集合を生成し、前記問合せデータ及び前記インデックスエントリ候補集合を該検索対象ロケータ集合の最初の検索対象ロケータにより定まる次の前記ノードに送る第６のステップと、
前記次のノードからはじめて前記検索対象ロケータ集合の最後の検索対象ロケータに到るまで前記第２のステップ及び前記第３のステップ及び前記第４のステップ及び前記第５のステップを繰り返しその結果得られたインデックスエントリ候補集合と本ステップ開始時のインデックスエントリ候補集合の積集合をとってその結果を次のインデックスエントリ候補集合とする第７のステップと、
最後の前記問合せロケータに到るまで前記第６のステップ及び前記第７のステップを繰り返し、最終結果を前記検索作業を行うノードに送信する第８のステップとからなることを特徴とするＰ２Ｐ環境におけるオブジェクトの登録検索プログラム。
【請求項７】
前記問合せロケータにより定まる各前記ノードにおいて、前記第１の問合せエントリ生成ステップ乃至前記第４の問合せエントリ生成ステップが実行されて前記次の問合せロケータを定める機能を更に実現させることを特徴とする請求項６に記載のＰ２Ｐ環境におけるオブジェクトの登録検索用プログラム方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｐ２Ｐ環境におけるシグネチャを用いたオブジェクトの登録検索方法及びこの方法を実施するために用いるプログラムに関するものである。
【背景技術】
【０００２】
近年、計算機の高性能化とネットワークインフラの発達により、Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ（Ｐ２Ｐ）技術が注目されている。Ｐ２Ｐでは各計算機（コンピュータ）がｐｅｅｒ  ｎｏｄｅ（ノード）となり、大規模な分散ネットワークを構築する。各ノードはサーバ、クライアントといった明確な区別はなく両方の役割を担っている。また、Ｐ２Ｐネットワークの形態は、クライアント・サーバシステムを融合させたハイブリッドＰ２Ｐ型と、完全な分散環境であるピュアＰ２Ｐ型に分類される。ハイブリッドＰ２Ｐ型は、ある種のサービスを提供するために特定のサーバが存在する。ハイブリッドＰ２Ｐ型におけるオブジェクト検索では、サーバがインデックス機能を提供することで、ノードに分散する情報の共有を図ることが可能である。しかし、多数のノードがそのサーバのサービスを要求した場合には、サーバがボトルネックとなる。また、サーバが停止した場合にはサービス全体が停止してしまう。一方、ピュアＰ２Ｐ型では各ノードが自律的に動作する。このため、サーバの処理能力に制約されずにノードの追加ができるなどの拡張性に富み、ボトルネックのない処理を実現することができる。
【０００３】
しかし、ピュアＰ２Ｐ型ではグローバルなインデックス等をサーバに持つことができないため、一般に情報の共有は容易ではない。代表的なピュアＰ２Ｐ型のシステムとして、ファイル共有システムＧｎｕｔｅｌｌａ［非特許文献１］（Ｇｎｕｔｅｌｌａ  ｗｅｂｓｉｔｅ．ｈｔｔｐ：／／ｗｗｗ．ｇｎｕｔｅｌｌａ．ｃｏｍ／）が挙げられる。Ｇｎｕｔｅｌｌａではブロードキャストを用いて、周辺のノードを巡回する方法で検索を行うため、オブジェクト検索時における通信コストが大きな問題となる。この問題を解決するため、Ｋａｒｌ  Ａｂｅｒｅｒが発表した論文「Ａ  Ｓｅｌｆ−Ｏｒｇａｎｉｚｉｎｇ  Ａｃｃｅｓｓ  Ｓｔｒｕｃｔｕｒｅ  ｆｏｒ  Ｐ２Ｐ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍｓ」［非特許文献２］や、Ｉｏｎ  Ｓｔｏｉｃａ，  Ｒｏｂｅｒｔ  Ｍｏｒｒｉｓ，  Ｄａｖｉｄ  Ｋａｒｇｅｒ，  Ｍ．  Ｆｒａｎｓ  Ｋａａｓｈｏｅｋ及びＨａｒｉ  Ｂａｌａｋｒｉｓｈｎａｎが発表した論文「Ａ  Ｓｃａｌａｂｌｅ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｌｏｏｋｕｐ  Ｓｅｒｖｉｃｅ  ｆｏｒＩｎｔｅｒｎｅｔ  Ａｐｐｌｉｃａｔｉｏｎｓ」［非特許文献３］、Ｓｙｌｖｉａ  Ｒａｔｎａｓａｍｙ，  Ｐａｕｌ  Ｆｒａｎｃｉｓ，  Ｍａｒｋ  Ｈａｎｄｌｅｙ，  Ｒｉｃｈａｒｄ  Ｋａｒｐ及びＳｃｏｔｔ  Ｓｈｅｎｋｅｒが発表した論文「Ａ  Ｓｃａｌａｂｌｅ  Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｎｅｔｗｏｒｋ」［非特許文献４］や、Ｋｉｒｓｔｅｎ  Ｈｉｌｄｒｕｍ、Ｊｏｈｎ  Ｄ．  Ｋｕｂｉａｔｏｗｉｃｚ、Ｓａｔｉｓｈ  Ｒａｏ及びＢｅｎ  Ｙ．Ｚｈａｏが発表した論文「Ｄｉｓｔｒｉｂｕｔｅｄ  Ｏｂｊｅｃｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  ａ  Ｄｙｎａｍｉｃ  Ｎｅｔｗｏｒｋ」［非特許文献５］に各手法が提案されている。これらの手法は、以下のような特徴を持つ。
【０００４】
・効率的なオブジェクト検索
全ノード数Ｎに対してＯ（ｌｏｇ（Ｎ））またはこれに準じた検索コストの効率的な検索方式を提供する。したがって、多数のノードが存在する環境にも適用可能である。
【０００５】
・負荷の均等化
データオブジェクトは各ノードに均等に配置され、ノード当たりの負荷が均等化される。
【０００６】
・ノードの追加・削除への対応
ノードの追加や削除に対し、自律的にノード情報を修正することで、サービスを継続することができる。
【０００７】
しかし、これらの手法では、オブジェクトＩＤというキーを用いたオブジェクト検索のみが考慮されており、オブジェクトの持つ種々の特徴量による検索を直接行うことはできない。
【０００８】
そこで一般に、オブジェクトの持つ種々の特徴量を用いた柔軟な検索を実現する手段としてシグネチャを用いることが考えられている。例えば、Ｃｈｒｉｓｔｏｓ  Ｆａｌｏｕｔｓｏｓが発表した論文「Ｄｅｓｉｇｎ  ａｎｄ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  Ｓｏｍｅ  Ｓｉｇｎａｔｕｒｅ  Ｅｘｔｒａｃｔｉｏｎ  Ｍｅｔｈｏｄｓ」［非特許文献６］や、石川  佳治，  北川  博之及び  大保  信夫が発表した論文「シグネチャファイルによる集合値検索のコスト評価」［非特許文献７］に説明されている。シグネチャを用いることで、多様な特徴量による検索を行うことができる。例えば、オブジェクト名やその内容記述に対するキーワード照合や任意の部分文字列照合があげられる。
【非特許文献１】Ｇｎｕｔｅｌｌａ  ｗｅｂｓｉｔｅ．ｈｔｔｐ：／／ｗｗｗ．ｇｎｕｔｅｌｌａ．ｃｏｍ／
【非特許文献２】「Ａ  Ｓｅｌｆ−Ｏｒｇａｎｉｚｉｎｇ  Ａｃｃｅｓｓ  Ｓｔｒｕｃｔｕｒｅ  ｆｏｒ  Ｐ２Ｐ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍｓ」  ＣｏｏｐＩＳ  ２００１，  ＬＮＣＳ  ２１７２，  ｐｐ．  １７９−１９４，  ２００１．
【非特許文献３】「Ａ  Ｓｃａｌａｂｌｅ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｌｏｏｋｕｐ  Ｓｅｒｖｉｃｅ  ｆｏｒＩｎｔｅｒｎｅｔ  Ａｐｐｌｉｃａｔｉｏｎｓ」，ＳＩＧＣＯＭＭ’０１，  ｐｐ．  １４９−１６０，  ２００１．
【非特許文献４】「Ａ  Ｓｃａｌａｂｌｅ  Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｎｅｔｗｏｒｋ」，ＳＩＧＣＯＭＭ’０１，  ｐｐ．  １６１−１７２，  ２００１．
【非特許文献５】「Ｄｉｓｔｒｉｂｕｔｅｄ  Ｏｂｊｅｃｔ  Ｌｏｃａｔｉｏｎ  ｉｎ  ａ  Ｄｙｎａｍｉｃ  Ｎｅｔｗｏｒｋ」，  ＳＰＡＡ’０２，ｐｐ．  ４１−５２，  ２００２．
【非特許文献６】「  Ｄｅｓｉｇｎ  ａｎｄ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  Ｓｏｍｅ  Ｓｉｇｎａｔｕｒｅ  Ｅｘｔｒａｃｔｉｏｎ  Ｍｅｔｈｏｄｓ」  Ｐｒｏｃ．  ＡＣＭ  ＳＩＧＭＯＤ  １９８５，ｐｐ．６３−８２，１９８５
【非特許文献７】「シグネチャファイルによる集合値検索のコスト評価」情報処理学会論文誌，Ｖｏｌ．３６，Ｎｏ．２，ｐｐ．３８３−３９５，１９９５
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら従来のシグネチャを用いる技術では、Ｐ２Ｐ環境における利用が検討されておらず、Ｐ２Ｐ環境におけるシグネチャを用いたオブジェクト検索を行うことができなかった。
【００１０】
本発明の目的は、多様な特徴量を用いた効率的オブジェクト検索、負荷の均等化、ノードの追加・削除への対応ができるＰ２Ｐ環境におけるオブジェクトの登録検索方法及びこの方法を実現するプログラムを提供することにある。
【００１１】
本発明の他の目的は、検索要求とオブジェクト登録要求の出現頻度に応じて、処理効率を最適化することができるＰ２Ｐ環境におけるオブジェクトの登録検索方法及びこの方法を実現するプログラムを提供することにある。
【００１２】
本発明の更に他の目的は、オフラインノードが存在する場合でも、オブジェクト検索を継続することができるＰ２Ｐ環境におけるオブジェクトの登録検索方法及びこの方法を実現するプログラムを提供することにある。
【課題を解決するための手段】
【００１３】
本発明の方法は、ネットワークに接続されてそれぞれ自己を特定するノードＩＤを有する最大２ｎ個のノードに、それぞれシグネチャを利用した共通の登録方法に従って登録されているオブジェクトからシグネチャを利用した共通の検索方法を用いて所望のオブジェクトを検索するＰ２Ｐ環境におけるオブジェクトの登録検索方法を対象とする。
【００１４】
本発明で用いる登録方法では、まず登録すべきオブジェクトの１個以上の特徴量を長さｍ（ｍは１以上の正の整数）のビット列からなるオブジェクトシグネチャとする（第１の登録ステップ）。次に、オブジェクトシグネチャの長さｍのビット列を長さｍ／ｐ（ｐは１以上の正の整数）のビット列からなるフレームシグネチャから構成されたｐ個の分割フレームに分割する（第２の登録ステップ）。そしてｐ個の分割フレームをそれぞれ特定するビット列と、フレームシグネチャを構成する長さｍ／ｐのビット列とを合成して各分割フレームに対応する合成シグネチャを作成する（第３の登録ステップ）。その後、合成シグネチャを構成するビット列から長さｎのビット列からなるｐ個のロケータを生成する（第４の登録ステップ）。この第４の登録ステップでは、合成シグネチャを構成するビット列の先頭から最大ｎ個のビットを用いて登録先のノードを特定するためのロケータを生成する。このようにするとロケータによるノードの特定を容易且つ確実に行える。次に登録作業を行っているノードのノードＩＤと、登録作業を行っているノード内で登録対象となっているオブジェクトを特定するローカルＩＤと、分割フレームを特定するデータと、フレームシグネチャとからなるインデックスエントリをｐ個のロケータに対応して作成する（第５の登録ステップ）。最後に、このインデックスエントリをロケータにより指定された１個以上のノードに登録する（第６の登録ステップ）。
【００１５】
また本発明の方法で用いる検索方法では、検索作業を行うノードにおいて、検索すべきオブジェクトの１以上の特徴量を長さｍ（ｍは以上の正の整数）のビット列からなる問合せシグネチャとする（第１の問合せエントリ生成ステップ）。次に問合せシグネチャの長さｍのビット列を長さｍ／ｐ（ｐは１以上の正の整数）のビット列からなる問合せフレームシグネチャから構成されたｐ個の分割フレームに分割する（第２の問合せエントリ生成ステップ）。そしてｐ個の分割フレームをそれぞれ特定するビット列と、問合せフレームシグネチャを構成する長さｍ／ｐのビット列を合成して各分割フレームに対応する合成シグネチャを作成する（第３の問合せエントリ生成ステップ）。次に合成シグネチャを構成するビット列から長さｎのビット列からなるｐ個の問合せロケータを生成する（第４の問合せエントリ生成ステップ）。これら第１乃至第４の問合わせエントリ生成ステップを実行するのが第１の検索ステップである。次に、ｐ個の問合せロケータに基づいて定まる１以上のノードにおいて問合せフレームシグネチャの条件を満たすインデックスエントリを収集し、最終的にインデックスエントリの収集を行うノードから１以上のノードにおいて収集した問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを、検索作業を行うノードに送信する（第２の検索ステップ）。本発明で用いる検索方法を採用すると、第１及び第２の検索ステップによりオブジェクトの検索に利用できるインデックスエントリをＰ２Ｐ環境において、簡単に且つ少ない通信費で収集することができる。収集したインデックスエントリから目的とするオブジェクトを検索する方法は、マニュアルでもよいし、公知の検索手法を用いてもよい。
【００１６】
このようにしてｐ個のロケータに対応して作成したインデックスエントリをｐ個のロケータによりそれぞれ指定されたノードに登録すると、１つのオブジェクトの検索に必要なインデックスをＰ２Ｐ環境において分散して各ノードに配置することになる。その結果、以下のような特徴的な利点が得られる。
【００１７】
１．シグネチャを用いることで、多様な特徴量による柔軟な検索に対応できる。
【００１８】
２．基本となる枠組みとして後述するＣｈｏｒｄやＰ−Ｇｒｉｄ等を利用し、かつこれらの持つ上記の特徴をシグネチャを用いた検索においても継承することができる。
【００１９】
３．シグネチャのフレーム分割を導入することで、適切なパラメタを選択することにより、利用環境におけるオブジェクト検索と追加の発生頻度に適合した構成をとることができる。
【００２０】
４．オフラインノードが存在する場合でもオブジェクト検索を継続することができる。
【００２１】
まずｐ個の問合せロケータ中の最初の問合せロケータに基づいて検索対象とすべきノードを定めるすべての検索対象ロケータを求めて検索対象ロケータ集合を生成する。すべての検索対象ロケータとは、１つの問合わせロケータで定められたノード以外のノードにもインデックスエントリが登録されることがあるため、これらのインデックスエントリを検索するためのロケータを意味する。そして、検索作業を行うノードのノードＩＤ及びすべての問合せフレームシグネチャを含む問合せデータを検索対象ロケータ集合の最初の検索対象ロケータにより定まるノードに送る（第１のステップ）。その後最初のノードにおいて、最初の検索対象ロケータに対応する問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを取得して部分インデックスエントリ候補集合とする（第２のステップ）。次に次の検索対象ロケータにより定まる次のノードに問合せデータとインデックスエントリ候補を送る（第３のステップ）。そして次のノードにおいて、次の検索対象ロケータに対応する問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを取得し且つ該インデックスエントリ集合と前記部分インデックスエントリ候補集合との和集合を取ってその結果を次の部分インデックスエントリ候補集合とする（第４のステップ）。またその後、最後の検索対象ロケータに到るまで第３のステップ及び第４のステップを繰り返し最後の部分インデックスエントリ候補集合をインデックスエントリ候補集合とする（第５のステップ）。またｐ個の問合せロケータ中の次の問合せロケータから検索対象ロケータ集合を生成し、問合せデータ及びインデックスエントリ候補集合を該検索対象ロケータ集合の最初の検索対象ロケータにより定まる次のノードに送る（第６のステップ）。そして次のノードからはじめて検索対象ロケータ集合の最後の検索対象ロケータに到るまで第２のステップ及び第３のステップ及び第４のステップ及び第５のステップを繰り返しその結果得られたインデックスエントリ候補集合と本ステップ（第７のステップ）開始時のインデックスエントリ候補集合の積集合をとってその結果を次のインデックスエントリ候補集合とする（第７のステップ）。最後の問合せロケータに到るまで第６のステップ及び第７のステップを繰り返し、最終結果を検索作業を行うノードに送信する（第８のステップ）。
【００２２】
このようにすることにより、所定のオブジェクトについてのインデックスエントリが登録されているすべてのノードにおいて検索が実行される。
【００２３】
なお問合せロケータにより定まる各ノードにおいて、第１の問合せエントリ生成ステップ乃至第４の問合せエントリ生成ステップが実行されて次の問合せロケータを定める。
【００２４】
本発明を、ネットワークに接続されてそれぞれ自己を特定するノードＩＤを有する最大２ｎ個のノードのコンピュータに、それぞれシグネチャを利用した共通の登録手順に従って登録し、且つ登録されているオブジェクトからシグネチャを利用した共通の検索手順を用いて所望のオブジェクトを検索するために用いられるＰ２Ｐ環境におけるオブジェクトの登録検索用プログラムとして特定すると、このプログラムは以下の登録手順と検索手順を実行するように構成される。すなわち登録手順では、登録すべきオブジェクトの１個以上の特徴量を長さｍ（ｍは１以上の正の整数）のビット列からなるオブジェクトシグネチャとする第１の登録ステップと、オブジェクトシグネチャの前記長さｍのビット列を長さｍ／ｐ（ｐは１以上の正の整数）のビット列からなるフレームシグネチャから構成されたｐ個の分割フレームに分割する第２の登録ステップと、ｐ個の分割フレームをそれぞれ特定するビット列と、フレームシグネチャを構成する長さｍ／ｐのビット列とを合成して各分割フレームに対応する合成シグネチャを作成する第３の登録ステップと、合成シグネチャを構成するビット列から長さｎのビット列からなるｐ個のロケータを生成する第４の登録ステップと、登録作業を行っているノードのノードＩＤと、登録作業を行っているノード内で登録対象となっているオブジェクトを特定するローカルＩＤと、分割フレームを特定するデータと、フレームシグネチャとからなるインデックスエントリをｐ個のロケータに対応して作成する第５の登録ステップと、インデックスエントリをロケータにより指定された１個以上のノードに登録する第６の登録ステップとからなる。
【００２５】
そして検索手順は、検索作業を行うノードにおいて、検索すべきオブジェクトの１以上の特徴量を長さｍ（ｍは以上の正の整数）のビット列からなる問合せシグネチャとする第１の問合せエントリ生成ステップと、問合せシグネチャの長さｍのビット列を長さｍ／ｐ（ｐは１以上の正の整数）のビット列からなる問合せフレームシグネチャから構成されたｐ個の分割フレームに分割する第２の問合せエントリ生成ステップと、ｐ個の分割フレームをそれぞれ特定するビット列と、問合せフレームシグネチャを構成する長さｍ／ｐのビット列を合成して各分割フレームに対応する合成シグネチャを作成する第３の問合せエントリ生成ステップと、合成シグネチャを構成するビット列から長さｎのビット列からなるｐ個の問合せロケータを生成する第４の問合せエントリ生成ステップとを実行する第１の検索ステップと、ｐ個の問合せロケータに基づいて定まる１以上のノードにおいて問合せフレームシグネチャの条件を満たすインデックスエントリを収集し、最終的にインデックスエントリの収集を行うノードから１以上のノードにおいて収集した問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを検索作業を行うノードに送信する第２の検索ステップとからなる。
【発明の効果】
【００２６】
本発明によれば、Ｐ２Ｐ環境における分散配置されたシグネチャ情報を用いたオブジェクトの登録検索方法を提供することができ、分割フレーム数を大きくすることで、検索時におけるメッセージ数、総データ転送量、応答時間を削減できる。また本発明によれば、分割フレーム数を増加させるとデータ追加の際のメッセージ数は増加するものの、並列処理の導入により応答時間については大きな変化がないという利点がある。さらに検索と追加の発生割合を考慮した場合でも、分割フレーム数を変化させることで処理効率を最適化できる。その上本発明によれば、オフラインノードが存在する場合の検索の精度についても、特に分割フレーム数が大きくすれば、オフラインノードが存在する場合でも一定の検索精度を維持可能であるという利点が得られる。
【発明を実施するための最良の形態】
【００２７】
以下図面を参照して本発明の実施の形態の一例を詳細に説明する。なお以下の説明では、基本アーキテクチャとしてＣｈｏｒｄの枠組みを利用した場合を具体的な対象とする。また、シグネチャを用いた特徴検索の例として、オブジェクト名に対する部分文字列照合を示す。さらに、シミュレーション実験により、オブジェクト検索時および追加時に要するメッセージ数とその応答時間、検索と追加が混在する場合でのメッセージ数、およびオフラインノードが存在する場合の検索の精度について評価検討を行う。
【００２８】
まず本発明の実施の形態を説明する前に、比較のために従来から採用されているＰ２Ｐ環境上にキーを用いた検索のための構造を導入し、適切なルーティング処理を行って、効率的な検索を実現するための検索方法について簡単に説明する。このような公知の検索方法としては、Ｃｈｏｒｄ、Ｐ−Ｇｒｉｄ、ＣＡＮ、Ｔａｐｅｓｔｒｙ等が知られている。しかし、これらの方法では、検索はキーとしてのオブジェクトＩＤに基づくもののみに限られるため、オブジェクトの特徴量などによる柔軟な検索は不可能である。
【００２９】
本発明の方法では、Ｐ２Ｐ環境におけるオブジェクト検索を実現するためにシグネチャを用いる。なお並列処理を用いてシグネチャの照合処理を効率化する研究（Ｚｈｅｎｇ  Ｌｉｎ，Ｃｏｎｃｕｒｒｅｎｔ  Ｆｒａｍｅ  Ｓｉｇｎａｔｕｒｅ  Ｆｉｌｅｓ，Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ，  Ｄｉｓｔｒｉｂｕｅｄ  ａｎｄ  Ｐａｒａｌｌｅｌ  Ｄａｔａｂａｓｅｓ  Ｖｏｌ．１，  ｐｐ．  ２３１−２４９，  １９９３．）もある。このの公知の方法では、シグネチャを分割しすべての計算機（ノード）に均等に割り当てを行って、照合処理を並列化することで効率化を図っている。しかしながらシグネチャの照合処理が全ノードで発生することや、シグネチャの分割や割当てが静的であることにより、この公知の方法をＰ２Ｐ環境に適応させることは非常に困難である。
【００３０】
これに対して、本発明では、シグネチャの分割法と配置法を工夫することで、シグネチャの照合処理が必要なノード数を少なく抑えることが可能である。また、ノードの追加や削除に対しても、シグネチャの動的な再配置を行うことが可能である。
【００３１】
本発明の実施の形態では、Ｃｈｏｒｄアーキテクチャを採用するので、まずＣｈｏｒｄアーキテクチャについて説明する。図１に示すように、Ｃｈｏｒｄアーキテクチャでは、ネットワーク空間全体がＩＤサークル（Ｉｄｅｎｔｉｆｉｅｒ  Ｃｉｒｃｌｅ）という円状の仮想空間として定義され、すべてのノードとすべてのデータオブジェクトはこのＩＤサークル上に配置される。Ｃｈｏｒｄのネットワーク空間の大きさはｓｃａｌｅ（スケール）で表現され、最大２ｓｃａｌｅ個すなわち２ｎ個（ｎは正の整数）のノードから構成される。ＣｈｏｒｄではノードおよびデータオブジェクトをＩＤサークル上に均等に配置するため、ハッシュ関数を用いる。これによりノードに対してｓｃａｌｅビットのノードＩＤ（ｎｉｄ）、データオブジェクトに対してｓｃａｌｅビットのオブジェクトＩＤ（ｏｉｄ）をそれぞれ与える。各ノードはノードＩＤに基づきＩＤサークル上に配置される。また、任意のオブジェクトＩＤのデータオブジェクトをＩＤサークル上に存在するいずれかのノードに割り当てるため、各ノードはＩＤ集合をもつ。
【００３２】
ノードｎのノードＩＤをｎ（ｉｄ）、その直前（時計回りの方向を順方向とする）に位置するノードｎ（ｐｒｅ）のノードＩＤをｎ（ｐｒｅ）ｉｄとする。この時、ノードｎのＩＤ集合は、以下の区間ｉｎｔｅｒｖａｌ（ｉｄ）に含まれるＩＤの集合のことである。
【００３３】
ｉｎｔｅｒｖａｌ（ｉｄ）＝（ｎ（ｐｒｅ）ｉｄ，ｎｉｄ］  
各データオブジェクトは、そのオブジェクトＩＤをＩＤ集合の要素に含む当該ノードへ割り当てられる。
【００３４】
各ノードは実際に割り当てられたオブジェクトＩＤのリスト、ルーティング情報、前後に位置するノード情報（ｓｕｃｃｅｓｓｏｒ、ｐｒｅｄｅｃｅｓｓｏｒ）を保持している。ルーティング情報は、検索対象のオブジェクトＩＤのオブジェクトが当該ノードに存在しない場合に、次にその問合せをフォワード（送信）すべきノードの情報を含む。この情報はｓｃａｌｅ個存在し、各ｉｎｔｅｒｖａｌに含まれるオブジェクトＩＤのオブジェクトを検索する際に次にどのノード（ｓｕｃｃｅｓｓｏｒ  ｎｏｄｅと呼ばれる）に検索要求をフォワードすべきかが示されている。ただし、ｉｎｔｅｒｖａｌとは次式で定義される区間のことである。
【数１】
2005071115.tif 000003
このように、各ｉｎｔｅｒｖａｌの大きさは時計回りに順に２ｋ−１となっている。これらのルーティング情報を持つことで、各ノードはＩＤサークル全体をカバーすることになり、任意の問合せに対して適切なルーティング処理を行うことができる。
【００３５】
Ｃｈｏｒｄにおいてノードの追加および削除があった場合の処理について説明する。新たにノードが追加された場合には、当該ノードを含む影響を受けるノードのルーティング情報と前後に位置するノード情報を更新し、ｓｕｃｃｅｓｓｏｒ（次のノード）の持つオブジェクトの再配置を行う。あるノードが削除される場合には、当該ノードの持つオブジェクトをｓｕｃｃｅｓｓｏｒへ再配置し、影響を受けるノードのルーティング情報と前後に位置するノード情報を更新する。
【００３６】
次に、Ｃｈｏｒｄでの検索処理についてより詳しく説明する。ＣｈｏｒｄではオブジェクトＩＤに基づく検索のみが考慮されている。このため、まず問合せでは獲得したいオブジェクトＩＤを指定する。問合せは任意のノードから開始することができる。問合せがノードへ渡されると、ノードは割り当てられたオブジェクトＩＤのリストから、その問合せのオブジェクトＩＤを持つデータオブジェクトがそのノード自身に存在するかどうかを判定する。存在する場合には、そのデータオブジェクトを返すことにより検索を終える。存在しない場合には、ルーティング情報を見ることで、次にフォワードすべきノードを決定しそのノードへ問合せを送る。この一連の判定処理を繰り返すことで、オブジェクトＩＤによる検索を実現する。２ｓｃａｌｅ個のノードを想定した場合、問合せがフォワードされる度に検索空間を半分に絞っていくことから、あるデータオブジェクトを検索するために要するメッセージ数はＯ（ｌｏｇ（Ｎ））となる。
【００３７】
なお図１において、楕円の中に記載された数字がオブジェクトＩＤであり、○で示したノードの側に記載したビットは、ノードＩＤである。また図１の右側に示した枠の内部には、オブジェクトＩＤリストに２が入っていること、そしてｉｎｔｅｒｖａｌ（検索対象となるオブジェクトＩＤの最初のＩＤと最後のＩＤ：但し前者は含まれるが、後者は含まれない）とｓｕｃｃｅｓｓｏｒ（次のノード）の関係と、ｓｕｃｃｅｓｓｏｒ（次のノード）とｐｒｅｄｅｃｅｓｓｏｒ（前のノード）の関係とが示されている。この関係から判ることは、ｉｎｔｅｒｖａｌが［４，６）とは、求めるオブジェクトＩＤが’４‘，’５’であればｓｕｃｃｅｓｓｏｒ（次のノード）はノードｃである。オブジェクトＩＤが’１０‘〜’１６‘，’１’であればｓｕｃｃｅｓｓｏｒ（次のノード）はノードａであることを示している。
【００３８】
具体的な検索の例を、図２を用いて説明する。問合せとして、オブジェクトＩＤが’２’であるオブジェクトを検索することを考える。まず、ノードｃより問合せが開始されるものとする。ノードｃでは問合せのオブジェクトＩＤを持つオブジェクトは存在しないため、ルーティング情報の中から’２’をｉｎｔｅｒｖａｌに含む［１４，６）のｓｕｃｃｅｓｓｏｒであるノードａへ問合せをフォワードする。ノードａでも同様に、問合せのオブジェクトＩＤを持つオブジェクトは存在しないため、ルーティング情報の中から’２’をｉｎｔｅｒｖａｌに含む［２，４）のｓｕｃｃｅｓｓｏｒであるノードｂへ問合せをフォワードする。ノードｂでは、問合せ条件に合致するデータオブジェクトが存在するため、開始ノードｃへ結果を返し、検索は終了する。以上のように、ＣｈｏｒｄではオブジェクトＩＤを用いた検索については、効率的な検索が可能である。また、各ノードのＩＤ集合の要素数がほぼ同じになることより、負荷の均等化が計れる。さらに、ノードの追加や削除への対応もなされている。したがって前述の３つの特徴が実現されている。
【００３９】
次に本発明で用いるシグネチャについて説明する。シグネチャは、個々のデータオブジェクトから生成される固定長のビット列であり、オブジェクトの特徴量を表現するものである。オブジェクトの特徴量をビット列という単純な表現方法に変換することで、特定の特徴量の存在の有無を容易に判定することができ、多様な特徴量によるオブジェクト検索が可能になる。
【００４０】
まず、各データオブジェクトから生成されるオブジェクトシグネチャについて述べる。図３は、ファイル名などのデータオブジェクトの名称から生成した公知のｔｒｉｇｒａｍを特徴量とした（名称を構成する文字を３文字づつに分けてそれを特徴量とした）場合の例を示している。ビット列からなるオブジェクトシグネチャの生成には、周知のスーパーインポーズドコーディングを用いている。これは各特徴量をハッシングしてシグネチャ長の要素シグネチャ（ｐｕｒ，ｕｒｅ，ｒｅＰ，ｅＰ２，Ｐ２Ｐをビット列であらわしたもの）を生成する。そしてさらに得られた要素シグネチャの各ビット列の論理和をとってそのビット列をオブジェクトシグネチャとする。このようにして生成されたオブジェクトシグネチャは、当該データオブジェクトの持つ特徴量を全て表すことになる。シグネチャでは、’１’の立っているビット位置によってこれを表現する。なお、この’１’の立っているビットの数のことをシグネチャのウェイトと呼ぶ。
【００４１】
問合せに関しても、図４に示すように、図３のオブジェクトシグネチャと同様にして問合せシグネチャを作成する。図４の例は、検索すべきオブジェクトの名称をｐｕｒｅとして問合せシグネチャを作成する例を示している。この例では、ｐｕｒｅをｔｒｉｇｒａｍに分解して、各特徴量の要素シグネチャの論理和を取って問合せシグネチャを作成している。問合せシグネチャの’１’の立っているビット位置が、問合せの持つ全ての特徴量を表している。オブジェクト検索では、問合せシグネチャの’１’の立っているビット位置がオブジェクトシグネチャでも’１’であるかを照合することで、当該オブジェクトが問合せの持つ全ての特徴量を含む可能性があるかを判定する。したがって、オブジェクトシグネチャと問合せシグネチャの各ビットの論理積をとったものが、問合せシグネチャと一致するときにそのオブジェクトは問合せの持つ特徴量を全て含む可能性があり、問合せ条件を満たす解の侯補となる。この解の侯補のことをドロップといい、この中で実際に正解となるものをアクチュアルドロップ、そうでないものをフォールスドロップという。この判定処理のことをフォールスドロップレゾリューションという。また、解の侯補がフォールスドロップとなる確率をフォールスドロップ確率Ｆｄといい、以下の式で与えられる。フォールスドロップ確率はシグネチャの検索精度を測る尺度となる。
【数２】
2005071115.tif 000004
上記式においては、Ｎｕｍ＿ＦａｌｓｅＤｒｏｐは、フォールスドロップ数、Ｎｕｍ＿ＵｎｑｕａｌｉｆｉｅｄＤａｔａＯｂｊｅｃｔは、問合せ条件を満たさないデータオブジェクト数である。このように、ｔｒｉｇｒａｍを特徴量と考えた場合には、シグネチャを用いることで、任意の文字列によるデータオブジェクト名の部分一致検索を実現できる。
【００４２】
本発明では、Ｐ２Ｐネットワークのノード上に、シグネチャ情報を分散配置することで、多様な特徴量に基づくオブジェクト検索の実現を計る。最も単純な分散配置法としては、各オブジェクトシグネチャを１つの単位として分散配置することが考えられる。この方法では、オブジェクトの追加時の処理は効率的にできるものの、検索時に各ノードに登録されている多数のシグネチャを参照する必要が生じる場合があり、多数のノードでの照合処理を避けるのは難しい。別の分散配置法としては、各オブジェクトシグネチャを複数の部分に分割し、部分シグネチャを単位として分散配置することが考えられる。この場合、照合時には問合せシグネチャ中の’１’の立っているビット位置を含む部分シグネチャのみを参照すればよいため検索処理の効率化を計ることができる。しかし、オブジェクト追加時には、各部分シグネチャの配置処理が必要になる。そこで、本発明では上記のオブジェクトシグネチャを単位とした分散配置法と部分シグネチャを単位とした分散配置法を融合し、利用環境におけるオブジェクト検索と追加の発生頻度に適合した構成が可能な方法を実現した。本発明の方法は、Ｐ２Ｐネットワーク上でデータの効率的検索を実現する枠組みの上に構築するものであり、先に述べたＣｈｏｒｄ、Ｐ−Ｇｒｉｄ等のいずれの枠組みを用いても実現することが可能である。本実施の形態では、Ｃｈｏｒｄを用いている。
【００４３】
図５は、本発明の方法の実施の形態を実施するために用いるプログラムにおける登録処理のアルゴリズムを示すフローチャートであり、図６はこのプログラムにおける検索処理のアルゴリズムを示すフローチャートである。以下図５及び図６のステップを説明しながら、本発明の方法及びプログラムの実施の形態の一例を説明する。図５及び図６に示したアルゴリズムを実現するプログラムは、Ｐ２Ｐ環境におけるネットワークに接続された自己を特定するノードＩＤを有する最大２ｎ個（ｎは正の整数）のノードにおけるコンピュータにすべてインストールされている。なお図５に示した関数は以下のことを意味する。ｌｅｎ（  ）は、引数で与えられた配列またはビット列の長さを返すことを意味する。ｖａｌｕｅ（  ）は、引数を１０進表現に変換した値を返すことを意味する。ｂｉｎａｒｙ（  ）は引数を２進表現に変換した値を返すことを意味する。ｃｏｎｃａｔｅｎａｔｅ（  ）は第１引数と第２引数を連結したビット列を返すことを意味する。ｐｒｅｆｉｘ（  ）は、第１引数のビット列に対して、先頭から第２引数番目までのビット列を返すことを意味する。ｚｅｒｏ  ｐａｄｄｉｎｇ（  ）は、第１引数のビット列に対して、ビット列の長さが第２引数になるまで‘０’をパディングし、生成されたビット列を返すことを意味する。また図６中においてｃｈｅｃｋ（  ）は、第１引数で与えられたインデックスエントリ集合に対して、以下の２つの条件１及び２を満たすインデックスエントリ集合を返すことを意味する。
【００４４】
１．各エントリのフレーム番号＝第１引数の値
２．各エントリのフレームシグネチャΛ第３引数のシグネチャ＝第３引数のシグネチャ
（Λはビット論理積を表す）
またｎｅｘｔ（  ）は、引数で与えられたロケータのフレームシグネチャ部分を基に、以下の２つの条件１及び２を満たすフレームシグネチャｎｅｘｔ  ｓｉｇを計算し、新たにロケータを生成して返すことを意味する。
【００４５】
１．ｎｅｘｔ  ｓｉｇ  Λ  フレームシグネチャ部分＝フレームシグネチャ部分
２．ｖａｌｕｅ（ｎｅｘｔ  ｓｉｇ）＞ｖａｌｕｅ（フレームシグネチャ部分）を満たす最小のｖａｌｕｅ（ｎｅｘｔ  ｓｉｇ）となるｎｅｘｔ  ｓｉｇ
まず登録処理では、図５に示すようにステップＳＴ１で、登録作業を行うノードにおいて、データオブジェクトの追加処理を実行するために、検索対象のデータオブジェクトをユーザが任意のノードに配置する。そしてステップＳＴ２乃至ＳＴ１５に従って、シグネチャ情報を含むインデックスエントリを所定のノードに分散配置する。インデックスエントリの配置処理、および検索処理はＣｈｏｒｄの枠組みを利用する。各データオブジェクトはノード単位で管理されるため、データオブジェクトのノード内でのＩＤとそれを格納するノードＩＤのペアが、データオブジェクトを一意に決定するキーとなる。ＣｈｏｒｄのオブジェクトＩＤ（ｏｉｄ）と本発明のデータオブジェクトのＩＤを明確に区別するため、本実施の形態におけるノード内でのデータオブジェクトのＩＤのことをローカルＩＤ（ｌｉｄ）と呼ぶことにする。
【００４６】
ステップＳＴ２及びＳＴ３では、シグネチャ情報の分散配置を行う上での前処理を行う。まず、ステップＳＴ２では図３を用いて説明した手法でオブジェクトシグネチャを生成する。そしてステップＳＴ３では、データオブジェクトから生成したオブジェクトシグネチャを図７に示すように分割フレーム数＝ｓｌｉｃｅ個のフレームシグネチャに分割する（第２の登録ステップ）（Ｚｈｅｎｇ  Ｌｉｎ及びＣｈｒｉｓｔｏｓ  Ｆａｌｏｕｔｓｏｓ著の「Ｆｒａｍｅ−Ｓｌｉｃｅｄ  Ｓｉｇｎａｔｕｒｅ  Ｆｉｌｅｓ」ＩＥＥＥ  ＴＫＤＥ  Ｖｏｌ．４，Ｎｏ．３，ｐｐ．２８１−２８９，１９９２．参照）。分割フレーム数Ｐは、１以上の正の整数である。図７の例では、分割フレーム数＝４であり、１６ビットのデータシグネチャまたはオブジェクトシグネチャ（検索の場合には問合せシグネチャ）の場合、４つの分割フレーム（ｆ０  〜ｆ３  ）が生成され、各分割フレームはそれぞれ４ビットのビット列からなるフレームシグネチャによって構成される。分割フレーム数が１の場合には、フレームシグネチャとオブジェクトシグネチャとが、一致する。特に、ｓｌｉｃｅがシグネチャ長と一致する場合をビットスライス構成と呼ぶ。
【００４７】
次に、ステップＳＴ４で、各フレームシグネチャに番号付けを行う。そして以下のステップＳＴ５からＳＴ１２までのステップで分割フレーム番号をバイナリ表現に変換したビット列と当該分割フレームのフレームシグネチャを結合し、合成シグネチャを得る（第３の登録ステップ）。本実施の形態では、合成シグネチャから長さがｓｃａｌｅビット（ｎ＝４ビット）のｐ個のロケータを生成する。ｐ個のロケータはＩＤサークル上へのインデックスエントリの配置、および検索処理の際に利用する。ロケータの生成方法は次の通りである。まず図７の右上の部分に示すようにｉ＋ｆｉで分割フレームをそれぞれ特定するビット列と、前記フレームシグネチャを構成する長さｍ／ｐのビット列とを合成して各分割フレームに対応する合成シグネチャを作成する（ステップＳＴ７）。そしてこの合成シグネチャの最大上位ｎ個のビット列によってロケータを生成する（ステップＳＴ８〜ＳＴ１２）。ステッすプＳＴ５では、分割フレームのすべてについて処理が終了しているか否かが判定され、すべての処理が終わっていれば終了する。分割フレームについてすべての処理が終了していなければ、ステップＳＴ６へと進む。そしてフレームシグネチャを構成するビット列がすべて０で構成されている場合には、ステップＳＴ１５へと進んで次の分割フレームの処理が行われる。フレームシグネチャを構成するビット列に１が少なくとも１つ含まれていれば、ステップＳＴ７へと進んで合成シグネチャが生成される。生成した合成シグネチャのビット列の長さに応じて、ステップＳＴ８〜ステップＳＴ１２までの処理が実行されてロケータが生成される。ステップＳＴ８からステップＳＴ１１までのステップでは以下のような処理が行われる。
【００４８】
［ケース１］  合成シグネチャ長がｓｃａｌｅ（図７の場合４）と同じ場合、合成シグネチャ自身をロケータとする（ステップＳＴ８，１０，１２）。
【００４９】
［ケース２］  合成シグネチャ長がｓｃａｌｅより大きい場合（図７の場合４より大きい場合）、先頭からｓｃａｌｅ番目（図７の場合４番目までの）プレフィックス（ビット列の先頭からのビット）をロケータとする（ステップＳＴ８，９）。
【００５０】
［ケース３］  合成シグネチャ長がｓｃａｌｅより小さい場合（図７の場合４より小さい場合）、’０’を合成シグネチャに追加することで長さをｓｃａｌｅ（図７の場合ビット数を４）とし、ロケータとする（ステップＳＴ８，１０，１１）。
【００５１】
このロケータ生成方法を用いることにより、任意の分割フレーム数、およびシグネチャ長に対してロケータを生成することができる（第４の登録ステップ）。次に、ステップＳＴ１３へと進んでインデックスエントリが生成される。ステップＳＴ１３では、登録作業を行っている前記ノードのノードＩＤと、登録作業を行っているノード内で登録対象となっているオブジェクトを特定するローカルＩＤと、分割フレームを特定するデータと、フレームシグネチャとからなるインデックスエントリを対応するロケータに対応して作成する（第５の登録ステップ）。そしてステップＳＴ１４で、インデックスエントリをロケータにより指定された１個以上のノードに配置即ち登録する（第６の登録ステップ）。このようなロケータを用いてインデックスエントリを配置することで、各ノードに対して均等にインデックスエントリを配置することができる。なお、ここでノードｎｉにおけるロケータの順序を以下のように定義する。ノードｎｉのノードＩＤをｎｉｄ、ロケータをｌｏｃとした場合に、次のｏｒｄを計算する。
【数３】
2005071115.tif 000005
ロケータの順序は上記式のｏｒｄの昇順とする。
【００５２】
次にインデックスエントリの生成、およびその配置方法についてより詳しく説明する。インデックスエントリは、各フレームシグネチャに対して生成する。ただし、すべてのビットが’０’であるフレームシグネチャに対しては、インデックスエントリは生成しない。インデックスエントリは、当該データオブジェクトのローカルＩＤ、それを格納したノードＩＤ、フレーム番号、およびそのフレームシグネチャから構成される。
【００５３】
あるノードにあるデータオブジェクトが追加された場合のインデックスエントリの配置方法について説明する。本実施の形態では、並列的にインデックスエントリの配置処理を行うことで、配置処理の応答時間を短縮する。まず、各インデックスエントリ中のフレーム番号とフレームシグネチャからロケータを生成する。そして図８に示すように、各インデックスエントリはＣｈｏｒｄのアルゴリズムに従い、ロケータをオブジェクトＩＤとみなして、適当なノードへ配置される。このとき、配置処理を行う必要のある各インデックスエントリを個別に処理するのではなく、まず、データオブジェクトが追加されたノードの持つルーティング情報に基づき、次にフォワードすべきノード毎に各インデックスエントリを分類する。次に、このようにして得られた各インデックスエントリ集合を当該ノードへ送付する。同様の処理を送付されたノードで繰り返し、インデックスエントリの配置を行う。この配置方法では、各ノードが処理するインデックスエントリ配置のためのメッセージ数を最小化することができる。以下では、あるロケータＬｏｃにより配置されているインデックスエントリ集合のことをＬｏｃの配置インデックスエントリ集合と呼ぶ。
【００５４】
次に図６を用いて、オブジェクトを検索するためのインデックスエントリの検索方法を説明する。このオブジェクト検索時においても、問合せ条件として与えられた特徴量から、問合せシグネチャ、フレームシグネチャ、合成シグネチャ、ロケータを順次生成する。ただし、フレームシグネチャがすべて’０’で構成されるものに対してはロケータを生成しない。これらは図６のステップＳＴ２１からステップＳＴ３１によって実現される（第１の検索ステップ）。なおステップＳＴ２１からステップＳＴ３１までは、図５におけるステップＳＴ１からステップＳＴ１３までと実質的に同じである。具体的には、検索作業を行うノードにおいて、検索すべきオブジェクトの１以上の特徴量を長さｍ（ｍは以上の正の整数）のビット列からなる問合せシグネチャとして生成する（第１の問合せエントリ生成ステップＳＴ２１）。そしてこの問合せシグネチャの長さｍのビット列を長さｍ／ｐ（ｐは１以上の正の整数）のビット列からなる問合せフレームシグネチャから構成されたｐ個の分割フレームに分割する（第２の問合せエントリ生成ステップＳＴ２２）。次に、ｐ個の分割フレームをそれぞれ特定するビット列と、問合せフレームシグネチャを構成する長さｍ／ｐのビット列を合成して各分割フレームに対応する合成シグネチャを作成する（第３の問合せエントリ生成ステップＳＴ２６）。そしてこの合成シグネチャを構成するビット列からｎ個のビット列からなるｐ個の問合せロケータを生成する（第４の問合せエントリ生成ステップＳＴ２７〜ＳＴ３１）。この第１の検索ステップは、最初は検索作業を行うノードで実行される。そして以後、ステップＳＴ２４〜ステップＳＴ３１（前述の第１の問合せエントリ生成ステップ乃至前記第４の問合せエントリ生成ステップ）は、前の問合せロケータにより定まる各ノードにおいて実行されて次の問合せロケータが定められる。
【００５５】
ステップＳＴ３２では、最初のノードにおいて、中間結果の集合を初期値にセットする。すなわち格納場所を空の状態にする。そして以後のステップＳＴ３３〜ステップＳＴ４１では、以下のようにインデックスエントリ集合の取得と絞り込みが実施される。まずステップＳＴ３３で、ｐ個の問合せロケータ中の最初の問合せロケータに基づいて検索対象とすべきノードを定めるすべての検索対象ロケータを求めて検索対象ロケータ集合を生成し（ステップＳＴ３６及び３７）、検索作業を行うノードのノードＩＤ及びすべての問合せフレームシグネチャを含む問合せデータ（すなわち部分問合せエントリ）を検索対象ロケータ集合の最初の検索対象ロケータにより定まるノードに送る（ステップＳＴ３３：第１のステップ）。そして次にステップＳＴ３４に進んで、最初のノードにおいて、最初の検索対象ロケータに対応する問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを取得して部分インデックスエントリ候補集合とする（第２のステップ）。次に、次の検索対象ロケータにより定まる次のノードに問合せデータとインデックスエントリ候補を送る（ステップＳＴ３６及び３７：第３のステップ）。そして次のノードにおいて、次の検索対象ロケータに対応する問合せフレームシグネチャの条件を満たすすべてのインデックスエントリを取得し（ステップＳＴ３３）且つ該インデックスエントリ集合と部分インデックスエントリ候補集合との和集合を取ってその結果を次の部分インデックスエントリ候補集合とする（ステップＳＴ３４及び３５：第４のステップ）。最後の検索対象ロケータに到るまで第３のステップ及び第４のステップを繰り返し最後の部分インデックスエントリ候補集合をインデックスエントリ候補集合とする（第５のステップ）。これら第１乃至第５のステップは、図６のステップＳＴ３３〜ＳＴ３７で実行される。なおステップＳＴ３６では、順次ロケータを計算するため、ロケータのフレームシグネチャ部分がすべて‘１’になった場合を終了条件となる。
【００５６】
そしてステップＳＴ３８で、最初の問合わせロケータの処理であったか否かの判定が行われ、最初の問合わせロケータの処理であれば、ステップＳＴ３９へと進んで収集したインデックスエントリ候補をそのまま次の問合せロケータにより定まるノードに送出する（ステップＳＴ４０、ＳＴ４２、ＳＴ２４〜ＳＴ３１）。
【００５７】
次にｐ個の問合せロケータ中の次の問合せロケータから検索対象ロケータ集合を生成し、問合せデータ及びインデックスエントリ候補集合を該検索対象ロケータ集合の最初の検索対象ロケータにより定まる次のノードに送る（ステップＳＴ３９及びＳＴ４０：第６のステップ）。次のノードからはじめて検索対象ロケータ集合の最後の検索対象ロケータに到るまで前述の第２のステップ及び第３のステップ及び第４のステップ及び第５のステップを繰り返しその結果得られたインデックスエントリ候補集合と本ステップ開始時のインデックスエントリ候補集合の積集合（ステップＳＴ４１）をとってその結果を次のインデックスエントリ候補集合とする（第７のステップ：ステップＳＴ２４〜ステップＳＴ３８、ステップＳＴ４１）。そして最後の問合せロケータに到るまで第６のステップ及び第７のステップを繰り返し、最終結果を解として検索作業を行うノードに送信する（第８のステップ：ステップＳＴ２４及びＳＴ４３）。
【００５８】
前述の部分問合せエントリはロケータ、フレーム番号、フレームシグネチャから構成される。問合せはこれらの部分問合せエントリを順次照合することで処理される。この処理は、時計回りに問合せ処理を行う上で参照すべきインデックスエントリを持つノードを順次巡回していくことで行う。この場合、照合処理による解の絞り込みが順次行われるため、中間結果のデータ転送量が小さくなることが期待される。
【００５９】
図９が上記の第１及び第２の検索ステップを別に表現した検索アルゴリズムである。まず、問合せから部分問合せエントリ集合が生成される（１行目）。各部分問合せエントリは、問合せが発生したノードにおけるロケータの順序に従い、より小さいロケータを持つ順に処理する（２行目）。次に、部分問合せエントリのロケータから検索対象ロケータ集合を生成する（３行目）。検索対象ロケータ集合は、ロケータの中にあるフレームシグネチャ中の’０’を’０’または’１’としたすべてのビット列の集合である（したがって次式を満たす。検索対象ロケータ集合の各要素Λ＊（Λはビット論理積を表す）ロケータ＝ロケータ）この時点では部分問合せエントリに対する検索処理は何も行われていないため、解侯補集合は空集合である（４行目）。ただし解侯補集合とは、ノードＩＤとローカルＩＤのペアを要素とする集合である。次に、検索対象ロケータ集合の各要素に対して、そのロケータの配置インデックスエントリ集合を保持するノードに、その時点の解侯補集合、未処理の部分問合せエントリ集合、未処理の検索対象ロケータ集合を送付する。ただし、検索対象ロケータ集合からのロケータ選択は、そのノードにおけるロケータの順序に従う。これらを受け取ったノードでは、自分の保持する配置インデックスエントリ集合の中で、以下の２つの条件を満たすインデックスエントリを選択し（６行目）、その中のノードＩＤとローカルＩＤのペアを解侯補集合に加える（７行目）。
【００６０】
［条件１］  部分問合せエントリ中のフレーム番号＝インデックスエントリ中のフレーム番号。
【００６１】
［条件２］  部分問合せエントリ中のフレームシグネチャΛインデックスエントリ中のフレームシグネチャ＝部分問合せエントリ中のフレームシグネチャ。
【００６２】
すべての検索対象ロケータ集合の各要素について解侯補集合の取得処理が終了した時点で、当該部分問合せエントリに関する処理が終了する。このあと、これまで計算された解Ａｎｓと解侯補集合との集合の積をとり、解の絞り込み処理を行う（１１行目）。この処理をすべての部分問合せエントリに対して行った後、開始ノードにＡｎｓを返す（１２行目）。
【００６３】
図１０の問合せを例として説明する。まず、ノードｎ４で問合せが発生するものとする。問合せ処理はノードｎ４におけるロケータの順序に従い、部分問合せエントリｄ０から開始される。ｄ０から検索対象ロケータ集合ｄ０Ｓｅｔ｛’００１０’，’００１１’｝が生成され、’００１０’の配置インデックスエントリ集合の有無を調べる。ノードｎ４には、’００１０’の配置インデックスエントリ集合は存在しない。このため、ルーティング情報を用いることで’００１０’の配置インデックスエントリ集合が存在するノードｎ１を辿る。このとき未処理部分問合せエントリ集合｛ｄ０、ｄ２｝、未処理検索対象ロケータ集合ｄ０Ｓｅｔ、解侯補集合をノードｎ１に送付する。ノードｎ１では、ｄ０Ｓｅｔ中の全ロケータ（’００１０’と’００１１’）の配置インデックスエントリ集合を持つため、これらを用いた解侯補集合を獲得する。この時点で、ｄ０Ｓｅｔ中のすべてのロケータに対する処理は終了となるため、ｄ０に対する処理は終了する。次に未処理の部分問合せエントリｄ２から検索対象ロケータ集合ｄ２Ｓｅｔ｛’１０００’，’１０１０’，’１００１’，’１０１１’｝が生成され、’１０００’の配置インデックスエントリ集合の有無を調べる。ノードｎ１には、’１０００’の配置インデックスエントリ集合は存在せず、ルーティング情報を使って配置インデックスエントリ集合の存在するノードｎ３を辿る。このとき、未処理部分問合せエントリ集合｛ｄ２｝、未処理検索対象ロケータ集合ｄ２Ｓｅｔ、解集合Ａｎｓをノードｎ３に送付する。ノードｎ３には、ｄ２Ｓｅｔ中のすべてのロケータの配置インデックスエントリ集合が存在し、ｄ２に対する処理は終了する。ここでＡｎｓの再計算を行う。この段階でシグネチャの照合処理は終了し、開始ノードｎ４へ検索結果であるＡｎｓが返される。
【００６４】
開始ノードｎ４では検索結果Ａｎｓ中の全要素に対応するデータオブジェクトを取得し、最後にフォールスドロップレゾリューションを行い、問合せに対する最終的な解を得る。
【００６５】
以下、上記の実施の形態を評価した実験について説明する。実験では、シミュレーションに基づく本実施の形態の方法の評価実験を行った。実験では、１）検索に必要なメッセージ数、総データ転送量、応答時間、２）オブジェクトの追加に伴うインデックスエントリの更新のためのメッセージ数と応答時間、３）検索と追加が混在する場合でのメッセージ数、４）オフラインノードが存在する場合の検索の精度を測定する。先に述べたように、検索コストと追加コストの間にはトレードオフの関係があり、分割フレーム数はそのコストに大きな影響を与えるパラメータである。その関係を確認するのが、実験  １）  ２）  ３）の主な目的である。また、シグネチャを用いた検索の特徴の１つとして、全てのフレームシグネチャを参照しなくとも対象オブジェクトの絞り込みが可能な点がある。この特徴により、仮に必要なインデックスエントリを保持するノードがオフラインであっても、残りのオンラインノードのもつインデックスエントリのみで絞り込み処理を行うことが可能である。この点を確認するのが実験  ４）の目的である。実験時の主なパラメタを表１、表２に示す。
【表１】
2005071115.tif 000006
【表２】
2005071115.tif 000007
シグネチャ長およびウェイトについては、表２に示す３通りについて実験を行う。データオブジェクトの特徴量の数を１６４とした場合、特徴量１個に基づく問合せに対するフォールスドロップ確率はこの３通りのいずれの場合も約５％となる。応答時間の測定では、ノード間で、あるメッセージを転送するために必要な転送時間を単位時間とする。その他の処理時間は、メッセージ転送に必要な時間と比較した場合に非常に小さくなると考えられるため、考慮しない。
【００６６】
［オブジェクト検索］
まず最初に、検索を行う際のメッセージ数、総データ転送量、応答時間の評価を行う。分割フレーム数ｓｌｉｃｅ、およびシグネチャ長Ｆを変化させて実験を行う。ノード数は１２８とし、問合せの特徴量は２、４、６と変化させる。既に述べたように、分割フレーム数を増加させた方が検索コストは減少することが予想される。また、シグネチャ長を大きくした場合には、問合せシグネチャのウェイトが小さくなるため、参照する必要のあるフレームシグネチャの数が減少し検索コストも小さくなることが予想される。一方、問合せ特徴量の数を大きくした場合には、問合せシグネチャのウェイトも大きくなり、検索コストは大きくなると考えられる。実験では、問合せを各５０回実行したときの平均を測定値とする。データ転送量を測る際、インデックスエントリの各要素のサイズについてはｎｉｄが６［Ｂｙｔｅ］、ｌｉｄが４［Ｂｙｔｅ］とする。フレーム番号のサイズとフレームシグネチャのサイズについてはｓｌｉｃｅの値によって変化する。ｓｌｉｃｅの値を表現するために必要なビット数をｂｉｔ＿ｓｌｉｃｅとした場合、フレーム番号に必要なサイズは［ｂｉｔ＿ｓｌｉｃｅ／８］［Ｂｙｔｅ］（［］はｘ以上の最小の整数を表す）、フレームシグネチャに必要なサイズは［Ｆ／ｂｉｔ＊ｓｌｉｃｅ］［Ｂｙｔｅ］である。
【００６７】
図１１は平均メッセージ数である。メッセージ数は、分割フレーム数が大きくなると減少している。これは、問合せシグネチャを分割したときに、解の判定を行う必要のないフレームシグネチャ（すべて’０’で構成されるフレームシグネチャ）が高い確率で出現するため、メッセージ数の削減につながっている。さらにフレームシグネチャ長も小さくなるため、検索対象ロケータ集合の要素数も小さくなり、辿らなければならないノードの数も減少する。これらの理由により、メッセージ数が大幅に削減される。
【００６８】
総データ転送量に関しても同様の傾向がある（図１２）。フレーム分割を行わない場合（分割フレーム数２０にデータ転送量が小さいのは、単一のインデックスエントリのみでデータオブジェクトのオブジェクトシグネチャ全体が得られるため、解の絞り込みが瞬時に行えることによる。分割フレーム数が２１以上の付近で総データ転送量が大きくなっているのは、順次巡回による十分な解の絞り込みが行えないため中間結果のデータ転送量が大きくなり、検索に必要なメッセージ数も大きくなっているためである。
【００６９】
応答時間について説明する。本提案手法では、各ノードを順次巡回することで検索を行っており、全ての絞り込み処理が終了した時点で結果を返す。このため応答時間は、検索時のメッセージ数（図１１）と同一の曲線となる。この場合についても分割フレーム数を大きくした場合の方が優れている。
【００７０】
実験結果より、検索時のメッセージ数に関しては分割フレーム数が大きくなる程効率的であることが分かる。また、シグネチャのウェイトを小さくすることで、メッセージ数を低減できることを確認できる。
【００７１】
［オブジェクト追加］
次に新規にデータオブジェクトが追加される場合の、インデックスエントリの配置に必要なメッセージ数とその応答時間について測定する。実験では、分割フレーム数とシグネチャ長Ｆを変化させ、ノード数は１２８、２５６と変化させて行う。配置方法即ち登録方法は先に述べた方法に基づいて行う。既に述べたように、分割フレーム数を増加させた方が追加の際に必要なメッセージ数は増加することが予想される。また、オブジェクト検索時と同様に、シグネチャ長を大きくした場合の方が、インデックスエントリの配置に必要なメッセージ数は小さくなることが予想される。
【００７２】
図１３は平均メッセージ数である。分割フレーム数が大きくなるほど、メッセージ数が大きくなっていることがわかる。この理由は、分割フレーム数が大きくなるほど、新たに配置する必要のあるインデックスエントリ数が多くなるからである。シグネチャのウェイトを小さくした場合には相対的にメッセージ数が小さくなっている。これは、配置する必要のあるインデックスエントリの数が小さくなるからである。
【００７３】
さらに応答時間についても測定する。図１４が実験結果である。インデックスエントリの配置では並列的な処理を行うため、分割フレーム数の増大によるインデックスエントリ数の増大に対し、応答時間の増加曲線は緩やかである。また、どのシグネチャ長の場合も応答時間はほとんど変化していないことがわかる。
【００７４】
このように、分割フレーム数を大きくした場合にはメッセージ数は非常に大きくなる傾向にあるが、応答時間で見た場合には、フレーム分割を行わない場合と比べてもそれほど大きな差はない。
【００７５】
［検索と追加が混在する場合］
オブジェクトの検索処理、およびオブジェクトの追加処理の発生頻度を考慮した場合の平均メッセージ数について検討する。ここでは検索処理の生起確率がｐであるものとし、追加処理の生起確率が（１−ｐ）であるものとする。実験ではノード数を１２８とし、分割シグネチャとシグネチャ長を変化させ、そのときの検索時のメッセージ数と追加時のメッセージ数にそれぞれの生起確率をかけて合計したものを平均メッセージ数とする。
【００７６】
図１５が実験結果である。一般的に検索処理の方が、追加処理と比べて多く発生すると考えられるため、ｐを０．７、０．８、０．９と変化させる。ｐ＝０．７の場合は、分割フレーム数が２４の辺りでメッセージ数が最も小さくなる。また、ｐ＝０．８の場合は、分割フレーム数が２５の辺りでメッセージ数が最も小さくなっており、ｐ＝０．９の場合では、分割フレーム数が２５以上であれば、最小となるメッセージ数はほぼ一定になっていることがわかる。このように、検索と追加の発生割合に応じて、最適の分割フレーム数が異なってくる。
【００７７】
［オフラインノードが存在する場合の検索の精度］
最後に、所定の割合のノードがオフラインの状態にあり、シグネチャの照合処理が正しく行えないと仮定した場合における、検索の精度について実験を行う。なお、Ｃｈｏｒｄの枠組みではオフラインノードが存在する場合でもルーティング情報を動的に更新することができる。このため、ルーティング情報は常に正しく利用できるものと仮定する。本実験では、問合せを実行した場合のフォールスドロップ確率を計算する。オフラインノードが存在する場合には、これらのオフラインノードに存在するフレームシグネチャとの照合ができないため、フォールスドロップ数が大きくなることが予想される。
【００７８】
実験では、問合せ特徴量の数を１とし、分割フレーム数ｓｌｉｃｅを２０、２４、２８と変化させフォールスドロップ確率を求める。また、ノード数は１２８とし、正しく照合処理が行えないノードの割合を０％から最大５０％まで２．５％ずつ変化させる。
【００７９】
図１６が実験結果である。オフラインノードの割合が大きくなるにつれて、フォールスドロップ確率も増加することを確認できる。分割フレーム数を大きくした場合の方が、フォールスドロップ確率の増加曲線は緩やかになっている。この理由は、分割フレーム数を大きくすることでフレームシグネチャのサイズが小さくなり、照合することができないシグネチャのサイズが小さくなるからであると考えられる。このように、オフラインノードが存在する状況下でも、分割フレーム数を大きくすることで一定水準の検索の精度を維持することができる。
【図面の簡単な説明】
【００８０】
【図１】Ｃｈｏｒｄアーキテクチャを説明するために用いる図である。
【図２】Ｃｈｏｒｄによる検索処理を説明するために用いる図である。
【図３】オブジェクトシグネチャの生成法を説明するために用いる図である。
【図４】問合せシグネチャの生成法を説明するために用いるである。
【図５】本発明の方法の実施の形態を実施するために用いるプログラムにおける登録処理のアルゴリズムを示すフローチャートである。
【図６】プログラムにおける検索処理のアルゴリズムを示すフローチャートである。
【図７】ロケータの生成法を説明するためにいる図である。
【図８】インデックスエントリの配置を説明するために用いる図である。
【図９】検索アルゴリズムを表にした図である。
【図１０】オブジェクト検索を説明するために用いる図である。
【図１１】検索時の平均メッセージ数についての実験結果を示す図である。
【図１２】検索時の平均総データ転送量についての実験結果を示す図である。
【図１３】配置時の平均メッセージ数についての実験結果を示す図である。
【図１４】配置時の平均応答時間についての実験結果を示す図である。
【図１５】検索と追加が混在する場合のメッセージ数についての実験結果を示す図である。
【図１６】オフラインノードがあるときのフォールスドロップ確率についての実験結果を示す図である。
【図１】
2005071115.tif 000008
【図２】
2005071115.tif 000009
【図３】
2005071115.tif 000010
【図４】
2005071115.tif 000011
【図５】
2005071115.tif 000012
【図６】
2005071115.tif 000013
【図７】
2005071115.tif 000014
【図８】
2005071115.tif 000015
【図９】
2005071115.tif 000016
【図１０】
2005071115.tif 000017
【図１１】
2005071115.tif 000018
【図１２】
2005071115.tif 000019
【図１３】
2005071115.tif 000020
【図１４】
2005071115.tif 000021
【図１５】
2005071115.tif 000022
【図１６】
2005071115.tif 000023