"キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを保持するサーバデータ保持部と、前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを保持する新規キー範囲データ保持部と、前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与する木構造データ生成部と、前記木構造データにおいてノードを共有しないエッジの組合せ非隣接エッジ群のうち、該エッジ群を構成するエッジに付与された重みの合計値重み合計が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する組み合わせ算出部と、を備えたデータ再配置装置。前記木構造データ生成部は、前記サーバデータをそのキー範囲を連続させる順序で並べたリスト、および、前記新規キー範囲データをそのキー範囲を連続させる順序で並べたリストを用いて、各リストにおける先頭のサーバデータおよび先頭の新規キー範囲データのうちいずれか一方をルートノードとして他方をその子ノードとし、親子となった2つのサーバデータおよび新規キー範囲データ間で重複するデータ量に基づく重みを親子間のエッジに付与し、以降、親子となった2つのノードのうちキー範囲の最大値が大きい方を新たに親ノードとして、小さい方のノードが属するリストにおける次のノードをその子ノードとしていく処理を繰り返すことにより、前記木構造データを生成することを特徴とする請求項1に記載のデータ再配置装置。前記組み合わせ算出部は、前記木構造データの深さiiは1以上、前記木構造データの深さ以下の整数までの部分木において、深さi-1のノードおよび深さiのノードを端点とする各エッジ深さiのエッジについて、深さiの該エッジを含む前記非隣接エッジ群および深さiの該エッジを含まない前記非隣接エッジ群の各重み合計を再帰的処理によりそれぞれ算出することにより、前記木構造データの最下層の各エッジについて2つずつ算出された重み合計のうち最大値を有する非隣接エッジ群を選択することを特徴とする請求項1または請求項2に記載のデータ再配置装置。前記組み合わせ算出部は、深さ1までの部分木において深さ1の各エッジについて、深さ1の該エッジを含まない前記非隣接エッジ群の前記重み合計として0を適用し、深さ1の該エッジを含む前記非隣接エッジ群の前記重み合計として該エッジの重みを適用し、深さiiは2以上、前記木構造データの深さ以下の整数までの部分木において深さiの各エッジについて、深さiの該エッジを含まない前記非隣接エッジ群の前記重み合計として、深さi-1までの部分木において深さi-1の各エッジについて2つずつ算出された重み合計のうちの最大値を適用し、深さiの該エッジを含む前記非隣接エッジ群の前記重み合計として、深さi-1までの部分木において深さi-1の各エッジについて2つずつ算出された重み合計のうち、深さiの該エッジに隣接する深さi-1のエッジを含む前記非隣接エッジ群の前記重み合計を除いた最大値に、深さiの該エッジの重みを加算した値を適用することを特徴とする請求項3に記載のデータ再配置装置。キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを取得し、前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを取得し、前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与し、前記木構造データにおいてノードを共有しないエッジの組合せ非隣接エッジ群のうち、該エッジ群を構成するエッジに付与された重みの合計値重み合計が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する、データ再配置方法。前記サーバデータをそのキー範囲を連続させる順序で並べたリスト、および、前記新規キー範囲データをそのキー範囲を連続させる順序で並べたリストを用いて、各リストにおける先頭のサーバデータおよび先頭の新規キー範囲データのうちいずれか一方をルートノードとして他方をその子ノードとし、親子となった2つのサーバデータおよび新規キー範囲データ間で重複するデータ量に基づく重みを親子間のエッジに付与し、以降、親子となった2つのノードのうちキー範囲の最大値が大きい方を新たに親ノードとして、小さい方のノードが属するリストにおける次のノードをその子ノードとしていく処理を繰り返すことにより、前記木構造データを生成することを特徴とする請求項5に記載のデータ再配置方法。前記木構造データの深さiiは1以上、前記木構造データの深さ以下の整数までの部分木において、深さi-1のノードおよび深さiのノードを端点とする各エッジ深さiのエッジについて、深さiの該エッジを含む前記非隣接エッジ群および深さiの該エッジを含まない前記非隣接エッジ群の各重み合計を再帰的処理によりそれぞれ算出することにより、前記木構造データの最下層の各エッジについて2つずつ算出された重み合計のうち最大値を有する非隣接エッジ群を選択することを特徴とする請求項5または請求項6に記載のデータ再配置方法。キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを取得するサーバデータ取得ステップと、前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを取得する新規キー範囲データ取得ステップと、前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与する木構造データ生成ステップと、前記木構造データにおいてノードを共有しないエッジの組合せ非隣接エッジ群のうち、該エッジ群を構成するエッジに付与された重みの合計値重み合計が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する組み合わせ算出ステップと、をコンピュータ装置に実行させるコンピュータプログラム。前記木構造データ生成ステップにおいて、前記サーバデータをそのキー範囲を連続させる順序で並べたリスト、および、前記新規キー範囲データをそのキー範囲を連続させる順序で並べたリストを用いて、各リストにおける先頭のサーバデータおよび先頭の新規キー範囲データのうちいずれか一方をルートノードとして他方をその子ノードとし、親子となった2つのサーバデータおよび新規キー範囲データ間で重複するデータ量に基づく重みを親子間のエッジに付与し、以降、親子となった2つのノードのうちキー範囲の最大値が大きい方を新たに親ノードとして、小さい方のノードが属するリストにおける次のノードをその子ノードとしていく処理を繰り返すことにより、前記木構造データを生成することを特徴とする請求項8に記載のコンピュータプログラム。前記組み合わせ算出ステップにおいて、前記木構造データの深さiiは1以上、前記木構造データの深さ以下の整数までの部分木において、深さi-1のノードおよび深さiのノードを端点とする各エッジ深さiのエッジについて、深さiの該エッジを含む前記非隣接エッジ群および深さiの該エッジを含まない前記非隣接エッジ群の各重み合計を再帰的処理によりそれぞれ算出することにより、前記木構造データの最下層の各エッジについて2つずつ算出された重み合計のうち最大値を有する非隣接エッジ群を選択することを特徴とする請求項8または請求項9に記載のコンピュータプログラム。上述のようなデータ再配置先の決定処理は、サーバ数nに対してスケーラブルに行うことが求められる。ところが、膨大なデータを処理する分散処理システムでは、サーバ数nが非常に大きくなる。上述の非特許文献1をデータ再配置先の決定処理に適用した場合、その計算時間は、Oとなりnに対して幾何級数的に増加してしまう。本発明は、上述の課題を解決するためになされたもので、データ再配置先の決定処理にかかる計算時間を削減することができるデータ再配置装置を提供することを目的とする。本発明のデータ再配置装置は、キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを保持するサーバデータ保持部と、前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを保持する新規キー範囲データ保持部と、前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与する木構造データ生成部と、前記木構造データにおいてノードを共有しないエッジの組合せ非隣接エッジ群のうち、該エッジ群を構成するエッジに付与された重みの合計値重み合計が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する組み合わせ算出部と、を備える。本発明のデータ再配置方法は、キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを取得し、前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを取得し、前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与し、前記木構造データにおいてノードを共有しないエッジの組合せ非隣接エッジ群のうち、該エッジ群を構成するエッジに付与された重みの合計値重み合計が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する。本発明のコンピュータプログラムは、キー空間に含まれるキーに対応付けられたデータを処理する分散処理システムを構成する各サーバについて、該サーバの識別情報と、前記キー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを取得するサーバデータ取得ステップと、前記キー空間が新たな区分に分割された各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報とを含む新規キー範囲データを取得する新規キー範囲データ取得ステップと、前記各サーバデータおよび前記各新規キー範囲データのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する前記サーバデータおよび前記新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成することにより木構造データを生成するとともに、各エッジに対して、重複するデータ量に基づく重みを付与する木構造データ生成ステップと、前記木構造データにおいてノードを共有しないエッジの組合せ非隣接エッジ群のうち、該エッジ群を構成するエッジに付与された重みの合計値重み合計が最大になるものを選択することにより、前記各サーバが担当する前記新規キー範囲を決定する組み合わせ算出ステップと、をコンピュータ装置に実行させる。本発明は、データ再配置先の決定処理にかかる計算時間を削減することができるデータ再配置装置を提供することができる。以下、本発明の実施の形態について、図面を参照して詳細に説明する。なお、本実施の形態としてのデータ再配置装置が対象とする分散処理システムは、キー空間キーがとりうる範囲に含まれるキーに対応付けられたデータを処理するものである。また、この分散処理システムは、キー空間がn個の区分に分割されたキー範囲をそれぞれ担当するn個のサーバによって構成されているものとする。また、本実施の形態としてのデータ再配置装置は、n個の各サーバから、担当するキー範囲、キー範囲に対するデータ分布、および、キー範囲に対する負荷分布をそれぞれ表す情報を取得しているものとする。また、本実施の形態としてのデータ再配置装置は、n個の各サーバから取得した負荷分布を表す情報に基づいて、負荷が均一になるようにキー空間を新たなn個のキー範囲新規キー範囲に分割しているものとする。まず、本発明の実施の形態としてのデータ再配置装置1のハードウェア構成を図1に示す。図1において、データ再配置装置1は、CPUCentralProcessingUnit1001と、RAMRandomAccessMemory1002と、ROMReadOnlyMemory1003と、ハードディスク等の記憶装置1004とを備えたコンピュータ装置によって構成されている。ROM1003および記憶装置1004には、コンピュータ装置を本実施の形態のデータ再配置装置1として機能させるためのコンピュータプログラムおよび各種データが記憶されている。CPU1001は、ROM1003および記憶装置1004に記憶されたコンピュータプログラムおよび各種データをRAM1002に読み込んで実行する。次に、データ再配置装置1の機能ブロック構成を図2に示す。図2において、データ再配置装置1は、サーバデータ保持部11と、新規キー範囲データ保持部12と、木構造データ生成部13と、組み合わせ算出部14とを備えている。ここで、サーバデータ保持部11および新規キー範囲データ保持部12は、記憶装置1004によって構成されている。また、木構造データ生成部13および組み合わせ算出部14は、ROM1003および記憶装置1004に記憶されたコンピュータプログラムおよび各種データをRAM1002に読み込んで実行するCPU1001によって構成される。なお、データ再配置装置1の各機能ブロックのハードウェア構成は上述の構成に限定されない。サーバデータ保持部11は、各サーバの識別情報IDと、前述のキー空間が分割されたキー範囲のうち該サーバが担当するキー範囲を表す情報とを含むサーバデータを保持している。サーバデータの一例を図3に示す。図3に示すサーバデータは、IDと、担当するキー範囲の最小値最小キーと、最大値最大キーとからなる。また、サーバデータ保持部11は、サーバデータを、そのキー範囲を連続させる順序で並べたリストとして保持していてもよい。例えば、サーバデータ保持部11は、キー範囲の昇順にサーバデータを並べたリストを保持していてもよい。新規キー範囲データ保持部12は、前述の各新規キー範囲について、その範囲を表す情報と、該新規キー範囲の識別情報IDとを含む新規キー範囲データを保持している。新規キー範囲データのデータ構造は、図3に示したサーバデータと同様であってもよい。また、新規キー範囲データ保持部12は、新規キー範囲データを、そのキー範囲を連続させる順序で並べたリストとして保持していてもよい。例えば、新規キー範囲データ保持部12は、キー範囲の昇順に新規キー範囲データを並べたリストを保持していてもよい。木構造データ生成部13は、各サーバデータを表すノード、および、各新規キー範囲データを表すノード間にエッジノード間を結ぶ辺を生成することにより木構造データを生成する。具体的には、木構造データ生成部13は、各サーバデータおよび各新規キー範囲データの組合せのうち、キー範囲に重複部分があり、かつ、その重複部分に含まれるキーに対応付けられたデータが存在する組合せを抽出する。そして、木構造データ生成部13は、抽出した組合せのサーバデータを表すノードおよび新規キー範囲データを表すノード間に、親子関係を示すエッジを生成する。また、木構造データ生成部13は、生成した各エッジに対して、重複するデータ量に基づく重みを付与する。このようにして、木構造データ生成部13は、重みを付与したエッジにより連結したノードのいずれかをルートノードとみなした木構造データを生成する。このような木構造データを生成する手法の一例について説明する。例えば、木構造データ生成部13は、サーバデータのリストサーバデータを、そのキー範囲を連続させる順序で並べたリスト、および、新規キー範囲データのリスト新規キー範囲データを、そのキー範囲を連続させる順序で並べたリストを用いて、木構造データを生成することが可能である。具体的には、木構造データ生成部13は、上記の各リストにおける先頭のサーバデータおよび先頭の新規キー範囲データのうちいずれか一方をルートノードとし、他方をその子ノードとする。そして、木構造データ生成部13は、親子となった2つのノードに対応するサーバデータおよび新規キー範囲データ間で重複するデータ量に基づく重みを、親子間のエッジに付与する。以降、木構造データ生成部13は、親子となった2つのノードのうちキー範囲の最大値が大きい方を新たに親ノードとして、小さい方のノードが属するリストにおける次のノードをその子ノードとして前述の親子間のエッジに重みを付与する処理を繰り返す。このようにして、木構造データ生成部13は、キー範囲が最も小さいサーバデータまたは新規キー範囲データをルートノードとし、重複データが存在するサーバデータおよび新規キー範囲データ間に親子関係を表すエッジを生成していくことにより、木構造データを生成する。組み合わせ算出部14は、木構造データ生成部13によって生成された木構造データにおいてノードを共有しないエッジの組合せ非隣接エッジ群のうち、該エッジ群を構成するエッジに付与された重みの合計値重み合計が最大になるものを選択する。このような非隣接エッジ群を選択する手法の一例について説明する。例えば、組み合わせ算出部14は、このような非隣接エッジ群を選択するために、木構造データの部分木を用いた再帰的処理を行ってもよい。具体例としては、組み合わせ算出部14は、木構造データの深さ階層数をiiは1以上、木構造データの深さ以下の整数としたときの再帰的処理を、各深さiについて実行してもよい。この場合、再帰的処理は、木構造データの深さiまでの部分木以降、部分木iとも記載するにおける非隣接エッジ群の重み合計を、部分木i-1における非隣接エッジ群の重み合計に基づいて算出する処理である。この場合、組み合わせ算出部14は、深さi-1のノードおよび深さiのノードを端点とする各エッジ深さiのエッジについて、深さiの該エッジを含む非隣接エッジ群および深さiの該エッジを含まない非隣接エッジ群の各重み合計を再帰的処理によりそれぞれ算出してもよい。これにより、組み合わせ算出部14は、木構造データに含まれる各エッジについて2つずつ重み合計を算出することになる。そして、組み合わせ算出部14は、最下層の各エッジについて2つずつ算出された重み合計のうち最大値を有する非隣接エッジ群を選択する。具体的には、組み合わせ算出部14は、まず、部分木1において深さ1の各エッジについて、深さ1の該エッジを含まない非隣接エッジ群の重み合計として0を適用する。また、組み合わせ算出部14は、部分木1において深さ1の該エッジを含む非隣接エッジ群の重み合計として該エッジの重みを適用する。以降、組み合わせ算出部14は、i=2以降の部分木iにおいて深さiの各エッジについて、深さiの該エッジを含まない非隣接エッジ群の重み合計として、部分木i-1において深さi-1の各エッジについて2つずつ算出された重み合計のうちの最大値を適用する。また、組み合わせ算出部14は、部分木iにおいて深さiの該エッジを含む非隣接エッジ群の重み合計として、部分木i-1において深さi-1の各エッジについて2つずつ算出された重み合計のうち、深さiの該エッジに隣接する深さi-1のエッジを含む非隣接エッジ群の重み合計を除いた最大値に、深さiの該エッジの重みを加算した値を適用する。以上のように構成されたデータ再配置装置1の動作について、図面を参照して説明する。まず、図4を用いて、データ再配置装置1の動作の概略について説明する。ここでは、まず、木構造データ生成部13は、サーバデータ保持部11からサーバデータのリストを取得するステップS1。次に、木構造データ生成部13は、新規キー範囲データ保持部12から新規キー範囲データのリストを取得するステップS2。ステップS1およびステップS2の処理は順不同である。次に、木構造データ生成部13は、取得した各サーバデータおよび各新規キー範囲データのうち、キー範囲が重複する組合せであって、かつ、重複する範囲に対応するデータが存在する組合せを抽出する。そして、木構造データ生成部13は、抽出した組合せのサーバデータおよび新規キー範囲データをそれぞれ表すノード間に、親子関係を示すエッジを生成する。そして、木構造データ生成部13は、そのようなエッジに対して、重複データ量に基づく重みを付与するステップS3。次に、組み合わせ算出部14は、生成した木構造データにおける非隣接エッジ群のうち、該エッジ群を構成するエッジに付与された重みの合計が最大となる非隣接エッジ群を選択するステップS4。例えば、前述のように、組み合わせ算出部14は、木構造データの部分木を用いた再帰的処理により非隣接エッジ群を選択してもよい。このようにして、データ再配置装置1は、組み合わせ算出部14によって選択されたエッジ群に基づいて、各エッジの一方の端点が表すサーバに対して、他方の端点が表す新規キー範囲を割り当てる。このとき、ノードを共有しないエッジ群が選択されているので、選択されたエッジ群のうちの複数のエッジの端点が、同一のサーバデータを表すことはない。したがって、データ再配置装置1は、非隣接エッジ群に基づいて、各サーバが担当する新規キー範囲を一意に決定可能となる。これにより、データ再配置装置1は、各サーバの新規キー範囲に基づいて、各サーバに配置されていたデータの再配置先を決定する。以上で、データ再配置装置1は、動作を終了する。次に、サーバデータおよび新規キー範囲データの具体例を用いながら、データ再配置装置1の動作の詳細について説明する。ここでは、まず、上述のステップS1およびS2で、図5に示すようなサーバデータおよび新規キー範囲データが取得されたものとする。図5は、各サーバデータおよび各新規キー範囲データのIDおよびキー範囲を模式的に表した図である。図5において、a、b、cおよびdは、サーバのIDを表す。また、a’、b’、c’およびd’は、新規キー範囲のIDを表す。以降、IDがxxは、a、b、cまたはdのサーバを、サーバxとも記載する。また、IDがx’x’は、a’、b’、c’またはd’の新規キー範囲を、新規キー範囲x’とも記載する。図5において、キー空間は、k1以上k8未満の値である。k1~k8は、それぞれキーの値を表し、k1k2k3k4k5k6k7k8である。この例の場合、サーバa、b、cおよびdは、それぞれ、キー範囲k1k3、k3k4、k4k6およびk6k8を担当している。なお、kikjkikjは、k1k8のいずれかは、ki以上kj未満のキー範囲を表す。例えば、各サーバデータが図3に示したデータ構造であれば、サーバaのサーバデータには、IDとしてa、最小キーとしてk1、最大キーとしてk3が含まれる。また、新規キー範囲a’、b’、c’およびd’は、それぞれk1k2、k2k5、k5k7およびk7k8の範囲である。例えば、各新規キー範囲データが図3に示したデータ構造であれば、新規キー範囲a’の新規キー範囲データには、IDとしてa’、最小キーとしてk1、最大キーとしてk2が含まれる。また、ここでは、サーバデータのリストには、キー範囲の昇順であるサーバa、b、c、dの順に、サーバデータが格納されているものとする。また、新規キー範囲データのリストには、キー範囲の昇順である新規キー範囲a’、b’、c’、d’の順に、新規キー範囲データが格納されているものとする。次に、ステップS3における木構造データ生成部13の動作の詳細について、図面を参照して説明する。まず、図5に示したサーバデータおよび新規キー範囲データから生成される木構造データの具体例を図6~図7に示す。図6aは、各サーバデータおよび各新規キー範囲データに重複するキー範囲に対応するデータ量を示している。図6aにおいて、qは、キー範囲kikjに対応するデータ量を表す。なお、木構造データ生成部13は、例えば、キー範囲kikjを担当するサーバに問い合わせることによりqを求めることができる。図6bは、サーバデータおよび新規キー範囲データをそれぞれノードとして表し、重複するキー範囲kikjに対応するqが存在する各ノード間にエッジを生成したグラフを示している。このグラフには、サーバa、b、cおよびdと、新規キー範囲a’、b’、c’およびd’とがそれぞれノードとして含まれる。また、各エッジには、重複するqに基づく重みが付与されている。以降、サーバa、b、cおよびdと、新規キー範囲a’、b’、c’およびd’とをそれぞれ表すノードを、単にノードa、b、c、d、a’、b’、c’およびd’とも記載する。また、ノードaおよびa’間のエッジを、エッジとも記載する。例えば、サーバaのキー範囲および新規キー範囲a’の重複する範囲は、k1k2である。この重複する範囲に対応するデータ量は、q9である。重複データ量が0より大きいため、木構造データ生成部13は、エッジを生成し、このエッジに重み9を付与している。図7aは、図6bのグラフを、ノードa’をルートノードとする木構造として表したものである。図7bは、図7aに示す木構造を保持するためのデータ構造木構造データの一例を示している。図7において、ID、重みおよび子集合からなる各データは、図7aの木構造における各エッジを表すエッジデータである。エッジデータのIDは、エッジが接続する親子のうち、子ノードのIDである。また、重みは、エッジに付与された重みである。また、子集合は、該エッジデータの1つ下の階層のエッジデータすなわち、エッジデータのIDが示すノードを親とするエッジデータへのポインタの集合である。なお、この具体例では、サーバデータのリストおよび新規キー範囲データのリストから1つに連結した木構造データが生成されるが、実際には、各サーバデータおよび各新規キー範囲データの各キー範囲の重複状態および重複範囲に対応するデータの有無に応じて、複数の木構造データが生成される場合もある。したがって、木構造データ生成部13は、サーバデータのリストおよび新規キー範囲データのリストから、木構造データのリストを生成するものとして以下の説明を行う。このような木構造データのリストを生成する木構造データ生成部13の動作の詳細を、図8~図11に示すフローチャートを参照して説明する。ここでは、まず、木構造データ生成部13は、サーバデータリストの先頭要素をsとおくステップS10。次に、木構造データ生成部13は、新規キー範囲データリストの先頭要素をrとおくステップS11。ステップS10およびステップS11の処理は順不同である。次に、木構造データ生成部13は、サーバデータsおよび新規キー範囲データrのいずれかをルートノードとする木構造データを生成するステップS12。この動作の詳細については後述する。次に、木構造データ生成部13は、ステップS11で生成した木構造データを、木構造データリストに追加するステップS13。次に、木構造データ生成部13は、ステップS12の処理においてサーバデータリスト中の最後尾の要素までが木構造データに追加されたか否かを判断するステップS14。ここで、最後尾のサーバデータまでが木構造データに追加されていれば、木構造データ生成部13は、木構造データリストの生成処理を終了する。一方、最後尾のサーバデータまでが木構造データに追加されていなければ、木構造データ生成部13は、サーバデータリストのうち木構造データに最後に追加されたノードの次のノードを次のsとおくステップS15。次に、木構造データ生成部13は、新規キー範囲データリストのうち木構造データに最後に追加されたノードの次のノードを次のrとおくステップS16。ステップS15およびステップS16の処理は順不同である。そして、木構造データ生成部13は、ステップS12からの処理を繰り返す。次に、ステップS12における木構造データ生成処理の詳細について、図9を参照して説明する。ここでは、まず、木構造データ生成部13は、サーバデータsおよび新規キー範囲データrのいずれかをルートノード親ノードとするエッジ生成初期処理を行うステップS20。このステップの詳細については後述する。次に、木構造データ生成部13は、サーバデータsおよび新規キー範囲データrのうち、親となっている一方のノードの子ノードとして、他方のノードを追加するエッジ生成処理を行うステップS21。このとき、木構造データ生成部13は、エッジに重みを付与する。このステップの詳細については後述する。次に、木構造データ生成部13は、サーバデータsおよび新規キー範囲データrのうち、いずれの最大キーがより大きいかを判断するステップS22。ここで、サーバデータsの最大キーの方が他方より大きい場合、木構造データ生成部13は、新規キー範囲データリストにおける新規キー範囲データrの次の要素を次のrとするステップS23。この場合、木構造データ生成部13は、サーバデータsについては、現在のサーバデータsを次のエッジ生成処理でもそのまま用いる。一方、新規キー範囲データrの最大キーの方が他方より大きい場合、木構造データ生成部13は、サーバデータリストにおけるサーバデータsの次の要素を次のsとするステップS24。この場合、木構造データ生成部13は、新規キー範囲データrについては、現在の新規キー範囲データrを次のエッジ生成処理でもそのまま用いる。そして、木構造データ生成部13は、次のサーバデータsおよび次の新規キー範囲データrを用いて、ステップS21からの処理を繰り返す。また、ステップS22において、新規キー範囲データrの最大キーおよびサーバデータsの最大キーが等しいと判断された場合、木構造データ生成部13は、木構造データ生成処理を終了する。次に、ステップS20におけるエッジ生成初期処理について、図10を参照して説明する。このエッジ生成初期処理では、サーバデータsおよび新規キー範囲データrのいずれをルートノードとしてもよいが、この例では、最大キーが小さい方をルートノードとしている。図10では、まず、木構造データ生成部13は、サーバデータsの最大キーおよび新規キー範囲データrの最大キーのいずれがより小さいかを判断するステップS30。ここで、サーバデータsの最大キーの方が他方より小さい場合、木構造データ生成部13は、sをルートノード親ノードpとする。そして、木構造データ生成部13は、サーバデータsのID、重み0、子集合としての空集合を含む親エッジデータpを生成するステップS31。一方、新規キー範囲データrの最大キーの方が他方より小さい場合、木構造データ生成部13は、rをルートノード親ノードpとする。そして、木構造データ生成部13は、新規キー範囲データrのID、重み0、子集合としての空集合を含む親エッジデータpを生成するステップS32。以上で、木構造データ生成部13は、エッジ生成初期処理を終了する。次に、ステップS21におけるエッジ生成処理について、図11を参照して説明する。図11では、まず、木構造データ生成部13は、サーバデータsおよび新規キー範囲データrの各キー範囲の重複部分に対応するデータ量を求める。具体的には、木構造データ生成部13は、サーバデータsおよび新規キー範囲データrの各最小キーのうち、より大きいキーをmとする。なお、各最小キーが等しければ、木構造データ生成部13は、その最小キーの値をmとする。また、木構造データ生成部13は、サーバデータsおよび新規キー範囲データrの各最大キーのうち、より小さいキーをnとする。なお、各最大キーが等しければ、木構造データ生成部13は、その最大キーの値をnとする。そして、木構造データ生成部13は、重複キー範囲mnに含まれるデータ群の合計サイズwを取得するステップS40。次に、木構造データ生成部13は、現在の親エッジデータpのID現在の親ノードpが、サーバデータsのIDであるか新規キー範囲データrのIDであるかを判断するステップS41。ここで、親エッジデータpのIDがサーバデータsのIDである場合親ノードpがサーバデータsである場合、木構造データ生成部13は、新規キー範囲データrを親ノードpの子ノードcとする。すなわち、木構造データ生成部13は、新規キー範囲データrのID、重みw、子集合としての空集合を含む子エッジデータcを生成するステップS42。一方、親エッジデータpのIDが新規キー範囲データrのIDである場合親ノードpが新規キー範囲データrである場合、木構造データ生成部13は、サーバデータsを親ノードpの子ノードcとする。すなわち、木構造データ生成部13は、サーバデータsのID、重みw、子集合としての空集合を含む子エッジデータcを生成するステップS43。そして、木構造データ生成部13は、ステップS42またはステップS43で生成した子エッジデータcへのポインタを、親エッジデータpの子集合に追加するステップS44。次に、木構造データ生成部13は、子ノードcの最大キーが親ノードpの最大キーよりも大きいか否かを判断するステップS45。ここで、子ノードcの最大キーが親ノードpの最大キーよりも大きい場合、木構造データ生成部13は、子ノードcを次の親ノードpとおく。すなわち、木構造データ生成部13は、子エッジデータcを次の親エッジデータpとおくステップS46。そして、木構造データ生成部13は、エッジ生成処理を終了する。この後、木構造データ生成部13は、図9の処理に戻り、ステップS23またはステップS24を実行する。一方、子ノードcの最大キーが親ノードpの最大キーより大きくない場合、木構造データ生成部13は、そのまま、エッジ生成処理を終了する。このとき、もし、子ノードcの最大キーおよび親ノードpの最大キーが等しければ、木構造データ生成部13は、図9の処理に戻った後、ステップS22における判断に基づいて、木構造データ生成処理を終了する。子ノードcの最大キーが親ノードpの最大キーより小さければ、木構造データ生成部13は、図9の処理に戻った後、ステップS23またはステップS24を実行する。以上で、木構造データ生成部13の木構造データリスト生成処理および木構造データ生成処理の説明を終了する。木構造データ生成部13が以上のように動作することにより、図6aに示したサーバデータおよび新規キー範囲データから、図7bに示す木構造データが生成される。次に、このように生成された木構造データリストから、エッジの重みの合計が最大になる非隣接エッジ群を選択する組み合わせ算出部14の動作の詳細を、図12~図18に示すフローチャートを参照して説明する。図12では、まず、組み合わせ算出部14は、木構造データリストに含まれる各木構造データについて、エッジの重みの合計が最大になるように、非隣接エッジ群を算出する組み合せ算出処理を実行するステップS50。ここで、組み合わせ算出処理の詳細を図13に示す。図13では、組み合わせ算出部14は、木構造データに含まれる各エッジについて、重み合計データを算出する重み合計算出処理を再帰的に実行するステップS61。ここで、あるエッジに関する重み合計データとは、該エッジを最下層に含む部分木iにおける非隣接エッジ群の重み合計を表すデータである。深さiの各エッジの重み合計データは、深さi-1の各エッジの重み合計データに基づいて再帰的に算出される。このステップの詳細については後述する。次に、組み合わせ算出部14は、各エッジについて生成した重み合計データに基づいて、非隣接エッジ群を選択する。そして、組み合わせ算出部14は、選択したエッジ群に基づいて、サーバデータおよび新規キー範囲データのペアを決定するステップS62。このステップの詳細については後述する。以上で、組み合わせ算出部14は、組み合わせ算出処理を終了する。次に、ステップS61における重み合計算出処理について、図14~図15を参照して説明する。この例では、組み合わせ算出部14は、重み合計データを階層化した階層化データを生成する。重み合計データの階層化データの一例を図14に示す。図14は、図7に示した木構造データに基づいて生成された重み合計データの階層化データである。図14に示すように、あるエッジに関する1つの重み合計データ105105a~105nは、そのエッジのIDと、重み合計を表す値と、そのエッジの選択状態を表す情報と、親となる重み合計データへのポインタとからなる。エッジのIDは、例えば、そのエッジの両端の深さi-1および深さiのノードのIDの組み合わせによって表される。また、重み合計を表す値は、そのエッジを最下層に含む部分木iにおける非隣接エッジ群の重み合計を表す値である。また、エッジの選択状態を表す情報は、この重み合計データが、そのエッジが選択された場合のデータであるか選択されない場合のデータであるかを表す情報である。また、親となる重み合計データへのポインタは、重み合計の算出に用いられた深さi-1のエッジに関する重み合計データへのポインタである。各エッジについて、このような重み合計データは、エッジの選択状態が選択であるものと、未選択であるものとで2つずつ生成されることになる。ここで、エッジの選択状態が選択の重み合計データは、該エッジを最下層に含む部分木において該エッジを含む非隣接エッジ群の重み合計を表す。また、エッジの選択状態が未選択の重み合計データは、該エッジを最下層に含む部分木において該エッジを含まない非隣接エッジ群の重み合計を表す。例えば、図14において、木構造データのルートノードの深さを0とし、この木構造データの深さを6として説明する。図14において、例えば、深さ5までの部分木5において最下層のエッジc,d’に関する重み合計データは、重み合計データ105kおよび重み合計データ105lの2つである。また、重み合計データ105kは、エッジのIDとしてc’,dを含んでいる。また、重み合計データ105kは、重み合計データとして42を含んでいる。また、重み合計データ105kが含む重み合計データ105jへのポインタは、この重み合計データ42の算出に用いられたのは、部分木4における最下層のエッジc,c’に関する重み合計データ105jであることを表している。このような重み合計データの階層化データを生成する重み合計算出処理について、図15を参照して説明する。ここでは、木構造データが、図7bに示したようなエッジデータにより表されているものとする。図15では、まず、組み合わせ算出部14は、ルートのエッジデータをpとするステップS70。次に、組み合わせ算出部14は、重み合計データ集合Pを空集合に初期化するステップS71。次に、組み合わせ算出部14は、重み合計データ集合Cを空集合に初期化するステップS72。次に、組み合わせ算出部14は、親エッジデータpの子集合に含まれる各子エッジデータcについて、ステップS73~S74の処理を実行する。ここでは、まず、組み合わせ算出部14は、この子エッジデータcが示すエッジを選択しない場合の重み合計データを、重み合計データ集合Pに基づいて生成するステップS73。そして、生成した重み合計データを、重み合計データ集合Cに追加する。このステップの詳細については後述する。次に、組み合わせ算出部14は、このエッジデータcが示すエッジを選択する場合の重み合計データを、重み合計データ集合Pに基づいて生成するステップS74。そして、生成した重み合計データを、重み合計データ集合Cに追加する。このステップの詳細については後述する。子集合の各エッジデータcについてステップS73~S74の処理を終了すると、組み合わせ算出部14は、重み合計データ集合Cを、次の重み合計データ集合PとするステップS75。次に、組み合わせ算出部14は、親エッジデータpの子集合に含まれる子エッジデータcのうち、その子集合のサイズが1以上のものを次の親エッジデータpとするステップS76。そのような次の親エッジデータpが存在すればステップS77でNo、組み合わせ算出部14は、ステップS72からの処理を繰り返し実行する。一方、そのような次の親エッジデータpが存在しなければステップS77でYes、組み合わせ算出部14は、重み合計算出処理を終了する。次に、ステップS73における対象エッジ未選択の場合の重み合計算出処理の詳細について、図16を参照して説明する。図16では、まず、組み合わせ算出部14は、重み合計データ集合Pが空であるか否かを判断するステップS81。ここで、重み合計データ集合Pが空である場合、組み合わせ算出部14は、エッジのIDとして親エッジデータpのID,子エッジデータcのIDと、重み合計0と、選択状態として未選択と、ポインタとしてnullとを含む重み合計データを生成するステップS82。一方、重み合計データ集合Pが空でない場合、組み合わせ算出部14は、重み合計データ集合Pに含まれる重み合計データのうち、最大の重みを有する重み合計データw1を選択するステップS83。次に、組み合わせ算出部14は、エッジのIDとして親エッジデータpのID,子エッジデータcのIDと、重み合計データw1が有する重みと、選択状態として未選択と、重み合計データw1へのポインタとを含む重み合計データを生成するステップS84。次に、組み合わせ算出部14は、ステップS82またはステップS84で生成した重み合計データを、重み合計データ集合Cに追加するステップS85。以上で、組み合わせ算出部14は、対象エッジ未選択の場合の重み合計算出処理を終了する。次に、ステップS74における対象エッジを選択する場合の重み合計算出処理の詳細について、図17を参照して説明する。図17では、まず、組み合わせ算出部14は、重み合計データ集合Pが空であるか否かを判断するステップS91。ここで、重み合計データ集合Pが空である場合、組み合わせ算出部14は、エッジのIDとして親エッジデータpのID,子エッジデータcのIDと、重み合計として子エッジデータcの重みと、選択状態として選択と、ポインタとしてnullとを含む重み合計データを生成するステップS92。一方、重み合計データ集合Pが空でない場合、組み合わせ算出部14は、重み合計データ集合Pに含まれる重み合計データのうち、エッジのIDに親エッジデータpのIDを含みエッジの選択状態が選択のものを除いた中から、最大の重みを有する重み合計データw2を選択するステップS93。次に、組み合わせ算出部14は、エッジのIDとして親エッジデータpのID,子エッジデータcのIDと、重み合計データw2が有する重みに子エッジデータcの重みを加算した重みと、選択状態として選択と、重み合計データw2へのポインタとを含む重み合計データを生成するステップS94。次に、組み合わせ算出部14は、ステップS92またはステップS94で生成した重み合計データを、重み合計データ集合Cに追加する。以上で、組み合わせ算出部14は、対象エッジを選択する場合の重み合計算出処理を終了する。このように、組み合わせ算出部14は、部分木iにおいて深さiの各エッジを含む非隣接エッジ群の重み合計として、部分木i-1において深さi-1の各エッジに関して2つずつ算出した重み合計データのうち、深さiの該エッジに隣接するエッジを含む非隣接エッジ群の重み合計データを除いた中で、重み合計の最大値に、深さiの該エッジの重みを加算した値を適用する。また、組み合わせ算出部14は、部分木iにおいて深さiの各エッジを含まない非隣接エッジ群の重み合計として、部分木i-1において深さi-1の各エッジに関して2つずつ算出した重み合計データのうち、重み合計の最大値を適用する。以上で、図13のステップS61における重み合計算出処理の説明を終了する。次に、ステップS62における非隣接エッジ群選択処理について、図18を参照して説明する。この例では、組み合わせ算出部14は、図15~図17に示した動作により生成した階層化データ例えば、図14に示した階層化データを用いるものとする。まず、組み合わせ算出部14は、ステップS61で生成した階層化データの最下層の重み合計データのうち、その重みが最大である重み合計データwを選択するステップS101。次に、組み合わせ算出部14は、重み合計データwの選択状態が選択であるか未選択であるかを判断するステップS102。ここで、選択状態が未選択であれば、組み合わせ算出部14の処理はステップS104に進む。一方、選択状態が選択であれば、組み合わせ算出部14は、重み合計データwのIDが示すエッジの両端に相当するサーバデータおよび新規キー範囲データを、ペアリストに追加するステップS103。次に、組み合わせ算出部14は、重み合計データwのポインタがnullであるか否かを判断するステップS104。ここで、重み合計データwのポインタがnullでなければ、ポインタが指す重み合計データを、次の重み合計データwとするステップS105。そして、組み合わせ算出部14は、ステップS102からの処理を繰り返す。一方、重み合計データwのポインタがnullであれば、組み合わせ算出部14は、ペアリストに含まれていないサーバデータおよび新規キー範囲の任意の組合せを決定し、ペアリストに追加するステップS106。そして、組み合わせ算出部14は、エッジ選択処理を終了する。このように、組み合わせ算出部14は、重み合計データのポインタが指す親を再帰的に辿ることにより参照される重み合計データのうち、選択状態が選択である重み合計データのエッジを選択する。例えば、図7に示す階層化データに対して、非隣接エッジ群選択処理を実行する場合について説明する。組み合わせ算出部14は、まず、最下層の重み合計データのうち、重みが最大の71である重み合計データ105nを選択するステップS101。次に、組み合わせ算出部14は、重み合計データ105nの選択状態が選択であるためステップS102でYes、エッジの両端ノードに相当するサーバdおよび新規キー範囲d’をペアリストに追加するステップS103。次に、組み合わせ算出部14は、重み合計データ105nのポインタが指す重み合計データ105kについて、選択状態が未選択であるのでステップS102でNo、ペアリストへの追加を行わない。つまり、エッジは選択されない。次に、組み合わせ算出部14は、重み合計データ105kのポインタが指す重み合計データ105jについて、選択状態が選択であるためステップS102でYes、エッジの両端ノードに相当するサーバcおよび新規キー範囲c’をペアリストに追加するステップS103。このような処理を繰り返すことにより、組み合わせ算出部14は、最終的に、エッジを選択する。すなわち、組み合わせ算出部14は、サーバdおよび新規キー範囲d’、サーバcおよび新規キー範囲c’、ならびに、サーバaおよび新規キー範囲b’を、ペアリストに追加する。そして、組み合わせ算出部14は、選択されなかったサーバbおよび新規キー範囲a’を、さらにペアリストに追加するステップS106。以上で、ステップS62における非隣接エッジ群選択処理の説明を終了する。次に、本実施の形態の効果について述べる。本実施の形態としてのデータ再配置装置は、データ再配置先の決定処理にかかる計算時間を削減することができる。その理由は、木構造データ生成部が、キー範囲が重複する組合せであって、かつ、重複する範囲に対応するデータが存在するサーバデータおよび新規キー範囲データ間に、親子関係を示すエッジを生成するとともに、そのエッジに重複データ量に基づく重みを付与するからである。そして、組み合わせ算出部が、このような木構造データから、その重み合計が最大となるよう、ノードを共有しないエッジの組合せを選択するからである。このように、木構造データを用いて非隣接エッジ群を選択することにより、本実施の形態としてのデータ再配置装置は、サーバに新規キー範囲を割り当てる処理を、非特許文献1に記載の手順で割り当て問題を解く処理よりも遥かに少ない計算時間で行うことが可能となる。例えば、上述のように、木構造データの部分木を用いた再帰的処理により非隣接エッジ群を選択する処理は、部分木の各ノード各エッジに対する処理となるため、その計算時間はOnとなる。したがって、この場合、本実施の形態としてのデータ再配置装置は、非特許文献1に記載の手順を採用した場合の計算時間On^3に比べて、サーバ数nに対するスケーラビリティをより向上させることができる。なお、本実施の形態において、木構造データ生成部は、サーバデータおよび新規キー範囲データをそれぞれ昇順に並べたサーバデータリストおよび新規キー範囲データリストを用いて、木構造データを生成する例について説明した。本発明における木構造データ生成部は、その他の手順により本発明における木構造データを生成してもよい。例えば、木構造データ生成部は、図6bに示したグラフを構成するいずれのノードをルートノードとした木構造データを生成してもよい。また、本実施の形態において、木構造データ生成部は、図7bに示したようなエッジデータの階層データとして木構造データを保持する例について説明した。本発明における木構造データ生成部は、木構造データを表現可能なその他のデータ構造を用いて本発明の木構造データを保持してもよい。また、本実施の形態において、組み合わせ算出部は、木構造データの部分木を用いた再帰的処理を用いて非隣接エッジ群を選択する例について説明した。本発明における組み合わせ算出部は、その他の手順を用いて本発明における木構造データから非隣接エッジ群を選択してもよい。また、本実施の形態において、各フローチャートを参照して説明したデータ再配置装置の動作を、本発明のコンピュータプログラムとしてコンピュータ装置の記憶装置記憶媒体に格納しておき、係るコンピュータプログラムを当該CPUが読み出して実行するようにしてもよい。そして、このような場合において、本発明は、係るコンピュータプログラムのコード或いは記憶媒体によって構成される。また、本発明は、上述した実施の形態に限定されず、様々な態様で実施されることが可能である。"