(57)【特許請求の範囲】
【請求項１】
データ要素をノードとしデータ要素同士の関係をリンクとするグラフのデータを記憶するグラフ記憶手段と、
前記グラフ上のノードの中から基点ノードの指定を受け付ける基点ノード指定受付手段と、
着目ノードに対して１つのリンクを介して接続された隣接ノードであって、当該着目ノード又は当該隣接ノードのうちの少なくとも一方が人を示す第１の属性を有するという検索条件を満たす隣接ノードを検索する検索手段であって、前記基点ノードを着目ノードとして前記検索条件を満たす隣接ノードを検索すると共に、前回の検索により求められた前記検索条件を満たす隣接ノードを次の着目ノードとして前記検索条件を満たす隣接ノードを検索する処理を繰り返し、前記繰り返しにより検索された隣接ノード群の連鎖を出力する検索手段と、
を備え、
前記検索手段は、着目ノードが前記第１の属性を有する場合は、隣接ノードのうち前記第１の属性を有する隣接ノード又は人間関係を媒介する事物を示す第２の属性を有する隣接ノードのみの連鎖を出力する、検索装置。
【請求項２】
前記検索条件は、当該着目ノード又は当該隣接ノードのうちの少なくとも一方が前記第１の属性を有すること、且つ当該着目ノードと当該隣接ノードとの間のリンクがあらかじめ定められた１以上の種類のいずれかに該当すること、であることを特徴とする請求項１に記載の検索装置。
【請求項３】
前記基点ノード指定受付手段は、第１の基点ノードと第２の基点ノードの指定を受け付け、
前記検索手段は、前記第１の基点ノードから前記第２の基点ノードまで前記検索条件を満たす隣接ノード群の連鎖を求める、
ことを特徴とする請求項１〜２のいずれか１項に記載の検索装置。
【請求項４】
前記検索手段は、前記検索条件を満たす隣接ノード群の連鎖が複数求められた場合に、各連鎖を、それぞれ当該連鎖に含まれるリンクの数が少ない順に並べて提示する、ことを特徴とする請求項１〜３のいずれか１項に記載の検索装置。
【請求項５】
コンピュータを、
データ要素をノードとしデータ要素同士の関係をリンクとするグラフのデータを記憶するグラフ記憶手段、
前記グラフ上のノードの中から基点ノードの指定を受け付ける基点ノード指定受付手段、
着目ノードに対して１つのリンクを介して接続された隣接ノードであって、当該着目ノード又は当該隣接ノードのうちの少なくとも一方が人を示す第１の属性を有するという検索条件を満たす隣接ノードを検索する検索手段であって、前記基点ノードを着目ノードとして前記検索条件を満たす隣接ノードを検索すると共に、前回の検索により求められた前記検索条件を満たす隣接ノードを次の着目ノードとして前記検索条件を満たす隣接ノードを検索する処理を繰り返し、前記繰り返しにより検索された隣接ノード群の連鎖を出力する検索手段、
として機能させるためのプログラムであって、
前記検索手段は、着目ノードが前記第１の属性を有する場合は、隣接ノードのうち前記第１の属性を有する隣接ノード又は人間関係を媒介する事物を示す第２の属性を有する隣接ノードのみの連鎖を出力する、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置及びプログラムに関する。
【背景技術】
【０００２】
特許文献１には、所望の文書の他に、その文書に関連する文書を検索する際、本当に必要な関連文書を絞込検索できるようにするための装置が示されている。この装置は、ディスプレイに表示されている管理体系内のノードの中から文書を登録するノードを指定するノード指定処理部と、登録対象の文書の属性情報を指定するとともに、その文書に関連する関連文書の属性情報と関連の意義を示す関連意義情報を指定する情報指定処理部とを備え、そのノード指定処理部により指定されたノードに登録対象の文書の文書ファイルを登録するとともに、その情報指定処理部により指定された登録対象の文書の属性情報と関連文書の属性情報及び関連意義情報を登録する。また、特許文献１には、検索キーとして関連文書の属性情報が与えられると、その属性情報に合致する関連文書を検索することが示されている。また、特許文献１には、所望の文書に関連する関連文書を再帰的に検索することが記載されている。また特許文献１には、検索キーとして関連意義情報が与えられると、検索した関連文書の中から、その関連意義情報に合致する関連文書の絞り込み検索を実施することが開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−２０９４３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、データ要素をノードとしデータ要素同士の関係をリンクとするグラフ状のデータ構造をなすデータベースにおいて、ユーザが指定した基点ノードから、特定の属性を有するノードを介した関係により連鎖する経路を求めることができるようにすることを目的とする。
【課題を解決するための手段】
【０００５】
請求項１に係る発明は、データ要素をノードとしデータ要素同士の関係をリンクとするグラフのデータを記憶するグラフ記憶手段と、前記グラフ上のノードの中から基点ノードの指定を受け付ける基点ノード指定受付手段と、着目ノードに対して１つのリンクを介して接続された隣接ノードであって、当該着目ノード又は当該隣接ノードのうちの少なくとも一方が人を示す第１の属性を有するという検索条件を満たす隣接ノードを検索する検索手段であって、前記基点ノードを着目ノードとして前記検索条件を満たす隣接ノードを検索すると共に、前回の検索により求められた前記検索条件を満たす隣接ノードを次の着目ノードとして前記検索条件を満たす隣接ノードを検索する処理を繰り返し、前記繰り返しにより検索された隣接ノード群の連鎖を出力する検索手段と、を備え、前記検索手段は、着目ノードが前記第１の属性を有する場合は、隣接ノードのうち前記第１の属性を有する隣接ノード又は人間関係を媒介する事物を示す第２の属性を有する隣接ノードのみの連鎖を出力する、検索装置である。
【０００６】
請求項２に係る発明は、前記検索条件は、当該着目ノード又は当該隣接ノードのうちの少なくとも一方が前記第１の属性を有すること、且つ当該着目ノードと当該隣接ノードとの間のリンクがあらかじめ定められた１以上の種類のいずれかに該当すること、であることを特徴とする請求項１に記載の検索装置である。
【０００７】
請求項３に係る発明は、前記基点ノード指定受付手段は、第１の基点ノードと第２の基点ノードの指定を受け付け、前記検索手段は、前記第１の基点ノードから前記第２の基点ノードまで前記検索条件を満たす隣接ノード群の連鎖を求める、ことを特徴とする請求項１〜２のいずれか１項に記載の検索装置である。
【０００８】
請求項４に係る発明は、前記検索手段は、前記検索条件を満たす隣接ノード群の連鎖が複数求められた場合に、各連鎖を、それぞれ当該連鎖に含まれるリンクの数が少ない順に並べて提示する、ことを特徴とする請求項１〜３のいずれか１項に記載の検索装置である。
【０００９】
請求項５に係る発明は、コンピュータを、データ要素をノードとしデータ要素同士の関係をリンクとするグラフのデータを記憶するグラフ記憶手段、前記グラフ上のノードの中から基点ノードの指定を受け付ける基点ノード指定受付手段、着目ノードに対して１つのリンクを介して接続された隣接ノードであって、当該着目ノード又は当該隣接ノードのうちの少なくとも一方が人を示す第１の属性を有するという検索条件を満たす隣接ノードを検索する検索手段であって、前記基点ノードを着目ノードとして前記検索条件を満たす隣接ノードを検索すると共に、前回の検索により求められた前記検索条件を満たす隣接ノードを次の着目ノードとして前記検索条件を満たす隣接ノードを検索する処理を繰り返し、前記繰り返しにより検索された隣接ノード群の連鎖を出力する検索手段、として機能させるためのプログラムであって、前記検索手段は、着目ノードが前記第１の属性を有する場合は、隣接ノードのうち前記第１の属性を有する隣接ノード又は人間関係を媒介する事物を示す第２の属性を有する隣接ノードのみの連鎖を出力する、プログラムである。
【発明の効果】
【００１０】
請求項１又は５に係る発明によれば、ユーザが指定した基点ノードから、特定の属性を有するノードを介した関係により連鎖する経路を求めることができる。
【００１１】
請求項２に係る発明によれば、限られた種類のリンクを介して連鎖する経路のみを検索することができる。
【００１２】
請求項３に係る発明によれば、第１の基点ノードから第２の基点ノードまでの経路を求めることができる。
【００１３】
請求項４に係る発明によれば、基点ノードに対して関係が深い（リンク数が少ない）連鎖から順に並べて提示することができる。
【図面の簡単な説明】
【００１４】
【図１Ａ】着目ノードに対して特定属性を持つノードが接続（隣接）している部分グラフを示す図である。
【図１Ｂ】着目ノードに対して特定属性を持つノードが接続（隣接）している部分グラフを示す図である。
【図２】着目ノードから特定属性を持つ隣接ノードが２つ連鎖した部分グラフを示す図である。
【図３】始点ノードから終点ノードまでの、特定属性（「人」）を持つノードを介した関係の連鎖の経路の例を示す図である。
【図４】実施の形態の検索装置の一例の機能ブロック図である。
【図５】データベースのデータ内容の一例を示す図である。
【図６】検索処理部の全体的な処理手順の一例を示すフローチャートである。
【図７】検索処理部が行う隣接ノード処理の手順の一例を示すフローチャートである。
【図８】検索処理部が求める経路情報の例を示す図である。
【図９】ソート部の処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１５】
データ要素同士の関係が構成するグラフ構造を記述する方式が知られている。例えば、事物（リソース。具体物も抽象概念を含む）同士の関係を主語、述語、目的語の組（「トリプル」と呼ばれる）で記述するＲＤＦ（Resource Description Framework）はその一例である。ＲＤＦでは、複数のトリプルにより、主語又は目的語である事物をノードとし、述語をリンク（エッジ）とするグラフが表される。また、ＲＤＦで記述されたデータを検索するコンピュータ言語として、例えばＳＰＡＲＱＬ（SPARQL Protocol and RDF Query Language）が知られている。
【００１６】
以下に示す実施の形態では、様々な事物同士の関係をＲＤＦに従って記述したデータからなるデータベースを検索する例を示す。なお、事物間の関係を表す方法はＲＤＦに限られるわけではないので、以下に示す実施の形態はＲＤＦ以外の方式でそのような関係を表すデータベースにも適用し得る。
【００１７】
この実施の形態の手法を理解しやすくするために、次のような事例を考える。
【００１８】
ユーザＡがデータベースを検索し、ある電子文書Ｘを見つけたとする。ところが、ユーザＡにはその電子文書Ｘのアクセス権がなく、中身を読むことができない。このような状況において、ユーザＡの知り合いの中にその電子文書Ｘへのアクセス権を持つ人がいれば、ユーザＡがその知り合いに頼んでその電子文書Ｘの内容を教えてもらうことも考えられる。また、ユーザＡの直接の知り合いの人物Ｂの同僚である人物Ｃの同僚である人物Ｄがその文書へのアクセス権を持っている場合には、ユーザＡは、人物Ｂの伝手により人物Ｃに接触し、更に人物Ｃの伝手により人物Ｄに接触することで、人物Ｄに電子文書Ｘの内容を教えてもらうなどの対処をとり得る。
【００１９】
また、ユーザＡの直接の知り合いの人物Ｂが参加していたＹ会議に参加していた人物Ｃがその電子文書Ｘへのアクセス権を持っている場合、人物Ｂと人物Ｃが直接の知り合いや同僚の関係にあるかは不明であるが、人物Ｂは同じ会議Ｘに参加していたという関係から人物Ｃに接触できる可能性がある。これにより、ユーザＡは、人物Ｂの伝手により人物Ｃに接触し、人物Ｃに電子文書Ｘの内容を教えてもらうなどの対処をとり得る。
【００２０】
したがって、人物を含む様々な事物や抽象概念同士の関係をＲＤＦに従って記述したデータベース内で、ユーザＡと電子文書Ｘとの間を繋ぐ、上述のような人物を介する関係の連鎖を見つけることができれば、ユーザＡはその連鎖の経路上の人物の伝手をたどって電子文書Ｘにアクセスできる可能性が出てくる。この経路は、「人である」という属性を持つ事物（例えば人物Ｂ）、又は「人である」という属性を持つ事物に対して関係を持つ事物（例えば人物Ｃが参加したＹ会議）が連鎖した経路である。なお、「Ｃは人である」というデータは、主語「Ｃ」と、述語「（目的語）という属性を有する／（目的語）のクラスのメンバである」と、目的語「人」とからなるトリプルで表現される。
【００２１】
この実施の形態では、事物間の関係の集合からなるグラフ構造を表すデータベースにおいて、そのような特定属性に関与する事物同士の関係の連鎖経路を求める。以下、このための方法の概要を説明する。
【００２２】
例えば、ユーザＡが、電子文書Ｘに関連がある「人」の連鎖を知りたいという場合には、ユーザＡは、検索装置に対して、経路検索の絞り込みの条件として、「人」という属性を有する、という条件を設定する。条件設定の方法としては、例えば、検索装置内に記憶された属性（「人」、「文書」、「会議」、「組織」など）の一覧を提示し、そこから選択させるなどの方法を用いればよい。検索装置が記憶しておく属性は、例えばＲＤＦのvocabularyに属するものなどでもよいし、検索装置内で独自に定義したものでもよい。
【００２３】
ＳＰＡＲＱＬで、例えば、「人」という属性をもったノードを検索する場合には、
Select ?p where { ?prdf:type foaf:Person . }
といった検索式を用いればよい。
【００２４】
ここで「rdf:type」とは、リソースがあるクラスのメンバ（インスタンス）であることを示すプロパティを意味する。また、「rdf:」とはＲＤＦモデル構文の名前空間を表す。この名前空間の具体的な仕様は、Ｗ３Ｃ勧告として，「RDF Vocabulary Description Language 1.0: RDF Schema」にまとめられている(http://www.w3.org/TR/rdf-schema/ 参照)。
【００２５】
同様に、「foaf:Person」とは「人」を表すリソースである。「foaf:Person」という記述は、「FOAF VocabularySpecification 0.9」に準拠したものである(http://xmlns.com/foaf/0.1/ 参照)。
【００２６】
また、ＲＤＦに従って記述されたグラフデータベースにおいて、特定のノード（以下、着目ノードと呼ぶ）を目的語として持つようなノードの検索には、着目ノードが<someUri>として記述できるとき、
Select ?n where { ?n?pred <someUri> }
といった検索式を用いればよい。
【００２７】
上述の検索式を組み合わせた例えば以下のような検索式を用いれば、着目ノードを目的語として持ち、且つ特定属性「人」を有するノード（以下では「subj-n」と表す）が検索されることになる。なお、このノードsubj-nは、着目ノード<someUri>に隣接するノードである。
＜検索式１＞
Select ?subj-n where {
?subj-n ?pred1<someUri> .
?subj-n rdf:typefoaf:Person .
}
この検索式１は、図１Ａに示すようなノードとリンクとからなる部分グラフを表している。図１Ａでは、ノードを楕円で示し、リンクをそれら楕円を結ぶ矢印で示している。すなわち、図１Ａに示す部分グラフは、「Subj-n」というノードが、<someUri>で特定されるリソースを目的語として持ち、且つ「人」という属性を有する(=foaf:Person タイプである)ことを示している。上述の検索式では、リンク（述語）「pred1」を変数としており、これにより「pred1」にはどのようなリンクでもマッチ（適合）することになる（すなわち「subj-n」と<someUri>と間の関係は限定されない）。そして、上記検索式は、ノード「Subj-n」を変数としており、上述のような部分グラフにマッチするノード「Subj-n」を検索結果とすることを示している。
【００２８】
例えば、電子文書ＸがＲＤＦデータベースにおいてリソース<someUri>として記述されているとすると、あるリソース「Subj-n」は、電子文書Ｘとあるプロパティ「pred1」(限定されない。例えば「作成する」)で記述される関係をもち、なおかつ「人」であるという条件を満たすことになる。
【００２９】
また、関係の方向性は一方向に限るものではない。例えば、以下の検索式２を用いれば、着目ノードを主語として持ち、且つ特定属性「人」を有するノード「subj-n」が検索されることになる。
＜検索式２＞
Select ?subj-n where {
<someUri> ?pred1?subj-n .
?subj-n rdf:typefoaf:Person .
}
この検索式２は、図１Ｂに示す部分グラフを表している。例えばリソース<someUri>が電子文書Ｘを表しており、「pred1」が「uploaded」(アップロードされた)という述語である場合には、ノード「subj-n」は、電子文書Ｘをアップロードした人物を示すものとなる。
【００３０】
上述の検索式１及び２のいずれかにより検索された、着目ノード（リソース）<someUri>の隣接ノード「Subj-n」は、着目ノード<someUri>に対して何らかの関係を持つ「人」を表す。
【００３１】
このようにして、上述の検索式１及び２による検索がなされると、次に、検索式１又は２のいずれかを満たすものとして検索された隣接ノード「Subj-n」の各々をそれぞれ次の繰り返し（イタレーション）における着目ノード<someUri>として扱い、同様な検索を繰り返す。このような繰り返しにより、特定属性「人」を持つノードの連鎖が生成される。例えば、図２に、２回の繰り返しにより求められるノードの連鎖「Subj-n -- Subj-n2」を示す。すなわち、図２は、着目ノード<someUri>（例えば目的とする電子文書Ｘ）に対してある関係pred1を持つ人subj-nと、その人subj-nに対してある関係pred2を持つ人subj-n2とからなる連鎖を示している。ここで、関係（述語）pred2は、例えば人物間の関係(たとえば「同僚である」)を表している。
【００３２】
なお上述の検索式１及び２は、着目ノードに隣接する隣接ノードの属性が「人」であることを示すものであるが、隣接ノードの属性が「人」でなくても着目ノードの属性が「人」であれば、連鎖を延ばすようにしてもよい。これは、最初に挙げた事例のうち、同じＹ会議に参加した人物Ｂと人物Ｃとの間を、そのＹ会議を介して連鎖させる例である。すなわち、人物Ｃ（着目ノードとする）がＹ会議（その着目ノードの隣接ノードに該当）に参加していた場合、Ｙ会議は人ではないものの、人物Ｃの次のノードとしてその連鎖の中に組み入れるのである。そして、次にＹ会議を着目ノードとしたときに、その隣接ノードである人物Ｂが、上述の検索式１にマッチすることになり、連鎖に組み入れられることになる。
【００３３】
このように、着目ノードの属性が「人」である場合の隣接ノードを検査するための検索式としては、次の検索式３及び４（それぞれ検索式１及び２の方向性に対応している）を用いればよい。
＜検索式３＞
Select ?subj-n where {
?subj-n ?pred1 <someUri>.
<someUri>rdf:type foaf:Person .
}
＜検索式４＞
Select ?subj-n where {
<someUri> ?pred1?subj-n .
<someUri>rdf:type foaf:Person .
}
【００３４】
このように、（ａ）着目ノード<someUri>に対して、検索式１〜４のいずれかを満たす隣接ノードsubj-nを検索する（ｂ）検索された各隣接ノードを次の繰り返しの着目ノードとする、というステップを繰り返すことで、最初に指定された着目ノードに関して関係のあるノードの連鎖が作成される。
【００３５】
そして、この実施の形態では、このようなノードの連鎖を、それらノード間がどのような関係（リンク）であるかと共に、検索結果として提示する。
【００３６】
図３には、あるグラフデータベースに対してそのような検索を行うことで求められる、人物「あなた」から文書「Ｄｏｃ１」に至る、人を介する事物の連鎖が２つ例示されている。なお、図３では、「人」の属性を持つノードを輪郭が破線の楕円で示しており、「人」の属性を持たないノードを輪郭が実線の楕円で示している。
＜連鎖１＞
人物「あなた」の『同僚』である人物「知り合い１」→人物「知り合い１」の『同僚』である人物「誰かａ」→人物「誰かａ」が『参加』した会議「B会議」→会議「B会議」に『参加』した人物「Ｐｓｎ１」→人物「Ｐｓｎ１」が『作成』した文書「Ｄｏｃ１」
＜連鎖２＞
人物「あなた」が『参加』した会議「A会議」→会議「A会議」に『参加』した人物「誰かｂ」→人物「誰かｂ」が『所属』する組織「組織C」→組織「組織C」に『所属』する人物「Ｐｓｎ１」→人物「Ｐｓｎ１」が『作成』した文書「Ｄｏｃ１」
【００３７】
この実施の形態の検索装置は、検索を指示したユーザ「あなた」に対し、このような連鎖経路の情報を提示する。すなわち、隣接ノード群の連鎖を、各ノード、リンクの情報およびノード間の接続情報の系列として、出力する。図３を例にすると、各ノード、リンクの情報は、各ノードに対応するのが「あなた」と「知り合い」であり、リンクに対応するのが「同僚」である。ノード間の接続情報は、「同僚」という関係によって「あなた」と「知り合い」が結びつけられていることを、矢印によって示されている。
【００３８】
以上、この実施の形態の手法について概説した。次に、この手法を実現した検索装置の構成及び処理手順の例を説明する。
【００３９】
図４に、この実施の形態の検索装置の構成の一例を例示する。
【００４０】
図４の構成において、データベース１０には、データ要素同士の関係が構成するグラフ構造を表すグラフデータが記憶されている。ここでは、データ要素同士の関係をＲＤＦで表現する場合の例を用いて説明するが、この実施の形態の検索手法は、ＲＤＦ以外の方式を用いる場合に適用してもよい。
【００４１】
図５に、データベース１０に記憶されるグラフデータの一例を示す。図５に例示するデータには、主語、述語、目的語の組である「トリプル」が複数含まれている。図５に例示したグラフデータは、図３に示したグラフを表している。ただし、図５に例示するデータ形式はあくまで一例に過ぎず、データ要素間の関係を記述できるデータ形式であれば、図５に例示した形式以外の形式を用いてもよい。
【００４２】
再び図１の説明に戻ると、データベース１０は、後で説明する検索処理部２０等のグラフ検索のための機能が実装されるコンピュータに対して実装されていてもよいし、このコンピュータからインターネット等のネットワークを介して接続された別のコンピュータに実装されていてもよい。
【００４３】
基点ノード指定受付部１２は、検索のための指定項目の１つとして、ユーザから基点ノードの指定を受け付ける。基点ノードは、ユーザが検索で求めたい連鎖経路の端点のノードである。図３の例では、経路の始点ノード「あなた」と終点ノード「Ｄｏｃ１」が基点ノードに該当する。なお、始点と終点をユーザに指定させる場合、終点の方がユーザが目的とする事物であり、始点はその終点まで連鎖して欲しい事物（典型的にはそのユーザ自身）である。また、始点と終点という２つのノードを基点ノードとして指定させる代わりに、基点ノードを１つだけ指定させてもよい。例えば、文書「Ｄｏｃ１」に対して人を介して関連する事物を知りたい場合、１つのノードすなわち文書「Ｄｏｃ１」のみを基点ノードとして指定させてもよい。
【００４４】
上限ホップ数指定受付部１４は、基点ノードからの検索範囲を表す上限のホップ数（すなわち、リンクの数）の指定をユーザから受け付ける。
【００４５】
これら基点ノード指定受付部１２及び上限ホップ数指定受付部１４が、この検索装置のための検索条件を入力する検索ＵＩ（ユーザインタフェース）１６を構成している。なお、検索範囲を表す上限ホップ数の指定は必須のことではない。上限ホップ数の指定を求めない構成の場合は、検索ＵＩ１６は上限ホップ数指定受付部１４を持たなくてよい。
【００４６】
検索処理部２０は、上に概説した検索手順を実行することで、検索ＵＩ１６を介してユーザから入力された基点ノードに対して、特定属性（例えば「人」）のノードを介した関係の連鎖経路を検索する。様々な属性のうちどれを「特定属性」とするかは、検索処理部２０内に固定的に設定しておいてもよいし、上述したようにユーザに選択させるようにしてもよい。ユーザに選択させる場合には、検索ＵＩ１６に属性選択のためのＵＩを設ければよい。なお、このように「特定属性」をユーザに選択させる方式の場合、検索に用いる検索式１〜４における述語rdf:type の目的語は、選択された属性を表す値とすればよい。ソート部２２は、検索処理部２０が検索した１以上の連鎖経路を、あらかじめ定められた基準に従ってソート（順序づけ）する。例えば、ソートの基準としては、連鎖経路のホップ数の小さい順などといった基準が考えられる。
【００４７】
検索結果提示部２４は、ソート部２２のソート結果をユーザに提示（すなわち表示）する処理を実行する。検索結果提示部２４は、例えば、検索された１以上の連鎖経路をソート順に一覧表示すればよい。ただし、これは一例に過ぎず、ソート結果の提示の仕方は特に限定されない。
【００４８】
次に、図６及び図７を参照して、検索処理部２０の処理手順の一例を説明する。この例は、基点ノードとして始点と終点の２つをユーザが指定する場合の例である。
【００４９】
この手順では、図６に示すように、まず検索ＵＩ１６の基点ノード指定受付部１２により、グラフ中のノードのうち始点とするノード及び終点とするノードの指定をユーザから受け付けると共に、上限ホップ数指定受付部１４によりユーザから上限ホップ数の指定を受け付ける（Ｓ１０）。これらの指定を受け付けると、検索処理部２０は、ホップ数を表すカウンタの値を１に初期化する（Ｓ１２）。
【００５０】
次に検索処理部２０は、終点に指定されたノードを含んだ経路情報を作成し、作成した経路情報をその終点ノードと対応づけて記憶すると共に（Ｓ１４）、その終点ノードをホップ数１用の着目ノードのリスト（着目ノードリスト）に入れる（Ｓ１６）（すなわち、終点ノードを最初の着目ノードとする）。
【００５１】
ここで、経路情報は、求めたい連鎖の経路に属するノードを、その連鎖経路上でのそれらノードの並び順に並べた列の情報である。なお、連鎖経路上のリンクの情報を経路情報に含めてもよい。
【００５２】
図６及び図７の手順では、終点ノードから連鎖経路の探索を始め、条件に合致する（すなわち上述の検索式１〜４のいずれかを満たす）隣接ノードを求めるごとに、その隣接ノードを経路情報に追加していく。この探索の過程で、連鎖経路が枝分かれする場合もある。このような枝分かれが生じる場合は、枝ごとに経路情報が追加される。
【００５３】
このように終点ノードから探索を開始するのは、ユーザが目的とする終点ノードから連鎖経路を探索することで、仮に始点ノードまで連鎖する経路が見つからない場合でも、目的とする終点ノードに繋がる連鎖経路は提示できるからである。図３の例を参照すると、目的である文書「Ｄｏｃ１」から人を介した関係が連鎖して構成される連鎖経路が、仮に始点である人物「あなた」に到達しなくても、その連鎖経路上にあるいずれかの「人」に、あなたが面識を持っている（ただし、この面識の事実はグラフデータには登録されていない）可能性があるので、このような連鎖経路を提示するのには意味がある。
【００５４】
次に、検索処理部２０は、カレントの着目ノードリスト内のノードごとに、Ｓ１８〜Ｓ３０の処理を繰り返す。これまでの説明の流れでは、現時点ではカレント（すなわちホップ数＝１）の着目ノードリストに終点ノードが入っているだけなので、まずはその終点ノードを着目ノードとして、Ｓ１８〜Ｓ３０の処理を実行する。
【００５５】
カレントの着目ノードリスト内の個々の着目ノードについての処理では、検索処理部２０は、まず、着目ノードリストから未処理の着目ノードを１つ取り出し（Ｓ１８）、その着目ノードに対応づけて記憶していた経路情報を取得する（Ｓ２０）。次に検索処理部２０は、その着目ノードに対してリンクを介して隣接する（すなわち１つのリンクで接続されている）ノードをグラフからすべて（ただしＳ２０で取得した経路情報に含まれるノードは除く）抽出し、それら抽出したノード（着目ノードに対する隣接ノードと呼ぶ）を隣接ノードリストに入れる（Ｓ２２）。そして、検索処理部２０は、隣接ノードリスト内の隣接ノードごとに、隣接ノード処理（Ｓ３０）を繰り返す。
【００５６】
隣接ノード処理（Ｓ３０）の詳細な手順の一例を図８に示す。個々の隣接ノードについての処理では、検索処理部２０は、まず、隣接ノードリストから未処理の隣接ノードを１つ取り出す（Ｓ３２）。そして、取り出した隣接ノード又は着目ノードが特定属性（図３等の例では「人」）を持つかどうかを判定する（Ｓ３４）。Ｓ２２，Ｓ３２，Ｓ３４の処理は、着目ノードを<someUri>に設定して上述した検索式１〜４を実行する処理である。Ｓ３４の判定結果がＹｅｓの場合、Ｓ２０で取得した経路情報（着目ノードに対応するもの）内のノードの列の末尾に当該隣接ノードを追加することで、新たな経路情報を生成し、生成した経路情報を当該隣接ノードと対応づけて記憶する（Ｓ３６）。新たに生成した経路情報には、カレントのホップ数のカウンタ値を含める。このカウンタ値が、その経路情報の終点ノードからの長さ（ホップ数）を示している。なお、経路情報にリンクも記録する場合には、新たに生成する経路情報には、着目ノードと当該隣接ノードとを繋ぐリンクの情報も含める。次に検索処理部２０は、当該隣接ノードがＳ１０で指定された始点ノードに一致しているか否かを判定する（Ｓ３８）。一致していなければ、当該隣接ノードを、（終点ノードからみてカレントのホップ数の）次のホップ数用の着目ノードリストに入れて、処理を終了する（Ｓ４０）。一致していれば、当該隣接ノードに対応づけて記憶している経路情報に対して、「到達済み」の旨の情報を記録して処理を終了する（Ｓ４２）。なお、着目ノードに隣接するすべての隣接ノードについてＳ３２〜Ｓ４２の処理が終わると、当該着目ノードに対応する経路情報は削除してよい。
【００５７】
以上の隣接ノード処理（Ｓ３０）により、着目ノード又は隣接ノードのいずれかが特定属性（例えば「人」）を有するという条件が満たされる場合に、終点ノードから着目ノードまで延びてきている連鎖の経路に対して隣接ノードが追加されることになる。また、条件を満たす隣接ノードが複数存在する場合は、その隣接ノードの数だけ新たな連鎖経路（経路情報）が生成されることになる。
【００５８】
図６に戻ると、カレントの着目ノードリスト中の全ノードについてＳ１８〜Ｓ３０の処理が終わると、検査処理部２０は次のホップ数用の着目ノードリストが空か否かを調べ（Ｓ２４）、空でなければ、ホップ数のカウンタの値を１増加させる（Ｓ２６）。そして、カウンタの値がＳ１０で指定された上限ホップ数を超えたかどうかを判定し（Ｓ２８）、超えていなければ、カウンタが示すホップ数用の着目ノードリストについて、Ｓ１８〜Ｓ３０の処理を繰り返す。カウンタ値が上限ホップ数を超えていれば、探索を打ち切って処理を終了する。また、Ｓ２４で次のホップ数用の着目ノードリストが空である（すなわち特定属性のノードを介した連鎖がとぎれた）ことが分かった場合も、探索を打ち切って処理を終了する。
【００５９】
図６及び図７に示した処理により、終点ノードからみて、特定属性のノードを介する関係により連鎖した経路の経路情報がいくつか作成される。そのような経路情報の例を図８に示す。図８に示した表の１行が１つの経路情報である。個々の経路情報は、到達フラグ、ホップ数、及び終点ノードからの経路、の情報を含んでいる。到達フラグは、当該連鎖の経路が始点ノードまで到達したか否かを示すフラグである。到達フラグは、Ｓ４２（図７）で「到達」にセットされる。それ以外の場合は「未達」（到達していない）である。ホップ数は当該連鎖の経路のホップ数である。そして、終点ノードからの経路は、Ｓ１４及びＳ３６で追加されるノード（及び着目ノードからそのノードまでのリンク）のリストである。図８の例は、図３に示したグラフに対応するものであり、１つめの経路情報は、終点ノード「Ｄｏｃ１」を先頭とし、リンク「作成」、属性が「人」であるノード「Ｐｓｎ１」、逆向きのリンク「参加」（図８においてリンクの名称に引いた下線は逆向きを示す。なお、終点に向かう向きを順方向とした場合の逆向きである）、ノード「Ｂ会議」、…というように始点ノード「あなた」まで延びる連鎖を示している。この経路情報は、始点まで到達しているので、到達フラグの値は「到達」である。図８の３行目の経路情報は、図３には示していないが、これは始点まで到達しない連鎖の例である。
【００６０】
次に、図９を参照して、ソート部２２の処理手順の一例を説明する。ソート部２２は、検索処理部２０が図６及び図７に示した処理により生成した経路情報群（図８参照）に対して、図９の処理を行う。この処理では、ソート部２２は、それら経路情報の中に到達フラグが「到達」となっているものがあるかどうかを調べ（Ｓ５０）、「到達」済みのものが１つでもあれば、それら「到達」済みの経路情報のみをホップ数の少ない順にソートする（Ｓ５２）。すなわち、ホップ数の少ない連鎖経路ほど、上位（すなわち重要度が高い）に順位付けする。間に入る人の数が少ないほど、目的（文書「Ｄｏｃ１」）にアクセスするための労力が少なくて済む可能性が高いからである。「到達」済みのものに限るのは、「到達」済みのものがあるのであれば、「未達」の連鎖経路には価値がないからである。
Ｓ５０の判定結果がＮｏ、すなわち検索処理部２０が求めた経路情報が未達のもののみであれば、それら未達の経路情報をホップ数の少ない順にソートする（Ｓ５４）。そして、Ｓ５２又はＳ５４のソート結果を検索結果提示部２４に出力する（Ｓ５６）。検索結果提示部２４は、ソートされた連鎖経路を表示する。
【００６１】
以上、実施の形態の装置の処理手順の例を説明した。以上の例では、終点ノードから探索を行ったが、これに限らず、始点ノードから探索を行うようにしてもよい。
【００６２】
また、以上に例示した図６及び図７の手順は、ユーザから２つの基点ノード、すなわち始点及び終点の指定を受け付ける場合の例であった。ユーザから１つ基点ノードのみの指定を受け付ける場合、図６の手順はＳ１０を１つの基点ノードの指定を受け付けるように変更すればよく、図７の手順はＳ３８及びＳ４２を除く形に変更すればよい。
【００６３】
また、上述の例では、着目ノード又は隣接ノードのいずれかが特定属性を持っている場合、それら両ノード間のリンクの種類によらずその隣接ノードを連鎖経路に組み入れたが、これは一例に過ぎない。この代わりに、そのような場合でも、両ノード間のリンクがあらかじめ定められた何種類かのうちのどれかに該当しなければ、隣接ノードを連鎖経路に組み入れないようにしてもよい。例えば、図３の例では、着目ノード又は隣接ノードの少なくとも一方が特定属性「人」を持つ場合、着目ノードと隣接ノードとの間のリンク（述語）の種類が「同僚である」、「参加する」、「所属する」のいずれかに該当する場合にのみ、その隣接ノードを連鎖経路に組み入れるようにする、等の処理を行えばよい。「同僚である」、「参加する」、「所属する」等のリンクは、人同士を繋ぐ関係であるため、これらに限定して連鎖経路を延ばすのである。ただし、終点ノードが特定属性（「人」）を持たない場合（図３の終点ノード「Ｄｏｃ１」はこれに該当する）は、例外であり、終点ノードに隣接するノードが特定属性（「人」）を持てば、その隣接ノードを連鎖経路に組み入れるようにしてもよい。
【００６４】
また、以上の例では、着目ノードが特定属性（例えば「人」）を持っている場合、その着目ノードに隣接するノードは無条件に連鎖経路に追加されるが、この代わりに、そのような場合でも、隣接するノードが別の条件を満たさない限り連鎖経路に入れないようにしてもよい。例えば、隣接ノードがある一群の属性のいずれかに該当するという条件を課す等である。
【００６５】
例えば、図３の例では、「人」属性を持つノード「Ｐｓｎ１」に隣接するノードとして「Ｂ会議」、「組織Ｃ」、「Ｄｏｃ１」が例示されているが、この他にその人物「Ｐｓｎ１」が文書「Ｄｏｃ１」以外の文書（例えば「Ｄｏｃ２」と呼ぶ）を「作成」していたとする。この場合、終点ノード「Ｄｏｃ１」から探索をはじめて、「Ｐｓｎ１」が着目ノードとなった場合、（直前の着目ノード「Ｄｏｃ１」を除いて）着目ノードに隣接するノードは「Ｂ会議」、「組織Ｃ」、「Ｄｏｃ２」となる。これらはいずれも特定属性「人」を有していないが、着目ノード「Ｐｓｎ１」が「人」属性を有しているので、上述の図７の手順では、それら３つのノードがそれぞれ連鎖経路に組み入れられる。これに対し、着目ノードが特定属性を持つ場合に、隣接ノードが「人」又は「会議」又は「組織」のいずれかの属性を持つ場合に限り、その隣接ノードを連鎖経路に組み入れるという条件を課してもよい。「会議」や「組織」等といった人の集まりに該当するノードは、人同士の関係を媒介する（例えばその会議の参加者同士として知り合っている）可能性が高いため、「人」を介した関係を辿っていく場合には、「会議」等の属性のノードが間に入っても人間関係が辿れる可能性が高い。これに対し、人物「Ｐｓｎ１」が「作成」した文書「Ｄｏｃ２」を別の人物「Ｐｓｎ２」が「閲覧」したという関係があったとして、人物「Ｐｓｎ１」と「Ｐｓｎ２」とが知り合いである可能性は高いとはいえない。そのようなことから、「人」でないノードは、人間関係を媒介する事物であることを示す属性（「会議」、「組織」など）の集合のうちのいずれかの属性を持つ場合にのみ、連鎖経路に組み入れられるように限定した方がよい場合がある。このように限定した場合、「文書」属性を持つ「Ｄｏｃ２」は連鎖経路に組み入れられない。
【００６６】
また、以上の例では、連鎖の条件とする特定属性が「人」である場合を示したが、他の属性を特定属性として用いてもよい。
【００６７】
以上に例示した検索装置は、例えば、汎用のコンピュータに上述の各機能モジュールの処理を表すプログラムを実行させることにより実現してもよい。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、ＨＤＤ（ハードディスクドライブ）を制御するＨＤＤコントローラ、各種Ｉ／Ｏ（入出力）インタフェース、ローカル・エリア・ネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバスを介して接続された回路構成を有する。また、そのバスに対し、例えばＩ／Ｏインタフェース経由で、ＣＤやＤＶＤなどの可搬型ディスク記録媒体に対する読み取り及び／又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び／又は書き込みのためのメモリリーダライタ、などが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがＣＤやＤＶＤ等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ハードディスクドライブ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。
【符号の説明】
【００６８】
１０  データベース、１２  基点ノード指定受付部、１４  上限ホップ数指定受付部、１６  検索ＵＩ、２０  検索処理部、２２  ソート部、２４  検索結果提示部。
【図１Ａ】
0005866922.tif 000002
【図１Ｂ】
0005866922.tif 000003
【図２】
0005866922.tif 000004
【図３】
0005866922.tif 000005
【図４】
0005866922.tif 000006
【図５】
0005866922.tif 000007
【図６】
0005866922.tif 000008
【図７】
0005866922.tif 000009
【図８】
0005866922.tif 000010
【図９】
0005866922.tif 000011