(57)【要約】【課題】多様性を有するクエリを生成できるクエリ生成装置を提供する。【解決手段】代表のパスが増えたことで、グループＧ１３に関連する箇所のクエリの数が増加し、閾値（例えば、１）以上となっている。このようにクエリの数が全て閾値以上となったなら、代表のパスを組み合わせたもののみからなるクエリを検索する。【選択図】図１５
2012038023.tif 000002
【特許請求の範囲】
【請求項１】
インスタンスおよび該インスタンスを示すクラスを有するノードを２以上有するデータで構成される２つのデータセットをマージして得られたデータセットから、データを検索するためのキーワードを示すものとして予め定められたクラスを有するノードと、検索されたデータにおける目的のインスタンスを示すものとして予め定められたクラスを有するノードとを結ぶデータを取得し、該データのインスタンスを変数に置き換えて得られたクエリが記憶されるクエリ記憶手段と、
前記クエリに含まれるノードによる１本の経路のみからなるパスを前記２つのデータセットに共通するノードに該当するノードで分割するパス生成手段と、
当該分割されたパスが記憶されるパス記憶手段と、
前記パス記憶部のパスを該パスの両端のノードのインスタンスを示すクラスの組ごとのグループに分類するパス分類手段と、
前記パス記憶部のパスの一方端のノードに該ノードのインスタンスとして所定の検索ワードを代入し、該パスに対して変数以外で合致するデータを前記マージされたデータセットから検索するデータ検索手段と、
前記各グループで該グループ内の各パスを対象とし、対象のパスにより検索されたデータの他方端のノードのインスタンスの集合と、該対象でないパスにより検索されたデータの他方端のノードのインスタンスの集合とを取得し、前者の集合のインスタンス数を各集合の和集合のインスタンス数で除した値を計算し、予め定めた閾値より高い該値に対応するパスを代表のパスとして該グループから選択する代表パス選択手段と、
異なるグループの代表のパスどうしをマージし且つマージ後のパスが前記キーワードに対応するノードと前記目的のインスタンスに対応するノードとを結ぶものとなるようにするパスマージ手段と、
該マージされたパスが記憶される代表パス記憶手段と、
前記クエリ記憶手段から該マージされたパスを含むクエリを検索し、マージ前の各パスが属していたグループの組のそれぞれにつき、該検索されたクエリの数が予め定められた数以上となるように、前記代表パス選択手段に対して閾値を調整するように指示する第１のクエリ検索手段と、
検索されたクエリの数が予め定められた数以上となったなら、前記クエリ記憶手段から該マージされたパスのみからなるクエリを検索する第２のクエリ検索手段と
を備えることを特徴とするクエリ生成装置。
【請求項２】
前記第２のクエリ検索手段は、前記クエリ記憶手段から、２以上のマージされたパスのみからなるクエリを検索する
ことを特徴とする請求項１記載のクエリ生成装置。
【請求項３】
インスタンスおよび該インスタンスを示すクラスを有するノードを２以上有するデータで構成される２つのデータセットをマージして得られたデータセットから、データを検索するためのキーワードを示すものとして予め定められたクラスを有するノードと、検索されたデータにおける目的のインスタンスを示すものとして予め定められたクラスを有するノードとを結ぶデータを取得し、該データのインスタンスを変数に置き換えて得られたクエリが記憶されるクエリ記憶手段を備えるクエリ生成装置の動作方法であって、
前記クエリに含まれるノードによる１本の経路のみからなるパスを前記２つのデータセットに共通するノードに該当するノードで分割し、当該分割されたパスをパス記憶手段に記憶させるパス生成工程と、
前記パス記憶部のパスを該パスの両端のノードのインスタンスを示すクラスの組ごとのグループに分類するパス分類工程と、
前記パス記憶部のパスの一方端のノードに該ノードのインスタンスとして所定の検索ワードを代入し、該パスに対して変数以外で合致するデータを前記マージされたデータセットから検索するデータ検索工程と、
前記各グループで該グループ内の各パスを対象とし、対象のパスにより検索されたデータの他方端のノードのインスタンスの集合と、該対象でないパスにより検索されたデータの他方端のノードのインスタンスの集合とを取得し、前者の集合のインスタンス数を各集合の和集合のインスタンス数で除した値を計算し、予め定めた閾値より高い該値に対応するパスを代表のパスとして該グループから選択する代表パス選択工程と、
異なるグループの代表のパスどうしをマージし且つマージ後のパスが前記キーワードに対応するノードと前記目的のインスタンスに対応するノードとを結ぶものとなるようにし、該マージされたパスを代表パス記憶手段に記憶させるパスマージ工程と、
前記クエリ記憶手段から該マージされたパスを含むクエリを検索し、マージ前の各パスが属していたグループの組のそれぞれにつき、該検索されたクエリの数が予め定められた数以上となるように、前記代表パス選択手段に対して閾値を調整するように指示する第１のクエリ検索工程と、
検索されたクエリの数が予め定められた数以上となったなら、前記クエリ記憶手段から該マージされたパスのみからなるクエリを検索する第２のクエリ検索工程と
を備えることを特徴とするクエリ生成装置の動作方法。
【請求項４】
前記第２のクエリ検索工程は、前記クエリ記憶手段から、２以上のマージされたパスのみからなるクエリを検索することを特徴とする請求項３記載のクエリ生成装置の動作方法。
【請求項５】
請求項１または２記載のクエリ生成装置としてコンピュータを機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クエリ生成装置およびその動作方法に関するものである。
【背景技術】
【０００２】
近年、セマンティックWebやLinked Dataの活用分野が広がっている。このような技術により、複数のサイトで保有されていた異種のデータセットが結合され、以前は検索できなかったデータが検索可能となった。
【０００３】
このようなデータセットを用いて、あるキーワードに関連する語などを得るには、データセットから生成されたクエリにキーワードを含ませ、このクエリに合致するデータをデータセットから検索し、検索されたデータから目的の語などを取り出す。
【０００４】
統合されたデータセットについては、多数のクエリが生成されるため、クエリの数を絞り込む必要がある。
【０００５】
しかし、単にクエリの数を絞り込んでしまうと、あるキーワードを使用した場合には目的の語などが得られるが、他のキーワードを使用した場合には得られないという可能性がある。つまり、絞り込んだクエリにおいて、多様性が欠如してしまうのである。
【０００６】
また、多様性を確保できた場合であっても、得られた語などに必ずしも信頼性があるとは限らない。
【０００７】
従来においては、多数のクエリグラフパターンの中から、ユーザの関心に沿ったものをランキングの上位として表示するものがある（非特許文献１）。
【０００８】
しかし、ユーザの関心を反映するための重み付けをどのようなルールで誰が行うかという問題が解決していない。
【０００９】
また、クエリグラフパターンを構成するパスの長さを制限することで、クエリグラフパターンの数を絞り込むものがある（非特許文献２）。
【００１０】
しかし、長いパスで構成されるクエリグラフパターンによる検索でしか得られなった情報が得られなくなる可能性がある。
【００１１】
また、パスの長さを制限して得た情報は、キーワードとの関連性は高いが、信頼性は必ずしも高くない。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００６−３１３５０１号公報
【非特許文献】
【００１３】
【非特許文献１】”SemRank: ranking complex relationship search results on the semantic web”、［ｏｎｌｉｎｅ］、［平成２２年７月１３日検索］、インターネット＜ＵＲＬ：http://lsdis.cs.uga.edu/library/download/AMS05-WWW2005.pdf＞
【非特許文献２】”What have Innsbruck and Leipzig in common? Extracting Semantics from Wiki Content”、［ｏｎｌｉｎｅ］、［平成２２年７月１３日検索］、インターネット＜ＵＲＬ：http://www.informatik.uni-leipzig.de/~auer/publication/ExtractingSemantics.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、多様性を有するクエリを生成できるクエリ生成装置およびその動作方法を提供することにある。
【００１５】
また、信頼性を有する語などを得るのに適し且つ多様性を有するクエリを生成できるようにすることが、さらなる目的である。
【課題を解決するための手段】
【００１６】
上記の課題を解決するために、第１の本発明は、インスタンスおよび該インスタンスを示すクラスを有するノードを２以上有するデータで構成される２つのデータセットをマージして得られたデータセットから、データを検索するためのキーワードを示すものとして予め定められたクラスを有するノードと、検索されたデータにおける目的のインスタンスを示すものとして予め定められたクラスを有するノードとを結ぶデータを取得し、該データのインスタンスを変数に置き換えて得られたクエリが記憶されるクエリ記憶手段と、前記クエリに含まれるノードによる１本の経路のみからなるパスを前記２つのデータセットに共通するノードに該当するノードで分割するパス生成手段と、当該分割されたパスが記憶されるパス記憶手段と、前記パス記憶部のパスを該パスの両端のノードのインスタンスを示すクラスの組ごとのグループに分類するパス分類手段と、前記パス記憶部のパスの一方端のノードに該ノードのインスタンスとして所定の検索ワードを代入し、該パスに対して変数以外で合致するデータを前記マージされたデータセットから検索するデータ検索手段と、前記各グループで該グループ内の各パスを対象とし、対象のパスにより検索されたデータの他方端のノードのインスタンスの集合と、該対象でないパスにより検索されたデータの他方端のノードのインスタンスの集合とを取得し、前者の集合のインスタンス数を各集合の和集合のインスタンス数で除した値を計算し、予め定めた閾値より高い該値に対応するパスを代表のパスとして該グループから選択する代表パス選択手段と、異なるグループの代表のパスどうしをマージし且つマージ後のパスが前記キーワードに対応するノードと前記目的のインスタンスに対応するノードとを結ぶものとなるようにするパスマージ手段と、該マージされたパスが記憶される代表パス記憶手段と、前記クエリ記憶手段から該マージされたパスを含むクエリを検索し、マージ前の各パスが属していたグループの組のそれぞれにつき、該検索されたクエリの数が予め定められた数以上となるように、前記代表パス選択手段に対して閾値を調整するように指示する第１のクエリ検索手段と、検索されたクエリの数が予め定められた数以上となったなら、前記クエリ記憶手段から該マージされたパスのみからなるクエリを検索する第２のクエリ検索手段とを備えることを特徴とするクエリ生成装置をもって解決手段とする。
【００１７】
例えば、前記第２のクエリ検索手段は、前記クエリ記憶手段から、２以上のマージされたパスのみからなるクエリを検索する。
【００１８】
第２の本発明は、インスタンスおよび該インスタンスを示すクラスを有するノードを２以上有するデータで構成される２つのデータセットをマージして得られたデータセットから、データを検索するためのキーワードを示すものとして予め定められたクラスを有するノードと、検索されたデータにおける目的のインスタンスを示すものとして予め定められたクラスを有するノードとを結ぶデータを取得し、該データのインスタンスを変数に置き換えて得られたクエリが記憶されるクエリ記憶手段を備えるクエリ生成装置の動作方法であって、前記クエリに含まれるノードによる１本の経路のみからなるパスを前記２つのデータセットに共通するノードに該当するノードで分割し、当該分割されたパスをパス記憶手段に記憶させるパス生成工程と、前記パス記憶部のパスを該パスの両端のノードのインスタンスを示すクラスの組ごとのグループに分類するパス分類工程と、前記パス記憶部のパスの一方端のノードに該ノードのインスタンスとして所定の検索ワードを代入し、該パスに対して変数以外で合致するデータを前記マージされたデータセットから検索するデータ検索工程と、前記各グループで該グループ内の各パスを対象とし、対象のパスにより検索されたデータの他方端のノードのインスタンスの集合と、該対象でないパスにより検索されたデータの他方端のノードのインスタンスの集合とを取得し、前者の集合のインスタンス数を各集合の和集合のインスタンス数で除した値を計算し、予め定めた閾値より高い該値に対応するパスを代表のパスとして該グループから選択する代表パス選択工程と、異なるグループの代表のパスどうしをマージし且つマージ後のパスが前記キーワードに対応するノードと前記目的のインスタンスに対応するノードとを結ぶものとなるようにし、該マージされたパスを代表パス記憶手段に記憶させるパスマージ工程と、前記クエリ記憶手段から該マージされたパスを含むクエリを検索し、マージ前の各パスが属していたグループの組のそれぞれにつき、該検索されたクエリの数が予め定められた数以上となるように、前記代表パス選択手段に対して閾値を調整するように指示する第１のクエリ検索工程と、検索されたクエリの数が予め定められた数以上となったなら、前記クエリ記憶手段から該マージされたパスのみからなるクエリを検索する第２のクエリ検索工程とを備えることを特徴とするクエリ生成装置の動作方法をもって解決手段とする。
【００１９】
例えば、前記第２のクエリ検索工程は、前記クエリ記憶手段から、２以上のマージされたパスのみからなるクエリを検索する。
【発明の効果】
【００２０】
本発明によれば、マージ前の代表のパスが属していたグループの組のそれぞれにつき、検索されたクエリの数が予め定められた数以上となるようにするので、多様性を有するクエリを得ることができる。
【図面の簡単な説明】
【００２１】
【図１】本実施の形態に係るクエリグラフパターン生成装置の構成要素を含むデータ検索装置のブロック図である。
【図２】データセットＤ１を構成するデータを示す図である。
【図３】データセットＤ３のＲＤＦのインスタンス同士の接続関係をクラス同士の関係に置き換えて表した図である。
【図４】クエリの一例を示す図である。
【図５】分割後の各クエリの部分を示す図である。
【図６】クエリの分割の様子を示す図である。
【図７】データセットＤ１から生成されたパスの分類の様子を示す図である。
【図８】データセットＤ２から生成されたパスの分類の様子を示す図である。
【図９】パスに検索ワードを含ませた様子を示す図である。
【図１０】検索ワードを含むパスと検索されるデータを示す図である。
【図１１】グループＧ１３から代表のパスが選択される様子を示す図である。
【図１２】パスがマージされる様子を示す図である。
【図１３】代表のパスをマージしたものによる１回目の検索の集計の結果を示す図である。
【図１４】任意のパスをマージしたものによる検索の集計の結果を示す図である。
【図１５】代表のパスをマージしたものによる２回目の検索の集計の結果を示す図である。
【図１６】パスＨ１、Ｈ２と、これらのパスから検索されたクエリＱ１０１とを示す図である。
【図１７】クエリにキーワードを含ませる様子を示す図である。
【図１８】「インターネット」を含ませたクエリＱ１０１について、クラスの値、プロパティ、有向性までも全て図示したものである。
【図１９】クエリにキーワードを含ませものから検索されたデータの例を示す図である。
【発明を実施するための形態】
【００２２】
以下、本発明の実施の形態について図面を参照して説明する。なお、一部の用語として、ＲＤＦ（Resource Description Framework）の技術用語を用いる。
【００２３】
図１は、本実施の形態に係るクエリ生成装置の構成要素を含むデータ検索装置のブロック図である。
【００２４】
データ検索装置１は、データセットＤ１を記憶するデータセット記憶部１１と、データセットＤ２を記憶するデータセット記憶部１２と、データセットＤ１、Ｄ２をマージ（結合）するデータセットマージ部１３と、マージ後のデータセットＤ３を記憶するデータセット記憶部１４と、外部から入力されるパラメータを基にデータセットＤ３からクエリグラフパターン（略してクエリという）を生成するクエリ生成部１５と、生成されたクエリが記憶されるクエリ記憶部１６と、クエリからパスを生成するパス生成部１７と、生成されたパスが記憶されるパス記憶部１８と、パスを複数のグループに分類するパス分類部１９と、データセットＤ３内の検索ワードを適用したパスに合致するデータをデータセットＤ３から検索するデータ検索部１０１と、検索されたデータを基にグループから代表のパスを選択する代表パス選択部１０２と、パス同士をマージするパスマージ部１０３と、マージされた代表のパスおよびマージできなかった単独の代表のパスが記憶される代表パス記憶部１０４と、マージされた任意のパスおよびマージできなかった単独の任意のパスが記憶されるパス記憶部１０５と、代表パス記憶部１０４やパス記憶部１０５のパスに合致するパスを含むクエリをクエリ記憶部１６から検索するクエリ検索部１０６と、クエリ記憶部１６から代表パス記憶部１０４の複数のパスのみからなるクエリを検索するクエリ検索部１０７と、検索されたクエリが記憶されるクエリ記憶部１０８と、クエリ記憶部１０８のクエリにキーワードを代入し、代入後のクエリに合致するデータをデータセットＤ３から検索するデータ検索部１０９とを備える。
【００２５】
図２は、データセットＤ１を構成するデータを示す図である。
【００２６】
図２（ａ）、（ｂ）に示すように、最小単位のデータは、２つのノードの一方を示す情報（ノードという）と、他方を示す情報（ノードという）と、ノード間を結ぶアークを示す情報（アークという）からなるラベル付き有向グラフデータである。
【００２７】
ノードは、インスタンスという値（「インターネット」、「卒業研究課題」、「田中一郎」など）を有する。ノードは、インスタンスの種類を示すクラスという値（「技術用語」、「研究課題」、「教職員」など）を有する。クラス「研究課題」を有するノードのインスタンスは、「研究課題」という種類に属する「卒業研究課題」などである。クラス「教職員」を有するノードのインスタンスは、「教職員」という種類に属する「田中一郎」である。
【００２８】
なお、クラス「技術用語」を有するノード（キーワードノード）のインスタンスは、外部から入力されるキーワードに一致するか否かの判定対象であり、データ検索装置１では、キーワードノードは特殊ノードとして扱われている。
【００２９】
アークは、有向性を有し、つまり、どちらかのノードに向き、プロパティという値を有する。アークの向きは、ノードの関係に応じたものとなっている。
【００３０】
図２（ａ）のデータは、「インターネットに関する卒業研究課題がある」という事実により得られたもので、アークの向きは「卒業研究課題」から「インターネット」を導くという動作に対応している。プロパティは、「インターネットに関する卒業研究課題がある」を「インターネットが卒業研究課題の技術用語である」と言い換えられることから、「技術用語」となっている。
【００３１】
図２（ｃ）は、図２（ａ）、（ｂ）のデータをマージ（結合）したものである。
【００３２】
データセットＤ１では、２つのデータに同じノード（「「卒業研究課題」のノード）がある場合、２つのデータはそのノードで互いに関連づけられる。これを、便宜的に、２つのデータがマージされたという。図２（ｃ）は、マージ後のデータを示している。
【００３３】
データセットＤ１は、マージ可能な多数のデータを有し、マージが繰り返され、網の目状となっている。
【００３４】
データセットＤ１は、例えば、大学関連のデータとなっている。
【００３５】
一方、データセットＤ２は、例えば、ＳＮＳ（Social Networking Service）となっている。図示しないが、データセットＤ２も、データセットＤ１と同様なデータからなり、網の目状となっている。
【００３６】
図１に戻り、まず、データセットマージ部１３は、データセットＤ１、Ｄ２に共に存在し且つクラスとインスタンスが共に互いに等しいノードを同一化しそのノードでデータセットＤ１、Ｄ２をマージする。データセットマージ部１３は、マージ後のデータセットＤ３をデータセット記憶部１４に記憶させる。
【００３７】
図３は、データセットＤ３のＲＤＦのインスタンス同士の接続関係をクラス同士の関係に置き換えて表した図である。この図では例えば技術用語をクラスとするインスタンスと研究課題をクラスとするインスタンスがアークによって結ばれたＲＤＦのトリプルが存在する事を示している。
【００３８】
図３は、クラス「技術用語」とクラス「教職員」とでマージされたデータセットＤ３のＲＤＦのインスタンス同士の接続関係をクラス同士の関係に置き換えて示している。各ノード（マージノード）は、データセットＤ１、Ｄ２のそれぞれにあったものである。
【００３９】
図１に戻り、データ検索装置１は、キーワード「インターネット」に詳しい「教職員」の名前（例えば、「田中一郎」）を調べるのに先立ち、外部からキーワード「インターネット」、パラメータ「教職員」を入力する。
【００４０】
クエリ生成部１５は、パラメータ「教職員」を基にデータセットＤ３からクエリを生成し、生成されたクエリをクエリ記憶部１６に記憶させる。
【００４１】
クエリ生成部１５は、具体的には、まず、特殊ノードつまりクラス「技術用語」を有するノード（キーワードノード）と、パラメータに等しいクラス「教職員」を有するノード（ゴールノード）と、これらのノードを結ぶ１以上のアークまたはこれらのノードを１以上の経路で結ぶアークおよびノードとからなるデータをデータセットＤ３から全て取得する。
【００４２】
次に、クエリ生成部１５は、各データの各ノードのインスタンスをノードのクラスに応じた変数に置き換える。なお、クエリ生成部１５は、データのアークの有向性を示す値およびプロパティは置き換えずに残しておく。こうして得たものが全てクエリである。
【００４３】
図１に戻り、パス生成部１７は、クエリ記憶部１６に記憶された全てのクエリから可能な限りパスを生成し、生成されたパスをパス記憶部１８に記憶させる。
【００４４】
図４は、クエリの一例を示す図である。
【００４５】
パス生成部１７は、具体的には、まず、図４に示すような、キーワードノードとゴールノードを複数の経路（アークまたはアークとノードからなる）で結ぶクエリを検索する。
【００４６】
クエリＱ１では、クラス「技術用語」を有するノードに応じた変数「？技術用語」を有するノードがキーワードノードであり、クラス「教職員」に応じた変数「？教職員」を有するノードがゴールノードである。他のノードも同様に、「？」とクラスの値（「研究課題」など）からなる変数を有する。
【００４７】
図５は、分割後の各クエリの部分を示す図である。
【００４８】
パス生成部１７は、次に、図５（ａ）、（ｂ）に示すように、該当のクエリを経路ごとに分割する。分割後の各クエリは、キーワードノードとゴールノードを１つの経路で結ぶクエリとなる。
【００４９】
次に、パス生成部１７は、分割後のクエリおよび元々キーワードノードとゴールノードを１つの経路で結ぶクエリをさらに分割する。
【００５０】
図６は、クエリの分割の様子を示す図である。
【００５１】
パス生成部１７は、具体的には、図６に示すように、まず、キーワードノードとゴールノード以外のノード（中間ノード）で、且つ、マージノード（クラス「技術用語」、または、「教職員」を有するノード）に該当するノード（マージノード）を有するクエリを検索する。
【００５２】
ここで、パス生成部１７は、例えば、データセットＤ１、Ｄ２をマージした際に、マージノードとして記憶されたノードを中間ノードとして有するクエリを検索する。
【００５３】
または、パス生成部１７は、例えば、予め各データセットのノードに該当のデータセットを示す識別情報（名前など）が付与されているなら、両方の識別情報を有するノードつまりマージノードを中間ノードとして有するクエリを検索する。
【００５４】
図６の変数「？教職員」を有するノードは、図３のクラス「教職員」を有するマージノードのインスタンスを変数「？教職員」に置き換えたものであり、よって、マージノードである。
【００５５】
パス生成部１７は、次に、図６に示すように、該当のクエリをマージノードで分割する。分割後のクエリは、キーワードノードとマージノードを１つの経路で結ぶクエリとなる。
【００５６】
パス生成部１７は、分割後のクエリにマージノードがある場合は、さらにクエリをマージノードで分割する。元々中間ノード且つマージノードを有していなかったクエリおよび分割後のクエリが全てパスである。
【００５７】
図１に戻り、次に、パス分類部１９が、パス記憶部１８の全てのパスを複数のグループに分類する。
【００５８】
パス分類部１９は、具体的には、まず、全てのパスを、データセットＤ１から生成されたパスのグループと、データセットＤ２から生成されたパスのグループとに分類する。
【００５９】
次に、パス分類部１９は、各グループのパスを、両端のノードが有するクラスの値の組み合わせによって分類する。
【００６０】
図７は、データセットＤ１から生成されたパスの分類の様子を示す図である。
【００６１】
データセットＤ１から生成されたパスでは、両端のノードのクラスの値は、「技術用語」、「教職員」のいずれかなので、パスは、両端のクラスの値が共に「技術用語」のグループＧ１１、両端のクラスの値が共に「教職員」のグループＧ１２、一方端のクラスの値が「技術用語」且つ他方端のクラスの値が「教職員」のグループＧ１３、に分類される。
【００６２】
グループＧ１１には、パスＧ１１１、１１２が含まれる。グループＧ１２には、パスＧ１２１、１２２が含まれる。グループＧ１３には、パスＧ１３１、１３２、１３３が含まれる。
【００６３】
図８は、データセットＤ２から生成されたパスの分類の様子を示す図である。
【００６４】
データセットＤ２から生成されたパスも、同様に、３つのグループＧ２１、Ｇ２２、Ｇ２３に分類される。
【００６５】
グループＧ２１には、パスＧ２１１、２１２、２１３が含まれる。グループＧ２２には、パスＧ２２１、２２２が含まれる。グループＧ２３には、パスＧ２３１、２３２、２３３が含まれる。
【００６６】
よって、パスは６グループに分類される。
【００６７】
なお、パス分類部１９は、パスにそのパスが属するグループのＩＤなどを付与する。
【００６８】
図１に戻り、データ検索部１０１は、パス記憶部１８のパスにデータセットＤ３内の検索ワードを適用し、適用後のパスに合致するデータをデータセットＤ３から検索する。
【００６９】
データ検索部１０１は、まず、パスにおける端のノードのクラスの値ごとに、該値と同じクラスを有するノードのインスタンスをデータセットＤ３から重複しないように１以上（便宜的に２とする）取得する。取得されたインスタンスを以下、検索ワードという。
【００７０】
図７、図８の例では、クラスの値は、「技術用語」、「教職員」の２つなので、データ検索部１０１は、「技術用語」から２つの検索ワード（以下、検索ワードＳＷ１１、ＳＷ１２）を取得し、「教職員」から２つの検索ワード（以下、検索ワードＳＷ２１、ＳＷ２２）を取得する。
【００７１】
データ検索部１０１は、まず、各グループについて以下のことを行う。
【００７２】
図９は、パスに検索ワードを含ませた様子を示す図である。
【００７３】
つまり、データ検索部１０１は、図９に示すように、グループＧ１１については、検索ワードＳＷ１１、ＳＷ１２のいずれかを一方端のインスタンスとして含ませたパスを生成する。こうして、パスＧ１１１からパスＰ１１、１２が生成され、パスＧ１１２からパスＰ２１、２２が生成され、データ検索部１０１は、他のグループＧ１２〜Ｇ２３についても同様の処理を行う。
【００７４】
図１０は、検索ワードを含むパスと検索されるデータを示す図である。
【００７５】
次に、データ検索部１０１は、図１０に一例を示すような、パスＰ１１に対し変数（「？研究課題」など）以外で全てが合致する全てのデータをデータセットＤ３から検索する。図１０では、検索ワードＳＷ１１は「特許」である。また、図１０では、図９では省略したクラスの値、プロパティ、有向性までも全て図示している。また、データ検索部１０１は、他のパスＰ１２、２１、２２についても同様の検索を行う。
【００７６】
また、データ検索部１０１は、他のグループＧ１２〜Ｇ２３についても同様の処理を行う。
【００７７】
そして、データ検索部１０１は、検索されたデータを代表パス選択部１０２に送信する。
【００７８】
図１に戻り、代表パス選択部１０２は、データを基にグループから代表のパスを選択する。
【００７９】
代表パス選択部１０２は、複数のパスを含むグループのそれぞれにおいて、当該グループに属する各パスを対象に値の集合Ｍを計算する。集合Ｍは、対象のパス（対象パス）が、同じグループの対象でない各パス（非対象パス）に対して有する特性を示す特性値ｍからなる集合である。
【００８０】
例えば、グループＧ１１においては、パスＧ１１１が対象の集合Ｍは、パスＧ１１１がパスＧ１１２に対して有する特性を示す特性値ｍのみからなる。また、パスＧ１１２が対象の集合Ｍは、パスＧ１１２がパスＧ１１１に対して有する特性を示す特性値ｍのみからなる。
【００８１】
例えば、グループＧ１３においては、パスＧ１３１が対象の集合Ｍは、パスＧ１３１がパスＧ１３２に対して有する特性を示す特性値ｍ、パスＧ１３１がパスＧ１３３に対して有する特性を示す特性値ｍからなる。パスＧ１３２が対象の集合Ｍは、パスＧ１３２がパスＧ１３１に対して有する特性を示す特性値ｍ、パスＧ１３２がパスＧ１３３に対して有する特性を示す特性値ｍからなる。パスＧ１３３が対象の集合Ｍは、パスＧ１３３がパスＧ１３２に対して有する特性を示す特性値ｍ、パスＧ１３３がパスＧ１３１に対して有する特性を示す特性値ｍからなる。
【００８２】
代表パス選択部１０２は、このような特性値ｍを以下の式（１）により計算する。
【数１】
2012038023.tif 000003
【００８３】
ただし、ｋｉは、該当のグループについて使用された各検索ワード
Ｑ１（ｋｉ）は、検索ワードｋｉの適用後の対象パスから検索されたデータの集合、
Ｑ２（ｋｉ）は、検索ワードｋｉの適用後の非対象パスから検索されたデータの集合、
Ｑ１（ｋｉ）∪Ｑ２（ｋｉ）は、集合Ｑ１（ｋｉ）と集合Ｑ２（ｋｉ）の和集合、
｜Ｑ１（ｋｉ）∪Ｑ２（ｋｉ）｜は、和集合Ｑ１（ｋｉ）∪Ｑ２（ｋｉ）に含まれるデータ数、
｜Ｑ１（ｋｉ）｜は、集合Ｑ１（ｋｉ）に含まれるデータ数、
Σは、データ数｜Ｑ１（ｋｉ）｜をデータ数｜Ｑ１（ｋｉ）∪Ｑ２（ｋｉ）｜で除した値を各検索ワードについて求めて総和したもの、
｜Ｋ｜は、各検索ワードｋｉの集合Ｍに含まれる検索ワード数、である。
【００８４】
つまり、特性値ｍは、対象パスから検索されたデータの集合で非対象パスから検索されたデータの集合をどの程度網羅できるかを示す値である。
【００８５】
代表パス選択部１０２は、次に、例えば、グループＧ１１においては、パスＧ１１１が対象の集合Ｍ、パスＧ１１２が対象の集合Ｍの２つから、予め定めた閾値より大きい特性値ｍを有する集合Ｍを選択し、グループＧ１１においては、選択された集合Ｍに対応するパスを代表として選択する。
【００８６】
代表パス選択部１０２は、例えば、グループＧ１３においては、パスＧ１３１が対象の集合Ｍ、パスＧ１３２が対象の集合Ｍ、パスＧ１３３が対象の集合Ｍの３つから、前記閾値より大きい特性値ｍのみからなる集合Ｍを選択し、グループＧ１３においては、選択された集合Ｍに対応するパスを代表として選択する。
【００８７】
図１１は、グループＧ１３から代表のパスが選択される様子を示す図である。
【００８８】
パスＧ１３１が対象の集合Ｍは、パスＧ１３２に対する特性値２９．３％、パスＧ１３３に対する特性値６４．７％からなる。
【００８９】
パスＧ１３２が対象の集合Ｍは、パスＧ１３１に対する特性値７１．０％、パスＧ１３３に対する特性値８２．３％からなる。
【００９０】
パスＧ１３３が対象の集合Ｍは、パスＧ１３１に対する特性値３６．０％、パスＧ１３２に対する特性値２０．３％からなる。
【００９１】
よって、閾値が７０％の場合、パスＧ１３２が対象の集合Ｍが選択され、パスＧ１３２が代表として選択される。
【００９２】
なお、代表パス選択部１０２は、代表のパスにその旨を示すフラグなどを付与する。
【００９３】
また、代表パス選択部１０２は、各集合Ｍ内の特性値ｍの平均または最大値を求め、この値が最も大きいものに対応するパスを代表のパスとして選択してもよい。
【００９４】
図１に戻り、パスマージ部１０３は、まず、パス記憶部１８から取りだした２つの代表のパスを、一方のパスの一方端のノードのクラスと他方のパスの一方端のノードのクラスとが同じ且つ一方のパスの他方端のノードのクラスが「技術用語」であり且つ他方のパスの他方端のノードのクラスが「教職員」なら、同じクラスのノードで２つのパスをマージし、これを全ての可能な組み合わせで行い、マージされたパス並びに元々一方端のクラスが「技術用語」であり且つ他方端のノードのクラスが「教職員」である単独のパスを全て代表パス記憶部１０４に記憶させる。
【００９５】
図１２は、パスがマージされる様子を示す図である。
【００９６】
パスマージ部１０３は、例えば、図１２に示すように、パスＧ１３１とパスＧ１２２が代表なら、これらをクラス「教職員」を有するノードでマージし、パスＨ１を生成する。
【００９７】
なお、例えば、グループＧ１１のパスの両端のクラスは「技術用語」であり、グループＧ１２のパスの両端のクラスは「教職員」であるから、これらのパスはマージできず、代表パス記憶部１０４にも記憶されない。
【００９８】
また、例えば、グループＧ１１のパスの両端のクラスは「技術用語」であるから、これらのパスは、単独のパスとしても代表パス記憶部１０４に記憶されない。
【００９９】
図１に戻り、パスマージ部１０３は、代表か否かによらず、任意のパスについても同じ処理を行う。
【０１００】
パスマージ部１０３は、パス記憶部１８から取りだした２つの任意のパスを、一方のパスの一方端のノードのクラスと他方のパスの一方端のノードのクラスとが同じ且つ一方のパスの他方端のノードのクラスが「技術用語」であり且つ他方のパスの他方端のノードのクラスが「教職員」なら、同じクラスのノードで２つのパスをマージし、これを全ての可能な組み合わせで行い、マージされたパス並びに元々一方端のクラスが「技術用語」であり且つ他方端のノードのクラスが「教職員」である単独のパスを全てパス記憶部１０５に記憶させる。なお、マージの方法は、代表のパスのマージと同様である。
【０１０１】
次に、クエリ検索部１０６が、代表パス記憶部１０４のパスに合致するパスを含むクエリをクエリ記憶部１６から検索し、検索されたクエリ数を、該当のパスが属していたグループまたはグループの組み合わせごとに集計する。
【０１０２】
図１３は、代表のパスをマージしたものによる１回目の検索の集計の結果を示す図である。
【０１０３】
図１３に示すように、例えば、グループＧ１１のパス同士をマージできず、よって、グループＧ１１同士の組については、検索自体がなされない。これが、Ｇ１１の列とＧ１１の行の交点が×印で示されている。
【０１０４】
また、グループＧ１１のパスとグループＧ１２のパスをマージできず、よって、グループＧ１１、Ｇ１２の組については、検索自体がなされない。これが、Ｇ１１の列とＧ１２の行の交点が×印で示されている。
【０１０５】
また、グループＧ１１のパスの両端のクラスは「技術用語」なので、Ｇ１１の列と最下行の交点が×印で示されている。
【０１０６】
一方、グループＧ１１のパスとグループＧ１３のパスはマージでき、検索されたクエリ数は「２」であった。
【０１０７】
また、グループＧ１２のパスとグループＧ１３のパスはマージでき、検索されたクエリ数は「０」であった。
【０１０８】
図１３は、他のグループまたはグループの組み合わせについても検索の有無、さらには、検索されたクエリの数を示している。
【０１０９】
また、クエリ検索部１０６は、パス記憶部１０５のパスに合致するパスを含むクエリをクエリ記憶部１６から検索し、検索されたクエリ数を、該当のパスが属していたグループまたはグループの組み合わせごとに集計する。
【０１１０】
図１４は、任意のパスをマージしたものによる検索の集計の結果を示す図である。
【０１１１】
図１４は、グループＧ１２のパスとグループＧ１３のパスはマージでき、検索されたクエリ数は「４１」であったことを示している。
【０１１２】
クエリ検索部１０６は、図１３のように、検索されたクエリ数が０の箇所にグループを特定する。図１３では、クエリ数が０の箇所が２箇所あり、共通するのは、グループＧ１３であるから、グループＧ１３が特定される。
【０１１３】
また、クエリ検索部１０６は、検索されたクエリ数が０の箇所に対応する、図１４のクエリ数が所定の閾値（例えば、１）以上なら、代表パス選択部１０２に対し、特定されたグループＧ１３については、代表のパスを選択するのに用いた閾値を低くして、再び代表のパスを同様の方法で選択するように指示する。
【０１１４】
図１３では、クエリの数が０の箇所が２箇所あり、図１４では、対応する箇所のクエリの数が４１、１５なので、例えば、閾値が１なら、クエリ検索部１０６は、代表パス選択部１０２に指示を行う。
【０１１５】
代表パス選択部１０２は、例えば、図１０において、閾値を例えば、２５％に変更し、これにより、パスＧ１３１、１３２が代表として選択される。つまり、代表の数が２に増加する。
【０１１６】
パスマージ部１０３は、代表のパスが再選択されたら、代表のパスのマージを再び行う。
【０１１７】
クエリ検索部１０６は、代表のパスのマージが再び行われたら、集計を再び行う。
【０１１８】
図１５は、代表のパスをマージしたものによる２回目の検索の集計の結果を示す図である。
【０１１９】
代表のパスが増えたことで、グループＧ１３に関連する箇所のクエリの数が増加し、閾値（例えば、１）以上となっている。
【０１２０】
図１に戻り、クエリ検索部１０７は、このようにクエリの数が全て閾値以上となったなら、クエリ記憶部１６から、代表パス記憶部１０４の複数のパスのみからなるクエリを検索し、検索されたクエリをクエリ記憶部１０８に記憶させる。
【０１２１】
図１６は、パスＨ１、Ｈ２と、これらのパスから検索されたクエリＱ１０１とを示す図である。
【０１２２】
クエリＱ１０１は、キーワードノードとゴールノードを複数の経路（アークまたはアークとノードからなる）で結ぶクエリであり、一方の経路はパスＨ１に相当し、他方の経路はパスＨ２に相当する。経路は３以上であってもよい。
【０１２３】
クエリ検索部１０７は、クエリＱ１０１をパスＨ１、Ｈ２から検索するように、このような条件を満たすクエリを全て検索する。
【０１２４】
図１に戻り、次に、データ検索部１０９は、クエリ記憶部１０８のクエリにキーワード「インターネット」を代入し、代入後のクエリに合致するデータをデータセットＤ３から検索する。
【０１２５】
具体的には、データ検索部１０９は、クエリを読み出し、例えば、「インターネット」を、クエリにキーワードノードのインスタンスとして含ませ、代入後のクエリに合致するデータをデータセットＤ３から検索する。
【０１２６】
図１７は、クエリにキーワードを含ませる様子を示す図である。
【０１２７】
データ検索部１０９は、図１７に示すように、例えば、クエリＱ１０１のキーワードノードにインスタンスとして「インターネット」を含ませる。
【０１２８】
図１８は、「インターネット」を含ませたクエリＱ１０１について、クラスの値、プロパティ、有向性までも全て図示したものである。
【０１２９】
図１９は、クエリにキーワードを含ませたものから検索されたデータの例を示す図である。
【０１３０】
データ検索部１０９は、図１８のクエリＱ１０１に対し変数（「？論文」など）以外で全てが合致する、図１９のデータＤ２０３のようなデータをデータセットＤ３から検索する。かかるデータは、「インターネット」に詳しい「教職員」の名前は「田中一郎」であることを示している。
【０１３１】
よって、データ検索部１０９は、ゴールノードのインスタンスを外部に出力する。
【０１３２】
これにより、外部では「インターネット」に詳しい「教職員」の名前は「田中一郎」であることがわかる。
【０１３３】
以上説明したように、データ検索装置１は、インスタンスおよび該インスタンスを示すクラスを有するノードを２以上有するデータで構成される２つのデータセットをマージするデータセットマージ手段（１３）と、マージされたデータセットが記憶されるデータセット記憶手段（１４）と、該データセットから、データを検索するためのキーワードを示すものとして予め定められたクラスを有するノード（キーワードノード）と、検索されたデータにおける目的のインスタンスを示すものとして予め定められたクラスを有するノード（ゴールノード）とを結ぶデータを取得し、該データのインスタンスを変数に置き換えたクエリを生成するクエリ生成手段（１５）と、該クエリが記憶されるクエリ記憶手段（１６）と、該クエリに含まれるノードによる１本の経路のみからなるパスを前記２つのデータセットに共通するノードに該当するノードで分割するパス生成手段（１７）と、当該分割されたパスが記憶されるパス記憶手段（１８）と、前記パス記憶部のパスを該パスの両端のノードのインスタンスを示すクラスの組ごとのグループに分類するパス分類手段（１９）と、前記パス記憶部のパスの一方端のノードに該ノードのインスタンスとして所定の検索ワードを代入し、該パスに対して変数以外で合致するデータを前記マージされたデータセットから検索するデータ検索手段（１０１）と、前記各グループで該グループ内の各パスを対象とし、対象のパスにより検索されたデータの他方端のノードのインスタンスの集合と、該対象でないパスにより検索されたデータの他方端のノードのインスタンスの集合とを取得し、前者の集合のインスタンス数を各集合の和集合のインスタンス数で除した値を式（１）により計算し、予め定めた閾値より高い該値に対応するパスを代表のパスとして該グループから選択する代表パス選択手段（１０２）と、異なるグループの代表のパスどうしをマージし且つマージ後のパスが前記キーワードに対応するノードと前記目的のインスタンスに対応するノードとを結ぶものとなるようにするパスマージ手段（１０３）と、該マージされたパスが記憶される代表パス記憶手段（１０４）と、前記クエリ記憶部から該マージされたパスを含むクエリを検索し、マージ前の各パスが属していたグループの組のそれぞれにつき、該検索されたクエリの数が予め定められた数以上となるように、前記代表パス選択手段に対して閾値を調整するように指示する第１のクエリ検索手段（１０６）と、検索されたクエリの数が予め定められた数以上となったなら、前記クエリ記憶部から該マージされたパスのみからなるクエリを検索する第２のクエリ検索手段（１０７）とを備える。
【０１３４】
つまり、マージ前の代表のパスが属していたグループの組のそれぞれにつき、検索されたクエリの数が予め定められた数以上となるようにするので、多様性を有するクエリを得ることができる。
【０１３５】
また、前記第２のクエリ検索手段は、前記クエリ記憶部から、２以上のマージされたパスのみからなるクエリを検索するので、信頼性を有する目的のインスタンスを得るのに適したクエリを得ることができる。
【０１３６】
なお、本実施の形態に係るクエリグラフパターン生成装置としてコンピュータを機能させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。
【符号の説明】
【０１３７】
１…データ検索装置
１１…データセット記憶部
１２…データセット記憶部
１３…データセットマージ部
１４…データセット記憶部
１５…クエリ生成部
１６…クエリ記憶部
１７…パス生成部
１８…パス記憶部
１９…パス分類部
１０１…データ検索部
１０２…代表パス選択部
１０３…パスマージ部
１０４…代表パス記憶部
１０５…パス記憶部
１０６…クエリ検索部
１０７…クエリ検索部
１０８…クエリ記憶部
１０９…データ検索部
【図１】
2012038023.tif 000004
【図２】
2012038023.tif 000005
【図３】
2012038023.tif 000006
【図４】
2012038023.tif 000007
【図５】
2012038023.tif 000008
【図６】
2012038023.tif 000009
【図７】
2012038023.tif 000010
【図８】
2012038023.tif 000011
【図９】
2012038023.tif 000012
【図１０】
2012038023.tif 000013
【図１１】
2012038023.tif 000014
【図１２】
2012038023.tif 000015
【図１３】
2012038023.tif 000016
【図１４】
2012038023.tif 000017
【図１５】
2012038023.tif 000018
【図１６】
2012038023.tif 000019
【図１７】
2012038023.tif 000020
【図１８】
2012038023.tif 000021
【図１９】
2012038023.tif 000022