(57)【要約】  クライアントコンピュータのメモリに格納されたグラフィカルユーザインターフェースを提供する。このインターフェースは、ユーザからの垂直検索照会のためのプロンプトフィールドを含む。このインターフェースは、さらに、複数の名前を表示するフィールドを含む。各そのような名前は、垂直集合を表す。複数の名前は、ユーザがまだプロンプトフィールド内に文字を入力しつつある時に、プロンプトフィールド内の1つ以上の文字列の関数として自動的に投入される。垂直検索照会を受け取る命令と、リモートコンピュータに照会を通信する命令と、リモートコンピュータから複数の名前を受信する命令とを格納するメモリを含むコンピュータ。各名前は、垂直検索照会への関連を有する垂直集合を表す。複数の名前は、ユーザがまだ垂直検索照会に追加文字を入力しつつある時に表示される。【選択図】図１
2009533767.tif 000002
【特許請求の範囲】
【請求項１】
クライアントコンピュータのメモリに格納されたグラフィカルユーザインターフェースであって、
ユーザから垂直検索照会を入手するプロンプトフィールド；及び
複数の名前を表示するディスプレイフィールドであって、前記複数の名前内の各名前が、複数の垂直集合内の垂直集合を表す、前記ディスプレイフィールド；
を含み、前記ディスプレイフィールド内の前記複数の名前が、前記ユーザがまだ前記プロンプトフィールド内に追加文字をタイプしつつある時に、前記垂直検索照会の関数として自動的に投入される、前記グラフィカルユーザインターフェース。
【請求項２】
前記ディスプレイフィールド内の前記複数の名前内の各個別の名前が、前記個別の名前によって表される前記垂直集合の関連の関数である寸法を有するグラフィックとして表示される、請求項1記載のグラフィカルユーザインターフェース。
【請求項３】
前記ディスプレイフィールド内の第1グラフィックが、前記ディスプレイフィールド内の第2グラフィックによって表される前記複数の垂直集合内の第2垂直集合より前記垂直検索照会に関連する前記複数の垂直集合内の第1垂直集合を表すときに、前記第1グラフィックが前記第2グラフィックより大きい寸法を有する、請求項2記載のグラフィカルユーザインターフェース。
【請求項４】
前記ディスプレイフィールド内の前記複数の名前内の各名前が、視覚的しるしを有するグラフィックとして表示され、前記ディスプレイフィールド内に表示される個別のグラフィックの前記視覚的しるしが、前記個別のグラフィックによって表される前記垂直集合の関連に基づく垂直検索照会によって決定される、請求項1〜3のいずれか一項記載のグラフィカルユーザインターフェース。
【請求項５】
前記視覚的しるしが、寸法又は色である、請求項4記載のグラフィカルユーザインターフェース。
【請求項６】
前記複数の垂直集合内の各垂直集合がリモートサーバ上に配置され、かつ特定のカテゴリに関連する文書を含む、請求項1〜5のいずれか一項記載のグラフィカルユーザインターフェース。
【請求項７】
前記グラフィカルユーザインターフェースが、ネットワークアクセス可能ブラウザ内のアプリケーションとして実行される、請求項1〜6のいずれか一項記載のグラフィカルユーザインターフェース。
【請求項８】
1つ以上の文字が前記ユーザによって入力された後に前記プロンプトフィールドの内容をリモートサーバに通信することと、前記プロンプトフィールドの前記内容の関数として前記ディスプレイフィールド内に表示するために前記リモートサーバから新しい複数の名前を受信することとによって、前記ディスプレイフィールド内の前記複数の名前が、1つ以上の文字が前記プロンプトフィールド内に前記ユーザによって入力されるたびに再投入される、請求項1〜7のいずれか一項記載のグラフィカルユーザインターフェース。
【請求項９】
前記プロンプトフィールドの前記内容が、各文字がユーザによって前記プロンプトフィールドにタイプされた後にリモートサーバに送信される、請求項8記載のグラフィカルユーザインターフェース。
【請求項１０】
前記プロンプトフィールドの前記内容が、列の終りの信号が検出された時にリモートサーバに送信される、請求項8記載のグラフィカルユーザインターフェース。
【請求項１１】
前記垂直検索照会が、単一の文字を含む、請求項1〜10のいずれか一項記載のグラフィカルユーザインターフェース。
【請求項１２】
前記垂直検索照会が複数の用語を含み、かつ前記複数の用語内の用語が、任意選択で1つ以上の述部条件によって互いから分離される、請求項1〜10のいずれか一項記載のグラフィカルユーザインターフェース。
【請求項１３】
クライアントコンピュータシステムと共に使用されるコンピュータプログラム製品であって、前記コンピュータプログラム製品が、コンピュータ可読記憶媒体及びそこに内蔵されるコンピュータプログラム機構を含み、前記コンピュータプログラム機構が：
前記クライアントコンピュータシステムのユーザから垂直検索照会を受け取る命令；
リモートコンピュータに前記垂直検索照会を通信する命令；
前記リモートコンピュータから複数の名前を受信する命令であって、前記複数の名前内の各名前が、複数の垂直集合内の垂直集合を表し、前記複数の垂直集合内の各垂直集合が、前記垂直検索照会への関連を有する、前記命令；及び
前記ユーザがまだ前記垂直検索照会に追加文字を入力しつつある時に前記複数の名前を表示する命令；
を含む、前記コンピュータプログラム製品。
【請求項１４】
前記複数の名前内の各個別の名前が、前記個別の名前によって表される前記垂直集合の関連に基づく垂直検索照会の関数である寸法を有するグラフィックとして表示される、請求項13記載のコンピュータプログラム製品。
【請求項１５】
表示される第1グラフィックが、表示される第2グラフィックによって表される前記複数の垂直集合内の第2垂直集合より前記垂直検索照会に関連する前記複数の垂直集合内の第1垂直集合を表すときに、前記第1グラフィックが前記第2グラフィックより大きい寸法を有する、請求項14記載のコンピュータプログラム製品。
【請求項１６】
前記複数の名前内の各名前が、視覚的しるしを有するグラフィックとして表示され、個別のグラフィックの前記視覚的しるしが、前記個別のグラフィックによって表される前記垂直集合の関連に基づく垂直検索照会によって決定される、請求項13〜15のいずれか一項記載のコンピュータプログラム製品。
【請求項１７】
前記視覚的しるしが、寸法又は色である、請求項16記載のコンピュータプログラム製品。
【請求項１８】
受け取る前記命令が、前記複数の名前内の各名前の垂直検索照会関連スコアを受け取る命令をさらに含み、かつ、
表示する前記命令が、前記名前の前記関連スコアの関数として前記複数の名前内の各名前を表示する命令をさらに含む、
請求項13〜17のいずれか一項記載のコンピュータプログラム製品。
【請求項１９】
前記複数の垂直集合内の各垂直集合が、前記リモートコンピュータ上に配置され、かつ特定のカテゴリに関連する文書を含む、請求項13〜18のいずれか一項記載のコンピュータプログラム製品。
【請求項２０】
前記垂直検索照会を通信する前記命令が、1つ以上の文字が前記ユーザによって前記垂直検索照会に入力されるたびに繰り返され、及び
複数の名前が、通信する前記命令が繰り返される時のすべて又は一部に、複数の名前を受信する前記命令によって前記リモートコンピュータから受信され、及び
表示する前記命令が、複数の名前が複数の名前を受信する前記命令によって受信されるたびに繰り返され、各複数の名前が、通信する前記命令によって通信される対応する垂直検索照会への関連を有する垂直集合を表す、
請求項13〜19のいずれか一項記載のコンピュータプログラム製品。
【請求項２１】
垂直検索照会を通信する前記命令が、単一の文字が前記ユーザによって前記垂直検索照会に入力されるたびに繰り返される、請求項20記載のコンピュータプログラム製品。
【請求項２２】
前記垂直検索照会を通信する前記命令が、列の終りの信号が検出されるたびに繰り返される、請求項20記載のコンピュータプログラム製品。
【請求項２３】
前記垂直検索照会が、単一の文字を含む、請求項13〜22のいずれか一項記載のコンピュータプログラム製品。
【請求項２４】
前記垂直検索照会が、複数の用語を含み、前記複数の用語内の用語が、任意選択で1つ以上の述部条件によって互いから分離される、請求項13〜22のいずれか一項記載のコンピュータプログラム製品。
【請求項２５】
中央処理装置と、
前記中央処理装置に結合されたメモリとを含むコンピュータであって、該メモリが：
前記コンピュータのユーザから垂直検索照会を受け取る命令；
リモートコンピュータに前記垂直検索照会を通信する命令；
前記リモートコンピュータから複数の名前を受信する命令であって、前記複数の名前内の各名前が、複数の垂直集合内の垂直集合を表し、かつ前記複数の垂直集合内の各垂直集合が、前記垂直検索照会への関連を有する、前記命令；及び
前記ユーザがまだ前記垂直検索照会に追加文字を入力しつつある時に前記複数の名前を表示する命令；
を格納している、前記コンピュータ。
【請求項２６】
複数の名前であって、前記複数の名前内の各名前が、複数の垂直集合内の垂直集合を表し、かつ前記複数の垂直集合内の各垂直集合が、垂直検索照会への関連を有する、前記複数の名前；及び
複数のスコアであって、前記複数のスコア内の各スコアが、前記複数の名前内の名前に対応し、かつ各スコアが、前記垂直検索照会への前記複数の垂直集合内の垂直集合の関連を表す、前記複数のスコア；
を含む、搬送波上で実施されるディジタル信号。
【請求項２７】
前記垂直検索照会が、単一の文字を含む、請求項26記載のディジタル信号。
【請求項２８】
前記垂直検索照会が、複数の用語を含み、前記複数の用語内の用語が、任意選択で1つ以上の述部条件によって互いから分離される、請求項26記載のディジタル信号。
【請求項２９】
サーバコンピュータシステムと共に使用されるコンピュータプログラム製品であって、前記コンピュータプログラム製品が、コンピュータ可読記憶媒体及びそこに内蔵されるコンピュータプログラム機構を含み、前記コンピュータプログラム機構が：
リモートクライアントコンピュータシステムから垂直検索照会を受け取る命令；
垂直インデックス内で前記垂直検索照会に関係付けられる複数の候補垂直集合を識別する命令であって、前記複数の候補垂直集合内の個別の候補垂直集合ごとに、前記個別の候補垂直集合に関連付けられた垂直検索照会関連スコアがある、前記命令；
前記複数の候補垂直集合内の各候補垂直集合の名前を、前記複数の候補垂直集合内の各候補垂直集合の前記垂直検索照会関連スコアと一緒に前記リモートクライアントコンピュータシステムに通信する命令；
を含む、前記コンピュータプログラム製品。
【請求項３０】
前記複数の候補垂直集合内の各候補垂直集合が、特定のカテゴリに関連する文書を含む、請求項29記載のコンピュータプログラム製品。
【請求項３１】
前記垂直検索照会が、単一の文字を含む、請求項29又は30記載のコンピュータプログラム製品。
【請求項３２】
前記垂直検索照会が、複数の原子的垂直検索照会を含み、前記複数の原子的垂直検索照会内の用語が、任意選択で1つ以上の述部条件によって互いから分離され、かつ識別する前記命令が：
前記垂直検索照会を前記複数の原子的垂直検索照会に分解すること；
前記複数の原子的垂直検索照会内の個別の原子的垂直検索照会ごとに、前記個別の原子的垂直検索照会に関連する複数の垂直集合を判定すること；及び、
前記複数の原子的垂直検索照会内の個別の原子的垂直検索照会に関連する各複数の垂直集合を前記複数の候補垂直集合に組み合わせること；
をさらに含む、請求項29又は30記載のコンピュータプログラム製品。
【請求項３３】
各前記複数の原子的垂直検索照会内にある垂直集合だけが、前記複数の候補垂直集合に含まれる、請求項32記載のコンピュータプログラム製品。
【請求項３４】
原子的垂直検索照会に関連する所与の複数の垂直集合内の、前記原子的垂直検索照会に関する高い関連性スコアscore(t,v)を有する垂直集合だけが、前記複数の候補垂直集合に含まれる、請求項32記載のコンピュータプログラム製品。
【請求項３５】
前記所与の複数の垂直集合内の垂直集合の、前記原子的垂直検索照会に対する相対的な前記関連性スコアscore(t,v)が、式
【数１】
2009533767.tif 000015
によって判定され、式中、score(t,d)が、前記垂直集合内の文書に関するスコアであり、かつw(d,v)が、前記垂直集合に割り当てられた重みである、請求項34記載のコンピュータプログラム製品。
【請求項３６】
w(d,v)が、前記垂直集合が前記原子的垂直検索照会の高い出現率を有する文書を含む時に前記垂直集合をアップウェイトする重みである、請求項35記載のコンピュータプログラム製品。
【請求項３７】
w(d,v)が、前記垂直集合が前記垂直集合内で最高ランキングの文書内の前記原子的垂直検索照会の高い優勢を有する時に前記垂直集合をアップウェイトする重みである、請求項35記載のコンピュータプログラム製品。
【請求項３８】
w(d,v)が、1である、請求項35記載のコンピュータプログラム製品。
【請求項３９】
w(d,v)が、前記垂直集合の人気又は前記垂直集合内の文書のリンク密度の集計の関数である、請求項35記載のコンピュータプログラム製品。
【請求項４０】
【数２】
2009533767.tif 000016
であり、式中、
f(d,t)は、前記原子的垂直検索が前記垂直集合の文書(d)内に現れる回数であり、
f(N)が、前記サーバコンピュータシステムによって追跡される垂直集合の個数の関数であり、
v(t)が、前記所与の複数の垂直集合内の垂直集合の個数であり、
A及びBが定数である、
請求項35記載のコンピュータプログラム製品。
【請求項４１】
f(N)が、Mvすなわち前記サーバコンピュータシステムによって追跡される垂直集合の前記個数、log(Mv)、又はMvである、請求項40記載のコンピュータプログラム製品。
【請求項４２】
score(t,d)=f(d,t)
であり、式中、
f(d,t)は、前記原子的垂直検索が前記垂直集合の文書(d)に現れる回数である、
請求項35記載のコンピュータプログラム製品。
【請求項４３】
前記所与の複数の垂直集合内の垂直集合の、前記原子的垂直検索照会に対する相対的な前記関連性スコアscore(t,v)が、式
【数３】
2009533767.tif 000017
によって判定され、式中、
f(d,t)は、前記原子的垂直検索が前記垂直集合の文書(d)内に現れる回数であり、
f(N)が、前記サーバコンピュータシステムによって追跡される垂直集合の個数の関数であり、
v(t)が、前記所与の複数の垂直集合内の垂直集合の個数であり、
A及びBが、定数であり、かつ、
w(d,v)が、重みである、
請求項34記載のコンピュータプログラム製品。
【請求項４４】
前記所与の複数の垂直集合内の垂直集合の、前記原子的垂直検索照会に対する相対的な前記関連性スコアscore(t,v)が、式
μ1*score1(t,v)+ μ2*score2(t,v)
によって判定され、式中、
score1(t,v)=(C+log(f(v,t)))*log(D+f(N)/v(t))
かつ
【数４】
2009533767.tif 000018
であり、式中、
f(d,t)が、前記原子的垂直検索が前記垂直集合の文書(d)内に現れる回数であり、
f(N)が、前記サーバコンピュータシステムによって追跡される垂直集合の個数の関数であり、
v(t)が、前記所与の複数の垂直集合内の垂直集合の個数であり、
A、B、C、D、μ1、及びμ2が、定数であり、かつ、
w(d,v)が、重みである
請求項34記載のコンピュータプログラム製品。
【請求項４５】
中央処理装置と、
前記中央処理装置に結合されたメモリとを含むコンピュータであって、該メモリが：
リモートクライアントコンピュータシステムから垂直検索照会を受け取る命令；
垂直インデックス内で前記垂直検索照会に関係付けられる複数の候補垂直集合を識別する命令であって、前記複数の候補垂直集合内の個別の候補垂直集合ごとに、前記個別の候補垂直集合に関連付けられた垂直検索照会関連スコアがある、前記命令；
前記複数の候補垂直集合内の各候補垂直集合の名前を、前記複数の候補垂直集合内の各候補垂直集合の前記垂直検索照会関連スコアと一緒に前記リモートクライアントコンピュータシステムに通信する命令；
を格納している、前記コンピュータ。
【請求項４６】
サーバコンピュータシステムと共に使用されるコンピュータプログラム製品であって、前記コンピュータプログラム製品が、コンピュータ可読記憶媒体及びそこに内蔵されるコンピュータプログラム機構を含み、前記コンピュータプログラム機構が、
複数の垂直インデックスリストを含む垂直インデックスであって、前記複数の垂直インデックスリスト内の垂直インデックスリストが、ヘッド用語及び複数の垂直集合識別子を含み、前記複数の垂直集合識別子内の垂直集合識別子によって参照される各垂直集合が、前記ヘッド用語を含む文書を含む、前記垂直インデックス
を含む、前記コンピュータプログラム製品。
【請求項４７】
前記複数の垂直インデックスリスト内の垂直インデックスリストが、前記複数の垂直集合識別子内の垂直集合識別子によって参照される複数の垂直集合内の垂直集合ごとに、ヘッド用語固有関連性スコアscore(t,v)をさらに含む、請求項46記載のコンピュータプログラム製品。
【請求項４８】
前記所与の複数の垂直集合内の垂直集合の前記関連性スコアscore(t,v)が、式
【数５】
2009533767.tif 000019
によって判定され、式中、score(t,d)が、前記垂直集合内の文書のスコアであり、かつw(d,v)が、前記垂直集合に割り当てられた重みである、請求項47記載のコンピュータプログラム製品。
【請求項４９】
w(d,v)が、前記垂直集合が前記ヘッド用語の高い出現率を有する文書を含む時に前記垂直集合をアップウェイトする重みである、請求項48記載のコンピュータプログラム製品。
【請求項５０】
w(d,v)が、前記垂直集合が前記垂直集合内で最高ランキングの文書内の前記ヘッド用語の高い優勢を有する時に前記垂直集合をアップウェイトする重みである、請求項48記載のコンピュータプログラム製品。
【請求項５１】
w(d,v)が、1である、請求項48記載のコンピュータプログラム製品。
【請求項５２】
w(d,v)が、前記垂直集合の人気又は前記垂直集合内の文書のリンク密度の集計の関数である、請求項48記載のコンピュータプログラム製品。
【請求項５３】
【数６】
2009533767.tif 000020
であり、式中、
f(d,t)は、前記原子的垂直検索が前記垂直集合の文書(d)内に現れる回数であり、
f(N)が、前記サーバコンピュータシステムによって追跡される垂直集合の個数の関数であり、
v(t)が、前記垂直インデックスリストによって参照される垂直集合の個数であり、かつ、
A及びBが定数である、
請求項47記載のコンピュータプログラム製品。
【請求項５４】
f(N)が、Mvすなわち前記サーバコンピュータシステムによって追跡される垂直集合の前記個数、log(Mv)、又はMvである、請求項53記載のコンピュータプログラム製品。
【請求項５５】
score(t,d)=f(d,t)
であり、式中、f(d,t)は、前記ヘッド用語が前記垂直集合の文書(d)に現れる回数である、
請求項48記載のコンピュータプログラム製品。
【請求項５６】
前記複数の垂直集合内の垂直集合の前記関連性スコアscore(t,v)が、式
【数７】
2009533767.tif 000021
によって判定され、式中、
f(d,t)は、前記ヘッド用語が前記垂直集合の文書(d)内に現れる回数であり、
f(N)が、前記サーバコンピュータシステムによって追跡されるいくつかの垂直集合であり、
v(t)が、前記垂直インデックス内の垂直集合の個数であり、
A及びBが、定数であり、かつ、
w(d,v)が、重みである
請求項47記載のコンピュータプログラム製品。
【請求項５７】
前記複数の垂直集合内の垂直集合の前記関連性スコアscore(t,v)が、式
μ1*score1(t,v)+ μ2*score2(t,v)
によって判定され、式中、
score1(t,v)=(C+log(f(v,t)))*log(D+f(N)/v(t))
かつ
【数８】
2009533767.tif 000022
であり、式中、
f(d,t)が、前記ヘッド用語が前記垂直集合の文書(d)内に現れる回数であり、
f(N)が、前記サーバコンピュータシステムによって追跡されるいくつかの垂直集合であり、
v(t)が、前記垂直インデックスリスト内の垂直集合の個数であり、
A、B、C、D、μ1、及びμ2が、定数であり、かつ、
w(d,v)が、重みである、
請求項47記載のコンピュータプログラム製品。
【請求項５８】
中央処理装置と、
前記中央処理装置に結合されたメモリとを含むコンピュータであって、該メモリは：
複数の垂直インデックスリストを含む垂直インデックスであって、前記複数の垂直インデックスリスト内の垂直インデックスリストが、ヘッド用語及び複数の垂直集合識別子を含み、前記複数の垂直集合識別子内の垂直集合識別子によって参照される各垂直集合が、前記ヘッド用語を含む文書を含む、前記垂直インデックス；
リモートクライアントコンピュータシステムから垂直検索照会を受け取る命令；
前記垂直インデックス内で前記垂直検索照会に関係付けられる複数の候補垂直集合を識別する命令であって、前記複数の候補垂直集合内の個別の候補垂直集合ごとに、前記個別の候補垂直集合に関連付けられた垂直検索照会関連スコアがある、前記命令；
前記複数の候補垂直集合内の各候補垂直集合の名前を、前記複数の候補垂直集合内の各候補垂直集合の前記垂直検索照会関連スコアと一緒に前記リモートクライアントコンピュータシステムに通信する命令；
をを含む、前記コンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
(関連出願の相互参照)
本願は、参照によって本明細書にその全体が組み込まれている、2006年4月13日に出願した米国特許出願第11/404,687号、名称「Systems and Methods for Performing Searches within Vertical Domains」の優先権を主張するものである。本願は、参照によって本明細書にその全体が組み込まれている、2006年4月13日に出願した米国特許出願第11/404,620号、名称「Systems and Methods for Ranking Vertical Domains」の優先権をも主張するものである。
(1.発明の分野)
本発明は、全般的には情報の検索及び取出しに関する。より具体的には、垂直ドメイン(vertical domain)を使用してインターネット検索を改善するシステム及び方法を開示する。
【背景技術】
【０００２】
(2.発明の背景)
ウェブは、情報検索に関する新しい課題を創り出す。ウェブ上の情報の量は、急速に増えつつある。新しくより使い易いウェブツールを用いると、より少ないウェブトレーニングを受けたか又は正式のウェブトレーニングを受けていないユーザが、ウェブサイトにアクセスすることができる。Google及びYahoo!などの多数の検索エンジンは、ユーザが情報を検索し、取り出すことを可能にする。これらの従来の検索エンジンは、性質において水平である。これらの検索エンジンは、ウェブ全体をインデクシングする。次に、ユーザの提供する検索照会が、このインデックスに対して検索され、最も関連する結果が返される。しかし、インターネット上で入手可能な膨大な量の情報並びにそのような情報の複雑さのゆえに、そのような水平インデックスから有用な情報を抽出するために、ますます複雑さを増した検索式が必要である。
【０００３】
さらに、単語は、しばしば複数の意味を有するので、検索語は、しばしば、意図されないカテゴリの文書を取り出す。たとえば、単語「tiger」は、アジアの一部にのみ見られる肉食動物を意味する可能性がある。この単語は、ゴルフ界の伝説的人物タイガーウッズのラストネームでもあり、また、Macintoshオペレーティングシステムの名前でもある。したがって、従来の検索エンジンでの検索語としての用語「tiger」の使用は、動物に関係する文書、ゴルフに関係する文書、及びオペレーティングシステムに関係する文書を含むごたまぜの文書を取り出す可能性が高い。そのような検索照会と共に返されるスポンサードリンク及び/又は広告は、同様に散らばったものになる。この問題を示すために、最近にGoogleに入力された検索照会「tiger」に応答して、上位の応答は、コンピュータ周辺機器ストアTigerDirect.comへのリンク、「Save the Tiger Fund」へのリンク、Macintosh OS X tigerオペレーティングシステムへのリンク、「Tiger Haven」(ライオン、虎、及びジャガーの鳥獣保護区)へのリンク、タイガーウッズの公式ウェブサイトへのリンク、並びにeBay.comで「tigers」を検索するための広告を含んだ。したがって、同一の句が、異なる人にとって完全に異なる意味を有するので、検索式の曖昧さは、しばしば回避不能である。これは、情報の検索及び取出しを、よりむずかしくし、大きい問題をユーザに提示する。これは、ユーザによって提供された検索照会に真に関連する、サーバに焦点を合わせた広告に対する無能力のゆえに、ウェブポータルにとっても問題である。
【０００４】
テキストベースの検索式に固有の曖昧さに対処する1つの形は、検索を、それ自体が特定の主題に制限されたデータベースに制限することである。ウェブ検索エンジン(たとえば、dmoz、Yahoo!、looksmartなど)は、そのような主題固有データベースを提供する。たとえば、dmozは、数百万個のサイトを収集しており、これらのサイトは、数千個のカテゴリに分類される。これらのカテゴリは、階層式に編成される。図1に、dmozのトップレベルカテゴリ(たとえば、データベース102)を示す。各カテゴリは、本質的に、1つ以上の特定の主題に制限された文書のデータベースである。検索を、これらの特定のディレクトリのうちの任意の1つに制約することができる。dmozは、検索を特定のカテゴリに制限するが、その階層ユーザインターフェースは不便である。しばしば、かなりの長さの時間及びかなりの量の労力が、階層リスティングから正確に正しいデータベースを探すのに費やされる。ユーザは、しばしば、所望のディレクトリ又はウェブページに達する前に、5つ以上もの多数のレベルをドリルダウンしなければならない。dmozのトップレベルで入力された検索照会は、おびただしい数のデータベース可能性を返す。しかし、このデータベース可能性は、各データベースの全階層情報を含む。そのような階層情報は、一部のユーザに情報を伝えはするが、平均的ユーザにとって、この階層情報は役に立たない。さらに悪いことに、この階層情報は、検索すべき適切な文書のデータベースを識別するという作業を複雑にする。
【０００５】
dmozとは異なって、looksmart及びYahoo!などの検索エンジンは、トピックのカテゴリのフラットな非階層リスティングを提供する。しかし、そのような手法に関する短所は、特定の検索照会を向けるべきカテゴリをユーザが実際に知っていることが前提となっていることである。しかし、ユーザは、しばしば、検索すべきカテゴリが全くわからない。菜園に関する質問は、「食品カテゴリ」又は「家庭生活」カテゴリのどちらで検索すべきか。ゴルフシューズは「スタイル」、「スポーツ」、又は「衣類」のどこで検索すべきか。「金融」カテゴリは、完全に別々の「ミューチュアルファンド」カテゴリがある場合に、ミューチュアルファンドを含むのか。したがって、looksmart及びExite!などのポータルに関する短所は、実際の検索を行う前に、検索すべきカテゴリをポータルに伝える効率的な形がないことである。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上の背景を考えると、当技術分野で必要なものは、インターネット又は他の広域ネットワークを使用して文書を検索する改善されたシステム及び方法である。
【課題を解決するための手段】
【０００７】
(3.発明の要旨)
本発明は、ユーザ入力に応答して垂直提案(vertical suggestion)を提供する。通常、この入力は、キーボード又は他のデータ入力デバイスによるものである。ユーザは、データ入力デバイスで文字及び/又は単語を入力し、システムは、これらの文字及び/又は単語を候補垂直集合(vertical collection)に関する1つ以上の照会に変換する。システムは、候補垂直集合を評価し、関連する候補垂直集合の名前のリストを返す。次に、ユーザは、提案された候補垂直集合のうちの1つを選択することによって対話を継続することができる。次に、システムは、選択された垂直集合を検索し、ユーザ入力に関連する、選択された垂直集合からの文書のリストを返す。
本発明の一態様は、クライアントコンピュータのメモリに格納されたグラフィカルユーザインターフェースを提供する。このグラフィカルユーザインターフェースは、ユーザから垂直検索照会を入手するプロンプトフィールドと、複数の名前を表示するディスプレイフィールドとを含む。複数の名前内の各名前は、複数の垂直集合内の垂直集合を表す。ディスプレイフィールド内の複数の名前は、ユーザがまだプロンプトフィールド内に追加文字を入力しつつある時に、プロンプトフィールドにユーザによって入力された1つ以上の用語の関数として自動的に投入される。
【０００８】
いくつかの実施態様で、ディスプレイフィールド内の複数の名前内の各個別の名前は、個別の名前によって表される垂直集合の関連に基づく垂直検索照会の関数である寸法を有するグラフィックとして表示される。たとえば、いくつかの実施態様で、ディスプレイフィールド内の第1グラフィックが、ディスプレイフィールド内の第2グラフィックによって表される複数の垂直集合内の第2垂直集合よりも垂直検索照会に関連する複数の垂直集合内の第1垂直集合を表すときに、第1グラフィックは、第2グラフィックより大きい寸法を有する。
いくつかの実施態様で、ディスプレイフィールド内の複数の名前内の各名前は、視覚的しるしを有するグラフィックとして表示される。ディスプレイフィールド内に表示される個別のグラフィックの視覚的しるしは、個別のグラフィックによって表される垂直集合の関連によって決定される。いくつかの実施態様で、視覚的しるしは、寸法又は色である。
【０００９】
いくつかの実施態様で、複数の垂直集合内の各垂直集合は、リモートサーバ上に配置され、かつ特定のカテゴリに関連する文書を含む。いくつかの場合に、グラフィカルユーザインターフェースは、ネットワークアクセス可能ブラウザ内のアプリケーションとして実行される。いくつかの実施態様で、ディスプレイフィールド内の複数の名前は、1つ以上の文字がユーザによって入力された後にプロンプトフィールドの内容をリモートサーバに通信することによって、1つ以上の文字がプロンプトフィールド内にユーザによって入力されるたびに再投入される。そのような実施態様では、新しい複数の名前が、リモートサーバに通信されたプロンプトフィールドの内容の関数としてディスプレイフィールド内に表示されるためにリモートサーバから受信される。いくつかの実施態様で、プロンプトフィールドの内容は、各文字がユーザによってプロンプトフィールドにタイプされた後にリモートサーバに送信される。いくつかの実施態様で、プロンプトフィールドの内容は、列の終りの信号が検出された時にリモートサーバに送信される。いくつかの実施態様で、垂直検索照会は、単一の文字を含む。いくつかの実施態様で、垂直検索照会は、1つ以上の述部条件(たとえば、AND、OR、NOT)によって互いから分離された複数の用語を含む。
【００１０】
本発明のもう1つの態様は、クライアントコンピュータシステムと共に使用されるコンピュータプログラム製品を提供する。このコンピュータプログラム製品は、コンピュータ可読記憶媒体及びそこに内蔵されるコンピュータプログラム機構を含む。コンピュータプログラム機構は、クライアントコンピュータシステムのユーザから垂直検索照会を受け取る命令と、リモートコンピュータに垂直検索照会を通信する命令と、リモートコンピュータから複数の名前を受信する命令とを含む。複数の名前内の各名前は、複数の垂直集合内の垂直集合を表す。複数の垂直集合内の各垂直集合は、垂直検索照会への関連を有する。このコンピュータプログラム製品は、ユーザがまだ垂直検索照会に追加文字を入力しつつある時に複数の名前を表示する命令をさらに含む。
いくつかの実施態様で、複数の名前内の各個別の名前は、個別の名前によって表される垂直集合の関連の関数である寸法を有するグラフィックとして表示される。一例で、表示される第1グラフィックが、第2グラフィックによって表される第2垂直集合より垂直検索照会に関連する複数の垂直集合内の第1垂直集合を表すときに、第1グラフィックは、第2グラフィックより大きい寸法を有する。いくつかの実施態様で、複数の名前内の各名前は、視覚的しるしを有するグラフィックとして表示され、かつ個別のグラフィックの視覚的しるしは、個別のグラフィックによって表される垂直集合の関連に基づく垂直検索照会によって決定される。いくつかの実施態様で、視覚的しるしは、寸法又は色である。
【００１１】
本発明のもう1つの実施態様は、中央処理装置と、中央処理装置に結合されたメモリとを含むコンピュータを提供する。メモリは、コンピュータのユーザから垂直検索照会を受け取る命令と、リモートコンピュータに垂直検索照会を通信する命令と、リモートコンピュータから複数の名前を受信する命令とを格納する。複数の名前内の各名前は、複数の垂直集合内の垂直集合を表す。各垂直集合は、垂直検索照会への関連を有する。メモリは、さらに、ユーザがまだ垂直検索照会に追加文字を入力しつつある時に複数の名前を表示する命令を格納する。
本発明のもう1つの実施態様は、複数の名前を含む搬送波上で実施されるディジタル信号を含む。複数の名前内の各名前は、複数の垂直集合内の垂直集合を表す。複数の垂直集合内の各垂直集合は、垂直検索照会への関連を有する。搬送波上で実施されるディジタル信号は、複数のスコアをさらに含む。複数のスコア内の各スコアは、複数の名前内の名前に対応する。各スコアは、垂直検索照会への複数の垂直集合内の垂直集合の関連を表す。いくつかの実施態様で、垂直検索照会は、単一の文字を含む。いくつかの実施態様で、垂直検索照会は、複数の用語を含み、該複数の用語内の用語は、任意選択で1つ以上の述部条件によって互いから分離される。
【発明を実施するための最良の形態】
【００１２】
(5.詳細な説明)
本発明は、既知の検索エンジンとは異なる。本発明では、インターネット全体を表すインデックスを使用するのではなく、垂直集合が使用される。「垂直集合」は、共通のカテゴリに関係する文書(たとえば、URL、ウェブサイトなど)のセットを含む。たとえば、帆船に関するウェブページは、「帆船」垂直集合を構成することができる。自動車レースに関するウェブページは、「自動車レース」集合を構成することができる。ユーザは、垂直集合を検索し、その結果、その垂直集合によって表されるカテゴリに関連する文書だけがユーザに返されるようになる。有利なことに、本発明は、検索する人が検索すべき正しい垂直集合を識別するのを助けるシステム及び方法を提供する。
図2に示されているように、垂直検索照会が、クライアントコンピュータ100によって垂直エンジンサーバ110にサブミットされる。この垂直検索照会を受け取った時に、垂直エンジンサーバ110は、その検索照会に関連する、垂直集合インデックス442内の垂直集合を識別する。次に、候補垂直集合の名前が、クライアントコンピュータ100に返される。次に、ユーザは、垂直集合のうちの1つを選択し、オリジナル検索式又は新しい検索式を用いる垂直集合の検索に進む。
【００１３】
垂直エンジンサーバ110が、所与の検索照会に関する候補垂直集合のリストをどのように生成するかに関する詳細に移る前に、垂直エンジンサーバ110の実施態様によって返される候補垂直集合のスクリーンショットを図3A〜3Fとして提供して、本発明の利益をよりよく理解できるようにする。図3Aでは、ユーザは、プロンプト302を含むグラフィックを与えられる。特筆すべきことに、図3Aでは、プロンプト302は存在するが、「検索」トグルがない。図3Aには、提案される垂直集合の集合を表示するvクラウド(v-cloud)304も存在する。vクラウド304にリストされる垂直集合のアイデンティティは、完全にプロンプト302の内容の関数である。実際に、本発明のいくつかの実施態様では、プロンプト302の内容がポーリングされ、追加キーストローク又はいくつかの実例で複数のキーストロークがプロンプト302に入力されるどの時にも、プロンプト302の内容が、垂直集合の新しいセットが垂直エンジンサーバ110を使用して取り出される垂直検索照会として扱われるようになっている。次に、vクラウド304に、垂直集合の新しいセットが再投入される。この形で、vクラウド304は、ユーザがプロンプト302に追加文字を追加する時に、最も関連する垂直カテゴリを常に含む。ユーザが、vクラウド304内の垂直集合のうちの1つを選択する時には、対応する垂直集合が、プロンプト302の垂直検索照会を使用して検索される。
本発明の概念を示すために、検索式「tiger」を検討されたい。図3Aに示されているように、ユーザは、まず文字「t」を入力することによって、プロンプト302を使用してこの検索式を作り始める。ユーザが、プロンプト302で文字「i」を入力する前に、垂直エンジンサーバ110は、垂直検索照会「t」に最も関連する垂直集合の垂直集合インデックス120を検索する。次に、垂直エンジンサーバ110は、これらの最も関連する垂直集合のアイデンティティをクライアントコンピュータ100に通信し、クライアントコンピュータ100では、これらのアイデンティティが、vクラウド304に投入するのに使用される。したがって、プロンプト302内の垂直検索照会「t」に応答して、vクラウド304は、「t」が式t-shirt(tシャツ)で顕著なので垂直集合「apparel(衣装)」を含み、「t」が携帯電話会社T-Mobileの名前で顕著なので垂直集合「cellular phone(携帯電話)」を含み、「t」が式「t.v.」などの一部を形成するので垂直集合「television programs(テレビジョン番組)」を含む。
【００１４】
図3Bを参照すると、ユーザがプロンプト302内で「i」をタイプする時に、垂直エンジンサーバ110は、垂直検索照会「ti」に最も関連する垂直集合の垂直集合インデックス120を検索する。次に、垂直エンジンサーバ110は、これらの最も関連する垂直集合のアイデンティティをクライアントコンピュータ100に通信し、クライアントコンピュータ100では、これらのアイデンティティが、vクラウド304に再投入するのに使用される。したがって、図3Bを参照すると、プロンプト302内の垂直検索照会「ti」に応答して、vクラウド304は、「ti」が電卓製造業者Texas Instrumentsを表すので垂直集合「calculators(電卓)」を含むと同時に、「ti」が元素チタニウムの化学記号なので垂直集合「chemistry(化学)」及び「elements(元素)」を含む。図3Cを参照すると、ユーザがプロンプト302内で「g」をタイプする時に、垂直エンジンサーバ110は、垂直検索照会「tig」に最も関連する垂直集合の垂直集合インデックス120を検索する。次に、垂直エンジンサーバ110は、これらの最も関連する垂直集合のアイデンティティをクライアントコンピュータ100に通信し、クライアントコンピュータ100では、これらのアイデンティティが、vクラウド304に再投入するのに使用される。したがって、図3Cを参照すると、プロンプト302内の垂直検索照会「tig」に応答して、vクラウド304は、「tig」がTIG保険会社を表すので垂直集合「insurance(保険)」を含む。vクラウド304は、垂直検索照会「tig」とタングステン不活性ガス(TIG)溶接として既知の溶接の一般的な形との間の類似性のゆえに垂直集合「welding(溶接)」をも含む。
【００１５】
図3Dを参照すると、ユーザがプロンプト302内で「e」をタイプする時に、垂直エンジンサーバ110は、垂直検索照会「tige」に最も関連する垂直集合の垂直集合インデックス120を検索する。次に、垂直エンジンサーバ110は、これらの最も関連する垂直集合のアイデンティティをクライアントコンピュータ100に通信し、クライアントコンピュータ100では、これらのアイデンティティが、vクラウド304に再投入するのに使用される。したがって、図3Dを参照すると、プロンプト302内の垂直検索照会「tige」に応答して、vクラウド304は、類似する俳優Tige Andrewsのゆえに垂直集合「actors(俳優)」を含み、Tigeボート製造業者のゆえに垂直集合「boating(ボートこぎ)」を含み、Brown Shoe Company社に関連するBuster Brown続き漫画に使用されるブルドックキャラクタのゆえに垂直集合「shoes(靴)」を含み、Tige canyon creakが米国Texas(テキサス)州に位置するので垂直集合「Texas」を含む。
図3Eを参照すると、ユーザがプロンプト302内で「r」をタイプすることによって式「tiger」を完成させる時に、垂直エンジンサーバ110は、垂直検索照会「tiger」に最も関連する垂直集合の垂直集合インデックス120を検索する。次に、垂直エンジンサーバ110は、これらの最も関連する垂直集合のアイデンティティをクライアントコンピュータ100に通信し、クライアントコンピュータ100では、これらのアイデンティティが、vクラウド304に再投入するのに使用される。したがって、図3Eを参照すると、プロンプト302内の垂直検索照会「tiger」に応答して、vクラウド304は、中国の占星術の虎の誕生のしるしのゆえに垂直集合「Chinese astrology(中国の占星術)」を含み、最も有名なゴルファであるタイガーウッズのゆえに垂直集合「golf(ゴルフ)」を含み、Tiger Macintoshオペレーティングシステムのゆえに垂直集合「Operating Systems(オペレーティングシステム)」を含み、ウシエビ(tiger shrimp)が海産食物の一形態であるので垂直集合「seafood(海産食物)」を含み、虎はもちろん野生動物なので垂直集合「wild animals(野生動物)」を含む。
【００１６】
したがって、図3Eの参照を続け、ユーザがタイガーウッズに関心をもつ場合を検討されたい。したがって、ユーザは、vクラウド304から垂直カテゴリ「golf」を選択した。この選択に応答して、golf垂直集合の検索が、実行され、その結果が、図3Fに示されている表示のために返される。この図からわかるように、Googleなどの水平検索エンジンの場合とは異なって、golf垂直集合内のTiger垂直検索照会に応答して、返される文書のそれぞれは、ゴルフに関係する。これは、ユーザの観点から有益である。ユーザは、検索すべき適切なカテゴリを識別するためにかなりの努力をおこなう必要が一度もなかった。各キーストロークに伴って、vクラウド304は、検索すべき複数の異なる垂直集合を自動的に提供する。ユーザが行わなければならなかったことは、関連する垂直カテゴリがvクラウド304に現れるまで、1文字ずつタイプし続けることだけである。図3Fに示された本発明のもう1つの利点は、いったんユーザがgolf垂直集合を選択すると、垂直エンジンサーバ110によって提供される広告のそれぞれがゴルフに関連することである。したがって、ユーザは、これらの広告に反応する可能性がはるかにより高い。
【００１７】
本発明のシステム及び方法の概要を開示した。この概要から、本発明の多数の利益及び特徴が明白である。本発明は、ユーザが指示した照会のターゲットとして使用できる候補垂直集合のリストをユーザに自動的に与える。本発明のシステム及び方法を使用することによって、ユーザは、候補垂直集合のリストの中からターゲット垂直集合を選択するのに最小量の努力を必要としながら、検索照会に関連する文書をターゲット垂直集合から検索することができる。したがって、本発明を使用すると、もはや、カテゴリの階層リストを通ってナビゲートする必要も、所与の検索照会に関連する文書についてインターネット全体の広い検索から入手された検索結果を取捨選択する必要もない。
【００１８】
本発明の概要及び本発明の利点を提示したので、本発明のシステム及び方法のより詳細な説明を開示する。このために、図4に、本発明の一実施態様による垂直エンジンサーバ110を示す。いくつかの実施態様で、垂直エンジンサーバ110は、図4に概略的に示された1つ以上のコンピュータシステム400を使用して実施される。大量の垂直検索照会を処理するように設計された垂直エンジンが、図4に示されたものより複雑なコンピュータアーキテクチャを使用できることを、当業者は了解するであろう。たとえば、サーバのフロントエンドセットを使用して、ユーザ照会を実際に処理するバックエンドサーバの組の間で垂直検索照会を受け取り、これらの間でそれらの垂直検索照会を分散させることができる。そのようなシステムでは、図4に示されたシステム400が、1つのそのようなバックエンドサーバになるはずである。
コンピュータシステム400は、通常は、ユーザインターフェース404(ディスプレイ406及びキーボード408を含む)、1つ以上の処理ユニット(CPU)402、ネットワーク又は他の通信インターフェース410、メモリ414、及びこれらのコンポーネントを相互接続する1つ以上の通信バス412を有する。メモリ414は、高速ランダムアクセスメモリを含むことができ、また、1つ以上の磁気ディスクストレージデバイス(図示せず)などの不揮発性メモリを含むこともできる。メモリ414には、中央処理ユニット(1つ以上)402からリモートに配置されるマスストレージを含めることができる。メモリ414は：
さまざまな基本システムサービスを処理し、ハードウェア依存タスクを実行するプロシージャを含むオペレーティングシステム416；
インターネット、他の広域ネットワーク、ローカルエリアネットワーク(たとえば、ローカル無線ネットワークは、クライアントコンピュータ100をコンピュータ400に接続することができる)、メトロポリタンエリアネットワークなどの1つ以上の通信ネットワークを介して、さまざまなクライアントコンピュータ100(図1)及びおそらくは他のサーバ又はコンピュータにシステム400を接続するのに使用されるネットワーク通信モジュール418；
クライアントコンピュータ100から垂直検索照会を受け取る照会ハンドラ420；
垂直検索照会に関係する文書466の選択された垂直集合450を検索し、かつ検索照会に関係するランキングされた文書のグループを形成する、検索エンジン422；
垂直インデックス442を、所与の垂直検索照会に関連する1つ以上の垂直インデックスリスト444から検索する垂直検索エンジン424；
垂直インデックス442を構成する垂直インデックス構成モジュール460；及ビ
文書466のセットから文書インデックス462を構築するインデックス構成モジュール464；を格納することが好ましい。
【００１９】
本発明の方法は、垂直検索照会が、インデックス構成モジュール464と共に照会ハンドラ420によって受け取られる前に始まる。インデックス構成モジュール464は、関連する検索語について文書466をスキャンすることによって文書インデックス462を構成する。文書インデックス462の例示を、下に示す。
【表１】
2009533767.tif 000003
いくつかの実施態様で、文書インデックス462は、従来のインデクシング技法を使用してインデックス構成モジュール464によって構成される。例示的インデクシング技法は、その全体が参照によって本明細書に組み込まれている米国特許出願公告第20060031195号に開示されている。例示のために、いくつかの実施態様で、所与の用語を、その用語が文書内にしきい値回数を超えて現れる時に特定の文書に関連付けることができる。いくつかの実施態様で、所与の用語を、その用語がしきい値スコアを超えるスコアを達成する時に特定の文書に関連付けることができる。候補用語に関して文書をスコアリングするのに使用できる判断基準は、(i)候補用語が文書の上側部分に現れる回数、(ii)文書内の候補用語の正規化された平均位置、(iii)候補用語内の文字数、及び(iv)文書が他の文書によって参照される回数を含むが、これらに限定はされない。高スコアリング文書が、用語に関連付けられる。文書インデックス462が、用語のリスト、用語のリスト内のその用語に関連する各文書を一意に識別する文書識別子、及びこれらの文書のスコアを格納する。当業者は、文書インデックス462を作成するために用語を文書に関連付ける多数の方法があり、そのような方法のすべてを、本発明の文書インデックス462を構成するために使用できることを了解するであろう。
【００２０】
文書インデックス462内に存在し得る用語の個数に制限はない。いくつかの実施態様で、長さが1〜10のASCII文字の文字列のすべての組合せが、文書インデックス462内で用語として表される。いくつかの実施態様で、長さが1〜20のASCII文字の文字列のすべての組合せが、文書インデックス462内で用語として表される。いくつかの実施態様で、長さが1〜30のASCII文字の文字列のすべての組合せが、文書インデックス462内で用語として表される。さらなる実施態様で、長さが1〜50のASCII文字の文字列のすべての組合せが、文書インデックス462内で用語として表される。さらに、文書インデックス462内の各用語に関連付けることのできる文書466の個数に制限はない。たとえば、いくつかの実施態様では、文書インデックス462を使用して、0個と100個との間の文書466が検索語に関連付けられ、0個と1000個との間の文書466が検索語に関連付けられ、0個と10000個との間の文書466が検索語に関連付けられ、或いは10000個を超える文書466が検索語に関連付けられる。さらに、所与の文書466に関連付けることのできる検索語の個数に制限はない。たとえば、いくつかの実施態様で、所与の文書466は、0個と10個との間の検索語、0個と100個との間の検索語、0個と1000個との間の検索語、0個と10000個との間の検索語、或いは10000個を超える検索語に関連付けられる。
【００２１】
本願の文脈で、文書466は、ウェブ文書、イメージ、マルチメディアファイル、テキスト文書、PDF若しくは他のイメージフォーマット付きのファイル、着信音、フルトラックメディア(full track media)などを含む、インデクシングされ、かつ検索エンジンによって取り出されることが可能なすべてのタイプの媒体と理解される。文書466は、その内容及びタイプに適当に、1つ以上のページ、区画、セグメント、又は他の構成要素を有することができる。同等に、文書466を、インターネット上の文書を指すのに一般に使用されているように、「ページ」と称する場合がある。本発明の範囲に関して、包括的用語「文書」の使用によって課せられる限定はない。本発明では、インデックス構成モジュール464によってインデクシングされた多数の文書466がある。通常、インデックス構成モジュール464によってインデクシングされた、10万個を超える文書、100万個を超える文書、10億個を超える文書、或いは1兆個を超える文書がある。
垂直集合450は、特定の非階層カテゴリに関する文書インデックス462内の文書を使用して構成される。たとえば、ある垂直集合450を、映画に関する文書インデックス462によってインデクシングされた文書から構成することができ、別の垂直集合450を、スポーツに関する文書インデックス462によってインデクシングされた文書から構成することができ、以下同様である。垂直集合450を、垂直エンジンサーバシステムオペレータによって比較的単純な形で構成し、合併し、又は分割することができる。いくつかの実施態様では、この形でセットアップされる数百個の垂直集合450がある。いくつかの実施態様では、この形でセットアップされる数千個の垂直集合450がある。
【００２２】
文書インデックス462が、インデックス構成モジュール464によって構成されたならば、垂直インデックス構成モジュール460は垂直インデックス442を構成することが可能である。これを達成するために、各垂直集合450が、反転される。図4から想起すると、各垂直集合450は、次の形を有する。
【表２】
2009533767.tif 000004
いくつかの実施態様で、垂直集合450内の各DocIdは、さらに、インデックス構成モジュール464によって割り当てられた文書品質スコアを含む。垂直集合450のそれぞれの反転及びこれらの反転された垂直集合のそれぞれの合併は、次のデータ構造を有する反転された文書-垂直インデックスにつながる。
【表３】
2009533767.tif 000005
したがって、文書インデックス462内の所与の文書466ごとに、所与の文書に関連付けられた垂直集合450のリストが、反転された文書-垂直インデックス内で提供される。任意の所与の文書に関連付けられた複数の垂直集合450を設けることができる。さらに、各文書466が垂直集合450の一意のセットに関連付けられるという要件はない。
【００２３】
反転された文書-垂直インデックスを用いると、今や、文書インデックス462内の文書識別子を、反転された文書-垂直インデックス内で示される文書識別子に関連する対応する垂直集合に置換することによって、垂直インデックス442を作成することが可能である。1つの手法で、これは、用語ごとの基礎で文書インデックス462をスキャンし、反転された文書-垂直インデックス内に示される各用語にそれ自体が関連する文書に関連する垂直集合450のセットを収集することによって行われる。たとえば、上で提示した例示的文書インデックス462内の用語1を検討されたい。文書インデックス462によれば、用語1は、docID1a、…、docID1xに関連する。したがって、セットdocID1a、…、docID1x内の個別のdocIDiごとに、反転された文書-垂直インデックスを調べて、どの垂直集合450が個別のdocIDiに関連するかを判定する。次に、用語1の垂直インデックスリスト444を構成するために、これらの垂直集合450のそれぞれを用語1に関連付ける。したがって、文書インデックス462内の用語1のエントリ
【表４】
2009533767.tif 000006
から始めて、垂直インデックスリスト
【表５】
2009533767.tif 000007
を構成するために、docID1a、…、docID1xに関連する垂直集合のセットが、反転された文書-垂直インデックスから収集され、ここで、V1、V2、…、VNのそれぞれは、一意の垂直集合450を指す垂直集合識別子である。このデータ構造が、垂直インデックスリスト444である。示されているように、垂直インデックスリスト444は、定義可能な属性(たとえば、「用語1」)を共有する垂直集合450の垂直集合識別子のリストである。用語1が「vacation(休暇)」である場合に、垂直インデックスリスト444は、単語「vacation」を含む文書を保持する垂直集合450の識別子を含む。このリストを定義する述部、上の例では「用語1」を、「ヘッド用語(head term)」と称する。
【００２４】
用語の集合内のすべての用語を検討することによって、垂直インデックス442が構成される。用語の集合に、多数の用語がある場合がある。たとえば、いくつかの実施態様で、用語の集合は、長さが1〜10のASCII文字の文字列のすべての組合せ、長さが1〜20のASCII文字の文字列のすべての組合せ、長さが1〜30のASCII文字の文字列のすべての組合せ、又は長さが1〜50のASCII文字の文字列のすべての組合せを含む。垂直インデックス442は、所与の属性(検索語)に対応する垂直インデックスリスト444を突き止め、及び返すための効率的なプロセスと共に、垂直インデックスリスト444を含む。たとえば、ある集合に現れるすべての単語の垂直インデックスリスト444を含む垂直インデックス442を定義することができる。垂直インデックス442は、集合内の所与の単語ごとに、これらの垂直集合450の垂直インデックスリスト444を格納する。所与の単語の垂直インデックスリスト444内の各そのような垂直集合450は、その所与の単語を含む少なくともいくつかの文書466を保持する。
図5を参照すると、本発明の一実施態様による、垂直インデックス442の特定の構造が与えられている。この実施態様では、垂直インデックス442は、ハッシュルックアップテーブル及び垂直インデックスリストストレージ構成要素を含む。ハッシュルックアップテーブルは、個々の垂直インデックスリスト444の位置を正確に示すポインタ又はファイルオフセットを含む。所与のヘッド用語(検索語)のハッシュは、その所与のヘッド用語の文書466を保持する垂直集合450の対応するリストへの正しいオフセットを提供する。たとえば、ヘッド用語が「vacation」である事例を検討されたい。このヘッド用語は、この例では、オフセット03を与えるようにハッシュ化される。垂直インデックス442内のオフセット03でのテーブルルックアップは、ヘッド用語「vacation」に対応する識別子のリスト[vertId31, vertId32, vertId33, vertId34,  …]を与える。セット[vertId31, vertId32, vertId33, vertId34,  …]内の各識別子は、「vacation」ヘッド用語を有する文書を含む垂直集合450に対応する。図5の参照を続けると、垂直インデックスリスト444は、通常はそうなので、異なる長さを有するものとして図示されている。いくつかの実施態様では、以下でより詳細に説明するように、用語固有スコアが、各垂直インデックスリスト444内の各垂直識別子に関連付けられる。
【００２５】
垂直インデックス442を構成するステップを、先に詳細に示した。垂直インデックス442は、ヘッド用語の集合内の個別のヘッド用語ごとに、その個別のヘッド用語を含む文書を有する垂直集合450のリストを含む。垂直インデックス442を最適化するために、追加ステップを行って、各個別の垂直インデックスリスト444内で参照される各垂直集合450をランキングし、その結果、最も重要な垂直集合450だけが、任意の所与の垂直検索照会について返されるようにする。したがって、垂直インデックス442内で表される個別のヘッド用語(t)ごとに、その個別のヘッド用語の垂直インデックス444内にリストされた各垂直集合(v)が、そのヘッド用語に関してスコアリングされて、score(t,v)を与える。垂直集合450のスコアは、特定のヘッド用語のscore(t,v)を与えられれば、多数の異なる形で計算することができる。いくつかの実施態様で、垂直集合450のスコアは、特定のヘッド用語(score(t,v))を与えられて、次のように垂直集合内のすべての文書466にまたがって合計することによって計算される。
【数１】
2009533767.tif 000008
式中、score(t,d)は、垂直集合450内の文書のスコアであり、かつw(d,v)は、その文書を含む垂直集合450に割り当てられる、ある重みである。
【００２６】
いくつかの実施態様で、w(d,v)は、最高頻度の所与のヘッド用語を有する垂直集合450をアップウェイトする(upweight)重みである。言い換えると、そのような実施態様で、w(d,v)は、ヘッド用語(t)のより低い出現率を有する文書を有する第2の垂直集合450より、ヘッド用語(t)のより高い出現率を有する文書を有する第1の垂直集合450について、より大きい。いくつかの実施態様で、w(d,v)は、そのような垂直集合450内の最高ランキングの文書内のヘッド用語のより高い優勢を有する垂直集合450をアップウェイトする重みである。言い換えると、そのような実施態様で、w(d,v)は、第2の垂直集合450の高ランキングの文書466内のヘッド用語(t)のより低い出現率を有する第2の垂直集合450より、第1の垂直集合450の高ランキングの文書466内のヘッド用語(t)のより高い出現率を有する第1の垂直集合450について、より大きい。ここで、高ランキングの文書466とは、インデックス構成モジュール464による高ランクを受け取った文書を指す。インデックス構成モジュール464がある種の文書466に高ランクを割り当てる方法は、当技術分野で周知である。文書466をランキングする1つの判断基準は、たとえば、何個の他の文書が所与の文書466を参照するかを査定することである。そのようなランキング方式の背後にある発想は、所与の文書を参照する文書が多ければ多いほど、その所与の文書がより興味深いものでなければならないというものである。文書をランキングする複数の他の判断基準及び方法は、当業者に既知であり、そのような判断基準及び方法のすべてを、本発明で文書466をランキングするのに使用することができる。次に、文書インデックス462内のそのような文書466のそのようなランキングが、そのような文書を含む垂直集合450のscore(t,v)を割り当てるのに使用される。その代わりに、より好ましくない実施態様では、文書466を、当技術分野で文書をランキングするのに一般に使用されるものと同一の判断基準及び方法を使用して、インデックス構成モジュール464と独立に、垂直集合内でランキングすることができる。いくつかの実施態様で、w(d,v)は、score(t,v)を計算するのに使用されない。すなわち、いくつかの実施態様では、w(d,v)がない。いくつかの実施態様で、所与の垂直集合450のw(d,v)は、垂直集合450の人気、垂直集合450内の文書466のリンク密度の集計、又は文書466の品質を評価するのに通常使用される任意の他の判断基準の関数である。
【００２７】
いくつかの実施態様では、
【数２】
2009533767.tif 000009
であり、式中、f(d,t)は、ヘッド用語(t)が垂直集合450の文書(d)内に現れる回数であり、かつf(N)は、垂直検索エンジン424にアクセス可能な(そのような垂直集合がメモリ414内に格納され、かつ/又はネットワークインターフェース410を介してアクセス可能であるのいずれであれ)垂直集合450の個数の関数である。いくつかの実施態様で、f(N)は、単純にMv、すなわち、メモリ414内に格納され、かつ/又はネットワークインターフェース410を介して入手可能な垂直集合450の個数である)。いくつかの実施態様で、f(N)は、log(Mv)、又はMvの平方根などのMvのいくつかの他の関数である。式(II)では、v(t)は、ヘッド用語(t)を含む垂直集合450の個数である。実際には、v(t)は、ヘッド用語(t)の垂直インデックスリスト442に含まれる垂直集合450の個数である。また、式(II)では、A及びBの両方が、いくつかの実施態様で1と等しい。他の実施態様では、A及びBは、同一の又は異なる定数である。いくつかの実施態様で、AはBより大きい。いくつかの実施態様で、AはBより小さい。いくつかの実施態様で、AはBと等しい。score(t,d)の他の式が可能である。たとえば、いくつかの実施態様では、
score(t,d)=f(d,t)  (III)
であり、式中、f(d,t)は、ヘッド用語(t)が垂直集合450の文書(d)内に現れる回数である。
【００２８】
式(II)を式(I)に代入し、並べ変えることによって、いくつかの実施態様で、大域的w(d,v)が垂直集合450全体の各文書に適用される実施態様では
【数３】
2009533767.tif 000010
であり、及び、w(d,v)が用語(t)のアイデンティティに基づいて各文書に適用される実施態様では
【数４】
2009533767.tif 000011
である。
【００２９】
いくつかの実施態様で、式(IV)又は(V)のいずれかで表されたscore(t,v)は、用語(t)に関する垂直集合450の全体的スコア(scoreov)の一部であり、次の形を有し、
μ1*score1(t,v)+ μ2*score2(t,v)  (VI)
式中、score2は、式(IV)及び(V)のいずれかのscore(t,v)であり、かつscore1(t,v)は、次の形を有し、
score1(t,v)=垂直vのヘッド用語のスコア=(C+log(f(v,t)))*log(D+f(N)/v(t))  (VII)
式中、f(v,t)は、用語(t)を含む垂直集合(v)の文書466の個数であり、f(N)は、メモリ414によって追跡される垂直集合の個数の関数であり(たとえば、Nすなわちメモリ414によって追跡される垂直集合の個数、log(N)、Nの平方根など)、v(t)は、用語(t)の垂直インデックスリスト444の垂直集合450の個数であり、並びに、C及びDは定数である。C及びDの両方が、いくつかの実施態様で1と等しい。他の実施態様では、C及びDは、同一の又は異なる定数である。いくつかの実施態様で、CはDより大きい。いくつかの実施態様で、CはDより小さい。式(VI)で、μ1及びμ2は、独立に調整できる項である。通常の実施態様で、μ1及びμ2は、定数値である。これらの値は、同一又は異なるものとすることができる。いくつかの実施態様で、μ1は0である。いくつかの実施態様で、μ1は、μ2より小さい定数値である。いくつかの実施態様で、μ1は、μ2より大きい定数値である。
【００３０】
図6を参照して、本発明の一実施態様による例示的方法を説明する。この方法は、ユーザが垂直検索照会を作成する時に、垂直集合450の推奨されるリストをユーザに対話的に提供するために垂直検索エンジン424によって行われるステップの詳細を示すものである。
ステップ602。ステップ602では、垂直検索照会をクライアントコンピュータ100から受け取る。垂直検索照会は、おそらくはブール演算子AND、OR、並びにNOTによって結合され、任意選択で括弧又は引用符によってグループ化された、キーワードのリストからなる。垂直検索照会の例は、(i)"Florida discount vacations"(フロリダ  値引き  休暇)、(ii)"The President of the United States"(米国の大統領)、及び"(car OR automobile) AND (transmission OR brakes)"((カー  OR  自動車) AND (トランスミッション  OR  ブレーキ))を含む。図3を参照すると、垂直検索照会は、所与の時点でのプロンプト302の内容である。いくつかの実施態様で、垂直検索照会は、http要求の形になっている。
ステップ604。ステップ604では、ユーザが垂直集合450を選択したかどうかに関する判定を行う。図3Aを参照すると、ユーザは、たとえば、vクラウド304にリストされた垂直集合のいずれかを選択することによって、いつでも垂直集合450を選択することができる。いくつかの実施態様で、プロンプト302が空である時には、垂直集合450がvクラウド304にリストされず、したがって、プロンプト302が空である時の段階では、ユーザは、そのような実施態様では垂直集合450を選択することができない。いくつかの実施態様で、vクラウド304は、プロンプト302が空である時に、人気のある及び/又はスポンサー付きの垂直集合450を投入される。ユーザが垂直カテゴリを選択していない場合には(604-No)、制御はステップ606に移る。ユーザが垂直カテゴリを選択している場合には(604-Yes)、制御はステップ620に移る。
【００３１】
ステップ606。ステップ606では、垂直検索照会を原子的垂直検索照会(atomic vertical search queries)に分解する。原子的垂直検索照会は、単一の用語又は述部条件からなる。たとえば、垂直検索照会"(car OR automobile) AND (transmission OR brakes)"は、単一の用語"car"、"automobile"、"transmission"、"brakes"と優先の述部条件"()"、AND、並びにORからなる。
ステップ608。通常の実施態様では、垂直検索照会内の原子的垂直検索照会のうちの1つだけが、新規であるか変更されたものである。したがって、ステップ608では、新規であるか又は変更された原子的垂直検索照会をはじめに識別する。例示のために、ステップ608の最後のインスタンスでの垂直検索照会が、"car OR auto"であったが、ステップ608の現在のインスタンスでは、垂直検索照会が"car OR automobile"であると考えられたい。ステップ606では、垂直検索照会"car OR automobile"が、原子的垂直検索照会"car"及び"automobile"に分解される。原子的垂直検索照会"car"は、ステップ608の最後のインスタンスに関して変更されないままであり、したがって、ステップ608の新しいインスタンスではハッシュ化されない。その一方で、原子的垂直検索照会"automobile"は、ステップ608の最後のインスタンスでは形"auto"を有し、したがって、ステップ608の新しいインスタンスではハッシュ化されない。いくつかの実施態様では、原子的垂直検索"automobile"全体を再ハッシュ化するよりもむしろ、ステップ608の前のインスタンスからの"auto"のハッシュが使用され、累積ハッシュが、ステップ608の現在のインスタンスでの"automobile"のフルハッシュに達するために、追加文字"mobile"を用いて実行される。いくつかの実施態様では、そのような累積ハッシュ化が実行されない。累積ハッシュ化は、いくつかの実施態様では、ユーザが多数のさらなるキーストロークをプロンプト302に入力する機会を有する前に、推奨される垂直集合450をクライアントコンピュータ100に返すことができるようにするために、好ましい。したがって、ステップ606から612までの計算を高速化するすべての技法が好ましい。
【００３２】
いくつかの実施態様で、原子的垂直検索照会は、ハッシュ化されない。そのような実施態様では、垂直インデックス442は、原子的垂直検索照会のハッシュ値によって順序付けられない。いくつかの実施態様で、垂直検索照会内の複数の原子的垂直検索照会が、新規であるか又は変更されている。そのような実施態様では、各新規の又は変更された原子的垂直検索照会が、ステップ608で別々にハッシュ化される。先駆式が、これらの変更された原子的垂直検索照会のいずれかについて使用可能である場合には、そのような先駆式のハッシュが、対応する変更された原子的垂直検索照会のハッシュを高速化するのに使用される。
ステップ610。ステップ610では、垂直照会内の各新規の又は変更された原子的垂直検索照会の垂直インデックスリスト444を識別する。図5に示されたものなど、垂直インデックス442がハッシュテーブルである実施態様では、この動作は、各新規の又は変更された原子的垂直検索照会の個別のハッシュを使用する単純なハッシュルックアップである。いくつかの実施態様では、ハッシュが使用されない。たとえば、いくつかの実施態様で、垂直インデックス442は、配列、リスト、スタック、キュー、ツリー、又はデータベースなど、垂直インデックス444を含む、いくつかの他の形のデータ構造である。そのようなデータ構造は、参照によってその全体が本明細書に組み込まれているBrookshear著、「計算機科学」(Computer Science)、2003年、Addison-Wesley、米国New York(ニューヨーク)州に記載されている。いくつかの実施態様で、垂直検索照会内の新規ではない原子的垂直検索照会に対応する垂直インデックス444は、ステップ610の以前のインスタンスから既に知られており、したがって、ステップ610の連続するインスタンスでは入手されない。いくつかの実施態様で、垂直検索照会の各原子的垂直検索照会の垂直インデックス444は、ステップ610の各インスタンスで識別される。実施態様にかかわりなく、ステップ610の完了時に、垂直検索照会内の各原子的垂直検索照会の垂直インデックスリスト444が識別される。
【００３３】
ステップ612。ステップ612では、クライアントコンピュータ100からの垂直検索照会の推奨される垂直集合450のリストを構成する。垂直検索照会が1つの原子的垂直検索語だけを含む場合には、ステップ612は、単純に、ステップ610のインスタンスを識別した原子的垂直検索語の垂直インデックス444内で参照される垂直集合450の名前のそれぞれを抽出することを含む。垂直検索語が複数の原子的垂直検索語を含む場合には、さらなる作業が必要である。2つの検索語の間に演算子がないか、又は2つの検索語が"AND"演算子によって結合されるかのいずれかにおいて、垂直検索語照会内に2つの原子的垂直検索語がある事例を検討されたい。この場合に、各原子的垂直検索語の垂直集合450の名前が、まず、先に説明したプロセスを使用して識別される。したがって、原子的垂直検索語が、term1及びterm2である場合に、この動作は、次の識別をもたらす。
【表６】
2009533767.tif 000012
次に、このインスタンスでの推奨される垂直集合450のリストを識別するために、本発明のいくつかの実施態様では、垂直集合450の各リストの交差をとる。これは、そのような実施態様で、両方の垂直インデックスリスト444に共通する垂直集合450だけが、推奨される垂直集合450のリストに含まれることを意味する。いくつかの実施態様では、各推奨される垂直集合が両方のインデックスリスト444に存在するという要件に加えて、各推奨される垂直集合は、最小関連性score(v,t)を有さなければならない。
【００３４】
次に、2つの原子的垂直検索語が、"OR"演算子によって結合される事例を検討されたい。ここでは、2つの検索語の2つの垂直インデックスリスト444内の垂直集合450の和集合をとる。すなわち、いずれかの垂直インデックスリスト444に含まれる垂直集合450が、垂直検索照会に応答して、クライアントコンピュータ100に送り返される候補垂直集合450の名前のリストに含めるために選択される。いくつかの実施態様で、各垂直インデックスリスト444内の各垂直集合450の関連性スコアも、どの垂直集合450が候補垂直集合450の名前のリストに関して選択されるかを決定するのに使用される。たとえば、いくつかの実施態様で、両方の原子的垂直検索語の垂直インデックスリスト444内で表される垂直集合450が、合計される。この合計演算のゆえに、そのような実施態様では、両方の原子的垂直検索語の垂直インデックスリスト444内で表される垂直集合450が、リスト又は推奨される垂直集合450に現れる傾向がある。しかし、そのような実施態様で、それでも、2つの垂直インデックスリスト444のうちの一方だけに現れる垂直集合450が高いスコアを有する場合に、そのような垂直集合450を推奨することは完全に可能である。次の例に、この点を示す。各垂直集合450の品質又は関連性スコアが計算済みであり、かつterm1及びterm2が"OR"演算子によって関係付けられる、term1及びterm2の垂直インデックス444を検討されたい。
【表７】
2009533767.tif 000013
したがって、所与の垂直検索照会に応答して、どの垂直集合450を推奨される垂直集合のリストに組み込まなければならないかを決定するために、次の計算が行われる。
VC150 = score150,t1
VC170 = score170,t1 + score170,t2
VC175 = score175,t1 + score175,t2
VC151 = score151,t2
式中、VC170及びVC175が、2つのスコアの合計から利益を得るが、VC150及びVC151のそれぞれは、1つのスコアだけを受け取る。しかし、それでも、VC150又はVC151が、VC150及びVC151より高いスコアを有する場合があり、したがって、推奨される垂直集合450のリストに含まれることが、完全に可能である。ここで、スコアのそれぞれは、上で式(I)から(VII)までに関して説明したスコアのいずれにすることもでき、或いは、垂直集合品質又は所与の検索語への垂直集合の関連を割り当てる、いくつかの他のスコアとすることができる。
【００３５】
NOT演算子によって結合された2つの原子的垂直検索語について、否定される検索語の垂直インデックスリスト444内の垂直集合450が、否定されない検索語に関連する垂直インデックス444内の垂直集合450のリストから減算されて、所与の垂直検索語に関する垂直集合の推奨されるリストに達する。例示のために、各垂直集合450の品質又は関連性スコアが計算済みであり、かつterm1及びterm2が"NOT"演算子によって関係付けられる、term1及びterm2の垂直インデックス444を検討されたい。
【表８】
2009533767.tif 000014
したがって、この場合に、垂直集合VC150だけが、推奨される垂直集合450のリストに含めるために選択されるであろう。
【００３６】
より複雑な論理式を、AND、OR、並びにNOTなどのブール演算子によって結合された原子的垂直検索照会の組合せを使用して作成することができる。さらに、括弧を使用することによって、優先を導入することができる。当業者は、所与の垂直検索照会の推奨される垂直集合のリストの最終的なセットに達するために、他の形の論理を、垂直インデックス442内の垂直集合450のリストを合併し又は分割するのに使用することができ、そのような形の論理のすべてが、本発明の範囲に含まれることを了解するであろう。
いくつかの実施態様で、推奨される垂直集合450のリストは、最大個数の垂直集合450を含む。いくつかの検索式について、識別される垂直集合450の個数は、この最大値を超えない。しかし、いくつかの検索式について、識別される垂直集合450の個数は、推奨される垂直集合450の最大の可能な個数を超える。そのような実施態様では、各垂直集合450に関連する用語ベースの関連性スコアは、どの垂直集合が所与の垂直検索照会の垂直集合の推奨されるリストに含まれるかを判定するのに使用される。最上位スコアの垂直集合450だけが、このリストに関して選択される。
【００３７】
ステップ614〜618。ステップ608から612までによって実行されるルックアップは、高速になるように設計される。いくつかの実施態様で、垂直集合450の推奨されるリストは、ユーザによってプロンプト302に入力される各文字ストロークの間にクライアントコンピュータ100に返される。それに対応して、いくつかの実施態様で、クライアントコンピュータ100は、ユーザが図3のプロンプト302に新しい文字を入力するたびに、新しい垂直検索照会を送信する。いくつかの実施態様で、クライアントコンピュータは、列の終りの信号がクライアントコンピュータ100によって検出されるたびに、新しい垂直検索照会を送信する。そのような列の終りの信号は、いくつかの実施態様で、ユーザのタイピングの一時停止が検出される時に、クライアントコンピュータ100によって検出される。たとえば、図3A及び3Bを参照すると、"t"(図3A)の入力と"i"(図3B)の入力との間に遅延(たとえば、1秒、2秒の遅延、3秒の遅延など)がある場合に、列の終りの信号が、クライアントコンピュータ100によって検出され、"t"が、垂直検索照会としてリモートサーバ(垂直エンジンサーバ110)に送信される。いくつかの実施態様で、列の終りの信号は、スペース文字若しくはキャリッジリターン又は他の指定された文字がユーザによってプロンプト302に入力される時にも検出される。
【００３８】
いくつかの実施態様では、チェックを実行して、新しい垂直照会がクライアントコンピュータ100から受け取られたかどうかを判定する(ステップ614)。たとえば、いくつかの実施態様で、新しいhttp要求が、新規の又は改訂された垂直検索照会と共にクライアントコンピュータ100から受け取られたかどうかに関する判定を行う。新規の又は改訂された垂直照会が受け取られている場合に(614-Yes)、制御は、推奨される垂直集合を報告せずに、ステップ604に戻って渡される(ステップ616)。新規の又は改訂された垂直検索照会が到着していない場合に(614-No)、推奨される垂直集合450をクライアントコンピュータ100に報告し、このクライアントコンピュータ100では、推奨される垂直集合450がvクラウド304などのグラフィック内に表示される(ステップ618)。いくつかの実施態様で、推奨される垂直集合450は、新しい垂直検索照会がクライアントコンピュータ100から到着した時であってもクライアントコンピュータ100に報告される。
【００３９】
いくつかの実施態様で、クライアントコンピュータ100に返される推奨される垂直集合のリストは、推奨される垂直集合450のアイデンティティ(名前)と各垂直集合450の関連性スコアとの両方を含む。そのような関連性スコアは、たとえば上で式(I)から(VII)までに関して説明したスコアリング関数のいずれか、又は所与の垂直検索照会に対する垂直集合450品質及び/若しくは垂直集合450を査定する任意の他のスコアリング関数を使用して、計算される。次に、図3に示されているように、より高いスコアを有する垂直集合が、より小さい関連性スコアを有する垂直集合より大きいグラフィックスとして表示される。たとえば、図3を参照すると、垂直検索照会"t"に関して、垂直集合"Apparel"は、垂直集合"television programs"より高い総合関連性スコアを有する。したがって、垂直集合"Apparel"は、vクラウド304内で垂直集合"television programs"より大きいグラフィックスとして表示される。いくつかの実施態様では、より高い度合の関連を有する垂直集合450をより大きいグラフィックスとして表示するよりむしろ、又はそれに加えて、他のしるしを使用することができる。たとえば、そのような垂直集合を、あるカラースペクトルから選択された色でリストすることができる。たとえば、より関連する垂直集合を、カラースペクトルの一方の端にあるもの、たとえば緑とすることができ、より関連しない垂直集合を、カラースペクトルの他方の端にあるものとすることができる。また、より関連する垂直集合を、より太いフォーマットで表示することもでき、より関連しない垂直集合を、より細いフォーマットで表示することもできる。
ステップ618の完了時に、制御は、新しい垂直検索照会を待つために、ステップ602に戻って渡される。
【００４０】
ステップ620〜622。最終的に、ユーザは垂直集合450を選択する。これが行われる時には、垂直検索照会が、選択された垂直集合450に向けられる。選択された垂直集合450から、最終的な垂直検索照会に最も関連する文書を検索する(ステップ620)。いくつかの実施態様では、検索エンジン422が、選択された垂直集合450の検索を実行する。次に、ステップ622で、これらの高ランキング文書をクライアントコンピュータ100に報告し、このクライアントコンピュータ100では、これらの高ランキング文書が、たとえば図3Fに示されているように表示される。
検索照会を構成しつつあるユーザに垂直集合を自動的に推奨するコンピュータシステム、グラフィカルユーザインターフェース、コンピュータプログラム製品、及び方法を開示した。本技法は、複数の理由から非常に有利である。垂直インデックス442の検索は、極めて高速である。これは、垂直検索エンジン424が、ユーザキーストロークの間に、推奨される垂直集合450のリストをユーザに返すことを可能にする。したがって、ユーザは、どの種類のトピックが検索照会に関連するかをすばやく知ることができ、カテゴリのうちの1つを選択するか、検索照会をタイプし続けるか、又は興味深くはない垂直集合450が現れている場合には新しい垂直検索照会を新たに始めるかのいずれかを行うことができる。本発明を用いると、ユーザは、カテゴリの階層リストを通ってナビゲートする必要も、何が検索すべき正しいカテゴリである可能性があるかに関する一様にされた推測を行う必要もなしに、関連する垂直集合内で検索を実行することのすべての利益を享受することができる。さらに、複数の展望から、図3Fに示されているように、垂直集合のユーザベースの選択が、垂直検索照会と結合されて、検索照会の曖昧さ除去の基礎を提供し(たとえば、tigerが、「タイガーウッズ」、Macintoshオペレーティングシステム、又は動物のどれを意味するかを判定する)、したがって、意味があり関連する公告及び/又はスポンサードリンクを配送するので、本発明は非常に有利である。
【００４１】
本明細書に列挙されたすべての参考文献は、各個々の出版物、特許、又は特許出願が具体的かつ個別にあらゆる目的のためその全体が参照によって組み込まれていることが示されているのと同一の範囲で、その全体が参照によって、またあらゆる目的のため本明細書に組み込まれている。
本発明は、コンピュータ可読記憶媒体に内蔵されるコンピュータプログラム機構を含むコンピュータプログラム製品として実施することができる。たとえば、コンピュータプログラム製品は、図4に示されたプログラムモジュールを含むことができる。これらのプログラムモジュールは、CD-ROM、DVD、磁気ディスクストレージ製品、又は任意の他のコンピュータ可読データ若しくはプログラムストレージ製品に格納することができる。コンピュータプログラム製品内のソフトウェアモジュールは、インターネットを介して又は他の形で、搬送波上のコンピュータデータ信号(その中にソフトウェアモジュールが埋め込まれる)の伝送によって、電子的に配布することもできる。
当業者に明白なように、本発明の多数の修正態様及び変形態様を、本発明の趣旨及び範囲から逸脱せずに作ることができる。本明細書で説明した特定の実施態様は、例としてのみ提供されるものである。これらの実施態様は、本発明の原理及び本発明の実用的応用例を最もよく説明し、これによって、当業者が、企図される特定の用途に適するようにさまざまな変更を加えて本発明及びさまざまな実施態様を最もよく利用できるようにするために選択及び記載した。本発明は、添付の特許請求の範囲が資格を与えられる同等物の全範囲と共に、添付の特許請求の範囲の言葉によってのみ限定される。
【図面の簡単な説明】
【００４２】
【図１】従来技術によるdmozウェブサイトポータルを示す図である。
【図２】本発明の実施態様による垂直エンジンサーバに照会をサブミットするクライアントコンピュータを示す図である。
【図３Ａ−３Ｆ】垂直検索照会の各文字が本発明の実施態様に従ってプロンプトに入力される時の垂直検索照会「tiger」に関連する垂直カテゴリの漸進検索を示す図である。
【図４】本発明の一実施態様による垂直エンジンサーバ400を示す図である。
【図５】本発明の一実施態様による垂直インデックスのアーキテクチャを示す図である。
【図６】本発明の実施態様による例示的方法を示す図である。  類似する符号は、これらの図面の複数の図を通じて対応する部分を指す。
【図１】
2009533767.tif 000023
【図２】
2009533767.tif 000024
【図３Ａ】
2009533767.tif 000025
【図３Ｂ】
2009533767.tif 000026
【図３Ｃ】
2009533767.tif 000027
【図３Ｄ】
2009533767.tif 000028
【図３Ｅ】
2009533767.tif 000029
【図３Ｆ】
2009533767.tif 000030
【図４】
2009533767.tif 000031
【図５】
2009533767.tif 000032
【図６】
2009533767.tif 000033
【国際調査報告】
2009533767.tif 000034