(57)【要約】【課題】インデックス数を検索コストが最小となるように動的に調整することにより検索システム性能の向上を図ることができる検索システムを提供する。【解決手段】キーワードを指定すると、該キーワードを含むレコードを返す処理を実行する複数のインデックス手段と、インデックス手段の処理結果を集約する１以上の集約装置とが木構造状に接続された検索システムにおいて、インデックス手段と集約装置から、検索コストを計算するために必要なパラメータを取得するパラメータ取得手段と、パラメータに基づいて、計算した検索コストを最小化するインデックス数を求めるコスト計算手段と、インデックス手段と集約装置に対して、コスト計算手段によって求めたインデックス数を実現するように、レコードの移動と木構造の変更を指示する構成変更指示手段とを備える。【選択図】図１
2011113205.tif 000002
【特許請求の範囲】
【請求項１】
キーワードを指定すると、該キーワードを含むレコードを返す処理を実行する複数のインデックス手段と、前記インデックス手段の処理結果を集約する１以上の集約装置とが木構造状に接続された検索システムにおいて、
前記インデックス手段と前記集約装置から、検索コストを計算するために必要なパラメータを取得するパラメータ取得手段と、
前記パラメータに基づいて、計算した検索コストを最小化するインデックス数を求めるコスト計算手段と、
前記インデックス手段と前記集約装置に対して、前記コスト計算手段によって求めた前記インデックス数を実現するように、レコードの移動と木構造の変更を指示する構成変更指示手段と
を備えることを特徴とする検索システム。
【請求項２】
前記構成変更指示手段は、
直前に求められた前記インデックス数と、新たに求められた前記インデックス数の差が所定の条件を満たした場合のみに、前記インデックス手段と前記集約装置に対して、レコードの移動と木構造の変更を指示することを特徴とする請求項１に記載の検索システム。
【請求項３】
キーワードを指定すると、該キーワードを含むレコードを返す処理を実行する複数のインデックス手段と、前記インデックス手段の処理結果を集約する１以上の集約装置とが木構造状に接続された検索システムに接続される検索コスト計算装置であって、
前記インデックス手段と前記集約装置から、検索コストを計算するために必要なパラメータを取得するパラメータ取得手段と、
前記パラメータに基づいて、計算した検索コストを最小化するインデックス数を求めるコスト計算手段と、
前記インデックス手段と前記集約装置に対して、前記コスト計算手段によって求めた前記インデックス数を実現するように、レコードの移動と木構造の変更を指示する構成変更指示手段と
を備えることを特徴とする検索コスト計算装置。
【請求項４】
前記構成変更指示手段は、
直前に求められた前記インデックス数と、新たに求められた前記インデックス数の差が所定の条件を満たした場合のみに、前記インデックス手段と前記集約装置に対して、レコードの移動と木構造の変更を指示することを特徴とする請求項３に記載の検索コスト計算装置。
【請求項５】
キーワードを指定すると、該キーワードを含むレコードを返す処理を実行する複数のインデックス手段と、前記インデックス手段の処理結果を集約する１以上の集約装置とが木構造状に接続された検索システムに、パラメータ取得手段と、コスト計算手段と、構成変更指示手段とを備える検索コスト計算装置が接続され、前記検索コスト計算装置が、前記検索システムの構成を変更して検索コストを最小化する検索コスト計算方法であって、
前記パラメータ取得手段が、前記インデックス手段と前記集約装置から、検索コストを計算するために必要なパラメータを取得するパラメータ取得ステップと、
前記コスト計算手段が、前記パラメータに基づいて、計算した検索コストを最小化するインデックス数を求めるコスト計算ステップと、
前記構成変更指示手段が、前記インデックス手段と前記集約装置に対して、前記コスト計算ステップによって求めた前記インデックス数を実現するように、レコードの移動と木構造の変更を指示する構成変更指示ステップと
を有することを特徴とする検索コスト計算方法。
【請求項６】
前記構成変更指示ステップは、
直前に求められた前記インデックス数と、新たに求められた前記インデックス数の差が所定の条件を満たした場合のみに、前記インデックス手段と前記集約装置に対して、レコードの移動と木構造の変更を指示することを特徴とする請求項５に記載の検索コスト計算方法。
【請求項７】
キーワードを指定すると、該キーワードを含むレコードを返す処理を実行する複数のインデックス手段と、前記インデックス手段の処理結果を集約する１以上の集約装置とが木構造状に接続された検索システムに、検索コスト計算装置が接続され、前記検索コスト計算装置上のコンピュータに前記検索システムの構成を変更して検索コストを最小化する処理を行わせる検索コスト計算プログラムであって、
前記インデックス手段と前記集約装置から、検索コストを計算するために必要なパラメータを取得するパラメータ取得ステップと、
前記パラメータに基づいて、計算した検索コストを最小化するインデックス数を求めるコスト計算ステップと、
前記インデックス手段と前記集約装置に対して、前記コスト計算ステップによって求めた前記インデックス数を実現するように、レコードの移動と木構造の変更を指示する構成変更指示ステップと
を前記コンピュータに行わせることを特徴とする検索コスト計算プログラム。
【請求項８】
前記構成変更指示ステップは、
直前に求められた前記インデックス数と、新たに求められた前記インデックス数の差が所定の条件を満たした場合のみに、前記インデックス手段と前記集約装置に対して、レコードの移動と木構造の変更を指示することを特徴とする請求項７に記載の検索コスト計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索を行うシステムにおいてインデックス数の最適化する検索システム、検索コスト計算装置、検索コスト計算方法及び検索コスト計算プログラムに関する。
【背景技術】
【０００２】
従来から、情報検索を行う際に、情報が格納されたレコード検索を高速にするために、インデックスと呼ばれるデータ構造を用いることが知られている。さらに、レコード数が多いときには、データ集合を複数のインデックスに分割し、各インデックスを個別に検索し、その結果を木構造を用いて集約することが一般的に行われる（例えば、特許文献１参照）。
【０００３】
インデックスを用いたデータ構造の一例として、木構造のインデックスツリーによるＢ−ｔｒｅｅ（Balanced Tree）などがよく知られており、データベースやファイルシステムなどで利用されている。木構造は、空でない接点（ノード：ｎｏｄｅ）の集合と辺（枝：ｅｄｇｅ）で構成された、木の形をしたデータ構造を有している。最上位層のノードを根（ｒｏｏｔ）、最下位層のノードを葉（ｌｅａｆ）と呼び、これらが相互にポインタによってリンクしている。Ｂ−Ｔｒｅｅでは、ルートから各リーフまでの階層数をすべて同じにする木構造を有しているのが特徴である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】西田圭介，「Ｇｏｏｇｌｅを支える技術」技術評論社，ｐｐ．５４−５９，２００８
【発明の概要】
【発明が解決しようとする課題】
【０００５】
検索対象のレコード数が多いときには、データ集合を複数のインデックスに分割することにより、検索コストを複数の装置に分散できるため有用である。しかしながら、検索システムの性能は、分割するインデックス数の影響を受けるため、最適なインデックス数を決定して、インデックスを分割しなければならないという問題がある。
【０００６】
本発明は、このような事情に鑑みてなされたもので、インデックス数を検索コストが最小となるように動的に調整することにより検索システム性能の向上を図ることができる検索システム、検索コスト計算装置、検索コスト計算方法及び検索コスト計算プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、キーワードを指定すると、該キーワードを含むレコードを返す処理を実行する複数のインデックス手段と、前記インデックス手段の処理結果を集約する１以上の集約装置とが木構造状に接続された検索システムにおいて、前記インデックス手段と前記集約装置から、検索コストを計算するために必要なパラメータを取得するパラメータ取得手段と、前記パラメータに基づいて、計算した検索コストを最小化するインデックス数を求めるコスト計算手段と、前記インデックス手段と前記集約装置に対して、前記コスト計算手段によって求めた前記インデックス数を実現するように、レコードの移動と木構造の変更を指示する構成変更指示手段とを備えることを特徴とする。
【０００８】
本発明は、前記構成変更指示手段は、直前に求められた前記インデックス数と、新たに求められた前記インデックス数の差が所定の条件を満たした場合のみに、前記インデックス手段と前記集約装置に対して、レコードの移動と木構造の変更を指示することを特徴とする。
【０００９】
本発明は、キーワードを指定すると、該キーワードを含むレコードを返す処理を実行する複数のインデックス手段と、前記インデックス手段の処理結果を集約する１以上の集約装置とが木構造状に接続された検索システムに接続される検索コスト計算装置であって、前記インデックス手段と前記集約装置から、検索コストを計算するために必要なパラメータを取得するパラメータ取得手段と、前記パラメータに基づいて、計算した検索コストを最小化するインデックス数を求めるコスト計算手段と、前記インデックス手段と前記集約装置に対して、前記コスト計算手段によって求めた前記インデックス数を実現するように、レコードの移動と木構造の変更を指示する構成変更指示手段とを備えることを特徴とする。
【００１０】
本発明は、前記構成変更指示手段は、直前に求められた前記インデックス数と、新たに求められた前記インデックス数の差が所定の条件を満たした場合のみに、前記インデックス手段と前記集約装置に対して、レコードの移動と木構造の変更を指示することを特徴とする。
【００１１】
本発明は、キーワードを指定すると、該キーワードを含むレコードを返す処理を実行する複数のインデックス手段と、前記インデックス手段の処理結果を集約する１以上の集約装置とが木構造状に接続された検索システムに、パラメータ取得手段と、コスト計算手段と、構成変更指示手段とを備える検索コスト計算装置が接続され、前記検索コスト計算装置が、前記検索システムの構成を変更して検索コストを最小化する検索コスト計算方法であって、前記パラメータ取得手段が、前記インデックス手段と前記集約装置から、検索コストを計算するために必要なパラメータを取得するパラメータ取得ステップと、前記コスト計算手段が、前記パラメータに基づいて、計算した検索コストを最小化するインデックス数を求めるコスト計算ステップと、前記構成変更指示手段が、前記インデックス手段と前記集約装置に対して、前記コスト計算ステップによって求めた前記インデックス数を実現するように、レコードの移動と木構造の変更を指示する構成変更指示ステップとを有することを特徴とする。
【００１２】
本発明は、前記構成変更指示ステップは、直前に求められた前記インデックス数と、新たに求められた前記インデックス数の差が所定の条件を満たした場合のみに、前記インデックス手段と前記集約装置に対して、レコードの移動と木構造の変更を指示することを特徴とする。
【００１３】
本発明は、キーワードを指定すると、該キーワードを含むレコードを返す処理を実行する複数のインデックス手段と、前記インデックス手段の処理結果を集約する１以上の集約装置とが木構造状に接続された検索システムに、検索コスト計算装置が接続され、前記検索コスト計算装置上のコンピュータに前記検索システムの構成を変更して検索コストを最小化する処理を行わせる検索コスト計算プログラムであって、前記インデックス手段と前記集約装置から、検索コストを計算するために必要なパラメータを取得するパラメータ取得ステップと、前記パラメータに基づいて、計算した検索コストを最小化するインデックス数を求めるコスト計算ステップと、前記インデックス手段と前記集約装置に対して、前記コスト計算ステップによって求めた前記インデックス数を実現するように、レコードの移動と木構造の変更を指示する構成変更指示ステップとを前記コンピュータに行わせることを特徴とする。
【００１４】
本発明は、前記構成変更指示ステップは、直前に求められた前記インデックス数と、新たに求められた前記インデックス数の差が所定の条件を満たした場合のみに、前記インデックス手段と前記集約装置に対して、レコードの移動と木構造の変更を指示することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、検索コストが最小となるようにインデックス数を動的に調整することができ、検索システムの性能を向上させることが可能になるという効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態の構成を示すブロック図である。
【図２】図１に示す装置の動作を示すシーケンス図である。
【図３】パラメータの一例を示す説明図である。
【図４】インデックス数と検索コストの関係を示す説明図である。
【発明を実施するための形態】
【００１７】
以下、図面を参照して、本発明の一実施形態による検索システム及び検索コスト計算装置を説明する。図１は同実施形態の構成を示すブロック図である。この図において、符号１は、検索コストを計算し、得られた検索コストに応じて、最適なインデックス数になるようにインデックスの木構造の構成を変更するコスト計算装置である。符号２１〜２３は、インデックスを集約する集約装置である。符号３１〜３４は、検索を高速に実行するためのデータ構造を有するインデックスである。ここでいうインデックスとは、あるキーワードを指定すると、それ含むレコードを返すソフトウェアコンポーネントである。
【００１８】
符号４は、根となる集約装置２１接続されるコンピュータネットワークであり、例えばインターネットである。符号５は、ユーザが使用するクライアント（端末装置）であり、インターネット４に接続される。図１に示すように、インデックス３１〜３４を葉とし、節を集約装置２１〜２３によって構成する木構造が構成されている。なお、具体的な木構造は図１と異なっていてもよく、インデックス数と集約装置数は任意であり、集約装置の分岐数も任意である。
【００１９】
符号１１は、集約装置２１、２２、２３及びインデックス３１、３２、３３、３４のそれぞれとの間で情報通信を行う通信部である。符号１２は、通信部１１を介して、集約装置２１、２２、２３及びインデックス３１、３２、３３、３４それぞれから所定のパラメータを収集するパラメータ収集部である。符号１３は、記憶装置で構成し、パラメータ収集部１２が収集したパラメータを保存するパラメータ保存部である。符号１４は、所定の時間間隔を計時するタイマである。
【００２０】
符号１５は、パラメータ保存部１３に保存されているパラメータに基づいて、検索コストを計算するコスト計算部である。符号１６は、コスト計算部１５が計算した検索コストの値に応じて、集約装置２１、２２、２３及びインデックス３１、３２、３３、３４に対して、構成の変更を指示する構成変更指示部である。なお、コスト計算装置１は、集約装置２１〜２３のいずれかに含まれていてもよい。
【００２１】
次に、図１を参照して、図１に示す検索システムの情報検索動作を説明する。まず、クライアント５は、木構造の根に位置する集約装置２１に対して検索クエリを送信する。この検索クエリは集約装置２２、２３を経由して、各インデックス３１、３２、３３、３４に配信される。インデックス３１、３２、３３、３４は検索を実行すると、上位の集約装置２２、２３に結果を返す。
【００２２】
例えば、インデックス３１、３２は、集約装置２２に検索結果を返し、インデックス３３、３４は、集約装置２３に検索結果を返す。集約装置２２、２３は検索結果を集約しながら上位の集約装置に転送することにより、最終的に根に位置する集約装置２１がクライアント５に集約された検索結果を返す。このように、インデックス３１〜３４における検索処理は並列に実行でき、また、格段の集約装置２２、２３における集約処理も並列に実行できるため、検索処理を高速に行うことが可能となる。
【００２３】
次に、図２を参照して、図１に示すコスト計算装置１の動作を説明する。図２は、図１に示すコスト計算装置１の動作を示すシーケンス図である。まず、パラメータ収集部１２は、通信部１１を介して、集約装置（ここでは、集約装置２１、２２、２３）のそれぞれから集約コストと分岐数の値（パラメータ）を受信する（ステップＳ１）。また、パラメータ収集部１２は、インデックス（ここではインデックス３１、３２、３３、３４）のそれぞれからレコード数の値を受信する（ステップＳ２）。
【００２４】
パラメータ収集部１２は、受信した各パラメータをパラメータ保存部１３に保存する。このとき、パラメータ収集部１２は、パラメータを送信した集約装置またはインデックスを識別可能な識別情報と関係付けて各パラメータをパラメータ保存部１３に保存する（ステップＳ３）。図２に示すシーケンスでは、集約装置とインデックスのそれぞれからパラメータを送信する例を示しているが、コスト計算装置１から集約装置とインデックスのそれぞれに対してパラメータ送信を要求し、この要求に応じて、集約装置とインデックスのそれぞれからパラメータを送信するようにしてもよい。
【００２５】
次に、タイマ１４が発火する（所定時刻になる、または所定時間経過する）と（ステップＳ４）、コスト計算部１５は、パラメータ保存部１３に保存されているパラメータを読み出して、検索コストを計算する（ステップＳ５）。コスト計算部１５が検索コストの計算を開始するタイミングは、いくつかの集約装置の付加状況が変化したり、応答時間が変化したときでもよい。検索コストは、総計算量やメモリ使用量、応答時間などいくつかの尺度を用いることができるが、ここでは総計算量と重みづけられた応答時間との和を用いる。
【００２６】
一般に、インデックス単体の検索コスト（計算量、応答時間）は、インデックスが保存しているレコード数をｒとし、コスト係数をｃとすると、ｃ・ｌｏｇ２（ｒ）となる。また、インデックス数をｘとし、システム全体のレコード数をＲとすると、インデックスが保存しているレコード数ｒは、ｒ＝Ｒ／ｘとなる。集約装置ひとつあたりの集約コストをａとし、集約装置の分岐数をｂとすると、集約装置の段数はｌｏｇｂ（ｘ）となり、集約装置数は（ｘ−１）／（ｂ−１）となる。
【００２７】
インデックスでの検索処理は並列に実行でき、格段での集約処理も並列に実行できるため、応答時間ｌ（ｘ）は、インデックスでの検索時間と、集約時間の和として、（１）式で表される。
ｌ（ｘ）＝ｃ・ｌｏｇ２（Ｒ／ｘ）＋ａ・ｌｏｇｂｘ・・・（１）
また、総計算量ｍ（ｘ）は（２）式になる。
ｍ（ｘ）＝ｃ・ｘ・ｌｏｇ２（Ｒ／ｘ）＋ａ（ｘ−１）／（ｂ−１）・・・（２）
【００２８】
そして、重みｗを用いると、検索コストｆ（ｘ）は（３）式によって求めることができる。
ｆ（ｘ）＝ｌ（ｘ）＋ｗ・ｍ（ｘ）・・・（３）
ここで、集約コストａ、集約装置の分岐数ｂ及びレコード数ｒは、パラメータ保存部１３から読み出したパラメータである。その他のパラメータ（コスト係数ｃ、重みｗ）については、実験やシミュレーションによって決定し、予めパラメータ保存部１３に保存しておく。なお、パラメータ保存部１３に保存されているパラメータが、集約装置ごとに異なるときは保存されているパラメータの平均値を用いて、（１）〜（３）式を計算する。
【００２９】
コスト計算部１５は、ｆ（ｘ）を微分してｆ（ｘ）が最小になるときのｘ（最適なｘ）の値を求める。各パラメータに図３に示す数値を与え、プロットした例を図４に示す。図４において、横軸はｘ、縦軸は、ｆ（ｘ）の値である。図４に示すように、図３に示すパラメータにおいては、ｘが１００付近で検索コストｆ（ｘ）が最小になることが分かる。コスト計算部１５は、新たに求めたｘ（最適インデックス数）の値を構成変更指示部１６へ出力する。
【００３０】
構成変更指示部１６は、コスト計算部１５から新たなｘの値が出力された場合に、直前にコスト計算部１５から出力されたｘの値と比較して、新たなｘの値が変化していれば、インデックス３１〜３４と集約装置２１〜２３のそれぞれに対して、新たに求められた最適なｘの値を実現するように、レコードの移動と木構造の変更を指示する（ステップＳ６）。これを受けて、インデックス３１〜３４と集約装置２１〜２３のそれぞれは、最適なｘの値を実現するように、レコードの移動と木構造の変更を行い、最適なインデックス数を実現する。新たなｘの値が変化していない場合、構成変更指示部１６は、インデックス３１〜３４と集約装置２１〜２３のそれぞれに対してレコードの移動と木構造の変更を指示しない。このように、検索システムに接続されたコスト計算装置１は、定期的に検索コストを計算し、インデックス数を最適な値に調整することで、検索コストを抑えることが可能となる。
【００３１】
なお、インデックス数の変更は、ｘの値が変化した場合のみに限らず、所定の条件を満たした場合に、レコードの移動と木構造の変更を行って、インデックス数の変更を行うようにしてもよい。例えば、インデックス数の変更コストを考慮した場合、インデックス数の変更コストＭは、移動レコード数をｓとし、レコードあたりの移動コストをｔとすると、Ｍ＝ｓｔとなる。インデックス数変更によるコスト低下をΔｆとしたとき、Δｆ＞Ｍであるときのみインデックス数の調整を行うようにしてもよい。このようにインデックス数の変更条件を与えることで、インデックス数の変更コストも含めた検索コストを最小化することができる。
【００３２】
以上説明したように、検索システムの性能（検索コスト）は、分割するインデックス数の影響を受けるが、検索コストを最小化する方程式を導入し、この方程式で求めた最適インデックス数を実現するように、インデックス数を動的に調整するようにしたため、システム性能の向上を図ることができる。さらに、十分な検索コスト削減効果が得られるときのみ、インデックス数の調整を行うようにしたため、インデックス数の変更コストも含めた検索コストを最小化することができる。
【００３３】
なお、図１に示すコスト計算装置１の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより検索コストの計算及び構成変更指示の出力処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００３４】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【産業上の利用可能性】
【００３５】
情報検索を行うシステムにおいてインデックス数の最適化することが不可欠な用途に適用できる。
【符号の説明】
【００３６】
１・・・コスト計算装置、１１・・・通信部、１２・・・パラメータ収集部、１３・・・パラメータ保存部、１４・・・タイマ、１５・・・コスト計算部、１６・・・構成変更指示部、２１、２２、２３・・・集約装置、３１、３２、３３、３４・・・インデックス、４・・・インターネット、５・・・クライアント
【図１】
2011113205.tif 000003
【図２】
2011113205.tif 000004
【図３】
2011113205.tif 000005
【図４】
2011113205.tif 000006