(57)【要約】  入力クエリと格納されたクエリとの間の意味的相関を、これらのクエリの時間的相関に基づいて判定する方法。実施形態は、入力クエリと格納されたクエリとの間の相関係数のフォーマル計算を含む。代替実施形態は、相関係数の精度をほとんどまたはまったく犠牲にせずに、リデュースドデータモデルおよび効率的なデータ検査を使用して相関係数を計算する方法を含む。
2008541228.tif 000002
【特許請求の範囲】
【請求項１】
２つの検索エンジンクエリの間の意味的関係を判定する方法であって、
（ａ）前記２つの検索エンジンクエリのクエリデータを正規化するステップと、
（ｂ）前記ステップ（ａ）で正規化された前記クエリデータに基づいて前記２つのクエリの間の意味的相関を識別するステップと
を含むことを特徴とする方法。
【請求項２】
前記２つの検索エンジンクエリの前記データは、前記２つの検索エンジンクエリの頻度に関係する時間的データであることを特徴とする請求項１に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項３】
クエリ頻度データの正規化の前記ステップ（ａ）は、離散時間単位内の他のすべての検索エンジンクエリの組み合わされた時間頻度データとの比較において各検索エンジンクエリの時間的クエリ頻度データを測定するステップを含むことを特徴とする請求項１に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項４】
前記２つの検索エンジンクエリの第１クエリは、入力クエリであり、前記２つの検索エンジンクエリの第２クエリは、格納されたクエリであり、前記方法は、閾レベルを超える意味的関係が前記入力クエリと前記格納されたクエリとの間に存在することが判定される場合に、ユーザまたは広告主に前記格納されたクエリを提案するステップをさらに含むことを特徴とする請求項１に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項５】
前記２つのクエリの間の意味的相関の識別の前記ステップ（ｂ）は、ビットストリングによって前記２つの検索エンジンクエリ頻度の前記データを表し、前記２つの検索エンジンクエリを表す前記ビットストリング内の対応するビットが互いに一致する度合を調べるステップを含むことを特徴とする請求項１に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項６】
前記２つのクエリの間の意味的相関の識別の前記ステップ（ｂ）は、前記第１クエリの正規化された頻度を表す第１ベクトルと前記第２クエリの正規化された頻度を表す第２ベクトルとのドット積を計算するステップを含むことを特徴とする請求項１に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項７】
２つの検索エンジンクエリの間の意味的関係を判定する方法であって、
（ａ）前記２つの検索エンジンクエリのそれぞれをビットストリングによって表すステップと、
（ｂ）前記２つの検索エンジンクエリを表す前記ビットストリング内の対応するビットが互いに一致する度合に基づいて前記２つの検索エンジンクエリの間の意味的相関を識別するステップと
を含むことを特徴とする方法。
【請求項８】
前記２つの検索エンジンクエリの前記データは、前記２つの検索エンジンクエリの頻度に関係する時間的データであることを特徴とする請求項７に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項９】
前記２つの検索エンジンクエリのそれぞれをビットストリングによって表す前記ステップ（ａ）は、１２８ビットストリングによって前記２つの検索エンジンクエリのそれぞれを表すステップを含むことを特徴とする請求項７に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項１０】
前記２つの検索エンジンクエリのクエリｑは、入力クエリであり、前記２つの検索エンジンクエリのクエリｐは、格納されたクエリであることを特徴とする請求項７に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項１１】
閾レベルを超える意味的関係が前記入力クエリと前記格納されたクエリとの間に存在することが判定される場合に、ユーザに前記格納されたクエリを提案するステップをさらに含むことを特徴とする請求項１０に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項１２】
前記２つの検索エンジンクエリの間の相関係数を計算するステップをさらに含み、前記相関係数は、前記２つの検索エンジンクエリの間の意味的関係の度合を示すことを特徴とする請求項１０に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項１３】
前記２つの検索エンジンクエリのそれぞれをビットストリングによって表す前記ステップ（ａ）は、複数の超平面を生成するステップと、前記２つの検索エンジンクエリの第１検索エンジンクエリの前記ビットストリング内のビットを生成するステップとを含み、前記ビットは、前記超平面の１つに直交する第１ベクトルと前記第１検索エンジンクエリを表す第２ベクトルとのドット積によって決定されることを特徴とする請求項７に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項１４】
（ｃ）第１および第２のビットストリングの分数内の対応するビットのある部分が互いに一致するかどうかを識別するために、前記ビットストリングのそれぞれのビットの前記分数をスキャンするステップと、
（ｄ）前記ステップ（ｃ）で、前記第１および第２のビットストリングの前記分数内の対応するビットのある部分が互いに一致すると判定される場合に、対応について前記ビットストリング内の残りのビットをスキャンするステップと
をさらに含むことを特徴とする請求項７に記載の２つの検索エンジンクエリの間の意味的関係を判定する方法。
【請求項１５】
（ａ）複数の検索エンジンクエリのそれぞれのクエリ頻度データを正規化するステップと、
（ｂ）前記ステップ（ａ）で正規化された前記クエリデータを、前記複数の検索エンジンクエリのそれぞれについて１つのビットストリングがある、めいめいのビットストリングとして表すステップと、
（ｃ）前記複数の検索エンジンクエリのうちで、前記複数の検索エンジンクエリの基準検索エンジンクエリに対する第１閾レベルを超える相関を有する１つまたは複数の検索エンジンクエリを選択するステップと
を含むことを特徴とするコンピュータ実行可能命令を有するコンピュータ可読媒体。
【請求項１６】
選択の前記ステップ（ｃ）は、
（ｉ）互いに一致する前記ビットストリングの分数内の対応するビットのある部分を有する前記１つまたは複数の検索エンジンクエリを識別するために、前記複数の検索エンジンクエリに関連する前記ビットストリングのそれぞれのビットの前記分数をスキャンするステップと、
（ｉｉ）前記基準検索エンジンクエリに対する前記第１閾レベルを超える相関を有する前記１つまたは複数の検索エンジンクエリを識別するために前記１つまたは複数の検索エンジンクエリをスキャンするステップと
を含むことを特徴とする請求項１５に記載のコンピュータ実行可能命令を有するコンピュータ可読媒体。
【請求項１７】
前記複数の検索エンジンクエリに関連する前記ビットストリングのそれぞれのビットの分数をスキャンする前記ステップ（ｉ）は、前記ビットストリングのそれぞれの２０ビットをスキャンするステップを含むことを特徴とする請求項１６に記載のコンピュータ実行可能命令を有するコンピュータ可読媒体。
【請求項１８】
前記ステップ（ａ）で正規化された前記クエリデータをめいめいのビットストリングとして表す前記ステップ（ｂ）は、複数の超平面を生成するステップと、前記複数の検索エンジンクエリの第１検索エンジンクエリの前記ビットストリング内のビットを生成するステップとを含み、前記ビットは、前記超平面の１つに直交する第１ベクトルと前記第１検索エンジンクエリを表す第２ベクトルとのドット積によって決定されることを特徴とする請求項１５に記載のコンピュータ実行可能命令を有するコンピュータ可読媒体。
【請求項１９】
前記１つまたは複数の検索クエリをユーザに提案するステップをさらに含むことを特徴とする請求項１５に記載のコンピュータ実行可能命令を有するコンピュータ可読媒体。
【請求項２０】
前記基準検索エンジンクエリと前記１つまたは複数の検索エンジンクエリとの間の相関係数を計算するステップをさらに含み、前記相関係数は、前記２つの検索エンジンクエリの間の意味的関係の度合を示すことを特徴とする請求項１５に記載のコンピュータ実行可能命令を有するコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、意味的に関係する検索エンジンクエリを見つける方法を対象とする。
【背景技術】
【０００２】
オンライン検索エンジンは、構造化された区別する方式で、インターネット上で入手可能な膨大な量の情報にアクセスする非常に強力なツールを提供する。ＭＳＮ（登録商標）、Ｇｏｏｇｌｅ（登録商標）、およびＹａｈｏｏ！（登録商標）などの人気のある検索エンジンは、毎日情報に関する数千万件のクエリをサービスしている。通常の検索エンジンは、検索エンジンインデックスのエントリを作成するためにワールドワイドウェブ上のウェブページから情報を集めるスパイダ（「クローラ」または「ボット」とも称する）と、読み取られたウェブページからインデックスを作成するインデクシングプログラムと、検索クエリを受け取り、そのクエリをインデックス内のエントリと比較し、検索クエリに適当な結果を返す検索プログラムとを含む、プログラムの調整されたセットによって動作する。
【０００３】
検索エンジンテクノロジの分野での重要な研究の現在の領域は、所与の検索クエリに関する結果の効率および品質をどのように改善するかである。いわゆるコンセプトベース検索は、入力検索クエリに意味的に非常に関係する代替検索クエリを識別し、提案するために、様々な検索判断基準に対する統計分析を使用することを用いる。代替の非常に相関する検索クエリの識別は、所与の検索に関する検索結果に焦点を合わせ、その検索結果を改善するのを助けることができる。さらに、会社および広告主は、特定のクエリが入力される時に広告を提示する。そのような会社および広告主にとって、彼らの広告を特定のクエリならびに他の意味的に関係するクエリに関連付けることは、極端に有益であるはずである。
【０００４】
コンセプトベース検索を使用する従来技術システムの例では、クエリが、めいめいのクエリで返される結果が同一である度合に応じて互いに相関される。したがって、第１および第２のクエリがほぼ同一の検索結果を返す場合に、この２つのクエリは、互いに非常に相関すると考えられる。コンセプトベース検索の例が、非特許文献１に示されている。
【０００５】
コンセプトベース検索のもう１つの例は、関連する検索クエリのインジケータとしてクリックスルーデータを調べる。このモデルは、異なる検索クエリの結果からクリックされたリンクを点検する。２つの異なるクエリが、ユーザによる同一ＵＲＬのクリックにつながる場合に、この２つのクエリは、非常に相関すると考えられる。クリックスルーコンセプトベース検索の例が、非特許文献２に開示されている。
【０００６】
もう１つの有望な意味ベース検索テクノロジは、指定された時間シーケンスにわたるパターン、トレンド、および周期性を明らかにするために入力クエリ自体を分析することに関する。例えば、その全体が参照によって本明細書に組み込まれている非特許文献３（以下では「Ｖｌａｃｈｏｓ他」と呼称する）がある。Ｖｌａｃｈｏｓ他は、異なるイベントが、異なる時間的検索頻度を有することに気付いた。例えば、クエリ「ｃｉｎｅｍａ（映画）」の頻度は、毎週末にピークを有するが、クエリ「Ｅａｓｔｅｒ（イースター）」の頻度は、毎年春に単一のピークを築き、その後、急速に低下する。時間的相関の背後にある理論は、２つの検索クエリが十分に類似する時間的パターンを示す場合に、それらのクエリが、意味的に関係する可能性が高いということである。Ｖｌａｃｈｏｓ他は、検索エンジン（彼らの研究ではＭＳＮ（登録商標））に関連する１つまたは複数のサーバに格納されたクエリログを使用して、実際のクエリごとに時系列を作成し、この時系列の要素は、そのクエリが所与の日に検索された回数である。
【０００７】
フーリエ分析を使用して、Ｖｌａｃｈｏｓ他は、フーリエ係数によって経時的なクエリのレートの時間的周期性を表し、次に、時系列マッチング技法を適用して、非常に類似する時間的パターンを有する他のクエリを識別する。彼らが使用するマッチング技法は、フーリエ係数の間のユークリッド距離に基づいて時間的類似性を測定する。このフレームワークの下で、彼らは、各クエリの複数の最良のフーリエ係数を使用して所与のクエリに最も似たクエリを見つける手法を説明している。
【０００８】
検索エンジンクエリの時間的パターンは、経時的に変化する。例えば、検索の量は、夜間より日中の方が多く、検索の量は、週末より平日の方が多い。意味的クエリ一致の識別を試みるモデルは、２つの検索の間で偽りの高い相関を有する場合がある。というのは、この経時的な自然変動が考慮に入れられていないからである。例えば、図１は、１カ月の期間にわたって毎日の基礎で測定された２つの異なる検索クエリの発生の回数のサンプルグラフである。第１のプロットｎａは、第１のクエリの発生の回数であり、第２のプロットｎｂは、第２のクエリの発生の回数である。この図からわかるように、両方のプロットが、平日に対して相対的に減った、週末での発生を示す。意味的に関係する検索クエリを見つける通常の時間モデルの下では、この種の平行して減少する週末のアクティビティは、この２つのクエリの間の相関が実際には経時的な検索クエリの自然変動に起因する可能性がある時であっても、この２つのクエリの間の偽りの高い意味的相関につながる場合がある。
【０００９】
【非特許文献１】H. Daume and E. Brill, entitled, "Web Search Intent Induction via Automatic Query Reformulation," published for the Human Language Technology Conference/North American Chapter of the Association for Computational Linguistics (HTL/NAACL), Boston, MA (2004)
【非特許文献２】D. Beeferman and A. Berger, entitled, "Agglomerative Clustering of a Search Engine Query Log," published for the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, MA (2000)
【非特許文献３】Vlachos, M., Meek, C., Vagena, Z. and Gunopulos, D. published a paper entitled, "Identifying Similarities, Periodicities and Bursts for Online Search Queries" for the International Conference on Management of Data (SIGMOD), Paris, France (2004)
【非特許文献４】P. Indyk and R. Motwani, entitled "Approximate nearest neighbors: Towards removing the curse of dimensionality," for the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas (1998)
【非特許文献５】W. Johnson and J. Lindenstrauss, entitled, "Extensions of Lipschitz Maps Into a Hilbert Space," published in Contemporary Mathematics, 26:189-206 (1984)
【非特許文献６】M. Goemans and D. Williamson, entitled, "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming," presented in the Journal of the ACM (JACM), 42(6):1115-1145 (1995)
【発明の開示】
【００１０】
本発明の実施形態は、時間的相関に基づいて入力クエリと格納されたクエリとの間の意味的相関を判定する方法を提供する。実施形態は、入力クエリと格納されたクエリとの間の相関係数のフォーマル計算を含む。代替実施形態は、相関係数の精度をほとんどまたはまったく犠牲にしない、リデュースドデータモデル（ｒｅｄｕｃｅｄ  ｄａｔａ  ｍｏｄｅｌ）および効率的なデータ検査を使用する相関係数の計算の方法を含む。
【００１１】
ｄ個の時間単位にわたるクエリｑの頻度関数は、ｄ次元ベクトルＹｑ＝（Ｙｑ，１，．．．，Ｙｑ，ｄ）である。各離散時間単位でのクエリ頻度Ｙｑ，ｉは、第ｉ時間単位中のクエリｑの正規化された頻度である。正規化された頻度（すなわち、所与の時間単位中に受け取られる他のすべてのクエリと比較したクエリｑの頻度）を使用することによって、経時的なクエリストリーム量の自然変動の影響が取り除かれるように正規化される。
【００１２】
フォーマルプロセスは、すべての時間単位およびすべての受け取られたクエリに関して正規化されたクエリ頻度関数Ｙｑ，ｉを格納する。各クエリの正規化された頻度関数の平均値および標準偏差を使用することによって、任意の２つのクエリの間の相関係数を判定することができる。２つのクエリに関する、閾値を超える相関係数は、意味があると考えられ、それらのクエリの間の時間的意味的相関を示す。
【００１３】
相関係数の計算にフォーマル法を使用することによって、ｎ個のクエリおよびｄ個の時間単位を有するクエリストリームは、合計ｄｎ個の正規化された頻度関数値について、クエリあたりｄ個の頻度値を格納することを必要とし、すべての格納されたクエリとの入力クエリの相関係数の判定が望まれるたびに、このデータのすべてにまたがる線形パスをも必要とする。代替実施形態は、エンベッディングおよび最近近傍アルゴリズムの理論からの技法を利用して、クエリごとの正規化された頻度関数をより少ないデータを用いて表すことを可能にする。リデュースドデータモデルを使用する相関係数の計算は、より短い処理時間での入力クエリと他のクエリとの間の相関係数の正確な推定をももたらし、相関係数のリアルタイム計算を可能にする。
【００１４】
リデュースドデータモデルは、ｄ次元のユークリッド実空間
【００１５】
【数１】
2008541228.tif 000003
【００１６】
内のすべての格納されたクエリについて正規化された頻度関数の単一クエリ頻度ベクトル
【００１７】
【数２】
2008541228.tif 000004
【００１８】
を定義することによって、リデュースド（減らされた）データを用いてクエリ頻度関数を表す。クエリ頻度ベクトルのそれぞれは、各クエリ頻度ベクトル
【００１９】
【数３】
2008541228.tif 000005
【００２０】
をδビットのストリング
【００２１】
【数４】
2008541228.tif 000006
【００２２】
として表す写像
【００２３】
【数５】
2008541228.tif 000007
【００２４】
への入力として使用することができる。このビットストリングすなわちエンベッディング
【００２５】
【数６】
2008541228.tif 000008
【００２６】
内のδビットそれぞれの値（１または０）は、エンベッディングの理論を使用し、ランダム超平面を使用して判定される。特定のクエリｑについて、エンベッディング
【００２７】
【数７】
2008541228.tif 000009
【００２８】
の第ｊビットの値は、ベクトル
【００２９】
【数８】
2008541228.tif 000010
【００３０】
がランダム超平面のどちら側にあるかによって規定され、この超平面は、ランダムに生成される超平面に直交するベクトルｒｊによって表すことができる。生成される超平面の個数δは、各クエリ頻度関数を正確に表すエンベッディング
【００３１】
【数９】
2008541228.tif 000011
【００３２】
を作るために超平面のほぼ均一な分布をもたらすのに十分に大きい。
【００３３】
リデュースドデータモデルでは、入力クエリｑと任意の格納されたクエリｐとの間の相関係数は、エンベッディング
【００３４】
【数１０】
2008541228.tif 000012
【００３５】
と
【００３６】
【数１１】
2008541228.tif 000013
【００３７】
との間の対応するビット１からδまでのうちで同一であるビットの分数によって推定される。一致する対応するビットの個数が多いほど、クエリｑとｐとの間の相関係数は、大きく、クエリは、より強く時間的に相関する。
【００３８】
すべてのクエリ頻度関数の表現が生成され、格納されたならば、入力クエリとすべてのそのような格納されたクエリとの間の相関を判定することができる。格納されたデータのすべてにまたがる線形パスを行うことが可能ではあるが、本発明の実施形態は、相関するクエリを見つけるのに要する処理時間を減らす、ある方式を採用する。これは、検査されるクエリの個数を、所定の相関係数閾値を超える相関を有する可能性が高いクエリだけに制限することによって達成することができる。
【００３９】
そのような実施形態では、格納されたクエリｐのそれぞれは、そのエンベッディング
【００４０】
【数１２】
2008541228.tif 000014
【００４１】
の最初のｋビットに基づいて、本明細書でバケットと称するバッファ位置に編成される。その後、入力クエリｑを受け取る時に、処理ユニットは、ｑのビットストリング
【００４２】
【数１３】
2008541228.tif 000015
【００４３】
を含むバケット内ならびにｑのビットストリングを含むバケットと一致する所定の個数のビットを有するバケット内のビットストリング
【００４４】
【数１４】
2008541228.tif 000016
【００４５】
だけを調べる。
【発明を実施するための最良の形態】
【００４６】
これから、図２〜１１を参照して本発明の実施形態を説明するが、図２〜１１は、一般に、意味的に関係する検索エンジンクエリを見つける方法に関係する。本発明の実施形態による方法は、クエリが時間的に相関する場合にクエリが意味的に関係するというアイデアに少なくとも部分的に基づく。すなわち、異なる検索クエリの人気が、経時的に一緒に増加し、減少する傾向がある場合に、これらのクエリは、互いに意味的に関係する可能性が高い。したがって、本発明の実施形態は、所与の検索クエリに時間的に相関するクエリを識別する。
【００４７】
実施形態で、本発明は、クエリの頻度ではなく、特定の時刻の特定のクエリの密度を分析する。密度とは、その特定の時刻の他のすべてのクエリと比較した、あるクエリの頻度である。この手法は、検索エンジン量の自然変動によって引き起こされる量の変化によって導入される誤差を取り除くように正規化する。さらに、偽陽性をよりよく把握するために、共分散ではなく、頻度関数の相関を比較する。さらに、このアルゴリズムを実用的にするために、実際の相関ではなく近似相関を見つけるために近似アルゴリズムを使用する。この近似アルゴリズムは、相関の精度をほとんどまたはまったく犠牲にせずに、意味的に関係するクエリを見つけるのに必要なストレージスペースおよび必要な処理時間を大幅に減らす。
【００４８】
本明細書で説明する方法は、様々な処理システムで実行することができる。図２に、本発明を実施できる適切な一般的なコンピューティングシステム環境１００の例を示す。コンピューティングシステム環境１００は、適切なコンピューティング環境の１つの例に過ぎず、本発明の使用または機能性の範囲に関する限定を提案することは意図されていない。コンピューティングシステム環境１００を、例示的なコンピューティングシステム環境１００に示されたコンポーネントのいずれかまたはその組合せに関する依存性または要件を有するものと解釈してもならない。
【００４９】
本発明は、多数の他の汎用のまたは特殊目的のコンピューティングシステム、コンピューティング環境、またはコンピューティング構成と共に動作する。本発明と共に使用するのに適切である可能性がある周知のコンピューティングシステム、コンピューティング環境、および／またはコンピューティング構成の例は、パーソナルコンピュータ、サーバコンピュータ、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラマブル消費者電子製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、ラップトップおよびパームコンピュータ、ハンドヘルドデバイス、上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境、および類似物を含むが、これらに限定はされない。
【００５０】
本発明を、コンピュータによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の全体的な文脈で説明することができる。一般に、プログラムモジュールは、特定のタスクを実行するか特定の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造体などを含む。本発明は、通信ネットワークを介してリンクされるリモート処理デバイスによってタスクが実行される分散コンピューティング環境で実践することもできる。分散コンピューティング環境では、プログラムモジュールを、メモリストレージデバイスを含む、ローカルコンピュータ記憶媒体とリモートコンピュータ記憶媒体との両方に配置することができる。
【００５１】
図２を参照すると、本発明を実施する例示的なシステムは、コンピュータ１１０の形の汎用コンピューティングデバイスを含む。コンピュータ１１０のコンポーネントは、処理ユニット１２０と、システムメモリ１３０と、システムメモリを含む様々なシステムコンポーネントを処理ユニット１２０に結合するシステムバス１２１とを含むが、これらに限定はされない。システムバス１２１は、メモリバスまたはメモリコントローラ、周辺バス、および様々なバスアーキテクチャのいずれかを使用するローカルバスを含む複数のタイプのバス構造のいずれかとすることができる。限定ではなく例として、そのようなアーキテクチャに、Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、Ｅｎｈａｎｃｅｄ  ＩＳＡ（ＥＩＳＡ）バス、Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ（ＶＥＳＡ）ローカルバス、およびメザニンバスとも称するＰｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バスが含まれる。
【００５２】
コンピュータ１１０には、通常は、様々なコンピュータ可読媒体が含まれる。コンピュータ可読媒体は、コンピュータ１１０によってアクセスすることができるすべての使用可能な媒体とすることができ、コンピュータ可読媒体には、揮発性媒体と不揮発性媒体との両方、取外し可能媒体と取外し不能媒体との両方が含まれる。限定ではなく例として、コンピュータ可読媒体に、コンピュータ記憶媒体および通信媒体を含めることができる。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造体、プログラムモジュール、または他のデータなどの情報を記憶する任意の方法またはテクノロジで実施される、揮発性と不揮発性との両方、取外し可能と取外し不能との両方の媒体が含まれる。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリテクノロジ、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、または他の光学ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、または他の磁気ストレージデバイス、あるいは所望の情報を格納するのに使用することができ、コンピュータ１１０によってアクセスすることができるすべての他の媒体が含まれるが、これに限定はされない。通信媒体は、通常、搬送波または他のトランスポート機構などの変調されたデータ信号内でコンピュータ可読命令、データ構造体、プログラムモジュール、または他のデータを実施し、通信媒体は、すべての情報配信媒体を含む。用語「変調されたデータ信号」は、信号内で情報を符号化する形でその特性の１つまたは複数を設定または変更された信号を意味する。限定ではなく例として、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体と、音響、ＲＦ、赤外線、および他の無線媒体などの無線媒体を含む。上記のいずれかの組合せも、コンピュータ可読媒体の範囲に含まれる。
【００５３】
システムメモリ１３０には、読み取り専用メモリ（ＲＯＭ）１３１およびランダムアクセスメモリ（ＲＡＭ）１３２などの揮発性および／または不揮発性のメモリの形のコンピュータ記憶媒体が含まれる。起動中などにコンピュータ１１０内の要素の間での情報の転送を助ける基本ルーチンを含む基本入出力システム１３３（ＢＩＯＳ）が、通常はＲＯＭ  １３１に格納される。ＲＡＭ  １３２には、通常は、即座にアクセス可能であるおよび／または処理ユニット１２０によって現在操作されているデータおよび／またはプログラムモジュールが含まれる。限定ではなく例として、図２に、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７を示す。
【００５４】
コンピュータ１１０には、他の取外し可能／取外し不能の揮発性／不揮発性コンピュータ記憶媒体を含めることもできる。例としてのみ、図２に、取外し不能不揮発性磁気媒体から読み取るかこれに書き込むハードディスクドライブ１４１、取外し可能不揮発性磁気ディスク１５２から読み取るかこれに書き込む磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭまたは他の光学媒体などの取外し可能不揮発性光ディスク１５６から読み取るかこれに書き込む光学ディスクドライブ１５５が図示されている。この例示的オペレーティング環境で使用することができる他の取外し可能／取外し不能の揮発性／不揮発性コンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭ、および類似物が含まれるが、これに限定はされない。ハードディスクドライブ１４１は、通常は、インターフェース１４０などの取外し不能メモリインターフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光学ディスクドライブ１５５は、通常は、インターフェース１５０などの取外し可能メモリインターフェースによってシステムバス１２１に接続される。
【００５５】
上で述べ、図２に図示したドライブおよびそれに関連するコンピュータ記憶媒体は、コンピュータ１１０のコンピュータ可読命令、データ構造、プログラムモジュール、および他のデータのストレージを提供する。図２では、例えば、ハードディスクドライブ１４１が、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７を格納するものとして図示されている。これらのコンポーネントを、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同一または異なるのいずれかとすることができる。オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７は、最低限でもこれらが異なるコピーであることを示すために、本明細書では異なる符号を与えられている。ユーザは、キーボード１６２および通常はマウス、トラックボール、またはタッチパッドと称するポインティングデバイス１６１などの入力デバイスを介してコンピュータ１１０にコマンドおよび情報を入力することができる。他の入力デバイス（図示せず）に、マイクロホン、ジョイスティック、ゲームパッド、衛星放送受信用パラボラアンテナ、スキャナ、または類似物を含めることができる。上記および他の入力デバイスは、しばしば、システムバスに結合されたユーザ入力インターフェース１６０を介して処理ユニット１２０に接続されるが、パラレルポート、ゲームポート、またはｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ（ＵＳＢ）などの、他のインターフェースおよびバス構造によって接続されることが可能である。モニタ１９１または他のタイプのディスプレイデバイスも、ビデオインターフェース１９０などのインターフェースを介してシステムバス１２１に接続される。モニタの他に、コンピュータに、スピーカ１９７およびプリンタ１９６など、出力周辺インターフェース１９５を介して接続することができる他の周辺出力デバイスをも含めることができる。
【００５６】
コンピュータ１１０は、リモートコンピュータ１８０などの１つまたは複数のリモートコンピュータへの論理接続を使用して、ネットワーク化された環境で動作することができる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の一般的なネットワークノードとすることができ、通常は、コンピュータ１１０に関して上で説明した要素の多数またはすべてを含むが、図２にはメモリストレージデバイス１８１だけが図示されている。図２に示された論理接続には、ローカルエリアネットワーク（ＬＡＮ）１７１および広域ネットワーク（ＷＡＮ）１７３が含まれるが、他のネットワークを含めることもできる。そのようなネットワーキング環境は、オフィス、会社全体のコンピュータネットワーク、イントラネット、およびインターネットでありふれたものである。
【００５７】
ＬＡＮネットワーキング環境で使用される場合に、コンピュータ１１０は、ネットワークインターフェースまたはネットワークアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーキング環境で使用される場合に、コンピュータ１１０には、通常は、インターネットなどのＷＡＮ１７３を介する通信を確立する、モデム１７２または他の手段が含まれる。モデム１７２は、内蔵または外付けとすることができるが、ユーザ入力インターフェース１６０または他の適当な機構を介してシステムバス１２１に接続することができる。ネットワーク化された環境では、コンピュータ１１０に関して示されたプログラムモジュールまたはその諸部分を、リモートメモリストレージデバイスに格納することができる。限定ではなく例として、図２に、メモリデバイス１８１に常駐するものとしてリモートアプリケーションプログラム１８５を示す。図示のネットワーク接続が、例示的であり、コンピュータの間の通信リンクを確立する他の手段を使用することができることを了解されたい。
【００５８】
図３は、本発明を実施できるソフトウェアモジュールおよびデータ構造を含む検索処理環境３００のブロック図である。検索処理環境３００は、上で説明したコンピューティングシステム環境１００と共におよび／またはその一部として動作することができる。検索処理環境３００は、３つの主要な要素を有するクローラベースのシステムとすることができる。第１の要素は、クローラ３０２とも呼ばれるスパイダである。スパイダは、ウェブページ３９０ａ、３９０ｂを訪れ、それを読み取り、次に、サイト内の他のページへのリンクに従う。スパイダは、変更を探すために、規則的な基礎でそのサイトに戻る。すべてのウェブクローラによって実行される基本アルゴリズムは、その入力としてシードＵＲＬのリストをとり、繰り返して、ＵＲＬリストからＵＲＬを除去し、そのホスト名のＩＰアドレスを判定し、対応する文書をダウンロードし、それに含まれるすべてのリンクを抽出する。抽出されたリンクのそれぞれについて、そのリンクを絶対ＵＲＬに変換し（必要な場合に）、そのリンクに前に出会っていない場合にはダウンロードすべきＵＲＬのリストに追加する。望まれる場合に、ダウンロードされた文書を他の形で処理する（例えば、その内容にインデックスを付ける）。
【００５９】
スパイダが見つけたすべてのものが、検索エンジンの第２部分すなわちインデックス３０６に送られる。インデックス３０６は、時々カタログと呼ばれるが、スパイダが見つけたすべてのウェブページのコピーを含むリポジトリである。ウェブページが変化した場合に、このブックが、新しい情報によって更新される。インデックスは、データストア３１０に格納される。
【００６０】
検索処理環境３００の第３の部分は、検索エンジン３１２である。これは、インデックスに記録された数百万ページを調べて、検索との一致を見つけ、最も関連すると思われる順番でランキングするプログラムである。インデックスを介する検索は、ユーザがクエリを作成することと、そのクエリを検索エンジンを介してサブミットすることとを含む。クエリは、非常に単純である可能性があり、最低限で単一の単語である可能性があり、あるいは、一連の単語または句である場合がある。より複雑なクエリの作成も、ユーザが検索の条件を洗練し、拡張することを可能にするブール演算子の使用によって可能である。
【００６１】
実際には、コンピューティングデバイス３２５のユーザは、クライアントサイドのウェブブラウザ３１６およびホストサイドのウェブサーバ３１４を介して検索処理環境３００にアクセスする。通信リンクがクライアントとホストとの間で確立されたならば、コンピューティングデバイス３２５のユーザは、上で説明したようにクエリ検索を実行することができる。
【００６２】
本発明の実施形態によれば、検索処理環境３００には、さらに、相関エンジン３５０を含めることができる。相関エンジン３５０は、コンピューティングデバイス３２５のユーザによって入力されたクエリに意味的に関係するクエリを識別でき、その意味的に関係するクエリを下で説明するある形でユーザに提示できるソフトウェアモジュールである。相関エンジンは、検索エンジン３１２と通信して、入力クエリを受け取る。相関エンジンは、データストア３１０内で維持されるクエリデータベース３５２とも通信する。クエリデータベース３５２は、後で説明するように本発明によって使用される、過去のクエリに関するすべての生の頻度データならびに正規化されたクエリデータおよび他のパラメータを格納する。また、相関エンジンは、ウェブサーバと通信して、識別された意味的に関係する検索クエリをデバイス３２５のユーザに提示することができ、あるいは、検索結果の洗練において助けることができる。
【００６３】
図４は、例えばデバイス３２５のユーザによって入力された、可能な入力検索クエリｑの正規化されたクエリ頻度関数Ｙｑである。正規化されたクエリ頻度は、離散時間単位ｄの総数にまたがって測定される。ｄ個の時間単位にまたがるクエリｑの頻度関数は、ｄ次元ベクトルＹｑ＝（Ｙｑ，１，．．．，Ｙｑ，ｄ）である。クエリｑは、例えばＭＳＮ（登録商標）Ｓｅａｒｃｈなどのオンライン検索エンジンを使用して検索できる、上で説明した任意のクエリである。本明細書で使用される時に、入力クエリおよびその表現は、一般に、文字「ｑ」を用いて参照され、格納されたクエリおよびその表現は、一般に、文字「ｐ」を用いて参照される。本発明の実施形態によれば、特定の時間単位内のあるクエリの頻度Ｙｑ，ｉは、ランダム変数とみなすことができ、２つのクエリの間の類似性は、後で説明するように、その頻度関数の相関係数によって与えられる。
【００６４】
各離散単位でのクエリ頻度Ｙｑ，ｉは、第ｉ時間単位中のクエリｑの正規化された頻度である。クエリｑの頻度Ｙｑ，ｉは、上で説明したように正規化される。すなわち、正規化された頻度Ｙｑ，ｉは、単純にクエリｑが第ｉ時間単位中に検索された回数ではない。そうではなく、正規化された頻度Ｙｑ，ｉは、
【００６５】
【数１９】
2008541228.tif 000017
【００６６】
によって与えられ、ここで、ｎｑ，ｉは、第ｉ時間単位中のクエリｑの発生の回数であり、Ｎｉは、第ｉ時間単位中のクエリの総数である。「背景技術」セクションで示したように、クエリストリーム量は、経時的に自然に変化する。クエリ頻度の上の定義は、クエリの密度すなわち、所与の時間期間内にクエリｑが他のすべてのクエリと比較してどれほど頻繁に入力されたかである。これは、クエリストリーム量の経時的な自然変動の影響を取り除くように正規化し、単に時間単位あたりのクエリの総数が特定の期間中すなわち夜間と比較して日中、週末と比較して平日中により多いのでクエリのある対が偽りの高い相関を示すことを防ぐ。すべてのクエリについて正規化された頻度を使用することによって、本発明の実施形態は、２つのクエリの間の真の相関をより正確に計算できるようになる。
【００６７】
入力クエリｑと格納されたクエリｐとの間の相関係数を計算するフォーマルプロセスを、図５の流れ図を参照して説明する。入力クエリと他のクエリとの間の相関を判定するために、複数の離散時間単位にわたって測定された正規化されたクエリデータの表現が、クエリデータベース３５２に格納される。一実施形態で、正規化されたクエリデータは、例えば、１年の期間にわたって１日１回集めることができる。しかし、様々な実施形態で、個々の離散時間単位を、秒、分、時、日、週、月、または年とすることができる。さらなる代替実施形態で、個々の離散時間単位を、１秒より短く、１年より長く、またはその間の任意の離散時間期間とすることができる。様々な実施形態で、検討されるそのような離散時間単位の総数は、１時間分、１日分、１週間分、１カ月分、１年分、または１０年分とすることができる。さらなる代替実施形態で、検討されるそのような離散時間単位の総数を、１時間未満分、１０年超分、またはその間の任意の時間期間分とすることができる。
【００６８】
図５の流れ図に示された一実施形態で、クエリデータベース３５２内で維持される正規化されたクエリデータの表現を、リアルタイムで生成することができる、すなわち、クエリデータベース内のエントリを、離散時間単位の総数（例えば、１年）のすべての離散時間単位（例えば、１日）ごとに１回更新することができる。そのような実施形態では、ステップ２００で、所与の時間単位ｉのすべての検索クエリの生データログをデータベース３５２から取り出す。このログは、通常、ある時間期間にわたって検索エンジン３１２によって受け取られるすべてのクエリについて維持される。ステップ２０２で、離散時間単位ｉの検索クエリのこのログから、その時間単位中の各クエリの密度Ｙｑ，ｉが、相関エンジン３５０によって判定される。上で示したように、ある時間単位中の各クエリの密度Ｙｑ，ｉは、
【００６９】
【数２０】
2008541228.tif 000018
【００７０】
によって与えられ、ここで、ｎｑ，ｉは、第ｉ時間単位中のクエリｑの発生の回数であり、Ｎｉは、第ｉ時間単位中のクエリの総数である。
【００７１】
本発明の一実施形態では、ステップ２０４で、ある離散時間単位中のすべてのクエリの密度をクエリデータベース３５２に格納することができる。後で説明するように、このデータを格納するステップは、本発明を実行するアプリケーションの代替実施形態で省略することができる。
【００７２】
引き続き図４および５を参照すると、ステップ２０６で、すべての時間期間ｉのクエリ頻度のランニングカウントを計算し、格納する。この値は、すべてのクエリの正規化されたクエリ頻度Ｙｑの平均頻度μ（Ｙｑ）を計算するのに使用される。平均頻度μ（Ｙｑ）は、
【００７３】
【数２１】
2008541228.tif 000019
【００７４】
によって与えることができ、ここで、ｉは、各離散時間単位を表し、ｄは、その時点までの時間単位ｉの総数を表す。
【００７５】
すべての時間期間ｉのクエリ頻度のランニングカウントは、すべてのクエリの正規化されたクエリ頻度Ｙｑの標準偏差σ（Ｙｑ）を計算するのにも使用することができる。標準偏差σ（Ｙｑ）は、
【００７６】
【数２２】
2008541228.tif 000020
【００７７】
によって与えることができる。
【００７８】
ステップ２１０で、望みの個数の時間単位のデータのすべてを収集したならば、データ収集プロセスが終了する。そうでない場合には、相関エンジン３５０は、ステップ２１２で次の時間単位ｉの経過を待ち、その後、相関エンジンは、次の時間単位に入手されるデータの計算および格納のためにステップ２００に戻る。図５は、データのリアルタイム収集を説明するものである。実施形態が、その代わりに、データベース３５２に格納されたクエリ頻度の過去のログを使用して、上で説明したようにすべてのクエリの正規化されたクエリ頻度を生成し、格納することができることを理解されたい。
【００７９】
図５に示されているように各クエリの正規化されたクエリ頻度データが各離散時間単位について生成され、格納されたならば、任意の２つのクエリｐとｑとの間の時間的相関を示す、クエリｐとｑとの間の相関係数λを計算することができる。したがって、クエリｑがステップ２１４（図６）で検索エンジンに入力される場合に、クエリｑと任意の他の格納されたクエリｐとの間の時間的相関を、ステップ２１６で計算することができる。クエリｐとｑとの間の相関係数は、
【００８０】
【数２３】
2008541228.tif 000021
【００８１】
によって与えられる。
【００８２】
相関係数λは、１と−１との間の範囲にまたがる。強く時間的に相関するクエリｑおよびｐは、λの大きい値を有するはずであり、完全に相関するクエリｑおよびｐは、１の相関係数を有する。逆に相関するクエリｑおよびｐは、負の相関係数を有するはずであり、相関しないクエリｑおよびｐは、０の相関係数を有するはずである。
【００８３】
上で示したように、各クエリの純粋な頻度ではなく正規化された頻度関数を使用することは、クエリストリーム量の経時的な自然変動の影響を取り除くように正規化し、単に時間単位あたりのクエリの総数がある時間期間中により多いのでクエリのある対が偽りの高い相関を示すことを防ぐ。さらに、上で説明した形での相関係数の測定は、類似性のもう１つの一般的な尺度である共分散ではなく、頻度関数の相関を使用する。共分散は、頻度関数の分散について正規化することができず、したがって、高い分散を有するクエリは、誤って、多数の他のクエリに時間的に関係するように見える。
【００８４】
図５および６に示されているように、任意の２つのクエリの間の相関係数を、相関エンジン３５０によって、正規化されたクエリの格納されたデータＹｑ，ｉおよびＹｐ，ｉならびにＹｑおよびＹｐのそれぞれの平均頻度および頻度の標準偏差と一緒に上で説明した式を使用して計算することができる。しかし、ｎ個のクエリおよびｄ個の時間単位を有するクエリストリームについて、これは、ｄｎ個の正規化された頻度関数値を格納することを必要とし、入力クエリの相関係数を判定することが望まれるたびにこのデータのすべてにまたがる線形パスをも必要とする。
【００８５】
この方法を、本発明の実施形態で使用することができるが、代替のリデュースドデータモデルは、エンベッディングおよび最近近傍アルゴリズムの理論からの技法を利用して、処理ユニット１２０がはるかに少ないデータおよびはるかに少ないストレージスペースを用いて各クエリの正規化された頻度関数を表すことを可能にする。この代替方法は、相関エンジン３５０が、入力クエリとすべての他のクエリとの間の相関係数を、このリデュースドデータからより短い処理時間で正確に推定することをも可能にし、相関係数のリアルタイム計算を可能にする。
【００８６】
本発明に従ってデータを減らす方法を、図７〜９を参照して説明する。一般に、リデュースドデータモデルは、すべての時間単位に関する各クエリ頻度関数を、例えば１２８ビットの格納されたストリングとして表すことを用いる。その場合に、任意の２つのクエリ頻度関数の間の相関係数は、２つのクエリ頻度関数を表すビットストリング内の対応するビットが互いに一致する度合によって与えられる。
【００８７】
リデュースドデータモデルのより厳密な数学的説明を、下で示し、検索処理環境３００内でのソフトウェア実装の説明をそれに続ける。エンベッディングの理論は、さらに、参照によってその全体が本明細書に組み込まれている非特許文献４に記載されており、最近近傍アルゴリズムの概念は、参照によってその全体が本明細書に組み込まれている非特許文献５に記載されている。
【００８８】
図７〜９を参照して説明するリデュースドデータ実施形態は、第ｉ時間単位の所与の正規化された入力クエリ頻度Ｙｑ，ｉを、
【００８９】
【数２４】
2008541228.tif 000022
【００９０】
によって与えられるスケーリングされ正規化されたベクトル
【００９１】
【数２５】
2008541228.tif 000023
【００９２】
に写像することができ、これによって記述することができるという事実を利用し、ここで、ｎは、第ｉ時間期間内のクエリの総数と等しい。すべての時間単位ｄにわたるすべてのそのようなベクトル
【００９３】
【数２６】
2008541228.tif 000024
【００９４】
は、ｄ次元のユークリッド実空間
【００９５】
【数２７】
2008541228.tif 000025
【００９６】
内のクエリｑの正規化された頻度関数を表す単一のクエリ頻度ベクトル
【００９７】
【数２８】
2008541228.tif 000026
【００９８】
を定義する。クエリ頻度ベクトル
【００９９】
【数２９】
2008541228.tif 000027
【０１００】
は、原点に第１点を有し、（ｘ１，ｘ２，．．．，ｘｄ）にｄ次元実空間内の第２点を有するベクトルであり、各ｘｉは、ｉ個の時間単位にまたがるクエリｑのスケーリングされ正規化された頻度ベクトル
【０１０１】
【数３０】
2008541228.tif 000028
【０１０２】
のそれぞれによって決定される。
【０１０３】
クエリ頻度ベクトルのそれぞれを使用して、各クエリ頻度ベクトル
【０１０４】
【数３１】
2008541228.tif 000029
【０１０５】
をδビットのストリング
【０１０６】
【数３２】
2008541228.tif 000030
【０１０７】
として表す写像
【０１０８】
【数３３】
2008541228.tif 000031
【０１０９】
を定義することができる。δのために選択される値は、近似の所望の精度の度合に依存するが、最初の次元ｄには依存しない。実施形態で、δを、８０ビットと１６０ビットとの間とすることができ、さらに、１２８ビットとすることができる。代替実施形態で、δのために選択される値を、８０未満または１６０超とすることができることを理解されたい。
【０１１０】
ビットストリング
【０１１１】
【数３４】
2008541228.tif 000032
【０１１２】
内のδ個のビットのそれぞれの値（１または０）は、参照によって組み込まれた非特許文献４および５、ならびに非特許文献６に記載のものに似た形でランダム超平面を使用して決定される。具体的に言うと、写像ｖ（・）は、δ個のランダムベクトル
【０１１３】
【数３５】
2008541228.tif 000033
【０１１４】
によって定義され、このランダムベクトルは、ガウス分布から引き出されたランダムに選択された超平面に対する法線ベクトルと解釈される。特定の入力クエリｑについて、ビットストリング
【０１１５】
【数３６】
2008541228.tif 000034
【０１１６】
の第ｊビットの値は、クエリ頻度ベクトル
【０１１７】
【数３７】
2008541228.tif 000035
【０１１８】
がｊ番目の選択された超平面のどちら側にあるかによって規定される。これは、ドット積
【０１１９】
【数３８】
2008541228.tif 000036
【０１２０】
の符号によって与えられる。このドット積の符号は、
【０１２１】
【数３９】
2008541228.tif 000037
【０１２２】
とｒｊとの間の角度のコサインの符号によって与えられる。ｒｊと
【０１２３】
【数４０】
2008541228.tif 000038
【０１２４】
との間の角度が９０°を超える（負のドット積を示す）場合に、ビットストリング（本明細書では「エンベッディング」とも称する）
【０１２５】
【数４１】
2008541228.tif 000039
【０１２６】
の第ｊビットの値は、０になる。ｒｊと
【０１２７】
【数４２】
2008541228.tif 000040
【０１２８】
との間の角度が９０°未満である（正のドット積を示す）場合に、エンベッディング
【０１２９】
【数４３】
2008541228.tif 000041
【０１３０】
の第ｊビットの値は、１になる。生成される超平面の個数δは、各クエリ頻度関数を正確に表すビットストリング
【０１３１】
【数４４】
2008541228.tif 000042
【０１３２】
を作るための超平面の均等な分布をもたらすのに十分に大きい。
【０１３３】
この概念を、図７および８を参照してさらに詳細に説明するが、図７および８は、クエリｑおよびｐを表すクエリ頻度ベクトルの対
【０１３４】
【数４５】
2008541228.tif 000043
【０１３５】
および
【０１３６】
【数４６】
2008541228.tif 000044
【０１３７】
を示す図である。第１ランダムベクトルｒ１は、ランダムに生成された超平面に対する直交ベクトルとして生成される。ドット積
【０１３８】
【数４７】
2008541228.tif 000045
【０１３９】
は、負の値であり、したがって、ストリング
【０１４０】
【数４８】
2008541228.tif 000046
【０１４１】
の第１ビットは、０である。同様に、ドット積
【０１４２】
【数４９】
2008541228.tif 000047
【０１４３】
は、負の値であり、したがって、ストリング
【０１４４】
【数５０】
2008541228.tif 000048
【０１４５】
の第１ビットは、０である。第２ランダムベクトルｒ２は、第２のランダムに生成された超平面に対する直交ベクトルとして生成される。ドット積
【０１４６】
【数５１】
2008541228.tif 000049
【０１４７】
は、正の値であり、したがって、ストリング
【０１４８】
【数５２】
2008541228.tif 000050
【０１４９】
の第２ビットは、１である。同様に、ドット積
【０１５０】
【数５３】
2008541228.tif 000051
【０１５１】
は、正の値であり、したがって、ストリング
【０１５２】
【数５４】
2008541228.tif 000052
【０１５３】
の第２ビットは、１である。第３ランダムベクトルｒ３は、第３のランダムに生成された超平面に対する直交ベクトルとして生成される。ドット積
【０１５４】
【数５５】
2008541228.tif 000053
【０１５５】
は、正の値であり、したがって、ストリング
【０１５６】
【数５６】
2008541228.tif 000054
【０１５７】
の第３ビットは、１である。しかし、ドット積
【０１５８】
【数５７】
2008541228.tif 000055
【０１５９】
は、負の値であり、したがって、ストリング
【０１６０】
【数５８】
2008541228.tif 000056
【０１６１】
の第３ビットは、０である。ランダムベクトルｒ１からｒδまでを生成し、クエリ頻度ベクトル
【０１６２】
【数５９】
2008541228.tif 000057
【０１６３】
および
【０１６４】
【数６０】
2008541228.tif 000058
【０１６５】
とのドット積をとる、このプロセスは、ストリング
【０１６６】
【数６１】
2008541228.tif 000059
【０１６７】
および
【０１６８】
【数６２】
2008541228.tif 000060
【０１６９】
内のビット１からδまでのそれぞれが１または０のビット値を割り当てられるまで継続される。
【０１７０】
入力クエリｑと任意の格納されたクエリｐとの間の相関係数λは、エンベッディング
【０１７１】
【数６３】
2008541228.tif 000061
【０１７２】
と
【０１７３】
【数６４】
2008541228.tif 000062
【０１７４】
との間で対応するビット１からδまでの同一であるビットの個数によって近似することができる。具体的に言うと、クエリｑとｐとの間の相関係数λは、クエリ頻度ベクトル
【０１７５】
【数６５】
2008541228.tif 000063
【０１７６】
および
【０１７７】
【数６６】
2008541228.tif 000064
【０１７８】
のドット積によって与えられる。これは、ラジアン単位で測定されたこの２つのベクトルの間のコサインすなわちｃｏｓ  θｑｐである。上で説明したエンベッディング法を使用すると、ビットストリング内で互いに一致すると期待される対応するビットの分数は、１−θｑｐ／Πになると期待される。真の相関係数およびビット一致の分数１−θｑｐ／Πによって与えられる相関係数の近似は、互いに同一ではないが、意味的に関係するクエリでは、互いに、相関係数の正確な近似を与えるのに十分に近い。例えば、０．９以上の相関係数λを有するクエリが、関心を持たれていると仮定する。
【０１７９】
θｑｐ＝Ｃｏｓ−１（０．９）＝０．４５ラジアン
１−θｑｐ／Π＝０．８５６
したがって、２つのクエリの間のビット一致の分数が０．８５６以上である場合に、これらのクエリは、０．９以上の相関係数を有し、本発明の実施形態では意味的に関係するクエリと考えられる。
【０１８０】
一致する対応するビットの分数が大きいほど、クエリｑとｐとの間の相関係数の近似がよく、それらのクエリはより強く時間的に相関する。エンベッディング
【０１８１】
【数６７】
2008541228.tif 000065
【０１８２】
および
【０１８３】
【数６８】
2008541228.tif 000066
【０１８４】
でのドット積符号は、ランダムに生成される超平面が、２つのクエリ頻度ベクトル
【０１８５】
【数６９】
2008541228.tif 000067
【０１８６】
と
【０１８７】
【数７０】
2008541228.tif 000068
【０１８８】
との間に含まれる場合に限って一致しないことがわかる。したがって、２つのクエリ頻度ベクトル
【０１８９】
【数７１】
2008541228.tif 000069
【０１９０】
と
【０１９１】
【数７２】
2008541228.tif 000070
【０１９２】
との間の角度が小さいほど、これらがランダム超平面によって二分される可能性は低く、クエリｑおよびｐの相関係数は大きい。
【０１９３】
リデュースドデータモデルは、クエリの間の相関係数の近い近似を、効率的な時間およびスペースの形で正確に判定することを可能にする。エンベッディング
【０１９４】
【数７３】
2008541228.tif 000071
【０１９５】
を１２８ビットとして格納する実施形態では、１６バイトのストレージ位置に各エンベッディングを格納することができる。したがって、例えば４０００００００個のクエリのストレージは、約６４０メガバイトのストレージスペースを占めるのみである。
【０１９６】
上で説明したリデュースドデータ数学演算を実行するソフトウェアステップを、図９を参照して説明する。図９の説明では、所望の離散時間単位１からｄまでのすべてにまたがるすべての検索クエリの生データログが、前の時間期間にとられ、既にデータベース３５２に存在すると仮定する。生データログを、その代わりにリアルタイムで生成できる（すなわち、生データは、前に格納されるのではなく、第ｉ時間単位の経過の後にリアルタイムで記録される）ことを理解されたい。どちらの実施形態でも、前に示したように、生頻度データのログは、通常、所定の時間期間についてデータベース３５２に格納され、維持される。
【０１９７】
図９に関して説明する実施形態では、ステップ２３０で、所与の時間単位ｉのすべての検索クエリの生データログを取り出す。ステップ２３２で、離散時間単位ｉの検索クエリのこのログから、相関エンジン３５０によって、その時間単位中の各格納されたクエリの密度Ｙｐ，ｉを計算する。上で示したように、ある時間単位中の各クエリの密度Ｙｐ，ｉは、
【０１９８】
【数７４】
2008541228.tif 000072
【０１９９】
によって与えられ、ここで、ｎｐ，ｉは、第ｉ時間単位中のクエリｐの発生の回数であり、Ｎｉは、第ｉ時間単位中のクエリの総数である。
【０２００】
ステップ２３６で、すべてのクエリの正規化されたクエリ頻度Ｙｐの平均頻度μ（Ｙｐ）のランニングカウントを計算し、格納することができる。また、ステップ２３８で、すべてのクエリの正規化されたクエリ頻度Ｙｐの標準偏差σ（Ｙｐ）のランニングカウントを計算し、格納することができる。
【０２０１】
本発明の実施形態では、相関エンジン３５０は、ステップ２４０で、時間期間の総数ｄに追加の離散時間期間があるかどうかをチェックする。追加の離散時間期間がある場合には、ｉ＝１からｄまでのＹｐ，ｉのすべての値をすべてのクエリについて計算し終えるまで、ステップ２４２で時間単位を増分し、相関エンジンは、ステップ２３０に戻る。離散時間単位１からｄまでのすべての正規化されたクエリ頻度Ｙｐ，ｉを各クエリについて計算し終えたならば、ステップ２４４で、各クエリの正規化されスケーリングされたクエリ頻度ベクトル
【０２０２】
【数７５】
2008541228.tif 000073
【０２０３】
を計算する。各離散時間期間および各クエリの正規化されたクエリ頻度Ｙｐ，ｉは、格納される必要がない。しかし、代替実施形態では、データリダクション技法が適用される場合であっても、各離散時間期間および各クエリの正規化されたクエリ頻度Ｙｐ，ｉを格納することができる。
【０２０４】
次に、ステップ２４６で、ランダムベクトルｒｊを定義するランダム超平面を生成する。これは、所与の超平面に直交するベクトルｒｊの成分のそれぞれをランダムに生成することによって行われる。すなわち、ベクトルｒｊは、０の平均値および１の分散を有する標準ガウス分布からランダムに選択されたｄ個の値からなる。ステップ２４８で、クエリ頻度ベクトル
【０２０５】
【数７６】
2008541228.tif 000074
【０２０６】
のそれぞれの、ランダムベクトルｒｊとのドット積を計算する。次に、相関エンジンは、ステップ２５０で、クエリ頻度ベクトル
【０２０７】
【数７７】
2008541228.tif 000075
【０２０８】
が特定のランダムベクトルｒｊのどちら側にあるかに応じて、ストリング
【０２０９】
【数７８】
2008541228.tif 000076
【０２１０】
のそれぞれの第ｊビットに０または１を割り当てる。次に、ステップ２５２で、各クエリのストリング
【０２１１】
【数７９】
2008541228.tif 000077
【０２１２】
の更新された値を格納する。次に、相関エンジン３５０は、ステップ２５４で、ストリング
【０２１３】
【数８０】
2008541228.tif 000078
【０２１４】
内のビット１からδまでのそれぞれがビット値を割り当てられたかどうかをチェックする。そうである場合には、データ収集プロセスが終了する。そうでない場合には、ステップ２５６でｊを増分し、相関エンジンは、ステップ２４６に戻って、ビット生成プロセスを継続する。
【０２１５】
当業者が了解するとおり、上で識別されたステップの一部を、代替実施形態では異なる順序で実行することができる。例えば、すべてのストリング
【０２１６】
【数８１】
2008541228.tif 000079
【０２１７】
の第ｊビットを判定し、その後、ｊを増分するのではなく、単一のストリング
【０２１８】
【数８２】
2008541228.tif 000080
【０２１９】
内の各ビットを判定し、その後、このプロセスを残りのすべてのストリング
【０２２０】
【数８３】
2008541228.tif 000081
【０２２１】
について繰り返すことができる。
【０２２２】
図５〜６を参照して説明した実施形態または図７〜９を参照して説明したデータリダクション実施形態のいずれかに従ってすべての頻度クエリデータを格納された状態で、入力されたクエリｑとすべての格納されたクエリｐとの間の相関係数を判定することができる。入力クエリとの閾相関係数を有するすべての格納されたクエリを次に識別するフォーマルモデルを、図１０に関して説明する。ステップ２６０で、クエリｑが入力される時に、ステップ２６２で、それに対応するストリング
【０２２３】
【数８４】
2008541228.tif 000082
【０２２４】
をメモリから取り出すことができる（データリダクション技法によって動作する実施形態で）。次に、ステップ２６４で、すべてのストリング
【０２２５】
【数８５】
2008541228.tif 000083
【０２２６】
内のすべてのビットδにまたがる線形パスを行って、入力クエリと他のすべての格納されたクエリとの間の相関係数λを判定することができる。
【０２２７】
ステップ２６６で、入力されたクエリとの所定の閾値を超える相関係数を有するすべてのクエリを識別する。本発明の実施形態では、相関係数の閾値を、０．８０とすることができる（エンベッディングの対応するビットの０．７９５の一致に変換される）。さらなる実施形態では、相関係数の閾値を、０．９とすることができる（上で説明したエンベッディングの対応するビットの０．８５６の一致に変換される）。入力クエリとのこれらの値以上の相関係数を有する識別されたクエリは、入力されたクエリに対する強い時間的意味的相関を有すると考えることができる。代替実施形態で、相関係数の閾値を、０．８未満または０．９超とすることができることを理解されたい。
【０２２８】
入力クエリに相関する１つまたは複数の検索クエリを識別したならば、ステップ２６８で、これらの結果をユーザに提示することができる。１つまたは複数の相関する検索クエリの提示は、本発明の代替実施形態で、異なって処理することができる。一実施形態で、ユーザに、入力された検索クエリに意味的に相関すると判定された１つまたは複数の検索クエリを見るオプションを与えることができる。代替案では、相関する検索クエリを、プロンプトなしでユーザに提示することができる。もう１つの代替実施形態では、入力クエリとの閾値を超える相関係数を有する格納されたクエリを、入力クエリと共に自動的に検索することができ、その結果を、入力クエリに関する検索結果と一緒に返すことができる。非常に相関する検索クエリの表示は、広告目的にも貴重である可能性がある。
【０２２９】
入力クエリが入力されたならば、すべてのストリング
【０２３０】
【数８６】
2008541228.tif 000084
【０２３１】
内のすべてのビットδにまたがる線形パスが、過剰な時間を要する場合がある。したがって、本発明の実施形態は、精度をほとんどまたはまったく犠牲にせずに、相関するクエリを見つけるのに要する時間を減らす方式を使用する。図１１を参照して説明されるそのような方式は、すべてのクエリｎの格納されたストリング
【０２３２】
【数８７】
2008541228.tif 000085
【０２３３】
を利用する。この方式によれば、アルゴリズムの実行時間は、相関エンジン３５０によって調べられるクエリの個数を、所定の閾値λを超える相関を有する可能性があるクエリだけに制限することによって減らされる。具体的に言うと、エンベッディング
【０２３４】
【数８８】
2008541228.tif 000086
【０２３５】
と
【０２３６】
【数８９】
2008541228.tif 000087
【０２３７】
との最初のｋビットの間で入力クエリｑへの高い相関を有する格納されたクエリｐだけが調べられる。というのは、これらのクエリｐが、クエリｑとの高い相関を有する可能性が最も高いからである。
【０２３８】
このプロセスを、図１１を参照してより詳細に説明する。ステップ２８０で、２ｋ個のバケット（すなわち、メモリバッファ）を割り振る。次に、ステップ２８２で、格納されたクエリｐのそれぞれを、そのエンベッディング
【０２３９】
【数９０】
2008541228.tif 000088
【０２４０】
の最初のｋビットによって示されるバケットに編成する。すなわち、同一の最初のｋビットを有するすべてのストリングを、同一バケットに編成する。本発明の実施形態では、ｋを、１０ビットと３０ビットとの間とすることができ、さらに、１５ビットと２５ビットとの間とすることができ、さらに、本発明の一実施形態では２０ビットとすることができる。
【０２４１】
ステップ２８４で、入力クエリｑを受け取る時に、処理ユニットは、ステップ２８６で、ｑのエンベッディング
【０２４２】
【数９１】
2008541228.tif 000089
【０２４３】
を含むバケット（すなわち、ｑのバケット内のすべてのストリング）ならびにｑのエンベッディング
【０２４４】
【数９２】
2008541228.tif 000090
【０２４５】
を含むバケットに近いものとして定義されたバケット内のエンベッディング
【０２４６】
【数９３】
2008541228.tif 000091
【０２４７】
だけを調べる。バケットｂ’は、バケットｂ’のｋ個のビットのある分数ρがクエリｑを含むバケットｂの対応するビットと一致する場合に、バケットｂに近いと定義される。本発明の実施形態では、ρは、相関係数λ以下とすることができる。０．９の相関係数λについて、ρは、０．６と０．９との間の範囲にわたるものとすることができ、あるいはその代わりに、０．７と０．８との間の範囲にわたるものとすることができ、あるいはその代わりに、本発明の実施形態では０．８５とすることができる。本発明の代替実施形態で、ρを、０．６未満、０．９超、および相関係数λを超えるものとすることができることを理解されたい。
【０２４８】
ステップ２８６でバケットｂおよびｂ’を判定した時に、これらのバケットのそれぞれのクエリは、本発明の実施形態で、ステップ２８８でそのビットδのすべてをビットストリング
【０２４９】
【数９４】
2008541228.tif 000092
【０２５０】
と比較されて、最初のｋビットだけを調べることから生じる偽陽性を除去し、実際に相関係数λ以上であるクエリを識別する。相関するクエリが識別されたならば、ステップ２９０で、上で図１０に関して示したように、これらのクエリをユーザに提示することができる。
【０２５１】
クエリｑのバケットおよび近いバケットだけを検索することによって、ビット比較が実行されるクエリの個数が、大幅に減る。例えば、ｋ＝２０かつρ＝０．８５の場合に、任意の所与のバケットについて、２２０＝１０４８５７６個のバケットのうちの１３５１個だけが調べられるはずである。
【０２５２】
ここまでで説明した本発明の実施形態は、所与の時間単位について入ってくるクエリデータを測定する。しかし、異なるタイムゾーンのおかげで、例えば米国の東海岸からのクエリは、同一時刻に検索エンジンの位置に到着する場合であっても、例えば米国の西海岸からのクエリと異なる時刻に送信される。代替実施形態では、クエリがそこから送信される位置のタイムゾーンを、正規化されたクエリ頻度の計算で考慮に入れることができ、その結果、例えば、４ｐｍ  ＥＳＴに送信されたクエリは、異なる時刻に検索エンジンの位置に到着する場合であっても、４ｐｍ  ＰＳＴに送信されたクエリと同一の時間単位に含まれるようになる。
【０２５３】
上で説明した実施形態では、時間単位ｉ中の各クエリの密度Ｙｐ，ｉは、すべての時間単位について格納される。本発明のさらなる実施形態では、本発明の上で説明した方法を、時間単位について各クエリの密度Ｙｐ，ｉを格納せずに実行することができる。具体的に言うと、上で説明したように、ランダムベクトルｒとクエリ頻度ベクトル
【０２５４】
【数９５】
2008541228.tif 000093
【０２５５】
とのドット積の符号を使用して、エンベッディング
【０２５６】
【数９６】
2008541228.tif 000094
【０２５７】
を判定し、これから、相関係数を２つのクエリについて正確に近似することができる。しかし、ｒと
【０２５８】
【数９７】
2008541228.tif 000095
【０２５９】
とのドット積の符号は、クエリ密度Ｙｐ，ｉの過去の値を格納せずに計算することができる。ｒと
【０２６０】
【数９８】
2008541228.tif 000096
【０２６１】
とのドット積は、
【０２６２】
【数９９】
2008541228.tif 000097
【０２６３】
によって与えられる。
【０２６４】
σ（Ｙｑ）の値は、ドット積の符号には影響せず、したがって、ドット積の符号を判定するために必要ではない。したがって、必要なものは、
【０２６５】
【数１００】
2008541228.tif 000098
【０２６６】
の符号であり、これは、
【０２６７】
【数１０１】
2008541228.tif 000099
【０２６８】
と等しい。
【０２６９】
項
【０２７０】
【数１０２】
2008541228.tif 000100
【０２７１】
と
【０２７２】
【数１０３】
2008541228.tif 000101
【０２７３】
との両方を、クエリ密度Ｙｐ，ｉの過去の値を参照せずに計算することができる。最初の項は、Ｙｐ，ｉの新しい値が受け取られる時に計算することができる。第２の項は、時間単位ｉが経過する時に、Ｙｐ，ｉの合計およびｒｉの合計だけを格納することによって計算することができる。したがって、ｒと
【０２７４】
【数１０４】
2008541228.tif 000102
【０２７５】
とのドット積の符号を、クエリ密度Ｙｐ，ｉの過去の値を格納せずに計算することができる。
【０２７６】
上で説明した実施形態では、異なる時間単位ｉの格納されたクエリ密度Ｙｐ，ｉは、正規化されスケーリングされた頻度ベクトル
【０２７７】
【数１０５】
2008541228.tif 000103
【０２７８】
の計算と同様に重みを付けられる。しかし、代替実施形態では、指数関数的に減衰する関数を、より古い時間単位のクエリ密度Ｙｐ，ｉに適用することができ、その結果、より最近の時間単位のクエリ密度が、正規化されスケーリングされた頻度ベクトル
【０２７９】
【数１０６】
2008541228.tif 000104
【０２８０】
の判定においてより大きい重みを与えられるようになる。例えば、現在の時間単位の新しいクエリ密度Ｙｐ，ｉを用いて頻度ベクトル
【０２８１】
【数１０７】
2008541228.tif 000105
【０２８２】
を更新する時に、１未満の乗数（例えば、０．５から０．９９、もう１つの例として０．９）を、現在の時間単位のクエリ密度に加算する前に、すべての過去のクエリ密度の合計に適用することができる。したがって、より古い時間期間からのクエリ密度情報は、頻度ベクトル
【０２８３】
【数１０８】
2008541228.tif 000106
【０２８４】
において、より小さい重みを与えられる。
【０２８５】
上で説明した実施形態では、意味的関係が、時間的相関すなわち、所与の時間単位内の２つのクエリの密度の関係によって判定される。所与の時間単位の密度以外の判断基準を、クエリの間の相関係数および意味的関係の判定の基礎として使用できることを理解されたい。例えば、代替実施形態では、ユーザの母集団内の単一のユーザによって生成されたクエリを、上で説明した本発明による方法を使用して相関させることができる。これは、時間と完全に独立とすることができる。もう１つの実施形態として、特定の時間期間内に単一のユーザによって生成されたクエリを、上で説明した方法を使用して相関させることができる。また、代替実施形態で、本発明の方法を使用して、地理的領域および他の判断基準に基づいてクエリを相関させることができることが企図されている。
【０２８６】
本発明の前述の詳細な説明は、例示および説明のために提示されたものである。網羅的であること、または本発明を開示された正確な形態に限定することは、意図されていない。多数の修正形態および変形形態が、上の教示に鑑みて可能である。説明された実施形態は、本発明の原理および実用的応用例を最もよく説明して、これによって当業者が様々な実施形態でおよび企図される特定の使用に適する様々な変更を加えて本発明を最もよく利用することを可能にするために選択されたものである。本発明の範囲は、添付の特許請求の範囲によって定義されることが意図されている。
【図面の簡単な説明】
【０２８７】
【図１】意味的に関係する検索クエリを見つける従来のシステムで１カ月の期間にわたって測定された２つの異なるクエリの頻度を示すグラフである。
【図２】本発明の実施形態を実施するのに適するコンピュータハードウェアを示すブロック図である。
【図３】図２に示されたコンピュータハードウェアと共におよび／またはその中で動作できるコードおよびデータ構造を含む検索エンジンを示すブロック図である。
【図４】本発明の実施形態によるシステムで複数の離散時間単位にわたって測定された正規化されたクエリデータを示すグラフである。
【図５】本発明の実施形態によるシステムで正規化されたクエリ頻度を生成し、格納するプロセスを示す流れ図である。
【図６】図４の生成され、格納された正規化されたクエリ頻度から相関係数を計算するプロセスを示す流れ図である。
【図７】ランダムベクトルｒｉのガウス分布のサンプルと一緒に、正規化されスケーリングされたベクトル
【数１５】
2008541228.tif 000107
および
【数１６】
2008541228.tif 000108
を示すプロットである。
【図８】ランダムベクトルｒｉに対する関係に基づくエンベッディング
【数１７】
2008541228.tif 000109
および
【数１８】
2008541228.tif 000110
への図６の正規化されスケーリングされたベクトルの写像を示す図である。
【図９】本発明の実施形態による、２つのクエリの相関係数を判定するデータリダクションモデルを示す流れ図である。
【図１０】本発明の実施形態による、相関するクエリを識別するフォーマルプロセスを示す流れ図である。
【図１１】本発明の実施形態による、相関するクエリを識別するリデュースドタイムモデルを示す流れ図である。
【図１】
2008541228.tif 000111
【図２】
2008541228.tif 000112
【図３】
2008541228.tif 000113
【図４】
2008541228.tif 000114
【図５】
2008541228.tif 000115
【図６】
2008541228.tif 000116
【図７】
2008541228.tif 000117
【図８】
2008541228.tif 000118
【図９】
2008541228.tif 000119
【図１０】
2008541228.tif 000120
【図１１】
2008541228.tif 000121
【国際調査報告】
2008541228.tif 000122