(57)【特許請求の範囲】
【請求項１】
互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフ、に含まれる特徴的なパスのパターンであって、インスタンスをもつノードを一方の端位置に有し、クラスが定義されたノードを他方の端位置に有し、各アークがラベルをもつ、パターンが予め記憶されるパターン記憶手段と、
第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、指定されたクラスが定義されたノードを他方の端位置に有する、パターンである第１パターンを前記パターン記憶手段から検索し、第２のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、指定されたクラスが定義されたノードを他方の端位置に有する、パターンである第２パターンを前記パターン記憶手段から検索するパターン検索手段と、
第１パターンおよび第２パターンを、他方の端位置のノードでマージするパターンマージ手段と、
このパターンマージ手段によりマージされたパターンにマッチするサブグラフを前記グラフから検索するグラフ検索手段と
を備えることを特徴とするグラフ検索装置。
【請求項２】
前記グラフから、予め決めた内容をラベルに含むアークの先端が接続されたノードを一方の端位置に有するパスを検索し、当該ノード以外のノードのインスタンスを変数に置き換えてなるパターンを生成し、前記パターン記憶手段に記憶させるパターン生成手段
を備えることを特徴とする請求項１記載のグラフ検索装置。
【請求項３】
前記グラフのアークがもつ各ラベルのスコアまたは前記グラフがもつノードに定義された各クラスのスコアが記憶された記憶手段と、
前記グラフから、予め決めた内容をラベルに含むアークの先端が接続されたノードを一方の端位置に有するパスを検索し、当該ノード以外のノードのインスタンスを変数に置き換え、当該パスのスコアを前記記憶手段に記憶されたスコアに基づいて計算し、当該パスにマッチするサブグラフを前記グラフから検索し、検索されたサブグラフの数に応じてスコアを増加させ、スコアが予め定めたしきい値より大きいパターンを前記パターン記憶手段に記憶させるパターン生成手段と
を備えることを特徴とする請求項１記載のグラフ検索装置。
【請求項４】
互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフ、に含まれる特徴的なパスのパターンであって、インスタンスをもつノードを両方の端位置に有し、各アークがラベルをもつ、パターンが予め記憶されるパターン記憶手段と、
第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、第２のキーワードに等しいインスタンスをもつノードを他方の端位置に有する、パターンである第１パターンを前記パターン記憶手段から検索し、第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、第３のキーワードに等しいインスタンスをもつノードを他方の端位置に有する、パターンである第２パターンを前記パターン記憶手段から検索するパターン検索手段と、
第１パターンと第２パターンとを、それぞれに共通に含まれる共通部分でマージするパターンマージ手段と、
このパターンマージ手段によりマージされたパターンにマッチするサブグラフを前記グラフから検索するグラフ検索手段と
を備えることを特徴とするグラフ検索装置。
【請求項５】
前記グラフから、予め決めた内容をラベルに含むアークの先端が接続されたノードを両方の端位置に有するパスであるパターンを生成し、前記パターン記憶手段に記憶させるパターン生成手段
を備えることを特徴とする請求項４記載のグラフ検索装置。
【請求項６】
前記グラフのアークがもつ各ラベルのスコアまたは前記グラフがもつノードに定義された各クラスのスコアが記憶された記憶手段と、
前記グラフから、予め決めた内容をラベルに含むアークの先端が接続されたノードを両方の端位置に有するパスを検索し、当該パスのスコアを前記記憶手段に記憶されたスコアに基づいて計算し、スコアが予め定めたしきい値より大きいパターンを前記パターン記憶手段に記憶させるパターン生成手段と
を備えることを特徴とする請求項４記載のグラフ検索装置。
【請求項７】
請求項１ないし３のいずれかに記載のグラフ検索装置としてコンピュータを動作させるコンピュータプログラム。
【請求項８】
請求項７記載のコンピュータプログラムが格納された記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各キーワードから検索されるサブグラフ同士の関係が明確なサブグラフを高速に検索できるグラフ検索装置に関するものである。
【背景技術】
【０００２】
従来のグラフ検索装置（例えば、非特許文献１に記載のもの）は、あるグラフから例えば、図２８に示すように、クエリにマッチするサブグラフを複数検索して表示する。一方は、キーワード「ＸＭＬ」から検索されたものであり、他方はキーワード「ウェブサービス」から検索されたものである。
【０００３】
また、非特許文献２に記載のＡＧＭ(Apriori-based Graph Mining)というグラフマイニングを用いたグラフ検索装置は、ラベル付きグラフから頻出のサブグラフを検索する。
【０００４】
また、単純最短パスアルゴリズムを用いたグラフ検索装置では、あるグラフから、キーワードにマッチするノード間の最短パス（広義のサブグラフ）を検索する。
【０００５】
また、リンク解析（HITS アルゴリズム）では、検索時にリンク解析を行うことで、サブグラフ同士の関係を表現する。
【非特許文献１】SPARQL Query Language for RDF, http://www.w3.org/TR/rdf-sparql-puery/
【非特許文献２】Complete Mining of Freqent from Graphs, Akihiro Inokuchi,Takashi Washio and Hiroshi Motoda:Complete Mining of Freqent Patterns from Graphs: Mining Graph Data, Machine Learning, Vol.50, pp.321-354,(2003)
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、図２８のようなサブグラフでは、同じインスタンス「Ｐｅｒｓｏｎ：電々太郎」をもつノードを両者が有しながらも、そのサブグラフ同士の関係が表現されておらず、よってその関係が不明確である。
【０００７】
非特許文献１では、クエリにマッチするサブグラフを検索することの記載があり、非特許文献２では、頻出のサブグラフを検索することの記載があるが、いずれの文献においても、サブグラフ同士の関係の記載がない。また、非特許文献２記載の技術では、ユーザが求めるキーワードに関係なく多くのサブグラフが検索されるので、どれがユーザの興味と関係あるのかがわからない。
【０００８】
また、単純最短パスアルゴリズムを用いたグラフ検索装置では、最短パス（サブグラフ）のみの関係を提供し、有益なサブグラフ周辺の知識が十分に考慮されていない。つまり、最短パス（サブグラフ）同士の関係以外を表現できない。
【０００９】
また、リンク解析（HITSアルゴリズム）では、検索時にリンク解析を行うので検索に長時間を要する。
【００１０】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、各キーワードから検索されるサブグラフ同士の関係が明確なサブグラフを高速に検索できるグラフ検索装置を提供することにある。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、請求項１の本発明は、互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフ、に含まれる特徴的なパスのパターンであって、インスタンスをもつノードを一方の端位置に有し、クラスが定義されたノードを他方の端位置に有し、各アークがラベルをもつ、パターンが予め記憶されるパターン記憶手段と、第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、指定されたクラスが定義されたノードを他方の端位置に有する、パターンである第１パターンを前記パターン記憶手段から検索し、第２のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、指定されたクラスが定義されたノードを他方の端位置に有する、パターンである第２パターンを前記パターン記憶手段から検索するパターン検索手段と、第１パターンおよび第２パターンを、他方の端位置のノードでマージするパターンマージ手段と、このパターンマージ手段によりマージされたパターンにマッチするサブグラフを前記グラフから検索するグラフ検索手段とを備えることを特徴とするグラフ検索装置をもって解決手段とする。
【００１２】
請求項２の本発明は、前記グラフから、予め決めた内容をラベルに含むアークの先端が接続されたノードを一方の端位置に有するパスを検索し、当該ノード以外のノードのインスタンスを変数に置き換えてなるパターンを生成し、前記パターン記憶手段に記憶させるパターン生成手段を備えることを特徴とする請求項１記載のグラフ検索装置をもって解決手段とする。
【００１３】
請求項３の本発明は、前記グラフのアークがもつ各ラベルのスコアまたは前記グラフがもつノードに定義された各クラスのスコアが記憶された記憶手段と、前記グラフから、予め決めた内容をラベルに含むアークの先端が接続されたノードを一方の端位置に有するパスを検索し、当該ノード以外のノードのインスタンスを変数に置き換え、当該パスのスコアを前記記憶手段に記憶されたスコアに基づいて計算し、当該パスにマッチするサブグラフを前記グラフから検索し、検索されたサブグラフの数に応じてスコアを増加させ、スコアが予め定めたしきい値より大きいパターンを前記パターン記憶手段に記憶させるパターン生成手段とを備えることを特徴とする請求項１記載のグラフ検索装置をもって解決手段とする。
【００１４】
請求項４の本発明は、互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフ、に含まれる特徴的なパスのパターンであって、インスタンスをもつノードを両方の端位置に有し、各アークがラベルをもつ、パターンが予め記憶されるパターン記憶手段と、第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、第２のキーワードに等しいインスタンスをもつノードを他方の端位置に有する、パターンである第１パターンを前記パターン記憶手段から検索し、第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、第３のキーワードに等しいインスタンスをもつノードを他方の端位置に有する、パターンである第２パターンを前記パターン記憶手段から検索するパターン検索手段と、第１パターンと第２パターンとを、それぞれに共通に含まれる共通部分でマージするパターンマージ手段と、このパターンマージ手段によりマージされたパターンにマッチするサブグラフを前記グラフから検索するグラフ検索手段とを備えることを特徴とするグラフ検索装置をもって解決手段とする。
【００１５】
請求項５の本発明は、前記グラフから、予め決めた内容をラベルに含むアークの先端が接続されたノードを両方の端位置に有するパスであるパターンを生成し、前記パターン記憶手段に記憶させるパターン生成手段を備えることを特徴とする請求項４記載のグラフ検索装置をもって解決手段とする。
【００１６】
請求項６の本発明は、前記グラフのアークがもつ各ラベルのスコアまたは前記グラフがもつノードに定義された各クラスのスコアが記憶された記憶手段と、前記グラフから、予め決めた内容をラベルに含むアークの先端が接続されたノードを両方の端位置に有するパスを検索し、当該パスのスコアを前記記憶手段に記憶されたスコアに基づいて計算し、スコアが予め定めたしきい値より大きいパターンを前記パターン記憶手段に記憶させるパターン生成手段とを備えることを特徴とする請求項４記載のグラフ検索装置をもって解決手段とする。
【００１７】
請求項７の本発明は、請求項１ないし３のいずれかに記載のグラフ検索装置としてコンピュータを動作させるコンピュータプログラムをもって解決手段とする。
【００１８】
請求項８の本発明は、請求項７記載のコンピュータプログラムが格納された記録媒体をもって解決手段とする。
【発明の効果】
【００１９】
本発明のグラフ検索装置によれば、互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフ、に含まれる特徴的なパスのパターンであって、インスタンスをもつノードを一方の端位置に有し、クラスが定義されたノードを他方の端位置に有し、各アークがラベルをもつ、パターンが予め記憶されるパターン記憶手段と、第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、指定されたクラスが定義されたノードを他方の端位置に有する、パターンである第１パターンを前記パターン記憶手段から検索し、第２のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、指定されたクラスが定義されたノードを他方の端位置に有する、パターンである第２パターンを前記パターン記憶手段から検索するパターン検索手段と、第１パターンおよび第２パターンを、他方の端位置のノードでマージするパターンマージ手段と、このパターンマージ手段によりマージされたパターンにマッチするサブグラフを前記グラフから検索するグラフ検索手段とを備えるので、第１のキーワードから検索されるサブグラフと第２のキーワードから検索されるサブグラフとの関係が明確なサブグラフを高速に検索することができる。
【００２０】
また、本発明のグラフ検索装置によれば、互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフ、に含まれる特徴的なパスのパターンであって、インスタンスをもつノードを両方の端位置に有し、各アークがラベルをもつ、パターンが予め記憶されるパターン記憶手段と、第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、第２のキーワードに等しいインスタンスをもつノードを他方の端位置に有する、パターンである第１パターンを前記パターン記憶手段から検索し、第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、第３のキーワードに等しいインスタンスをもつノードを他方の端位置に有する、パターンである第２パターンを前記パターン記憶手段から検索するパターン検索手段と、第１パターンと第２パターンとを、それぞれに共通に含まれる共通部分でマージするパターンマージ手段と、このパターンマージ手段によりマージされたパターンにマッチするサブグラフを前記グラフから検索するグラフ検索手段とを備えるので、第１のキーワードおよび第２のキーワードから検索されるサブグラフと第１のキーワードおよび第３のキーワードから検索されるサブグラフとの関係が明確なサブグラフを高速に検索することができる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施の形態を図面を参照して説明する。なお、同一のものには同一符号を付与し、重複説明を省略する。
【００２２】
［第１の実施の形態］
図１は、第１の実施の形態に係るグラフ検索装置の構成図である。
【００２３】
グラフ検索装置１は、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００２４】
グラフ検索装置１は、有向グラフであるグラフＧを表示するためのデータ群が記憶されたグラフデータベース１１と、グラフのサブグラフを検索する際に表示装置３に表示される入力用インタフェースを生成する入力用インタフェース生成部１２とを備える。
【００２５】
図２は、グラフデータベース１１に記憶されたデータ群を全て使って表示できるグラフＧの一部を例示した図である。
【００２６】
グラフデータベース１１に記憶されたデータ群を全て使って、図２に一部を例示したグラフＧ、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフＧ、を表示することができる。逆にいえば、グラフＧを表示するための過不足ないデータ群がグラフデータベース１１に記憶されている。以下、そのデータ群を便宜的にグラフＧという。また、なんらかのグラフ、サブグラフ（なんらかのグラフそのものまたはそれに含まれるグラフ）、パス（分岐および閉ループをもたないグラフ）などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
【００２７】
グラフＧでは、例えば、「ＸＭＬ」や「Ｂプロジェクト」などのインスタンスをもつノードが、「ｒｍ：技術キーワード」や「ｒｍ：著者」などのラベルをもつアークで接続される。また、グラフＧでは、ノードにそのインスタンス「Ｐｅｒｓｏｎ：山田太郎」などの概念であるクラス「Ｐｅｒｓｏｎ：人」などが定義される。
【００２８】
図３は、グラフデータベース１１に記憶されたデータ群の一部を例示した図である。
【００２９】
例えば、最初のデータ「＜ｏｒｇ：Ｄプロジェクト＞＜ｒｍ：技術キーワード＞”ＸＭＬ”」は、インスタンス「ｏｒｇ：Ｄプロジェクト」をもつノードからインスタンス「ＸＭＬ」のノードへ向かうアークがラベル「ｒｍ：技術キーワード」をもつことを示している。また、例えば、最後のデータ「＜ｐｅｒｓｏｎ：鈴木花子＞＜ｒｄｆ：ｔｙｐｅ＞＜Ｐｅｒｓｏｎ：人＞」は、インスタンス「ｐｅｒｓｏｎ：鈴木花子」をもつノードのクラスが「ｐｅｒｓｏｎ：人」であることを示している。
【００３０】
なお、各データは、実際にはＲＤＦ（以下の文献に記載）で表現されている。
【００３１】
「Resource Description Framework(RDF)Model and Syntax Specification」, Ora Lassia, Ralph R.Swick編,[online], インターネット<URL:http://www.w3.org/TR/1999/REC-rdf-syntax-19990222/>
「RDF Vocabulary Description Language 1.0: RDF Schema」, Dan Brickley, R.V.Guha編,[online], インターネット<URL:http://www.w3.org/TR/rdf-schema/>
図１に戻り、グラフ検索装置１は、サブグラフの検索に用いられるパターンの生成に用いられるアークスコア記憶部１３を備える。
【００３２】
図４は、アークスコア記憶部１３の記憶内容を示す図である。アークスコア記憶部１３は、グラフＧのアークがもつ各ラベルのスコア（アークスコア）を記憶している。グラフＧの各ノードのインスタンスをそのノードのクラスに置き換え、同一のインスタンス（クラス）をもつノードではその中の１つのみ残し、そのようにしてなるグラフにアークスコア記憶部１３の各アークスコアを当てはめると、その一部は、例えば図５のようになる。この図に示すグラフでは、ノードのインスタンス（グラフＧのノードのクラス）のクラスをインスタンスとしてもつノードの例として、インスタンス「org:Organization」をもつノードを示している。
【００３３】
図１に戻り、グラフ検索装置は、さらに、パターンを生成するパターン生成部１４と、生成されたパターンが記憶されるパターンデータベース１５と、パターンデータベース１５からパターンを検索するパターン検索部１６と、パターンをマージするパターンマージ部１７と、グラフＧのサブグラフを検索するグラフ検索部１８と、パターン検索部１６およびグラフ検索部１８と各データベースとを中継するデータベースインタフェース１９と、表示装置３に表示される出力用インタフェースを生成する出力用インタフェース生成部１１０とを備える。
【００３４】
グラフ検索装置１は、各部（データベース含む）でデータの送受信（受け渡し）が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータをグラフ検索装置として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。第２の実施の形態でも同様である。
【００３５】
（第１の実施の形態の動作）
図６は、パターン生成部１４のフローチャートである。ここでは、パターン生成部１４がグラフＧを扱う際、グラフＧからパスを取得する際、パターンをパターンデータベース１５に記憶させる際、データベースインタフェース１９にクエリを送信するのだが、それについては冗長なのでの言及しないこととする。
【００３６】
パターン生成部１４は、まず、グラフＧのノードに、その重要度を示すこととなる、ノードスコアの初期値「１」を設定する（Ｓ１）。
【００３７】
次に、パターン生成部１４は、各ノードにつき、図７の式により、ノードスコアを計算する（Ｓ３）。
【００３８】
そして、このノードスコアで、グラフＧに設定されたノードスコアの初期値を更新する（Ｓ５）。このような計算更新を、ノードスコアが収束するまで、再帰的に行う。これにより、ノードスコアが重要度を示すこととなる。
【００３９】
グラフＧにアークスコア記憶部１３の各アークスコアを当てはめたグラフの一部が、例えば図８に示すようなものであった場合、インスタンス「ＸＭＬ」をもつノードのノードスコアは０．５となる。インスタンス「Person:電々三郎」をもつノードのノードスコアは０．９となる。インスタンス「org:H3G」をもつノードのノードスコアは０．６となる。
【００４０】
次に、パターン生成部１４は、グラフＧから、予め決めた内容（例えば「キーワード」や「技術用語」）をラベルに含むアークの先端が接続されたノード（キーワードノード）を一方の端位置に有する、予め決めた長さ以下の、パスを取得する（Ｓ７）。
【００４１】
次に、パターン生成部１４は、図９の式により、その各パスのパススコアを計算する（Ｓ９）。
【００４２】
次に、パターン生成部１４は、その各パスにつき、キーワードノード以外のノードのインスタンスを変数に置き換える（Ｓ１１）。
【００４３】
次に、パターン生成部１４は、全てのパスをパスグループ（同一のパスからなる）ごとに区分し、各パスグループにつき、図１０の式により、スコアを計算する（Ｓ１３）。そして、スコアが予め定めたしきい値以下の各パスグループを削除する（Ｓ１５）。
【００４４】
次に、パターン生成部１４は、残った各パスグループにつき、１パス以外を削除する（Ｓ１７）。
【００４５】
次に、パターン生成部１４は、残ったパス（パターンという）に、そのパターンスコアとして、元のパスグループのスコアを付与し、パターンデータベース１５に記憶させる（Ｓ１９）。
【００４６】
これにより、図１１に２つ示すようなパターンがパターンデータベース１５に記憶される。
【００４７】
パターンは、グラフデータベース１１に記憶されるデータ群（グラフＧ）の一部をなすデータ群と同様なものであり、それを本図ようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。なお、データ群である実際のパターンを逐一説明するのが冗長なので、図１１のように、グラフ化されたパターンで便宜的に説明する。
【００４８】
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、図に示すように、？とそれに後続する単語からなる。
【００４９】
ここでのパターンは、一方の端位置のノードがインスタンスをもち、他のノードには変数が設定され、各アークがラベルをもつものである。
【００５０】
また、一般的にパターンでは、必要があれば、変数が設定された一部のノードに、そのパターンにより検索されるグラフにおける、同位置のノードがもつインスタンスの上位概念を示すクラスが予め定義される。
【００５１】
ここでのパターンは、他方の端位置のノードにクラスが定義されたものである。
【００５２】
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。
【００５３】
つまり、検索されるのは、（１）そのグラフまたはそのサブグラフであって、（２）パターンの構造を過不足なく有し、（３）パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有し、（４）場合によってはパターンに含まれるクラスが定義されたノードの位置に等しい位置にあるノードが当該クラスの下位概念であるインスタンスを有するものである。
【００５４】
なお、パターンにより、このようにしてサブグラフを検索することを、パターンにマッチするサブグラフを検索するという。
【００５５】
図１２は、パターン生成部１４が他の方法でパターンを生成するときに、アークスコア記憶部１３に代えて用いるクラススコア記憶部の記憶内容を示す図である。クラススコア記憶部は、グラフＧがもつノードに定義された各クラスのスコア（クラススコア）を記憶している。グラフＧの各ノードのインスタンスをそのノードのクラスに置き換え、同一のインスタンス（クラス）をもつノードではその中の１つのみ残し、そのようにしてなるグラフにクラススコア記憶部の各クラススコアを当てはめると、その一部は、例えば図１４のようになる。
【００５６】
図１３は、パターン生成部１４が他の方法でパターンを生成するときのフローチャートである。図６のときと同様な理由から、データベースインタフェース１９とクエリについては言及しない。
【００５７】
パターン生成部１４は、まず、グラフＧを取得し、そのグラフＧの各ノードのインスタンスをそのノードのクラスに置き換え、同一のインスタンス（クラス）をもつ複数のノードではその中の１つのみ残しそれ以外を削除し、そのようにしてなるグラフにクラススコア記憶部の各クラススコアを設定（初期設定）する（Ｓ２１）。その一部は、例えば図１４のようになる。この図に示すグラフでは、ノードのインスタンス（グラフＧのノードのクラス）のクラスをインスタンスとしてもつノードの例として、インスタンス「org:Organization」をもつノードを示している。このように、クラススコア記憶部は、いわばクラスのクラスについてのスコアをも記憶しており、ここでは、このようなノードにもクラススコアが設定される。
【００５８】
次に、各クラスにつき、つまり、図１４に例示したグラフの各ノードにつき、図１５の式により、クラススコアを計算する（Ｓ２３）。そして、このクラススコアで、図１４に例示したグラフのクラススコアを更新する（Ｓ２５）。このような計算更新を、クラススコアが収束するまで、再帰的に行う。これにより、クラススコアが重要度を示すこととなる。
【００５９】
次に、パターン生成部１４は、グラフＧから、予め決めた内容（例えば「キーワード」や「技術用語」）をラベルに含むアークの先端が接続されたノード（キーワードノード）を一方の端位置に有する、予め決めた長さ以下の、パスを取得する（Ｓ２７）。
【００６０】
次に、パターン生成部１４は、その各パスにつき、キーワードノード以外のノードのインスタンスを変数に置き換える（Ｓ２９）。
【００６１】
次に、パターン生成部１４は、全てのパスをパスグループ（同一のパスからなる）ごとに区分し、各パスグループで１パス以外を削除する（Ｓ３１）。
【００６２】
次に、パターン生成部１４は、図１６の式により、残った各パスのパススコアを計算する（Ｓ３３）。なお、ここでは、再帰計算後のクラススコアを用いるのだが、再帰的計算前のクラススコア（初期値）をそのまま利用してもよい。
【００６３】
次に、パターン生成部１４は、各パスにマッチするサブグラフをグラフＧから取得する（Ｓ３５）。
【００６４】
なお、Ｓ２７からＳ３５は、以下のようにしてもよい。
【００６５】
つまり、Ｓ２７では、予め決めた長さ以下の、パスを取得し、Ｓ２９では、その各パスのノードのインスタンスを変数に置き換え、Ｓ３１では、全てのパスをパスグループ（同一のパスからなる）ごとに区分し、各パスグループで１パス以外を削除し、Ｓ３３では、図１６の式により、残った各パスのパススコアを計算し、Ｓ３５では、各パスの一方の端位置のノードに、予め決めておいたインスタンス（例えば、「ＸＭＬ」や「ウェブサービス）を設定し、そのパスにマッチするサブグラフをグラフＧから取得する。
【００６６】
次に、パターン生成部１４は、図１７の式により、各パススコアを再計算する（Ｓ３７）。  次に、パターン生成部１４は、残ったものから、パススコアが予め定めたしきい値以下のパスを削除する（Ｓ３９）。
【００６７】
次に、パターン生成部１４は、残ったパス（パターンという）に、そのパターンスコアとして、元のパススコアを付与し、パターンデータベース１５に記憶させる（Ｓ４１）。
【００６８】
なお、図１３のフローチャートで採用したパスのスコアの再計算を、図６のフローチャートで採用してもよい。また、図６のフローチャートで採用した、パスのスコアの計算にノードスコアを用いる方法を、図１３のフローチャートで採用してもよい。
【００６９】
いずれにしても、パターンデータベース１５にパターンスコアを含むパターンが記憶されると、最終的に得たいサブグラフの検索が可能となる。
【００７０】
図１８は、このサブグラフをグラフＧから検索するときのシーケンス図である。図６などのときと同様な理由から、パターンを取得する説明では、データベースインタフェース１９とクエリについて言及しない。
【００７１】
グラフ検索装置１では、入力用インタフェース生成部が入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ１０１）、図１９のように表示させる（Ｓ１０３）。ここでの操作により特定されたキーワードＫＷ１、ＫＷ２およびクラスＣＬを、ユーザ端末２がグラフ検索装置１に送信する（Ｓ１０５）。
【００７２】
これ以降、グラフ検索装置１は、これらキーワードおよびクラスを用いるのだが、ユーザ端末２から送信されたキーワードやクラスを用いるのでなく、かかるキーワードやクラスを予めグラフ検索装置１が記憶しておき、それを用いてもよい。以降の処理を、予め決めた時刻に行ってもよい。これは第２の実施の形態でも同様である。
【００７３】
さて、グラフ検索装置１では、パターン検索部１６が、キーワードＫＷ１に等しいインスタンスをもつノードを一方の端位置に有し、クラスＣＬが定義されたノードを他方の端位置に有する、パターン（第１パターンという）をパターンデータベース１５から取得する（Ｓ１０７）。また、パターン検索部１６は、キーワードＫＷ２に等しいインスタンスをもつノードを一方の端位置に有し、クラスＣＬが定義されたノードを他方の端位置に有する、パターン（第２パターンという）をパターンデータベース１５から取得する（Ｓ１０９）。
【００７４】
なお、グラフ検索装置に、１以上のキーワード（例えば、「ＸＭＬ」、「ウェブサービス」、「ＲＤＦ」および「セマンティックＷｅｂ」）と１つのインデクス（例えば、「技術キーワード」）とを含むレコードを１以上有するインデクス記憶部を設け、Ｓ１０７では、以下のようにしてもよい。
【００７５】
つまり、Ｓ１０７では、このインデクス記憶部から、キーワードＫＷ１に等しいキーワードを含むレコードを検索し、そのレコードに含まれたインデクスに等しいインスタンスをもつノードを一方の端位置に有し、クラスＣＬが定義されたノードを他方の端位置に有する、パターン（第１パターンという）をパターンデータベース１５から取得する（Ｓ１０７）。なお、Ｓ１０９や、以下に説明するＳ４０７、Ｓ４０９およびＳ４１１でも同様である。
【００７６】
次に、パターンマージ部１７は、第１パターンおよび第２パターンを他方の端位置のノードでマージする（Ｓ１１１）。
【００７７】
これにより、図２０に２つ示すような、パターンが生成される。
【００７８】
次に、グラフ検索部１８が、そのパターンをクエリに変換し、それをデータベースインタフェース１９に送信する（Ｓ１１５）ことで、そのパターンにマッチするサブグラフをグラフＧから取得する（Ｓ１１７）。これにより、図２１に２つ示すような、サブグラフが検索される。
【００７９】
そして、グラフ検索部１８は、図２２の式により、各サブグラフのサブグラフスコアを計算する（Ｓ１１９）。
【００８０】
次に、グラフ検索部１８は、サブグラフをサブグラフスコアの順にソートする（Ｓ１２１）。ここで、複数のサブグラフを共通のインスタンスをもつノードでマージし、そのサブグラフのスコアとして、当該複数のサブグラフのサブグラフスコアの総和を計算してもよい。
【００８１】
そして、出力用インタフェース生成部１１０が、各サブグラフがサブグラフスコアの高い順に並べた出力用インタフェースを生成し、これをユーザ端末２に送信し（Ｓ１２３）、表示させる（Ｓ１２５）。
【００８２】
なお、本実施の形態では、ユーザ端末２での操作で特定されたクラスが１つの場合を説明したが、複数の場合は、それぞれにつき上記処理を行えばよい。
【００８３】
また、本実施の形態では、ユーザ端末２での操作で特定されたキーワードが２つの場合を説明したが、３つ以上の場合は、その中の２つづつについて上記処理を行えばよい。
【００８４】
以上説明したように、第１の実施の形態によれば、グラフＧに含まれる特徴的なパスのパターンであって、インスタンスをもつノードを一方の端位置に有し、クラスが定義されたノードを他方の端位置に有するパターンが予め記憶されるパターン記憶手段（パターンデータベース１５）と、第１のキーワード（キーワードＫＷ１）に等しいインスタンスをもつノード（キーワードノード）を一方の端位置に有し、指定されたクラス（クラスＣＬ）が定義されたノードを他方の端位置に有する、パターンである第１パターンをパターン記憶手段から検索し（Ｓ１０７）、第２のキーワード（キーワードＫＷ２）に等しいインスタンスをもつノードを一方の端位置に有し、指定されたクラス（クラスＣＬ）が定義されたノードを他方の端位置に有する、パターンである第２パターンをパターン記憶手段から検索する（Ｓ１０９）パターン検索手段（パターン検索部１６）と、第１パターンおよび第２パターンを、他方の端位置のノードでマージする（Ｓ１１１）パターンマージ手段（パターンマージ部１７）と、このパターンマージ手段によりマージされたパターンにマッチするサブグラフをグラフＧから検索する（Ｓ１１７）グラフ検索手段（グラフ検索部１８）とを備えるので、第１のキーワードから検索されるサブグラフ（図２８に例示）と第２のキーワードから検索されるサブグラフ（図２８に例示）との関係が明確なサブグラフ（図２１に例示）を高速に検索することができる。ここでは、検索時にはパターンを生成しないので、高速な検索が行える。また、その際には、パターンの指定が不要である。
【００８５】
また、グラフＧから、予め決めた内容をラベルに含むアークの先端が接続されたノードを一方の端位置に有するパスを検索し（Ｓ７）、当該ノード以外のノードのインスタンスを変数に置き換えてなるパターンを生成し（Ｓ１１）、パターン記憶手段に記憶させる（Ｓ１９）パターン生成手段（パターン生成部１４）を備えるので、より詳しくは、グラフＧのアークがもつ各ラベルのスコアまたはグラフＧがもつノードに定義された各クラスのスコアが記憶された記憶手段（アークスコア記憶部１３やクラススコア記憶部）と、グラフＧから、予め決めた内容をラベルに含むアークの先端が接続されたノードを一方の端位置に有するパスを検索し（Ｓ７）、当該ノード以外のノードのインスタンスを変数に置き換え（Ｓ２９）、当該パスのスコアを記憶手段に記憶されたスコアに基づいて計算し（Ｓ１３）、当該パスにマッチするサブグラフをグラフＧから検索し（Ｓ３５）、検索されたサブグラフの数に応じてスコアを増加させ（Ｓ３７）、スコアが予め定めたしきい値より大きいパターンをパターン記憶手段に記憶させる（Ｓ４１）パターン生成手段（パターン生成部１４）を備えるので、前記したパターン検索が行えるようになる。
【００８６】
［第２の実施の形態］
図２３は、第２の実施の形態に係るグラフ検索装置の構成図である。
【００８７】
グラフ検索装置１Ａは、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００８８】
グラフ検索装置１Ａは、グラフデータベース１１と、アークスコア記憶部１３と、パターン生成部１４Ａと、パターンデータベース１５と、パターン検索部１６Ａと、パターンマージ部１７Ａと、グラフ検索部１８と、データベースインタフェース１９と、出力用インタフェース生成部１１０とを備える。
【００８９】
（第２の実施の形態の動作）
図２４は、パターン生成部１４Ａのフローチャートである。図６などのときと同様な理由から、データベースインタフェース１９とクエリについては言及しない。
【００９０】
まず、パターン生成部１４Ａが、再帰的にステップＳ１、Ｓ３およびＳ５（図６と同様）を行う。これによりグラフＧのノードスコアがノードの重要度を示すこととなる。
【００９１】
次に、パターン生成部１４Ａは、グラフＧから、予め決めた内容（例えば「キーワード」や「技術用語」）をラベルに含むアークの先端が接続されたノード（キーワードノード）を両方の端位置に有する全てのパスを取得する（Ｓ２０１）。
【００９２】
なお、パターン生成部１４Ａは、以下のようにして、パスを取得してもよい。
【００９３】
つまり、パターン生成部１４Ａは、予め決めたインスタンスの組み合わせ（例えば「ＸＭＬ」と「ウェブサービス」）毎に、各インスタンスにのみ関連するサブグラフＧｓを取得する。そして、グラフＧについて再帰的に行われたステップＳ１、Ｓ３およびＳ５（図６と同様）を、このサブグラフＧｓについて行う。
【００９４】
そして、Ｓ２０１では、それらのインスタンスを両方の端位置に有する全てのパスを取得する。
【００９５】
サブグラフＧｓはグラフＧよりも規模が小さいので高速な処理が可能となる。また、サブグラフＧｓは、後述するキーワードのペアの関連性を正確に反映しているので、そのキーワードのペアの関連性を正確に反映したサブグラフを検索する（Ｓ４１９）ことができるようになる。
【００９６】
いずれにしても、Ｓ２０１ではパスが取得されることとなる。なお、このパスにおいて、キーワードノード以外の部分またはそれに含まれる部分を中間部分という。
【００９７】
次に、パターン生成部１４Ａは、図９の式により、その各パスのパススコアを計算する（Ｓ２０３）。
【００９８】
次に、パターン生成部１４Ａは、残ったパスから、パススコアが予め定めたしきい値以下のパスを削除する（Ｓ２０５）。
【００９９】
次に、パターン生成部１４Ａは、残ったパス（パターンという）に、そのパターンスコアとして、元のパススコアを付与し、パターンデータベース１５に記憶させる（Ｓ２０７）。
【０１００】
これにより、図２５に２つ示すような、各ノードがインスタンスをもち、各アークがラベルをもつ、パターンがパターンデータベース１５に記憶される。
【０１０１】
このように、パターンデータベース１５にパターンがスコアとともに記憶されると、最終的に得たいサブグラフの検索が可能となる。
【０１０２】
図２６は、このサブグラフをグラフＧから検索するときのシーケンス図である。図６などのときと同様な理由から、パターンを取得する説明では、データベースインタフェース１９とクエリについて言及しない。
【０１０３】
グラフ検索装置１Ａでは、入力用インタフェース生成部１２が入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ４０１）、図１９のように表示させる（Ｓ４０３）。ここでの操作により特定されたキーワードＫＷ１、ＫＷ２およびＫＷ３を、ユーザ端末２がグラフ検索装置１に送信する（Ｓ４０５）。
【０１０４】
グラフ検索装置１Ａでは、パターン検索部１６Ａが、キーワードＫＷ１に等しいインスタンスをもつノードを一方の端位置に有し、キーワードＫＷ２に等しいインスタンスをもつノードを他方の端位置に有する、パターン（第１パターンという）をパターンデータベース１５から取得する（Ｓ４０７）。また、パターン検索部１６Ａは、キーワードＫＷ１に等しいインスタンスをもつノードを一方の端位置に有し、キーワードＫＷ３に等しいインスタンスをもつノードを他方の端位置に有する、パターン（第２パターンという）をパターンデータベース１５から取得する（Ｓ４０９）。また、パターン検索部１６Ａは、キーワードＫＷ２に等しいインスタンスをもつノードを一方の端位置に有し、キーワードＫＷ３に等しいインスタンスをもつノードを他方の端位置に有する、パターン（第３パターンという）をパターンデータベース１５から取得する（Ｓ４１１）。
【０１０５】
次に、パターンマージ部１７Ａは、第１パターンと第２パターンとを、それぞれに共通に含まれる共通部分があればその共通部分でマージする（Ｓ４１３）。また、パターンマージ部１７Ａは、第１パターンと第３パターン、第２パターンと第３パターン、についても同様のことを行う（Ｓ４１５）。これにより、図２７に示すような、パターンが生成される。
【０１０６】
次に、グラフ検索部１８が、そのパターンをクエリに変換し、それをデータベースインタフェース１９に送信する（Ｓ４１７）ことで、そのパターンにマッチするサブグラフをグラフＧから取得する（Ｓ４１９）。これにより、図２７に示すような、パターンと同じサブグラフが検索される。
【０１０７】
そして、グラフ検索部１８は、図２２の式により、各サブグラフのサブグラフスコアを計算する（Ｓ４２１）。
【０１０８】
次に、グラフ検索部１８は、サブグラフをサブグラフスコアの順にソートする（Ｓ４２３）。ここで、複数のサブグラフを共通のインスタンスをもつノードでマージし、そのサブグラフのスコアとして、当該複数のサブグラフのサブグラフスコアの総和を計算してもよい。
【０１０９】
そして、出力用インタフェース生成部１１０が、各サブグラフがサブグラフスコアの高い順に並べた出力用インタフェースを生成し、これをユーザ端末２に送信し（Ｓ４２５）、表示させる（Ｓ４２７）。
【０１１０】
なお、本実施の形態では、ユーザ端末２での操作で特定されたキーワードが３つの場合を説明したが、４つ以上の場合でも、同様に処理を行えばよい。
【０１１１】
以上説明したように、第２の実施の形態によれば、グラフＧに含まれる特徴的なパスのパターンであって、インスタンスをもつノードを両方の端位置に有し、各アークがラベルをもつ、パターンが予め記憶されるパターン記憶手段（パターンデータベース１５）と、第１のキーワード（キーワードＫＷ１）に等しいインスタンスをもつノードを一方の端位置に有し、第２のキーワード（キーワードＫＷ２）に等しいインスタンスをもつノードを他方の端位置に有する、パターンである第１パターンをパターン記憶手段から検索し（Ｓ４０７）、第１のキーワードに等しいインスタンスをもつノードを一方の端位置に有し、第３のキーワード（キーワードＫＷ３）に等しいインスタンスをもつノードを他方の端位置に有する、パターンである第２パターンをパターン記憶手段から検索する（Ｓ４０９）パターン検索手段（パターン検索部１６Ａ）と、第１パターンと第２パターンとを、それぞれに共通に含まれる共通部分でマージする（Ｓ４１１）パターンマージ手段（パターンマージ部１７Ａ）と、このパターンマージ手段によりマージされたパターンにマッチするサブグラフをグラフＧから検索する（Ｓ４１９）グラフ検索手段（グラフ検索部１８）とを備えるので、第１のキーワードおよび第２のキーワードから検索されるサブグラフ（図２５（ａ）のパターンに等しいサブグラフ）と第１のキーワードおよび第３のキーワードから検索されるサブグラフ（図２５（ａ）のパターンに等しいサブグラフ）との関係が明確なサブグラフ（図２７に例示）を高速に検索することができる。ここでは、検索時にはパターンを生成しないので、高速な検索が行える。また、その際には、パターンの指定が不要である。
【０１１２】
また、グラフＧから、予め決めた内容をラベルに含むアークの先端が接続されたノードを両方の端位置に有するパスであるパターンを生成し（Ｓ２０５）、パターン記憶手段に記憶させる（Ｓ２０７）パターン生成手段を備えるので、より詳しくは、グラフＧのアークがもつ各ラベルのスコアまたはグラフＧがもつノードに定義された各クラスのスコアが記憶された記憶手段（アークスコア記憶部１３やクラススコア記憶部）と、グラフＧから、予め決めた内容をラベルに含むアークの先端が接続されたノードを両方の端位置に有するパスを検索し（Ｓ２０１）、当該パスのスコアを記憶手段に記憶されたスコアに基づいて計算し（Ｓ２０３）、スコアが予め定めたしきい値より大きいパターンをパターン記憶手段に記憶させる（Ｓ２０７）パターン生成手段（パターン生成部１４Ａ）とを備えるので、前記したパターン検索が行えるようになる。
【図面の簡単な説明】
【０１１３】
【図１】第１の実施の形態に係るグラフ検索装置の構成図である。
【図２】グラフＧの一部を例示した図である。
【図３】グラフＧを表示するためのデータ群の一部を例示した図である。
【図４】アークスコア記憶部に記憶されたアークスコアの一部を示した図である。
【図５】アークスコアの一部をグラフに当てはめた図である。
【図６】パターンを生成するときのフローチャートを示した図である。
【図７】ノードスコアの計算式を示した図である。
【図８】ノードスコア計算の例にしたグラフを示す図である。
【図９】パススコアの計算式を示した図である。
【図１０】パスグループのスコアの計算式を示した図である。
【図１１】生成されたパターンを例示した図である。
【図１２】クラススコア記憶部に記憶されたクラススコアの一部を示した図である。
【図１３】パターンを生成する別のフローチャートを示した図である。
【図１４】クラススコアの一部をグラフに当てはめた図である。
【図１５】クラススコアの計算式を示した図である。
【図１６】パススコアの計算式を示した図である。
【図１７】パススコアの再計算式を示した図である。
【図１８】第１の実施の形態のシーケンス図である。
【図１９】表示された入力用インタフェースを例示した図である。
【図２０】マージされたパターンを例示した図である。
【図２１】検索されたサブグラフを例示した図である。
【図２２】サブグラフスコアの計算式を示した図である。
【図２３】第２の実施の形態に係るグラフ検索装置の構成図である。
【図２４】パターンを生成するときのフローチャートを示した図である。
【図２５】生成されたパターンを例示した図である。
【図２６】第２の実施の形態のシーケンス図である。
【図２７】マージされたパターンを例示した図である。
【図２８】従来のグラフ検索装置で検索されるサブグラフを例示した図である。
【符号の説明】
【０１１４】
１、１Ａ…グラフ検索装置
２…ユーザ端末
３…表示装置
１１…グラフデータベース
１２…入力用インタフェース生成部
１３…アークスコア記憶部
１４、１４Ａ…パターン生成部
１５…パターンデータベース
１６、１６Ａ…パターン検索部
１７、１７Ａ…パターンマージ部
１８…グラフ検索部
１９…データベースインタフェース
１１０…出力用インタフェース生成部
【図１】
0004628258.tif 000002
【図２】
0004628258.tif 000003
【図３】
0004628258.tif 000004
【図４】
0004628258.tif 000005
【図５】
0004628258.tif 000006
【図６】
0004628258.tif 000007
【図７】
0004628258.tif 000008
【図８】
0004628258.tif 000009
【図９】
0004628258.tif 000010
【図１０】
0004628258.tif 000011
【図１１】
0004628258.tif 000012
【図１２】
0004628258.tif 000013
【図１３】
0004628258.tif 000014
【図１４】
0004628258.tif 000015
【図１５】
0004628258.tif 000016
【図１６】
0004628258.tif 000017
【図１７】
0004628258.tif 000018
【図１８】
0004628258.tif 000019
【図１９】
0004628258.tif 000020
【図２０】
0004628258.tif 000021
【図２１】
0004628258.tif 000022
【図２２】
0004628258.tif 000023
【図２３】
0004628258.tif 000024
【図２４】
0004628258.tif 000025
【図２５】
0004628258.tif 000026
【図２６】
0004628258.tif 000027
【図２７】
0004628258.tif 000028
【図２８】
0004628258.tif 000029