(57)【要約】【課題】所望のサブグラフの発見を容易にするグラフ検索装置を提供する。【解決手段】グラフデータベース１１にデータ群を記憶されたグラフＧからサブグラフを複数検索するグラフ検索部１６と、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数ＧＮの、一方または両方を用いて、計算するスコア計算部１７と、各サブグラフをそのスコアの高い順に並べて表示させる出力用インタフェース生成部１９とを備えるので、所望のサブグラフを容易に発見することができる。【選択図】図１
2007140714.tif 000002
【特許請求の範囲】
【請求項１】
インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索するグラフ検索手段と、
各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算するスコア計算手段と、
各サブグラフをそのスコアの高い順に並べて表示させる表示制御手段と
を備えることを特徴とするグラフ検索装置。
【請求項２】
前記スコア計算手段は、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算し、
前記表示制御手段は、各ノードのインスタンスをそのスコアの高い順に並べて表示させることを特徴とする請求項１記載のグラフ検索装置。
【請求項３】
前記グラフ検索手段は、インスタンスをもつノード間がアークによって接続された第２のグラフから、前記検索したサブグラフの部分に共通な共通部分を検索し、
前記スコア計算手段は、当該共通部分があった場合、当該サブグラフのスコアを増加させる
ことを特徴とする請求項１または２記載のグラフ検索装置。
【請求項４】
前記グラフは、互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフであり、
このグラフから、指定されたキーワードに等しいインスタンスをもつノードに接続されたアークのラベルを取得し、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラスが定義されたノードを他方の端位置に有する、パターンを生成するパターン生成手段を備え、
前記グラフ検索手段が、
このパターンにマッチするサブグラフを前記グラフから検索し、
前記パターン生成手段が、
検索されたサブグラフの中で、指定されたクラスが定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせであって、第１および第２サブグラフのそれぞれが、前記指定されたキーワードに等しいインスタンスをもつノードである第１ノードと前記指定されたクラスが定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードに当該指定されたクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置き換え、第１ノードのインスタンスとして前記指定されたキーワードを設定してなるパターンを生成し、
前記グラフ検索手段が、
このパターンにマッチするサブグラフを前記グラフから検索する
ことを特徴とする請求項１ないし３のいずれかに記載のグラフ検索装置。
【請求項５】
インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索するグラフ検索手段と、
各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算し、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算するスコア計算手段と、
各ノードのインスタンスをそのスコアの高い順に並べて表示させる表示制御手段と
を備えることを特徴とするグラフ検索装置。
【請求項６】
インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索するグラフ検索手段と、
各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算するスコア計算手段と、
各サブグラフをそのスコアの高い順に並べて表示させる表示制御手段と
を備えるグラフ検索装置の制御方法であって、
前記グラフ検索手段が、インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索し、
前記スコア計算手段が、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算し、
前記表示制御手段が、各サブグラフをそのスコアの高い順に並べて表示させる
ことを特徴とするグラフ検索装置の制御方法。
【請求項７】
前記スコア計算手段は、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算し、
前記表示制御手段は、各ノードのインスタンスをそのスコアの高い順に並べて表示させることを特徴とする請求項６記載のグラフ検索装置の制御方法。
【請求項８】
前記グラフ検索手段は、インスタンスをもつノード間がアークによって接続された第２のグラフから、前記検索したサブグラフの部分に共通な共通部分を検索し、
前記スコア計算手段は、当該共通部分があった場合、当該サブグラフのスコアを増加させる
ことを特徴とする請求項６または７記載のグラフ検索装置の制御方法。
【請求項９】
前記グラフは、互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフであり、
前記グラフ検索装置に設けられたパターン生成手段が、当該グラフから、指定されたキーワードに等しいインスタンスをもつノードに接続されたアークのラベルを取得し、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラスが定義されたノードを他方の端位置に有する、パターンを生成し、
前記グラフ検索手段が、
このパターンにマッチするサブグラフを前記グラフから検索し、
前記パターン生成手段が、
検索されたサブグラフの中で、指定されたクラスが定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせであって、第１および第２サブグラフのそれぞれが、前記指定されたキーワードに等しいインスタンスをもつノードである第１ノードと前記指定されたクラスが定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードに当該指定されたクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置き換え、第１ノードのインスタンスとして前記指定されたキーワードを設定してなるパターンを生成し、
前記グラフ検索手段が、
このパターンにマッチするサブグラフを前記グラフから検索する
ことを特徴とする請求項６ないし８のいずれかに記載のグラフ検索装置の制御方法。
【請求項１０】
インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索するグラフ検索手段と、
各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算し、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算するスコア計算手段と、
各ノードのインスタンスをそのスコアの高い順に並べて表示させる表示制御手段と
を備えるグラフ検索装置の制御方法であって、
前記グラフ検索手段が、インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索し、
前記スコア計算手段が、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算し、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算し、
前記表示制御手段が、各ノードのインスタンスをそのスコアの高い順に並べて表示させることを特徴とするグラフ検索装置の制御方法。
【請求項１１】
請求項１ないし５のいずれかに記載のグラフ検索装置としてコンピュータを動作させるコンピュータプログラム。
【請求項１２】
請求項１１記載のコンピュータプログラムが格納された記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所望のサブグラフの発見を容易にするグラフ検索装置に関するものである。
【背景技術】
【０００２】
従来のグラフ検索装置は、あるグラフから例えば、図１８に示すような、クエリにマッチするサブグラフを複数検索して表示する。各サブグラフは、例えば、検索された順に並べて表示される。なお、非特許文献１には、そのようなグラフ検索の仕様が規定されている。
【０００３】
また、非特許文献２に記載のAGM.(Apriori-based Graph Mining)というグラフマイニングを用いたグラフ検索装置は、ラベル付きグラフから頻出のサブグラフを検索する。
【０００４】
他にFSG、gSpanと呼ばれる手法でも同様の検索が行える。
【非特許文献１】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)
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、検索された順に多数のサブグラフを表示した場合、所望のサブグラフの発見が困難になる。
【０００６】
非特許文献１では、クエリにマッチするサブグラフを検索することの記載があり、非特許文献２では、頻出のサブグラフを検索することの記載があるが、いずれの文献においても、表示の際の並び順の記載がない。
【０００７】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、所望のサブグラフの発見を容易にするグラフ検索装置を提供することにある。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、請求項１の本発明は、インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索するグラフ検索手段と、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算するスコア計算手段と、各サブグラフをそのスコアの高い順に並べて表示させる表示制御手段とを備えることを特徴とするグラフ検索装置をもって解決手段とする。
【０００９】
請求項２の本発明は、前記スコア計算手段は、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算し、前記表示制御手段は、各ノードのインスタンスをそのスコアの高い順に並べて表示させることを特徴とする請求項１記載のグラフ検索装置をもって解決手段とする。
【００１０】
請求項３の本発明は、前記グラフ検索手段は、インスタンスをもつノード間がアークによって接続された第２のグラフから、前記検索したサブグラフの部分に共通な共通部分を検索し、前記スコア計算手段は、当該共通部分があった場合、当該サブグラフのスコアを増加させることを特徴とする請求項１または２記載のグラフ検索装置をもって解決手段とする。
【００１１】
請求項４の本発明は、前記グラフは、互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフであり、このグラフから、指定されたキーワードに等しいインスタンスをもつノードに接続されたアークのラベルを取得し、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラスが定義されたノードを他方の端位置に有する、パターンを生成するパターン生成手段を備え、前記グラフ検索手段が、このパターンにマッチするサブグラフを前記グラフから検索し、前記パターン生成手段が、検索されたサブグラフの中で、指定されたクラスが定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせであって、第１および第２サブグラフのそれぞれが、前記指定されたキーワードに等しいインスタンスをもつノードである第１ノードと前記指定されたクラスが定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードに当該指定されたクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置き換え、第１ノードのインスタンスとして前記指定されたキーワードを設定してなるパターンを生成し、前記グラフ検索手段が、このパターンにマッチするサブグラフを前記グラフから検索することを特徴とする請求項１ないし３のいずれかに記載のグラフ検索装置をもって解決手段とする。
【００１２】
請求項５の本発明は、インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索するグラフ検索手段と、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算し、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算するスコア計算手段と、各ノードのインスタンスをそのスコアの高い順に並べて表示させる表示制御手段とを備えることを特徴とするグラフ検索装置をもって解決手段とする。
【００１３】
請求項６の本発明は、インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索するグラフ検索手段と、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算するスコア計算手段と、各サブグラフをそのスコアの高い順に並べて表示させる表示制御手段とを備えるグラフ検索装置の制御方法であって、前記グラフ検索手段が、インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索し、前記スコア計算手段が、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算し、前記表示制御手段が、各サブグラフをそのスコアの高い順に並べて表示させることを特徴とするグラフ検索装置の制御方法をもって解決手段とする。
【００１４】
請求項７の本発明は、前記スコア計算手段は、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算し、前記表示制御手段は、各ノードのインスタンスをそのスコアの高い順に並べて表示させることを特徴とする請求項６記載のグラフ検索装置の制御方法をもって解決手段とする。
【００１５】
請求項８の本発明は、前記グラフ検索手段は、インスタンスをもつノード間がアークによって接続された第２のグラフから、前記検索したサブグラフの部分に共通な共通部分を検索し、前記スコア計算手段は、当該共通部分があった場合、当該サブグラフのスコアを増加させることを特徴とする請求項６または７記載のグラフ検索装置の制御方法をもって解決手段とする。
【００１６】
請求項９の本発明は、前記グラフは、互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフであり、前記グラフ検索装置に設けられたパターン生成手段が、当該グラフから、指定されたキーワードに等しいインスタンスをもつノードに接続されたアークのラベルを取得し、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラスが定義されたノードを他方の端位置に有する、パターンを生成し、前記グラフ検索手段が、このパターンにマッチするサブグラフを前記グラフから検索し、前記パターン生成手段が、検索されたサブグラフの中で、指定されたクラスが定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせであって、第１および第２サブグラフのそれぞれが、前記指定されたキーワードに等しいインスタンスをもつノードである第１ノードと前記指定されたクラスが定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードに当該指定されたクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出し、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置き換え、第１ノードのインスタンスとして前記指定されたキーワードを設定してなるパターンを生成し、前記グラフ検索手段が、このパターンにマッチするサブグラフを前記グラフから検索することを特徴とする請求項６ないし８のいずれかに記載のグラフ検索装置の制御方法をもって解決手段とする。
【００１７】
請求項１０の本発明は、インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索するグラフ検索手段と、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算し、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算するスコア計算手段と、各ノードのインスタンスをそのスコアの高い順に並べて表示させる表示制御手段とを備えるグラフ検索装置の制御方法であって、前記グラフ検索手段が、インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索し、前記スコア計算手段が、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算し、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算し、前記表示制御手段が、各ノードのインスタンスをそのスコアの高い順に並べて表示させることを特徴とするグラフ検索装置の制御方法をもって解決手段とする。
【００１８】
請求項１１の本発明は、請求項１ないし５のいずれかに記載のグラフ検索装置としてコンピュータを動作させるコンピュータプログラムをもって解決手段とする。
【００１９】
請求項１２の本発明は、請求項１１記載のコンピュータプログラムが格納された記録媒体をもって解決手段とする。
【発明の効果】
【００２０】
本発明のグラフ検索装置によれば、インスタンスをもつノード間がアークによって接続されたグラフからサブグラフを複数検索するグラフ検索手段と、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータと、検索されたサブグラフの数の、一方または両方を用いて、計算するスコア計算手段と、各サブグラフをそのスコアの高い順に並べて表示させる表示制御手段とを備えるので、所望のサブグラフを容易に発見することができる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施の形態を図面を参照して説明する。なお、同一のものには同一符号を付与し、重複説明を省略する。
【００２２】
［第１の実施の形態］
図１は、第１の実施の形態に係るグラフ検索装置の構成図である。
【００２３】
グラフ検索装置１は、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００２４】
グラフ検索装置１は、有向グラフであるグラフＧを表示するためのデータ群が記憶されたグラフデータベース１１と、グラフのサブグラフを検索する際に表示装置３に表示される入力用インタフェースを生成する入力用インタフェース生成部１２とを備える。
【００２５】
図２は、グラフデータベース１１に記憶されたデータ群を全て使って表示できるグラフＧの一部を例示した図である。
【００２６】
グラフデータベース１１に記憶されたデータ群を全て使って、図２に一部を例示したグラフＧ、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフＧ、を表示することができる。逆にいえば、グラフＧを表示するための過不足ないデータ群がグラフデータベース１１に記憶されている。以下、そのデータ群を便宜的にグラフＧという。また、なんらかのグラフ、サブグラフ（なんらかのグラフそのものまたはそれに含まれるグラフ）、パス（分岐および閉ループをもたないグラフ）などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
【００２７】
グラフＧでは、例えば、「ＸＭＬ」や「Ｂプロジェクト」などのインスタンスをもつノードが、「ｒｍ：技術キーワード」や「ｒｍ：著者」などのラベルをもつアークで接続される。また、グラフＧでは、ノードにそのインスタンス「Ｐｅｒｓｏｎ：山田太郎」などの概念であるクラス「Ｐｅｒｓｏｎ：人」などが定義される。
【００２８】
図３に示すように、「Ｔ−０４１」で示され、その元データの著者が山田太郎でり、題名が「セマンティックｗｅｂ」入門であり、キーワードがセマンティックｗｅｂである、元データは、グラフデータベース１１では、ＲＤＦ／ＸＭＬ形式のデータとなって、グラフデータベース１１に記憶され、これがグラフＧのサブグラフをなす。「ＲＤＦのグラフ表現」と題されたものは、このサブグラフをグラフィカルに表現したものである。ＲＤＦについては、以下の文献に記載されている。
【００２９】
「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/>
図４は、グラフデータベース１１に記憶されたデータ群の一部を例示した図である。
【００３０】
例えば、最初のデータ「＜ｏｒｇ：Ｄプロジェクト＞＜ｒｍ：技術キーワード＞”ＸＭＬ”」は、インスタンス「ｏｒｇ：Ｄプロジェクト」をもつノードからインスタンス「ＸＭＬ」のノードへ向かうアークがラベル「ｒｍ：技術キーワード」をもつことを示している。また、例えば、最後のデータ「＜Ｐｅｒｓｏｎ：鈴木花子＞＜ｒｄｆ：ｔｙｐｅ＞＜Ｐｅｒｓｏｎ：人＞」は、インスタンス「Ｐｅｒｓｏｎ：鈴木花子」をもつノードのクラスが「Ｐｅｒｓｏｎ：人」であることを示している。
【００３１】
なお、各データは、実際にはＲＤＦで表現されている。
【００３２】
図１に戻り、グラフ検索装置１は、グラフデータベース１１から検索されたサブグラフからなるグラフあるいはユーザに関するグラフ（これらを区別せずに、グラフＨと総称する）が記憶された第２グラフデータベース１３を備える。よって、この第２グラフデータベース１３には、図４と同様の形式のデータが記憶されている。
【００３３】
また、グラフ検索装置１は、サブグラフの検索に用いられるパターンが記憶されたパターンデータベース１４を備える。
【００３４】
図５は、パターンデータベース１４に記憶されたパターンのうちの４パターンをグラフ化して例示した図である。
【００３５】
パターンは、グラフデータベース１１に記憶されるデータ群（グラフＧ）の一部をなすデータ群と同様なものであり、それを本図のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。なお、データ群である実際のパターンを逐一説明するのは冗長なのでグラフ化されたパターンで便宜的に説明する。
【００３６】
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、図に示すように、？とそれに後続する単語からなる。
【００３７】
ここでは、予め決めた内容（例えば「キーワード」）をインスタンスに含むアークの先端が接続されたノード（キーワードノード）を一方の端位置に有し、予め決めたクラス（例えばクラス「Ｐｅｒｓｏｎ：人」）が定義されたノードを他方の端位置に有し、各ノードがインスタンスをもたず、各アークがラベルをもつ、パターンＰａ、Ｐｂ、Ｐｃ、Ｐｄがパターンデータベース１４に記憶されていることとする。
【００３８】
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。
【００３９】
つまり、検索されるのは、（１）そのグラフまたはそのサブグラフであって、（２）パターンの構造を過不足なく有し、（３）パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有し、（４）場合によってはパターンに含まれるクラスが定義されたノードの位置に等しい位置にあるノードが当該クラスの下位概念であるインスタンスを有するものである。
【００４０】
なお、パターンにより、このようにしてサブグラフを検索することを、パターンにマッチするサブグラフを検索するという。
【００４１】
図１に戻り、また、グラフ検索装置１は、パターンデータベース１４からパターンを検索するパターン検索部１５と、グラフＧのサブグラフを検索するグラフ検索部１６と、サブグラフのスコアを計算するスコア計算部１７と、パターン検索部およびグラフ検索部と各データベースとを中継するデータベースインタフェース１８と、表示装置３に表示される出力用インタフェースを生成する出力用インタフェース生成部１９とを備える。
【００４２】
グラフ検索装置１は、各部（データベース含む）でデータの送受信（受け渡し）が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータをグラフ検索装置として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。第２の実施の形態でも同様である。
【００４３】
（第１の実施の形態の動作）
図６は、グラフＧからサブグラフを検索するときのシーケンス図である。
【００４４】
グラフ検索装置１では、入力用インタフェース生成部１２が入力用インタフェースを生成し、それをユーザ端末２に送信して（Ｓ１）、図７のように表示させる（Ｓ３）。ここでの操作により特定されたキーワードＫＷ（例えば、キーワード「セマンティックｗｅｂ」）およびクラスＣＬ（例えば、クラスＣＬを「Ｐｅｒｓｏｎ：人」）を、ユーザ端末２がグラフ検索装置１に送信する（Ｓ５）。
【００４５】
グラフ検索装置１では、パターン検索部１５が、クラスＣＬを含む検索構文であるクエリをデータベースインタフェース１８に送信し、これにより、クラスＣＬが定義されたノードを一方の端位置に有するパターンをパターンデータベース１４から検索する（Ｓ７）。
【００４６】
次に、グラフ検索部１６が、そのパターンをクエリに変換し、それをデータベースインタフェースに送信する（Ｓ９）ことで、そのパターンにマッチするサブグラフをグラフＧから取得する（Ｓ１１）。
【００４７】
なお、このパターンは、ユーザ端末２での操作により検索されたものであるが、ここで使用するものとして予めグラフ検索装置１が記憶したパターンを用いてよい。また、この検索は、ユーザ端末２での操作により行われるが、これを予め決めた時刻に行ってもよい。また、キーワードＫＷとクラスＣＬは、ユーザ端末２での操作によりグラフ検索装置１が得るものであるが、かかるキーワードＫＷとクラスＣＬの一方または両方を予めグラフ検索装置１が記憶しておき、それを用いてもよい。これは第２の実施の形態でも同様である。
【００４８】
さて、前述のＳ１１を行うことで、ここでは、図５のパターンＰａから、図８に太線で示したサブグラフＳＧａ１、図９に太線で示したサブグラフＳＧａ２、図１０に太線で示したサブグラフＳＧａ３が取得されたこととする。つまり、トータルでは、図１１に太線で示したサブグラフＳＧａが取得されたこととする。同様に、パターンＰｂ、Ｐｃ、Ｐｄからもサブグラフが取得される。
【００４９】
図６に戻り、このサブグラフがスコア計算部１７に与えられる（Ｓ１２）と、スコア計算部１７が、各サブグラフのスコアを計算する（Ｓ１３）。なお、ここでの計算では、与えられたサブグラフの数が利用されるが、この数をグラフ検索部１６がスコア計算部１７に通知するようにしてもよい。
【００５０】
Ｓ１３では、図１２に示す計算結果が得られるのだが、まずスコア計算部１７は、パターンＰａから検索されたサブグラフの数ＧＮａを計算する。パターンＰａから検索されたのが、サブグラフＳＧａ１、ＳＧａ２、ＳＧａ３であるので、ＧＮａ＝３となる。同様に、パターンＰｂ、Ｐｃ、Ｐｄから検索されたサブグラフの数ＧＮｂ、ＧＮｃ、ＧＮｄを計算する。
【００５１】
また、スコア計算部１７は、各サブグラフの複雑さを示すパラメータとして、パスの数ＰＮとアークの数ＡＮを計算する。
【００５２】
具体的には、まず、パターンＰａから検索されたサブグラフに含まれるパスの数ＰＮａ（＝５）を計算する。同様に、パターンＰｂ、Ｐｃ、Ｐｄから検索されたサブグラフに含まれるパスの数ＰＮｂ、ＰＮｃ、ＰＮｄを計算する。
【００５３】
そして、アークの数ＡＮの計算について、スコア計算部１７は、パターンＰａから検索されたサブグラフに含まれたアークであって、クラスＣＬを定義されたノードにつながるアーク、の数ＡＮａ（＝５）を計算する。同様に、パターンＰｂ、Ｐｃ、Ｐｄから検索されたサブグラフに含まれる当該アークの数ＡＮｂ、ＡＮｃ、ＡＮｄを計算する。
【００５４】
また、スコア計算部１７は、他のパターンＰｂ、Ｐｃ、Ｐｄについても同様な計算を行う。
【００５５】
次に、スコア計算部１７は、図１２に示す式により、図１１のサブグラフＳＧａにつき、その重要度を示すスコアＳａ（＝８．３３３３３３）を計算する。パターンＰｂ、Ｐｃ、Ｐｄの結果からも同様にスコアＳｂ、Ｓｃ、Ｓｄを計算する。
【００５６】
次に、スコア計算部１７は、サブグラフＳＧａ１に対し、その重要度を示すスコアＳａ１として、スコアＳａを対応づける。また、サブグラフＳＧａ２、ＳＧａ３についても、同様なことを行う。また、他のパターンＰｂ、Ｐｃ、Ｐｄについても同様なことを行う。
【００５７】
なお、ここでは、サブグラフのスコアを、サブグラフの複雑さを示すパラメータ（アークの数ＡＮやパスの数ＰＮなど）と、検索されたサブグラフの数ＧＮの両方を用いて計算したが、一方を用いてスコアを計算してもよい。
【００５８】
つまり、以下のようにして、サブグラフのスコアを計算してもよい。
【００５９】
サブグラフＳＧａ１を例にすると、そのスコアＳａ１は、アークの数ＡＮａまたはパスの数ＰＮａまたはこれらから計算されたスコアとしてもよい。または、スコアＳａ１は、パターンＰａから検索されたサブグラフに含まれる閉路や並行路の数（これらも複雑さのパラメータである）としてもよい。また、スコアＳａ１は、パターンＰａから検索されたサブグラフに含まれるラベルの種類の数（これらも複雑さのパラメータである）としてもよい。または、かかるパラメータを用いることにより、既に計算されたスコアＳａ１に対する重み付け（加算または減算）を行ってもよい。
【００６０】
また、サブグラフＳＧａ１を例にすると、そのスコアＳａ１は、サブグラフの数ＧＮａとしてもよい。
【００６１】
図６に戻り、次にスコア計算部１７が、各ノードのスコアを計算する（Ｓ１５）。
【００６２】
Ｓ１５では、図１３に示す計算結果が得られるのだが、まずスコア計算部１７は、クラスＣＬを定義された各ノードについて、パターンＰａから検索されたサブグラフの中でその１ノードを含むものを選択し、その選択されたサブグラフの合計数Ｔａを計算する。
【００６３】
具体的には、クラス「Ｐｅｒｓｏｎ：人」を定義されたノード（インスタンス「Ｐｅｒｓｏｎ：鈴木花子」をもつ）について、図８のサブグラフＳＧａ１には当該ノードが含まれず、図９のサブグラフＳＧａ２には当該ノードが含まれ、図１０のサブグラフＳＧａ３には当該ノードが含まれているので、当該ノードの合計数Ｔａ（鈴木花子）＝２と計算する。また、スコア計算部１７は、他のノードについても同様の計算を行う。また、スコア計算部１７は、他のパターンについても同様の計算を行う。これにより、クラス「Ｐｅｒｓｏｎ：人」を定義されたノード（インスタンス「Ｐｅｒｓｏｎ：鈴木花子」をもつ）についての、パターンＰｂによるサブグラフから合計数Ｔｂ（鈴木花子）、パターンＰｃによるサブグラフから合計数Ｔｃ（鈴木花子）、パターンＰｄによるサブグラフから合計数Ｔｂ（鈴木花子）が計算される。
【００６４】
そして、スコア計算部１７は、インスタンス「Ｐｅｒｓｏｎ：鈴木花子」をもつノードについて、その重要度を示すスコアＮＳ（鈴木花子）を次の式により計算する。
【００６５】
スコアＮＳ（鈴木花子）
＝Ｔａ（鈴木花子）×Ｓａ＋Ｔｂ（鈴木花子）×Ｓｂ
＋Ｔｃ（鈴木花子）×Ｓｃ＋Ｔｄ（鈴木花子）×Ｓｄ＝２．４
また、スコア計算部１７は、他のノードについても同様の計算を行う。
【００６６】
図６に戻り、次に、グラフ検索部１６が、サブグラフの部分をクエリに変換し、それをデータベースインタフェースに送信する（Ｓ１７）ことで、その部分にマッチする部分（つまり共通部分）をグラフＨ（第２グラフデータベース１３）から検索する（Ｓ１９）。共通部分が取得できたときは、クエリに変換する前の部分を含むサブグラフのスコアを増加させる（Ｓ２１）。共通部分の数が多いときにスコアが大きく増加するようにしてもよい。つまり、かかる数をパラメータとして用いることにより、既に計算されたスコアに対する重み付け（加算または減算）を行ってもよい。
【００６７】
次に、出力用インタフェース生成部１９が、各サブグラフをそのスコアの高い順に並べた出力用インタフェースと、各ノードのインスタンスをそのスコア順に並べた出力用インタフェースを生成し、これらをユーザ端末２に送信し（Ｓ２３）、表示させる（Ｓ２５）。
【００６８】
なお、第１の実施の形態では、Ｓ２１で行うようなスコア変更が不要ならば、第２グラフデータベース１３は不要である。
【００６９】
以上説明したように、第１の実施の形態によれば、グラフＧからサブグラフを複数検索する（Ｓ１１）グラフ検索手段（グラフ検索部１６）と、各サブグラフのスコアを、そのサブグラフの複雑さを示すパラメータ（アークの数ＡＮやパスの数ＰＮなど）と、検索されたサブグラフの数ＧＮの、一方または両方を用いて、計算する（Ｓ１３）スコア計算手段（スコア計算部１７）と、各サブグラフをそのスコアの高い順に並べて表示させる（Ｓ２３）表示制御手段（出力用インタフェース生成部１９）とを備えるので、所望のサブグラフを容易に発見することができる。
【００７０】
また、スコア計算手段は、各サブグラフに含まれる各ノードの重要度を示すスコアを、当該サブグラフのスコアをパラメータとして、計算し（Ｓ１５）、表示制御手段は、各ノードのインスタンスをそのスコアの高い順に並べて表示させる（Ｓ２３）ので、所望のノードを容易に発見することができる。
【００７１】
また、グラフ検索手段は、第２のグラフＨから、検索したサブグラフの部分に共通な共通部分を検索し（Ｓ１９）、スコア計算手段は、当該共通部分があった場合、当該サブグラフのスコアを増加させる（Ｓ２１）ので、所望のサブグラフの中でも、より必要性の高いサブグラフを容易に発見することができる。
【００７２】
なお、第１の実施の形態では、各ノードのインスタンスをそのスコア順に並べた出力用インタフェースを生成し、これらをユーザ端末２に送信し（Ｓ２３）、表示させる（Ｓ２５）ようにしてもよい。つまり、表示させる（Ｓ２３）のは、ノードのインスタンスだけとしてもよい。この場合であっても、後にサブグラフをそのスコアの高い順に表示させることができるので、所期の目的を達成することができる。
【００７３】
［第２の実施の形態］
図１４は、第２の実施の形態に係るグラフ検索装置の構成図である。
【００７４】
グラフ検索装置１Ａは、ユーザ端末２に接続され、ユーザ端末２には、表示装置３が接続されている。
【００７５】
グラフ検索装置１Ａは、グラフデータベース１１と、入力用インタフェース生成部１２と、第２グラフデータベース１３と、パターンデータベース１４と、グラフ検索部１６と、スコア計算部１７と、データベースインタフェース１８と、出力用インタフェース生成部１９とを備え、さらに、パターンを生成するパターン生成部１１０を備える。
【００７６】
（第２の実施の形態の動作）
図１５は、グラフＧからサブグラフを検索するときのシーケンス図（一部）である。
【００７７】
グラフ検索装置１に、キーワードＫＷおよびクラスＣＬが送信されるまで（Ｓ１、Ｓ３、Ｓ５）は、第１の実施の形態（図６）と同様である。
【００７８】
グラフ検索装置１Ａでは、パターン生成部１１０が、キーワードＫＷを含むクエリをデータベースインタフェースに送信する（Ｓ１０１）ことで、グラフＧにおいてキーワードＫＷに等しいインスタンスをもつノードに接続されたアークのラベルを取得する（Ｓ１０３）。
【００７９】
パターン生成部１１０は、例えばキーワードＫＷが「セマンティックＷｅｂ」のとき、図１６の太線のアークがもつ、下線のラベル「ｒｍ：技術キーワード」を取得する（Ｓ１０３）。
【００８０】
以下、これらのインスタンスが取得されたときのことについて説明する。
【００８１】
次に、パターン生成部１１０は、まず、このラベルを含むパス（パターンという）を生成する（Ｓ１０５）。具体的には、例えば、図１７に示すように、ラベル「ｍｓ：技術キーワード」をもつアークが一方の端位置のノード（キーワードノードという）に接続され、クラスＣＬが定義されたノード（対象クラスノードという）を他方の端位置に有する、パス（パターンＰｍという）を生成する。なお、キーワードノードと対象クラスノードという表現は、パターンＰｍで後に検索されるサブグラフでも用いることとする。
【００８２】
次に、グラフ検索部１６が、パターンＰｍをクエリに変換し、それをデータベースインタフェースに送信する（Ｓ１０７）ことで、そのパターンにマッチするサブグラフをグラフＧから取得する（Ｓ１０９）。
【００８３】
そして、パターン生成部１１０は、取得されたサブグラフの中で、対象クラスノードのインスタンスが同じもの同士を、対象クラスノードでマージする（Ｓ１１０）。
【００８４】
例えば、キーワードＫＷが「セマンティックＷｅｂ」のとき、Ｓ１１０では、キーワードノードのインスタンスが「セマンティックＷｅｂ」であるサブグラフが、マージにより、１以上生成される。また、その他のインスタンスをキーワードノードにもつサブグラフも１以上生成される。例えば、図１８に示すような、キーワードノードのインスタンスが「ＸＭＬ」であるサブグラフＳＧｍ１、ＳＧｍ２、ＳＧｍ３が生成される。
【００８５】
これ以降は、図１８に示すような、同じインスタンスをキーワードノードにもつサブグラフのグループについての処理が行われ、同様の処理が他のグループについても行われる。
【００８６】
なお、説明としては、図１８に示す各サブグラフについての処理を説明し、他のグループについての説明は省略する。
【００８７】
さて、図１８を例にすると、パターン生成部１１０は、サブグラフＳＧｍ１、ＳＧｍ２、ＳＧｍ３の中の１つ（例えばＳＧｍ１）またはそのサブグラフ（以下、第１サブグラフ）と他のサブグラフ（例えばＳＧｍ２）またはそのサブグラフ（以下、第２サブグラフ）とからなる組み合わせであって、第１および第２サブグラフのそれぞれが、キーワードノードと対象クラスノードとをそれぞれ端位置にもつ２以上のパスからなり且つ対象クラスノードのクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出する（Ｓ１１１）。
【００８８】
例えば、図１９に示すように、サブグラフＳＧｍ２にサブグラフＳＧｍ２ａが含まれているとすると、サブグラフＳＧｍ１とサブグラフＳＧｍ２ａとからなる組み合わせが検出される（Ｓ１１１）。
【００８９】
次に、パターン生成部１１０が、検出された組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置き換える（Ｓ１１３）。
【００９０】
次に、パターン生成部１１０が、そのサブグラフ（パターンという）がパターンデータベース１４になければそれを記憶させる（Ｓ１１５）。
【００９１】
例えば、図１８、図１９に示したサブグラフＳＧｍ１からは、図２０に示すパターンＰｍ１が生成され（Ｓ１１３）、それがなければパターンデータベース１４に記憶される（Ｓ１１５）。
【００９２】
次に、パターン生成部１１０が、生成したパターンのキーワードノードのインスタンスとしてキーワードＫＷを設定する（Ｓ１１７）。
【００９３】
例えば、図２０に示したパターンＰｍ１からは、図２１に示すパターンＰｍ１’が生成される（Ｓ１１７）。
【００９４】
以下、このパターンが、第１の実施の形態のＳ７で取得されたパターンと同様に扱われることとなる（Ｓ９〜Ｓ２５）。
【００９５】
以上説明したように、第２の実施の形態によれば、グラフＧから、指定されたキーワードに等しいインスタンスをもつノードに接続されたアークのラベルを取得し（Ｓ１０３）、取得したラベルをもつアークが一方の端位置のノードに接続され、指定されたクラスが定義されたノードを他方の端位置に有する、パターンを生成する（Ｓ１０５）パターン生成手段（パターン生成部１１０）を備え、グラフ検索手段は、このパターンにマッチするサブグラフをグラフＧから検索し（Ｓ１０９）、パターン生成手段は、検索されたサブグラフの中で、指定されたクラスが定義されたノードのインスタンスが同じもの同士を当該ノードでマージし、マージにより生成されたサブグラフまたはそのサブグラフである第１サブグラフと第２サブグラフとからなる組み合わせであって、第１および第２サブグラフのそれぞれが、前記指定されたキーワードに等しいインスタンスをもつノードである第１ノードと前記指定されたクラスが定義されたノードである第２ノードとをそれぞれ端位置にもつ２以上のパスからなり且つ当該第２ノードに当該指定されたクラスが定義されたサブグラフであって、第１サブグラフ内の各アークのラベルが当該各アークに対応する第２サブグラフの中でのアークのラベルに等しいという条件を満たす、組み合わせを検出し（Ｓ１１１）、検出した組み合わせの中の一方のサブグラフのノードのインスタンスを変数に置き換え（Ｓ１１３）、第１ノードのインスタンスとして前記指定されたキーワードを設定してなるパターンを生成し（Ｓ１１７）、グラフ検索手段は、このパターンにマッチするサブグラフをグラフＧから検索する（図６、Ｓ１１）ので、いままで検索できなかったサブグラフを検索することでができる。また、第１の実施の形態と同様に、その各サブグラフをそのスコアの高い順に並べて表示させるので、その各サブグラフから所望のサブグラフを容易に発見することができる。
【００９６】
なお、各実施の形態では、有向グラフを対象としたが、本発明を有向グラフでない、単にノードとアークとが接続されたグラフ（例えば、分子構造を表すグラフ）に利用してもよい。その際、グラフからサブグラフを検索する方法としては、ＡＧＭの方法つまり頻出のサブグラフを検索する方法（非特許文献２に記載）を採用してもよい。また、検索されたサブグラフの中で予め定められたインスタンスや予め定められたクラスを定義されたノードを含むサブグラフを検索し、これをグラフから検索されたサブグラフと同様に扱ってもよい。
【図面の簡単な説明】
【００９７】
【図１】第１の実施の形態に係るグラフ検索装置の構成図である。
【図２】グラフＧの一部を例示した図である。
【図３】ＲＤＦ／ＸＭＬ形式のデータ、その元データおよびこの形式のデータによるサブグラフを例示した図である。
【図４】グラフＧを表示するためのデータ群の一部を例示した図である。
【図５】パターンをグラフ化して例示した図である。
【図６】第１の実施の形態のシーケンス図である。
【図７】表示された入力用インタフェースを例示した図である。
【図８】サブグラフＳＧａ１を示した図である。
【図９】サブグラフＳＧａ２を示した図である。
【図１０】サブグラフＳＧａ３を示した図である。
【図１１】サブグラフＳＧａを示した図である。
【図１２】サブグラフのスコア計算結果を示した図である。
【図１３】ノードのスコアの計算結果を示した図である。
【図１４】第２の実施の形態に係るグラフ検索装置の構成図である。
【図１５】第２の実施の形態のシーケンス図である。
【図１６】キーワードノードへのアークとそのインスタンスを例示した図である。
【図１７】生成されたパターンＰｍを例示した図である。
【図１８】サブグラフＳＧｍ１、ＳＧｍ２、ＳＧｍ３を例示した図である。
【図１９】サブグラフの組み合わせが検出される様子を例示した図である。
【図２０】生成されたパターンＰｍ１を例示した図である。
【図２１】キーワードＫＷが設定されたパターンＰｍ１’を例示した図である。
【符号の説明】
【００９８】
１、１Ａ…グラフ検索装置
２…ユーザ端末
３…表示装置
１１…グラフデータベース
１２…入力用インタフェース生成部
１３…第２グラフデータベース
１４…パターンデータベース
１５…パターン検索部
１６…グラフ検索部
１７…スコア計算部
１８…データベースインタフェース
１９…出力用インタフェース生成部
１１０…パターン生成部
【図１】
2007140714.tif 000003
【図２】
2007140714.tif 000004
【図３】
2007140714.tif 000005
【図４】
2007140714.tif 000006
【図５】
2007140714.tif 000007
【図６】
2007140714.tif 000008
【図７】
2007140714.tif 000009
【図８】
2007140714.tif 000010
【図９】
2007140714.tif 000011
【図１０】
2007140714.tif 000012
【図１１】
2007140714.tif 000013
【図１２】
2007140714.tif 000014
【図１３】
2007140714.tif 000015
【図１４】
2007140714.tif 000016
【図１５】
2007140714.tif 000017
【図１６】
2007140714.tif 000018
【図１７】
2007140714.tif 000019
【図１８】
2007140714.tif 000020
【図１９】
2007140714.tif 000021
【図２０】
2007140714.tif 000022
【図２１】
2007140714.tif 000023