(57)【要約】【課題】高速かつ高精度な検索を可能にする有向グラフを生成することができる検索データ管理装置、検索データ管理方法、および検索データ管理プログラムを提供すること。【解決手段】データ検索の対象となる複数のノードを記憶する記憶部と、前記記憶部に記憶された各ノードから近傍ノードに対して有向エッジが設定されたグラフ構造のデータである一次グラフを生成する一次グラフ生成部と、前記記憶部に記憶された一次グラフにおける前記有向エッジの向きを逆にしたグラフ構造のデータである転置グラフを、データ検索のためのデータとして生成する転置グラフ生成部と、を備える検索データ管理装置。【選択図】図１
2018032374.tif 000002
【特許請求の範囲】
【請求項１】
データ検索の対象となる複数のノードを記憶する記憶部と、
前記記憶部に記憶された各ノードから近傍ノードに対して有向エッジが設定されたグラフ構造のデータである一次グラフを生成する一次グラフ生成部と、
前記記憶部に記憶された一次グラフにおける前記有向エッジの向きを逆にしたグラフ構造のデータである転置グラフを、データ検索のためのデータとして生成する転置グラフ生成部と、
を備える検索データ管理装置。
【請求項２】
前記一次グラフ生成部は、着目ノードから距離が短い順に所定数のノードが選択され、前記着目ノードから前記選択された所定数のノードに対して有向エッジが設定されたグラフ構造のデータを、前記一次グラフとして生成する、
請求項１記載の検索データ管理装置。
【請求項３】
前記一次グラフ生成部は、複数のノードに対して無向エッジが設定されたグラフ構造のデータに対し、無向エッジを二本の有向エッジとみなし、各ノードから他のノードに向かうエッジにそれぞれ上限を設け、上限を超える分を距離の長いエッジから順に削減することで、前記一次グラフを生成する、
請求項１記載の検索データ管理装置。
【請求項４】
前記転置グラフ生成部は、更に、前記転置グラフに対して、各ノードに付与されたエッジに対して、逆向きのエッジを所定数または所定割合加えたグラフを、データ検索のためのデータとして生成する、
請求項１から３のうちいずれか１項記載の検索データ管理装置。
【請求項５】
前記転置グラフ生成部は、更に、前記転置グラフに対して、各ノードに付与されたエッジのうち、短い順に所定数または所定割合のエッジを残して長いエッジを削除したグラフを、データ検索のためのデータとして生成する、
請求項１から４のうちいずれか１項記載の検索データ管理装置。
【請求項６】
クエリデータから得られるクエリオブジェクトと前記転置グラフに含まれるノードに対応するオブジェクトとの距離を計算することによって、前記クエリデータに類似するデータを検索する検索部であって、
前記クエリオブジェクトを基準とした検索範囲または探索範囲の仮想半径と、前記転置グラフに含まれる第１のノードに対応する第１のオブジェクトと前記クエリオブジェクトとの間の第１の距離と、前記第１のオブジェクトと前記転置グラフに含まれる第２のノードに対応する第２のオブジェクトとの間の第２の距離との関係に基づいて、前記第２のノードと前記クエリデータとの類似を判定するか否かを決定する検索部を更に備える、
請求項１から５のうちいずれか１項記載の検索データ管理装置。
【請求項７】
前記検索部は、前記第１のオブジェクトが前記クエリオブジェクトに類似しない場合において、前記第１の距離から前記仮想半径を差し引いた距離が、前記第２の距離よりも大きい場合に、前記第２のノードと前記クエリデータとの類似を判定しないと決定する、
請求項６記載の検索データ管理装置。
【請求項８】
前記検索部は、前記第１のオブジェクトが前記クエリオブジェクトに類似しない場合において、前記第１の距離に前記仮想半径を加算した距離が、前記第２の距離よりも小さい場合に、前記第２のノードと前記クエリデータとの類似を判定しないと決定する、
請求項６または７記載の検索データ管理装置。
【請求項９】
コンピュータが、
データ検索の対象となる複数のノードに含まれる各ノードから近傍ノードに対して有向エッジが設定されたグラフ構造のデータである一次グラフを生成し、
前記生成した一次グラフにおける前記有向エッジの向きを逆にしたグラフ構造のデータである転置グラフを、データ検索のためのデータとして生成する、
検索データ管理方法。
【請求項１０】
コンピュータに、
データ検索の対象となる複数のノードに含まれる各ノードから近傍ノードに対して有向エッジが設定されたグラフ構造のデータである一次グラフを生成させ、
前記生成させた一次グラフにおける前記有向エッジの向きを逆にしたグラフ構造のデータである転置グラフを、データ検索のためのデータとして生成させる、
検索データ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索データ管理装置、検索データ管理方法、および検索データ管理プログラムに関する。
【背景技術】
【０００２】
画像検索などのデータ検索の分野において、検索対象のデータ同士を仮想的に接続要素によって接続したグラフ構造のデータを構築しておき、接続要素を辿ることで、データ検索が行われている。接続要素とは、二つのデータが接続されていることを示す情報であり、エッジ、リンクなどと称される（以下ではエッジと称する）。エッジの設定は、まず検索対象のデータのオブジェクトを求め、オブジェクトが近いデータ同士を接続するといった規則に従って行われる。オブジェクトとは、距離が定義可能なデータである。オブジェクトは、典型的には多次元ベクトルデータで表され、オブジェクトが近いとは、例えば、多次元ベクトルデータ間の距離が短いことと定義される。多次元ベクトルデータ同士の距離としては、例えば、ベクトル要素間の差分についてＬｐノルムを求めたものが使用される（ｐ＝１、２、…）。
【０００３】
また、エッジには、有向エッジと無向エッジが存在する。有向エッジとは、一方向にしかデータを辿れないエッジであり、無向エッジとは、双方向にデータを辿ることができるエッジである。無向エッジによって表現されたグラフ構造のデータ（無向グラフ）を用いて検索を行う技術が開示されている（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第５２０８００１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
無向グラフを使用する場合、検索経路のパターンが多くなるため、より網羅的な検索を行うことができる。反面、無駄な経路で検索を行ってしまう機会も多くなるため、時間辺りの検索精度が、有向グラフを用いた場合よりも高くなるとは限らない。
【０００６】
一方で、有向グラフを使用する場合、そのグラフの作り方によっては、他のデータから参照されないデータが出現する可能性がある。この場合、検索処理において、そのデータに辿り着かない可能性が高くなり、網羅的な検索を行うことができなくなる場合がある。
【０００７】
本発明は、このような事情を考慮してなされたものであり、高速かつ高精度な検索を可能にする有向グラフを生成することができる検索データ管理装置、検索データ管理方法、および検索データ管理プログラムを提供することを目的の一つとする。
【課題を解決するための手段】
【０００８】
本発明の一態様は、データ検索の対象となる複数のノードを記憶する記憶部と、前記記憶部に記憶された各ノードから近傍ノードに対して有向エッジが設定されたグラフ構造のデータである一次グラフを生成する一次グラフ生成部と、前記記憶部に記憶された一次グラフにおける前記有向エッジの向きを逆にしたグラフ構造のデータである転置グラフを、データ検索のためのデータとして生成する転置グラフ生成部と、を備える検索データ管理装置である。
【発明の効果】
【０００９】
本発明の一態様によれば、高速かつ高精度な検索を可能にする有向グラフを生成することができる検索データ管理装置、検索データ管理方法、および検索データ管理プログラムを提供することができる。
【図面の簡単な説明】
【００１０】
【図１】実施形態の検索データ管理装置１を中心とした構成図である。
【図２】制御部２０のハードウェア構成の一例を示す図である。
【図３】既存データオブジェクト４２の内容の一例を示す図である。
【図４】グラフインデックス４４の内容の一例を示す図である。
【図５】一次グラフ生成部２６Ａによる処理の流れの一例を示すフローチャートである。
【図６】近傍オブジェクトが更新される様子を示す図である。
【図７】一次グラフＧに基づいて転置グラフＧｒが生成される様子を示す図である。
【図８】転置グラフＧｒに基づいて転置グラフＧｒ＋が生成される様子を示す図である。
【図９】転置グラフＧｒ＋に基づいて転置グラフＧｒ＋＋が生成される様子を示す図である。
【図１０】転置グラフ生成部２６Ｂにより実行される処理の流れの一例を示すフローチャートである。
【図１１】各グラフを用いて検索を行うシミュレーションの結果を示す図である。
【図１２】無向グラフＧａを生成する処理の一例を示すフローチャートである。
【図１３】無向グラフＧａを生成する処理の一例を示すフローチャートである。
【図１４】第２実施形態に係るインデックス検索部２４の処理の内容を説明するための図である。
【発明を実施するための形態】
【００１１】
以下、図面を参照し、本発明の検索データ管理装置、検索データ管理方法、および検索データ管理プログラムの実施形態について説明する。
【００１２】
＜第１実施形態＞
以下、第１実施形態について説明する。
［全体構成］
図１は、実施形態の検索データ管理装置１を中心とした構成図である。検索データ管理装置１は、一以上のクライアント端末ＣＬとネットワークＮＷを介して接続される。クライアント端末は、パーソナルコンピュータ、スマートフォンなどの携帯電話、タブレット端末、その他の端末装置である。ネットワークＮＷは、無線基地局、公衆回線、専用回線、プロバイダ端末、インターネットなどを含む。検索データ管理装置１は、クライアント端末ＣＬからクエリデータを受信すると、クエリデータに類似するデータを検索し、検索結果をクライアント端末ＣＬに返信する。検索データ管理装置１が返信するデータは、データそのもの（例えばｊｐｇなどで生成された画像データ）であってもよいし、データを参照するための識別子（ＵＲＬなど）であってもよい。また、クエリデータや検索対象のデータは、画像、音声、テキストデータなど、如何なる種類のデータであってもよい。以下の説明では、検索データ管理装置１が画像を検索するものとして説明する。
【００１３】
検索データ管理装置１は、例えば、ネットワークインターフェース１０と、制御部２０と、入出力装置３０と、データサーバ４０とを備える。ネットワークインターフェース１０は、例えば、ＮＩＣ（Network Interface Card）である。
【００１４】
制御部２０は、例えば、データオブジェクト生成部２２と、インデックス検索部２４と、グラフインデックス編集部２６とを備える。グラフインデックス編集部２６は、一次グラフ生成部２６Ａと、転置グラフ生成部２６Ｂとを備える。これらの制御部２０の構成要素は、例えば、ＣＰＵ（Central Processing Unit）などのプロセッサがプログラムを実行することにより実現される。また、これらの機能部のうち一部または全部は、ＬＳＩ（Large Scale Integration）やＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field-Programmable Gate Array）などのハードウェアによって実現されてもよいし、ソフトウェアとハードウェアが協働して実現されてもよい。これらの機能部による処理の内容については後述する。
【００１５】
図２は、制御部２０のハードウェア構成の一例を示す図である。制御部２０は、例えば、ＣＰＵ２０Ａと、ＲＡＭ（Random Access Memory）２０Ｂと、プログラムメモリ２０Ｃとが内部バスによって接続された構成を有する。内部バスには、ネットワークインターフェース１０、入出力インターフェース、メモリインターフェースなどの各種インターフェースが接続される。ＲＡＭ２０Ｂには、ＣＰＵ２０Ａによる処理対象のデータ、或いは処理結果のデータなどが格納される。プログラムメモリ２０Ｃは、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリなどの記憶装置のうち一部または全部を含む。プログラムメモリ２０Ｃには、データオブジェクト生成プログラム２０Ｃａ、インデックス検索プログラム２０Ｃｂ、グラフインデックス編集プログラム２０Ｃｃなどのプログラムが格納される。これらのプログラムは明確に分離されている必要はなく、一部または全部が共通化されてもよい。
【００１６】
図１に戻り、入出力装置３０は、検索データ管理装置１の管理者による入力操作を受け付けるマウスやキーボード、タッチパネルなどの入力装置と、ＬＣＤ（Liquid Crystal Display）や有機ＥＬ（Electroluminescence）表示装置、スピーカなどの出力装置とを含む。
【００１７】
データサーバ４０は、ＨＤＤやフラッシュメモリなどの記憶装置により実現される。データサーバ４０は、制御部２０のプログラムメモリ２０Ｃと共通化されてもよいし、プログラムメモリ２０Ｃとは別体の記憶装置により実現されてもよい。また、データサーバ４０は、検索データ管理装置１から各種ネットワークを介してアクセス可能なＮＡＳ（Network Attached Storage）装置などの外部記憶装置により実現されてもよい。この場合、特許請求の範囲における「記憶部」は、データサーバ４０から取得したデータが一時的に格納されるＲＡＭ２０Ｂを指すものと解釈してもよい。
【００１８】
［制御部］
以下、制御部２０の各機能部による処理の内容について説明する。なお、制御部２０は、一つのプロセッサにより実現される必要はなく、機能ごとに分散処理を行ってもよい。例えば、データオブジェクト生成部２２およびインデックス検索部２４と、グラフインデックス編集部２６とは、それぞれ別体のプロセッサにより実現されてもよい。
【００１９】
データオブジェクト生成部２２は、クライアント端末ＣＬなどから受信した入力データに基づいて、入力データのオブジェクトを生成する。入力データが画像である場合、オブジェクトは、例えば、局所特徴量やＢｏＦ（Bag of Features）、色のヒストグラムなど、或いはこれらの組み合わせである。また、入力データがテキストデータである場合、オブジェクトは、例えば、単語の出現頻度のベクトルデータ、ニューラルネットワークを用いて抽出した意味ベクトル、或いは、他の単語と共に出現する頻度その他の相対関係に基づくベクトルなどである。オブジェクトは、データ検索の対象となる「ノード」の一例である。
【００２０】
インデックス検索部２４は、データオブジェクト生成部２２により生成されたオブジェクト（以下、新規オブジェクトと称する）をクエリデータとしてデータサーバ４０を検索し、新規オブジェクトに類似するオブジェクトを、既存データオブジェクト４２から抽出する。データサーバ４０には、例えば、既存データオブジェクト４２と、グラフインデックス４４とが格納される。
【００２１】
既存データオブジェクト４２は、検索対象となるデータから予め生成されたオブジェクトのデータである。既存データオブジェクト４２には、その既存データオブジェクト４２を生成する元となったデータ、或いはデータを参照する識別子が対応付けられている。検索データ管理装置１は、新規オブジェクトをクエリとして得られた既存オブジェクト、すなわち新規オブジェクトに類似するオブジェクトに対応付けられたデータ、或いはそのデータを参照する識別子をクライアント端末ＣＬに送信する。図３は、既存データオブジェクト４２の内容の一例を示す図である。図示するように、既存データオブジェクト４２は、オブジェクトの識別情報（図中、オブジェクトＩＤ）に対して、オブジェクト（図ではベクトルデータ）、およびそのオブジェクトを生成する元となったデータ、或いはデータを参照する識別子が対応付けられたデータである。
【００２２】
グラフインデックス４４は、複数のオブジェクトを接続するエッジに関する情報であり、参照元のオブジェクトと参照先のオブジェクトとを接続する有向エッジの集合により形成されるグラフ構造のデータである。図４は、グラフインデックス４４の内容の一例を示す図である。
【００２３】
グラフインデックス４４は、例えば、参照元のオブジェクトの識別情報である参照元オブジェクトＩＤに対し、参照先のオブジェクトの識別情報である参照先オブジェクトＩＤ、それらを接続する有向エッジの識別情報であるエッジＩＤ、および参照元のオブジェクトと参照先のオブジェクトとの距離などの情報が対応付けられたものである。オブジェクトがベクトルである場合、それらの距離は、例えば、ベクトル要素間の差分についてＬｐノルムを求めたものと定義される（ｐ＝１、２、…）。なお、図３および図４に示すデータ構造は、あくまで一例であり、他のデータ構造が採用されてもよい。例えば、グラフインデックス４４は、エッジＩＤに対してその他の情報が対応付けられたものであってもよい。すなわち、本実施形態においてデータ構造の形式は本質的な問題ではなく、距離が定義されている限り、如何なるデータ構造のデータがデータサーバ４０に格納されてもよい。なお、本来距離とは距離の公理を満たすことを意味するが、距離の公理を満たさない擬似的な距離であっても構わない。擬似的な距離の場合には検索性能が低下するが、処理上扱いやすいなどのメリットがあれば疑似的な距離を使用してもよい。
【００２４】
インデックス検索部２４は、グラフインデックス４４により規定されたエッジによって、参照元のオブジェクトから参照先のオブジェクトへの向きに従って辿ることのできるオブジェクトのうち、新規オブジェクトに対して既定の距離以内にあるオブジェクトを、新規オブジェクトに類似するオブジェクトとして抽出する。また、インデックス検索部２４は、グラフインデックス４４により規定されたエッジによって、参照元のオブジェクトから参照先のオブジェクトへの向きに従って辿ることのできるオブジェクトのうち、新規オブジェクトに対する距離が短いものから順に所定数のオブジェクトを、新規オブジェクトに類似するオブジェクトとして抽出してもよい。そして、インデックス検索部２４は、既存データオブジェクト４２において、抽出したオブジェクトに対応付けられているデータまたはその識別子を、ネットワークインターフェース１０およびネットワークＮＷを介してクライアント端末ＣＬに送信する。
【００２５】
なお、インデックス検索部２４による検索処理は、例えば、後述する図１３のフローチャートの処理を用いて実現される。図１３のフローチャートにおいて、新規オブジェクトをオブジェクトｙとして得られるオブジェクト集合Ｒが、インデックス検索部２４による検索結果の一例である。この場合、所定数ｋｓを所望の値に調整することで、検索結果に含まれるオブジェクトの数を調整することができる。
【００２６】
データオブジェクト生成部２２およびインデックス検索部２４の機能によって、クライアント端末ＣＬは、送信したデータに類似するデータを検索データ管理装置１から取得することができる。なお、検索データ管理装置１の役割は、新規オブジェクトに類似するオブジェクトを抽出するところまでであってもよく、その場合、抽出したオブジェクトに対応したデータ、或いはデータを参照する識別子をクライアント端末ＣＬに送信する機能は、検索データ管理装置１とは異なる装置が有してもよい。
【００２７】
グラフインデックス編集部２６の一次グラフ生成部２６Ａは、グラフインデックス４４の元となる有向グラフ（一次グラフ）Ｇを生成する。一次グラフ生成部２６Ａは、一次グラフをＲＡＭ２０Ｂまたはデータサーバ４０などの記憶部に記憶させる。なお、以下の説明において「オブジェクト間の距離が短い」と「オブジェクト同士が近い」、および「オブジェクト間の距離が長い」と「オブジェクトが遠い」は同じ意味である。
【００２８】
図５は、一次グラフ生成部２６Ａによる処理の流れの一例を示すフローチャートである。本フローチャートの処理の前提として、既存データオブジェクト４２に含まれるオブジェクトには、１からｎまでのオブジェクトＩＤが付与されているものとする。フローチャートの中で使用する引数ｉおよびｊは、１からｎまで順に選択されて処理が実行される。すなわち、一次グラフ生成部２６Ａは、まず、引数ｉを１に設定すると共に、引数ｊを１から一つずつインクリメントしながら引数ｊがｎに至るまで繰り返しＳ１００〜Ｓ１０６の処理を行う。次に、一次グラフ生成部２６Ａは、引数ｉを２に設定すると共に、引数ｊを１から一つずつインクリメントしながら引数ｊがｎに至るまで繰り返しＳ１００〜Ｓ１０６の処理を行う。これを、引数ｉがｎに至るまで繰り返し実行する。
【００２９】
まず、一次グラフ生成部２６Ａは、オブジェクトｉ（オブジェクトＩＤがｉであるオブジェクト；以下同様）が、オブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）の要素である、またはｉ＝ｊであるか否かを判定する（Ｓ１００）。オブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）とは、オブジェクトｊ（着目ノードの一例）から見て距離が短い方から順に所定数ｋｐだけ選択されるオブジェクトの集合であり、オブジェクトｊを参照元とする参照先のオブジェクトの集合である。以下、オブジェクトｊを参照元とし、近傍オブジェクト集合Ｎ（Ｇ，ｊ）に含まれるオブジェクトを参照先とするエッジを、「オブジェクトｊに付与されたエッジ」と称することがある。「Ｇ」は、グラフ構造のデータを示す符号である。オブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）の要素であるオブジェクトのそれぞれと、オブジェクトｊとの間は、有向エッジによって接続される。従って、少なくともオブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）の要素であるオブジェクトは、オブジェクトｊから一つのエッジを介して辿ることのできるオブジェクトである。なお、オブジェクトｊが、オブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）の要素でない他のオブジェクト（例えばｕ）の近傍オブジェクト集合Ｎ（Ｇ，ｕ）の要素である場合もある。以下、このことを前提として説明する。オブジェクトｉがオブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）の要素である場合、またはｉ＝ｊである場合、Ｓ１０２〜Ｓ１０６の処理がスキップされる。
【００３０】
オブジェクトｉがオブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）の要素でなく、且つｉ＝ｊでない場合、一次グラフ生成部２６Ａは、オブジェクトｉをオブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）の要素に追加する（Ｓ１０２）。次に、一次グラフ生成部２６Ａは、オブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）の要素であるオブジェクトの数が所定数ｋｐを超えるか否かを判定する（Ｓ１０４）。所定数ｋｐは、任意に定められる自然数である。例えば、ｋｐ＝４０である。オブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）の要素であるオブジェクトの数が所定数ｋｐを超える場合、一次グラフ生成部２６Ａは、オブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）から、オブジェクトｊとの距離が最も長い（オブジェクトｊから最も遠い）オブジェクトを除外する（Ｓ１０６）。
【００３１】
図６は、近傍オブジェクト集合が更新される様子を示す図である。図示の例では、元々、オブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）にオブジェクト（１）〜（３）が設定されていたところ、オブジェクトｉが追加されると共にオブジェクト（３）が除外された。この結果、オブジェクトｊの近傍オブジェクト集合Ｎ（Ｇ，ｊ）がＮ（Ｇ，ｊ）＊に更新された。このような処理を繰り返すことで、オブジェクトｘ＝１〜ｎの全てについて、近傍オブジェクト集合Ｎ（Ｇ，ｘ）が設定される。これによって、グラフインデックス４４の元となる有向グラフ（一次グラフ）Ｇが生成される。
【００３２】
転置グラフ生成部２６Ｂは、一次グラフ生成部２６Ａにより生成された一次グラフＧに対して、エッジの向きを逆にした（すなわち参照元のデータと参照先のデータを入れ替えた）転置グラフＧｒを生成する。図７は、一次グラフＧに基づいて転置グラフＧｒが生成される様子を示す図である。
【００３３】
ここで、一次グラフＧにおいては、「他のデータから参照されない、或いは参照元のデータが極めて少ないデータ」が存在する可能性がある。これに対し、転置グラフＧｒにおいては、各データは、所定数ｋｐのデータから参照されることが保証されている。この結果、検索漏れを無くすことができる。
【００３４】
また、転置グラフ生成部２６Ｂは、転置グラフに対し、各オブジェクトに付与されたエッジに対して、逆向きのエッジを所定数ｋｒ（または所定割合）加えてもよい。所定数ｋｒは、所定数ｋｐよりも小さい数であり、一例として、ｋｒ＝２０である。以下、逆向きのエッジを所定数ｋｒ加えたものを転置グラフＧｒ＋と称する。図８は、転置グラフＧｒに基づいて転置グラフＧｒ＋が生成される様子を示す図である。図中、ＡＥは転置グラフＧｒに対して追加されたエッジである。
【００３５】
更に、転置グラフ生成部２６Ｂは、逆向きのエッジを所定数ｋｒ加えた転置グラフＧｒ＋に対し、各オブジェクトに付与されたエッジを長さ順にソートし、短い順に所定数ｋｍ（または所定割合）のエッジを残して長いエッジを削除してもよい。一例として、ｋｍ＝６０である。以下、短い順に所定数ｋｍのエッジを残して長いエッジを削除したものを転置グラフＧｒ＋＋と称する。図９は、転置グラフＧｒ＋に基づいて転置グラフＧｒ＋＋が生成される様子を示す図である。図中、破線で示す矢印は、転置グラフＧｒ＋から削除されたエッジである。なお、転置グラフ生成部２６Ｂは、転置グラフＧｒ＋を生成せず、転置グラフＧｒにおいて、各オブジェクトに付与されたエッジを長さ順にソートし、短い順に所定数ｋｍのエッジを残して長いエッジを削除して転置グラフＧｒ＋＋を生成してもよい。
【００３６】
図１に示すグラフインデックス４４は、例えば、転置グラフＧｒ、転置グラフＧｒ＋、または転置グラフＧｒ＋＋のうちいずれかである。
【００３７】
図１０は、転置グラフ生成部２６Ｂにより実行される処理の流れの一例を示すフローチャートである。なお、本フローチャートの処理は、図８に示す処理と、図９に示す処理とを明確に分離せず、これらの処理をオブジェクト毎の処理に包含させたものであるが、結果として得られる転置グラフＧｒ＋＋は同じになる。
【００３８】
まず、転置グラフ生成部２６Ｂは、ＲＡＭ２０Ｂまたはデータサーバ４０に記憶された一次グラフからエッジを一つ選択し（Ｓ２００）、参照元と参照先を入れ替える（Ｓ２０２）。次に、転置グラフ生成部２６Ｂは、Ｓ２００において全てのエッジを選択したか否かを判定する（Ｓ２０４）。全てのエッジを選択していない場合、Ｓ２００に戻り、次のエッジを選択する。全てのエッジを選択した場合、Ｓ２０６に処理が進められる。これによって、転置グラフＧｒが生成される。転置グラフＧは、ＲＡＭ２０Ｂまたはデータサーバ４０に格納される。
【００３９】
転置グラフ生成部２６Ｂは、転置グラフＧにおけるオブジェクトを一つ選択する（Ｓ２０６）。以下、Ｓ２０６で選択されたオブジェクトを選択オブジェクトと称する。次に、転置グラフ生成部２６Ｂは、選択オブジェクトに付与されたエッジが無いかどうかを判定する（Ｓ２０８）。選択オブジェクトに付与されたエッジとは、前述したように、選択オブジェクトを参照元とするエッジである。選択オブジェクトに付与されたエッジが無い場合、転置グラフ生成部２６Ｂは、選択オブジェクトに所定数ｋａのエッジを付与する（Ｓ２１０）。例えば、転置グラフ生成部２６Ｂは、選択オブジェクトを参照先とするエッジのうち短い方から順に所定数ｋａのエッジを選択し、これらと逆向きのエッジを選択オブジェクトに付与する。なお、Ｓ２０８およびＳ２１０の処理は必須でなく、付与されたエッジの無いオブジェクトが生じる可能性が低い場合、省略されてもよい。
【００４０】
次に、転置グラフ生成部２６Ｂは、選択オブジェクトに付与されたエッジを長さ順にソートし（Ｓ２１２）、最も短いエッジから順に所定数ｋｒ分、逆向きのエッジを転置グラフＧに追加する（Ｓ２１４）。また、転置グラフ生成部２６Ｂは、最も長いエッジから順に、所定数ｋｍのエッジを残すように削除を行う（Ｓ２１６）。
【００４１】
そして、転置グラフ生成部２６Ｂは、Ｓ２０６において全てのオブジェクトを選択したか否かを判定する（Ｓ２１８）。全てのオブジェクトを選択していない場合、Ｓ２０６に戻り、次のオブジェクトを選択する。全てのオブジェクトを選択した場合、本フローチャートの処理が終了する。これによって、転置グラフＧｒ＋＋が生成される。転置グラフＧｒ＋＋は、グラフインデックス４４としてデータサーバ４０に格納される。
【００４２】
図１１は、上記各グラフを用いて検索を行うシミュレーションの結果を示す図である。本シミュレーションは、画像の局所特徴量ＳＩＦＴをオブジェクトとし、上記説明した各種グラフを用いて、ＳＩＦＴ１０００万件から２０件の近傍オブジェクトを検索するシミュレーションである。このシミュレーションは、前述のように、ｋｐ＝４０、ｋｒ＝２０、ｋｍ＝６０として行った。図１１は、そのシミュレーション結果としての検索時間に対する精度の関係を示している。図中、縦軸は精度（２０件中の正解数の割合）を、横軸は検索時間を示している。このため、特性線が左上に偏しているほどシミュレーション結果が良好であったことになる。図示するように、転置グラフＧｒ＋＋を用いた場合に最も良好なシミュレーション結果が得られ、次いで転置グラフＧｒ＋、転置グラフＧｒ、一次グラフＧの順であった。
【００４３】
以上説明した第１実施形態の検索データ管理装置１によれば、一次グラフＧにおける有向エッジの向きを逆にしたグラフ構造のデータである転置グラフＧｒを、データ検索のためのデータとして生成するため、高速かつ高精度な検索を可能にする有向グラフを生成することができる。
【００４４】
また、第１実施形態の検索データ管理装置１によれば、転置グラフＧｒにおいて、各オブジェクトに付与されたエッジに対して、逆向きのエッジを所定数ｋｒ加えた転置グラフＧｒ＋を生成することにより、より高速かつ高精度な検索を可能にする有向グラフを生成することができる。
【００４５】
また、第１実施形態の検索データ管理装置１によれば、転置グラフＧｒ＋において、各オブジェクトに付与されたエッジを長さ順にソートし、短い順に所定数ｋｍのエッジを残して長いエッジを削除した転置グラフＧｒ＋＋を生成することにより、更に高速かつ高精度な検索を可能にする有向グラフを生成することができる。
【００４６】
第１実施形態において（或いは後述する第２実施形態において）、一次グラフＧは、図５で説明したフローチャートの処理ではなく、以下に説明する処理によって生成される無向グラフＧａに対し、無向エッジを二本の有向エッジとみなし、各オブジェクトに付与されるエッジに上限を設けて、上限を超える分を距離の長いエッジから削減したものであってもよい。
【００４７】
図１２および図１３は、無向グラフＧａを生成する処理の一例を示すフローチャートである。本フローチャートの処理の前提として、既存データオブジェクト４２において、１からｍまでのオブジェクトＩＤが付与されているものとする。フローチャートの中で使用する引数ｙは、１からｍまで順に選択されて処理が実行される。ここでは、近傍オブジェクト集合Ｎ（Ｇ，ｙ）は、オブジェクトｙに対して相互に参照し合うオブジェクトの集合である。
【００４８】
一次グラフ生成部２６Ａは、Ｋ近傍検索処理を実行する（Ｓ３００）。Ｋ近傍検索処理については図１３を用いて説明する。図１３に示すように、一次グラフ生成部２６Ａは、超球の半径ｒを∞（無限大）に設定し（Ｓ４００）、既存のオブジェクト集合から部分集合Ｓを抽出する（Ｓ４０２）。超球とは、検索範囲（その範囲に入っていれば入力オブジェクトｙの近傍オブジェクト集合Ｎ（Ｇ，ｙ）の要素に含められる可能性がある範囲）を示す仮想的な球である。なお、Ｓ４０２で抽出されたオブジェクト集合Ｓに含まれるオブジェクトは、同時にオブジェクト集合Ｒの初期集合にも含められてもよい。
【００４９】
次に、一次グラフ生成部２６Ａは、オブジェクト集合Ｓに含まれるオブジェクトの中で、オブジェクトｙとの距離が最も短いオブジェクトを抽出し、オブジェクトｓとする（Ｓ４０４）。次に、一次グラフ生成部２６Ａは、オブジェクトｓをオブジェクト集合Ｓから除外する（Ｓ４０６）。
【００５０】
次に、一次グラフ生成部２６Ａは、オブジェクトｓとオブジェクトｙとの距離ｄ（ｓ，ｙ）がｒ（１＋ε）を超えるか否かを判定する（Ｓ４０８）。ここで、εは拡張要素であり、ｒ（１＋ε）は、探索範囲（その範囲にあるオブジェクトの近傍オブジェクトについて、入力オブジェクトｙの近傍オブジェクト集合Ｎ（Ｇ，ｙ）の要素に含められるか否かを判定する範囲）の半径を示す値である。オブジェクトｓとオブジェクトｙとの距離ｄ（ｓ，ｙ）がｒ（１＋ε）を超える場合、一次グラフ生成部２６Ａは、オブジェクト集合Ｒをオブジェクトｙの近傍オブジェクト集合Ｎ（Ｇ，ｙ）として出力し（Ｓ４１０）、図１３のフローチャートの処理を終了する。
【００５１】
オブジェクトｓとオブジェクトｙとの距離ｄ（ｓ，ｙ）がｒ（１＋ε）を超えない場合、一次グラフ生成部２６Ａは、オブジェクトｓの近傍オブジェクト集合Ｎ（Ｇ，ｓ）の要素であるオブジェクトの中からオブジェクト集合Ｃに含まれないオブジェクトを一つ選択し、選択したオブジェクトｕを、オブジェクト集合Ｃに格納する（Ｓ４１２）。オブジェクト集合Ｃは、重複検索を回避するために便宜上設けられるものであり、図１３のフローチャートが開始されるときにリセットされて空集合とされる。
【００５２】
次に、一次グラフ生成部２６Ａは、オブジェクトｕとオブジェクトｙとの距離ｄ（ｕ，ｙ）がｒ（１＋ε）以下であるか否かを判定する（Ｓ４１４）。オブジェクトｕとオブジェクトｙとの距離ｄ（ｕ，ｙ）がｒ（１＋ε）以下である場合、一次グラフ生成部２６Ａは、オブジェクトｕをオブジェクト集合Ｓに追加する（Ｓ４１６）。
【００５３】
次に、一次グラフ生成部２６Ａは、オブジェクトｕとオブジェクトｙとの距離ｄ（ｕ，ｙ）がｒ以下であるか否かを判定する（Ｓ４１８）。オブジェクトｕとオブジェクトｙとの距離ｄ（ｕ，ｙ）がｒを超える場合、Ｓ４３０に処理が進められる。
【００５４】
オブジェクトｕとオブジェクトｙとの距離ｄ（ｕ，ｙ）がｒ以下である場合、一次グラフ生成部２６Ａは、オブジェクトｕをオブジェクト集合Ｒに追加する（Ｓ４２０）。
【００５５】
そして、一次グラフ生成部２６Ａは、オブジェクト集合Ｒに含まれるオブジェクト数がｋｓを超えるか否かを判定する（Ｓ４２２）。所定数ｋｓは、任意に定められる自然数である。例えば、ｋｓ＝３である。
【００５６】
オブジェクト集合Ｒに含まれるオブジェクト数がｋｓを超える場合、一次グラフ生成部２６Ａは、オブジェクト集合Ｒに含まれるオブジェクトの中でオブジェクトｙとの距離が最も長いオブジェクトを、オブジェクト集合Ｒから除外する（Ｓ４２４）。
【００５７】
次に、一次グラフ生成部２６Ａは、オブジェクト集合Ｒに含まれるオブジェクト数がｋｓと一致するか否かを判定する（Ｓ４２６）。オブジェクト集合Ｒに含まれるオブジェクト数がｋｓと一致する場合、一次グラフ生成部２６Ａは、オブジェクト集合Ｒに含まれるオブジェクトの中でオブジェクトｙとの距離が最も長いオブジェクトと、オブジェクトｙとの距離を、新たなｒに設定する（Ｓ４２８）。
【００５８】
そして、一次グラフ生成部２６Ａは、オブジェクトｓの近傍オブジェクト集合Ｎ（Ｇ，ｓ）の要素であるオブジェクトから全てのオブジェクトを選択してオブジェクト集合Ｃに格納し終えたか否かを判定する（Ｓ４３０）。オブジェクトｓの近傍オブジェクト集合Ｎ（Ｇ，ｓ）の要素であるオブジェクトから全てのオブジェクトを選択してオブジェクト集合Ｃに格納し終えていない場合、Ｓ４１２に処理が戻される。
【００５９】
オブジェクトｓの近傍オブジェクト集合Ｎ（Ｇ，ｓ）の要素であるオブジェクトから全てのオブジェクトを選択してオブジェクト集合Ｃに格納し終えた場合、一次グラフ生成部２６Ａは、オブジェクト集合Ｓが空集合であるか否かを判定する（Ｓ４３２）。オブジェクト集合Ｓが空集合でない場合、Ｓ４０４に処理が戻され、オブジェクト集合Ｓが空集合である場合、一次グラフ生成部２６Ａは、オブジェクト集合Ｒをオブジェクトｙの近傍オブジェクト集合Ｎ（Ｇ，ｙ）として出力し、図１３のフローチャートの処理を終了する（Ｓ４３４）。
【００６０】
図１２に戻る。オブジェクトｙの近傍オブジェクト集合Ｎ（Ｇ，ｙ）が求められると、一次グラフ生成部２６Ａは、オブジェクトｙの近傍オブジェクト集合Ｎ（Ｇ，ｙ）の要素であるオブジェクトを一つ選択し、オブジェクトｚとする（Ｓ３０２）。次に、一次グラフ生成部２６Ａは、オブジェクトｚの近傍オブジェクト集合Ｎ（Ｇ，ｚ）の要素としてオブジェクトｙを追加する（Ｓ３０４）。
【００６１】
次に、一次グラフ生成部２６Ａは、オブジェクトｚの近傍オブジェクト集合Ｎ（Ｇ，ｚ）の要素であるオブジェクトの数がｋｐを超えるか否かを判定する（Ｓ３０６）。オブジェクトｚの近傍オブジェクト集合Ｎ（Ｇ，ｚ）の要素であるオブジェクトの数が所定数ｋｐを超える場合、一次グラフ生成部２６Ａは、オブジェクトｚの近傍オブジェクト集合Ｎ（Ｇ，ｚ）から、オブジェクトｚとの距離が最も長い（オブジェクトｊから最も遠い）オブジェクトを除外する（Ｓ３０８）。
【００６２】
そして、一次グラフ生成部２６Ａは、オブジェクトｙの近傍オブジェクト集合Ｎ（Ｇ，ｙ）の要素であるオブジェクトｚを全て選択したか否かを判定する（Ｓ３１０）。オブジェクトｙの近傍オブジェクト集合Ｎ（Ｇ，ｙ）の要素であるオブジェクトｚを全て選択していない場合はＳ３０２に処理が戻され、オブジェクトｙの近傍オブジェクト集合Ｎ（Ｇ，ｙ）の要素であるオブジェクトｚを全て選択した場合はＳ３００〜Ｓ３０８のループ処理の１回分が終了する。これによって、無向グラフＧａが生成される。
【００６３】
＜第２実施形態＞
以下、第２実施形態について説明する。第２実施形態において、インデックス検索部２４は、下記のような処理を行うことで、検索対象のオブジェクトの数を低減し、より高速な検索処理を実現する。
【００６４】
図１４は、第２実施形態に係るインデックス検索部２４の処理の内容を説明するための図である。これについて、インデックス検索部２４の処理としても採用される図１３の処理を参照しながら説明する。図中Ｑはクエリデータに対応するオブジェクトであり、Ｏ１は、検索処理（図１３に示す処理）の中のＳ４１２で選択されたオブジェクトｕに相当する。オブジェクトｕとオブジェクトＱの距離Ｄ１は、Ｓ４１２の時点で既に算出されている。一方、オブジェクトＯ２、Ｏ３、およびＯ４は、オブジェクトｕの近傍オブジェクト集合Ｎ（Ｇ，ｕ）の要素である。また、Ｄ０はオブジェクトＱを基準とした検索範囲の仮想的な半径（Ｓ４１８のｒ）、または探索範囲の仮想的な半径（Ｓ４１４のｒ（１＋ε））である。図１３の説明と同様に、検索範囲とは、その範囲内に無ければクエリデータと類似しないと判定される範囲であり、探索範囲とは、オブジェクトを辿る過程で、その範囲内に無いオブジェクトは参照されない範囲である。本来、オブジェクトＱと、オブジェクトＯ２、Ｏ３、およびＯ４のそれぞれとの間の距離を算出して、Ｓ４１４またはＳ４１８の判定処理を行うのであるが、この距離を算出せずにＳ４１４またはＳ４１８の判定処理を行うことが可能な状態が存在する。
【００６５】
図１４に示す状態において、まず、オブジェクトＱとオブジェクトＯ１との距離が算出される。距離Ｄ１＞距離Ｄ０であるので、オブジェクトＯ１で表されるデータは、オブジェクトＱで表されるデータとは類似しないと判定される。ここで、オブジェクトＯ２、Ｏ３、Ｏ４のそれぞれについて、オブジェクトＱとの距離は未だ算出されていないが、オブジェクトＯ１とオブジェクトＱとの距離は算出されている。
【００６６】
この場合、オブジェクトＯ２に関しては、［Ｄ２＜（Ｄ１−Ｄ０）］であるため、検索範囲または探索範囲の中には入らないことが明らかである。従って、オブジェクトＱとオブジェクトＯ２の距離を算出するまでもなく、オブジェクトＯ２で表されるデータは、オブジェクトＱで表されるクエリデータと類似しないと判定される。
【００６７】
オブジェクトＯ３に関しては、［Ｄ３＞（Ｄ１−Ｄ０）］であるため、検索範囲または探索範囲の中に入る可能性がある。従って、オブジェクトＱとオブジェクトＯ３の距離が算出され、オブジェクトＯ３で表されるデータが、オブジェクトＱで表されるクエリデータと類似するか否かが判定される。
【００６８】
オブジェクトＯ４に関しては、［Ｄ４＞（Ｄ１＋Ｄ０）］であるため、検索範囲または探索範囲の中には入らないことが明らかである。従って、オブジェクトＱとオブジェクトＯ４の距離を算出するまでもなく、オブジェクトＯ４で表されるデータは、オブジェクトＱで表されるクエリデータと類似しないと判定される。
【００６９】
このように、第２実施形態に係るインデックス検索部２４は、あるオブジェクト（図１４ではＯ１）についてクエリデータを表すオブジェクトとの距離を算出し、検索範囲または探索範囲の中には入らないことが判明した場合には、図中の範囲Ａ０またはＡ１に含まれるオブジェクトのみを距離算出の対象とし、Ａ２またはＡ３に含まれることが明らかなオブジェクトに関しては、距離算出の対象とせず棄却する。これによって、より高速な検索処理を実現することができる。
【００７０】
以上説明した第２実施形態の検索データ管理装置１によれば、より高速な検索処理を実現することができる。
【００７１】
なお、第２実施形態の処理を実行する場合、転置グラフＧｒ＋を求めることで、第１実施形態における転置グラフＧｒ＋＋と同程度の性能を発揮することができる。
【００７２】
以上、本発明を実施するための形態について実施形態を用いて説明したが、本発明はこうした実施形態に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変形及び置換を加えることができる。
【符号の説明】
【００７３】
１…検索データ管理装置、１０…ネットワークインターフェース、２０…制御部、２２…データオブジェクト生成部、２４…インデックス検索部、２６…グラフインデックス編集部、２６Ａ…一次グラフ生成部、２６Ｂ…転置グラフ生成部、３０…入出力装置、４０…データサーバ、４２…既存データオブジェクト、４４…グラフインデックス
【図１】
2018032374.tif 000003
【図２】
2018032374.tif 000004
【図３】
2018032374.tif 000005
【図４】
2018032374.tif 000006
【図５】
2018032374.tif 000007
【図６】
2018032374.tif 000008
【図７】
2018032374.tif 000009
【図８】
2018032374.tif 000010
【図９】
2018032374.tif 000011
【図１０】
2018032374.tif 000012
【図１１】
2018032374.tif 000013
【図１２】
2018032374.tif 000014
【図１３】
2018032374.tif 000015
【図１４】
2018032374.tif 000016
【手続補正書】
【提出日】平成30年1月18日(2018.1.18)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ検索の対象となる複数のノードを記憶する記憶部と、
前記記憶部に記憶された各ノードから近傍ノードに対して有向エッジが設定されたグラフ構造のデータである一次グラフを生成する一次グラフ生成部と、
前記記憶部に記憶された一次グラフにおける前記有向エッジの向きを逆にしたグラフ構造のデータである転置グラフを、データ検索のためのデータとして生成する転置グラフ生成部と、
を備える検索データ管理装置。
【請求項２】
前記一次グラフ生成部は、着目ノードから距離が短い順に所定数のノードが選択され、前記着目ノードから前記選択された所定数のノードに対して有向エッジが設定されたグラフ構造のデータを、前記一次グラフとして生成する、
請求項１記載の検索データ管理装置。
【請求項３】
前記一次グラフ生成部は、複数のノードに対して無向エッジが設定されたグラフ構造のデータに対し、無向エッジを二本の有向エッジとみなし、各ノードから他のノードに向かうエッジの数にそれぞれ上限を設け、上限を超える分を距離の長いエッジから順に削減することで、前記一次グラフを生成する、
請求項１記載の検索データ管理装置。
【請求項４】
前記転置グラフ生成部は、エッジを付与された各ノードに対して、前記エッジの逆向きのエッジを所定数または所定割合加えたグラフを、データ検索のためのデータである前記転置グラフとして生成する、
請求項１から３のうちいずれか１項記載の検索データ管理装置。
【請求項５】
前記転置グラフ生成部は、エッジを付与された各ノードに対して、所定数または所定割合のエッジが短い順に残るように前記付与されたエッジを削除したグラフを、データ検索のためのデータである前記転置グラフとして生成する、
請求項１から４のうちいずれか１項記載の検索データ管理装置。
【請求項６】
クエリデータから得られるクエリオブジェクトと前記転置グラフに含まれるノードに対応するオブジェクトとの距離を計算することによって、前記クエリデータに類似するデータを検索する検索部であって、
前記クエリオブジェクトを基準とした検索範囲または探索範囲の仮想半径と、前記転置グラフに含まれる第１のノードに対応する第１のオブジェクトと前記クエリオブジェクトとの間の第１の距離と、前記第１のオブジェクトと前記転置グラフに含まれる第２のノードに対応する第２のオブジェクトとの間の第２の距離との関係に基づいて、前記第２のノードと前記クエリデータとの類似を判定するか否かを決定する検索部を更に備える、
請求項１から５のうちいずれか１項記載の検索データ管理装置。
【請求項７】
前記検索部は、前記第１のオブジェクトが前記クエリオブジェクトに類似しない場合において、前記第１の距離から前記仮想半径を差し引いた距離が、前記第２の距離よりも大きい場合に、前記第２のノードと前記クエリデータとの類似を判定しないと決定する、
請求項６記載の検索データ管理装置。
【請求項８】
前記検索部は、前記第１のオブジェクトが前記クエリオブジェクトに類似しない場合において、前記第１の距離に前記仮想半径を加算した距離が、前記第２の距離よりも小さい場合に、前記第２のノードと前記クエリデータとの類似を判定しないと決定する、
請求項６または７記載の検索データ管理装置。
【請求項９】
コンピュータが、
データ検索の対象となる複数のノードに含まれる各ノードから近傍ノードに対して有向エッジが設定されたグラフ構造のデータである一次グラフを生成し、
前記生成した一次グラフにおける前記有向エッジの向きを逆にしたグラフ構造のデータである転置グラフを、データ検索のためのデータとして生成する、
検索データ管理方法。
【請求項１０】
コンピュータに、
データ検索の対象となる複数のノードに含まれる各ノードから近傍ノードに対して有向エッジが設定されたグラフ構造のデータである一次グラフを生成させ、
前記生成させた一次グラフにおける前記有向エッジの向きを逆にしたグラフ構造のデータである転置グラフを、データ検索のためのデータとして生成させる、
検索データ管理プログラム。