(57)【要約】  電子地図及びデータベースと共に使用するための地域索引が提示される。地理データベース内の各地理的特徴は、種々の地域名供給元からの地域名に関連付けられる。地域名の文脈依存トークン化、標準化、最適化及びマッチングは、重複する地域名及び異なる地域名を削除する一方で、有意味に異なる名称を保存する。地域名テーブルは各地域名の構文解析された表現及び他の関連情報を含み、索引化用主トークンは識別される。主供給元マスクは、本方法において使用される各地域名供給元にビットを割り当てることにより作成される。個別の供給元マスクは地域名に関連付けられる地理特徴毎に格納され、地域が見つけられる各供給元に対してビットが設定される。各地理特徴に関連付けられる地域名は、所定のアプリケーションにおける使用に対する普及度の順序で地理特徴のテーブル内に索引化される。
2009537049.tif 000002
【特許請求の範囲】
【請求項１】
記憶媒体に格納可能な地理データベースの地域索引であって、
地理データベース内の少なくとも１つの地理特徴に対するポインタと、
前記少なくとも１つの地理特徴に関連付けられる１つ以上の地域名のセットとを備え、
前記１つ以上の地域名は、１つ以上の地域名供給元から選択され、対象のアプリケーションに対する、前記１つ以上の地域名の慣用的な使用における普及度に基づく優先順位により配列されることを特徴とする索引。
【請求項２】
地理特徴は、街路、街路セグメント、街路セグメントエッジ、ブロック面、目印、州立公園、幹線道路、小包センタ、フェリーの航路、バスのルート、小包センタ、事業拠点及び居住地域を含むことを特徴とする請求項１に記載の索引。
【請求項３】
前記索引において使用される前記１つ以上の地域名供給元の各々に対してビットを割り当てることにより作成される主供給元マスクを更に備えることを特徴とする請求項１に記載の索引。
【請求項４】
各地理特徴に関連付けられる各地域に対する地域供給元マスクを更に備え、対応するビットが前記主供給元マスクに割り当てられた前記供給元において当該地域が見つけられる場合に、前記地域供給元マスク内の各ビットが設定されることを特徴とする請求項３に記載の索引。
【請求項５】
優先順位は、異なる慣用的な使用に適合するように、異なる方法で適用可能であることを特徴とする請求項１に記載の索引。
【請求項６】
対象のアプリケーションにおける慣用的な使用は、前記アプリケーションが地元のユーザに対するものである場合、地域名が見つけられる供給元を最も少なく含むことを特徴とする請求項１に記載の索引。
【請求項７】
対象のアプリケーションにおける慣用的な使用は、前記アプリケーションが地元ではないユーザに対するものである場合、地域名が見つけられる供給元を最も多く含むことを特徴とする請求項１に記載の索引。
【請求項８】
対象のアプリケーションに対する、各地域名の慣用的な使用における普及度に基づく地理特徴に対する地域名の優先順位は、好適な郵便名供給元で見つけられる地域である地理特徴に関連付けられる最高優先順位の地域の判定と、各地域供給元マスクに設定されるビット数による前記地理特徴に関連付けられる残りの地域の優先順位の判定とを含み、前記残りの地域に対して、前記地域に対する前記供給元マスクにおける名称の供給元数が多いほど、前記地域の前記優先順位は高いことを特徴とする請求項１に記載の索引。
【請求項９】
対象のアプリケーションに対する、各地域名の慣用的な使用における普及度に基づく地理特徴に対する地域名の優先順位は、前記地域に関連付けられる前記供給元マスクに基づく前記地域が見つけられる地域名供給元数の判定を含み、前記地域に対する前記供給元マスクにおける名称の供給元数が大きいほど、前記地域の前記優先順位は高いことを特徴とする請求項１に記載の索引。
【請求項１０】
地理特徴に対する地域名の別の優先順位は、
各地域における地理特徴数による判定であって、前記地域における前記地理特徴数が多いほど前記地域の前記優先順位が高いとする地理特徴数による判定と、
各地域の物理的大きさによる判定であって、前記地域の前記物理的大きさが大きいほど前記地域の前記優先順位が高いとする物理的大きさによる判定と、
各地域の人口規模による判定であって、前記地域の前記人口規模が大きいほど前記地域の前記優先順位が高いとする人口規模による判定と、のうちの１つの判定に基づくことを含むことを特徴とする請求項１に記載の索引。
【請求項１１】
地理特徴に対する地域名の別の優先順位は、前記地域供給元マスクを使用した特定の地域名供給元の他の地域名供給元に対する優先度の判定に基づくことを含み、前記特定の地域に対する地域供給元マスクにビットが設定されている地域は、ビットが設定されていない地域より高い優先順位を有することを特徴とする請求項１に記載の索引。
【請求項１２】
前記主供給元マスクはトランプ供給元を更に含み、地理特徴に対する地域名の別の優先順位は前記トランプ供給元に基づくことを含み、前記トランプ供給元に対する地域供給元マスクにビットが設定されている地域は、ビットが設定されていない地域より高い優先順位を有することを特徴とする請求項３に記載の索引。
【請求項１３】
地理特徴に対する地域名の優先順位の判定の結果、複数の地域が同等である場合、前記同等な地域の優先順位は、
同等な各地域における地理特徴数による判定であって、前記同等な地域における前記地理特徴数が大きいほど前記同等な地域の前記優先順位が高いとする地理特徴数による判定と、
同等な各地域の物理的大きさによる判定であって、前記同等な地域の前記物理的大きさが大きいほど前記同等な地域の前記優先順位が高いとする物理的大きさによる判定と、
同等な各地域の人口規模による判定であって、前記同等な地域の前記人口規模が大きいほど前記同等な地域の前記優先順位が高いとする人口規模による判定と、
前記地域供給元マスクを使用したある特定の地域名供給元の他の地域名供給元に対する優先度による判定であって、前記特定の地域に対する地域供給元マスクにビットが設定されている同等な地域はビットが設定されていない同等な地域より高い優先順位を有するとする優先度による判定と、のうちの１つの判定に基づくことを含むことを特徴とする請求項１に記載の索引。
【請求項１４】
前記１つ以上の地域名から前記少なくとも１つの地理特徴への地域名の関連付けは、直接的又は間接的な関連付けを含むことを特徴とする請求項１に記載の索引。
【請求項１５】
直接的関連付けは、地理特徴に関連付けられるある特定の地域名供給元に対して、前記地域名供給元と前記地理データベース内の前記地理特徴との間の少なくとも１つの共通属性を使用して、前記地域名に関連付けられる任意の地理特徴を前記地理データベース内の前記少なくとも１つの地理特徴にマッチングすることを含むことを特徴とする請求項１４に記載の索引。
【請求項１６】
前記地理データベース内のマッチングされていない地理特徴に地域を割り当てるため、前記マッチングされていない地理特徴に隣接する地図上のマッチングした地理特徴を用いて行われる面による投票を更に含むことを特徴とする請求項１５に記載の索引。
【請求項１７】
面による投票は、多数決、重み付け投票及び直線長さによる投票のうちの１つを含むことを特徴とする請求項１６に記載の索引。
【請求項１８】
間接的関連付けは、地理特徴に関連付けられない第１の地域名供給元に対して、前記第１の供給元内の各地域名が地理特徴に関連付けられる第２の地域名供給元から地理特徴に対する前記関連付けを受け継ぐように、前記第２の供給元との供給元間地域名マッチングが使用されることを含むことを特徴とする請求項１４に記載の索引。
【請求項１９】
前記地域名の主トークンを更に含み、前記主トークンは、前記地域名のトークン化、標準化及び最適化、並びに前記地域名を任意の重複するか又は同様の地域名とマッチングすることのうちのいずれか１つ以上により決定されることを特徴とする請求項１に記載の索引。
【請求項２０】
トークン化は、前記地域名をトークン又は構成要素に分解することを含むことを特徴とする請求項１９に記載の索引。
【請求項２１】
前記主トークンは、索引化に適切な本体又は主構成要素を含むことを特徴とする請求項１９に記載の索引。
【請求項２２】
前記主トークン以外のトークンは、先頭の方向トークン、先頭の種類トークン、前記本体に先行する名前又は非種類情報、接頭部、末尾の種類、末尾の方向、接尾部、前記地域の分割を特定する数値識別子及び修飾又は近隣の容易に認識可能な都市名のうちの１つ以上を含むことを特徴とする請求項２０に記載の索引。
【請求項２３】
標準化は、略語の伸張、句読点の減少、埋め込まれたスペースの除去及び大文字使用の標準化のうちの１つ以上を含むことを特徴とする請求項１９に記載の索引。
【請求項２４】
最適化は、前記地域名を前記地域に含まれる地理特徴に関連付けることを含む請求項１９記載の索引。
【請求項２５】
前記地域名を任意の重複するか又は若干異なる地域名とマッチングすることは、地域名トークンを連結し、マッチングする地域名を判定するために前記地域名のトークンを任意の重複するか又は同様の地域名の前記トークンと比較することを含むことを特徴とする請求項１９に記載の索引。
【請求項２６】
前記地域名を任意の重複するか又は若干異なる地域名とマッチングすることは、音声表現に基づいて又は他の手段により前記名称をマッチングすることを含むことを特徴とする請求項１９に記載の索引。
【請求項２７】
マッチングは、前記最適化ステップから取得された前記地域名に対する地理特徴と任意の重複するか又は若干異なる地域名に対する地理特徴とを比較することにより、これらの地域がオーバーラップするか又は隣接するかを判定することを更に含むことを特徴とする請求項２６に記載の索引。
【請求項２８】
前記地域名及び任意の重複するか又は若干異なる地域名に対して全ての前記地理特徴がマッチングする場合、これらの地域名は同一の地域を表し、重複する地域名は１つの地域名を除いて前記索引から削除されることを特徴とする請求項２７に記載の索引。
【請求項２９】
前記地域及び任意の重複するか又は同様の地域に対して前記地理特徴のうち１つ以上がマッチングするが全てがマッチングするわけではない場合、これらの地域名は同一の地域を表すと判断され、前記索引において１つの地域名にマージされることを特徴とする請求項２７に記載の索引。
【請求項３０】
オーバーラップするか又は隣接する地域からの全地理特徴の和集合が、前記マージされた地域名に関連付けられることを特徴とする請求項２９に記載の索引。
【請求項３１】
前記地域及び任意の重複するか又は同様の地域に対して全ての前記地理特徴がマッチングしないとして得られる異なる地域に対して作成され、且つ前記索引に格納される、近隣の有名な都市の修飾を更に含むことを特徴とする請求項２７に記載の索引。
【請求項３２】
地理特徴識別番号、地域識別番号、都心地域の緯度点及び経度点、地域の修飾、地域の完全な名称、並びに地域の大きさのうちの１つ以上を更に含むことを特徴とする請求項１に記載の索引。
【請求項３３】
前記索引は自動的に作成されることを特徴とする請求項１に記載の索引。
【請求項３４】
地域を索引化する方法であって、
地理データベースから１つ以上の地理特徴の集合を受信するステップと、
１つ以上の地域名供給元のセットからの１つ以上の地域名のセットを判定するステップと、
前記地域名を前記地理データベースの前記地理特徴に関連付けるステップと、
各地理特徴に対して、前記関連付けられた地域名を対象のアプリケーションに対して設定された慣用的な利用における普及度の順序で優先順位付けするステップと、
各地理特徴に関連付けられた前記地域名を優先順位により配列するステップとを有することを特徴とする方法。
【請求項３５】
ユーザが地域及び前記地域内の地理特徴にアクセスできるようにする機能性を含むシステムであって、
地理データベース内の少なくとも１つの地理特徴と前記少なくとも１つの地理特徴に関連付けられる１つ以上の地域名のセットとを有する地理データベース索引であって、前記１つ以上の地域名が１つ以上の地域名供給元から選択され、且つ、対象のアプリケーションに対する、前記地域名の慣用的な使用における普及度に基づく優先順位により前記１つ以上の地域名が配列される地理データベース索引と、
ユーザに対する地域及び地理特徴情報の表示、並びにユーザからの入力の受信と組み合わせて前記地理データベース索引を使用するアプリケーションプログラムとを含むことを特徴とするシステム。
【請求項３６】
地域及び地理特徴情報の前記表示は、ユーザに対する地域及び地理特徴情報のテキスト表示、前記ユーザに対する地理特徴の場所の地図上での表示、並びに前記ユーザに対する地図上でのルーティング情報の表示のうちの１つ以上を含むことを特徴とする請求項３５に記載のシステム。
【請求項３７】
前記システムはインターネット系システムを含むことを特徴とする請求項３５に記載のシステム。
【請求項３８】
前記システムは車載ナビゲーションシステムを含むことを特徴とする請求項３５に記載のシステム。
【請求項３９】
ユーザが地域及び前記地域内の地理特徴にアクセスできるようにする機能性を含むポータブルハンドヘルドデバイスであって、
地理データベース内の少なくとも１つの地理特徴と前記少なくとも１つの地理特徴に関連付けられる１つ以上の地域名のセットとを有する地理データベース索引であって、前記１つ以上の地域名が１つ以上の地域名供給元から選択され、且つ、対象のアプリケーションに対する、前記地域名の慣用的な使用における普及度に基づく優先順位により配列される地理データベース索引と、
ユーザに対する地域及び地理特徴情報の表示、並びにユーザからの入力の受信と組み合わせて前記地理データベース索引を使用するアプリケーションプログラムとを備えることを特徴とするポータブルハンドヘルドデバイス。
【請求項４０】
地域及び地理特徴情報の前記表示は、ユーザに対する地域及び地理特徴情報のテキスト表示、前記ユーザに対する地理特徴の場所の地図上での表示、並びに前記ユーザに対する地図上でのルーティング情報の表示のうちの１つ以上を含むことを特徴とする請求項３９に記載のポータブルハンドヘルドデバイス。
【請求項４１】
前記ポータブルハンドヘルドデバイスはパーソナルデジタルアシスタント（ＰＤＡ）を含むことを特徴とする請求項３９に記載のポータブルハンドヘルドデバイス。
【請求項４２】
前記ポータブルハンドヘルドデバイスはパーソナルナビゲーションシステムを含むことを特徴とする請求項３９に記載のポータブルハンドヘルドデバイス。
【請求項４３】
前記ポータブルハンドヘルドデバイスは携帯電話を含むことを特徴とする請求項３９に記載のポータブルハンドヘルドデバイス。
【請求項４４】
ユーザが地域及び前記地域内の地理特徴にアクセスできるようにする機能性を含むアプリケーションプログラムに基づく地理情報システム（ＧＩＳ）であって、
地理データベース内の少なくとも１つの地理特徴と前記少なくとも１つの地理特徴に関連付けられる１つ以上の地域名のセットとを有する地理データベース索引であって、前記１つ以上の地域名が１つ以上の地域名供給元から選択され、且つ、対象のアプリケーションに対する、前記地域名の慣用的な使用における普及度に基づく優先順位により配列される地理データベース索引を備えることを特徴とする地理情報システム。
【請求項４５】
演算が格納されたコンピュータ可読媒体であって、１つ以上のプロセッサにより処理される場合に、
地理データベースから地理特徴の選択項目を受信するステップと、
１つ以上の地域名供給元のセットからの１つ以上の地域名のセットを判定するステップと、
前記地域名を前記地理データベースからの前記地理特徴に関連付けるステップと、
各地理特徴に対して、前記関連付けられた地域名を、対象のアプリケーションに対する、慣用的な使用における普及度の順序で優先順位付けするステップと、
各地理特徴に関連付けられた前記地域名を優先順位により配列するステップとをシステムに実行させるコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地理データベースに対する地域の索引に関し、特に、地域名及び地域に含まれ関連付けられる地理特徴を索引化するために使用される地理データベース内のデータ構造に関する。
【背景技術】
【０００２】
近年、消費者が特定の所在地住所をデジタル地図上に配置できるようにするための種々のデバイス及びシステムが消費者に提供されている。これらのデバイス及びシステムは、運転者が街路及び道路をナビゲートできるようにする車載ナビゲーションシステム、同様の機能を有するパーソナルデジタルアシスタント（「ＰＤＡ」）、パーソナルナビゲーションデバイス及び携帯電話等のポータブルハンドヘルドデバイス、並びにユーザが所望の場所を示す地図を生成できるインターネットアプリケーションの形態をとる。上記の種類及び他の種類のデバイス及びシステムの全てに共通する面は、地理特徴の地理データベース及びユーザ入力に応答して地理データベースにアクセスし且つそれを操作するソフトウェアである。基本的に、上記のデバイス及びシステムの全てにおいて、ユーザは目的の場所を入力でき、目的の場所の位置が返される。
【０００３】
通常、ユーザは住所、レストラン等の事業の名称、都心又はゴールデンゲートブリッジ等の目的地の目印を入力し、要求した位置又は特徴の場所を返される。場所は、地図表示上に示されてもよく、その場所への運転指示を計算及び表示するために使用されてもよく、又は他の方法で使用されてもよい。
【０００４】
通常、アプリケーションは、所望の地理特徴が位置する地域を探索し、その後、その地域内で地理特徴を探索するトップダウン式の探索方法を使用する。地域内で見つけられる地理特徴の例は、住所、目印及び事業拠点である。アプリケーションは、ある特定の判定基準にマッチングする全ての地理特徴を探索し、その後、マッチングする地理特徴が位置する地域のリストから所望の地理特徴を選択するボトムアップ式の探索方法を更に使用する。
【０００５】
現在、地理データベースは地域索引を供給されていないか、又は地域内の地理特徴を探索する際の機能性が制限される地域索引を有する。地域索引は、ユーザに対して表示するための地域名及び関連情報を選択するために使用されてもよい。地域は、例えば米国の州（state）、カナダの州（province）、郡又は他の主要な地理特徴内の都市又は町である。現在、地域索引を有する地理データベースの場合、索引は基本的に、名称供給元により配列され且つ供給元間で名称が重複する地域名のリストである。地域名は、行政名供給元、郵便名供給元及び慣用名供給元等の多くの地域名供給元で見つけられる。本出願における用語「地域名」は、地域の記述として使用可能な任意のデータを示すために使用される。上記の供給元の他に、郵便番号自体は地域名として使用可能である。また、いくつかの国において、電話局番は地域を示し、地域名として使用可能である。ドイツにおいて、ナンバープレートの接頭部は地域を示し、地域名として使用可能である。以下は、地理データベースが地域索引を供給されているか否かに関わらない地理データベースの従来技術の説明である。
【０００６】
現在、種々の地域名供給元から地域情報をポピュレートされた地理データベースは、ある地域名が複数の地域名供給元で出現する場合、その地域に対する重複するエントリを含む。デバイス製造業者、システム製造業者又はアプリケーション開発者は、重複する地域を単一の名称セットにマージしない。あるいは、重複する名称間の綴り、句読点、略語又は他の差異により地域供給元間で重複する名称の表現が異なるため、不完全なマージを実行する。従って、その後ユーザが地理データベースアプリケーションに地域をクエリする時、地域名が複数の地域名供給元で出現する場合、ユーザのデバイス又はシステムは同一の地域名を複数回列挙することがあるだろう。この場合、ユーザは自分のシステム又はデバイスの画面に表示された同一又はほぼ同一の名称から選択しなければならず、これは分かりにくい。ユーザが実際に重複する地域と同一又は若干異なる名称を有する異なる地域とを区別できない場合、更なる問題が地域名リストに存在する。複数の地域名供給元からの重複する地域名に関する問題は、メモリが制限されるいくつかのナビゲーションデバイスにおいて悪化する。例えばいくつかのデバイスは、１つの地理特徴に対して２つの地域名しか保持できない。３つ以上の地域名に関連付けられる地理特徴に対して、デバイスにおいて使用するために地域名のうち２つを任意に選択することは、名称が重複するが異なる地域及びより一般的な地域名を有する地域が選択されない可能性があるため最適ではない場合がある。名称が重複する異なる地域が選択されない結果、リスト中には誤った地域のみが示されるため、ユーザは誤った地域を選択する。地域索引を有する地理データベースの場合、重複する地域をマージしないことにより、特にメモリが制限されるナビゲーションデバイスに対して、サイズが大き過ぎる地域索引が更に作成されてしまう。
【０００７】
現在、完全に同一の地理特徴を共有する同一又は若干異なる名称を有する地域の場合、重複する名称のエントリは従来技術の地域索引から削除されない。少なくとも１つの地理特徴を共有する同一又は若干異なる名称を有する地域の場合、名称のエントリは従来技術の地域索引において単一エントリにマージされない。種々の地域名供給元から地域情報をポピュレートされた地理データベースは、異なる供給元のうち少なくとも２つの供給元がある地域に対して若干異なる名称を有する場合、その地域に対して若干異なる名称を含むことがある。例えばNew JerseyのHo-Ho-Kusは、Ho-Ho-Kus、Ho Ho Kus又はHo-Ho-Kus（Hohokus）等、異なる供給元において若干異なる名称で知られる。従来技術の地域索引において、若干異なる地域名を有する地理データベースのエントリを削除しないことにより、特にメモリが制限されるナビゲーションデバイスに対してサイズが大き過ぎる地域索引が作成され、これらの若干異なる地域名を区別しようとするユーザにとって分かりにくくなる。名称が重複するが異なる地域の場合、現在の従来技術は、地域が位置する郡等の追加情報を表示することにより、それらの地域を区別する。これらの地域の場合、都市の名称及び場所は米国内の郡名よりユーザに認識される可能性が高いため、その地域と共に追加情報として表示される近隣の都市、有名な都市又は一般的な都市はユーザにとってより有用である。
【０００８】
図１は、慣用的な利用において一貫して扱われない地域定義の一例を示す図である。地域定義の例は、「Postal Place」及び「County Subdivision」である。図１において、慣例ではAllstonはBostonの一部であると考えられる。AllstonはPostal Placeであり、BostonはCounty Subdivisionである。図１において、Postal PlaceであるAllstonはCounty SubdivisionであるBostonに含まれて示される。それに対して、ManhattanはNew York Cityの一部であると考えられるが、ManhattanはCounty Subdivisionであり、New York CityはPostal Placeであり且つIncorporated Placeである。図１において、County SubdivisionであるManhattanはPostal PlaceであるNew York Cityに含まれて示される。そのような矛盾は、慣例と公的な地域定義との間の差異を示す。
【０００９】
更に、慣例において一貫して扱われない地域定義の別の例において、New York州内のある特定の地理特徴は、慣例においてSoHo、Manhattan及びNew York Cityとして知られる部分的にオーバーラップする地域に含まれる。上述のように、New York CityはPostal Placeの地域名供給元で見つけられ、ManhattanはIncorporated Placeの地域名供給元で見つけられる。一方、SoHoは地域名供給元で見つけられず、これは慣用的に知られる。SoHoは、公的な地域定義のみに基づく地域索引から欠落することになる。
【００１０】
更に、現在の地理データベースの地域索引は、優先順位又は慣例に対する重要度により配列されていない。更に、地理データベース内の各地理特徴に対して、地理特徴に関連付けられる地域はその地理特徴に対して優先順位付けされていない。各地理特徴に対して２つの地域名のみを格納できるメモリの制限されたデバイスに対して地域の優先順位付けを行わない場合、アプリケーション開発者は、３つ以上の地域に関連付けられる地理特徴に対して２つの地域名を選択する必要がある。地理特徴に関連付けられる最高優先順位の地域、あるいは慣例において最も有名又は最も一般的な地域がユーザのデバイスに対して表示されるのが好ましい。ユーザに対して地域リストを提示する場合、地理特徴に関連付けられる最高優先順位の名称が最も認識可能であるため、それらが使用されるべきである。
【００１１】
更に、地域名の最も重要な名称構成要素又は主トークン、例えば名称「South Hadley」の「Hadley」は、現在の地理データベースの地域索引において識別されないことがある。現在市販されているナビゲーションアプリケーションがMassachusettsの都市Hadleyを探索する場合、Hadleyは検索されるがSouth Hadleyは検索されないことがある。South Hadleyを見つけるためには、ユーザは「S」から開始し、「South」から始まる多くの選択肢をソートする必要がある。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
地理データベースの地域索引では、特にメモリが制限されるデバイスに対して、重複する地域名及び若干異なる名称で知られる地域が同一の地域を表す時且つその時に限りマージされることが、マージされない場合には同一又は若干異なる名称のリストから選択しなければならないユーザの混乱を取り除くために必要である。また、そのような地域索引は、大きくなり過ぎる索引のサイズを減少するために必要である。重複する名称及び異なる名称を有する地域をマージする一方で、有意味に異なる地域名を保存する必要もある。地域索引は、異なる地域を表す重複する地域名を区別するために必要である。これらが区別されない場合、ユーザは、同一名称を有する２つの異なる位置を区別できない。更に、融通性を有する地域索引は、慣例において一貫して扱われない公的な地域定義を考慮するため及び索引がこれらの公的な地域定義に基づかないようにするために必要である。複数の地域に関連付けられる各地理特徴に対する地域の優先順位により配列された地域索引が必要である。優先順位により配列することにより、メモリが制限されるアプリケーションに含まれるように最も重要な名称を選択することが可能になり、ユーザに対して提示するのに最適な名称が識別される。最後に、地域索引は、名称構成要素を探索することにより全関連地域を含む拡張リストが返されることを保証するために、地域の最も重要な名称構成要素が索引の一部であることが必要である。
【課題を解決するための手段】
【００１３】
電子地図及び電子データベースと共に使用するための地域索引、並びに索引を作成する方法及びシステムが提供される。
【００１４】
種々の地域名供給元からの地域名は、地理データベース内の地理特徴毎に地理特徴に関連付けられる。地域名の文脈依存トークン化、標準化、最適化及びマッチングにより、重複する地域名及び異なる地域名を削除及びマージする一方で、有意味に異なる名称を保存することが可能になる。重複する地域名は、それらが同一の地域を表す時且つその時に限り削除される。これにより、それらが削除されない場合には同一又は同様の名称のリストから地域名を選択しなければならないというユーザの混乱が低減される。若干異なる名称で知られる地域に対する地理データベースのエントリは、地域が少なくとも１つの地理特徴を共有する場合、単一のエントリにマージされる。また、重複するか又は若干異なる地域名を有する異なる地域は、それらが異なる地域を表す時に限り、近隣地域の名称を用いて修飾表示することにより区別される。これにより、修飾表示されない場合には同一名称のリスト、又はユーザに対してあまり意味のない方法、例えば一般にユーザが場所を知らない郡名を用いて修飾表示することにより区別される名称のリスト、から選択しなければならないというユーザの混乱が低減される。
【００１５】
地域名テーブルが作成され、これは地域の完全な名称、地域の索引化用主トークン、並びに修飾、都心情報及び地域の大きさ等の他の関連情報を含む。主供給元マスクは、本方法において使用される各地域名供給元毎にビットを割り当てることにより作成される。特徴／地域／優先順位テーブル内の各地理特徴に対して、別個の供給元マスクが地理特徴に関連付けられる地域毎に格納され、地域が見つけられる各供給元に対してビットが設定される。このテーブル内には、地域名テーブルへのリンク及び地理特徴に関連付けられる各地域の優先順位が存在する。特徴／地域テーブルは、各地理特徴に関連付けられる地理特徴情報を含む特徴探索テーブルへのリンクを更に含む。
【００１６】
各地理特徴に対する地域名は、優先順位で索引化される。好適な実施形態において、地理特徴に関連付けられる最高優先順位の地域は、好適な郵便名供給元で見つけられる地域であり、残りの地域の優先順位は、各地域供給元マスクに設定されたビット数により判定される。そのような索引において、第１の地域が慣用的な使用においてより有名又は一般的な場合、第１の地域は第２の地域より高い優先順位を有する。
【００１７】
優先順位により配列することにより、メモリが制限されるアプリケーションに含まれるように最も重要な名称を選択することが可能になり、ユーザに対して提示するのに最適な名称がボトムアップ式探索で識別される。このようにして、重複する地域名及び若干異なる地域名を含む場合に大きくなり過ぎる地域索引のサイズは減少される。更に、地域索引がこれらの公的な地域定義に基づかないため、地域索引は、慣例（慣用的な使用）においては一貫して扱われないような地域定義を考慮する。最後に、トークン化ステップから取得される地域の最も重要な名称構成要素が索引の一部であるため、名称構成要素を探索することにより全関連地域を含む拡張リストが返されることを保証する。
【発明を実施するための最良の形態】
【００１８】
より適切な地域索引を作成するためには、種々の地域名供給元、特に行政地域名供給元、郵便地域名供給元及び慣用地域名供給元から名称を収集することにより、地域名の完全なリストが最初に作成される必要がある。任意の数及び種類の供給元からの地域名を使用することにより、国際データに対する汎用スキーマが可能になる。この特徴を用いない場合、重要な名称が欠落している可能性があり且つ様々な国で使用されてもよい供給元の種類を制限する郵便名供給元又は行政名供給元等、一定数の供給元のみが使用されることがある。
【００１９】
本明細書において使用される言語は米国特有のものであるが、実施形態において、同一の原理は僅かな調整のみで国際的に適用可能である。外国の地域名供給元の等価物の例は、英国の陸地測量局及びロイヤルメール、並びにカナダのカナダ統計局及びカナダ郵政省を含む。
【００２０】
実施形態において、地域名供給元の所定の集合に対して、地域名リストは各地域名供給元から取得される。実施形態において、供給元は、例えば１つ以上の選択された州（states）、准州（territories）、州（provinces）又は地区における地域を含む供給元である。好適な実施形態において、供給元は米国内の地域を含む供給元である。米国において、例えば地域名の供給元は以下を含むが、これらに限定されない。
【００２１】
１．連邦情報処理規格５５（ＦＩＰＳ５５）。米国地質調査所（ＵＳＧＳ）のＴＩＧＥＲデータベースのこの構成要素はパブリックドメイン（http://geonames.usgs.gov/fips55.html）にある。ＦＩＰＳ５５は、政府により定義される行政地域の地域構造、例えば名称を有し且つ人が住む場所、主要な郡区分、並びに米国、プエルトリコ及び海外地域の他の場所に対するコードを記述する規格供給元である。
２．米国郵政公社（ＵＳＰＳ）の都市／州ファイル。このファイルはＵＳＰＳのＺＩＰ＋４製品の構成要素である。これらの都市名及び州名は、住所範囲又はＺＩＰコードレベルで見つけられる。５桁のＺＩＰコード及び４桁の拡張番号（ＺＩＰ＋４）は、索引において地域名として扱われ、ＵＳＰＳの都市／州ファイル内の適切な名称セットを示す。一般に、各場所に対して好適な郵便地域名は１つだけ存在するが、郵政公社は、同一の場所に対して任意の数の許可される郵便地域名及び許可されない郵便地域名を更に含む。「好適」な郵便地域名は、ＵＳＰＳが手紙の宛名に使用することを推薦する名称である。「許可される」郵便地域名は、ＵＳＰＳが容認した郵便配達の可能な別名である。「許可されない」郵便地域名は、ＵＳＰＳが郵便配達できない名称である。実施形態において、地域索引は、各地理特徴に対して好適な郵便地域名及び許可される郵便地域名の全てを含む。
３．米国地質調査所（ＵＳＧＳ）により提供される地名情報システム（ＧＮＩＳ）。これは、５０の州及び準州を含む米国内の地域名のパブリックドメインデータベースである。ＧＮＩＳは、都市名、中心点、人口及び同様の情報を列挙する。
４．都心の地点情報（ＰＯＩ）。
５．ＵＳＰＳの郵便局に対するＰＯＩ。
６．米国勢調査局の位相総合地理符号化参照システム（ＴＩＧＥＲ）のエンティティ「Ｐ」（ＴＩＧＥＲ内のIncorporated place）に対するレコード型Ｃ。
７．ＴＩＧＥＲのエンティティ「Ｍ」（ＴＩＧＥＲ内のCounty Subdivision）に対するレコード型Ｃ。１つの州に完全に含まれる地域名は、索引化のためにその州に関連付けられる。米国のある特定のＺＩＰコード等の１つの州に完全には含まれない地域は、それらが含む複数の州の索引に記載される。図２は、米国の行政区分の階層を示す図である。これらの行政区分は、国、地方、区域、州及び郡として図の中心に示されるグループに完全に含まれる。この図は、County Subdivisionが郡に含まれることを示す。図２において「Places」と示されるAdministrative Placeは州に完全に含まれる。Administrative Placeは、郡及びCounty Subdivisionの境界を横断してもよい。Metropolitan Area、UrbanArea及びZip Codeは州の境界を横断してもよいため、図２に示すように、国にのみ完全に含まれる。
【００２２】
図１は、複数の地域供給元からの名称を処理するために定型のルールセットのみを使用するナビゲーションアプリケーションに対して、米国内の地域が有用に自動モデル化されない例を示す図である。Postal Place及びCounty Subdivisionは公的な供給元で見つけられる。図１において、MassachusettsではAllstonというPostal PlaceはBostonというCounty Subdivisionに完全に含まれる。しかしNew Yorkでは、ManhattanというCounty SubdivisionはNew York CityというPostal Placeに完全に含まれる。従って、County Subdivisionの地域名供給元は、ある特定のCounty Subdivision内のPostal Placeを判定するために必ずしも使用されなくてもよい。同様に、Postal Placeの地域名供給元は、ある特定のPostal Place内のCounty Subdivisionを判定するために必ずしも使用されなくてもよい。異なる供給元からの地域名の慣用的な使用（慣例）は地理により異なる。複数の供給元からの地域名を索引化する場合、この相違を考慮する必要がある。
【００２３】
実施形態において、地理データベースにアクセスするソフトウェアアプリケーション又はデバイスのユーザにより使用される場合の以下の使用例は、索引を構成するために複数の供給元からの地域名を使用する利点を示す。１つの名称供給元のみが使用される場合、重要な名称が漏れる。郵便名、行政名及び慣用名ですら全て重要である。
【００２４】
索引において郵便名供給元を使用しない場合：
州(state)を入力 −〉 Vermont
都市(city)を入力 −〉 Quechee
都市が見つかりません ： Quechee
索引において郵便名供給元を使用する場合：
州(state)を入力 −〉 Vermont
都市(city)を入力 −〉 Quechee
見つかりました −〉
Quechee
索引において行政名供給元を使用しない場合：
州(state)を入力 −〉 New York
都市(city)を入力 −〉 Manhattan
都市が見つかりません ： “Manhattan”
索引において行政名供給元を使用する場合：
州(state)を入力 −〉 New York
都市(city)を入力 −〉 Manhattan
見つかりました ： “Manhattan”
【００２５】
実施形態において、以下の４つの使用例により、複数の地域名供給元からの地域名を集約することの別の利点として、地域内の紛らわしい所在地住所の区別を可能とすることを示す。米国の都市は、都市の異なる部分に位置する重複する所在地住所を有することができる。これは、MassachusettsのBoston等の大都市の場合に特に当てはまる。上述のように、Bostonは、行政地域名供給元ＦＩＰＳ５５においてCounty Subdivisionとして見つけられる。実施形態において、以下で説明する４つの使用例における第１の使用例では、ある特定の所在地住所が都市内に１つしかなく、都市が大都市であってもナビゲーションに問題が発生しない典型的な例を示す。この一例はBostonのNewbury Streetである。この街路名は１０ブロックの距離があり、Bostonの他の場所において重複しない：
索引において行政名供給元を使用する場合：
州(state)を入力 −〉 Massachusetts
都市(city)を入力 −〉 Boston
街路(street)を入力 −〉 Newbury Street  //番地に関係なく１つしかない
【００２６】
この時点で、正確な目的地のために、特定の街路番号、最も近い交差点又は最も近いブロック等のユーザからの更なる入力を待つ。入力が供給される場合、目的地はユーザに対して地図上に正確に示される：
街路番号(street number)を入力 −〉 173
見つかりました：“173 Newbury Street, Boston, Massachusetts”
【００２７】
実施形態における４つの使用例のうちの第２の使用例は、街路名が都市内で重複するが、番地が目的地を１つにするために役立つ場合である。大都市の中の複数のより小さな町を通る長い街路は、そのような例のひとつである。例えば、Commonwealth AvenueはBoston、並びにBoston内のより小さな町であるAllston及びChestnut Hillを通る。上述のように、Bostonは行政地域名供給元で見つけられるCounty Subdivisionである。Allston及びChestnut Hillは、郵便地域名供給元において郵便番号０２１３４及び０２４６７でそれぞれ見つけられる町である。
【００２８】
索引において行政名供給元を使用しない場合：
州(state)を入力 −〉 Massachusetts
都市(city)を入力 −〉 Boston
街路(street)を入力 −〉 Commonwealth Avenue
街路番号(street number)を入力 −〉 2000
街路番号が見つかりません ： “2000”
【００２９】
Bostonが米国郵政公社による郵便番号０２４６７に対する妥当な郵便名ではないため、ChestnutHillがBoston内の小さな町であったとしても、「2000 Commonwealth Ave, Chestnut Hill, Massachusetts 02467」は上述のBostonの例において見つけられない。
【００３０】
索引において行政名供給元及び郵便名供給元の双方を使用する場合：
州(state)を入力 −〉 Massachusetts
都市(city)を入力 −〉 Boston
街路(street)を入力 −〉 Commonwealth Avenue
【００３１】
この時点で、CommonwealthAvenueはBoston、Allston及びChestnut Hillを通ることが見つけられる。正確な目的地のために、特定の街路番号、最も近い交差点又な最も近いブロック等のユーザからの更なる入力を待つ。入力が供給される場合、目的地はユーザに対して地図上に正確に示される：
街路番号(street number)を入力 −〉 2000
見つかりました ： “2000 Commonwealth Avenue, Chestnut Hill, Massachusetts”
【００３２】
実施形態における４つの使用例のうちの第３の使用例は、図３に示すように、４つの異なるAdams StreetがBoston内の４つの異なる地域で見つけられる点を除いて第２の使用例に類似する。図３は、「Boston,Massachusetts」等の地域内の４つの異なる地域に位置する「Adams Street」等の同名の住所を区別する必要がある例を示す図である：
索引において郵便名供給元を使用しない場合：
州(state)を入力 −〉 Massachusetts
都市(city)を入力 −〉 Boston
街路(street)を入力 −〉 Adams Street
以下より選択してください −〉
Adams St., Boston
Adams St.,Boston
Adams St.,Boston
Adams St.,Boston  //アプリケーションはBoston市内に４つの別個のAdams Streetを見つけるが、ユーザはこれらの４つの選択肢を区別できない
索引において郵便名供給元を使用する場合：
州(state)を入力 −〉 Massachusetts
都市(city)を入力 −〉 Boston
街路(street)を入力 −〉 Adams Street
以下より選択してください −〉
Adams St.,Charlestown
Adams St.,Hyde Park
Adams St.,Roxbury
Adams St.,Dorchester
街路番号(street number)を入力 −〉  //ユーザは、街路番号を入力することにより続行する
【００３３】
この使用例において、アプリケーションは、更なる情報をユーザに要求する前に各ユーザエントリを処理する。他の実施形態において、「索引において郵便名供給元を使用する場合」に対して、ユーザは都市Boston、街路Adams Street及び街路番号を入力し、その後アプリケーションはこれらの３つのエントリを処理する。小さい町であるCharlestown、HydePark、Roxbury及びDorchesterにおいて街路番号が重複しないと仮定すると、街路名及び街路番号は、これらの４つの町のうちの１つに対して見つけられ、ユーザに対して表示するために地図上に正確に示される。
【００３４】
実施形態における４つの使用例のうちの第４の使用例は、街路番号、例えば「2 Adams St.」が都市内の同名の別個の街路に重複する場合を示す。この場合、適切な応答は、目的地を１つだけ導き出すため、重複する街路番号が位置するより小さな町のリストをユーザに提示することのみである。従って、上述の第３の使用例の例を使用した場合は、以下のようになる。
索引において行政名供給元及び郵便名供給元を使用する場合：
州(state)を入力 −〉 Massachusetts
都市(city)を入力 −〉 Boston
街路(street)を入力 −〉 Adams Street
街路番号(street number)を入力 −〉 2
以下より選択してください −〉
2 Adams Street,Charlestown
2 Adams Street,Hyde Park
2 Adams Street,Roxbury
2 Adams Street,Dorchester
【００３５】
実施形態において、図４に示すような別の使用例の場合、「Brentwood, California」等の公的な地域及び同名の近隣は、複数種類の地域名供給元を使用することにより区別される。「Brentwood, California」は、San Francisco近隣の公的な行政区域（Administrative Place）であると共に、Los Angelesの有名だが公的ではない近郊でもある。これは、許可されるが好適ではない郵便名である。図４は、California内のBrentwood地域の双方を示す。双方の地域はナビゲーションの目的において一般的な住所を含み、適切なナビゲーションアプリケーションはユーザに対してこれらを区別する：
州(state)を入力 −〉 California
都市(city)を入力 −〉 Brentwood
以下より選択してください −〉
Brentwood (San Franciscoの近隣都市)
Brentwood (Los Angelsの近郊)
【００３６】
他の実施形態において同一の使用例を使用すると、ユーザが州、都市及び街路名を入力した後にアプリケーションがユーザ入力（user entry）を処理する場合、アプリケーションは正しいBrentwoodを判定できる。例えば：
州(state)を入力 −〉 California
都市(city)を入力 −〉 Brentwood
街路名(street name)を入力 −〉 Concord Avenue
街路番号(street number)を入力 −〉 767
見つかりました ： “767 Concord Avenue, Brentwood (San Franciscoの近隣都市), California”
【００３７】
実施形態において、図５に示すような更なる使用例の場合、「Quechee, Vermont」等の公的な供給元に列挙されることもあるが明確に引かれた境界を有さない小さな村は、包括的な地域索引に含む必要がある。VermontのQuechee村は、人気の観光目的地である小さな町である。Simon Pierce Glassblowingは、職業別電話帳において1760 Quechee Main Street, Quechee, Vermont 05059として見つけられる。しかし、Quecheeは行政地域ではなく、米国郵政公社もこの住所を認識しない。ＺＩＰコード０５０５９は、非常に少ない所在地住所を含む「私書箱限定」ＺＩＰコードである。従って、Quechee Main StreetはQuechee内で識別される街路ではない。Quecheeの中心を包囲する地域は、White River Junction及びHartfordとして知られる。図５は、１つの可能な村の境界が引かれたQuecheeの見込み地図を示す。適切なナビゲーションアプリケーションは、住所が妥当な郵便住所又はIncorporated Placeであるかに関わらず、職業別電話帳に記載された通りに住所を認識する必要がある：
州(state)を入力 −〉 Vermont
都市(city)を入力 −〉 Quechee
街路(street)を入力 −〉 Quechee Main Street
番号(number)を入力 −〉 1760
見つかりました ： “1760 Quechee Main Street, White River Junction, Vermont”
【００３８】
しかし、Quecheeの境界が未知であるため、地域名Quecheeは所在地住所に含まれない。その代わり、White River Junctionはその街路住所に対して指定される地域である。この選択は郵便住所に従う。ナビゲーションアプリケーションは、以下に説明するように作成される地域索引を使用することにより、所望の場所を見つけたと判定できる。Quecheeは「1760 Quechee Main Street」に対する地域ではないが、地域索引は、「White River Junction, Vermont」の街路を探し出せるように地域Quecheeを拡張できる。マッチングした地域がユーザ入力と異なる場合、ナビゲーションアプリケーションはユーザに確認を求めることができる。街路が１つだけ見つけられた場合であっても、可能なマッチングにすぎない場合があり、ナビゲーションアプリケーションのユーザはそれを受け入れるか又は拒否できる。将来的にQuecheeの境界が追加されたならば、地図を改善することにより正確な解答が可能になる。その場合、「1760 Quechee Main street」が位置する地域の名称は実際にQuecheeになる。
【００３９】
実施形態において、図６に示すような更なる使用例の場合、New York Cityの「Greenwich Village」等の公的ではない地域名である近隣を包括的な地域索引に含む必要がある。ナビゲーションのためには重要であるが任意の行政名供給元又は郵便名供給元に記載されない種々の地域名が米国に存在する。そのような名称の１つの種類は有名な近隣である。New York CityのGreenwich Village及びSoHo、並びにSan FranciscoのHaight-Ashburyが例に含まれる。これらの場所は十分に大きいため、街路セグメント、住所、事業及び他の地点情報を含むことができる。適切なナビゲーションアプリケーションは、公的な行政名又は郵便名であるか否かに関わらず、有名な場所及びそれらに含まれる所在地住所の場所を探し出す機能を含む。
【００４０】
種々の供給元からの名称を使用しない場合：
州(state)を入力 −〉 New York
都市(city)を入力 −〉 Greenwich Village
都市が見つかりません ： “Greenwich Village”
種々の供給元からの名称を使用する場合：
州(state)を入力 −〉 New York
都市(city)を入力 −〉 Greenwich Village  //郵便名でも行政名でもない
街路(street)を入力 −〉          //ユーザは街路名を入力することにより続行する
【００４１】
この使用例において、種々の供給元からの名称を使用する場合、改善された地図はGreenwich Villageの境界を含むことができる。図６は、Greenwich VillageがGreenwich St.とBroadwayとの間でSpring Street及び14th Streetにより境界付けられるManhattanの地域として定義可能であることを示す。この情報を有する地図を使用する場合、対話は以下のように続行する：
街路(street)を入力 −〉 Carmine Street
街路番号(street number)を入力 −〉 13
見つかりました ： “13 Carmine Street, Greenwich Village, New York”
【００４２】
実施形態において、図７に示すような更なる使用例の場合、New York CityのQueens区の「Forest Hills」等の区に位置する村を包括的な地域索引に含む必要がある。異なる供給元からの地域名は、街路名が位置するNew York Cityの区を判定するために使用可能である。New York市は５つの区から構成される。そのうちQueens以外の全てが地域名として独立している。しかし、Queens内には数十個の内在地域が定義される。Queens内の住所を探す場合、ユーザは住所が位置するQueens内の地域を知る必要がない。住所が１つの村にだけ１つだけ含まれる場合、以下に説明する地域索引は住所を含む村を判定できる：
州(state)を入力 −〉 New York
都市(city)を入力 −〉 Queens
街路(street)を入力 −〉 70th Rd.
街路番号(street number)を入力 −〉 10700
見つかりました ： “10700 70th Road, Forest Hills, New York”
【００４３】
この使用例の場合、地域索引はQueensに位置する村の名称に対する要求を更に処理できる：
州(state)を入力 −〉 New York
都市(city)を入力 −〉 Forest Hills
街路(street)を入力 −〉 70th Rd.
街路番号(street number)を入力 −〉 10700
見つかりました ： “10700 70th Road, Forest Hills, New York”
【００４４】
図８Ａ及び図８Ｂは、地域を地理データベース内の地理特徴にリンクし、地域名をトークン化、標準化、最適化及びマッチングし且つ地域が優先順位により配列された索引を作成する処理のフローチャートの一実施形態を示す図である。実施形態において、地域内で見つけられる地理特徴の例は、街路、街路セグメント、街路セグメントエッジ、ブロック面（block faces）、目印、州立公園、幹線道路、フェリーの航路、バスのルート、小包センタ、事業拠点及び居住地域を含むがこれらに限定されない。街路セグメントは、街路、住所範囲又は単一の住所の一部分である。街路セグメントエッジは、街路セグメントの街路の片側である。ブロック面は、都市のブロックを構成する４つの面の１つである。
【００４５】
上述の地域名供給元の所定の集合及び独自仕様（proprietary）の地理データベースに対して、処理はステップ８０５から開始する。ステップ８１０において、処理する別の地域名供給元が存在する場合、ステップ８１５において、その供給元が地理データベース内の地理特徴にマッチングする地理特徴を含むならば、地図のマッチングが可能であるかを判定する。ステップ８１５において、供給元に対する地図のマッチングが可能であると判定された場合、ステップ８２０において、地域名供給元からの地域名は地図のマッチングにより地理データベース内の地理特徴に直接に関連付けられる。この直接的関連付けは、合成又は属性マッチングにより自動的に実行されるか、あるいは検査により手動で実行される。直接的関連付けは、通常、属性を地理データベースと共有する地域名供給元に対して使用される。好適な実施形態において、合成は、地域名供給元が地球上の場所及び範囲を示す空間情報を有する場合に使用可能である。直接的関連付けは、地域名供給元からの地域を地理データベースに空間的にオーバーラップし、ある地域の境界内で出現する任意の地理データベースの特徴にその地域を割り当てることにより実行される。属性マッチングは、供給元と地理データベースとの間で共通の属性をマッチングすることにより実行され、それにより直接的関連付けの実行が可能となる。マッチング可能な属性は、文字列又は数字により表される属性である。通常、間接的関連付けはその他の供給元に対して使用される。
【００４６】
実施形態では、ステップ８２０において、地域名供給元が属性を地理データベースと共有する場合、地理データベース内の地理特徴に対する直接的関連付けは、供給元内の属性を地図又は地理データベース内の同一属性とマッチングすることにより実行される。例えば、範囲マッチングは、地域供給元と地理データベースとの間で住所属性をマッチングするために使用可能である。範囲マッチングは、ＴＩＧＥＲ及びＵＳＰＳのCity Place Namesディレクトリを含む街路の詳細に関連付けられる地域名を有する任意の供給元を使用して実行される。County Subdivision（エンティティ「Ｍ」）コード及びIncorporated Place（エンティティ「Ｐ」）コードは、マッチングしたＴＩＧＥＲの地理特徴から注目地図又は注目データベース内の地理特徴に直接伝搬される。範囲マッチングは、街路名、番地の範囲及び地域をＴＩＧＥＲから取得し、これらの項目を独自仕様の、対象の地理データベース内の対応する街路セグメントにマッチングしようとする。ＴＩＧＥＲにおいて、街路ブロックの各側は住所範囲だけではなく、その場所におけるエンティティの種類Ｐ（Incorporated place名）、その場所におけるエンティティの種類Ｍ（County Subdivision名）、州コード、ブロックコード、土地コード及びMinor Civil Division（ＭＣＤ）を表すタグを有する。マッチングした範囲により、情報をＴＩＧＥＲから地理データベースに転送することが可能になる。範囲マッチングは、接触する又は正確に位置合わせされる街路セグメント、又は部分的に重なる街路セグメントの正確なマッチングであってもよい。
【００４７】
また、ステップ８２０において、ＵＳＰＳ都市／州ファイルが地域名供給元である場合、供給元のＵＳＰＳＺＩＰ＋４カタログから配布可能な住所範囲は地図又はデータベースに対してジオコードされる。実施形態において、この供給元からのＺＩＰコードは地域名自体として扱われる。また、この供給元からのＺＩＰコードは、都市／州ファイル内の適切な地域名セットを示す。正確な各マッチングに対して、５桁のＺＩＰコード及びＺＩＰ＋４からの１つの４桁のplus4コードは地域名として扱われ、対応する地理特徴に伝搬される。
【００４８】
ステップ８２５において、地域名供給元にマッチングしなかった地理データベース内の地理特徴に対して、地理特徴を地理データベース内の他の特徴とマッチングするために面による投票（face voting）が使用され、それによりマッチングした特徴から地域の割り当てを受け継ぐ。図９は、未知の地域名に関連付けられた地理データベース内の都市のブロック面の名称を判定するために使用される面による投票の一例を示す図である。実施形態において、ＴＩＧＥＲ名称供給元の有効範囲内の穴（holes）又はマッチングされていない地理特徴は、「面による投票」の処理により削除される。未知の都市名に関連付けられたブロック面を有する都市のブロックに対して、面による投票は、それを包囲するブロック面又はその所定のブロック面をそれ自体に接続するブロック面に対応する都市名に基づいて、ブロック面に対する都市名を判定する。図９は、都市のブロックに対する面による投票を示す。この場合、所定のブロック面に対して、面による投票に使用されるブロック面は、その所定のブロック面に隣接する２つのブロック面及びその所定のブロック面に対向する１つのブロック面である。図９に示すブロック面は、街路セグメントの各側である地理特徴としても見られる。実施形態において、隣接及び対向するブロック面は調べられ、割り当てられていない面が位置する支配的地域はその他の隣接及び対向する面の多数決により判定される。この処理は、County Subdivisionコード、Incorporated Placeコード及びそれらに関連付けられる名称を隣接及び対向する符号化地理特徴から任意の未符号化地理特徴に伝搬する。実施形態において、地理特徴はブロック面である。
【００４９】
例えば図９において、Center Streetの１つのブロック街路セグメントの北側は、それが地域名供給元内の任意の地域に関連付けられなかった地理特徴であるため、未知の都市名に関連付けられる。しかし、その他のブロック面、すなわちFirst Streetの１つのブロック街路セグメントの東側、Main Streetの１つのブロック街路セグメントの南側及びSecond Streetの１つのブロック街路セグメントの西側は、「Boston」に関連付けられることが判明している。ブロックに対するこれらの３つの街路セグメントのうち３つがBostonに関連付けられたため、面による投票は３／３であり、Center Streetは同様にBostonに関連付けられる。これらの３つの街路セグメントのうち２つがある特定の都市に関連付けられる場合、面による投票は２／３であり、Center Streetは同様にその特定の都市に関連付けられる。３つの街路セグメントがそれぞれ異なる都市に関連付けられる引き分けの場合、面による投票は１／３である。この場合は多数決が存在しないため、Center Streetは最も近接する隣接街路のうちの１つの都市に関連付けられる。本例において、これはFirst Street又はSecond Streetである。
【００５０】
実施形態において、面による投票は、街路セグメントの側又は道路エッジ等の都市のブロック面以外に他の地理特徴に対して使用可能である。実施形態において、面による投票は、未知の都市名に関連付けられた街路セグメント以外に２つ以上の他の街路セグメントの側に対して使用可能である。実施形態において、面による投票は、ブロック面のうち２つ以上が未知の都市名に関連付けられる場合に更に使用さてもよい。この場合、多数決は残りのブロック面により行われ、上述のように、多数決又は引き分けが判明して処理される。実施形態において、面による投票は、ブロック面を都市又は町以外の他の地域名に関連付けるために使用されてもよい。例えば、ＵＳＰＳ都市／州ファイル内の地域名は、５桁のＺＩＰコード及びＺＩＰ＋４ファイルからの１つの４桁コードである。
【００５１】
面による投票の他の実施形態は、多数決の代わりに重み付け投票又は直線長さによる投票を含む。重み付け投票を使用する実施形態において、地域に関連付けられない１つのブロック面に隣接するある特定のブロック面は、優先度を付与されるか又は投票処理においてより重く重み付けされる。重み付け投票は、隣接するブロック面の割り当ての信頼度を測定する任意の重み付け要素を有することができる。例えば優先度は、主要な街路に対応するブロック面に付与されてもよく、又はより広い範囲に位置するブロック面に付与されてもよい。ブロック面の長さは、別のそのような重み付けである。直線長さによる投票を使用する実施形態において、地域に関連付けられていない所定のブロック面の場合、その所定のブロック面に隣接するブロック面に関連付けられる既知の各地域に対して、ブロック面の全長が取得され、直線長さの全長が最長のブロック面を有する隣接ブロック面に関連付けられる地域が判定される。そして、この結果得られる地域は、地域に関連付けられていないその所定のブロック面に割り当てられる。
【００５２】
図８Ａを参照すると、ステップ８１５において、供給元が属性を地理データベースと共有しないため地図のマッチングが不可能な場合、実施形態では、ステップ８５５において供給元間名称マッチング（cross-source name matching）が採用される。供給元間名称マッチングは、供給元又は第１の供給元内の地域名と地理データベース内の地理特徴に既に直接関連付けられている別の供給元の地域名との間接的関連付けである。ステップ８５５において、地理データベース内の地理特徴に既に直接関連付けられている第２の供給元が第１の供給元に対してマッチングする地域名を有すると判明するため供給元間名称マッチングが可能な場合、ステップ８６０において、第１の供給元は第２の供給元にマッチングされる。ステップ８６５において、第１の供給元内の各地域名は地理特徴に対する関連付けを第２の供給元から受け継ぎ、それにより、その特定の地理特徴に間接的に関連付けられる。実施形態において、受け継がれる地理特徴の例は、街路セグメントの側、ブロック面及びフェリーの航路である。実施形態において、ＦＩＰＳ５５のデータは供給元間名称マッチングに対して有用な名称供給元である。例えば、Populated Placesの供給元に対するＧＮＩＳの地域は、州及び郡においてＦＩＰＳ５５供給元内の地域名に対してマッチングされる。マッチングが実行される場合、ＧＮＩＳの名称は、マッチングしたＦＩＰＳ５５の名称から街路セグメントの側に対する関連付けを受け継ぐ。以下に説明するように、ステップ８６５からステップ８３０へ進む。ステップ８５５において、供給元間マッチングが供給元に対して不可能な場合、この供給元は本処理において使用不可能であり、別の地域供給元を選択するためにステップ８１０に戻る。
【００５３】
実施形態において、種々の地域名供給元から取得された地域名は、重複する地域名及び異なる地域名を削除するために、トークン化、標準化、最適化及び／又はマッチング、マージ又は修飾表示される。好適な実施形態において、トークン化ステップ、標準化ステップ、最適化ステップ、マッチングステップ及びマージステップ又は修飾表示ステップの全てが実行される。この処理は、２つ以上の同様の名称を有する各地域の地域名数を減少する一方で、有意味に異なる地域名を更に保存する。これらのステップは、種々の供給元間の名称符号化における差異に対処する。種々の供給元からの同様の地域名の一例は、New JerseyのHo-Ho-Kus市であり、これは種々の地域名供給元において以下のように出現する。
ＴＩＧＥＲのレコード型Ｃ：Ho-Ho-KusTwnshp
ＵＳＰＳの都市／州ファイル：HoHo KUS Township
POI Center of Settlement：HO-HO-KUS
ＦＩＰＳ５５−３：Ho-Ho-Kus（Hohokus）
ＧＮＩＳ：Ho-Ho-Kus
【００５４】
図８Ａのステップ８２５及び８６５からステップ８３０へ進む。本実施形態では、ステップ８３０において、名称マッチング処理の第１の部分であるトークン化又は構文解析により、地域名は最大約１０個のトークン又は構成要素に分解される。多くの技術が地域名をトークン化するために使用可能である。このステップの目的は、索引化のために地域名の重要な構成要素又は部分、すなわち名称の「本体（body）」を取り出すことである。接頭部（prefix）又は接尾部（suffix）等のその他の構成要素は、それぞれ別個の構成要素になる。その後、地域名は索引においてトークンにより表され、それにより、アプリケーション開発者は名称の重要な部分を索引化できる。例えばAmherst及びSouth Amherstの双方は、要望に応じて索引の「A」の項に記載される。実施形態において重複する名称を削除することにより、エンドユーザは、メモリが制限されるアプリケーションにおいてより多くの名称にアクセスできるようになり、複数回提示される同一名称を見ることによりユーザが混乱することが防止される。
【００５５】
Ho-Ho-Kusに対する上記の最初の２つの地域名供給元からの地域名をトークン化することにより、NewJerseyの例では次の本体トークン及び接尾トークンが生成される：
本体：Ho-Ho-Kus、接尾部：Twnshp
本体：HO HO KUS、接尾部：Township
【００５６】
トークン化は、固有の名称を定義する構成要素を分離し、マッチング処理において無視可能なトークンを関連付けにより分離するのに有用である。大部分のエンドユーザは「Rutland」が「Rutland Township」とマッチングすること、すなわち用語「Township」が重要ではないものとして扱われることを望むだろう。同時に、大部分のエンドユーザは「Boston」が「South Boston」とマッチングしないこと、すなわち用語「South」が重要なものとして扱われることを望むだろう。トークン化の別の理由は、名称の重要な部分が索引化されることにより、エンドユーザに対して地域名を提示する際の融通性をソフトウェアアプリケーション開発者に提供することである。例えば、「Hollywood」及び「West Hollywood」をトークン化することにより、双方は「Hollywood」に対する地図探索を入力するエンドユーザに対して選択肢として提示される。これは、West Hollywoodが本体：Hollywood、接頭部：Westとしてトークン化され、他方、Hollywoodが本体：Hollywoodとしてトークン化されるため、双方の「本体」トークンが「Hollywood」になるからである。
【００５７】
別の実施形態において、トークン化は、文脈依存略語の正確な伸張の判定を助長する。例えば、地域の接頭部トークン「St.」は殆どの場合「Saint」を示す一方、地域の接尾部トークン「St.」は殆どの場合「State」を示す。
【００５８】
以下は、トークンの他の種類及びそれらのトークンの例である。
PreDirection−先頭の方向（「North」 Adams）
PreType−先頭の種類（「Lake」 Isabella）
Prefix−先頭だが方向又は種類ではない（「Old」 Orchard Beach））
PreName−本体前の種類ではない単語（lake 「of the」 woods）
Body−索引化のために使用される主要な部分（Lake 「Isabella」）
PostType−末尾の種類（Imperial 「Beach」）
PostDirection−末尾の方向トークン（Leisure Village 「West」）
Suffix−末尾だが方向又は種類ではない（Manchester 「By The Sea」））
Division−地域の分割を特定する数値識別子（Meredosia 「1」）
Adornment−地域名の位置を明確にするための郡名等の括弧の中に示される補足情報（Middletown「（Bethlehem）」）
【００５９】
実施形態では、図８Ａのステップ８３５において、一般に、トークン化ステップから取得されたトークンの標準化は以下の処理のうち１つ以上の処理を含む：略語の伸張、句読点の減少又は除去、一貫した文字（大文字又は小文字）の使用及び埋め込まれたスペースの除去。実施形態において、方向及び種類の標準的な略語は伸張される。例えば、方向の略語「N」は「北（North）」に伸張される。種類の略語の場合、例えば「Mt.」は「Mount」に伸張され、「AFB」は「空軍基地（Air Force Base）」に伸張される。異なる供給元において出現する名称が異なる方法で表されると仮定すると、略語の適切な標準化はマッチング処理に不可欠である。実施形態において、埋め込まれたスペース及び句読点は除去される。実施形態において、大文字の使用は、地域名のトークンに対して大文字又は小文字を一貫して使用することにより標準化可能である。実施形態において、大文字の使用は、各トークンの最初の文字のみを大文字にすることにより更に標準化可能である。更に、実施形態において、大文字の使用における差異は、標準化処理の代わりにマッチング処理において対処可能である。好適な実施形態において、大文字の使用は一貫した大文字に標準化される。New JerseyのHo-Ho-Kusの例を使用する場合、トークンの標準化により以下の結果が生成される：
本体：HOHOKUS、接尾部：TOWNSHIP
本体：HOHOKUS、接尾部：TOWNSHIP
【００６０】
以下の使用例では、地域索引に格納可能な特徴のトークン化及び標準化の利点を示す。地域索引の作成は以下に説明される。これらの特徴を索引において使用しない場合、異なる略語は異なる都市名として出現する。これらの特徴を索引において使用する場合、略語は共通の形態にされ、アプリケーション開発者はそのリストを単一の明確なエントリとすることができる。トークンの大文字使用は、マッチングを容易にするために一貫した大文字に標準化されるが、通常、トークンは各トークンの最初の文字のみが大文字の状態でユーザに提示される。
【００６１】
トークン化及び標準化された地域名を索引において使用しない場合：
都市(city)を入力 −〉 Randolph
以下より選択してください −〉
Randolph Hghts
Randolph Heights
Randolph Hts
トークン化及び標準化された地域名を索引において使用する場合：
都市(city)を入力 −〉 Randolph
以下が選択されました ： Randolph Heights
【００６２】
また、以下の使用例では、地域名における方向トークンのトークン化及び標準化の利点を示す。方向トークンを識別することにより、地域名は方向トークンではなく本体により索引化される。方向トークンが標準化されると、アプリケーション開発者は標準化されたトークンを調べるだけでよく、それらのトークンの略語を調べる必要はない。
【００６３】
トークン化及び標準化された地域名を索引において使用しない場合：
都市(city)を入力 −〉 Boston
見つかりました ： Boston
都市(city)を入力 −〉 South B
以下より選択してください −〉
South Bath
South Barrister
South Barnstable
South Boston
都市(city)を入力 −〉 S. Boston
都市が見つかりません ： “S. Boston”
都市(city)を入力 −〉 South Boston
見つかりました ： “South Boston”
トークン化及び標準化された地域名を索引において使用する場合：
都市(city)を入力 −〉 Boston
以下より選択してください −〉
Boston
South Boston
【００６４】
実施形態では、図８Ａのステップ８４０において、標準化ステップから取得された２つ以上の同様の地域名の最適化は、一般に、同様の地域名の各々を地域に含まれる地理特徴に関連付ける。地理特徴の例は、街路、街路セグメント、目印、州立公園、幹線道路、事業拠点及び居住地域を含む。New JerseyのHo-Ho-Kusの例において、HoHoKus及びHOHOKUSに対する同一の地理特徴が最適化により見つけられる。
【００６５】
図８Ａのステップ８４５において、主供給元マスクでは、その供給元マスク内の次のビットが供給元に割り当てられる。実施形態において、マスクは国において固有である。他の実施形態において、マスクは州又は大陸等の任意の地理地域に固有であってもよい。図１０は、米国及びカナダに対する地域名供給元マスクの２つの例を示す図である。実施形態において、供給元マスク内の各ビット位置は単一の地域名供給元を表す。マスクは、１つ以上の行政地域名供給元、郵便地域名供給元又は他の地域名供給元を含むことができる。マスクは国に固有であり、地域名供給元の優先順位を示さない。列「１０進ビット値」内の各ビット値に対して、列「地域名供給元」内の地域名供給元がビット値に割り当てられる。索引化のために、地域供給元マスクは、エンドアプリケーションに最適なように異なる種類の地域名を定義する融通性を可能にする。実施形態において、「トランプ」と示されるマスク内の供給元は、索引化のため、これらの供給元で見つけられる地域名を最優先するために使用可能である。地域名が出現する供給元を示す個別の供給元マスクが供給元内の地域名毎に更に作成される。
【００６６】
ステップ８５０において、供給元内の各地域名に対する供給元マスク内の次のビット位置はこの供給元に設定される。複数の供給元で出現する名称は、それらが出現する各供給元に対するマスクに設定された複数のビットを有する。例えば名称「Boston」は、同時にCounty Subdivision名、Administrative Place名及び多くのＺＩＰコードに対する好適な郵便名である。複数の供給元で出現しない名称は、供給元に対応するマスクに設定された単一ビットのみを有する。ステップ８１０に戻り、次の地域名供給元が存在する場合はそれを処理する。
【００６７】
図８Ａのステップ８１０において、処理する地域名供給元が残っていない場合、図８Ｂのステップ８６８へ進む。ステップ８６８において、使用可能な全供給元からの最適化済み名称はマッチングされる。使用可能な供給元は、ステップ８１５で地図のマッチングが可能だった供給元及び図８Ａのステップ８５５で他の供給元のマッチングが可能だった供給元である。実施形態において、マッチングは標準化されたトークンを連結して完全な名称にし、それらがマッチングすると考えられるかを判定するために比較する。実施形態において、地域名の大文字・小文字又は大文字使用の差異の標準化は、上述の標準化ステップではなく、この名称マッチングステップにおいて実行されてもよい。実施形態において、大文字・小文字を区別しないマッチング論理はこのマッチングステップにおいて使用可能である。実施形態において、米国の各州に対して、指定された供給元からの全地域名はマッチングされる。
【００６８】
多くの異なるアルゴリズムが名称マッチングに利用可能である。名称マッチング技術の例は、文脈依存マッチング、音声マッチング及びサウンデックス（Soundex）を含む。文脈依存マッチングは、名称の文字列マッチング又は名称の綴りのマッチングである。この種類のマッチングはマッチング中のトークンに関する知識を用いて実行され、これは特別なルールを可能にする。例えば本体トークンの場合、適切な文脈依存マッチングアルゴリズムは「John F. Kennedy」と「JohnFitzgerald Kennedy」とをマッチングできる。最適な文脈依存マッチングアルゴリズムは「MLK」と「Martin Luther King」とをマッチングできる。一方、音声マッチングは、単語の綴りではなく単語の音をマッチングする。例えば、「fish」及び「Phish」は音声学的にマッチングする。種々の言語における名称マッチングの場合、異なる音声マッチングアルゴリズムが使用可能である。サウンデックスは、英語で発音された場合の音により名称を索引化する音声アルゴリズムである。基本的な目的は、同一の発音を有する名称が同一の文字列に符号化されることにより、綴りの小さな差異に関わらずマッチングが実行されることである。音声アルゴリズムに関するより詳細な情報は、２００６年３月１６日に出願されたJesse Sheridanによる米国特許出願第１１／３７７，７６４号公報「Geographic Feature Name Reduction Using Phonetic Algorithms」に記載されている。
【００６９】
実施形態において、２つの完全な名称（full name）がマッチングするためには、文字列が正確にマッチングする必要がある。実施形態において、完全な名称がマッチングしない場合、本体トークンのマッチングが試される。正確なトークンマッチングのためには、本体トークンがマッチングしなければならず且つ方向トークン及び種類トークンが更にマッチングしなければならない。従って、トークンのマッチングは一方又は双方の先頭トークンから開始しなくてもよく、一方のトークンは他方のトークンの先頭の部分文字列である必要がある。従って、トークンのマッチングは、ある特定のトークンを更に無視する必要がある。実施形態において、綴りの小さな差異は２つのマッチングする名称間で許容される。実施形態において、誤ったマッチングを防止するため、名称マッチングはかなり保守的に実現される。従って：
「North Boston」は「South Boston」とマッチングしない
「South Boston」は「Boston」とマッチングしない
「Township of Rutland」は「Rutland Township」とマッチングする
【００７０】
図８Ｂのステップ８７０において、ステップ８６８で見つけられたマッチングした地域名の全セットが処理される。マッチングした地域名の各セットは、重複するか又は若干異なる名称を有する地域である。ステップ８７０において、マッチングした地域名の別のセットが存在する場合、ステップ８７２において、マッチングした名称がオーバーラップする配置を表すかを判定する。ステップ８７２において、地域がオーバーラップする場合又は地域が互いに隣接するだけの場合であっても、それらが少なくとも１つの地理特徴を共有することが最適化ステップ８４０で判定される限り、マッチングした名称はオーバーラップする配置を表す。
【００７１】
図８Ｂのステップ８７２において、マッチングした名称がオーバーラップする配置を表し、ステップ８７３において、配置が完全にオーバーラップする場合、ステップ８７４において、重複する名称は１つを除いて地理データベース内の地域索引エントリから削除される。１つの地域名に関連付けられる全地理特徴が別の地域名に関連付けられる全地理特徴と同一の場合、これらの地域名は完全に重複するものであり、１つを除いて全てが削除される。地域名が同一の地域を表す時且つその時に限り、地域名は削除される。このステップにおいて、重複する地域は削除され、地域名セットは減少される。多くの重複するエントリを有する地域索引に対して、この技術は索引化の量及び索引が必要とするスペースを大幅に減少する。New JerseyのHo-Ho-Kusの例において、各名称に対して１つに連結された標準化済みトークンは共に「HOHOKUS TOWNSHIP」である。これらの２つの地域名は、全地理特徴が共通することが最適化ステップから判定されるため、これらの地域名は完全に重複するものであり、一方が削除される。その後ステップ８７０に戻り、マッチングした地域名の別のセットが存在するかを判定する。
【００７２】
図８Ｂのステップ８７３において、配置が完全にオーバーラップしない場合又は地域が別の地域、通常は若干異なる名称を有する地域と少なくとも１つの地理特徴を共有するが全地理特徴を共有しない場合、これらの地域は同一の地域であると見なされ、ステップ８７５においてマージされる。例えば、Vermontの「Randolph」及び「Randolph Center」は２つの別個のものだがオーバーラップする町である。２つの町がオーバーラップするため、これらは少なくとも１つの地理特徴を共有し、同一の地域であると見なされてマージされる。
【００７３】
実施形態において、地域名のマージは、オーバーラップする地域が互いに区別されない、オーバーラップしない特徴を有さない場合にのみ実行される。例えば、Randolph及びRandolph Centerの双方が街路番号のオーバーラップしないMain Streetを有する場合、２つの町はマージ可能である。しかし、双方の町が例えば「2 Main Street」を有する場合、町をマージしてはいけない。
【００７４】
以下の使用例は、オーバーラップする配置を有する複数の供給元からの重複する地域名のうち１つを除いて全てを削除することの利点を示す。この特徴を使用しない場合、地域名は、ユーザに対して提示される選択肢に複数列挙される。
【００７５】
重複する地域名を削除しない場合：
都市(city)を入力 −〉 Hanover
以下より選択してください −〉
Hanover (County subdivision)
Hanover (Administrative place)
Hanover (03755)
重複する地域名の削除後：
都市(city)を入力 −〉 Hanover
見つかりました ： “Hanover”
【００７６】
以下の使用例は、若干異なる名称を有する地域をマージすることの利点を更に示す。マージしない場合、ユーザは、若干異なる名称のうちどの名称が所望の目的地の位置する地域であるか分からないことがある。マージすることにより、ユーザは名称を区別する必要がない。例えば地域「Randolph」、「Randolph Center」及び「Randolph Township」はオーバーラップするため、単一の名称「Randolph」により表される共通の地域にマージされる。従って、ユーザが探索する場合：
マージしない場合：
都市(city)を入力 −〉 Randolph
街路(street)を入力 −〉 Main Street
以下より選択してください −〉
Main street, Randolph
Main street, Randolph Center
Main street, Randolph Township
マージする場合：
都市(city)を入力 −〉 Randolph
街路(street)を入力 −〉 Main Street
見つかりました ： “Main Street, Randolph”
【００７７】
図８Ｂのステップ８７６において、マッチングした名称から取得される全特徴の和集合（union）はマージされた名称に割り当てられる。例えばＦＩＰＳ５５において、BostonというCounty Subdivisionはある特定の地理を定義する。BostonというAdministrative Placeは、オーバーラップするが必ずしも同一ではない他の地理を定義する。BostonというPostal Placeは、米国の手紙が配達可能な街路を範囲に含む地理の第３のセットを定義する。これらの異なる特徴の和集合を作成することにより、Bostonに関連付けられる特徴の完全なセットが形成される。Bostonに関連するこれらの各名称に関連付けられる地理特徴の和集合は、それらの各供給元を含む地理特徴の集合を含む。例えば、エンドユーザがAdams St.に注目する場合、Adams St.はPostal PlaceであるBostonの一部ではないが、種々の地域名供給元のマッチングした地域名からの地理特徴の和集合によりBostonというCounty Subdivisionの一部になるため、ユーザはAdams St.を見つけられる。従って、各名称が見つけられる供給元に対応する供給元マスクに設定されたビット及び各名称が適用される全地理特徴の和集合を用いることにより、唯一の地域名から成るリストが取得される。その後ステップ８７０に戻り、マッチングした地域名の別のセットが存在するかを判定する。
【００７８】
図１１は、地域名のマッチングにより地域名セットを減少するアルゴリズムの一実施形態を示す図である。地域名供給元内の各地域名Ａの場合、名称Ａにマッチングする任意の他の供給元内の各名称Ｂに対して、Ｂに関連付けられた任意のセグメント街路の側であって、Ａにまだ割り当てられていない側をＡに割り当てる。これは、上述の図８Ｂのステップ８７６である。供給元マスクＡにまだ含まれていない供給元Ｂ内の任意のビットを含み、Ｂを削除する。
【００７９】
図８Ｂのステップ８７２において、マッチングした名称がオーバーラップする配置を表さない場合、ステップ８７８において、マッチングした名称は明確にするために修飾表示される。オーバーラップする配置を表さないマッチングした名称は、重複するか又は若干異なる名称を有する物理的に異なる地域である。実施形態において、これらの物理的に異なる地域は、米国の１つの州内に位置する都市である。多くの州は、同一又は若干異なる名称を有する複数の都市を有する。一般に、重複する名称を有するそのような地域は州内の異なる郡に存在する。従って、地域が位置する郡名等の修飾を示すことにより、ユーザはこれらの重複する名称を区別できる。通常、地域の修飾は地域名の次に括弧又は引用符の中に示される。しかし、郡名又は他の境界の修飾は、地元ではないユーザが認識できない場合がある。その代わり、重複する名称を有する各地域の近隣の容易に認識可能な大都市名は、より適切な情報をユーザに提供する。従って、ステップ８７８において、ステップ８７２から取得される各名称に対して、別個の都市の修飾が地域索引に格納される。この種類の修飾の作成に関するより詳細な情報は、２００６年２月１日に出願されたMichael Geilichによる米国特許出願第１１／３４５，８７７号公報「Method for Differentiating Duplicate or Similarly Named Disjoint Localities within a State or other Principle Geographic Unit of Interest」に記載されている。その後ステップ８７０に戻り、マッチングした地域名の別のセットが存在するかを判定する。
【００８０】
以下の使用例は、重複するか又は若干異なる名称を有する異なる地域に対する修飾を示す：
郡名を用いて修飾表示する場合：
州(state)を入力 −〉 PA
都市(city)を入力 −〉 Bethel
以下より選択してください −〉
Bethel (Berks)
Bethel (Allegheny)
Bethel (Lancaster)
Bethel (Mercer)
Bethel (Sullivan)
Bethel (Wayne)
近隣の容易に認識可能な大都市名を用いて修飾表示する場合：
州(state)を入力 −〉 PA
都市(city)を入力 −〉 Bethel
以下より選択してください −〉
Bethel (Fredericksburg)
Bethel (Pittsburgh)
Bethel (Lancaster)
Bethel (Youngstown)
Bethel (Willamsport)
Bethel (Scranton)
【００８１】
この使用例において、アプリケーションは、更なる情報をユーザに要求する前に各ユーザエントリを処理する。他の実施形態において、「近隣の容易に認識可能な大都市名を用いて修飾表示する場合」に対して、ユーザが州名、都市及び街路名を入力し、その後アプリケーションがこれらの３つのユーザエントリを処理する場合、その所在地住所が選択肢のうち１つの選択肢においてのみ見つけられるならば、唯一つの目的地が判定される。例えば：
近隣の容易に認識可能な大都市名を用いて修飾表示する場合：
州(state)を入力 −〉 PA
都市(city)を入力 −〉 Bethel
街路名(street name)を入力 −〉 Main Street
見つかりました ： “Main Street, Bethel (Fredericksburg)”
【００８２】
ステップ８７０において、マッチングした地域名の別のセットが存在しない場合、図８Ｂのステップ８８０において、索引が作成される。最初に、索引は地理特徴により配列される。地理特徴を含む地域は、地理特徴毎に優先順位で索引化される。索引内の地域名は優先順位により配列され、それによりアプリケーション開発者は、任意の地理特徴に対して最も一般的な名称の集合をアプリケーションにプログラムできる。これにより、例えばメモリが制限される環境において、最も一般的な名称が選択するためにエンドユーザに提供される。各地理特徴に対して２つの地域名のみを格納可能なメモリが制限されるデバイスの場合、アプリケーション開発者は地域索引を使用して、３つ以上の地域に関連付けられる地理特徴に対してユーザに対する優先順位が最も高い地域を選択できる。同様に、ボトムアップ式探索アプリケーションの場合、アプリケーションは、住所又は地理特徴をユーザに要求し、ユーザが選択に使用する地域リストを提示する。地域リストを提示する場合、住所に関連付けられる最高優先順位の名称が使用可能である。
【００８３】
実施形態において、地理特徴に関連付けられる地域の優先順位は、対象のアプリケーションに対する、各地域名の慣用的な使用における普及度に基づく。実施形態において、慣例に基づく優先順位付けにより、地域名は異なるユーザに対して異なる方法で配列される。「New York City」、「Manhattan」及び「SoHo」等のオーバーラップする地域の例の場合、慣例において、その地域に精通する地元ユーザは、３つの地域のうちより特定の地域、すなわち「SoHo」を使用する可能性が高い。アプリケーションがこの地元ユーザに対するものである場合、最高優先順位の地域名は、地域名が見つけられる供給元数が最も少ない地域名である可能性が高い。従って、優先順位の降順は「SoHo」、「Manhattan」、その次に「New York City」となる。
【００８４】
New York City内のオーバーラップする地域の同一の例を使用する場合、慣用的な使用において、局所地域に精通しない地元ではないユーザは、より有名であり且つ容易に認識可能な地域を使用する可能性が高い。アプリケーションがこの地元ではないユーザに対するものである場合、最高優先順位の地域名は、地域名が見つけられる供給元数が最も多い地域名である可能性が高い。従って、優先順位の降順は「New York City」、「Manhattan」、その次に「SoHo」となる。
【００８５】
実施形態において、アプリケーションにおける優先順位を判定するアルゴリズムは、ユーザに対する異なる慣例（慣用的な使用）に適合するように異なる方法で適用可能である。例えば、大都市等の地域内でナビゲートしている地元ユーザの場合、地元ユーザの慣用的な使用に基づく地域名の優先順位を所望するだろう。しかし、同一のユーザが同一の大都市に遠方からナビゲートする場合、地元ではないユーザに対する慣用的な使用に基づく異なる優先順位を所望するだろう。しかし、大都市に到達し、境界を越えて都市の中に入ると、ユーザは優先順位を地元ユーザの優先順位に戻したいだろう。
【００８６】
多くの異なる優先順位配列方式が可能である。好適な実施形態において、地理特徴に関連付けられる最高優先順位の地域は、好適な郵便名供給元で見つけられる地域であり、残りの地域の優先順位は、各地域供給元マスクに設定されたビット数により判定される。実施形態において、第１の地域が慣用的な使用においてより有名又は一般的な場合、第１の地域は第２の地域より高い優先順位を有する。実施形態において、地域名の優先順位は、その名称が見つけられる供給元の数により判定される。地理特徴に対して優先順位の最も高い地域名は、最も多くの供給元で見つけられる地域名であり、従って、供給元マスクに設定されたビットが最も多い地域名である。地理特徴に対する地域名の優先順位は降順である。
【００８７】
実施形態において、アプリケーション開発者は供給元マスクを更に使用して、ある特定の地域名供給元を他の供給元より優先することにより、このデフォルトの優先順位方式を変更できる。他の実施形態において、優先順位は、地域の最大物理的大きさ又は地域の最大人口に関して定義される。他の実施形態において、優先順位は、地域における地理特徴、例えば街路セグメントの最大数として定義される。他の実施形態において、優先順位は、地域内に位置する地理特徴の数ではなく、地域内に位置する主要な地理特徴の最大数に関して更に定義可能である。主要な地理特徴の一例は重要な幹線道路である。実施形態において、優先順位は、ある特定の地域名供給元の他の供給元に対する優先度を判定するために、地域名供給元マスクを使用して定義可能である。実施形態において、アプリケーション開発者は、図１０において「トランプ（trump）」と示される地域供給元からの地域名を最高優先順位の名称として使用できる。
【００８８】
実施形態において、地域の優先順位が同等の場合、１次ソートが上記の方式のうちの１つを使用して実行され、必要な場合は２次ソートが上記の方式のうちの１つに基づいて実行される。好適な実施形態において、１次ソートは、各地域が見つけられる供給元数に対して降順で実行される。２次ソートは、例えば、各地域に含まれる地理特徴数又は街路セグメント数の降順に基づく。
【００８９】
図１２は、所定の地理特徴に対する地域名の優先順位を判定するアルゴリズムの一実施形態を示す図である。地理データベース内の街路セグメントの各側Ｓに対して、Ｓが割り当てられる全ての地域名Ａを見つける。各Ａに対して、供給元マスクに設定されたビットが最も多い名称Ａを見つける。この街路セグメントの側Ｓの索引において、次に優先順位の高い名称にＡを割り当てる。
【００９０】
図８Ｂの処理はステップ８９０において終了する。
【００９１】
図１３は、特徴／地域／優先順位テーブル、地域名テーブル及び特徴探索テーブルを含む地域索引ファイルの一実施形態を示す図である。これらのテーブルは、最終的にデータベースに格納される。実施形態において、図１３の特徴／地域／優先順位テーブルは、各地理特徴に対する優先順位によりに地域を列挙する。実施形態において、テーブル内の各地理特徴は特徴ＩＤ番号FF_IDに関連付けられる。特徴ＩＤ番号は連続してもよいが、必ずしも連続しなくてもよい。また、特徴ＩＤ番号は特徴探索テーブルへのリンクである。実施形態において、テーブル内の各地理特徴に関連付けられる各地域は、地域ＩＤ番号NAME_IDに更に関連付けられる。地域ＩＤ番号は連続してもよいが、必ずしも連続しなくてもよい。PRIORITYフィールドは、地理特徴に関連付けられる地域名の普及度を示す。上述のように、各地理特徴に関連付けられる地域名に優先順位付けするための多くの優先順位方式が存在する。PRIORITYは、最優先順位である「１」から開始する連続数である。テーブルは、上述のように、この地域に対する地域名供給元マスクLOC_MASKを更に含む。
【００９２】
地域索引の形式が可変であることにより、特徴／地域／優先順位テーブル内の各地理特徴に対して任意の数のテーブルエントリを含むことができる。北アメリカにおいて、これは郵便名のために特に重要である。一般に、好適な郵便地域名は各場所に対して１つのみ存在するが、郵政公社は、同一の場所に対して任意の数の許可される郵便地域名を更に含む。地域索引は、各地理特徴に対する全ての好適な郵便名及び許可される郵便名を含む。
【００９３】
実施形態において、図１３の地域名テーブルは、地域ＩＤ番号NAME_IDを介して特徴／地域／優先順位テーブルにリンクされる。本実施形態において、このテーブルは、混在する大文字及び小文字を使用する地域の完全な名称FULL_NAMEを更に含む。実施形態において、ＦＩＰＳ５５で表されるような完全な地域名は、このテーブル内の完全な地域名の最終符号化に使用される。しかし、完全な地域名を表す他の供給元が使用されてもよい。テーブルのNAME_KEYフィールドは、索引化するための地域名の重要な構成要素である。実施形態において、NAME_KEYは上記の地域名をトークン化及び標準化することにより見つけられる。これにより、例えば「Hollywood」及び「West Hollywood」の双方の本体トークンが「Hollywood」になるため、双方を索引の「H」の項に記載できる。ADORNMENTフィールドは、地域近隣の容易に認識可能な大きな場所又は都市の地域名を含む地域名テーブル内の別のエントリに対するポインタである。実施形態において、地域が州等の国の一次下位区分内の曖昧な地域である場合にのみ、ADORNMENTはテーブルに格納される。実施形態において、修飾は、ユーザのデバイス又はシステム上のリスト内の重複する地域を区別するために使用される。
【００９４】
NAME_LCフィールドは、地域名の言語に対する３文字コードである。実施形態において、NAME_LCは、名称の母国語を示して多言語の国に対応するため、地域名毎に設定される。実施形態において、NAME_LCは任意の数の文字である。LOC_SIZEは、この地域名に関連付けられる地理特徴の数を示し、特徴／地域／優先順位テーブルにおいて供給されるデフォルトの優先順位方式を変更するためにアプリケーション開発者により使用される。COUNTRYは国コードであり、地域が位置する国の３文字略語である。実施形態において、COUNTRYは、国際標準化機構により最初に発行されたＩＳＯ３１６６規格の一部であるＩＳＯ３１６６−１等の規格国コードであってもよい。実施形態において、COUNTRYは任意の数の文字である。CENTER_IDは、この地域に対して地理データベース内の他の場所で見つけられる都心部の特徴へのリンクである。実施形態において、これらの都心部の特徴は、地域センター点の緯度及び経度座標、並びに都心に対応する街路セグメントである。特定の所在地住所が要求されないか又は見つけられない場合、都心は地域内の点をユーザに提供する。
【００９５】
実施形態において、図１３の地域名テーブルは地域に関する多くの他の有用な種類の情報を含むことができる。例えば、地域名テーブルに音素を含むことは、テキスト読み上げアプリケーションに対して有用である。この場合、音素は認識上等価である音声又は符号要素の集合である。地域名テーブルに格納可能な異なる種類の情報の他の例は、地域の市役所の写真及び地域の警察署の電話番号である。
【００９６】
実施形態において、図１３の特徴探索テーブルは各地理特徴に関する情報を含む。FF_IDは、地理特徴情報を特徴／地域／優先順位テーブルにリンクするために使用される特徴ＩＤ番号である。FEAT_TYPEは、道路特徴に対する「R」及びフェリー航路特徴に対する「F」等の地理特徴の種類である。FEAT_IDは、街路名及び住所範囲等の地理データベース内の特徴に関する情報へのリンクである。FEAT_IDは、地点情報等の地理データベースにリンクされる他のコンテンツへの間接的リンクを更に提供する。SIDEは地理特徴の側、例えば街路エッジである。SIDEは、右側に対する「R」、左側に対する「L」、両側に対する「B」及び「適用不可能」に対する「null」を含む。
【００９７】
実施形態において、地域索引は、独自仕様の地理データベースとの統合を容易にするために、国際形式を含む複数の形式で提供される。地域索引は、任意の国からのデータを収容するために提供される。形式が一般化される一方、内容は、各国において適切な特定の地域供給元及び種類を含むように適合される。独自仕様のアプリケーションは、各地域名の正確な発音を提供する。
【００９８】
実施形態において、地域索引テーブルを使用するために住所の探索がトップダウン式で実現される場合、最初に地域が決定され、その後、正確な地理特徴が地域内で見つけられる。ナビゲーションアプリケーションは最初に名称マッチングを実行し、地域名テーブルにおいて所望の地域名を見つける。地域が見つけられると、特徴／地域／優先順位テーブルは選択された地域のNAME_IDを使用して探索され、その地域に含まれる地理特徴が判定される。それらの特徴のFF_IDは、街路セグメントの場合の街路名及び住所範囲等のある特定の特徴を見つけるために必要なそれらの特徴に関する情報を検索するための特徴探索テーブルに対する索引として使用され、その後、所望の特定の地理特徴を選択するためにマッチングが実行される。例えば、[都市(city)を入力 −〉 Boston]が入力される。「Boston」は地域名テーブル内の名称にマッチングされ、「Boston」に対するNAME_IDが返される。[街路(street)を入力 −〉 Adams]が入力される。特徴／地域／優先順位テーブルは、NAME_IDが「Boston」に対するNAME_IDであるFF_IDのリストを求めて探索される。特徴探索テーブルは、地理データベースにおいて「Adams」を示すFEAT_IDを求めて探索される。その後、所望の番地がユーザに要求され、特徴探索テーブルは、地理データベースにおいて要求された番地を含む住所範囲を示すFEAT_IDを求めて探索される。例えば、ユーザに対してナビゲーションアプリケーション又はデバイス上に特徴の場所を表示するため、特徴探索テーブルは、地理データベースにおけるこの特徴に対する緯度及び経度点を示すFEAT_IDを求めて探索されてもよい。性能を向上するため、多くの場合、地域索引はこれらの間接的参照の多くを削除するために事前にコンパイルされる。
【００９９】
実施形態において、地域索引テーブルを使用するために住所の探索がボトムアップ式で実現される場合、最初に目的の地理特徴のリストが選択され、その後、特徴を含む全地域のリストから所望の地域をその名称により決定することにより、正確な地域が選択される。ナビゲーションアプリケーションは、最初にマッチングを実行し、特徴探索テーブル内の地理特徴リストを見つける。その後、特徴探索テーブルから取得される対応するFF_IDは特徴／地域／優先順位テーブルに対する索引として使用される。これらのFF_IDに対する優先順位テーブル内のエントリは、地域名テーブルにおける名称が所望の地域にマッチングするNAME_IDを求めて走査される。アプリケーション開発者が地域の選択肢をユーザに提示したい場合、アプリケーションは地域のNAME_IDを優先順位で考慮し、考慮中のFF_IDに対して固有である最高優先順位の地域名を選択する必要がある。その後、これらの名称は選択対象としてユーザに提示される。トップダウン式の場合と同様に、多くの場合、地域索引はテーブル間の間接的参照の多くを削除するために事前にコンパイルされる。
【０１００】
実施形態において、地域索引は、地点情報及び目印等の名称が付けられた場所を見つけるために使用可能である。最初に、そのような場所のリストは、独自仕様の地理データベースから取得される街路セグメントに関連付けられる。その後、アプリケーションは、所望の地点情報又は目印の名称をマッチングして街路セグメントを見つける。次にアプリケーションは、正確な地域を判定するために街路セグメントを使用する上述の住所探索の実現例を使用する。
【０１０１】
実施形態において、地域索引は、都心を見つけるために使用可能である。アプリケーションは、地域名テーブル内のFULL_NAME及びNAME_KEYを使用して所望の地域の名称をマッチングし、テーブル内の正確なエントリを見つける。正確なエントリが見つけられると、都心に対応する緯度座標及び経度座標又は街路セグメント等、地理データベース内の対応する独自仕様の地域センター情報を見つけるためにCENTER_IDフィールドが使用される。
【０１０２】
実施形態において、地域索引は、名称が重複するが地理が異なる地域を明確にするために使用可能である。アプリケーションは、地域名テーブル内のFULL_NAME及びNAME_KEYを使用して所望の地域の名称をマッチングし、テーブル内の正確なエントリを見つける。例えば地域が「Brentwood, California」の場合、図４に示すように、２つのマッチングする地域が見つけられる。この場合、地域名テーブルから取得されるADORNMENT、例えば「Los Angels」及び「San Francisco」という修飾は、Brentwoodの各地域に対して使用される。これらは、ユーザに対して「Brentwood (LosAngels)」及び「Brentwood (San Francisco)」として表示され、ユーザはこれらから選択できる。
【０１０３】
実施形態において、地域索引は、住所特徴における曖昧さを解決するために使用可能である。例えば図３の「2 Adams Street」の例の場合、アプリケーションは、MassachusettsのBostonの地域内で見つけられる４つの「2 Adams Street」という住所を区別するために、各特徴に対するPRIORITYにより配列された複数の地域名を使用する。最初にアプリケーションは、特徴探索テーブルのFEAT_IDフィールドを使用して、地理データベースにおいて重複する住所に対応する住所セグメントを見つける。次にアプリケーションは、特徴探索テーブルにおいて対応するFF_IDを見つける。その後、FF_IDは特徴／地域／優先順位テーブルに対する索引として使用される。各FF_IDエントリに対して固有のNAME_IDが見つけられるまで、地域はPRIORITYを使用して優先順位の降順に検索される。NAME_IDは、重複する各住所に対する固有の地域名であるFULL_NAMEを検索するために、地域名テーブルに対する索引として使用される。「2 Adams Street」の例において、固有の地域名はCharlestown、HydePark、Roxbury及びDorchesterで見つけられる。これらは全てMassachusettsのBostonの隣接地域である。
【０１０４】
実施形態において、地域索引は、トップダウン式アプリケーションにおいて要求された特徴に対する近隣地域を探索するために使用可能である。いくつかの例において、所望の特徴は、ユーザにより特定される地域で見つけられない場合があり、ナビゲーションアプリケーションは探索を近隣地域又はより多くの内容を含む地域に拡大したい。最初にアプリケーションは、地域名テーブルにおいて所望の地域の名称をマッチングし、対応するNAME_IDを検索する。この地域のNAME_IDを含み且つ要求された特徴に対応するFF_IDが特徴／地域／優先順位テーブル内に存在しないと判定した後、アプリケーションは、このNAME_IDを含む１つ以上のFF_IDを特徴／地域／優先順位テーブルにおいて見つける。特徴／地域／優先順位テーブル内のこれらのFF_IDに対して、それらのFF_IDに対応する他のNAME_IDを検索するため、優先順位を昇順又は降順に辿ってもよい。要求された住所がこれらの他の関連する地域のいずれかの中に存在するかを判定するため、特徴探索テーブルは調べられる。
【０１０５】
実施形態において、以下の使用例は、地域索引の優先順位付けされた特徴の利点を示す。優先順位付けを行わない場合、ユーザにクエリする際に最も認識可能な名称をどのようにして使用するかがアプリケーション開発者に対して不明瞭である。いくつかの場所においては郵便名が最も一般的である。他の地域においては行政名が有名である。優先順位付けされた特徴を用いる場合、最も一般的な名称が選択可能である。
【０１０６】
優先順位付けを行わない場合：
街路(street)を入力 −〉 Broadway
以下より選択してください −〉
Broadway (Charlestown, MA)
Broadway (Manhattan, NY)
優先順位付けを行う場合：
街路(street)を入力 −〉 Broadway
以下より選択してください −〉
Broadway (Boston, MA)
Broadway (New York, NY)
【０１０７】
実施形態において、図１４に示すような更なる使用例において、ナビゲーションアプリケーションは、近隣の都市が誤って特定された場合の矛盾に対処できる。一般に、Chicago等の大都市は郊外に囲まれる。郊外は分離され、それ自体の行政構造を有する。特に、それらの地域名は異なる場合が多い。ユーザは、郊外の地域を意識せずに大きな中心都市のみを考えている可能性がある。図１４に示すように、一例はChicago北部の郊外で見つけられる。ユーザがLincolnwoodの「BrynMawr Country Club」の場所を見つけたいが地域をChicagoとしてしか知らないとする。所在地住所が「6600 North Crawford Ave.」であることをユーザが知っている場合、入力は以下のように進む：
州(state)を入力 −〉 Illinois
都市(city)を入力 −〉Chicago
街路(street)を入力 −〉North Crawford Avenue
【０１０８】
ナビゲーションアプリケーションは、ここで矛盾を確認する。最初にアプリケーションは、特徴／地域／優先順位テーブルにおいてNAME_IDがChicagoを示す全てのFF_IDを探索する。アプリケーションは、「North Crawford Avenue」がChicagoに存在しないことを確認する。アプリケーションは、特徴／地域／優先順位テーブルにおいてFF_IDが「North Crawford Avenue」を示す全てのFF_IDを探索する。アプリケーションは、LincolnwoodのChicago郊外に「North Crawford Avenue」を見つける。アプリケーションが複数の地域に「North Crawford Avenue」を見つけた場合、アプリケーションは、特徴／地域／優先順位テーブルにおいてPRIORITYを使用して、このFF_IDに対して最高優先順位の地域名を使用する。アプリケーションは、「South Crawford Avenue」がChicagoに存在することを確認できる。その後アプリケーションは街路番号を要求する：
街路番号(street number)を入力 −〉 6600
Find:“6600 North Crawford Avenue, Lincolnwood, Illinois”
【０１０９】
本例において、正確な街路番号が双方の場所で見つけられた場合、アプリケーションは、「6600 South Crawford Avenue, Chicago」又は「6600 North Crawford Avenue, Lincolnwood」を選択するようにユーザに提案できる。街路番号「6600」がChicagoの「South Crawford Avenue」で見つけられないため、この住所選択はユーザに対して表示されない。「North Crawford Avenue」に対して見つけられた街路番号「6600」がChicagoではなくLincolnwoodに位置する場合であっても、アプリケーションは、ユーザが要求した住所はこれであると想定できる。
【０１１０】
実施形態では、更なる使用例において、アプリケーションは街路又は都市に対するユーザの入力のうちの一方が矛盾していて修正する必要のある場合に対処できる。チャンドラー音楽堂（Chandler Music Hall）のウェブサイト上の住所は「71-73 Main Street, Randolph, Vermont」である。Randolph市において、Main Streetは「North Main Street」及び「South Main Street」に分割される。「Main Street」は、近隣の町であるRandolph Centerに更に存在する。エンドユーザに対して、街路が実際にMain Streetであるならば、音楽堂はRandolph Centerになければならない。音楽堂がRandolphにあるならば、それはNorth Main Street又はSouthMain Streetに位置する。実際は、音楽堂はRandolphの71 North Main Streetに位置する。エンドユーザがトップダウン式アプリケーションにおいてウェブサイトの住所を使用している場合、ユーザはRandolphからNorth Main Street又はSouth Main Streetに正確に誘導されるが、街路番号71が双方の街路に存在するため、アプリケーションはユーザに決定するように要求する。ユーザがボトムアップ式アプリケーションにおいてウェブサイトの住所を使用している場合、Main streetからRandolph Centerに不正確に誘導される。実施形態において、ナビゲーションアプリケーションがこの種の状況に対処するための１つの方法は、全選択肢をユーザに提示することである。
【０１１１】
州(state)を入力 −〉Vermont
都市(city)を入力 −〉Randolph
街路(street)を入力 −〉Main Street
街路番号(street number)を入力 −〉 71
以下より選択してください −〉
71 North Main Street, Randolph
71 South Main Street, Randolph
71 Main Street,Randolph Center
【０１１２】
実施形態において、本発明の１つ以上のステップは自動的に実行される。自動化された特徴は、適切なソフトウェアを使用して実現される。自動化された特徴は、地域索引が作成される効率及び速度を大幅に増加する。
【０１１３】
変更された本発明の実施形態は、ナビゲーションアプリケーション及びデバイス以外に適用可能である。例えば、空間的な職業別電話帳アプリケーションにおいて、ある点からの距離によりソートされたある特定の種類の全事業を見つけることは望ましい。実施形態において、この種類のアプリケーションに対する地域の索引化は、職業別電話帳ディレクトリにおける出現頻度に基づく優先順位方式を使用してもよい。
【０１１４】
図１５は、本発明の実施形態と共に使用可能なシステム９００の一例を示すブロック図である。この図は構成要素を論理的に別個のものとして示すが、そのような描写は例示のためにすぎない。この図に示される構成要素が別個のソフトウェア構成要素、ファームウェア構成要素及び／又はハードウェア構成要素に組み合わされるか又は分割されてもよいことは当業者には明らかだろう。更に、そのような構成要素が組み合わされ又は分割される方法に関わらず、それらが同一の演算装置／システム上で実行してもよく、あるいは１つ以上のネットワーク又は他の適切な通信手段により接続される異なる演算装置／システムに分配されてもよいことも当業者には明らかだろう。
【０１１５】
図１５に示すように、通常、システム９００は演算装置９１０を含む。演算装置９１０は、任意の種類の１つ以上のメモリ９１２、１つ以上のプロセッサ９１４及び１つ以上の記憶装置又はリポジトリ９１６を具備してもよい。システム９００は表示装置９１８を更に含んでもよい。表示装置９１８は、表示装置９１８上で動作するグラフィカルユーザインタフェース又はＧＵＩ９２０を含み、これにより、システムは地図及び他の情報をユーザに対して表示できる。ユーザは演算装置を使用して、例えば、地域が地図上に表示されること、あるいは運転指示が地図上のルート及び／又はテキスト指示として表示されることを要求する。ＧＵＩ９２０は、「Washington, New Jersey」に対する一対の重複する地域の一例、並びにそれらの修飾「Easton」及び「Hammonton」を表示する。ユーザは、ＧＵＩ９２０に表示するために重複する地域のうちの一方を選択する。
【０１１６】
地理データベース９３０は演算装置又はシステム９１０に対する外部記憶装置として示されるが、いくつかの例において、地理データベース９３０は記憶装置９１６と同一の記憶装置であってもよい。実施形態において、地域名エントリは、地理データベース９３０内の重複する地域及び異なる地域９３２に対してマージされる。実施形態において、地理データベース９３０は地域供給元の主供給元マスク９３４を含む。実施形態において、特徴／地域／優先順位テーブル、地域名テーブル及び特徴探索テーブルを含む地域索引９３６は地理データベース９３０に格納される。
【０１１７】
独自仕様の地理データベース作成ソフトウェア９４０は、重複する地域名及び異なる地域名のエントリ９３２をマージ及び／又は修飾表示し、地域供給元の主供給元マスク９３４を作成し且つ地域索引９３６を作成するために、実世界の地域名の供給元及び定義９６０を使用できる。実世界の地域の供給元及び定義の例は、図２の説明において上述した。地理データベース９３０からの情報は、地理データベース／アプリケーション変換器及びデバイスアプリケーションソフトウェア９５０により使用され、これは最終的に演算装置９１０のユーザにより使用される。地理データベース／アプリケーション変換器及びデバイスアプリケーションソフトウェア９５０は、ユーザの演算装置９１０に対してリモートであるように示されるが、ユーザの演算装置９１０に常駐してもよい。
【０１１８】
インターネット上又はナビゲーションデバイス上でユーザにより使用されるような地理データベース／アプリケーション変換器及びデバイス／アプリケーションソフトウェア９５０の一例の場合、ユーザは地図上に表示される地域を選択できる。あるいは、例えばユーザが運転指示を要求する場合、地域は開始地域又は終了地域のいずれであってもよい。
【０１１９】
実施形態において、ユーザにクエリするソフトウェアアプリケーションの種類は、トップダウン式又はボトムアップ式のドリルダウン式アプリケーションである。ドリルダウン法は、メモリが制限される自動車用ナビゲーションシステムにおいて有用である。メモリが制限されるデバイスに対して有用な実施形態において、アプリケーション開発者は、高い優先順位に位置付けられる地域名のみをデバイスに含むことができる。トップダウン式アプリケーションは、最初に主要な地理特徴、例えば州（state又はprovince）を入力するようにユーザに要求する。次にアプリケーションは、主要な地理特徴に位置する地域、例えば都市又は町を入力するようにユーザに要求する。その後アプリケーションは、地域内の街路名を入力するようにユーザに要求する。最後にアプリケーションは、街路番号を入力するようにユーザに要求する。殆どの場合、クエリの結果、アプリケーションにより、例えばユーザに対して表示装置９１８のＧＵＩ９２０に地域を表示することにより、ユーザに対して明確な地理データベースの特徴が特定される。ボトムアップ式アプリケーションは、最初に番地及び街路名を入力するようにユーザに要求する。次にアプリケーションは、そのような住所が見つけられる全地域を表示する。最後にアプリケーションは、所望の地域の名称を選択又は入力するようにユーザに要求する。ボトムアップ方法の結果、通常、明確な地理データベースの特徴が同様に特定され、これはその後アプリケーションにより使用される。
【０１２０】
実施形態において、アプリケーションソフトウェアは地理データベースの索引をドリルダウン式アプリケーションにおいて使用でき、それによりエンドユーザは、通常は所定の州内に存在する地域名の一部又は全部を入力できる。実施形態において、アプリケーションは、ユーザの入力にマッチングする名称をエンドユーザに提示し、ユーザは最適な選択肢を選択する。トークン化された名称の本体に対してマッチングを行うことにより、アプリケーションは、「Hollywood」の任意の最初の文字がエンドユーザにより入力された場合に「Hollywood」及び「West Hollywood」の双方を提示できる。
【０１２１】
他の実施形態において、ソフトウェアプリケーションはドリルダウン式アプリケーションではなく、その代わりに街路番号及び街路、地域、並びに主要な地理特徴をユーザに同時にクエリする。殆どの場合、クエリの結果、明確な地理データベースの特徴が特定され、場所がユーザに返される。ユーザが街路名「Main Street」及び地域「Springfield」を入力する場合、重複する地域「Springfield」が「Main Street」という名称の街路を同様に有するならば、その重複する地域は見つけられる。重複する地域が地理特徴に対して存在する場合、地域及びそれらの修飾のリストは、１つを選択するようにユーザに要求するためにユーザに対して表示装置９１８のＧＵＩ９２０等に表示される。「Washington, New Jersey」に対する１対の重複する地域の例の場合、２つの地域は、それらが見つけられる郡又は近隣の大都市名と共に修飾表示される。「Easton, New Jersey」及び「Hammonton, New Jersey」はそれぞれ、２つの重複する地域の近隣の大都市である。従って、「Washington (Easton), NJ」及び「Washington (Hammonton), NJ」は図１５のＧＵＩ９２０に表示される。本例において、修飾は括弧の中に提示されるが、重複する各地域をそれぞれの修飾から分離するために句点を使用する等の他の方法で提示されてもよい。ユーザは重複する地域の一方を選択し、その後、地図上の地域又は運転指示はユーザに対して表示される。
【０１２２】
ソフトウェア分野の当業者には明らかなように、適切なソフトウェア符号化は、本開示の教示に基づいて、熟練したプログラマにより容易に準備される。また、当業者には容易に明らかとなるように、本発明の実施形態は、特定用途向け集積回路を準備するか又は従来の構成要素回路の適切なネットワークを相互接続することにより実行されてもよい。
【０１２３】
本発明の実施形態は、本発明の実施形態の任意の処理を実行するようにコンピュータをプログラムするために使用可能な命令が格納された記憶媒体であるコンピュータプログラム製品を含むことができる。記憶媒体は、フロッピディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ及び光磁気ディスクを含む任意の種類のディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリ素子、磁気カード又は光カード、分子記憶ＩＣを含むナノシステム、あるいは命令及び／又はデータを格納するのに適した任意の種類のシステム又は素子を含むことができるが、これらに限定されない。
【０１２４】
任意のコンピュータ可読媒体に格納される場合、本発明の実施形態は、汎用／専用コンピュータ又はマイクロプロセッサのハードウェアの双方を制御し且つコンピュータ又はマイクロプロセッサが本発明の実施形態の結果を利用して人間のユーザ又は他の機構と対話ソフトウェアを含むことができる。そのようなソフトウェアは、デバイスドライバ、オペレーティングシステム及びユーザアプリケーションを含んでもよいが、それらに限定されない。最終的に、そのようなコンピュータ可読媒体は、上述のように本発明の実施形態を実行するソフトウェアを更に含む。
【０１２５】
本発明の教示を実現するソフトウェアモジュールは、汎用／専用コンピュータ又はマイクロプロセッサのプログラミング又はソフトウェアに含まれる。コンピュータ分野の当業者には明らかなように、本発明の実施形態は、本開示の教示に従ってプログラムされた従来の汎用又は専用デジタルコンピュータ又はマイクロプロセッサを使用して良好に実現されてもよい。
【０１２６】
本発明の上記説明は、例示及び説明のために与えられた。これは、全ての実施形態を含むこと又は本発明の実施形態を開示される形態に限定することを意図しない。多くの変更及び変形は当業者には明らかだろう。実施形態は、本発明の原理及びその実際の用途を最適に説明し、それによって他の当業者が、種々の実施形態に対して及び考えられる特定の使用に適した種々の変更を用いて本発明を理解できるようにするために選択及び説明された。本発明の範囲は、以下の請求の範囲及びその均等物により定義されることが意図される。
【図面の簡単な説明】
【０１２７】
【図１】慣用的な使用において一貫して扱われない地域定義の一例を示す図である。
【図２】米国の行政区分の階層を示す図である。
【図３】「Boston, Massachusetts」等の地域内の４つの異なる地域に位置する「Adams Street」等の同名の住所を区別する必要がある例を示す図である。
【図４】複数種類の地域名供給元を使用することにより区別される「Brentwood, California」等の公的な地域及び同名の近郊の一例を示す図である。
【図５】「Quechee, Vermont」等の公的な供給元に列挙されることもあるが明確に引かれた境界を有さず、包括的な地域索引に含む必要のある小さな村の一例を示す図である。
【図６】New York Cityの「Greenwich Village」等の公的ではない地域名だが包括的な地域索引に含む必要のある近郊の一例を示す図である。
【図７】New York CityのQueens区の「Forest Hills」等の区に位置し、包括的な地域索引に含む必要のある村の一例を示す図である。
【図８Ａ】地域を地理データベース内の地理特徴にリンクし、地域名をトークン化、標準化、最適化及びマッチングし且つ地域が優先順位により配列された索引を作成する処理のフローチャートの一実施形態を示す図である。
【図８Ｂ】地域を地理データベース内の地理特徴にリンクし、地域名をトークン化、標準化、最適化及びマッチングし且つ地域が優先順位により配列された索引を作成する処理のフローチャートの一実施形態を示す図である。
【図９】未知の地域名に関連付けられた街路の地域名を判定するために使用される面による投票の一例を示す図である。
【図１０】米国及びカナダに対する地域名供給元マスクの２つの例を示す図である。
【図１１】地域名のマッチングにより地域名セットを減少するアルゴリズムの一実施形態を示す図である。
【図１２】所定の地理特徴に対する地域名の優先順位を判定するアルゴリズムの一実施形態を示す図である。
【図１３】特徴／地域／優先順位テーブル、地域名テーブル及び特徴探索テーブルを含む地域索引ファイルの一実施形態を示す図である。
【図１４】近隣の都市が誤って特定された場合にナビゲーションアプリケーションが矛盾に対処できる一例を示す図である。
【図１５】実施形態と共に使用可能なシステムの一例を示すブロック図である。
【図８Ａ】
2009537049.tif 000003
【図８Ｂ】
2009537049.tif 000004
【図９】
2009537049.tif 000005
【図１０】
2009537049.tif 000006
【図１１】
2009537049.tif 000007
【図１２】
2009537049.tif 000008
【図１３】
2009537049.tif 000009
【図１５】
2009537049.tif 000010
【図１】
2009537049.tif 000011
【図２】
2009537049.tif 000012
【図３】
2009537049.tif 000013
【図４】
2009537049.tif 000014
【図５】
2009537049.tif 000015
【図６】
2009537049.tif 000016
【図７】
2009537049.tif 000017
【図１４】
2009537049.tif 000018
【国際調査報告】
2009537049.tif 000019