(57)【特許請求の範囲】
【請求項１】
検索結果のドキュメントを順位付けるコンピューティングデバイスであって、
コンピュータ実行可能な命令を有するメモリと、
前記メモリに格納されたコンピュータ実行可能な命令を実行する中央処理装置と
を備え、前記コンピュータ実行可能な命令は、
問い合わせをユーザから受信するステップと、
前記受信された問い合わせに対して検索結果としてのドキュメントを識別するステップと、
前記識別されたドキュメントのキーワードを識別するステップと、
前記検索結果の識別されたドキュメントの各組に対して、組のうちのドキュメントが有する、前記組のうちのもう一方のドキュメントに対する類似度を計算するステップであって、前記類似度は、次の式
【数１】
0004845420.tif 000023
に基づいて計算され、ただし、ａｆｆ（ｄｉ，ｄｊ）はドキュメントｄｉのドキュメントｄｊに対する類似度であり、ドキュメントｄｉは前記組のうちのドキュメントを表して、ドキュメントｄｊは前記組のうちのもう一方のドキュメントを表して、
【数２】
0004845420.tif 000024
はドキュメントｄｉのベクトルを表して、
【数３】
0004845420.tif 000025
はドキュメントｄｊのベクトルを表して、および
【数４】
0004845420.tif 000026
はドキュメントｄｉのベクトルの長さを表して、各ベクトルは、対応するドキュメントの識別された少なくとも１つのキーワードに対する少なくとも１つのエントリを有する、ステップと、
前記検索結果の識別された各ドキュメントに対して、類似度の行列から得られる正規化された類似度の行列の要素に基づいて、前記識別されたドキュメントに対する情報の豊富さを計算するステップであって、前記情報の豊富さは、次の式
【数５】
0004845420.tif 000027
に基づいて計算され、ただし、ＩｎｆｏＲｉｃｈ（ｄｉ）はドキュメントｄｉの情報の豊富さであり、ドキュメントｄｉは前記検索結果の識別されたドキュメントを表して、ドキュメントｄｊは前記検索結果における別のドキュメントを表して、
【数６】
0004845420.tif 000028
は前記正規化された類似度の行列の要素であり、前記類似度の行列は前記検索結果における識別されたドキュメントおよび別のドキュメントの計算された類似度を含む、ステップと、
前記検索結果のドキュメントについて計算された情報の豊富さに基づいて順位付けされた検索結果のドキュメントの表示を表示装置に出力するステップと
を含むことを特徴とするコンピューティングデバイス。
【請求項２】
前記ドキュメントを識別するステップは、
検索エンジンサービスへ前記問い合わせを送信するステップと、
検索結果としてのドキュメントを受信するステップと
を含むことを特徴とする請求項１に記載のコンピューティングデバイス。
【請求項３】
前記ドキュメントは、ウェブページであることを特徴とする請求項１に記載のコンピューティングデバイス。
【請求項４】
コンピュータシステムにおいて、ドキュメントの集まり内のドキュメントの情報の豊富さを中央処理装置およびメモリにより計算する方法であって、
前記集まり内の各ドキュメントが有する、前記集まり内の別のドキュメントに対する類似度を前記中央処理装置が識別するステップであって、前記類似度は、前記集まり内のドキュメントであるドキュメントの組のうちの１つのドキュメント、および前記集まり内の別のドキュメントである前記組のうちのもう一方のドキュメントを含むドキュメントの各組に対して識別されて、１つのドキュメントの情報が別のドキュメントの情報にどの程度含まれているかを示す、ステップと、
前記集まり内の各ドキュメントに対して、類似度の行列から得られる正規化された類似度の行列の要素に基づいて前記情報の豊富さを前記中央処理装置が決定するステップと、
前記集まり内のドキュメントの前記決定された情報の豊富さを前記メモリに前記中央処理装置が格納するステップと、
前記格納された情報の豊富さに基づいて前記ドキュメントを前記中央処理装置が順位付けするステップであって、各ドキュメントに対して前記決定された情報の豊富さは、次の式
【数７】
0004845420.tif 000029
として定義され、ただし、ＩｎｆｏＲｉｃｈ（ｄｉ）はドキュメントｄｉの情報の豊富さであり、ドキュメントｄｉは前記集まり内のドキュメントを表して、ドキュメントｄｊは前記集まり内の別のドキュメントを表して、
【数８】
0004845420.tif 000030
は前記正規化された類似度の行列の要素であり、前記類似度の行列は、前記集まり内のドキュメントの、前記集まり内の別のドキュメントに対する識別された類似度を含み、前記集まり内のドキュメントはウェブページである、ステップと
を備えたことを特徴とする方法。
【請求項５】
ウェブページの集まり内のドキュメントの情報の豊富さを計算するコンピューティングデバイスであって、
コンピュータ実行可能な命令を有するメモリと、
前記メモリに格納されたコンピュータ実行可能な命令を実行する中央処理装置と
を備え、前記コンピュータ実行可能な命令は、
前記集まり内の各ウェブページが有する、前記集まり内の別のウェブページに対する類似度を識別するステップであって、前記類似度は、前記ウェブページの集まり内のウェブページであるウェブページの組のうちの１つのウェブページ、および前記ウェブページの集まり内の別のウェブページである前記組のうちのもう一方のウェブページを含むウェブページの各組に対して識別されて、１つのウェブページの情報が別のウェブページの情報にどの程度含まれているかを示す、ステップと、
前記集まり内の各ウェブページに対して、類似度の行列から得られる正規化された類似度の行列の要素に基づいて前記情報の豊富さを決定するステップと、
前記集まり内のウェブページの前記決定された情報の豊富さを前記メモリに格納するステップと、
前記格納された情報の豊富さに基づいて前記ウェブページを順位付けするステップであって、各ウェブページに対して前記決定された情報の豊富さは、次の式
【数９】
0004845420.tif 000031
として定義され、ただし、ＩｎｆｏＲｉｃｈ（ｄｉ）はウェブページｄｉの情報の豊富さであり、ウェブページｄｉは前記集まり内のウェブページを表して、ウェブページｄｊは前記集まり内の別のウェブページを表して、
【数１０】
0004845420.tif 000032
は前記正規化された類似度の行列の要素であり、前記類似度の行列は、前記集まり内のウェブページの、前記集まり内の別のウェブページに対する識別された類似度を含む、ステップと
を含むことを特徴とするコンピューティングデバイス。
【請求項６】
前記集まり内の別のウェブページに対する類似度を識別するステップは、類似度の図式を生成するステップであって、前記類似度の図式は、ドキュメントをノードとして表現し、類似度の値をノードの間の有向のエッジの重みとして表現する、ステップを含むことを特徴とする請求項５に記載のコンピューティングデバイス。
【請求項７】
前記ウェブページを順位付けするステップは、
検索エンジンサービスへ問い合わせを送信するステップと、
検索結果としてのウェブページを受信するステップと
を含むことを特徴とする請求項５に記載のコンピューティングデバイス。
【請求項８】
前記ウェブページを順位付けするステップは、前記問い合わせに対する前記検索結果の各ドキュメントの適合度にさらに基づくことを特徴とする請求項７に記載のコンピューティングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般には、検索エンジンサービスに送信された検索要求により識別される検索結果のドキュメントを順位付ける技術に関する。
【背景技術】
【０００２】
ＧｏｏｇｌｅやＯｖｅｒｔｕｒｅなど多数の検索エンジンサービスにより、インターネットを介してアクセス可能な情報検索が提供されている。これらの検索エンジンは、ユーザに、ユーザが関心を持つであろうウェブページなどの表示ページを検索することを可能にする。ユーザが、検索語を含む検索要求を送信した後、検索エンジンサービスは、これらの検索語に関連する可能性があるウェブページを識別する。関連するウェブページを速やかに識別するために、検索エンジンサービスは、キーワードのウェブページへのマッピングを保持する。このマッピングは、各ウェブページのキーワードを抽出するために、ウェブ（すなわちワールドワイドウェブ）を「クロール（ｃｒａｗｌｉｎｇ）」することによって作成される。ウェブをクロールするために、検索エンジンサービスは、ルートウェブページ（ｒｏｏｔ  ｗｅｂ  ｐａｇｅ）のリストを使用して、ルートウェブページを介してアクセス可能なすべてのウェブページの識別を行うことができる。様々な周知の情報検索技術、例えば、ヘッドラインの単語、ウェブページのメタデータに与えられている単語、およびハイライトされている単語などを識別することなどを用いて、あらゆる特定のウェブページのキーワードを抽出する。検索エンジンサービスは、各ウェブページが検索要求にどの程度関連しているかを示す適合度の得点を、各組合せの緊密性、およびウェブページの人気度（例えば、ＧｏｏｇｌｅのＰａｇｅＲａｎｋ）などに基づいて計算することができる。次いで、検索エンジンサービスは、ユーザに、この適合度に基づいた順序で、各ウェブページへのリンクを表示する。より一般的には、検索エンジンは、あらゆるドキュメントの集まりにおける情報検索を可能にする。例えば、ドキュメントの集まりには、すべての米国特許、すべての連邦の法廷意見、会社のすべての保管文書などが含まれる。
【０００３】
ウェブベースの検索エンジンサービスによって提供される検索結果のうちで、最も高い順位のウェブページを、人気のある同一の話題にすべて方向付けることがある。例えば、ユーザが「スピルバーグ（Ｓｐｉｅｌｂｅｒｇ）」という検索語で検索要求を送信する場合、検索結果のうちで最も高い順位のウェブページは、おそらくスティーブン・スピルバーグ（Ｓｔｅｖｅｎ  Ｓｐｉｅｌｂｅｒｇ）に関係するはずである。しかし、ユーザが、スティーブン・スピルバーグに関心が無く、代わりに、同姓の数学の教授のホームページの所在位置を突き止めることに関心がある場合、ウェブページの順位は、ユーザの役には立たない。教授のホームページは、検索結果に含まれているかも知れないが、ユーザは、教授のホームページへのリンクの所在位置を突き止めるために、検索結果のウェブページへのリンクからなるページを何ページも綿密に見る必要がある場合がある。一般に、所望のドキュメントを検索結果の最初のページ上で識別しない場合、ユーザが、所望のドキュメントの所在位置を突き止めることは困難になることがある。さらに、ユーザは、関心のあるドキュメントを探すために、検索結果を複数のページにわたり見る必要がある場合、挫折することがある。
【０００４】
【特許文献１】米国特許出願第＿＿＿号明細書、"Method and System for Calculating Importance of a Block Within a Display Page"、＿＿日出願
【発明の開示】
【発明が解決しようとする課題】
【０００５】
最も高い順位のドキュメントのうちで、より多様な話題を提供する、ドキュメントを順位付けるための技術を有することが望ましく、さらに、このような最も高い順位の各ドキュメントは、その話題に関係する情報内容を非常に豊富に有することが望ましい。
【課題を解決するための手段】
【０００６】
システムは、情報の豊富さおよび話題の多様性に基づいて検索結果のドキュメントを順位付ける。順位付けのシステムにより、検索結果のドキュメントをそれらの関連性に基づいてグループ化し、ドキュメントを同様な話題に関連付けることを意味する。順位付けのシステムにより、最も高い順位のドキュメントには、各トピックに及ぶ少なくとも１つのドキュメントを含み得るように、ドキュメントを順位付ける。次いで、順位付けのシステムにより、最も高い順位のドキュメントのうちの１つとして、グループ内で最も豊富な情報を有するドキュメントを、各グループから選択する。
【発明を実施するための最良の形態】
【０００７】
情報の豊富さおよび話題の多様性に基づいて検索結果のドキュメントを順位付ける方法およびシステムを提供する。一実施形態では、順位付けのシステムは、検索結果に含まれる各ドキュメントの情報の豊富さを決定する。情報の豊富さは、ドキュメントがその話題に関係する情報をどの程度含むのかを示す尺度である。情報の豊富さが高いドキュメント（例えばウェブページ）は、同一の話題に関係し、情報の豊富さがより低いドキュメントの情報を含む情報を含むことがありそうであろう。順位付けのシステムは、検索結果のドキュメントをそれらの関連性に基づいてグループ化し、ドキュメントは同様な話題に関連付けられることを意味する。順位付けのシステムにより、最も高い順位のドキュメントには、各話題に及ぶ少なくとも１つのドキュメントを含むことができ、すなわち、各グループから１つのドキュメントを含むことができ得るように、ドキュメントを順位付ける。順位付けのシステムは、グループ内でドキュメントに属する情報の豊富さが最も高いドキュメントを、各グループから選択する。ドキュメントを順位付けの順序でユーザに提示する場合、ユーザは、おそらく、検索結果の最初のページで、人気のある単一の話題だけよりもむしろ、様々な話題に及ぶドキュメントを見つけるであろう。例えば、検索要求が、検索語の「スピルバーグ」を含む場合、検索結果の最初のページ上のある１つのドキュメントは、スティーブン・スピルバーグに関係しているとともに、最初のページ上の別のドキュメントは、スピルバーグ教授に関係していることが可能である。このようにして、検索結果の最初のページで多様性のある話題に及ぶドキュメントをユーザに提示する可能性は高くなり、また、関心のある話題が検索要求に関係する最も人気のある話題ではない場合でも、ユーザが挫折する可能性は低くなる。さらに、順位付けのシステムは、情報の豊富さがより低いドキュメントよりも、情報の豊富さがより高いドキュメントを順位付けるので、ユーザは、検索結果の最初のページで提示されるドキュメントのうちから所望の情報を見つける可能性が高くなる。
【０００８】
一実施形態では、順位付けのシステムは、類似度の図式に基づいて、検索結果のドキュメントの情報の豊富さを計算する。類似度は、１つのドキュメントの情報が、別のドキュメントの情報に、どの程度含まれているかを示す尺度である。例えば、スピルバーグの映画のうちの１つを表面的に説明したドキュメントは、スピルバーグの映画のすべてについて詳しく説明したドキュメントに対して、高い類似度を有することがある。反対に、スピルバーグの映画のすべてについて詳しく説明したドキュメントは、スピルバーグの映画のうちの１つを表面的に説明したドキュメントに対して、比較的低い類似度を有する可能性がある。大きく異なる話題に関係するドキュメントは、互いに類似度を有していないはずである。他のすべてのドキュメントに対する各ドキュメントの類似度の集まりにより、類似度の図式を表現する。ドキュメントに対して高い類似度を有する他の多数のドキュメントがあるドキュメントは、高い情報の豊富さを有することがありそうであろう。理由は、そのドキュメントの情報は他の多数のドキュメントの情報を含むからである。さらに、高い類似度を有するこれらの他のドキュメントが、ドキュメント自体に比較的高い情報の豊富さをも有する場合、ドキュメントの情報の豊富さは、さらに高い。
【０００９】
一実施形態では、順位付けのシステムは、類似度の図式をやはり使用して、検索結果で高い順位のドキュメントの多様性を得る助けとなる。順位付けのシステムは、従来技術の順位付けの技術（例えば適合度）、情報の豊富さの技術、または他のいくつかの順位付けの技術に基づいたドキュメントの初期の順位の得点を有することができる。初めに、順位付けのシステムは、最も高い初期の順位の得点を有するドキュメントを、最も高い最終順位の得点を有するドキュメントとして選択する。次いで、順位付けのシステムは、選択したドキュメントに対して高い類似度を有する各ドキュメントの順位の得点を減少させる。それらのドキュメントの内容は、選択したドキュメントにおそらく含まれている冗長な情報であるので、順位付けのシステムは、順位の得点を減少させる。次いで、順位付けのシステムは、次に最も高い順位の得点を有するドキュメントを残りのドキュメントから選択する。順位付けのシステムは、新しく選択したドキュメントに対して高い類似度を有する各ドキュメントの順位の得点を減少させる。順位付けのシステムは、所望の個数のドキュメントが最終順位の得点を得る、すべてのドキュメントが最終順位の得点を得る、または、他の何らかの終了条件が満たされるまで、このプロセスを繰り返す。一実施形態では、多様性とは、ドキュメントの集まりにおける異なる話題の数を表現し、集まりにおけるドキュメントの情報の豊富さは、集まり全体に対するドキュメントの情報を提供する度合いを意味している。
【００１０】
情報の豊富さと多様性との組合せではなくて、情報の豊富さのみまたは多様性のみに基づいて、検索結果のドキュメントを順位付けることができることは当事業者には理解されよう。検索エンジンサービスは、例えば、同様の話題に関係するドキュメントのグループを識別し、そのグループ内の各ドキュメントの情報の豊富さを決定することにより、情報の豊富さのみを用いることがある。次いで、検索エンジンサービスは、決定した情報の豊富さをドキュメントの順位付けの計算に入れ、グループで最も高い情報の豊富さを有するドキュメントを、グループ内の他のドキュメントよりも高く順位付けることがありそうにすることがある。検索エンジンサービスは、例えば、同様の話題に関係するドキュメントのグループを識別し、各グループからの少なくとも１つのドキュメントを、その情報の豊富さに関わらず、検索結果として高く順位付け得ることによって、多様性のみを用いることがある。例えば、検索エンジンサービスは、検索結果の最初のページに、各グループから、グループのうちで最も高い適合度を有するドキュメントを表示するように選択することができる。
【００１１】
類似度の図式では、ドキュメントをノードとして表現し、類似度の値を、ノードの間の有向のエッジの重みとして表現する。順位付けのシステムでは、各ドキュメントを、ドキュメントの集まり内の他のすべてのドキュメントにマッピングする正方行列によって、類似度の図式を表現する。順位付けのシステムは、行列の要素の値を、対応するドキュメントの類似度に設定する。Ｍを行列とする場合、Ｍｉｊは、ドキュメントｊに対するドキュメントｉの類似度を表現する。順位付けのシステムは、各ドキュメントをベクトルとして表現することにより、ドキュメントの類似度を計算する。ベクトルは、ドキュメントの情報内容を表現する。例えば、各ベクトルは、ドキュメントの最も重要な２５個のキーワードを含むことができる。順位付けのシステムは、次の式に従って、類似度を計算することができる。
【００１２】
【数１】
0004845420.tif 000002
【００１３】
ただし、ａｆｆ（ｄｉ，ｄｊ）は、ドキュメントｄｊに対するドキュメントｄｉの類似度であり、ｄｉは、ドキュメントｄｉのベクトルを表現し、ｄｊは、ドキュメントｄｊのベクトルを表現し、
【００１４】
【数２】
0004845420.tif 000003
【００１５】
は、ベクトルｄｉの長さを表現する。式１では、類似度を、ｄｊからｄｉへの射影の長さに設定する。類似度は、異なる多くの方法で定義することができることは、当事業者には理解されよう。例えば、別のドキュメントに対するひとつのドキュメントの類似度を、その他のドキュメントのキーワードにおいて、そのひとつのドキュメントのキーワードが占める割合に基づいて定義することができる。他のドキュメントに対するひとつのドキュメントの類似度は、集合論の用語では、２つのドキュメントの積集合のキーワード数を、その他のドキュメント内のキーワード数で割ったものとして表現することができる。行列Ｍの各要素は、類似度の図式において、ひとつのドキュメントのノードからその他のドキュメントのノードへの有向のエッジを表現する。一実施形態では、順位付けのシステムは、類似度の閾値（例えば、２）未満の類似度の値を零に設定する。概念上、類似度が低い場合、類似度の図式において、ひとつのドキュメントのノードからその他のドキュメントのノードへの有向のエッジが存在しないことを意味する。類似度の行列は、次の式で表現する。
【００１６】
【数３】
0004845420.tif 000004
【００１７】
ただし、Ｍｉｊは、行列の要素であり、ａｆｆｔは、類似度の閾値である。ノードの間に多数のエッジを有するノードのグループは、単一の話題を表現する可能性がある。理由は、グループ内のドキュメントの多くが、互いに閾値の類似度よりも大きい類似度を有するからである。対照的に、ノードの間にリンクを有していないノードは、異なる話題に方向付けられたドキュメントを表現する。
【００１８】
順位付けのシステムは、類似度の図式に対して、エッジ（ｅｄｇｅ）解析のアルゴリズムを適用することによって、各ドキュメントの情報の豊富さを計算する。順位付けのシステムは、各行の値の合計が１になるよう類似度の行列を正規化する。正規化された類似度の行列は、次の式で表現する。
【００１９】
【数４】
0004845420.tif 000005
【００２０】
ただし、
【００２１】
【数５】
0004845420.tif 000006
【００２２】
は、正規化された類似度の行列の要素である。順位付けのシステムは、次の式に従って情報の豊富さを計算する。
【００２３】
【数６】
0004845420.tif 000007
【００２４】
ただし、ＩｎｆｏＲｉｃｈ（ｄｉ）は、ドキュメントｄｉの情報の豊富さである。したがって、情報の豊富さは、帰納的に定義される。式４は、次の式により行列の形式で表現することができる。
【００２５】
【数７】
0004845420.tif 000008
【００２６】
ただし、λ＝［ＩｎｆｏＲｉｃｈ（ｄｉ）］ｎ×ｌは、正規化された類似度の行列
【００２７】
【数８】
0004845420.tif 000009
【００２８】
の固有ベクトルである。正規化された類似度の行列
【００２９】
【数９】
0004845420.tif 000010
【００３０】
は、通常、疎行列であるので、場合によっては、すべてが零である行が、行列の中に現れることがあり、いくつかのドキュメントは、いくつかのドキュメントに対して重要な類似度を有する他のドキュメントがないことを意味する。順位付けのシステムは、意味のある固有ベクトルを計算するために、ドキュメントの人気度に基づくドキュメントの順位とすることができる、ダンピング因子（ｄｕｍｐｉｎｇ  ｆａｃｔｏｒ）（例えば、８５）を使用する。ダンピング因子を用いた情報の豊富さは、次の式で表現する。
【００３１】
【数１０】
0004845420.tif 000011
【００３２】
ただし、ｃは、ダンピング因子であり、ｎは、集まりの中のドキュメントの数である。式６は、次のように行列の形式で表現することができる。
【００３３】
【数１１】
0004845420.tif 000012
【００３４】
ただし、
【００３５】
【数１２】
0004845420.tif 000013
【００３６】
は、すべての成分が１に等しい単位ベクトルである。情報の豊富さの計算は、情報のフローおよびシンク（ｓｉｎｋ）モデルから類推することができる。このモデルでは、情報が、各反復でノードの間を流れる。ドキュメントｄｉには、次によって表現される類似度を有するドキュメントの集合Ａ（ｄｉ）がある。
【００３７】
Ａ（ｄｉ）＝｛ｄｊ｜∀ｊ≠ｉ，ａｆｆ（ｄｉ，ｄｊ）＞ａｆｆｔ｝      （８）
各反復において、情報を、以下の規則のうち１つに従って流すことができる。
１．  確率ｃ（すなわち、ダンピング因子）で、情報は、Ａ（ｄｉ）のうちの１つのドキュメントに流れ込み、ドキュメントｄｊに流れ込む確率は、ａｆｆ（ｄｉ，ｄｊ）に比例する。
２．  １−ｃの確率で、情報は、集まり内のあらゆるドキュメントに無作為に流れ込む。
【００３８】
上述のプロセスからマルコフ連鎖を帰納することができ、状態はドキュメントによって与えられ、推移（すなわち、フロー）行列は、
【００３９】
【数１３】
0004845420.tif 000014
【００４０】
によって与えられる。ただし、
【００４１】
【数１４】
0004845420.tif 000015
【００４２】
である。各状態の定常確率分布は、推移行列の主固有ベクトルによって与えられる。
【００４３】
一実施形態では、順位付けのシステムは、同一の話題に方向付けられる複数のドキュメントが、他の話題に方向付けられるドキュメントを排除して、すべてが高く順位付けられないよう、情報の豊富さと類似性のペナルティを組合せることによって、類似度の順位を計算する。類似性のペナルティの使用により、最も高い順位の複数のドキュメントの間における話題の多様性が増大する。順位付けのシステムは、切望の反復アルゴリズムを使用して、類似性のペナルティを計算することができ、ドキュメントの初期の類似度の順位を、ドキュメントの情報の豊富さに設定する。各反復では、アルゴリズムは、その次に最も高い類似度の順位を有するドキュメントを選択し、同一の話題に方向付けられるドキュメントの類似度の順位を、類似性のペナルティによって減少させる。したがって、ドキュメントを選択した後、同一の話題に方向付けられる他のすべてのドキュメントが減少された類似度の順位を有することにより、最も高い順位のドキュメントが様々な話題を表す機会を向上させるであろう。順位付けのシステムは、次の式に従って、ドキュメントの類似度の順位を減少させることができる。
【００４４】
【数１５】
0004845420.tif 000016
【００４５】
ただし、ＡＲｊはドキュメントｊの類似度の順位を表現し、ｉは選択されたドキュメントである。類似性のペナルティは、類似度の行列に基づくので、ドキュメントが選択したドキュメントに類似しているほど、ドキュメントの類似性のペナルティは大きくなる。
【００４６】
一実施形態では、順位付けのシステムは、全体の順位を生成するために、類似度の順位と、テキストベースの順位（例えば、従来技術の適合度）とを組合せることができる。順位付けを、得点または順位に基づいて組合せることができる。組合せた得点に関して、ドキュメントの最終得点を表現する全体的な得点を得るために、テキストベースの得点を類似度の順位と組合せる。組合せた得点は、テキストベースの得点と類似度の順位との線形結合に基づくことができる。得点は異なるオーダの大きさを有するので、順位付けのシステムは得点を正規化する。組合せた得点は、次の式で表現することができる。
【００４７】
【数１６】
0004845420.tif 000017
【００４８】
ただし、α＋β＝１であり、Θは検索要求ｑに対する検索結果を表現し、Ｓｉｍ（ｑ，ｄｉ）は検索要求ｑに対するドキュメントｄｉの類似性を表現し、
【００４９】
【数１７】
0004845420.tif 000018
【００５０】
であり、
【００５１】
【数１８】
0004845420.tif 000019
【００５２】
である。
【００５３】
組合せた順位に関して、ドキュメントの最終順位を得るために、テキストベースの順位を、類似度の順位と組合せる。組合せた順位は、テキストベースの順位と類似度の順位との線形結合に基づくことができる。組合せた順位は、次の式で表現することができる。
【００５４】
【数１９】
0004845420.tif 000020
【００５５】
ただし、Ｓｃｏｒｅは、検索要求ｑに対するドキュメントｄｉの最終順位を表現し、
【００５６】
【数２０】
0004845420.tif 000021
【００５７】
は、テキストベースの順位を表現し、
【００５８】
【数２１】
0004845420.tif 000022
【００５９】
は、類似度の順位を表現する。結合のアルゴリズムの中のαおよびβの両方は、調整可能なパラメータである。α＝１かつβ＝０の場合、再順位付けは実行されず、検索結果は、テキストベースの検索に基づいて順位付けされる。β＞αの場合、再順位付けを行う際に、類似度の順位付けに、より重みがかけられる。β＝１かつα＝０の場合、類似度の順位付けだけに基づいて、再順位付けが行われる。
【００６０】
図１は、一実施形態における類似度の図式を例示する図である。類似度の図式１００には、ノード１１１〜１１５、ノード１２１〜１２４、およびノード１３１を含み、各々はドキュメントを表現する。ノードの間の有向のエッジは、別のノードに対するひとつのノードの類似度を示す。例えば、ノード１１１は、ノード１１５に対する類似度を有するが、ノード１１５は、ノード１１１に対する類似度を有していない（または閾値のレベルを下回る類似度を有する）。この例では、ノードグループ１１０は、同一の話題に方向付けられたノード１１１〜１１５を含む。理由は、このノードグループのノードの間には多数のエッジが存在するからである。同様に、ノードグループ１２０は、同一の話題に方向付けられたノード１２１〜１２４を含む。ノードグループ１３０には、１つのノードしかないのは、このノードが、他のどのノードに対しても類似度を有しておらず、このノードに対する類似度を有するノードもないからである。ノード１１５は、おそらくノードグループ１１０のすべてのノードのうちで最も高い情報の豊富さを有し、ノード１２４は、おそらくノードグループ１２０のすべてのノードのうちで最も高い情報の豊富さを有する。理由はは、各ノードは、ノードに対する類似度を有するノードの数が最も多いからである。
【００６１】
図２は、一実施形態における順位付けのシステムのコンポーネントを例示するブロック図である。順位付けのシステム２００は、データストア２０１〜２０４、およびコンポーネント２１１〜２１６を含む。ドキュメントストア２０１は、ドキュメントの集まりを収容するが、このストアは、インターネットを介して利用可能なすべてのウェブページを表現する場合もある。類似度の図式を生成するコンポーネント２１１は、ドキュメントストアのドキュメントに基づいて類似度の図式を生成する。類似度の図式を生成するコンポーネントは、類似度の図式ストア２０２内に類似度を格納する。情報の豊富さを計算するコンポーネント２１２は、類似度の図式ストアからの類似度の図式を入力し、各ドキュメントの情報の豊富さの得点を計算する。このコンポーネントは、計算した情報の豊富さの得点を、情報の豊富さストア２０３に格納する。一実施形態では、類似度の図式を生成するコンポーネント、および情報の豊富さを計算するコンポーネントは、検索を実施するのに先立って、類似度の図式および情報の豊富さの得点を生成するためにオフラインで実行することができる。検索を実施するコンポーネント２１３は、ユーザからの検索要求を受信し、ドキュメントストアのドキュメントから検索結果を識別する。検索を実施するコンポーネントは、検索結果を、検索要求に対する検索結果の各ドキュメントの適合度の表示と共に検索結果ストア２０４に格納する。類似性のペナルティを計算するコンポーネント２１４は、類似性ペナルティを計算して、検索結果ストア、類似度の図式ストア、および情報の豊富さストアの情報に基づく類似度の順位に適用する。類似度の順位を計算するコンポーネント２１５は、検索結果の中にある各ドキュメントの類似度の順位を生成する。類似度の順位を計算するコンポーネントは、ドキュメントの情報の豊富さ、類似度の図式ストア、および検索結果を計算に入れる。最終得点を計算するコンポーネント２１６は、類似度の順位と適合度の得点とを組合せて、最終得点を計算する。
【００６２】
順位付けのシステムが実装されるコンピューティングデバイスには、中央処理装置、メモリ、入力装置（例えば、キーボード、ポインティングデバイス）、出力装置（例えば、表示装置）、および記憶装置（例えば、ディスク装置）が含まれる。メモリおよび記憶装置は、順位付けのシステムを実装する命令を含むことができるコンピュータ可読媒体である。さらに、データ構造およびメッセージ構造は、通信リンク上の信号などのデータ伝送媒体を介して格納または伝送することができる。様々な通信リンク、例えば、インターネット、ＬＡＮ、ＷＡＮ、または、ポイントツーポイントのダイヤルアップ接続などを使用することができる。
【００６３】
順位付けのシステムは、様々な動作環境で実装することができる。使用するのに適切となり得る、周知の様々なコンピューティングシステム、環境、および構成には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラム可能家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、および、あらゆる上述のシステムまたは装置を含む分散コンピューティング環境などが含まれる。
【００６４】
１つまたは複数のコンピュータまたは他の装置によって実行される、プログラムモジュールなどコンピュータ実行可能命令の一般的コンテキストにおいて、順位付けのシステムを説明することができる。一般に、プログラムモジュールには、特定のタスクを実行または特定の抽象データ型などを実装する、ルーチン、プログラム、オブジェクト、コンポーネント、およびデータ構造などが含まれる。一般に、様々な実施形態において、プログラムモジュールの諸機能を、所望に応じて、結合または分散することができる。
【００６５】
図３は、一実施形態における順位付けのシステムの全体的な処理を例示する流れ図である。順位付けのシステムには、検索結果を表現することができるドキュメントの集まりが提供される。ブロック３０１では、コンポーネントが、ドキュメントの集まりについての類似度の図式を構成する。コンポーネントは、オフラインでドキュメントの集成の中にあるすべてのドキュメント（例えば、すべてのウェブページ）に及ぶ、またはリアルタイムで集まりのドキュメントのみに及ぶ類似度の図式を構成することができる。ブロック３０２では、コンポーネントは、集まりの各ドキュメントの情報の豊富さを計算する。ブロック３０３では、コンポーネントは、集まりのドキュメントを順位付けし、次いで完了となる。
【００６６】
図４は、一実施形態における類似度の図式を構成するコンポーネントの処理を例示する流れ図である。コンポーネントは、ドキュメントの集まりが伝わり、これらのドキュメントについての類似度の図式を構成する。ブロック４０１〜４０３では、コンポーネントは、ドキュメント集まりの中にある各ドキュメントについてのドキュメントベクトルを生成するループを実行する。ブロック４０１では、コンポーネントは、集まり内の次のドキュメントを選択する。決定ブロック４０２では、集まり内のすべてのドキュメントを既に選択した場合、ブロック４０４に進み、そうでなければ、ブロック４０３に進む。ブロック４０３では、コンポーネントは、選択されたドキュメントに対するドキュメントベクトルを生成し、次いで、集まり内の次のドキュメントを選択するためにブロック４０１へのループを実行する。ブロック４０４〜４０８では、コンポーネントは、集まり内のドキュメントの各組についての類似度を計算する。ブロック４０４では、コンポーネントは、第１のドキュメントから開始し、集まりの中にある次のドキュメントを選択する。決定ブロック４０５では、すべてのドキュメントが既に選択された場合、コンポーネントは、類似度の図式を返し、そうでない場合、ブロック４０６に進む。ブロック４０６〜４０８では、コンポーネントは、集まりの各ドキュメントを選ぶループを実行する。ブロック４０６では、コンポーネントは、第１のドキュメントから開始し、集まりの中にある次のドキュメントを選択する。決定ブロック４０７では、集まり内のすべてのドキュメントが既に選ばれた場合、コンポーネントは、集まり内の次のドキュメントを選択するためにブロック４０４へのループを実行し、そうでない場合、ブロック４０８に進む。ブロック４０８では、コンポーネントは、式１に従って（ブロック４０６で）選んだドキュメントに対する（ブロック４０４で）選択されたドキュメントの類似度を計算し、次いで、集まり内の次のドキュメントを選ぶブロック４０６へのループを実行する。
【００６７】
図５は、一実施形態におけるドキュメントを順位付けるコンポーネントの処理を例示する流れ図である。コンポーネントには、類似度の図式が生成され、各ドキュメントの情報の豊富さが計算されたドキュメントの集まりを伝える。ブロック５０１〜５０３では、コンポーネントは、集まり内の各ドキュメントの類似度の順位を、その情報の豊富さに初期設定するループを実行する。ブロック５０１では、コンポーネントは、集まり内の次のドキュメントを選択する。決定ブロック５０２では、すべてのドキュメントを既に選択した場合、ブロック５０４に進み、そうでない場合、ブロック５０３に進む。ブロック５０３では、コンポーネントは、選択したドキュメントの類似度の順位を、選択したドキュメントの情報の豊富さに設定し、集まり内の次のドキュメントを選択するブロック５０１へのループを実行する。ブロック５０４〜５０８では、コンポーネントは、ドキュメントの組を識別し、類似性のペナルティによって類似度の順位を調整するループを実行する。ブロック５０４では、コンポーネントは、次に最も高い類似度の順位を有するドキュメントを選択する。決定ブロック５０５では、終了条件に到達した場合、コンポーネントは、順位付けしたドキュメントを返し、そうでない場合、ブロック５０６に進む。ブロック５０６〜５０８では、コンポーネントは、ドキュメントを選び、類似性のペナルティにより類似度を調整するループを実行する。ブロック５０６では、コンポーネントは、選ばれたドキュメントから選択されたドキュメントへの類似度についての類似度の図式において、零以外の値で指示されるように、選択されたドキュメントに対する類似度を有する、次のドキュメントを選ぶ。決定ブロック５０７では、このようなドキュメントがすべて既に選ばれた場合、コンポーネントは、次に最も高い類似度の順位を有するドキュメントを選択するブロック５０４へのループを実行する。ブロック５０８では、コンポーネントは、式１０に従って、類似性のペナルティによって選ばれたドキュメントに対する類似度の順位を調整する。次いで、コンポーネントは、選択されたドキュメントに対する類似度を有する次のドキュメントを選ぶブロック５０６へのループを実行する。
【００６８】
本明細書では、例示の目的のために、順位付けのシステムの特定の実施形態について説明したが、本発明の精神および範囲から逸脱することなく様々な変形形態を構成することができることは当事業者には理解されよう。一実施形態では、順位付けのシステムは、ドキュメントごとではなくブロックごとを基礎にして類似度および情報の豊富さを計算することができる。ブロックは、単一の話題に一般的に関係するウェブページの情報を表現する。ウェブページの順位付けは、そのウェブページに対するブロックの重要度に部分的に基づくことができる。ブロックの重要度に関しては文献に記載されている（例えば、特許文献１参照。この文献を参照により本明細書に援用する。）。したがって、本発明は添付の特許請求の範囲を除いて限定されるものではない。
【図面の簡単な説明】
【００６９】
【図１】一実施形態における類似度の図式を例示する図である。
【図２】一実施形態における順位付けのシステムのコンポーネントを例示するブロック図である。
【図３】一実施形態における順位付けのシステムの全体的な処理を例示する流れ図である。
【図４】一実施形態における類似度の図式を構成するコンポーネントの処理を例示する流れ図である。
【図５】一実施形態におけるドキュメントを順位付けるコンポーネントの処理を例示する流れ図である。
【図１】
0004845420.tif 000033
【図２】
0004845420.tif 000034
【図３】
0004845420.tif 000035
【図４】
0004845420.tif 000036
【図５】
0004845420.tif 000037