(57)【要約】  本発明の実施形態は、クエリの一部（a portion of a query）に関する関係結果を取得し、サーバのキャッシュに対する更新されたクエリセットを生成するためのシステムと方法を提供することを目的としている。サーバキャッシュと共通クエリセットとを含むデータ構造から、クエリの一部から始まる他のクエリを特定し取得することを可能にしている。いったん他のクエリが特定されると、他のクエリに関する結果がサーバキャッシュまたはバックエンドデータベースから取得される。共通クエリセットには、削除クエリ（deleted queries）と追加クエリを含むことが可能であり、共通クエリセットは更新されたクエリセットをサーバ用に生成するために利用することできる。割り当て関数（assignment function）に基づきサーバに属すことが可能である紛失クエリ（missing queries）と削除クエリは共に、キューに挿入され、そのあとでサーバのキャッシュに送られる。この転送は低アクティビティ期間またはアイドル状態期間に行なうことが可能である。
2009528624.tif 000002
【特許請求の範囲】
【請求項１】
クエリ結果を提供する方法であって、
クエリの一部を取得するステップと、
前記クエリの一部をサーバ（２３０）に割り当てるステップと、
前記クエリの一部から始まる他のクエリを取得するステップと、
前記他のクエリの一部または全部の結果を前記クエリの一部に基づいて取得するステップと、
を備えることを特徴とする方法。
【請求項２】
前記クエリの一部の表現を計算するステップをさらに備え、
前記クエリの一部をサーバ（２３０）に割り当てるステップは、前記表現に基づいて前記クエリの一部をサーバ（２３０）に割り当てることを含む、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記クエリの一部が予め定めたエントリに一致しているかどうかを判定するステップと、
後続文字を前記クエリの一部として割り当てるステップと、
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項４】
キャッシュクエリ（３２０）と共通クエリセット（３３０）とをデータ構造（３１０）に格納する格納するステップをさらに備え、
前記クエリの一部から始まる他のクエリを取得するステップは、前記クエリの一部から始まる他のクエリをデータ構造（３１０）から取得することを含む、
ことを特徴とする請求項１に記載の方法。
【請求項５】
キャッシュクエリに対して行なわれた変更と共通クエリセット（３３０）に対して行なわれた変更とを反映するようにデータ構造（３１０）を修正するステップを、
さらに備えることを特徴とする請求項４に記載の方法。
【請求項６】
キャッシュクエリ（３２０）と共通クエリセット（３３０）とを使用頻度に応じて格納するステップと、
前記クエリの一部から始まる他のクエリの各々の結果を使用頻度の降順に表示するステップと、
をさらに備えることを特徴とする請求項４に記載の方法。
【請求項７】
前記クエリの一部から始まる他のクエリの各々の結果を取得するステップは、前記他のクエリの各々の結果をサーバ（２３０）のキャッシュ（４１０）から取得することを含むことを特徴とする請求項１に記載の方法。
【請求項８】
前記クエリの一部から始まる他のクエリの各々の結果を取得するステップは、前記他のクエリの各々の結果をバックエンドサーバ（２４０）から取得することを含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記クエリの一部から始まる他のクエリが取得できない場合に、空の結果を提供するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１０】
クエリシステム（３００）であって、
クエリの一部を受け取るディストリビュータサーバ（２２０）と、
キャッシュクエリ（３２０）と共通クエリセット（３３０）とを格納するデータ構造（３１０）と、
前記キャッシュクエリ（３２０）と前記共通クエリセット（３３０）とに対する結果を提供する結果構造（３４０）と、
前記クエリの一部に基づいて関連結果を提供するために前記データ構造（３１０）と前記結果構造（３４０）を調べるフロントエンドサーバ（２３０）と、
を備えることを特徴とするクエリシステム。
【請求項１１】
バックエンドデータベース（２４０）をさらに備えることを特徴とする請求項１０に記載のクエリシステム。
【請求項１２】
ディストリビュータサーバ（２２０）は前記クエリの一部をフロントエンドサーバ（２３０）に割り当てることを特徴とする請求項１０に記載のクエリシステム。
【請求項１３】
前記クエリの一部は前記クエリのプレフィックスであることを特徴とする請求項１０に記載のクエリシステム。
【請求項１４】
共通クエリセット（３３０）を構築する方法であって、
フロントエンドサーバ（２３０）のキャッシュ（４１０）から削除されたエントリをコンパイルするステップと、
前記削除されたエントリで構成された共通クエリセット（３３０）を形成するステップであって、前記削除されたエントリは予め定めた時間範囲からのものある、ステップと、
共通クエリセット（３３０）を別のフロントエンドサーバ（２３０）に配信するステップと、
を備えることを特徴とする方法。
【請求項１５】
前記共通クエリセット（３３０）を別のフロントエンドサーバ（２３０）に配信するステップは、前記共通クエリセット（３３０）を複数のフロントエンドサーバ（２３０）に配信することを含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
予め定めたリストに基づいて追加クエリを生成するステップと、
前記追加クエリを前記共通クエリセット（３３０）に追加するステップと、
をさらに備えることを特徴とする請求項１４に記載の方法。
【請求項１７】
フロントエンドサーバ（２３０）のための更新されたクエリセットを計算するステップであって、前記更新されたクエリセットは前記フロントエンドサーバ（２３０）に割り当てられた前記共通クエリセット（３３０）内の割り当てられたクエリで構成されている、ステップと、
フロントエンドサーバ（２３０）のためのデータ構造（３１０）を構築するステップであって、前記データ構造のコンテンツは前記更新されたクエリセットとキャッシュクエリ（３２０）とで構成される、ステップと
をさらに備えることを特徴とする請求項１４に記載の方法。
【請求項１８】
紛失クエリを計算するステップであって、前記紛失クエリは前記フロントエンドサーバ（２３０）のキャッシュ（４１０）に属している、ステップと、
前記紛失クエリをキューに挿入するステップと
をさらに備えることを特徴とする請求項１７に記載の方法。
【請求項１９】
前記紛失クエリを前記キューから除去するステップと、
前記紛失クエリを前記キューからバックエンドデータベース（２４０）に送信するステップと、
前記紛失クエリを前記フロントエンドサーバ（２３０）の前記キャッシュ（４１０）に挿入するステップと、
をさらに備えることを特徴とする請求項１８に記載の方法。
【請求項２０】
前記サーバ（２３０）の前記キャッシュ（４１０）から期限満了した期限満了クエリが更新されたクエリセットに属しているかどうかを判定するステップと、
前記期限満了クエリをキューに挿入するステップと、
前記期限満了クエリを前記キューから除去するステップと、
前記期限満了クエリをキューからバックエンドデータベース（２４０）に送信するステップと、
前記期限満了クエリを前記フロントエンドサーバ（２３０）の前記キャッシュ（４１０）に挿入するステップと、
をさらに含むことを特徴とする請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クエリの一部に基づくキャッシュクエリ結果の提供に関する。
【背景技術】
【０００２】
ウェブサーチエンジンは、ユーザのサーチ、すなわち、クエリをディストリビュータサーバに誘導し、ディストリビュータサーバはそのクエリをフロントエンドサーバに順に転送している。フロントエンドサーバはクエリおよびそのクエリに対応する結果を含んでいることもあれば、クエリの結果に関してバックエンドデータベースを調べることもある。ウェブサーチエンジンは、同じサーチターム（search term）を入力するユーザから反復的クエリを受け取ることがよくある。最新クエリとその結果は、予め定めた時間量の間、フロントエンドサーバのフロントエンドキャッシュに保持することが可能である。というのも、全部のウェブインデックス（full web index）を含み、通常、フロントエンドキャッシュよりも大きいバックエンドデータベースを調べるよりも、望みの結果を得るためにフロントエンドキャッシュを調べた方が効率的で、消費する時間が少ないからである。詳細ウェブインデックスは、ウェブページのように、利用可能なウェブ結果すべてを含むことが可能である。それゆえ、インデックスが、フロントエンドキャッシュに格納されている結果よりもはるかに大きいので、サーチに時間を要する結果となる。しかし、望みの結果がフロントエンドキャッシュに見つからないときは、バックエンドデータベースを調べることが可能である。
【０００３】
最新クエリと結果を格納しておくことに加えて、フロントエンドキャッシュは有用なサーチのレコードとして役立つこともあり、そこにはユーザがより頻繁に調べていた結果や、調べられることをシステムアドミニストレータが確信している結果を含むことが可能になっている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
関連結果が提示されるためには、ユーザは全部のサーチターム（search term）またはクエリを入力する必要があるのが一般である。最初の数文字のように、クエリの一部（portion of a query）が入力されると、エラーメッセージまたは正しくない結果がユーザに提示されることがよくある。さらに、ユーザが結果を受け取るために入力するクエリに自信がない場合には、例えば、ユーザは複数のクエリを個別に入力し、その結果をかき分けるように調べて、望みのウェブページを見つける必要がある。望ましいことは、ユーザがクエリの一部を入力し、その入力したクエリの一部から始まるクエリのグループに関する関連結果を受け取るようにすることである。さらに、望ましいことは、ユーザがクエリの入力を続けて、クエリの一部が拡張されたとき、その結果がクエリの変化と共に自動的に調整されるようにすることである。
【０００５】
さらに、このような一部クエリメカニズム（portion-querying mechanism）がさらに望ましいとされるのは、リソースが保存されていて、フロントエンドキャッシュの利用によってオペレーションの完了が高速化されているときである。
【課題を解決するための手段】
【０００６】
クエリの一部に対する関係結果は、クエリの一部から始まる他のクエリを特定し、他のクエリの結果を取得することによって得られる。クエリの一部は、同じクエリの一部から始まる他のクエリを受け取るフロントエンドサーバに割り当てることができる。他のクエリは、サーバキャッシュと共通クエリセットを含むデータ構造に格納しておくことができる。他のクエリの結果は、サーバキャッシュに格納しておくことも、バックエンドデータベースに格納しておくことも可能である。
【０００７】
共通クエリセット（a set of common queries）は、サーバキャッシュから削除された削除クエリ（deleted query）をコンパイルすることによって形成することができる。この共通クエリセットには、事前に定められたリスト（predetermined list）からの追加クエリを含むことも可能である。
【０００８】
サーバキャッシュに対する更新されたクエリセットは共通クエリセットを使用して計算することができる。紛失クエリ（missing query）は、サーバキャッシュに属しているが、おそらくサーバキャッシュに格納されていないクエリである可能性がある。紛失クエリは共通クエリセットの一部であることもある。紛失クエリはキューに挿入され、そのあとで、アイドル期間または低アクティビティ期間にサーバキャッシュに置いておくことが可能である。同様に、サーバキャッシュから削除された期限満了クエリ（expired query）も、キューに挿入され、そのあとで、サーバキャッシュに置いておくこともできる。
【０００９】
この簡単な説明は、以下の詳細説明の中で詳しく説明されている概念のいくつかを選んで簡単に紹介したものである。この簡単な説明は、請求項に記載の主題の重要な特徴または基本的特徴を特定するものではなく、また請求項に記載の主題の範囲を限定するために使用されるものでもない。
【００１０】
上述した簡単な説明と以下の詳細説明の理解を容易にするために、以下では添付図面を参照して説明することにする。例示の実施形態が図面に示されているが、当然に理解されるように、これらの実施形態は本明細書に説明されている具体的方法および手段に限定されるものではない。
【発明を実施するための最良の形態】
【００１１】
図１を参照して説明すると、本発明を実現するための例示システムはコンピュータ１１０の形体をした汎用コンピューティングデバイスを備えている。コンピュータ１１０のコンポーネントとしては、処理ユニット１２０、システムメモリ１３０、およびシステムメモリを含む種々のシステムコンポーネントを処理ユニット１２０に結合するシステムバス１２１があるが、これらに限定されない。システムバス１２１は、いくつかのタイプのバス構造のいずれにすることも可能であり、その中には、種々のバスアーキテクチャを使用したメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスが含まれている。例を挙げると、そのようなアーキテクチャには、ＩＳＡ（Industry Standard Architecture）バス、ＭＣＡ（Micro Channel Architecture）バス、ＥＩＳＡ（Enhanced ISA）バス、ＶＥＳＡ（Video Electronics Standards Association）ローカルバス、およびＰＣＩ（Peripheral Component Interconnect）バス（これはMezzanineバスとも呼ばれている）が含まれているが、これらに限定されない。
【００１２】
コンピュータ１１０は、種々のコンピュータ可読媒体（computer readable media）を装備しているのが代表的である。コンピュータ可読媒体は、コンピュータ１１０によってアクセス可能である、どのような媒体にすることも可能であり、その中には揮発性および不揮発性で取り外し可能および取り外し不能の両方の媒体が含まれている。例を挙げると、コンピュータ可読媒体には、コンピュータ記憶媒体と通信媒体が含まれていることがあるが、これらに限定されない。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータのような情報を格納するための任意の方法またはテクノロジで実現された揮発性と不揮発性の両方、および取り外し可能と取り外し不能の両方の媒体が含まれている。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリや他のメモリテクノロジ、ＣＤ−ＲＯＭ、ＤＶＤ（digital versatile disk）や他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージや他の磁気ストレージデバイス、または望みの情報を格納するために使用可能で、コンピュータ１１０によってアクセス可能である他の任意の媒体が含まれているが、これらに限定されない。通信媒体は、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータを、搬送波などの変調データ信号または他のトランスポートメカニズムで具現化しているのが一般である。ここで「変調データ信号（modulated data signal）」という用語は、信号の中で情報を符号化するような形でその特性の１つまたは２つ以上がセットまたは変更されている信号を意味している。例を挙げると、通信媒体には、ワイヤド（有線）ネットワークや直接ワイヤドコネクションのようなワイヤド媒体、ならびに音響、ＲＦ、赤外線および他のワイヤレス（無線）媒体のようなワイヤレス媒体が含まれているが、これらに限定されない。上に挙げたものを任意に組み合わせたものも、コンピュータ可読媒体の範囲に含まれることは当然である。
【００１３】
システムメモリ１３０には、ＲＯＭ１３１およびＲＡＭ１３２のような揮発性／不揮発性メモリの形体をしたコンピュータ記憶媒体が含まれている。スタートアップ期間のように、コンピュータ１１０内のエレメント間で情報を転送するのを支援する基本ルーチンを含む基本入出力システム（basic input/output system  BIOS）１３３はＲＯＭ１３１に格納されているのが一般である。ＲＡＭ１３２は、処理ユニット１２０によって即時にアクセス可能であり、および／または現在操作の対象になっているデータおよび／またはプログラムモジュールを収めているのが一般である。例を挙げると、図１にはオペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６およびプログラムデータ１３７が示されているが、これらに限定されない。
【００１４】
コンピュータ１１０は、他の取り外し可能／取り外し不能で揮発性／不揮発性のコンピュータ記憶媒体を備えることも可能である。例を挙げると、図１には取り外し不能で不揮発性の磁気媒体との間で読み書きを行なうハードディスクドライブ１４１、取り外し可能で不揮発性の磁気ディスク１５２との間で読み書きを行なう磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭや他の光媒体のような取り外し可能で不揮発性の光ディスク１５６との間で読み書きを行なう光ディスクドライブ１５５が示されているが、これらに限定されない。例示コンピューティング環境で使用できる、その他の取り外し可能／取り外し不能で揮発性／不揮発性のコンピュータ記憶媒体としては、磁気テープカセット、フラッシュメモリカード、デジタルバーサタイルディスク（ＤＶＤ）、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭがある。ハードディスクドライブ１４１は、インタフェース１４０のような取り外し不能メモリインタフェースを通してシステムバス１２１に接続されているのが代表的であり、磁気ディスクドライブ１５１と光ディスクドライブ１５５は、インタフェース１５０のような取り外し可能メモリインタフェースによってシステムバス１２１に接続されているのが代表的である。
【００１５】
上述し、図１に図示のドライブとその関連コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、コンポーネント、プログラムモジュールおよび他のデータをコンピュータ１１０のために格納している。図１には、例えば、ハードディスクドライブ１４１はオペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６およびプログラムデータ１４７を格納しているものとして示されている。なお、これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６およびプログラムデータ１３７と同じであることも、異なっていることもある。ここで、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６およびプログラムデータ１４７に異なる番号が付けられているのは、最低限でも、これらが異なるコピーであることを示すためである。ユーザは、キーボード１６２および一般にマウス、トラックボールまたはタッチパッドと呼ばれているポインティングデバイスなどのインプットデバイスを通してコマンドおよび情報をコンピュータ１１０に入力することができる。その他のインプットデバイス（図示せず）としては、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナなどがある。これらおよび他のインプットデバイスは、システムバスに結合されたユーザ入力インタフェース１６０を通して処理ユニット１２０に接続されていることがよくあるが、パラレルポート、ゲームポートまたはＵＳＢ（universal serial bus）のような、他のインタフェースおよびバス構造によって接続されていることもある。モニタ１９１または他のタイプのディスプレイデバイスも、ビデオインタフェース１９０のようなインタフェースを介してシステムバス１２１に接続されている。モニタのほかに、コンピュータは、スピーカ１９７およびプリンタ１９６のように、出力周辺インタフェース１９５を通して接続可能である他の周辺アウトプットデバイスを備えることも可能である。
【００１６】
コンピュータ１１０は、リモートコンピュータ１８０のような１または２以上のリモートコンピュータとの論理コネクションを使用したネットワーキング環境で動作することが可能である。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイスまたは他の共通ネットワークノードにすることが可能であり、図１にはメモリストレージデバイス１８１だけが示されているが、コンピュータ１１０に関連して上述したエレメントの多くまたはすべてを備えているのが一般である。図示の論理コネクションとしては、ローカルエリアネットワーク（ＬＡＮ）１７１とワイドエリアネットワーク（ＷＡＮ）１７３があるが、他のネットワークが含まれていることもある。このようなネットワーキング環境は、オフィス、企業内コンピュータネットワーク、イントラネットおよびインターネットでは普通になっている。
【００１７】
ＬＡＮネットワーキング環境で使用されるときは、コンピュータ１１０はネットワークインタフェースまたはアダプタ１７０を通してＬＡＮ１７１に接続されている。ＷＡＮネットワーキング環境で使用されるときは、コンピュータ１１０は、インターネットのようなＷＡＮ１７３上の通信を確立するモデムまたは他の手段を装備しているのが代表的である。モデム１７２は内蔵型と外付け型があり、ユーザ入力インタフェース１６０または他の該当メカニズムを介してシステムバス１２１に接続することが可能になっている。ネットワーキング環境では、コンピュータ１１０に関連して図示のプログラムモジュールまたはその一部は、リモートメモリストレージデバイスに格納されていることがある。例を挙げると、図１にはリモートアプリケーションプログラム１８５がメモリデバイス１８１上に置かれているものとして示されているが、このことに限定されない。当然に理解されるように、図示のネットワークコネクションは例示であり、コンピュータ間の通信リンクを確立する他の手段を使用することも可能である。
【００１８】
上述した本発明の方法のすべてまたはその一部は、ハードウェア、ソフトウェアまたはその両方を組み合わせたもので具現化することが可能である。ソフトウェアで具現化されているときは、本発明の方法またはその一部の側面または一部は、コンピューティングシステムによって実行されたとき、コンピューティングシステムに本発明の方法を実行させるプログラムコードの形で具現化することができる。このプログラムコードは、どのコンピュータ可読媒体上にも格納しておくことができ、この用語の意味は上記に定義されている通りである。
【００１９】
図２は、例えば、コンピュータ１１０を通してインターネットサーチエンジンに入力されたクエリ（query）またはクエリの一部のようなクエリに対する結果を提供するために利用することが可能であるサーバ構成（server organization）２００を示している。クエリはインターネット２１０から出され、そこでは、ユーザは、クエリに送られるウェブページ（Web page）のような、関係結果を得たいと望んでいるクエリを挿入することができる。このクエリはサーチエンジンにて入力することができるので、サーチエンジンを使用すると、ユーザは関心のあるクエリを挿入することができ、また、サーチエンジンは関係結果を表示して、ユーザがアクセスできるようにする。インターネット２１０はディストリビュータサーバ（distributor sever）２２０に接続することが可能であり、ディストリビュータサーバ２２０はインターネット２１０からクエリを受信する。複数のディストリビュータサーバ２２０をインターネット２１０に接続することも可能である。図２には、３つのディストリビュータサーバ２２０（２２０ａ、２２０ｂおよび２２０ｃ）が示されているが、ディストリビュータサーバ２２０の数は３つに限定されない。クエリは、例えば、クエリの送信元インターネットプロトコルアドレス（ＩＰ）によってディストリビュータサーバ２２０のうちの特定のディストリビュータサーバに割り当てることが可能である。クエリをディストリビュータサーバ２２０の１つに割り当てるために他の方法が利用されることもある。あるいは、クエリはディストリビュータサーバ２２０のうちの任意のディストリビュータサーバにランダムに送信されることもある。
【００２０】
クエリを受け取るディストリビュータサーバ２２０は、図２のサーバ構成２００に示されているフロントエンドサーバ２３０ａ、２３０ｂ、２３０ｃおよび２３０ｎの１つのように、そのクエリをフロントエンドサーバ２３０に送信することができる。サーバ構成２００はフロントエンドサーバ２３０の一定数に限定されない。ディストリビュータサーバ２２０からクエリを受け取るフロントエンドサーバ２３０は、クエリをフロントエンドサーバ２３０にリンクしているマッピング（mapping）に基づいてクエリを受け取ることができる。例えば、クエリはある値を得るためにハッシング（hashing）されることがあり、その値は、あるクエリを特定のフロントエンドサーバ２３０に置いておくマッピング関数（mapping function）の中で使用され、同じクエリは常に、またはほぼ常に、同じフロントエンドサーバ２３０に送られることを保証することができる。マッピング関数は、フロントエンドサーバ２３０のうちのどのフロントエンドサーバがクエリを受け取るかを判断することができる。フロントエンドサーバ２３０はマッピング関数に基づいて割り当てられる必要がなく、例えば、ランダムにクエリを受け取るようにすることができるが、そのことに限定されない。
【００２１】
キャッシュ、つまり、ローカルストレージはクエリとその対応する結果を収めておくことができる。キャッシュはフロントエンドサーバ２３０の一部であることがあり、キャッシュのクエリと結果とは、予め定められた期間、例えば、３時間からのものであるように、最新クエリと結果のセットであることがある。フロントエンドサーバ２３０がディストリビュータサーバ２２０からクエリを受け取ったとき、フロントエンドサーバ２３０はそのキャッシュをサーチして、クエリとその対応する結果がすでにキャッシュに格納されているかどうかを判断することができる。そのクエリがキャッシュにあれば、フロントエンドサーバ２３０は結果をキャッシュから返すことができる。結果は、クエリを入力したユーザに返されることもある。
【００２２】
フロントエンドサーバ２３０は、既存結果、例えば、ウェブページを収めておくことのできるバックエンドデータベース２４０と通信していることがある。クエリ結果はバックエンドデータベース２４０に格納されていることがある。入力したクエリがフロントエンドサーバ２３０のキャッシュにないときは、関係クエリ結果をユーザに返すためにバックエンドデータベース２４０を調べることができる。バックエンドデータベース２４０はフロントエンドサーバ２３０のキャッシュよりもはるかに大きいのが一般的であるため、バックエンドデータベースを調べると、フロントエンドサーバ２３０のキャッシュを調べるよりもはるかに時間がかかることになる。そのために、バックエンドデータベース２４０を調べることが行なわれるのは、例えば、要求した結果がフロントエンドサーバ２３０にないとき、またはサーバ障害のような問題がフロントエンドサーバ２３０に起ったときだけである。
【００２３】
図３は、クエリの一部に対する結果を得るために利用することができるクエリシステム３００を示すブロック図である。クエリシステム３００は、クエリの一部を受け取るためのディストリビュータサーバ２２０を備えることができる。クエリの一部は、例えば、クエリの最初の３文字にすることができる。クエリに対する結果を必要とするユーザは、そのクエリの一部をインターネットサーチエンジンにタイプまたは入力することができる。クエリの一部は、そこからそのクエリの一部が出されるコンピュータ１１０のＩＰアドレスに基づいてディストリビュータサーバ２２０に送ることが可能である。クエリの一部はディストリビュータサーバ２２０にランダムに送ることも可能である。
【００２４】
ディストリビュータサーバ２２０は、クエリの一部をフロントエンドサーバ２３０に割り当てることを受け持つことができる。ハッシュ関数は、その割り当てタスクのためにディストリビュータサーバ２２０によって使用することができる。ディストリビュータサーバ２２０は、例えば、同じ一部を持つ他のクエリが同じフロントエンドサーバ２３０に割り当てられるようにクエリの一部をフロントエンドサーバ２３０に割り当てることができる。クエリの一部がフロントエンドサーバ２３０に割り当てられたあと、ディストリビュータサーバ２２０はその割り当てられたフロントエンドサーバ２３０にクエリの一部を送信することができる。
【００２５】
フロントエンドサーバ２３０がクエリの一部を受け取ると、フロントエンドサーバ２３０は、そのクエリの一部と同じ一部を持つ他のクエリを得るためにサーチを行なうことを受け持つことができる。これらのクエリを得るために、フロントエンドサーバ２３０はデータ構造３１０を調べることができる。このデータ構造３１０は、図３には別のコンポーネントとして示されているが、フロントエンドサーバ２３０の一部にすることも可能である。データ構造３１０には、キャッシュクエリ３２０のようなサーバキャッシュが含まれていることもある。キャッシュクエリ３２０には、予め定めた時間期間の間データ構造３１０に保持されていた以前のクエリが含まれていることがある。従って、キャッシュクエリ３２０には、例えば、最新のクエリが含まれていることがある。キャッシュクエリ３２０は、最新クエリへのアクセスの容易化および高速化のためにデータ構造３１０に保持されることができる。また、データ構造３１０には、共通クエリセット（set of common queries）３３０が含まれていることもある。この共通クエリセットの形成については、以下に詳しく説明されている。
【００２６】
データ構造は拡張ツリー構造（augmented tree structure）にすることが可能であり、これはクエリまたはクエリの一部に関係する情報の検索を高速化する構造になっている。例えば、起り得るクエリの一部は、そのクエリの各一部に関係する追加情報と一緒にツリー構造に格納しておくことができる。クエリの各一部に関係する情報は、例えば、そのクエリの一部から始まる、予め定めた数の最も頻繁に要求されたクエリのリストにすることができる。このリストは、クエリの一部から始まる最も要求された共通クエリが最初にリストされるように頻度の降順にソートすることができる。
【００２７】
クエリの一部を含むことが可能である他のクエリのリストがデータ構造３１０から得られたとき、キャッシュ構造にすることが可能な結果構造３４０が調べられる。この結果構造はフロントエンドサーバ２３０の一部であることもある。結果構造３４０はクエリの結果を収めている。結果構造３４０を調べると、クエリの一部から始まるクエリの結果が得られ、ユーザに提供される。これらの結果は、例えば、何度も選択されたウェブページであることもある。
【００２８】
バックエンドデータベース２４０は、クエリシステム３００の一部にすることも可能である。このバックエンドデータベース２４０が調べられるのは、クエリの一部を含んでいる１または２以上のクエリの結果が結果構造３４０に置かれていないときである。バックエンドデータベース２４０から得られた結果も、図３に示すようにユーザに提供される。
【００２９】
図４は、共通クエリ構築システム（common query constructing system）４００を示すブロック図である。このシステム４００には、共通クエリ３３０を作成するタスクを割り当てることが可能であり、その共通クエリは、クエリの一部と同じ一部を持つクエリを得るために利用されることがある。共通クエリ構築システム４００は、クエリの一部をディストリビュータサーバ２２０から受け取るフロントエンドサーバ２３０を備えることが可能である。サーバキャッシュ４１０はフロントエンドサーバ２３０の一部にすることが可能である。サーバキャッシュ４１０はフロントエンドサーバ２３０のキャッシュ構造にすることが可能であり、そこには、予め定めた時間期間の間保持されていたクエリのような、以前のクエリが格納されている。フロントエンドサーバ２３０のサーバキャッシュ４１０は、フロントエンドサーバ２３０の一部にできるデータ構造３１０のキャッシュクエリ３２０と同じコンポーネントにすることが可能である。
【００３０】
クエリは、フロントエンドサーバ２３０のサーバキャッシュ４１０から削除されることがよくある。この削除が行なわれるのは、サーバキャッシュ４１０のサイズが限られているためである。クエリを削除する必要が起るのは、より新しいクエリ（またはクエリの一部）のための記憶スペースを作るためである。また、削除は定期的に行なわれることもある。クエリがサーバキャッシュ４１０から削除されたとき、ログエントリ４２０は削除クエリを受け取り、追跡することができる。予め定めた時間期間が経過したあと、ログエントリ４２０からは削除クエリがログエントリコンパイラ（log entry compiler）４３０に渡され、ログエントリコンパイラ４３０は削除されたエントリをコンパイルする。ログエントリコンパイラ４３０は、例えば、一週間の期間に２回以上現れたエントリのように、以前に判断された基準に基づいて、削除されたエントリをコンパイルすることができる。ログエントリコンパイラ４３０は、削除クエリのコンパイルを完了すると、そのコンパイルしたものをデータ構造３１０の共通クエリ３３０に渡すことができる。そのあと、データ構造３１０には共通クエリが格納され、その共通クエリは、サーチしたクエリの一部と同じ一部を持つクエリを結果構造３４０に与える際に使用される。
【００３１】
共通クエリ３３０は、キャッシュクエリを補足するものとして使用されることがある。キャッシュクエリ３２０は、もっと最新のクエリであることがあるのに対し、共通クエリ３３０は必ずしも最新のクエリである必要がないので、例えば、一週間のように、予め定めた比較的長い時間期間からの頻繁に要求されたクエリであることがある。
【００３２】
図５ａおよび図５ｂは、クエリ結果を提供する方法を示している。５０５において、クエリの一部が取得される。このクエリの一部は、クエリに関係する結果を望んでいるユーザが、例えば、そのクエリの一部をインターネットサーチエンジンに入力することで開始されることがある。クエリの一部はディストリビュータサーバ２２０で得られることもある。５１０において、クエリの一部は、そのクエリの一部が予め定めたエントリに一致しているかどうかを判断するために調べられる。クエリの一部が予め定めたれられエントリに一致していれば、５１５において、後続文字がクエリの一部として割り当てられる。頻繁に出現するエントリであって、ユーザがクエリの一部にするつもりのないエントリがいくつか存在することもあるので、この比較を行なうと、望まれていないクエリのクエリ結果を与えないで済むことがある。例えば、あるユーザが“ｈｔｔｐ”および“ｗｗｗ”から始まるクエリを入力する場合、そのユーザはこれらのクエリをサーチするのを望まず、その代わりに、これらの頻繁に出現するエントリの後に続く文字に関心を持つことがあるのが一般である。従って、“ｗｗｗ”の後に続く３文字のような、後続文字をクエリの一部として割り当てると、クエリの正しい一部がサーチされることになる。クエリの一部は予め定めた他のクエリと比較することができる。
【００３３】
後続文字がクエリの一部として割り当てられたあと、そのクエリの一部が予め定めたエントリと一致していないときは、クエリ結果を提供する方法は、それぞれ５１５および５１０から５２０に進むことになる。５２０において、クエリの一部の表現を計算することができる。この表現は、例えば、クエリの一部のハッシュ関数にすることができる。他の表現も可能である。
【００３４】
５２０に続く５２５において、クエリの一部はフロントエンドサーバ２３０に割り当てることができる。クエリの一部の表現が５２０において計算されたとき、その表現はクエリの一部をフロントエンドサーバ２３０に割り当てるために使用することができる。クエリの一部をフロントエンドサーバに割り当てるために他の割り当て基準が使用されることもある。あるいは、その割り当てはランダムな選択であることもある。５３０において、クエリの一部は割り当てられたフロントエンドサーバ２３０に送信されることになる。
【００３５】
図３および図４を参照して上述したデータ構造３１０のような、データ構造がクエリの一部から始まるクエリを収めているかどうかが５３５において判定される。予め定めた時間期間の間データ構造３１０に保持されていた以前のクエリを含むことが可能であるキャッシュクエリ３２０および共通クエリ３３０を含むことが可能であるデータ構造３１０が、クエリの一部から始まるクエリを収めていない場合には、５４０において、空の結果リストがユーザに提供される。他方、データ構造３１０がクエリの一部から始まるクエリを収めているときは、この方法は５４５（図５ｂ）に進む。５４５において、クエリの一部から始まるクエリはデータ構造３１０から取得されることになる。
【００３６】
５５０において、クエリの一部から始まる取得された各々のクエリについて、結果構造３４０のように、フロントエンドサーバ２３０の一部にすることが可能なサーバキャッシュに結果が格納されているかどうかを確かめる判定が行なわれる。５６０において、クエリの一部から始まる取得されたクエリに対する結果が結果構造３４０にないときは、その結果はバックエンドデータベース２４０から取得される。他方、５５５において、クエリの一部から始まる取得されたクエリに対する結果が結果構造３４０にあるときは、その結果は結果構造３４０から取得される。５５０における判断は、クエリの一部を含んでいる、各々の取得されたクエリについて行なわれる。このようにすると、結果がバックエンドデータベース２４０からのものであるか、結果構造３４０からのものであるかに関係なく、クエリの一部を含む各々のクエリに対して結果が提供されることが保証される。このクエリ提供方法は５６５で終了し、そこで結果が提供される。
【００３７】
図６は、共通クエリセット（set of common queries）を構築する方法を示すフロー図である。６１０において、クエリは予め定めたリストに基づいて生成される。この予め定めたリストには、共通クエリセット３３０の一部のはずであると、システムアドミニストレータが確信しているクエリを含むことが可能である。例えば、予め定めたリストは、ユーザによるクエリサーチの中で使用されなかったが、近い将来に人気が出て、幅広くサーチされることが予想される新作ムービであることがある。このようなクエリをデータ構造３１０の一部である共通クエリ３３０に追加しておくと、クエリまたはクエリの一部をサーチするとき、バックエンドデータベース２４０を調べないで済むことになる。
【００３８】
６１５において、フロントエンドサーバ２３０のサーバキャッシュ４１０のようなサーバのキャッシュまたはキャッシュクエリ３２０から削除クエリがコンパイルされる。削除クエリは、予め定めた時間期間にわたってコンパイルすることができる。削除クエリは、図４の共通クエリ構築システム４００に関連して上述したように、ログエントリ４２０によって追跡され、ログエントリコンパイラ４３０によってコンパイルすることができる。
【００３９】
６２０において、共通クエリセット３３０が形成される。共通クエリには、６１０において生成された予め定めたクエリを組み合わせたものまたはコンパイルしたもの、および６１５において生成された削除クエリを含むことが可能である。共通クエリ３３０が形成されたあと、６２５において、共通クエリ３３０はフロントエンドサーバ２３０に配信される。削除クエリが、図２のフロントエンドサーバ２３０ｂのような特定のフロントエンドサーバから削除されたものであれば、その共通クエリはシステム２００の他のフロントエンドサーバ２３０ａ、２３０ｃおよび２３０ｎに配信されることになる。
【００４０】
図７は、フロントエンドサーバ２３０の一部にすることができる、フロントエンドサーバのデータ構造３１０のキャッシュクエリ３２０を更新する方法を示すフロー図である。このキャッシュクエリ３２０には、最新のクエリを含むことが可能である。７１０において、更新されたクエリセットが計算される。この更新されたクエリセットには、共通クエリ３３０からのクエリを含むことが可能であり、そのクエリは、例えば、同じクエリおよび同じクエリの一部を同じフロントエンドサーバ２３０に送るように動作するハッシングおよびマッピングオペレーションに基づいて、フロントエンドサーバ２３０に割り当てられたものである。更新されたクエリセットはフロントエンドサーバ２３０によって計算することができる。７２０において、更新されたクエリセットは、キャッシュクエリ３２０と一緒にデータ構造３１０に格納しておくことができる。これはキャッシュクエリ３２０を更新しやすくするためである。
【００４１】
７３０において、更新されたクエリセットにあるが、キャッシュクエリ３２０にないクエリ（紛失クエリ）が判定される。どのクエリもこの基準に一致していないときは、この方法は、基準に一致するクエリを探し出すためのサーチを行なう。この方法が続行され、紛失クエリがキャッシュクエリ３２０に追加される。７４０において、紛失クエリはキューに追加される。
【００４２】
この方法は７５０に進むことがあり、そこでシステムは、システムが軽負荷状態にあるかどうか判定するために分析される。フロントエンドサーバ２３０が要求をバックエンドシステム２４０に送信するたびに、バックエンドシステム２４０からの応答には、バックエンド２４０のカレントステータス（これにはバックエンドの現負荷状態が含まれていることがある）を判断するために使用できるフィードバックが含まれていることがある。例えば、このフィードバックには、キューに置かれていてバックエンド２４０による処理待ちにある平均要求数またはバックエンド２４０がクエリ処理時間制限期間に取得できる返答の品質が含まれていることがある。そのあと、フロントエンドサーバ２３０は、カレントバックエンド２４０が軽負荷状態にあるとみなすべきか、重負荷状態にあるとみなすべきかを、そのフィードバックに基づいて判断するアルゴリズムが使用されることになる。システムが軽負荷状態にあれば、この方法は７６０に進むことになる。
【００４３】
７４０または７５０に続いて、７６０において、紛失クエリはキューから除去される。７７０において、紛失クエリはバックエンドデータベース２４０に送られることがある。７８０において、バックエンドデータベース２４０はキャッシュクエリ３２０を紛失クエリで更新する。紛失クエリは、もはやキャッシュクエリ３２０からの「紛失」クエリではなくなる。
【００４４】
以上から理解されるように、本明細書に開示されている実施形態は、その全体または一部を１または２以上のコンピューティングシステムまたはデバイスで実現することが可能である。図１は、実施形態を具現化または実施することが可能であるコンピューティングシステム１００の一例の機能コンポーネントを示している。本明細書で用いられている「コンピューティングシステム」、「コンピュータシステム」および「コンピュータ」の用語は、プログラムコードおよび／またはデータを実行し、さもなければ処理する能力を備えたプロセッサを含む、すべてのマシン、システムまたはデバイスのことを指している。コンピューティングシステムの例としては、パーソナルコンピュータ（ＰＣ）、ミニコンピュータ、メインフレームコンピュータ、シンクライアント（thin client）、ネットワークＰＣ、サーバ、ワークステーション、ラップトップコンピュータ、ハンドヘルドコンピュータ、プログラマブルコンシューマエレクトロニクス、マルチメディアコンソール、ゲームコンソール、サテライト受信器、セットトップボックス、自動化テラーマシン、アーケードゲーム、モバイル電話、パーソナルデジタルアシスタント（ＰＤＡ）およびその他のプロセッサベースのシステムまたはマシンがあるが、これらに限定されるものではない。「プログラムコード」および「コード」の用語は、プロセッサによって実行され、さもなければ処理されるすべての命令セットのことを指している。プログラムコードおよび／またはデータは、特定の関数を実行するルーチン、プログラム、オブジェクト、モジュール、データ構造などの形体で実現することが可能である。
【００４５】
以上から理解されるように、上述した例は説明目的のための単なる例示であり、どのような意味においても限定的ではない。種々の実施形態を参照して本発明を説明してきたが、当然に理解されるように、本明細書の中で用いられている用語は、限定を意味する用語ではなく、説明と例示を目的とした用語である。さらに、本明細書において特定の手段、マテリアル、および例と関連付けて実施形態を説明してきたが、これらの実施形態は本明細書に開示されている詳細に限定されるものではなく、むしろ、これらの実施形態は、請求項に記載の本発明の範囲に属する、機能的に同等の構造、方法および使用のすべてに及ぶものである。
【図面の簡単な説明】
【００４６】
【図１】例示コンピューティングデバイスを示すブロック図である。
【図２】例示サーバ構成を示すブロック図である。
【図３】クエリシステムを示すブロック図である。
【図４】クエリ構築システムを示すブロック図である。
【図５ａ】クエリ結果を提供する方法の一実施形態を示すフロー図である。
【図５ｂ】クエリ結果を提供する方法の一実施形態を示すフロー図である。
【図６】共通クエリセットを構築する方法の一実施形態を示すフロー図である。
【図７】キャッシュクエリセットを更新する方法の一実施形態を示すフロー図である。
【図１】
2009528624.tif 000003
【図２】
2009528624.tif 000004
【図３】
2009528624.tif 000005
【図４】
2009528624.tif 000006
【図５ａ】
2009528624.tif 000007
【図５ｂ】
2009528624.tif 000008
【図６】
2009528624.tif 000009
【図７】
2009528624.tif 000010
【国際調査報告】
2009528624.tif 000011
2009528624.tif 000012
2009528624.tif 000013