(57)【要約】      （修正有）【課題】複数の相互接続されるデータノードをエンコードするデータグラフとともにターゲットデータノードをリコンサイルする方法を提供すること。【解決手段】本方法は、初期候補群のメンバとターゲットデータノードとの部分的比較処理を実行することにより、複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングする工程を有する。部分的比較処理は、第1のハッシュ関数群を利用して、メンバの各々及びターゲットデータノードから抽出される第1特徴群を比較し、初期候補群中のメンバと、そのメンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける初期候補群中の何らかの他のメンバとを除外することを含む。【選択図】図１
2016071865.tif 000002
【特許請求の範囲】
【請求項１】
複数の相互接続されるデータノードをエンコードするデータグラフとともにターゲットデータノードをリコンサイルする方法であって、
前記複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングする工程であって：
前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理であって、第1のハッシュ関数群を利用して、前記メンバの各々及び前記ターゲットデータノードから抽出される第1特徴群を比較する部分的比較処理を実行すること；及び
前記部分的比較処理の結果が1つ以上の除外基準を充足する場合に、前記初期候補群中の前記メンバと、当該メンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける前記初期候補群中の何らかの他のメンバとを除外すること；
により、フィルタリングを行う工程；及び
前記初期候補群の残存するメンバの各々が前記ターゲットデータノードとの前記部分的比較処理を完了するまで、前記除外基準が充足される場合に、前記実行すること及び前記除外することを反復する工程；
を有し、当該方法は、
前記フィルタリングする工程に続いて、前記初期候補群の残存するメンバの各々と前記ターゲットデータノードとの間の完全な比較処理であって、第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較する完全な比較処理を実行する工程；
をさらに有し、前記第2のハッシュ関数群は、前記第1のハッシュ関数群より多いハッシュ関数を含む、方法。
【請求項２】
前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理が、サブセット結果照合手順を含み、前記サブセット結果照合手順は：
前記第1のハッシュ関数群からハッシュ関数の部分集合を選択すること；
前記メンバの第1特徴群に対して前記ハッシュ関数の部分集合を実行した結果と、前記ターゲットデータノードの第1特徴群に対して前記ハッシュ関数の部分集合を実行した結果とを取得すること；を含み、
前記サブセット結果照合手順は、
(i)ハッシュ関数の同じ部分集合に関し、前記メンバについて取得される結果及び前記ターゲットデータノードについて取得される結果が、合致基準を充足する；或いは
(ii)単独のメンバに対する前記サブセット結果照合手順の反復回数の所定の上限に達するまで、
同じメンバについての反復の各々に異なるハッシュ関数群を選択する反復的な方法で実行され；
前記除外基準は：
前記合致基準を充足することなく、単独のメンバに対する前記サブセット結果照合手順の反復回数の所定の上限に前記メンバに対して到達すること；及び
前記合致基準が充足され、前記ターゲットデータノードの前記第1特徴群について実行される前記ハッシュ関数による結果と比較される前記メンバの前記第1特徴群について実行される同じハッシュ関数の選択される部分集合についての結果の集まりの評価が、前記メンバと前記ターゲットデータノードとが同等である確率は所定の閾確率未満であることを示すこと；
のうちの1つ以上を含む、請求項1に記載の方法。
【請求項３】
前記合致基準が、あるメンバに対する前記サブセット結果照合手順により充足される場合に、当該メンバが更なる部分的比較処理のためのグループに加えられ；及び
前記部分的比較処理は：
更なる部分的比較処理のためのグループに加えられる前記メンバの各々について：
前記メンバの前記第1特徴群に対して前記第1のハッシュ関数群を実行した結果を取得し、前記ターゲットデータノードの前記第1特徴群に対して前記第1のハッシュ関数群を実行した結果を取得し、取得された各々の結果を比較し、前記比較に基づいて、前記メンバと前記ターゲットデータノードとが同等である確率の指標を生成し、前記指標が所定の閾確率未満である場合に、除外基準は充足されていると判断される；
ことを更に含む、請求項2に記載の方法。
【請求項４】
前記第1特徴群と前記第2特徴群とが同じである、請求項1に記載の方法。
【請求項５】
前記第1のハッシュ関数群は前記第2のハッシュ関数群の一部分である、請求項1に記載の方法。
【請求項６】
前記意味論的類似性閾値は、前記部分的比較処理により示される前記メンバと前記ターゲットデータノードとが同等である確率に応じて動的に決定される、請求項1に記載の方法。
【請求項７】
前記フィルタリングする工程及び前記完全な比較処理を実行する工程が第1反復として実行され、当該方法は、前記フィルタリングする工程及び前記完全な比較処理を実行する工程の1回以上の追加的な反復を更に含み：
各々の追加的な反復に対するデータノードの前記初期候補群は、先行する反復の前記フィルタリングする工程に続く先行する反復における初期候補群のうちの残存するメンバであり；及び
各々の追加的な反復についての前記第1特徴群は前記先行する反復の前記第1特徴群の上位集合であり、各々の追加的な反復についての前記第2特徴群は前記先行する反復の前記第2特徴群の上位集合である、請求項1に記載の方法。
【請求項８】
前記1回以上の追加的な反復は、前記フィルタリングする工程及び前記完全な比較処理を実行する工程を実行するために割り当てられるハードウェアリソースがアイドルであると確認されるタイミングまで、遅延させられる、請求項7に記載の方法。
【請求項９】
前記ターゲットデータノード及び前記残存するメンバから抽出される前記第2特徴群に対して実行される第2のハッシュ関数群の結果を比較することは、前記ターゲットデータノードと前記残存するメンバとは意味的に同等である尤度を表現する値を生成し、
生成された前記値が意味的同等性閾値を超える場合、前記ターゲットデータノードを前記データグラフに加え、前記ターゲットデータノードと前記残存するメンバとの間の同等性の関係を示す同等リンクを前記データグラフに加える、請求項1に記載の方法。
【請求項１０】
前記データグラフは、データモデルを規定する第1グループのデータノードと前記第1グループのデータノードのインスタンスを規定する第2グループのデータノードとを有し、
前記初期候補群は前記第2グループのデータノードである、請求項1に記載の方法。
【請求項１１】
当該方法は、前記フィルタリングする工程の後に、前記ターゲットデータノード及び前記初期候補群の各メンバから第1特徴群の各々の値を抽出し、前記ターゲットデータノード及び前記初期候補群の残存する各メンバから第2特徴群の各々の値を抽出する工程をさらに有し、
第1のハッシュ関数群を利用して、前記メンバ及び前記ターゲットデータノードの双方から抽出される第1特徴群を比較することが：
前記第1のハッシュ関数群のうちの各々のハッシュ関数について、前記ターゲットデータノードの前記第1特徴群の値に対して前記ハッシュ関数を実行することによる第1結果と、前記メンバの前記第1特徴群の値に対して前記ハッシュ関数を実行することによる第2結果とを取得し、前記第1結果と前記第2結果とを比較すること；
を含み、及び/又は
第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較することが：
前記第2のハッシュ関数群のうちの各々のハッシュ関数について、前記ターゲットデータノードの前記第2特徴群の値に対して前記ハッシュ関数を実行することによる第1結果と、前記残存するメンバの前記第2特徴群の値に対して前記ハッシュ関数を実行することによる第2結果とを取得し、前記第1結果と前記第2結果とを比較すること；
を含む、請求項1に記載の方法。
【請求項１２】
前記部分的比較処理の結果は、前記第1結果が前記第2結果に合致する前記第1のハッシュ関数群の割合である；及び/又は
前記完全な比較処理の結果は、前記第1結果が前記第2結果に合致する前記第2のハッシュ関数群の割合である、請求項11に記載の方法。
【請求項１３】
複数の相互接続されるデータノードをエンコードするデータグラフを保存するように構成されるデータストレージシステムのコントローラであって、前記データグラフに挿入するためのターゲットデータノードを受信するように構成されるリコンシリエーション処理モジュールを有し；
前記リコンシリエーション処理モジュールは：
前記複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングするように構成されるフィルタリングモジュールであって：
前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理であって、第1のハッシュ関数群を利用して、前記メンバの各々及び前記ターゲットデータノードから抽出される第1特徴群を比較する部分的比較処理を実行すること；及び
前記部分的比較処理の結果が1つ以上の除外基準を充足する場合に、前記初期候補群中の前記メンバと、当該メンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける前記初期候補群中の何らかの他のメンバとを除外すること；
により、フィルタリングを行い；及び
前記初期候補群の残存するメンバの各々が前記ターゲットデータノードとの前記部分的比較処理を完了するまで、前記除外基準が充足される場合に、前記実行すること及び前記除外することを反復する、フィルタリングモジュール；
を有し、前記リコンシリエーション処理モジュールは、
前記フィルタリングモジュールにより出力される前記初期候補群の残存するメンバの各々と前記ターゲットデータノードとの間の完全な比較処理であって、第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較する完全な比較処理を実行する完全比較処理モジュール；
をさらに有し、前記第2のハッシュ関数群は、前記第1のハッシュ関数群より多いハッシュ関数を含む、コントローラ。
【請求項１４】
個別的に又は協調して、複数の相互接続されるデータノードをエンコードするデータグラフを保存するように構成される1つ以上のストレージユニットと、請求項13に記載のコントローラとを有するデータストレージシステム。
【請求項１５】
コンピュータプログラムを保存する非一時的な記憶媒体であって、前記コンピュータプログラムは、1つ又は複数のコンピュータ装置により実行される場合に、複数の相互接続されるデータノードをエンコードするデータグラフとともにターゲットデータノードをリコンサイルする方法を、前記1つ又は複数のコンピュータ装置に実行させ、
前記方法は：
前記複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングする工程であって：
前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理であって、第1のハッシュ関数群を利用して、前記メンバの各々及び前記ターゲットデータノードから抽出される第1特徴群を比較する部分的比較処理を実行すること；及び
前記部分的比較処理の結果が1つ以上の除外基準を充足する場合に、前記初期候補群中の前記メンバと、当該メンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける前記初期候補群中の何らかの他のメンバとを除外すること；
により、フィルタリングを行う工程；及び
前記初期候補群の残存するメンバの各々が前記ターゲットデータノードとの前記部分的比較処理を完了するまで、前記除外基準が充足される場合に、前記実行すること及び前記除外することを反復する工程；
を有し、当該方法は、
前記フィルタリングする工程に続いて、前記初期候補群の残存するメンバの各々と前記ターゲットデータノードとの間の完全な比較処理であって、第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較する完全な比較処理を実行する工程；
をさらに有し、前記第2のハッシュ関数群は、前記第1のハッシュ関数群より多いハッシュ関数を含む、記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータストレージ及び関連する処理の分野に属する。特に、本発明の実施形態は、グラフデータのノードのリコンシリエーション(reconciliation)を実行することに関連する。リコンシリエーションの処理はグラフの中で意味的に等価なリソース間の不均一性をリコンサイル(reconcile)するように意図される。
【背景技術】
【０００２】
利用可能な大量のグラフデータは、統計的な傾向を明らかにするだけでなく隠れたパターンを発見すること及びデータの範囲外の知識を抽出することも可能な自動的又は半自動的な分析の可能性を生み出す。形式的意味論(formal  semantics)はコンピュータインテンシブなタスクを自動化する際に重要な役割を演じる。どのようにして最良の意味を取得するかについて悪戦苦闘が長く続いているが、グラフ又はグラフのような表現は、(エンティティとのオントロジ及びエンティティ間の関係として)人間が世界をどのように感じているかを真似る最良の手段であることが、広く認められている。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
データセットは一般に非常に不均一に分散されている。そのようなデータのセントラル化されてない性質は、しばしば、多くのデータソースが現実世界の同じ対象(オブジェクト)を示すために異なるリファレンスを使用する、という問題を招く。利用可能なデータを効率的に利用することに向けた必要な重要なステップは、意味の一貫性に関して、複数のリファレンスを特定してリコンサイルすることである(リコンサイルは、調整、調停、調和、照合などと言及されてもよい)。以後、「リコンシリエーション」という用語は、(データのグラフにおけるノード、例えば、RDFトリプルの対象又は客体のような)意味的に互いに対応するリソースの中で同等リンク(equivalence  link)を特定及び規定することにより、リソース間の不均一性をリコンサイルするプロセスを指すために使用される。従って、「リコンシリエーション処理」は、リコンシリエーションを達成するためのプロセッサによるアルゴリズム及び命令の実行である。
【０００４】
データのリコンシリエーションの重要性は明らかである。データのリコンシリエーションは、不均一又は異なるデータセットがリンクされる(データの様々な意味をもたらす)場合に、データのインテグリティ(完全性、整合性など)を保証する。さもなくば、有意義な分析を行うことはできない。一方、等価性又は同等性は、アプリケーションが互いに整合することを許容する。従って、アプリケーション間の通信は、自動化されることが可能であり従ってコンピュータに委託することができる。
【０００５】
データのリコンシリエーションは、大規模なデータベースや大規模なナレッジベースにおいて困難な研究課題である。以後、「ナレッジベース(knowledge  base)」は、例えばオントロジやリレーショナルデータベースのスキーマのような所定のスキーマを有するデータリポジトリを示すために使用される。全てのノードに対する完全な線形比較(full  linear  comparison)によりデータのリコンシリエーションを行うことは、大規模なナレッジベースの場合には実用的でない。そのような比較方法は、データ項目の全てのペアの類似性/距離を推定することを含み、各ペアの類似性/距離の計算は時間のかかり演算負担が大きくなり得る。その理由の一部は、類似性を計算するために、高次元の特徴ベクトルが使用されることである。線形比較は、高次元ベクトルについての多数のペア形式の比較を招く結果となる。
【０００６】
セマンティックウェブ技術の最近の進歩は、そのような問題を緩和していない。現在のセマンティクスは、拡張方式(エクステントベース方式)(extent  based  approach)又は集中方式(インテントベース方式)(intent  based  approach)の何れかにより論じられる。拡張方式は、データ項目の明確なインスタンス/リファレンスにより意味を投影するが、集中方式は、データ項目のいわゆる形式的な定義(十分に定義された論理的又は数学的な言語)を当てにする。リコンシリエーションは、その後に、明確なリファレンス及び/又は形式的な定義を双方のデータ項目から数字(類似性又は距離の定量的な表現)に投影することにより行われる。
【０００７】
何百万ものデータ項目あるいは何十億のデータ項目さえ有する大規模なナレッジベース(例えば、LOD(Linked  Open  Data)あるいはNCD(National  Consensus  Database))に関し、特にオンラインデータベースにおいて、データ項目の全てのペアの線形比較は実用的ではなくなる。
【０００８】
実施形態の一側面に関する課題は、大規模なデータベースに対しても実用的なデータ処理を行うことが可能な方法及び装置を提供することである。
【課題を解決するための手段】
【０００９】
一実施形態による方法は、
複数の相互接続されるデータノードをエンコードするデータグラフとともにターゲットデータノードをリコンサイルする方法であって、
前記複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングする工程であって：
前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理であって、第1のハッシュ関数群を利用して、前記メンバの各々及び前記ターゲットデータノードから抽出される第1特徴群を比較する部分的比較処理を実行すること；及び
前記部分的比較処理の結果が1つ以上の除外基準を充足する場合に、前記初期候補群中の前記メンバと、当該メンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける前記初期候補群中の何らかの他のメンバとを除外すること；
により、フィルタリングを行う工程；及び
前記初期候補群の残存するメンバの各々が前記ターゲットデータノードとの前記部分的比較処理を完了するまで、前記除外基準が充足される場合に、前記実行すること及び前記除外することを反復する工程；
を有し、当該方法は、
前記フィルタリングする工程に続いて、前記初期候補群の残存するメンバの各々と前記ターゲットデータノードとの間の完全な比較処理であって、第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較する完全な比較処理を実行する工程；
をさらに有し、前記第2のハッシュ関数群は、前記第1のハッシュ関数群より多いハッシュ関数を含む、方法である。
【発明の効果】
【００１０】
実施形態の一側面によれば、大規模なデータベースに対しても実用的なデータ処理を行うことが可能になる。
【図面の簡単な説明】
【００１１】
添付図面を参照しながら単なる一例により本発明の好ましい特徴が説明される。
【図１】実施形態による手順の全体を示す図である。
【発明を実施するための形態】
【００１２】
実施形態は、複数の相互接続されるデータノードをエンコードするデータグラフとともにターゲットデータノードをリコンサイルする方法を含む。本方法は：前記複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングする工程であって：前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理であって、第1のハッシュ関数群を利用して、前記メンバの各々及び前記ターゲットデータノードから抽出される第1特徴群を比較する部分的比較処理を実行すること；及び前記部分的比較処理の結果が1つ以上の除外基準を充足する場合に、前記初期候補群中の前記メンバと、当該メンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける前記初期候補群中の何らかの他のメンバとを除外すること；により、フィルタリングを行う工程；及び前記初期候補群の残存するメンバの各々が前記ターゲットデータノードとの前記部分的比較処理を完了するまで、前記除外基準が充足される場合に、前記実行すること及び前記除外することを反復する工程；を有する。当該方法は、前記フィルタリングする工程に続いて、前記初期候補群の残存するメンバの各々と前記ターゲットデータノードとの間の完全な比較処理であって、第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較する完全な比較処理を実行する工程；をさらに有し、前記第2のハッシュ関数群は、前記第1のハッシュ関数群より多いハッシュ関数を含む。
【００１３】
有利なことに、本発明の実施形態は、データノード間の意味的類似性を利用して、完全な比較処理は実行されないことになるデータノードを特定する。候補データノード群の各メンバとターゲットデータノードとの間で完全な比較が実行される方法と比較して、リコンシリエーション処理に課される処理オーバーヘッドは削減される。部分的比較処理は、ターゲットデータノードと十分に相違して見える初期候補群中のデータノードを特定するように実行され、完全な比較処理に進む機会は、(処理する)価値が無いと判断される場合に形成される同等リンクの結果により、さほど多くはならず、そのようなデータノードは候補群から除外される。更に、部分的比較処理が実行されたノードのみを除外するのではなく、除外するように選択されるノードと意味的類似度が大きな(すなわち、閾値を超える)任意のデータノードについても、初期候補群は検査される。意味的類似度は、部分的比較処理により除外するように選択されるデータノードだけでなく、除外するように選択されるデータノードに意味的に十分類似すると判断されるデータノードをも含むように、(初期候補群から、及び、何らかの以後のリコンシリエーション処理から)除外する範囲を拡張する手段を提供する。従って、部分的比較処理及び完全な比較処理の双方が、初期候補群から何らかのデータノードを除外することにより縮小される。
【００１４】
実施形態は、グラフに属する複数のデータノードとともにターゲットノードのリコンシリエーション処理を実行する方法を含み、ターゲットノードと同等であると判断される確率が閾確率未満である値を有すると評価される、複数のデータノードのうちの何らかのデータノードを特定するように実行される。特定されたデータノードとターゲットデータのとの間での更なるリコンシリエーション処理は実行されない。更に、特定されたデータノードとの意味的類似度が閾値より高い値を有すると評価されるデータノードも、ターゲットデータノードとともに実行される以後の如何なるリコンシリエーション処理から除外される。ターゲットデータノードは、データグラフに新たに追加されるデータであってもよい。代替的に、ターゲットデータノードは、データグラフに既に追加されていてもよいが、例えば、追加の時点で占有される必要なリソースに起因して、リコンシリエーション処理は処理を待機するかもしれない。
【００１５】
リソースのリコンシリエーションは、(グラフ内のノードにより表現される)リソース間で同等リンクを特定及び生成することにより、グラフ内のリソース間の不均一性をリコンサイルするためのプロセスである。例えば、異なる名称を有する2つのリソースが現実世界の同じ対象を指す場合(すなわち、2つのリソースは意味的に等価/意味的に同等である)、2つのリソースが同等であることを示すリンクをグラフに追加することは適切なことであろう。リソースをリコンサイルすることは、同等性がリソース間に存在する場所を特定し(例えば、グラフノードはリソースである)、その同等性の指示又は指標(indication)をグラフに追加することを含んでよい。現実世界の同じエンティティ(entity)についての複数のリソース又は表現を特定することは、オントロジマッピング、オントロジマッチング又はオントロジアライメント等として知られている。
【００１６】
データグラフとともにターゲットデータノードをリコンサイルすることは、ターゲットデータノードと意味的に同等であるデータグラフ中の何らかのデータノードを特定し、その意味的な同等性を示すリンクとともにデータグラフにターゲットデータノードを追加することを含む。意味的に同等である何らかのデータノードを特定するのに必要な処理は、データグラフシステムにおいて、かなりのパフォーマンスオーバーヘッドとなる。本発明の実施形態による方法は、ターゲットデータノードと意味的に同等であると判断される確率が、更なるリコンシリエーション処理を実行することはリソースの非効率的な利用になってしまうほど小さい、候補群中のデータノードを特定する仕組みを提供し、従ってそれらは候補群から除外される。発明者等は、部分的比較処理により除外するように特定されるデータノードだけでなく、除外するように特定されるデータノード又はノード群と意味的に類似する(又は閾値より高い意味的類似度を有する)と判断されるデータノードも、初期候補群から除外するポリシ及び部分的比較処理の新規な結合を創作している。
【００１７】
初期候補群は、データグラフ中の全てのデータノードであってもよいし、或いは、例えばインスタンスのような所定のタイプのデータノードの全体であってもよい。初期候補群は、候補群、リコンシリエーション候補群、又は、同等性候補群などと言及されてもよい。フィルタリングは、同等である少なくとも見込みのある候補を特定し、それらを候補群から除外する手順である。フィルタリング及び完全な比較処理に使用されるハッシュ関数は、局所性鋭敏型ハッシュ関数(locality  sensitive  hash  function)、すなわち、ハッシュされる集団の分散を減らすハッシュ関数であってもよい。言い換えれば、ハッシュ関数がデータノードを分ける「ビン(bin)」の数が、ハッシュ関数が実行される特徴(feature)の可能な数の範囲より少ない。従って、候補をフィルタリング(又は選別)するハッシュ関数を活用することは、ハッシュ関数を利用して候補をロケーションに投影し、同じハッシュ関数により同じロケーションに投影されるものをターゲットデータノードとして特定するように考えることが可能である。初期候補群を構成する特定の一例として：データグラフは、データモデルを規定するデータノードの第1グループと、第1グループのノードのインスタンスを規定するデータノードの第2グループとを有し；初期候補群は第2グループのデータノードである。
【００１８】
データノードは特徴のベクトル(特徴ベクトル)として表現されてもよい。本方法は、データノードを分析し、データノードの複数の所定の特性の各々について値を抽出するプロセスを含んでもよい(抽出される値は特徴(特性)を示す)。第1特徴群(又は第1セットの特徴)は部分的比較処理に使用され、第2特徴群(又は第2セットの特徴)は完全な比較処理に使用される。選択的に、第1特徴群及び第2特徴群は、各データノードについて同じである。言い換えれば、単独の特徴群が、各データノードから抽出され、部分的比較処理及び完全な比較処理の双方に使用されてもよい。代替的に、第2特徴群は第1特徴群より広範囲に及んでもよいし、或いはその逆でもよい。
【００１９】
選択的に、第1特徴群及び第2特徴群は同一である。
【００２０】
データグラフは、エッジにより相互接続される複数のデータノードとして表現されてもよい。データノードは、ノードに向かう/ノードから来るグラフのエッジにより表現される全ての関係の総体(全体)であってもよいし、及び/又は、グラフのエッジにより表現される関連性に追加的な情報を含んでもよい。データグラフは、例えばRDFトリプルのようなトリプルとしてエンコードされてもよい。
【００２１】
グラフ中のデータは、特に、「接続されたデータ(又は接続データ)」、「リンクされたデータ(リンクデータ)」又は「関連するデータ(関連データ)」のように言及されてもよく、これらは何れも弧(arc)によって相互接続される複数のノードとしてグラフの概念構造を反映するように意図される。所定の実施形態において、グラフ中のデータは、「オープンリンクデータ」(LOD)イニシアチブの一部として提供されるデータのような「リンクされたデータ」であってもよいが、本発明の実施形態はその実施形態に限定されず、「リンクされたデータ」という用語は、LODイニシアチブの一部として提供される唯一のデータよりも広義に解釈される。
【００２２】
除外基準は、第1のハッシュ関数群の全部又は一部に基づいて、候補群のメンバがターゲットデータノードと意味的に同等であると判断される可能性が、そのメンバについてリコンシリエーション処理を継続するパフォーマンスオーバーヘッドを正当化するほど十分に高いか否かを判断する1つ以上の方法である。除外基準の形態が何れであれ、ターゲットデータノードに対するメンバの部分的比較処理の結果により、1つ以上が充足されるならば(候補群からの除外を開始するための必要数が充足されるならば)、そのメンバは初期候補群から除外するように特定される。除外するメンバを特定することは、候補群の残存する全てのメンバと除外するように特定されるメンバとの意味の比較を行うトリガを与え、十分に類似すると判断されるものも候補群から除外される。
【００２３】
部分的比較処理は、以後の完全な比較処理におけるものよりも少ない数のハッシュ関数が、初期候補群のメンバ毎に実行される点で、部分的である。以後の完全な比較処理は、部分的比較処理を考察する場合に完全な比較処理であると考えられ、その理由は、部分的比較処理の場合よりも多い数のハッシュ関数が、完全な比較処理における2つのデータノード間の比較で実行されるからである。所定の実施形態において、何れかの除外基準に適合すると、第1のハッシュ関数群の中の何らかの残存するハッシュ関数を実行することなく、速やかにそのメンバについて部分的比較処理が停止されてもよい。
【００２４】
初期候補群からメンバを除外することは、除外されるデータノードとターゲットデータノードとの間で更なるリコンシリエーション処理は一切実行されないことを意味する。これは、除外基準が充足されないメンバであって、除外されるデータノードの各々との意味的な類似度が閾値未満である値を有すると評価されるメンバを、完全な比較処理が実行されるメンバのリストに追加することと等価である。
【００２５】
2つのグラフデータノード間の意味的な類似度を評価するための多数の確立された技術が存在し、それらの何れもが実施形態に有益に利用可能である。何れの技術を選択するかについての具体的な判断は、実施形態の実現手段に依存してなされてよい。例示的な技術が本明細書において後述される。初期候補群中の他の何らかのメンバ(除外されるメンバに対する意味的類似性について評価されるメンバ)は、1つ以上の除外基準が充足されるメンバ以外の初期候補群中に残存する任意のメンバである。従って、1つ以上の除外基準が充足されるメンバと、初期候補群に残存する各メンバとの間の意味的類似性が評価され、閾値を超える意味的類似性を有するものが初期候補群から除外される。
【００２６】
完全な比較処理は、完全な線形比較処理であり、2つのデータノード(初期候補群中の残存するメンバ及びターゲットデータノード)が同等であるか否かを判断するための処理である。ハッシュ関数の結果を利用して、2つのデータノードが同等であるか否かを判断するための多くの技術が存在し、特定の技術の選択は特定の実現手段の条件に依存する。
【００２７】
部分的比較処理の結果は、例えば、(ハッシュ関数の)一部分が発見される前にメンバについて実行された第1ハッシュ関数群のハッシュ関数の一部分の数の形態をとってもよく、その実行された結果は、ターゲットデータノードに同じ一部分を実行することにより生成される結果に合致する。代替的に、部分的比較処理の結果は、第1ハッシュ関数群の中のハッシュ関数の数の形態をとってもよく、メンバについて生成される結果はターゲットデータノードについて生成される結果に合致する。代替的又は追加的に、メンバ及びターゲットデータノードに対する結果の近接度(closeness)を評価する全体的なスコアが、1つ以上の除外基準について生成及び評価されるように、1つ以上のハッシュ関数が近接度を評価することが可能な結果を生成してもよい(すなわち、近い値は、ハッシュ関数によりハッシュされる特徴が、遠く離れた値の場合よりも近接していることを示す)。実施形態は、充足されるように判断されるべき基準について、幾つの除外基準が合致する必要があるかに応じて異なってもよい。
【００２８】
例示的な部分的比較処理は、サブセット結果照合手順(subset  result  matching  procedure)を含み、前記サブセット結果照合手順は：前記第1のハッシュ関数群からハッシュ関数の部分集合を選択すること；前記メンバの第1特徴群に対して前記ハッシュ関数の部分集合を実行した結果と、前記ターゲットデータノードの第1特徴群に対して前記ハッシュ関数の部分集合を実行した結果とを取得すること；を含み、前記サブセット結果照合手順は、(i)ハッシュ関数の同じ部分集合に関し、前記メンバについて取得される結果及び前記ターゲットデータノードについて取得される結果が、合致基準を充足する；或いは(ii)単独のメンバに対する前記サブセット結果照合手順の反復回数の所定の上限に達するまで、同じメンバについての反復の各々に異なる一のハッシュ関数群を選択する反復的な方法で実行される。前記除外基準は：前記合致基準を充足することなく、単独のメンバに関し、前記単独のメンバに対する前記サブセット結果照合手順の反復回数の所定の上限値に到達すること；及び前記合致基準が充足され、前記ターゲットデータノードの前記第1特徴群について実行される前記ハッシュ関数による結果と比較される前記メンバの前記第1特徴群について実行される同じハッシュ関数の選択される部分集合についての結果の集まりの評価が、前記メンバと前記ターゲットデータノードとが同等である確率は所定の閾確率未満であること；のうちの1つ以上を含む。
【００２９】
サブセット結果照合手順は、第1ハッシュ関数群のうちの小さなサンプル(一部分)を利用して、メンバ及びターゲットデータノードの類似性を評価する仕組みを提供する。ハッシュ関数の部分集合が、メンバ及びターゲットデータノードについて同じ結果を生成することが見出される場合、そのメンバに対するサブセット結果照合手順は停止される。選択的に、停止されるサブセット結果照合手順は、そのメンバについて部分的比較処理は完了することを意味するが、更なる部分的比較処理が実行される実施形態も存在する。
【００３０】
除外基準が充足される部分集合が見出されることなく、サブセット結果照合手順で使用されるサブセット数の所定の上限に達する場合、メンバ及びデータノードが意味的に同等である確率は、そのメンバについて完全な比較処理の処理オーバーヘッドは正当化されない程度に十分低いことを示す。従って、この場合、除外基準は充足されると判断される。
【００３１】
合致基準は、結果が合致しなければならないものであってもよい。例えば、メンバの第1特徴群に対してハッシュ関数群の一部分を実行した結果が結果の文字列に連結され、ターゲットデータノードの第1特徴群に対してハッシュ関数群の一部分を実行した結果が結果の文字列に同じ順序で連結され、両者が比較される。両者が合致する場合、合致基準は充足される。代替的に、合致基準に何らかの許容度(耐性又はトレランス)が存在し、そのメンバ及びターゲットデータノードについて異なる結果を生成してよい部分集合におけるハッシュ関数の割合又は所定の最大数が存在し、合致基準が充足されると判断されてもよい。
【００３２】
部分集合当たりのハッシュ関数の数及び単独のメンバに対するサブセット結果照合手順の反復回数の上限は、何れも、特定のターゲットデータノードのリコンシリエーション処理が実行される前に事前に決定されていてもよいが、システムの属性として設定可能であってもよいし、或いは、リコンシリエーション処理の要求に対する入力変数として設定可能であってもよい。部分集合当たりのハッシュ関数の数に関し、多い数は多くの選択的な部分的な処理を生じ、合致基準に適合することは困難になり、単独のメンバに対するサブセット結果照合手順の反復回数に対する上限に容易に到達し、除外基準を充足しやすくなる。一方、サブセット結果照合手順の反復回数に対する上限の場合、多い数はより少ない選択的なプロセスを生じるが、「フォールスネガティブ又は偽陰性」の可能性を減らし、すなわちその場合、メンバは、ターゲットデータノードに実際に同等となって除外基準を充足するが、除外されるべきではない。
【００３３】
ターゲットデータノードの第1特徴群に対して実行されるハッシュ関数の結果とともにメンバの第1特徴群に対して実行される同じハッシュ関数の選択される部分集合の総合的な結果の評価を含む除外基準は、好都合なことに合致基準を満たしていたメンバを選別する(すなわち、初期候補群からの除外をもたらす)追加的な検査を提供する。例えば、あるメンバが、ハッシュ関数の最初の3つの部分についてターゲットデータノードから完全に異なる結果を生成し、第4の部分についてターゲットデータノードと同じ結果を生成した場合、完全な比較処理は評価に値しない。総合的なハッシュ関数結果の比較は、同等性の照合の確率を生成するために、そのような状況に対する代替的な除外基準を提供する。
【００３４】
メンバとターゲットデータノードが同等である確率の指標(indication)は、メンバ及びターゲットデータノードは同等であると判定される結果を完全比較処理がもたらす確率についての評価であると考えられてよい。例えば、多項式分布を利用して仮説検定を実行し、データノードが同等である旨の仮定に基づいて、取得される合致度(obtained  level  of  agreement)(すなわち、第1群におけるハッシュ関数の総数のうちのx個が合致すること)又はそれ未満を取得する仮説を検査することにより、確率が生成されてもよい。代替的に、ランダムに選択されるデータノードが、取得される合致度又はそれ未満を得る尤度(likelihood)を評価することにより(上記と同様に、多項式分布又はそれに等価なものを利用して)(閾値と比較するための指標である尤度を1からマイナスしたものとともに)、確率が生成されてもよい。
【００３５】
代替的又は追加的に、前記合致基準が、あるメンバに対する前記サブセット結果照合手順により充足される場合に、当該メンバが更なる部分的比較処理のためのグループに加えられ、及び、前記部分的比較処理は：更なる部分的比較処理のためのグループに加えられる前記メンバの各々について：前記メンバの前記第1特徴群に対して前記第1のハッシュ関数群を実行した結果を取得し、前記ターゲットデータノードの前記第1特徴群に対して前記第1のハッシュ関数群を実行した結果を取得し、取得された各々の結果を比較し、前記比較に基づいて、前記メンバと前記ターゲットデータノードとが同等である確率の指標を生成し、前記指標が所定の閾確率未満である場合に、除外基準は充足されていると判断される；ことを更に含む。
【００３６】
上記の処理(プロセス)は、スタガード又はステージ形式(ステージ毎に実行される形式)の部分的比較処理を可能にし、第1ハッシュ関数群の一部分(部分集合)がターゲットデータノードと同じ結果(又は十分に類似する結果)を生成したメンバのみが、それらについて完全な第1ハッシュ関数群が実行される。初期候補群からメンバが除外される際に2段階の部分的比較処理がある。先ず、サブセット照合手順が何らかの候補を除外する結果をもたらし、次に、サブセット結果照合手順で合致基準に適合しないことにより(又は合致基準を充足しなかったメンバに意味的に類似する旨の評価を受けることにより)、初期候補群から除外されなかった任意のメンバが、更なる部分的比較処理を実行してもらい、その結果が更なる除外基準に対して評価される。有利なことに、上記のスタガード又はステージ形式のアプローチは初期スクリーニングの仕組みを提供し、メンバ及びター下とデータノードについて同じ結果をもたらすハッシュ関数群が実行されると速やかに、(ターゲットデータノードのハッシュ関数結果に合致しないメンバに意味的に類似しないと判定される限り)そのメンバは更なる部分的比較処理に推し進められる。その根拠は、ターゲットデータノードのものに合致するハッシュ関数群の結果が得られないメンバは、完全な比較処理において、ほぼ確実に、ターゲットデータノードと同等であるとは判定されないであろう、ということである。従って、ハッシュ関数が実行される見込みがない時点で、メンバの中から類似する意味のメンバを取り出し、全体的な処理オーバーヘッドを削減することが可能になる。
【００３７】
各々のハッシュ関数は、結果を生成するためにデータノードの1つ以上の特徴に作用する。本明細書におけるハッシュ関数は局所性鋭敏型ハッシュ関数であってもよい。データノードを比較する目的のためにハッシュ関数のライブラリが利用可能であり、実施形態に関する予備的なステップとして、データベースのアドミニスタのレベルで、各々のハッシュ関数群に対するハッシュ関数の何らかの選択が必要である。ハッシュ関数の選択は別の研究分野になるが、実施形態において、一群のハッシュ関数の相対的なサイズ及びメンバーシップは設定可能なパラメータである。第2のハッシュ関数群は第1のハッシュ関数群より大きい。本明細書に関し、同じデータノードからの異なる特徴について複数回実行される同じハッシュ関数は、複数のハッシュ関数であると考えられる。特定の具体例において、前記第1のハッシュ関数群は前記第2のハッシュ関数群の一部分(部分集合)である。
【００３８】
有利なことに、2つのハッシュ関数群の間のそのような関係は、特定のメンバの部分的比較処理からのハッシュ関数結果が、同じメンバの完全な比較処理に使用されること、従って、そのメンバについて実行されるハッシュ関数の総数をへらすことを可能にする。ハッシュ関数は、ジャカール類似度(Jaccard  similarity)の最小ハッシュファミリから選択されてもよい。
【００３９】
初期候補群のメンバ間の意味的類似度を評価し、その評価を利用して、初期候補群からメンバを除外するか否かを判定する手順は、静的な類似性閾値を利用してもよい。すなわち、除外基準を充足するデータノードが発見され、従ってそのデータノードは初期候補群から除外されるべき場合に、除外されるべきデータノードと初期候補群の他のメンバの各々との間の類似性が評価され、除外されるべきデータノードと静的閾値以上の類似度を有する旨の評価を受けた如何なるメンバも、初期候補群から除外される。代替的又は追加的に、全部又は幾つかの例において、閾値について或る程度の柔軟性が存在してよい。例えば、可能性のある閾値の範囲(レンジ)が規定され、対象のメンバについて実行される部分的比較処理の結果に依存して、各インスタンスにおいて実際の閾値が選択されてもよい。例えば、部分的比較処理が、メンバについて実行される第1ハッシュ関数群の結果とターゲットデータノードについて実行される同じハッシュ関数(による結果)との比較を含み、その比較に基づいて、両者が同等であると判断される確率の指標が生成される場合に、その指標は、レンジの中から値が選択される基礎として使用されてもよい。例えば、意味論的類似性閾値は、前記部分的比較処理により示される前記メンバと前記ターゲットデータノードとが同等である確率に応じて動的に決定されてもよい。
【００４０】
有利なことに、閾値を或る程度変更できることは、部分的比較処理に基づいて、ターゲットデータノードと同等であるとほぼ判定されそうにないデータノードは、初期候補群から除外されるべき他のメンバに関し、他のメンバとの意味的類似性は比較的少ないと評価される必要があることを意味する。一方、あるメンバが、除外基準を充足するが、第1ケースの場合よりも、ターゲットデータノードと同等であるとは今ひとつ判断されそうにない場合、相対的に柔軟性は少なく、従って、除外されるべき他のメンバに必要な意味的類似度の必要レベルは、相対的に高い。従って、意味的類似性閾値は、部分的比較処理により示される確率(メンバとターゲットデータノードとが同等である確率)に逆比例又は負の比例関係に依存して所定の範囲内で変動してよい。
【００４１】
リコンシリエーション処理は、処理するリソースを利用することに起因するパフォーマンスオーバーヘッドを表す。リコンシリエーション処理のスケジューリング(処理計画)には柔軟性があることが望ましく、その理由は、他の処理がリソースを必要とする場合に、リソースを独り占めしてしまうことを回避し、そうではなくリソースがアイドルである場合にシステムがリコンシリエーション処理を実行できるようにするためである。実施形態は、反復的な処理としてリコンシリエーションを実行してもよく：前記フィルタリングする工程及び前記完全な比較処理を実行する工程が第1反復として実行され、当該方法は、前記フィルタリングする工程及び前記完全な比較処理を実行する工程の1回以上の追加的な反復を更に含む。それらの追加的な反復において、各々の追加的な反復に対するデータノードの前記初期候補群は、先行する反復の前記フィルタリングする工程に続く先行する反復における初期候補群のうちの残存するメンバであり；及び各々の追加的な反復についての前記第1特徴群は前記先行する反復の前記第1特徴群の上位集合であり、各々の追加的な反復についての前記第2特徴群は前記先行する反復の前記第2特徴群の上位集合である。
【００４２】
選択的に、各々の反復における特徴群のサイズを増やすことに応じて、各々の追加的な反復の第1ハッシュ関数群は先行する反復の第1ハッシュ関数群の一部分であり、各々の追加的な反復の第2ハッシュ関数群は先行する反復の第2ハッシュ関数群の一部分である。
【００４３】
有利なことに、上記のリコンシリエーション処理に対する反復的なアプローチは、実行するシステムにスケジューリングの自由度を提供し、リコンシリエーション処理が、リコンシリエーション処理の間にスケジューリングを予定する他のプロセスからリソースを遮ってしまうことを防止する。
【００４４】
例えば、前記1回以上の追加的な反復は、前記フィルタリングする工程及び前記完全な比較処理を実行する工程を実行するために割り当てられるハードウェアリソースがアイドルであると確認されるタイミングまで、遅延させられる。
【００４５】
1つのパス又は1つのルーチンでグラフ全体に対してリコンシリエーション処理を実行する条件を緩和することにより、新たなノードのリコンシリエーション処理に起因する障害が緩和される。これは、システムのパフォーマンスを全体的に改善し、システムオペレータが、システムパフォーマンスに及ぼす不利な影響を懸念することなく、更に複雑な及び潜在的に更に効果的なリコンシリエーションアルゴリズムを指向できるようにする。
【００４６】
アイドルであるリソースは、ある範囲内の動作状態に関し、便宜的な表記法として使用されており、その動作状態では、リコンシリエーション処理の責務を負うリソースにおいて、リコンシリエーション処理により課される余分な処理負担を取り扱う能力(余裕)がある。例えば、別の部分集合のリコンシリエーション処理は、プロセッサにおいて他の待機中のタスクが存在しない場合に、そのプロセッサにより実行される。そのような判断は、セントラル化されたワークロードスケジューラ(データベースコントローラの一部を形成してもよいし或いはそうでなくてもよい)によりなされてもよいし、或いは、プロセッサ自らローカルになされてもよい。
【００４７】
リコンシリエーション処理は、異なるデータ項目が意味的に同等である旨のデータグラフ指標をエンコードすることにより、データの不均一性を補償する。選択的に、同等なデータ項目を単独のデータ項目に統一することのような以後の更なる処理が、実行されてもよい。更なる選択肢として、データ項目を返すクエリが、データ項目に同等なものを返してもよい。同等リンクは多くの方法で使用されてよい。同等リンクを追加する場所の決定は、完全なリコンシリエーション処理の結果に依存してなされる。2つのデータノードが意味的に同等である尤度を表現する値を生成するために、ハッシュ関数の結果を分析する多くの技術が確立されており、分析及び生成を実行する詳細な仕組みは、特定の実現手段の条件に基づいて選択されることが可能である。同等リンクをデータグラフに追加するか否か及び追加する場所を判断する際の手順の具体例は次のようなものであってもよい：
選択的に、完全な比較処理は、前記ターゲットデータノードと前記残存するメンバとは意味的に同等である尤度を表現する値を生成し；生成された前記値が意味的同等性閾値を超える場合、前記ターゲットデータノードを前記データグラフに加え、前記ターゲットデータノードと前記残存するメンバとの間の同等性の関係を示す同等リンクを前記データグラフに加える。
【００４８】
生成された値が意味的同等性閾値を超えない場合、ターゲットデータノードは、何らの同等リンクもなしに、データグラフに加えられる。
【００４９】
局所性先鋭型ハッシュ関数のようなハッシュ関数を利用して、データノードを比較する後続の手順は次のようなものであってよく：当該方法は、前記ターゲットデータノード及び前記初期候補群の各メンバから第1特徴群の各々の値を抽出し、前記ターゲットデータノード及び前記初期候補群の残存する各メンバから第2特徴群の各々の値を抽出する工程をに有し；第1のハッシュ関数群を利用して、前記メンバ及び前記ターゲットデータノードの双方から抽出される第1特徴群を比較することが：前記第1のハッシュ関数群のうちの各々のハッシュ関数について、前記ターゲットデータノードの前記第1特徴群の値に対して前記ハッシュ関数を実行することによる第1結果と、前記メンバの前記第1特徴群の値に対して前記ハッシュ関数を実行することによる第2結果とを取得し、前記第1結果と前記第2結果とを比較すること；を含み、及び/又は第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較することが：前記第2のハッシュ関数群のうちの各々のハッシュ関数について、前記ターゲットデータノードの前記第2特徴群の値に対して前記ハッシュ関数を実行することによる第1結果と、前記残存するメンバの前記第2特徴群の値に対して前記ハッシュ関数を実行することによる第2結果とを取得し、前記第1結果と前記第2結果とを比較すること；を含む。
【００５０】
何れのケースにおいても比較の結果は、ハッシュ関数結果の近接度(closeness)を要約する値であってもよい。例えば、実施形態は、各々のケースにおいて第1結果と第2結果との間の距離を比較し、結果の間の平均距離を表す値を生成するアルゴリズムを実行してもよい。一方、結果の間の距離は適切な値でなく、評価される全体は、群中のハッシュ関数のうち合致した数であってもよい。例えば、前記部分的比較処理の結果は、メンバが初期候補群から除外する基準を充足するか否かの指標、及び/又は、前記第1結果が前記第2結果に合致する前記第1のハッシュ関数群の割合である；及び/又は前記完全な比較処理の結果は、前記第1結果が前記第2結果に合致する前記第2のハッシュ関数群の割合である。
【００５１】
有利なことに、そのような結果は、計算の際に簡易であり、従って、リコンシリエーション処理により課される全体的な処理負担を抑制することを支援する。
【００５２】
本発明の別の実施形態は、複数の相互接続されるデータノードをエンコードするデータグラフを保存するように構成されるデータストレージシステムのコントローラであって、前記データグラフに挿入するためのターゲットデータノードを受信するように構成されるリコンシリエーション処理モジュールを有する。前記リコンシリエーション処理モジュールは：前記複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングするように構成されるフィルタリングモジュールであって：前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理であって、第1のハッシュ関数群を利用して、前記メンバの各々及び前記ターゲットデータノードから抽出される第1特徴群を比較する部分的比較処理を実行すること；及び前記部分的比較処理の結果が1つ以上の除外基準を充足する場合に、前記初期候補群中の当該メンバと、当該メンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける前記初期候補群中の何らかの他のメンバとを除外すること；により、フィルタリングを行い；及び、前記初期候補群の残存するメンバの各々が前記ターゲットデータノードとの前記部分的比較処理を完了するまで、前記除外基準が充足される場合に、前記実行すること及び前記除外することを反復する、フィルタリングモジュール；を有し、前記リコンシリエーション処理モジュールは、前記フィルタリングモジュールにより出力される前記初期候補群の残存するメンバの各々と前記ターゲットデータノードとの間の完全な比較処理であって、第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較する完全な比較処理を実行する完全比較処理モジュール；をさらに有し、前記第2のハッシュ関数群は、前記第1のハッシュ関数群より多いハッシュ関数を含む。
【００５３】
コントローラは、単独のコンピュータリソースにおいてセントラル化されるコントローラとして、複数のコンピュータリソースが協調することによるセントラル化されるコントローラとして、或いは、分散ストレージシステムの個々のコンピュータリソースそれぞれにおける複数の同等なコントローラのうちのコントローラとして実現されることが可能である。例えば、コントローラはストレージシステムのコンピュータリソースで動作するプログラムにより提供されてもよいし、1つ上の他のコンピュータリソースは、1データベースが複数のコントローラを介してアクセス可能であるように同等なプログラムを走らせていてもよい。コントローラはデータベースコントローラ又はデータベースマネジャのように言及されてもよい。
【００５４】
各々の機能モジュールは、モジュールの機能を実行するように具体的に構成されるハードウェアにより実現されてもよい。機能モジュールは、コンピュータ処理ユニットにより実行される場合に、命令又は実行可能なプログラムコードにより実現されてもよく、命令又は実行可能なプログラムコードは、機能モジュールに帰属する機能をコンピュータ処理ユニットに実行させる。コンピュータ処理ユニットは、(オペレーティングシステムを介して又は他の手段を介して)メモリ、ストレージ、I/Oデバイス、ネットワークインタフェース、センサ及びコンピュータ装置のその他のコンポーネントのうちの1つ以上と協働して動作し、機能モジュールに帰属する機能を実現してもよい。モジュールは、ユニットとして言及されてもよいし、方法、プログラム、処理又はプロセスのステップ、ステージ、段階又は工程であってもよい。
【００５５】
本発明の他の実施形態は、リソースがグラフのノードとして表現されるデータのグラフを保存するデータストレージシステムを提供し、データストレージシステムは、データのグラフの中のデータのセグメントを保存するようにそれぞれ構成される複数のストレージユニット；及び上記の及び/又は何れかの実施形態によるデータベースコントローラを有する。当然に、データストレージユニットは、コンピュータリソースの一例であり、ストレージ(記憶)に加えて、処理機能及び制御/管理機能を有してもよい。
【００５６】
ストレージユニットのそれぞれはコンピュータリソースであってもよく、例えば、それらの各々は、ストレージユニットに加えて、プロセッサ、メモリ及び/又は追加的なコンポーネント(例えば、ネットワークインタフェース、マザーボード、入力/出力デバイス等)を含んでもよい。
【００５７】
本発明の別の実施形態は、コンピュータにより実行される場合に、本発明を組み込む方法をコンピュータに実行させるコンピュータプログラムを提供する。更に、本発明の別の実施形態は、1つ以上のコンピュータにより実行される場合に、本発明を組み込むデータベースコントローラとして、1つ以上のコンピュータを機能させるコンピュータプログラムを含む。本発明を組み込むコンピュータプログラムは、非一時的な記憶媒体のようなコンピュータ読み取り可能な記憶媒体に保存されてもよいし、単独のコンピュータプログラム又は複数のサブプログラム一式として提供されてもよい。
【００５８】
本発明の実施形態に必須ではないが、実現手段は、グラフがコンピュータリソースの分散ネットワークに保存されるシステムを含んでもよい。コンピュータリソース(ストレージノード)の分散ネットワークは、1つより多い数の互いに通信する個別的なストレージユニットのシステムを含んでもよい。通信形態の実例はピアツーピア(P2P)であり、コンピュータリソースの分散ネットワークは、ストレージノードのピアツーピア・ネットワークであってもよい。P2Pは、ピア同士の間でタスク又はワークロードを分ける分散アーキテクチャである。ピア(個々のストレージノード又はプロセッサ)は、対等な権利を有し、アプリケーション中の対等な参加者である。各々のピアは、サーバ又は固定ホストによる集中制御を必要とすることなく、他のネットワーク参加者に対して直接的に利用可能なリソース(例えば、処理パワー、ディスクストレージ又はネットワーク帯域幅など)の一部をなすように構成される。サーバが供給してクライアントが消費する従来のクライアントサーバモデルとは異なり、ピアはリソースのサプライヤ及びコンシューマの双方であると考えられる。有利なことに、P2Pシステムは、対数的な通信コストとともに、メッセージを送受信する多数のストレージユニットのグループを維持することが可能である。
【００５９】
本発明の実施形態が実現される形態に依存して、特定のノードとともにリコンシリエーション処理が実行されるノードの部分集合に所属しかつコンピュータリソースに保存されるノードとターゲットデータノードとの間で、リコンシリエーション処理は、コンピュータリソースの分散ネットワーク内で1つより多いコンピュータリソースで同時に実行されてもよい。
【００６０】
図1は実施形態による手順の全体を示す。ステップS101ないしS107はフィルタリング手順を表す。そのようなフィルタリング手順は、データベースコントローラのフィルタリングモジュールにより実行されてもよい。ステップS108は完全比較処理手順を表す。そのような完全比較処理手順は、データベースコントローラの完全比較処理モジュールにより実行されてもよい。
【００６１】
全体的なフィルタリング手順の概略に示されるように、データ項目の集合C(これは、初期候補群の具体例である)、所定の類似度測定値α、フィルタリングf及びクエリ(問い合わせ)qの下で、類度サーチ/比較は、∀c∈S.(α(c,q)∈f)であるように、アイテム集合S⊆Cを取り出す。フィルタリング手段は、上位N個の候補、或いは、クエリqを満たす所定の類似度閾値より大きな全ての候補に戻ることが可能である。
【００６２】
(概念、プロパティ及びインスタンス等であってもよい)オントロジ的なエンティティとして言及されてもよいデータノードの1つ以上の類似度の計算は、(エンティティの意味を一緒に説明する)ノードから取り出される選択されるオントロジ的な又は意味論的な特徴(これは、第1及び第2特徴群の具体例である)の高次元ベクトルに基づいていてもよい。局所性鋭敏型ハッシュ(locality  sensitive  hashing：LSH)は、(フィルタリングの基礎として)初期候補の除去に適用されることが可能であり、その結果のセットが線形比較(これは、完全な比較処理の具体例である)に委ねられる。初期の除去は、線形比較に委ねるデータセットのサイズをかなり削減することが可能であり、従って、フィルタリング手順はリコンシリエーション処理に必要な時間及び処理リソースをかなり減らすことが可能になる。
【００６３】
フィルタリング手順はステップS101から始まり、初期候補群中のメンバが、ターゲットデータノードとの部分的比較処理のために選択され、ターゲットデータノードは初期候補群とともにリコンサイルの処理がなされるデータノードである。選択に関する唯一の制約は、ターゲットデータノードとの部分比較処理が未だ実行されてないメンバを選択することである。データのリコンシリエーションはインスタンスレベルで実行されるが、このため、ステップS101でメンバが選択される初期候補群はインスタンスデータノードのみを含んでもよく、概念的なスキーマ又はモデルの存在により、候補の除外において重要な役割を演じることが可能になる。例えば、取り出される特徴は、概念的なスキーマ又はオントロジモデルの特性を利用してもよい。
【００６４】
ステップS101は、初期候補群のうち選択したメンバをステップS102に出力し、ステップS102では、選択されたメンバとターゲットデータノードとの間で部分的比較処理が実行される。部分的比較処理は、第1のハッシュ関数群を使用して、メンバ及びターゲットデータノードの双方から取り出される第1特徴群を比較することを含む。比較の結果はステップS102によりステップS103に出力される。
【００６５】
特徴の選択(最も有用なオントロジ特徴を発見し、その特徴を、第1及び/又は第2特徴群に含めること)又はハッシュ関数の選択(ハッシュ関数ファミリの中から適切な数(right  number)のハッシュ関数を発見すること)に関し、マシン学習アルゴリズムが使用されてもよい。
【００６６】
ハッシュ関数のファミリの選択は、次のようにして実行されてもよい：
−  アルゴリズムを固定するが、アルゴリズムのパラメータは調整される。パラメータはアルゴリズムの規定パラメータとすることも可能である：例えば、cが或る関数f(X,c)=aの定数である場合に、cの値を調整することは、若干異なる「f」を生成する。パラメータはアルゴリズムの入力とすることも可能である：例えば、Xを整数に射影する別の手法を得るために、f(X)=aによるXの成分の部分集合が組織的に選択されてもよい。
【００６７】
−  目的は、候補及びターゲットを整数に射影する大きな均一なアルゴリズム(large  homogeneous  algorithm)を構成し、高次の特徴ベクトル(又はベクトルの部分集合)を比較する代わりに、結果の整数を速やかに比較することである。
【００６８】
第1のハッシュ関数群(実際の比較処理で使用されるもの)として、実施形態は、完全な比較処理のために選択されるn個のハッシュ関数のうちの一部分(部分集合)m個を使用してもよい。その根拠は、1番目からm/nのハッシュ関数の全部又は一部に基づいて、メンバをターゲットデータノードと比較した後に(ここで、ハッシュ関数の必要数としてのnに関し、m＜＜nであり、mは第1群のハッシュ関数の数であり、nは第2群のハッシュ関数の数である)、2つのデータノードが同等(等価)であると判定される確率を推定することが可能である、ということである。すなわち、(例えば、閾値未満又は一定の最低比率のような)ターゲットノードと同等であると判定されることについて非常に確率を有するメンバが特定されることが可能であり、残りの(n-m)個のハッシュ関数の処理は回避される(全てのハッシュ関数の完全な処理は既知の結果から大きくは逸脱しない確実性(confidence)に基づく)。
【００６９】
(完全な比較処理に使用されるものである)第2のハッシュ関数群に属するハッシュ関数の数であるnを決定する例示的な手順に関し、以下の原理が使用されてもよい：
ハッシュ関数の全体的な数は、ハッシュ関数グループ(群)のサイズ(g)及び各々の特徴について計算されるハッシュ関数の数(k)という2つの要素によって決定される。必要なハッシュ関数の総数nは、n=g*kである。従って、手順は、複合的な特徴/シグネチャ(署名)を得るために、k個のハッシュ関数の結果を組み合わせることを含んでもよい。従って、各々のデータノードに関し、ハッシュ関数の「g」個のファミリの全体が、各々の「f」の「g」次元空間を形成するために使用される。より具体的に言えば、予想される誤差マージン「e」の下で、「k」が固定される場合、gは次のようにして計算されることが可能である：
g=loge/log(1-t^k)
ここで、tは、所定の閾値でありデータベースのアドミニストレータのレベルで設定可能である。一例として、例えばk=1としてkの条件を緩和すると、ハッシュ関数ファミリの総数は次のようにして算出されることが可能である。
【００７０】
g=loge/log(1-t)
これはハッシュ関数の数を選択するための手順の単なる一例に過ぎない。要するに、第2のハッシュ関数群に属するハッシュ関数の数nは、loge/log(1-t^k)という数式を用いて求められてもよく、eはリコール(recall)であり、tは所定の閾値であり、kは各々の特徴に対するハッシュ関数の数である。kの例示的な値は1である。第1群について選択されるハッシュ関数の数mは、データベースのアドミニストレータにより設定可能であり、その選択(値)は、処理のオーバーヘッドと、初期候補群からメンバを除外するように求められる確実性との間のバランスを表す。
【００７１】
ステップS102における局所性鋭敏型ハッシュは、同じハッシュ関数ファミリからの複数のハッシュ関数を利用して、一群のk個の特徴の中のシグネチャ(signature)を計算することにより、2つのエンティティ間の類似度を近似し、この場合において、kは、可能性のある全ての取り出される特徴のうちの部分集合を表す。この場合、完全な特徴ベクトルによる完全な比較は回避され、絶対に必要なものについてのみ比較が実行され、その理由は、第1特徴群は第2特徴群より小規模だからである。
【００７２】
ステップS103において、部分的比較プロセスの結果により、除外条件(又は除外判断基準)が満たされるか否かが判定される。充足されるか否かという単独の基準が使用されてもよい。代替的に、複数の基準が使用されてもよく、除外条件は充足されていると判定されるには、そのうちの所定数の基準が充足されなければならない(例えば、所定数は、全部であってもよいし、或いは、少なくとも1つであってもよい)。代替的に、除外条件は条件に応じて分岐してもよいし(staggered)或いは段階的に行われてもよく、例えば、第1の除外条件が充足されない場合に、追加的な除外条件が充足されるか否かを判定するために別の部分的比較処理が実行されてもよい。
【００７３】
部分的比較プロセスを実行し(S102)、部分的比較プロセスの結果が除外条件を充足するか否かを判定する(S103)ための例示的な手順が、以下に説明される。この例示的な手順において、部分的比較処理は2段階で実行され、第1段階の後に、いくつかのメンバが除外条件を充足していると考えられ(これらのノードに対する部分的比較処理は完了している)、いくつかが第2段階を待機するリストに加えられる(これらのノードに対する部分的比較処理は未だ完了していない)。第2段階を待機するリストに載るものは、依然として初期候補群のメンバであると考えられるが、それらは、ステップS104による各自自身の部分的比較処理の完了の際に又はステップS106により除外される。
【００７４】
例示的な手順では、次の事項が想定される。
【００７５】
−  dは、リコンサイルされるべきデータ項目であり(これは、ターゲットデータノードの具体例である)、抽出された特徴のベクトルvdにより表現される(これは、ターゲットデータノードから抽出される第1群(及び場合によっては第2群)の特徴の具体例である)；
−  Iは一群のインスタンスデータであり、dはその一群のインスタンスデータに対してリコンサイルされ(これは、初期候補群の具体例である)、αi∈Iにおける各々の項目(これは、初期候補群のメンバの具体例である)は、抽出された特徴のベクトルvαiにより表現される(これは、メンバから抽出される第1群(及び場合によっては第2群)の特徴の具体例である)；
−  Ωは完全なナレッジモデルである(これは、初期候補群の具体例であるが、追加的なオントロジモデルデータ又はスキーマデータを有する)；
−  tは、所定の閾値であり、実施の条件に基づいて設定可能である；
−  p及びqは、0及び1の間の実数であり、pは所定の確率閾値の具体例であり、qは意味の類似度閾値の具体例である；
−  hj∈Hは、ハッシュ関数ファミリから選択される任意のハッシュ関数である(場合によってはランダムに選択される)；
−  (ステップS105で評価されるような)意味論的な類似度はσ()である；
−  m/nは、完全な比較プロセスの一部として実行される数に対する、部分的比較処理の一部として実行されるハッシュ関数の数を示す(すなわち、これは、第2のハッシュ関数群のサイズに対する第1のハッシュ関数群のサイズの具体例である)。部分的比較処理の第1段階において、第2段階に進むメンバのリストが生成され(リストは、メンバ又はメンバの指定が保存又は維持される形式に限定されることなく、広義にグループを意味するように解釈される)、進まないものは初期候補群から除外される。第1段階は、全てのαiの和集合(union)を見出し、Hに属する複数の部分集合のうちの何れかは、αiについて実行される場合に、dについて実行される場合と同じ結果を生成する。
【００７６】
第1段階は次のようにして実行されることが可能である：
−  m個のハッシュ関数に属する個数の部分集合の各々について、ハッシュ結果を算出し、ハッシュ関数の部分集合に対するハッシュ結果がd及びαiの間で合致する場合には反復を終了し、第2段階に進むようにリストに追加する；
−  所定の上限数の部分集合について一致が見られない場合(これは、除外条件の具体例である)、αiを否定的な候補群(ネガティブ候補群)Cnegに追加する(初期候補群からαiを除外することと等価である)；
−  初期候補群Iのうちの他のメンバαkとαiとの間の意味的な類似度又は意味的な相関性を評価し、閾値と比較し、閾値を超える場合、αkも初期候補群から除外する、すなわち、σΩ(αi,αk)＞qならば、αkをCnegに加える。
【００７７】
各々のメンバが、Cnegに追加される、或いは、第2段階に進むリストに加えられると、第2段階が開始される。リストは、Cnegに追加される全てのデータノードが除外された後に、事実上、何が初期候補群に残っているかを示す。第2段階において、更なる部分的比較処理が実行され、その結果は別の除外条件に関連して評価される。
【００７８】
部分的比較処理の第2段階において、第1群のm個のハッシュ関数に対する結果は、部分的比較処理が実行されているメンバ(αi)及びターゲットデータノードについて取得される。第1群に含まれるm個のハッシュ関数のみに基づいて、完全な比較処理段階において(すなわち、完全なn個のハッシュ関数が実行される場合に)同等であると判断されるαi及びdの尤度(確からしさ)(pr)の推定値が生成される。
【００７９】
第2段階はつぎのように要約することが可能である：
pr[s(d,αi)|m/n]＜p  ならば、αiをCnegに加える。
【００８０】
上記と同様に、Cnegに追加することは、初期候補群から除外することと等価であり、Cnegに追加されるメンバについては更なるリコンシリエーション処理は実行されないことを示す。第2段階を裏付ける根拠は、n個のハッシュ関数のうちのm個に基づいて、「d」及び「αi」が互いに一致するか否かの確率を推定することが可能である、ということであり、ここでmはnより十分に小さい(例えば、nのうちの0ないし10％の間であってもよいし、或いは、nのうちの0ないし20％の間であってもよい)。確率prが閾値pより小さい場合(これは、除外条件が満たされる場合の具体例である)、αiは更なる比較から除外され、閾値は、ユーザにより予め選択されることが可能であり、或いは、データグラフのパラメータとして設定されてもよい。この場合において、システムは、完全な比較処理には必要となっていた残りの(n-m)個のハッシュ結果の処理を回避する。
【００８１】
例えば、多項式分布を利用して仮説検定を実行し、データノードが同等である旨の仮定に基づいて、取得される合致度(すなわち、第1群におけるハッシュ関数の総数のうちのx個が合致すること)又はそれ未満を取得する仮説を検査することにより、確率が生成されてもよい。代替的に、ランダムに選択されるデータノードが、取得される合致度又はそれ未満を得る尤度を評価することにより(上記と同様に、多項式分布又はそれに等価なものを利用して)(閾値と比較するための指標である尤度を1からマイナスしたものとともに)、確率が生成されてもよい。
【００８２】
メンバαiが計算されたその確率prを有し、除外条件を充足すると、(Cnegに追加されてはいない)部分的比較処理の第2段階に対するリストの他のメンバαk同士の意味的な類似度又は意味の相関性が、算出されて閾値qと比較される。閾値qを上回ると、αkはCnegに追加され、すなわち、σΩ(αi,αk)＞qならば、αkをCnegに加える。意味的に関連する全てのαkに関し、αkをCnegに追加し、この場合、σΩ(αi,αk)＞qである。除外条件を充足しないメンバであって、Cnegに追加される他のメンバに対する意味の類似性によりその後にCnegに追加されていない任意のメンバが、フィルタリングプロセスの後に残っており、それらが完全な比較処理に委ねられることになる。
【００８３】
部分的比較処理の結果により、除外条件が充足されると判断される場合、フローはステップS104に進む。ステップS104において、選択されるメンバ(ターゲットデータノードとの部分的比較処理により除外条件を充足するメンバ)は、初期候補群から除外される。
【００８４】
ステップS105において、初期候補群から未だ除外されてない任意のメンバは、ステップS104で除外されたメンバとの意味的な類似性について評価される。初期候補群から未だ除外されてないメンバは、ターゲットデータノードとの部分的比較処理が未だ実行されてないメンバと、ステップS103における部分的比較処理の結果が除外条件を充足してないメンバとを含む。意味的な類似性の評価のために閾値が適用され、除外されたメンバと閾値を超える意味的類似度を有すると評価される初期候補群中の如何なるメンバも、ステップS106において初期候補群から除外される。
【００８５】
ステップS106において、除外されたメンバと閾値以上の意味的類似度を有すると評価されたメンバの除外は、あるエンティティが、ターゲットデータノードと所定の閾値未満の類似度を有する場合に(部分的比較処理で評価される)、意味的に関連するエンティティも確率モデルに対して除外されることが可能である、という仮定に基づく。確率モデルは、部分的比較処理で計算される類似度に基づいて、メンバ及びターゲットノードデータが完全な比較処理で意味的に等価であると判断される尤度を表す値を生成し、及び、確率モデルは、初期候補群中の他のメンバが、除外される対象のメンバとどの程度類似していなければならないか(或いは、どの程度意味的に関連していなければならないか)についての閾値を設定するために使用されることが可能である。そのように関連するエンティティに関し、ハッシュ処理は必要とされない。そのように意味的に近いエンティティの場合、排除は速やかに実行可能であり、別のハッシュ計算は実行されなくてよい。
【００８６】
実施形態において、除外条件の充足に起因して(S104)或いは除外条件を充足するノードとの意味的類似性に起因して(S106)初期候補リストからメンバを除外することは、様々な形態をとってよい。除外されるメンバとターゲットデータノードとの間では、更なる部分的比較処理も完全な比較処理も実行されない(すなわち、更なるリコンシリエーション処理はなされない)効果をもたらす。これは、ターゲットデータノードとの完全な及び部分的な比較処理を待機するデータノードのリストから除外する形式をとってもよい。代替的又は追加的に、これは、完全な比較処理が実行されるべきデータノードについてのコンパイルされるリストから省略する形態をとってもよい。
【００８７】
ステップS105における閾値との簡易な比較に対する代替例を説明する。第1具体例は、あるデータ項目が、初期候補群から除外されるメンバに意味的に近い場合、それらは肯定的な候補(ポジティブ候補)として提供しない、という仮定を活用する。そのような仮定は以下の例示的な数式に組み込むことが可能である：
c-(αk)=s(d,αi)×(1+log(γ・σ(αi,αk)+e))
ここで、eは0を超える対数をとることを避ける程度に十分小さな数であり、γは意味の相関性(correlation)の重要度を調整するための係数である。c-は、所与のデータ項目αkのネガティブ候補メンバーシップのネガティブ候補性又は確実性であり、αiとともに初期候補群からαkを除外するか否かを判定するために閾値と比較される。基本的には、σ(αi,αk)が大きい場合(これは、2つのデータ項目が意味的に類似することを示す)、c-(αk)及びs(d,αi)はポジティブカップリング(positive  coupling)である。αiがネガティブ候補になる場合、αkもそのようになる。σ(αi,αk)が小さい場合、αkがネガティブとして判断されるべきか否かは不定のままである(ただし、ネガティブ候補値を有する傾向が強い)。
【００８８】
第2具体例は、αk及びαi間の距離δ(αi,αk)を測定し、測定された距離を活用してc-(αk)のネガティブ候補性を評価する(上記と同様に、αiとともに初期候補群からαkを除外するか否かを判定するために閾値と比較されることが可能である)。c-(αk)及びs(d,αi)はδ(αi,αk)に関してポジティブカップリングである。δ(αi,αk)が大きい場合(1に向かうことは、αi及びαkが意味的に互いに否定的である(又は対極にある)ことを示す)、αiのネガティブ候補性は、その否定(対極)のαkのポジティブ候補性をもたらす。αkがポジティブ候補であるか否かは、s(d,αi)の値なしには不定のままである。δ(αi,αk)が小さい場合、c-(αk)の確実性はかなり減少する。そのような関係についての実現例は、以下の数式に従って示すことが可能である：
【数１】
2016071865.tif 000003
距離測定値δ(αi,αk)及び類似度σ(αi,αk)は相補的ではないことに留意を要する。両者は別様に実現されることが可能である。例えば、σ(αi,αk)は、階層構造上の類似測定値に基づくことが可能である。Ωは、概念階層のような最小スパニングツリーが存在するグラフであるとする。あるデータモデルに関し、人為的なトップ(top)が導入される場合(すでには存在しない場合)、単独のスパニングツリーが保証されることがかのうである。オントロジの場合、そのトップは、全てのトップレベル概念という共通の親概念であり、例えば、＜OWL:Thing＞である。データベーススキーマの場合、スパニングフォレスト)は、人為的なトップによりツリーに変換されることが可能である。
2つのデータ項目の概念的な相関性は、次のようにして算出されることが可能である：
【数２】
2016071865.tif 000004
len(x,T)は、トップとデータ項目との間の経路の長さであり、事実上、概念階層におけるxの深さである。len(x,y)はx及びyの間の最短経路の長さである。
【００８９】
δ(αi,αk)は、明示的なネゲーション(negation)又はディスジョイント(disjoint)が存在するか否かに依存するべきである。例えば、αi∈neg(αk)∈Ω又はαi∩αk=φである場合、δ(αi,αk)=1である。他の既存の意味論的なメトリック/距離測定値を使用することも可能である。
【００９０】
ステップS106の後、又は、選択されたメンバはステップS103で除外条件を満たさないと判断された場合、フローはステップS107に進む。ステップS107では、ターゲットデータノードとの部分的比較処理が未だ完了してない何らかのメンバが初期候補群中に残っているか否かの検査が実行される。検査結果がYESである場合(存在する場合)、フローはステップS101に戻り、ターゲットデータノードとの部分的比較処理を未だ完了してない初期候補群中に残っている何れかのメンバが選択される。初期候補群に残っているメンバが存在しない場合、或いは、残りのメンバの全てが既にターゲットデータノードとの部分的比較処理を実行している場合、フローはステップS108に進む。
【００９１】
ステップS108では、初期候補群の残りのメンバとターゲットノードとの間の完全な比較処理が実行される。ノードのペアの間の完全な比較処理は、より多くのハッシュ関数が実行されること；及び比較の際により多くの特徴(又は属性)が抽出されることのうちの双方又は一方に起因して、同じノードペア間の部分的比較処理よりも演算コストが大きい。完全な比較処理は、2つのデータ項目が意味的に等価であると考えられるか否かに対する判断を生じることによっても特徴付けられる。これに対して、部分的比較処理は、メンバが意味的に等価であると判断されることについての尤度であって完全な比較処理を実行することを正当化する程度に十分な尤度が存在するか否かに対する判断によって特徴付けられる。完全な比較処理の具体例は、初期候補群に残っているメンバ間でn個のハッシュ関数の完全なリストとともにペアワイズ線形比較を実行し、最終的な類似度を算出し、両者が意味的に同等であるか否かを判断することである。
【００９２】
ステップS103は、部分的比較処理の結果が、完全な比較処理を実行すべき条件を充足するか否かを判断するステップと等価であり、充足する場合、そのメンバを、完全な比較処理を待機しているデータノードのリストに肯定的に追加する。この等価的なシナリオの場合、完全な比較処理が実行されるべき条件を充足しない他のメンバに意味的に類似すると判断されることにより、メンバが、完全な比較処理を待機するデータノードのリストから事後的に除外されることが可能である点に留意すべきである。
【００９３】
反復の各々において増やされるデータノードを比較するために使用される特徴群のサイズとともに増加する形式でリコンシリエーション処理が実行される実施形態が以下に開示される。
【００９４】
オントロジでは、通常、オントロジのエンティティの間の様々なタイプの関係及び様々なタイプのエンティティ属性が存在するので、より多くの意味的な手掛かり(clue)を含めることにより成長する様々な特徴ベクトルにハッシュ処理を適用することが可能である。そのように実行するために、初期の特徴ベクトルの次元は小さく維持されてもよい。
【００９５】
例えば、方法ステップは次のように実現されることが可能である：
第1反復において、特徴ベクトルは、概念階層に沿って到達可能な親エンティティからの属性のみを含み；
第2反復において、特徴ベクトルは、全ての属性(これは、属性の完全な集合である)を含み；及び
第3反復において、特徴ベクトルは、全てのオブジェクト特性(データノードを含む2つのリソースを接続するエッジ)を含む。
【００９６】
各々のステップは、先行するステップよりも強力かつ繊細な除外する「力(power)」を提供し、特徴ベクトルの増加するサイズに起因して、演算コストは高くなる。
【００９７】
所与のステップで考慮に入れられる属性(特徴)は、先行するステップからの属性の上位集合(superset)であるので、早期のステップで除外されるインスタンスは、より多くの証拠が存在する場合には、フォールスネガティブ(false  negative)ではないことが保証される。
属性(特徴)抽出は、全ての概念、特性及びインスタンス名/値を適切な文字列として取り扱う標準的なテキストインデキシング方法(例えば、TF-IDF)を利用して簡易に実行されることが可能である。
【００９８】
プロセスは次のようにして行われてもよい：
始めに、ステップS101ないしS108の第1反復として、フィルタリング及び完全な比較処理が実行される。次に、フィルタリング及び完全な比較処理の1つ以上の追加的な反復であるS101-S108が実行される。追加的な処理の各々において、各々の追加的な処理に対するデータノードの初期候補群は、先行する反復のフィルタリングに続く先行する反復の初期候補群の残存するメンバである。選択的に、各々の追加的な反復の第1特徴群は先行する反復の第1特徴群の上位集合であり、各々の追加的な反復の第2特徴群は先行する反復の第2特徴群の上位集合である。別の選択肢として、各々の反復に関し、第1特徴群及び第2特徴群は同じであってもよい。先行する反復で追加されていたものは以後の反復で除外されてもよいように、最近実行したばかりの完全な比較処理の結果生じる同等リンクは真正であると判断される。
【００９９】
本発明の実施形態において、知識(ナレッジ)、事実及び/又は記述(ステートメント)は、ノード及びエッジのグラフによって表現され、ノードは記述又は表現されるエンティティであり、エッジはそれらのエンティティ間の関係又は関連性(relationship)である。本発明の実施形態は、グラフデータを、直接的にすなわちノード及びエッジとして保存するように構成されてもよい。しかしながら、データ構造に基づく他の方法が使用されてもよい。
【０１００】
例示的な前提とするデータストレージ構造に関し、グラフのデータはトリプル(3つ組)としてエンコードされ、各々のトリプルは主語又はサブジェクト(subject)、述語又はプレディケート(predicate)及び目的語又はオブジェクト(object)を有し、グラフのノードはトリプルのサブジェクト及びオブジェクトであり、トリプレットのプレディケートはトリプルのサブジェクトとオブジェクトとの間のリンクを示す。
【０１０１】
選択的に、トリプルはRDF(Resource  Description  Framework)トリプルであってもよい。本明細書を通じて、「RDFトリプル」という具体的な言及がなされる場合、それはRDF規格に従うトリプルの例示的な形態であることが、理解されるべきである。更に、「トリプル」という言い方は、対象におけるトリプルがRDFトリプルである可能性を含む。同様に、本明細書で言及されるRDFプロセッサは、APIラッパ(API  wrapper)及び保存されるデータ項目の間のやり取りに使用されるプロセッサの具体例である。
【０１０２】
リソース・ディスクリプション・フレームワーク(RDF)は、情報の概念的な記述及びモデリングのための一般的な方法であり、セマンティックモデリング又はセマンティックナレッジモデリングのための規格である。セマンティックネットワークにおける情報のモデリングを標準化することは、共通のセマンティックネットワークで動作するアプリケーション間の相互運用性を許容する。RDFは、RDFにおける語彙(vocabulary)を記述する言語としてRDFスキーマ(RDFS)を提供することにより、曖昧でない正式な意味を有する語彙を維持する。
【０１０３】
選択的に、トリプルの要素(要素は述語、目的語又は主語である)のうちの1つ以上の各々は、ユニフォーム・リソース・ロケータ(URI)である。RDF及び他のトリプルのフォーマットは、URIのようなウェブ識別子を利用するモノ(things)(すなわち、オブジェクト、リソース又はインスタンス)を特定し、簡易な特性及び特性値により、特定されたそれらの「モノ」を記述する考え方を前提とする。トリプルの観点からは、ウェブリソースの実現において、主語はエンティティを記述するウェブリソースを特定するURIであってもよく、述語は特性のタイプ(例えば、色)を特定するURIであってもよく、目的語は対象のエンティティに帰属する特性のタイプの特定のインスタンスを指定するURIであってもよい。URIを利用することは、トリプルが、簡易なステートメント、関連するリソースを、リソースを表現する弧(arc)及びノードのグラフとして表現できるようにするだけでなく、それら各自の特性及び値をも表現できるようにする。RDFグラフは、SPARQLプロトコル及びRDFクエリ言語(SPARQL)を用いて問い合わせ又は検索されることが可能である。これは、ワールド・ワイド・ウェブ・コンソーシアムのRDFデータ・アクセス・ワーキング・グループDAWGにより標準化され、主要なセマンティックウェブ技術と考えられる。SPARQLは、トリプルパターン、コンジャンクション(conjunction)、ディスジャンクション(disjunction)及び選択的なパターンからクエリを構成することを許容する。
【０１０４】
トリプルは、グラフデータを複数の主語-述語-目的語の表現として特徴付けることにより、グラフデータのエンコードをもたらす。この場合において、主語及び目的語はグラフデータのグラフノードであり、従って、エンティティ、オブジェクト、インスタンス又は概念であり、述語は主語及び目的語の間の関連性の表現である。述語は、指定されるタイプのリンクを目的語に提供することにより、主語に関する何かを述べる。例えば、主語はウェブのリソース(例えば、URIによるリソース)を示し、述語はリソースの特定の属性、特性又は態様を示し、目的語はその属性、特性又は態様のインスタンスを示す。言い換えれば、トリプルのステートメントの集まりは、有向グラフのデータを本質的に表現する。RDF規格はそのようなトリプルの定式化された構造を提供する。
【０１０５】
様々な形態(ソフトウェア/方法/装置)が別々に議論されるが、ある形態に関連して説明されるものの特徴及び結論は別の形態にも等しく適用可能であることが理解されるべきである。従って、方法の特徴が説明される場合、装置の実施形態がその特徴を実行する或いは適切な機能を提供するように構成されるユニット又は装置を含んでよいこと、及び、プログラムは、それらが実行されるコンピュータ装置に、その方法の特徴を実行させるように構成されてよいことが、認められる。
【０１０６】
上記の何れの形態においても、様々な特徴は、ハードウェアにおいて、又は、1つ以上のプロセッサで動作するソフトウェアモジュールとして実現されてよい。一形態の特徴は他の任意の形態に適用されてもよい。
【０１０７】
本発明は、本願で説明される任意の方法を実行するコンピュータプログラム又はコンピュータプログラムプロダクト、及び、本願で説明される任意の方法を実行するプログラムを保存するコンピュータ読み取り可能な媒体も提供する。本発明を組み込むコンピュータプログラムは、コンピュータ読み取り可能な媒体に保存されてもよいし、或いは、例えば、インターネットウェブサイトから提供されるダウンロード可能なデータ信号のような信号の形態であってもよく、或いは、他の任意の形態とすることも可能である。
【０１０８】
以上の実施の形態に関し、更に以下の付記を開示する。
【０１０９】
（付記1）
複数の相互接続されるデータノードをエンコードするデータグラフとともにターゲットデータノードをリコンサイルする方法であって、
前記複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングする工程であって：
前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理であって、第1のハッシュ関数群を利用して、前記メンバの各々及び前記ターゲットデータノードから抽出される第1特徴群を比較する部分的比較処理を実行すること；及び
前記部分的比較処理の結果が1つ以上の除外基準を充足する場合に、前記初期候補群中の当該メンバと、当該メンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける前記初期候補群中の何らかの他のメンバとを除外すること；
により、フィルタリングを行う工程；及び
前記初期候補群の残存するメンバの各々が前記ターゲットデータノードとの前記部分的比較処理を完了するまで、前記除外基準が充足される場合に、前記実行すること及び前記除外することを反復する工程；
を有し、当該方法は、
前記フィルタリングする工程に続いて、前記初期候補群の残存するメンバの各々と前記ターゲットデータノードとの間の完全な比較処理であって、第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較する完全な比較処理を実行する工程；
をさらに有し、前記第2のハッシュ関数群は、前記第1のハッシュ関数群より多いハッシュ関数を含む、方法。
【０１１０】
（付記2）
前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理が、サブセット結果照合手順を含み、前記サブセット結果照合手順は：
前記第1のハッシュ関数群からハッシュ関数の部分集合を選択すること；
前記メンバの第1特徴群に対して前記ハッシュ関数の部分集合を実行した結果と、前記ターゲットデータノードの第1特徴群に対して前記ハッシュ関数の部分集合を実行した結果とを取得すること；を含み、
前記サブセット結果照合手順は、(i)ハッシュ関数の同じ部分集合に関し、前記メンバについて取得される結果及び前記ターゲットデータノードについて取得される結果が、合致基準を充足する；或いは(ii)単独のメンバに対する前記サブセット結果照合手順の反復回数の所定の上限に達するまで、同じメンバについての反復の各々に異なる一のハッシュ関数群を選択する反復的な方法で実行され；
前記除外基準は：
前記合致基準を充足することなく、単独のメンバに関し、前記単独のメンバに対する前記サブセット結果照合手順の反復回数の所定の上限値に到達すること；及び
前記合致基準が充足され、前記ターゲットデータノードの前記第1特徴群について実行される前記ハッシュ関数による結果と比較される前記メンバの前記第1特徴群について実行される同じハッシュ関数の選択される部分集合についての結果の集まりの評価が、前記メンバと前記ターゲットデータノードとが同等である確率は所定の閾確率未満であること；
のうちの1つ以上を含む、付記1に記載の方法。
【０１１１】
（付記3）
前記合致基準が、あるメンバに対する前記サブセット結果照合手順により充足される場合に、当該メンバが更なる部分的比較処理のためのグループに加えられ；及び
前記部分的比較処理は：
更なる部分的比較処理のためのグループに加えられる前記メンバの各々について：
前記メンバの前記第1特徴群に対して前記第1のハッシュ関数群を実行した結果を取得し、前記ターゲットデータノードの前記第1特徴群に対して前記第1のハッシュ関数群を実行した結果を取得し、取得された各々の結果を比較し、前記比較に基づいて、前記メンバと前記ターゲットデータノードとが同等である確率の指標を生成し、前記指標が所定の閾確率未満である場合に、除外基準は充足されていると判断される；
ことを更に含む、付記2に記載の方法。
【０１１２】
（付記4）
前記第1特徴群と前記第2特徴群とが同じである、付記1に記載の方法。
【０１１３】
（付記5）
前記第1のハッシュ関数群は前記第2のハッシュ関数群の一部分である、付記1に記載の方法。
【０１１４】
（付記6）
前記意味論的類似性閾値は、前記部分的比較処理により示される前記メンバと前記ターゲットデータノードとが同等である確率に応じて動的に決定される、付記1に記載の方法。
【０１１５】
（付記7）
前記フィルタリングする工程及び前記完全な比較処理を実行する工程が第1反復として実行され、当該方法は、前記フィルタリングする工程及び前記完全な比較処理を実行する工程の1回以上の追加的な反復を更に含み：
各々の追加的な反復に対するデータノードの前記初期候補群は、先行する反復の前記フィルタリングする工程に続く先行する反復における初期候補群のうちの残存するメンバであり；及び
各々の追加的な反復についての前記第1特徴群は前記先行する反復の前記第1特徴群の上位集合であり、各々の追加的な反復についての前記第2特徴群は前記先行する反復の前記第2特徴群の上位集合である、付記1に記載の方法。
【０１１６】
（付記8）
前記1回以上の追加的な反復は、前記フィルタリングする工程及び前記完全な比較処理を実行する工程を実行するために割り当てられるハードウェアリソースがアイドルであると確認されるタイミングまで、遅延させられる、付記7に記載の方法。
【０１１７】
（付記9）
前記ターゲットデータノード及び前記残存するメンバから抽出される前記第2特徴群に対して実行される第2のハッシュ関数群の結果を比較することは、前記ターゲットデータノードと前記残存するメンバとは意味的に同等である尤度を表現する値を生成し、
生成された前記値が意味的同等性閾値を超える場合、前記ターゲットデータノードを前記データグラフに加え、前記ターゲットデータノードと前記残存するメンバとの間の同等性の関係を示す同等リンクを前記データグラフに加える、付記1に記載の方法。
【０１１８】
（付記10）
前記データグラフは、データモデルを規定する第1グループのデータノードと前記第1グループのデータノードのインスタンスを規定する第2グループのデータノードとを有し、
前記初期候補群は前記第2グループのデータノードである、付記1に記載の方法。
【０１１９】
（付記11）
当該方法は、前記フィルタリングする工程の後に、前記ターゲットデータノード及び前記初期候補群の各メンバから第1特徴群の各々の値を抽出し、前記ターゲットデータノード及び前記初期候補群の残存する各メンバから第2特徴群の各々の値を抽出する工程をさらに有し、
第1のハッシュ関数群を利用して、前記メンバ及び前記ターゲットデータノードの双方から抽出される第1特徴群を比較することが：
前記第1のハッシュ関数群のうちの各々のハッシュ関数について、前記ターゲットデータノードの前記第1特徴群の値に対して前記ハッシュ関数を実行することによる第1結果と、前記メンバの前記第1特徴群の値に対して前記ハッシュ関数を実行することによる第2結果とを取得し、前記第1結果と前記第2結果とを比較すること；
を含み、及び/又は
第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較することが：
前記第2のハッシュ関数群のうちの各々のハッシュ関数について、前記ターゲットデータノードの前記第2特徴群の値に対して前記ハッシュ関数を実行することによる第1結果と、前記残存するメンバの前記第2特徴群の値に対して前記ハッシュ関数を実行することによる第2結果とを取得し、前記第1結果と前記第2結果とを比較すること；
を含む、付記1に記載の方法。
【０１２０】
（付記12）
前記部分的比較処理の結果は、前記第1結果が前記第2結果に合致する前記第1のハッシュ関数群の割合である；及び/又は
前記完全な比較処理の結果は、前記第1結果が前記第2結果に合致する前記第2のハッシュ関数群の割合である、付記11に記載の方法。
【０１２１】
（付記13）
複数の相互接続されるデータノードをエンコードするデータグラフを保存するように構成されるデータストレージシステムのコントローラであって、前記データグラフに挿入するためのターゲットデータノードを受信するように構成されるリコンシリエーション処理モジュールを有し；
前記リコンシリエーション処理モジュールは：
前記複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングするように構成されるフィルタリングモジュールであって：
前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理であって、第1のハッシュ関数群を利用して、前記メンバの各々及び前記ターゲットデータノードから抽出される第1特徴群を比較する部分的比較処理を実行すること；及び
前記部分的比較処理の結果が1つ以上の除外基準を充足する場合に、前記初期候補群中の当該メンバと、当該メンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける前記初期候補群中の何らかの他のメンバとを除外すること；
により、フィルタリングを行い；及び
前記初期候補群の残存するメンバの各々が前記ターゲットデータノードとの前記部分的比較処理を完了するまで、前記除外基準が充足される場合に、前記実行すること及び前記除外することを反復する、フィルタリングモジュール；
を有し、前記リコンシリエーション処理モジュールは、
前記フィルタリングモジュールにより出力される前記初期候補群の残存するメンバの各々と前記ターゲットデータノードとの間の完全な比較処理であって、第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較する完全な比較処理を実行する完全比較処理モジュール；
をさらに有し、前記第2のハッシュ関数群は、前記第1のハッシュ関数群より多いハッシュ関数を含む、コントローラ。
【０１２２】
（付記14）
個別的に又は協調して、複数の相互接続されるデータノードをエンコードするデータグラフを保存するように構成される1つ以上のストレージユニットと、付記13に記載のコントローラとを有するデータストレージシステム。
【０１２３】
（付記15）
コンピュータプログラムを保存する非一時的な記憶媒体であって、前記コンピュータプログラムは、1つ又は複数のコンピュータ装置により実行される場合に、複数の相互接続されるデータノードをエンコードするデータグラフとともにターゲットデータノードをリコンサイルする方法を、前記1つ又は複数のコンピュータ装置に実行させ、
前記方法は：
前記複数の相互接続されるデータノードの中のデータノードの初期候補群をフィルタリングする工程であって：
前記初期候補群のメンバと前記ターゲットデータノードとの部分的比較処理であって、第1のハッシュ関数群を利用して、前記メンバの各々及び前記ターゲットデータノードから抽出される第1特徴群を比較する部分的比較処理を実行すること；及び
前記部分的比較処理の結果が1つ以上の除外基準を充足する場合に、前記初期候補群中の当該メンバと、当該メンバに対して意味論的類似性閾値以上の意味論的類似性を有する旨の評価を受ける前記初期候補群中の何らかの他のメンバとを除外すること；
により、フィルタリングを行う工程；及び
前記初期候補群の残存するメンバの各々が前記ターゲットデータノードとの前記部分的比較処理を完了するまで、前記除外基準が充足される場合に、前記実行すること及び前記除外することを反復する工程；
を有し、当該方法は、
前記フィルタリングする工程に続いて、前記初期候補群の残存するメンバの各々と前記ターゲットデータノードとの間の完全な比較処理であって、第2のハッシュ関数群を利用して、前記残存するメンバ及び前記ターゲットデータノードの双方から抽出される第2特徴群を比較する完全な比較処理を実行する工程；
をさらに有し、前記第2のハッシュ関数群は、前記第1のハッシュ関数群より多いハッシュ関数を含む、記憶媒体。
【符号の説明】
【０１２４】
ｐ．ｃ．ｐ  部分的な比較処理
ｔ．ｄ．ｎ  ターゲットデータノード
【図１】
2016071865.tif 000005