(57)【要約】  クエリ提案を予めキャッシュするための方法、システム、装置、およびコンピュータプログラム製品。一態様において、方法は、検索リソースの要求をクライアントデバイスから受信するステップと、この要求に応答してクライアントデバイスに検索リソースを提供するステップであって、検索リソースは、第1のクエリ入力フィールドを含む検索インターフェースをクライアントデバイスに生成させる第1の命令、初期クエリ提案、第2の命令であって、クライアントデバイスに、初期クエリ提案をクライアントデバイスの提案ストアに記憶すること、第1のクエリ入力フィールドに入力されたクエリの文字を提案ストアに記憶されたクエリ提案と比較すること、第1のクエリ入力フィールドに入力されたクエリの文字に合うクエリ提案を比較に基づいて選択すること、および選択されたクエリ提案を第1のクエリ入力フィールドに入力されたクエリの文字に対するクエリ提案として表示することを行わせる、第2の命令を含む、提供するステップとを含む。
2013535729.tif 000002
【特許請求の範囲】
【請求項１】
データ処理装置と、
前記データ処理装置とデータ通信するメモリストレージ装置であって、前記データ処理装置によって実行されるときに、前記データ処理装置に、
検索リソースの要求をクライアントデバイスから受信する動作と、
前記要求に応答して前記クライアントデバイスに前記検索リソースを提供する動作であって、前記検索リソースは、
第1のクエリ入力フィールドを含む検索インターフェースを前記クライアントデバイスに生成させる第1の命令、
初期クエリ提案、ならびに
第2の命令であって、前記クライアントデバイスに
前記初期クエリ提案を前記クライアントデバイスの提案ストアに記憶すること、
前記第1のクエリ入力フィールドに入力されたクエリの文字を前記提案ストアに記憶されたクエリ提案と比較すること、
前記第1のクエリ入力フィールドに入力された前記クエリの文字に合うクエリ提案を比較に基づいて選択すること、および
選択されたクエリ提案を前記第1のクエリ入力フィールドに入力された前記クエリの文字に対するクエリ提案として表示すること
を行わせる、第2の命令
を含む、提供する動作と
を含む動作を行わせるサーバ命令を記憶する、メモリストレージ装置と
を備えるシステム。
【請求項２】
前記第2の命令は、前記クライアントデバイスに、
前記第1のクエリ入力フィールドに入力された前記クエリの文字をクエリ提案の要求として前記データ処理装置に与えさせ、
前記要求に応答して、追加的なクエリ提案を前記データ処理装置から受信させ、
前記追加的なクエリ提案を前記提案ストアに記憶させ、
前記サーバ命令は、前記データ処理装置に、前記クエリ提案の要求に応答して前記クライアントデバイスに前記追加的なクエリ提案を提供させる
請求項1に記載のシステム。
【請求項３】
前記第2の命令は、前記クライアントデバイスに、前記クエリ入力フィールドにクエリの文字を入力するごとに別個のクエリ提案の要求を与えさせる請求項2に記載のシステム。
【請求項４】
前記サーバ命令は、さらに、前記データ処理装置に、前記クライアントデバイスから受信されたクエリに応答して検索結果リソースを提供させ、前記検索結果リソースは、
前記クエリに対応すると判定されたリソースを参照する検索結果を表示する検索結果ページを前記クライアントデバイスに生成させる第3の命令と、
追加的なクエリ提案と、
前記クライアントデバイスに、前記追加的なクエリ提案を前記クライアントデバイスの前記提案ストアに記憶させる第4の命令とを含む
請求項1に記載のシステム。
【請求項５】
前記検索結果ページは、第2のクエリ入力フィールドを含み、
前記第4の命令は、前記クライアントデバイスに、
前記第2のクエリ入力フィールドに入力されたクエリの文字を前記提案ストアに記憶されたクエリ提案と比較させ、
前記第2のクエリ入力フィールドに入力された前記クエリの文字に合うクエリ提案を比較に基づいて選択させ、
選択されたクエリ提案を前記第2のクエリ入力フィールドに入力された前記クエリの文字に対するクエリ提案として表示させる
請求項4に記載のシステム。
【請求項６】
前記サーバ命令は、前記データ処理装置に、
ユーザによって送られたクエリと、各クエリが送られた頻度とを含むクエリログデータにアクセスする動作と、
最初のクエリの文字の最も有望なシーケンスを前記クエリログデータから決定する動作と、
それぞれの最も有望なシーケンスに関して、最も有望なクエリを前記最も有望なシーケンスおよび前記クエリログデータから決定する動作であって、それぞれの最も有望なクエリは、最初のクエリの文字の前記最も有望なシーケンスに合うクエリの文字の最初のシーケンスを有する、決定する動作と、
最初のクエリの文字の前記最も有望なシーケンスのそれぞれに対して決定された前記最も有望なクエリを前記初期クエリ提案として指定する動作と
を含む動作を行わせるようにさらに動作可能である請求項1に記載のシステム。
【請求項７】
前記第2の命令は、前記クライアントデバイスに、
前記第1のクエリ入力フィールドに入力された前記クエリの文字をクエリ提案の要求として前記データ処理装置に与えさせ、
前記要求に応答して、追加的なクエリ提案を前記データ処理装置から受信させ、
前記追加的なクエリ提案を前記提案ストアに記憶させ、
前記サーバ命令は、前記データ処理装置に、
前記クライアントデバイスから前記クエリの文字を受信することと、
前記クライアントデバイスから受信された前記クエリの文字の後に順番に続くクエリの文字である後続のクエリの文字の最も有望なシーケンスを前記クエリログデータから決定することと、
後続のクエリの文字のそれぞれの最も有望なシーケンスに関して、最も有望な追加的なクエリを後続のクエリの文字の前記最も有望なシーケンスおよび前記クエリログデータから決定することであって、それぞれの最も有望なクエリは、前記クライアントデバイスから受信された前記クエリの文字および後続のクエリの文字の前記最も有望なシーケンスに合うクエリの文字の最初のシーケンスを有する、決定することと、
後続のクエリの文字の前記最も有望なシーケンスのそれぞれに対して決定された前記最も有望な追加的なクエリを前記追加的なクエリ提案として指定することと、
前記クエリ提案の要求に応答して前記クライアントデバイスに前記追加的なクエリ提案を提供することとを行わせる
請求項6に記載のシステム。
【請求項８】
前記サーバ命令は、前記データ処理装置に、
前記初期クエリ提案および前記追加的なクエリ提案をキー値の対の形式で提供することであって、前記キー値の対は、クエリの入力シーケンスと、前記クエリの入力シーケンスに合う最初のクエリの文字を有するクエリ提案との対である、提供することを行わせ、
前記第2の命令は、前記クライアントデバイスに、
前記第1のクエリ入力フィールドに入力された前記クエリの文字が前記キー値の対の前記クエリの入力シーケンスのいずれにも合わないと判定することにのみ応じて、前記第1のクエリ入力フィールドに入力された前記クエリの文字をクエリ提案の要求として前記データ処理装置に与えさせる
請求項7に記載のシステム。
【請求項９】
前記検索リソースの前記要求は、前記クライアントデバイスの現在の位置を特定する位置データを含み、
前記初期クエリ提案は、前記クライアントデバイスの前記現在の位置に固有である位置に固有のクエリ提案を含み、
前記第1のクエリ入力フィールドに入力された前記クエリの文字に合うクエリ提案を比較に基づいて選択することは、前記クライアントデバイスの前記現在の位置に固有ではない位置に固有のクエリ提案を除外することをさらに含む
請求項1に記載のシステム。
【請求項１０】
処理システムと、
前記処理システムとデータ通信するメモリストレージ装置であって、前記処理システムによって実行されるときに、クライアントデバイスに、
検索エンジンからの検索リソースの要求を与える動作と、
前記検索リソースの前記要求に応答して前記検索リソースを受信する動作であって、前記検索リソースは、
第1のクエリ入力フィールドを含む検索インターフェースをクライアントデバイスに生成させる第1の命令、
初期クエリ提案、ならびに
第2の命令であって、クライアントデバイスに、
前記初期クエリ提案をクライアントデバイスの提案ストアに記憶すること、
前記第1のクエリ入力フィールドに入力されたクエリの文字を前記提案ストアに記憶されたクエリ提案と比較すること、
前記第1のクエリ入力フィールドに入力された前記クエリの文字に合うクエリ提案を比較に基づいて選択すること、および
選択されたクエリ提案を前記第1のクエリ入力フィールドに入力された前記クエリの文字に対するクエリ提案として表示すること
を行わせる、第2の命令
を含む、受信する動作と
を含む動作を行わせるブラウザ命令を記憶する、メモリストレージ装置と
を備えるクライアントデバイス。
【請求項１１】
前記第2の命令は、前記クライアントデバイスに、
前記第1のクエリ入力フィールドに入力された前記クエリの文字をクエリ提案の要求としてデータ処理装置に与えさせ、
前記要求に応答して、追加的なクエリ提案を前記データ処理装置から受信させ、
前記追加的なクエリ提案を前記提案ストアに記憶させる
請求項10に記載のクライアントデバイス。
【請求項１２】
前記第2の命令は、前記クライアントデバイスに、前記クエリ入力フィールドにクエリの文字を入力するごとに別個のクエリ提案の要求を与えさせる請求項11に記載のクライアントデバイス。
【請求項１３】
前記クライアントデバイスは、前記クライアントデバイスから受信されたクエリに応答して検索結果リソースを受信し、前記検索結果リソースは、
前記クエリに対応すると判定されたリソースを参照する検索結果を表示する検索結果ページを前記クライアントデバイスに生成させる第3の命令と、
追加的なクエリ提案と、
前記クライアントデバイスに、前記追加的なクエリ提案を前記クライアントデバイスの前記提案ストアに記憶させる第4の命令とを含む
請求項11に記載のクライアントデバイス。
【請求項１４】
前記検索結果ページは、第2のクエリ入力フィールドを含み、
前記第4の命令は、前記クライアントデバイスに、
前記第2のクエリ入力フィールドに入力されたクエリの文字を前記提案ストアに記憶されたクエリ提案と比較させ、
前記第2のクエリ入力フィールドに入力された前記クエリの文字に合うクエリ提案を比較に基づいて選択させ、
選択されたクエリ提案を前記第2のクエリ入力フィールドに入力された前記クエリの文字に対するクエリ提案として表示させる
請求項13に記載のクライアントデバイス。
【請求項１５】
前記初期クエリ提案および前記追加的なクエリ提案は、キー値の対の形式で提供され、前記キー値の対は、クエリの入力シーケンスと、前記クエリの入力シーケンスに合う最初のクエリの文字を有するクエリ提案との対であり、
前記第2の命令および前記第4の命令は、前記クライアントデバイスに、前記第1のクエリ入力フィールドまたは前記第2のクエリ入力フィールドにそれぞれ入力された前記クエリの文字が前記キー値の対の前記クエリの入力シーケンスのいずれにも合わないと判定することにのみ応じて、前記第1のクエリ入力フィールドおよび前記第2のクエリ入力フィールドにそれぞれ入力された前記クエリの文字をクエリ提案の要求として前記データ処理装置に与えさせる
請求項14に記載のクライアントデバイス。
【請求項１６】
前記検索リソースの前記要求は、前記クライアントデバイスの現在の位置を特定する位置データを含み、
前記初期クエリ提案は、前記クライアントデバイスの前記現在の位置に固有である位置に固有のクエリ提案を含み、
前記第1のクエリ入力フィールドに入力された前記クエリの文字に合うクエリ提案を比較に基づいて選択することは、前記クライアントデバイスの前記現在の位置に固有ではない位置に固有のクエリ提案を除外することをさらに含む
請求項15に記載のクライアントデバイス。
【請求項１７】
データ処理装置によって実行されるコンピュータによって実施される方法であって、
検索リソースの要求をクライアントデバイスから受信するステップと、
前記検索リソースの前記要求に応答して前記クライアントデバイスに前記検索リソースを提供するステップであって、前記検索リソースは、
第1のクエリ入力フィールドを含む検索インターフェースを前記クライアントデバイスに生成させる第1の命令、
初期クエリ提案、ならびに
第2の命令であって、前記クライアントデバイスに、
前記初期クエリ提案を前記クライアントデバイスの提案ストアに記憶すること、
前記第1のクエリ入力フィールドに入力されたクエリの文字を前記提案ストアに記憶されたクエリ提案と比較すること、
前記第1のクエリ入力フィールドに入力された前記クエリの文字に合うクエリ提案を比較に基づいて選択すること、および
選択されたクエリ提案を前記第1のクエリ入力フィールドに入力された前記クエリの文字に対するクエリ提案として表示すること
を行わせる、第2の命令
を含む、提供するステップと
を含む、方法。
【請求項１８】
ユーザによって送られたクエリと、各クエリが送られた頻度とを含むクエリログデータにアクセスするステップと、
最初のクエリの文字の最も有望なシーケンスを前記クエリログデータから決定するステップと、
それぞれの最も有望なシーケンスに関して、最も有望なクエリを前記最も有望なシーケンスおよび前記クエリログデータから決定するステップであって、それぞれの最も有望なクエリは、最初のクエリの文字の前記最も有望なシーケンスに合うクエリの文字の最初のシーケンスを有する、決定するステップと、
最初のクエリの文字の前記最も有望なシーケンスのそれぞれに対して決定された前記最も有望なクエリを前記初期クエリ提案として指定するステップと
をさらに含む請求項17に記載の方法。
【請求項１９】
前記第1のクエリ入力フィールドに入力されたクエリの文字を前記クライアントデバイスから受信するステップと、
前記クライアントデバイスから受信された前記クエリの文字の後に順番に続くクエリの文字である後続のクエリの文字の最も有望なシーケンスを前記クエリログデータから決定するステップと、
後続のクエリの文字のそれぞれの最も有望なシーケンスに関して、最も有望な追加的なクエリを後続のクエリの文字の前記最も有望なシーケンスおよび前記クエリログデータから決定するステップであって、それぞれの最も有望なクエリは、前記クライアントデバイスから受信された前記クエリの文字および後続のクエリの文字の前記最も有望なシーケンスに合うクエリの文字の最初のシーケンスを有する、決定するステップと、
後続のクエリの文字の前記最も有望なシーケンスのそれぞれに対して決定された前記最も有望な追加的なクエリを追加的なクエリ提案として指定するステップと、
前記クエリ提案の要求に応答して前記クライアントデバイスに前記追加的なクエリ提案を提供するステップと
をさらに含む請求項18に記載の方法。
【請求項２０】
前記初期クエリ提案および前記追加的なクエリ提案は、キー値の対の形式であり、前記キー値の対は、クエリの入力シーケンスと、前記クエリの入力シーケンスに合う最初のクエリの文字を有するクエリ提案との対であり、
前記第1のクエリ入力フィールドまたは第2の入力フィールドに入力された前記クエリの文字が前記キー値の対の前記クエリの入力シーケンスのいずれにも合わないと判定することにのみ応じて、前記第1のクエリ入力フィールドまたは前記第2の入力フィールドに入力された前記クエリの文字がクエリ提案の要求として与えられる
請求項19に記載の方法。
【請求項２１】
コンピュータプログラムを符号化されたコンピュータストレージ媒体であって、前記プログラムは、データ処理装置によって実行されるときに、前記データ処理装置に、
検索リソースの要求をクライアントデバイスから受信する動作と、
前記検索リソースの前記要求に応答して前記クライアントデバイスに前記検索リソースを提供する動作であって、前記検索リソースは、
第1のクエリ入力フィールドを含む検索インターフェースを前記クライアントデバイスに生成させる第1の命令、
初期クエリ提案、ならびに
第2の命令であって、前記クライアントデバイスに、
前記初期クエリ提案を前記クライアントデバイスの提案ストアに記憶すること、
前記第1のクエリ入力フィールドに入力されたクエリの文字を前記提案ストアに記憶されたクエリ提案と比較すること、
前記第1のクエリ入力フィールドに入力された前記クエリの文字に合うクエリ提案を比較に基づいて選択すること、および
選択されたクエリ提案を前記第1のクエリ入力フィールドに入力された前記クエリの文字に対するクエリ提案として表示すること
を行わせる、第2の命令
を含む、提供する動作と
を含む動作を行わせる命令を含む、コンピュータストレージ媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、クエリ提案に関する。
【背景技術】
【０００２】
インターネットは、多種多様なリソースへのアクセスを可能にする。例示的なリソースは、動画ファイル、画像ファイル、音声ファイル、または特定の題材、本の記事、もしくはニュース記事に関するコンテンツを含むウェブページを含む。検索システムは、検索クエリを受信することに応答して1つまたは複数のリソースを選択することができる。検索クエリは、ユーザがユーザの情報のニーズを満たすために検索エンジンに送るデータである。検索システムは、検索クエリに対するリソースの関連性、およびその他のリソースと比べたそれらのリソースの重要性に基づいてリソースを選択し、スコアを付けて、選択されたリソースにリンクする検索結果を生成する。通常、検索結果は、スコアに従って順序付けられ、検索結果ページで提供される。
【０００３】
検索システムは、ユーザがユーザの情報のニーズを満たすのを支援するために、検索提案(search suggestion)をユーザに提供することが可能である。本明細書において使用されるとき、用語「クエリ提案」は、検索を改善するため、または検索の方針を改善するために使用可能な提案されるデータである。クエリ提案は、検索クエリまたはキーワードが属する別の検索クエリ、キーワード、またはトピックである可能性がある。クエリ提案は、追加的なクエリとして使用されることが多く、例えば、クエリ提案は、そのクエリ提案をユーザが選択することに応答して検索システムによってクエリとして処理されうる。
【０００４】
一部の検索システムは、ユーザがクエリ全体をタイプすることを必要とせずにクエリ提案を選択することができるように、ユーザがタイプしているときにクエリ提案を提供する。通常、これらのシステムは、キーを打つごとに検索エンジンに提案の要求を送信し、検索エンジンは、入力された文字に合うプレフィックス(prefix)を有するクエリ提案を提供する。この提案サービスは、モバイルデバイスにおいても提供される。しかし、モバイルデバイスは、ずっと高いネットワークレイテンシーに対処する必要があることが多く、提案サービスの性能が、レイテンシーの増加とともに悪化する可能性がある。多くの場合、レイテンシーは、受信された提案が入力された現在のクエリのプレフィックスに合わないようにする可能性があり、このことは、ユーザエクスペリエンスを向上させるどころか損なう傾向がある。
【発明の概要】
【課題を解決するための手段】
【０００５】
概して、本明細書に記載の主題の1つの革新的な態様は、検索リソースの要求をクライアントデバイスから受信する動作と、この要求に応答してクライアントデバイスに検索リソースを提供する動作であって、検索リソースは、第1のクエリ入力フィールドを含む検索インターフェースをクライアントデバイスに生成させる第1の命令、初期クエリ提案(initial query suggestion)、ならびに第2の命令であって、クライアントデバイスに、初期クエリ提案をそのクライアントデバイスの提案ストア(suggestion store)に記憶すること、第1のクエリ入力フィールドに入力されたクエリの文字を提案ストアに記憶されたクエリ提案と比較すること、第1のクエリ入力フィールドに入力されたクエリの文字に合うクエリ提案を比較に基づいて選択すること、および選択されたクエリ提案を第1のクエリ入力フィールドに入力されたクエリの文字に対するクエリ提案として表示することを行わせる、第2の命令を含む、提供する動作とを含む方法で具現化されうる。この態様のその他の実施形態は、コンピュータのストレージデバイスにおいて符号化されたこの方法の動作を実行するように構成された対応するシステム、装置、およびコンピュータプログラムを含む。
【０００６】
概して、本明細書に記載の主題の別の態様は、検索エンジンからの検索リソースの要求を与える動作と、この要求に応答して検索リソースを受信する動作であって、検索リソースが、第1のクエリ入力フィールドを含む検索インターフェースをクライアントデバイスに生成させる第1の命令、初期クエリ提案、ならびに第2の命令であって、クライアントデバイスに、初期クエリ提案をそのクライアントデバイスの提案ストアに記憶すること、第1のクエリ入力フィールドに入力されたクエリの文字を提案ストアに記憶されたクエリ提案と比較すること、第1のクエリ入力フィールドに入力されたクエリの文字に合うクエリ提案を比較に基づいて選択すること、および選択されたクエリ提案を第1のクエリ入力フィールドに入力されたクエリの文字に対するクエリ提案として表示することを行わせる、第2の命令を含む、受信する動作とを含む方法で具現化されうる。この態様のその他の実施形態は、コンピュータのストレージデバイスにおいて符号化されたこの方法の動作を実行するように構成された対応するシステム、装置、およびコンピュータプログラムを含む。
【０００７】
本明細書に記載の主題の1つまたは複数の実施形態の詳細が、添付の図面および以下の説明に記載されている。主題のその他の特徴、態様、および利点は、それらの説明、図面、および特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【０００８】
【図１】クライアントデバイスとデータ通信するクエリ提案システムのブロック図である。
【図２】検索インターフェースリソースを用いて提供されるべき初期クエリ提案を決定するための例示的な方法の流れ図である。
【図３】検索エンジンのインターフェースリソースを用いて初期クエリ提案を提供するための例示的な方法の流れ図である。
【図４】クエリ提案を受信し、クライアントデバイスからクエリ提案を要求するための例示的な方法の流れ図である。
【図５】クライアントデバイスから検索エンジンにクエリ提案の要求を与え、受信されたクエリ提案を処理するための例示的な方法の流れ図である。
【発明を実施するための形態】
【０００９】
さまざまな図面における同様の参照番号および参照指示は、同様の要素を示す。
【００１０】
§1.0  概説
図1は、クライアントデバイス106とデータ通信するクエリ提案システム100のブロック図である。ローカルエリアネットワーク(LAN)、広域ネットワーク(WAN)、インターネット、またはこれらの組合せなどのコンピュータネットワーク102は、パブリッシャー(publisher)104と、クライアントデバイス106と、検索システム110とを接続する。
【００１１】
パブリッシャー104は、ネットワーク102を使用することによってリソースへの電子的なアクセスをホストし、提供する任意のウェブサイトである。ウェブサイトは、ドメイン名に関連する1つまたは複数のリソース105の集合である可能性がある。例示的なウェブサイトは、テキスト、グラフィック画像、マルチメディアコンテンツ、およびスクリプトなどのプログラミング要素を含みうるハイパーテキストマークアップ言語(HTML)形式のウェブページの集合である。
【００１２】
リソースは、ネットワーク102を介してパブリッシャー104によって提供可能な、リソースアドレスによってアドレス指定される、任意のデータである。リソースは、ほんのいくつか例を挙げるとすれば、HTMLページ、ワープロ文書、ポータブルドキュメントフォーマット(PDF)文書、画像、動画、およびフィードソース(feed source)を含む。リソースは、単語、語句、写真などのコンテンツを含む可能性があり、メタ(またはメタデータ)情報およびハイパーリンクなどの埋め込み情報ならびに/または(JavaScript（登録商標）などの)埋め込み命令を含む可能性がある。
【００１３】
それぞれのリソースは、一意的に特定されうるアドレス指定可能な記憶位置を有する。アドレス指定可能な位置は、ユニバーサルリソースロケータ(universal resource locator)(URL)などのリソースロケータによってアドレス指定される。
【００１４】
クライアントデバイス106は、ユーザの制御下にあり、ネットワーク102を介してリソースを要求し、受信することができる電子デバイスである。例示的なクライアントデバイス106は、パーソナルコンピュータ、ラップトップコンピュータ、モバイル通信デバイス、およびネットワーク102を介してデータを送受信することができるその他のデバイスを含む。典型的には、クライアントデバイス106は、ネットワーク102を介したデータの送受信を容易にするための、ウェブブラウザなどのユーザアプリケーションを含む。
【００１５】
検索システム110は、リソースを検索するための検索エンジン118を含む。何千ものパブリッシャーが存在するとき、ネットワーク102を介して利用可能な何百万ものリソースが存在する。これらのリソースの検索を容易にするために、検索エンジン118は、パブリッシャー104をクローリングし、パブリッシャー104によって提供されるリソース105を索引付けすることによってリソースを特定する。索引付けされ、任意的にキャッシュされたリソース105の複製が、リソース索引112に記憶される。概して、リソース索引112は、キーワードに基づく索引、位置に基づく索引、およびその他の索引を含む、リソース105に対するさまざまな種類の索引を含みうる。
【００１６】
クライアントデバイス106は、検索エンジン118に検索クエリを送る。それに応答して、検索エンジン118は、リソース索引112を用いて、クエリに関連するリソースを特定する。検索エンジン118は、リソースを特定し、リソースを特定する検索結果を生成し、検索結果をクライアントデバイス106に返す。検索結果111は、クエリに対応するリソースを特定し、リソースに関するリソースロケータを含む。例示的な検索結果111は、ウェブページのタイトル、ウェブページから抽出されたテキストのスニペット(または一部)、およびウェブページのURLを含みうる。
【００１７】
検索結果は、情報検索(「IR」)スコア(information retrieval ("IR") score)、および任意的にその他のリソースと比べた各リソースの品質スコア(quality score)などの、検索結果によって特定されたリソース105に関連するスコアに基づいてランク付けされる。一部の実装形態において、IRスコアは、検索クエリおよびリソース105に対応する特徴ベクトルの内積から計算され、検索結果のランク付けは、IRスコアと品質スコアとの組合せである初期関連性スコア(initial relevance score)に基づく。検索結果は、これらの初期関連性スコアに従って順序付けられ、その順序に従ってクライアントデバイス106に提供される。
【００１８】
クライアントデバイス106は、検索結果ページを受信し、ユーザのブラウザなどにおいて、ユーザに対する表示のためにそれらのページをレンダリングする。ユーザがクライアントデバイス106において検索結果を選択することに応答して、検索結果111が参照するリソース105が、要求元のクライアントデバイス106に提供される。
【００１９】
クライアントデバイスから送られたクエリは、クエリログ114に記憶される。クエリと検索結果によって参照されるウェブページとに関するクリックデータが、クリックログ116に記憶される。クリックデータは、検索エンジン118によって与えられた検索結果に応じて行われる動作を定義する。クエリログ114およびクリックログ116は、クライアントデバイスによって送られたクエリを検索結果で特定されたウェブページおよびユーザによって行われた動作(すなわち、各識別子に関する検索履歴がアクセスされうるように、検索要求からの識別子に関連づけられるデータ)にマッピングするために使用されうる。時間データも記憶される場合、それらのアクションが行われた相対的な時間と、クエリがいつ送られたかも判定されうる。したがって、クリックログ116およびクエリログ114は、クライアントデバイスによって送られた一連のクエリ、クエリに応答して(例えば、ユーザによって)行われた動作、およびクエリがどれぐらいの頻度で送られるかを追跡するために検索エンジンによって使用されうる。
【００２０】
一部の実装形態においては、検索システム110は、ユーザがクエリをタイプしている間にクエリ提案を決定し、提供することができる。例として、クライアントデバイス106のユーザが、「new y...」で始まるクエリを入力している可能性がある。検索システム110は、「new york」、「new york city」、「new york times」などの提案されるクエリの完成形または提案を提供する可能性がある。提案は、例えば、ユーザがクエリをタイプし始めた検索ボックスに隣接するような、ユーザのウェブブラウザ内の提案ボックス内に現れる可能性がある。提案ボックスが、ユーザが意図し、したがってユーザによって認められるクエリを含む場合、ユーザは提案を選択する(例えば、クリックする)ことができ、提案が検索ボックス内のユーザの不完全なクエリを置き換えることができる。結果として、ユーザは、クエリ全体を入力する必要がない。
【００２１】
このクエリ提案のプロセスは、比較的速くクエリ提案を処理するためのネットワーク帯域幅を有するユーザのパーソナルコンピュータまたはその他のコンピューティングデバイスにおいて良好に動作することができる。しかし、携帯電話およびスマートフォンなどの一部のモバイル通信デバイスは、デスクトップPCへの有線接続のレイテンシーと比較してより高いネットワークレイテンシーを有する可能性がある。結果として、提案プロセスは、ユーザがクエリをタイプするプロセスを邪魔するほど低速になる可能性がある。この1つの理由は、ユーザがさらなるキーの打ち込みを終えた後に提案が到着するときに、その遅延が、一部の提案を現在入力されているクエリに適用できなくする影響を有する可能性があることである。
【００２２】
一部のコンピューティングデバイスの接続(例えば、モバイル通信デバイスの接続)に固有のネットワークレイテンシーを克服するために、検索システム110は、提案が不完全に入力されたクエリのみから別な方法で予測可能になりうるよりも前にそれらの提案をうまく予測することができる。例えば、検索システム110は、ユーザのクライアントデバイス106が有望な提案を表示するよりも前にそれらの有望な提案をうまく決定することを開始するために、ユーザのクエリの履歴を使用することができる。検索システム110によって与えられる提案は、クライアントデバイス106に提供可能であり、次に、クライアントデバイス106が、キャッシュとローカルストレージとを用いて、それらの提案が必要とされる前にそれらの提案をクライアントデバイス106において利用可能にすることができる。
【００２３】
再び図1を参照すると、検索システム110は、提案アグリゲータ127および提案サーバ128を含む。提案アグリゲータ127は、ユーザがタイプしたか、またはタイプする可能性が最も高い内容に基づく不完全なクエリに対する選択の集約された組を生成することができるサーバサイドコードモジュールである。提案サーバ128は、1つの特定の不完全なクエリに関する完全な提案されるクエリを提供することができるサーバサイドコードモジュールである。提案アグリゲータ127および提案サーバ128は、個別提案要求/応答インターフェース129を用いて通信することができる。例えば、提案アグリゲータ127は、提案サーバ128に要求(例えば、不完全なクエリ)を送信することができ、それに応答して、提案サーバ128は、対応する応答(例えば、不完全なクエリに合う提案)を返すことができる。一部の実装形態においては、提案アグリゲータ127および提案サーバ128は、単一のコンポーネントへと組み合わされる可能性がある。
【００２４】
提案アグリゲータ127は、検索エンジン118とも通信する。例えば、検索エンジン118が(例えば、ユーザのブラウザ130から)受信するクエリに基づいて、検索エンジン118は、よくある/関連する提案の要求131を提案アグリゲータ127に送信することができる。それに応答して、提案アグリゲータ127は、(例えば、提案サーバ128とのインターフェースをとることによって)提案を特定し、集約された提案132を検索エンジン118に送信することができる。結果として、予めキャッシュされる提案が、ブラウザ130で使用するために検索エンジン118がクライアントデバイス106に提供する検索ページに含められることもある。一緒に働くことで、検索エンジン118、提案アグリゲータ127、および提案サーバ128は、システム100内で提案を生成するために使用されるサーバサイドの処理を提供する。
【００２５】
不完全なクエリおよび結果として得られる提案の例として、典型的なフローは、以下のようにすることができる。クライアントデバイス106上でブラウザ130を実行するユーザが、HTMLの検索ページを要求する可能性がある。ユーザは、(例えば、新品のモバイル通信デバイス上で)ブラウザ130を初めて使用している可能性があり、またはユーザは、そのユーザのクライアントデバイス106上で以前に何度かブラウジングしたことがある可能性があり、単に新しいブラウジングセッションを開始している。提供される検索ページは、一部の実装形態においては、初期クエリ提案を含む。例えば、提案は、クエリログ114に記憶された情報を用いて、すべてのユーザの過去のクエリに基づく可能性がある。これらの提案を用いて、検索システム110は、ユーザがクエリを入力し始める前であっても、予めキャッシュされる提案を伴う検索ページ136をユーザのブラウザ130に提供することができる。
【００２６】
クライアントデバイス106が、予めキャッシュされる提案を伴う検索ページ136を受信する。検索ページの通常のHTMLコードに加えて、検索ページは、検索履歴と、多くの不完全なクエリおよび関連する提案のキャッシュとを管理することができる追加的な命令、例えば、JavaScript（登録商標）コード140を含む。検索ページは、ユーザがそのユーザのクエリにおいてタイプする可能性が高い最初の数文字に基づく最も有望な提案の組も含む。検索システム110から受信された提案は、ブラウザ130内のローカルストレージ142に記憶される。
【００２７】
ユーザがブラウザ130内の検索フィールドに文字(例えば、「ne」)をタイプするとき、ローカルストレージ142内の提案のキャッシュが、その不完全なクエリを含むかどうかを確認するために調べられる。提案のキャッシュがその不完全なクエリを含む場合、その不完全なクエリに対する提案が、ブラウザ130においてユーザに対して即座に表示可能である。一部の実装形態においては、要求(例えば、先読み(look-ahead)を用いた提案の要求134)が、ユーザがそれまでにタイプしたか、次にタイプする可能性が最も高い内容に基づくさらなる不完全なクエリに対する集約された提案135を得るために提案アグリゲータ127にやはり送信される。このようにして、システム100は、高い頻度でユーザに先んじ、ユーザが任意の不完全なクエリをタイプし終わる前にその不完全なクエリに対する利用可能な提案を持つことができる。特に、多くのユーザはある期間にわたって同様の(またはさらには同一の)クエリを実行する傾向があるので、この性能は、キャッシュが増えるにつれて時間とともに向上する可能性がある。
【００２８】
通信が高いレイテンシーに見舞われる可能性があるが、予めキャッシュされた提案の存在が、追加的な提案が検索システム110から適時受信されない場合であってもクエリ提案の生成を可能にする。追加的な提案が適時受信される(すなわち、それらの提案が、不完全なクエリに合うプレフィックスを有するなど、入力されている不完全なクエリとまだ関連性があるときに受信される)場合、それらの提案が、提案として表示可能である。しかし、追加的な提案が適時受信されない(すなわち、それらの提案が、不完全なクエリに合うプレフィックスを持たないなど、入力されている不完全なクエリともはや関連性がないときに受信される)場合、それらの提案は、ありうる提案として後で使用するためにローカルストレージ142に記憶されうる。
【００２９】
一部の実装形態においては、検索エンジン118が、ユーザが入力した前の関連するクエリに基づく追加的な予めキャッシュされる提案を伴う検索結果144を提供することもできる。例えば、前のクエリは、その検索結果ページを用いて提供される検索結果を特定するために使用されるクエリである可能性がある。(例えば、クエリ「new york times」に対応する)対応する検索結果に付随するこのクエリ(例えば、「new york times」)に基づいて、検索エンジン118は、関連する提案(例えば、「LA times」、「New York Post」など)を提供する。
【００３０】
関連する提案を特定するために、検索エンジン118は、クエリログ114からの過去のユーザのクエリと、クリックログ116からの対応するウェブページとのユーザのインタラクションの履歴とについての情報を用いることができる。追加的な予めキャッシュされる提案を伴う検索結果144は、前のクエリに基づく追加的な提案を伴うHTML検索結果ページ146としてブラウザ130によって記憶されうる。
【００３１】
提案を予めキャッシュするこのプロセスは、ユーザがクエリの文字の入力を続けるときは継続することができる。ローカルストレージ142内の最も有望な提案を更新し、キャッシュすることによって、ブラウザ130は、より高いネットワークレイテンシーを有する可能性があるモバイル通信デバイスにおいてさえ、ユーザがタイプするいかなる内容にも先んじることができる。結果として、キャッシュされた提案は、数回(例えば、2回以上の)キーの打ち込みの分だけユーザに先んじ続けることができる。これは、「新鮮でない」提案、または言い換えると、もはや適用可能でない、2回もしくは3回分のキーの打ち込みをさかのぼったユーザの不完全なクエリに基づいていた提案を表示することを防止することができる。例えば、(その時点で)不完全なクエリ「ne」に基づいてもともとキャッシュされた「Nebraska」で始まる提案は、ユーザが不完全なクエリ「new」をもたらす別の文字(例えば、「b」ではなく「w」)をそれ以降に入力した場合、「新鮮でない」ことになる。
【００３２】
ローカルストレージ142は、クライアントデバイス106において必要とされうる任意の種類の提案に関連するデータを記憶することができる。例えば、ローカルストレージ142は、HTML、HTML5、Google Gears、単純なJavaScript（登録商標）のオブジェクト、またはユーザのブラウザ130において提案をサポートし、表示するために必要とされる任意のその他のキャッシュされる情報を含みうる。
【００３３】
一部の実装形態においては、検索システム110によって提供される提案は、キー値(key value)の対の形式であり、ローカルストレージ142に記憶される予めキャッシュされる提案は、キー値の対として記憶される。キー値の対は、クエリの入力シーケンス(例えば、不完全なクエリ)、およびそのクエリの入力シーケンスに合う最初のクエリの文字を有するクエリ提案である可能性がある。例えば、1つのキー値の対は、入力シーケンス「ne」、および「new york」、「new york city」、「new york times」、「Nebraska football」などのクエリ提案である可能性がある。例えば、予めキャッシュされる提案をこのようにして記憶することは、ブラウザ130がユーザの現在の不完全なクエリに基づいて提案にアクセスし、それらの提案を表示するプロセスを高速化することができる。
【００３４】
§2.0  初期クエリ提案の決定
図2は、検索インターフェースリソースを用いて提供されるべき初期クエリ提案を決定するための例示的な方法200の流れ図である。検索インターフェースリソースは、検索エンジンをホストするためのホームページなどの、ユーザが検索クエリを入力するページである。検索システム110は、問い合わせの時間より前に、すなわち、ユーザによって入力されるユーザのクエリの処理とは別個のバックエンドプロセスで方法200のステップを実行することが好ましい。初期クエリ提案が決定されると、初期提案は、検索インターフェースリソースを用いて提供される。
【００３５】
ユーザによって送られたクエリと、各クエリが送られた頻度とを含むクエリログデータが、アクセスされる(202)。例えば、検索システム110は、クエリログ114にアクセスすることができる。アクセスされる情報は、複数のユーザによって前に入力された特定のクエリ、検索結果の選択、およびクエリが入力された頻度を含む。
【００３６】
最初のクエリの文字の最も有望なシーケンスが、クエリログデータから決定される(204)。決定は、クエリログ114に記憶される完全な前のクエリおよびそれらのクエリの頻度に基づく可能性がある。一部の実装形態においては、最も有望なシーケンスを決定するために使用されるクエリの頻度は、前年または前月などの特定の期間に限られる。
【００３７】
それぞれの最も有望なシーケンスに関して、最も有望なクエリが、その最も有望なシーケンスおよびクエリログデータから決定される(206)。例えば、「new」という有望なシーケンスに関して、検索システム110は、それぞれが非常に高い相対的頻度で入力されたクエリ「new york times」および「new york city」が最も有望なクエリであると決定する可能性がある。比較によって、検索システム110は、前に頻度が比較的低かったクエリ「new day rising」はシーケンス「new」に対する可能性がより低いクエリであると決定する可能性がある。プロセスは、その他の最も有望なシーケンス(例えば、「abc」、「xyz」など)に対して繰り返される。
【００３８】
一部の実装形態においては、クエリの頻度分析が、ユーザの国および言語における履歴的なクエリを見て、最も有望な最初の文字のシーケンスを計算することによって最も有望なシーケンスおよび最も有望なクエリを決定するために使用されうる。大きなキャッシュヒット率が、ほんのわずかな量の予めキャッシュされたデータを用いて、最初の数文字に対して実現されうる。
【００３９】
最初のクエリの文字の最も有望なシーケンスのそれぞれに対して決定された最も有望なクエリが、初期クエリ提案として指定される(208)。例として、最も有望なクエリは、検索ページ140を用いて提供される予めキャッシュされる提案136を生成するために使用されうる。
【００４０】
一部の実装形態において、最も有望なシーケンスのそれぞれに対して決定された最も有望なクエリは、まとめてグループ化される。例えば、クエリは、それらのクエリに割り当てられた見込みスコア(likelihood score)を有する可能性があり、このスコアを使用して、提案を見込み(likelihood)の降順に並べることができる。結果として、検索システム110によって与えられる提案のリストは、最も有望な提案(例えば、「new york times」)を最初に示し、2番目に有望な提案(例えば、「new york yankees」)をその次に示し、以下同様に示すことができる。一部の実装形態において、ブラウザ130は、提案がユーザが意図したものであるという見込みの順序で提案を表示する。その他の実装形態においては、提案は、アルファベット順などのその他の順序で表示される可能性がある。
【００４１】
§2.1  追加的なクエリ提案の決定
方法200は、ユーザデバイスから受信された不完全なクエリに基づいて追加的な提案を生成するために検索システム110によって使用されることもできる。追加的な提案は、(例えば、検索結果ページを例えば用いて)初期提案に続いて与えられる。検索システム110は、上述のクエリの頻度分析、プレフィックス分析、および文字の頻度分析を含む、不完全なクエリを処理するためのさまざまな技術を使用することができる。プレフィックス分析は、不完全なクエリを調べ、履歴的なクエリデータを分析することに基づいて最も有望な完全なクエリを決定することができる。この技術は、ユーザがタイプする文字ごとにネットワーク要求を行うことを必要とせずに、最も有望な中間的な不完全なクエリ(例えば、「new」または「new york」)に対する予めキャッシュされる提案を生成するためにそれらの不完全なクエリを予測することができる。
【００４２】
文字の頻度分析は、例えば、不完全なクエリの最後の(例えば、最後に入力された)文字に基づいて履歴的なクエリを処理することによって最も有望な後に続く文字を予測するために使用されうる。例えば、クエリの残りがまれであり、プレフィックス分析に適さない場合であっても、英語ユーザが「q」とタイプするときはいつも、後に続く文字は「u」である可能性がかなり高い。したがって、「q」で終わる不完全なクエリに対する応答は、文字「u」を含む別の要求を必要とせずに、同じ不完全なクエリの後に「u」を続けたものに対する提案も含む。
【００４３】
加えて、検索システム110は、ユーザから受信された完全なクエリを処理して追加的なクエリ提案を提供することができる。例えば、検索システム110は、関連検索分析(related search analysis)を用いてクエリ提案を特定することができる。関連検索分析は、ユーザによって実行された完全なクエリが与えられるとき、ユーザがタイプする可能性が高いその他のクエリを予測することができる。それらのクエリは、ユーザがそれらのクエリをタイプする場合にネットワーク要求を必要とせずに利用できるようにHTML検索結果ページにそれらのクエリに対する予めキャッシュされる提案として含められることもある。
【００４４】
最後に、クライアントデバイスが、クエリの履歴を用いてクライアント上でクエリ提案を生成することもできる。クエリの履歴は、ユーザが前のクエリを繰り返す可能性が非常に高いという見込みに基づいて提案を生成するために使用されうる。例えば、ユーザの前のクエリが、ネットワーク要求をせずに表示されうるようにローカルに(例えば、ローカルストレージ142に)キャッシュされる可能性がある。一部の実装形態においては、ローカルにキャッシュされたクエリは、タイムスタンプおよび頻度を含む可能性があり、頻度の数が少ないクエリまたは最近(例えば、前月もしくは前年などに)使用されていないクエリは、キャッシュ空間を解放するために削除される可能性がある。
【００４５】
§3.0  予めキャッシュされるクエリ提案の提供
図3は、検索エンジンのインターフェースリソースを用いて初期クエリ提案を提供するための例示的な方法300の流れ図である。例えば、検索システム110は、サーバ指向のプロセスである方法300のステップを実行することができる。方法300は、検索システム110が予めキャッシュされるクエリの初期の組をクライアントデバイスにどのようにして提供するか、および検索システム110が予めキャッシュされるクエリの追加的な組をクライアントデバイスにどのようにして提供するかを示す。
【００４６】
検索リソースの要求が、クライアントデバイスから受信される(302)。例として、検索システム110が、クライアントデバイス106から検索リソースページの要求を受信する。要求は、例えば、ユーザがブラウザアプリケーションを開始し、検索システム110のホームページにナビゲートするときに、クライアントデバイス106上で実行されているユーザのブラウザ130から送信されうる。
【００４７】
検索リソースが、検索リソースの要求に応答してクライアントデバイスに提供される(304)。検索リソースに含まれるのは、第1のクエリ入力フィールドを含む検索インターフェースをクライアントデバイスに生成させる第1の命令、および初期クエリ提案である。例として、検索システム110は、予めキャッシュされる提案を伴う検索ページ136をクライアントデバイス106に送信することができる。検索ページは、ユーザのブラウザ130上で実行可能なHTMLコードの形式である可能性がある。提案は、上述の方法200によって決定された提案である可能性がある。検索リソースは、クライアントデバイスに初期クエリ提案をそのクライアントデバイスの提案ストアに記憶させる、JavaScript（登録商標）コードなどの第2の命令も含む。
【００４８】
検索リソースがクライアントデバイス上でレンダリングされた後、ユーザがクエリを入力するときに、第2の命令は、さらに、クライアントデバイスにクエリ入力フィールドに入力されたクエリの文字を提案ストアに記憶されたクエリ提案と比較させ、第1のクエリ入力フィールドに入力されたクエリの文字に合うクエリ提案を比較に基づいて選択させる。第2の命令を実行するクライアントデバイスは、次に、選択されたクエリ提案を第1のクエリ入力フィールドに入力されたクエリの文字に対するクエリ提案として表示する。ユーザは、提案されたクエリのうちの1つを選択する可能性があり、またはクエリの入力を続ける可能性がある。最終的に、ユーザは(提案のうちの1つを選択するか、またはクエリをタイプするかのいずれかによって)クエリを入力し、クライアントデバイスに検索システム110へクエリを送信させる。
【００４９】
比較の動作に関して、提案ストアのローカルストレージ142に記憶された予めキャッシュされたクエリが直ちに利用できるので、クライアントデバイス106は、検索システム110からの追加的な提案を要求し、それらの追加的な提案を受信するのを待つ必要がない。上述のように、一部の実装形態においては、要求(例えば、先読みを用いた提案の要求134)が、ユーザがそれまでにタイプしたか、次にタイプする可能性が最も高い内容に基づくさらなる不完全なクエリに対する追加的な集約された提案135を得るために提案アグリゲータ127にやはり送信される。追加的な提案が適時受信される場合、それらの追加的な提案は、提案として表示可能であり、追加的な提案が適時受信されない場合、それらの提案は、ありうる提案として後で使用するためにローカルストレージ142に記憶されうる。
【００５０】
クエリが、クライアントデバイスから受信される(306)。例として、検索システム110が、クライアントデバイス106からクエリを受信することができる。クエリは、ユーザがタイプしたか、または提案から選択したか、またはこれら2つの何らかの組合せかのいずれかである完全なクエリである可能性がある。
【００５１】
検索結果リソースが、クライアントデバイスから受信されたクエリに応答して提供される(308)。検索結果リソースは、クエリに対応すると判定されたリソースを参照する検索結果と、追加的なクエリ提案とを表示する検索結果ページをクライアントデバイスに生成させる第3の命令を含む。例として、図1を参照すると、検索システム110は、検索結果リソースを、追加的な予めキャッシュされる提案を伴う検索結果144の形式でクライアントデバイス106に提供することができる。
【００５２】
検索結果リソースは、クライアントデバイス106がブラウザ130に検索結果を表示するために使用することができるHTMLコードを含む。さらに、検索結果リソースは、検索システム110が上述のようにクエリログ114からの、または別のクエリ提案サービスからの情報を用いて得ることができる追加的なクエリ提案を含みうる。一部の実装形態においては、追加的な予めキャッシュされる提案は、その検索結果リソースのための検索結果を特定するために選択され、使用されたクエリに基づく。検索結果リソースは、クライアントデバイスに追加的なクエリ提案をそのクライアントデバイスの提案ストアに記憶させる、JavaScript（登録商標）コードなどの第4の命令も含む。結果として、予めキャッシュされた提案は、ユーザの関心により関連性のあるクエリ提案を含み始め、ユーザのブラウザ130は、パーソナライズされた予めキャッシュされた提案を表示し始める可能性がある。
【００５３】
検索結果リソースがクライアントデバイス上でレンダリングされた後、ユーザが、検索結果リソースのクエリ入力フィードに別のクエリを改めて入力する可能性がある。第4の命令は、さらに、クライアントデバイスにクエリ入力フィールドに入力されたクエリの文字を提案ストアに記憶されたクエリ提案と比較させ、第1のクエリ入力フィールドに入力されたクエリの文字に合うクエリ提案を比較に基づいて選択させる。第4の命令を実行するクライアントデバイスは、次に、選択されたクエリ提案を第1のクエリ入力フィールドに入力されたクエリの文字に対するクエリ提案として表示する。
【００５４】
§4.0  予めキャッシュされる提案のクライアントサイドの処理
図4は、クエリ提案を受信し、クライアントデバイスからクエリ提案を要求するための例示的な方法400の流れ図である。クライアントデバイス106は、例えば、ステップの一部に関して検索システム110とインタラクションして方法400のステップを実行することができる。
【００５５】
検索エンジンからの検索リソースの要求が、与えられる(402)。例として、クライアントデバイス106は、検索システム110に検索リソースの要求を与えることができる。要求は、例えば、ユーザがブラウザアプリケーションを開始し、検索システム110のホームページにナビゲートするときに、クライアントデバイス106上で実行されているユーザのブラウザ130から送信されうる。
【００５６】
検索リソースの要求に応答して検索リソースが、受信される(404)。例として、クライアントデバイス106は、予めキャッシュされる提案を伴う検索ページ136を検索システム110から受信することができる。検索ページは、クライアントデバイスがクエリ入力フィールドおよび初期クエリ提案を含む検索インターフェースを生成することを可能にする命令を含みうる。検索ページは、ユーザのブラウザ130上で実行可能なHTMLコードの形式である可能性がある。検索ページは、上述のように予めキャッシュされる提案を処理することができる第2の命令、例えば、JavaScript（登録商標）コードも含みうる。
【００５７】
初期クエリ提案が、クライアントデバイスの提案ストアに記憶される(406)。例えば、第2の命令を実行するクライアントデバイス106が、初期クエリ提案をローカルストレージ142に記憶する。このようにして、ユーザが提案から選択する可能性が高いクエリが、クライアントデバイス106で利用可能であり、予めキャッシュされる。
【００５８】
第1のクエリ入力フィールドに入力されたクエリの文字が、提案ストアに記憶されたクエリ提案と比較される(408)。例として、ユーザがクエリ入力フィールドに入力するクエリの文字が、ローカルストレージ142に記憶されたクエリ提案と比較される。例えば、ユーザの不完全なクエリ「ne」が、ローカルストレージ142に記憶された提案(例えば、「new york times」など)と比較されうる。
【００５９】
第1のクエリ入力フィールドに入力されたクエリの文字に合うクエリ提案が、比較に基づいて選択される(410)。例えば、クライアントデバイス106が、第1のクエリ入力フィールドに入力されたクエリの文字に合うクエリ提案を比較に基づいて選択することができる。この場合、提案「new york times」および「ne」で始まるその他の提案が、それらの提案が不完全なクエリ「ne」に合うので選択される。
【００６０】
選択されたクエリ提案が、第1のクエリ入力フィールドに入力されたクエリの文字に対するクエリ提案として表示される(412)。選択されたクエリ提案は、第1のクエリ入力フィールドに隣接する提案ボックスに表示される可能性がある。例として、ユーザが第1のクエリ入力フィールドに「ne」とタイプしたとき、ユーザのブラウザ130が、その不完全なクエリに合う「new york times」などの提案を表示することもできる。ブラウザは、ローカルストレージ142からそれらの提案を取得することができる。ユーザがクエリに対して追加的な文字をタイプする場合、ローカルストレージから取得される提案が、現在の不完全なクエリに合うように変わることができる。
【００６１】
一部の実装形態においては、ローカルストレージ142が(例えば、ユーザの現在のユーザセッションおよび不完全なクエリに基づく)最近予めキャッシュされたクエリ提案を含むことに加えて、ローカルストレージ142が、例えば、事前に決められた期間中(例えば、前月中)などにブラウザに最近入力されたクエリに基づく保存されたクエリ提案を含む可能性がある。
【００６２】
方法400が検索リソース(例えば、検索システムのホームページ)を受信することに関連して説明されているが、方法400は、追加的なクエリ提案を含む検索結果ページを受信することに関連して適用されることもできる。
【００６３】
§5.0  検索システムに対するクライアントサイドの検索提案の要求
図5は、クライアントデバイスから検索エンジンにクエリ提案の要求を与え、受信されたクエリ提案を処理するための例示的な方法500の流れ図である。例えば、クライアントデバイス106が、方法500のステップを実行することができる。
【００６４】
第1のクエリ入力フィールドに入力されるクエリの文字が、クエリ提案の要求として検索システム110に与えられる(502)。例えば、ユーザが、検索リソースまたは検索結果リソースのクエリ入力フィールド(例えば、検索ページまたは検索結果ページの検索ボックス)に不完全なクエリ「ne」を入力する可能性がある。クライアントデバイス106は、入力を、先読みを用いた提案の要求134として検索システム110に送信することができる。要求が送信されるときに、クライアントデバイス106は、ローカルストレージ142に記憶されたいくらかの予めキャッシュされた提案を既に有する可能性があり、それらの予めキャッシュされた提案の一部はユーザの現在の不完全なクエリに関連する可能性があり、クライアントデバイス106は、これらの予めキャッシュされた提案を処理して、ユーザに対して示すべきクエリ提案を決定することができる。
【００６５】
要求に応答して、追加的なクエリ提案が、データ処理装置から受信される(504)。例えば、クライアントデバイス106が、集約された提案135を検索システム110から受信することができる。受信される提案は、例えば、上述のようにクエリログ114およびクリックログ116を用いて検索システム110によって生成されるか、または別個の提案サービスから受信される可能性がある。追加的な提案が適時受信される(すなわち、それらの提案が、不完全なクエリに合うプレフィックスを有するなど、入力されている不完全なクエリとまだ関連性があるときに受信される)場合、それらの提案が、提案として表示可能である。しかし、追加的な提案が適時受信されない(すなわち、それらの提案が、不完全なクエリに合うプレフィックスを持たないなど、入力されている不完全なクエリともはや関連性がないときに受信される)場合、それらの提案は、ありうる提案として後で使用するためにローカルストレージ142に記憶されうる。
【００６６】
追加的なクエリ提案が、提案ストアに記憶される(506)。例えば、クライアントデバイス106が受信する提案の出所に関係なく、提案は、ローカルストレージ142にキャッシュされうる。それ以降、ローカルストレージ142に記憶された予めキャッシュされた提案が、ユーザの現在の不完全なクエリに合う提案を表示するためにブラウザ130によって使用されうる。さらに、提案は、クエリ提案のより後の処理のためにクライアントデバイス106で利用できる可能性がある。
【００６７】
§6.0  位置に固有の提案の事前キャッシュ
一部の実装形態において、提案アグリゲータ127は、クライアントデバイス106の位置を示す位置データを考慮し、位置データを用いて、キャッシュするための位置に固有のクエリ提案を提供する。ローカルストレージ142は、一部の実装形態において、位置に固有のクエリ提案をそれらの位置、例えば、位置L1、L2...Lnによって関連づける。位置に固有のクエリ提案は、必ずしも位置に固有ではない上で与えられたクエリ提案を増強するために使用され、すなわち、位置に固有のクエリ提案は、位置に依存しないクエリ提案を増強するために使用される。
【００６８】
例えば、一部の実装形態において、検索結果ページを用いて提供される予めキャッシュされる提案136および検索結果ページを用いて提供される追加的な提案は、位置に依存しないクエリ提案および位置に固有のクエリ提案を含む。本明細書において使用されるとき、位置に依存しないクエリ提案は、クライアントデバイスの位置に関係なくクエリ提案として表示されるのに適したクエリ提案である。反対に、位置に固有のクエリ提案は、位置または地域に関連づけられ、クライアントデバイスがその位置または地域内にあるときにクエリ提案として表示されることにのみ適するクエリ提案である。
【００６９】
位置に固有のクエリ提案は、特定の位置に固有であることを除いて、上で説明されたのと同様にして生成される。例えば、位置に固有のクエリ提案の初期の組を決定するため、および追加的な位置に固有のクエリ提案を決定するための方法は、処理されるクエリが特定の位置内にあるデバイスから受信されたクエリに制限されることを除いて、図2に示されたステップと同様のステップを実行する。
【００７０】
クエリ提案に関する関連する位置情報は、クライアントデバイスによって提供される位置データ、例えば、GPS座標、特定の地方の地域に解決されるIPアドレスなどから与えられる。例えば、クライアントデバイスのユーザがCaliforniaのMountain Viewに住んでいると仮定する。結果として、ユーザデバイスは、位置に依存しないクエリ提案と、(位置L1によって示される)CaliforniaのMountain Viewの地域に固有の位置に固有のクエリ提案とを含む。ユーザがバーベキューレストランで食事を楽しみ、Mountain Viewにいる間にテキスト「barbeque」をクエリとして入力し始めるとさらに仮定する。テキストが入力されているときに、入力された文字列に合うクエリ提案は、位置に依存しないクエリ提案から、およびクエリ提案のただ1つの位置に固有の組、すなわち、位置L1に関連するクエリ提案から与えられる。これらの文字のクエリ提案は、例えば、CaliforniaのMountain Viewの地域内のレストラン名、およびCaliforniaのMountain Viewの位置に固有のクエリに合うその他のものを含む。
【００７１】
後日、ユーザは、位置L2によって示されるGeorgiaのAtlantaを訪れる。ユーザがGeorgiaのAtlantaの地域内で初めてクライアントデバイス106を使用するとき、ユーザは、検索ページを用いてAtlantaに固有の初期クエリ提案の組を提供され、与えられたそれぞれの検索結果ページを用いて追加的なAtlantaに固有のクエリ提案を与えられる。位置に依存しないクエリ提案も、やはり提供される可能性がある。したがって、ユーザがAtlantaにいる間に検索クエリ「barbeque」を入力し始めるとき、入力された文字列に合うクエリ提案は、位置に依存しないクエリ提案から、およびクエリ提案のただ1つの位置に固有の組、すなわち、位置L2に関連するクエリ提案から提供される。これらの文字のクエリ提案は、例えば、GeorgiaのAtlantaの地域内のレストラン名、およびGeorgiaのAtlantaの位置に固有のクエリに合うその他のものを含む。
【００７２】
ユーザに対して表示するための位置に固有のクエリ提案の処理は、一部の実装形態においては、フィルタリングプロセスによって行われる場合もある。例えば、検索リソースの要求が、クライアントデバイス106の現在の位置を特定する位置データを含むと仮定する。位置に依存しないクエリ提案に加えて、初期クエリ提案の組は、クライアントデバイスの現在の位置に固有である位置に固有のクエリ提案を含む。同様に、検索結果ページを用いて提供されるクエリ提案は、クライアントデバイスの現在の位置に固有である位置に固有のクエリ提案をやはり含む。ユーザに対して表示するためのクエリ提案を選択するとき、ブラウザで命令を実行するクライアントデバイスは、クライアントデバイスの現在の位置に固有ではない位置に固有のクエリ提案を除外する。したがって、上述のように、ユーザがGeorgiaのAtlantaの地域内にいるとき、CaliforniaのMountain Viewに関する位置に固有のクエリ提案は、これらのクエリ提案が現在の位置GeorgiaのAtlantaに固有ではないので提供されない。
【００７３】
位置に固有のクエリ提案をフィルタリングし、提供するその他の方法も、使用されうる。
【００７４】
§7.0  さらなる実装形態の詳細
本明細書に記載の主題の実施形態および動作は、本明細書で開示された構造およびそれらの構造的均等物を含む、デジタル電子回路、またはコンピュータソフトウェア、ファームウェア、もしくはハードウェア、またはそれらのうちの1つもしくは複数の組合せで実施されうる。本明細書に記載の主題の実施形態は、1つまたは複数のコンピュータプログラム、すなわち、データ処理装置による実行のために、またはデータ処理装置の動作を制御するためにコンピュータストレージ媒体において符号化されたコンピュータプログラム命令の1つまたは複数のモジュールとして実施されうる。代替的にまたは追加的に、プログラム命令は、データ処理装置による実行のために好適な受信機装置に送信するために情報を符号化するように生成される人為的に生成された伝播信号、例えば、機械によって生成された電気的信号、光学的信号、または電磁的信号に符号化されうる。コンピュータストレージ媒体は、コンピュータ可読ストレージデバイス、コンピュータ可読ストレージ基板、ランダムもしくはシリアルアクセスメモリアレイもしくはデバイス、またはそれらの1つもしくは複数の組合せであるか、またはそれらに含まれる可能性がある。さらに、コンピュータストレージ媒体は伝播信号ではないが、コンピュータストレージ媒体は、人為的に生成された伝播信号に符号化されたコンピュータプログラム命令の送信元または送信先である可能性がある。コンピュータストレージ媒体は、1つまたは複数の別個の物理コンポーネントまたは媒体(例えば、複数のCD、ディスク、またはその他のストレージデバイス)であるか、またはそれらに含まれる可能性もある。
【００７５】
本明細書に記載の動作は、1つもしくは複数のコンピュータ可読ストレージデバイスに記憶された、またはその他のソースから受信されたデータに対してデータ処理装置によって実行される動作として実施されうる。
【００７６】
用語「データ処理装置」は、例として、1つのプログラム可能なプロセッサ、1台のコンピュータ、1つのシステムオンチップ、またはそれらの複数もしくは組合せを含む、データを処理するためのすべての種類の装置、デバイス、および機械を包含する。装置は、専用の論理回路、例えば、FPGA(フィールドプログラマブルゲートアレイ)またはASIC(特定用途向け集積回路)を含みうる。装置は、ハードウェアに加えて、問題にしているコンピュータプログラムのための実行環境を生成するコード、例えば、プロセッサのファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、クロスプラットフォームランタイム環境、仮想マシン、またはそれらのうちの1つもしくは複数の組合せを構成するコードも含みうる。装置および実行環境は、ウェブサービスインフラストラクチャ、分散コンピューティングインフラストラクチャ、およびグリッドコンピューティングインフラストラクチャなどの、さまざまな異なるコンピューティングモデルインフラストラクチャを実現することができる。
【００７７】
コンピュータプログラム(プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、またはコードとしても知られる)は、コンパイラ型言語もしくはインタープリタ型言語、宣言型言語もしくは手続き型言語を含む任意の形式のプログラミング言語で記述可能であり、独立型プログラムとしての形式、またはモジュール、コンポーネント、サブルーチン、オブジェクト、もしくはコンピューティング環境での使用に適したその他の単位としての形式を含む任意の形式で配置されうる。コンピュータプログラムは、ファイルシステム内のファイルに対応する可能性があるが、ファイルシステム内のファイルに対応することは必須ではない。プログラムは、その他のプログラムもしくはデータを保持するファイルの一部(例えば、マークアップ言語の文書に記憶された1つもしくは複数のスクリプト)、問題にしているプログラムに専用の単一のファイル、または複数の組織されたファイル(例えば、1つもしくは複数のモジュール、サブプログラム、もしくはコードの一部を記憶するファイル)に記憶されうる。コンピュータプログラムは、1つのコンピュータにおいて、または1つの場所に置かれるか、もしくは複数の場所に分散され、通信ネットワークによって相互に接続されている複数のコンピュータにおいて実行されるように配置されうる。
【００７８】
本明細書に記載のプロセスおよび論理フローは、入力データに対して演算を行い、出力を生成することによって動作を行う1つまたは複数のコンピュータプログラムを1つまたは複数のプログラム可能なプロセッサが実行することによって行われる場合もある。また、プロセスおよび論理フローは、専用の論理回路、例えば、FPGA(フィールドプログラマブルゲートアレイ)またはASIC(特定用途向け集積回路)によって実行される可能性があり、さらに、装置は、それらの専用の論理回路として実装される場合もある。
【００７９】
コンピュータプログラムの実行に適したプロセッサは、例として、汎用マイクロプロセッサおよび専用マイクロプロセッサの両方、ならびに任意の種類のデジタルコンピュータの任意の1つまたは複数のプロセッサを含む。概して、プロセッサは、読出し専用メモリ、またはランダムアクセスメモリ、またはそれらの両方から命令およびデータを受け取る。コンピュータの必須の要素は、命令に従って動作を実行するためのプロセッサ、ならびに命令およびデータを記憶するための1つまたは複数のメモリデバイスである。また、概してコンピュータは、データを記憶するための1つまたは複数の大容量ストレージデバイス、例えば、磁気ディスク、光磁気ディスク、もしくは光ディスクを含むか、またはそれらの大容量ストレージデバイスからデータを受信するか、もしくはそれらの大容量ストレージデバイスにデータを転送するか、もしくはその両方を行うためにそれらの大容量ストレージデバイスに動作可能に結合される。しかし、コンピュータは、そのようなデバイスを備えていなくてもよい。さらに、コンピュータは、別のデバイス、例えば、ほんのいくつか例を挙げるとすれば、携帯電話、携帯情報端末(PDA)、モバイルオーディオもしくはビデオプレーヤ、ゲームコンソール、全地球測位システム(GPS)受信機、またはポータブルストレージデバイス(例えば、ユニバーサルシリアルバス(USB)フラッシュドライブ)に組み込まれる場合もある。コンピュータプログラム命令およびデータを記憶するのに適したデバイスは、例として、半導体メモリデバイス、例えば、EPROM、EEPROM、およびフラッシュメモリデバイス、磁気ディスク、例えば、内蔵ハードディスクまたはリムーバブルディスク、光磁気ディスク、ならびにCD-ROMディスクおよびDVD-ROMディスクを含む、すべての形式の不揮発性メモリ、媒体、およびメモリデバイスを含む。プロセッサおよびメモリは、専用の論理回路によって補完されるか、または専用の論理回路に組み込まれる場合もある。
【００８０】
ユーザとのインタラクションを行うために、本明細書に記載の主題の実施形態は、ユーザに対して情報を表示するためのディスプレイデバイス、例えば、CRT(ブラウン管)またはLCD(液晶ディスプレイ)モニタ、ならびに、それによってユーザがコンピュータに入力を与えることができるキーボードおよびポインティングデバイス、例えば、マウスまたはトラックボールを有するコンピュータ上に実装されうる。その他の種類のデバイスが、ユーザとのインタラクションを行うためにやはり使用される可能性があり、例えば、ユーザに提供されるフィードバックは、任意の形式の感覚フィードバック、例えば、視覚的フィードバック、聴覚的フィードバック、または触覚的フィードバックである可能性があり、ユーザからの入力は、音響、発話、または触覚による入力を含む任意の形式で受け取られる可能性がある。加えて、コンピュータは、ユーザによって使用されるデバイスに文書を送信し、そのデバイスから文書を受信することによって、例えば、ウェブブラウザから受信された要求に応答してユーザのクライアントデバイスのウェブブラウザにウェブページを送信することによってユーザとインタラクションすることができる。
【００８１】
本明細書に記載の主題の実施形態は、バックエンドコンポーネントを、例えば、データサーバとして含むか、またはミドルウェアコンポーネント、例えば、アプリケーションサーバを含むか、またはフロントエンドコンポーネント、例えば、それによってユーザが本明細書に記載の主題の実装形態とインタラクションすることができるグラフィカルユーザインターフェースもしくはウェブブラウザを有するクライアントコンピュータを含むか、または1つもしくは複数のそのようなバックエンドコンポーネント、ミドルウェアコンポーネント、もしくはフロントエンドコンポーネントの任意の組合せを含むコンピューティングシステムで実装されうる。システムのコンポーネントは、任意の形式または媒体のデジタルデータ通信、例えば、通信ネットワークによって相互に接続されうる。通信ネットワークの例には、ローカルエリアネットワーク(「LAN」)および広域ネットワーク(「WAN」)、インターネットワーク(例えば、インターネット)、ならびにピアツーピアネットワーク(例えば、アドホックピアツーピアネットワーク)が挙げられる。
【００８２】
コンピューティングシステムは、クライアントおよびサーバを含みうる。クライアントおよびサーバは、典型的には、互いに離れており、通常は通信ネットワークを介してインタラクションする。クライアントとサーバとの関係は、それぞれのコンピュータ上で実行されており、互いにクライアント／サーバの関係を有するコンピュータプログラムによって生じる。一部の実施形態において、サーバは、(例えば、クライアントデバイスとインタラクションするユーザに対してデータを表示し、そのようなユーザからユーザ入力を受信するために)クライアントデバイスにデータ(例えば、HTMLページ)を送信する。クライアントデバイスで生成されたデータ(例えば、ユーザのインタラクションの結果)が、サーバにおいてクライアントデバイスから受信される可能性がある。
【００８３】
本明細書は多くの具体的な実装形態の詳細を含むが、これらは、いかなる発明の範囲または特許請求されうるものの範囲に対する限定とも見なされるべきではなく、むしろ、特定の発明の特定の実施形態に固有の特徴の説明と見なされるべきである。別個の実施形態に関連して本明細書に記載されている特定の特徴が、単一の実施形態で組み合わせて実装される可能性もある。反対に、単一の実施形態に関連して説明されているさまざまな特徴が、複数の実施形態に別々に、または任意の適切な部分的組合せで実装される可能性もある。さらに、特徴は、特定の組合せで動作するように上で説明されている可能性があり、最初にそのように主張されてさえいる可能性があるが、主張された組合せの1つまたは複数の特徴は、場合によってはその組合せから削除される可能性があり、主張された組合せは、部分的組合せ、または部分的組合せの変形形態を対象とする可能性がある。
【００８４】
同様に、動作が図中に特定の順序で示されているが、これは、そのような動作が、示された特定の順序で、もしくは逐次的順序で実行されること、または所望の結果を達成するために、示されたすべての動作が実行されることを必要とすると理解されるべきでない。特定の状況においては、マルチタスクおよび並列処理が、有利である可能性がある。さらに、上述の実施形態におけるさまざまなシステムコンポーネントの分割は、すべての実施形態においてそのような分割を必要とすると理解されるべきでなく、説明されたプログラムコンポーネントおよびシステムは、概して、単一のソフトウェア製品に一緒に統合されるか、または複数のソフトウェア製品にパッケージングされる可能性があると理解されるべきである。
【００８５】
このように、主題の特定の実施形態が説明された。その他の実施形態は、添付の特許請求の範囲内にある。場合によっては、特許請求の範囲に挙げられた動作は、異なる順序で実行され、それでも所望の結果を達成することができる。加えて、添付の図面に示されたプロセスは、所望の結果を達成するために、必ずしも、示された特定の順序、または逐次的順序である必要はない。特定の実装形態においては、マルチタスクおよび並列処理が有利である可能性がある。
【符号の説明】
【００８６】
100  クエリ提案システム
102  コンピュータネットワーク
104  パブリッシャー
105  リソース
106  クライアントデバイス
110  検索システム
111  検索結果
112  リソース索引
114  クエリログ
116  クリックログ
118  検索エンジン
127  提案アグリゲータ
128  提案サーバ
129  個別提案要求/応答インターフェース
130  ブラウザ
131  よくある/関連する提案の要求
132  集約された提案
134  先読みを用いた提案の要求
135  集約された提案
136  予めキャッシュされる提案を伴う検索ページ
140  JavaScript（登録商標）コード
142  ローカルストレージ
144  追加的な予めキャッシュされる提案を伴う検索結果
146  前のクエリに基づく追加的な提案を伴うHTML検索結果ページ
【図１】
2013535729.tif 000003
【図２】
2013535729.tif 000004
【図３】
2013535729.tif 000005
【図４】
2013535729.tif 000006
【図５】
2013535729.tif 000007
【国際調査報告】
2013535729.tif 000008
2013535729.tif 000009