(57)【要約】【課題】利用パターンに応答するようにデータグラフの物理記憶を調整するメカニズムを提供する。【解決手段】実施形態は、頂点間の関係を表す辺によって相互接続される頂点として情報を表し、複数のグラフパーティションを有するデータグラフを記憶する分散型データグラフ記憶システムを含む。システムは、グラフパーティションのバーションを符号化するデータ部分を記憶する複数のデータ記憶サーバと、２以上のデータ部分が同じグラフパーティションのバージョンを夫々符号化する場合に、それらのデータ部分を異なるデータ記憶サーバへ割り当てるデータ部分分配コントローラと、データグラフのアクセス要求を受け取ってデータ記憶サーバ間で分配するデータアクセスモジュールと、アクセス要求によるデータアクセスイベントのデータ部分間の分配を表す統計値を記録するグラフパーティション利用モニタとを有し、データ部分分配コントローラは、統計値に応じて特定のグラフパーティションのバージョンを符号化するデータ部分の数を増減させる。【選択図】図１
2015225656.tif 000002
【特許請求の範囲】
【請求項１】
接続される頂点どうしの間の関係を表す辺によって相互接続される頂点として情報を表し、複数のグラフパーティションを有するデータグラフを記憶するよう構成される分散型データグラフ記憶システムであって、
夫々が前記複数のグラフパーティションの中の１つのバーションを符号化する１又はそれ以上のデータ部分を記憶するよう夫々構成される複数のデータ記憶サーバと、
２又はそれ以上のデータ部分が前記複数のグラフパーティションの中の同じグラフパーティションのバージョンを夫々符号化する場合に、前記複数のデータ記憶サーバの中の異なるデータ記憶サーバへ前記２又はそれ以上のデータ部分を割り当てるよう構成されるデータ部分分配コントローラと、
前記記憶されたデータグラフのアクセス要求を受け取り、該受け取られたアクセス要求を前記複数のデータ記憶サーバの間で分配するよう構成されるデータアクセスモジュールと、
前記アクセス要求によって引き起こされるデータアクセスイベントの前記データ部分の間の分配を表す統計値を記録するよう構成されるグラフパーティション利用モニタと
を有し、
前記データ部分分配コントローラは、前記記録された統計値に応じて前記グラフパーティションの中の１つのバージョンを符号化する前記データ部分の数を増減させるよう構成される、分散型データグラフ記憶システム。
【請求項２】
前記記録された統計値は、時間期間を通じた前記データ部分にわたるデータアクセスイベントの分配と、前記時間期間を通じた前記複数のデータ記憶サーバにわたるデータアクセスイベントの分配とを含み、
前記データ部分分配コントローラは、
データ部分を特定し、該特定されたデータ部分を記憶するデータ記憶サーバでのデータアクセスイベントの数の割合としての前記特定されたデータ部分でのデータイベントの数が、前記特定されたデータ部分を記憶するデータ記憶サーバで記憶されるデータ部分の総サイズの割合としての前記特定されたデータ部分のサイズを閾量よりも多く超えるようにし、且つ
前記特定されたデータ部分によって符号化されるバージョンのグラフパーティションを、そのバージョンを符号化するデータ部分の数を増大させるグラフパーティションとして選択する
ことによって、前記グラフパーティションの中からパーティションを選択し、該選択されたパーティションのバージョンを符号化するデータ部分の数を増大させるよう構成される、
請求項１に記載の分散型データグラフ記憶システム。
【請求項３】
前記記録された統計値は、前記グラフパーティションにわたるデータアクセスイベントの分配を含み、
前記データ部分分配コントローラは、
グラフパーティションを特定し、該特定されたグラフパーティションを符号化するデータ部分ごとの前記特定されたグラフパーティションでのデータアクセスイベントの数が、前記特定されたグラフパーティションを符号化するデータ部分のサイズによって加減される前記特定されたグラフパーティションを符号化するデータ部分を記憶する１又はそれ以上のデータ記憶サーバでのデータアクセスイベントの総数を閾量よりも多く超えるようにする
ことによって、前記グラフパーティションの中からパーティションを選択し、該選択されたパーティションのバージョンを符号化するデータ部分の数を増大させるよう構成される、
請求項１に記載の分散型データグラフ記憶システム。
【請求項４】
前記データ部分分配コントローラは更に、前記複数のグラフパーティションの夫々について、当該グラフパーティションの１の特性又は１よりも多い特性の組み合わせに応じて、記憶すべき前記グラフパーティションのバージョンを符号化するデータ部分の数を決定するよう構成され、
前記１又はそれ以上の特性は、
当該グラフパーティションにおける辺の数に比例する第１の値によって測定される第１の特性、及び
前記データグラフにおける頂点の平均及び最大次数と比較される当該グラフパーティションにおける頂点の平均及び最大次数に基づき第２の値によって測定される第２の特性
の少なくともいずれかを含む、
請求項１に記載の分散型データグラフ記憶システム。
【請求項５】
前記データ部分分配コントローラは、
夫々が関連する係数を有する辺タイプの所定の組の中の１つであると夫々の辺を特定し、
夫々の辺タイプについての、当該辺タイプであると特定された前記グラフパーティションにおける辺の数と前記関連する係数との積を合計することによって、前記第１の値を計算する
よう構成される、請求項４に記載の分散型データグラフ記憶システム。
【請求項６】
境界複製モジュールを更に有し、該境界複製モジュールは、夫々のグラフパーティションについて、当該グラフパーティションのバージョンを符号化する夫々のデータ部分へ
当該グラフパーティションの境界頂点の近傍にある各頂点であり且つ当該グラフパーティション以外の他のグラフパーティションに含まれる第１グループの頂点の夫々を符号化するデータのコピー、及び
前記第１グループの頂点の近傍にある各頂点であり且つ当該グラフパーティション以外の他のグラフパーティションに含まれる第２グループの頂点の一員と当該グラフパーティションとの間の結合を評価する基準を満足していると前記境界複製モジュールによって決定される、前記第２グループの頂点の夫々を符号化するデータのコピー
を加えるよう構成される、請求項１に記載の分散型データグラフ記憶システム。
【請求項７】
前記境界複製モジュールは、前記第２グループの頂点の各員について、
当該グラフパーティションと前記第２グループの頂点の一員との和集合の範囲である第１の範囲、及び
当該グラフパーティションの範囲である第２の範囲
を計算するよう構成され、
前記第２グループの頂点の一員は、前記第１の範囲が前記第２の範囲よりも小さい場合に、当該グラフパーティションと前記第２グループの頂点の一員との間の結合を評価する前記基準を満足したと決定される、
請求項６に記載の分散型データグラフ記憶システム。
【請求項８】
パーティション境界更新モジュールを更に有し、該パーティション境界更新モジュールは、
目標頂点とグラフパーティションとの間のグラフごとの結合を表すグラフベース結合値を計算するよう構成されるグラフベース結合計算部と、
目標頂点とグラフパーティションとの間の利用ごとの結合を表す利用ベース結合値を計算するよう構成される利用ベース結合計算部と
を有し、
前記パーティション境界更新モジュールは、前記グラフパーティションの夫々についてパーティション更新を実行するよう構成され、
パーティション更新は、当該グラフパーティションの境界頂点の近傍にあり且つ前記目標頂点として当該グラフィパーティション以外の前記複数のグラフパーティションの中の他の１つに含まれる夫々の頂点について、
前記目標頂点と当該グラフパーティションとの間のグラフごとの結合を表す前記グラフベース結合値を計算するよう前記グラフベース結合計算部を使用し、前記目標頂点と当該グラフパーティションとの間の利用ごとの結合を表す利用ベース結合値を計算するよう前記利用ベース結合計算部を使用することと、
前記グラフベース結合値及び前記利用ベース結合値を結合して全体結合値を計算することと、
前記全体結合値が所定の閾値を超える場合は、前記目標頂点を当該グラフパーティションに加え、前記目標頂点をその現在のグラフパーティションから除くことと
を含む、請求項１に記載の分散型データグラフ記憶システム。
【請求項９】
前記グラフベース結合値は、当該グラフパーティションにおける夫々の中心頂点について、前記中心頂点から当該グラフパーティションの辺での頂点の夫々への最短経路の中で最長の長さの割合としての、前記目標頂点から前記中心頂点への最短経路の長さに基づく、
請求項８に記載の分散型データグラフ記憶システム。
【請求項１０】
前記利用ベース結合値は、当該グラフパーティションと重なり合うグラフトラバーサル経路の総数の、該グラフトラバーサル経路において前記目標頂点を含んだ被選択時間期間に対する割合に基づく、
請求項８に記載の分散型データグラフ記憶システム。
【請求項１１】
前記計算された利用ベース結合値は、その計算と前記被選択時間期間の終わりとの間の時間に基づき時間減衰係数によって加減される、
請求項１０に記載の分散型データグラフ記憶システム。
【請求項１２】
前記目標頂点を当該グラフパーティションに加えることが、当該グラフパーティションに所定の最大パーティションサイズを超えさせる場合に、新しいデータ部分が、前記目標頂点を符号化するデータと、当該グラフパーティションの中心頂点又は１以上の中心頂点の夫々について、前記中心頂点を符号化するデータ、及び前記目標頂点から前記中心頂点への最短経路上の頂点の夫々を符号化するデータとを有して生成される、
請求項１１に記載の分散型データグラフ記憶システム。
【請求項１３】
接続される頂点どうしの間の関係を表す辺によって相互接続される頂点として情報を表すデータグラフを記憶する方法であって、前記データグラフは、複数のグラフパーティションを有し、複数のデータ記憶サーバの間で分散される複数のデータ部分として記憶され、夫々のデータ部分は、前記複数のグラフパーティションの中の１つのバーションを符号化し、２又はそれ以上のデータ部分が前記複数のグラフパーティションの中の同じグラフパーティションのバージョンを夫々符号化する場合に、前記２又はそれ以上のデータ部分は、前記複数のデータ記憶サーバの中の異なるデータ記憶サーバに記憶される、方法において、
前記記憶されたデータグラフのアクセス要求を受け取り、
前記受け取られたアクセス要求を前記複数のデータ記憶サーバの間で分配し、
前記アクセス要求によって引き起こされるデータアクセスイベントの前記データ部分の間の分配を表す統計値を記録し、
前記記録された統計値に応じて前記グラフパーティションの中の１又はそれ以上のバージョンを符号化する前記データ部分の数を増減させる、方法。
【請求項１４】
コンピュータによって実行される場合に、該コンピュータに、接続される頂点どうしの間の関係を表す辺によって相互接続される頂点として情報を表すデータグラフを記憶するプロセスを実行させるコンピュータプログラムであって、前記データグラフは、複数のグラフパーティションを有し、複数のデータ記憶サーバの間で分散される複数のデータ部分として記憶され、夫々のデータ部分は、前記複数のグラフパーティションの中の１つのバーションを符号化し、２又はそれ以上のデータ部分が前記複数のグラフパーティションの中の同じグラフパーティションのバージョンを夫々符号化する場合に、前記２又はそれ以上のデータ部分は、前記複数のデータ記憶サーバの中の異なるデータ記憶サーバに記憶される、コンピュータプログラムにおいて、
前記プロセスは、
前記記憶されたデータグラフのアクセス要求を受け取るステップと、
前記受け取られたアクセス要求を前記複数のデータ記憶サーバの間で分配するステップと、
前記アクセス要求によって引き起こされるデータアクセスイベントの前記データ部分の間の分配を表す統計値を記録するステップと、
前記記録された統計値に応じて前記グラフパーティションの中の１又はそれ以上のバージョンを符号化する前記データ部分の数を増減させるステップと
を有する、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフデータの分散記憶の分野にある。特に、本発明は、データグラフ内からのサブグラフの複製を制御する制御メカニズムに関する。
【背景技術】
【０００２】
グラフデータモデルは、分散型データ記憶システムに記憶される場合に、２つの特性に起因して困難にぶつかる。第１に、アクセス要求に応答して実行されるべき２つの主たるグラフデータ演算は、トラバーサル／経路探索及びサブグラフ照合である。前者の演算を有効にサポートするために、トラバーサル経路上にある全ての頂点（又は可能な限り多くの頂点）は、通信ネットワーク上でデータを運ぶことを避けるように、同じ物理データ記憶サーバに記憶されるべきある。通信ネットワーク上でデータを運ぶことは、多くの場合に、性能のボトルネックとなる。しかし、これは、トラバースのクエリ及び適用に依存し、トラバーサル経路は、静的な様態において予測され得ない。幾つかのドメインヒューリスティックは、数値基準に基づきグラフを分割するのに役立つことができるが、実際の性能は、依然としてクエリに特有であり、予測するのが困難である。システム性能は、クエリパターンが変化する場合に悪化することがある。
【０００３】
最小カット（min-cut）に基づくパーティションアルゴリズムは、データ記憶サーバ境界にわたって共有されるグラフ辺の数を最小限とすることができる。しかし、これは、共有される辺を横断するトラバーサルのトラフィックよりむしろ、共有される辺の数を最小限にし、よって、２つのデータサーバの間の通信が最小限とされることを保証することはできない。時間にわたって、辺が、過渡に多数のトラバースクエリに現れることがよくある。この辺におけるカットは、全体の性能の悪化を必然的に引き起こす。
【０００４】
一方、グラフの特定の部分は、幾つかの部分におけるグラフ頂点が他の部分のグラフ頂点よりもずっと大きい次数を有することができるという意味で、他の部分よりも密度が高いことがある。また、グラフの特定の経路は、特定のユーザアプリケーションにとって重要である情報を保持し、よって、他の経路と比較してクエリが多くなる可能性が高い。そのような人気のあるグラフ経路は、システム性能のボトルネックとなり得る。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
通信ネットワークにわたってグラフ頂点を運ぶ必要性を減らすように、利用パターンに応答するためにデータグラフの物理記憶を調整することができるメカニズムを見つけることが望ましい。
【課題を解決するための手段】
【０００６】
本発明の実施形態は、接続される頂点どうしの間の関係を表す辺によって相互接続される頂点として情報を表し、複数のグラフパーティションを有するデータグラフを記憶するよう構成される分散型データグラフ記憶システムを含む。当該データグラフ記憶システムは、夫々が前記複数のグラフパーティションの中の１つのバーションを符号化する１又はそれ以上のデータ部分を記憶するよう夫々構成される複数のデータ記憶サーバと、２又はそれ以上のデータ部分が前記複数のグラフパーティションの中の同じグラフパーティションのバージョンを夫々符号化する場合に、前記複数のデータ記憶サーバの中の異なるデータ記憶サーバへ前記２又はそれ以上のデータ部分を割り当てるよう構成されるデータ部分分配コントローラと、前記記憶されたデータグラフのアクセス要求を受け取り、該受け取られたアクセス要求を前記複数のデータ記憶サーバの間で分配するよう構成されるデータアクセスモジュールと、前記アクセス要求によって引き起こされるデータアクセスイベントの前記データ部分の間の分配を表す統計値を記録するよう構成されるグラフパーティション利用モニタとを有し、前記データ部分分配コントローラは、前記記録された統計値に応じて前記グラフパーティションの中の１つのバージョンを符号化する前記データ部分の数を増減させるよう構成される。
【０００７】
有利に、本発明の実施形態は、データグラフの特定のサブセットに対してなされる同時のアクセスに付随するボトルネックを回避するために、データグラフのサブセットの複製を制御する手段を提供する。データアクセス要求の分配を表す統計値の記録及び使用は、しばしば偏ってクエリされる記憶されたデータのサブセットを特定し、それらの記憶されたデータによって符号化されるグラフのエリアの複製を増やすメカニズムを提供する。そのような複製は、ほとんど偏らずにクエリされる記憶されたデータのサブセットを記憶するのに既に使用されている記憶空間を犠牲にすることがある。
【０００８】
分散型記憶システムは、少なくとも２つの別個のデータ記憶サーバを含む。データ記憶サーバは、記憶ノード、データ記憶ノード、記憶ユニット、データ記憶ユニット、又は単にノード若しくはサーバと呼ばれることもある。データ記憶サーバは、データを、それらがアクセス、クエリ、及び読み出し又は変更され得る形で記録する記憶ハードウェアのみならず、記憶されたデータへのアクセスを制御するよう構成される管理モジュール又はコントローラも含む。例えば、管理モジュールは、データ記憶サーバへ提起されるクエリを扱うよう構成されてよい。クエリを扱うことは、データアクセスモジュールのような他のエンティティからクエリを受け取ること、データ記憶サーバに記憶されているデータを検索して、クエリを満足するデータ項目を見つけること、及びクエリを満足するデータ項目を（場合により、変更された形又は部分的な形において）クエリ結果として出力することを含んでよい。夫々のデータ記憶サーバは、自身に記憶されているデータへの特定の数の同時のアクセス（例えば、クエリ又は範囲クエリであるアクセス）を扱うよう構成されるそれ自身のプロセッサを有してよい。特定の数は、記憶システム内の全てのデータ記憶サーバにわたって一様であってよく、あるいは、データ記憶サーバ間で異なることがある個々のデータ記憶サーバの特性であってよい。
【０００９】
データグラフは、記憶されているデータのマニフェステーションであり、記憶されているデータを、ユーザ又は他の外部のアプリケーションへ並びに記憶システム内のプロセスへ表す手段である。データグラフは、記憶に際して何らかの方法で符号化される。例えば、データグラフは、トリプル、例えば、ＲＤＦトリプルとして符号化されてよい。代替的に、又は追加的に、データは、リソース又は頂点を定義する追加データ（例えば、メタデータ）が記憶される記憶位置に索引付けするキーとしての機能を果たすトリプルとともに、キー値記憶において記憶され得る。
【００１０】
グラフパーティションは、データグラフのサブセットであり、グラフ内の隣接する頂点のサブセットであってよく、それにより、グラフパーティションは、グラフの連続的な範囲である。アルゴリズムが、データグラフを分割するために存在し、そのようなアルゴリズムは、如何にしてデータグラフを分割するかを決定するために、本発明の実施形態と協調して使用されてよい。例えば、一緒にクエリされる傾向がある頂点のグループが同じグラフパーティションに含まれるように、利用に基づく統計値が考慮され得る。代替的に、又は追加的に、パーティション境界をまたぐ辺（弧又は相互接続とも呼ばれる。）の数を最小限とするといった、トポグラフィー的配慮が、考慮されてよい。
【００１１】
トリプルは、グラフデータを複数のサブジェクト−プリディケート−オブジェクト表現として特性化することによって、グラフデータを符号化することを提供する。その意味で、サブジェクト及びオブジェクトは、グラフデータのグラフノード／リソースであり、そのようなもとしても、エンティティ、頂点、リソース、インスタンス、又はコンセプトであり、プリディケートは、サブジェクトとオブジェクトとの間の関係の表れである。プリディケートは、オブジェクトへの特定のタイプのリンクを提供することによって、サブジェクトに関する何かをアサートする。例えば、サブジェクトは、ウェブリソースを表してよく（例えば、ＵＲＩを介する。）、プリディケートは、リソースの特定の特質、特性、又は側面を表し、オブジェクトは、その特質、特性、又は側面のインスタンスを表す。つまり、トリプル記述の集合は、有向グラフデータを本質的に表す。ＲＤＦ標準は、そのようなトリプルのための軽視課された構造を提供する。
【００１２】
グラフパーティションは、データグラフの領域であると考えられてよい。グラフパーティションは、データグラフを符号化するデータ項目が記憶のために如何にしてグループ化されるかを定義する。データ部分は、記憶のためにグループ化された複数のデータ項目であると考えられてよい（すなわち、記憶サーバへ分配されて記憶されるプロセスのための単位として扱われる。）。よって、グラフパーティションは、対応するデータ部分に記憶されているデータ項目を定義する。このように、夫々のデータ部分は、対応するグラフパーティションのバージョンを符号化する。同じグラフパーティションのバージョンを符号化する１よりも多いデータ部分が存在してよい。同じグラフパーティションを符号化するデータ部分の数は、設定可能である。データ部分に対応するグラフパーティションは、対応するデータ部分の夫々によって必ずしも完全に符号化されない。例えば、グラフパーティションの中心頂点、１又はそれ以上の境界頂点、及び中心頂点の夫々と１又はそれ以上の境界頂点の夫々との間の最短経路上の頂点を含むグラフパーティションに対応するデータ部分が存在してよい。データ部分は、対応するグラフパーティションに加えて、グラフの部分、例えば、近傍のグラフパーティションの境界頂点を符号化してよい。
【００１３】
２又はそれ以上のデータ部分が夫々同じグラフパーティションのバージョンを符号化する場合に、データ部分分配コントローラは、それらの２又はそれ以上のデータ部分の夫々を異なるデータ記憶サーバへ割り当てるよう構成される。この技術によって、データ部分、ひいては、グラフパーティションに対してなされる同時のアクセスの機会は増やされる。
【００１４】
データグラフへのアクセス要求は、データアクセスモジュールによって受け取られて分配される。データアクセスモジュールは、夫々のアクセス要求を満足するようどのグラフパーティションをクエリすべきかを決定し、受け取られたアクセス要求を、夫々の決定されたグラフパーティションのバージョンを符号化するデータ部分を記憶するデータ記憶サーバへ分配するよう構成される。例えば、データ記憶サーバへのグラフパーティションのためのマッピングが、データアクセスモジュールで保持されてよい。そのような場合におけるデータアクセスイベントは、データ記憶サーバへの又はデータ記憶サーバに記憶されている特定のデータ部分へのアクセス要求の分配であってよい。代替的に、データアクセスモジュールは、受け取られたアクセス要求を全てのノードへ分配するよう構成されてよい。
【００１５】
受け取られたアクセス要求は、記憶システムでのイベントを引き起こす。そのようなイベントは、グラフパーティション利用モニタによってデータアクセスイベントとして記録されてよい。記録されるデータアクセスイベントと、それらが記録されるフォーマットとの正確な組み合わせは、実施に応じて様々である。一例として、記録されたデータアクセスイベントは、受け取られたアクセス要求を満足する結果としてのデータ部分からのデータ項目の読み出しであってよく、読み出しは、データ部分、データ部分によって符号化されるグラフパーティション、及び／又はデータ部分が記憶されるデータ記憶サーバのうちの１又はそれ以上によって起こる結果のカウントをインクリメントすることによって記録されてよい。記録されたデータアクセスイベントの他の例は、データ記憶サーバによるアクセス要求の受け取り及び処理であってよい（例えば、データアクセスモジュールが夫々のアクセス要求を満足するようどのグラフパーティションをクエリすべきかを決定し、受け取られたアクセス要求を、夫々の決定されたグラフパーティションのバージョンを符号化するデータ部分を記憶するデータ記憶サーバへ分配するよう構成される実施形態における）。先と同じく、それは、決定されたグラフパーティション、若しくはデータ記憶サーバにある、決定されたグラフパーティションを符号化するデータ部分によって起こるカウントとして、又はデータ記憶サーバによって起こるカウントとして、記録されてよい。アクセスイベントは、イベントが起こったタイミングと関連付けて記録されるか、又は何らかの他の方法で時間に依存させてよく、それにより、特定の時間期間に起こるカウントがクエリされ得る。
【００１６】
グラフパーティション利用モニタによって（統計値の例として）記録されたカウントは、どのグラフパーティションが現在よりも多い回数複製されるべきかと、どのグラフパーティションが現在よりも少ない回数複製されるべきかとを決定する手段として、データ部分分配コントローラによって利用される。統計値は、どのグラフパーティションがよりビジーであり、すなわち、他よりも多く同時にアクセスされ、従って、例えば、同時のアクセスの回数が、特定の時点にグラフパーティションのバージョンを符号化するデータ部分にアクセスすることができる管理モジュールの数よりも多い場合に、処理のボトルネックを引き起こすかを決定する手段を提供する。このように、データ部分分配コントローラは、複数のグラフパーティションの中の特定のグラフパーティションのバージョンを符号化するデータ部分の数を増減させることによって、その特定のグラフパーティションへの同時のアクセスを扱うよう記憶システムの能力を制御することができる。グラフパーティション利用モニタによって記録された統計値は、増大すべき数（グラフパーティションの中のグラフパーティションのバージョンを符号化するデータの数）及び低減すべき数に関する決定が基づくべき情報のソースを提供する。
【００１７】
データ部分分配コントローラによって実施される理論的解釈を行う特定の解析及び決定は、利用可能な記録された統計値及び記憶システムの利用環境に従って様々である。なお、データ部分分配コントローラが従うプロシージャは、データアクセスイベントが偏って起こる、データグラフの又はデータグラフを符号化するデータのサブセットを特定してよく、釣り合いは、データ部分を記憶するデータ記憶サーバに記憶されているデータ部分の合計サイズ又はデータグラフ全体に対するサブセットのサイズに関して決定される。
【００１８】
データ部分分配コントローラが従うプロシージャの第１の例として、記録された統計値は、時間期間を通じた前記データ部分にわたるデータアクセスイベントの分配と、前記時間期間を通じた前記複数のデータ記憶サーバにわたるデータアクセスイベントの分配とを含み、前記データ部分分配コントローラは、データ部分を特定し、該特定されたデータ部分を記憶するデータ記憶サーバでのデータアクセスイベントの数の割合としての前記特定されたデータ部分でのデータイベントの数が、前記特定されたデータ部分を記憶するデータ記憶サーバで記憶されるデータ部分の総サイズの割合としての前記特定されたデータ部分のサイズを閾量よりも多く超えるようにし、且つ、前記特定されたデータ部分によって符号化されるバージョンのグラフパーティションを、そのバージョンを符号化するデータ部分の数を増大させるグラフパーティションとして選択することによって、前記グラフパーティションの中からパーティションを選択し、該選択されたパーティションのバージョンを符号化するデータ部分の数を増大させるよう構成される。
【００１９】
例えば、データアクセスイベントは、アクセス要求に応答してデータ部分から読み出されたデータ項目であってよい。第１の例となるプロシージャは、データ部分での単位データ当たりのデータアクセスイベントの頻度が、データ部分を記憶するデータ記憶サーバでの単位データ当たりのデータアクセスイベントの頻度よりも多いか否かを特定する。データ部分のサイズ及びデータ記憶サーバのサイズ、従って、単位は、データ項目の数であってよく、あるいは、ｋＢのような記憶空間の単位であってよい。データ部分での単位データ当たりの頻度が、データ記憶サーバでの単位データ当たりの頻度よりも閾量よりも多く多い場合は、そのデータ部分は複製され、新しい複製は、同じグラフパーティションのバージョンを符号化するデータ部分を未だ記憶していないデータ記憶サーバへ加えられる。閾量は、所定の量であってよく、あるいは、時間期間を通じたデータ記憶サーバでのデータアクセスイベントの回数のうちの所定の部分、例えば、１０％であってよい。所定の部分は、データ管理者によって設定可能である。
【００２０】
第１の例となるプロシージャに対する代替の又は追加のプロシージャとして、第２の例となるプロシージャが、以下で説明される。
【００２１】
第２の例となるプロシージャにおいて、記録された統計値は、前記グラフパーティションにわたるデータアクセスイベントの分配を含み、前記データ部分分配コントローラは、グラフパーティションを特定し、該特定されたグラフパーティションを符号化するデータ部分ごとの前記特定されたグラフパーティションでのデータアクセスイベントの数が、前記特定されたグラフパーティションを符号化するデータ部分のサイズによって加減される前記特定されたグラフパーティションを符号化するデータ部分を記憶する１又はそれ以上のデータ記憶サーバでのデータアクセスイベントの総数を閾量よりも多く超えるようにすることによって、前記グラフパーティションの中からパーティションを選択し、該選択されたパーティションのバージョンを符号化するデータ部分の数を増大させるよう構成される。
【００２２】
第２の例となるプロシージャは、広くクエリされるグラフパーティションを特定しようとし（グラフパーティションでのデータアクセスイベントが、そのグラフパーティション内から結果を返す、行われているクエリであってよいことを念頭に置く。）、そうして特定されたグラフパーティションの複製を増やす点で、第１の例となるプロシージャと相違する。
【００２３】
第１及び第２の例となるプロシージャは、時間期間を通じたデータアクセスイベントの分配に応答して異なるグラフパーティションの複製の数を調整する技術を提供する。データグラフの開始時に、調整すべきその時点、又は特定のシステムイベント後といった他の時点で、利用統計値がない場合に、夫々のグラフパーティションの幾つのバージョンが記憶されるべきかを決定するためにグラフの構造特性を使用する必要があり得る。例えば、前記データ部分分配コントローラは更に、前記複数のグラフパーティションの夫々について、当該グラフパーティションの１の特性又は１よりも多い特性の組み合わせに応じて、記憶すべき前記グラフパーティションのバージョンを符号化するデータ部分の数を決定するよう構成され、前記１又はそれ以上の特性は、当該グラフパーティションにおける辺の数に比例する第１の値によって測定される第１の特性と、前記データグラフにおける頂点の平均及び最大次数と比較される当該グラフパーティションにおける頂点の平均及び最大次数に基づき第２の値によって測定される第２の特性との少なくともいずれかを含む。
【００２４】
データ部分分配コントローラによる決定は、最初の計算としてであってよく、あるいは、システムイベントに応答してよい。有利に、第１の特性は、計算するのが極めて容易であり、結果として、より大きいグラフパーティションのより多くのバージョンが記憶される。処理のボトルネックを引き起こす同時のアクセス要求の可能性は、より大きいグラフパーティションでより高く、故に、第１の特性はこれを考慮に入れる。有利に、第２の特性は、より高い次数を有する頂点はクエリされる可能性がより高く、従って、処理のボトルネックの原因となる可能性画より高いとの予測を利用する。第２の特性は、夫々のパーティションが何回複製されるべきかを決定する際にこれを考慮に入れる。
【００２５】
第１の特性は、単に、夫々のグラフパーティションを符号化する辺の数のカウントを求めることによって、測定されてよい。より高度な例では、辺は、異なる辺タイプの所定の組からの１つとして特性化されてよい。例えば、前記データ部分分配コントローラは、夫々が関連する係数を有する辺タイプの所定の組の中の１つであると夫々の辺を特定し、夫々の辺タイプについての、当該辺タイプであると特定された前記グラフパーティションにおける辺の数と前記関連する係数との積を合計することによって、前記第１の値を計算するよう構成される。有利に、そのようなプロシージャは、ドメインの存在論を定義し及び／又はクラス定義を与えるもののような特定のタイプの辺が、より頻繁にクエリされ、従って、処理のボトルネックを引き起こす可能性がより高いと認識する。
【００２６】
記憶すべき夫々のグラフパーティションのバージョンの数を決定すると、実施形態は、どの頂点をグラフパーティションの各バージョンにおいて符号化すべきかを決定する更なるステップを含んでよい。特定のグラフパーティションを符号化する各バージョンは、そのグラフパーティションにおける各頂点、次いで、更に、他のグラフパーティションからの幾つかの頂点を符号化してよい。グラフパーティションの符号化されたバージョンを投入する制御は、コントローラにあるモジュールによって実行されてよく、例えば、分散型データグラフ記憶システムは、境界複製モジュールを更に有してよく、該境界複製モジュールは、夫々のグラフパーティションについて、当該グラフパーティションのバージョンを符号化する夫々のデータ部分へ、当該グラフパーティションの境界頂点の近傍にある各頂点であり且つ当該グラフパーティション以外の他のグラフパーティションに含まれる第１グループの頂点の夫々を符号化するデータのコピーと、前記第１グループの頂点の近傍にある各頂点であり且つ当該グラフパーティション以外の他のグラフパーティションに含まれる第２グループの頂点の一員と当該グラフパーティションとの間の結合を評価する基準を満足していると前記境界複製モジュールによって決定される、前記第２グループの頂点の夫々を符号化するデータのコピーとを加えるよう構成される。
【００２７】
グラフパーティションの境界頂点は、グラフパーティションに属し、且つ、単一の辺を介して他のグラフパーティションに属する１又はそれ以上の頂点の夫々へ接続される頂点である。有利に、特定のグラフパーティションが符号化される同じデータ部分において特定のグラフパーティションの近傍にあるグラフパーティションからの境界頂点を符号化することは、境界を越えるトラバーサル経路を減らすのに役立つことができ、これは、最終的に、データグラフアクセスレベルで処理のボトルネックの可能性を低減する。結合を評価する基準は、近傍のグラフパーティションからのどの境界頂点を含めるべきか、及びどれを含めないべきかを決定し、それによって、不必要な記憶空間をデータ部分に捧げることを回避するのを支援するメカニズムを提供する。
【００２８】
結合を評価するための、特定の形態の基準は、データグラフ及びその適用の具体的な要件に依存する。距離又は経路長さが辺に起因すると考えるデータグラフにおける基準の例となる形態は、候補境界頂点を有して及びそれを有さずに符号化されているグラフパーティションの範囲を計算し、両者を比較することである。例えば、前記境界複製モジュールは、前記第２グループの頂点の各員について、当該グラフパーティションと前記第２グループの頂点の一員との和集合の範囲である第１の範囲と、当該グラフパーティションの範囲である第２の範囲を計算するよう構成され、前記第２グループの頂点の一員は、前記第１の範囲が前記第２の範囲よりも小さい場合に、当該グラフパーティションと前記第２グループの頂点の一員との間の結合を評価する前記基準を満足したと決定される。
【００２９】
グラフパーティションを含むサブグラフの範囲は、グラフパーティションの中心頂点の夫々からサブグラフの辺頂点への最短距離を計算し、計算された最短経路のうちの最長のものを範囲として設定することによって、決定される。経路長さは、辺の特性として各辺に属してよい。代替的に、データグラフは一様であってよく、各辺は同じ経路長さを属性とし、それにより、１つの頂点から他の頂点までの経路長さを計算することは、その経路上の辺の数を数えることによって実行される。サブグラフに属する頂点は、それが、同じくサブグラフに属する頂点どうしを接続する辺によって囲まれていない場合は、サブグラフの辺にあると見なされてよい。中心頂点は、媒介中心性メトリックを用いて、上位ｎスコア（ｎは、予め決定されているか、又はグラフパーティションにおける頂点の数の所定の割合である正の数である。）を有する頂点を選択することによって、決定されてよい。グラフパーティションの中心頂点を見つける代替の技術として、次数に基づくメトリックが使用されてよく、それにより、次数に応じて順位付けるされる場合に上位ｎ個（先と同じく、ｎは、予め決定されているか、又はグラフパーティションにおける頂点の数の所定の割合である正の数である。）の頂点が中心頂点である。最後に、グラフパーティションにおける頂点の各対の間の最短経路が計算されてよく、頂点は出現回数に応じて順位付けされ、上位ｎ個（先と同じく、ｎは、予め決定されているか、又はグラフパーティションにおける頂点の数の所定の割合である正の数である。）が中心頂点と見なされる。
【００３０】
記憶されているデータの特定のセクションに対してなされる同時のアクセスに付随する処理のボトルネックを減らすことを目的として、夫々のグラフパーティションが、そのグラフパーティションの間のデータアクセスイベントの分配に応答して、記憶の際に符号化される回数を適応させる技術は、先に及び別の場所で論じられている。同時のアクセスに付随する処理のボトルネックを減らすために、記憶されているデータを適応させる代替の又は追加の技術として、グラフパーティションは、利用に基づく結合指標に応答して変更されてよい。例えば、当該分散型データグラフ記憶システムは、パーティション境界更新モジュールを更に有してよい。そのようなパーティション境界更新モジュールは、目標頂点とグラフパーティションとの間のグラフごとの結合を表すグラフベース結合値を計算するよう構成されるグラフベース結合計算部と、目標頂点とグラフパーティションとの間の利用ごとの結合を表す利用ベース結合値を計算するよう構成される利用ベース結合計算部とを有し、前記パーティション境界更新モジュールは、前記グラフパーティションの夫々についてパーティション更新を実行するよう構成され、パーティション更新は、当該グラフパーティションの境界頂点の近傍にあり且つ前記目標頂点として当該グラフィパーティション以外の前記複数のグラフパーティションの中の他の１つに含まれる夫々の頂点について、前記目標頂点と当該グラフパーティションとの間のグラフごとの結合を表す前記グラフベース結合値を計算するよう前記グラフベース結合計算部を使用し、前記目標頂点と当該グラフパーティションとの間の利用ごとの結合を表す利用ベース結合値を計算するよう前記利用ベース結合計算部を使用することと、前記グラフベース結合値及び前記利用ベース結合値を結合して全体結合値を計算することと、前記全体結合値が所定の閾値を超える場合は、前記目標頂点を当該グラフパーティションに加え、前記目標頂点をその現在のグラフパーティションから除くこととを含む。頂点をグラフパーティションに加えることは、そのグラフパーティションのバージョンを符号化する各データ部分に頂点のコピーを加えることを含んでよい。
【００３１】
前記グラフベース結合値は、データグラフ自体から導き出せる情報に基づき計算され、グラフの構造特性に制限されてよい。前記利用ベース結合値は、他方で、グラフトラバーサルルート及びデータアクセスイベントのようなデータアクセス統計値の記録から導き出せる情報に基づき計算される。
【００３２】
有利に、上記のパーティション境界更新モジュールは、一緒にクエリされると期待され得る頂点を同じグループにまとめ、従って、パーティションをまたぐグラフトラバーサルに付随する処理のオーバヘッドを減らすために、データグラフ自体の構造特性と、データグラフにおいてどこでデータアクセスイベントが起こったかの記録とを結合するメカニズムを提供する。
【００３３】
如何にしてグラフベース結合値が計算され得るかの例として、１又はそれ以上の中心頂点までの最短経路が考慮に入れられてよい。なお、中心頂点は、本明細書で論じられている手段のいずれかによって決定されている。特定の例では、前記グラフベース結合値は、グラフパーティションにおける夫々の中心頂点について、前記中心頂点から当該グラフパーティションの辺での頂点の夫々への最短経路の中で最長の長さの割合としての、前記目標頂点から前記中心頂点への最短経路の長さに基づく。
【００３４】
有利に、かかる技術は、グラフパーティションの現在の境界を考慮に入れ、事実上新しい境界頂点の候補である目標頂点を現在の境界と比較する。
【００３５】
他方で、前記利用ベース結合値は、データグラフの構造特性に基づかず、データアクセスイベント、具体的に、クエリに対する結果として返された頂点によって定義されるトラバーサル経路に基づく。利用ベース結合値の特定の例として、該利用ベース結合値は、グラフパーティションと重なり合うグラフトラバーサル経路の総数の、該グラフトラバーサル経路において前記目標頂点を含んだ被選択時間期間に対する割合に基づく。グラフトラバーサル経路は、接続された頂点及び接続された頂点を接続する辺の連続であり、該連続は、アクセス要求を処理するデータアクセスモジュールの結果としてアクセスされる。つまり、前記利用ベース結合値は、グラフパーティションから結果を返した被選択時間期間におけるデータグラフへのクエリのうちの幾つがクエリ結果として目標頂点を返したかを示す。
【００３６】
有利に、前記利用ベース結合値は、グラフパーティション間の境界がどこに起こるかを決定する場合にグラフの利用を考慮に入れるメカニズムを提供し、一般に同じクエリにおいてアクセスされる頂点を一緒に記憶することを好む。
【００３７】
前記利用ベース結合値を計算する場合に、被選択時間期間において起こる全てのグラフトラバーサルは等しい重み付けを与えられ得る。代替的に、より最近のグラフトラバーサルは、より高い重み付けを与えられてよい。例えば、前記計算された利用ベース結合値は、その計算と前記被選択時間期間の終わりとの間の時間に基づき時間減衰係数によって加減されてよい。
【００３８】
有利に、前記利用ベース結合値を時間減衰係数によって加減することは、より大きい有意性を、より最近の計算へ導く。これは、幾つかの実施において、それらがグラフクエリの将来の傾向を示す可能性がより高いためである。
【００３９】
パーティション境界を調整するための上記のプロシージャは、特に、グラフパーティションの拡大及び他の縮小をもたらし得る。従って、最大パーティションサイズの制限を実施することが望ましい。これは、もし越えられる場合に、パーティションへの追加のために選択されたあらゆる新しい頂点が、代わりに、オーバーフローデータ部分に置かれるようにする。そのようなポリシーは、次のように実施される。前記目標頂点をグラフパーティションに加えることが、当該グラフパーティションに所定の最大パーティションサイズを超えさせる場合に、新しいデータ部分が、前記目標頂点を符号化するデータと、当該グラフパーティションの中心頂点又は１以上の中心頂点の夫々について、前記中心頂点を符号化するデータ、及び前記目標頂点から前記中心頂点への最短経路上の頂点の夫々を符号化するデータとを有して生成される。
【００４０】
有利に、新しいデータ部分は、グラフパーティション全体を複製しないために空間に関して効率的であり、且つ、目標頂点とともに既存のグラフパーティションからの最も重要な頂点を含むその包含に関して機能的である。最大パーティションサイズを課すことは、結合値の計算におけるバイアス効果が、グラフパーティション間のデータの分配を過剰に非対称とすることを防ぐ。
【００４１】
本発明の他の実施形態は、接続される頂点どうしの間の関係を表す辺によって相互接続される頂点として情報を表すデータグラフを記憶する方法であって、前記データグラフは、複数のグラフパーティションを有し、複数のデータ記憶サーバの間で分散される複数のデータ部分として記憶され、夫々のデータ部分は、前記複数のグラフパーティションの中の１つのバーションを符号化する、方法を含む。当該方法は、２又はそれ以上のデータ部分が前記複数のグラフパーティションの中の同じグラフパーティションのバージョンを夫々符号化する場合に、前記２又はそれ以上のデータ部分を前記複数のデータ記憶サーバの中の異なるデータ記憶サーバに割り当て、前記記憶されたデータグラフのアクセス要求を受け取り、夫々のアクセス要求を満足するようどのグラフパーティションをクエリすべきかを決定し、前記受け取られたアクセス要求を、夫々の決定されたグラフパーティションのバージョンを符号化するデータ部分を記憶するデータ記憶サーバへ分配し、データ部分への受け取られたアクセス要求の分配を表す統計値を記録し、該記録された統計値に応じて前記グラフパーティションの中の１つのバージョンを符号化するデータ部分の数を増減させる。
【００４２】
更に、発明実施形態は、コンピュータ装置の分散ネットワークによって実行される場合に、該コンピュータ装置の分散ネットワークを、本発明を具現する分散型データグラフ記憶システムとして機能させるコンピュータプログラムの組を含んでよい。
【００４３】
更に、本発明の実施形態は、記憶ユニットの分散ネットワークを含むコンピュータ装置のシステムによって実行される場合に、該システムに、本発明を具現する方法を実行させるコンピュータプログラム又はコンピュータプログラムの組を含む。
【００４４】
更なる態様の実施形態は、接続される頂点どうしの間の関係を表す辺によって相互接続される頂点として情報を表し、複数のグラフパーティションを有するデータグラフを記憶するよう構成される分散型データグラフ記憶システムであって、夫々が前記複数のグラフパーティションの中の１つのバーションを符号化する１又はそれ以上のデータ部分を記憶するよう夫々構成される複数のデータ記憶サーバと、パーティション境界更新モジュールと有し、該パーティション境界更新モジュールは、目標頂点とグラフパーティションとの間のグラフごとの結合を表すグラフベース結合値を計算するよう構成されるグラフベース結合計算部と、目標頂点とグラフパーティションとの間の利用ごとの結合を表す利用ベース結合値を計算するよう構成される利用ベース結合計算部とを有し、前記パーティション境界更新モジュールは、前記グラフパーティションの夫々についてパーティション更新を実行するよう構成され、パーティション更新は、当該グラフパーティションの境界頂点の近傍にあり且つ前記目標頂点として当該グラフィパーティション以外の前記複数のグラフパーティションの中の他の１つに含まれる夫々の頂点について、前記目標頂点と当該グラフパーティションとの間のグラフごとの結合を表す前記グラフベース結合値を計算するよう前記グラフベース結合計算部を使用し、前記目標頂点と当該グラフパーティションとの間の利用ごとの結合を表す利用ベース結合値を計算するよう前記利用ベース結合計算部を使用することと、前記グラフベース結合値及び前記利用ベース結合値を結合して全体結合値を計算することと、前記全体結合値が所定の閾値を超える場合は、前記目標頂点を当該グラフパーティションに加え、前記目標頂点をその現在のグラフパーティションから除くこととを有する、分散型データグラフ記憶システムを含む。
【００４５】
更なる態様に従って、前記グラフベース結合値は、グラフパーティションにおける夫々の中心頂点について、前記中心頂点から当該グラフパーティションの辺での頂点の夫々への最短経路の中で最長の長さの割合としての、前記目標頂点から前記中心頂点への最短経路の長さに基づいてよい。
【００４６】
更に、更なる態様において、前記利用ベース結合値は、グラフパーティションと重なり合うグラフトラバーサル経路の総数の、該グラフトラバーサル経路において前記目標頂点を含んだ被選択時間期間に対する割合に基づいてよく、グラフトラバーサル経路は、接続された頂点及び接続された頂点を接続する辺の連続であり、該連続は、アクセス要求を処理するデータアクセスモジュールの結果としてアクセスされる。
【００４７】
任意に、更なる態様において、前記計算された利用ベース結合値は、その計算と前記被選択時間期間の終わりとの間の時間に基づき時間減衰係数によって加減される。
【００４８】
更に、更なる態様において、前記目標頂点をグラフパーティションに加えることが、当該グラフパーティションに所定の最大パーティションサイズを超えさせる場合に、新しいデータ部分が、前記目標頂点を符号化するデータと、当該グラフパーティションの中心頂点又は１以上の中心頂点の夫々について、前記中心頂点を符号化するデータ、及び前記目標頂点から前記中心頂点への最短経路上の頂点の夫々を符号化するデータとを有して生成される。
【発明の効果】
【００４９】
本発明の実施形態によれば、通信ネットワークにわたってグラフ頂点を運ぶ必要性を減らすように、利用パターンに応答するためにデータグラフの物理記憶を調整することができるメカニズムを提供することが可能となる。
【図面の簡単な説明】
【００５０】
【図１】本発明を具現するデータ記憶システムを表す。
【図２】実施形態のシステムアーキテクチャを表す。
【図３】実施形態においてデータ記憶サーバへ分配されるデータ部分を表す。
【発明を実施するための形態】
【００５１】
これより、一例として、添付の図面を参照して実施形態が記載される。
【００５２】
図１は、本発明を具現するデータ記憶システムを表す。コントローラ１００は、データ部分分配コントローラ１０２と、データアクセスモジュール１０４と、グラフパーティション利用モニタ１０６と、境界複製モジュール１０８と、パーティション境界更新モジュール１１０と、グラフベース結合計算部１１２と、利用ベース結合計算部１１４との機能を組み合わせる装置の例として表されている。構成要素１０２乃至１１４の夫々は、機能モジュールと呼ばれることがあり、それらは集合的に機能モジュールと呼ばれることがある。機能モジュールは、必ずしも全てが全ての実施形態に含まれるわけではない。機能モジュール１０２、１０４及び１０６は、機能モジュール１１０、１１２及び１１４から独立して設けられてよく、逆もまた同様である。境界複製モジュール１０８は任意である。機能モジュールは、全てが単一の実施形態にまとめられてよい。
【００５３】
機能モジュールの夫々は、モジュールの機能を実行するよう特に構成されたハードウェアによって実現されてよい。機能モジュールはまた、コンピュータプロセッシングユニットによって実行される場合に、コンピュータプロセッシングユニットに、機能モジュールによって起こる機能性を実行させる命令又は実行可能プログラムコードによって実現されてよい。コンピュータプロセッシングユニットは、機能モジュールによって起こる機能性を実現するために、メモリ、ストレージ、Ｉ／Ｏデバイス、ネットワークインターフェース、センサ（オペレーティングシステムを介するか又は別の方法による。）及びコンピュータデバイスの他の構成要素のうちの１又はそれ以上と連携して動作してよい。モジュールはまた、ユニットとも呼ばれてよく、方法、プログラム又はプロセスのステップ又は段階であってよい。機能モジュールを組み合わせるコントローラ１００の図解は、機能モジュールが組み合わされ得るという事実を例証する。なお、機能モジュールはまた、別個のデバイスによって提供されてよい。
【００５４】
コントローラ１００は、コンピュータデバイス又はサーバのような単一のエンティティによって実現されてよく、あるいは、例えば、制御プロトコルのレイヤとして、協調して動作する１よりも多いコンピュータデバイスによって実現されてよい。従って、夫々の機能モジュールは、複数のコンピュータデバイスに属する構成要素によって実行されてよく、機能モジュールは、１よりも多いコンピュータデバイスによって提供されてよい。
【００５５】
たとえ態様（ソフトウェア／方法／装置）が別個に論じられるとしても、１つの態様に関連して論じられるそれらの特徴及び結果は、等しく他の態様に適用可能であることが理解されるべきである。従って、方法の特徴が論じられる場合に、装置の実施形態が、その特徴を実行するか又は適切な機能性を提供するよう構成されたユニット又は装置を含み、且つ、プログラムが、それらが実行されているコンピュータ装置に上記の方法の特徴を実行させるよう構成されることは、当然のことである。
【００５６】
機能モジュールの夫々は、通信ネットワーク３００を介して、又はコントローラ１００内のデータの交換によって、他の機能モジュールの夫々と、及び通信ネットワーク３００を介してデータ記憶サーバと通信するよう構成される。矢印は、グラフパーティション利用モニタ１０６によってモニタされるように、データアクセスモジュール１０４に到着して、データ記憶サーバ２００へ分配されるアクセス要求の経路を表す。
【００５７】
データグラフは、データ記憶サーバ２００に記憶されるデータのマニフェステーションであり、記憶されているデータを、データ記憶システムの外部及び内部の他のプロセス又はエンティティに及びユーザに表す手段である。データグラフは、トリプル、例えば、ＲＤＦトリプルとして符号化され、リソースは、それがサブジェクトとして指名されるトリプルによって定義されることがある。グラフパーティションは、データグラフのサブセット、又はサブグラフであり、データグラフの部分又は領域である。グラフパーティションは、相互に接続された頂点のみを有してよく、あるいは、互いに接続されていない頂点を有してよい。データ部分は、グラフパーティションの符号化されたバージョンであり、すなわち、それは、グラフパーティションとして表される基礎データである。同じグラフパーティションを符号化する夫々のデータ部分は、互いの複製であってよい。代替的に、同じグラフパーティションを符号化するデータ部分は、互いと異なってよい。例えば、それらは、近傍のグラフパーティションからのどの境界頂点をそれらが符号化するのかに関して、異なってよい。
【００５８】
データグラフを符号化するための記憶されたデータの例となる形は、トリプル、特に、ＲＤＦトリプルである。トリプルは、グラフデータを複数のサブジェクト−プリディケート−オブジェクト表現として特性化することによって、グラフデータを符号化することを提供する。その意味で、サブジェクト及びオブジェクトは、グラフデータのグラフノード／リソースであり、そのようなもとしても、エンティティ、頂点、リソース、インスタンス、又はコンセプトであり、プリディケートは、サブジェクトとオブジェクトとの間の関係の表れである。プリディケートは、オブジェクトへの特定のタイプのリンクを提供することによって、サブジェクトに関する何かをアサートする。例えば、サブジェクトは、ウェブリソースを表してよく（例えば、ＵＲＩを介する。）、プリディケートは、リソースの特定の特質、特性、又は側面を表し、オブジェクトは、その特質、特性、又は側面のインスタンスを表す。つまり、トリプル記述の集合は、有向グラフデータを本質的に表す。ＲＤＦ標準は、そのようなトリプルのための軽視課された構造を提供する。
【００５９】
データ部分分配コントローラ１０２は、グラフパーティションを符号化するデータ部分をデータ記憶サーバ２００へ割り当てることに関与する。特に、データ部分分配コントローラ１０２は、２又はそれ以上のデータ部分が複数のグラフパーティションの中の同じグラフパーティションのバージョンを夫々符号化する場合に、それらの２又はそれ以上のデータ部分を複数のデータ記憶サーバの中の異なるデータ記憶サーバへ割り当てるよう構成される。データ部分分配コントローラは、同じグラフパーティションを符号化するデータ部分が同じデータ記憶サーバ２００に記憶されないために、どのデータ記憶サーバ２００がどのグラフパーティションを符号化するデータ部分を記憶するかのマッピングを保持してよい。
【００６０】
潜在的に不平衡のクエリプロセッシング（グラフパーティションの間で均等に分配されないアクセス要求）を扱うために、複製因子（夫々のグラフパーティションを符号化するデータ部分の数である。）は、異なるグラフパーティションにわたって不均一であってよい。夫々のグラフパーティションを符号化するデータ部分の数は、データ部分分配コントローラ１０２によって決定される。最初に、すなわち、十分なアクセス要求が、グラフパーティションのうちのどれがより頻繁にクエリされるかを観測するよう、データグラフに対してなされる前に、以下のポリシーが、幾つのデータ部分が夫々のグラフパーティションを符号化すべきかを決定するようグラフ特性を利用するために、別々に又は組み合わせて使用され得る：
１．グラフパーティションにおける辺の数を、他のグラフパーティションにおける辺の数と比較すること；及び／又は
２．グラフパーティションにおける頂点の次数（頂点に接続している辺の数）を、他のグラフパーティションにおける頂点の次数と比較すること。
【００６１】
幾つのデータ部分が夫々のグラフパーティションを符号化すべきかを最初に決定するための第１の技術は、次のとおりである：
グラフはＫ個の辺を有するとする。夫々の辺は、クエリされるｐｅｄｇｅ＝α・１／Ｋ＝α・ｐａｖｇの可能性を有する。なお、αは、辺タイプの所定の組からの辺の特性に基づきグラフ辺の有意性を調整するための係数である。例えば、存在論において、セマンティック階層構造を表す辺は、コンセプトの特定の属性を表す辺よりも重要であってよく、従って、より高い値のαを引く。
【００６２】
Ｍ個の又はより少ないデータ記憶サーバ２００の間でのグラフパーティションのバージョンを符号化するデータ部分の最初の割り当てのために、Ｍ個の利用可能なスロットが存在する。任意に、Ｍは、利用に応答して更なるデータ部分を加える余地を残すために、利用可能なスロットの総数よりも小さい値として選択されてよい。簡単のために、グラフパーティションのサイズの違いは無視され、夫々のデータ記憶サーバ２００は単に、グラフパーティションのいずれかを符号化するデータ部分を記憶するのに夫々十分大きい１又はそれ以上のスロットを有する。辺特性に基づきパーティションＰｉのバージョン（Ｐｉの複製因子）を符号化するデータ部分の数（ｎｒｅｐ．ｅｄｇｅ）を計算する式は、次のとおりである：
【数１】
2015225656.tif 000003
【００６３】
データ部分分配コントローラ１０２は、同じグラフパーティションを符号化するデータ部分を異なるデータ記憶サーバ２００へ割り当てるよう構成されるので、この式は、幾つの異なるデータ記憶サーバにグラフパーティションＰｉが記憶されるべきかを計算する技術の例を与える。上記の式で、ｐａｖｇ×ｅｄｇｅ（Ｐｉ）は、Ｐｉにおける辺がクエリされる集計された尤度を与える。トリプルに基づくデータは、複数の辺としてデータグラフを効率的に記憶し、従って、特定のタイプの辺の数及びそれがクエリされる確率は、パーティションがクエリされる全体的な尤度を与えるべきである。ｐａｖｇを設定するテキストは、確率について合計が１に制限されることを強調しなかった。代替的に、以下が、ｐａｖｇ×ｅｄｇｅ（Ｐｉ）の代わりに使用され得る：
【数２】
2015225656.tif 000004
なお、合計は、辺の異なる可能なカテゴリに及ぶ。
【００６４】
Ｍ／ｃａｐａｃｉｔｙ（Ｄ）は単に、幾つかのデータサーバ（Ｄ）がＭ個の利用可能なスロットに必要とされるかを与える。
【００６５】
幾つのデータ部分が夫々のグラフパーティションを符号化すべきかを最初に決定するための第２の技術は、次のとおりである：
パーティションがより高い次数を示す（すなわち、多数の辺を含む）場合に、クエリは、より低い確度を示す場合よりも、このパーティションに対して評価される可能性が高いとする。高い頂点次数は、クエリ経路上にある可能性が高い。パーティションを複数のデータ記憶サーバへ分配することは、グラフパーティションの符号化されたバージョンにアクセスすることができるプロセッシングユニットを有効に増やし、従って、同時のクエリプロセッシングの機会を増やして、このパーティションが性能ボトルネックとなることを防ぐことができる。
【００６６】
１．ｄｅｇ（Ｐ）、Δ（Ｐ）、及びδ（Ｐ）として夫々表されるグラフパーティションの平均次数、最大次数及び最小次数を計算する。
【００６７】
２．ｄｅｇ（Ｇ）及びΔ（Ｇ）として夫々表される原のグラフの平均次数及び最大次数を計算する。
【００６８】
頂点特性に基づきパーティションＰｉのバージョン（Ｐｉの複製因子）を符号化するデータ部分の数（ｎｒｅｐ．ｖｅｒｔｅｘ）を計算する式は、次のとおりである：
【数３】
2015225656.tif 000005
【００６９】
この式は、高い次数を有する頂点を含むグラフパーティションについて、より高い複製因子を好むと解釈され得る。夫々の因子によって起こる正確な重み付けは、システム起動時にデータベース管理者によって調整され得る係数α、β及びγによって調整される。
【００７０】
実際に、両技術は、最初に夫々のグラフパーティションを符号化すべきデータ部分の実際の数を決定するために組み合わされ得る。代替的に、又は追加的に、他の方策が適用可能であり、頂点の中間を計算し、大部分の最短経路上にあるそれらが同時のアクセスのためにバンド幅を増大させるよう多くのデータノードへ分配されることを確かにすることを含む。
【００７１】
同じグラフパーティションのバージョンを符号化するデータ部分の一貫性は、記憶されているデータへの変更が他の位置で複製され得るために、同じグラフパーティションのバージョンを符号化する他のデータ部分の位置を詳述する夫々のデータ部分とともに制御情報を記憶することによって確かにされ得る。頂点が更新される場合に、それは全ての複製において更新されるべきである。この動作は、データ記憶システムにわたるデータ一貫性を確かにする。
【００７２】
複製因子の最初の計算は、単にグラフ特性（グラフの構造特性）に基づき、データアクセスイベントの実際の分配は、データ部分からのクエリ結果の検索であって、グラフパーティションの複製因子と一致しないことがある。つまり、最も一般的にクエリされるグラフパーティションは、最初の計算の結果として大部分のデータ部分によって符号化されたグラフパーティションでないことがある。結果として、必要とされないグラフパーティションでの同時のデータアクセスのために相対的により広いバンド幅が存在し、必要とされるグラフパーティションでの同時のデータアクセスのために相対的により狭いバンド幅が存在することとなる。
【００７３】
大量に接続され且つ密集したパーティションは、ほとんどクエリを引き込まず、よって、グラフパーティションによって最初に起こる高い複製因子、及びその特定のグラフパーティションへのクエリに対する応答に利用可能な高いバンド幅（多数のプロセッシングユニット）は不要となる。他方で、以前に不十分であると考えられていた（すなわち、低い次数及び比較的少ない辺を有する）グラフパーティションは、頻繁なクエリ実行の的となることができ、よって、グラフパーティションによって最初に起こる低い複製因子、及びその特定のグラフパーティションへのクエリに対する応答に利用可能な低いバンド幅は不要となる。
【００７４】
データ部分分配コントローラ１０２は、グラフパーティションの実際の利用に応答し、グラフパーティションの間のデータアクセスイベントの分配に応じて夫々のグラフパーティションのバージョンを符号化するデータ部分の数を増大させるよう構成される。夫々のグラフパーティションを符号化するデータの部分の原の数（グラフパーティションの複製因子）は、データグラフの構造に基づくものであって、パーティションが最近のクエリにおいて頻繁に使用されている場合に、そのパーティションは概して更なる別個のデータサーバ／ノードに複製されるべきであるとの原理により、パーティションの実際の仕様を反映するよう精緻化される。さもなければ、総数は、記憶空間及びリソースの不必要な消費を回避するよう縮小すべきである。
【００７５】
我々は、どのグラフパーティションについて対応するデータ部分の数を増大させるべきかと、どのグラフパーティションについて対応するデータ部分の数を低減させるべきかとを決定するための技術の例を以下で提示する。
【００７６】
不等式が以下で詳述される。これは、満足される場合に、クエリを満足するグラフパーティションを、対応するデータ部分の数を増大させるための候補として特定し、満足されない場合に、クエリを満足しないグラフパーティションを、対応するデータ部分の数を低減させるための候補として特定する。制御アルゴリズムは、どのグラフパーティションが時間期間を通して不等式を満足するか／満足しないかをモニタリングするために課されてよく、次いで、モニタリングに基づきデータ部分の数の増減を命じる。
【００７７】
データ記憶サーバの並列容量τｄｎ、すなわち、データ記憶サーバによって同時に扱われ得るアクセスの数（同時に到着する幾つのクエリがまとめて扱われ得るか）、データ部分で起こるデータアクセスイベントの数ｑｎｄｒ、データ部分のサイズｓｄｒ、及びデータノードでの異なるデータ複製の総数ｎｄｒ（シグマが合計される。）を考えると、例となる不等式は、次のとおりである：
【数４】
2015225656.tif 000006
【００７８】
代替的に、τｄｎは、問題となっている時間期間においてデータグラフ全体にわたり受け取られるクエリの総数である。データアクセスイベントは、受け取られたアクセス要求データ部分へ向けられることであってよく、あるいは、受け取られたアクセス要求に応答したデータ部分からのデータ項目のリターンであってよい。不等式は、データ部分で起こるデータアクセスイベントの数がサイズ比を超える必要がある量を決定する可変係数αを有する。データ部分によって符号化されるグラフパーティションは、グラフパーティションを符号化するデータ部分の１つ又は所定の割合が不等式を満足する場合に増大の候補と見なされる。アルゴリズムは、不等式を満足するデータ部分がグラフパーティションに起因すると考え、それによって、グラフパーティションの複製因子が増大されるべき場合及びそれが低減されるべき場合を決定するために使用されてよい。
【００７９】
代替的に、関数は、利用をモニタリングするために使用され得、関数が特定の値（上限又は下限）に達する場合に、グラフパーティションの複製因子は増大／低減される（注：値はデータ部分ごとであるから、グラフパーティションに関し、それはデータ部分にわたって合計され、現在の複製因子によって除算されてよい。）：
【数５】
2015225656.tif 000007
【００８０】
故に、クエリ数がサイズ比に比例する場合、結果は１である。α及びβは、ｑｎｄｒ＝０の状況を回避するためにシステム管理者によって調整可能な係数である。αは、非零の正の整数である。故に、グラフパーティションがそのサイズに比例したレートでクエリされる場合、結果は０である。ｑｎｄｒ（ｔ）は、時間窓（ｔ）、例えば、現時点からさかのぼる時間期間にわたるデータ部分でのクエリの数である。
【００８１】
上記の不等式に対する代替の不等式として、以下が使用され得る。グラフパーティションを符号化するデータ部分でのデータアクセスイベントの総数ｑｎｐ、グラフパーティションの複製因子ｒｎｐ、データノードの並列容量τｄｎを考えると、不等式は、次のとおりである：
【数６】
2015225656.tif 000008
【００８２】
グラフパーティションは、そのグラフパーティションを符号化する異なるデータ部分へ分配されるクエリの総数が依然として、データノードでの異なるデータ複製の数に比例してデータノードの並列容量を超える場合に、複製因子を増大させるための候補と見なされることが分かる。
【００８３】
データアクセスモジュール１０４は、プロセッシングのボトルネックを回避するために、グラフパーティションを符号化する複数のデータ部分にわたって等しくグラフパーティションへのアクセス要求をルーティングするよう構成されてよい。
【００８４】
グラフパーティション利用モニタ１０６は、どのデータ部分がロックされているか（すなわち、どのデータ部分が、それに対してルーティングされているが未だ応答していないアクセス要求を有しているか）の記録を保持する。それにより、同じグラフパーティションを符号化する他のデータ部分へのアクセス要求のルーティングが、データアクセスイベントとして記録される。
【００８５】
データ部分分配コントローラ１０２の機能の原理は、上記の不等式の一方又は両方を使用して、不等式を満足したグラフパーティション（すなわち、その対応するデータ部分が不等式を満足している。）を符号化するデータ部分の数を増大させ、且つ、不等式を満足しないグラフパーティションを符号化するデータ部分の数を低減させるようにすることである。
【００８６】
データアクセスモジュール１０４は、記憶されたデータグラフのアクセス要求を受け取り、受け取られたアクセス要求を複数のデータ記憶サーバの間で分配するよう構成される。任意に、データアクセスモジュール１０４は、アクセス要求を受け取り、どのグラフパーティションに要求が関連するかを決定し、受け取られたアクセス要求を、夫々の決定されたグラフパーティションのバージョンを符号化するデータ部分を記憶するデータ記憶サーバへ分配するよう構成されてよい。そのような目的のためのマッピングは、データアクセスモジュール１０４自体に保持されてよく、あるいは、データ部分分配コントローラ１０２のような他のモジュールで保持されるマッピングが利用されてよい。例えば、アクセス要求は、特定の範囲の頂点を特定するクエリ又はレンジクエリであってよく、それにより、その特定の範囲内にあるあらゆる頂点がクエリ結果として返される。あらゆる頂点の位置は、マッピングを使用することによって決定されてよい。
【００８７】
代替的に、データアクセスモジュール１０４は単に、全てのアクセス要求を全てのデータ記憶サーバ２００へ転送してよい。そのような実施形態では、モニタリングされ、且つ、データ部分分配コントローラ１０２によって使用される統計値の基礎をなすデータアクセスイベントは、例えば、特定のデータ記憶サーバ２００から返される結果であってよい。
【００８８】
グラフパーティション利用モニタ１０６は、アクセス要求によって引き起こされるデータアクセスイベントのデータ部分の間の分配を表す統計値を記録するよう構成される。データアクセスイベントは、受け取られたアクセス要求のハンドリングに関連するプロセッシングイベントであり、データ部分の使用を表す、すなわち、データ部分が記憶されるデータ記憶サーバ２００によって実行されている何らかのプロセッシングを伴う。データアクセスイベントは、データ記憶サーバ２００よりむしろ、結果が返されるデータ部分によって起こる。
【００８９】
幾つかの実施形態において、グラフパーティション利用モニタ１０６は、データ部分で起こるデータアクセスイベントに加えて、グラフパーティションの間の受け取られたアクセス要求の分配をモニタリングしてよい。
【００９０】
境界複製モジュール１０８は、夫々のグラフパーティションについて、当該グラフパーティションのバージョンを符号化する夫々のデータ部分へ、当該グラフパーティションの境界頂点の近傍にある各頂点であり且つ当該グラフパーティション以外の他のグラフパーティションに含まれる第１グループの頂点の夫々を符号化するデータのコピーと、第１グループの頂点の近傍にある各頂点であり且つ当該グラフパーティション以外の他のグラフパーティションに含まれる第２グループの頂点の一員と当該グラフパーティションとの間の結合を評価する基準を満足していると前記境界複製モジュールによって決定される、第２グループの頂点の夫々を符号化するデータのコピーを加えるよう構成される。そこまで、境界複製モジュール１０８は、データ部分の夫々の母集団を決定する。
【００９１】
複数のグラフパーティションに及ぶデータを要求するアクセス要求に応答してデータ記憶システムの性能を改善する有効な方法は、境界頂点を複製することである。すなわち、２つのパーティションの境界にある（すなわち、１つのグラフパーティションに含まれるが、他のグラフパーティション内の頂点へ接続された辺を有する）頂点は、両方のグラフパーティションを符号化するデータ部分に含まれる。境界複製モジュール１０８は、どの境界頂点がどのデータ部分において複製されるべきかを決定することに関与する。実際の境界頂点複製メカニズムは、データ構造及び基礎をなす記憶システムのインデックスメカニズムに依存して種々の方法で実現され得る。境界頂点を複製することに加えて、それらの近傍も、データ部分境界にまたがるクエリによって引き起こされる潜在的なネットワークトラフィックを減らすために、他のグラフパーティションを符号化するデータ部分において複製されてよい。
【００９２】
パーティションごとに境界複製モジュール１０８が従うプロシージャの例として、特定のグラフパーティションのバージョンを符号化するデータ部分が近傍のグラフパーティションからの境界頂点（本明細書の別の場所で述べられている第１グループ）を含むのみならず、近傍のグラフパーティションからのそれらの境界頂点の近傍（本明細書の別の場所で述べられている第２グループ）も複製されるかどうかは、次のように決定される：
パーティションＰｉ及びＰｊ並びに複製される境界頂点ｖｂを考えると、任意の頂点ｖｘ∈Ｐｊに関し、＜ｖｂ，ｖｘ＞∈Ｐｊ∧ｂｉｎｄｉｎｇ（ｖｂ，ｖｘ）≧ｔｈの場合に、ｖｘをＰｉに加える。結合関数は、グラフごと及び／又は利用ごとの係数を考慮に入れてよく、結合関数によって生成される値は、所定の閾値と比較される。ｖｂの隣のｖｘに関し、ｖｂとのその結合が所定の閾値を超える場合は、それは複製されて、境界が共有されるグラフパーティションを符号化するデータ部分へ加えられるべきである。
【００９３】
グラフパーティションＰｊからの頂点ｖｘを、他のグラフパーティションＰｉを符号化するデータ部分において複製すべきか否かを決定するための結合値の計算は、種々の方法で実行され得る。例えば、第１のアプローチは、ｖｘの有無による他のグラフパーティションＰｉの範囲を最初に計算することであり、次いで、｛ｖｘ｝を含むＰｉの範囲がｖｘを含まないＰｉの範囲より小さい場合は、ｖｘはＰｉに加えられるべきである（すなわち、Ｐｉのバージョンを符号化するデータ部分はまた、ｖｘを符号化すべきである。）。グラフパーティションＰｊからの頂点ｖｘを、他のグラフパーティションＰｉを符号化するデータ部分において複製すべきか否かを決定するための代替のアプローチは、ｖｘとＰｉの中心頂点との間の平均距離を計算して、計算された平均距離をｖｂと中心との間の平均距離と比較することである。前者が後者よりも短い場合は、ｖｘはＰｉに加えられるべきである（すなわち、Ｐｉのバージョンを符号化するデータ部分はまた、ｖｘを符号化すべきである。）。
【００９４】
複製（他のパーティションのバージョンを符号化するデータ部分における、他のパーティションからの頂点の包含）は、より良い空間効率のために、境界頂点（第１グループ）の直ぐ隣（第２グループ）のみに制限されてよい。
【００９５】
パーティションは、複製された頂点の場所に関する情報を更に記憶すべきである。頂点が複製される場合に、パーティション番号に関する情報（全ての複製はどこにあるか）は、その頂点を含む全てのデータ部分とともに記憶されるべきである。この制御情報は、影響下の頂点への書込動作においてデータ一貫性を維持するのに有用である。
【００９６】
パーティション境界更新モジュール１１０は、頂点の間の結合に基づきグラフパーティションの間の境界への変更を決定するよう構成される。更新が決定されると、パーティション境界更新モジュール１１０は、変更を実現するために、記憶されているデータ部分の更新を命じるよう構成される。パーティション境界更新モジュール１１０は、グラフパーティションを変更すべきか且つ如何にすべきかを決定する際に、構造的要因（データグラフ自体の特性）及び使用要因の両方を考慮に入れるよう構成される。グラフパーティション境界の動的性質、場合により、データグラフ自体への変更は、周期的に更新される必要がある構造的要因の計算をもたらし、あるいは、境界の移動、又は特定のグラフパーティションへの付加される新しい頂点若しくはそのようなグラフパーティションから除去される既存の頂点のような、あるイベントに応答する。
【００９７】
パーティション境界更新モジュール１１０は、グラフベース結合計算部１１２及び利用ベース結合計算部１１４の一方又は両方を有してよい。グラフベース結合計算部１１２は、グラフパーティションの間の境界への変更を決定する際にパーティション境界更新モジュール１１０によって考慮に入れられる構造的要因を表す値を生成するよう構成される、グラフベース結合計算部１１２は、データ部分へアクセスしてグラフパーティションの構造を解析し、代表値を生成するよう構成される。利用ベース結合計算部１１４は、グラフパーティションの間の境界への変更を決定する際にパーティション境界更新モジュール１１０によって考慮に入れられる使用要因を表す値を生成するよう構成される。利用ベース結合計算部１１４は、値を生成するために、グラフパーティション利用モニタ１０６によって生成された統計値にアクセスしてよく、あるいは、統計値自体を生成してよい。
【００９８】
境界への変更を決定することに加えて、パーティション境界更新モジュール１１０は、グラフパーティションの間の境界が最初にデータグラフのどこにあるべきかを決定するよう構成されてよい。
【００９９】
たとえグラフパーティションがＮＰ困難の問題であるとしても、（カットされる辺及び頂点の接近の数として）高いパーティション内結合及び低いパーティション間結合を確かにする点から見て、妥当な品質を有する迅速なパーティションのためのアルゴリズムが存在する。パーティションアルゴリズムを選択する場合に、必要条件は、目標グラフが、辺重みの有無にかかわらず、有向、非周期、且つラベル付きであることである。辺重み、すなわち、経路長さは、辺によって連結されている頂点の間の距離を表すために実施形態で使用されてよい。他の実施形態では、辺は、それらの重み付けに関して一様であってよい（これは、以下で論じられる、辺自体が同次であることとは異なる。）。ＲＤＦグラフは、データフォーマットの例として使用される。ＲＤＦの場合に、辺重みは、データフォーマットにおいて本質的に生成されない。しかし、以下の解決法のうちの１つが、重み付けによりデータ項目に注釈をつけるために使用されてよい。：
−  辺が一様である（すなわち、辺が全て同じラベルを付されている）場合、ＲＤＦ辺ラベルのためにリザーブされる記憶空間は、その辺による長さ値を記憶するために使用され得る；又は
−  長さ値は、辺ラベルへ連結され、計算プロシージャの間に、別個の読出動作によりパースすることで取り出され得る；又は
−非ＲＤＦ構成が使用され得（例えば、ＸＭＬタギングが使用され得）、これは、パーシング及び取り出しのために実行される特定の処理を必要とする；
−  長さ値のような辺属性は、相補存在論的推論及びグラフ解析プロシージャと組み合わせて、特別の相関概念を用いてエミュレートされ得る。
【０１００】
正確なデータフォーマットにかかわりなく、データグラフを分割するための多くのアルゴリズムが適用され得る。例えば、Ｋｅｒｎｉｇｈａｎ−Ｌｉｎアルゴリズム（Ｋｅｒｎｉｇｈａｎ及びＬｉｎ、１９７０年）又はマルチレベルパーティションアルゴリズムは、可能な候補である。
【０１０１】
最初の分割プロセスは、計算上高価であり、グラフが展開されている後の段階では利用可能でないかもしれない計算リソースを用いてオフラインで実行され得る。
【０１０２】
パーティション境界更新モジュール１１０は、グラフＧ＝＜Ｖ，Ｅ＞（グラフは頂点及び辺によって表される。）のパーティションとして結果Ｐｉ＝Ｐ１・・・Ｐｎを生成する最小カットに基づくパーティションアルゴリズムを用いて、最初の分割を実行してよい。アルゴリズムは、データサーバ２００の記憶容量を超えないサイズを有するグラフパーティションを生成するように実施される。実際に、最小パーティションサイズは、２又はそれ以上のパーティションが夫々のデータ記憶サーバ２００で符号化され得るように、記憶容量よりも相当に小さい。例えば、データ記憶サーバ２００は、記憶容量よりも小さい総データサイズを有する１よりも多い符号化されたグラフパーティションを収容してよい（すなわち、Ｓｊ＝Ｓｉ・・・Ｓｍがデータ記憶サーバの番号であるとして、Σｓｉｚｅ（Ｐｉ）≦Σｃａｐａｃｉｔｙ（Ｓｊ））。分散型記憶システムで展開される場合に、データ記憶サーバは、従って、複数の符号化されたグラフパーティション（すなわち、データ部分）を含むことができる。
【０１０３】
最初のパーティションは、パーティション境界アルゴリズムによって生成され、データ部分分配コントローラ１０２によって複数のデータ記憶サーバ２００の間の分散配置のために準備される。
【０１０４】
最初の分割は、単にグラフ特性（グラフの構造特性）に基づき、同じグラフパーティションに強連結な頂点を置くよう意図される境界の設置は、頻繁に一緒にクエリされる頂点を反映しないことがあり、従って、境界をまたぐクエリに関して高い処理費用を生じさせる。これは、例えば、グラフクエリにおいて頻繁に同時発生し、よって、利用に関して強連結を示すグラフ特性に基づき、更に区別して検討される頂点によって、引き起こされ得る。パーティション境界更新モジュール１１０は、利用ごとのパーティション更新を実施し、これは、その場合に、グラフパーティション境界（又はデータ部分境界）をまたいでトラバースするクエリの頻度を減らして、全体的なクエリ品質をより良いものとするようグラフパーティションの間の境界の設置を適応させるために、利用され得る。
【０１０５】
パーティション境界更新モジュール１１０は、頂点のパーティション結合、すなわち、パーティションにおける頂点の構成の強さを表す量、を計算する。パーティション結合を計算するための技術の例は次のとおりであり、グラフベース結合計算部１１２によって計算され得るグラフベース結合値と、利用ベース結合計算部１１４によって計算され得る利用ベース結合値とを含む：
既存のパーティションは中心頂点を有する。パーティションに対する頂点の結合は、そのパーティションの全ての中心頂点に対する頂点の近接中心性として計算される。つまり、それは、パーティションの中心頂点の頂点からの最短距離の長さの和である。
【０１０６】
距離値ｄ（ｖｉ，ｃｉ）は、結合を反映するようグラフパーティションのｃｉの範囲を用いて正規化される。ｒｃｉは、中心ｃｉからグラフパーティションの辺までの最長の最短距離と見なされ得る。
【数７】
2015225656.tif 000009
【０１０７】
全体の結合は、次いで、以下のように、中心頂点ｃｉの夫々にわたってｂｇ値を合計して、中心頂点の数によって除算することで正規化される：
【数８】
2015225656.tif 000010
【０１０８】
この式は、パーティションの（複数の）中心と任意の頂点との間の全長を与え、如何にしてグラフベース結合値が計算され得るかの例である。トポロジー的観点から、この指標は静的である。
【０１０９】
データアクセスモジュール１０４によって受け取られ、記憶されているデータに対して評価されるクエリ（アクセス要求の例）は、グラフトラバーサル経路、つまり、グラフ頂点の連結サブセットを表すと考えられてよい。例えば、グラフパーティション利用モニタ１０６で、グラフトラバーサル経路を記録することによって、どれくらい強く頂点がパーティションに結合されるかの利用ベースの結合指標が計算され得る。利用ベース結合値を計算するための技術の例は、以下の式によって表現される：
【数９】
2015225656.tif 000011
ここで、ｎｑ（ｖ）は、クエリを満足する経路の数であり、他方、クエリ経路上でｖを有し、Ｎｑは、パーティションと重なり合うクエリを満足する経路の総数である。
【０１１０】
利用履歴における所与の時間期間を通して、全体の利用ベース結合値は、全ての関連するクエリにわたって夫々の関連するクエリ（グラフパーティションと重なり合い、グラフパーティションにおいて頂点を含むクエリ結果として少なくとも１つのトラバーサル経路を有するクエリ）のｂｑを合計することで計算される：
【数１０】
2015225656.tif 000012
【０１１１】
任意に、ＢＱが計算される時間が考慮に入れられ、それにより、より最近の計算は、より高い重み付けを与えられる。
【数１１】
2015225656.tif 000013
【０１１２】
クエリのタイミングを考慮に入れる代替の方法として、時間減衰係数が、以下のように、総和において夫々の成分クエリに適用され得る：
【数１２】
2015225656.tif 000014
【０１１３】
頂点とパーティションとの間の全体の結合が次いで、グラフベース結合値及び利用ベース結合値を正規化することで計算され得る。
【０１１４】
パーティション境界更新モジュール１１０は、計算された結合値に基づきグラフパーティションの間の境界を動的に調整するよう構成される。閾境界値を超える結合値（グラフベース結合値及び利用ベース結合値の結合）を有する目標頂点（パーティションとの結合が計算される頂点、例えば、問題となっているグラフパーティションとの境界にある近郷グラフパーティションからの境界頂点）は、グラフパーティションに組み入れられる。閾結合値は、予め決定されてよく、あるいは、現在含まれているグラフパーティションとの目標頂点についての計算された結合値であってよい。
【０１１５】
グラフパーティションがそのサイズ限界に達し、従って、更なる頂点が最大値を超えることなしに加えられ得ない場合、グラフパーティションとの最低結合値を有するグラフパーティション内の頂点は押し出され、その近傍の多くを保持するパーティションへ移動される。代替的に、全ての他のグラフパーティションの中心までの距離が計算されてよく、出されると選択された頂点は、それが中心頂点までの最短距離を有するパーティションへ付加される。グラフパーティションから出された頂点は、新しいパーティションへ付加されてよく、その場合に、それらが加えられるべきグラフパーティションを見つけるための処理が、システムリフレッシング段階で実行される。グラフパーティションから出される頂点は、そのパーティション内の全ての頂点から選択されてよく、あるいは、境界頂点の中から選択されてよい。例えば、グラフパーティションの境界頂点は、グラフパーティションとのそれらの結合値と、除去のために選択された最低のｎ（ｎは１又はそれ以上である。）とに従ってランク付けされ得る。
【０１１６】
グラフパーティション境界調整を調整する上記の技術は、不安定な結果を生み出す可能性がある（幾つかのパーティション及びそれらの複製を他よりも有利なものとし、よって、当該パーティションを、記憶システムによって割り当てられるそれらの最大容量に至らせる。）。従って、最大グラフパーティションサイズが与えられ、最大となるグラフパーティションを処理するための技術が用いられる（最大値は、変数の数、頂点の数、又はグラフパーティションを符号化するデータのサイズであってよい。）。
【０１１７】
グラフ頂点ｖ’に関し、パーティション境界更新モジュール１１０によってそれが付加されるべきであると決定されるグラフパーティションが満杯であり（システムによって予め設定されているその最大容量に達しており）、一方、グラフパーティションのバージョンを符号化するデータ部分を記憶するデータ記憶サーバ又は他のデータ記憶サーバには利用可能なスロットが依然としてある場合は、同じグラフパーティションのバージョンを符号化する新しいデータ部分が、利用可能なデータスロットにおいて生成され得る。新しいデータ部分は、ｖ’からグラフ中心の夫々への最短経路上の全ての頂点を符号化するデータに加えて、目下満杯のグラフパーティションの中心であると見なされる頂点を符号化するデータとともにｖ’を符号化するデータを入れられる。この最初の設定は、新しいデータ部分が適切に接続されているサブグラフを提供し、経路に基づくクエリに既に応答することができるとの考えに基づく。データ記憶システムは、同じグラフパーティションを符号化するデータ部分を予め記憶しているデータ記憶サーバに記憶されている新しいデータ部分に制限されることがある。
【０１１８】
プロシージャの例は、頂点をグラフパーティションへ加えると決定されるが、グラフパーティションが既に最大サイズにあり、グラフパーティションの頂点を符号化するデータ部分を記憶するデータ記憶サーバ２００に利用可能なデータスロットがない場合に従うよう、以下で説明される。そのようなデータ記憶サーバ２００は、それらが、未だ実行されていない計画されたアクティビティを有するので、“膠着状態”にあると見なされてよい。データグラフの分割は、パーティション境界更新モジュール１１０によって周期的にリフレッシュされてよい。リフレッシュはまた、グラフパーティションの閾パーセンテージがそれらの最大サイズに近づくといった、システムイベントに応答することができる。例えば、グラフパーティションのｘ％がそれらの容量の所定パーセンテージ又はその中にある場合（ｘは、設定可能なシステム変数であり、例えば、２０である。）、グラフパーティションの動的な調整は、リフレッシュが実行されるまで一時中断されてよい。
【０１１９】
データ記憶サーバ２００は、夫々がプロセッサ及び記憶ユニットを有し、アクセス要求（例えば、クエリ又は範囲クエリ）を受け取って、要求に一致するか又は要求によって指定される範囲を満足するあらゆるデータ項目によりアクセス要求に応答するよう構成される。夫々のデータ記憶サーバ２００は、１よりも多い同時のアクセス要求を扱うよう構成されてよい。データ記憶サーバ２００は、特定のデータアクセスイベントの同時発生をグラフパーティション利用モニタ１０６に通知し、どのデータ部分によってイベントが起こるべきかを特定するよう構成されてよい。例えば、データアクセスイベントは、アクセス要求に応答してデータ部分からデータ項目を返すこと、データ部分へのアクセス要求を処理すること、データ部分への同時アクセスを処理すること、同時アクセスのためにデータ記憶サーバ２００の容量を超えるデータ部分への多数の同時アクセスを処理することのうちの１又はそれ以上であってよい。
【０１２０】
通信ネットワーク３００は、有線又は無線であってよく、機能モジュール及びデータ記憶サーバ２００が互いと又はそれら自体の間でデータを交換する構成されるための手段である。
【０１２１】
図２は、システムアーキテクチャの例を表す。システムは、通信ネットワーク３００によって相互接続されているデータ記憶サーバ２００の組から成る。図の上にあるレイヤは、記憶サーバ２００及び通信ネットワーク３００によって実現される機能である。図１のコントローラ１００は、データ記憶サーバ２００とは別個のデバイスとして設けられてよく、あるいは、データ記憶サーバのうちの１つによって又は互いと協調して動作する複数のデータ記憶サーバ２００によって実現されてよい。データ記憶サーバ２００の全てが、他のデータ記憶サーバの夫々のアドレスを認識しており、他のサーバと通信するよう構成される。夫々のサーバは、通信レイヤ２４０、記憶レイヤ２３０、グラフ抽象化レイヤ２２０及びＡＰＩレイヤ２１０から成る。
【０１２２】
通信レイヤ２４０は、パーティション及び頂点の複製に必要とされるサーバ間の通信に関与する。
【０１２３】
記憶レイヤ２３０は、永続記憶においてデータパーティションを記憶し、パーティション及び頂点の複製を保持するための全ての制御情報を保持することに関与する。読み出し及び書き込み動作は、上のレイヤから記憶レイヤ２３０へ起こる。
【０１２４】
書き込む動作が、１よりも多いデータ記憶サーバ２００で複製されるグラフ頂点に対して起こる場合、記憶レイヤ２３０は、書き込み動作がその頂点の全ての複製で実行されることを確かにするよう、頂点の残りのコピーの位置を示す制御情報を利用するよう構成される。
【０１２５】
図３に表されるように、特定のグラフパーティション（すなわち、Ｐ２）は、複数のデータ記憶サーバ（サーバ１及びサーバ２）に記憶されるデータ部分において複製され得る。図３はまた、パーティションＰ３及びＰ４の共通部分での境界複製を表す。
【０１２６】
グラフレイヤ２２０は、データ記憶サーバに記憶されている符号化されたデータのグラフ表現の形で、データ記憶サーバにおいてデータ部分内に記憶されたデータの抽象化されたバージョンを提供する。加えて、グラフレイヤ２２０は、データグラフ全体のビューにアクセスするために他のデータ記憶サーバ２００と協調するよう構成される。これは、例えば、データアクセスモジュール１０４と関連する機能を実行する場合に必要とされ得る。
【０１２７】
ＡＰＩレイヤ２１０は、データグラフをクライアントアプリケーションに見せることに関与し、データアクセス要求が受け取られ且つ結果が返されるレイヤである。システムアーキテクチャに依存して、クライアントアプリケーションは、データ記憶サーバ２００のうちの特定の１つへ接続することによって、いずれかのデータ記憶サーバ２００へ接続することによって、又はコントローラ１００へ接続することによって、データグラフにアクセスすることが可能であってよい。例えば、コントローラが、協調して動作するデータ記憶サーバ２００によって実現される場合は、データグラフへのアクセスは、データ記憶サーバ２００自体へ接続することによる。コントローラ１００が別個のデバイスである場合は、データグラフへのアクセスはコントローラ１００を介してのみ可能であってよい。クライアントアプリケーションからの接続がなされると、システムは、全てのサーバにわたって接続を分配することができ、それにより、アクセス要求を処理する負荷は分配され、システムリソースは最適化される。
【０１２８】
上記の態様のいずれにおいても、様々な特徴は、ハードウェアにおいて、あるいは、１又はそれ以上のプロセッサで実行されるソフトウェアモジュールとして、実施されてよい。一態様の特徴は、他の態様のいずれにも適用されてよい。
【０１２９】
本発明はまた、ここで記載される方法のいずれも実行するコンピュータプログラム又はコンピュータプログラムプロダクトと、ここで記載される方法のいずれも実行するコンピュータプログラムを記憶したコンピュータ可読媒体とを提供する。本発明を具現するコンピュータプログラムは、コンピュータ可読媒体に記憶されてよく、あるいは、それは、例えば、インターネットのウェブサイトから提供されるダウンロード可能なデータ信号のような信号の形をとることができ、あるいは、それは、如何なる他の形をとることができる。
【０１３０】
上記の実施形態に加えて、以下の付記を開示する。
（付記１）
接続される頂点どうしの間の関係を表す辺によって相互接続される頂点として情報を表し、複数のグラフパーティションを有するデータグラフを記憶するよう構成される分散型データグラフ記憶システムであって、
夫々が前記複数のグラフパーティションの中の１つのバーションを符号化する１又はそれ以上のデータ部分を記憶するよう夫々構成される複数のデータ記憶サーバと、
２又はそれ以上のデータ部分が前記複数のグラフパーティションの中の同じグラフパーティションのバージョンを夫々符号化する場合に、前記複数のデータ記憶サーバの中の異なるデータ記憶サーバへ前記２又はそれ以上のデータ部分を割り当てるよう構成されるデータ部分分配コントローラと、
前記記憶されたデータグラフのアクセス要求を受け取り、該受け取られたアクセス要求を前記複数のデータ記憶サーバの間で分配するよう構成されるデータアクセスモジュールと、
前記アクセス要求によって引き起こされるデータアクセスイベントの前記データ部分の間の分配を表す統計値を記録するよう構成されるグラフパーティション利用モニタと
を有し、
前記データ部分分配コントローラは、前記記録された統計値に応じて前記グラフパーティションの中の１つのバージョンを符号化する前記データ部分の数を増減させるよう構成される、分散型データグラフ記憶システム。
（付記２）
前記記録された統計値は、時間期間を通じた前記データ部分にわたるデータアクセスイベントの分配と、前記時間期間を通じた前記複数のデータ記憶サーバにわたるデータアクセスイベントの分配とを含み、
前記データ部分分配コントローラは、
データ部分を特定し、該特定されたデータ部分を記憶するデータ記憶サーバでのデータアクセスイベントの数の割合としての前記特定されたデータ部分でのデータイベントの数が、前記特定されたデータ部分を記憶するデータ記憶サーバで記憶されるデータ部分の総サイズの割合としての前記特定されたデータ部分のサイズを閾量よりも多く超えるようにし、且つ
前記特定されたデータ部分によって符号化されるバージョンのグラフパーティションを、そのバージョンを符号化するデータ部分の数を増大させるグラフパーティションとして選択する
ことによって、前記グラフパーティションの中からパーティションを選択し、該選択されたパーティションのバージョンを符号化するデータ部分の数を増大させるよう構成される、
付記１に記載の分散型データグラフ記憶システム。
（付記３）
前記記録された統計値は、前記グラフパーティションにわたるデータアクセスイベントの分配を含み、
前記データ部分分配コントローラは、
グラフパーティションを特定し、該特定されたグラフパーティションを符号化するデータ部分ごとの前記特定されたグラフパーティションでのデータアクセスイベントの数が、前記特定されたグラフパーティションを符号化するデータ部分のサイズによって加減される前記特定されたグラフパーティションを符号化するデータ部分を記憶する１又はそれ以上のデータ記憶サーバでのデータアクセスイベントの総数を閾量よりも多く超えるようにする
ことによって、前記グラフパーティションの中からパーティションを選択し、該選択されたパーティションのバージョンを符号化するデータ部分の数を増大させるよう構成される、
付記１に記載の分散型データグラフ記憶システム。
（付記４）
前記データ部分分配コントローラは更に、前記複数のグラフパーティションの夫々について、当該グラフパーティションの１の特性又は１よりも多い特性の組み合わせに応じて、記憶すべき前記グラフパーティションのバージョンを符号化するデータ部分の数を決定するよう構成され、
前記１又はそれ以上の特性は、
当該グラフパーティションにおける辺の数に比例する第１の値によって測定される第１の特性、及び
前記データグラフにおける頂点の平均及び最大次数と比較される当該グラフパーティションにおける頂点の平均及び最大次数に基づき第２の値によって測定される第２の特性
の少なくともいずれかを含む、
付記１に記載の分散型データグラフ記憶システム。
（付記５）
前記データ部分分配コントローラは、
夫々が関連する係数を有する辺タイプの所定の組の中の１つであると夫々の辺を特定し、
夫々の辺タイプについての、当該辺タイプであると特定された前記グラフパーティションにおける辺の数と前記関連する係数との積を合計することによって、前記第１の値を計算する
よう構成される、付記４に記載の分散型データグラフ記憶システム。
（付記６）
境界複製モジュールを更に有し、該境界複製モジュールは、夫々のグラフパーティションについて、当該グラフパーティションのバージョンを符号化する夫々のデータ部分へ
当該グラフパーティションの境界頂点の近傍にある各頂点であり且つ当該グラフパーティション以外の他のグラフパーティションに含まれる第１グループの頂点の夫々を符号化するデータのコピー、及び
前記第１グループの頂点の近傍にある各頂点であり且つ当該グラフパーティション以外の他のグラフパーティションに含まれる第２グループの頂点の一員と当該グラフパーティションとの間の結合を評価する基準を満足していると前記境界複製モジュールによって決定される、前記第２グループの頂点の夫々を符号化するデータのコピー
を加えるよう構成される、付記１に記載の分散型データグラフ記憶システム。
（付記７）
前記境界複製モジュールは、前記第２グループの頂点の各員について、
当該グラフパーティションと前記第２グループの頂点の一員との和集合の範囲である第１の範囲、及び
当該グラフパーティションの範囲である第２の範囲
を計算するよう構成され、
前記第２グループの頂点の一員は、前記第１の範囲が前記第２の範囲よりも小さい場合に、当該グラフパーティションと前記第２グループの頂点の一員との間の結合を評価する前記基準を満足したと決定される、
付記６に記載の分散型データグラフ記憶システム。
（付記８）
パーティション境界更新モジュールを更に有し、該パーティション境界更新モジュールは、
目標頂点とグラフパーティションとの間のグラフごとの結合を表すグラフベース結合値を計算するよう構成されるグラフベース結合計算部と、
目標頂点とグラフパーティションとの間の利用ごとの結合を表す利用ベース結合値を計算するよう構成される利用ベース結合計算部と
を有し、
前記パーティション境界更新モジュールは、前記グラフパーティションの夫々についてパーティション更新を実行するよう構成され、
パーティション更新は、当該グラフパーティションの境界頂点の近傍にあり且つ前記目標頂点として当該グラフィパーティション以外の前記複数のグラフパーティションの中の他の１つに含まれる夫々の頂点について、
前記目標頂点と当該グラフパーティションとの間のグラフごとの結合を表す前記グラフベース結合値を計算するよう前記グラフベース結合計算部を使用し、前記目標頂点と当該グラフパーティションとの間の利用ごとの結合を表す利用ベース結合値を計算するよう前記利用ベース結合計算部を使用することと、
前記グラフベース結合値及び前記利用ベース結合値を結合して全体結合値を計算することと、
前記全体結合値が所定の閾値を超える場合は、前記目標頂点を当該グラフパーティションに加え、前記目標頂点をその現在のグラフパーティションから除くことと
を含む、付記１に記載の分散型データグラフ記憶システム。
（付記９）
前記グラフベース結合値は、当該グラフパーティションにおける夫々の中心頂点について、前記中心頂点から当該グラフパーティションの辺での頂点の夫々への最短経路の中で最長の長さの割合としての、前記目標頂点から前記中心頂点への最短経路の長さに基づく、
付記８に記載の分散型データグラフ記憶システム。
（付記１０）
前記利用ベース結合値は、当該グラフパーティションと重なり合うグラフトラバーサル経路の総数の、該グラフトラバーサル経路において前記目標頂点を含んだ被選択時間期間に対する割合に基づく、
付記８に記載の分散型データグラフ記憶システム。
（付記１１）
前記計算された利用ベース結合値は、その計算と前記被選択時間期間の終わりとの間の時間に基づき時間減衰係数によって加減される、
付記１０に記載の分散型データグラフ記憶システム。
（付記１２）
前記目標頂点を当該グラフパーティションに加えることが、当該グラフパーティションに所定の最大パーティションサイズを超えさせる場合に、新しいデータ部分が、前記目標頂点を符号化するデータと、当該グラフパーティションの中心頂点又は１以上の中心頂点の夫々について、前記中心頂点を符号化するデータ、及び前記目標頂点から前記中心頂点への最短経路上の頂点の夫々を符号化するデータとを有して生成される、
付記１１に記載の分散型データグラフ記憶システム。
（付記１３）
接続される頂点どうしの間の関係を表す辺によって相互接続される頂点として情報を表すデータグラフを記憶する方法であって、前記データグラフは、複数のグラフパーティションを有し、複数のデータ記憶サーバの間で分散される複数のデータ部分として記憶され、夫々のデータ部分は、前記複数のグラフパーティションの中の１つのバーションを符号化し、２又はそれ以上のデータ部分が前記複数のグラフパーティションの中の同じグラフパーティションのバージョンを夫々符号化する場合に、前記２又はそれ以上のデータ部分は、前記複数のデータ記憶サーバの中の異なるデータ記憶サーバに記憶される、方法において、
前記記憶されたデータグラフのアクセス要求を受け取り、
前記受け取られたアクセス要求を前記複数のデータ記憶サーバの間で分配し、
前記アクセス要求によって引き起こされるデータアクセスイベントの前記データ部分の間の分配を表す統計値を記録し、
前記記録された統計値に応じて前記グラフパーティションの中の１又はそれ以上のバージョンを符号化する前記データ部分の数を増減させる、方法。
（付記１４）
コンピュータによって実行される場合に、該コンピュータに、接続される頂点どうしの間の関係を表す辺によって相互接続される頂点として情報を表すデータグラフを記憶するプロセスを実行させるコンピュータプログラムであって、前記データグラフは、複数のグラフパーティションを有し、複数のデータ記憶サーバの間で分散される複数のデータ部分として記憶され、夫々のデータ部分は、前記複数のグラフパーティションの中の１つのバーションを符号化し、２又はそれ以上のデータ部分が前記複数のグラフパーティションの中の同じグラフパーティションのバージョンを夫々符号化する場合に、前記２又はそれ以上のデータ部分は、前記複数のデータ記憶サーバの中の異なるデータ記憶サーバに記憶される、コンピュータプログラムにおいて、
前記プロセスは、
前記記憶されたデータグラフのアクセス要求を受け取るステップと、
前記受け取られたアクセス要求を前記複数のデータ記憶サーバの間で分配するステップと、
前記アクセス要求によって引き起こされるデータアクセスイベントの前記データ部分の間の分配を表す統計値を記録するステップと、
前記記録された統計値に応じて前記グラフパーティションの中の１又はそれ以上のバージョンを符号化する前記データ部分の数を増減させるステップと
を有する、コンピュータプログラム。
【符号の説明】
【０１３１】
１００  コントローラ
１０２  データ部分分配コントローラ
１０４  データアクセスモジュール
１０６  グラフパーティション利用モニタ
１０８  境界複製モジュール
１１０  パーティション境界更新モジュール
１１２  グラフベース結合計算部
１１４  利用ベース結合計算部
２００  データ記憶サーバ
３００  通信ネットワーク
【図１】
2015225656.tif 000015
【図２】
2015225656.tif 000016
【図３】
2015225656.tif 000017