(57)【要約】【課題】  調整処理を実行する方法、制御部、プログラム及びデータ記憶システムを提供する。【解決手段】  データのグラフ内にノードとして表されたリソースの調整を実行する方法、プログラム及びデータ記憶システムであって、特定ノードとの調整処理が実行されるべき、前記グラフ内のノードの初期サブセットを選択するステップ、前記特定ノードと前記初期サブセットの各ノードとの間で調整処理を実行するステップ、前記特定ノードと、前記特定ノードとの調整が実行されるべき前記グラフのノードの更なるサブセットとの間の調整処理を遅延するステップ、を有する。【選択図】  図４
2013257874.tif 000002
【特許請求の範囲】
【請求項１】
データのグラフ内にノードとして表されたリソースの調整を実行する方法であって、
前記方法は、
特定ノードとの調整処理が実行されるべき、前記グラフ内のノードの初期サブセットを選択するステップ、
前記特定ノードと前記初期サブセットの各ノードとの間で調整処理を実行するステップ、
前記特定ノードと、前記特定ノードとの調整が実行されるべき前記グラフのノードの更なるサブセットとの間の調整処理を遅延するステップ、
を有する方法。
【請求項２】
前記初期サブセットを選択するステップは、グラフトラバース動作においてどのノードが該ノードへの最多アクセス回数を有するかを決定するステップ、及び該ノードを最も訪問されたノードとして前記初期サブセットに含めるステップ、を有する、請求項１に記載の方法。
【請求項３】
前記初期サブセットを選択するステップは、グラフトラバース動作において、最も訪問されたノードのうちの１つの後の次のノードとして、どのノードが該ノードへのリードアクセスを有する最も高い確率を有するかを決定するステップを更に有する、請求項２に記載の方法。
【請求項４】
ノードの前記更なるサブセットは、前記初期サブセットのメンバでない前記グラフ内の全てのノードである、請求項１乃至３のいずれか一項に記載の方法。
【請求項５】
ノードの前記更なるサブセットの調整処理は、遅延され、コンピューティングリソースの監視が該コンピューティングリソースはアイドルであると示すタイムスロット中に十こうされる、請求項１乃至４のいずれか一項に記載の方法。
【請求項６】
前記特定ノードの識別情報をリストに追加するステップ、
前記特定ノードの識別情報が前記リストから削除されると直ぐに、前記グラフのノードの前記更なるサブセットとの処理が実行されるまで、前記リスト内に前記特定ノードの識別情報を維持するステップ、
前記グラフへのクエリが受信されると、リードされるべき１又は複数のノードを識別し、該リードされるべき１又は複数のノードのうちのどれが前記リストで識別されるかを調べ、前記リストで識別された前記リードされるべき１又は複数のノードのうちの各々について、前記グラフの各ノードとの調整処理を実行するステップ、
を更に有する請求項１乃至５のいずれか一項に記載の方法。
【請求項７】
調整処理が実行される前記初期サブセットに含まれない前記グラフの各ノードについて、前記特定ノードの識別情報を関連するメタデータ内の未調整ノードのリストに追加し、前記特定ノードの識別情報が前記リストから削除されると直ぐに、前記特定ノードとの処理が実行されるまで、前記リスト内に前記識別情報を維持するステップ、
前記グラフへのクエリが受信されると、リードされるべき１又は複数のノードを識別し、該リードされるべきノードの各々について、該ノードと前記関連するメタデータ内の未調整ノードのリスト内で識別された各ノードとの間で調整処理を実行するステップ、
を更に有する請求項１乃至６のいずれか一項に記載の方法。
【請求項８】
前記グラフは、コンピューティングリソースの分散型ネットワークに格納される、請求項１乃至７のいずれか一項に記載の方法。
【請求項９】
前記特定ノードの別のノードとの調整処理は、
複数の異なる類似性計算を実行した結果生じる値を集約することにより、類似性値を得るか、又は１つの類似性計算を実行した結果生じる単一の値を得るステップであって、類似性計算は、前記特定ノード及び前記別のノードが意味的に等価である可能性を表す値を生成する計算である、ステップ、
前記類似性値が所定の類似性閾を超える場合、前記特定ノードと前記別のノードとの間の等価関係を示す等価リンクを前記グラフに追加するステップ、
を有する、請求項１乃至８のいずれか一項に記載の方法。
【請求項１０】
調整処理は、前記コンピューティングリソースの分散型ネットワーク内の１より多いコンピューティングリソースで同時に、前記特定ノードと、該コンピューティングリソースに格納され且つ前記特定ノードとの調整処理が実行されているノードのサブセットに属するノードとの間で、実行される、請求項８又は９に記載の方法。
【請求項１１】
各ノードについて、関連するメタデータとして、グラフトラバース動作でノードへのリードアクセス回数を表す値、及び前記グラフ内でノードがリンク付けされた各ノードがグラフトラバース動作で次のノードとしてリードされた回数を表す値を格納するステップ、
を更に有する、請求項１乃至１０のいずれか一項に記載の方法。
【請求項１２】
前記グラフ内のデータは、それぞれ主語、述語及び目的語を有するトリプルとしてエンコードされ、前記グラフ内のノードは、トリプルの主語及び述語であり、トリプルの述語は、該トリプルの主語と目的語との間のリンクを示す、請求項１乃至１１のいずれか一項に記載の方法。
【請求項１３】
データのグラフ内にノードとして表されたリソースの調整を実行するデータベース制御部であって、
前記データベース制御部は、
特定ノードとの調整処理が実行されるべき、前記グラフ内のノードの初期サブセットを選択するよう構成される選択モジュール、
前記特定ノードと前記初期サブセットの各ノードとの間で調整処理を実行するよう構成される調整処理モジュール、
前記特定ノードとの調整が実行されるべき前記グラフのノードの更なるサブセットの調整処理を遅延するよう構成される調整処理制御モジュール、
を有するデータベース制御部。
【請求項１４】
リソースがグラフのノードとして表されるデータの該グラフを格納するデータ記憶システムであって、前記データ記憶システムは、
それぞれ前記データのグラフからのデータのセグメントを格納するよう構成される複数の記憶ユニット、
請求項１３に記載のデータベース制御部、
を有するデータ記憶システム。
【請求項１５】
コンピュータにより実行されると、前記コンピュータに請求項１乃至１２のいずれか一項に記載の方法を実行させ、又は前記コンピュータを請求項１３に記載のデータベース制御部として動作させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ記憶及び関連する処理の分野に関する。具体的には、本発明の実施形態は、データセットのグラフ表現においてリソースを処理する調整の実行に関する。調整処理は、グラフ内で意味的に対応するリソース間の異質性を調整することを目的とする。
【背景技術】
【０００２】
膨大な量の利用可能なグラフデータは、統計的傾向を明らかにするだけでなく、隠れたパターンを発見し、データから知識を引き出すことができる自動又は半自動分析の可能性を生み出す。形式意味論は、自動コンピュータ集約的タスクにおいて主要な役割を果たす。どのように意味論が最適に捕らえられるかについて長い戦いが続いているが、どのように人間が世界を（エンティティを有するオントロジ及びエンティティ間の関係として）知覚するかをエミュレートするためにグラフ及びグラフに似た表現が最適な道具であると広く考えられている。
【０００３】
したがって、グラフデータベースは、膨大な構造化及び非構造化データを格納できる知識表現に基づく「意味ネットワーク」を本来表すという利点を提供する。
【０００４】
グラフデータベースは、エンティティを表すためにノード及びエッジ（又はアーク）を用い、該エンティティ間の関係を表すためにノード間のアークを用いるデータ表現である。グラフデータベースは、概して２つの主なカテゴリに分類できる広範な種類の異なるアプリケーションで用いられる。第１の種類は、知的意思決定支援及び自己学習のようなコンセプト記述子の大規模な集合体（「知識ベースアプリケーション」と称される）を有する複雑な知識ベースシステムを有する。第２の種類は、社会的データ及びビジネスインテリジェンスのようなトランザクションデータに対するグラフ分析の実行を含むアプリケーション（「トランザクションデータアプリケーション」と称される）を有する。
【０００５】
形式化されたグラフデータベースの中心にあるのは、データの意味的マークアップを提供する簡易なグラフベースのデータモデリング言語であるＲＤＦ（Resource  Description  Framework）である。ＲＤＦでは、データサイロ（silos）は、一緒に断片化されることから開始でき、現在の群データランドスケープは、接続されたデータグラフに変換され、その上に複雑なデータ分析及びビジネスインテリジェンスアプリケーションが構築される。
【０００６】
データセットは、通常、非常に異質であり且つ分散している。このようなデータの集中的でない特性は、多くの場合、多くのデータソースが同じ現実世界オブジェクトを示すために異なる参照を用いるという問題を生じる。利用可能なグラフデータを効率的に利用するために必要且つ重要なステップは、意味的一致のために複数の参照を識別し調整することである。以下では、用語「調整（reconciliation）」は、意味的に互いに対応するリソース間の等価なリンクを識別し及び定めることにより、（データのグラフにおけるノードのような、例えばＲＤＦトリプルの主語若しくは目的語のような）リソース間の異質性を調整する処理を示すために用いられる。したがって、「調整処理」は、調整を達成するためのプロセッサによるアルゴリズム及び命令の実行ということになる。
【０００７】
データ調整で重要なことは、明白さである。データ調整は、異質なデータセットがリンク付けされるとき（データの意味的多様性を生じる）、データ完全性を保証する。さもなければ、有意義な分析は実行できない。一方で、等価は、アプリケーションを互いに協調できるようにする。したがって、アプリケーション間の通信は、自動化されコンピュータに委任できる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
調整処理を実行する方法、制御部、プログラム及びデータ記憶システムを提供する。
【課題を解決するための手段】
【０００９】
本発明の実施形態は、データのグラフ内にノードとして表されたリソースの調整を実行する方法を提供する。前記方法は、特定ノードとの調整処理が実行されるべき、前記グラフ内のノードの初期サブセットを選択するステップ、前記特定ノードと前記初期サブセットの各ノードとの間で調整処理を実行するステップ、前記特定ノードと、前記特定ノードとの調整が実行されるべき前記グラフのノードの更なるサブセットとの間の調整処理を遅延するステップ、を有する。
【００１０】
等価リンクは、グラフの作成中又は作成後に生成され得る。既存の調整処理では、等価リンクを発見する処理は、データセット全体に対して同時に（単一ルーチンで）実行される。これは、大容量データ（莫大な数のノード）を検討する場合に非効率さの重大な原因になり得る。調整は、複雑で、退屈な、時間の掛かる処理であるとともに、概して高価である。調整アルゴリズムは、相当時間の掛かるコンピュータ的に集中的な動作を実行する場合が多い。これは、真に複雑なタスク、並びに最大性能及び拡張性を得るためのデータ要件に最適なコンピューティングアーキテクチャの効率的利用のための実際の適用への多くの課題を提起する。利用可能なデータ量は増大しているので、調整されるべき利用可能なデータ量は、既存のアプローチやツールにより管理できない場合が多い。膨大な量のデータを調整可能にするために、サーバは拡張性の課題に焦点を当てることが望ましい。
【００１１】
グラフ内のデータは、特に「接続されたデータ」、「グラフデータ」、「リンク付けされたデータ」又は「関連するデータ」と表されても良い。これらは全て、グラフの概念的構造をアークにより相互接続された複数のノードとして反映することを意図している。特定の実装では、グラフ内のデータは、ＬＯＤ（Open  Linked  Data）イニシアチブの一部として提供されるデータにおけるような「リンク付けされたデータ」であっても良い。しかしながら、本発明の実施形態は、このような実装に限定されず、用語「リンク付けされたデータ」は、ＬＯＤイニシアチブの一部として提供されるデータのみではなく更に広義に解釈される。
【００１２】
必ずしも単一ルーチン内に全てではないが調整処理が実行される処理を提供することにより、拡張性が可能になる。つまり、特定の調整処理は、新しいノードのグラフへの追加で、又は主語としてのノードを有する（トリプルのような）新しいデータアイテムの追加で実行され得る、しかし、調整処理は、必ずしもグラフ内のノードのセット全体、単にサブセットとではない。初期サブセットの大きさは、グラフの大きさが増大するとき必ずしも増大しないので、初期調整処理のために必要な処理は、グラフの成長につれて実現不可能にならない。
【００１３】
さらに、１回又は１ルーチンでグラフ全体に対する調整処理を実行する要求を減少させることにより、新しいノードの調整処理により引き起こされるボトルネックが軽減される。これは、全体としてシステム性能を向上させ、システム性能への悪影響を心配することなくシステムオペレータがより複雑な、場合によってはより効率的な調整アルゴリズムへ向かうのを可能にする。
【００１４】
リソースの調整は、互いに意味的に対応する（グラフ内のノードにより表される）リソースを識別し、それらの間の等価リンクを生成することにより、グラフ内のリソース間の異質性を調整する処理であっても良い。例えば、異なる名称を有する２つのリソースが同じ現実世界オブジェクトを参照する場合（つまり、２つのリソースは意味的等価／意味において等価である）、グラフに２つのリソースが等価であることを示すリンクを追加することが適切だろう。リソースの調整は、リソース（グラフノードはリソースである）間に等価性が存在する場所を識別するステップ、等価性の指示をグラフに追加するステップを有しても良い。複数のリソース及び同じ現実世界エンティティの表現の識別は、オントロジマッピング、オントロジマッチング又はオントロジアライメントとしても知られている。
【００１５】
リソースは、ＵＲＩにより参照可能なウェブリソースであっても良く、グラフ内のデータにより記述されているエンティティの表現（記述）であっても良い。特定のエンティティは、１又は複数のリソースにより表現されても良い。
【００１６】
調整処理を遅延するステップは、リソース間の意味的等価性を識別する処理の実行を停止するステップ、該意味的等価性を示すリンクをグラフに追加するステップ、該処理を再開する前に、トリガイベントの所定のセットのうちの１つのトリガイベント又はシステム内のコンピューティングリソースの（使用／負荷のような）状態に応答してタスクスケジューラにより行われる決定を待機するステップ、を有しても良い。
【００１７】
本発明の実施形態では、前記初期サブセットを選択するステップは、グラフトラバース動作においてどのノードが該ノードへの最多アクセス回数を有するかを決定するステップ、及び外ノードを最も訪問されたノードとして前記初期サブセットに含めるステップ、を有しても良い。
【００１８】
初期サブセットの大きさは、システム管理者により制御可能であっても良く、又は予め設定されても良く、例えば設定されたノード数若しくは設定されたグラフ内のノード割合であっても良い。グラフトラバース動作は、特定の方法でグラフノードを訪問する／リードするステップを有し、訪問方法がトラバースアルゴリズムの効率に影響し得る場合、最終的に全てのノードが訪問され得る。有利なことに、初期サブセットの中の最も訪問されたノードを選択することにより、調整処理は、特定ノードと最もクエリされる可能性の高いノードとの間で完了する。したがって、グラフへのクエリの一部としてのノードリードは、グラフ内の他のノードとの調整処理を実行させる。
【００１９】
さらに、前記初期サブセットを選択するステップは、グラフトラバース動作において、最も訪問されたノードのうちの１つの後の次のノードとして、どのノードが該ノードへのリードアクセスを有する最も高い確率を有するかを決定するステップを更に有しても良い。
【００２０】
有利なことに、この特定の方法では、最も訪問されたノードとの共起は、初期サブセットの￥内の選択の基礎として用いられる。これは、クエリされたときに調整処理を高い割合の他のノードと実行させるノードの範囲を拡張する。この拡張は、ノードへのリードアクセスが行われるメカニズムに好意的な方法にされる。グラフトラバース動作で最も訪問されたノードのうちの１つの後に訪問される可能性の最も高いノードを識別するために共起関連付けルールを用いることにより、最も訪問されたノードに対して実行された調整処理は、初期サブセットの一部として、識別されたノードに対しても実行できる（伝搬される）。
【００２１】
代替の実施形態では、グラフトラバース動作において、最も訪問されたノードのうちの１つの後の次のノードとして、該ノードへのリードアクセスを有する最も高い確率を有するノードは、調整処理が遅延される更なるサブセットとして識別されても良い。例えば、更なるサブセットは、それぞれ、グラフトラバース動作において、最も訪問されたノードのうちの１つの後の次のノードとして、該ノードへのリードアクセスを有するある範囲の確率を有するノードと関連付けられても良く、ノードは、前記確率に依存して更なるサブセットに割り当てることができる。
【００２２】
あるとき又は他のときに、各ノードが自身と各他のノードとの間で調整処理を実行させなければならないと決定される実装では、ノードの更なるサブセットは、初期サブセットのメンバではないグラフ内の全てのノードである。しかしながら、ノードの更なるサブセットは、必ずしも全てが自身及び特定ノードとの調整を単一ルーチンで実行させなくても良く、追加の更なるサブセットに分けられ、各追加の更なるサブセットに対する調整処理の間で遅延を有しても良い。
【００２３】
各ノードと各他のノードとの間で調整処理を実行することは、グラフ内のデータを利用又は分析する幾つかのアプリケーションが互いに協調することを可能にし、それらの間の通信を実現するので、望ましい。例えば、データ収穫者は、潜在的に終わりのないデータのウェブを通じてナビゲートするために、調整処理により生成された等価リンクを辿ることができる。
【００２４】
任意的に、ノードの前記更なるサブセットの調整処理は、遅延され、コンピューティングリソースの監視が該コンピューティングリソースはアイドルであると示すタイムスロット中に十こうされても良い。
【００２５】
調整処理は、単にシステムアイドル時間に実行されても良い。任意的に、特定ノードの初期サブセットとの調整処理はグラフ内のイベントにより決定される時間、例えば（ＲＤＦトリプルのような）新しいデータアイテムのグラフへの挿入のときに実行されても良く、更なるサブセットと特定ノードとの間の調整処理は、システムアイドル時間まで遅延されても良い。システムアイドル時間は、ここでは、調整処理を担うリソースにおいて、調整処理により化される余分な処理負荷のための能力がある動作状態の範囲の便利な表記法として用いられる。例えば、更なるサブセットの調整処理は、プロセッサにおいて他の保留中タスクが無いとき、該プロセッサにより実行されても良い。このような決定は、（調整処理制御モジュールの機能を有する）中央負荷スケジューラにより又はプロセッサ自身によりローカルに行われても良い。つまり、特定ノードとノードの更なるサブセットとの間の調整処理を実行するときの決定は、該処理を実行する責任のあるコンピューティングリソースの動作状態に依存して行われても良い。
【００２６】
本発明を実施する方法は、前記特定ノードの識別情報をリストに追加するステップ、前記特定ノードの識別情報が前記リストから削除されると直ぐに、前記グラフのノードの前記更なるサブセットとの処理が実行されるまで、前記リスト内に前記特定ノードの識別情報を維持するステップ、前記グラフへのクエリが受信されると、リードされるべき１又は複数のノードを識別し、該リードされるべき１又は複数のノードのうちのどれが前記リストで識別されるかを調べ、前記リストで識別された前記リードされるべき１又は複数のノードのうちの各々について、前記グラフの各ノードとの調整処理を実行するステップ、を更に有しても良い。
【００２７】
このようなリストは、中央で、（調整処理制御モジュールのような）調整制御部の機能を有するエンティティにより、又はシステム制御部により、維持され得る。代替として、リストは、分散型アーキテクチャ内で実現され、互いに協働する分散型システムの１より多いノードにより実現されても良い。幾つかの実装では、望ましくは、調整処理は、クエリに対する応答の一部として返される前に、又はクエリに対する応答の一部としてリードされる前に、特定ノードに対して完了しても良い。有利なことに、完全な調整処理（つまり、グラフ内の各他のノードとの調整処理）が未だ実行されていないノードのリストを維持することは、クエリに対する応答を返す前に実行される必要のある調整処理の識別を容易にする。リストにあるノードの識別情報は、例えば名称又はＵＲＩであっても良い。特定ノードの識別情報は、実装に依存してノードの更なるサブセットとの調整処理が開始され又は完了されるまで、リストに維持されても良い。
【００２８】
追加又は代替として、調整処理が実行される前記初期サブセットに含まれない前記グラフの各ノードについて、本発明を実施する方法は、前記特定ノードの識別情報を関連するメタデータ内の未調整ノードのリストに追加し、前記特定ノードの識別情報が前記リストから削除されると直ぐに、前記特定ノードとの処理が実行されるまで、前記リスト内に前記識別情報を維持するステップ、前記グラフへのクエリが受信されると、リードされるべき１又は複数のノードを識別し、該リードされるべきノードの各々について、該ノードと前記関連するメタデータ内の未調整ノードのリスト内で識別された各ノードとの間で調整処理を実行するステップ、を更に有しても良い。
【００２９】
各ノードが関連するメタデータを有する実装がある。関連するメタデータは、ノードに格納されても良く、該ノードからリンク付けされた場所に格納され若しくは該ノードの識別情報に基づき場所を特定できても良い。各ノードは、自身の個々の関連するメタデータを有する。メタデータは、ノードの初期サブセットと調整されたが（＝それらの間で調整処理が実行されている且つ）質問内のノードとは未調整のノードのリストを有しても良い。有利なことに、これは、ノードで利用可能な又はノードから直接アクセス可能な情報に基づきノードの更なるサブセットとのローカルに実行されるべき調整処理の制御を可能にする。
【００３０】
本発明の実施形態では必須ではないが、実装は、前記グラフがコンピューティングリソースの分散型ネットワークに格納されるシステムを有しても良い。コンピューティングリソース（記憶ノード）の分散型ノードネットワークは、互いに通信する１より多い異なる記憶ユニットのシステムを有しても良い。例示的な通信パラダイムはピアツーピア（Ｐ２Ｐ）である。したがって、コンピューティングリソースの分散型ネットワークは記憶ノードのピアツーピアネットワークであっても良い。Ｐ２Ｐは、タスク又は負荷をピア間に区分する分散アーキテクチャである。ピア（個々の記憶ノード又はプロセス）は、等価な特権を有し、アプリケーション内で等しい力を有する参加者である。各ピアは、処理能力、ディスクストレージ又はネットワーク帯域幅のようなそれ自体のリソースの一部を、サーバ又は安定したホストによる集中的強調の必要無しに、他のネットワーク参加者に直接利用可能にするよう構成される。ピアは、リソースの供給者及び消費者の両方であると考えられ、サーバが供給しクライアントが消費するという従来のクライアント−サーバモデルとは対照的である。有利なことに、Ｐ２Ｐは、対数的な通信コストでメッセージを交換する記憶ノードの大規模なグループを維持できる。
【００３１】
２ノード間で調整を実行する実際の処理の観点から、本発明の実施形態では、前記特定ノードの別のノードとの調整処理は、複数の異なる類似性計算を実行した結果生じる値を集約することにより、類似性値を得るか、又は１つの類似性計算を実行した結果生じる単一の値を得るステップであって、類似性計算は、前記特定ノード及び前記別のノードが意味的に等価である可能性を表す値を生成する計算である、ステップ、前記類似性値が所定の類似性閾を超える場合、前記特定ノードと前記別のノードとの間の等価関係を示す等価リンクを前記グラフに追加するステップ、を有しても良い。
【００３２】
有利なことに、本発明の実施形態は、特定ノードに対する全ての調整処理を一度に又は単一ルーチンで実行する要求を低減する。本発明の実施形態で用いられる調整処理の増加的アプローチの追加の柔軟性により、より堅牢なアルゴリズム又はアルゴリズムのセットが、全体のシステム性能に悪影響を与えることなく、調整処理自体で利用できる。この目的のために、本発明の実施形態は、それぞれ類似性値を与える複数のアルゴリズムを実行し、又は１つの類似性値を与える単一の堅牢なアルゴリズムを実行し、閾と比較する全体の類似性値を得るためにこれらの値を集約しても良い。各アルゴリズム（又は類似性計算）は、２ノードが意味的に等価か否かとしてＹｅｓ／Ｎｏ（１／０）を与える。閾は、実行された類似性計算の総数から求められた「Ｙｅｓ」の結果の割合である。代替として、類似性計算の数の加重平均は、類似性値を得るために用いられても良い。
【００３３】
本発明の実施形態が実施される方法に依存して、調整処理は、前記コンピューティングリソースの分散型ネットワーク内の１より多いコンピューティングリソースで同時に、前記特定ノードと、該コンピューティングリソースに格納され且つ前記特定ノードとの調整処理が実行されているノードのサブセットに属するノードとの間で、実行されても良い。
【００３４】
データのグラフを格納するために用いられ得るような分散型記憶システムは、それらの特性によりデータにセグメント化を課す。有利なことに、本発明の実施形態は、各コンピューティングリソースで調整処理を実行することにより、特定ノードに対する並列調整を実行することにより、このセグメント化を活用する。各コンピューティングリソースは、特定ノードと該コンピューティングリソースに格納されたグラフノードとの間のノードの記憶のために用いられる。データの特定の直交セグメント化が実行され、各コンピューティングリソースが特定ノードと該コンピューティングリソースに格納された各ノードとの間の調整処理を１つのルーチンで実行せず、例えばグラフトラバース動作でノードが訪問される頻度に基づきノードを分けるようにしても良い。この直交セグメント化は、並列処理実装に更なる柔軟性を提供する。特定ノードと初期サブセットとの間の調整処理は集中型で実行され、次に特定ノードと更なるサブセットとの間の調整処理が、ローカルに実行され及び場合によってはスケジューリングされても良い。
【００３５】
本発明の実施形態は、ノード毎に格納されたメタデータとしての特定の統計／値／特性／パラメータ／測定値の記憶を介して拡張され又は提供されるそれらの機能を有しても良い。本発明の実施形態は、各ノードについて、関連するメタデータとして、グラフトラバース動作でノードへのリードアクセス回数を表す値、及び前記グラフ内でノードがリンク付けされた各ノードがグラフトラバース動作で次のノードとしてリードされた回数を表す値を格納するステップ、を更に有しても良い。
【００３６】
本発明の実施形態では、知識、事実及び／又はステートメントは、ノード及びエッジのグラフにより表される。ここで、ノードは記述される又は表されるエンティティであり、エッジは該エンティティ間の関係である。本発明の実施形態は、グラフデータを直接、つまりノード及びエッジとして、格納するよう構成されても良い。しかしながら、特定の他の基礎的データ構造が用いられても良い。
【００３７】
例示的な基礎的データ記憶構造として、前記グラフ内のデータは、それぞれ主語、述語及び目的語を有するトリプルとしてエンコードされ、前記グラフ内のノードは、トリプルの主語及び述語であり、トリプルの述語は、該トリプルの主語と目的語との間のリンクを示しても良い。
【００３８】
任意で、トリプルは、ＲＤＦ（Resource  Description  Framework）トリプルであっても良い。本願明細書を通じて、「ＲＤＦトリプル」への特定の参照が行われるとき、それはＲＤＦ標準に準拠するトリプルの例示的形式であることが理解されるべきである。さらに、「トリプル」への参照は、問題のトリプルがＲＤＦトリプルである可能性を有する。同様に、本願明細書のいずれかの箇所で議論されるＲＤＦプロセッサは、ＡＰＩラッパと格納されたデータアイテムとの間の相互作用のために用いられるプロセッサの例である。
【００３９】
ＲＤＦ（Resource  Description  Framework）は、概念記述又は意味ネットワークの標準である情報のモデル化のための一般的方法である。意味ネットワークにおける情報のモデル化の標準化は、共通の意味ネットワークで動作するアプリケーション間の相互接続性を可能にする。ＲＤＦは、ＲＤＦスキーマ（ＲＤＦＳ）をＲＤＦ内の語彙を記述するための言語として提供することにより、一義的な形式意味論と共に語彙を保持する。
【００４０】
任意で、トリプルの１又は複数の要素のうちの各々は（要素は、述語、目的語又は主語である）、ＵＲＩ（Uniform  Resource  Identifier）である。ＲＤＦ及び他のトリプルの形式は、識別するものの概念（つまり、オブジェクト、リソース又はインスタンス）を前提として、ＵＲＩのようなウェブ識別子を用い、それら識別される「もの」を簡易な特性及び特性値の観点で記述する。トリプルの観点では、そのトリプルのウェブリソースの具体化において、主語はエンティティを記述するウェブリソースを特定するＵＲＩであっても良く、述語は特性の種類（例えば、色）を特定するＵＲＩであっても良く、目的語は問題のエンティティに起因する特性の種類の特定のインスタンスを指定するＵＲＩであっても良い。ＵＲＩの使用は、トリプルに、個々の特性及び値と同様に、リソースを表すノード及びアークのグラフのようなリソースに関する簡易なステートメントを表すことを可能にする。ＲＤＦグラフは、SPARQLプロトコル及びＲＤＦクエリ言語（SPARQL）を用いて問い合わせることができる。SPARQLは、World  Wide  Web  ConsortiumのRDF  Data  Access  Working  Group  (DAWG)により標準化され、主要なセマンティックウェブ技術と考えられている。SPARQLは、クエリがトリプルのパターン、連結、分離、任意のパターンを有することを許容する。
【００４１】
トリプルは、グラフデータを複数の主語−述語−目的語の表現として特徴付けることにより、グラフデータのエンコードを提供する。この文脈では、主語及び述語は、グラフデータのグラフノードであり、オブジェクト、インスタンス又はコンセプトのようなエンティティであり、述語は、主語と目的語の間の関係の表現である。述語は、目的語への特定の種類のリンクを提供することにより、主語に関する何かを断言する。例えば、主語は、（例えば、ＵＲＩを介して）ウェブリソースを示しても良く、述語はリソースの個々の特性、特徴又は状況を示し、目的語は、該特性、特徴又は状況のインスタンスを示す。言い換えると、トリプルステートメントの集合は、元来、方向性グラフデータを表す。ＲＤＦ標準は、このようなトリプルの形式化された構造を提供する。
【００４２】
ノードとノードの初期サブセットとの間の調整処理は、新しいトリプルのグラフへのエントリにより開始されても良い。さらに、新しいトリプルの主語それ自体が新しいか（この場合には、調整処理は該「特定ノード」に対して開始される）、否か（この場合には、調整処理は必要ないと決定される）を条件としても良い。
【００４３】
本発明の特定の態様の実施形態は、データのグラフ内にノードとして表されたリソースの調整を実行するデータベース制御部を提供する。前記データベース制御部は、特定ノードとの調整処理が実行されるべき、前記グラフ内のノードの初期サブセットを選択するよう構成される選択モジュール、前記特定ノードと前記初期サブセットの各ノードとの間で調整処理を実行するよう構成される調整処理モジュール、前記特定ノードとの調整が実行されるべき前記グラフのノードの更なるサブセットの調整処理を遅延するよう構成される調整処理制御モジュール、を有する。
【００４４】
データベース制御部は、単一のコンピューティングリソースにある中央制御部として、協力する複数のコンピューティングリソースによる中央制御部として、又は分散型記憶システム内のそれぞれ個々のコンピューティングリソースにある複数の等価な制御部の中の制御部として実現され得る。例えば、データベース制御部は、ノードの分散型ノードネットワーク内のコンピューティングリソースで実行するプログラムにより提供されても良く、１又は複数の他のコンピューティングリソースも等価なプログラムを実行し、データベースが複数のデータベース制御部を介してアクセス可能になるようにしても良い。
【００４５】
本発明の他の態様の実施形態は、リソースがグラフのノードとして表されるデータの該グラフを格納するデータ記憶システムを提供する。前記データ記憶システムは、それぞれ前記データのグラフからのデータのセグメントを格納するよう構成される複数の記憶ユニット、上述の及び／又はその他の場合の本発明の実施形態としてのデータベース制御部、を有する。勿論、データ記憶ユニットは、コンピューティングリソースの例であり、記憶に加えて処理機能及び制御／管理機能を有しても良い。
【００４６】
記憶ユニットは、それぞれ、コンピューティングリソースであっても良い。例えば、それらは、それぞれ、プロセッサ、メモリ及び／又はネットワークインタフェースカード、マザーボード、入力／出力装置のような追加構成要素に加えて、記憶ユニットを有しても良い。
【００４７】
本発明の別の態様の実施形態は、コンピュータにより実行されると、前記コンピュータに本発明を実施する方法を実行させる、コンピュータプログラムが提供される。さらに、本発明の別の態様の実施形態は、１又は複数のコンピュータにより実行されると、前記１又は複数のコンピュータを本発明を実施するデータベース制御部として機能させる、コンピュータプログラムが提供される。本発明を実施するコンピュータプログラムは、非一時的記憶媒体のようなコンピュータ可読記憶媒体に格納されても良く、単一のコンピュータプログラム若しくはサブプログラムのスーツとして提供されても良い。
【００４８】
本発明の実施形態は、調整のコンピュータ的労力を低減する、処理を小さいチャンクに分解して調整タスクの良好なスケジューリングを可能にする、分散型データ記憶を活用してデータの直交セグメント化を可能にし並列性能を向上し及び拡張性を向上させる、複数の類似性測定の同時に且つ分散したコンピュータリソースでの実行を可能にする、調整を実行する確率モデルにより導かれる、という有利な効果のうちの１又は複数を有する調整処理を実行するアプローチを実施する。
【図面の簡単な説明】
【００４９】
本発明の好適な特徴は、単なる例として添付の図面を参照して以下に説明される。
【図１】本発明を具現化するデータ記憶システムのサーバに展開されるソフトウェアの概略図である。
【図２】制御機能の部分が集中化される、本発明の一実施形態のシステムアーキテクチャを示す。
【図３】本発明の一実施形態における、基礎的データ記憶に新しいトリプルを追加する際に実行される処理を示すフローチャートである。
【図４】本発明の一実施形態における、拡張グラフを更新し調整処理を実行する際に実行される処理を示すフローチャートである。
【図５】本発明の一実施形態における、調整処理を実行する例示的な処理を示すフローチャートである。
【図６】本発明の一実施形態における、クエリを受信し処理する例示的な処理を示すフローチャートである。
【図７】本発明の一実施形態における、ノードの包括的調整を実行する例示的な処理を示すフローチャートである。
【図８】本発明の一実施形態における、「オンノード」調整処理を実行する例示的な処理を示すフローチャートである。
【図９】調整処理の並列化の概念的説明である。
【図１０】データの物理的分布により及びメタデータとして格納された値を用いることにより可能になるデータのセグメント化の概念的説明である。
【発明を実施するための形態】
【００５０】
図１は、各サーバ１０に展開されるソフトウェアのアーキテクチャを示す。この特定の例では、記憶システムは、メッセージ通過システムを通じて通信するサーバのセットを有する。図１に示した例では、サーバは、各レイヤが下位のレイヤの機能を活用し及び用いるマルチレイヤモデルを実装する。アーキテクチャは、最上位のものから、セマンティックレイヤ１１、ＲＤＦレイヤ１２、トリプルアダプタレイヤ１４、ＫＶＳレイヤ１５、通信レイヤ１６を有し、障害検出部１３は、トリプルアダプタレイヤ１４及びＫＶＳレイヤ１５と平行して動作する。勿論、以下の説明で明らかになるように、本願明細書で議論する実施形態は、ＲＤＦトリプルをデータのグラフを格納するための基礎的データ構造として用いる。これは、決して本発明の実施形態で用いることができる唯一の基礎的データ構造ではなく、本発明の実施形態の例示的な実行を表現する目的でここで選択されただけである。さらに、ＫＶＳ（Key  Value  Store）フォーマットが用いられる。ＫＶＳフォーマットでは、ＲＤＦトリプル自体が、関連付けられた値の記憶において（メタデータを含む）更なるデータにアクセスするためのキーとして用いられる。再び、ＫＶＳフォーマットは、本発明の実施形態の例示的な実装を表現する目的で選択されたものであり、当業者には、本発明の実施形態がこの特定のフォーマットに限定されないことが明らかである。
【００５１】
以下の段落で、各レイヤの役割及びそれらの相互作用を説明する。
【００５２】
（１）セマンティックレイヤ：セマンティックレイヤ１１は、エンドユーザと相互作用するクライアントアプリケーションとのインタフェースであり、ユーザクエリをＲＤＦプロセッサへ中継するよう構成される。このレイヤで、データは、個々のＲＤＦトリプルとしてではなく、概念的レベルで又はモデルレベルで（関連するＲＤＦトリプルのグループとして）見られる。データ調整処理及び特性のトラバース（property  traversal）のような意味的処理動作がこのレイヤで実行される。ルールに基づく推論及び推論に基づく決定ロジックのような更に高度なオントロジ分析も、深い意味解析が必要なとき、有効にされ得る。例示的な実装では、高レベルな推論は、Jena及びOWL２  RL/RDFを通じて実現できる。しかしながら、セマンティックレイヤ２２は、特定の実装に限られず、他の推論エンジンを簡単にプラグインすることもできる。セマンティックレイヤ１１は、本願明細書の他の場所で言及される選択モジュール、調整処理モジュール、及び調整処理制御モジュールの制御機能を提供する。
【００５３】
（２）ＲＤＦレイヤ：ＲＤＦレイヤ１２は、基礎的データレイヤとセマンティックレイヤをブリッジする。これは、Jena  Graph  APIのようなＡＰＩで実装できる。ＲＤＦレイヤ１２は、トリプルと直接連動する方法を用いるよう構成される、例えば、RDF  SPARQLクエリを用いてトリプルを追加／削除する及びトリプルを読み出す。また、ＲＤＦレイヤ１２は、SPARQLエンジンであり、テキストベースのクエリを動作セットに変換することを担う。これらの動作は、特に、低レベルの検索動作、フィルタリング及び参加メカニズムを含む。これらの機能のうちの幾つかはこのレイヤのSPARQLエンジン内に実装され、一方で、低レベルのデータ検索は、下にあるトリプルアダプタレイヤ１４により実現される。
【００５４】
（３）トリプルアダプタレイヤ：トリプルアダプタレイヤ１４は、トリプルを、ＫＶＳレイヤ１５に格納できるキーに変換することを担う。このキーは、一意であるべきであり、複数のキーに対する順序を補足するために（該順序では、各キーはトリプルから生成された任意の他のキーより高い又は低い又はそれと等しい）、他のキーと比較可能であっても良い。トリプルアダプタレイヤ１４は、上位レイヤに３つの単純な動作を提供する。つまり、新しいトリプルを追加する、既存のトリプルを削除する、及び特定の基準に従ってトリプルのセットを発見する。発見（find）動作は、ＲＤＦ特有であり、特定の値又はヌル（null）であり得る３つのパラメータを受信する。例えば、find（subject;null;null）は、特定の（定められた）主語（subject）を有する全てのトリプルを返す。このレイヤは、データを格納し、削除し及びクエリするために下にあるＫＶＳインタフェースを用いる。
【００５５】
（４）ＫＶＳレイヤ：ＫＶＳレイヤ１５は、分散型の順序付きキー値記憶を実装する。これは、キー値ペアを追加し、キー値（所与の特定のキー）をゲット若しくは削除し、更には順序付きＫＶＳに渡り範囲クエリを実行する規則的に順序付けられたハッシュマップインタフェースを提供する。範囲クエリメソッドは、プレフィックス最小キー及びプレフィックス最大キーを受け、所与の範囲内に含まれる全てのキー値ペアに渡るイテレータ（iterator）を返す。このレイヤは、他のサーバからのデータの配分及び検索を担う。このレイヤは、メッセージを渡すことにより他のサーバと通信するために、下にある通信レイヤ１６を用いる。
【００５６】
（５）障害検出部：障害検出部１３は、サーバ障害を検出し、残りの（障害のない）サーバを記憶レイヤに通知するウォッチドックの実行を担う。また、これは、他のサーバ間でメッセージを交換し及びシステムビューとも呼ばれる生きているプロセッサのセットを生成するために通信レイヤ１６を用いる。このビューが変化するとき、ＫＶＳレイヤ１５は通知されるので、例えば障害からの復旧をトリガできる。障害検出部１３は、本発明の実施形態の文脈では非常に任意的であり、本発明の実施形態の機能を格納する機能を提供する。
【００５７】
（６）通信レイヤ：通信レイヤ１６は、メッセージがサーバ（本願明細書の別の場所で言及される記憶ユニット又はコンピューティング装置の例）間で渡されるメカニズムである。例えば、通信レイヤ１６は、他のサーバへ／からメッセージを送信及び受信するためにプリミティブ（primitive）をエクスポートするよう構成されても良い。熟練した読者は、多くの代替の実装をこの目的のために用いることができることを理解するだろう。
【００５８】
図２は、クライアントアプリケーション３０が単一の中央の接点と中央ＰＤＦプロセッサ２２を介して通信する代替のアーキテクチャを示す。ＲＤＦプロセッサ２２は、ＲＤＦレイヤ１２の機能を有するが、図２の例では、ローカルレベルではなく集中型で実装される。調整プロセッサ２１は（調整プロセッサ２１は、本願明細書の別の場所で言及される選択モジュール、調整処理モジュール、及び調整処理制御モジュールの機能を結合する）、図２の例における中央レベルで実装される。調整プロセッサ２１は、複数のデータ記憶ユニット２３に格納されたグラフに対し調整処理を制御し及び実行するよう構成される。複数のデータ記憶ユニット２３は、少なくとも、データのグラフのセグメントを格納するよう構成される。さらに、データ記憶ユニット２３は、上述のトリプルアダプタレイヤ１４、ＫＶＳレイヤ１５、通信レイヤ１６、及び障害検出部１３のうちの１又は複数の機能を実行するよう構成されても良い。図１及び２は、実施形態が実装されるシステムの要件に依存して、ローカルレベル又は中央レベルで実行できる、本発明の実施形態の種々の機能を示す。
【００５９】
ＫＶＳは、図１の例示的な実施形態で、ＲＤＦデータ記憶を拡大縮小する（scale-out）アプローチ、つまり所謂データのグラフの格納として用いられる。しかしながら、ＲＤＦトリプル自体は、ＫＶＳの準備ができていない。第１のステップは、標準ＫＶＳが好都合に用いるキー値タプルを定めることである。以下では、データの分散型格納（グラフ）のための例示的な形式化データ構造を説明する。
【００６０】
定義１：ＲＤＦトリプル。
【００６１】
ＲＤＦトリプルt,<s,p,o>（ＳＰＯと表される）は、主語（ｓ）と目的語（ｏ）との間の関係を定める。関係は、述語（ｐ）を用いて表される。主語（ｓ）及び目的語（ｏ）は、両方ともグラフ内のノードであり、述語はアークである。
【００６２】
トリプルは、ＲＤＦにおける基本的データ構造である。したがって、トリプルは、本発明の実施形態において、（グラフの格納された形式を取り得る）グラフデータベースを格納するための例示的な基礎的データ構造である。しかしながら、本発明は、ＲＤＦトリプル以外の基礎的データ構造が用いられる実施形態にも具現化され又は適用できる。また、トリプルの目的語は、他のトリプルの主語になることができ、又はストリング、整数等のような具体的なデータ型であり得る。グラフは、ＲＤＦトリプルの自然な表現である。ＲＤＦグラフは、有向性のラベル付けされたグラフである。グラフの頂点（ノード）は、トリプルの主語又は目的語であり、エッジは述語である。ＲＤＦグラフでは、ノード及びエッジは両方ともＲＤＦリソースとして参照される。
【００６３】
定義２：ＲＤＦグラフ。
【００６４】
ＴをＲＤＦトリプルのセットとする。Ｔのグラフ表現はG=<V,E>である。ここで、次式の通りである。
【数１】
2013257874.tif 000003
【数２】
2013257874.tif 000004
Ｖは、ＲＤＦトリプルの主語及び目的語としてのノード（又は頂点）のセットとして定められる。一方、Ｅは、通常、ノード対
【数３】
2013257874.tif 000005
として指定されるノード間のエッジ（又はアーク）のセットである。
【００６５】
一般的に、ＫＶＳは、スキーマレスデータを格納することを可能にする非関係型データモデルである。
【００６６】
ＫＶＳのキーの利点は、簡易性及び拡張性である。ＫＶＳのデータアイテムは、キー値タプル<k,v>である。ここで、kはユニークな識別子であり、vはkが識別するペイロードである。
【００６７】
定義３：トリプル化されたＫ／Ｖ（キー値）タプル。
【００６８】
トリプルｔが与えられると、トリプル化されたＫ／Ｖタプルは、次式の通りである。
【数４】
2013257874.tif 000006
【００６９】
ここで、メタデータは、トリプルメタデータをキー値タプルの値として格納する。
【００７０】
本発明の実施形態の基礎的データフォーマットとしてのトリプルの格納の一例として、形式ＳＰＯの各トリプルは、<p,o,s>（ＰＯＳと表す）及び<o,s,p>（ＯＳＰと表す）の形式の２つの意味的に同一だがシンタックス的に異なる変形を生成することにより複製される。
【００７１】
これは、クエリ実行及び障害復旧の検討のもと、本発明の特定の実施形態で用いられる種々の形式のメタデータを格納するメカニズムを提供することを目的とする。
【００７２】
ＲＤＦデータを問い合わせることは、通常、範囲クエリを介して行われ、トリプル内の要素をワイルドカードで置き換える。
【００７３】
例えばSELECT<?,?,?>は、データ記憶内の全てのトリプルを検索し、一方で、SELECT<?,?,o>は、目的語としてｏを有する全てのトリプルを返す。トリプルを複製することは、主語だけでなく述語及び目的語にも従ってデータを格納することを可能にするこれは、クエリの実行を拡張する。
【００７４】
この特定の実装では、トリプルは分散したＫＶＳに格納され、各トリプル及びその変形はキーとして、関連するメタデータは値として格納される。このようなアプローチは、柔軟なメタデータモデル化及び管理を実現する。本願明細書で前述したように、任意の他のグラフに基づく記憶が用いられても良い。望ましくは、本発明の実施形態は、メタデータがグラフに基づく記憶を介して格納され及びアクセスされ得るように実装される。本発明の実施形態では、メタデータは、以下に説明するように、ノードの訪問頻度及びノード対の共起を記録するために用いられても良い。また、メタデータは、どのグラフノードをノードの初期サブセットに含めるか、及び特定のノードを有する調整処理を遅らせることができるかを選択するために用いられる。
【００７５】
形式ＳＰＯの元のトリプル並びに形式ＰＯＳ及びＯＳＰのそれらの変形の両方のセットは、格納され、ｎ個のセグメントに分けられる。ここで、ｎは、データを格納するために用いられるサーバ（又は記憶ユニット）の数であり、各サーバは１つのデータセグメントに関与する。ハッシュ関数が、データのセグメントをサーバにマッピングするために用いられても良い。
【００７６】
特定のトリプル又はその変形の１つが置かれるべきセグメントの位置を効率的に特定するために、Trie（インデックス付けされるべきストリングのサイズに結合した検索の複雑性を有するソート木）を用いることができる。ここで、Trieの各々の葉はデータセグメントに対応する。例えば、データアイテムからサーバへの２段階のマッピングを実施できる。全ての既存のトリプルは、トリプルセット全体がアルファベット順に並べられたTrieを用いて整理され格納される。次に、Trie内の各ノードに関連付けられたプレフィックに従うことにより、正しいデータセグメントの発見が行われる。セグメントＩＤを検索した後、コンシステントハッシングは、セグメントをサーバマシンにマッピングするツールとして用いることができる。２つのマッピングを一緒につなげると、各トリプル、宛先記憶マシンを見付けることができる関数（γ）は、γ＝consistent-hashing(trie-search(t))）の実装で、γ：t→IDmachine。この関数は、Trie構造を用いてデータアイテムをセグメントＩＤ（segment  ID）にマッピングし、次にセグメントＩＤはコンシステントハッシングを用いてマシンＩＤ（machine  ID）にマッピングされる。この方法は、以下の段落に記載するように、全てのトリプルバージョンを格納するために用いられる。
【００７７】
トリプルの追加は、順序付けられたデータ空間内のデータセグメントの位置を特定するステップ、及び（γ()マッピングを用いて）キー値タプルを対応するマシンに挿入するステップを含む。トリプルの挿入のための例示的なアルゴリズムを、以下のAlgorithm１で詳述する。
【数５】
2013257874.tif 000007
【００７８】
記憶マシンに渡される引数は、トリプル又はトリプルの変形、並びに障害復旧のためのサーバローカル記憶インデックステーブルに保持される（変形のための）関連マシンの識別子（m１、m２、m３）を含む。これらのプロシジャは、プレフィックスとしてトリプルデータのサブセットの任意の組合せを用いた範囲クエリを可能にするように、各トリプル、つまりＳＰＯ、ＰＯＳ及びＯＳＰがシステムに格納されることを保証する。
【００７９】
トリプルの位置を特定するメカニズムは、検索及び削除と同じである。データは常に順序付けられるので、ＲＤＦ範囲クエリを処理するために必要なセグメントＩＤを検索することが可能である。定義５は、どのようにこの特定の実装で範囲クエリが実行され得るかを説明する。
【００８０】
定義４：範囲クエリ。
【００８１】
２つのトリプルｔ１及びｔ２並びにデータセグメントＤ０，．．．，Ｄｎが与えられると、範囲クエリは、次のように、ｔ１とｔ２との間の全てのトリプルを包括的に検索する。
【数６】
2013257874.tif 000008
【００８２】
ここで、key()は、トリプルをＫＶＳ内のキーに変換する。
【００８３】
訪問される必要のあるセグメントは、ｔ１を含むセグメント、ｔ２を含むセグメント、及び全ての中間にあるセグメントである。
【００８４】
削除動作は、各サーバで、Algorithm１の「store」命令を「delete」で置き換えることにより同様に処理される。「delete」命令は、トリプルに対応する行を削除し、必要な場合に個々のインデックステーブルを更新する。
【００８５】
本発明の実施形態の調整の付加的なアプローチは、「イベント駆動型の」方法で実施されても良い。イベントは、「何か」がデータ記憶の状態を変更するときに（例えば、新しいトリプルが挿入される、又は既存のトリプルが検索される）生じる。ここで、データ記憶はグラフの格納されたバージョンである。データ調整の目的で、２つの例示的なイベントを、調整処理をトリガし得る関連イベントとして検討する。つまり、addEvent及びreadEventである。addEventは、トリプル挿入動作により発せられる。readEventは、グラフをクエリすることにより発せられる。調整は、これら２つのイベントに対する反応としてトリガされる。データ調整に影響を与え得る他の種類のイベントは、addEvent及びreadEventのシリーズとして表現でき、したがって別個に定められない。勿論、addEvent及びreadEventは非常に関連が深い。トリプルを空でないグラフに追加するとき、関連するトリプルが訪問され、調整されるべきデータを検出するために評価され、readEventのシリーズをデータ記憶に発行させる。このような密接な関係は、以下に説明する特定のノードを有する調整処理を実行すべき初期のノードサブセットを選択する例示的な方法で反映される。readEventは、グラフトラバース動作と考えられる。トラバース履歴は、最も訪問されたノード及び最も訪問されたノードとの強い共起関係を有するノードを含む初期サブセットを確立するために用いられる。初期サブセットを選択するアルゴリズムは、初期サブセットを選択する例示的なメカニズムであり、２つのノードが強く相関している（つまり、グラフトラバース動作においてノードＡを訪問した後にノードＢを訪問する確率が非常に高い）場合、Ａに実行された調整処理が、遅延されるのではなく同じルーチンで、Ｂにも実行されるべきである可能性が高いという仮定に基づく。共起関係を用いたこのような相関するノードの経路に従うと、他のノードよりも調整が差し迫っているノードの初期サブセットが選択できる。
【００８６】
このような選択メカニズムの好ましさは明らかである。グラフが複数のサーバに渡って格納される場合でも、個々のマシンにあるデータのサイズは、場合によっては非常に大きく、リアルタイムの包括的調整動作ができない。２個の任意のノード間の共起確率は、グラフを頻繁に訪問されたノード及び最も頻繁に訪問されたノードとの強い相関を有するノードのサブグラフ、並びに余り訪問されていないノードを含むサブグラフ（更なるサブセット）に区分するために用いることができる。後者では、調整のチェックは、直接リード動作が実行されるまで延期される。したがって、付加的なアプローチは、大規模データグラフに関する調整のために有効である。
【００８７】
グラフを初期サブセット及び更なるサブセットに区分することにより、物理的なデータセグメント化が既に適当な位置にあると、グラフデータのセグメント化をオーバレイすることも可能である。この使用に基づくセグメント化は、データ調整の並列処理を更に向上させる。
【００８８】
本発明の実施形態は、以下に詳述する幾つかの特定のメタデータフィールド／値により拡張された拡張グラフを用い又は作成しても良い。特定のメタデータフィールドは、ノードの初期サブセットをノードの更なるサブセットから区別するのに用いることができる情報を提供する。
【００８９】
定義５：拡張ＲＤＦグラフ。
【００９０】
拡張ＲＤＦグラフは、Ge=<V',E'>である。これは、ＲＤＦグラフG=<V,E>を次式のノード及びエッジメタデータで拡張する。
【数７】
2013257874.tif 000009
【００９１】
ここで、V及びEは、定義２：ＲＤＦグラフで定めた通りである。
【００９２】
トリプルは、この特定の実装において基礎的データ構造として扱われ、上述の拡張ＲＤＦグラフは、ノードローカル及びエッジローカルメタデータを必要とする。この実装は各トリプルの３個の変形を格納するので、メタデータは次のように格納できる。
【００９３】
・ノード及びエッジメタデータを格納する：myは、それぞれトリプルの主語及びトリプルの目的語を表すノードの各ＳＰＯ及びＯＳＰトリプルにローカルに格納される。meは、各ＰＳＯにローカルに格納される。既存のトリプルのメタデータの更新は、トリプルのメタデータをリードし、値を再計算し、及び値を元に戻すステップを含む。
【００９４】
・ノード及びエッジメタデータをクエリする：特定のノード又はエッジに関するメタデータをクエリするとき、全ての関連するトリプルが検索され、メタデータは適切に集約される。
【００９５】
例えば、特定のトリプルが何回リードされるかの指示は、単純なキー値タプル<kt,number_of_visit>を用いて維持できる。
【００９６】
全ての訪問回数だけノードｓにアクセスするために機能モジュールが必要な場合、キーとして<s,?,?>を有する全てのキー値タプルが検索されるべきである（ここで、?は任意のストリングに一致する）。次に、最終解を与えるために、対応するnumber_of_visitsが合計される。
【００９７】
通常のＲＤＦグラフは、ノード訪問頻度及びノード対の共起を記録するメタデータで拡張される。頻度及び共起の使用は、調整処理が最初に訪問する必要のあるノード数を減少させ、したがってトリプルの挿入のときの計算コストを低減するためである。これは、必要になるときに、そのポイントへの非緊急動作を延期する付加的な調整技術を可能にする。ノード及びエッジメタデータは、他者の中でノードがどれだけ重要か、及びノードが互いにどれだけ密接に接続されるかを伝達するメカニズムとして用いられる。
【００９８】
数値は、（データクエリによりトリガされる）readEventの結果として通常のグラフに増加的に加算される。以下では、通常のデータグラフ（ＲＤＦグラフ）はGと表され、拡張グラフG'iである。ここで、iは、（readEvent及びaddEventによりトリガされる）何回の繰り返しが元のグラフに適用され増加的グラフ変換を生じたかを示す。
【００９９】
定義６：頻度、共起、保留中要求。
【０１００】
Tをトリプル<s,p,o>とし、s及びoをtのグラフ表現から生じた２つのノードとする。頻度f(s)は、主語ノードsへの合計訪問回数である。共起を次式に示す。
【数８】
2013257874.tif 000010
ここで、ｍは、特定のトリプル<s,p,o>が主語sで訪問／クエリされた回数である。
【０１０１】
Lt=[t０;…,ti,…,tn]は、ノードにおいて調整されるべき全てのトリプルを含むトリプルのリストである。Ltは空であり得る。
【０１０２】
ノードsとノードoとの間の共起は、ノードsへの全ての訪問のうち、ノードoへの訪問を生じた数として概算される。基礎的記憶レベルでは、メタデータは、キー値タプルを形成するトリプルと関連付けられる。ここで、頻度及び保留中要求は、ノードメタデータ（つまり、<v,f:Lf>）として実装され、一方で、共起はエッジメタデータを通じて<e,co>として実現される。
【０１０３】
勿論、これらは、グラフトラバース動作で最も訪問されたノード及び最も訪問されたノードの後に訪問されたノードを識別するために必要なメタデータを格納するための単に例示的な技術である。熟練した読者は、異なる場所にメタデータとして格納される種々の異なる値が同じ目的のために使用され得ることを理解するだろう。
【０１０４】
addEvent及びreadEventはシステムにより異なる方法で処理される。グラフへのトリプルの追加はクエリのシリーズを発行させ、場合によっては、新しいトリプルを生成及び追加させるので、addEventのインスタンスは、頻度及び共起の値に関する更新のシーケンスであると考えることができる。理論的に、このようなリップルオフ効果は、処理される必要のあるノードが無い場合にのみ終了する。
【０１０５】
tを、主語ノードから目的語ノードへ向かう有向エッジと等価なトリプル<s,p,o>とする。
【０１０６】
グラフに対する各リード動作は、訪問されたノードの頻度値f(s)及びG'i内の近隣ノード間の共起関係co(s,o)を増加的に変化させる。論理的解釈は次の通りである。共起関連付けルールを用いることにより、ノードsに関して実行される調整処理が、sに接続する近隣ノードに伝搬されるべきか否か、又はこれらの近隣ノードの調整処理が遅延されるべきか否かを決定することができる。
【０１０７】
図３は、グラフに新しいトリプルを追加する処理における制御のフローを示す。
【０１０８】
トリプルを空のグラフに追加するとき、調整は必要なく、Ｓ１０１−Ｓ１０３、Ｓ１０２で「ＹＥＳ」である。ステップＳ１０４で、拡張グラフは、簡素なＲＤＦグラフとして開始される。トリプルを既存のグラフに追加するとき、Ｓ１０２で「ＮＯ」であり、主語ノードの対応する頻度とトリプルの主語及び目的語を接続するエッジの共起が１だけ増加される場合、Ｓ１０５で拡張グラフは更新される。必要な場合、Ｓ１０５で、調整処理が実行される。この段階で、ノードの初期サブセットが選択され、調整処理がノードの初期サブセットと新しいトリプルの主語ノードとの間で実行される。図４は、以下に議論するように、Algorithm２で形式化された、Ｓ１０５内の処理の例示的な制御フローを提供する。多くの場合、調整処理は、新しいトリプルの生成をもたらし、Ｓ１０６で「ＹＥＳ」であり、また、メタデータの更新及び新しい調整処理を発生する。これは、新しい知識（トリプル）が生成されなくなるまで続く。この処理は、Algorithm２で形式化される。留意すべき点は、ＫＶＳの特性により、既存のキー値ペアを追加することは、単にタプルの値を更新する。
【０１０９】
特定のプロシジャを実行する装置の観点から、初期サブセットの選択は、選択モジュールにより実行されても良い。類似性計算、それらの集約、及び適切な場合には新しい等価リンクの生成を含む調整処理は、調整処理モジュールにより実行されても良い。特定のトリガイベントへの応答、及びトリガイベントに応答して実行されるべき調整処理の識別を含む更なる（遅延された）調整処理の識別及びスケジューリングは、調整処理制御モジュールにより実行される。各モジュールは、分散型システム内の記憶ユニット／サーバ／コンピューティングリソースにローカルであっても良く又は集中型にされ中央ハードウェア要素に設けられるか若しくは効率的集中型制御部を生成するよう協働する分散型ハードウェア／コンピューティングリソース／サーバにより設けられても良いデータベース制御部の一部として実現されても良い。モジュールは、ハードウェアとして実現されても良く、コンピューティングリソース／サーバ／記憶ユニットで例えばデータベース管理システムの一部として動作するソフトウェアモジュールであっても良い。
【０１１０】
データ／セマンティック調整は、主に、新しいインスタンスデータがアサートされるとき生じる。
【０１１１】
トリプルt=<s,p,o>を追加するとき、addEventインスタンスは、グラフ全体に対して実行されるべき、挿入されるトリプルtの主語sの調整をトリガする。実際に、処理を必要とするグラフのサイズは、容易に何百万ものノードに達し、包括的トラバースを可能にするには大き過ぎてしまう。特定のノード、この場合には新しいトリプルの主語の調整が最初に実行されるべき初期サブセットを選択することに焦点を当てることにより、最初の処理負荷が軽減され、費用のかからない初期調整近似が得られる。
【数９】
2013257874.tif 000011
【数１０】
2013257874.tif 000012
【０１１２】
Algorithm３は、特定のノードとの調整処理が実行されるノードの初期サブセットを選択する例示的なアルゴリズムであり、初期サブセットの一部ではないノードに特定のノードの指示を記録することで、それらは将来オンデマンドで特定のノードと調整できる（つまり調整処理が遅延される）。
【０１１３】
図４は、Algorithm２及び図３のＳ１０５の一部として生じる処理に対応する制御フローを示す。つまり、図４は、グラフを有する特定のノード（例えば、新しいトリプルの主語ノード）に対する調整処理を実行し拡張グラフを更新する制御フローを示す。Ｓ２００で、最も訪問されたノードが検索される。Ｓ２０１で特定のノードと最も訪問されたノードとの間の調整処理が実行され、Ｓ２０２でノードの共起が検索／計算され、個々の最も訪問されたノードとの共起頻度が所定の閾より高い、最も訪問されたノードの近隣のノード（Ｓ２０３で「ＹＥＳ」）も、初期サブセットの一部としてＳ２０１の特定のノードと調整される。Ｓ２０１で実行される処理は、図５のフローチャート及びAlgorithm３に更に詳細に示される。最も訪問されたノードが残っていない又は最も訪問されたノードとの共起が閾より高い、最も訪問されたノードの近隣がないと、調整処理の一部としての新しいトリプルの生成が新しい最も訪問されたノードを生じるか否かについてのチェックが実行される。つまりステップＳ２００乃至Ｓ２０３が繰り返される。これは、「リップル効果」として知られ、調整処理の一部として新しいトリプルが追加されなくなるまで続く。残りのノードと特定のノードとの間の調整処理は、遅延される。Algorithm２で説明したように、特定のノードの指示は、ステップＳ２００乃至Ｓ２０４の一部として調整処理が実行されない各ノードに記録され、したがってそれらのノードは遅延の後に増加的に調整され得る。
【０１１４】
この増加的アプローチの背後にある論理的解釈は次の通りである。調整は、過去に頻繁に訪問されたノード及び（共起を通じて）それらと強い相関のあるそれらの近隣に対してのみ実行されることである。他のノードの調整は、それらが訪問されるまで又は包括的調整要求が明示的に行われるまで、延期される。Algorithm３に示したように、最も頻繁に訪問されたノードのサブセットＳは、頻度値を用いて識別される。
【０１１５】
調整は、この最も頻繁に訪問されたノードの初期サブセットに対して実行される。（所定の閾βより上の）頻繁に訪問されたノードに強く接続された全ての未処理ノードは、特定のノードに対して調整される。強く接続されたノードは、初期サブセットの一部であっても良いが、幾つかの実施形態では、初期サブセットは最も頻繁に訪問されたノードのみであっても良く、強く接続されたノード（閾より高い、最も訪問されたノードとの共起関係co(s,o)を有するノード）は、特定のノードと調整処理が遅延されるノードの更なるサブセットの一部であっても良い。
【０１１６】
全ての残りのノードの調整は、それらが明示的に訪問されるときまで、包括的調整アプローチが特定のノードに関して行われるまで、又はシステムがアイドルである若しくは予備の処理能力を有するという指示に応答して調整処理が実行されるまで、延期されるだろう。しかしながら、未実行の調整は、record()を用いて各ノードにローカルに記録される。これは、必要になるまで又は有利になるとき、ワンパス調整を可能にするだろう。
【０１１７】
v'∈V'kに対する調整doReconciliation(s,v’)は、２つの固有の部分、つまり類似性計算及び結果の集約を有する。
【０１１８】
図５は、図４のステップＳ２０１の「調整の実行」の一部として実行される処理を説明するフローチャートである。この調整処理は、上述のAlgorithm３で形式化される。Algorithm  ３及び図５は、本発明の実施形態の特定の実装における例示的な調整処理を説明する。勿論、多くの代替の調整処理ルーチンが本発明の実施形態において実行され得る。ステップＳ３００で調整候補リストが得られる。これは、例えば、ノードの初期サブセット又はノードの更なるサブセットの全部若しくは一部である。ステップＳ３０１で、類似性指標が計算され、又は類似性計算が実行される。類似性計算は、２つのリソースs、v'が等価である範囲を決定するための類似性測定のセットであっても良い。各類似性計算は、２つのリソース間の類似性の程度を示すスコア（又は特定のノードsと別のノードv'が等価である可能性）を生成する。したがって、similarity(s;v′)=σであり、σは[０,１]のスコアであり、ここで、０は２つのエンティティが異なることを示し、１はそれらが等価であることを示す（同じ現実世界オブジェクトを記述する）。次に、類似性計算は、例えば単なる集約により又は加重平均により、類似性値を得るために結合される。
【０１１９】
類似性計算は、異なる類似性指標に基づき、大部分は種々のストリング類似性メトリックを含み、記録連鎖及びスキーママッチングの両方に広く用いられる。ストリング類似性メトリックは、共通のスペル偏差を考慮に入れるよう設計された、あるストリング値を別のストリング値に変換するために必要な初期変化動作の数を測定するLevenshtein  Edit距離、及び／又はメトリックを有しても良い。これらの２つは、多くの類似性指標の単なる例であり、実施形態はリソースの調整を実行するために用いることができる。結果の集約では、各対（s,v',score）について、調整は、例えば、これらの類似性指標の加重平均として集約された類似性値equivalent(s,vi,weighted_score)を得る。類似性値が選択された類似性閾similarity_thより高い場合のみ（Ｓ３０３）、候補等価リンクが選択され、グラフに追加される。similarity_thは、オブジェクト対の記述を互いの類似性と見なすために必要な類似性の最小値を示す。
【０１２０】
延期された調整は、２つの異なる方法の一方又は両方で処理される。
【０１２１】
ｉ）「オンデマンド」及び「オンノード」調整が、readEvent（クエリ）によりトリガされる。
【０１２２】
ii)システムアイドル時間における強制的調整。極端な場合には、トリプル挿入のときに調整が行われないことも可能である。つまり、全ての調整がシステムアイドル時間又は明示的クエリの時点まで延期され得る。
【０１２３】
（１）保留中の調整要求によるグラフのクエリ
本発明の実施形態で用いられる増加的調整アプローチは、グラフ内の既存ノードとの調整が実行されるべきであると決定された特定ノードと、グラフ内の少なくとも幾つかのノードとの間の調整処理を、本当に必要又は有利になるまで、延期又は遅延させるステップを有する。上述のように、特定ノードは、グラフに挿入される新しいトリプルの主語ノードであっても良い。挿入のときに、特定ノードは、自身と最も頻繁に訪問されたノード／リソース及びそれらの強く相関した近隣との間で実行された調整処理のみを有しても良い。全ての残りのノードに対する調整処理は、「オンデマンド」を考慮して遅延される。
【０１２４】
遅延された調整処理が識別されスケジューリングされるメカニズムとして、これらの保留中要求が、２つの異なる場所の一方又は両方に格納されても良い。事実上、このメカニズムのために必要な追加記憶空間は、時間効率及び処理性能とのトレードオフである。
【０１２５】
第一に、データ調整処理を開始するトリプルは、拡張グラフの各未訪問ノードに、ノードメタデータとして格納される（定義４及び定義６を参照）。保留中要求を（リストLt内の）ノードにローカルに格納することにより、更なる調整が各ノードにおいてオンデマンドで処理できる。つまり、１つのノードに関して遅延された処理が存在するという事実は、該ノードの格納されたメタデータをリードすることにより確かめることができ、遅延された処理は相応してスケジューリングできる。
【０１２６】
第二に、システムは、未だ完全に調整されていない新しく追加されたトリプルのリストをグラフで保持する（ここで、完全に調整されたトリプル又はノードは、グラフ内の他のノードの各々との調整処理が実行されたトリプル又はノードである。）。このリストは、未調整トリプルのキュー（又はキャッシュ）Q=[t０,…,tm]と表される。
【０１２７】
図６は、クエリに応答して検索されるべきノードについての調整処理がグラフ内の全ての他のノードに対して実行されるのを保証するために、グラフへのクエリの要求を受信すると実行される処理を説明するフローチャートである。
【０１２８】
クエリするとき、query(q)は、先ず、Ｓ４０１及びＳ４０２で、Qのメンバに対して調べられる。
【０１２９】
Ｑ内の要素を含むと考えられるクエリに対して満たされるべき条件は、次の形式を取り得る。
【数１１】
2013257874.tif 000013
【０１３０】
ここで、δは所定の数値閾である。基本的に、クエリがＱ内の要素と等しいか又はＱ内の要素と極めて類似する場合（閾の類似性がσにより与えられる場合）、質問内のノードのデータ調整は、グラフ全体に対して強制される。類似性閾の条件は、Ｑが対象クエリを含むか否かを調べるときに柔軟性を提供する。
【０１３１】
Ｑがクエリを含む場合（つまり、上述の条件が満たされる場合）、Ｓ４０２で「ＹＥＳ」であり、フローはＳ４０３へ進み、Ｑのメンバであるクエリされたノードのデータ調整ｔｊが、グラフ全体に対して強化される。留意すべきことに、この「包括的調整」は、クエリを受信すると実行されなければならない調整処理の量の観点から「最悪のシナリ
オ」を効率的に定める。しかしながら、殆どの実装では、Ｑのサイズはグラフに比べて遙かに小さいと予測される。したがって、強制的包括グラフ調整は、頻繁には生じない。また、システムアイドル時間に、待ち行列に入れられた未調整トリプルは削除及び処理され、クエリが自身を「最悪のシナリオ」であると気付く機会を更に減少させる。さらに、これは、クエリ内のノードの識別により包括的調整がこの点で要求される場合であり、したがって、処理は、調整がアクセスされているノードについてであるという事実の観点から効率的である。Ｓ４０３の包括的調整の後（包括的調整の例示的な処理は図７で更に詳細に説明される）、フローはＳ４０４へ進み、クエリは評価されノードがリードされる。
【０１３２】
Ｓ４０２で「ＮＯ」であり、クエリｑと行列Ｑとの間に重複がない場合、フローはＳ４０５へ進み、拡張グラフに対して評価される。ステップＳ４０５及びＳ４０６で、クエリされている任意のノードが、保留中の／遅延された調整処理を有するノードの「オンノード」指示（メタデータに格納された行列Lt内で識別される）を有するか否かを識別するためにチェックが実行される。Ｓ４０７で、未調整ノード（保留中の調整を有する拡張グラフ内のノード）に遭遇すると直ぐに、「オンノード」データ調整処理が実行される。図８は、「オンノード」データ調整処理の例示的な処理を説明する。
【０１３３】
ステップＳ４０８で、クエリの評価中に、拡張グラフのメタデータが、頻度、共起及びノードローカル及びグローバルキャッシュされた保留中調整要求の観点から更新される。
【０１３４】
図８及び９から分かるように、各場合に実行されなければならない調整処理は、大部分が図５に示した調整処理と同じであり、同様の数値が直接的に等価なステップで用いられている。相違は、単に、特定のノードとの調整処理が実行されるべき候補ノードにある。
【０１３５】
（２）アイドル時間における調整：クエリにより強制される「オンデマンド」及び「オンノード」データ調整とは別に、増加的アプローチは、コンピューティングリソースの良好な利用を可能にする。システム全体を監視することにより、コンピューティングリソースの動作負荷に調整処理を追加する十分な処理能力を有すると決定された、コンピューティングリソースがアイドルである又は動作状態であるタイムスロットを識別することが可能である。保留中の調整は、識別され、スケジューリングされ、必要な及び適切な場合にはグラフ全体に対し、又は再び頻度及び共起値を用いて増加的に実行され得る。留意すべきことに、調整は、拡張グラフメタデータの更新も生じる。アイドル時間における調整は、「オンノード」調整及び包括的調整の一方又は両方であっても良い。
【０１３６】
イベント駆動型アプローチの実装は、幾つかの類似性タスクの存在を異なる分散した相互にネットワーク接続されたノードで同時に実行させることを可能にする。これは、他のアプローチと異なる。イベントの使用は、コンポーネントの相互通信を編成するための主な媒体である。セマンティック動作の並列化は、２次元のデータセグメント化を通じて達成される。
【０１３７】
先ず、元のデータグラフは、複数の物理的記憶に渡って分散され、調整が実行されるときにデータの「縦方向の」セグメント化を可能にする。異なる類似性タスクは、通信ネットワークを通じてリンク付けされた遠隔サーバにより実行され得る。そして、このようなタスクは並列に実行され得る。分散及び並列化は、調整処理全体の実行時間を高速化するのを助け得るイベント駆動型システムの特徴である。調整処理は、未だコンピューティングリソースの全てのノードと調整されていない特定のノードについてのリードイベント又は追加イベントによりトリガされるコンピューティングリソースにより実行できる。１より多いコンピューティングリソースが、一度に同じ特定のノードについてこのような調整処理を実行できる。
【０１３８】
図９は、多数のサーバに渡る調整処理の並列化の概念的説明である。調整処理は、イベントによりトリガされる。イベントは、新しいトリプルの基礎的データ構造への追加であっても良く、この場合、トリプルの主語が「詳細（particular）」になる。類似性計算及びこれらの計算に基づく類似性値を得るために必要な処理の性能は、各サーバにおいて、特定のノードと該サーバに格納される選択された候補リストのノード（例えば、初期サブセット、又は包括的処理の場合に、グラフの全て）との間で、実行されても良い。この意味で、調整処理は、個々のサーバで並列に実行される多数の類似性タスク（類似性タスク１乃至ｎ）に分解される。次に、結果が集約され、グラフは適切な場合に等価リンクで更新される。これは、更なる調整処理をトリガする別の「イベント」の発生を与え得る。
【０１３９】
第二に、拡張グラフは、データパーティショニングの要約及び動的レイヤを通じて並列化の向上した能力を提供する。拡張グラフG'にメタデータとして格納された頻度及び共起値を識別子として用いることにより、分散データ記憶を通じて取得される基礎的な物理的データセグメント化に直交したデータセグメント化を課すことができる。次に、グラフ内のデータは、調整処理のために小さい断片に効率的に角切り（dice）にされる。ここで、（図１０に示すように）各ダイスは調整処理のルーチンが閉じ込められる境界を定める。この第２のセグメント化は、グラフが複数のマシンに渡って格納される場合でも、個々のマシンにあるデータのサイズは、場合によっては非常に大きく、リアルタイムの包括的調整動作ができないので、望ましい。２個の任意のノード間の共起確率は、グラフを頻繁に訪問されたノードのサブグラフ（初期サブセット）及び余り訪問されていないノードを含むサブグラフ（更なるサブセット）に区分するために用いることができる。後者では、調整処理は、直接リード動作が実行されるまで又はシステムアイドル時間まで、遅延又は延期される。したがって、場合によってはセマンティックデータ調整処理を並列化できる増加的アプローチが有効である。既に配置されている物理的記憶セグメント化に重ね合わせて、この使用に基づくセグメント化は、データ調整の並列処理を更に向上させる。
【０１４０】
上述の態様の何れにおいても、種々の特徴は、ハードウェアで、又は１若しくは複数のプロセッサで動作するソフトウェアモジュールとして実施されても良い。ある態様の特徴は、他の態様の特徴に適用されても良い。
【０１４１】
本発明は、上述の任意の方法を実行するコンピュータプログラム又はコンピュータプログラムプロダクト、及び上述の任意の方法を実行するプログラムを格納しているコンピュータ可読媒体も提供する。本発明を実施するコンピュータプログラムは、コンピュータ可読媒体に格納されてもよい。或いは、例えば、インターネット・ウェブサイトから提供されるダウンロード可能なデータ信号のような信号形式又は任意の他の形式であってもよい。
【符号の説明】
【０１４２】
１０  サーバ
１１  セマンティックレイヤ
１２  ＲＤＦレイヤ
１３  障害検出
１４  トリプルアダプタレイヤ
１５  ＫＶＳレイヤ
１６  通信レイヤ
２１  調整プロセッサ
２２  ＲＤＦプロセッサ
２３  データ記憶
３０  クライアントアプリケーション
【図１】
2013257874.tif 000014
【図２】
2013257874.tif 000015
【図３】
2013257874.tif 000016
【図４】
2013257874.tif 000017
【図５】
2013257874.tif 000018
【図６】
2013257874.tif 000019
【図７】
2013257874.tif 000020
【図８】
2013257874.tif 000021
【図９】
2013257874.tif 000022
【図１０】
2013257874.tif 000023