(57)【要約】【課題】評価の信頼性を高めることができる。【解決手段】記憶部１ａは、複数のデータおよび複数のデータそれぞれの評価値を記憶する。演算部１ｂは、記憶部１ａを参照して、データＸの評価値が更新されると、データＸの評価値に基づいて、少なくともデータＸからリンクされるデータＸ１，Ｘ２それぞれの評価値を評価して更新する。演算部１ｂは、データＹの評価値の参照要求を受け付けると、少なくともデータＹへのリンクをもつデータＹ１，Ｙ２それぞれの評価値に基づいて、データＹの評価値を評価し出力する。【選択図】図１
2014044552.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータそれぞれが他のデータを指し示す関係性であるリンクをもっており、前記複数のデータそれぞれの評価値を、他のデータの評価値と他のデータがもつリンクとに基づいて評価する評価方法であって、情報処理装置が、
第１のデータの評価値が更新されると、前記第１のデータの評価値に基づいて、少なくとも前記第１のデータからリンクされる１または複数の第２のデータそれぞれの評価値を評価して更新し、
何れかのデータの評価値の参照要求を受け付けると、少なくとも当該データへのリンクをもつ１または複数の第３のデータそれぞれの評価値に基づいて、参照要求を受けた当該データの評価値を評価し出力する、評価方法。
【請求項２】
前記第１のデータの評価値が更新されると、前記第１のデータから前記第２のデータを介してリンクされるデータのうち、前記第１のデータの評価値の変化分に対して各データの評価値に反映される変化分の割合が第１の閾値以上であるデータの評価値を、前記第２のデータの評価値に基づいて更新し、
第４のデータの前記参照要求を受け付けると、前記第４のデータへ前記第３のデータを介してリンクするデータのうち、前記第４のデータの評価値に反映される各データの評価値の割合が第２の閾値以上であるデータの評価値に基づいて、前記第４のデータの評価値を評価する、請求項１記載の評価方法。
【請求項３】
何れかのデータの評価値の更新がクライアント装置により要求される頻度と、クライアント装置から前記参照要求を受け付ける頻度と、に基づいて、前記第１の閾値および前記第２の閾値を変更する、請求項２記載の評価方法。
【請求項４】
前記第１の閾値を増加させ前記第２の閾値を減少させるか、または、前記第１の閾値を減少させ前記第２の閾値を増加させるように、前記第１の閾値および前記第２の閾値を変更する、請求項３記載の評価方法。
【請求項５】
前記第１の閾値と前記第２の閾値との積が一定になるように、前記第１の閾値および前記第２の閾値を変更する、請求項３または４記載の評価方法。
【請求項６】
複数のデータそれぞれが他のデータを指し示す関係性であるリンクをもっており、前記複数のデータそれぞれの評価値を、他のデータの評価値と他のデータがもつリンクとに基づいて評価するために用いられる情報処理装置であって、
前記複数のデータおよび前記複数のデータそれぞれの評価値を記憶する記憶部と、
前記記憶部を参照して、第１のデータの評価値が更新されると、前記第１のデータの評価値に基づいて、少なくとも前記第１のデータからリンクされる１または複数の第２のデータそれぞれの評価値を評価して更新し、また、何れかのデータの評価値の参照要求を受け付けると、少なくとも当該データへのリンクをもつ１または複数の第３のデータそれぞれの評価値に基づいて、参照要求を受けた当該データの評価値を評価し出力する演算部と、を有する情報処理装置。
【請求項７】
複数のデータそれぞれが他のデータを指し示す関係性であるリンクをもっており、前記複数のデータそれぞれの評価値を、他のデータの評価値と他のデータがもつリンクとに基づいて評価するためのプログラムであって、コンピュータに、
第１のデータの評価値が更新されると、前記第１のデータの評価値に基づいて、少なくとも前記第１のデータからリンクされる１または複数の第２のデータそれぞれの評価値を評価して更新し、
何れかのデータの評価値の参照要求を受け付けると、少なくとも当該データへのリンクをもつ１または複数の第３のデータそれぞれの評価値に基づいて、参照要求を受けた当該データの評価値を評価し出力する、処理を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は評価方法、情報処理装置およびプログラムに関する。
【背景技術】
【０００２】
情報処理装置からネットワークを介して他の装置上に蓄積されたデータ（例えば、文書データ）にアクセスし、当該データの内容を閲覧することがある。データの蓄積量が大量になると、閲覧したい内容を含むデータをユーザ自身が探索するのに手間がかかる。そこで、検索システムが利用されている。検索システムは、例えばキーワードの入力を受け付け、キーワードを含む、または、キーワードに関連するデータを検索し出力する。
【０００３】
例えば、文書データの一例にＷｅｂページが挙げられる。Ｗｅｂページの検索システムにはＷｅｂページをランク付けして提示するものがある。ランクとは人気度や重要度などを示す指標である。検索システムは、例えば検索されたＷｅｂページのうち、ランクの高いものを相対的に上位に提示し、ランクの低いものを相対的に下位に提示する。
【０００４】
Ｗｅｂページのランク付けの方法として、ページランク（ＰＡＧＥＲＡＮＫ、登録商標）と呼ばれる方法がある。Ｗｅｂページはリンクをもつ。リンクは他のＷｅｂページを指し示す情報である。ページランクでは、各Ｗｅｂページのバックリンク（backlink）とフォワードリンク（forwardlink）とに基づいて各Ｗｅｂページをランク付けする。バックリンクはＷｅｂページが他のＷｅｂページから指し示されるリンクである。フォワードリンクはＷｅｂページから他のＷｅｂページを指し示すリンクである。例えば、Ｗｅｂページ間のリンクの関係性は隣接行列で表され得る。すると、ページランクによるランク付けは隣接行列（または隣接行列に調整を加えた行列）の固有ベクトルを求める問題に帰着される。行列の固有ベクトルは、例えばベキ乗法（Power Method）を用いて計算され得る。
【０００５】
ところで、Ｗｅｂページの数は膨大である。このため、ページランクの方法を用いて全てのＷｅｂページのランクを精度良く求めるとすると計算に時間がかかる。そこで、近似的なランクで代替することで計算コストを削減する提案がある。この提案では、収集されたページの近似ＰａｇｅＲａｎｋ値をリンク先に等分配することでリンク先の近似ＰａｇｅＲａｎｋ値を更新する。リンク先のページでも分配された分を更にそのリンク先へと分配し、それを繰り返す。分配を適当なところで打ち切ることで計算コストを削減する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許第６２８５９９９号明細書
【非特許文献】
【０００７】
【非特許文献１】Page、外３名、“The PageRank Citation Ranking: Bringing Order to the Web.”、［online］、2001年10月30日、The Stanford University InfoLab、［2012年2月23日検索］、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｉｌｐｕｂｓ．ｓｔａｎｆｏｒｄ．ｅｄｕ：８０９０／４２２／１／１９９９−６６．ｐｄｆ＞
【非特許文献２】山田、外３名、“インクリメンタルＰａｇｅＲａｎｋによる重要Ｗｅｂページの効率的な収集戦略”、情報処理学会論文誌：コンピューティングシステム、社団法人情報処理学会、2004年10月、Vol.45、No.SIG 12、p.465-473
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記のように、複数のデータ（例えば、文書データ）それぞれの評価値（例えば、ランク）を、他のデータの評価値と他のデータがもつリンクとに基づいて評価する方法が考えられる。また、このような方法において、リンク元のデータの評価値をリンク先のデータに分配して評価値の更新処理を行っていき、分配を途中で打ち切ることが考えられる。
【０００９】
ところが、分配を途中で打ち切ると、評価値の更新の影響を受けるリンク先の範囲が制限されることになる。すると、その範囲外のデータの評価値を参照するとき、当該データの評価値を単に読み取るだけでは、他のデータの更新の影響が当該データの評価値に反映されていないために、読み取った評価値の精度が低い可能性があるという問題がある。
【００１０】
一側面によれば、本発明は、評価の信頼性を高めることができる評価方法、情報処理装置およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
一実施態様によれば、複数のデータそれぞれが他のデータを指し示す関係性であるリンクをもっており、複数のデータそれぞれの評価値を、他のデータの評価値と他のデータがもつリンクとに基づいて評価する評価方法が提供される。この評価方法では、情報処理装置が、第１のデータの評価値が更新されると、第１のデータの評価値に基づいて、少なくとも第１のデータからリンクされる１または複数の第２のデータそれぞれの評価値を評価して更新する。何れかのデータの評価値の参照要求を受け付けると、少なくとも当該データへのリンクをもつ１または複数の第３のデータそれぞれの評価値に基づいて、参照要求を受けた当該データの評価値を評価し出力する。
【００１２】
また、一実施態様によれば、複数のデータそれぞれが他のデータを指し示す関係性であるリンクをもっており、複数のデータそれぞれの評価値を、他のデータの評価値と他のデータがもつリンクとに基づいて評価するために用いられる情報処理装置が提供される。この情報処理装置は、記憶部と演算部とを有する。記憶部は、複数のデータおよび複数のデータそれぞれの評価値を記憶する。演算部は、記憶部を参照して、第１のデータの評価値が更新されると、第１のデータの評価値に基づいて、少なくとも第１のデータからリンクされる１または複数の第２のデータそれぞれの評価値を評価して更新する。演算部は、何れかのデータの評価値の参照要求を受け付けると、少なくとも当該データへのリンクをもつ１または複数の第３のデータそれぞれの評価値に基づいて、参照要求を受けた当該データの評価値を評価し出力する。
【００１３】
また、一実施態様によれば、コンピュータによって実行されるプログラムであって、複数のデータそれぞれが他のデータを指し示す関係性であるリンクをもっており、複数のデータそれぞれの評価値を、他のデータの評価値と他のデータがもつリンクとに基づいて評価するためのプログラムが提供される。このプログラムは、コンピュータに、第１のデータの評価値が更新されると、第１のデータの評価値に基づいて、少なくとも第１のデータからリンクされる１または複数の第２のデータそれぞれの評価値を評価して更新し、何れかのデータの評価値の参照要求を受け付けると、少なくとも当該データへのリンクをもつ１または複数の第３のデータそれぞれの評価値に基づいて、参照要求を受けた当該データの評価値を評価し出力する、処理を実行させる。
【発明の効果】
【００１４】
一実施態様によれば、評価の信頼性を高めることができる。
【図面の簡単な説明】
【００１５】
【図１】第１の実施の形態の情報処理装置を示す図である。
【図２】第２の実施の形態の情報処理システムを示す図である。
【図３】第２の実施の形態のグラフの例を示す図である。
【図４】第２の実施の形態のサーバのハードウェア例を示す図である。
【図５】第２の実施の形態のサーバのソフトウェア例を示す図である。
【図６】第２の実施の形態のＷｅｂページ管理テーブルを示す図である。
【図７】第２の実施の形態のキューを示す図である。
【図８】第２の実施の形態の更新範囲の例を示す図である。
【図９】第２の実施の形態の参照範囲の例を示す図である。
【図１０】第２の実施の形態のランク更新を示すフローチャートである。
【図１１】第２の実施の形態の更新時影響度の例を示す図である。
【図１２】第２の実施の形態のランク参照を示すフローチャートである。
【図１３】第２の実施の形態の参照時影響度の例を示す図である。
【図１４】第３の実施の形態のログテーブルの例を示す図である。
【図１５】第３の実施の形態の更新・参照範囲の変更を示すフローチャートである。
【図１６】第３の実施の形態の更新・参照範囲の変更例（その１）を示す図である。
【図１７】第３の実施の形態の更新・参照範囲の変更例（その２）を示す図である。
【発明を実施するための形態】
【００１６】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理装置を示す図である。情報処理装置１は、複数のデータそれぞれの評価値を評価するために用いられる。ここで、複数のデータそれぞれは他のデータを指し示す関係性であるリンクをもっている。例えば、データは文書データである。例えば、文書データがＷｅｂページであれば、リンクはＷｅｂページのＨＴＭＬ（HyperText Markup Language）ファイル内にハイパーテキストにより記述されたＵＲＬ（Uniform Resource Locator）である。当該リンクはハイパーリンクと呼ばれることもある。また、例えば文書データが論文データであれば、リンクは引用文献として記述された他の文献の名称である。データは、文書データの識別情報と当該文書データがもつリンクとを管理できれば、文書データそのものでなくてもよい。データは、リンクの情報をもつものであれば、文書データ以外のものでもよい。
【００１７】
情報処理装置１は、複数のデータそれぞれの評価値を、他のデータの評価値と他のデータがもつリンクとに基づいて評価する。評価値は、例えば、人気度、重要度およびお薦め度などを示す指標（ランク）である。具体的には、リンク元のデータの評価値を、リンク先のデータに分配する。あるデータが複数のリンク元のデータから評価値の分配を受ける場合、分配を受けた評価値の合計が当該データの評価値である。そして、当該評価値を当該データのリンク先のデータに更に分配する。この分配を繰り返した結果を得ることで、複数のデータそれぞれの評価値を得る。
【００１８】
情報処理装置１は、記憶部１ａおよび演算部１ｂを有する。記憶部１ａはＲＡＭ（Random Access Memory）などのメモリである。演算部１ｂはＣＰＵ（Central Processing Unit）などのプロセッサである。例えば、記憶部１ａに記憶されたプログラムを演算部１ｂが実行することで、第１の実施の形態の情報処理を実現できる。
【００１９】
記憶部１ａは、複数のデータおよび複数のデータそれぞれの評価値を記憶する。複数のデータそれぞれは、前述のように他のデータへのリンクの情報を有している。
例えば、記憶部１ａはデータＸ，Ｘ１，Ｘ２，Ｘ１１，Ｘ１２，Ｘ１３，Ｘ１４，Ｘ１５，Ｘ１６，Ｘ１７，・・・を記憶する。データＸはデータＸ１，Ｘ２へのリンクを有する。データＸ１はデータＸ１１，Ｘ１２へのリンクを有する。データＸ２はデータＸ１２，Ｘ１３へのリンクを有する。データＸ１１はデータＸ１４へのリンクを有する。データＸ１２はデータＸ１５，Ｘ１６へのリンクを有する。データＸ１３はデータＸ１７へのリンクを有する。グラフ構造２はこれらデータ間のリンクの関係性を示している。
【００２０】
更に、例えば、記憶部１ａはデータＹ，Ｙ１，Ｙ２，Ｙ１１，Ｙ１２，Ｙ１３，Ｙ１４，Ｙ１５，Ｙ１６，Ｙ１７，・・・を記憶する。データＹ１，Ｙ２はデータＹへのリンクを有する。データＹ１１はデータＹ１へのリンクを有する。データＹ１２はデータＹ１，Ｙ２へのリンクを有する。データＹ１３はデータＹ２へのリンクを有する。データＹ１４はデータＹ１１へのリンクを有する。データＹ１５，Ｙ１６はデータＹ１２へのリンクを有する。データＹ１７はデータＹ１３へのリンクを有する。グラフ構造３はこれらデータ間のリンクの関係性を示している。
【００２１】
演算部１ｂは、記憶部１ａを参照して、第１のデータの評価値が更新されると、第１のデータの評価値に基づいて、少なくとも第１のデータからリンクされる１または複数の第２のデータそれぞれの評価値を評価して更新する。
【００２２】
例えば、データＸの評価値が更新される。具体的には、データＸに対する別のデータからのリンクが追加されると、データＸの評価値が増大し得る。当該別のデータから評価値の分配を受けるからである。あるいは、データＸに対する別のデータからのリンクが削除されると、データＸの評価値が減少し得る。当該別のデータから評価値の分配を受けられなくなるからである。
【００２３】
演算部１ｂは、データＸの評価値が更新されると、データＸの評価値に基づいて、少なくともデータＸからリンクされるデータＸ１，Ｘ２それぞれの評価値を評価して更新する。例えば、データＸ１，Ｘ２から更にリンクされるデータＸ１１，Ｘ１２，Ｘ１３それぞれの評価値を評価して更新してもよい。例えば、データＸの評価値が増大する場合、評価値の増分をデータＸ１，Ｘ２に分配する。データＸ１１，Ｘ１２，Ｘ１３にも分配する場合、データＸ１，Ｘ２に分配された分を更にデータＸ１１，Ｘ１２，Ｘ１３に分配する。分配の繰り返しにより、データＸの評価値の増大による影響が他のデータに伝搬する。
【００２４】
例えば、他のデータが受ける当該影響の度合い（更新時影響度）は、データＸの評価値の変化分に対して他の各データの評価値に反映される変化分の割合により表せる。例えば、データＸの評価値の変化分の２５％がデータＸ１１の評価値の変化分となるならば、データＸからデータＸ１１が受ける更新時影響度は２５％（＝０．２５）である。
【００２５】
例えば、データＸはデータＸ１，Ｘ２の２つに増分を分配する。このとき、データＸの増分によるデータＸ自身の影響度１に対して、データＸ１，Ｘ２それぞれが受ける影響度は、１／２＝０．５である。例えば、データＸ１はデータＸ１１，Ｘ１２の２つに更に分配する。このとき、データＸ１１，Ｘ１２それぞれが受ける影響度は０．５×０．５＝０．２５である。データＸの評価値が減少する場合は、評価値の減少分を同様に分配して各データの評価値を減少させればよい。このときも増加時と同様の考え方で更新時影響度を表せる。
【００２６】
ここで、更新範囲２ａは更新対象となるデータの集合である。更新範囲２ａは、更新時の影響度閾値ε（εは０＜ε＜１の実数）によって定めることができる。更新時の影響度閾値は、各データに対する分配の影響をどこまで伝搬させるかを示す情報である。例えば、各データが受ける更新時影響度がε以上であるデータの集合が更新範囲２ａである。
【００２７】
演算部１ｂは、何れかのデータの評価値の参照要求を受け付けると、少なくとも当該データへのリンクをもつ１または複数の第３のデータそれぞれの評価値に基づいて、参照要求を受けた当該データの評価値を評価し出力する。
【００２８】
例えば、データＹの評価値の参照要求を受け付ける。すると、演算部１ｂは、少なくともデータＹへのリンクをもつデータＹ１，Ｙ２それぞれの評価値に基づいて、参照要求を受けたデータＹの評価値を評価し出力する。ここで、例えばデータＹはデータＹ１，Ｙ２のみからリンクされているとする。例えば、データＹ１，Ｙ２はデータＹへのリンクのみを有するとする。このとき、例えばデータＹ１，Ｙ２の評価値のみに基づいてデータＹの評価値を評価するならば、データＹ１，Ｙ２の評価値の和がデータＹの評価値である。
【００２９】
データＹ１，Ｙ２の評価値に加え、データＹ１，Ｙ２へのリンクをもつデータＹ１１，Ｙ１２，Ｙ１３それぞれの評価値に基づいて、データＹの評価値を評価してもよい。例えば、データＹ１１，Ｙ１２，Ｙ１３の評価値はデータＹ１，Ｙ２を介して、データＹの評価値に影響を及ぼす。例えば、この影響度（参照時影響度）は、データＹの評価値に反映される他のデータの評価値の割合により表せる。例えば、データＹ１１の評価値の４０％がデータＹの評価値に反映されるならデータＹに対するデータＹ１１の参照時影響度は４０％（＝０．４）である。参照時影響度とデータＹ１，Ｙ２，Ｙ１１，Ｙ１２，Ｙ１３それぞれの評価値とを考慮した値に基づいて、データＹの評価値を評価してもよい。
【００３０】
ここで、参照範囲３ａは参照対象となるデータの集合である。参照範囲３ａは、参照時の影響度閾値ε’（ε’は０＜ε’＜１の実数）によって定めることができる。例えば、参照時影響度がε’以上であるようなデータの集合が参照範囲３ａである。
【００３１】
情報処理装置１によれば、演算部１ｂにより、記憶部１ａが参照されて、データＸの評価値が更新されると、データＸの評価値に基づいて、少なくともデータＸからリンクされるデータＸ１，Ｘ２それぞれの評価値が評価されて更新される。また、演算部１ｂにより、データＹの評価値の参照要求が受け付けられると、少なくともデータＹへのリンクをもつデータＹ１，Ｙ２それぞれの評価値に基づいて、データＹの評価値が評価されて出力される。
【００３２】
これにより、評価値を更新するための処理コストを軽減しながら、評価の信頼性を高めることができる。具体的には、評価値の更新時において更新範囲２ａに含まれるデータのみを更新すると、処理コストを軽減できる反面、更新の影響の伝搬が制限されることになる。したがって、更新範囲２ａの外部のデータについて評価値の精度が悪化し得る。このため、当該外部のデータについて、評価値の参照要求を受けた時に、記憶部１ａから当該外部のデータの評価値を単に読み出して応答するのみでは、応答された評価値の信頼性は低いことになる。
【００３３】
そこで、情報処理装置１は、あるデータの評価値の参照時に参照範囲３ａに含まれるデータの評価値を考慮して、参照対象のデータの評価値を求める。このように、参照対象のデータの評価値を、周囲のデータの評価値に基づいて再評価して応答する。したがって、あるデータの更新の影響が、参照対象のデータに伝搬していなかったとしても、周囲のデータに対して当該影響が伝搬していれば、当該影響を参照対象のデータに反映させて評価値を得ることができる。
【００３４】
より具体的には、データの全体集合４に、データＡ，Ｂ，Ｃ，Ｄ，Ｅが含まれているとする。データＡの評価値を更新するとき更新範囲４ａに含まれるデータ（データＡの周囲のデータ）が更新対象となる。データＢの評価値を参照するとき参照範囲４ｂに含まれるデータ（データＢの周囲のデータ）が参照対象となる。データＡの更新時にデータＢまで更新の影響が伝搬しなかったとしても、更新範囲４ａと参照範囲４ｂとの両方に含まれるデータにより、データＢについて当該更新の影響を反映させた評価値を得られる。
【００３５】
一方、データＣの評価値を参照するとき参照範囲４ｃに含まれるデータが参照対象となる。周囲のデータに何れのデータからの更新の影響も及んでいなければ、データＣの評価値を参照する際に、何れかのデータの更新の影響が及ぶことはない。この場合は、参照範囲４ｃに含まれるデータに有意な更新が発生していないと考えてよい。よって、周囲のデータの評価値に基づいてデータＣの評価値を求めても期待する信頼性は確保される。
【００３６】
同様に、データＤの評価値を更新するとき更新範囲４ｄに含まれるデータが更新対象となる。データＥの評価値を参照するとき参照範囲４ｅに含まれるデータが参照対象となる。データＡ，Ｄの更新時にデータＥまで更新の影響が伝搬しなかったとしても、更新範囲４ａと参照範囲４ｅとの両方に含まれるデータ、および、更新範囲４ｄと参照範囲４ｅとの両方に含まれるデータにより、当該更新影響を考慮してデータＥの評価値を得られる。
【００３７】
このようにして、更新時の処理コストを軽減できる。そして、あるデータの評価値の更新の影響をリンク先の他のデータのうちの一部までにしか伝搬させないとしても、参照する評価値の信頼性を高めることができる。
【００３８】
［第２の実施の形態］
図２は、第２の実施の形態の情報処理システムを示す図である。第２の実施の形態の情報処理システムは、Ｗｅｂページをランク付けする。第２の実施の形態の情報処理システムは、サーバ１００，１００ａおよびクライアント２００，２００ａを有する。
【００３９】
サーバ１００，１００ａおよびクライアント２００，２００ａは、ネットワーク１０を介して接続されている。ネットワーク１０は、例えばインターネットやＷＡＮ（Wide Area Network）などの広域ネットワークである。ネットワーク１０は、ＬＡＮ（Local Area Network）でもよい。
【００４０】
サーバ１００，１００ａは、Ｗｅｂページのランク付けを行うサーバコンピュータである。サーバ１００，１００ａは、クライアント２００，２００ａから各Ｗｅｂページにおけるランクの更新内容（例えば、増分や減少分）を受け付ける。すると、サーバ１００，１００ａは、ランクが更新されたＷｅｂページからリンクされている他のＷｅｂページに当該更新の影響を伝搬させ、他のＷｅｂページの評価値を更新する。
【００４１】
また、サーバ１００，１００ａは、クライアント２００，２００ａから何れかのＷｅｂページのランクの参照要求を受け付ける。すると、サーバ１００，１００ａは、参照対象のＷｅｂページのランクを評価してクライアント２００，２００ａに応答する。
【００４２】
サーバ１００，１００ａは、Ｗｅｂページの全体を分担して管理している。例えば、サーバ１００は、全体のうちの一部のＷｅｂページのランクなどの情報を保持する。サーバ１００ａは、全体のうちの他の一部のＷｅｂページのランクなどの情報を保持する。３以上のサーバコンピュータでＷｅｂページの管理を分担してもよい。
【００４３】
例えば、サーバ１００の処理により、サーバ１００ａが保持する情報が更新される場合は、サーバ１００はサーバ１００ａに該当の情報を更新させる。サーバ１００の処理に、サーバ１００ａが保持する情報を用いる場合は、サーバ１００はサーバ１００ａから該当の情報を取得する。逆の場合も同様である。
【００４４】
クライアント２００，２００ａは、ユーザが操作するクライアントコンピュータである。クライアント２００，２００ａは、ユーザの指示に応じて、Ｗｅｂページのランクの更新要求または参照要求をサーバ１００，１００ａに送信する。
【００４５】
図３は、第２の実施の形態のグラフの例を示す図である。図３（Ａ）は有向グラフを例示している。有向グラフは、例えばノード２１，２２および矢印２３で表される。ノード２１，２２は、それぞれが１つのデータ（あるいはレコード）に相当するものであり、第２の実施の形態ではＷｅｂページＰｘ，Ｐｙである。ＷｅｂページＰｘ，Ｐｙは、例えばＨＴＭＬで記述された文書データである。例えば、ＷｅｂページＰｘには、ハイパーテキストでＷｅｂページＰｙのＵＲＬが記述されることで、ＷｅｂページＰｙへのリンクが張られている。
【００４６】
矢印２３は、ノード２１からノード２２へ向けたリンクを示している。矢印２３はノード２１を起点としている。このため、矢印２３はノード２１のフォワードリンクである。矢印２３はノード２２を終点としている。このため、矢印２３はノード２２のバックリンクである。このように、ノード２１，２２および矢印２３を組み合わせたグラフ構造により、各Ｗｅｂページのリンクの関係性を表すことができる。
【００４７】
図３（Ｂ）はＷｅｂページのグラフ構造を例示している。このような関係性をもつ各Ｗｅｂページをランク付けする方法として、ページランクが知られている。以下の説明においてｉ，ｊ，ｎは１以上の整数である。ｋは０以上の整数である。ページランクの単純な総和公式ではページＰｉのランクｒ（Ｐｉ）は式（１）により表される。
【００４８】
【数１】
2014044552.tif 000003
【００４９】
ここで、ＢPiは、ＷｅｂページＰｉへのリンクをもつＷｅｂページ（Ｐｉのバックリンク）の集合である。｜Ｐｊ｜は、ＷｅｂページＰｊからのフォワードリンクの個数である。全てのＷｅｂページのランクを求める場合、ｒ（Ｐｊ）が未知である。そこで、全てのＷｅｂページにランクの初期値（Ｗｅｂページの総数がｎ個であれば１／ｎ）を与え、反復法により各Ｗｅｂページのランクを収束させる。具体的には、ｋ＋１回目の手続におけるＷｅｂページＰｉのランクｒk+1（Ｐｉ）は式（２）により表される。
【００５０】
【数２】
2014044552.tif 000004
【００５１】
ここで、ｒ0（Ｐｉ）＝１／ｎである。式（２）はＷｅｂページのランクを１つずつ順番に計算する。行列を用いて同じ計算を行うことで、１×ｎの行ベクトルπTにより全てのＷｅｂページのｋ＋１回目の手続後のランクを保持できる。添え字Ｔは転置を示し、ベクトルπTがｎ列の要素をもつ行ベクトルであることを示す。Ｗｅｂページのグラフ構造を行単位に正規化したｎ×ｎ行列Ｈで表す。行列Ｈはグラフ構造を表す隣接行列である。具体的には、ＷｅｂページＰｉからＷｅｂページＰｊへのリンクが存在するとき、Ｈｉｊ＝１／｜Ｐｉ｜である。それ以外の箇所は０である。行列Ｈの一例を示せば式（３）のようになる。
【００５２】
【数３】
2014044552.tif 000005
【００５３】
行列Ｈの行ｉにおける非ゼロの要素はＷｅｂページＰｉからのフォワードリンクのＷｅｂページに対応する。列ｉにおける非ゼロの要素はＷｅｂページＰｉに対するバックリンクのＷｅｂページに対応する。このとき、ｋ＋１回目の手続後のベクトルπ(k+1)Tは式（４）のように表せる。
【００５４】
【数４】
2014044552.tif 000006
【００５５】
ベクトルπ(k+1)Tのｉ列目の要素がｒk+1（Ｐｉ）に対応する。ただし、式（４）ではベクトルπTの収束性において不十分な点がある。例えば、フォワードリンクをもたないＷｅｂページのランクが過大となるランクシンク（Rank Sink）などの問題がある。そこで、行列Ｈに調整を加え、このような問題を解消した行列Ｇを用いる（式（４）において、行列Ｈを行列Ｇに置き換える）。その場合、ページランクを求める計算は、行列Ｇの固有ベクトル問題に帰着される。行列Ｇの固有ベクトルがベクトルπTに相当するからである。この固有ベクトル問題は、式（５）（６）のように表せる。
【００５６】
【数５】
2014044552.tif 000007
【００５７】
【数６】
2014044552.tif 000008
【００５８】
ここで、行列ｅは単位行列である。式（６）は全Ｗｅｂページのランクの合計が１になるように正規化するものである。式（５）について、例えばバッチ処理でベキ乗法を用いた計算を行い、式（６）を用いてベクトルπTの要素を正規化することで、全Ｗｅｂページのランクを所望の精度で算出することができる。しかし、Ｗｅｂページの数は膨大であり、当該バッチ処理には時間を要する。よって、この方法は、Ｗｅｂページの更新に対してランクを逐次更新したい場合などには不向きである。
【００５９】
そこで、第２の実施の形態では、ページランクの厳密な方法を用いて求まるランクの代わりに、Ｗｅｂページの近似的なランクを求める。以下の説明では、当該近似的なランクも含めてランクと称している。
【００６０】
図４は、第２の実施の形態のサーバのハードウェア例を示す図である。サーバ１００は、プロセッサ１０１、ＲＡＭ１０２、ＨＤＤ（Hard Disk Drive）１０３、通信部１０４、画像信号処理部１０５、入力信号処理部１０６、ディスクドライブ１０７および機器接続部１０８を有する。各ユニットがサーバ１００のバスに接続されている。サーバ１００ａおよびクライアント２００，２００ａのハードウェア例もサーバ１００と同様である。
【００６１】
プロセッサ１０１は、サーバ１００の情報処理を制御する。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ、ＭＰＵ（Micro Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）またはＰＬＤ（Programmable Logic Device）などである。プロセッサ１０１は、ＣＰＵ、ＭＰＵ、ＤＳＰ、ＡＳＩＣ、ＦＰＧＡ、ＰＬＤのうちの２以上の要素の組み合わせであってもよい。
【００６２】
ＲＡＭ１０２は、サーバ１００の主記憶装置である。ＲＡＭ１０２は、プロセッサ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部を一時的に記憶する。また、ＲＡＭ１０２は、プロセッサ１０１による処理に用いる各種データを記憶する。
【００６３】
ＨＤＤ１０３は、サーバ１００の補助記憶装置である。ＨＤＤ１０３は、内蔵した磁気ディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。サーバ１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の補助記憶装置を備えてもよく、複数の補助記憶装置を備えてもよい。
【００６４】
通信部１０４は、ネットワーク１０を介して他のコンピュータと通信を行えるインタフェースである。通信部１０４は、有線インタフェースでもよいし、無線インタフェースでもよい。
【００６５】
画像信号処理部１０５は、プロセッサ１０１からの命令に従って、サーバ１００に接続されたディスプレイ１１に画像を出力する。ディスプレイ１１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどを用いることができる。
【００６６】
入力信号処理部１０６は、サーバ１００に接続された入力デバイス１２から入力信号を取得し、プロセッサ１０１に出力する。入力デバイス１２としては、例えば、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００６７】
ディスクドライブ１０７は、レーザ光などを利用して、光ディスク１３に記録されたプログラムやデータを読み取る駆動装置である。光ディスク１３として、例えば、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などを使用できる。ディスクドライブ１０７は、例えば、プロセッサ１０１からの命令に従って、光ディスク１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００６８】
機器接続部１０８は、サーバ１００に周辺機器を接続するための通信インタフェースである。例えば、機器接続部１０８にはメモリ装置１４やリーダライタ装置１５を接続できる。メモリ装置１４は、機器接続部１０８との通信機能を搭載した記録媒体である。リーダライタ装置１５は、メモリカード１６へのデータの書き込み、またはメモリカード１６からのデータの読み出しを行う装置である。メモリカード１６は、カード型の記録媒体である。機器接続部１０８は、例えば、プロセッサ１０１からの命令に従って、メモリ装置１４またはメモリカード１６から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００６９】
図５は、第２の実施の形態のサーバのソフトウェア例を示す図である。図５に示す各ユニットは、例えば、プロセッサ１０１がＲＡＭ１０２に記憶されたプログラムを実行することで実現できる。図５の各ユニットはＡＳＩＣやＦＰＧＡなどによって実現されてもよい。また、サーバ１００ａのソフトウェア例もサーバ１００と同様である。
【００７０】
サーバ１００は、ページ情報記憶部１１０、キュー記憶部１２０、受信部１３０、キュー制御部１４０、ランク処理部１５０および送信部１６０を有する。
ページ情報記憶部１１０は、Ｗｅｂページに関する情報を記憶する。例えば、各Ｗｅｂページのリンク・被リンク関係や、各Ｗｅｂページのランクである。
【００７１】
キュー記憶部１２０は、Ｗｅｂページのランクの更新要求（以下、単に更新要求と称する）、または、Ｗｅｂページのランクの参照要求（以下、単に参照要求と称する）を、キューを用いて記憶する。
【００７２】
ページ情報記憶部１１０およびキュー記憶部１２０は、ＲＡＭ１０２やＨＤＤ１０３の記憶領域を用いて実装できる。
受信部１３０は、クライアント２００，２００ａから更新要求や参照要求を受信して、キュー制御部１４０に出力する。
【００７３】
キュー制御部１４０は、受信部１３０から取得した更新要求や参照要求のジョブをキュー記憶部１２０に格納する。キュー制御部１４０は、ＦＩＦＯ（First In / First Out）の手順に従って、キュー記憶部１２０に記憶された更新要求または参照要求のジョブを取り出して、ランク処理部１５０に出力する。キュー制御部１４０は、ランク処理部１５０によって生成された更新や参照のジョブ内容を示す情報を、キュー記憶部１２０に格納することもある。
【００７４】
ランク処理部１５０は、ページ情報記憶部１１０に記憶されたＷｅｂページの情報に基づいて、ランクの評価を行う。具体的には、ランク処理部１５０は、キュー制御部１４０から取得した更新要求のジョブに基づいて、更新対象となるＷｅｂページのランクを更新する。このとき、上述のバッチ処理とは異なり、ランク処理部１５０は更新対象となるＷｅｂページをページ情報記憶部１１０から検索しながら、ランクの更新処理を行うことになる。ランク処理部１５０は、ランクの更新処理が完了すると、更新完了の通知を送信部１６０に出力する。
【００７５】
また、ランク処理部１５０は、キュー制御部１４０から取得した参照要求のジョブに基づいて、参照対象のＷｅｂページのランクを評価し、送信部１６０に出力する。ランク処理部１５０は、参照対象のＷｅｂページに対するリンク元のＷｅｂページのランクに基づいて、参照対象のＷｅｂページのランクを評価する。
【００７６】
ランク処理部１５０は、更新や参照の処理に応じたジョブを生成し、当該ジョブ内容を示す情報をキュー制御部１４０に出力することもある。
送信部１６０は、ランク処理部１５０から取得した更新完了の通知を、更新要求の送信元であるクライアント（例えば、クライアント２００）に応答する。送信部１６０はランク処理部１５０から取得したＷｅｂページのランクを、参照要求の送信元であるクライアントに応答する。
【００７７】
図６は、第２の実施の形態のＷｅｂページ管理テーブルを示す図である。Ｗｅｂページ管理テーブル１１１は、ページ情報記憶部１１０に記憶される。Ｗｅｂページ管理テーブル１１１は、ＵＲＬ、ランク、フォワードリンクおよびバックリンクの項目を含む。
【００７８】
ＵＲＬの項目には、ＷｅｂページのＵＲＬが登録される。ランクの項目には、ランクの値が登録される。フォワードリンクの項目には、当該Ｗｅｂページが指し示すリンク先ＷｅｂページのＵＲＬのリストが登録される。バックリンクの項目には、当該Ｗｅｂページに対するリンク元ＷｅｂページのＵＲＬのリストが登録される。
【００７９】
例えば、Ｗｅｂページ管理テーブル１１１には、ＵＲＬが“Ｐ１”、ランクが“０．０１”、フォワードリンクが“Ｐ２，Ｐ３”、バックリンクが“Ｐ２１，Ｐ２２”という情報が登録されている。これは、ＵＲＬ“Ｐ１”で示されるＷｅｂページのランクが“０．０１”であることを示している。また、ＵＲＬ“Ｐ１”のＷｅｂページからＵＲＬ“Ｐ２，Ｐ３”のＷｅｂページへのフォワードリンクが存在すること、ＵＲＬ“Ｐ１”のＷｅｂページに対してＵＲＬ“Ｐ２１，Ｐ２２”のＷｅｂページからのバックリンクが存在することを示している。
【００８０】
ランク処理部１５０は、定期的に（例えば、月次などで）ページランクの方法を用いて全Ｗｅｂページのランクを求め、Ｗｅｂページ管理テーブル１１１を更新してもよい。全Ｗｅｂページのランクを定期的に一括更新することで、第２の実施の形態による評価の信頼性を向上し得るからである。
【００８１】
なお、以下の説明では、ＵＲＬ“Ｐ１”に対応するＷｅｂページを、ＷｅｂページＰ１のように表記することがある。
図７は、第２の実施の形態のキューを示す図である。キュー１２１は、キュー記憶部１２０に格納されている。キュー１２１には次のようなフォーマットのジョブデータが格納される。当該フォーマットは（処理対象のＷｅｂページのＵＲＬ、処理種別、処理内容、影響度）である。
【００８２】
処理対象のＷｅｂページのＵＲＬには、更新または参照対象とするＷｅｂページのＵＲＬが設定される。処理種別には、更新または参照の何れかを示す情報が設定される。処理内容には、処理種別が更新の場合に、具体的なランクの増減値が設定される。処理内容は、処理種別が参照の場合、設定なしとなる。影響度は、ランク更新の場合、更新要求を受けたＷｅｂページのランク変化によって処理対象のＷｅｂページが受ける影響の度合いを示す。また、ランク参照の場合、参照対象のＷｅｂページに対して処理対象のＷｅｂページが与える影響の度合いを示す。クライアント２００，２００ａから受信した更新要求および参照要求のジョブをキュー１２１に格納する場合、影響度は常に“１”である。
【００８３】
例えば、キュー１２１には、“Ｐ３，更新，増分０．０１，影響度１”という情報が登録されている。これは、ＷｅｂページＰ３について、ランクの更新要求を受信しており、更新内容が０．０１だけランクを増加させるものであること、この更新がＷｅｂページＰ３に対して１００％の影響度をもつことを示す。
【００８４】
また、例えば、キュー１２１には、“Ｐ２，参照，影響度１”という情報が登録されている。これは、ＷｅｂページＰ２について、ランクの参照要求を受信していること、ＷｅｂページＰ２のランク更新はＷｅｂページＰ２自身に対して１００％の影響度をもつことを示す。
【００８５】
更に、例えば、キュー１２１には、“Ｐ２，更新，減少分０．００５，影響度１”という情報が登録されている。これは、ＷｅｂページＰ２について、ランクの更新要求を受信しており、更新内容が０．００５だけランクを減少させるものであること、この更新がＷｅｂページＰ２に対して１００％の影響度をもつことを示す。
【００８６】
キュー１２１には、クライアント２００，２００ａから要求が到着するたびに、キュー制御部１４０により当該要求に関するジョブデータが挿入される。そして、キュー制御部１４０によりＦＩＦＯの手順で各要求に対応するジョブデータが取り出され、ランク処理部１５０に出力される。ランク処理部１５０により、各ジョブが処理される。
【００８７】
なお、あるＷｅｂページでランクが増える場合としては、例えば、次のような場合が考えられる。第１には、当該Ｗｅｂページの既存のリンク元Ｗｅｂページがもつフォワードリンク数が減少することで、当該リンク元Ｗｅｂページから受け取るランクが増加する場合である。第２には、ランクが既知である他のＷｅｂページに当該Ｗｅｂページへのフォワードリンクが追加されることで、当該他のＷｅｂページからランクの分配を新たに受け取るようになる場合である。
【００８８】
また、あるＷｅｂページでランクが減少する場合としては、例えば、当該Ｗｅｂページの既存のリンク元Ｗｅｂページがもつフォワードリンク数が増加することで、当該リンク元Ｗｅｂページから受け取るランクが減少する場合が考えられる。
【００８９】
１つのＷｅｂページでフォワードリンクの追加・削除が行われると、複数の他のＷｅｂページにおいてランクの増減に係る更新が発生し得る。
また、キュー１２１に格納されるデータは、要求元のクライアントを示す情報（例えば、ＩＰ（Internet Protocol）アドレスなど）を含んでもよい。要求に対する応答先を判別可能にするためである。
【００９０】
図８は、第２の実施の形態の更新範囲の例を示す図である。図８ではＷｅｂページの全体集合３００に対して更新範囲Ｒ１が例示されている。更新範囲Ｒ１は、ＷｅｂページＰｘのランクの更新要求を受け付けたときに、その更新の影響を伝搬させる範囲である。更新範囲Ｒ１に含まれるＷｅｂページがランクの更新対象となる。このとき、各Ｗｅｂページが受ける影響度（更新時影響度）は、データＰｘのランクの変化分Δｒに対して各Ｗｅｂページのランクに反映される変化分Δｒ’の割合δ＝Δｒ’／Δｒにより表せる（これを百分率で表してもよい）。ここで、Δｒは−１＜Δｒ＜０、０＜Δｒ＜１の実数である。Δｒ’は−１＜Δｒ’＜０、０＜Δｒ’＜１の実数である。δは０＜δ≦１の実数である。
【００９１】
更新範囲Ｒ１は、影響度閾値ε（εは０＜ε＜１の実数）によって定めることができる。例えば、ＷｅｂページＰｘのランク変化に対し、δ≧εである他のＷｅｂページの集合が更新範囲Ｒ１である。例えば、ε＝０．０５＝５％とする。
【００９２】
図９は、第２の実施の形態の参照範囲の例を示す図である。図９ではＷｅｂページの全体集合３００に対して参照範囲Ｒ２が例示されている。参照範囲Ｒ２は、ＷｅｂページＰｘのランクの参照要求を受け付けたときに、ランクの参照対象とするＷｅｂページの範囲である。ＷｅｂページＰｘのランクに対して、他のＷｅｂページが及ぼす影響度（参照時影響度）は、ＷｅｂページＰｘのランクに反映される他のＷｅｂページのランクの割合γ（γは０＜γ≦１の実数）により表せる。参照時影響度γは、あるＷｅｂページのフォワードリンク数と、当該ＷｅｂページとＷｅｂページＰｘとの間に介入する他のＷｅｂページのフォワードリンク数と、に基づいて算出される。
【００９３】
参照範囲Ｒ２は、影響度閾値ε’（ε’は０＜ε’＜１の実数）によって定めることができる。例えば、ＷｅｂページＰｘのランクの参照要求を受けたとき、ＷｅｂページＰｘのランクに対してγ≧ε’である他のＷｅｂページの集合が参照範囲Ｒ２である。例えば、ε’＝０．０５＝５％とする。
【００９４】
図１０は、第２の実施の形態のランク更新を示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。なお、ステップＳ１１の直前においてキュー１２１に格納されているジョブデータは存在しないものとする。
【００９５】
（ステップＳ１１）受信部１３０は、クライアント２００から更新要求を受信する。受信部１３０は、当該更新要求をキュー制御部１４０に出力する。更新要求は、ＷｅｂページＰ１について、Δｒだけランクを増加させることを示しているとする。なお、ＷｅｂページＰ１の変化分がＷｅｂページＰ１に及ぼす更新時影響度は前述の通りΔｒ／Δｒ＝１である。すなわち、当該更新要求に相当するジョブは（Ｐ１，更新，Δｒ，１）である。
【００９６】
（ステップＳ１２）キュー制御部１４０は、受信部１３０から取得した更新要求のジョブ（Ｐ１，更新，Δｒ，１）をキュー１２１に挿入する。
（ステップＳ１３）キュー制御部１４０は、キュー１２１が空であるか否かを判定する。キュー１２１が空である場合、キュー制御部１４０はランク処理部１５０にその旨を通知して、処理をステップＳ１８に進める。キュー１２１が空でない場合、処理をステップＳ１４に進める。
【００９７】
（ステップＳ１４）キュー制御部１４０は、キュー１２１から更新のジョブ（Ｐ，更新，Δｒ，δ）を取り出して、ランク処理部１５０に出力する。取り出されたジョブは、キュー１２１から削除される。
【００９８】
（ステップＳ１５）ランク処理部１５０は、Ｗｅｂページ管理テーブル１１１を参照して、ＷｅｂページＰのランクにδ×Δｒを加算する。
（ステップＳ１６）ランク処理部１５０は、δ＜εであるか否かを判定する。δ＜εである場合、処理をステップＳ１３に進める。δ≧εである場合、処理をステップＳ１７に進める。
【００９９】
（ステップＳ１７）ランク処理部１５０は、更新のジョブ（Ｐ’，更新，Δｒ，δ’）を生成して、キュー制御部１４０に出力する。キュー制御部１４０は、取得したジョブをキュー１２１に挿入する。ここで、ＷｅｂページＰ’は、ＷｅｂページＰのリンク先（フォワードリンク）のＷｅｂページである。ランク処理部１５０は、Ｗｅｂページ管理テーブル１１１に基づいてＷｅｂページＰ’を取得する。δ’は、ＷｅｂページＰ１からＷｅｂページＰ’に対する影響度である。具体的には、δ’＝δ／（ＷｅｂページＰのフォワードリンク数）である。なお、ここでいうδはステップＳ１４で取り出されたＷｅｂページＰが受ける影響度δである。ＷｅｂページＰのリンク先のＷｅｂページが複数ある場合は、複数のジョブが生成されて、キュー１２１に挿入されることになる。そして、処理がステップＳ１３に進められる。なお、ＷｅｂページＰからのフォワードリンクが存在しない場合は、ステップＳ１７をスキップして、ステップＳ１３に進む。
【０１００】
（ステップＳ１８）ランク処理部１５０は、更新完了の通知を生成して送信部１６０に出力する。更新完了の通知には、クライアント２００を示す情報（例えば、ＩＰアドレスなど）が含まれる。送信部１６０は、更新完了の通知をクライアント２００に応答する。
【０１０１】
このようにして、更新時影響度が影響度閾値εよりも小さくなるまでＷｅｂページのフォワードリンクを辿り、ランクを更新する。上述の手順は、グラフの幅優先探索に基づいている。その探索のステップ数は、更新範囲Ｒ１に含まれるＷｅｂページの数をＮ（Ｎは２以上の整数）およびリンクの数をＭ（Ｍは１以上の整数）とすれば、Ｏ（Ｎ＋Ｍ）である。すなわち、更新範囲Ｒ１が小さいほど更新の処理コストは低減し、更新範囲Ｒ１が大きいほど更新の処理コストは増大する。
【０１０２】
なお、図１０ではＷｅｂページＰ１の更新要求を受け付けた場合を例示したが、他のＷｅｂページの更新要求を受け付けた場合も同様の手順となる。
図１１は、第２の実施の形態の更新時影響度の例を示す図である。図１１は更新時の影響度閾値ε＝５％である場合を例示している。ＷｅｂページＰ１〜Ｐ１７は、Ｗｅｂページの全体集合３００の一部分である。
【０１０３】
ＷｅｂページＰ１はＷｅｂページＰ２，Ｐ３へのフォワードリンクを有する。ＷｅｂページＰ２はＷｅｂページＰ４，Ｐ５へのフォワードリンクを有する。ＷｅｂページＰ３はＷｅｂページＰ５，Ｐ６へのフォワードリンクを有する。ＷｅｂページＰ５はＷｅｂページＰ７，Ｐ８へのフォワードリンクを有する。ＷｅｂページＰ８はＷｅｂページＰ９，Ｐ１０へのフォワードリンクを有する。ＷｅｂページＰ９はＷｅｂページＰ１１，Ｐ１２へのフォワードリンクを有する。ＷｅｂページＰ１１はＷｅｂページＰ１３，Ｐ１４へのフォワードリンクを有する。ＷｅｂページＰ１２はＷｅｂページＰ１４，Ｐ１５へのフォワードリンクを有する。ＷｅｂページＰ１３は、ＷｅｂページＰ１６へのフォワードリンクを有する。ＷｅｂページＰ１４はＷｅｂページＰ１６，Ｐ１７へのフォワードリンクを有する。
【０１０４】
図１０で示した手順によれば、ＷｅｂページＰ１のランク更新に対して、各Ｗｅｂページに及ぶ更新時影響度は次のようになる。ＷｅｂページＰ１に対する影響度は１００％である。
【０１０５】
ＷｅｂページＰ２，Ｐ３に対する影響度は５０％である。ＷｅｂページＰ１がＷｅｂページＰ２，Ｐ３への２つのフォワードリンクを有するからである。すなわち、１００％÷２＝５０％である。
【０１０６】
ＷｅｂページＰ４，Ｐ５，Ｐ６に対する影響度は２５％である。ＷｅｂページＰ２，Ｐ３のそれぞれが２つのフォワードリンクを有するからである。すなわち、５０％÷２＝２５％である。
【０１０７】
ＷｅｂページＰ７，Ｐ８に対する影響度は１２．５％である。ＷｅｂページＰ５がＷｅｂページＰ７，Ｐ８への２つのフォワードリンクを有するからである。すなわち、２５％÷２＝１２．５％である。
【０１０８】
ＷｅｂページＰ９，Ｐ１０に対する影響度は６．２５％である。ＷｅｂページＰ８がＷｅｂページＰ９，Ｐ１０への２つのフォワードリンクを有するからである。すなわち、１２％÷２＝６．２５％である。
【０１０９】
ＷｅｂページＰ１１，Ｐ１２に対する影響度は３．１２％である。ＷｅｂページＰ９がＷｅｂページＰ１１，Ｐ１２への２つのフォワードリンクを有するからである。すなわち、６．２５％÷２＝３．１２５％である（図１１では小数第２位までを表記）。
【０１１０】
ＷｅｂページＰ１３，Ｐ１４，Ｐ１５に対する影響度は１．５６％である。ＷｅｂページＰ１１，Ｐ１２のそれぞれが２つのフォワードリンクを有するからである。すなわち、３．１２５％÷２＝１．５６２５％である（図１１では小数第２位までを表記）。
【０１１１】
ＷｅｂページＰ１６に対する影響度は１．５６％である。ＷｅｂページＰ１３がＷｅｂページＰ１６への１つのフォワードリンクを有するからである。すなわち、１．５６％÷１＝１．５６％である。ただし、ＷｅｂページＰ１６は、ＷｅｂページＰ１４からの影響度０．７８％もある（ＷｅｂページＰ１４は２つのフォワードリンクをもつため）。この場合、ＷｅｂページＰ１６に対する影響度を１．５６％＋０．７８％＝２．３４％と評価してもよい。
【０１１２】
ＷｅｂページＰ１７に対する影響度は０．７８％である。ＷｅｂページＰ１４がＷｅｂページＰ１６，Ｐ１７への２つのフォワードリンクを有するからである。すなわち、１．５６２５％÷２＝０．７８１２５％である（図１１では小数第２位までを表記）。
【０１１３】
この場合、更新時影響度がεよりも初めて小さくなるのは、ＷｅｂページＰ１からフォワードリンクを辿っていくと、ＷｅｂページＰ１１，Ｐ１２である。すなわち、ＷｅｂページＰ１〜Ｐ１２が更新範囲Ｒ１に含まれるＷｅｂページとなる。よって、ランク処理部１５０は、ＷｅｂページＰ１からフォワードリンクを辿り、ＷｅｂページＰ２〜Ｐ１２のランクを更新する。一方、ＷｅｂページＰ１３〜Ｐ１７のランクは更新しない。
【０１１４】
図１２は、第２の実施の形態のランク参照を示すフローチャートである。以下、図１２に示す処理をステップ番号に沿って説明する。なお、ステップＳ２１の直前においてキュー１２１に格納されているジョブデータは存在しないものとする。
【０１１５】
（ステップＳ２１）受信部１３０は、クライアント２００から参照要求を受信する。受信部１３０は、当該参照要求をキュー制御部１４０に出力する。当該参照要求では、ＷｅｂページＰ１６が指定されているものとする。なお、ＷｅｂページＰ１６のランクがＷｅｂページＰ１６のランクに及ぼす参照時影響度を前述の通り“１”としている。すなわち、当該参照要求に相当するジョブは（Ｐ１６，参照，１）である。
【０１１６】
（ステップＳ２２）キュー制御部１４０は、ＷｅｂページＰ１６の参照要求を受け付けたことをランク処理部１５０に通知する。ランク処理部１５０は、ＷｅｂページＰ１６のランクａをａ＝０に初期化する。
【０１１７】
（ステップＳ２３）キュー制御部１４０は、当該参照要求のジョブ（Ｐ１６，参照，１）をキュー１２１に挿入する。
（ステップＳ２４）キュー制御部１４０は、キュー１２１が空であるか否かを判定する。キュー１２１が空である場合、キュー制御部１４０はランク処理部１５０にその旨を通知して、処理をステップＳ２９に進める。キュー１２１が空でない場合、処理をステップＳ２５に進める。
【０１１８】
（ステップＳ２５）キュー制御部１４０は、キュー１２１から参照のジョブ（Ｐ，参照，γ）を取り出して、ランク処理部１５０に出力する。取り出されたジョブは、キュー１２１から削除される。
【０１１９】
（ステップＳ２６）ランク処理部１５０は、Ｗｅｂページ管理テーブル１１１を参照して、ＷｅｂページＰのランクを取得する。ただし、ＷｅｂページＰがＷｅｂページＰ１６にする場合、当該ランク値は０である。ランク処理部１５０は、γ×（ＷｅｂページＰのランク）をＷｅｂページＰ１６のランクａに加算する。
【０１２０】
（ステップＳ２７）ランク処理部１５０は、γ＜ε’であるか否かを判定する。γ＜ε’である場合、処理をステップＳ２４に進める。γ≧ε’である場合、処理をステップＳ２８に進める。
【０１２１】
（ステップＳ２８）ランク処理部１５０は、参照のジョブ（Ｐ’，参照，αγ’）を生成して、キュー制御部１４０に出力する。キュー制御部１４０は、取得したジョブをキュー１２１に挿入する。ここで、ＷｅｂページＰ’は、ＷｅｂページＰのリンク元（バックリンク）のＷｅｂページである。ランク処理部１５０は、Ｗｅｂページ管理テーブル１１１に基づいてＷｅｂページＰ’を取得する。αγ’は、ＷｅｂページＰ’からＷｅｂページＰ１６に対する影響度である。γ’は、γ’＝γ／（ＷｅｂページＰ’のフォワードリンク数）により得られる値である。αは補正係数であり、０＜α＜１の実数である。なお、ここでいうγはステップＳ２５で取り出されたＷｅｂページＰからの影響度γである。ＷｅｂページＰへのリンク元のＷｅｂページが複数ある場合は、複数のジョブが生成されて、キュー１２１に挿入されることになる。そして、処理がステップＳ２４に進められる。なお、ＷｅｂページＰへのバックリンクが存在しない場合は、ステップＳ２８をスキップして、ステップＳ２４に進む。
【０１２２】
（ステップＳ２９）ランク処理部１５０は、ＷｅｂページＰ１６のランクａの通知を送信部１６０に出力する。当該通知には、クライアント２００を示す情報（例えば、ＩＰアドレスなど）が含まれる。送信部１６０は、ＷｅｂページＰ１６のランクａをクライアント２００に応答する。
【０１２３】
このようにして、ＷｅｂページＰ１６への参照時影響度がε’よりも小さくなるまで、バックリンクを辿り、各Ｗｅｂページのランクに参照時影響度を乗じた値を、ＷｅｂページＰ１６のランクに加算していく。なお、上述の手順はグラフの幅優先探索に基づいている。その探索のステップ数は、参照範囲Ｒ２に含まれるＷｅｂページの数をＮ（Ｎは２以上の整数）およびリンクの数をＭ（Ｍは１以上の整数）とすれば、Ｏ（Ｎ＋Ｍ）である。すなわち、参照範囲Ｒ２が小さいほど参照の処理コストは低減し、参照範囲Ｒ２が大きいほど参照の処理コストは増大する。
【０１２４】
なお、図１２ではＷｅｂページＰ１６の参照要求を受け付けた場合を例示したが、他のＷｅｂページの参照要求を受け付けた場合も同様の手順となる。
図１３は、第２の実施の形態の参照時影響度の例を示す図である。図１３は参照時の影響度閾値ε’＝５％，α＝８０％である場合を例示している。ＷｅｂページＰ１〜Ｐ１７のグラフ構造は、図１１と同様である。
【０１２５】
図１２で示した手順によれば、ＷｅｂページＰ１６のランク参照に対して、各ＷｅｂページからＷｅｂページＰ１６に対する参照時影響度は次のようになる。ＷｅｂページＰ１６からの影響度は１００％である。
【０１２６】
ＷｅｂページＰ１３からの影響度は８０％である。ＷｅｂページＰ１３はＷｅｂページＰ１６への１つのフォワードリンクを有するからである。すなわち、１００％÷１×０．８＝８０％である。
【０１２７】
ＷｅｂページＰ１４からの影響度は４０％である。ＷｅｂページＰ１４はＷｅｂページＰ１６，Ｐ１７への２つのフォワードリンクを有するからである。すなわち、１００％÷２×０．８＝４０％である。
【０１２８】
ＷｅｂページＰ１１，Ｐ１２からの影響度は１６％である。ＷｅｂページＰ１１，Ｐ１２のそれぞれは２つのフォワードリンクを有するからである。すなわち、４０％÷２×０．８＝１６％である。
【０１２９】
ＷｅｂページＰ９からの影響度は６．４％である。ＷｅｂページＰ９はＷｅｂページＰ１１，Ｐ１２への２つのフォワードリンクを有するからである。すなわち、１６％÷２×０．８＝６．４％である。
【０１３０】
ＷｅｂページＰ８からの影響度は２．５６％である。ＷｅｂページＰ８はＷｅｂページＰ９，Ｐ１０への２つのフォワードリンクを有するからである。すなわち、６．４％÷２×０．８＝２．５６％である。
【０１３１】
ＷｅｂページＰ５からの影響度は１．０２％である。ＷｅｂページＰ５はＷｅｂページＰ７，Ｐ８への２つのフォワードリンクを有するからである。すなわち、２．５６％÷２×０．８＝１．０２４％である（図１３では小数第２位までを表記）。
【０１３２】
ＷｅｂページＰ２，Ｐ３からの影響度は０．４０％である。ＷｅｂページＰ２，Ｐ３のそれぞれは２つのフォワードリンクを有するからである。すなわち、１．０２４％÷２×０．８＝０．４０９６％である（図１３では小数第２位までを表記）。
【０１３３】
ＷｅｂページＰ１からの影響度は０．１６％である。ＷｅｂページＰ１はＷｅｂページＰ２，Ｐ３への２つのフォワードリンクを有するからである。すなわち、０．４０９６％÷２×０．８＝０．１６３８４％である（図１３では小数第２位までを表記）。
【０１３４】
上記以外のＷｅｂページＰ４，Ｐ６，Ｐ７，Ｐ１０，Ｐ１５，Ｐ１７は、ＷｅｂページＰ１６に繋がるフォワードリンクを有していない。このため、ＷｅｂページＰ４，Ｐ６，Ｐ７，Ｐ１０，Ｐ１５，Ｐ１７からＷｅｂページＰ１６に対する影響度は０％である。
【０１３５】
この場合、参照時影響度がε’よりも初めて小さくなるのは、ＷｅｂページＰ１６からバックリンクを辿っていくと、ＷｅｂページＰ８である。すなわち、ＷｅｂページＰ８，Ｐ９，Ｐ１１，Ｐ１２，Ｐ１４，Ｐ１６が参照範囲Ｒ２に含まれるＷｅｂページとなる。よって、ランク処理部１５０は、ＷｅｂページＰ１６からバックリンクを辿り、ＷｅｂページＰ１４，Ｐ１３，Ｐ１２，Ｐ１１，Ｐ９，Ｐ８のランクに基づいて、ＷｅｂページＰ１６のランクを計算する。
【０１３６】
これにより、ランクを更新するための処理コストを軽減しながら、ランク評価の信頼性を高めることができる。具体的には、ランクの更新時において更新範囲Ｒ１に含まれるＷｅｂページのランクのみを更新することで、処理コストを軽減できる。ただし、更新の影響の伝搬が制限されることになるので、更新範囲Ｒ１の外部のＷｅｂページ（図１１の例でいえばＷｅｂページＰ１３〜Ｐ１７）についてランクの精度が悪化し得る。このため、当該Ｗｅｂページについて、ランクの参照要求を受けた時に、当該Ｗｅｂページのランクを単に抽出して応答するのみでは、応答されたランクの信頼性は低いことになる。
【０１３７】
そこで、サーバ１００，１００ａは、あるＷｅｂページのランクの参照時に参照範囲Ｒ２に含まれるＷｅｂページのランクを考慮して、参照対象のＷｅｂページのランクを求める。例えば、上記のようにＷｅｂページＰ１６のランクを参照する際に、ＷｅｂページＰ１６のランクに影響を及ぼす所定範囲のＷｅｂページのランクに基づいて、当該ＷｅｂページＰ１６のランクを評価して応答する。このため、例えばＷｅｂページＰ１の更新の影響がＷｅｂページＰ１６に伝搬していなかったとしても、関連するＷｅｂページに対して当該影響が伝搬していれば、当該影響を参照対象のＷｅｂページＰ１６に反映させてランクを得ることができる。すなわち、その時点においてＷｅｂページＰ１６につき、より信頼性の高いランクを得られることになる。このとき、参照するランクの誤差（式（５），（６）に基づいて厳密に算出されるランクに対する誤差）は、影響度閾値ε，ε’を用いてεε’程度となることが期待される。ランクの分配を途中で打ち切る場合の誤差が更新時の影響度閾値ε程度とすると、０＜ε’＜１であるから、εε’＜εである。すなわち、ランクの分配を途中で打ち切る場合に、あるＷｅｂページのランクを単に読み出す方法に比べて誤差を改善し得る。よって、ランク評価の信頼性を向上し得る。
【０１３８】
上記の方法は、例えばあるＷｅｂページの更新に対し、より短時間で更新の影響を他のＷｅｂページに反映させたい場合に有用である。Ｗｅｂページの更新の頻度が比較的高ければ、更新時の影響度閾値εを参照時の影響度閾値ε’よりも大きくしておく（更新範囲Ｒ１を狭める）。すると、更新処理の処理コストを軽減でき、頻繁に発生するＷｅｂページの更新に追随して、各Ｗｅｂページのランクをリアルタイムに更新し得る。その場合、例えば、ε’をεよりも小さくしておく（参照範囲Ｒ２を広げる）。更新時の影響度閾値と参照時の影響度閾値との積εε’が一定になるようにε，ε’を変化させれば、変化の前後で、参照するランクについて期待される誤差をおおよそ一定に保つことができる。なお、例えば参照の頻度が比較的多ければ、逆にε’を大きくし、εを小さくすることも考えられる。
【０１３９】
［第３の実施の形態］
以下、第３の実施の形態を説明する。前述の第２の実施の形態との相違点を主に説明し、共通する事項の説明を省略する。
【０１４０】
第３の実施の形態では、更新要求の頻度および参照要求の頻度に応じて、影響度閾値ε，ε’を動的に変化させる機能を提供する。ここで、第３の実施の形態の情報処理システムは、図２で説明した第２の実施の形態の情報処理システムと同様である。また、第３の実施の形態のサーバのハードウェア例およびソフトウェア例は、図４，５で説明した第２の実施の形態のサーバ１００のハードウェア例およびソフトウェア例と同様である。このため、第３の実施の形態の各装置を第２の実施の形態と同一の名称・符号を付して示す。
【０１４１】
ただし、ページ情報記憶部１１０は、ログテーブルを更に記憶する点が第２の実施の形態と異なる。ログテーブルは、更新範囲Ｒ１の外部との境界に位置する更新範囲Ｒ１内のＷｅｂページに対するランクの更新内容を記録したものである。
【０１４２】
また、ランク処理部１５０は、過去の所定期間（例えば１日、１週間など）における更新要求の頻度および参照要求の頻度に応じて、影響度閾値ε，ε’を変化させる点が第２の実施の形態と異なる。
【０１４３】
図１４は、第３の実施の形態のログテーブルの例を示す図である。ログテーブル１１２は、ページ情報記憶部１１０に記憶される。ログテーブル１１２は、開始ノード、終了ノードおよびランク増分の項目を含む。
【０１４４】
開始ノードの項目には、更新要求で指定されたＷｅｂページのＵＲＬが登録される。終了ノードの項目には、更新処理の終端となったＷｅｂページのＵＲＬが登録される。更新処理の終端のＷｅｂページとは、更新範囲Ｒ１の外部との境界に位置する更新範囲Ｒ１内のＷｅｂページである。ランク増分の項目には、ランクの増分値が登録される。ランクの増分値は負の値でもよい（その場合はランクの減少分を示すことになる）。
【０１４５】
例えば、ログテーブル１１２には、開始ノードが“Ｐ１”、終了ノードが“Ｐ１１”、ランク増分が“０．００２”という情報が登録されている。これは、ＷｅｂページＰ１のランクの更新要求を受信し、その際に更新処理の終端となったＷｅｂページがＷｅｂページＰ１１であったことを示す。また、このときのＷｅｂページＰ１１のランクの増分値が“０．００２”であったことを示す。
【０１４６】
ある開始ノードに対して複数の終了ノードが登録されることもある。ログテーブル１１２の例では開始ノードであるＷｅｂページＰ１に対して、終了ノードである２つのＷｅｂページＰ１１，Ｐ１２が登録されている。
【０１４７】
なお、ランク処理部１５０は、図１０のステップＳ１８において、更新処理の結果に基づいてログテーブル１１２にレコードを登録する。図１１の例でいえば、ＷｅｂページＰ１（開始ノード）に対して、更新範囲Ｒ１に含まれるＷｅｂページＰ１１，Ｐ１２（終了ノード）の情報を、ログテーブル１１２に登録することになる。
【０１４８】
図１５は、第３の実施の形態の更新・参照範囲の変更を示すフローチャートである。以下、図１５に示す処理をステップ番号に沿って説明する。
（ステップＳ３１）ランク処理部１５０は、クライアント２００，２００ａから過去の所定期間内（例えば、１日）に受け付けた更新要求の頻度および参照要求の頻度の比率を確認する。ランク処理部１５０は、参照要求の頻度の比率が、デフォルトの比率よりも増大しているか否かを判定する。デフォルトの比率よりも増大している場合、処理をステップＳ３２に進める。デフォルトの比率よりも増大していない場合、処理をステップＳ３５に進める。例えば、更新要求の頻度：参照要求の頻度のデフォルトの比率を、１：２などのようにランク処理部１５０に予め与えておく。デフォルトの比率に応じて影響度閾値ε，ε’についてもデフォルトの値が定められる。例えば、上記比率１：２に対して、ε＝５％，ε’＝１０％とする。
【０１４９】
（ステップＳ３２）ランク処理部１５０は、更新時の影響度閾値εを現在値よりも小さくする。例えば、ステップＳ３１で例示したデフォルトの比率に対して、更新要求の頻度：参照要求の頻度が１：４（参照要求の頻度が２倍）になっているとする。その場合、例えば、εを２分の１にする。後述のようにε’を２倍にして参照の処理コストを軽減し、かつ、誤差のオーダを維持するためである。すなわち、ε＝５％÷２＝２．５％とする。これは、更新範囲Ｒ１を広げることに相当する。
【０１５０】
（ステップＳ３３）ランク処理部１５０は、ログテーブル１１２に基づいて、拡大した後の更新範囲と拡大前の更新範囲との差分の範囲に含まれる各Ｗｅｂページのランクを更新する。詳細は後述する。
【０１５１】
（ステップＳ３４）ランク処理部１５０は、参照時の影響度閾値ε’を現在値よりも大きくする。ステップＳ３２での例示を継続して説明すれば、ε’を２倍にする。すなわち、ε’＝１０％×２＝２０％とする。これは、参照範囲Ｒ２を狭めることに相当する。そして、処理を終了する。
【０１５２】
（ステップＳ３５）ランク処理部１５０は、更新要求の頻度の比率が、デフォルトの比率よりも増大しているか否かを判定する。デフォルトの比率よりも増大している場合、処理をステップＳ３６に進める。デフォルトの比率よりも増大していない場合、処理を終了する。
【０１５３】
（ステップＳ３６）ランク処理部１５０は、更新時の影響度閾値εを現在値よりも大きくする。例えば、ステップＳ３１で例示したデフォルトの比率に対して、更新要求の頻度：参照要求の頻度が２：２（更新要求の頻度が２倍）になっているとする。その場合、例えば、εを２倍にする。すなわち、ε＝５％×２＝１０％とする。これは、更新範囲Ｒ１を狭めることに相当する。更新の処理コストを軽減するためである。
【０１５４】
（ステップＳ３７）ランク処理部１５０は、参照時の影響度閾値ε’を現在値よりも小さくする。ステップＳ３６での例示を継続して説明すれば、ε’を２分の１にする。誤差のオーダを維持するためである。すなわち、ε’＝１０％÷２＝５％とする。これは、参照範囲Ｒ２を広げることに相当する。そして、処理を終了する。
【０１５５】
このようにして、ランク処理部１５０は定期的に影響度閾値ε，ε’を調整する。このようにすれば、更新要求の頻度および参照要求の頻度に応じて、更新範囲Ｒ１および参照範囲Ｒ２を変更でき、要求の受信状況に応じて効率的に処理コストを削減できるようになる。特に、例示したように更新時の影響度閾値と参照時の影響度閾値との積εε’が一定になるように調整すれば、ε，ε’の変更前後においてランクの評価精度を一定に保つことができる。
【０１５６】
なお、図１５の手順において、ステップＳ３３の処理をスキップしてステップＳ３４を先に実行しておき、ステップＳ３３の処理をランクの更新・参照の通常の処理と並行して行ってもよい。
【０１５７】
図１６は、第３の実施の形態の更新・参照範囲の変更例（その１）を示す図である。図１６では更新範囲を広げて、参照範囲を狭める場合を例示する。図１５のステップＳ３２〜Ｓ３４に相当する処理である。
【０１５８】
図１６（Ａ）は、影響度閾値の変更前の状態の更新範囲Ｒ１０および参照範囲Ｒ２０を例示している。このとき、例えば、更新範囲Ｒ１０に対応する更新時の影響度閾値ε＝５％である。また、例えば、参照範囲Ｒ２０に対応する参照時の影響度閾値ε’＝１０％である。
【０１５９】
図１６（Ｂ）は、図１６（Ａ）よりもεを小さくした状態を例示している。例えば、ε＝２．５％である。これにより、更新範囲Ｒ１０は更新範囲Ｒ１１に広がる。すると、更新範囲Ｒ１０，Ｒ１１について差分領域ΔＲが生ずることになる。そこで、ランク処理部１５０は、差分領域ΔＲに含まれるＷｅｂページにつき、ログテーブル１１２に基づいてランクの更新を行う。ランクの参照時の評価精度を高めるためである。
【０１６０】
具体的には、ログテーブル１１２に記録された開始ノードを起点とした変更の影響を、終了ノードのフォワードリンク先まで伝搬させる。伝搬の範囲（更新範囲Ｒ１１）は開始ノードを起点としたフォワードリンクのツリーと変更後の影響度閾値εとにより定まる。このとき、ログテーブル１１２には、終了ノードのランク増分が登録されている。よって、終了ノードのフォワードリンク先を起点に終了ノードのランク増分の影響を伝搬させればよい（更新範囲Ｒ１０内のＷｅｂページのランクは改めて計算しなくてよい）。
【０１６１】
図１６（Ｃ）は、図１６（Ｂ）よりもε’を大きくした状態を例示している。例えば、ε’＝２０％である。これにより、参照範囲Ｒ２０は参照範囲Ｒ２１に狭まる。その結果、参照時の処理コストを軽減できる。その代わり、更新範囲Ｒ１０を更新範囲Ｒ１１のように拡張しているので、ランクの参照精度を、図１６（Ａ）の状態と同程度に維持することができる。
【０１６２】
図１７は、第３の実施の形態の更新・参照範囲の変更例（その２）を示す図である。図１７では更新範囲を狭めて、参照範囲を広げる場合を例示する。図１５のステップＳ３６，Ｓ３７に相当する処理である。
【０１６３】
図１７（Ａ）は、影響度閾値の変更前の状態の更新範囲Ｒ１０ａおよび参照範囲Ｒ２０ａを例示している。このとき、例えば、更新範囲Ｒ１０ａに対応する更新時の影響度閾値ε＝５％である。また、例えば、参照範囲Ｒ２０ａに対応する参照時の影響度閾値ε’＝１０％である。
【０１６４】
図１７（Ｂ）は、図１７（Ａ）よりもεを大きくした状態を例示している。例えば、ε＝１０％である。これにより、更新範囲Ｒ１０ａは更新範囲Ｒ１１ａに狭まる。
図１７（Ｃ）は、図１７（Ｂ）よりもε’を小さくした状態を例示している。例えば、ε’＝５％である。これにより、参照範囲Ｒ２０ａは参照範囲Ｒ２１ａに広がる。
【０１６５】
このように、更新範囲Ｒ１０ａを更新範囲Ｒ１１ａに狭めることで、更新時の処理コストを軽減できる。その代わり、参照範囲Ｒ２０ａを参照範囲Ｒ２１ａのように拡張しているので、ランクの参照精度を、図１７（Ａ）の状態と同程度に維持することができる。
【０１６６】
以上のように、第３の実施の形態では更新要求の頻度および参照要求の頻度に応じて、Ｗｅｂページのランクの更新範囲および参照範囲を変更するようにした。具体的には、更新要求の頻度がデフォルトよりも高まれば、更新範囲を狭める（縮小する）。これにより、更新要求の頻度が高い場合に、更新処理の処理コストを軽減することができる。一方、参照要求の頻度がデフォルトよりも高まれば、参照範囲を狭める（縮小する）。これにより、参照要求の処理コストを軽減して、より早くランクの評価結果を応答することができる。
【０１６７】
このとき、更新範囲を縮小したならば参照範囲を拡大し、また、参照範囲を縮小したならば更新範囲を拡大するように制御する。これによって、参照時に得られるランクの信頼性が低下するのを抑制できる。
【０１６８】
ここで、第２，第３の実施の形態では、Ｗｅｂページをランク付けする場合を例示したが、他の場合にも利用できる。例えば、論文を評価する際に利用することが考えられる。論文は、他の論文を引用することが多い。このため、第１の論文（例えば、論文の文書データ）を有向グラフのノード２１に、第２の論文を有向グラフのノード２２に、第１の論文における第２の論文の引用を有向グラフの矢印２３（リンク）に対応付けることができる。これによって、論文ごとの重要度を示す評価値を評価することが考えられる。同様にして、特許文献の評価に利用することも考えられる。特許文献も先行技術文献を引用するからである。
【０１６９】
更に、文書以外を評価する場合にも利用できる。例えば、オンラインの通信販売などでお薦めの商品を提示するような場合である。例えば、ユーザが購入した第１，第２の商品を示す情報を有向グラフのノード２１，２２に、第１の商品が購入された場合、同じユーザにより第２の商品も購入されるという関連を矢印２３（リンク）に対応付けることができる。すなわち、第１の商品を示す情報に、第２の商品を示す情報を指し示すリンクを含めたデータを作成し得る。このデータを用いて、商品ごとのお薦め度を示す評価値を評価することが考えられる。
【０１７０】
なお、前述のように、第１の実施の形態の情報処理は、情報処理装置１にプログラムを実行させることで実現できる。また、第２の実施の形態の情報処理は、サーバ１００，１００ａにプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体（例えば、光ディスク１３、メモリ装置１４およびメモリカード１６など）に記録できる。
【０１７１】
プログラムを流通させる場合、例えば、当該プログラムを記録した可搬記録媒体が提供される。また、プログラムを他のコンピュータの記憶装置に格納しておき、ネットワーク経由でプログラムを配布することもできる。コンピュータは、例えば、可搬記録媒体に記録されたプログラムまたは他のコンピュータから受信したプログラムを、記憶装置に格納し、当該記憶装置からプログラムを読み込んで実行する。ただし、可搬記録媒体から読み込んだプログラムを直接実行してもよく、他のコンピュータからネットワークを介して受信したプログラムを直接実行してもよい。
【０１７２】
また、上記の情報処理の少なくとも一部を、ＤＳＰ、ＡＳＩＣ、ＰＬＤなどの電子回路で実現することもできる。
【符号の説明】
【０１７３】
１  情報処理装置
１ａ  記憶部
１ｂ  演算部
２，３  グラフ構造
２ａ，４ａ，４ｄ  更新範囲
３ａ，４ｂ，４ｃ，４ｅ  参照範囲
４  データの全体集合
【図１】
2014044552.tif 000009
【図２】
2014044552.tif 000010
【図３】
2014044552.tif 000011
【図４】
2014044552.tif 000012
【図５】
2014044552.tif 000013
【図６】
2014044552.tif 000014
【図７】
2014044552.tif 000015
【図８】
2014044552.tif 000016
【図９】
2014044552.tif 000017
【図１０】
2014044552.tif 000018
【図１１】
2014044552.tif 000019
【図１２】
2014044552.tif 000020
【図１３】
2014044552.tif 000021
【図１４】
2014044552.tif 000022
【図１５】
2014044552.tif 000023
【図１６】
2014044552.tif 000024
【図１７】
2014044552.tif 000025