(57)【特許請求の範囲】
【請求項１】
複数のデータ点と、これらのデータ点の間に張られたリンクとを有するグラフインデックスを格納するインデックスＤＢと、
リンク削除の対象となるデータ点である対象点と、前記対象点から所定範囲内のデータ点を除く他のデータ点である周囲点とのリンクを除去するリンク削減部と、
前記周囲点に最も近いデータ点を、前記対象点から検索するデータ検索部と、
検索によって得られたデータ点である検索データ点と、前記周囲点との間に、新たにリンクを生成するリンク生成部と
を備える、グラフインデックス再構成装置。
【請求項２】
前記所定範囲とは、前記対象点からの距離、及び／又は、前記対象点から近い順の個数である、請求項１に記載のグラフインデックス再構成装置。
【請求項３】
前記検索は、前記対象点から前記周囲点に向けて前記リンクを辿ることにより行われる、請求項１又は２に記載のグラフインデックス再構成装置。
【請求項４】
前記データ検索部は、前記周囲点が複数である場合において、前記対象点から前記周囲点への検索を並行して行う構成となっている、請求項１〜３のいずれか１項に記載のグラフインデックス再構成装置。
【請求項５】
前記リンク生成部は、前記検索によって前記周囲点自体が検索された場合には、当該周囲点に対する新たなリンクを生成しない構成となっている、請求項１〜４のいずれか１項に記載のグラフインデックス再構成装置。
【請求項６】
複数のデータ点と、これらのデータ点の間に張られたリンクとを有するグラフインデックスの再構成を、処理部と記憶部とを用いて行う方法であって、前記記憶部は、前記グラフインデックスを格納しており、
リンク削除の対象となるデータ点である対象点と、前記対象点から所定範囲内のデータ点を除く他のデータ点である周囲点とのリンクを、前記処理部により除去するステップと、
前記周囲点に最も近いデータ点を、前記対象点から、前記処理部により検索するステップと、
検索によって得られたデータ点である検索データ点と、前記周囲点との間に、新たなリンクを、前記処理部により生成するステップと
を備える、グラフインデックス再構成方法。
【請求項７】
請求項６に記載の各ステップをコンピュータで実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ検索のために用いられるグラフインデックスを再構成するための装置及び方法に関するものである。特に、本発明は、特定のノードにリンクが集中したグラフインデックスにおいて、リンクを張り直すための技術に関するものである。
【背景技術】
【０００２】
本願の出願人による下記特許文献１には、グラフ構造型のインデックス（すなわちグラフインデックス）を辿ることで、リーフノードに対応するベクトルデータを検索できる技術が記載されている。ここで、ベクトルデータは、例えば画像データの特徴量を表すものである。なお、リーフノードは、データの集合（クラスタ）に対応する。ただし、特定のクラスタが空集合である場合も存在する。
【０００３】
しかしながら、この技術では、特定のノードにリンクが集中することがある。すると、検索効率が劣化するおそれがある。
【０００４】
特定ノードにリンクが集中した状態を図１（ａ）に示す。この例では、ノードＮ１に対する、他のノードからのリンクが集中している。
【０００５】
以下、このような場合におけるリンク再構成方法の例を説明する。以下の説明では、ノードを「点」と称する。
【０００６】
まず、リンクを削減する対象となる点Ｎ１から近い距離にある５つの点Ｎ２ａ〜Ｎ２ｅまでのリンクを、残すリンクとして決定する。次に、その他の点、すなわち、点Ｎ１から遠い距離にある点Ｎ３ａ〜Ｎ３ｊへのリンクを逐一張り直す処理を行う。ここで、リンクを張り直す際に、単純に古いリンクを削除すると、孤立点や孤立したグラフが生成されてしまう。そこで、まず、リンクを張り直す点（例として点Ｎ３ｅ）と、リンクを残した全ての点Ｎ２ａ〜Ｎ２ｅ及び対象点Ｎ１との距離を求め、リンクを張り直す点Ｎ３ｅに最も近い点Ｎ２ｄと、当該の点Ｎ３ｅとをリンクする（図１（ｂ）参照）。ただし、既にリンクが存在している場合もあるので、存在している場合にはリンクしない。次に、対象点と点Ｎ３ｅと間の元のリンクを削除する。点Ｎ３ｅに最も近い点が結局、元の対象点である場合は、リンクの張替えをしない。この処理を、リンクを張り直すべき全ての点Ｎ３ａ〜Ｎ３ｊについて同様に操作をすることで、リンクを張り替えて、特定ノードに集まるリンクの数を削減することができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１０−７９８７１号公報（例えば図１０）
【発明の概要】
【発明が解決しようとする課題】
【０００８】
このようにすることで、対象点Ｎ１に集まるリンクの数を削減できることが多いが、超多次元の特徴量空間では、次のような現象が発生することがある。すなわち、リンクを削除した点（前記の例では点Ｎ３ｅ）から、全ての点Ｎ２ａ〜Ｎ２ｅ及び対象点Ｎ１との距離を算出すると、対象点Ｎ１が最も近い場合が発生する。これがまれに発生するのであれば何ら問題ないが、超多次元の特徴量空間の場合には、ほとんどの点Ｎ３ａ〜Ｎ３ｊから最も近い点が対象点Ｎ１であるということが頻繁に起きる。この場合には、結局、元のリンクを削減することができなくなる。また、対象点Ｎ１を除く点Ｎ２ａ〜Ｎ２ｅの中で最も近い点に、点Ｎ３ｅからのリンクを張り替えることも考えられる。しかし、この場合にも、やはり特定の点（点Ｎ２ａ〜Ｎ２ｅのいずれか一つ）にリンクが集中してしまうことがある。そこでさらに、この集中したリンクを削除しようとすると、次に、元の対象点Ｎ１にリンクが集中するという現象が発生することがある。つまり、大量のリンクが二つの点を往復するような状況となる可能性がある。
【０００９】
本発明は、前記した状況に鑑みてなされたものである。本発明の主な目的は、特定のノードへのリンクの集中を避けるために、リンクを効果的に削減し、かつ、ノードの孤立を避けることが可能な装置又は方法を提供することである。
【課題を解決するための手段】
【００１０】
本発明は、以下のいずれかの項目に記載の構成とされている。
【００１１】
（項目１）
複数のデータ点と、これらのデータ点の間に張られたリンクとを有するグラフインデックスを格納するインデックスＤＢと、
リンク削除の対象となるデータ点である対象点と、前記対象点から所定範囲内のデータ点を除く他のデータ点である周囲点とのリンクを除去するリンク削減部と、
前記周囲点に最も近いデータ点を、前記対象点から検索するデータ検索部と、
検索によって得られたデータ点である検索データ点と、前記周囲点との間に、新たにリンクを生成するリンク生成部と
を備える、グラフインデックス再構成装置。
【００１２】
周囲点に最も近いデータ点は、対象点から周囲点に向けて検索を行うことで取得できる。
【００１３】
（項目２）
前記所定範囲とは、前記対象点からの距離、及び／又は、前記対象点から近い順の個数である、項目１に記載のグラフインデックス再構成装置。
【００１４】
（項目３）
前記検索は、前記対象点から前記周囲点に向けて前記リンクを辿ることにより行われる、項目１又は２に記載のグラフインデックス再構成装置。
【００１５】
（項目４）
前記データ検索部は、前記周囲点が複数である場合において、前記対象点から前記周囲点への検索を並行して行う構成となっている、項目１〜３のいずれか１項に記載のグラフインデックス再構成装置。
【００１６】
（項目５）
前記リンク生成部は、前記検索によって前記周囲点自体が検索された場合には、当該周囲点に対する新たなリンクを生成しない構成となっている、項目１〜４のいずれか１項に記載のグラフインデックス再構成装置。
【００１７】
（項目６）
複数のデータ点と、これらのデータ点の間に張られたリンクとを有するグラフインデックスの再構成を、処理部と記憶部とを用いて行う方法であって、前記記憶部は、前記グラフインデックスを格納しており、
リンク削除の対象となるデータ点である対象点と、前記対象点から所定範囲内のデータ点を除く他のデータ点である周囲点とのリンクを、前記処理部により除去するステップと、
前記周囲点に最も近いデータ点を、前記対象点から、前記処理部により検索するステップと、
検索によって得られたデータ点である検索データ点と、前記周囲点との間に、新たなリンクを、前記処理部により生成するステップと
を備える、グラフインデックス再構成方法。
【００１８】
（項目７）
項目６に記載の各ステップをコンピュータで実行させるためのコンピュータプログラム。
【００１９】
このコンピュータプログラムは、適宜な記録媒体（例えばＣＤ−ＲＯＭやＤＶＤディスクのような光学的な記録媒体、ハードディスクやフレキシブルディスクのような磁気的記録媒体、あるいはＭＯディスクのような光磁気記録媒体）に格納することができる。このコンピュータプログラムは、インターネットなどの通信回線を介して伝送されることができる。
【発明の効果】
【００２０】
本発明によれば、特定のノードへのリンクの集中を避けるために、リンクを効果的に削減し、かつ、ノードの孤立を避けることが可能となる。
【図面の簡単な説明】
【００２１】
【図１】従来のリンク数削減方法を示す説明図である。図（ａ）は、リンク削減前の状態を示す。図（ｂ）は、リンクを削減して新たにリンクを張り直した状態を示す。
【図２】本発明の一実施形態におけるグラフインデックス再構成装置が使用されるネットワーク構成の一例を説明するための説明図である。
【図３】本発明の一実施形態におけるグラフインデックス再構成装置で使用される機能要素を示すブロック図である。
【図４】本発明の一実施形態におけるグラフインデックス再構成方法を説明するためのフローチャートである。
【図５】本発明の一実施形態におけるグラフインデックス再構成方法を説明するための説明図である。図（ａ）はリンク削減前、図（ｂ）はリンク削減後、図（ｃ）は検索処理中、図（ｄ）はリンク張り直し後の状態をそれぞれ示している。
【発明を実施するための形態】
【００２２】
（本実施形態の構成）
本発明の第１実施形態に係るグラフインデックス再構成装置を説明する前提として、この再構成装置を含む検索システム全体の構成を、図２を参照しながら説明する。この検索システムは、ネットワーク１と、ユーザ端末２と、検索用のサーバ３とを主要な要素として備えている。
【００２３】
ネットワーク１は、例えばインターネットである。ネットワーク１は、この例では、ユーザ端末２とサーバ３とを接続して、これらの間での通信を可能にするものである。
【００２４】
ユーザ端末２は、ネットワーク１を介してサーバ３に接続することにより、所定の検索を行うことができるようになっている。例えば、ユーザ端末２は、ユーザ端末２に表示されたブラウザを介してユーザの指示を入力することにより、所望の検索が行えるようになっている。
【００２５】
サーバ３は、検索部３１と、データベース３２と、グラフインデックス再構成部３３とを備えている。グラフインデックス再構成部３３は、本発明のグラフインデックス再構成装置の一部を構成するものである。
【００２６】
検索部３１は、ユーザ端末２から入力された検索キーに対応して、データベース３２を用いて、所定の検索を行う機能を有している。
【００２７】
データベース３２は、インデックスＤＢ３２１と、ベクトルデータＤＢ３２２とを備えている。データベース３２は、本発明における記憶部の一例に対応している。
【００２８】
インデックスＤＢ３２１は、複数のデータ点と、これらのデータ点の間に張られたリンクとを有するグラフインデックスを格納するものである。データ点は、ベクトルデータＤＢ３２２に格納されたベクトルデータに対応する。グラフインデックスは、ユーザから入力された検索クエリに対応してデータを効率的に検索するための情報である。
【００２９】
ベクトルデータＤＢ３２２は、検索対象であるベクトルデータを格納するためのデータベースである。ベクトルデータＤＢ３２２に格納されるベクトルデータは、例えば画像データの特徴量を示すデータである。ただし、ベクトルデータは、音声データなど、他の種類のデータに対応するものであってもよい。
【００３０】
グラフインデックス再構成部３３は、リンク削減部３３１と、データ検索部３３２と、リンク生成部３３３とを備えている（図３参照）。なお、図３では、データベース３２の一部を構成するインデックスＤＢ３２１も記載している。
【００３１】
リンク削減部３３１は、リンク削除の対象となるデータ点である対象点と、前記対象点から所定範囲内のデータ点を除く他のデータ点である周囲点とのリンクを除去する構成となっている。
【００３２】
データ検索部３３２は、周囲点に最も近いデータ点を、対象点から検索する構成となっている。具体的には、データ検索部３３２は、対象点を出発点として、ここから周囲点に向けて検索する。データ検索部３３２は、サーバ３における検索部３１と兼用であってもよいが、この明細書では、別途準備されているものとして説明する。
【００３３】
リンク生成部３３３は、検索によって得られたデータ点である検索データ点と、周囲点との間に、新たにリンクを生成する構成となっている。
【００３４】
グラフインデックス再構成部３３における具体的な処理内容については後述する。
【００３５】
なお、本実施形態における再構成部３３とインデックスＤＢ３２１とが、本発明のグラフインデックス再構成装置の一実施形態に対応している。
【００３６】
（本実施形態の動作）
ついで、前記したグラフインデックス再構成部３３の具体的な動作を、図４及び図５をさらに参照しながら説明する。
【００３７】
（図４のステップＳＡ−１）
まず、リンク削除の対象となるデータ点である対象点４を決定する（図５（ａ）参照）。対象点４は、他のデータ点からのリンクが集中している点とする。対象点４の決定は、人間により行うことも可能であるし、あるいは、リンク数などの所定の閾値を用いて自動的に決定することも可能である。ただし、全てのデータ点を対象点として、リンクを張り直すことも可能である。
【００３８】
また、ベクトルデータを新たにデータベースに登録する場合に、このベクトルデータの追加により新たに形成するリンクにより、そのリンク元のデータ点のリンク数が特定のリンク数の閾値を超えたときに、そのリンク元のデータ点をリンク削減の対象点として、データ登録処理の延長としてリンク削減をすることとしてもよい。
【００３９】
ついで、対象点４から所定範囲内のデータ点５１〜５５を除く他のデータ点である周囲点６１〜７０とのリンクを、リンク削減部（すなわち処理部）３３１により除去する（図５（ｂ）参照）。ここで、所定範囲を、例えば、対象点４からの既定の距離に基づいて決定することができる。あるいは、所定範囲を、対象点４から近い順の個数に基づいて決定することができる。他の方法により所定範囲を決定することも可能である。
【００４０】
（図４のステップＳＡ−２）
ついで、リンクを張り直すべき周囲点を決定する。この例では、周囲点６５に対するリンクを張り直す処理を説明する。他の周囲点についても同様に処理することが可能である。
【００４１】
ついで、データ検索部（すなわち処理部）３３２により、対象点４から、周囲点６５に向けて検索を開始する（図５（ｃ）参照）。これにより、データ検索部３３２は、周囲点６５自体か、あるいは、それに最も近いデータ点を、後述のように、検索により取得することができる。
【００４２】
対象点４から周囲点６５に向けて検索する手法としては、前記した特許文献１に記載の手法を用いることができる。
【００４３】
あるいは、検索を、対象点４から周囲点６５に向けてリンクを順次辿ることにより行うことも可能である。ここで、リンクを順次辿るとは、次のような手順を意味する。すなわち、まず、対象点４から直接のリンクが張られたデータ点のうち、周囲点６５に近いデータ点を特定する。次に、この特定したデータ点からリンクが張られたデータ点のうち、周囲点６５に近いデータ点を更に特定する。この手順を繰り返し、周囲点６５に近いと判定した特定のデータ点からリンクが張られたデータ点が、いずれも、この特定のデータ点よりも周囲点６５から遠い場合、辿る作業を終了し、最終的に特定したデータ点を、周囲点６５に最も近いデータ点とすることができる。このようにすると、特許文献１の手法で検索する場合に比べて、処理手順を簡略化できるという利点がある。また、リンクを順次辿る手順では対象点４から移動できない場合（つまり対象点４が最も周囲点６５に近い場合）に限り、特許文献１の手法で検索するという処理も可能である。また、それ以外の他の検索方法を用いることも可能である。
【００４４】
（図４のステップＳＡ−３）
ついで、データ検索部（すなわち処理部）３３２は、検索の結果、目指した周囲点６５に到達したかどうかを判断する。
【００４５】
（図４のステップＳＡ−４）
ステップＳＡ−３において、目指した周囲点６５に到達したと判断された場合は、新たなリンクは生成せず、次のステップＳＡ−６に移る。
【００４６】
（図４のステップＳＡ−５）
ステップＳＡ−３において、目指した周囲点６５に到達しなかったと判断された場合は、リンク生成部（すなわち処理部）３３３は、検索によって得られた最も近いデータ点である検索データ点８２と、周囲点６５との間に、新たなリンク９１を生成する（図５（ｄ）参照）。図示の例では、検索データ点８２は、データ点５３とデータ点８１との間、及び、データ点８１とデータ点８２との間の既存のリンクを経由して検索されているものである。
【００４７】
このようにして、新たなリンク９１を介して、対象点４と周囲点６５との間のリンクを再度生成することができる。しかも、以上の説明から分かるように、この場合には、新たなリンクを生成しても、対象点４にリンクが集中することはない。つまり、対象点４への直接にリンクしなくても、対象点４から周囲点６５へのリンクの接続ができる。このため、本実施形態の手法によれば、各データ点に張られるリンク数を均一化できると考えられる。
【００４８】
（図４のステップＳＡ−６）
ついで、リンク削減部（すなわち処理部）３３１は、ステップＳＡ−１において対象点４とのリンクが削除された、未処理の他の周囲点が存在するかどうか判断する。存在する場合はステップＳＡ−２に戻り、当該他の周囲点（例えば周囲点６１）について、前記と同様の手順を行う。未処理の他の周囲点が存在しない場合は、グラフインデックス再構成の処理を終了する。
【００４９】
なお、前記した説明では、データ検索部３３２が、周囲点６５に向けて検索を始め、その後、順次他の周囲点を検索することとした。しかしながら、周囲点が複数存在する場合において、対象点から周囲点への検索を並行して行うことも可能である。このようにすると、検索作業を短時間で行うことができるという利点がある。
【００５０】
以上のように、本実施形態によれば、多次元のベクトルデータをグラフ構造により構成したグラフインデックスにおいて、特定のノードへのリンクの集中を避けるために、グラフ構造を用いた検索によって、リンク削減対象のデータ点（対象点）と、リンクを削除した周囲点との間に確実にリンクを張り直すことができる。このため、リンクの削除によってリンク切れを防止し、ノードの孤立を避けることが可能となる。
【００５１】
また、単に削減対象のデータ点（対象点）に近い周囲点の間でリンクを張り直すのではなく、グラフ構造を利用して周囲点に向けて探索して行き、周囲点に近い点と周囲点との間でリンクを張り直す。このため、削減対象のデータ点（対象点）に元々リンクされている周囲点の間でリンクの集中が繰り返し発生してしまうことを防止できる。
【００５２】
また、前記した実施形態では、対象点４から所定範囲内のデータ点５１〜５５を除く他のデータ点である周囲点６１〜７０とのリンクを、リンク削減部（すなわち処理部）３３１により除去している。そして、ここでの所定範囲を、対象点４からの既定の距離に基づいて決定している。これにより、本実施形態では、対象点４から近いデータ点については既存のリンクを利用し、対象点４から遠いデータ点については、前記したリンク張り直し作業を行うことができる。これにより、対象点４に対して再度のリンク集中が起きる可能性を減らすことができる。所定範囲を、対象点４から近い順の個数に基づいて決定した場合も、同様の利点を発揮できる。
【００５３】
また、本実施形態では、ステップＳＡ−３において、目指した周囲点６５に到達したと判断された場合は、新たなリンクは生成しない。これにより、同じデータ点の間で重複してリンクが生成されるという冗長性を回避できる。
【００５４】
前記した各実施形態の動作は、コンピュータに適宜のコンピュータソフトウエアを組み込むことにより実施することができる。
【００５５】
なお、本発明の内容は、前記実施形態に限定されるものではない。本発明は、特許請求の範囲に記載された範囲内において、具体的な構成に対して種々の変更を加えうるものである。
【００５６】
例えば、前記した各構成要素は、機能ブロックとして存在していればよく、独立したハードウエアとして存在しなくても良い。また、実装方法としては、ハードウエアを用いてもコンピュータソフトウエアを用いても良い。さらに、本発明における一つの機能要素が複数の機能要素の集合によって実現されても良く、本発明における複数の機能要素が一つの機能要素により実現されても良い。
【００５７】
また、機能要素は、物理的に離間した位置に配置されていてもよい。この場合、機能要素どうしがネットワークにより接続されていても良い。グリッドコンピューティングにより機能を実現し、あるいは機能要素を構成することも可能である。
【符号の説明】
【００５８】
１  ネットワーク
２  ユーザ端末
３  サーバ
３１  検索部
３２  データベース
３２１  インデックスＤＢ（グラフインデックス再構成装置）
３２２  ベクトルデータＤＢ
３３  グラフインデックス再構成部（グラフインデックス再構成装置）
３３１  リンク削減部
３３２  データ検索部
３３３  リンク生成部
４  対象点
６１〜７０  対象点とのリンクを削除した周囲点
５１〜５５  対象点から所定範囲内のデータ点
８１  データ点
８２  検索データ点
９１  新たに生成したリンク
【図１】
0005292384.tif 000002
【図２】
0005292384.tif 000003
【図３】
0005292384.tif 000004
【図４】
0005292384.tif 000005
【図５】
0005292384.tif 000006