(57)【要約】  場所分類子は、入力テキスト中のテキスト文字列に基づいて場所情報を生成する。場所情報は、入力テキストの潜在的な地理的関連性を規定する。場所情報を定める際、場所分類子は、入力テキスト中の少なくとも１つの文字列に関連付けられる少なくとも１つの地理関連性プロファイルを受け、少なくとも１つの地理関連性プロファイルから文書についての地理関連性プロファイル組合せを得て、地理関連性プロファイル組合せに基づいて入力テキストの地理的関連性を判断し得る。
2008536195.tif 000002
【特許請求の範囲】
【請求項１】
文書の地理的関連性を判断する方法であって、
前記文書の中の少なくとも１つの文字列に関連付けられている少なくとも１つの地理関連性プロファイルを受けるステップと、
前記少なくとも１つの地理関連性プロファイルから前記文書についての地理関連性プロファイル組合せを得るステップと、
前記地理関連性プロファイル組合せに基づいて前記文書の地理的関連性を定めるステップとを含む、方法。
【請求項２】
前記少なくとも１つの地理関連性プロファイルは複数の地理関連性プロファイルを含み、前記複数の地理関連性プロファイルの各々は、前記文字列のうち１つの出現を地理的領域に関連させるヒストグラムである、請求項１に記載の方法。
【請求項３】
前記地理関連性プロファイル組合せを得るステップは、前記複数のヒストグラムを掛け合わせるステップを含む、請求項２に記載の方法。
【請求項４】
前記地理関連性プロファイル組合せに基づいて前記文書の地理的関連性を判断するステップは、ピークについて前記地理関連性プロファイル組合せを分析するステップを含む、請求項１に記載の方法。
【請求項５】
少なくとも１つの地理関連性プロファイルを受けるステップは、前記文書を調べて、前記文書の中の文字列と地理関連性プロファイルが以前に生成された複数の文字列とを比較することによって前記少なくとも１つの文字列を探し出すステップを含む、請求項１に記載の方法。
【請求項６】
前記少なくとも１つの文字列は単一の用語の文字列である、請求項１に記載の方法。
【請求項７】
前記少なくとも１つの文字列は連語を含む、請求項１に記載の方法。
【請求項８】
前記文書はウェブページである、請求項１に記載の方法。
【請求項９】
前記文書は検索クエリーである、請求項１に記載の方法。
【請求項１０】
場所分類子であって、
入力テキストを受けるための手段と、
地理的に関連性があると以前判断された前記入力テキスト内の文字列を探し出すための手段と、
前記探し出された文字列について地理関連性プロファイルを検索するための手段と、
前記検索された地理関連性プロファイルに基づいて前記入力テキストが地理的に関連性があるか否かを判断するための手段とを含む、場所分類子。
【請求項１１】
前記検索された地理関連性プロファイルを組合せるための手段をさらに含む、請求項１０に記載の場所分類子。
【請求項１２】
プロセッサによる実行のためのプログラミング命令を含むコンピュータ読出可能媒体であって、
文書内の複数の文字列のそれぞれに関連付けられている複数の地理関連性プロファイルを受けるためのプログラミング命令を含み、前記地理関連性プロファイルは各々、地理的領域に対して前記文字列の地理的関連性を規定しており、さらに
前記複数の地理関連性プロファイルに基づいて前記文書の地理的関連性を判断するためのプログラミング命令を含む、コンピュータ読出可能媒体。
【請求項１３】
前記文書についての地理関連性プロファイル組合せを得るように前記複数の地理関連性プロファイルを組合せるためのプログラミング命令をさらに含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１４】
前記地理関連性プロファイルを組合せるための前記プログラミング命令は、前記複数の地理関連性プロファイルをともに掛け合わせるためのプログラミング命令を含む、請求項１３に記載のコンピュータ読出可能媒体。
【請求項１５】
前記文書の地理的関連性を判断するための前記プログラミング命令は、ピークについて前記地理関連性プロファイル組合せを分析するためのプログラミング命令をさらに含む、請求項１３に記載のコンピュータ読出可能媒体。
【請求項１６】
前記複数の地理関連性プロファイルはヒストグラムを含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１７】
前記文字列は単一の用語の文字列を含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１８】
前記文字列は連語を含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１９】
前記文書はウェブページである、請求項１２に記載のコンピュータ読出可能媒体。
【請求項２０】
前記文書は検索クエリーである、請求項１２に記載のコンピュータ読出可能媒体。
【請求項２１】
文字列の地理関連性プロファイルを生成するための方法であって、
トレーニングテキストの複数の部分を定めるステップを含み、トレーニングテキストの各々の部分は地理的領域に関連付けられており、さらに
トレーニングテキストの複数のセレクション中の文字列の出現を累積するステップと、
累積された前記文字列の前記出現に基づいてヒストグラムとして前記地理関連性プロファイルを生成するステップとを含む、方法。
【請求項２２】
前記ヒストグラムは前記文字列の前記出現を地理的領域に関連させる、請求項２１に記載の方法。
【請求項２３】
トレーニングテキストの複数の部分を定めるステップは、
複数の文書の中の既知の地理的シグナルを探し出すステップと、
前記既知の地理的シグナルを含む前記複数の文書の部分からトレーニングテキストの部分を選択するステップとを含む、請求項２１に記載の方法。
【請求項２４】
前記文書はウェブ文書である、請求項２１に記載の方法。
【請求項２５】
前記トレーニングテキスト内の地理的領域のグローバルな分布に基づいて、生成された前記地理関連性プロファイルを正規化するステップをさらに含む、請求項２１に記載の方法。
【請求項２６】
前記地理的領域は郵便番号で表わされる、請求項２１に記載の方法。
【請求項２７】
前記地理関連性プロファイルが統計的に関連性のあるピークを含む場合、前記生成された地理関連性プロファイルを将来の使用のために保存するステップをさらに含む、請求項２１に記載の方法。
【請求項２８】
前記文字列の出現を累積するステップは、前記文字列の周りのテキスト文脈が前記文字列の以前の出現の周りの前記テキスト文脈に一致する場合に前記文字列の出現を累積しないステップをさらに含む、請求項２１に記載の方法。
【請求項２９】
プロセッサと、
前記プロセッサに結合され、命令を含むコンピュータ読出可能メモリとを含み、前記コンピュータ読出可能メモリは、前記プロセッサによって実行されると、前記プロセッサに、
トレーニングテキストの複数の部分を定めさせ、前記トレーニングテキストの各々の部分は地理的領域に関連付けられており、さらに
トレーニングテキストの複数のセレクション中の文字列の出現を累積させ、かつ
累積された前記文字列の前記出現に基づいて地理的領域に対する前記文字列の前記地理的関連性を規定する地理関連性プロファイルを生成させる、装置。
【請求項３０】
文書を調べて、地理的関連性を有すると以前判断された文字列を探し出すステップと、
前記文字列に関連付けられている地理関連性文字列を受けるステップと、
受けた地理関連性プロファイルをともに掛け合わせることによって、受けた前記地理関連性プロファイルから前記文書についての地理関連性プロファイル組合せを得るステップと、
ピークについて前記地理関連性プロファイル組合せを分析するステップと、
前記地理関連性プロファイルの組合せ中にピークが存在するか否かに基づいて前記文書の地理的関連性を定めるステップとを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
背景
Ａ．発明の分野
本明細書中に記載されるシステムおよび方法は検索エンジンに関し、より特定的には、地理的領域に関連性があるものとしてテキストを分類するための技術に関する。
【背景技術】
【０００２】
Ｂ．関連技術の説明
ワールドワイドウェブ（「ウェブ」）は大量の情報を含んでいる。しかしながら、情報の所望の部分を探し出すことは困難であり得る。ウェブ上の情報量およびインターネット検索に不慣れな新しいユーザの数は急速に増加しているため、この問題は倍加している。
【０００３】
検索エンジンは、ユーザが関心のあるウェブページへのハイパーリンクを返そうと試みる。一般的に、検索エンジンによるユーザの関心の判断は、ユーザが入力する（検索クエリーと称される）検索用語に基づいている。検索エンジンの目標は、検索クエリーに基づき、ユーザに、（たとえばウェブページなどの）高品質の関連性ある結果へのリンクを提供することである。典型的に、検索エンジンは、検索クエリー中の用語を予め記憶されたウェブページのコーパスと一致させることによってこれを達成する。ユーザの検索用語を含むウェブページは「ヒット」であり、リンクとしてユーザに返される。
【０００４】
ユーザに返されるウェブページの関連性および品質を向上させようとして、検索エンジンは、最も関連性が高いおよび／または最も高品質のページが、ユーザに返されるヒットリストの一番上に来るようにヒットリストを並べ替えるよう試み得る。たとえば、検索エンジンは、各々のヒットにランクまたはスコアを割当て得る。ここでスコアとは、ウェブページの関連性または重要性に対応するように設計される。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ローカル検索エンジンは、特定の地理的領域内の関連のウェブページを返すよう試みる検索エンジンである。ローカル検索エンジンのために文書をインデックス付けする際は、文書または文書の部分を特定の地理的領域と適宜自動的に関連付けできることが望ましい。たとえば、ニューヨーク市のレストランについてのウェブページはニューヨーク市に関連付けられるべきである。多くの場合、地理的に特定的なウェブページは、所在地住所またはウェブページを地理的領域に明確に関連付ける他の地理的情報を含む。しかしながら他の場合、ウェブページは、特定の地理的領域に関連付けられ得るが、依然として部分的な所在地住所情報しか含まなかったり、または特定の地理的場所に関連付けられていることを容易に認識できないかもしれない他の用語を含んだりし得る。このためにウェブページに関連付けられている地理的領域を判断することが困難になっている。
【課題を解決するための手段】
【０００６】
発明の概要
発明の１つの局面は、文書の地理的関連性を判断する方法に向けられている。この方法は、文書の中の少なくとも１つの文字列に関連付けられている少なくとも１つの地理関連性プロファイルを受けるステップと、少なくとも１つの地理関連性プロファイルから文書についての地理関連性プロファイル組合せを得るステップと、地理関連性プロファイル組合せに基づいて文書の地理的関連性を判断するステップとを含む。
【０００７】
発明の別の局面は、プロセッサによる実行のためのプログラミング命令を含むコンピュータ読出可能媒体に向けられている。コンピュータ読出可能媒体は、文書の中のそれぞれの文字列に関連付けられている地理関連性プロファイルを受けるためのプログラミング命令を含む。地理関連性プロファイルは各々、地理的領域に対する文字列の地理的関連性を規定する。コンピュータ読出可能媒体は、地理関連性プロファイルに基づいて文書の地理的関連性を判断するためのプログラミング情報をさらに含む。
【０００８】
発明のさらに別の局面は、文字列についての地理関連性プロファイルを生成するための方法に向けられている。この方法は、その各々が地理的領域に関連付けられているトレーニングテキストの複数の部分を定めるステップと、トレーニングテキストの複数のセレクション中の文字列の出現を累積するステップと、累積された文字列の出現に基づいて地理関連性プロファイルをヒストグラムとして生成するステップとを含む。
【発明を実施するための最良の形態】
【０００９】
この明細書に組入れられかつその一部を構成する添付の図面は、この発明の実施例を説明し、その記載とともにこの発明を説明する。
【００１０】
詳細な説明
以下のこの発明の詳細な説明は添付の図面を参照する。詳細な説明はこの発明を限定するものではない。
【００１１】
概要
本明細書中では、入力テキストを特定の地理的領域に適宜自動的に分類する場所分類子を説明する。図１は、場所分類子１００を含む、この発明の局面に整合する一般的概念を説明する図である。場所分類子１００の動作の例として、カリフォルニア州マウンテンビューのカストロ通りの店舗を記載する、図１に示される例示的な文書などの入力文書を考える。文書は、湾岸地域のカストロ通りに存在するとして店舗を記載するが、完全な所在地住所、電話番号を具体的に含んでおらず、かつ明示的に「カリフォルニア州マウンテンビュー」と述べていないと仮定する。
【００１２】
場所分類子１００は、文書の中の連語「湾岸地域」および「カストロ通り」が地理的に有意義であると認識し得る。「湾岸地域」自体はカリフォルニア州のサンフランシスコ湾を取囲む区域を参照するのに頻繁に用いられるが、これはウィスコンシン州のグリーンベイ地域などの他の湾岸の場所を参照するのにも共通して用いられる。さらに、カストロ通り自体はよくある通り名であり得る。場所分類子１００は、「湾岸地域」および「カストロ通り」という語句の両者の出現が、文書がカリフォルニア州マウンテンビューに位置するカストロ通りに属することを示す可能性があると認識することによって、これらの語句の個々の地理的曖昧さを解決し得る。
【００１３】
次に、場所分類子１００は、文書で言及されている店舗の潜在的対応物として、完全な住所または郵便番号９４０４３、カリフォルニア州マウンテンビューなどの他の場所識別子を生成し得る。
【００１４】
例示的なネットワークの概要
図２は、この発明の原則に整合するシステムおよび方法を実現し得るネットワーク２００の例示的な図である。ネットワーク２００は、ネットワーク２４０を介してサーバ２２０に接続されるクライアント２１０を含み得る。ネットワーク２４０は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、公衆電話交換網（ＰＳＴＮ）などの電話網、イントラネット、インターネット、またはネットワークの組合せを含み得る。簡略化のため、２つのクライアント２１０および１つのサーバ２２０がネット
ワーク２４０に接続されて図示されている。実際には、より多くのクライアントおよび／またはサーバが存在し得る。また、いくつかの例では、クライアントがサーバの機能を果たし、サーバがクライアントの機能を果たすことがある。
【００１５】
クライアント２１０は、無線電話、パーソナルコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）、ラップトップ、もしくは別のタイプの電算もしくは通信装置などのデバイス、これらのデバイスのうち１つで実行されるスレッドもしくはプロセス、および／またはこれらのデバイスのうち１つによって実行可能なオブジェクトを含み得る。クライアント２１０およびサーバ２２０は、有線、無線または光接続を介してネットワーク２４０に接続し得る。
【００１６】
サーバ２２０は、クライアント２１０が利用可能な検索エンジン２２５を含み得る。検索エンジン２２５は、クエリーに基づく文書検索エンジンなどの検索エンジンであり得る。いくつかの実現例では、検索エンジン２２５は、地理的領域にローカルな結果を返すように特に設計され得る。検索エンジン２２５は場所分類子１００を含み得る。場所分類子１００は、部分的な住所または地理的関連性を有する用語／語句を含み得、入力文書に対応する地理的区域に対応する１つ以上の場所識別子を生成し得る入力データを受ける。たとえば、検索エンジン２２５は、場所分類子１００を用いてウェブページなどの文書を地理的区域に関連付けたり、またはユーザの検索クエリーが特定の地理的場所に関するか否かを判断したりし得る。
【００１７】
本明細書中で使用されるような文書という用語は、いずれの機械読取可能なおよび機械上に記憶可能なワークプロダクトも含むと広く解釈されるべきである。文書は、電子メール、検索クエリー、ファイル、ファイルの組合せ、他のファイルへの埋込リンクを備える１つ以上のファイル、ニュースグループへの投稿などであり得る。インターネットの文脈では、通常の文書がウェブページである。ウェブページはしばしばコンテンツを含み、（メタ情報、ハイパーリンクなどの）埋込情報および／または（JavaScriptなどの）埋込命令を含み得る。
【００１８】
例示的なクライアント／サーバアーキテクチャ
図３は、発明の原則に整合する実現例に従う、コンピュータデバイス３００と称されるクライアント２１０またはサーバ２２０の例示的な図である。コンピュータデバイス３００は、バス３１０、プロセッサ３２０、メインメモリ３３０、読出専用メモリ（ＲＯＭ）３４０、記憶装置３５０、入力装置３６０、出力装置３７０および通信インターフェイス３８０を含み得る。バス３１０は、コンピュータデバイス３００の構成要素間の通信を可能にする経路を含み得る。
【００１９】
プロセッサ３２０は、命令を解釈しかつ実行し得る、いずれの種類の従来のプロセッサ、マイクロプロセッサまたは処理ロジックも含み得る。メインメモリ３３０は、ランダムアクセスメモリ（ＲＡＭ）、またはプロセッサ３２０による実行のための命令および情報を記憶する別のタイプの動的記憶装置を含み得る。ＲＯＭ３４０は、従来のＲＯＭデバイス、またはプロセッサ３２０が使用するための命令および静的情報を記憶する別のタイプの静的記憶装置を含み得る。記憶装置３５０は磁気的および／または光学的記録媒体ならびにその対応のドライブを含み得る。
【００２０】
入力装置３６０は、キーボード、マウス、ペン、音声認識および／またはバイオメトリックメカニズムなどの、ユーザがコンピュータデバイス３００に情報を入力できるようにする従来のメカニズムを含み得る。出力装置３７０は、ディスプレイ、プリンタ、スピーカなどを含む、情報をユーザに出力する従来のメカニズムを含み得る。通信インターフェイス３８０は、コンピュータデバイス３００が他のデバイスおよび／またはシステムと通
信できるようにするいずれのトランシーバ状のメカニズムも含み得る。たとえば、通信インターフェイス３８０は、ネットワーク２４０などのネットワークを介して別のデバイスまたはシステムと通信するためのメカニズムを含み得る。
【００２１】
発明の原則に整合するサーバ２２０は、検索エンジン２２５および／または場所分類子エンジン１００を通じて、ある検索または文書検索関連の動作を行なう。検索エンジン２２５および／または場所分類子エンジン１００は、メモリ３３０などのコンピュータ読出可能媒体に記憶され得る。コンピュータ読出可能媒体は、１つ以上の物理的または論理的メモリデバイスおよび／または搬送波として規定され得る。
【００２２】
検索エンジン２２５を規定するソフトウェア命令は、通信インターフェイス３８０を介してデータ記憶装置３５０などの別のコンピュータ読出可能媒体から、または別のデバイスからメモリ３３０に読込まれ得る。メモリ３３０に含まれるソフトウェア命令は、後述される処理をプロセッサ３２０に行なわせる。これに代えて、配線で接続された回路構成をソフトウェア命令の代わりにまたはこれと組合せて用いて、本発明に整合する処理を実行してもよい。このように、この発明の原則に整合する実現例は、ハードウェア回路構成とソフトウェアとのいずれの特定の組合せに限定されるものでもない。
【００２３】
場所分類子１００のトレーニング
場所分類子１００は、入力文書または文書の部分について地理的場所情報を自動的に生成し得る。場所分類子１００が地理的場所情報を生成できるようになる前に、これは多数のトレーニング文書に対してトレーニングされ得る。１つの実現例では、文書はウェブページであり得る。
【００２４】
図４は、場所分類子１００をトレーニングするための例示的な手順を説明するフローチャートである。
【００２５】
場所分類子１００は、多数のウェブ文書などの多数の文書に対してトレーニングされ得る。場所分類子エンジン１００は、文書のうちの第１のものを検索し（ステップ４０１）、文書内の既知の地理的シグナルを探し出す（ステップ４０２）ことによってトレーニングを開始し得る。既知の地理的シグナルは、たとえば、地理的場所を明確に特定する完全な住所を含み得る。地理的シグナルは、たとえば、住所の一般的な形態にあるテキストの部分を探すパターンマッチング技術によって探し出され得る。たとえば、場所分類子エンジン１００は、州名または州の略号の近くに位置する５桁の整数としての郵便番号、および「通り」、「通」、「大通り」などの語を含む文字列を後に従える一連の数字としての通り名を探し得る。このように、場所分類子１００は、地理的住所を明確に参照するテキストの部分として既知の地理的シグナルを探し出し得る。
【００２６】
図５は、２つの地理的シグナルが存在する例示的な文書５００を説明する図である。示されるように、文書５００は、第１の地理的シグナル５０５、テキストの段落５１０、第２の地理的シグナル５１５、および第２のテキストの段落５２０を含む。
【００２７】
第１の地理的シグナルであるシグナル５０５は、「コーヒータイム」という仮想のコーヒーショップについてのものであり、標準的な所在地住所としてコーヒータイムの場所を特定する。場所分類子１００は、住所の構造ならびに／または郵便番号、通り名および町の名前がすべてカリフォルニア州の既知の場所と整合することに基づいて、この住所が有効な住所であると認識し得る。同様に、場所分類子１００は、地理的シグナル５１５も物理的場所に明確に関連付けられている有効な住所を表わすことを認識し得る。なお、当業者は、手作業での文書の分類など、文書が地理的場所に関連付けられているか否かを判断するための他の技術を用い得ることを認識するであろう。
【００２８】
ステップ４０２で有効な地理的シグナルに関連付けられていると判断される文書は、既知の地理的領域に対応する文書と考えられる。現在処理中の文書が特定の地理的領域に関連付けられていないウェブ文書などの文書ではない場合、次の文書が処理され得る（ステップ４０３および４０５）。しかしながら、有効な地理的シグナルを含む文書については、場所分類子１００は、発見された地理的シグナルに関連付けられているトレーニングテキストとして用いるべき文書からテキストを選択し得る（ステップ４０４）。
【００２９】
文書に関連付けられているトレーニングテキストとしてステップ４０４で選択されたテキストは、多数の異なる態様で選択され得る。たとえば、各々の地理的シグナルの周りの固定ウインドウ（たとえば１００語のウインドウ）がトレーニングテキストとして選択され得る。他の実現例では、文書全体が選択され得る。さらに他の実現例では、複数の地理的シグナルを含む文書が、文書中の目に見える切れ目およびセグメントから取ったトレーニングテキストに基づいてセグメント化され得る。図５に示す文書については、たとえば、段落５１０は住所シグナル５０５に関連付けられ得、段落５２０は住所シグナル５１５に関連付けられ得る。
【００３０】
ステップ４０２−４０５は、トレーニング文書として用いるべき文書のコーパス中の各々の文書について繰返され得る（ステップ４０６）。一般的に、ステップ４０１−４０５は、多数（通常は大多数）の既知の場所の各々がテキストに関連付けられているトレーニングデータを生成するように働く。図６は、ステップ４０２−４０５で生成される例示的なトレーニングデータを説明する表の一部の図である。表６００は、多数の場所識別子フィールド６０５および対応のテキスト部分６１０を含み得る。識別子フィールド６０５は地理的シグナルに基づき得、テキスト部分６１０は各々の地理的シグナルごとに選択されたテキストを含み得る。このように、各々の探し出された地理的シグナルは表６００の中のエントリに対応し得る。
【００３１】
１つの実現例では、場所識別子フィールド６０５は、ステップ４０２で識別された地理的シグナルに対応する郵便番号を含み得る。郵便番号は、地理的場所の識別子として用いるのに特に有用である。なぜなら、番号が互いに近い郵便番号は、地理的に互いに近い場所に対応する傾向があるからである。しかしながら、郵便番号以外の場所識別子も用いてもよい。
【００３２】
表６００には２つのエントリが特に示される。これらの２つのエントリは文書５００からの２つの地理的シグナルに対応する。第１のエントリは探し出された識別子として郵便番号９４０４０を含み、選択されたテキストとして段落５１０を含む。第２のエントリは探し出された識別子として郵便番号９４０４１を含み、選択されたテキストとして段落５２０を含む。
【００３３】
表６００中のトレーニングデータは、本明細書中で、トレーニングの残余（すなわちステップ４０７−４１０）と同じプロセスで場所分類子１００によって生成されると説明されているが、トレーニングデータは前もって、または別の構成要素もしくはデバイスによって生成されてもよい。
【００３４】
この発明の１つの局面に従うと、場所分類子１００は、部分的に、地理的シグナルの近傍にある文書中のテキストが地理的シグナルに関する用語または語句を用いる方にバイアスされるという前提で動作する。ステップ４０１−４０６で得られるトレーニングデータは、ステップ４０７−４１０を参照して以下に説明されるように、場所分類子１００によってさらに処理されて、ある用語／語句についての地理関連性プロファイルを得ることができる。
【００３５】
場所分類子１００は、選択用語または語句について、用語／語句が出現する場所識別子に対するテキストセレクション６１０中の（テキスト文字列または本明細書中では単に文字列とも称される）用語／語句のすべての出現を累積する（ステップ４０７）ことによって開始し得る。換言すると、場所分類子１００は、用語／語句の出現数を場所識別子に関連させるヒストグラムを生成し得る。ヒストグラムは、本明細書中では、用語／語句の地理関連性プロファイルとも称される。
【００３６】
図７Ａは、連語「キャピトルヒル」についての例示的なヒストグラム７００を説明する図である。示されるように、ヒストグラムは３つの顕著なピーク、すなわちワシントンＤＣの「キャピトルヒル」地域に対応する郵便番号２０５１５の近傍に中心を置く大きなピーク、カリフォルニア州サクラメントの「キャピトルヒル」地域に対応する郵便番号９５８１４の近傍に中心を置く比較的小さなピーク、およびワシントン州シアトルの「キャピトルヒル」地域に対応する郵便番号９８１０４の近傍に中心を置く中程度のピークを含む。テキストセレクション６１０は「キャピトルヒル」への数多くの参照を潜在的に含み、その多くはワシントンＤＣ、サクラメントまたはシアトルの近傍ではない区域に連付けられたが、ヒストグラム７００は、これらの３つの場所のうち１つを参照する際に「キャピトルヒル」が用いられる傾向に全般的にあることを図示する。最大のピークに対応するワシントンＤＣは、「キャピトルヒル」という語句を用いる人が意図する可能性が最も高い地理的領域と解釈することができる。
【００３７】
図７Ｂは、連語「湾岸地域」についての別の例示的なヒストグラムであるヒストグラム７１０を説明する図である。ヒストグラム７１０は２つのピーク、すなわちウィスコンシン州のグリーンベイ地域付近に中心を置く小さい方と、カリフォルニア州サンフランシスコの湾岸地域を規定する大きい方のピークとを含む。
【００３８】
場所分類子１００は、テキストセレクション６１０に出現する用語／語句のうちいくつかまたはすべてに対してステップ４０７を実行し得る。１つの実現例では、場所分類子１００は、テキスト６１０に出現するすべての連語（２語の語句）についてのヒストグラムを生成し得る。他の実現例では、ヒストグラムはより長い語句または単一の用語についても生成され得る。
【００３９】
用語／語句のある出現は、用語／語句の出現を累積する際には無視され得る。いくつかの定型的表現はトレーニング文書のセット中に頻繁に出現し得る。しかし定型的表現は地理的関連性を判断するのに必ずしも関連性があるとは限らない。したがって、いくつかの実現例では、選択用語／語句の左側および／または右側の用語も調べて、これらの用語が用語／語句の左側または右側の用語の以前の事例とは異なっている場合にしか用語／語句を累積しない。これにより、用語／語句が正当な新しい文脈で出現していない場合は、これは無視され得る。
【００４０】
場所分類子１００は次に、地理的に関連性のある用語／語句に対応する生成されたヒストグラムを選択し、記憶し得る（ステップ４０８および４０９）。記憶されたヒストグラムは用語／語句についての地理関連性プロファイルとして働く。ステップ４０７でヒストグラムが生成される用語／語句の多くは、地理的に関連性がないかもしれない。図７Ｃは、連語「ライブブックマーク」についての例示的なヒストグラム７２０の図である。この語句は地理的な関連性がなく、したがってヒストグラムは比較的平らである。しかしながら、ヒストグラム７００および７１０は、これらの用語／語句が特定の地理的場所に関連性があり得ることを示す統計的に有意義な山を含む。当業者は、ヒストグラムが統計的に有意義なピークを含むか否かを判断するのに多数の公知の技術を用い得ることを認識するであろう。
【００４１】
テキストセレクション６１０中の多数の用語／語句についてステップ４０８および４０９を繰返してもよい（ステップ４１０）。１つの実現例では、場所分類子１００は、テキストセレクション６１０中に存在するあらゆる連語の地理的関連性を調べ得る。他の実現例では、地理的関連性について単一の用語を調べたり、または３つ以上の用語を有する語句を調べたりし得る。
【００４２】
図４に示されるトレーニングの結果、場所分類子１００は、多数（潜在的には大多数）の用語／語句およびそれらの対応の地理関連性プロファイルを記憶し得る。図８は、例示的な用語／語句およびそれらの対応の地理関連性プロファイルを含む表８００を概念的に説明する図である。
【００４３】
１つの実現例では、ステップ４０９で記憶される地理関連性プロファイルは、トレーニングデータ中の郵便番号のグローバルな分布に基づいて正規化され得る。このように、トレーニングデータ中で頻繁に言及される領域が地理関連性プロファイルの中で強調され過ぎることはない。
【００４４】
場所分類子１００の動作
図９は、入力文書について潜在的に関連性のある地理的区域を判断する際の場所分類子１００の例示的な動作を図示するフローチャートである。
【００４５】
場所分類子１００は、入力文書を受ける（ステップ９０１）ことによって開始し得る。一般的に、入力文書は、場所に対して潜在的に曖昧な参照を含むものであろう。たとえば、入力文書は、検索クエリーなどの比較的短いテキストの部分、またはウェブ文書などのテキストのより長いブロックであり得る。用語／語句は、表８００に記憶される用語／語句に対応する入力文書の中から探し出され得る（ステップ９０２）。換言すると、地理的関連性を有すると以前判断された用語／語句が識別される。
【００４６】
次に、識別された用語／語句の各々についての地理関連性プロファイルを組合せて、入力文書についての結果的な地理関連性プロファイルを生成する（ステップ９０３）。１つの実現例では、地理関連性プロファイルは、ステップ９０２で識別された地理関連性プロファイルの各々を掛け合わせることによって組合され得る。すなわち、郵便番号ごとに、各々のヒストグラムの値をともに掛け合わせて、結果的に得られるヒストグラム中のその郵便番号の値を得ることができる。図１０Ａ−図１０Ｃは、複数の地理関連性プロファイルを組合せてプロファイル組合せを得ることを説明する。この例では、入力文書が表８００中に存在する２つの連語を含む１ページのテキストである（すなわち、入力ページが２つの地理的に関連性のある用語／語句を含む）と仮定する。２つの連語は「カストロ通り」および「湾岸地域」である。カストロ通りの地理関連性プロファイルは図１０Ａに示され、湾岸地域の地理関連性プロファイルは図１０Ｂに示される。図１０Ｃは地理関連性プロファイルの組合せを説明する。示されるように、図１０Ａおよび図１０Ｂのヒストグラムは両者とも複数のピークを含むが、組合されると、ピークは、両者のプロファイルが地理的関連性を示す区域を除いて互いに打消し合う傾向にある。これにより、図１０Ｃの地理関連性プロファイルの組合せは、「カストロ通り」および「湾岸地域」への参照が北カリフォルニア湾岸地域に位置するカストロ通りへの参照である可能性が非常に高いことを正しく示す。
【００４７】
図１０Ｃに示される例示的なプロファイルなどの地理関連性プロファイルの組合せに基づき、場所分類子１００は、１つ以上の地理的領域に対する入力文書の潜在的関連性を規定する出力情報を生成し得る（ステップ９０４）。出力情報は一般的に、ピークについて地理関連性プロファイル組合せを調べることによって得られ得る。図１０Ｃの例では、た
とえば、出力情報は、北カリフォルニアのカストロ通りを含む領域の郵便番号を含み得る。いくつかの実現例では、郵便番号は、郵便番号で規定される区域が正しいという可能性または確実性に関する値にも関連付けられ得る。
【００４８】
１つの実現例では、ステップ９０１で受ける文書は、ウェブページ、検索クエリーまたは他のソースから取られる部分的住所などの部分的住所であり得る。次に出力情報を用いて部分的住所を明確にし得る。たとえば、町または州を含まない文書中に「カストロ通り６５０番地」などの住所が識別される場合、住所それ自体は完全な住所ではない。しかしながら、場所分類子１００が、文書が郵便番号９４０４３のマウンテンビューに関連性があると結論付ければ、住所は明確になり、正確な地理的場所（緯度／経度）になり得る。
【００４９】
例示的な実現例
図１１は、検索エンジンの文脈で実現される場所分類子１００の例示的な実現例を説明する図である。多数のユーザ１１０５がインターネットなどのネットワーク１１１５を介して検索エンジン１１１０に接続し得る。検索エンジン１１１０は、ユーザがある地理的領域への適用を意図するユーザクエリーに関する、データベース１１２０からのランク付けされた文書のセットへのリンクを返すローカル検索エンジンであり得る。
【００５０】
場所分類子１００は、データベース１１２０中の文書の（もしあれば）地理的関連性を判断する際に検索エンジン１１１０を支援し得る。特に、場所分類子１００は、そうしなければ特定の地理的区域に関連付けられているとははっきりと識別できない文書または文書の一部の各々を地理的に分類し得る。次にこの地理的分類情報を、検索エンジン１１１０がユーザ検索クエリーへの応答の際に用い得る対応の文書とともに、場所識別子としてデータベース１１２０に記憶し得る。
【００５１】
別の可能な例示的な実現例では、場所分類子１００は、ユーザ１１０５から受けた検索クエリー上で動作し得る。このように、場所分類子１００は、検索クエリーに属する地理的関連性情報を与え得る。関連性ある結果をユーザに返す際に、この情報を用いて検索エンジン１１１０を支援し得る。
【００５２】
むすび
上述のように、場所分類子は、入力テキスト中の用語／語句に基づいて場所情報を生成する。用語／語句は、通常ならば地理的に曖昧であると考えられる用語／語句を含み得る。
【００５３】
当業者には、図で説明された実現例において、上述のような発明の局面をソフトウェア、ファームウェアおよびハードウェアの多くの異なる形態で実現し得ることが明らかであろう。本発明に整合する局面を実現するのに用いられる実際のソフトウェアコードまたは特別なコントロールハードウェアは本発明を限定するものではない。このように、特定のソフトウェアコードを参照せずに局面の動作および挙動を説明した。当業者ならば、本明細書中の説明に基づいて局面を実現するようにソフトウェアおよびコントロールハードウェアを設計できるであろうと理解される。
【００５４】
本発明の好ましい実施例の以上の説明は例示および説明を与えるが、網羅的になったり、または開示された厳密な形態に発明を限定したりすることを意図するものではない。上記教示に照らして修正例および変形例が可能であり、またはそれらは発明の実践から得られ得る。たとえば、上述の動作の多くは特定の順序で説明されたが、動作の多くは同時にまたは異なる順序で行なわれてもよい。さらに、一般的に検索エンジンの一部として場所分類子を説明したが、検索エンジンはより一般的には場所分類子とは別個のものであり得ることを理解されたい。
【００５５】
本願で用いられるいずれの要素、ステップまたは命令も、そのようなものであると明示的に説明されない場合は、本発明に不可欠または必須と解釈されてはならない。また、本明細書中で使用されるような冠詞「ａ」は１つ以上のものを潜在的に許容することが意図される。単一のものが意図される場合は、「１つの」という用語または同様の文言が用いられる。さらに、「基づいて」という語句は、他に明示的に記載されなければ、「少なくとも部分的に基づいて」を意味することが意図される。この発明の範囲は請求項およびその均等物によって規定される。
【図面の簡単な説明】
【００５６】
【図１】発明の局面に整合する一般的概念を説明する図である。
【図２】発明の原則に整合するシステムおよび方法を実現し得るネットワークの例示的な図である。
【図３】図２に示されるクライアントまたはサーバの例示的な図である。
【図４】図１および図２に示される場所分類子エンジンをトレーニングするための例示的な手順を説明するフローチャートの図である。
【図５】２つの地理的シグナルが存在する例示的な文書を説明する図である。
【図６】トレーニングデータを説明する例示的な表の一部の図である。
【図７Ａ】用語／語句についての例示的な地理関連性プロファイルを説明する図である。
【図７Ｂ】用語／語句についての例示的な地理関連性プロファイルを説明する図である。
【図７Ｃ】用語／語句についての例示的な地理関連性プロファイルを説明する図である。
【図８】例示的な用語／語句およびそれらの対応の地理関連性プロファイルを含む表を概念的に説明する図である。
【図９】入力文書について、潜在的に関連性のある地理的区域を定める際の場所分類子の例示的な動作を説明するフローチャートの図である。
【図１０Ａ】複数の地理関連性プロファイルを組合わせてプロファイル組合せを得ることを説明する図である。
【図１０Ｂ】複数の地理関連性プロファイルを組合わせてプロファイル組合せを得ることを説明する図である。
【図１０Ｃ】複数の地理関連性プロファイルを組合わせてプロファイル組合せを得ることを説明する図である。
【図１１】検索エンジンの文脈で実現される場所分類子の例示的な実現例を説明する図である。
【図１】
2008536195.tif 000003
【図２】
2008536195.tif 000004
【図３】
2008536195.tif 000005
【図４】
2008536195.tif 000006
【図５】
2008536195.tif 000007
【図６】
2008536195.tif 000008
【図７Ａ】
2008536195.tif 000009
【図７Ｂ】
2008536195.tif 000010
【図７Ｃ】
2008536195.tif 000011
【図８】
2008536195.tif 000012
【図９】
2008536195.tif 000013
【図１０Ａ】
2008536195.tif 000014
【図１０Ｂ】
2008536195.tif 000015
【図１０Ｃ】
2008536195.tif 000016
【図１１】
2008536195.tif 000017
【手続補正書】
【提出日】平成19年8月28日(2007.8.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
文書の地理的関連性を判断する方法であって、
前記文書の中の複数のそれぞれの文字列に関連付けられている複数の地理関連性プロファイルを識別するステップを含み、各々の地理関連性プロファイルは、文字列の出現を地理的領域に関連させ、さらに
前記複数の地理関連性プロファイルから前記文書についての地理関連性プロファイル組合せを得るステップと、
前記地理関連性プロファイル組合せに基づいて前記文書に関連性のある地理的領域を定めるステップとを含む、方法。
【請求項２】
前記複数の地理関連性プロファイルの各々は、文字列の出現を地理的領域に関連させるヒストグラムである、請求項１に記載の方法。
【請求項３】
前記地理関連性プロファイル組合せを得るステップは、前記複数のヒストグラムを掛け合わせるステップを含む、請求項２に記載の方法。
【請求項４】
前記地理関連性プロファイル組合せに基づいて前記文書の地理的関連性を判断するステップは、ピークについて前記地理関連性プロファイル組合せを分析するステップを含む、請求項１に記載の方法。
【請求項５】
前記複数の地理関連性プロファイルを受けるステップは、前記文書を調べて、前記文書の中の文字列と地理関連性プロファイルが以前に生成された複数の文字列とを比較することによって前記複数のそれぞれの文字列を探し出すステップを含む、請求項１に記載の方法。
【請求項６】
前記複数のそれぞれの文字列は単一の用語の文字列を含む、請求項１に記載の方法。
【請求項７】
前記複数のそれぞれの文字列は連語を含む、請求項１に記載の方法。
【請求項８】
前記文書はウェブページである、請求項１に記載の方法。
【請求項９】
前記文書は検索クエリーである、請求項１に記載の方法。
【請求項１０】
場所分類子であって、
入力テキストを受けるための手段と、
地理的に関連性があると以前判断された前記入力テキスト内の文字列を探し出すための手段と、
前記探し出された文字列について地理関連性プロファイルを検索するための手段とを含み、各々の地理関連性プロファイルは、それぞれの文字列の出現を地理的領域に関連させ、さらに
前記検索された地理関連性プロファイルに基づいて前記入力テキストが地理的に関連性があるか否かを判断するための手段とを含む、場所分類子。
【請求項１１】
前記検索された地理関連性プロファイルを組合せるための手段をさらに含む、請求項１０に記載の場所分類子。
【請求項１２】
プロセッサによる実行のためのプログラミング命令を含むコンピュータ読出可能媒体であって、
文書内の複数の文字列のそれぞれに関連付けられている複数の地理関連性プロファイルを受けるためのプログラミング命令を含み、前記地理関連性プロファイルは各々、地理的領域に対する前記文字列の地理的関連性を規定しており、さらに
地理関連性プロファイルの組合せを得るように前記複数の地理関連性プロファイルを組合わせるためのプログラミング命令と、
前記地理関連性プロファイルの組合せに基づいて前記文書に関連性のある地理的領域を定めるためのプログラミング命令とを含む、コンピュータ読出可能媒体。
【請求項１３】
前記地理関連性プロファイルを組合せるための前記プログラミング命令は、前記複数の地理関連性プロファイルをともに掛け合わせるためのプログラミング命令を含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１４】
前記文書の地理的関連性を判断するための前記プログラミング命令は、ピークについて前記地理関連性プロファイル組合せを分析するためのプログラミング命令をさらに含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１５】
前記複数の地理関連性プロファイルはヒストグラムを含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１６】
前記文字列は単一の用語の文字列を含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１７】
前記文字列は連語を含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１８】
前記文書はウェブページである、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１９】
前記文書は検索クエリーである、請求項１２に記載のコンピュータ読出可能媒体。
【請求項２０】
文字列の地理関連性プロファイルを生成するための方法であって、
トレーニングテキストの複数の部分を定めるステップを含み、トレーニングテキストの各々の部分は地理的領域に関連付けられており、さらに
トレーニングテキストの複数のセレクション中の前記文字列の出現を累積するステップと、
累積された前記文字列の前記出現に基づいてヒストグラムとして前記地理関連性プロファイルを生成するステップとを含み、前記ヒストグラムは、前記文字列の前記出現を地理的領域に関連させる、方法。
【請求項２１】
トレーニングテキストの複数の部分を定めるステップは、
複数の文書の中の既知の地理的シグナルを探し出すステップと、
前記既知の地理的シグナルを含む前記複数の文書の部分からトレーニングテキストの部分を選択するステップとを含む、請求項２０に記載の方法。
【請求項２２】
前記文書はウェブ文書である、請求項２０に記載の方法。
【請求項２３】
前記トレーニングテキスト内の地理的領域のグローバルな分布に基づいて、生成された前記地理関連性プロファイルを正規化するステップをさらに含む、請求項２０に記載の方法。
【請求項２４】
前記地理的領域は郵便番号で表わされる、請求項２０に記載の方法。
【請求項２５】
前記地理関連性プロファイルが統計的に関連性のあるピークを含む場合、前記生成された地理関連性プロファイルを将来の使用のために保存するステップをさらに含む、請求項２０に記載の方法。
【請求項２６】
前記文字列の出現を累積するステップは、前記文字列の周りのテキスト文脈が前記文字列の以前の出現の周りの前記テキスト文脈に一致する場合に前記文字列の出現を累積しないステップをさらに含む、請求項２０に記載の方法。
【請求項２７】
プロセッサと、
前記プロセッサに結合され、命令を含むコンピュータ読出可能メモリとを含み、前記コンピュータ読出可能メモリは、前記プロセッサによって実行されると、前記プロセッサに、
トレーニングテキストの複数の部分を定めさせ、前記トレーニングテキストの各々の部分は地理的領域に関連付けられており、さらに
トレーニングテキストの複数のセレクション中の文字列の出現を累積させ、かつ
累積された前記文字列の前記出現に基づいて地理的領域に対する前記文字列の前記地理的関連性を規定する地理関連性プロファイルを生成させる、装置。
【請求項２８】
文書を調べて、地理的関連性を有すると以前判断された文字列を探し出すステップと、
前記文字列に関連付けられている地理関連性プロファイルを受けるステップとを含み、各々の地理関連性プロファイルは、文字列の出現を地理的領域に関連させ、さらに
受けた前記地理関連性プロファイルをともに掛け合わせることによって、受けた前記地理関連性プロファイルから前記文書についての地理関連性プロファイル組合せを得るステップと、
ピークについて前記地理関連性プロファイル組合せを分析するステップと、
前記地理関連性プロファイルの組合せ中にピークが存在するか否かに基づいて前記文書に関連性のある地理的領域を定めるステップとを含む、方法。
【国際調査報告】
2008536195.tif 000018
2008536195.tif 000019
2008536195.tif 000020