(57)【要約】【課題】データグラフの中からクエリグラフを含むものを探索するサブグラフマッチング処理を高速化すること。【解決手段】抽出部１３ａが、概念を示すラベルが付与された頂点と、頂点間の関係を表すエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと一致する部分を探索する際に、データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、該データグラフの頂点と、該データグラフの頂点と一致し得るクエリグラフの頂点との組み合わせを抽出し、除外部１３ｂが、抽出部１３ａにより抽出された組み合わせのうち、該データグラフの頂点に隣接する頂点と、対応するクエリグラフの頂点に隣接する頂点とが一致し得ない組み合わせを除外する。【選択図】図３
2018136821.tif 000002
【特許請求の範囲】
【請求項１】
概念を示すラベルが付与された頂点と、頂点間の関係を表すエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと一致する部分を探索する際に、前記データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、該データグラフの頂点と、該データグラフの頂点と一致し得る前記クエリグラフの頂点との組み合わせを抽出する抽出部と、
前記抽出部により抽出された前記組み合わせのうち、該データグラフの頂点に隣接する頂点と、対応する前記クエリグラフの頂点に隣接する頂点とが一致し得ない組み合わせを除外する除外部と、
を備えることを特徴とする探索装置。
【請求項２】
前記除外部が、前記データグラフの頂点に隣接する頂点と、対応するクエリグラフの頂点に隣接する頂点とが一致し得るか否かを、該頂点同士の写像が単射であることを条件として判定することを特徴とする請求項１に記載の探索装置。
【請求項３】
前記除外部が、前記データグラフの頂点に隣接する頂点と、対応するクエリグラフの頂点に隣接する頂点とが一致し得るか否かを、該頂点同士の写像が単射であるという条件を緩和した判定式を用いて判定することを特徴とする請求項１に記載の探索装置。
【請求項４】
探索装置で実行される探索方法であって、
概念を示すラベルが付与された頂点と、頂点間の関係を表すエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと一致する部分を探索する際に、前記データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、該データグラフの頂点と、該データグラフの頂点と一致し得る前記クエリグラフの頂点との組み合わせを抽出する抽出工程と、
前記抽出工程において抽出された前記組み合わせのうち、該データグラフの頂点に隣接する頂点と、対応する前記クエリグラフの頂点に隣接する頂点とが一致し得ない組み合わせを除外する除外工程と、
を含むことを特徴とする探索方法。
【請求項５】
概念を示すラベルが付与された頂点と、頂点間の関係を表すエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと一致する部分を探索する際に、前記データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、該データグラフの頂点と、該データグラフの頂点と一致し得る前記クエリグラフの頂点との組み合わせを抽出する抽出ステップと、
前記抽出ステップにおいて抽出された前記組み合わせのうち、該データグラフの頂点に隣接する頂点と、対応する前記クエリグラフの頂点に隣接する頂点とが一致し得ない組み合わせを除外する除外ステップと、
をコンピュータに実行させることを特徴とする探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、探索装置、探索方法および探索プログラムに関する。
【背景技術】
【０００２】
近年、大量に生成される情報の中から必要な情報を的確に探索する技術が不可欠になっている。例えば、キーワードによるテキスト検索では、テキストの意味を考慮して概念グラフ化されたテキストに対して効率的な探索手法が提案されている。ここで、概念グラフは、例えば、概念を表す頂点と概念間の関係を表すエッジからなるグラフ構造で表される。この技術において、検索対象となるテキスト集合から作成された概念グラフがデータグラフ、クエリとして入力される概念グラフがクエリグラフとされる。この場合に、概念グラフ化されたテキストを探索するということは、データグラフの中からクエリグラフを含むものを探索することになる。
【０００３】
このように、グラフ構造の中からクエリとして与えられた特定の部分構造すなわちサブグラフを発見する問題は、サブグラフマッチングと呼ばれる。従来、サブグラフマッチングは、バックトラッキングと呼ばれる探索アルゴリズムに基づいて探索されていた（非特許文献１参照）。この場合、クエリグラフの頂点に着目して、マッチするデータグラフの頂点を探索するいわゆるサブグラフ同型問題として取り扱われていた。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Jinsoo  Lee，Wook-Shin  Han，Romans  Kasperovics，Jeong-Hoon  Lee，“An  In-depth  Comparison  of  Subgraph  Isomorphism  Algorithms  in  Graph  Databases”，Proceedings  of  the  39th  international  conference  on  Very  Large  Data  Bases，2013年，pp.133-144
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、サブグラフ同型問題は、ＮＰ（Non-deterministic  Polynomial  time、非決定性多項式時間）困難、すなわち、ＮＰクラスに属する問題と同等に困難であることが知られている。つまり、多項式時間（Polynomial  time）で解くことができる問題のクラスをＰとする場合に、Ｐ≠ＮＰであれば、サブグラフ同型問題は多項式時間で解くことができない。そのため、データグラフおよびクエリグラフのサイズが増大するにつれ、サブグラフマッチングに要する時間が爆発的に増大してしまっていた。これにより、例えば、利用者からの問い合わせをクエリグラフで表現してデータベース上のデータグラフに対してサブグラフマッチングにより回答を提示するサービス等のように高速な応答を要求されても、対応することができない場合があった。
【０００６】
本発明は、上記に鑑みてなされたものであって、データグラフの中からクエリグラフを含むものを探索するサブグラフマッチング処理を高速化することを目的とする。
【課題を解決するための手段】
【０００７】
上述した課題を解決し、目的を達成するために、本発明に係る探索装置は、概念を示すラベルが付与された頂点と、頂点間の関係を表すエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと一致する部分を探索する際に、前記データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、該データグラフの頂点と、該データグラフの頂点と一致し得る前記クエリグラフの頂点との組み合わせを抽出する抽出部と、前記抽出部により抽出された前記組み合わせのうち、該データグラフの頂点に隣接する頂点と、対応する前記クエリグラフの頂点に隣接する頂点とが一致し得ない組み合わせを除外する除外部と、を備えることを特徴とする。
【発明の効果】
【０００８】
本発明によれば、データグラフの中からクエリグラフを含むものを探索するサブグラフマッチング処理を高速化することができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、本発明の一実施形態に係る探索装置の処理対象のグラフを例示する図である。
【図２】図２は、本実施形態の探索装置の処理概要を説明するための説明図である。
【図３】図３は、本実施形態の探索装置の概略構成を示す模式図である。
【図４】図４は、本実施形態の探索装置による探索処理の効果を説明するための説明図である。
【図５】図５は、本実施形態の探索処理手順を示すフローチャートである。
【図６】図６は、本実施形態の探索処理手順を示すフローチャートである。
【図７】図７は、本実施形態の探索処理手順を示すフローチャートである。
【図８】図８は、本実施形態の探索処理手順を示すフローチャートである。
【図９】図９は、他の実施形態の探索処理を説明するための説明図である。
【図１０】図１０は、探索プログラムを実行するコンピュータを例示する図である。
【発明を実施するための形態】
【００１０】
以下、図面を参照して、本発明の一実施形態を詳細に説明する。なお、この実施形態により本発明が限定されるものではない。また、図面の記載において、同一部分には同一の符号を付して示している。
【００１１】
［探索装置の処理概要］
まず、図１および図２を参照して、本実施形態に係る探索装置の処理概要を説明する。探索装置は、概念を示すラベルが付与された頂点と、頂点間の関係を表すエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと一致（マッチ）する部分を探索する。以下、この処理をサブグラフマッチング処理と記す。また、クエリグラフとマッチするデータグラフの部分をサブグラフと記す。
【００１２】
探索装置は、以下に説明するバックトラッキングによりサブグラフマッチング処理を実行する。その際、探索装置は、バックトラッキングの前処理として、後述する探索処理により、バックトラッキングの対象から除外するデータグラフの頂点を決定する枝刈りを行う。なお、バックトラッキングでは、クエリグラフの頂点にマッチするデータグラフの頂点を探索する。これに対し、探索処理では、データグラフの頂点に着目して、マッチし得るクエリグラフの頂点を探索する。この場合に、各データグラフの頂点は、マッチし得るかの情報を他の頂点と共有しないため、容易かつ高効率に処理を並列化することが可能となる。
【００１３】
ここで、データグラフは、頂点がラベルをもつ無向グラフｇ＝（Ｖｇ，Ｅｇ，Σ，ｌ）で表されるものとする。ただし、Ｖｇは頂点の集合、Ｅｇ⊆Ｖｇ×Ｖｇはエッジの集合、Σはラベルの集合、ｌは頂点とラベルを対応させる関数を表す。また、クエリグラフはｑ＝（Ｖq，Ｅq，Σ，ｌ）で表されるものとする。ｇがｑに対してサブグラフ同型である場合、次式（１）が成立する。すなわち、サブグラフマッチングとは、あるデータグラフｇとクエリグラフｑが与えられた場合に、次式（１）を満たす全ての写像Ｍを発見する問題と定義される。
【００１４】
【数１】
2018136821.tif 000003
【００１５】
次に、前処理としての探索処理が行われない場合の従来のバックトラッキングについて説明する。図１は、探索装置の処理対象のグラフを例示する図である。本実施形態において、図１に示すように、クエリグラフｑの頂点Ｖｑ（以下、ｕとも記す）は、ｕ０，ｕ１，ｕ２，…のように番号付けして識別されている。また、データグラフｇの頂点Ｖｇ（以下、ｖとも記す）は、ｖ０，ｖ１，ｖ２，…のように番号付けして識別されている。
【００１６】
また、図２は、従来のバックトラッキングを説明するための説明図である。図２に示すように、バックトラッキングでは、具体的にまず、ｕ０にマッチするデータグラフｇの頂点を探索する。ｕ０のラベルはａであり、データグラフｇのうちラベルがａの頂点はｖ３のみであることから、Ｍ［ｕ０］＝ｖ３とする。次に、ｕ１にマッチし得るｇの頂点を探索する。ｕ１のラベルはｃであり、ｕ０に隣接していることから、ｖ２，ｖ４，ｖ６がマッチし得る。ここでは、まずＭ［ｕ１］＝ｖ２として探索を進める。このことは、図２においてｖ３からｖ２への矢印で表される。
【００１７】
同様に、ｕ２にはｖ０とｖ１とがマッチし得る。ここで、Ｍ［ｕ２］＝ｖ０として探索を進めると、ｕ４にマッチし得るデータグラフの頂点が存在しないことがわかる。そこで、処理を戻してＭ［ｕ２］＝ｖ１として探索を進めると、再びｕ４にマッチし得るデータグラフの頂点が存在しないことがわかる。そこで、処理を戻し、Ｍ［ｕ１］＝ｖ４として探索を進める。
【００１８】
このように探索を進めることにより、Ｍ＝｛ｖ３，ｖ６，ｖ７，ｖ５，ｖ４｝および｛ｖ３，ｖ６，ｖ8，ｖ５，ｖ４｝の場合に、クエリグラフｑがデータグラフｇにマッチすることがわかり、サブグラフマッチングの処理結果として出力される。
【００１９】
このように、バックトラッキングでは、クエリグラフｑの頂点ｕｉについて、マッチし得るデータグラフの頂点（Ｖｇ＼Ｍ）を網羅するように探索する。ここでｕｉにマッチし得るデータグラフｇの頂点ｖとは、次式（２）で表されるように、ｕｉと同じラベルを持ち、ｕｉに隣接する頂点ｕｊ（ｊ＜ｉ）のうち、マッピングが写像Ｍに含まれるもの、すなわちマッピング先の頂点との間にエッジを持つ頂点を意味する。
【００２０】
【数２】
2018136821.tif 000004
【００２１】
そして、ｕｉにマッチし得る頂点ｖのうち一つを選択してｕｉにマッチさせたものとして、クエリグラフの次の頂点ｕｉ＋１にマッチし得るデータグラフの頂点の探索を再帰的に実行し、クエリグラフｑの全ての頂点についての写像Ｍを設定する。
【００２２】
［探索装置の構成］
次に、図３を参照して、本実施形態に係る探索装置の概略構成を説明する。図３に示すように、本実施形態に係る探索装置１は、ワークステーションやパソコン等の汎用コンピュータで実現され、入力部１１と出力部１２と制御部１３とを備える。探索装置１は、後述する探索処理を実行して、バックトラッキングの対象のデータグラフ頂点を削減する枝刈りを行った後に、サブグラフマッチング処理を行う。
【００２３】
入力部１１は、キーボードやマウス等の入力デバイスを用いて実現され、操作者による入力操作に対応して、制御部１３に対して各種指示情報を入力する。また、本実施形態において、入力部１１は、後述する探索処理の対象のデータグラフｇおよびクエリグラフｑを含むグラフデータを受け付けて制御部１３に入力する。
【００２４】
出力部１２は、液晶ディスプレイなどの表示装置、プリンター等の印刷装置、情報通信装置等によって実現され、例えば、後述する探索処理の処理結果であるサブグラフマッチング結果等を操作者に対して出力する。
【００２５】
また、探索装置１は、図示しない通信制御部と記憶部とを備える。通信制御部は、ＮＩＣ（Network  Interface  Card）等で実現され、ＬＡＮ（Local  Area  Network）やインターネットなどの電気通信回線を介したサーバ等の外部の装置と制御部１３との通信を制御する。例えば、上記のグラフデータは、通信制御部を介して外部の装置から受け付けてもよい。また、サブグラフマッチング結果は、通信制御部を介して外部の装置に出力されてもよい。
【００２６】
記憶部は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、または、ハードディスク、光ディスク等の記憶装置によって実現される。記憶部には、探索装置１を動作させる処理プログラムや、処理プログラムの実行中に使用されるデータなどが予め記憶され、あるいは処理の都度一時的に記憶される。この記憶部は、通信制御部を介して制御部１３と通信する構成でもよい。
【００２７】
制御部１３は、ＣＰＵ（Central  Processing  Unit）等の演算処理装置がメモリに記憶された処理プログラムを実行することにより、図３に例示するように、抽出部１３ａ、除外部１３ｂ、および探索部１３ｃとして機能する。
【００２８】
なお、本実施形態において、制御部１３は複数ＣＰＵコアで実現される。これにより、バックトラッキングの各枝に対応する処理や、後述する探索処理における各データグラフの頂点に関する処理を、複数のＣＰＵによる並行処理で行うことが可能となる。
【００２９】
抽出部１３ａは、概念を示すラベルが付与された頂点と、頂点間の関係を表すエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと一致する部分を探索する際に、データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、該データグラフの頂点と、該データグラフの頂点と一致し得るクエリグラフの頂点との組み合わせを抽出する。
【００３０】
具体的に、抽出部１３ａは、サブグラフマッチング処理に先立って、データグラフｇの各頂点と隣接する頂点とのラベルの組み合わせを用いて、このデータグラフｇの頂点とマッチし得るクエリデータｑの頂点を抽出する。
【００３１】
例えば、図１に例示するグラフに対して、ラベルがｃであるデータグラフｇ頂点ｖ２，ｖ４，ｖ６に着目する。これに対し、ラベルがｃであるクエリグラフｑの頂点はｕ１，ｕ４の２つである。このうち、ｕ１は、隣接する頂点のラベルに着目すると、ラベルがａの１つの頂点と、ラベルがｂの２つの頂点とに隣接する。したがって、ｕ１は、ｖ２，ｖ６にはマッチし得るが、ｖ４にはマッチし得ない。同様に、ｕ４については、ラベルがｂの１つの頂点に隣接することから、ｖ２，ｖ４，ｖ６のいずれにもマッチし得る。
【００３２】
ここで、各データグラフの頂点ｖのうち、クエリグラフの頂点ｕとマッチし得る頂点について、マッチし得るｖとｕとの組み合わせを示す写像Ｐを定義する。なお、Ｐ［ｖ］⊆Ｖｑである。上記の場合に、Ｐ［ｖ２］＝｛ｕ１，ｕ４｝、Ｐ［ｖ４］＝｛ｕ４｝、Ｐ［ｖ６］＝｛ｕ１，ｕ４｝が導出される。
【００３３】
さらに、ラベルｃの頂点に隣接するラベルｂのデータグラフの頂点ｖ０，ｖ１に着目する。この２頂点は、ラベルｃの頂点１つに隣接することから、ｕ２にはマッチし得るが、ｕ３にはマッチし得ないことがわかる。したがって、Ｐ［ｖ０］＝｛ｕ２｝、Ｐ［ｖ１］＝｛ｕ２｝が導出され、Ｐが更新される。同様に、抽出部１３ａは、データグラフの他の頂点についてもＰを更新する。
【００３４】
なお、抽出部１３ａは、Ｐの初期値を全てのｖについてＰ［ｖ］＝Ｖｑとして、マッチし得ないデータグラフの頂点とクエリグラフの頂点との組み合わせをＰから削除するように、Ｐの更新を行ってもよい。これによっても、マッチし得るデータグラフの頂点とクエリグラフの頂点との組み合わせが抽出されることになる。
【００３５】
図３の説明に戻る。除外部１３ｂは、抽出部１３ａにより抽出された組み合わせのうち、該データグラフの頂点に隣接する頂点と、対応するクエリグラフの頂点に隣接する頂点とが一致し得ない組み合わせを除外する。
【００３６】
例えば、図１に例示するグラフに対して、ラベルがｃのデータグラフの頂点ｖ２に着目する。ｖ２がｕ４にマッチし得る場合には、ｕ４に隣接するラベルｂのｕ３と、ｖ２に隣接するいずれかの頂点とがマッチし得る。ここで、ｖ２に隣接するラベルｂの頂点ｖ０およびｖ１は、抽出部１３ａの処理により、ｕ３とはマッチし得ないことがわかっている。したがって、ｖ２はｕ４にマッチし得ないことになる。
【００３７】
同様に、ｖ２がｕ１にマッチし得る場合には、隣接する頂点どうしがマッチし得ることから、ｖ２はｕ１にマッチし得ないことになる。従って、Ｐ［ｖ２］＝０が導出される。
【００３８】
さらに、ｖ２に隣接するラベルｂの頂点ｖ０およびｖ１に着目する。ｖ０またはｖ１がラベルｂのｕ２にマッチし得る場合には、ｖ０またはｖ１に隣接するラベルｃのｖ２と、ｕ２に隣接するラベルｃのｕ１とがマッチし得る。ここで、Ｐ［ｖ２］＝０がわかっていることから、ｖ０およびｖ１はｕ２にマッチし得ないことになる。
【００３９】
このようにして、除外部１３ｂは、抽出部１３ａにより抽出されたマッチし得るデータグラフの頂点とクエリグラフの頂点との組み合わせを示すＰから、隣接する頂点どうしがマッチし得ない組み合わせを除外する。
【００４０】
図３の説明に戻る。探索部１３ｃは、抽出部１３ａが抽出した組み合わせのうち、除外部１３ｂにより除外されていない組み合わせを対象に、サブグラフマッチング処理を行って、クエリグラフにマッチするデータグラフのサブグラフを抽出する。
【００４１】
例えば、図１に例示するグラフについて、ｖ２は、ｕ０にマッチし得るｖ３に隣接するラベルｃの頂点であるが、Ｐ［ｖ２］＝０、すなわち、Ｐ［ｖ２］≠ｕ１であり、ｕ１にマッチし得ない。したがって、図２に例示したバックトラッキングにおいて、除外される。
【００４２】
図４は、上記の抽出部１３ａおよび除外部１３ｂによる探索処理の効果を例示する図である。図４の網掛部に示すように、探索部１３ｃは、バックトラッキングによるサブグラフマッチング処理を行う際、図２に示した組み合わせから、上記の探索処理によって除外された組み合わせを除外することができる。
【００４３】
［探索処理］
次に、図５〜図８を参照して、探索装置１の探索処理について説明する。図５は、探索装置１の探索処理手順を示すフローチャートである。図５のフローチャートは、例えば、処理の開始を指示する操作入力があったタイミングで開始される。
【００４４】
まず、抽出部１３ａが、写像Ｐを全てのｖについてＰ［ｖ］＝Ｖｑとする初期化を行う（ステップＳ２００）。次に、抽出部１３ａが、各データグラフの頂点ｖについて、自身と隣接する頂点とのラベルの組み合わせに基づいて、Ｐに対する枝刈りを行う（ステップＳ２１０）。言い換えれば、抽出部１３ａが、データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、マッチし得るデータグラフの頂点とクエリデータの頂との組み合わせを示す写像Ｐを抽出する。
【００４５】
次に、除外部１３ｂが、隣接する頂点どうしのマッチ可能性に基づいて、Ｐに対する枝刈りを行う（ステップＳ２２０）。言い換えれば、除外部１３ｂが、抽出部１３ａにより抽出されたマッチし得るデータグラフの頂点とクエリグラフの頂点との組み合わせを示すＰから、隣接する頂点どうしがマッチし得ない組み合わせを除外する。
【００４６】
次に、探索部１３ｃが、ステップＳ２２０の処理でＰが書き換えられたか否か、すなわち枝刈りが行われた否かを確認する（ステップＳ２３０）。Ｐが書き換えられた場合（ステップＳ２３０，Ｙｅｓ）、探索部１３ｃは、ステップＳ２２０の処理が継続中として、ステップＳ２２０に処理を戻す。一方、Ｐが書き換えられなかった場合（ステップＳ２３０，Ｎｏ）、探索部１３ｃは、ステップＳ２２０の処理が終了したものとして、ステップＳ２４０に処理を進める。
【００４７】
ステップＳ２４０の処理では、探索部１３ｃが、最新のＰを用いたバックトラッキングを実行する関数（ＰＲＵＮＥＤ  ＢＡＣＫＴＲＡＣＫ（０，ｉ，Ｐ））を呼び出してサブグラフマッチング処理を行って、データグラフからサブグラフを抽出する。ここで、ＰＲＵＮＥＤ  ＢＡＣＫＴＲＡＣＫ（０，ｉ，Ｐ）とは、すなわち、バックトラッキングを実行する関数ＢＡＣＫＴＲＡＣＫ（０，ｉ）にＰが適用されたものである。これにより、一連の探索処理が終了する。
【００４８】
図６は、ステップＳ２１０の詳細な処理手順を示すフローチャートである。抽出部１３ａが、各データグラフの頂点ｖ∈Ｖｇについて、並列に処理を行う（ステップＳ２１１，Ｓ２１６）。また、抽出部１３ａが各クエリグラフの頂点ｕ∈Ｖｑについて、ループ処理を行う（ステップＳ２１２，Ｓ２１５）。
【００４９】
また、抽出部１３ａは、ｖがｕにマッチし得る条件を示す次式（３）を満たすか否かを確認する（ステップＳ２１３）。この条件は、自身と隣接する頂点とのラベルの組み合わせについて、ｕとｖとが同じラベルを持ち、任意のラベルについてｕに隣接する頂点数と同数以上の頂点にｖが隣接することを表している。
【００５０】
【数３】
2018136821.tif 000005
【００５１】
上記式（３）の条件を満たす場合に（ステップＳ２１３，Ｙｅｓ）、抽出部１３ａはステップＳ２１５に処理を進める。一方、上記式（３）の条件を満たさない場合に（ステップＳ２１３，Ｎｏ）、抽出部１３ａは、Ｐ［ｖ］からｕを削除して（ステップＳ２１４）、その後、ステップＳ２１５に処理を進める。
【００５２】
なお、抽出部１３ａの処理はｖについてのＰ［ｖ］の更新のみであるため、各ｖについての処理の並行化を容易に行える。
【００５３】
図７は、ステップＳ２２０の詳細な処理手順を示すフローチャートである。除外部１３ｂが、各データグラフの頂点ｖ∈Ｖｇについて、並列に処理を行う（ステップＳ２２１，Ｓ２２６）。また、除外部１３ａが、ｖにマッチし得るクエリグラフの頂点ｕ∈Ｖｑについて、ループ処理を行う（ステップＳ２２２，Ｓ２２５）。
【００５４】
また、除外部１３ｂが、ｖがｕにマッチし得る条件を示す次式（４）を満たすか否かを、Ｐを用いて確認する（ステップＳ２２３）。この条件は、ｕが隣接するすべての頂点すなわちｕの隣接頂点のすべてに、ｖが隣接する頂点すなわちｖの隣接頂点もマッチし得ることを表している。
【００５５】
【数４】
2018136821.tif 000006
【００５６】
上記式（４）の条件を満たす場合に（ステップＳ２２３，Ｙｅｓ）、除外部１３ｂは、ステップＳ２２５に処理を進める。一方、上記式（４）の条件を満たさない場合に（ステップＳ２２３，Ｎｏ）、除外部１３ｂは、Ｐ［ｖ］からｕを削除して（ステップＳ２２４）、その後、ステップＳ２２５に処理を進める。
【００５７】
なお、除外部１３ｂの処理も、抽出部１３ａの処理と同様に、ｖについてのＰ［ｖ］の更新のみであるため、各ｖについての処理の並行化を容易に行える。
【００５８】
図８は、ステップＳ２４０の詳細な処理手順を示すフローチャートである。探索部１３ｃは、まず、クエリグラフの全頂点について写像Ｍを設定する処理が終了したか否かを確認する（ステップＳ２４１）。終了した場合、すなわち、クエリグラフの頂点の番号ｉ（＝０〜｜Ｖｑ｜−１）がクエリグラフの頂点数｜Ｖｑ｜に達した場合（ステップＳ２４１，Ｙｅｓ）、探索部１３ｃは、写像Ｍをマッチとして記録して（ステップＳ２４２）、呼び出し元に戻り（ステップＳ２４６）、処理を終了させる。
【００５９】
一方、写像Ｍを設定する処理が終了していない場合（ステップＳ２４１，Ｎｏ）、探索部１３ｃは、ｕｉにマッチし得る上記式（２）を満たす頂点を、まだ探索していないデータグラフの頂点（Ｖｇ＼Ｍ）のうち、ｕｉ∈Ｐ［ｖ］であるｖから探索するループ処理を行う（ステップＳ２４３，ステップＳ２４５）。
【００６０】
また、探索部１３ｃは、ｕの隣接頂点集合Ｎ（ｕ）から１つを選び、ｕｉにマッチさせたものとして、次のクエリ頂点ｕｉ＋１にマッチする頂点を探索する処理を行う関数ＰＲＵＮＥＤ  ＢＡＣＫＴＲＡＣＫを再帰的に呼び出して実行する。具体的に、探索部１３ｃは、写像ＭのコピーＭ’を作成し、Ｍ’［ｕｉ］にｖを設定し、ＰＲＵＮＥＤ  ＢＡＣＫＴＲＡＣＫ（Ｍ’，ｉ＋１，Ｐ）を呼び出して実行する（ステップＳ２４４）。
【００６１】
なお、図８に示すステップＳ２４０の処理は、従来のバックトラッキングとは、ステップＳ２４３の処理において、各データグラフの頂点ｖについてｕｉ∈Ｐ［ｖ］であることを確認する点のみが異なる。これに伴い、ステップＳ２４４の処理において呼び出される関数が、従来のＢＡＣＫＴＲＡＣＫに代えてＰＲＵＮＥＤ  ＢＡＣＫＴＲＡＣＫになる。このように、各データグラフの頂点ｖについてｕｉ∈Ｐ［ｖ］であることを確認することにより、マッチし得ない頂点を経由したデータグラフの頂点の探索を枝刈りすることができる。したがって、バックトラッキングの探索空間を削減することができるので、サブグラフマッチング処理の高速化が可能となる。
【００６２】
以上、説明したように、本実施形態の探索装置１では、抽出部１３ａが、概念を示すラベルが付与された頂点と、頂点間の関係を表すエッジとで構成されるグラフのうち、検索対象のデータのグラフであるデータグラフから、検索に使用されるクエリのグラフであるクエリグラフと一致する部分を探索する際に、データグラフの各頂点と隣接する頂点とのラベルの組み合わせに基づいて、該データグラフの頂点と、該データグラフの頂点と一致し得るクエリグラフの頂点との組み合わせを抽出する。また、除外部１３ｂが、抽出部１３ａにより抽出された組み合わせのうち、該データグラフの頂点に隣接する頂点と、対応するクエリグラフの頂点に隣接する頂点とが一致し得ない組み合わせを除外する。
【００６３】
これにより、探索装置１は、探索部１３ｃによるバックトラッキングの探索空間を削減することができる。したがって、データグラフの中からクエリグラフを含むものを探索するサブグラフマッチング処理を高速化して現実的な時間で完了させることが可能となる。例えば、利用者からの問い合わせをクエリグラフで表現してデータベース上のデータグラフに対してサブグラフマッチングにより回答を提示するサービス等のように高速な応答を要求された場合にも対応可能となる。
【００６４】
また、探索処理では、データグラフの頂点に着目して、マッチし得るクエリグラフの頂点を探索する。これにより、各データグラフの頂点は、他の頂点とマッチし得るかの情報を共有しないため、容易かつ高効率に枝刈りの処理を並列化することが可能となる。
【００６５】
［他の実施形態］
上記実施形態において、除外部１３ｂは、データグラフの頂点に隣接する頂点と、対応するクエリグラフの頂点に隣接する頂点とが一致し得るか否かを、該頂点同士の写像が単射であることを条件として判定している。すなわち、除外部１３ｂは、上記式（４）を用いて、クエリグラフの頂点ｕの隣接頂点のすべてについて、データグラフの頂点ｖの隣接頂点がマッチし得るか否かを確認している。この式（４）における、単射（ｉｎｊｅｃｔｉｏｎ）の存在の確認には、膨大な計算量が必要となる。
【００６６】
そこで、除外部１３ｂは、データグラフの頂点に隣接する頂点と、対応するクエリグラフの頂点に隣接する頂点とが一致し得るか否かを、該頂点同士の写像が単射であるという条件を緩和した判定式を用いて判定することもできる。すなわち、以下に説明するように、厳密な単射の存在の確認に代えて、簡易な判定式を適用することもできる。この場合に、所定の条件の下では厳密な単射の存在の確認を行った場合と同一の解を得ることができる。一方、所定の条件に当てはまらない場合にも、マッチし得ないデータグラフの頂点とクエリグラフの頂点との組み合わせについてマッチし得ると判定するいわゆる偽陽性の解が与えられることはあっても、逆にマッチし得る組み合わせをマッチし得ないとする偽陰性の解が与えられることはない。
【００６７】
ここで、図９を参照して、単射の存在の確認の必要性について説明する。図９（ｂ）はクエリグラフｑを例示している。また、図９（ａ）は、データグラフｇの一部を例示している。図９（ａ）には、そこまでの枝刈りで求められた各頂点についての集合Ｐ、すなわち上記したステップＳ２２３の処理に移行した際の、各データグラフの頂点とマッチし得るクエリグラフの頂点との組み合わせの集合を表すＰも例示されている。図９（ａ）に示されている範囲で、データグラフｇはクエリグラフｑにマッチしない。仮に、上記したステップＳ２２３の処理に移行した際、各データグラフの頂点とマッチし得るクエリグラフの頂点との組み合わせの集合を表すＰが、図９（ａ）に示すように判定されている場合について説明する。この場合に、ステップＳ２２３の処理において、上記式（４）に変えて、ｆが単射であるという条件を除いた次式（５）を用いることにする。
【００６８】
【数５】
2018136821.tif 000007
【００６９】
その場合に、ｖ０に着目してステップＳ２２３の処理を行うと、図９（ａ）の範囲のデータグラフがクエリグラフにマッチしないにも関わらず、Ｐ［ｖ０］＝｛ｕ０｝のままとなる。これは、上記式（５）では、ｖ２がｕ２およびｕ４に同時にマッチする、いわゆる一人二役になっていることに起因する。実際には、ｕ２にマッチするデータグラフの頂点と、ｕ４にマッチするデータグラフの頂点とは異なるため、一人二役では偽陽性となり、枝刈りの効果を低下させる。
【００７０】
このような一人二役による偽陽性の解の発生を回避するために、ｕ１，ｕ２，ｕ３，ｕ４のそれぞれの頂点にマッチし得る異なるｖ０の隣接頂点との組み合わせすなわち単射を発見する必要がある。しかしながら、隣接頂点が多くなるほどこの組み合わせの数が爆発的に増大するため、単射の発見に要する計算時間が増大する。
【００７１】
そこで、本実施形態では、単射の存在を確認せずに偽陽性の解を可能な限り削減するため、次式（６）に示すように上記式（５）を書き換えることにより、隣接頂点のラベルごとにマッチし得るか否かを確認する。
【００７２】
【数６】
2018136821.tif 000008
【００７３】
上記式（６）に含まれる次式（７）の部分に適切な条件を追加することにより、可能な限り偽陽性の解を減らし上記式（４）と同一の解を得るために、以下のように、Ｎσ（ｕ）の要素数に応じて３つの場合に分けて考える。
【００７４】
【数７】
2018136821.tif 000009
【００７５】
まず、｜Ｎσ（ｕ）｜＝１の場合には、クエリグラフの頂点が１つであるため、データグラフの一つの頂点を複数のクエリグラフの頂点にマッチさせることによって発生する一人二役による偽陽性の解は発生しない。例えば、図９に示した例において、ｕ０に隣接するラベルａの頂点はｕ１のみであり、｜Ｎａ（ｕ０）｜＝１である。この場合に、ｖ０に隣接するラベルａの頂点がいずれもｕ１にマッチし得なければ、ｖ０がｕ０にマッチし得ないことは明らかである。
【００７６】
次に、｜Ｎσ（ｕ）｜＝２の場合には、Ｎσ（ｕ）の要素をｕ’０，ｕ’１とすると、次式（８）に示すように、クエリグラフ頂点ｕ’０，ｕ’１にマッチし得る２つの異なるデータグラフ頂点が存在する場合には、偽陽性の解が発生しない。
【００７７】
【数８】
2018136821.tif 000010
【００７８】
上記式（８）を満たす場合であることは、次式（９）のように容易に確認することができる。すなわち、ｕ’０，ｕ’１にマッチし得るＮσ（ｖ）に含まれるデータグラフ頂点をそれぞれ計数して加算した後、重複して計数しているｕ’０，ｕ’１の双方にマッチし得るデータグラフの頂点の数を減算した値が２以上であることを確認すればよい。
【００７９】
【数９】
2018136821.tif 000011
【００８０】
例えば、図９に示したグラフからｕ４よびｖ４を除外したグラフについて考える。この場合に、Ｎｂ（ｕ０）＝｛ｕ２，ｕ３｝である。ここで、ｖ０の隣接頂点のうちｕ２にマッチし得るのはｖ２の１つであり、ｕ３にマッチし得るのはｖ２，ｖ３の２つであり、加算すると３になる。このうち、重複して計数しているｕ２，ｕ３の双方にマッチし得るｖ２の１つを減算して得た値２が２以上であることから、偽陽性の解は発生せず、ｖ０はｕ０にマッチし得ると言うことができる。
【００８１】
最後に、｜Ｎσ（ｕ）｜≧３の場合には、｜Ｎσ（ｕ）｜＝２の場合と同様のアイディアを用いて偽陽性を排除することが可能である。すなわち、｛ｕ’０，ｕ’１，ｕ’２，…｝＝Ｎσ（ｕ）として、それぞれにマッチし得る頂点の数の和から、重複して計数した頂点の数を減算する。ただし、この計算の項数は、上記式（９）のとおり｜Ｎσ（ｕ）｜＝２の場合は３項であるが、｜Ｎσ（ｕ）｜の増加に従って爆発的に増加するため、却って計算コストが増大する。
【００８２】
そこで、｜Ｎσ（ｕ）｜≧３の場合には、偽陽性の解を許容することにする。ただし、任意の２頂点ｕ’０，ｕ’１∈Ｎσ（ｕ）について、｜Ｎσ（ｕ）｜＝２の場合と同様に、偽陽性の解の発生を抑制する。
【００８３】
例えば、図９に示したグラフにおいて、ｕ’０＝ｕ２，ｕ’1＝ｕ４とした場合に、上記式（８）に含まれる部分について、次式（１０）が成立することから、データグラフの隣接頂点が一人二役となり、ｖ０はｕ０にマッチし得ないことがわかる。
【００８４】
【数１０】
2018136821.tif 000012
【００８５】
一方、ｕ’０＝ｕ２，ｕ’１＝ｕ３とした場合には、｛ｖ２，ｖ３｝または｛ｖ２，ｖ４｝の組み合わせが存在するために、ｖ０はｕ０にマッチし得うると判定され、偽陽性の解が発生する。
【００８６】
以上により、クエリグラフに含まれる任意のラベルσの任意の頂点ｕについて、｜Ｎσ（ｕ）｜≦２の場合には、簡単な条件で偽陽性の解を排除可能であることがわかる。具体的に、データグラフの頂点ｖがクエリグラフの頂点ｕにマッチし得るかを確認するために、上記式（４）に変えて、次式（１１）が用いられる。
【００８７】
【数１１】
2018136821.tif 000013
【００８８】
ここで、ｈは次式（１２）により定義される関数である。
【００８９】
【数１２】
2018136821.tif 000014
【００９０】
一般に、クエリグラフは小さいため、クエリグラフの各頂点の隣接頂点も少数であり、さらに隣接頂点は複数のラベルに分類されることから、｜Ｎσ（ｕ）｜≦２を満たすケースは少なくない。また、｜Ｎσ（ｕ）｜≧３の場合にも、偽陽性の解が与えられることはあっても偽陰性の解が与えられることはない。したがって、上記ステップＳ２２３の処理において、上記式（１１）を用いることにより、より高速にサブグラフマッチング処理の枝刈りを行うことが可能となる。
【００９１】
［プログラム］
上記実施形態に係る探索装置１が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。一実施形態として、探索装置１は、パッケージソフトウェアやオンラインソフトウェアとして上記の探索処理を実行する探索プログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記の探索プログラムを情報処理装置に実行させることにより、情報処理装置を探索装置１として機能させることができる。ここで言う情報処理装置には、デスクトップ型またはノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal  Handyphone  System）などの移動体通信端末、さらには、ＰＤＡ（Personal  Digital  Assistants）などのスレート端末などがその範疇に含まれる。また、ユーザが使用する端末装置をクライアントとし、当該クライアントに上記の探索処理に関するサービスを提供するサーバ装置として実装することもできる。例えば、探索装置１は、グラフデータを入力とし、サブグラフマッチング結果を出力する探索処理サービスを提供するサーバ装置として実装される。この場合、探索装置１は、Ｗｅｂサーバとして実装することとしてもよいし、アウトソーシングによって上記の探索処理に関するサービスを提供するクラウドとして実装することとしてもかまわない。以下に、探索装置１と同様の機能を実現する探索プログラムを実行するコンピュータの一例を説明する。
【００９２】
図１０に示すように、探索プログラムを実行するコンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。
【００９３】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０３１に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。ディスクドライブ１０４１には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１０５１およびキーボード１０５２が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１０６１が接続される。
【００９４】
ここで、図１０に示すように、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。上記実施形態で説明した各テーブルは、例えばハードディスクドライブ１０３１やメモリ１０１０に記憶される。
【００９５】
また、探索プログラムは、例えば、コンピュータ１０００によって実行される指令が記述されたプログラムモジュール１０９３として、ハードディスクドライブ１０３１に記憶される。具体的には、上記実施形態で説明した探索装置１が実行する各処理が記述されたプログラムモジュール１０９３が、ハードディスクドライブ１０３１に記憶される。
【００９６】
また、探索プログラムによる情報処理に用いられるデータは、プログラムデータ１０９４として、例えば、ハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した各手順を実行する。
【００９７】
なお、探索プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１０４１等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、探索プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ＬＡＮやＷＡＮ（Wide  Area  Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【００９８】
以上、本発明者によってなされた発明を適用した実施形態について説明したが、本実施形態による本発明の開示の一部をなす記述および図面により本発明は限定されることはない。すなわち、本実施形態に基づいて当業者等によりなされる他の実施形態、実施例および運用技術等は全て本発明の範疇に含まれる。
【符号の説明】
【００９９】
１  探索装置
１１  入力部
１２  出力部
１３  制御部
１３ａ  抽出部
１３ｂ  除外部
１３ｃ  探索部
【図１】
2018136821.tif 000015
【図２】
2018136821.tif 000016
【図３】
2018136821.tif 000017
【図４】
2018136821.tif 000018
【図５】
2018136821.tif 000019
【図６】
2018136821.tif 000020
【図７】
2018136821.tif 000021
【図８】
2018136821.tif 000022
【図９】
2018136821.tif 000023
【図１０】
2018136821.tif 000024