(57)【要約】      （修正有）【課題】グラフまたはネットワークの符号化およびインデキシングならびにグラフデータにおけるサブ構造の一致または類似の識別のための非一時的なコンピュータ可読媒体を提供する。【解決手段】コグニティブメモリは、特性、類似、あるいは構造またはサブ構造に基づく検索のためのコグニティブシグネチャと呼ばれるインデックスデータ構造を構築するための縮約およびグラフ特性の計算に加え、グラフの局所構造を要約するために、一般化組み合わせマップおよび新たな量子に着想を得たＱ−Ｈａｓｈｉｎｇアルゴリズムによってグラフを符号化する。方法は、グラフのコグニティブシグネチャの特性を基礎となるデータの特性との相関に使用することで、システムを大規模グラフデータセットの意味的インデキシングにとって理想的にする。【選択図】図１
2020119591.tif 000002
【特許請求の範囲】
【請求項１】
量子コンピューティング要素を実装しているデータ構造を含んでいる非一時的なコンピュータ可読媒体であって、
入力グラフを符号化するマップであって、前記符号化は、前記マップの複数の局所的構造を含み、かつ、前記局所的構造の縮約レベルに関連するＱ−ハッシングアルゴリズムにより実行される、マップと、
前記グラフのノードの状態と関連するインデックスであって、前記グラフの各々のノードは、実数で表され、前記グラフの各々のエッジは、虚数で表される、インデックスと、  を備える非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願］
本出願は、２０１５年３月２４日に出願された米国特許仮出願第６２／１３７，５９８号に基づくとともに、この米国特許仮出願の優先権の利益を主張し、この米国特許仮出願の全内容が、参照によって本明細書に組み込まれる。
【０００２】
［背景］
［開示の分野］
本開示は、高速な格納、クエリ処理、および検索のためにネットワークおよびそれらの任意のサイズのサブ構造の符号化および復号を可能にする「コグニティブメモリ（Cognitive Memory）」モデルを説明する。このモデルは、グラフを一般化マップ（generalized map）へとマッピングすることによってより大きなグラフおよびグラフのグローバル空間において、Ｑ−Ｈａｓｈｉｎｇと呼ばれる量子に着想を得たハッシングスキームを使用するサブグラフのローカル記述に、Ｑ−Ｍｅｄｏｉｄｓと呼ばれるパーティションアルゴリズムに基づくローカライズされた指向サブ空間の概念を具体的に結合させる。
【背景技術】
【０００３】
一般化マップは、ノードおよびエッジがどこで実数値および複素数値をとるかについての新しい表現を使用する。そのような表現は、量子ランダムウォーカ（quantum random walker）が複素ベクトル空間の概念を埋め込む伝統的な概念を逆転させ、代わりにグラフ自体が複素空間を定める。このモデルは、どちらも書き換えプロセスにおいて一意に利用されるより大きなグラフおよびその含まれるサブグラフのグローバルな記述を維持する。
書き換えプロセスは、所与のクエリグラフが格納されたグラフに正確に一致またはほぼ一致するかどうか、あるいは所与のグラフが格納されたグラフのうちの一グラフの一部であるかどうか、などのクエリに応答するためのマルチインデックス構造を生成するための方法の固定の終端点を保証するローカルおよびグローバル表現の構築を含む。さらに、書き換えプロセスは、グラフの一部分が他のグラフの他の部分の「中間」であるか否かについての洞察ももたらすことができ、すなわち中間性および到達可能性の特徴を達成することができる。
【０００４】
関連技術の説明
本明細書において提示される「背景」の説明は、本開示の文脈を大まかに提示することを目的とするものである。現時点の記名発明者の研究のうち、この背景技術の項に記載される範囲の研究、ならびに本明細書の態様のうち、出願の時点における先行技術に該当し得ない態様は、明示的にも、黙示的にも、本発明に対する先行技術として同意されるものではない。
【０００５】
ネットワーク（グラフとも呼ばれる）記憶方法は、画像データベース、化学分子データベース、社会、財政、交通ネットワーク、およびインターネットネットワークコンテンツデータベースなどにおけるハッシングおよびコンテンツベースのアクセスの変種に基づいている。ネットワークベースのインデキシングのための世界で最も一般的なアルゴリズムは、コンテンツのハブページへのインターネット出入りリンクから派生したネットワーク上で動作するＧｏｏｇｌｅ（商標）Ｐａｇｅ−Ｒａｎｋアルゴリズムである。複合ネットワークにおける階層的なサブ構造は、バイオミック（biomic）、プロエテオミック（proeteomic）、ゲノミック（genomic）、ニューラル（neural）、およびソーシャル（social）な組織に偏在している。複合ネットワーク内の関連ネットワークグループ（ＲＮＧ：Related Network Groups）の識別は、一般に、ネットワークの全体およびその構成要素の構造、機能、および進化ゆえにさまざまな異なるやり方でリンクまたは関連付けされ得るノードの階層的なサブネットワークグループへとネットワークを区画する必要があるため、単純なグラフ−同形またはサブ−同形問題よりも難題である。例えば、コミュニティ検出は、中間性（betweeness）およびモジュール性（modularity）の概念を使用して、ネットワークがコンポーネントに分割されるまで最大の中間性を持つリンクを徐々に削除する分割アルゴリズムを実現し、ネットワークが自己類似または反復的な再帰的性質を有するもの（例えば、スケールフリーネットワーク）である場合、モジュール式コンポーネント内でより小さいクラスタを洗練できるかどうかが困難である。すべてのリンクがネットワーク内の構造に関する情報を潜在的に含むため、プロセスのいかなる段階においてもリンクを破棄せずに異なる構造レベルをクラスタ化する階層表現およびパーティション戦略が必要である。
【０００６】
ＨｏｓｏｙａのＴｏｐｏｌｏｇｉｃａｌ  ＩｎｄｅｘおよびＧｏｏｇｌｅのＰａｇｅ−Ｒａｎｋなどのネットワークのトポロジまたはジオメトリについての指標は、単独で用いられても、組み合わせにて用いられたとしても、とりわけ時間につれての変化に関して画像のコンテンツ記述を充分に表すことができないだけでなく、ネットワーク間の脆弱なマッチングが望ましくない複雑な、リレーショナルな、類推的なクエリを表現するためのツールとしても充分でない。例えば、画像処理において、グラフはコンテンツの良好な表現を提供するが、グラフに基づく記憶および検索は、単独またはビデオなどにおける連続の画像のスケール、サイズ、解像度、数、および忠実度が増大し、これがグラフに基づく方法の複雑さに拍車をかけるとき、困難である。
【０００７】
インターネット検索においては、Ｇｏｏｇｌｅ（商標）のＰａｇｅ−Ｒａｎｋが、支配的かつ最も成功したネットワークインデキシングアルゴリズムとなっている。しかしながら、Ｐａｇｅ−Ｒａｎｋは、ウェブサイト間の類似性ならびに文脈を捕らえることができず、コンテンツ表現によってウェブサイトユーザをプロファイリングする手段としても機能しない。Ｐａｇｅ  Ｒａｎｋおよび他のグラフアルゴリズムなどのアルゴリズムにおいて、主たる注目は、接続されたコンポーネント、および最も重要な基本的概念を捕らえる最大限に接続されたコンポーネントを表すいわゆるハブによって重要な意味的概念を識別することに向けられている。
【０００８】
他のグラフベースのアルゴリズムの大部分およびそれらの主なクラスタリング方法は、いずれも、データがテキスト（すなわち、テキストグラフを形成する）または画像（すなわち、視覚的パターン認識のために画像グラフを分割および形成する）あるいは金融ネットワークもしくは分子または生化学的グラフおよびネットワーク（薬剤設計または化学的特性の評価用）のいずれであったとしても、受け取るデータから形成されるグラフまたはネットワークの最大の接続されたコンポーネントの単一の静的ビューに基づく。
【０００９】
候補グラフを検索するために、現時点において、２つの主な手法が文献に存在する。ＬｅｖｉｎｓｏｎのＵｎｉｖｅｒｓａｌ  Ｇｒａｐｈ［３］ならびにＳＵＢＤＵＥおよび他の手法［４］などのインデックスベースの手法。Ｐｅｔｒａｋｉｓ［５］による属性関係グラフ「ＡＲＧ」（Attribute Relational Graph）法などのベクトルベースの手法。
【００１０】
方法（ｉ）および（ｉｉ）は、構造的な変動性、複雑さ、多様性、および特徴が大きく異なる場合や、グラフに大きな動的変化が存在する場合、成功しない。いずれの方法も、グラフの動的変化のシーケンスの符号化および格納に、あまり適していない。
【００１１】
インデックスベースの手法は、クエリに応答してトラバースされるメンバーグラフの階層的なインデックスの静的な多くの場合に事前に計算されるセットを保持する。トラバースの際に、クエリグラフと現在のインデックス要素との間のインデックス値による距離指標が計算され、検索に使用される。ベクトルベースの手法は、メンバーグラフを特徴のベクトルとみなし、各グラフを特徴空間に変換する。通常は、ベクトル化は、グラフの属性について実行される。このプロセスにおいて、グラフ属性がどのように連結されているかを示す構造特性は無視される。
【００１２】
画像データベースにおけるネットワーク検索は、意味が全く異なるがゆえに、化学データバンクにおけるグラフ検索とは異なり、テキストデータベースまたはハイパーリンクされたウェブにおける検索とは大きく異なる。いくつかの応用分野は、すべてのグラフがデータベースに格納されたユニバーサルグラフの変形であるユニバーサルグラフ概念を使用し、構造は類似しているがテーマによる変化が存在する場合（ＣＡＤ図面または他の機械カタログ部品など）に最良に機能するグラフデータベースを必要とする。これは、メンバーグラフが構造に関してほとんど似ていることを意味する。しかしながら、各々のグラフについて考えられるノードおよびエッジ属性の数が、大きくなると考えられる。実際に、現代のあらゆるＯＯＲＤＢＭＳ（オブジェクト指向リレーショナルデータベース管理システム：Object Oriented Relational Database Management System）は、属性関係グラフデータベースとみなすことができる。これは、関係スキーマが等価なＥＲ（エンティティ関係：Entity Relation）スキーマグラフを有し、したがってメンバーグラフがＥＲスキーマグラフの異なるインスタンスであるグラフデータベースであるとみなされるためである。しかしながら、高複雑度構造指向グラフ記憶システムのクエリ処理および生成は、多くの場合に、グラフが、ほぼ同一の構造を共有しないが、全体的類似にもかかわらず局所的に異なり（例えば、タンパク質の構造の場合）、あるいは局所的に類似であるが全体としてはきわめて異なる（例えば、言語リソースにおけるテキストのグラフの場合）可能性があるため、ＯＯＲＤＢＭＳシステムとほとんど共通点がなく、したがって大規模にてネットワークを格納および検索するために一般的に利用できるシステムは存在しない。
【００１３】
したがって、これらの非常に異なる視点に対応する方法が必要とされる。具体的には、グラフの動的変化を効率的なやり方で捕らえることを可能にするフレームワークが必要とされる。
【発明の概要】
【００１４】
コグニティブメモリは、グラフの関係型クエリ、類似物の発見、データマイニング、およびグラフ構造コンテンツと意味的特性との相関に適する。グラフ構造を有するデータとして、ソーシャルネットワーク、生化学ネットワーク、タンパク質および化学分子グラフ、トラフィックネットワークグラフおよび金融取引ネットワークなどの動的に時間変化するグラフ、ならびに通信システムトポロジが挙げられる。グラフのインデキシング、格納、呼び出し、および互いの比較の問題が、本開示によって対処される根本的な課題である。
【００１５】
本開示および本開示に付随する多数の利点のより完全な理解が、本開示が以下の詳細な説明を参照し、添付の図面と併せて検討することによってよりよく理解されるときに、容易に得られるであろう。
【００１６】
以下の図が、本発明を説明する。
【図面の簡単な説明】
【００１７】
【図１】コグニティブメモリシステムおよびプロセスを示している。
【図２】一般化組み合わせマップとしてのネットワークの符号化を示している。
【図３】Ｑ−Ｍｅｄｏｉｄｓ分割アルゴリズムを示している。
【図４】Ｄｉｓｔａｎｃｅ  Ｔｏ  Ｚｏｎｅ  ＮＳＩの分割およびゾーニングを示している。
【図５】量子粒子および相互作用のための典型的な球面調和形状制約を示している。
【図６】典型的なＱハッシング関数を示している。
【図７】典型的なローカライズドブルームフィルタインデックスを示している。
【図８】典型的な有色グラフを示している。
【図９】一実施形態による典型的な接続マトリクスを示している。
【図１０】典型的な有色接続マトリクスを示している。
【図１１】ノード関数加重マトリクスを示している。
【図１２】隣接ノード重みの逆数平方根の和としてのマトリクス特性関数を示している。
【図１３】単語「ｔｅｓｔｅｒ」における文字ペアの組み合わせ経路グラフマトリクスを示している。
【図１４】表２の符号化を使用する「ｔｅｓｔｅｒ」のネットワークの典型的な有色経路マトリクスを示している。
【図１５】グラフを表すマトリクスのＤＵＮＲＣを示している。
【図１６】一実施形態による典型的な縮約ルール操作を示している。
【図１７】ＧＭＡＰの二重を示している。
【図１８】部分的一般化組み合わせマップの縮約および符号化を示している。
【図１９】結合縮約および特性関数計算操作を示している。
【図２０】ＲＤＢＭＳへのネットワークの符号化および格納のフローチャートを示している。
【図２１】ＲＤＢＭＳからのネットワークの検索のフローチャートを示している。
【図２２】一実施形態によるコンピューティングデバイスのブロック図を示している。
【発明を実施するための形態】
【００１８】
コグニティブメモリは、グラフデータを学習し、グラフの構造を関心の対象の観察を表す尺度に関連付けるための新規かつ大きく改善された表現、方法、およびアルゴリズムである。参照によってその全体が本明細書に組み込まれる米国特許第９，１５８，８４７号を参照されたい。例えば、時間につれての金融ネットワークの構造の変化、あるいは時間につれての交通または輸送ネットワークの変化に、コグニティブメモリモデル手法を利用することによって対処することができる。種々のグラフカーネルが、グラフ間の類似度を測定するための効率的かつ広く使用されている方法となっているが、これらの方法は、巨大複合ネットワーク全体の数百万または数十億のノードまたはデータフローを超える拡大が不可能である。これらの巨大なグラフは、テキストグラフとしての自然言語処理、分子構造としての化学情報学、プロテオームやバイオームネットワークなどのバイオインフォマティクス、医学的画像理解などの画像解析、コグニティブ状況理解などのコンピュータビジョンなどの分野において一般的に生じる。さらに、グラフ構造の多くにおいては、データフロー密度、速度、形状、オブジェクトの関係位置、あるいは他の測定されるノードまたはエッジもしくは組み合わせの特性が、これらのグラフ構造の区分、分類、および意味的理解のための重大かつ重要な特徴を決定する。
【００１９】
本明細書において説明されるコグニティブメモリモデルは、グラフを折り畳み、あるいは縮約するとともに、変換されたグラフ構造を随意により可逆またはロスレスにて拡大し、あるいは広げるプロセスを、随意により離散的または連続値のノードまたはエッジあるいはノードおよびエッジ属性を有するグラフ上の複素ベクトル値のロケール（すなわち、サブ空間）とともに結合させる独自かつ進歩的な組み合わせを提示する。
【００２０】
伝統的な技術水準の波動伝搬法では、ランダムまたは量子状ウォークが、その構造が静的なままであるグラフについて実行される。これは、例えば、Ｗｅｉｓｆｅｉｌｅｒ−Ｌｅｈｍａｎアルゴリズム、グラフ不変カーネル、および波動（ならびに、いわゆる量子波）伝播カーネルを含み、グラフカーネルは、パスの構造的特徴を捕捉し、これらをグラフ間の比較に使用することができる。しかしながら、これらの方法はいずれも、例外なく、ノードおよびエッジの数あるいは入力グラフのサイズ（直径）において、きわめて大きい幾何級数的な累乗（例えば、ｎ４）の複雑さを有するため、数万または数十万あるいは数千万または数億以上のノードおよびエッジを有するグラフにおいては非現実的である。
【００２１】
グラフカーネルおよびグラフ構造の学習に関する文献が明白または直接的な解決策を提供していないはるかに明白ではない一連の問題も、本開示の態様によって対処される。
【００２２】
（ｉ）種々の粒度レベルのグラフデータは、或る種の順序付けの形態で生じることが多く、例えばテキスト内のキャラクタがグラフで表される場合、テキスト内の単語の文字は、キャラクタよりも上の１つのレベルまたは粒度の順序付けを表し、単語のテキストの合計グラフは、別の順序付けを表す。これらの順序付けの表現、ならびに潜在的に順序付けられたグラフシーケンスのインデキシング、格納、呼び出し、および推論の目的でのグラフの展開および構造付けにおける技術水準は、きわめて特定的な用途に合わせて作られた種々のその場しのぎの手作りの手法にすぎない。
【００２３】
（ｉｉ）上述のように、グラフまたはネットワークのデータの分野は、著しく多様化した用途を有し、結果として、幅広く変化する特徴一式（例えば、キャラクタ、テキスト、画像、トラフィック、ソーシャルネットワーク、など）を含む。今日の技術水準は、個々の用途にきわめて特有なやり方にて手作業で特徴を選択および作成することである。最終的な結果として、手作業による手法はいずれも、一般化、移転、および再使用が不可能である。
【００２４】
（ｉｉｉ）グラフデータは、多くの場合に大きく、数百、数千、または数百万のエッジおよびノードの違いを容易に超え得るネットワーク構造およびその間の時間変化を伴う。
各々の観測またはデータムごとに複数のネットワークが存在し得る複合システムでは、そのようなサイズが天文学的に大きくなり、その結果、類似性、類似物、または同形を識別するための計算時間が、スーパーコンピュータにおいてさえも非現実的になる。
【００２５】
本開示のいくつかの態様は、グラフデータのインデキシング、格納、呼び出し、および重要な特徴の推論のための処理がきわめて効率的かつ新規なやり方で実行されるように、上述の問題に対処する。さらに、従来からの手法の場合のように静的な構造に依存しない動的なカーネルに対する特徴抽象、グラフの構造的書き換え、およびシグネチャの間の独特の強力な結合が存在する。さらに、システムは、時間変化するグラフ、あるいは各々のデータムがセットもしくは集合、または順次に部分的に順序付けられ、もしくは完全に順序付けられたグラフ自体を代表することができるイベントによって変化するグラフを、取り扱うことができる。
【００２６】
グラフが関数の集合およびグラフ縮約操作（可逆的であり得る）に基づく基準の特徴の集合によって記述されるため、人間のその場しのぎまたは手作りの手法は、もはや必要ではない。そのような基準の特徴の集合は、時間につれてのそれらの発展も含め、コグニティブシグネチャに表される。コグニティブシグネチャは、さまざまなサイズおよび長さのシーケンスおよび構造をメトリックに比較できるようにする一連のベクトルで構成される。好ましい実施形態によれば、本明細書で提示される方法は、手作業による特徴の選択および抽出の必要性を直接的に排除する。
【００２７】
コグニティブシグネチャは、ノードおよびエッジが大まかにサブ空間の回転（移動）に対応する複素数値のベクトル空間を使用し、より高次のモーメントも取ることもできるが、その構成は順序またはシーケンス構造を捕らえる非可換カーネルをもたらす。したがって、コグニティブメモリモデルは、非連続カーネル複素数値カーネル法が現在存在しないことが知られている任意の複雑なグラフ構造データシーケンスの直接的な機械学習を可能にする。したがって、コグニティブメモリモデルおよびそのシグネチャは、構造グラフだけでなく、複雑な順序構造のエピソードシーケンスまたはエピソード記憶も表現するための人間のようなパターンに基づくグラフのインデキシング、格納、呼び出し、および推論のシステムを形成する。コグニティブシグネチャは、きわめて効率的に計算することができ、その特性は、高速なキャッシュ内計算が必要とされる場合に、超高速低ランク加速近似計算に理想的に適する。これらには、一般的な方法、特異値分解に基づく方法、Ｍａｒｋｏｖ、Ｇａｕｓｓｉａｎ、またはＤｉｒｉｃｈｌｅｔプロセス法の学習、ならびにこれらに限られるわけではないがＣｈｏｌｅｓｋｙ近似、Ｎｙｓｔｒｏｍ近似、類似マトリクス技術などのそこでの近似方法が含まれる。
【００２８】
さらに、本開示の特定の態様によって、（ＧＭＡＰ内の）埋め込みとしての頂点の幾何学的形状を決定するためにポテンシャル場関数についての複素数値のカーネルを使用することができ、このプロセスは、ここでダーツ（元のグラフの頂点またはエッジを表す）を使用してＧＭＡＰにおいてＱ−Ｍｅｄｏｉｄｓと定義されるものを生成する。量子ランダムウォークプロセスに類似した古典的なガウス過程法と同様の反復ランダムプロセスが、グラフのロケール（すなわち、メドイド）をモデル化するために使用される。非自明な本開示の多数の特徴のうちの１つが、（量子または古典的な）ランダムウォークによってメドイドを表すサブ空間の生成であり、プロセスが概念的に反転させられており、したがってグラフを歩く粒子の代わりに、実際にはグラフノードまたはエッジが隣接する頂点（２つでエッジ）を反発させ、あるいは引き付けるポテンシャル場関数に従ってそれら自身を歩き、サブ空間の成形における再配置または縮約のいずれかをもたらすことを、理解しなければならない。
【００２９】
量子ランダムウォークは、ベクトルがまたぐ状態空間において動作し、したがって概念化の反転という先の類推に続いて、ベクトルは、頂点上の関数の各々の遷移後にグラフの特性を計算する関数によって集められる。
【００３０】
時系列データに対する機械学習の一般的な手法は、５つのテーマ領域に分類される。
【００３１】
１．Ｎｅｕｒａｌネットワーク（いわゆる「ディープラーニング」）ベースの機械学習。
【００３２】
２．（Ｐｒｏｌｏｇなどの論理プログラミング言語および文字列に基づく種々のシーケンスサブシーケンス比較法を使用する方法など）論理およびダイナミックプログラミングに基づく象徴的学習。
【００３３】
３．グラフおよび他の複雑なデータ（像など）のための機械学習コミュニティにおけるカーネル学習。
【００３４】
４．遺伝的アルゴリズムなどのランダムまたは確率的進化法。
【００３５】
５．ラフパス、グラフスペクトル、多様体学習、などの多様体法および局所線形サブ空間近似。
【００３６】
しかしながら、最近になって、量子に着想を得たアルゴリズムが、テンソル、テンソルネットワーク、および複素ベクトル値関数を使用する他の「物理学的に着想を得た」手法とともに現れている。コグニティブメモリモデルは、新興の最後の方法のカテゴリに分類される。したがって、カーネルは、分子軌道理論と同様に、原子軌道の線形結合（ＬＣＡＯ：Linear Combination of Atom Orbitals）および分子静電擬ポテンシャル法から着想を得て、多項式系の複雑な組み合わせの他の一般的な多項式表現と同様の組み合わせ的複雑さを排除する。
【００３７】
本開示の一態様によれば、ネットワークの符号化は、「コグニティブシグネチャ」（ＣＳ：Cognitive Signature）と呼ばれるデータ構造にカプセル化され、入力ネットワークを再現するために復号できるシグネチャに基づく方法である。本明細書においてコグニティブメモリ（ＣＭ：Cognitive Memory）と呼ばれるものを形成すべくすべてのコグニティブシグネチャを格納するために使用されるデータベースを、例えばマルチバンテージポイントツリー（Multi-Vantage Point Trees）を使用して任意の（複素数を含む）ベクトルを格納することができる空間データ表現をサポートする任意のリレーショナルデータベース管理システム（ＲＤＢＭＳ：Relational Database Management System）において実現することができる。コグニティブメモリを使用した格納またはクエリ処理のための方法およびスキーマは、ユーザのクエリに高速の類推の結果または正確な結果を提供するために提示される。本明細書で説明されるネットワーク符号化のフレームワークは、呼び出しのための（ｎ）ｌｏｇ（ｎ）の複雑さを提供する。独自に、このフレームワークは、グラフの一般化組み合わせマップ（ＧＭＡＰ：Generalized Combinatorial Map）表現における最も高いｋ次の複合体と、符号化されるデータの最も重要な基本的な意味的特性との間の関連によって、符号化プロセスの自然な一部分としてトピックおよび概念の抽出を可能にする。
【００３８】
コグニティブメモリの主な考え方は、反復縮約プロセスを、より大きなグラフのロケールを代表的なサブマップへと分割するために基準の方法から導出されたグラフについて計算された関数と組み合わせることである。プロセスは、グラフを縮約し（すなわち、サブマップ）、サブマップのローカリティベースのインデックスを計算し、この方法は、ローカルサブマップが、シードをランダムに分配し、次いで頂点の近傍を含むボールについて範囲（半径）を定義するプロセスによって選択されると仮定する。
【００３９】
コグニティブメモリは、充分に小さく、コンパクトで、計算が速い特別な短いハッシュ構造を使用する。ハッシュを、巨大なグラフ（数百万、数十億、または数兆のノード）のインデックスとして使用することができる。ハッシュは、頂点に関するグラフ距離の概念および高速な近似のグラフ距離を可能にするシェルを含む。この革新は、大規模な動的グラフを、ネットワーク構造インデックスＮＳＩアルゴリズムにおけるアイデアに着想した重なり合うインデックス領域の集合に分割するという考えから引き出されている。しかしながら、ＮＳＩと本開示のフレームワークとの間の重要な相違点は、ＮＳＩがハッシュに組み込まれておらず、ＮＳＩの定義および計算ならびにその使用が局所感性インデキシングまたは複素ベクトル値を取り入れていないことにある。
【００４０】
コグニティブメモリのシステムおよび方法は、ノードおよびリンクのポテンシャル場または波動関数に関して接続マトリクスを表すことによって、グラフ構造を表す階乗のネットワーク記述空間を排除する量子物理学に着想を得た方法を利用する。具体的には、すべてのｎ個のノードが、１つの（ｎ−１）次元ポリトープ上に点（頂点）として投影され、点状オブジェクトとして移動することができる一方で、エッジが、グラフの関数の計算を可能にし、次いで（ｎ−（ｎ−１））の固定点に達するまでの（ｎ−２）への後続の縮約を可能にするための隣接（すなわち、仮想リンク）、接続、または非接続のノードについての有向の中性、引力、または斥力の状態を表すこれらのノードに作用する力を生成する複素値とされる。規約が一方向または他方向に選択される場合、実数値のノードおよび複素値のエッジを、複素値のノードおよび実数値のエッジとしても二重に見ることができることを、理解すべきである。
【００４１】
エッジに対する複素値関数の導入により、頂点に、それらのポテンシャル場関数とエッジ波動関数との相互作用ゆえに正確に集まる機会が与えられ、これらの集まりを後に縮約でき、複素数を使用することなく、関数の影響下で実数値のみを有する頂点およびエッジが、お互いに向かって移動してマージし、ネットワーク全体を表すと考えられる単一の点へと迅速に崩壊する傾向を有する。一例として、ノードのダイナミクスを表す複素ポテンシャル関数の導関数をとることにより、ノードの運動の方向を識別するために使用することができる複素共役型の速度流場が生成される。そのようなモデルは、Ｇｕｄｋｏｖら［１１，１２，１３］によって紹介されたが、Ｇｕｄｋｏｖのモデルは、複素ポテンシャル関数ではなく、単純化した実ポテンシャル井戸にのみ基づいており、本開示のＱ−Ｍｅｄｏｉｄｓの方法またはＱ−Ｈａｓｈの方法を取り入れていないため、Ｇｕｄｋｏｖの改善である。
【００４２】
本開示の一態様は、可逆であるが、解の一意性を助ける階層へとグラフを崩壊させる縮約操作の使用を提供する。そのような縮約は、波動関数の選択、頂点間の相対距離に依存するポテンシャル場関数の力によって保証される。このアルゴリズムは、密度（流体流および粘度などの概念に関連するレイノルズ数と同様に）場密度に比例する単純な模擬のアニーリングプロセス（量子アニールに類似）を使用して機械学習できる無次元数係数を持つ場における仮想量子粒子の量子化された方向性運動として頂点の動きを考慮する。
【００４３】
さらに、コグニティブメモリモデルは、階層ブルームフィルタに依拠して、大規模なグラフデータベースのためのきわめて高速かつ迅速な解を生成するために本開示の方法によって構築されたグラフの空間から候補を構築するための迅速なテストを実行する。
【００４４】
本開示の一態様は、ＧｏｏｇｌｅのＰａｇｅ−Ｒａｎｋアルゴリズムとは対照的に、以下の有利な能力を提供する。本開示の一特徴は、縮約ルールの使用を介して、組み合わせマップ内の最大のｋ次元複合体を自動的に識別し、したがって最も重要な基礎概念を捕捉し、ゆえにＧｏｏｇｌｅのＰａｇｅ−Ｒａｎｋに対する同様の動作のための代替のアルゴリズムとしての使用に適する。
【００４５】
さらに、比較において、構造の相同体および類似体の特定、とりわけそれらの時間変化の関係付けに効果的に使用することが不可能であるＰａｇｅ−Ｒａｎｋと異なり、本開示は、測定ルール（すなわち、データを表す一般化マップの構造およびジオメトリに基づく値を生成する関数）と最大の最も重要な基本概念が最高の次元の最大のトポロジカルセルラーコンプレックスとして投影された最大の連続的に縮約された一般化マップとを組み合わせることによって、コア概念構造および構造の変化の高速かつ容易な識別を可能にする。
【００４６】
さらに、本開示は、意味論的に基づく縮約ルールの下での動的進化によってグラフを識別するシグネチャのマトリクスのセットを生成する連続的に抽象化された階層表現のシーケンスを生成する。その結果、ネットワークおよびそのデータが、コンテンツおよび構造の両方に影響され、縮約ルールの下で形成されたｋセルの最高次元が種々の抽象化レベルにおけるインデキシングまたはクラスタリングのための重要な概念または機能を表すようなやり方で、符号化される。これらの抽象化は、高速な類似体および相同体の識別を可能にする。
【００４７】
したがって、本発明の重要な利点は、類似グラフ間の動的変化を、それらのサブネットワーク（すなわち、サブグラフ）のトポロジ変化から直接導出されるシグネチャの変化に基づいて、効率的に説明できることにある。
【００４８】
さらに、本開示は、グラフおよびネットワーク構造のサイズが大きくなるときに、最小限の増分変更だけで、コアデータストアの再インデキシングを必要とせずに、拡大してより大きいデータをサポートするという好都合な能力を有する。より大規模または異なるグラフおよびネットワーク構造は、再インデキシングを伴わずに現在のストアに単純に追加される。
【００４９】
本開示に記載の技術は、以下の利点も有する。
【００５０】
（ａ）コグニティブシグネチャと呼ばれる特別に符号化されたグローバル表現から一致する候補グラフのセットを検索するクエリグラフの使用。
【００５１】
（ｂ）コグニティブメモリと呼ばれるコグニティブシグネチャのデータベースから検索された候補の各々における局所Ｑ−Ｍｅｄｏｉｄｓブルームフィルタ、候補に対するクエリグラフの照合および一致するサブパートの選択。
【００５２】
（ｃ）グラフによって符号化された特性の計算およびグラフによって符号化された基礎データの特性との相関付け（例えば、グラフがピクチャを符号化する場合の画像特性、またはグラフが化学構造を符号化する場合の化学特性、あるいは基礎データの他の意味的特性）。
【００５３】
（ｄ）コード表現ツリー表現を用いた効率的なやり方でのグラフへの連続的な動的変化の格納。
【００５４】
（ｅ）グラフの基礎データの変化としてのグラフ構造の変化の関心対象の意味的特性との相関付け。
【００５５】
本開示の実施形態は、ネットワークをそれらの構造または意味的特性によって符号化、復号、格納、および検索するためのシステムおよび方法を提供する。グラフは、一般化組み合わせマップ（ＧＭＡＰ）へと変換される。ＧＭＡＰは、表現および符号化アルゴリズムに３つの重要な利点を提供し、第１には、グラフに関し、ＧＭＡＰは、ＧＭＡＰの各頂点がダーツと呼ばれる暗黙のオブジェクトに属する自然な二重表現を提供し、示されるとおり、これは元のグラフの対応するエッジも表すことができる。
【００５６】
第２に、必ずしもインボリューションではない関数が、グラフからＧＭＡＰを構築するために使用されるが、ＧＭＡＰのダーツを横断する関数などの他の関数が、元のグラフのエッジおよび頂点の横断の状態空間を表す。したがって、ＧＭＡＰは、関数としての振る舞いが元のグラフにおける関心対象の特徴または特性と共変であるアルゴリズムを定義することを容易にするグラフの簡潔かつエレガントな表現である。第３に、ＧＭＡＰは埋め込みに対応するように設計されており、すなわち本開示は、細かい粒度のサブ構造（すなわち、サブマップ）をインデキシングするための高速局所化処理を可能にするＱ−Ｍｅｄｏｉｄｓの埋め込みという概念を拡張する。
【００５７】
前述のように、グラフまたはネットワーク構造は、一般化組み合わせマップ（ＧＭＡＰＳ）へと符号化され、これらのＧＭＡＰＳは、本明細書で定義されるＱ−Ｍｅｄｏｉｄｓグラフアルゴリズム（文献中のＫ−Ｍｅｄｏｉｄｓアルゴリズムと混同してはならない）を使用してサブマップに分割され、コードは、マトリクス階乗ナンバリングを使用してＧＭＡＰ上で計算され、Ｌｅｈｍｅｒコードおよびマトリクス特性関数は、すべて縮約ルールに堅く結合し（すなわち、ペアにされ）され、コグニティブシグネチャと呼ばれるデータ構造に集約されたシグネチャのセットを生成する。
【００５８】
コグニティブシグネチャは、第１には、離散無色ネットワーク表現コード（ＤＵＮＲＣ：Discrete Uncolored Network Representation Code）と呼ばれるトポロジカル符号化を含み、第２には、離散カラーネットワーク表現コード（ＤＣＮＲＣ：Discrete Colored Network Representation Code）と呼ばれるジオメトリック符号化（ネットワークコンテンツを構成する）を含み、第３には、ネットワークをベクトル空間に投影するｋマトリクス特性評価関数のｋベクトルを含み、第４には、ネットワークを別のベクトル空間に投影するｍマトリクストポロジ評価関数のｍベクトルを含み、第５には、他の以前の方法のインデキシング力を大幅に拡張するネットワークの新たに導出されたＱ−Ｍｅｄｉｏｄコンプレックスブルームフィルタインデックス（ＣＢＦＩ：Complex Bloom Filter Index）を有するネットワーク縮約ツリーコード（ＮＣＴＣ：Network Contraction Tree Code）を含む。
【００５９】
前処理時間の複雑さは、入力グラフのサイズに線形に比例するが、格納および呼び出し時間は、サブリニアであり、グラフのサイズのｌｏｇ（ｎ）として比例する。グラフの比較はＮＰ完全な問題であることは、よく知られている。これは、ほとんどのそのようなアルゴリズムの実行時の複雑さがＯ（ｅ（Ｎ＋Ｅ））であることを意味し、ここで、Ｎはノードの数であり、Ｅはグラフのエッジの数である。本開示の符号化フレームワークは、プロセスを２つの段階に分割し、すなわち入力クエリグラフおよび他のグラフの両方のコンパイル段階とクエリ段階とに分割することにより、著しく良好に機能することができる。
コンパイル段階において、グラフはＧＭＡＰに変換され、Ｑ−Ｍｅｄｏｉｄアルゴリズムに従って分割され、複雑なフィルタが挿入され、ネットワークのスペクトル値が、ネットワークを表すマトリクスのジオメトリおよびトポロジ特性関数を使用してクエリされるすべてのネットワークについて縮約を横断して計算される。ネットワークマトリクス特性関数は、好ましい実施形態においてはＯ（Ｎ＋Ｅ）の実行時間で計算可能であるように選択される。コンパイル時、Ｑ−Ｍｅｄｏｉｄｓおよびブルームフィルタは１回だけ事前計算され、次いでネットワークは、入力ごとにＯ（ｌｏｇ（Ｎ＋Ｅ））の縮約ステップにて縮約させられる。合計コンパイル時間は、各々のネットワークについてＯ（（Ｎ＋Ｅ）×ｌｏｇ（Ｎ＋Ｅ））である。Ｋ個のネットワークを扱うために、合計時間はＯ（Ｋ×（Ｎ＋Ｅ）×ｌｏｇ（Ｎ＋Ｅ））になり、これはＯ（Ｋ×ｅ（Ｎ＋Ｅ））の伝統的な方法よりもはるかに速い。クエリ時には、データベース内のグラフがコンパイルされた形式であり、すなわちコグニティブシグネチャの形式であるため、新しい入力クエリグラフについてのみ計算が実行される。したがって、ネットワークのクエリ時間は比較的小さく、Ｏ（ｌｏｇ（Ｋ））であり、ここで、Ｋはデータベース内のネットワークの数である。
【００６０】
以上の段落は、全体的な紹介として提示されており、以下の特許請求の範囲を限定しようとするものではない。記載される実施形態は、さらなる利点とともに、以下の詳細な説明を添付の図面と併せて参照することによって、最もよく理解されるであろう。
【００６１】
ここで図面を参照すると、類似の参照番号は、いくつかの図面を通して、同一または対応する部分を示している。
【００６２】
図１は、高速な意味的インデキシング、記憶、および検索のためのコグニティブメモリ符号化ネットワークのためのシステムおよび符号化を示す。システムおよび方法は、図１を参照する以下の番号の付いた要素によって説明される。
【００６３】
処理されるデータネットワーク（２）と呼ばれるネットワーク（１）が、システムへと存在する。
【００６４】
データネットワーク（２）は、プロセス（３）によってコグニティブシグネチャ（５）へとコンパイルされ（４）、この場合には「ｇｍａｐ１」（しかしながら、各々のネットワークについて異なり、特有である）と呼ばれるＧＵＩＤ（グローバルユニークアイデンティティ指定：Global Unique Identity Designation）と、入力ネットワーク（１）の縮約の各レベルＫについて１つずつのベクトルのマトリクスＴ（トポロジとも呼ばれる）と、入力ネットワーク（１）の縮約の各レベルＫについて１つずつのベクトルのマトリクスＧ（ジオメトリとも呼ばれる）と、ネットワーク（１）のコンテンツまたはラベルのシンボルＳと、入力ネットワーク（１）を表すトポロジについてのＤＵＮＲＣ（Discrete Uncolored Network Representation Code）およびジオメトリについてのＤＣＮＲＣ（Discrete Colored Network Representation Code）と、縮約の各レベルの中間コードとを含み、  コグニティブシグネチャ（５）は、（６）、（７）、および（８）に示されるプライマリキー、すなわちＤＵＮＲＣ値と、ＤＣＮＲＣ値としてのセカンダリキーと、ＧＵＩＤおよび縮約のレベルである第３のキーと、それぞれＴおよびＧのベクトルをＧＵＩＤおよび縮約のレベルとともに格納するマルチバンテージポイントツリー（または、他の同等の空間データ構造）のペアとによってインデキシングされた縮約の各レベルについて１つずつのテーブルに離散値をそれぞれが格納するデータベースセットの各レベルＫにおいて比較される。レベル（８）のデータベースは、元の入力ネットワーク（１）を一般化組み合わせマップ（ＧＭＡＰ）として格納するデータベースである。
【００６５】
入力ネットワーク（１）が、データベースに格納されたそのコグニティブシグネチャ（５）、各々の縮約レベルについて１つずつのＫ個のデータベースが存在するコグニティブメモリ（６）、（７）、（８）の比較に基づいてマッチしない場合、非マッチが返され（９）、入力は、本開示で詳述されるシステムおよび方法を使用してコグニティブメモリに格納され、そうでなければ、
（サブネットワークの）正確、類似、または部分的なマッチについて、これらがＴおよびＧならびに返されたレベルにおいて返されたネットワークのベクトルをランク付けすることによってランク付けされた順序（１０）で返される。したがって、詳細の複数のレベルが返されるが、ユーザは、好ましい使用例では、詳細の不要なレベルを除外することができる。
【００６６】
図２は、グラフ構造のための一般化組み合わせマップ（ＧＭＡＰＳ）の形態を示している。以下では、最初に、本開示の実施形態によるブルームフィルタの説明を提示する。
【００６７】
構造ロケールを構築する場合、ブルームフィルタは、ＭａｘＲおよびＮｕｍＯｒｂｉｔｓという２つのしきい値によって制約されるインデックスとして使用される。ＭａｘＲは、ダーツＤの近傍の最大半径である。或る範囲の下限に適応するために、近傍は軌道セットに分割される。パラメータＮｕｍＯｒｂｉｔは、近傍の軌道の数を制御する。軌道は、メトリック範囲［ｍｉｎＲ，ｍａｘＲ］に制約され、すなわちＤまでの最短距離が区間内にあるダーツが、軌道に関連付けられる。例えば、ＭａｘＲ＝１０００であり、ＮｕｍＯｒｂｉｔ＝１０である場合、軌道は［１，１００］、［１０１，２００］、．．．、［９０１，１０００］である。
【００６８】
構成は、埋め込まれたジオメトリがロケールをｋ−ｓｉｍｐｌｅｘとして表すダーツの周りの制約ＭａｘＲおよびＮｕｍＯｒｂｉｔｓ、すなわち点を多面体の頂点の線形結合として表す重心座標系の局所座標系の使用に依存する。この特許で使用されるブルームフィルタの変種は、隣接するダーツ（すなわち、中央の選択された根の頂点から離れたエッジ長にある頂点）の軌道を表す複素数（重心座標）の実部および虚部を構成するための対関数の使用に基づく。２つの数をｍビットのブルームフィルタにペアリングするために、Ｃａｎｔｏｒの対関数π（ａ，ｂ）など、最も単純な対関数を使用することができる。
【００６９】
π（ａ，ｂ）＝１／２．（ａ＋ｂ）（ａ＋ｂ＋１）＋ｂ
他の対関数が使用可能であり、主な点は、複素数係数がブルームフィルタのバケット内のビットを表す自然数にマッピングされることである。
【００７０】
データベースから返される候補グラフへの入力クエリグラフのサブマップ（すなわち、サブグラフ）を識別するためにロケールブルームフィルタベースのインデックスが使用される候補グラフを選択するためにグローバルＤＣＮＲＣを使用して複数のＧＭＡＰＳ（および、グラフにおいて相補的に）のエッジクエリが定義される。
【００７１】
［１５，２５］の間の区間に境界付けられたＧＭＡＰ  Ｇ１の間のダーツ（ｄ１，ｄ２）および他のＧＭＡＰ  Ｇ２のダーツ（ｅ１，ｅ２）の間のインボリューションによって暗黙的に定義されるエッジに鑑み、Ｇ１のブルームフィルタが区間［１５，２５］を含む区間［１０，３０］をカバーする［１０，２０］および［２０，３０］からの軌道に関連付けられたバケットを有する場合、ブルームフィルタデータ構造を、ブルームフィルタに偽陰性が存在しないことに注目し、Ｇ１におけるテストおよびＧ２におけるテストによってバケットをチェックするために使用することができる。しかしながら、偽陽性の可能性がある。当業者であれば、ブルームフィルタのサイズを許容可能な値（例えば、１％の偽陽性の場合は１０ビット、あるいは偽陽性の割合をさらに下げる必要がある場合には、それ以上）に設定することができる。いずれにせよ、候補をすぐに直接確認することができる。
【００７２】
図２は、ネットワークとその一般化組み合わせマップ（ＧＭＡＰ）への符号化との関係を示す。元のソースデータネットワーク（１）およびネットワークから導出された組み合わせマップ（２）が、図２に示されている。所与の頂点の周りのエッジの方向の明示的な符号化が存在し、エッジはダーツと呼ばれる２つのハーフエッジで構成され、各々のダーツはそれが結び付けられた頂点に起点を有するグラフ（１）とも呼ばれるネットワークは、ＧＭＡＰ（２）と等価である。ダーツによって定義された２つのハーフエッジが同じエッジを決定するという事実は、エッジ内の第１のダーツの後継が第２のダーツであり、第２のダーツの後継が最初のダーツであるように、インボリューションと呼ばれる置換関数に記録される。Ｌｉｕ  １９９９［１］によると、方向付けられたエッジは、４つのダーツ、すなわちエッジを指定するための２つのダーツ、およびエッジの相対的な向きまたは方向を指定するための２つのダーツを必要とし、完全に方向付けられたネットワークの向きは、ダーツを表す整数の符号の方向についての慣例を単純に使用して達成できるが、ネットワークが部分的に方向付けられ、部分的に方向のない部分を有する場合には、これが不可能であり、４つのダーツが必要である。ダーツがそれらのハーフエッジによっては付随しないが、同じ場所（すなわち、ノード）から始まり得る場合、それらは同じ場所で１隣接（１−ａｄｊａｃｅｎｔ）であり、したがってノードの周囲のダーツの（局所的）配置を定める後継置換である軌道と呼ばれる第２の置換によってノードの周りに定義され、この操作は、一般に、α１−インボルーションと呼ばれる。２つのダーツが互いに異なる２つの場所にあり、それらのハーフエッジ、すなわち０次元のオブジェクトが隣接している場合、２つのゼロ次元の発生は、１次元の線を生成し、そのインボリューションは、一般に、α０−インボリュートと呼ばれ、最も単純なインボリューションは、負の１（−１）を乗算することであり、２回の適用が元の数をもたらす。連続する一連のダーツの各々の軌道は、１つのノードに関連付けられ、このノードの周りを反時計回りに回るときに遭遇される一連のダーツを符号化する（例えば、図１の軌道（６，７，８）、（２））。フェースの隣接性ならびにボリュームまたはハイパーボリュームの隣接性の置換は、当業者にとって一般化組み合わせマップについて一般的に定義および理解される。例えば、図２（３）および図２（４）を参照すると、ネットワーク（３）は、フェース隣接関係「Ｔ」および「Ｒ」、ならびに０次元の隣接性、１次元の隣接性、または２次元の隣接性をそれぞれ有することに基づいてエッジ、頂点、および面についてそれぞれα０、α１、およびα２とマークされたインボリューションタイプが存在する組み合わせマップ（４）を使用して表される。本開示は、ＧＭＡＰＳを詳細に操作する方法を、それらの方法のすべてがＬｉｕ［１］およびＫｒｏｐａｔｓｃｈ［７］の参考文献における説明および方法の標準的な部分であるため、詳述しない。また、図１（３）の（Ｄ）、（Ｅ）とラベリングされたエッジが、ダーツのペアのペアによって表現されていることに注意すべきである。２つのダーツペアが同じ共有エッジを表している場合、それらは、（３，−３）の番号が付けられたダーツが「Ｔ」に属し、（８，−８）のラベルが付けられたダーツが「Ｒ」に属するように、異なるｋコンプレックスでラベリングされて定められ、この場合、２つのダーツペアは１つに縫い合わせられている。それらを分離するために、この操作をアンソーイング（ｕｎｓｅｗｉｎｇ）と呼ぶ。組み合わせマップのサブマップのダーツのｋソーイング（ｋ−ｓｅｗｉｎｇ）によって、マップ内のオブジェクトを組み合わせることができる。ダーツを使用してオブジェクトを結合する操作は、一般に、縮約と呼ばれる。
【００７３】
以上で明らかにされたように、一般化組み合わせマップ（ＧＭＡＰＳ）は、ダーツと呼ばれる基本要素間の相対的隣接関係の置換の符号化の概念に基づくトポロジカルおよび組み合わせデータ構造である。本発明は、ハーフエッジダーツおよび空ダーツという２種類のダーツを使用する。空ダーツは、アルゴリズムがサイクルをツリーへと変換するためにほどかれ、もしくは反対にツリーをサイクルへと変換するためにダーツを加えるオブジェクトのインシデントペアに依存する部分的な組み合わせマップまたは部分構造を定めるために使用され、あるいは空ダーツは、本発明のアルゴリズムの目的で構造を完成させるために「ブランク」を埋めることができる。ダーツの間には、次元によって定義される隣接関係が存在し、空ダーツは定義された次元を持たない（すなわち、ゼロではないが未定義であり、空のダーツは必要とされるときにいつでも特別にマークされ、それは通常はきわめてまれである）。単一のハーフエッジダーツは、ゼロの次元を有し、ダーツが一部分であり得る次元Ｎのオブジェクトとは別個かつ区別されるｋ次元のセルとして次元を参照すると好都合であり、したがって、ｋ＝ｄｉｍ（ｃ）は、セルｃの次元を表し、Ｎは、オブジェクトの次元を表す。したがって、０セルは頂点であり、１セルはエッジであり、２セルはポリゴンであり、３セルは多面体であり、以下同様である。ダーツは、縫い合わせられ、あるいは分離時にほどかれ、隣接フェースの場合、各々のフェースがそれを定義するダーツのセットを有するように、「共有」エッジが分離される。ダーツの縫い合わせは、置換操作によって定義され、置換演算子が、ダーツから組み合わせマップを構築する。ダーツは、本発明において、２つの他の特性を有し、第１に、それらは整数を使用して命名され、第２に、それらは通常は何らかの種類のコンテンツ（例えば、ソーシャルネットワークにおける人々の名前、またはタンパク質構造における原子の名前など）である他のデータへのポインタである。ポインタとして、ダーツは、さまざまな種類のデータを埋め込むことができ、単一ダーツは、暗黙的にノードを定義し、ダーツの埋め込みは、他の組み合わせオブジェクトまたはマップを含むことができるノードに含まれるデータを定義する。したがって、マップのトポロジ構造は、根底にあるトポロジまたはスケルトンにジオメトリまたは形状の特徴を接続するように機能することができる埋め込みとは異なる。
【００７４】
化学情報学の分野、とくには定量的構造活性相関（ＱＳＡＲ：Quantitative Structure Activity Relationship）モデリングの分野において、Ｈｏｓｏｙａ  Ｉｎｄｅｘ（細矢インデックス）あるいはＷｉｅｎｅｒ  Ｉｎｄｅｘ（ウィーナーインデックス）および多数の他のインデックスなど、研究中の化学物質のグラフについて計算することができる多くのトポロジインデックスが存在する［２］。これらのインデックスは、基本的に、化学構造の根底にあるグラフの連結マトリクスおよびグラフの原子の特性（原子の電気陰性度の値など）についての関数である。本発明では、ネットワークまたはグラフの組み合わせマップから導出されたマトリクスについての関数であり、接続性だけでなく、グラフ内の経路の組み合わせ構造も表すことができる一般関数が使用され、他の関数が、グラフの重みまたは特性（すなわち、着色）を表すことができる。したがって、我々は、マトリクスについての我々の修正された関数を、マトリクス特性関数と呼ぶ。本発明では、多数のマトリクス特性関数が計算され、値のベクトルを生成する。
【００７５】
Ｑ−ＭＥＤＯＩＤＳグラフ（したがって、ＧＭＡＰ）パーティショニングは、以下のとおりであり、すなわちＱ−Ｍｅｄｏｉｄに対応する領域ラベルのｄ次元ベクトルを有するベクトルによって定義され、ノードセットのロケールのベクトルは、Ｇｕｄｋｏｖによる研究およびＲａｔｔｉｇａｎの研究によって領域を構築するというアイデアに基づく。グラフを領域に分割するＱ−Ｍｅｄｏｉｄｓを構築するために、以下のＱ−Ｍｅｄｏｉｄｓアルゴリズムのステップ１〜１０に示されるとおりのアルゴリズムステップを使用する。
【００７６】
Ｑ−Ｍｅｄｏｉｄｓアルゴリズム
ここで、図３を参照すると、Ｑ−Ｍｅｄｏｉｄｓアルゴリズムは、３つの部分を含み、すなわち第１に、弱クラスタを生成するために頂点を仮想粒子として扱うことによってグラフのジオメトリを計算し、第２に、ネットワークメドイド（ゾーンまたはロケール）を計算し、最後に、局所近傍のＱ−Ｈａｓｈｉｎｇ要約を計算し、ハッシュをローカルインデックスブルームフィルタへと符号化する。これらの各々は、別々に扱われ、本明細書において説明される。第１に、グラフの弱いパーティショニングが説明され、当業者にとって明らかであるように、メドイドを構築する目的において強いパーティショニングは必要でない。フロー図は、力場式から出発し、ステップを伴うための以下の説明によって詳述される。
【００７７】
１．ｎ個の頂点のグラフが与えられた場合、ｎ個の頂点は、ｎ個のすべての点が（ｎ−１）次元における単位超球の表面に位置するように埋め込まれたものとして扱われるｎ次元のＧＭＡＰを形成するために均一に分布したｎ個の仮想粒子としてモデル化される。ＧＭＡＰは、サブマップの集合に分割される必要があり、好ましい実施形態は、Ｑ−ｍｅｄｏｉｄｓのアルゴリズムを用いて分割を行うことである。
【００７８】
Ｑ−Ｍｅｄｏｉｄｓは、シードがランダムに選択される（Ｓ１）がゆえにＫ−Ｍｅｄｏｉｄｓとは異なり、１つのダーツが属するクラスタの平均数をＸとする。シードダーツから出発して、各シードは、元のダーツから等距離にあるすべてのダーツが説明されるまでクラスタへと成長させられ、いくつかのダーツが訪問されない場合、それらは必要に応じてランダムに最も近い隣接したダーツに割り当てられる。次に、頂点が超球の表面に触れているダーツを含むポリトープを表現し、ダーツ（すなわち、対応する頂点）の任意のペアの間の距離を以下のように定義する。
【００７９】
【数１】
2020119591.tif 000003
２．以下のように定数Ｋに対して設定されるグラフの頂点ｎに作用するＵによる反発および引き付けのポテンシャル力の比を定義する。
【００８０】
【数２】
2020119591.tif 000004
正規形へのマトリクス再配置のためにＫ＝１を設定する。
【００８１】
３．ｎ次元のＧＭＡＰは、（ｎ−１）の超球に埋め込まれた２次元フェース、１次元エッジなどのｋ−複体（すなわち単体的複体）に対する種々の等価物で構成されます。これらのシンプレックスの各々について、シンプレックスに外接する単体球を定義し、その半径をｒとする。単位（ｎ−１）−超球に埋め込まれたｎ−ＧＭＡＰは、単体球の中心と超球の中心との間の距離を、
【数３】
2020119591.tif 000005
として有する。
【００８２】
ＧＭＡＰの単体複体（サブマップ）の単位ベクトルをｓと定義する。単位ベクトルｓを用いて、元のＧＭＡＰのｎ個のベクトルおよび距離ｄを計算する。
【００８３】
【数４】
2020119591.tif 000006
および
【数５】
2020119591.tif 000007
４．ベクトル点ｎとシンプレックスｓの単位ベクトルとの間の角度をθｓとして計算する。
【００８４】
【数６】
2020119591.tif 000008
５．  ＧＭＡＰの２つの隣接するｐおよびｑ（すなわち、隣接するシンプレックス）の中心間の角度θｐｑを、
【数７】
2020119591.tif 000009
として計算する。
【００８５】
６．引き付け（および、符号の変化による反発）の力を
【数８】
2020119591.tif 000010
として設定する。
【００８６】
７．イプシロンε、およびイプシロンの倍数をしきい値として使用し、固定点平衡を定数Ｃとして設定する。
【００８７】
【数９】
2020119591.tif 000011
８．次のようにルールを使用して力を計算する。
【００８８】
ａ．頂点が隣接している場合、引力（負の符号）を計算する。
【００８９】
ｂ．頂点が直接には接続されていない場合、反発を計算する。
【００９０】
ｃ．頂点がグラフ上の終端ノードである場合、近接を１／εに制限する。
【００９１】
ｄ．（ｉ）最小の変化を前回の値のパーセンテージとして測定すること、または排他的かつ好ましくは、（ｉｉ）ノードの次数に等しい固定された回数の反復について繰り返すことのいずれかを選択することによって、固定点平衡に達するまでステップ（ａ）〜（ｃ）を繰り返す。
【００９２】
９．次のようなルールを使用してＱ−Ｍｅｄｏｉｄｓを計算する。
【００９３】
ｅ．シードノードを選択することによって確率的にグラフをあふれさせる。
【００９４】
ｆ．各シードノードについて、その隣人をチェックして、より高いノード次数を有するかどうかを調べ、それを新しいシードとして選択する。
【００９５】
ｇ．Ｑ−Ｍｅｄｏｉｄは、シードにゾーンラベルを割り当てることによって生成される。
【００９６】
ｈ．Ｍａｔｔｈｅｗ  Ｊ．Ｒａｔｔｉｇａｎ，Ｍａｒｃ  Ｍａｉｅｒ，ａｎｄ  Ｄａｖｉｄ  Ｊｅｎｓｅｎ．２００７．Ｇｒａｐｈ  ｃｌｕｓｔｅｒｉｎｇ  ｗｉｔｈ  ｎｅｔｗｏｒｋ  ｓｔｒｕｃｔｕｒｅ  ｉｎｄｉｃｅｓ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ
ｔｈｅ  ２４ｔｈ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎｅ  ｌｅａｒｎｉｎｇ（ＩＣＭＬ’０７），Ｚｏｕｂｉｎ  Ｇｈａｈｒａｍａｎｉ（Ｅｄ．）．ＡＣＭ，Ｎｅｗ  Ｙｏｒｋ，ＮＹ，ＵＳＡ，７８３−７９０に記載されているように、Ｇｕｄｋｏｖの教示はゾーン距離法のためのゾーニングの計算の繰り返しの必要をなくす動的な粒子場ベースの計算を提供するため、ゾーンを複数回再計算する代わりに１回の反復のみを使用するＮＳＩアルゴリズムによって続行する。
【００９７】
１０．以下（Ｒａｔｔｉｇａｎらから）を用いてＱ−ＭｅｄｏｉｄｓのセットおよびＱ−ＭｅｄｏｉｄｓのＮＳＩ（ネットワーク構造インデックス：Network Structure Indices）のセットを返し、各々のノードｕおよび領域Ｚについて、ノードｕから領域Ｚ内の最も近いノードまでの距離を、距離関数を使用して計算する。
【００９８】
【数１０】
2020119591.tif 000012
Ｄｉｓｔａｎｃｅ  Ｔｏ  Ｚｏｎｅ（ＤＴＺ）のネットワーク構造インデックス（ＮＳＩ）は、距離尺度と組み合わせられたノード注釈のセットで構成される。ＮＳＩは、グラフ内のノード間の短い経路の発見を可能にするように設計される。Ｑ−Ｍｅｄｏｉｄｓプロセスとの組み合わせにおいて、ＤＴＺは独立したパーティションセットを生成し、ＤＴＺは、各々のノードおよび各々のパーティションを横切るすべてのゾーンの間の距離を記録する。パーティションが重複している場合、重複領域内のノードを一方または他方の領域にランダムに再割り当てすることによって非重複ゾーンを作成することを選択することができる。ノードが異なるゾーンで重複から除去されない場合、構造の本質的部分がグラフの距離への近似として依然として有効であり、一部が冗長であるにすぎないため、性能の影響は無視できる。
【００９９】
図４は、各々のＱ−ｍｅｄｏｉｄのＤＴＺを示す。Ｑ−ｍｅｄｏｉｄｓの総数は、次元であり、３つの数字は、領域とノードとの間の距離を示し、Ｒａｔｔｉｇａｎらに従い、図は、最も左下のノードを白、黒、および灰色の領域への距離に対応する［０，２，４］というインデックスで示している。このノードから最も右下のノードまでの距離は、４＋５＝９である。
【０１００】
距離測定ベクトルは、各グラフについて計算され、これらの値をグラフＧＵＩＤに対して格納し、さらには呼び出すために、空間データベースを参照することによってコグニティブ構造に加えられる。
【０１０１】
ここで、図５および図６を参照すると、Ｑ−ハッシング関数、またはＱ−ハッシュ（あるいは、単に「Ｑハッシュ」）関数は、動的関数と頂点近傍の周囲のラベルとの間の変動相互作用に基づくともに、グラフのＱ−Ｍｅｄｏｉｄの頂点を中心としたダーツの回転順序およびそれらのＭａｘＲ（メドイドのリンクの最大半径）までの関連パスに別々に基づく。
【０１０２】
粒子のように振る舞う量子にインスパイアされた仮想波パケットであり、仮想量子粒子としての相互作用の数に依存し、確率密度関数シェルの範囲内にあるＱ関数と呼ばれる反復動的相互作用関数の定義から出発し、これらの仮想エンティティを「インタラクトン（Interactons）」と呼ぶ。インタラクトンとシェル境界との間の相互作用は、モデルの対象であり、例えばインタラクトンが電磁気および光子状である場合、適切な振る舞いは、インタラクトンがシェル境界条件に再び遭遇するまでシェル境界（完璧な鏡のように働く）においてシェル内の何らかの他の点へと反射することである。確率密度関数の境界の例は、量子物理学の任意の教科書に見出すことができるが、いくつかの代表的な形状が図５に示されている。電磁波パケット状モデルとしての相互作用の提示は、上記を限定するものではなく、重力子あるいは任意の他の想像上の仮想化された相互作用およびフィールドまたは制約形状を、図６のフロー図に示されるように使用することができる。参考のために、論文Ｖ．Ｖ．Ｓｒｅｅｄｈａｒ，Ｔｈｅ  ｃｌａｓｓｉｃａｌ  ａｎｄ  ｑｕａｎｔｕｍ  ｍｅｃｈａｎｉｃｓ  ｏｆ  ａ  ｐａｒｔｉｃｌｅ  ｏｎ  ａ  ｋｎｏｔ，Ａｎｎａｌｓ  ｏｆ  Ｐｈｙｓｉｃｓ，Ｖｏｌｕｍｅ  ３５９，Ａｕｇｕｓｔ  ２０１５，Ｐａｇｅｓ  ２０−３０に存在する教示が、制約条件、経路、および存在する力学的公式がインスパイアされた粒子の動きの考え方についての背景に関して、本明細書に含まれる。
【０１０３】
Ｑ関数が、２Ｄ円形シェルの場合について、ここに示される。
【０１０４】
【数１１】
2020119591.tif 000013
２Ｄ方向ベクトルｘおよびｙについてのパラメータならびに他の値は、次のように定義される。
【０１０５】
ＱＨａｓｈパラメータセット
Ｃ＝次元
ｘ＝デカルトｘ座標＝初期頂点重み
ｙ＝デカルトｙ座標＝初期エッジ重み
Ｐ＝素数
Ｄｖ＝頂点ｖにおけるダーツからの（浮動小数または整数としての）データム
Ｂ＝２×ハッシュ幅＝最大ビット深度
ハッシュ幅＝ビット数（例えば、１２８）
【０１０６】
関数φは、シェル内での反射において粒子状の挙動を示す仮想化された電磁波パケット光子の位相角を表す。また、データムＤｖについて、ラベルがＡＳＣＩＩまたはＵｎｉｃｏｄｅである場合、その整数値が使用され、別の数量の場合は、その浮動小数点値が使用され、それ以外の場合は、データムを整数（いずれにせよ、そのバイナリ表現）にマップする必要があることに注意すべきである。データムＤｖが、ダイナミクスの変動摂動を駆動し、最終的にはハッシング出力の原因である。
【０１０７】
ｘｙ平面（複素平面と等価）における２Ｄ円形シェルについて、インタラクトンの振る舞いを、次のようにデカルト座標においてモデル化することができる。
【０１０８】
【数１２】
2020119591.tif 000014
Ｊｏｈｎ  Ｋｉｎｇ  Ｇａｍｂｌｅ，Ｍａｒｋ  Ｆｒｉｅｓｅｎ，Ｄｏｎｇ  Ｚｈｏｕ，Ｒｏｂｅｒｔ  Ｊｏｙｎｔ，ａｎｄ  Ｓ．Ｎ．Ｃｏｐｐｅｒｓｍｉｔｈ，Ｔｗｏ−ｐａｒｔｉｃｌｅ  ｑｕａｎｔｕｍ  ｗａｌｋｓ  ａｐｐｌｉｅｄ  ｔｏ  ｔｈｅ  ｇｒａｐｈ  ｉｓｏｍｏｒｐｈｉｓｍ  ｐｒｏｂｌｅｍ，ＰＨＹＳＩＣＡＬ  ＲＥＶＩＥＷ  Ａ，８１，０５２３１３（２０１０）およびＶｌａｄｉｍｉｒ  Ｇｕｄｋｏｖ  ａｎｄ  Ｓｈｍｕｅｌ  Ｎｕｓｓｉｎｏｖ，Ｇｒａｐｈ  ｅｑｕｉｖａｌｅｎｃｅ  ａｎｄ  ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ  ｖｉａ  ａ  ｃｏｎｔｉｎｕｏｕｓ  ｅｖｏｌｕｔｉｏｎ  ｏｆ  ａ  ｐｈｙｓｉｃａｌ  ａｎａｌｏｇ，ｃｏｎｄ−ｍａｔ／０２０９１１２，２００２の教示に従い、Ｇｕｄｋｏｖらがグラフについて１つの量子または古典的なランダムウォーキング粒子だけで推測したため、特定のグラフを区別することは不可能であるが、少なくとも２つの粒子が必要であるとＪｏｈｎ  Ｋｉｎｇ  Ｇａｍｂｌｅが述べているため、我々は２つの相互作用波パケットを使用し、我々は、第１に、我々の手法がグラフ全体ではなくてグラフのロケールに適用され、第２に、我々の手法がブルームフィルタ内の他の高速ハッシュとのハッシュを使用する目的でグラフ内の頂点の局所近傍およびそのラベルのハッシュサマリをもたらすことを、指摘する。ハッシュは、局所インデックスについてブルームフィルタを必要とせずにグラフにおいて単独で使用され得るが、好ましい実施形態は、代替ハッシュ関数（すなわち、粒子のモデル）で値を計算し、ブルームフィルタに挿入することである。したがって、Ｑ（Ｋ）とＫとが（所望の数の仮想インタラクトンとして）ａ，ｂ，ｃ，．．．とラベリングされた相互作用である最小二者Ｑ関数を書くことができる。最小の好ましい実施形態は、２つの相互作用であり、したがって我々は、１つの相互作用ペアとして以下の組み合わせＱ（ａ，ｂ）を有し、次に他のペアとしてＱ（ｂ，ａ）を有する（一般に、式は選択されたインタラクトンの数の階乗として増える）：
【数１３】
2020119591.tif 000015
次に、これまでにラベリングした代表的なインタラクトンの式［１］、［２］、［３］、および［４］を使用し、我々は、倍精度浮動小数点数を使用して、最上位６４ビット（ＭＳＢ）を連結し、あるいは最下位６４ビット（ＬＳＢ）またはビット内の任意の一定のオフセットを連結することにより、例えば２５６のハッシュ幅のハッシュコードを書くことができ、すなわち、「＋」記号が連結演算子として解釈される場合、我々は、Ｑ−関数の二重印加（インタラクトンについて２回）を表す。
【０１０９】
【数１４】
2020119591.tif 000016
したがって、
【数１５】
2020119591.tif 000017
ＱＨａｓｈが効果的に機能するためには、初期条件を設定して、起動時にコグニティブメモリ構成内のデフォルトの不変なプリファレンスとして保存する必要がある。これを行うために、我々は、
【数１６】
2020119591.tif 000018
という制約を持つ参照一貫初期化子を使用する。
【０１１０】
ＱＨａｓｈは、さまざまなビット深度に適合させることができ、グラフデータ用に特有に設計されているが、反復システムとして入力データとインタラクトンのダイナミクスの状態との間に相互作用モデルが存在する限りにおいて、他の任意のデータにも適用で可能である。
【０１１１】
Ｑ−Ｍｅｄｏｉｄｓアルゴリズムから各々のラベルリングされたロケールまたはゾーンについて、ＱＨＡＳＨが計算される。各々の同心シェルについて、ローカルブルームフィルタインデックスが計算され、本特許において後に説明されるように、距離が、ブルームフィルタの距離について局所センシティブハッシュに組み合わせられる。
【０１１２】
図４を参照すると、図４の［Ａ］の図は、入力を示し、上述のとおりの矢印［Ｂ］によって表されるプロセスを通じ、Ｒａｔｔｉｎｇｅｒらの教示に従ってディスタンストゥゾーンマップを構築するためのＮＳＩアルゴリズムに関する粒子場ベースのゾーニングによるラベリングを有するゾーン化された出力が、［Ｃ］に示されている。
【０１１３】
１．ＧＭＡＰが図４［Ｃ］のようにＱ−Ｍｅｄｏｉｄｓのアルゴリズムを使用してサブマップの集合へとゾーンかされていると考える。
【０１１４】
２．次に、図５に示されるとおりの選択肢にてインタラクトン粒子の２Ｄまたは３Ｄあるいは他の拘束形状を選択し、図６の方法に従ってＱＨａｓｈ関数を計算し、ここでプロセスはＱ−Ｍｅｄｏｉｄのランダムな選択で始まる。
【０１１５】
３．図６のようなステップからのラベリングされた頂点を考え、図４［Ｃ］に示される頂点の近傍における局所表現を格納するローカライズされたブルームインデックスを作成し、したがってＲａｔｔｉｎｇｅｒらのＮＳＩアルゴリズムを使用した長さ限定（何らかの最大長まで）最短経路探索アルゴリズムを使用してそのメドイドおよびそのラベルを作成する。
【０１１６】
４．次に、図７を参照して、ローカライズされたブルーム頂点の構築を制御するために２つのしきい値ＭａｘＲおよびＮｕｍＯｒｂｉｔｓを使用する。
【０１１７】
ａ．ＭａｘＲは、所与のダーツをルートの始点として使用するダーツ（それぞれ、頂点）の近傍の最大半径である。範囲の境界であるダーツの局所の軌道を制限する図７に示されるとおりのシェル内のＭａｘＲ半径よりも小さいエッジの各々の増分に関して、エッジ増分が幅優先で実行され、これにより、ダーツ（すなわち、頂点）の軌跡としてのインボリューション（すなわち、エッジ）のセットがもたらされる。このプロセスが続けられ、最初にルートのダーツの周りにエッジ増分幅の同心円（すなわち、シェル）を形成する。
【０１１８】
ｂ．次いで、同心な幅優先範囲の数が数えられ、格納された値として使用されるか、または先験的に固定された制約値として使用される場合、近傍の同心範囲の数を制御する。
同心の幅を、Ｋ−ｍｅｄｏｉｄｓから見出される少なくとも２つのダーツ（それぞれ、頂点）を含む最初の最小半径として定義される最小半径からＭａｘＲまでの区間範囲によって定義することができる。
【０１１９】
ｃ．組み合わせマップは、ロケールを有し、これらのロケールは、Ｋ−ｍｅｄｏｉｄｓアルゴリズムによって発見されたダーツ周辺のインボリューションによって定義され、この幾何学的および構造的プロセスが、本特許に特有の特別なやり方で構築されるロケールベースのブルームフィルタを定義および構築するために使用される。
【０１２０】
ｄ．時計回り（すなわち、最も内側の円、あるいは球または超球）の（ハイパー）パスの同心シェルの周りを移動するルートダーツの周囲の軌道、他のダーツ（元のグラフのエッジまたは頂点）が遭遇され、バケットが、同心の軌道ごとに１つずつ、ダーツから頂点へのインボリューションインデックスとして構築される。
【０１２１】
ｅ．元のグラフの出発の頂点を定義するルートダーツまでの最短距離が、頂点の周りの回転の方向および区間の半径の両方に関連付けられた単一の複素数値の二進数を使用してバケットに挿入されるダーツ（すなわち、同心円の最小半径および最大半径の間のダーツ）。二重に、エッジインデックスについて、頂点の代わりに、ＧＭＡＰが元のグラフの二重表現を提供するがゆえにエッジがバケットに追加される。明らかに、ダーツから頂点へのインボリュートインデックスは、保証はされないが、頂点の複数のダーツが同じエッジを共有する可能性があるため、エッジからダーツへのインボリュートインデックスよりも小さい可能性が高い。図７は、シェルが占められている場合に各シェルに１つずつ、これらの複素２値のブルームフィルタインデックスの一般的な構造を示している。
【０１２２】
クエリパターンは、頂点ｖ１およびｖ２のマッチが図７によればδ距離の範囲内でなければならず、このδがコグニティブメモリデータベースのすべてのエッジで同じであることを表している。線形スケーリングの代わりに対数を使用してシェルを構築する場合、これはデータベース全体およびすべてのグラフに対しても保持されなければならず、したがって部分構造の探索ならびに本方法による構造の符号化のためのユーザ選択パラメータである。グラフの各々のエッジｅに範囲［ｍｉｎ（ｅ）、ｍａｘ（ｅ）］が関連付けられており、各々のエッジについて、エッジを指定するインボリューションを定義するダーツが存在する。しかしながら、異なるエッジは、Ｑ−Ｍｅｄｏｉｄｓアルゴリズムの結果として異なる範囲を有することができる。範囲の区間は、端点（頂点）の一致の間の最短距離をもたらす。
【０１２３】
各々のメドイドについて、各々のゾーンＺの中心ｖが存在する。三角形の相当により、ゾーン間の距離は、ｖ１およびｖ２の間の最短距離であり、図４のようにゾーンラベルまでの距離によって近似される。いくつかの暗黙の関係が存在する。例えば、ｖ１からｖ２へのエッジが範囲［１０，２０］を有し、ｖ２からｖ３へのエッジが［３０，５０］にある場合、（ｖ１，ｖ３）からの区間は、［１０，７０］の範囲内でなければならない。ｖ１およびｖ３の間の距離についてネットワーク構造インデックスを用いてゾーンまでの距離によって与えられる範囲が［２０，８０］である場合、真の暗示範囲は依然として［２０，７０］に存在すべきである。
【０１２４】
コグニティブメモリは非常に大きく設計されているので、インデキシング構造は、縮約ならびにＱハッシングおよびブルームフィルタを使用して局所的に要約された情報へのこの好ましい実施形態における強い信頼を使用する。利点は、グラフを動的に更新する場合に、インデキシング構造のわずかな部分のみを修正すればよい点である。本発明が（おそらくは重複する）ゾーンのセットの強化されたパーティションベースのインデキシング構造を使用することに鑑み、挿入または削除操作によってエッジまたは頂点が変更されるとき、ゾーンのみを修正すればよい。
【０１２５】
ここで図８を参照し、ネットワークを組み合わせマップとして表現する方法をすでに説明したので、ダーツとその詳細を組み合わせマップとして指定する詳細を省き、単純な４ノードグラフを示す。図８のグラフは、ｖ１：３、ｖ２：９、ｖ３：５、およびｖ４：７としてのノードを有する単純に着色された（すなわち、ラベリングされた）グラフであり、ノードラベルがｖ１、ｖ２、ｖ３およびｖ４であり、コンテンツが３、９、５、および７である。
【０１２６】
図９は、図８のネットワークのトポロジ的接続構造を表すが、着色（すなわち、ノードｖ１、ｖ２、ｖ３、およびｖ４の値３、９、５、および７）を符号化しないネットワークの隣接マトリクスを表す。
【０１２７】
図１０は、マトリクスへと符号化する図８のネットワークの着色を示しており、対角線がノードを着色し、３、９、５、および７としての図８のネットワークの値が、頂点の置換が着色の置換と同等であるように対角線上に位置している。図１０のマトリクスは、独自に着色されたネットワークを符号化する。ノード１および４の間のエッジについては、エッジに対してｖ１４を書き込むだけである。図８のグラフおよび図１０のマトリクスを参照して、以下を定義する。
【０１２８】
離散カラーネットワーク表現コード（ＤＣＮＲＣ）を生成するためのアルゴリズム：
１．ラベルを識別し、これらを固有の整数ラベルを有するダーツへとマップする
ｖ１１＝３；ｖ２２＝９；ｖ３３＝５；およびｖ４４＝７；
［ｖ１１，ｖ２２，ｖ３３，ｖ４４］＝［３，９，５，７］
２．ノード間の接続を識別する
ｖ１２＝０；ｖ１３＝１；ｖ１４＝１
ｖ２３＝１；ｖ２４＝１
ｖ３４＝１
［ｖ１２，ｖ１３，ｖ１４，ｖ２３，ｖ２４，ｖ３４］＝［０，１，１，１，１，１］
３．単純な連結によって２進数の［０，１，１，１，１，１］を変換し、先頭のゼロを維持するために先頭の１を加える：
［０，１，１，１，１，１］→１，０，１，１，１，１，１］＝９５
９５を十進法の同等物として示す。コード［３，９，５，７］は、ネットワークのすべての可能な置換（すなわち、着色）のセットからの置換であるという点で、ネットワークの固有の着色を表す。
【０１２９】
４．この置換を変換のペア、すなわち
（ｉ）Ｌｅｈｍｅｒ  Ｃｏｄｅ、および
（ｉｉ）Ｆａｃｔｏｒａｄｉｃ
を使用して固有のインデックスに変換する。
【０１３０】
［３，９，５，７］のＬｅｈｍｅｒコードは、ベクトル［０，２，０，０］である（対照的に、ベクトル［３，９，５，７］のＬｅｈｍｅｒコードは、数置換［４，１１，７，１０，１，２，３，５，６，８，９］である）。
【０１３１】
［３，９，５，７］の離散的コードは、以下のように計算される：Ｐ＝（３，９，５，７）は、Ｓ９における置換であり、そのＬｅｈｍｅｒコードは、Ｌ（Ｐ）＝［０，２，０，０］である。
【０１３２】
Ｆａｃｔｏｒａｄｉｃ  ｂａｓｅを使用して、右から左へと０！から、
０×３！＋２×２！＋０×１！＋０×０！＝４＋１＝５
の計算を行う。
【０１３３】
Ｆａｃｔｏｒａｄｉｃ形式の９５は、［３，３，２，１，０］である。
【０１３４】
５．ステップ３およびステップ４からの数字のペアを組み合わせ、今や元のネットワークを再現できるようにネットワークを表す数字のペアを有する。
【０１３５】
離散ネットワークカラー表現コード＝ＤＮＣＲＣ＝９５
ベースは、選択された階乗ベースであり、コードが続く。離散非カラーネットワーク表現コード（ＤＵＮＲＣ）を書くために、対角要素の代わりに単にゼロを代入してから、プロセスを繰り返すことができる。
【０１３６】
コードからネットワークを復元するために、最初の数字９５が、色を復元するために逆順のステップで使用される（ＬｅｈｍｅｒコードおよびＦａｃｔｏｒａｄｉｃｓは可逆であるため）。ネットワークを構築するためにコードを直接使用できるので、ネットワークを再構築するためにマトリクスを再構築する必要がないことに、注意すべきである。一般的に、任意のネットワークについて、後にＦａｃｔｏｒａｄｉｃ数およびＬｅｈｍｅｒコードを使用して符号化できる可逆コードを生成することが重要である。
【０１３７】
図８のネットワークおよび図１０のマトリクスを参照すると、図１０のマトリクスのノードに作用する式を示すノード関数中間重み付けマトリクスを生成することができる（図１１）。図１０のこの特定の例におけるノードについての重み付け関数は、図１１を生成するために掛け合わせられる２つの接続されたノードのそれぞれの重みの逆数平方根として定義され、図１２は、図１１のマトリクスのすべての重みの単純な和としての典型的なマトリクス特性関数の計算を示している。この式は、マトリクス特性関数の基本的な計算を示しており、その大部分は、文献において入手可能であり、化学情報学およびグラフ理論の当業者にとって周知であり、［２］に挙げられている種々のトポロジカル記述子および他のグラフ不変記述子から導かれる。このような関数は、本明細書においてマトリクス特性関数（ＭＰＦ：Matrix Property Function）と呼ばれ、ここで図１２を参照すると、マトリクス特性関数は、図１０の入力マトリクスに基づく数１．５０２９５２２７２３０５７７９を生成する。やはり、マトリクス特性関数は、常にではないが通常は、分子記述子に基づく。例えば、ノードによって与えられた色が存在しない場合、Ｒｏｂｅｒｔｏ  ＴｏｄｅｓｃｈｉｎｉおよびＶｉｖｉａｎａ  Ｃｏｎｓｏｎｎｉの参考文献［２］に示されているように、ＷｉｅｎｅｒまたはＨｏｓｏｙａインデックスならびに他の関数のような接続インデックスを使用するなど、純粋にトポロジカルな他の関数を使用することができる。
【０１３８】
図１３を参照して、ネットワークが暗黙的に存在し得る任意のラベリングされていない標識記号シーケンスを、シーケンス内の関係記号−隣接構造の経路グラフのマトリクスとして変換する方法を説明する。ネットワークは、そのノードまたはエッジの固有の整数ラベリングが存在しない場合、ラベリングされていない。さらに、任意のネットワークを、任意の深度の経路グラフのマトリクスに書き換えることができ、最大深度は、グラフ内の最も遠い２つの接続ノードの間の最大パス長によって制限される。しかしながら、例示および簡単さの目的で、英語の単語の例を使用し、今回の場合には、４つの文字｛ｔ，ｅ，ｓ，ｒ｝のセットで構成される単語「ｔｅｓｔｅｒ」を使用する。図１３は、各要素が、｛ｅｒ，ｅｓ，ｅｔ，ｒｓ，ｒｔ，ｓｔ｝として、４つの固有の文字のセットからの６つの基本文字ペアのうちの１つを接続するパスであるマトリクスを示す。
【０１３９】
ラベリングされていない記号のシーケンスをグラフに符号化するためのアルゴリズム
１．素数のソースが、ラベリングにおいて使用するために、番号ｎに応答してｎ番目の素数を生成し、０番目のインデックスが１であり、２番目が２であり、３番目が３であり、４番目が５であり、以下同様である。
【０１４０】
２．各々の固有文字が固有の素数で置き換えられ、この具体例では、ラベリング規則は、ＵｎｉｃｏｄｅまたはＡＳＣＩＩのキャラクタコードあるいは文字を指すダーツの整数値がｎ番目の素数をインデックスするために使用されることである。
【０１４１】
３．各々の文字（または、記号）に固有のアドレスが与えられ、記号のシーケンスの場合には、これは先のステップ２からの素数によってインデックスされた位置１の最初の記号から始まる整数位置カウントである。したがって、この符号化方式を使用するｔｅｓｔｅｒのコードは、［６４１，５４７，６３１，１２８２，１０９４，６１８］である。
【０１４２】
４．文字の各ペアについて、文字ペアの間のパスが、介在する記号遷移のカウントとして測定される。したがって、文字「ｔ」と「ｅ」との間には、１つの遷移が存在する。「ｔｅｓｔｅｒ」の文字「ｔ」と「ｓ」との間には、２つの遷移（ｔからｅおよびｅからｓ）と、１つの遷移（ｔからｓへと逆行）とが存在する。すべてのパスは、ユーザ定義の最大ｋ−深度までカウントされる。単語「ｔｅｓｔｅｒ」の例では、深度は５に設定されている。
【０１４３】
５．表１は、文字とコード値との間の最終的なマッピングに言及しており、位置値は文字を指すダーツを表し、出現値が素数値を乗算し、ここから表２をパス長（深度５まで）のマトリクスとして導くことができる。深度は、ユーザが選択した小さなパラメータであり、グラフ全体をカバーする必要はなく、通常は２と７の間である。
【０１４４】
６．単語「ｔｅｓｔｅｒ」について得られたマトリクスは、のパスマトリクスとして表現され、これは表２で指定され、図１３（２）に示され、これを図１４（１）に点線で示されている元の文字ペアで構成された図１３のネットワーク（１）に容易に変換することができる。
【０１４５】
【表１】
2020119591.tif 000019
【表２】
2020119591.tif 000020
図１４（１）は、個々の文字を表すために素数を使用し、パスグラフとして文字列内の文字ペアの間の距離を使用する文字列の符号化を示す。繰り返し文字の場合、復号時の素因数分解がきわめて簡単であるように、位置出現乗数が使用される。組み合わせマップを形成するために使用されるダーツは、常に連続して番号が付けられる。アルゴリズムを、テキストを表すグラフについて示してきたが、グラフは、関係のグラフを使用して表現可能な画像または任意の他のデータを表すことができる。したがって、得られるネットワークの図１４（２）のマトリクスを、図３〜図７に付随する方法を参照して、本発明において先に説明したようにして記述および符号化することができる。単語「ｔｅｓｔｅｒ」を符号化するために使用されるプロセスが、符号化方法、すなわち（文字ペアの）線形ストリームを埋め込むノードへの固有のアイデンティティの割り当てを、任意の線形記号ストリームをグラフとして符号化するために使用できることを示すために例示されている。記号のペアまたは統計分析から得られたバイグラムに限定されず、３つの記号のグループまたはトリグラムを、グラフを表すために同様に使用することができ、例えばテキストのテキストグラフへの処理および変換において、バイグラムまたはトリグラムの使用が有用であり、コグニティブメモリの好ましい実施形態では、バイグラムおよびトリグラムが、記号のシーケンスをネットワークに変換し、次いでＧＭＡＰに変換するために使用される。
データがまだＧＭＡＰでない場合は、これらの方法で入力データを変換する必要がある。
【０１４６】
ここで図１５を参照すると、ネットワーク（１）は、例示の目的で、接続マトリクス（２）に示されている。接続マトリクスは、上方の三角形の数のセットから離散的なコードをもたらし、これらのコードを整数（３）として書き直すことができ、これをＦａｃｔｏｒａｄｉｃ数（４）へと変換することができ、最終的にマトリクスの再現に必要なコード、したがってＤＵＮＲＣ（離散非カラーネットワーク表現コード）と呼ばれるアイテム（５）のコードとしてのグラフへと変換することができる。有色ネットワークの場合、すでに概説した方法が使用され、ＤＣＮＲＣ（離散カラーネットワーク表現コード）が生成される。
【０１４７】
ここで図１６を参照すると、縮約ルール操作の方法が示されている。縮約ルールは、トポロジ的に集中した縮約を適用することによって、ネットワークをより大きな構造からより小さい構造に統合または崩壊させる。これは、縮約が他の次元に進む前に同じ次元で生じることを意味し、換言すると、一般化組み合わせマップの縮約が所与のｋセルから始まり、ｋに等しくない他の次元に適用される前にすべてのｋセルに適用される。
【０１４８】
ここで図１６を参照して、縮約操作を以下のルールで指定することができる。
【０１４９】
縮約ルールの種類
１．ｋ＝１の各々のｋセルについて、エッジ縮約（１）は、エッジ（２）上の隣接するノードのマージおよびエッジの再ラベリングならびに残りのエッジ／ノードの構文表現ツリーへの埋め込みとして定義され、あるいは、
２．ｋ＝０の各々のｋセルについて、ノード縮約（３）は、ノード（４）上の隣接するエッジのマージならびにノードの再ラベリングおよび残りのエッジ／ノードの構文表現ツリーへの埋め込みとして定義され、あるいは、
３．ｋ＝２の各々のｋセルについて、フェース縮約は、隣接するエッジ（６）へのフェース（５）のマージならびに残りのフェース／エッジ／ノードへのフェースの再ラベリングおよび埋め込みとして定義され、各々のｋ＝３について、ボリューム縮約（図１５には示されていない）は、隣接するフェースへのボリュームの縮約であり、任意のｋについて、縮約は、残りのより低い次元のオブジェクトへと再ラベリングおよび埋め込みされるｋ−１次元のオブジェクトを常にもたらす。
【０１５０】
図１７を参照すると、ＧＭＡＰ（１）は、そのダーツ（２）のインボリュートとして表される典型的なノードによって示されており、単純な反転（すなわち、すべてのダーツの向きを逆にする）によって、ダーツ（４）の結果としての逆置換による二重ＧＭＡＰ（３）が生成されている。図１６における定義のとおりの縮約ルールは、本発明に速度、柔軟性、および並列性の付加的利点を提供する暗黙の二重構造の維持ゆえに、任意のＧＭＡＰにおいて暗黙的に更新され、したがって二重マップは常に利用可能である。この方法は、Ｋｒｏｐａｔｓｃｈ［７］による研究に関連しているが、自己ループを有する構造を取り除くために空ダーツを縫い合わせ、したがってルールによって規則的に縮約させることが可能である。
【０１５１】
ここで図１８を参照すると、より大きなＧＭＡＰの一部であり得る小さな組み合わせサブマップ（１）が示されている。本発明の重要な要素の１つは、マップの縮約と、コードの生成と、さらなる縮約が不可能になるまでの操作の反復との結合である。図１８（１）は、ダーツおよび埋め込みオブジェクト（すなわち、ラベルａ、ｂ、およびｃ）の置換を表すバイナリツリー（２）に書き換えられる。本発明の図１８（６）の符号化は、Ｊａｃｏｂｓｏｎ［８］、Ｔａｒａｕ［１０］、およびＭｕｎｒｏ  ａｎｄ  Ｒａｍａｎ［９］による研究から着想したものである。Ｊａｃｏｂｓｏｎの簡潔なツリー表現［８］は、レベル順トラバーサルでノードを列挙するツリーのレベル順単項度順序に基づいており、ルートノードが最初であり、次いですべての子が左から右へと続き、さらにツリーの後続の各レベル（深度）のすべてのノードが続き、それらの単項度（すなわち、０を終端とする１の並び）を符号化する。
【０１５２】
Ｍｕｎｒｏ  ａｎｄ  Ｒａｍａｎ［９］による所与のツリーの括弧言語シーケンス（ｐａｒｅｎｔｈｅｓｉｓ  ｌａｎｇｕａｇｅ  ｓｅｑｕｅｎｃ）は、バイナリツリーの深度優先トラバースによって得ることができ、ノードが訪問されるたびに開き括弧を出力し、左から右へとまずそのすべての子孫、次いでそのすべての子供の後で、閉じ括弧が続き、ツリーの後続の各レベル（深度）のすべてのノードが続く。ひとたび符号化が完了すると、開き括弧および閉じ括弧がそれぞれ０および１で置き換えられ、２進ビットベクトルシーケンスビットが得られる。Ｔａｒａｕ［１０］は、Ａｃｋｅｒｍａｎｎの関数から始まって遺伝的に有限の集合の有限置換に基づくコードを生成し、縮小されたコードおよびネットワークの符号化にも使用することができる最適符号化を導出した。本発明では、ツリーのみを扱うのではなく、任意のグラフを扱い、括弧言語は、縮約させられているロケール内のダーツの整数によって接頭された角括弧で拡張される。この表現は、丸括弧、角括弧、およびダーツの組み合わせを使用して、サイクルおよび他の構造をコード化することを可能にする。ダーツ操作を使用するノードが縮約されると、グラフのトポロジが変更される。縮約ツリーは、マルチウェイツリーとして発生し、標準的な方法でグラフの完全な履歴を提供するバイナリツリーに変換される。
【０１５３】
したがって、各々の縮約操作について、図１８（１）〜（４）を参照して、以下のような一連の再ラベリングルールが存在する。
【０１５４】
構文縮約ツリー構築：
１．空のツリーおよび入力ＧＭＡＰ（１）から出発し、バイナリツリー（２）を生成する。
【０１５５】
２．ｋ−セルの表現をｋ−１−セルへと包むために角括弧「［］」の記号を使用し、置換の順番でレベルｋのセルをグループ化するために丸括弧「（）」を使用する。縮約操作ごとに、ドット「．」を使用して縮約の存在を表す。他のすべての記号は、ダーツのラベルである。
【０１５６】
３．次いで、ノードにｋの値によって使用された縮約操作の名前が含まれているツリーへの分岐を追加する（例えば、ｋ＝０はノード縮約であり、ｋ＝１の場合はエッジ縮約であり、ｋ＝２の場合はフェース縮約である）。
【０１５７】
４．Ｇのｋ−セルの再ラベリングのための子ノードを追加する。
【０１５８】
５．Ｇの各々のｋ−セル、および縮約ルールの影響を受けるダーツの各々の軌道について：
ａ．ダーツの軌道が次元ｋにある場合、ダーツの軌道のためのラベルによってｋ−１における表現を包むために角括弧およびドットを使用し、新たなダーツを作成して、新たなダーツをｋ−１におけるラベルに縫い合わせ、そうでない場合には、
ｂ．ｋにおけるダーツのラベルをｋにおいて縮約させられているオブジェクトに縫い付によって付加する。
【０１５９】
６．各々のリーフについて、縮約操作が利用可能である場合、新しい縮約操作ノードを追加し、図１８（３）を生成し、そうでない場合には、
７．図１８（４）のノードに示されるとおりの完成した縮約ツリーおよびその表現を停止させて返す。
【０１６０】
縮約ツリー表現符号化
１．ツリーの頂上において出発（例えば、図１８の（２））。
【０１６１】
２．各々のノードにおいて丸括弧を開く。
【０１６２】
３．単一の下降の一部ではない各々のエッジにおいて、正の側のダーツ整数で接頭された角括弧を開く。
【０１６３】
４．それ以上（３）が実行できなくなるまで、（２）および（３）を繰り返す。
【０１６４】
５．次いで、角括弧の各ペアを、それが属するダーツの整数コードによって指定されたファンクタへとたたむ。
【０１６５】
６．次いで、下降の各エッジにおいて、丸括弧を閉じる。
【０１６６】
７．ノードまたはエッジがそれ以上訪問されなくなるまで続ける。
【０１６７】
８．すべての左丸括弧を１で置き換える。
【０１６８】
９．すべての右丸括弧を０で置き換える。
【０１６９】
１０．バイナリコードを出力して停止する。
【０１７０】
これらのアルゴリズムは、すべての縮約レベルにおいてグラフの無損失記録を提供する。各々の非リーフノードは、縮約を生成するために使用された２つのノードを表す左右の子を有する。各々のリーフノードは、元のグラフに含まれていたノードを表す。拡張された縮約ツリーでは、ダーツをマージするために使用される演算子を、必要に応じて参照によって保存することも可能である。
【０１７１】
したがって、図１８を詳細に参照すると、（２）を（３）として表すために括弧表記を用いた符号化を適用すると、（２）がさらに書き直され、（４）が生成される。それ以上の縮約の書き換えは不可能である。縮約式（５）は、プロローグ言語表現（５）を生成するためのファンクタの名前としてダーツを使用することによって（４）から生成される。
（５）を使用すると、これを（６）としてプロローグ表現（および、暗黙的にそのツリー）（５）からの記号による純粋な括弧表現に変換することは自明である。左括弧を１で、右括弧を０で置き換えると、（７）における１および０のリストが生成される。（７）の記号を単純に連結すると、コード（８）が生成される。（８）の１０進数は（９）であり、Ｔａｒａｕ［１０］の方法を使用して、記号（１）の記号テーブルの小さな整数のリストへのハッシングが、Ｔａｒａｕ［１０］を使用して自然数として符号化され、次いでそれを使用して１６１５の（９）の結果とともに数のペアへと集められ、Ｔａｒａｕ［１０］の対関数の使用が、入力（１）のストアへと追加されるコード（１１）３６５８８２０を生成する。
【０１７２】
図１９は、符号化を伴う一式の縮約演算ならびにトポロジおよび幾何学のためのマトリクス特性関数の同期した計算をデータベースに記憶される単一の部分構造へと結合させる方法を示している点で、本発明の鍵となる中心部分であり、このプロセスは、さらなる縮約が不可能になるまで縮約によって反復される。図１（１）のグラフから引き出され、図１９（１）として再現されたネットワークが、グラフの縮約変換に対するマトリクス特性関数の挙動を表すベクトルのシーケンスを生成するために使用され、これらの挙動（すなわち、関数の数値出力によって与えられる）が、空間ベクトルストア（通常は、マルチバンテージポイントツリー）に格納される。したがって、次に図１９を参照して、主たるアルゴリズムを記述する。
【０１７３】
縮約ルールアルゴリズム：
（ｉ）隣接関係（すなわち、縮約のためのｋ−セル）および縮約ルールのためのエッジタイプの順番を選択する（図１６において説明したとおり）。図１９の場合、あくまでも説明の目的で、リンクタイプの順番は辞書の順によって｛ｓ，ｔ，ｕ｝であるため、エッジタイプ「ｓ」の周りのノードが最初に縮約され、縮約が「ｓ」の周りでさらに進むことができない場合、縮約させられる次のエッジタイプは「ｔ」であり、ｓおよびｔのエッジタイプのどちらも単独では縮約させることができない場合、「ｓｔ」または「ｔｓ」隣接エッジタイプというこれらの組み合わせが縮約させられる。「ｔｓ」および「ｓｔ」のどちらの隣接も縮約させることができない場合、その場合に初めて、「ｕ」のエッジタイプが縮約に関して考慮される（図１８の縮約表現に示されているとおり）。いずれの場合においても、置換の順序は保持され、縮約が辞書の組み合わせ順序に従って進行する。辞書による順序付けがＴａｒａｕ［１０］による整数序列で置き換えられる場合、縮約は数値の順序および組み合わせにて進行する。トップダウン縮約については、最高のｋ値を有するｋセルを選択し、ボトムアップ縮約については、最低のｋ値を有するｋセルを選択する。最高のｋ値はハイパーボリュームをマージし、次にフェースをマージし、次いでエッジをマージし、最後にノードをマージする一方で、最低のｋ値からの出発は、この逆を実行する。各々の縮約操作について、ラベルは、図１８に示されるとおりの縮約表現符号化を使用してそれらの置換の順序を維持してマージされます。したがって、あくまでも説明の目的で、エッジ｛ｓ｝に関するノード｛ｅ，ｄ，ｆ｝の縮約のための図１９（１）において、（ｄ）がｅおよびｆがエッジタイプ「ｓ」について縮約させられるノードであることを識別する図１９（２）に示される新しいラベリング［ｅ（ｄ）ｆ］．ｓが生成される。
【０１７４】
任意の所与のレベルにおけるネットワーク（ＧＭＡＰ）の縮約のための選択のルール
ａ．最高のダーツ数（すなわち、ノードにとって単にノードにおけるそれらの濃度にすぎないダーツの最高のα０軌道）を有するノードを選択し、このノードを、縮約ルールがノード隣接縮約に従うときに縮約が生じる中心とする。任意の要素の場合、縮約順序（幅優先または深度優先）が選択された後に、ダーツの軌道の濃度に基づいて最高のｋ−セルの要素が最初に選択される。
【０１７５】
ｂ．丸括弧内のラベルを使用して最高のｋ−セルをラベリングする。
【０１７６】
ｃ．接続されたノードの各々について、ノードラベルを連結し、ｋセルについてそれらの置換順序を保持し、これらをｋセルの括弧で囲まれたノードラベルの構文表現に追加する。
【０１７７】
ｄ．記号を接続するリンクの種類を示すために「．」（すなわち、ドット記号）を使用して角括弧で先行する（ｃ）からの表現を包む。
【０１７８】
ｅ．さらなるラベルを所与の縮約レベルにおいてマージさせることができなくなるまで、選択された縮約順序で各々のｋセルのサブツリー近傍の各々についてステップ（ａ）〜（ｄ）を繰り返す。
【０１７９】
ｆ．次元ｋの任意のｋ−セルがラベルを持たない場合（例えば、フェースのセットがフェース−１、フェース−２などとラベリングされていない場合）、置換の順序におけるｋセルのダーツの軌道がラベルである。このラベルを、フェースラベルダーツをそれらの記号（または、数字）名へと記憶するためのポインタが格納されていれば、別のラベルで置き換えることができます。
【０１８０】
（ｉｉ）選択された縮約隣接関係について、ラベルをマージされた隣接エレメントのペアごとに構文表現ツリーへと移動させることによってそれらの置換の順序を保持するダーツを削除する。図１８の方法に従い、必要に応じてそれぞれハイパーボリューム、フェース、およびエッジのラベルをそれぞれ生成することができる。場合によっては、一部のｋ−セルを部分的に定義できるようにして、開いた組み合わせマップをもたらすことが有用であり得る。この方法は、ダーツのセットに特別にマークされた空ダーツを追加し、ダーツを空ダーツと縫い合わせることを可能にすることである。エッジの両方のダーツが同時に縮約または除去されるがゆえに、正のダーツは符号によって符号化されるため、縮約レベルを各々のエッジの１つのダーツにおいてのみ符号化することができ、ダーツの半分だけを格納すればよく、残りはインボリューションによって暗黙的に定義される。
【０１８１】
（ｉｉｉ）図１９（７）の項目として示される最高縮約レベルは、単一のノード（ノード隣接縮約の場合）、あるいはボリュームまたはフェース隣接縮約のそれぞれの場合の単一のボリュームまたはフェース、またはエッジ隣接縮約の場合の単一のエッジのいずれかである。縮約ルールが、無向エッジまたは対称関係が各々のエッジについて１つのダーツペアを使用して格納されるというルールで無向エッジを最初に（すなわち、一度に４つのダーツ、または有向エッジの場合は８つのダーツ）縮約させる場合、各々のエッジにおける一方向から他方への有向関係は、エッジ上の無向ダーツの符号を一致させるか、あるいは逆方向について、所与のエッジを定めるダーツの第１のペアの符号を一致させない。
【０１８２】
（ｉｖ）すべてのダーツのテーブルが維持され、各々の縮約操作について、縮約表現ツリーが維持され、随意によりハッシュマップなどの標準的な技術を使用してネットワークの結合されたラベルについて図１８のように符号化された置換が格納される。
【０１８３】
図１９を参照し、本発明の主要かつ最も重要な部分が、本実施形態にとって絶対的に重要な結合された二重演算であることを繰り返す。第１に、図は（図１０、図６、および図７のように）マトリクスの値を生成するためのマトリクス特性関数を１つだけ示しているが、好ましい実施形態は、ｋ個の異なる関数を使用してｋ次元ベクトルを生成し、これがｋ次元マルチバンテージポイントツリーにおいて点として格納されるとともに、ｋビットのブルームフィルタへのフィットのための値として抽出され、第２に、最も単純な場合にはノードをマージしてダーツを削除することを含む隣接要素の削除、あるいは隣接エッジのマージ、およびダーツの埋め込み（すなわち、ラベル）の置換の順序を保持し、より高い次元において、ダーツに隣接するフェースを削除し、縮約ルールによって指定されるように単一ノードへとフェースラベルの通常の置換にフェースをマージすることによるノードのマージのいずれかによるＧＭＡＰの縮約の動作が行われる。図１９は、ノードによる縮約を示し、次いでエッジを削除し、隣接セルのラベルを新たなセル（すなわち、ノード）へと連結することによるエッジについての縮約を示す。ＧＭＡＰモデルは、ノードがエッジとなり、エッジがノードとなるように、（図１８（１）および（３）に示されるような）二重グラフの生成を自動的に可能にし、したがって本発明の方法は、必要に応じて２組の値を生成するために二重グラフについて再び計算されることができる。各々の縮約において、表現されたネットワーク構造は、より小さいｋ−１次元の形態へと崩壊させられるが、縮約ルールは、ｋからｋ−２に縮約し、あるいは一般的にはｋ＞ｎについてｋ−ｎに縮約するように指定されることができる。一般に、縮約操作は蓄積され、構造における縮約の操作の回数、反復、および結果を表す表現ツリーに格納される。反復の回数は、構造のサイズに比例する。
【０１８４】
図１９を参照すると、（１）〜（７）は、ラベリングされ、連続して縮約させられる典型的なネットワークを示す。この場合、図１９（１）自体の反復回数はゼロである各々の縮約反復について、ネットワークグラフの関数を計算することができる。ベクトルを協働して表す複数のマトリクス特性関数を計算することができる。この例の場合、あくまでも例示を目的として、各々の反復（すなわち、縮約レベル）ごとに１要素ベクトルを計算した。各々のレベルにおけるベクトルの集合は、グラフに作用する関数の挙動を表す。図１９の（７）は、さらなる縮約を行うことができない点を表し、停止縮約である。
【０１８５】
図１９を参照すると、詳細には、以下の一連の動作が行われる。
【０１８６】
１．入力グラフは、ノードラベル｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｍ，ｎ，ｏ，ｐ，ｑ，ｒ｝によって表されるデータを埋め込んだ多数のノードと、｛ｓ，ｔ，ｕ｝とラベリングされたエッジタイプとを有する。グローバルユニークアイデンティティ指定（ＧＵＩＤ）が、「ｇｍａｐ１」として生成される。例えば、あくまでも説明の目的で、グラフは、ノードラベルが種々の原子を表し、エッジラベルが結合の種類を表す化学構造を表すことができ、あるいはグラフは、ソーシャルネットワークを、人々を表すノードと、電子メールの交換、論文の共著、および電話コールなどのタイプの関係を表すエッジとを有するグラフとして表すことができる。いずれにせよ、データを、エッジおよびノードのセットによってグラフとして表すことができ、すでに述べた方法により、グラフは、ＧＭＡＰへと変換される。典型的な入力グラフが、図１７に項目（１）として示されている。
【０１８７】
２．少なくとも、それぞれＴ（「トポロジ」の略）およびＧ（「ジオメトリ」の略）と呼ばれるネットワークについての２つの特性値が計算される。図１９のすべての項目（１）〜（７）に示されるように、各々のグラフはＴおよびＧ値を有する。Ｔはネットワークのトポロジ記述子を表し、Ｇはネットワーク内の要素のデータまたはジオメトリ記述子を表す。トポロジカル記述子Ｔは、データの接続または経路ネットワークについて計算され、Ｇは、重み付きまたは色付きネットワークを使用して計算される。Ｔの関数の例は、これらに限られるわけではないが、Ｈｏｓｏｙａ  Ｉｎｄｅｘ、Ｗｉｅｎｅｒ  Ｉｎｄｅｘ、Ｒａｎｄｉｃ  Ｉｎｄｅｘを含み、Ｇの例は、データに特有であるが、例えば化学に関して結合次数値または原子電気陰性度を含み、一般的なネットワークに関してはノードに位置するノードの重みとしての潜在的な関数およびエッジの重みとしての力を、これらを数値へと規則的に結合させる任意のルールによって含むが、これらに限られるわけではない。例えばウェブグラフにおけるノードの関数の例は、ノードへの有向エッジのｉｎ−ｄｅｇｒｅｅおよびｏｕｔ−ｄｅｇｒｅｅを含み、ノード重みの例は、出力度に対する入力度の比である。
【０１８８】
３．各々の縮約操作について、図１９の項目（２）に示される第１の操作により、操作は幅方向に行われるが、深度方向の縮約も選択することができる。ノードラベルは、ノード（１）の項目（２）へのマージによって示されるように構文ツリーへとマージされ、場合によってはループの保存および考慮ならびに必要な場合の下の構造の回復のために、エッジラベルを保持するループを考慮して繰り返される。ノードの縮約およびマージは、縮約表現ツリーに保持され、図１９の完全なツリーは、縮約表現ツリールールを使用してノード（７）で生成され、ここでは
［ｅ（ｄ）ｆ（ａ（ｂ））（ｃ）］．ｓ［ｏｐ（ｕ．［ｍ］（ｎ））ｑｒ］．ｔ．［（ｑｒ）．ｕ．（ｇ）］
として繰り返される。
【０１８９】
縮約表現ツリーを読み返すことは、簡単であり、履歴を縮約に格納する。例えば、ノード（ｇ）は、「ｑｒ」を含むループ内のエッジ「ｕ」および「ｔ」で生じる。（ｇ）からの順序を逆にすることにより、グラフを復元することができる。さらに、Ｔａｒａｕ［１０］（コンテンツを考慮しないが、トポロジカル構造コードを生成する）の式を修正することにより、ドットを数字で置き換え、表現ツリーをファンクタに変換し、線形記号シーケンスを符号化するための方法に従い、図１９（４）を「ｇｍａｐ１」とラベリングし、先に指定したＤＵＮＲＣアルゴリズムを使用して、項を書き換えることができる。ＤＵＮＲＣ＝４８９５９２８１７０７８４９１０７６８５５０９９９１０８となり、およびダーツラベルのセット＝［ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｍ，ｎ，ｏ，ｐ，ｑ，ｒ，ｓ，ｔ，ｕ］となる。
【０１９０】
４．縮約ルールは、符号化処理の開始時に選択され、図１７を参照して（１）から（７）へと以下のように進行するルールであるため、以下の出力が生成される。
【０１９１】
［ｅ（ｄ）ｆ（ａ（ｂ））（ｃ）］．ｓ［ｏｐ（ｕ．［ｍ］（ｎ））ｑｒ］．ｔ．［（ｑｒ）．ｕ．（ｇ）］これが、
ＤＵＮＲＣ＝４８９５９２８１７０７８４９１０７６８５５０９９９１０８
として符号化され、シンボルを小さな整数へとハッシングし、Ｔａｒａｕ［１０］の対関数の方法を使用することにより、離散カラーネットワークコードが
ＤＣＮＲＣ＝３１６８５５９１３０３４２２７２４４５９４５０１０１０５００
として得られる。
【０１９２】
このツリーは履歴を符号化するので、すべての履歴およびすべての先行コードを削除することができる。「ドット」操作の数に１を加えたものが、縮約レベルの数である。角括弧内の最も深い要素は、最大数の異なるリンクを有する要素である（この例では、これは周囲に｛ｓ，ｔ，ｕ｝としてドットされたエッジを有するラベル「ｍ」である）。したがって、すべてのレベルに関する図１５の項目（１）〜（７）のＴおよびＧの履歴が記録され、ベクトルの最初の要素がゼロ番目の縮約レベルであり、最後がｎ番目の縮約レベルである（それぞれ図１５の項目（１）および項目（７））。
【０１９３】
Ｔ＝（０．５８２３，０．５９８１，０．６７７３，０．７６５９，０．８１１５，０．８９２１，０．８９２１）
Ｇ＝（０．１００１，０．１５０１，０．２５３３，０．３７３８，０．６７３８，０．９７３８，０．９７３８）
標準ブルームフィルタは、０に初期化されたｍビットのビット配列である。また、ｋ個の異なるハッシュ関数が存在しなければならず、各々のハッシュ関数は、いくつかの集合要素を、均一なランダム分布を有するｍ個の配列位置の１つにマップまたはハッシュする。要素を追加するために、それはｋハッシュ関数の各々へと送られ、これは最も単純な場合には単なるしきい値ベクトルであり、ｋビット位置を取得し、値がしきい値ベクトルよりも大きい場合に限り、これらすべての位置のビットを１に設定する。
【０１９４】
２つのしきい値ベクトルＶ（Ｔ）およびＶ（Ｇ）について、説明の目的で、
Ｖ（Ｔ）＝Ｖ（Ｇ）＝（０．５，０．５，０．５，０．５，０．５，０．５，０．５）
である。
【０１９５】
結果として導き出されるＴおよびＧのブルームフィルタは、以下のとおりである。
【０１９６】
Ｔ＝（１，１，１，１，１，１，１）
Ｇ＝（０，０，０，０，１，１，１）
単一のブルームフィルタＦが、以下のとおりのＴおよびＧの連結として、好ましい実施形態である。
【０１９７】
Ｆ＝（１，１，１，１，１，１，１，０，０，０，０，１，１，１）
図１９のネットワークのコグニティブシグネチャ（４）データ構造は、ＴおよびＧについて１つの特性関数しか存在しないので、最小のシグネチャであり、記号ストアＳ、ブルームフィルタＦ、およびＧＵＩＤとともに、両方について１ベクトルのシーケンスをもたらす（好ましい実施形態において、ＴおよびＧはそれぞれのｋおよびｍマトリクスならびにノード内容特性関数についてのｋ−ベクトルおよびｍ−ベクトルのシーケンスであると考えられる）。
【０１９８】
ＧＵＩＤ＝ｇｍａｐ１；
Ｔ＝（（０．５８２３）０，（０．５９８１）１，（０．６７７３）２，（０．７６５９）３，（０．８１１５）４，（０．８９２１）５，（０．８９２１）６）
Ｇ＝（（０．１００１）０，（０．１５０１）１，（０．２５３３）２，（０．３７３８）３，（０．６７３８）４，（０．９７３８）５，（０．９７３８）６）
Ｆ＝（１，１，１，１，１，１，１，０，０，０，０，１，１，１）
Ｓ＝［ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｍ，ｎ，ｏ，ｐ，ｑ，ｒ，ｓ，ｔ，ｕ］；
ＤＵＮＲＣ＝４８９５９２８１７０７８４９１０７６８５５０９９９１０８
ＤＣＮＲＣ＝３１６８５５９１３０３４２２７２４４５９４５０１０１０５００
ブルームフィルタは、偽陽性を生じ得るが、他の試験は、図１６に示されるように、偽陽性を排除する。ネットワークベクトル空間は、ｋ特性関数のベクトルならびにネットワークのｍトポロジ関数のｍベクトルで構成されるｋベクトル空間の階層からなる。所与のメンバーネットワークは、縮約レベル（すなわち、反復）数に基づく異なるレベルにおいてこれらのベクトル空間の１つ以上へとマッピングする。マッピングされる構造の複雑さに応じて、ネットワークは、そのサイズおよび選択された特定の縮約方法に応じて、空間のすべてのレベルに拡張されても、拡張されなくてもよい。例えば、アルファ−ゼロインボリュ−ションが「Ｘ  ｉｓ−ａ  Ｙ」の「ｉｓ−ａ」などのオントロジに共通なラベルが埋め込まれたエッジである場合、「ｉｓ−ａ」とラベリングされたエッジのみの縮約は、ラベルが無視され、すべてのエッジがラベリングに関係なく縮約させられる場合と比べ、異なるコグニティブシグネチャをもたらす。
【０１９９】
ここで図２０を参照すると、図２０の凡例と一致する主要なステップ（１）〜（１１）で番号付けされた以下のアルゴリズムが提示される。
【０２００】
ネットワークをコンパイルして格納するアルゴリズム：
（１）生の入力データが取り込まれる。
【０２０１】
（２）入力ネットワークをコグニティブシグネチャデータ構造に変換する。
【０２０２】
（３）入力ネットワークについて以下のステップを使用してネットワークのシンボリックコンテンツを格納する。
【０２０３】
１．入力サンプルネットワークＧｉｎを読み込む。
【０２０４】
２．ノードタイプおよびエッジタイプの組によって次元のセットを識別することにより、空間Ｖを作成する。
【０２０５】
３．計算するインデックスのセット（すなわち、例えば文献［２］を用いたマトリクス特性ベクトルのサイズ）を選択することによって識別された次元に基づいてＧｉｎを記述するベクトルを生成する。以下の基準に従って、次元の集合を既存のベクトル空間Ｖｊに追加し、Ｖｊがレベル１に存在しない場合には生成する。
【０２０６】
ｉ．ＧｉｎがＶｊにおいてまだ利用可能でなく、
ｉｉ．ＧｉｎおよびＶｊにおいて識別された次元間の重なりが最大である。
【０２０７】
４．次元をそれらのコンポーネントの減少するｋ順序ならびにそれらの出現および重み付け（ノードの重み付け関数が選択されている場合）の頻度によってＧｉｎに並べる。
【０２０８】
５．複数のマップを生成するためにダーツを追加し、縫い合わせ、あるいはアンソーイングすることによってｍ出力ネットワークＧｏｕｔのセットを生成するためにこれらの異なる次元によってＧｉｎを区画する。
【０２０９】
６．次に、Ｇｉｎから濃度カウントのセットを生成する。Ｇｉｎを記述するノードタイプおよびエッジタイプの組み合わせが、これを実行する。ひとたび次元のセットが導出されると、異なるエッジ出現の数を次元に投影することによってこれらの次元に沿ってＧｉｎを投影する。エッジが数値特性（重みおよび多重度）を有する場合は、それは重みによって乗算されたエッジの発生回数のカウントとして使用される。
【０２１０】
７．区画されたネットワークＧｏｕｔ〜Ｇｏｕｔの各々を入力ネットワークＧｏｕｔ’およびＧｏｕｔ’’およびＧｏｕｔ’’’．．．などとして使用して、レベル１＋１についてステップ１から繰り返す。
【０２１１】
８．ステップ１から７が行われた（さらなる入力がない）とき、完成した初期化されたデータベースを返す。
【０２１２】
メンバーネットワークは、データベースに追加（または、削除）される。新しいメンバーネットワークを追加する場合は、任意の他のネットワークと同じ構文解析技術を使用して処理される必要がある。ひとたびネットワークが構文解析されると、ベクトル空間のいずれにも存在しない発見された新たな特徴は、類似物の検索の目的において黙って無視される。学習および獲得段階において選択されたサンプルは、文脈に関してのみ重要であるが、トポロジカルな類似物に関しては重要でない。それは、インデキシングされるべきすべてのトポロジ的特徴の少なくとも１回の出現を含まなければならない。
【０２１３】
（４）ネットワークには、強力な乱数の発生を含み得る外部サービスまたはプロセスを使用してグローバル固有アイデンティティ指定（ＧＵＩＤ）コードが与えられる。ＧＵＩＤは、固有でなければならず、すでに処理されて格納されている他のいかなるメンバーネットワークとも衝突してはならない。したがって、ネットワークは、次のように一般化組み合わせマップへと変換される。
【０２１４】
ａ．各々のエッジについて、整数を順番に使用して、ダーツのペアを生成し、あるいは
ｂ．各々の有向エッジについて、時計回りの順序で、エッジが頂点のｏｕｔ−ｄｅｇｒｅｅである場合には出ていく半分に正の符号を持つダーツを割り当て、無向エッジを表すダーツのペアへの整数の次のより高いペアとして到来するエッジに負のダーツを割り当てる。各々のノードは、その周囲のすべてのダーツの回転（すなわち、軌道）として記述される。したがって、マップの軌道指定は、整数または辞書順のいずれかにおけるマップ内のすべてのノードの回転のシーケンスである。出力はＧＭＡＰである。
【０２１５】
（５）ＧＭＡＰは、ＧＭＡＰ（０）マトリクスと呼ばれるコネクティビティマトリクスまたはＰａｔｈ  Ｇｒａｐｈ  Ｍａｔｒｉｘに変換される。
【０２１６】
（６）離散非カラーネットワーク表現コード（ＤＵＮＲＣ）が計算され、離散カラーネットワーク表現コード（ＤＣＮＲＣ）が生成される。
【０２１７】
（７）特性関数のベクトルが、ＧＭＡＰ（０）マトリクスについて計算される。
【０２１８】
（８）次に、縮約ルールを適用してＧＭＡＰ（０）を縮約させ、１縮約レベルだけ縮約した新しいＧＭＡＰ（１）を生成する。
【０２１９】
（９）コグニティブシグネチャが、ＧＭＡＰ（０）について収集および格納される。
【０２２０】
（１０）ＧＭＡＰ（１）が、さらなる縮約が可能であるか否かを判断するためにテストされ、可能である場合には、ステップ（５）〜（７）が、固定点に達し、さらなる縮約が不可能になるまで繰り返される。
【０２２１】
（１１）コグニティブシグネチャベクトルは、マルチバンテージポイントツリーに格納され、ＧＭＡＰ（０）のＧＵＩＤならびにすべての離散コードおよびブルームフィルタは、縮約のレベルごとに１つずつ、ＲＤＢＭＳテーブルに格納される。処理すべきさらなるグラフが存在せず、あるいは縮約によって固定点に到達すると、関係データベースが結果として返される。
【０２２２】
図２０（１１）の各要素について、以下のインデックスが生成される。
【０２２３】
（ａ）特定のＴおよびＧのペアに一致するネットワークのＧＵＩＤ値を格納する逆インデックスを使用するコグニティブシグネチャのＴおよびＧベクトルからなる特性関数ベクトルのデータベースのインデックス：マルチバンテージポイントツリーを使用してネットワークの埋め込みを検索する。
【０２２４】
（ｂ）縮約レベルのデータベースの階層内の各縮約グラフについて生成されたすべてのコグニティブシグネチャのコグニティブシグネチャツリー（ＣＳＴ）：ＣＳＴは、ネットワークをそのＧＵＩＤ、ブルームフィルタ、または名前／ラベルの組み合わせ、あるいは任意の縮約レベルにおける特性ベクトルまたは表現ツリーのいずれかに基づいて素早く検索するために使用される。ネットワーク自体は、１つ以上のデータファイルに格納され、データファイル内のネットワークの数は、「ファイルごとのネットワーク」（ｇｐｆ）と呼ばれる設定可能なパラメータによって決定される。ＣＳＴは、これらのデータファイルへとプライマリインデックスを形成し、データベースへと縮約させられたすべてのネットワークをインデキシングする。ＣＳＴは、種々の抽象化レベルにおけるネットワークセットの素早い検索を可能にする。
【０２２５】
（ｃ）セカンダリネットワークインデックス：これは、ＧＵＩＤＳに対するコグニティブシグネチャのインデックスであり、シグネチャ自体の特性にも可能である。
【０２２６】
（ｄ）ハッシュコード（ＤＵＮＣＲおよびＤＣＮＣＲコード）の使用に基づく構造インデックス。
【０２２７】
（ｅ）ＧＭＡＰとしてデータベースに格納された元のネットワーク要素に対するＧＵＩＤＳのセカンダリインデックス。
【０２２８】
したがって、各々のネットワークに対してＧＵＩＤが存在し、各々のＧＵＩＤに対してマルチバンテージポイントツリーにおける関連のマトリクス特性ベクトルが存在する。ブルームフィルタを使用して、特性がデータベースに存在する場合、埋め込みは、データベース内の候補の種類および出現回数を有する。次に、ＲＤＢＭＳが、データベースに存在するブルームフィルタによって選択されたすべての値のエントリを探すために検索される。
【０２２９】
所与のレベルＬにおいてＧＭＡＰを格納するためのアルゴリズムは、以下のとおりである。
【０２３０】
アルゴリズムストア
１．ＧＭＡＰ、Ｋ、およびレベルＬを入力。ＧＭＡＰ  Ｍをスキャンし、同じＫにおけるすべてのＫ−セルを識別する。ＧＵＩＤおよびすべてのＫ−セルコード（縮約表現コード）を置換の順序で格納する。このようにして見つけられたすべてのそのようなコード（すなわち、Ｋ−セル）のセットをｄｉｍｓ（Ｇ）とする。
【０２３１】
２．任意のＫ−次元について、ｐｒｏｊ（Ｍ，Ｋ−Ｃｅｌｌ−Ｅｎｃｏｄｉｎｇ）は、発見されたそのようなコード化された下位構造の数である。
【０２３２】
３．ＳＬをレベルＬのＲＤＢＭＳのベクトル空間とする。ＧＭＡＰ  ＭがレベルＬに挿入される最初のグラフである場合、
ＳＬ＝（｛｝．｛｝）。次のようにＧＭＡＰ  ＭをＳＬへと挿入する。
【０２３３】
ａ）ｄｉｍｓ（Ｍ）をｄｉｍｓ（ＳＬ）へとマージする。
【０２３４】
ｄｉｍｓ（ＳＬ）＝ｄｉｍｓ（ＳＬ）  ｕｎｉｏｎ  ｗｉｔｈ  ｄｉｍｓ（Ｍ）
ｂ）ＳＬのＴおよびＧベクトルの組にＭを加える。
【０２３５】
ｖｅｃ（Ｔ，ＳＬ）＝ｖｅｃ（Ｔ，ＳＬ）ｕｎｉｏｎ  ｗｉｔｈ  ｖｅｃ（Ｔ，Ｍ）、および
ｖｅｃ（Ｇ，ＳＬ）＝ｖｅｃ（Ｇ，ＳＬ）ｕｎｉｏｎ  ｗｉｔｈ  ｖｅｃ（Ｇ，Ｍ）
（ｄｉｍｓ（ＳＬ）の任意のｄおよびｄｉｍｓ（Ｍ）にないｄについて、ｐｒｏｊ（Ｍ、ｄ）が０と定義されることに注意されたい）。
【０２３６】
４．停止。
【０２３７】
伝統的なＲＤＢＭＳにおけるコグニティブシグネチャの好ましい実施形態は、「スタースキーマ」である。スタースキーマは、中央テーブルと、１つ以上のリンクされた特性テーブルとで構成される。本発明では、スタースキーマモデルを変更し、（ｄ１，ｄ２，．．．，ｄｎ，ｖ）という形式のファクト表のキーおよびベクトルを使用し、ここで、ｄ１，ｄ２，．．．，ｄｎは次元インデックス（すなわち、ベクトル空間を含むノード）への外部キー（ダーツ）であり、ｖはマルチバンテージポイントツリーとして見られるベクトル空間データベースのベクトルまたはメンバーデータ要素である。
【０２３８】
我々のスキーマの基礎は、メモリ内のファクトテーブルから始まるが、その構造は、ディメンションテーブルからのディメンションリンクが基本ファクトを指し、反対を指さないため、ＳＱＬに格納される通常のファクトテーブルの構造とは異なる。ディメンションテーブルのセットは、空間の異なるレイヤを表す等価クラスに分割される。
【０２３９】
ｂａｓｉｓ（ｇｕｉｄ，ｍｅｍｂｅｒ＿ｎｅｔｗｏｒｋ）．
ここで、ｇｕｉｄは、各メンバーネットワークに割り当てられたグローバルユニバーサル固有指定ＩＤであり、ｍｅｍｂｅｒ＿ｎｅｔｗｏｒｋは、メンバーネットワーク構造ｃｏｎｔａｉｎｅｒ（ＧＭＡＰのノード）へのＤａｒｔです。各々のディメンションインデックスの構造は、
ｄｉｍｅｎｓｉｏｎ＿ｉｎｄｅｘ（ｐｒｏｊ（ｖｅｃｔｏｒ），ｎｅｔｗｏｒｋ＿ｉｎｄｅｘ）
という形式の述語である。
【０２４０】
ここで、ｐｒｏｊは、点を含む領域を定義するバンテージポイントである固定ベクトルをインデキシングする投影インデックス値である。ｎｅｔｗｏｒｋ＿ｉｎｄｅｘは、所与の次元の空間への投影がベクトルのテーブルに与えられるメンバーネットワークガイドのソートされたテーブルである。したがって、我々は、バンテージポイントに関するベクトルテーブルへのインデックスを有する。
【０２４１】
レベル間のナビゲーションは、
Ｈｉｅｒａｒｃｈｙ（Ｌｅｖｅｌｓ（ＮｅｘｔＬｅｖｅｌ（“ｉｎｔｅｇｅｒ”），ＰｒｅｖｉｏｕｓＬｅｖｅｌ（“ｉｎｔｅｇｅｒ｜ｖｏｉｄ”）））
という形式を（述語論理表記法で）使用する。
【０２４２】
前のレベルがボイドである場合、我々は基礎レベルにある。
【０２４３】
各々の縮約レベルは、それぞれ独自のベクトル空間を含み、各々の縮約レベルは、ＲＤＢＭＳデータベース内のテーブルとしてモデル化される。テーブルの列の名前は、ベクトル空間（テーブル自体）のネットワーク記述子ｄｉ（ｄｌ，ｄ２．．．．ｄｎ）を使用するＧの投影値である。各々のテーブルの最後の列は、ネットワークの構造および説明を保持するファイル名である。初期化段階において、ＳＱＬで新しいデータベース名を作成すると、コグニティブメモリが初期化される。また、初期化は、各々のレベルにおいて、幾何学的マトリクス特性関数およびネットワークを表すマトリクスのトポロジカルインデックス上に作成されたベクトルのトポロジ構造のすべてのベクトル空間の集合に基づいて、意味的特性の特性空間に対応する一組のテーブルを作成する。ひとたびこれらのベクトル空間のそれぞれの次元が知れると、それらは常に選択されたマトリクス特性関数の最大ｋ−数に等しいが、対応する列が、次元によってソートされたテーブルを有するようにＳＱＬ  ＣＲＥＡＴＥコマンドを発行することによってこれらのテーブルに生成される。新しい記述子（すなわち、特性関数）が選択された場合、それは単に列のリストに追加される。
【０２４４】
スキーマネットワーク内のノードによって参照されるネットワークは、さらにスキーマネットワーク自体であり得る。これは、任意のレベルへと続くことができ、実際に、循環および自己参照も許される。スキーマは、自身をノードの１つとして参照することができる。メンバーネットワークＧｉがスキーマネットワークＨ内のノードになるとき、Ｇｉのネットワーク特性は、Ｈ内のＧｉを表すどのノードのノード特性にもなる。
【０２４５】
すべてのメンバーネットワークは、空ベクトルネットワークと呼ばれるスキーマに属する。空のベクトルは、データベース内のすべてのメンバーネットワーク（自身を含む）を表すノードのみを含む。空のベクトルにエッジを追加して、メンバーネットワークを表す要素間の関係を確立することができる。
【０２４６】
ここで、クエリグラフとコグニティブメモリ内のグラフとの間の部分的、類似、および完全一致を生成するクエリプロセスを詳細に示す図２１を参照すると、以下のクエリ処理ステップが与えられる。
【０２４７】
（１）データクエリが入力され、このクエリが、縮約レベルについてベクトルおよび離散コードのセットならびにブルームフィルタによって与えられるコグニティブシグネチャへと符号化される。クエリ処理は、クエリグラフおよびそのＱ−ｍｅｄｏｉｄｓへの変換、ならびに頂点間のゾーンまでの距離の使用による暗黙の距離関係を得るための計算で始まり、一般に、クエリ処理は、ひとたびグラフ候補が主アルゴリズムによって返されたならば候補頂点マッチを生成することを含む。頂点マッチングは、ブルームフィルタにおけるＱＨａｓｈサマリの使用によって加速され、当業者にとっての標準的な方法を、偽陽性を取り除くべく候補マッチを厳密に検証するために使用することができる。
【０２４８】
（２）ローカルブルームフィルタインデックスを構築するためにＱ−Ｍｅｄｏｉｄｓを構築する方法（バーチャルパーティクルモデル、Ｑハッシング関数、およびネットワーク構造インデックスを使用する）は、先行技術において下位構造の探索の有効性を可能にしていると考えられるアドホックユーザ定義しきい値の方法を置き換える。
【０２４９】
（３）コグニティブシグネチャが、図１６の項目（１）〜（１０）に示されるように入力データから生成される。
【０２５０】
（４）ブルームフィルタが、ユーザしきい値（２）およびデータコグニティブシグネチャ（３）から抽出される。
【０２５１】
（５）ブルームフィルタは、最初に、当業者にとって公知の通常の技術を使用して、データベース内の格納されたセットに対してチェックされる。
【０２５２】
（６）一致が存在しない場合、早期拒絶がもたらされる。しかしながら、偽陽性か真実の一致かにかかわらず、次のステップが続く。
【０２５３】
（７）ＴおよびＧベクトル要素で構成されるマトリクス特性ベクトルが、各レベルのコグニティブシグネチャから抽出される。
【０２５４】
（８）ベクトルが、ｋ最近傍アルゴリズムを使用して、マルチバンテージポイントツリーまたは他の同等の空間データ記憶構造において検索される。
【０２５５】
（９）一体化し、すなわちｋ−最近傍の一致が存在するレベルの各々について、カウントが生成される。
【０２５６】
（１０）すべてのレベルが一致する場合、または、
（１１）いかなるレベルも一致しない場合、
（１２）一致なしが返され、そうでなければ、
（１３）ＧＵＩＤＳの候補セットが返され、
（１４）マッチング表現ツリーが、Ｌｅｖｅｎｓｔｅｉｎ距離または文字列間の任意の他の適切な距離指標によって表現ツリーマッチが与えられるしきい値内で選択される。
【０２５７】
（１５）各々の最も近い表現ツリーマッチについて、ランク付けされた最も近い離散符号化、ＤＵＮＲＣまたはＤＣＮＲＣのいずれか、または好ましくは両方がマッチされる。
【０２５８】
（１６）ステップ（１４）および（１５）の間のマッチからの候補が存在しない場合、  （１７）一致なしが返され、そうでない場合、
（１８）完全一致が存在するならば、
（１９）完全一致が返され、そうでなければ、
（２０）候補が、
（２１）（ユーザによる評価のために）部分的または類似の一致として返される。
【０２５９】
コグニティブシグネチャは、データベースに格納され、クエリ入力グラフのシグネチャと比較される。最近傍マッチを、ｋ−レベルへと縮約させられたデータベース時間内にｎ個のメンバーネットワークについてｋ（ｎ）ｌｏｇ（ｎ）において行うことができる。入力の複雑さは、実際には入力のサイズのｌｏｇ２である。
【０２６０】
コグニティブメモリにおけるクエリマッチングのためのアルゴリズム：
クエリによって返された各々のメンバーネットワークに、図１（１０）によってランクが与えられる。ランクは、結果が正解である可能性を示す。サブネットワーククエリについて、ランク付けは、メンバーネットワークが所与のクエリにどの程度広範囲に一致しているかに基づき、すなわち換言すると、マッチが許容範囲の所与のしきい値の範囲内のあらゆるレベルで発生したことに基づく。
【０２６１】
より高い文脈上の抽象化レベルにおいてマップするメンバーネットワークには、より低い抽象化レベルでマッチするメンバーネットワークよりも高いランク付けが与えられ、なぜならば、より高いレベルはより一般化されており、より特定のより低いレベルにおける包括的なマッチまでの意味的距離がより小さいからである。より低いランク付けは、より長い意味的距離を反映する。同様に、任意の抽象化レベルにおいて多くのベクトル空間にマッチするメンバーネットワークには、少数のベクトル空間でしかマップしないメンバーネットワークよりも高いランク付けが与えられる。
【０２６２】
【数１７】
2020119591.tif 000021
レベルの数はｉであり、ｆｉはマッチが存在するレベルにおけるマッチの数である（すなわち、最近傍セット）。
【０２６３】
１つ以上のベクトル空間内の領域へのクエリのマッピングは、クエリの解決を実行する。クエリ結果は、すべてのベクトル空間内のクエリ領域にあるすべての点のランク付けされた和集合によって計算される。したがって、クエリの解決および検索は、クエリの領域へのマッピングおよびクエリ結果のランク付けという２つの問題を含む。領域の生成は、探索の半径という概念に基づく。探索の半径は、任意の次元に沿った領域の幅を定義するパラメータである。このタイプの探索は、おおよそのマッチを生む。
【０２６４】
類似探索は、ネットワークをパラメータとして受け取り、「トポロジ的に類似した」ネットワークのセットを返す。ネットワーク間のトポロジカル距離は意味的距離であり、トポロジカルおよび意味的インデックスに関して或るネットワークと別のネットワークとの間のノード／エッジ差の数を指す。サポートされているこの種のクエリは、コグニティブメモリのアナログクエリと呼ばれる。
【０２６５】
サブネットワーククエリは、クエリネットワークを入力として受け取り、クエリネットワークをサブネットワークのうちの１つとして有する可能性があるすべてのネットワークを返す。任意の所与のレベルにおける所与のｇｕｉｄのすべての特性が、そのレベルにおける空間内のネットワークの位置を表すベクトルとして取り扱われる。クエリネットワークが同様に投影されるとき、クエリ結果は、クエリネットワークベクトルとメンバーネットワークベクトルとの間の距離に基づくと考えられる。
【０２６６】
ネットワークのデータベース内の共通サブネットワークを採掘するために、探索前提は、データベース内のすべてのネットワークが同形であることであり、そのような主張に反論するローカルに接続されたローカルネットワークの刈り込みを漸進的に開始する。次いで、プロセスは、ローカルのネットワークのうちの最大共通サブネットワークに収束する。したがって、探索はいかなる所与のレベルにおいてもグローバルビューを「参照」しないため、インデキシングが複数のレベルでプロセスを繰り返す機能である（検索の反復的な深化）。
【０２６７】
共通サブネットワークを探索するためのアルゴリズム：
クエリネットワークＱおよびコグニティブメモリデータベースＳが与えられると、類似探索は、次のように進行する。
【０２６８】
１．ＣＳＴツリーのルートの後の第１のレベルとしてレベルｌ＝０から開始する。
【０２６９】
２．ＷＳをデータベースＳに存在するすべてのｇｕｉｄの集合とする。
【０２７０】
３．Ｑｌを、すべての縮約およびレベルｌでのクエリネットワークにおけるそれらの対応する出現回数（すなわち、クエリネットワークのベクトル）の集合とする。
【０２７１】
４．Ｌｌを、レベルｌのＣＳＴツリー内のすべての縮約ベクトルの集合とする。
【０２７２】
５．ＱｌをＬｌと比較し、ＳにおけるウィンドウパラメータＲ  ｒａｄｉｕｓに基づいてクエリベクトルに「充分に近い」すべてのｇｕｉｄ  ＷＬの集合を取得する。
【０２７３】
６．レベルｌでのクエリ結果の集合として、Ｒｌ＝Ｗ  Ｓｎ  ＷＬを計算する。
【０２７４】
７．レベルｌ＋１におけるクエリ結果はレベルｌにおけるクエリ結果に含まれなければならないため、ＲｌにないすべてのｇｕｉｄをＷＳから除去する。すなわち、ＷＳ＝Ｒｌに交差したＷＳである。
【０２７５】
８．Ｌｌのいずれかの区分に新しいＷｌからのｇｕｉｄが含まれていない場合、ＣＳＴツリーの対応するノードを未使用としてマークする。このノードの下方のサブツリー全体は、次のレベルの比較時に無視することが可能である。
【０２７６】
９．所望の数の洗練が行われるまで、ｌ＝ｌ＋１を設定し、ステップ２に戻る。
【０２７７】
「充分に近い」関数は、各レベルにおいてクエリネットワークベクトルの周りの半径Ｓの球を考慮し、この半径内にあるすべてのベクトルを追加することによって計算される。
部分構造のクエリの場合、「充分に近い」関数は、クエリベクトルの上方にあるすべてのベクトルの集合を返す関数で置き換えられる。
【０２７８】
トポロジカルクエリは、ａｎａｌｏｇ（）、ｃｏｎｔａｉｎｓ（）、およびｍｃｇ（）などの関数への入力パラメータとしてネットワーク参照（ＧＵＩＤ）を提供することによって実行可能である。ここで、ｍｃｇは、第３のパラメータにおけるクエリネットワークとネットワーク参照との間の「最大共通サブネットワーク」を表す。上記のすべてのトポロジカルなクエリ構造は、２つの形式で現れる。
【０２７９】
１．単一ステップトポロジカルクエリ。トポロジカル探索が、以前の検索よりも１レベル上について実行され、誤った一致がある場合にはそれを削除するためにＤＵＮＣＲが使用される。
【０２８０】
２．マルチステップトポロジカルクエリ。トポロジカル探索が、削除のためにＤＵＮＣＲを使用して事前指定された数のレベルについて実行される。
【０２８１】
このように、以上の検討は、あくまでも本発明の典型的な実施形態の開示および説明にすぎない。当業者であれば理解できるとおり、本発明は、特性またはトポロジに関するネットワーク上のハッシュコードおよび／または機能との縮約ルールの結合および組み合わせにおいて、本発明の技術的思想または基本的特徴から離れることなく、他の具体的形態にて具現化可能である。したがって、本発明の開示は、例示であるように意図されており、本発明の範囲および他の請求を限定するものではない。本明細書における教示の容易に認識可能な変種を含む本開示は、本発明の主題が公衆に捧げられることがないように、上述の特許請求の範囲の用語の範囲を一部分において定義する。
【０２８２】
本実施形態は、量子コンピューティングの特徴または態様を包含および実行することができ、量子コンピュータ上で物理的に実行されても、量子コンピュータまたは量子コンピューティングの態様のエミュレーションを介して仮想的に実行されてもよい。スーパーコンピュータまたはコンピューティングあるいは任意の他の同様の技術を、本明細書において説明した機能を実行するために使用することができる。
【０２８３】
上述の種々の特徴は、コンピュータシステム（または、プログラマブルロジック）などのコンピューティングデバイスによって実装されてもよい。回路を、回路の処理を改善し、人間では不可能であり、あるいは本実施形態の特徴を欠いた汎用コンピュータでも不可能であるやり方でデータを処理することを可能にする上述の機能および特徴を実現するようにとくに設計またはプログラムすることができる。本発明の特徴は、何らかの形のコンピュータプロセッサを使用して実施することができる。当業者であれば分かるように、コンピュータプロセッサは、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、または他のコンプレックスプログラマブル論理デバイス（ＣＰＬＤ）としてディスクリート論理ゲートとして実装することができる。ＦＰＧＡまたはＣＰＬＤの実装は、ＶＨＤＬ、Ｖｅｒｉｌｏｇ、またはその他のハードウェア記述言語でコード化することができ、コードは、ＦＰＧＡまたはＣＰＬＤ内の電子メモリに直接格納されても、別の電子メモリとして格納されてもよい。さらに、電子メモリは、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、またはＦＬＡＳＨメモリなど、不揮発性であってよい。電子メモリは、スタティックまたはダイナミックＲＡＭなど、揮発性であってもよく、電子メモリならびにＦＰＧＡまたはＣＰＬＤと電子メモリとの間の相互作用を管理するために、マイクロコントローラまたはマイクロプロセッサなどのプロセッサが設けられてよい。
【０２８４】
あるいは、コンピュータプロセッサは、本明細書に記載の機能を実行するコンピュータ可読命令のセットを含むコンピュータプログラムを実行することができ、プログラムは、上記の非一時的な電子メモリならびに／あるいはハードディスクドライブ、ＣＤ、ＤＶＤ、ＦＬＡＳＨドライブ、または任意の他の公知の記憶媒体のいずれかに格納されてよい。
さらに、コンピュータ可読命令は、米国Ｉｎｔｅｌ社のゼノン（Ｘｅｎｏｎ）プロセッサまたは米国ＡＭＤ社のオプテロン（Ｏｐｔｅｒｏｎ）プロセッサなどのプロセッサならびにＭｉｃｒｏｓｏｆｔ  ＶＩＳＴＡ、ＵＮＩＸ（登録商標）、Ｓｏｌａｒｉｓ、ＬＩＮＵＸ、Ａｐｐｌｅ、ＭＡＣ−ＯＳＸ、および当業者にとって公知の他のオペレーティングシステムなどのオペレーティングシステムと連携して実行されるユーティリティアプリケーション、バックグラウンドデーモン、またはオペレーティングシステムのコンポーネント、あるいはこれらの組み合わせとして提供され得る。
【０２８５】
さらに、本発明は、コンピュータベースのシステム１０００を使用して実施することができる。コンピュータ１０００は、情報を通信するためのバスＢまたは他の通信機構、ならびに情報を処理するためにバスＢに接続されたプロセッサ／ＣＰＵ１００４を含む。さらに、コンピュータ１０００は、情報およびプロセッサ／ＣＰＵ１００４によって実行される命令を記憶するためにバスＢに接続されたランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置（例えば、ダイナミックＲＡＭ（ＤＲＡＭ）、スタティックＲＡＭ（ＳＲＡＭ）、およびシンクロナスＤＲＡＭ（ＳＤＲＡＭ））などのメインメモリ／メモリユニット１００３を備える。加えて、メモリユニット１００３を、ＣＰＵ１００４による命令の実行の最中に一時変数または他の中間情報を記憶するために使用することができる。
また、コンピュータ１０００は、ＣＰＵ１００４のための静的な情報および命令を記憶するためにバスＢに接続された読み出し専用メモリ（ＲＯＭ）または他の静的記憶装置（例えば、プログラマブルＲＯＭ（ＰＲＯＭ）、消去可能ＰＲＯＭ（ＥＰＲＯＭ）、および電気的に消去可能なＰＲＯＭ（ＥＥＰＲＯＭ））をさらに備えることができる。
【０２８６】
さらに、コンピュータ１０００は、大容量記憶装置１００２および駆動装置１００６（例えば、フロッピーディスクドライブ、読み出し専用コンパクトディスクドライブ、読み／書きコンパクトディスクドライブ、コンパクトディスクジュークボックス、テープドライブ、およびリムーバブル光磁気ドライブ）などの情報および命令を格納するための１つ以上の記憶装置を制御するためのバスＢへと接続されたディスクコントローラを含むことができる。ストレージデバイスを、適切なデバイスインターフェース（例えば、スモールコンピュータシステムインターフェース（ＳＣＳＩ）、統合デバイスエレクトロニクス（ＩＤＥ）、拡張ＩＤＥ（Ｅ−ＩＤＥ）、ダイレクトメモリアクセス（ＤＭＡ）、またはｕｌｔｒａ−ＤＭＡなど）を使用してコンピュータ１０００に追加することができる。
【０２８７】
さらに、コンピュータ１０００は、専用の論理デバイス（例えば、特定用途向け集積回路（ＡＳＩＣ））あるいは設定可能な論理デバイス（例えば、シンプルプログラマブル論理デバイス（ＳＰＬＤ）、コンプレックスプログラマブル論理デバイス（ＣＰＬＤ）、およびフィールドプログラマブルゲートアレイ（ＦＰＧＡ））を含むことができる。
【０２８８】
また、コンピュータ１０００は、バスＢへと接続され、コンピュータユーザに情報を表示するための陰極線管（ＣＲＴ）などの表示装置を制御するディスプレイコントローラを含むことができる。コンピュータシステムは、コンピュータユーザと対話し、プロセッサに情報を提供するために、キーボードおよびポインティングデバイスなどの入力デバイスを含む。ポインティングデバイスは、例えば、方向情報およびコマンド選択をプロセッサに伝達し、表示装置上のカーソルの移動を制御するためのマウス、トラックボール、またはポインティングスティックであってよい。さらに、プリンタは、コンピュータシステムによって格納および／または生成されたデータの印刷リストをもたらすことができる。
【０２８９】
コンピュータ１０００は、メモリユニット１００３などのメモリに含まれる１つ以上の命令の１つ以上のシーケンスのＣＰＵ１００４による実行に応答して本発明の処理ステップの少なくとも一部を実行する。そのような命令は、大容量記憶装置１００２または取り外し可能媒体１００１などの別のコンピュータ可読媒体からメモリユニットに読み込まれてもよい。マルチプロセッシング構成の１つ以上のプロセッサを使用して、メモリユニット１００３に含まれる命令のシーケンスを実行することもできる。別の実施形態においては、ソフトウェア命令の代わりに、またはソフトウェア命令と組み合わせて、ハードワイヤード回路を使用することができる。したがって、実施形態は、ハードウェア回路およびソフトウェアの特定の組み合わせに限定されない。
【０２９０】
上述したように、コンピュータ１０００は、本発明の教示に従ってプログラムされた命令を保持し、本明細書に記載のデータ構造、テーブル、レコード、または他のデータを格納するための少なくとも１つのコンピュータ可読媒体１００１またはメモリを含む。コンピュータ可読媒体の例は、コンパクトディスク、ハードディスク、フロッピーディスク、テープ、光磁気ディスク、ＰＲＯＭ（ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュＥＰＲＯＭ）、ＤＲＡＭ、ＳＲＡＭ、ＳＤＲＡＭ、または任意の他の磁気媒体、コンパクトディスク（例えば、ＣＤ−ＲＯＭ）、あるいはコンピュータにとって読み取り可能な任意の他の媒体である。
【０２９１】
本発明は、本発明を実施するために１つ以上のデバイスを駆動すべく主処理ユニットを制御するため、および主処理ユニットにとって人間のユーザとの対話を可能にするためのコンピュータ可読媒体のいずれか１つまたは組み合わせに格納されたソフトウェアを含む。そのようなソフトウェアは、これらに限られるわけではないが、デバイスドライバ、オペレーティングシステム、開発ツール、およびアプリケーションソフトウェアを含む。そのようなコンピュータ可読媒体は、本発明の実施において実行される処理の全部または一部（処理が分散されている場合）を実行するための本発明のコンピュータプログラム製品をさらに含む。
【０２９２】
本発明の媒体上のコンピュータコード要素は、これらに限られるわけではないが、スクリプト、解釈可能プログラム、ダイナミックリンクライブラリ（ＤＬＬ）、Ｊａｖａ（登録商標）クラス、および完全な実行可能プログラムを含む任意の解釈可能または実行可能コード機構であってよい。さらに、本発明の処理の一部は、より良い性能、信頼性、および／またはコストのために分散されてもよい。
【０２９３】
本明細書において使用されるとき、「コンピュータ可読媒体」という用語は、実行のためのＣＰＵ１００４への命令の提供に関与する任意の媒体を指す。コンピュータ可読媒体は、これらに限られるわけではないが不揮発性媒体および揮発性媒体など、多くの形態を取ることができる。不揮発性媒体は、例えば、大容量記憶装置１００２または取り外し可能媒体１００１など、光学ディスク、磁気ディスク、および光磁気ディスクを含む。揮発性媒体は、メモリユニット１００３などのダイナミックメモリを含む。
【０２９４】
さまざまな形態のコンピュータ可読媒体が、実行のためのＣＰＵ１００４への１つ以上の命令の１つ以上のシーケンスの実行に関与することができる。例えば、命令は、当初は遠隔コンピュータの磁気ディスク上に担持されてよい。バスＢへと接続された入力が、データを受信し、データをバスＢ上に置くことができる。バスＢは、メモリユニット１００３へとデータを運び、そこからＣＰＵ１００４が命令を取り出して実行する。メモリユニット１００３によって受信された命令は、随意により、ＣＰＵ１００４による実行の前または後のいずれかにおいて、大容量記憶装置１００２に格納されてよい。
【０２９５】
さらに、コンピュータ１０００は、バスＢに接続された通信インターフェース１００５を含む。通信インターフェース１００４は、例えばローカルエリアネットワーク（ＬＡＮ）またはインターネットなどの別の通信ネットワークに接続されたネットワークに結合する双方向データ通信を提供する。例えば、通信インターフェース１００５は、任意のパケット交換ＬＡＮに接続するためのネットワークインターフェースカードであってよい。別の例として、通信インターフェース１００５は、非対称デジタル加入者回線（ＡＤＳＬ）カード、統合サービスデジタルネットワーク（ＩＳＤＮ）カード、または対応する種類の通信回線へのデータ通信接続を提供するためのモデムであってよい。無線リンクを実装することも可能である。任意のそのような実装において、通信インターフェース１００５は、さまざまなタイプの情報を表すデジタルデータストリームを搬送する電気シグナル、電磁シグナル、または光シグナルを送信および受信する。
【０２９６】
ネットワークは、典型的には、１つ以上のネットワークを介する他のデータデバイスへのデータ通信を提供する。例えば、ネットワークは、ローカルネットワーク（例えば、ＬＡＮ）を介し、あるいは通信ネットワークを介して通信サービスを提供するサービスプロバイダによって操作される機器を介して、別のコンピュータへの接続を提供することができる。ローカルネットワークおよび通信ネットワークは、例えば、デジタルデータストリームを搬送する電気信号、電磁信号、または光信号、ならびに関連する物理層（例えば、ＣＡＴ５ケーブル、同軸ケーブル、光ファイバ、など）を使用する。さらに、ネットワークは、携帯情報端末（ＰＤＡ）、ラップトップコンピュータ、または携帯電話機などのモバイルデバイスへの接続を提供することができ、コンピュータ１０００は、携帯情報端末（ＰＤＡ）、ラップトップコンピュータ、または携帯電話機などのモバイルデバイスであってよい。
【０２９７】
特定の実施形態を説明したが、これらの実施形態は、あくまでも例として提示されたものであり、本発明の範囲を限定しようとするものではない。実際に、本明細書に記載の新規な方法およびシステムは、種々の他の形態で具体化されてよく、本発明の技術的思想から離れることなく、本明細書に記載の方法およびシステムの形態における種々の省略、置換、および変更が実行可能である。添付の特許請求の範囲およびそれらの均等物は、本発明の技術的範囲および技術的思想に含まれると考えられる形態または改変を包含するように意図されている。さらに、いずれの実施形態も、必要に応じて任意の他の実施形態と組み合わせることができる。
【０２９８】
本開示の態様は、実施例として提案されるその特定の実施形態と関連して記載されているが、実施例に対する代替、変更、および変形がなされてもよい。さらに、本明細書および添付の特許請求の範囲で使用されるとき、単数形「ａ」、「ａｎ」、および「ｔｈｅ」は、文脈上他に明確に指示されない限り、複数の指示対象を含むことに、留意すべきである。
【０２９９】
［参考文献］
1.  Liu, Y.P., 1999. Enumerative Theory of Maps. Kluwer, Boston
2.  Roberto Todeschini and Viviana Consonni, Molecular Descriptors for Chemoinformatics (2 volumes), Wiley-VCH, 2009.
3.  Levinson, R.A., Self-organising retrieval system for graphs Proceedings of the AAAI (1984), 203--206.
4.  D. Cook and L. Holder (editors), Mining Graph Data, John Wiley and Sons, 2006.
5.  E.G.M. Petrakis, C. Faloutsos. Similarity Searching in Medical Image Databases. IEEE Transactions on Knowledge and Data Engineering, Vol. 9, No. 3, 1997.
6.  Gareth, A. J., Singerman, D., 1978. Theory of maps on orientable surfaces. Proceedings of the London Mathematical Society 3 (37), 273−307.
7.  Kropatsch, W. G., December 1995. Building Irregular Pyramids by Dual Graph Contraction. IEE-Proc. Vision, Image and Signal Processing Vol. 142 (No. 6), pp. 366−374.
8.  J. Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In IEEE Symposium on Foundations of Computer Science, pages 118−126, 1997.
9.  Guy Joseph Jacobson. Space-efficient static trees and graphs. In 30th Annual Symposium on Foundations of Computer Science, pages 549−554, 1989.
10.  Paul Tarau. 2009. An embedded declarative data transformation language. In Proceedings of the 11th ACM SIGPLAN conference on Principles and practice of declarative programming (PPDP '09). ACM, New York, NY, USA, 171-182. DOI=10.1145/1599410.1599432 http://doi.acm.org/10.1145/1599410.1599432
11.  Matthew J. Rattigan, Marc Maier, and David Jensen. 2006. Using structure indices for efficient approximation of network properties. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '06). ACM, New York, NY, USA, 357-366.
12.  Matthew J. Rattigan, Marc Maier, and David Jensen. 2007. Graph clustering with network structure indices. In Proceedings of the 24th international conference on Machine learning (ICML '07), Zoubin Ghahramani (Ed.). ACM, New York, NY, USA, 783-790.
13.  Gudkov and S. Nussinov, “Graph equivalence and characterization via a continuous evolution of a physical analog,” cond-mat/0209112
14.  V. Gudkov, J.E. Johnson and S. Nussinov, arXiv: cond-mat/0209111 (2002).
15.  Vladimir Gudkov, Shmuel Nussinov, arXiv:cond-mat/0209112v2 (2007)
16.  Gudkov, V., Montealegre, V., Nussinov, S., and Nussinov, Z. (2008). Community detection in complex networks by dynamical simplex evolution. Physical Review E, 78(1), 016113-1 - 016113-7.
17.  John King Gamble,Mark Friesen, Dong Zhou, Robert Joynt, and S. N. Coppersmith,  Two-particle quantum walks applied to the graph isomorphism problem, PHYSICAL REVIEW A, 81, 052313 (2010)
18.  T. Rudolph, “Constructing physically intuitive graph invariants,” quant-ph/0206068
19.  V.V. Sreedhar, The classical and quantum mechanics of a particle on a knot, Annals of Physics, Volume 359, August 2015, Pages 20−30.
20.     US Patent 8566321: Conceptual Relativity
21.     US Patent 9158847: Cognitive Memory
【図１】
2020119591.tif 000022
【図２】
2020119591.tif 000023
【図３】
2020119591.tif 000024
【図４】
2020119591.tif 000025
【図５】
2020119591.tif 000026
【図６】
2020119591.tif 000027
【図７】
2020119591.tif 000028
【図８】
2020119591.tif 000029
【図９】
2020119591.tif 000030
【図１０】
2020119591.tif 000031
【図１１】
2020119591.tif 000032
【図１２】
2020119591.tif 000033
【図１３】
2020119591.tif 000034
【図１４】
2020119591.tif 000035
【図１５】
2020119591.tif 000036
【図１６】
2020119591.tif 000037
【図１７】
2020119591.tif 000038
【図１８】
2020119591.tif 000039
【図１９】
2020119591.tif 000040
【図２０】
2020119591.tif 000041
【図２１】
2020119591.tif 000042
【図２２】
2020119591.tif 000043
【手続補正書】
【提出日】令和2年5月8日(2020.5.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ構造を含む非一時的コンピュータ可読媒体であって、
前記データ構造は、
ネットワークの複数の縮約レベルから縮約レベルを識別するフィールドと、
前記ネットワークを一意的に識別するグローバル固有アイデンティティ指定（GUID）コードのエントリと、
前記ネットワークの前記縮約レベルにおいて計算された関数値を識別するフィールドと、
前記ネットワークのノードに亘り適用されるポテンシャル力の均衡におけるQ-Medoidに基づいて、複数のサブグラフに分割された前記ネットワークのサブグラフに対応するパーティションインデックスと、
前記ネットワークのそれぞれのサブグラフと、前記ネットワークの他のサブグラフと、の間の距離測定ベクトルと、
前記ネットワークのそれぞれのサブグラフに関連するハッシュであって、前記それぞれのサブグラフのノードに亘り、シェル境界により作用される仮想粒子相互作用を用いて生成されるハッシュと、
サブグラフのQ-Medoidの半径の範囲に対応する、ローカルブルームフィルタを含むフィールドと、
を備える、コグニティブシグニチャを含み、
前記それぞれのサブグラフの前記ノードに亘る前記仮想粒子相互作用は、
Q-Medoidをランダムに選択し、
前記シェル境界の形状を設定し、前記Q-Medoidの前記ハッシュのパラメータを初期化し、
前記仮想粒子相互作用の位相角関数を、前記選択されたQ-Medoidの半径の範囲内の全てのノードが処理されるまで、繰り返し更新し、
前記仮想粒子相互作用に対する前記位相角関数の二重印加の連結を含むハッシュを生成する、
非一時的コンピュータ可読媒体。
【請求項２】
前記コグニティブシグニチャは、
前記ネットワークの前記縮約レベルに対応するそれぞれのベクトルである第１のベクトルの順序づけられたリストのセットTと、
前記ネットワークの前記縮約レベルに対応するそれぞれの第２のベクトルのリストのセットGと、
前記セットT及び対応する第１の閾値ベクトルと、前記セットG及び対応する第２の閾値ベクトルと、に基づいて計算されたグローバルブルームフィルタを含むフィールドFと、
離散非カラーネットワーク表現コード（DUNRC）のためのフィールドと、
離散カラーネットワーク表現コード（DCNRC）のためのフィールドと、
次のコグニティブシグニチャのためのフィールドと、
を備える、請求項１に記載の非一時的コンピュータ可読媒体。
【請求項３】
前記コグニティブシグニチャはさらに、
前記ネットワークは、縮約規則に基づいているかを示す縮約ツリー演算の縮約ツリー表現のフィールド、を備える、
請求項２に記載の非一時的コンピュータ可読媒体。
【請求項４】
前記コグニティブシグニチャは、前記ネットワークが縮約されるたびに生成され、前記ローカルブルームフィルタは、１度計算される、
請求項１に記載の非一時的コンピュータ可読媒体。
【請求項５】
前記ハッシュは、前記それぞれのサブグラフのノードに亘る仮想粒子のランダムウォークに基づいている、
請求項１に記載の非一時的コンピュータ可読媒体。
【請求項６】
前記シェル境界の形状は、量子確率密度関数に対応する、
請求項１に記載の非一時的コンピュータ可読媒体。
【請求項７】
前記ローカルブルームフィルタは、前記サブグラフの前記Q-Medoidに関連した複数のハッシュに基づいて計算され、前記複数のハッシュのそれぞれは、固有の初期状態をそれぞれが設定される、
請求項１に記載の非一時的コンピュータ可読媒体。
【請求項８】
DUNRCは、前記ネットワークの接続マトリクスに基づいて計算され、前記接続マトリクスは、それぞれのサブグラフの前記距離測定ベクトルに基づいて計算され、前記ハッシュは、前記ネットワークのそれぞれのサブグラフに関連する、
請求項１に記載の非一時的コンピュータ可読媒体。
【請求項９】
前記パーティションインデックスは、さらに、複数のサブグラフが前記ポテンシャル力と均衡している前記ネットワークの前記ノードに基づいて分割されることを含み、
エッジを共有するノード間において、それぞれのポテンシャル力は、引力であり、
エッジを共有しないノード間において、それぞれのポテンシャル力は、斥力である、
請求項１に記載の非一時的コンピュータ可読媒体。
【請求項１０】
前記ネットワークの斥力のポテンシャル力の合計は、前記ネットワークの引力のポテンシャル力の合計と等しい、
請求項９に記載の非一時的コンピュータ可読媒体。
【請求項１１】
前記パーティションインデクスは、さらに、前記複数のサブグラフがゾーン内のそれぞれのノード間の前記ゾーンの距離尺度に基づいたネットワーク構造インデックスにしたがって、前記ゾーン内にクラスタ化される、ことを含む、
請求項１に記載の非一時的コンピュータ可読媒体。
【請求項１２】
ネットワークをコグニティブシグニチャであるデータ構造にエンコードする方法であり、回路を含むコンピュータにより実行される方法であって、
ネットワークを入力し、
前記ネットワークの複数の縮約レベルの縮約レベルを識別し、
前記ネットワークを識別するグローバル固有アイデンティティ指定（GUID）コードを生成し、
前記ネットワークの前記縮約レベルにおいて計算された関数値を識別し、
前記ネットワークのノードに亘り適用されるポテンシャル力の均衡におけるQ-Medoidに基づいて複数のサブグラフに前記ネットワークを分割し、
前記ネットワークのそれぞれのサブグラフと、前記ネットワークの他のサブグラフと、の間の距離ベクトルを測定し、
前記ネットワークのそれぞれのサブグラフに関連するハッシュを計算し、
それぞれのサブグラフの第２のパラメータに対応するローカルブルームフィルタを、測定された前記距離ベクトル及び前記ハッシュから計算する、
方法。
【請求項１３】
前記ハッシュは、前記それぞれのサブグラフのノードに亘り、仮想粒子相互作用を用いて生成され、前記仮想粒子縮約は、シェル境界により作用される、
請求項１２に記載の方法。
【請求項１４】
フィールドTにおける第１のベクトルの順序づけられたリストを生成し、それぞれの前記第１のベクトルは、前記ネットワークの前記縮約レベルに対応し、
フィールドGにおける第２のベクトルのリストを生成し、それぞれの前記第２のベクトルは、前記ネットワークの前記縮約レベルに対応し、
グローバルブルームフィルタを計算し、前記グローバルブルームフィルタは、Tのセット及び対応する第１の閾値ベクトル、並びに、Gのセット及び対応する第２の閾値ベクトルに基づいて計算され、
離散非カラーネットワーク表現コード（DUNRC）及び離散カラーネットワーク表現コード（DCNRC）を生成し、
前記ローカルブルームフィルタ、前記グローバルブルームフィルタ、前記DUNRC及び前記DCNRCに基づいて前記ネットワークを前記データ構造にエンコードする、
ことをさらに備える、請求項１２に記載の方法。
【請求項１５】
前記ネットワークが縮約されるたびに前記コグニティブシグニチャを生成し、
前記ローカルブルームフィルタ及び前記距離測定ベクトルを１度生成する、
ことをさらに備える、請求項１４に記載の方法
【請求項１６】
前記ネットワークを前記複数のサブグラフに分割することは、さらに、
前記複数のサブグラフが前記ポテンシャル力と均衡している前記ネットワークの前記ノードに基づいて分割されることを含み、エッジを共有するノード間において、それぞれのポテンシャル力は、引力であり、エッジを共有しないノード間において、それぞれのポテンシャル力は、斥力である、
請求項１２に記載の方法。
【請求項１７】
前記ネットワークを前記複数のサブグラフに分割することは、さらに、
前記ネットワークの斥力のポテンシャル力の合計は、前記ネットワークの引力のポテンシャル力の合計と等しい、ことを含む、
請求項１６に記載の方法。
【請求項１８】
前記ネットワークを前記複数のサブグラフに分割することは、さらに、
ゾーン内のそれぞれのノード間の前記ゾーンの距離に基づいたネットワーク構造インデックスにしたがった前記ゾーンにクラスタ化されることを含む、
請求項１２に記載の方法。
【請求項１９】
前記ネットワークの前記それぞれのサブグラフに関連づけられる前記ハッシュを計算することは、
前記ネットワークの前記それぞれのサブグラフに関連づけられ、前記測定距離ベクトルに関連づけられる前記ハッシュを計算することを含み、前記ハッシュは、前記それぞれのサブグラフのノードに亘り、仮想粒子相互作用を使用して生成され、前記仮想粒子相互作用は、シェル境界により作用される、
請求項１２に記載の方法。
【請求項２０】
前記ハッシュを計算することは、前記それぞれのサブグラフの前記ノードに亘る仮想粒子のランダムウォークに基づいている、
請求項１９に記載の方法。
【外国語明細書】
2020119591000001.pdf