(57)【要約】【課題】データ再配置先の決定処理にかかる計算時間を削減することができるデータ再配置装置を提供すること。【解決手段】分散処理システムを構成する各サーバについて、サーバＩＤと、該サーバの担当キー範囲とを含むサーバデータを保持するサーバデータ保持部１１と、キー空間が新たな区分に分割された各新規キー範囲について、その範囲と、該新規キー範囲のＩＤとを含む新規キー範囲データを保持する新規キー範囲データ保持部１２と、キー範囲の重複部分に含まれるキーに対応するデータが存在するサーバデータおよび新規キー範囲データをそれぞれ表すノード間にエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複データ量に基づく重みを付与する木構造データ生成部１３と、木構造データにおいてノードを共有しないエッジ群のうち、重みの合計値が最大になるものを選択する組み合わせ算出部１４とを備える。【選択図】      図１
2013117763.tif 000002
【特許請求の範囲】
【請求項１】
キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを保持するサーバデータ保持部と、
前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを保持する新規キー範囲データ保持部と、
前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与する木構造データ生成部と、
前記木構造データにおいてノードを共有しないエッジの組合せ（非隣接エッジ群）のうち、該エッジ群を構成するエッジに付与された重みの合計値（重み合計）が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する組み合わせ算出部と、
を備えたデータ再配置装置。
【請求項２】
前記木構造データ生成部は、前記サーバデータをそのキー範囲を連続させる順序で並べたリスト、および、前記新規キー範囲データをそのキー範囲を連続させる順序で並べたリストを用いて、各リストにおける先頭のサーバデータおよび先頭の新規キー範囲データのうちいずれか一方をルートノードとして他方をその子ノードとし、親子となった２つのサーバデータおよび新規キー範囲データ間で重複するデータ量に基づく重みを親子間のエッジに付与し、以降、親子となった２つのノードのうちキー範囲の最大値が大きい方を新たに親ノードとして、小さい方のノードが属するリストにおける次のノードをその子ノードとしていく処理を繰り返すことにより、前記木構造データを生成することを特徴とする請求項１に記載のデータ再配置装置。
【請求項３】
前記組み合わせ算出部は、前記木構造データの深さｉ（ｉは１以上、前記木構造データの深さ以下の整数）までの部分木において、深さi−１のノードおよび深さiのノードを端点とする各エッジ（深さiのエッジ）について、深さｉの該エッジを含む前記非隣接エッジ群および深さｉの該エッジを含まない前記非隣接エッジ群の各重み合計を再帰的処理によりそれぞれ算出することにより、前記木構造データの最下層の各エッジについて２つずつ算出された重み合計のうち最大値を有する非隣接エッジ群を選択することを特徴とする請求項１または請求項２に記載のデータ再配置装置。
【請求項４】
前記組み合わせ算出部は、深さ１までの部分木において深さ１の各エッジについて、深さ１の該エッジを含まない前記非隣接エッジ群の前記重み合計として０を適用し、深さ１の該エッジを含む前記非隣接エッジ群の前記重み合計として該エッジの重みを適用し、深さｉ（ｉは２以上、前記木構造データの深さ以下の整数）までの部分木において深さｉの各エッジについて、深さｉの該エッジを含まない前記非隣接エッジ群の前記重み合計として、深さｉ−１までの部分木において深さｉ−１の各エッジについて２つずつ算出された重み合計のうちの最大値を適用し、深さｉの該エッジを含む前記非隣接エッジ群の前記重み合計として、深さｉ−１までの部分木において深さｉ−１の各エッジについて２つずつ算出された重み合計のうち、深さｉの該エッジに隣接する深さｉ−１のエッジを含む前記非隣接エッジ群の前記重み合計を除いた最大値に、深さｉの該エッジの重みを加算した値を適用することを特徴とする請求項３に記載のデータ再配置装置。
【請求項５】
キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを取得し、
前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを取得し、
前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与し、
前記木構造データにおいてノードを共有しないエッジの組合せ（非隣接エッジ群）のうち、該エッジ群を構成するエッジに付与された重みの合計値（重み合計）が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する、データ再配置方法。
【請求項６】
前記サーバデータをそのキー範囲を連続させる順序で並べたリスト、および、前記新規キー範囲データをそのキー範囲を連続させる順序で並べたリストを用いて、各リストにおける先頭のサーバデータおよび先頭の新規キー範囲データのうちいずれか一方をルートノードとして他方をその子ノードとし、親子となった２つのサーバデータおよび新規キー範囲データ間で重複するデータ量に基づく重みを親子間のエッジに付与し、以降、親子となった２つのノードのうちキー範囲の最大値が大きい方を新たに親ノードとして、小さい方のノードが属するリストにおける次のノードをその子ノードとしていく処理を繰り返すことにより、前記木構造データを生成することを特徴とする請求項５に記載のデータ再配置方法。
【請求項７】
前記木構造データの深さｉ（ｉは１以上、前記木構造データの深さ以下の整数）までの部分木において、深さi−１のノードおよび深さiのノードを端点とする各エッジ（深さiのエッジ）について、深さｉの該エッジを含む前記非隣接エッジ群および深さｉの該エッジを含まない前記非隣接エッジ群の各重み合計を再帰的処理によりそれぞれ算出することにより、前記木構造データの最下層の各エッジについて２つずつ算出された重み合計のうち最大値を有する非隣接エッジ群を選択することを特徴とする請求項５または請求項６に記載のデータ再配置方法。
【請求項８】
キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを取得するサーバデータ取得ステップと、
前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを取得する新規キー範囲データ取得ステップと、
前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与する木構造データ生成ステップと、
前記木構造データにおいてノードを共有しないエッジの組合せ（非隣接エッジ群）のうち、該エッジ群を構成するエッジに付与された重みの合計値（重み合計）が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する組み合わせ算出ステップと、
をコンピュータ装置に実行させるコンピュータ・プログラム。
【請求項９】
前記木構造データ生成ステップにおいて、前記サーバデータをそのキー範囲を連続させる順序で並べたリスト、および、前記新規キー範囲データをそのキー範囲を連続させる順序で並べたリストを用いて、各リストにおける先頭のサーバデータおよび先頭の新規キー範囲データのうちいずれか一方をルートノードとして他方をその子ノードとし、親子となった２つのサーバデータおよび新規キー範囲データ間で重複するデータ量に基づく重みを親子間のエッジに付与し、以降、親子となった２つのノードのうちキー範囲の最大値が大きい方を新たに親ノードとして、小さい方のノードが属するリストにおける次のノードをその子ノードとしていく処理を繰り返すことにより、前記木構造データを生成することを特徴とする請求項８に記載のコンピュータ・プログラム。
【請求項１０】
前記組み合わせ算出ステップにおいて、前記木構造データの深さｉ（ｉは１以上、前記木構造データの深さ以下の整数）までの部分木において、深さi−１のノードおよび深さiのノードを端点とする各エッジ（深さiのエッジ）について、深さｉの該エッジを含む前記非隣接エッジ群および深さｉの該エッジを含まない前記非隣接エッジ群の各重み合計を再帰的処理によりそれぞれ算出することにより、前記木構造データの最下層の各エッジについて２つずつ算出された重み合計のうち最大値を有する非隣接エッジ群を選択することを特徴とする請求項８または請求項９に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散処理システムを構成する各サーバに配置されたデータの再配置先を決定するデータ再配置装置、データ再配置方法、および、コンピュータ・プログラムに関する。
【背景技術】
【０００２】
１つ以上のサーバを用いてデータを処理する分散処理システムが知られている。このような分散処理システムは、処理対象のデータを、そのデータに基づいて算出されるキーを担当するサーバに配置する。各サーバは、キー空間（キーがとり得る範囲）が分割されたキー範囲のうちのいずれかを担当している。そして、各サーバは、配置されたデータに対する処理を行う。
【０００３】
このような分散処理システムは、各サーバの負荷を均一にするため、各サーバの担当するキー範囲を新規のキー範囲に変更してデータを再配置することがある。具体的には、このような分散処理システムは、各サーバが担当していたキー範囲のうち、新規のキー範囲に含まれない部分に対応するデータを、新たにその部分を担当することになった他のサーバに移動する。このようなデータ再配置処理では、サーバ間のデータ移動量を最小化するよう、データの再配置先を決定することが求められる。
【０００４】
データ移動量を最小化するようなデータ再配置先を決定する問題は、二部グラフにおける最大重み完全マッチング問題（割り当て問題）とみなすことができる。非特許文献１には、このような割り当て問題の解決手法が開示されている。
【０００５】
割り当て問題について、図１９を参照して説明する。割り当て問題は、|V+|=|V-|（＝ｎ、ｎは１以上の整数）なる二部グラフ（bipartite graph）G=(V+,V-;A)および各エッジa∈Aの重みｗ(a)∈Rが与えられたときに、エッジの重みの和Σw(a) (a∈M)を最大にする完全マッチングM⊆Aを求める問題である。ここで、V+およびV-は、ノード集合Ｖが２つに分割された各ノード集合であり、ｎは、V+およびV-にそれぞれ属するノード数である。エッジａは、ノード間を結ぶ辺であり、Ａは、V+に属するノードおよびV-に属するノード間を結ぶエッジの集合である。上述のようなデータ再配置先を決定する問題では、各サーバから移動させるデータ量の総和が最小の場合、各サーバが移動させずに保持しているデータ量の総和が最大となる。よって、上述のデータ移動量を最小化するようなデータ再配置先を決定する問題は、各サーバが移動させずに保持しているデータ量の総和を最大化する問題とみなすことができる。
【０００６】
つまり、図１９におけるV+に属するノードとして、分散処理システムを構成する各サーバを適用し、V-に属するノードとして各新規キー範囲を適用する。そして、求めたa∈Mの一方の端点であるサーバに、もう一方の端点である新規キー範囲を新たに担当させると考えればよい。このとき、最大化するのは、サーバから移動させないデータ量である。そこで、各エッジに付与する重みw(a)は、エッジaの一方の端点であるサーバが、もう一方の端点である新規キー範囲を担当することになった場合に、該サーバが他のサーバに移動せずに保持し続けるデータ量に基づいて定めればよい。このような重みを各エッジに付与した二部グラフを生成するには、ｎ個のサーバのそれぞれが、ｎ個の新規キー範囲のそれぞれを担当することになった場合に、該サーバが移動せずに保持し続けるデータの量を求める。そこで、このような二部グラフの生成処理に要する計算時間は、O(n^2)となる。ここで、O(n^x)は、計算時間がｎのｘ乗のオーダーであることを表す。また、そのようなエッジの重みの総和を最大化するM⊆Aを求める処理に要する計算時間は、非特許文献１において開示される手順に基づけばO(n^3)となる。よって、データ再配置先の決定処理にかかる時間は、O(n^3)となる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】“Bipartite Matching & the Hungarian Method”、[online]、[２０１１年１１月１日検索]、インターネット<URL:http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述のようなデータ再配置先の決定処理は、サーバ数ｎに対してスケーラブルに行うことが求められる。ところが、膨大なデータを処理する分散処理システムでは、サーバ数ｎが非常に大きくなる。上述の非特許文献１をデータ再配置先の決定処理に適用した場合、その計算時間は、O(n^3)となりｎに対して幾何級数的に増加してしまう。
【０００９】
本発明は、上述の課題を解決するためになされたもので、データ再配置先の決定処理にかかる計算時間を削減することができるデータ再配置装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明のデータ再配置装置は、キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを保持するサーバデータ保持部と、前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを保持する新規キー範囲データ保持部と、前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与する木構造データ生成部と、前記木構造データにおいてノードを共有しないエッジの組合せ（非隣接エッジ群）のうち、該エッジ群を構成するエッジに付与された重みの合計値（重み合計）が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する組み合わせ算出部と、を備える。
【００１１】
本発明のデータ再配置方法は、キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを取得し、前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを取得し、前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与し、前記木構造データにおいてノードを共有しないエッジの組合せ（非隣接エッジ群）のうち、該エッジ群を構成するエッジに付与された重みの合計値（重み合計）が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する。
【００１２】
本発明のコンピュータ・プログラムは、キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを取得するサーバデータ取得ステップと、前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを取得する新規キー範囲データ取得ステップと、前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与する木構造データ生成ステップと、前記木構造データにおいてノードを共有しないエッジの組合せ（非隣接エッジ群）のうち、該エッジ群を構成するエッジに付与された重みの合計値（重み合計）が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する組み合わせ算出ステップと、をコンピュータ装置に実行させる。
【発明の効果】
【００１３】
本発明は、データ再配置先の決定処理にかかる計算時間を削減することができるデータ再配置装置を提供することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態としてのデータ再配置装置のハードウェア構成図である。
【図２】本発明の実施の形態としてのデータ再配置装置の機能ブロック図である。
【図３】本発明の実施の形態におけるサーバデータのデータ構造の一例を示す図である。
【図４】本発明の実施の形態としてのとしてのデータ再配置装置の動作を説明するシーケンス図である。
【図５】本発明の実施の形態におけるサーバデータおよび新規キー範囲データの一例を説明する模式図である。
【図６】（ａ）および（ｂ）は、本発明の実施の形態における木構造データの生成手法の一例を説明する模式図である。
【図７】（ａ）および（ｂ）は、図６に続く模式図である。
【図８】本発明の実施の形態としてのとしてのデータ再配置装置の木構造データリスト生成動作を説明するフローチャートである。
【図９】本発明の実施の形態としてのとしてのデータ再配置装置の木構造データ生成動作を説明するフローチャートである。
【図１０】本発明の実施の形態としてのとしてのデータ再配置装置のエッジ生成初期動作を説明するフローチャートである。
【図１１】本発明の実施の形態としてのとしてのデータ再配置装置のエッジ生成動作を説明するフローチャートである。
【図１２】本発明の実施の形態としてのとしてのデータ再配置装置の組み合わせ算出動作を説明するフローチャートである。
【図１３】本発明の実施の形態としてのとしてのデータ再配置装置の１つの木構造データに関する組み合わせ算出動作を説明するフローチャートである。
【図１４】本発明の実施の形態における重み合計データの一例を説明する模式図である。
【図１５】本発明の実施の形態としてのとしてのデータ再配置装置の重み合計算出動作を説明するフローチャートである。
【図１６】本発明の実施の形態としてのとしてのデータ再配置装置の、対象エッジを選択しない場合の重み合計算出動作を説明するフローチャートである。
【図１７】本発明の実施の形態としてのとしてのデータ再配置装置の、対象エッジを選択する場合の重み合計算出動作を説明するフローチャートである。
【図１８】本発明の実施の形態としてのとしてのデータ再配置装置のエッジ選択動作を説明するフローチャートである。
【図１９】データ再配置先の決定処理に関連技術を適用した場合の二部グラフを説明する模式図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。なお、本実施の形態としてのデータ再配置装置が対象とする分散処理システムは、キー空間（キーがとりうる範囲）に含まれるキーに対応付けられたデータを処理するものである。また、この分散処理システムは、キー空間がｎ個の区分に分割されたキー範囲をそれぞれ担当するｎ個のサーバによって構成されているものとする。また、本実施の形態としてのデータ再配置装置は、ｎ個の各サーバから、担当するキー範囲、キー範囲に対するデータ分布、および、キー範囲に対する負荷分布をそれぞれ表す情報を取得しているものとする。また、本実施の形態としてのデータ再配置装置は、ｎ個の各サーバから取得した負荷分布を表す情報に基づいて、負荷が均一になるようにキー空間を新たなｎ個のキー範囲（新規キー範囲）に分割しているものとする。
【００１６】
まず、本発明の実施の形態としてのデータ再配置装置１のハードウェア構成を図１に示す。
【００１７】
図１において、データ再配置装置１は、ＣＰＵ（Central Processing Unit）１００１と、ＲＡＭ（Random Access Memory）１００２と、ＲＯＭ（Read Only Memory）１００３と、ハードディスク等の記憶装置１００４とを備えたコンピュータ装置によって構成されている。
【００１８】
ＲＯＭ１００３および記憶装置１００４には、コンピュータ装置を本実施の形態のデータ再配置装置１として機能させるためのコンピュータ・プログラムおよび各種データが記憶されている。
【００１９】
ＣＰＵ１００１は、ＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムおよび各種データをＲＡＭ１００２に読み込んで実行する。
【００２０】
次に、データ再配置装置１の機能ブロック構成を図２に示す。
【００２１】
図２において、データ再配置装置１は、サーバデータ保持部１１と、新規キー範囲データ保持部１２と、木構造データ生成部１３と、組み合わせ算出部１４とを備えている。ここで、サーバデータ保持部１１および新規キー範囲データ保持部１２は、記憶装置１００４によって構成されている。また、木構造データ生成部１３および組み合わせ算出部１４は、ＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムおよび各種データをＲＡＭ１００２に読み込んで実行するＣＰＵ１００１によって構成される。なお、データ再配置装置１の各機能ブロックのハードウェア構成は上述の構成に限定されない。
【００２２】
サーバデータ保持部１１は、各サーバの識別情報（ＩＤ）と、前述のキー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを保持している。サーバデータの一例を図３に示す。図３に示すサーバデータは、ＩＤと、担当するキー範囲の最小値（最小キー）と、最大値（最大キー）とからなる。
【００２３】
また、サーバデータ保持部１１は、サーバデータを、そのキー範囲を連続させる順序で並べたリストとして保持していてもよい。例えば、サーバデータ保持部１１は、キー範囲の昇順にサーバデータを並べたリストを保持していてもよい。
【００２４】
新規キー範囲データ保持部１２は、前述の各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報（ＩＤ）とを含む新規キー範囲データを保持している。新規キー範囲データのデータ構造は、図３に示したサーバデータと同様であってもよい。
【００２５】
また、新規キー範囲データ保持部１２は、新規キー範囲データを、そのキー範囲を連続させる順序で並べたリストとして保持していてもよい。例えば、新規キー範囲データ保持部１２は、キー範囲の昇順に新規キー範囲データを並べたリストを保持していてもよい。
【００２６】
木構造データ生成部１３は、各サーバデータを表すノード、および、各新規キー範囲データを表すノード間にエッジ（ノード間を結ぶ辺）を生成することにより木構造データを生成する。具体的には、木構造データ生成部１３は、各サーバデータおよび各新規キー範囲データの組合せのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する組合せを抽出する。そして、木構造データ生成部１３は、抽出した組合せのサーバデータを表すノードおよび新規キー範囲データを表すノード間に、親子関係を示すエッジを生成する。また、木構造データ生成部１３は、生成した各エッジに対して、重複するデータ量に基づく重みを付与する。このようにして、木構造データ生成部１３は、重みを付与したエッジにより連結したノードのいずれかをルートノードとみなした木構造データを生成する。
【００２７】
このような木構造データを生成する手法の一例について説明する。
【００２８】
例えば、木構造データ生成部１３は、サーバデータのリスト（サーバデータを、そのキー範囲を連続させる順序で並べたリスト）、および、新規キー範囲データのリスト（新規キー範囲データを、そのキー範囲を連続させる順序で並べたリスト）を用いて、木構造データを生成することが可能である。具体的には、木構造データ生成部１３は、上記の各リストにおける先頭のサーバデータおよび先頭の新規キー範囲データのうちいずれか一方をルートノードとし、他方をその子ノードとする。そして、木構造データ生成部１３は、親子となった２つのノードに対応するサーバデータおよび新規キー範囲データ間で重複するデータ量に基づく重みを、親子間のエッジに付与する。以降、木構造データ生成部１３は、親子となった２つのノードのうちキー範囲の最大値が大きい方を新たに親ノードとして、小さい方のノードが属するリストにおける次のノードをその子ノードとして前述の親子間のエッジに重みを付与する処理を繰り返す。このようにして、木構造データ生成部１３は、キー範囲が最も小さいサーバデータまたは新規キー範囲データをルートノードとし、重複データが存在するサーバデータおよび新規キー範囲データ間に親子関係を表すエッジを生成していくことにより、木構造データを生成する。
【００２９】
組み合わせ算出部１４は、木構造データ生成部１３によって生成された木構造データにおいてノードを共有しないエッジの組合せ（非隣接エッジ群）のうち、該エッジ群を構成するエッジに付与された重みの合計値（重み合計）が最大になるものを選択する。
【００３０】
このような非隣接エッジ群を選択する手法の一例について説明する。
【００３１】
例えば、組み合わせ算出部１４は、このような非隣接エッジ群を選択するために、木構造データの部分木を用いた再帰的処理を行ってもよい。具体例としては、組み合わせ算出部１４は、木構造データの深さ（階層数）をｉ（ｉは１以上、木構造データの深さ以下の整数）としたときの再帰的処理を、各深さｉについて実行してもよい。この場合、再帰的処理は、木構造データの深さｉまでの部分木（以降、部分木ｉとも記載する）における非隣接エッジ群の重み合計を、部分木ｉ−１における非隣接エッジ群の重み合計に基づいて算出する処理である。
【００３２】
この場合、組み合わせ算出部１４は、深さi−１のノードおよび深さiのノードを端点とする各エッジ（深さiのエッジ）について、深さｉの該エッジを含む非隣接エッジ群および深さｉの該エッジを含まない非隣接エッジ群の各重み合計を再帰的処理によりそれぞれ算出してもよい。これにより、組み合わせ算出部１４は、木構造データに含まれる各エッジについて２つずつ重み合計を算出することになる。そして、組み合わせ算出部１４は、最下層の各エッジについて２つずつ算出された重み合計のうち最大値を有する非隣接エッジ群を選択する。
【００３３】
具体的には、組み合わせ算出部１４は、まず、部分木１において深さ１の各エッジについて、深さ１の該エッジを含まない非隣接エッジ群の重み合計として０を適用する。また、組み合わせ算出部１４は、部分木１において深さ１の該エッジを含む非隣接エッジ群の重み合計として該エッジの重みを適用する。
【００３４】
以降、組み合わせ算出部１４は、ｉ＝２以降の部分木ｉにおいて深さｉの各エッジについて、深さｉの該エッジを含まない非隣接エッジ群の重み合計として、部分木ｉ−１において深さｉ−１の各エッジについて２つずつ算出された重み合計のうちの最大値を適用する。また、組み合わせ算出部１４は、部分木ｉにおいて深さｉの該エッジを含む非隣接エッジ群の重み合計として、部分木ｉ−１において深さｉ−１の各エッジについて２つずつ算出された重み合計のうち、深さｉの該エッジに隣接する深さｉ−１のエッジを含む非隣接エッジ群の重み合計を除いた最大値に、深さｉの該エッジの重みを加算した値を適用する。
【００３５】
以上のように構成されたデータ再配置装置１の動作について、図面を参照して説明する。
【００３６】
まず、図４を用いて、データ再配置装置１の動作の概略について説明する。
【００３７】
ここでは、まず、木構造データ生成部１３は、サーバデータ保持部１１からサーバデータのリストを取得する（ステップＳ１）。
【００３８】
次に、木構造データ生成部１３は、新規キー範囲データ保持部１２から新規キー範囲データのリストを取得する（ステップＳ２）。ステップＳ１およびステップＳ２の処理は順不同である。
【００３９】
次に、木構造データ生成部１３は、取得した各サーバデータおよび各新規キー範囲データのうち、キー範囲が重複する組合せであって、かつ、重複する範囲に対応するデータが存在する組合せを抽出する。そして、木構造データ生成部１３は、抽出した組合せのサーバデータおよび新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成する。そして、木構造データ生成部１３は、そのようなエッジに対して、重複データ量に基づく重みを付与する（ステップＳ３）。
【００４０】
次に、組み合わせ算出部１４は、生成した木構造データにおける非隣接エッジ群のうち、該エッジ群を構成するエッジに付与された重みの合計が最大となる非隣接エッジ群を選択する（ステップＳ４）。例えば、前述のように、組み合わせ算出部１４は、木構造データの部分木を用いた再帰的処理により非隣接エッジ群を選択してもよい。
【００４１】
このようにして、データ再配置装置１は、組み合わせ算出部１４によって選択されたエッジ群に基づいて、各エッジの一方の端点が表すサーバに対して、他方の端点が表す新規キー範囲を割り当てる。このとき、ノードを共有しないエッジ群が選択されているので、選択されたエッジ群のうちの複数のエッジの端点が、同一のサーバデータを表すことはない。したがって、データ再配置装置１は、非隣接エッジ群に基づいて、各サーバが担当する新規キー範囲を一意に決定可能となる。これにより、データ再配置装置１は、各サーバの新規キー範囲に基づいて、各サーバに配置されていたデータの再配置先を決定する。
【００４２】
以上で、データ再配置装置１は、動作を終了する。
【００４３】
次に、サーバデータおよび新規キー範囲データの具体例を用いながら、データ再配置装置１の動作の詳細について説明する。
【００４４】
ここでは、まず、上述のステップＳ１およびＳ２で、図５に示すようなサーバデータおよび新規キー範囲データが取得されたものとする。図５は、各サーバデータおよび各新規キー範囲データのＩＤおよびキー範囲を模式的に表した図である。
【００４５】
図５において、ａ、ｂ、ｃおよびｄは、サーバのＩＤを表す。また、ａ’、ｂ’、ｃ’およびｄ’は、新規キー範囲のＩＤを表す。以降、ＩＤがｘ（ｘは、ａ、ｂ、ｃまたはｄ）のサーバを、サーバｘとも記載する。また、ＩＤがｘ’（ｘ’は、ａ’、ｂ’、ｃ’またはｄ’）の新規キー範囲を、新規キー範囲ｘ’とも記載する。図５において、キー空間は、k1以上k8未満の値である。k1〜k8は、それぞれキーの値を表し、k1<k2<k3<k4<k5<k6<k7<k8である。この例の場合、サーバａ、ｂ、ｃおよびｄは、それぞれ、キー範囲[k1,k3)、[k3,k4)、[k4,k6)および[k6,k8)を担当している。なお、“[ki,kj)”（ki,kjは、k1~k8のいずれか）は、ki以上kj未満のキー範囲を表す。例えば、各サーバデータが図３に示したデータ構造であれば、サーバaのサーバデータには、IDとしてa、最小キーとしてk1、最大キーとしてk3が含まれる。また、新規キー範囲a’、b’、c’およびd’は、それぞれ[k1,k2)、[k2,k5)、[k5,k7)および[k7,k8)の範囲である。例えば、各新規キー範囲データが図３に示したデータ構造であれば、新規キー範囲ａ’の新規キー範囲データには、ＩＤとしてａ’、最小キーとしてk1、最大キーとしてk2が含まれる。また、ここでは、サーバデータのリストには、キー範囲の昇順であるサーバａ、ｂ、ｃ、ｄの順に、サーバデータが格納されているものとする。また、新規キー範囲データのリストには、キー範囲の昇順である新規キー範囲a’、b’、c’、d’の順に、新規キー範囲データが格納されているものとする。
【００４６】
次に、ステップＳ３における木構造データ生成部１３の動作の詳細について、図面を参照して説明する。
【００４７】
まず、図５に示したサーバデータおよび新規キー範囲データから生成される木構造データの具体例を図６〜図７に示す。
【００４８】
図６（ａ）は、各サーバデータおよび各新規キー範囲データに重複するキー範囲に対応するデータ量を示している。図６（ａ）において、q(ki,kj)は、キー範囲[ki,kj)に対応するデータ量を表す。なお、木構造データ生成部１３は、例えば、キー範囲[ki,kj)を担当するサーバに問い合わせることによりq(ki,kj)を求めることができる。
【００４９】
図６（ｂ）は、サーバデータおよび新規キー範囲データをそれぞれノードとして表し、重複するキー範囲[ki,kj)に対応するq(ki,kj)が存在する各ノード間にエッジを生成したグラフを示している。このグラフには、サーバa、b、cおよびdと、新規キー範囲a’、b’、c’およびd’とがそれぞれノードとして含まれる。また、各エッジには、重複するq(ki,kj)に基づく重みが付与されている。以降、サーバa、b、cおよびdと、新規キー範囲a’、b’、c’およびd’とをそれぞれ表すノードを、単にノードa、b、c、d、a’、b’、c’およびd’とも記載する。また、ノードａおよびａ’間のエッジを、エッジ(a,a’)とも記載する。例えば、サーバaのキー範囲および新規キー範囲a’の重複する範囲は、[k1,k2)である。この重複する範囲に対応するデータ量は、q(k1,k2)=9である。重複データ量が0より大きいため、木構造データ生成部１３は、エッジ(a,a’)を生成し、このエッジに重み9を付与している。
【００５０】
図７（ａ）は、図６（ｂ）のグラフを、ノードａ’をルートノードとする木構造として表したものである。
【００５１】
図７（ｂ）は、図７（ａ）に示す木構造を保持するためのデータ構造（木構造データ）の一例を示している。図7において、ID、重みおよび子集合からなる各データは、図７（ａ）の木構造における各エッジを表すエッジデータである。エッジデータのIDは、エッジが接続する親子のうち、子ノードのIDである。また、重みは、エッジに付与された重みである。また、子集合は、該エッジデータの1つ下の階層のエッジデータ（すなわち、エッジデータのＩＤが示すノードを親とするエッジデータ）へのポインタの集合である。
【００５２】
なお、この具体例では、サーバデータのリストおよび新規キー範囲データのリストから１つに連結した木構造データが生成されるが、実際には、各サーバデータおよび各新規キー範囲データの各キー範囲の重複状態および重複範囲に対応するデータの有無に応じて、複数の木構造データが生成される場合もある。したがって、木構造データ生成部１３は、サーバデータのリストおよび新規キー範囲データのリストから、木構造データのリストを生成するものとして以下の説明を行う。
【００５３】
このような木構造データのリストを生成する木構造データ生成部１３の動作の詳細を、図８〜図１１に示すフローチャートを参照して説明する。
【００５４】
ここでは、まず、木構造データ生成部１３は、サーバデータリストの先頭要素をｓとおく（ステップＳ１０）。
【００５５】
次に、木構造データ生成部１３は、新規キー範囲データリストの先頭要素をｒとおく（ステップＳ１１）。ステップＳ１０およびステップＳ１１の処理は順不同である。
【００５６】
次に、木構造データ生成部１３は、サーバデータｓおよび新規キー範囲データｒのいずれかをルートノードとする木構造データを生成する（ステップＳ１２）。この動作の詳細については後述する。
【００５７】
次に、木構造データ生成部１３は、ステップＳ１１で生成した木構造データを、木構造データリストに追加する（ステップＳ１３）。
【００５８】
次に、木構造データ生成部１３は、ステップＳ１２の処理においてサーバデータリスト中の最後尾の要素までが木構造データに追加されたか否かを判断する（ステップＳ１４）。
【００５９】
ここで、最後尾のサーバデータまでが木構造データに追加されていれば、木構造データ生成部１３は、木構造データリストの生成処理を終了する。
【００６０】
一方、最後尾のサーバデータまでが木構造データに追加されていなければ、木構造データ生成部１３は、サーバデータリストのうち木構造データに最後に追加されたノードの次のノードを次のｓとおく（ステップＳ１５）。
【００６１】
次に、木構造データ生成部１３は、新規キー範囲データリストのうち木構造データに最後に追加されたノードの次のノードを次のｒとおく（ステップＳ１６）。ステップＳ１５およびステップＳ１６の処理は順不同である。
【００６２】
そして、木構造データ生成部１３は、ステップＳ１２からの処理を繰り返す。
【００６３】
次に、ステップＳ１２における木構造データ生成処理の詳細について、図９を参照して説明する。
【００６４】
ここでは、まず、木構造データ生成部１３は、サーバデータｓおよび新規キー範囲データｒのいずれかをルートノード（親ノード）とするエッジ生成初期処理を行う（ステップＳ２０）。このステップの詳細については後述する。
【００６５】
次に、木構造データ生成部１３は、サーバデータｓおよび新規キー範囲データｒのうち、親となっている一方のノードの子ノードとして、他方のノードを追加するエッジ生成処理を行う（ステップＳ２１）。このとき、木構造データ生成部１３は、エッジに重みを付与する。このステップの詳細については後述する。
【００６６】
次に、木構造データ生成部１３は、サーバデータｓおよび新規キー範囲データｒのうち、いずれの最大キーがより大きいかを判断する（ステップＳ２２）。
【００６７】
ここで、サーバデータｓの最大キーの方が他方より大きい場合、木構造データ生成部１３は、新規キー範囲データリストにおける新規キー範囲データｒの次の要素を次のｒとする（ステップＳ２３）。この場合、木構造データ生成部１３は、サーバデータｓについては、現在のサーバデータｓを次のエッジ生成処理でもそのまま用いる。
【００６８】
一方、新規キー範囲データｒの最大キーの方が他方より大きい場合、木構造データ生成部１３は、サーバデータリストにおけるサーバデータｓの次の要素を次のｓとする（ステップＳ２４）。この場合、木構造データ生成部１３は、新規キー範囲データｒについては、現在の新規キー範囲データｒを次のエッジ生成処理でもそのまま用いる。
【００６９】
そして、木構造データ生成部１３は、次のサーバデータｓおよび次の新規キー範囲データｒを用いて、ステップＳ２１からの処理を繰り返す。
【００７０】
また、ステップＳ２２において、新規キー範囲データｒの最大キーおよびサーバデータｓの最大キーが等しいと判断された場合、木構造データ生成部１３は、木構造データ生成処理を終了する。
【００７１】
次に、ステップＳ２０におけるエッジ生成初期処理について、図１０を参照して説明する。このエッジ生成初期処理では、サーバデータｓおよび新規キー範囲データｒのいずれをルートノードとしてもよいが、この例では、最大キーが小さい方をルートノードとしている。
【００７２】
図１０では、まず、木構造データ生成部１３は、サーバデータｓの最大キーおよび新規キー範囲データrの最大キーのいずれがより小さいかを判断する（ステップＳ３０）。
【００７３】
ここで、サーバデータｓの最大キーの方が他方より小さい場合、木構造データ生成部１３は、ｓをルートノード（親ノードｐ）とする。そして、木構造データ生成部１３は、サーバデータｓのＩＤ、重み０、子集合としての空集合を含む親エッジデータｐを生成する（ステップＳ３１）。
【００７４】
一方、新規キー範囲データrの最大キーの方が他方より小さい場合、木構造データ生成部１３は、ｒをルートノード（親ノードｐ）とする。そして、木構造データ生成部１３は、新規キー範囲データｒのＩＤ、重み０、子集合としての空集合を含む親エッジデータｐを生成する（ステップＳ３２）。
【００７５】
以上で、木構造データ生成部１３は、エッジ生成初期処理を終了する。
【００７６】
次に、ステップＳ２１におけるエッジ生成処理について、図１１を参照して説明する。
【００７７】
図１１では、まず、木構造データ生成部１３は、サーバデータｓおよび新規キー範囲データｒの各キー範囲の重複部分に対応するデータ量を求める。具体的には、木構造データ生成部１３は、サーバデータｓおよび新規キー範囲データｒの各最小キーのうち、より大きいキーをｍとする。なお、各最小キーが等しければ、木構造データ生成部１３は、その最小キーの値をｍとする。また、木構造データ生成部１３は、サーバデータｓおよび新規キー範囲データｒの各最大キーのうち、より小さいキーをｎとする。なお、各最大キーが等しければ、木構造データ生成部１３は、その最大キーの値をｎとする。そして、木構造データ生成部１３は、重複キー範囲[m,n)に含まれるデータ群の合計サイズｗを取得する（ステップＳ４０）。
【００７８】
次に、木構造データ生成部１３は、現在の親エッジデータｐのＩＤ（現在の親ノードｐ）が、サーバデータｓのＩＤであるか新規キー範囲データｒのＩＤであるかを判断する（ステップＳ４１）。
【００７９】
ここで、親エッジデータｐのＩＤがサーバデータｓのＩＤである場合（親ノードｐがサーバデータｓである場合）、木構造データ生成部１３は、新規キー範囲データrを親ノードpの子ノードｃとする。すなわち、木構造データ生成部１３は、新規キー範囲データｒのＩＤ、重みｗ、子集合としての空集合を含む子エッジデータｃを生成する（ステップＳ４２）。
【００８０】
一方、親エッジデータｐのＩＤが新規キー範囲データｒのＩＤである場合（親ノードｐが新規キー範囲データｒである場合）、木構造データ生成部１３は、サーバデータｓを親ノードpの子ノードｃとする。すなわち、木構造データ生成部１３は、サーバデータｓのＩＤ、重みｗ、子集合としての空集合を含む子エッジデータｃを生成する（ステップＳ４３）。
【００８１】
そして、木構造データ生成部１３は、ステップＳ４２またはステップＳ４３で生成した子エッジデータｃへのポインタを、親エッジデータｐの子集合に追加する（ステップＳ４４）。
【００８２】
次に、木構造データ生成部１３は、子ノードｃの最大キーが親ノードｐの最大キーよりも大きいか否かを判断する（ステップＳ４５）。
【００８３】
ここで、子ノードｃの最大キーが親ノードｐの最大キーよりも大きい場合、木構造データ生成部１３は、子ノードｃを次の親ノードpとおく。すなわち、木構造データ生成部１３は、子エッジデータｃを次の親エッジデータｐとおく（ステップＳ４６）。そして、木構造データ生成部１３は、エッジ生成処理を終了する。この後、木構造データ生成部１３は、図９の処理に戻り、ステップＳ２３またはステップＳ２４を実行する。
【００８４】
一方、子ノードｃの最大キーが親ノードｐの最大キーより大きくない場合、木構造データ生成部１３は、そのまま、エッジ生成処理を終了する。このとき、もし、子ノードｃの最大キーおよび親ノードｐの最大キーが等しければ、木構造データ生成部１３は、図９の処理に戻った後、ステップＳ２２における判断に基づいて、木構造データ生成処理を終了する。子ノードｃの最大キーが親ノードｐの最大キーより小さければ、木構造データ生成部１３は、図９の処理に戻った後、ステップＳ２３またはステップＳ２４を実行する。
【００８５】
以上で、木構造データ生成部１３の木構造データリスト生成処理および木構造データ生成処理の説明を終了する。
【００８６】
木構造データ生成部１３が以上のように動作することにより、図６（ａ）に示したサーバデータおよび新規キー範囲データから、図７（ｂ）に示す木構造データが生成される。
【００８７】
次に、このように生成された木構造データリストから、エッジの重みの合計が最大になる非隣接エッジ群を選択する組み合わせ算出部１４の動作の詳細を、図１２〜図１８に示すフローチャートを参照して説明する。
【００８８】
図１２では、まず、組み合わせ算出部１４は、木構造データリストに含まれる各木構造データについて、エッジの重みの合計が最大になるように、非隣接エッジ群を算出する組み合せ算出処理を実行する（ステップＳ５０）。
【００８９】
ここで、組み合わせ算出処理の詳細を図１３に示す。
【００９０】
図１３では、組み合わせ算出部１４は、木構造データに含まれる各エッジについて、重み合計データを算出する重み合計算出処理を再帰的に実行する（ステップＳ６１）。ここで、あるエッジに関する重み合計データとは、該エッジを最下層に含む部分木ｉにおける非隣接エッジ群の重み合計を表すデータである。深さｉの各エッジの重み合計データは、深さｉ−１の各エッジの重み合計データに基づいて再帰的に算出される。このステップの詳細については後述する。
【００９１】
次に、組み合わせ算出部１４は、各エッジについて生成した重み合計データに基づいて、非隣接エッジ群を選択する。そして、組み合わせ算出部１４は、選択したエッジ群に基づいて、サーバデータおよび新規キー範囲データのペアを決定する（ステップＳ６２）。このステップの詳細については後述する。
【００９２】
以上で、組み合わせ算出部１４は、組み合わせ算出処理を終了する。
【００９３】
次に、ステップＳ６１における重み合計算出処理について、図１４〜図１５を参照して説明する。この例では、組み合わせ算出部１４は、重み合計データを階層化した階層化データを生成する。重み合計データの階層化データの一例を図１４に示す。図１４は、図７に示した木構造データに基づいて生成された重み合計データの階層化データである。
【００９４】
図１４に示すように、あるエッジに関する１つの重み合計データ１０５（１０５ａ〜１０５ｎ）は、そのエッジのＩＤと、重み合計を表す値と、そのエッジの選択状態を表す情報と、親となる重み合計データへのポインタとからなる。
【００９５】
エッジのＩＤは、例えば、そのエッジの両端の深さｉ−１および深さｉのノードのＩＤの組み合わせによって表される。
【００９６】
また、重み合計を表す値は、そのエッジを最下層に含む部分木ｉにおける非隣接エッジ群の重み合計を表す値である。
【００９７】
また、エッジの選択状態を表す情報は、この重み合計データが、そのエッジが選択された場合のデータであるか選択されない場合のデータであるかを表す情報である。
【００９８】
また、親となる重み合計データへのポインタは、重み合計の算出に用いられた深さｉ−１のエッジに関する重み合計データへのポインタである。
【００９９】
各エッジについて、このような重み合計データは、エッジの選択状態が“選択”であるものと、“未選択”であるものとで２つずつ生成されることになる。ここで、エッジの選択状態が“選択”の重み合計データは、該エッジを最下層に含む部分木において該エッジを含む非隣接エッジ群の重み合計を表す。また、エッジの選択状態が“未選択”の重み合計データは、該エッジを最下層に含む部分木において該エッジを含まない非隣接エッジ群の重み合計を表す。
【０１００】
例えば、図１４において、木構造データのルートノードの深さを０とし、この木構造データの深さを６として説明する。図１４において、例えば、深さ５までの部分木５において最下層のエッジ（ｃ，ｄ’）に関する重み合計データは、重み合計データ１０５ｋおよび重み合計データ１０５ｌの２つである。また、重み合計データ１０５ｋは、エッジのＩＤとして（ｃ’，ｄ）を含んでいる。また、重み合計データ１０５ｋは、重み合計データとして４２を含んでいる。また、重み合計データ１０５ｋが含む重み合計データ１０５ｊへのポインタは、この重み合計データ４２の算出に用いられたのは、部分木４における最下層のエッジ（ｃ，ｃ’）に関する重み合計データ１０５ｊであることを表している。
【０１０１】
このような重み合計データの階層化データを生成する重み合計算出処理について、図１５を参照して説明する。ここでは、木構造データが、図７（ｂ）に示したようなエッジデータにより表されているものとする。
【０１０２】
図１５では、まず、組み合わせ算出部１４は、ルートのエッジデータをｐとする（ステップＳ７０）。
【０１０３】
次に、組み合わせ算出部１４は、重み合計データ集合Ｐを空集合に初期化する（ステップＳ７１）。
【０１０４】
次に、組み合わせ算出部１４は、重み合計データ集合Ｃを空集合に初期化する（ステップＳ７２）。
【０１０５】
次に、組み合わせ算出部１４は、親エッジデータｐの子集合に含まれる各子エッジデータｃについて、ステップＳ７３〜Ｓ７４の処理を実行する。
【０１０６】
ここでは、まず、組み合わせ算出部１４は、この子エッジデータｃが示すエッジを選択しない場合の重み合計データを、重み合計データ集合Ｐに基づいて生成する（ステップＳ７３）。そして、生成した重み合計データを、重み合計データ集合Ｃに追加する。このステップの詳細については後述する。
【０１０７】
次に、組み合わせ算出部１４は、このエッジデータｃが示すエッジを選択する場合の重み合計データを、重み合計データ集合Ｐに基づいて生成する（ステップＳ７４）。そして、生成した重み合計データを、重み合計データ集合Ｃに追加する。このステップの詳細については後述する。
【０１０８】
子集合の各エッジデータｃについてステップＳ７３〜Ｓ７４の処理を終了すると、組み合わせ算出部１４は、重み合計データ集合Ｃを、次の重み合計データ集合Ｐとする（ステップＳ７５）。
【０１０９】
次に、組み合わせ算出部１４は、親エッジデータｐの子集合に含まれる子エッジデータｃのうち、その子集合のサイズが１以上のものを次の親エッジデータｐとする（ステップＳ７６）。
【０１１０】
そのような次の親エッジデータｐが存在すれば（ステップＳ７７でＮｏ）、組み合わせ算出部１４は、ステップＳ７２からの処理を繰り返し実行する。
【０１１１】
一方、そのような次の親エッジデータｐが存在しなければ（ステップＳ７７でＹｅｓ）、組み合わせ算出部１４は、重み合計算出処理を終了する。
【０１１２】
次に、ステップＳ７３における対象エッジ未選択の場合の重み合計算出処理の詳細について、図１６を参照して説明する。
【０１１３】
図１６では、まず、組み合わせ算出部１４は、重み合計データ集合Ｐが空であるか否かを判断する（ステップＳ８１）。
【０１１４】
ここで、重み合計データ集合Ｐが空である場合、組み合わせ算出部１４は、エッジのＩＤとして（親エッジデータｐのＩＤ，子エッジデータｃのＩＤ）と、重み合計０と、選択状態として“未選択”と、ポインタとしてｎｕｌｌとを含む重み合計データを生成する（ステップＳ８２）。
【０１１５】
一方、重み合計データ集合Ｐが空でない場合、組み合わせ算出部１４は、重み合計データ集合Ｐに含まれる重み合計データのうち、最大の重みを有する重み合計データｗ１を選択する（ステップＳ８３）。
【０１１６】
次に、組み合わせ算出部１４は、エッジのＩＤとして（親エッジデータｐのＩＤ，子エッジデータｃのＩＤ）と、重み合計データｗ１が有する重みと、選択状態として“未選択”と、重み合計データｗ１へのポインタとを含む重み合計データを生成する（ステップＳ８４）。
【０１１７】
次に、組み合わせ算出部１４は、ステップＳ８２またはステップＳ８４で生成した重み合計データを、重み合計データ集合Ｃに追加する（ステップＳ８５）。
【０１１８】
以上で、組み合わせ算出部１４は、対象エッジ未選択の場合の重み合計算出処理を終了する。
【０１１９】
次に、ステップＳ７４における対象エッジを選択する場合の重み合計算出処理の詳細について、図１７を参照して説明する。
【０１２０】
図１７では、まず、組み合わせ算出部１４は、重み合計データ集合Ｐが空であるか否かを判断する（ステップＳ９１）。
【０１２１】
ここで、重み合計データ集合Ｐが空である場合、組み合わせ算出部１４は、エッジのＩＤとして（親エッジデータｐのＩＤ，子エッジデータｃのＩＤ）と、重み合計として子エッジデータｃの重みと、選択状態として“選択”と、ポインタとしてｎｕｌｌとを含む重み合計データを生成する（ステップＳ９２）。
【０１２２】
一方、重み合計データ集合Ｐが空でない場合、組み合わせ算出部１４は、重み合計データ集合Ｐに含まれる重み合計データのうち、エッジのＩＤに親エッジデータｐのＩＤを含みエッジの選択状態が“選択”のものを除いた中から、最大の重みを有する重み合計データｗ２を選択する（ステップＳ９３）。
【０１２３】
次に、組み合わせ算出部１４は、エッジのＩＤとして（親エッジデータｐのＩＤ，子エッジデータｃのＩＤ）と、重み合計データｗ２が有する重みに子エッジデータｃの重みを加算した重みと、選択状態として“選択”と、重み合計データｗ２へのポインタとを含む重み合計データを生成する（ステップＳ９４）。
【０１２４】
次に、組み合わせ算出部１４は、ステップＳ９２またはステップＳ９４で生成した重み合計データを、重み合計データ集合Ｃに追加する。
【０１２５】
以上で、組み合わせ算出部１４は、対象エッジを選択する場合の重み合計算出処理を終了する。
【０１２６】
このように、組み合わせ算出部１４は、部分木ｉにおいて深さｉの各エッジを含む非隣接エッジ群の重み合計として、部分木ｉ−１において深さｉ−１の各エッジに関して２つずつ算出した重み合計データのうち、深さｉの該エッジに隣接するエッジを含む非隣接エッジ群の重み合計データを除いた中で、重み合計の最大値に、深さｉの該エッジの重みを加算した値を適用する。また、組み合わせ算出部１４は、部分木ｉにおいて深さｉの各エッジを含まない非隣接エッジ群の重み合計として、部分木ｉ−１において深さｉ−１の各エッジに関して２つずつ算出した重み合計データのうち、重み合計の最大値を適用する。
【０１２７】
以上で、図１３のステップＳ６１における重み合計算出処理の説明を終了する。
【０１２８】
次に、ステップＳ６２における非隣接エッジ群選択処理について、図１８を参照して説明する。この例では、組み合わせ算出部１４は、図１５〜図１７に示した動作により生成した階層化データ（例えば、図１４に示した階層化データ）を用いるものとする。
【０１２９】
まず、組み合わせ算出部１４は、ステップＳ６１で生成した階層化データの最下層の重み合計データのうち、その重みが最大である重み合計データｗを選択する（ステップＳ１０１）。
【０１３０】
次に、組み合わせ算出部１４は、重み合計データｗの選択状態が“選択”であるか“未選択”であるかを判断する（ステップＳ１０２）。
【０１３１】
ここで、選択状態が“未選択”であれば、組み合わせ算出部１４の処理はステップＳ１０４に進む。
【０１３２】
一方、選択状態が“選択”であれば、組み合わせ算出部１４は、重み合計データｗのＩＤが示すエッジの両端に相当するサーバデータおよび新規キー範囲データを、ペアリストに追加する（ステップＳ１０３）。
【０１３３】
次に、組み合わせ算出部１４は、重み合計データｗのポインタがｎｕｌｌであるか否かを判断する（ステップＳ１０４）。
【０１３４】
ここで、重み合計データｗのポインタがｎｕｌｌでなければ、ポインタが指す重み合計データを、次の重み合計データｗとする（ステップＳ１０５）。
【０１３５】
そして、組み合わせ算出部１４は、ステップＳ１０２からの処理を繰り返す。
【０１３６】
一方、重み合計データｗのポインタがｎｕｌｌであれば、組み合わせ算出部１４は、ペアリストに含まれていないサーバデータおよび新規キー範囲の任意の組合せを決定し、ペアリストに追加する（ステップＳ１０６）。そして、組み合わせ算出部１４は、エッジ選択処理を終了する。
【０１３７】
このように、組み合わせ算出部１４は、重み合計データのポインタが指す親を再帰的に辿ることにより参照される重み合計データのうち、選択状態が“選択”である重み合計データのエッジを選択する。
【０１３８】
例えば、図７に示す階層化データに対して、非隣接エッジ群選択処理を実行する場合について説明する。組み合わせ算出部１４は、まず、最下層の重み合計データのうち、重みが最大の７１である重み合計データ１０５ｎを選択する（ステップＳ１０１）。
【０１３９】
次に、組み合わせ算出部１４は、重み合計データ１０５ｎの選択状態が“選択”であるため（ステップＳ１０２でＹｅｓ）、エッジ(d,d’)の両端ノードに相当するサーバｄおよび新規キー範囲ｄ’をペアリストに追加する（ステップＳ１０３）。
【０１４０】
次に、組み合わせ算出部１４は、重み合計データ１０５ｎのポインタが指す重み合計データ１０５ｋについて、選択状態が“未選択”であるので（ステップＳ１０２でＮｏ）、ペアリストへの追加を行わない。つまり、エッジ(c’,d)は選択されない。
【０１４１】
次に、組み合わせ算出部１４は、重み合計データ１０５ｋのポインタが指す重み合計データ１０５ｊについて、選択状態が“選択”であるため（ステップＳ１０２でＹｅｓ）、エッジ(c,c’)の両端ノードに相当するサーバｃおよび新規キー範囲ｃ’をペアリストに追加する（ステップＳ１０３）。
【０１４２】
このような処理を繰り返すことにより、組み合わせ算出部１４は、最終的に、エッジ(d,d’),(c,c’),(a,b’)を選択する。すなわち、組み合わせ算出部１４は、サーバｄおよび新規キー範囲ｄ’、サーバｃおよび新規キー範囲ｃ’、ならびに、サーバａおよび新規キー範囲ｂ’を、ペアリストに追加する。そして、組み合わせ算出部１４は、選択されなかったサーバbおよび新規キー範囲a’を、さらにペアリストに追加する（ステップＳ１０６）。
【０１４３】
以上で、ステップＳ６２における非隣接エッジ群選択処理の説明を終了する。
【０１４４】
次に、本実施の形態の効果について述べる。
【０１４５】
本実施の形態としてのデータ再配置装置は、データ再配置先の決定処理にかかる計算時間を削減することができる。
【０１４６】
その理由は、木構造データ生成部が、キー範囲が重複する組合せであって、かつ、重複する範囲に対応するデータが存在するサーバデータおよび新規キー範囲データ間に、親子関係を示すエッジを生成するとともに、そのエッジに重複データ量に基づく重みを付与するからである。そして、組み合わせ算出部が、このような木構造データから、その重み合計が最大となるよう、ノードを共有しないエッジの組合せを選択するからである。このように、木構造データを用いて非隣接エッジ群を選択することにより、本実施の形態としてのデータ再配置装置は、サーバに新規キー範囲を割り当てる処理を、非特許文献１に記載の手順で割り当て問題を解く処理よりも遥かに少ない計算時間で行うことが可能となる。
【０１４７】
例えば、上述のように、木構造データの部分木を用いた再帰的処理により非隣接エッジ群を選択する処理は、部分木の各ノード（各エッジ）に対する処理となるため、その計算時間はＯ（ｎ）となる。したがって、この場合、本実施の形態としてのデータ再配置装置は、非特許文献１に記載の手順を採用した場合の計算時間Ｏ（ｎ＾３）に比べて、サーバ数ｎに対するスケーラビリティをより向上させることができる。
【０１４８】
なお、本実施の形態において、木構造データ生成部は、サーバデータおよび新規キー範囲データをそれぞれ昇順に並べたサーバデータリストおよび新規キー範囲データリストを用いて、木構造データを生成する例について説明した。本発明における木構造データ生成部は、その他の手順により本発明における木構造データを生成してもよい。例えば、木構造データ生成部は、図６（ｂ）に示したグラフを構成するいずれのノードをルートノードとした木構造データを生成してもよい。
【０１４９】
また、本実施の形態において、木構造データ生成部は、図７（ｂ）に示したようなエッジデータの階層データとして木構造データを保持する例について説明した。本発明における木構造データ生成部は、木構造データを表現可能なその他のデータ構造を用いて本発明の木構造データを保持してもよい。
【０１５０】
また、本実施の形態において、組み合わせ算出部は、木構造データの部分木を用いた再帰的処理を用いて非隣接エッジ群を選択する例について説明した。本発明における組み合わせ算出部は、その他の手順を用いて本発明における木構造データから非隣接エッジ群を選択してもよい。
【０１５１】
また、本実施の形態において、各フローチャートを参照して説明したデータ再配置装置の動作を、本発明のコンピュータ・プログラムとしてコンピュータ装置の記憶装置（記憶媒体）に格納しておき、係るコンピュータ・プログラムを当該ＣＰＵが読み出して実行するようにしてもよい。そして、このような場合において、本発明は、係るコンピュータ・プログラムのコード或いは記憶媒体によって構成される。
【０１５２】
また、本発明は、上述した実施の形態に限定されず、様々な態様で実施されることが可能である。
【符号の説明】
【０１５３】
１    データ再配置装置
１１    サーバデータ保持部
１２    新規キー範囲データ保持部
１３    木構造データ生成部
１４    組み合わせ算出部
１００１    ＣＰＵ
１００２    ＲＡＭ
１００３    ＲＯＭ
１００４    記憶装置
【図１】
2013117763.tif 000003
【図２】
2013117763.tif 000004
【図３】
2013117763.tif 000005
【図４】
2013117763.tif 000006
【図５】
2013117763.tif 000007
【図６】
2013117763.tif 000008
【図７】
2013117763.tif 000009
【図８】
2013117763.tif 000010
【図９】
2013117763.tif 000011
【図１０】
2013117763.tif 000012
【図１１】
2013117763.tif 000013
【図１２】
2013117763.tif 000014
【図１３】
2013117763.tif 000015
【図１４】
2013117763.tif 000016
【図１５】
2013117763.tif 000017
【図１６】
2013117763.tif 000018
【図１７】
2013117763.tif 000019
【図１８】
2013117763.tif 000020
【図１９】
2013117763.tif 000021