(57)【要約】  ネットワーク上の文書に文書関連性スコアを提供する方法を開示する。ネットワーク上の文書に文書関連性スコアを提供する方法を実行するためのコンピュータ実行可能命令が格納されたコンピュータ可読媒体も開示する。さらに、ネットワーク上の文書に文書関連性スコアを提供する方法を実行するためのアプリケーションコードが含まれて成る少なくとも１つのアプリケーションモジュールを含むコンピューティングシステムを開示する。
2009505292.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上の文書をランク付けするためのコンピュータ実行可能命令が格納されたコンピュータ可読媒体であって、前記コンピュータ実行可能命令が１つまたは複数のクエリ非依存成分を含むランキング関数を利用しており、少なくとも１つのクエリ非依存成分が、ネットワーク上の各文書のバイアスクリック距離値を考慮に入れたバイアスクリック距離パラメータを含むことを特徴とするコンピュータ可読媒体。
【請求項２】
全部でＮ個の文書を含むネットワーク上のｍ個の権威文書にバイアスクリック距離値が割り当てられ、ｍが２以上、Ｎ未満であることを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項３】
割当てバイアスクリック距離値の少なくとも２つが相互に異なることを特徴とする請求項２に記載のコンピュータ可読媒体。
【請求項４】
前記ランキング関数は、ネットワーク上の各エッジのエッジ値を考慮に入れたエッジ値パラメータを含む少なくとも１つのクエリ非依存成分をさらに含み、１つまたは複数のエッジ値は１以外の数であることを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項５】
エッジ値は相互に等しく、かつ１以外の数であることを特徴とする請求項４に記載のコンピュータ可読媒体。
【請求項６】
エッジ値は相互に等しく、かつ最初に１つまたは複数の権威文書に割り当てられた最高バイアスクリック距離値以上であることを特徴とする請求項４に記載のコンピュータ可読媒体。
【請求項７】
前記少なくとも１つのクエリ非依存成分はバイアスクリック距離パラメータおよびエッジ値パラメータの両方を含むことを特徴とする請求項４に記載のコンピュータ可読媒体。
【請求項８】
前記ランキング関数によって生成されたスコアをネットワーク上の各文書に割り当てるためのコンピュータ実行可能命令をさらに含み、前記スコアが文書を昇順または降順にランク付けするために使用されることを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項９】
各文書の前記スコアは次式：
【数１】
2009505292.tif 000006
を用いて生成され、
式中、
ｗｔｆ’は加重語頻度を表し、
Ｎはネットワーク上の文書の数を表し、
ｎはクエリ語を含む文書の数を表し、
ｗcdはクエリ非依存成分の重みを表し、
ｂcdはクリック距離の重みを表し、
ｂudはＵＲＬの深さの重みを表し、
ＣＤは文書の計算クリック距離または割当てバイアスクリック距離を表し、
ｋewはエッジ重みに関連する同調定数を表し、
ＵＤはＵＲＬの深さを表し、
ｋcdおよびｋ1は定数である、
ことを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１０】
ユーザによって入力された検索問合せを受け入れ、ネットワーク上の文書に検索を実行して、多数の文書を含む検索結果を生成し、ランク付けされた検索結果を生成するランキング関数を使用して検索結果の多数の文書をランク付けし、かつランク付けされた検索結果をユーザに表示するためのコンピュータ実行可能命令をさらに含むことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項１１】
コンピューティングシステム上で使用可能な少なくとも１つのアプリケーションモジュールを含むコンピューティングシステムであって、前記少なくとも１つのアプリケーションモジュールが、請求項１に記載のコンピュータ可読媒体からロードされたアプリケーションコードを含むことを特徴とするコンピューティングシステム。
【請求項１２】
ネットワーク上の文書の文書関連性スコアを決定する方法であって、
ネットワーク上の文書の文書およびリンク情報を格納するステップと、
前記文書およびリンク情報から、文書を表すノードおよびリンクを表すエッジを含むネットワークの表現を生成するステップと、
バイアスクリック距離値を割り当てられるノードは権威ノードであり、ネットワーク上の少なくとも２つのノードにバイアスクリック距離値を割り当てるステップと、
所与の非権威ノードのクリック距離は前記所与の非権威ノードから前記所与の非権威ノードに最も近い権威ノードまで測定され、前記ネットワークの表現における非権威ノードの各々のクリック距離を算出し、前記算出ステップの結果、各文書のバイアスクリック距離値を得るステップと、
各文書の前記バイアスクリック距離値を使用して、ネットワーク上の所与の文書の文書関連性スコアを決定するステップと、
を含むことを特徴とする方法。
【請求項１３】
少なくとも２つの権威ノードが相互に異なる割当てバイアスクリック距離値を有することを特徴とする請求項１２に記載の方法。
【請求項１４】
前記表現における各エッジにエッジ値を割り当てるステップをさらに含み、前記エッジ値は１以上であることを特徴とする請求項１２に記載の方法。
【請求項１５】
各エッジ値はどの権威ノードに割り当てられた最高バイアスクリック距離値よりも大きいことを特徴とする請求項１４に記載の方法。
【請求項１６】
ネットワーク上の各文書の文書関連性スコアは次式：
【数２】
2009505292.tif 000007
を用いて生成され、
式中、
ｗｔｆ’は加重語頻度を表し、
Ｎはネットワーク上の文書の数を表し、
ｎはクエリ語を含む文書の数を表し、
ｗｃｄはクエリ非依存成分の重みを表し、
ｂｃｄはクリック距離の重みを表し、
ｂｕｄはＵＲＬの深さの重みを表し、
ＣＤは文書の計算クリック距離または割当てバイアスクリック距離を表し、
ｋｅｗはエッジ重みに関連する同調定数を表し、
ＵＤはＵＲＬの深さを表し、
ｋcdおよびｋ1は定数である、
ことを特徴とする請求項１２に記載の方法。
【請求項１７】
ネットワーク上の文書をランク付けする方法であって、
請求項１２に記載の方法を使用して、ネットワーク上の各文書の文書関連性スコアを決定するステップと、
各文書の前記文書関連性スコアに基づいて文書を降順にランク付けするステップと、
を含むことを特徴とする方法。
【請求項１８】
検索クエリの検索結果をランク付けする方法であって、
請求項１２に記載の方法を使用して、検索クエリの検索結果における各文書の文書関連性スコアを決定するステップと、
各文書の前記文書関連性スコアに基づいて文書を降順にランク付けするステップと、
を含むことを特徴とする方法。
【請求項１９】
請求項１２に記載の方法を実行するためのコンピュータ実行可能命令が格納されたことを特徴とするコンピュータ可読媒体。
【請求項２０】
コンピューティングシステム上で使用可能な少なくとも１つのアプリケーションモジュールを含むコンピューティングシステムであって、前記少なくとも１つのアプリケーションモジュールは、ネットワーク上の文書の文書関連性スコアを決定する方法を実行するためのアプリケーションコードを含み、前記方法が、
バイアスクリック距離値を割り当てられるノードは権威ノードであり、ネットワーク上の表現における少なくとも２つのノードにバイアスクリック距離値を割り当てるステップと、
所与の非権威ノードのクリック距離は前記所与の非権威ノードから前記所与の非権威ノードに最も近い権威ノードまで測定され、ネットワークの表現における各非権威ノードのクリック距離を算出し、前記算出ステップの結果、各文書のバイアスクリック距離値を得るステップと、
各文書の前記バイアスクリック距離値を使用して、ネットワーク上の所与の文書の文書関連性スコアを決定するステップと、
を含むことを特徴とするコンピューティングシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
所与の検索クエリに対する文書の関連性に従って文書をランク付けするランキング関数は公知である。公知のランキング関数を使用する検索エンジンによって生成される検索結果と比較して、所与の検索クエリに対する検索結果を改善するランキング関数を開発する努力が、当該技術分野で続いている。
【０００２】
【特許文献１】米国特許出願第１０／９５５，４６２号明細書
【特許文献２】米国特許出願第１０／８０４，３２６号明細書
【発明の開示】
【課題を解決するための手段】
【０００３】
本明細書に記載するのは、中でも特に、ネットワーク上の所与の文書の文書関連性スコアを決定するための様々な技術である。文書関連性スコアは、１つまたは複数のクエリ非依存成分を含むランキング関数を介して生成され、ここで少なくとも１つのクエリ非依存成分は、ネットワーク上の多数の文書のバイアスクリック距離値を考慮に入れた、バイアスクリック距離パラメータを含む。ランキング関数は、多数の文書の文書関連性スコアに基づいて多数の文書を順番に（一般的に降順に）ランク付けするために、検索エンジンによって使用され得る。
【０００４】
この発明の開示は、「発明を実施するための最良の形態」節で下述する厳選された１つまたは複数の概念を簡素化された形で読者に概略的に紹介するために提供するものである。この発明の開示は、特許請求する対象物の重要なおよび／または必須の特徴を特定することを意図するものではない。
【発明を実施するための最良の形態】
【０００５】
本明細書に開示する方法およびプロセスの原理の理解を容易にするために、特定の実施形態の説明を以下に示し、特定の言語を使用して特定の実施形態を説明する。それでもなお、開示する方法およびプロセスの範囲は、特定の専門用語の使用によって限定されないことを理解されたい。開示する方法およびプロセスが関係する当業者は、検討する開示の方法およびプロセスの原理の変形、さらなる変更、およびそのようなさらなる適用を普通に思いつくことが予想される。
【０００６】
ネットワーク上の文書の文書関連性スコアを決定する方法を開示する。各文書関連性スコアは、１つまたは複数のクエリ依存成分（例えば所与の検索クエリまたは検索クエリ語の特質に依存する関数成分）のみならず１つまたは複数のクエリ非依存成分（例えば所与の検索クエリまたは検索クエリ語に依存しない関数成分）をも含むランキング関数を使用して計算される。ランキング関数によって決定された文書関連性スコアは、ネットワーク空間（例えば企業イントラネット空間）内の文書を各文書関連性スコアに従ってランク付けするために、使用することができる。開示の方法を使用することのできる例示的検索プロセスを、図１に例示的プロセス１０として示す。
【０００７】
図１は、ユーザが検索クエリを入力するプロセスステップ８０から始まる例示的検索プロセス１０を示す。ステップ８０から、例示的検索プロセス１０はステップ２００に進み、そこで検索エンジンは、検索クエリの１つまたは複数の語について、ネットワーク空間内の全ての文書を検索する。ステップ２００から、例示的検索プロセス１０はステップ３００に進み、そこで検索エンジンのランキング関数は、各文書の関連性スコアに基づいてネットワーク空間内の文書をソートする。文書関連性スコアは１つまたは複数のクエリ依存成分および１つまたは複数のクエリ非依存成分に基づく。ステップ３００から、例示的検索プロセス１０はステップ４００に進み、そこでソートされた検索結果が、一般的に関連性の降順にユーザに提示され、検索クエリに最も関連性の高いネットワーク空間内の文書が識別される。
【０００８】
下でさらに詳述するように、文書関連性スコアを決定する一部の例示的方法では、文書関連性スコアを決定するために使用されるランキング関数の少なくとも１つのクエリ非依存成分は、ネットワーク空間内の各文書の「バイアスクリック距離」を考慮に入れる。本明細書でネットワーク内の「権威文書」またはウェブグラフ上の「権威ノード」とも呼ばれる特定の文書のバイアスクリック距離に対し、これらの文書を相互に対して異なる重要度を有し、かつ多分ネットワーク上の残りの文書に対してより高い重要度を有するものとして識別するために、初期クリック距離値を割り当てることができる。本明細書でネットワーク内の「非権威文書」またはウェブグラフ上の「非権威ノード」と呼ばれる残りの文書は、ネットワーク空間内の最も近い権威文書（またはウェブグラフ上の最も近い権威ノード）までのそれらの位置に基づいて算出されるバイアスクリック距離値を有し、結果的に権威ノードに向かってバイアスされたクリック距離値が得られる。
【０００９】
１つの例示的実施形態では、バイアスクリック距離値は、全部でＮ個の文書を含むネットワーク上のｍ個の権威文書に割り当てられ得る。ここでｍは２以上、Ｎ未満である。この例示的実施形態では、ネットワーク空間内である程度の重要度を有する所与のネットワーク空間内のｍ個の権威文書を、システム管理者が手動で選択するか、あるいは検索システム内のアプリケーションコードが自動的に識別する。例えば、ｍ個の権威文書の１つは、ウェブサイトのホームページ、またはウェブサイトのホームページに直接リンクされた別のページであるかもしれない。
【００１０】
別の例示的実施形態では、ｍ個の権威文書に割り当てられたバイアスクリック距離値の少なくとも２つが相互に異なる。この実施形態では、１つの権威文書の別の権威文書に対する重要度をさらに数量化するために、２以上のｍ個の権威文書に異なる数値を割り当てることができる。例えば、所与の権威文書の重要度は低いバイアスクリック距離値によって示すことができる。この実施例では、０に等しいバイアスクリック距離値を有する権威文書は、０より大きいバイアスクリック距離値を有する権威文書より重要度が高いとみなされる。
【００１１】
文書関連性スコアを決定する開示される方法はさらに、ネットワーク上の各エッジに割り当てられるエッジ値を考慮に入れるエッジ値パラメータが含まれる少なくとも１つのクエリ非依存成分を含むランキング関数を利用することができ、ここで各エッジはネットワークのハイパーリンク構造内の１つの文書を別の文書に（またはウェブグラフ上の１つのノードを別のノードに）接続する。ネットワーク上の文書を相互に接続する１つまたは複数のエッジにエッジ値を割り当てることにより、ネットワーク上の文書の文書関連性スコアに影響を及ぼすさらなる方法がもたらされる。例えば、低いバイアスクリック距離値が所与の文書の重要度を示す上述の実施例では、第１文書および第１文書にリンクされた第２文書のような２つの文書間のエッジ値が増大すると、第１文書に対する第２文書（すなわちリンクされた文書）の重要度がさらに低下する。逆に、第１文書と第２文書との間のエッジにより低いエッジ値を割り当てることにより、第１文書に対する第２文書の重要度は高くなる。
【００１２】
例示的実施形態では、ネットワーク空間内の文書をリンクする２つ以上のエッジに対し、相互に異なるエッジ値を割り当てることができる。この例示的実施形態では、ネットワーク空間内の１つの文書の別の文書に対する重要度をさらに数量化するために、２つ以上のエッジに異なる数値を割り当てることができる。他の例示的実施形態では、ネットワーク空間内の文書をリンクする全てのエッジに同一エッジ値が割り当てられ、そこで割り当てられるエッジ値は１または他の正数である。さらに別の実施形態では、エッジ値は相互に等しく、１つまたは複数の権威文書に最初に割り当てられる最高バイアスクリック距離値と等しいかそれ以上である。
【００１３】
さらになお別の例示的実施形態では、文書関連性スコアを決定する開示される方法は、上記のバイアスクリック距離パラメータおよび上記のエッジ値パラメータの両方が含まれる少なくとも１つのクエリ非依存成分を含むランキング関数を利用する。
【００１４】
文書関連性スコアは、ネットワーク空間内の文書をランク付けするために使用することができる。例えば、ネットワーク上の文書をランク付けする方法は、上記の方法を使用してネットワーク上の各文書の文書関連性スコアを決定するステップと、各文書の文書関連性スコアに基づいて文書を所望の順序で（一般的に降順に）ランク付けするステップとを含むことができる。
【００１５】
文書関連性スコアはまた、検索クエリの検索結果をランク付けするために使用することもできる。例えば、検索クエリの検索結果をランク付けする方法は、上記の方法を使用して検索クエリの検索結果における各文書の文書関連性スコアを決定するステップと、各文書の文書関連性スコアに基づいて文書を所望の順序で（一般的に降順に）ランク付けするステップとを含むことができる。
【００１６】
本明細書に開示する方法を使用するアプリケーションプログラムは、様々なハードウェア構成要素を含む様々なコンピュータシステムにロードして実行することができる。本明細書に開示する方法を実施するための例示的コンピュータシステムおよび例示的動作環境については下述する。
【００１７】
例示的動作環境
図２は、本明細書に開示する方法が実現され得る適切なコンピューティングシステム環境１００の実施例を示す。コンピューティングシステム環境１００は適切なコンピューティング環境の一実施例にすぎず、本明細書に開示する方法の使用および機能性の範囲に関する制限を示唆することを意図するものではない。また、コンピューティング環境１００は、例示的動作環境１００に示される構成要素のいずれか１つまたは組合せに関して、何らかの依存性または要件を有していると解釈すべきではない。
【００１８】
本明細書に開示する方法は、多くの他の汎用または専用コンピューティングシステム環境または構成で動作する。本明細書に開示する方法に使用するのに適し得る周知のコンピューティングシステム、環境、および／または構成の実施例として、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップ装置、マルチプロセッサシステム、マイクロプロセッサをベースとするシステム、セットトップボックス、プログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記システムまたは装置のいずれかを含む分散コンピューティング環境、および類似物が挙げられるが、それらに限定されない。
【００１９】
本明細書に開示する方法およびプロセスは、コンピュータによって実行されるプログラムモジュールのようなコンピュータ実行可能命令の一般的文脈で説明することができる。一般的に、プログラムモジュールは、特定のタスクを実行するか特定の抽象データ型を実現するルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含む。本明細書に開示する方法およびプロセスはまた、通信ネットワークを介してリンクされた遠隔処理装置によってタスクが実行され得る、分散コンピューティング環境で実施することもできる。分散コンピューティング環境では、プログラムモジュールはメモリ格納装置を含む局所および遠隔コンピュータ記憶媒体の両方に配置することができる。
【００２０】
図２に関連して、本明細書に開示する方法およびプロセスを実現するための例示的システムは、コンピュータ１１０の形の汎用コンピューティング装置を含む。コンピュータ１１０の構成要素は、処理ユニット１２０、システムメモリ１３０、およびシステムメモリ１３０をはじめそれに限らず様々なシステム構成要素を処理ユニット１２０に結合するシステムバス１２１を含むことができるが、それらに限定されない。システムバス１２１は、メモリバスまたはメモリコントローラ、周辺バス、および様々なバスアーキテクチャのいずれかを使用する局所バスを含むいくつかの型のバス構造のいずれかとすることができる。実施例として、そのようなアーキテクチャは業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、エンハンストＩＳＡ（ＥＩＳＡ）バス、Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ（ＶＥＳＡ）局所バス、およびメザニンバスとしても知られるＰｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バスを含むが、それらに限定されない。
【００２１】
コンピュータ１１０は一般的に、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体はコンピュータ１１０によってアクセスすることのできる任意の利用可能な媒体とすることができ、揮発性および不揮発性媒体、取外し可能および取外し不能な媒体の両方を含む。限定ではなく、実施例として、コンピュータ可読媒体はコンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータのような情報の格納のための任意の方法または技術によって実現される揮発性および不揮発性の取外し可能および取外し不能な媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくは他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置、もしくは他の磁気記憶装置、または所望の情報を格納するために使用することができ、かつコンピュータ１１０によってアクセスすることができる任意の他の媒体を含むが、それらに限定されない。通信媒体は一般的に、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを搬送波または他の輸送機構のような変調データ信号で具現し、任意の情報配信媒体を含む。用語「変調データ信号」とは、その特性セットを１つまたは複数有する信号、または情報を信号で符号化するようなやり方で変化した信号を意味する。限定ではなく、実施例として、通信媒体は有線ネットワークまたは直接配線接続のような有線媒体、ならびに音響、ＲＦ、赤外、および他の無線媒体のような無線媒体を含む。上記のいずれかの組合せも、本明細書で使用するコンピュータ可読媒体の範囲内に含めるべきである。
【００２２】
システムメモリ１３０は、読出し専用メモリ（ＲＯＭ）１３１およびランダムアクセスメモリ（ＲＡＭ）１３２のような揮発性および／または不揮発性メモリの形のコンピュータ記憶媒体を含む。始動中のようにコンピュータ１１０内の要素間で情報を転送するのに役立つ基本的ルーチンを含む基本的入／出力システム１３３（ＢＩＯＳ）は一般的に、ＲＯＭ１３１に格納される。ＲＡＭ１３２は一般的に、処理ユニット１２０によってすぐにアクセス可能な、かつ／または現在操作中であるデータおよび／またはプログラムモジュールを含む。限定ではなく、実施例として、図２はオペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７を示す。
【００２３】
コンピュータ１１０はまた、他の取外し可能／取外し不能な揮発性／不揮発性コンピュータ記憶媒体をも含むことがある。単なる実施例として、図２は、取外し不能な不揮発性磁気媒体に読み書きするハードディスクドライブ１４０、取外し可能な不揮発性磁気ディスク１５２に読み書きする磁気ディスクドライブ１５１、およびＣＤ  ＲＯＭもしくは他の光媒体のような取外し可能な不揮発性光ディスク１５６に読み書きする光ディスクドライブ１５５を示す。例示的動作環境で使用することのできる他の取外し可能／取外し不能な揮発性／不揮発性コンピュータ記憶媒体として、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、固体ＲＡＭ、固体ＲＯＭ、および類似物が挙げられるが、それらに限定されない。ハードディスクドライブ１４１は一般的に、インタフェース１４０のような取外し不能なメモリインタフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は一般的に、インタフェース１５０のような取外し可能なメモリインタフェースによって、システムバス１２１に接続される。
【００２４】
上述し、図２に示すドライブおよびそれらに関連付けられるコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびコンピュータ１１０用の他のデータの格納を果たす。図２で、例えばハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７を格納するように図示されている。これらの構成要素は、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同じとすることも、それらとは異なることもできることに留意されたい。オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７はここでは、最小限、それらが異なるコピーであることを示すために異なる番号が付与されている。
【００２５】
ユーザは、キーボード１６２、および一般的にマウス、トラックボール、またはタッチパッドと呼ばれるポインティング装置１６１のような入力装置を介して、コンピュータ１１０にコマンドおよび情報を入力することができる。他の入力装置（図示せず）として、マイクロフォン、ジョイスティック、ゲームパッド、パラボラアンテナ、スキャナ、または類似物を挙げることができる。これらおよび他の入力装置はしばしば、システムバス１２１に結合されたユーザ入力インタフェース１６０を介して処理ユニット１２０に接続されるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）のような他のインタフェースおよびバス構造によって接続することもできる。モニタ１９１または他の型の表示装置もまた、ビデオインタフェース１９０のようなインタフェースを介してシステムバス１２１に接続される。モニタ１９１に加えて、コンピュータ１１０は、出力周辺インタフェース１９５を介して接続され得る、スピーカ１９７およびプリンタ１９６のような他の周辺出力装置をも含むことができる。
【００２６】
コンピュータ１１０は、遠隔コンピュータ１８０のような１つまたは複数の遠隔コンピュータへの論理接続を使用して、ネットワーク環境で動作することができる。遠隔コンピュータ１８０はパーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア装置、または他の共通ネットワークノードとすることができ、図２にはメモリ記憶装置１８１だけが示されているが、一般的にコンピュータ１１０に関連して上述した要素の多くまたは全部を含む。図２に示す論理接続はローカルエリアネットワーク（ＬＡＮ）１７１およびワイドエリアネットワーク（ＷＡＮ）１７３を含むが、他のネットワークをも含むことができる。そのようなネットワーク環境は、オフィス、企業規模コンピュータネットワーク、イントラネット、およびインターネットで一般的である。
【００２７】
ＬＡＮネットワーク環境で使用される場合、コンピュータ１１０はネットワークインタフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーク環境で使用される場合、コンピュータ１１０は一般的に、インターネットのようなＷＡＮ１７３での通信を確立するためのモデム１７２または他の手段を含む。内部または外部に置くことのできるモデム１７２は、ユーザ入力インタフェース１６０または他の適切な機構を介して、システムバス１２１に接続することができる。ネットワーク環境では、コンピュータ１１０に関連して図示したプログラムモジュール、またはその一部分は、遠隔メモリ記憶装置に格納することができる。限定ではなく、実施例として、図２はメモリ装置１８１上に常駐する遠隔アプリケーションプログラム１８５を示す。図示するネットワーク接続は例示であって、コンピュータ間の通信リンクを確立する他の手段を使用することができることは理解されるであろう。
【００２８】
本明細書に開示する方法およびプロセスは、検索ランキングアプリケーションを含め、それに限定せず、１つまたは複数のアプリケーションプログラムを使用して実現することができ、それは例示的システム１００でアプリケーションプログラム１３５、アプリケーションプログラム１４５、および遠隔アプリケーションプログラム１８５と指定された多数のアプリケーションプログラムの１つとすることができる。
【００２９】
上述の通り、所与の文書の文書関連性スコアを生成する開示の方法は、ハンドヘルド装置、マルチプロセッサシステム、マイクロプロセッサベースまたはプログラム可能な家庭用電化製品、ネットワークされたパーソナルコンピュータ、ミニコンピュータ、メインフレームコンピュータ、および類似物を含め、他のコンピュータシステム構成で実現することができることを当業者は理解されるであろう。所与の文書の文書関連性スコアを生成する開示の方法は、タスクが通信ネットワークを介してリンクされた遠隔処理装置によって実行される分散コンピューティング環境で実施することもできる。分散コンピューティング環境で、プログラムモジュールは局所および遠隔メモリ記憶装置の両方に配置することができる。
【００３０】
例示的実施形態の実現
上述の通り、ネットワーク上の文書の文書関連性スコアを決定する方法を提供する。開示する方法は、（i）ネットワーク上の各文書のバイアスクリック距離値を考慮に入れるランキング関数、（ii）ネットワーク上の文書間のエッジ（またはリンク）に割り当てられた１つまたは複数のエッジ値を考慮に入れるランキング関数、または（iii）（i）および（ii）の両方を利用して、ネットワーク上の文書をランク付けすることができる。
【００３１】
ネットワーク上の文書の文書関連性スコアを決定する開示の方法は、いくつかのステップを含むことができる。１つの例示的実施形態では、ネットワーク上の文書の文書関連性スコアを決定する方法は、文書およびネットワーク上の文書のリンク情報を格納するステップと、文書およびリンク情報からネットワークの表現を生成するステップと、ここでネットワークの表現は文書を表すノードおよびリンクを表すエッジを含み、ネットワーク上の少なくとも２つのノードにバイアスクリック距離値（ＣＤA）を割り当てるステップと、ここでバイアスクリック距離値を割り当てられるノードは権威ノードであり、ネットワークの表現における非権威ノードの各々に対するバイアスクリック距離を算出するステップと、ここで所与の非権威ノードのバイアスクリック距離は所与の非権威ノードから該所与の非権威ノードに最も近い権威ノードまで測定され、ここで算出ステップは結果的に各非権威文書に対して算出されたバイアスクリック距離値（ＣＤC）を生じ、各文書のバイアスクリック距離値（すなわち（ＣＤAまたはＣＤC）を使用してネットワーク上の所与の文書の文書関連性スコアを決定するステップとを含む。
【００３２】
文書およびネットワーク上の文書のリンク情報を格納するステップは、コンピューティングシステムに共通して見出されるアプリケーションコードのインデックス処理によって実行され得る。アプリケーションコードのインデックス処理により、文書およびリンク情報からネットワークの表現が生成され、ここでネットワークの表現は、文書を表すノード、およびリンクを表すエッジを含む。そのようなネットワークの表現は一般的に「ウェブグラフ」と呼ばれる。ウェブグラフを生成する１つの例示的方法は、リンクおよびアンカテキスト情報が収集され、アンカの特定のターゲット文書に帰属されるプロセスによって収集されるデータを使用することを含む。このプロセスおよびアンカテキストの概念は、２００４年８月３０日出願の（例えば、特許文献１参照。）、名称「SYSTEM AND METHOD FOR INCORPORATING ANCHOR TEXT INTO RANKING SEARCH RESULTS」により詳細に記載されており、その対象物全体を参照によって本明細書に援用する。
【００３３】
図３は、ネットワーク空間内の文書、および文書間のリンクを識別する例示的ウェブグラフを示す。図３に示す通り、例示的ウェブグラフ３０は、所与のネットワーク空間（例えば企業イントラネット）内の各文書を表すノード３１、および所与のネットワーク空間内の文書間のリンクを表すエッジ３２を含む。例示的ウェブグラフ３０は所与のネットワーク空間の過度に単純化された表現であることを理解されたい。一般的に、所与のネットワーク空間は数百、数千、または数百万の文書、および文書を相互に接続する数百、数千、または数百万のリンクを含むことができる。さらに、例示的ウェブグラフ３０は所与のノード（例えば中心ノード３３）に接続された最高８個のリンクを示しているが、実際のネットワークセッティングでは、所与のノードは、ノード（例えば文書）をネットワーク内の数百の他の文書に接続する数百のリンクを有するかもしれないことを理解されたい（例えばネットワークのホームページは、ネットワーク内の全てのページにリンクすることができる）。
【００３４】
加えて、例示的ウェブグラフ３０はごく少数のサイクルを示す（例えば第１ノードが第２ノードにリンクし、それが追加ノードにリンクすることができ、第２ノードまたは追加ノードの１つが第１ノードに回帰リンクする）。１つのそのようなサイクルは、図３にノード４１および４２によって表される。端部ノード４０のいずれかが図３に示すいずれかの他のノード、例えば中心ノード３３に回帰リンクされる場合、他のサイクルを表すことができる。所与のウェブグラフの単純さまたは複雑さに関係なく、所与の文書の文書関連性スコアを生成する開示の方法は、サイクルを含むものをはじめ、どんなウェブグラフでも使用することができる。
【００３５】
ウェブグラフが生成された後、１つまたは複数の技術を使用して、ウェブグラフのノードによって表されたネットワーク空間内の１つまたは複数の文書の相対的重要度に影響を及ぼすことができる。上述し、かつ下述する通り、これらの技術は、（i）２つ以上のノードを権威ノードと指定すること、（ii）権威ノードの各々にバイアスクリック距離値（ＣＤA）を割り当てること、（i）任意選択的に、相互に異なる２つ以上のバイアスクリック距離値（ＣＤA）を割り当てること、（iｖ）ウェブグラフの各エッジにエッジ値を割り当てること、（ｖ）任意選択的に、ウェブグラフの各エッジに、最大または最高割当てバイアスクリック距離値（ＣＤAmax）より大きい最小エッジ値を割り当てること、（ｖi）任意選択的に、相互に異なる２つ以上のエッジ値を割り当てること、（ｖii）各非権威ノードのバイアスクリック距離値（ＣＤC）を算出すること、および（ｖiii）任意選択的に、バイアスクリック距離値を使用した検査クエリが無関係の検索結果を生成した場合、必要に応じて、バイアスクリック距離値（ＣＤAまたはＣＤC）のいずれかの評価を下げることを含むが、それらに限定されない。例示的ウェブグラフ３０によって表されるネットワーク内の１つまたは複数の文書のバイアスクリック距離値に影響を及ぼすための上記の例示的技術の一部は、図３に示される。
【００３６】
例示的ウェブグラフ３０では、矩形の形状を有するノード３１はネットワーク内の権威ノードを識別するために使用される一方、円形の形状を有するノード３１は、非権威ノードを識別するために使用される。ネットワーク空間内の文書の総数、およびネットワーク空間内の「重要な」文書数を含め、それらに限らず、因子の個数に応じて、所与のウェブグラフ内の任意の個数のノードを権威ノードと指定することができることを理解されたい。例示的ウェブグラフ３０では、１０４個のノードのうちの９個が権威ノードと指定される（すなわち１０４の文書のうちの９個が特に重要であることを表す）。
【００３７】
さらに、例示的ウェブグラフ３０には示されないが、各対のノード３１間の各エッジ３２は、それに関連付けられるエッジ加重を有する。一般的に、各エッジ３２は１のデフォルトエッジ加重を有する。しかし、上述の通り、１以外のエッジ加重を各エッジ３２に割り当てることができる。さらに、一部の実施形態では、２つ以上の異なるエッジ加重を、同じウェブグラフ内のエッジに割り当てることができる。図３で、例示的ウェブグラフ３０に示される文字ｐ、ｑ、ｒ、ｓ、およびｔは、いくつかのエッジ３２のエッジ値を示すために使用されている。上述の通り、エッジ値ｐ、ｑ、ｒ、ｓ、およびｔは１の値、１以外の値、および／または例示的ウェブグラフ３０内のノード３１のバイアスクリック距離値にさらに影響を及ぼすために相互に異なる値を持つことができる。一般的に、ｐ、ｑ、ｒ、ｓ、およびｔのエッジ値のみならず、例示的ウェブグラフ３０の他のエッジも同数であり、一般的に１以上である。一部の実施形態では、ｐ、ｑ、ｒ、ｓ、およびｔのエッジ値のみならず、例示的ウェブグラフ３０の他のエッジも同数であり、権威ノードに割り当てられた最高バイアスクリック距離値に等しいかそれより大きい。
【００３８】
ネットワーク上の文書のバイアスクリック距離値に影響を及ぼすためにウェブグラフを変更すべく使用される１つまたは複数の技術は、システム管理者が手動で始動して実行することができる。システム管理者は所与のウェブグラフを見て、上述の通りネットワーク空間内の１つまたは複数の文書の相対的重要度を増減するように、必要に応じてウェブグラフを編集することができる。検索クエリを実行することのできるコンピューティングシステム内のアプリケーションコードのようなアプリケーションコードは、上記技術の１つまたは複数を使用して（例えば各非権威ノードのバイアスクリック距離値（ＣＤC）を算出して）ウェブグラフのバイアスを自動的に生成することができる。
【００３９】
図４Ａ〜４Ｂは、ウェブグラフ上のノードのバイアスクリック距離値を割り当て、かつ生成し、その後にシステム管理者によって任意選択的に評価を下げる手順が続く例示的方法の例示的ステップを示す論理流れ図を表す。図４Ａに示す通り、例示的方法４０１はブロック４０２から始まり、ステップ４０３に進む。ステップ４０３で、ネットワーク空間内の全部でＮ個のノード（またはＵＲＬ）からある個数の権威ノード（またはＵＲＬ）が選択される。例示的方法４０１では、ｍ個の権威ノード（またはＵＲＬ）が選択され、ここでｍは２以上である。権威ノード（またはＵＲＬ）が選択されると、例示的方法４０１は決定ブロック４０４に進む。
【００４０】
決定ブロック４０４で、ｍ個の権威ノード（またはＵＲＬ）のうちの２つ以上に対し、少なくとも２つの異なるバイアスクリック距離値（ＣＤA）を割り当てるかどうかの決定がシステム管理者によって行われる。ｍ個の権威ノード（またはＵＲＬ）のうちの２つ以上に少なくとも２つの異なるバイアスクリック距離値（ＣＤA）を割り当てることが決定された場合、例示的方法４０１はステップ４０５に進み、そこで少なくとも２つの異なるバイアスクリック距離値（ＣＤA）がｍ個の権威ノード（またはＵＲＬ）のうちの２つ以上に割り当てられる。例えば、図３に示す例示的ウェブグラフ３０に関連して、権威ノード３３および３４には０のバイアスクリック距離値を割り当てることができ、権威ノード３５および３６には＋３のバイアスクリック距離値を割り当てることができ、権威ノード４８には＋２のバイアスクリック距離値を割り当てることができる。ステップ４０５から、例示的方法４０１は決定ブロック４０７に進む。
【００４１】
決定ブロック４０４に戻って、ｍ個の権威ノード（またはＵＲＬ）のうちの２つ以上に対し少なくとも２つの異なるバイアスクリック距離値（ＣＤA）を割り当てないことが決定された場合、例示的方法４０１はステップ４０６に進み、そこで同一のバイアスクリック距離値（ＣＤA）がｍ個の権威ノード（またはＵＲＬ）の各々に割り当てられる。例えば、図３の例示的ウェブグラフ３０を再び参照すると、各々の権威ノードに０、＋２、または＋５のようなバイアスクリック距離値を割り当てることができる。ステップ４０６から、例示的方法４０１は決定ブロック４０７に進む。
【００４２】
決定ブロック４０７で、１以外のエッジ加重をウェブグラフの１つまたは複数のエッジに割り当てるかどうかの決定が、システム管理者またはアプリケーションコードによって行われる。１以外のエッジ加重をウェブグラフの１つまたは複数のエッジに割り当てることが決定された場合、例示的方法４０１は決定ブロック４０８に進む。決定ブロック４０８で、ウェブグラフのエッジに最小エッジ値を割り当てるかどうかの決定がシステム管理者によって行われる。ここで最小エッジ値は、最大割当てバイアスクリック距離値（ＣＤAmax）より大きい。最大割当てバイアスクリック距離値（ＣＤAmax）より大きい最小エッジ値をウェブグラフのエッジに割り当てることが決定された場合、例示的方法４０１はステップ４０９に進み、そこで最大割当てバイアスクリック距離値（ＣＤAmax）より大きい最小エッジ値がウェブグラフの各エッジに割り当てられる。例えば、図３に示す例示的ウェブグラフ３０に関連して、権威ノード３３に最大バイアスクリック距離値（ＣＤAmax）が割り当てられ、ＣＤAmaxが＋３に等しい場合、＋３より大きい最小エッジ値は、図３に示す各エッジ３２に割り当てられる。
【００４３】
一部の実施形態では、最大割当てバイアスクリック距離値（ＣＤAmax）より大きい最小エッジ値をウェブグラフの各エッジに割り当てることは、多少の利点を有するかもしれない。この実施形態では、そのような技術は、各権威ノード（または文書もしくはＵＲＬ）の割当てバイアスクリック距離値（ＣＤA）が、ウェブグラフ内の全ての非権威ノード（または文書もしくはＵＲＬ）の計算バイアスクリック距離値（ＣＤC）より小さくなることを保証する。文書の重要度がより低いバイアスクリック距離値に基づく場合、そのような技術は、全ての権威ノード（または文書もしくはＵＲＬ）をウェブグラフ内の非権威ノード（または文書もしくはＵＲＬ）より重要であるとみなすことを可能にする。
【００４４】
ステップ４０９から、例示的方法４０１は、図４Ｂに示し、かつ下述する決定ブロック４１０に進む。決定ブロック４０８に戻って、最大割当てバイアスクリック距離値（ＣＤAmax）より大きい最小エッジ値を各エッジに割り当てないことが決定された場合、例示的方法４０１は、図４Ｂに示し、かつ下述する決定ブロック４１０に直接進む。この実施形態では、非権威ノードが権威ノードより小さいバイアスクリック距離値を有すること（すなわち権威ノードより重要であるとみなされ、ここで文書の重要度はより低いバイアスクリック距離値に基づくこと）が可能である。例えば、図３の例示的ウェブグラフ３０を参照して、権威ノード３４に＋３のバイアスクリック距離値が割り当てられ、権威ノード４８に０のバイアスクリック距離値が割り当てられ、エッジ値ｓが＋１である場合、非権威ノード３９は＋１の計算バイアスクリック距離値（すなわち最も近い権威ノード４８の割当てバイアスクリック距離値０とエッジ値ｓ＋１の和）を有する。
【００４５】
図４Ｂに示す決定ブロック４１０で、少なくとも２つの異なるエッジ値をウェブグラフの２つ以上のエッジに割り当てるかどうかの決定が、システム管理者によって行われる。少なくとも２つの異なるエッジ値をウェブグラフの２つ以上のエッジに割り当てることが決定された場合、例示的方法４０１はステップ４１１に進み、そこで少なくとも２つの異なるエッジ値がウェブグラフの２つ以上のエッジに割り当てられる。例えば、図３に示す例示的ウェブグラフ３０に関連して、エッジ値ｐ、ｑ、ｒ、ｓ、およびｔのいずれか２つに少なくとも２つの異なる数を割り当てることができる。ステップ４１１から、例示的方法４０１は下述するステップ４１４に進む。
【００４６】
決定ブロック４１０に戻って、少なくとも２つの異なるエッジ値をウェブグラフの２つ以上のエッジに割り当てないことが決定された場合、例示的方法４０１はステップ４１２に進み、そこで同じエッジ値がウェブグラフの各エッジに割り当てられ、エッジ値は１以外の値である。例えば、図３に示す例示的ウェブグラフ３０に関連して、エッジ値ｐ、ｑ、ｒ、ｓ、およびｔの各々に１以外の同じ数が割り当てられる。ステップ４１２から、例示的方法４０１は下述するステップ４１４に進む。
【００４７】
図４Ａに示す決定ブロック４０７に戻って、エッジ加重をウェブグラフの１つまたは複数のエッジに割り当てないことが決定された場合、例示的方法４０１はステップ４１３に進み、そこで、ウェブグラフのエッジが計算バイアスクリック距離値に対して最小限の影響を持つように、ウェブグラフの各エッジにデフォルトエッジ値（例えば＋１）が使用される。この実施形態では、権威ノードの個数および位置のような因子は、計算バイアスクリック距離値に対し、デフォルトエッジ値より大きい影響を持つ。ステップ４１３から、例示的方法４０１は図４Ｂに示すステップ４１４に進む。
【００４８】
ステップ４１４で、非権威ノード（または文書もしくはＵＲＬ）のバイアスクリック距離値（ＣＤC）が算出される。下でさらに詳述する通り、権威ノードに直接リンクされた所与のターゲットノード（すなわち非権威ノード）のバイアスクリック距離値（ＣＤCtarget）は、次の公式を用いて算出することができる。
ＣＤCtarget＝ｍｉｎ（ＣＤAclosest＋ＥｄｇｅＷｅｉｇｈｔ）
ここで、ＣＤAclosestはターゲットノードに最も近い権威ノードに対する割当てバイアスクリック距離値を表し、ＥｄｇｅＷｅｉｇｈｔ（ここではＥｄｇｅＶａｌｕｅとも呼ばれる）は、ターゲットノードに最も近い権威ノードをリンクするエッジに割り当てられたエッジ値またはエッジ加重を表す。ｍｉｎ（ｘ）関数は、例えばノードが２つの権威ノードに直接リンクされている場合に、最小計算バイアスクリック距離値が所与のノードに使用されることを指摘するために使用される。権威ノードに直接リンクされているもの以外の所与のターゲットノード（すなわち非権威ノード）のバイアスクリック距離値（ＣＤCtarget）は、次の公式を用いて算出することができる。
ＣＤCtarget＝ｍｉｎ（ＣＤCmin＋ＥｄｇｅＷｅｉｇｈｔ）
ここで、ＣＤCminは最低計算バイアスクリック距離値を有する隣接ノードの計算バイアスクリック距離値を表し、ＥｄｇｅＷｅｉｇｈｔは、最低計算バイアスクリック距離値を有する隣接ノードおよびターゲットノードをリンクするエッジに割り当てられたエッジ値またはエッジ加重を表す。ステップ４１４から、例示的方法４０１はステップ４１５に進む。
【００４９】
ステップ４１５で、結果的に得られたバイアスクリック距離の割当て値（ＣＤA）および計算値（ＣＤC）は、システム管理者によって検査される。一般的にシステム管理者は、結果的に得られたバイアスクリック距離値（割当て値（ＣＤA）および計算値（ＣＤC））を使用して１つまたは複数の検索クエリを実行することによって、システムを検査する。システム管理者は、明らかに無関係の内容が返ってきたことに気付いた場合、上記のバイアスツール／技術を使用して、無関係の内容を生成した１つまたは複数のサイト、例えばアーカイブフォルダまたはウェブサイトの評価を下げることができる。上記の検査は、システム管理者が、（ｉ）ネットワーク空間内の所与の文書の実際の重要度と、（ｉｉ）バイアスクリック距離値によって示される文書の重要度との間に起こり得る矛盾について、バイアスクリック距離値を評価することを可能にする。ステップ４１５から、例示的方法４０１は決定ブロック４１６に進む。
【００５０】
決定ブロック４１６で、ネットワーク空間内の所与の文書の重要度をより厳密に表すために、いずれかのバイアスクリック距離値の評価を下げるかどうかが、システム管理者によって決定される。ネットワーク空間内の１つまたは複数の文書の重要度をより厳密に表すために、１つまたは複数のバイアスクリック距離値の評価を下げることが決定された場合、例示的方法４０１はステップ４１７に進み、そこで１つまたは複数の文書（またはＵＲＬ）のバイアスクリック距離値が、プラスまたはマイナスに調整される。ステップ４１７から、例示的方法４０１はステップ４１８に進む。
【００５１】
決定ブロック４１６に戻って、ネットワーク空間内の１つまたは複数の文書の重要度をより厳密に表すために、１つまたは複数のバイアスクリック距離値の評価を下げないことが決定された場合、例示的方法４０１はステップ４１８に直接進む。ステップ４１８で、権威ノードに割り当てられたバイアスクリック距離値および非権威ノードに対して算出されたバイアスクリック距離値がランキング関数で利用され、ネットワーク空間内の各文書の全体的文書関連性スコアが決定される。ステップ４１８から、例示的方法４０１は終了ブロック４１９に進む。
【００５２】
上述の通り、ウェブグラフ上の非権威ノード（またはＵＲＬ）のバイアスクリック距離値（ＣＤC）は、「ターゲットノード」とも呼ばれる所与の非権威ノード（またはＵＲＬ）と、最も近い権威ノード（またはＵＲＬ）との間の最短距離に基づいて算出される。ネットワーク空間内の非権威ＵＲＬのバイアスクリック距離値（ＣＤC）を算出するための１つの例示的プロセスを図５Ａ〜５Ｂに示す。
【００５３】
図５Ａ〜５Ｂは、ネットワーク空間内の非権威ノード（またはＵＲＬ）のバイアスクリック距離値（ＣＤC）を算出するための１つの例示的プロセス４０の論理流れ図を示す。例示的プロセス４０はブロック４１４０から開始され、ステップ４１４１に進み、そこで、（ｉ）割当てバイアスクリック距離値（ＣＤA）を持つ権威ノード、（ｉｉ）非権威ノード、（ｉｉｉ）ノード間のリンク、および（ｉｖ）各リンクのエッジ値を含むウェブグラフが、データベースからメモリにロードされる（例えば図３の例示的ウェブグラフ３０を参照されたい）。ウェブグラフは以前には、上述したようにインデックス処理手順を用いて生成することがあった。ステップ４１４１から、例示的プロセス４０はステップ４１４２に進む。
【００５４】
ステップ４１４２で、非権威ノードのバイアスクリック距離値（ＣＤC）は、無限大のような最大バイアスクリック距離値に初期化される。無限大のような最大バイアスクリック距離値を非権威ノードに割り当てることにより、バイアスクリック距離値（ＣＤC）を算出する必要のあるノードが識別される。最大バイアスクリック距離値の初期化が完了すると、例示的プロセス４０はステップ４１４３に進む。
【００５５】
ステップ４１４３で、ｍ個の権威ノードが待ち行列に挿入される。待ち行列に挿入されるｍ個の権威ノードは、システム管理者または何らかの他のシステム決定者によって予め定められた、ネットワーク空間のｍ個の最高権威ノードに対応する。ｍ個の権威ノードが待ち行列に追加されると、例示的プロセス４０は決定ブロック４１４４に進む。
【００５６】
決定ブロック４１４４で、待ち行列が空であるかどうかの決定が、アプリケーションコードによって行われる。空の待ち行列は、ウェブグラフの全てのノードが、（ｉ）割当てバイアスクリック距離値（ＣＤA)をすでに得たか、それとも（ｉｉ）算出されたバイアスクリック距離値（ＣＤC）を有しているか、いずれかであることを意味する。待ち行列が空である場合、例示的プロセス４０は終了ブロック４１４５に進み、そこで例示的プロセス４０は終了する。しかし、待ち行列が空でない場合、例示的プロセス４０はステップ４１４６に続く。
【００５７】
ステップ４１４６で、最小バイアスクリック距離値（すなわちＣＤAまたはＣＤC）を有するノードが待ち行列から取り出される。このノードをここでは「現在のノード」と呼ぶ。例示的プロセス４０の１回目の繰返し中は、最小割当てバイアスクリック距離値（すなわちＣＤAmin）を有する権威ノードが現在のノードである。例示的プロセス４０のその後の繰返し中に、最小バイアスクリック距離値を有するノードは、権威ノードまたは非権威ノードになり得る。例示的プロセス４０の最後の繰返し中に、最小割当てバイアスクリック距離値を有するノードは一般的に非権威ノードになる。最小バイアスクリック距離値（すなわちＣＤAまたはＣＤC）を有するノードが待ち行列から取り出されると、例示的プロセス４０は決定ブロック４１４７に進む。
【００５８】
決定ブロック４１４７で、現在のノードがターゲットノードを有するかどうかについての決定が、アプリケーションコードによって行われる。本明細書で使用する場合、用語「ターゲットノード（単数形）」または「ターゲットノード（複数形）」は、現在のノードにリンクされた１つまたは複数のノードを指す。現在のノードがターゲットノードを持たない場合、例示的プロセス４０は決定ブロック４１４４に戻って、再び待ち行列が空であるかどうかを決定し、次いで上述の通り進む。しかし、現在のノードが１つまたは複数のターゲットノードを有する場合、例示的プロセス４０はステップ４１４８に進む。
【００５９】
ステップ４１４８で、現在のノードに関連付けられたターゲットノードがウェブグラフから検索され、評価される。例えば、図３の例示的ウェブグラフ３０に関連して、権威ノード４８が現在のノード（すなわち最小バイアスクリック距離値を有するノード）である場合、非権威ノード３９のいずれか１つがターゲットノード（すなわち権威ノード４８にリンクされ、かつ無限大に設定された初期バイアスクリック距離値を有するノード）であり得る。現在のノードおよびターゲットノードが選択されると、例示的プロセス４０は決定ブロック４１４９に進む。
【００６０】
決定ブロック４１４９で、ターゲットノードのバイアスクリック距離値に関連付けられたクリック距離が、現在のノードのバイアスクリック距離値と、現在のノードをターゲットノードに接続するエッジのエッジ加重値とを足した値より大きいかどうかについての決定が、アプリケーションコードによって行われる。ターゲットノードのバイアスクリック距離値が、現在のノードのバイアスクリック距離値と、現在のノードをターゲットノードに接続するエッジのエッジ加重値とを足した値より大きいことが決定された場合、例示的プロセス４０はステップ４１５０（図５Ｂに示す）に進み、そこでターゲットノードのバイアスクリック距離値が、現在のノードのバイアスクリック距離値と、現在のノードをターゲットノードに接続するエッジのエッジ加重値とを足した値に等しくなるように更新される。
【００６１】
例示的プロセス４０の１回目の繰返し中に、全てのターゲットノードは、無限大に設定された初期ターゲットノードバイアスクリック距離値を有する。その結果、例示的プロセス４０はステップ４１５０に進み、そこでターゲットノードのバイアスクリック距離値が上述の通り更新される。しかし、例示的プロセス４０のその後の繰返しで、選択されたターゲットノードは、例えば無限大に設定された初期ターゲットノードバイアスクリック距離値を有することができ（例示的プロセス４０はステップ４１５０に進む）、またはシステム管理者によって以前に設定されたバイアスクリック距離値を持つことができる（例えばターゲットノードは権威ノードである）。ステップ４１５０から、例示的プロセス４０はステップ４１５１に進む。
【００６２】
ステップ４１５１で、現在のノードおよび更新されたターゲットノードのバイアスクリック距離値を持つターゲットノードは両方とも、待ち行列に追加される。ステップ４１５０から、例示的プロセス４０は決定ブロック４１４６に戻り（図５Ａに示す）、上述の通り続行される。
【００６３】
決定ブロック４１４９に戻って（図５Ａに示す）、ターゲットノードのバイアスクリック距離値が、現在のノードのバイアスクリック距離値と、現在のノードをターゲットノードに接続するエッジのエッジ加重値とを足した値より大きくないと決定された場合、（ｉ）ターゲットノードはその計算ターゲットノードバイアスクリック距離値を維持し、（ｉｉ）ターゲットノードは待ち行列の外に維持され、かつ（ｉｉｉ）例示的プロセス４０は決定ブロック４１４７（図５Ａに示す）に戻り、そこで現在のノードが他のターゲットノードを有するかどうかの決定が行われる。現在のノードが別のターゲットノードを持たないと決定された場合、例示的プロセス４０は決定ブロック４１４４に戻り、上述の通り続行される。現在のノードが別のターゲットノードを有することが決定された場合、例示的プロセス４０はステップ４１４８に進み、上述の通り続行される。
【００６４】
例示的プロセス４０がステップ４１４８に戻ると、現在のノードに関連付けられた別のターゲットノードが選択され、上述の通り評価される。選択されたターゲットノードが前に選択されていない場合、ターゲットノードは無限大に設定された初期バイアスクリック距離値を有し、例示的プロセス４０は上述の通りステップ４１５０に進む。
【００６５】
ウェブグラフ上の全てのノードにバイアスクリック距離値を提供する上記の例示的方法は、バイアスクリック距離値が、現在のノードのバイアスクリック距離値と、ターゲットノードを現在のノードにリンクするエッジのエッジ値とを足した和より低い場合に、所与のターゲットノードのバイアスクリック距離値が変更されることを防止する。
【００６６】
所与のウェブグラフの全てのノードを決定し、希望に応じて任意選択的に評価を下げた（または任意選択的に評価を上げた）後、各文書の文書関連性スコアを提供するために、各文書のバイアスクリック距離値をランキング関数のパラメータとして使用することができる。そのような文書関連性スコアは、検索クエリの検索結果をランク付けするために使用することができる。バイアスクリック距離値パラメータを含むランキング関数を使用して生成される検索結果をランク付けする例示的方法を図６に示す。
【００６７】
図６は、例示的方法２０の例示的ステップを示す論理流れ図を提示する。ここで、例示的方法２０は、バイアスクリック距離値パラメータを含むランキング関数を使用して生成される検索結果をランク付けする方法を含む。図６に示す通り、例示的方法２０はブロック２０１から開始され、ステップ２０２に進む。ステップ２０２で、ユーザは、検索クエリを入力することによって検索を要求する。ステップ２０２の前に、ネットワーク上の文書の各々に対するバイアスクリック距離値が事前に算出されている。ステップ２０２から、例示的方法２０はステップ２０３に進む。
【００６８】
ステップ２０３で、ネットワーク上の各文書のバイアスクリック距離値は、インデックスに格納された各文書に対し、いずれかの他の文書統計（例えばクエリ非依存統計）と併合される。バイアスクリック距離値を他の文書統計と併合することにより、ランク付けに関係する全ての情報が１つにクラスタ化されるので、より高速のクエリ応答時間が得られる。したがって、インデックスにリストされる各文書は、併合後の関連バイアスクリック距離値を有する。併合が完了すると、例示的方法２０はステップ２０４に進む。
【００６９】
ステップ２０４で、バイアスクリック距離値を含む、所与の文書のクエリ非依存文書統計が、ランキング関数の成分として提供される。所与の文書についてクエリ依存データもまた、一般的にランキング関数の別個の成分として提供される。ランキング関数のクエリ依存データまたは内容関連部分は、実際の検索語および所与の文書の内容に依存する。
【００７０】
１つの実施形態では、ランキング関数は、次のように、少なくとも１つのクエリ依存（ＱＤ）成分および少なくとも１つのクエリ非依存（ＱＩＤ）成分の和を含む。
【００７１】
スコア＝ＱＤ（ｄｏｃ，ｑｕｅｒｙ）＋ＱＩＤ（ｄｏｃ）
ＱＤ成分は任意の文書スコアリング関数とすることができる。１つの実施形態では、ＱＤ成分は、２００４年３月１８日出願の（例えば、特許文献２参照。）、名称「FIELD WEIGHTING IN TEXT DOCUMENT SEARCHING」に記載されたフィールド加重スコアリング関数に対応し、該文献の対象物全体を参照によって本明細書に援用する。（例えば、特許文献２参照。）に提示される通り、フィールド加重スコアリング関数の代表として使用することのできる１つの方程式は次の通りである。
【００７２】
【数１】
2009505292.tif 000003
【００７３】
式中、
ｗｔｆ’は、加重語頻度、すなわち検索クエリ中の所与の語の語頻度に全てのフィールド（例えば文書のタイトル、本文等）をまたぐ加重を乗算し、各フィールドの長さおよび対応する平均長さに従って正規化した値の和を表す。
【００７４】
Ｎは、ネットワーク上の文書の数を表す。
【００７５】
ｎは、クエリ語を含む文書の数を表す。
【００７６】
ｋ1は、調整可能な定数である。
上記の項および方程式については、（例えば、特許文献２参照。）にさらに詳述されており、その対象物全体を参照によって本明細書に援用する。
【００７７】
ＱＩＤ成分は、所与の文書のバイアスクリック距離値および他の文書統計（ＵＲＬの深さ）の任意の変形とすることができる。１つの実施形態では、ＱＩＤ成分は次の関数を含む。
【００７８】
【数２】
2009505292.tif 000004
【００７９】
式中、
ｗｃｄは、バイアスクリック距離パラメータを含む成分のようなクエリ非依存成分の重みを表す。
【００８０】
ｂｃｄは、ＵＲＬの深さに対するバイアスクリック距離の重みを表す。
【００８１】
ｂｕｄは、ＵＲＬの深さの重みを表す。
【００８２】
ＣＤは、文書の計算クリック距離または割当てバイアスクリック距離を表す。
【００８３】
ｋｅｗは、他の同調パラメータと同様の、ランキング関数の精度を最適化することによって決定される同調定数を表す（すなわちｋｅｗは、全てのエッジが同一エッジ加重値を有する場合のエッジ加重値を表し、あるいはｋｅｗは、エッジ加重値が相互に異なる場合の平均エッジ値を表すことができる）。
【００８４】
ＵＤはＵＲＬの深さを表す。
【００８５】
ｋｃｄは、バイアスクリック距離飽和定数である。
【００８６】
加重項（ｗｃｄ、ｂｃｄ、およびｂｕｄ）は、それらの関連項（すなわちバイアスクリック距離パラメータ、所与の文書のバイアスクリック距離値、および所与の文書のＵＲＬの深さをそれぞれ含む成分）の各々の重要度、および最終的にスコアリング関数の結果を規定するのに役立つ。
【００８７】
ＵＲＬの深さ（ＵＤ）は、バイアスクリック距離値がスコアリング関数に対して持つことができる影響を平滑化するために、上記クエリ非依存成分に任意選択的に追加される。例えば、場合によっては、あまり重要でない（すなわち大きいＵＲＬの深さを有する）文書が短いバイアスクリック距離値を持つことがある。ＵＲＬの深さは、文書のＵＲＬにおけるスラッシュの数によって表される。例えばwww.example.com/d1/d2/d3/d4.htmは４つのスラッシュを含み、したがって４のＵＲＬの深さを有する。しかし、この文書はメインページwww.example.comから直接リンクを有し、比較的低いバイアスクリック距離値をもたらすかもしれない。上記関数にＵＲＬの深さの項を含め、ＵＲＬの深さの項をバイアスクリック距離値に対して加重することにより、比較的高いバイアスクリック距離値が補償され、ネットワーク内の文書の重要度がより正確に反映される。ネットワークによっては、３以上のＵＲＬの深さはかなり深いリンクとみなされるかもしれない。
【００８８】
１つの実施形態では、所与の文書の文書関連性スコアを決定するために使用されるランキング関数は、次の関数を含む。
【００８９】
【数３】
2009505292.tif 000005
【００９０】
式中の項は上述の通りである。
【００９１】
他の実施形態では、クエリ依存成分、クエリ非依存成分、または両方の精度を向上するために、ＵＲＬの深さをランキング関数から除去することができ、あるいは他の成分をランキング関数に追加することができる。さらに、検索結果のランク付けを改善するために、バイアスクリック距離パラメータを含む上記のクエリ非依存成分を他のランキング関数（図示せず）に組み込むことができる。
【００９２】
ステップ２０４で所与の文書の文書統計がランキング関数に提供されると、例示的方法２０はステップ２０５に進む。ステップ２０５で、所与の文書に対して文書関連性スコアが決定され、メモリに格納され、所与の文書と関連付けられる。ステップ２０５から、例示的方法２０は決定ブロック２０６に進む。
【００９３】
決定ブロック２０６で、文書関連性スコアがネットワーク内の各文書に対して計算されたかどうかの決定がアプリケーションコードによって行われる。ネットワーク内の各文書に対して文書関連性スコアが計算されていないと決定された場合、例示的方法２０はステップ２０４に戻り、上述の通り続行される。ネットワーク内の各文書に対して文書関連性スコアが計算されたと決定された場合、例示的方法２０はステップ２０７に進む。
【００９４】
ステップ２０７で、多数の文書を含むクエリの検索結果は、それらの関連付けられた文書関連性スコアに従ってランク付けされる。結果的に得られる文書関連性スコアは、ネットワーク内の各々の文書のバイアスクリック距離値を考慮に入れる。検索結果がランク付けされると、例示的方法２０はステップ２０８に進み、そこでランク付けされた結果がユーザに表示される。ステップ２０８から、例示的方法２０はステップ２０９に進み、そこで最高ランクの結果が選択され、ユーザによって見られる。ステップ２０９から、例示的方法２０はステップ２１０に進み、そこで例示的方法２０は終了する。
【００９５】
ネットワーク内の文書の文書関連性スコアを生成し、かつ文書関連性スコアを使用して検索クエリの検索結果をランク付けする上記の方法に加えて、上記の方法を実行するためのコンピュータ実行可能命令が格納されたコンピュータ可読媒体も本明細書に開示する。
【００９６】
コンピューティングシステムもまた本明細書に開示する。例示的コンピューティングシステムは、コンピューティングシステム上で使用可能な少なくとも１つのアプリケーションモジュールを含み、少なくとも１つのアプリケーションモジュールはそこにロードされたアプリケーションコードを含み、アプリケーションコードは、ネットワーク内の文書の文書関連性スコアを生成する方法を実行する。アプリケーションコードは、上述の通りネットワーク内の文書の文書関連性スコアを生成し、かつ文書関連性スコアを使用して検索クエリの検索結果をランク付けするためのコンピュータ実行可能命令を有する上記のコンピュータ可読媒体のいずれかを使用して、コンピューティングシステムにロードすることができる。
【００９７】
明細書では特定の実施形態に関して詳述したが、上記を理解すれば、当業者がこれらの実施形態の変化物、変形物、および均等物を容易に思いつくことは理解されるであろう。したがって、開示した方法、コンピュータ可読媒体、およびコンピューティングシステムの範囲は、付属の特許請求の範囲およびそれらの均等物の範囲として評価すべきである。
【図面の簡単な説明】
【００９８】
【図１】ユーザによって入力された検索クエリに応答してランク付けされた検索結果を生成する方法の例示的ステップを示す例示的論理流れ図である。
【図２】本明細書に開示する方法およびプロセスの実現のための例示的動作環境の主要構成要素の一部のブロック図である。
【図３】ネットワーク空間内の文書、文書間のリンク、割当てバイアスクリック距離値を有する権威ノード、および計算バイアスクリック距離値を有する非権威ノードを識別する例示的ウェブグラフである。
【図４Ａ】ウェブグラフ上のノードのバイアスクリック距離値を割り当て、かつ生成する方法の例示的ステップを示す論理流れ図である。
【図４Ｂ】ウェブグラフ上のノードのバイアスクリック距離値を割り当て、かつ生成する方法の例示的ステップを示す論理流れ図である。
【図５Ａ】ウェブグラフ上の非権威ノードのバイアスクリック距離値を生成する方法の例示的ステップを示す論理流れ図である。
【図５Ｂ】ウェブグラフ上の非権威ノードのバイアスクリック距離値を生成する方法の例示的ステップを示す論理流れ図である。
【図６】バイアスクリック距離値パラメータを含むランキング関数を使用して生成する検索結果をランク付けする方法の例示的ステップを示す論理流れ図である。
【図１】
2009505292.tif 000008
【図２】
2009505292.tif 000009
【図３】
2009505292.tif 000010
【図４Ａ】
2009505292.tif 000011
【図４Ｂ】
2009505292.tif 000012
【図５Ａ】
2009505292.tif 000013
【図５Ｂ】
2009505292.tif 000014
【図６】
2009505292.tif 000015
【国際調査報告】
2009505292.tif 000016
2009505292.tif 000017