(57)【要約】【課題】  異なるオブジェクト型のオブジェクトの関係に基づいてオブジェクトに格付けを行う方法およびシステムを提供すること。【解決手段】  格付けシステムにより、オブジェクトの各型の属性ごとに式を定義する。式は、属性値を定義し、属性と、同一の型のオブジェクトおよび異なる型のオブジェクトに関連付けられる属性との間の関係に基づく。格付けシステムにより、属性値が解に収束するまで、式を使用してオブジェクトの属性値を繰り返し計算する。そして、格付けシステムにより、属性値に基づいてオブジェクトに格付けを行う。【選択図】  図１
2005327293.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトの属性の属性値を決定するためのコンピュータシステムにおける方法であって、
各型が型に固有の属性を有する型を提供するステップと、
各々が所定の型に関連付けられるオブジェクトを識別するステップと、
前記型の各々に対して、
該型に関連付けられるオブジェクト間の該型についての関係を識別し、
該型に関連付けられるオブジェクトと他の型に関連付けられるオブジェクトとの間の該型についての関係を識別するステップと、
前記型の各々に対して、前記識別された関係に基づいて前記オブジェクトの前記属性の評点を計算するステップと
を備えたことを特徴とする方法。
【請求項２】
前記型は、権威型、ハブ型、および専門知識型を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記権威型のオブジェクトの前記関係は、Ｗｅｂページが別のＷｅｂページへのリンクを有するかどうかに基づくことを特徴とする請求項２に記載の方法。
【請求項４】
前記権威型のオブジェクトと前記専門知識型のオブジェクトとの間の前記関係は、ユーザによるＷｅｂページへのアクセスに基づくことを特徴とする請求項３に記載の方法。
【請求項５】
前記ハブ型のオブジェクトの前記関係は、Ｗｅｂページが別のＷｅｂページへのリンクを有するかどうかに基づくことを特徴とする請求項２に記載の方法。
【請求項６】
前記ハブ型のオブジェクトと前記専門知識型のオブジェクトとの間の前記関係は、ユーザによるＷｅｂページへのアクセスに基づくことを特徴とする請求項５に記載の方法。
【請求項７】
同じ型のオブジェクト間の前記関係は、型内の関係であることを特徴とする請求項１に記載の方法。
【請求項８】
異なる型のオブジェクト間の前記関係は、型間の関係であることを特徴とする請求項１に記載の方法。
【請求項９】
型のオブジェクトを該属性値に基づいて格付けするステップをさらに備えたことを特徴とする請求項１に記載の方法。
【請求項１０】
前記型の前記属性値を定義する各型の式を提供するステップをさらに備えたことを特徴とする請求項１に記載の方法。
【請求項１１】
前記計算するステップは、前記式を繰り返し解くステップを含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記式は、他の式の属性値に基づいて再帰的に定義されることを特徴とする請求項１０に記載の方法。
【請求項１３】
各型の関数が該型の前記属性値を計算するよう定義するステップをさらに備えたことを特徴とする請求項１に記載の方法。
【請求項１４】
前記関数は、
Ｆｉ＝ＦｉＲｉ＋Σｊ≠ｉＦｊＲｊｉ
であり、ただし、Ｆｉはオブジェクトｉに関連付けられた前記属性値を表し、Ｒｉは前記オブジェクトｉの前記型のオブジェクト間の型内の関係を表し、およびＲｊｉは前記オブジェクトｉの前記型のオブジェクトと他のオブジェクトｊの型のオブジェクトとの間の型間の関係を表すことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記関数は、
【数１】
2005327293.tif 000016
であることを特徴とする請求項１３に記載の方法。
【請求項１６】
オブジェクトの属性値を決定するコンピュータシステムにおける方法であって、
型のオブジェクトに対する型に固有の属性の属性値を、該型のオブジェクトと、別の型に固有の属性を有する別の型のオブジェクトとの間の関係に基づいて計算する関数を提供するステップと、
該型の前記オブジェクトともう一方の型のオブジェクトとの間の関係を指定するデータを受け取るステップと、
前記提供された関数を計算して、該型の前記オブジェクトの前記属性値を決定するステップと
を備えたことを特徴とする方法。
【請求項１７】
もう一方の型のオブジェクトの前記型に固有の属性の前記属性値を計算する関数を提供するステップをさらに備えたことを特徴とする請求項１６に記載の方法。
【請求項１８】
前記関数は、再帰的に定義されることを特徴とする請求項１７に記載の方法。
【請求項１９】
前記計算するステップは、前記属性値が解に収束するまで各関数を繰り返し計算するステップを含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
前記関数は、一次方程式を表すことを特徴とする請求項１８に記載の方法。
【請求項２１】
前記提供された関数は、該型のオブジェクト間の関係に基づいて前記属性値を計算することを特徴とする請求項１６に記載の方法。
【請求項２２】
前記関数は、
Ｆｉ＝ＦｉＲｉ＋Σｊ≠ｉＦｊＲｊｉ
として定義され、ただし、Ｆｉはオブジェクトｉに関連付けられる前記属性値を表し、Ｒｉは前記オブジェクトｉの前記型のオブジェクト間の型内の関係を表し、およびＲｊｉは前記オブジェクトｉの前記型のオブジェクトと他のオブジェクトｊの型のオブジェクトとの間の型間の関係を表すことを特徴とする請求項２１に記載の方法。
【請求項２３】
オブジェクトの属性値を決定するコンピュータシステムを制御するための命令を含むコンピュータ読取可能な媒体であって、
第１の型のオブジェクトに対する第１の型に固有の属性の属性値を、前記第１の型のオブジェクトと、第２の型に固有の属性を有する第２の型のオブジェクトとの間の関係に基づいて計算する第１の関数を提供するステップと、
前記第２の型のオブジェクトに対する前記第２の型に固有の属性の属性値を計算するための第２の関数を提供するステップと、
前記第１の型の前記オブジェクトと前記第２の型のオブジェクトとの間の関係を指定するデータを受け取るステップと、
前記提供された関数の計算を行って、前記第１の型および前記第２の型の前記オブジェクトの前記属性値を決定するステップと
を備えた方法によって、前記オブジェクトの属性値を決定することを特徴とするコンピュータ読取可能な媒体。
【請求項２４】
前記第２の関数は、前記第２の型のオブジェクト間の関係に基づいて前記属性値を計算することを特徴とする請求項２３に記載のコンピュータ読取可能な媒体。
【請求項２５】
前記第１の関数は、前記第１の型のオブジェクト間の関係に基づいて前記属性値をさらに計算することを特徴とする請求項２３に記載のコンピュータ読取可能な媒体。
【請求項２６】
前記第２の関数は、前記第１の型の前記オブジェクトの前記属性値に基づいて前記属性値を計算することを特徴とする請求項２３に記載のコンピュータ読取可能な媒体。
【請求項２７】
前記関数は再帰的に定義されることを特徴とする請求項２３に記載のコンピュータ読取可能な媒体。
【請求項２８】
前記計算するステップは、前記属性値が解に収束するまで各関数を繰り返し計算するステップを含むことを特徴とする請求項２７に記載のコンピュータ読取可能な媒体。
【請求項２９】
前記関数は、一次方程式を表すことを特徴とする請求項２３に記載のコンピュータ読取可能な媒体。
【請求項３０】
前記関数は、
Ｆｉ＝ＦｉＲｉ＋Σｊ≠ｉＦｊＲｊｉ
として定義され、ただし、Ｆｉはオブジェクトｉに関連付けられる前記属性値を表し、Ｒｉは前記オブジェクトｉの前記型のオブジェクト間の型内の関係を表し、およびＲｊｉは前記オブジェクトｉの前記型のオブジェクトと他のオブジェクトｊの型のオブジェクトとの間の型間の関係を表すことを特徴とする請求項２３に記載のコンピュータ読取可能な媒体。
【請求項３１】
オブジェクトの属性値を決定するためのコンピュータシステムであって、
第１の型のオブジェクトに対する第１の型に固有の属性の属性値を、前記第１の型のオブジェクトと、第２の型に固有の属性を有する第２の型のオブジェクトとの間の関係に基づいて計算する第１の関数を実装する第１のコンポーネントと、
前記第２の型のオブジェクトに対する前記第２の型に固有の属性の属性値を計算するための第２の関数を実装し、第１および第２の関数が再帰的に定義される第２のコンポーネントと、
前記第１の型の前記オブジェクトと前記第２の型のオブジェクトとの間の関係を指定するデータを含むデータストアと、
前記第１および第２のコンポーネントを繰り返し呼び出すことによって、前記第１の型および前記第２の型の前記オブジェクトの前記属性値を決定するコンポーネントと
を備えたことを特徴とするコンピュータシステム。
【請求項３２】
前記第２の関数は、前記第２の型のオブジェクト間の関係に基づいて前記属性値を計算することを特徴とする請求項３１に記載のコンピュータシステム。
【請求項３３】
前記第１の関数は、前記第１の型のオブジェクト間の関係に基づいて前記属性値をさらに計算することを特徴とする請求項３１に記載のコンピュータシステム。
【請求項３４】
前記第２の関数は、前記第１の型の前記オブジェクトの前記属性値に基づいて属性値を計算することを特徴とする請求項３１に記載のコンピュータシステム。
【請求項３５】
前記第１および第２のコンポーネントは、前記属性値が解に収束するまで呼び出されることを特徴とする請求項３１に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般には、オブジェクトの格付けに関し、より詳細には、オブジェクト関係に基づく格付けに関する。
【背景技術】
【０００２】
ＧｏｏｇｌｅおよびＯｖｅｒｔｕｒｅなど多くの検索エンジンサービスは、インターネットを介してアクセス可能な情報の検索を提供する。これらの検索エンジンサービスによりユーザは、Ｗｅｂページなど、ユーザにとって興味深いと思われる表示ページを検索することができる。検索語を含む検索要求（「クエリ」とも呼ばれる）をユーザが送信した後、検索エンジンサービスは、これらの検索語に関連していると思われるＷｅｂページを識別する。関連するＷｅｂページを迅速に識別するために、検索エンジンサービスは、Ｗｅｂページへのキーワードのマッピングを保持することができる。検索エンジンサービスは、Ｗｅｂ（すなわちワールドワイドウェブ）を「クローリング」することによりこのマッピングを生成して、各Ｗｅｂページのキーワードを抽出することができる。Ｗｅｂをクロールするために、検索エンジンサービスは、ルートのＷｅｂページのリストを使用し、これらのルートのＷｅｂページを通じてアクセス可能なすべてのＷｅｂページを識別することができる。特定のＷｅｂページのキーワードは、見出し語、Ｗｅｂページのメタデータで供給された語、ハイライト表示された語などを識別するような、様々な周知の情報検索技術を使用して抽出することができる。検索エンジンサービスにより、各々の合致の近さ、Ｗｅｂページの人気（例えばＧｏｏｇｌｅのＰａｇｅＲａｎｋ）などに基づいて各Ｗｅｂページが検索要求にどの程度関連しているかを示す適合性の評点（ｓｃｏｒｅ）を計算することができる。次に、検索エンジンサービスにより、これらのＷｅｂページへのリンクを適合性に基づいた順序でユーザに表示する。検索エンジンにより、さらに一般的に、あらゆる文書の集まりで情報の検索を提供することができる。例えば、文書の集まりには、すべての米国特許、すべての連邦の法廷意見、企業のすべての保管文書などを含めることもできる。
【０００３】
Ｗｅｂページを格付けするための２つの周知の技術は、ＰａｇｅＲａｎｋおよびＨＩＴＳ（「Ｈｙｐｅｒｌｉｎｋｅｄ−Ｉｎｄｕｃｅｄ  Ｔｏｐｉｃ  Ｓｅａｒｃｈ」）である。ＰａｇｅＲａｎｋは、Ｗｅｂページが重要なＷｅｂページへのリンク（つまり「外向きのリンク」）を持つという原則に基づく。したがって、Ｗｅｂページの重要度は、そのＷｅｂページにリンク（つまり「内向きのリンク」）する他のＷｅｂページの数および重要度に基づく。簡単な形式では、Ｗｅｂページの間のリンクは行列Ａによって表すことができ、ここでＡｉｊはＷｅｂページｉからＷｅｂページｊへの外向きのリンクの数を表す。Ｗｅｂページｊの重要度の評点ｗｊは、以下の式で表すことができる。
ｗｊ＝ΣｉＡｉｊｗｉ
この式は、以下の式に基づく反復計算によって解くことができる。
ＡＴｗ＝ｗ
ただし、ｗはＷｅｂページの重要度の評点のベクトルであり、ＡＴの優固有ベクトル（ｐｒｉｎｃｉｐａｌ  ｅｉｇｅｎｖｅｃｔｏｒ）である。
【０００４】
ＨＩＴＳ技術はさらに、他の重要なＷｅｂページへのリンクを数多く持つＷｅｂページはそれ自体が重要であるという原則に基づく。したがって、ＨＩＴＳは、Ｗｅｂページの「重要度」を、「ハブ」および「権威」という２つの関連する属性に分割する。「ハブ」は、ＷｅｂページがリンクするＷｅｂページの「権威」の評点によって測定され、「権威」は、ＷｅｂページにリンクするＷｅｂページの「ハブ」の評点によって測定される。Ｗｅｂページの重要度をクエリからは独立して計算するＰａｇｅＲａｎｋとは対照的に、ＨＩＴＳでは、内向きおよび外向きのリンクをたどることによって結果のＷｅｂページおよび結果のＷｅｂページに関連するＷｅｂページに基づいて重要度を計算する。ＨＩＴＳは、検索エンジンサービスにクエリを送信し、結果のＷｅｂページをＷｅｂページの初期セットとして使用する。ＨＩＴＳは、内向きのリンクの宛先であるＷｅｂページおよび結果のＷｅｂページの外向きのリンクのソースであるＷｅｂページをセットに追加する。次にＨＩＴＳは、反復アルゴリズムを使用して各Ｗｅｂページの権威およびハブの評点を計算する。権威およびハブの評点は、以下の式で表すことができる。
【０００５】
【数１】
2005327293.tif 000003
【０００６】
ただし、ａ（ｐ）はＷｅｂページｐの権威の評点を表し、ｈ（ｐ）はＷｅｂページｐのハブの評点を表す。ＨＩＴＳでは、隣接行列Ａを使用してリンクを表す。隣接行列は、以下の式で表すことができる。
【０００７】
【数２】
2005327293.tif 000004
【０００８】
ベクトルａおよびｈはそれぞれ、セット内のすべてのＷｅｂページの権威およびハブの評点に対応し、以下の式で表すことができる。
ａ＝ＡＴｈおよびｈ＝Ａａ
したがって、ａおよびｈは、行列ＡＴＡおよびＡＡＴの固有ベクトルである。ＨＩＴＳはまた、アクセス数によって測定されるＷｅｂページの人気を計算に入れるように変更することもできる。Ｗｅｂログの分析に基づいて、隣接行列のｂｉｊは、ユーザがＷｅｂページｉからＷｅｂページｊに移動するときに増分することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上述のＷｅｂページ格付け技術では、Ｗｅｂページの格付けを主としてＷｅｂページ自体の属性に基づく。Ｗｅｂページ自体の属性は、一方のＷｅｂページから別のＷｅｂページへのリンクを含み、一方のＷｅｂページから別のＷｅｂページへ伝わる。格付け技術では、Ｗｅｂページに直接関連がない属性を計算に入れることができない。例えば、Ｗｅｂページの重要度は、Ｗｅｂページにアクセスするユーザの専門知識が計算に入れられる場合、より正確に決定することができる。Ｗｅｂページに直接関連がない属性に基づいてＷｅｂページの重要度を計算するための技術を有することが望ましい。より一般的には、一方の型のオブジェクト（例えば、Ｗｅｂページ）の評点を、別の型のオブジェクト（例えば、ユーザ）との関係に基づいて生成することが望ましい。
【課題を解決するための手段】
【００１０】
異なるオブジェクト型のオブジェクトとの関係に基づいてオブジェクトを格付けするための方法およびシステムを提供する。格付けシステムにより、オブジェクトの各型の属性ごとに式を定義する。式は、属性値を定義し、属性と、同じ型のオブジェクトおよび異なる型のオブジェクトに関連付けられる属性との間の関係に基づく。属性値は、一方の属性が別の属性に関して定義され、逆の場合も同じであるように相互依存することができるので、式は属性の再帰的定義を表す。格付けシステムにより、属性値が解に収束するまで式を使用して、オブジェクトの属性値を繰り返し計算する。次に、格付けシステムにより、属性値に基づいてオブジェクトの格付けを行う。
【発明を実施するための最良の形態】
【００１１】
同じまたは別のデータオブジェクト型のデータオブジェクトとの関係に基づいてデータオブジェクト型のデータオブジェクトを格付けするための方法およびシステムを提供する。一実施形態において、格付けシステムにより、様々なデータオブジェクト型のデータオブジェクトを識別する。例えば、一方のデータオブジェクト型がＷｅｂページであり、別のデータオブジェクト型がクエリであり、および別のデータオブジェクト型がユーザである場合がある。各データオブジェクト型は、様々な型固有の属性を有することができる。例えば、Ｗｅｂページが権威属性を有し、およびユーザが専門知識属性を有する場合がある。Ｗｅｂページの権威属性は、Ｗｅｂページの内向きのリンクの数に基づくことができる。ユーザの専門知識属性は、ユーザが高い権威属性値を持つＷｅｂページにアクセスする場合に増加される。格付けシステムにより、データオブジェクトの属性値を計算し、およびデータオブジェクトの属性値に基づいてデータオブジェクトを格付けすることができる。
【００１２】
格付けシステムにより、各オブジェクトが単一の属性を含むように、オブジェクトの「型」を定義する。例えば、格付けシステムにより、Ｗｅｂページの権威属性に対応する型、およびＷｅｂページのハブ属性に対応する別の型を定義することができる。したがって、２つの型は、同じ基礎をなすデータオブジェクト（例えばＷｅｂページ）を表すことができる。格付けシステムにより、型内の関係と呼ばれる同じ型のオブジェクトの間の様々な関係、および型間の関係と呼ばれる異なる型のオブジェクトの間の様々な関係を決定する。例えば、クエリが送信される場合、格付けシステムにより、結果を権威型のオブジェクトとして使用し、およびＷｅｂログを使用して、これらのＷｅｂページにアクセスしたユーザを専門知識型のオブジェクトとして識別することができる。権威型の型内の関係のオブジェクトは、Ｗｅｂページの内向きのリンクと外向きのリンクとの関係を含むことができる。例えば、Ｗｅｂページが別のＷｅｂページへのリンクを有する場合、Ｗｅｂページはその他のＷｅｂページへの外向きのリンクの関係を有し、およびその他のＷｅｂページはＷｅｂページへの内向きのリンクの関係を有する。権威型と専門知識型とのオブジェクトの間の型間の関係は、Ｗｅｂページへのユーザアクセスに基づく。例えば、ユーザがＷｅｂページにアクセスする場合、Ｗｅｂページおよびユーザはアクセスの関係を有する。格付けシステムにより、他の型のオブジェクトの属性値と組み合わされた型内の関係および型間の関係を使用して、所定の型のオブジェクトに対する属性の値を導き出す。例えば、格付けシステムにより、内向きと外向きとのリンクの関係およびユーザアクセスの関係を使用して、Ｗｅｂページの権威およびハブ属性ならびにユーザの専門知識属性を導き出すことができる。
【００１３】
一実施形態において、格付けシステムにより、一次方程式など一連の式を使用して関係および属性を表す。格付けシステムにより、別の型の属性値に基づいて再帰的に定義される一次方程式を使用して、各型の属性値を表す。例えば、権威属性の一次方程式が専門知識属性の属性値に基づいて定義されることも、またその逆の場合もある。一次方程式は再帰的に定義することができるので、格付けシステムにより、属性値が解に収束するまで、各一次方程式の属性値を繰り返し計算することによって一次方程式を解く。一次方程式を解いた後、格付けシステムにより、属性値に基づいてデータオブジェクトを格付けすることができる。例えば、格付けシステムにより、Ｗｅｂページの権威属性値に基づいてＷｅｂページを格付けすることができる。
【００１４】
格付けシステムにより、オブジェクトの型内と型間との関係に基づいて、オブジェクトの属性値を表す。属性の値は、以下の数式によって表すことができる。
Ｆｉ＝ＦｉＲｉ＋Σｊ≠ｉＦｊＲｊｉ
【００１５】
ただし、Ｆｉはオブジェクトｉに関連付けられる属性値を表し、Ｒｉはオブジェクトｉの型のオブジェクトの間の型内関係を表し、Ｒｊｉはオブジェクトｉの型と他のオブジェクトｊの型とのオブジェクトの間の型間の関係を表す。ｘ＝｛ｘ１、ｘ２、・・・ｘｍ｝およびｙ＝｛ｙ１、ｙ２、・・・ｙｎ｝の２つのオブジェクトの型がある場合、これらの型内の関係はＲＸおよびＲＹとして表すことができ、型間の関係はＲＸＹおよびＲＹＸによって表すことができる。格付けシステムでは、隣接行列を使用して関係情報を表す。ＬＸおよびＬＹは、それぞれ集合ＸおよびＹの型内の関係の隣接行列を表す。ＬＸＹおよびＬＹＸは、それぞれ、ＸのオブジェクトからＹのオブジェクトへの型間の関係の隣接行列およびＹのオブジェクトからＸのオブジェクトへの型間の関係の隣接行列を表す。格付けシステムでは、以下のように隣接行列を表す。
【００１６】
【数３】
2005327293.tif 000005
【００１７】
ただし、ＬＸＹ（ｉ，ｊ）は、集合Ｘのオブジェクトｉから集合Ｙのオブジェクトｊへの関係（「リンク」とも呼ばれる）が存在するかどうかを示す。属性値の一次方程式は、以下の式のように表すことができる。
【００１８】
【数４】
2005327293.tif 000006
【００１９】
ただし、ｗｘは、Ｘのオブジェクトの属性ベクトルであり、ｗｙはＹのオブジェクトの属性ベクトルである。式１は、以下の形式に一般化することができる。
【００２０】
【数５】
2005327293.tif 000007
【００２１】
ただし、Ｍは属性ベクトルの行列を表す。
【００２２】
オブジェクトの間の相互に補強し合う関係がオブジェクトに過度の属性値をもたらすことがあるので、格付けシステムにより、オブジェクトが１つの隣接行列内のｎ個の他のオブジェクトに関連する場合、各関連するオブジェクトはその１／ｎ番目の属性値を受け取るような方法で、バイナリの隣接行列を正規化することができる。格付けシステムにより、ＰａｇｅＲａｎｋのランダムサーファーモデルを導入して、ランダムな関係をシミュレートし、したがって、以下に説明する計算時のシンクノードを回避することができる。さらに、異なる型からの属性が各々他の属性に対して異なる重要度を有する可能性があるので、格付けシステムにより、型の各々の組み合わせに重み付けを使用することができる。したがって、格付けシステムにより、正規化、ランダムサーファーモデル、および重み付けを計算に入れて、以下の式によって属性値を表すことができる。
【００２３】
【数６】
2005327293.tif 000008
【００２４】
ただし、Ｕは一様な推移確率の推移行列であり（すべてのｉ、ｊについてＵｉｊ＝１／ｎ、ただし、ｎはデータ空間Ｎのオブジェクトの合計数）、ＬＭおよびＬＮＭは正規化された隣接行列であり、δおよびεは行列ＬＭおよびＬＮＭ内のランダムな関係をシミュレートするために使用される平滑化因数であり、αＭおよびβＮＭは関係の重み付けを表す。格付けシステムにより、収束するまで式３を繰り返し計算する。式３は、以下の式で表される統合された正方行列Ａによって表すことができる。
【００２５】
【数７】
2005327293.tif 000009
【００２６】
行列Ａは、対角線上に
【００２７】
【数８】
2005327293.tif 000010
【００２８】
、統合された行列の他の部分に
【００２９】
【数９】
2005327293.tif 000011
【００３０】
を有する。格付けシステムにより、行列Ａを使用して、異なるデータ空間にあるすべてのデータオブジェクトの属性ベクトルである、ベクトルｗを変換するために反復アプローチを使用する（例えば、ｗ＝ＡＴｗ）。反復が収束する場合、ベクトルｗは行列Ａの優固有ベクトルである。
【００３１】
ＭおよびＮが異質のデータ空間である場合、格付けシステムでは、ランダムな関係を使用して無関係を表す。ＭのオブジェクトがＮのオブジェクトにリンクの関係を持たない場合、部分行列
【００３２】
【数１０】
2005327293.tif 000012
【００３３】
はゼロであり、「シンクノード」を表す。計算では、シンクノードにすべての属性値を割り当てることがある。これを防ぐために、格付けシステムにより、部分行列
【００３４】
【数１１】
2005327293.tif 000013
【００３５】
の対応する行のすべての要素を１／ｎに設定する。ただし、ｎはデータ空間Ｎのオブジェクトの合計数である。代替として、格付けシステムにより、望ましくない型内および型間の関係に対して、対応する重み付けを０に設定することができる。しかし、βＭＮが０よりも大きい場合、反復計算が収束するのであればβＮＭは０よりも大きい必要がある。したがって、
【００３６】
【数１２】
2005327293.tif 000014
【００３７】
の関係が望ましくない場合、格付けシステムにより、βＮＭを非常に小さい正の重みに設定して
【００３８】
【数１３】
2005327293.tif 000015
【００３９】
の影響を低減する。
【００４０】
すべての隣接行列を使用して統合された行列を構築することにより、格付けシステムでは、異なるオブジェクトの型を含む、統合されたデータ空間を構築する。したがって、以前の型間の関係は、統合された空間の型間の関係と見なすことができ、格付けシステムにより、効率的に単一のデータ空間のリンク解析を行う。
【００４１】
図１は、一実施形態における格付けシステムのコンポーネントを例示するフロー図である。格付けシステム１１０は、通信リンク１０２を介して様々なＷｅｂサイト１０１に接続されている。格付けシステムには、オブジェクト収集コンポーネント１１２、関係確立コンポーネント１１３、評点計算コンポーネント１１４、およびオブジェクト順序付けコンポーネント１１５を呼び出してオブジェクトを格付けするオブジェクト格付けコンポーネント１１１を含む。オブジェクト格付けコンポーネントは、Ｗｅｂページのセットを受け取り、型内および型間の関係に基づいてＷｅｂページを格付けすることができる。オブジェクト収集コンポーネントは、様々な型のオブジェクトに関連する関係情報を取り出す。例えば、オブジェクト収集コンポーネントは、ＷｅｂサイトのＷｅｂログにアクセスして、どのユーザがどのＷｅｂページにアクセスするのかを識別することができる。関係確立コンポーネントは、型内および型間の関係の行列を作成する。例えば、関係の行列は、ユーザがアクセスするＷｅｂページにユーザをマッピングすることができる。評点計算コンポーネントは、属性値が解に収束するまで、式３を使用して属性値を再帰的に計算する。オブジェクト順序付けコンポーネントは、属性値に基づいてデータオブジェクトをソートする。例えば、オブジェクト順序付けコンポーネントは、Ｗｅｂページの権威属性の値を使用して、Ｗｅｂページをソートすることができる。
【００４２】
格付けシステムが実装されるコンピューティング装置には、中央処理装置、メモリ、入力装置（例えば、キーボードおよびポインティングデバイスなど）、出力装置（例えば、ディスプレイ装置など）、および記憶装置（例えば、ディスクドライブなど）を含めることができる。メモリおよび記憶装置は、格付けシステムを実装する命令を含めることができるコンピュータ読取可能な媒体である。さらに、データ構造およびメッセージ構造を、通信リンク上の信号などのデータ伝送媒体を介して格納または送信することができる。インターネット、ローカルエリアネットワーク、ワイドエリアネットワーク、またはポイントツーポイントのダイヤルアップ接続など、様々な通信リンクを使用することができる。
【００４３】
格付けシステムを、様々なオペレーティング環境において実装することができる。使用に最適な様々な周知のコンピューティングシステム、環境、および構成には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップ装置、マルチプロセッサシステム、マイクロプロセッサに基づくシステム、プログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたは装置のいずれかを含む分散コンピューティング環境などが含まれる。
【００４４】
格付けシステムにより、１つまたは複数のコンピュータまたは他の装置によって実行されるプログラムモジュールなど、コンピュータ実行可能命令の一般的なコンテキストにおいて説明することができる。一般に、プログラムモジュールには、特定のタスクを実行するかまたは特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。通常、プログラムモジュールの機能を、様々な実施形態において望ましいように組み合わせまたは分散することができる。
【００４５】
図２は、一実施形態におけるオブジェクト格付けコンポーネントの処理を例示するフロー図である。コンポーネントは、オブジェクト情報を収集し、オブジェクトの間の関係を確立し、オブジェクトの属性値を計算し、属性に基づいてオブジェクトを順序付ける。ブロック２０１において、コンポーネントは、様々なオブジェクトに関連する情報を収集する。ブロック２０２において、コンポーネントは、関係確立コンポーネントを呼び出して、隣接行列を生成する。関係確立コンポーネントはまた、αおよびβの重みを取り出して調整することもできる。ブロック２０３において、コンポーネントは、評点計算コンポーネントを呼び出して、属性値が解に収束するまで属性値を繰り返し計算する。ブロック２０４において、コンポーネントは、属性の値に基づいてデータオブジェクトを順序付ける。例えば、コンポーネントは、権威属性に基づいてＷｅｂページを順序付けすることができる。
【００４６】
図３は、一実施形態における関係確立コンポーネントの処理を例示するフロー図である。ブロック３０１から３０３において、コンポーネントは、各型に対する隣接行列を確立するループを行う。ブロック３０１において、コンポーネントは次の型を選択する。判断ブロック３０２において、すべての型がすでに選択されている場合、コンポーネントは戻り、別の場合、コンポーネントはブロック３０３において続行する。ブロック３０３において、コンポーネントは、選択された型のオブジェクトとすべての型のオブジェクトとの間の関係を確立する。例えば、コンポーネントは、権威型とハブ型との間の関係、および権威型と専門知識型との間の関係を確立する。次に、コンポーネントはブロック３０１へのループを行い、次の型を選択する。
【００４７】
図４は、一実施形態における評点計算コンポーネントの処理を例示するフロー図である。コンポーネントは、属性値が収束するまで式を繰り返し計算する。ブロック４０１において、コンポーネントは、隣接行列によって表されたオブジェクトの関係を取り出す。ブロック４０２において、コンポーネントは、型内および型間の関係に対する重みαおよびβを取り出す。ブロック４０３において、コンポーネントは、各型のベクトルｗを初期化して、その型の各オブジェクトに対し等しい属性値を持つようにする。コンポーネントは、各値を１／ｍに設定することができる。ただし、ｍは型のオブジェクトの数である。例えば、１０のユーザがある場合、コンポーネントは専門知識型の初期の属性値を１／１０に設定する。コンポーネントはまた、判断ブロック４０５の検査を最初に通過するように、各型の差異変数を大きい値に初期化する。コンポーネントは、計算が解に収束しているかどうかを決定するために、各反復の最後において各差異変数に新しい値を計算する。ブロック４０４から４０９において、コンポーネントは、計算が解に収束するまで式３の計算を実行する。ブロック４０４において、コンポーネントは次の反復を開始する。判断ブロック４０５において、前回の反復中に計算された差異の合計が差異のしきい値よりも小さい場合、計算は解に収束しており、コンポーネントは戻り、別の場合、コンポーネントはブロック４０６において続行する。ブロック４０６において、コンポーネントは次の型を選択する。判断ブロック４０７において、すべての型がすでに選択されている場合、コンポーネントはブロック４０４にループを行い、次の反復を開始し、別の場合、コンポーネントはブロック４０８において続行する。ブロック４０８において、コンポーネントは、以前の反復において計算された値に基づいて、選択された型の値を計算する。ブロック４０９において、コンポーネントは、この反復の値と選択された型の以前の反復の値との間の差異を計算する。次に、コンポーネントはブロック４０６にループを行い、次の型を選択する。
【００４８】
本明細書において格付けシステムの特定の実施形態について例示のために説明しているが、本発明の精神および範囲を逸脱することなく、様々な変更を行うことができることを、当事業者であれば理解するであろう。例えば、当事業者であれば、属性値を表すために非線形方程式を使用することができることを理解するであろう。また、格付けシステムは、相互に何らかの関係を有するすべての型のオブジェクトに使用することができる。例えば、格付けシステムにより、学生または志願者と教授との関係を使用する「重要度」に基づいて大学を格付けするために使用することもできる。ここで、大学、学生、および教授は異なる型のオブジェクトを表す。したがって、本発明は、添付の請求の範囲による場合を除き、限定されることはない。
【図面の簡単な説明】
【００４９】
【図１】一実施形態における格付けシステムのコンポーネントを例示するフロー図である。
【図２】一実施形態におけるオブジェクト格付けコンポーネントの処理を例示するフロー図である。
【図３】一実施形態における関係確立コンポーネントの処理を例示するフロー図である。
【図４】一実施形態における評点計算コンポーネントの処理を例示するフロー図である。
【図１】
2005327293.tif 000017
【図２】
2005327293.tif 000018
【図３】
2005327293.tif 000019
【図４】
2005327293.tif 000020
【外国語明細書】
2005327293000001.pdf