(57)【要約】  本発明における情報処理装置は、複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた各インデックスデータを生成するインデックス生成手段と、各インデックスデータを記憶したサーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段と、を備え、上記インデックス生成手段は、リファレンス点情報に対応するインデックスデータが記憶されたサーバの通信コスト情報に基づいて、特定のデータ点情報に対して関連付けを行うリファレンス点情報の選択を行う。
2012137422.tif 000002
【特許請求の範囲】
【請求項１】
複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた前記各インデックスデータを生成するインデックス生成手段と、
前記各インデックスデータを記憶した前記サーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段と、を備え、
前記インデックス生成手段は、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、特定の前記データ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理装置。
【請求項２】
請求項１に記載の情報処理装置であって、
前記インデックス生成手段は、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、前記特定のデータ点情報に対して関連付ける予め設定された数の前記リファレンス点情報を選択する、
情報処理装置。
【請求項３】
請求項１又は２に記載の情報処理装置であって、
前記インデックス生成手段は、前記特定のデータ点情報に対して前記リファレンス点情報の候補となる前記他のデータ点情報であるリファレンス点候補情報のうち、一の前記リファレンス点候補情報を除き、残りの前記リファレンス点候補情報の１つを基準として他の前記リファレンス点候補情報との距離を座標とした座標点を算出すると共に、前記残りのリファレンス点候補情報のそれぞれを基準としたときに算出される各前記座標点を頂点とする多面体の体積を算出し、この算出した体積と、前記除かれた一のリファレンス点候補情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報と、に基づいて、前記特定のデータ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理装置。
【請求項４】
請求項３に記載の情報処理装置であって、
前記インデックス生成手段は、前記算出した体積に、前記除かれた一のリファレンス点候補情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報を加算した値が、他の前記リファレンス点候補情報を除いたときの値と比較して最も大きい値である場合の前記除かれた一のリファレンス点候補情報を、前記特定のデータ点情報に対して関連付けを行う前記リファレンス点情報から除いて当該リファレンス情報の選択を行う、
情報処理装置。
【請求項５】
請求項１乃至４のいずれかに記載の情報処理装置であって、
前記通信コスト記憶手段は、前記各インデックスデータを記憶した前記サーバ毎における前記通信コスト情報として、各サーバ間において通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶し、
前記インデックス生成手段は、前記特定のデータ点情報に対応する前記インデックスデータが記憶された前記サーバと、前記リファレンス点情報の候補となる前記他のデータ点情報に対応する前記インデックスデータが記憶された前記サーバと、の間における前記通信コスト情報に基づいて、前記特定のデータ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理装置。
【請求項６】
請求項５に記載の情報処理装置であって、
前記通信コスト記憶手段は、前記各インデックスデータを記憶した前記サーバ毎における前記通信コスト情報として、各サーバ間における処理能力差に応じて生じる当該各サーバ間において通信する際にかかる予め設定されたコストを表す情報を記憶する、
情報処理装置。
【請求項７】
請求項１乃至６のいずれかに記載の情報処理装置であって、
所定の前記データ点情報に対応する前記インデックスデータを記憶するインデックス記憶手段と、
前記検索対象データに対する検索要求を受け付ける検索要求受付手段と、
前記インデックス記憶手段に記憶された前記インデックスデータ内から、予め設定された基準に従って前記検索要求受付手段にて受け付けた前記検索要求に対応する前記データ点情報を検索する検索手段と、
前記検索手段にて前記インデックス記憶手段に記憶された前記インデックスデータ内に、予め設定された基準に従って前記検索要求受付手段にて受け付けた前記検索要求に対応する前記データ点情報がない場合に、前記検索要求を他の情報処理装置に転送する検索要求転送手段と、
を備えた情報処理装置。
【請求項８】
各インデックスデータを記憶したサーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段を備えた情報処理装置に、
複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた前記各インデックスデータを生成するインデックス生成手段を実現させると共に、
前記インデックス生成手段は、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、特定の前記データ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
ことを実現させるためのプログラム。
【請求項９】
各インデックスデータを記憶したサーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段を備えた情報処理装置にて、
複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた前記各インデックスデータを生成する際に、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、特定の前記データ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理方法。
【請求項１０】
請求項９に記載の情報処理方法であって、
前記各インデックスデータを生成する際に、前記特定のデータ点情報に対して前記リファレンス点情報の候補となる前記他のデータ点情報であるリファレンス点候補情報のうち、一の前記リファレンス点候補情報を除き、残りの前記リファレンス点候補情報の１つを基準として他の前記リファレンス点候補情報との距離を座標とした座標点を算出すると共に、前記残りのリファレンス点候補情報のそれぞれを基準としたときに算出される各前記座標点を頂点とする多面体の体積を算出し、この算出した体積と、前記除かれた一のリファレンス点候補情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報と、に基づいて、前記特定のデータ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置にかかり、特に、検索対象データのメタデータが複数のサーバに分散記憶されている場合において、各メタデータのインデックスを作成する機能を有する情報処理装置に関する。
【背景技術】
【０００２】
近年、画像データや音声データ等のメディアデータを扱うシステムが広く利用されている。計算機の処理能力向上や、解析技術の進展、および監視システム等での安全性に対する要求等、機能面、要件面からも需要が高まっている。そのようなメディアデータ解析システムでは、メディアデータから人のいる領域を抽出したり、音声データをテキストデータに変換したりするなどの処理が行われる。【０００３】
メディアデータを扱うシステムで課題となる機能として、類似データの検索が挙げられる。メディアデータ解析システムでは、例えば類似画像の検索や、音声の類似性の判定等のユースケースにおいて、大量に蓄積されているデータから、クエリデータと類似しているデータを取り出す必要がある。ここでの類似データとは、個々のデータ種別によって定義され、判定方法や類似性のしきい値は様々である。【０００４】
メディアデータのような高次元データに対する類似データの検索では、より低い次元でよく用いられるツリー構造のインデックスでは問題となることがある。多次元のインデックスとして、KD-Treeのようなツリー型のインデックス構造がよく用いられる。ツリー構造のインデックスでは、ログオーダで検索を行なうことができ、次元が大きくない場合には十分効果的である。しかし、高次元データに対してツリー構造のインデックスを用いた場合、その分割した領域がスパース（sparse）になり、効率的な検索を行なうことができないことが問題となる。この問題は、例えば非特許文献３にて指摘されている。【０００５】
また、非特許文献１では、高次元データの類似検索のため、リング構造を持ったインデックスであるMLRインデックスを提案している。このMLRインデックスは、データ点と距離関数で定義される距離空間にて用いることができる。このインデックス構造を使うと、クエリ点に対して、ある確率で類似データを効率的に見つけることができる。【０００６】
そして、上記MLRインデックスでは、各リング点が、距離に応じた階層的なリング構造を持つ。そのリング階層は、中心から離れるとそのリングの半径が指数的に増えていくように構成されている。リング中には、非特許文献１の図１のように（ｋ＋１）個のリング点を持つ。リング点のうち、ｋ個のリング点は、比較／検索対象となるリファレンス点である。類似点を検索する際には、これらのリファレンス点との距離を比較するようにして検索が行なわれる。【０００７】
一方、リファレンス点以外の１個のリング点は、スペア点である。スペア点は、リファレンス点とは異なり検索時に比較対象とはならないが、リング点からリファレンス点の選択を行なう際に、その候補となる点である。このような構造を持つことにより、クエリ点に対する類似点を検索する際に、ログオーダでの検索を可能としている。【０００８】
このリング構造インデックスを用いた検索は、次のように行なわれる。まず、ランダムにデータ点が選択されて、そのデータ点が持つリング構造インデックスが選択される。次に、クエリ点とデータ点との距離が計算され、その距離から、クエリ点が含まれるリングを選択する。そして、クエリ点と、選択したリング内の各リファレンス点との距離を計算し、クエリ点に最も近いリファレンス点を最近傍リファレンス点として選択する。この時、最近傍リファレンス点とクエリ点との距離が、中心にあるデータ点とクエリ点との距離よりも大きい場合には、データ点を類似点として返却する。一方、リファレンス点とクエリ点の距離が一定以内であれば、そのリファレンス点を類似点として返却する。また、上記以外の場合には、最近傍のリファレンス点をデータ点として選択し、探索処理を続ける。距離は徐々に近づいていくので、データ点が有限である場合には収束することがわかる。【０００９】
そして、この検索に用いるリング構造インデックスを作成するには、リングに含まれるｋ個のリファレンス点の選択方法が重要となる。例えば、リファレンス点の選択方法が悪くて、クエリ点に対して十分に近いリファレンス点が見つからない場合には、類似点が見つからないことになってしまう。そのため、任意のクエリ点に対して、最近傍のリファレンス点との距離が小さくなるように、（ｋ＋１）個のリング点から、ｋ個のリファレンス点を選択する必要がある。これを実現するために、非特許文献２では、リファレンス点ｉとリファレンス点ｊの距離を「dij」としたときに、[di1,di2,...,dik]というｋ次元の点ｋ個と、原点とからなるｋ次元多面体の体積を最大化するように、リファレンス点を選択する。なお、このインデックスの構造は、非特許文献２で用いられている構造を元にしており、インデックスの探索方法や構築方法は、非特許文献２にて詳しく述べられている。【００１０】
一方、メディアデータは、近年、その対象とするデータ量が増え続けており、スケールアウトによるデータベースの拡張が必要となる。メディアデータは、単体でもデータ量が大きいため、サーバの能力を拡張させる、すなわちスケールアップによる大量データへの対応では、対応するサーバが無いか、もしくは対応するサーバがあったとしても、非常に高価なものとなってしまう。そのため、複数のサーバを並列に動作させる、すなわちスケールアウトによる大量データへの対応が必要である。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Rahul Malik, Sangkyum Kim, Xin Jin, Chandrasekar Ramachandran,Jiawei Han, Indranil Gupta, and Klara Nahrstedt、"MLR-index: An Index Structurefor Fast and Scalable Similarity Search in High Dimensions"、SSDBM 2009Proceedings of the 21st International Conference on Scientific and StatisticalDatabase Management、 Springer-Verlag Berlin, Heidelberg、June 2-4, 2009、pp167 - 184
【非特許文献２】Bernard Wong, Aleksandrs Slivkins, Emin Gun Sirer、"Meridian: ALightweight Network Location Service without Virtual Coordinates"、SIGCOMM '05Proceedings of the 2005 conference on Applications, technologies,architectures, and protocols for computer communications、ACM New York, NY,USA、August22-26, 2005、pp85-96
【非特許文献３】Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft、"When isnearest neighbor meaningful?"、ICDT '99 Proceedings of the 7th International Conference on DatabaseTheory、Springer-Verlag London, UK、January 10-12, 1999、Lecture Notes in Computer Science, 1999, Volume 1540/1999、pp217-235
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、非特許文献３で提案されているインデックスをそのまま複数サーバに分散させた場合には、サーバ間の通信が増加し、データ検索時の効率が低下する、という問題が生じる。これは、そのままデータを分散させた場合に、リファレンス点が他のサーバに保持されていると、リファレンス点を辿る際に通信が発生し、通信コストが増えてしまうためである。【００１３】
このため、本発明の目的は、上述した課題である、検索対象となるデータが複数サーバ間で分散させたシステムにおいて、データ検索の効率低下という問題を解決することができる情報処理装置を提供することにある。
【課題を解決するための手段】
【００１４】
本発明の一形態である情報処理装置は、
複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた前記各インデックスデータを生成するインデックス生成手段と、
前記各インデックスデータを記憶した前記サーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段と、を備え、
前記インデックス生成手段は、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、特定の前記データ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
という構成を取る。【００１５】
また、本発明の他の形態であるプログラムは、
各インデックスデータを記憶したサーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段を備えた情報処理装置に、
複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた前記各インデックスデータを生成するインデックス生成手段を実現させると共に、
前記インデックス生成手段は、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、特定の前記データ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
ことを実現させるためのプログラムである。【００１６】
また、本発明の他の形態である情報処理方法は、
各インデックスデータを記憶したサーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段を備えた情報処理装置にて、
複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた前記各インデックスデータを生成する際に、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、特定の前記データ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
という構成を取る。
【発明の効果】
【００１７】
本発明は、以上のように構成されることにより、検索対象となるデータが複数サーバ間で分散させたシステムにおいて、データ検索の効率の向上を図ることができる。
【図面の簡単な説明】
【００１８】
【図１】本発明における情報処理システムの全体構成を示すブロック図である。
【図２】図１に開示した検索クライアントとデータ保持サーバの構成を示す機能ブロック図である。
【図３】本発明で用いるインデックスの構成を示す模式図である。
【図４】図１に開示したデータ保持サーバによるインデックス構築処理の動作を示すフローチャートである。
【図５Ａ】図１に開示した検索クライアントによる検索処理の動作を示すフローチャートである。
【図５Ｂ】図１に開示したデータ保持サーバによるインデックスを用いた検索処理の動作を示すフローチャートである。
【図６Ａ】インデックス作成処理の一例を説明するための図である。
【図６Ｂ】リファレンス作成処理の一例を説明するための図である。
【発明を実施するための形態】
【００１９】
本発明の第１の実施形態を、図１乃至図６を参照して説明する。図１乃至図３は、情報処理システムの構成を説明するための図であり、図４乃至図６は、情報処理システムの動作を説明するための図である。
【００２０】
なお、本実施形態における情報処理システムは、画像データや音声データ等のメディアデータの類似検索を行うシステムであり、検索対象となるデータのインデックスが複数のサーバに分散して記憶されている構成のものを説明する。但し、本発明における情報処理システムは、メディアデータの類似検索を行うシステムであることに限定されず、いかなるデータの検索を行うシステムであってもよい。
【００２１】
［構成］
図１に示すように、本実施形態における情報処理システムは、プログラム制御により動作する検索クライアント（中央処理装置；プロセッサ；データ処理装置）１００と、プログラム制御により動作する複数のデータ保持サーバ（中央処理装置；プロセッサ；データ処理装置）２００と、その検索クライアント１００と複数のデータ保持サーバ２００との間で通信を行なうためのネットワーク３００から構成される。
【００２２】
検索クライアント１００は、ネットワーク３００に接続された情報処理端末であり、図２に示すように、サーバ情報保持手段１０１と、サーバ選択手段１０２と、検索要求発行手段１０３とを備えている。これらの手段は、それぞれ概略次のように動作する。
【００２３】
上記サーバ情報保持手段１０１は、複数のデータ保持サーバ２００のアドレスなどのデータである要求先データを保持する。サーバ情報所持手段１０１は、この保持している複数のデータ保持サーバ２００の要求先データを、サーバ選択手段１０２からの要求に応じて渡す。
【００２４】
上記サーバ選択手段１０２は、サーバ情報保持手段１０１の持つ複数のデータ保持サーバ２００の要求先データを受け取り、その中から適切なデータ保持サーバ２００の要求先データを選択する。適切なデータ保持サーバ２００の要求先データを選択する方法は、複数のデータ保持サーバ２００に対して、均等に検索クライアントからの要求が届くようにすればよい。例えば、データ保持サーバ２００の負荷状況によって、最も負荷が小さいデータ保持サーバ２００を選択してもよいし、また例えば、ランダムにデータ保持サーバ２００を選択するようにしてもよい。
【００２５】
上記検索要求発行手段１０３は、入力されたクエリとの類似データの検索要求を、サーバ選択手段１０２によって選択されたデータ保持サーバ２００の要求先に対して発行する。この検索要求発行手段１０３から発行された検索要求に対しては、後述するデータ保持サーバ２００から、検索して発見された類似データ、もしくは、検索失敗との結果、が返却されるため、その結果を入力元に返却する。
【００２６】
次に、データ保持サーバ２００の構成について説明する。データ保持サーバ２００は、演算装置と記憶装置とを備えた情報処理装置であり、図２に示すように、検索要求受付手段２０１と、検索手段２０２と、リング構造保持手段２０３と、データ保持手段２０４と、検索要求転送手段２０５と、リング構造計算手段２０６と、転送コスト保持手段２０７とから構成される。なお、データ保持サーバ２００は、後述するように、データ保持手段２０４に検索対象となるデータ本体を記憶し、リング構造保持手段２０３に検索の際に用いるインデックスを記憶しているが、上記リング構造計算手段２０６や転送コスト保持手段２０７は、データ本体やインデックスが記憶されている同一の情報処理装置に装備されている必要はなく、他の情報処理装置に装備されていてもよい。
【００２７】
上記検索要求受付手段２０１は、検索クライアント１００、または、他のデータ保持サーバ２００から送信された検索要求を受け取り、類似データの検索を検索手段２０２に依頼する。また、検索要求受付手段２０１は、検索手段２０２から検索結果が得られた後に、検索要求の要求元である、検索クライアント１００、または、他のデータ保持サーバ２００に結果を返却する。
【００２８】
上記検索手段２０２は、検索要求受付手段２０１から受け取った類似データの検索要求に従い、類似データ検索を実行する。このとき、検索手段２０２は、リング構造保持手段２０３が保持する類似データ検索のためのインデックスを用いて類似データの検索を行い、例えば、予め設定された基準に従って、検索要求に含まれる条件と類似するデータの検索を行う。そして、リング構造保持手段２０３が保持する類似データ検索のためのインデックスを用いて類似データが見つかった場合には、データ保持手段２０４から対象となるデータを取得し、結果として返却する。なお、詳しい検索処理フローは、後の動作説明時に説明する。
【００２９】
上記リング構造保持手段２０３（インデックス記憶手段）は、類似検索のためのインデックスとしてリング構造インデックスを保持する。リング構造保持手段２０３が保持するリング構造インデックスは、リング構造計算手段２０６によって作成される。そして、リング構造保持手段２０３が保持するリング構造インデックスは、検索手段２０２によって、検索要求に対応する類似データを検索する際に利用される。
【００３０】
上記データ保持手段２０４は、リング構造保持手段２０３によって管理されるリング構造インデックスが指し示すデータ本体、つまり、リング構造インデックスの中心に位置する後述するデータ点が参照するデータ本体を保持する。ここで、上記リング構造保持手段２０３が管理しているインデックスは、あくまでメタデータであることが多く、求められているデータ本体とは異なることがある。そのため、データ保持手段２０４では、リング構造保持手段２０３によって管理されるインデックスが指し示すデータのデータ本体を保持し、検索手段２０２の要求に応じて、そのデータ本体を返却する。
【００３１】
上記検索要求転送手段２０５は、後述するように、検索要求に対応する類似データとなるリファレンス点を中心としたリング構造インデックスを、上記検索手段２０２にて検索処理を行った自己のサーバではない他のデータ保持サーバ２００が持つ場合に、当該他のデータ保持サーバ２００に検索要求を転送する。ここで、１つのデータ保持サーバ２００のリング構造保持手段２０３が管理するインデックスは、全てのデータに対するインデックスを持っているわけではない。従って、他のデータ保持サーバ２００が保持するデータのインデックスに関しては、その検索要求を転送し、類似検索の処理を他のデータ保持サーバ２００で続行する必要がある。このとき、リング構造保持手段２０３が管理するインデックスには、他のデータ保持サーバ２００が保持するデータについてどの他のデータ保持サーバ２００が保持しているかという関係を表す情報を持っているため、その関係情報を用いて、検索要求を転送する。
【００３２】
上記リング構造計算手段２０６（インデックス生成手段）は、後述するように、検索対象データ毎にリング構造インデックスを作成し、リング構造保持手段２０３に渡す。このリング構造計算手段２０６は、類似検索のためのリング構造インデックスを、データ、データ間の距離を計算する距離関数、および、複数のデータ保持サーバ２００間での処理の転送コスト、から計算する。ここで、リング構造インデックスを計算する対象となるデータは、自サーバ２００のデータ保持手段２０４にて保持されているものであり、このデータのメタデータに対して予め設定された基準に基づく距離が予め設定された範囲内に位置する他のデータを関連付けたインデックスを計算する。また、データ間の距離を計算する距離関数は、ベクトル空間におけるユークリッド距離を用いてもよいし、データ種別によって変更するように構成しても構わない。この計算手順は、処理フローの説明にて述べる。
【００３３】
上記転送コスト保持手段２０７（通信コスト記憶手段）は、リング構造計算手段２０６が類似検索のためのリング構造インデックスを計算するために用いる、複数のデータ保持サーバ２００間での処理の際に生じる予め設定された転送コストを表すコスト値を保持している。この複数のデータ保持サーバ２００間での処理のコスト値は、定数値でも良いし、データ保持サーバ２００のネットワーク接続構成を反映して個別のデータ保持サーバ２００間毎に異なる値を定義してもよい。例えば、コスト値は、データ保持サーバ２００間で通信した場合にかかる通信時間、ある基準値に対する遅延時間などである。このとき、通信時間や遅延時間は、各データ保持サーバ２００間におけるネットワーク接続構成や処理能力差に応じた値であってもよい。
【００３４】
次に、図３には、類似検索のためのリング構造インデックスを示す。図３を参照すると、類似検索のためのリング構造インデックスは、中心にあって黒丸で表されるデータ点４０１と、周辺にあって斜線の点で表されるリファレンス点４０２と、周辺にあって白丸で表されるスペア点４０３と、データ点４０１を中心とした同心円状に描かれているリング４１１，４１２，４１３とからなる。なお、ここでは、二次元に各点の配置をマッピングしているが、図示する都合上の表現であり、必ずしも二次元データに限定する必要はない。
【００３５】
上記データ点４０１は、検索対象データに対応する点情報であり、当該検索対象データに対応するリング構造インデックスの中心に位置する。そして、データ点４０１は、対応する検索対象データの特徴を表す情報として距離空間におけるメタデータと、データ本体への参照データとを持つ。ここでは、データ本体への参照データ等については説明しない。
【００３６】
また、上記リファレンス点４０２とスペア点４０３は、上記データ点４０１とは異なる他の検索対象データに対応する点情報であり、上記同様に、その検索対象データの特徴を表すメタデータと、データ本体への参照データを持つ。そして、リファレンス点４０２とスペア点４０３は、データ点４０１との距離、つまり、データ点４０１に対するメタデータの距離に応じて、リング構造インデックス内にマッピングされている。例えば、データ点４０１に対して予め設定された基準に基づく距離が予め設定された範囲内に位置するリファレンス点４０２とスペア点４０３が、リング構造インデックス内にマッピングされ、中心に位置するデータ点４０１に関連付けられている。また、リファレンス点４０２とスペア点４０３は、自己の点を中心としたリング構造インデックスが記憶されているデータ保持サーバ２００の情報を記憶しており、他の点との距離計算を行なうためのデータを保持している。なお、リファレンス点４０２とスペア点４０３を合わせて、リング点と呼ぶ。
【００３７】
上記リング４１１、リング４１２、リング４１３は、データ点４０１から一定の距離を持つ点の集合である。これらのリングは、データ点４０１に近いリングから数えた数を「ｉ」とした場合、その距離がαｓ（ｉ−１）となるように配置されている。すなわち、最もデータ点４０１に近いリングであるリング４１１のデータ点４０１からの距離はαであり、次にデータ点４０１に近いリングであるリング４１２のデータ点４０１からの距離はαｓであり、そして、リング４１３のデータ点４０１からの距離はαｓ２である。
【００３８】
なお、各リング４１１，４１２，４１３に挟まれたリファレンス点４０２の数は、予め設定された数である「ｋ」個以内に制限される。例えば、「ｋ」の数が「４」として設定されている場合、リング４１２とリング４１３に挟まれた領域内に含まれるリファレンス点４０２は、最大でも４個となる。そして、リファレンス点４０２は、リング構造インデックスを作成する際に、当該リング構造インデックスの中心となるデータ点４０１に対してリファレンス点として保持するべきかが判断され、リング構造インデックス内の各リング間の領域内で「ｋ」個になるように調整される。また、各リング４１１，４１２，４１３に挟まれたスペア点４０３は、例えば、「１」個に制限される。これは、リング構造インデックスを作成する際に、リファレンス点として選択されなかった点をスペア点とし、また、その際に「１」個となるように調整される。
【００３９】
以上のようなリング構造インデックス（インデックスデータ）が、検索対象データ毎に当該検索対象データに対応するデータ点を中心としてそれぞれ生成される。そして、各リング構造インデックスは、対応する検索対象データのデータ本体と共に、各データ保持サーバ２００に分散されて記憶されている。
【００４０】
［動作］
次に、図４及び図５のフローチャートを参照して、上述した情報処理システムの全体の動作について詳細に説明する。動作のフローは、図４が示すリング構造インデックスの計算フローと、図５Ａ，５Ｂが示す類似データの検索フローからなる。各処理フローは独立しているため、個別に説明を行なう。
【００４１】
まず、リング構造計算手段２０６が、リング構造計算要求を受信する（ステップＡ１０１）。リング構造計算要求を受信したリング構造計算手段２０６は、保持しているデータに対して処理を開始する。この処理は、各データ点を中心した各リング構造インデックスが持つリファレンス点４０２の選択を行なう処理である。なお、以下では、一つのデータ点に対する処理のみを記述するが、以下の処理が、自己であるデータ保持サーバ２００が記憶している検索対象データのメタデータ等を含むデータ点毎に行われ、各リング構造インデックスを生成して記憶保持する。
【００４２】
続いて、リング構造計算手段２０６は、データ点４０１を中心とした全てのリング間でリファレンス点４０２の選択処理を行ったかを確認する（ステップＡ１０２）。もし、このときに、全てのリング間で計算を行なってリファレンス点４０２を選択していた場合には、そのデータ点４０１に対するリング構造インデックス作成処理を終了する（ステップＡ１１０）。
【００４３】
一方、ステップＡ１０２で、対象となるデータ点４０１を中心とした全てのリング間でリファレンス点４０２の選択処理を完了していない場合には、未計算のリング間を選択し（ステップＡ１０３）、そのリングに含まれるリング点間の距離を全て計算する（ステップＡ１０４）。ここで、リファレンス点候補の数が「ｋ」個に絞れている場合には、そのリファレンス点情報を保存して、ステップＡ１０２に戻る（ステップＡ１０５）。
【００４４】
ステップＡ１０５でリファレンス点候補が「ｋ」個に絞れていない場合には、各リファレンス点候補間の距離から構成される多面体の体積が大きくなるよう、リファレンス点候補を選択する。具体的には、リファレンス点候補ｉとリファレンス点候補ｊとの距離を「dij」とし、リファレンス点候補の数をｎとしたとき、そのｎ次元空間上の点piの座標を[di0,di1,di2,...,dij,...,din]とする。ここで、dii=0である。これにより、各リファレンス点候補ｉに対してpiを定義することができ、このpiと原点から構成されるｎ次元空間上の多面体の体積を、最大化することを考える。各リファレンス点の距離が小さくなると多面体の体積も小さくなるため、できるだけ大きな多面体を構成するようにリファレンス点を選択することで、リング間上のどこにクエリ点があったとしても、そのクエリ点に近いリファレンス点を見つけやすくなる。できるだけ大きな多面体の体積を構成するリファレンス点の候補集合を見つけるためには、全てのリファレンス点候補の組み合わせに対して、多面体の体積を計算する必要がある。但し、このように組み合わせを全て計算すると計算量が大きくなってしまうために、本実施形態では、以下のような単純化した方法を用いる。
【００４５】
まず、ｎ個のリファレンス点候補の内、各リファレンス点候補を外した際の（ｎ−１）次元空間上の多面体の体積をそれぞれ求める（ステップＡ１０５）。具体的には、１つのリファレンス点piを外した場合、（ｎ−１）次元空間の点pjの座標は、[dj0,dj1,...,dj(i-1),dj(i+1),...,djn]となる。このような点から多面体を構成し、その体積を求めることとなる。ここで、リファレンス点候補ｉを外した際の多面体の体積を、「V(-i)」とする。
【００４６】
次に、各計算された多面体の体積に、リファレンス点候補から外したリング点に対応するコスト値を加算する（ステップＡ１０７）。ここで、コスト値は、リング点に対応するリング構造インデックスデータが記憶されたデータ保持サーバ２００に応じて事前に設定され、上述したように転送コスト保持手段２０７に記憶されている値である。そして、リファレンス点候補ｉに対するコスト値を「ci」とすると、上記で求める値は「V(-i)+ci」である。このとき、コスト値「ci」として、データ点４０１に対応するデータ保持サーバ２００とリファレンス点候補ｉに対応するデータ保持サーバ２００との間における値が記憶されている場合には、かかる値を用いる。
【００４７】
そして、ステップＡ１０７の結果である「V(-i)+ci」の値が最も大きいリファレンス点候補ｉを、リファレンス候補から外す（ステップＡ１０８）。ここで外されるリファレンス点候補は、その点を外した際に多面体の体積に与える影響が少ない点であるか、その点に対するコストが高い点である、という性質を持つ。その結果として、参照コストが小さく、かつ任意のクエリ点と近い点がみつかりやすいような、リファレンス点の集合が選択され、リファレンス点候補の数が「ｋ」個に絞れると（ステップＡ１０５）、そのリファレンス点情報を保存する（ステップＡ１０９）。
【００４８】
次に、図５Ａ，５Ｂのフローチャートを参照して、類似データを検索する処理フローを示す。類似データを検索するフローは、検索クライアント１００におけるフロー（図５Ａ）と、データ保持サーバ２００におけるフロー（図５Ｂ）から構成される。
【００４９】
まず、検索を始める際に、サーバ情報保持手段１０１からサーバリストを取得する（ステップＢ１０１）。そして、サーバ選択手段１０２が、ステップＢ１０１にて取得したサーバリストから、検索要求を発行するデータ保持サーバ２００を選択する（ステップＢ１０２）。
【００５０】
次に、検索要求発行手段１０３は、ステップＢ１０２で選択されたデータ保持サーバ２００に検索要求を発行する（ステップＢ１０３）。最後に、検索要求発行手段１０３は、発行した検索要求の結果を、データ保持サーバ２００から受信する（ステップＢ１０４）。
【００５１】
次に、データ保持サーバ２００における類似データ検索フローを、図５Ｂを参照して説明する。データ保持サーバ２００が検索要求を受信すると（ステップＣ１０１）、リング構造保持手段２０３にて保持されているリング構造インデックスから、ランダムにデータ点を選択する（ステップＣ１０２）。
【００５２】
データ点が選択されると、選択されたデータ点とクエリ点との距離を計算する（ステップＣ１０３）。距離の計算方法は、事前に決まっているとする。この距離を「ｄ」と置いたとき、「αｓ（ｉ−１）＜ｄ≦αｓｉ」となるリングを選択する（ステップＣ１０４）。これは、クエリ点が含まれるリングを選択することである。
【００５３】
そして、選択中のリングに含まれるｋ個のリファレンス点を全て取得し、クエリ点とその選択中のリングに含まれるｋ個の全てのリファレンス点との距離を計算し、最もクエリ点と近いリファレンス点を選択する（ステップＣ１０５）。
【００５４】
ここで、クエリ点と選択されたリファレンス点の距離が、クエリ点とデータ点との距離よりも大きいかどうかを比較する（ステップＣ１０６）。もし、クエリ点と選択されたリファレンス点の距離が、クエリ点とデータ点との距離よりも大きい場合には、クエリ点は、リファレンス点よりもデータ点と近いということになり、データ点を類似データとして検索処理を終了する（ステップＣ１０９）。一方、クエリ点と選択されたリファレンス点の距離が、クエリ点とデータ点との距離以下の場合には、そのクエリ点と選択されたリファレンス点との距離がしきい値以下であるかを判断する（ステップＣ１０７）。その結果、しきい値以下であった場合には、選択中のリファレンス点を類似データとして検索処理を終了する（ステップＣ１１０）。一方、しきい値以下でなかった場合には、探索処理を継続する必要があり、その場合には、選択中のリファレンス点をデータ点として、再度処理を行なう。このとき、選択したデータ点は、別のデータ保持サーバ２００に存在する可能性があるため、その場合には、その他のデータ保持サーバ２００に処理要求を転送する（ステップＣ１０８）。
【００５５】
以上のように、本実施形態における情報処理装置では、リング構造インデックスを構築する際に、サーバ間の処理の転送コストを考慮してインデックスを構築するように処理を行なうため、検索処理を行なう際にサーバ間での処理の転送コストを減らすことができ、検索処理時間を短くすることができる。
【００５６】
［実施例］
次に、上述した情報処理システムを用いた具体的な実施例を説明する。なお、ここでは、リング構造インデックスの作成処理についてのみを説明することとする。
【００５７】
図６Ａ，６Ｂには、本実施例で用いるデータ表現を示す。図６Ａに示すデータ点Ｅ１０１は、ｎ個のデータである。この例では、各データは、３０次元のベクトルデータとして表されている。このベクトルデータに対し、ユークリッド距離を距離関数として用いるとする。また、k=3、l=4とする。
【００５８】
リング構造インデックスの作成時に、上述したステップＡ１０３でリングが選択されると、リング点間距離を算出する。ここで、リング点ｉとリング点ｊの距離を「dij」と置く。以降では、７個のリング点の中から、３個のリファレンス点を選択する処理を行なうこととする。
【００５９】
上述したステップＡ１０６では、各リング点の距離をその次元の値として持つ点から構成される多次元多面体の体積を求める。ここで、データ点１からデータ点７までがリファレンス候補のリング点として選択されているとき、図６ＢのＥ１０３では、データ点７を外した際の多面体を構成する原点以外の頂点を示している。例えば、点p1は、１次元目の値が「０」で、二次元目の値が「d1 2」であることを示している。このような点から構成される多面体の体積は、一般的に知られている多次元多面体の体積を求める方法で求める、あるいは、近似することができる。ここで、データ点ｉを除いた多次元多面体の体積を「V(-i)」と表わすこととする。例えば、データ点７を除いた多次元多面体の体積は、「V(-7)」となる。
【００６０】
次に、各データ点に対して、そのデータ点を除いた距離で定義される点を頂点とする多次元多面体の体積が求まった後、その体積とコスト値を足し合わせ、最大となるデータ点を選択する。図６ＡのＥ１０２には、その一般的な式を示す。かかる式に基づいてＥ１０２を満たすような「ｉ」を選択し、ここではデータ点５が選択されたとすると、このデータ点５をリファレンス点の候補から外す。
【００６１】
続いて、データ点５をリファレンス点の候補から外すと、当初７個あったリファレンス点候補は６個となる。図６ＢのＥ１０４には、データ点５がリファレンス点の候補から外された後に、データ点７を外した際の多面体を構成する原点以外の頂点を示している。
【００６２】
以上のように処理を行ない、リファレンス点の候補を３個に絞ると、リファレンス点の選択処理が終わる。このような処理を全てのリング間、および全てのデータ点に対して行ない、リング構造インデックスを生成する
【００６３】
＜付記＞
上記実施形態の一部又は全部は、以下の付記のようにも記載されうる。以下、本発明における情報処理装置等の構成の概略を説明する。但し、本発明は、以下の構成に限定されない。
【００６４】
（付記１）
複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた前記各インデックスデータを生成するインデックス生成手段と、
前記各インデックスデータを記憶した前記サーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段と、を備え、
前記インデックス生成手段は、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、特定の前記データ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理装置。
【００６５】
（付記２）
付記１に記載の情報処理装置であって、
前記インデックス生成手段は、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、前記特定のデータ点情報に対して関連付ける予め設定された数の前記リファレンス点情報を選択する、
情報処理装置。
【００６６】
（付記３）
付記１又は２に記載の情報処理装置であって、
前記インデックス生成手段は、前記特定のデータ点情報に対して前記リファレンス点情報の候補となる前記他のデータ点情報であるリファレンス点候補情報のうち、一の前記リファレンス点候補情報を除き、残りの前記リファレンス点候補情報の１つを基準として他の前記リファレンス点候補情報との距離を座標とした座標点を算出すると共に、前記残りのリファレンス点候補情報のそれぞれを基準としたときに算出される各前記座標点を頂点とする多面体の体積を算出し、この算出した体積と、前記除かれた一のリファレンス点候補情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報と、に基づいて、前記特定のデータ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理装置。
【００６７】
（付記４）
付記３に記載の情報処理装置であって、
前記インデックス生成手段は、前記算出した体積に、前記除かれた一のリファレンス点候補情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報を加算した値が、他の前記リファレンス点候補情報を除いたときの値と比較して最も大きい値である場合の前記除かれた一のリファレンス点候補情報を、前記特定のデータ点情報に対して関連付けを行う前記リファレンス点情報から除いて当該リファレンス情報の選択を行う、
情報処理装置。
【００６８】
（付記５）
付記１乃至４のいずれかに記載の情報処理装置であって、
前記通信コスト記憶手段は、前記各インデックスデータを記憶した前記サーバ毎における前記通信コスト情報として、各サーバ間において通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶し、
前記インデックス生成手段は、前記特定のデータ点情報に対応する前記インデックスデータが記憶された前記サーバと、前記リファレンス点情報の候補となる前記他のデータ点情報に対応する前記インデックスデータが記憶された前記サーバと、の間における前記通信コスト情報に基づいて、前記特定のデータ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理装置。
【００６９】
（付記６）
付記５に記載の情報処理装置であって、
前記通信コスト記憶手段は、前記各インデックスデータを記憶した前記サーバ毎における前記通信コスト情報として、各サーバ間における処理能力差に応じて生じる当該各サーバ間において通信する際にかかる予め設定されたコストを表す情報を記憶する、
情報処理装置。
【００７０】
（付記７）
付記１乃至６のいずれかに記載の情報処理装置であって、
所定の前記データ点情報に対応する前記インデックスデータを記憶するインデックス記憶手段と、
前記検索対象データに対する検索要求を受け付ける検索要求受付手段と、
前記インデックス記憶手段に記憶された前記インデックスデータ内から、予め設定された基準に従って前記検索要求受付手段にて受け付けた前記検索要求に対応する前記データ点情報を検索する検索手段と、
前記検索手段にて前記インデックス記憶手段に記憶された前記インデックスデータ内に、予め設定された基準に従って前記検索要求受付手段にて受け付けた前記検索要求に対応する前記データ点情報がない場合に、前記検索要求を他の情報処理装置に転送する検索要求転送手段と、
を備えた情報処理装置。
【００７１】
（付記８）
各インデックスデータを記憶したサーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段を備えた情報処理装置に、
複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた前記各インデックスデータを生成するインデックス生成手段を実現させると共に、
前記インデックス生成手段は、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、特定の前記データ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
ことを実現させるためのプログラム。
【００７２】
（付記９）
付記８に記載のプログラムであって、
前記インデックス生成手段は、前記特定のデータ点情報に対して前記リファレンス点情報の候補となる前記他のデータ点情報であるリファレンス点候補情報のうち、一の前記リファレンス点候補情報を除き、残りの前記リファレンス点候補情報の１つを基準として他の前記リファレンス点候補情報との距離を座標とした座標点を算出すると共に、前記残りのリファレンス点候補情報のそれぞれを基準としたときに算出される各前記座標点を頂点とする多面体の体積を算出し、この算出した体積と、前記除かれた一のリファレンス点候補情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報と、に基づいて、前記特定のデータ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
プログラム。
【００７３】
（付記１０）
各インデックスデータを記憶したサーバ毎に、当該サーバに対して通信する際にかかる予め設定されたコストを表す通信コスト情報を記憶した通信コスト記憶手段を備えた情報処理装置にて、
複数のサーバに分散されて記憶される各インデックスデータであり、検索対象データの特徴を表すメタデータを含むデータ点情報毎に、当該データ点情報に対する予め設定された基準に基づく距離が予め設定された範囲内に位置する他の前記データ点情報をリファレンス点情報として関連付けた前記各インデックスデータを生成する際に、前記リファレンス点情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報に基づいて、特定の前記データ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理方法。
【００７４】
（付記１１）
付記１０に記載の情報処理方法であって、
前記各インデックスデータを生成する際に、前記特定のデータ点情報に対して前記リファレンス点情報の候補となる前記他のデータ点情報であるリファレンス点候補情報のうち、一の前記リファレンス点候補情報を除き、残りの前記リファレンス点候補情報の１つを基準として他の前記リファレンス点候補情報との距離を座標とした座標点を算出すると共に、前記残りのリファレンス点候補情報のそれぞれを基準としたときに算出される各前記座標点を頂点とする多面体の体積を算出し、この算出した体積と、前記除かれた一のリファレンス点候補情報に対応する前記インデックスデータが記憶された前記サーバの前記通信コスト情報と、に基づいて、前記特定のデータ点情報に対して関連付けを行う前記リファレンス点情報の選択を行う、
情報処理方法。
【００７５】
以上、上記各実施形態を参照して本願発明を説明したが、本願発明は、上述した実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明の範囲内で当業者が理解しうる様々な変更をすることができる。
【００７６】
なお、本発明は、日本国にて２０１１年４月５日に特許出願された特願２０１１−０８３３８６の特許出願に基づく優先権主張の利益を享受するものであり、当該特許出願に記載された内容は、全て本明細書に含まれるものとする。
【符号の説明】
【００７７】
１００  検索クライアント
１０１  サーバ情報保持手段
１０２  サーバ選択手段
１０３  検索要求発行手段
２００  データ保持サーバ
２０１  検索要求受付手段
２０２  検索手段
２０３  リング構造保持手段
２０４  データ保持手段
２０５  検索要求転送手段
２０６  リング構造計算手段
２０７  転送コスト保持手段
３００  ネットワーク
【図１】
2012137422.tif 000003
【図２】
2012137422.tif 000004
【図３】
2012137422.tif 000005
【図４】
2012137422.tif 000006
【図５Ａ】
2012137422.tif 000007
【図５Ｂ】
2012137422.tif 000008
【図６Ａ】
2012137422.tif 000009
【図６Ｂ】
2012137422.tif 000010
【国際調査報告】
2012137422.tif 000011
2012137422.tif 000012
2012137422.tif 000013
2012137422.tif 000014