(57)【特許請求の範囲】
【請求項１】
各データ要素をノードとしそれらデータ要素同士の関係の種類を表す関係データをリンクとするグラフを表すグラフデータについて、前記グラフにおける検索の基準位置を示す基準ノードと、検索対象の部分グラフが満たすべき検索条件と、の入力をユーザから受け付ける入力受付手段と、
前記検索条件を満たす部分グラフを前記グラフデータから検索する通常検索手段と、
前記通常検索手段により検索された１以上の検索結果をそれぞれ前記基準ノードから当該検索結果までの前記グラフ上の経路を示す経路データとともに示す検索結果データを前記ユーザに提示し、提示した前記検索結果データに含まれる１以上の検索結果の中から前記ユーザの選択を受け付ける選択受付手段と、
ユーザごとに、当該ユーザが過去の前記通常検索手段による検索において前記選択受付手段に対して選択した検索結果に対応する経路データを、当該ユーザの検索経路履歴として記憶する経路データ記憶手段と、
ユーザから前記検索経路履歴を利用する履歴利用検索の指示と当該履歴利用検索の基準とするノードの指定とを受けると、前記グラフ上で、前記基準とするノードからみて、当該ユーザの検索経路履歴として前記経路データ記憶手段に記憶された各経路データが示す経路に類似する経路を経た位置にあるノード又は部分グラフを検索し、当該検索の結果得られた各ノード又は部分グラフを提示する履歴利用検索手段と、
を備える検索装置。
【請求項２】
前記経路データ記憶手段は、前記ユーザの検索経路履歴に含まれる経路データごとに経路評価値を記憶しており、経路データに対応する経路評価値は、過去の前記履歴利用検索手段の検索結果のうち当該経路データが示す経路に対応する検索結果が当該ユーザにより選択された回数に基づく値であり、
前記履歴利用検索手段は、前記ユーザからの前記履歴利用検索の指示に応じて行った検索の結果得られたノード又は部分グラフを、当該経路データの経路評価値に基づく検索順位に従って配列して提示する、
ことを特徴とする請求項１に記載の検索装置。
【請求項３】
前記履歴利用検索手段は、前記ユーザからの前記履歴利用検索の指示に応じて行った検索の結果得られたノード又は部分グラフと前記履歴利用検索の基準とするノードとを結ぶ経路と、前記履歴利用検索で用いた経路データと、の類似度を求め、求めた類似度と当該経路データの経路評価値と、に基づく検索順位に従って、前記検索の結果得られたノード又は部分グラフを配列して提示する、
ことを特徴とする請求項２に記載の検索装置。
【請求項４】
ユーザから、前記選択受付手段に対して選択した検索結果に対応する経路データの端点ノードから拡張すべき１以上のリンクの指定を受け付け、当該指定された１以上のリンクを当該端点ノードに付加することにより当該経路データを拡張し、拡張された経路データを当該ユーザの検索経路履歴として前記経路データ記憶手段に記憶させる経路拡張手段、
を更に備える、ことを特徴とする請求項１〜３のいずれか１項に記載の検索装置。
【請求項５】
前記選択受付手段に対して選択した検索結果に対応する経路データを拡張するリンク数の指定をユーザから受け付け、前記グラフ上で当該経路データを端点ノードからそのリンク数分のリンクだけ拡張し、拡張された経路データを当該ユーザの検索経路履歴として前記経路データ記憶手段に記憶させる経路拡張手段、
を更に備える、ことを特徴とする請求項１〜３のいずれか１項に記載の検索装置。
【請求項６】
コンピュータを、
各データ要素をノードとしそれらデータ要素同士の関係の種類を表す関係データをリンクとするグラフを表すグラフデータについて、前記グラフにおける検索の基準位置を示す基準ノードと、検索対象の部分グラフが満たすべき検索条件と、の入力をユーザから受け付ける入力受付手段、
前記検索条件を満たす部分グラフを前記グラフデータから検索する通常検索手段と、
前記通常検索手段により検索された１以上の検索結果をそれぞれ前記基準ノードから当該検索結果までの前記グラフ上の経路を示す経路データとともに示す検索結果データを前記ユーザに提示し、提示した前記検索結果データに含まれる１以上の検索結果の中から前記ユーザの選択を受け付ける選択受付手段、
ユーザごとに、当該ユーザが過去の前記通常検索手段による検索において前記選択受付手段に対して選択した検索結果に対応する経路データを、当該ユーザの検索経路履歴として記憶する経路データ記憶手段、
ユーザから前記検索経路履歴を利用する履歴利用検索の指示と当該履歴利用検索の基準とするノードの指定とを受けると、前記グラフ上で、前記基準とするノードからみて、当該ユーザの検索経路履歴として前記経路データ記憶手段に記憶された各経路データが示す経路に類似する経路を経た位置にあるノード又は部分グラフを検索し、当該検索の結果得られた各ノード又は部分グラフを提示する履歴利用検索手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置及びプログラムに関する。
【背景技術】
【０００２】
データ要素同士の関係が構成するグラフ構造を記述する方式が知られている。例えば、リソース同士の関係を主語、述語、目的語の組（「トリプル」と呼ばれる）で記述するＲＤＦ（Resource Description Framework）はその一例である。ＲＤＦでは、複数のトリプルにより、主語又は目的語であるリソースをノードとし、述語をリンク（エッジ）とするグラフが表される。また、ＲＤＦで記述されたデータを検索するコンピュータ言語として、例えばＳＰＡＲＱＬ（SPARQL Protocol and RDF Query Language）が知られている。
【０００３】
特許文献１に開示されたデータベースシステムでは、複数のノードからなるノード集合体と各ノード間の関連の程度を示すリンクの集合からなるリンク集合体とを定義する。ノード・リンク集合体をデータベースのフロントエンドにおき、任意のノードが着目ノードとして指定された場合に、データベース内から着目ノードに対応するデータがオペレータに提供されるようにする。各ノードにはキーワードを定義しておく。オペレータが着目ノードに対して検索指示を与えると、リンクを介して、着目ノードに対してある程度以上の関連性を有する各ノードのキーワードがオペレータに提示され、そのうちの１つがオペレータにより新たな着目ノードとして採択される。各リンクは重みをもち、ノードの採択行為により、重みづけの修正や新リンクの追加が行われる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１０−１９８７０１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、データ要素をノードとしデータ要素同士の関係をリンクとするグラフ内での検索において、個々のユーザの過去の検索のパターンに合わせて検索できる装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
請求項１に係る発明は、各データ要素をノードとしそれらデータ要素同士の関係の種類を表す関係データをリンクとするグラフを表すグラフデータについて、前記グラフにおける検索の基準位置を示す基準ノードと、検索対象の部分グラフが満たすべき検索条件と、の入力をユーザから受け付ける入力受付手段と、前記検索条件を満たす部分グラフを前記グラフデータから検索する通常検索手段と、前記通常検索手段により検索された１以上の検索結果をそれぞれ前記基準ノードから当該検索結果までの前記グラフ上の経路を示す経路データとともに示す検索結果データを前記ユーザに提示し、提示した前記検索結果データに含まれる１以上の検索結果の中から前記ユーザの選択を受け付ける選択受付手段と、ユーザごとに、当該ユーザが過去の前記通常検索手段による検索において前記選択受付手段に対して選択した検索結果に対応する経路データを、当該ユーザの検索経路履歴として記憶する経路データ記憶手段と、ユーザから前記検索経路履歴を利用する履歴利用検索の指示と当該履歴利用検索の基準とするノードの指定とを受けると、前記グラフ上で、前記基準とするノードからみて、当該ユーザの検索経路履歴として前記経路データ記憶手段に記憶された各経路データが示す経路に類似する経路を経た位置にあるノード又は部分グラフを検索し、当該検索の結果得られた各ノード又は部分グラフを提示する履歴利用検索手段と、を備える検索装置である。
【０００７】
請求項２に係る発明は、前記経路データ記憶手段は、前記ユーザの検索経路履歴に含まれる経路データごとに経路評価値を記憶しており、経路データに対応する経路評価値は、過去の前記履歴利用検索手段の検索結果のうち当該経路データが示す経路に対応する検索結果が当該ユーザにより選択された回数に基づく値であり、前記履歴利用検索手段は、前記ユーザからの前記履歴利用検索の指示に応じて行った検索の結果得られたノード又は部分グラフを、当該経路データの経路評価値に基づく検索順位に従って配列して提示する、ことを特徴とする請求項１に記載の検索装置である。
【０００８】
請求項３に係る発明によれば、前記履歴利用検索手段は、前記ユーザからの前記履歴利用検索の指示に応じて行った検索の結果得られたノード又は部分グラフと前記履歴利用検索の基準とするノードとを結ぶ経路と、前記履歴利用検索で用いた経路データと、の類似度を求め、求めた類似度と当該経路データの経路評価値と、に基づく検索順位に従って、前記検索の結果得られたノード又は部分グラフを配列して提示する、ことを特徴とする請求項２に記載の検索装置である。
【０００９】
請求項４に係る発明は、ユーザから、前記選択受付手段に対して選択した検索結果に対応する経路データの端点ノードから拡張すべき１以上のリンクの指定を受け付け、当該指定された１以上のリンクを当該端点ノードに付加することにより当該経路データを拡張し、拡張された経路データを当該ユーザの検索経路履歴として前記経路データ記憶手段に記憶させる経路拡張手段、を更に備える、ことを特徴とする請求項１〜３のいずれか１項に記載の検索装置である。
【００１０】
請求項５に係る発明は、前記選択受付手段に対して選択した検索結果に対応する経路データを拡張するリンク数の指定をユーザから受け付け、前記グラフ上で当該経路データを端点ノードからそのリンク数分のリンクだけ拡張し、拡張された経路データを当該ユーザの検索経路履歴として前記経路データ記憶手段に記憶させる経路拡張手段、を更に備える、ことを特徴とする請求項１〜３のいずれか１項に記載の検索装置である。
【００１１】
請求項６に係る発明は、コンピュータを、各データ要素をノードとしそれらデータ要素同士の関係の種類を表す関係データをリンクとするグラフを表すグラフデータについて、前記グラフにおける検索の基準位置を示す基準ノードと、検索対象の部分グラフが満たすべき検索条件と、の入力をユーザから受け付ける入力受付手段、前記検索条件を満たす部分グラフを前記グラフデータから検索する通常検索手段と、前記通常検索手段により検索された１以上の検索結果をそれぞれ前記基準ノードから当該検索結果までの前記グラフ上の経路を示す経路データとともに示す検索結果データを前記ユーザに提示し、提示した前記検索結果データに含まれる１以上の検索結果の中から前記ユーザの選択を受け付ける選択受付手段、ユーザごとに、当該ユーザが過去の前記通常検索手段による検索において前記選択受付手段に対して選択した検索結果に対応する経路データを、当該ユーザの検索経路履歴として記憶する経路データ記憶手段、ユーザから前記検索経路履歴を利用する履歴利用検索の指示と当該履歴利用検索の基準とするノードの指定とを受けると、前記グラフ上で、前記基準とするノードからみて、当該ユーザの検索経路履歴として前記経路データ記憶手段に記憶された各経路データが示す経路に類似する経路を経た位置にあるノード又は部分グラフを検索し、当該検索の結果得られた各ノード又は部分グラフを提示する履歴利用検索手段、として機能させるためのプログラムである。
【発明の効果】
【００１２】
請求項１又は６に係る発明によれば、データ要素をノードとしデータ要素同士の関係をリンクとするグラフ内での検索において、個々のユーザの過去の検索のパターンに合わせて検索できる。
【００１３】
請求項２に係る発明によれば、ユーザが過去に検索に多く使用した経路データに類似する経路ほど高い順位として提示することができる。
【００１４】
請求項３に係る発明によれば、ユーザが過去に検索に多く使用した経路データに類似する経路ほど、かつその類似度が高いほど、高い順位として提示することができる。
【００１５】
請求項４に係る発明によれば、ユーザの希望によりよく沿った経路データを記憶し、その経路データに類似する経路を検索することが可能になる。
【００１６】
請求項５に係る発明によれば、ユーザの希望によりよく沿った経路データに類似する経路を検索できる可能性を高めることができる。
【図面の簡単な説明】
【００１７】
【図１】実施形態の検索装置の構成例を示す機能ブロック図である。
【図２】データ要素群が構成するグラフの一例を示す図である。
【図３】グラフを規定するグラフデータの一例を示す図である。
【図４】検索経路履歴データの例を示す図である。
【図５】リンクのみの経路データが示す経路を説明するための図である。
【図６】検索経路履歴データの別の例を示す図である。
【図７】検索処理の手順の一例を示すフローチャートである。
【図８】関連ノード抽出処理の手順の一例を示すフローチャートである。
【図９】関連ノード抽出処理の結果得られるデータの一例を示す図である。
【図１０】検索条件の部分グラフの一例を示す図である。
【図１１】図２のグラフにおける検索結果の例を示す図である。
【図１２】ソート結果のデータ内容の一例を示す図である。
【図１３】類似検索処理の手順の一例を示すフローチャートである。
【図１４】類似検索結果の例を示す図である。
【図１５】検索条件を満たす部分グラフの一部が検索範囲からはみ出す例を示す図である。
【図１６】検索範囲を拡張することで元の検索範囲からはみ出す部分グラフが検索できるようになることを示す図である。
【図１７】履歴利用検索処理の手順の一例を示すフローチャートである。
【図１８】履歴利用検索の検索結果の一例を示す図である。
【図１９】履歴利用検索処理の手順の第２の例を示すフローチャートである。
【図２０】履歴利用検索処理の第３の例で用いられる検索経路履歴データの例を示す図である。
【図２１】履歴利用検索処理の手順の第３の例を示すフローチャートである。
【図２２】経路拡張を説明するための図である。
【発明を実施するための形態】
【００１８】
図１に、実施形態の検索装置の機能的な構成の一例を示す。
【００１９】
図１の構成において、データベース１０には、データ要素同士の関係が構成するグラフ構造を表すグラフデータ１０ａが記憶されている。以下では、データ要素同士の関係をＲＤＦで表現する場合の例を用いて説明する。ただし、実施形態の検索手法は、ＲＤＦ以外の方式を用いる場合に適用してもよい。
【００２０】
図２に、データ要素同士の関係のグラフの例を示す。この例では、楕円形のノードがデータ要素を示し、ノード同士を結ぶリンク（矢印で示す）がそれらノード同士の関係を示す。この例では、ノード内の文字列が、対応するデータ要素のデータ内容の少なくとも一部を示し、リンクの矢印の近傍に表示された文字列が、データ要素間の関係の種類を示す。ＲＤＦを用いている場合、矢印の根本側のノードが主語を、矢印の先端側のノードが目的語をそれぞれ示し、リンク（矢印）がそれら両者間の関係である述語を示す。例えば、ノード１０２と１０４とが構成する関係は、”Workplace-a”という識別名の作業場所は”User-c”という識別名のユーザにより「参加された」（”participated”）、ということを示す（言い換えれば、「”Workplace-a”に”User-c”が参加した」ということ）。
【００２１】
図３は、図２に示したグラフを表すグラフデータ１０ａの一例を示す。図３に例示するグラフデータには、主語、述語、目的語の組である「トリプル」が複数含まれている。１つの例では、データベース１０には、図３に例示するようなグラフデータ１０ａが登録されている。ただし、これはあくまで一例に過ぎず、データ要素間の関係を記述できるデータ形式であれば、図３に例示した形式以外の形式を用いてもよい。
【００２２】
図１の説明に戻ると、データベース１０には、各ユーザが過去に検索した際に使用した経路（以下、「履歴経路」と呼ぶ）のリストを含む検索経路履歴データ１０ｂも記憶されている。後で詳しく説明するように、この実施の形態の装置は、基準ノードと検索条件の部分グラフの指定をユーザから受け付け、基準ノードから検索条件を満たす検索結果の部分グラフまでのグラフ上での経路を求めてユーザに提示する機能（後述する「初期検索」）を備えている。部分グラフは、元のグラフ全体のうちの一部分のことであり、単一のノード、単一のリンク、又は相互に接続された１以上のノードと１以上のリンクの組合せである。経路は、基準ノードから検索結果の部分グラフまでを結ぶ、グラフ上の１以上のリンクの並び（又はリンクとノードの並び）のことである。ユーザは、各検索結果についての経路を見て、どの検索結果が自分の知りたがっていたものかを判別し、判別した検索結果を選択して詳細情報を表示する。このように、ユーザが選択した検索結果に対応する経路が、履歴経路である。ユーザが検索を行い、その検索結果の中から所望のものを選択すると、その検索結果に対応する経路が履歴経路として、当該ユーザに対応づけて検索履歴経路データ１０ｂに追加される。
【００２３】
図４に検索経路履歴データ１０ｂのデータ内容に一例を示す。検索経路履歴データ１０ｂには、ユーザごとに、当該ユーザが過去に検索に使用した履歴経路の情報が含まれる。図示のように、検索経路履歴データ１０ｂは、「ユーザＩＤ」、「履歴経路ＩＤ」、「履歴経路データ」、「経路評価値」の項目を含んでいる。「ユーザＩＤ」は、履歴経路を使用したユーザの識別情報である。「履歴経路ＩＤ」は、履歴経路の識別情報である。
【００２４】
「履歴経路データ」は、当該履歴経路を表すデータである。図４の例では、履歴経路データは、当該履歴経路を構成するリンクの並び、すなわちそれらリンクの種類（述語）を基準ノードに近い順に並べたものである。例えば、図５に示すように、楕円１０３で囲んだ検索結果の部分ノードがユーザから選択された場合、基準ノード１０２からその検索結果までを結ぶ順方向のリンク”participated”と逆方向の”created”の並びが、履歴経路データとして記憶されることになる。なお、図中”created”に付された下線は、当該リンク”created”が逆方向であること示す。一方、下線を付されていないリンクは順方向であることを示す。この例では、経路上にあるノードの情報は履歴経路データには含まれない。
【００２５】
「経路評価値」は、当該履歴経路の重要度を示す評価値であり、当該履歴経路が過去に当該ユーザにより使用された回数が多いほど高い値となる。すなわち、後述する「類似検索」や「履歴利用検索」により履歴経路が検索に使用されるが、その使用の回数（より詳しくは、多数提示される検索結果のうちユーザが所望のものとして選択した回数）が多いほど、ユーザが過去にその履歴経路が表すパターンで情報を探していたことが多いことを示す。このように、履歴経路の使用回数が多いほど、すなわち当該履歴経路の経路評価値が高いほど、ユーザが当該履歴経路に沿った思考のパターンでものを探す可能性が高いといえる。なお、履歴経路の使用回数自体を経路評価値としてもよい。
【００２６】
図６に、検索経路履歴データ１０ｂの別の例を示す。図６の例では、履歴経路データに、経路上のノードの情報（”User-c”など）が含まれている。すなわち、この例の履歴経路データは、履歴経路を構成するリンク及びノードを、基準ノードから近い順に並べたものである。
【００２７】
再び図１の説明に戻ると、データベース１０は、後で説明する関連ノード抽出部２２、部分グラフ検索処理部２６等のグラフ検索のための機能が実装されるコンピュータに対して実装されていてもよいし、このコンピュータからインターネット等のネットワークを介して接続された別のコンピュータに実装されていてもよい。
【００２８】
基準ノード指定受付部１２は、検索のための指定項目の１つとして、ユーザから基準ノードの指定を受け付ける。基準ノードは、ユーザが検索の基準位置（すなわち目印）とするノードのことである。基準ノード指定受付部１２は、例えばグラフを画面表示し、ユーザからポインティングデバイス等によりそのグラフ上で基準ノードとするノードの指定を受け付けてもよい。また、別の例として、基準ノード指定受付部１２は、基準ノードが満たすべき条件（例えばノードの種類）の指定をユーザから受け付け、その条件を満たすノードをグラフデータから検索してユーザに提示し、提示されたノードの中から基準ノードとするものをユーザが選択するようにしてもよい。ホップ数指定受付部１４は、基準ノードからの検索範囲を表す上限ホップ数（すなわち、リンクの数）の指定をユーザから受け付ける。
【００２９】
検索条件指定受付部１６は、グラフから検索すべき検索対象が満たすべき検索条件の指定をユーザから受け付ける。検索対象は、例えば部分グラフの形で指定してもよい。検索条件となる部分グラフは、典型的には、１以上のノードが１以上のリンクで結ばれた一続きのグラフである。また、１つのリンクのみ、あるいは１つのノードのみ、を検索条件の部分グラフとして指定可能としてもよい。検索条件の部分グラフに含まれるノード及びリンクの１以上を変数としてもよい。検索条件は、部分グラフ全体を検索結果として求めるものであってもよいし、その検索条件に適合（マッチ）する部分グラフの中の指定した１以上の変数を求めるものであってもよい。この場合、データベース１０に記憶されたデータにより表されるグラフの中から、検索条件の部分グラフに適合する部分グラフが検索される。なお、検索条件は、例えば、ＳＰＡＲＱＬ等のクエリ言語により記述すればよい。
【００３０】
本実施形態の検索装置は、「初期検索」と「類似検索」と「履歴利用検索」の３種類の検索方式をサポートしている。初期検索は、基準ノード及び検索条件を指定して行う検索である。一方、類似検索は、初期検索の検索結果を利用した検索である。類似検索では、基準ノードの指定は受けるが、検索条件の指定は不要である。また、履歴利用検索では、着目ノードを指定するだけでよい。なお、初期検索及び類似検索及び履歴利用検索のいずれについても、検索範囲を規定するホップ数の指定は可能であるが必須ではない（ホップ数を指定しない場合、データベース１０に記憶されたデータにより表されるグラフ全体となる）。したがって、初期検索のためのユーザインタフェース（ＵＩ）である初期検索ＵＩ１８は、基準ノード指定受付部１２，検索条件指定受付部１６及びホップ数指定受付部１４を含んだものとなり、類似検索のためのＵＩである類似検索ＵＩ２０は基準ノード指定受付部１２及びホップ数指定受付部１４を含んだものとなる。基準ノード指定受付部１２，ホップ数指定受付部１４及び検索条件指定受付部１６は、基準ノード、ホップ数、検索条件などの指定のための入力画面の画像を例えばウェブページその他の形式で作成し、その入力画面画像をユーザが操作するクライアント（例えばウェブブラウザ、あるいは専用の検索用クライアント）に対して提供する。この場合、クライアントは、図１に示した検索装置が実装されたコンピュータ上に実装されてもよいし、このコンピュータに対してインターネット等のネットワークを介して接続されるコンピュータ上に実装されていてもよい。
【００３１】
関連ノード抽出部２２は、基準ノード指定受付部１２で受け付けた基準ノードから、ホップ数指定受付部１４に指定されたホップ数の範囲内に含まれるノード（及びリンク）を抽出する。抽出されたノード群からなる部分グラフが、検索範囲となる。関連ノード記憶部２４には、それら抽出された関連ノード群が記憶される。
【００３２】
部分グラフ検索処理部２６は、関連ノード記憶部２４に記憶された関連ノード群からなる部分グラフから、検索条件指定受付部１６で受け付けた検索条件に適合する部分グラフを検索する。検索結果記憶部２８は、部分グラフ検索処理部２６の検索結果を記憶する。
【００３３】
ソート部３０は、検索結果記憶部２８に記憶された各検索結果の順位付け（すなわちスコア付け）と、順位（又はスコア）に基づくソート（並べ替え）処理を実行する。この実施形態では、ソート部３０は、ホップ数基準ソート処理３２と経路類似度基準ソート処理３４と履歴利用検索ソート処理３５の３種類の順位付け及びソート処理の機能を備える。
【００３４】
ホップ数基準ソート処理３２は、基準ノードから検索結果の部分グラフまでのホップ数（すなわちリンクの数）に基づいて順位付け及びソートを行うものである。基準ノードからのホップ数が少ないほど順位（あるいはスコア）を高くし、順位が高いものから降順に検索結果をソートする。ホップ数基準ソート処理３２は、例えば、初期検索ＵＩ１８から指示された初期検索の結果をソートする際に用いられる。
【００３５】
経路類似度基準ソート処理３４では、基準ノードから検索結果までのグラフ上での経路と、基準の経路との類似度に基づいて順位付け及びソートを行う。基準の経路としては、例えば、初期検索の際の基準ノードから、初期検索の検索結果のうちユーザが選択したものまでのグラフ上での経路を用いればよい。経路類似度基準ソート処理３４は、例えば、初期検索の結果を利用した類似検索の検索結果の順位付け及びソートの際に用いられる。
【００３６】
なお、例示したホップ数基準ソート処理３２と経路類似度基準ソート処理３４はあくまで一例に過ぎず、別の基準に基づく順位（スコア）付け及びソート処理を採用してもよい。ソート結果記憶部３６は、ソート部３０によるソート結果を記憶する。
【００３７】
また、履歴利用検索ＵＩ５０は、履歴利用検索（詳細は後述）の起点となる着目ノードの指定を受け付ける。また、グラフ中から着目ノードを見つけ出すこと自体に手間がかかる場合もあるので、履歴利用検索ＵＩ５０で着目ノードを求めるための検索条件をユーザから受け付け、着目ノード候補検索部５２がその条件を満たすノードの候補を着目ノードの候補として検索してもよい。着目ノードの検索条件としては、例えば、（ア）「ノードの種類がユーザ（”User”）に該当する」、（イ）「なんらかの会議（ノードの種類が”Workplace”に該当）に参加（”participated”）しているユーザ（ノードの種類が”User”に該当）」、（ウ）「特定の会議”Workplace-a”に参加（”participated”）しているユーザ（ノードの種類が”User”に該当）」など様々なものがある。（イ）及び（ウ）の検索条件は、ノードとリンクの組合せである部分グラフと、その部分グラフの中で着目するノードを特定する情報（上述の例では、ノードの種類が”User”に該当するという情報）を含んでいる。このような検索条件は、ＳＰＡＲＱＬ等のクエリ言語で記述すればよい。履歴利用検索ＵＩ５０は、着目ノード候補検索部５２が求めた着目ノードの候補を列挙して表示し、ユーザからの選択を受け付ける。そして、ユーザが選択した候補を着目ノードとして履歴利用検索処理部５４に通知する。
【００３８】
履歴利用検索処理部５４は、履歴利用検索ＵＩ５０から通知された着目ノードと、検索経路履歴データ１０ｂに記憶された当該ユーザ（履歴利用検索を指示したユーザ）の履歴経路とに基づいた検索を行う。すなわち、履歴利用検索処理部５４は、着目ノードを起点として、当該ユーザの履歴経路と同じ又は類似する経路を経た位置にあるノード（又はそのノードの近傍のリンクと他のノードを含む部分グラフ）を検索結果として求め、求めた各検索結果の検索スコアを求める。履歴利用検索処理部５４が行う処理については、後でフローチャートを参照して更に詳しく説明する。  履歴利用検索ソート処理３５では、履歴利用検索処理部５４の検索結果を、検索スコアの順にソートする。
【００３９】
検索結果提示ＵＩ４０は、関連ノード抽出部２２，部分グラフ検索処理部２６、履歴利用検索処理部５４及びソート処理部３０による検索及びソート処理の結果をユーザに提示するユーザインタフェース処理を実行する。検索結果提示ＵＩ４０は、ソート結果提示部４２及び選択受付部４４を備える。
【００４０】
ソート結果提示部４２は、ソート部３０によるソート結果（例えばこれはソート結果記憶部３６に保持されている）を表示するソート結果表示画像を例えばウェブページなどの形式で生成し、この表示画像をユーザが操作するクライアント（例えばウェブブラウザ、あるいは専用の検索用クライアント）に提供する。
【００４１】
選択受付部４４は、そのソート結果表示画像において順位（又はスコア）に従って並べられた各検索結果の中から、ユーザが着目するものの選択を受け付ける。例えば、ユーザが選択受付部４４を用いて、表示された各検索結果の中から更に詳細に確認したいものを選択すると、選択された検索結果の詳細情報が表示されるようにしてもよい。詳細情報としては、例えば基準ノードからその検索結果の部分グラフまでのグラフ上の経路の表示情報（例えばそのグラフ上でその経路を強調表示したものなど）や、検索結果の部分グラフに含まれるノードやリンクについての情報（例えばノードに含まれるＵＲＬ（Uniform Resource Locator）が指し示すリソースの内容など）などがある。また、選択受付部４４は、ソートされた各検索結果のうち、ユーザが次の類似検索における基準とするものの選択を受け付ける機能を備える。ユーザが、次の類似検索の基準とする検索結果を選択すると、選択受付部４４は、基準ノードからその選択された検索結果までのグラフ上での経路を基準経路として求め、基準経路記憶部３８に記憶する。基準経路記憶部３８に記憶された基準経路は、後の類似検索における検索結果をソートする際に経路類似度基準ソート処理３４によって参照される。
【００４２】
次に、この実施形態の検索装置における検索処理の流れの例を説明する。
【００４３】
この実施形態の検索装置の基本ＵＩ画面には、初期検索と履歴利用検索とが選択肢として表示される。その中でユーザが初期検索を選択すると、図７の手順が実行される。初期検索では、図７に示すように、まず初期検索ＵＩ１８の基準ノード指定受付部１２により、グラフ中のノードのうち基準ノードとするノードの指定をユーザから受け付けると共に（Ｓ１０）、ホップ数指定受付部１４によりユーザから上限ホップ数の指定を受け付ける（Ｓ１２）。
【００４４】
次に、関連ノード抽出部２２は、指定された基準ノードから指定された上限ホップ数以内で到達できるノード群を、関連ノード群として抽出する（Ｓ１４）。データベース１０に記憶されたデータにより規定される元のグラフのうち、抽出された関連ノード群により構成される部分グラフが、以降の検索処理における検索範囲となる。例えば、図２のグラフにおいて、ノード１０２が基準ノードに指定され、上限ホップ数が「３」と指定された場合、検索範囲は図１１に破線の矩形で示す範囲となる。
【００４５】
関連ノード群の抽出処理（Ｓ１４）の詳細な処理手順の一例を、図８に示す。この例では、まずホップ数のカウンタを１に初期化し（Ｓ７０）、処理対象とする注目ノードを収容するためのリストに、Ｓ１０で指定された基準ノードを入れる（Ｓ７２）。ここで、注目ノードのリストは、ホップ数ごとに作成される。例えば、Ｓ７２では、カウンタが示すホップ数「１」に対応するリストに対し、基準ノードが唯一の注目ノードとして登録されることになる。
【００４６】
次に、リスト中の注目ノードごとに、Ｓ７４〜Ｓ８０の処理を実行する。すなわち、Ｓ７４でリストから注目ノードを１つ取り出し、Ｓ７６で、元のグラフにおいてその注目ノードに隣接する（すなわち１つのリンクを介して接続された）ノードをすべて、関連ノードとして抽出する。なお、Ｓ７６では、既に関連ノードとして抽出済のノードは、重複して抽出しない。次に、抽出した各関連ノードについて、基準ノードから当該関連ノードまでのグラフ上での経路を求め、その経路の情報を当該関連ノードに対応づけて関連ノード記憶部２４に登録する（Ｓ７８）。
【００４７】
このようにして関連ノード記憶部２４に記憶される各関連ノードのデータの例を、図９に示す。この例では、関連ノードごとに、そのノードの識別情報（図中での「ノード」）、基準ノードからのホップ数（図中での「ホップ数」）、及び基準ノードからの経路情報（図中での「基準ノードからの経路」）が登録されている。ここで「ホップ数」は、Ｓ７８の処理を行う時点でのカウンタの値を登録すればよい。基準ノードからの経路情報は、例えば、基準ノードから出発して当該関連ノードに到達するまでに通過するグラフ上のリンク及びノードを、通過する順に並べたリストである。図９に示した関連ノード群のデータは、図２のグラフにおいてノード１０２を基準ノードとした場合の例である。
【００４８】
再び図８の説明に戻ると、Ｓ７６にて抽出された各隣接ノードが、次のホップ数に対応するリストに対して注目ノードとして追加される（Ｓ８０）。なお、Ｓ７４でリストから取り出された注目ノードは、リストからは削除されている。
【００４９】
今回のホップ数に対応するリストに含まれるすべての注目ノードについてＳ７４〜Ｓ８０の処理が終了すると、ホップ数のカウンタの値を１だけインクリメントする（Ｓ８２）。そして、カウンタの値が上限ホップ数を上回ったかどうかを検査し（Ｓ８４）、上回っていなければ、そのカウンタ値に対応するリストに含まれる各注目ノードを対象として、Ｓ７４〜Ｓ８０の処理を行う。Ｓ８４で、カウンタの値が上限ホップ数を超えていると判定された場合、図８の処理は終了する。
【００５０】
再び図７の手順の説明に戻る。初期検索ＵＩ１８の検索条件指定受付部１６により、検索条件の指定を受け付ける（Ｓ１６）。検索条件として指定される部分グラフの例を図１０に示す。図１０に例示する部分グラフは、”Document”（文書）に該当する種類のノードを主語とし、”Comment”（コメント）に該当する種類のノードを目的語とし、述語が”commented”（コメントされた）である１つのトリプルで表されるグラフである。この部分グラフは、ある文書に対しあるコメントが付されている、という関係を表す。もちろん、検索条件としては、３以上のノードを含んだもっと複雑な部分グラフを指定してもよい。図７の手順では関連ノード群の抽出（Ｓ１４）の後に検索条件の指定を受け付けているが、検索条件の指定を受け付けるタイミングはＳ１４の前であってももちろんよい。ユーザが入力した検索条件（部分グラフ）は、例えばＳＰＡＲＱＬにより記述され、部分グラフ検索処理部２６に渡される。
【００５１】
部分グラフ検索処理部２６は、Ｓ１４で抽出された関連ノード群（すなわち検索範囲）の中から、Ｓ１６で指定された検索条件にマッチする部分グラフを検索する（Ｓ１８）。例えば、図２に例示したグラフにおいて、ノード１０２を基準ノードとし、上限ホップ数を３とし、図１０に例示した部分グラフを検索条件として検索を行うと、図１１に例示するように、部分グラフ１１０及び１１２が検索結果として求められる。
【００５２】
次に、ソート部３０が、部分グラフ検索処理部２６により検索された各検索結果を、ホップ数の順にソートする（Ｓ２０）。このソート処理では、例えば、Ｓ１８で求められた検索結果ごとに、当該検索結果の部分グラフに含まれる各ノードの基準ノードからのホップ数を関連ノード記憶部２４（図９参照）から求め、それらホップ数のうちの例えば最小値を当該検索結果に対応するホップ数とする。そして、そのホップ数の昇順に各検索結果をソートする。ソート結果は、ソート結果記憶部３６に記憶される。ソート結果の例を、図１２に示す。この例では、ソート結果記憶部３６には、各検索結果の部分グラフが、対応するホップ数の小さい順に、基準ノードからその部分グラフまでの経路と共に登録される。なお、この経路の情報は、当該検索結果の部分グラフにおけるホップ数が最小のノードの、基準ノードからの経路情報であり、これは関連ノード記憶部２４から求めればよい。なお、ＲＤＦにより表されるグラフは有向グラフ（すなわち、述語が表すリンクは、例えば主語から目的語を指す矢印となる）なので、基準ノードから部分グラフまでの経路に含まれるリンクは、（基準ノードから部分グラフの入口のノードに向かって）順方向のものと逆方向のものがある。図１２では、逆方向のリンクには、下線を付している。
【００５３】
なお、ここで説明したソート処理の例では、検索結果の部分グラフに含まれるノードの中のホップ数の最小値を当該検索結果のホップ数としたが、これは一例に過ぎない。この代わりに、検索結果の部分グラフに含まれるノードの中のホップ数の例えば最大値を当該検索結果のホップ数としてもよい。
【００５４】
このようにソート結果が求められると、そのソート結果がソート結果提示部４２によりユーザに提供される（Ｓ２２）。提示されるソート結果の表示画像には、順位に従って並べられた各検索結果が、基準ノードからのグラフ上の経路の情報と共に表示される。
【００５５】
基準ノードから検索結果の部分グラフまでの全体をユーザが前もって検索条件として指定することは困難な場合が多いが、基準ノードと部分グラフ（検索条件）とを指定することはそれよりもはるかに容易である。ユーザが、例えば断片的な記憶などを元に基準ノードと検索条件の部分グラフとを本実施形態の検索装置に指定すれば、この検索装置は、検索条件を満たす各検索結果（部分グラフ）を、基準ノードからその検索結果までの経路の情報と共にユーザに提供する。ユーザは、経路の情報も参考に、検索結果の各部分グラフの中から、自分が検索したかったものを特定する。この意味では、経路の情報が第一義的であり、ホップ数に基づく順位付けは参考的な情報である。
【００５６】
ユーザは、選択受付部４４に対して、ソート結果に含まれる各部分グラフの中から、自分が検索したかったものではないかと思われる部分グラフを選択してもよい。選択が行われると（Ｓ２４の選択結果がＹｅｓ）、ソート結果提示部４２は選択された部分グラフについての詳細情報を表示し（Ｓ２６）、基準ノードから選択された部分グラフまでの経路情報を、基準経路記憶部３８に登録する（Ｓ２８）。また、Ｓ２８では、その経路情報を検索経路履歴データ１０ｂに対して当該ユーザの新たな履歴経路として追加する。追加する履歴経路は、当該ユーザのＩＤに対応づけられるとともに、新たな履歴経路ＩＤを付与される（図４参照）。また、この時点ではその履歴経路は１回使用（すなわちユーザに所望の部分グラフを指すものとして選択）されただけなので、使用回数１回に応じた経路評価値が登録される。
【００５７】
さて、ここで、ソート結果から部分グラフを選択すると、例えば、類似検索を指示するためのＧＵＩ（グラフィカルユーザインタフェース）が画面表示され、ユーザが類似検索の実行を指示すると、図１３に例示する処理手順が実行される。ユーザは、類似検索の実行ではなく、ソート結果から他の部分グラフを選択してもよく（図７では表示省略）、この場合新たに選択された部分グラフについてＳ２６及びＳ２８の処理が実行される。
【００５８】
また、ユーザは、類似検索に進む代わりに、上限ホップ数又は検索条件（部分グラフ）の少なくとも一方を変更してもよい（Ｓ３２の判定結果がＹｅｓ）。このような変更を行う場合、処理はステップＳ１２に戻り、新たに上限ホップ数や検索条件が指示され、それらに従って検索処理（Ｓ１８）が再び実行される。
【００５９】
ユーザが、検索終了の操作を行うと、Ｓ３２の判定結果がＮｏとなり、一連の検索処理手順が終了する。
【００６０】
次に、図１３を参照して、類似検索の処理手順の例を説明する。類似検索は、新たに指定された基準ノードから、初期検索のＳ５８で登録された基準経路に近い部分グラフを検索する処理である。
【００６１】
図１３の手順では、類似検索の基準ノードの指定を受け付け（Ｓ４０）、更に類似検索における上限ホップ数の指定を受け付ける（Ｓ４２）。なお、上限ホップ数については、ユーザが変更しなければ、初期検索時の値をそのまま用いる。そして、関連ノード抽出部２２が、新たに指定された類似検索の基準ノードから、その上限ホップ数の範囲内にある関連ノード群を抽出し（Ｓ４４）、抽出結果を関連ノード記憶部２４に記憶する。Ｓ４４の処理は、図８と同様の処理手順により行えばよい。関連ノード群が抽出されると、それら関連ノード群が表す検索範囲内で、部分グラフ検索処理部２６が検索処理を実行する（Ｓ４６）。このとき用いる検索条件は、初期検索のときに用いた条件と同じである。検索が完了すると、ソート部３０が、経路類似度基準ソート処理３４を実行することにより、検索結果ごとに、基準ノードからその検索結果までの経路と、基準経路記憶部３８に記憶された基準経路との類似度を計算する（Ｓ４８）。類似度の計算は、例えばGraph edit distance法など、グラフ同士の類似度を計算するための公知の方法を用いればよい。経路類似度基準ソート処理３４では、このようにして求めた類似度の降順（すなわち類似度が高い順）に、検索結果をソートする（Ｓ５０）。そして、そのソート結果をソート結果提示部４２からユーザに提供する（Ｓ５２）。この類似検索におけるソート結果の表示画像でも、検索された各部分グラフに対する基準ノードからの経路の情報を合わせて表示する。
【００６２】
このようにして提供された類似検索処理のソート結果の中から、ユーザは特定の検索結果（部分グラフ）を選択してもよい（Ｓ５４の選択結果がＹｅｓ）。この場合、選択された部分グラフの詳細情報が検索結果提示ＵＩ４０に表示され（Ｓ５６）、基準ノードから選択された部分グラフまでの経路情報が基準経路記憶部３８に記憶される（Ｓ５８）。また、この選択により、その経路（既に初期検索の際に検索経路履歴データ１０ｂに登録済み）の使用回数が１回増えたので、Ｓ５８では、選択受付部４４は、検索経路履歴データ１０ｂ内のその経路の経路評価値をその使用回数の増加に応じて更新する。
【００６３】
さて、ここで、更なる類似検索を指示する（Ｓ６０の判定結果がＹｅｓ）ことにより、このように新たに記憶された経路情報を基準経路として、Ｓ４０に戻って新たな類似検索を実行するようにしてもよい。もちろんユーザは、新たな類似検索の実行ではなく、ソート結果から他の部分グラフを選択してもよく（図１３では表示省略）、この場合新たに選択された部分グラフについてＳ５６及びＳ５８の処理が実行される。
【００６４】
また、ユーザは、Ｓ５８で新たに記憶した基準経路に基づく新たな類似検索に進む代わりに、上限ホップ数を変更してもよい（Ｓ６２の判定結果がＹｅｓ）。このような変更を行う場合、処理はステップＳ４２に戻り、新たに上限ホップ数が指示され、それらに従って検索処理（Ｓ４６）及びソート処理（Ｓ４８及びＳ５０）が再び実行される。なお、このときのＳ４８では、Ｓ５８で新たに記憶した基準経路ではなく、初期検索において記憶した基準経路を用いる。
【００６５】
例えば、図２のグラフに対し、図１０の部分グラフを検索条件とした初期検索を実行し、図１１に示す検索結果の部分グラフ１１０及び１１２のうち、部分グラフ１１２がＳ２４で選択され、類似検索に進んだ場合を考える。この場合、基準経路は、”Workspace-a, participated, User-c, created”（下線は、逆方向のリンクであることを示す）である。ノードを個別のものから種類別へと一般化すると、基準経路は”Workspace, participated, User, created”である。この状況で、ノード１０６が類似検索の基準ノードとして指定され、上限ホップ数が「３」に指定された場合、Ｓ４６の検索処理では、図１４に例示する部分グラフ１２０及び１２２が検索結果として求められる。ここで、基準ノード１０６から検索結果の各部分グラフ１２０及び１２２までの各経路と、基準経路”Workspace, participated, User, created”とを比較すると、部分グラフ１２０までの経路の方が基準経路に近い。したがって、類似度は部分グラフ１２０の方が高くなり、ソート結果は部分グラフ１２０，１２２の順となる。
【００６６】
なお、以上の例では、類似度を求めるにあたり基準ノードから検索結果の部分グラフまでの経路にはその部分グラフ自体は含めなかったが、部分グラフ自体を経路に含めて類似度を求めてもよい。
【００６７】
以上に説明したように、類似検索では、基準ノードを新たに指定して、その新たな基準ノードから見て、初期検索でユーザが特定した基準経路と類似の経路を持つ部分グラフが検索される。したがって、類似検索では、いわば、新たな視点（基準ノード）から、前の検索の結果である基準経路と類似した検索結果が求められることとなる。
【００６８】
以上の例では、検索範囲を基準ノードから上限ホップ数以内の検索範囲内から検索条件に合致する部分グラフを検索した。この場合、部分グラフ全体が検索範囲内に含まれていないと、その部分グラフは検索されない。例えば図１５に示すグラフ１００において、基準ノードがノード１０２と、上限ホップ数が「３」と、検索条件として部分グラフ１３０が指定された場合、グラフ１００中の部分グラフ１３５は検索条件に適合するが、一部のノードが検索範囲（破線で示した矩形）から外れるため、検索されないことになる。
【００６９】
これに対し、検索条件に適合する部分グラフの一部のノードでも検索範囲内に含まれていたら、その部分グラフを検索するようにしてもよい。このためには、例えば、指定された上限ホップ数に対して検索条件の部分グラフの最大ホップ数（すなわち部分グラフ中のノード同士の間のホップ数の中の最大値）を上限ホップ数に加算し、基準ノードからその加算結果のホップ数の範囲を検索範囲とすればよい。
【００７０】
例えば、図１５の例では、検索条件の部分グラフ１３０の最大ホップ数は「２」なので、指定された上限ホップ数「３」にこの最大ホップ数を加えた結果「５」が、拡張した検索範囲の広さを示すものとなる。図１６に示すように、検索条件１３０を満たす部分グラフ１３５は、このように拡張された検索範囲１５０内に完全に含まれているので、検索されることとなる。このような検索範囲の拡張は、初期検索、類似検索及び履歴利用検索のいずれに適用してもよい。
【００７１】
次に、履歴利用検索の手順の一例を、図１７を参照して説明する。この実施形態の検索装置の基本ＵＩ画面にてユーザが履歴利用検索を選択すると、図１７の手順が実行される。
【００７２】
この手順では、まず履歴利用検索ＵＩ５０が、着目ノード候補の検索条件を入力するためのＵＩ画面を表示し、ユーザから検索条件の入力を受け付ける。検索条件が入力されると、着目ノード候補検索部５２がグラフデータ１０ａから、その検索条件を満たすノードを検索する（Ｓ１００）。この検索により着目ノードの候補が求められる。履歴利用検索ＵＩ５０は、求められた候補を一覧表示し、その中から着目ノードとするものをユーザに選択させる（Ｓ１０２）。ユーザが選択した着目ノードは、履歴利用検索処理部５４に通知される。
【００７３】
履歴利用検索処理部５４は、検索経路履歴データ１０ｂから当該ユーザのユーザＩＤに対応する履歴経路データ群を抽出し、抽出した当該ユーザの履歴経路データの中にＳ１０６以降の処理をまだ適用していないものがあるかどうかを判定する（Ｓ１０４）。このような未処理の履歴経路が存在する場合は、その中から１つを選択する（Ｓ１０６）。そして、着目ノードを端点とするグラフ上の経路であってＳ１０６で選択した履歴経路に合致する経路、を探索する（Ｓ１０８）。図４に示したノードを含まない履歴経路データを用いる場合、Ｓ１０８では、例えば、まず着目ノードに接続されたリンクの中から、選択した履歴経路中の最初のリンクに合致するものを探す。例えば、図４の履歴経路ＩＤ“ａ１”の履歴経路データが選択された場合、着目ノードに接続されたリンクの中からまず“participated”という種類のリンクを探す。そのようなリンクが見つかれば、そのリンクのリンク先のノードに接続されたリンクの中から、その履歴経路の２番目のリンクに合致するものを探す。このような探索を繰り返すことで、着目ノードを端点とする、履歴経路に合致する経路が求められる。以上は履歴経路と順方向に合致する経路を見つける例であるが、逆方向に合致する経路を、同様の方法において、すなわち履歴経路データを構成するリンクを末尾から順に適用していくことで、求めてもよい。合致する経路が見つからない場合もあるし、複数見つかる場合もある。
【００７４】
このような探索の結果、Ｓ１０６で選択した履歴経路に合致する経路が見つかった場合（Ｓ１１０の判定結果がＹｅｓ）、履歴利用検索処理部５４は、見つかった経路（着目ノードから見たその経路の反対側の端点のノードも含む）を、その履歴経路のＩＤと対応づけて記憶する（Ｓ１１２）。そして、Ｓ１０４に戻って当該ユーザの履歴経路に未処理のものがないかを調べ、あれば再びＳ１０６以降の処理を行う。また、Ｓ１１０で合致する経路がないと判定された場合は、Ｓ１１２はスキップしてＳ１０４に戻る。
【００７５】
以上の処理を検索経路履歴データ１０ｂに含まれる当該ユーザのすべての履歴経路について繰り返す（Ｓ１０４）。そして、当該ユーザのすべての履歴経路について処理を完了した場合（Ｓ１０４の判定結果がＮｏ）、それまでの処理で求めて記憶した各経路（及びその経路を求める際に用いた履歴経路データのＩＤ）の情報が履歴利用検索ソート処理３５に渡される。
【００７６】
履歴利用検索ソート処理３５は、受け取った検索結果の各経路について、その経路を求める際に用いた履歴経路データのＩＤを用いることで、検索経路履歴データ１０ｂからその履歴経路データの経路評価値を取得する。そして、それら各経路を、経路評価値の順にソートする（Ｓ１１４）。この例は、検索結果のスコアとして、経路評価値そのものを用いる例である。ソート結果はソート結果記憶部３６に記憶される。そして、そのソート結果をソート結果提示部４２からユーザに提供する（Ｓ１１６）。ソート結果提示部４２は、個々の検索結果について、着目ノードからその経路の反対側の端点ノードまでのリンクとノードとの並びを、グラフとして表示する。この表示において、着目ノードの反対側の端点ノードは、他のノードと区別がつきやすいよう強調表示してもよい。また、着目ノードについても、他のノードと（また反対側の端点ノードとも）区別が付きやすいよう強調表示してもよい。
【００７７】
例えば、あるユーザについて図１８の上段に例示するリンク”participated”と逆方向の”created”の並びからなる履歴経路データが存在する場合において、そのユーザが図２のグラフのノード１０６（“Workplace-b”）を着目ノードとして履歴利用検索の実行を指示した場合、図１８の下段に示す経路が求められ、表示されることになる。この表示では、着目ノード１０６と反対側の端点ノード１０７とが、それぞれ違う形態で強調表示されている。この反対側の端点ノードは、着目ノードに対し、ユーザの過去の検索のパターンに沿って求められるノードであり、そのユーザの思考パターンから見て何らかの価値がある可能性がある。なお、このように着目ノード１０６から端点ノード１０７までの経路を表示するだけでなく、端点ノード１０７の近傍（例えば端点ノード１０７から予め定められたホップ数の範囲）のリンク及びノードからなる部分グラフも合わせて表示するようにしてもよい。
【００７８】
このようにして提供されたソート結果の中から、ユーザは選択受付部４４を用いて特定の経路（あるいはその経路の端点ノード）を選択してもよい（Ｓ１１８）。この場合、選択された経路（及び端点ノード）の詳細情報が検索結果提示ＵＩ４０に表示される（Ｓ１２０）。この選択により、その選択された経路を求める際に用いた履歴経路の使用回数が１回増えたので、選択受付部４４は、検索経路履歴データ１０ｂ内のその履歴経路の経路評価値をその使用回数の増加に応じて更新する（Ｓ１２２）。ユーザは、その選択した経路で満足すれば、検索結果提示ＵＩ４０に対して検索終了の旨を入力し、ソート結果中の別の経路を見たければその旨の指示を入力する。ユーザが別の経路を見る旨を指示した場合（Ｓ１２４の判定結果がＹｅｓ）、Ｓ１１６に戻る。終了を指示した場合は、処理を終了する。
【００７９】
以上では、図４に示すリンクのみの履歴経路データを用いる場合を説明したが、図６に例示したノードも含む履歴経路データを用いる場合にも、同様の処理を適用可能である。すなわち、ノードも含む履歴経路データを用いる場合には、Ｓ１０８で履歴経路に合致する経路を求める際に、リンクが合致するだけでなく、ノードの種類も合致する経路を求めればよい。例えば、図６の履歴経路ＩＤ“ａ１”の履歴経路の場合、途中のノード“User-c”は“User”（ユーザ）という種類に該当するので、例えば、着目ノードにリンク“participated”が接続し、そのリンクに“User”の種類のノードが接続し、そのノードに逆方向のリンク“created”が接続する経路が検索される。
【００８０】
以上、履歴利用検索の手順の一例を説明した。上述した初期検索では、ユーザは、基準ノードと検索条件（部分グラフ）を指定する必要があった。これに対し、この履歴利用検索では、着目ノードを指定するのみで、その着目ノードから見て、過去によく使用した（すなわち経路評価値が高い）履歴経路に合致する経路の先の位置にある端点ノードが提示されることになる。この端点ノードは、ユーザが過去によく使用した履歴経路から求められるので、ユーザが潜在的に探したいと思っているものである可能性が高いといえる。
【００８１】
また、以上の例において、図４に例示したリンクのみの履歴経路データを用いる場合には、経路上のノードの種類が一致しない経路も検索されるので、ユーザが過去に検索に用いた経路と類似した経路が幅広く求められる。
【００８２】
次に、履歴利用検索の手順の別の例を、図１９を参照して説明する。図１７の手順では、履歴経路とすべてのリンクが一致する経路を求めるものであったのに対し、図１９の手順では、履歴経路と類似する経路を求める。
【００８３】
この手順では、まず、図１７の手順と同様着目ノードの候補を検索し（Ｓ１４０）、それら候補の中からユーザに着目ノードを選択させる（Ｓ１４２）。また、履歴利用検索ＵＩ５１は、ユーザから上限ホップ数の指定を受け付け（Ｓ１４４）、指定された基準ノードから指定された上限ホップ数以内で到達できるノード群を、関連ノード群として抽出する（Ｓ１４６）。Ｓ１４６の処理内容は、図８に示したものと同様でよい。この処理により、図９に示したものと同様に、着目ノードから各関連ノードまでの経路の情報が、経路のホップ数（リンク数）の少ない順に並べたデータが得られる。上限ホップ数の指定は、この後の処理での検索範囲を限定するためのものである。検索範囲を限定しなくてよい場合は、Ｓ１４４及びＳ１４６の処理は不要である。
【００８４】
履歴利用検索処理部５４は、検索経路履歴データ１０ｂから当該ユーザのユーザＩＤに対応する履歴経路データ群を抽出し、抽出した当該ユーザの履歴経路データの中にＳ１０６以降の処理をまだ適用していないものがあるかどうかを判定する（Ｓ１４８）。このような未処理の履歴経路が存在する場合は、その中から１つを選択する（Ｓ１５０）。次に、各関連ノードについて、着目ノードから当該関連ノードまでの経路とＳ１５０で選択した履歴経路との類似度を計算する（Ｓ１５２）。類似度の計算は、例えばGraph edit distance法など、グラフ同士の類似度を計算するための公知の方法を用いればよい。類似度は、リンクのみの履歴経路データを用いる場合にはリンクのみの並びについて、ノードも含む履歴経路データを用いる場合はリンクのノードの並びについて、計算すればよい。なお、Ｓ１５２では、順方向の履歴経路と逆方向の履歴経路の両方についてそれぞれ類似度を求めてもよい。そして、関連ノードごとに、着目ノードから当該関連ノードまでの経路と履歴経路との類似度と、当該履歴経路の経路評価値と、から検索スコアを計算する（Ｓ１５４）。この検索スコアは、類似度が高いほど高くなり、経路評価値が高いほど高くなる計算規則を用いて求めればよい。求められた検索スコアは、着目ノードから関連ノードまでの経路の情報と、Ｓ１５０で選択した履歴経路のＩＤと、に対応づけて記憶される。
【００８５】
以上のＳ１４８からＳ１５４の処理を検索経路履歴データ１０ｂに含まれる当該ユーザのすべての履歴経路について繰り返す（Ｓ１４８）。そして、当該ユーザのすべての履歴経路について処理を完了した場合（Ｓ１４８の判定結果がＮｏ）、それまでの処理で求めて記憶した各経路（及びその経路を求める際に用いた履歴経路データのＩＤ）と検索スコアの情報が履歴利用検索ソート処理３５に渡される。
【００８６】
履歴利用検索ソート処理３５は、受け取った検索結果の各経路を、検索スコアの順にソートする（Ｓ１５６）。ソート結果はソート結果記憶部３６に記憶される。そして、そのソート結果をソート結果提示部４２からユーザに提供する（Ｓ１５８）。このようにして提供されたソート結果の中から、ユーザは選択受付部４４を用いて特定の経路（あるいはその経路の端点ノード）を選択してもよい（Ｓ１６０）。この場合、選択された経路（及び端点ノード）の詳細情報が検索結果提示ＵＩ４０に表示される（Ｓ１６２）。この選択により、その選択された経路を求める際に用いた履歴経路の使用回数が１回増えたので、選択受付部４４は、検索経路履歴データ１０ｂ内のその履歴経路の経路評価値をその使用回数の増加に応じて更新する（Ｓ１６４）。ユーザは、その選択した経路で満足すれば、検索結果提示ＵＩ４０に対して検索終了の旨を入力し、ソート結果中の別の経路を見たければその旨の指示を入力する。ユーザが別の経路を見る旨を指示した場合（Ｓ１６６の判定結果がＹｅｓ）、Ｓ１５８に戻る。終了を指示した場合は、処理を終了する。
【００８７】
図１９の手順では、履歴経路に厳密には一致しない経路も検索される。
【００８８】
次に、履歴利用検索の手順の別の例を、図２０及び図２１を参照して説明する。この例では、図２０に示すように、履歴経路が登録された時の初期検索にて用いられた基準ノード及び検索条件（部分グラフ）の情報が履歴経路データに含まれており、これら基準ノード及び検索条件を用いて検索範囲を絞り込む。
【００８９】
この例の手順の例を図２１に示す。この手順のうち、Ｓ１４０からＳ１５０までは、図１９の手順と同様である。Ｓ１５０で未処理の履歴経路を１つ選択すると、履歴利用検索処理部５４は、その履歴経路の両端（すなわち基準ノードと検索条件の部分グラフ）のどちらかが、着目ノードに適合するか否かを判定する（Ｓ１７０）。基準ノードの種類が着目ノードの種類に合致する場合、基準ノードが着目ノードに適合すると判定する。また、検索条件の部分グラフの中のいずれかのノードの種類が着目ノードの種類に合致し、且つグラフ上の着目ノードの近傍の部分グラフが検索条件の部分グラフと合致（リンクのみ合致でもよいし、リンクもノードも合致することを要件としてもよい）する場合、検索条件の部分グラフが着目ノードに適合すると判定する。この判定で、履歴経路の基準ノード及び部分グラフのどちらも、履歴利用検索の着目ノードに適合しない場合、その履歴経路は不採用として、Ｓ１４８に戻る。すなわち、この例では、検索に使用する履歴経路を、着目ノードを端点として持つ履歴経路のみに絞り込んでいる。
【００９０】
Ｓ１７０の判定結果がＹｅｓの場合、履歴利用検索処理部５４は、履歴経路の両端のうち、Ｓ１７０で着目ノードと適合した端部と反対側の端部の基準ノード又は部分グラフを、Ｓ１４６で求めた関連ノード群が構成する検索範囲の中から検索する（Ｓ１７２）。検索が完了すると、検索結果ごとに、着目ノードからその検索結果までの経路と、Ｓ１５０で選択した履歴経路との類似度を計算する（Ｓ１７４）。Ｓ１７４では、着目ノードが履歴経路の基準ノードに適合した場合は、順方向の履歴経路との類似度を計算する。また、着目ノードが検索条件の部分グラフの中のノードに合致した場合は、着目ノードから検索ケンカまでの経路のうち、着目ノードの近傍のその検索条件の部分グラフに合致する部分を除いた経路と、逆方向の履歴経路との類似度を計算する。そして、検索結果ごとに、着目ノードから当該検索結果までの経路と履歴経路との類似度と、当該履歴経路の経路評価値と、から検索スコアを計算する（Ｓ１７６）。当該ユーザの履歴経路のすべてについて、Ｓ１４８からＳ１７６の処理を繰り返す。そして、当該ユーザのすべての履歴経路について処理を完了した場合（Ｓ１４８の判定結果がＮｏ）、図１９のＳ１５６に進む。Ｓ１５６以降の処理は、上述の例と同様である。
【００９１】
次に、履歴経路の拡張について説明する。これまで説明してきた例では、ユーザが初期検索において指定した基準ノードと、検索条件に合致する部分グラフとを結ぶグラフ上の経路が履歴経路として記録された。ところが、初期検索で検索された経路とその周辺のリンクやノードを見たユーザが、その経路に周辺のリンクを付け加えて拡張した方が、後の履歴検索や類似検索において便利であると考える場合もある。そのような場合に対応するのが履歴経路の拡張機能である。
【００９２】
この経路拡張について、図２２を参照して説明する。図２２の最上段に示すグラフ１００に対する初期検索で、ユーザがノード“Workplace-a”１０２を基準ノードに指定し、図１０に示した“Document, commented, Comment”という部分グラフを検索条件に指定したとする。そして、符号１０３で示す楕円で囲まれた部分グラフが検索され、ユーザから選択されたとする。この場合、経路を拡張しなければ、基準ノード１０２から検索結果の部分グラフの最初のノード“Document-c”までの経路“participated, created”１７０が履歴経路として記憶されることになる。これに対し、ユーザが例えば基準ノード１０２に接続されたリンク“held”を履歴経路に追加する拡張を指示すると、経路“held, participated, created”１７２が履歴経路として検索経路履歴データ１０ｂ内に登録されることとなる。この場合、拡張しない経路１７０に代えて拡張した経路１７２を登録してもよいし、拡張しない経路１７０に加えて拡張した経路１７２を登録してもよい。また、経路の拡張は、基準ノードに接続するリンクに限らず、履歴経路において基準ノードの反対側の端点に接続するリンクを拡張できるようにしてもよい。また、拡張は、１ホップに限られるものではなく、複数ホップのリンクを追加する拡張ができるようにしてもよい。
【００９３】
この経路拡張機能は、例えば選択受付部４４が初期検索、類似検索、又は履歴検索の検索結果の中からユーザが所望のものを選択した際に実行すればよい。例えば、ユーザが検索結果から所望のものを選択した場合、選択受付部４４は、選択された検索結果に対応する経路（基準ノード又は着目ノードから選択された部分グラフまでの経路）を表示すると共に、履歴経路の拡張の指示を受け付けるＵＩを表示する。このＵＩに対して拡張を指示すると、例えばその表示した経路の両端のノードから、あらかじめ設定したホップ数の範囲のリンク及びノードを表示し、それら表示されたリンク（又はノード）の中から、履歴経路に追加すべきリンク（又はノード）をユーザに指定させる。そして、指定されたリンクを追加して拡張した履歴経路を検索経路履歴データ１０ｂに追加する。
【００９４】
また、このように追加したいリンクをユーザに指定させる代わりに、拡張するホップ数をユーザに指定させ、そのホップ数分のリンクを選択受付部４４がグラフから抽出し、履歴経路に追加するようにしてもよい。指定されたホップ数分のリンクの追加は、最初の履歴経路の両端のノードに対してそれぞれ行ってもよいし、それら両端のノードのうちユーザが指定した片方のみに対して行ってもよい。また、履歴経路の各端部のノードから延びるホップ数分のリンクの組合せが複数ある場合は、それら複数の組合せのそれぞれについて履歴経路の拡張を行ってもよい。
【００９５】
例えば基準ノードから２ホップのリンクを追加する設定の場合、基準ノードに接続するリンクと、基準ノードからみてそのリンクの反対側のノードに接続するリンクとを履歴経路に追加する。ここで、基準ノードからみて２ホップのリンクの組合せが複数存在する場合は、組合せごとに拡張した履歴経路を作成し、登録してもよい。
【００９６】
このようにして拡張した履歴経路を検索経路履歴データ１０ｂに追加しておけば、後の類似検索や履歴検索において、拡張された履歴経路に合致又は類似する経路も検索されることとなる。
【００９７】
以上に例示した検索装置は、例えば、汎用のコンピュータに上述の各機能モジュールの処理を表すプログラムを実行させることにより実現してもよい。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、ＨＤＤ（ハードディスクドライブ）を制御するＨＤＤコントローラ、各種Ｉ／Ｏ（入出力）インタフェース、ローカル・エリア・ネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバスを介して接続された回路構成を有する。また、そのバスに対し、例えばＩ／Ｏインタフェース経由で、ＣＤやＤＶＤなどの可搬型ディスク記録媒体に対する読み取り及び／又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び／又は書き込みのためのメモリリーダライタ、などが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがＣＤやＤＶＤ等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ハードディスクドライブ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。
【符号の説明】
【００９８】
１０  データベース、１２  基準ノード指定受付部、１４  ホップ数指定受付部、１６  検索条件指定受付部、１８  初期検索ＵＩ、２０  類似検索ＵＩ、２２  関連ノード抽出部、２４  関連ノード記憶部、２６  部分検索処理部、２８  検索結果記憶部、３０  ソート部、３２  ホップ数基準ソート処理、３４  経路類似度基準ソート処理、３５  履歴利用検索ソート処理、３６  ソート結果記憶部、３８  基準経路記憶部、４０  検索結果提示ＵＩ、４２  ソート結果提示部、４４  選択受付部、５０  履歴利用検索ＵＩ、５２  着目ノード候補検索部、５４  履歴利用検索処理部。
【図１】
0005747749.tif 000002
【図２】
0005747749.tif 000003
【図３】
0005747749.tif 000004
【図４】
0005747749.tif 000005
【図５】
0005747749.tif 000006
【図６】
0005747749.tif 000007
【図７】
0005747749.tif 000008
【図８】
0005747749.tif 000009
【図９】
0005747749.tif 000010
【図１０】
0005747749.tif 000011
【図１１】
0005747749.tif 000012
【図１２】
0005747749.tif 000013
【図１３】
0005747749.tif 000014
【図１４】
0005747749.tif 000015
【図１５】
0005747749.tif 000016
【図１６】
0005747749.tif 000017
【図１７】
0005747749.tif 000018
【図１８】
0005747749.tif 000019
【図１９】
0005747749.tif 000020
【図２０】
0005747749.tif 000021
【図２１】
0005747749.tif 000022
【図２２】
0005747749.tif 000023