(57)【要約】【課題】多次元属性のデータ検索を効率よく高速に実行することができる。【解決手段】ネットワーク１００上に複数のピア１１０，１２０・・・が接続されている。各ピア１１０，１２０・・・は既存のネットワーク１００の上位層のオーバレイネットワーク（Ｐ２Ｐネットワーク）上で互いにデータを共有している。各ピア１１０，１２０・・・は、それぞれ、複数属性のデータを一次元の値に変換し、一次元化した値に対して分布関数を適用して論理識別子を生成し、オーバレイネットワーク上の各ピア１１０，１２０・・・に対する論理識別子の割り当てにもとづいて、生成した論理識別子を管理する他のピアを特定し、特定した他のピアにデータを登録する処理を実行する。【選択図】図１
2008234563.tif 000002
【特許請求の範囲】
【請求項１】
オーバレイネットワーク上に配置され、他の装置と共有するデータを管理するオーバレイ管理装置であって、
複数属性のデータを一次元の値に変換する一次元化手段と、
前記一次元化手段によって一次元化された値に対して、値の分布情報を含む関数を適用して論理識別子を生成する識別子生成手段と、
オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、前記識別子生成手段にて生成された論理識別子を管理する他の装置を特定する管理装置特定手段と、
前記管理装置特定手段によって特定された前記他の装置にデータを登録する処理を実行するデータ登録手段とを備えた
ことを特徴とするオーバレイ管理装置。
【請求項２】
複数属性の検索条件を一次元の値の集合に変換する検索条件一次元化手段と、
前記検索条件一次元化手段によって一次元化された値の集合内の要素に対して、値の分布情報を含む関数を適用して論理識別子の範囲の集合を生成する識別子範囲生成手段と、
前記識別子範囲生成手段にて生成された論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行う検索要求転送手段とを備えた
請求項１記載のオーバレイ管理装置。
【請求項３】
オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、論理識別子の範囲の集合を分割する論理識別子範囲分割手段を備え、
検索要求転送手段は、前記論理識別子範囲分割手段によって分割された論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行う
請求項２記載のオーバレイ管理装置。
【請求項４】
一次元化手段または検索条件一次元化手段は、空間充填曲線を用いて複数属性のデータを一次元の値または値の集合に変換し、
識別子生成手段または識別子範囲生成手段は、前記空間充填曲線にて一次元化された値または値の集合を均一化する空間充填曲線分布関数を適用して一次元化された値または値の集合から論理識別子またはその範囲の集合を生成する
請求項１から請求項３のうちのいずれか１項に記載のオーバレイ管理装置。
【請求項５】
論理識別子範囲分割手段は、ルーティングテーブルに格納された論理識別子にもとづいて、論理識別子の範囲の集合を分割する
請求項３または請求項４記載のオーバレイ管理装置。
【請求項６】
オーバレイネットワーク上に配置された複数の端末を備え、各端末間で共有するデータを管理するオーバレイ管理システムであって、
前記各端末は、
複数属性のデータを一次元の値に変換する一次元化手段と、
前記一次元化手段によって一次元化された値に対して、値の分布情報を含む関数を適用して論理識別子を生成する識別子生成手段と、
前記各端末に対する論理識別子の割り当てにもとづいて、前記識別子生成手段にて生成された論理識別子を管理する他の端末を特定する管理端末特定手段と、
前記管理端末特定手段によって特定された前記他の端末にデータを登録する処理を実行するデータ登録手段とを備えた
ことを特徴とするオーバレイ管理システム。
【請求項７】
各端末は、
複数属性の検索条件を一次元の値の集合に変換する検索条件一次元化手段と、
前記検索条件一次元化手段によって一次元化された値の集合内の要素に対して、値の分布情報を含む関数を適用して論理識別子の範囲の集合を生成する識別子範囲生成手段と、
前記識別子範囲生成手段にて生成された論理識別子の範囲の集合を他の端末に検索要求として転送することによりデータの検索を行う検索要求転送手段とを備えた
請求項６記載のオーバレイ管理システム。
【請求項８】
各端末に対する論理識別子の割り当てにもとづいて、論理識別子の範囲の集合を分割する論理識別子範囲分割手段を備え、
検索要求転送手段は、前記論理識別子範囲分割手段によって分割された論理識別子の範囲の集合を他の端末に検索要求として転送することによりデータの検索を行う
請求項７記載のオーバレイ管理システム。
【請求項９】
一次元化手段または検索条件一次元化手段は、空間充填曲線を用いて複数属性のデータを一次元の値または値の集合に変換し、
識別子生成手段または識別子範囲生成手段は、前記空間充填曲線にて一次元化された値または値の集合を均一化する空間充填曲線分布関数を適用して一次元化された値または値の集合から論理識別子またはその範囲の集合を生成する
請求項６から請求項８のうちのいずれか１項に記載のオーバレイ管理システム。
【請求項１０】
論理識別子範囲分割手段は、ルーティングテーブルに格納された論理識別子にもとづいて、論理識別子の範囲の集合を分割する
請求項８または請求項９記載のオーバレイ管理システム。
【請求項１１】
オーバレイネットワーク上に配置された管理装置の制御部が制御プログラムに従って、
複数属性のデータを一次元の値に変換し、
一次元化した値に対して、値の分布情報を含む関数を適用して論理識別子を生成し、
オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、生成した論理識別子を管理する他の装置を特定し、
特定した前記他の装置にデータを登録する処理を実行する
ことを特徴とするオーバレイ管理方法。
【請求項１２】
オーバレイネットワーク上に配置された管理装置の制御部が制御プログラムに従って、
複数属性の検索条件を一次元の値の集合に変換し、
一次元化した値の集合内の要素に対して、値の分布情報を含む関数を適用して論理識別子の範囲の集合を生成し、
生成した論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行う
請求項１１記載のオーバレイ管理方法。
【請求項１３】
オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、論理識別子の範囲の集合を分割し、
分割した論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行う
請求項１２記載のオーバレイ管理方法。
【請求項１４】
空間充填曲線を用いて複数属性のデータを一次元の値または値の集合に変換し、
前記空間充填曲線にて一次元化された値または値の集合を均一化する空間充填曲線分布関数を適用して一次元化された値または値の集合から論理識別子またはその範囲の集合を生成する
請求項１１から請求項１３のうちのいずれか１項に記載のオーバレイ管理方法。
【請求項１５】
ルーティングテーブルに格納された論理識別子にもとづいて、論理識別子の範囲の集合を分割する
請求項１３または請求項１４記載のオーバレイ管理方法。
【請求項１６】
オーバレイネットワーク上に配置された管理装置が他の装置と共有するデータを管理するためのオーバレイ管理用プログラムであって、
複数属性のデータを一次元の値に変換する一次元化処理と、
一次元化した値に対して、値の分布情報を含む関数を適用して論理識別子を生成する識別子生成処理と、
オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、生成した論理識別子を管理する他の装置を特定する管理装置特定処理と、
特定した前記他の装置にデータを登録する処理を実行するデータ登録処理とを
前記管理装置に実行させるためのオーバレイ管理用プログラム。
【請求項１７】
複数属性の検索条件を一次元の値の集合に変換する検索条件一次元化処理と、
一次元化した値の集合内の要素に対して、値の分布情報を含む関数を適用して論理識別子の範囲の集合を生成する識別子範囲生成処理と、
生成した論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行う検索要求転送処理とを
前記管理装置に実行させる請求項１６記載のオーバレイ管理用プログラム。
【請求項１８】
オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、論理識別子の範囲の集合を分割する論理識別子範囲分割処理を管理装置に実行させ、
検索要求転送処理において、分割した論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行わせる
請求項１７記載のオーバレイ管理用プログラム。
【請求項１９】
一次元化処理または検索条件一次元化処理において、空間充填曲線を用いて複数属性のデータを一次元の値または値の集合に変換させ、
識別子生成処理または識別子範囲生成処理において、前記空間充填曲線にて一次元化された値または値の集合を均一化する空間充填曲線分布関数を適用して一次元化された値または値の集合から論理識別子またはその範囲の集合を生成させる
請求項１６から請求項１８のうちのいずれか１項に記載のオーバレイ管理用プログラム。
【請求項２０】
論理識別子範囲分割処理において、ルーティングテーブルに格納された論理識別子にもとづいて、論理識別子の範囲の集合を分割させる
請求項１８または請求項１９記載のオーバレイ管理用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オーバレイネットワークに配置された各端末で共有するデータを管理するオーバレイ管理装置、オーバレイ管理システム、オーバレイ管理方法およびオーバレイ管理用プログラムに関し、特に多次元情報を、均一かつ連続性を保持しつつ論理識別子を算出できるオーバレイ管理装置、オーバレイ管理システム、オーバレイ管理方法およびオーバレイ管理用プログラムに関する。
【背景技術】
【０００２】
オーバレイネットワークとは、既存のリンクを用いて、その上位層における目的に応じて仮想的なリンクを形成し構成するネットワークである。すなわち、コンピュータネットワークの下位層のトポロジーとは関係なく構築された上位層のネットワークをオーバーレイ・ネットワークと呼ぶ。例えば、ＩＰネットワークのトポロジーとは無関係に構築されたＰ２Ｐ（Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ）ネットワークなどを指す。
【０００３】
オーバレイネットワークの技術を利用すると、センターサーバ（中央サーバ）を用いることなく、複数のピア（ノードともいう）に分散してデータを保持させることにより、広域でデータを共有するデータベースを実現することができる。特に、連想配列（ハッシュテーブル）を実現する手法として、分散ハッシュテーブル（Ｄｉｓｔｒｉｂｕｔｅｄ  Ｈａｓｈ  Ｔａｂｌｅ：ＤＨＴ）がある。オーバレイネットワーク上で分散ハッシュテーブルを構築することで膨大なデータを高速に検索可能となる。
【０００４】
分散ハッシュテーブルの概要について説明する。まず、オーバレイネットワーク上に複数のピアが存在しているものとする。ピアが保持しているコンテンツの名前（キーワード）はハッシュ関数を使用してハッシュ値に変換される（数値化される）。例えば、ピアがＡという名前のコンテンツを持っている場合は、Ａはハッシュ値ｈａｓｈ（Ａ）に変換される。
【０００５】
ピアがオーバレイネットワークに参加するときに、ピアはランダムなノードＩＤ（Ｎｏｄｅ＿ＩＤ）を決定し保持する。そして、ピアがＡという名前のコンテンツを持っている場合、そのピアはＮｏｄｅ＿ＩＤ＝ｈａｓｈ（Ａ）であるピア（ノード）にＡのハッシュ値｛ｈａｓｈ（Ａ）｝と自身のＩＰアドレス｛ＩＰ＿Ａｄｒｅｓｓ｝の組である｛ｈａｓｈ（Ａ），ＩＰ＿Ａｄｒｅｓｓ｝を通知して登録する。仮に、Ｎｏｄｅ＿ＩＤ＝ｈａｓｈ（Ａ）となるピアがなければ、ｈａｓｈ（Ａ）に一番近いＮｏｄｅ＿ＩＤであるピアが｛ｈａｓｈ（Ａ），ＩＰ＿Ａｄｒｅｓｓ｝を登録することになる。ユーザ（検索者）が例えばＣという名前のコンテンツを欲しい場合、Ｎｏｄｅ＿ＩＤ＝ｈａｓｈ（Ｃ）であるピアに問い合わせれば、それを所有しているピアのＩＰアドレスがわかることになる。
【０００６】
なお、分散ハッシュテーブルには、Ｃｈｏｒｄ（円状）、ＣＡＮ（Ｎ次元トーラス）、Ｋａｄｅｍｌｉａ、Ｐ−Ｇｒｉｄ（２分木）、Ｔａｐｅｓｔｒｙ，Ｐａｓｔｒｙ（Ｐｌａｘｔｏｎアルゴリズム）という手法が存在する。分散ハッシュテーブルの中でも最も一般的なＣｈｏｒｄについては後述する。
【０００７】
このような構成によれば、センターサーバがなくても高速にコンテンツを検索することができ、そのコンテンツを所有するピアのＩＰアドレスを見つけることができる。
【０００８】
オーバレイネットワークを利用した従来技術が以下に示す特許文献に開示されている。
【０００９】
特許文献１に記載されたシステムでは、端末が自端末の物理的情報を収集して公開し、他端末の物理的情報を収集し、収集した物理的情報にもとづいてピアごとの信頼度を計算し、信頼度に応じて接続管理を行い、ネットワークトポロジを決定し、トラヒック変動を検知して接続を変更する技術が開示されている。
【００１０】
特許文献２には、未参加ノードが、オーバレイネットワークに参加している複数の参加ノードからの返信パケットにもとづいて、返信パケットを返信した参加ノードと自己との間の通信経路における通信負荷に関する情報を取得し、取得した情報にもとづいてネットワーク的に近い参加ノードを選定して、その参加ノードに対して参加要求を行ってオーバレイネットワークに参加する構成が開示されている。
【００１１】
また、特許文献３には、オーバレイネットワークが複数のゾーンを有するように形成され、一のノードと他のノードとの間の通信経路における通信負荷が所定範囲の場合には、一のノードと他のノードとをオーバレイネットワークにおいて同一のゾーンに所属するように配置させる構成が開示されている。
【００１２】
【特許文献１】特開２００５−２５２５９６号公報
【特許文献２】特開２００６−１９１４８９号公報
【特許文献３】特開２００６−２１７５３８号公報
【非特許文献１】Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｆｏｒｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｇｒｉｄ  Ｃｏｍｐｕｔｉｎｇ、“ＭＡＡＮ：Ａ  Ｍｕｌｔｉ−Ａｔｔｒｉｂｕｔｅ  Ａｄｄｒｅｓｓａｂｌｅ  Ｎｅｔｗｏｒｋ  ｆｏｒ  Ｇｒｉｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｒｖｉｃｅｓ”
【非特許文献２】Ｈｔｔｐ:／／ａｎｄｙ．ｕｓｃ．ｅｄｕ／〜ｍｃａｉ／ｐａｐｅｒｓ／ｍａａｎ．ｐｄｆ，“ＭＡＡＮ：Ａ  Ｍｕｌｔｉ−Ａｔｔｒｉｂｕｔｅ  Ａｄｄｒｅｓｓａｂｌｅ  Ｎｅｔｗｏｒｋ  ｆｏｒ  Ｇｒｉｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｒｖｉｃｅｓ”
【非特許文献３】Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２００１  ＳＩＧＣＯＭＭ  Ｃｏｎｆｅｒｅｎｃｅ，“Ｃｈｏｒｄ：  Ａ  Ｓｃａｌａｂｌｅ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｌｏｏｋｕｐ  Ｓｅｒｖｉｃｅ  Ｆｏｒ  Ｉｎｔｅｒｎｅｔ  Ａｐｐｌｉｃａｔｉｏｎｓ”
【非特許文献４】ＩＥＥＥ  Ｉｎｔｅｒｎｅｔ  Ｃｏｍｐｕｔｉｎｇ，”Ｅｎａｂｌｉｎｇ  Ｆｌｅｘｉｂｌｅ  Ｑｕｅｒｉｅｓ  ｗｉｔｈ  Ｇｕａｒａｎｔｅｅｓ  ｉｎ  Ｐ２Ｐ  Ｓｙｓｔｅｍｓ”
【非特許文献５】Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔｉｎｇ，“Ｆｌｅｘｉｂｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｄｉｓｃｏｖｅｒｙ  ｉｎ  Ｄｅｃｅｎｔｒａｌｉｚｅｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ”
【発明の開示】
【発明が解決しようとする課題】
【００１３】
ところで、ユーザは、多次元属性の検索条件にもとづいてデータ検索を行うことも考えられる。例えば、コンピュータのＣＰＵスピードという属性とメモリサイズという属性の検索条件にもとづいてデータ検索を実行するような場合である。しかし、上記の特許文献１〜３にはオーバレイネットワーク上の通信負荷を軽減する技術が開示されているが、多次元属性（複数属性）のデータ検索を実現する技術については開示されていない。
【００１４】
本発明の目的は、上記のような課題を解決するためになされたものであり、多次元属性のデータ検索を効率よく高速に実行することができるオーバレイ管理装置、オーバレイ管理システム、オーバレイ管理方法およびオーバレイ管理用プログラムを得ることを目的とする。
【課題を解決するための手段】
【００１５】
以上の目的を達成するため、本発明によるオーバレイ管理装置は、オーバレイネットワーク上に配置され、他の装置と共有するデータを管理するオーバレイ管理装置であって、複数属性のデータを一次元の値に変換する一次元化手段と、一次元化手段によって一次元化された値に対して、値の分布情報を含む関数を適用して論理識別子を生成する識別子生成手段と、オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、識別子生成手段にて生成された論理識別子を管理する他の装置を特定する管理装置特定手段と、管理装置特定手段によって特定された他の装置にデータを登録する処理を実行するデータ登録手段とを備えたことを特徴とする。
【００１６】
複数属性の検索条件を一次元の値の集合に変換する検索条件一次元化手段と、検索条件一次元化手段によって一次元化された値の集合内の要素に対して、値の分布情報を含む関数を適用して論理識別子の範囲の集合を生成する識別子範囲生成手段と、識別子範囲生成手段にて生成された論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行う検索要求転送手段とを備えていてもよい。この構成によれば、複数属性からなる１つのデータを１つの装置に登録する場合において、特定の装置に検索要求の転送負荷が集中するのを防止することができる。
【００１７】
オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、論理識別子の範囲の集合を分割する論理識別子範囲分割手段を備え、検索要求転送手段は、論理識別子範囲分割手段によって分割された論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行うように構成されていてもよい。この構成によれば、検索範囲の広い場合にも検索要求のホップ数が増加しないようにすることができ、その結果、高速な検索、通信負荷の軽減なども図ることができる。
【００１８】
一次元化手段または検索条件一次元化手段は、空間充填曲線を用いて複数属性のデータを一次元の値または値の集合に変換し、識別子生成手段または識別子範囲生成手段は、空間充填曲線にて一次元化された値または値の集合を均一化する空間充填曲線分布関数を適用して一次元化された値または値の集合から論理識別子またはその範囲の集合を生成するように構成されていてもよい。この構成によれば、検索要求（検索メッセージ）を転送する論理識別子の範囲を狭くすることができるとともに（例えば、図１８に示すようにｘ属性とｙ属性をともに満たす要素数に検索メッセージを伝播させることができる）、オーバレイネットワーク上の各装置にデータ管理負荷が集中しないようにすることができる。
【００１９】
論理識別子範囲分割手段は、ルーティングテーブルに格納された論理識別子にもとづいて、論理識別子の範囲の集合を分割するように構成されていてもよい。この構成によれば、適切な範囲に論理識別子の範囲の集合を分割することができ、その結果、より一層高速な検索を実現することができる。なお、ルーティングテーブルには、例えばＣｈｏｒｄで用いるフィンガーテーブルやサクセッサーリストなどが含まれる。
【００２０】
本発明によるオーバレイ管理システムは、オーバレイネットワーク上に配置された複数の端末を備え、各端末間で共有するデータを管理するオーバレイ管理システムであって、各端末は、複数属性のデータを一次元の値に変換する一次元化手段と、一次元化手段によって一次元化された値に対して、値の分布情報を含む関数を適用して論理識別子を生成する識別子生成手段と、各端末に対する論理識別子の割り当てにもとづいて、識別子生成手段にて生成された論理識別子を管理する他の端末を特定する管理端末特定手段と、管理端末特定手段によって特定された他の端末にデータを登録する処理を実行するデータ登録手段とを備えたことを特徴とする。
【００２１】
各端末は、複数属性の検索条件を一次元の値の集合に変換する検索条件一次元化手段と、検索条件一次元化手段によって一次元化された値の集合内の要素に対して、値の分布情報を含む関数を適用して論理識別子の範囲の集合を生成する識別子範囲生成手段と、識別子範囲生成手段にて生成された論理識別子の範囲の集合を他の端末に検索要求として転送することによりデータの検索を行う検索要求転送手段とを備えていてもよい。この構成によれば、複数属性からなる１つのデータを１つの装置に登録する場合において、特定の装置に検索要求の転送負荷が集中するのを防止することができる。
【００２２】
各端末に対する論理識別子の割り当てにもとづいて、論理識別子の範囲の集合を分割する論理識別子範囲分割手段を備え、検索要求転送手段は、論理識別子範囲分割手段によって分割された論理識別子の範囲の集合を他の端末に検索要求として転送することによりデータの検索を行うように構成されていてもよい。この構成によれば、検索範囲の広い場合にも検索要求のホップ数が増加しないようにすることができ、その結果、高速な検索、通信負荷の軽減なども図ることができる。
【００２３】
一次元化手段または検索条件一次元化手段は、空間充填曲線を用いて複数属性のデータを一次元の値または値の集合に変換し、識別子生成手段または識別子範囲生成手段は、空間充填曲線にて一次元化された値または値の集合を均一化する空間充填曲線分布関数を適用して一次元化された値または値の集合から論理識別子またはその範囲の集合を生成するように構成されていてもよい。この構成によれば、検索要求（検索メッセージ）を転送する論理識別子の範囲を狭くすることができるとともに（例えば、図１８に示すようにｘ属性とｙ属性をともに満たす要素数に検索メッセージを伝播させることができる）、オーバレイネットワーク上の各装置にデータ管理負荷が集中しないようにすることができる。
【００２４】
論理識別子範囲分割手段は、ルーティングテーブルに格納された論理識別子にもとづいて、論理識別子の範囲の集合を分割するように構成されていてもよい。この構成によれば、適切な範囲に論理識別子の範囲の集合を分割することができ、その結果、より一層高速な検索を実現することができる。
【００２５】
本発明によるオーバレイ管理方法は、オーバレイネットワーク上に配置された管理装置の制御部が制御プログラムに従って、複数属性のデータを一次元の値に変換し、一次元化した値に対して、値の分布情報を含む関数を適用して論理識別子を生成し、オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、生成した論理識別子を管理する他の装置を特定し、特定した他の装置にデータを登録する処理を実行することを特徴とする。
【００２６】
オーバレイネットワーク上に配置された管理装置の制御部が制御プログラムに従って、
複数属性の検索条件を一次元の値の集合に変換し、一次元化した値の集合内の要素に対して、値の分布情報を含む関数を適用して論理識別子の範囲の集合を生成し、生成した論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行うように構成されていてもよい。この構成によれば、複数属性からなる１つのデータを１つの装置に登録する場合において、特定の装置に検索要求の転送負荷が集中するのを防止することができる。
【００２７】
オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、論理識別子の範囲の集合を分割し、分割した論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行うように構成されていてもよい。この構成によれば、検索範囲の広い場合にも検索要求のホップ数が増加しないようにすることができ、その結果、高速な検索、通信負荷の軽減なども図ることができる。
【００２８】
空間充填曲線を用いて複数属性のデータを一次元の値または値の集合に変換し、空間充填曲線にて一次元化された値または値の集合を均一化する空間充填曲線分布関数を適用して一次元化された値または値の集合から論理識別子またはその範囲の集合を生成するように構成されていてもよい。この構成によれば、検索要求（検索メッセージ）を転送する論理識別子の範囲を狭くすることができるとともに（例えば、図１８に示すようにｘ属性とｙ属性をともに満たす要素数に検索メッセージを伝播させることができる）、オーバレイネットワーク上の各装置にデータ管理負荷が集中しないようにすることができる。
【００２９】
ルーティングテーブルに格納された論理識別子にもとづいて、論理識別子の範囲の集合を分割するように構成されていてもよい。この構成によれば、適切な範囲に論理識別子の範囲の集合を分割することができ、その結果、より一層高速な検索を実現することができる。
【００３０】
本発明によるオーバレイ管理用プログラムは、オーバレイネットワーク上に配置された管理装置が他の装置と共有するデータを管理するためのオーバレイ管理用プログラムであって、複数属性のデータを一次元の値に変換する一次元化処理と、一次元化した値に対して、値の分布情報を含む関数を適用して論理識別子を生成する識別子生成処理と、オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、生成した論理識別子を管理する他の装置を特定する管理装置特定処理と、特定した他の装置にデータを登録する処理を実行するデータ登録処理とを管理装置に実行させることを特徴とする。
【００３１】
複数属性の検索条件を一次元の値の集合に変換する検索条件一次元化処理と、一次元化した値の集合内の要素に対して、値の分布情報を含む関数を適用して論理識別子の範囲の集合を生成する識別子範囲生成処理と、生成した論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行う検索要求転送処理とを管理装置に実行させるようにしてもよい。この構成によれば、複数属性からなる１つのデータを１つの装置に登録する場合において、特定の装置に検索要求の転送負荷が集中するのを防止することができる。
【００３２】
オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、論理識別子の範囲の集合を分割する論理識別子範囲分割処理を管理装置に実行させ、検索要求転送処理において、分割した論理識別子の範囲の集合を他の装置に検索要求として転送することによりデータの検索を行わせるようにしてもよい。この構成によれば、検索範囲の広い場合にも検索要求のホップ数が増加しないようにすることができ、その結果、高速な検索、通信負荷の軽減なども図ることができる。
【００３３】
一次元化処理または検索条件一次元化処理において、空間充填曲線を用いて複数属性のデータを一次元の値または値の集合に変換させ、識別子生成処理または識別子範囲生成処理において、空間充填曲線にて一次元化された値または値の集合を均一化する空間充填曲線分布関数を適用して一次元化された値または値の集合から論理識別子またはその範囲の集合を生成させるようにしてもよい。この構成によれば、検索要求（検索メッセージ）を転送する論理識別子の範囲を狭くすることができるとともに（例えば、図１８に示すようにｘ属性とｙ属性をともに満たす要素数に検索メッセージを伝播させることができる）、オーバレイネットワーク上の各装置にデータ管理負荷が集中しないようにすることができる。
【００３４】
論理識別子範囲分割処理において、ルーティングテーブルに格納された論理識別子にもとづいて、論理識別子の範囲の集合を分割させるようにしてもよい。この構成によれば、適切な範囲に論理識別子の範囲の集合を分割することができ、その結果、より一層高速な検索を実現することができる。
【発明の効果】
【００３５】
本発明によれば、オーバレイネットワーク上に配置された管理装置の制御部が制御プログラムに従って、複数属性のデータを一次元の値に変換し、一次元化した値に対して関数を適用して論理識別子を生成し、オーバレイネットワーク上の各装置に対する論理識別子の割り当てにもとづいて、生成した論理識別子を管理する他の装置を特定し、特定した他の装置にデータを登録する処理を実行するように構成されているので、多次元属性（複数属性）のデータ検索を効率よく高速に実行することができる。
【発明を実施するための最良の形態】
【００３６】
以下、本発明の実施の一形態を図面を参照して説明する。
【００３７】
実施の形態１．
図１は、実施の形態１におけるオーバレイ管理システムの構成を示すブロック図である。図１に示すように、このオーバレイ管理システムは、インターネットなどのネットワーク１００上におけるアドレスを有する複数のピア１１０，１２０，１３０・・・（なお、ピアのことをノードともいう）から構成されている。なお、図１には、ピアとしてピア１１０，１２０，１３０だけしか示していないが、ほかにも複数のピアが複数ネットワーク１００に接続されている。
【００３８】
図１に示すように、各ピア１１０，１２０，１３０・・・は、ローカルデータ格納部１１１と、ルーティングテーブル１１２と、メッセージ転送手段１１３と、通信手段１１４と、ピア論理識別子格納部１１５と、個別属性分布関数格納部１１７と、登録・検索実行手段１１８とを備えている。
【００３９】
ピア論理識別子格納部１１５には、オーバレイネットワークにおける当該ピア（例えばピア１１０）の論理識別子（ノードＩＤともいう）が格納される。この実施の形態では、論理識別子はオーバレイネットワーク上において各ピアを識別するための識別子である。この実施の形態では、後述するように、Ｃｈｏｒｄアルゴリズムを利用してデータ検索を実行するが、Ｃｈｏｒｄでは、各ピアはオーバレイネットワークに参加するときにＳＨＡ−１などのハッシュ関数により自分の論理識別子を生成し、生成した論理識別子（ノードＩＤ）をピア論理識別子格納部１１５に格納する。この論理識別子はピア毎にユニークな値である。
【００４０】
ローカルデータ格納部１１１には、全ピア１１０，１２０，１３０・・・で共有するデータ（コンテンツ）のうち、当該ピア（例えばピア１１０）が担当するデータが格納される。各ピアがどの部分のデータを担当（管理）するかは、各ピアの論理識別子によって異なる。
【００４１】
ルーティングテーブル（フィンガーテーブルともいう）１１２は、各ピアがルーティングを行うときに参照するテーブルである。ルーティングテーブル１１２には、他のピアの論理識別子と、ネットワーク１００上でのアドレス（例えば、ＩＰアドレス；Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌアドレス）の組が複数格納されている。このルーティングテーブル１１２による管理方式は、Ｃｈｏｒｄと同一の管理方式である。Ｃｈｏｒｄの詳しい内容は後述する。
【００４２】
個別属性分布関数格納部１１７は、図２に示す個別属性分布関数格納表２００を格納する。個別属性分布関数格納表２００には、属性名２０１と、それに対応する分布関数２０２とが格納されている。図２に示す個別属性分布関数格納表２００では、属性名が「ＣＰＵ−Ｓｐｅｅｄ」と「Ｍｅｍｏｒｙ−Ｓｉｚｅ」とされ、「ＣＰＵ−Ｓｐｅｅｄ」の分布関数Ｈ（ｘ）として「６３ｘ／５」が格納され、「Ｍｅｍｏｒｙ−Ｓｉｚｅ」の分布関数Ｈ（ｘ）として「６３ｘ／１０２４」が格納されている。ここで、「ＣＰＵ−Ｓｐｅｅｄ」の「／５」はＣＰＵスピードが５ＧＨｚであることを示し、「Ｍｅｍｏｒｙ−Ｓｉｚｅ」の「／１０２４」はメモリサイズが１０２４Ｍバイトであることを示している。
【００４３】
下記の式１に示すように、この分布関数Ｈ（ｖ）は、属性の値ｖを１変数とする累積分布関数Ｄ（ｖ）と、オーバレイネットワークが持つ論理識別子の最大値（２＾ｍ−１）（つまり、ハッシュ空間が２６ （２の６乗）であるとすると、２６ −１＝６４−１＝６３）との積から得られる。
【００４４】
Ｈ（ｖ）＝Ｄ（ｖ）×（２＾ｍ−１）・・・（式１）
【００４５】
なお、累積分布関数および分布関数の詳しい説明について後述する。
【００４６】
登録・検索実行手段１１８は、データの登録および検索の処理を実行する。具体的には、登録・検索実行手段１１８は、外部インタフェースからデータを入力すると、その入力したデータに対応する論理識別子を生成し、生成した論理識別子をメッセージ転送手段１１３に出力し、この論理識別子に対応するピアにデータを登録するよう要求する。また、登録・検索実行手段１１８は、外部インタフェースからの検索要求を受け取ると、検索要求に含まれる検索条件に応じた属性の分布関数を個別属性分布関数格納部１１７から読み出し、読み出した分布関数および検索条件にもとづいて検索メッセージ（検索要求）を生成する。また、登録・検索実行手段１１８は、他のピアからの検索メッセージにもとづいて、ローカルデータ格納部１１１内に格納されているデータの検索処理を実行する。
【００４７】
メッセージ転送手段１１３は、データの登録要求および検索メッセージ（検索要求）の転送処理を実行する。具体的には、メッセージ転送手段１１３は、登録・検索実行手段１１８からのデータ登録要求を受けると、登録・検索実行手段１１８にて生成された論理識別子のピアに対してデータを送信する処理を実行する。また、メッセージ転送手段１１３は、ルーティングテーブル１１２を参照して、登録・検索実行手段１１８にて生成された検索メッセージを所定の転送先のピアに転送する処理を実行する。また、メッセージ転送手段１１３は、他のピアからの検索メッセージを受け取ると、ルーティングテーブル１１２を参照して、検索メッセージを所定の転送先のピアに転送し、または登録・検索実行手段１１８に出力する処理を実行する。
【００４８】
通信手段１１４は、ネットワーク１００を通じて他のピアとの間で検索メッセージ等を送受信する処理を実行する。
【００４９】
（１）Ｃｈｏｒｄについて；
まず、分散ハッシュテーブルの一つであるＣｈｏｒｄについて説明する。Ｃｈｏｒｄでは、円状のハッシュ空間（１次元のハッシュ空間）を２１６０ （２の１６０乗）とし、ハッシュ関数としてＳＨＡ−１を想定している。ここでは、ハッシュ空間を説明しやすくするために、図３に示すように、２６ （＝６４；２の６乗）とする。この場合、円状のハッシュ空間に０〜６３の論理識別子（ノードＩＤ）が配置される。そのうち、実際にピアが存在しているのは、図３に示す例では「４」「１５」「３０」「４８」「５６」「６０」である。
【００５０】
Ｃｈｏｒｄでは、自身のピアの論理識別子に、２ｉ （２のｉ乗：ｉ＝０，１，２，４，８，・・・，ｎ）を加えた数の論理識別子のピアの情報（ピアの論理識別子とＩＰアドレスの組の情報）がフィンガーテーブルとしてルーティングテーブル１１２に登録される。すなわち、自身のピアの論理識別子の１，２，４，８，・・・先の論理識別子のピアの情報が登録される。自身の１，２，４，８，・・・先の論理識別子のピアが存在しないときは、その論理識別子の数より大きく最も近いピアの情報（ピアの論理識別子とＩＰアドレスの組の情報）が登録される。また、自身の論理識別子から見て時計回りの方向に最初に存在するピア（自身の論理識別子より大きい隣のピア）の情報（ピアの論理識別子とＩＰアドレスの組の情報）もルーティングテーブル１１２に登録される。
【００５１】
なお、所定の論理識別子から見て時計回りの方向に最初に存在するピアを「ｓｕｃｃｅｓｓｏｒ」という。また、所定の論理識別子から見て反時計回りの方向に最初に存在するピア（自身の論理識別子より小さい隣のピア）を「ｐｒｅｄｅｃｅｓｓｏｒ」という。そのｐｒｅｄｅｃｅｓｓｏｒと自身との間のハッシュ空間を責任領域としてデータの管理を行う。
【００５２】
例えば、図３に示す例では、論理識別子のハッシュ空間が２６ （２の６乗）であり、オーバレイネットワーク上に論理識別子４，１５，３０，４８，５６，６０のピアが存在している。このとき、自身のピアの論理識別子が「５６」であれば、自身の１，２，４，８，・・・先の論理識別子（つまり、論理識別子５７，５８，６０，０，８，２４）のピア、またはそれらの論理識別子よりも大きく最も近い論理識別子のピアを管理することになる。従って、論理識別子６０，１５，３０のピアの情報をルーティングテーブル１１２に保持することになる。また、自身の論理識別子より大きい隣のピアである論理識別子６０のピア（ｓｕｃｃｅｓｓｏｒ）の情報もルーティングテーブル１１２に保持することになる。
【００５３】
上記の場合において、ユーザが論理識別子５６のピア３０５から検索キーワードのハッシュ値（転送先論理識別子２０）をオーバーレイネットワークに送信する場合、論理識別子５６のピア３０５は、ルーティングテーブル１１２を参照して論理識別子２０に最も近い論理識別子１５のピア３０２に検索要求（検索メッセージ）を転送し、論理識別子１５のピア３０２は、転送先論理識別子２０のｓｕｃｃｅｓｓｏｒである論理識別子３０のピア３０３に検索要求を転送する。
【００５４】
このように、Ｃｈｏｒｄでは、ルーティングテーブル１１２を用いて、検索するピアを次のピアに渡す度に検索すべきハッシュ空間を１／２に絞っているので、検索にかかるホップ数（ピアから他のピアに検索メッセージが転送される回数）をＯ（ｌｏｇＮ）に抑えることが可能となり、その結果、高速なデータ検索を実現することができる。
【００５５】
次に、Ｃｈｏｒｄにおけるピアの参加について説明する。図３に示す例において、論理識別子１０のピアが新たにオーバレイネットワークに参加するものとする。この場合、論理識別子１０のピアは、現在、オーバレイネットワークに参加している適当なピアに論理識別子１０よりも大きい次の論理識別子（図３に示す例では論理識別子１５）のピアを探してもらう。また、論理識別子１０のピアは、論理識別子１５の一つ前の論理識別子（図３に示す例では４）のピアを教えてもらう。そして、論理識別子１０のピアは、論理識別子１５のピアと論理識別子４のピアに自分の存在を通知し、ルーティングテーブル１１２の変更を行わせる。また、論理識別子１０のピアは、論理識別子１５のピアからハッシュ値１０〜１４に対応しているデータをもらって格納する。このような処理によって論理識別子１０のピアがＣｈｏｒｄ（オーバレイネットワーク）に参加することができることになる。
【００５６】
次に、Ｃｈｏｒｄにおけるピアの離脱について説明する。オーバレイネットワーク上の各ピアは、ルーティングしているピアに対して定期的にピアの生死を確認する。これによってピアの離脱を確認した場合はルーティングテーブルの変更を行う。しかし、この場合、ネットワークから離脱するピアに蓄積しているデータが失われてしまう可能性がある。このため、ピアが保持しているデータは、当該ピアから見て時計回りに近い順番から所定個のピアにデータを複製しておく。これにより、あるピアがネットワークから離脱してもデータが消失してしまうことはない。
【００５７】
（２）累積分布関数および分布関数について；
累積分布関数Ｄ（ｖ）は、単調増加で連続な０以上１以下の関数である。例えば、日本の年齢の密度関数を考える。この場合、６０歳の年齢の人は、全体の０．０５だとする。この密度関数を積分して得られるものが累積分布関数Ｄ（ｖ）である。すなわち、６０歳以下の人の割合が全体の０．７であり、およそ１２０歳で１となる。このＤ（ｖ）は、同一分布に従うデータサンプルを０〜１の間に均一化させるという特徴を持つ。例えば、任意の日本人を選んで、その人の年齢ｖを聞くと、２０代くらいまでの年齢の人が比較的少なく、３０代、４０代が徐々に多くなり、５８歳あたり（団塊の世代）の割合が最も多く、その後の年代では割合が少なくなっていく。しかし、累積分布関数Ｄ（ｖ）を求めると〜１に均一に分布する。
【００５８】
２＾ｍ−１は、上述したように、オーバレイネットワークにおけるＩＤ（論理識別子）の最大値で、ｍビットの最大値を表わす。例えば、６ビットの数値は００００００〜１１１１１１の範囲となるが、この場合の最大値は２＾６−１＝６３（２進数表示で１１１１１１）である。
【００５９】
累積分布関数Ｄ（ｖ）と２ｍ −１の積をとることで、分布関数Ｈ（ｖ）は０〜２ｍ −１に均一に分布することになる。仮に、各ＩＤ毎にサーバ（端末）が存在するとすると、この年齢データは同一確率で各サーバに配置されるため、負荷の偏りがおきないというメリットがある。
【００６０】
次に、この実施の形態１におけるオーバレイ管理システムの動作について説明する。
【００６１】
図４は、実施の形態１におけるオーバレイ管理システムの動作を示すシーケンス図である。例えば、図３に示す論理識別子４を持つピア３０１が、図２に示す属性名「ＣＰＵ−Ｓｐｅｅｄ」の値が（４．０，５．０）で、属性名「Ｍｅｍｏｒｙ−Ｓｉｚｅ」が［７６８，１０２４］の値を持つデータを探すことを想定する。ここで、（４．０，５．０）は、下限値が４．０ＧＨｚで上限値が５．０ＧＨｚの検索範囲を示し、［７６８，１０２４］は、下限値が７６８Ｍバイトで上限値が１０２４Ｍバイトの検索範囲であることを示している。
【００６２】
図４に示すように、ピア３０１において、登録・検索実行手段１１８は、検索条件として、属性名「ＣＰＵ−Ｓｐｅｅｄ」における（４．０，５．０）と、属性名「Ｍｅｍｏｒｙ−Ｓｉｚｅ」における［７６８，１０２４］とを外部インタフェースから入力（取得）する（ステップＳ１００）。すると、登録・検索実行手段１１８は、属性名「ＣＰＵ−Ｓｐｅｅｄ」および属性名「Ｍｅｍｏｒｙ−Ｓｉｚｅ」に対応する分布関数Ｈ（ｖ）を求める計算式を個別属性分布関数格納部１１７から読み出して取得する。
【００６３】
そして、登録・検索実行手段１１８は、検索条件および分布関数Ｈ（ｖ）を求める計算式にもとづいて、検索メッセージ（検索要求）を生成する（ステップＳ１０１）。具体的には、まず、各属性に応じた分布関数Ｈ（ｖ）を求める計算式（上記の式１）に、指定された各属性の下限値および上限値を代入して、各属性の分布関数Ｈ（ｖ）の下限値および上限値を取得する。例えば、属性名「ＣＰＵ−Ｓｐｅｅｄ」の場合、下限値４．０から求められる分布関数の値は５０．４であり、上限値５．０から求められる分布関数の値は６３であるものとする。また、属性名「Ｍｅｍｏｒｙ−Ｓｉｚｅ」の場合、下限値７６８から求められる分布関数の値は４７．２３であり、上限値１０２４から求められる分布関数の値は６３であるものとする。従って、属性名「ＣＰＵ−Ｓｐｅｅｄ」では分布関数の範囲（５０．４，６３）が得られ、属性名「Ｍｅｍｏｒｙ−Ｓｉｚｅ」では分布関数の範囲［４７．２３，６３］が得られたことになる。
【００６４】
次いで、登録・検索実行手段１１８は、各属性の分布関数の範囲のうち、範囲の幅の狭い属性を支配的属性として選択する。ここでは、ＣＰＵ−Ｓｐｅｅｄの属性が選択される。そして、登録・検索実行手段１１８は、支配的属性として選択した属性の範囲の下限値を転送先論理識別子とする。ここでは、５０．４を転送先論理識別子とみなす。そして、登録・検索実行手段１１８は、これらの情報から、検索メッセージ（転送要求）３１０を生成する。図３に示すように、検索メッセージは、Ｃｈｏｒｄアルゴリズムの転送で用いられる［転送先論理識別子、支配的属性、支配的属性に対応する範囲、サブ検索式、結果リスト］を含んでいる。ここで、サブ検索式は、元の各属性の検索式（検索条件）から支配的属性の検索式を除いた検索式、すなわち、支配的属性として属性名ＣＰＵ−Ｓｐｅｅｄを選択した場合は属性名Ｍｅｍｏｒｙ−Ｓｉｚｅの検索式［７６８，１０２４］である。上記の例では、検索メッセージ３１０の具体例は、［５０．４、ＣＰＵ−Ｓｐｅｅｄ、（４．０，５．０）、Ｍｅｍｏｒｙ−Ｓｉｚｅ∈［７６８，１０２４］、Ｎｕｌｌ］という検索メッセージ３１１となる。なお、結果リストは最初は「Ｎｕｌｌ」（初期状態）に設定されている。
【００６５】
登録・検索実行手段１１８は、生成した検索メッセージをメッセージ転送手段１１３に出力する。メッセージ転送手段１１３は、ルーティングテーブル１１２を参照し、検索メッセージの転送先のピアを決定した上で、検索メッセージを通信手段１１４を介して送信する（ステップＳ１０２）。この場合、検索メッセージに含まれる「転送先論理識別子」が５０．４であるので、検索メッセージの転送先のピアとして、転送先論理識別子５０．４よりも小さい論理識別子４８のピア３０４と決定される。
【００６６】
論理識別子４８のピア３０４は、ピア３０１からの検索メッセージを受信すると、転送先論理識別子５０．４のｓｕｃｃｅｓｓｏｒであるかどうかを判定する（ステップＳ１０３）。ｓｕｃｃｅｓｓｏｒでない場合は（ステップＳ１０３のＮ）、ルーティングテーブルにもとづいて、検索メッセージを他のピアに転送する（ステップＳ１０４）。最終的には、転送先論理識別子５０．４のｓｕｃｃｅｓｓｏｒであるピアに転送される。ｓｕｃｃｅｓｓｏｒである場合は（ステップＳ１０３のＹ）、ステップＳ１０５〜Ｓ１０８の処理を実行する。なお、図３に示す例では、ピア３０４はｓｕｃｃｅｓｓｏｒではないので（ステップＳ１０３のＮ）、ステップＳ１０５〜Ｓ１０８の処理を実行せずに、検索メッセージを論理識別子５６のピア３０５に転送する（ステップＳ１０４）。
【００６７】
ピア３０５も、ピア３０４と同様の処理を実行する。すなわち、転送先論理識別子５０．４のｓｕｃｃｅｓｓｏｒであるかどうかを判定する（ステップＳ１０３）。図３に示す例では、論理識別子５６のピア３０５は、転送先論理識別子５０．４のｓｕｃｃｅｓｓｏｒであるので（ステップＳ１０３のＹ）、検索処理を実行する（ステップＳ１０５）。すなわち、検索メッセージに含まれるサブ検索式に適合するデータがローカルデータ格納部１１１（図３ではローカルデータ格納部３２１）内に存在するかどうかを検索する。図３に示す例では、サブ検索式（Ｍｅｍｏｒｙ−Ｓｉｚｅ∈［７６８，１０２４］）に適合するデータとして［Ｍｅｍｏｒｙ−Ｓｉｚｅ］７６８ＭＢが検索されたものとする。この場合、［Ｍｅｍｏｒｙ−Ｓｉｚｅ］７６８ＭＢのピアとして「ピア１５」（つまり論理識別子１５のピア３０２）という名前（検索キーワード）が発見されるため、検索メッセージ３１２の結果リストに「ピア１５」が格納される。
【００６８】
次に、ピア３０５は、検索メッセージに含まれる支配的属性に対応する範囲上限の論理識別子のｓｕｃｃｅｓｓｏｒであるかどうかを判定する（ステップＳ１０６）。範囲上限の論理識別子のｓｕｃｃｅｓｓｏｒである場合は（ステップＳ１０６のＹ）、検索結果をピア３０１に返信して（ステップＳ１０８）、処理を終了する。一方、範囲上限の論理識別子のｓｕｃｃｅｓｓｏｒでない場合は（ステップＳ１０６のＮ）、検索メッセージを他のピア（当該ピアのｓｕｃｃｅｓｓｏｒのピア）に転送する（ステップＳ１０７）。図３に示す例では、支配的属性に対応する検索範囲の上限値が６３であり、ピア３０５の論理識別子が５６であるので、ピア３０５は範囲上限の論理識別子のｓｕｃｃｅｓｓｏｒでないと判断して（ステップＳ１０６のＮ）、検索メッセージをピア３０５のｓｕｃｃｅｓｓｏｒである論理識別子６０のピア３０６に転送する（ステップＳ１０７）。
【００６９】
ピア３０６も、ピア３０５と同様にステップＳ１０６の処理を実行する。すなわち、範囲上限の論理識別子のｓｕｃｃｅｓｓｏｒであるかどうかを判定する。図３に示す例では、ピア３０６は、範囲上限の論理識別子のｓｕｃｃｅｓｓｏｒでないため（ステップＳ１０６のＮ）、さらに検索メッセージをピア３０６のｓｕｃｃｅｓｓｏｒである論理識別子４のピア３０１に転送する（ステップＳ１０７）。
【００７０】
ピア３０１は、範囲上限の論理識別子のｓｕｃｃｅｓｓｏｒであるが、図３に示す例では、ピア３０１には検索対象のデータがないので、ここで検索を終了する。そして、「ピア１５」という検索結果３１３が検索メッセージの発行元（送信元）のピア３０１に返信される（ステップＳ１０８）。なお、この場合、ピア３０１が自分に返信することになる。
【００７１】
図５は、属性値と分布関数の関係を示す説明図である。図５のｘｙ座標のグラフ４００に示すように、ｘ属性のデータをｘ軸にとり、ｙ属性のデータをｙ軸にとると、そのデータの値（データのプロット）は所定の範囲に集中しているものとする。図５に示す例では、３箇所に集中している。ここで、上記の式１を用いて、ｘ属性のデータを分布関数に変換すると、図５の下のグラフ４２１に示すような均一化された分布となる。また、上記の式１を用いて、ｙ属性のデータを分布関数に変換すると、図５の右のグラフ４２２に示すような均一化された分布となる。
【００７２】
図５に示すように、ｘ属性の検索条件４１１としてほぼ中央の範囲４３１が指定され、ｙ属性の検索条件４１２として上半分の範囲４３２が指定されたものとする。この場合、範囲の幅が狭いのはｘ属性であるので、ｘ属性が支配的属性として選択される。そして、上述したように、支配的属性の検索範囲の下限値が転送先論理識別子として決定され、転送先論理識別子に対する検索メッセージが送信される。そして、転送先論理識別子のｓｕｃｃｅｓｓｏｒのピアに検索メッセージが到達すると、そのピア内においてローカルでデータ検索が実行される。その後、支配的属性の検索範囲の上限値の論理識別子についてのｓｕｃｃｅｓｓｏｒのピアに対して検索メッセージが転送される。そして、そのピアにおいてデータ検索がローカルで実行される。その後、検索結果が検索メッセージの送信元のピアに返信される。
【００７３】
以上のように、この実施の形態１によれば、多次元属性の検索条件にもとづいてデータ検索を実行することができる。この場合、Ｃｈｏｒｄアルゴリズムを利用して検索を行うように構成されているので、ホップ数を削減することができ、ネットワーク上の通信負荷の軽減や高速な検索を実現することができる。また、多次元の属性のデータを分布関数に変換して均一化しているので、特定のピアに対して負荷が集中してしまうのを防止することができる。
【００７４】
なお、上記の実施の形態１では、２次元属性の検索条件にもとづくデータ検索について説明したが、多次元属性の検索条件にもとづくデータ検索にも適用することができる。その場合も、検索範囲の幅の最も狭い属性を支配的属性として選択し、その支配的属性の下限値を転送先論理識別子として検索メッセージ（検索要求）を送信することになる。
【００７５】
実施の形態２．
上記の実施の形態１では、各属性の分布関数を用いる手法であったが、この実施の形態２では、空間充填曲線を用いる手法について説明する。
【００７６】
図６は、実施の形態２におけるオーバレイ管理システムの構成を示すブロック図である。図６に示すように、実施の形態２におけるオーバレイ管理システムについても、インターネットなどのネットワーク５００上におけるアドレスを有する複数のピア５１０，５２０，５３０・・・（なお、ピアのことをノードともいう）から構成されている。なお、図６には、ピアとしてピア５１０，５２０，５３０だけしか示していないが、ほかにも複数のピアが複数ネットワーク５００に接続されている。
【００７７】
図６に示すように、各ピア５１０，５２０，５３０・・・は、ローカルデータ格納部５１１と、ルーティングテーブル５１２と、メッセージ転送手段５１３と、通信手段５１４と、ピア論理識別子格納部５１５と、空間充填曲線変換手段５１７と、登録・検索実行手段５１８とを備えている。
【００７８】
ピア論理識別子格納部５１５には、オーバレイネットワークにおける当該ピア（例えばピア１１０）の論理識別子（ノードＩＤともいう）が格納される。
【００７９】
ローカルデータ格納部５１１には、全ピア５１０，５２０，５３０・・・で共有するデータ（コンテンツ）のうち、当該ピア（例えばピア１１０）が担当するデータが格納される。
【００８０】
ルーティングテーブル５１２は、各ピアがルーティングを行うときに参照するテーブルである。ルーティングテーブル５１２には、他のピアの論理識別子と、ネットワーク５００上でのアドレス（例えば、ＩＰアドレス）の組が複数格納されている。
【００８１】
空間充填曲線変換手段５１７は、空間充填曲線を用いて、多次元属性の検索条件の値を１次元の検索条件の値に変換する処理を実行する。
【００８２】
登録・検索実行手段５１８は、データの登録および検索の処理を実行する。メッセージ転送手段５１３は、ルーティングテーブル５１２を参照して、検索メッセージ（検索要求）の転送処理を実行する。
【００８３】
通信手段５１４は、ネットワーク５００を通じて他のピアとの間で検索メッセージ等を送受信する処理を実行する。
【００８４】
なお、この実施の形態２では、上記の実施の形態１の場合と異なり、Ｃｈｏｒｄアルゴリズムを利用した手法ではない。ただし、登録・検索実行手段５１８および空間充填曲線変換手段５１７の構成以外は、ほぼ同じ内容の処理を実行する。
【００８５】
次に、この実施の形態２におけるオーバレイ管理システムの動作について説明する。
【００８６】
図７は、空間充填曲線を用いてＣｌｕｓｔｅｒを分割する具体例を示す説明図である。検索式Ｑｕｅｒｙ（データベース管理システムに対する処理要求（問い合わせ）を文字列として表わしたもの）が２次元属性に対する検索式であるものとする。例えば、ｘ属性の値が０１１で、ｙ属性の値が１＊＊であるとすると、（０１１，１＊＊）と表わせる。このとき、各属性の先頭ビットの組は（０，１）となる。ここで、図７の左上の表６００における左上の領域６０２が（０，１）で指定された領域（範囲）であり、Ｃｌｕｓｔｅｒは「０１」（左上の領域６０２の中心位置に示した数字）である。この「０１」は、空間充填曲線（空間充填曲線とはある空間を曲線で埋め尽くしてしまうような曲線）のルートになぞった原点「００」からの距離を示している。なお、図７では、空間充填曲線としてヒルベルト空間充填曲線を用いている。
【００８７】
次いで、（０１１，１＊＊）の第２ビットの組は（１，＊）となっている。ここで、「＊」は０または１の値となる。従って、（１，０）と（１，１）の組み合わせが存在する。図７の右上の表６１０におけるｘ属性が「０１」でｙ属性が「１０」および「１１」である領域６１１が（０１，１＊）で指定された領域（範囲）であり、Ｃｌｕｓｔｅｒは「０１１０」と「０１１１」である。この「０１１０」、「０１１１」は空間充填曲線のルートになぞった原点「００００」からの距離を示している。
【００８８】
そして、（０１１，１＊＊）の第３ビットの組も（１，＊）となっている。この場合も、（１，０）と（１，１）の組み合わせが存在する。図７の左下の表６２０におけるｘ属性が「０１１」でｙ属性が「１００」、「１０１」、「１１０」および「１１１」である領域６２１が（０１１，１＊＊）で指定された領域（範囲）であり、Ｃｌｕｓｔｅｒは「０１１０１０」、「０１１０１１」、「０１１１００」、「０１１１１１」である。この「０１１０１０」、「０１１０１１」、「０１１１００」、「０１１１１１」は空間充填曲線のルートになぞった原点「００００００」からの距離を示している。
【００８９】
このように、空間充填曲線を用いて検索式（０１１，１＊＊）から複数のＣｌｕｓｔｅｒを持つリストを生成することができる。複数のＣｌｕｓｔｅｒを持つリストをＣｌｕｓｔｅｒＬｉｓｔという。Ｃｌｕｓｔｅｒをハッシュ空間における論理識別子と対応させることによって、検索メッセージを転送するピアのルーティングを行うのが、この実施の形態２の手法である。
【００９０】
図８は、実施の形態２におけるピア間でのメッセージの流れの具体例を示す説明図である。図９は、実施の形態２におけるオーバレイ管理システムの動作を示すシーケンス図である。図８に示すように、論理識別子５６のピア７０５において、登録・検索実行手段５１８は、外部インタフェースから入力される検索式Ｑｕｅｒｙを取得すると、論理識別子０のピア７０６に検索式を含む検索メッセージを送信する。このとき、検索式は（０１１，１＊＊）であるものとする。この検索式（０１１，１＊＊）は、２つの属性に対する検索式であって、ｘ属性が０１１の完全一致検索であり、ｙ属性が１＊＊の前方一致検索である。なお、実施の形態２における検索メッセージは、実施の形態１で示した検索メッセージとは異なるフォーマットである。
【００９１】
ピア７０６が検索メッセージ（検索式）を発行すると（ステップＳ５００）、ピア７０６の登録・検索実行手段５１８は、空間充填曲線変換手段５１７に検索式を出力し、ＣｌｕｓｔｅｒＬｉｓｔを生成させる（ステップＳ５０１）。空間充填曲線変換手段５１７は、図７で説明した手順で、Ｃｌｕｓｔｅｒ「０１」を生成して登録・検索実行手段５１８に出力する。登録・検索実行手段５１８は、Ｃｌｕｓｔｅｒ「０１」に対応する論理識別子０１００００（＝１６）のピア７０２に検索メッセージを送信する（ステップＳ５０２）。
【００９２】
論理識別子１６のピア７０２は、ピア７０６からの検索メッセージ（検索式）を受信して取得すると、ピア７０２の登録・検索実行手段５１８は、検索メッセージに含まれる検索式で指定されている論理識別子が自分の管理する論理識別子であるか否か判定する（ステップＳ５０３）。自分が管理する論理識別子である場合は（ステップＳ５０３のＹ）、登録・検索実行手段５１８は、検索処理を実行する（ステップＳ５０６）。すなわち、検索メッセージに含まれる検索式に適合するデータがローカルデータ格納部５１１内に存在するかどうかを検索する。そして、ピア７０２は、検索結果をメッセージの送信元（発信元）のピア７０５に返信する（ステップＳ５０７）。なお、図８に示す例では、検索式で指定されている論理識別子は論理識別子１６のピア７０２が管理する論理識別子でない。
【００９３】
自分が管理する論理識別子でない場合は（ステップＳ５０３のＮ）、登録・検索実行手段５１８は、検索式を空間充填曲線変換手段５１７に出力してＣｌｕｓｔｅｒＬｉｓｔを生成させる（ステップＳ５０４）。空間充填曲線変換手段５１７は、図７で説明した手順で、「０１１０」と「０１１１」を含むＣｌｕｓｔｅｒ「０１１」を生成して登録・検索実行手段５１８に出力する。なお、Ｃｌｕｓｔｅｒの識別子はそれに含まれる要素の共通先頭ビットとする。登録・検索実行手段５１８は、Ｃｌｕｓｔｅｒ「０１１」を管理するピアを探し、論理識別子０１１１１０（＝３０）のピアに対して検索メッセージを送信する（ステップＳ５０５）。
【００９４】
論理識別子３０のピア７０３は、ピア７０２からの検索メッセージ（検索式）を受信して取得すると、ピア７０３の登録・検索実行手段５１８は、検索メッセージに含まれる検索式で指定されている論理識別子が自分の管理する論理識別子であるか否か判定する（ステップＳ５０３）。図８に示す例では、Ｃｌｕｓｔｅｒに含まれる中で、「０１１０」で始まる論理識別子は論理識別子３０のピア７０３が管理する論理識別子である。従って、ピア７０３の登録・検索実行手段５１８は、検索処理を実行する（ステップＳ５０６）。すなわち、検索メッセージに含まれる検索式に適合するデータがローカルデータ格納部５１１内に存在するかどうかを検索する。そして、ピア７０３は、検索結果をメッセージの送信元（発信元）のピア７０５に返信する（ステップＳ５０７）。
【００９５】
また、論理識別子３０のピア７０３で、Ｃｌｕｓｔｅｒに含まれる中で「０１１１」で始まる論理識別子と検索式（０１１，１＊＊）から空間充填曲線変換手段５１７を用いて得られる出力として、「０１１１００」を含むＣｌｕｓｔｅｒ「０１１１００」と「０１１１１１」を含むＣｌｕｓｔｅｒ「０１１１１１」が得られる。これらはそれぞれ次の宛先である論理識別子０１１１１０（＝３０）であるピア７０３と論理識別子１１００００（＝４８）であるピア７０４に転送され、それぞれの論理識別子は当該ピアで管理するものと判定されるため、ローカルデータ格納部５１１内にデータが存在するか検索し、存在する場合には検索結果をメッセージの送信元のピア７０５に返信する（ステップＳ５０７）。
【００９６】
以上のように、この実施の形態２によれば、空間充填曲線変換を用いて、多次元データを１次元データに変換することによって、多次元属性の検索式（検索条件）にもとづいてデータ検索を行うことができる。また、検索メッセージを転送する度に、Ｃｌｕｓｔｅｒを段階的に分割させていくことにより、検索メッセージの転送先を分散させることができ、ホップ数を削減することができる。その結果、ネットワーク上の通信負荷の軽減や高速な検索を実現することができる。
【００９７】
なお、上記の実施の形態１では、２次元属性の検索式にもとづくデータ検索について説明したが、多次元属性の検索式にもとづくデータ検索にも適用することができる。また、空間充填曲線としてヒルベルト空間充填曲線を用いていたが、ヒルベルト空間充填曲線に限られるわけでなく、Ｚ−ｃｕｒｖｅ空間充填曲線、ペアノ空間充填曲線、シェルピンスキー空間充填曲線、ルベーグ空間充填曲線などであってもよい。
【００９８】
実施の形態３．
図１０は、実施の形態３におけるオーバレイ管理システムの構成を示すブロック図である。図１０に示すように、このオーバレイ管理システムは、インターネットなどのネットワーク１０００上におけるアドレスを有する複数のピア１０１０，１０２０，１０３０・・・（なお、ピアのことをノードともいう）から構成されている。なお、図１０には、ピアとしてピア１０１０，１０２０，１０３０だけしか示していないが、ほかにも複数のピアが複数ネットワーク１０００に接続されている。
【００９９】
図１０に示すように、各ピア１０１０，１０２０，１０３０・・・は、ローカルデータ格納部１０１１と、ルーティングテーブル１０１２と、メッセージ転送手段１０１３と、通信手段１０１４と、論理識別子範囲分割手段１０１５と、空間充填曲線分布格納部１０１６と、空間充填曲線変換手段１０１７と、登録・検索実行手段１０１８と、ピア論理識別子格納部１０１９とを備えている。
【０１００】
ピア論理識別子格納部１０１９には、オーバレイネットワークにおける当該ピア（例えばピア１１０）の論理識別子（ノードＩＤともいう）が格納される。この実施の形態では、論理識別子はオーバレイネットワーク上において各ピアを識別するための識別子である。この実施の形態では、実施の形態１と同様に、Ｃｈｏｒｄアルゴリズムを利用してデータ検索を実行するが、Ｃｈｏｒｄでは、各ピアはオーバレイネットワークに参加するときにＳＨＡ−１などのハッシュ関数により自分の論理識別子を生成し、生成した論理識別子（ノードＩＤ）をピア論理識別子格納部１０１９に格納する。この論理識別子はピア毎にユニークな値である。
【０１０１】
ローカルデータ格納部１０１１には、全ピア１０１０，１０２０，１０３０・・・で共有するデータ（コンテンツ）のうち、当該ピア（例えばピア１０１０）が担当するデータが格納される。各ピアがどの部分のデータを担当（管理）するかは、各ピアの論理識別子によって異なる。
【０１０２】
ルーティングテーブル１０１２は、各ピアがルーティングを行うときに参照するテーブルである。ルーティングテーブル１０１２には、他のピアの論理識別子と、ネットワーク１０００上でのアドレス（例えばＩＰアドレス）の組が複数格納されている。このルーティングテーブル１０１２による管理方式は、Ｃｈｏｒｄと同一の管理方式である。
【０１０３】
空間充填曲線分布格納部１０１６には、図１１に示すように、複数の属性の組インデックス毎に空間充填曲線分布関数Ｄ（ｋ）が格納されている。
【０１０４】
空間充填曲線変換手段１０１７は、空間充填曲線分布格納部１０１６に格納されている空間充填曲線分布関数Ｄ（ｋ）を用いて登録されるデータに応じた論理識別子Ｉｄを生成する。また、空間充填曲線変換手段１０１７は、空間充填曲線分布格納部１０１６に格納されている空間充填曲線分布関数Ｄ（ｋ）を用いて検索要求に含まれる検索式に応じた論理識別子範囲リストを生成する。
【０１０５】
登録・検索実行手段１０１８は、外部インタフェースからのデータ登録の要求に応じて、所定のデータ登録に関する処理を実行する。また、登録・検索実行手段１０１８は、外部インタフェースからのデータ検索の要求に応じて、所定のデータ検索に関する処理を実行する。また、登録・検索実行手段１０１８は、他のピアからの検索要求の受信に応じて、ローカルデータ格納部１０１１内のデータ検索、他のピアへの検索要求の転送などの処理を実行する。
【０１０６】
メッセージ転送手段１０１３は、検索要求（検索メッセージ）の転送処理を実行する。通信手段１０１４は、ネットワーク１０００を通じて他のピアとの間で検索メッセージ等を送受信する処理を実行する。これにより、あるピアのメッセージ転送手段１０１３が、他のピアのメッセージ転送手段１０１３を呼び出すことができる。
【０１０７】
論理識別子範囲分割手段１０１５は、検索対象として与えられた論理識別子の範囲を、ルーティングテーブル１０１２に格納されたピアの論理識別子の情報にもとづいて２つの論理識別子の範囲に分割する。
【０１０８】
次に、空間充填曲線を用いて２次元データを１次元データに変換する処理について図１２を参照して説明する。
【０１０９】
図１２は、空間充填曲線を用いて２次元データを１次元データに変換する処理のアルゴリズムを視覚的に表わすデータ構造を示す説明図である。なお、図１２では空間充填曲線としてヒルベルト空間充填曲線を使用した場合を示している。
【０１１０】
図１２に示すデータ構造によって、状態１２１１（図１２中の「０」）と、その状態によって一意に決定されるビットパターンの変換規則が管理される。変換規則とは、多次元属性の第ｉビットから生成されるビット列１２１３（例えば（００１，０１１）という２次元属性の第１ビットから生成されるビット列００、第２ビットから生成されるビット列０１、第３ビットから生成されるビット列１１）にもとづいて、第ｉ階層（例えば図１２の第１階層１２１０）の１次元の追加ビット列１２１２への変換を行うための規則である（例えば、第１階層１２１０を第ｉ階層とすると、下の段のビット列が００の場合は上の段の００が追加ビット列となり、下の段のビット列が０１の場合は上の段の０１が追加ビット列となり、下の段のビット列が１１の場合は上の段の１０が追加ビット列となり、下の段のビット列が１０の場合は上の段の追加ビット列は１１となる）。
【０１１１】
第ｉ＋１ビット目の変換規則を定める状態１４２１（図１２中の「１」「０」「０」「２」）は、第ｉビットの状態１２１１からの状態遷移として扱われる。多次元から１次元への変換を行うべきビット数まで変換規則を適用し、各階層におけるビット列に対応した追加ビット列を繋ぎ合せたビット列が、多次元属性の値を変換した後のＫｅｙとなる。
【０１１２】
図１２に示したデータ構造を用いて多次元データを１次元データに変換するアルゴリズム（手法）は、図７で説明した多次元データを１次元データに変換するアルゴリズム（手法）と同じである。具体的には、ｘ属性の値が０１１で、ｙ属性の値が１１１である場合は、（０１１，１１１）と表わせる。このとき、２つの属性の先頭ビット（第１ビット）の組は（０，１）となる。この場合の先頭ビットの組のビット列は「０１」となる。図１２に示す第１階層１２１０において、下の段のビット列「０１」に対応する上の段の追加ビット列は「０１」である。また、２つの属性の第２ビットの組は（１，１）となる。この場合の第２ビットの組のビット列は「１１」となる。図１２に示す第２階層１２２０において、状態「０」の場合における下の段のビット列「１１」に対応する上の段の追加ビット列は「１０」である。また、２つの属性の第３ビットの組は（１，１）となる。この場合の第３ビットの組のビット列は「１１」となる。図１２に示す第３階層１２３０において、状態「０」の場合における下の段のビット列「１１」に対応する上の段の追加ビット列は「１０」である。このように各階層におけるビット列に対応した追加ビット列を繋ぎ合せたビット列「０１１０１０」が２次元属性の値（０１１，１１１）を変換した後のＫｅｙとなる。
【０１１３】
次に、この実施の形態３におけるオーバレイ管理システムの動作について説明する。
【０１１４】
（１）オーバレイネットワークにて共有するデータを登録する動作；
図１３は、実施の形態３におけるオーバレイネットワークにて共有するデータを登録する処理を示すフローチャートである。まず、オーバレイネットワークにて共有するデータを登録する際に、あるピア（例えばピア１０１０）の登録・検索実行手段１０１８は、外部インタフェースからのデータ登録要求を受け付け、空間充填曲線変換手段１０１７に対してデータを出力し、このデータ（複数属性の値Ａｔｔｓ）に対応する論理識別子を要求する。そして、登録・検索実行手段１０１８は、空間充填曲線変換手段１０１７によって生成されたデータに対応する論理識別子を取得する（ステップＳ１３０１）。そして、登録・検索実行手段１０１８は、空間充填曲線変換手段１０１７から取得した論理識別子をメッセージ転送手段１０１３に出力し、この論理識別子に対応するピア（この論理識別子のｓｕｃｃｅｓｓｏｒのピア）にデータを登録するように要求する（ステップＳ１３０２）。
【０１１５】
メッセージ転送手段１０１３は、登録・検索実行手段１０１８からのデータの登録要求を受けると、登録・検索実行手段１０１８から出力された論理識別子に対応するピアに対してデータを送信してデータ登録を要求する。
【０１１６】
登録に成功した場合（論理識別子に対応するピアから登録完了の通知を受けた場合）は（ステップＳ１３０３のＹ）、登録・検索実行手段１０１８は、外部インタフェースに対して登録成功を返し（ステップＳ１３０３）、登録に失敗した場合は（ステップＳ１３０３のＮ）、登録・検索実行手段１０１８は、外部インタフェースに対して登録失敗を返す（ステップＳ１３０４）。なお、登録に失敗した場合は、再試行処理や当該論理識別子から一意に算出される他の論理識別子にも同時に登録し、データの冗長化を図ってもよい。
【０１１７】
図１４は、ステップＳ１３０１のサブルーチンの処理を示すフローチャートである。図１４に示すように、他のピアと共有するデータを登録する際に、あるピアの空間充填曲線変換手段１０１７は、登録・検索実行手段１０１８から論理識別子を要求されると、以下に示す論理識別子Ｉｄを算出する処理を実行する。まず、空間充填曲線変換手段１０１７は、登録・検索実行手段１０１８からのデータに含まれる複数属性の値Ａｔｔｓと対応する属性名の組から、図１１に示す属性名の組とその属性名の組に対応する空間充填曲線分布関数Ｄ（ｋ）を空間充填曲線分布格納部１０１６から取得する（ステップＳ１４０１）。
【０１１８】
そして、空間充填曲線変換手段１０１７は、データに含まれる複数属性の値の組を空間充填曲線に適合して得られる１次元の値Ｋｅｙを算出して取得する（ステップＳ１４０２）。ここで、複数属性の値の組を空間充填曲線を用いて１次元の値Ｋｅｙに変換する処理は、上述したように、図１２に示したデータ構造によるデータ変換の手法を用いて行う。Ｋｅｙを求める計算式は下記の式２となる。なお、式２における「ＳＦＣ」は空間充填曲（Ｓｐａｃｅ  Ｆｉｌｌｉｎｇ  Ｃｕｒｖｅ）線を示している。
【０１１９】
Ｋｅｙ＝ＳＦＣ（ｖ１，・・・・，ｖｉ，・・・・，ｖｎ）・・・（式２）
【０１２０】
次に、空間充填曲線変換手段１０１７は、式２から求めた値Ｋｅｙを空間充填曲線分布格納部１０１６から取得した空間充填曲線分布関数Ｄ（ｋ）に代入して、論理識別子Ｉｄを算出する（ステップＳ１４０３）。論理識別子Ｉｄを求める計算式は下記の式３となる。
【０１２１】
Ｉｄ＝Ｄ（Ｋｅｙ）・・・（式３）
【０１２２】
（２）オーバレイネットワークにて共有するデータを検索する動作；
図１５は、実施の形態３におけるオーバレイネットワークにて共有するデータを検索する処理を示すフローチャートである。まず、オーバレイネットワークにて共有するデータを検索する際に、あるピア（例えばピア１０１０）の登録・検索実行手段１０１８は、外部インタフェースから検索式Ｑｕｅｒｙを含んだ検索要求を受け付け、空間充填曲線変換手段１０１７に対して検索式を出力し、この検索式と対応する論理識別子範囲リストＩｄＲａｎｇｅｓを要求する。そして、登録・検索実行手段１０１８は、空間充填曲線変換手段１０１７によって生成された検索式に対応する論理識別子範囲リストを取得する（ステップＳ１５０１）。次に、登録・検索実行手段１０１８は、検索結果を格納するリスト（結果リストＲｅｓｕｌｔｓ）を初期化し、他のピアからの検索結果メッセージ（受信結果）を結果リストに格納するプロセスの起動を行う（ステップＳ１５０２）。
【０１２３】
次いで、登録・検索実行手段１０１８は、検索結果を待つ最大時間をタイムアウト（Ｔｉｍｅｏｕｔ）として設定し（ステップＳ１５０３）、空間充填曲線変換手段１０１７から取得した論理識別子範囲リストを引数として、メッセージ転送手段１０１３を非同期に呼び出す（ステップＳ１５０４）。すなわち、登録・検索実行手段１０１８は、メッセージ転送手段１０１３に対して論理識別子範囲リストの論理識別子のピアに対する検索メッセージ（検索要求）の転送を非同期に要求する。
【０１２４】
登録・検索実行手段１０１８は、論理識別子範囲リスト内の全ての論理識別子のピアに対する検索結果が得られたか、あるいはタイムアウト（Ｔｉｍｅｏｕｔ）が０以下になるまで検索結果を待ち続ける（ステップＳ１５０５，Ｓ１５０６）。すなわち、論理識別子範囲リスト内の全ての論理識別子のピアに対する検索結果を取得しておらず、かつタイムアウトが０以上である間は、一定時間のインターベルをおいて、タイムアウトの値を引いていく。
【０１２５】
論理識別子範囲リスト内の全ての論理識別子のピアに対する検索結果を取得したとき、あるいは、タイムアウトが０以下になったときは、登録・検索実行手段１０１８は、他のピアから送信された検索結果を格納されている結果リストを検索要求者（外部インタフェースから検索要求を行ったユーザ）に返して提示する。
【０１２６】
図１６は、ステップＳ１５０１のサブルーチンの処理を示すフローチャートである。図１６に示すように、他のピアと共有するデータを検索する際に、あるピアの空間充填曲線変換手段１０１７は、登録・検索実行手段１０１８から出力された検索式に含まれる属性名の組にもとづいて、属性名の組に応じた空間充填曲線分布関数Ｄ（ｋ）を取得する（ステップＳ１６０１）。
【０１２７】
そして、空間充填曲線変換手段１０１７は、空間充填曲線を用いて、検索式（複数属性の上限値、下限値）を満たす複数のＫｅｙの範囲ＫｅｙＲａｎｇｅｓを取得する（ステップＳ１６０２）。ここで、検索式を空間充填曲線を用いて複数の１次元の値Ｋｅｙに変換する処理は、上述したように、図１２に示したデータ構造によるデータ変換の手法を用いて行う。ＫｅｙＲａｎｇｅｓを求める計算式は下記の式４となる。
【０１２８】
ＫｅｙＲａｎｇｅｓ＝ＳＦＣ（ｑ１，・・・，ｑｉ，・・・，ｑｎ）・・・（式４）
【０１２９】
次に、空間充填曲線変換手段１０１７は、論理識別子範囲リストＩｄＲａｎｇｅｓを初期化する（ステップＳ１６０３）。そして、空間充填曲線変換手段１０１７は、ＫｅｙＲａｎｇｅｓに含まれる要素Ｋｅｙ（各Ｋｅｙ）の範囲に対して、範囲の始端（ＫｅｙＳｔａｒｔ；下限値）と終端（ＫｅｙＥｎｄ；上限値）をそれぞれ、空間充填曲線分布関数Ｄ（ｋ）を適用（代入）して、論理識別子範囲ＩｄＲａｎｇｅの始端と終端を決定する（ステップＳ１６０４）。そして、空間充填曲線変換手段１０１７は、ステップＳ１６０４で得られた論理識別子範囲（始端と終端）を論理識別子範囲リストＩｄＲａｎｇｅｓに追加する（ステップＳ１６０５）。論理識別子範囲リストＩｄＲａｎｇｅｓを求める計算式は下記の式５となる。
【０１３０】
ＩｄＲａｎｇｅｓ＝｛Ｉｄ  ｜  Ｉｄ＝Ｈ（Ｋｅｙ），Ｋｅｙ  ∈  ＫｅｙＲａｎｇｅｓ）｝・・・（式５）
【０１３１】
そして、空間充填曲線変換手段１０１７は、ステップＳ１６０５で得られた論理識別子範囲リストＩｄＲａｎｇｅｓを、検索式に対応する論理識別子範囲リストＩｄＲａｎｇｅｓとして登録・検索実行手段１０１８に返す（ステップＳ１６０６）。
【０１３２】
図１７は、ステップＳ１５０４のサブルーチンの処理を示すフローチャートである。メッセージ転送手段１０１３は、登録・検索実行手段１０１８からの検索メッセージの転送要求を受けると、データ格納先の論理識別子を担当（管理）するピアを検索するためのメッセージ転送処理を実行する。また、論理識別子範囲分割手段１０１５は、メッセージ転送手段１０１３がメッセージ転送処理を実行する際に、論理識別子範囲の分割に関する処理を実行する。
【０１３３】
なお、全てのピアで共有するデータを登録するときは、１つの論理識別子に対応するピアを発見（検索）する方式であって、Ｃｈｏｒｄのアルゴリズムと同様の方式であった。しかし、全てのピアで共有するデータを検索する処理は、論理識別子範囲に対応するピアを発見（検索）する処理であり、Ｃｈｏｒｄの方式とは異なる方式である。
【０１３４】
まず、論理識別子範囲分割手段１０１５は、登録・検索実行手段１０１８から与えられた論理識別子範囲ＩｄＲａｎｇｅｓをｓｕｃｃｅｓｓｏｒの論理識別子ｓで２つの論理識別子範囲（ＬｏｗＲａｎｇｅｓとＨｉｇｈＲａｎｇｅｓ）に分割し、当該ピア（この例ではピアｍ）に近い論理識別子範囲ＬｏｗＲａｎｇｅｓとピアｍから遠い論理識別子範囲ＨｉｇｈＲａｎｇｅｓを取得する（ステップＳ１７０１）。ここで、遠近とは、当該ピアｍの論理識別子ｍ＿Ｉｄが、合同式ｍｏｄを用いて、ＬｏｗＲａｎｇｅｓ内の任意の論理識別子Ｌ＿ＩｄとＨｉｇｈＲａｎｇｅｓ内の任意の論理識別子Ｈ＿Ｉｄとの間において以下の式６が成立することを指す。例えば、ｍ＿Ｉｄが５６でありｍ＝６の場合は、４０よりも４の方が近い。
【０１３５】
（Ｌ＿Ｉｄ  −  ｍ＿Ｉｄ）  ｍｏｄ（２＾ｍ−１）  ＜  （Ｈ＿Ｉｄ  −  ｍ＿Ｉｄ）  ｍｏｄ（２＾ｍ−１）・・・（式６）
【０１３６】
ここで、合同式ｍｏｄとは、整数を整除関係を用いて分類することにより定義される一種の等式である。ある自然数で割った余りが等しいかどうかを判定する。
【０１３７】
なお、ステップＳ１７０１において、論理識別子範囲ＩｄＲａｎｇｅｓにｓｕｃｃｅｓｓｏｒの論理識別子ｓが含まれていない場合は、ステップＳ１７０１〜Ｓ１７０４の処理が実行されずに、ステップＳ１７０５の処理に移行される。
【０１３８】
次に、論理識別子範囲分割手段１０１５は、ピアｍに近い論理識別子範囲ＬｏｗＲａｎｇｅｓがＮｕｌｌ（０）であるかどうかを判定する（ステップＳ１７０２）。ピアｍに近い論理識別子範囲ＬｏｗＲａｎｇｅｓがＮｕｌｌ（０）でないときは（ステップＳ１７０２のＮ）、論理識別子範囲分割手段１０１５は、自身のローカルデータ格納部１０１１から検索式に合致するデータを検索する（ステップＳ１７０３）。ピアｍに近い論理識別子範囲ＬｏｗＲａｎｇｅｓがＮｕｌｌ（０）でないときは、自身のピアｍとｓｕｃｃｅｓｓｏｒとの間の範囲はピアｍが管理する範囲であるからである。一方、ピアｍに近い論理識別子範囲ＬｏｗＲａｎｇｅｓがＮｕｌｌ（０）であるときは（ステップＳ１７０２のＹ）、ステップＳ１７０３の処理を実行せずに、ステップＳ１７０４の処理に移行する。
【０１３９】
ステップＳ１７０４では、論理識別子範囲分割手段１０１５は、残り論理識別子範囲Ｒｅｓｉｄｕａｌ（未だ検索が実行されていない残りの論理識別子範囲）に、ＨｉｇｈＲａｎｇｅｓを代入する（ステップＳ１７０４）。ステップＳ１７０３の処理が実行された場合は、残り論理識別子範囲Ｒｅｓｉｄｕａｌには、論理識別子範囲ＩｄＲａｎｇｅｓからピアｍとｓｕｃｃｅｓｓｏｒとの範囲を除いた論理識別子範囲（ＨｉｇｈＲａｇｅｓ）が代入される。
【０１４０】
次いで、論理識別子範囲分割手段１０１５は、ルーティングテーブル（ＦｉｎｇｅｒＴａｂｌｅ）１０１２に格納されたＦｉｎｇｅｒ（自身の論理識別子の１，２，４，・・・先の論理識別子、または自身の論理識別子１，２，４，・・・先の論理識別子が存在しない場合はそれらの論理識別子よりも大きく最も近い論理識別子を格納するテーブル）をピアｍから離れた順に読み出す（ステップＳ１７０５）。
【０１４１】
そして、論理識別子範囲分割手段１０１５は、残り論理識別子範囲Ｒｅｓｉｄｕａｌを、ステップＳ１７０５で探したＦｉｎｇｅｒの論理識別子によって２つの論理識別子範囲ＬｏｗＲａｎｇｅｓとＨｉｇｈＲａｎｇｅｓに分割する（ステップＳ１７０６）。
【０１４２】
そして、論理識別子範囲分割手段１０１５は、ピアｍから遠い論理識別子範囲ＨｉｇｈＲａｎｇｅｓがＮｕｌｌ（０）であるかどうかを判定する（ステップＳ１７０７）。ピアｍから遠い論理識別子範囲ＨｉｇｈＲａｎｇｅｓがＮｕｌｌ（０）でないときは（ステップＳ１７０７のＮ）、ピアＦｉｎｇｅｒにて、複数論理識別子範囲ＩｄＲａｎｇｅｓを探す処理を実行する（ステップＳ１７０８）。すなわち、Ｆｉｎｇｅｒのピアにおいて、図１７に示すステップＳ１７０１〜Ｓ１７０９の処理を実行する。
【０１４３】
一方、ピアｍから遠い論理識別子範囲ＨｉｇｈＲａｎｇｅｓがＮｕｌｌ（０）であるときは（ステップＳ１７０７のＹ）、ステップＳ１７０８の処理を実行せずに、ステップＳ１７０９の処理に移行する。
【０１４４】
ステップＳ１７０９において、論理識別子範囲分割手段１０１５は、残り論理識別子範囲ＲｅｓｉｄｕａｌにＬｏｗＲａｎｇｅｓを代入する（ステップＳ１７０９）。そして、処理を終了する。
【０１４５】
以上のように、この実施の形態３によれば、複数次元の分布情報（分布関数）を管理し、この分布にもとづいて論理識別子を算出するので、検索要求（検索メッセージ）を転送する論理識別子の範囲を狭くすることができる。
【０１４６】
また、この実施の形態３によれば、複数属性を一次元に変換する処理をメッセージ転送処理の中で行い、特定のピア（例えば論理識別子０あるいは１を担当するピア）を経由するのではなく、この変換処理を検索要求ピア内で終えて、算出された論理識別子の集合に対してメッセージが転送されるので、特定のピアに検索要求転送負荷が集中することない。
【０１４７】
また、この実施の形態３によれば、複数属性の論理識別子を算出する際に、値の均一性を担保しているので、これによっても、特定のピアにデータ管理負荷が集中することを防止している。
【０１４８】
さらに、この実施の形態３によれば、検索対象の論理識別子の範囲を転送途中に分割し、並列化しているので、検索範囲の広い場合にも検索要求のホップ数が増加しないようにすることができる。
【実施例】
【０１４９】
次に、実施の形態３における構成の具体例について図１８および図１９を参照して説明する。図１８は、検索式から論理識別子範囲リストを導くデータ構造を示す図である。図１９は、検索式で導かれた論理識別子範囲リストと対応するピアに検索メッセージを転送する例を示す図である。
【０１５０】
実施の形態３におけるオーバレイ管理システムにおいて、ｘとｙという２つの属性を持つデータが共有され、各データは図１８の１８６０の座標で示される値に分布しているものとする。オーバレイ管理システムには、図１９に示すピア（論理識別子０，４，１５，２０，２７，３０，３２，４０，５６のピア）が参加しており、論理識別子の空間のサイズ（ハッシュ空間のサイズ）は６４とする。また、データ登録と検索は、図１９において論理識別子０を持つピア１９０９が実行するものとする。このピアのルーティングテーブル１０１２には、Ｓｕｃｃｅｓｓｏｒ１９２１として論理識別子４を持つピア１９０１のＩＰアドレスが記憶されている。また、Ｆｉｎｇｅｒ１９２２としては、ピア１９０９の論理識別子０に、２のｉ乗（ｉ＝０，１，２，３，４，５）を加えた論理識別子の時計回り方向に初めて論理識別子を持つピアの情報が格納されている。この場合、ｉ＝０，１，２に対してはピア１９０１のＩＰアドレスを記憶し、ｉ＝３に対してはピア１９０２のＩＰアドレスを記憶する。同様に、ｉ＝４，５に対してもピア１９０３、１９０６の情報を記憶する。
【０１５１】
（１）データ登録；
まず、データ登録実行時の例として、登録検索受付手段１０１８が、ｘ属性の値が０１１、ｙ属性の値が１１１であるデータ（０１１，１１１）を登録したとする。このデータ登録要求は、空間充填曲線変換手段１０１７にて、このデータに対応する論理識別子に変換される。この空間充填曲線手段１０１７は、属性ｘと属性ｙに対応する空間充填曲線分布関数を、空間充填曲線分布格納部１０１６から取得する。ここでは、図１８の１８４０、および図１１の１１１３で示される関数が取得されたとする。
【０１５２】
次に、空間充填曲線がヒルベルト空間充填曲線であるとし、この変換規則を用いて、データ（０１１，１１１）に対応する論理識別子を取得する。まず第１ビットが取得され、ｘ属性の０、ｙ属性の１から生成されるビットパターン０１となり、これが保存される。次に、状態０（図１８の１８１１）のビットパターン０１の次に来る状態は０（図１８の１８２１）であることから、この状態に対応する変換規則が第２ビットに適用される。この第２ビットは、ｘ属性の１，ｙ属性の１から生成されるビットパターン１１であり、このビットパターン１１に対して変換規則１８２２が適用され、“１０”が得られる。これと、第１階層のビット列を組み合わせ、“０１１０”がＫｅｙとなる。同様に、第３ビットまで適用すると、“０１１０１０”（１０進表示で、２６）がＫｅｙとなる。これを空間充填曲線分布関数Ｄ（ｋ）に適用すると、０．４となり、これと論理識別子空間のサイズ６４から、論理識別子は２５となる。
【０１５３】
次に、この論理識別子に対して、登録メッセージを転送する。ここでの転送方式はＣｈｏｒｄの方式であるが、Ｆｉｎｇｅｒ１９２２より、目的の論理識別子２５よりも左回りで最も近いＦｉｎｇｅｒが論理識別子２０を持つピア１９０３であることから、このピア１９０３にＳｕｃｃｅｓｓｏｒの論理識別子を問い合わせる。ピア１９０３は論理識別子として２７を返し、目的の論理識別子２５は、このＦｉｎｇｅｒの論理識別子２０とそのＳｕｃｃｅｓｓｏｒ２７の間に存在する数であるので、この論理識別子２７を持つピア１９０４が、論理識別子２５のデータ（０１１，１１１）を管理するピアであると決定され、このピアのローカルデータ格納部１０１１に当該データが格納される。
【０１５４】
（２）データ検索；
次に、データ検索実行時の例として、登録検索受付手段１０１８が、ｘ属性に対する０１１の完全一致検索、ｙ属性に対する１＊＊の前方一致検索が実行されたとする。この検索要求は、空間充填曲線変換手段１０１７にて、対応する論理識別子リストに変換される。この空間充填曲線変換手段１０１７は、属性ｘと属性ｙに対応する空間充填曲線分布関数を、空間充填曲線分布格納部１０１６から取得する。ここでは、図１８の１８４０、および図１１の１１１３で示される関数が取得されたとする。
【０１５５】
次に、空間充填曲線がヒルベルト空間充填曲線であるとし、この変換規則を用いて、検索式（０１１，１＊＊）に対応する論理識別子範囲リストを取得する。まず第１ビットが取得され、ｘ属性の０、ｙ属性の１から生成されるビットパターン０１に対して変換規則を適用し、“０１”（図１８の１８１３）が“０１”（図１８の１８１２）に変換される規則から一次元変換後のビットパターンは０１となり、これが保存される。
【０１５６】
次に、状態０（図１８の１８１１）のビットパターン０１の次に来る状態は０（図１８の１８２１）であることから、この状態に対応する変換規則が第２ビットに適用される。この第２ビットは、ｘ属性の０，ｙ属性の＊（任意ビット）から生成されるビットパターン００，０１であるが、それぞれに対して、変換規則が適用され、“１０”と“１１”が得られる。これと、第１階層のビット列を組み合わせ、“０１１０”と“０１１１”が第２階層までの一次元変換後のＫｅｙである。同様に、第３ビットまで適用すると、“０１１０１０”、“０１１０１１”、“０１１１００”、“０１１１１１”がＫｅｙの集合となり、範囲としては、第１のＫｅｙＲａｎｇｅの起点が“０１１０１０”、終点が“０１１１００”となり、第２のＫｅｙＲａｎｇｅの起点および終点が“０１１０１１”となる。これらを空間充填曲線分布関数Ｄ（ｋ）に適用して、論理識別子範囲リスト１８４３が得られる。ここではＤの適用結果として、［０．４０，０．４５］と［０．５２５，０．５２５］が得られるので、これと論理識別子空間のサイズ６４から、論理識別子範囲リストは、｛［２５，２８]，［３３，３３］｝が得られる。
【０１５７】
次に、これらの範囲に含まれる論理識別子に対して、検索メッセージを転送して、検索結果を取得する。まず、検索結果を格納するリストを初期化し、他ピアからの結果を受け付けるプロセスを立ち上げた後に、この論理識別子範囲リストを探すように、ピア１９０９におけるメッセージ転送手段１０１３が呼び出される。
【０１５８】
まず、これらの範囲リストは、ピア１９０９のＳｕｃｃｅｓｓｏｒの論理識別子４を境界として分割されるが、宛先の範囲リスト｛［２５，２８]，［３３，３３］｝は、（０，４］には存在しないので、ここでは宛先範囲は発見されない。
【０１５９】
次に、最も離れたＦｉｎｇｅｒピア１９０６の論理識別子３２を境界として分割すると、範囲リストが｛［２５，２８]｝と｛［３３，３３]｝に分割され、範囲リスト｛［３３，３３]｝はピア１９０６に転送され、範囲リスト｛［２５，２８]｝はピア１９０３に転送される。ピア１９０６に転送された範囲リスト｛［３３，３３]｝は、ピア１９０６のＳｕｃｃｅｓｓｏｒであるピア１９０７の論理識別子４０を境に分割されるが、｛［３３，３３]｝は全て（３２，４０]に含まれるため、このピア１９０７が範囲［３３，３３]を管理するピアであると判定され、このピアのローカルデータ格納部１０１１を検索する。また、ピア１９０３に転送された範囲リスト｛［２５，２８]｝は、ピア１９０３のＳｕｃｃｅｓｓｏｒであるピア１９０４の論理識別子２７で分割され、（２０，２７］に含まれる論理識別子範囲｛［２５，２７］｝については、ピア２７にローカルデータ格納部１０１１を検索するように要求し、含まれない範囲｛（２７，２８］｝については、Ｆｉｎｇｅｒに転送される。
【０１６０】
ここでは、Ｆｉｎｇｅｒでもあるピア１９０４に転送され、ピア１９０４に転送された範囲｛（２７，２８］｝は、ピア１９０４の論理識別子２７とＳｕｃｃｅｓｓｏｒであるピア１９０５の論理識別子３０の間に存在するため、ピア１９０５に対してローカルデータ格納部１０１１を検索するように要求される。
【０１６１】
ピア１９０４、１９０５、１９０７で実行されたローカルデータ格納部１０１１に対する検索結果は、検索要求元である１９０９に対して送信され、検索要求元１９０９の検索結果受付プロセスがこの結果を受け取り、要求した全ての論理識別子範囲リスト｛［２５，２８］，［３３，３３］｝から検索結果が得られた場合、あるいはＴｉｍｅｏｕｔ時間が経過した場合に、当該検索処理が終了する。
【０１６２】
なお、上記の実施の形態１，３では、Ｃｈｏｒｄを元にしたオーバレイネットワークに、多次元属性値の分布の偏りを一次元に均一化して、範囲検索を行う手法を開示したが、Ｃｈｏｒｄと同様にピアが論理識別子を持つＳｔｒｕｃｔｕｒｅｄ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒと呼ばれる他の方式においても、同様の手法で同様の効果を得ることができる。これは、一次元の論理識別子空間を持つオーバレイネットワークに限らず、多次元の論理識別子を持つオーバレイネットワークについても、一次元に均一化した後に空間充填曲線を用いて再度一次元から多次元に変換することで、同様の効果が得られる。
【０１６３】
上記の各実施の形態１〜３において、ピアは、例えばサーバやパーソナルコンピュータなどの計算機（端末）で実現されている。また、各ピアにおいて、ＣＰＵなどの制御部がハードディスクなどの記憶手段に記憶されているプログラム（オーバレイ管理用プログラム）に従って実施の形態１〜３で説明した処理を実行することにより各構成部（手段）が実現される。また、各ピアにおいて、格納部、テーブルなどはハードディスクなどの記憶手段で実現される。
【産業上の利用可能性】
【０１６４】
本発明は、広域でデータを共有するリレーショナルデータベースなどに適用できる。特に、Ｒａｄｉｏ  Ｆｒｅｑｕｅｎｃｙ  Ｉｄｅｎｔｉｆｉｅｒ（ＲＦＩＤ）データの格納といった用途や、システム運用管理におけるログの格納といった用途や、メールやＷｅｂページの格納、Ｓｏｃｉａｌ  Ｎｅｔｗｏｒｋ  Ｓｅｒｖｉｃｅ（ＳＮＳ）データの格納などにも適用可能である。
【図面の簡単な説明】
【０１６５】
【図１】実施の形態１におけるオーバレイ管理システムの構成を示すブロック図である。
【図２】各属性の属性名および分布関数の例を示すテーブル図である。
【図３】実施の形態１におけるピア間でのメッセージの流れの具体例を示す説明図である。
【図４】実施の形態１におけるオーバレイ管理システムの動作を示すシーケンス図である。
【図５】属性値と分布関数の関係を示す説明図である。
【図６】実施の形態２におけるオーバレイ管理システムの構成を示すブロック図である。
【図７】空間充填曲線を用いてＣｌｕｓｔｅｒを分割する具体例を示す図である。
【図８】実施の形態２におけるピア間でのメッセージの流れの具体例を示す説明図である。
【図９】実施の形態２におけるオーバレイ管理システムの動作を示すシーケンス図である。
【図１０】実施の形態３におけるオーバレイ管理システムの構成を示すブロック図である。
【図１１】複数の属性の組インデックス毎に空間充填曲線分布を格納するテーブル図である。
【図１２】空間充填曲線を用いて２次元データを１次元データに変換する処理のアルゴリズムを視覚的に表わすデータ構造を示す説明図である。
【図１３】実施の形態３におけるオーバレイネットワークにて共有するデータを登録する処理を示すフローチャートである。
【図１４】ステップＳ１３０１のサブルーチンの処理を示すフローチャートである。
【図１５】実施の形態３におけるオーバレイネットワークにて共有するデータを検索する処理を示すフローチャートである。
【図１６】ステップＳ１５０１のサブルーチンの処理を示すフローチャートである。
【図１７】ステップＳ１５０４のサブルーチンの処理を示すフローチャートである。
【図１８】検索式から論理識別子範囲リストを導くデータ構造を示す図である。
【図１９】検索式で導かれた論理識別子範囲リストと対応するピアに検索メッセージを転送する例を示す図である。
【符号の説明】
【０１６６】
１１０，１２０，１３０  ピア
１１１  ローカルデータ格納部
１１２  ルーティングテーブル
１１３  メッセージ転送手段
１１７  個別属性分布関数格納部
１１８  登録・検索実行手段
５１０，５２０，５３０  ピア
５１１  ローカルデータ格納部
５１２  ルーティングテーブル
５１３  メッセージ転送手段
５１７  空間充填曲線変換手段
５１８  登録・検索実行手段
１０１０，１０２０，１０３０  ピア
１０１１  ローカルデータ格納部
１０１２  ルーティングテーブル
１０１３  メッセージ転送手段
１０１５  論理識別子範囲分割手段
１０１６  空間充填曲線分布格納部
１０１７  空間充填曲線変換手段
１０１８  登録・検索実行手段
【図１】
2008234563.tif 000003
【図２】
2008234563.tif 000004
【図３】
2008234563.tif 000005
【図４】
2008234563.tif 000006
【図６】
2008234563.tif 000007
【図８】
2008234563.tif 000008
【図９】
2008234563.tif 000009
【図１０】
2008234563.tif 000010
【図１１】
2008234563.tif 000011
【図１２】
2008234563.tif 000012
【図１３】
2008234563.tif 000013
【図１４】
2008234563.tif 000014
【図１５】
2008234563.tif 000015
【図１６】
2008234563.tif 000016
【図１７】
2008234563.tif 000017
【図１８】
2008234563.tif 000018
【図１９】
2008234563.tif 000019
【図５】
2008234563.tif 000020
【図７】
2008234563.tif 000021