(57)【要約】【課題】グラフ構造データの中からユーザにより入力されたキーワードまたは概念などの情報に関連し且つ共通の意味合いの構造を持つ有意な情報を効率よく取得するクエリグラフパターンを生成可能な共通クエリグラフパターン生成装置、生成方法、および生成用プログラムを提供する。【解決手段】グラフ構造を持つ大量のデータの中からクエリグラフパターンが一致する情報を検索する際に、検索クエリグラフパターンの中から、ユーザに入力されたキーワードと同じラベルを持つアークにつながるノードとユーザに入力された概念のインスタンスであるノードとの間に存在するノードである中間ノードの数を制限するためのユーザから入力された情報を入力する入力部３１と、入力された中間ノードの数を制限するための情報に基づいて、検索クエリグラフパターンを生成する検索クエリグラフパターン生成部３２１とを有する。【選択図】図１
2010277322.tif 000002
【特許請求の範囲】
【請求項１】
グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、
ユーザから入力された検索対象のキーワードおよび概念を入力する入力手段と、
前記キーワードと同じラベルを持つアークにつながるノードと、前記概念のインスタンスであるノードとの間に存在するパスを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、
生成された検索クエリグラフパターンにマッチする前記グラフ構造データ内の部分データである検索サブグラフを、前記グラフ構造データベースから取得する検索サブグラフ取得手段と、
取得された検索サブグラフに含まれるグラフ構造から複数回出現する共通のグラフ構造を抽出し、この抽出したグラフ構造に含まる任意のノード名およびプロパティ名を変数にすることにより、前記ユーザにより入力されたキーワードおよび概念に関する情報を検索するための共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段と、
を備えた共通クエリグラフパターン生成装置において、
前記入力手段は、ユーザから入力された、前記検索クエリグラフパターンの、前記キーワードと同じラベルを持つアークにつながるノードと前記概念のインスタンスであるノードとの間に存在するノードである中間ノードの数を制限するための情報をさらに入力し、
前記検索クエリグラフパターン生成手段は、前記入力手段で入力された中間ノードの数を制限するための情報に基づいて、前記検索クエリグラフパターンを生成する
ことを特徴とする共通クエリグラフパターン生成装置。
【請求項２】
前記入力手段は、ユーザから入力された、前記検索クエリグラフパターンの、前記キーワードと同じラベルを持つアークにつながるノードから前記概念のインスタンスとして存在するノードへのパスを辿っていく際に、連結するアークのサブジェクトからオブジェクトに向かう向きが変わるノードである中心ノードの数を制限するための情報をさらに入力し、
前記検索クエリグラフパターン生成手段は、前記入力手段で入力された中心ノードの数を制限するための情報に基づいて、前記検索クエリグラフパターンを生成する
ことを特徴とする請求項１に記載の共通クエリグラフパターン生成装置。
【請求項３】
前記共通クエリグラフパターン生成手段はさらに、生成された複数の共通クエリグラフパターンの中から、異なるリソースに跨った連続するアークで構成されている共通クエリグラフパターンを抽出することで、生成された共通クエリグラフパターンの数を絞り込む
ことを特徴とする請求項１または２に記載の共通クエリグラフパターン生成装置。
【請求項４】
ユーザから入力された検索対象のキーワードおよび概念を入力する入力ステップと、
前記キーワードと同じラベルを持つアークにつながるノードと、前記概念のインスタンスであるノードとの間に存在するパスを、グラフ構造を持つデータが格納されているグラフ構造データベースから検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成ステップと、
生成された検索クエリグラフパターンにマッチする前記グラフ構造データ内の部分データである検索サブグラフを、前記グラフ構造データベースから取得する検索サブグラフ取得ステップと、
取得された検索サブグラフに含まれるグラフ構造から複数回出現する共通のグラフ構造を抽出し、この抽出したグラフ構造に含まる任意のノード名およびプロパティ名を変数にすることにより、前記ユーザにより入力されたキーワードおよび概念に関する情報を検索するための共通クエリグラフパターンを生成する共通クエリグラフパターン生成ステップと、
を有する共通クエリグラフパターン生成方法において、
前記入力ステップでは、ユーザから入力された、前記検索クエリグラフパターンの、前記キーワードと同じラベルを持つアークにつながるノードと前記概念のインスタンスであるノードとの間に存在するノードである中間ノードの数を制限するための情報をさらに入力し、
前記検索クエリグラフパターン生成ステップでは、前記入力ステップで入力された中間ノードの数を制限するための情報に基づいて、前記検索クエリグラフパターンを生成する
ことを特徴とする共通クエリグラフパターン生成方法。
【請求項５】
前記入力ステップでは、ユーザから入力された、前記検索クエリグラフパターンの、前記キーワードと同じラベルを持つアークにつながるノードから前記概念のインスタンスとして存在するノードへのパスを辿っていく際に、連結するアークのサブジェクトからオブジェクトに向かう向きが変わるノードである中心ノードの数を制限するための情報をさらに入力し、
前記検索クエリグラフパターン生成ステップでは、前記入力ステップで入力された中心ノードの数を制限するための情報に基づいて、前記検索クエリグラフパターンを生成する
ことを特徴とする請求項４に記載の共通クエリグラフパターン生成方法。
【請求項６】
前記共通クエリグラフパターン生成ステップではさらに、生成された複数の共通クエリグラフパターンの中から、異なるリソースに跨った連続するアークで構成されている共通クエリグラフパターンを抽出することで、生成された共通クエリグラフパターンの数を絞り込む
ことを特徴とする請求項４または５に記載の共通クエリグラフパターン生成方法。
【請求項７】
ユーザから入力された検索対象のキーワードおよび概念を入力する入力機能と、
前記キーワードと同じラベルを持つアークにつながるノードと、前記概念のインスタンスであるノードとの間に存在するパスを、グラフ構造を持つデータが格納されているグラフ構造データベースから検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成機能と、
生成された検索クエリグラフパターンにマッチする前記グラフ構造データ内の部分データである検索サブグラフを、前記グラフ構造データベースから取得する検索サブグラフ取得機能と、
取得された検索サブグラフに含まれるグラフ構造から複数回出現する共通のグラフ構造を抽出し、この抽出したグラフ構造に含まる任意のノード名およびプロパティ名を変数にすることにより、前記ユーザにより入力されたキーワードおよび概念に関する情報を検索するための共通クエリグラフパターンを生成する共通クエリグラフパターン生成機能と、
を有する共通クエリグラフパターン生成用プログラムにおいて、
前記入力機能では、ユーザから入力された、前記検索クエリグラフパターンの、前記キーワードと同じラベルを持つアークにつながるノードと前記概念のインスタンスであるノードとの間に存在するノードである中間ノードの数を制限するための情報をさらに入力し、
前記検索クエリグラフパターン生成機能では、前記入力ステップで入力された中間ノードの数を制限するための情報に基づいて、前記検索クエリグラフパターンを生成する
ことを特徴とする共通クエリグラフパターン生成用プログラム。
【請求項８】
前記入力機能では、ユーザから入力された、前記検索クエリグラフパターンの、前記キーワードと同じラベルを持つアークにつながるノードから前記概念のインスタンスとして存在するノードへのパスを辿っていく際に、連結するアークのサブジェクトからオブジェクトに向かう向きが変わるノードである中心ノードの数を制限するための情報をさらに入力し、
前記検索クエリグラフパターン生成機能では、前記入力ステップで入力された中心ノードの数を制限するための情報に基づいて、前記検索クエリグラフパターンを生成する
ことを特徴とする請求項７に記載の共通クエリグラフパターン生成用プログラム。
【請求項９】
前記共通クエリグラフパターン生成機能ではさらに、生成された複数の共通クエリグラフパターンの中から、異なるリソースに跨った連続するアークで構成されている共通クエリグラフパターンを抽出することで、生成された共通クエリグラフパターンの数を絞り込む
ことを特徴とする請求項７または８に記載の共通クエリグラフパターン生成用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、膨大なデータの中からユーザが必要とする情報を検索するために用いる共通クエリグラフパターンを生成する共通クエリグラフパターン生成装置、共通クエリグラフパターン生成方法、および共通クエリグラフパターン生成用プログラムに関する。
【背景技術】
【０００２】
近年、コンピュータネットワーク上には大量のデータが存在しており、ユーザはその中から所望のデータを検索することが困難になってきている。そのため、大量のデータから所望のデータを簡易に入手するための精度の高い検索技術が注目を集めている。
【０００３】
このような精度の高い検索を行うために用いられる技術にセマンティックWebがある。このセマンティックWebは、Webサイト上にメタデータとしてセマンティクス（意味情報）を付与し、人の手を使わずにデータを機械的に処理できる空間を創出するものである。
【０００４】
このセマンティックWebを利用することにより、メタデータの記述方法を定めたResource  Description  Framework（ＲＤＦ）により表現されたグラフ構造のデータから、グラフパターンをクエリとしてマッチングさせて必要なデータを検索することが可能になる。
【０００５】
このＲＤＦにより表現されたグラフ構造は、サブジェクト（主体）としてのノードを始点とし、オブジェクト（客体）としてのノードを終点として、これらのノード間を、識別情報となるラベルを付加し矢印で表現したプロパティ（属性）としてのアークで連結することで、その構成を表現することができる。
【０００６】
特許文献１には、このクエリグラフパターンを用いてグラフ構造を持つ大量のデータの中から情報を検索する際、ユーザにより入力されたキーワードを含むノードおよびそのノードと同じラベルを持つアークにつながるノードのそれぞれと、ユーザにより指定された概念（クラス）のインスタンスとして存在するノードとの間にある共通の構造を検索するための検索クエリグラフパターンを生成し、この検索クエリグラフパターンに基づいて抽出されたサブグラフの構造からさらに共通のグラフ構造を有する共通クエリグラフパターンを自動的に生成する技術が記載されている。
【０００７】
この技術を用いて生成された共通クエリグラフパターンを用いて検索処理を行うことにより、ユーザにより入力された情報および予め設定された情報に基づいて、共通の意味合いの構造を持つ情報を抽出することが可能になる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００６−３１３５０１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
この特許文献１に記載の技術において共通クエリグラフパターンを生成する際に、ユーザにより入力されたキーワードを含むノードおよびそのノードと同じラベルを持つアークにつながるノードのそれぞれと、ユーザにより指定された概念（クラス）のインスタンスとして存在するノードとの間が２点以上のノードで構成されている場合には、ノード間のアークの向きのパターンが複数存在するため検索クエリグラフパターンが複数生成される。
【００１０】
例えば、ユーザにより入力されたキーワードと同じラベルを持つアークにつながる任意のノードを「?key」とし、ユーザにより指定された概念（クラス）のインスタンスとして存在する任意のノードを「?target」とすると、このノード「?key」とノード「?target」との間に２点の任意のノード「?node1」、「?node2」が存在するときには、図６（ａ）〜（ｈ）に示すようにアークの向きのパターンにより８通りの検索クエリグラフパターンが生成される。
【００１１】
しかし、検索クエリグラフパターンが８通り生成されると、これらのパターンのそれぞれに基づいて共通クエリグラフパターンを生成し、さらに生成された各共通クエリグラフパターンに基づいて所望のサブグラフの検索処理を行うことになるため、計算量が膨大になり処理に相当な時間がかかってしまうという問題があった。
【００１２】
この場合、共通クエリグラフパターンの共通度（頻出度）の高い構造を選択することで共通クエリグラフパターンの数を制御することも可能であるが、共通度（頻出度）の高い共通クエリグラフパターンには有意でなく当たり前の構造や理解不能な構造が含まれることが多く、ユーザが入力した情報特有の有意な構造が抽出しにくくなることがあるという問題があった。
【００１３】
本発明は、上記事情に鑑みてなされたものであり、グラフ構造を持つ大量のデータの中からクエリグラフパターンが一致する情報を検索する際に、ユーザにより入力されたキーワードまたは概念などの情報に関連し且つ共通の意味合いの構造を持つ有意な情報を効率よく取得するクエリグラフパターンを自動的に生成可能な共通クエリグラフパターン生成装置、共通クエリグラフパターン生成方法、および共通クエリグラフパターン生成用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するための、本発明の共通クエリグラフパターン生成装置は、グラフ構造を持つデータが格納されているグラフ構造データベースに接続され、ユーザから入力された検索対象のキーワードおよび概念を入力する入力手段と、前記キーワードと同じラベルを持つアークにつながるノードと、前記概念のインスタンスであるノードとの間に存在するパスを検索するための検索クエリグラフパターンを生成する検索クエリグラフパターン生成手段と、生成された検索クエリグラフパターンにマッチする前記グラフ構造データ内の部分データである検索サブグラフを、前記グラフ構造データベースから取得する検索サブグラフ取得手段と、取得された検索サブグラフに含まれるグラフ構造から複数回出現する共通のグラフ構造を抽出し、この抽出したグラフ構造に含まる任意のノード名およびプロパティ名を変数にすることにより、前記ユーザにより入力されたキーワードおよび概念に関する情報を検索するための共通クエリグラフパターンを生成する共通クエリグラフパターン生成手段とを備えた共通クエリグラフパターン生成装置において、前記入力手段は、ユーザから入力された、前記検索クエリグラフパターンの、前記キーワードと同じラベルを持つアークにつながるノードと前記概念のインスタンスであるノードとの間に存在するノードである中間ノードの数を制限するための情報をさらに入力し、前記検索クエリグラフパターン生成手段は、前記入力手段で入力された中間ノードの数を制限するための情報に基づいて、前記検索クエリグラフパターンを生成することを特徴とする。
【００１５】
またこの共通クエリグラフパターン生成装置の前記入力手段では、ユーザから入力された、前記検索クエリグラフパターンの、前記キーワードと同じラベルを持つアークにつながるノードから前記概念のインスタンスとして存在するノードへのパスを辿っていく際に、連結するアークのサブジェクトからオブジェクトに向かう向きが変わるノードである中心ノードの数を制限するための情報をさらに入力し、前記検索クエリグラフパターン生成手段では、前記入力手段で入力された中心ノードの数を制限するための情報に基づいて、前記検索クエリグラフパターンを生成するようにしてもよい。
【００１６】
またこの共通クエリグラフパターン生成装置の前記共通クエリグラフパターン生成手段ではさらに、生成された複数の共通クエリグラフパターンの中から、異なるリソースに跨った連続するアークで構成されている共通クエリグラフパターンを抽出することで、生成された共通クエリグラフパターンの数を絞り込むようにしてもよい。
【発明の効果】
【００１７】
本発明の共通クエリグラフパターン生成装置、共通クエリグラフパターン生成方法、および共通クエリグラフパターン生成用プログラムによれば、グラフ構造を持つ大量のデータの中からクエリグラフパターンが一致する情報を検索する際に、ユーザにより入力されたキーワードまたは概念などの情報に関連し且つ共通の意味合いの構造を持つ有意な情報を効率よく取得するクエリグラフパターンを自動的に生成可能であるため、所望の情報を効率よく取得することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態による共通クエリグラフパターン生成装置としてのクエリグラフパターン生成部を有する検索装置を利用した検索システムの構成を示すブロック図である。
【図２】本発明の一実施形態による共通クエリグラフパターン生成装置としてのクエリグラフパターン生成部を有する検索装置に接続されたグラフ構造データベース内のデータを示す説明図である。
【図３】（ａ）は、本発明の一実施形態による共通クエリグラフパターン生成装置としてのクエリグラフパターン生成部を有する検索装置に接続されたグラフ構造データベース内のデータの一部を示す説明図であり、（ｂ）は、（ａ）のＲＤＦ表現をＸＭＬ形式データで記述した状態を示す説明図である。
【図４】本発明の一実施形態による共通クエリグラフパターン生成装置としてのクエリグラフパターン生成部を有する検索装置で実行される処理を説明するフローチャートである。
【図５】本発明の一実施形態による共通クエリグラフパターン生成装置としてのクエリグラフパターン生成部を有する検索装置で生成された検索クエリグラフパターンの一例である。
【図６】従来の共通クエリグラフパターン生成装置で生成された検索クエリグラフパターンの一例である。
【発明を実施するための形態】
【００１９】
本発明の共通クエリグラフパターン生成装置の一実施形態を、図１〜図５を用いて説明する。
【００２０】
《一実施形態による検索システム１の構成》
図１は、本発明の一実施形態による共通クエリグラフパターン生成装置としてのクエリグラフパターン生成部３２を有する検索装置３０を用いた検索システム１の構成を示す全体図である。
【００２１】
本実施形態における検索システム１は、グラフ構造データベース１０と、ユーザ端末２０と、検索装置３０とを有する。
【００２２】
グラフ構造データベース１０には、図２に表すようなグラフ構造を持つデータが格納されている。このグラフ構造データはラベル付き有向グラフデータであり、データのアーク（ノード間をサブジェクトからオブジェクトに向けて結ぶ矢印）をRDFの仕様に基づいてプロパティと称する。
【００２３】
本実施形態においてグラフ構造データベース１０に格納されているグラフ構造データは、人が所属する組織に関する組織データベース（ＤＢ）と、論文や著書に関する論文データベース（ＤＢ）と、ＳＮＳ（Social Networking Service）コミュニティに関するＳＮＳコミュニティデータベース（ＤＢ）との３つの異なるリソースのデータで構成されている。
【００２４】
例えば、組織ＤＢのデータとしては、オブジェクトとしての「京都大学大学院」、「情報学研究所」、「知能情報学専攻」、「社会情報学専攻」、「ＮＴ研究所」等とともに、これらの組織に所属する人名がサブジェクトとして格納されている。また、論文ＤＢのデータとしては、サブジェクトとしての「知能情報システムの課題」、「マルチエージェントシステム」、「探索アルゴリズムの研究」、「インタラクションの理解とデザイン」等とともに、これらの論文の著者である人名およびキーワードがオブジェクトとして格納されている。また、ＳＮＳコミュニティＤＢのデータとしては、サブジェクトとしての「人工知能技術は今」等とともに、このＳＮＳコミュニティのキーワードおよびメンバの人名がオブジェクトとして格納されている。
【００２５】
図３は、これらのグラフ構造データがどのように既存のリレーショナルデータベースなどで管理されているデータから生成され、グラフ化されているかを示すための説明図である。図３（ａ）は図２のデータの一部を示したものであり、単語「人工知能」は、サブジェクトであるＳＮＳコミュニティ「人工知能技術は今」のオブジェクトとなるキーワードであるとともに、サブジェクトである論文「アルゴリズムの研究」のオブジェクトとなるキーワードであることが示されている。
【００２６】
また、図３（ｂ）は、図３（ａ）のグラフ構造データのＲＤＦ表現をＸＭＬ形式データで記述したものであり、グラフ構造データベース１０には、図２のデータのそれぞれを図３（ｂ）に示すようなＸＭＬ形式データで記述した情報が格納されている。このＸＭＬ形式データには、各アークがどのリソースに由来するプロパティであるかを区別するために名前空間を利用しており、各名前空間の定義と、一のサブジェクトから一のオブジェクトに向かうアークの名前空間を用いたプロパティとが記載されている。
【００２７】
例えば図３（ｂ）では、名前空間として、リソース（ＳＮＳコミュニティＤＢ）に由来することを示すための「SNS」、リソース（論文ＤＢ）に由来することを示すための「PAPER」が定義され、サブジェクトであるＳＮＳコミュニティ「人工知能技術は今」とオブジェクトである単語「人工知能」は、名前空間「SNS」を用いたプロパティ「SNS:キーワード」のアークで連結され、また、サブジェクトである論文「探索アルゴリズムの研究」とオブジェクトである単語「人工知能」は、名前空間「PAPER」を用いたプロパティ「PAPER:キーワード」のアークで連結されていることが記載されている。
【００２８】
ユーザ端末２０は、検索システム１を利用するユーザにより操作される端末であり、ユーザにより入力された検索対象となるキーワード、概念、および検索クエリグラフパターンの複雑さにより検索クエリグラフパターンの数を制御するためのパラメータを検索装置３０に送出するとともに、検索装置３０で出力された検索結果を表示する。
【００２９】
検索装置３０は、入力部３１と、クエリグラフパターン生成部３２と、サブグラフ検索部３３と、出力部３４とを有する。
【００３０】
入力部３１は、ユーザ端末２０から送出された検索対象となるキーワード、概念、および検索クエリグラフパターンの数を制御するためのパラメータを入力する。
【００３１】
クエリグラフパターン生成部３２は、検索クエリグラフパターン生成部３２１と、検索クエリグラフパターン記憶部３２２と、共通クエリグラフパターン生成部３２３と、データ跨り検出部３２４と、パターン絞込み部３２５と、共通クエリグラフパターン記憶部３２６とを有する。
【００３２】
検索クエリグラフパターン生成部３２１は、入力部３１から入力された検索対象となるキーワードおよび概念の情報に基づいて、当該キーワードを含むノードおよびそのノードと同じラベルを持つアークにつながるノードのそれぞれと、当該概念（クラス）のインスタンスとして存在するノードとの間にある共通の構造を検索し、この共通の構造を検索クエリグラフパターンとして生成する。
【００３３】
また検索クエリグラフパターン生成部３２１は、入力部３１から入力された検索クエリグラフパターンの数を制御するためのパラメータに基づいて、生成した検索クエリグラフパターンの中から有効な検索クエリグラフパターンを抽出する。
【００３４】
検索クエリグラフパターン記憶部３２２は、検索クエリグラフパターン生成部３２１で抽出された検索クエリグラフパターンを記憶する。
【００３５】
共通クエリグラフパターン生成部３２３は、検索クエリグラフパターン記憶部３２２に記憶された検索クエリグラフパターンにマッチするグラフ構造データの部分データであるサブグラフを、グラフ構造データベース１０から検索して抽出する。
【００３６】
また共通クエリグラフパターン生成部３２３は、検索した結果抽出されたサブグラフの構造からさらに複数回出現する共通のグラフ構造を抽出し、この抽出したグラフ構造に含まる任意のノード名およびプロパティ名を変数にすることにより、ユーザにより入力されたキーワードおよび概念に関する情報を検索するための共通クエリグラフパターンを生成する。
【００３７】
データ跨り検出部３２４は、共通クエリグラフパターン生成部３２３で生成された共通クエリグラフパターンから、異なるリソースに跨った連続するアークの構造を検出する。この際、異なるリソースに跨った連続するアークであるか否かの判断は、グラフ構造データベース１０内のＸＭＬ形式データに記載された各アークのプロパティの情報に基づいて行う。
【００３８】
パターン絞込み部３２５は、共通クエリグラフパターン生成部３２３で生成された複数の共通クエリグラフパターンの中から、データ跨り検出部３２４において異なるリソースに跨った連続するアークで構成されている共通クエリグラフパターンを抽出することで、共通クエリグラフパターンの数を絞り込む。
【００３９】
共通クエリグラフパターン記憶部３２６は、パターン絞込み部３２５で絞り込まれた共通クエリグラフパターンを記憶する。
【００４０】
サブグラフ検索部３３は、クエリグラフパターン生成部３２の共通クエリグラフパターン記憶部３２６に記憶された共通クエリグラフパターンにマッチするサブグラフを、グラフ構造データベースから検索して抽出する。
【００４１】
出力部３４は、サブグラフ検索部３３で抽出されたサブグラフの情報を、検索結果としてユーザ端末に出力する。
【００４２】
《一実施形態による検索システム１の動作》
次に、上記のように構成された検索システム１を用いて検索処理を実行するときの動作について説明する。図４は、検索処理を行うときの検索装置３０の動作を示すフローチャートである。
【００４３】
まず、ユーザによりユーザ端末２０が操作され、検索対象のキーワードが入力されるとともに概念としてリソースが選択される。例えば、「人工知能」に関係する組織を検索したいときには、キーワードとして単語「人工知能」を入力するとともに概念としてリソース「組織」が選択される。また、ユーザ端末２０からさらに検索クエリグラフパターンの複雑さにより検索クエリグラフパターンの数を制御するためのパラメータが入力される。検索クエリグラフパターンの数を制御するためのパラメータとしては、ユーザにより入力されたキーワードを含むノードおよびそのノードと同じラベルを持つアークにつながるノードのそれぞれと、ユーザにより指定された概念（クラス）のインスタンスとして存在するノードとの間にある共通の構造である検索クエリグラフパターンの、両端のノードの間に存在する中間のノード（以下、「中間ノード」という）の数を制限するための「中間ノード数」と、当該キーワードまたは当該キーワードと同じラベルを持つアークにつながるノードから当該概念のインスタンスとして存在するノードへのパスを辿っていく際に連結するアークの矢印の向きが変わるノード（自身がサブジェクトからオブジェクトに変わるノード、またはオブジェクトからサブジェクトに変わるノード、以下「中心ノード」という）の数を制限するための「中心ノード数」が入力される。これらの「中間ノード数」と「中心ノード数」とは、数が多い程多様な構造の検索結果を得ることができるが計算量が多くなり、数が少ない程検索クエリグラフパターンの複雑さが低減し共通クエリグラフパターンを生成するときの計算量が少なくなるものであり、グラフ構造データベースに格納されたデータの量や所望の検索精度に基づいてユーザにより指定される。本実施形態においては、中間ノード数としては「２」が入力され、中心ノード数としては「０」および「１」が入力されたものとする。
【００４４】
これらのキーワード、概念、中間ノード、中心ノードの情報がユーザ端末２０で入力されると検索装置３０に送出され、入力部３１から入力される（Ｓ１）。
【００４５】
入力部３１からこれらの情報が入力されると、クエリグラフパターン生成部３２の検索クエリグラフパターン生成部３２１において、当該キーワードを含むノードおよびそのノードと同じラベルを持つアークにつながるノードのそれぞれと、当該概念（クラス）のインスタンスとして存在するノードとの間にある共通の構造を検索して検索クエリグラフパターンが生成される。
【００４６】
ここで本実施形態においては、中間ノード数が「２」に指定されていることから、矢印の向きのパターンに基づいて最大で図５（ａ）〜（ｈ）に示す８つの検索クエリグラフパターンが生成される。この検索クエリグラフパターンの生成については、特開２００６−３１３５０１号公報に記載の方法を用いることができる。
【００４７】
さらに中心ノード数が「０」および「１」に指定されていることから、これら８つの検索クエリグラフパターンの中から中心ノード数が「０」または「１」のものが抽出される。図５においては中心ノードが太線枠で示されており、中心ノード数が「０」または「１」に該当する（ａ）、（ｂ）、（ｄ）、（ｅ）、（ｆ）、（ｈ）の６つが有効な検索クエリグラフパターンとして抽出される（Ｓ２）。
【００４８】
そして、この抽出された６つの検索クエリグラフパターン（ａ）、（ｂ）、（ｄ）、（ｅ）、（ｆ）、（ｈ）は、検索クエリグラフパターン記憶部３２２に記憶される（Ｓ３）。
【００４９】
次に、共通クエリグラフパターン生成部３２３において、検索クエリグラフパターン記憶部３２２に記憶された６つの検索クエリグラフパターン（ａ）、（ｂ）、（ｄ）、（ｅ）、（ｆ）、（ｈ）にそれぞれマッチするグラフ構造データの部分であるサブグラフがグラフ構造データベース１０から抽出される（Ｓ４）。
【００５０】
次に、共通クエリグラフパターン生成部３２３において、検索した結果抽出されたサブグラフの構造からさらに複数回出現する共通のグラフ構造が抽出され、この抽出されたグラフ構造に含まる任意のノード名およびプロパティ名を変数にすることにより、ユーザにより入力されたキーワードおよび概念に関する情報を検索するための共通クエリグラフパターンが生成される（Ｓ５）。この共通クエリグラフパターンの生成については、特開２００６−３１３５０１号公報に記載の方法を用いることができる。
【００５１】
次に、データ跨り検出部３２４において、共通クエリグラフパターン生成部３２３で生成された共通クエリグラフパターンの構造の中から、異なるリソースに跨った連続するアークの構造が、グラフ構造データベース１０内のＸＭＬ形式データに記載された各アークのプロパティの情報に基づいて検出される（Ｓ６）。この異なるリソースに跨った連続するアークであるか否かは、本実施形態においては図３（ｂ）に示すようなＸＭＬ形式データ内のプロパティで用いられている名前空間で判断される。例えば、「SNS:キーワード」と「PAPER:キーワード」とは名前空間が異なるため、図３（ａ）のサブグラフにおいてノード「人工知能」を挟んで連続する２つのアークは、異なるリソースに跨っていると判断される。
【００５２】
次に、パターン絞込み部３２５において、共通クエリグラフパターン生成部３２３で生成された複数の共通クエリグラフパターンが、異なるリソースに跨った連続するアークで構成された共通クエリグラフパターンに絞り込まれる（Ｓ７）。それぞれのリソースはもともと異なる意図で作られているため、異なるリソースを跨った構造に絞り込まれることで、それぞれのリソースの作成時には意図していなかったような有意な情報である新たな情報、知識が得られる可能性が高くなる。
【００５３】
絞り込まれた共通クエリグラフパターンは、共通クエリグラフパターン記憶部３２６に記憶される（Ｓ８）。
【００５４】
次に、サブグラフ検索部３３において、共通クエリグラフパターン記憶部３２６に記憶された共通クエリグラフパターンにマッチするサブグラフが、グラフ構造データベースから検索され抽出される（Ｓ９）。
【００５５】
そして、抽出されたサブグラフの情報が、入力したキーワードおよび概念に対する検索結果としてユーザ端末に出力される（Ｓ１０）。
【００５６】
以上の本実施形態によれば、グラフ構造を持つ大量のデータの中からクエリグラフパターンが一致する情報を検索する際に、検索クエリグラフパターンの数を制御するためのパラメータを入力しておくことで検索処理の計算量を大幅に減らすことができ、また生成した複数の共通クエリグラフパターンを異なるリソースに跨った連続するアークで構成された共通クエリグラフパターンに絞り込むことで、さらに検索処理の計算量を減らすとともに共通の意味合いを持つ有意な情報を効率よく取得することができる。
【００５７】
本実施形態においては、検索クエリグラフパターン生成部３２１で生成された検索クエリグラフパターンを検索クエリグラフパターン記憶部３２２に記憶させた後、共通クエリグラフパターンを生成する場合について説明したが、検索クエリグラフパターン記憶部３２２に記憶させることなく、検索クエリグラフパターン生成部３２１で検索クエリグラフパターンを生成しながら共通クエリグラフパターン生成部３２３で共通クエリグラフパターンを生成するようにしてもよい。
【符号の説明】
【００５８】
１…検索システム
１０…グラフ構造データベース
２０…ユーザ端末
３０…検索装置
３１…入力部
３２…クエリグラフパターン生成部
３３…サブグラフ検索部
３４…出力部
３２１…検索クエリグラフパターン生成部
３２２…検索クエリグラフパターン記憶部
３２３…共通クエリグラフパターン生成部
３２４…データ跨り検出部
３２５…パターン絞込み部
３２６…共通クエリグラフパターン記憶部
【図１】
2010277322.tif 000003
【図２】
2010277322.tif 000004
【図３】
2010277322.tif 000005
【図４】
2010277322.tif 000006
【図５】
2010277322.tif 000007
【図６】
2010277322.tif 000008