(57)【要約】【課題】処理速度の低下を防止することができる情報処理装置、情報処理方法及び情報処理プログラムを提供する。【解決手段】実施形態の情報処理装置は、第１記憶部と、第２記憶部と、変換処理部と、を有する。第１記憶部は、ノードに関するエッジの一覧をノードの情報とするグラフ構造を有するデータを記憶する。第２記憶部は、グラフ構造とは異なる非グラフ構造を有してデータ要素間の相互関係を表すデータを記憶する。変換処理部は、第１記憶部が記憶するデータに対して、データ構造をグラフ構造から非グラフ構造へ変換し、第２記憶部に記憶させる。【選択図】図１
2014153961.tif 000002
【特許請求の範囲】
【請求項１】
ノードに関するエッジの一覧を前記ノードの情報とするグラフ構造を有するデータを記憶する第１記憶部と、
前記グラフ構造とは異なる非グラフ構造を有してデータ要素間の相互関係を表すデータを記憶する第２記憶部と、
前記第１記憶部が記憶するデータに対して、データ構造を前記グラフ構造から前記非グラフ構造へ変換し、前記第２記憶部に記憶させる変換処理部と、
を有する情報処理装置。
【請求項２】
データを前記グラフ構造又は前記非グラフ構造のいずれのデータ構造にして記憶させるべきであるかを予め定められた判定条件に基づいて判定する判定部をさらに有し、
前記変換処理部は、
前記第１記憶部が記憶するデータに対して、前記非グラフ構造にして記憶させるべきであると前記判定部が判定した場合、データ構造を前記グラフ構造から前記非グラフ構造へ変換し、前記第２記憶部に記憶させる
請求項１に記載の情報処理装置。
【請求項３】
前記判定部は、
前記ノードに関するエッジの数、前記ノードのエッジに対するアクセス頻度、前記ノードのエッジを探索する計算量、前記ノードのエッジに対する最後のアクセスからの時間、及び前記ノードのエッジに接合している他のノードが葉ノードであるか否かの少なくともいずれかが予め定められた判定条件に基づいて判定する
請求項２に記載の情報処理装置。
【請求項４】
前記第２記憶部が記憶するデータに対して、前記グラフ構造にして記憶させるべきであると前記判定部が判定した場合に、データ構造を前記非グラフ構造から前記グラフ構造へ変換し、前記第１記憶部に記憶させる逆変換処理部をさらに有する
請求項２に記載の情報処理装置。
【請求項５】
前記第１記憶部が記憶するデータに対して、前記変換処理部がデータ構造を前記グラフ構造から前記非グラフ構造へ変換し、前記第２記憶部に記憶させたことを少なくとも示す変換処理情報を記憶する第３記憶部をさらに有する
請求項１に記載の情報処理装置。
【請求項６】
前記判定部は、
前記第１記憶部が記憶するデータが更新される毎に、予め定められた判定条件に基づいて判定する
請求項２に記載の情報処理装置。
【請求項７】
前記判定部は、
判定開始を指示する指示情報を取得した場合、又は予め定められた周期で判定を行う
請求項２に記載の情報処理装置。
【請求項８】
前記判定部は、
前記第１記憶部が記憶するデータに対して読出しクエリが実行された後に判定を行う
請求項２に記載の情報処理装置。
【請求項９】
前記第１記憶部は、
前記ノードに関するエッジ、又は前記ノードのエッジに接合している他のノードを一意に識別する識別情報に基づくツリー構造によって前記ノードに関するエッジの一覧を前記ノードの情報とするグラフ構造を有するデータを記憶する
請求項１に記載の情報処理装置。
【請求項１０】
ノードに関するエッジの一覧を前記ノードの情報とするグラフ構造を有するデータを記憶する第１記憶部と、前記グラフ構造とは異なる非グラフ構造を有してデータ要素間の相互関係を表すデータを記憶する第２記憶部と、を有する情報処理装置にデータを記憶させる情報処理方法であって、
前記第１記憶部が記憶するデータに対して、データ構造を前記グラフ構造から前記非グラフ構造へ変換する工程と、
データ構造を前記グラフ構造から前記非グラフ構造へ変換したデータを前記第２記憶部に記憶させる工程と、
を含む情報処理方法。
【請求項１１】
ノードに関するエッジの一覧を前記ノードの情報とするグラフ構造を有するデータを記憶する第１記憶部と、前記グラフ構造とは異なる非グラフ構造を有してデータ要素間の相互関係を表すデータを記憶する第２記憶部と、を有する情報処理装置にデータを記憶させる情報処理プログラムであって、
前記第１記憶部が記憶するデータに対して、データ構造を前記グラフ構造から前記非グラフ構造へ変換するステップと、
データ構造を前記グラフ構造から前記非グラフ構造へ変換したデータを前記第２記憶部に記憶させるステップと、
をコンピュータに実行させるための情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、情報処理装置、情報処理方法及び情報処理プログラムに関する。
【背景技術】
【０００２】
従来、リレーショナルデータベースでは効率的に表現しにくいデータを表現するグラフデータベースが知られている。また、高速な探索を可能にするさまざまなグラフデータベース技術が検討されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１０−７９８７１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、グラフデータベースには、ノードのエッジ数が多すぎる場合などのように、記憶されるデータによっては処理負荷が非常に大きくなり、処理速度が低下してしまうという問題があった。本発明が解決しようとする課題は、処理速度の低下を防止することができる情報処理装置、情報処理方法及び情報処理プログラムを提供することである。
【課題を解決するための手段】
【０００５】
実施形態の情報処理装置は、第１記憶部と、第２記憶部と、変換処理部と、を有する。第１記憶部は、ノードに関するエッジの一覧をノードの情報とするグラフ構造を有するデータを記憶する。第２記憶部は、グラフ構造とは異なる非グラフ構造を有してデータ要素間の相互関係を表すデータを記憶する。変換処理部は、第１記憶部が記憶するデータに対して、データ構造をグラフ構造から非グラフ構造へ変換し、第２記憶部に記憶させる。
【図面の簡単な説明】
【０００６】
【図１】実施形態にかかる情報処理装置の構成を例示するブロック図。
【図２】実施形態にかかる情報処理装置の動作例を示すフローチャート。
【図３】実施形態の第１記憶部が記憶するグラフ構造のデータと、第２記憶部がデータを記憶する非グラフ構造とを例示する図。
【図４】図３に示したグラフ構造のデータを構造変換部が最適化した第１例を示す図。
【図５】図３に示したグラフ構造のデータを構造変換部が最適化した第２例を示す図。
【図６】図３に示したグラフ構造のデータを構造変換部が最適化した第３例を示す図。
【図７】実施形態にかかる情報処理装置がクエリを処理する場合の動作例を示すフローチャート。
【図８】実施形態の第１記憶部が記憶するグラフ構造のデータ（対向ノードが葉ノードでない場合）を例示する図。
【図９】対向ノードが葉ノードでない場合に、実施形態にかかる情報処理装置が実行する第３の処理例を示す図。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、実施形態にかかる情報処理装置について説明する。
【０００８】
（実施形態）
図１は、実施形態にかかる情報処理装置１００の構成を例示するブロック図である。なお、情報処理装置１００は、例えば、汎用のコンピュータなどによって実現される。即ち、情報処理装置１００は、ＣＰＵ、記憶装置及び通信インターフェイスなどを備えたコンピュータとしての機能を有する。
【０００９】
図１に示すように、情報処理装置１００は、第１記憶部１０、第２記憶部１２、第３記憶部１４、構造変換部１６及び判定部１８を有する。第１記憶部１０、第２記憶部１２及び第３記憶部１４は、例えば単一又は複数のＨＤＤ（Hard  Disk  Drive）などによって構成される。構造変換部１６及び判定部１８は、ハードウェア回路、又はＣＰＵで実行するソフトウェアのいずれであってもよい。
【００１０】
第１記憶部１０は、ノードに関するエッジの一覧をノードの情報とするグラフ構造を有するデータを記憶する。例えば、第１記憶部１０は、グラフ構造のデータを記憶してグラフデータベースを構成する。
【００１１】
第２記憶部１２は、グラフ構造とは異なる非グラフ構造を有してデータ要素間の相互関係を表すデータを記憶する。例えば、第２記憶部１２は、主としてキーとバリューからなるプロパティ構造を有するデータを記憶する。具体的には、第２記憶部１２は、グラフデータベースのノードのプロパティを記憶したり、ＫＶＳ（キーバリューストア）、列指向データベース、ＲＤＢＭＳ（リレーショナルデータベース管理システム）などを構成する。
【００１２】
構造変換部１６は、変換処理部１６０及び逆変換処理部１６２を有し、第１記憶部１０及び第２記憶部１２にアクセスを行って後述する変換処理情報を第３記憶部１４に記憶させる。変換処理部１６０は、判定部１８の判定結果（後述）に基づいて、第１記憶部１０が記憶するデータに対して、データ構造をグラフ構造から非グラフ構造へ変換し、第２記憶部１２に記憶させる。逆変換処理部１６２は、判定部１８の判定結果（後述）に基づいて、第２記憶部１２が記憶するデータに対して、データ構造を非グラフ構造からグラフ構造へ変換し、第１記憶部１０に記憶させる。
【００１３】
判定部１８は、第１記憶部１０又は第２記憶部１２が記憶するデータを例えば構造変換部１６を介して取得し、データをグラフ構造又は非グラフ構造のいずれのデータ構造にして記憶させるべきであるかを予め定められた判定条件に基づいて判定する。ここで、判定部１８は、ノードに関するエッジの数、ノードのエッジに対するアクセス頻度、ノードのエッジを探索する計算量、ノードのエッジに対する最後のアクセスからの時間、及びノードのエッジに接合している他のノードが葉ノードであるか否かの少なくともいずれかが予め定められた判定条件を用いて判定する。つまり、判定部１８は、第１記憶部１０又は第２記憶部１２に記憶させるデータの最適なデータ構造を判定している。
【００１４】
また、判定部１８は、以下の少なくとも１つの場合に判定を行うように構成されてもよい。例えば、判定部１８は、第１記憶部１０が記憶するデータが更新される毎に、予め定められた判定条件に基づいて判定する。また、判定部１８は、判定開始を指示する指示情報を取得した場合、又は予め定められた周期で判定を行う。また、判定部１８は、第１記憶部１０が記憶するデータに対して読出しクエリが実行された後に判定を行う。
【００１５】
そして、判定部１８が判定した最適なデータ構造の判定結果に基づいて、構造変換部１６は、データ構造の変換を行う。第３記憶部１４は、構造変換部１６がデータ構造を変換して記憶させた結果を示す情報（履歴）を変換処理情報として記憶する。例えば、構造変換部１６は、第１記憶部１０が記憶するデータに対して、変換処理部１６０がデータ構造をグラフ構造から非グラフ構造へ変換して第２記憶部１２に記憶させた場合、その旨を少なくとも示す変換処理情報を第３記憶部１４に記憶させる。
【００１６】
上述したように、第１記憶部１０が記憶するデータは、あるノードにエッジを介して繋がれたノードを高速に探し出せるグラフ構造になっている。具体的には、あるノードに関するエッジの一覧がそのノードの情報として保持されており、エッジには対向ノード（エッジに接合している他のノード）の情報へのポインタが含まれている。よって、ノードからノードへエッジを辿って移動するためには、エッジに含まれるポインタに従うだけでよい。つまり、ノード全体（総数Ｎ）からあるノードに関する情報を探し出す処理Ｏ（ｌｏｇＮ）〜Ｏ（Ｎ）は、不要である。
【００１７】
一方、あるノードに関するエッジの数Ｍが非常に大きくなってしまうと、ノードからエッジや隣接ノードを探し出す処理がＯ（Ｍ）であるため、Ｍが小さい場合に比べて情報を探し出す処理時間（計算量）が大幅に増加してしまう。従って、あるノードに関するエッジの数Ｍを小さくすることが、情報処理装置１００全体の処理性能の向上に繋がると考えられる。以下、ノードに関するエッジの数を予め定められた数よりも少なくすること等によって、グラフ構造のデータに対する処理（計算量）が過大になることを防止することを最適化と記すことがある。
【００１８】
次に、情報処理装置１００の動作について詳述する。図２は、情報処理装置１００の動作例を示すフローチャートである。まず、判定部１８は、第１記憶部１０が記憶するグラフ構造のデータの中から、データ構造を変換して記憶させるべきデータの候補（以下、最適化対象ノード）となるノードを探し出す処理を開始する（Ｓ１００）。
【００１９】
具体例として、判定部１８は、ノード毎にエッジ数が閾値を超えているか否かを判定する（Ｓ１０２）。ここで、判定部１８は、エッジ数Ｍが多すぎる（例えばノード数Ｎと同数以上のエッジを有している）ノードを最適化対象ノードとする（第１判定条件）。判定部１８は、エッジ数が閾値を超えているノード（Ｓ１０２：Ｙｅｓ）に対してはＳ１０４の処理を開始する。また、判定部１８は、ノードのエッジ数が閾値以下である場合には残っている別のノードに対する判定を行う（Ｓ１０２：Ｎｏ）。
【００２０】
次に、判定部１８は、エッジ数Ｍが多すぎるノードの中から、データ構造を変換して記憶させるべきデータ（変換対象データ）を探し出す処理を開始する（Ｓ１０４）。
【００２１】
例えば、判定部１８は、予め定められた条件を満たすエッジであるか否かをエッジ毎に判定する（Ｓ１０６）。ここで、判定部１８は、例えばアクセス頻度が閾値未満（例えばアクセス頻度が１％未満）のエッジを変換対象データとする（第２判定条件）。判定部１８は、アクセス頻度が閾値未満のエッジ（Ｓ１０６：Ｙｅｓ）に対してはＳ１０８の処理を開始する。また、判定部１８は、エッジのアクセス頻度が閾値以上である場合には残っている別のエッジに対する判定を行う（Ｓ１０６：Ｎｏ）。
【００２２】
Ｓ１０８の処理において、変換処理部１６０は、変換対象データと判定されたエッジのデータ構造を変換してプロパティ化（図４等参照）することにより、最適化対象ノードのエッジ数を削減する。
【００２３】
Ｓ１１０の処理において、変換処理部１６０は、データ構造を変換してプロパティ化したデータ（グラフ構造から非グラフ構造へ変換したデータ）を第２記憶部１２に記憶させる。
【００２４】
情報処理装置１００の動作例では、最適化対象ノードの変換対象データに対してデータ構造を変換する場合を例に説明したが、情報処理装置１００の動作はこれに限定されない。また、変換処理部１６０がデータ構造を変換して第２記憶部１２に記憶させたデータ（エッジ）は、第１記憶部１０から削除されてもよいし、探索されない（エッジでない）ように削除マークを付されて区別されるだけでもよい。即ち、情報処理装置１００は、最適化対象ノードの処理対象となるエッジ数を削減することにより、最適化対象ノードに関する処理速度を向上させることができる。例えば、最適化対象ノードが有するエッジ数が１００から１０に減少した場合、最適化対象ノードに関する処理（計算量）は１／１０となる。
【００２５】
次に、データ構造の変換について詳述する。図３は、第１記憶部１０が記憶するグラフ構造のデータと、第２記憶部１２がデータを記憶する非グラフ構造とを例示する図である。ここで、図３（ａ）は、第１記憶部１０が記憶する最適化前のグラフ構造のデータを例示している。図３（ｂ）は、第２記憶部１２がデータを記憶する非グラフ構造を例示している。なお、情報処理装置１００が最適化を実行する前には、第２記憶部１２にはデータが記憶されていないものとする。
【００２６】
図３（ａ）に示すように、第１記憶部１０は、例えば３つのノード１〜３（ｉｄ＝１，２，３）と２つのエッジ（ｔｙｐｅ＝ｈａｔｅ、ｔｙｐｅ＝ｌｉｋｅ）からなるグラフ構造のデータを記憶している。ノードのｉｄは、最適化対象ノードを一意に識別可能な情報（ＩＤ）であり、情報１とする。エッジの種類（ｔｙｐｅ）や名前（ｎａｍｅ）を表す情報は、情報２とする。最適化対象ノードとエッジを介して接合されている他方のノード（対向ノード）を一意に識別可能な情報（ＩＤ）、又は対向ノードを表す（人間が）可読な名前情報は、情報３とする。ここで、例えば「人」とは、ｔｙｐｅ＝ｈｕｍａｎの全てのノードを指す。
【００２７】
グラフ構造のデータに対するクエリは、例えば「Ａさんが好きな映画のタイトルは？」といったものである。このクエリを図３（ａ）に示したデータにあてはめて厳密に表現すると、「ｎａｍｅがＡであるｔｙｐｅ＝ｈｕｍａｎのノード（ｉｄ＝１）に対し、ｔｙｐｅ＝ｌｉｋｅのエッジを介して接合されているｔｙｐｅ＝ｍｏｖｉｅのノード（ｉｄ＝３）のｎａｍｅを表示」となる。
【００２８】
また、図３（ｂ）に示すように、第２記憶部１２は、情報１〜３からなるデータをプロパティ構造（非グラフ構造）データとして記憶する。
【００２９】
（最適化の第１例）
図４は、図３に示したグラフ構造のデータを構造変換部１６が最適化（変換）した第１例を示す図である。図４（ａ）に示すように、例えばｔｙｐｅ＝ｌｉｋｅのエッジは最適化によって第１記憶部１０から削除される。なお、破線で示したエッジ（又はノード）は、削除された（又は削除と同等に処理対象とされない）ものであることを示している。
【００３０】
一方、図４（ｂ）に示すように、第２記憶部１２は、第１記憶部１０から削除されたエッジの情報（変換処理部１６０が変換した情報）を記憶している。ここでは、第２記憶部１２は、対向ノードを一意に表す識別可能な情報（ＩＤ＝ｉｄ３）を情報３としている。
【００３１】
図４に示した状態では、「ノード（ｉｄ＝１）に対してｔｙｐｅ＝ｌｉｋｅのエッジを介して接合されているノード」が第１記憶部１０に存在しない。よって、上述したクエリと同じクエリでは、最適化前と同じ処理結果を得ることはできない。例えば、第３記憶部１４は、ｔｙｐｅ＝ｌｉｋｅのエッジが第２記憶部１２に存在することを示す変換処理情報を記憶する。これにより、クエリに対し、第２記憶部１２が記憶しているデータを利用して、ノード１（ｉｄ＝１）が好き（ｌｉｋｅ）なノードはノード３（ｉｄ＝３）であり、最終的にノード３のｎａｍｅを表示することが可能となる。
【００３２】
このように、最適化において、情報処理装置１００は、単に最適化対象ノードが有するエッジを削除するのではなく、削除したエッジの情報（データ）をグラフ構造とは異なるデータ構造で第２記憶部１２に記憶しておく。よって、情報処理装置１００は、最適化後であっても、第１記憶部１０から削除したエッジの情報（データ）を第２記憶部１２から読み出して利用することが可能である。
【００３３】
（最適化の第２例）
図５は、図３に示したグラフ構造のデータを構造変換部１６が最適化（変換）した第２例を示す図である。図５（ａ）に示すように、例えばｔｙｐｅ＝ｌｉｋｅのエッジ、及びノード３（ｉｄ＝３）は第１記憶部１０から削除される。一方、図５（ｂ）に示すように、第２記憶部１２は、第１記憶部１０から削除された情報（変換処理部１６０が変換した情報）を記憶している。ここでは、第２記憶部１２は、対向ノードを表す（人間）可読な名前情報を情報３としている。
【００３４】
図５に示した状態でも、図４に示した状態とほぼ同じ処理結果を得ることが可能である。ただし、ノード３の情報が人間可読な名前情報として表現されているため、クエリがノード３に接合されたノードをさらに辿っていくようなものである場合には対応できない。例えば「Ａさんが好きな映画、に出演している人が好きな食べ物」のようなクエリには対応できない。そこで、情報処理装置１００は、削除したノード３が葉ノードでない場合には、図５に示した最適化にともなって支障が出る場合があるので、図８，９を用いて後述するような処理をさらに行う。
【００３５】
（最適化の第３例）
図６は、図３に示したグラフ構造のデータを構造変換部１６が最適化（変換）した第３例を示す図である。図６に示すように、例えばｔｙｐｅ＝ｌｉｋｅのエッジ、及びノード３（ｉｄ＝３）は第１記憶部１０から削除される。さらに、最適化の第３例では、情報処理装置１００は、対向ノードを表す（人間）可読な名前情報を情報３とし、削除したエッジとノードの情報をノード１（ｉｄ＝１）のプロパティ（一点鎖線で囲んだ範囲）として記憶する。つまり、最適化の第３例では、ノード１のプロパティが第２記憶部１２の代わりとなっている。図６に示した状態でも、図５に示した状態とほぼ同じ処理結果を得ることが可能である。また、情報処理装置１００は、削除したノード３が葉ノードでない場合には、図６に示した最適化にともなって支障が出る場合があるので、図８，９を用いて後述するような処理をさらに行う。
【００３６】
図７は、情報処理装置１００が上述したクエリを処理する場合の動作例を示すフローチャートである。図７に示すように、ステップ２００（Ｓ２００）において、ＣＰＵ（図示せず）は、ノード（ｎａｍｅ＝Ａ、ｔｙｐｅ＝ｈｕｍａｎ）を取得する。
【００３７】
ステップ２０２（Ｓ２０２）において、ＣＰＵは、エッジ（ｔｙｐｅ＝ｌｉｋｅ）の記憶場所が第１記憶部１０又は第２記憶部１２のいずれであるかを判定する。ＣＰＵは、エッジ（ｔｙｐｅ＝ｌｉｋｅ）の記憶場所が第１記憶部１０である場合にはＳ２０４の処理に進む。また、ＣＰＵは、エッジ（ｔｙｐｅ＝ｌｉｋｅ）の記憶場所が第２記憶部１２である場合にはＳ２１０の処理に進む。
【００３８】
ステップ２０４（Ｓ２０４）において、ＣＰＵは、エッジ（ｔｙｐｅ＝ｌｉｋｅ）を取得する。
【００３９】
ステップ２０６（Ｓ２０６）において、ＣＰＵは、Ｓ２０４の処理で取得したエッジに接合されるノードを取得する。
【００４０】
ステップ２０８（Ｓ２０８）において、ＣＰＵは、Ｓ２０６の処理で取得したノードのｎａｍｅを出力する。
【００４１】
ステップ２１０（Ｓ２１０）において、ＣＰＵは、第２記憶部１２から情報２がｌｉｋｅであるデータを取得する。
【００４２】
ステップ２１２（Ｓ２１２）において、ＣＰＵは、Ｓ２１０の処理で取得したデータの情報３がＩＤであるか否かを判定する。ＣＰＵは、取得したデータの情報３がＩＤである場合（Ｓ２１２：Ｙｅｓ）には、Ｓ２１４の処理に進む。また、ＣＰＵは、取得したデータの情報３がＩＤでない場合（Ｓ２１２：Ｎｏ）には、Ｓ２１８の処理に進む。
【００４３】
ステップ２１４（Ｓ２１４）において、ＣＰＵは、ノード（ｉｄ＝情報３）を取得する。
【００４４】
ステップ２１６（Ｓ２１６）において、ＣＰＵは、Ｓ２１４の処理で取得したノードのｎａｍｅを出力する。
【００４５】
ステップ２１８（Ｓ２１８）において、ＣＰＵは、情報３を出力する。
【００４６】
次に、対向ノードが葉ノードでない場合に、情報処理装置１００が行う処理について説明する。図８は、第１記憶部１０が記憶するグラフ構造のデータ（対向ノードが葉ノードでない場合）を例示する図である。図８に示すように、対向ノード（＝ノード３）が葉ノードでない場合、情報処理装置１００は、例えば以下の処理（第１〜第３の処理例）のいずれかを行う。
【００４７】
第１の処理例として、情報処理装置１００は、対向ノードが葉ノードでない場合には、最適化（データ構造の変換）を実行しない。また、第２の処理例として、情報処理装置１００は、対向ノードが葉ノードでない場合には、最適化の第１例（図４）を実行し、最適化の第２例（図５）又は最適化の第３例（図６）を実行しない。また、第３の処理例として、情報処理装置１００は、対向ノードが葉ノードでない場合には、対向ノードに接合された他のノード（対向ノードの対向ノード）をすべて最適化対象ノードとみなし、最適化を実行する。
【００４８】
図９は、対向ノードが葉ノードでない場合に情報処理装置１００が実行する第３の処理例を示す図である。図９に示すように、第３の処理例において、情報処理装置１００は、対向ノード（削除されるノード：図８におけるｉｄ＝３のノード）と接続されたノード（ｉｄ＝４）も最適化対象ノードとみなして最適化を実行する。ここで、ノード３（ｉｄ＝３）と２つのエッジ（ｔｙｐｅ＝ｌｉｋｅ、ｔｙｐｅ＝ｐｅｒｆｏｒｍｅｒ）の情報は、ノード１又はノード４のプロパティ（一点鎖線で囲んだ範囲）として記憶されている。
【００４９】
ただし、第３の処理例では、上述した「Ａさんが好きな映画、に出演している人が好きな食べ物」というようなクエリには対応できない。しかし、「食べ物Ｅを好きな人が出演している作品」というように、ノード３から先を辿らないクエリであれば対応することができる。
【００５０】
このように、情報処理装置１００は、第１記憶部１０が記憶するデータに対して、データ構造をグラフ構造から非グラフ構造へ変換処理部１６０などによって変換し、第２記憶部１２に記憶させることにより、処理速度の低下を防止することができる。
【００５１】
また、情報処理装置１００は、データ構造を非グラフ構造からグラフ構造へ逆変換処理部１６２などによって逆変換することも可能である。例えば、更新処理などの影響により、最適化対象ノードのエッジ数が十分小さくなった場合、又は第２記憶部１２が記憶するデータへのアクセス頻度が上昇した場合などに、逆変換処理部１６２は、逆変換を行う。つまり、逆変換処理部１６２は、これらの場合に第２記憶部１２が記憶するデータのデータ構造を非グラフ構造からグラフ構造へ変換（逆変換）し、第１記憶部１０に記憶させる。
【００５２】
例えば、図４に示した状態においてデータ構造を非グラフ構造からグラフ構造へ変換する場合、逆変換処理部１６２は、第２記憶部１２が記憶している情報１が示すノードから情報３が示すノードに向かってエッジを作成する。ここで、逆変換処理部１６２は、エッジの種類や名前として、情報２を使う。
【００５３】
また、図５又は図６に示した状態においてデータ構造を非グラフ構造からグラフ構造へ変換する場合、逆変換処理部１６２は、まず情報３からノードを作成する（このノードの種類や名前として情報３を使う）。ここで、逆変換処理部１６２は、もし同じ情報を有するノードが既に存在していれば、存在しているノードを用いる。次に、逆変換処理部１６２は、情報１が示すノードから、作成した（又は既存の用いた）ノードに向かってエッジを作成し、そのエッジの種類や名前として情報２を使う。
【００５４】
さらに、情報処理装置１００は、最適化対象ノードのエッジをリスト構造などで管理せず、エッジや対向ノードのＩＤなどに基づくツリー構造（Ｂ−Ｔｒｅｅなど）によって管理するようにデータの構造を変更されてもよい。具体的には、例えば、第１記憶部１０は、ノードに関するエッジ、又はノードのエッジに接合している他のノードを一意に識別する識別情報に基づくツリー構造により、ノードに関するエッジの一覧をノードの情報とするグラフ構造を有するデータを記憶する。これにより、情報処理装置１００は、特定のＩＤを持つエッジや対向ノードをＯ（ｌｏｇＭ）の計算量で検索することが可能になる。
【００５５】
本実施形態の情報処理装置で実行される情報処理プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【００５６】
また、本実施形態の情報処理装置で実行される情報処理プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。
【００５７】
また、本発明のいくつかの実施形態を複数の組み合わせによって説明したが、これらの実施形態は例として提示したものであり、発明の範囲を限定することは意図していない。これら新規の実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００５８】
１０  第１記憶部
１２  第２記憶部
１４  第３記憶部
１６  構造変換部
１８  判定部
１００  情報処理装置
１６０  変換処理部
１６２  逆変換処理部
【図１】
2014153961.tif 000003
【図２】
2014153961.tif 000004
【図３】
2014153961.tif 000005
【図４】
2014153961.tif 000006
【図５】
2014153961.tif 000007
【図６】
2014153961.tif 000008
【図７】
2014153961.tif 000009
【図８】
2014153961.tif 000010
【図９】
2014153961.tif 000011