(57)【要約】      （修正有）【課題】オブジェクトネットワーク内のオブジェクト間アソシエーションをモデル化するシステムを提供する。【解決手段】システムは、メモリと、メモリに結合されている少なくとも一つのプロセッサと、少なくとも一つのプロセッサによって実行可能なオブジェクトネットワークモデラ構成要素とを含む。メモリは、複数のオブジェクトを含むオブジェクトネットワークを記憶し、複数のオブジェクトは、第１のオブジェクト、第２のオブジェクト、第３のオブジェクト、及び第４のオブジェクトを含む。オブジェクトネットワークモデラ構成要素は、オブジェクトネットワーク内で第１のオブジェクトを第２のオブジェクトと黙示的に関連付ける動作と、オブジェクトネットワーク内で第３のオブジェクトを第４のオブジェクトと明示的に関連付ける動作とを行う。【選択図】図１
2019053772.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトネットワーク内でクエリに十分に類似しているオブジェクトを識別するためのコンピューティングシステムであって、
実行可能命令を備えるメモリと、
前記メモリに動作可能に接続されているプロセッサと
を備え、
前記プロセッサが、方法を達成するために前記実行可能命令を実行するように構成されており、
前記方法が、
前記クエリを表すプローブオブジェクトを得るステップと、
前記プローブオブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記プローブオブジェクトを表す１以上の内部ベクトルを、前記プローブオブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
前記プローブオブジェクトを表すフィンガープリントを、前記プローブオブジェクトを表す前記１以上の内部ベクトルに基づいて生成するステップと、
第１の候補オブジェクト集合を識別するために、前記プローブオブジェクトを表す前記フィンガープリントと前記オブジェクトネットワーク内の複数のオブジェクトを表す複数のフィンガープリントとの比較と、前記プローブオブジェクトを表す前記１以上の内部ベクトルと前記オブジェクトネットワーク内の前記複数のオブジェクトを表す複数の内部ベクトルとの比較とのうちの少なくとも一つを実施するステップと、
前記プローブオブジェクトを表す前記１以上の内部ベクトルと、前記第１の候補オブジェクト集合内の各オブジェクトを表す対応する内部ベクトルとを比較することによって、前記プローブオブジェクトと前記第１の候補オブジェクト集合内の各オブジェクトとの間のそれぞれの第１の類似度基準を計算するステップと、
前記第１の候補オブジェクト集合に基づいて第２の候補オブジェクト集合を生成するステップであって、前記第２の候補オブジェクト集合が、第１の類似度基準が第１の所定の閾値を超えるオブジェクトを含む、該ステップとを含む、
コンピューティングシステム。
【請求項２】
前記プロセッサが、前記方法を達成するために前記実行可能命令を実行するように構成されており、
前記方法が、
前記プローブオブジェクトを表す前記１以上の外部ベクトルと、前記第２の候補オブジェクト集合内の各オブジェクトを表す対応する外部ベクトルとを比較することによって、前記プローブオブジェクトと前記第２の候補オブジェクト集合内の各オブジェクトとの間のそれぞれの第２の類似度基準を計算するステップと、
前記第２の候補オブジェクト集合に基づいて第３の候補オブジェクト集合を生成するステップであって、前記第３の候補オブジェクト集合が、第２の類似度基準が第２の所定の閾値を超えるオブジェクトを含む、該ステップとを含む、
請求項１に記載のコンピューティングシステム。
【請求項３】
前記第１の所定の閾値及び前記第２の所定の閾値が同じである、
請求項２に記載のコンピューティングシステム。
【請求項４】
前記プローブオブジェクトを表す前記フィンガープリントと、前記オブジェクトネットワーク内の前記複数のオブジェクトを表す前記複数のフィンガープリントとの比較が、
前記プローブオブジェクトを表す前記フィンガープリントと、前記オブジェクトネットワーク内の前記複数のオブジェクトを表す前記複数のフィンガープリントの各々との間のそれぞれのハミング距離を計算するステップと、
前記複数のオブジェクトのうち、フィンガープリントが、前記プローブオブジェクトを表す前記フィンガープリントから所定のハミング距離内にあるオブジェクトを、前記第１の候補オブジェクト集合の一部分として識別するステップと
を含む、
請求項１に記載のコンピューティングシステム。
【請求項５】
各内部ベクトルが複数の次元を含み、
前記プローブオブジェクトを表す前記１以上の内部ベクトルと前記オブジェクトネットワーク内の前記複数のオブジェクトを表す前記複数の内部ベクトルとの比較が、
前記プローブオブジェクトを表す前記１以上の内部ベクトルの各々について、前記プローブオブジェクトを表す各内部ベクトルの所定数の次元と、前記オブジェクトネットワーク内の前記複数のオブジェクトを表す前記複数の内部ベクトルの対応する次元とを比較するステップ
を含む、
請求項１に記載のコンピューティングシステム。
【請求項６】
前記プロセッサが、前記方法を達成するために前記実行可能命令を実行するように構成されており、
前記方法が、
前記第１の候補オブジェクト集合内に各オブジェクトの単一のインスタンスのみがあるように、前記第１の候補オブジェクト集合から、前記第１の候補オブジェクト集合内のオブジェクトの任意の重複したインスタンスを削除するステップ
をさらに含む、
請求項１に記載のコンピューティングシステム。
【請求項７】
前記プローブオブジェクトと、前記第１の候補オブジェクト集合内の各オブジェクトとの間の前記それぞれの第１の類似度基準を計算するステップが、
前記プローブオブジェクトを表す前記１以上の内部ベクトルと、前記オブジェクトネットワーク内の前記複数のオブジェクトを表す前記内部ベクトルの各々との間のそれぞれのコサイン類似度基準を計算するステップと、
前記プローブオブジェクトを表す前記１以上の内部ベクトルと、前記オブジェクトネットワーク内の前記複数のオブジェクトを表す前記内部ベクトルの各々との間のそれぞれのＪａｃｃａｒｄ指数類似度基準を計算するステップと
のうちの少なくとも一つを含む、
請求項１に記載のコンピューティングシステム。
【請求項８】
前記プローブオブジェクトと、前記第２の候補オブジェクト集合内の各オブジェクトとの間の前記それぞれの第２の類似度基準を計算するステップが、
前記プローブオブジェクトを表す前記１以上の外部ベクトルと、前記オブジェクトネットワーク内の前記複数のオブジェクトを表す前記外部ベクトルの各々との間のそれぞれのコサイン類似度基準を計算するステップと、
前記プローブオブジェクトを表す前記１以上の外部ベクトルと、前記オブジェクトネットワーク内の前記複数のオブジェクトを表す前記外部ベクトルの各々との間のそれぞれのＪａｃｃａｒｄ指数類似度基準を計算するステップと
のうちの少なくとも一つを含む、
請求項２に記載のコンピューティングシステム。
【請求項９】
前記プローブオブジェクトを表す前記１以上の外部ベクトルのそれぞれが、前記プローブオブジェクトを記述する複数の特徴を含み、前記複数の特徴のそれぞれが各々の重みと関連付けられている、
請求項１に記載のコンピューティングシステム。
【請求項１０】
前記プローブオブジェクトを表す前記１以上の内部ベクトルを、前記プローブオブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップが、
前記プローブオブジェクトを表す少なくとも一つの外部ベクトルの前記複数の特徴のそれぞれにハッシュ関数を適用するステップと、
前記プローブオブジェクトを表す前記少なくとも一つの外部ベクトルの前記複数の特徴のそれぞれと関連付けられている各重みに、スケーリング関数及び正規化関数のうちの少なくとも一つを適用するステップと
を含み、
前記プローブオブジェクトを表す前記１以上の内部ベクトルが固定ビット数で表され、前記プローブオブジェクトを表す前記対応する１以上の外部ベクトルが可変ビット数で表される、
請求項９に記載のコンピューティングシステム。
【請求項１１】
前記プローブオブジェクトを表す前記１以上の内部ベクトルのそれぞれが複数の次元を含み、前記複数の次元のそれぞれが各々の大きさと関連付けられ、
前記プローブオブジェクトを表す前記フィンガープリントを、前記プローブオブジェクトを表す前記１以上の内部ベクトルに基づいて生成するステップが、
前記プローブオブジェクトを表す前記１以上の内部ベクトルのうちの少なくとも一つの内部ベクトルについて、前記少なくとも一つの内部ベクトルを表す複数のフィンガープリント断片を生成するステップであって、前記複数のフィンガープリント断片のそれぞれが、前記少なくとも一つの内部ベクトルの前記複数の次元と、前記少なくとも一つの内部ベクトルの前記複数の次元の各々と関連付けられている前記各々の大きさとに基づいて生成される、該ステップと、
前記プローブオブジェクトを表す前記フィンガープリントを生成するために、生成された前記複数のフィンガープリント断片を集約するステップと
を含む、
請求項１に記載のコンピューティングシステム。
【請求項１２】
プロセッサが、第１の外部オブジェクトを得るステップと、
前記プロセッサが、前記第１の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記プロセッサが、前記第１の外部オブジェクトを表す１以上の内部ベクトルを、前記第１の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
前記プロセッサが、第２の外部オブジェクトを得るステップと、
前記プロセッサが、前記第２の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記プロセッサが、前記第２の外部オブジェクトを表す１以上の内部ベクトルを、前記第２の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
前記プロセッサが、前記第１の外部オブジェクトが前記第２の外部オブジェクトと明示的に関連付けられるかどうかを判定するステップと、
前記第１の外部オブジェクトが前記第２の外部オブジェクトと明示的に関連付けられるという判定に応答して、前記プロセッサが、前記第１の外部オブジェクトと前記第２の外部オブジェクトとの間の明示的アソシエーションを生成するステップと、
前記プロセッサが、前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと、第２の外部オブジェクトを表す前記１以上の内部ベクトルとを比較することによって、前記第１の外部オブジェクトが前記第２の外部オブジェクトと黙示的に関連付けられるかどうかを判定するステップと、
前記第１の外部オブジェクトが前記第２の外部オブジェクトと黙示的に関連付けられるという判定に応答して、前記プロセッサが、前記第１の外部オブジェクトと前記第２の外部オブジェクトとの間の黙示的アソシエーションを生成するステップと
を含む、コンピュータによって実施される方法。
【請求項１３】
各外部ベクトルが、前記外部オブジェクトを記述する複数の特徴を含み、前記複数の特徴のそれぞれが各々の重みと関連付けられる、
請求項１２に記載のコンピュータによって実施される方法。
【請求項１４】
前記１以上の内部ベクトルを前記１以上の外部ベクトルに基づいて生成するステップが、
少なくとも一つの外部ベクトルの前記複数の特徴のそれぞれにハッシュ関数を適用するステップと、
前記少なくとも一つの外部ベクトルの前記複数の特徴のそれぞれと関連付けられている各重みに正規化関数を適用するステップと
を含み、
前記１以上の内部ベクトルが固定ビット数で表され、前記対応する１以上の外部ベクトルが可変ビット数で表される、
請求項１３に記載のコンピュータによって実施される方法。
【請求項１５】
前記第１の外部オブジェクトが前記第２の外部オブジェクトと明示的に関連付けられるかどうかを判定するステップが、
前記第１の外部オブジェクトが前記第２の外部オブジェクトを直接的に参照するかどうかを判定するステップと、
前記第２の外部オブジェクトが前記第１の外部オブジェクトを直接的に参照するかどうかを判定するステップと
のうちの少なくとも一つを含む、
請求項１２に記載のコンピュータによって実施される方法。
【請求項１６】
前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第２の外部オブジェクトを表す前記１以上の内部ベクトルとを比較するステップが、
前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第２の外部オブジェクトを表す前記１以上の内部ベクトルとの間のコサイン類似度基準を計算するステップと、
前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第２の外部オブジェクトを表す前記１以上の内部ベクトルとの間のＪａｃｃａｒｄ指数類似度基準を計算するステップと
のうちの少なくとも一つを含む、
請求項１２に記載のコンピュータによって実施される方法。
【請求項１７】
前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第２の外部オブジェクトを表す前記１以上の内部ベクトルとを比較するステップが、
前記第１の外部オブジェクトと前記第２の外部オブジェクトとの間の類似度を、前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第２の外部オブジェクトを表す前記１以上の内部ベクトルとに基づいて計算するステップと、
計算された前記類似度が所定の閾値を超えるかどうかを判定するステップと、
計算された前記類似度が前記所定の閾値を超えるという判定に応答して、前記第１の外部オブジェクトと前記第２の外部オブジェクトとの間の黙示的アソシエーションを生成するステップと
を含む、
請求項１２に記載のコンピュータによって実施される方法。
【請求項１８】
前記プロセッサが、前記第１の外部オブジェクトと前記第２の外部オブジェクトの両方を表す第１の重心オブジェクトを生成するステップであって、前記第１の重心オブジェクトが、前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと前記第２の外部オブジェクトを表す前記１以上の内部ベクトルとの加重平均を含む、該ステップ
をさらに含む請求項１２に記載のコンピュータによって実施される方法。
【請求項１９】
前記プロセッサが、第３の外部オブジェクトを得るステップと、
前記プロセッサが、前記第３の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記プロセッサが、前記第３の外部オブジェクトを表す１以上の内部ベクトルを、前記第３の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
前記プロセッサが、前記第１の重心オブジェクトが前記第１の外部オブジェクト、前記第２の外部オブジェクト、及び前記第３の外部オブジェクトを表すように前記第１の重心オブジェクトを調整するステップであって、前記調整された第１の重心オブジェクトが、前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第２の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第３の外部オブジェクトを表す前記１以上の内部ベクトルとの加重平均を含む、該ステップと
をさらに含む請求項１８に記載のコンピュータによって実施される方法。
【請求項２０】
前記プロセッサが、前記第１の重心オブジェクトが第２の重心オブジェクトと黙示的に関連付けられるかどうかを、前記第１の重心オブジェクトと前記第２の重心オブジェクトとを比較することによって判定するステップであって、前記第２の重心オブジェクトが、第３の外部オブジェクトを表す１以上の内部ベクトルと第４の外部オブジェクトを表す前記１以上の内部ベクトルとの加重平均を含む、該ステップと、
前記第１の重心オブジェクトが前記第２の重心オブジェクトと黙示的に関連付けられるという判定に応答して、前記プロセッサが、前記第１の重心オブジェクトと前記第２の重心オブジェクトとの間の黙示的アソシエーションを生成するステップと
をさらに含む請求項１８に記載のコンピュータによって実施される方法。
【請求項２１】
前記第１の重心オブジェクトと前記第２の重心オブジェクトとを比較するステップが、
前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第２の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第３の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第４の外部オブジェクトを表す前記１以上の内部ベクトルとに基づいて、前記第１の重心オブジェクトと前記第２の重心オブジェクトとの間の類似度を計算するステップと、
計算された前記類似度が所定の閾値を超えるかどうかを判定するステップと、
計算された前記類似度が前記所定の閾値を超えるという判定に応答して、前記第１の重心オブジェクトと前記第２の重心オブジェクトとの間の黙示的アソシエーションを生成するステップと
を含む、
請求項２０に記載のコンピュータによって実施される方法。
【発明の詳細な説明】
【関連出願の相互参照及び優先権の主張】
【０００１】
[0001]本出願は、参照によりその内容全体が本明細書に組み込まれる、同じ発明の名称を共有する、２０１３年１２月２日に提出された米国仮特許出願第６１／９１０，７９９号に対する優先権を主張する。
【技術分野】
【０００２】
[0002]本技術分野は、一般的に、アソシエーション（ａｓｓｏｃｉａｔｉｏｎ）ベースの情報検索に関し、より詳細には、オブジェクトネットワーク内のオブジェクト間のアソシエーションをモデル化するためのシステム及び方法に関する。
【背景技術】
【０００３】
[0003]基礎となるデータによって記述されるエンティティ間のアソシエーションを発見及び探索する情報システムが、今日の情報ベースの経済には豊富に存在する。これらの情報システムの例としては、データウェアハウス、ビジネスインテリジェンスシステム、検索エンジンなどが挙げられる。これらの情報システムの多くは、カリフォルニア州レッドウッドシティ所在のＯｒａｃｌｅ  Ｃｏｒｐｏｒａｔｉｏｎから利用可能なＯＲＡＣＬＥ  １２ｃのような、商用データベース管理システムを利用する。カリフォルニア州マウンテンビュー所在のＧｏｏｇｌｅ  Ｉｎｃ．から利用可能なＧＯＯＧＬＥ検索エンジンのような他のシステムは、ＢｉｇＴａｂｌｅ及びＳｐａｎｎｅｒのような、独自のデータベースシステムを利用する。
【０００４】
[0004]しかしながら、従来のデータベースシステムを含む、従来の情報システムは、今日の増強されたハードウェア及びソフトウェア機能に遅れを取っている。言い換えれば、従来の情報システムは、現在利用可能な増強された処理能力及び拡張されたアドレス指定可能記憶空間、又は、なおさらに、近い将来の増強された処理能力及び拡張されたアドレス指定可能記憶空間を活用するようには設計されていない。
【０００５】
[0005]たとえば、ｘ８６命令セットの６４ビットバージョン（ｘ６４としても知られている）を実施することが可能である様々なＣＰＵが、現在存在する。当業者には諒解されるように、これらのｘ６４コンピューティングシステムは、従来のコンピューティングシステムと比較して、非常に大きいアドレス指定可能メモリセットを含む。その上、ｘ８６命令セットアーキテクチャ向けの２５６ビットＡｄｖａｎｃｅｄ  Ｖｅｃｔｏｒ  Ｅｘｔｅｎｓｉｏｎｓ  ＳＩＭＤ（単一命令複数データ）命令に対する５１２ビット拡張が、近年のうちに利用可能になることが予期されている。待望されているそのような５１２ビット拡張の一例が、２０１３年７月にＩｎｔｅｌによって提案されたＡＶＸ−５１２拡張である。しかしながら、従来の情報システムは、たとえば、ＡＶＸ−５１２拡張及び当該拡張を実行するように構成されるプロセッサによって利用可能になる並列処理機能を活用するには準備不足である。加えて、ＧＰＧＰＵ（汎用グラフィックス処理ユニット）が、それらＧＰＧＰＵのアーキテクチャによる効率の高い処理進行であって、当該処理進行自体を大規模な並列処理に供する、処理進行を実施するための魅力的なハードウェア・オプションを表すことになることが予期される。また、従来の情報システムは、現在利用可能であるか、又は、まもなく利用可能になるコンピューティング能力を活用するようには設計されていない。
【０００６】
[0006]したがって、現在利用可能なコンピュータハードウェア及びソフトウェア並びに近い将来のコンピュータハードウェア及びソフトウェアの劇的な改善を考慮に入れるオブジェクトネットワークをモデル化するコンピューティングシステム及び方法が必要とされている。
【発明の概要】
【０００７】
[0007]様々な態様及び実施形態によれば、システムは、１以上のオブジェクトネットワークを実装し、問い合わせるように構成される。これらのオブジェクトネットワークは、たとえば、明示的なアソシエーション及び黙示的なアソシエーションを使用して、複数のオブジェクトを関連付ける。明示的なアソシエーションは、オブジェクト間の関係を明確に表す、記憶されている情報に基づき得る（たとえば、ウェブページ上のハイパーリンク）。黙示的なアソシエーションは、ベクトル要約及び比較のような、様々なデータ操作技法を使用して、本明細書に開示されているいくつかの実施形態によって発見することができる。いくつかの実施形態は、オブジェクトが既存のオブジェクトネットワークに、リアルタイムで追加されることを可能にする。加えて、いくつかの実施形態において、オブジェクトネットワークは、ユーザ又はより高次のアプリケーションのような、外部エンティティに対する対象のオブジェクトと同様である、オブジェクトネットワーク内のオブジェクトを識別するために、効率的に検索することができる。
【０００８】
[0008]たとえば、いくつかの実施形態において、システムは、プローブオブジェクトを受信し、プローブオブジェクトと１以上の特性を共有する、オブジェクトネットワーク内の１以上のオブジェクトを識別するように構成される。これらの実施形態は、高い性能及び容量を達成するために、再現率及び適合率のトレードオフを実装することによって、類似度照合が本質的に曖昧であり、不正確であるという評価を明らかにする。下記にさらに説明するように、いくつかの実施形態は、再現率、適合率、及び性能に関する個別の特性を有する、複数の別個のクエリ処理段階に基づく。本明細書に記載されているこれら上記の手法を使用して、実施形態は、従来の技術と比較して、クエリ待ち時間の低減及びクエリボリューム（ｑｕｅｒｙ  ｖｏｌｕｍｅ）（スループット）の増大を呈する。
【０００９】
[0009]様々な態様及び実施形態によれば、システムが提供される。システムは、複数のオブジェクトを含むオブジェクトネットワークを記憶するメモリであって、複数のオブジェクトは、第１のオブジェクトと、第２のオブジェクトと、第３のオブジェクトと、第４のオブジェクトとを含む、メモリと、メモリに結合されている少なくとも一つのプロセッサと、少なくとも一つのプロセッサによって実行可能であり、オブジェクトネットワーク内で、第１のオブジェクトを第２のオブジェクトと黙示的に関連付け、オブジェクトネットワーク内で、第３のオブジェクトを第４のオブジェクトと明示的に関連付けるように構成される、オブジェクトネットワークモデラ構成要素とを含む。
【００１０】
[0010]一つの実施形態において、複数のオブジェクトの各々は、少なくとも一つの文書を表す。別の実施形態において、複数のオブジェクトは、複数のオブジェクトのうちの第５のオブジェクトと関連付けられている少なくとも一つの重心を含む。加えて、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、第６のオブジェクトを第５のオブジェクトに類似するものとして識別することによって、複数のオブジェクトのうちの第６のオブジェクトを少なくとも一つの重心と関連付け、第５のオブジェクトと少なくとも一つの重心との間の１以上のリンクをトラバースし、少なくとも一つの重心の識別子を第６のオブジェクト内に記憶するように構成することができる。この実施形態において、オブジェクトネットワークモデラ構成要素は、第６のオブジェクトのベクトルに基づいて重心のベクトルを修正するように構成することができる。加えて、複数のオブジェクトは、第７のオブジェクトと関連付けられている１以上の追加の重心を含んでもよい。
【００１１】
[0011]一つの実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、第７のオブジェクト並びに第５のオブジェクト及び第６のオブジェクトの間の類似度の閾値レベルを識別することによって、上記少なくとも一つの重心を、上記１以上の重心と関連付け、第５のオブジェクトと少なくとも一つの重心との間の１以上のリンクをトラバースし、第６のオブジェクトと少なくとも一つの重心との間の１以上のリンクをトラバースし、第７のオブジェクトと１以上の重心との間の１以上のリンクをトラバースし、少なくとも一つの重心の識別子を１以上の重心内に記憶するように構成することができる。
【００１２】
[0012]一つの実施形態によれば、コンピュータシステムを使用して方法が実施される。コンピュータシステムは、メモリと、メモリに結合されている少なくとも一つのプロセッサとを含む。方法は、メモリ内に、複数のオブジェクトを含むオブジェクトネットワークを記憶する動作であって、複数のオブジェクトは、第１のオブジェクトと、第２のオブジェクトと、第３のオブジェクトと、第４のオブジェクトとを含む、記憶する動作と、オブジェクトネットワーク内で、第１のオブジェクトを第２のオブジェクトと黙示的に関連付ける動作と、オブジェクトネットワーク内で、第３のオブジェクトを第４のオブジェクトと明示的に関連付ける動作とを含む。
【００１３】
[0013]本方法において、オブジェクトネットワークを記憶する動作は、各々が少なくとも一つの文書を表す複数のオブジェクトを記憶する動作を含むことができる。いくつかの実施形態において、オブジェクトネットワークを記憶する動作は、複数のオブジェクトのうちの第５のオブジェクトと関連付けられている少なくとも一つの重心を記憶する動作を含むことができる。
【００１４】
[0014]本方法は、少なくとも部分的に、第６のオブジェクトが第５のオブジェクトに類似することを識別することによって、複数のオブジェクトのうちの第６のオブジェクトを少なくとも一つの重心と関連付ける動作と、第５のオブジェクトと少なくとも一つの重心との間の１以上のリンクをトラバースする動作と、少なくとも一つの重心の識別子を第６のオブジェクト内に記憶する動作とをさらに含むことができる。一つの実施形態において、本方法は、第６のオブジェクトのベクトルに基づいて重心のベクトルを修正する動作を含むことができる。さらに、オブジェクトネットワークを記憶する動作は、第７のオブジェクトと関連付けられている１以上の追加の重心を記憶する動作を含むことができる。
【００１５】
[0015]別の実施形態において、方法は、少なくとも部分的に、第７のオブジェクト並びに第５のオブジェクト及び第６のオブジェクトの間の類似度の閾値レベルを識別することによって、上記少なくとも一つの重心を、上記１以上の重心と関連付ける動作と、第５のオブジェクトと少なくとも一つの重心との間の１以上のリンクをトラバースする動作と、第６のオブジェクトと少なくとも一つの重心との間の１以上のリンクをトラバースする動作と、第７のオブジェクトと１以上の重心との間の１以上のリンクをトラバースする動作と、少なくとも一つの重心の識別子を１以上の重心内に記憶する動作とを含む。
【００１６】
[0016]別の実施形態によれば、オブジェクトネットワークモデルを実装するように構成されるコンピュータ実行可能命令シーケンスを記憶している持続性コンピュータ可読媒体が提供される。命令シーケンスは、少なくとも一つのプロセッサに、複数のオブジェクトを含むオブジェクトネットワークを記憶する動作であって、複数のオブジェクトは、第１のオブジェクトと、第２のオブジェクトと、第３のオブジェクトと、第４のオブジェクトとを含む、記憶する動作と、オブジェクトネットワーク内で、第１のオブジェクトを第２のオブジェクトと黙示的に関連付ける動作と、オブジェクトネットワーク内で、第３のオブジェクトを第４のオブジェクトと明示的に関連付ける動作とを行うよう命令するように構成される命令を含む。
【００１７】
[0017]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、各々が少なくとも一つの文書を表す複数のオブジェクトを記憶することによって、オブジェクトネットワークを記憶する動作を行うよう命令するようにさらに構成することができる。加えて、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、複数のオブジェクトのうちの第５のオブジェクトと関連付けられている少なくとも一つの重心を記憶することによって、オブジェクトネットワークを記憶する動作を行うよう命令するようにさらに構成することができる。
【００１８】
[0018]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、第６のオブジェクトが第５のオブジェクトに類似することを識別することによって、複数のオブジェクトのうちの第６のオブジェクトを少なくとも一つの重心と関連付ける動作と、第５のオブジェクトと少なくとも一つの重心との間の１以上のリンクをトラバースする動作と、少なくとも一つの重心の識別子を第６のオブジェクト内に記憶する動作とを行うよう命令するようにさらに構成することができる。加えて、命令は、少なくとも一つのプロセッサに、第６のオブジェクトのベクトルに基づいて重心のベクトルを修正する動作を行うよう命令するようにさらに構成することができる。
【００１９】
[0019]別の実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、第７のオブジェクトと関連付けられている１以上の追加の重心を記憶することによって、オブジェクトネットワークを記憶する動作を行うよう命令するようにさらに構成することができる。
【００２０】
[0020]また別の実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、第７のオブジェクト並びに第５のオブジェクト及び第６のオブジェクトの間の類似度の閾値レベルを識別することによって、上記少なくとも一つの重心を、上記１以上の重心と関連付ける動作と、第５のオブジェクトと少なくとも一つの重心との間の１以上のリンクをトラバースする動作と、第６のオブジェクトと少なくとも一つの重心との間の１以上のリンクをトラバースする動作と、第７のオブジェクトと１以上の重心との間の１以上のリンクをトラバースする動作と、少なくとも一つの重心の識別子を１以上の重心内に記憶する動作とを行うよう命令するようにさらに構成することができる。
【００２１】
[0021]別の実施形態によれば、システムが提供される。システムは、少なくとも一つの特徴を記述する情報を含む外部ベクトルを記憶しているメモリと、メモリに結合されている少なくとも一つのプロセッサと、少なくとも一つのプロセッサによって実行可能なオブジェクトネットワークモデラ構成要素とを含む。オブジェクトネットワークモデラ構成要素は、少なくとも一つの特徴の少なくとも一つの内部表現を生成し、少なくとも一つの内部表現を内部ベクトルに記憶するように構成される。加えて、外部ベクトルは、少なくとも一つの文書を表すことができる。
【００２２】
[0022]一つの実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、少なくとも一つの特徴を識別する情報の少なくとも一部分の少なくとも一つのハッシュ値を計算することによって、少なくとも一つの内部表現を生成するように構成することができる。別の実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、少なくとも一つの特徴の重みを指定する情報の少なくとも一部分の少なくとも一つの正規化値を計算することによって、少なくとも一つの内部表現を生成するように構成することができる。
【００２３】
[0023]また別の実施形態において、オブジェクトネットワークモデラ構成要素は、外部ベクトルを受信し、外部ベクトルによって記述されている特徴の数を判定し、特徴の数に基づいて内部ベクトルを割り当てるようにさらに構成することができる。加えて、オブジェクトネットワークモデラは、少なくとも、特徴の数に等しい次元の数を記憶するようなサイズにされているベクトルを割り当てるように構成されるベクトルアロケータ（ｖｅｃｔｏｒ  ａｌｌｏｃａｔｏｒ）を使用して内部ベクトルを割り当てるように構成することができる。
【００２４】
[0024]一つの実施形態において、オブジェクトネットワークモデラは、所定サイズに適合するように内部ベクトルを量子化するようにさらに構成することができる。さらに、オブジェクトネットワークモデラ構成要素は、内部ベクトルの要約を生成するように構成することができる。
【００２５】
[0025]別の実施形態によれば、メモリと、メモリに結合されている少なくとも一つのプロセッサとを含むコンピュータシステムを使用して実施される方法が提供される。方法は、少なくとも一つの特徴を記述する情報を含む外部ベクトルを記憶する動作と、少なくとも一つの特徴の少なくとも一つの内部表現を生成する動作と、少なくとも一つの内部表現を内部ベクトルに記憶する動作とを含む。
【００２６】
[0026]本方法において、外部ベクトルを記憶する動作は、少なくとも一つの文書を表す外部ベクトルを記憶する動作を含むことができる。加えて、少なくとも一つの内部表現を生成する動作は、少なくとも一つの特徴を識別する情報の少なくとも一部分の少なくとも一つのハッシュ値を計算する動作を含むことができる。その上、少なくとも一つの内部表現を生成する動作は、少なくとも一つの特徴の重みを指定する情報の少なくとも一部分の少なくとも一つの正規化値を計算する動作を含むことができる。
【００２７】
[0027]方法は、外部ベクトルを受信する動作と、外部ベクトルによって記述されている特徴の数を判定する動作と、特徴の数に基づいて内部ベクトルを割り当てる動作とをさらに含むことができる。本方法において、内部ベクトルを割り当てる動作は、少なくとも、特徴の数に等しい次元の数を記憶するようなサイズにされているベクトルを割り当てるように構成されるベクトルアロケータを使用して内部ベクトルを割り当てる動作を含むことができる。加えて、本方法は、所定サイズに適合するように内部ベクトルを量子化する動作を含むことができる。本方法はまた、内部ベクトルの要約を生成する動作をも含むことができる。
【００２８】
[0028]別の実施形態によれば、オブジェクトネットワークモデルを実装するように構成されるコンピュータ実行可能命令シーケンスを記憶している持続性コンピュータ可読媒体が提供される。少なくとも一つのプロセッサに、少なくとも一つの特徴を記述する情報を含む外部ベクトルを記憶する動作と、少なくとも一つの特徴の少なくとも一つの内部表現を生成する動作と、少なくとも一つの内部表現を内部ベクトルに記憶する動作とを行うよう命令するように構成される命令を含む命令シーケンス。
【００２９】
[0029]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、少なくとも一つの文書を表す外部ベクトルを記憶することによって、外部ベクトルを記憶する動作を行うよう命令するようにさらに構成することができる。加えて、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、少なくとも一つの特徴を識別する情報の少なくとも一部分の少なくとも一つのハッシュ値を計算することによって、少なくとも一つの内部表現を生成する動作を行うよう命令するように構成することができる。
【００３０】
[0030]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、少なくとも一つの特徴の重みを指定する情報の少なくとも一部分の少なくとも一つの正規化値を計算することによって、少なくとも一つの内部表現を生成する動作を行うよう命令するようにさらに構成することができる。別の実施形態において、命令は、少なくとも一つのプロセッサに、外部ベクトルを受信する動作と、外部ベクトルによって記述されている特徴の数を判定する動作と、特徴の数に基づいて内部ベクトルを割り当てる動作とを行うよう命令するようにさらに構成することができる。
【００３１】
[0031]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、少なくとも、特徴の数に等しい次元の数を記憶するようなサイズにされているベクトルを割り当てるように構成されるベクトルアロケータを使用して内部ベクトルを割り当てることによって、内部ベクトルを割り当てる動作を行うよう命令するようにさらに構成することができる。別の実施形態において、命令は、少なくとも一つのプロセッサに、所定サイズに適合するように内部ベクトルを量子化する動作を行うよう命令するようにさらに構成することができる。また別の実施形態において、命令は、少なくとも一つのプロセッサに、内部ベクトルの要約を生成する動作を行うよう命令するようにさらに構成することができる。
【００３２】
[0032]別の態様によれば、システムが提供される。システムは、メモリと、メモリに結合されている少なくとも一つのプロセッサと、少なくとも一つのプロセッサによって実行可能なオブジェクトネットワークモデラ構成要素とを含む。オブジェクトネットワークモデラ構成要素は、第１のオブジェクト内に第１のベクトルを生成する動作であって、第１のベクトルは第１のエンティティを記述する、第１のベクトルを生成する動作と、第２のオブジェクト内に第２のベクトルを生成する動作であって、第２のベクトルは第１のエンティティを記述する、第２のベクトルを生成する動作とを行うように構成される。
【００３３】
[0033]一つの実施形態において、第１のエンティティは、少なくとも一つの文書を含むことができる。別の実施形態において、少なくとも一つの文書は複数の部分を含むことができ、第１のベクトルは複数の部分のうちの第１の部分を記述しており、第２のベクトルは複数の部分のうちの第２の部分を記述する。加えて、複数の部分のそれぞれは少なくとも一つの文書の線形セグメントを含むことができる。一つの実施形態において、複数の部分のそれぞれは単語クラスを含むことができる。加えて、複数の部分のそれぞれは単語バケットを含むことができる。
【００３４】
[0034]一つの実施形態において、第１の部分は、少なくとも一つの文書からのテキストを含んでもよく、第２の部分は、少なくとも一つの文書からの画像を含んでもよい。別の実施形態において、オブジェクトネットワークモデラ構成要素は、第１のオブジェクト及び第２のオブジェクトを、第１のエンティティを表す重心と関連付けるように構成することができる。
【００３５】
[0035]別の実施形態によれば、コンピュータシステムを使用して実施される方法が提供される。コンピュータシステムは、メモリと、メモリに結合されている少なくとも一つのプロセッサとを含む。方法は、第１のオブジェクト内に第１のベクトルを生成する動作であって、第１のベクトルは第１のエンティティを記述する、第１のベクトルを生成する動作と、第２のオブジェクト内に第２のベクトルを生成する動作であって、第２のベクトルは第１のエンティティを記述する、第２のベクトルを生成する動作とを含む。
【００３６】
[0036]一つの実施形態において、第１のベクトルを生成する動作は、少なくとも一つの文書を記述する第１のベクトルを生成する動作を含むことができる。加えて、少なくとも一つの文書は複数の部分を含むことができ、第１のベクトルを生成する動作は、複数の部分のうちの第１の部分を記述する第１のベクトルを生成する動作を含むことができ、第２のベクトルを生成する動作は、複数の部分のうちの第２の部分を記述する第２のベクトルを生成する動作を含むことができる。
【００３７】
[0037]別の実施形態において、複数の部分のそれぞれは少なくとも一つの文書の線形セグメントを含むことができ、第１のベクトルを生成する動作は、線形セグメントを記述する第１のベクトルを生成する動作を含む。また別の実施形態において、複数の部分のそれぞれは単語クラスを含むことができ、第１のベクトルを生成する動作は、単語クラスを記述する第１のベクトルを生成する動作を含む。なお別の実施形態において、複数の部分のそれぞれは単語バケットを含むことができ、第１のベクトルを生成する動作は、単語バケットを記述する第１のベクトルを生成する動作を含む。
【００３８】
[0038]別の実施形態において、第１の部分は、少なくとも一つの文書からのテキストを含んでもよく、第２の部分は、少なくとも一つの文書からの画像を含み、第１のベクトルを生成する動作は、テキストを記述する第１のベクトルを生成する動作を含み、第２のベクトルを生成する動作は、画像を記述する第２のベクトルを生成する動作を含む。加えて、本方法は、第１のオブジェクト及び第２のオブジェクトを、第１のエンティティを表す重心と関連付ける動作を含むことができる。
【００３９】
[0039]別の実施形態によれば、オブジェクトネットワークモデルを実装するように構成されるコンピュータ実行可能命令シーケンスを記憶している持続性コンピュータ可読媒体が提供される。コンピュータ実行可能命令シーケンスは、少なくとも一つのプロセッサに、第１のオブジェクト内に第１のベクトルを生成する動作であって、第１のベクトルは第１のエンティティを記述する、第１のベクトルを生成する動作と、第２のオブジェクト内に第２のベクトルを生成する動作であって、第２のベクトルは第１のエンティティを記述する、第２のベクトルを生成する動作とを行うように命令するように構成される。
【００４０】
[0040]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、少なくとも一つの文書を記述する第１のベクトルを生成することによって、第１のベクトルを生成する動作を行うよう命令するようにさらに構成することができる。加えて、少なくとも一つの文書は複数の部分を含むことができ、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、複数の部分のうちの第１の部分を記述する第１のベクトルを生成することによって、第１のベクトルを生成する動作と、少なくとも部分的に、複数の部分のうちの第２の部分を記述する第２のベクトルを生成することによって、第２のベクトルを生成する動作とを行うよう命令するようにさらに構成することができる。
【００４１】
[0041]一つの実施形態において、複数の部分のそれぞれは少なくとも一つの文書の線形セグメントを含むことができ、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、線形セグメントを記述する第１のベクトルを生成することによって第１のベクトルを生成する動作を行うよう命令するようにさらに構成することができる。加えて、複数の部分のそれぞれは単語クラスを含むことができ、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、単語クラスを記述する第１のベクトルを生成することによって第１のベクトルを生成する動作を行うよう命令するようにさらに構成することができる。
【００４２】
[0042]一つの実施形態において、複数の部分のそれぞれは単語バケットを含むことができ、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、単語バケットを記述する第１のベクトルを生成することによって第１のベクトルを生成する動作を行うよう命令するようにさらに構成することができる。別の実施形態において、第１の部分は、少なくとも一つの文書からのテキストを含んでもよく、第２の部分は、少なくとも一つの文書からの画像を含んでもよく、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、テキストを記述する第１のベクトルを生成することによって第１のベクトルを生成する動作と、少なくとも部分的に、画像を記述する第２のベクトルを生成することによって第２のベクトルを生成する動作とを行うよう命令するようにさらに構成することができる。また別の実施形態において、命令は、少なくとも一つのプロセッサに、第１のオブジェクト及び第２のオブジェクトを、第１のエンティティを表す重心と関連付ける動作を行うよう命令するようにさらに構成することができる。
【００４３】
[0043]別の実施形態によれば、システムが提供される。システムは、複数の次元を記述する情報を含む内部ベクトルを記憶しているメモリと、メモリに結合されている少なくとも一つのプロセッサと、少なくとも一つのプロセッサによって実行可能なオブジェクトネットワークモデラ構成要素とを含む。オブジェクトネットワークモデラ構成要素は、複数の次元を記述する情報を複数の断片にグループ化する動作と、複数の次元を記述する情報に基づいて複数の要約を生成する動作であって、複数の要約のそれぞれは、複数の断片のそれぞれに対応する、複数の要約を生成する動作と、複数の要約をフィンガープリントに集約する動作とを行うように構成される。
【００４４】
[0044]一つの実施形態において、内部ベクトルは、少なくとも一つの文書を表すことができる。別の実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、複数の次元を記述する情報を複数の大きさに従って重み付けすることによって、複数の要約をフィンガープリントに集約する動作を行うように構成することができ、複数の大きさのそれぞれは、複数の次元を記述する情報に記述されているそれぞれの次元に対応する。
【００４５】
[0045]別の実施形態において、オブジェクトネットワークモデラ構成要素は、複数の次元を記述する情報を、所定の数を有する複数の断片にグループ化するように構成することができる。また別の実施形態において、オブジェクトネットワークモデラ構成要素は、複数の要約についての１以上の要約の配列をインデックス内に記憶する動作を行うようにさらに構成することができる。加えて、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、プローブオブジェクトのフィンガープリントの一部分をインデックスと比較することによって、クエリを実行する動作を行うようにさらに構成することができる。また別の実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、プローブオブジェクト内のベクトルから生成されるベクトルと、インデックスにおいて参照されるオブジェクトのベクトルとの間の類似度を計算することによって、クエリを実行する動作を行うようにさらに構成することができる。
【００４６】
[0046]別の実施形態によれば、コンピュータシステムを使用して実施される方法が提供される。コンピュータシステムは、メモリと、メモリに結合されている少なくとも一つのプロセッサとを含む。方法は、複数の次元を記述する情報を含む内部ベクトルを記憶する動作と、複数の次元を記述する情報を複数の断片にグループ化する動作と、複数の次元を記述する情報に基づいて複数の要約を生成する動作であって、複数の要約のそれぞれは、複数の断片のそれぞれに対応する、複数の要約を生成する動作と、複数の要約をフィンガープリントに集約する動作とを含む。
【００４７】
[0047]本方法において、内部ベクトルを記憶する動作は、少なくとも一つの文書を表す内部ベクトルを記憶する動作を含むことができる。加えて、複数の要約をフィンガープリントに集約する動作は、複数の次元を記述する情報を複数の大きさに従って重み付けする動作を含むことができ、複数の大きさのそれぞれは、複数の次元を記述する情報に記述されているそれぞれの次元に対応する。
【００４８】
[0048]本方法において、情報をグループ化する動作は、複数の次元を記述する情報を、所定の数を有する複数の断片にグループ化する動作を含むことができる。さらに、本方法は、複数の要約についての１以上の要約の配列をインデックス内に記憶する動作を含むことができる。
【００４９】
[0049]方法は、少なくとも部分的に、プローブオブジェクトのフィンガープリントの一部分をインデックスと比較することによって、クエリを実行する動作をさらに含むことができる。加えて、本方法は、少なくとも部分的に、プローブオブジェクト内のベクトルから生成されるベクトルと、インデックスにおいて参照されるオブジェクトのベクトルとの間の類似度を計算することによって、クエリを実行する動作を含むことができる。
【００５０】
[0050]別の実施形態によれば、オブジェクトネットワークモデルを実装するように構成されるコンピュータ実行可能命令シーケンスを記憶している持続性コンピュータ可読媒体が提供される。コンピュータ実行可能命令シーケンスは、少なくとも一つのプロセッサに、複数の次元を記述する情報を含む内部ベクトルを記憶する動作と、複数の次元を記述する情報を複数の断片にグループ化する動作と、複数の次元を記述する情報に基づいて複数の要約を生成する動作であって、複数の要約のそれぞれは、複数の断片のそれぞれに対応する、複数の要約を生成する動作と、複数の要約をフィンガープリントに集約する動作とを行うよう命令するように構成される命令を含む。
【００５１】
[0051]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、少なくとも一つの文書を表す内部ベクトルを記憶することによって、内部ベクトルを記憶する動作を行うよう命令するようにさらに構成することができる。加えて、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、複数の次元を記述する情報を複数の大きさに従って重み付けすることによって、複数の要約をフィンガープリントに集約する動作を行うよう命令するようにさらに構成することができ、複数の大きさのそれぞれは、複数の次元を記述する情報に記述されているそれぞれの次元に対応する。
【００５２】
[0052]別の実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、複数の次元を記述する情報を、所定の数を有する複数の断片にグループ化することによって、情報をグループ化する動作を行うよう命令するようにさらに構成することができる。また別の実施形態において、命令は、少なくとも一つのプロセッサに、複数の要約についての１以上の要約の配列をインデックス内に記憶する動作を行うよう命令するようにさらに構成することができる。
【００５３】
[0053]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、プローブオブジェクトのフィンガープリントの一部分をインデックスと比較することによって、クエリを実行する動作を行うよう命令するようにさらに構成することができる。加えて、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、プローブオブジェクト内のベクトルから生成されるベクトルと、インデックスにおいて参照されるオブジェクトのベクトルとの間の類似度を計算することによって、クエリを実行する動作を行うよう命令するようにさらに構成することができる。
【００５４】
[0054]別の実施形態によれば、グラフィックス処理ユニット（ＧＰＵ）が提供される。ＧＰＵは、複数のオブジェクトを含むオブジェクトネットワークを記憶しているメモリであって、複数のオブジェクトは、第１のオブジェクトと、第２のオブジェクトと、第３のオブジェクトと、第４のオブジェクトとを含む、メモリと、メモリに結合されている複数の算術論理演算ユニット（ＡＬＵ）と、メモリに結合されている少なくとも一つのプロセッサと、少なくとも一つのプロセッサによって実行可能なオブジェクトネットワークモデラ構成要素とを含む。オブジェクトネットワークモデラ構成要素は、オブジェクトネットワーク内で第１のオブジェクトを第２のオブジェクトと黙示的に関連付ける動作と、オブジェクトネットワーク内で第３のオブジェクトを第４のオブジェクトと明示的に関連付ける動作とを行うように構成される。
【００５５】
[0055]一つの実施形態において、複数のオブジェクトの各々は、少なくとも一つの文書を表すことができる。別の実施形態において、オブジェクトネットワークモデラ構成要素は、複数のＡＬＵを使用して単一のバッチ内に外部特徴の複数の内部表現を生成する動作を行うようにさらに構成することができる。加えて、オブジェクトネットワークモデラ構成要素は、複数のＡＬＵを使用して単一のバッチ内の複数の外部特徴の重みを正規化する動作を行うようにさらに構成することができる。
【００５６】
[0056]一つの実施形態において、オブジェクトネットワークモデラ構成要素は、複数のＡＬＵを使用して単一のバッチ内に複数の次元−大きさ対を要約する動作を行うようにさらに構成することができる。別の実施形態において、オブジェクトネットワークモデラ構成要素は、複数のＡＬＵを使用して単一のバッチ内で複数のコサイン類似度値及び／又は複数のＪａｃｃａｒｄ指数値を計算する動作を行うようにさらに構成することができる。別の実施形態において、オブジェクトネットワークモデラ構成要素は、複数のＡＬＵを使用して単一のバッチ内で複数のハミング距離値を計算する動作を行うようにさらに構成することができる。また別の実施形態において、オブジェクトネットワークモデラ構成要素は、複数のＡＬＵを使用して単一のバッチ内で複数のフィンガープリント断片を処理する動作を行うようにさらに構成することができる。
【００５７】
[0057]別の実施形態によれば、グラフィックス処理ユニット（ＧＰＵ）を使用して実施される方法が提供される。ＧＰＵは、メモリと、メモリに結合されている複数の算術論理演算ユニット（ＡＬＵ）と、メモリに結合されている少なくとも一つのプロセッサとを含む。方法は、複数のオブジェクトを含むオブジェクトネットワークを記憶する動作であって、複数のオブジェクトは、第１のオブジェクトと、第２のオブジェクトと、第３のオブジェクトと、第４のオブジェクトとを含む、記憶する動作と、オブジェクトネットワーク内で、第１のオブジェクトを第２のオブジェクトと黙示的に関連付ける動作と、オブジェクトネットワーク内で、第３のオブジェクトを第４のオブジェクトと明示的に関連付ける動作とを含む。
【００５８】
[0058]本方法において、複数のオブジェクトを含むオブジェクトネットワークを記憶する動作は、各々が少なくとも一つの文書を表す複数のオブジェクトを記憶する動作を含むことができる。加えて、方法は、複数のＡＬＵを使用して単一のバッチ内に外部特徴の複数の内部表現を生成することを含む動作を含むことができる。さらに、方法は、複数のＡＬＵを使用して単一のバッチ内で複数の外部特徴の重みを正規化する動作を含むことができる。
【００５９】
[0059]一つの実施形態において、方法は、複数のＡＬＵを使用して単一のバッチ内に複数の次元−大きさ対を要約する動作をさらに含むことができる。別の実施形態において、方法は、複数のＡＬＵを使用して単一のバッチ内で複数のコサイン類似度値を計算する動作をさらに含むことができる。また別の実施形態において、方法は、複数のＡＬＵを使用して単一のバッチ内で複数のハミング距離値を計算する動作をさらに含むことができる。なおまた別の実施形態において、方法は、複数のＡＬＵを使用して単一のバッチ内で複数のフィンガープリント断片を処理する動作をさらに含むことができる。
【００６０】
[0060]別の実施形態によれば、オブジェクトネットワークモデルを実装するように構成されるコンピュータ実行可能命令シーケンスを記憶している持続性コンピュータ可読媒体が提供される。コンピュータ実行可能命令シーケンスは、少なくとも一つのプロセッサ及び複数の算術論理演算ユニット（ＡＬＵ）に、複数のオブジェクトを含むオブジェクトネットワークを記憶する動作であって、複数のオブジェクトは、第１のオブジェクトと、第２のオブジェクトと、第３のオブジェクトと、第４のオブジェクトとを含む、記憶する動作と、オブジェクトネットワーク内で、第１のオブジェクトを第２のオブジェクトと黙示的に関連付ける動作と、オブジェクトネットワーク内で、第３のオブジェクトを第４のオブジェクトと明示的に関連付ける動作とを行うよう命令するように構成される命令を含む。
【００６１】
[0061]一つの実施形態において、命令は、少なくとも一つのプロセッサ及び複数のＡＬＵに、少なくとも部分的に、各々が少なくとも一つの文書を表す複数のオブジェクトを記憶することによって、複数のオブジェクトを含むオブジェクトネットワークを記憶する動作を行うよう命令するようにさらに構成することができる。別の実施形態において、命令は、少なくとも一つのプロセッサ及び複数のＡＬＵに、複数のＡＬＵを使用して単一のバッチ内に外部特徴の複数の内部表現を生成する動作を行うよう命令するようにさらに構成することができる。
【００６２】
[0062]また別の実施形態において、命令は、少なくとも一つのプロセッサ及び複数のＡＬＵに、複数のＡＬＵを使用して単一のバッチ内で複数の外部特徴の重みを正規化する動作を行うよう命令するようにさらに構成することができる。加えて、命令は、少なくとも一つのプロセッサ及び複数のＡＬＵに、複数のＡＬＵを使用して単一のバッチ内で複数の次元−大きさ対を要約する動作を行うよう命令するようにさらに構成することができる。
【００６３】
[0063]また別の実施形態において、命令は、少なくとも一つのプロセッサ及び複数のＡＬＵに、複数のＡＬＵを使用して単一のバッチ内で複数のコサイン類似度値を計算する動作を行うよう命令するようにさらに構成することができる。加えて、命令は、少なくとも一つのプロセッサ及び複数のＡＬＵに、複数のＡＬＵを使用して単一のバッチ内で複数のハミング距離値を計算する動作を行うよう命令するようにさらに構成することができる。またさらに、命令は、少なくとも一つのプロセッサ及び複数のＡＬＵに、複数のＡＬＵを使用して単一のバッチ内で複数のフィンガープリント断片を処理する動作を行うよう命令するようにさらに構成することができる。
【００６４】
[0064]別の実施形態によれば、システムが提供される。システムは、メモリと、メモリに結合されている少なくとも一つのプロセッサと、少なくとも一つのプロセッサによって実行可能なオブジェクトネットワークモデラ構成要素とを含む。オブジェクトネットワークモデラ構成要素は、複数のオブジェクトを含むオブジェクトストアを生成する動作と、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つのオブジェクトインデックスを生成する動作と、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つの逆インデックスを生成する動作とを行うように構成される。
【００６５】
[0065]一つの実施形態において、複数のオブジェクトのそれぞれは、少なくとも一つの文書を表すことができる。別の実施形態において、オブジェクトネットワークモデラ構成要素は、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つの順列インデックスを生成する動作を行うようにさらに構成することができる。別の実施形態において、オブジェクトネットワークモデラ構成要素は、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つの次元インデックスを生成する動作を行うようにさらに構成することができる。また別の実施形態において、少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスは、共通のデータ構造から生成されてもよい。加えて、少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスの各々は、インデックスアロケータ（ｉｎｄｅｘ  ａｌｌｏｃａｔｏｒ）を使用して割り当てられる少なくとも一つのインデックススロットアレイ（ｉｎｄｅｘｓｌｏｔ  ａｒｒａｙ）を含んでもよい。
【００６６】
[0066]一つの実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスに対する変更をリアルタイムで実行する動作を行うようにさらに構成することができる。別の実施形態において、複数のオブジェクトのうちの少なくとも一つのオブジェクトは、ベクトルアロケータを使用して割り当てられるベクトルを含むことができる。
【００６７】
[0067]別の実施形態によれば、コンピュータシステムを使用して実施される方法が提供される。コンピュータシステムは、メモリと、メモリに結合されている少なくとも一つのプロセッサとを含む。方法は、複数のオブジェクトを含むオブジェクトストアを生成する動作と、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つのオブジェクトインデックスを生成する動作と、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つの逆インデックスを生成する動作とを含む。
【００６８】
[0068]一つの実施形態において、オブジェクトストアを生成する動作は、各々が少なくとも一つの文書を表す複数のオブジェクトを生成する動作を含む。別の実施形態において、方法は、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つの順列インデックスを生成する動作をさらに含むことができる。また別の実施形態において、方法は、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つの次元インデックスを生成する動作をさらに含むことができる。
【００６９】
[0069]本方法において、少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスを生成する動作は、共通のデータ構造から少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスを生成する動作を含んでもよい。加えて、少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスの各々を生成する動作は、インデックスアロケータを使用して割り当てられる少なくとも一つのインデックススロットアレイを割り当てる動作を含んでもよい。
【００７０】
[0070]本方法は、少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスに対する変更をリアルタイムで実行する動作をさらに含むことができる。一つの実施形態において、オブジェクトストアを生成する動作は、ベクトルアロケータを使用してベクトルを割り当てる動作を含むことができる。
【００７１】
[0071]別の実施形態において、オブジェクトネットワークモデルを実装するように構成されるコンピュータ実行可能命令シーケンスを記憶している持続性コンピュータ可読媒体が提供される。命令のコンピュータ実行可能命令は、少なくとも一つのプロセッサに、複数のオブジェクトを含むオブジェクトストアを生成する動作と、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つのオブジェクトインデックスを生成する動作と、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つの逆インデックスを生成する動作とを行うよう命令するように構成される命令を含む。
【００７２】
[0072]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、各々が少なくとも一つの文書を表す複数のオブジェクトを生成することによって、オブジェクトスコアを生成する動作を行うよう命令するようにさらに構成することができる。別の実施形態において、命令は、少なくとも一つのプロセッサに、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つの順列インデックスを生成する動作を行うよう命令するようにさらに構成することができる。また別の実施形態において、命令は、少なくとも一つのプロセッサに、複数のオブジェクトのうちのオブジェクトに対するポインタを含む少なくとも一つの次元インデックスを生成する動作を行うよう命令するようにさらに構成することができる。加えて、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、共通のデータ構造から少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスを生成することによって、少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスを生成する動作を行うよう命令するようにさらに構成されてもよい。
【００７３】
[0073]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、インデックスアロケータを使用して割り当てられる少なくとも一つのインデックススロットアレイを割り当てることによって、少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスの各々を生成する動作を行うよう命令するようにさらに構成されてもよい。別の実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも一つのオブジェクトインデックス、少なくとも一つの逆インデックス、少なくとも一つの順列インデックス、及び少なくとも一つの次元インデックスに対する変更をリアルタイムで実行する動作を行うよう命令するようにさらに構成することができる。また別の実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、ベクトルアロケータを使用してベクトルを割り当てることによって、オブジェクトストアを生成する動作を行うよう命令するようにさらに構成することができる。
【００７４】
[0074]別の実施形態によれば、システムが提供される。システムは、メモリと、メモリに結合されている少なくとも一つのプロセッサと、少なくとも一つのプロセッサによって実行可能なオブジェクトネットワークモデラ構成要素とを含む。オブジェクトネットワークモデラは、プローブオブジェクトを含むクエリメッセージを受信する動作であって、プローブオブジェクトはプローブベクトルを含む、クエリメッセージを受信する動作と、プローブベクトルを使用して符号化段階を実行する動作と、順列インデックス及び次元インデックスのうちの少なくとも一方を使用して、再現段階を実行して少なくとも一つの候補オブジェクトを識別する動作と、所定の類似度閾値を使用して適合段階を実行する動作とを行うように構成される。
【００７５】
[0075]一つの実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、プローブベクトルに対応する内部ベクトルを生成し、プローブベクトルに対応するフィンガープリントを生成することによって、符号化段階を実行する動作を行うように構成することができる。別の実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、プローブベクトルに対応するフィンガープリントを、順列インデックスに記憶されている１以上のフィンガープリントと照合することによって、再現段階を実行する動作を行うように構成することができる。
【００７６】
[0076]一つの実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、プローブベクトルに対応する内部ベクトルを、次元インデックスに記憶されている１以上の内部ベクトルと照合することによって、再現段階を実行するようにさらに構成することができる。別の実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、１以上のフィンガープリント及び１以上の内部ベクトルに対応する重複オブジェクトを削除することによって、再現段階を実行する動作を行うようにさらに構成することができる。また別の実施形態において、オブジェクトネットワークモデラ構成要素は、少なくとも部分的に、プローブベクトル、及び、少なくとも一つの候補オブジェクトに対応するベクトルを参照する類似度関数を使用して類似度基準を計算し、類似度基準が所定の類似度閾値を超えるどうかを判定することによって、適合段階を実行する動作を行うように構成することができる。その上、類似度関数は、コサイン類似度とＪａｃｃａｒｄ指数とを組み合わせることができる。さらに、オブジェクトネットワークモデラ構成要素は、メタストアを使用してアンチエイリアシング段階を実行するようにさらに構成することができる。
【００７７】
[0077]別の実施形態によれば、コンピュータシステムを使用して実施される方法が提供される。コンピュータシステムは、メモリと、メモリに結合されている少なくとも一つのプロセッサとを含む。方法は、プローブオブジェクトを含むクエリメッセージを受信する動作であって、プローブオブジェクトはプローブベクトルを含む、クエリメッセージを受信する動作と、プローブベクトルを使用して符号化段階を実行する動作と、順列インデックス及び次元インデックスのうちの少なくとも一方を使用して、再現段階を実行して少なくとも一つの候補オブジェクトを識別する動作と、所定の類似度閾値を使用して適合段階を実行する動作とを含む。
【００７８】
[0078]本方法において、符号化段階を実行する動作は、プローブベクトルに対応する内部ベクトルを生成することと、プローブベクトルに対応するフィンガープリントを生成することとを含むことができる。加えて、再現段階を実行する動作は、プローブベクトルに対応するフィンガープリントを、順列インデックスに記憶されている１以上のフィンガープリントと照合する動作を含むことができる。
【００７９】
[0079]本方法において、再現段階を実行する動作は、プローブベクトルに対応する内部ベクトルを、次元インデックスに記憶されている１以上の内部ベクトルと照合する動作をさらに含むことができる。加えて、再現段階を実行する動作は、１以上のフィンガープリント及び１以上の内部ベクトルに対応する重複オブジェクトを削除する動作をさらに含むことができる。
【００８０】
[0080]本方法において、適合段階を実行する動作は、プローブベクトル、及び、少なくとも一つの候補オブジェクトに対応するベクトルを参照する類似度関数を使用して類似度基準を計算することと、類似度基準が所定の類似度閾値を超えるどうかを判定することとを含むことができる。一つの実施形態において、類似度基準を計算する動作は、コサイン類似度とＪａｃｃａｒｄ指数とを組み合わせる動作を含むことができる。別の実施形態において、本方法は、メタストアを使用してアンチエイリアシング段階を実行する動作を含むことができる。
【００８１】
[0081]別の実施形態によれば、オブジェクトネットワークモデルを実装するように構成されるコンピュータ実行可能命令シーケンスを記憶している持続性コンピュータ可読媒体が提供される。コンピュータ実行可能命令シーケンスは、少なくとも一つのプロセッサに、プローブオブジェクトを含むクエリメッセージを受信する動作であって、プローブオブジェクトはプローブベクトルを含む、クエリメッセージを受信する動作と、プローブベクトルを使用して符号化段階を実行する動作と、順列インデックス及び次元インデックスのうちの少なくとも一方を使用して、再現段階を実行して少なくとも一つの候補オブジェクトを識別する動作と、所定の類似度閾値を使用して適合段階を実行する動作とを行うよう命令するように構成される命令を含む。
【００８２】
[0082]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、プローブベクトルに対応する内部ベクトルを生成し、プローブベクトルに対応するフィンガープリントを生成することによって、符号化段階を実行する動作を行うよう命令するようにさらに構成することができる。別の実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、プローブベクトルに対応するフィンガープリントを、順列インデックスに記憶されている１以上のフィンガープリントと照合することによって、再現段階を実行する動作を行うよう命令するようにさらに構成することができる。
【００８３】
[0083]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、プローブベクトルに対応する内部ベクトルを、次元インデックスに記憶されている１以上の内部ベクトルと照合することによって、再現段階を実行する動作を行うよう命令するようにさらに構成することができる。別の実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、１以上のフィンガープリント及び１以上の内部ベクトルに対応する重複オブジェクトを削除することによって、再現段階を実行する動作を行うよう命令するようにさらに構成することができる。また別の実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、プローブベクトル、及び、少なくとも一つの候補オブジェクトに対応するベクトルを参照する類似度関数を使用して類似度基準を計算し、類似度基準が所定の類似度閾値を逸脱するかどうかを判定することによって、適合段階を実行する動作を行うよう命令するようにさらに構成することができる。
【００８４】
[0084]一つの実施形態において、命令は、少なくとも一つのプロセッサに、少なくとも部分的に、コサイン類似度とＪａｃｃａｒｄ指数とを組み合わせることによって、類似度基準を計算する動作を行うよう命令するようにさらに構成することができる。別の実施形態において、命令は、少なくとも一つのプロセッサに、メタストアを使用してアンチエイリアシング段階を実行する動作を行うよう命令するようにさらに構成することができる。
【００８５】
[0085]別の実施形態において、オブジェクトネットワーク内で、クエリに十分に類似しているオブジェクトを識別するためのコンピューティングシステムが提供される。この実施形態において、システムは、実行可能命令を備えるメモリと、メモリに動作可能に接続されているプロセッサとを含むことができる。プロセッサは、方法を達成するために実行可能命令を実行するように構成することができる。本方法は、クエリを表すプローブオブジェクトを得る動作を含むことができる。プローブオブジェクトを表す１以上の外部ベクトルを生成することができる。プローブオブジェクトを表す１以上の内部ベクトルを、プローブオブジェクトを表す１以上の外部ベクトルに基づいて生成することができる。プローブオブジェクトを表すフィンガープリントを、プローブオブジェクトを表す１以上の内部ベクトルに基づいて生成することができる。続いて、プロセッサによって達成される方法は、第１の候補オブジェクト集合を識別するための以下の比較、すなわち、（ｉ）プローブオブジェクトを表すフィンガープリントと、オブジェクトネットワーク内の複数のオブジェクトを表す複数のフィンガープリントとの比較、及び／又は、（ｉｉ）プローブオブジェクトを表す１以上の内部ベクトルと、オブジェクトネットワーク内の複数のオブジェクトを表す複数の内部ベクトルとの比較、のうちの少なくとも一つを実施する動作を含むことができる。本方法は、プローブオブジェクトと、第１の候補オブジェクト集合内のオブジェクトの各々との間のそれぞれの第１の類似度基準を計算する動作をさらに含むことができる。それぞれの第１の類似度基準は、プローブオブジェクトを表す１以上の内部ベクトルと、第１の候補オブジェクト集合内の各オブジェクトを表す対応する内部ベクトルとを比較することによって計算することができる。最後に、この例において、本方法は、第１の候補オブジェクト集合に基づいて第２の候補オブジェクト集合を生成する動作を含むことができる。第２の候補オブジェクト集合は、第１の類似度基準が第１の所定の閾値を超えるオブジェクトを含み得る。
【００８６】
[0086]別の実施形態において、コンピュータ実施方法が提供される。この実施形態において、方法は、第１の外部オブジェクトを得る動作を含むことができる。第１の外部オブジェクトを表す１以上の外部ベクトルを生成することができる。第１の外部オブジェクトを表す１以上の内部ベクトルを、第１の外部オブジェクトを表す１以上の外部ベクトルに基づいて生成することができる。本方法は、第２の外部オブジェクトを得る動作をさらに含むことができる。第２の外部オブジェクトを表す１以上の外部ベクトルを生成することができる。第２の外部オブジェクトを表す１以上の内部ベクトルを、第２の外部オブジェクトを表す１以上の外部ベクトルに基づいて生成することができる。本方法は、第１の外部オブジェクト及び第２の外部オブジェクトが互いに明示的に関連付けられるかどうかを判定する動作をさらに含むことができる。第１の外部オブジェクト及び第２の外部オブジェクトが明示的に関連付けられるという判定に応答して、第１の外部オブジェクトと第２の外部オブジェクトとの間に明示的なアソシエーションが生成され得る。さらにまた、第１の外部オブジェクト及び第２の外部オブジェクトが黙示的に関連付けられるかどうかについて判定を行うことができる。この判定は、第１の外部オブジェクトを表す１以上の内部ベクトルと、第２の外部オブジェクトを表す１以上の内部ベクトルとを比較することによって行うことができる。第１の外部オブジェクト及び第２の外部オブジェクトが黙示的に関連付けられるという判定に応答して、第１の外部オブジェクトと第２の外部オブジェクトとの間に黙示的なアソシエーションが生成され得る。
【００８７】
[0087]これら上記の例示的な態様及び実施形態のまた他の態様、実施形態及び利点を下記に詳細に説明する。その上、上記の情報と以下の詳細な説明は両方とも、様々な態様及び実施形態の例示的な実施例に過ぎず、特許請求される態様及び実施形態の性質及び特性を理解するための概観又は枠組みを与えるように意図されている。本明細書において開示される任意の実施形態は、任意の他の実施形態と組み合わされてもよい。「一実施形態（ａｎ  ｅｍｂｏｄｉｍｅｎｔ）」、「一例（ａｎ  ｅｘａｍｐｌｅ）」、「いくつかの実施形態（ｓｏｍｅ  ｅｍｂｏｄｉｍｅｎｔｓ）」、「いくつかの例（ｓｏｍｅ  ｅｘａｍｐｌｅｓ）」、「代替的な実施形態（ａｎ  ａｌｔｅｒｎａｔｅ  ｅｍｂｏｄｉｍｅｎｔ）」、「様々な実施形態（ｖａｒｉｏｕｓ  ｅｍｂｏｄｉｍｅｎｔｓ）」、「一つの実施形態（ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ）」、「少なくとも一つの実施形態（ａｔ  ｌｅａｓｔ  ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ）」、「別の実施形態（ａｎｏｔｈｅｒ  ｅｍｂｏｄｉｍｅｎｔ）」、「他の実施形態（ｏｔｈｅｒ  ｅｍｂｏｄｉｍｅｎｔｓ）」、「この実施形態及び他の実施形態（ｔｈｉｓ  ａｎｄ  ｏｔｈｅｒ  ｅｍｂｏｄｉｍｅｎｔｓ）」などが参照されている場合、これらの参照は必ずしも相互に排他的ではなく、当該実施形態に関連して記載されている特定の特徴、構造、又は特性が少なくとも一つの実施形態に含まれ得ることを示すように意図されている。本明細書においてそのような用語が見られる場合、これらの用語は必ずしもすべてが同じ実施形態を参照しているとは限らない。
【００８８】
[0088]原寸に比例して描かれるようには意図されていない添付の図面を参照しながら、少なくとも一つの実施形態の様々な態様を下記に説明する。図面は、様々な態様及び実施形態の例示及びさらなる理解を与えるために含まれており、本明細書に組み込まれ、本明細書の一部分を構成するが、任意の特定の実施形態の限定を規定するものとしては意図されていない。図面は、本明細書の残りの部分とともに、記載されている態様及び実施形態並びに特許請求される態様及び実施形態を説明する役割を果たす。図面において、様々な図面に示されている同一の構成要素又はほぼ同一の構成要素の各々は、同様の参照符号によって表されている。明瞭にする目的で、すべての構成要素がすべての図面において符号を付されているとは限らない場合がある。
【図面の簡単な説明】
【００８９】
【図１】分散コンピュータシステムのブロック図である。
【図２】オブジェクトネットワークをモデル化するためのシステムを示すブロック図である。
【図３】オブジェクトネットワーク内のオブジェクト間の様々な関係を定義するエンティティ関係図である。
【図４】オブジェクトネットワーク内のオブジェクト間の様々な関係を定義するエンティティ関係図である。
【図５】例示的なオブジェクトネットワークのエンティティ関係図である。
【図６】オブジェクトを重心にアタッチ（ａｔｔａｃｈ）するためのプロセスを示す一連のエンティティ関係図のうちの一つの図である。
【図７】オブジェクトを重心にアタッチするためのプロセスを示す一連のエンティティ関係図のうちの一つの図である。
【図８】オブジェクトを重心にアタッチするためのプロセスを示す一連のエンティティ関係図のうちの一つの図である。
【図９】例示的なオブジェクトネットワークのエンティティ関係図である。
【図１０】例示的なオブジェクトネットワークのエンティティ関係図である。
【図１１】例示的なオブジェクトネットワークのエンティティ関係図である。
【図１２】内部ベクトルを示すデータ構造図である。
【図１３】ベクトル符号化プロセスを示すシーケンス線図である。
【図１４】コサイン類似度計算を示すグラフ図である。
【図１５】順列インデックスのセットを示すデータ構造図である。
【図１６】フィンガープリント生成プロセスを示すシーケンス線図である。
【図１７】ＬＳＨ生成プロセスを示すシーケンス線図である。
【図１８】データ低減プロセスを示すシーケンス線図である。
【図１９】問い合わせプロセスを示すシーケンス線図である。
【図２０】再現プロセスプロセスを示す修正ベン図である。
【図２１】類似度再現プロセスに関与する構成要素を強調したブロック図である。
【図２２】類似度再現プロセスを示すシーケンス線図である。
【図２３】ベクトルアロケータを示すデータエンティティ図である。
【図２４】次元再現プロセスに関与する構成要素を強調したブロック図である。
【図２５】統合再現プロセスに関与する構成要素を強調したブロック図である。
【図２６】適合プロセスを示す修正ベン図である。
【図２７】アンチエイリアシングプロセスを示す修正ベン図である。
【図２８】システム構成の変動を考慮したクエリ精度のベン図である。
【図２９】システム内のデータ構成要素間の接続を示すデータエンティティ図である。
【図３０−１】システム内のオブジェクトストアデータ構成要素間の接続を示すデータエンティティ図である。
【図３０−２】システム内のオブジェクトストアデータ構成要素間の接続を示すデータエンティティ図である。
【図３１−１】システム内のインデックス構成要素を示すデータ構造図である。
【図３１−２】システム内のインデックス構成要素を示すデータ構造図である。
【図３２−１】システム内のオブジェクトストアデータ構成要素間の接続を示すデータエンティティ図である。
【図３２−２】システム内のオブジェクトストアデータ構成要素間の接続を示すデータエンティティ図である。
【図３３−１】システム内のオブジェクトストア構成要素を示すデータ構造図である。
【図３３−２】システム内のオブジェクトストア構成要素を示すデータ構造図である。
【図３４】システム内のオブジェクトストア構成要素を示すデータ構造図である。
【図３５】システム内のベクトルアロケータの概略図である。
【図３６】システム内のインデックスアロケータの概略図である。
【図３７】例示的なオブジェクトネットワークのエンティティ関係図である。
【図３８】グラフィックス処理ユニット（ＧＰＵ）物理アーキテクチャのブロック図である。
【図３９】ベクトル符号化プロセスを示す流れ図である。
【図４０】フィンガープリント生成プロセスを示す流れ図である。
【図４１】類似度再現プロセスを示す流れ図である。
【図４２】オブジェクトを重心にアタッチするためのプロセスを示す流れ図である。
【発明を実施するための形態】
【００９０】
[0129]いくつかの実施形態は、近似照合機能を有するデータ間関連オブジェクトクラスタリングネットワークを含むシムアレイベクトルインテリジェンスネットワーク（Ｓｉｍａｒｒａｙ  Ｖｅｃｔｏｒ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  Ｎｅｔｗｏｒｋ）を実装する。これらの実施形態において、シムアレイオブジェクト（Ｓｉｍａｒｒａｙ  ｏｂｊｅｃｔ）（本明細書においては「オブジェクト」と称する）の挿入及び削除、並びに、オブジェクトリンクの形成及び破壊は、オフラインインデックス付けの必要なしにリアルタイムで行われる。いくつかの実施形態は、高性能動作のためにメモリに基づく。オブジェクト耐久性が、すべてのデータ修正動作のディスクライトスルーを介して促進される。類似度照合が、ベクトルフィンガープリンティング、次元インデックス付け、及びベクトル空間モデルフィルトレーションの機能を組み合わせることを通じて達成される。オブジェクトネットワークは、既存の外部接続情報を適用することによって明示的に、また、オブジェクト又はオブジェクトクラスタの類似度分析を通じて黙示的に形成される。
【００９１】
[0130]本明細書において説明されている方法及びシステムの例は、以下の説明において記載されているか、又は、添付の図面に示されている構成要素の構造及び構成の詳細への適用に限定されない。本方法及びシステムは、他の実施形態における実装、又は、様々な方法で実践若しくは実行されることが可能である。本明細書において、特定の実施形態の例は、例示を目的として与えられており、限定するようには意図されていない。特に、任意の１以上の例に関連して説明されている動作、構成要素、要素及び特徴は、任意の他の例における同様の役割から除外されるようには意図されていない。
【００９２】
[0131]さらに、本明細書において使用されている表現専門用語は説明を目的とするものであり、限定として考えられるべきではない。単数形において参照されている、本明細書におけるシステム及び方法の例、実施形態、構成要素、要素又は動作の任意の参照はまた、複数を含む実施形態をも包含し、本明細書における任意の実施形態、構成要素、要素又は動作に対する複数における任意の参照はまた、単数のみを含む実施形態をも参照してもよい。単数形又は複数形における参照は、現在開示されているシステム若しくは方法、それらのシステム若しくは方法の構成要素、動作、又は要素を限定するようには意図されていない。本明細書において、「含む（ｉｎｃｌｕｄｉｎｇ）」、「備える（ｃｏｍｐｒｉｓｉｎｇ）」、「有する（ｈａｖｉｎｇ）」、「含有する（ｃｏｎｔａｉｎｉｎｇ）」、「伴う（ｉｎｖｏｌｖｉｎｇ）」、及びそれらの語の変化形が使用されている場合、これは、それらの語の後にリストされている項目及びそれらの項目の均等物並びに追加の項目を包含するように意図されている。「又は（ｏｒ）」に対する参照は、「又は」を使用して記載されている任意の事項が、単数、２つ以上、及びすべての記載されている事項のいずれかを示すことができるように、包括的に解釈され得る。加えて、本明細書と参照により本明細書に組み込まれている文献との間で用語が一貫性なく使用されている場合、組み込まれている引用文献における用語の使用は、本命差書における用語の使用に対する補足であり、共存できない不一致については、本明細書における用語の使用が優先する。
【００９３】
コンピュータシステム
[0132]図１及び図２９に関連して下記に説明するように、本明細書に記載されている様々な態様及び機能は、１以上のコンピュータシステム内で実行している専用ハードウェア又はソフトウェア構成要素として実装することができる。現在使用されているコンピュータシステムには多くの例がある。これらの例は、中でも、ネットワークアプライアンス、パーソナルコンピュータ、ワークステーション、メインフレーム、ネットワーク接続されたクライアント、サーバ、メディアサーバ、アプリケーションサーバ、データベースサーバ、及びウェブサーバを含む。コンピュータシステムの他の例は、携帯電話及び携帯情報端末のようなモバイルコンピューティングデバイス、並びに、負荷分散装置、ルータ、及びスイッチのようなネットワーク機器を含み得る。さらに、態様は、単一のコンピュータシステム上に位置してもよく、又は、１以上の通信ネットワークに接続されている複数のコンピュータシステムにわたって分散されてもよい。
【００９４】
[0133]たとえば、様々な態様、機能、及びプロセスが、１以上のクライアントコンピュータにサービスを提供するか、又は、分散システムの一部分として全体的なタスクを実施するように構成される１以上のコンピュータシステムの間で分散されてもよい。加えて、態様は、様々な機能を実施する１以上のサーバシステムの間で分散される構成要素を含むクライアント−サーバ又は多段構成システム上で実施されてもよい。結果として、実施形態は、いかなる特定のシステム又はシステムグループ上での実施にも限定されない。さらに、態様、機能、及びプロセスは、ソフトウェア、ハードウェア又はファームウェア、又はそれらの任意の組み合わせで実装されてもよい。したがって、態様、機能、及びプロセスは、様々なハードウェア及びソフトウェア構成を使用して方法、動作、システム、システム要素及び構成要素内で実装されてもよく、実施例は、いかなる特定の分散アーキテクチャ、ネットワーク、又は通信プロトコルにも限定されない。
【００９５】
[0134]ここで図１を参照すると、様々な態様及び機能が実践される分散コンピュータシステムのブロック図が示されている。図示されているように、分散コンピュータシステムは、情報を交換する１以上のコンピュータシステムを含む。より詳細には、分散コンピュータシステムは、コンピュータシステム１０２、１０４、及び１０６を含む。図示されているように、コンピュータシステム１０２、１０４、及び１０６は、通信ネットワーク１０８によって相互接続されており、通信ネットワーク１０８を通じてデータを交換することができる。ネットワーク１０８は、コンピュータシステムがデータを交換することができる任意の通信ネットワークを含んでもよい。ネットワーク１０８を使用してデータを交換するために、コンピュータシステム１０２、１０４、及び１０６並びにネットワーク１０８は、中でも、ファイバーチャネル、トークンリング、Ｅｔｈｅｒｎｅｔ、無線Ｅｔｈｅｒｎｅｔ、Ｂｌｕｅｔｏｏｔｈ、ＩＰ、ＩＰＶ６、ＴＣＰ／ＩＰ、ＵＤＰ、ＤＴＮ、ＨＴＴＰ、ＦＴＰ、ＳＮＭＰ、ＳＭＳ、ＭＭＳ、ＳＳ７、ＪＳＯＮ、ＳＯＡＰ、ＣＯＲＢＡ、ＲＥＳＴ、及びウェブサービスを含む様々な方法、プロトコル及び規格を使用することができる。データ伝送が安全であることを保証するために、コンピュータシステム１０２、１０４、及び１０６は、たとえば、ＳＳＬ又はＶＰＮ技術を含む様々な安全対策を使用してネットワーク１０８を介してデータを送信することができる。分散コンピュータシステムは３つのネットワーク接続されたコンピュータシステムを示しているが、分散コンピュータシステムはそのようには限定されず、任意の媒体及び通信プロトコルを使用してネットワーク接続された任意の数のコンピュータシステム及びコンピューティングデバイスを含んでもよい。
【００９６】
[0135]図１に示すように、コンピュータシステム１０２は、プロセッサ１１０と、メモリ１１２と、相互接続要素１１４と、インターフェース１１６と、データ記憶要素１１８とを含む。本明細書に開示されている態様、機能、及びプロセスのうちの少なくともいくつかを実装するために、プロセッサ１１０は、操作されたデータを結果としてもたらす一連の命令を実施する。プロセッサ１１０は、任意のタイプのプロセッサ、マイクロプロセッサ又はコントローラであってもよい。加えて、単一のプロセッサのみが図示されているが、いくつかの実施形態において、本明細書に開示されている技法及びシステムは、各プロセッサが１以上のコアを有し得る、複数のプロセッサの使用を含んでもよいことが、当業者には諒解されよう。例示的なプロセッサは、Ｉｎｔｅｌ  Ｘｅｏｎ、Ｉｔａｎｉｕｍ、Ｃｏｒｅ、Ｃｅｌｅｒｏｎ、若しくはＰｅｎｔｉｕｍプロセッサ、ＡＭＤ  Ｏｐｔｅｒｏｎプロセッサ、Ａｐｐｌｅ  Ａ４若しくはＡ５プロセッサ、Ｓｕｎ  ＵｌｔｒａＳＰＡＲＣプロセッサ、ＩＢＭ  Ｐｏｗｅｒ５＋プロセッサ、ＩＢＭメインフレームチップ、又は量子コンピュータのような市販のプロセッサを含んでもよい。加えて、いくつかの実施形態において、プロセッサはＧＰＧＰＵであってもよい。また別の実施形態において、プロセッサは、上述したＡＶＸ−５１２拡張を実行するように構成されるプロセッサであってもよい。プロセッサ１１０は、相互接続要素１１４によって、１以上のメモリデバイス１１２を含む他のシステム構成要素に接続されている。
【００９７】
[0136]メモリ１１２は、コンピュータシステム１０２の動作中にプログラム（たとえば、プロセッサ１１０によって実行可能であるようにコード化されている命令シーケンス）及びデータを記憶する。したがって、メモリ１１２は、ダイナミックランダムアクセスメモリ（「ＤＲＡＭ」）又はスタティックメモリ（「ＳＲＡＭ」）のような、相対的に性能の高い、揮発性ランダムアクセスメモリであってもよい。しかしながら、メモリ１１２は、ディスクドライブ又は他の不揮発性記憶デバイスのような、データを記憶するための任意のデバイスを含んでもよい。様々な実施例は、本明細書に開示されている機能を実施するために、メモリ１１２を、特定化された、場合によっては特有の構造になるように編成してもよい。これらのデータ構造は、特定のデータの値及びデータ型を記憶するようなサイズにされ、編成されてもよい。
【００９８】
[0137]コンピュータシステム１０２の構成要素は、相互接続要素１１４のような相互接続要素によって結合されている。相互接続要素１１４は、ＩＤＥ、ＳＣＳＩ、ＰＣＩ及びＩｎｆｉｎｉＢａｎｄのような専用又は標準コンピューティングバス技術に適合した１以上の物理バスのような、システム構成要素間の任意の通信結合を含んでもよい。相互接続要素１１４は、命令及びデータを含む通信が、コンピュータシステム１０２のシステム構成要素間で交換されることを可能にする。
【００９９】
[0138]コンピュータシステム１０２はまた、入力デバイス、出力デバイス、及び組み合わせ入出力デバイスのような、１以上のインターフェースデバイス１１６をも含む。インターフェースデバイスは、入力を受信するか、又は、出力を与えることができる。より詳細には、出力デバイスは、外部に提示するために情報をレンダリングすることができる。入力デバイスは、外部ソースから情報を受け入れることができる。インターフェースデバイスの例は、キーボード、マウスデバイス、トラックボール、マイクロホン、タッチスクリーン、印刷デバイス、表示画面、スピーカ、ネットワークインターフェースカードなどを含む。インターフェースデバイスは、コンピュータシステム１０２が、情報を交換し、ユーザ及び他のシステムのような外部エンティティと通信することを可能にする。
【０１００】
[0139]データ記憶要素１１８は、プロセッサ１１０によって実行されるプログラム又は他のオブジェクトを定義する命令が記憶されている、コンピュータ可読且つ書き込み可能な不揮発性又は持続性のデータ記憶媒体を含む。データ記憶要素１１８はまた、媒体の上又は中に記録され、プログラムの実行中にプロセッサ１１０によって処理される情報をも含むことができる。より詳細には、情報は、特に記憶容量を節約するか又はデータ交換性能を増大させるように構成される１以上のデータ構造に記憶することができる。命令は、符号化信号として持続的に記憶することができ、命令は、プロセッサ１１０に、本明細書に記載されている機能のいずれかを実施させることができる。媒体は、中でも、たとえば、光ディスク、磁気ディスク又はフラッシュメモリであってもよい。動作時、プロセッサ１１０又は何らかの他のコントローラは、データが不揮発性記録媒体から、メモリ１１２のような、プロセッサ１１０によってデータ記憶要素１１８に含まれている記憶媒体よりも高速に情報にアクセスすることを可能にする別のメモリに読み出されるようにする。メモリは、データ記憶要素１１８又はメモリ１１２内に位置してもよいが、プロセッサ１１０はメモリ内でデータを操作し、その後、処理が完了した後に、データ記憶要素１１８と関連付けられている記憶媒体にデータをコピーする。様々な構成要素が記憶媒体と他のメモリ要素との間のデータ移動を管理することができ、実施例は、特定のデータ管理構成要素に限定されない。さらに、実施例は、特定のメモリシステム又はデータ記憶システムに限定されない。
【０１０１】
[0140]コンピュータシステム１０２は、例として、様々な態様及び機能を実践することができる一つのタイプのコンピュータシステムとして示されているが、態様及び機能は、図１に示すようなコンピュータシステム１０２で実装されるようには限定されない。図１に示すものとは異なるアーキテクチャ及び構成要素を有する１以上のコンピュータで様々な態様及び機能が実践されてもよい。たとえば、コンピュータシステム１０２は、本明細書に開示されている特定の動作を実施するように調整されている特定用途向け集積回路（「ＡＳＩＣ」）のような、特別にプログラムされた専用ハードウェアを含んでもよい。一方で、別の実施例は、Ｍｏｔｏｒｏｌａ  ＰｏｗｅｒＰＣプロセッサを用いてＭＡＣ  ＯＳ  Ｓｙｓｔｅｍ  Ｘを作動させるいくつかの汎用コンピューティングデバイス、及び、専用ハードウェア及びオペレーティングシステムを作動させるいくつかの専用コンピューティングデバイスのグリッドを使用して同じ機能を実施してもよい。
【０１０２】
[0141]コンピュータシステム１０２は、コンピュータシステム１０２に含まれるハードウェア要素の少なくとも一部分を管理するオペレーティングシステムを含むコンピュータシステムであってもよい。いくつかの実施例において、プロセッサ１１０のようなプロセッサ又はコントローラが、オペレーティングシステムを実行する。実行され得る特定のオペレーティングシステムの例は、Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎから入手可能な、Ｗｉｎｄｏｗｓ  ＮＴ、Ｗｉｎｄｏｗｓ  ２０００（Ｗｉｎｄｏｗｓ  ＭＥ）、Ｗｉｎｄｏｗｓ  ＸＰ、Ｗｉｎｄｏｗｓ  Ｖｉｓｔａ若しくはＷｉｎｄｏｗｓ  ７オペレーティングシステムのようなＷｉｎｄｏｗｓベースのオペレーティングシステム、Ａｐｐｌｅ  Ｃｏｍｐｕｔｅｒから入手可能なＭＡＣ  ＯＳ  Ｓｙｓｔｅｍ  Ｘオペレーティングシステム若しくはｉＯＳオペレーティングシステム、多くのＬｉｎｕｘベースのオペレーティングシステム配布、たとえば、Ｒｅｄ  Ｈａｔ  Ｉｎｃ．から入手可能なＥｎｔｅｒｐｒｉｓｅ  Ｌｉｎｕｘオペレーティングシステム、Ｏｒａｃｌｅ  Ｃｏｒｐｏｒａｔｉｏｎから入手可能なＳｏｌａｒｉｓオペレーティングシステム、又は、様々なソースから入手可能なＵＮＩＸオペレーティングシステムを含む。多くの他のオペレーティングシステムが使用されてもよく、実施例は、いかなる特定のオペレーティングシステムにも限定されない。
【０１０３】
[0142]プロセッサ１１０及びオペレーティングシステムはともに、高度なプログラミング言語によるアプリケーションプログラムが書かれるコンピュータプラットフォームを定義する。これらのコンポーネントアプリケーションは、通信プロトコル、たとえば、ＴＣＰ／ＩＰを使用して通信ネットワーク、たとえば、インターネットを介して通信する実行可能な中間のバイトコード又は解釈済みコードであってもよい。同様に、態様は、．Ｎｅｔ、ＳｍａｌｌＴａｌｋ、Ｊａｖａ、Ｃ＋＋、Ａｄａ、Ｃ＃（Ｃシャープ）、Ｐｙｔｈｏｎ、又はＪａｖａＳｃｒｉｐｔのようなオブジェクト指向型プログラミング言語を使用して実装されてもよい。他のオブジェクト指向型プログラミング言語も使用されてもよい。代替的に、関数型プログラミング言語、スクリプトプログラミング言語、又は論理型プログラミング言語が使用されてもよい。
【０１０４】
[0143]加えて、様々な態様及び機能は、プログラムによらない環境において実装されてもよい。たとえば、ＨＴＭＬ、ＸＭＬ又は他のフォーマットで作成された文書が、ブラウザプログラムのウィンドウで見たときに、グラフィカルユーザインターフェースの態様をレンダリングするか、又は、他の機能を実施することができる。さらに、様々な実施例が、プログラムによる要素若しくはプログラムによらない要素、又は、それらの要素の任意の組み合わせとして実装されてもよい。たとえば、ウェブページはＨＴＭＬを使用して実装されてもよく、一方で、ウェブページ内から呼び出されるデータオブジェクトは、Ｃ＋＋で書かれてもよい。したがって、実施例は特定のプログラミング言語に限定されず、任意の適切なプログラミング言語が使用されてもよい。したがって、本明細書に開示されている機能構成要素は、本明細書に記載されている機能を実施するように構成される多種多様な要素（たとえば、専用ハードウェア、実行可能コード、データ構造又はオブジェクト）を含んでもよい。
【０１０５】
[0144]いくつかの実施例において、本明細書に開示されている構成要素は、構成要素によって実施される機能に影響を与えるパラメータを読み出すことができる。これらのパラメータは、揮発性メモリ（ＲＡＭなど）又は不揮発性メモリ（磁気ハードドライブなど）を含む任意の形態の適切なメモリに物理的に記憶されてもよい。加えて、これらのパラメータは、専用データ構造（ユーザモードアプリケーションによって定義されるデータベース又はファイルなど）又は一般的に共有されているデータ構造（オペレーティングシステムによって定義されるアプリケーションレジストリなど）に論理的に記憶されてもよい。加えて、いくつかの実施例は、外部エンティティがこれらのパラメータを修正し、これにより、その構成要素の挙動を構成することを可能にするシステムとユーザインターフェースの両方を提供する。
【０１０６】
オブジェクトモデル化システム
[0145]様々な実施形態は、オブジェクト及びオブジェクト間のアソシエーションをモデル化するように特に構成される１以上のコンピュータシステムを利用する。図２は、これらの実施形態のうちの一つ、すなわち、オブジェクトモデル化システムを示している。図示されているように、図２は、オブジェクトネットワークモデラ２０２と、ベクタライザ（ｖｅｃｔｏｒｉｚｅｒ）２０４と、外部オブジェクトデータストア２０６と、アプリケーション２０８とを含む。オブジェクトネットワークモデラ２０２は、オブジェクトマネージャ２１０と、インデックスマネージャ２１２と、オブジェクトストア２１４と、インデックスストア２１６と、クエリエンジン２１８とを含む。オブジェクトネットワークモデラ２０２、ベクタライザ２０４、外部オブジェクトデータストア２０６、及びアプリケーション２０８は、図１を参照して上述したコンピュータシステムのような、１以上のコンピュータシステムを使用して実装されてもよい。図２に示すように、オブジェクトネットワークモデラ２０２、ベクタライザ２０４、外部オブジェクトデータストア２０６、及びアプリケーション２０８は、１以上の接続２２０を介して情報を交換（たとえば、送信又は受信）する。接続２２０は、コンピュータ構成要素が情報を交換することができる任意の通信デバイスを含んでもよい。たとえば、接続２２０は、ローカルバス接続、ＬＡＮ接続、アプリケーション・プログラムインターフェース、ソケット、及び、コンピュータ構成要素間の情報の流れを促進する他のデータ通信デバイスを含んでもよい。
【０１０７】
[0146]いくつかの実施形態において、アプリケーション２０８は、外部オブジェクトデータストア２０６によって記述されるオブジェクト間の関係を探索するために、オブジェクトネットワークモデラ２０２とインターフェースするように構成される。アプリケーション２０８の例は、他のシステムの中でも、類語集、辞書、百科事典、データマイニングシステム、ビジネスインテリジェンスシステム、及びインターネット検索エンジンのような、オブジェクト間のアソシエーションの識別及び探索から値を導出するアプリケーションを含む。これらの実施形態において、アプリケーション２０８は、アプリケーションプログラムインターフェース（ＡＰＩ）のような、オブジェクトネットワークモデラ２０２によって露出されるインターフェースを介してオブジェクトネットワークモデラ２０２とインターフェースする。ＡＰＩを介して、アプリケーション２０８はオブジェクトネットワークモデラ２０２に様々なメッセージを送信する。これらのメッセージは、オブジェクトネットワークモデラ２０２に対する、図２９を参照して下記にさらに説明されるデータ構造のような、データ構造セットにデータを投入することを求める要求を含むことができる。メッセージはまた、オブジェクトネットワークモデラ２０２に対する、これらのデータ構造に対するクエリを実行することを求める要求をも含むことができる。いくつかの実施形態において、オブジェクトネットワークモデラ２０２は、これらのメッセージを受信したことに応答して、これらのＡＰＩメッセージを処理するように構成される。このように、オブジェクトネットワークモデラ２０２は、下記にさらに説明するように、オブジェクトネットワークを作成、維持、及び問い合わせすることによって、アプリケーション２０８の動作を支援する。
【０１０８】
[0147]図２によって示す一つの実施形態において、外部オブジェクトデータストア２０６は、アプリケーション２０８による分析の対象となっている外部オブジェクトを記述する情報を含む。これらの外部オブジェクトの例は、他のオブジェクトの中でも、単語、概念、人、製品、及び文書を含む。外部オブジェクトデータストア２０６は、フラットファイル、インデックスファイル、階層型データベース、関係型データベース又はオブジェクト指向型データベースを含む、コンピュータ可読媒体に情報を記憶することが可能な任意の論理的構成の形態で実装されてもよい。
【０１０９】
[0148]他の実施形態において、ベクタライザ２０４は、外部オブジェクトデータストアに記憶されている未加工データからベクトルを生成する。これは、当該技術分野においてベクトル化として知られているプロセスである。ベクタライザ２０４によって生成されるベクトルは、外部オブジェクトを記述する情報を含む。良好なベクタライザは、未加工データから重要な特徴を抽出し、これにより、高次元空間において疎ベクトルを作成することが可能である。一般的なタイプのベクタライザは、一片のフリーテキストからキーワード及び重要な語句（ｎグラム）を抽出するものである。他のベクタライザは、画像、メディア、又は、任意の他の形態の情報を特徴セットとして表すベクトルを生成することができる。
【０１１０】
[0149]いくつかの実施形態によれば、オブジェクトマネージャ２１０は、オブジェクトネットワークモデラ２０２によって処理されるオブジェクトを作成、更新、及び消去するように構成される。これらの実施形態において、オブジェクトマネージャ２１０は、ベクタライザ２０４から外部ベクトルを受信し、外部ベクトルを内部ベクトルとして符号化し、内部ベクトルをフィンガープリントに要約し、このフィンガープリントの情報を使用してオブジェクトストア２１４を維持する。いくつかの実施形態において、オブジェクトマネージャ２１０は、これら上記の動作を要求するメッセージを受信したことに応答して、これらの動作を実行する。オブジェクトマネージャは、そのようなメッセージをアプリケーション２０８、ベクタライザ２０４、構成ファイル、又は何らかの他のソースから受信し得る。オブジェクトマネージャ２１０が実施するように構成されるプロセスの例は、さらに説明される。
【０１１１】
[0150]いくつかの実施形態において、インデックスマネージャ２１２は、インデックスストア２１６に記憶されるインデックスストアを作成、更新、及び消去するように構成される。これらの実施形態において、インデックスマネージャ２１２は、オブジェクトがオブジェクトストア２１４内で記憶又は修正されるときに、インデックスをリアルタイムで構築及び更新する。インデックスマネージャ２１２によって実施されるプロセス及び操作されるデータの例は、下記にさらに説明される。
【０１１２】
[0151]いくつかの実施形態において、オブジェクトストア２１４は、オブジェクトマネージャ２１０によって作成及び操作されるオブジェクトを記憶するように構成される。これらの実施形態において、オブジェクトストア２１４は、メモリ断片化を最小限に抑え、性能を最大限に引き出すように特別に調整されているデータ構造を含む。オブジェクトストア２１４に含まれる構造及びデータの例は、下記にさらに説明される。
【０１１３】
[0152]いくつかの実施形態において、インデックスストア２１６は、インデックスマネージャ２１２によって作成及び操作されるインデックスを記憶するように構成される。これらの実施形態において、インデックスストア２１６は、メモリ断片化を最小限に抑え、性能を最大限に引き出すように特別に調整されているデータ構造を含む。インデックスストア２１６に含まれる構造及びデータの例は、下記にさらに説明される。
【０１１４】
[0153]いくつかの実施形態において、クエリエンジン２１８は、クエリ要求を含むクエリプロセスメッセージを処理するように構成される。これらのクエリメッセージは、関連付けられるオブジェクトがそれについて探索される１以上のプローブオブジェクトを記述する情報を含むことができる。クエリメッセージを受信したことに応答して、クエリエンジン２１８は、クエリメッセージを処理する。クエリエンジン２１８によって操作されるプロセス及びデータの例は、下記にさらに説明される。
【０１１５】
シムアレイオブジェクト及びオブジェクトネットワーク
[0154]様々な実施形態において、オブジェクトマネージャは、オブジェクトネットワークを実装するように構成される。このオブジェクトネットワークは、文書、人、製品、ウェブページなどのような実世界のエンティティを表す１以上のオブジェクトを含むことができる。オブジェクトネットワーク内のオブジェクトの各々は、オブジェクトによって表される実世界のエンティティを記述する属性セットを含むことができる。表１は、これらの属性のいくつかの例をリストしている。
【表１】
2019053772.tif 000003
【０１１６】
[0155]いくつかの実施形態において、オブジェクトマネージャは、たとえば、ＳＵＢＩＤ参照を介して、オブジェクトネットワーク内でオブジェクトを互いと関連付ける。これらの実施形態において、オブジェクトマネージャは、たとえば、オブジェクトインデックス及び逆インデックスを介して、オブジェクトネットワーク内でオブジェクトをトラバースする。オブジェクトマネージャは、少なくとも２つの個別の方法で、すなわち、（ｉ）（たとえば、以前に確立されている関係を活用することによって）実世界から導出されるリンクから明示的に、及び、（ｉｉ）類似度分析を介して「オブジェクトの性質」から黙示的に、オブジェクトを関連付けることができる。
【０１１７】
[0156]たとえば、オブジェクトマネージャは、以下の属性を用いて２つのオブジェクトをインスタンス化することによって、オブジェクトＡ（Ａ）をオブジェクトＢ（Ｂ）と関連付けるオブジェクトネットワークを作成することができる。
【表２】
2019053772.tif 000004
【０１１８】
[0157]オブジェクトマネージャは、オブジェクトネットワークが存在するためにＡがＢと関連付けられる理由を記録する必要はなく、オブジェクトマネージャは、その理由を、以下の値を有するＬＮＫ属性として内部的に記録することができる。
ＬＮＫ＝ＩＭＰＬＩＣＩＴ（黙示的）    「オブジェクトの性質」に起因してＡ→Ｂ、すなわち、Ａ及びＢは類似している
ＬＮＫ＝ＥＸＰＬＩＣＩＴ（明示的）    オブジェクト関係の外部予備知識に起因してＡ→Ｂ
ＬＮＫ＝ＤＵＡＬ（二重）    外部関係及び類似度に起因してＡ→Ｂ
【０１１９】
[0158]したがって、一実施例において、オブジェクトマネージャは、以下のように、外部予備知識に起因してＡがＢと明示的に関連付けられていることの最小限の表現を作成する。
【表３】
2019053772.tif 000005
【０１２０】
[0159]いくつかの実施形態において、オブジェクトマネージャは、同様に（たとえば、ＬＮＫ属性を使用して）黙示的な又は二重のアソシエーションを記録する。しかしながら、黙示的な又は二重のアソシエーションの発見は、上述したように、ベクトル及びフィンガープリントを使用した類似度分析を必要とする。オブジェクトマネージャは、以下のように、オブジェクト特徴の近似照合に起因してＡがＢと黙示的に関連付けられることの最小限の表現を作成することができる。
【表４】
2019053772.tif 000006
【０１２１】
[0160]代替的に、オブジェクトマネージャは、ＡがＢと黙示的且つ明示的に関連付けられることの最小限の表現を作成してもよい。
【表５】
2019053772.tif 000007
【０１２２】
[0161]図３は、オブジェクトマネージャがオブジェクト間の関係に基づいて作成するように構成される、オブジェクトアソシエーションの例をさらに示す。図３に示すように、これらのアソシエーションは、一方向性黙示的アソシエーション、一方向性明示的アソシエーション、一方向性明示的且つ黙示的アソシエーション、双方向性黙示的アソシエーション、双方向性明示的アソシエーション、双方向性明示的且つ黙示的アソシエーション、及びＮＵＬＬアソシエーションを含む。図３は、図示されているように、図形表現とオブジェクト表の両方を使用してこれらのアソシエーションの各々を示す。
【０１２３】
[0162]他の実施形態において、オブジェクトマネージャは、ベクトル型（ＶＥＣ）を有するオブジェクトをインスタンス化するように構成される。図４は、これらのベクトル型の例を示す。図４に示すように、ベクトル型は、標準ベクトル型、重心ベクトル型、及びＮＵＬＬベクトル型を含む。図４は、図示されているように、図形表現とオブジェクト表の両方を使用してこれらのベクトル型の各々を示す。
【０１２４】
[0163]上述したように、ベクトル及びベクトル型は、オブジェクトネットワークモデラ構成要素によって、黙示的オブジェクトアソシエーションを発見するために利用される。明示的アソシエーションは、オブジェクトがベクトル値又はベクトル型値を有することを必要とせず、それゆえ、オブジェクトは、要素を有していないベクトル及びＮＵＬＬのベクトル型値を有してもよいことが諒解される。図５は、オブジェクトマネージャによって作成及び管理することができるオブジェクトネットワークの一例を示す。図５に示すように、オブジェクトネットワークは、重心オブジェクトＣＡ、ＣＢ、及びＣＤを含む。ＣＡはＴＥＲＭＩＮＡＬオブジェクトでもあり、他のオブジェクトとのアソシエーションを含まない。ＣＢはＣＤとの明示的双方向性アソシエーションを含み、ＣＤはＣＢとの明示的双方向性アソシエーションを含む。
【０１２５】
[0164]図５の例において、オブジェクトＡ１、Ａ２、及びＡ３の各々は、ＣＡとの黙示的一方向性アソシエーションを含む標準ベクトルオブジェクトである。Ａ３は、Ｂ３との黙示的一方向性アソシエーション、Ｂ２との二重双方向性アソシエーション、及び、Ｎ１との明示的一方向性アソシエーションを含む。Ｎ１は、Ｎ２及びＮ３との明示的一方向性アソシエーションを含むＮＵＬＬベクトルオブジェクトである。Ｎ２及びＮ３は両方ともＮＵＬＬベクトル、ＴＥＲＭＩＮＡＬオブジェクトである。オブジェクトＢ１、Ｂ２、Ｂ３、及びＢ４の各々は、ＣＢとの黙示的一方向性アソシエーションを含む標準ベクトルオブジェクトである。
【０１２６】
[0165]図５の例において、オブジェクトＤ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５、及びＤ６の各々は、ＣＢとの黙示的一方向性アソシエーションを含む標準ベクトルオブジェクトである。Ｄ６はまた、Ｎ４との明示的一方向性アソシエーション、Ｎ５との二重一方向性アソシエーション、及び、Ｎ６との黙示的一方向性アソシエーションを含む。Ｎ４はＮＵＬＬベクトル、ＴＥＲＭＩＮＡＬオブジェクトである。Ｎ５及びＮ６は両方とも標準ベクトル、ＴＥＲＭＩＮＡＬオブジェクトである。
【０１２７】
[0166]いくつかの実施形態において、オブジェクトマネージャは、他のオブジェクトのグループ又はクラスタを表す重心オブジェクトを維持するように構成される。これらの実施形態において、重心オブジェクトのベクトルは、一方向性アソシエーション又は双方向性アソシエーションを介して重心オブジェクトにリンクされているオブジェクトのベクトルの関数である。たとえば、重心のベクトルは、（切り捨て制限まで）平均の大きさによってソートされた重心にリンクされているオブジェクトの次元を含むことができる。他の構成要素（たとえば、アプリケーション層構成要素）による重心オブジェクトの維持を容易にするために、オブジェクトマネージャは、オブジェクトマネージャがそれによって他の構成要素からクリスタリングメッセージを受信するクラスタインターフェースを露出させることができる。これらのクラスタリングメッセージは、他のクラスタリング命令の中でも、重心を作成するための命令、オブジェクトを重心にアタッチするための命令、又は、オブジェクトを重心からデタッチするための命令を含むことができる。
【０１２８】
[0167]いくつかの実施形態において、オブジェクトマネージャは、クラスタインターフェースを介して受信されるクラスタリングメッセージ内に含まれているクラスタリング命令を実行するように構成される。たとえば、少なくとも一つの実施形態において、オブジェクトマネージャは、重心の作成を要求するクラスタリングメッセージに応答するように構成される。このタイプのクラスタリングメッセージは、重心を記述するメタデータ（たとえば、グループＩＤ、名前など）を含むことができる。このタイプのクラスタリングメッセージを受信したことに応答して、オブジェクトマネージャは、オブジェクトがアタッチされ得るＮＵＬＬベクトル重心オブジェクトをインスタンス化する。加えて、これらの実施形態において、オブジェクトマネージャは、クラスタリングメッセージに応答してオブジェクトがリアルタイムでアタッチ又はデタッチされるときに、重心のベクトル及び濃度カウント（重心に対する内部参照）を自動的に維持するように構成される。
【０１２９】
[0168]図６〜図８は、いくつかの実施形態においてオブジェクトマネージャが実行するように構成されるクラスタリングプロセスを示す。クラスタリングプロセスは、アソシエーションがオブジェクト内容（たとえば、テキスト文書）に基づいて黙示的に定義されている、図６に示すオブジェクトネットワークなどの、既存のオブジェクトネットワーク内で、リンクを有していない新たなオブジェクトを重心にアタッチする。図６に示すように、クラスタリングプロセスは、新たなオブジェクトに基づいてクエリを送信する動作と、クエリに関する結果を受信する動作と、重心を識別する動作と、新たなオブジェクトを重心にアタッチする動作とを含む。図６に示すように、既存のオブジェクトネットワークは、重心Ｃ並びにオブジェクトＡ１、Ａ２、及びＡ３を含む。
【０１３０】
[0169]図４２を手短に参照すると、図４２は、図６〜図８に示すプロセスと一致して、オブジェクトを重心にアタッチするためのプロセスの流れ図を示している。４２０２において、オブジェクトマネージャはクラスタリングプロセス４２００を開始する。動作４２０４において、オブジェクトマネージャはクエリメッセージをクエリエンジンに送信する。クエリメッセージは、閾値類似度基準及び新たなオブジェクト（たとえば、図７に示すオブジェクトＡ４）のベクトル又はその一部分を含むことができる。クエリメッセージを受信したことに応答して、クエリエンジンは、クエリメッセージに基づいてベクトルクエリを実行し、閾値類似度基準を満たす１以上のオブジェクト（たとえば、図８に示すオブジェクトＡ２）を識別するクエリ結果を含む結果メッセージを返す。動作４２０６において、オブジェクトマネージャは結果メッセージを受信する。動作４２０８において、オブジェクトマネージャは、クエリ結果において新たなオブジェクトに類似している（たとえば、最も類似している）として識別されているオブジェクトに直接的又は間接的にリンクされている重心（たとえば、図８に示すオブジェクトＣ）を識別する。いくつかの実施形態において、また、図８に示すように、オブジェクトマネージャは、類似しているとして識別されているオブジェクト（たとえば、オブジェクトＡ２）から、重心に達するまでオブジェクトネットワークをトラバースすることによって、重心を識別する。動作４２１０において、オブジェクトマネージャは、新たなオブジェクトの属性及び様々なインデックスに含まれる情報を更新することによって、新たなオブジェクトを識別された重心にアタッチする。動作４２１０内で、オブジェクトマネージャはまた、新たなオブジェクトの存在及びベクトルに基づいて重心の濃度及びベクトルを更新する。４２１２において、オブジェクトマネージャはクラスタリングプロセス４２００を終了する。
【０１３１】
[0170]クラスタリングプロセス４２００に従ってクラスタリングプロセスを実行することによって、共通した内容をほとんど有していない要素を有し、結果として、リンクされているオブジェクトから重心が相対的に離れている大規模なクラスタが作成され得ることが諒解される。このようなクラスタが作成される問題に対処するために、オブジェクトマネージャと相互作用する構成要素を、（たとえば、分散の量を示す１以上の分散基準を追跡することによって）クラスタ内で許容される分散を監視し、分散基準が分散閾値を逸脱する（たとえば、超える）分散の量を制限するために、クラスタをより小さいクラスタに再クラスタリングするように構成することができる。
【０１３２】
[0171]いくつかの実施形態において、オブジェクトマネージャは、オブジェクト間の明示的アソシエーションを要求するクラスタリングメッセージを処理するように構成される。このタイプのクラスタリングメッセージは、明示的にリンクされるべきオブジェクト、及び、確立されるべきアソシエーションのタイプ（たとえば、一方向性アソシエーション又は双方向性アソシエーション）を識別する情報を含むことができる。明示的アソシエーションを要求するクラスタリングメッセージを受信したことに応答して、オブジェクトマネージャは、要求されているアソシエーションを実装するために、識別されたオブジェクトの属性及びインデックスを調整する。
【０１３３】
[0172]いくつかの実施形態において、重心を他の重心と関連付けることによって、クラストの集合が作成される。たとえば、ウェブページのあるクラスタは、ウェブページの別のクラスタと関連付けることができ、これにより、サブクラスタが他のサブクラスタに内部で黙示的にリンクされ、明示的にリンクされているスーパークラスタが作成される。様々な実施形態によれば、オブジェクトマネージャは、１以上の条件が検出されることに応答して、重心を明示的又は黙示的に関連付けるように構成される。たとえば、一つの実施形態において、オブジェクトマネージャは、第１の重心にリンクされている、閾値を超える数のオブジェクトが、第２の重心にリンクされているオブジェクトとの明示的アソシエーションを有することが検出されることに応答して、第１の重心を第２の重心と関連付けるように構成される。いくつかの実施形態において、オブジェクトマネージャが、重心自体を関連付けるのではなく、単純に重心にリンクされている個々のオブジェクトを関連付けることによって、より弱い関係を表すように構成されることが諒解される。
【０１３４】
[0173]図９は、重心ＣＡが重心ＣＢとの明示的双方向性アソシエーションを含み、重心ＣＢがＣＡとの明示的双方向性アソシエーションを含むスーパークラスタの一例を示す。図９に示すオブジェクトネットワークに対するプローブオブジェクトに関するベクトルクエリを実行するとき、プローブオブジェクトがオブジェクトＡ１、Ａ２、Ａ３、又はＡ４のいずれかに類似しているとクエリエンジンが判定した場合、クエリエンジンはまた、ＣＡとＣＢとの間の明示的双方向性リンクのために、プローブオブジェクトと、オブジェクトＢ１、Ｂ２、及びＢ３の各々との間の類似度についても試験することになる。
【０１３５】
[0174]図１０は、重心ＣＡを有するサブクラスタが、Ａ３に含まれているＤ２に対する明示的一方向性アソシエーションを介して重心ＣＤに緩やかにリンクされている、スーパークラスタの別の例を示す。図１０に示すオブジェクトネットワークに対するプローブオブジェクトに関するベクトルクエリを実行するとき、プローブオブジェクトがオブジェクトＡ１、Ａ２、Ａ３、又はＡ４のいずれかに類似しているとクエリエンジンが判定した場合、クエリエンジンはまた、ＣＡとＣＢとの間の明示的双方向性リンクのために、プローブオブジェクトと、オブジェクトＢ１、Ｂ２、及びＢ３の各々との間の類似度についても試験することになる。加えて、プローブオブジェクトがＡ３に類似しているとクエリエンジンが判定した場合、クエリエンジンはまた、プローブオブジェクトとＤ１、Ｄ２、及びＤ３との間の類似度についても試験することになる。
【０１３６】
[0175]図１１は、オブジェクトマネージャによって生成されるオブジェクトネットワークの別の例を示す。図１１に示すように、オブジェクトネットワーク内の各オブジェクトは、括弧内にその濃度をリストしているＮＵＬＬベクトルオブジェクトである。たとえば、Ｐ１は０の濃度を有し、一方で、Ｐ１２は１の濃度を有する。いくつかの実施形態において、オブジェクトマネージャは、オブジェクトの各外部アソシエーションの体現形を内部に維持する。たとえば、オブジェクトＰ３は、外部アソシエーションに対する「アンカーテキスト」としての役割を果たす任意選択のメタデータ、様々な要因に基づく任意選択のアソシエーション強度、及び、他のオブジェクトに対する任意選択の全体的なランクを各々が有する４つの内部体現形（Ｐ３１、Ｐ３２、Ｐ３３、及びＰ３４）を有する。いくつかの実施形態において、オブジェクトマネージャと相互作用する構成要素は、標的オブジェクトの内部アソシエーション、内部アソシエーションを介して標的オブジェクトにリンクされているオブジェクト、それらのオブジェクトの内部アソシエーションなどを、オブジェクトマネージャと相互作用する構成要素によって決定される任意の深度で分析することによって、マルチホップアソシエーション分析を実行する。
【０１３７】
[0176]いくつかの実施形態において、オブジェクトマネージャは、オブジェクト及び逆インデックスを使用して順方向と逆方向の両方でオブジェクトネットワークをトラバースするように構成される。たとえば、あるアプリケーションの目標は、検索エンジンにおける適切性ランキングを強化することであり得る。オブジェクトネットワークモデラにおいて前もって、インデックス付けされているページのリンクグラフをモデル化することによって、アプリケーションが、リンク情報を用いて検索エンジンを強化することが可能になる。ページを検索エンジンに投入する前に、アプリケーションは、複雑な順方向／逆方向分析、及び、任意の静的ページランク、又は、ページの元のテキストとともにインデックス付けするための内部参照物からのアンカーテキストを任意に使用して、ネットワーク内のページの位置及び重要性に関する情報を抽出するために、予めロードされているオブジェクトネットワークモデラをリアルタイムで参照することができる。
【０１３８】
[0177]ページ間の黙示的アソシエーションを含めることによって標準的なリンクグラフを超えることによって、アプリケーションの機能が大きく拡大する。概念連結、重複排除、関連内容などを可能にするファジー関係が明らかになる。
【０１３９】
ベクトル符号化
[0178]いくつかの実施形態において、クエリエンジンは、ベクトル空間モデルに基づいてファジーマッチングを実行するように構成される。これらの実施形態において、オブジェクトマネージャは、ベクタライザから外部ベクトルを受信し、これらの受信された外部ベクトルに基づいて内部ベクトルを生成するように構成される。内部ベクトルを生成することによって、オブジェクトマネージャは、データ処理効率、記憶効率、及び統一性を含むいくつかの利点を実現する。たとえば、ベクタライザがフリーテキストに適用される場合、ベクタライザは、任意長の文字列である次元（特徴）を有する外部ベクトルを出力することになる。統一性及び効率を達成するために、オブジェクトマネージャは、下記に説明するようにベクトルを符号化する。
【０１４０】
[0179]いくつかの実施形態において、外部ベクトルＶｅｘｔは、式１のように表すことができる一般的な形式を有する。
Ｖｅｘｔ＝｛（特徴１，重み１），（特徴２，重み２），…｝        （１）
式中、（特徴ｎ，重みｎ）は、重みの降順でソートされている、ｎ番目のベクトル要素である。外部ベクトルは、任意の数の要素を含んでもよい。各要素ｎは、データが導出されたオブジェクトを記述するデータであり、任意のサイズであってもよい特徴ｎを含み、任意の正の実数である重みｎは、他の特徴に対する特徴ｎの重要性を示す。
【０１４１】
[0180]いくつかの実施形態において、オブジェクトマネージャは、Ｖｅｘｔを、特徴ハッシュ法、重み正規化及び長さ量子化を通じて内部形式Ｖｉｎｔに変換する。これらの実施形態において、オブジェクトマネージャは、式２のように表すことができる一般的な形式を有する内部ベクトルＶｉｎｔを生成するように構成される。
Ｖｉｎｔ＝｛（ｄｉｍ１，ｍａｇ１），（ｄｉｍ２，ｍａｇ２），…｝      （２）
式中、要素（ｄｉｍｎ，ｍａｇｎ）は、（特徴ｎ，重みｎ）から導出される。オブジェクトマネージャは、実施態様特有の切り捨て制限ｍまでの任意の数の要素を内部ベクトルに記憶することができる。したがって、いくつかの実施形態において、ｎ＞ｍである場合、オブジェクトマネージャは、任意の（特徴ｎ，重みｎ）を切り捨て、破棄し、Ｖｉｎｔに含まないように構成される。様々な実施形態によれば、オブジェクトマネージャは、図１２に示すように、各々が、ｄｉｍｎのために２６ビットを使用し、ｍａｇｎのために６ビットを使用して一つの要素を表す３２ビット整数のアレイとしてＶｉｎｔを内部に記憶する。
【０１４２】
[0181]いくつかの実施形態において、オブジェクトマネージャは、内部アレイサイズＱｋを、Ｖｉｎｔ内の（非ゼロ）要素の数の関数として量子化するように構成される。これらの実施形態において、オブジェクトマネージャは、ｋ番目のベクトルアロケータからＶｉｎｔを保持するアレイを割り当てるように構成されており、後続する要素（すなわち、外部ベクトル内に対応する特徴を有していない要素）の集合をゼロに設定する。Ｘ内の要素の数を示すためにｎ（Ｘ）を使用すると、切り捨て制限、内部アレイサイズ、及びＶｉｎｔの間の関係は、不等式３のように表すことができる。
ｍ≧Ｑｋ≧ｎ（Ｖｉｎｔ）        （３）
【０１４３】
[0182]記憶を効率的にする目的のために、オブジェクトマネージャは、各々が、Ｖｉｎｔを記憶するのに十分に大きいサイズＱｋのｉｎｔ３２アレイをもたらす、ベクトルアレイのためのカスタムメモリアロケータ（ｃｕｓｔｏｍ  ｍｅｍｏｒｙ  ａｌｌｏｃａｔｏｒ）を設定するように構成される。ｎ（Ｖｉｎｔ）＝Ｑｋでないかぎり、オブジェクトマネージャは、ベクトルアレイの後続の要素をゼロに設定する。
【０１４４】
[0183]いくつかの実施形態において、ベクトルアロケータの集合Ａは、ｎ（Ｖｉｎｔ）＜Ｑｋであるときに無駄になる後続のゼロ要素の数を最小限に抑える必要性と平衡させて、すべての可能性のあるベクトルサイズｎ（Ｖｉｎｔ）≦ｍについての別個のアロケータを有するというオーバーヘッドを回避するために量子化される。これらの実施形態において、オブジェクトマネージャは、内部ベクトルを記憶するのに十分な容量を有するアレイを生成するための最小のアロケータＡｋを選択する。
【０１４５】
[0184]いくつかの実施形態において、アロケータサイズの集合Ｑは、図２を参照して上述したアプリケーション２０８のような１以上のアプリケーションに対応するように、コンパイル時間又は実行時間において調節可能である構成可能パラメータである。アロケータサイズの集合Ｑは、式４のように表すことができる。
Ｑ＝｛Ｑ１，Ｑ２，…，Ｑｋ，…Ｑｍａｘ｝，    Ｑｍａｘ＝ｍ        （４）
【０１４６】
[0185]図１３及び図３９は、ともに、いくつかの実施形態に従ってオブジェクトマネージャによって実行される、ＶｅｘｔからＶｉｎｔを作成するための変換プロセスを示す。図３９に関連して、図３９は、外部ベクトルを受信する動作と、ベクトルアロケータを選択する動作と、内部表現を生成する動作と、重みを正規化する動作と、長さを量子化する動作とを含むベクトル符号化プロセス３９００を示す流れ図である。変換プロセス３９００は３９０２において開始する。
【０１４７】
[0186]動作３９０４において、オブジェクトマネージャは処理のための外部ベクトルを受信する。外部ベクトルは、ベクタライザから送信され得る。図１３に示すように、外部ベクトルは、要素の集合｛特徴１，…特徴ｎ｝を含み得、各要素は、特徴及び重みを含む。
【０１４８】
[0187]動作３９０６において、オブジェクトマネージャは、Ｖｉｎｔを記憶するための内部ベクトルアレイを割り当てる。一つの実施形態において、オブジェクトマネージャは、外部ベクトルを分析してそのサイズを判定し、Ｑｋ≧ｎ（Ｖｅｘｔ），Ｑｋ≦ｍとなるようにベクトルアロケータ（図１３のＡｋとして示す）を選択する。次に、オブジェクトマネージャは、Ａｋを使用して新たな内部ベクトルアレイを割り当てる（図１３の「内部ベクトルＶｉｎｔ」を参照されたい）。
【０１４９】
[0188]動作３９０８において、オブジェクトマネージャは、外部ベクトルに含まれている各特徴の内部表現を作成する。一つの実施形態において、オブジェクトマネージャは、すべてのｎ＞Ｑｋについて、ハッシング関数ｄｉｍｎ＝ｈａｓｈ（特徴ｎ）を使用して、特徴ｎを整数ｄｉｍｎとして符号化することによって、内部表現を作成する。いくつかの実施形態において、ｈａｓｈ（）は高速であり、所定サイズ（たとえば、２６ビット）の均一に分散した整数を生成する。動作３９１０において、オブジェクトマネージャは、動作３９０８において作成された内部表現の重みを正規化する。一つの実施形態において、オブジェクトマネージャは、すべてのｎ＞Ｑｋについて、最大重みが所定の最大値（たとえば、２６−１＝６３）に位置し、最小重みが所定の最小値（たとえば、１）に位置するようなスケーリング及び正規化関数ｍａｇｎ＝ｓｃａｌｅ（重みｎ）を使用して、各重みｎをｍａｇｎとして符号化する。この符号化動作は、Ｖｅｘｔが、可能性のある最大特徴重みを１．０のような既知の量として表すために予め正規化されていることによって容易にすることができる。
【０１５０】
[0189]動作３９１２において、オブジェクトマネージャは、Ｖｉｎｔの長さを量子化する。一つの実施形態において、オブジェクトマネージャは、図１３の内部ベクトルアレイの最後の要素に示されているように、すべてのｎ＞Ｑｋについてｄｉｍｎ＝０１ｍａｇｎ＝０を設定する。
【０１５１】
[0190]いくつかの実施形態において、特徴ベクトルＶｅｘｔはオブジェクトネットワークモデラ２０２内に記憶される必要はないが、オブジェクトメタデータの一部分として含まれてもよい。これらの実施形態において、内部ベクトルＶｉｎｔが、アロケータＡｋによって返されるｉｎｔ３２アレイに対するポインタとしてベクトルが記述するオブジェクトに記憶される。同じオブジェクトＯの複数の体現形Ｏ１、Ｏ２、Ｏ３、…は、メモリ内で同じアレイを参照することによって、同じベクトルインスタンスを共有し得る。これらの実施形態において、オブジェクトマネージャは、体現形が消去されると、さらなる体現形がアレイを参照するかどうかを判定し、参照しない場合、アレイの割り当てを解除するように構成される。たとえば、アレイを参照する体現形の数を追跡するために参照カウントが使用される実施形態において、オブジェクトマネージャは、オブジェクト体現形が消去されている間に参照カウントを減分することができる。さらに、参照カウントがゼロに等しい場合、オブジェクトマネージャはアレイの割り当てを解除することができる。
【０１５２】
[0191]Ｖｅｘｔの特徴空間は実際的には無限であるが、Ｖｅｘｔの次元空間は、符号化の一部分としてさらに制約される。いくつかの実施形態において、内部ベクトル次元に２６ビットが使用されることに起因して、オブジェクトネットワークモデラは、２２６−１＝６７，１０３，８６３次元有限ベクトル空間内で動作する。（ｎ（Ｖｉｎｔ）＜Ｑｋの場合、ｄｉｍ＝０はゼロ詰めベクトルアレイのために確保される。）
【０１５３】
[0192]たとえ６７００万自由度は最初は豊富であるように見え得るとしても、誕生日問題として一般的に知られている現象に起因して、オブジェクトモデルのベクトル空間よりも数桁多様性に劣る制限された特徴語彙の中でさえエイリアシング（衝突）が発生し得ることが諒解される。いくつかの実施形態において、次元エイリアシングは、ベクトルを比較するときに偶発的な偽陽性をもたらす場合があり、全体的な適合率に影響を与える。しかしながら、これらの実施形態において、コンパクトな内部ベクトルの性能利点は、散発的な偽陽性の欠点にまさる。加えて、絶対的な適合率を必要とするアプリケーションについて、いくつかの実施形態は、下記にさらに説明されるようにフィルタリング（アンチエイリアシング）のためにメタデータとしてのオブジェクトに沿ってＶｅｘｔを記憶するように構成されたオブジェクトマネージャを含む。
【０１５４】
ベクトル類似度基準
[0193]いくつかの実施形態において、クエリエンジンは、ベクトル類似度計算を使用して黙示的アソシエーション（ファジーマッチング）を判定するように構成される。この黙示的アソシエーションを判定する構成を２次元の文脈の中で説明するために、クエリエンジンは、図５に表すように２つのベクトルＡ及びＢについて類似度を計算することができる。
【数１】
2019053772.tif 000008
【０１５５】
[0194]角度θは、図１４に示すように空間的位置整合を表し、ＡとＢとの間の長さの差は考慮に入れない。この類似度計算手法は、コサイン類似度と称され、任意の数の次元に適用することができる。
【０１５６】
[0195]他の実施形態において、クエリエンジンは、式６に表すような計算を使用して類似度を測定するように構成される。
【数２】
2019053772.tif 000009
【０１５７】
[0196]この類似度測定手法は、Ｊａｃｃａｒｄ指数と称される。２つの集合Ａ及びＢのＪａｃｃａｒｄ指数は、共通集合／和集合比として定義され、ベクトル次元間の重複を測定し、重複が多いほど、類似度は高くなる。
【０１５８】
[0197]本明細書に開示されているいくつかの実施形態は、コサイン類似度もＪａｃｃａｒｄ指数も、すべての状況について理想的ではないという評価を明らかにする。これらの実施形態において、クエリエンジンは、コサイン類似度とＪａｃｃａｒｄ指数の２つを組み合わせて、一方又は他方における望ましくない特異な挙動に対抗するのを助ける複合基準にするように構成される。この組み合わせ手法は、式７のように表すことができる。
Ｓｉｍ（Ａ，Ｂ）＝Ｃｏｓｉｎｅ（Ａ，Ｂ）α・Ｊａｃｃａｒｄ（Ａ，Ｂ）β        （７）
指数α及びβは、一方の類似度基準が他方よりも適切であるアプリケーションに対応するための、（α＋βが１．０になるような）０．０〜１．０の可変構成可能パラメータである。
【０１５９】
[0198]次元性の問題が、コンパクトな内部ベクトルを使用するときでさえ、計算効率に制限を課すことが諒解される。このように制限が課されるという理由から、オブジェクトネットワークモデラのいくつかの実施形態は、ファジーマッチングのために総当たりベクトル比較のみには依拠しないが、オブジェクトネットワークモデラは、総当たりベクトル比較を必要とする特定のアプリケーションのためにこれを行うように構成することができる。いくつかの実施形態は、最初のＭ個の要素に対しては内部ベクトルに対する直接次元インデックスを利用する。これらの実施形態において、クエリエンジンは、上位Ｍ個の要素の間で少なくとも一つの次元を共有するベクトルの再現率を保証する。しかしながら、すべての要素について直接次元インデックス付けを構成すると、この手法の０（ｎ２）性に起因して性能に影響があることが諒解される。いくつかの実施形態は、下記にさらに説明するフィンガープリントを使用してこの問題に対処する。
【０１６０】
フィンガープリンティング
[0199]いくつかの実施形態において、オブジェクトネットワークモデラは、局在性鋭敏型ハッシング（ＬＳＨ）に基づくフィンガープリンティングと称される次元性低減技法を使用して、ベクトル比較に関する次元性の問題に対処するように構成される。これらの実施形態において、オブジェクトネットワークモデラは、いくつかの独立したＬＳＨ断片がともに接合されて、本明細書において「Ｆ−ＬＳＨ」と称される単一のフィンガープリントが形成される手法を使用する。より詳細には、これらの実施形態において、オブジェクトマネージャ及びクエリエンジンのようなオブジェクトネットワークモデラ構成要素は、Ｆ−ＬＳＨ断片の様々な組み合わせを使用して照合プロセスを実行するように構成される。そのため、これらの実施形態において、全体としての各フィンガープリントは、効率的な「記憶装置」、又はＷビット幅のビットベクトルＶｆｐである。これらの実施形態において、オブジェクトマネージャは、標的マシンアーキテクチャ上の単語の偶数倍に適合し、それゆえ、最小数の機械語命令で操作するためにコンパクトであると同時に高速であるフィンガープリントを生成する。一つの実施形態において、オブジェクトネットワークモデラは、ｘ６４プラットフォームでＶｆｐに対して単一の６４ビットワードを使用し、すなわちｗ＝６４である。他の実施形態は、他のワードサイズを使用してもよい。
【０１６１】
[0200]内部ベクトルＶｉｎｔが高次元空間内の疎ベクトルである一方、Ｖｆｐは、インデックスキーを形成するためにオブジェクトネットワークモデラ構成要素によって組み合わされる部分領域（断片）を有する、Ｗ次元内の密ベクトルである。式８及び９は、Ｖｉｎｔ及びＶｆｐのそれぞれのサイズを表す。
【０１６２】
[0201]内部特徴ベクトルＶｉｎｔ：
ｎ（Ｖｉｎｔ）∈［１，∞），ｓｐａｃｅ＝Ｒ２２６−ｌ        （８）
【０１６３】
[0202]フィンガープリントＶｆｐ：
ｎ（Ｖｆｐ）＝Ｗ，ｓｐａｃｅ＝｛０，１｝Ｗ，Ｗ∈｛６４，１２８，２５６，５１２，…｝        （９）
【０１６４】
[0203]いくつかの実施形態において、オブジェクトネットワークモデラ構成要素は、フィンガープリントによって表される内部ベクトル間の差を求めるためにフィンガープリントを比較するように構成される。特に、これらの実施形態は、性能最適化のためにフィンガープリント間のハミング距離を使用することができるが、これらの実施形態は、ハミング距離を直接的に類似度基準としては使用しない。２つの２進数のハミング距離は、反対の値を有するビット位置の数である。
【０１６５】
[0204]いくつかの実施形態において、オブジェクトネットワークモデラ構成要素は、フィンガープリントをベクトルインデックス付けにとって適切なものにするＦ−ＬＳＨフィンガープリント（オブジェクトネットワークモデラによって実装されるような）の少なくとも一つの特性が、内部ベクトル間の差が中程度である結果として、ビットが、ビットの対応するフィンガープリント内で局所的に（クラスタ化されて）修正されることであるという評価を明らかにする。ベクトルＶｉｎｔが小さく変化する結果として、フィンガープリントＶｆｐは小さく局所的に変化する。言い換えれば、ＶｉｎｔとＶ’ｉｎｔとの間の差が小さい（数次元）場合、ＶｆｐとＶ’ｆｐとの間の差は、１以上の（ただし、すべてではない）フィンガープリント断片内で発生する反対の値の数ビットになる。
【０１６６】
[0205]いくつかの実施形態において、インデックスマネージャは、この変化の特性を使用して、Ｖｆｐの個々の断片をシャッフルして再結合して、テーブルの集合への直接検索キーとして使用するための、本明細書においては重要領域と称するより小さい部分集合にすることによって、Ｖｆｐに対する順列インデックスの集合を作成する。本明細書において参照される場合、Ｐｊは断片を示し、Ｒｉは重要領域を示し、Ｔｉは、Ｒｉをキーとして使用した順列インデックス（ルックアップテーブル）を示す。
【０１６７】
[0206]いくつかの実施形態において、断片Ｖｆｐの数Ｆは、重要領域Ｒｉあたりの断片の数ｆＲのように、構成可能パラメータである。すべてのＲｉは同じ数の断片を含み得、すべてのＰｊが必ずしも同じ幅であるとは限らないため、Ｒｉ内のビットの数はわずかに変化し得る。これは、下記で図１５において、Ｆ＝５、ｆＲ＝２について示されている。これらの実施形態において、全インデックス範囲のために必要とされるルックアップテーブルの数（Ｎ）は、式１０に従ってＦ及びｆＲとともに変化する。
【数３】
2019053772.tif 000010
【０１６８】
[0207]たとえば、ＶｆｐをＦ＝４個の断片に分割し、重要領域あたりｆＲ＝１個の断片を使用する構成は、Ｎ＝Ｃｏｍｂ（４，１）＝４個のルックアップテーブルを必要とする。ＶｆｐをＦ＝５個の断片に分割し、重要領域あたりｆＲ＝２個の断片を使用する、より大きな構成は、上記で分かるように、Ｎ＝Ｃｏｍｂ（５，２）＝１０個のルックアップテーブルを必要とする。本明細書において参照される場合、（Ｆ，ｆＲ）は、断片、及び、断片あたりの領域の特定の構成を示す。
【０１６９】
[0208]テーブル集合をより大きくすることの利点の一つは、入力ベクトルＶｉｎｔの変化に対するロバスト性が増大し、テーブルあたりの検索性能が増大することであることが諒解される。マイナス面は、すべてのテーブルにわたる同時の検索を実施するためにメモリフットプリントが大きくなること、及び、ＣＰＵ需要がより高くなることを含み得る。２つのフィンガープリント間のビット変動がＦ−ｆＲ以下の断片まで分離されているかぎり、少なくとも一つの同一の重要領域が２つのフィンガープリントについて存在し、結果として、テーブルの少なくとも一つにおいて一致がもたらされることも諒解される。
フィンガープリントの生成
【０１７０】
[0209]いくつかの実施形態において、オブジェクトマネージャは、図１６〜図１７及び図４０によって示されているフィンガープリント生成プロセス４０００を実行することによって、内部ベクトルＶｉｎｔのフィンガープリントＶｆｐの１以上の断片を生成するように構成される。内部ベクトルＶｉｎｔが、図１６の上部に示されている。
【０１７１】
[0210]図４０を簡潔に参照すると、フィンガープリント生成プロセスを示す流れ図が示されている。フィンガープリント生成プロセス４０００は、４つの断片を有するフィンガープリントを生成するように構成されるが、本明細書に開示されている実施形態は、特定の数の断片には限定されない。例示的なフィンガープリントが、概して図１６の下部に示されている。図４０に示すように、フィンガープリント生成プロセス４０００は、内部ベクトルの次の未処理の要素を選択する動作と、生成されているフィンガープリントの標的断片を選択する動作と、選択された要素内の次元情報の要約を生成する動作と、要約を重み付けする動作と、要約を以前の要約と組み合わせる動作と、内部ベクトルのさらなる未処理の要素が存在するかどうかを判定する動作と、組み合わされた要約を標的断片として記憶する動作とを含む。フィンガープリント生成プロセス４０００は４００２において開始する。
【０１７２】
[0211]動作４００４において、内部ベクトルの次の未処理の要素が選択される。動作４００６において、生成されているフィンガープリントの標的断片が選択される。一つの実施形態において、オブジェクトマネージャは、選択された要素に記憶されている次元情報を分析することによって、標的断片を選択する。図１６は、ｄｉｍｎの複数の異なる部分を、１）ＬＳＨ生成のためのビットパターン及び２）断片ルーティングとして使用して、ＶｉｎｔをＶｆｐに変換するためのプロセスを示す。たとえば、オブジェクトマネージャは、次元ｄｉｍｎの上位８ビットを使用して、ｄｉｍｎの下位ビットｂによって影響を受けるためのＶｆｐの断片Ｐｊを選択することができる。この例において、断片選択は、ｊ＝１＋Ｕｐｐｅｒ８（ｄｉｍｎ）ｍｏｄ  Ｆとして計算される。結果もたらされるビットパターンＰｊは、一例において、すべてのＬｏｗｅｒＢ（ｄｉｍｎ）からの、ｍａｇｎによって重み付けされた個々のビットパターンを組み合わせる累積ハッシュ関数を使用して計算することができる。
【０１７３】
[0212]動作４００８において、選択された要素の要約が生成される。一つの実施形態において、オブジェクトマネージャは、選択された要素に記憶されている次元情報のハッシュ値を計算することによって、要約を生成する。たとえば、オブジェクトマネージャは、ｄｉｍｎの下位ｂビットのハッシュ値を計算することができ、ｂは、標的断片内のビット数に等しい。
【０１７４】
[0213]動作４０１２において、要約が重み付けされる。一つの実施形態において、オブジェクトマネージャは、選択された要素に記憶されている大きさに従って要約を重み付けする。たとえば、オブジェクトマネージャは、選択された要素の記憶されている大きさによって表される最大の大きさのうちの割合として、重み付け係数を計算することができる。動作４０１４によって、重み付けされた要約が、以前の重み付けされた要約と組み合わされる。動作４０１２及び４０１４は、図１６内に示されている。動作４０１６において、内部ベクトルのさらなる未処理の要素が存在するかどうかが判定される。存在する場合、フィンガープリント生成プロセスは動作４００４に戻る。存在しない場合、フィンガープリント生成は、動作４０１８において、組み合わされた、重み付けされている要約を標的断片（図１６のＰ１〜Ｐ４のいずれか）として記憶する。フィンガープリント生成プロセス４０００は４０２０において終了する。
【０１７５】
[0214]図１７は、動作４００４〜４０１６の一例を示す。図１７によれば、オブジェクトマネージャによって実行されるＬＳＨ生成器は、すべての寄与するベクトル次元から個々のビットパターンをビットごとに「投票」することによって、最終的なビットパターンを決定し、各個々の「票」の重みは、ベクトル要素の大きさに等しい。図１７の例に示されている実施例において、３つのベクトル要素｛（１００１０，２０）、（１１００１，１５）、（０００１１，１０）｝が組み合わされて、最終的なパターン１００１１が形成されている。また、第３のベクトル要素が０００１１ではなく１１１１１であったとすると、最終的なパターンは１００１１ではなく１１０１１になっていたことにも留意されたい（すなわち、一つのベクトル要素が異なると、結果としてＬＳＨ値において単一ビットの差がもたらされる）。
【０１７６】
[0215]図１８は、オブジェクトネットワークモデラ２０２内で実施される次元性低減の３つの段階を通じた元のオブジェクトからの変換を要約している。
類似度照合
【０１７７】
[0216]いくつかの実施形態において、オブジェクトマネージャは、オブジェクトと関連付けられるベクトルの類似度の関数として、オブジェクトを黙示的に関連付ける。様々な実施形態によれば、類似度に基づいて２つのオブジェクトをリンクさせるための決定は、動的閾値及び混合規則を含む様々な構成可能パラメータを使用して構成することができる。規則は、オブジェクトの属性、オブジェクトのランク、濃度、クラスタサイズ、クラスタ分散、動的閾値の使用などのような、一致する可能性のあるオブジェクトの特性を分析することができる。一つの実施形態において、オブジェクトマネージャは、不等式１１が満たされる場合にオブジェクトをリンクさせるように構成される。
「Ｓｉｍ（Ａ，Ｈ）＞閾値である場合にベクトルＡ及びＢは類似している」  （１１）
【０１７８】
[0217]当業者には諒解されるように、本明細書に記載されている技法及びシステムはまた、照合するオブジェクトの他の属性、それらのオブジェクトのランク、濃度、クラスタサイズ、クラスタ分散、動的閾値の使用などを考慮に入れた、より複雑な決定方針をも可能にする。
【０１７９】
[0218]図１８は、上記の教示と連携した、データ低減プロセスを示すシーケンス線図である。より詳細には、図１８は、オブジェクトを様々な表現（たとえば、１以上の外部ベクトル、１以上の内部ベクトル、及び、一つ若しくは複数の断片を含むフィンガープリント）に変換するための一つの例示的な方法を示す。
【０１８０】
[0219]以下説明する動機として、ベクトル記憶及び検索のための標準的なＳＱＬデータベースを使用するナイーブアプローチ（ｎａｉｖｅ  ａｐｐｒｏａｃｈ）を考察する。このナイーブアプローチにおいて、オブジェクトは、ＤＢテーブル内の行として表され、上記で紹介した元の特徴ベクトルＶｅｘｔの列を有することができる。そのベクトルがプローブベクトルＱｅｘｔに類似している、ＤＢ内のすべての行を取り出すことが所望される場合、第１の課題は、この種類のクエリを直接サポートしていないＳＱＬ言語そのものである。したがって、一つの解決策は、必要な計算を有する記憶されている手順を書き出すことを含み得るが、これにはすべてのクエリについて線形テーブルスキャンを行う必要があり、非効率的である。さらに、ベクトル次元を別個の列又はテーブルに記憶し、インデックスを追加し、精緻な接合方式を使用することなども可能であり得るが、結局のところ、従来の既存のデータベース技術は、このタイプのアプリケーションについて大きなスケールで首尾よく機能するようには最適化されない。
【０１８１】
[0220]したがって、本明細書に記載されているデータベースシステム及び技法は、部分的には、上記のタイプのクエリを最適化し、したがって、従来のデータベースシステムと関連付けられる上記の制約の多くを克服するように設計されている。詳細には、本明細書に記載されているデータベースシステム及び技法は、（１）最大再現率、（２）最大適合率、（３）最小クエリ待ち時間、及び（４）最大クエリボリューム（スループット）を達成するように設計されている。
【０１８２】
[0221]本明細書において参照される場合、再現率（Ｒ）及び適合率（Ｐ）は、真陽性（ｔｐ）、偽陽性（ｆｐ）及び偽陰性（ｆｎ）の概念によって定義される。再現率及び適合率はそれぞれ、式１２及び１３として表すことができる。
【数４】
2019053772.tif 000011
【０１８３】
[0222]本明細書において使用される場合、真陽性（ｔｐ）とは、クエリの結果内に含まれる、クエリに対する期待される結果である。偽陽性（ｆｐ）とは、期待されない結果であるクエリ結果である。偽陰性（ｆｎ）は、クエリ結果における不正確な脱落、すなわち、期待されていたが、返されなかった結果である。上記の定義から、２つの病的状況が指摘される：１）ｆｎ＝０とする脱落がないため、常にすべてを返すクエリが１００％の再現率をもたらす、２）ｆｐ＝０とする結果がない（また、０／０→１と考えられる）ため、常に何も返さないクエリが１００％の適合率をもたらす。一実施例において、本明細書に記載されているシステム及び技法は、再現率と適合率の両方を可能なかぎり高いままにしながら、クエリが何かを返すように設計されている。したがって、類似度照合の一例において、「期待される」とは、以下のように設計され得るものである。Ｓｉｍ（Ｑ，Ｖ）＝τである場合、ＱについてのクエリからＶが返されると期待され、Ｓｉｍ（Ｑ，Ｖ）＝τでない場合、期待されない。
【０１８４】
[0223]いくつかの実施形態において、クエリエンジンは、３つの（任意選択的に４つの）段階に分割されるクエリプロセスを実行するように構成される。これらの段階は、符号化段階、再現段階、適合段階、及び（任意選択的に）アンチエイリアシング段階を含む。符号化段階は、最初に、プローブオブジェクト（Ｑ）を、特徴ベクトルＱｅｘｔ、内部ベクトルＱｉｎｔ、及びフィンガープリントＱｆｐに変換する。クエリエンジンによる再現段階の実行は、偽陰性を最小限に抑え、偽陽性を制限しながら、可能なかぎり迅速に、可能なかぎり多くの真陽性候補を収集するように設計されている。クエリエンジンによる適合段階の実行は、再現段階の間に生成されるほとんどの偽陽性をなくすように設計されている。クエリエンジンによるアンチエイリアシング段階の実行は、適合段階の間に生成される任意の残りの偽陽性をなくすように設計されている。
【０１８５】
[0224]１００％の再現率及び１００％の適合率は、再現段階においてすべてのベクトルを返し、適合段階を飛ばし、すべての偽陽性をフィルタリング除外するためにアンチエイリアシング段階に依拠することによって達成することができることが諒解される。しかしながら、この手法では、相当のサイズのオブジェクトネットワークについて適切な性能をもたらすことができない。したがって、いくつかの実施形態において、クエリエンジンは、図１８に示すように適用される、図１２、図１３、図１６、及び図１７を参照して上述したベクトル符号化及びフィンガープリンティングプロセスを利用することによって、再現率及び適合率を最大化するように構成される。
【０１８６】
[0225]図１９は、符号化段階１の動作、再現段階２の動作、適合段階３の動作、及びアンチエイリアシング段階４の動作を含むクエリプロセスを示す。これらの段階の各々は、下記にさらに説明する。
【０１８７】
[0226]一つの実施形態によれば、符号化段階１において、クエリエンジンは、プローブオブジェクト（図１９においては「Ｑ」として参照されている）から、照合及びフィルタリングの間に使用するための特徴ベクトルＱｅｘｔ、内部ベクトルＱｉｎｔ及びフィンガープリントＱｆｐを準備する。外部ベクトル、内部ベクトル、及びフィンガープリントを生成するための技法は上記に記載されており、したがって、この説では詳細には説明しない。
【０１８８】
[0227]さらに、この実施形態によれば、再現段階２において、クエリエンジンは、性能を高め、偽陰性を妥当に良好に防止するために順列インデックスを使用して、すべての記憶されている｛Ｖｆｐ｝に対してフィンガープリントＱｆｐを照合する。クエリエンジンはまた、性能をより高め、偽陽性を（可能性として）低減するために、ハミング距離閾値を適用することもできる。クエリエンジンはまた、偽陰性の数を最小限に抑えるための性能要件を依然として満たしながら、許容され得るかぎり多くの直接次元インデックスを使用して（すなわち、インデックスマネージャによって作成される直接次元インデックスを使用して）、すべての記憶されている｛Ｖｉｎｔ｝に対して内部ベクトルＱｉｎｔを照合することもできる。この再現段階の終わりに、クエリエンジンは、すべてのインデックスから統合及び重複排除された候補集合を返す。
【０１８９】
[0228]この実施形態を続けると、適合段階３の中で、クエリエンジンは、再現段階から返されたすべての候補｛Ｖｉｎｔ｝について、ほとんどの偽陽性をフィルタリング除外するために、ベクトル類似度基準Ｓｉｍ（Ｑｉｎｔ，｛Ｖｉｎｔ｝）≧τを適用する。たとえば、前述した２６ビットハッシュ関数及び「誕生日問題」によって引き起こされる次元エイリアシングに起因して、偽陽性が依然としてすり抜ける場合がある。
【０１９０】
[0229]また、この実施形態において、任意選択のアンチエイリアシング段階４内で、クエリエンジンは、適合段階から返されるすべての偽陽性をフィルタリング除外するために、適合段階から返されるすべての結果について、オブジェクトメタデータ｛Ｖｅｘｔ｝を取り出し、ベクトル類似度基準Ｓｉｍ（Ｑｅｘｔ，｛Ｖｅｘｔ｝）≧τを適用する。このアンチエイリアシング段階は、１００％の適合率が保証されなければならないのでないかぎり、必要ない。このアンチエイリアシング段階は、Ｖｅｘｔが、すべての記憶されているオブジェクトとともに「ブロブ」メタデータとして含まれていることを必要とし得、より高い記憶需要、より高いディスクＩ／Ｏ、及びより長いクエリ待ち時間を必要とし得る。
【０１９１】
[0230]図１９は、高レベルにおけるクエリエンジンの動作を示す。オブジェクトネットワークモデラは、クエリエンジンのマルチスレッド処理を支援し、多くのＣＰＵ（又はＧＰＵ）コアを同時に使用して複数のクエリが並列して処理されることを可能にする。いくつかの構成要素は、無制限の並列実行を支援し（リソースを共有しない）、一方で、他の構成要素は、クエリ「コンベアベルト」の副部分に対してリソースをロックして作業するスタイル（パイプライン化手法）を必要とする。いくつかの実施形態において、パイプライン化手法は、順列インデックス及び次元インデックスに適用される。
【０１９２】
[0231]より多数のインデックスを用いる構成は、ＣＰＵカウントの多いマルチコアマシンアーキテクチャから直接的に受益する。実行はまた、各々が順列インデックス及び次元インデックスの全体集合のうちの部分集合をホストする複数のマシンにスケーリングすることもできる。マルチマシン設定は、ディスパッチャ構成要素（図示せず）を使用した候補の追加の統合／重複排除ステップが必要になることと引き換えに、同じクエリに対して構成された多くの（又はすべての）インデックスにわたる真の同時のインデックス検索を可能にすることから受益する。
【０１９３】
[0232]図１９を参照して上述したように、本明細書に開示されている実施形態は、クエリ実行中に再現段階を実行するように構成される。再現段階の一つの目的は、偽陰性が最小限に抑えられ、偽陽性が制限されるように、基準Ｓｉｍ（Ｑ，Ｖ）≧τを部分的に満たす、クエリＱについての候補集合Ｃ＝｛Ｖ｝の一致を返すことである。クエリエンジンは、この目的を達成するために、順列インデックスと次元インデックスとの組み合わせを参照する。陽性一致条件は、陽性クラス＝Ｓｉｍ（Ｑ，Ｖ）≧τ及び陰性クラス＝Ｓｉｍ（Ｑ，Ｖ）＜τであるように、類似度閾値に関して定義される。
【０１９４】
[0233]図２０は、再現段階において生成される候補をグラフで示す。クエリエンジンの再現率メカニズムの性質は、「網を打つ」ものであり、これは、図面内の再現候補ボックスが、偽陰性を最小限に抑える試行において右と左の両方に拡張されることを意味する。しかしながら、偽陽性領域に対する左への拡張は、真陰性の集合よりもはるかに小さく、後続の適合段階のために、結果候補集合が管理可能であることが保証される。
【０１９５】
[0234]いくつかの実施形態において、クエリエンジンは、図２１に示すように、順列インデックスを通じてクエリ再現段階の間にフィンガープリントによって迅速で高度にスケーラブルなオブジェクト検索を実施するように構成される。フィンガープリンティングの節の中で上述したように、所与の構成（Ｆ、ｆＲ）について、オブジェクトマネージャは、各々がｆＲ個の断片のインデックスキーを構築するためにシャッフル及び再結合されるＦ個の断片に分割されるフィンガープリントを生成する。Ｎ＝Ｃｏｍｂ（Ｆ，ｆＲ）によって表されるように、各々がＦ個の断片をｆＲ個の断片から成る集合に組み合わせるＮ個の異なる方法がある。ｉ番目の組み合わせについて、選択された断片部分集合から構成されるキーは、本明細書においては、重要領域Ｒｉとして参照され、ｉ∈｛１，２，３，…，Ｎ｝である。いくつかの実施形態において、Ｒｉは順列インデックスＴｉに対するキーであり、順列インデックスの完全な集合は、Ｔ＝｛Ｔ１，Ｔ２，…，Ｔｎ｝として示される。
【０１９６】
[0235]いくつかの実施形態において、類似度クエリについて、クエリエンジンは、図２２及び図２３に示すように、順列インデックスＴｉについて、再現段階の間に候補オブジェクトを収集するように構成される。これらの実施形態において、順列インデックスＴｉは大きいが、ロックのレベルが低い単純なハッシュ状構造であり、競合の機会を最小限に抑えて同時の読み書きを可能にする。すべての順列インデックスは、実行時にはメモリ（ＲＡＭ）内に存在する。
【０１９７】
[0236]図４２に示すように、再現プロセス４２００は、プローブフィンガープリントの次の領域を形成する動作と、形成された領域に対応するインデックススロットアレイを選択する動作と、インデックススロットアレイに含まれるオブジェクトフィンガープリントを走査する動作と、プローブフィンガープリントのさらなる未処理の領域が存在するかどうかを判定する動作と、再現候補を返す動作とを含む。再現プロセス４２００は４２０２において開始する。
【０１９８】
[0237]動作４２０４において、プローブフィンガープリントの次の領域が形成される。図２２は、プローブフィンガープリントＱｆｐを参照し、Ｐ１とＰ４との組み合わせとして、形成された領域を参照する。いくつかの実施形態において、クエリエンジンは、プローブオブジェクトのフィンガープリントＱｆｐのビットの部分集合から重要領域Ｒｉを形成する。Ｒｉ内のビットの数ｄは、順列インデックスＴｉの必要とされる長さ２ｄを決定付ける。Ｔｉ内の各インデックスラインは、可変長インデックススロットアレイに対するポインタ、並びに、様々な簿記データ及びロックを含む構造である。インデックスキーＲｉは、Ｔｉ内のインデックスラインを直接的に識別する。インデックススロットアレイ内の各スロットはオブジェクトに対するポインタ及びそのオブジェクトのフィンガープリントＶｆｐを保持する。インデックススロットアレイ内のすべてのオブジェクトは、同一の重要領域Ｒｉを有するフィンガープリントＶｆｐを有する。
【０１９９】
[0238]動作４２０６において、動作４２０４において形成された領域によって識別されるインデックスラインに基づいて、インデックスラインが選択される。この選択動作は図２２に示されている。一つの実施形態において、クエリエンジンが、識別されたインデックスラインを選択する。
【０２００】
[0239]動作４２０８において、選択されたインデックスライン内のポインタによって識別されたインデックススロットアレイが走査される。この走査動作も図２２に示されている。一つの実施形態において、クエリエンジンが、選択されたインデックスライン内のポインタによって識別されたインデックススロットアレイを走査する。インデックススロットアレイは、そのフィンガープリントが最大でｈビット位置しか異ならない、すなわち、ｈａｍｍｉｎｇ＿ｄｉｓｔａｎｃｅ（Ｑｆｐ，Ｖｆｐ）≦ｈであるスロットを選出してスロットごとに始まりから終わりまで走査することができる。クエリエンジンは、Ｑｆｐの構成されるハミング距離ｈ内にあるフィンガープリントＶｆｐを有する各オブジェクトを、再現候補のアレイに追加し、したがって、順列インデックス再現段階からクエリ結果を形成する。少なくとも一つの実施形態において、オブジェクトはポインタとして再現候補のアレイ内に追加される。この追加動作も図２２に示されている。
【０２０１】
[0240]動作４２１０において、プローブフィンガープリントのさらなる未処理の領域が残っているかどうかが判定される。残っている場合、再現プロセス４２００は動作４２０４に戻る。残っていない場合、再現プロセス４２００は、動作４２１２において再現候補のアレイを返す。再現プロセスは４２１４において終了する。
【０２０２】
[0241]図２２に示すように、いくつかの実施形態において、オブジェクト自体はオブジェクトストア内に存在する。少なくとも一つの実施形態において、オブジェクトネットワークモデラインスタンス（マシン）あたり一つのみのオブジェクトストアが存在する。この実施形態によれば、オブジェクトネットワークモデラが複数のマシンにわたって展開されるとき、マシンあたり一つのオブジェクトストアが存在する。すべてのインデックスＴ’⊆Ｔは、ポインタを通じてオブジェクトを参照することによって、同じオブジェクトストアを共有する。
【０２０３】
[0242]いくつかの実施形態において、インデックスマネージャは、計算を効率的にするために、各インデックススロット内にフィンガープリントＶｆｐのコピーを維持する（Ｖｆｐもオブジェクト内に存在する）。これらの実施形態において、インデックススロットアレイは、メインメモリから１度だけフェッチすることができ、線形走査の継続時間にわたってＬ１キャッシュ内に適合することができる連続したメモリ片であり、これにより、オブジェクトのフィンガープリントにアクセスするためのすべてのオブジェクトポインタが逆参照されることが回避される。
【０２０４】
[0243]いくつかの実施形態において、インデックススロットアレイを下方に走査することは非常に効率的であり、Ｌ１メモリ及びレジスタに高速にアクセスする密なループ内にほんの少しの命令しか必要としない。これらの実施形態において、クエリエンジンは、２つのみの命令、すなわち、ｘ８６マイクロアーキテクチャの一部分である、ビットごとのＸＯＲ、及び、その後の固有のＰＯＰＣＮＴでハミング距離の計算を実行する。クエリエンジンがＱｆｐのハミング距離ｈ内にＶｆｐを有するためのインデックススロットを発見するときはいつでも、スロットのオブジェクトポインタが再現段階クエリ結果に添付される。
【０２０５】
[0244]いくつかの実施形態において、インデックスエンジンは、空のスロットが見つかるまで（Ｖｆｐ＝０）、又は、インデックススロットアレイが拡張されるアレイの終わりの時点に達するまで、インデックススロットアレイを下方に走査することによって、新たなオブジェクトを順列インデックスＴｉに挿入するように構成される。これらの実施形態において、インデックスエンジンは、オブジェクトポインタをＮＵＬＬに設定し、Ｖｆｐ＝０を設定することによって、順列インデックスＴｉからオブジェクトを削除するように構成される。さらに、これらの実施形態において、インデックスエンジンは、利用が一定の閾値を下回ったときに、インデックススロットアレイを縮小及びデフラグするように構成される。
【０２０６】
[0245]いくつかの実施形態において、インデックスマネージャは、最大効率及び最小量のメモリ断片化でインデックススロットアレイの一定の動的拡張及び低減を支援するために実装されている専用アロケータを実行する。これらの実施形態において、順列インデックスＴｉは、メインテーブルからの様々なサイズのインデックススロットアレイが存在している図２３の単純な図解に従って構造化されている。インデックスマネージャは、より大きい又はより小さいアロケータから新たなアレイを調べ出し、既存のアレイから新たなアレイへとフィンガープリント及びオブジェクトポインタをコピーし、必要に応じてデフラグし、その後、古いアレイをリサイクルのためにそのアロケータに戻すことによって、既存のインデックススロットアレイを、より大きい又はより小さいアレイと交換する。
【０２０７】
[0246]いくつかの実施形態において、クエリエンジンは、図２４に示すように、次元インデックスを通じてクエリ再現段階の間に直接次元インデックスによって迅速で高度にスケーラブルなオブジェクト検索を実施するように構成される。いくつかの実施形態において、直接次元インデックスは、順列インデックスと同じインデックス構造を使用して実装される。しかしながら、順列インデックスについて行われるように、複数のベクトル次元を処理して、それらの次元をフィンガープリント断片にまとめるのではなく、次元インデックスは、個々のベクトル次元ｄｉｍｎを、インデックス付け及び検索キーとして使用する。
【０２０８】
[0247]本明細書において参照されている場合、次元インデックスの全体集合は、Ｄ｛Ｄ１，Ｄ２，…Ｄｎ｝として表すことができる。いくつかの実施形態において、クエリエンジンは、次元ｄｉｍｎを使用してＶｉｎｔを識別する。所与のオブジェクトネットワークモデラ構成は、性能需要及び必要とされている保証される再現率のレベルに応じて、ゼロ又はそれ以上の次元インデックスを含み得る。
【０２０９】
[0248]一般的に、インデックスマネージャがＭ個の直接次元インデックスを使用するとき、インデックスマネージャは、ｄｉｍｎ，ｎ∈｛１…Ｍ｝をＤｉ＝ｎｎ∈｛１…Ｍ｝にインデックス付けする。クエリの再現段階の間に、クエリエンジンがＱｉｎｔをＶｉｎｔに対して照合するとき、クエリエンジンは、Ｑｉｎｔの最初のＭ個の次元をＶｉｎｔの最初のＭ個の次元に対して比較する。これは、すべてのｄｉｍｎ∈Ｑｉｎｔ，ｎ∈｛１…Ｍ｝が、ｄｉｍｎ∈Ｖｉｎｔ，ｎ∈｛１…Ｍ｝に対して照合されることを意味し、Ｍ２回の検索動作が必要になる。直接次元インデックスに関するクエリ実行時間はＭとともに二次的に増大するため、Ｍを可能なかぎり小さいままにすることが有益である。
【０２１０】
[0249]高い再現率を必要とするアプリケーションについて、インデックスマネージャはＭを、１００％の再現率に対するＶｉｎｔに使用される最大数のベクトル次元まで、必要とされるかぎり高く設定することができる。それゆえ、いくつかの実施形態において、図２０に示す再現候補ボックスを右端まで拡張することが可能であり、性能が犠牲にはなるが、すべての偽陰性がなくなる。
【０２１１】
[0250]所与のアプリケーションａについて、Ｍ＞ρａが十分な再現率をもたらすような閾値ρａが存在することが諒解される。同時に、Ｍ＜τａが十分な性能をもたらすような閾値τａが存在する。オブジェクトネットワークモデラは、ρａ＜Ｍ＜τａであるとき、アプリケーションの次元性の問題を解決する。ρａ＜Ｍ＜τａを満たすために、各マシンが部分集合Ｄ’⊆Ｄにサービスする複数のマシンにわたってオブジェクトネットワークモデラを展開する必要があり得る。
【０２１２】
[0251]いくつかの実施形態において、クエリエンジンは、図２５に示すように、順列インデックス及び直接次元インデックスを介して識別される再現候補を統合するように構成される。すべての順列インデックスＴｉ∈Ｔ及び次元インデックスＤｉ∈Ｄは、オブジェクトストア内のすべてのオブジェクトの独立したインデックス付け及び検索を可能にする。そのため、オブジェクトＡは、Ｖｆｐの複数の異なる「ビュー」（重要領域）によってＴにインデックス付けされ、Ｖｉｎｔの複数の異なる次元によってＤにインデックス付けされる。クエリエンジンはすべてのＴ及びＤについてクエリＱを繰り返すため、完全に、複数の（又はすべての）インデックスにおいてオブジェクトＡが発見されることが可能である。それゆえ、任意の候補オブジェクトが最終的な候補集合内でただ１度だけ現れるように、再現段階は、クエリエンジンがすべてのインデックスからの個々の候補集合を統合及び重複排除するまで完了しない。
【０２１３】
[0252]いくつかの実施形態において、この再現プロセスを実行するために、クエリエンジンは、すべてのインデックスからのすべての結果候補をトラバースし、重複排除ハッシュに置くように構成される。いくつかの静的に割り当てられた重複排除ハッシュが、マルチスレッド処理実行を可能にするために利用可能であり、任意の結果集合に最も計算効率的に対応するように、種々のサイズのハッシュが存在する。これらの実施形態は、他のスレッドのキャッシュ無効化を最小限に抑えながら、現在のスレッドについてほとんどの活動を最内ＣＰＵキャッシュ内に維持する。さらに、これらの実施形態において、クエリエンジンは、クエリ再現段階の最終結果として、統合及び重複排除された候補集合を返す。
【０２１４】
[0253]図１９を参照して上述したように、本明細書に開示されている実施形態は、クエリ実行中に適合段階を実行するように構成される。一つの実施形態において、クエリエンジンが、適合段階を実行する。この実施形態において、再現段階が可能なかぎり多くの可能性の高い類似度一致を収集した後、適合段階が、Ｖｉｎｔにおける次元エイリアシングによって隠されたものを除いて、すべての偽陽性をフィルタリング除外する。いくつかの実施形態において、クエリエンジンは、プローブオブジェクト、及び、再現候補の集合内に残っている各オブジェクトについて式１１を計算することによって、偽陽性を識別及び削除する。一つの実施形態による適合段階が、図２６に示されている。
【０２１５】
[0254]図１９を参照して上述したように、本明細書に開示されている実施形態は、クエリ実行中にアンチエイリアシング段階を実行するように構成される。一つの実施形態において、クエリエンジンが、アンチエイリアシング段階を実行する。２６ビット特徴符号化の結果としてのＶｉｎｔにおけるベクトル次元エイリアシングに起因して、偽陽性が適合段階の間に隠される可能性があることが諒解される。すなわち、Ｓｉｍ（Ｑｉｎｔ，Ｖｉｎｔ≧）τは、Ｓｉｍ（Ｑｅｘｔ，Ｖｅｘｔ）≧τを暗示しない。一般的に、次元エイリアシングは、式１４のように表すことができる。
δ＝Ｓｉｍ（Ｑｉｎｔ，Ｖｉｎｔ）−Ｓｉｍ（（Ｑｅｘｔ，Ｖｅｘｔ），    τ＞＞δ＞０        （１４）
【０２１６】
[0255]ベクトル比較についてδは通常小さく、ゼロであることが多いが、クエリエンジンは、絶対的な精度を必要とするアプリケーションに最終クエリ結果を返す前に、任意選択のアンチエイリアシング段階を適用するように構成されてもよい。アンチエイリアシングは、図２７に示すように、適合段階において生成された結果にフィルタＳｉｍ（Ｑｅｘｔ，Ｖｅｘｔ）≧τを適用することによって実施される。いくつかの実施形態において、クエリエンジンは、Ｖｅｘｔがアンチエイリアシングを可能にするためにオブジェクトメタデータとして含まれることを必要とする。
【０２１７】
クエリ実行の形式化された要約
[0256]形式的に要約するために、少なくとも一つの実施形態によるクエリ実行は、Ｖがインデックス付けされたベクトルの完全な集合を示すものとし、Ｃが順列インデックス及び次元インデックスを使用して再現段階において生成される候補の集合を示すものとする。さらに、Ｓτが、式１５に記載されているように、クエリＱｉｎｔに対するその類似度がτ以上である、すなわち、陽性クラスであるベクトルの実際の集合を示すものとする。
Ｓτ＝｛Ｖｉｎｔ∈Ｖ｜Ｓｉｍ（Ｑｉｎｔ，Ｖｉｎｔ）≧τ｝        （１５）
【０２１８】
[0257]（Ｆ，ｆＲ）として構成される所与の順列インデックスＴ＝｛Ｔ１，Ｔ２，…，Ｔｎ｝について、クエリの文脈に適用されるときにＱｉｎｔがいかなる偽陰性ももたらさないような、最小類似度閾値γが存在する。したがって、陽性集合Ｓγにおける任意のＶｉｎｔとＱｉｎｔとの間の差は、任意のＶｆｐとＱｆｐとの間で少なくとも一つの重要領域Ｒｉが完全なままであることを保証するのに十分に小さい。
∃γ：Ｃ⊇Ｓγ        （１６）
【０２１９】
[0258]クエリの文脈に適用されるときにＱｉｎｔが常に偽陰性をもたらすようなより小さい類似度閾値γ−δも存在する。ここで、拡張された陽性集合Ｓγ−δ内の何らかのＶｉｎｔとＱｉｎｔとの間の差は、ＶｆｐとＱｆｐとの間のすべての重要領域Ｒｉ∈（０…Ｎ）における変更を引き起こすのに十分に大きく、したがって、Ｖｆｐを任意のテーブルＴｎにおいて回復不可能にする。
【数５】
2019053772.tif 000012
【０２２０】
[0259]これらの概念は図２８に示されている。類似度τ≧γを有するベクトルを返すようにクエリＱｉｎｔに対する期待値を設定すると、再現候補Ｃ内で全体集合Ｓγを捕捉することが可能である。異なるクエリは、「再現の可能性」の中にあるままで水平に動くことが可能である、Ｃの実線及び破線の境界の間の「Ｃの変動性」によって示される、同じ構成に対してわずかに異なる再現率特性を有する。
【０２２１】
[0260]類似度閾値をτ≧γに下げることによって期待値を上昇させるとき、陽性クラスの部分（中心から２番目の実線の同心円）がＣの内部に入り得、陽性クラスの他の部分は、再現の可能性の中でＣの変動する範囲の外側になり得ることが分かる。τがγよりもほんの下になり、τ→γ−δとして確率が１をわずかに下回るとき、ゼロをわずかに上回る確率で偽陰性が時折発生する。
【０２２２】
[0261]類似度閾値をτ＜γ−δに下げることによって再現率期待値をさらに上昇させるとき、偽陰性のないクエリ結果が可能である陽性クラスの境界を、Ｓγ−δがマークすることが分かる。τ＜γ−δのようにＳγ−δを超えるとき、すべてのクエリ結果が偽陰性の問題を被ることが理解される。
【０２２３】
[0262]δの値は、インデックス付けされたベクトルＶの性質に応じて決まり、一般的に、クエリごとに変動する。Ｐ（ｆｎ｜Ｑｉｎｔ，Ｖ）が、ベクトルＶの特定の集合に対するクエリＱｉｎｔを所与とした偽陰性の確率を示すものとする。このとき、τ≧γであることによって、偽陰性がないことが保証され、τ＜γ−δであることによって、１以上の偽陰性があることが保証される。γとγ−δとの間の空間において、確実ではないが、クエリが偽陰性の問題を被る可能性がある。
【数６】
2019053772.tif 000013
【０２２４】
[0263]関数λ（τ）の値はτ≒γについて０に近く、τ≒γ−δについて１に近い。
【０２２５】
[0264]一例として、図２８を再び参照すると、γ＝０．９且つδ＝０．７である場合、Ｖに対するクエリＱｉｎｔは、０．９以上の類似度を有する、すなわち、τ≧０．９である一致を求めるかぎり、決して偽陰性を返さない。（最内円は常にＣによって含まれる。）一致する基準を広げ、τ＝０．０を有する一致を求める場合、１００％の再現率は得られない場合がある、すなわち、偽陰性の可能性がある。τ＝０．７のさらにより広いクエリでは偽陰性の確率がより高くなり、以下同様である。（ここでは、最内円の外部のλ（τ）領域に入っている。）最後に、類似度閾値τ＝０．９−０．７＝０．２以下を有するクエリは常に偽陰性の問題を被る。
【０２２６】
[0265]再現段階において偽陰性を最小限に抑えるという主目的を満たすためには、γを最小化し、δを最大化し、λ（τ）を最大限に凸状にする（可能なかぎり遅く１に向かうようにする）ようにしなければならない。実際には、γ、δ及びλ（τ）を分析的に定量化することは困難であり得る。それらの変数がクエリＱｉｎｔ及びインデックス付けされたベクトルＶの性質に依存することに起因して、それらの変数を絶対値に関して定義することは意味を成さない。しかしながら、それらの変数は、全体的な目的を達成するために順列インデックス付け及び次元インデックス付けを使用することに関して一定の定性的陳述が行われることを可能にする。
【０２２７】
[0266]順列インデックスＴについて（Ｆ，ｆＲ）を選択することを通じてγを直接的に制御し、δを間接的に制御することができる。一般的に、フィンガープリントＶｆｐ内の断片Ｆの数を増大させることによって、各断片はより小さくなり、それゆえ、Ｆ−ＬＳＨビット変更による影響をより受けにくくなる。同時に、重要領域あたりの断片の数ｆＲを増大させることによって、Ｒｉが効率的な検索に十分なビットを含むことが保証される（すなわち、線形走査を必要とする平均インデックススロットアレイの長さが最小化される）。Ｖｆｐがよりロバストになる結果として、γが低減する、すなわち、偽陰性の危険性を冒すことなくより小さい類似度閾値を指定することができる。しかしながら、δ及びλ（τ）は間接的に改善されるが、それらの変数は、順列インデックスを拡張するときの主目標ではない。
【０２２８】
[0267]代わりに、次元インデックスＤ＝｛Ｄ１，Ｄ２，…Ｄｎ｝を拡張することによって、δ及びλ（τ）を制御することができる。一般的に、Ｖｉｎｔのより多くの次元をインデックス付けすることによって、Ｓのより大きい部分がクエリＱｉｎｔによって発見可能になることが保証され、したがって、δが増大する、すなわち、個々のベクトル次元が直接的にインデックス付けされるため、ここですべての重要領域におけるビット変更に起因して順列インデックスＴから隠されているＳの部分が見えるようになる。最も強く重み付けされている次元がＤにおいてインデックス付けされている（また、問い合わせされている）ものであることを保証することによって、λ（τ）が最大限に凸状になる。明らかに、次元インデックスを拡張することによってもγには良い影響があるが、通常、順列インデックスを使用するよりもコストが高くなる。それゆえ、次元インデックスの主目的は、δ及びλ（τ）を制御することである。
【０２２９】
[0268]順列インデックスＴは、Ｃｏｍｂ（Ｆ，ｆＲ）に起因して非常に大きくなる可能性があり、高いクエリ性能でより低いγを達成するためにより多くの並列計算及びメモリリソースが必要になることも留意される。クエリ性能は劣るが、より低いリソース（ハードウェア）コストで次元インデックスＤのみによって同じ再現率特性を達成することも可能であり得る。極端なところでは、インデックス付けされている次元の数ＭをＶｉｎｔ内の次元の数に等しくすることによって、次元インデックスＤのみを展開することができる。この構成は明らかにより優れた再現率特性（γ→０）を有するが、Ｖｉｎｔについて構成される次元の数が小さくないかぎり極端に非効率的でもある。（Ｖｉｎｔが小さいシステムについては、排他的にＤのみを介してインデックス付けすることが、実際には最適な解決策であり得る。）
【０２３０】
[0269]適切な構成を選択することは、（Ｆ，ｆＲ）によるＴのサイズＮを、ＭによるＤのサイズと平衡させるという問題である。許容可能な最大のクエリ待ち時間及びハードウェアコスト、アプリケーションに対する偽陰性の全体的な影響、偽陰性の許容可能な確率、並びに、重要なことには、必要とされるファジーマッチングの度合いを考慮に入れて、確かな情報に基づく選択が行われるべきである。必要とされるファジーマッチングの度合いは、ファジーマッチングアプリケーションが、再現率を保証して、たとえば、τ≧０．９において動作する必要がある場合、γ＝０．９を達成するコストは、たとえば、γ＝０．５を達成するコストよりもはるかに低いため、重要である。さらに、アプリケーションが再現率を保証することなく適切に動作することができる場合、実施態様はなお単純である。
【０２３１】
[0270]高い適合率を達成することは、適切なフィルタ関数をＣに適用するという問題である。Ｖｉｎｔにアクセスすることができるため、Ｃにおいて返されるオブジェクトの一つとして、適合率の高い結果Ｒａを得るために、Ｓｉｍ（Ｑｉｎｔ，Ｖｉｎｔ）をＣに直接的に適用することができる。
Ｒａ．＝｛Ｖｉｎｔ∈Ｃ｜（Ｓｉｍ（Ｑｉｎｔ，Ｖｉｎｔ）≧τ｝        （１９）
【０２３２】
[0271]一般的に、Ｒａは、ＶｅｘｔからＶｉｎｔを符号化するときの特徴エイリアシングに起因して、非常に低いがゼロではない確率で偽陽性を含むと予測される。いかなる状況下でも偽陽性のない結果Ｒを得るために、Ｒａに別のフィルタ関数が適用される。
Ｒ＝｛Ｖｅｘｔ∈Ｒａ｜Ｓｉｍ（Ｑｅｘｔ，Ｖｅｘｔ）≧Ｔ｝        （２０）
【０２３３】
[0272]エイリアシングされている結果ＲａからＶｅｘｔを抽出することは、メタストアを使用する補助検索メカニズムを伴うことに留意されたい。ＲａからＶｅｘｔを抽出することは、Ｖｅｘｔがディスクから取り出されなければならないため資源集約的であり、一方、Ｖｉｎｔは、Ｖがメモリ内に存在するため、容易に利用可能である。そのため、Ｖｅｘｔを取り出すことは、フィルタＳｉｍ（Ｑｅｘｔ，Ｖｅｘｔ）≧τを実際に適用するよりもはるかにより費用がかかる。
アーキテクチャ概要及びデータ構造
【０２３４】
[0273]本明細書に記載されているオブジェクトネットワークモデラは、オブジェクトアソシエーション及び類似度照合のために積極的にメモリを利用する。高い性能を達成するために、すべてのインデックスはメモリ内全体において、ハイブリッドハッシュ／線形ルックアップテーブルとして存在することができ、将来システムを起動するときに初期化を加速するために、必要に応じてディスクがフラッシュされる。オブジェクトネットワークモデラのすべての構成要素は、一つの実施例において、６４ビットターゲットプラットフォーム及び企業グレードサーバ容量を仮定して作成される。（必要とされるメモリ容量は、消費者グレードハードウェアでもすぐに利用可能になっている。）
【０２３５】
[0274]いくつかの実施形態において、オブジェクトストア２１４は、オブジェクトネットワーク内のオブジェクトを記述する情報を記憶するように構成される。この情報の例は、オブジェクト属性、ベクトル、及びメタデータを含む。これらの実施形態において、オブジェクトストア２１４は、耐久性のためにディスクミラーリングを使用しているメモリ内に存在する。他の実施形態において、オブジェクトストア２１４は、揮発性メモリと不揮発性メモリの両方の中に存在し、したがって、特定のタイプのメモリには限定されない。たとえば、メタストア構成要素は、ディスク上にのみ存在してもよい。いくつかの実施形態において、オブジェクトネットワークモデラ２０２は、データライトスルー技法を使用してメモリ内オブジェクトストア２１４及びそのディスクベースのシャドウコピーを同期させるように構成される。これらの実施形態において、オブジェクトストア２１４は、コミットログ及び動作バッチのストリーミングされるディスクキャッシングを使用して性能について最適化される。
【０２３６】
[0275]いくつかの実施形態によれば、オブジェクトネットワークモデラの最小限の配備は、オブジェクトストア２１４と、オブジェクトインデックスと、逆インデックスとを含む。これらの構成要素の各々は、下記に詳細に説明する。
【０２３７】
[0276]図２９は、いくつかの実施形態による、図２を参照して上述したオブジェクトネットワークモデラ２０２のようなオブジェクトネットワークモデラによって利用されるデータ構成要素を示す。図示されているように、図２９のデータ構成要素は、オブジェクトインデックスと、逆インデックスと、１以上の順列インデックスと、１以上の次元インデックスと、オブジェクトストアと、複数のインデックススロットアレイアロケータと、複数のベクトルアロケータとを含む。オブジェクトストアは、１以上のオブジェクトと、メタストアとを含む。１以上のオブジェクトは各々、１以上のベクトルを含む。１以上のベクトルは各々、１以上の特徴を含む。いくつかの実施形態において、オブジェクトインデックス、逆インデックス、１以上の順列インデックス、及び、１以上の次元インデックスは、図２を参照して上述したインデックスストア２１６に対応する。
【０２３８】
インデックスストア
[0277]上記で言及したように、いくつかの実施形態において、オブジェクトネットワークモデラは、オブジェクトアソシエーション及び類似度照合のために積極的にメモリを利用する。たとえば、これらの実施形態において、オブジェクトネットワークモデラは、起動時に初期化を加速するために、必要に応じてディスクをフラッシュして、メモリ内のすべてのインデックスをハイブリッドハッシュ／線形ルックアップテーブルとして割り当てることによって、高い性能を達成する。いくつかの実施形態において、オブジェクトネットワークモデラのすべての構成要素は、６４ビットターゲットプラットフォーム及び企業グレードサーバ容量向けに構成されるが、実施形態は、特定のターゲットプラットフォーム又はサーバには限定されない。
【０２３９】
[0278]これらの実施形態において、オブジェクトインデックス２００と逆インデックス２０２は両方ともメモリベースである。オブジェクトネットワークモデラの配備は、類似度照合向けに構成される必要はなく、その場合、黙示的オブジェクトアソシエーション特徴は利用可能でない。しかしながら、ほとんどの配備シナリオは、一つ若しくは複数の順列インデックス２０４又は一つ若しくは複数の次元インデックス２０６を使用する何らかの形態の類似度照合を含むことになる。
【０２４０】
[0279]いくつかの実施形態において、オブジェクトネットワークモデラ、より詳細には、図２を参照して上述したインデックスマネージャ２１２のようなインデックスマネージャが、図３０に示すデータ構造を使用して、図２を参照して上述したインデックスストア２１６のようなインデックスストアを実装するように構成される。これらの実施形態において、インデックスストア内の各インデックスは、同様のインデックス付け及び検索メカニズムを使用する。さらに、これらの実施形態において、ラインレール（ｌｉｎｅｒａｉｌ）構造が、インデックスストア内の各インデックスの基礎を形成する。表２は、いくつかの実施形態によるラインレール構造の属性をリストしている。
【表６】
2019053772.tif 000014
【０２４１】
[0280]これらの実施形態において、ラインレール構造は、テーブル識別、テーブルモード、簿記、及びロック支援をもたらす。加えて、これらの実施形態において、順列（ｐｅｒｍ）属性は、オブジェクトネットワークモデラが検索ハンドルからテーブル検索キーをどのように形成するかを定義し、これは、テーブルモードに応じて決まる。
順列インデックスについて、ハンドルはフィンガープリントである：ｈａｎｄｌｅ＝Ｖｆｐ
次元インデックスＤ＿ｎについて、ハンドルは次元である：ｈａｎｄｌｅ＝ｄｉｍｎ  ｏｆ  Ｖｉｎｔ
オブジェクトインデックスについて、ハンドルはＯＢＩＤの高部である：ｈａｎｄｌｅ＝ｈｉｇｈ６４（ＯＢＩＤ）。
【０２４２】
[0281]いくつかの実施形態において、下記表３に定義されている順列記述子が、インデックスマネージャ又はクエリエンジンのような、インデックスと相互作用するオブジェクトネットワークモデラ構成要素がどのようにハンドル内のビットを識別し、ビットを再構築してインデックスレコードのうちの一つにマッピングするインデックスキーにするかを指定する。順列インデックスについて、オブジェクトネットワークモデラ構成要素は、Ｖｆｐの断片をインデックスキーに再構成する。他のインデックスについて、オブジェクトネットワークモデラ構成要素は、テーブルのｎｒｏｗｓを照合するためのハンドルのサイズを制限するために、ビットマスクをそれらのシャッフルされていないハンドルに適用する。たとえば、ｎｒｏｗｓ＝２２２＝４１９４３０４で構成されるテーブルは、ハンドルからインデックスキーを形成するために２２ＬＳＢ＝１のビットマスクを使用する。
【表７】
2019053772.tif 000015
【０２４３】
[0282]いくつかの実施形態において、下記表４に定義されているルックアップテーブルｂａｓｅは、長さｎｒｏｗｓのインデックスライン構造のアレイである。これらの実施形態において、オブジェクトネットワークモデラ構成要素は、インデックスキーによって支持されているものに対して動作するインデックスラインを選択する。さらに、これらの実施形態において、インデックスマネージャは、ラインレール構造内のインデックスラインの全体集合に関する簿記属性を維持し、個々のインデックススロットアレイの使用を統制する、インデックスライン構造内に保持されている属性を維持する。そのため、これらの実施形態において、ラインレールのｎｏｂｊ属性は、したがって、すべてのインデックスライン内のｎｏｂｊ属性の合計であり、ラインレールのｎｓｌｏｔｓは、すべてのインデックスライン内のｓｚ属性の合計である。
【表８】
2019053772.tif 000016
【０２４４】
[0283]いくつかの実施形態において、オブジェクトネットワークモデラ構成要素（たとえば、インデックスマネージャ又はクエリエンジンのような、オブジェクトネットワークモデラの態様を実行しているスレッド）は、マルチコア実行環境において最大限の並列性を可能にするためにテーブルロックを実施するように構成される。したがって、これらの実施形態において、複数のスレッドが同じラインレールに同時にアクセスすることを可能にされる。過剰なリソースの使用を回避するために、いくつかの実施形態において、個々のインデックスラインがそのインデックスラインについて現在進行中の特定の活動に関する情報を保持しながら、ミューテックス及び状態インスタンスがラインレール全体にわたって共有される。いくつかの実施形態によれば、任意の所与の時点において、インデックスラインは、読み出し又は書き込みすることができるが、両方はできない。また、いくつかの実施形態においては、複数のスレッドが同じインデックスラインを同時に読み出すことができるが、一方で、単一のスレッドしかインデックスラインに書き込むことができない。
【０２４５】
[0284]いくつかの実施形態において、オブジェクトネットワークモデラ構成要素は、インデックススレットアレイａｒｒに対する読み出し動作が、他のスレッドがａｒｒに書き込んでいないかぎり、又は、ａｒｒに対して書き込み待ちでないかぎり、進行することを可能にするように構成される。必要な場合、オブジェクトネットワークモデラ構成要素は、最初にｗｒｅｑの高速チェックを実施し、ｗｒｅｑがゼロでない場合、現在ロックされているｗｂｕｓｙロックをブロックすることによって、現在の書き込み動作が完了するまで、読み出し動作を遅延させる。通常、ｗｒｅｑはゼロであり、ｗｂｕｓｙに対するブロックは必要ない。補助ｗｂｕｓｙロックを含むすべての状態変数に対するアトミックアクセスは、ｖｌｏｃｋを介して保証される。読み出し動作が進行することを可能にされると、インデックスラインのｒｃｎｔが１だけ増分される。最大で６５５３５個までの複数のリーダが許容される。
【０２４６】
[0285]いくつかの実施形態において、オブジェクトネットワークモデラ構成要素は、読み出し動作の完了を受けて、インデックスラインのｒｃｎｔを１だけ減分するように構成される。ｒｃｎｔがゼロに達した場合、この状態を検出したオブジェクトネットワークモデラ構成要素は、ｒｚｅｒｏイベントを他のオブジェクトネットワークモデラ構成要素（たとえば、書き込み待ちの別のスレッド）にブロードキャストするように構成され、これにより、待っている構成要素に、その構成要素がその動作を進行させることができることを通知する。インデックスラインのｒｃｎｔに対するアトミックアクセスは、ラインレールのｖｌｏｃｋを介して保証される。
【０２４７】
[0286]いくつかの実施形態において、オブジェクトネットワークモデラ構成要素（インデックスマネージャを実行しているスレッドなど）は、インデックススロットアレイａｒｒに対する書き込み動作が、他のスレッドがａｒｒに書き込んでいないかぎり、又は、ａｒｒに対して書き込み待ちでないかぎり、進行することを可能にするように構成される。必要な、オブジェクトネットワークモデラ構成要素は、別の同時の書き込み動作が完了するまで、書き込み動作を遅延させる。オブジェクトネットワークモデラ構成要素が、書き込み動作が進行することを可能にすると、インデックスラインのｗｒｅｑが１だけ増分され、ラインレールのｗｂｕｓｙｃｎｔも１だけ増分される。一つの実施形態において、ｗｒｅｑとｗｂｕｓｙｃｎｔは両方ともシングルトンセマフォであり、それゆえ、インデックスラインあたり、またラインレールあたりの同時の書き込み動作は一つだけであり得る。次に、ｗｂｕｓｙロックが取得され、インデックスラインのｒｃｎｔがゼロであることが検証される。すべての状態変数に対するアトミックアクセスは、ラインレールのｖｌｏｃｋを介して保証される。この時点においてｒｃｎｔがゼロでない場合、書き込んでいるオブジェクトネットワークモデラ構成要素（たとえば、スレッド）は、現在のリーダの最後のものが完了するまでスリープ状態に置かれる。書き込んでいるオブジェクトネットワークモデラ構成要素がｗｂｕｓｙロックを保持しているため、新たな読み出し動作が進行することは許可されない。その読み出しを完了させる最後のスレッドがｒｃｎｔをゼロに設定し、検出しているオブジェクトネットワークモデラ構成要素がｒｚｅｒｏイベントをスリープ状態の書き込みオブジェクトネットワークモデラ構成要素にブロードキャストし、その後、スリープ状態の書き込みオブジェクトネットワークモデラ構成要素は起動して書き込み動作を進行させる。
【０２４８】
[0287]書き込み動作が完了すると、書き込みオブジェクトネットワークモデラ構成要素は、インデックスラインのｗｒｅｑ及びラインレールのｗｂｕｓｙｃｎｔを減分し、インデックスラインのｗｂｕｓｙロックを解放する。アトミックアクセスは、ラインレールのｖｌｏｃｋを用いて保証される。この時点で、オブジェクトネットワークモデラ構成要素は、その排他的アクセスを解放しており、他のオブジェクトネットワークモデラ構成要素によるすべての他の動作を進行することができる。
【０２４９】
[0288]いくつかの実施形態において、オブジェクトネットワークモデラ構成要素が読み出しのためにインデックスラインを取得すると、ａｒｒインデックススロットアレイは、オブジェクトネットワークモデラ構成要素によって解放されるまで一定のままであることを保証される。これらの実施形態において、オブジェクトネットワークモデラ構成要素は、ａｒｒを線形的に、ｒｄｘから始まってｗｄｘの直前で終わるように走査することによって検索を実施する。オブジェクトネットワークモデラ構成要素は、ラインレールのモードに応じて、下記に記載するように読み出し動作を実行するように構成される。
【０２５０】
[0289]ラインレールのモード＝ＰＥＲＭＵＴＡＴＩＯＮ（順列）の場合、オブジェクトネットワークモデラ構成要素は、インデックススロットを、下記表５に記載されているｈａｍｓｌｏｔ構造と解釈する。読み出し動作の実施中、オブジェクトネットワークモデラ構成要素は、ｈａｍｓｌｏｔアレイａｒｒ内のすべてのスロットを順次、ｒｄｘから始まってｗｄｘの直前で終わるように訪れる。スロットのオブジェクトポインタがＮＵＬＬである場合、これはスロットが消去されていることを示し、オブジェクトネットワークモデラ構成要素は、そのスロットを飛ばす。ポインタがＮＵＬＬでない場合、オブジェクトネットワークモデラ構成要素は、スロットのフィンガープリントをプローブフィンガープリントと比較する。スロットのフィンガープリントに対するプローブフィンガープリントのハミング距離が構成される閾値内である場合、オブジェクトネットワークモデラ構成要素は、スロットのオブジェクトポインタを、再現候補の結果アレイに添付する。
【表９】
2019053772.tif 000017
【０２５１】
[0290]ラインレールのモード＝ＤＩＭＥＮＳＩＯＮ（次元）の場合、オブジェクトネットワークモデラ構成要素は、インデックススロットを、下記表６に記載されているｄｉｍｓｌｏｔ構造と解釈する。読み出し動作の実施中、オブジェクトネットワークモデラ構成要素は、ｄｉｍｓｌｏｔアレイａｒｒ内のすべてのスロットを順次、ｒｄｘから始まってｗｄｘの直前で終わるように訪れる。スロットのオブジェクトポインタがＮＵＬＬである場合、これはスロットが消去されていることを示し、オブジェクトネットワークモデラ構成要素は、そのスロットを飛ばす。ポインタがＮＵＬＬでない場合、オブジェクトネットワークモデラ構成要素は、スロットの次元ハンドルをプローブ次元ハンドルと比較する。これら２つのハンドルが所定の関係に一致する（たとえば、それらのハンドルが等しい）場合、オブジェクトネットワークモデラ構成要素は、スロットのオブジェクトポインタを、再現候補の結果アレイに添付する。
【表１０】
2019053772.tif 000018
【０２５２】
[0291]ラインレールのモード＝ＯＢＩＤの場合、オブジェクトネットワークモデラ構成要素は、インデックススロットを、下記表７に記載されているｏｂｊｓｌｏｔ構造と解釈する。読み出し動作の実施中、オブジェクトネットワークモデラ構成要素は、ｏｂｊｓｌｏｔアレイａｒｒ内のすべてのスロットを順次、ｒｄｘから始まってｗｄｘの直前で終わるように訪れる。スロットのオブジェクトポインタがＮＵＬＬである場合、これはスロットが消去されていることを示し、オブジェクトネットワークモデラ構成要素は、そのスロットを飛ばす。ポインタがＮＵＬＬでない場合、オブジェクトネットワークモデラ構成要素は、以下のプロセスのうちの一つを実行する。
１．ＳＵＢＩＤがプローブ内で指定されている（したがって、単一のオブジェクト体現形を要求している）場合、オブジェクトネットワークモデラ構成要素は、オブジェクトのオブジェクトＩＤハンドルｏｂｉｄ＿Ｈを、プローブＯＢＩＤの上位６４ビットと比較する。オブジェクトＩＤハンドルとプローブＩＤの上位６４ビットの２つが所定の関係に一致する（たとえば、それら２つが等しい）とオブジェクトネットワークモデラ構成要素が判定する場合、オブジェクトのオブジェクトポインタｏｂｊｅｃｔが、ＯＢＩＤの下位６４ビットを比較するために逆参照される。オブジェクトポインタとＯＢＩＤの下位６４ビットの２つが所定の関係に一致する（たとえば、それら２つが等しい）とオブジェクトネットワークモデラ構成要素が判定する場合、オブジェクトポインタが、オブジェクトのＳＵＢＩＤをプローブのＳＵＢＩＤと比較するために再び逆参照される。オブジェクトのＳＵＢＩＤとプローブのＳＵＢＩＤの２つが所定の関係に一致する（たとえば、それら２つが等しい）とオブジェクトネットワークモデラ構成要素が判定する場合、一致が宣言され、一致するオブジェクトのＮＵＬＬ番兵終端アレイにおいて単一のヒットが返される。
２．ＳＵＢＩＤがプローブにおいて指定されていない場合、ＳＵＢＩＤ一致を除いて上記と同じプロセスがオブジェクトネットワークモデラ構成要素によって実行される。結果は、プローブのＯＢＩＤに一致する任意のオブジェクトのＮＵＬＬ番兵終端アレイである。
【表１１】
2019053772.tif 000019
【０２５３】
[0292]ラインレールのモード＝ＳＵＢＩＤの場合、オブジェクトネットワークモデラ構成要素は、インデックススロットを、下記表８に記載されているｏｂｊｓｌｏｔ構造と解釈する。読み出し動作の実施中、オブジェクトネットワークモデラ構成要素は、ｏｂｊスロットアレイａｒｒ内のすべてのスロットを順次、ｒｄｘから始まってｗｄｘの直前で終わるように訪れる。スロットのオブジェクトポインタがＮＵＬＬである場合、これはスロットが消去されていることを示し、オブジェクトネットワークモデラ構成要素は、そのスロットを飛ばす。ポインタがＮＵＬＬでない場合、オブジェクトネットワークモデラ構成要素は、ｏｂｊスロットのサブオブジェクトＩＤハンドルｏｂｉｄ＿Ｈを、プローブＳＵＢＩＤの上位６４ビットと比較する。サブオブジェクトＩＤハンドルとプローブＳＵＢＩＤの上位６４ビットの２つが所定の関係に一致する（たとえば、それら２つが等しい）とオブジェクトネットワークモデラ構成要素が判定する場合、ｏｂｊスロットのオブジェクトポインタｏｂｊｅｃｔが、オブジェクト及びプローブのＳＵＢＩＤの下位６４ビットを比較するために逆参照される。ポインタと下位６４ビットの２つが所定の関係に一致する（たとえば、それら２つが等しい）とオブジェクトネットワークモデラ構成要素が判定する場合、一致が宣言され、一致するプローブのＳＵＢＩＤのオブジェクトのＮＵＬＬ番兵終端アレイにおいて単一のヒットが返される。
【表１２】
2019053772.tif 000020
【０２５４】
[0293]いくつかの実施形態において、オブジェクトネットワークモデラ構成要素（インデックスマネージャを実行しているスレッドなど）が書き込みのためにインデックスラインを取得すると、ａｒｒインデックススロットアレイは、他のスレッドによって読み出されないことが保証され、一貫性のない検索が行われる危険なく書き込み動作が完了することが可能である。これらの実施形態において、オブジェクトネットワークモデラ構成要素は、オブジェクトポインタ及びオブジェクトのオブジェクトＩＤハンドルをｗｄｘにあるインデックススロットに記憶することによって、オブジェクトをインデックスに書き込む動作を実行する。オブジェクトＩＤハンドルは、インデックスライン検索動作について上述したように、テーブルモードに依存する。
【０２５５】
[0294]いくつかの実施形態において、ｗｄｘがインデックススロットアレイの終端を越えたスロットを参照する場合、オブジェクトネットワークモデラ構成要素は、インデックススロットアレイアロケータの一つを使用してより大きいアレイを割り当てる（図２９参照）。次に、これらの実施形態に従って、オブジェクトネットワークモデラ構成要素は、必要に応じてデフラグも実施しながら、古いアレイを新たなアレイにコピーする。オブジェクトネットワークモデラ構成要素はその後、古いアレイの割り当てを解除する。いくつかの実施形態において、オブジェクトネットワークモデラ構成要素はまた、必要に応じて簿記属性もインデックスライン及びラインレール内で維持及び更新する。
【０２５６】
[0295]いくつかの実施形態において、オブジェクトネットワークモデラ構成要素（インデックスマネージャを実行しているスレッドなど）が書き込みのためにインデックスラインを取得すると、ａｒｒインデックススロットアレイは、他のスレッドによって読み出されないことが保証され、一貫性のない検索が行われる危険なく消去動作が完了することが可能である。これらの実施形態において、オブジェクトネットワークモデラ構成要素は、インデックススロットアレイを、ｒｄｘから始まって、消去されるべきオブジェクトのオブジェクトポインタがインデックススロットアレイ内のものに一致するまで走査することによって、インデックスからのオブジェクトの消去動作を実行する。さらに、これらの実施形態において、消去されるべきオブジェクトが見つかった場合、オブジェクトネットワークモデラ構成要素は、インデックススロットのオブジェクトＩＤハンドルをゼロに設定し、オブジェクトポインタをＮＵＬＬに設定する。この設定によって、将来の検索動作によって無視されることになる「穴」がインデックススロットアレイ内に作成される。一致するオブジェクトが発見及び消去されると、消去動作が完了する。ｗｄｘに達すると連続的な走査は停止する。これは、参照されるオブジェクトがインデックス付けされておらず、動作が実施されないことを意味する。いくつかの実施形態において、オブジェクトネットワークモデラ構成要素はまた、必要に応じて簿記属性もインデックスライン及びラインレール内で維持及び更新する。
【０２５７】
[0296]いくつかの実施形態において、インデックススロットアレイ内のアクティブなオブジェクトの数が閾値を下回った場合、オブジェクトネットワークモデラ構成要素は、インデックススロットアレイアロケータの一つを使用してより小さいアレイを割り当てる。次に、これらの実施形態に従って、オブジェクトネットワークモデラ構成要素は、必要に応じてデフラグも実施しながら、古いアレイを新たなアレイにコピーする。オブジェクトネットワークモデラ構成要素はその後、古いアレイの割り当てを解除する。
【０２５８】
[0297]いくつかの実施形態において、オブジェクトネットワークモデラは、メモリ内全体の様々なインデックスを使用して動作するように構成される。動作停止後の迅速なシステム再起動を可能にするために、すべてのインデックスをディスク上のファイルに書き出すことができる。ファイルフォーマットは図３１に示されている。図示されているように、インデックスファイルは、２つの主要部分、すなわち、インデックスヘッダと、１以上のインデックスレコードとを有する。
【０２５９】
[0298]図３１によって示す実施形態において、インデックスヘッダは３つの部分、すなわち、インデックスパラメータと、インデックスキー順列マスク及びシフトと、インデックススロットアレイアロケータ記述子とに分割される。インデックスパラメータは、ラインレールパラメータの多くを反映しているが、ロック、セマフォ及びポインタのような実行時間のみの属性は省かれており、ＡＰＩバージョン（ａｐｉ＿ｖｅｒ）及び動作カウンタ（ｏｐｃｎｔ）のような一貫性マーカが加わっている。インデックスキー順列マスク及びシフト４０４は、ラインレールのｐｅｒｍ属性のものを反映している。アレイアロケータ記述子は、このラインレールのランタイムメモリ要件に関する情報を保持する。このランタイムメモリ要件に関する情報は、オブジェクトネットワークモデラが、起動時に性能を最適化し断片化を最小限に抑えるために必要とされる正確な容量のメモリを予め割り当てることを可能にする。
【０２６０】
[0299]図３１によって示す実施形態において、インデックスレコードは、ラインレールの各インデックスライン内のインデックススロットアレイを直接反映したものである。この実施形態においては、アクティブなオブジェクトのみが記憶され、各々に対するオブジェクトカウンタが、インデックスラインあたりのアクティブなオブジェクトの数を示す。いくつかの実施形態において、オブジェクトは、ｉｄｘｒｅｃｂｕｆ構造内の２つの数、すなわち、オブジェクトが存在するオブジェクトストアのブロック数、及び、オブジェクトを含むブロック内のスロットに対するブロックオフセットによって表される。これらの実施形態において、オブジェクト参照は、インデックスヘッダのｏｐｃｎｔがオブジェクトストアのｏｐｃｎｔに一致する場合にのみ有効である。起動時にこれらのｏｐｃｎｔが一致していない場合、オブジェクトネットワークモデラはインデックスファイルを拒絶し、オブジェクトストアからインデックスファイルを再構築し、その結果として、起動が遅れる。
【０２６１】
オブジェクトストア
[0300]図３２は、図２を参照して上述したオブジェクトストア２１４のようなオブジェクトストア内に含まれるデータ構成要素を示す。いくつかの実施形態において、オブジェクトストアは、下記表１０に記載するオブジェクトブロックの集合ｏｂｊｂｌｏｃｋ＿ｔを参照する、下記表９に記載する基本構造ｏｂｊｅｃｔｓｔｏｒｅ＿ｔとして構成される。これらの実施形態において、オブジェクトストアは、固定最大オブジェクト容量、及び、ディスク上のパーティションファイルとの１対１関係を有する。加えて、これらの実施形態において、オブジェクトストアは、６５，５３６個のオブジェクトブロックを含むことができ、オブジェクトブロックは各々２６２，１４４オブジェクトの固定容量を有し、理論容量は合計で約１７０億オブジェクトになる。しかしながら、他の実施形態は、異なる容量を有してもよく、実施形態は、特定の固定又は可変容量には限定されないことが諒解される。
【表１３】
2019053772.tif 000021
【０２６２】
[0301]いくつかの実施形態において、図２を参照して上述したオブジェクトマネージャ２１０のようなオブジェクトマネージャは、オブジェクトストアを必要に応じて１ｏｂｊｂｌｏｃｋの増分で動的に増大及び縮小するように構成される。これらの実施形態において、ｏｂｊｂｌｏｃｋは、オブジェクトデータがオブジェクトネットワークモデラ２０２に取り込まれるときにアクティブになるオブジェクトスロットの固定の予め割り当てられているセットを有する。書き込まれている現在のブロックが一杯であるとき、次のブロックが書き込みブロックになり得、まだ予め割り当てられていない場合は作成され得る。
【０２６３】
[0302]いくつかの実施形態において、オブジェクトマネージャは、図２を参照して上述したオブジェクトネットワークモデラ２０２のようなオブジェクトネットワークモデラが、セグメント化データセットを維持することを可能にするためのオブジェクト承認システムを実装する。インデックスの節の中で下記に説明するインデックス付け及び検索プロセスが、現在のインデックス付け／検索コレクションの文脈に基づくセグメント属性によってオブジェクトを自動的にフィルタリングする。
【表１４】
2019053772.tif 000022
【０２６４】
[0303]いくつかの実施形態において、ｏｂｊｂｌｏｃｋ内のオブジェクトアレイは、下記表１１に記載する、型ｏｂｊｅｃｔ＿ｔの予め割り当てられているオブジェクトの大きい集合である。これらのオブジェクトは、本開示全体を通じて論じられているシムアレイオブジェクトである。
【表１５】
2019053772.tif 000023
【０２６５】
[0304]いくつかの実施形態において、オブジェクトストアに挿入されるオブジェクトは、メモリベースのｏｂｊｂｌｏｃｋ及びディスク上のブロックデータファイルに書き込まれる。ブロックデータファイルフォーマットを図３３に示す。図示されているように、ブロックデータファイルフォーマットは、ヘッダ、及び、後続する、オブジェクトデータを記憶している１以上のレコードを含む。これらの実施形態において、オブジェクトマネージャは、新たなオブジェクトがメモリ内で作製されるときに、新たなオブジェクトをディスクに書き込む。さらに、これらの実施形態において、オブジェクトマネージャは、修正されたオブジェクトを直接的にディスクに固定するか（デフォルト）、又は、明示的なコミットコマンドの受信に応答して、ディスクに対するバッチ更新のために固定を延期するかのいずれかである。修正されたオブジェクトをディスクに固定するとき、オブジェクトマネージャは、修正されたオブジェクトを連続的に回転する変更ログにストリーミングする。このように、オブジェクトマネージャは、大抵の場合（性能の改善のために）、ディスクに対するオブジェクトブロックデータ部分の不定期のバッチ更新によって連続的なディスク書き込みを保証する。
【０２６６】
[0305]いくつかの実施形態において、オブジェクトは、任意選択的に、任意の「ＢＬＯＢ」メタデータ、すなわち、２ＧＢまでの任意のバイナリデータを含むことができる。これらの実施形態において、メタデータはメモリに記憶されない。そうではなく、これらの実施形態において、メタデータは、オブジェクトブロックファイルと関連付けられるメタデータファイルに記憶される。それゆえ、これらの実施形態において、ブロックデータパーティションはそれゆえ２つのファイル、すなわち、ｏｂｊｂｌｏｃｋデータファイル及びメタデータファイルを有する。
【０２６７】
[0306]いくつかの実施形態において、クエリエンジン（たとえば、図２を参照して上述したクエリエンジン２１８）又はオブジェクトマネージャのような、オブジェクトネットワークモデラの構成要素が、オブジェクトのｍｅｔａｏｆｆｓｅｔ（メタオフセット）属性を使用してオブジェクトに対応するメタデータを記憶し、アクセスする。これらの実施形態において、ｍｅｔａｏｆｆｓｅｔがゼロであるとき、オブジェクトのメタデータは存在しない。また、これらの実施形態において、メタデータがゼロでないとき、オブジェクトネットワークモデラ構成要素によって、オブジェクトのメタデータレコードが位置するメタデータファイルへのオフセットとして解釈されるｍｅｔａｏｆｆｓｅｔ属性。さらに、これらの実施形態によれば、メタデータレコードは、オブジェクトを識別する標準メタ属性の固定セット（回復に必要な場合）、及び、後続する、実際のメタデータを保持する可変バイトアレイを含む。図３４は、一つの実施形態によるメタデータファイルのフォーマットを示す。
【０２６８】
[0307]いくつかの実施形態において、クエリエンジンなどによってメタデータが検索動作によってアクセスされると、最初にメタデータファイルが開かれ（まだ開いていない場合）、ファイルポインタが最初からｍｅｔａｏｆｆｓｅｔバイトに位置付けられる。その後、ファイルからデータが読み出され、返される。メタデータを使用することの性能オーバーヘッドは、ディスクＩ／Ｏサブシステムの速度に依存する。
【０２６９】
アロケータ
[0308]メモリを大量に使用することに起因して、オブジェクトネットワークモデラのいくつかの実施形態は、オブジェクトに使用されるＶｉｎｔベクトルデータ及びラインレール内で使用されるインデックススロットアレイのためにカスタムメモリアロケータを実装する。ベクトルアロケータ（図２９を参照した上述した１以上のベクトルアロケータなど）及びインデックスアロケータ（図２９を参照して上述した１以上のインデックスアロケータなど）の高レベル図を、それぞれ図３５及び図３６に示す。いくつかの実施形態において、アロケータは、ベクトル及びインデックススロットアレイに適したメモリのブロックを予め割り当てるように構成される。これらの実施形態において、選択されたサイズセットのみが各アロケータタイプについてサポートされる。しかしながら、実施形態は、本明細書に明示的に記載されている特定のサイズには限定されない。
【０２７０】
[0309]いくつかの実施形態において、内部ベクトルＶｉｎｔを表現するとき、オブジェクトマネージャは、本明細書におけるベクトル符号化の節に記載したように、最小アロケータＡｋを使用して可能な最小のベクトルアレイ内に適合するようにベクトルサイズを量子化する。これらの実施形態において、以下のサイズ、すなわち、４、８、１２、１６、２０、３２、４８、６４、８０、９６、１２８、１６０、１９２、２２４、２５６、３２０、３８４、４４８、５１２、及び５２０のベクトルをサポートする２０個のベクトルアロケータがある。
【０２７１】
[0310]たとえば、２７個の要素でベクトルを表現するためには、オブジェクトマネージャは、第６のアロケータを使用してＶｉｎｔに容量３２を割り当てることになり、終わりに５個の要素が未使用のままになる。平均的な無駄な空間の量は、関連するメモリ管理オーバーヘッドによって性能を最適化し、断片化を最小限に抑えるための固定サイズのアロケータの小さいセットを有する利点とでバランスが取られている。
【０２７２】
[0311]いくつかの実施形態において、インデックスマネージャは、インデックススロットアロケータのセットからラインレール構造の一部分としてオブジェクトをインデックス付けするために使用されるインデックススロットアレイを割り当てるように構成される。インデックススロットアレイは、オブジェクトネットワークモデラの通常動作によって動的に増大及び縮小する。一般的なアロケータ（たとえば、ｍａｌｌｏｃ／ｆｒｅｅ）がインデックスマネージャによって使用されたとすると、メモリ断片化の効果は、効率的な動作にとって有害なものになる。そうではなく、インデックスマネージャは、カスタムアプリケーション特有アロケータを使用する。このように、インデックスマネージャは、特定の目的のために微調整される大きいメモリブロックを作成及び維持する。
【０２７３】
[0312]これらの実施形態において、以下のサイズ、すなわち、２、１２、４８、１０４、１７１、２４５、３２４、４０８、４９４、５８４、６７６、７７０、８６５、９６３、１０６２、１１６３、１２６５、１３６８、１４７２、１５７７、１６８３、１７９０、１８９８、２００７、２１１７、２２２８、２３３９、２４５１、２５６３、２６７６、２７９０、２９０５、３０２０、３１３５、３２５２、３３６８、３４８５、３６０３、３７２１、３８４０、３９５９、４０７８、４１９８、４３１９、４４４０、４５６１、４６８２、４８０４のサイズのインデックススロットアレイをサポートする４８個の個別のインデックススロットアロケータがある。インデックススロットアレイが空間から外れるとき、インデックスマネージャは、古いアレイを新しいアレイと置き換えるために、次のより高いアロケータを使用する。たとえば、現在のアレイが「１２」のアロケータを使用して割り当てられており、第１３の要素が書き込まれなければならない場合、インデックスマネージャは、「４８」のアロケータを使用して、新たなインデックススロットアレイを提供して、インデックスライン構造から参照される古いアレイに置き換える。インデックスマネージャは、古いアレイのデータを新しいアレイにコピーして、必要に応じてデータをデフラグする。その後、インデックスマネージャは、古いアレイを将来の使用のために「１２」のアロケータにとって利用可能にすることによって、古いアレイの割り当てを解除する。ｍａｌｌｏｃ又はｆｒｅｅはこのプロセスにおいて使用されないことに留意されたい。同様に、インデックスマネージャがインデックスからオブジェクトを削除する場合、古いアレイは、可能であるときはいつでもより小さいアレイと置き換えられる。いくつかの実施形態において、アロケータ自体が、稀な間隔を置いて大きいブロック内で必要に応じて拡大及び縮小する。この拡大及び縮小には、ｍａｌｌｏｃ及びｆｒｅｅに対する、低頻度ではあるが非常に大きい量での呼び出しが必要であり得る。したがって、メモリ断片化が最小限に抑えられる。
【０２７４】
[0313]まだインデックススロットアレイ又はベクトルを提供するために利用されていないアロケータは、簿記に使用される非常に少数のメタ属性を除いて、空間を専有しない。たとえば、いかなるラインレール内のインデックススロットアレイも４８スロットより大きくない場合、４８を上回るすべてのアロケータは空になり、いかなる予め割り当てられている空間も専有しない。
【０２７５】
[0314]インデックススロットアレイは、最も大きいアロケータ（「４０８４）よりも大きく増大し得ることが諒解される。この増大は、入力データのハッシュ値が均等に分散されない状況において発生し得る。いくつかのベクトル次元が他と比較して不均等な頻度で発生する場合に、次元インデックス付けはこの挙動を被る傾向にある。積極的なＩＤＦ正規化を用いる、図２を参照して上述したベクタライザ２０４のようなベクタライザが、そのような事例において望ましい場合がある。しかしながら、オブジェクトネットワークモデラのいくつかの実施形態は、あらゆるサイズのインデックススロットアレイを許容する。これらの実施形態において、インデックスマネージャは、ｍａｌｌｏｃ及びｆｒｅｅを使用して、標準的なインデックスアロケータには大きすぎるインデックススロットアレイにメモリを割り当てる。しかしながら、大きすぎるアレイが使用されると検索性能が影響を受け得ることも諒解される。したがって、いくつかの実施形態において、インデックスマネージャは、これらのアレイが大きすぎる状況において最適化を誘導するために、インデックススロットアロケータプロファイル統計を記録及び提供する。
【０２７６】
マルチベクトル表現
[0315]いくつかの実施形態において、オブジェクトネットワークモデラは、特徴の集合が次元性低減を通じて情報を正規化するのに効率的な方法であるとき、大きい外部オブジェクト（たとえば、文書）を表現するように構成される。しかしながら、これらの実施形態において、元のオブジェクトを適切に記述するために単一の特徴集合を作成することが可能でない場合がある。
【０２７７】
[0316]たとえば、一実施例において、オブジェクトネットワークモデラは、テキスト文書をオブジェクトとしてモデル化するために使用されてもよい。この実施例において、本全体を特徴ベクトルとして表現することは、ベクタライザにとって困難である場合がある。この問題に対処するために、オブジェクトネットワークモデラは、複数のベクトルを使用して様々な「視点」からオブジェクトを表現することができる。このように、オブジェクトネットワークモデラは、オブジェクトの選択された態様の間での部分的照合に基づいてオブジェクトを関連付けることが可能である。
【０２７８】
[0317]図３７は、一つの文書を表す４つのベクトルを示す。ベクトルは、他のオブジェクトを照合するための重心に結合することができるか、又は、個々に使用することができる。オブジェクトネットワークモデラは、アプリケーションが、ネットワークを形成するためにベクトル照合基準の任意の組み合わせを使用することを可能にする。オブジェクトは複数のベクトルとして表すことができ、各ベクトルは、異なるタイプの情報に基づく。いくつかの他の例は、以下を含む。
１）線形セグメント化。入力データの異なる部分に対して別個のベクトルを作成することができる。粒度のレベルは任意である。粒度のレベルは、本の章ごとに一つのベクトル、段落ごとに一つのベクトル又は何らかの他のレベルであり得る。入力データは、適切なメディアベクタライザによって表される音声、発話又はビデオのセグメントでもあり得る。ベクトルごとの情報の領域が重なり合うことを許容する窓関数が入力に適用され得る。
２）エンティティタイプ。異なるカテゴリの情報について別個のベクトルが作成され得る。たとえば、別個のベクトルは、人、場所、製品、会社、薬、食品などを表すために使用され得る。特定のタイプのエンティティを認識する専用のベクタライザが、このシナリオにおいて有用であり得る。
３）単語クラス。入力文書内の名詞、動詞及び形容詞を表すために別個のベクトルが使用され得る。さらに、ベクトルは、動詞の時制（過去、現在、未来）に基づくテキストセグメント、又は、感情ベースのベクトルの形容詞の周囲に作成され得る。
４）単語バケット。偽陰性に対するロバスト性を改善するために、複数のベクトルを使用することができ、各ベクトルは、たとえば、Ａ〜Ｆ、Ｇ〜Ｌ、Ｍ〜Ｒ、Ｓ〜Ｚのような第１の文字バケットに基づく単語の部分集合のみを考慮する。これは、フィンガープリント脆弱性が問題であり得る、（性能のために）順列インデックスのみに基づく高再現率重複検出アプリケーションにとって有用である。
【０２７９】
グラフィックス処理ユニット（ＧＰＵ）実施態様
[0318]ＧＰＵは、多くのデータ片に対する操作を同時に実施するのによく適している。この操作は、多くの「規模を小さくした」コアをＧＰＵ内にまとめることによって達成され、それらのコアの各々が、独立した操作を同時に実施することができる。さらに、これらのコアの各々は、コアが単一のクロックサイクル内で複数のデータ片に操作を適用することを可能にする、複数のＡＬＵ（算術論理演算ユニット）を含む。この機能は、ＳＩＭＤ（単一命令複数データ）処理と呼ばれる。
【０２８０】
[0319]図３８に示すサンプルアーキテクチャを参照すると、フェッチ／複合ブロックが、すべてのＡＬＵに対する同一の操作の分散を処理する。各ＡＬＵは、そのローカルコンテキストブロックを参照して、操作が実施されるべきデータを得る。その後、結果が出力バッファに書き込まれる。出力バッファは、必ずしも、ローカルコンテキストブロックに位置していなくてもよい（出力バッファは、共有コンテキストデータブロックに位置してもよい）。
【０２８１】
[0320]ＧＰＵは複数のコアを含み、上述したプロセスは、これらのコアの各々において実施されてもよい。したがって、ＧＰＵが実施することができる同時操作の数は、一般的に、コア数と、コア数あたりのＡＬＵとを乗算することによって定義される。
【０２８２】
[0321]いくつかの実施形態において、オブジェクトネットワークモデラは、１以上の汎用ＣＰＵを使用して実装されてもよい。特に、以下の操作、すなわち、ベクトル符号化、フィンガープリント生成、フィンガープリント比較、及び、コサイン類似度計算を増強することができる。加えて、ＧＰＵ上で実行する実施形態は、より広いフィンガープリントを実装することができ、次元あたりの分解能をより高くすることが可能である。
【０２８３】
[0322]ベクトル符号化に関して、特徴ハッシング及び重み正規化操作は、各ハッシュが独立した操作であるということを利用して、数回に分けてＧＰＵにオフロードすることができる。したがって、ＧＰＵを使用して数千のハッシュを同時に計算することができ、この結果として、大きいデータセットをインデックス付けするときに相当の速度改善がもたらされるはずである。フィンガープリント生成に関して、数千のフィンガープリント断片生成操作を、ＧＰＵを使用して同時に実施することができる。ＧＰＵベースのベクトル符号化と組み合わせて、データインデックス付けスループットが相当に改善するはずである。フィンガープリント比較に関して、線形テーブル走査を実施する代わりに、ハミング距離計算をＧＰＵ上で数回に分けて実施することができる。コサイン類似度計算に関して、ドット積をＧＰＵ上で数回に分けて計算することができる。
【０２８４】
[0323]広いフィンガープリントに関して、いくつかの実施形態において、フィンガープリントは６４ビット幅であり、そのため、フィンガープリントはｘ８６−６４  ＣＰＵによって効率的に処理することができる。フィンガープリント生成及び比較をＧＰＵにオフロードすることによって、システムは、より広いフィンガープリントを処理することが可能であり得る。ＧＰＵは並列データ処理に非常に良好であるため、より広いフィンガープリント（たとえば、１２８ビット）を、バッチジョブの一部分として処理することができるより小さい断片（３２／６４ビット、ＧＰＵアーキテクチャに依存する）に分解することができる。このように６４ビットフィンガープリントを処理するのにかかるのと同じ時間でより広いフィンガープリントを処理することができる。フィンガープリントがより広くなることでより多くの断片が許容され、これによって、入力ベクトルＶの変化に対するロバスト性が増大することになる。
【０２８５】
[0324]このように、少なくとも一つの実施例のいくつかの態様を説明したが、様々な変更、修正、及び改善が当業者には容易に想起されることが諒解されるべきである。たとえば、本明細書に開示されている実施例は、他の文脈において使用されてもよい。そのような変更、修正、及び改善は本開示の一部であるように意図されており、本明細書に論じられている実施例の範囲内にあることが意図されている。したがって、上記の説明及び図面は例示のみを目的としたものである。
【図１】
2019053772.tif 000024
【図２】
2019053772.tif 000025
【図３】
2019053772.tif 000026
【図４】
2019053772.tif 000027
【図５】
2019053772.tif 000028
【図６】
2019053772.tif 000029
【図７】
2019053772.tif 000030
【図８】
2019053772.tif 000031
【図９】
2019053772.tif 000032
【図１０】
2019053772.tif 000033
【図１１】
2019053772.tif 000034
【図１２】
2019053772.tif 000035
【図１３】
2019053772.tif 000036
【図１４】
2019053772.tif 000037
【図１５】
2019053772.tif 000038
【図１６】
2019053772.tif 000039
【図１７】
2019053772.tif 000040
【図１８】
2019053772.tif 000041
【図１９】
2019053772.tif 000042
【図２０】
2019053772.tif 000043
【図２１】
2019053772.tif 000044
【図２２】
2019053772.tif 000045
【図２３】
2019053772.tif 000046
【図２４】
2019053772.tif 000047
【図２５】
2019053772.tif 000048
【図２６】
2019053772.tif 000049
【図２７】
2019053772.tif 000050
【図２８】
2019053772.tif 000051
【図２９】
2019053772.tif 000052
【図３０−１】
2019053772.tif 000053
【図３０−２】
2019053772.tif 000054
【図３１−１】
2019053772.tif 000055
【図３１−２】
2019053772.tif 000056
【図３２−１】
2019053772.tif 000057
【図３２−２】
2019053772.tif 000058
【図３３−１】
2019053772.tif 000059
【図３３−２】
2019053772.tif 000060
【図３４】
2019053772.tif 000061
【図３５】
2019053772.tif 000062
【図３６】
2019053772.tif 000063
【図３７】
2019053772.tif 000064
【図３８】
2019053772.tif 000065
【図３９】
2019053772.tif 000066
【図４０】
2019053772.tif 000067
【図４１】
2019053772.tif 000068
【図４２】
2019053772.tif 000069
【手続補正書】
【提出日】平成30年12月28日(2018.12.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プロセッサが、第１の外部オブジェクトを得るステップと、
前記プロセッサが、前記第１の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記プロセッサが、前記第１の外部オブジェクトを表す１以上の内部ベクトルを、前記第１の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
前記プロセッサが、第２の外部オブジェクトを得るステップと、
前記プロセッサが、前記第２の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記プロセッサが、前記第２の外部オブジェクトを表す１以上の内部ベクトルを、前記第２の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
前記プロセッサが、前記第１の外部オブジェクトと前記第２の外部オブジェクトの両方を表す第１の重心オブジェクトを生成するステップであって、前記第１の重心オブジェクトのベクトルが、前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと前記第２の外部オブジェクトを表す前記１以上の内部ベクトルとの平均を含む、該ステップと
を含む、コンピュータによって実施される方法。
【請求項２】
前記プロセッサが、前記重心オブジェクトの前記ベクトルと、前記重心オブジェクトに対する内部参照である濃度カウントとを自動的に維持するステップをさらに含む請求項１に記載のコンピュータによって実施される方法。
【請求項３】
前記プロセッサが、第３の外部オブジェクトを得るステップと、
前記プロセッサが、前記第３の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記プロセッサが、前記第３の外部オブジェクトを表す１以上の内部ベクトルを、前記第３の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
前記プロセッサが、前記第１の重心オブジェクトが前記第１の外部オブジェクトと、前記第２の外部オブジェクトと、前記第３の外部オブジェクトとを表すように前記第１の重心オブジェクトを調整するステップであって、前記調整された第１の重心オブジェクトのベクトルが、前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第２の外部オブジェクトを表す前記１以上の内部ベクトルと、前記第３の外部オブジェクトを表す前記１以上の内部ベクトルとの平均を含む、該ステップと
をさらに含む請求項１または２に記載のコンピュータによって実施される方法。
【請求項４】
前記プロセッサが、前記第３の外部オブジェクトに最も類似する外部オブジェクトを前記第１の外部オブジェクトまたは前記第２の外部オブジェクトとして識別することで前記第１の重心オブジェクトを識別するステップをさらに含む請求項３に記載のコンピュータによって実施される方法。
【請求項５】
少なくとも一つのプロセッサを備え、
前記少なくとも一つのプロセッサが、
第１の外部オブジェクトを得るステップと、
前記第１の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記第１の外部オブジェクトを表す１以上の内部ベクトルを、前記第１の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
第２の外部オブジェクトを得るステップと、
前記第２の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記第２の外部オブジェクトを表す１以上の内部ベクトルを、前記第２の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
前記第１の外部オブジェクトと前記第２の外部オブジェクトの両方を表す第１の重心オブジェクトを生成するステップであって、前記第１の重心オブジェクトのベクトルが、前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと前記第２の外部オブジェクトを表す前記１以上の内部ベクトルとの平均を含む、該ステップと
を実行する、
コンピュータシステム。
【請求項６】
第１の外部オブジェクトを得るステップと、
前記第１の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記第１の外部オブジェクトを表す１以上の内部ベクトルを、前記第１の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
第２の外部オブジェクトを得るステップと、
前記第２の外部オブジェクトを表す１以上の外部ベクトルを生成するステップと、
前記第２の外部オブジェクトを表す１以上の内部ベクトルを、前記第２の外部オブジェクトを表す前記１以上の外部ベクトルに基づいて生成するステップと、
前記第１の外部オブジェクトと前記第２の外部オブジェクトの両方を表す第１の重心オブジェクトを生成するステップであって、前記第１の重心オブジェクトのベクトルが、前記第１の外部オブジェクトを表す前記１以上の内部ベクトルと前記第２の外部オブジェクトを表す前記１以上の内部ベクトルとの平均を含む、該ステップと
をコンピュータに実行させるプログラム。
【外国語明細書】
2019053772000001.pdf