(57)【要約】【課題】Ｗｅｂページの人気や話題性、記載内容の精度等を反映した検索結果を短時間で出力可能な情報検索システム及び情報検索方法を提供することである。【解決手段】検索を実行した端末で入力されたキーワードに基づいてＷｅｂページの検索を行う情報検索システムにおいて、検索対象となるＷｅｂページがリンクしているＷｅｂページと、検索対象となるＷｅｂページに対して現にあるいは一定期間内に接続された端末との関連から遷移確率を演算し、演算した値に基づいて検索対象となるＷｅｂページを序列化して端末に出力する。【選択図】図４
2013025421.tif 000002
【特許請求の範囲】
【請求項１】
検索を実行した端末で入力されたキーワードに基づいてＷｅｂページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、
検索対象となるＷｅｂページを序列化する情報序列化手段を有するものであり、
情報序列化手段は、検索対象となるＷｅｂページがリンクしているＷｅｂページと、検索対象となるＷｅｂページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施する機能を備えたことを特徴とする情報検索システム。
【請求項２】
遷移確率の演算は、検索対象となるＷｅｂページと検索対象となるＷｅｂページに対して現にあるいは一定期間内に接続された端末を含む構成によって正方行列を設定し、当該正方行列の固有ベクトルを演算する演算内容を含むことを特徴とする請求項１に記載の情報検索システム。
【請求項３】
前記正方行列の要素は、Ｗｅｂページがリンクしているリンク先の数に基づく値と、端末が現にあるいは一定期間内に接続したＷｅｂページの数に基づく値によって構成されていることを特徴とする請求項２に記載の情報検索システム。
【請求項４】
前記正方行列の要素は、Ｗｅｂページがリンクしているリンク先の数に基づく値をＡとし、端末が現にあるいは一定期間内に接続したＷｅｂページの数をＢとしたとき、Ａ／（Ａ＋Ｂ）、Ｂ／（Ａ＋Ｂ）あるいはこれらに系数が掛けられた値であることを特徴とする請求項２又は３に記載の情報検索システム。
【請求項５】
検索実行時又は検索実行以前に、検索対象となるＷｅｂページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、
情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすＷｅｂページと、当該Ｗｅｂページを出力している又は出力した端末である出力端末を特定するものであって、
前記出力端末を仮想のＷｅｂページとし、出力端末が出力しているＷｅｂページと仮想のＷｅｂページとの間に相互リンクが形成されるとしたとき、Ｗｅｂページ及び仮想のＷｅｂページによって形成されるリンク構造に基づき、リンク元のＷｅｂページの表示からリンク先のＷｅｂページの表示への切り替えを遷移とした遷移確率行列を設定し、
設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるＷｅｂページを序列化することを特徴とする請求項１乃至３のいずれかに記載の情報検索システム。
【請求項６】
前記端末情報に基づいて、前記出力端末を使用する使用者の特定項目に対する知識及び／又は使用者の検索能力に対するユーザの重要度を示すユーザランク値を算出するものであり、
前記ユーザランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び／又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項２乃至５のいずれかに記載の情報検索システム。
【請求項７】
ネットワーク上のＷｅｂページの内容に関する情報を取得可能な情報取得機能を有し、情報取得機能が取得した情報に基づいてＷｅｂページの内容の重要度を示すリレーションランク値を算出するものであり、
前記リレーションランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び／又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項２乃至６のいずれかに記載の情報検索システム。
【請求項８】
端末で入力されたキーワードに基づいてデータベースの検索を行なうと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、
検索実行時又は検索実行以前に、検索対象となるＷｅｂページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、
検索対象となるＷｅｂページを序列化する情報序列化手段を有するものであり、
情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすＷｅｂページと、当該Ｗｅｂページを出力している又は出力した端末である出力端末を特定し、前記Ｗｅｂページと出力端末に基づいて正方行列を設定するものであって、
前記正方行列はＷｅｂページ及び出力端末に対応する行要素及び列要素から形成されるものであり、その各要素Ｐ（ｉ，ｊ）は下記式（１）の関係を満たすものであり、
設定した前記正方行列の固有ベクトルを算出し、算出した固有ベクトルの成分の大きさに基づいて検索対象となるＷｅｂページを序列化することを特徴とする情報検索システム。
Ｐ（ｉ，ｊ）＝  αＸ／Ｙ  ・・・（１）
α  ＝０以外の数
Ｘ  ＝  列「ｊ」に対応するＷｅｂページから行「ｉ」に対応するＷｅｂページへのリンクの数、又は、列「ｊ」に対応するＷｅｂページの行「ｉ」に対応する出力端末での表示数、又は、列「ｊ」に対応する出力端末での行「ｉ」に対応するＷｅｂページの表示数、又は０
Ｙ  ＝  列「ｊ」に対応するＷｅｂページの出力端末での表示数と、列「ｊ」に対応するＷｅｂページに形成されているリンク数の総和
【請求項９】
検索を実行した端末で入力されたキーワードに基づいてＷｅｂページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索方法であって、
検索対象となるＷｅｂページがリンクしているＷｅｂページと、検索対象となるＷｅｂページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施することを特徴とする情報検索方法。
【請求項１０】
検索実行時又は検索実行以前に、検索対象となるＷｅｂページを出力している端末に係る情報である端末情報を取得し、
少なくとも端末情報に基づいて所定の条件を満たすＷｅｂページと、当該Ｗｅｂページを出力している又は出力した端末である出力端末を特定するものであり、
前記出力端末を仮想のＷｅｂページとし、出力端末が出力しているＷｅｂページと仮想のＷｅｂページとの間に相互リンクが形成されるとしたとき、Ｗｅｂページ及び仮想のＷｅｂページによって形成されるリンク構造に基づき、リンク元のＷｅｂページの表示からリンク先のＷｅｂページの表示への切り替えを遷移とした遷移確率行列を設定し、
設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるＷｅｂページを序列化することを特徴とする請求項９に記載の情報検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）の情報検索システムにおいて、目的の情報を効率良く容易に取得するための技術に関する。
【背景技術】
【０００２】
ＷＷＷの膨大な情報の中から目的の情報を得ようとする場合、検索システムを利用して該当するＷｅｂページを特定することが一般的である。このような検索システムでは、ユーザが入力した検索キーワードに該当するＷｅｂページを特定して集め、集められたＷｅｂページに重要度を付けて重要度の高いものから順に提示している。
【０００３】
ここで、集められたＷｅｂページに重要度を付ける技術として、Ｗｅｂページ内の名詞の出現数やリンク構造等を基準にＷｅｂページのランク付けを行う技術が広く知られている。具体的には、例えば、ユーザが入力した検索キーワードがタイトル等の重要な箇所で使用されているＷｅｂページや、ユーザが入力した検索キーワードが適度に多く出現するＷｅｂページに対して高い重要度を付ける方法が知られている。また、他のＷｅｂページから数多くリンクされているＷｅｂページや、内容の関連性が高いＷｅｂページからリンクされているＷｅｂページに対して高い重要度を付ける方法が知られている。
【０００４】
しかしながら、このようにＷｅｂページの内容やリンク構造だけを基準にＷｅｂページの重要度を規定すると、ユーザが検索用語を上手く選定できない場合、目的とする情報が開示されたＷｅｂページが上位に表示されず、ユーザが目的とする情報が開示されたＷｅｂページを発見できないという問題があった。さらにまた、目的とする情報が開示されたＷｅｂページを特定できた場合であっても、目的とする情報が難解であった場合、ユーザが深い理解を得られないという問題があった。
【０００５】
そこで本発明者らは、このような問題に鑑み、検索結果として集められた各Ｗｅｂページの人気や話題性、記載内容の精度等に基づいてＷｅｂページに重要度を付け、重要度の高いものから順に提示することができる情報検索システム及び情報検索方法を先の出願（特許文献１）により提案した。
【０００６】
具体的に説明すると、本発明者らが提案した情報検索システムでは、検索結果として集められた複数のＷｅｂページを、検索実行時にそれぞれのＷｅｂページを閲覧しているユーザの数が多い順に並び替えて検索結果を表示することができる。即ち、検索実行時に多くのユーザが注目しているＷｅｂページとは、検索実行時において話題性（必要性）の高いＷｅｂページであり、そのようなＷｅｂページを検索結果の上位に表示することによって、検索実行時に必要性が高い情報を取得し易くしている。
【０００７】
また、本発明者らが提案した情報検索システムでは、予め情報検索システムを使用する全てのユーザの情報を取得しておき、取得した情報を検索結果に反映することができる。例えば、ある特定のユーザが検索を実行したとき、検索結果として集められたそれぞれのＷｅｂページをどのようなユーザが閲覧しているのか情報検索システムが判別し、特定の条件を満たしたユーザが閲覧しているＷｅｂページを上位に表示する。例えば、検索を実行したユーザが「プログラム」というキーワードで検索を実行したのであれば、「職業」が「プログラマ」であるユーザが閲覧しているＷｅｂページが上位に表示される。このように、検索結果として集められたＷｅｂページに、検索のキーワードに関連する分野の専門家であるユーザが閲覧しているＷｅｂページあれば、そのＷｅｂページを上位に表示する。即ち、専門家が多く閲覧しているＷｅｂページは内容が充実した（内容の精度が高い）Ｗｅｂページであり、そのようなＷｅｂページを検索結果の上位に表示することによって、ユーザが精度の高い情報を取得し易くしている。
【０００８】
そして、本発明者らが提案した情報検索システムでは、検索実行後に特定したＷｅｂページを閲覧するとき、同じＷｅｂページを閲覧している他のユーザと通信可能となっている。そのことにより、特定したＷｅｂページの内容が難解であった場合であっても、他のユーザに質問することで、ユーザはＷｅｂページの内容に対する理解を深めることができる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２０１１−３９６２５号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記したように、検索結果として集められた各Ｗｅｂページの人気や話題性、記載内容の精度等に基づいてＷｅｂページに重要度を付け、重要度の高いものから順に提示する情報検索システムによると、ユーザが真に必要とする情報をより容易に取得できる。そこで本発明は、人気や話題性、記載内容の精度等を反映したＷｅｂページの重要度の算出がより正確に実施可能であり、算出したＷｅｂページの重要度を反映した検索結果を短時間で出力可能な情報検索システム及び情報検索方法を提供することを課題とする。
【課題を解決するための手段】
【００１１】
上記課題を解決するための本発明の一態様は、検索を実行した端末で入力されたキーワードに基づいてＷｅｂページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、検索対象となるＷｅｂページを序列化する情報序列化手段を有するものであり、情報序列化手段は、検索対象となるＷｅｂページがリンクしているＷｅｂページと、検索対象となるＷｅｂページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施する機能を備えたことを特徴とする情報検索システムである。
なお、「遷移傾向を推定する演算」とは、実際の遷移確率の演算に加えて、遷移確率の演算に必要な要素に改変を加えた上で行う演算を含む。また、「遷移」とは、Ｗｅｂページ又は端末を頂点とし、特定のＷｅｂページからリンクを辿って他のＷｅｂページを表示することとする。さらに、特定の端末による特定のＷｅｂページの出力があったとき、特定のＷｅｂページを含む２つのＷｅｂページの間にリンクが形成されているものと同様な遷移が想定されるものとする。
また、このとき想定される「特定のＷｅｂページを含む２つのＷｅｂページの間にリンクが形成されているものと同様な遷移」は、「２つのＷｅｂページの間に相互リンクが形成されているものとする遷移」とすることが望ましい。なぜなら、「２つのＷｅｂページの間にいずれか一方のＷｅｂページから他方のＷｅｂページにリンクが形成されているものとする遷移」が想定された場合に比べて、ユーザに閲覧されることによるＷｅｂページの重要度の上昇がより正確に反映されるためである。
【００１２】
本発明の第二の態様は、遷移確率の演算は、検索対象となるＷｅｂページと検索対象となるＷｅｂページに対して現にあるいは一定期間内に接続された端末を含む構成によって正方行列を設定し、当該正方行列の固有ベクトルを演算する演算内容を含むことを特徴とする請求項１に記載の情報検索システムである。
【００１３】
本発明の第三の態様は、前記正方行列の要素は、Ｗｅｂページがリンクしているリンク先の数に基づく値と、端末が現にあるいは一定期間内に接続したＷｅｂページの数に基づく値によって構成されていることを特徴とする請求項２に記載の情報検索システムである。
【００１４】
本発明の第四の態様は、前記正方行列の要素は、Ｗｅｂページがリンクしているリンク先の数に基づく値をＡとし、端末が現にあるいは一定期間内に接続したＷｅｂページの数をＢとしたとき、Ａ／（Ａ＋Ｂ）、Ｂ／（Ａ＋Ｂ）あるいはこれらに系数が掛けられた値であることを特徴とする請求項２又は３に記載の情報検索システムである。
【００１５】
本発明の第五の態様は、検索実行時又は検索実行以前に、検索対象となるＷｅｂページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすＷｅｂページと、当該Ｗｅｂページを出力している又は出力した端末である出力端末を特定するものであって、前記出力端末を仮想のＷｅｂページとし、出力端末が出力しているＷｅｂページと仮想のＷｅｂページとの間に相互リンクが形成されるとしたとき、Ｗｅｂページ及び仮想のＷｅｂページによって形成されるリンク構造に基づき、リンク元のＷｅｂページの表示からリンク先のＷｅｂページの表示への切り替えを遷移とした遷移確率行列を設定し、設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるＷｅｂページを序列化することを特徴とする請求項１乃至３のいずれかに記載の情報検索システムである。
なお、上記リンク構造には仮想のリンクを含み、上記リンク元のＷｅｂページ又は上記リンク先のＷｅｂページには、仮想のページを含むものとする。
【００１６】
このような情報検索システムによると、人気や話題性、記載内容の精度等を反映したＷｅｂページの重要度の算出がより正確に実施可能であり、算出したＷｅｂページの重要度を反映した検索結果を短時間で出力可能となっている。したがって、並び替えの基準となる項目が多くなる等によって計算量が膨大になってしまった場合であっても、短時間で検索結果を取得することができる。
【００１７】
本発明の第六の態様は、前記端末情報に基づいて、前記出力端末を使用する使用者の特定項目に対する知識及び／又は使用者の検索能力に対するユーザの重要度を示すユーザランク値を算出するものであり、
前記ユーザランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び／又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項２乃至５のいずれかに記載の情報検索システムである。
【００１８】
本発明の第六の態様では、特定項目に対する知識が高いユーザや検索能力が高いユーザが閲覧している、内容の充実したＷｅｂページを上位に表示させることができる。そのことにより、ユーザが検索実行時に必要性の高い情報を容易に取得することができる。
【００１９】
本発明の第七の態様は、ネットワーク上のＷｅｂページの内容に関する情報を取得可能な情報取得機能を有し、情報取得機能が取得した情報に基づいてＷｅｂページの内容の重要度を示すリレーションランク値を算出するものであり、前記リレーションランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び／又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項２乃至６のいずれかに記載の情報検索システムである。
【００２０】
本発明の第七の態様では、検索条件と関連性の高い内容のＷｅｂページを上位に表示させることができる。そのことにより、ユーザが検索実行時に必要性の高い情報を容易に取得することができる。
【００２１】
本発明の第八の態様は、端末で入力されたキーワードに基づいてデータベースの検索を行なうと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、検索実行時又は検索実行以前に、検索対象となるＷｅｂページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、検索対象となるＷｅｂページを序列化する情報序列化手段を有するものであり、情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすＷｅｂページと、当該Ｗｅｂページを出力している又は出力した端末である出力端末を特定し、前記Ｗｅｂページと出力端末に基づいて正方行列を設定するものであって、前記正方行列はＷｅｂページ及び出力端末に対応する行要素及び列要素から形成されるものであり、その各要素Ｐ（ｉ，ｊ）は下記式（１）の関係を満たすものであり、設定した前記正方行列の固有ベクトルを算出し、算出した固有ベクトルの成分の大きさに基づいて検索対象となるＷｅｂページを序列化することを特徴とする情報検索システムである。
Ｐ（ｉ，ｊ）＝  αＸ／Ｙ  ・・・（１）
α  ＝０以外の数
Ｘ  ＝  列「ｊ」に対応するＷｅｂページから行「ｉ」に対応するＷｅｂページへのリンクの数、又は、列「ｊ」に対応するＷｅｂページの行「ｉ」に対応する出力端末での表示数、又は、列「ｊ」に対応する出力端末での行「ｉ」に対応するＷｅｂページの表示数、又は０
Ｙ  ＝  列「ｊ」に対応するＷｅｂページの出力端末での表示数と、列「ｊ」に対応するＷｅｂページに形成されているリンク数の総和
【００２２】
本発明の第九の態様は、検索を実行した端末で入力されたキーワードに基づいてＷｅｂページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索方法であって、検索対象となるＷｅｂページがリンクしているＷｅｂページと、検索対象となるＷｅｂページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施することを特徴とする情報検索方法である。
【００２３】
本発明の第十の態様は、検索実行時又は検索実行以前に、検索対象となるＷｅｂページを出力している端末に係る情報である端末情報を取得し、少なくとも端末情報に基づいて所定の条件を満たすＷｅｂページと、当該Ｗｅｂページを出力している又は出力した端末である出力端末を特定するものであり、前記出力端末を仮想のＷｅｂページとし、出力端末が出力しているＷｅｂページと仮想のＷｅｂページとの間に相互リンクが形成されるとしたとき、Ｗｅｂページ及び仮想のＷｅｂページによって形成されるリンク構造に基づき、リンク元のＷｅｂページの表示からリンク先のＷｅｂページの表示への切り替えを遷移とした遷移確率行列を設定し、設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるＷｅｂページを序列化することを特徴とする請求項９に記載の情報検索方法。
【００２４】
本発明の第九の態様及び第十の様態では、検索実行時において人気の高い情報を有するＷｅｂページや、ものごとに対する興味が似ているユーザ、検索目的の分野に精通しているユーザ等が閲覧するＷｅｂページ等が検索結果の上位に表示されるため、必要性が高い情報や質の高い情報を取得し易い。また、そのような検索結果を短時間で出力できる。
【発明の効果】
【００２５】
本発明は、検索を実行した端末で入力されたキーワードに基づいてＷｅｂページの検索を行い、その検索結果を前記端末に出力して表示させるための情報検索システムにおいて、Ｗｅｂページの人気や話題性、記載内容の精度等を反映した検索結果をより速く出力できるという効果がある。
【図面の簡単な説明】
【００２６】
【図１】本発明の第１の実施形態に係る情報検索システムの構成を示す概念図である。
【図２】本発明の第１の実施形態に係る情報検索システムの機能ブロックの一例を示す図である。
【図３】本発明の第１の実施形態に係る情報検索システムのハードウェア構成の一例を示す図である。
【図４】本発明の第１の実施形態に係る情報検索システムによる検索手順の一例を示すフローチャートである。
【図５】本発明の第１の実施形態に係る情報検索システムで検索を実施する際に検索対象となるＷｅｂページのリンク構造、及び当該Ｗｅｂページの閲覧状況の一例を示す説明図である。
【図６】本発明の第１の実施形態に係る情報検索システムで検索を実施する際に設定するランク値演算用行列の一例を示す説明図である。
【図７】本発明の第２の実施形態に係る情報検索システムで検索を実施する際に設定するランク値演算用行列の一例を示す説明図である。
【図８】本発明の実施例において固有値演算の速度を検証するために用いた行列を示す説明図であり、（ａ）はラプラシアン行列を示し、（ｂ）は遷移確率行列を示す。
【図９】本発明の実施例において、ラプラシアン行列の固有値演算におけるプロセッサ数を変化させたときの処理時間比を示すグラフである。
【図１０】本発明の実施例において、ラプラシアン行列の固有値演算における処理時間を示すグラフである。
【図１１】本発明の実施例において、遷移確率行列の固有値演算におけるプロセッサ数を変化させたときの処理時間比を示すグラフである。
【図１２】本発明の実施例において、遷移確率行列の固有値演算における並列化効率を示すグラフである。
【図１３】本発明の実施例において、複数ノードでのラプラシアン行列の固有値演算におけるネットワーク性能の影響を示すグラフである。
【発明を実施するための形態】
【００２７】
本発明の実施形態に係る情報検索システム、並びに情報検索方法の提供方法についてそれぞれ図面を参照しながら詳細に説明する。
【００２８】
図１は、第１の実施形態の情報検索システム１の構成の概略を示す概念図である。図１に示す様に、情報検索システム１は、検索装置２とクライアント端末４（図１では符号４ａ〜４ｄ及び・・・で示す）で構成されており、それぞれ電気通信網を介して接続されている。クライアント端末４にて、それぞれブラウザ５（図１では符号５ａ〜５ｄ及び・・・で示す）が起動されている。
【００２９】
第１の実施形態の情報検索システム１は、入力情報を取得可能となっている。具体的には、この入力情報は、ブラウザ５にプラグイン形式等の所定の手段で組み込んだ端末側情報取得装置７で取得され、検索装置２へ送信される。なお、入力情報とは、ユーザがブラウザ５やブラウザ５と連動するプログラム（例えば、プラグインツールバー等）を介して入力した検索キーワード等に関する情報である。
【００３０】
また端末側情報取得装置７は、上記した入力情報だけでなく、ブラウザ５を介したＷｅｂページの出力に関する情報である使用情報も検索装置２へ送信することができる。具体的には、端末側情報取得装置７は、使用情報として、ブラウザ５における規定のＷｅｂページの表示開始時間や表示終了時間といったＷｅｂページの表示時間に関わる情報を検索装置２へ送信することができる。さらに、使用情報として、規定のＷｅｂページからリンクを辿って他のＷｅｂページを表示させた場合に、移動元のＷｅｂページのＵＲＬや移動先のＷｅｂページのＵＲＬといったＷｅｂページの遷移経路を示す情報を検索装置２へ送信することができる。
【００３１】
このように、端末側情報取得装置７は、上記したような入力情報や使用情報を端末情報として検索装置２へ送信する。このとき、端末側情報取得装置７による情報の送信は、ブラウザ５が起動された場合、検索が実行された等の所定の操作が実行された場合、前回情報の送信が終了してから規定時間が経過した場合、といった所定のタイミングに自動で実施される。
【００３２】
一方、検索装置２では、端末側情報取得装置７から送信された端末情報を検索用データベース３に格納する。即ち、ネットワーク上の各クライアント端末４（４ａ〜４ｄ，・・・）から検索装置２に送信された端末情報が、検索装置２の検索用データベース３に格納される（図２）。
【００３３】
また、検索装置２は情報収集部１２を有している。この情報収集部１２は、所謂クローラとインデクサの機能を有するものであって、ＷＷＷ上を巡回し、リソースに関する情報を取得し、まとめて、検索用データベース３に蓄積する。そして、検索用データベース３に蓄積するときは、Ｗｅｂページのリンク構造に関する情報や、記載されているテキスト、タイトル、各種タグ等の内容に関する情報を特徴毎に解析、選別、分類し、検索しやすいようにしておく。
【００３４】
情報検索システム１は、いずれかのクライアント端末４で検索が実行されると、入力された検索キーワードより、検索クエリを作成してサーバである検索装置２に送信する。
【００３５】
検索装置２で検索クエリを受信すると、検索装置２の検索実行部１３は、検索用データベース３に蓄積されたＷｅｂページの中から検索対象となるＷｅｂページを特定する。また、特定されたそれぞれのＷｅｂページを閲覧している、又は閲覧したユーザの数を特定する。そして、詳しくは後述するが、これらの情報に基づいて形成されるランク値演算用行列の固有値を算出し、算出した固有値を検索対象となる各Ｗｅｂページのランク値（重要度の値）とする。
【００３６】
さらに検索実行部１３は、検索結果のＷｅｂページを取得したランク値に基づいて並び替える。そして、検索装置２の検索結果出力部１５が、検索が実行されたクライアント端末４に検索結果を送信し、クライアント端末４で検索結果のＷｅｂページが並び替えた順に表示される。
このことにより、検索実行時に人気が高く、話題性のあるＷｅｂページを検索結果の上位に表示させることができる。
【００３７】
以下、本実施形態の情報検索システム１についてより詳細に説明する。
【００３８】
まず、本実施形態の情報検索システム１の機能的構成について説明する。
なお、以下に記載する本実施形態の情報検索システム１の各機能ブロックは、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの両方として実現され得る。具体的には、コンピュータを利用するものであれば、ＣＰＵや主メモリ、バス、あるいは不揮発性メモリや、所謂外部記憶装置（ハードディスクやフロッピーディスク（登録商標）、ＭＯ、ＣＤ、ＤＶＤ、ＢＤ、磁気テープ等々の記憶装置、及びそれらメディアの読み取り装置）、印刷機器、表示装置、その他外部周辺装置等のハードウェア構成部、またその外部周辺装置用のＩ／Ｏポート、それらハードウェアを制御するためのドライバプログラムやその他アプリケーションプログラム、情報入力に利用されるユーザーインターフェース等が挙げられる。
【００３９】
そして主メモリ上に展開したプログラムに従ったＣＰＵの演算処理によって、インターフェースを介して入力され、各種メモリやハードディスク上に保持されているデータなどが加工、蓄積されたり、上記各ハードウェアやソフトウェアを制御するための命令が生成されたりする。また、本発明はシステムとして実現できるのみでなく、方法としても実現可能である。加えて、本発明の一部をソフトウェアとして構成することができる。そして、そのようなソフトウェアをコンピュータに実行させるために用いるソフトウェア製品、及び同製品を記録媒体に固定した記録媒体も、当然に本発明の技術的な範囲に含まれる（本明細書の全体を通じて同様である）。
【００４０】
図２は、本実施形態の情報検索システム１における機能ブロックの一例を示す図である。この図にあるように、本実施形態の検索システム１は、主に端末側情報取得装置７と検索装置２から構成されている。
【００４１】
端末側情報取得装置７は、端末情報取得部１０と端末情報送信部１１とを少なくとも有している。
【００４２】
端末情報取得部１０は、クライアント端末４のブラウザから、少なくとも閲覧ＵＲＬを含む、端末情報を取得する機能を有する。ここで閲覧ＵＲＬとは、ブラウザを介して表示された（クライアント端末４でユーザが閲覧していた）ＷｅｂページのＷｅｂ上（ネットワーク上）での所在を示す情報であり、例えば、「ｈｔｔｐ：／／・・・／ＡＢＣ．ｊｐｇ」のように記述される情報である。
ここで、ブラウザから端末情報を取得する手段は、特に限定されるものでなく、適宜の方法を用いてよい。これらの方法は、例えば、ＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍ  Ｉｎｔｅｒｆａｃｅ）やＤＤＥ（Ｄｙｎａｍｉｃ  Ｄａｔａ  Ｅｘｃｈａｎｇｅ）、ＯＬＥ（Ｏｂｊｅｃｔ  Ｌｉｎｋｉｎｇ  ａｎｄ  Ｅｍｂｅｄｄｉｎｇ）やファイルシステム等が挙げられる。
【００４３】
また端末情報取得部１０が取得する端末情報には、閲覧ＵＲＬ以外にもブラウザでのＷｅｂページの閲覧に関する各種情報が含まれてよい。これらの情報には、例えば、システム利用者のユーザＩＤ、ブラウザＩＤ、Ｗｅｂページの閲覧開始時刻、Ｗｅｂページの閲覧終了時刻、あるいは、リンクを辿って２以上のＷｅｂページを閲覧した際の「移動元Ｗｅｂページ」や「移動先Ｗｅｂページ」などの移行情報などが挙げられる。
さらに、端末情報には、特定のＷｅｂページにおいて、ユーザが入力した検索キーワード等の入力情報が含まれてよい。
【００４４】
ユーザＩＤとはユーザを識別するための情報を示し、例えば、クライアント端末４へのログイン時のＩＤや、サービス単位又はソフトウェア単位で割り当てられるＩＤなどが挙げられる。ブラウザＩＤも同様に、ブラウザを識別するための情報であり、例えば、これらの情報は予めブラウザプログラムやツールバープログラムに記録されている製品ＩＤなどを利用することで取得することができる。
そして、これら識別情報を利用することでクライアント端末４を識別することができるので、クライアント端末４（ユーザ）単位での閲覧情報の管理、分析を行うことができる。なお、これらＩＤ情報の保持は、例えば、端末側情報取得装置７自身が保持する方法や、ブラウザが有するｃｏｏｋｉｅ機能を利用する方法等、適宜な方法で行われる。
【００４５】
閲覧開始時刻とは、ブラウザにてＷｅｂ上のＷｅｂページにアクセスした時刻、あるいはそのアクセスによってブラウザにＷｅｂページが取得された時刻や、表示された時刻などをいう。具体的に説明すると、当該時間は、例えば、ブラウザにてリクエストを行ったリソースのロード完了を検出した時刻や、ＷｅｂサーバがＨＴＴＰステータスコード（例えば、「２００：ＯＫ」と記述されるコード）等の信号を応答した時刻等が挙げられる。
【００４６】
閲覧終了時刻とは、ブラウザにてＷｅｂページの表示を終了した時刻をいい、例えば、ブラウザのＵＩウィンドウがクローズした時刻や、当該ウィンドウがアクティブでなくなった時刻、ウィンドウ領域内からマウスポインタが検出されなくなった時刻（マウスポインタがウィンドウ領域外へ移動した時刻）等が挙げられる。また、一定時間の操作がないためクライアント端末４のＯＳが自動的にログオフ処理を行ったり、スクリーンセーバ等が起動したりした場合には、それらが行われた時刻を閲覧終了時刻としてもよい。
【００４７】
移行情報とは、２以上のＷｅｂページを連続で閲覧した際の「移動元Ｗｅｂページ」と「移動先Ｗｅｂページ」を示す情報のことであり、例えば、ハイパーリンクのクリックによる移行（遷移）の他、ブラウザやツールバーのＵＲＬ入力欄に連続で入力された２以上のＵＲＬを「移動先」、「移動元」とする移行情報などが挙げられる。
【００４８】
端末情報送信部１１は、取得した端末情報を所定の検索装置２に送信する機能を有する。具体的には、当該端末情報を、クライアント端末の通信Ｉ／Ｆを使用し通信回線等を介して、所定の検索装置２（サーバ装置）に自動送信する機能を有する。
なお、端末情報の送信先となる所定の検索装置２の送信先アドレスは、例えば端末側情報取得装置７のプログラム内に予め記述されることで特定する方法などが挙げられる。
また、この端末情報送信部１１から端末情報が送信されるタイミングは、適宜のタイミングに設定可能である。例えば、ブラウザにて表示されているＷｅｂページが切換わるごとに送信するといったタイミングや、一定の時間、又は時刻が到来した際にバッチ処理で送信するタイミング、あるいはツールバー起動時または終了時に送信するタイミングなどが挙げられる。
【００４９】
このように、各クライアント端末４でのブラウザ５を介したＷｅｂページの出力（表示）に対する端末情報が、端末側情報取得装置７によって取得され、検索装置２に送信される。そして、検索装置２で当該端末情報が収集されることにより、クライアント端末４で閲覧している、又は閲覧されたＷｅｂページが特定できる。つまり、各クライアント端末４のブラウジング（閲覧）履歴を容易に把握することができる、
【００５０】
次に検索装置２の機能的構成を説明する。
【００５１】
検索装置２は、サーバ装置であって、検索用データベース３、情報収集部１２、検索実行部１３、検索結果出力部１５を有している。
【００５２】
検索用データベース３は、クライアント端末４から送信される端末情報を受信、管理、蓄積する機能を有するデータベースである。
【００５３】
情報収集部１２は、上記したように、ＷＷＷ上を巡回し、Ｗｅｂページの構造や内容に関する情報を取得し、取得した内容に基づいてインデックスファイルを作成することができる。また、作成したインデックスファイルを検索用データベース３に格納、保存することができる。
【００５４】
検索実行部１３は、いずれかのクライアント端末４で検索が実行された時に、ユーザからの検索キーワード等に基づいて、検索用データベース３に格納された情報を参照し、検索を実行する。具体的には、検索用データベース３を参照することにより、検索対象となるＷｅｂページを特定し、加えて特定した各Ｗｅｂページを出力している端末数を特定する。そして、詳しくは後述するが、これらの情報に基づいて形成されるランク値演算用行列の固有値を算出し、算出した固有値を検索対象となる各Ｗｅｂページのランク値（重要度の値）とする。またさらに、取得したランク値を用いて検索結果となるＷｅｂの並び替えを実行する。
【００５５】
検索結果出力部１５は、検索用データベース３から抽出し、並び替えを実行した検索結果をクライアント端末４のブラウザ５に表示する機能を有する。具体的には、クライアント端末の送信先アドレスを適宜の方法で取得する。ここで、適宜の方法とは、検索クエリと同時に受信する方法や、ユーザＩＤとあらかじめ登録しておいたＩＰアドレスを照合する方法等がある。そして、端末側情報取得装置７を介して、特定したクライアント端末４のブラウザ５上で検索結果画面を表示する。
【００５６】
次に、本実施形態における、情報検索システム１のハードウェア的構成について説明する。
図３は上記した機能的な各構成要件を、ハードウェアとして実現した際の、情報検索システム１における構成の一例を表わす概略図である。この図を利用して、本実施形態の検索システム１におけるそれぞれのハードウェア構成の働きについて説明する。図３にあるように、本実施形態の情報検索システム１のハードウェア構成は、クライアント端末４に組み込まれた端末側情報取得装置７と、サーバ装置としてネットワーク上に配置されている検索装置２により構成される。
【００５７】
端末側情報取得装置７と検索装置２は電気通信回線を介して相互に接続され、情報の送受信を行う。なお、電気通信回線はインターネットを含む。
【００５８】
端末側情報取得装置７においては、端末情報取得部１０を実現し、またその他各種演算処理を行うＣＰＵ（中央演算装置）とＲＡＭや、端末情報送信部１１である通信Ｉ／Ｆを備える。またキーボード、マウス等の入力装置であるＵＩ（Ｕｓｅｒ  Ｉｎｔｅｒｆａｃｅ）や、ブラウザプログラムにて処理されたリソースを表示するためのＶＲＡＭや、ディスプレイなどの表示装置も備える。そしてそれらがシステムバスなどのデータ通信経路によって相互に接続され、情報の送受信や処理を行う。
【００５９】
端末側情報取得装置７のＲＡＭ上には、ブラウザプログラムと、プラグインプログラムとが格納されており、これらプログラムに従い端末情報の取得や送信処理やその他処理に係るＣＰＵの各種演算処理が実行される。また上記プラグインプログラムによって、ＲＡＭ上の所定のアドレスには閲覧ＵＲＬやユーザＩＤ等の端末情報を格納する領域が確保されている。
【００６０】
一方、検索装置２においては、各種演算処理を行うＣＰＵと、ＲＡＭと、通信Ｉ／Ｆと、大量の端末情報等を蓄積するためのハードディスクなどの外部記憶装置とを有している。そしてそれらがシステムバスなどのデータ通信経路によって相互に接続され、情報の送受信や処理を行う。
【００６１】
また検索装置２のＲＡＭ上には、検索実行部や検索結果出力部の各機能を実現するプログラムやデータベース管理プログラム（図示せず）等の情報検索システム１の機能を実現する各プログラムが格納されており、当該プログラムに従い端末情報の管理処理やその他処理に係るＣＰＵの各種演算処理が実行される。
【００６２】
ここで、端末側情報取得装置７では、ユーザのＵＩを介した操作入力を受け付け、ＲＡＭ上のブラウザプログラムおよびプラグインプログラムに従い以下のような処理が実行される。
【００６３】
例えば、ＵＩを介したブラウザ操作によってＷｅｂページへのアクセス指示が入力されると、そのアクセス指示で指定されたＷｅｂページのＵＲＬがＲＡＭの所定アドレスに格納される。すると、ブラウザプログラムに従い指定されたＵＲＬに対して、ＨＴＴＰリクエストがクライアント端末４から検索装置２へ送信される。そして、そのＨＴＴＰリクエストに対するレスポンスをアクセスリソースのコンテンツとして通信Ｉ／Ｆにて該クライアント端末４が受信する。続いてクライアント端末４が受信したコンテンツに含まれるＨＴＭＬファイル、イメージファイルなどを、ブラウザ５が有するＨＴＭＬレンダリングエンジンなどに従ったＣＰＵの演算処理よってレンダリング処理する。そしてその処理結果がＶＲＡＭに転送され、表示装置上にＷｅｂコンテンツが表示される。それから、ユーザは表示された当該ＷＷＷ上のＷｅｂページなどのリソースを閲覧する。
【００６４】
また、それとともに前記ブラウザでのアクセス指示入力に応じてプラグインプログラムは次の処理を実行する。即ち、ＲＡＭの所定アドレスに格納されたＵＲＬを端末情報として、前述のような所定の各タイミングで通信Ｉ／Ｆから検索装置２に自動送信する、という具合である。
【００６５】
これに対して、検索装置２では、通信Ｉ／Ｆにて各クライアント端末４の端末側情報取得装置７から送信されてきた端末情報を受信し、ＲＡＭの所定アドレス等に格納する。そして、検索装置２のプログラムにしたがって、例えば、端末情報に含まれるＵＲＬやユーザＩＤなどをパラメータとして、ＣＰＵの演算処理によって検索用データベース３のファイルを作成又は、作成されている検索用データベース３のファイルに追記し、ＨＤＤ等の外部記憶装置に格納する、という具合である。
【００６６】
また、ＵＩによるブラウザ操作によって、検索エンジン（検索用Ｗｅｂページ）にアクセスし、検索クエリの入力、送信を行なった場合や、ツールバーに検索クエリの入力、送信を行った場合のように、クライアント端末４にて検索が実行された場合について説明する。その際、検索装置２は通信Ｉ／Ｆにて該検索クエリを含むＨＴＴＰリクエストを受信し、ＲＡＭの所定アドレスに格納する。すると、検索装置２では検索サーバプログラムに従い以下の処理を実行する。即ち、ＲＡＭに格納されている検索クエリをキーとして、外部記憶装置に保存されている、インデックスファイルデータベースの中から、検索クエリの条件を満たすＷｅｂページを抽出する。続いて、ＣＰＵの比較演算処理によって、抽出されたＷｅｂページの情報と外部記憶装置に保存されている端末情報（端末側情報取得装置７から送信された端末情報）とを比較演算することにより、抽出されたＷｅｂページを出力している端末を特定する。そして、詳しくは後述するが、抽出されたＷｅｂページのリンク構造と、抽出されたＷｅｂページが出力された端末の情報からランク値演算用行列を設定する。さらにまた、設定されたランク値演算用行列の固有値を規定のアルゴリズムに基づいて算出することにより、抽出された各Ｗｅｂページのランク値を取得し、ＣＰＵの比較演算処理によって、抽出されたＷｅｂページをランク値の高い順に並び替える。加えて、検索装置２は、Ｗｅｂページを並べて箇条形式とした検索結果をＣＰＵの演算処理によって生成し、通信Ｉ／Ｆにより検索クエリの送信元のクライアント端末４のブラウザ５に対して送信する、と言う具合である。
【００６７】
次に、本実施形態の情報検索システム１の検索実行時の処理の流れについて説明する。
図４は、本実施形態の情報検索システム１の検索実行時の処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００６８】
いずれかのクライアント端末４で検索が実行され（ステップ１０１でＹｅｓの場合）、クライアント端末４から検索装置２に検索クエリが送信されると、検索クエリを受信した検索装置２が検索用データベース３から検索クエリの条件を満たすＷｅｂページを抽出する（ステップ１０２）。即ち、検索クエリをキーワードにして該当するインデックスファイルを検索する。
【００６９】
さらに検索装置２は、抽出したＷｅｂページのデータと、検索用データベース３に格納された端末情報とを比較することにより、抽出したＷｅｂページを出力している端末を特定する（ステップ１０３）。即ち、各クライアント端末４から送信された、ブラウザ５を介したＷｅｂページの出力、又は過去の出力に係る情報を参照することにより、抽出したＷｅｂページを出力している端末、又は出力した端末を特定する。
【００７０】
次に、検索装置２は、検索クエリの条件を満たすＷｅｂページに係る情報（ステップ１０２で取得した情報）と、抽出したＷｅｂページを出力している端末に係る情報（ステップ１０３で取得した情報）からランク値演算用行列を設定する（ステップ１０４）。本発明の特徴的構成であるところのランク値演算用行列の設定処理について、図５，６を参照しつつ以下で詳細に説明する。
【００７１】
ランク値演算用行列は、ネットワーク上で公開された複数のＷｅｂページとユーザからなるリンク構造に対応して設定するものであり、その各「列」は、「列」に対応するＷｅｂページから他のＷｅｂページへのリンクを示すものとなっている。即ち、「列」に属する各要素がそれぞれ別箇の他のＷｅｂページへのリンクを示している。さらにまた、その各「行」は、他のＷｅｂページから「行」に対応するＷｅｂページへのリンクを示すものとなっている。即ち、「行」に属する各要素がそれぞれ別箇の他のＷｅｂページから「行」に対応するＷｅｂページへのリンクを示している。
具体的に説明すると、例えば、図６で示されるようなランク値演算用行列Ｐであれば、その行列Ｐの各要素は、行列の上部に示したＷｅｂページＡ，Ｂ，Ｃ，Ｄ及びユーザ（Ｗｅｂページの閲覧者）Ｅ，Ｆ，Ｇ，Ｈから、行列の左部に表示したＷｅｂページＡ，Ｂ，Ｃ，Ｄ及びユーザＥ，Ｆ，Ｇ，Ｈに対するリンク又はユーザによるＷｅｂページの閲覧の状況を示す数値である。
即ち、図６に示す正方行列（ランク値演算用行列Ｐ）は、検索対象となるＷｅｂページがリンク先となっているＷｅｂページと、検索対象となるＷｅｂページがリンクしているＷｅｂページに対して現に、あるいは一定期間内に接続された端末との関連を示すものである。
【００７２】
ここで、ランク値演算用行列についてモデルを用いて具体的に説明する。なお、本発明のランク値演算用行列がモデルのものに限らないことは当然である。
図５で示されるように、４つのＷｅｂページＡ，Ｂ，Ｃ，ＤがＷｅｂサーバ上に保持され、インターネットやＬＡＮ等のネットワークに接続されたコンピュータでブラウザを介して閲覧可能となっているものとする。即ち、４つのＷｅｂページＡ，Ｂ，Ｃ，Ｄがネットワーク上に公開された状態となっているものとする。ここで、１つめのＷｅｂページＡは、ＷｅｂページＢ，ＷｅｂページＣにそれぞれリンクを張った状態となっている。
ここで、「リンクを張った状態」とは、リンク元となる特定のＷｅｂページにリンク先となる他のＷｅｂページのＵＲＬが関連付けられており、例えば、リンク元のＷｅｂページ上の所定の部分をクリックするといった所定の操作によって、リンク先のＷｅｂページがブラウザで表示される構造となっている状態とする。
【００７３】
さらに、２つめのＷｅｂページＢは、ＷｅｂページＤにリンクを張った状態となっている。３つめのＷｅｂページＣは、ＷｅｂページＤにリンクを張った状態となっている。４つめのＷｅｂページＤは、ＷｅｂページＡ，ＷｅｂページＣにそれぞれリンクを張った状態となっている。
【００７４】
換言すると、１つ目のＷｅｂページＡは、４つ目のＷｅｂページＤにリンクを張られた状態となっている。
ここで、「リンクを張られた状態」とは、リンク元となる他のＷｅｂページが、リンク先となる特定のＷｅｂページにリンクを張った状態であることとする。即ち、他のＷｅｂページに特定のＷｅｂページのＵＲＬが関連付けられており、他のＷｅｂページで所定の操作を行うことによって、特定のＷｅｂページがブラウザで表示される構造となっている状態とする。
【００７５】
同様に、２つめのＷｅｂページＢは、ＷｅｂページＡにリンクを張られた状態となっている。３つめのＷｅｂページＣは、ＷｅｂページＡとＷｅｂページＤにそれぞれリンクを張られた状態となっている。４つめのＷｅｂページＤは、ＷｅｂページＢ，ＷｅｂページＣにそれぞれリンクを張られた状態となっている。
【００７６】
ここで、ＷｅｂページＡをユーザＥが閲覧しているものとする。即ち、閲覧者Ｅが使用しているクライアント端末４ａのブラウザ５が、インターネットやＬＡＮ等のネットワークを介してＷｅｂページＡを保持しているＷｅｂサーバからデータを取得し、ＷｅｂページＡを閲覧可能な状態に出力しているものとする。
【００７７】
また同様に、ＷｅｂページＢをユーザＦ，Ｇ，Ｈがそれぞれ閲覧しているものとする。即ち、クライアント端末４ｂ，４ｃ，４ｄの各ブラウザ５が、ＷｅｂページＢを閲覧可能な状態に出力しているものとする。
【００７８】
以上説明した状況において、いずれかのクライアント端末４で検索が実行され、ＷｅｂページＡ，Ｂ，Ｃ，Ｄがいずれも検索クエリの条件を満たすＷｅｂページであったとする。このとき、検索装置２は、ＷｅｂページＡ，Ｂ，Ｃ，Ｄを出力しているクライアント端末４ａ，４ｂ，４ｃ，４ｄを特定し、ユーザＥ，Ｆ，Ｇ，ＨがＷｅｂページＡ，Ｂ，Ｃ，Ｄを閲覧しているものとして、図６で示されるようなランク値演算用行列Ｐを設定する。
【００７９】
ランク値演算用行列Ｐの各「列」要素に注目すると、左側部分ＲＬはＷｅｂページＡ，Ｂ，Ｃ，Ｄに関する要素となっており、右側部分ＲＲはユーザＥ，Ｆ，Ｇ，Ｈに関する要素となっている。即ち、複数のＷｅｂページＡ，Ｂ，Ｃ，Ｄに関する要素から構成される要素群と、複数のユーザＥ，Ｆ，Ｇ，Ｈに関する要素から構成される要素群とが隣合わせに配されている。
【００８０】
このように本実施形態の検索装置２は、ユーザＥ，Ｆ，Ｇ，Ｈを仮想のＷｅｂページＥ，Ｆ，Ｇ，Ｈとしてランク値演算用行列Ｐを設定している。即ち、「特定のユーザによる特定のＷｅｂページの閲覧」を「仮想のＷｅｂページと特定のＷｅｂページの間で互いにリンクが張られている」状態としてランク値演算用行列Ｐに反映させている。換言すると、図６に示す正方行列では、ＷｅｂページＡ，Ｂ，Ｃ，Ｄと、その閲覧者Ｅ，Ｆ，Ｇ，Ｈを同格に扱い、行列の各要素に反映させている。
【００８１】
詳説すると、上記したようにＷｅｂページＡをユーザＥが閲覧しているとする（図５参照）。このとき、検索装置２は、ＷｅｂページＡ，Ｂ，Ｃ，Ｄからなるリンク構造に、実際には存在しない仮想のＷｅｂページＥがあるものとし、ＷｅｂページＡ，Ｂ，Ｃ，Ｄ，Ｅからなるリンク構造であるものとする。そして、ＷｅｂページＡ，Ｂ，Ｃ，Ｄに対応する「行」及び「列」に加えて、仮想ＷｅｂページＥに対応する新たな「行」と「列」とを追加してランク値演算用行列Ｐを設定する。換言すると、ユーザＥが使用するクライアント端末４ａでＷｅｂページＡが出力されたことを条件に、ランク値演算用行列Ｐに新たな「行」と「列」とを追加する。
【００８２】
したがって、上記のように４人のユーザＥ，Ｆ，Ｇ，Ｈが、それぞれ検索対象となるＷｅｂページＡ，Ｂ，Ｃ，Ｄのいずれかを閲覧している場合、ＷｅｂページＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈからなるリンク構造であるものとして、仮想ＷｅｂページＥ，Ｆ，Ｇ，Ｈに対応する新たな「行」と「列」を４つずつ追加してランク値演算用行列Ｐを設定する。即ち、検索対象となるＷｅｂページの数と、検索対象となるＷｅｂページを出力している端末の数との合計がランク値演算用行列Ｐの行数及び列数となる。
【００８３】
ここで、ランク値演算用行列Ｐの各「列」は、上記した検索対象となるＷｅｂページ、又は検索対象となるＷｅｂページの出力を条件にして定義される仮想のＷｅｂページに対応している。そして、「列」に属する各要素は、対応するＷｅｂページ又は仮想のＷｅｂページ（以下単にＷｅｂページとも称す）から、他のページへのリンクを示すものとなっている。具体的には、「列」に属する要素Ｐ（ｉ，ｊ）は、下記式（１）：
Ｐ（ｉ，ｊ）＝  αＸ／Ｙ  ・・・（１）
α  ＝０以外の数
Ｘ  ＝  列「ｊ」に対応するＷｅｂページから行「ｉ」に対応するＷｅｂページへのリンクの数、又は、列「ｊ」に対応するＷｅｂページの行「ｉ」に対応する出力端末での表示数、又は、列「ｊ」に対応する出力端末での行「ｉ」に対応するＷｅｂページの表示数、又は０
Ｙ  ＝  列「ｊ」に対応するＷｅｂページの出力端末での表示数と、列「ｊ」に対応するＷｅｂページに形成されているリンク数の総和
の関係を満たすものである。
即ち、Ｗｅｂページがリンクしているリンク先の数に基づく値をＡとし、端末が現にあるいは一定期間内に接続したＷｅｂページの数をＢとしたとき、ランク値演算用行列Ｐの各要素は、Ａ／（Ａ＋Ｂ）、Ｂ／（Ａ＋Ｂ）あるいはこれらに系数αが掛けられた値となっている。
【００８４】
ここで、上記したように、本実施形態の検索装置２は、ユーザＥが使用するクライアント端末４ａでＷｅｂページＡが出力されていることを条件に、ＷｅｂページＡから仮想のＷｅｂページＥへリンクが張られ、仮想のＷｅｂページＥからＷｅｂページＡへリンクが張られているものとして、ランク値演算用行列Ｐを設定する。換言すると、ユーザＥによるＷｅｂページＡの閲覧を、実際には存在しないＷｅｂページＥとＷｅｂページＡの相互リンク（互いにリンクを張っている状態）として、ランク値演算用行列Ｐに反映させる。
【００８５】
つまり、図５で示されるように、特定のＷｅｂページＡから他の２つのＷｅｂページＢ，Ｃにそれぞれリンクが張られ、ユーザＥが前記特定のＷｅｂページＡを閲覧しているとする。このとき、検索装置２は、特定のＷｅｂページＡが２つのＷｅｂページＢ，Ｃに加えて、仮想のＷｅｂページＥにリンクを張っているとする。このとき、図６で示されるように、ランク値演算用行列Ｐの特定のＷｅｂページＡに対応する列（図６で最も左側の列）を形成する各要素Ｐ（ｉ，１）に注目すると、ＷｅｂページＢ，Ｃ及び、仮想のＷｅｂページＥへのリンクとそれぞれ対応する要素であるＰ（２，１），Ｐ（３，１），Ｐ（５，１）はいずれも１／３となっている。これらは、特定のＷｅｂページＡのリンクの総数が３であり、特定のＷｅｂページＡからＷｅｂページＢ，Ｃ及び、仮想のＷｅｂページＥにそれぞれ１つずつリンクが張られていることを示している。したがって、ランク値演算用行列Ｐの各「列」の要素の総和は１となっている。
【００８６】
また、ここでランク値演算用行列Ｐの各「行」要素に注目すると、上側部分ＬＨはＷｅｂページＡ，Ｂ，Ｃ，Ｄに関する要素となっており、下側部分ＬＬはユーザＥ，Ｆ，Ｇ，Ｈに関する要素となっている。即ち、複数のＷｅｂページＡ，Ｂ，Ｃ，Ｄに関する要素から構成される要素群と、複数のユーザＥ，Ｆ，Ｇ，Ｈに関する要素から構成される要素群とが上下に連続して配されている。
【００８７】
以上のことから、図６で示されるように、ランク値演算用行列Ｐは、検索対象となるＷｅｂページＡ，Ｂ，Ｃ，Ｄと上記仮想のＷｅｂページＥ，Ｆ，Ｇ，ＨとからなるＷｅｂページ群において、各ＷｅｂページＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈを頂点とし、リンクを辿ることを遷移（推移）とするものであり、さらに、Ｗｅｂページ内の各リンクから一様な確率で１つのリンクを辿ることを想定する遷移確率行列（推移確率行列）となっているといえる。
なお、ここでいう「リンクを辿る」とは、リンク元となる特定のＷｅｂページにリンク先となる他のＷｅｂページのＵＲＬが関連付けられており、例えば、リンク元のＷｅｂページ上の所定の部分をクリックするといった所定の操作によって、リンク先のＷｅｂページがブラウザで表示されることとする。そしてさらに、実際のＷｅｂページと仮想のＷｅｂページの間に定義したリンクにおいても、実際のＷｅｂページ間のリンクと同様に取り扱うものとする。
【００８８】
このとき、ランク値演算用行列Ｐに注目すると、図６で示されるように、左上に位置するエリアＥ１に属する各要素は、実際に存在するＷｅｂページＡ，Ｂ，Ｃ，Ｄの間に形成されるリンクを示している。また、右上に位置するエリアＥ２に属する各要素は、仮想のＷｅｂページＥ，Ｆ，Ｇ，Ｈのいずれかから実際に存在するＷｅｂページＡ，Ｂ，Ｃ，Ｄのいずれかへのリンクを示している。さらに、左下に位置するエリアＥ３に属する各要素は、実際に存在するＷｅｂページＡ，Ｂ，Ｃ，Ｄのいずれかから、仮想のＷｅｂページＥ，Ｆ，Ｇ，Ｈのいずれかへのリンクを示している。そして、右下に位置するエリアＥ４は、仮想のＷｅｂページＥ，Ｆ，Ｇ，Ｈの間に形成される仮想のリンクを示している。
【００８９】
このようなランク値演算用行列Ｐが設定されると、図４で示されるように、ステップ１０４からステップ１０５へ移行して、検索装置２がランク値演算用行列Ｐの固有値を算出する。つまり、遷移確率行列の各頂点であるＷｅｂページＡ，Ｂ，Ｃ，Ｄ及び仮想のＷｅｂページＥ，Ｆ，Ｇ，Ｈのそれぞれにおける遷移確率を演算する。そして、検索装置２は、算出したランク値演算用行列Ｐの固有値に基づいて検索対象となるＷｅｂページを並び替える（ステップ１０６）。
【００９０】
詳説すると、例えば、図６で示されるランク値演算用行列Ｐでは、その固有値は下記式（２）：
〔Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ〕＝〔０．４０８，０．５４４，０．４０８，０．５４４，０．１３６，０．１３６，０．１３６，０．１３６〕・・・（２）
の関係を満たしている。
したがって、図５で示されるＷｅｂページＡ，Ｂ，Ｃ，Ｄの固有値はそれぞれ０．４０８，０．５４４，０．４０８，０．５４４となる。ここで、このＷｅｂページＡ，Ｂ，Ｃ，Ｄを固有値の高い順に並べ替えるのであれば、ＷｅｂページＢ，ＷｅｂページＤ，ＷｅｂページＡ，ＷｅｂページＣの順となる。
【００９１】
そして検索装置２は、並び替えた検索対象となるＷｅｂページを検索結果としてクライアント端末４へ送信する（ステップ１０７）。
以上で情報検索システム１の検索実行時の処理の流れの説明を終了する。
【００９２】
上記した実施形態では、ランク値演算用行列Ｐを設定するとき、ユーザＥ，Ｆ，Ｇ，Ｈをいずれも画一的なユーザとして仮想のＷｅｂページＥ，Ｆ，Ｇ，Ｈを設定した。つまり、Ｗｅｂページを閲覧したユーザがいずれのユーザＥ，Ｆ，Ｇ，Ｈであっても、仮想のＷｅｂページと実在のＷｅｂページの間に定義される仮想のリンクの数は同一となっている。即ち、いずれのユーザであっても１つの仮想のＷｅｂページと１つの実在のＷｅｂページの間に１つの相互リンクが定義される構成となっている。
【００９３】
しかしながら、本発明の情報検索システムはこのような構成に限るものではない。即ち、各ユーザＥ，Ｆ，Ｇ，Ｈの間で特定項目に対する知識の深さや、検索スキル等が異なっている場合、ランク値演算用行列の設定に閲覧しているユーザＥ，Ｆ，Ｇ，Ｈの知識やスキルの違いを反映させる構成であってもよい。さらにまた、ランク値演算用行列Ｐに、検索キーワード等の出現数といったＷｅｂページＡ，Ｂ，Ｃ，Ｄの内容を反映させる構成であってもよい。
【００９４】
以下で第２の実施形態及び第３の実施形態を説明するが、特に説明がない限り、第１の実施形態における情報検索システム１と同様の部分については、同様の符号を付して重複する説明を省略する。
【００９５】
第２の実施形態では、ランク値演算用行列を設定するとき、ユーザＥ，Ｆ，Ｇ，Ｈの知識や検索スキル等の違いや、ＷｅｂページＡ，Ｂ，Ｃ，Ｄの内容の違いに応じて、ランク値演算用行列の各要素を変更することを特徴とする。
【００９６】
第２の実施形態の情報検索システム２０は、第１の実施形態と同様に、検索装置２、各クライアント端末４、そして、各クライアント端末４で動作するブラウザ５及び端末側情報取得装置７によって構成されている（図１）。
【００９７】
第２の実施形態の端末情報取得装置７は、取得した端末情報を利用することで各ユーザのユーザランク値を算出する。本明細書における、「ユーザランク値」とは、各ユーザの特定項目に対する知識の深さや、検索スキル等を基に決定される、ユーザの重要度を数値化した値を示す。算出したユーザランク値は検索用データベース３に端末情報として格納される。
【００９８】
ユーザランク値の算出方法は、例えば、上記した端末情報取得装置７が取得した端末情報と、情報収集機能（情報収集部１２）が収集したＷｅｂページの情報に基づいて、ユーザがブラウザ５を介して出力したＷｅｂページの種類や、Ｗｅｂページの閲覧時間、リンクを辿ったときの変遷履歴等に基づいて算出してもよい。
また、端末情報取得装置７をブラウザに組み込むとき、又はソフトウェアのインストール時等に、ユーザの職業や趣味等の個人情報を取得する方法がある。また、ブラウザ５に記録された頻繁に閲覧するＷｅｂページへのショートカットの情報を取得するという方法がある。即ち、検索が実行されたときに、検索対象となるＷｅｂページをユーザが閲覧しており、且つそのユーザの職業や趣味等がＷｅｂページの内容と関連していた場合、そのユーザのユーザランク値を高くするという方法である。
さらに、ユーザが、ＢＢＳ等で特定の項目と関連する質問に対して回答を行った際に、必要に応じて当該ＢＢＳ（特定のＷｅｂページ）からデータを取得する方法がある。具体的には、ユーザが行った回答に対する他のユーザの評価の情報等を必要に応じて取得する。そして、他のユーザから高い評価を得た回答を行ったユーザのユーザランク値を高くするという方法である。
そしてまた、検索キーワード、検索後に閲覧したＷｅｂページ、及び検索後にＷｅｂページを閲覧した時間、検索後のＷｅｂページからリンクしたページ等を解析することにより、ユーザの検索スキルを判定し、それを基にユーザランク値を付与するという方法が考えられる。
このような、検索内容に対する知識の深さや、検索スキル等を基にユーザを評価する方法から、適宜なものを少なくとも一つ選択し、端末情報取得装置７や情報収集部１２に情報を収集させ、検索装置２において解析処理を実行することで、ユーザランク値を決定する。
【００９９】
第２の実施形態の端末情報取得装置７では、情報収集部１２が収集した情報に基づいて、各Ｗｅｂページのリレーションランク値を算出する。本明細書における、「リレーションランク値」とは、各Ｗｅｂページの内容に特定の単語がどれだけ記載されているか、特定の単語がタイトル等の所定の箇所に記載されているか等の情報を基に決定される、Ｗｅｂページの内容と特定項目との関連性の高さを数値化した値を示す。算出したリレーションランク値は検索用データベース３に端末情報として格納される。
【０１００】
次に、本実施形態の情報検索システム１の検索実行時の処理の流れについて説明する。
いずれかのクライアント端末４で検索が実行されると、第１の実施形態と同様の手順によって、検索装置２がランク値演算用行列を設定する。
【０１０１】
ここで、本実施形態では、検索によって抽出された各ＷｅｂページＡ，Ｂ，Ｃ，Ｄのリレーションランク値と、抽出された各Ｗｅｂページを閲覧しているユーザＥ，Ｆ，Ｇ，Ｈのユーザランク値を参照してランク値演算用行列の各要素の値を変更する。
【０１０２】
モデルを用いて具体的に説明すると、図５で示されるモデルにおいて、ユーザＦがユーザＧ，Ｈに比べてユーザランクが高いユーザであったとする。このとき、図６で示される
ランク値演算用行列Ｐの要素の値を、図７で示されるランク値演算用行列Ｐのように変更する。即ち、Ｐ（４，２），Ｐ（７，２），Ｐ（８，２）の値をそれぞれ１／４から１／５に変更し、Ｐ（６，２）の値を１／４から２／５に変更している。このことで、ＷｅｂページＢから仮想のＷｅｂページＦへのリンクの重要度を、ＷｅｂページＢから仮想のＷｅｂページＧ，Ｈそれぞれへの各リンクの重要度より高くしている。
【０１０３】
このように、作成したランク値演算用行列の各要素の値を、ユーザランク値とリレーションランク値のいずれか一方又は両方の値に基づき、適宜変更することにより、実在するＷｅｂページＡ，Ｂ，Ｃ，Ｄ、やユーザＥ，Ｆ，Ｇ，Ｈによって定義される仮想のＷｅｂページＥ，Ｆ，Ｇ，Ｈの重要度をランク値演算用行列に反映させる。なお、このとき、ランク値演算用行列の各要素の値を変更しても、ランク値演算用行列Ｐの各「列」の要素の総和は１となる。したがって、図６で示されるランク値演算用行列Ｐから要素Ｐ（６，２）値を変更するとき、１／４から（１＋α）／（４＋α）（αは０でない数）のように変更される。
【０１０４】
さらに、必要に応じて各要素の値の変更を行ったランク値演算用行列の固有値を算出する。即ち、遷移確率行列の各要素の値を変更してから演算することで、遷移確率行列の各頂点であるＷｅｂページＡ，Ｂ，Ｃ，Ｄ及び仮想のＷｅｂページＥ，Ｆ，Ｇ，Ｈのそれぞれにおける遷移確率に基づく遷移傾向を推定する演算を実施する。そして、算出した固有値に基づいて抽出したＷｅｂページを並び替える。
【０１０５】
また、検索装置２は、並び替えた検索対象となるＷｅｂページを検索結果としてクライアント端末４へ送信する。以上で本実施形態の情報検索システム１の検索実行時の処理の流れの説明を終了する。
【０１０６】
次に第３の実施形態について説明する。
第３の実施形態では、ランク値演算用行列を設定して固有値を算出した後、各固有値あるいは行列の要素に対してユーザランク値やリレーションランク値に基づく値を付加することを特徴とする。
詳説すると、第１の実施形態又は第２の実施形態と同様の手順により、ランク値演算用行列を設定し、固有値を算出する。そして、算出した各固有値を変更し、変更された固有値でＷｅｂページの並び替えを実施する。
【０１０７】
例えば、算出されたＷｅｂページＡ，Ｂ，Ｃ，Ｄの固有値が、それぞれ０．４０８，０．５４４，０．４０８，０．５４４であったとする。そして、このとき、ＷｅｂページＡをユーザランク値の高いユーザが閲覧していたとする。すると、検索装置２は、ＷｅｂページＡの固有値に所定の値を加えて０．６０８とする。そして、変更したＷｅｂページＡ，Ｂ，Ｃ，Ｄに対応する固有値０．６０８，０．５４４，０．４０８，０．５４４に基づいてＷｅｂページＡ，Ｂ，Ｃ，Ｄの並び替えを実施する。このように、ユーザランク値の高いユーザが閲覧しているＷｅｂページやリレーションランク値の高いＷｅｂページに対応する固有値を変更したのち、Ｗｅｂページの並び替えを実施する。なお、上記した例では、ユーザランク値の高いユーザが閲覧しているＷｅｂページやリレーションランク値の高いＷｅｂページに対応する固有値に値を付与する例を示したが、固有値の変更方法はこれに限るものではない。例えば、リレーションランク値の低いＷｅｂページに対応する固有値の値を差し引いてもよい。固有値の変更は、ユーザランク値又はリレーションランク値に応じて適宜変更してよい。
【０１０８】
上記した各実施形態では、ランク値演算用行列Ｐは、検索対象となるＷｅｂページＡ，Ｂ，Ｃ，Ｄと上記仮想のＷｅｂページＥ，Ｆ，Ｇ，ＨとからなるＷｅｂページ群において、各ＷｅｂページＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈを頂点とする遷移確率行列なっている。したがって、このランク値演算用行列Ｐの設定は、例えば、各ＷｅｂページＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈを頂点とする隣接行列を作成し、作成した隣接行列を基に遷移確率行列を導出してもよい。ランク値演算用行列Ｐの設定するときの導出方法は、適宜変更してよい。
【０１０９】
上記した各実施形態では、検索が実行されたとき、検索クエリの条件を満たすＷｅｂページを抽出し、抽出したＷｅｂページを閲覧しているユーザを特定して、抽出したＷｅｂページとそれを閲覧しているユーザとに対応するランク値演算用行列Ｐを設定した。しかしながら、本発明の検索システムの検索実行時の処理はこれに限るものではない。
例えば、ネットワーク上の全てのＷｅｂページとそれを閲覧しているユーザとに対応するランク値演算用行列Ｐ２を予め導出しておき、検索が実行された場合に、予め導出しておいたランク値演算用行列Ｐ２から、「行」の要素や「列」の要素から必要な要素を抜き出してランク値演算用行列Ｐを設定してもいい。即ち、予め導出しておいたランク値演算用行列Ｐ２から、必要な「行」の要素や「列」の要素を抜き出し、組み合わせることによって、検索クエリの条件を満たすＷｅｂページと、それを閲覧しているユーザとに対応するランク値演算用行列Ｐを設定してもよい。
【０１１０】
また同様に、特定の条件を満たすＷｅｂページと、それを閲覧しているユーザとに対応するランク値演算用行列Ｐ３を予め導出しておき、検索が実行された場合に、予め導出しておいたランク値演算用行列Ｐ３から、「行」の要素や「列」の要素から必要な要素を抜き出してランク値演算用行列Ｐを設定してもいい。
【０１１１】
上記した各実施形態では、ランク値演算用行列の行要素と列要素において、ＷｅｂページＡ，Ｂ，Ｃ，Ｄに対応する要素群とユーザＥ，Ｆ，Ｇ，Ｈに対応する要素群とが隣接して形成されるランク値演算用行列を例に挙げて説明したが、本発明のランク値演算用行列はこれに限るものではない。例えば、ランク値演算用行列の行要素と列要素の順番は適宜入れ替わってもよい。また、説明の便宜上、ランク値演算用行列を行列の書式で表しているが、実際に検索システムが演算する際の行列の取り扱いは適宜設定してよい。つまり、行列を形成する各要素、又は行列を形成する各要素の内で演算に必要な要素のみを記憶保持して、必要な計算を実行してもよい。必ずしも、上記したような行列の形状で取り扱わなくてもよい。
【０１１２】
上記した各実施形態では、検索が実行されたとき、端末側情報取得装置７が予め取得した端末情報と、情報収集部１２が予め取得したＷｅｂページの構造に係る情報とを検索用データベース３から取得してランク値演算用行列Ｐを設定したが、ランク値演算用行列の設定方法はこれに限るものではない。例えば、検索が実行されたとき、検索装置２がクライアント端末４から、Ｗｅｂページの閲覧に係る情報を取得する構成であってもよい。また、取得した情報をデータベースに保持させずにランク値演算用行列の設定に使用してもよい。即ち、クライアント端末４から検索装置２への端末情報の送信は、適時実施してもよい。そして、情報のデータベースへの格納は、適時実施してもよく、場合によっては実施しなくてもよい。
【０１１３】
上記した各実施形態では、Ｗｅｂページを固有値の高い順に並び替えたが、本発明はこれに限らず、例えば、Ｗｅｂページを固有値の低い順に並び替えてもよい。しかしながら、Ｗｅｂページを固有値の高い順に並び替える方法によると、検索実行時に話題性の高いＷｅｂページ（例えば、多数のクライアント端末４で出力されたＷｅｂページ）が上位に表示されるため、望ましい。
【０１１４】
また、上記した各実施形態では、検索結果となるＷｅｂページを並び替えるとき、Ｗｅｂページの固有値が同じ場合、閲覧者が多いページを上位に表示している。しかしながら、本発明の検索システムはこれに限るものではなく、例えば、Ｗｅｂページの固有値が同じだった場合、閲覧者が少ないページを上位に表示してもよい。
【０１１５】
上記した各実施形態では、図３に示すように、検索用データベース３及びクライアント端末４から送信された情報を受信、管理する機能が検索装置２に含まれる構成を例に挙げているが、本発明の検索システム１はこれに限定されるものではない。例えば、検索用データベース３をネットワーク上の別途のサーバ装置に設けておき、検索装置２が検索を実行する際に、当該サーバの検索用データベース３から情報を取得するという構成でもよい。即ち、システム全体で機能を実現できればよく、設置するサーバの数及び各機能（プログラム）、データベースの配置は、サーバの能力等により適宜変更可能である。
【０１１６】
なお、上記した各実施形態のプログラム、及びシステムは、ＣＤ−ＲＯＭ等の光学ディスク、磁気ディスク、半導体メモリなどの各種の記録媒体を通じて、又は電気通信網などを介してダウンロードすることにより、コンピュータにインストール又はロードすることができる。
【実施例】
【０１１７】
ところで、上記したランク値演算用行列の固有値を求める際の演算は、適宜のハードウェア構成、適宜の演算アルゴリズムで行ってよい。しかし、より高速にランク値演算用行列の固有値を求めるべく、下記の検証を実施した。本発明の情報検索システムは、下記の検証を参考にハードウェア構成及び演算アルゴリズムを選択してもよい。
【０１１８】
検証を実施するに当たって、ＬＲ法やＱＲ法等の古典的な手法は一般的に大きな手間を要するので、固有値が等しく、元の行列よりサイズの小さい行列に変換することで計算時間を削減する「射影法」に基づく手法について検証を行った。Ｌａｎｚｃｏｓ，Ａｒｎｏｌｄｉ，Ｋｒｙｌｏｖ−Ｓｃｈｕｒ等の射影法に基づく手法は，Ｇｒａｍ−Ｓｃｈｍｉｄｔの手法をベースにした直交化のフェーズと、マルチシフトＱＲ法による固有値計算およびＳｃｈｕｒ分解のフェーズからなる手法で、分解フェーズでブロックを並べかえることで、最大固有値、最小固有値など，欲しい固有値および固有ベクトルの組から求められる手法である。そのため、最大固有値と対応する固有ベクトルのみが必要なアプリケーションでは、大幅に計算時間を削減できる可能性がある。そのため、「射影法」に基づく手法は、上記したランク値演算用行列の固有値を求める演算に適していると考えられる。
【０１１９】
これらの射影法を実装したライブラリの中で、大規模行列の計算に対応したものとしてＳＬＥＰｃがある。ＳＬＥＰｃでは、ＰＥＴＳｃ、ＢＬＡＳ、ＬＡＰＡＣＫなどの既存の数値計算ライブラリを用いて、最新の固有値計算手法を実装しており、大幅な計算時間の短縮が期待できる。ＳＬＥＰｃが用いているＰＥＴＳｃという数値計算ライブラリでは、ＯｐｅｎＭＰＩを用いてベクトルや行列の演算を複数プロセスで並列処理する機能を備えている。ＰＥＴＳｃはＣ言語で記述されており、高速に演算を行える。また、ＯｐｅｎＭＰＩはプロセス間通信方式として、共有メモリ、ＩｎｆｉｎｉＢａｎｄ、ＴＣＰ／ＩＰ等、さまざまな方式をサポートしており、内部で自動的に切り替えてくれるため、準備できる環境に応じて最適な並列化が容易に実現できる。
【０１２０】
これに対して、一般的な検索サービスでは、常に大規模な分散環境における処理を前提としてシステムを構築している。これらのミドルウェアは、ノード故障等が頻繁に発生する環境で、安定して大量のバッチ処理を実行できるという特徴を有する。しかしながら、冗長化のためのオーバヘッドも大きく、大量の通信を伴う処理では高い性能を出すことができない。
【０１２１】
つまり、中小規模の計算機環境では密結合な処理の方が高性能で処理できる可能性があるため、本検証では、ＭＰＩベースで実装されたクラスタ向けのミドルウェアも含めて調査することにした。
【０１２２】
まず、ＯｐｅｎＭＰＩで実装されたＳＬＥＰｃの性能について調査した。詳細には、本発明の情報検索システムが要求するスケーラビリティを実現するため、どの程度のリソースを要するのかを調査した。さらに具体的には、Ｗｅｂページと閲覧者をあわせて１０万エントリ程度の計算を実施する場合を想定した性能について調査した。
【０１２３】
検証における評価環境は以下の通りである。
計算機：ＰｏｗｅｒＥｄｇｅ  Ｒ４１０×２（ＤＥＬＬ社製）
ＣＰＵ：Ｉｎｔｅｌ（Ｒ）  Ｘｅｏｎ（Ｒ）  Ｌ５５２０  （２．２６ＧＨｚ，８ＭＢ  キャッシュ，  ５．８６  ＧＴ／ｓ  ＱＰＩ）  ×２  （コア数４）
メモリ：３２ＧＢ（４ＧＢ×８／２Ｒ／１０６６ＭＨｚ／ＤＤＲ３  ＲＤＩＭＭ）
ディスク：ＲＡＩＤ６（ＰＥＲＣ６ｉ），６００ＧＢ，１５，０００ＲＰＭ  ＳＡＳ
ネットワーク：Ｂｒｏａｄｃｏｍ  ＮｅｔＸｔｒｅｍｅ  ＩＩ  ＢＣＭ５７１６  １０００Ｂａｓｅ−Ｔ  ＰＣＩＥｘｐｒｅｓｓ
スイッチ：Ｃｉｓｃｏ  Ｃａｔａｌｙｓｔ  ２９６０Ｇ−８ＴＣ−Ｌ
ＯＳ：Ｕｂｕｎｔｕ  Ｌｉｎｕｘ１０．０４
ライブラリ：ＰＥＴＳｃ  ３．０．０，  ＳＬＥＰｃ  ３．０．０，ＬＡＰＡＣＫ  ３．２．１，ＢＬＡＳ  １．２
【０１２４】
性能評価では、対称行列の例としてラプラシアン行列を用い、非対称行列の例として要素間をランダムに遷移するモデルを想定して生成した遷移確率行列を用いて固有値、固有ベクトルを計算した。本実験で用いたラプラシアン行列は、図８（ａ）に示したような行列で、対角要素が２、その両脇の要素が１の行列とした。また、遷移確率行列は、三角格子の上をランダムに移動することを想定して生成した図８（ｂ）のような行列とした。本検証ではまず単一ノード内での並列処理性能について評価し、その後ＴＣＰ／ＩＰを用いて複数ノードでの評価を行なう。
【０１２５】
実機での評価の前にＳＬＥＰｃのソースコードから、Ａｒｎｏｌｄｉ，Ｋｒｙｌｏｖ−Ｓｃｈｕｒの実装について調査した。
【０１２６】
ＳＬＥＰｃで用いられているＰＥＴＳｃでは、ＯｐｅｎＭＰＩの集合通信機能を利用し、行列の１行目からｎ１行目、ｎ１＋１行目からｎ２行目など、指定した範囲で分割して、各プロセッサごとに部分行列を生成、処理する機能を実装している。直交化の計算では、各プロセスに分散配置した部分行列およびベクトルの中間計算結果をギャザ，スキャタ，レデュース等の機能で相互にやりとりする必要があるため、並列化時の通信オーバヘッドが大きくなると考えられる。
【０１２７】
対して、マルチシフトＱＲやＳｃｈｕｒ分解の処理では、注目している部分行列のみに注目して処理できるため、通信オーバヘッドは発生しないと考えられる。以上の点について、実際に性能計測して確認した。
【０１２８】
ＰＥＴＳｃでは、−ｌｏｇ  ｓｕｍｍａｒｙというオプションにより、プログラムの実行時間、事前設定した箇所の呼び出し回数、実行時間などを分析する機能を提供している。下記の実験では、この−ｌｏｇ  ｓｕｍｍａｒｙの機能を用いて性能計測した。
【０１２９】
またさらに、ＭＰＩにおけるオールギャザ、オールレデュース等の集合通信では、プロセッサ数が偶数であることを想定しており、奇数の場合余ったノードの通信は効率的に行えないため、集合通信を多用する計算では偶数個のプロセッサを利用するのが良いと考えられる。実際に奇数ｎ個のプロセッサを利用した場合、偶数ｎ１個のプロセッサ数と同等程度の性能しか得られなかった。そのため、以下の評価では偶数個のプロセッサの性能について評価した。
【０１３０】
計算対象となる行列の値により実際に並列に実行されるコードが異なってくるので，ソースコードから直接並列化率を求めることはできないが、性能測定結果から指定したパラメータでの並列化率を算出し、ライブラリの性能を評価できると考えられる。以下で求めた並列化率は指定したパラメータでの並列化率である。また、ＳＬＥＰｃでは、求める固有値の許容誤差を指定することで、計算結果が指定した誤差内に収まるまで、反復計算を継続する。以下の実験では許容誤差を１０の−７乗として計算した。
【０１３１】
まず、ラプラシアン行列での計算時間について調査する。
【０１３２】
調査に当たって、１０万×１０万のサイズのラプラシアン行列の固有値計算時間を測定した。このとき、まず、同じ反復回数での処理時間を比較した。反復回数を１２５００回程度に制限すると、このサイズの行列ではどの手法もまだ固有値が収束しないので、同じ繰り返し回数だけ計算される。単一プロセッサで計算したときの処理時間をＴ１、プロセッサ数ｎで計算したときの処理時間をＴｎとしたとき，プロセッサ数を変化させた場合の処理時間比Ｔ１＝Ｔｎは図９のようになった。
【０１３３】
利用したハードウェアはノードあたり８コアのプロセッサが利用でき、さらにＩｎｔｅｌのＨｙｐｅｒ  Ｔｈｒｅａｄｉｎｇ技術により、仮想的に１６コアのプロセッサが利用できる。しかし、図９に示すように、プロセッサ数が８から９に増えるところで性能が低下している。そこでＨｙｐｅｒ  Ｔｈｒｅａｄｉｎｇ機能をＯＦＦにして各手法の処理時間をプロセス数８まで測定したところ、プロセッサ数８まではほぼ同様な変化を示した。そのため、複数ＣＰＵの利用ではなくＨｙｐｅｒ  Ｔｈｒｅａｄｉｎｇが原因で性能低下していると考えられる。Ｕｂｕｎｔｕの実装が影響していることも考えられるが、詳細な原因までは調査できていない。このことを受け、以下の実験ではＨｙｐｅｒ  Ｔｈｒｅａｄｉｎｇ機能をＯＦＦにして評価を実施した。
【０１３４】
プロセッサ数８までの結果では、アムダールの法則が示すとおりプロセッサ数の増加に対して処理時間比の伸びが鈍化している。プログラム中で並列化されている部分の割合(並列化率:Ｐａｒａｌｌｅｌ  Ｐｏｒｔｉｏｎ)をｒ（０＜＝ｒ＜＝１）とし、プロセッサ数をｎとすると、オーバヘッドを無視した並列処理部分の処理時間はｒＴ１＝ｎ、逐次処理部分の処理時間は（１―ｒ）Ｔ１なので、処理時間比Ｓｐｅｅｄｕｐは下記〔数１〕のようになっている。
【０１３５】
【数１】
2013025421.tif 000003
【０１３６】
計測した値から最小二乗法でｒを推定すると、Ｌａｎｚｃｏｓ，Ａｒｎｏｌｄｉ，Ｋｒｙｌｏｖ−Ｓｃｈｕｒでそれぞれ、およそ０．９６５３（９６．５３％），０．９７２０（９７．２０％）０．９５８３（９５．８３％）という値になった。なお、図９中の直線は理想的な性能，曲線は推定した曲線を表す。オーバヘッドを無視した式で推定しているため、観測値と推定曲線にはずれがある。８プロセッサでの計測値が近似曲線よりも下に来ているので、１０プロセッサ以上の性能を測定して再計算すれば、並列化率は低下すると考えられる。次に、それぞれの手法における８プロセッサでの並列化効率(ＰａｒａｌｌｅｌＥｆｆｉｃｉｅｎｃｙ)を調べた。並列化効率ＰＥは、処理時間比をプロセッサ数で割った値であるため百分率で表すと、下記〔数２〕のようになっている。
【０１３７】
【数２】
2013025421.tif 000004
【０１３８】
並列化効率は、Ｌａｎｚｃｏｓ，Ａｒｎｏｌｄｉ，Ｋｒｙｌｏｖ−Ｓｃｈｕｒｂで、それぞれ、およそ７４．５８％，７６．１１％，６８．８７％となり、Ａｒｎｏｌｄｉが最も良い数値を示した。
【０１３９】
対称行列での並列化効率は３手法とも、８プロセッサまでであれば５０％は割り込まないが、それ以上になると並列化効率が低下する可能性がある。例えば、大規模なシステムであれば、システムの利用効率を維持するため，５０％の並列化効率に満たないジョブの投入を断るという事例がある。したがって、今後、本発明の情報検索システムで要求される処理性能の実現に８ノード以上が必要であることが判明し、かつ、８プロセッサ以上で並列化効率が５０％を割り込むことが判明した場合は、ハードウェア追加による投資対効果を得るために、他のライブラリや計算手法の利用が考えられる。
【０１４０】
３手法の繰り返し回数１２５００回の計算時間を比較したグラフを図１０に示す。対称行列では、Ｌａｎｚｃｏｓの計算時間が最も少ないことが分かる。非対称行列も計算可能な残りの２手法では、Ｋｒｙｌｏｖ−Ｓｃｈｕｒがより計算時間が短いことが分かる。ただし、これらは繰り返し回数を等しくした場合の計算時間であり、実際には各手法で固有値が収束するまでに必要な繰り返し回数は異なっている。例えば、今回調査した中ではＡｒｎｏｌｄｉは３６５３４回の繰り返しで収束している。
【０１４１】
次に生成した遷移確率行列での計算時間について調査した。
【０１４２】
生成した行列は非対称行列であり、遷移確率行列であるため、ラプラシアン行列よりも対象とするＷｅｂページのリンク構造に近い行列となっている。行列の列方向の値の和が１になるように行列を生成するため制約条件があり、行列のサイズは中途半端な値となる。今回２８１６２５というサイズの行列を用いた。また、繰り返し回数は各手法で固有値が収束しない５００回に制限して実施した。Ｌａｎｚｃｏｓは対称行列を対象とした計算手法であるため、非対称行列については、Ａｒｎｏｌｄｉ，Ｋｒｙｌｏｖ−Ｓｃｈｕｒの２手法について比較した。Ｋｒｙｌｏｖ−Ｓｃｈｕｒでは、行列が対称の場合、部分的に計算アルゴリズムをＬａｎｚｃｏｓをベースとした計算手法に切り替えているため、非対称の場合では性能特性が異なっている。
【０１４３】
図１１にプロセッサ数を変化させた場合の処理時間比Ｔ１＝Ｔｎの結果を示す。最小二乗法で推定した並列化率は、Ａｒｎｏｌｄｉ,Ｋｒｙｌｏｖ−Ｓｃｈｕｒがそれぞれ０．８１７５９１(８１．７５％), ０．８３９２９８（８３．９２％）となっており、非対称行列ではＡｒｎｏｌｄｉ，Ｋｒｙｌｏｖ−Ｓｃｈｕｒともに対称行列の場合と比べて並列化率が低下している。同様に、プロセッサ数を変化させた場合の並列化効率(Ｐａｒａｌｌｅｌ  Ｅｆｆｉｃｉｅｎｃｙ)の結果を図１２に示す。Ａｒｎｏｌｄｉ，Ｋｒｙｌｏｖ−Ｓｃｈｕｒともにプロセッサ数８で並列化効率が５０％を切っており、上述の例を考えると現在の実装では効果的にＣＰＵを利用できていないおそれがある。
【０１４４】
しかし、遷移確率行列は疎行列であるため固有値の収束が速く、収束までの繰り返し回数が少ない。実際に収束までにかかった繰り返し回数は、手法やプロセッサ数によって差があるが、Ｋｒｙｌｏｖ−Ｓｃｈｕｒでは、１１５７回以内で収束することが確認できた。処理時間は２プロセッサでおよそ１０２．２秒，５６．７７秒であり、ラプラシアン行列の場合の１／４程度の処理時間となっている。そのため、必要となるプロセッサ数も少なくなると考えられる。
【０１４５】
次に、通信オーバヘッドの影響を調査するため、単一ノードと複数ノードで計算した場合を比較した。具体的には、１ノードで実行した場合と２ノードで実行した場合を比較した。なお、評価はＴＣＰ／ＩＰで実施した。
【０１４６】
遷移確率行列は疎行列であるため、固有値の収束が速く、計算の繰り返し回数が少なくなる。そのため、計算の繰り返し回数が多くなるラプラシアン行列の計算結果で確認した。２プロセッサを利用した計算で、繰り返し回数を変化させた場合の処理時間について、図１３に示す。
【０１４７】
単一ノードで処理した場合に比べて、ＭＰＩ関連の関数呼び出し時間は大きくなるが、その他の部分の処理時間の関係で、複数ノードを利用した方が性能が良くなっているケースがある。これらは、Ｏｐｅｎ  ＭＰＩのドライバの実装等に依存している可能性がある。本検証の結果より、今後、情報検索システムが要求する性能が単一ノードのプロセッサ数では実現できないと判明した場合、今回調査した性能向上率で対応できる範囲であれば、ノード間通信を利用してプロセッサを追加することで対応できる可能性がある。
【０１４８】
以上で、ＭＰＩベースで実装されたクラスタ向けのミドルウェアも含めた固有値計算の処理速度に関する検証の説明を終了する。
【０１４９】
上記した検証では、ＳＬＥＰｃに実装されたＰｏｗｅｒ（べき乗）法についての検証を行っていないが、この方法も本発明の情報検索システムに好適に使用できる可能性がある
【０１５０】
上記した検証では、ランキング機能の固有値計算部分の高速化についてのみ検討を行った。しかし、実際にはページ間のリンク構造を取得して遷移確率行列として固有値計算プログラムに入力する必要がある。行列サイズが大きくなると、入出力がボトルネックになる可能性がある。ここで、ＭＰＩでは並列入出力の機能を備えており、これを利用することで入出力による性能低下を回避できる可能性がある。また、ＰＥＴＳｃは疎行列を効率的に格納するデータ構造をサポートしているため、メモリ使用量を抑えることができる。
【０１５１】
上記した検証によって、並列計算ライブラリＳＬＥＰｃを用いることで、８コア程度のＰＣで、数十万規模の遷移確率行列の固有値および固有ベクトルの計算が数十秒で完了できることが確認された。
【符号の説明】
【０１５２】
１  情報検索システム
１０  端末情報取得部（情報取得手段）
１３  検索実行部（情報序列化手段）
【図１】
2013025421.tif 000005
【図２】
2013025421.tif 000006
【図３】
2013025421.tif 000007
【図４】
2013025421.tif 000008
【図５】
2013025421.tif 000009
【図６】
2013025421.tif 000010
【図７】
2013025421.tif 000011
【図８】
2013025421.tif 000012
【図９】
2013025421.tif 000013
【図１０】
2013025421.tif 000014
【図１１】
2013025421.tif 000015
【図１２】
2013025421.tif 000016
【図１３】
2013025421.tif 000017