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