(57)【特許請求の範囲】
【請求項１】
複数のウェブ・ページを有する複数のウェブサイトを含むコンテンツ配信ネットワークにおいて、一組のウェブ・ページＶと、無向近傍グラフＧN（ＶN、ＥN）として表されるウェブ・ページの間の一組のリンクＥとを持つウェブ空間が、さらに、Ｖ内のシード・ウェブ・ページｖa，ｖbを含む場合に、ｖa，ｖb、および他のウェブ・ページｖi∈Ｖの間の関連を推定し、ウェブ・ページをウェブ・ページメモリに予備取り出しするための方法であって、
ＶN内にｖiおよびｖjの両方が存在する場合に、各ｖi∈ＶNに対して、Ｖ内に新しいｖi'を作り出し、各ｅk＝＜ｖi'，ｖj'＞∈ＥNに対して、Ｅ内に二つの有向辺ｅ'2×k＝＜ｖi'，ｖj'＞およびｅ'2×k+1＝＜ｖj'，ｖi'＞を作り出し、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を生成して構成した有向ランダム・ウォーク・グラフをメモリに格納し、
Ｔ［ｊ，ｉ］が、節点ｖjから節点ｖiへの移動の可能性を示すＥ内の各有向辺に対して遷移値を表す場合に、前記ペナルティ値ｐｅｎａｌｔｙ（ｖi'）に基づいて、｜Ｖ｜×｜Ｖ｜遷移マトリックスＴを生成してメモリに格納し、
各ｖi∈Ｖに対して、ｔ［ｉ］が、シード・ウェブ・ページとｖiとの間の関連を示す場合に、前記遷移マトリックスＴの定常状態分布（収束ベクトル）ｔを生成してメモリに格納し、
ウェブ・ページを前記ｔ［ｉ］の降順に取り出して前記ウェブ・ページメモリに格納する、
段階を含み、
前記ペナルティ値ｐｅｎａｌｔｙ（ｖi'）の生成は、
ＧN内におけるｖi'とｖaに対応する節点ｖa'との間の最短距離としてｓｄｉｓｔ（ｖi'，ｖa'）を計算する段階と、
ＧN内におけるｖi'とｖbに対応する節点ｖb'との間の最短距離としてｓｄｉｓｔ（ｖi'，ｖb'）を計算する段階と、
ｐｅｎａｌｔｙ（ｖi'）＝ｓｄｉｓｔ（ｖi'，ｖa'）＋ｓｄｉｓｔ（ｖi'，ｖb'）を計算する段階と、
を含む、
ことを特徴とする方法。
【請求項２】
｜Ｖ｜×｜Ｖ｜遷移マトリックスＴを生成する段階が、
すべての節点ｖi'∈Ｖおよび、すべての
【数１】
0003659181.tif 000022
に対して、Ｔ［ｊ，ｉ］＝０．０をリセットする段階と、
すべての節点ｖi'∈Ｖに対して、下記一組の一次式、
【数２】
0003659181.tif 000023
を解く段階と
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
Ｔの定常状態分布（収束ベクトル）ｔを生成する段階が、
Ｉが単位マトリックスであり、また、
【数３】
0003659181.tif 000024
である場合に、一次式（Ｉ−Ｔ）ｔ＝０を解く段階
を含むことを特徴とする請求項２に記載の方法。
【請求項４】
ランダム・ウォーク・グラフを構成するためのＧN（ＶN，ＥN）の関連近傍を、
【数４】
0003659181.tif 000025
という一組の節点として定義する段階をさらに含み、該節点には、
【数５】
0003659181.tif 000026
となるようなｄの辺トラバーサル内のｖaまたはｖbから到達可能であることを特徴とする請求項１に記載の方法。
【請求項５】
前記ウェブ空間が、Ｖ内に一組のシード・ウェブ・ページ｜Ｓ｜≧２をさらに含み、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を生成する段階が、該ペナルティ値を、
【数６】
0003659181.tif 000027
として計算する段階を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記ウェブ空間が、Ｖ内に一組のシード・ウェブ・ページ｜Ｓ｜≧２をさらに含み、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を生成する段階が、ｐｅｎａｌｔｙ（ｖi'）＝ｌｅｎｇｔｈ（ｍｉｎｉｍｕｍ＿ｓｔｅｉｎｅｒ＿ｔｒｅｅ（Ｓ∪｛ｖi'｝））としてペナルティ値を計算する段階を含むことを特徴とする請求項１に記載の方法。
【請求項７】
ランダム・ウォーク・グラフを構成するためのＧN（ＶN，ＥN）の関連近傍を、
【数７】
0003659181.tif 000028
という一組の節点として定義する段階をさらに含み、該節点には、
【数８】
0003659181.tif 000029
となるようなｄの辺トラバーサル内のＳ内の節点の中のいずれかから到達可能であることを特徴とする請求項６に記載の方法。
【請求項８】
各ウェブ・ページｖi∈Ｖが、特定のトピックｒｅｌｅｖａｎｃｅ（ｖ，ｔｏｐｉｃ）に対する既知の関連値を持ち、前記方法が、ｒｅｌｅｖａｎｃｅ（ｖ，ｔｏｐｉｃ）でｐｅｎａｌｔｙ（ｖi'）を除算することにより、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を調整する段階をさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
複数のウェブ・ページを有する複数のウェブサイトを含むコンテンツ配信ネットワークにおいて、一組のウェブ・ページＶと、有向グラフＧ（Ｖ，Ｅ）としてモデル化されたウェブ・ページＥの間の一組のリンクとを持つウェブ空間において、Ｏvが主ＨＴＭＬファイルを含む一組の媒体オブジェクトであり、ａvがページ著者であり、各オブジェクトｏ∈Ｏvが、エンドユーザーｕに対する既知のエンドユーザー優先順位ｕｐｒｅｆ（ｕ）およびページ著者ａvに対するページ著者優先順位ａｐｒｅｆ（ａv）を持つ場合に、各ウェブ・ページｖi∈Ｖがペア（Ｏv，ａv）を含み、前記ウェブ空間が、シード・ウェブ・ページｖcに位置するエンドユーザーｕをさらに含む場合に、前記媒体オブジェクトと前記シード・ウェブ・ページとの間の関連を推定し、ウェブ・ページをウェブ・ページメモリに予備取り出しするための方法であって、
該方法が、
Ｏvのコンテンツに対し、ｕｐｒｅｆ（ｕ）およびａｐｒｅｆ（ａv）により定義される優先順位規則を適用することにより、各ウェブ・ページｖiに対するページ優先順位重みｐｒｅｆ（ｕ，ｖ）をメモリに格納し、
Ｏvのコンテンツに対し、ｕｐｒｅｆ（ｕ）およびａｐｒｅｆ（ａv）により定義される優先順位規則を適用することにより、各オブジェクトｏ∈Ｏvに対するオブジェクト優先順位重みｐｒｅｆ（ｕ，ｏ，ｖ）をメモリに格納し、
一組の節点Ｖwと一組の辺Ｅwとを持つランダム・ウォーク・グラフＧwをメモリに格納し、
ランダム・ウォーク・グラフの定常状態分布（収束ベクトル）を見出すことによりページ利得ｇａｉｎ（ｕ，ｖ）を生成し、
オブジェクト利得が、前記オブジェクトと前記シード・ウェブ・ページとの間の関連を表す場合に、各オブジェクトに対するオブジェクト利得ｇａｉｎ（ｕ，ｏ）を
【数９】
0003659181.tif 000030
として算出する、
段階を含むことを特徴とする方法。
【請求項１０】
一組の節点Ｖwと一組の辺Ｅwとを持つランダム・ウォーク・グラフＧwを生成する段階が、
Ｖ内の各ウェブ・ページに対して、Ｖw内に節点ｖiを作り出す段階と、
Ｅ内の各辺ｅj＝＜ｖa，ｖb＞に対してＥw内に二つの辺ｅj'＝＜ｖa'，ｖb'＞およびｅj"＝＜ｖb'，ｖa'＞を作り出す段階と、
Ｅ内の各辺ｅj＝＜ｖa，ｖb＞に対して辺の重みｗ（ｅ）＝ｓ（ｕ，ｖj）を割り当てる段階と
を含むことを特徴とする請求項９に記載の方法。
【請求項１１】
ｓ（ｕ，ｖj）が、各ウェブ・ページｖj∈Ｖに対する既知の密着性の数値であることを特徴とする請求項１０に記載の方法。
【請求項１２】
ｓ（ｕ，ｖj）に、Ｅ内の各辺ｅj＝＜ｖa，ｖb＞に対する単位値が割り当てられることを特徴とする請求項１０に記載の方法。
【請求項１３】
ｓ（ｕ，ｖj）に、領域境界を横切るＥ内の各辺ｅj＝＜ｖa，ｖb＞に対する単位値より大きい数値が割り当てられることを特徴とする請求項１０に記載の方法。
【請求項１４】
定常状態分布（収束ベクトル）を見出すことによりページ利得ｇａｉｎ（ｕ，ｖ）を計算する前記段階が、
最短経路アルゴリズムを使用して、前記辺の重みを考慮に入れながら、節点ｖcからすべての節点ｖi'∈Ｖまでの最短距離ｓｈｏｒｔｅｓｔ（ｖc，ｖi）を見出す段階と、
各節点ｖ∈ＶWに対して、ペナルティｐｅｎａｌｔｙ（ｕ，ｖ）＝ｓｈｏｒｔｅｓｔ（ｖc，ｖi）／（ｐｒｅｆ（ｕ，ｖ）＋１）を計算する段階と、
【数１０】
0003659181.tif 000031
を解くことにより単位確率ｕｎｉｔ（ｕ，ｖ）を計算する段階と、
各辺ｅ＝∈＜ｖi，ｖj＞∈ＶWに対して、ｐｒｏｂ（ｕ）（ｖj｜ｖi）＝ｕｎｉｔ（ｕ，ｖj）／ｐｅｎａｌｔｙ（ｕ，ｖi）を計算する段階と、
各ｖi∈Ｖに対して、Ｔが遷移値ｐｒｏｂ（ｕ）（ｖj｜ｖi）のマトリックスである場合で、ｔ［ｉ］が、前記シード・ウェブ・ページとｖiとの間の関連を表す場合に、Ｔの定常委状態分布（収束ベクトル）ｔを見出すことにより利得ｇａｉｎ（ｕ，ｖ）を計算する段階と
を含むことを特徴とする請求項１０に記載の方法。
【請求項１５】
Ｔの定常状態分布（収束ベクトル）ｔを見出すことによりｇａｉｎ（ｕ，ｖ）を計算する前記段階が、Ｉが単位マトリックスであり、また、
【数１１】
0003659181.tif 000032
である場合に、一次式（Ｉ−Ｔ）ｔ＝０を解く段階を含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
各オブジェクトｏ∈Ｏvが既知のサイズｓｉｚｅ（ｏ）を持ち、有効な予備取り出し帯域幅Ｐuと、サーバーがオブジェクトをメモリ内に予備取り出しすることができる予備取り出し持続時間δｔとを持つ方法であって、
該方法が、
エンドユーザー、またはシード・ウェブ・ページに深く関連する一組のオブジェクトＯsを識別する段階をさらに含み、該段階が、各オブジェクトのコストをｃｏｓｔ（ｏ）＝ｓｉｚｅ（ｏ）として定義する段階と、
【数１２】
0003659181.tif 000033
であるように、また、
【数１３】
0003659181.tif 000034
が最大となるように、ＯvのサブセットＯsを識別する段階と
を含むことを特徴とする請求項１５に記載の方法。
【請求項１７】
Ｏsからオブジェクトをメモリ内に予備取り出しする、またはリフレッシュする段階をさらに含むことを特徴とする請求項１６に記載の方法。
【請求項１８】
各オブジェクトｏ∈Ｏvが、既知の期限切れ時間ｅｘｐｉｒｅ（ｏ）を持ち、
前記方法が、自らの最も早い概観時間の前に期限切れになるオブジェクトを除去することにより一組のオブジェクトＯsを正確にする段階をさらに含み、該段階が、
最短経路アルゴリズムを使用して、前記辺の重みを考慮に入れながら、節点ｖcからすべての節点ｖi∈Ｖまでの最短経路ｓｈｏｒｔｅｓｔ＿ｐａｔｈ（ｖc，ｖi）を見出す段階と、
ページｐにアクセスすることができる、最も早い時間の測定値を、ｅａｒｌｉｅｓｔ（ｕ，ｐ）＝ｓｈｏｒｔｅｓｔ＿ｐａｔｈ（ｖc，ｖp）として計算する段階と、
オブジェクトｏが必要とされる最も早い時間の測定値を、ｅａｒｌｉｅｓｔ（ｕ，ｏ）＝ｍｉｎ｛ｅａｒｌｉｅｓｔ（ｕ，ｐ）｜ｐ∈ｐａｇｅｓ（ｏ）｝として計算する段階と、
前記一組のオブジェクトＯsを識別する前に、ｅｘｐｉｒｅ（ｏ）＜ｅａｒｌｉｅｓｔ（ｕ，ｏ）であるオブジェクトを、Ｏvから除去する段階と
を含むことを特徴とする請求項１６に記載の方法。
【請求項１９】
各オブジェクトｏ∈Ｏvが既知のサイズｓｉｚｅ（ｏ）を持ち、有効な予備取り出し帯域幅Ｐuと、サーバーがオブジェクトをメモリ内に予備取り出しすることができる予備取り出し持続時間δｔとを持ち、および、一組のユーザーＵ、またはシード・ウェブ・ページが与えられている方法であって、
該方法が、前記一組のユーザー、またはシード・ウェブ・ページに深く関連する一組のオブジェクトＯsを識別する段階をさらに含み、該段階が、
オブジェクトの利得が、前記オブジェクトと前記一組のエンドユーザー、またはシード・ウェブ・ページとの間の関連を表す場合に、各オブジェクトに対するオブジェクト利得ｇａｉｎ（ｏ）を、
【数１４】
0003659181.tif 000035
として計算する段階と、
各オブジェクトのコストを、ｃｏｓｔ（ｏ）＝ｓｉｚｅ（ｏ）として定義する段階と、
【数１５】
0003659181.tif 000036
であるように、また、
【数１６】
0003659181.tif 000037
が最大となるように、ＯvのサブセットＯsを識別する段階と
を含むことを特徴とする請求項１５に記載の方法。
【請求項２０】
複数のウェブ・ページを有する複数のウェブサイトを含むコンテンツ配信ネットワークにおいて、一組のウェブ・ページＶと、これらのウェブ・ページの間の一組のリンクＥとを持つウェブ空間において、シード・ウェブ・ページｖa，ｖb、および他のウェブ・ページｖi∈Ｖとの間の関連を推定し、ウェブ・ページをウェブ・ページメモリに予備取り出しするためのシステムであって、
Ｖ内の前記シード・ウェブ・ページｖa，ｖb、および他のウェブ・ページｖiの位置を記憶するためのメモリと、
前記ウェブ空間を、無向近傍グラフＧN（ＶN，ＥN）としてモデル化する手段と、
ＶN内にｖiおよびｖjの両方が存在する場合に、各ｖi∈ＶNに対して、Ｖ内に新しいｖi'を作り出し、各ｅk＝＜ｖi'，ｖj'＞∈ＥNに対して、Ｅ内に二つの有向辺ｅ'2×k＝＜ｖi'，ｖj'＞およびｅ'2×k+1＝＜ｖj'，ｖi'＞を作り出し、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を生成して構成した有向ランダム・ウォーク・グラフを格納する手段と、
Ｔ［ｊ，ｉ］が、節点ｖjから節点ｖiへの移動の可能性を示すＥ内の各有向辺に対して遷移値を表す場合に、前記ペナルティ値ｐｅｎａｌｔｙ（ｖi'）に基づいて、｜Ｖ｜×｜Ｖ｜遷移マトリックスＴを生成して格納する手段と、
各ｖi∈Ｖに対して、ｔ［ｉ］が、シード・ウェブ・ページとｖiとの間の関連を示す場合に、前記遷移マトリックスＴの定常状態分布（収束ベクトル）ｔを生成して格納する手段と、
ウェブ・ページを前記ｔ［ｉ］の降順に取り出して前記ウェブ・ページメモリに格納する手段と、
を備え、
前記有向ランダム・ウォーク・グラフは、ＧN内における、ｖi'とｖaに対応する節点ｖa'との間の最短距離として、ｓｄｉｓｔ（ｖi'，ｖa'）を生成し、ＧN内における、ｖi'とｖbに対応する節点ｖb'との間の最短距離として、ｓｄｉｓｔ（ｖi'，ｖb'）を生成し、ｓｄｉｓｔ（ｖi'，ｖa'）＋ｓｄｉｓｔ（ｖi'，ｖb'）によりペナルティ値ｐｅｎａｌｔｙ（ｖi'）を計算することにより、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を生成することを特徴とするシステム。
【請求項２１】
｜Ｖ｜×｜Ｖ｜遷移マトリックスＴを生成して格納する手段は、
すべての節点ｖi'∈Ｖおよび、すべての
【数１７】
0003659181.tif 000038
に対して、Ｔ［ｊ，ｉ］＝０．０をリセットし、
すべての節点ｖi'∈Ｖに対して、下記一組の一次式、
【数１８】
0003659181.tif 000039
を解くことにより前記｜Ｖ｜×｜Ｖ｜遷移マトリックスＴを構成することを特徴とする請求項２０に記載のシステム。
【請求項２２】
前記Ｔの定常状態分布（収束ベクトル）ｔを生成する手段は、
Ｉが単位マトリックスであり、また、
【数１９】
0003659181.tif 000040
である場合に、一次式（Ｉ−Ｔ）ｔ＝０を解くことによって、Ｔの定常状態分布（収束ベクトル）ｔを生成することを特徴とする請求項２１に記載のシステム。
【請求項２３】
前記有向ランダム・ウォーク・グラフを構成する手段は、ランダム・ウォーク・グラフを構成するためのＧN（ＶN，ＥN）の関連近傍を、
【数２０】
0003659181.tif 000041
という一組の節点として定義し、該節点には、
【数２１】
0003659181.tif 000042
となるようなｄの辺トラバーサル内のｖaまたはｖbから到達可能であることを特徴とする請求項２０に記載のシステム。
【請求項２４】
前記ウェブ空間が、Ｖ内に一組のシード・ウェブ・ページ｜Ｓ｜≧２をさらに含み、前記有向ランダム・ウォーク・グラフを構成する手段は、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を、
【数２２】
0003659181.tif 000043
としてすることを特徴とする請求項２０に記載のシステム。
【請求項２５】
前記ウェブ空間が、Ｖ内に一組のシード・ウェブ・ページ｜Ｓ｜≧２をさらに含み、前記有向ランダム・ウォーク・グラフを構成する手段は、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を、
penalty(vi') = length (minimum_steiner_tree (S ∪ [vi']))
として計算するように、さらにプログラムされていることを特徴とする請求項２０に記載のシステム。
【請求項２６】
前記有向ランダム・ウォーク・グラフを構成する手段は、ランダム・ウォーク・グラフを構成するためのＧN（ＶN，ＥN）の関連近傍を、
【数２３】
0003659181.tif 000044
という一組の節点として定義し、該節点には、
【数２４】
0003659181.tif 000045
となるようなｄの辺トラバーサル内のＳ内の節点の中のいずれかから到達可能であることを特徴とする請求項２５に記載のシステム。
【請求項２７】
各ウェブ・ページｖi∈Ｖが、特定のトピックｒｅｌｅｖａｎｃｅ（ｖ，ｔｏｐｉｃ）に対する既知の関連値を持ち、
前記有向ランダム・ウォーク・グラフを構成する手段は、ｒｅｌｅｖａｎｃｅ（ｖ，ｔｏｐｉｃ）でｐｅｎａｌｔｙ（ｖi'）を除算することにより、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を調整することを特徴とする請求項２０に記載のシステム。
【請求項２８】
複数のウェブ・ページを有する複数のウェブサイトを含むコンテンツ配信ネットワークにおいて、一組のウェブ・ページＶと、ウェブ・ページＥの間の一組のリンクとを持つウェブ空間において、Ｏvが主ＨＴＭＬファイルを含む一組の媒体オブジェクトであり、ａvがページ著者である場合に、各ウェブ・ページｖi∈Ｖがペア（Ｏv，ａv）を含む場合に、前記媒体オブジェクトと、エンドユーザーｕの現在位置に対応するシード・ウェブ・ページｖcとの間の関連を推定し、ウェブ・ページをウェブ・ページメモリに予備取り出しするためのシステムであって、
各オブジェクトｏ∈Ｏvに対して、前記エンドユーザーｕの既知のエンドユーザーの優先順位ｕｐｒｅｆ（ｕ）、ページ著者ａvに対するページ著者の優先順位ａｐｒｅｆ（ａv）、および前記シード・ウェブ・ページｖcの位置を記憶するためのメモリと、
前記ウェブ空間を有向グラフＧ（Ｖ，Ｅ）としてモデル化する手段と、
Ｏvのコンテンツに対し、ｕｐｒｅｆ（ｕ）およびａｐｒｅｆ（ａv）により定義される優先順位規則を適用することにより、各ウェブ・ページｖiに対するエンドユーザーｕのページ優先順位重みｐｒｅｆ（ｕ，ｖ）を生成する手段と、
Ｏvのコンテンツに対し、ｕｐｒｅｆ（ｕ）およびａｐｒｅｆ（ａv）により定義される優先順位規則を適用することにより、各オブジェクトｏ∈Ｏvに対するオブジェクト優先順位重みｐｒｅｆ（ｕ，ｏ，ｖ）を生成する手段と、
一組の節点Ｖwと一組の辺Ｅwとを持つランダム・ウォーク・グラフＧwを生成するように、ランダム・ウォーク・グラフの定常状態分布（収束ベクトル）を見出すことにより、ページ利得ｇａｉｎ（ｕ，ｖ）を生成する手段と、
オブジェクト利得が、前記オブジェクトと前記一組のエンドユーザー、または前記シード・ウェブ・ページとの間の関連を表す場合に、
【数２５】
0003659181.tif 000046
として各オブジェクトに対するオブジェクト利得ｇａｉｎ（ｕ，ｏ）を生成する手段と、
を備えることを特徴とするシステム。
【請求項２９】
前記ランダム・ウォーク・グラフＧwは、Ｖ内の各ウェブ・ページに対してＶw内に節点ｖiを作り出し、Ｅ内の各辺ｅj＝＜ｖa，ｖb＞に対して、Ｅw内に二つの辺ｅj'＝＜ｖa'，ｖb'＞、およびｅj"＝＜ｖb'，ｖa'＞を作り出し、Ｅ内の各辺ｅj＝＜ｖa，ｖb＞に対して、辺の重みｗ（ｅ）＝ｓ（ｕ，ｖj）を割り当てることにより生成されることを特徴とする請求項２８に記載のシステム。
【請求項３０】
ｓ（ｕ，ｖj）が、各ウェブ・ページｖj∈Ｖに対する既知の密着性の数値であることを特徴とする請求項２９に記載のシステム。
【請求項３１】
ｓ（ｕ，ｖj）に、Ｅ内の各辺ｅj＝＜ｖa，ｖb＞に対する単位値が割り当てられることを特徴とする請求項２９に記載のシステム。
【請求項３２】
ｓ（ｕ，ｖj）に、領域境界を横切るＥ内の各辺ｅj＝＜ｖa，ｖb＞に対する単位値より大きい数値が割り当てられることを特徴とする請求項２９に記載のシステム。
【請求項３３】
前記ページ利得ｇａｉｎ（ｕ，ｖ）を生成する手段は、
最短経路アルゴリズムを使用して、前記辺の重みを考慮に入れながら、節点ｖcからすべての節点ｖi∈Ｖまでの最短距離ｓｈｏｒｔｅｓｔ（ｖc，ｖi）を見出すことにより、各節点ｖ∈ＶWに対して、ペナルティｐｅｎａｌｔｙ（ｕ，ｖ）＝ｓｈｏｒｔｅｓｔ（ｖc，ｖi）／（ｐｒｅｆ（ｕ，ｖ）＋１）を計算し、
【数２６】
0003659181.tif 000047
を解くことにより単位確率ｕｎｉｔ（ｕ，ｖ）を計算し、
各辺ｅ＝∈＜ｖi，ｖj＞∈ＶWに対して、ｐｒｏｂ（ｕ）（ｖj｜ｖi）＝ｕｎｉｔ（ｕ，ｖj）／ｐｅｎａｌｔｙ（ｕ，ｖi）を計算し、
Ｔが遷移値ｐｒｏｂ（ｕ）（ｖj｜ｖi）のマトリックスであり、
【数２７】
0003659181.tif 000048
である場合に、Ｔの定常委状態分布（収束ベクトル）を見出すことによって利得ｇａｉｎ（ｕ，ｖ）を計算することにより、前記ランダム・ウォーク・グラフの定常状態分布（収束ベクトル）を見出すことによって、ページ利得ｇａｉｎ（ｕ，ｖ）を計算する
ことを特徴とする請求項２９に記載のシステム。
【請求項３４】
前記ページ利得ｇａｉｎ（ｕ，ｖ）を生成する手段は、
Ｉが単位マトリックスであり、また、
【数２８】
0003659181.tif 000049
である場合に、一次式（Ｉ−Ｔ）ｔ＝０を解くことにより、Ｔの定常委状態分布（収束ベクトル）ｔを見出すことにより、ｇａｉｎ（ｕ，ｖ）を計算する
ことを特徴とする請求項３３に記載のシステム。
【請求項３５】
前記メモリが、各オブジェクトｏ∈Ｏvの既知のサイズｓｉｚｅ（ｏ）を記憶するためのものであり、
有効な予備取り出し帯域幅Ｐu、およびオブジェクトをメモリ内に予備取り出しすることができる予備取り出し持続時間δｔを持ち、また、各オブジェクトのコストをｃｏｓｔ（ｏ）＝ｓｉｚｅ（ｏ）として定義することにより、
【数２９】
0003659181.tif 000050
であるように、また、
【数３０】
0003659181.tif 000051
が最大となるように、ＯvのサブセットＯsを識別することにより、前記エンドユーザー、またはシード・ウェブ・ページに深く関連する一組のオブジェクトＯsを識別する手段をさらに有することを特徴とする請求項３４に記載のシステム。
【請求項３６】
前記Ｏsからオブジェクトをメモリ内に予備取り出し、またはリフレッシュすることを特徴とする請求項３５に記載のシステム。
【請求項３７】
前記メモリが、各オブジェクトｏ∈Ｏvに対する既知の期限切れ時間ｅｘｐｉｒｅ（ｏ）を記憶するためのものであり、
前記一組のオブジェクトＯsを識別する手段は、最短経路アルゴリズムを使用して、前記辺の重みを考慮に入れながら、節点ｖcからすべての節点ｖi∈Ｖまでの最短距離ｓｈｏｒｔｅｓｔ＿ｐａｔｈ（ｖc，ｖi）を見出し、ページｐにアクセスすることができる最も早い時間の測定値を、ｅａｒｌｉｅｓｔ（ｕ，ｐ）＝ｓｈｏｒｔｅｓｔ＿ｐａｔｈ（ｖc，ｖp）として計算し、オブジェクトｏが必要とされる最も早い時間の測定値を、ｅａｒｌｉｅｓｔ（ｕ，ｏ）＝ｍｉｎ｛ｅａｒｌｉｅｓｔ（ｕ，ｐ）｜ｐ∈ｐａｇｅｓ（ｏ）｝として計算し、一組のオブジェクトＯsを識別する前に、ｅｘｐｉｒｅ（ｏ）＜ｅａｒｌｉｅｓｔ（ｕ，ｏ）であるオブジェクトをＯvから除去し、自らの最も早い概観時間の前に期限切れになるオブジェクトを除去することによって、一組のオブジェクトＯsを正確にすることを特徴とする請求項３５に記載のシステム。
【請求項３８】
前記メモリが、各オブジェクトｏ∈Ｏvの既知のサイズｓｉｚｅ（ｏ）を記憶するためのものであり、
前記一組のオブジェクトＯsを識別する手段は、有効な予備取り出し帯域幅Ｐuと、サーバーがオブジェクトをメモリ内に予備取り出しすることができる予備取り出し持続時間δｔとを持ち、オブジェクトの利得が、オブジェクトと一組のエンドユーザー、またはシード・ウェブ・ページとの間の関連を表す場合に、各オブジェクトに対するオブジェクト利得ｇａｉｎ（ｏ）を、
【数３１】
0003659181.tif 000052
として計算し、各オブジェクトのコストをｃｏｓｔ（ｏ）＝ｓｉｚｅ（ｏ）として定義することにより、
【数３２】
0003659181.tif 000053
であるように、また、
【数３３】
0003659181.tif 000054
が最大となるように、ＯvのサブセットＯsを識別することにより、一組のユーザーＵ、またはシード・ウェブ・ページと深い関連を持つ一組のオブジェクトＯsを識別することを特徴とする請求項３４に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、概して、コンテンツ配信ネットワークに関するもので、好ましい実施形態の場合には、ユーザー指向のウェブ・ページのリフレッシュおよび予備取り出し（pre-fetch）スケジューリングを最適化する目的で、ウェブ・ページの関連および使用（データ探査）を探査するためにランダム・ウォーク（random walks）を使用するシステムおよび方法に関する。
【０００２】
【従来の技術】
ウェブの性能は、コンテンツ・プロバイダの間の差別化の最も重要なポイントである。主要なウェブサイトが混乱状態にあり、また低速状態にあることが、大量のウェブ・トラフィックを克服しようとしている各社が当面している困難な問題を証明している。インターネットのバックボーン技術が発達するにつれて、ネットワークの帯域幅を改善し、ウェブ・コンテンツの検索時間を短縮するために、サービス管理の品質のような多くの革新が使用されてきた。しかし、インフラストラクチャに関するこれらの改善は、インターネット内の任意のある点で発生するトラフィックの問題を解決することはできない。例えば、図１の場合には、日本のネットワーク１２内のエンドユーザー１０が、米国のネットワーク１６内のコンテンツ・プロバイダのオリジナル・ウェブサイト１４内の、あるページにアクセスしようとしている。この要求は、コンテンツ・プロバイダのオリジナル・ウェブサイト１４に届く前に、いくつかのインターネット・サービス・プロバイダ（ＩＳＰ）のゲートウェイ１８、２０および２２を通過する。ゲートウェイのところが狭くなっていることと、ユーザーとコンテンツ・プロバイダのオリジナル・ウェブサイト１４との間のインターネット経路に沿った他の遅延要因があるので、ゲートウェイのエンドユーザー側で、プロキシサーバーを利用するコンテンツ予備取出し／リフレッシュ方法を使用すれば、応答時間を短縮することができる。
【０００３】
図２は、複数の非特定ウェブサイト２８および３０に接続しているキャッシュ・システム２６を含む、通常のウェブ・コンテンツ配信およびキャッシュ・スキーム２４である。キャッシュ・システム２６は、プロキシサーバーまたはキャッシュ・サーバー３２およびキャッシュ３４からなる。キャッシュ３４としては、プロキシ・キャッシュ、エッジ・キャッシュ、フロントエンド・キャッシュ、逆キャッシュ等を使用することができることを理解されたい。別の方法としては、図２のキャッシュ・システム２６の代わりに、コンテンツ配信サービス・プロバイダとすでに加入者契約を結んでいるウェブサイトに接続しているコンテンツ配信サービス・プロバイダおよびミラー・サイトを利用することができる。これら加入者ウェブサイトは、ミラー化するためのコンテンツ配信サービス・プロバイダにコンテンツを配信するが、コンテンツが変更された場合、必ずしもコンテンツ配信サービス・プロバイダに通知しない。
【０００４】
図２の場合、コンテンツがウェブサイトからキャッシュ３４に配信されると、メタ記述またはメタデータと呼ばれるヘッダが、コンテンツと一緒に配信される。メタデータはコンテンツのサブセットであってもよいし、またはコンテンツのある種の特性を表示することもできる。例えば、メタデータは、最後に修正した日付、ある時期にコンテンツが期限切れになる推定値、コンテンツが直ちに期限切れになるか、またはキャッシュすべきでないという表示を含むことができる。コンテンツおよびメタデータが配信された後で、メタデータが、キャッシュ３４内にコンテンツを記憶するように表示している場合には、コンテンツが、キャッシュ３４に記憶される。
【０００５】
ユーザー３６（ユーザー１）が、ウェブサイト２８（ウェブサイト１）からあるページ（例えば、index.html）へのアクセスを要求した場合には、ユーザー１のウェブ・ブラウザは、最初に、ウェブサイト１のドメイン名に対応するインターネット・プロトコル（ＩＰ）アドレスを見出すために、要求をドメイン名サーバー（ＤＮＳ）に送る。図２の例の場合のように、キャッシュ・システム２６を利用した場合には、ウェブ・ブラウザをウェブサイト１にではなく、プロキシサーバー３２に送ることができる。その後で、プロキシサーバー３２は、要求したコンテンツがキャッシュ３４内に存在するかどうかを判断する。
【０００６】
しかし、要求したコンテンツがキャッシュ３４内で見出すことができたとしても、キャッシュ３４内のコンテンツが最新のものであるかどうかを判断しなければならない。この問題は、データベース同期として説明することができる。すなわち、キャッシュ３４およびウェブサイト１としては、同じコンテンツを持つことが望ましい。しかし、すでに説明したように、加入者ウェブサイトは、そのコンテンツが変更されたとき、それをプロキシサーバー３２に知らせないかもしれない。それ故、プロキシサーバー３２は、コンテンツが最新のものであることを容易に判断できるように、キャッシュ３４内に記憶している、要求されたコンテンツに関連するメタデータをチェックする。
【０００７】
キャッシュ３４内で要求されたコンテンツが見出され、メタデータが期限切れの推定日時が、まだ来ていないことを示している場合には、ある種のキャッシュ・システムは、単に、コンテンツをユーザー１に直接配信する。しかし、もっと高度なキャッシュ・システムの場合には、必要なコンテンツが、最後に更新された日時に関する情報を求めて、ウェブサイト１に要求を送ることができる。キャッシュ３４への最後のリフレッシュ以降にコンテンツが更新されている場合には、キャッシュ３４内に現在入っているコンテンツは最新のものではなくなり、最新のコンテンツが、ユーザー１に配信される前に、ウェブサイト１からキャッシュ３４に配信される。しかし、コンテンツが変更されたかどうかを判断するためにウェブサイトをチェックするこのプロセスは、より広い帯域幅またはシステム資源利用を必要とすることも理解されたい。
【０００８】
同様に、キャッシュ３４内で要求されたコンテンツを見出したが、そのコンテンツが直ちに時間切れになるものである場合には、ある種のキャッシュ・システムは、単に、ウェブサイト１からコンテンツを取り出し（fetch）、それをユーザー１に配信する。しかし、ユーザーが、データが最新のものであるかどうかの確認を要求した場合には、ある種のキャッシュ・システムは、必要なコンテンツが最後に更新された日時に関する情報を求めて、ウェブサイト１に要求を送ることができる。キャッシュ３４に対する最後のリフレッシュの前にコンテンツが更新された場合には、コンテンツは依然として最新のものであり、キャッシュ・システムは、そのコンテンツが「直ちに期限切れになる」状態であっても、それをユーザー１に配信する。
【０００９】
要求されたコンテンツがキャッシュ３４内に入っていない場合には、プロキシサーバー３２は、必要なウェブ・ページ（例えば、index.html）のテキストを取り出すために、ウェブサイト１に要求を送る。ユーザー１のウェブ・ブラウザが、index.htmlを受信した後で、ブラウザはhtmlページを分析し、画像またはアイコンのような、任意のエンベッディド・オブジェクトを取り出すために、ウェブサイト１に追加要求を発行することができる。しかし、キャッシュ・システム２６を利用している場合には、プロキシサーバー３２は、最初に、エンベッディド・オブジェクトがキャッシュ３４内にキャッシュされているかどうかを判断する。すべてのトラフィック（すなわち、データの流れ）は、プロキシサーバー３２内のログファイル３８内に記録される。ログファイル３８は、要求の発行が行われる位置のＩＰアドレス、取り出したオブジェクトのＵＲＬ、各行動のタイム・スタンプ等を含むことができる。プロキシサーバー３２は、通常、多くのエンドユーザーにより共有され、そのため、同じ様な利害関係を持つユーザーが、キャッシュ３４内のコンテンツにアクセスできることに留意されたい。すなわち、ユーザー１があるページにアクセスし、そのページがキャッシュ３４に記憶されている場合であって、他のユーザー４０（ユーザー２）が同じページを要求した場合には、プロキシサーバー３２は、単に、キャッシュ３４内のコンテンツをユーザー２に供給することができる。
【００１０】
ある種のキャッシュ・システムの場合には、コンテンツに対するエンドユーザーの要求がない場合でも、リフレッシュを実行することができる。ユーザーからの要求を受信しない場合でも、キャッシュは、要求を、ウェブサイトのコンテンツが、最後に更新された日時を判断するために、キャッシュ内にコンテンツを配信するウェブサイトに要求を送ることができる。コンテンツが変更された場合には、そのコンテンツは、ウェブサイトからキャッシュに、リフレッシュされて送り返される。それ故、エンドユーザーからコンテンツに対する要求を受信した場合には、キャッシュ内のコンテンツが最新のものであり、直ちにエンドユーザーに直接送信される可能性が高い。
【００１１】
ネットワークの帯域幅資源およびシステム資源は、インターネットに接続しているエンドユーザーおよびプロキシサーバーにとって重要なものである。エンドユーザーおよびプロキシサーバーは、帯域幅および接続資源を入手するために、相互に「競合している」と見なすことができる。しかし、エンドユーザーおよびプロキシサーバーの目標は同じである。すなわち、最も速い応答時間でユーザーに供給することである。
【００１２】
図３は、通常のプロキシサーバー４２にとって有効な接続を示す。個々の要求に対する最も速い応答時間は、要求されたコンテンツが、プロキシサーバー・キャッシュ内に位置していて、最新のものである場合に達成することができる。そのため、プロキシサーバー４２は、インターネットを通してウェブサイトからコンテンツを取り出す必要はない。この状況は、キャッシュ「ヒット」と呼ばれる。キャッシュ・ヒット率が非常に高い場合には、システム全体を通して、最も速い応答時間が達成される。それ故、予め取り出しておき４４、リフレッシュしておき、確認しておけば、最新のコンテンツが増え、キャッシュ・ヒット率がもっと高くなり、エンドユーザーに対する応答時間がもっと速くなることを明確に理解することができるだろう。しかし、折り合いをつける必要がある。非常に高いキャッシュ・ヒット率を達成するためには、プロキシサーバー４２は、コンテンツのリフレッシュ、予備取り出し、取出し、または予備確認４４をキャッシュに対して行うために、ネットワークの大きなパーセンテージの帯域幅を使用しなければならない。しかし、大量のフレッシュにもかかわらず、エンドユーザーが、キャッシュ内にまだリフレッシュしていない、または単にキャッシュに位置していないコンテンツを要求する事態が起こる場合がある。そのような場合には、プロキシサーバー４２は、ウェブサイトからそのコンテンツを要求するために、要求取出し４６を発行しなければならない。しかし、他のコンテンツをリフレッシュするために、帯域幅の過度の帯域が現在利用されている場合には、ウェブサイトからの要求コンテンツを取り出すために、キャッシュにとって有効な帯域幅が不十分である場合があり、コンテンツ取り出しの応答時間が、実際にはかなり長くなる場合がある。それ故、キャッシュ・リフレッシュおよび予備取り出しは、ウェブサイトのコンテンツ取出しと競合し、ウェブサイトのコンテンツ取出しに悪影響を及ぼす恐れがあることを理解されたい。
【００１３】
もちろん、任意の瞬間に、利用していない帯域幅がある場合には、要求しているエンドユーザーが使えるように、最も優先権の高いコンテンツをキャッシュ内に予め取り出しておくことは合理的な方法である。例えば、エンドユーザーがコンテンツを要求したがキャッシュ・ヒットがない場合に、ウェブサイトからコンテンツを取り出すために、帯域幅の２０％を利用していると仮定する。上記取出しのために、帯域幅の２０％が利用されている場合には、帯域幅の８０％は利用されていない。この利用されていない帯域幅は、エンドユーザーが他のコンテンツを要求した場合にエンドユーザーにとって有用となり得るように、キャッシュ内にそのコンテンツを予め取り込むために利用することができる。しかし、ネットワークの帯域幅には制限があるために、キャッシュ内に記憶しているコンテンツの一部しかリフレッシュまたは予備取り出しできないので、リフレッシュまたは予備取り出しするコンテンツを選択するための方法が必要になる。
【００１４】
状況次第で、どのコンテンツを予備取り出しするのかを選択するのは簡単な仕事ではない。例えば、最も簡単な場合には、一人のエンド・ユーザーが、現在ウェブサイト内の特定のウェブ・ページにアクセスしていると仮定しよう。要するに、このエンドユーザーは、他のウェブ・ページに、リンクに沿って情報を順次表示する（navigate）ことができる。次にリンクに沿って情報を順次表示する可能性が最も高い、これらウェブ・ページを予備取り出しすることによりエンドユーザーの応答時間を改善することができる。エンドユーザーが、他のウェブ・ページに、リンクに沿って情報を順次表示するために現在のウェブ・ページ上のハイパーリンクを使用する可能性が高いので、エンドユーザーの現在の位置で見出されるハイパーリンク（リンク構造体）によりウェブ・ページを予備取り出しするのは意味のあることである。しかし、二人またはそれ以上のエンドユーザーが、一つまたはそれ以上のウェブサイトをリンクに沿って情報を順次表示している場合であって、限られたウェブ・ページだけを予備取り出しすることができる場合には、どのウェブ・ページを予備取り出しするかの決定はさらに難しくなる。
【００１５】
予備取り出しするウェブ・ページの優先順位を決定する一つの方法は、更新頻度および問合わせ頻度を使用する方法である。しかし、ウェブサイト上のホームページが任意の他のウェブ・ページよりももっと頻繁に問い合わせをされるとしても、そのウェブサイトを現在リンクに沿って情報を順次表示しているエンドユーザーは、しばらくの間は、ホームページに戻らないかもしれない。そのため、問合わせ頻度は、予備取り出しするウェブ・ページを決定する際には、最善の判断基準ではない場合がある。さらに、エンドユーザーは、通常、ホームページからウェブサイトに入るので、ホームページは、すでにキャッシュ内で使用できるようになっている。さらに、ウェブ・ページの更新頻度は、ウェブサイトをリンクに沿って情報を順次表示しているエンドユーザーの現在の位置が分かっている場合、必ずしも、次にアクセスする可能性を示していない。
【００１６】
次にアクセスされる確率が高いウェブ・ページを識別しようとする試みは、ウェブ・ページ間の一つの「関連」として見ることもできる。例えば、二つのウェブ・ページは、両方とも、株式市場に関する情報を含んでいるので、これらのウェブ・ページは、相互に関連づけることができる。通常、エンドユーザーの現在位置が分かっている場合には、次にアクセスするウェブ・ページが、現在のウェブ・ページに幾分関連している可能性の方が関連していない可能性より高い。ウェブ・ページ間の関連についての何かが分かれば、予備取り出し優先順位を決定する際にある程度の見通しを得ることができる。
【００１７】
ある人がウェブ文書を作成する場合、主要な情報は、直接ウェブ・ページ内に掲載し、一方、他のウェブ・ページ上の関連情報は、アンカーでリンクされる。従来の情報検索システムの場合には、所与の文書の間の関連は、ウェブ・ページ内に直接掲載されている主要な情報のコンテンツを表すキーワード・ベクトルを比較することにより決定される。これらの文書の関連は、ユーザーに、そのユーザーが現在見ているものに関連するページを供給するためのものである。しかし、このようなシステムは、リンク構造体を考慮に入れない。
【００１８】
【発明が解決しようとする課題】
それ故、本発明の実施形態の利点は、リンク構造体およびウェブ・ページのコンテンツの両方を考慮に入れるウェブ・ページの関連および使用を探査するためのものであって、ユーザー指向のウェブ・ページのリフレッシュおよび予備取り出しスケジューリングを最適化するためにランダム・ウォークを使用するシステムおよび方法を提供することである。
【００１９】
本発明の実施形態のもう一つの利点は、反復をベースとする方法を使用するのではなく、式を解くことをベースとすることから得られるリンク分析を含むユーザー指向のウェブ・ページのリフレッシュ、および予備取り出しスケジューリングを最適化する目的で、ウェブ・ページの関連および使用を探査するために、ランダム・ウォークを使用するシステムおよび方法を提供することである。
【００２０】
本発明のさらにもう一つの利点は、推理に焦点を合わせるために、一組のウェブ・ページを指定することができるユーザー指向のウェブ・ページのリフレッシュおよび予備取り出しスケジューリングを最適化する目的で、ウェブ・ページの関連および使用を探査するためにランダム・ウォークを使用するシステムおよび方法を提供することである。
【００２１】
【課題を解決するための手段】
複数のウェブ・ページを有する複数のウェブサイトを含むコンテンツ配信ネットワークにおいて、一組のウェブ・ページＶと、無向近傍グラフＧN（ＶN、ＥN）として表されるウェブ・ページの間の一組のリンクＥとを持つウェブ空間が、さらに、Ｖ内のシード・ウェブ・ページｖa，ｖbを含む場合に、ｖa，ｖb、および他のウェブ・ページｖi∈Ｖの間の関連を推定するための方法であって、該方法が、ＶN内にｖiおよびｖjの両方が存在する場合に、各ｖi∈ＶNに対して、Ｖ内に新しいｖi'を作り出し、各ｅk＝＜ｖi'，ｖj'＞∈ＥNに対して、Ｅ内に二つの有向辺ｅ'2×k＝＜ｖi'，ｖj'＞およびｅ'2×k+1＝＜ｖj'，ｖi'＞を作り出し、すべての節点ｖi'∈Ｖに対するペナルティ値ｐｅｎａｌｔｙ（ｖi'）を生成し、Ｔ［ｊ，ｉ］が、節点ｖiから節点ｖjへの移動の可能性を示すＥ内の各有向辺に対して遷移値を表す場合に、｜Ｖ｜×｜Ｖ｜遷移マトリックスＴを構成することにより、有向ランダム・ウォーク・グラフを構成する段階と、各ｖi∈Ｖに対して、ｔ［ｉ］が、シード・ウェブ・ページとｖiとの間の関連を示す場合に、Ｔの定常状態分布（収束ベクトル）ｔを生成する段階とを有し、前記ペナルティ値ｐｅｎａｌｔｙ（ｖi'）の生成は、ＧN内におけるｖi'とｖaに対応する節点ｖa'との間の最短距離としてｓｄｉｓｔ（ｖi'，ｖa'）を計算する段階と、ＧN内におけるｖi'とｖbに対応する節点ｖb'との間の最短距離としてｓｄｉｓｔ（ｖi'，ｖb'）を計算する段階と、ｐｅｎａｌｔｙ（ｖi'）＝ｓｄｉｓｔ（ｖi'，ｖa'）＋ｓｄｉｓｔ（ｖi'，ｖb'）を計算する段階と、を含む。
上記および他の利点は、媒体オブジェクトおよびシード・ウェブ・ページの間の関連を推定するための方法により達成される。上記方法は、一組のウェブ・ページＶと、有向グラフＧ（Ｖ，Ｅ）としてモデル化されたこれらのウェブ・ページＥの間の一組のリンクを持つウェブ空間の関連で使用される。各ウェブ・ページｖi∈Ｖは、ペア＜Ｏv，ａv＞を含む。この場合、Ｏvは、一組の媒体オブジェクト（主ＨＴＭＬファイルを含む）であり、ａvはページ著者である。各オブジェクトｏ∈Ｏvは、既知の大きさ（ｏ）、エンドユーザーｕに対するエンドユーザー優先順位ｕｐｒｅｆ（ｕ）、およびページの作者ａvに対するページの作者の優先順位ａｐｒｅｆ（ａv）を持つ。ウェブ空間は、さらに、シード・ウェブ・ページｖcのところに現在位置するエンドユーザーｕ、および使用できる予備取り出し帯域幅Ｐを含む。
【００２２】
本発明の方法は、最初に、Ｏvのコンテンツに対し、ｕｐｒｅｆ（ｕ）およびａｐｒｅｆ（ａv）によって定義される優先順位規則を適用することによって、各ウェブ・ページｖiに対するページ優先順位重みｐｒｅｆ（ｕ，ｖ）を計算し、Ｏvのコンテンツに対してｕｐｒｅｆ（ｕ）およびａｐｒｅｆ（ａv）により定義される優先順位規則を適用することによって、各オブジェクトｏ∈Ｏvに対するオブジェクト優先順位重みｐｒｅｆ（ｕ，ｏ，ｖ）を計算する。
【００２３】
次に、ランダム・ウォーク・グラフが生成され、ランダム・ウォーク・グラフの定常状態分布（収束ベクトル）を見出すことにより、ページ利得ｇａｉｎ（ｕ，ｖ）が計算され、その後で、各オブジェクトに対するオブジェクト利得ｇａｉｎ（ｕ，ｏ）が、下記式により計算される。
【数３４】
0003659181.tif 000002
ここで、オブジェクト利得は、オブジェクトとシード・ウェブ・ページとの間の関連を表す。
【００２４】
当業者であれば、添付の図面を参照しながら、本発明の実施形態の下記の詳細な説明を読めば、本発明の実施形態の上記および他の目的、機能および利点を理解することができるだろう。
【００２５】
【発明の実施の形態】
好ましい実施形態の以下の説明においては、本明細書の一部を形成し、本発明を実施することができる例示としての特定の実施形態を示す添付の図面を参照する。他の実施形態を利用することもできるし、本発明の好ましい実施形態の範囲から逸脱することなしに構造を変更することができることを理解されたい。
【００２６】
ハイパーメディアは、情報を記憶し、構造化するための主要機構として開発された。ワールド・ワイド・ウェブは、ハイパーメディア環境の一例である。ウェブが普及するにつれて、ハイパーテキストおよびハイパーメディアが、広い範囲の情報システムで使用されるようになり、分配ソースからの情報にアクセスし、情報をリンクに沿って情報を順次表示しながら、エンドユーザーを案内するための主要な手段となっている。
【００２７】
ハイパーメディアは、コンテンツ情報と構造情報の両方を含む。ある人がウェブ文書を作成した場合、主要な情報は、ウェブ・ページ内に直接掲載され、一方、他のウェブ・ページ上の関連情報は、アンカーを使用してリンクされる。従来の情報検索システムの場合には、所与の組の文書の関連は、ウェブ・ページ内に直接掲載される主要な情報のコンテンツを表すキーワード・ベクトルを比較することにより決定される。これらの文書の関連は、ユーザーに、自分が現在見ているものに関連するページを供給するために使用される。しかし、ウェブ・ページ間の関連の背後に隠れている理由も、暗黙のうちに、ウェブ・ページを接続しているリンク内に埋め込まれ、そのため、リンク構造体を、ウェブ・ページ間の関連を入手するために使用することができる。
【００２８】
ウェブ・ページ間の関連は、データ探索のために有用なものである。データ探索とは、二つまたはそれ以上のウェブ・ページ、またはウェブサイトの間の関連を発見するためのプロセスである。データ探索は、競争者の間の関係を発見できる場合に、競合ビジネスの利点を入手する際に役に立つ。例えば、新しく発足した会社が、コンサルタント、パートナーまたは既知の確立された会社と共通の重役メンバーを持っている場合には、その新しい会社の技術領域および技術力を予測する際に役に立つ。もう一つの例の場合には、ある会社が、財政が危機状態にある会社から重要な部分を購入したり、重要なサービスを受けたりすることを決定することができる場合には、その会社の弱点が露呈する場合がある。
【００２９】
ウェブ・ページ間の関連は、キャッシュ機能等を持つミラー・サーバー、プロキシ・サーバー、エンドユーザー・サーバーによりコンテンツを予備取り出ししたり、リフレッシュする際にも役に立つ。一人のエンドユーザーが、ウェブサイトをリンクに沿って情報を順次表示している場合、次に、どのコンテンツを予備取り出しするかの選択を、現在のウェブ・ページ（ソース・ページまたはシード・ページ）からの限定された数のリンクを通してアクセスすることができるウェブ・ページだけに基づいて行うことができる。しかし、二つまたはそれ以上のシード・ページが関連する場合には、リンクに沿って情報を順次表示しているエンドユーザーが複数である場合のように、上記選択プロセスは、遥かに複雑なものになる。（予備取り出しできるウェブ・ページの数が限定されていると仮定した場合に）ウェブ・ページを効率的に予備取り出しするために、本発明の実施形態は、すべてのリンクに沿って情報を順次表示しているエンドユーザーとの関連が、最も高いウェブ・ページを選択する。好ましい実施形態の場合には、これらウェブ・ページを識別する際に、リンク構造体およびコンテンツの両方を考慮すべきである。
【００３０】
最初に、リンク構造体に基づく関連を調査する。二つまたはそれ以上のシード・ページが関連している場合には、本発明の実施形態は、シード・ページに、中間ウェブ・ページ内のリンクを通して直接または間接にリンクしているウェブ・ページを識別する。これらウェブ・ページが識別されると、現在アクセスされているシード・ページとの関連が最も高いウェブ・ページが決定される。これらのウェブ・ページは、データ探索のためにチェックすることもできるし、エンドユーザーの応答時間を改善するために予備取り出しまたはリフレッシュすることもできる。
【００３１】
シード・ページとの関連が最も高いウェブ・ページを識別するために、ウェブ・ページが何故関連しているかを理解することが役に立つ。一例を挙げて説明する。図４は、二つのウェブ・ページ、Ｗ．Ｓ．リー（Li）４８と、Ｄ．アグレウォール（Agrawal）５０の間の一組のリンクである。これら二つのウェブ・ページは、シード・ページまたはノードであると見なすことができる。各リンクが存在する理由は、リンクを表す矢印に沿って表示してある。例えば、Ｗ．Ｓ．リーは、ノースウェスタン大学（ＮＷＵ）を卒業したので、ＮＷＵのウェブ・ページ５４とＷ．Ｓ．リーのウェブ・ページ４８との間にはリンク５２が存在する。同様に、Ｄ．アグレウォールおよびＰ．シュールマン（Scheuermann）の両方は、ニューヨーク州立大学、ＳＢ（ＳＵＮＹ，ＳＢ）を卒業したので、Ｄ．アグレウォールのウェブ・ページ５０と、ＳＵＮＹ，ＳＢのウェブ・ページ５６との間、およびＰ．シュールマンのウェブ・ページ５８とＳＵＮＹ，ＳＢのウェブ・ページ５６との間にはリンクが存在する。
【００３２】
このリンク構造体に基づいて、Ｗ．Ｓ．リーのウェブ・ページ４８と、Ｄ．アグレウォールのウェブ・ページ５０との間の関連を調査する場合には、Ｗ．Ｓ．リーのウェブ・ページ４８と、Ｄ．アグレウォールのウェブ・ページ５０との間を接続しているリンク構造体は、上記リンク内に埋め込まれている、根底にある関連を発見するための有力な手がかりを提供することができる。以下に、何故Ｗ．Ｓ．リーのウェブ・ページ４８、およびＤ．アグレウォールのウェブ・ページ５０が関連しているのかを説明することができるリンク内の暗黙のうちに含まれているいくつかの理由を列挙する。（正確を期するために、発見という用語は、見出した関連に対して使用すべきであり、理由という用語は、確認された関連に対して使用すべきである。しかし、説明を簡単にするために、本明細書においては、二つの用語は、同じ意味で使用する。）
・  理由１：ウェブ８論文を含むウェブ・ページ６０は、Ｗ．Ｓ．リーのウェブ・ページ４８、およびＤ．アグレウォールのウェブ・ページ５０を接続している距離２の経路内に現われる。それ故、Ｗ．Ｓ．リー、およびＤ．アグレウォールは、同じ作者の論文により関連づけることができる。
・  理由２：Ｙ．ウー（Wu）のウェブ・ページ６２は、各距離４のＮＥＣ研究所（ＣＣＲＬ）（ＣＣＲＬウェブ・ページ６４参照）に関連する二本の経路上に存在する。Ｗ．Ｓ．リーおよびＤ．アグレウォールは、両者とも異なる機会に、Ｙ．ウーを監督したという事実、またはＮＥＣの同じプロジェクトに参加したという理由で関連を持つことができる。
・  理由３：ＷＯＷＳ’９９ウェブ・ページ６６、およびＤＬ’９９ウェブ・ページ６８は、距離３の一本の経路上に現われる。Ｗ．Ｓ．リーおよびＤ．アグレウォールは、両者とも（例えば、プレゼンテーションまたはプログラム委員会のメンバーのような）同じ会議に参加したという事実により関連づけることができる。
・  理由４：Ｐ．シュールマン、Ｄ．アグレウォール、ＮＷＵ、Ｗ．Ｓ．リーおよびＳＵＮＹ，ＳＢのウェブ・ページは、距離４の一本の経路上に現われる。このようなリンク関係は、Ｄ．アグレウォールおよびＷ．リーが、ＳＵＮＹ，ＳＢで共通の知己であること、または同級生関係であることにより関連づけることができる。
【００３３】
上記例は、上記ページの実際のコンテンツと一緒に、下記の二つの直感を、通常、所与の組のページが何故関連を持つのかを識別するために使用することができることを示す。
・  入力ページの間の関連を表すページは、それらに近いものでなければならない。例えば、Ｗ．Ｓ．リーのページと、Ｄ．アグレウォールのページの間のより短い経路上のページは、何故Ｗ．Ｓ．リーのページとＤ．アグレウォールのページが関連しているのかを反映するための、他のものよりは強力なインジケータとなる。
・  構造上の代表は、所与のページに強く接続していなければならない。より多くの経路上に現われるページは、他のものと比較した場合、何故Ｗ．Ｓ．リーのウェブ・ページとＤ．アグレウォールのウェブ・ページが関連しているのかを反映するための、より強力なインジケータでなければならない。
【００３４】
より高い接続性（すなわち、より多くの入力リンクおよび出力リンク）を持つウェブ・ページは、より多くの経路内に含まれる可能性が高いことに留意されたい。従って、そのようなページは、上記基準により、より高いランクを持つ可能性が高い。一方、接続性は高いが、シード・ページから遠いページは、シード・ページにもっと近い、接続性の低いページと比較すると、関連を理解するための重要性は低い場合がある。上記の基準（すなわち、シード・ページに近いこと、および接続性が高いこと）の両方を満足するページは、二つのシード・ページの間の関連を理解するのに良いウェブ・ページである。
【００３５】
二つのウェブ・ページの間の距離は、種々の方法で定義することができる。最も簡単な場合、二つのページの間のリンクの数を距離測定基準として使用することができる。一方、ページ間の物理的および論理的距離を捕捉するために、ユーザーが、興味のある文書のコンテンツを捕捉することができる別の距離測定基準を使用することができる。例えば、ＮＥＣに関するＷ．Ｓ．リーおよびＤ．アグレウォールの間の関連を理解する場合には、推理をＮＥＣに焦点を合わせるようにする必要がある。
【００３６】
上記直感に従って、本発明の実施形態は、それらを接続しているリンク内に、暗黙のうちに埋め込まれている情報を使用して、また、これらの接続文書のコンテンツを使用して、ウェブ文書間の関連を推理するための枠組みを供給する。推理スキームは、ランダム・ウォーク・アルゴリズムに基づいている。
【００３７】
説明を分かりやすくするために、本発明の実施形態の下記の説明の性質は、アルゴリズム的なものであるが、下記のプロセスは、図２に示すように、キャッシュのようなメモリ内のウェブ・コンテンツ文書の記憶装置に関するログに対してアクセスすることができる、一つまたはそれ以上のサーバー内に含まれている、一つまたはそれ以上のプロセッサにより実行することができる。サーバーは、プロキシ・サーバー、キャッシュ・サーバー、ミラー・サーバー、ウェブ・ブラウザ・コンピュータ等を含むことができるが、これに限定されない。キャッシュは、プロキシ・キャッシュ、エッジ・キャッシュ、フロントエンド・キャッシュ、逆キャッシュ等を含むことができるが、これに限定されない。別の方法としては、図２のキャッシュ・システムの代わりに、コンテンツ配信サービス・プロバイダおよびミラー・サイトを使用することができる。
【００３８】
＜文書関連を推理するためのランダム・ウォーク・アルゴリズム＞
図４の例を参照しながら、最初に、本発明の実施形態のランダム・ウォーク・アルゴリズムの背後にある一般的なコンセプトについて説明する。Ｄ．アグレウォールのウェブ・ページ５０およびＷ．Ｓ．リーのウェブ・ページ４８のような二つのスタート点が分かっていて、これら二つのスタート点からのランダムなナビゲーションを仮定した場合、ランダム・ウォーク・アルゴリズムは、あるスタート点（ソース・ページ）から他のスタート点へのランダム・ウォーク中に、各ウェブ・ページのところで消費する可能性が高い時間に従って、優先順位が与えられたウェブ・ページのリストを作成する。
【００３９】
図４に示すように、Ｄ．アグレウォールのウェブ・ページ５０、およびＷ．Ｓ．リーのウェブ・ページ４８（二つのシード・ページ）は、複数の経路を通して接続している。ある経路の場合には、リンクは二つしかなく、一つのウェブ・ページ（ウェブ８論文を含むウェブ・ページ６０）が、上記二つのウェブ・ページを分離している。他の経路の場合には、複数のリンクが存在し、複数のウェブ・ページが、二つのウェブ・ページを分離している。ランダム・ウォーク・アルゴリズムは、最初、もっと少ない数のリンク（例えば、図４のウェブ８論文を含むウェブ・ページ６０）内のＤ．アグレウォールのウェブ・ページ５０、およびＷ．Ｓ．リーのウェブ・ページ４８を接続しているこれらのウェブ・ページに低いペナルティを割り当てる。何故なら、ランダム・ウォーク・プロセスは、これらのウェブ・ページのところで、大部分の時間を消費する可能性が高いからである。反対に、もっと数の多いリンク（例えば、Ｐ．シュールマンのウェブ・ページ５８）内でシード・ページを接続しているこれらウェブ・ページには、もっと重いペナルティが割り当てられる。
【００４０】
次に、他のウェブ・ページに対して一つまたはそれ以上のリンクを持つ各ウェブ・ページの場合であって、他のウェブ・ページに対して割り当てられたペナルティの数値が分かっている場合には、ランダム・ウォーク・プロセスが、他の各ウェブ・ページに遷移する確率が計算される。この計算は、他のウェブ・ページのペナルティの数値が、この遷移の確率に逆に関連するものと見なす。
【００４１】
＜正式モデル、ケース１：二つのシード・ページを含むＳ＞
ランダム・ウォーク・アルゴリズムについてもっと正式に説明する。シード・ウェブ・ページ（または、ｓノード）のある組の関連、Ｓ＝｛ｓ1，．．．，ｓn）を理解してもらう必要があると仮定しよう。推理タスクは、ｓノードの所与の組の間の関連を最もよく引き出す（または、反映する）ページの組Ｒｅｆ（Ｓ）を見出すためのものである。このようなページは、誘導性ウェブ・ページ（またはｉノード）と呼ばれる。説明の都合上、関連を推理するためのシード・ページが二つしかない場合を仮定する。（Ｓが二つ以上のページを含む場合について以下に説明する。）
【００４２】
本発明の実施形態の場合には、ウェブは、有向（directed）グラフＧ（Ｖ，Ｅ）としてモデル化することができる。この場合、ｓノードとして定義されたＳ内の二つのシード・ページは、Ｖ内の節点（vertices）ｖaおよびｖbに対応する。Ｖaまたはｖbから半径ｄ内にｉノード・ページ（または節点）を見出す必要があるものと仮定する。ｄの選択は、用途により異なることに留意されたい。このことは、計算リソース、または、ある数のリンクよりもっと離れているページを考慮することが意味のあることかどうかにより異なる場合がある。進行的な結果が必要な場合には、ｄを１からスタートして大きくして、プロセスがタイムアウトするまで、または受け入れることができるｉノードの位置を見出すまで、各段階毎に結果をより正確なものにすることができる。
【００４３】
文書を関連づけるために、多くの分野でリンクが使用されてきた。リンクは、図５に示すように四つのタイプに分類することができる。例えば、共引用（co-citation）は、二つの文書が共通の文書によりリンクされている場合には、上記二つの文書は、相互に関連していることを示唆している。社会的フィルタリング（social filtering）は、二つの文書が共通の文書にリンクしている場合には、これら二つの文書が相互に関連していることを示唆する。図５のすべてのリンク・タイプは、仮想でないウェブ環境内で見出すことができるが、他の関係と比較して、どのタイプの関係がより重要であるかを判断するのが難しい。従って、ランダム・ウォーク・アルゴリズムは、無向（undirected）ウェブのグラフＧu（Ｖ，Ｅu）だけを使用することにより簡単なものにすることができる。さらに、本発明の他の実施形態の場合には、半径ｄを仮定して、Ｇu（Ｖ，Ｅu）の関連する近接ＧN（ＶN，ＥN）を、
【数３５】
0003659181.tif 000003
という一組の節点として定義することができ、これらの節点には、
【数３６】
0003659181.tif 000004
となるようなｄの辺トラバーサル（edge traversals）内のｖaまたはｖbから到達可能（reachable）である。
【００４４】
ｖaおよびｖbの両方から到達可能である節点ｖi∈ＶNが存在しない場合には、半径ｄが短かすぎて、ｉノードを含むことができない。それ故、一般に適用できるままで、少なくとも一つの上記節点が存在し、従って、近傍（neighborhood）グラフＧNが接続していると仮定する。
【００４５】
ｉノード選択に対する測定基準を入手するために、距離による接続性のスコアを調整するある直感的な測定基準の候補は下記式のようになる。
【数３７】
0003659181.tif 000005
ここで、経路（Ａ、Ｂ、ｖ）は、候補のｉノードｖを通る、シードＡおよびＢの間の（無向の、簡単な）一組の経路であり、長さ（ｐ）は、経路ｐの長さである。しかし、この測定基準は、長さおよびファンアウトの二つの必要な構造上の基準を融合するが、関連を推理する際には使用することができない二つの主な欠点を持つ。
【００４６】
第一の欠点は、その計算が、グラフ内のすべての経路を数えなければならない場合があることである。このことは、（最悪の場合には）グラフの大きさによっては、指数的な非常に長い時間を必要とする場合があることを意味する。経路の最大の長さは、グラフ内の節点の数の増大とともに、一次的に増加するが、経路の数は指数的に増大する。従って、直感とは反対に、点数（ｖ）の計算に対する長い経路の影響は、短い経路の影響よりも遥かに大きくなる可能性が高い。（何故なら、短い経路の数と比較した場合、その数は、指数的に多いからである。）
【００４７】
第二の欠点は、一つのウェブ・グラフのために機能するスコア機能が、他のウェブ・グラフに対してはうまく機能しないことである。何故なら、スコア機能は、ウェブ・グラフに依存するからである。すなわち、上記の測定基準の長さ（ｐ）は、（例えば、商業的ウェブサイトが、施設のウェブサイトより高い端末増設機構を持つことができ、そのためスコア測定基準がケース毎に異なるように）ファンアウトに従って変化する指数を持つことができる。それ故、特別機能は、ｉノード選択には適していない測定基準である。
【００４８】
従って、測定基準を明確に定義する代わりに、本発明の実施形態は、暗黙のうちに上記スコア機能の観察の本質を捕捉する一組のランダム・ウォーク・パラメータを選択する。観察をアルゴリズムに実体化するために、必要なランダム・ウォーク・パラメータを反映するランダム・ウォーク・グラフが定義され、構成される。
【００４９】
＜ランダム・ウォーク・グラフ＞
ランダム・ウォーク・グラフＲ（Ｖ，Ｅ，Ｔ）は、以下の三つのものからなっている。
・  Ｖは、一組の節点である。
・  Ｅは、一組の有向辺である。
・  Ｔは、｜Ｖ｜×｜Ｖ｜マトリックスである。この場合、Ｔ［ｊ，ｉ］は、節点ｖjから節点ｖiへの移動の可能性を示す。
【数３８】
0003659181.tif 000006
であることに留意されたい。
【００５０】
無向近隣のグラフＧN（ＶN，ＥN）、Ｖ内の二つのシード節点ｖaおよびｖb、および半径ｄが分かっている場合には、本発明の実施形態の場合には、有向ランダム・ウォーク・グラフＲ（ｖa，ｖb，ｄ）（Ｖ，Ｅ，Ｔ）を下記のアルゴリズムにより構成することができる。
１．Ｖ＝φ
２．各ｖi∈ＶNに対して新しいｖi’を作り出し、Ｖに挿入する。
３．Ｅ＝φ
４．ｖiおよびｖjの両方が、ＶN内に位置する各ｅk＝＜ｖi，ｖj＞∈ＥNに対して二つの有向辺ｅ’2×k＝＜ｖi’，ｖj’＞およびｅ’2×k+1＝＜ｖj’，ｖi’＞を作り出し、Ｅに挿入する。
５．すべての節点ｖi’∈Ｖに対して、下記のように仮定する。
（ａ）ｓｄｉｓｔ（ｖi’，ｖa’）は、ｖi’とｖaに対応する節点ｖa’との間のＧN内の最短距離である。
（ｂ）ｓｄｉｓｔ（ｖi’，ｖb’）は、ｖi’とｖbに対応する節点ｖb’との間のＧN内の最短距離である。
（ｃ）ｐｅｎａｌｔｙ（ｖi’）＝ｓｄｉｓｔ（ｖi’，ｖa’）＋ｓｄｉｓｔ（ｖi’，ｖb’）
（ｄ）すべての節点ｖi’∈Ｖ、および、すべての
【数３９】
0003659181.tif 000007
に対して、Ｔ［ｊ，ｉ］＝０．０である。
（ｅ）すべての節点ｖi’∈Ｖについて、下記の一組の一次式を解く。
【数４０】
0003659181.tif 000008
ここで、Ｌ（ｖi’）は、各節点ｖi’に対する一組の一次制約条件である。
【００５１】
このアルゴリズムの段階１および段階２においては、近隣の関連節点をランダム・ウォーク・グラフ内に挿入する。これら二つの段階は、半径ｄ内のサブグラフが探査されるまで増分に基づいて実行することができることに留意されたい。段階３および段階４は、ランダム・ウォーク・グラフ内の節点の間の（順方向および逆方向の）二つの遷移を定義するために、近隣グラフ内の無向辺を使用する。これら二つの遷移により、ランダム・ウォークは、グラフの近隣節点の間を前後に自由に移動することができる。
【００５２】
その後で、段階５において、各ノードに対するペナルティが計算される。このペナルティ項は、シード節点からの各節点の距離を反映している。それ故、シードが二つある場合には、ペナルティは、所与の節点と二つのシード節点との間の最短経路距離の合計であると定義される。上記ペナルティは、各節点が、ランダム・ウォーク・プロセスにより、アクセスする可能性を計算するのに使用される。より詳細に説明すると、グラフ内の辺（edge）の遷移の確率は、この項を使用して計算される。
【００５３】
ペナルティが高いということは、シードからの距離が長いということを意味するので、当然、関連スコアは低くなる。従って、ある節点ｖiで、ランダム・ウォーク・プロセスが実行されると、次の節点ｖjに進まなければならないが、この場合、確率は、ｖjのペナルティに反比例する。さらに、ランダム・ウォークは、無限の時間継続して行われるので、ランダム・ウォーク・プロセスが、節点ｖiを離れる確率（すなわち、その近隣の一つに進む確率は）１．０に等しくなければならない。
【００５４】
引続き上記例について説明するが、これは単に説明のためのものに過ぎない。図６は、遷移確率に対するペナルティの影響を示し、また、段階５の効果についてさらに詳細に説明する。説明を分かり易くするために、図６（ａ）は、上記例の一部を示す。この図は、節点Ａ、その四つの近隣節点（節点Ｆ、Ｄ、ＣおよびＪ）と、距離測定基準により計算した関連ペナルティ（それぞれ、４、３、２および４）を示す。図６は図４に対応すること、また、Ｄ．アグレウォールのウェブ・ページ５０が節点Ａに対応し、ウェブ８ウェブ・ページ６０が節点Ｃに対応し、ＤＬ’９９ウェブ・ページ６８が節点Ｄに対応し、ＳＵＮＹ，ＳＢウェブ・ページ５６が節点Ｆに対応し、Ｙ．Ｗｕウェブ・ページ６２が節点Ｊに対応することを理解されたい。
【００５５】
図６（ａ）は、節点ＡからＷ．Ｓ．リーのウェブ・ページ（図６には図示していない）に引くことができる経路は４本あることを示す。ウェブ・ページ内をランダム・ウォークした場合には、ペナルティの数値（節点ＡとＷ．Ｓ．リーのウェブ・ページとの間のリンクの数）は関連する。何故なら、ランダム・ウォークを行った場合、リンク数の少ない経路内のウェブ・ページがアクセスされる頻度は、リンク数の多い経路内のウェブ・ページがアクセスされる頻度より高い可能性があるからである。各リンクには、図６（ｂ）に示すように、そのペナルティの数値に基づいて、確率の数値および遷移の数値が割り当てられる。
【００５６】
下記の項は、節点Ａを離れている辺の遷移の確率に関する既知の事実のいくつかを反映している。
・  すべての上記遷移確率の合計は、１．０に等しい。
・  節点Ｆのペナルティは、節点Ｃのペナルティの二倍であるので、ＡからＦまでの遷移確率は、ＡからＣまでの遷移の確率の半分でなければならない。
・  節点Ｄのペナルティは、節点Ｃのペナルティの３／２であるので、ＡからＤまでの遷移確率は、ＡからＣまでの遷移の確率の２／３でなければならない。
【００５７】
それ故、節点Ａを離れる辺に対する遷移の数値は、（上記アルゴリズムの段階５（ｅ）のところで説明したように）、下記の一組の一次制約条件を使用して計算することができる。
Ｔ［Ｆ，Ａ］＋Ｔ［Ｄ，Ａ］＋Ｔ［Ｃ，Ａ］＋Ｔ［Ｊ，Ａ］＝１．０
４×Ｔ［Ｆ，Ａ］＝３＊Ｔ［Ｄ，Ａ］
３×Ｔ［Ｄ，Ａ］＝２＊Ｔ［Ｃ，Ａ］
２×Ｔ［Ｃ，Ａ］＝４＊Ｔ［Ｊ，Ａ］
４×Ｔ［Ｊ，Ａ］＝４＊Ｔ［Ｆ，Ａ］
４×Ｔ［Ｆ，Ａ］＝２＊Ｔ［Ｃ，Ａ］
４×Ｔ［Ｊ，Ａ］＝３＊Ｔ［Ｄ，Ａ］
【００５８】
上記一組の制約条件は、冗長性を持つものであることに留意されたい。（すべての未知数を解くのに、最初の四つの式だけで十分である。）図６（ｂ）は、これらの一次制約条件を解くことにより入手する遷移の数値を示す。ランダム・ウォーク・アルゴリズムが節点Ａを離れる際に、節点ＪまたはＦがアクセスを受ける確率は３／１６であり、節点Ｃがアクセスを受ける確率は３／８であり、節点Ｄがアクセスを受ける確率は２／８である。
【００５９】
本発明の実施形態の場合には、構造情報を反映する辺遷移の確率が計算されると、ｉノードを識別するために、収束ベクトル（または上記一次式に対応する固有ベクトル）を使用することができる。以下に収束ベクトルについて説明する。ランダム・ウォーク・グラフＲ（ｖw）（Ｖ，Ｅ，Ｔ）が分かっている場合には、ｔはＴの収束ベクトルであり、この場合、
【数４１】
0003659181.tif 000009
であり、また、ｔ［ｉ］は、十分長いランダム・ウォーク中に、節点ｖ［ｉ］のところで、ランダム・ウォーク・プロセスが使用した時間の百分率を示す。それ故、ｔ＝Ｔｔであり、（Ｉ−Ｔ）ｔ＝０である。ここで、Ｉは単位マトリックスである。
【００６０】
遷移マトリックスの構造のために、上記収束ベクトルの存在が保証される。直感的に、ｔ［ｉ］は、十分長いランダム・ウォーク中に、節点ｖ［ｉ］のところで、ランダム・ウォーク・プロセスが使用した時間の百分率を示す。すでに説明したように、ｔ［ｉ］の数値が高いということは、対応する節点ｖ［ｉ］が、より良いｉノードであることを示す。従って、ｉノードは、収束ベクトル内のその対応する数値の順序内において高い優先順位を持つことができる。
【００６１】
任意の二つの節点の間の関連を最もよく反映している節点、（すなわち、最も高いｔ［ｉ］値を持つ節点）は、ｉノード節点と呼ばれ、下記のように定義される。グラフＧ（Ｖ，Ｅ）が分かっている場合には、Ｇ内の節点ｖa、ｖb、ｉノード節点、およびｉノードG（ｖa，ｖb，ｄ）として表示された距離ｄにｉノード節点は、下記式で示される節点ｖk∈ＶNである。
ｔ［ｋ］＝ｍａｘ｛ｔ［ｉ］｜ｖi’∈Ｖ｝
ｔ［ｉ］＞ｔ［ｊ］である場合には、ｖiは、ｖjより優勢であると見なされる。
【００６２】
引続き上記例について説明するが、これは説明のためだけのものに過ぎない。図７（ａ）は、グラフＧuを示し、この場合、各節点ｖiは、二つの辺内の節点ＡまたはＢから、届く範囲にあると仮定しよう。ここでもまた、図７の節点は、図４のウェブ・ページに対応することを理解されたい。図７（ａ）の節点につけた数字は、その節点の対応する距離ペナルティである。これらのペナルティは、グラフの優勢な節点を決定する際に使用される。
【００６３】
図７（ｂ）は、図７（ａ）に対応する完全なランダム・ウォーク・グラフＲ(A,B,2)を示す。上記節点ペナルティを使用して計算した遷移の数値は、辺上に数字で表示してある。また、図８（ａ）は、対応する遷移マトリックスＴを示す。図８（ａ）に示すように、直接接続していない多くの節点があり、そのため、これら二つの節点の間の移動がゼロである確率がある。このことが、図８（ａ）内のゼロを説明している。
【００６４】
一次式（Ｉ−Ｔ）ｔ＝０（すなわち、１２の変数および１３の制約条件）を解いた場合、図８（ｂ）に示すように、ｔの数値を計算することができる。例えば、図８（ｂ）の行Ａ内の収束ベクトルを計算するために、図８（ａ）の行Ａを使用することができる。すでに説明したように、図８（ｂ）の収束ベクトルは、十分長いランダム・ウォーク中に、その特定の節点のところで、ランダム・ウォーク・プロセスが費やす時間の一部である。図８（ｂ）の場合には、節点ＡおよびＢを除いて、最も優勢な節点はＣである。節点ＤおよびＥの優勢度はＣより低い。何故なら、これらの節点は、もはやＡとＢの間の経路上に存在しないからである。また、節点ＪおよびＬは、節点ＦおよびＨと同じ遷移の数値を持っているが、これらの節点ＪおよびＬはより高い収束ベクトルを持つ。何故なら、節点ＪおよびＬは、複数の経路（一本は節点Ｉを含み、一本は節点Ｋを含む）上に位置していて、そのため、ランダム・ウォーク・プロセスは、節点ＦおよびＨのところでよりも、節点ＪおよびＬのところで、より多くの時間を費やす可能性が高いからである。
【００６５】
図８（ｂ）は、ランダム・ウォークに基づいて作成したものであるが、エンドユーザー要求の実際のログを使用することができる場合には、実際のエンドユーザーの要求パターンに基づいて、上記確率を修正することができる。実際の使用に基づく確率により、図７（ｂ）のグラフを作成することができる。その後で、図８のチャートに類似のもう一組のチャートが作成される。
【００６６】
図７に示すグラフのような二つの既知のソース・ページ用のグラフを作成する場合には、上記ウェブ・ページおよびその中に埋め込まれているすべてのリンクを参照することにより、順方向のリンクを決定することができる。逆方向のリンクを見出すためには、逆方向のリンクの位置を見出すことができる探索を使用することができる。これら二つのタイプの情報を使用して、図７のグラフを作成することができる。時間が経過するにつれて、一本リンク、二本のリンク内等のソース・ページから到達可能であるページのリストが蓄積される。最終的には、両方のソース・ウェブ・ページから到達可能である一組のページを識別しなければならない。
【００６７】
＜ケース２：二ページ以上のページを含むＳ＞
本発明の他の実施形態の場合には、構造ｉノード選択プロセスを、二つ以上のシード・ページを含む状況にまで拡大して適用することができる。前の節で説明したアルゴリズムを、Ｓが二つ以上のシード・ページを含むケースにまで拡大適用するために、上記アルゴリズムは、近隣の境界を発見し、ランダム・ウォーク・グラフ内の各節点のペナルティを計算するために、これらのシード・ページを使用することに留意されたい。
【００６８】
これらのタスクの中の第一のタスク（近隣の境界を発見すること）は、下記のように一般化することができる。一組の節点｜Ｓ｜＞２、および半径ｄが分かっている場合には、本発明の他の実施形態の場合には、Ｇu（Ｖ、Ｅu）の関連近隣ＧN（ＶN，ＥN）は、
【数４２】
0003659181.tif 000010
という一組の節点であり、これらの節点には、
【数４３】
0003659181.tif 000011
となるような横方向の辺ｄ内のＩ内の節点から到達可能である。
ここでもまた、すべてのシード節点から到達可能である少なくとも一つの節点、
【数４４】
0003659181.tif 000012
が存在すると仮定することができる。このように単純化した理由は、ソース・ページからさらに遠くにあるウェブ・ページは、重要性が少なくなり、ソース・ページからアクセスされる可能性が少ないとの判断が行われたためである。
【００６９】
各節点のペナルティを決定するという第二のタスクは、二つの方法で処理することができる。本発明の他の実施形態の場合には、シード節点からの距離ｖi’のもっと正確なコンテンツを入力するために、ペナルティの定義を、
【数４５】
0003659181.tif 000013
のように一般化することもでき、または、好ましい実施形態の場合には、下記のように定義することもできる。
ｐｅｎａｌｔｙ（ｖi’）＝ｌｅｎｇｔｈ（ｍｉｎｉｍｕｍ＿ｓｔｅｉｎｅｒ＿ｔｒｅｅ（Ｓ∪｛ｖi’｝））
Ｇ’が、Ｇの所与のサブセットＲ内のすべての節点を含むように、所与のグラフＧの最小重み接続サブグラフＧ’を見出すための問題は、シュタイナーの木問題と呼ばれていることに留意されたい。（それが存在する場合には、Ｇ’は、木であることが保証される。）当業者であれば、シュタイナーの木問題をよく理解していることに留意されたい。（例えば、１９９２年発行の個別数学会誌５３巻の編集者であるフランク  Ｋ．ワング、ダナ  Ｓ．リチャード、およびパウエル・ウィンターの「シュタイナーの木問題」を参照されたい。）都合の悪いことに、最小重みシュタイナーの木問題は、ＮＰハードであることが周知である。すなわち、多項時間解があるのかどうかが分かっていない。一方、すべての関連する最短経路の合成として計算され、上記アルゴリズムで使用されるペナルティの定義は、多項時間を必要とすることが分かっていて、これはもっと効率のよい解法である。
【００７０】
＜ケース３：重要トピックスの考察＞
ランダム・ウォークのための遷移確率の計算の際に使用される、ペナルティを識別するための節点−シード間距離情報を使用する、本発明の実施形態の上記ランダム・ウォーク・アルゴリズム。関連を推理するためのタスクに文書のコンテンツを内蔵させる目的で、文書のコンテンツを含めるために、ペナルティの定義を変更することができる。以下の説明は、本明細書内においては、トピックスに焦点を当てたランダム・ウォーク・アルゴリズムと呼ぶ、ユーザーが推理に興味を持つ特定のトピックスを考察する基本的ランダム・ウォーク・アルゴリズムの延長である。
【００７１】
トピックスに焦点を当てたランダム・ウォーク・アルゴリズムを使用すれば、シードＵＲＬに対してだけではなく、特定のトピックスに対する文書関連を推理することができる。例えば、上記例について再び説明すると、Ｗ．Ｓ．リーのウェブ・ページ、およびＤ．アグレウォールのウェブ・ページが、何故ＮＥＣに関連しているのか、何故、Ｗ．Ｓ．リーのウェブ・ページ、およびＤ．アグレウォールのウェブ・ページが、Ｐ．シュールマンのウェブ・ページに関連しているのかを発見することに興味がある。これらの質問に答えるために、ＮＥＣ、またはＰ．シュールマンのページに関連するページにもっと低いペナルティの数値が割り当てられ、その結果、これらのページは、もっと高いスコアを受け取る。
【００７２】
節点ｖのコンテンツと所与のトピックスとの間の関連を測定するための関数、ｒｅｌｅｖａｎｃｅ（ｖ，ｔｏｐｉｃ）が存在すると仮定した場合、トピックスに焦点を当てたランダム・ウォーク・アルゴリズムに対する調整は、節点のペナルティを下記のように再定義することになる。
ｐｅｎａｌｔｙ（ｖ）／ｒｅｌｅｖａｎｃｅ（ｖ，ｔｏｐｉｃ）
【００７３】
それがあるトピックスに関連する場合に、ウェブ・ページの関連の程度を測定する一つの方法は、標準探索エンジンの結果を使用する方法である。すなわち、所与のトピックスに対して、探索エンジンは、そのトピックスを含んでいる多数のウェブ・ページを識別することができ、さらに、そのウェブ・ページ内において、そのトピックスが見出された回数に従って、そのウェブ・ページのランク付けを行うこともできる。これらのウェブ・ページには、高い関連の数値を割り当てることができる。関連の程度を測定する際に、そのウェブ・ページの全体の大きさも考慮することができる。例えば、「自動車」という言葉が、非常に小さいウェブ・ページ内に１０回でてきて、一方、非常に大きいウェブ・ページ内に１１回でてきたとする。この場合には、大きなウェブ・ページより小さなウェブ・ページの方が、自動車に深い関連を持つものと思われる。他の考慮としては、そのウェブ・ページ内で、そのトピックスが見出される場所を含めることができる。例えば、あるウェブ・ページの本文中含まれている「自動車」という言葉は、その言葉「自動車」が、そのウェブ・ページのある種の表題の中にでてきた場合と比較すると、その重要性は低い。その言葉が、どのように使用されているかも重要である。例えば、「自動車」という言葉が、太字またはイタリック体で印刷されている場合には、関連性の点でより重要である。
【００７４】
引続き上記例について説明を続けるが、この説明は単に説明のためのものに過ぎない。また、図９（ａ）について説明すると、Ｗ．Ｓ．リーのウェブ・ページ（節点Ａ）、およびＤ．アグレウォールのウェブ・ページ（節点Ｂ）が、何故Ｐ．シュールマンに関連しているのかを見出すことに興味を持っていると仮定する。また、Ｐ．シュールマンのウェブ・ページ（節点Ｇ）が、焦点を当てているコンテンツ、Ｐ．シュールマンに深い関連を持っていると仮定し、また、使用した関連関数が、Ｇに０．８を割り当て、他のすべてのページに０．１を割り当てたと仮定する。さらに、下記のペナルティ機能を使用すると仮定する。
ｐｅｎａｌｔｙ（ｖ）／ｒｅｌｅｖａｎｃｅ（ｖ，ｔｏｐｉｃ）
【００７５】
図９（ａ）は、対応するグラフと関連する節点ペナルティを示す。ランダム・ウォーク・グラフおよび遷移マトリックスＴを構成した後で、図９（ｂ）に示すように、収束マトリックスｔを計算することができる。収束ベクトルによれば、このグラフ内の最も「優勢な」節点はＧである。図８（ｂ）の結果と比較した場合、Ｇ、ＦおよびおよびＨのスコアは、節点Ｇの関連性が増大したために大きくなる。それ故、トピックスに焦点を当てたランダム・ウォーク・アルゴリズムは、リンク構造および焦点を当てたトピックスの考慮の両方を反映する。
【００７６】
本発明の実施形態によれば、上記ランダム・ウォーク・アルゴリズムのいずれかが生成したもっと優勢な収束ベクトルを、データ探索、またはコンテンツを予備取り出しおよびリフレッシュするために使用することができる。
【００７７】
＜ユーザー指向のウェブ・ページのリフレッシュおよび予備取り出し＞
ウェブ・ページを識別した上記方法は、データ探索またはコンテンツの予備取り出しのための、二つまたはそれ以上のシード・ページに対して高い関連数値を持つ。上記方法を使用して構成したランダム・ウォーク・グラフは、ペナルティ値を、節点間の距離、および節点の関連性に基づいて節点（ウェブ・ページ）の間の辺またはリンクに割り当てる。
【００７８】
本発明の他の実施形態は、一つまたはそれ以上のウェブサイトをリンクに沿って情報を順次表示している一人またはそれ以上のエンドユーザーの現在の位置を考慮して、どのウェブ・ページを予備取り出しすべきか、リフレッシュすべきかを決定するための技術を開示している。上記技術は、上記開示のランダム・ウォーク・アルゴリズムを修正したもので、このアルゴリズムの場合には、リンクに沿って情報を順次表示しているエンドユーザーの現在の位置は、シード・ページまたはソース・ウェブ・ページであり、ミラー・サーバー、プロキシ・サーバー等が維持しているエンドユーザー・ナビゲーション履歴ログが、その辺（すなわち、ナビゲーション用のリンク）に対するペナルティの数値を決定するために使用される。通常、ウェブ・ページが、現在のエンドユーザーのナビゲーション位置に近ければ近いほど、小さなペナルティの数値が割り当てられる。しかし、ペナルティの数値を計算する際には、第二のシード・ページの代わりにユーザーおよび他の優先順位が考慮される。
【００７９】
予備取り出し帯域幅Ｐおよび予備取り出しすべき一組のオブジェクトＯが分かっている場合には、本発明の実施形態は、全優先順位を最大にするためにオブジェクトを予備取り出しする場合、優先順位ｐiをオブジェクトｏi∈Ｏに割り当て、下記のものも最大にされる。
・  ユーザーの満足度（例えば、もっと重要なオブジェクトが最初に配信される。）
・  顧客（ページ・オーナー）の満足度（例えば、もっと頻繁に更新されたページが、もっと頻繁に予備取り出しされる。）
・  予備取り出ししたオブジェクトの利用（例えば、予備取り出しされたオブジェクトの頻度が使用される。）
【００８０】
下記の説明は、「オブジェクト」または「ページ」の予備取り出しについての説明であるが、どちらのユーザーも、上記オブジェクトを含むウェブ・ページ、およびオブジェクト自身の予備取り出しの両方を含むことと理解されたい。
【００８１】
＜ユーザーの満足度および顧客の満足度＞
ユーザーの満足度は、そのオブジェクト（例えば、宣伝対ニュース映像）のタイプ／特性に基づいて、各オブジェクトｏi∈Ｏに割り当てられたユーザーオブジェクト優先順位ｕiにより知ることができる。顧客／著者の満足度は、そのオブジェクト（例えば、宣伝対ニュース映像）のタイプ／特性に基づいて、Ｏ内の各オブジェクトｏiに割り当てられた、パラメータｃiにより測定することができる。
【００８２】
＜オブジェクトの利用度＞
予備取り出ししたオブジェクトの利用度は、オブジェクトの利用確率により測定することができる。この確率は、（１）期限が切れる前に、予備取り出しされたオブジェクトが、実際に利用される（ユーザーに視覚化される）可能性、および（２）それが視覚化される速さを示す。それ故、この情報を入手するには、下記の情報が必要である。
・  ページ関連（何故なら、関連するページが視覚化される可能性が高いから）
・  エンドユーザーの現在の位置からのリンクの数およびエンドユーザーの「密着度（stickness）」で示すそのページまでの距離（エンドユーザーがそのページを概観するのに使用した時間）
・  エンドユーザーのそのページを概観する前に、そのページが更新され（それにより、予備取り出ししたページが役に立たなくなる）可能性。この数値は、更新頻度およびオブジェクト期限切れ時間により計算することができる。）
【００８３】
＜技術＞
説明上の都合で、その期間中に、予備取り出し帯域幅ｐ（ｔ）＝Ｐを使用して、Ｏ内のオブジェクトの適当なサブセットが予備取り出しされる時間フレーム（ｔ0、ｔ0＋δt）が存在すると仮定する。さらに、ユーザーの優先順位およびページ著者の優先順位が分かっていると仮定する。それ故、エンドユーザーｕが分かっている場合には、ｕｐｒｅｆ（ｕ）が、エンドユーザー（ｕ）の優先順位を示すものとし、ページ著者ａが分かっている場合には、ａｐｒｅｆ（ａ）が、対応する一組のページ著者の優先順位を表すものとする。ｕｐｒｅｆ（ｕ）およびａｐｒｅｆ（ａ）は、数値を表すものではなく、ユーザーの優先順位および著者の優先順位を定義する一組の規則を表すものと理解されたい。
【００８４】
さらに、ウェブは、有向グラフＧ（Ｖ，Ｅ）としてモデル化することができる。この場合、Ｖはウェブ・ページに対応し、Ｅはリンクに対応する。各ｖ∈Ｖは、一組の＜Ｏv，ａv＞である。この場合、Ｏvは、（主ＨＴＭＬファイルを含む）一組の媒体オブジェクトであり、ａvはページ著者である。各オブジェクトｏは、それに関連するあるサイズｓｉｚｅ（ｏ）を持つ。グラフＧ内の二つの節点ｖ１およびｖ２が分かっている場合には、Ｏv1∩Ｏv2は、必ずしも空でなくてもよいことを理解されたい。すなわち、オブジェクトは、ページを横切って共有することができる。所与のオブジェクトｏを持つページのリストは、ページ（ｏ）である。
【００８５】
エンドユーザーｕの場合には、Ｖ内の各節点ｖに対してページ優先順位重みｐｒｅｆ（ｕ，ｖ）を割り当てることができる。ｐｒｅｆ（ｕ，ｖ）の数値は、ｕｐｒｅｆ（ｕ）、ａｐｒｅｆ（ａv）により定義される優先順位規則を、Ｏvのコンテンツに適用することにより計算することができる。同様に、個々の各オブジェクトｏ∈Ｏvの場合には、ユーザーの優先順位と著者の優先順位とを結びつけるオブジェクト優先順位重みｐｒｅｆ（ｕ，ｏ，ｖ）およびオブジェクトのタイプおよびコンテンツを計算することができる。
【００８６】
有向グラフおよびページ優先順位を使用して、各ページに対してページ利得ｇａｉｎ（ｕ，ｖ）を計算することができる。この場合、ページ利得は、通常、ページとエンドユーザーの現在の位置との間の関連を表す。ページが予備取り出しされている場合には、エンドユーザーの満足度と見なすことができるし、または、ページとエンドユーザーの現在の位置との間の関連のレベルのすべての測定であるエンドユーザーが、そのページにアクセスする可能性であると見なすことができる。
【００８７】
本発明の好ましい実施形態の場合には、各ページｖに対してランダム・ウォーク・アルゴリズムを使用して、利得（ｕ，ｖ）を計算することができる。グラフＧ（Ｖ、Ｕ）および現在のページｐ（エンドユーザーの現在の位置）に対応する節点ｖcが分かっている場合には、下記のように、ランダム・ウォーク・グラフＧW（ＶW，ＥW）を生成することができる。
・  Ｖ内の各節点ｖiに対してＶW内の節点ｖi’を設定する。
・  Ｅ内の各辺ｅj＝＜ｖa，ｖb＞に対して二つの辺ｅj’＝＜ｖa’，ｖb’＞およびｅj”＝＜ｖb’，ｖa’＞を設定し、それらをＥW内に入れる。
・  各辺ｅ＝＜ｖa，ｖb＞∈Ｅの場合であって、辺に、辺の重みｗ（ｅ）＝ｓ（ｕ，ｖs）を割り当てる。好ましい実施形態の場合には、ｓ（ｕ，ｖs）は、ソース節点ｖsに対するエンドユーザーｕの「密着性」（エンドユーザーｕが、ページｖsのところで費やした時間の期待値）を表す。しかし、他の実施形態の場合には、辺の重みｓ（ｕ，ｖs）は、単位値で近似することもできるし、または辺が領域の境界を横切っている場合には、もっと大きな数値を割り当てることもできる。
・  節点ｖcから、Ｖ内のすべての節点までの最短距離を見出す。この場合、ｓｈｏｒｔｅｓｔ（ｖc，ｖi）は、ｖcからｖi∈Ｖへの最短距離を示す。ｓｈｏｒｔｅｓｔ（ｖc，ｖi）の代わりに、（以下に定義する）ｅａｒｌｉｅｓｔ（ｕ，ｖi）を使用することもできることを理解されたい。最短の経路は、当業者であれば周知の最短経路アルゴリズムを使用して、各辺の辺の重みを考慮に入れて識別することができる。
・  各節点ｖ∈ＶWに対してペナルティを計算する。
ｐｅｎａｌｔｙ（ｕ，ｖ）＝ｓｈｏｒｔｅｓｔ（ｖc，ｖ）／（ｐｒｅｆ（ｕ，ｖ）＋１）
・  各節点ｖ∈ＶWに対して下記式を解くことにより単位確率ｕｎｉｔ（ｕ，ｖ）を計算する。
【数４６】
0003659181.tif 000014
ここで、単位確率ｕｎｉｔ（ｕ，ｖ）は、各々の１／ｐｅｎａｌｔｙ（ｕ，ｖi）に対する一つの辺の使用の確率を表す。
・各辺ｅ＝∈＜ｖi，ｖj＞∈ＶWに対して、下記のように、ｐｒｏｂ（ｕ）（ｖj｜ｖi）を計算する。
ｐｒｏｂ（ｕ）（ｖj｜ｖi）＝ｕｎｉｔ（ｕ，ｖj）／ｐｅｎａｌｔｙ（ｕ，ｖi）
【００８８】
次に、ランダム・ウォーク・グラフの定常状態分布（収束ベクトル）を見出すことにより、利得（ｕ，ｖ）を計算することができる。ランダム・ウォーク・グラフＧW（Ｖw，ＥW）が分かっている場合には、利得ｇａｉｎ（ｕ，ｖ）は、Ｔの収束ベクトルである。この場合、Ｔは遷移値ｐｒｏｂ（ｕ）（ｖj｜ｖi）のマトリックスであり、また、
【数４７】
0003659181.tif 000015
である。この収束ベクトルは、下記のものを捕捉することに留意されたい。
・  エンドユーザーに対するページの関連
・  エンドユーザーが特定のページにアクセスする可能性（接続性）
・  エンドユーザーがページにアクセスする速さ（エンドユーザーの現在の位置から、各ページまでの距離）
【００８９】
その後で、ページ利得ｇａｉｎ（ｕ，ｖ）を使用して、各オブジェクトに対するオブジェクトの利得ｇａｉｎ（ｕ，ｏ）を、
【数４８】
0003659181.tif 000016
として計算することができる。
各オブジェクトのコストも下記のように定義することができる。
ｃｏｓｔ（ｏ）＝ｓｉｚｅ（ｏ）
それ故、ユーザーｕへの利益を最大にするために、予備取り出し帯域幅Ｐuおよび予備取り出し持続時間δｔが分かっている場合には、Ｏの適当なサブセットＯsは、下記基準を満足させなければならない。
【数４９】
0003659181.tif 000017
【数５０】
0003659181.tif 000018
【００９０】
サブセットＯs、上記拘束条件への識別されたオブジェクトは、本発明の好ましい実施形態により、一人のエンドユーザー、またはシード・ページの現在位置に基づいて予備取り出しすることができる一組のオブジェクトを生成する。しかし、他の実施形態の場合には、上記アルゴリズムは、複数のエンドユーザーまたはシード・ページに拡大適用することができることを理解されたい。一組のユーザーＵが分かっている場合には、各オブジェクトに対して、オブジェクトの利得ｇａｉｎ（ｏ）を下記式により計算することができる。
【数５１】
0003659181.tif 000019
【００９１】
各オブジェクトのコストは、再び下記のように定義することができる。
コスト（ｏ）＝サイズ（ｏ）
【００９２】
この場合、上記一組のユーザーＵへの利益を最大にするために、予備取り出し帯域幅Ｐuおよび予備取り出し持続時間δｔが分かっている場合には、Ｏの適当なサブセットＯsは、下記基準を満足させなければならない。
【数５２】
0003659181.tif 000020
【数５３】
0003659181.tif 000021
【００９３】
本発明の他の実施形態の場合には、各オブジェクトｏに対して、そのオブジェクトが必要になる最も早い時間を表す数値（概観するのに最も早い時間、指定のｅａｒｌｉｅｓｔ（ｕ，ｏ）を計算することができる場合には、下記のようなこれらのオブジェクトを、Ｏsが決定される前に除去することができる。
ｅｘｐｉｒｅ（ｏ）＜ｅａｒｌｉｅｓｔ（ｕ，ｏ）
あるオブジェクトがウェブサイトからキャッシュに配信された場合には、そのオブジェクトの期限切れ時間ｅｘｐｉｒｅ（ｏ）を含むことができるメタ記述またはメタ・データを要求したヘッダが、上記オブジェクトと一緒に配信されることに留意されたい。
【００９４】
＜利得の計算および概観するための最も早い時間の推定＞
予備取り出しされたオブジェクトｏが、最初に有用になる時間であるｅａｒｌｉｅｓｔ（ｕ，ｏ）を推定するために、エンドユーザーが、ｏを含むページｐにアクセスすることができる時間を推定しなければならない。この時間は、エンドユーザーｕの現在位置、エンドユーザーの現在位置からの距離ｐ、およびエンドユーザーのウェブ空間内の移動方法により異なる。
【００９５】
ウェブ空間内のエンドユーザーの動きのパターンは、あるエンドユーザーがそこを通る可能性があるリンク、およびエンドユーザーが各ページに留まる長さを示すページの優先順位によりモデル化することができる。
・  ページの密着性ｓo（ｕ，ｖ）およびｓ（ｕ，ｖ）：ユーザーｕがページｖのところで使用する予想時間。この予想時間は、ユーザーおよびページコンテンツのサイズおよびタイプに対するそのページの関連の関数である。また、最初の密着性ｓo（ｕ，ｖ）は、再アクセスの密着性ｓ（ｕ，ｖ）より大きい。密着性は、予め定義したユーザーの優先順位であることに留意されたい。
【００９６】
密着性は重要である場合がある。何故なら、長時間の間、エンドユーザーがアクセスしようとしているページ（高い密着性の数値）は、そのエンドユーザーがアクセスする次のページを比較的長い時間必要としないことを意味するからである。このことは、そのユーザーにとって、次のウェブ・ページがいますぐ予備取り出しする必要のないページであることを意味する。一方、密着性の数値が低いページは、非常に短時間の間に、エンドユーザーが、次のページに移動しようとしていることを意味し、そのため、次にアクセスするウェブ・ページには、高い予備取り出し優先順位を与えなければならないことを意味する。しかし、ページの密着性は、次にどのページを予備取り出しすべきかの決定に関連する場合があるが、その時点で見ているウェブ・ページの重要性とは必ずしも関連しないことを理解されたい。これは、そのページが、どうしてそんなに長い時間見られていたのかその理由が分からないからである。例えば、そのページを見ている人が、ひと休みしたせいかもしれないし、そのウェブ・ページが非常に乱雑であるか、混乱しているために、長い間、そのページを見ていただけかもしれないからである。
【００９７】
＜概観するための最も早い時間の推定＞
ｖsおよびｖdは、グラフＧ内の任意の二つの節点である各リンクｅ＝（ｖs，ｖd）に対して辺の重みｗ（ｅ）＝ｓo（ｕ，ｖs）を割り当てることができる。エンドユーザーｕが現在位置しているページｖcが分かっている場合には、ページｐにアクセスすることができる最も早い時間を下記式のように計算することができる。
ｅａｒｌｉｅｓｔ（ｕ，ｐ）＝ｓｈｏｒｔｅｓｔ＿ｐａｔｈw（ｖc，ｖp）
それ故、あるオブジェクトを必要とする最も早い時間は下記のように計算することができる。
ｅａｒｌｉｅｓｔ（ｕ，ｏ）＝ｍｉｎ｛ｅａｒｌｉｅｓｔ（ｕ，ｐ）｜ｐ∈ｐａｇｅｓ（ｏ）｝
【００９８】
それ故、本発明の実施形態は、リンク構造とウェブ・ページのコンテンツの両方を考慮に入れるユーザー指向ウェブ・ページのリフレッシュ、および予備取り出しスケジューリングを最適にする目的のウェブ・ページ関連および利用を探索するために、ランダム・ウォークを使用するシステムおよび方法を提供する。本発明の実施形態は、また、反復をベースとする方法を使用しないで、式を解くことをベースとして入手するリンク分析を含むユーザー指向ウェブ・ページのリフレッシュ、および予備取り出しスケジューリングを最適にする目的のウェブ・ページ関連および利用を探索するためにランダム・ウォークを使用するシステムおよび方法を提供する。さらに、本発明の実施形態は、推理に焦点を当てるために一組のウェブ・ページを指定することができるユーザー指向ウェブ・ページのリフレッシュ、および予備取り出しスケジューリングを最適にする目的のウェブ・ページ関連および利用を探索するためにランダム・ウォークを使用するシステムおよび方法を提供する。
【００９９】
＜関連出願への相互参照＞
本発明の実施形態は、２０００年４月７日付の、「ユーザー指向のウェブ・ページのリフレッシュおよび予備取り出しスケジューリングにおけるウェブ・ページの関連および使用を探査するためのランダム・ウォーク」という名称の米国特許出願第６０／１９５，６４０号の優先権を主張する。上記出願のコンテンツは、引用によって本明細書の記載に援用する。
【図面の簡単な説明】
【図１】  エンドユーザーとウェブサイトとの間の従来のコンテンツ配信経路の一例のブロック図である。
【図２】  従来のキャッシュ・システムの一例のブロック図である。
【図３】  プロキシサーバーにとって有効な通常の接続の一例のブロック図である。
【図４】  二つのソース・ウェブ・ページを関連づける例示としてのリンク構造体のグラフである。
【図５】  異なるタイプのリンクである。
【図６】  （ａ）は、本発明の実施形態の図４の例の二つのソース・ページの間を移動するための、いくつかの中間ウェブ・ページに関連するペナルティ値のグラフであり、（ｂ）は、本発明の実施形態の図４の例の二つのソース・ページの間を移動するためのいくつかの中間ウェブ・ページに関連する遷移値のグラフである。
【図７】  （ａ）は、本発明の実施形態の図４の例の二つのソース・ページの間を移動するためのすべての中間ウェブ・ページに関連するペナルティ値のグラフであり、（ｂ）は、本発明の実施形態の図４の例の二つのソース・ページの間を移動するためのすべての中間ウェブ・ページに関連する遷移値のグラフである。
【図８】  （ａ）は、本発明の実施形態の図７（ｂ）の、遷移値に対応する遷移マトリックスであり、（ｂ）は、本発明の実施形態の（ａ）の、遷移マトリックスに対応する収束ベクトルである。
【図９】  （ａ）は、本発明の実施形態の焦点トピックスの考慮を含む、図４の例の二つのソース・ページの間を移動するためのすべての中間ウェブ・ページに関連するペナルティ値のグラフであり、（ｂ）は、本発明の実施形態の（ａ）の、グラフに対応する収束ベクトルである。
【符号の説明】
４８  Ｗ．Ｓ．リーのウェブ・ページ
５０  Ｄ．アグレウォールのウェブ・ページ
５４  ＮＷＵのウェブ・ページ
５６  ＳＵＮＹ，ＳＢのウェブ・ページ
５８  Ｐ．シュールマンのウェブ・ページ
６０  ウェブ８論文を含むウェブ・ページ
６２  Ｙ．ウーのウェブ・ページ
６４  ＣＣＲＬウェブ・ページ
６６  ＷＯＷＳ’９９ウェブ・ページ
６８  ＤＬ’９９ウェブ・ページ
【図１】
0003659181.tif 000055
【図２】
0003659181.tif 000056
【図３】
0003659181.tif 000057
【図４】
0003659181.tif 000058
【図５】
0003659181.tif 000059
【図６】
0003659181.tif 000060
【図７】
0003659181.tif 000061
【図８】
0003659181.tif 000062
【図９】
0003659181.tif 000063