(57)【要約】【課題】セッションベースクエリのためのノードのランク付けを課題とする。【解決手段】一実施形態において、本方法はセッションノードとそれにリンクした複数のリンクされたノードを含むノードのセットのモデルを利用する。リンクされたノードは親ノードと子ノードとを含む。親ノードは１つ以上の子ノードをセッションノードにリンクし、子ノードはそれをセッションノードにリンクする１つ以上の親ノードを有する。上記方法は、セッションノードから所定リンク数内のすべてのリンクされたノードに確率を分配する、前記ノードのセットの複数の確率分布を生成する段階を含む。各子ノードはその親ノードから親ノードに分配された所定割合の確率を受け取り、親ノードはその子ノードの各々に分配された確率の所定割合を一様に分配する。【選択図】図４
2008217764.tif 000002
【特許請求の範囲】
【請求項１】
セッションノードと前記セッションノードにリンクされた複数のリンクされたノードとを含むノードのセットのモデルにアクセスし、前記リンクされたノードは親ノードと子ノードとを含み、親ノードは１つ以上の子ノードを前記セッションノードにリンクし、子ノードは前記子ノードを前記セッションノードにリンクする１つ以上の親ノードを有する段階と、
前記ノードのセットに対して、前記セッションノードから所定リンク数内のすべてのリンクされたノードに確率を分配する確率分布を生成し、各子ノードはその親ノードの各々から前記親ノードに分配された確率の所定割合を受け取り、前記親ノードはその子ノードの各々に前記親ノードに分配された前記確率の前記所定割合を一様に分配する段階と、
前記ノードのセットのランク付けに使用するため前記確率分布を伝える段階とを有する方法。
【請求項２】
前記ノードはハイパーテキスト・マークアップ・ランゲージ（ＨＴＭＬ）文書である、請求項１に記載の方法。
【請求項３】
前記所定数のリンクはユーザの我慢強さをモデル化したものである、請求項１に記載の方法。
【請求項４】
前記所定数のリンクは２つのリンクである、請求項１に記載の方法。
【請求項５】
前記所定割合は１／２である、請求項１に記載の方法。
【請求項６】
前記ノードのセットのモデルはワールド・ワイド・ウェブの少なくとも一部をモデル化するグラフを含む、請求項１に記載の方法。
【請求項７】
前記ランク付けは前記ノードのセットの検索を容易にして、ユーザからのクエリに対する応答を生成する、請求項１に記載の方法。
【請求項８】
前記セッションノードから相異なる所定リンク数内のすべてのリンクされたノードに確率を分配する、前記ノードのセットの複数の確率分布を生成する段階と、
前記確率分布を平均化する段階と、
前記ノードのセットのランク付けに使用するため平均化した前記確率分布を伝える段階とを有する、請求項１に記載の方法。
【請求項９】
前記セッションノードから相異なる所定リンク数内のすべてのリンクされたノードに確率を分配する、前記ノードのセットの複数の確率分布を生成する段階と、
ユーザにより指定された嗜好に基づき前記ノードのセットのランク付けに使用する前記複数の確率分布を伝える段階とをさらに有する、請求項１に記載の方法。
【請求項１０】
前記ノードのセットの前記確率分布を生成する段階は、一様な確率分布から始めて確率分布を反復的に計算し、生成される前記確率分布は反復的に計算された確率分布の収束の結果得られる段階を含む、請求項１に記載の方法。
【請求項１１】
コンピュータにより実行される、有体的媒体にエンコードされた論理であって、前記論理は実行されると、
セッションノードと前記セッションノードにリンクされた複数のリンクされたノードとを含むノードのセットのモデルにアクセスし、前記リンクされたノードは親ノードと子ノードとを含み、親ノードは１つ以上の子ノードを前記セッションノードにリンクし、子ノードは前記子ノードを前記セッションノードにリンクする１つ以上の親ノードを有する段階と、
前記ノードのセットに対して、前記セッションノードから所定リンク数内のすべてのリンクされたノードに確率を分配する確率分布を生成し、各子ノードはその親ノードの各々から前記親ノードに分配された確率の所定割合を受け取り、前記親ノードはその子ノードの各々に前記親ノードに分配された前記確率の前記所定割合を一様に分配する段階と、
前記ノードのセットのランク付けに使用するため前記確率分布を伝える段階とを実行する論理。
【請求項１２】
前記ノードはハイパーテキスト・マークアップ・ランゲージ（ＨＴＭＬ）文書である、請求項１１に記載の論理。
【請求項１３】
前記所定数のリンクはユーザの我慢強さをモデル化したものである、請求項１１に記載の論理。
【請求項１４】
前記所定数のリンクは２つのリンクである、請求項１１に記載の論理。
【請求項１５】
前記所定割合は１／２である、請求項１１に記載の論理。
【請求項１６】
前記ノードのセットのモデルはワールド・ワイド・ウェブの少なくとも一部をモデル化するグラフを含む、請求項１１に記載の論理。
【請求項１７】
前記ランク付けは前記ノードのセットの検索を容易にして、ユーザからのクエリに対する応答を生成する、請求項１１に記載の論理。
【請求項１８】
実行されたとき、
前記セッションノードから相異なる所定リンク数内のすべてのリンクされたノードに確率を分配する、前記ノードのセットの複数の確率分布を生成する段階と、
前記確率分布を平均化する段階と、
前記ノードのセットのランク付けに使用するため平均化した前記確率分布を伝える段階とをさらに実行する、請求項１１に記載の論理。
【請求項１９】
実行されたとき、
前記セッションノードから相異なる所定リンク数内のすべてのリンクされたノードに確率を分配する、前記ノードのセットの複数の確率分布を生成する段階と、
ユーザにより指定された嗜好に基づき前記ノードのセットのランク付けに使用する前記複数の確率分布を伝える段階とをさらに実行する、請求項１１に記載の論理。
【請求項２０】
前記ノードのセットの前記確率分布を生成する段階は、一様な確率分布から始めて確率分布を反復的に計算し、生成される前記確率分布は反復的に計算された確率分布の収束の結果得られる段階を含む、請求項１１に記載の論理。
【請求項２１】
セッションノードと前記セッションノードにリンクされた複数のリンクされたノードとを含むノードのセットのモデルにアクセスし、前記リンクされたノードは親ノードと子ノードとを含み、親ノードは１つ以上の子ノードを前記セッションノードにリンクし、子ノードは前記子ノードを前記セッションノードにリンクする１つ以上の親ノードを有する手段と、
前記ノードのセットに対して、前記セッションノードから所定リンク数内のすべてのリンクされたノードに確率を分配する確率分布を生成し、各子ノードはその親ノードの各々から前記親ノードに分配された確率の所定割合を受け取り、前記親ノードはその子ノードの各々に前記親ノードに分配された前記確率の前記所定割合を一様に分配する手段と、
前記ノードのセットのランク付けに使用するため前記確率分布を伝える手段とを有するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はワールド・ワイド・ウェブ中のウェブページ等の相互リンクが張られたオブジェクトの検索に関する。
［関連出願］
この出願は、米国仮出願第６０／８７６５４６号（２００６年１２月２２日出願）の米国特許法第１１９条（ｅ）の利益を主張するものである。
【背景技術】
【０００２】
ウェブベース検索のためのノードのランク付けは重要な技術である。例えば、ＰＡＧＥＲＡＮＫはグーグル社が使用しているものであるが、ワールド・ワイド・ウェブの構造を調べてウェブページをランク付けしている。しかし、ＰＡＧＥＲＡＮＫは、成功しているが、ユーザの一般的な検索行動を正確にモデル化していない。
【発明を実施するための最良の形態】
【０００３】
実施形態により、例えばワールド・ワイド・ウェブのウェブページ等の相互リンクが張られた文書またはその他のオブジェクトのコレクション（collection）を検索するためのセッションベースのユーザモデルを提供する。一部の実施形態では、典型的なユーザ行動を従来技術よりよく追跡（track）できる、オブジェクトのセット全体の順序（すなわちランク）を計算する。
【０００４】
ＰＡＧＥＲＡＮＫはウェブページをその間のリンクを調べてランク付けするアルゴリズムである。各ウェブページＰｉに付されるランクは、ユーザが、ランダムに選択したウェブページから始まるリンクをランダムに選択した場合に、いずれはＰｉを訪れる（visit）確率に対応する。ワールド・ワイド・ウェブを「サーフィン（surfing）」するこのモデルは、ランダムサーファーモデルである。
【０００５】
ウェブにｎページＰ１，．．．，Ｐｎあり、各ページｉは外へのｌｉ個のリンクを有すると仮定する。Ｅｉｊ＝１であるとき、ページｉからページｊへのリンクがあることを示す。リンクが無ければＥｉｊ＝０である。ＰＡＧＥＲＡＮＫはｎページの各々のランクのベクトルＲを計算する。ここで、Ｒ（ｉ）はページｉのランクである。ＰＡＧＥＲＡＮＫはこの計算を反復し、計算したベクトルが同じ（similar）になるまでこの計算を反復する。このアルゴリズムでは、次の計算を行う：
【数１】
2008217764.tif 000003
ＰＡＧＥＲＡＮＫでは、αの値は０．８５である。
【０００６】
最初、ユーザがあるウェブページを訪れる確率はすべてのウェブページで等しい。ユーザがｔ番目の反復時にウェブページｉをおとずれる確率はＲｔ（ｉ）である。ユーザはページｉ中のｌｉ個のリンクの１つをランダムに選択するので、ユーザがウェブページｊにジャンプする確率は
【数２】
2008217764.tif 000004
である。ＰＡＧＥＲＡＮＫは、この確率を、ユーザが次のステップにウェブページｊにいる確率Ｒｔ＋１（ｊ）に加える。ユーザがウェブページｊ以外のウェブページにジャンプする確率は１−αであり、この確率は比較的小さい。
【０００７】
ランダムサーファーモデルは分析が比較的容易であるが、現実のユーザが検索をするやり方を正しく捉えていない。対照的に、本発明の実施形態は検索セッションの概念に基づくモデルを利用する。
【０００８】
図１は、ウェブページのセットにわたってのユーザの検索行動例を示す図である。ユーザはセッションページｉから検索を開始すると仮定する。ユーザは外へのｌｉ個のリンクの１つから他のページｊに進み、検索をやめるか、セッションページｉに戻って異なるリンク経路に進むまで、リンクのシーケンスの行き来を続ける。例えば、ユーザはセッションページｉから検索を開始する。ユーザはノード１を訪れ、ノード２に進む。ここで、必要に応じて、ノードとはウェブページやその他のリンク可能オブジェクトを含むものとし、その逆の場合も同じとする。ユーザは、欲するものが見つからなければ、セッションページｉに戻り、他のリンクを選択し、ノード３まで行く。ユーザは、この方向性は望ましくないと判断し、再びセッションページｉに戻る。ユーザは、ノード４に行くリンクに進み、最終的にノード５に行く。
【０００９】
この検索方法は現実のユーザの典型的な行動により近いものである。ユーザは、長いリンク経路（long  path  of  links）をたどってページに行き着くのではなく、もっと小さいリンクシーケンスをたどり、その途中で（at  the  end）そのシーケンスをさらに先に進むかどうか判断する。ユーザは、そのシーケンスをさらに先に進まない場合、元のページに戻り他の経路に進む。かかる検索パターンはインテリジェントサーファーモデル（Intelligent  Surfer  Model）の基礎となる。一部の実施形態では、かかる検索パターンを使用し、ウェブページやその他のリンク可能オブジェクト（linkable  objects）のランクを計算する。
【００１０】
Ｈｉｄをセッションページｉからｄ個のリンクを隔てたページのセットとする。Ｈｉをセッションページｉから最大ｋ個のリンクを隔てたページのセットとする。一部の実施形態では、以下の一様分布から始めて、確率ベクトルＲを反復的に計算する。
【数３】
2008217764.tif 000005
Ｒ０は、すべてのノードが最初にセッションノードとして等しい確率を有することを意味している。Ｃｉｊは、反復ｔにおいてセッションページｉがノードｊに貢献する確率Ｒｔ（ｉ）の割合を示す。Ｃｉｊは、ノードｉとノードｊの間に最大ｋ個のリンクを有する経路がある場合にのみ非ゼロとなる。一部の実施形態では、Ｃｉｊはｔとは独立なので、Ｃｉｊを事前に計算する。
【００１１】
一部の実施形態では、Ｈｉ中のノードに確率Ｒｔ（ｉ）を階層化して分配する。例えば、第１のステップですべてのＲｔ（ｉ）をＨｉ１中のｌｉ個のノードに分配する。簡単のため、一部の実施形態では、この分配は実質的に一様であると仮定する。第２のステップで、ｊからリンクされたＨｉ２中のノードに、Ｈｉ１中の各ノードｊに分配された確率のパーセンテージを分配する。再度、簡単のため、一部の実施形態では、ｊの確率の１／２をｊがリンクするｌｊ個のノードに均等に分配するものとしてもよい。一部の実施形態では、このプロセスをｋ回のステップに対して反復する。
【００１２】
図２乃至図４は、一部の実施形態でＲｔ（ｉ）をＨｉ中のノードにいかに分配するかを例示する分配例を示す。図２は一例であり、第１のステップで確率β＝Ｒｔ（ｉ）をノードｖ１、ｖ２及びｖ３に均等に分配する。ノードｖ１、ｖ２及びｖ３はノードｉに集まっているものである。図３に例として示したように、これ以降のステップで、ノードｖ１、ｖ２及びｖ３の確率をそれぞれノード［v４、v５、v６］、［v６、v７、v８］及び［v９、v１０］に分配する。図４はβの分配結果を示している。一部の実施形態では、この分析からファクタＣｉｊを直接求め、一部の実施形態では、ファクタＣｉｊはβとは独立である。限定ではなく一例として、一部の実施形態では
【数４】
2008217764.tif 000006
である。一部の実施形態では、対応するファクタＣｉｊをルックアップ（look  up）することにより、各反復の動作を実行する。かかる実施形態では、各反復においてリンクを進む（link  traversals）必要はない。
【００１３】
一部の実施形態では、このアルゴリズムの実行にはファクタｋが重要である。ファクタｋは、所望のウェブページを見つけるためにユーザが進んでもよいと思うリンクを示す。従って、ファクタｋはユーザの辛抱強さをモデル化したものである。一部の実施形態では、ｋ＝１の場合はＰＡＧＥＲＡＮＫの計算に戻る。従って、一部の実施形態はＰＡＧＥＲＡＮＫを包含している。
【００１４】
図５は、セッションベースクエリのためにノードのランク付けをするシステム１０の例を示す図である。システム１０は、端末１２とサーバ１４とを含み、これらはネットワーク１６を介して通信する。一部の実施形態では、ネットワーク１６は、ローカルエリアネットワーク（ＬＡＮ）、ワイヤレスＬＡＮ（ＷＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、インターネットの一部、その他のネットワーク１６、またはこれらの組合せである。本発明では、ネットワーク１６は任意の適切なものでよい。リンク１８は各端末１２またはサーバ１４をネットワークに結合する。一部の実施形態では、各リンク１８は有線リンク、無線リンクまたは光リンクを含む。一部の実施形態では、各リンク１８はＬＡＮ、ＷＬＡＮ、ＷＡＮ、ＭＡＮ、インターネットの一部、公衆交換電話網（ＰＳＴＮ）、アクセスネットワーク、その他のリンクまたはこれらの組合せである。本発明では、任意の適切な端末１２と任意の適切なサーバ１４を任意の適切なネットワーク１６に結合する任意の適切なリンク１８を予定している。
【００１５】
端末１２によりユーザはネットワーク１６を介して通信できる。限定ではなく一例として、端末１２はコンピュータシステム（ノートブックまたはデスクトップコンピュータシステム）、携帯電話（ワールド・ワイド・ウェブをブラウズする機能を含むものであってもよい）、その他の端末１２を含む。サーバ１４は、端末１２にサーバ１４の機能またはデータへのアクセスを提供する。限定ではなく一例として、サーバ１４はウェブサーバを含んでもよい。ウェブサーバは端末１２からのＨＴＴＰ（Hyper  Text  Transfer  Protocol）リクエストを受け取り、端末１２にＨＴＴＰレスポンス及びウェブページ等の要求データを伝送する。ウェブページはＨＴＭＬ文書を含んでいてもよい。他の例として、サーバ１４はアプリケーションサーバを含んでいてもよい。本発明では、任意の適切なサーバ１４を予定している。
【００１６】
一部の実施形態では、システム１０の１つ以上のサーバ１４は、１つ以上のウェブ検索エンジン２０、１つ以上のランキングエンジン２２、またはその両方を含む。一部の実施形態では、バスまたはその他のワイヤにより、１つ以上のウェブ検索エンジン２０は通信のため１つ以上のランキングエンジン２２に結合している。ウェブ検索エンジン２０の例には、ＢＡＩＤＵ、グーグル、ＬＩＶＥ  ＳＥＡＲＣＨ、ヤフー！検索などがある。本発明では、任意の適切なウェブ検索エンジン２０を予定している。さらに、本発明は任意の適切な検索エンジンを予定しているが、これは必ずしもウェブ検索エンジン２０である必要はない。一部の実施形態では、ランキングエンジン２２は、上記のように、ウェブページまたはその他のリンク可能オブジェクトをランク付けするハードウェア、ソフトウェア、または組み込みロジックコンポーネント（embedded  logic  component）またはこれらの２つ以上の組合せを含む。限定ではなく一例として、ランキングエンジン２２はサーバ１４のすべてのウェブページまたはその一部をランク付けし、１つ以上のウェブ検索エンジン２０はランキングエンジン２２が生成したランキングを使って、端末１２のユーザからの検索クエリに応答して検索結果を生成し、それを端末１２のユーザに返す。
【００１７】
一部の実施形態では、ユーザがセッションページＰから検索を開始して、そこから始まる一定数Ｎのリンクをたどるというユーザモデルを仮定してインテリジェントサーファーのモデル化を試みる。ある確率で、ユーザは検索がうまく行かず、セッションページＰに戻って別のリンク経路を進む。一部の実施形態では、ＰＡＧＥＲＡＮＫはかかるモデルの特別な場合（Ｎ＝１の場合）である。一部の実施形態では、検索結果を生成して返すために、ウェブページまたはその他の相互リンクされたオブジェクトをよりよくランク付けできる。
【００１８】
図６は、セッションベースクエリのためにノードのランク付けをする方法例を示す図である。Ｇ＝（Ｖ，Ｅ）はワールド・ワイド・ウェブをモデル化したグラフとする。ノードＶはウェブページを表し、ノード間をつなぐエッジはウェブページ間のウェブリンクを表す。ユーザが最初のウェブページから進み、あきらめて最初のウェブページから再び開始する連続したリンクの数をＮとする。数Ｎはユーザの我慢強さを表す。ＧとＮが与えられると、アルゴリズムにより、インテリジェントサーファーパターンをたどるユーザに対応するノードＶにわたる確率分布Ｄを求める。すなわち、インテリジェントサーファーパターンをたどるユーザは、確率分布Ｄにおいて高い確率を有するノードに行く可能性が高い。本方法はステップ１００で始まり、アルゴリズムによりＶにおいて一様な分布Ｄ０＝Ｕを生成する。ステップ１０２において、アルゴリズムにより、最終分布Ｄに収束するまで、反復的に「よりよい」分布Ｄｉを生成する。各反復ｉにおいて、アルゴリズムにより、vからＮ個のエッジ以内で到達できるすべてのノードに対して、各ノードvに確率Ｄｉ（v）を分布させる。こうして分布Ｄｉ＋１′を求める。一部の実施形態では、アルゴリズムにより、確率分布ＤｉをＵで重み付けして分布Ｄｉ＋１を生成する。ステップ１０４において、Ｄｉ＋１とＤｉが互いに、例えば所定の１つ以上の基準に基づき非常に近くなるとアルゴリズムは終了する。ステップ１０６において、結果として得られた、ノードをランク付けする確率分布Ｄを伝えて、本方法が終了する。一部の実施形態では、必要に応じて、Ｎの複数の値に対してアルゴリズムを複数回実行する。かかる実施形態では、結果として得られた分布を平均するか、またはユーザが検索を実行するときに選択肢を与える。
【００１９】
本発明は、ここに説明した実施形態に対する、当業者が想到するだろうすべての変更、置換、変形、代替、修正を含むものである。同様に、適切な場合には、特許請求の範囲は、ここに説明した実施形態に対する、当業者が想到するだろうすべての変更、置換、変形、代替、修正を含むものである。
【００２０】
なお、本発明の一部の実施形態を整理すると以下の通りである。
（付記１）  セッションノードと前記セッションノードにリンクされた複数のリンクされたノードとを含むノードのセットのモデルにアクセスし、前記リンクされたノードは親ノードと子ノードとを含み、親ノードは１つ以上の子ノードを前記セッションノードにリンクし、子ノードは前記子ノードを前記セッションノードにリンクする１つ以上の親ノードを有する段階と、
前記ノードのセットに対して、前記セッションノードから所定リンク数内のすべてのリンクされたノードに確率を分配する確率分布を生成し、各子ノードはその親ノードの各々から前記親ノードに分配された確率の所定割合を受け取り、前記親ノードはその子ノードの各々に前記親ノードに分配された前記確率の前記所定割合を一様に分配する段階と、
前記ノードのセットのランク付けに使用するため前記確率分布を伝える段階とを有する方法。
（付記２）  前記ノードはハイパーテキスト・マークアップ・ランゲージ（ＨＴＭＬ）文書である、付記１に記載の方法。
（付記３）  前記所定数のリンクはユーザの我慢強さをモデル化したものである、付記１に記載の方法。
（付記４）  前記所定数のリンクは２つのリンクである、付記１に記載の方法。
（付記５）  前記所定割合は１／２である、付記１に記載の方法。
（付記６）  前記ノードのセットのモデルはワールド・ワイド・ウェブの少なくとも一部をモデル化するグラフを含む、付記１に記載の方法。
（付記７）  前記ランク付けは前記ノードのセットの検索を容易にして、ユーザからのクエリに対する応答を生成する、付記１に記載の方法。
（付記８）  前記セッションノードから相異なる所定リンク数内のすべてのリンクされたノードに確率を分配する、前記ノードのセットの複数の確率分布を生成する段階と、
前記確率分布を平均化する段階と、
前記ノードのセットのランク付けに使用するため平均化した前記確率分布を伝える段階とを有する、付記１に記載の方法。
（付記９）  前記セッションノードから相異なる所定リンク数内のすべてのリンクされたノードに確率を分配する、前記ノードのセットの複数の確率分布を生成する段階と、
ユーザにより指定された嗜好に基づき前記ノードのセットのランク付けに使用する前記複数の確率分布を伝える段階とをさらに有する、付記１に記載の方法。
（付記１０）  前記ノードのセットの前記確率分布を生成する段階は、一様な確率分布から始めて確率分布を反復的に計算し、生成される前記確率分布は反復的に計算された確率分布の収束の結果得られる段階を含む、付記１に記載の方法。
（付記１１）  コンピュータにより実行される、有体的媒体にエンコードされた論理であって、前記論理は実行されると、
セッションノードと前記セッションノードにリンクされた複数のリンクされたノードとを含むノードのセットのモデルにアクセスし、前記リンクされたノードは親ノードと子ノードとを含み、親ノードは１つ以上の子ノードを前記セッションノードにリンクし、子ノードは前記子ノードを前記セッションノードにリンクする１つ以上の親ノードを有する段階と、
前記ノードのセットに対して、前記セッションノードから所定リンク数内のすべてのリンクされたノードに確率を分配する確率分布を生成し、各子ノードはその親ノードの各々から前記親ノードに分配された確率の所定割合を受け取り、前記親ノードはその子ノードの各々に前記親ノードに分配された前記確率の前記所定割合を一様に分配する段階と、
前記ノードのセットのランク付けに使用するため前記確率分布を伝える段階とを実行する論理。
（付記１２）  前記ノードはハイパーテキスト・マークアップ・ランゲージ（ＨＴＭＬ）文書である、付記１１に記載の論理。
（付記１３）  前記所定数のリンクはユーザの我慢強さをモデル化したものである、付記１１に記載の論理。
（付記１４）  前記所定数のリンクは２つのリンクである、付記１１に記載の論理。
（付記１５）  前記所定割合は１／２である、付記１１に記載の論理。
（付記１６）  前記ノードのセットのモデルはワールド・ワイド・ウェブの少なくとも一部をモデル化するグラフを含む、付記１１に記載の論理。
（付記１７）  前記ランク付けは前記ノードのセットの検索を容易にして、ユーザからのクエリに対する応答を生成する、付記１１に記載の論理。
（付記１８）  実行されたとき、
前記セッションノードから相異なる所定リンク数内のすべてのリンクされたノードに確率を分配する、前記ノードのセットの複数の確率分布を生成する段階と、
前記確率分布を平均化する段階と、
前記ノードのセットのランク付けに使用するため平均化した前記確率分布を伝える段階とをさらに実行する、付記１１に記載の論理。
（付記１９）  実行されたとき、
前記セッションノードから相異なる所定リンク数内のすべてのリンクされたノードに確率を分配する、前記ノードのセットの複数の確率分布を生成する段階と、
ユーザにより指定された嗜好に基づき前記ノードのセットのランク付けに使用する前記複数の確率分布を伝える段階とをさらに実行する、付記１１に記載の論理。
（付記２０）  前記ノードのセットの前記確率分布を生成する段階は、一様な確率分布から始めて確率分布を反復的に計算し、生成される前記確率分布は反復的に計算された確率分布の収束の結果得られる段階を含む、付記１１に記載の論理。
（付記２１）  セッションノードと前記セッションノードにリンクされた複数のリンクされたノードとを含むノードのセットのモデルにアクセスし、前記リンクされたノードは親ノードと子ノードとを含み、親ノードは１つ以上の子ノードを前記セッションノードにリンクし、子ノードは前記子ノードを前記セッションノードにリンクする１つ以上の親ノードを有する手段と、
前記ノードのセットに対して、前記セッションノードから所定リンク数内のすべてのリンクされたノードに確率を分配する確率分布を生成し、各子ノードはその親ノードの各々から前記親ノードに分配された確率の所定割合を受け取り、前記親ノードはその子ノードの各々に前記親ノードに分配された前記確率の前記所定割合を一様に分配する手段と、
前記ノードのセットのランク付けに使用するため前記確率分布を伝える手段とを有するシステム。
【図面の簡単な説明】
【００２１】
【図１】ウェブページにわたるユーザの検索行動例を示す図である。
【図２】ウェブページの第１のレイヤにわたる確率分布例を示す図である。
【図３】図２に示したウェブページの第２のレイヤにわたる確率分布例を示す図である。
【図４】図２に示したウェブページの第１のレイヤと第２のレイヤとにわたる確率分布例を示す図である。
【図５】セッションベースクエリのためにノードのランク付けをするシステム例を示す図である。
【図６】セッションベースクエリのためにノードのランク付けをする方法例を示す図である。
【図１】
2008217764.tif 000007
【図２】
2008217764.tif 000008
【図３】
2008217764.tif 000009
【図４】
2008217764.tif 000010
【図５】
2008217764.tif 000011
【図６】
2008217764.tif 000012
【外国語明細書】
2008217764000001.pdf