(57)【要約】      （修正有）【課題】ローカル検索エンジンが、郵便番号や所在地住所等で示される所望の地理的区域の中から、関連性のある結果を効率的に探し出し、その情報を返却できるよう文書をインデックス付けする。【解決手段】ローカル検索エンジンは、各文書ごとに、地理的領域集合体をまとめて規定する複数の場所識別子をインデックス付けすることにより、地理的区域に関連性のある文書を効率的にインデックス付けする。インデックスを作成する際、検索エンジンは、文書に関連性のある地理的区域の周りの地理的区域のセットを定め、地理的区域のセットへの参照を文書インデックスに関連付け得る。【選択図】図４
2011238248.tif 000002
【特許請求の範囲】
【請求項１】
文書をインデックス付けするための方法であって、
前記文書から、前記文書に関連付けられている地理的場所を、１つ以上のサーバ装置内の１つ以上のプロセッサによって抽出するステップと、
前記地理的場所に関連付けられている特定の地理的区域を、１つ以上のサーバ装置内の１つ以上のプロセッサによって識別するステップと、
予め定められた範囲内で、前記文書に関連付けられている前記特定の地理的区域を囲み、かつ、前記文書に関連付けられていない複数の周囲の地理的区域を、１つ以上のサーバ装置内の１つ以上のプロセッサによって定めるステップと、
前記特定の地理的区域への参照および前記複数の周囲の地理的区域への参照を含むように前記文書を１つ以上のサーバ装置内の１つ以上のプロセッサによってインデックス付けするステップを含む、方法。
【請求項２】
前記特定の地理的区域および前記複数の周囲の地理的区域への前記参照は、場所識別子によって特定される、請求項１に記載の方法。
【請求項３】
前記場所識別子は、階層型三角メッシュの中のノードの標識を含む、請求項２に記載の方法。
【請求項４】
前記文書は店舗の一覧表である、請求項１に記載の方法。
【請求項５】
前記文書は地理的に関連性のあるウェブ文書である、請求項１に記載の方法。
【請求項６】
前記複数の周囲の地理的区域は場所識別子によって参照され、前記方法はさらに、
複数の場所識別子を定めるステップを含み、各々の前記場所識別子は、前記複数の周囲の地理的区域のうちの１つに関連付けられている、請求項１に記載の方法。
【請求項７】
検索エンジンであって、
文書インデックスを記憶するための手段と、
文書から、前記文書に関連付けられている地理的場所を抽出するための手段と、
前記地理的場所が位置する特定の地理的領域を識別するための手段と、
予め定められた範囲内で、前記特定の地理的領域を囲み、かつ、前記文書に関連付けられていない別の周囲の地理的領域を識別するための手段と、
前記文書インデックスの中に前記特定の地理的領域および前記別の周囲の地理的領域への参照を含むように前記文書をインデックス付けするための手段とを含む、検索エンジン。
【請求項８】
文書をインデックス付けするための方法であって、
文書から、地理的場所を、１つ以上のサーバ装置内の１つ以上のプロセッサによって抽出するステップと、
前記地理的場所が位置する特定の地理的領域を、１つ以上のサーバ装置内の１つ以上のプロセッサによって識別するステップと、
前記地理的場所が位置する前記特定の地理的領域から特定の半径の円内に少なくとも部分的に位置し、かつ、前記文書に関連付けられていない別の地理的領域を、１つ以上のサーバ装置内の１つ以上のプロセッサによって定めるステップと、
前記関連付けられた参照で前記特定の地理的領域への参照と、前記別の地理的領域への参照とによって、前記文書を、１つ以上のサーバ装置内の１つ以上のプロセッサによってインデックス付けするステップとを含む、方法。
【請求項９】
前記特定の地理的領域への文書参照と前記別の地理的領域への文書参照とを、階層型三角メッシュの中のノードに対応する場所識別子となるように、１つ以上のサーバ装置内の１つ以上のプロセッサによって定めるステップをさらに含む、請求項８に記載の方法。
【請求項１０】
前記参照が前記文書の中の用語であるかのように前記参照を文書インデックスに挿入することによって前記文書を、１つ以上のサーバ装置内の１つ以上のプロセッサによってインデックス付けするステップをさらに含む、請求項８に記載の方法。
【請求項１１】
前記文書は店舗の一覧表である、請求項８に記載の方法。
【請求項１２】
前記文書は地理的に関連性のあるウェブ文書である、請求項８に記載の方法。
【請求項１３】
プロセッサによる実行のためのプログラミング命令を含むメモリ装置であって、
地理的領域を複数の個別領域に分割するためのプログラミング命令と、
文書から地理的場所を抽出するためのプログラミング命令と、
前記地理的場所が位置する特定の地理的領域を識別するためのプログラミング命令と、
前記地理的場所が位置する前記特定の地理的領域を囲むとともに、前記特定の地理的領域から特定の半径の円内に少なくとも部分的に位置し、かつ、前記文書に関連付けられていない別の地理的領域を識別するためのプログラミング命令と、
前記文書からの用語を含むインデックスにおいて、前記文書を、前記特定の地理的領域への参照と、前記別の地理的領域への参照とに関連付けるためのプログラミング命令とを含む、メモリ装置。
【請求項１４】
地理的領域に関連付けられている検索クエリーを、１つ以上のサーバ装置における１つ以上のプロセッサによって受けるステップと、
前記地理的領域に関連付けられている場所識別子を、１つ以上のサーバ装置における１つ以上のプロセッサによって定めるステップと、
前記検索クエリーおよび前記場所識別子と、前記文書インデックスと、の比較に基づいて、前記文書が前記検索クエリーに関連性があるかどうかを、１つ以上のサーバ装置における１つ以上のプロセッサによって判断するステップとをさらに含む、請求項８に記載の方法。
【請求項１５】
前記検索によって判定された関連性のある文書をユーザに送信するステップをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記場所識別子は、階層型三角メッシュの中のノードへの参照である、請求項１４に記載の方法。
【請求項１７】
前記検索クエリーを受けるステップは、ユーザが入力する検索用語および地理記述用語を受けるステップを含む、請求項１４に記載の方法。
【請求項１８】
所望の検索領域の指示を受けるステップと、
前記所望の検索領域と以前にインデックス付けされた検索領域との間の差を判断するステップと、
前記差に基づいて場所識別子のセットを定めるステップと、
前記検索クエリーおよび前記場所識別子のセットに基づいて前記検索を行なうステップとをさらに含む、請求項１４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
背景
Ａ．発明の分野
本明細書中で説明される実現例は検索エンジンに関し、より特定的には、地理的領域に関連性のある文書をローカル検索エンジンが効率的に検索することができる技術に関する。
【背景技術】
【０００２】
Ｂ．関連技術の説明
ワールドワイドウェブ（「ウェブ」）は大量の情報を含んでいる。しかしながら、情報の所望の部分を探し出すことは困難であり得る。ウェブ上の情報量およびインターネット検索に不慣れな新しいユーザの数は急速に増加しているため、この問題は倍加している。
【０００３】
検索エンジンは、ユーザが関心のあるウェブページへのハイパーリンクを返そうと試みる。一般的に、検索エンジンによるユーザの関心の判断は、ユーザが入力する（検索クエリーと称される）検索用語に基づいている。検索エンジンの目標は、検索クエリーに基づき、ユーザに、（たとえばウェブページなどの）高品質の関連性ある結果へのリンクを提供することである。典型的に、検索エンジンは、検索クエリー中の用語を予め記憶されたウェブページのコーパスと一致させることによってこれを達成する。ユーザの検索用語を含むウェブページは「ヒット」であり、リンクとしてユーザに返される。
【０００４】
ユーザに返されるウェブページの関連性および品質を向上させようとして、検索エンジンは、最も関連性が高いおよび／または最も高品質のページが、ユーザに返されるヒットリストの一番上に来るようにヒットリストを並べ替えるよう試み得る。たとえば、検索エンジンは、各々のヒットにランクまたはスコアを割当て得る。ここでスコアとは、ウェブページの関連性または重要性に対応するように設計される。
【０００５】
ローカル検索エンジンは、特定の地理的領域内の関連性のあるウェブページおよび／または店舗一覧表を返そうと試みる検索エンジンである。ローカル検索のため、ユーザは、検索クエリーを入力し、その周りで検索クエリーを行なうべき地理的領域を特定し得る。ローカル検索エンジンは、地理的領域に属する関連性のあるウェブページまたは地理的領域の中の店舗の一覧表などの関連性のある結果をユーザに返し得る。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
いくつかのローカル検索エンジンの場合、関心のあるローカルな地理的領域は、郵便番号または所在地住所からある数マイルなど、スタート場所からのある距離または半径で規定される領域である。理想的には、ローカル検索エンジンは、所望の地理的領域の中から関連性ある結果を効率的に探し出し、これを返す必要がある。
【課題を解決するための手段】
【０００７】
発明の概要
１つの局面は、文書をインデックス付けするための方法に向けられている。この方法は、文書に関連付けられている場所を定めるステップと、文書に関連付けられている場所の周りの場所のセットを定めるステップと、場所および場所のセットへの参照を含むように文書をインデックス付けするステップとを含む。
【０００８】
発明の別の局面は、文書をインデックス付けするためのさらに別の方法に向けられている。方法は、第１の地理的区域に関連性を有する文書を識別するステップと、第１の地理的区域の周りの地理的区域のセットを定めるステップと、第１の地理的区域および地理的区域のセットへの参照を文書に関連付けるステップに関連付けられている参照で文書をインデックス付けするステップとを含む。
【０００９】
発明のさらに別の局面は、検索を行なう方法に向けられている。方法は、地理的領域に関連付けられている検索クエリーを受けるステップと、地理的領域に関連付けられている場所識別子を定めるステップと、検索クエリーおよび場所識別子と文書インデックスとの比較に基づいて検索クエリーに関連性のある文書の検索を行なうステップとを含む。
【図面の簡単な説明】
【００１０】
【図１】発明の原則に整合するシステムおよび方法を実現し得るネットワークの例示的な図である。
【図２】図１に示されるクライアントまたはサーバの例示的な図である。
【図３Ａ】階層型三角メッシュ（ＨＴＭ）を例示する図である。
【図３Ｂ】階層型三角メッシュ（ＨＴＭ）を例示する図である。
【図４】地理的関連性を有する文書をインデックス付けするための、発明の局面に整合する例示的な動作を説明するフローチャートの図である。
【図５】図４に示される動作を説明する図である。
【図６Ａ】地理的関連性を有する例示的な文書を説明する図である。
【図６Ｂ】地理的関連性を有する例示的な文書を説明する図である。
【図７】地理的関連性を有する別の例示的な文書を説明する図である。
【図８】発明の局面に整合する実現例に従ってローカル検索クエリーを処理する際の検索エンジンの例示的な動作を説明するフローチャートの図である。
【図９】発明の局面に整合する別の実現例に従ってローカル検索クエリーを処理する際の検索エンジンの例示的な動作を説明するフローチャートの図である。
【図１０】図９に示されるステップを説明するのに用いられる例示的なＨＴＭグリッドの図である。
【図１１】ユーザに提示され得るローカル検索ユーザインターフェイスの例示的な図である。
【図１２】ユーザに提示され得るローカル検索ユーザインターフェイスの例示的な図である。
【発明を実施するための形態】
【００１１】
この明細書に組入れられかつその一部を構成する添付の図面は、この発明の実施例を説明し、その記載とともにこの発明を説明する。
【００１２】
詳細な説明
以下のこの発明の詳細な説明は添付の図面を参照する。詳細な説明はこの発明を限定するものではない。
【００１３】
概要
ローカル検索エンジンは、所望の地理的領域に限定されるローカル検索クエリーについての結果を生成し得る。地理的領域は、たとえば、特定された地点または領域から（たとえば２０マイルなどの）ある距離によって規定され得る。検索結果は、文書の内容に基づいて、および複数の場所識別子にも基づいて地理的に関連性のある文書をインデックス付けすることによって効率的に生成される。１つの実現例では、場所識別子は等間隔をあけられた地理的区域を規定し、文書は、文書ごとにインデックス付けされた複数の場所識別子が、文書に関連付けられている領域の周りの予め定められた範囲を規定して選択されるようにインデックス付けされる。この文書インデックス付け技術により、地理的領域による効率的な検索が可能になる。
【００１４】
例示的なネットワークの概要
図１は、この発明の原則に整合するシステムおよび方法を実現し得るネットワーク１００の例示的な図である。ネットワーク１００は、ネットワーク１４０を介してサーバ１２０に接続されるクライアント１１０を含み得る。ネットワーク１４０は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、公衆電話交換網（ＰＳＴＮ）などの電話網、イントラネット、インターネット、またはネットワークの組合せを含み得る。簡略化のため、２つのクライアント１１０および１つのサーバ１２０がネットワーク１４０に接続されて図示されている。実際には、より多くのクライアントおよび／またはサーバが存在し得る。また、いくつかの例では、クライアントがサーバの機能を果たし、サーバがクライアントの機能を果たすことがある。
【００１５】
クライアント１１０は、無線電話、パーソナルコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）、ラップトップ、もしくは別のタイプの電算もしくは通信装置などのデバイス、これらのデバイスのうち１つで実行されるスレッドもしくはプロセス、および／またはこれらのデバイスのうち１つによって実行可能なオブジェクトを含み得る。サーバ１２０は、文書を処理し、検索し、および／または維持するサーバ装置を含み得る。クライアント１１０およびサーバ１２０は、有線、無線または光接続を介してネットワーク１４０に接続し得る。
【００１６】
サーバ１２０は、クライアント１１０が利用可能な検索エンジン１２５を含み得る。検索エンジン１２５は、クエリーに基づく文書検索エンジンであり得る。検索エンジン１２５は、地理的領域にローカルな結果を返すように特に設計され得る。検索エンジン１２５は、データベース１３５に記憶される文書に基づいてユーザ検索クエリーに応答し得る。データベース１３５に記憶される文書は、一般的に、特定の地理的領域に関連性があると判定された文書を含み得る。これらの文書は、たとえば、特定の住所に位置する店舗の店舗一覧情報または何らかの形で地理的領域に関連性のあるウェブ文書（たとえば、ローカルのレストランのレビューを提供するウェブ文書）を含み得る。
【００１７】
本明細書中で使用されるような文書という用語は、いずれの機械読取可能なおよび機械上に記憶可能なワークプロダクトも含むと広く解釈されるべきである。文書は、電子メール、店舗一覧表、ウェブサイト、ファイル、ファイルの組合せ、他のファイルへの埋込リンクを備える１つ以上のファイル、ニュースグループへの投稿などであり得る。インターネットの文脈では、通常の文書がウェブページである。ウェブページはしばしばコンテンツを含み、（メタ情報、ハイパーリンクなどの）埋込情報および／または（Java（登録商標）Script（登録商標）などの）埋込命令を含み得る。
【００１８】
例示的なクライアント／サーバアーキテクチャ
図２は、発明の原則に整合する実現例に従う、コンピュータデバイス２００と称されるクライアント１１０またはサーバ１２０の例示的な図である。コンピュータデバイス２００は、バス２１０、プロセッサ２２０、メインメモリ２３０、読出専用メモリ（ＲＯＭ）２４０、記憶装置２５０、入力装置２６０、出力装置２７０および通信インターフェイス２８０を含み得る。バス２１０は、コンピュータデバイス２００の構成要素間の通信を可能にする経路を含み得る。
【００１９】
プロセッサ２２０は、命令を解釈しかつ実行し得る、いずれの種類の従来のプロセッサ、マイクロプロセッサまたは処理ロジックも含み得る。メインメモリ２３０は、ランダムアクセスメモリ（ＲＡＭ）、またはプロセッサ２２０による実行のための命令および情報を記憶する別のタイプの動的記憶装置を含み得る。ＲＯＭ２４０は、従来のＲＯＭデバイス、またはプロセッサ２２０が使用するための命令および静的情報を記憶する別のタイプの静的記憶装置を含み得る。記憶装置２５０は磁気的および／または光学的記録媒体ならびにその対応のドライブを含み得る。
【００２０】
入力装置２６０は、キーボード、マウス、ペン、音声認識および／またはバイオメトリックメカニズムなどの、ユーザがコンピュータデバイス２００に情報を入力できるようにする従来のメカニズムを含み得る。出力装置２７０は、ディスプレイ、プリンタ、スピーカなどを含む、情報をユーザに出力する従来のメカニズムを含み得る。通信インターフェイス２８０は、コンピュータデバイス２００が他のデバイスおよび／またはシステムと通信できるようにするいずれのトランシーバ状のメカニズムも含み得る。たとえば、通信インターフェイス２８０は、ネットワーク１４０などのネットワークを介して別のデバイスまたはシステムと通信するためのメカニズムを含み得る。
【００２１】
検索エンジン１２５は、メモリ２３０などのコンピュータ読出可能媒体に記憶され得る。コンピュータ読出可能媒体は、１つ以上の物理的または論理的メモリデバイスおよび／または搬送波として規定され得る。検索エンジン１２５を規定するソフトウェア命令は、通信インターフェイス２８０を介してデータ記憶装置２５０などの別のコンピュータ読出可能媒体から、または別のデバイスからメモリ２３０に読込まれ得る。メモリ２３０に含まれるソフトウェア命令は、後述される処理をプロセッサ２２０に行なわせる。これに代えて、配線で接続された回路構成をソフトウェア命令の代わりにまたはこれと組合せて用いて、本発明に整合する処理を実行してもよい。このように、この発明の原則に整合する実現例は、ハードウェア回路構成とソフトウェアとのいずれの特定の組合せに限定されるものでもない。
【００２２】
場所識別子
データベース１３５中の文書は各々地理的領域に関連付けられ得る。地理的領域は、文書に関連付けられている場所識別子によって特定され得る。１つの実現例では、場所識別子は、周知の階層型三角メッシュ（ＨＴＭ）モデルなどの階層型グリッドを用いて地表のモデルから導出され得る。読者の便宜のため、ＨＴＭモデルを簡単に説明する。
【００２３】
階層型三角メッシュ（ＨＴＭ）は、地球などの球体の表面を球面三角形に分割する区画手法である。これは階層的な手法であり、細分部の面積は、正確には等しくないものの、ほぼ等しくなる。図３Ａは、（たとえば地表などの）球体３００を、領域Ｎ０、Ｎ１、Ｎ２、Ｎ３およびＳ０、Ｓ１、Ｓ２、Ｓ３として識別される８つの領域にまず細分したものを例示する図である。図３Ａで、領域Ｎ０、Ｎ１、Ｓ０およびＳ１のみが標識付けられており、その他の領域は球体の「裏側半分」に対応している。これらの細分部は８つの最大の同サイズの球面三角形である。各々の細分部は隣り合う辺の中点を接続することによって三角形にさらに細分され得る。図３Ｂは、次の細分化レベルを例示する図である。図３Ｂに示されるように、細分部Ｎ０は、細分部Ｎ００、Ｎ０１、Ｎ０２およびＮ０３として標識付けされる４つの細分部にさらに分割される。各々の細分部は実際には球体上の弧によって形成されるが、簡略化のため、図３Ｂの細分部は三角形の線のセグメントとして示される。細分部の大きさが小さくなるにつれ、各々の細分部の形状はより三角形に近づいていく。
【００２４】
細分部は、８つの根ノード（Ｎ０、Ｎ１、Ｎ２、Ｎ３、Ｓ０、Ｓ１、Ｓ２およびＳ３）を有するツリー構造の子ノードと考えることができる、各々の根ノードが４つの子ノードを有し得る。細分部はいずれのレベルまで継続してもよい。示された命名方式では、各々の連続するレベルで、細分部は細分化標識に文字を追加することによって命名される。たとえば、ノードＮ２０１１０２を考える。Ｎ２は根の名称を指し、後続の５桁（０１１０２）は各レベルでどの三角形を選ぶかを示す。これらの細分化標識は、データベース１３５中の地理的に関連性のある文書に関連付けられている場所識別子として用い得る。
【００２５】
当業者は、ＨＴＭ以外の地形面モデリング技術またはＨＴＭの異なる実現例を用いて、データベース１３５に記憶される場所識別子を実現し得ることを認識するであろう。たとえば、代替的に用い得る他の可能な細分化モデリング技術は、ＨＥＡＬＰｉｘ（階層型等面積同一緯度画素化）（Hierarchical Equal Area isoLatitude Pixelisation）、Ｃ−キー（C-Key）、ＵＴＭ（ユニバーサル横メルカトル）、および（英国の全国距離座標系などの）さまざまな地域座標システムを含む。
【００２６】
データベース１３５のインデックス付け
図４は、地理的関連性を有する文書をインデックス付けするための、発明の局面に整合する例示的な動作を説明するフローチャートである。
【００２７】
言及されたように、データベース１３５は、地理的に関連性のあるウェブ文書および店舗一覧表などの文書のインデックスを含み得る。インデックスは、文書中に見出される用語のインデックスであり得、各用語ごとにその用語を含むすべての文書のリストを記憶する逆インデックスデータ構造として形成され得る。
【００２８】
地理的に関連性のある文書が識別され得る（ステップ４０１）。本明細書中で用いられるような地理的に関連性のある文書とは、一般的に、何らかの態様で地理的場所に特定の関連性を有すると判定されたいずれの文書も指す。職業別電話帳一覧表などの店舗一覧表は各々、たとえば、店舗の住所で規定される地理的領域に関連性のある地理的に関連性のある文書と考えられ得る。ウェブ文書などの他の文書も特定の地理的関連性を有し得る。たとえば、店舗はホームページを有し得たり、店舗にコメントしたりまたはレビューを書いたりする文書の対象であり得たり、または何らかの他の形で店舗に関するウェブページによって言及されたりし得る。文書が関連付けられている特定の地理的場所は、住所または他の地理的シグナルからなど、多数の態様で定められ得る。
【００２９】
地理的に関連性のある文書に関連付けられている地理的領域は次に、その対応の場所識別子にマッピングされ得る（ステップ４０２）。換言すると、文書に関連付けられている（たとえばＮ２０１１０２などの）ＨＴＭ識別子が定められる。このマッピングは、たとえば、所在地住所の場所（または緯度／経度が特定された場所）を適切なＨＴＭ識別子に対応させる予め規定されたルックアップテーブルで文書の所在地住所または緯度／経度の場所を調べることによって行なわれ得る。
【００３０】
文書についてさらに場所識別子が定められてもよい。特に、予め定められた範囲内の周囲領域に対応する場所識別子も定められ得る（ステップ４０３）。図５は、ステップ４０３の例示的な実現例を説明する図である。この例では、予め定められた範囲は丸５３０で図示される１マイルとして選択されると仮定する。グリッド５００は、各々の三角形領域が約１平方マイルを表わすメッシュレベルなどの特定のメッシュレベルのＨＴＭメッシュの一部を表わす。文書が三角形の地理的領域５１０の中の店舗５０５に関連付けられていると仮定する。丸５３０で図示されるように、領域５２０−１から５２０−１２は領域５１０から１マイルの範囲内に少なくとも部分的に入る。したがって、領域５１０の中心から約１マイル内の地理的領域は、領域５１０および５２０で規定される地理的領域を含む（図５に太字で例示）。
【００３１】
図４に戻って、検索エンジン１２５は、文書が文書の領域およびステップ４０３で識別された周囲領域に関連付けられている場所識別子を含むかのように各々の地理的に関連性のある文書をインデックス付けし得る（ステップ４０４）。図５の例では、たとえば、文書は、領域５１０および５２０−１から５２０−１２のすべてについてのＨＴＭ識別子がこの文書についてのインデックスに含まれるようにインデックス付けされ得る。１つの実施例では、場所識別子は、それらが元の文書テキストの一部ではないことを示す、データベース１３５中の特別なタグに関連付けられ得る。
【００３２】
図６Ａおよび図６Ｂは、図４に示される動作を用いてデータベース１３５でインデックス付けされ得る例示的な文書を説明する図である。図６Ａは、仮想のレストランである「ジノズピッツァ」の店舗一覧表６０５を例示する。検索エンジン１２５は、文書６０５のテキストならびに場所識別子および文書に関連付けられている潜在的に他の情報をインデックス付けし得る。この例では、カテゴリ情報６１０および場所識別子６１５も文書でインデックス付けされる。第１の場所識別子であるＨＴＭ領域Ｎ２０１３０１は、ジノズピッツァが位置する（たとえば、図５の例では領域５１０などの）特定の地理的領域を指し得る一方で、残余の場所識別子は、（たとえば、図５の例では領域５２０などの）Ｎ２０１３０１の周りの地理的領域を参照し得る。
【００３３】
図６Ｂは、ジノズピッツァのレビューを含む仮想のウェブページ６２０を例示する。ウェブページ６２０は、地理的に関連性があると判定され得る。というのもこれは主に、特定の地理的場所の店舗についてのものだからである。したがって、ウェブページ６２０もジノズピッツァと同じ地理的領域に関連付けられ得る。このように、場所識別子６２５は、店舗一覧表６０５に関連付けられ、店舗一覧表６０５でインデックス付けされる場所識別子６１５と同様の態様でウェブページ６２０に関連付けられ、ウェブページ６２０でインデックス付けされ得、これにより複数の場所識別子が文書５２０に関連付けられ得る。
【００３４】
説明の容易のため、図５、図６Ａおよび図６Ｂに示される例示的なＨＴＭ領域は、第５のレベルの子ノードを参照する。実際には、ローカル検索結果を与えるのに適切な区域を参照するＨＴＭ領域はより低いノードレベルにある傾向があろう。
【００３５】
図７は、図４に示される動作を用いた別の例示的な文書のインデックス付けを説明する図である。図７の文書は、１セットの場所識別子の代わりに２つの異なる予め定められた範囲に対応する２セットの場所識別子が定められたことを除き、図６Ａの文書と同一である。この例では、場所識別子７１０は、予め定められた範囲が１マイルである場合に定められる場所識別子のセットであり得る。場所識別子７２０として標識付けされる第２のセットの場所識別子は、５マイルなどの予め定められた範囲の別の値に基づいて選択され得る。したがって、７１０よりも多くの場所識別子７２０が存在し、場所識別子７１０は場所識別子７２０のサブセットである。場所識別子のセットの両者とも、独立して文書でインデックス付けされ得る。
【００３６】
１つの実現例では、セット７１０および７２０の場所識別子は、２セットの場所識別子に標識を付加することにより、インデックス付けの間に互いから区別され得る。この例では、標識「：１」を場所識別子７１０に付加してそれらが１マイル識別子に対応することを示し、標識「：５」を場所識別子７２０に付加してそれらが５マイル識別子に対応することを示す。
【００３７】
検索エンジンの動作
図８は、ローカル検索クエリーを処理する際の検索エンジン１２５の例示的な動作を説明するフローチャートである。検索エンジン１２５はユーザから検索クエリーを受け得る（ステップ８０１）。検索クエリーはローカルクエリーであり得、地理的区域に関連付けられ得る。たとえば、ユーザは「コーヒーショップ」を検索し、場所が「ニューヨーク州ポキプシー」地域であることを特定し得る。検索エンジン１２５は、ユーザが入力した領域を、（たとえばＨＴＭ識別子などの）データベース１３５に記憶される文書インデックスを作成する際に用いられる場所識別子のフォーマットを有する１つ以上の場所識別子に変換し得る。次に場所識別子が検索クエリーに付加され得る（ステップ８０２）。たとえば、検索クエリーが「コーヒーショップ」であり、対応の場所識別子がＮ０３０１３と定められる場合、修正された検索クエリーは「コーヒーショップＮ０３０１３」であり得る。異なる予め定められた範囲に基づいて異なるセットの場所識別子が識別された実現例では、修正された検索クエリーは、検索されるべき範囲に対応する場所識別子を含んでもよい。たとえば、修正された検索クエリー「コーヒーショップＮ０３０１３：５」は、５マイル半径内のローカル検索に用いられ得る。
【００３８】
次に、修正された検索クエリーを用いて、従来の態様で検索結果を得る（ステップ８０３）。たとえば、検索エンジン１２５は、文書インデックスから、検索クエリー中の用語を含む文書を識別し得る。これに代えてまたはこれに加えて、検索エンジン１２５は、検索用語の同義語を含む文書を識別し得る。修正された検索クエリーは検索領域の中心に対応する場所識別子を含み、地理的に関連性のある文書は予め定められた範囲内のすべての領域の場所識別子を含むようにインデックス付けされるので、検索結果は予め定められた検索範囲内の文書に限定される。このように、例示的な検索「コーヒーショップＮ０３０１３：５」についての検索結果は、ニューヨーク州ポキプシーから５マイル内の、コーヒーショップの店舗一覧表などのコーヒーショップに関連性のある文書であろう。
【００３９】
次に、ステップ８０３で得られた検索結果がユーザに返され得る（ステップ８０４）。１つの実現例では、結果は、ユーザクエリーに関連性がある店舗一覧表のランク付けされたリストとして表示され得る。各々の一覧表は、店舗一覧表に関連付けられている店舗についての住所情報、店舗の電話番号、店舗に関連付けられているより多くの情報へのリンク、店舗への行き方へのリンク、および／または店舗を参照する１つ以上のウェブ文書へのリンクなどの情報を含み得る。
【００４０】
図９は、選択された検索範囲が予め定められたインデックス付け範囲に一致しない場合にローカル検索クエリーを処理する際の検索エンジン１２５の例示的な動作を説明するフローチャートである。検索エンジン１２５はユーザから検索クエリーを受け得る（ステップ９０１）。検索クエリーはローカルクエリーであり得、地理的区域に関連付けられ、ユーザが検索したい範囲の指示を含み得る。たとえば、ユーザは「コーヒーショップ」を検索し、場所が「ニューヨーク州ポキプシー」地域であることを特定し、かつユーザが３マイルの検索半径を希望すると特定し得る。
【００４１】
ユーザが選んだ３マイル検索範囲がデータベース１３５中で具体的にインデックス付けされているものではないと仮定する。ユーザが選んだ範囲に最も近いがそれよりも大きくない予めインデックス付けされた範囲が定められ得る（ステップ９０２）。この例では、最も近い予めインデックス付けされた範囲が１マイルであると仮定する。すなわち、場所識別子のセットが１マイル範囲のインデックスに追加された。次に検索エンジン１２５は、検索に関連付けられている地理的区域から２マイル（３マイル−１マイル）内の領域のセットを探し出し得る（ステップ９０３）。図１０は、ステップ９０２および９０３を説明する例示的なＨＴＭグリッド１０００の図である。領域１０１０が検索に関連付けられている領域であり、内側の破線の丸が１マイル半径を表わし、外側の破線の丸が２マイル半径を表わすと仮定する。したがって、この例については、ステップ９０３で、検索エンジン１２５は外側の丸に含まれる領域のセットを探し出し得る。
【００４２】
次に検索クエリーは、ステップ９０３で識別された場所識別子を論理和演算として検索クエリーに付加することによって修正され得る（ステップ９０４）。元の検索クエリーが「コーヒーショップ」であった上記の例では、修正された検索クエリーは、「コーヒーショップ」プラス図１０の外側の破線の丸の中の三角形領域に対応するすべての場所識別子の論理和演算されたリストであり得る。次に修正された検索クエリーを用いて従来の態様で検索結果を得る。すなわち、ステップ９０２で定められた予めインデックス付けされた場所識別子に検索クエリーを適用する（ステップ９０５）。このように、以上の「コーヒーショップ」の検索は、予めインデックス付けされた１マイル場所識別子に適用され得る。
【００４３】
次に、ステップ９０５で得られた検索結果がユーザに返され得る（ステップ９０６）。１つの実現例では、結果は、ユーザクエリーに関連性のある店舗一覧表のランク付けされたリストとして表示され得る。
【００４４】
図９に示された技術の可能な代替的変形例として、多数の場所識別子で文書を予めインデックス付けする代わりに、文書に関連付けられている唯一の場所識別子で各文書をインデックス付けしてもよい。次に、範囲が全検索領域であるステップ９０３で行なわれたように、検索クエリーを作成してもよい。すなわち、クエリーは、検索範囲内のすべての場所識別子の論理和連結を含み得る。この変形例は、インデックスのサイズを低減し、クエリー時の領域サイズおよび形状を選択する際の一層の柔軟性を可能にし得るが、クエリーの複雑さを増大させてしまう。
【００４５】
例示的なユーザインターフェイス
図１１および図１２は、発明の原則に整合する実現例に従う、ユーザに提示され得るローカル検索ユーザインターフェイスの例示的な図である。図１１に示されるように、ユーザインターフェイスはローカル検索に関して提示され得る。ローカル検索ユーザインターフェイスはユーザが特定の場所の店舗一覧表を検索することを可能にし得る。ユーザの検索を支援するため、ユーザインターフェイスは、「何を」フィールドおよび「どこで」フィールドを設け得る。たとえば、ユーザは（たとえば「ピザハット」などの）店舗の名称または（たとえばピザレストランなどの）店舗の種類を「何を」フィールドに入力し得る。ユーザは、（たとえばニューヨーク州オールバニーなどの）場所の名前を「どこで」フィールドに入力し得る。この例について、ユーザがユーザインターフェイスの何をフィールドに「マタニティードレス」を、どこでフィールドに「バージニア州フェアファクス」を入力したと仮定する。
【００４６】
上で論じた態様で、検索エンジン１２５は、検索用語「マタニティードレス」および「バージニア州フェアファクス」に基づいて検索を行ない、「バージニア州フェアファクス」という場所の検索用語「マタニティードレス」に関する店舗に関連付けられている文書を識別し、検索結果のリストに識別された文書を含み得る。識別された文書は、「どこで」フィールドに入力された場所の推定中心から１５マイルのデフォルト領域などの特定の地理的領域に関連性のある文書から選択され得る。
【００４７】
図１２にさらに示されるように、ローカル検索ユーザインターフェイスは検索結果をユーザに提示し得る。ユーザは、範囲１２０５とは異なる検索範囲を選択することによって検索される領域を修正し得る。異なる範囲を選択することにより、選択された範囲を用いて別の検索を行ない得る。
【００４８】
むすび
ローカル検索エンジンは、各文書ごとに、地理的領域集合体をまとめて規定する複数の場所識別子をインデックス付けすることにより、地理的区域に関連性のある文書を効率的にインデックス付けする。インデックスを用いて個々の検索クエリに応答する際、検索クエリに場所識別子を追加するだけで地理的領域集合体を効率的に検索し得る。
【００４９】
当業者には、図で説明された実現例において、上述のような発明の局面をソフトウェア、ファームウェアおよびハードウェアの多くの異なる形態で実現し得ることが明らかであろう。本発明に整合する局面を実現するのに用いられる実際のソフトウェアコードまたは特別なコントロールハードウェアは本発明を限定するものではない。このように、特定のソフトウェアコードを参照せずに局面の動作および挙動を説明した。当業者ならば、本明細書中の説明に基づいて局面を実現するようにソフトウェアおよびコントロールハードウェアを設計できるであろうと理解される。
【００５０】
本発明の好ましい実施例の以上の説明は例示および説明を与えるが、網羅的になったり、または開示された厳密な形態に発明を限定したりすることを意図するものではない。上記教示に照らして修正例および変形例が可能であり、またはそれらは発明の実践から得られ得る。たとえば、上述の動作の多くは特定の順序で説明されたが、動作の多くは同時にまたは異なる順序で行なわれてもよい。
【００５１】
さらに、発明のある部分は、１つ以上の機能を果たす「エンジン」として説明された。エンジンは、特定用途向け集積回路もしくはフィールドプログラマブルゲートアレイなどのハードウェア、ソフトウェア、またはハードウェアとソフトウェアとの組合せを含み得る。
【００５２】
本願で用いられるいずれの要素、ステップまたは命令も、そのようなものであると明示的に説明されない場合は、本発明に不可欠または必須と解釈されてはならない。また、本明細書中で使用されるような冠詞「ａ」は１つ以上のものを潜在的に許容することが意図される。単一のものが意図される場合は、「１つの」という用語または同様の文言が用いられる。さらに、「基づいて」という語句は、他に明示的に記載されなければ、「少なくとも部分的に基づいて」を意味することが意図される。この発明の範囲は請求項およびその均等物によって規定される。
【図１】
2011238248.tif 000003
【図２】
2011238248.tif 000004
【図３Ａ】
2011238248.tif 000005
【図３Ｂ】
2011238248.tif 000006
【図４】
2011238248.tif 000007
【図５】
2011238248.tif 000008
【図６Ａ】
2011238248.tif 000009
【図６Ｂ】
2011238248.tif 000010
【図７】
2011238248.tif 000011
【図８】
2011238248.tif 000012
【図９】
2011238248.tif 000013
【図１０】
2011238248.tif 000014
【図１１】
2011238248.tif 000015
【図１２】
2011238248.tif 000016