(57)【要約】      （修正有）【課題】データが特定のノードに偏ることを防ぎ、ノード間での解析効率を向上させることを目的とする。【解決手段】ＳｋｉｐＬｉｓｔ構造を持つ構造化オーバレイネットワークに備わるノード装置であって、ノード数Ｎ及び定数Ｋを取得すると、自装置がルートノードであるか否かを判定するルートノード判定部と、自装置がルートノードである場合、自装置のレベルを［ｌｏｇＫＮ］＝ＬＲに設定し、自装置からＮ／２番目に位置する中間ノードのレベルをＬＲ−１とし、それ以外のノードのレベルをＬＲ−２とするルートノード設定部と、自装置がレベルＬＲからｉ番目のレベル（ＬＲ−ｉ）のノードである場合、自装置から［Ｎ／２ｉ＋１］番目に位置する中間ノードのレベルを（ＬＲ−ｉ−１）に設定し、それ以外のノードのレベルを（ＬＲ−ｉ−２）とする下位ノード設定部と、を備えるノード装置である。【選択図】図３
2018018194.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを構成するノード数Ｎ及び前記ネットワークに含まれるノードの最大レベルを示す定数Ｋを取得すると、自装置が前記ネットワークを構成するノードのうちの最上位のレベルに属しかつノードＩＤが最大のルートノードであるか否かを判定するルートノード判定部と、
自装置がルートノードである場合、自装置のレベルを［ｌｏｇＫＮ］＝ＬＲに設定し、自装置から［Ｎ／２］番目に位置する中間ノードのレベルを（ＬＲ−１）に設定し、探索時に経由する全てのノードのうちの中間ノードを除くノードのレベルを（ＬＲ−２）に設定するルートノード設定部と、
自装置がレベルＬＲからｉ番目のレベル（ＬＲ−ｉ）に設定された場合、自装置から［Ｎ／２ｉ＋１］番目に位置する中間ノードを探索し、当該中間ノードのレベルを（ＬＲ−ｉ−１）に設定し、探索時に経由する全てのノードのレベルを（ＬＲ−ｉ−２）に設定する下位ノード設定部と、
を備えるノード装置。
【請求項２】
ネットワークを構成するノードが実行するレベル設定方法であって、
前記ネットワークを構成するノード数Ｎ及び前記ネットワークに含まれるノードの最大レベルを示す定数Ｋを取得すると、自装置が前記ネットワークを構成するノードのうちの最上位のレベルに属しかつノードＩＤが最大のルートノードであるか否かを判定するルートノード判定手順と、
自装置がルートノードである場合、自装置のレベルを［ｌｏｇＫＮ］＝ＬＲに設定し、自装置から［Ｎ／２］番目に位置する中間ノードのレベルを（ＬＲ−１）に設定し、探索時に経由する全てのノードのうちの中間ノードを除くノードのレベルを（ＬＲ−２）に設定するルートノード設定手順と、
自装置がレベルＬＲからｉ番目のレベル（ＬＲ−ｉ）に設定された場合、自装置から［Ｎ／２ｉ＋１］番目に位置する中間ノードを探索し、当該中間ノードのレベルを（ＬＲ−ｉ−１）に設定し、探索時に経由する全てのノードのレベルを（ＬＲ−ｉ−２）に設定する下位ノード設定手順と、
を備えるノード管理方法。
【請求項３】
請求項２に記載の各手順をコンピュータに実行させるためのノード管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、ネットワークを構成するノードを階層的に管理する構造化オーバレイネットワーク技術に関する。
【背景技術】
【０００２】
近年、携帯電話や車といった移動通信体のセンサ情報やトラヒック情報などを蓄積し、解析することで、渋滞情報の予測やネットワークの故障推定を行うことができるようになった。これらの情報は刻々と発信され、時間の経過とともに増大するため、単一のデータベースにて管理することが難しく、分散ストレージ（いわゆるＫｅｙ  Ｖａｌｕｅ  Ｓｔｏｒｅ）を用いて管理されるようになった。中でも、分散ストレージ上の任意のデータに対して柔軟なクエリ（取得要求）を発行できることから、ＳｋｉｐＬｉｓｔと呼ばれるデータ構造を応用した分散ストレージ技術が提案されている（例えば、非特許文献１、２参照。）。
【０００３】
ＳｋｉｐＬｉｓｔを用いた分散ストレージでは、各ノードは２つの識別子を持ち、ノード自体を特定する識別子（ノードＩＤ）とノードのＳｋｉｐＬｉｓｔ上での高さを示すＬｅｖｅｌ（以下、レベルと表記する。）を持つ。レベルに従ってノードの集約構造を階層化し、ノード同士の関係性を木構造にする。ノードＩＤおよびレベルは、乱数を用いて決定される。ノードＩＤは、図１のような順序にて分散ストレージ上で並ぶようになっている。レベルについては、あらかじめ決めた定数（Ｋ）と乱数（ＲＡＮＤ）を用いて［−ｌｏｇＫＲＡＮＤ］にて決定される。これは、１／Ｋｉの確率でレベルｉ（≠０）となることを示している。
【０００４】
ここで、［  ］はガウス記号であり、［ａ］はａを超えない最大の整数を意味する。なお以下では［ａ，  ｂ］や［ａ，  ｂ）のような表現が頻出するが、［ａ，  ｂ］はａ以上ｂ以下を意味し、［ａ，  ｂ）はａ以上ｂより小さいを意味する。さらに、（ａ，  ｂ］はａより大きくｂ以下を意味し、（ａ，  ｂ）はａより大きくｂより小さいことを意味する。
【０００５】
分散ストレージ上では、両識別子を持つノードを以下の規則に基づき、各レベルにおける隣接関係を維持する（ｉ．ｅ．、ＴＣＰ等を用いたセッションを維持する）。
・レベルｉのノードは、レベルｉ（≧０）以下のレベルにも属する。
・レベルｉにて、ノードは時計回りに最も近いノードＩＤを持つノード（Ｓｕｃ）との隣接関係と、反時計回りに最も近いノードＩＤを持つノード（Ｐｒｅ）との隣接関係と、を維持する。
・レベルｉのノードは、レベル（ｉ−１）（≧０）に所属し、自身とＳｕｃとの間のノードＩＤを持つノードを子ノード（ｃｈｉｌｄｒｅｎ）として隣接関係を維持する。
・子ノードとなるノードは、自身を子ノードとして隣接関係を持つノードを親ノードとして隣接関係を維持する。
【０００６】
これらの特徴を持つ分散ストレージの例を図１に示す。各ノードはレベル０においてＰｒｅとの間の識別子（ノードＩＤ）を持つデータを保持する。各ノードは、特定のデータＩＤを有するデータを検索するとき、自身と隣接関係を持つノードの中で最もデータＩＤの近いノードに対して、Ｌｏｏｋ−ｕｐメッセージなどの探索要求を送る。もし、当該条件に当てはまらない場合は、自身の親サーバに対して探索依頼を送る。この２手順を繰り返し行うことで、分散ストレージがＮ台のノードを備える場合であっても、［ｌｏｇＮ］のＬｏｏｋ−ｕｐメッセージの転送にて、目的のデータを発見することができる。
【０００７】
非特許文献１の分散ストレージ技術は、データの取得だけでなく、データの統計値も取得することができる。例えば、特定の範囲に所属するデータの平均値を求める場合、当該範囲を持つ子ノード群を持つノードの中で最もレベルの小さなノードが、子ノードのデータの値を取得し計算する。また、特定の範囲に所属するデータの人気の高い上位ｐ個のデータを取得する場合、各ノードが自身の持つデータのうちの上位ｐ個の人気データを自身の親ノードに送信し、親ノードは、子ノードの情報からｐ個の人気の高いデータを選択し、さらに自身の親ノードに送信する。本手順を繰り返すことによって、上位ｐ個の人気データを取得することができる。このとき、各ノードは、予め決めた定数に等しいＫ個の子ノードからのデータに対してのみ処理を行えばよい。
【０００８】
非特許文献２は、乱数を用いて、各ノードのノードＩＤやレベルを決定している。この場合、特定のデータＩＤ区間に対して多くのノードが存在していたり、全く存在しない場合が発生する。図２に、１０２４ノードから構成されるＳｋｉｐＬｉｓｔを１０００回作成し、各レベルにおけるノード数分布を示す。Ｐｅｒｆｅｃｔ  ＳｋｉｐＬｉｓｔは、レベル１以上のノードは、１つ下のレベルの子ノードが必ず２台になるような理想的なＳｋｉｐＬｉｓｔを示している。Ｒａｎｄｏｍ  ＳｋｉｐＬｉｓｔは、乱数によってレベルを決めた場合のＳｋｉｐＬｉｓｔを示している。その結果、ノード数が１０２４に対して、レベルの最大値が２になるＳｋｉｐＬｉｓｔが構成される場合や、１ノードにて１つ下のレベルの子ノードを最大で１００ノード保持する場合が存在した。
【０００９】
ノードのノードＩＤやレベルを変更しない限り、ノードの偏りを解消することは難しいが、既存のＳｋｉｐＬｉｓｔを用いた分散データベースには本状況の改善手法は提案されていない。改善がなされない場合、ノードがオーバレイ上の特定の位置に偏ることにより、データが特定のノードに偏り、ノード間での解析効率が低下するという問題が生じる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０１３−２３５５１５号公報
【非特許文献】
【００１１】
【非特許文献１】Ｐ．  Ｗｉｌｌｉａｍ，  “Ｓｋｉｐ  Ｌｉｓｔｓ：  Ａ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ａｌｔｅｒｎａｔｉｖｅ  ｔｏ  Ｂａｌａｎｃｅｄ  Ｔｒｅｅｓ，”  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，  １９９０．
【非特許文献２】水谷后宏、間野暢、明石修、福田健介、“連続データに柔軟な大規模計算基盤、”コンピュータソフトウェア、ｖｏｌ．３０、ｐｐ．１０１−１１８、２０１３．
【非特許文献３】Ａ．  Ｒ．  Ｂｈａｒａｍｄｅ，  Ｍ．  Ａｇｒａｗａｌ，  ａｎｄ  Ｓ．  Ｓｅｃｈａｎ，  “Ｍｅｒｃｕｒｙ：  Ｓｃａｌａｂｌｅ  Ｒｏｕｔｉｎｇ  ｆｏｒ  Ｒａｎｇｅ  Ｑｕｅｒｉｅｓ，”  ｉｎ  ＡＣＭ  ＳＩＧＣＯＭＭ，  ２００４．
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本開示は、データが特定のノードに偏ることを防ぎ、ノード間での解析効率を向上させることを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、本開示は、ＳｋｉｐＬｉｓｔ構造を持つ構造化オーバレイネットワークのノード装置において、ステップａ１〜ａ３（ルートノードのみ）、またはステップｂ１〜ｂ２（全てのノード）を実行することにより、ＳｋｉｐＬｉｓｔを再構成する。
【００１４】
本開示に係るノード装置は、
ネットワークを構成するノード数Ｎ及び前記ネットワークに含まれるノードの最大レベルを示す定数Ｋを取得すると、自装置が前記ネットワークを構成するノードのうちの最上位のレベルに属しかつノードＩＤが最大のルートノードであるか否かを判定するルートノード判定部と、
自装置がルートノードである場合、自装置のレベルを［ｌｏｇＫＮ］＝ＬＲに設定し、自装置から［Ｎ／２］番目に位置する中間ノードのレベルを（ＬＲ−１）に設定し、探索時に経由する全てのノードのうちの中間ノードを除くノードのレベルを（ＬＲ−２）に設定するルートノード設定部と、
自装置がレベルＬＲからｉ番目のレベル（ＬＲ−ｉ）に設定された場合、自装置から［Ｎ／２ｉ＋１］番目に位置する中間ノードを探索し、当該中間ノードのレベルを（ＬＲ−ｉ−１）に設定し、探索時に経由する全てのノードのレベルを（ＬＲ−ｉ−２）に設定する下位ノード設定部と、
を備える。
【００１５】
本開示に係るレベル設定方法は、
前記ネットワークを構成するノード数Ｎ及び前記ネットワークに含まれるノードの最大レベルを示す定数Ｋを取得すると、自装置が前記ネットワークを構成するノードのうちの最上位のレベルに属しかつノードＩＤが最大のルートノードであるか否かを判定するルートノード判定手順と、
自装置がルートノードである場合、自装置のレベルを［ｌｏｇＫＮ］＝ＬＲに設定し、自装置から［Ｎ／２］番目に位置する中間ノードのレベルを（ＬＲ−１）に設定し、探索時に経由する全てのノードのうちの中間ノードを除くノードのレベルを（ＬＲ−２）に設定するルートノード設定手順と、
自装置がレベルＬＲからｉ番目のレベル（ＬＲ−ｉ）に設定された場合、自装置から［Ｎ／２ｉ＋１］番目に位置する中間ノードを探索し、当該中間ノードのレベルを（ＬＲ−ｉ−１）に設定し、探索時に経由する全てのノードのレベルを（ＬＲ−ｉ−２）に設定する下位ノード設定手順と、
を備える。
【００１６】
本開示に係るノード管理プログラムは、本開示に係るノード装置に備わる各機能をコンピュータに実現させるためのプログラムであり、本開示に係るノード装置のレベル設定方法に備わる各手順をコンピュータに実行させるためのプログラムであり、コンピュータ読み取り可能な記憶媒体に記録されていてもよい。
【発明の効果】
【００１７】
本開示によれば、データが特定のノードに偏ることを防ぎ、ノード間での解析効率を向上させることができる。
【図面の簡単な説明】
【００１８】
【図１】ＳｋｉｐＬｓｉｔの構成の一例を示す。
【図２】ＳｋｉｐＬｉｓｔにおけるレベル毎のノードの数の一例を示す。
【図３】実施形態に係るノード装置の機能構成例を示す。
【図４】ノード数が偶数でありかつ設定レベルに変更がない場合のＳｋｉｐＬｉｓｔの再構成例を示す。
【図５】ノード数が奇数でありかつ設定レベルに変更がない場合のＳｋｉｐＬｉｓｔの再構成例を示す。
【図６】ノード数が偶数でありかつ設定レベルが下がる場合のＳｋｉｐＬｉｓｔの再構成例を示す。
【図７】ノード数が偶数でありかつ設定レベルが上がる場合のＳｋｉｐＬｉｓｔの再構成例を示す。
【図８】ＳｋｉｐＬｉｓｔ上でのデータ探索例を示す。
【発明を実施するための形態】
【００１９】
以下、本開示の実施形態について、図面を参照しながら詳細に説明する。なお、本開示は、以下に示す実施形態に限定されるものではない。これらの実施の例は例示に過ぎず、本開示は当業者の知識に基づいて種々の変更、改良を施した形態で実施することができる。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２０】
図３に、実施形態に係るノード装置の構成の一例を示す。実施形態に係るノード装置は、ＳｋｉｐＬｉｓｔを用いた分散データベースの機能を備える。実施形態に係るノード装置は、ＭａｐＲｅｄｕｃｅ処理管理部１００、構造化オーバレイ管理部２００及び通信部３００を備える。構造化オーバレイ管理部２００は、Ｔｏｐｏｌｏｇｙ  Ｏｐｔｉｍｉｚｅｒを備える。
【００２１】
ＭａｐＲｅｄｕｃｅ処理管理部１００は、解析スキーム記憶部１１０、同期部１２０、データ記憶部（Ｄａｔａ  Ｂｕｆｆｅｒ）１３０を備える。解析スキーム記憶部１１０は、解析スキームバッファ（Ａｎａｌｙｓｉｓ  Ｓｃｈｅｍｅ  Ｂｕｆｆｅｒ）として機能し、ユーザが発行する解析スキームを保存する。同期部１２０は、子ノードからの解析結果を同期させる。データ記憶部１３０は、連続データを蓄積する。なお、ＭａｐＲｅｄｕｃｅ処理管理部１００から発行される解析スキームの伝搬には構造化オーバレイ管理部２００が提供するＡＰＩ（Ｓｃａｔｔｅｒ  ＡＰＩ）を利用する。
【００２２】
構造化オーバレイ管理部２００は、ＳｋｉｐＬｉｓｔマネージャ（ＳｋｉｐＬｉｓｔ  Ｍａｎａｇｅｒ）２１０、負荷分散部（Ｌｏａｄ  Ｂａｌａｎｃｉｎｇ  Ｅｘｅｃｕｔｏｒ）２２０、Ｔｏｐｏｌｏｇｙ  Ｏｐｔｉｍｉｚｅｒ２３０を備える。ＳｋｉｐＬｉｓｔマネージャ２１０は、ＳｋｉｐＬｉｓｔの構築及び維持を行う。ＳｋｉｐＬｉｓｔマネージャ２１０は、ルーティングバッファ２１１を備える。負荷分散部２２０は、ＳｋｉｐＬｉｓｔ上で負荷分散を行う。
【００２３】
通信部３００は、送信部（Ｓｅｎｄｅｒ）３１０、受信部（Ｒｅｃｅｉｖｅｒ）３２０を備える。送信部３１０は、ＴＣＰプロトコルを用いてデータを送信する。受信部３２０は、ＴＣＰプロトコルを用いてデータを受信する。なお、通信部３００はＯＳに実装されているＴＣＰ  Ｓｏｃｋｅｔを利用しデータの送受信を行うモジュールを用いることができる。
【００２４】
（ＳｋｉｐＬｉｓｔマネージャ２１０）
ノードＩＤがｐのノードＮｐは、レベルｉ以下の各レベルのノード情報をルーティングバッファ２１１内のルーティングテーブルに記録する。ノード情報は、隣接ノードのノードＩＤ及びアドレスを含む。ノードＩＤは、ハッシュ値となっており、“ｄｄｄ”と同様にＣｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇを行うために利用してもよい。アドレスは、例えばＩＰアドレスである。隣接ノードは、隣接方向によって識別されていることが好ましく、例えば、時計回りの隣接ノードをＳｕｃｃｅｓｓｏｒ、反時計回りの隣接ノードをＰｒｅｄｅｃｅｓｓｏｒとする。
【００２５】
ノードＮｐのレベルｋ（０≦ｋ≦ｉ）におけるＳｕｃｃｅｓｓｏｒのノードＩＤをｓｐ，ｋとし、レベルｋのＰｒｅｄｅｃｅｓｓｏｒのノードＩＤをｐｐ，ｋとする。また、ノードＮｐが担当するデータＩＤ空間は、ｐｐ，０＜ｐを満たす時、（ｐｐ，０，ｐ］とする。また、ｐ＜ｐｐ，０を満たす時、ノードＮｐが担当するデータＩＤ空間は（ｐｐ，０，Ｌ）、［０，ｐ］とする（ＬはデータＩＤ空間全体のサイズであり、データＩＤ：ＬはデータＩＤ：０と同値となっており、データＩＤ空間はリング型の構造になっている）。なお、以下では上記の範囲を纏めて、（ｐｐ，０，ｐ］とする。
【００２６】
なお、ノードＮｐが担当するデータＩＤ空間は、Ｓｈｕｆｆｌｅ処理の際に配置されるデータＩＤの範囲を意味してもよい。例えば、ノードＮｐが担当するデータＩＤ空間が１０から１００とする。この時、データＩＤが４５や７６のデータはノードＮｐが保持することになる。データＩＤ空間は、時間をＩＤにしたトラヒックデータを管理してもよい。例えば、レベル０のノードＮ７は時刻６：０１〜時刻７：００に該当するデータを担当し、レベル０のノードＮ９は時刻８：０１〜時刻９：００に該当するデータを担当する。
【００２７】
さらに、レベルがｋ（１≦ｋ≦ｉ）にて、ノードＩＤが［ｐ，ｓｐ，ｋ）を満たすレベル（ｋ−１）のノード群を子ノードとして当該ノード情報を保持し、レベルｉで自身のノードＩＤであるｐを子ノードとして保持しているノードを親としてノード情報をルーティングバッファ２１１に保持する。なお、ノードＮｐが担当するノードＩＤ空間と子ノードのノードＩＤ空間を逆方向に定める理由は、子ノードが担当するノードＩＤ空間とノードＮｐが担当するノードＩＤ空間が重って冗長になることを避けるためである。ノード数をＮｑ（０＜Ｎ、０≦ｑ）とした時、レベルがｋ＞ｑを満たす場合、レベルｋはｑとする。なお、レベルｑのノードをルートノードとし、ＳｋｉｐＬｉｓｔ上の分散計算を統括する役割を果たす。レベルｑに属するルートノードが複数存在する場合、レベルｑにおけるＳｕｃｃｅｓｓｏｒのノードＩＤが自身のノードＩＤよりも小さいと判断したノードが、レベル（ｑ＋１）に所属することにし、レベルｑのノード群を子に持つ。なお、これらの子ノード、親ノード、ルーティングテーブル（ＳｕｃｃｅｓｓｏｒとＰｒｅｄｅｃｅｓｓｏｒノードの情報）はルーティングバッファ２１１に保存される。
【００２８】
図１は、上記のような解析データの集約構造の例を示す。ノードＮ２のルーティングバッファ２１１は、レベル０のノード情報としてノードＮ１，Ｎ３のノード情報を、レベル１のノード情報としてノードＮ０，Ｎ４のノード情報を保持する。さらに、ノードＮ２は、レベル０のノードＮ３を子ノードとして記録し、レベル２のノードＮ０を親ノードとして記録している。ノードＮ２と同様に、ノードＮ０もルーティングテーブル、親ノード、子ノードの情報を保持している。なお、レベル２において、ノードＮ０と隣接するノードが存在しないため、当該ノードがルートノードとなっている。
【００２９】
ノードＮｐにおけるＳｋｉｐＬｉｓｔの構築方法の一例について説明する。
まず、Ｊｏｉｎ処理を実行する。Ｊｏｉｎ処理は、ノードＮｐが担当するデータＩＤ空間を決定し、親ノード、子ノードを決定し、ルーティングバッファ２１１内にルーティングテーブルを構築する。
【００３０】
ＳｋｉｐＬｉｓｔマネージャ２１０は、自身のノードＩＤであるｐを、ＳｋｉｐＬｉｓｔ上に存在している任意のノードに対して、ｐを担当するノードを探索するメッセージ（Ｊｏｉｎメッセージ）を送る。
当該メッセージを受けたレベルａのノードＮｂのＳｋｉｐＬｉｓｔマネージャ２１０は、自身のルーティングテーブルに記録している全てのＳｕｃｃｅｓｓｏｒのノード情報に対して、［ｂ，ｓｂ，ｉ）（０≦ｉ≦ａ）の範囲にｐが含まれているかどうかを、ルーティングテーブルの上位から調べる。［ｂ，ｓｂ，ｉ）にｐが含まれていた場合、当該範囲の子ノードの中で、Ｎｐに最も近く、Ｎｐを超えないノードＩＤを持つ子ノードに対して、当該メッセージを転送する。含まれていない場合、親ノードに対して、当該メッセージを転送し、親ノードに対してＪｏｉｎ処理を委託する。
【００３１】
なお、本転送は、時計回り又は反時計回りのいずれか一方の予め定められた方向に対して行われることが好ましい。この転送処理をノード間で再帰的に繰り返すことにより、ノードＮｐを担当するノードに当該メッセージが到達する。ｐを管理するノードをノードＮｍとした時、ノードＮｍはノードＮｐに対して自身の親、子ノード、ルーティングテーブルの情報を転送すると同時に、ｐを自身のルーティングテーブル、親、子ノードの情報に対して転送することにより反映する。以上の手順によって、各ノードがＳｋｉｐＬｉｓｔ構造に対してＪｏｉｎ処理を完了し、ＳｋｉｐＬｉｓｔ構造が構築される。
【００３２】
（負荷分散部２２０）
構造化オーバレイ上で連続データの負荷分散を行うために各ノードがオーバレイ上をランダムウォークするクエリ（Ｓａｍｐｌｉｎｇ  Ｑｕｅｒｙ）を投げ、オーバレイ上のノードをランダムに選択しつつ、当該ノードの負荷情報を集めて、全体の負荷を推定する方法がある（例えば、非特許文献３参照。）。この手法における問題点として、規模に応じて、Ｓａｍｐｌｉｎｇ  Ｑｕｅｒｙの送信回数を適切に指定する必要があり、集めた負荷情報を元にした全体の推定精度に影響を与える可能性がある。
【００３３】
既存技術に対して、実施形態に係る負荷推定技術は、ＳｋｉｐＬｉｓｔの集約構造を用いることで規模に依存せず全体の負荷の推定を的確に行うことが可能になっている。具体的には、各ノードの構造化オーバレイ管理部２００の負荷分散部２２０が自身の負荷情報を親ノードに対して送信し、親ノードの負荷分散部２２０は負荷のランキングを作成する。ランキングは、子ノードから送信されてきた負荷情報から、負荷の高い順にノード情報をソートし、上位Ｒ（１≦Ｒ）番目までのノード情報と下位Ｒ（１≦Ｒ）番目までのノード情報を抽出する処理をルートノードまで再帰的に繰り返し転送する。ルートノードの負荷分散部２２０は、負荷情報を参考に負荷の低いノードに負荷の高いノードが管理するデータＩＤ空間の中から負荷が均一になるようなデータＩＤをルーティングバッファ２１１のルーティングテーブルから選択し、当該負荷の低いノードに対してデータＩＤを追加するように指示する。さらに、当該ノードに負荷の高いノードに対して追加したデータＩＤを用いてＪｏｉｎメッセージを送信するよう命令し、負荷の均一化を図る。
【００３４】
なお、負荷の高いノードと負荷の低いノードを区別する判別式を以下に示す。ルートノードが受け取ったランキングのｉ（１≦ｉ≦Ｒ）番目の負荷情報をＬｉ、全体の負荷の平均値をＡＶＧ、ランキングのｉ番目の負荷値をＱｉとし、定数α（０＜α＜１）を用いて、Ｑｉは、
【数２】
2018018194.tif 000003
と表すことにする。なお、以下で説明するランキングとは、集約した上位・下位のランキングを一体化した、１から２Ｒまでの順位を持つランキングと見なす。
【００３５】
ルートノードの構造化オーバレイ管理部２００の負荷分散部２２０において、式（２）を用いて、まずランキング１位の負荷情報Ｌ１とランキング２Ｒ位の負荷情報Ｌ２Ｒの負荷値Ｑ１，Ｑ２Ｒを求め、Ｑ１＝１、Ｑ２Ｒ＝０を満たす場合、ルートノードは、Ｌ１のノード（以下「ノード１」と記す）に対して、Ｌ２Ｒのノード（以下、「ノード２Ｒ」と記す）がデータＩＤ空間の分割要求を行うように、ノード２Ｒに命令する。その結果、ノード２Ｒの負荷分散部２２０は、ノード１のＩＰアドレスをルートノードから取得し、ノード１に対して、自身の負荷情報Ｌ２Ｒを通知する。Ｌ２Ｒを知ったノード１は、負荷分散部２２０において、自身の負荷Ｌ１’が（Ｌ１＋Ｌ２Ｒ）／２となる様に、自身のデータＩＤ空間を分割し、ノード２Ｒに対して分割したデータＩＤ空間と当該データＩＤ空間に関連するデータ群をノード２Ｒに送信する。ノード２Ｒは、ＭａｐＲｅｄｕｃｅ処理管理部１００のデータ記憶部１３０に蓄積する。
【００３６】
なお、ルートノードはノード１およびノード２Ｒのノードに対してデータＩＤ空間の分割要求を通知した後、次はノード２とノード２Ｒ−１に対しても同様の処理を行う。本処理は負荷の高いノードと負荷の低いノードの負荷値が１，０とならなくなるまで繰り返す。各負荷値が１、０とならない場合、ルートノードは負荷分散を終了し、全体の負荷分散が完了する。なお、この負荷分散の処理は、ルートノードにて一定時間間隔で行われるものとし、負荷情報を各ノードの親ノードに対して送信する命令をルートノードから送信し、各ノードの親ノードから子ノードに対して発行されるＳｔａｂｉｌｉｚａｔｉｏｎメッセージに付加され、上層から下層のノードに転送されていく。これにより、負荷分散処理に必要なメッセージ数を抑制することができる。
【００３７】
（Ｓｈｕｆｆｌｅ処理）
センサやモニタから発行されたｎのデータｎ（ＨａｓｈＩＤ：ｎ）がノードｐに到着したとする。データｎに対してＳｈｕｆｆｌｅ処理を行う際、ノードｐは当該データを担当するノードに当該データを転送しなければならない。転送方法は前述のＳｋｉｐＬｉｓｔの構築方法と同様の転送方法を用いる。
【００３８】
（トポロジーオプティマイザ２３０）
トポロジーオプティマイザ（Ｔｏｐｏｌｏｇｙ  Ｏｐｔｉｍｉｚｅｒ）２３０は、ＳｋｉｐＬｉｓｔを再構成する。再構成する理由としては、分散ストレージ上では、ノードが新たに追加されたり、故障したりすることで、ＳｋｉｐＬｉｓｔ構造が崩れる場合があるためである。
【００３９】
前提として、各ノードは自身の子ノードのレベル以下に属しているノード数を記録しているものとし、ルートノード（最上位のレベルに属し、最大のノードＩＤを持つノード）は全ノード数（Ｎ）を記録しているものとする。
【００４０】
トポロジーオプティマイザ２３０は、ＳｋｉｐＬｉｓｔマネージャ２１０内のルーティングバッファ２１１から隣接関係情報を取得し、各ノードが各レベルにてＫ個の子ノードに対して隣接関係を持つようにＳｋｉｐＬｉｓｔを再構成する。ここで、「Ｋ」は、各ノードが予め共通で設定した値である。
【００４１】
前提条件を用いたＳｋｉｐＬｉｓｔの再構成は、下記の手順を通して、ルートノードから順に行われるものとする。
・ステップａ１．ルートノードは、［ｌｏｇＫＮ］＝ＬＲを自身のレベルに設定する。
・ステップａ２．ルートノードは、自身から［Ｎ／２］番目のノードを探索し、当該ノードのレベルをＬＲ−１とする。
・ステップａ３．探索時に経由する全てのノードのレベルをＬＲ−２とする。
【００４２】
ステップａ２において、ルートノードとルートノードから［Ｎ／２］番目のノードの隣接関係が構成される。さらに、上記の同様の手順を、レベルＬＲ−１から下記の手順を繰り返して行うこととする。
【００４３】
・ステップｂ１．レベル（ＬＲ−ｉ）（≧０）のノードは、自身から［Ｎ／２ｉ＋１］番目のノードを探索し、当該ノードのレベルを（ＬＲ−ｉ−１）とする。ここで、０＜ｉ＜ＬＲである。すなわち、自身のもつレベルの下のレベルにおいて、隣接するノードを探索し、自身のノードと探索したノードを接続する。
・ステップｂ２．探索時に経由する全てのノードのレベルを（ＬＲ−ｉ−２）とする。ただし、レベル０のノードを経由する場合は、−１としない。
【００４４】
図４及び図５に、設定レベルに変更がない場合のＳｋｉｐＬｉｓｔの再構成例を示す。丸の内側に記載されている数字はレベルを示し、ノードの符号の数字はノードＩＤを示す。図４（ａ）は、再構成前のＳｋｉｐＬｉｓｔの構成であり、Ｎ＝４でありかつＫ＝２の場合を示す。ノードＮ５３がレベル２であり、ノードＮ５２がレベル２であり、ノードＮ５１及びＮ５４がレベル０である。レベル０のノードはリング状に接続されており、ノードＮ５４とノードＮ５１は接続されている。最上位のレベルに属しかつ最大のノードＩＤを持つノードはノードＮ５３であるため、ノードＮ５３がルートノードとなる。
【００４５】
ステップａ１では、ルートノードＮ５３は、［ｌｏｇ２４］＝２を自身のレベルに設定する。
ステップａ２では、ルートノードＮ５３は、自身から［４／２］＝２番目のノードを探索し、当該ノードのレベルを｛［ｌｏｇ２４］−１｝＝１とする。このとき、ノードＮ５３はノードＮ５１に対してレベルが１であることを通知し、ノードＮ５１はこの通知に従って自装置のレベルを１に設定する。
ステップａ３では、ルートノードＮ５３は、探索時に経由する全てのノードのレベルを｛［ｌｏｇ２４］−２｝＝０とする。このとき、ノードＮ５３はノードＮ５２及びＮ５４に対してレベルが０であることを通知し、ノードＮ５２及びＮ５４はこの通知に従って自装置のレベルを０に設定する。これにより、図４（ｃ）に示すように、ノードＮ５２はレベル１を削除する。
【００４６】
ステップｂ１では、レベル１のノードがノードを探索し、探索したノードのレベルを０にする。例えば、レベル１のノードＮ５１が自身から［４／２２］＝１番目のノードＮ５４を探索し、ノードＮ５３が自身から１番目のノードＮ５２を探索する。これにより、図４（ｄ）に示すように、レベル１のノードＮ５１とレベル０のノードＮ５４が接続され、レベル１のノードＮ５３とレベル０のノードＮ５２が接続される。
【００４７】
ステップｂ２では、探索時に経由する全てのノードのレベルを０とする。これにより、図４（ｅ）に示すように、ノードＮ５１からＮ５４のレベルが０に設定される。
【００４８】
なお、図５も同様の手順にてレベルの再設定を行う。ここで、図５では、Ｎが奇数である。そのため、ステップａ１では、ルートノードＮ５４は、［ｌｏｇ２５］を求め、２を自身のレベルに設定する。ステップａ２では、ルートノードＮ５４は、自身から［５／２］を求め、２番目のノードを探索する。また、当該ノードのレベルを｛［ｌｏｇ２５］−１｝を求め、１とする。このとき、ノードＮ５４はノードＮ５２に対してレベルが１であることを通知し、ノードＮ５２はこの通知に従って自装置のレベルを１に設定する。また、図５（ｄ）のステップｂ１にて、レベル１のノードＮ５２が自身から［５／２２］を求め、１番目のノードＮ５１及び２番目のノードＮ５５を探索する。このように、ステップｂ１では、［Ｎ／２Ｋ］の値に余りが発生する場合、演算値を繰り上げる。これにより、レベル１のノードＮ５２は、自身から１番目及び２番名の子ノードと接続される。
【００４９】
図６に、設定レベルが下がる場合のＳｋｉｐＬｉｓｔの再構成例を示す。丸の内側に記載されている数字はレベルを示し、ノードの符号の数字はノードＩＤを示す。図６では、Ｎ＝４でありかつＫ＝３の設定から、Ｎ＝４でありかつＫ＝２に設定を変更する場合について説明する。
【００５０】
図６（ａ）は、再構成前のＳｋｉｐＬｉｓｔの構成であり、Ｎ＝４でありかつＫ＝３の場合を示す。ノードＮ６４がレベル３であり、ノードＮ６３がレベル２であり、ノードＮ６２がレベル１であり、ノードＮ６１がレベル０である。レベル０のノードはリング状に接続されており、ノードＮ６４とノードＮ６１は接続されている。最上位のレベルに属しかつ最大のノードＩＤを持つノードはノードＮ６４であるため、ノードＮ６４がルートノードとなる。
【００５１】
ステップａ１では、ルートノードＮ６４は、［ｌｏｇ２４］＝２を自身のレベルに設定する。
ステップａ２では、ルートノードＮ６４は、自身から［４／２］＝２番目のノードを探索し、当該ノードのレベルを｛［ｌｏｇ２４］−１｝＝１とする。このとき、ノードＮ６４はノードＮ６２に対してレベルが１であることを通知し、ノードＮ６２はこの通知に従って自装置のレベルを１に設定する。
ステップａ３では、ルートノードＮ６４は、探索時に経由する全てのノードのレベルを｛［ｌｏｇ２４］−２｝＝０とする。このとき、ノードＮ６４はノードＮ６３及びＮ６１に対してレベルが０であることを通知し、ノードＮ６３及びＮ６１はこの通知に従って自装置のレベルを０に設定する。これにより、図６（ｃ）に示すように、ノードＮ６３はレベル１及び２を削除する。
【００５２】
ステップｂ１では、レベル１のノードがノードを探索し、探索したノードのレベルを０にする。例えば、レベル１のノードＮ６２が自身から１番目のノードＮ６１を探索し、ノードＮ６１のレベルを０にする。レベル１のノードＮ６４が自身から１番目のノードＮ６３を探索し、ノードＮ６３のレベルを０にする。これにより、図６（ｄ）に示すように、レベル１のノードＮ６２とレベル０のノードＮ６１が接続され、レベル１のノードＮ６４とレベル０のノードＮ６３が接続される。
【００５３】
ステップｂ２では、探索時に経由する全てのノードのレベルを０とする。これにより、図６（ｅ）に示すように、ノードＮ６１からＮ６４のレベルが０に設定される。
【００５４】
図７に、設定レベルが上がる場合のＳｋｉｐＬｉｓｔの再構成例を示す。丸の内側に記載されている数字はレベルを示し、ノードの符号の数字はノードＩＤを示す。図７では、Ｎ＝４でありかつＫ＝１の設定から、Ｎ＝４でありかつＫ＝２に設定を変更する場合について説明する。
【００５５】
図７（ａ）は、再構成前のＳｋｉｐＬｉｓｔの構成であり、Ｎ＝４でありかつＫ＝１の場合を示す。Ｋ＝１であるため、ノードＮ７１，７２，７３，７４のいずれもレベル０である。レベル０のノードはリング状に接続されており、ノードＮ７４とノードＮ７１は接続されている。最上位のレベルに属しかつ最大のノードＩＤを持つノードはノードＮ７４であるため、ノードＮ７４がルートノードとなる。
【００５６】
ステップａ１では、ルートノードＮ７４は、［ｌｏｇ２４］を自身のレベルに設定する。これにより、図７（ｂ）に示すように、ノードＮ７４のレベルがレベル２に設定される。このとき、レベルが２になるため、レベル１及び２のノードＮ７４を追加する。
ステップａ２では、ルートノードＮ７４は、自身から［４／２］＝２番目のノードを探索し、当該ノードのレベルを｛［ｌｏｇ２４］−１｝＝１とする。これにより、図７（ｃ）に示すように、ノードＮ７２がレベル１に設定される。
ステップａ３では、探索時に経由する全てのノードのレベルを｛［ｌｏｇ２４］−２｝＝０とする。これにより、図７（ｃ）に示すように、ノードＮ７１〜７４のレベルが０に設定される。
【００５７】
ステップｂ１及びｂ２における動作は、図６（ｄ）及び図６（ｅ）と同様である。
【００５８】
図８に、探索方法の一例を示す。図８では、時系列データをレベル０ではノードＩＤがＩＤ０〜ＩＤ９の１０台のノードＮ０〜Ｎ９が管理する。ノードＮ９が時刻８：３７のデータを管理しているものとする。時刻８：３７のｋｅｙを持つデータＤ０８３７がノードＩＤ４のノードＮ４に到着した場合、ノードＮ４は、時刻８：３７のデータを管理するノードを探索し、データを送信する。
【００５９】
具体的には、ノードＮ４は、自身のルーティングテーブルを参照し、子ノードの中で、時刻８：３７のデータを管理しているノードを探す。例えば、時刻８：３７のデータがノードＮ４と自身の経路情報全ての間に含まれるかどうかをルーティングテーブルの上位から調べる。そのようなノードが検出された場合、そのノードに対してデータを送信する。一方、そのようなノードが検出されない場合、自身の親ノードに対して、探索命令（Ｌｏｏｋ−ｕｐメッセージ）を送る。本手順を繰り返すことで、データは下位レベルから上位に上がり、上位レベルから下位レベルに転送されていき、やがて、ノードＮ９が時刻８：３７のデータＤ０８３７を管理するノードと判定できる。
【００６０】
上記の手順のように、探索とレベルの再設定をｉ＝１からｉ＝［ｌｏｇＫＮ］−１まで繰り返すことによって、ルートノードから全てのノードがＰｅｒｆｅｃｔ  ＳｋｉｐＬｉｓｔの構造になり、各ノードが各レベルにてＫ個の子ノードを管理すればよい（ノード数が奇数の場合、Ｋ＋１個の子ノードを管理するノードが存在する）。これにより、ノードがオーバレイ上の特定の位置に偏ることを防ぎ、データの偏り、ノード間での解析効率を向上させることができると考えられる。以下、探索時における各ノードの具体的な処理を説明する。
【００６１】
ノードＮ４のＳｋｉｐＬｉｓｔマネージャ２１０は、自身のルーティングテーブルを参照し、時刻８：３７のデータを管理するノードを探索する。ノードＮ４の担当するデータＩＤ空間には時刻８：３７が含まれていないため、レベル０及び１のノードＮ４のＳｋｉｐＬｉｓｔマネージャ２１０は、親ノードであるノードＮ０に対して、時刻８：３７のデータを管理するノードを探索するためのＬｏｏｋＵｐメッセージを転送する。ＬｏｏｋＵｐメッセージを受信したノードＮ０は、ＬｏｏｋＵｐメッセージの宛先である時刻８：３７を読み取り、自身のルーティングテーブルの上位から、時刻８：３７を含むＳｕｃｃｅｓｓｏｒを調べる。
【００６２】
ノードＮ０は、時刻８：３７を管理するノードを発見できなかった場合、親、子ノードから時刻８：３７を管理するノードがあるかどうかを調べる。ノードＮ９が時刻８：３７のデータを管理しており、ノードＮ９の親ノードはノードＮ８である。この場合、ノードＮ０は、ノードＮ８が管理していると判断し、ノードＮ８に対して、ＬｏｏｋＵｐメッセージを転送する。
【００６３】
ＬｏｏｋＵｐメッセージを受け取ったノードＮ８のＳｋｉｐＬｉｓｔマネージャ２１０は、自身のルーティングテーブルを上位から調べる。ノードＮ８のルーティングバッファ２１１は、ノードＮ９を子ノードとして記憶している。ノードＮ８のＳｋｉｐＬｉｓｔマネージャ２１０は、ノードＮ９が時刻８：３７のデータを管理していると判定することができる。ノードＮ８のＳｋｉｐＬｉｓｔマネージャ２１０は、自身のルーティングテーブルを参照し、ＬｏｏｋＵｐメッセージの送信元であるノードＮ４に対して、ノードＮ９のＩＰアドレスを伝達する。
【００６４】
ノードＮ４は、時刻８：３７のデータをノードＮ９に対して転送する。ノードＮ９のＳｋｉｐＬｉｓｔマネージャ２１０は、データＤ０８３７をノードＮ４から受信し、データ記憶部１３０に記憶する。これにより、Ｓｈｕｆｆｌｅ処理が完了する。
【００６５】
なお、センサやモニタから発行されたデータに対してＳｈｕｆｆｌｅ処理を行う際の通信回数は、ノード数をｎとすると１データあたり２ｌｏｇ（ｎ）となっており、ノード数が増えたとしてもＳｈｕｆｆｌｅ処理を行う際の通信コストの増加率は低いため、規模拡張性に優れたＳｈｕｆｆｌｅを実現していることがわかる。
【００６６】
（ＳｋｉｐＬｉｓｔの維持）
次に、ＳｋｉｐＬｉｓｔマネージャ２１０における、ＳｋｉｐＬｉｓｔを維持するための方法について説明する。
【００６７】
ＳｋｉｐＬｉｓｔを維持するために、各ノードのＳｋｉｐＬｉｓｔマネージャ２１０が各レベルのＳｕｃｃｅｓｓｏｒ、Ｐｒｅｄｅｃｅｓｓｏｒ、および親ノードに対して定期的にＳｔａｂｉｌｉｚａｔｉｏｎメッセージを送信し、ノードの生存・離脱を確認する。応答がない場合は、離脱と判定し、ＳｕｃｃｅｓｓｏｒやＰｒｅｄｅｃｅｓｓｏｒ、Ｐａｒｅｎｔの候補となるノードを再度検索し、代替ノードの情報を得ることで、ＳｋｉｐＬｉｓｔ構造を更新する。
【００６８】
この手順以外にも、ＳｕｃｃｅｓｓｏｒとＰｒｅｄｅｃｅｓｓｏｒの数を増やすことで、容易にＳｋｉｐＬｉｓｔ構造を維持することが可能になる。具体的には、各ノードが自身のＳｕｃｃｅｓｓｏｒのＳｕｃｃｅｓｓｏｒの情報やＰｒｅｄｅｃｅｓｓｏｒのＰｒｅｄｅｃｅｓｓｏｒの情報を持つということである。こうすることで、Ｓｕｃｃｅｓｓｏｒが離脱しても、瞬時に、当該ＳｕｃｃｅｓｓｏｒのＳｕｃｃｅｓｓｏｒに対して接続関係を結ぶだけで、ＳｋｉｐＬｉｓｔの構造を維持することができる。
【００６９】
（ＭａｐＲｅｄｕｃｅ処理管理部１００）
ＳｋｉｐＬｉｓｔに対して、解析スキームと呼ばれるユーザが定義する解析内容の反映方法を述べる。解析スキームは任意のノードに対して投入することができ、ユーザは、解析スキームに解析スキームの識別子（ＡＩＤ）を付けて投入する。解析スキームを全ノードに反映するために、当該ＭａｐＲｅｄｕｃｅ処理管理部１００は、Ｓｃａｔｔｅｒ（ＡｎａｌｙｓｉｓＳｃｈｅｍｅ）という構造化オーバレイ管理部２００が提供するＡＰＩを用いる。
【００７０】
Ｓｃａｔｔｅｒ  ＡＰＩを用いて、解析スキームの配布を構造化オーバレイ管理部２００に対して依頼すると、まず解析スキームを投入されたノードのＳｋｉｐＬｉｓｔマネージャ２１０はルートノードを探索する。ルートノードを発見すると、当該ルートノードに対して、ＳｃａｔｔｅｒＡｎａｌｉｚｅｒメッセージを転送し、ルートノードが自身の子ノードに対して当該メッセージを転送する。ＳｃａｔｔｅｒＡｎａｌｉｚｅｒメッセージはユーザが定義した解析スキームと共にＳｋｉｐＬｉｓｔの木構造に従って、各ノードに対して再帰的に転送される。ＳｃａｔｔｅｒＡｎａｌｉｚｅｒメッセージを受け取った各ノードは、自身の同期部１２０（Ｓｃｈｅｍｅ  Ｃｏｏｒｄｉｎａｔｏｒ）に対して、当該スキームのＡＩＤと当該スキームを登録する。同期部１２０は、登録されている解析スキームの保存や、解析スキームの実行時において、子ノードからの解析結果の同期を行う。
【００７１】
（解析例）
全てのノードに対して、１日のトラヒックデータが保存されているとする。トラヒックデータは時系列データであり、昼間のトラヒックデータは少ないが、夜間のトラヒックデータは莫大に存在しているものとする。これらのデータがＳｈｕｆｆｌｅ処理によって、各データの担当ノードに対して転送され、各担当ノードは当該トラヒックデータを管理しているものとする。なお、トラヒックデータは時刻と通信端末のＩＰアドレスから構成しているものとする。このトラヒックデータから、通信回数が最も多い１００位までの通信端末のＩＰアドレスを特定するといった内容の解析スキームをＳｋｉｐＬｉｓｔ上のノードに反映していたとする。
【００７２】
負荷の均一化は、例えば、負荷の高いノードと低いノードのノードＩＤ空間の負荷の均一化である。一定時間間隔で、ルートノードの構造化オーバレイ管理部２００のＳｋｉｐＬｉｓｔマネージャ２１０は、自身の子ノードに対して負荷情報の転送を依頼する。その後、子ノードは自身の子ノードに対して当該依頼を転送する。これらの処理を再帰的に行うことによって、レベル０のノード群に対して負荷情報の転送依頼が到達する。レベル０のノードは、自身の負荷情報としてトラヒックデータの総量を親ノードに伝達する。各親ノードから負荷情報を受信した親ノードは、負荷情報のランキングを作成し、再度、自身の親ノードに対して転送する。この処理を再帰的に行うことによって、ルートノードにランキングが伝達される。ランキングを受け取ったルートノードは、負荷分散部２２０において、負荷の低いノードを負荷の高いノードが担当するデータＩＤ空間に対して、Ｊｏｉｎ処理を行うように命令する。例えば、負荷の高いノードの負荷が１００、負荷の低いノードの負荷が１０としたとき、負荷の低いノードは１０と１００の中間である５５の負荷になるように、負荷の高いノードからデータＩＤ空間を分けてもらい、分けてもらったデータＩＤ空間に対してＪｏｉｎ処理を行う。これを繰り返すことによって、連続データの負荷の隔たりを解消することができる。
【００７３】
まず、各ノードが自身のＭａｐＲｅｄｕｃｅ処理管理部１００の中のデータ記憶部１３０内で管理するトラヒックデータから、通信端末のＩＰ毎の通信回数のランキングを作成し、上位１００位までの通信端末のＩＰとその端末の通信回数を親ノードに転送する。各親ノードは自身が管理する全ての子ノードから、ランキングが送られてくるまで待機し、ランキングの結果が揃ったところで、再度、１００位までのランキングを受信データから作成し、自身の親ノードに対してランキングを転送する。このランキングの作成を再帰的に行うことによって、ルートノードに対してランキングが到着する。ルートノードにてランキングを再度構成した後に、ＡＩＤに登録されている解析を依頼したノードに対して解析結果を転送する。この時、各ノードの計算量は、負荷分散部２２０によって連続データであるトラヒックデータの負荷の偏りが平滑化されており、さらに各解析が平衡木の構造を持つ構造化オーバレイ上で再帰的に行われることにより、解析の並列性を最大化することができる。
【００７４】
なお、本開示の装置はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。ノードのＭａｐＲｅｄｕｃｅ処理管理部１００、構造化オーバレイ管理部２００、通信部３００の各構成要素を、それぞれソフトウェア（プログラム）として構築し、ＭａｐＲｅｄｕｃｅ処理管理モジュール、構造化オーバレイ管理モジュール、通信モジュールとし、ノードとして利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させること可能である。
【産業上の利用可能性】
【００７５】
本開示は情報通信産業に適用することができる。
【符号の説明】
【００７６】
１００：ＭａｐＲｅｄｕｃｅ処理管理部
１１０：解析スキーム記憶部
１２０：同期部
１３０：データ記憶部
２００：構造化オーバレイ管理部
２１０：ＳｋｉｐＬｉｓｔマネージャ
２１１：ルーティングバッファ
２２０：負荷分散部
２３０：トポロジーオプティマイザ
３００：通信部
３１０：送信部
３２０：受信部
【図１】
2018018194.tif 000004
【図２】
2018018194.tif 000005
【図３】
2018018194.tif 000006
【図４】
2018018194.tif 000007
【図５】
2018018194.tif 000008
【図６】
2018018194.tif 000009
【図７】
2018018194.tif 000010
【図８】
2018018194.tif 000011