情報検索システム及び情報検索方法
【課題】Webページの人気や話題性、記載内容の精度等を反映した検索結果を短時間で出力可能な情報検索システム及び情報検索方法を提供することである。
【解決手段】検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行う情報検索システムにおいて、検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移確率を演算し、演算した値に基づいて検索対象となるWebページを序列化して端末に出力する。
【解決手段】検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行う情報検索システムにおいて、検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移確率を演算し、演算した値に基づいて検索対象となるWebページを序列化して端末に出力する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、WWW(World Wide Web)の情報検索システムにおいて、目的の情報を効率良く容易に取得するための技術に関する。
【背景技術】
【0002】
WWWの膨大な情報の中から目的の情報を得ようとする場合、検索システムを利用して該当するWebページを特定することが一般的である。このような検索システムでは、ユーザが入力した検索キーワードに該当するWebページを特定して集め、集められたWebページに重要度を付けて重要度の高いものから順に提示している。
【0003】
ここで、集められたWebページに重要度を付ける技術として、Webページ内の名詞の出現数やリンク構造等を基準にWebページのランク付けを行う技術が広く知られている。具体的には、例えば、ユーザが入力した検索キーワードがタイトル等の重要な箇所で使用されているWebページや、ユーザが入力した検索キーワードが適度に多く出現するWebページに対して高い重要度を付ける方法が知られている。また、他のWebページから数多くリンクされているWebページや、内容の関連性が高いWebページからリンクされているWebページに対して高い重要度を付ける方法が知られている。
【0004】
しかしながら、このようにWebページの内容やリンク構造だけを基準にWebページの重要度を規定すると、ユーザが検索用語を上手く選定できない場合、目的とする情報が開示されたWebページが上位に表示されず、ユーザが目的とする情報が開示されたWebページを発見できないという問題があった。さらにまた、目的とする情報が開示されたWebページを特定できた場合であっても、目的とする情報が難解であった場合、ユーザが深い理解を得られないという問題があった。
【0005】
そこで本発明者らは、このような問題に鑑み、検索結果として集められた各Webページの人気や話題性、記載内容の精度等に基づいてWebページに重要度を付け、重要度の高いものから順に提示することができる情報検索システム及び情報検索方法を先の出願(特許文献1)により提案した。
【0006】
具体的に説明すると、本発明者らが提案した情報検索システムでは、検索結果として集められた複数のWebページを、検索実行時にそれぞれのWebページを閲覧しているユーザの数が多い順に並び替えて検索結果を表示することができる。即ち、検索実行時に多くのユーザが注目しているWebページとは、検索実行時において話題性(必要性)の高いWebページであり、そのようなWebページを検索結果の上位に表示することによって、検索実行時に必要性が高い情報を取得し易くしている。
【0007】
また、本発明者らが提案した情報検索システムでは、予め情報検索システムを使用する全てのユーザの情報を取得しておき、取得した情報を検索結果に反映することができる。例えば、ある特定のユーザが検索を実行したとき、検索結果として集められたそれぞれのWebページをどのようなユーザが閲覧しているのか情報検索システムが判別し、特定の条件を満たしたユーザが閲覧しているWebページを上位に表示する。例えば、検索を実行したユーザが「プログラム」というキーワードで検索を実行したのであれば、「職業」が「プログラマ」であるユーザが閲覧しているWebページが上位に表示される。このように、検索結果として集められたWebページに、検索のキーワードに関連する分野の専門家であるユーザが閲覧しているWebページあれば、そのWebページを上位に表示する。即ち、専門家が多く閲覧しているWebページは内容が充実した(内容の精度が高い)Webページであり、そのようなWebページを検索結果の上位に表示することによって、ユーザが精度の高い情報を取得し易くしている。
【0008】
そして、本発明者らが提案した情報検索システムでは、検索実行後に特定したWebページを閲覧するとき、同じWebページを閲覧している他のユーザと通信可能となっている。そのことにより、特定したWebページの内容が難解であった場合であっても、他のユーザに質問することで、ユーザはWebページの内容に対する理解を深めることができる。
【先行技術文献】
【特許文献】
【0009】
【特許文献1】特開2011−39625号公報
【発明の概要】
【発明が解決しようとする課題】
【0010】
上記したように、検索結果として集められた各Webページの人気や話題性、記載内容の精度等に基づいてWebページに重要度を付け、重要度の高いものから順に提示する情報検索システムによると、ユーザが真に必要とする情報をより容易に取得できる。そこで本発明は、人気や話題性、記載内容の精度等を反映したWebページの重要度の算出がより正確に実施可能であり、算出したWebページの重要度を反映した検索結果を短時間で出力可能な情報検索システム及び情報検索方法を提供することを課題とする。
【課題を解決するための手段】
【0011】
上記課題を解決するための本発明の一態様は、検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、検索対象となるWebページを序列化する情報序列化手段を有するものであり、情報序列化手段は、検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施する機能を備えたことを特徴とする情報検索システムである。
なお、「遷移傾向を推定する演算」とは、実際の遷移確率の演算に加えて、遷移確率の演算に必要な要素に改変を加えた上で行う演算を含む。また、「遷移」とは、Webページ又は端末を頂点とし、特定のWebページからリンクを辿って他のWebページを表示することとする。さらに、特定の端末による特定のWebページの出力があったとき、特定のWebページを含む2つのWebページの間にリンクが形成されているものと同様な遷移が想定されるものとする。
また、このとき想定される「特定のWebページを含む2つのWebページの間にリンクが形成されているものと同様な遷移」は、「2つのWebページの間に相互リンクが形成されているものとする遷移」とすることが望ましい。なぜなら、「2つのWebページの間にいずれか一方のWebページから他方のWebページにリンクが形成されているものとする遷移」が想定された場合に比べて、ユーザに閲覧されることによるWebページの重要度の上昇がより正確に反映されるためである。
【0012】
本発明の第二の態様は、遷移確率の演算は、検索対象となるWebページと検索対象となるWebページに対して現にあるいは一定期間内に接続された端末を含む構成によって正方行列を設定し、当該正方行列の固有ベクトルを演算する演算内容を含むことを特徴とする請求項1に記載の情報検索システムである。
【0013】
本発明の第三の態様は、前記正方行列の要素は、Webページがリンクしているリンク先の数に基づく値と、端末が現にあるいは一定期間内に接続したWebページの数に基づく値によって構成されていることを特徴とする請求項2に記載の情報検索システムである。
【0014】
本発明の第四の態様は、前記正方行列の要素は、Webページがリンクしているリンク先の数に基づく値をAとし、端末が現にあるいは一定期間内に接続したWebページの数をBとしたとき、A/(A+B)、B/(A+B)あるいはこれらに系数が掛けられた値であることを特徴とする請求項2又は3に記載の情報検索システムである。
【0015】
本発明の第五の態様は、検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定するものであって、前記出力端末を仮想のWebページとし、出力端末が出力しているWebページと仮想のWebページとの間に相互リンクが形成されるとしたとき、Webページ及び仮想のWebページによって形成されるリンク構造に基づき、リンク元のWebページの表示からリンク先のWebページの表示への切り替えを遷移とした遷移確率行列を設定し、設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるWebページを序列化することを特徴とする請求項1乃至3のいずれかに記載の情報検索システムである。
なお、上記リンク構造には仮想のリンクを含み、上記リンク元のWebページ又は上記リンク先のWebページには、仮想のページを含むものとする。
【0016】
このような情報検索システムによると、人気や話題性、記載内容の精度等を反映したWebページの重要度の算出がより正確に実施可能であり、算出したWebページの重要度を反映した検索結果を短時間で出力可能となっている。したがって、並び替えの基準となる項目が多くなる等によって計算量が膨大になってしまった場合であっても、短時間で検索結果を取得することができる。
【0017】
本発明の第六の態様は、前記端末情報に基づいて、前記出力端末を使用する使用者の特定項目に対する知識及び/又は使用者の検索能力に対するユーザの重要度を示すユーザランク値を算出するものであり、
前記ユーザランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び/又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項2乃至5のいずれかに記載の情報検索システムである。
【0018】
本発明の第六の態様では、特定項目に対する知識が高いユーザや検索能力が高いユーザが閲覧している、内容の充実したWebページを上位に表示させることができる。そのことにより、ユーザが検索実行時に必要性の高い情報を容易に取得することができる。
【0019】
本発明の第七の態様は、ネットワーク上のWebページの内容に関する情報を取得可能な情報取得機能を有し、情報取得機能が取得した情報に基づいてWebページの内容の重要度を示すリレーションランク値を算出するものであり、前記リレーションランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び/又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項2乃至6のいずれかに記載の情報検索システムである。
【0020】
本発明の第七の態様では、検索条件と関連性の高い内容のWebページを上位に表示させることができる。そのことにより、ユーザが検索実行時に必要性の高い情報を容易に取得することができる。
【0021】
本発明の第八の態様は、端末で入力されたキーワードに基づいてデータベースの検索を行なうと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、検索対象となるWebページを序列化する情報序列化手段を有するものであり、情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定し、前記Webページと出力端末に基づいて正方行列を設定するものであって、前記正方行列はWebページ及び出力端末に対応する行要素及び列要素から形成されるものであり、その各要素P(i,j)は下記式(1)の関係を満たすものであり、設定した前記正方行列の固有ベクトルを算出し、算出した固有ベクトルの成分の大きさに基づいて検索対象となるWebページを序列化することを特徴とする情報検索システムである。
P(i,j)= αX/Y ・・・(1)
α =0以外の数
X = 列「j」に対応するWebページから行「i」に対応するWebページへのリンクの数、又は、列「j」に対応するWebページの行「i」に対応する出力端末での表示数、又は、列「j」に対応する出力端末での行「i」に対応するWebページの表示数、又は0
Y = 列「j」に対応するWebページの出力端末での表示数と、列「j」に対応するWebページに形成されているリンク数の総和
【0022】
本発明の第九の態様は、検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索方法であって、検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施することを特徴とする情報検索方法である。
【0023】
本発明の第十の態様は、検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得し、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定するものであり、前記出力端末を仮想のWebページとし、出力端末が出力しているWebページと仮想のWebページとの間に相互リンクが形成されるとしたとき、Webページ及び仮想のWebページによって形成されるリンク構造に基づき、リンク元のWebページの表示からリンク先のWebページの表示への切り替えを遷移とした遷移確率行列を設定し、設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるWebページを序列化することを特徴とする請求項9に記載の情報検索方法。
【0024】
本発明の第九の態様及び第十の様態では、検索実行時において人気の高い情報を有するWebページや、ものごとに対する興味が似ているユーザ、検索目的の分野に精通しているユーザ等が閲覧するWebページ等が検索結果の上位に表示されるため、必要性が高い情報や質の高い情報を取得し易い。また、そのような検索結果を短時間で出力できる。
【発明の効果】
【0025】
本発明は、検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行い、その検索結果を前記端末に出力して表示させるための情報検索システムにおいて、Webページの人気や話題性、記載内容の精度等を反映した検索結果をより速く出力できるという効果がある。
【図面の簡単な説明】
【0026】
【図1】本発明の第1の実施形態に係る情報検索システムの構成を示す概念図である。
【図2】本発明の第1の実施形態に係る情報検索システムの機能ブロックの一例を示す図である。
【図3】本発明の第1の実施形態に係る情報検索システムのハードウェア構成の一例を示す図である。
【図4】本発明の第1の実施形態に係る情報検索システムによる検索手順の一例を示すフローチャートである。
【図5】本発明の第1の実施形態に係る情報検索システムで検索を実施する際に検索対象となるWebページのリンク構造、及び当該Webページの閲覧状況の一例を示す説明図である。
【図6】本発明の第1の実施形態に係る情報検索システムで検索を実施する際に設定するランク値演算用行列の一例を示す説明図である。
【図7】本発明の第2の実施形態に係る情報検索システムで検索を実施する際に設定するランク値演算用行列の一例を示す説明図である。
【図8】本発明の実施例において固有値演算の速度を検証するために用いた行列を示す説明図であり、(a)はラプラシアン行列を示し、(b)は遷移確率行列を示す。
【図9】本発明の実施例において、ラプラシアン行列の固有値演算におけるプロセッサ数を変化させたときの処理時間比を示すグラフである。
【図10】本発明の実施例において、ラプラシアン行列の固有値演算における処理時間を示すグラフである。
【図11】本発明の実施例において、遷移確率行列の固有値演算におけるプロセッサ数を変化させたときの処理時間比を示すグラフである。
【図12】本発明の実施例において、遷移確率行列の固有値演算における並列化効率を示すグラフである。
【図13】本発明の実施例において、複数ノードでのラプラシアン行列の固有値演算におけるネットワーク性能の影響を示すグラフである。
【発明を実施するための形態】
【0027】
本発明の実施形態に係る情報検索システム、並びに情報検索方法の提供方法についてそれぞれ図面を参照しながら詳細に説明する。
【0028】
図1は、第1の実施形態の情報検索システム1の構成の概略を示す概念図である。図1に示す様に、情報検索システム1は、検索装置2とクライアント端末4(図1では符号4a〜4d及び・・・で示す)で構成されており、それぞれ電気通信網を介して接続されている。クライアント端末4にて、それぞれブラウザ5(図1では符号5a〜5d及び・・・で示す)が起動されている。
【0029】
第1の実施形態の情報検索システム1は、入力情報を取得可能となっている。具体的には、この入力情報は、ブラウザ5にプラグイン形式等の所定の手段で組み込んだ端末側情報取得装置7で取得され、検索装置2へ送信される。なお、入力情報とは、ユーザがブラウザ5やブラウザ5と連動するプログラム(例えば、プラグインツールバー等)を介して入力した検索キーワード等に関する情報である。
【0030】
また端末側情報取得装置7は、上記した入力情報だけでなく、ブラウザ5を介したWebページの出力に関する情報である使用情報も検索装置2へ送信することができる。具体的には、端末側情報取得装置7は、使用情報として、ブラウザ5における規定のWebページの表示開始時間や表示終了時間といったWebページの表示時間に関わる情報を検索装置2へ送信することができる。さらに、使用情報として、規定のWebページからリンクを辿って他のWebページを表示させた場合に、移動元のWebページのURLや移動先のWebページのURLといったWebページの遷移経路を示す情報を検索装置2へ送信することができる。
【0031】
このように、端末側情報取得装置7は、上記したような入力情報や使用情報を端末情報として検索装置2へ送信する。このとき、端末側情報取得装置7による情報の送信は、ブラウザ5が起動された場合、検索が実行された等の所定の操作が実行された場合、前回情報の送信が終了してから規定時間が経過した場合、といった所定のタイミングに自動で実施される。
【0032】
一方、検索装置2では、端末側情報取得装置7から送信された端末情報を検索用データベース3に格納する。即ち、ネットワーク上の各クライアント端末4(4a〜4d,・・・)から検索装置2に送信された端末情報が、検索装置2の検索用データベース3に格納される(図2)。
【0033】
また、検索装置2は情報収集部12を有している。この情報収集部12は、所謂クローラとインデクサの機能を有するものであって、WWW上を巡回し、リソースに関する情報を取得し、まとめて、検索用データベース3に蓄積する。そして、検索用データベース3に蓄積するときは、Webページのリンク構造に関する情報や、記載されているテキスト、タイトル、各種タグ等の内容に関する情報を特徴毎に解析、選別、分類し、検索しやすいようにしておく。
【0034】
情報検索システム1は、いずれかのクライアント端末4で検索が実行されると、入力された検索キーワードより、検索クエリを作成してサーバである検索装置2に送信する。
【0035】
検索装置2で検索クエリを受信すると、検索装置2の検索実行部13は、検索用データベース3に蓄積されたWebページの中から検索対象となるWebページを特定する。また、特定されたそれぞれのWebページを閲覧している、又は閲覧したユーザの数を特定する。そして、詳しくは後述するが、これらの情報に基づいて形成されるランク値演算用行列の固有値を算出し、算出した固有値を検索対象となる各Webページのランク値(重要度の値)とする。
【0036】
さらに検索実行部13は、検索結果のWebページを取得したランク値に基づいて並び替える。そして、検索装置2の検索結果出力部15が、検索が実行されたクライアント端末4に検索結果を送信し、クライアント端末4で検索結果のWebページが並び替えた順に表示される。
このことにより、検索実行時に人気が高く、話題性のあるWebページを検索結果の上位に表示させることができる。
【0037】
以下、本実施形態の情報検索システム1についてより詳細に説明する。
【0038】
まず、本実施形態の情報検索システム1の機能的構成について説明する。
なお、以下に記載する本実施形態の情報検索システム1の各機能ブロックは、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの両方として実現され得る。具体的には、コンピュータを利用するものであれば、CPUや主メモリ、バス、あるいは不揮発性メモリや、所謂外部記憶装置(ハードディスクやフロッピーディスク(登録商標)、MO、CD、DVD、BD、磁気テープ等々の記憶装置、及びそれらメディアの読み取り装置)、印刷機器、表示装置、その他外部周辺装置等のハードウェア構成部、またその外部周辺装置用のI/Oポート、それらハードウェアを制御するためのドライバプログラムやその他アプリケーションプログラム、情報入力に利用されるユーザーインターフェース等が挙げられる。
【0039】
そして主メモリ上に展開したプログラムに従ったCPUの演算処理によって、インターフェースを介して入力され、各種メモリやハードディスク上に保持されているデータなどが加工、蓄積されたり、上記各ハードウェアやソフトウェアを制御するための命令が生成されたりする。また、本発明はシステムとして実現できるのみでなく、方法としても実現可能である。加えて、本発明の一部をソフトウェアとして構成することができる。そして、そのようなソフトウェアをコンピュータに実行させるために用いるソフトウェア製品、及び同製品を記録媒体に固定した記録媒体も、当然に本発明の技術的な範囲に含まれる(本明細書の全体を通じて同様である)。
【0040】
図2は、本実施形態の情報検索システム1における機能ブロックの一例を示す図である。この図にあるように、本実施形態の検索システム1は、主に端末側情報取得装置7と検索装置2から構成されている。
【0041】
端末側情報取得装置7は、端末情報取得部10と端末情報送信部11とを少なくとも有している。
【0042】
端末情報取得部10は、クライアント端末4のブラウザから、少なくとも閲覧URLを含む、端末情報を取得する機能を有する。ここで閲覧URLとは、ブラウザを介して表示された(クライアント端末4でユーザが閲覧していた)WebページのWeb上(ネットワーク上)での所在を示す情報であり、例えば、「http://・・・/ABC.jpg」のように記述される情報である。
ここで、ブラウザから端末情報を取得する手段は、特に限定されるものでなく、適宜の方法を用いてよい。これらの方法は、例えば、API(Application Program Interface)やDDE(Dynamic Data Exchange)、OLE(Object Linking and Embedding)やファイルシステム等が挙げられる。
【0043】
また端末情報取得部10が取得する端末情報には、閲覧URL以外にもブラウザでのWebページの閲覧に関する各種情報が含まれてよい。これらの情報には、例えば、システム利用者のユーザID、ブラウザID、Webページの閲覧開始時刻、Webページの閲覧終了時刻、あるいは、リンクを辿って2以上のWebページを閲覧した際の「移動元Webページ」や「移動先Webページ」などの移行情報などが挙げられる。
さらに、端末情報には、特定のWebページにおいて、ユーザが入力した検索キーワード等の入力情報が含まれてよい。
【0044】
ユーザIDとはユーザを識別するための情報を示し、例えば、クライアント端末4へのログイン時のIDや、サービス単位又はソフトウェア単位で割り当てられるIDなどが挙げられる。ブラウザIDも同様に、ブラウザを識別するための情報であり、例えば、これらの情報は予めブラウザプログラムやツールバープログラムに記録されている製品IDなどを利用することで取得することができる。
そして、これら識別情報を利用することでクライアント端末4を識別することができるので、クライアント端末4(ユーザ)単位での閲覧情報の管理、分析を行うことができる。なお、これらID情報の保持は、例えば、端末側情報取得装置7自身が保持する方法や、ブラウザが有するcookie機能を利用する方法等、適宜な方法で行われる。
【0045】
閲覧開始時刻とは、ブラウザにてWeb上のWebページにアクセスした時刻、あるいはそのアクセスによってブラウザにWebページが取得された時刻や、表示された時刻などをいう。具体的に説明すると、当該時間は、例えば、ブラウザにてリクエストを行ったリソースのロード完了を検出した時刻や、WebサーバがHTTPステータスコード(例えば、「200:OK」と記述されるコード)等の信号を応答した時刻等が挙げられる。
【0046】
閲覧終了時刻とは、ブラウザにてWebページの表示を終了した時刻をいい、例えば、ブラウザのUIウィンドウがクローズした時刻や、当該ウィンドウがアクティブでなくなった時刻、ウィンドウ領域内からマウスポインタが検出されなくなった時刻(マウスポインタがウィンドウ領域外へ移動した時刻)等が挙げられる。また、一定時間の操作がないためクライアント端末4のOSが自動的にログオフ処理を行ったり、スクリーンセーバ等が起動したりした場合には、それらが行われた時刻を閲覧終了時刻としてもよい。
【0047】
移行情報とは、2以上のWebページを連続で閲覧した際の「移動元Webページ」と「移動先Webページ」を示す情報のことであり、例えば、ハイパーリンクのクリックによる移行(遷移)の他、ブラウザやツールバーのURL入力欄に連続で入力された2以上のURLを「移動先」、「移動元」とする移行情報などが挙げられる。
【0048】
端末情報送信部11は、取得した端末情報を所定の検索装置2に送信する機能を有する。具体的には、当該端末情報を、クライアント端末の通信I/Fを使用し通信回線等を介して、所定の検索装置2(サーバ装置)に自動送信する機能を有する。
なお、端末情報の送信先となる所定の検索装置2の送信先アドレスは、例えば端末側情報取得装置7のプログラム内に予め記述されることで特定する方法などが挙げられる。
また、この端末情報送信部11から端末情報が送信されるタイミングは、適宜のタイミングに設定可能である。例えば、ブラウザにて表示されているWebページが切換わるごとに送信するといったタイミングや、一定の時間、又は時刻が到来した際にバッチ処理で送信するタイミング、あるいはツールバー起動時または終了時に送信するタイミングなどが挙げられる。
【0049】
このように、各クライアント端末4でのブラウザ5を介したWebページの出力(表示)に対する端末情報が、端末側情報取得装置7によって取得され、検索装置2に送信される。そして、検索装置2で当該端末情報が収集されることにより、クライアント端末4で閲覧している、又は閲覧されたWebページが特定できる。つまり、各クライアント端末4のブラウジング(閲覧)履歴を容易に把握することができる、
【0050】
次に検索装置2の機能的構成を説明する。
【0051】
検索装置2は、サーバ装置であって、検索用データベース3、情報収集部12、検索実行部13、検索結果出力部15を有している。
【0052】
検索用データベース3は、クライアント端末4から送信される端末情報を受信、管理、蓄積する機能を有するデータベースである。
【0053】
情報収集部12は、上記したように、WWW上を巡回し、Webページの構造や内容に関する情報を取得し、取得した内容に基づいてインデックスファイルを作成することができる。また、作成したインデックスファイルを検索用データベース3に格納、保存することができる。
【0054】
検索実行部13は、いずれかのクライアント端末4で検索が実行された時に、ユーザからの検索キーワード等に基づいて、検索用データベース3に格納された情報を参照し、検索を実行する。具体的には、検索用データベース3を参照することにより、検索対象となるWebページを特定し、加えて特定した各Webページを出力している端末数を特定する。そして、詳しくは後述するが、これらの情報に基づいて形成されるランク値演算用行列の固有値を算出し、算出した固有値を検索対象となる各Webページのランク値(重要度の値)とする。またさらに、取得したランク値を用いて検索結果となるWebの並び替えを実行する。
【0055】
検索結果出力部15は、検索用データベース3から抽出し、並び替えを実行した検索結果をクライアント端末4のブラウザ5に表示する機能を有する。具体的には、クライアント端末の送信先アドレスを適宜の方法で取得する。ここで、適宜の方法とは、検索クエリと同時に受信する方法や、ユーザIDとあらかじめ登録しておいたIPアドレスを照合する方法等がある。そして、端末側情報取得装置7を介して、特定したクライアント端末4のブラウザ5上で検索結果画面を表示する。
【0056】
次に、本実施形態における、情報検索システム1のハードウェア的構成について説明する。
図3は上記した機能的な各構成要件を、ハードウェアとして実現した際の、情報検索システム1における構成の一例を表わす概略図である。この図を利用して、本実施形態の検索システム1におけるそれぞれのハードウェア構成の働きについて説明する。図3にあるように、本実施形態の情報検索システム1のハードウェア構成は、クライアント端末4に組み込まれた端末側情報取得装置7と、サーバ装置としてネットワーク上に配置されている検索装置2により構成される。
【0057】
端末側情報取得装置7と検索装置2は電気通信回線を介して相互に接続され、情報の送受信を行う。なお、電気通信回線はインターネットを含む。
【0058】
端末側情報取得装置7においては、端末情報取得部10を実現し、またその他各種演算処理を行うCPU(中央演算装置)とRAMや、端末情報送信部11である通信I/Fを備える。またキーボード、マウス等の入力装置であるUI(User Interface)や、ブラウザプログラムにて処理されたリソースを表示するためのVRAMや、ディスプレイなどの表示装置も備える。そしてそれらがシステムバスなどのデータ通信経路によって相互に接続され、情報の送受信や処理を行う。
【0059】
端末側情報取得装置7のRAM上には、ブラウザプログラムと、プラグインプログラムとが格納されており、これらプログラムに従い端末情報の取得や送信処理やその他処理に係るCPUの各種演算処理が実行される。また上記プラグインプログラムによって、RAM上の所定のアドレスには閲覧URLやユーザID等の端末情報を格納する領域が確保されている。
【0060】
一方、検索装置2においては、各種演算処理を行うCPUと、RAMと、通信I/Fと、大量の端末情報等を蓄積するためのハードディスクなどの外部記憶装置とを有している。そしてそれらがシステムバスなどのデータ通信経路によって相互に接続され、情報の送受信や処理を行う。
【0061】
また検索装置2のRAM上には、検索実行部や検索結果出力部の各機能を実現するプログラムやデータベース管理プログラム(図示せず)等の情報検索システム1の機能を実現する各プログラムが格納されており、当該プログラムに従い端末情報の管理処理やその他処理に係るCPUの各種演算処理が実行される。
【0062】
ここで、端末側情報取得装置7では、ユーザのUIを介した操作入力を受け付け、RAM上のブラウザプログラムおよびプラグインプログラムに従い以下のような処理が実行される。
【0063】
例えば、UIを介したブラウザ操作によってWebページへのアクセス指示が入力されると、そのアクセス指示で指定されたWebページのURLがRAMの所定アドレスに格納される。すると、ブラウザプログラムに従い指定されたURLに対して、HTTPリクエストがクライアント端末4から検索装置2へ送信される。そして、そのHTTPリクエストに対するレスポンスをアクセスリソースのコンテンツとして通信I/Fにて該クライアント端末4が受信する。続いてクライアント端末4が受信したコンテンツに含まれるHTMLファイル、イメージファイルなどを、ブラウザ5が有するHTMLレンダリングエンジンなどに従ったCPUの演算処理よってレンダリング処理する。そしてその処理結果がVRAMに転送され、表示装置上にWebコンテンツが表示される。それから、ユーザは表示された当該WWW上のWebページなどのリソースを閲覧する。
【0064】
また、それとともに前記ブラウザでのアクセス指示入力に応じてプラグインプログラムは次の処理を実行する。即ち、RAMの所定アドレスに格納されたURLを端末情報として、前述のような所定の各タイミングで通信I/Fから検索装置2に自動送信する、という具合である。
【0065】
これに対して、検索装置2では、通信I/Fにて各クライアント端末4の端末側情報取得装置7から送信されてきた端末情報を受信し、RAMの所定アドレス等に格納する。そして、検索装置2のプログラムにしたがって、例えば、端末情報に含まれるURLやユーザIDなどをパラメータとして、CPUの演算処理によって検索用データベース3のファイルを作成又は、作成されている検索用データベース3のファイルに追記し、HDD等の外部記憶装置に格納する、という具合である。
【0066】
また、UIによるブラウザ操作によって、検索エンジン(検索用Webページ)にアクセスし、検索クエリの入力、送信を行なった場合や、ツールバーに検索クエリの入力、送信を行った場合のように、クライアント端末4にて検索が実行された場合について説明する。その際、検索装置2は通信I/Fにて該検索クエリを含むHTTPリクエストを受信し、RAMの所定アドレスに格納する。すると、検索装置2では検索サーバプログラムに従い以下の処理を実行する。即ち、RAMに格納されている検索クエリをキーとして、外部記憶装置に保存されている、インデックスファイルデータベースの中から、検索クエリの条件を満たすWebページを抽出する。続いて、CPUの比較演算処理によって、抽出されたWebページの情報と外部記憶装置に保存されている端末情報(端末側情報取得装置7から送信された端末情報)とを比較演算することにより、抽出されたWebページを出力している端末を特定する。そして、詳しくは後述するが、抽出されたWebページのリンク構造と、抽出されたWebページが出力された端末の情報からランク値演算用行列を設定する。さらにまた、設定されたランク値演算用行列の固有値を規定のアルゴリズムに基づいて算出することにより、抽出された各Webページのランク値を取得し、CPUの比較演算処理によって、抽出されたWebページをランク値の高い順に並び替える。加えて、検索装置2は、Webページを並べて箇条形式とした検索結果をCPUの演算処理によって生成し、通信I/Fにより検索クエリの送信元のクライアント端末4のブラウザ5に対して送信する、と言う具合である。
【0067】
次に、本実施形態の情報検索システム1の検索実行時の処理の流れについて説明する。
図4は、本実施形態の情報検索システム1の検索実行時の処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【0068】
いずれかのクライアント端末4で検索が実行され(ステップ101でYesの場合)、クライアント端末4から検索装置2に検索クエリが送信されると、検索クエリを受信した検索装置2が検索用データベース3から検索クエリの条件を満たすWebページを抽出する(ステップ102)。即ち、検索クエリをキーワードにして該当するインデックスファイルを検索する。
【0069】
さらに検索装置2は、抽出したWebページのデータと、検索用データベース3に格納された端末情報とを比較することにより、抽出したWebページを出力している端末を特定する(ステップ103)。即ち、各クライアント端末4から送信された、ブラウザ5を介したWebページの出力、又は過去の出力に係る情報を参照することにより、抽出したWebページを出力している端末、又は出力した端末を特定する。
【0070】
次に、検索装置2は、検索クエリの条件を満たすWebページに係る情報(ステップ102で取得した情報)と、抽出したWebページを出力している端末に係る情報(ステップ103で取得した情報)からランク値演算用行列を設定する(ステップ104)。本発明の特徴的構成であるところのランク値演算用行列の設定処理について、図5,6を参照しつつ以下で詳細に説明する。
【0071】
ランク値演算用行列は、ネットワーク上で公開された複数のWebページとユーザからなるリンク構造に対応して設定するものであり、その各「列」は、「列」に対応するWebページから他のWebページへのリンクを示すものとなっている。即ち、「列」に属する各要素がそれぞれ別箇の他のWebページへのリンクを示している。さらにまた、その各「行」は、他のWebページから「行」に対応するWebページへのリンクを示すものとなっている。即ち、「行」に属する各要素がそれぞれ別箇の他のWebページから「行」に対応するWebページへのリンクを示している。
具体的に説明すると、例えば、図6で示されるようなランク値演算用行列Pであれば、その行列Pの各要素は、行列の上部に示したWebページA,B,C,D及びユーザ(Webページの閲覧者)E,F,G,Hから、行列の左部に表示したWebページA,B,C,D及びユーザE,F,G,Hに対するリンク又はユーザによるWebページの閲覧の状況を示す数値である。
即ち、図6に示す正方行列(ランク値演算用行列P)は、検索対象となるWebページがリンク先となっているWebページと、検索対象となるWebページがリンクしているWebページに対して現に、あるいは一定期間内に接続された端末との関連を示すものである。
【0072】
ここで、ランク値演算用行列についてモデルを用いて具体的に説明する。なお、本発明のランク値演算用行列がモデルのものに限らないことは当然である。
図5で示されるように、4つのWebページA,B,C,DがWebサーバ上に保持され、インターネットやLAN等のネットワークに接続されたコンピュータでブラウザを介して閲覧可能となっているものとする。即ち、4つのWebページA,B,C,Dがネットワーク上に公開された状態となっているものとする。ここで、1つめのWebページAは、WebページB,WebページCにそれぞれリンクを張った状態となっている。
ここで、「リンクを張った状態」とは、リンク元となる特定のWebページにリンク先となる他のWebページのURLが関連付けられており、例えば、リンク元のWebページ上の所定の部分をクリックするといった所定の操作によって、リンク先のWebページがブラウザで表示される構造となっている状態とする。
【0073】
さらに、2つめのWebページBは、WebページDにリンクを張った状態となっている。3つめのWebページCは、WebページDにリンクを張った状態となっている。4つめのWebページDは、WebページA,WebページCにそれぞれリンクを張った状態となっている。
【0074】
換言すると、1つ目のWebページAは、4つ目のWebページDにリンクを張られた状態となっている。
ここで、「リンクを張られた状態」とは、リンク元となる他のWebページが、リンク先となる特定のWebページにリンクを張った状態であることとする。即ち、他のWebページに特定のWebページのURLが関連付けられており、他のWebページで所定の操作を行うことによって、特定のWebページがブラウザで表示される構造となっている状態とする。
【0075】
同様に、2つめのWebページBは、WebページAにリンクを張られた状態となっている。3つめのWebページCは、WebページAとWebページDにそれぞれリンクを張られた状態となっている。4つめのWebページDは、WebページB,WebページCにそれぞれリンクを張られた状態となっている。
【0076】
ここで、WebページAをユーザEが閲覧しているものとする。即ち、閲覧者Eが使用しているクライアント端末4aのブラウザ5が、インターネットやLAN等のネットワークを介してWebページAを保持しているWebサーバからデータを取得し、WebページAを閲覧可能な状態に出力しているものとする。
【0077】
また同様に、WebページBをユーザF,G,Hがそれぞれ閲覧しているものとする。即ち、クライアント端末4b,4c,4dの各ブラウザ5が、WebページBを閲覧可能な状態に出力しているものとする。
【0078】
以上説明した状況において、いずれかのクライアント端末4で検索が実行され、WebページA,B,C,Dがいずれも検索クエリの条件を満たすWebページであったとする。このとき、検索装置2は、WebページA,B,C,Dを出力しているクライアント端末4a,4b,4c,4dを特定し、ユーザE,F,G,HがWebページA,B,C,Dを閲覧しているものとして、図6で示されるようなランク値演算用行列Pを設定する。
【0079】
ランク値演算用行列Pの各「列」要素に注目すると、左側部分RLはWebページA,B,C,Dに関する要素となっており、右側部分RRはユーザE,F,G,Hに関する要素となっている。即ち、複数のWebページA,B,C,Dに関する要素から構成される要素群と、複数のユーザE,F,G,Hに関する要素から構成される要素群とが隣合わせに配されている。
【0080】
このように本実施形態の検索装置2は、ユーザE,F,G,Hを仮想のWebページE,F,G,Hとしてランク値演算用行列Pを設定している。即ち、「特定のユーザによる特定のWebページの閲覧」を「仮想のWebページと特定のWebページの間で互いにリンクが張られている」状態としてランク値演算用行列Pに反映させている。換言すると、図6に示す正方行列では、WebページA,B,C,Dと、その閲覧者E,F,G,Hを同格に扱い、行列の各要素に反映させている。
【0081】
詳説すると、上記したようにWebページAをユーザEが閲覧しているとする(図5参照)。このとき、検索装置2は、WebページA,B,C,Dからなるリンク構造に、実際には存在しない仮想のWebページEがあるものとし、WebページA,B,C,D,Eからなるリンク構造であるものとする。そして、WebページA,B,C,Dに対応する「行」及び「列」に加えて、仮想WebページEに対応する新たな「行」と「列」とを追加してランク値演算用行列Pを設定する。換言すると、ユーザEが使用するクライアント端末4aでWebページAが出力されたことを条件に、ランク値演算用行列Pに新たな「行」と「列」とを追加する。
【0082】
したがって、上記のように4人のユーザE,F,G,Hが、それぞれ検索対象となるWebページA,B,C,Dのいずれかを閲覧している場合、WebページA,B,C,D,E,F,G,Hからなるリンク構造であるものとして、仮想WebページE,F,G,Hに対応する新たな「行」と「列」を4つずつ追加してランク値演算用行列Pを設定する。即ち、検索対象となるWebページの数と、検索対象となるWebページを出力している端末の数との合計がランク値演算用行列Pの行数及び列数となる。
【0083】
ここで、ランク値演算用行列Pの各「列」は、上記した検索対象となるWebページ、又は検索対象となるWebページの出力を条件にして定義される仮想のWebページに対応している。そして、「列」に属する各要素は、対応するWebページ又は仮想のWebページ(以下単にWebページとも称す)から、他のページへのリンクを示すものとなっている。具体的には、「列」に属する要素P(i,j)は、下記式(1):
P(i,j)= αX/Y ・・・(1)
α =0以外の数
X = 列「j」に対応するWebページから行「i」に対応するWebページへのリンクの数、又は、列「j」に対応するWebページの行「i」に対応する出力端末での表示数、又は、列「j」に対応する出力端末での行「i」に対応するWebページの表示数、又は0
Y = 列「j」に対応するWebページの出力端末での表示数と、列「j」に対応するWebページに形成されているリンク数の総和
の関係を満たすものである。
即ち、Webページがリンクしているリンク先の数に基づく値をAとし、端末が現にあるいは一定期間内に接続したWebページの数をBとしたとき、ランク値演算用行列Pの各要素は、A/(A+B)、B/(A+B)あるいはこれらに系数αが掛けられた値となっている。
【0084】
ここで、上記したように、本実施形態の検索装置2は、ユーザEが使用するクライアント端末4aでWebページAが出力されていることを条件に、WebページAから仮想のWebページEへリンクが張られ、仮想のWebページEからWebページAへリンクが張られているものとして、ランク値演算用行列Pを設定する。換言すると、ユーザEによるWebページAの閲覧を、実際には存在しないWebページEとWebページAの相互リンク(互いにリンクを張っている状態)として、ランク値演算用行列Pに反映させる。
【0085】
つまり、図5で示されるように、特定のWebページAから他の2つのWebページB,Cにそれぞれリンクが張られ、ユーザEが前記特定のWebページAを閲覧しているとする。このとき、検索装置2は、特定のWebページAが2つのWebページB,Cに加えて、仮想のWebページEにリンクを張っているとする。このとき、図6で示されるように、ランク値演算用行列Pの特定のWebページAに対応する列(図6で最も左側の列)を形成する各要素P(i,1)に注目すると、WebページB,C及び、仮想のWebページEへのリンクとそれぞれ対応する要素であるP(2,1),P(3,1),P(5,1)はいずれも1/3となっている。これらは、特定のWebページAのリンクの総数が3であり、特定のWebページAからWebページB,C及び、仮想のWebページEにそれぞれ1つずつリンクが張られていることを示している。したがって、ランク値演算用行列Pの各「列」の要素の総和は1となっている。
【0086】
また、ここでランク値演算用行列Pの各「行」要素に注目すると、上側部分LHはWebページA,B,C,Dに関する要素となっており、下側部分LLはユーザE,F,G,Hに関する要素となっている。即ち、複数のWebページA,B,C,Dに関する要素から構成される要素群と、複数のユーザE,F,G,Hに関する要素から構成される要素群とが上下に連続して配されている。
【0087】
以上のことから、図6で示されるように、ランク値演算用行列Pは、検索対象となるWebページA,B,C,Dと上記仮想のWebページE,F,G,HとからなるWebページ群において、各WebページA,B,C,D,E,F,G,Hを頂点とし、リンクを辿ることを遷移(推移)とするものであり、さらに、Webページ内の各リンクから一様な確率で1つのリンクを辿ることを想定する遷移確率行列(推移確率行列)となっているといえる。
なお、ここでいう「リンクを辿る」とは、リンク元となる特定のWebページにリンク先となる他のWebページのURLが関連付けられており、例えば、リンク元のWebページ上の所定の部分をクリックするといった所定の操作によって、リンク先のWebページがブラウザで表示されることとする。そしてさらに、実際のWebページと仮想のWebページの間に定義したリンクにおいても、実際のWebページ間のリンクと同様に取り扱うものとする。
【0088】
このとき、ランク値演算用行列Pに注目すると、図6で示されるように、左上に位置するエリアE1に属する各要素は、実際に存在するWebページA,B,C,Dの間に形成されるリンクを示している。また、右上に位置するエリアE2に属する各要素は、仮想のWebページE,F,G,Hのいずれかから実際に存在するWebページA,B,C,Dのいずれかへのリンクを示している。さらに、左下に位置するエリアE3に属する各要素は、実際に存在するWebページA,B,C,Dのいずれかから、仮想のWebページE,F,G,Hのいずれかへのリンクを示している。そして、右下に位置するエリアE4は、仮想のWebページE,F,G,Hの間に形成される仮想のリンクを示している。
【0089】
このようなランク値演算用行列Pが設定されると、図4で示されるように、ステップ104からステップ105へ移行して、検索装置2がランク値演算用行列Pの固有値を算出する。つまり、遷移確率行列の各頂点であるWebページA,B,C,D及び仮想のWebページE,F,G,Hのそれぞれにおける遷移確率を演算する。そして、検索装置2は、算出したランク値演算用行列Pの固有値に基づいて検索対象となるWebページを並び替える(ステップ106)。
【0090】
詳説すると、例えば、図6で示されるランク値演算用行列Pでは、その固有値は下記式(2):
〔A,B,C,D,E,F,G,H〕=〔0.408,0.544,0.408,0.544,0.136,0.136,0.136,0.136〕・・・(2)
の関係を満たしている。
したがって、図5で示されるWebページA,B,C,Dの固有値はそれぞれ0.408,0.544,0.408,0.544となる。ここで、このWebページA,B,C,Dを固有値の高い順に並べ替えるのであれば、WebページB,WebページD,WebページA,WebページCの順となる。
【0091】
そして検索装置2は、並び替えた検索対象となるWebページを検索結果としてクライアント端末4へ送信する(ステップ107)。
以上で情報検索システム1の検索実行時の処理の流れの説明を終了する。
【0092】
上記した実施形態では、ランク値演算用行列Pを設定するとき、ユーザE,F,G,Hをいずれも画一的なユーザとして仮想のWebページE,F,G,Hを設定した。つまり、Webページを閲覧したユーザがいずれのユーザE,F,G,Hであっても、仮想のWebページと実在のWebページの間に定義される仮想のリンクの数は同一となっている。即ち、いずれのユーザであっても1つの仮想のWebページと1つの実在のWebページの間に1つの相互リンクが定義される構成となっている。
【0093】
しかしながら、本発明の情報検索システムはこのような構成に限るものではない。即ち、各ユーザE,F,G,Hの間で特定項目に対する知識の深さや、検索スキル等が異なっている場合、ランク値演算用行列の設定に閲覧しているユーザE,F,G,Hの知識やスキルの違いを反映させる構成であってもよい。さらにまた、ランク値演算用行列Pに、検索キーワード等の出現数といったWebページA,B,C,Dの内容を反映させる構成であってもよい。
【0094】
以下で第2の実施形態及び第3の実施形態を説明するが、特に説明がない限り、第1の実施形態における情報検索システム1と同様の部分については、同様の符号を付して重複する説明を省略する。
【0095】
第2の実施形態では、ランク値演算用行列を設定するとき、ユーザE,F,G,Hの知識や検索スキル等の違いや、WebページA,B,C,Dの内容の違いに応じて、ランク値演算用行列の各要素を変更することを特徴とする。
【0096】
第2の実施形態の情報検索システム20は、第1の実施形態と同様に、検索装置2、各クライアント端末4、そして、各クライアント端末4で動作するブラウザ5及び端末側情報取得装置7によって構成されている(図1)。
【0097】
第2の実施形態の端末情報取得装置7は、取得した端末情報を利用することで各ユーザのユーザランク値を算出する。本明細書における、「ユーザランク値」とは、各ユーザの特定項目に対する知識の深さや、検索スキル等を基に決定される、ユーザの重要度を数値化した値を示す。算出したユーザランク値は検索用データベース3に端末情報として格納される。
【0098】
ユーザランク値の算出方法は、例えば、上記した端末情報取得装置7が取得した端末情報と、情報収集機能(情報収集部12)が収集したWebページの情報に基づいて、ユーザがブラウザ5を介して出力したWebページの種類や、Webページの閲覧時間、リンクを辿ったときの変遷履歴等に基づいて算出してもよい。
また、端末情報取得装置7をブラウザに組み込むとき、又はソフトウェアのインストール時等に、ユーザの職業や趣味等の個人情報を取得する方法がある。また、ブラウザ5に記録された頻繁に閲覧するWebページへのショートカットの情報を取得するという方法がある。即ち、検索が実行されたときに、検索対象となるWebページをユーザが閲覧しており、且つそのユーザの職業や趣味等がWebページの内容と関連していた場合、そのユーザのユーザランク値を高くするという方法である。
さらに、ユーザが、BBS等で特定の項目と関連する質問に対して回答を行った際に、必要に応じて当該BBS(特定のWebページ)からデータを取得する方法がある。具体的には、ユーザが行った回答に対する他のユーザの評価の情報等を必要に応じて取得する。そして、他のユーザから高い評価を得た回答を行ったユーザのユーザランク値を高くするという方法である。
そしてまた、検索キーワード、検索後に閲覧したWebページ、及び検索後にWebページを閲覧した時間、検索後のWebページからリンクしたページ等を解析することにより、ユーザの検索スキルを判定し、それを基にユーザランク値を付与するという方法が考えられる。
このような、検索内容に対する知識の深さや、検索スキル等を基にユーザを評価する方法から、適宜なものを少なくとも一つ選択し、端末情報取得装置7や情報収集部12に情報を収集させ、検索装置2において解析処理を実行することで、ユーザランク値を決定する。
【0099】
第2の実施形態の端末情報取得装置7では、情報収集部12が収集した情報に基づいて、各Webページのリレーションランク値を算出する。本明細書における、「リレーションランク値」とは、各Webページの内容に特定の単語がどれだけ記載されているか、特定の単語がタイトル等の所定の箇所に記載されているか等の情報を基に決定される、Webページの内容と特定項目との関連性の高さを数値化した値を示す。算出したリレーションランク値は検索用データベース3に端末情報として格納される。
【0100】
次に、本実施形態の情報検索システム1の検索実行時の処理の流れについて説明する。
いずれかのクライアント端末4で検索が実行されると、第1の実施形態と同様の手順によって、検索装置2がランク値演算用行列を設定する。
【0101】
ここで、本実施形態では、検索によって抽出された各WebページA,B,C,Dのリレーションランク値と、抽出された各Webページを閲覧しているユーザE,F,G,Hのユーザランク値を参照してランク値演算用行列の各要素の値を変更する。
【0102】
モデルを用いて具体的に説明すると、図5で示されるモデルにおいて、ユーザFがユーザG,Hに比べてユーザランクが高いユーザであったとする。このとき、図6で示される
ランク値演算用行列Pの要素の値を、図7で示されるランク値演算用行列Pのように変更する。即ち、P(4,2),P(7,2),P(8,2)の値をそれぞれ1/4から1/5に変更し、P(6,2)の値を1/4から2/5に変更している。このことで、WebページBから仮想のWebページFへのリンクの重要度を、WebページBから仮想のWebページG,Hそれぞれへの各リンクの重要度より高くしている。
【0103】
このように、作成したランク値演算用行列の各要素の値を、ユーザランク値とリレーションランク値のいずれか一方又は両方の値に基づき、適宜変更することにより、実在するWebページA,B,C,D、やユーザE,F,G,Hによって定義される仮想のWebページE,F,G,Hの重要度をランク値演算用行列に反映させる。なお、このとき、ランク値演算用行列の各要素の値を変更しても、ランク値演算用行列Pの各「列」の要素の総和は1となる。したがって、図6で示されるランク値演算用行列Pから要素P(6,2)値を変更するとき、1/4から(1+α)/(4+α)(αは0でない数)のように変更される。
【0104】
さらに、必要に応じて各要素の値の変更を行ったランク値演算用行列の固有値を算出する。即ち、遷移確率行列の各要素の値を変更してから演算することで、遷移確率行列の各頂点であるWebページA,B,C,D及び仮想のWebページE,F,G,Hのそれぞれにおける遷移確率に基づく遷移傾向を推定する演算を実施する。そして、算出した固有値に基づいて抽出したWebページを並び替える。
【0105】
また、検索装置2は、並び替えた検索対象となるWebページを検索結果としてクライアント端末4へ送信する。以上で本実施形態の情報検索システム1の検索実行時の処理の流れの説明を終了する。
【0106】
次に第3の実施形態について説明する。
第3の実施形態では、ランク値演算用行列を設定して固有値を算出した後、各固有値あるいは行列の要素に対してユーザランク値やリレーションランク値に基づく値を付加することを特徴とする。
詳説すると、第1の実施形態又は第2の実施形態と同様の手順により、ランク値演算用行列を設定し、固有値を算出する。そして、算出した各固有値を変更し、変更された固有値でWebページの並び替えを実施する。
【0107】
例えば、算出されたWebページA,B,C,Dの固有値が、それぞれ0.408,0.544,0.408,0.544であったとする。そして、このとき、WebページAをユーザランク値の高いユーザが閲覧していたとする。すると、検索装置2は、WebページAの固有値に所定の値を加えて0.608とする。そして、変更したWebページA,B,C,Dに対応する固有値0.608,0.544,0.408,0.544に基づいてWebページA,B,C,Dの並び替えを実施する。このように、ユーザランク値の高いユーザが閲覧しているWebページやリレーションランク値の高いWebページに対応する固有値を変更したのち、Webページの並び替えを実施する。なお、上記した例では、ユーザランク値の高いユーザが閲覧しているWebページやリレーションランク値の高いWebページに対応する固有値に値を付与する例を示したが、固有値の変更方法はこれに限るものではない。例えば、リレーションランク値の低いWebページに対応する固有値の値を差し引いてもよい。固有値の変更は、ユーザランク値又はリレーションランク値に応じて適宜変更してよい。
【0108】
上記した各実施形態では、ランク値演算用行列Pは、検索対象となるWebページA,B,C,Dと上記仮想のWebページE,F,G,HとからなるWebページ群において、各WebページA,B,C,D,E,F,G,Hを頂点とする遷移確率行列なっている。したがって、このランク値演算用行列Pの設定は、例えば、各WebページA,B,C,D,E,F,G,Hを頂点とする隣接行列を作成し、作成した隣接行列を基に遷移確率行列を導出してもよい。ランク値演算用行列Pの設定するときの導出方法は、適宜変更してよい。
【0109】
上記した各実施形態では、検索が実行されたとき、検索クエリの条件を満たすWebページを抽出し、抽出したWebページを閲覧しているユーザを特定して、抽出したWebページとそれを閲覧しているユーザとに対応するランク値演算用行列Pを設定した。しかしながら、本発明の検索システムの検索実行時の処理はこれに限るものではない。
例えば、ネットワーク上の全てのWebページとそれを閲覧しているユーザとに対応するランク値演算用行列P2を予め導出しておき、検索が実行された場合に、予め導出しておいたランク値演算用行列P2から、「行」の要素や「列」の要素から必要な要素を抜き出してランク値演算用行列Pを設定してもいい。即ち、予め導出しておいたランク値演算用行列P2から、必要な「行」の要素や「列」の要素を抜き出し、組み合わせることによって、検索クエリの条件を満たすWebページと、それを閲覧しているユーザとに対応するランク値演算用行列Pを設定してもよい。
【0110】
また同様に、特定の条件を満たすWebページと、それを閲覧しているユーザとに対応するランク値演算用行列P3を予め導出しておき、検索が実行された場合に、予め導出しておいたランク値演算用行列P3から、「行」の要素や「列」の要素から必要な要素を抜き出してランク値演算用行列Pを設定してもいい。
【0111】
上記した各実施形態では、ランク値演算用行列の行要素と列要素において、WebページA,B,C,Dに対応する要素群とユーザE,F,G,Hに対応する要素群とが隣接して形成されるランク値演算用行列を例に挙げて説明したが、本発明のランク値演算用行列はこれに限るものではない。例えば、ランク値演算用行列の行要素と列要素の順番は適宜入れ替わってもよい。また、説明の便宜上、ランク値演算用行列を行列の書式で表しているが、実際に検索システムが演算する際の行列の取り扱いは適宜設定してよい。つまり、行列を形成する各要素、又は行列を形成する各要素の内で演算に必要な要素のみを記憶保持して、必要な計算を実行してもよい。必ずしも、上記したような行列の形状で取り扱わなくてもよい。
【0112】
上記した各実施形態では、検索が実行されたとき、端末側情報取得装置7が予め取得した端末情報と、情報収集部12が予め取得したWebページの構造に係る情報とを検索用データベース3から取得してランク値演算用行列Pを設定したが、ランク値演算用行列の設定方法はこれに限るものではない。例えば、検索が実行されたとき、検索装置2がクライアント端末4から、Webページの閲覧に係る情報を取得する構成であってもよい。また、取得した情報をデータベースに保持させずにランク値演算用行列の設定に使用してもよい。即ち、クライアント端末4から検索装置2への端末情報の送信は、適時実施してもよい。そして、情報のデータベースへの格納は、適時実施してもよく、場合によっては実施しなくてもよい。
【0113】
上記した各実施形態では、Webページを固有値の高い順に並び替えたが、本発明はこれに限らず、例えば、Webページを固有値の低い順に並び替えてもよい。しかしながら、Webページを固有値の高い順に並び替える方法によると、検索実行時に話題性の高いWebページ(例えば、多数のクライアント端末4で出力されたWebページ)が上位に表示されるため、望ましい。
【0114】
また、上記した各実施形態では、検索結果となるWebページを並び替えるとき、Webページの固有値が同じ場合、閲覧者が多いページを上位に表示している。しかしながら、本発明の検索システムはこれに限るものではなく、例えば、Webページの固有値が同じだった場合、閲覧者が少ないページを上位に表示してもよい。
【0115】
上記した各実施形態では、図3に示すように、検索用データベース3及びクライアント端末4から送信された情報を受信、管理する機能が検索装置2に含まれる構成を例に挙げているが、本発明の検索システム1はこれに限定されるものではない。例えば、検索用データベース3をネットワーク上の別途のサーバ装置に設けておき、検索装置2が検索を実行する際に、当該サーバの検索用データベース3から情報を取得するという構成でもよい。即ち、システム全体で機能を実現できればよく、設置するサーバの数及び各機能(プログラム)、データベースの配置は、サーバの能力等により適宜変更可能である。
【0116】
なお、上記した各実施形態のプログラム、及びシステムは、CD−ROM等の光学ディスク、磁気ディスク、半導体メモリなどの各種の記録媒体を通じて、又は電気通信網などを介してダウンロードすることにより、コンピュータにインストール又はロードすることができる。
【実施例】
【0117】
ところで、上記したランク値演算用行列の固有値を求める際の演算は、適宜のハードウェア構成、適宜の演算アルゴリズムで行ってよい。しかし、より高速にランク値演算用行列の固有値を求めるべく、下記の検証を実施した。本発明の情報検索システムは、下記の検証を参考にハードウェア構成及び演算アルゴリズムを選択してもよい。
【0118】
検証を実施するに当たって、LR法やQR法等の古典的な手法は一般的に大きな手間を要するので、固有値が等しく、元の行列よりサイズの小さい行列に変換することで計算時間を削減する「射影法」に基づく手法について検証を行った。Lanzcos,Arnoldi,Krylov−Schur等の射影法に基づく手法は,Gram−Schmidtの手法をベースにした直交化のフェーズと、マルチシフトQR法による固有値計算およびSchur分解のフェーズからなる手法で、分解フェーズでブロックを並べかえることで、最大固有値、最小固有値など,欲しい固有値および固有ベクトルの組から求められる手法である。そのため、最大固有値と対応する固有ベクトルのみが必要なアプリケーションでは、大幅に計算時間を削減できる可能性がある。そのため、「射影法」に基づく手法は、上記したランク値演算用行列の固有値を求める演算に適していると考えられる。
【0119】
これらの射影法を実装したライブラリの中で、大規模行列の計算に対応したものとしてSLEPcがある。SLEPcでは、PETSc、BLAS、LAPACKなどの既存の数値計算ライブラリを用いて、最新の固有値計算手法を実装しており、大幅な計算時間の短縮が期待できる。SLEPcが用いているPETScという数値計算ライブラリでは、OpenMPIを用いてベクトルや行列の演算を複数プロセスで並列処理する機能を備えている。PETScはC言語で記述されており、高速に演算を行える。また、OpenMPIはプロセス間通信方式として、共有メモリ、InfiniBand、TCP/IP等、さまざまな方式をサポートしており、内部で自動的に切り替えてくれるため、準備できる環境に応じて最適な並列化が容易に実現できる。
【0120】
これに対して、一般的な検索サービスでは、常に大規模な分散環境における処理を前提としてシステムを構築している。これらのミドルウェアは、ノード故障等が頻繁に発生する環境で、安定して大量のバッチ処理を実行できるという特徴を有する。しかしながら、冗長化のためのオーバヘッドも大きく、大量の通信を伴う処理では高い性能を出すことができない。
【0121】
つまり、中小規模の計算機環境では密結合な処理の方が高性能で処理できる可能性があるため、本検証では、MPIベースで実装されたクラスタ向けのミドルウェアも含めて調査することにした。
【0122】
まず、OpenMPIで実装されたSLEPcの性能について調査した。詳細には、本発明の情報検索システムが要求するスケーラビリティを実現するため、どの程度のリソースを要するのかを調査した。さらに具体的には、Webページと閲覧者をあわせて10万エントリ程度の計算を実施する場合を想定した性能について調査した。
【0123】
検証における評価環境は以下の通りである。
計算機:PowerEdge R410×2(DELL社製)
CPU:Intel(R) Xeon(R) L5520 (2.26GHz,8MB キャッシュ, 5.86 GT/s QPI) ×2 (コア数4)
メモリ:32GB(4GB×8/2R/1066MHz/DDR3 RDIMM)
ディスク:RAID6(PERC6i),600GB,15,000RPM SAS
ネットワーク:Broadcom NetXtreme II BCM5716 1000Base−T PCIExpress
スイッチ:Cisco Catalyst 2960G−8TC−L
OS:Ubuntu Linux10.04
ライブラリ:PETSc 3.0.0, SLEPc 3.0.0,LAPACK 3.2.1,BLAS 1.2
【0124】
性能評価では、対称行列の例としてラプラシアン行列を用い、非対称行列の例として要素間をランダムに遷移するモデルを想定して生成した遷移確率行列を用いて固有値、固有ベクトルを計算した。本実験で用いたラプラシアン行列は、図8(a)に示したような行列で、対角要素が2、その両脇の要素が1の行列とした。また、遷移確率行列は、三角格子の上をランダムに移動することを想定して生成した図8(b)のような行列とした。本検証ではまず単一ノード内での並列処理性能について評価し、その後TCP/IPを用いて複数ノードでの評価を行なう。
【0125】
実機での評価の前にSLEPcのソースコードから、Arnoldi,Krylov−Schurの実装について調査した。
【0126】
SLEPcで用いられているPETScでは、OpenMPIの集合通信機能を利用し、行列の1行目からn1行目、n1+1行目からn2行目など、指定した範囲で分割して、各プロセッサごとに部分行列を生成、処理する機能を実装している。直交化の計算では、各プロセスに分散配置した部分行列およびベクトルの中間計算結果をギャザ,スキャタ,レデュース等の機能で相互にやりとりする必要があるため、並列化時の通信オーバヘッドが大きくなると考えられる。
【0127】
対して、マルチシフトQRやSchur分解の処理では、注目している部分行列のみに注目して処理できるため、通信オーバヘッドは発生しないと考えられる。以上の点について、実際に性能計測して確認した。
【0128】
PETScでは、−log summaryというオプションにより、プログラムの実行時間、事前設定した箇所の呼び出し回数、実行時間などを分析する機能を提供している。下記の実験では、この−log summaryの機能を用いて性能計測した。
【0129】
またさらに、MPIにおけるオールギャザ、オールレデュース等の集合通信では、プロセッサ数が偶数であることを想定しており、奇数の場合余ったノードの通信は効率的に行えないため、集合通信を多用する計算では偶数個のプロセッサを利用するのが良いと考えられる。実際に奇数n個のプロセッサを利用した場合、偶数n1個のプロセッサ数と同等程度の性能しか得られなかった。そのため、以下の評価では偶数個のプロセッサの性能について評価した。
【0130】
計算対象となる行列の値により実際に並列に実行されるコードが異なってくるので,ソースコードから直接並列化率を求めることはできないが、性能測定結果から指定したパラメータでの並列化率を算出し、ライブラリの性能を評価できると考えられる。以下で求めた並列化率は指定したパラメータでの並列化率である。また、SLEPcでは、求める固有値の許容誤差を指定することで、計算結果が指定した誤差内に収まるまで、反復計算を継続する。以下の実験では許容誤差を10の−7乗として計算した。
【0131】
まず、ラプラシアン行列での計算時間について調査する。
【0132】
調査に当たって、10万×10万のサイズのラプラシアン行列の固有値計算時間を測定した。このとき、まず、同じ反復回数での処理時間を比較した。反復回数を12500回程度に制限すると、このサイズの行列ではどの手法もまだ固有値が収束しないので、同じ繰り返し回数だけ計算される。単一プロセッサで計算したときの処理時間をT1、プロセッサ数nで計算したときの処理時間をTnとしたとき,プロセッサ数を変化させた場合の処理時間比T1=Tnは図9のようになった。
【0133】
利用したハードウェアはノードあたり8コアのプロセッサが利用でき、さらにIntelのHyper Threading技術により、仮想的に16コアのプロセッサが利用できる。しかし、図9に示すように、プロセッサ数が8から9に増えるところで性能が低下している。そこでHyper Threading機能をOFFにして各手法の処理時間をプロセス数8まで測定したところ、プロセッサ数8まではほぼ同様な変化を示した。そのため、複数CPUの利用ではなくHyper Threadingが原因で性能低下していると考えられる。Ubuntuの実装が影響していることも考えられるが、詳細な原因までは調査できていない。このことを受け、以下の実験ではHyper Threading機能をOFFにして評価を実施した。
【0134】
プロセッサ数8までの結果では、アムダールの法則が示すとおりプロセッサ数の増加に対して処理時間比の伸びが鈍化している。プログラム中で並列化されている部分の割合(並列化率:Parallel Portion)をr(0<=r<=1)とし、プロセッサ数をnとすると、オーバヘッドを無視した並列処理部分の処理時間はrT1=n、逐次処理部分の処理時間は(1―r)T1なので、処理時間比Speedupは下記〔数1〕のようになっている。
【0135】
【数1】
【0136】
計測した値から最小二乗法でrを推定すると、Lanzcos,Arnoldi,Krylov−Schurでそれぞれ、およそ0.9653(96.53%),0.9720(97.20%)0.9583(95.83%)という値になった。なお、図9中の直線は理想的な性能,曲線は推定した曲線を表す。オーバヘッドを無視した式で推定しているため、観測値と推定曲線にはずれがある。8プロセッサでの計測値が近似曲線よりも下に来ているので、10プロセッサ以上の性能を測定して再計算すれば、並列化率は低下すると考えられる。次に、それぞれの手法における8プロセッサでの並列化効率(ParallelEfficiency)を調べた。並列化効率PEは、処理時間比をプロセッサ数で割った値であるため百分率で表すと、下記〔数2〕のようになっている。
【0137】
【数2】
【0138】
並列化効率は、Lanzcos,Arnoldi,Krylov−Schurbで、それぞれ、およそ74.58%,76.11%,68.87%となり、Arnoldiが最も良い数値を示した。
【0139】
対称行列での並列化効率は3手法とも、8プロセッサまでであれば50%は割り込まないが、それ以上になると並列化効率が低下する可能性がある。例えば、大規模なシステムであれば、システムの利用効率を維持するため,50%の並列化効率に満たないジョブの投入を断るという事例がある。したがって、今後、本発明の情報検索システムで要求される処理性能の実現に8ノード以上が必要であることが判明し、かつ、8プロセッサ以上で並列化効率が50%を割り込むことが判明した場合は、ハードウェア追加による投資対効果を得るために、他のライブラリや計算手法の利用が考えられる。
【0140】
3手法の繰り返し回数12500回の計算時間を比較したグラフを図10に示す。対称行列では、Lanzcosの計算時間が最も少ないことが分かる。非対称行列も計算可能な残りの2手法では、Krylov−Schurがより計算時間が短いことが分かる。ただし、これらは繰り返し回数を等しくした場合の計算時間であり、実際には各手法で固有値が収束するまでに必要な繰り返し回数は異なっている。例えば、今回調査した中ではArnoldiは36534回の繰り返しで収束している。
【0141】
次に生成した遷移確率行列での計算時間について調査した。
【0142】
生成した行列は非対称行列であり、遷移確率行列であるため、ラプラシアン行列よりも対象とするWebページのリンク構造に近い行列となっている。行列の列方向の値の和が1になるように行列を生成するため制約条件があり、行列のサイズは中途半端な値となる。今回281625というサイズの行列を用いた。また、繰り返し回数は各手法で固有値が収束しない500回に制限して実施した。Lanzcosは対称行列を対象とした計算手法であるため、非対称行列については、Arnoldi,Krylov−Schurの2手法について比較した。Krylov−Schurでは、行列が対称の場合、部分的に計算アルゴリズムをLanzcosをベースとした計算手法に切り替えているため、非対称の場合では性能特性が異なっている。
【0143】
図11にプロセッサ数を変化させた場合の処理時間比T1=Tnの結果を示す。最小二乗法で推定した並列化率は、Arnoldi,Krylov−Schurがそれぞれ0.817591(81.75%), 0.839298(83.92%)となっており、非対称行列ではArnoldi,Krylov−Schurともに対称行列の場合と比べて並列化率が低下している。同様に、プロセッサ数を変化させた場合の並列化効率(Parallel Efficiency)の結果を図12に示す。Arnoldi,Krylov−Schurともにプロセッサ数8で並列化効率が50%を切っており、上述の例を考えると現在の実装では効果的にCPUを利用できていないおそれがある。
【0144】
しかし、遷移確率行列は疎行列であるため固有値の収束が速く、収束までの繰り返し回数が少ない。実際に収束までにかかった繰り返し回数は、手法やプロセッサ数によって差があるが、Krylov−Schurでは、1157回以内で収束することが確認できた。処理時間は2プロセッサでおよそ102.2秒,56.77秒であり、ラプラシアン行列の場合の1/4程度の処理時間となっている。そのため、必要となるプロセッサ数も少なくなると考えられる。
【0145】
次に、通信オーバヘッドの影響を調査するため、単一ノードと複数ノードで計算した場合を比較した。具体的には、1ノードで実行した場合と2ノードで実行した場合を比較した。なお、評価はTCP/IPで実施した。
【0146】
遷移確率行列は疎行列であるため、固有値の収束が速く、計算の繰り返し回数が少なくなる。そのため、計算の繰り返し回数が多くなるラプラシアン行列の計算結果で確認した。2プロセッサを利用した計算で、繰り返し回数を変化させた場合の処理時間について、図13に示す。
【0147】
単一ノードで処理した場合に比べて、MPI関連の関数呼び出し時間は大きくなるが、その他の部分の処理時間の関係で、複数ノードを利用した方が性能が良くなっているケースがある。これらは、Open MPIのドライバの実装等に依存している可能性がある。本検証の結果より、今後、情報検索システムが要求する性能が単一ノードのプロセッサ数では実現できないと判明した場合、今回調査した性能向上率で対応できる範囲であれば、ノード間通信を利用してプロセッサを追加することで対応できる可能性がある。
【0148】
以上で、MPIベースで実装されたクラスタ向けのミドルウェアも含めた固有値計算の処理速度に関する検証の説明を終了する。
【0149】
上記した検証では、SLEPcに実装されたPower(べき乗)法についての検証を行っていないが、この方法も本発明の情報検索システムに好適に使用できる可能性がある
【0150】
上記した検証では、ランキング機能の固有値計算部分の高速化についてのみ検討を行った。しかし、実際にはページ間のリンク構造を取得して遷移確率行列として固有値計算プログラムに入力する必要がある。行列サイズが大きくなると、入出力がボトルネックになる可能性がある。ここで、MPIでは並列入出力の機能を備えており、これを利用することで入出力による性能低下を回避できる可能性がある。また、PETScは疎行列を効率的に格納するデータ構造をサポートしているため、メモリ使用量を抑えることができる。
【0151】
上記した検証によって、並列計算ライブラリSLEPcを用いることで、8コア程度のPCで、数十万規模の遷移確率行列の固有値および固有ベクトルの計算が数十秒で完了できることが確認された。
【符号の説明】
【0152】
1 情報検索システム
10 端末情報取得部(情報取得手段)
13 検索実行部(情報序列化手段)
【技術分野】
【0001】
本発明は、WWW(World Wide Web)の情報検索システムにおいて、目的の情報を効率良く容易に取得するための技術に関する。
【背景技術】
【0002】
WWWの膨大な情報の中から目的の情報を得ようとする場合、検索システムを利用して該当するWebページを特定することが一般的である。このような検索システムでは、ユーザが入力した検索キーワードに該当するWebページを特定して集め、集められたWebページに重要度を付けて重要度の高いものから順に提示している。
【0003】
ここで、集められたWebページに重要度を付ける技術として、Webページ内の名詞の出現数やリンク構造等を基準にWebページのランク付けを行う技術が広く知られている。具体的には、例えば、ユーザが入力した検索キーワードがタイトル等の重要な箇所で使用されているWebページや、ユーザが入力した検索キーワードが適度に多く出現するWebページに対して高い重要度を付ける方法が知られている。また、他のWebページから数多くリンクされているWebページや、内容の関連性が高いWebページからリンクされているWebページに対して高い重要度を付ける方法が知られている。
【0004】
しかしながら、このようにWebページの内容やリンク構造だけを基準にWebページの重要度を規定すると、ユーザが検索用語を上手く選定できない場合、目的とする情報が開示されたWebページが上位に表示されず、ユーザが目的とする情報が開示されたWebページを発見できないという問題があった。さらにまた、目的とする情報が開示されたWebページを特定できた場合であっても、目的とする情報が難解であった場合、ユーザが深い理解を得られないという問題があった。
【0005】
そこで本発明者らは、このような問題に鑑み、検索結果として集められた各Webページの人気や話題性、記載内容の精度等に基づいてWebページに重要度を付け、重要度の高いものから順に提示することができる情報検索システム及び情報検索方法を先の出願(特許文献1)により提案した。
【0006】
具体的に説明すると、本発明者らが提案した情報検索システムでは、検索結果として集められた複数のWebページを、検索実行時にそれぞれのWebページを閲覧しているユーザの数が多い順に並び替えて検索結果を表示することができる。即ち、検索実行時に多くのユーザが注目しているWebページとは、検索実行時において話題性(必要性)の高いWebページであり、そのようなWebページを検索結果の上位に表示することによって、検索実行時に必要性が高い情報を取得し易くしている。
【0007】
また、本発明者らが提案した情報検索システムでは、予め情報検索システムを使用する全てのユーザの情報を取得しておき、取得した情報を検索結果に反映することができる。例えば、ある特定のユーザが検索を実行したとき、検索結果として集められたそれぞれのWebページをどのようなユーザが閲覧しているのか情報検索システムが判別し、特定の条件を満たしたユーザが閲覧しているWebページを上位に表示する。例えば、検索を実行したユーザが「プログラム」というキーワードで検索を実行したのであれば、「職業」が「プログラマ」であるユーザが閲覧しているWebページが上位に表示される。このように、検索結果として集められたWebページに、検索のキーワードに関連する分野の専門家であるユーザが閲覧しているWebページあれば、そのWebページを上位に表示する。即ち、専門家が多く閲覧しているWebページは内容が充実した(内容の精度が高い)Webページであり、そのようなWebページを検索結果の上位に表示することによって、ユーザが精度の高い情報を取得し易くしている。
【0008】
そして、本発明者らが提案した情報検索システムでは、検索実行後に特定したWebページを閲覧するとき、同じWebページを閲覧している他のユーザと通信可能となっている。そのことにより、特定したWebページの内容が難解であった場合であっても、他のユーザに質問することで、ユーザはWebページの内容に対する理解を深めることができる。
【先行技術文献】
【特許文献】
【0009】
【特許文献1】特開2011−39625号公報
【発明の概要】
【発明が解決しようとする課題】
【0010】
上記したように、検索結果として集められた各Webページの人気や話題性、記載内容の精度等に基づいてWebページに重要度を付け、重要度の高いものから順に提示する情報検索システムによると、ユーザが真に必要とする情報をより容易に取得できる。そこで本発明は、人気や話題性、記載内容の精度等を反映したWebページの重要度の算出がより正確に実施可能であり、算出したWebページの重要度を反映した検索結果を短時間で出力可能な情報検索システム及び情報検索方法を提供することを課題とする。
【課題を解決するための手段】
【0011】
上記課題を解決するための本発明の一態様は、検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、検索対象となるWebページを序列化する情報序列化手段を有するものであり、情報序列化手段は、検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施する機能を備えたことを特徴とする情報検索システムである。
なお、「遷移傾向を推定する演算」とは、実際の遷移確率の演算に加えて、遷移確率の演算に必要な要素に改変を加えた上で行う演算を含む。また、「遷移」とは、Webページ又は端末を頂点とし、特定のWebページからリンクを辿って他のWebページを表示することとする。さらに、特定の端末による特定のWebページの出力があったとき、特定のWebページを含む2つのWebページの間にリンクが形成されているものと同様な遷移が想定されるものとする。
また、このとき想定される「特定のWebページを含む2つのWebページの間にリンクが形成されているものと同様な遷移」は、「2つのWebページの間に相互リンクが形成されているものとする遷移」とすることが望ましい。なぜなら、「2つのWebページの間にいずれか一方のWebページから他方のWebページにリンクが形成されているものとする遷移」が想定された場合に比べて、ユーザに閲覧されることによるWebページの重要度の上昇がより正確に反映されるためである。
【0012】
本発明の第二の態様は、遷移確率の演算は、検索対象となるWebページと検索対象となるWebページに対して現にあるいは一定期間内に接続された端末を含む構成によって正方行列を設定し、当該正方行列の固有ベクトルを演算する演算内容を含むことを特徴とする請求項1に記載の情報検索システムである。
【0013】
本発明の第三の態様は、前記正方行列の要素は、Webページがリンクしているリンク先の数に基づく値と、端末が現にあるいは一定期間内に接続したWebページの数に基づく値によって構成されていることを特徴とする請求項2に記載の情報検索システムである。
【0014】
本発明の第四の態様は、前記正方行列の要素は、Webページがリンクしているリンク先の数に基づく値をAとし、端末が現にあるいは一定期間内に接続したWebページの数をBとしたとき、A/(A+B)、B/(A+B)あるいはこれらに系数が掛けられた値であることを特徴とする請求項2又は3に記載の情報検索システムである。
【0015】
本発明の第五の態様は、検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定するものであって、前記出力端末を仮想のWebページとし、出力端末が出力しているWebページと仮想のWebページとの間に相互リンクが形成されるとしたとき、Webページ及び仮想のWebページによって形成されるリンク構造に基づき、リンク元のWebページの表示からリンク先のWebページの表示への切り替えを遷移とした遷移確率行列を設定し、設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるWebページを序列化することを特徴とする請求項1乃至3のいずれかに記載の情報検索システムである。
なお、上記リンク構造には仮想のリンクを含み、上記リンク元のWebページ又は上記リンク先のWebページには、仮想のページを含むものとする。
【0016】
このような情報検索システムによると、人気や話題性、記載内容の精度等を反映したWebページの重要度の算出がより正確に実施可能であり、算出したWebページの重要度を反映した検索結果を短時間で出力可能となっている。したがって、並び替えの基準となる項目が多くなる等によって計算量が膨大になってしまった場合であっても、短時間で検索結果を取得することができる。
【0017】
本発明の第六の態様は、前記端末情報に基づいて、前記出力端末を使用する使用者の特定項目に対する知識及び/又は使用者の検索能力に対するユーザの重要度を示すユーザランク値を算出するものであり、
前記ユーザランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び/又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項2乃至5のいずれかに記載の情報検索システムである。
【0018】
本発明の第六の態様では、特定項目に対する知識が高いユーザや検索能力が高いユーザが閲覧している、内容の充実したWebページを上位に表示させることができる。そのことにより、ユーザが検索実行時に必要性の高い情報を容易に取得することができる。
【0019】
本発明の第七の態様は、ネットワーク上のWebページの内容に関する情報を取得可能な情報取得機能を有し、情報取得機能が取得した情報に基づいてWebページの内容の重要度を示すリレーションランク値を算出するものであり、前記リレーションランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び/又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項2乃至6のいずれかに記載の情報検索システムである。
【0020】
本発明の第七の態様では、検索条件と関連性の高い内容のWebページを上位に表示させることができる。そのことにより、ユーザが検索実行時に必要性の高い情報を容易に取得することができる。
【0021】
本発明の第八の態様は、端末で入力されたキーワードに基づいてデータベースの検索を行なうと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、検索対象となるWebページを序列化する情報序列化手段を有するものであり、情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定し、前記Webページと出力端末に基づいて正方行列を設定するものであって、前記正方行列はWebページ及び出力端末に対応する行要素及び列要素から形成されるものであり、その各要素P(i,j)は下記式(1)の関係を満たすものであり、設定した前記正方行列の固有ベクトルを算出し、算出した固有ベクトルの成分の大きさに基づいて検索対象となるWebページを序列化することを特徴とする情報検索システムである。
P(i,j)= αX/Y ・・・(1)
α =0以外の数
X = 列「j」に対応するWebページから行「i」に対応するWebページへのリンクの数、又は、列「j」に対応するWebページの行「i」に対応する出力端末での表示数、又は、列「j」に対応する出力端末での行「i」に対応するWebページの表示数、又は0
Y = 列「j」に対応するWebページの出力端末での表示数と、列「j」に対応するWebページに形成されているリンク数の総和
【0022】
本発明の第九の態様は、検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索方法であって、検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施することを特徴とする情報検索方法である。
【0023】
本発明の第十の態様は、検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得し、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定するものであり、前記出力端末を仮想のWebページとし、出力端末が出力しているWebページと仮想のWebページとの間に相互リンクが形成されるとしたとき、Webページ及び仮想のWebページによって形成されるリンク構造に基づき、リンク元のWebページの表示からリンク先のWebページの表示への切り替えを遷移とした遷移確率行列を設定し、設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるWebページを序列化することを特徴とする請求項9に記載の情報検索方法。
【0024】
本発明の第九の態様及び第十の様態では、検索実行時において人気の高い情報を有するWebページや、ものごとに対する興味が似ているユーザ、検索目的の分野に精通しているユーザ等が閲覧するWebページ等が検索結果の上位に表示されるため、必要性が高い情報や質の高い情報を取得し易い。また、そのような検索結果を短時間で出力できる。
【発明の効果】
【0025】
本発明は、検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行い、その検索結果を前記端末に出力して表示させるための情報検索システムにおいて、Webページの人気や話題性、記載内容の精度等を反映した検索結果をより速く出力できるという効果がある。
【図面の簡単な説明】
【0026】
【図1】本発明の第1の実施形態に係る情報検索システムの構成を示す概念図である。
【図2】本発明の第1の実施形態に係る情報検索システムの機能ブロックの一例を示す図である。
【図3】本発明の第1の実施形態に係る情報検索システムのハードウェア構成の一例を示す図である。
【図4】本発明の第1の実施形態に係る情報検索システムによる検索手順の一例を示すフローチャートである。
【図5】本発明の第1の実施形態に係る情報検索システムで検索を実施する際に検索対象となるWebページのリンク構造、及び当該Webページの閲覧状況の一例を示す説明図である。
【図6】本発明の第1の実施形態に係る情報検索システムで検索を実施する際に設定するランク値演算用行列の一例を示す説明図である。
【図7】本発明の第2の実施形態に係る情報検索システムで検索を実施する際に設定するランク値演算用行列の一例を示す説明図である。
【図8】本発明の実施例において固有値演算の速度を検証するために用いた行列を示す説明図であり、(a)はラプラシアン行列を示し、(b)は遷移確率行列を示す。
【図9】本発明の実施例において、ラプラシアン行列の固有値演算におけるプロセッサ数を変化させたときの処理時間比を示すグラフである。
【図10】本発明の実施例において、ラプラシアン行列の固有値演算における処理時間を示すグラフである。
【図11】本発明の実施例において、遷移確率行列の固有値演算におけるプロセッサ数を変化させたときの処理時間比を示すグラフである。
【図12】本発明の実施例において、遷移確率行列の固有値演算における並列化効率を示すグラフである。
【図13】本発明の実施例において、複数ノードでのラプラシアン行列の固有値演算におけるネットワーク性能の影響を示すグラフである。
【発明を実施するための形態】
【0027】
本発明の実施形態に係る情報検索システム、並びに情報検索方法の提供方法についてそれぞれ図面を参照しながら詳細に説明する。
【0028】
図1は、第1の実施形態の情報検索システム1の構成の概略を示す概念図である。図1に示す様に、情報検索システム1は、検索装置2とクライアント端末4(図1では符号4a〜4d及び・・・で示す)で構成されており、それぞれ電気通信網を介して接続されている。クライアント端末4にて、それぞれブラウザ5(図1では符号5a〜5d及び・・・で示す)が起動されている。
【0029】
第1の実施形態の情報検索システム1は、入力情報を取得可能となっている。具体的には、この入力情報は、ブラウザ5にプラグイン形式等の所定の手段で組み込んだ端末側情報取得装置7で取得され、検索装置2へ送信される。なお、入力情報とは、ユーザがブラウザ5やブラウザ5と連動するプログラム(例えば、プラグインツールバー等)を介して入力した検索キーワード等に関する情報である。
【0030】
また端末側情報取得装置7は、上記した入力情報だけでなく、ブラウザ5を介したWebページの出力に関する情報である使用情報も検索装置2へ送信することができる。具体的には、端末側情報取得装置7は、使用情報として、ブラウザ5における規定のWebページの表示開始時間や表示終了時間といったWebページの表示時間に関わる情報を検索装置2へ送信することができる。さらに、使用情報として、規定のWebページからリンクを辿って他のWebページを表示させた場合に、移動元のWebページのURLや移動先のWebページのURLといったWebページの遷移経路を示す情報を検索装置2へ送信することができる。
【0031】
このように、端末側情報取得装置7は、上記したような入力情報や使用情報を端末情報として検索装置2へ送信する。このとき、端末側情報取得装置7による情報の送信は、ブラウザ5が起動された場合、検索が実行された等の所定の操作が実行された場合、前回情報の送信が終了してから規定時間が経過した場合、といった所定のタイミングに自動で実施される。
【0032】
一方、検索装置2では、端末側情報取得装置7から送信された端末情報を検索用データベース3に格納する。即ち、ネットワーク上の各クライアント端末4(4a〜4d,・・・)から検索装置2に送信された端末情報が、検索装置2の検索用データベース3に格納される(図2)。
【0033】
また、検索装置2は情報収集部12を有している。この情報収集部12は、所謂クローラとインデクサの機能を有するものであって、WWW上を巡回し、リソースに関する情報を取得し、まとめて、検索用データベース3に蓄積する。そして、検索用データベース3に蓄積するときは、Webページのリンク構造に関する情報や、記載されているテキスト、タイトル、各種タグ等の内容に関する情報を特徴毎に解析、選別、分類し、検索しやすいようにしておく。
【0034】
情報検索システム1は、いずれかのクライアント端末4で検索が実行されると、入力された検索キーワードより、検索クエリを作成してサーバである検索装置2に送信する。
【0035】
検索装置2で検索クエリを受信すると、検索装置2の検索実行部13は、検索用データベース3に蓄積されたWebページの中から検索対象となるWebページを特定する。また、特定されたそれぞれのWebページを閲覧している、又は閲覧したユーザの数を特定する。そして、詳しくは後述するが、これらの情報に基づいて形成されるランク値演算用行列の固有値を算出し、算出した固有値を検索対象となる各Webページのランク値(重要度の値)とする。
【0036】
さらに検索実行部13は、検索結果のWebページを取得したランク値に基づいて並び替える。そして、検索装置2の検索結果出力部15が、検索が実行されたクライアント端末4に検索結果を送信し、クライアント端末4で検索結果のWebページが並び替えた順に表示される。
このことにより、検索実行時に人気が高く、話題性のあるWebページを検索結果の上位に表示させることができる。
【0037】
以下、本実施形態の情報検索システム1についてより詳細に説明する。
【0038】
まず、本実施形態の情報検索システム1の機能的構成について説明する。
なお、以下に記載する本実施形態の情報検索システム1の各機能ブロックは、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの両方として実現され得る。具体的には、コンピュータを利用するものであれば、CPUや主メモリ、バス、あるいは不揮発性メモリや、所謂外部記憶装置(ハードディスクやフロッピーディスク(登録商標)、MO、CD、DVD、BD、磁気テープ等々の記憶装置、及びそれらメディアの読み取り装置)、印刷機器、表示装置、その他外部周辺装置等のハードウェア構成部、またその外部周辺装置用のI/Oポート、それらハードウェアを制御するためのドライバプログラムやその他アプリケーションプログラム、情報入力に利用されるユーザーインターフェース等が挙げられる。
【0039】
そして主メモリ上に展開したプログラムに従ったCPUの演算処理によって、インターフェースを介して入力され、各種メモリやハードディスク上に保持されているデータなどが加工、蓄積されたり、上記各ハードウェアやソフトウェアを制御するための命令が生成されたりする。また、本発明はシステムとして実現できるのみでなく、方法としても実現可能である。加えて、本発明の一部をソフトウェアとして構成することができる。そして、そのようなソフトウェアをコンピュータに実行させるために用いるソフトウェア製品、及び同製品を記録媒体に固定した記録媒体も、当然に本発明の技術的な範囲に含まれる(本明細書の全体を通じて同様である)。
【0040】
図2は、本実施形態の情報検索システム1における機能ブロックの一例を示す図である。この図にあるように、本実施形態の検索システム1は、主に端末側情報取得装置7と検索装置2から構成されている。
【0041】
端末側情報取得装置7は、端末情報取得部10と端末情報送信部11とを少なくとも有している。
【0042】
端末情報取得部10は、クライアント端末4のブラウザから、少なくとも閲覧URLを含む、端末情報を取得する機能を有する。ここで閲覧URLとは、ブラウザを介して表示された(クライアント端末4でユーザが閲覧していた)WebページのWeb上(ネットワーク上)での所在を示す情報であり、例えば、「http://・・・/ABC.jpg」のように記述される情報である。
ここで、ブラウザから端末情報を取得する手段は、特に限定されるものでなく、適宜の方法を用いてよい。これらの方法は、例えば、API(Application Program Interface)やDDE(Dynamic Data Exchange)、OLE(Object Linking and Embedding)やファイルシステム等が挙げられる。
【0043】
また端末情報取得部10が取得する端末情報には、閲覧URL以外にもブラウザでのWebページの閲覧に関する各種情報が含まれてよい。これらの情報には、例えば、システム利用者のユーザID、ブラウザID、Webページの閲覧開始時刻、Webページの閲覧終了時刻、あるいは、リンクを辿って2以上のWebページを閲覧した際の「移動元Webページ」や「移動先Webページ」などの移行情報などが挙げられる。
さらに、端末情報には、特定のWebページにおいて、ユーザが入力した検索キーワード等の入力情報が含まれてよい。
【0044】
ユーザIDとはユーザを識別するための情報を示し、例えば、クライアント端末4へのログイン時のIDや、サービス単位又はソフトウェア単位で割り当てられるIDなどが挙げられる。ブラウザIDも同様に、ブラウザを識別するための情報であり、例えば、これらの情報は予めブラウザプログラムやツールバープログラムに記録されている製品IDなどを利用することで取得することができる。
そして、これら識別情報を利用することでクライアント端末4を識別することができるので、クライアント端末4(ユーザ)単位での閲覧情報の管理、分析を行うことができる。なお、これらID情報の保持は、例えば、端末側情報取得装置7自身が保持する方法や、ブラウザが有するcookie機能を利用する方法等、適宜な方法で行われる。
【0045】
閲覧開始時刻とは、ブラウザにてWeb上のWebページにアクセスした時刻、あるいはそのアクセスによってブラウザにWebページが取得された時刻や、表示された時刻などをいう。具体的に説明すると、当該時間は、例えば、ブラウザにてリクエストを行ったリソースのロード完了を検出した時刻や、WebサーバがHTTPステータスコード(例えば、「200:OK」と記述されるコード)等の信号を応答した時刻等が挙げられる。
【0046】
閲覧終了時刻とは、ブラウザにてWebページの表示を終了した時刻をいい、例えば、ブラウザのUIウィンドウがクローズした時刻や、当該ウィンドウがアクティブでなくなった時刻、ウィンドウ領域内からマウスポインタが検出されなくなった時刻(マウスポインタがウィンドウ領域外へ移動した時刻)等が挙げられる。また、一定時間の操作がないためクライアント端末4のOSが自動的にログオフ処理を行ったり、スクリーンセーバ等が起動したりした場合には、それらが行われた時刻を閲覧終了時刻としてもよい。
【0047】
移行情報とは、2以上のWebページを連続で閲覧した際の「移動元Webページ」と「移動先Webページ」を示す情報のことであり、例えば、ハイパーリンクのクリックによる移行(遷移)の他、ブラウザやツールバーのURL入力欄に連続で入力された2以上のURLを「移動先」、「移動元」とする移行情報などが挙げられる。
【0048】
端末情報送信部11は、取得した端末情報を所定の検索装置2に送信する機能を有する。具体的には、当該端末情報を、クライアント端末の通信I/Fを使用し通信回線等を介して、所定の検索装置2(サーバ装置)に自動送信する機能を有する。
なお、端末情報の送信先となる所定の検索装置2の送信先アドレスは、例えば端末側情報取得装置7のプログラム内に予め記述されることで特定する方法などが挙げられる。
また、この端末情報送信部11から端末情報が送信されるタイミングは、適宜のタイミングに設定可能である。例えば、ブラウザにて表示されているWebページが切換わるごとに送信するといったタイミングや、一定の時間、又は時刻が到来した際にバッチ処理で送信するタイミング、あるいはツールバー起動時または終了時に送信するタイミングなどが挙げられる。
【0049】
このように、各クライアント端末4でのブラウザ5を介したWebページの出力(表示)に対する端末情報が、端末側情報取得装置7によって取得され、検索装置2に送信される。そして、検索装置2で当該端末情報が収集されることにより、クライアント端末4で閲覧している、又は閲覧されたWebページが特定できる。つまり、各クライアント端末4のブラウジング(閲覧)履歴を容易に把握することができる、
【0050】
次に検索装置2の機能的構成を説明する。
【0051】
検索装置2は、サーバ装置であって、検索用データベース3、情報収集部12、検索実行部13、検索結果出力部15を有している。
【0052】
検索用データベース3は、クライアント端末4から送信される端末情報を受信、管理、蓄積する機能を有するデータベースである。
【0053】
情報収集部12は、上記したように、WWW上を巡回し、Webページの構造や内容に関する情報を取得し、取得した内容に基づいてインデックスファイルを作成することができる。また、作成したインデックスファイルを検索用データベース3に格納、保存することができる。
【0054】
検索実行部13は、いずれかのクライアント端末4で検索が実行された時に、ユーザからの検索キーワード等に基づいて、検索用データベース3に格納された情報を参照し、検索を実行する。具体的には、検索用データベース3を参照することにより、検索対象となるWebページを特定し、加えて特定した各Webページを出力している端末数を特定する。そして、詳しくは後述するが、これらの情報に基づいて形成されるランク値演算用行列の固有値を算出し、算出した固有値を検索対象となる各Webページのランク値(重要度の値)とする。またさらに、取得したランク値を用いて検索結果となるWebの並び替えを実行する。
【0055】
検索結果出力部15は、検索用データベース3から抽出し、並び替えを実行した検索結果をクライアント端末4のブラウザ5に表示する機能を有する。具体的には、クライアント端末の送信先アドレスを適宜の方法で取得する。ここで、適宜の方法とは、検索クエリと同時に受信する方法や、ユーザIDとあらかじめ登録しておいたIPアドレスを照合する方法等がある。そして、端末側情報取得装置7を介して、特定したクライアント端末4のブラウザ5上で検索結果画面を表示する。
【0056】
次に、本実施形態における、情報検索システム1のハードウェア的構成について説明する。
図3は上記した機能的な各構成要件を、ハードウェアとして実現した際の、情報検索システム1における構成の一例を表わす概略図である。この図を利用して、本実施形態の検索システム1におけるそれぞれのハードウェア構成の働きについて説明する。図3にあるように、本実施形態の情報検索システム1のハードウェア構成は、クライアント端末4に組み込まれた端末側情報取得装置7と、サーバ装置としてネットワーク上に配置されている検索装置2により構成される。
【0057】
端末側情報取得装置7と検索装置2は電気通信回線を介して相互に接続され、情報の送受信を行う。なお、電気通信回線はインターネットを含む。
【0058】
端末側情報取得装置7においては、端末情報取得部10を実現し、またその他各種演算処理を行うCPU(中央演算装置)とRAMや、端末情報送信部11である通信I/Fを備える。またキーボード、マウス等の入力装置であるUI(User Interface)や、ブラウザプログラムにて処理されたリソースを表示するためのVRAMや、ディスプレイなどの表示装置も備える。そしてそれらがシステムバスなどのデータ通信経路によって相互に接続され、情報の送受信や処理を行う。
【0059】
端末側情報取得装置7のRAM上には、ブラウザプログラムと、プラグインプログラムとが格納されており、これらプログラムに従い端末情報の取得や送信処理やその他処理に係るCPUの各種演算処理が実行される。また上記プラグインプログラムによって、RAM上の所定のアドレスには閲覧URLやユーザID等の端末情報を格納する領域が確保されている。
【0060】
一方、検索装置2においては、各種演算処理を行うCPUと、RAMと、通信I/Fと、大量の端末情報等を蓄積するためのハードディスクなどの外部記憶装置とを有している。そしてそれらがシステムバスなどのデータ通信経路によって相互に接続され、情報の送受信や処理を行う。
【0061】
また検索装置2のRAM上には、検索実行部や検索結果出力部の各機能を実現するプログラムやデータベース管理プログラム(図示せず)等の情報検索システム1の機能を実現する各プログラムが格納されており、当該プログラムに従い端末情報の管理処理やその他処理に係るCPUの各種演算処理が実行される。
【0062】
ここで、端末側情報取得装置7では、ユーザのUIを介した操作入力を受け付け、RAM上のブラウザプログラムおよびプラグインプログラムに従い以下のような処理が実行される。
【0063】
例えば、UIを介したブラウザ操作によってWebページへのアクセス指示が入力されると、そのアクセス指示で指定されたWebページのURLがRAMの所定アドレスに格納される。すると、ブラウザプログラムに従い指定されたURLに対して、HTTPリクエストがクライアント端末4から検索装置2へ送信される。そして、そのHTTPリクエストに対するレスポンスをアクセスリソースのコンテンツとして通信I/Fにて該クライアント端末4が受信する。続いてクライアント端末4が受信したコンテンツに含まれるHTMLファイル、イメージファイルなどを、ブラウザ5が有するHTMLレンダリングエンジンなどに従ったCPUの演算処理よってレンダリング処理する。そしてその処理結果がVRAMに転送され、表示装置上にWebコンテンツが表示される。それから、ユーザは表示された当該WWW上のWebページなどのリソースを閲覧する。
【0064】
また、それとともに前記ブラウザでのアクセス指示入力に応じてプラグインプログラムは次の処理を実行する。即ち、RAMの所定アドレスに格納されたURLを端末情報として、前述のような所定の各タイミングで通信I/Fから検索装置2に自動送信する、という具合である。
【0065】
これに対して、検索装置2では、通信I/Fにて各クライアント端末4の端末側情報取得装置7から送信されてきた端末情報を受信し、RAMの所定アドレス等に格納する。そして、検索装置2のプログラムにしたがって、例えば、端末情報に含まれるURLやユーザIDなどをパラメータとして、CPUの演算処理によって検索用データベース3のファイルを作成又は、作成されている検索用データベース3のファイルに追記し、HDD等の外部記憶装置に格納する、という具合である。
【0066】
また、UIによるブラウザ操作によって、検索エンジン(検索用Webページ)にアクセスし、検索クエリの入力、送信を行なった場合や、ツールバーに検索クエリの入力、送信を行った場合のように、クライアント端末4にて検索が実行された場合について説明する。その際、検索装置2は通信I/Fにて該検索クエリを含むHTTPリクエストを受信し、RAMの所定アドレスに格納する。すると、検索装置2では検索サーバプログラムに従い以下の処理を実行する。即ち、RAMに格納されている検索クエリをキーとして、外部記憶装置に保存されている、インデックスファイルデータベースの中から、検索クエリの条件を満たすWebページを抽出する。続いて、CPUの比較演算処理によって、抽出されたWebページの情報と外部記憶装置に保存されている端末情報(端末側情報取得装置7から送信された端末情報)とを比較演算することにより、抽出されたWebページを出力している端末を特定する。そして、詳しくは後述するが、抽出されたWebページのリンク構造と、抽出されたWebページが出力された端末の情報からランク値演算用行列を設定する。さらにまた、設定されたランク値演算用行列の固有値を規定のアルゴリズムに基づいて算出することにより、抽出された各Webページのランク値を取得し、CPUの比較演算処理によって、抽出されたWebページをランク値の高い順に並び替える。加えて、検索装置2は、Webページを並べて箇条形式とした検索結果をCPUの演算処理によって生成し、通信I/Fにより検索クエリの送信元のクライアント端末4のブラウザ5に対して送信する、と言う具合である。
【0067】
次に、本実施形態の情報検索システム1の検索実行時の処理の流れについて説明する。
図4は、本実施形態の情報検索システム1の検索実行時の処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【0068】
いずれかのクライアント端末4で検索が実行され(ステップ101でYesの場合)、クライアント端末4から検索装置2に検索クエリが送信されると、検索クエリを受信した検索装置2が検索用データベース3から検索クエリの条件を満たすWebページを抽出する(ステップ102)。即ち、検索クエリをキーワードにして該当するインデックスファイルを検索する。
【0069】
さらに検索装置2は、抽出したWebページのデータと、検索用データベース3に格納された端末情報とを比較することにより、抽出したWebページを出力している端末を特定する(ステップ103)。即ち、各クライアント端末4から送信された、ブラウザ5を介したWebページの出力、又は過去の出力に係る情報を参照することにより、抽出したWebページを出力している端末、又は出力した端末を特定する。
【0070】
次に、検索装置2は、検索クエリの条件を満たすWebページに係る情報(ステップ102で取得した情報)と、抽出したWebページを出力している端末に係る情報(ステップ103で取得した情報)からランク値演算用行列を設定する(ステップ104)。本発明の特徴的構成であるところのランク値演算用行列の設定処理について、図5,6を参照しつつ以下で詳細に説明する。
【0071】
ランク値演算用行列は、ネットワーク上で公開された複数のWebページとユーザからなるリンク構造に対応して設定するものであり、その各「列」は、「列」に対応するWebページから他のWebページへのリンクを示すものとなっている。即ち、「列」に属する各要素がそれぞれ別箇の他のWebページへのリンクを示している。さらにまた、その各「行」は、他のWebページから「行」に対応するWebページへのリンクを示すものとなっている。即ち、「行」に属する各要素がそれぞれ別箇の他のWebページから「行」に対応するWebページへのリンクを示している。
具体的に説明すると、例えば、図6で示されるようなランク値演算用行列Pであれば、その行列Pの各要素は、行列の上部に示したWebページA,B,C,D及びユーザ(Webページの閲覧者)E,F,G,Hから、行列の左部に表示したWebページA,B,C,D及びユーザE,F,G,Hに対するリンク又はユーザによるWebページの閲覧の状況を示す数値である。
即ち、図6に示す正方行列(ランク値演算用行列P)は、検索対象となるWebページがリンク先となっているWebページと、検索対象となるWebページがリンクしているWebページに対して現に、あるいは一定期間内に接続された端末との関連を示すものである。
【0072】
ここで、ランク値演算用行列についてモデルを用いて具体的に説明する。なお、本発明のランク値演算用行列がモデルのものに限らないことは当然である。
図5で示されるように、4つのWebページA,B,C,DがWebサーバ上に保持され、インターネットやLAN等のネットワークに接続されたコンピュータでブラウザを介して閲覧可能となっているものとする。即ち、4つのWebページA,B,C,Dがネットワーク上に公開された状態となっているものとする。ここで、1つめのWebページAは、WebページB,WebページCにそれぞれリンクを張った状態となっている。
ここで、「リンクを張った状態」とは、リンク元となる特定のWebページにリンク先となる他のWebページのURLが関連付けられており、例えば、リンク元のWebページ上の所定の部分をクリックするといった所定の操作によって、リンク先のWebページがブラウザで表示される構造となっている状態とする。
【0073】
さらに、2つめのWebページBは、WebページDにリンクを張った状態となっている。3つめのWebページCは、WebページDにリンクを張った状態となっている。4つめのWebページDは、WebページA,WebページCにそれぞれリンクを張った状態となっている。
【0074】
換言すると、1つ目のWebページAは、4つ目のWebページDにリンクを張られた状態となっている。
ここで、「リンクを張られた状態」とは、リンク元となる他のWebページが、リンク先となる特定のWebページにリンクを張った状態であることとする。即ち、他のWebページに特定のWebページのURLが関連付けられており、他のWebページで所定の操作を行うことによって、特定のWebページがブラウザで表示される構造となっている状態とする。
【0075】
同様に、2つめのWebページBは、WebページAにリンクを張られた状態となっている。3つめのWebページCは、WebページAとWebページDにそれぞれリンクを張られた状態となっている。4つめのWebページDは、WebページB,WebページCにそれぞれリンクを張られた状態となっている。
【0076】
ここで、WebページAをユーザEが閲覧しているものとする。即ち、閲覧者Eが使用しているクライアント端末4aのブラウザ5が、インターネットやLAN等のネットワークを介してWebページAを保持しているWebサーバからデータを取得し、WebページAを閲覧可能な状態に出力しているものとする。
【0077】
また同様に、WebページBをユーザF,G,Hがそれぞれ閲覧しているものとする。即ち、クライアント端末4b,4c,4dの各ブラウザ5が、WebページBを閲覧可能な状態に出力しているものとする。
【0078】
以上説明した状況において、いずれかのクライアント端末4で検索が実行され、WebページA,B,C,Dがいずれも検索クエリの条件を満たすWebページであったとする。このとき、検索装置2は、WebページA,B,C,Dを出力しているクライアント端末4a,4b,4c,4dを特定し、ユーザE,F,G,HがWebページA,B,C,Dを閲覧しているものとして、図6で示されるようなランク値演算用行列Pを設定する。
【0079】
ランク値演算用行列Pの各「列」要素に注目すると、左側部分RLはWebページA,B,C,Dに関する要素となっており、右側部分RRはユーザE,F,G,Hに関する要素となっている。即ち、複数のWebページA,B,C,Dに関する要素から構成される要素群と、複数のユーザE,F,G,Hに関する要素から構成される要素群とが隣合わせに配されている。
【0080】
このように本実施形態の検索装置2は、ユーザE,F,G,Hを仮想のWebページE,F,G,Hとしてランク値演算用行列Pを設定している。即ち、「特定のユーザによる特定のWebページの閲覧」を「仮想のWebページと特定のWebページの間で互いにリンクが張られている」状態としてランク値演算用行列Pに反映させている。換言すると、図6に示す正方行列では、WebページA,B,C,Dと、その閲覧者E,F,G,Hを同格に扱い、行列の各要素に反映させている。
【0081】
詳説すると、上記したようにWebページAをユーザEが閲覧しているとする(図5参照)。このとき、検索装置2は、WebページA,B,C,Dからなるリンク構造に、実際には存在しない仮想のWebページEがあるものとし、WebページA,B,C,D,Eからなるリンク構造であるものとする。そして、WebページA,B,C,Dに対応する「行」及び「列」に加えて、仮想WebページEに対応する新たな「行」と「列」とを追加してランク値演算用行列Pを設定する。換言すると、ユーザEが使用するクライアント端末4aでWebページAが出力されたことを条件に、ランク値演算用行列Pに新たな「行」と「列」とを追加する。
【0082】
したがって、上記のように4人のユーザE,F,G,Hが、それぞれ検索対象となるWebページA,B,C,Dのいずれかを閲覧している場合、WebページA,B,C,D,E,F,G,Hからなるリンク構造であるものとして、仮想WebページE,F,G,Hに対応する新たな「行」と「列」を4つずつ追加してランク値演算用行列Pを設定する。即ち、検索対象となるWebページの数と、検索対象となるWebページを出力している端末の数との合計がランク値演算用行列Pの行数及び列数となる。
【0083】
ここで、ランク値演算用行列Pの各「列」は、上記した検索対象となるWebページ、又は検索対象となるWebページの出力を条件にして定義される仮想のWebページに対応している。そして、「列」に属する各要素は、対応するWebページ又は仮想のWebページ(以下単にWebページとも称す)から、他のページへのリンクを示すものとなっている。具体的には、「列」に属する要素P(i,j)は、下記式(1):
P(i,j)= αX/Y ・・・(1)
α =0以外の数
X = 列「j」に対応するWebページから行「i」に対応するWebページへのリンクの数、又は、列「j」に対応するWebページの行「i」に対応する出力端末での表示数、又は、列「j」に対応する出力端末での行「i」に対応するWebページの表示数、又は0
Y = 列「j」に対応するWebページの出力端末での表示数と、列「j」に対応するWebページに形成されているリンク数の総和
の関係を満たすものである。
即ち、Webページがリンクしているリンク先の数に基づく値をAとし、端末が現にあるいは一定期間内に接続したWebページの数をBとしたとき、ランク値演算用行列Pの各要素は、A/(A+B)、B/(A+B)あるいはこれらに系数αが掛けられた値となっている。
【0084】
ここで、上記したように、本実施形態の検索装置2は、ユーザEが使用するクライアント端末4aでWebページAが出力されていることを条件に、WebページAから仮想のWebページEへリンクが張られ、仮想のWebページEからWebページAへリンクが張られているものとして、ランク値演算用行列Pを設定する。換言すると、ユーザEによるWebページAの閲覧を、実際には存在しないWebページEとWebページAの相互リンク(互いにリンクを張っている状態)として、ランク値演算用行列Pに反映させる。
【0085】
つまり、図5で示されるように、特定のWebページAから他の2つのWebページB,Cにそれぞれリンクが張られ、ユーザEが前記特定のWebページAを閲覧しているとする。このとき、検索装置2は、特定のWebページAが2つのWebページB,Cに加えて、仮想のWebページEにリンクを張っているとする。このとき、図6で示されるように、ランク値演算用行列Pの特定のWebページAに対応する列(図6で最も左側の列)を形成する各要素P(i,1)に注目すると、WebページB,C及び、仮想のWebページEへのリンクとそれぞれ対応する要素であるP(2,1),P(3,1),P(5,1)はいずれも1/3となっている。これらは、特定のWebページAのリンクの総数が3であり、特定のWebページAからWebページB,C及び、仮想のWebページEにそれぞれ1つずつリンクが張られていることを示している。したがって、ランク値演算用行列Pの各「列」の要素の総和は1となっている。
【0086】
また、ここでランク値演算用行列Pの各「行」要素に注目すると、上側部分LHはWebページA,B,C,Dに関する要素となっており、下側部分LLはユーザE,F,G,Hに関する要素となっている。即ち、複数のWebページA,B,C,Dに関する要素から構成される要素群と、複数のユーザE,F,G,Hに関する要素から構成される要素群とが上下に連続して配されている。
【0087】
以上のことから、図6で示されるように、ランク値演算用行列Pは、検索対象となるWebページA,B,C,Dと上記仮想のWebページE,F,G,HとからなるWebページ群において、各WebページA,B,C,D,E,F,G,Hを頂点とし、リンクを辿ることを遷移(推移)とするものであり、さらに、Webページ内の各リンクから一様な確率で1つのリンクを辿ることを想定する遷移確率行列(推移確率行列)となっているといえる。
なお、ここでいう「リンクを辿る」とは、リンク元となる特定のWebページにリンク先となる他のWebページのURLが関連付けられており、例えば、リンク元のWebページ上の所定の部分をクリックするといった所定の操作によって、リンク先のWebページがブラウザで表示されることとする。そしてさらに、実際のWebページと仮想のWebページの間に定義したリンクにおいても、実際のWebページ間のリンクと同様に取り扱うものとする。
【0088】
このとき、ランク値演算用行列Pに注目すると、図6で示されるように、左上に位置するエリアE1に属する各要素は、実際に存在するWebページA,B,C,Dの間に形成されるリンクを示している。また、右上に位置するエリアE2に属する各要素は、仮想のWebページE,F,G,Hのいずれかから実際に存在するWebページA,B,C,Dのいずれかへのリンクを示している。さらに、左下に位置するエリアE3に属する各要素は、実際に存在するWebページA,B,C,Dのいずれかから、仮想のWebページE,F,G,Hのいずれかへのリンクを示している。そして、右下に位置するエリアE4は、仮想のWebページE,F,G,Hの間に形成される仮想のリンクを示している。
【0089】
このようなランク値演算用行列Pが設定されると、図4で示されるように、ステップ104からステップ105へ移行して、検索装置2がランク値演算用行列Pの固有値を算出する。つまり、遷移確率行列の各頂点であるWebページA,B,C,D及び仮想のWebページE,F,G,Hのそれぞれにおける遷移確率を演算する。そして、検索装置2は、算出したランク値演算用行列Pの固有値に基づいて検索対象となるWebページを並び替える(ステップ106)。
【0090】
詳説すると、例えば、図6で示されるランク値演算用行列Pでは、その固有値は下記式(2):
〔A,B,C,D,E,F,G,H〕=〔0.408,0.544,0.408,0.544,0.136,0.136,0.136,0.136〕・・・(2)
の関係を満たしている。
したがって、図5で示されるWebページA,B,C,Dの固有値はそれぞれ0.408,0.544,0.408,0.544となる。ここで、このWebページA,B,C,Dを固有値の高い順に並べ替えるのであれば、WebページB,WebページD,WebページA,WebページCの順となる。
【0091】
そして検索装置2は、並び替えた検索対象となるWebページを検索結果としてクライアント端末4へ送信する(ステップ107)。
以上で情報検索システム1の検索実行時の処理の流れの説明を終了する。
【0092】
上記した実施形態では、ランク値演算用行列Pを設定するとき、ユーザE,F,G,Hをいずれも画一的なユーザとして仮想のWebページE,F,G,Hを設定した。つまり、Webページを閲覧したユーザがいずれのユーザE,F,G,Hであっても、仮想のWebページと実在のWebページの間に定義される仮想のリンクの数は同一となっている。即ち、いずれのユーザであっても1つの仮想のWebページと1つの実在のWebページの間に1つの相互リンクが定義される構成となっている。
【0093】
しかしながら、本発明の情報検索システムはこのような構成に限るものではない。即ち、各ユーザE,F,G,Hの間で特定項目に対する知識の深さや、検索スキル等が異なっている場合、ランク値演算用行列の設定に閲覧しているユーザE,F,G,Hの知識やスキルの違いを反映させる構成であってもよい。さらにまた、ランク値演算用行列Pに、検索キーワード等の出現数といったWebページA,B,C,Dの内容を反映させる構成であってもよい。
【0094】
以下で第2の実施形態及び第3の実施形態を説明するが、特に説明がない限り、第1の実施形態における情報検索システム1と同様の部分については、同様の符号を付して重複する説明を省略する。
【0095】
第2の実施形態では、ランク値演算用行列を設定するとき、ユーザE,F,G,Hの知識や検索スキル等の違いや、WebページA,B,C,Dの内容の違いに応じて、ランク値演算用行列の各要素を変更することを特徴とする。
【0096】
第2の実施形態の情報検索システム20は、第1の実施形態と同様に、検索装置2、各クライアント端末4、そして、各クライアント端末4で動作するブラウザ5及び端末側情報取得装置7によって構成されている(図1)。
【0097】
第2の実施形態の端末情報取得装置7は、取得した端末情報を利用することで各ユーザのユーザランク値を算出する。本明細書における、「ユーザランク値」とは、各ユーザの特定項目に対する知識の深さや、検索スキル等を基に決定される、ユーザの重要度を数値化した値を示す。算出したユーザランク値は検索用データベース3に端末情報として格納される。
【0098】
ユーザランク値の算出方法は、例えば、上記した端末情報取得装置7が取得した端末情報と、情報収集機能(情報収集部12)が収集したWebページの情報に基づいて、ユーザがブラウザ5を介して出力したWebページの種類や、Webページの閲覧時間、リンクを辿ったときの変遷履歴等に基づいて算出してもよい。
また、端末情報取得装置7をブラウザに組み込むとき、又はソフトウェアのインストール時等に、ユーザの職業や趣味等の個人情報を取得する方法がある。また、ブラウザ5に記録された頻繁に閲覧するWebページへのショートカットの情報を取得するという方法がある。即ち、検索が実行されたときに、検索対象となるWebページをユーザが閲覧しており、且つそのユーザの職業や趣味等がWebページの内容と関連していた場合、そのユーザのユーザランク値を高くするという方法である。
さらに、ユーザが、BBS等で特定の項目と関連する質問に対して回答を行った際に、必要に応じて当該BBS(特定のWebページ)からデータを取得する方法がある。具体的には、ユーザが行った回答に対する他のユーザの評価の情報等を必要に応じて取得する。そして、他のユーザから高い評価を得た回答を行ったユーザのユーザランク値を高くするという方法である。
そしてまた、検索キーワード、検索後に閲覧したWebページ、及び検索後にWebページを閲覧した時間、検索後のWebページからリンクしたページ等を解析することにより、ユーザの検索スキルを判定し、それを基にユーザランク値を付与するという方法が考えられる。
このような、検索内容に対する知識の深さや、検索スキル等を基にユーザを評価する方法から、適宜なものを少なくとも一つ選択し、端末情報取得装置7や情報収集部12に情報を収集させ、検索装置2において解析処理を実行することで、ユーザランク値を決定する。
【0099】
第2の実施形態の端末情報取得装置7では、情報収集部12が収集した情報に基づいて、各Webページのリレーションランク値を算出する。本明細書における、「リレーションランク値」とは、各Webページの内容に特定の単語がどれだけ記載されているか、特定の単語がタイトル等の所定の箇所に記載されているか等の情報を基に決定される、Webページの内容と特定項目との関連性の高さを数値化した値を示す。算出したリレーションランク値は検索用データベース3に端末情報として格納される。
【0100】
次に、本実施形態の情報検索システム1の検索実行時の処理の流れについて説明する。
いずれかのクライアント端末4で検索が実行されると、第1の実施形態と同様の手順によって、検索装置2がランク値演算用行列を設定する。
【0101】
ここで、本実施形態では、検索によって抽出された各WebページA,B,C,Dのリレーションランク値と、抽出された各Webページを閲覧しているユーザE,F,G,Hのユーザランク値を参照してランク値演算用行列の各要素の値を変更する。
【0102】
モデルを用いて具体的に説明すると、図5で示されるモデルにおいて、ユーザFがユーザG,Hに比べてユーザランクが高いユーザであったとする。このとき、図6で示される
ランク値演算用行列Pの要素の値を、図7で示されるランク値演算用行列Pのように変更する。即ち、P(4,2),P(7,2),P(8,2)の値をそれぞれ1/4から1/5に変更し、P(6,2)の値を1/4から2/5に変更している。このことで、WebページBから仮想のWebページFへのリンクの重要度を、WebページBから仮想のWebページG,Hそれぞれへの各リンクの重要度より高くしている。
【0103】
このように、作成したランク値演算用行列の各要素の値を、ユーザランク値とリレーションランク値のいずれか一方又は両方の値に基づき、適宜変更することにより、実在するWebページA,B,C,D、やユーザE,F,G,Hによって定義される仮想のWebページE,F,G,Hの重要度をランク値演算用行列に反映させる。なお、このとき、ランク値演算用行列の各要素の値を変更しても、ランク値演算用行列Pの各「列」の要素の総和は1となる。したがって、図6で示されるランク値演算用行列Pから要素P(6,2)値を変更するとき、1/4から(1+α)/(4+α)(αは0でない数)のように変更される。
【0104】
さらに、必要に応じて各要素の値の変更を行ったランク値演算用行列の固有値を算出する。即ち、遷移確率行列の各要素の値を変更してから演算することで、遷移確率行列の各頂点であるWebページA,B,C,D及び仮想のWebページE,F,G,Hのそれぞれにおける遷移確率に基づく遷移傾向を推定する演算を実施する。そして、算出した固有値に基づいて抽出したWebページを並び替える。
【0105】
また、検索装置2は、並び替えた検索対象となるWebページを検索結果としてクライアント端末4へ送信する。以上で本実施形態の情報検索システム1の検索実行時の処理の流れの説明を終了する。
【0106】
次に第3の実施形態について説明する。
第3の実施形態では、ランク値演算用行列を設定して固有値を算出した後、各固有値あるいは行列の要素に対してユーザランク値やリレーションランク値に基づく値を付加することを特徴とする。
詳説すると、第1の実施形態又は第2の実施形態と同様の手順により、ランク値演算用行列を設定し、固有値を算出する。そして、算出した各固有値を変更し、変更された固有値でWebページの並び替えを実施する。
【0107】
例えば、算出されたWebページA,B,C,Dの固有値が、それぞれ0.408,0.544,0.408,0.544であったとする。そして、このとき、WebページAをユーザランク値の高いユーザが閲覧していたとする。すると、検索装置2は、WebページAの固有値に所定の値を加えて0.608とする。そして、変更したWebページA,B,C,Dに対応する固有値0.608,0.544,0.408,0.544に基づいてWebページA,B,C,Dの並び替えを実施する。このように、ユーザランク値の高いユーザが閲覧しているWebページやリレーションランク値の高いWebページに対応する固有値を変更したのち、Webページの並び替えを実施する。なお、上記した例では、ユーザランク値の高いユーザが閲覧しているWebページやリレーションランク値の高いWebページに対応する固有値に値を付与する例を示したが、固有値の変更方法はこれに限るものではない。例えば、リレーションランク値の低いWebページに対応する固有値の値を差し引いてもよい。固有値の変更は、ユーザランク値又はリレーションランク値に応じて適宜変更してよい。
【0108】
上記した各実施形態では、ランク値演算用行列Pは、検索対象となるWebページA,B,C,Dと上記仮想のWebページE,F,G,HとからなるWebページ群において、各WebページA,B,C,D,E,F,G,Hを頂点とする遷移確率行列なっている。したがって、このランク値演算用行列Pの設定は、例えば、各WebページA,B,C,D,E,F,G,Hを頂点とする隣接行列を作成し、作成した隣接行列を基に遷移確率行列を導出してもよい。ランク値演算用行列Pの設定するときの導出方法は、適宜変更してよい。
【0109】
上記した各実施形態では、検索が実行されたとき、検索クエリの条件を満たすWebページを抽出し、抽出したWebページを閲覧しているユーザを特定して、抽出したWebページとそれを閲覧しているユーザとに対応するランク値演算用行列Pを設定した。しかしながら、本発明の検索システムの検索実行時の処理はこれに限るものではない。
例えば、ネットワーク上の全てのWebページとそれを閲覧しているユーザとに対応するランク値演算用行列P2を予め導出しておき、検索が実行された場合に、予め導出しておいたランク値演算用行列P2から、「行」の要素や「列」の要素から必要な要素を抜き出してランク値演算用行列Pを設定してもいい。即ち、予め導出しておいたランク値演算用行列P2から、必要な「行」の要素や「列」の要素を抜き出し、組み合わせることによって、検索クエリの条件を満たすWebページと、それを閲覧しているユーザとに対応するランク値演算用行列Pを設定してもよい。
【0110】
また同様に、特定の条件を満たすWebページと、それを閲覧しているユーザとに対応するランク値演算用行列P3を予め導出しておき、検索が実行された場合に、予め導出しておいたランク値演算用行列P3から、「行」の要素や「列」の要素から必要な要素を抜き出してランク値演算用行列Pを設定してもいい。
【0111】
上記した各実施形態では、ランク値演算用行列の行要素と列要素において、WebページA,B,C,Dに対応する要素群とユーザE,F,G,Hに対応する要素群とが隣接して形成されるランク値演算用行列を例に挙げて説明したが、本発明のランク値演算用行列はこれに限るものではない。例えば、ランク値演算用行列の行要素と列要素の順番は適宜入れ替わってもよい。また、説明の便宜上、ランク値演算用行列を行列の書式で表しているが、実際に検索システムが演算する際の行列の取り扱いは適宜設定してよい。つまり、行列を形成する各要素、又は行列を形成する各要素の内で演算に必要な要素のみを記憶保持して、必要な計算を実行してもよい。必ずしも、上記したような行列の形状で取り扱わなくてもよい。
【0112】
上記した各実施形態では、検索が実行されたとき、端末側情報取得装置7が予め取得した端末情報と、情報収集部12が予め取得したWebページの構造に係る情報とを検索用データベース3から取得してランク値演算用行列Pを設定したが、ランク値演算用行列の設定方法はこれに限るものではない。例えば、検索が実行されたとき、検索装置2がクライアント端末4から、Webページの閲覧に係る情報を取得する構成であってもよい。また、取得した情報をデータベースに保持させずにランク値演算用行列の設定に使用してもよい。即ち、クライアント端末4から検索装置2への端末情報の送信は、適時実施してもよい。そして、情報のデータベースへの格納は、適時実施してもよく、場合によっては実施しなくてもよい。
【0113】
上記した各実施形態では、Webページを固有値の高い順に並び替えたが、本発明はこれに限らず、例えば、Webページを固有値の低い順に並び替えてもよい。しかしながら、Webページを固有値の高い順に並び替える方法によると、検索実行時に話題性の高いWebページ(例えば、多数のクライアント端末4で出力されたWebページ)が上位に表示されるため、望ましい。
【0114】
また、上記した各実施形態では、検索結果となるWebページを並び替えるとき、Webページの固有値が同じ場合、閲覧者が多いページを上位に表示している。しかしながら、本発明の検索システムはこれに限るものではなく、例えば、Webページの固有値が同じだった場合、閲覧者が少ないページを上位に表示してもよい。
【0115】
上記した各実施形態では、図3に示すように、検索用データベース3及びクライアント端末4から送信された情報を受信、管理する機能が検索装置2に含まれる構成を例に挙げているが、本発明の検索システム1はこれに限定されるものではない。例えば、検索用データベース3をネットワーク上の別途のサーバ装置に設けておき、検索装置2が検索を実行する際に、当該サーバの検索用データベース3から情報を取得するという構成でもよい。即ち、システム全体で機能を実現できればよく、設置するサーバの数及び各機能(プログラム)、データベースの配置は、サーバの能力等により適宜変更可能である。
【0116】
なお、上記した各実施形態のプログラム、及びシステムは、CD−ROM等の光学ディスク、磁気ディスク、半導体メモリなどの各種の記録媒体を通じて、又は電気通信網などを介してダウンロードすることにより、コンピュータにインストール又はロードすることができる。
【実施例】
【0117】
ところで、上記したランク値演算用行列の固有値を求める際の演算は、適宜のハードウェア構成、適宜の演算アルゴリズムで行ってよい。しかし、より高速にランク値演算用行列の固有値を求めるべく、下記の検証を実施した。本発明の情報検索システムは、下記の検証を参考にハードウェア構成及び演算アルゴリズムを選択してもよい。
【0118】
検証を実施するに当たって、LR法やQR法等の古典的な手法は一般的に大きな手間を要するので、固有値が等しく、元の行列よりサイズの小さい行列に変換することで計算時間を削減する「射影法」に基づく手法について検証を行った。Lanzcos,Arnoldi,Krylov−Schur等の射影法に基づく手法は,Gram−Schmidtの手法をベースにした直交化のフェーズと、マルチシフトQR法による固有値計算およびSchur分解のフェーズからなる手法で、分解フェーズでブロックを並べかえることで、最大固有値、最小固有値など,欲しい固有値および固有ベクトルの組から求められる手法である。そのため、最大固有値と対応する固有ベクトルのみが必要なアプリケーションでは、大幅に計算時間を削減できる可能性がある。そのため、「射影法」に基づく手法は、上記したランク値演算用行列の固有値を求める演算に適していると考えられる。
【0119】
これらの射影法を実装したライブラリの中で、大規模行列の計算に対応したものとしてSLEPcがある。SLEPcでは、PETSc、BLAS、LAPACKなどの既存の数値計算ライブラリを用いて、最新の固有値計算手法を実装しており、大幅な計算時間の短縮が期待できる。SLEPcが用いているPETScという数値計算ライブラリでは、OpenMPIを用いてベクトルや行列の演算を複数プロセスで並列処理する機能を備えている。PETScはC言語で記述されており、高速に演算を行える。また、OpenMPIはプロセス間通信方式として、共有メモリ、InfiniBand、TCP/IP等、さまざまな方式をサポートしており、内部で自動的に切り替えてくれるため、準備できる環境に応じて最適な並列化が容易に実現できる。
【0120】
これに対して、一般的な検索サービスでは、常に大規模な分散環境における処理を前提としてシステムを構築している。これらのミドルウェアは、ノード故障等が頻繁に発生する環境で、安定して大量のバッチ処理を実行できるという特徴を有する。しかしながら、冗長化のためのオーバヘッドも大きく、大量の通信を伴う処理では高い性能を出すことができない。
【0121】
つまり、中小規模の計算機環境では密結合な処理の方が高性能で処理できる可能性があるため、本検証では、MPIベースで実装されたクラスタ向けのミドルウェアも含めて調査することにした。
【0122】
まず、OpenMPIで実装されたSLEPcの性能について調査した。詳細には、本発明の情報検索システムが要求するスケーラビリティを実現するため、どの程度のリソースを要するのかを調査した。さらに具体的には、Webページと閲覧者をあわせて10万エントリ程度の計算を実施する場合を想定した性能について調査した。
【0123】
検証における評価環境は以下の通りである。
計算機:PowerEdge R410×2(DELL社製)
CPU:Intel(R) Xeon(R) L5520 (2.26GHz,8MB キャッシュ, 5.86 GT/s QPI) ×2 (コア数4)
メモリ:32GB(4GB×8/2R/1066MHz/DDR3 RDIMM)
ディスク:RAID6(PERC6i),600GB,15,000RPM SAS
ネットワーク:Broadcom NetXtreme II BCM5716 1000Base−T PCIExpress
スイッチ:Cisco Catalyst 2960G−8TC−L
OS:Ubuntu Linux10.04
ライブラリ:PETSc 3.0.0, SLEPc 3.0.0,LAPACK 3.2.1,BLAS 1.2
【0124】
性能評価では、対称行列の例としてラプラシアン行列を用い、非対称行列の例として要素間をランダムに遷移するモデルを想定して生成した遷移確率行列を用いて固有値、固有ベクトルを計算した。本実験で用いたラプラシアン行列は、図8(a)に示したような行列で、対角要素が2、その両脇の要素が1の行列とした。また、遷移確率行列は、三角格子の上をランダムに移動することを想定して生成した図8(b)のような行列とした。本検証ではまず単一ノード内での並列処理性能について評価し、その後TCP/IPを用いて複数ノードでの評価を行なう。
【0125】
実機での評価の前にSLEPcのソースコードから、Arnoldi,Krylov−Schurの実装について調査した。
【0126】
SLEPcで用いられているPETScでは、OpenMPIの集合通信機能を利用し、行列の1行目からn1行目、n1+1行目からn2行目など、指定した範囲で分割して、各プロセッサごとに部分行列を生成、処理する機能を実装している。直交化の計算では、各プロセスに分散配置した部分行列およびベクトルの中間計算結果をギャザ,スキャタ,レデュース等の機能で相互にやりとりする必要があるため、並列化時の通信オーバヘッドが大きくなると考えられる。
【0127】
対して、マルチシフトQRやSchur分解の処理では、注目している部分行列のみに注目して処理できるため、通信オーバヘッドは発生しないと考えられる。以上の点について、実際に性能計測して確認した。
【0128】
PETScでは、−log summaryというオプションにより、プログラムの実行時間、事前設定した箇所の呼び出し回数、実行時間などを分析する機能を提供している。下記の実験では、この−log summaryの機能を用いて性能計測した。
【0129】
またさらに、MPIにおけるオールギャザ、オールレデュース等の集合通信では、プロセッサ数が偶数であることを想定しており、奇数の場合余ったノードの通信は効率的に行えないため、集合通信を多用する計算では偶数個のプロセッサを利用するのが良いと考えられる。実際に奇数n個のプロセッサを利用した場合、偶数n1個のプロセッサ数と同等程度の性能しか得られなかった。そのため、以下の評価では偶数個のプロセッサの性能について評価した。
【0130】
計算対象となる行列の値により実際に並列に実行されるコードが異なってくるので,ソースコードから直接並列化率を求めることはできないが、性能測定結果から指定したパラメータでの並列化率を算出し、ライブラリの性能を評価できると考えられる。以下で求めた並列化率は指定したパラメータでの並列化率である。また、SLEPcでは、求める固有値の許容誤差を指定することで、計算結果が指定した誤差内に収まるまで、反復計算を継続する。以下の実験では許容誤差を10の−7乗として計算した。
【0131】
まず、ラプラシアン行列での計算時間について調査する。
【0132】
調査に当たって、10万×10万のサイズのラプラシアン行列の固有値計算時間を測定した。このとき、まず、同じ反復回数での処理時間を比較した。反復回数を12500回程度に制限すると、このサイズの行列ではどの手法もまだ固有値が収束しないので、同じ繰り返し回数だけ計算される。単一プロセッサで計算したときの処理時間をT1、プロセッサ数nで計算したときの処理時間をTnとしたとき,プロセッサ数を変化させた場合の処理時間比T1=Tnは図9のようになった。
【0133】
利用したハードウェアはノードあたり8コアのプロセッサが利用でき、さらにIntelのHyper Threading技術により、仮想的に16コアのプロセッサが利用できる。しかし、図9に示すように、プロセッサ数が8から9に増えるところで性能が低下している。そこでHyper Threading機能をOFFにして各手法の処理時間をプロセス数8まで測定したところ、プロセッサ数8まではほぼ同様な変化を示した。そのため、複数CPUの利用ではなくHyper Threadingが原因で性能低下していると考えられる。Ubuntuの実装が影響していることも考えられるが、詳細な原因までは調査できていない。このことを受け、以下の実験ではHyper Threading機能をOFFにして評価を実施した。
【0134】
プロセッサ数8までの結果では、アムダールの法則が示すとおりプロセッサ数の増加に対して処理時間比の伸びが鈍化している。プログラム中で並列化されている部分の割合(並列化率:Parallel Portion)をr(0<=r<=1)とし、プロセッサ数をnとすると、オーバヘッドを無視した並列処理部分の処理時間はrT1=n、逐次処理部分の処理時間は(1―r)T1なので、処理時間比Speedupは下記〔数1〕のようになっている。
【0135】
【数1】
【0136】
計測した値から最小二乗法でrを推定すると、Lanzcos,Arnoldi,Krylov−Schurでそれぞれ、およそ0.9653(96.53%),0.9720(97.20%)0.9583(95.83%)という値になった。なお、図9中の直線は理想的な性能,曲線は推定した曲線を表す。オーバヘッドを無視した式で推定しているため、観測値と推定曲線にはずれがある。8プロセッサでの計測値が近似曲線よりも下に来ているので、10プロセッサ以上の性能を測定して再計算すれば、並列化率は低下すると考えられる。次に、それぞれの手法における8プロセッサでの並列化効率(ParallelEfficiency)を調べた。並列化効率PEは、処理時間比をプロセッサ数で割った値であるため百分率で表すと、下記〔数2〕のようになっている。
【0137】
【数2】
【0138】
並列化効率は、Lanzcos,Arnoldi,Krylov−Schurbで、それぞれ、およそ74.58%,76.11%,68.87%となり、Arnoldiが最も良い数値を示した。
【0139】
対称行列での並列化効率は3手法とも、8プロセッサまでであれば50%は割り込まないが、それ以上になると並列化効率が低下する可能性がある。例えば、大規模なシステムであれば、システムの利用効率を維持するため,50%の並列化効率に満たないジョブの投入を断るという事例がある。したがって、今後、本発明の情報検索システムで要求される処理性能の実現に8ノード以上が必要であることが判明し、かつ、8プロセッサ以上で並列化効率が50%を割り込むことが判明した場合は、ハードウェア追加による投資対効果を得るために、他のライブラリや計算手法の利用が考えられる。
【0140】
3手法の繰り返し回数12500回の計算時間を比較したグラフを図10に示す。対称行列では、Lanzcosの計算時間が最も少ないことが分かる。非対称行列も計算可能な残りの2手法では、Krylov−Schurがより計算時間が短いことが分かる。ただし、これらは繰り返し回数を等しくした場合の計算時間であり、実際には各手法で固有値が収束するまでに必要な繰り返し回数は異なっている。例えば、今回調査した中ではArnoldiは36534回の繰り返しで収束している。
【0141】
次に生成した遷移確率行列での計算時間について調査した。
【0142】
生成した行列は非対称行列であり、遷移確率行列であるため、ラプラシアン行列よりも対象とするWebページのリンク構造に近い行列となっている。行列の列方向の値の和が1になるように行列を生成するため制約条件があり、行列のサイズは中途半端な値となる。今回281625というサイズの行列を用いた。また、繰り返し回数は各手法で固有値が収束しない500回に制限して実施した。Lanzcosは対称行列を対象とした計算手法であるため、非対称行列については、Arnoldi,Krylov−Schurの2手法について比較した。Krylov−Schurでは、行列が対称の場合、部分的に計算アルゴリズムをLanzcosをベースとした計算手法に切り替えているため、非対称の場合では性能特性が異なっている。
【0143】
図11にプロセッサ数を変化させた場合の処理時間比T1=Tnの結果を示す。最小二乗法で推定した並列化率は、Arnoldi,Krylov−Schurがそれぞれ0.817591(81.75%), 0.839298(83.92%)となっており、非対称行列ではArnoldi,Krylov−Schurともに対称行列の場合と比べて並列化率が低下している。同様に、プロセッサ数を変化させた場合の並列化効率(Parallel Efficiency)の結果を図12に示す。Arnoldi,Krylov−Schurともにプロセッサ数8で並列化効率が50%を切っており、上述の例を考えると現在の実装では効果的にCPUを利用できていないおそれがある。
【0144】
しかし、遷移確率行列は疎行列であるため固有値の収束が速く、収束までの繰り返し回数が少ない。実際に収束までにかかった繰り返し回数は、手法やプロセッサ数によって差があるが、Krylov−Schurでは、1157回以内で収束することが確認できた。処理時間は2プロセッサでおよそ102.2秒,56.77秒であり、ラプラシアン行列の場合の1/4程度の処理時間となっている。そのため、必要となるプロセッサ数も少なくなると考えられる。
【0145】
次に、通信オーバヘッドの影響を調査するため、単一ノードと複数ノードで計算した場合を比較した。具体的には、1ノードで実行した場合と2ノードで実行した場合を比較した。なお、評価はTCP/IPで実施した。
【0146】
遷移確率行列は疎行列であるため、固有値の収束が速く、計算の繰り返し回数が少なくなる。そのため、計算の繰り返し回数が多くなるラプラシアン行列の計算結果で確認した。2プロセッサを利用した計算で、繰り返し回数を変化させた場合の処理時間について、図13に示す。
【0147】
単一ノードで処理した場合に比べて、MPI関連の関数呼び出し時間は大きくなるが、その他の部分の処理時間の関係で、複数ノードを利用した方が性能が良くなっているケースがある。これらは、Open MPIのドライバの実装等に依存している可能性がある。本検証の結果より、今後、情報検索システムが要求する性能が単一ノードのプロセッサ数では実現できないと判明した場合、今回調査した性能向上率で対応できる範囲であれば、ノード間通信を利用してプロセッサを追加することで対応できる可能性がある。
【0148】
以上で、MPIベースで実装されたクラスタ向けのミドルウェアも含めた固有値計算の処理速度に関する検証の説明を終了する。
【0149】
上記した検証では、SLEPcに実装されたPower(べき乗)法についての検証を行っていないが、この方法も本発明の情報検索システムに好適に使用できる可能性がある
【0150】
上記した検証では、ランキング機能の固有値計算部分の高速化についてのみ検討を行った。しかし、実際にはページ間のリンク構造を取得して遷移確率行列として固有値計算プログラムに入力する必要がある。行列サイズが大きくなると、入出力がボトルネックになる可能性がある。ここで、MPIでは並列入出力の機能を備えており、これを利用することで入出力による性能低下を回避できる可能性がある。また、PETScは疎行列を効率的に格納するデータ構造をサポートしているため、メモリ使用量を抑えることができる。
【0151】
上記した検証によって、並列計算ライブラリSLEPcを用いることで、8コア程度のPCで、数十万規模の遷移確率行列の固有値および固有ベクトルの計算が数十秒で完了できることが確認された。
【符号の説明】
【0152】
1 情報検索システム
10 端末情報取得部(情報取得手段)
13 検索実行部(情報序列化手段)
【特許請求の範囲】
【請求項1】
検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、
検索対象となるWebページを序列化する情報序列化手段を有するものであり、
情報序列化手段は、検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施する機能を備えたことを特徴とする情報検索システム。
【請求項2】
遷移確率の演算は、検索対象となるWebページと検索対象となるWebページに対して現にあるいは一定期間内に接続された端末を含む構成によって正方行列を設定し、当該正方行列の固有ベクトルを演算する演算内容を含むことを特徴とする請求項1に記載の情報検索システム。
【請求項3】
前記正方行列の要素は、Webページがリンクしているリンク先の数に基づく値と、端末が現にあるいは一定期間内に接続したWebページの数に基づく値によって構成されていることを特徴とする請求項2に記載の情報検索システム。
【請求項4】
前記正方行列の要素は、Webページがリンクしているリンク先の数に基づく値をAとし、端末が現にあるいは一定期間内に接続したWebページの数をBとしたとき、A/(A+B)、B/(A+B)あるいはこれらに系数が掛けられた値であることを特徴とする請求項2又は3に記載の情報検索システム。
【請求項5】
検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、
情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定するものであって、
前記出力端末を仮想のWebページとし、出力端末が出力しているWebページと仮想のWebページとの間に相互リンクが形成されるとしたとき、Webページ及び仮想のWebページによって形成されるリンク構造に基づき、リンク元のWebページの表示からリンク先のWebページの表示への切り替えを遷移とした遷移確率行列を設定し、
設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるWebページを序列化することを特徴とする請求項1乃至3のいずれかに記載の情報検索システム。
【請求項6】
前記端末情報に基づいて、前記出力端末を使用する使用者の特定項目に対する知識及び/又は使用者の検索能力に対するユーザの重要度を示すユーザランク値を算出するものであり、
前記ユーザランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び/又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項2乃至5のいずれかに記載の情報検索システム。
【請求項7】
ネットワーク上のWebページの内容に関する情報を取得可能な情報取得機能を有し、情報取得機能が取得した情報に基づいてWebページの内容の重要度を示すリレーションランク値を算出するものであり、
前記リレーションランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び/又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項2乃至6のいずれかに記載の情報検索システム。
【請求項8】
端末で入力されたキーワードに基づいてデータベースの検索を行なうと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、
検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、
検索対象となるWebページを序列化する情報序列化手段を有するものであり、
情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定し、前記Webページと出力端末に基づいて正方行列を設定するものであって、
前記正方行列はWebページ及び出力端末に対応する行要素及び列要素から形成されるものであり、その各要素P(i,j)は下記式(1)の関係を満たすものであり、
設定した前記正方行列の固有ベクトルを算出し、算出した固有ベクトルの成分の大きさに基づいて検索対象となるWebページを序列化することを特徴とする情報検索システム。
P(i,j)= αX/Y ・・・(1)
α =0以外の数
X = 列「j」に対応するWebページから行「i」に対応するWebページへのリンクの数、又は、列「j」に対応するWebページの行「i」に対応する出力端末での表示数、又は、列「j」に対応する出力端末での行「i」に対応するWebページの表示数、又は0
Y = 列「j」に対応するWebページの出力端末での表示数と、列「j」に対応するWebページに形成されているリンク数の総和
【請求項9】
検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索方法であって、
検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施することを特徴とする情報検索方法。
【請求項10】
検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得し、
少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定するものであり、
前記出力端末を仮想のWebページとし、出力端末が出力しているWebページと仮想のWebページとの間に相互リンクが形成されるとしたとき、Webページ及び仮想のWebページによって形成されるリンク構造に基づき、リンク元のWebページの表示からリンク先のWebページの表示への切り替えを遷移とした遷移確率行列を設定し、
設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるWebページを序列化することを特徴とする請求項9に記載の情報検索方法。
【請求項1】
検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、
検索対象となるWebページを序列化する情報序列化手段を有するものであり、
情報序列化手段は、検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施する機能を備えたことを特徴とする情報検索システム。
【請求項2】
遷移確率の演算は、検索対象となるWebページと検索対象となるWebページに対して現にあるいは一定期間内に接続された端末を含む構成によって正方行列を設定し、当該正方行列の固有ベクトルを演算する演算内容を含むことを特徴とする請求項1に記載の情報検索システム。
【請求項3】
前記正方行列の要素は、Webページがリンクしているリンク先の数に基づく値と、端末が現にあるいは一定期間内に接続したWebページの数に基づく値によって構成されていることを特徴とする請求項2に記載の情報検索システム。
【請求項4】
前記正方行列の要素は、Webページがリンクしているリンク先の数に基づく値をAとし、端末が現にあるいは一定期間内に接続したWebページの数をBとしたとき、A/(A+B)、B/(A+B)あるいはこれらに系数が掛けられた値であることを特徴とする請求項2又は3に記載の情報検索システム。
【請求項5】
検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、
情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定するものであって、
前記出力端末を仮想のWebページとし、出力端末が出力しているWebページと仮想のWebページとの間に相互リンクが形成されるとしたとき、Webページ及び仮想のWebページによって形成されるリンク構造に基づき、リンク元のWebページの表示からリンク先のWebページの表示への切り替えを遷移とした遷移確率行列を設定し、
設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるWebページを序列化することを特徴とする請求項1乃至3のいずれかに記載の情報検索システム。
【請求項6】
前記端末情報に基づいて、前記出力端末を使用する使用者の特定項目に対する知識及び/又は使用者の検索能力に対するユーザの重要度を示すユーザランク値を算出するものであり、
前記ユーザランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び/又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項2乃至5のいずれかに記載の情報検索システム。
【請求項7】
ネットワーク上のWebページの内容に関する情報を取得可能な情報取得機能を有し、情報取得機能が取得した情報に基づいてWebページの内容の重要度を示すリレーションランク値を算出するものであり、
前記リレーションランク値に基づいて前記正方行列と前記遷移確率行列のいずれかの要素、及び/又は算出された正方行列又は前記遷移確率行列の固有ベクトルの少なくともいずれかを変更することを特徴とする請求項2乃至6のいずれかに記載の情報検索システム。
【請求項8】
端末で入力されたキーワードに基づいてデータベースの検索を行なうと共に、その検索結果を前記端末に出力して表示させるための情報検索システムであって、
検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得する情報取得手段を有しており、
検索対象となるWebページを序列化する情報序列化手段を有するものであり、
情報序列化手段は、少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定し、前記Webページと出力端末に基づいて正方行列を設定するものであって、
前記正方行列はWebページ及び出力端末に対応する行要素及び列要素から形成されるものであり、その各要素P(i,j)は下記式(1)の関係を満たすものであり、
設定した前記正方行列の固有ベクトルを算出し、算出した固有ベクトルの成分の大きさに基づいて検索対象となるWebページを序列化することを特徴とする情報検索システム。
P(i,j)= αX/Y ・・・(1)
α =0以外の数
X = 列「j」に対応するWebページから行「i」に対応するWebページへのリンクの数、又は、列「j」に対応するWebページの行「i」に対応する出力端末での表示数、又は、列「j」に対応する出力端末での行「i」に対応するWebページの表示数、又は0
Y = 列「j」に対応するWebページの出力端末での表示数と、列「j」に対応するWebページに形成されているリンク数の総和
【請求項9】
検索を実行した端末で入力されたキーワードに基づいてWebページの検索を行うと共に、その検索結果を前記端末に出力して表示させるための情報検索方法であって、
検索対象となるWebページがリンクしているWebページと、検索対象となるWebページに対して現にあるいは一定期間内に接続された端末との関連から遷移傾向を推定する演算を実施することを特徴とする情報検索方法。
【請求項10】
検索実行時又は検索実行以前に、検索対象となるWebページを出力している端末に係る情報である端末情報を取得し、
少なくとも端末情報に基づいて所定の条件を満たすWebページと、当該Webページを出力している又は出力した端末である出力端末を特定するものであり、
前記出力端末を仮想のWebページとし、出力端末が出力しているWebページと仮想のWebページとの間に相互リンクが形成されるとしたとき、Webページ及び仮想のWebページによって形成されるリンク構造に基づき、リンク元のWebページの表示からリンク先のWebページの表示への切り替えを遷移とした遷移確率行列を設定し、
設定した遷移確率行列に基づいて遷移確率を演算し、演算結果に基づいて検索対象となるWebページを序列化することを特徴とする請求項9に記載の情報検索方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【公開番号】特開2013−25421(P2013−25421A)
【公開日】平成25年2月4日(2013.2.4)
【国際特許分類】
【出願番号】特願2011−157226(P2011−157226)
【出願日】平成23年7月15日(2011.7.15)
【新規性喪失の例外の表示】特許法第30条第1項適用申請有り 社団法人電子情報通信学会発行 「電子情報通信学会技術研究報告 IEICE Technical Report IA2010−84−IA2010−103 インターネットアーキテクチャー」(平成23年2月21日発行)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Linux
【出願人】(504322611)学校法人 京都産業大学 (27)
【公開日】平成25年2月4日(2013.2.4)
【国際特許分類】
【出願日】平成23年7月15日(2011.7.15)
【新規性喪失の例外の表示】特許法第30条第1項適用申請有り 社団法人電子情報通信学会発行 「電子情報通信学会技術研究報告 IEICE Technical Report IA2010−84−IA2010−103 インターネットアーキテクチャー」(平成23年2月21日発行)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Linux
【出願人】(504322611)学校法人 京都産業大学 (27)
[ Back to top ]