(57)【要約】【課題】新規な多次元ベクトルデータに類似するデータをデータベースから高速に検索できる装置あるいは手法を提供する。【解決手段】データベース１４は、複数の既存ベクトルデータを備える。複数の既存ベクトルデータの間には、一つの既存ベクトルデータから他の既存ベクトルデータを辿るためのリンクが張られている。検索部１３は、いずれかの既存ベクトルデータを、検索開始点として取得する。さらに、検索部１３は、既定の終了条件を満足するまで、検索開始点から、リンクを順次辿る。さらに、検索部１３は、リンクを辿る経路上にある既存ベクトルデータのうち、新規ベクトルデータに対して既定の距離にある既存ベクトルデータを類似データとして取得する。【選択図】図１
2010079871.tif 000002
【特許請求の範囲】
【請求項１】
データベースと、検索部とを備えており、
前記データベースは、複数の既存ベクトルデータを備えており、
前記複数の既存ベクトルデータの間には、一つの既存ベクトルデータから他の既存ベクトルデータを辿るためのリンクが張られており、
前記検索部は、
前記複数の既存ベクトルデータのうちのいずれかを検索開始点として取得する処理と、
既定の終了条件を満足するまで、前記検索開始点から、前記リンクを順次辿る処理と、
前記リンクを辿る経路上にある前記既存ベクトルデータのうち、新規ベクトルデータに対して既定の距離にある前記既存ベクトルデータを類似データとして取得する処理と
を行う構成となっている
ことを特徴とする、ベクトルデータ検索装置。
【請求項２】
前記検索開始点から前記リンクを辿る処理は、前記検索開始点を始点とする全ての経路における前記リンクを辿った結果がいずれも前記既定の終了条件を満足するまで実行される構成となっている
請求項１に記載のベクトルデータ検索装置。
【請求項３】
インデックス生成部をさらに備えており、
前記インデックス生成部は、
前記複数の既存ベクトルデータによって構成される多次元データ空間を階層的に分割することにより、個々の前記既存ベクトルデータに対応するリーフノードを備えた木構造インデックスを構築する構成となっており、
前記検索開始点となる前記既存ベクトルデータを取得する処理は、前記新規ベクトルデータに近い前記既存ベクトルデータに到達するように、前記木構造インデックスを前記リーフノードに向けて辿ることにより行われる
請求項１又は２に記載のベクトルデータ検索装置。
【請求項４】
前記検索開始点を取得する処理は、
前記木構造インデックスを辿ることで得られた前記リーフノードに対応する複数の前記既存ベクトルデータを、それぞれ前記検索開始点とする構成となっている
請求項３に記載のベクトルデータ検索装置。
【請求項５】
前記インデックス生成部は、前記新規ベクトルデータと、検索の結果として取得された類似データとの間に、リンクを生成する構成となっている
請求項３又は４に記載のベクトルデータ検索装置。
【請求項６】
前記インデックス生成部は、前記多次元データ空間を階層的に分割したことで生じるクラスタに属する前記既存ベクトルデータのうち、各クラスタの間で最も近接するものどうしにリンクを生成する構成となっている
請求項３〜５のいずれか１項に記載のベクトルデータ検索装置。
【請求項７】
前記既定の終了条件とは、前記検索開始点を始点とするリンクを辿った結果が、前記新規ベクトルデータに対する検索範囲をα倍（α＞１）した範囲を越えることである
請求項１〜６のいずれか１項に記載のベクトルデータ検索装置。
【請求項８】
前記既定の終了条件とは、前記検索開始点を始点とするリンクを辿った結果が、前記新規ベクトルデータに対する検索範囲の外側において、前記リンクを、既定の回数だけ辿ったことである
請求項１〜７のいずれか１項に記載のベクトルデータ検索装置。
【請求項９】
前記検索部は、
前記αの値を、検索した前記既存ベクトルデータの数の増加に対応して減少させる構成となっている
請求項７に記載のベクトルデータ検索装置。
【請求項１０】
前記既定の距離は、既定の検索数の前記既存ベクトルデータのうち、前記新規ベクトルデータに対して最遠の前記既存ベクトルデータまでの距離であり、
前記検索部は、前記リンクを辿ることで得られる検索結果としての前記既存ベクトルデータに応じて、前記規定の距離を更新する構成となっている
請求項１〜９のいずれか１項に記載のベクトルデータ検索装置。
【請求項１１】
前記既定の終了条件は、以下の処理により決定される、請求項１０に記載のベクトルデータ検索装置：
（Ａ）前記既定の検索数をβ倍（ただしβ＞１）した限界検索数に至るまで、前記既存ベクトルデータを、前記リンクを辿ることによって取得する処理；
（Ｂ）前記限界検索数に含まれる前記既存ベクトルデータと前記新規ベクトルデータとの距離のうちで、最大のものを求める処理；
（Ｃ）前記リンクを辿った結果が、前記ステップ（Ｂ）で求めた前記最大の距離を越えるか、又は、越えた後に既定の回数だけリンクを辿ることにより、前記既定の終了条件を満たすとする処理。
【請求項１２】
前記検索部は、
前記βの値を、検索した前記既存ベクトルデータの数の増加に対応して減少させる構成となっている
請求項１１に記載のベクトルデータ検索装置。
【請求項１３】
前記最遠の前記既存ベクトルデータよりも前記新規ベクトルデータに近い既存ベクトルデータが検索された場合には、この近い既存ベクトルデータを含み、かつ、前記新規ベクトルデータに対して近い順に既定の検索数までの既存ベクトルデータの中から、最遠の既存ベクトルデータを選択することにより、前記新規ベクトルデータと既存ベクトルデータとの最大の距離を更新する構成とされている
請求項１０〜１３のいずれか１項に記載のベクトルデータ検索装置。
【請求項１４】
さらにインデックス再構成部を備えており、
前記インデックス再構成部は、以下の処理により、前記既存ベクトルデータの間に張られたリンクを再設定する構成となっている、請求項１〜１３のいずれか１項に記載のベクトルデータ検索装置：
（Ａ）既にリンクが張られた任意の前記既存ベクトルデータを、対象ベクトルとして取得する処理；
（Ｂ）前記対象ベクトルの近傍のベクトルを、前記既存ベクトルデータから取得する処理；
（Ｃ）前記近傍のベクトルに対して、前記対象ベクトルからリンクを張る処理；
（Ｄ）前記近傍のベクトルのいずれかを、新たな対象ベクトルとして取得する処理；
（Ｅ）前記（Ｂ）〜（Ｄ）の処理を繰り返すことにより、前記既存ベクトルデータの間に張られたリンクを再設定する処理。
【請求項１５】
さらにインデックス再構成部を備えており、
前記インデックス再構成部は、いずれかの前記既存ベクトルデータが削除される場合に、以下の処理により、前記既存ベクトルデータの間に張られたリンクを再設定する構成となっている、請求項１〜１４のいずれか１項に記載のベクトルデータ検索装置：
（Ａ）削除対象の前記既存ベクトルデータからリンクしている前記既存ベクトルデータの集合Ｓを特定する処理；
（Ｂ）前記集合Ｓに含まれる任意の既存ベクトルデータｓ１を特定する処理；
（Ｃ）前記既存ベクトルデータｓ１に最も近い既存ベクトルデータｓ２を前記集合Ｓから取得する処理；
（Ｄ）前記既存ベクトルデータｓ１とｓ２とをリンクさせる処理；
（Ｅ）前記集合Ｓに他の既存ベクトルデータが含まれている場合には、前記のようにリンクされた既存ベクトルデータｓ１及びｓ２を集合Ｓから除外した上で、前記（Ｂ）〜（Ｄ）の処理を繰り返すことにより、前記削除対象の既存ベクトルデータの近傍の既存ベクトルデータの間におけるリンクを再設定する処理。
【請求項１６】
請求項１〜１５のいずれか１項に記載のベクトルデータ検索装置と、表示装置とを備えており、
前記ベクトルデータ検索装置は、取得した類似データ又はこれに関連する情報を、前記表示装置に送信する構成となっており、
前記表示装置は、前記類似データ又はこれに関連する情報を、使用者に提示する
構成となっているベクトルデータ検索システム。
【請求項１７】
以下のステップを備える、ベクトルデータ検索方法：
複数の既存ベクトルデータの間に、一つの既存ベクトルデータから他の既存ベクトルデータを辿るためのリンクを張るステップ；
前記複数の既存ベクトルデータのうちのいずれかを、検索開始点として取得するステップ； 
既定の終了条件を満足するまで、前記検索開始点から、前記リンクを順次辿るステップ；
前記リンクを辿る経路上にある前記既存ベクトルデータのうち、前記新規ベクトルデータに対して既定の距離にある前記既存ベクトルデータを類似データとして取得するステップ。
【請求項１８】
請求項１〜１５のいずれか１項に記載の検索装置と、ラベル生成部とを備えており、
前記検索装置における前記データベースは、前記既存ベクトルデータとラベルとを対応して記憶する構成となっており、
前記ラベル生成部は、前記検索装置における前記検索部によって取得された前記類似データに対応する前記ラベルに基づいて、前記新規ベクトルデータに付与すべきラベルを生成する構成となっている
ことを特徴とするラベル付与装置。
【請求項１９】
前記ラベル生成部は、前記新規ベクトルデータに対して最近傍にあるか、又は、既定の距離にある前記類似データを特定し、この前記類似データに対応する前記ラベルに基づいて、前記新規ベクトルデータに付与すべきラベルを生成する
請求項１８に記載のラベル付与装置。
【請求項２０】
前記データベースにおいては、一つの前記既存ベクトルデータについて、複数のラベルが対応して記憶されている
請求項１８又は１９に記載のラベル付与装置。
【請求項２１】
前記ラベル生成部は、前記類似データに対応するラベルを複数取得した場合には、ラベルの出現数に基づいてラベルの順位づけを行い、既定の順位までのラベルを前記新規ベクトルデータに付与する構成となっている
請求項１８〜２０のいずれか１項に記載のラベル付与装置。
【請求項２２】
前記ラベル生成部は、前記類似データに対応するラベルを複数取得した場合には、ラベルの確信度に基づいてラベルの順位づけを行い、既定の順位までのラベルを前記新規ベクトルデータに付与する構成となっており、
前記ラベルの確信度は、
前記ラベルに対応する既存ベクトルデータと新規ベクトルデータとの間の距離と、
取得された前記ラベルの個数と
に基づいて決定されるものである
請求項１８〜２０のいずれか１項に記載のラベル付与装置。
【請求項２３】
前記ラベル生成部は、
前記類似データに対応するラベルのクラスタを生成する処理と、
前記新規ベクトルデータが前記クラスタに含まれる場合に、前記クラスタに対応するラベルを前記新規ベクトルデータに付与する処理と
を行う構成となっている請求項１８〜２０のいずれか１項に記載のラベル付与装置。
【請求項２４】
請求項１〜１５のいずれか１項に記載の検索装置を用いたラベル付与方法であって：
前記既存ベクトルデータとラベルとを対応して記憶するステップと；
前記検索装置における前記検索部によって取得された前記類似データに対応する前記ラベルに基づいて、前記新規ベクトルデータに付与すべきラベルを生成するステップと
を備えることを特徴とするラベル付与方法。
【請求項２５】
請求項１８〜２３のいずれか１項に記載のラベル付与装置により付与されたラベルをキーとして用いる画像検索方法であって、
入力されたクエリに基づいて前記ラベルを検索するステップと；
前記ラベルに対応するベクトルデータを特定するステップと；
前記ベクトルデータに対応する画像を検索結果として出力するステップと
を備えることを特徴とする画像検索方法。
【請求項２６】
請求項１７、２４又は２５に記載のステップをコンピュータに実行させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトルデータを検索するための装置に関するものである。より詳しくは、本発明は、新規なベクトルデータに類似する既存のベクトルデータを検索するための装置に関するものである。
【背景技術】
【０００２】
例えば、ある画像（検索画像）に類似する画像を、多数の画像（対象画像）の中から検索する場合がある。この場合、各画像の特徴を、多次元のベクトルデータ（すなわち特徴量）で表し、各ベクトルデータの距離などを用いて、類似画像を抽出する方法が考えられる。
【０００３】
類似画像の検索作業において、対象画像の数が多い場合には、検索画像と対象画像との距離を逐一計算していると、検索に要する時間が非常に長くなってしまう。
【０００４】
そこで、木構造のインデックス（索引）を用いて、検索を高速化する方法も提案されている。
【０００５】
一般に、多次元のベクトル空間において、ある範囲の多次元データを高速に検索するには、多次元空間インデックスであるkd-tree若しくは R-treeや、又は、距離空間インデックスである Vp-treeなどが知られている。これらの手法は、空間を分割して木構造のインデックスを生成し、生成された木構造を辿ることで高速な検索を目指している。
【０００６】
しかしながら、次元数が多くなると、木構造において辿るべき枝を絞りきれず、結果的に多くのデータどうしを照合する必要が生じる。つまり、次元の数が多くなるほど、木構造インデックスの効果は低くなってしまう。画像や音声などのマルチメディアデータでは、一般に、特徴を正確に表すために、次元数が多くなる傾向がある。このため、木構造インデックスでは、検索の高速化が不十分になりがちであるという問題がある。
【０００７】
一方、下記特許文献１（例えば図４や図８参照）には、次のような技術が記載されている。
・予め、データベース内のすべての特徴量にそれぞれＩＤを付す。さらに、各ＩＤについて、データベース内における他の全てのＩＤとの間で、特徴量の類似度を予め計算する。
・特徴量の類似度が高いＩＤの情報を、各ＩＤに対応させて格納しておく。
・検索キーとして、データベース内におけるいずれかの既存ＩＤについての特徴量を用いる。
・検索キーである特徴量に対する類似度が高いＩＤを検索結果として返す。
【０００８】
この特許文献１の技術では、各ＩＤに対して高い類似度を持つＩＤ群を、当該ＩＤに関連付けて格納している。このため、関連付けて格納されるＩＤ群の数に応じて、検索結果として出力できる結果の上限が定まってしまう。
【０００９】
また、ある検索キー（データベース中の既存ＩＤ）に対して、他の全てのＩＤを検索対象としたい場合には、各ＩＤに対して、残りの全ＩＤを類似度順に記憶しておかなければならない。このため、特許文献１の技術では、事前計算により登録しておくデータベースのデータ量が膨大になってしまうという不都合もある。
【特許文献１】特開２００１−５２０２４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ところで、特許文献１の技術では、検索キーとなる特徴量も、既にデータベースに登録され、所定の類似度計算が行われていることが前提となっている。
【００１１】
しかしながら、ユーザが指定した新規な画像（未知画像と言うこともできる）に類似する画像をデータベース中から検索する場合も考え得る。この場合に、新規画像の特徴量を逐一事前計算してデータベースに格納してから検索するのでは、時間がかかりすぎ、例えばリアルタイムでの検索用途には不向きである。なお、前記では、理解の容易のため、多次元ベクトルデータの例として画像の特徴量を用いて説明したが、他の種類の多次元ベクトルデータ（例えば音声の特徴量など）であっても、同様の状況が妥当する。
【００１２】
本発明は、前記の状況に鑑みてなされたものである。本発明の目的の一つは、新規な多次元ベクトルデータに類似するデータをデータベースから高速に検索できる装置あるいは手法を提供することである。
本発明の他の目的は、検索結果として得られた類似データに付与されたラベルに基づいて、新規ベクトルデータに付与すべきラベルを決定できる装置あるいは手法を提供することである。
【課題を解決するための手段】
【００１３】
本発明は、以下のいずれかの項目に記載の構成とされている。
【００１４】
（項目１）
データベースと、検索部とを備えており、
前記データベースは、複数の既存ベクトルデータを備えており、
前記複数の既存ベクトルデータの間には、一つの既存ベクトルデータから他の既存ベクトルデータを辿るためのリンクが張られており、
前記検索部は、
前記複数の既存ベクトルデータのうちのいずれかを、検索開始点として取得する処理と、
既定の終了条件を満足するまで、前記検索開始点から、前記リンクを順次辿る処理と、
前記リンクを辿る経路上にある前記既存ベクトルデータのうち、前記新規ベクトルデータに対して既定の距離にある前記既存ベクトルデータを類似データとして取得する処理と
を行う構成となっている
ことを特徴とする、ベクトルデータ検索装置。
【００１５】
新規ベクトルデータとは、検索の基本となるデータである。新規ベクトルデータの一例は、ユーザが指定した画像の特徴を表すベクトルデータである。ただし、本発明において用いるベクトルデータには特に制約はない。本発明におけるリンクとは、あるベクトルデータから他のベクトルデータへ辿るための情報である。
【００１６】
この発明においては、新規ベクトルデータが何らかの方法で提示されると、検索開始点を取得し、そこからリンクを辿る。これにより、既存ベクトルデータの中から、新規ベクトルデータに類似するデータを効率よく検索することができる。
【００１７】
ここで、本発明では、新規ベクトルデータと既存ベクトルデータとの類似度を予め算出しておく必要がない。また、新規ベクトルデータを予めデータベースに格納しておく必要もない。
【００１８】
また、検索開始点である既存ベクトルデータを、新規ベクトルデータに近接させることにより、効率の良い検索が可能になる。どの程度近接させるかは、設計事項であるが、例えば、
・新規ベクトルデータに対する検索範囲内とする、
・検索範囲のα倍（α＞１）の範囲とする、
という手段が考えられる。他の範囲を設定することも可能である。また、必ずしも特定の範囲にある必要はなく、例えば、木構造インデックスを辿ることによって得られたリーフノードに対応する既存ベクトルデータであることもできる。
【００１９】
また、この発明においては、新規ベクトルデータに対する「既定の距離」は、類似データであるか否かを判別するための基準になるものである。この「既定の距離」は、使用者によって指定されてもよいし、何らかの方法で動的に生成することもできる。動的に生成する方法としては、たとえば、検索結果となるデータ数を指定する（例えば画像の数を５０件までと指定する）場合に、そのデータ数から、所定の関数ないし算出式により、既定の距離を生成することができる。
【００２０】
（項目２）
前記検索開始点から前記リンクを辿る処理は、前記検索開始点を始点とする全ての経路における前記リンクを辿った結果が前記既定の終了条件を満足するまで実行される構成となっている
項目１に記載のベクトルデータ検索装置。
【００２１】
リンクを辿るということは、あるベクトルデータ（いわゆるノード又は点）から、そこに張られたリンクに基づいて、他のベクトルデータ（すなわち他のノード又は点）の情報を取得するということである。この項目の発明では、終了条件を満たすまでは、リンクの経路を次々に辿っていく。また、途中でリンクが分岐しているときは、各分岐を、逐次的あるいは並列的に辿っていく。リンクを辿る経路にある既存ベクトルデータの情報を記憶することにより、これらの既存ベクトルデータを、類似データの候補とすることができる。この候補となった既存ベクトルデータのうち、新規ベクトルデータに対して既定の距離にあるものを、検索結果としての類似データとして取得することができる。
【００２２】
（項目２−１）
前記リンクは、いずれか一つの前記既存ベクトルデータからリンクを辿ることによって、全ての前記既存ベクトルデータを辿ることができるように張られている
項目１又は２に記載のベクトルデータ検索装置。
【００２３】
任意の既存ベクトルデータを起点として、他の全てのベクトルデータを辿ることができるようにリンクを張ることが好ましい。もちろん、一筆書きのようにリンクを辿る必要はなく、例えば、分岐点まで戻って別の方向にリンクを辿ることも可能である。
【００２４】
（項目２−２）
少なくとも一つの前記既存ベクトルデータは、複数の前記既存ベクトルデータとの間において、前記リンクを直接に張られた構成となっている
項目１〜２に記載のベクトルデータ検索装置。
【００２５】
一筆書きのようにリンクを張ると、リンクを辿っても、新規ベクトルデータに類似するデータを効率よく収集することが難しい。一つの既存ベクトルデータと複数の既存ベクトルデータとの間でリンクを直接に張ることにより、複数の経路でリンクを辿ることができるので、検索の効率を向上させることが可能になる。
【００２６】
（項目２−３）
前記リンクは、類似度が最も高い又は類似度が既定値以上の前記既存ベクトルデータどうしの間に張られている
項目１〜２に記載のベクトルデータ検索装置。
【００２７】
リンクは、類似度が高い既存ベクトルデータどうしの間に張ることが好ましい。どの程度の類似を持つデータどうしにリンクを張るかは適宜に設定することができる。例えば、既定値以上の類似度を持つデータどうしをリンクさせることができる。あるいは、最も類似度が高いデータどうしにリンクを張ることができる。検索開始点である既存ベクトルデータに近いデータは、新規ベクトルデータに対する検索範囲内にある可能性が高い。したがって、類似度が高いデータの間にリンクを張ることにより、検索を効率的に行うことが可能になる。
【００２８】
（項目３）
インデックス生成部をさらに備えており、
前記インデックス生成部は、
前記複数の既存ベクトルデータによって構成される多次元データ空間を階層的に分割することにより、個々の前記既存ベクトルデータに対応するリーフノードを備えた木構造インデックスを構築する構成となっており、
前記検索開始点となる前記既存ベクトルデータを取得する処理は、前記新規ベクトルデータに近い前記既存ベクトルデータに到達するように、前記木構造インデックスを前記リーフノードに向けて辿ることにより行われる
項目１〜２に記載のベクトルデータ検索装置。
【００２９】
木構造インデックスを辿ることにより、検索開始点である既存ベクトルデータを高速に取得することができる。また、木構造インデックスの生成自体も高速に行うことができる。しかも、木構造インデックス自体のデータ量は、一般的には小さく抑えることができる。
【００３０】
木構造インデックスを辿った結果のリーフノードに対応する（つまりリーフノードのレベルのクラスタに含まれる）既存ベクトルデータと新規ベクトルデータとの距離自体は、一般的には保証されない。しかしながら、新規ベクトルデータに近い方向へと木構造インデックスを辿ることにより、少なくとも、他の多くの既存ベクトルデータよりも新規ベクトルデータに近い既存ベクトルデータを検索開始点として特定することができる。
【００３１】
（項目４）
前記検索開始点を取得する処理は、
前記木構造インデックスを辿ることで得られた前記リーフノードに対応する複数の前記既存ベクトルデータを、それぞれ前記検索開始点とする構成となっている
項目３に記載のベクトルデータ検索装置。
【００３２】
木構造インデックスを辿ることで得られるリーフノードに対応するデータ（点）は複数存在することができる。この場合、これら複数のリーフノードに対応する複数の既存ベクトルデータを、それぞれ検索開始点とすることができる。
【００３３】
（項目５）
前記インデックス生成部は、前記新規ベクトルデータと、検索の結果として取得された類似データとの間に、リンクを生成する構成となっている
項目３又は４に記載のベクトルデータ検索装置。
【００３４】
木構造インデックスを用いて検索開始点を取得する構成において、データ間のリンクを、類似度の高いデータ間において生成することもできる。例えば、類似データの検索結果として得られたデータと、新たに格納した新規データとの間にリンクを生成していく手法も可能である。
【００３５】
（項目６）
前記インデックス生成部は、前記多次元データ空間を階層的に分割したことで生じるクラスタに属する前記既存ベクトルデータのうち、各クラスタの間で最も近接するものどうしにリンクを生成する構成となっている
項目３〜５のいずれか１項に記載のベクトルデータ検索装置。
【００３６】
一般に、木構造インデックスの生成においては、データ空間を階層的に分割することで、クラスタを生成していく。生成されたクラスタをさらに分割することで、リーフノードの数（すなわち最下位レベルのクラスタに属するデータの数）を減少させていく。木構造インデックスの生成において、生成されたクラスタ間のデータどうしをリンクさせることにより、木構造インデックスの生成とリンクの生成とを並行して行うことができる。
【００３７】
（項目６−１）
前記インデックス生成部は、全ての前記リーフノードに対応するクラスタに属する前記既存ベクトルデータが多くとも一つとなるまで、前記多次元データ空間を階層的に分割する構成となっており、
これにより、全ての既存ベクトルデータは、いずれかの他の既存ベクトルデータとリンクされた構成となっている
項目６に記載のベクトルデータ検索装置。
【００３８】
リーフノードに対応するクラスタに属する既存ベクトルデータが一つとなるまで、多次元データ空間を階層的に分割し、分割するたびに、各クラスタにおける近接したデータどうしをリンクさせることができる。これにより、全ての既存ベクトルデータを、いずれかの他の既存ベクトルデータとリンクさせることができる。しかも、木構造インデックスの生成と並行してリンクを生成することができる。なお、リーフノードに対応する既存ベクトルデータの数が０であることも可能である。
【００３９】
（項目６−２）
前記インデックス生成部は、前記リーフノードに対応するクラスタに属する前記既存ベクトルデータが多くとも一つ又は複数となるまで、前記多次元データ空間を階層的に分割する構成となっており、
さらに、前記インデックス生成部は、前記リーフノードに対応するクラスタに属する前記既存ベクトルデータが複数である場合には、当該クラスタにおける複数の前記既存ベクトルデータを、それぞれ、これらの既存ベクトルデータに最も近くかつ他のクラスタに属する既存ベクトルデータにリンクさせる構成となっている
項目６に記載のベクトルデータ検索装置。
【００４０】
リーフノードに対応するクラスタに属する既存ベクトルデータの数は複数であってもよい。この場合には、リーフノードのレベルに存在する複数の前記既存ベクトルデータを、それぞれ、これらの既存ベクトルデータに最も近くかつ他のクラスタに属する既存ベクトルデータにリンクさせることができる。
【００４１】
（項目６−３）
インデックス生成部をさらに備えており、
前記インデックス生成部は、前記既存ベクトルデータの間に張られるリンクを生成する構成となっている
項目１又は２に記載のベクトルデータ検索装置。
【００４２】
リンクの生成は、木構造インデックスを前提としなくても良い。例えば、既存ベクトルデータのうち、比較的近いものどうしを選択し、それらをリンクさせることができる。これにより、グラフ構造を生成することができる。ただし、本発明では、全ての既存ベクトルデータに少なくとも一つのリンクが付されていることが好ましい。リンクが張られていないデータは検索対象から外れるためである。もちろん、本発明では、完全グラフ構造（任意の二つのノードどうしの間に必ずリンクがある構造）とする必要はない。すなわち、完全グラフ構造でなくても、リンクを辿ることにより、新規データに類似するデータを検索することができる。
【００４３】
（項目６−４）
前記新規ベクトルデータに近接する前記既存ベクトルデータを取得する処理は、
任意の一つの前記既存ベクトルデータから、前記新規ベクトルデータに近い方向に、前記リンクを辿る処理と、
前記リンクを辿った結果、既定の開始条件を満たす既存ベクトルデータに到達した場合には、当該既存ベクトルデータを、前記検索開始点とする処理と
を含む、項目１又は２に記載のベクトルデータ検索装置。
【００４４】
この項目の発明においては、木構造インデックスを前提とせずに、任意の既存ベクトルデータを出発点として、検索開始点を取得することができる。新規ベクトルデータに近い方向にリンクを辿るためには、例えば、出発点のデータから直接に辿れる複数のデータと新規データとの距離をそれぞれ計算し、近い距離のデータの方向にリンクを辿る方法を用いることができる。この方法を順次適用することで、任意のデータ（出発点）から検索開始点に到達することができる。到達できない場合は、出発点を変更してから、同様の処理を行うことができる。
【００４５】
（項目６−５）
前記既定の開始条件とは、前記新規ベクトルデータに対する検索範囲内に前記既存ベクトルデータが存在することである
項目６−４に記載のベクトルデータ検索装置。
【００４６】
「既存ベクトルデータを検索開始点とするための条件」を、「新規ベクトルデータに対する検索範囲内に当該既存ベクトルデータが存在すること」とすることにより、検索範囲内に少なくとも一つの既存ベクトルデータが存在することを保証できる。したがって、無駄な検索を避けることができる。また、このようにして発見した検索開始点からリンクを辿ることにより、類似データを効率よく発見することが期待できる。つまり、この項目の発明によれば、検索の高速化が可能になる。
【００４７】
（項目６−６）
前記既定の開始条件とは、前記リンクを辿る処理を終了させるための前記既定の終了条件を満たさないことである
項目６−４に記載のベクトルデータ検索装置。
【００４８】
既定の終了条件とは、例えば、検索範囲のα倍（但しα＞１）の範囲の外にあることである。したがって、既定の終了条件を満たさないとは、例えば、検索範囲のα倍（但しα＞１）の範囲の内側に存在するということである。
【００４９】
既定の終了条件を満たさない検索開始点からリンクを辿ることにより、類似データを効率よく発見することが期待できる。つまり、この項目の発明によれば、検索の高速化が可能になる。
【００５０】
（項目７）
前記既定の終了条件とは、前記検索開始点を始点とするリンクを辿った結果が、前記新規ベクトルデータに対する検索範囲をα倍（α＞１）した範囲を越えることである
項目１〜６のいずれか１項に記載のベクトルデータ検索装置。
【００５１】
この項目の発明においては、検索開始点を始点とするリンクを辿った結果が、新規ベクトルデータに対する検索範囲をα倍（α＞１）した範囲を越えた場合には、その経路について、それ以上の検索を打ち切る。そして、各経路について、終了条件を満たすまで、検索を行う。そして、このような検索で得た既存データのうち、所定の検索範囲に属するものを、検索結果として返すことができる。αの値は、適宜に設定することができる。αの値を大きくすると、検索精度を高めることができる。また、αの値を小さくすると、検索時間を短縮することができる。
【００５２】
（項目８）
前記既定の終了条件とは、前記検索開始点を始点とするリンクを辿った結果が、前記新規ベクトルデータに対する検索範囲の外側において、前記リンクを、既定の回数だけ辿ったことである
項目１〜７のいずれか１項に記載のベクトルデータ検索装置。
【００５３】
類似データの検索のために、検索開始点を始点としたリンクを辿る。そのとき、検索範囲の外側で、既定の回数だけ、リンクを辿った場合は、その経路の探索をやめて、他の経路でリンクを辿る。他の経路がなければそこで探索をやめる。同様にして全ての経路におけるリンクを辿る。その後、検索で得た既存ベクトルデータのうち、検索範囲内にあるデータを、検索結果として返すことができる。既定の回数は、適宜に設定することができる。回数の値を大きくすると、検索精度を高めることができる。また、回数の値を小さくすると、検索時間を短縮することができる。
【００５４】
（項目８−１）
前記インデックス生成部は、前記新規ベクトルデータと、検索の結果として取得された類似データとの間に、リンクを生成する構成となっている
項目６−３に記載のベクトルデータ検索装置。
【００５５】
新規ベクトルデータに対する類似データを検索した後、その新規ベクトルデータをデータベースに登録することができる。このとき、新規ベクトルデータと、この新規ベクトルデータに対して所定の距離にある（例えば検索範囲内にある）既存ベクトルデータとの間にリンクを張る。データベースに登録されると、新規ベクトルデータは、既存ベクトルデータとして扱うことが可能になる。このようにすると、既存ベクトルデータ間のリンクを、自己増殖的に張っていくことができる。つまり、リンク生成作業を簡便に行うことができる。例えば、初期における既存ベクトルデータが一つであるとし、新規ベクトルデータを、既存ベクトルデータとリンクさせながらデータベースに登録することにより、既存ベクトルデータどうしがリンクされたデータベースを得ることができる。
【００５６】
（項目９）
前記検索部は、前記αの値を、検索した前記既存ベクトルデータの数の増加に対応して減少させる構成となっている
項目７に記載のベクトルデータ検索装置。
【００５７】
リンクを辿って検索したデータの数が増えた場合に、αの値を減少させることで、検索を早期に終了させることができる。これにより、データの数が過大である場合でも、検索結果を早期に取得することができる。データ数とαとの関係は、適宜な関数を用いて設定することができる。なお、αの値は、１以下にならないように設定することが、検索精度を高めるためには好ましい。ただし、早期に検索を終了させたい場合は、α＜１とすることも可能である。
【００５８】
（項目１０）
前記既定の距離は、既定の検索数の前記既存ベクトルデータのうち、前記新規ベクトルデータに対して最遠の前記既存ベクトルデータまでの距離であり、
前記検索部は、前記リンクを辿ることで得られる検索結果としての前記既存ベクトルデータに応じて、前記規定の距離を更新する構成となっている
項目１〜９のいずれか１項に記載のベクトルデータ検索装置。
【００５９】
リンクを辿ることによって得られたデータのうち、新規ベクトルデータに近い順に、既定の検索数のデータを取得することができる。この発明では、既定の検索数のデータを出力すれば、結果的に、新規ベクトルデータに対して既定の距離の範囲にあるデータを得ることができる。
【００６０】
（項目１１）
前記既定の終了条件は、以下の処理により決定される、項目１０に記載のベクトルデータ検索装置：
（Ａ）前記既定の検索数をβ倍（ただしβ＞１）した限界検索数に至るまで、前記既存ベクトルデータを、前記リンクを辿ることによって取得する処理；
（Ｂ）前記限界検索数に含まれる前記既存ベクトルデータと前記新規ベクトルデータとの距離のうちで、最大のものを求める処理；
（Ｃ）前記リンクを辿った結果が、前記ステップ（Ｂ）で求めた前記最大の距離を越えるか、又は、越えた後に既定の回数だけリンクを辿ることにより、前記既定の終了条件を満たすとする処理。
【００６１】
検索数に基づいて既定の終了条件を定めることも可能であるが、本項目の発明によれば、検索数をβ倍して得られた限界検索数を元にして、既定の終了条件を定めることができる。これにより、検索精度の向上を期待することができる。
【００６２】
（項目１２）
前記βの値を、検索した前記既存ベクトルデータの数の増加に対応して減少させる構成となっている
項目１１に記載のベクトルデータ検索装置。
【００６３】
リンクを辿って検索したデータの数が増加した場合に、βの値を減少させることで、検索を早期に終了させることができる。
【００６４】
（項目１２−１）
前記リンクを辿る処理は、前記最遠の前記既存ベクトルデータと同じか、又は、それよりも近い距離にある全ての前記既存ベクトルデータを検索した場合には終了する構成となっている
項目１０のいずれか１項に記載のベクトルデータ検索装置。
【００６５】
検索数に基づいて検索範囲を定めた場合には、検索数のデータの内で、新規ベクトルデータに対して最遠方にあるデータの距離により、検索範囲が定まることになる。この検索範囲内のデータを全て検索した場合は、検索を終了させることが望ましい。ただし、最遠方にあるデータが更新された場合には、検索範囲も更新される。
【００６６】
（項目１３）
前記最遠の前記既存ベクトルデータよりも前記新規ベクトルデータに近い既存ベクトルデータが検索された場合には、この近い既存ベクトルデータを含み、かつ、前記新規ベクトルデータに対して近い順に既定の検索数までの既存ベクトルデータの中から、最遠の既存ベクトルデータを選択することにより、前記新規ベクトルデータと既存ベクトルデータとの距離を更新する構成とされている
項目１０〜１３のいずれか１項に記載のベクトルデータ検索装置。
【００６７】
検索によって、それまでに得た最遠方のデータよりも近いデータを取得する場合がある。この場合は、検索数に含まれていたデータ群から最遠方のデータが除外され、より近いデータがここに追加される。このようにして、検索数のリストに含まれるデータを更新することができる。その結果、新規ベクトルデータから最遠のベクトルデータまでの距離が更新される。すなわち、この項目の発明では、最遠の既存ベクトルデータまでの距離を、検索の過程において、動的に更新することができる。
【００６８】
（項目１４）
さらにインデックス再構成部を備えており、
前記インデックス再構成部は、以下の処理により、前記既存ベクトルデータの間に張られたリンクを再設定する構成となっている、項目１〜１３のいずれか１項に記載のベクトルデータ検索装置：
（Ａ）既にリンクが張られた任意の前記既存ベクトルデータを、対象ベクトルとして取得する処理；
（Ｂ）前記対象ベクトルの近傍のベクトルを、前記既存ベクトルデータから取得する処理；
（Ｃ）前記近傍のベクトルに対して、前記対象ベクトルからリンクを張る処理；
（Ｄ）前記近傍のベクトルのいずれかを、新たな対象ベクトルとして取得する処理；
（Ｅ）前記（Ｂ）〜（Ｄ）の処理を繰り返すことにより、前記既存ベクトルデータの間に張られたリンクを再設定する処理。
【００６９】
この項目の発明では、遠距離にあるデータどうしの間にリンクが張られていた場合でも、リンクの接続関係を更新して、近い距離のデータ間にリンクを張ることができる。
【００７０】
（項目１５）
さらにインデックス再構成部を備えており、
前記インデックス再構成部は、いずれかの前記既存ベクトルデータが削除される場合に、以下の処理により、前記既存ベクトルデータの間に張られたリンクを再設定する構成となっている、項目１〜１４のいずれか１項に記載のベクトルデータ検索装置：
（Ａ）削除対象の前記既存ベクトルデータからリンクしている前記既存ベクトルデータの集合Ｓを特定する処理；
（Ｂ）前記集合Ｓに含まれる任意の既存ベクトルデータｓ１を特定する処理；
（Ｃ）前記既存ベクトルデータｓ１に最も近い既存ベクトルデータｓ２を前記集合Ｓから取得する処理；
（Ｄ）前記既存ベクトルデータｓ１とｓ２とをリンクさせる処理；
（Ｅ）前記集合Ｓに他の既存ベクトルデータが含まれている場合には、前記のようにリンクされた既存ベクトルデータｓ１及びｓ２を集合Ｓから除外した上で、前記（Ｂ）〜（Ｄ）の処理を繰り返すことにより、前記削除対象の既存ベクトルデータの近傍の既存ベクトルデータの間におけるリンクを再設定する処理。
【００７１】
この項目の発明では、いずれかの既存ベクトルデータが削除された場合でも、リンク切れを予防をすることができる。これにより、検索を効率的に行うことができる。
【００７２】
（項目１６）
項目１〜１５のいずれか１項に記載のベクトルデータ検索装置と、表示装置とを備えており、
前記ベクトルデータ検索装置は、取得した類似データ又はこれに関連する情報を、前記表示装置に送信する構成となっており、
前記表示装置は、前記類似データ又はこれに関連する情報を、使用者に提示する
構成となっているベクトルデータ検索システム。
【００７３】
この項目の発明では、表示装置を用いて、使用者に検索結果を呈示することができる。例えば、取得した類似データ（ベクトルデータ）に対応するマルチメディアデータ（例えば画像）や、そのマルチメディアデータに関連する情報（例えば関連するＵＲＬ）を使用者に呈示することができる。
【００７４】
（項目１７）
以下のステップを備える、ベクトルデータ検索方法：
複数の既存ベクトルデータの間に、一つの既存ベクトルデータから他の既存ベクトルデータを辿るためのリンクを張るステップ；
前記複数の既存ベクトルデータのうちのいずれかを、検索開始点として取得するステップ；
既定の終了条件を満足するまで、前記検索開始点から、前記リンクを順次辿るステップ；
前記リンクを辿る経路上にある前記既存ベクトルデータのうち、前記新規ベクトルデータに対して既定の距離にある前記既存ベクトルデータを類似データとして取得するステップ。
【００７５】
（項目１８）
項目１〜１５のいずれか１項に記載の検索装置と、ラベル生成部とを備えており、
前記検索装置における前記データベースは、前記既存ベクトルデータとラベルとを対応して記憶する構成となっており、
前記ラベル生成部は、前記検索装置における前記検索部によって取得された前記類似データに対応する前記ラベルに基づいて、前記新規ベクトルデータに付与すべきラベルを生成する構成となっている
ことを特徴とするラベル付与装置。
【００７６】
この項目に係るラベル付与装置により、本発明における検索装置を用いて、新規ベクトルデータに付与すべきラベルを決定することができる。
また、検索装置で取得された類似データに対応するラベルに基づいて、新規データに付与すべきラベルを決定するので、ラベルの信頼性を向上させることができる。さらに、このラベル付与装置では、ラベル付与処理についての計算コストを低く抑えることが可能になる。
【００７７】
ラベルが付与された新規ベクトルデータを、既存ベクトルデータとして、データベースに格納することができる。このとき、新たに格納される既存ベクトルデータについては、付与されたラベルと対応付けてデータベースに格納することが望ましい。
【００７８】
（項目１９）
前記ラベル生成部は、前記新規ベクトルデータに対して最近傍にあるか、又は、既定の距離にある前記類似データを特定し、この前記類似データに対応する前記ラベルに基づいて、前記新規ベクトルデータに付与すべきラベルを生成する
項目１８に記載のラベル付与装置。
【００７９】
この項目の装置によれば、最近傍にあるか、又は既定の距離にある類似データに対応するラベルに基づいて、新規ベクトルデータに付与すべきラベルを決定することができる。
【００８０】
（項目２０）
前記データベースにおいては、一つの前記既存ベクトルデータについて、複数のラベルが対応して記憶されている
項目１８又は１９に記載のラベル付与装置。
【００８１】
（項目２１）
前記ラベル生成部は、前記類似データに対応するラベルを複数取得した場合には、ラベルの出現数に基づいてラベルの順位づけを行い、既定の順位までのラベルを前記新規ベクトルデータに付与する構成となっている
項目１８〜２０のいずれか１項に記載のラベル付与装置。
【００８２】
類似データに対応するラベルが複数ある場合とは、類似データが複数あることによってラベルが複数ある場合と、一つの類似データが複数のラベルに対応している場合とを含む。
【００８３】
（項目２２）
前記ラベル生成部は、前記類似データに対応するラベルを複数取得した場合には、ラベルの確信度に基づいてラベルの順位づけを行い、既定の順位までのラベルを前記新規ベクトルデータに付与する構成となっており、
前記ラベルの確信度は、
前記ラベルに対応する既存ベクトルデータと新規ベクトルデータとの間の距離と、
取得された前記ラベルの個数と
に基づいて決定されるものである
項目１８〜２０のいずれか１項に記載のラベル付与装置。
【００８４】
類似データに対応するラベルが複数ある場合とは、類似データが複数あることによってラベルが複数ある場合と、一つの類似データが複数のラベルに対応している場合とを含む。
【００８５】
（項目２３）
前記ラベル生成部は、
前記類似データに対応するラベルのクラスタを生成する処理と、
前記新規ベクトルデータが前記クラスタに含まれる場合に、前記クラスタに対応するラベルを前記新規ベクトルデータに付与する処理と
を行う構成となっている項目１８〜２０のいずれか１項に記載のラベル付与装置。
【００８６】
（項目２３−１）
前記データベースに記憶された前記既存ベクトルデータは、Ｗｅｂ上で動作する画像検索エンジンにより収集された画像から生成されたものであり、
前記データベースに記憶された前記ラベルは、前記画像検索エンジンにより、前記画像に関連して収集されたテキストから生成されたものである
項目２１〜２３のいずれか１項に記載のラベル付与装置。
【００８７】
（項目２３−２）
前記データベースに記憶された前記既存ベクトルデータは、Ｗｅｂ上で動作する画像検索エンジンにより収集された画像から生成されたものであり、
前記データベースに記憶された前記ラベルは、前記画像検索エンジンにおいて、画像検索のために用いられたクエリとしての単語群から生成されたものである
項目２１〜２３のいずれか１項に記載のラベル付与装置。
【００８８】
（項目２３−３）
前記ラベルは、前記単語群のうち、前記クエリとしての使用頻度が高いものから生成されている
項目２３−２に記載のラベル付与装置。
【００８９】
（項目２３−４）
前記データベースに記憶された前記既存ベクトルデータは、
前記画像検索エンジンにより収集された画像について、画像特徴量によるクラスタリングを行い、生成されたクラスタのうちで、比較的に大きいクラスタに属する画像を抽出する処理と、
抽出された画像に基づいて前記既存ベクトルデータを生成する処理と
により生成されたものである
項目２３−１に記載のラベル付与装置。
【００９０】
このようにクラスタリングを行うことにより、検索エンジンで取得された画像のうち、ノイズである可能性が高いものを排除することができる。
【００９１】
（項目２４）
項目１〜１５のいずれか１項に記載の検索装置を用いたラベル付与方法であって：
前記既存ベクトルデータとラベルとを対応して記憶するステップと；
前記検索装置における前記検索部によって取得された前記類似データに対応する前記ラベルに基づいて、前記新規ベクトルデータに付与すべきラベルを生成するステップと
を備えることを特徴とするラベル付与方法。
【００９２】
（項目２５）
項目１８〜２３のいずれか１項に記載のラベル付与装置により付与されたラベルをキーとして用いる画像検索方法であって、
入力されたクエリに基づいて前記ラベルを検索するステップと；
前記ラベルに対応するベクトルデータを特定するステップと；
前記ベクトルデータに対応する画像を検索結果として出力するステップと
を備えることを特徴とする画像検索方法。
【００９３】
この項目におけるベクトルデータには、本発明の方法により、ラベルを付与しておくことができる。
【００９４】
（項目２６）
項目１７、２４又は２５に記載のステップをコンピュータに実行させることを特徴とするコンピュータプログラム。
【００９５】
このコンピュータプログラムは、適宜な記録媒体（例えばＣＤ−ＲＯＭやＤＶＤディスクのような光学的な記録媒体、ハードディスクやフレキシブルディスクのような磁気的記録媒体、あるいはＭＯディスクのような光磁気記録媒体）に格納することができる。このコンピュータプログラムは、インターネットなどの通信回線を介して伝送されることができる。
【発明の効果】
【００９６】
本発明によれば、新規な多次元ベクトルデータに類似するデータをデータベースから高速に検索することが可能になる。
【００９７】
また、本発明においては、終了条件を満たすまでリンクを辿ることによって類似データを検索することができる。このため、検索結果として出力できるデータ数の上限には特に制約がないという効果もある。
【００９８】
しかも、本発明では、ある検索キーに対する類似度を全て記録しておくという処理が必要ないので、データベースのデータ量を低く抑えることが可能になる。
【００９９】
さらに、本発明によれば、検索結果として得られた類似データに付与されたラベルに基づいて、新規ベクトルデータに付与すべきラベルを決定することができる。これにより、ラベル付与を簡便にかつ精度良く行うことができる。
【発明を実施するための最良の形態】
【０１００】
（第１実施形態の装置構成）
本発明の第１実施形態に係るベクトルデータ検索装置を、添付の図面に基づいて説明する。この実施形態では、ベクトルデータとして、画像の特徴量を表す多次元ベクトルデータを扱う例を説明する。ただし、ベクトルデータとしては、音声やその他のマルチメディアデータ情報の特徴量を表すものであってもよいし、他の種類の多次元データであってもよい。
【０１０１】
図１は、ベクトルデータを検索するためのシステムの全体を概略的に表している。このシステムは、サーバ１と、クライアント端末２と、ネットワーク３とを備えている。
【０１０２】
サーバ１は、本発明におけるベクトルデータ検索装置の一例に対応している。サーバ１は、一つのハードウエアあるいはソフトウエアにより構成される必要はない。必要に応じて、複数のハードウエアあるいはソフトウエアの組み合わせによりサーバ１に相当する機能を提供することができる。ネットワーク上に点在する複数のサーバにより、本実施形態のサーバ１を構成することもできる。
【０１０３】
サーバ１は、ベクトルデータ生成部１１と、インデックス生成部１２と、検索部１３と、データベース１４とを備えている。
【０１０４】
ベクトルデータ生成部１１は、クライアント端末２から送られた検索データ（例えば画像）に基づいて、多次元ベクトルデータ（すなわち新規ベクトルデータ）を生成するものである。
【０１０５】
インデックス生成部１２は、この実施形態においては、データベース１４に格納された既存ベクトルデータに対して、木構造インデックス及びリンク（すなわちグラフインデックス）を付するものである。
【０１０６】
検索部１３は、開始点取得部１３１と、インデックス検索部１３２とを備えている。
【０１０７】
開始点取得部１３１は、検索キーとなる新規ベクトルデータに近接する既存ベクトルデータを、検索開始点として取得するものである。ここで、既存ベクトルデータは、データベース１４に格納されている。これにより、本実施形態の検索部１３は、複数の既存ベクトルデータのうちのいずれかを、検索開始点として取得ないし指定することができるようになっている。
【０１０８】
インデックス検索部１３２は、既定の終了条件を満足するまで、検索開始点から、リンクを順次辿る処理を行うものである。さらに、インデックス検索部１３２は、リンクを辿る経路上にある既存ベクトルデータのうち、新規ベクトルデータに対して既定の距離にある既存ベクトルデータを類似データとして取得する処理を行う。取得された類似データあるいはそれに関連する情報は、クライアント端末２に送られる。
【０１０９】
データベース１４は、複数の既存ベクトルデータＤＢ１４１と、多次元インデックスＤＢ１４２と、グラフインデックスＤＢ１４３とを備えている。データベース１４も、当然のことながら、複数のハードウエアあるいはソフトウエアの組み合わせにより構成することができるし、データの一部がネットワークを介して遠隔地から提供される構成であっても良い。なお、前記の説明では、データベース１４が各ＤＢ１４１〜１４３を含むとしたが、これは説明の便宜のためであり、実装としては、一つのデータベース内にこれらのデータが識別可能なように格納されていても良い。
【０１１０】
既存ベクトルデータＤＢ１４１は、検索対象となるデータの特徴量を表すベクトルデータ（すなわち既存ベクトルデータ）を格納している。用いられるベクトルデータの次元数は特に制約されないが、検索精度を高めるためには、かなり高い次元数とする（例えば１０次元以上とする）ことが好ましい。
【０１１１】
多次元インデックスＤＢ１４２には、この実施形態では、木構造インデックスの情報が格納されている。木構造インデックスは、既存ベクトルデータをクラスタに分割することで得られる索引である。この実施形態では、木構造インデックスの例として、Vp-treeが用いられているが、このほかに、kd-tree、R-treeなどの他の木構造型の多次元インデックスも用いることができる（木構造インデックスについて詳しくは後述する）。
【０１１２】
グラフインデックスＤＢ１４３には、複数の既存ベクトルデータどうしの間に張られたリンクの情報が格納されている。グラフインデックスとは、既存ベクトルデータの間にリンクを張ることで形成されたグラフ構造の情報である。リンクとは、一つのデータから他のデータを辿ることができる情報である。リンクは一方向であってもよいが、双方向に辿れる構成とすることが好ましい。これにより、本実施形態では、既存ベクトルデータどうしの間に、「一つの既存ベクトルデータから他の既存ベクトルデータを辿るためのリンク」が張られたものとなっている。
【０１１３】
クライアント端末２は、この実施形態では、入力手段、出力手段及びＣＰＵなど（図示せず）を備えたパーソナルコンピュータにより構成されている。入力手段とは、例えばキーボードやマウスやタッチパッドである。出力手段とは、例えばディスプレイやプリンタである。クライアント端末２は、ネットワーク３を介してサーバ１と接続されている。本実施形態のクライアント端末２は、検索結果を使用者に呈示するための表示装置の一例に相当している。ただし、表示装置の構成は、使用者に検索結果を呈示できるものであれば、特に制約されない。
【０１１４】
また、クライアント端末２は、検索したいデータ（すなわち新規データ）を指定し、そのデータをサーバ１に送ることができるようになっている。
【０１１５】
本実施形態におけるサーバ１の構成を、その動作と共に、以下においてさらに詳しく説明する。
【０１１６】
（第１実施形態の動作）
次に、本実施形態の動作を、図面を参照しながら説明する。
【０１１７】
（全体動作の説明）
まず、動作の全体を、図２を参照しながら説明する。その後、各ステップにおける詳細な動作を説明する。
【０１１８】
（図２のステップＳＡ−１）
まず、データベース１４に登録された既存ベクトルデータについて、木構造のインデックスを付与する。なお、本実施形態では、木構造インデックスを付与すると同時に、グラフインデックスが付与される（後述）。グラフインデックスは、「一つの既存ベクトルデータから他の既存ベクトルデータを辿るためのリンク」に相当する。
【０１１９】
（図２のステップＳＡ−２）
一方、サーバ１は、クライアント端末２によって指定されたデータ（例えば画像）を受け取る。サーバ１のベクトルデータ生成部１１は、このデータ（新規データ）から特徴量を抽出する。これにより、サーバ１は、新規ベクトルデータを生成することができる。この新規ベクトルデータは、使用者が指定したデータに類似するデータを検索するための「キー」となる。サーバ１は、新規データそのものを受け取る必要はなく、新規データを特定するための情報をクライアント端末２から受け取ることもできる。この場合においても、サーバ１は、特定された新規データを取得して、新規ベクトルデータを生成することができる。要するに、本実施形態においては、検索のための新規ベクトルデータをサーバ１が生成できる構成であればよい。
【０１２０】
（図２のステップＳＡ−３）
ついで、サーバ１の検索部１３は、新規ベクトルデータに類似するデータを、以下の手順で検索する。
（１）検索部１３の開始点取得部１３１が、新規ベクトルデータに近接する既存ベクトルデータを、検索開始点として取得する。本実施形態では、木構造インデックスを用いて、検索開始点を取得する。
（２）検索部１３のインデックス検索部１３２が、既定の終了条件を満足するまで、検索開始点から、リンク（すなわちグラフインデックス）を順次辿る。
（３）リンクを辿る経路上にある既存ベクトルデータのうち、新規ベクトルデータに対して既定の距離にある既存ベクトルデータを、類似データとして、インデックス検索部１３２が取得する。
【０１２１】
以上の検索処理の詳細も後述する。
【０１２２】
（図２のステップＳＡ−４）
ついで、取得した既存ベクトルデータによって特定されるデータ（例えば画像データ）又はそれに関連するデータをサーバ１がクライアント端末２に返す。クライアント端末２では、返されたデータを、例えばブラウザにより表示する。これにより、類似データについての検索結果を使用者に呈示することができる。
【０１２３】
（インデックス生成手順）
以下、図３及び図４を主に参照しながら、本実施形態におけるインデックスの生成手順の詳細を説明する。前提としては、既存ベクトルデータがデータベース１４に格納されているものとする。
【０１２４】
（ステップＳＢ−１）
まず、任意の点（いずれかの既存ベクトルデータに相当）Ａを選択する（図４参照）。ここで選択される既存ベクトルデータには、特に制約はない。
【０１２５】
（ステップＳＢ−２）
次に、選択された点Ａから、最遠の点Ｂを選択する。これにより、点Ａから見て最も分散している方向を選択することができる。最遠の点を選ぶためには、点Ａから各点までの距離をそれぞれ計算すればよい。
【０１２６】
（ステップＳＢ−３）
次に、点Ｂからすべての点までの距離を求め、距離の順序でソートする。
【０１２７】
（ステップＳＢ−４）
ソートされた順において隣接する距離どうしの間の差分を算出する。例えば、ソートされた距離が、順に、ｄ１，ｄ２，ｄ３，…，ｄｎのように並んでいるとする。この場合、｜ｄ１−ｄ２｜，｜ｄ２−ｄ３｜のように順次算出する。
【０１２８】
そして、差分が最大である距離の間で、クラスタの分割を行う。例えば、ｄ１とｄ２との距離が最大であるとすると、距離ｄ１に対応する点Ｐ１（図４参照）と、距離ｄ２に対応する点Ｐ２の間で分割を行う。これにより、類似するデータをクラスタに分けることができる。
【０１２９】
このときの分割半径は、点Ｂを中心として、［（点Ｂと点Ｐ１間の距離）＋（点Ｂと点Ｐ２間の距離）］／２とする。既存ベクトルデータをこのように分割することによって、異なるクラスタに属するデータどうしを、比較的に距離が遠いものとすることができる。データ群を二分割した様子が図４に示されている。
【０１３０】
（ステップＳＢ−５）
さらに、この実施形態では、隣接するクラスタに属している点Ｐ１と点Ｐ２とをリンクする。これにより、本実施形態では、木構造インデックスの生成と並行して、グラフ構造（グラフインデックス）を作ることができる。
【０１３１】
一般に、点Ｐ１と点Ｐ２とは、隣接するクラスタの間において最も近接する点となるので、この実施形態においては、隣接するクラスタにおいて近接する点どうしの間にリンクを張ることができる。
【０１３２】
なお、リンク生成に当たっては、両クラスタに属するデータのすべてについて距離を計算し、距離が最小となる（又は距離が既定値以下となる）二つのデータをリンクすることも可能である。ただし、この場合は、計算時間が長くなりやすいと考えられる。
【０１３３】
（ステップＳＢ−６）
ついで、リーフノードのレベルにおける各クラスタに属するデータの数（つまりリーフノードに対応するデータの数）が２以上か否かを判断する。２以上のデータを有するクラスタについては、ステップＳＢ−１に戻り、当該クラスタをさらに分割する処理を行う。
【０１３４】
リーフノードの各クラスタに属するデータの数が１つあるいは零となった場合、インデックス生成処理を終了する。
【０１３５】
クラスタ分割の具体例を、図５〜図９を参照してさらに説明する。図５は、図４に示されるクラスタを、図３の手順でさらに分割した例である。ここで、リンクされる点の間には矢印を付している。図６〜図９は、図５に示されるクラスタを順次分割した例である。図９に示した状態では、リーフノードのクラスタに属するデータが一つだけとなっている。この段階で、クラスタの分割を終了する。また、この状態では、各クラスタに属するデータの間にリンクが生成されている（図中において矢印で示している）。
【０１３６】
また、前記のようにして生成された木構造インデックスの例（生成途中の例）を図１０に示す。なお、図１０では、リーフノードのクラスタに複数のデータが存在する例を示しており、これらのクラスタはさらに分割される必要がある。また、図１０における大きな丸はノードを表しており、小さな丸はデータを表している。さらに、図１０は木構造インデックスの構成例を示すものであり、図５〜図９に示すクラスタ構造とは一致していない。
【０１３７】
なお、前記の例では、リーフノードであるクラスタに属するデータの数を１以下としたが、２以上とすることも可能である。リーフノードに属するデータが２以上である例を図１１に示す。この場合は、前記したアルゴリズムにおけるリンクに加えて、リーフノードに属する各データをリンクさせることが望ましい（図１１参照）。このようにすれば、各データをリンクで接続することができる。
【０１３８】
（類似データ検索手順）
次に、本実施形態における類似データの検索手順を、図１２及び図１３を主に参照しながら説明する。
【０１３９】
（ステップＳＣ−１）
まず、前記のようにして生成された木構造インデックスを用いて、検索開始点取得部１３１が、検索開始点としての既存ベクトルデータを求める（図１３参照）。木構造インデックスによる検索は、トップノードから開始する。ついで、次のレベルのノード（子ノード）のうち、新規ベクトルデータが属するノードに進む。このようにして、順次、下のレベルのノードに進む。これによって、リーフノード（最下位レベルのノード）に達することができる。リーフノードに属する既存データを検索開始点とすることができる。リーフノードに複数の既存データが属する場合、それぞれを検索開始点とすることができる。すなわち、この実施形態によれば、新規ベクトルデータに近付く方向に木構造インデックスを辿ることにより、新規ベクトルデータに比較的に近い既存データを検索開始点として取得することができる。
【０１４０】
（ステップＳＣ−２）
ついで、インデックス検索部１３２が、検索開始点である既存データから、リンクを順次辿る。一つの既存データからリンクが分岐している（つまり複数の進路がある）場合も存在する。このようにリンクが分岐している場合、この明細書では、「複数の経路がある」と称している。辿った経路上にあった既存データ、あるいはそれを特定するための情報は、適宜の方法でサーバ１のメモリに記憶しておく。
【０１４１】
（ステップＳＣ−３）
ついで、一つの経路上のリンクを辿った場合において、終了条件を満たすかどうかを判断する。終了条件としては、種々のものが考えられる。例えば、以下のいずれかの終了条件がありうる。また、他の終了条件を採用することも可能である。
【０１４２】
（終了条件１）
検索開始点を始点とするリンクを辿った結果が、前記新規ベクトルデータに対する検索範囲をα倍（α＞１）した範囲（すなわち検索限界範囲）を越えること。
【０１４３】
ここで、αは、例えば１．５など、適宜の値を採用することができる。αを大きくするほど検索もれを少なくできる。一方、αを小さくするほど、検索時間を短縮できる。
【０１４４】
なお、αの値は、検索した既存ベクトルデータの数の増加に対応して減少させる構成とすることが可能である。既存ベクトルデータの数とαの値のと関係は、例えば、以下のような関数で設定することができる。
α＝1.0 + m・e-n/k
ここでｍとｋは任意定数であり、nは既に探索済み（検索済み）のベクトル数である。
【０１４５】
リンクを辿って検索したデータの数が増えた場合に、αの値を減少させることで、検索を早期に終了させることができる。これにより、データの数が過大である場合でも、検索結果を早期に取得することができる。なお、αの値は、１以下にならないように設定することが、検索精度を高めるためには好ましい。ただし、早期に検索を終了させたい場合は、α＜１とすることも可能である。
【０１４６】
（終了条件２）
検索開始点を始点とするリンクを辿った結果が、新規ベクトルデータに対する検索範囲の外側において、リンクを、既定の回数だけいずれも辿ったこと。
【０１４７】
ここで、既定の回数とは、例えば５回であるが、これについても、適宜の値を採用することができる。回数を大きくするほど検索もれを少なくでき、一方、回数を少なくするほど、検索時間を短縮できる。
【０１４８】
一つの経路について終了条件を満たしたとき、他の経路におけるリンクを辿る。いずれの経路についても終了条件を満たしたとき、次のステップに移る。
【０１４９】
（ステップＳＣ−４）
ついで、前記のようにしてリンクを辿った経路上にある各既存ベクトルデータのうち、既定の距離にあるもの（つまり検索条件に合致するもの）を、インデックス検索部１３２が特定する。そして、検索条件に合致するデータ（あるいはそれに関連するデータ）を、サーバ１が、クライアント端末２に返す。ここで、「既定の距離」は、使用者が指定しても良いし、動的に生成しても良い。使用者が指定した検索結果数（例えば検索結果として表示したい画像の数）に応じて、サーバ１が、動的に既定の距離を算出することもできる。
【０１５０】
（実施例１）
検索の具体的な実施例を図１４に基づいて説明する。検索元データ（新規データ）に符号５１、検索開始点に符号５２、検索半径（既定の距離）に符号５３、終了判定半径に符号５４を付す。検索開始点５２からリンクを辿ると、終了判定半径５４の外側においてリンクを辿ることがある。この場合に、検索を終了する。あるいは、検索半径５３の外側で既定回数以上（例えば３回以上）リンクを辿った場合に、検索を終了することもできる。また、検索結果としては、検索半径５３の範囲内にあるデータがクライアント端末２に返される。
【０１５１】
（第２実施形態）
次に、本発明の第２実施形態を、図１５及び図１６を主に参照して説明する。なお、この第２実施形態の説明においては、前記した第１実施形態と基本的に共通する構成については、同一符号を用いることにより、説明を簡略化する。
【０１５２】
第２実施形態においては、検索開始点の取得方法が、前記した第１実施形態と異なる。第１実施形態では、木構造インデックスを用いて、検索開始点を取得していた。これに対して、第２実施形態では、任意の点を起点として、検索開始点を取得する。以下、図１５に示すフローチャートに沿って詳しく説明する。第２実施形態の前提としては、既存ベクトルデータの間に、リンクが張られていることである。つまり、この実施形態の既存ベクトルデータはグラフ構造を備えている。グラフ構造の生成手法は後述する。
【０１５３】
（ステップＳＤ−１）
まず、任意の点（すなわち任意の既存データ）５０を選択する（図１６参照）。任意の点５０は、他の点（すなわち他の既存データ）との間にリンクが張られていれば、どの点であってもよい。この実施形態では、任意の点５０から、三つの点Ａ，Ｂ，Ｃ（図１６参照）にそれぞれリンクが張られているとする。
【０１５４】
（ステップＳＤ−２）
ついで、三つの点Ａ，Ｂ，Ｃのうち、検索元データ（新規データ）５１に最も近い点に向けて、リンクを辿る。この例であれば、任意の点５０から点Ａに向けてリンクを辿る。どの点が検索元データ５１に近いかを判断するためには、リンク先の各点と検索元データ５１との距離を計算すればよい。本実施形態では、リンクが張られている各点についてだけ、検索元データとの距離を計算すればよい。したがって、この実施形態では、全ての点に対する距離を求める方式に比較して、計算量を少なく抑えることができるという利点がある。
【０１５５】
（ステップＳＤ−３）
ついで、ステップＳＤ−２において取得された点が既定の範囲にあるか否かを判断する。この例では、既定の範囲を、前記した終了判定半径５４の中にあることとしている。ステップＳＤ−２で取得された点が終了判定半径５４の中に無い場合は、ステップＳＤ−２の処理を繰り返す。この例では、点Ａを中心として、各リンク先のデータと検索元データ５１との距離どうしを比較する。これによって、点Ｄを取得することができる。
【０１５６】
さらに、点Ｄについて、ステップＳＤ−３における判定を行う。この例では、点Ｄが終了判定半径５４の内部に存在する。これにより、次のステップに進むことができる。仮に点Ｄが終了判定半径５４の外部にある場合は、前記した処理を繰り返す。既定回数だけ前記の処理を繰り返しても、終了判定半径５４の内部の点が見つからない場合は、検索不能として処理を終了することができる。あるいは、任意の点を新たに取得して、前記の処理を繰り返すことができる。任意の点を取得し直す処理の回数についても、上限を設けることができる。
【０１５７】
（ステップＳＤ−４）
任意の点５０からリンクを辿った結果、終了判定半径５４の内部に存在する点が見つかった場合は、その点（本例では点Ｄ）を検索開始点とする。
【０１５８】
（第２実施形態における検索処理）
検索開始点が見つかった後は、検索終了条件を満たすまでリンクを辿ることで、類似データを検索することができる。第２実施形態における検索処理は、基本的に、第１実施形態と同様なので、これ以上詳細な説明は省略する。
【０１５９】
（第２実施形態におけるリンクの生成方法）
前記した第２実施形態では、既存ベクトルデータの間にリンクが既に張られていることを前提とした。このリンクの張り方は、検索対象である既存ベクトルデータがリンクでつながっていれば、どのようなものであってもよい。ただし、近接するデータどうしをリンクすることが、検索の効率を向上させるためには好ましい。
【０１６０】
第２実施形態では、自己生成的にリンクを張っていくことができる。例えば、既存ベクトルデータのうち、任意の一点を新規データと仮定する。すると、前記のアルゴリズムに従って、仮定した新規データに近接する既存ベクトルデータ（一つ又は複数）を見つけることができる。仮定した新規データと、見つかった既存ベクトルデータとの間にリンクを張ることができる。この処理を、各既存ベクトルデータについて行うことにより、全ての既存ベクトルデータに対してリンクを張ることができる。ここで、検索終了条件の取り方によっては、どれともリンクできない既存データも存在しうる。このような既存データについては、検索終了条件を緩和して、少なくとも一つの他の既存データとリンクさせることが好ましい。
【０１６１】
また、他の方法で自己生成的にリンクを張ることも可能である。例えば、既存ベクトルデータのうちの一点のみを既存ベクトルデータと仮定する。そして、既存ベクトルデータのうちの他の一点を新規ベクトルデータとする。この状態で前記アルゴリズムを適用すれば、これら二つのデータ間をリンクさせることができる。この場合、二つのデータが必ずリンクできるように検索終了条件を設定することが好ましい（例えば検索範囲の外側でのリンク数を終了条件とする）。ついで、さらに他の一点のデータを新規データと仮定し、リンクが張られた点を既存データと見なして、前記のアルゴリズムを適用する。この処理を順次行えば、リンクを生成することができる。
【０１６２】
また、第１実施形態のように木構造インデックスを用いて検索開始点を取得する手法において、グラフインデックスの生成には、第２実施形態の手法による検索結果を利用して、既存データ間にリンクを生成することとしてもよい。例えば、各既存データを順次新規データと見なすことで、前記した第２実施形態の手法により、各既存データに対応する類似データを検索してリンクを張ることができる。つまり、類似データの検索のために木構造インデックスの手法を用いる実施形態においても、既存データ間のリンクは、他の何らかの手法で生成しておくことが可能である。一般に、第１実施形態で説明したように、木構造インデックスの生成過程においてグラフインデックスのリンクを張ると、類似度が低いデータ間にリンクを張ってしまう場合もあるため、検索精度が低下してしまうおそれがある。これに対して、類似度が高いデータ間にリンクを張ることによって検索精度の低下を防止することができる。
【０１６３】
（第３実施形態の構成）
次に、前記した第１実施形態又は第２実施形態で説明した検索装置を用いたラベル付与装置の構成を、第３実施形態として、図１７に基づいて説明する。なお、本実施形態の説明においては、前記した第１実施形態又は第２実施形態で用いる構成要素と基本的に共通する要素については、同一符号を付することにより、説明を簡潔にする。
【０１６４】
第３実施形態では、第１実施形態におけるサーバ１に代えて、サーバ１００が用いられている。このサーバ１００が、この実施形態では、ラベル付与装置に対応している。
【０１６５】
サーバ１００は、第１実施形態におけるサーバ１と同様に、ベクトルデータ生成部１１と、インデックス生成部１２と、検索部１３と、データベース１４とを備えている。これらの要素により、第３実施形態では、検索装置が構成されている。
【０１６６】
第３実施形態のサーバ１００は、さらに、ラベル生成部１６を備えている。これにより、本実施形態のラベル付与装置は、第１実施形態又は第２実施形態に記載された検索装置と、ラベル生成部１６とを備えた構成となっている。
【０１６７】
第３実施形態におけるデータベース１４は、ラベルＤＢ１４５をさらに備えている。このデータベース１４においては、ベクトルデータＤＢ１４１に記憶された既存ベクトルデータと、ラベルＤＢ１４５に記憶されたラベルとが関連付けられている。つまり、既存ベクトルデータ及びラベルの一方に基づいて、他方を参照できるようになっている。これにより、本実施形態のデータベース１４は、既存ベクトルデータとラベルとを対応して記憶する構成となっている。
【０１６８】
ラベル生成部１６は、検索部１３によって取得された類似データに対応するラベルに基づいて、新規ベクトルデータに付与すべきラベルを生成する構成となっている。ラベル生成部１６の構成は、ラベル生成の手順として追って詳しく説明する。
【０１６９】
（第３実施形態におけるラベル付与手順）
次に、第３実施形態におけるラベル付与の方法を、図１８を参照して説明する。
【０１７０】
（図１８のステップＳＥ−１）
まず、既存ベクトルデータとラベルとを対応してデータベース１４に記憶する。対応する既存ベクトルデータとラベルとを取得する方法としては、特に制約されないが、例えば以下の方法がある。下記以外の取得方法については後述する。
【０１７１】
（画像検索エンジンによるクローリングの結果を利用する方法…図１９）
（図１９のステップＳＦ−１）
一般に、Ｗｅｂ上で動作する画像検索エンジンが知られている。この画像検索エンジンは、ユーザが入力したクエリ（一般的にはテキスト）に基づいて、Ｗｅｂ上の画像を検索する。
【０１７２】
（ステップＳＦ−２）
例えば、Ｗｅｂ上に、クエリに対応するテキストがあれば、そのテキストが含まれる文書中の画像を検索結果として返すことができる。
【０１７３】
あるいは、画像の特徴量を用いた画像検索エンジンも考えられる。この場合、クエリ画像の特徴量と、Ｗｅｂ上の画像との距離を計算し、近い距離にある画像を検索結果として返すことができる。
【０１７４】
検索の結果として得られた画像の一例を、図２０として示す。
【０１７５】
（ステップＳＦ−３及びＳＦ−４）
さらに、画像検索エンジンによって、検索結果として得られた画像に近い位置にあるテキストを、画像と同時に取得することができる。このテキストから、ラベルを生成することができる。例えば、形態素解析によってテキストから単語（単数又は複数）を抽出してラベルとすることができる。ラベルは単語の組み合わせであっても良い。図２０に対応するラベルの例としては、「富士山」「山」「空」「雪」などが考えられる。ラベルとは、一般に、このようなテキスト情報であるが、テキストに基づいて検索できる情報であればよい。
【０１７６】
前記のようにして取得した画像に対応するベクトルデータは、第１又は第２実施形態で説明したように、リンクを付された上で、既存ベクトルデータとして、ベクトルデータＤＢ１４１に記憶される。リンクが付された既存ベクトルデータの一例を図２１に示す。この図における一つの丸が一つの既存ベクトルデータを示している。
【０１７７】
一方、ラベルを、画像から生成された既存ベクトルデータに対応して、ラベルＤＢ１４５に格納する。図２１では、一つの既存ベクトルデータに対して一つのラベルが付されている。
【０１７８】
（図１８のステップＳＥ−２）
次に、新規ベクトルデータに近い既存ベクトルデータを検索する。新規ベクトルデータは、ラベルを付すべき画像に対応するベクトルデータである。この検索手法としては、既に説明した第１又は第２次実施形態での類似データの検索方法を用いることができるので、詳細についての説明は省略する。
【０１７９】
（図１８のステップＳＥ−３）
ついで、新規データに付すべきラベルの生成手順を、図２２をさらに参照しながら説明する。
【０１８０】
（図２２のステップＳＧ−１）
前記したステップＳＥ−２により、新規ベクトルデータに近い（すなわち類似する）既存ベクトルデータを、類似データとして特定する。このように特定された類似データ６１の例を、図２３に示す。なお、ここで符号５１は新規データを示す。
【０１８１】
（ステップＳＧ−２）
ついで、類似データのうち、最近傍のデータを特定する。図２３の例では、類似データ６１が一つだけ特定されているので、これが最近傍データとして特定される。ステップＳＧ−１において複数の類似データを特定した場合は、そのうちで最近傍のデータを特定する。なお、ここでは、最近傍の類似データを選択しているが、既定の距離にある類似データ（単数あるいは複数）を選択することも可能である。
【０１８２】
（ステップＳＧ−３）
最近傍のデータに付されていたラベルを、新規データのためのラベルとして特定する。このようにして特定されたラベルを、ラベルＤＢに格納することができる。一方、ラベルが付された新規データは、ラベルと関連付けられた既存データとして、ベクトルデータＤＢ１４１に記憶される。
【０１８３】
この実施形態のようなラベル付けの手順は、図２４に示されるように空間をラベル付けしていることと等価である。しかしながら、この実施形態のラベル付与方法では、一般的な学習方法に比べて、ラベル付けのための計算量が少なくなり、このため、ラベル付けを高速に行うことが可能になる。なお、図２４に示した境界は、論理的な境界を示すものに過ぎず、実際にこのような区分けがされるわけではない。
【０１８４】
ラベル付けの手法としては、従来、ＳＶＭ（Support Vector Machine）などの機械学習器を用いて、入力に対するラベルを決定するものが知られている（例えば、特開2007-235951号公報参照）。しかしながら、ＳＶＭを用いた手法を、画像のベクトルデータ（特徴量）に適用すると、学習において多大な時間を要してしまい、実用的ではない。これに対して、本実施形態の方法では、未知データ（新規画像に対応するベクトルデータ）に対するラベルを、簡便な方法で、しかも精度良く決定することができる。したがって、本実施形態の方法は、計算コストを低く抑えることができる。
【０１８５】
（第４実施形態）
次に、第４実施形態に係るラベル付与方法を図２５〜図２７を参照しながら説明する。なお、この実施形態の説明においては、第３実施形態におけるラベル付与方法と基本的に共通する部分については、同一符号を付することにより、説明を簡易とする。
【０１８６】
第４実施形態においては、一つの既存データに対して、複数のラベルが付されている（図２６参照）。
【０１８７】
（図２５のステップＳＨ−１）
この第４実施形態においても、前記した第３実施形態の場合と同様に、新規データに類似するデータを特定する。第４実施形態では、四つの類似データ７１〜７４が特定されたと仮定する（図２７参照）。
【０１８８】
（ステップＳＨ−２）
ついで、この第４実施形態では、各類似データに付されたラベルを集計して、順位をつける。具体的には、例えば、以下のように行う。
【０１８９】
四つの類似データについて、新規データとの距離（類似度）をそれぞれ計算する。その結果が以下のようであったとする。
順位、距離、ラベル
１位、0.2、空、山、海
２位、0.3、空、雪
３位、0.4、空、雪
４位、0.5、雲、空
【０１９０】
この場合、最高位にあるデータに対応するラベルを、新規データに付すラベルとすることができる。これは、第３実施形態の方法と同様である。
【０１９１】
ただし、この第４実施形態では、さらに、以下のような処理を行う。これは、言わば、ラベル単位に多数決を行って決定する方法である。上記の例では、ラベル単位に出現数を数えると、
空：３点
雪：２点
山：１点
海：１点
雲：１点
となる。
【０１９２】
このように、ラベルについて、その出現数に応じて順位をつけることができる。
【０１９３】
（ステップＳＨ−３）
次に、既定の範囲内のラベルを選択する。例えば上位の二つのラベルを選択すれば、空と雪を選択することができる。これらのラベルを、新規データに対するラベルとすることができる。
【０１９４】
一般に、ラベルと既存データとの対応関係（つまり学習データ）にノイズ（つまり間違った学習データ）が入っている場合がある。この場合において、最近傍の類似データに付されたラベルがノイズである場合には、そのラベルを用いることは不適切である。前記の方法によれば、ノイズであるラベルの影響を軽減することができるという利点がある。
【０１９５】
（第５実施形態）
次に、第５実施形態に係るラベル付与方法を図２８を参照しながら説明する。なお、この実施形態の説明においては、第３実施形態におけるラベル付与方法と基本的に共通する部分については、同一符号を付することにより、説明を簡易とする。
【０１９６】
第５実施形態においては、第４実施形態と同様に、一つの既存データに対して、複数のラベルが付されている。
【０１９７】
（図２８のステップＳＩ−１）
第５実施形態においても、前記した第３実施形態の場合と同様に、新規データに類似するデータを特定する。
【０１９８】
（ステップＳＩ−２）
ついで、この第５実施形態では、各ラベル毎に確信度を算出する。具体的には、例えば、以下のように行う。
確信度(w)＝Σsiw / 100
siw:ラベルwを持つi番目の学習データ（既存データ）と新規データとの類似度
【０１９９】
ここで、類似度は以下のように定義できる。
類似度(%)＝（1-d / max）・100
d:データ間の距離
max:距離の最大値（距離が無限大の場合には何らかの有限な値を指定）
【０２００】
（ステップＳＩ−３）
前記のように計算された確信度を元に、ラベルを順位づけし、順位に基づいてラベルを決定することができる。例えば、既定の順位にあるラベルを選択することができる。このようにして選択されたラベルを、新規データに対するラベルとすることができる。
【０２０１】
この方法においても、ノイズであるラベルの影響を軽減することができるという利点がある。
【０２０２】
（第６実施形態）
次に、第６実施形態に係るラベル付与方法を図２９及び図３０を参照しながら説明する。なお、この実施形態の説明においては、第３実施形態におけるラベル付与方法と基本的に共通する部分については、同一符号を付することにより、説明を簡易とする。
【０２０３】
第６実施形態においては、第４実施形態と同様に、一つの既存データに対して、複数のラベルが付されている。
【０２０４】
（図２９のステップＳＪ−１）
第６実施形態においても、前記した第３実施形態の場合と同様に、新規データに類似するデータを特定する。
【０２０５】
（ステップＳＪ−２）
ついで、この第６実施形態では、各ラベル毎の特徴量（ベクトルデータ）を用いて、ラベル毎にクラスタを生成する（図３０参照）。多次元データであれば、同一ラベルを持つベクトルデータの重心（中心）と半径とでクラスタを表現できる。
【０２０６】
（ステップＳＪ−３）
ついで、生成されたクラスタに、新規データが包含されるか否かを判断する。つまり、新規データが、どのクラスタに属するかを決定する。なお、図３０の例では、新規データは、図示されたクラスタには属していないと判断できる。
【０２０７】
（ステップＳＪ−４）
ついで、新規データが属するクラスタのラベルを、付与すべきラベルと決定する。本実施形態のようにラベルを生成すると、ラベルの信頼性を向上させることができる。
【０２０８】
（第７実施形態）
次に、第７実施形態に係るラベル付与方法を図３１及び図３２を参照しながら説明する。なお、この実施形態の説明においては、第３実施形態におけるラベル付与方法と基本的に共通する部分については、同一符号を付することにより、説明を簡易とする。
【０２０９】
第７実施形態においては、第４実施形態と同様に、一つの既存データに対して、複数のラベルが付されている。
【０２１０】
（図３１のステップＳＫ−１）
第７実施形態においても、前記した第３実施形態の場合と同様に、新規データに類似するデータを特定する。
【０２１１】
（ステップＳＫ−２）
ついで、この第７実施形態では、各ラベル毎に、距離を用いてクラスタを生成する（図３２参照）。すなわち、この方法では、同一ラベル内で、任意の１点からの他のすべての点までの距離の総和が最小となる点を求める。そして、それを中心とした半径を求める。
【０２１２】
この半径は例えば、次のようにして求めることができる。
【０２１３】
同一ラベル内から抽出した任意の一点pkからの距離の総和ｓは以下の式で表される。
2010079871.tif 000003
【０２１４】
なお、この式においてd(pi,pj)はpiとpj間の距離、nはラベル内の点の総数である。同一ラベル内のすべての点に対して上記距離の総和を求め、総和が最小となるpkをクラスタの中心とする。次に、pkから他のすべての点の距離を求めて、最大の距離を半径とする。また、単純にすべての点の重心（平均）を求めそれをクラスタの中心としてもよいし、予め設定した適宜な値を用いても良い。
【０２１５】
（ステップＳＫ−３）
ついで、生成されたクラスタに、新規データが包含されるか否かを判断する。つまり、新規データが、どのクラスタに属するかを決定する。なお、図３２の例では、新規データは、図示されたクラスタに属していると判断できる。図３２の例は、図３０の例と同じ特徴点が表されているが、クラスタの取り方によって、ラベルが異なっている。
【０２１６】
（ステップＳＫ−４）
ついで、新規データが属するクラスタのラベルを、付与すべきラベルと決定する。この実施形態の方法によれば、距離しか定義されていない空間の場合においても、クラスタに基づいてラベルを決定することができる。
【０２１７】
（第８実施形態）
前記した実施形態では、図１９に示されるように、画像検索エンジンによるクローリングの結果を利用して、既存ベクトルデータとラベルとの対応関係を設定していた。
【０２１８】
第８実施形態では、データベースに記憶されるラベルを、画像検索エンジンにおいて、画像検索のために用いられたクエリとしての単語群（すなわちテキスト情報）から生成する。そして、そのラベルを、画像検索の結果として得られた画像を示すベクトルデータに対応付けて記録する。ラベルに対応付けられたベクトルデータは、既存ベクトルデータとしてベクトルデータＤＢ１４１に記憶される。これによって、既存ベクトルデータに対するラベル付与を簡便に行うことができる。
【０２１９】
特に、単語群のうちで、クエリとしての使用頻度が高いものからラベルを生成することが好ましい。このようにすれば、ラベルの信頼性を向上させることができる。
【０２２０】
第８実施形態における他の構成及び利点は、前記した実施形態と同様なので、これ以上詳しい説明は省略する。
【０２２１】
（第９実施形態）
第９実施形態は、既存ベクトルデータとラベルとの初期の対応関係を設定するために、さらに別の手順を用いる例である。この実施形態を、図３３を参照しながら説明する。
【０２２２】
（図３３のステップＳＬ−１及びＳＬ−２）
まず、画像検索エンジンにクエリを入力し、画像を取得する。これは前記した実施形態と同様である。
【０２２３】
（ステップＳＬ−３）
ついで、この実施形態では、画像検索エンジンにより収集された画像について、画像特徴量によるクラスタリングを行う。そして、生成されたクラスタのうちで、比較的に大きいクラスタに属する画像を抽出する。小さいクラスタに属する画像は廃棄してよい。検索エンジンで得られた画像には、誤検索によるものもありうる。そこで、クラスタリングを行うことにより、誤検索による画像を除外することができる。
【０２２４】
（ステップＳＬ−４）
ついで、抽出された画像についてベクトルデータを生成する。このベクトルデータは、既存ベクトルデータとしてベクトルデータＤＢ１４１に記憶されるものである。
【０２２５】
（ステップＳＬ−５及びＳＬ−６）
一方、抽出された画像に関連するテキストを、前記した実施形態と同様にして取得し、それに基づいてラベルを取得する。さらに、取得されたラベルを、既存ベクトルデータに対応してラベルＤＢ１４５に記録する。
【０２２６】
本実施形態における他の構成及び利点は、第８実施形態と同様なので、これ以上詳細な説明は省略する。
【０２２７】
（応用例）
以下、本実施形態の方法で付与されたラベルを用いた検索方法を説明する。
【０２２８】
（応用例１）
Web上で画像を検索する検索エンジンにおけるクローラで画像を収集する。この画像に対して、本実施形態の方法でラベルを付与する。そして、テキストクエリを用いて、ラベルを基準にして検索を行う。こうすることで、画像の検索精度を高めることができる。つまり、本実施形態のラベル付与装置により付与されたラベルをキーとして画像検索を行うことができる。ラベルによる検索と、従来の画像検索とを組み合わせた実装も可能である。
【０２２９】
（応用例２）
Ｗｅｂ上で画像を共有するためのコミュニティサイトが知られている。このシステムの場合、画像に対して、人手によりタグを付与し、このタグを用いて画像を検索している。
【０２３０】
本実施形態の方法を用いれば、既登録画像に付されたタグを基準にして、新規の画像に対するタグ（つまりラベル）を自動的にかつ高速に生成することができる。タグを画像に関連付けて登録しておくことにより、タグを用いて高精度の画像検索が可能になる。
【０２３１】
（応用例３）
指定されたメディア（たとえば画像）から特徴量（ベクトルデータ）を抽出する。ついで、その特徴量に基づいて、本実施形態のラベル付け方式により、ラベルを取得する。そして、取得したラベルでWeb検索をし、検索されたWebページを出力する。
【０２３２】
この場合、たとえば、カメラ付携帯電話で商品を撮影すると、商品紹介ページを検索できるサービスを提供できる。また、花を撮影すると、その花の説明ページが検索でき、花図鑑のようなものを実現できる。
【０２３３】
（第１０実施形態）
次に、本発明の第１０実施形態に係るベクトルデータ検索装置を、図３４〜図３６を参照して説明する。なお、この第１０実施形態の説明においては、前記した第１実施形態と基本的に共通する構成については、同一符号を用いることにより、説明を簡略化する。また、このベクトルデータ検索装置を、前記したラベル付与装置のために用いることは可能である。
【０２３４】
前記した実施形態では、新規ベクトルデータからの距離を具体的に指定することで、検索範囲を決定していた。この第１０実施形態では、距離ではなく、検索数（検索結果として取得したいデータの数）を指定する。そして、この検索数に基づいて、検索範囲を決定する。以下、図３４に示すフローチャートを参照しながら、本実施形態における検索範囲の決定方法の具体例を説明する。この実施形態では、検索数を１０に設定した例を説明する。
【０２３５】
（図３４のステップＳＭ−１）
まず、検索元データ（新規ベクトルデータ）５１を取得した後、検索開始点５２を特定する（図３５参照）。そのための方法は、前記第１実施形態と同様でよい。
【０２３６】
（ステップＳＭ−２）
ついで、検索開始点からリンクを辿ることにより、データを検索する。リンクの辿り方は、前記第１実施形態と同様でよい。
【０２３７】
（ステップＳＭ−３）
リンクを辿ることにより、所定の検索数（この例では１０個）のデータを収集することができる。収集した各データと検索元データ５１との距離の順に各データをソートして得たリストを、図３６（ａ）に示す。
【０２３８】
そして、このリストにおいて、最遠の既存ベクトルデータに対応する距離を、検索範囲とする。検索範囲を図３５において符号５６１で示した。
【０２３９】
また、この実施形態では、検索範囲のα倍（α＞１）の範囲を、検索限界範囲として設定する。検索範囲５６１に対応する検索限界範囲を、図３５において符号５７１で示した。この実施形態では、検索限界範囲の外においてリンクを既定回数（例えば５回）辿ったときに、検索の終了条件を満たすとする。既定回数は１以上の任意の整数に設定することができる。なお、本実施形態において、α＝１とすることは可能である。この場合は、検索範囲を検索限界範囲とすることに等しい。すなわち、検索範囲を、前記した例における検索限界範囲と見なし、その外側においてリンクを既定回数辿ったとき、検索を終了させることができる。
【０２４０】
（ステップＳＭ−４及びＳＭ−５）
引き続き、既定の終了条件を満たさない限り、リンクを辿って、データを検索していく。ここで、既定の終了条件として、検索限界範囲の外側におけるリンクを既定回数辿ったことであるとすれば、全ての探索経路においてこの条件を満たしたとき、検索結果を出力する。
【０２４１】
（ステップＳＭ−６及びＳＭ−７）
検索によって得られたデータと、新規ベクトルデータとの距離が、既に取得していた最遠のベクトルデータまでの距離（つまり検索範囲）よりも短い場合、最遠のベクトルデータを更新する。例えば、図３６の例において、新たに、距離０．２０のデータを検索したとする。この場合、検索数の第６順位にこのデータが割り込む（図３６（ｂ）参照）。そして、以前の最遠のデータ（図３６（ａ）における、距離０．３２のデータ）は、リストから削除される。この結果、最遠データまでの距離は、０．３０となる。つまり、図（ａ）のリストで第９順位であったデータが繰り下がって、第１０順位、すなわち最遠データとなる。この状態では、以前の最遠データは、リストから押し出された状態となっている。
【０２４２】
最遠データが更新された結果、検索範囲も小さくなる。距離０．３０に対応した検索範囲を、図３５において符号５６２で示す。また、この検索範囲に対応した限界検索範囲を、符号５７２で示す。このように、最遠データより近いデータが検索されるたび、検索範囲及び限界検索範囲が更新され、小さくなる。
【０２４３】
（ステップＳＭ−８）
検索範囲内の全てのベクトルデータの検索が終了した場合は、それまでの検索結果を出力する
【０２４４】
（ステップＳＭ−９）。
【０２４５】
検索範囲内に未検索のデータが残っている場合は、ステップＳＭ−４に戻り、前記した処理を続ける。
【０２４６】
ここで、検索の結果、距離０．２２のデータが検索された例を図３６（ｃ）に示す。この場合、このデータが第８順位に割り込み、従来の最遠データ（図３６（ｂ）において距離０．３０のデータ）が押し出される。その結果、距離０．２４のデータが最遠データとなる。
【０２４７】
距離０．２４のデータに対応して、前記と同様に、新たな検索範囲５６３と、新たな検索限界範囲５７３とが定まる。
【０２４８】
このようにして、この実施形態によれば、検索数の指定に応じて、検索範囲を動的に定めることができる。また、近いデータが検索されるたびに、検索範囲を狭めることができるので、検索精度を維持しつつ、検索速度を向上させることができる。
【０２４９】
本実施形態においては、本発明における「既定の距離」が、「既定の検索数の既存ベクトルデータのうち、新規ベクトルデータに対して最遠の既存ベクトルデータまでの距離」となっている。また、この実施形態では、「既定の検索数の既存ベクトルデータが、検索開始点からリンクを辿ることにより取得されたもの」となっている。
【０２５０】
また、前記した実施形態の検索手法によれば、「最遠の既存ベクトルデータよりも新規ベクトルデータに近い既存ベクトルデータが検索された場合には、この近い既存ベクトルデータを含み、かつ、新規ベクトルデータに対して近い順に既定の検索数までの既存ベクトルデータの中から、最遠の既存ベクトルデータを選択することにより、新規ベクトルデータと既存ベクトルデータと間の最大距離を更新する」という構成が実現されている。
【０２５１】
（第１０実施形態の変形例）
本実施形態においては、限界検索範囲を、検索範囲のα倍（α＞１）により求めた。しかしながら、限界検索範囲を、限界検索数から求めることも可能である。以下、限界検索数を用いる変形例を説明する。
【０２５２】
（Ａ）まず、既定の検索数をβ倍（ただしβ＞１）した限界検索数を求める。なお、理論的にはβ＝１も可能であるが、この場合は、限界検索数＝検索数となるため、限界検索数を別途定める意義が薄い。
【０２５３】
（Ｂ）ついで、限界検索数に至るまで、既存ベクトルデータを、リンクを辿ることによって取得する。この取得は、前記した検索数までのデータの取得と並行して行われることが好ましい。すなわち、限界検索数までのデータを常に取得するものとし、そのうちで、検索数の順位までのデータを、前記した検索範囲の決定のために用いる。
【０２５４】
（Ｃ）ついで、限界検索数に含まれる既存ベクトルデータと新規ベクトルデータとの距離のうちで、最大のものを求める。この最大の距離が、検索限界範囲に相当する。検索に伴い、検索限界範囲内のデータが新たに見つかれば、限界検索数に含まれるデータのリストを更新し、検索限界範囲を縮小することができる。
【０２５５】
（Ｄ）リンクを辿った結果が、前記したステップ（Ｃ）で求めた最大の距離（すなわち検索限界範囲）を越えるか、又は、越えた後に既定の回数だけリンクを辿ることにより、既定の終了条件を満たすとすることができる。あるいは、検索限界範囲を、求めた最大の距離のα倍とすることもできる。
【０２５６】
この検索手法によれば、限界検索数を元にして、既定の終了条件を定めることができる。
【０２５７】
また、βの値を、検索した既存ベクトルデータの数の増加に対応して減少させることも可能である。減少させるための関数としては、前記したαを減少させる関数と同じでも良いし、異なっていてもよい。
【０２５８】
リンクを辿って検索したデータの数が増加した場合に、βの値を減少させることで、検索を早期に終了させることができる。
【０２５９】
本実施形態における他の構成及び利点は、第１実施形態と同様なので、これ以上詳細な説明は省略する。
【０２６０】
（第１１実施形態）
次に、本発明の第１１実施形態に係るベクトルデータ検索装置を、図３７〜図３９を参照して説明する。なお、この第１１実施形態の説明においては、前記した第１実施形態と基本的に共通する構成については、同一符号を用いることにより、説明を簡略化する。また、このベクトルデータ検索装置を、前記したラベル付与装置のために用いることは可能である。
【０２６１】
本実施形態の検索装置は、第１実施形態の検索装置に加えて、さらにインデックス再構成部１８を備えている。
【０２６２】
インデックス再構成部１８は、既存ベクトルデータの間に張られたリンクの関係を再設定することにより、この関係を整理するためのものである。
【０２６３】
インデックス再構成部１８の詳しい動作を、図３８に示すフローチャートに従って説明する。
【０２６４】
（図３８のステップＳＮ−１）
まず、既にリンクが張られた任意の既存ベクトルデータを、対象ベクトルとして取得する。すなわち、前記したように、各既存ベクトルデータ間には、これらを検索するためのリンクが張られている。リンクが張られたデータの一例を、図３９（ａ）に示す。この図において、符号５８１は対象ベクトルを示す。また、符号５８２は、比較的に登録が早いベクトルデータを示す。この図の例では、ベクトルデータ５８２は、比較的に遠方のデータともリンクが張られている。このような状態は、データの追加と同時にリンクを動的に生成する場合に生じやすいと考えられる。このリンクの状態においては、検索効率や検索精度が悪くなることが予想される。なお、図３９に示すインデックス空間を、以下では旧インデックス空間と呼ぶ。
【０２６５】
（ステップＳＮ−２）
ついで、対象ベクトル５８１を、新しいインデックス空間に登録する。新しいインデックス空間は、まだデータが登録されていない空間であり、データベース中に生成される仮想の空間である。
【０２６６】
（ステップＳＮ−３）
ついで、対象ベクトル５８１の近傍のベクトルを、旧インデックス空間における既存ベクトルデータの中から取得する。この例では、四つの近傍ベクトル５８３が選択される（図３９（ｂ）参照）。また、近傍ベクトルの検索方法としては、前記した実施形態において説明したベクトルデータ検索方法を用いることができる。
【０２６７】
（ステップＳＮ−４）
ついで、近傍ベクトル５８３を、対象ベクトルとの間でのリンクを張りながら、新インデックス空間に登録する。登録した状態を、図３９（ｂ）に示している。
【０２６８】
（ステップＳＮ−５）
ついで、旧インデックス空間にベクトルデータが残っているかを確認する。残っていなければ処理が終了する。残っている場合は次のステップに進む。
【０２６９】
（ステップＳＮ−６）
ついで、近傍ベクトル５８３のいずれかを、新たな対象ベクトルとして取得する。つまり、近傍ベクトル５８３のうちの一つを、旧インデックス空間における対象ベクトルとする。
【０２７０】
その後、前記したステップＳＮ−３〜ＳＮ−５の処理を繰り返す。つまり、再帰的な処理を行う。これによって、この実施形態では、既存ベクトルデータの間に張られたリンクを再設定することができる。リンクを再構成した結果の例を、図３９（ｃ）に示す。
【０２７１】
この実施形態においては、遠距離にあるデータどうしの間にリンクが張られていた場合でも、リンクの接続関係を更新して、近い距離のデータ間にリンクを張ることができる。新たなインデックス空間を用いて検索を行うことにより、検索効率や検索精度の向上が期待できる。
【０２７２】
本実施形態における他の構成及び利点は、第１実施形態と同様なので、これ以上詳細な説明は省略する。
【０２７３】
（第１２実施形態）
次に、本発明の第１２実施形態に係るベクトルデータ検索装置を、図４０及び図４１を参照して説明する。なお、この第１２実施形態の説明においては、前記した第１実施形態と基本的に共通する構成については、同一符号を用いることにより、説明を簡略化する。また、このベクトルデータ検索装置を、前記したラベル付与装置のために用いることは可能である。
【０２７４】
本実施形態の検索装置は、前記した第１１実施形態と同様に、第１実施形態の検索装置に加えて、さらにインデックス再構成部１８を備えている。本実施形態におけるインデックス再構成部１８は、いずれかの既存ベクトルデータが削除される場合に、既存ベクトルデータの間に張られたリンクを再設定するためのものである。なお、インデックス再構成部１８は、第１１実施形態で説明した機能と、第１２実施形態で説明する機能の両方を備えることも可能である。
【０２７５】
第１２実施形態におけるインデックス再構成部１８の機能を、図４０に示すフローチャートに従って説明する。
【０２７６】
（図４０のステップＳＰ−１）
まず、インデックス空間における一つのデータを削除する。図４１の例において、削除するデータを、符号５９１１で示す。データ５９１１を削除すると、その近傍のデータどうしのリンクが切れてしまう。これでは、検索精度の悪化が予想される。
【０２７７】
（ステップＳＰ−２）
本実施形態のインデックス再構成部１８は、まず、削除対象の既存ベクトルデータ５９１１からリンクしている既存ベクトルデータの集合Ｓを特定する。図４１の例において、集合Ｓを構成するデータに、符号５９１２を付した。
【０２７８】
（ステップＳＰ−３）
ついで、集合Ｓに含まれる任意の既存ベクトルデータｓ１を特定する。つまり、データ５９１２のいずれかを選択する。
【０２７９】
（ステップＳＰ−４）
ついで、既存ベクトルデータｓ１に最も近い既存ベクトルデータｓ２を集合Ｓから取得する。つまり、残ったデータ５９１２のうち、いずれかのデータを選択する。
【０２８０】
（ステップＳＰ−５）
ついで、既存ベクトルデータｓ１とｓ２とをリンクさせる。リンクした状態の一例を図４１（ｂ）に示す。なお、データｓ１とｓ２との間に既にリンクがあれば、あらためてリンクを張る必要はない。
【０２８１】
（ステップＳＰ−６）
集合Ｓに他の既存ベクトルデータが含まれている場合には、前記のようにリンクされた既存ベクトルデータｓ１及びｓ２を集合Ｓから除外した上で、前記したステップＳＰ３〜ＳＰ５の処理を繰り返す。つまり、再帰的な処理を行う。集合Ｓに含まれる他のデータがなければ、処理を終了する。これにより、削除対象の既存ベクトルデータの近傍の既存ベクトルデータの間におけるリンクを再設定することができる（図４１（ｂ）参照）。
【０２８２】
この実施形態では、いずれかの既存ベクトルデータが削除された場合でも、リンク切れを予防することができる。これにより、検索を効率的にかつ高精度で行うことができる。
【０２８３】
なお、集合Ｓからベクトルデータｓ１を選択する場合、「削除したベクトルデータに対して最近傍のベクトルデータから最も遠いベクトルデータ」をｓ１に選ぶことが好ましい。削除したデータに近いデータからリンクの付与を始めると、比較的に遠いデータどうしがリンクされる可能性がある。これに対して、前記のようにベクトルデータｓ１を選ぶと、近いデータが順次リンクされる傾向が高くなり、検索の効率化を期待することができる。
【０２８４】
本実施形態における他の構成及び利点は、第１実施形態と同様なので、これ以上詳細な説明は省略する。
【０２８５】
前記した各実施形態の動作は、コンピュータに適宜のコンピュータソフトウエアを組み込むことにより実施することができる。
【０２８６】
なお、本発明の内容は、前記実施形態に限定されるものではない。本発明は、特許請求の範囲に記載された範囲内において、具体的な構成に対して種々の変更を加えうるものである。
【０２８７】
例えば、前記した各構成要素は、機能ブロックとして存在していればよく、独立したハードウエアとして存在しなくても良い。また、実装方法としては、ハードウエアを用いてもコンピュータソフトウエアを用いても良い。さらに、本発明における一つの機能要素が複数の機能要素の集合によって実現されても良く、本発明における複数の機能要素が一つの機能要素により実現されても良い。
【０２８８】
また、機能要素は、物理的に離間した位置に配置されていてもよい。この場合、機能要素どうしがネットワークにより接続されていても良い。グリッドコンピューティングにより機能を実現し、あるいは機能要素を構成することも可能である。
【図面の簡単な説明】
【０２８９】
【図１】本発明の第１実施形態に係る検索装置を用いた検索システムの基本的な構成を示すブロック図である。
【図２】本発明の第１実施形態に係る検索方法の全体的な流れを概略的に説明するためのフローチャートである。
【図３】第１実施形態におけるインデックスの作成方法を説明するためのフローチャートである。
【図４】第１実施形態におけるインデックスの作成方法を説明するための説明図である。
【図５】第１実施形態におけるインデックスを作成する過程を説明するための説明図である。
【図６】第１実施形態におけるインデックスを作成する過程を説明するための説明図である。
【図７】第１実施形態におけるインデックスを作成する過程を説明するための説明図である。
【図８】第１実施形態におけるインデックスを作成する過程を説明するための説明図である。
【図９】第１実施形態におけるインデックスを作成する過程を説明するための説明図である。
【図１０】生成された木構造インデックスの一例を示す説明図である。
【図１１】リーフノードに対応するデータが複数存在する場合におけるリンクの張り方を説明するための説明図である。
【図１２】第１実施形態における検索の手順を説明するためのフローチャートである。
【図１３】第１実施形態における検索の手順を説明するための説明図である。
【図１４】類似データの検索においてリンクを辿る様子を説明するための説明図である。
【図１５】第２実施形態において検索開始点を取得する方法を説明するためのフローチャートである。
【図１６】第２実施形態において検索開始点を取得する方法を説明するための説明図である。
【図１７】第３実施形態におけるラベル付与装置の概略的な構成を説明するためのブロック図である。
【図１８】第３実施形態におけるラベル付与方法の概略的な手順を説明するためのフローチャートである。
【図１９】既存ベクトルデータに対応するラベルを登録する手順の一例を説明するためのフローチャートである。
【図２０】ラベルに対応付けられる画像の一例を示す説明図である。
【図２１】データベースに登録された既存ベクトルデータとラベルとの対応関係を概念的に説明するための説明図である。
【図２２】新規ベクトルデータに対するラベルを決定するための手順を説明するためのフローチャートである。
【図２３】新規ベクトルデータに対するラベルを決定するための手順を説明するための説明図である。
【図２４】新規ベクトルデータに対するラベルを決定するための手順を説明するための説明図である。
【図２５】第４実施形態におけるラベル付与方法を説明するためのフローチャートである。
【図２６】第４実施形態におけるラベル付与方法を説明するための説明図である。
【図２７】第４実施形態におけるラベル付与方法を説明するための説明図である。
【図２８】第５実施形態におけるラベル付与方法を説明するためのフローチャートである。
【図２９】第６実施形態におけるラベル付与方法を説明するためのフローチャートである。
【図３０】第６実施形態におけるラベル付与方法を説明するための説明図である。
【図３１】第７実施形態におけるラベル付与方法を説明するためのフローチャートである。
【図３２】第７実施形態におけるラベル付与方法を説明するための説明図である。
【図３３】第９実施形態におけるラベル付与方法において、既存ベクトルデータとラベルとの対応関係を設定する手順を説明するためのフローチャートである。
【図３４】第１０実施形態におけるベクトルデータ検索装置の動作を説明するためのフローチャートである。
【図３５】第１０実施形態におけるベクトルデータ検索装置の動作を説明するための説明図である。
【図３６】第１０実施形態におけるベクトルデータ検索装置の動作を説明するための説明図である。図（ａ）〜（ｃ）は、取得されたデータのリストが更新される様子を示す。
【図３７】第１１実施形態におけるベクトルデータ検索装置の概略を示すブロック図である。
【図３８】第１１実施形態におけるベクトルデータ検索装置の動作を説明するためのフローチャートである。
【図３９】第１１実施形態におけるベクトルデータ検索装置の動作を説明するための説明図である。
【図４０】第１２実施形態におけるベクトルデータ検索装置の動作を説明するためのフローチャートである。
【図４１】第１２実施形態におけるベクトルデータ検索装置の動作を説明するための説明図である。
【符号の説明】
【０２９０】
１  サーバ（ベクトルデータ検索装置）
１１  ベクトルデータ生成部
１２  インデックス生成部
１３  検索部
１３１  開始点取得部
１３２  インデックス検索部
１４  データベース
１４１  ベクトルデータＤＢ
１４２  多次元インデックスＤＢ
１４３  グラフインデックスＤＢ
１４５  ラベルＤＢ
１６  ラベル生成部
１８  インデックス再構成部
２  クライアント端末（表示装置）
３  ネットワーク
５０  任意の点
５１  検索元データ（新規データ）
５２  検索開始点
５３  検索半径
５４  終了判定半径
６１・７１〜７４  類似データ
１００  サーバ（ラベル付与装置）
【図１】
2010079871.tif 000004
【図２】
2010079871.tif 000005
【図３】
2010079871.tif 000006
【図４】
2010079871.tif 000007
【図５】
2010079871.tif 000008
【図６】
2010079871.tif 000009
【図７】
2010079871.tif 000010
【図８】
2010079871.tif 000011
【図９】
2010079871.tif 000012
【図１０】
2010079871.tif 000013
【図１１】
2010079871.tif 000014
【図１２】
2010079871.tif 000015
【図１３】
2010079871.tif 000016
【図１４】
2010079871.tif 000017
【図１５】
2010079871.tif 000018
【図１６】
2010079871.tif 000019
【図１７】
2010079871.tif 000020
【図１８】
2010079871.tif 000021
【図１９】
2010079871.tif 000022
【図２１】
2010079871.tif 000023
【図２２】
2010079871.tif 000024
【図２３】
2010079871.tif 000025
【図２５】
2010079871.tif 000026
【図２６】
2010079871.tif 000027
【図２７】
2010079871.tif 000028
【図２８】
2010079871.tif 000029
【図２９】
2010079871.tif 000030
【図３０】
2010079871.tif 000031
【図３１】
2010079871.tif 000032
【図３２】
2010079871.tif 000033
【図３３】
2010079871.tif 000034
【図３４】
2010079871.tif 000035
【図３５】
2010079871.tif 000036
【図３６】
2010079871.tif 000037
【図３７】
2010079871.tif 000038
【図３８】
2010079871.tif 000039
【図３９】
2010079871.tif 000040
【図４０】
2010079871.tif 000041
【図４１】
2010079871.tif 000042
【図２０】
2010079871.tif 000043
【図２４】
2010079871.tif 000044
【手続補正書】
【提出日】平成21年2月6日(2009.2.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１３
【補正方法】変更
【補正の内容】
【請求項１３】
前記最遠の前記既存ベクトルデータよりも前記新規ベクトルデータに近い既存ベクトルデータが検索された場合には、この近い既存ベクトルデータを含み、かつ、前記新規ベクトルデータに対して近い順に既定の検索数までの既存ベクトルデータの中から、最遠の既存ベクトルデータを選択することにより、前記新規ベクトルデータと既存ベクトルデータとの最大の距離を更新する構成とされている
請求項１０〜１２のいずれか１項に記載のベクトルデータ検索装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
（項目１３）
前記最遠の前記既存ベクトルデータよりも前記新規ベクトルデータに近い既存ベクトルデータが検索された場合には、この近い既存ベクトルデータを含み、かつ、前記新規ベクトルデータに対して近い順に既定の検索数までの既存ベクトルデータの中から、最遠の既存ベクトルデータを選択することにより、前記新規ベクトルデータと既存ベクトルデータとの距離を更新する構成とされている
項目１０〜１２のいずれか１項に記載のベクトルデータ検索装置。