(57)【要約】【課題】データ群から類似するデータを高速に検索すると共に、データ登録による検索速度の低下を防止すること。【解決手段】グラフインデックスのデータ間のリンクを巡回して類似データを検索するという検索アルゴリズムを用いて、登録データに対する類似データを検索し、その類似データと登録データとの間に新たにリンクを生成することで、検索装置１がリンクを辿って検索しているグラフインデックスにデータ登録して、登録後に巡回するデータとしてリンクを形成していく。また、データの登録を行う都度、新たにリンクが形成されたデータのリンク数の最適化を行う。【選択図】図１
2011090351.tif 000002
【特許請求の範囲】
【請求項１】
一方のデータから他方のデータに辿るためのリンクがデータ間に設定されて該データが複数記憶されたデータベースと、
入力された検索対象のデータに対し、前記データベースに記憶されたデータのうちの何れかを検索開始点として選択し、該検索開始点から前記リンクを順次辿ることによって、該リンクを辿る経路上にあるデータのうち、該検索対象のデータと既定の距離内にあるデータを類似データとして検索し出力するグラフ検索手段と、
前記データベースへの登録対象となるデータを前記グラフ検索手段に入力することにより、該登録対象のデータに対する類似データを取得する類似データ取得手段と、
前記登録対象となるデータと、前記類似データ取得手段により取得された類似データとの間にリンクを設定して前記データベースに記憶すると共に、該類似データに設定されているリンクの削減処理を行うリンク最適化手段と、
を備えることを特徴とする検索データ管理装置。
【請求項２】
前記リンク最適化手段は、
前記類似データに設定されたリンクが所定数以上である場合に、該リンクが設定されたデータ間の距離が短い順に該所定数分の該リンクを保持し、他のリンクを解除することを特徴とする請求項１に記載の検索データ管理装置。
【請求項３】
前記リンク最適化手段は、
前記リンクの削減対象のデータにリンクされている他方のデータの中から、リンクを保持する保持データと、リンクを解除する解除データとを特定し、
解除データと保持データとの間の距離に基づいて、該解除データと該保持データとの間にリンクを設定して前記データベースに記憶することを特徴とする請求項１又は２に記載の検索データ管理装置。
【請求項４】
前記グラフ検索手段は、
前記データベースから任意のデータを選択し、そのデータから前記リンクを順次辿ることにより前記登録対象のデータから前記既定の距離内のデータを探索して、該データを検索開始点として選択することを特徴とする請求項１〜３の何れか一項に記載の検索データ管理装置。
【請求項５】
前記グラフ検索手段は、
前記任意のデータからリンクを辿った結果、該リンクを辿る経路上にあるデータの中に、前記規定の距離内にあるデータがない場合には、選択済みの前記任意のデータとは異なるデータを新たに選択して、再度前記リンクを順次辿る処理を行って前記検索開始点を探索することを特徴とする請求項４に記載の検索データ管理装置。
【請求項６】
前記データベースに記憶されたデータを空間分割により階層化し、該データが属する階層毎に記憶する階層データベースを更に備え、
前記グラフ検索手段は、
前記登録対象のデータが属する前記階層を特定し、その特定した階層に属する他のデータを前記検索開始点として選択することを特徴とする請求項１〜３の何れか一項に記載の検索データ管理装置。
【請求項７】
前記グラフ検索手段は、
前記階層データベースに基づいて選択した前記検索開始点と、前記登録対象のデータとの距離が前記規定の距離より離れている場合には、前記データベースから任意のデータを選択し、そのデータに対するリンクを辿ることで該規定の距離内のデータを探索して、該検索開始点として選択することを特徴とする請求項６に記載の検索データ管理装置。
【請求項８】
一方のデータから他方のデータに辿るためのリンクがデータ間に設定されて該データが複数記憶されたデータベースをコンピュータが検索対象のデータ群としてデータ管理する検索データ管理方法において、
入力された検索対象となるデータに対し、前記データベースに記憶されたデータのうちの何れかを検索開始点として選択し、該検索開始点から前記リンクを順次辿ることによって、該リンクを辿る経路上にあるデータのうち、該検索対象のデータと既定の距離内にあるデータを類似データとして検索して出力するグラフ検索工程と、
前記データベースへの登録対象となるデータを前記検索対象として前記グラフ検索工程において検索させて、該登録対象のデータに対する類似データを取得する類似データ取得工程と、
前記登録対象となるデータと、前記類似データ取得工程において取得された類似データとの間にリンクを設定して前記データベースに記憶すると共に、該類似データに設定されているリンクの削減処理を行うリンク最適化工程と、
を前記コンピュータが行うことを特徴とする検索データ管理方法。
【請求項９】
請求項８に記載の検索方法の処理をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似データをデータベースから検索すると共に、そのデータベースに新たなデータを登録するための装置に関するものである。
【背景技術】
【０００２】
画像や音声等から抽出される特徴量は、多次元のベクトルデータで表され、各ベクトルデータ間の距離等を用いて類似データの検索が行われる。多次元ベクトルデータの検索において、検索対象のデータ数が多い場合、検索キーとなるデータ（検索データ）と検索対象のデータとの距離を逐一計算しなければならないため、検索に要する時間が非常に長くなってしまう。
【０００３】
特許文献１には、次のような技術が記載されている。即ち、データベース内の全ての特徴量について、他の特徴量との間の類似度を予め計算し、類似度の高いデータをそれぞれ関連付けて格納しておく。そして、与えられた検索キーの最近傍を求めてその最近傍のデータに対応する類似データを検索結果として返す。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−５２０２４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、検索対象のデータ群（データベース）に新たなデータを登録しようとするときは、データ間の類似度を考慮したインデックスを予め付与しておくことで、検索の高速性を担保できる。このため、その登録データに対する類似データをデータベース中から検索する必要がある。
【０００６】
しかし、特許文献１の技術では、検索の高速化のために、各データに対して全データを類似度順に記憶しておく必要があるが、データベースの全データとの類似度を事前計算する必要があり、検索対象のデータが膨大になると、データ数に応じて検索にかかる時間が長くなってしまった。また、データ登録を行う都度、データ間の類似度を算出して、インデックスの見直しを行う必要があるため、データ数が増えるほど、そのインデックスの構築が煩雑になってしまった。
【０００７】
本発明は、上述の課題に鑑みて為されたものであり、その目的とするところは、類似データの検索対象であるデータ群に、検索インデックスを煩雑にすることなく高速にデータを登録することである。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、第１の発明の検索データ管理装置は、
一方のデータから他方のデータに辿るためのリンクがデータ間に設定されて該データが複数記憶されたデータベースと、
入力された検索対象のデータに対し、前記データベースに記憶されたデータのうちの何れかを検索開始点として選択し、該検索開始点から前記リンクを順次辿ることによって、該リンクを辿る経路上にあるデータのうち、該検索対象のデータと既定の距離内にあるデータを類似データとして検索し出力するグラフ検索手段と、
前記データベースへの登録対象となるデータを前記グラフ検索手段に入力することにより、該登録対象のデータに対する類似データを取得する類似データ取得手段と、
前記登録対象となるデータと、前記類似データ取得手段により取得された類似データとの間にリンクを設定して前記データベースに記憶すると共に、該類似データに設定されているリンクの削減処理を行うリンク最適化手段と、
を備えることを特徴としている。
【０００９】
また、第２の発明において、前記リンク最適化手段は、
前記類似データに設定されたリンクが所定数以上である場合に、該リンクが設定されたデータ間の距離が短い順に該所定数分の該リンクを保持し、他のリンクを解除することを特徴としている。
【００１０】
また、第３の発明において、前記リンク最適化手段は、
前記リンクの削減対象のデータにリンクされている他方のデータの中から、リンクを保持する保持データと、リンクを解除する解除データとを特定し、
解除データと保持データとの間の距離に基づいて、該解除データと該保持データとの間にリンクを設定して前記データベースに記憶することを特徴としている。
【００１１】
また、第４の発明において、前記グラフ検索手段は、
前記データベースから任意のデータを選択し、そのデータから前記リンクを順次辿ることにより前記登録対象のデータから前記既定の距離内のデータを探索して、該データを検索開始点として選択することを特徴としている。
【００１２】
また、第５の発明において、前記グラフ検索手段は、
前記任意のデータからリンクを辿った結果、該リンクを辿る経路上にあるデータの中に、前記規定の距離内にあるデータがない場合には、選択済みの前記任意のデータとは異なるデータを新たに選択して、再度前記リンクを順次辿る処理を行って前記検索開始点を探索することを特徴としている。
【００１３】
また、第６の発明において、
前記データベースに記憶されたデータを空間分割により階層化し、該データが属する階層毎に記憶する階層データベースを更に備え、
前記グラフ検索手段は、
前記登録対象のデータが属する前記階層を特定し、その特定した階層に属する他のデータを前記検索開始点として選択することを特徴としている。
【００１４】
また、第７の発明において、前記グラフ検索手段は、
前記階層データベースに基づいて選択した前記検索開始点と、前記登録対象のデータとの距離が前記規定の距離より離れている場合には、前記データベースから任意のデータを選択し、そのデータに対するリンクを辿ることで該規定の距離内のデータを探索して、該検索開始点として選択することを特徴としている。
【００１５】
また、第８の発明は、一方のデータから他方のデータに辿るためのリンクがデータ間に設定されて該データが複数記憶されたデータベースをコンピュータが検索対象のデータ群としてデータ管理する検索データ管理方法において、
入力された検索対象となるデータに対し、前記データベースに記憶されたデータのうちの何れかを検索開始点として選択し、該検索開始点から前記リンクを順次辿ることによって、該リンクを辿る経路上にあるデータのうち、該検索対象のデータと既定の距離内にあるデータを類似データとして検索して出力するグラフ検索工程と、
前記データベースへの登録対象となるデータを前記検索対象として前記グラフ検索工程において検索させて、該登録対象のデータに対する類似データを取得する類似データ取得工程と、
前記登録対象となるデータと、前記類似データ取得工程において取得された類似データとの間にリンクを設定して前記データベースに記憶すると共に、該類似データに設定されているリンクの削減処理を行うリンク最適化工程と、
を前記コンピュータが行うことを特徴としている。
【００１６】
また、第９の発明のプログラムは、検索データ管理方法の処理をコンピュータに実行させることを特徴としている。
【発明の効果】
【００１７】
本発明によれば、データベースにデータを登録する際には、データ間に設定されたリンクを辿った経路上のデータの中から規定の距離内の類似データが検索されるため、データベース内の全データに対して距離を算出する必要がなく、データ群から類似するデータを高速に検索するため、データ登録を高速に行うことができる。また、データベース内にデータ登録する際に、類似データの設定されているリンクの削減をするため、データ登録によってデータ間のリンク構造が煩雑になることを逐次防止できるため、データ登録による検索速度の低下を防止することが可能になる。
【発明を実施するための最良の形態】
【００１８】
〔第１実施形態の装置構成〕
本発明を適用した第１実施形態に係る検索装置を、添付の図面に基づいて説明する。尚、本発明の内容は、本実施形態に限定されるものではなく、特許請求の範囲に記載された範囲内において、具体的な構成に対して種々の変更を加えうるものである。
【００１９】
また、本実施形態では、ベクトルデータとして、画像の特徴量を表す多次元ベクトルデータを扱う例を説明する。但し、ベクトルデータとしては、音声やその他のマルチメディアデータ情報の特徴量を表すものであってもよいし、他の種類の多次元データであってもよい。
【００２０】
図１は、本発明の一例である検索装置１の機能構成を示すブロック図である。検索装置１は、一つのハードウエアあるいはソフトウエアにより構成される必要はない。必要に応じて、複数のハードウエアあるいはソフトウエアの組み合わせにより検索装置１に相当する機能を提供することができる。ネットワーク上に点在する複数のサーバにより、本実施形態の検索装置１を構成することもできる。
【００２１】
検索装置１は、クライアント端末から送信される各種要求に応じてデータ処理を行って、その処理結果をクライアント端末に返送する。具体的に、検索装置１は、検索要求である検索クエリを受信すると、検索クエリに応じた検索を行って検索結果をクライアント端末に返送する。また、検索対象のデータを格納したデータベース（以下「ＤＢ」と略す）に新たなデータを登録する要求を受信した場合にはＤＢに登録する。
【００２２】
［クライアント端末の構成］
クライアント端末の図示は省略するが、キーボードやマウスやタッチパッドといった入力手段と、ディスプレイやプリンタといった出力手段と、ＣＰＵ等を備えたパーソナルコンピュータにより構成される。クライアント端末は、ネットワークを介して検索装置１と接続されている。また、クライアント端末は、ユーザに指定された検索データや登録データを検索装置１に送る。
【００２３】
ここで、検索データとは、検索装置１のデータベースに記憶されたデータの中から類似するデータを検索するためのキーとなるデータである。また、登録データとは、検索装置１のデータベースに新たに登録するデータである。尚、検索データ及び登録データから抽出したベクトルデータも以下「検索データ」、「登録データ」という。
【００２４】
［検索装置の構成］
図１によれば、検索装置１は、登録データ入力部１０と、検索データ入力部２０と、検索結果出力部３０と、グラフ検索部４０と、データ登録部５０と、画像ＤＢ６０と、グラフインデックスＤＢ７０とを備えて構成される。
【００２５】
登録データ入力部１０は、クライアント端末から送信される登録データを受け付ける機能部であり、データの登録要求と共に登録データを受信すると、該登録データをデータ登録部５０に入力する。
【００２６】
検索データ入力部２０は、クライアント端末から送信される検索データを受け付けるための機能部であり、検索要求と共に検索データを受信すると、その検索データをグラフ検索部４０に入力する。
【００２７】
検索結果出力部３０は、検索データ入力部２０の入力に応じてグラフ検索部４０による検索結果をクライアント端末に送信するための機能部である。検索結果出力部３０は、検索結果を表示するための表示データを生成してクライアント端末に送信する。
【００２８】
画像ＤＢ６０は、検索対象となる画像データを蓄積記憶するデータベースであり、図１に示すように画像ＩＤと、画像データと、ベクトルデータとを対応付けて記憶する。グラフ検索部４０は、この画像ＤＢ６０に記憶された画像データから複数の特徴量である多次元のベクトルデータを抽出して記憶する。ベクトルデータの次元数は特に制約されないが、検索精度を高めるためには、高い次元数（例えば１０次元以上）とすることが好ましい。
【００２９】
グラフインデックスＤＢ７０は、グラフ構造のインデックスを記憶するデータベースであり、検索対象となるデータの特徴量を表すベクトルデータを格納している。データ登録部５０は、画像データから抽出したベクトルデータに基づいてグラフ構造のインデックスを生成する。
【００３０】
また、グラフインデックスＤＢ７０は、一方のベクトルデータから他方のベクトルデータに辿るために設定されたリンクの情報が格納されている。具体的には、図１に示すように、グラフインデックスＤＢ７０は、画像ＤＢ６０に対応したリンク元である画像ＩＤと、このベクトルデータにリンクされた一つ以上の他方のリンク先の画像ＩＤとを対応付けて記憶する。ベクトルデータ間にリンクを張ることにより、図４（ａ）に示すようにベクトル空間上のベクトルデータａ〜ｆの間にグラフ構造が形成される。
【００３１】
このグラフインデックスＤＢ７０のリンク情報により形成されるグラフ構造、即ち、該リンク情報を適宜「グラフインデックス」という。リンクとは、一つのデータから他のデータを辿ることができる情報である。リンクは一方向であってもよいが、図１に示すように、一方のリンク先を示すデータとその逆方向のリンク先を示すデータとを対に記憶して双方向に辿れる構成とすることで、データの検索速度を向上できる。
【００３２】
図４（ａ）においては、ベクトルデータを点（ａ〜ｆ）により表しており、多次元の特徴量空間にベクトルデータが分布している様子を示している。また、各ベクトルデータの間にリンクが設定され、実線により該リンクが表されている。以下の説明において、ベクトルデータを適宜「点」と称して説明する。
【００３３】
グラフ検索部４０は、グラフインデックスＤＢ７０に設定されているリンクを巡回することにより検索データに類似するデータを検索する。グラフ検索部４０は、図１に示すようにベクトルデータ生成部４１と、検索開始点決定部４３と、グラフ巡回部４５と、類似データ特定部４７とを備えて構成される。
【００３４】
ベクトルデータ生成部４１は、検索データ入力部２０又はデータ登録部５０から入力されたデータから多次元のベクトルデータとなる特徴量を抽出する。
【００３５】
検索開始点決定部４３は、検索データから抽出したベクトルデータに近接するグラフインデックス上の既存のベクトルデータを、検索開始点として決定する。グラフ検索部４０は、複数のベクトルデータのうちのいずれかを検索開始点として決定し、この検索開始点を起点としてリンクの巡回を始める。
【００３６】
グラフ巡回部４５は、既定の検索終了条件を満たすまで、検索開始点からグラフインデックスＤＢ７０に設定されているリンクを順次辿る処理を行う。
【００３７】
類似データ特定部４７は、グラフ巡回部４５が辿ったリンクの経路上にあるベクトルデータのうち、検索データに対して既定の距離内にあるベクトルデータを類似データとして特定する。この特定した類似データ、或いはそれに関連する情報が検索結果としてクライアント端末に送られる。
【００３８】
データ登録部５０は、登録データ入力部１０から入力された登録データを画像ＤＢ６０及びグラフインデックスＤＢ７０に登録する処理を行う。データ登録部５０は、登録データとして入力された画像データに新たな画像ＩＤを割り当てて、画像ＤＢ６０に記憶する。また、画像データから抽出したベクトルデータに画像ＩＤを対応付けて画像ＤＢ６０に記憶する。
【００３９】
図１によれば、データ登録部５０は、類似データ取得部５１と、リンク登録部５３と、リンク最適化部５５とを備えて構成される。
【００４０】
類似データ取得部５１は、登録データ入力部１０から入力された登録データについての類似データを検索する要求をグラフ検索部４０に出力することで、登録データに類似するデータを取得する。
【００４１】
リンク登録部５３は、登録データと、類似データ取得部５１により取得された類似データとの間にリンクを設定して、グラフインデックスＤＢ７０に記憶する。具体的には、登録データについての画像ＩＤとベクトルデータとをグラフインデックスＤＢ７０に登録する際に、類似データの画像ＩＤをリンク先として対応付けて記憶する。また、類似データの画像ＩＤに対したリンク先に、登録データの画像ＩＤを追加することで、登録データと類似データとの間に相互のリンクが形成される。
【００４２】
リンク最適化部５５は、リンク登録部５３により登録された新たなリンクにより、グラフインデックスのグラフ構造が煩雑にならないようリンクの最適化を行う機能部である。詳細は後述するが、簡単に説明すると、類似データに対してリンク先を追加することにより、類似データからのリンク数が増加していき、これにより、グラフ検索部４０が巡回するリンクが増加してしまい、検索速度の低下を招く可能性がある。そのため、類似データからのリンク先を追加する際には、そのリンク数を適正に保つよう、リンクの見直しを行う。
【００４３】
検索装置１は、グラフ構造を有する検索インデックスであるグラフインデックスＤＢ７０を生成し、グラフ構造上のリンクを辿ることにより検索データに類似するデータを検索する。また、登録データが入力された場合には、検索時に巡回する検索インデックスに登録データを新たに追加して、該登録データも巡回経路とすることによりその登録データの検索も可能になるように、自己生成的にグラフインデックスを形成していく。
【００４４】
〔検索装置の動作〕
次に、本実施形態における検索装置１がデータの登録時に行うグラフ自己生成処理の動作を、図２〜６を参照して詳細に説明する。このグラフ自己生成処理は、予め検索装置１のメモリ上に記憶されたプログラムに基づくことにより実行される。図２及び３は、検索装置１の動作の一例を示すフローチャートであり、図４〜６は、グラフインデックス上でのデータ検索並びにリンク最適化の処理の様子を示す図である。
【００４５】
〔グラフ自己生成処理〕
まず、検索装置１は、初期設定処理を行う（ステップＳ１）。ここでの初期設定は、データ登録を行った場合に新たに登録したデータに設定するリンク数や、リンク削減を行う際の閾値（リンク削減閾値）を予め設定する。
【００４６】
次に、登録データ入力部１０から登録データがデータ登録部５０に入力されると（ステップＳ２）、類似データ取得部５１が登録データをグラフ検索部４０に出力してグラフ検索処理を行わせる（ステップＳ３）。
【００４７】
〔グラフ検索処理〕
グラフ検索部４０がグラフ検索処理を開始すると、先ず、ベクトルデータ生成部４１は、登録データから特徴量を抽出することで、ベクトルデータを生成する（ステップＳ４１）。
【００４８】
〔検索開始点決定処理〕
ついで、検索開始点決定部４３が、登録データに近接するベクトルデータを、検索開始点として決定する（ステップＳ４３）。図３は、検索開始点を決定するための処理の一例を示すフローチャートである。
【００４９】
検索開始点決定部４３は、先ず、グラフインデックスの中から任意の点（例えば、図４（ｂ）の点ａ）を選択し（ステップＳ４３０）、その選択した点（選択点）にリンクされた点（例えば、図４（ｃ）の点ｂ及びｃ）をグラフインデックスＤＢ７０に基づいて取得する（ステップＳ４３２）。
【００５０】
次に、そのリンクされた点（リンク先）に対する登録データとの特徴量空間における距離を算出する（ステップＳ４３４）。検索開始点決定部４３は、算出した距離の中で登録データと距離が最短の点を抽出し（ステップＳ４３６）、その点と登録データとの距離Ｄ２が、登録データと選択点との距離Ｄ１よりも小さいかを判定する（ステップＳ４３８、４４０）。図４（ｄ）において、選択点ａと登録データｇとの間の距離Ｄ１と、選択点ａとリンク先ｃとの間の距離Ｄ２とを比較すると、距離Ｄ２のほうが小さいと判定される。
【００５１】
検索開始点決定部４３は、距離Ｄ２が距離Ｄ１より小さいと判定した場合には（ステップＳ４４０；Ｙｅｓ）、ステップＳ４３６において抽出した点を選択して（ステップＳ４４２）、ステップＳ４３２に処理を移行する。
【００５２】
即ち、ステップＳ４３２〜Ｓ４４２のループ処理を行うことにより、最初に任意に選択した点からグラフインデックス上で登録データに近い点を選んでいくようにリンクを辿っていくこととなる。
【００５３】
検索開始点決定部４３は、ステップＳ４４０において、距離Ｄ２が距離Ｄ１よりも大きいと判定した場合には（ステップＳ４４０；Ｎｏ）、選択している点を検索開始点として決定する（ステップＳ４４４）。
【００５４】
図４（ｅ）においては、最初に選択された点ａから登録データｇに近い点が順次選択され、点ｃ→点ｂ→点ｄとリンクが巡回されて、登録データに最も近い点ｄが検索開始点として決定される。
【００５５】
尚、上述した検索開始点決定処理において、距離Ｄ２が距離Ｄ１よりも大きいとして検索開始点を決定した場合にも、その検索開始点が登録データを中心とした検索範囲よりも外にある場合がある。この場合、検索開始点が検索範囲外にあるので検索を開始することができない。そのため、ステップＳ４４４で決定した検索開始点が検索範囲外である場合には、新たにグラフインデックス内から任意点を選択して、検索開始点決定処理を所定回数行うことで検索範囲内の検索開始点を決定する。
【００５６】
また、ステップＳ４３０で任意選択する点をランダムに選択すると、検索開始点決定処理を繰り返し行った場合に、近接した点を再度選択してしまう可能性がある。その場合、その近接した点からリンクを辿ったとしても同経路のリンクを辿る可能性が高くなり、検索範囲内の検索開始点を決定することができない。
【００５７】
そのため、検索開始点決定処理を所定回数繰り返し行う場合には、過去に選択した点から所定距離離れた点を新たに選択することが好ましい。予めベクトル空間上で分散した点を複数特定しておきその中から任意点を選択することとしてもよい。これにより、検索範囲内の検索開始点を効率よく決定することができる。
【００５８】
［グラフの巡回］
上述のようにして検索開始点を決定すると、グラフ巡回部４５が、検索開始点を起点としてリンクを順次辿っていく（ステップＳ４５）。このとき、一つのベクトルデータからリンクが分岐している（つまり複数の進路がある）場合もあり、その場合には、辿った経路上にあったベクトルデータ、或いはそれを特定するための情報を、適宜の方法で検索装置１のメモリに記憶しておく。
【００５９】
［類似データの検索］
グラフ巡回部４５は、経路上のリンクを辿りながら、規定の検索終了条件を満たすかどうかを判断する。検索終了条件としては、種々のものが考えられる。例えば、以下の何れかの検索終了条件がありうる。
【００６０】
（検索終了条件１）
検索開始点を始点としてリンクを辿った結果が、登録データを中心とした所定の検索範囲（例えば、図５（ａ）の検索範囲）をα倍（α＞１）した範囲（すなわち検索限界範囲）を越えること。ここで、αは、例えば１．５など、適宜の値を採用することができる。αを大きくする程、検索もれを少なくできる。一方、αを小さくする程、検索時間を短縮できる。
【００６１】
リンクを辿って検索したデータの数が増えた場合に、αの値を減少させることで、検索を早期に終了させることができる。これにより、データの数が過大である場合でも、検索結果を早期に取得することができる。なお、αの値は、１以下にならないように設定することが、検索精度を高めるためには好ましい。但し、早期に検索を終了させたい場合は、α＜１とすることも可能である。
【００６２】
（検索終了条件２）
検索開始点を始点とするリンクを辿った結果が、登録データを中心とした検索範囲の外側において、リンクを、既定の回数だけ何れも辿ったこと。
【００６３】
ここで、既定の回数とは、例えば５回であるが、適宜の値を採用することができる。例えば、図５（ａ）において、点ｂから点ａを辿ると、検索範囲を超えてしまうが、検索範囲を超えてから更に１回リンクを辿ると点ｃに辿り着く。このように、検索範囲の外側での巡回数を設定することで、検索漏れを少なくできる。
【００６４】
一つの経路について検索終了条件を満たしたとき、他の経路におけるリンクを辿る。いずれの経路についても検索終了条件を満たしたとき、次のステップに移る。
【００６５】
類似データ特定部４７は、検索終了条件を満たすまでグラフの巡回を行い（ステップＳ４７→Ｓ４５）、検索終了条件を満たした場合は（ステップＳ４７；Ｙｅｓ）、巡回した点（ベクトルデータ）と、登録データとの距離を算出し、その距離に基づいてランキングした類似データを出力する（ステップＳ４９）。
【００６６】
例えば、図５（ａ）において検索開始点を点ｄとした場合は、リンク先である点ｂ、ｅ、ｆのリンクを辿り、図５（ｂ）のように次に点ｅにリンクされている点ｃに辿る。そして、図５（ｃ）のように点ｃから点ａに辿ると検索範囲を超える。この検索範囲を超えたことが検索終了条件である場合に、リンクの巡回を終了する。
【００６７】
そして、検索開始点の点ｄから辿った、点ｂ〜ｆそれぞれと登録データｇとの距離に基づいて類似データのランキングを得る。図５（ｃ）においては、点ｄ、ｂ、ｃ、ｅ、ｆといった順でランキングが得られる。
【００６８】
グラフ検索部４０による類似データの検索が終了すると、データ登録部５０のリンク登録部５３が登録データと類似データとの間にリンクを設定する（ステップＳ５）。ここで、リンク登録部５３は、登録データと類似データとの間の仮のリンクを生成して、後述のリンク最適化処理後にグラフインデックスＤＢ７０に記憶することとしてもよい。尚、仮のリンクも一つベクトルデータから他方のベクトルデータに辿るためのものであり、一時的にメモリに保持される。
【００６９】
検索された類似データのランキングの上位から、初期設定により設定されたリンク数分の類似データが選択されて、その類似データに対して仮のリンクが設定される。例えば、リンク数が‘３’である場合には、図５（ｄ）のように登録データｇに類似データの点ｂ、ｃ、ｄがリンクされる。
【００７０】
［リンク最適化処理］
次に、リンク最適化部５５が、リンク最適化処理を行う（ステップＳ６）。本実施形態においてリンク最適化処理は、登録データから仮リンクを生成した類似データをリンク削減対象として行われる。即ち、リンク削減対象のデータについてのリンク数をグラフインデックスＤＢ７０に基づいて取得し、そのリンク数がリンク削減閾値以上であった場合には、そのデータのリンクの削減を行う。
【００７１】
このとき、リンク削減対象のデータにリンク（仮リンクを含む）された類似データのうち、距離の遠い順に削減する。例えば、リンク削減閾値が‘４’である場合、図６（ａ）においては、リンクが生成された点ｃ、ｂ、ｄに設定されたリンク数が４となり、リンク削減閾値以上となる。従って、点ｃについては、リンクの中で最も距離の遠い点ｂとの間に設定されたリンクが削減される。また、点ｄについては、点ｅとの間に設定されたリンクが削減され、図６（ｂ）のようなグラフ構造となる。ここで、リンク削減対象の点ｂについては、点ｃのリンクが削減された時点で、リンク数がリンク削減閾値未満となるため、リンクの削減は行わなくともよい。
【００７２】
リンク最適化部５５がリンク削減処理の結果に基づいて、グラフインデックスＤＢ７０のリンク情報を更新すると共に、画像ＤＢ６０に登録データが記憶される（ステップＳ７）。そして、登録データ入力部１０から更に登録データが入力される場合には（ステップＳ８；Ｙｅｓ）、ステップＳ２に処理を移行して、グラフ検索処理、リンクの生成、リンクの最適化を行う。また、新たなデータがない場合には（ステップＳ８；Ｎｏ）、グラフ自己生成処理を終了する。
【００７３】
また、詳細な説明は省略するが、検索データに対して類似するデータを検索して検索結果をクライアント端末に返す検索処理のみの場合は、検索データ入力部２０から入力される検索データに対して、上述したグラフ検索部４０によるグラフ検索処理を行う。そして、類似データ特定部４７により得られた類似データを距離に基づいてランキングした検索結果を表示データとして検索結果出力部３０が生成して、クライアント端末に返送する。
【００７４】
以上、第１実施形態によれば、グラフインデックスのデータ間のリンクを巡回して類似データを検索するという検索アルゴリズムを用いて、登録データに対する類似データを検索し、その類似データと登録データとの間に新たにリンクを生成することで、検索装置１がリンクを辿って検索しているグラフインデックスにデータ登録して、登録後に巡回するデータとしてリンクを形成していく。このように、検索装置１は、検索の際に巡回していくグラフインデックス上にデータの登録を行って、グラフインデックスを自己生成する。
【００７５】
また、データの登録を行う都度、新たにリンクが形成されたデータのリンク数の最適化を行うことで、検索装置１は、データの登録の際に、グラフインデックスのリンク構造の最適化を行って、自己修復していく。
【００７６】
従って、グラフインデックスを用いた検索アルゴリズムにより、データベースの全てのデータとの距離を算出することなく、類似データを検索できるため、多次元のベクトルデータを記憶したデータベースに高速にデータ登録していくことができる。また、グラフインデックスのリンク数を最適に保っていくため、データの増加によってリンク構造が煩雑になって検索速度が低下してしまうことを防止できる。
【００７７】
〔第２実施形態〕
次に、検索装置１の第２実施形態について説明する。尚、上述した第１実施形態と同一の機能構成、同一の処理ステップには、説明を省略する。第２実施形態における検索装置１は、図２におけるリンク最適化処理を図７に示すフローチャートによるリンク最適化処理に置き換えることにより実現される。以下、図８のリンク最適化処理の様子を示す図を参照しつつ、リンク最適化処理について説明する。尚、図８のリンク構造の図示において、説明の簡略化のため、図８（ｂ）以降のデータ間のリンクの図示を破線により適宜省略している。
【００７８】
上述したように、グラフインデックスを用いた検索アルゴリズムでは、ベクトルデータ間のリンクを巡回していくことにより、類似データを探索するが、リンク切れが生じてしまうと、ベクトルデータの孤立により巡回できなくなってしまう。第２実施形態の検索装置１は、そのリンク削減を行う際に、そのリンクの修復を行うものである。
【００７９】
先ず、リンク最適化部５５は、削減対象のリンクが設定された点について、その点にリンクされた全て点の中から該リンクを保持する点（リンク保持点）を特定する（ステップＳ６１）。このリンク保持点の特定は、例えば、削減対象の点との距離が近いものから所定数の点としてもよいし、所定距離内にある点としてもよい。図８（ａ）においては、削減対象の点ａに対して、距離の近い６つの点ｂ、ｃ、ｄ、ｅ、ｆをリンク保持点として特定している。また、削減対象の点をリンク保持点に含めても良い。
【００８０】
図８（ａ）においては、削減対象の点ａに対して、距離の近い５つの点ｂ、ｃ、ｄ、ｅ、ｆをリンク保持点として特定している。そして、削減対象点にリンクされた点のうち、リンク保持点以外の点をリンクの修復対象として、その修復対象点の中から一つずつ選択していく（ステップＳ６２）。図８（ａ）では、点ｇを修復対象点として選択している。
【００８１】
次に、リンク最適化部５５は、修復対象点と各リンク保持点との距離を算出し（ステップＳ６３）、その算出した距離の中から最短距離を有するリンク保持点と、修復対象点との間に新たなリンクを設定する（ステップＳ６４）。
【００８２】
例えば、図８（ｂ）のように、修復対象点ｇと、リンク保持点ｂ〜ｆのそれぞれとの距離を算出し、図８（ｃ）のように、最短の距離となったリンク保持点ｅと修復対象点ｇとの間に新たなリンクを設定する。尚、修復対象点と、リンク保持点との間に既にリンクが設定されている場合には、リンクの設定を行わなくとも良い。
【００８３】
リンク最適化部５５は、リンクの設定を行った修復対象点と、削減対象点との間に設定されているリンクを解除する（ステップＳ６５）。図８（ｄ）において、点ａと点ｇとの間のリンクが解除される。
【００８４】
次に、リンク保持点以外の削減対象点にリンクされた点、即ち、修復対象点の中でステップＳ６２〜Ｓ６５の修復処理を全ての点に対して行った場合には（ステップＳ６６；Ｎｏ）、リンク最適化処理を終了し、修復しいない点がある場合には（ステップＳ６６；Ｙｅｓ）、ステップＳ６２に処理を移行する。
【００８５】
図８（ａ）においてリンク保持点として特定された点ｂ〜ｆ以外の点について削減対象点に対するリンクが解除されても、図８（ｅ）のようにそれぞれリンク保持点に対してリンクが設定されるため、リンク切れが生ずることを防止できる。
【００８６】
以上のように、第２実施形態によれば、リンクの削減対象点と修復対象点とのリンクが解除されても、修復対象点からリンク保持点に対してのリンクが確保されるため、リンク切れが発生することを防止できる。従って、グラフインデックスのリンク削除を行う場合にも、検索性能の低下を防止できる。
【００８７】
〔第３実施形態〕
次ぎに、検索装置１の第３実施形態について説明する。上述した実施形態において、検索装置１は、グラフインデックス上で任意選択した点からリンクを辿ることで検索開始点を特定することとしたが、第３実施形態においては、ベクトルデータをベクトル空間上でクラスタリングしてインデックス化しておくことにより、検索開始点を特定する。このインデックスは、公知のベクトル空間の空間分割の技術により生成され、簡単に説明すると以下のように実現される。
【００８８】
先ず、グラフインデックスＤＢ７０中の任意のベクトルデータ（点Ａ）を選択し、その点Ａから最遠の点Ｂを選択する。最遠の点を選ぶためには、点Ａから各点までの距離をそれぞれ計算すればよい。次に、点ＢからグラフインデックスＤＢ７０の全ての点までの距離を求め、距離の順序でソートする。ソートされた順において隣接する距離どうしの間の差分を算出する。例えば、ソートされた距離が、順に、ｄ１，ｄ２，ｄ３，…，ｄｎのように並んでいるとする。この場合、｜ｄ１−ｄ２｜，｜ｄ２−ｄ３｜のように順次算出する。
【００８９】
そして、差分が最大である距離の間で、クラスタの分割を行う。例えば、ｄ１とｄ２との距離が最大であるとすると、距離ｄ１に対応する点Ｐ１と、距離ｄ２に対応する点Ｐ２の間で分割を行う。これにより、類似するデータを木構造のクラスタに分けることができる。
【００９０】
木構造のクラスタによるインデックスは、例えば、クラスタの中心点と、クラスタの半径、親子関係を有する子クラスタのＩＤとを対応付けることによりデータベース化される。尚、このクラスタのインデックスの構成は適宜公知技術を適用可能である。
【００９１】
木構造インデックスからの検索開始点の探索は、先ず、クラスタの中心と半径とに基づいて登録データが属するクラスタを木構造の上層から特定し、下層のクラスタのうち、登録データが属するクラスタを特定する。このようにして、順次、登録データが属する下層のクラスタを特定していき、最下層のクラスタに属するデータを検索開始点として決定する。最下層のクラスタに複数のデータが属している場合、それぞれを検索開始点とすることができる。即ち、登録データに近付く方向に木構造インデックスを辿ることにより、登録データに比較的に近いデータを検索開始点として取得することができる。
【００９２】
空間分割によりベクトルデータ群をクラスタに分割した様子を図９に示す。このように、分割したクラスタ毎にベクトルデータを対応付けたインデックスを生成しておくことで、同一階層にあるベクトルデータを高速に検索することができる。
【００９３】
ここで、例えば、図９に示すように、登録データが入力されたとし、木構造インデックスを探索することで同階層のベクトルデータを探索するが、そのベクトルデータが登録データを中心とした検索範囲外である場合がある。この場合、同階層のベクトルデータを検索開始点と設定すると、検索効率が悪くなってしまう。
【００９４】
そのため、先ず、同一階層のベクトルデータをクラスタリングによるインデックスを用いて探索し、そのベクトルデータが検索範囲内であるか否かを判定する。そして、検索範囲内であれば、そのベクトルデータを検索開始点として特定する。
【００９５】
また、検索範囲外であるならば、上述した検索開始点決定処理（図３参照）に従って、その同一階層のベクトルデータを任意点として選択して開始して検索開始点を決定する。これにより、検索開始点を高速に決定できると共に、検索結果の精度を保つことができる。
【００９６】
次ぎに、上述した実施形態における変形例を説明する。
［変形例１］
登録データのベクトルデータと同一のベクトルデータが既にグラフインデックスＤＢ７０に記憶されている場合には、グラフインデックスＤＢ７０には記憶せずに、画像ＤＢ６０にのみ記憶し、既に記憶されている同一のベクトルデータに関連付けることができる。この場合、グラフインデックスＤＢ７０には、画像ＩＤの他に、同一ベクトルデータを有する画像データの画像ＩＤを関連ＩＤとして記憶するデータ項目を新たに設ける。
【００９７】
データ検索の際に、類似データとして検索したデータに関連ＩＤが対応付けられている場合には、その関連ＩＤで示される画像データも検索結果として出力することができる。このため、同一のベクトルデータの登録によりグラフインデックスの構造が煩雑化して検索速度が低下してしまうことを防止できる。
【００９８】
［変形例２］
グラフ検索処理の検索範囲を、登録データを中心とした規定の距離により定めたが、検索開始点から巡回する検索数により定めることとしてもよい。即ち、上述した方法により検索開始点を決定し、その検索開始点からリンクを辿る。このとき、リンクの巡回により所定の検索数（例えば、１０個）のデータを収集する。そして、収集した各データと登録データの距離の順に各データをソートして、巡回したデータのリストを得る。このリストにおいて検索数分のベクトルデータを保持し、登録データに対して最遠のベクトルデータに対応する距離を、検索範囲として更新していく。
【００９９】
即ち、検索終了条件を満たさない限りリンクを辿り、上記のリスト内のデータよりも登録データに近いデータが見つかった場合には、その距離順に上記リストに追加する。そして、このデータ追加によりリスト内において更新された最遠のデータに応じて検索範囲が更新される。これにより、検索数分のデータの収集に応じて登録データとの距離が近いデータでリストが更新されていくことで、検索範囲を狭めていくことができる。このため、検索数の指定に応じて、検索範囲を動的に定めることができる。また、近いデータが検索されるたびに、検索範囲を狭めることができるので、検索精度を維持しつつ、検索速度を向上させることができる。
【０１００】
［変形例３］
上述の変形例２の手法を用いて、検索開始点の決定のためのリンク巡回する範囲を定めることとしてもよい。即ち、グラフインデックスから任意の点を選択して最近傍の点を特定する処理を、検索数を１個としたグラフ検索処理と見なして、リンク巡回することで検索される登録データにより近いデータを１つ収集して保持・更新することで、そのデータと登録データとの距離を検索範囲の半径として動的に定めていく。
【０１０１】
リンクを巡回する際には、動的に定めた検索範囲を超えないようにデータを選択していく。このため、検索開始点を特定するためにリンクを辿りながら、検索範囲を狭めていくことができ、検索開始点特定までの時間を短くできる。
【０１０２】
また、検索範囲をα倍（α＞１）した範囲（検索限界範囲）を越えない範囲でリンクを巡回することにより、登録データに近いデータがリンクされていない場合があっても、巡回する範囲が広がるため、最適な検索開始点の特定することができるようになる。
【０１０３】
［変形例４］
検索開始点を決定する際に巡回したデータが最終的な検索結果となり得る可能性があるため、図３のステップＳ４３４において算出した距離を巡回履歴としてメモリに保持しておき、グラフ検索においてその巡回履歴を参照することで、距離の算出処理を省略することができる。
【０１０４】
尚、上述した各実施形態の動作は、コンピュータに適宜のコンピュータソフトウエアを組み込むことにより実施することができる。例えば、前記した各構成要素は、機能ブロックとして存在していればよく、独立したハードウエアとして存在しなくても良い。また、実装方法としては、ハードウエアを用いてもコンピュータソフトウエアを用いても良い。さらに、本発明における一つの機能要素が複数の機能要素の集合によって実現されても良く、本発明における複数の機能要素が一つの機能要素により実現されても良い。
【０１０５】
また、機能要素は、物理的に離間した位置に配置されていてもよい。この場合、機能要素どうしがネットワークにより接続されていても良い。グリッドコンピューティングにより機能を実現し、あるいは機能要素を構成することも可能である。
【図面の簡単な説明】
【０１０６】
【図１】第１実施形態における検索装置の機能構成の一例を示すブロック図。
【図２】第１実施形態におけるグラフ自己生成処理の処理内容を説明するためのフローチャート。
【図３】第１実施形態における検索開始点決定の処理フローを説明するためのフローチャート。
【図４】第１実施形態における検索開始点の決定の処理の具体例を示す模式図。
【図５】第１実施形態における類似データを検索の処理の具体例を示す模式図。
【図６】第１実施形態におけるリンク最適化処理の処理内容の具体例を示す模式図。
【図７】第２実施形態におけるリンク最適化処理の処理フローを説明するためのフローチャート。
【図８】第２実施形態におけるリンク最適化処理の処理内容の具体例を示す模式図。
【図９】第３実施形態における木構造インデックスの一例を示す図。
【符号の説明】
【０１０７】
１    検索装置
１０  登録データ入力部
２０  検索データ入力部
３０  検索結果出力部
４０  グラフ検索部
４１  ベクトルデータ生成部
４３  検索開始点決定部
４５  グラフ巡回部
４７  類似データ特定部
５０  データ登録部
５１  類似データ取得部
５３  リンク登録部
５５  リンク最適化部
６０  画像ＤＢ
７０  グラフインデックスＤＢ
【図１】
2011090351.tif 000003
【図２】
2011090351.tif 000004
【図３】
2011090351.tif 000005
【図４】
2011090351.tif 000006
【図５】
2011090351.tif 000007
【図６】
2011090351.tif 000008
【図７】
2011090351.tif 000009
【図８】
2011090351.tif 000010
【図９】
2011090351.tif 000011