アフィニティのための地図データを編成する方法及びそれを使用するためのアプリケーション
【課題】行先を特定するためにナビゲーションシステム又は他のコンピューティングプラットホームのアプリケーションに使用できるインデックス方法を提供する。
【解決手段】アフィニティ関係インデックス、及びこれを使用する方法が開示される。アフィニティ関係インデックスは、所与の場所の名前に対し、1つ以上の潜在的により重要な場所の名前に対するアフィニティを捕える。このようなより重要な各場所は、他の場所がその中にあると思われるところのアフィニティドメインを抱いている。インデックスは、これをハイアラーキー式に保持し、そしてユーザが意図する行先に対して迅速にサーチできる比較的意義のある且つ最小の構造体を生成するという作用を有する。アプリケーションは、これらのアフィニティドメインを使用して、案内される旅程に乗り出すに必要なインストラクションを決定するのであって、旅程を完了するに必要な全てのインストラクションを決定するのではない。
【解決手段】アフィニティ関係インデックス、及びこれを使用する方法が開示される。アフィニティ関係インデックスは、所与の場所の名前に対し、1つ以上の潜在的により重要な場所の名前に対するアフィニティを捕える。このようなより重要な各場所は、他の場所がその中にあると思われるところのアフィニティドメインを抱いている。インデックスは、これをハイアラーキー式に保持し、そしてユーザが意図する行先に対して迅速にサーチできる比較的意義のある且つ最小の構造体を生成するという作用を有する。アプリケーションは、これらのアフィニティドメインを使用して、案内される旅程に乗り出すに必要なインストラクションを決定するのであって、旅程を完了するに必要な全てのインストラクションを決定するのではない。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、場所を特定する方法に係り、より詳細には、行先を特定するためのナビゲーションシステム又は他のコンピューティングプラットホームのアプリケーションに使用できるインデックス方法に係る。
【背景技術】
【0002】
ナビゲーションに関係した機能が種々の異なるコンピュータプラットホームに設けられている。例えば、ナビゲーションに関係した機能は、スタンドアローンシステム又はネットワークシステムと共に設けることができる。スタンドアローンシステムでは、ソフトウェアアプリケーション、地理的データ及びハードウェアが単一の位置において結合される。スタンドアローンシステムは、乗物にインストールしてもよいし又は個人が携帯してもよい。ネットワークシステムでは、ソフトウェア又は地理的データのあるものは、ユーザを伴うハードウェアと共に配置され、そしてソフトウェア又は地理的データのあるものは、遠隔に配置されて通信システムを経てアクセスされる。ナビゲーションに関係した機能は、専用プラットホームで実施されるシステムにより与えられ、ここでは、ハードウェア及びソフトウェアがナビゲーション目的で特に設計される。或いは又、ナビゲーションに関係した特徴を与えるシステムは、適切なソフトウェアアプリケーション及びデータを使用して汎用のコンピューティングプラットホーム(例えば、パーソナルコンピュータ、パーソナルデジタルアシスタント、又はネットワーク型コンピュータ)において実施することができる。
【0003】
ナビゲーションアプリケーションを実行する専用のナビゲーションシステム及び汎用のコンピューティングプラットホーム(以下、集合的に「ナビゲーションシステム」と称する。)は、種々様々な有用な特徴及びサービスを提供する。例えば、乗物に使用されるナビゲーションシステムは、所望の行先へ運転するための詳細なインストラクションを与え、走行時間及び経費を減少することができる。又、ナビゲーションシステム及びナビゲーションアプリケーションは、所望のタイプの会社をサーチし、そしてその会社の位置へのルート案内を与えることもできる。
【0004】
これらのシステムに関連した1つの事柄は、ユーザがどのようにしてシステムに場所を特定するかに関する。例えば、ユーザが行先へのルートをたどるためにナビゲーションシステムから案内を得たいときには、ユーザが何らかの手段によりシステムに行先を指示することが必要である。行先を特定する機能は、種々の理由で複雑なものとなる。多くのシステムは、行先の正確な位置がユーザにより完全に指示されるまで、ルートを計算しなかったり、案内を与えない。しかしながら、ある場合には、ユーザは、都市や街路の正確なつづりを知らないことがある。都市や町が同じ又は同様の名前をもつときには、別の複雑さが考えられる。
【発明の開示】
【発明が解決しようとする課題】
【0005】
従って、ユーザがシステムに行先のような位置を特定できる方法を改善することが要望される。例えば、計算されたルートを得るためにユーザが行先を特定する方法を改善することが要望される。
【課題を解決するための手段】
【0006】
これら及び他の目的に対処するために、本発明は、ナビゲーションシステムに対する迅速且つ便利な行先入力及び案内を可能にするようなデジタル地図データを編成するための実施形態を包含する。2つの関連するコンポーネントが含まれる。その第1は、所与の場所の名前に対し、1つ以上の潜在的により重要な場所の名前に対する密接な関係(アフィニティ:affinity)を捕える仕方で場所の名前をインデックスする手段である。このようなより重要な各場所は、他の場所がその中にあると思われるところのアフィニティドメインを抱いている。これは、ハイアラーキー式に保持され、そしてユーザが意図する行先に対して迅速にサーチできる比較的意義のある且つ最小の構造体を生成するという作用を有する。第2のコンポーネントは、これらのアフィニティドメインを使用して、案内される旅程に乗り出すに必要なインストラクションを決定するのであって、旅程を完了するに必要な全てのインストラクションを決定するのではない。
【発明を実施するための最良の形態】
【0007】
I.地理的データベース形成の概要
図1は、地理的データベースのマスター即ちソースバージョン100を示す。地理的データベースのマスターバージョンは、地理的データベースデベロッパー101(「地図デベロッパー」、「地図データデベロッパー」等とも称される。)により所有され、開発される。(1つのソースデータベース及び地理的データベースデベロッパーしか示されていないが、ここに示す実施形態は、単一のソースデータベース又は単一の地理的データベースデベロッパーに限定されない。)
【0008】
地理的データベースのマスターバージョン100は、地理的カバレージエリアにおける特徴を表わすデータ102(「地理的データ」又は「空間的データ」とも称される。)を含む。地理的カバレージエリアは、米国のような国全体に対応してもよい。或いは又、地理的カバレージエリアは、多数の国々、例えば、米国、カナダ及びメキシコ、或いはフランス、ドイツ及びイタリア、等々に対応してもよい。別の態様によれば、地理的データベースのマスターバージョン100の地理的カバレージエリアは、国内の単一領域、例えば、米国のウェストコースト又はミッドウェストを表わすだけでもよい。地理的データベースのマスターバージョン100は、全地理的カバレージエリアにおける地理的特徴を表わすデータを含むが、地理的データベースのデータにより表わされない地理的特徴を含むか、又は地理的特徴の表示が希薄であるような地理的カバレージエリアの部分も存在し得る。
【0009】
地理的データベースのマスターバージョン100は、地理的カバレージエリア内に位置する道路網に関するデータを含む。道路網に関するデータは、色々な種類の情報、例えば、道路の位置の地理的座標、道路のストリート名、道路に沿った住所範囲、道路の交差点における転回制限、等々を含む。又、地理的データベースのマスターバージョン100は、カバーされた地理的エリアにおける関心のあるポイントに関するデータも含む。関心のあるポイントは、ホテル、レストラン、美術館、スタジアム、オフィス、自動車販売店、自動車修理店、等々を含むことができる。地理的データベースのマスターバージョン100は、これら関心のあるポイントの位置に関するデータを含むことができる。又、地理的データベースのマスターバージョン100は、都市、町、又は他のコミュニティのような場所に関するデータや、水域、山脈等の他の地理的特徴を含むこともできる。更に、地理的データベースのマスターバージョン100は、他の種類の情報を含んでもよい。
【0010】
データを収集するために種々の方法が地理的データベースデベロッパー101により使用されている。これらの方法は、自治体や航空写真のような他のソースからデータを得ることを含む。更に、地理的データベースデベロッパー101は、現場要員を雇って地理的領域全体にわたり道路に沿って乗物で走行し、特徴を観察すると共に、それらに関する情報を記録することができる。地理的データベースデベロッパー101により収集されたデータは、地理的データベースのマスターバージョン100に記憶される。
【0011】
地理的データベースデベロッパー101は、地理的カバレージエリアにおける特徴を表わすデータを進行形態で収集し続ける。地理的データベースデベロッパーがデータを収集し続ける1つの理由は、カバレージエリアにおける特徴が時間と共に変化するからである。従って、地理的データベースデベロッパー101は、特徴に関する以前に収集したデータを更新又は確認するために、その同じ特徴に関するデータを収集する。地理的データベースデベロッパー101がデータを収集し続ける別の理由は、地理的データベースのマスターバージョン100のカバレージ及び/又は詳細を拡張するためである。例えば、ある時点に、地理的データベースのマスターバージョン100は、全カバレージエリアの一部分だけを表わすデータを含んでもよい。その時点以降に、地理的データベースデベロッパー101は、以前に表わされなかったエリアにおける特徴に関するデータを収集し、地理的データベースのマスターバージョン100のカバレージを拡張する。
【0012】
地理的データベースのマスターバージョン100は、地理的カバレージエリアに関する最新のデータを有するコピーとして維持される。従って、地理的データベースのマスターバージョン100は、規則的で且つ連続的なベースで、更新され、拡張され、及び/又はその他変更される。これらのオペレーションを容易にするために、地理的データベースのマスターバージョン100は、更新、維持、及び開発を容易にするフォーマットで記憶される。例えば、マスターバージョン100のデータは、非圧縮でもよい。適当なフォーマットは、例えば、バーチャル・ストレージ・アクセス・メソッド(VSAM)フォーマットを含むが、他の種類のフォーマット、独占的及び非独占的の両方、も適している。一般に、マスターデータベース100のフォーマットは、ナビゲーションシステムに使用するのには適していない。
【0013】
一実施形態では、地理的データベースのマスターバージョン100は、1つ以上のハードドライブ、テープ又は他の媒体の位置に記憶され、そして適切なコンピュータでアクセスされる。メインフレームコンピュータ、複数のネットワーク型マイクロコンピュータ等の適当なコンピュータを使用することができる。
【0014】
地理的データベースのマスターバージョン100からのデータは、コンパイルされたデータベース製品110を形成するのに使用される。このコンパイルされたデータベース製品110は、コンパイラー111を使用して作られる。コンパイラー111は、適当なコンピュータプラットホームで実行されるソフトウェアプログラムである。コンパイルされたデータベース製品110は、地理的データベースデベロッパー101により形成されてもよいし、或いは別のエンティティ、例えば、地理的データベースデベロッパーからデータを取得するか又はライセンス契約する地理的データベースデベロッパーの顧客により形成されてもよい。コンパイルされたデータベース製品を形成する前に、地理的データベースのマスターバージョン100からのデータは、GDFフォーマットのような1つ以上の中間フォーマットにコンパイルされ又は配送されてもよい。
【0015】
コンパイルされたデータベース製品110は、地理的データベースのマスターバージョン100における全データの一部分のみを含んでもよい。例えば、コンパイルされたデータベース製品110は、地理的データベースのマスターバージョン100のカバレージエリア内の1つ以上の特定のサブエリアのみに関連したデータを含んでもよい。更に、コンパイルされたデータベース製品110は、地理的データベースのマスターバージョン100で表わされる地理的特徴を記述する全てのデータ属性より少数のものを含んでもよい。
【0016】
コンパイルされたデータベース製品110において、地理的データは、地理的データベースのマスターバージョン100の場合とは異なる仕方で編成される。コンパイルされたデータベースは、それがインストールされるコンピューティングプラットホームにおけるデータの使用を容易にする形態で編成され、配列され、構造化されそして記憶される。例えば、コンパイルされたデータベース製品110では、データは、特定の機能を実行するに必要な属性のみを各々含む個別のデータ集合体118へと編成されてもよい。例えば、1つのデータ集合体は、ルート計算を実行するのに必要な属性のみを含み、別の集合体は、ポジショニングに必要な属性のみを含み、又、更に別の集合体は、行先選択に必要な属性のみを含んでもよい。
【0017】
又、コンパイルされたデータベース製品110は、地理的データの集合体を異なるレベル又はスケールで含んでもよい。例えば、1つのデータ集合体は、カバレージエリア内の全ての道路を含んでもよく、そして同じデータベースの別のデータ集合体は、より高い機能クラスの道路、即ち制御されたアクセス道路のような比較的高い交通量を輸送する道路、のみを含んでもよい。
【0018】
又、コンパイルされたデータベース110は、データ集合体の幾つかを空間的に編成してもよく、即ち物理的に互いに接近した地理的特徴が、データベース内で互いに接近配置されたデータにより表わされるように編成してもよい。
【0019】
コンパイルされたデータベースは、マスター地理的データベース100に見られないデータエンティティを含んでもよい。例えば、コンパイルされた地理的データベース110は、マスター地理的データベース100内の多数の異なるデータエンティティの複合体であるか、又はマスター地理的データベース100内のデータエンティティから導出されたものであるデータエンティティを含んでもよい。
【0020】
又、コンパイルされたデータベース製品は、それが位置する媒体に圧縮フォーマットで記憶されてもよい。
又、コンパイルされたデータベースは、1つ以上のインデックス120を含んでもよい。種々のデータ集合体を互いに関連付けるインデックス、データをそれが記憶された媒体において見つけるためのインデックス、及びデータ集合体内で特定の情報を見つけるためのインデックスを含む種々の形式のインデックス120が含まれてもよい。
【0021】
地理的データをコンピューティングプラットホームに使用するように編成できる幾つかの仕方が、参考としてここに全開示を援用する米国特許第5,953,722号、第5,968,109号、第5,974,419号、第6,038,559号、第6,112,200号、第6,081,803号、第6,118,404号、第6,122,593号、第6,184,823号、第6,249,742号、第6,308,177号、第6,324,470号、第6,336,111号、第6,393,149号、第6,460,046号、第6,473,770号、第6,507,850号、第6,591,270号、第6,600,841号、第6,751,629号、第6,768,818号、第6,782,319号、及び第6,829,690号に説明されている。
【0022】
II.コンピューティングプラットホームにおける地理的データの使用
コンパイルされたデータベース製品110は、色々な種類のコンピューティングプラットホーム122において使用される。コンピューティングプラットホーム122は、乗物内ナビゲーションシステム、ハンドヘルドポータブルナビゲーションシステム、パーソナルコンピュータ(デスクトップ及びノードブックコンピュータを含む)、及び他の種類のデバイス、例えば、パーソナルデジタルアシスタント(PDA)デバイス、ページャー、電話等を含む。又、コンパイルされたデータベース製品110は、インターネットに接続されたシステムを含むネットワーク型コンピューティングプラットホーム及び環境にも使用される。
【0023】
コンピューティングプラットホーム122に使用されるコンパイルされたデータベース製品110は、適当な媒体に記憶される。例えば、コンパイルされたデータベースは、CD−ROMディスク、ハードドライブ、DVDディスク、フラッシュメモリ、メモリカード、或いは現在入手できるか又は将来入手できるようになる他の形式の媒体に記憶することができる。
【0024】
コンピューティングプラットホーム122では、コンパイルされたデータベース製品110が種々のソフトウェアアプリケーションにより使用される。例えば、コンパイルされたデータベース製品110は、ナビゲーションに関連した機能、例えば、ルート計算、ルート案内、乗物のポジショニング、地図表示、及び電子的イエローページ、並びに他の種類の機能を与えるソフトウェアアプリケーションにより使用することができる。
【0025】
図2は、コンピューティングプラットホーム122の幾つかのコンポーネントを示すブロック図である。図2に示すコンピューティングプラットホーム122は、ナビゲーション用の幾つかのコンポーネントを含むものである。コンピューティングプラットホーム122は、ポジショニングシステム134を備えている。このポジショニングシステム134は、ポータブルナビゲーションシステム130の現在位置を決定する。ポジショニングシステム134は、いかなる位置感知装置又は技術により実施されてもよい。例えば、ポジショニングシステムは、GPSユニット、或いは到着時間、到着方向、三角法、WiFi、RFID、Loran、デッドレコニング(dead reckoning)、或いはこれら又は他のシステムの組み合せを使用するシステムを含んでもよい。
【0026】
この実施形態では、コンピューティングプラットホーム122は、ナビゲーションアプリケーション132を備えている。このナビゲーションアプリケーション132は、ナビゲーションに関連するか又は地図に関連したある機能を実行するソフトウェアプログラムである。これらのナビゲーションアプリケーション132は、コンピューティングプラットホーム122における適当なデータ記憶媒体に記憶される。ナビゲーションアプリケーション132は、必要なときに実行される。ナビゲーションアプリケーション132間に含まれるのは、ルート計算アプリケーション136、ルート案内アプリケーション140、地図表示アプリケーション144、ポジショニングアプリケーション148、及び行先選択アプリケーション152である。他の実施形態は、これらアプリケーションをより多く又はより少なく有してもよい。或いは又、ある実施形態では、これらアプリケーションの2つ以上を組み合せてもよい。
【0027】
コンピューティングプラットホーム122は、コンパイルされたデータベース製品110の1つを含む。コンパイルされたデータベース製品110は、コンピューティングプラットホーム122においてデータ記憶媒体164に記憶される。コンパイルされたデータベース製品110は、ナビゲーション関連機能を与えるためにナビゲーションアプリケーション132により使用される。地図データベース160は、カバーされた地理的エリアにおける道路、交差点、関心のあるポイント、及び他の地理的特徴に関する情報を含む。カバーされた地理的エリアは、1つ以上の都会エリア、州、国、領域又はその組み合せを含んでもよい。
【0028】
ナビゲーションアプリケーション132は、一緒に機能しコンパイルされたデータベース製品110を使用して、色々な種類のナビゲーション機能を与える。例えば、ナビゲーションアプリケーションは、所望の行先へのルートを得るのに使用できる。この例によれば、ユーザは、行先選択アプリケーション152を使用して、所望の場所を見つけることができる。ルートの出発点は、ポジショニングシステム134と一緒に使用されるポジショニングアプリケーション148により決定されるユーザの位置であると仮定される。所望の行先の位置及び出発点の位置を指示するデータは、ルート計算アプリケーション136へ転送される。このルート計算アプリケーション136は、出発点から行先までのルートを決定し、次いで、ルートを指示するデータをルート案内アプリケーション140へ転送する。ルート案内アプリケーション140は、ルートをたどるためにユーザに適した方向を発生する。
【0029】
コンピューティングプラットホーム122を使用し、ユーザをルートに沿って行先へ案内するときには、ユーザが位置するエリアのグラフィック地図をユーザに示すことが有用である。地図表示アプリケーション144は、この目的で使用することができる。地図表示アプリケーション144は、ルート計算アプリケーション136からルートを指示するデータを受け取ると共に、ポジショニングアプリケーション148からユーザの現在位置を指示するデータを受け取る。地図表示アプリケーション144は、コンパイルされたデータベース製品110からのデータにアクセスして、ユーザの現在位置の周りの地理的エリアのグラフィック地図像を発生する。地図表示アプリケーション144は、コンピューティングプラットホーム122のディスプレイスクリーンに像をレンダリングし、ユーザの現在位置の周りの地理的エリアを示す。像は、ユーザの付近に位置する道路を示してもよい。ユーザの現在位置を指示するために、インジケータマークを像に重畳してもよい。又、ユーザがたどるべきルートを、ハイライトにより、像において指示してもよい。
【0030】
III.アフィニティ関係インデックスの形成
図3A、3B及び3Cは、アフィニティ関係インデックス202を形成するためのプロセス200を示す。プロセス200は、適当なコンピューティングプラットホーム122に使用される地図データベース製品110を形成するときにコンパイラー111(図1)により実行されるコンパイルプロセスの一部分でよい。プロセス200は、ソースデータベース204からのデータを使用する。ソースデータベース204は、マスター地理的データベース100、又はこのソースデータベース100から派生したデータベース、例えば、中間、交換又は配送フォーマットのデータベースでよい。プロセス200は、ソースデータベース204からのデータを入力として使用し、そして1つ以上のアフィニティ関係インデックス202の形態で出力を与える。アフィニティ関係インデックス202は、コンパイルされた地理的データベース製品110を形成するときに作られる図1のインデックス132の1つに含まれてもよい。
【0031】
プロセス200は、カバーされた領域内の各自治体に対して実行される一連のステップを含む。(説明上、自治体という語は、種々の形式の法的に編成されたコミュニティ、例えば、市、町、村、等を含む。)図3Aを参照すれば、プロセス200は、ソースデータベース204のカバレージ領域で表わされた全ての自治体から1つの自治体を選択する(ステップ208)。選択された自治体に対して、プロセスは、自治体の管理境界に対応する多角形内の人口を指示する情報をソースデータベース204からアクセスする(ステップ210)。次いで、プロセスは、ソースデータベース204にアクセスし、その多角形内に位置する道路網におけるノード(即ち交差点)の数Nのカウントを決定する(ステップ220)。次いで、プロセスは、ソースデータベース204にアクセスし、そして自治体の管理境界に対応する多角形内に包囲された道路のキロメーター数Kを計算する(ステップ230)。次いで、プロセスは、ソースデータベース204にアクセスし、そして自治体の管理境界に対応する多角形の道路横断の数Rをカウントする(ステップ240)。
【0032】
ソースデータベース204から得られ又は導出されたこの情報を使用して、プロセスは、自治体に対する重要値Iを計算する(ステップ250)。プロセスは、次の式を使用する。
I=APαxBNβxCKγxDRδ
但し、Pは、自治体の管理境界多角形内の人口であり、Nは、同じ多角形内に存在する道路網におけるノードの数であり、Kは、多角形内に含まれる道路のキロメーター数であり、そしてRは、多角形の境界が道路を横断する数である。大文字の係数及び小文字の指数は、重要度インデックスIの値を調整するのに使用されるチューニング変数である。
【0033】
プロセスが自治体に対する重要値を計算すると、その重要値に対する地理的な位置が決定される(ステップ260)。この実施形態では、自治体の管理境界に対応する多角形の中心の地理的座標が決定されて、重要値の地理的位置として使用される。重要値を指示するデータ、重要値に関連した中心位置、及び自治体の認識が、一時的に記憶される(ステップ270)。この目的のために、一時的データベース280又はスクラッチファイルを使用してもよい。プロセス200は、ソースデータベース204により表わされたカバーされた領域における別の自治体を選択するように進み(ステップ290)、そしてソースデータベース204にアクセスして自治体に関する情報を得ると共に、重要値及びその重要値に対する関連位置(即ち中心)を計算するに必要な情報を導出するという同じステップ(即ち、ステップ210、220、230、240、250及び260)を実行する。この自治体に対する重要値、その関連位置、及びその関連自治体を識別する情報が記憶される(ステップ270)。このプロセスは、カバーされた領域における全ての自治体に対する重要値及びそれに関連した位置を決定して記憶するように続けられ、やがて、全ての自治体に対する重要値及びそれに関連した位置が計算されて一時的データベース280に記憶される(ステップ290)。
【0034】
ソースデータベース204で表わされた全ての自治体に対して重要値及びそれに対応する位置が決定されて記憶された後、プロセス200は、ソースデータベース204で表わされた自治体に対してアフィニティ関係のインデックスを決定することで続けられる。アフィニティ関係を決定する際に、プロセスは、各自治体間の距離と組み合せて各自治体に対して決定された重要値を使用して、アフィニティ関係インデックスのどのレベルを自治体が占有するか、及び他の地自体のどれが所与の自治体とのアフィニティ関係を有するか決定する。
【0035】
図3Bは、アフィニティ関係のインデックスを決定するためのプロセス200のステップを示す。このプロセスは、最も大きな重要値を決定しそしてそれに関連した自治体を選択することで継続される(ステップ300及び310)。この自治体に対するアフィニティドメインが計算される(ステップ320)。このアフィニティドメインは、自治体に関連した位置、この実施形態では、自治体の管理境界により形成される多角形の中心、からの距離関数である値(即ち、アフィニティ値)を各ポイントが有するような円形領域を画成する。自治体の中心の位置にあるこのアフィニティ値は、自治体に対して決定される重要値に対応する。又、この値は、自治体に対するアフィニティドメインの最大値でもある。自治体に対するアフィニティ値は、あらゆる方向に等しく先細りとなる。アフィニティ値の先細りの割合は、指数関数、双曲線関数、又は他の適当な関数により定義することができる。
【0036】
アフィニティドメインを画成するのに使用される関数に基づいて、アフィニティ値は、自治体の中心からの距離関数として減少し続ける。自治体の中心からのある距離において、アフィニティ値は、所定の最小スレッシュホールド値TMINに対応する値へと先細りになる。アフィニティ値が最小閾値(スレッシュホールド値)TMINに到達する位置は、その自治体に対するアフィニティドメインの水平境界を定義する(ステップ330)。ある実施形態では、大きな都市に対するアフィニティドメインの水平境界は、都市のより大きな都会エリア、即ち都市とその郊外にほぼ対応してもよい。
【0037】
図4は、自治体、即ち都市Aに対して計算されたアフィニティドメインを示す。このアフィニティドメインは、自治体の中心に位置する重要値に対応するピーク値を有することに注意されたい。アフィニティドメインは、ピークから最小閾値(スレッシュホールド)へと軸対称に先細りとなる。
【0038】
再び図3Bを参照すれば、プロセスは、次いで、そのアフィニティドメインの地理的エリア(即ち足跡)内に包囲された他の自治体に関連した全ての重要値位置を決定する(ステップ340)。図5は、アフィニティドメイン内に位置する重要値位置を有する他の自治体を決定するステップを示す。図5において、都市B、C、D、E、G及びHは、都市Aのアフィニティドメイン内に位置する重要値を有する。都市Fの重要値は、都市Aのアフィニティドメイン内にないことに注意されたい。(簡単化のために、図5では、6つの自治体が都市Aのアフィニティドメイン内に重要値位置を有するものとして示されている。実際の実世界の例では、より多数の、例えば、百以上の自治体が大都市のアフィニティドメイン内に位置することがある。)
【0039】
再び図3Bを参照すれば、アフィニティドメイン内に置かれた重要値位置を有する自治体の各々は、そのアフィニティドメインに関連した自治体とアフィニティ関係を有すると決定される。これら自治体が、アフィニティドメインに関連した自治体とアフィニティ関係を有すること(この関係において「優勢な自治体」と称される。)を指示するデータは、一時的データファイル344に記憶される(ステップ350)。図6は、一時的データファイル344に記憶されたアフィニティ関係情報を示す。
【0040】
再び図3Bを参照すれば、プロセスは、アフィニティドメインに関連した自治体とアフィニティ関係を有すると決定された自治体が、そのアフィニティドメインに関連した自治体と同じインデックスレベルの位置を占有するに充分なほど重要であるかどうか決定する(ステップ360)。この決定を行うために、アフィニティドメインの足跡内に置かれた重要値を有する各自治体の重要値は、その位置におけるアフィニティ値と比較される。優勢な自治体のアフィニティ値を越える重要値を有する自治体は、その優勢な自治体と同じインデックスレベルの位置を占有するに充分なほど重要であると決定される。
【0041】
図7A及び7Bは、ある自治体がその優勢な自治体のアフィニティ値を越えるような重要値を有するかどうか決定するステップを示す。図7Aは、図5の都市Aに対するアフィニティドメインを、都市A及び都市Hに対する重要値の位置を通る平面において示す縦断面図である。図7Aにおいて、都市Hの重要値は、都市Aのアフィニティ値ドメインを越えることが示されている。従って、都市Hは、都市Aと同じインデックスレベルの位置を占有するに充分なほど重要である。図7Bは、図5の都市Aに対するアフィニティドメインを、都市A及び都市Gに対する重要値の位置を通る平面において示す縦断面図である。図7Bにおいて、都市Gの重要値は、都市Aのアフィニティ値を越えるように示されていない。従って、都市Gは、都市Aと同じインデックスレベルの位置を占有するに充分なほど重要でない。
【0042】
再び図3を参照すれば、アフィニティドメイン内のどの自治体が、そのアフィニティドメインに関連した自治体と同じインデックスレベルの位置を占有するに充分なほど重要であり、且つアフィニティドメイン内のどの自治体が、そのアフィニティドメインに関連した自治体と同じインデックスレベルの位置を占有するに充分なほど重要でないかをプロセスが決定した後に、このような決定を指示するデータが一時的記憶ファイル344に記憶される(ステップ370)。
【0043】
このプロセスは、アフィニティドメインに関連した自治体を一時的データベースファイル280から除去する(又は終了とマークする)ことで続けられる(ステップ380)。次いで、このプロセスは、ソースデータベース204のデータにより表わされた別の自治体を選択し、そして他の自治体のどれがその選択された自治体とアフィニティ関係を有するか決定することで続けられる。プロセスは、新たに選択された自治体で同じステップ(ステップ300、310、320、330、340、350、360、370及び380)を実行する。
【0044】
プロセス200は、ソースデータベース204によりカバーされた領域で表わされる全ての自治体に対してアフィニティドメインが決定されるまで続けられる。選択された自治体に対するアフィニティドメインが他の自治体を包囲せず、即ちアフィニティドメインが他の自治体の重要値の位置を包囲しない場合には、選択された自治体に対してアフィニティを有する他の自治体がない。
【0045】
自治体が2つ以上の他の自治体のアフィニティドメイン内にあってもよい。このような場合に、自治体は、アフィニティドメインがこれを包囲するところの各々の自治体と個別のアフィニティ関係を有する。
【0046】
自治体が2つ以上の他の自治体とアフィニティ関係を有するときには、その2つ以上の他の自治体が互いの個別のものでよく、即ちそのいずれも他のものとアフィニティ関係をもたなくてもよい。というのは、そのいずれも他のもののアフィニティドメイン内にないからである。或いは又、自治体が2つ以上の他の自治体とアフィニティ関係を持つときには、その2つ以上の他の自治体は、他のものとアフィニティ関係をもってもよく、即ち一方が他方のアフィニティドメイン内にあってもよい。この後者の状態が図8に示されている。
【0047】
図8において、都市Bは、都市A及び都市Hの両方のアフィニティドメイン内にあることが示されている。従って、都市Bは、都市A及び都市Hの両方とアフィニティ関係をもつと決定される。都市Hは、都市Aのアフィニティドメイン内にある。従って、都市Hは、都市Aとアフィニティ関係をもつと決定される。
【0048】
図3Cを参照すれば、このプロセスは、ソースデータベースによりカバーされた領域で表わされた全ての自治体に対して決定されたアフィニティ関係を含む一時的データファイル344を使用してアフィニティ関係インデックス202を発生することで続けられる。このアフィニティ関係インデックス202は、ソースデータベース204によりカバーされた領域内の各自治体に対して決定されたアフィニティドメインにより決定されたアフィニティ関係を含むハイアラーキー構造を備えている。
【0049】
アフィニティ関係インデックスにおいて、自治体に関連したアフィニティドメイン内に位置する他の全ての自治体は、アフィニティドメインに関連した自治体が他の自治体とのアフィニティ関係有すると予め決定されない限り、その自治体とアフィニティ関係をもつと思われる。換言すれば、2つの自治体が他の各々のアフィニティドメインに位置すると決定された場合に、小さい重要値をもつ自治体は、大きい重要値をもつ自治体とアフィニティ関係をもつと思われ、そしてその逆のことは考えられない。従って、大きい自治体及び小さい自治体が互いに物理的に接近して互いのアフィニティドメイン内にある場合には、小さい自治体は、大きい自治体とアフィニティ関係を有すると思われるが、大きい自治体は、小さい自治体に対してアフィニティをもつと思われない。
【0050】
上述したように、アフィニティ関係インデックスは、積層ハイアラーキー構造を有する。この構造は、ルート(根)レイヤーに1つ以上のエントリーを含み、次に高いレイヤーに1つ以上のエントリーを含み、等々となる。各レベルのエントリーは、そのエントリーに対してアフィニティを有する自治体により指示される。
【0051】
図9は、アフィニティ関係インデックスファイル202の編成を示す。アフィニティ関係インデックスは、ルートレイヤーを含む。ルートレイヤーは、複数のエントリーを含む。ルートレイヤーのエントリーは、(1)他の自治体のアフィニティドメイン内にない自治体、又は(2)他の自治体のアフィニティドメイン内にあるが、重要値が該他の自治体のアフィニティドメインの値を越えるような自治体を含む。例えば、図7Aを参照すれば、都市Hの重要値は、都市Aのアフィニティドメインの値を越える。それ故、都市A及び都市Hは、両方とも、アフィニティ関係インデックスのルートレイヤー内の位置を占有する。
【0052】
ルートレイヤー内の各エントリーに関連しているのは、そのエントリーとアフィニティ関係をもつ自治体である。データは、これらの自治体を識別し、そしてそれらがルートレイヤーの自治体とアフィニティ関係をもつことを指示する。
【0053】
効果:
以上のプロセスは、ルートエントリーが一次コミュニティである一次インデックスで始めてアフィニティにより場所の名前をインデックスするための順序付け方法を提供する。一次コミュニティを見出しとするインデックス内には、上位及び下位レベルのコミュニティの更に別のサブインデックスがある。各レベルは、包含されたコミュニティのサブディレクトリーを表わす。下位レベルのコミュニティは、見掛け上、2つ以上の上位レベルコミュニティのアフィニティであって、それ自身、あるケースではあるレベルにあり、そして他のケースでは他のレベルにあってもよい。インデックスのこの実施形態は、重要な都市の比較的希薄な集合体、例えば、最大の都市圏がルートレベルディレクトリーを占有するのを許す。
【0054】
アフィニティに基づくインデックスの結果として、この実施形態は、いかなる場所も、「接近(near)」に対してある公式な意味をもつようにして、「接近した」別の場所として記述されるのを許す。換言すれば、場所の名前「A」は、それを「B」のディレクトリー内で見つけることができれば、接近した場所の名前「B」であり、そしてこれは、重要値位置が「A」のアフィニティドメイン内に存在する場合に見つかる。更に別の実施形態では、参照が両方向でもよい。
【0055】
IV.アフィニティ関係インデックスの使用
一実施形態において、アフィニティ関係インデックスは、コンピューティングプラットホームで実行されるナビゲーションアプリケーションにより使用される地理的データベースの一部分である。この実施形態では、アフィニティ関係インデックスは、ユーザがナビゲーションアプリケーションに対して場所(例えば、自治体)を特定するときに使用される。例えば、ユーザは、経路案内を所望する行先として場所を特定することができる。
【0056】
上述したように、従来のナビゲーションシステム及びアプリケーションは、経路を計算して案内を与えることができる前に、行先の正確な位置を特定するに充分な情報をユーザが与えることを必要とした。ある従来のナビゲーションシステム及びアプリケーションでは、充分な情報は、行先の完全に正確な住所を含むものであった。アフィニティ関係インデックスを含む又は使用する地理的データベースでは、ユーザが場所を別々の仕方で特定することができる。ユーザは、従来のシステムの場合のように、完全に正確なアドレスを使用して場所を特定することもできるし、或いはユーザは、場所をおおよそ特定することもでき、例えば、実際の所望の場所に近い他の場所を指示することで特定することもできる。
【0057】
図10は、アフィニティ関係インデックスを使用するためのプロセス500を示す。このプロセス500は、ナビゲーションプラットホーム(図2の122)におけるナビゲーションアプリケーション(図2の132)の1つの一部分でよい。プロセス500は、行先を特定するのに使用されるものとして説明するが、別の実施形態では、このプロセスは、何らかの目的で場所を特定するのに使用することができる。図10に示すプロセスは、ユーザに情報を与えると共に、ユーザから入力を受け取ることを要求する。情報は、視覚的、又は聴覚的に、或いは視覚と聴覚の組み合せでユーザに与えることができる。ユーザからの入力は、聴覚的に、又は手動入力により、或いは他の手段により受け取ることができる。
【0058】
プロセス500によれば、ユーザには、場所を正確に特定するか又はおおよそ特定するオプションが与えられる(ステップ510)。ユーザが場所を正確に特定することを選択した場合には、アプリケーションは、その目的のための適切なメニュー及び/又はプロンプトをユーザに与えるように進む。場所を正確に特定するためのこれらメニュー及び/又はプロンプトは、従来のシステムにより行われていたものと同様でよい。
【0059】
ユーザが場所をおおよそ特定することを選択した場合には、ユーザには、実際の所望の行先に近い場所(例えば、自治体)の識別を要求するプロンプトが与えられる(ステップ520)。ユーザの入力が得られ、そしてアフィニティ関係インデックス202のサーチに使用される。アフィニティ関係インデックス202をサーチするときには、ルートレベルのエントリーからスタートしてエントリーをサーチすることができる(ステップ530)。他のレベルをサーチすることもできる。ユーザにより指示された場所に対してアフィニティ関係インデックスがサーチされた後に、3つの考えられる結果が生じ、即ち、一致が生じないか、厳密に1つの一致が生じるか、又は2つ以上の一致が生じるかである(ステップ540)。一致が生じない場合には、ユーザに、指示された場所が見つからなかったという情報が与えられ、所望の行先の付近の場所の名前に対して再び促され、そしてアフィニティ関係インデックスが再びサーチされる(ステップ550及び530)。2つ以上の一致がある場合には、ユーザにより指示された名前をもつ自治体が2つ以上あることを意味する。この場合に、アフィニティ関係インデックスは、ユーザにより指示された名前をもつ場所の近くにある他の場所に関する付加的な情報を得るのに使用される(ステップ560)。例えば、アフィニティ関係インデックスは、同じ名前をもつ多数の場所の各々がアフィニティをもつ場所のうち、どれがより高いレベルかを識別するのに使用できる。次いで、この情報をユーザに与え、ユーザは、適当な場所を選択することができる(ステップ570及び574)。例えば、ユーザが「都市Y」を指示し、そしてアフィニティ関係インデックスが、名前が「都市Y」で都市Xとアフィニティ関係をもつ1つの都市と、名前が「都市Y」で都市Zとアフィニティ関係をもつ別の都市とがあることを示す場合には、名前が「都市Y」で都市X及び都市Zに近い都市があることを指示する情報がユーザに与えられる。ユーザには、これらの1つを選択するプロンプトが与えられる。
【0060】
プロセスが、所望の行先に近い1つの場所を厳密に決定すると、その場所へのルートが計算される(ステップ580)。この機能は、経路(ルート)計算アプリケーション(図2の136)により実行される。ルートを計算するときには、ルート計算は、行先として指示された近傍の場所のポイントを使用する。例えば、近傍の場所に関連した重要値の位置(即ち、その場所の管理境界の中心)を使用することができる。ユーザの位置が得られる(ステップ590)。これは、もし利用できれば、ポジショニングシステム(図2の134)から得ることができる。或いは又、ユーザは、現在位置を指示するように促されてもよい。ユーザには、計算された経路(ルート)をたどるための案内が与えられる(ステップ600)。
【0061】
ユーザが、計算された経路をたどり続けるときに、ユーザの新たな現在位置が決定され、そしてその計算された経路をたどるために適切な案内がユーザに与えられる(再びステップ590及び600)。ユーザが行先の閾値(スレッシュホールド)内を走行すると、所望の行先を正確に特定するか又は所望の行先の近くの場所を指示することで特定するオプションがユーザに再び与えられる(ステップ610及び510)。閾値(スレッシュホールド)距離は、計算経路のスタートポイントから指示された場所の行先までの全距離のパーセンテージとして決定されてもよい。或いは又、閾値(スレッシュホールド)は、走行時間に基づいて決定されてもよい。プロセスは、ユーザが所望の行先として正確な位置を特定するまで続けられる。
【0062】
アフィニティ関係インデックスを使用するプロセスは、ユーザが経路に乗り出すときに正確なアドレスを特定しなくてよいという効果を発揮する。むしろ、ユーザは、実際の所望の行先の近くの場所を特定することができる。これは、ユーザが正確な全住所を行先として特定することが要求される場合よりも迅速に経路を計算して案内を与えるのを許す。
【0063】
多くの場合、特に、実際の所望の行先が経路のスタートポイントから比較的遠い場合には、指示された近傍の場所への経路の最初の部分が、実際の所望の行先へのルートと同じになる。
【0064】
前記プロセスにおいて、所望の行先の正確な住所を特定するようにユーザを促すためのスレッシュホールドが使用される。上述したように、このスレッシュホールドは、経路に沿って行先へ至る距離の割合でよい。或いは又、固定の距離又は別の距離を使用してもよい。又、スレッシュホールドは、走行時間に基づくものでもよい。上述したように、実際の所望の行先付近にある指示された場所への経路をたどるための案内がユーザに与えられる。多くの場合に、指示された場所への経路は、最初、実際の所望の行先への経路と同じである。しかしながら、指示された近傍の場所への経路に沿ったあるポイントにおいて、実際の所望の行先への経路がそれる。スレッシュホールドは、ユーザが実際の所望の行先の正確な住所を適時に与えることができるように決定される。
【0065】
V.別の実施形態及び効果
上述したように、アフィニティ関係インデックスは、ナビゲーションシステムのようなシステムを使用するときに場所の特定を容易にする。アフィニティ関係システムは、手動或いはスピーチ又はボイスコマンドの使用によりユーザ入力を受け容れるシステムと共に使用することができる。スピーチ又はボイスコマンドと共に使用するときには、アフィニティ関係インデックスをインタラクティブに使用して、実際の所望の行先の付近の場所(自治体)を選択して、経路案内を迅速に受け取り、従って、ユーザが行先の正確な全住所をシステムに対して特定せずに行先に向かって乗り出すことができる。従来の方法は、一般に、その性質がアルファベット順であるか、さもなければ、ユーザが正確な行先を選択するために多数の特定レベルを横断するように強制する。アフィニティ関係インデックスは、行先をインタラクティブに特定するための比較的高速な、より直観的な仕方を与える。スピーチ認識システムと共にアフィニティ関係インデックスを使用する別の効果は、サーチする必要のある異なる都市名の数を減少し、これにより、スピーチ認識システムが正しい一致をなし得る確率を改善することである。
【0066】
前記実施形態において、アフィニティ関係インデックスは、自治体の名前を、それらに接近し且つ相対的により重要な他の自治体と関連付けるのに使用された。アフィニティ関係インデックスの別の実施形態は、関心のあるポイントのような他の種類の場所に使用することができる。アフィニティ関係インデックスが他の種類の場所に使用される場合には、このような種類の場所の重要性を反映するファクタ及び/又はパラメータを含むように重要値アルゴリズムが変更される。アフィニティ関係インデックスの更に別の実施形態は、自治体を、関心のあるポイント、国立公園等の他の種類の場所に結合することができる。自治体を他の種類の場所に結合するアフィニティ関係インデックスが使用される場合には、このような種類の場所の相対的な重要値が自治体の重要値と一貫したものとなるようにファクタ及び/又はパラメータを含むよう重要値アルゴリズムが変更される。
【0067】
アフィニティ関係インデックスは、ユーザが行先を取り巻く地理的エリアに馴染みがないか、又は行先に関する完全な情報をもたず、大都市や全国的/地域的に重要な関心ポイントのような近傍の重要位置の知識をある程度もつだけである状況に特に有用である。
【0068】
アフィニティ関係インデックスは、全ての通常のサーチ方法を使用してサーチを行えるようにする。更に、アフィニティ関係インデックスは、ユーザが、大都市のみの参照を使用することにより行先選択プロセスを開始し、次いで、その特定を後で洗練することができるようにする。
【0069】
場所を正確に特定するか又はおおよそ特定するオプションがユーザに与えられることは前記で述べた。このオプションは、ユーザに明確に与えられてもよいし、暗示的に与えられてもよい。例えば、ユーザには、行先住所を正確に特定するか又は行先をおおよそ特定するための別々のメニュー選択が与えられてもよい。或いは又、ユーザの入力を使用して、正確な行先住所が特定されるか、おおよその行先位置が特定されるか決定してもよい。例えば、ユーザがワード「on」又は「at」を使用する場合には、プロセスは、ユーザが行先を正確に特定すると推論する。しかしながら、ユーザがワード「near」を使用する場合には、プロセスは、ユーザがおおよその行先を特定すると推論し、それ故、アフィニティ関係インデックスを使用して、行先に向かって経路に最初に乗り出す場所を決定する。
【0070】
アフィニティ関係インデックスと、これを使用する関連プログラムは、あいまいな即ち不完全な行先入力を、重要性が次第に高くなるか又は低くなる位置と位置との間のアフィニティの自然特性を使用して、益々の洗練さでサポートする。
【0071】
アフィニティ関係インデックスと、これを使用する関連プログラムは、空間的アフィニティ、即ち物理的な接近性しか一般的に使用しない従来のシステムに勝る効果を発揮する。アフィニティ関係インデックスの実施形態は、物理的な接近性を、重要性のハイアラーキー環境における成分として含む。付加的な実施形態は、政治的関係、空間的幾何学形状、及び歴史的重要性ファクタを含むハイアラーキーをサポートすることができる。
【0072】
以上の詳細な説明は、本発明を例示するもので、限定するものではなく、又、あらゆる等効物を含む特許請求の範囲が本発明の範囲を規定することを理解されたい。
【図面の簡単な説明】
【0073】
【図1】種々のコンピューティングプラットホームに使用するための地理的データベース製品を形成しそして配送するプロセスを示す図である。
【図2】地理的データベース製品を使用する図1のシステムの1つを示すブロック図である。
【図3A】アフィニティ関係インデックスを形成するプロセスを示すフローチャートである。
【図3B】アフィニティ関係インデックスを形成するプロセスを示すフローチャートである。
【図3C】アフィニティ関係インデックスを形成するプロセスを示すフローチャートである。
【図4】図3A、3B及び3Cのプロセスにより計算されたアフィニティドメインを示す図である。
【図5】図4のアフィニティドメインの別の図で、そこに示された他の自治体に対する重要値を付加した図である。
【図6】図3A、3B及び3Cのプロセスにより形成されたアフィニティ関係データを含む一時的ファイルの編成を示すブロック図である。
【図7A】都市に対する重要値と、図5に示すアフィニティドメインとの間の関係を示す図である。
【図7B】別の都市に対する重要値と、図5に示すアフィニティドメインとの間の関係を示す別の図である。
【図8】自治体間のアフィニティ関係を示す図である。
【図9】図3A、3B及び3Cのプロセスにより形成されたアフィニティ関係インデックスファイルデータのコンポーネントを示すブロック図である。
【図10】図9のアフィニティ関係インデックスファイルを使用するアプリケーションにより実行されるプロセスのフローチャートである。
【符号の説明】
【0074】
100:地理的データベース
101:地理的データベースデベロッパー
102:データ
110:コンパイルされたデータベース製品
118:データ集合体
120:インデックス
122:コンピューティングプラットホーム
132:ナビゲーションアプリケーション
134:ポジショニングシステム
136:経路(ルート)計算アプリケーション
140:経路(ルート)案内アプリケーション
144:地図表示アプリケーション
148:ポジショニングアプリケーション
152:行先選択アプリケーション
164:データ記憶媒体
202:アフィニティ関係インデックス
204:ソースデータベース
【技術分野】
【0001】
本発明は、場所を特定する方法に係り、より詳細には、行先を特定するためのナビゲーションシステム又は他のコンピューティングプラットホームのアプリケーションに使用できるインデックス方法に係る。
【背景技術】
【0002】
ナビゲーションに関係した機能が種々の異なるコンピュータプラットホームに設けられている。例えば、ナビゲーションに関係した機能は、スタンドアローンシステム又はネットワークシステムと共に設けることができる。スタンドアローンシステムでは、ソフトウェアアプリケーション、地理的データ及びハードウェアが単一の位置において結合される。スタンドアローンシステムは、乗物にインストールしてもよいし又は個人が携帯してもよい。ネットワークシステムでは、ソフトウェア又は地理的データのあるものは、ユーザを伴うハードウェアと共に配置され、そしてソフトウェア又は地理的データのあるものは、遠隔に配置されて通信システムを経てアクセスされる。ナビゲーションに関係した機能は、専用プラットホームで実施されるシステムにより与えられ、ここでは、ハードウェア及びソフトウェアがナビゲーション目的で特に設計される。或いは又、ナビゲーションに関係した特徴を与えるシステムは、適切なソフトウェアアプリケーション及びデータを使用して汎用のコンピューティングプラットホーム(例えば、パーソナルコンピュータ、パーソナルデジタルアシスタント、又はネットワーク型コンピュータ)において実施することができる。
【0003】
ナビゲーションアプリケーションを実行する専用のナビゲーションシステム及び汎用のコンピューティングプラットホーム(以下、集合的に「ナビゲーションシステム」と称する。)は、種々様々な有用な特徴及びサービスを提供する。例えば、乗物に使用されるナビゲーションシステムは、所望の行先へ運転するための詳細なインストラクションを与え、走行時間及び経費を減少することができる。又、ナビゲーションシステム及びナビゲーションアプリケーションは、所望のタイプの会社をサーチし、そしてその会社の位置へのルート案内を与えることもできる。
【0004】
これらのシステムに関連した1つの事柄は、ユーザがどのようにしてシステムに場所を特定するかに関する。例えば、ユーザが行先へのルートをたどるためにナビゲーションシステムから案内を得たいときには、ユーザが何らかの手段によりシステムに行先を指示することが必要である。行先を特定する機能は、種々の理由で複雑なものとなる。多くのシステムは、行先の正確な位置がユーザにより完全に指示されるまで、ルートを計算しなかったり、案内を与えない。しかしながら、ある場合には、ユーザは、都市や街路の正確なつづりを知らないことがある。都市や町が同じ又は同様の名前をもつときには、別の複雑さが考えられる。
【発明の開示】
【発明が解決しようとする課題】
【0005】
従って、ユーザがシステムに行先のような位置を特定できる方法を改善することが要望される。例えば、計算されたルートを得るためにユーザが行先を特定する方法を改善することが要望される。
【課題を解決するための手段】
【0006】
これら及び他の目的に対処するために、本発明は、ナビゲーションシステムに対する迅速且つ便利な行先入力及び案内を可能にするようなデジタル地図データを編成するための実施形態を包含する。2つの関連するコンポーネントが含まれる。その第1は、所与の場所の名前に対し、1つ以上の潜在的により重要な場所の名前に対する密接な関係(アフィニティ:affinity)を捕える仕方で場所の名前をインデックスする手段である。このようなより重要な各場所は、他の場所がその中にあると思われるところのアフィニティドメインを抱いている。これは、ハイアラーキー式に保持され、そしてユーザが意図する行先に対して迅速にサーチできる比較的意義のある且つ最小の構造体を生成するという作用を有する。第2のコンポーネントは、これらのアフィニティドメインを使用して、案内される旅程に乗り出すに必要なインストラクションを決定するのであって、旅程を完了するに必要な全てのインストラクションを決定するのではない。
【発明を実施するための最良の形態】
【0007】
I.地理的データベース形成の概要
図1は、地理的データベースのマスター即ちソースバージョン100を示す。地理的データベースのマスターバージョンは、地理的データベースデベロッパー101(「地図デベロッパー」、「地図データデベロッパー」等とも称される。)により所有され、開発される。(1つのソースデータベース及び地理的データベースデベロッパーしか示されていないが、ここに示す実施形態は、単一のソースデータベース又は単一の地理的データベースデベロッパーに限定されない。)
【0008】
地理的データベースのマスターバージョン100は、地理的カバレージエリアにおける特徴を表わすデータ102(「地理的データ」又は「空間的データ」とも称される。)を含む。地理的カバレージエリアは、米国のような国全体に対応してもよい。或いは又、地理的カバレージエリアは、多数の国々、例えば、米国、カナダ及びメキシコ、或いはフランス、ドイツ及びイタリア、等々に対応してもよい。別の態様によれば、地理的データベースのマスターバージョン100の地理的カバレージエリアは、国内の単一領域、例えば、米国のウェストコースト又はミッドウェストを表わすだけでもよい。地理的データベースのマスターバージョン100は、全地理的カバレージエリアにおける地理的特徴を表わすデータを含むが、地理的データベースのデータにより表わされない地理的特徴を含むか、又は地理的特徴の表示が希薄であるような地理的カバレージエリアの部分も存在し得る。
【0009】
地理的データベースのマスターバージョン100は、地理的カバレージエリア内に位置する道路網に関するデータを含む。道路網に関するデータは、色々な種類の情報、例えば、道路の位置の地理的座標、道路のストリート名、道路に沿った住所範囲、道路の交差点における転回制限、等々を含む。又、地理的データベースのマスターバージョン100は、カバーされた地理的エリアにおける関心のあるポイントに関するデータも含む。関心のあるポイントは、ホテル、レストラン、美術館、スタジアム、オフィス、自動車販売店、自動車修理店、等々を含むことができる。地理的データベースのマスターバージョン100は、これら関心のあるポイントの位置に関するデータを含むことができる。又、地理的データベースのマスターバージョン100は、都市、町、又は他のコミュニティのような場所に関するデータや、水域、山脈等の他の地理的特徴を含むこともできる。更に、地理的データベースのマスターバージョン100は、他の種類の情報を含んでもよい。
【0010】
データを収集するために種々の方法が地理的データベースデベロッパー101により使用されている。これらの方法は、自治体や航空写真のような他のソースからデータを得ることを含む。更に、地理的データベースデベロッパー101は、現場要員を雇って地理的領域全体にわたり道路に沿って乗物で走行し、特徴を観察すると共に、それらに関する情報を記録することができる。地理的データベースデベロッパー101により収集されたデータは、地理的データベースのマスターバージョン100に記憶される。
【0011】
地理的データベースデベロッパー101は、地理的カバレージエリアにおける特徴を表わすデータを進行形態で収集し続ける。地理的データベースデベロッパーがデータを収集し続ける1つの理由は、カバレージエリアにおける特徴が時間と共に変化するからである。従って、地理的データベースデベロッパー101は、特徴に関する以前に収集したデータを更新又は確認するために、その同じ特徴に関するデータを収集する。地理的データベースデベロッパー101がデータを収集し続ける別の理由は、地理的データベースのマスターバージョン100のカバレージ及び/又は詳細を拡張するためである。例えば、ある時点に、地理的データベースのマスターバージョン100は、全カバレージエリアの一部分だけを表わすデータを含んでもよい。その時点以降に、地理的データベースデベロッパー101は、以前に表わされなかったエリアにおける特徴に関するデータを収集し、地理的データベースのマスターバージョン100のカバレージを拡張する。
【0012】
地理的データベースのマスターバージョン100は、地理的カバレージエリアに関する最新のデータを有するコピーとして維持される。従って、地理的データベースのマスターバージョン100は、規則的で且つ連続的なベースで、更新され、拡張され、及び/又はその他変更される。これらのオペレーションを容易にするために、地理的データベースのマスターバージョン100は、更新、維持、及び開発を容易にするフォーマットで記憶される。例えば、マスターバージョン100のデータは、非圧縮でもよい。適当なフォーマットは、例えば、バーチャル・ストレージ・アクセス・メソッド(VSAM)フォーマットを含むが、他の種類のフォーマット、独占的及び非独占的の両方、も適している。一般に、マスターデータベース100のフォーマットは、ナビゲーションシステムに使用するのには適していない。
【0013】
一実施形態では、地理的データベースのマスターバージョン100は、1つ以上のハードドライブ、テープ又は他の媒体の位置に記憶され、そして適切なコンピュータでアクセスされる。メインフレームコンピュータ、複数のネットワーク型マイクロコンピュータ等の適当なコンピュータを使用することができる。
【0014】
地理的データベースのマスターバージョン100からのデータは、コンパイルされたデータベース製品110を形成するのに使用される。このコンパイルされたデータベース製品110は、コンパイラー111を使用して作られる。コンパイラー111は、適当なコンピュータプラットホームで実行されるソフトウェアプログラムである。コンパイルされたデータベース製品110は、地理的データベースデベロッパー101により形成されてもよいし、或いは別のエンティティ、例えば、地理的データベースデベロッパーからデータを取得するか又はライセンス契約する地理的データベースデベロッパーの顧客により形成されてもよい。コンパイルされたデータベース製品を形成する前に、地理的データベースのマスターバージョン100からのデータは、GDFフォーマットのような1つ以上の中間フォーマットにコンパイルされ又は配送されてもよい。
【0015】
コンパイルされたデータベース製品110は、地理的データベースのマスターバージョン100における全データの一部分のみを含んでもよい。例えば、コンパイルされたデータベース製品110は、地理的データベースのマスターバージョン100のカバレージエリア内の1つ以上の特定のサブエリアのみに関連したデータを含んでもよい。更に、コンパイルされたデータベース製品110は、地理的データベースのマスターバージョン100で表わされる地理的特徴を記述する全てのデータ属性より少数のものを含んでもよい。
【0016】
コンパイルされたデータベース製品110において、地理的データは、地理的データベースのマスターバージョン100の場合とは異なる仕方で編成される。コンパイルされたデータベースは、それがインストールされるコンピューティングプラットホームにおけるデータの使用を容易にする形態で編成され、配列され、構造化されそして記憶される。例えば、コンパイルされたデータベース製品110では、データは、特定の機能を実行するに必要な属性のみを各々含む個別のデータ集合体118へと編成されてもよい。例えば、1つのデータ集合体は、ルート計算を実行するのに必要な属性のみを含み、別の集合体は、ポジショニングに必要な属性のみを含み、又、更に別の集合体は、行先選択に必要な属性のみを含んでもよい。
【0017】
又、コンパイルされたデータベース製品110は、地理的データの集合体を異なるレベル又はスケールで含んでもよい。例えば、1つのデータ集合体は、カバレージエリア内の全ての道路を含んでもよく、そして同じデータベースの別のデータ集合体は、より高い機能クラスの道路、即ち制御されたアクセス道路のような比較的高い交通量を輸送する道路、のみを含んでもよい。
【0018】
又、コンパイルされたデータベース110は、データ集合体の幾つかを空間的に編成してもよく、即ち物理的に互いに接近した地理的特徴が、データベース内で互いに接近配置されたデータにより表わされるように編成してもよい。
【0019】
コンパイルされたデータベースは、マスター地理的データベース100に見られないデータエンティティを含んでもよい。例えば、コンパイルされた地理的データベース110は、マスター地理的データベース100内の多数の異なるデータエンティティの複合体であるか、又はマスター地理的データベース100内のデータエンティティから導出されたものであるデータエンティティを含んでもよい。
【0020】
又、コンパイルされたデータベース製品は、それが位置する媒体に圧縮フォーマットで記憶されてもよい。
又、コンパイルされたデータベースは、1つ以上のインデックス120を含んでもよい。種々のデータ集合体を互いに関連付けるインデックス、データをそれが記憶された媒体において見つけるためのインデックス、及びデータ集合体内で特定の情報を見つけるためのインデックスを含む種々の形式のインデックス120が含まれてもよい。
【0021】
地理的データをコンピューティングプラットホームに使用するように編成できる幾つかの仕方が、参考としてここに全開示を援用する米国特許第5,953,722号、第5,968,109号、第5,974,419号、第6,038,559号、第6,112,200号、第6,081,803号、第6,118,404号、第6,122,593号、第6,184,823号、第6,249,742号、第6,308,177号、第6,324,470号、第6,336,111号、第6,393,149号、第6,460,046号、第6,473,770号、第6,507,850号、第6,591,270号、第6,600,841号、第6,751,629号、第6,768,818号、第6,782,319号、及び第6,829,690号に説明されている。
【0022】
II.コンピューティングプラットホームにおける地理的データの使用
コンパイルされたデータベース製品110は、色々な種類のコンピューティングプラットホーム122において使用される。コンピューティングプラットホーム122は、乗物内ナビゲーションシステム、ハンドヘルドポータブルナビゲーションシステム、パーソナルコンピュータ(デスクトップ及びノードブックコンピュータを含む)、及び他の種類のデバイス、例えば、パーソナルデジタルアシスタント(PDA)デバイス、ページャー、電話等を含む。又、コンパイルされたデータベース製品110は、インターネットに接続されたシステムを含むネットワーク型コンピューティングプラットホーム及び環境にも使用される。
【0023】
コンピューティングプラットホーム122に使用されるコンパイルされたデータベース製品110は、適当な媒体に記憶される。例えば、コンパイルされたデータベースは、CD−ROMディスク、ハードドライブ、DVDディスク、フラッシュメモリ、メモリカード、或いは現在入手できるか又は将来入手できるようになる他の形式の媒体に記憶することができる。
【0024】
コンピューティングプラットホーム122では、コンパイルされたデータベース製品110が種々のソフトウェアアプリケーションにより使用される。例えば、コンパイルされたデータベース製品110は、ナビゲーションに関連した機能、例えば、ルート計算、ルート案内、乗物のポジショニング、地図表示、及び電子的イエローページ、並びに他の種類の機能を与えるソフトウェアアプリケーションにより使用することができる。
【0025】
図2は、コンピューティングプラットホーム122の幾つかのコンポーネントを示すブロック図である。図2に示すコンピューティングプラットホーム122は、ナビゲーション用の幾つかのコンポーネントを含むものである。コンピューティングプラットホーム122は、ポジショニングシステム134を備えている。このポジショニングシステム134は、ポータブルナビゲーションシステム130の現在位置を決定する。ポジショニングシステム134は、いかなる位置感知装置又は技術により実施されてもよい。例えば、ポジショニングシステムは、GPSユニット、或いは到着時間、到着方向、三角法、WiFi、RFID、Loran、デッドレコニング(dead reckoning)、或いはこれら又は他のシステムの組み合せを使用するシステムを含んでもよい。
【0026】
この実施形態では、コンピューティングプラットホーム122は、ナビゲーションアプリケーション132を備えている。このナビゲーションアプリケーション132は、ナビゲーションに関連するか又は地図に関連したある機能を実行するソフトウェアプログラムである。これらのナビゲーションアプリケーション132は、コンピューティングプラットホーム122における適当なデータ記憶媒体に記憶される。ナビゲーションアプリケーション132は、必要なときに実行される。ナビゲーションアプリケーション132間に含まれるのは、ルート計算アプリケーション136、ルート案内アプリケーション140、地図表示アプリケーション144、ポジショニングアプリケーション148、及び行先選択アプリケーション152である。他の実施形態は、これらアプリケーションをより多く又はより少なく有してもよい。或いは又、ある実施形態では、これらアプリケーションの2つ以上を組み合せてもよい。
【0027】
コンピューティングプラットホーム122は、コンパイルされたデータベース製品110の1つを含む。コンパイルされたデータベース製品110は、コンピューティングプラットホーム122においてデータ記憶媒体164に記憶される。コンパイルされたデータベース製品110は、ナビゲーション関連機能を与えるためにナビゲーションアプリケーション132により使用される。地図データベース160は、カバーされた地理的エリアにおける道路、交差点、関心のあるポイント、及び他の地理的特徴に関する情報を含む。カバーされた地理的エリアは、1つ以上の都会エリア、州、国、領域又はその組み合せを含んでもよい。
【0028】
ナビゲーションアプリケーション132は、一緒に機能しコンパイルされたデータベース製品110を使用して、色々な種類のナビゲーション機能を与える。例えば、ナビゲーションアプリケーションは、所望の行先へのルートを得るのに使用できる。この例によれば、ユーザは、行先選択アプリケーション152を使用して、所望の場所を見つけることができる。ルートの出発点は、ポジショニングシステム134と一緒に使用されるポジショニングアプリケーション148により決定されるユーザの位置であると仮定される。所望の行先の位置及び出発点の位置を指示するデータは、ルート計算アプリケーション136へ転送される。このルート計算アプリケーション136は、出発点から行先までのルートを決定し、次いで、ルートを指示するデータをルート案内アプリケーション140へ転送する。ルート案内アプリケーション140は、ルートをたどるためにユーザに適した方向を発生する。
【0029】
コンピューティングプラットホーム122を使用し、ユーザをルートに沿って行先へ案内するときには、ユーザが位置するエリアのグラフィック地図をユーザに示すことが有用である。地図表示アプリケーション144は、この目的で使用することができる。地図表示アプリケーション144は、ルート計算アプリケーション136からルートを指示するデータを受け取ると共に、ポジショニングアプリケーション148からユーザの現在位置を指示するデータを受け取る。地図表示アプリケーション144は、コンパイルされたデータベース製品110からのデータにアクセスして、ユーザの現在位置の周りの地理的エリアのグラフィック地図像を発生する。地図表示アプリケーション144は、コンピューティングプラットホーム122のディスプレイスクリーンに像をレンダリングし、ユーザの現在位置の周りの地理的エリアを示す。像は、ユーザの付近に位置する道路を示してもよい。ユーザの現在位置を指示するために、インジケータマークを像に重畳してもよい。又、ユーザがたどるべきルートを、ハイライトにより、像において指示してもよい。
【0030】
III.アフィニティ関係インデックスの形成
図3A、3B及び3Cは、アフィニティ関係インデックス202を形成するためのプロセス200を示す。プロセス200は、適当なコンピューティングプラットホーム122に使用される地図データベース製品110を形成するときにコンパイラー111(図1)により実行されるコンパイルプロセスの一部分でよい。プロセス200は、ソースデータベース204からのデータを使用する。ソースデータベース204は、マスター地理的データベース100、又はこのソースデータベース100から派生したデータベース、例えば、中間、交換又は配送フォーマットのデータベースでよい。プロセス200は、ソースデータベース204からのデータを入力として使用し、そして1つ以上のアフィニティ関係インデックス202の形態で出力を与える。アフィニティ関係インデックス202は、コンパイルされた地理的データベース製品110を形成するときに作られる図1のインデックス132の1つに含まれてもよい。
【0031】
プロセス200は、カバーされた領域内の各自治体に対して実行される一連のステップを含む。(説明上、自治体という語は、種々の形式の法的に編成されたコミュニティ、例えば、市、町、村、等を含む。)図3Aを参照すれば、プロセス200は、ソースデータベース204のカバレージ領域で表わされた全ての自治体から1つの自治体を選択する(ステップ208)。選択された自治体に対して、プロセスは、自治体の管理境界に対応する多角形内の人口を指示する情報をソースデータベース204からアクセスする(ステップ210)。次いで、プロセスは、ソースデータベース204にアクセスし、その多角形内に位置する道路網におけるノード(即ち交差点)の数Nのカウントを決定する(ステップ220)。次いで、プロセスは、ソースデータベース204にアクセスし、そして自治体の管理境界に対応する多角形内に包囲された道路のキロメーター数Kを計算する(ステップ230)。次いで、プロセスは、ソースデータベース204にアクセスし、そして自治体の管理境界に対応する多角形の道路横断の数Rをカウントする(ステップ240)。
【0032】
ソースデータベース204から得られ又は導出されたこの情報を使用して、プロセスは、自治体に対する重要値Iを計算する(ステップ250)。プロセスは、次の式を使用する。
I=APαxBNβxCKγxDRδ
但し、Pは、自治体の管理境界多角形内の人口であり、Nは、同じ多角形内に存在する道路網におけるノードの数であり、Kは、多角形内に含まれる道路のキロメーター数であり、そしてRは、多角形の境界が道路を横断する数である。大文字の係数及び小文字の指数は、重要度インデックスIの値を調整するのに使用されるチューニング変数である。
【0033】
プロセスが自治体に対する重要値を計算すると、その重要値に対する地理的な位置が決定される(ステップ260)。この実施形態では、自治体の管理境界に対応する多角形の中心の地理的座標が決定されて、重要値の地理的位置として使用される。重要値を指示するデータ、重要値に関連した中心位置、及び自治体の認識が、一時的に記憶される(ステップ270)。この目的のために、一時的データベース280又はスクラッチファイルを使用してもよい。プロセス200は、ソースデータベース204により表わされたカバーされた領域における別の自治体を選択するように進み(ステップ290)、そしてソースデータベース204にアクセスして自治体に関する情報を得ると共に、重要値及びその重要値に対する関連位置(即ち中心)を計算するに必要な情報を導出するという同じステップ(即ち、ステップ210、220、230、240、250及び260)を実行する。この自治体に対する重要値、その関連位置、及びその関連自治体を識別する情報が記憶される(ステップ270)。このプロセスは、カバーされた領域における全ての自治体に対する重要値及びそれに関連した位置を決定して記憶するように続けられ、やがて、全ての自治体に対する重要値及びそれに関連した位置が計算されて一時的データベース280に記憶される(ステップ290)。
【0034】
ソースデータベース204で表わされた全ての自治体に対して重要値及びそれに対応する位置が決定されて記憶された後、プロセス200は、ソースデータベース204で表わされた自治体に対してアフィニティ関係のインデックスを決定することで続けられる。アフィニティ関係を決定する際に、プロセスは、各自治体間の距離と組み合せて各自治体に対して決定された重要値を使用して、アフィニティ関係インデックスのどのレベルを自治体が占有するか、及び他の地自体のどれが所与の自治体とのアフィニティ関係を有するか決定する。
【0035】
図3Bは、アフィニティ関係のインデックスを決定するためのプロセス200のステップを示す。このプロセスは、最も大きな重要値を決定しそしてそれに関連した自治体を選択することで継続される(ステップ300及び310)。この自治体に対するアフィニティドメインが計算される(ステップ320)。このアフィニティドメインは、自治体に関連した位置、この実施形態では、自治体の管理境界により形成される多角形の中心、からの距離関数である値(即ち、アフィニティ値)を各ポイントが有するような円形領域を画成する。自治体の中心の位置にあるこのアフィニティ値は、自治体に対して決定される重要値に対応する。又、この値は、自治体に対するアフィニティドメインの最大値でもある。自治体に対するアフィニティ値は、あらゆる方向に等しく先細りとなる。アフィニティ値の先細りの割合は、指数関数、双曲線関数、又は他の適当な関数により定義することができる。
【0036】
アフィニティドメインを画成するのに使用される関数に基づいて、アフィニティ値は、自治体の中心からの距離関数として減少し続ける。自治体の中心からのある距離において、アフィニティ値は、所定の最小スレッシュホールド値TMINに対応する値へと先細りになる。アフィニティ値が最小閾値(スレッシュホールド値)TMINに到達する位置は、その自治体に対するアフィニティドメインの水平境界を定義する(ステップ330)。ある実施形態では、大きな都市に対するアフィニティドメインの水平境界は、都市のより大きな都会エリア、即ち都市とその郊外にほぼ対応してもよい。
【0037】
図4は、自治体、即ち都市Aに対して計算されたアフィニティドメインを示す。このアフィニティドメインは、自治体の中心に位置する重要値に対応するピーク値を有することに注意されたい。アフィニティドメインは、ピークから最小閾値(スレッシュホールド)へと軸対称に先細りとなる。
【0038】
再び図3Bを参照すれば、プロセスは、次いで、そのアフィニティドメインの地理的エリア(即ち足跡)内に包囲された他の自治体に関連した全ての重要値位置を決定する(ステップ340)。図5は、アフィニティドメイン内に位置する重要値位置を有する他の自治体を決定するステップを示す。図5において、都市B、C、D、E、G及びHは、都市Aのアフィニティドメイン内に位置する重要値を有する。都市Fの重要値は、都市Aのアフィニティドメイン内にないことに注意されたい。(簡単化のために、図5では、6つの自治体が都市Aのアフィニティドメイン内に重要値位置を有するものとして示されている。実際の実世界の例では、より多数の、例えば、百以上の自治体が大都市のアフィニティドメイン内に位置することがある。)
【0039】
再び図3Bを参照すれば、アフィニティドメイン内に置かれた重要値位置を有する自治体の各々は、そのアフィニティドメインに関連した自治体とアフィニティ関係を有すると決定される。これら自治体が、アフィニティドメインに関連した自治体とアフィニティ関係を有すること(この関係において「優勢な自治体」と称される。)を指示するデータは、一時的データファイル344に記憶される(ステップ350)。図6は、一時的データファイル344に記憶されたアフィニティ関係情報を示す。
【0040】
再び図3Bを参照すれば、プロセスは、アフィニティドメインに関連した自治体とアフィニティ関係を有すると決定された自治体が、そのアフィニティドメインに関連した自治体と同じインデックスレベルの位置を占有するに充分なほど重要であるかどうか決定する(ステップ360)。この決定を行うために、アフィニティドメインの足跡内に置かれた重要値を有する各自治体の重要値は、その位置におけるアフィニティ値と比較される。優勢な自治体のアフィニティ値を越える重要値を有する自治体は、その優勢な自治体と同じインデックスレベルの位置を占有するに充分なほど重要であると決定される。
【0041】
図7A及び7Bは、ある自治体がその優勢な自治体のアフィニティ値を越えるような重要値を有するかどうか決定するステップを示す。図7Aは、図5の都市Aに対するアフィニティドメインを、都市A及び都市Hに対する重要値の位置を通る平面において示す縦断面図である。図7Aにおいて、都市Hの重要値は、都市Aのアフィニティ値ドメインを越えることが示されている。従って、都市Hは、都市Aと同じインデックスレベルの位置を占有するに充分なほど重要である。図7Bは、図5の都市Aに対するアフィニティドメインを、都市A及び都市Gに対する重要値の位置を通る平面において示す縦断面図である。図7Bにおいて、都市Gの重要値は、都市Aのアフィニティ値を越えるように示されていない。従って、都市Gは、都市Aと同じインデックスレベルの位置を占有するに充分なほど重要でない。
【0042】
再び図3を参照すれば、アフィニティドメイン内のどの自治体が、そのアフィニティドメインに関連した自治体と同じインデックスレベルの位置を占有するに充分なほど重要であり、且つアフィニティドメイン内のどの自治体が、そのアフィニティドメインに関連した自治体と同じインデックスレベルの位置を占有するに充分なほど重要でないかをプロセスが決定した後に、このような決定を指示するデータが一時的記憶ファイル344に記憶される(ステップ370)。
【0043】
このプロセスは、アフィニティドメインに関連した自治体を一時的データベースファイル280から除去する(又は終了とマークする)ことで続けられる(ステップ380)。次いで、このプロセスは、ソースデータベース204のデータにより表わされた別の自治体を選択し、そして他の自治体のどれがその選択された自治体とアフィニティ関係を有するか決定することで続けられる。プロセスは、新たに選択された自治体で同じステップ(ステップ300、310、320、330、340、350、360、370及び380)を実行する。
【0044】
プロセス200は、ソースデータベース204によりカバーされた領域で表わされる全ての自治体に対してアフィニティドメインが決定されるまで続けられる。選択された自治体に対するアフィニティドメインが他の自治体を包囲せず、即ちアフィニティドメインが他の自治体の重要値の位置を包囲しない場合には、選択された自治体に対してアフィニティを有する他の自治体がない。
【0045】
自治体が2つ以上の他の自治体のアフィニティドメイン内にあってもよい。このような場合に、自治体は、アフィニティドメインがこれを包囲するところの各々の自治体と個別のアフィニティ関係を有する。
【0046】
自治体が2つ以上の他の自治体とアフィニティ関係を有するときには、その2つ以上の他の自治体が互いの個別のものでよく、即ちそのいずれも他のものとアフィニティ関係をもたなくてもよい。というのは、そのいずれも他のもののアフィニティドメイン内にないからである。或いは又、自治体が2つ以上の他の自治体とアフィニティ関係を持つときには、その2つ以上の他の自治体は、他のものとアフィニティ関係をもってもよく、即ち一方が他方のアフィニティドメイン内にあってもよい。この後者の状態が図8に示されている。
【0047】
図8において、都市Bは、都市A及び都市Hの両方のアフィニティドメイン内にあることが示されている。従って、都市Bは、都市A及び都市Hの両方とアフィニティ関係をもつと決定される。都市Hは、都市Aのアフィニティドメイン内にある。従って、都市Hは、都市Aとアフィニティ関係をもつと決定される。
【0048】
図3Cを参照すれば、このプロセスは、ソースデータベースによりカバーされた領域で表わされた全ての自治体に対して決定されたアフィニティ関係を含む一時的データファイル344を使用してアフィニティ関係インデックス202を発生することで続けられる。このアフィニティ関係インデックス202は、ソースデータベース204によりカバーされた領域内の各自治体に対して決定されたアフィニティドメインにより決定されたアフィニティ関係を含むハイアラーキー構造を備えている。
【0049】
アフィニティ関係インデックスにおいて、自治体に関連したアフィニティドメイン内に位置する他の全ての自治体は、アフィニティドメインに関連した自治体が他の自治体とのアフィニティ関係有すると予め決定されない限り、その自治体とアフィニティ関係をもつと思われる。換言すれば、2つの自治体が他の各々のアフィニティドメインに位置すると決定された場合に、小さい重要値をもつ自治体は、大きい重要値をもつ自治体とアフィニティ関係をもつと思われ、そしてその逆のことは考えられない。従って、大きい自治体及び小さい自治体が互いに物理的に接近して互いのアフィニティドメイン内にある場合には、小さい自治体は、大きい自治体とアフィニティ関係を有すると思われるが、大きい自治体は、小さい自治体に対してアフィニティをもつと思われない。
【0050】
上述したように、アフィニティ関係インデックスは、積層ハイアラーキー構造を有する。この構造は、ルート(根)レイヤーに1つ以上のエントリーを含み、次に高いレイヤーに1つ以上のエントリーを含み、等々となる。各レベルのエントリーは、そのエントリーに対してアフィニティを有する自治体により指示される。
【0051】
図9は、アフィニティ関係インデックスファイル202の編成を示す。アフィニティ関係インデックスは、ルートレイヤーを含む。ルートレイヤーは、複数のエントリーを含む。ルートレイヤーのエントリーは、(1)他の自治体のアフィニティドメイン内にない自治体、又は(2)他の自治体のアフィニティドメイン内にあるが、重要値が該他の自治体のアフィニティドメインの値を越えるような自治体を含む。例えば、図7Aを参照すれば、都市Hの重要値は、都市Aのアフィニティドメインの値を越える。それ故、都市A及び都市Hは、両方とも、アフィニティ関係インデックスのルートレイヤー内の位置を占有する。
【0052】
ルートレイヤー内の各エントリーに関連しているのは、そのエントリーとアフィニティ関係をもつ自治体である。データは、これらの自治体を識別し、そしてそれらがルートレイヤーの自治体とアフィニティ関係をもつことを指示する。
【0053】
効果:
以上のプロセスは、ルートエントリーが一次コミュニティである一次インデックスで始めてアフィニティにより場所の名前をインデックスするための順序付け方法を提供する。一次コミュニティを見出しとするインデックス内には、上位及び下位レベルのコミュニティの更に別のサブインデックスがある。各レベルは、包含されたコミュニティのサブディレクトリーを表わす。下位レベルのコミュニティは、見掛け上、2つ以上の上位レベルコミュニティのアフィニティであって、それ自身、あるケースではあるレベルにあり、そして他のケースでは他のレベルにあってもよい。インデックスのこの実施形態は、重要な都市の比較的希薄な集合体、例えば、最大の都市圏がルートレベルディレクトリーを占有するのを許す。
【0054】
アフィニティに基づくインデックスの結果として、この実施形態は、いかなる場所も、「接近(near)」に対してある公式な意味をもつようにして、「接近した」別の場所として記述されるのを許す。換言すれば、場所の名前「A」は、それを「B」のディレクトリー内で見つけることができれば、接近した場所の名前「B」であり、そしてこれは、重要値位置が「A」のアフィニティドメイン内に存在する場合に見つかる。更に別の実施形態では、参照が両方向でもよい。
【0055】
IV.アフィニティ関係インデックスの使用
一実施形態において、アフィニティ関係インデックスは、コンピューティングプラットホームで実行されるナビゲーションアプリケーションにより使用される地理的データベースの一部分である。この実施形態では、アフィニティ関係インデックスは、ユーザがナビゲーションアプリケーションに対して場所(例えば、自治体)を特定するときに使用される。例えば、ユーザは、経路案内を所望する行先として場所を特定することができる。
【0056】
上述したように、従来のナビゲーションシステム及びアプリケーションは、経路を計算して案内を与えることができる前に、行先の正確な位置を特定するに充分な情報をユーザが与えることを必要とした。ある従来のナビゲーションシステム及びアプリケーションでは、充分な情報は、行先の完全に正確な住所を含むものであった。アフィニティ関係インデックスを含む又は使用する地理的データベースでは、ユーザが場所を別々の仕方で特定することができる。ユーザは、従来のシステムの場合のように、完全に正確なアドレスを使用して場所を特定することもできるし、或いはユーザは、場所をおおよそ特定することもでき、例えば、実際の所望の場所に近い他の場所を指示することで特定することもできる。
【0057】
図10は、アフィニティ関係インデックスを使用するためのプロセス500を示す。このプロセス500は、ナビゲーションプラットホーム(図2の122)におけるナビゲーションアプリケーション(図2の132)の1つの一部分でよい。プロセス500は、行先を特定するのに使用されるものとして説明するが、別の実施形態では、このプロセスは、何らかの目的で場所を特定するのに使用することができる。図10に示すプロセスは、ユーザに情報を与えると共に、ユーザから入力を受け取ることを要求する。情報は、視覚的、又は聴覚的に、或いは視覚と聴覚の組み合せでユーザに与えることができる。ユーザからの入力は、聴覚的に、又は手動入力により、或いは他の手段により受け取ることができる。
【0058】
プロセス500によれば、ユーザには、場所を正確に特定するか又はおおよそ特定するオプションが与えられる(ステップ510)。ユーザが場所を正確に特定することを選択した場合には、アプリケーションは、その目的のための適切なメニュー及び/又はプロンプトをユーザに与えるように進む。場所を正確に特定するためのこれらメニュー及び/又はプロンプトは、従来のシステムにより行われていたものと同様でよい。
【0059】
ユーザが場所をおおよそ特定することを選択した場合には、ユーザには、実際の所望の行先に近い場所(例えば、自治体)の識別を要求するプロンプトが与えられる(ステップ520)。ユーザの入力が得られ、そしてアフィニティ関係インデックス202のサーチに使用される。アフィニティ関係インデックス202をサーチするときには、ルートレベルのエントリーからスタートしてエントリーをサーチすることができる(ステップ530)。他のレベルをサーチすることもできる。ユーザにより指示された場所に対してアフィニティ関係インデックスがサーチされた後に、3つの考えられる結果が生じ、即ち、一致が生じないか、厳密に1つの一致が生じるか、又は2つ以上の一致が生じるかである(ステップ540)。一致が生じない場合には、ユーザに、指示された場所が見つからなかったという情報が与えられ、所望の行先の付近の場所の名前に対して再び促され、そしてアフィニティ関係インデックスが再びサーチされる(ステップ550及び530)。2つ以上の一致がある場合には、ユーザにより指示された名前をもつ自治体が2つ以上あることを意味する。この場合に、アフィニティ関係インデックスは、ユーザにより指示された名前をもつ場所の近くにある他の場所に関する付加的な情報を得るのに使用される(ステップ560)。例えば、アフィニティ関係インデックスは、同じ名前をもつ多数の場所の各々がアフィニティをもつ場所のうち、どれがより高いレベルかを識別するのに使用できる。次いで、この情報をユーザに与え、ユーザは、適当な場所を選択することができる(ステップ570及び574)。例えば、ユーザが「都市Y」を指示し、そしてアフィニティ関係インデックスが、名前が「都市Y」で都市Xとアフィニティ関係をもつ1つの都市と、名前が「都市Y」で都市Zとアフィニティ関係をもつ別の都市とがあることを示す場合には、名前が「都市Y」で都市X及び都市Zに近い都市があることを指示する情報がユーザに与えられる。ユーザには、これらの1つを選択するプロンプトが与えられる。
【0060】
プロセスが、所望の行先に近い1つの場所を厳密に決定すると、その場所へのルートが計算される(ステップ580)。この機能は、経路(ルート)計算アプリケーション(図2の136)により実行される。ルートを計算するときには、ルート計算は、行先として指示された近傍の場所のポイントを使用する。例えば、近傍の場所に関連した重要値の位置(即ち、その場所の管理境界の中心)を使用することができる。ユーザの位置が得られる(ステップ590)。これは、もし利用できれば、ポジショニングシステム(図2の134)から得ることができる。或いは又、ユーザは、現在位置を指示するように促されてもよい。ユーザには、計算された経路(ルート)をたどるための案内が与えられる(ステップ600)。
【0061】
ユーザが、計算された経路をたどり続けるときに、ユーザの新たな現在位置が決定され、そしてその計算された経路をたどるために適切な案内がユーザに与えられる(再びステップ590及び600)。ユーザが行先の閾値(スレッシュホールド)内を走行すると、所望の行先を正確に特定するか又は所望の行先の近くの場所を指示することで特定するオプションがユーザに再び与えられる(ステップ610及び510)。閾値(スレッシュホールド)距離は、計算経路のスタートポイントから指示された場所の行先までの全距離のパーセンテージとして決定されてもよい。或いは又、閾値(スレッシュホールド)は、走行時間に基づいて決定されてもよい。プロセスは、ユーザが所望の行先として正確な位置を特定するまで続けられる。
【0062】
アフィニティ関係インデックスを使用するプロセスは、ユーザが経路に乗り出すときに正確なアドレスを特定しなくてよいという効果を発揮する。むしろ、ユーザは、実際の所望の行先の近くの場所を特定することができる。これは、ユーザが正確な全住所を行先として特定することが要求される場合よりも迅速に経路を計算して案内を与えるのを許す。
【0063】
多くの場合、特に、実際の所望の行先が経路のスタートポイントから比較的遠い場合には、指示された近傍の場所への経路の最初の部分が、実際の所望の行先へのルートと同じになる。
【0064】
前記プロセスにおいて、所望の行先の正確な住所を特定するようにユーザを促すためのスレッシュホールドが使用される。上述したように、このスレッシュホールドは、経路に沿って行先へ至る距離の割合でよい。或いは又、固定の距離又は別の距離を使用してもよい。又、スレッシュホールドは、走行時間に基づくものでもよい。上述したように、実際の所望の行先付近にある指示された場所への経路をたどるための案内がユーザに与えられる。多くの場合に、指示された場所への経路は、最初、実際の所望の行先への経路と同じである。しかしながら、指示された近傍の場所への経路に沿ったあるポイントにおいて、実際の所望の行先への経路がそれる。スレッシュホールドは、ユーザが実際の所望の行先の正確な住所を適時に与えることができるように決定される。
【0065】
V.別の実施形態及び効果
上述したように、アフィニティ関係インデックスは、ナビゲーションシステムのようなシステムを使用するときに場所の特定を容易にする。アフィニティ関係システムは、手動或いはスピーチ又はボイスコマンドの使用によりユーザ入力を受け容れるシステムと共に使用することができる。スピーチ又はボイスコマンドと共に使用するときには、アフィニティ関係インデックスをインタラクティブに使用して、実際の所望の行先の付近の場所(自治体)を選択して、経路案内を迅速に受け取り、従って、ユーザが行先の正確な全住所をシステムに対して特定せずに行先に向かって乗り出すことができる。従来の方法は、一般に、その性質がアルファベット順であるか、さもなければ、ユーザが正確な行先を選択するために多数の特定レベルを横断するように強制する。アフィニティ関係インデックスは、行先をインタラクティブに特定するための比較的高速な、より直観的な仕方を与える。スピーチ認識システムと共にアフィニティ関係インデックスを使用する別の効果は、サーチする必要のある異なる都市名の数を減少し、これにより、スピーチ認識システムが正しい一致をなし得る確率を改善することである。
【0066】
前記実施形態において、アフィニティ関係インデックスは、自治体の名前を、それらに接近し且つ相対的により重要な他の自治体と関連付けるのに使用された。アフィニティ関係インデックスの別の実施形態は、関心のあるポイントのような他の種類の場所に使用することができる。アフィニティ関係インデックスが他の種類の場所に使用される場合には、このような種類の場所の重要性を反映するファクタ及び/又はパラメータを含むように重要値アルゴリズムが変更される。アフィニティ関係インデックスの更に別の実施形態は、自治体を、関心のあるポイント、国立公園等の他の種類の場所に結合することができる。自治体を他の種類の場所に結合するアフィニティ関係インデックスが使用される場合には、このような種類の場所の相対的な重要値が自治体の重要値と一貫したものとなるようにファクタ及び/又はパラメータを含むよう重要値アルゴリズムが変更される。
【0067】
アフィニティ関係インデックスは、ユーザが行先を取り巻く地理的エリアに馴染みがないか、又は行先に関する完全な情報をもたず、大都市や全国的/地域的に重要な関心ポイントのような近傍の重要位置の知識をある程度もつだけである状況に特に有用である。
【0068】
アフィニティ関係インデックスは、全ての通常のサーチ方法を使用してサーチを行えるようにする。更に、アフィニティ関係インデックスは、ユーザが、大都市のみの参照を使用することにより行先選択プロセスを開始し、次いで、その特定を後で洗練することができるようにする。
【0069】
場所を正確に特定するか又はおおよそ特定するオプションがユーザに与えられることは前記で述べた。このオプションは、ユーザに明確に与えられてもよいし、暗示的に与えられてもよい。例えば、ユーザには、行先住所を正確に特定するか又は行先をおおよそ特定するための別々のメニュー選択が与えられてもよい。或いは又、ユーザの入力を使用して、正確な行先住所が特定されるか、おおよその行先位置が特定されるか決定してもよい。例えば、ユーザがワード「on」又は「at」を使用する場合には、プロセスは、ユーザが行先を正確に特定すると推論する。しかしながら、ユーザがワード「near」を使用する場合には、プロセスは、ユーザがおおよその行先を特定すると推論し、それ故、アフィニティ関係インデックスを使用して、行先に向かって経路に最初に乗り出す場所を決定する。
【0070】
アフィニティ関係インデックスと、これを使用する関連プログラムは、あいまいな即ち不完全な行先入力を、重要性が次第に高くなるか又は低くなる位置と位置との間のアフィニティの自然特性を使用して、益々の洗練さでサポートする。
【0071】
アフィニティ関係インデックスと、これを使用する関連プログラムは、空間的アフィニティ、即ち物理的な接近性しか一般的に使用しない従来のシステムに勝る効果を発揮する。アフィニティ関係インデックスの実施形態は、物理的な接近性を、重要性のハイアラーキー環境における成分として含む。付加的な実施形態は、政治的関係、空間的幾何学形状、及び歴史的重要性ファクタを含むハイアラーキーをサポートすることができる。
【0072】
以上の詳細な説明は、本発明を例示するもので、限定するものではなく、又、あらゆる等効物を含む特許請求の範囲が本発明の範囲を規定することを理解されたい。
【図面の簡単な説明】
【0073】
【図1】種々のコンピューティングプラットホームに使用するための地理的データベース製品を形成しそして配送するプロセスを示す図である。
【図2】地理的データベース製品を使用する図1のシステムの1つを示すブロック図である。
【図3A】アフィニティ関係インデックスを形成するプロセスを示すフローチャートである。
【図3B】アフィニティ関係インデックスを形成するプロセスを示すフローチャートである。
【図3C】アフィニティ関係インデックスを形成するプロセスを示すフローチャートである。
【図4】図3A、3B及び3Cのプロセスにより計算されたアフィニティドメインを示す図である。
【図5】図4のアフィニティドメインの別の図で、そこに示された他の自治体に対する重要値を付加した図である。
【図6】図3A、3B及び3Cのプロセスにより形成されたアフィニティ関係データを含む一時的ファイルの編成を示すブロック図である。
【図7A】都市に対する重要値と、図5に示すアフィニティドメインとの間の関係を示す図である。
【図7B】別の都市に対する重要値と、図5に示すアフィニティドメインとの間の関係を示す別の図である。
【図8】自治体間のアフィニティ関係を示す図である。
【図9】図3A、3B及び3Cのプロセスにより形成されたアフィニティ関係インデックスファイルデータのコンポーネントを示すブロック図である。
【図10】図9のアフィニティ関係インデックスファイルを使用するアプリケーションにより実行されるプロセスのフローチャートである。
【符号の説明】
【0074】
100:地理的データベース
101:地理的データベースデベロッパー
102:データ
110:コンパイルされたデータベース製品
118:データ集合体
120:インデックス
122:コンピューティングプラットホーム
132:ナビゲーションアプリケーション
134:ポジショニングシステム
136:経路(ルート)計算アプリケーション
140:経路(ルート)案内アプリケーション
144:地図表示アプリケーション
148:ポジショニングアプリケーション
152:行先選択アプリケーション
164:データ記憶媒体
202:アフィニティ関係インデックス
204:ソースデータベース
【特許請求の範囲】
【請求項1】
自治体のインデックスを編成する方法であって、
第1の自治体集合を含むデータ構造体をハイアラーキー式で積層されるよう形成するステップと、
前記第1の自治体集合内の各自治体に対し、1つ以上の他の自治体を、前記第1の自治体集合内の自治体と密接な関係(アフィニティ:affinity関係)を有するものとして指示するステップと、
を含み、自治体は、それが前記第1の自治体集合内の自治体のアフィニティドメイン内にある場合に、前記第1の自治体集合内の自治体と密接な関係(アフィニティ関係)をもつよう決定されることを特徴とする方法。
【請求項2】
前記自治体のアフィニティドメインは、前記自治体からの距離関数として減少する値の集合を定義する、請求項1に記載の方法。
【請求項3】
前記自治体のアフィニティドメインは、前記自治体の管理境界によって形成された多角形の中心からの距離関数として減少する値の集合を定義する、請求項1に記載の方法。
【請求項4】
前記自治体のアフィニティドメインは、前記自治体に対して決定された重要値に関連した位置からの距離関数として減少する値の集合を定義する、請求項1に記載の方法。
【請求項5】
前記自治体の重要値は、次の式により決定され、
I=APαxBNβxCKγxDRδ
但し、Pは、自治体の管理境界に対応する多角形内の人口であり、Nは、多角形内の道路交差点の数であり、Kは、多角形内に含まれる道路のキロメーター数であり、そしてRは、多角形の境界が道路を横断する数である、請求項4に記載の方法。
【請求項6】
前記A、B、C、D及びα、β、γ、δは、重要インデックスIの値を調整するのに使用されるチューニング(tuning)変数である、請求項5に記載の方法。
【請求項7】
前記自治体のアフィニティドメインは、自治からの距離関数として指数関数的に減少する値の集合を定義する、請求項1に記載の方法。
【請求項8】
前記インデックスは地理的データベースの一部分である、請求項1に記載の方法。
【請求項9】
前記インデックスは行先を見つけるのに使用される、請求項1に記載の方法。
【請求項10】
前記インデックスはナビゲーションシステムの一部分である、請求項1に記載の方法。
【請求項11】
コンピューティングシステムで行先への案内を与える方法であって、
所望する実際の行先の近傍にある自治体を指示するユーザ入力を受け取るステップと、
前記所望する実際の行先の近傍にある自治体に対する第1ルートを計算するステップと、
前記所望する実際の行先の近傍にある自治体に対する第1ルートをたどるようにユーザに案内を与えるステップと、
前記所望する実際の行先の近傍にある自治体に対するルート上で、前記所望する実際の行先の正確な位置を指示するユーザ入力を受け取るステップと、
前記所望する実際の行先に対する第2ルートを計算するステップと、
前記所望する実際の行先に対する前記第2ルートをたどるようにユーザに案内を与えるステップと、を備えた方法。
【請求項12】
前記所望する実際の行先の近傍にある自治体に対する前記第1ルートを計算する前に、他の自治体の重要度に基づいて自治体を他の自治体に関連付けるアフィニティ関係インデックスを使用するステップを更に備えた、請求項11に記載の方法。
【請求項13】
前記第1ルートは、前記所望する実際の行先の近傍にある自治体に関連する位置を行先とする、請求項11に記載の方法。
【請求項14】
前記第1ルートは、前記所望する実際の行先の近傍にある自治体の管理境界に対応する多角形の中心を行先とする、請求項11に記載の方法。
【請求項15】
前記所望する実際の行先付近の自治体を指示するユーザ入力を受け取る前に、前記所望する行先を正確に特定するか又は近傍の自治体を指示することで特定するオプションをユーザに与えるステップを更に備えた、請求項11に記載の方法。
【請求項16】
前記所望する実際の行先の近傍にある自治体に対するルート上で、且つ前記所望する実際の行先の正確な位置を指示するユーザ入力を受け取る前に、前記所望する実際の行先の正確な位置を指示するようにユーザに要求するステップを更に備えた、請求項11に記載の方法。
【請求項17】
前記所望する実際の行先の正確な位置を指示するようにユーザに要求する前記ステップは、ユーザが前記ルートに沿った所定の閾値(threshold)に到達したときに行う、請求項16に記載の方法。
【請求項18】
前記所望する実際の行先の近傍にある自治体に対する前記ルート上で、且つ前記所望する実際の行先の正確な位置を指示するユーザからの入力を受け取る前に、前記所望する実際の行先の正確な位置を指示する、又は所望する実際の行先の近傍にある別の自治体を指示するオプションをユーザに与えるステップを更に備えた、請求項11に記載の方法。
【請求項19】
システムで行先を特定する方法であって、
所望する実際の行先が近くにある自治体を指示するステップと、
前記自治体へ走行するための案内を受け取るステップと、
前記自治体へのルートにある間に、前記実際の所望の行先の正確な住所を指示するステップと、
前記所望する実際の行先に対する前記正確な住所へ走行するための案内を受け取るステップと、を備えた方法。
【請求項20】
前記所望する実際の行先が近くにある自治体を指示する前に、行先を正確に選択するか、又は近傍の自治体を選択するオプションを受け取るステップを更に備えた、請求項19に記載の方法。
【請求項1】
自治体のインデックスを編成する方法であって、
第1の自治体集合を含むデータ構造体をハイアラーキー式で積層されるよう形成するステップと、
前記第1の自治体集合内の各自治体に対し、1つ以上の他の自治体を、前記第1の自治体集合内の自治体と密接な関係(アフィニティ:affinity関係)を有するものとして指示するステップと、
を含み、自治体は、それが前記第1の自治体集合内の自治体のアフィニティドメイン内にある場合に、前記第1の自治体集合内の自治体と密接な関係(アフィニティ関係)をもつよう決定されることを特徴とする方法。
【請求項2】
前記自治体のアフィニティドメインは、前記自治体からの距離関数として減少する値の集合を定義する、請求項1に記載の方法。
【請求項3】
前記自治体のアフィニティドメインは、前記自治体の管理境界によって形成された多角形の中心からの距離関数として減少する値の集合を定義する、請求項1に記載の方法。
【請求項4】
前記自治体のアフィニティドメインは、前記自治体に対して決定された重要値に関連した位置からの距離関数として減少する値の集合を定義する、請求項1に記載の方法。
【請求項5】
前記自治体の重要値は、次の式により決定され、
I=APαxBNβxCKγxDRδ
但し、Pは、自治体の管理境界に対応する多角形内の人口であり、Nは、多角形内の道路交差点の数であり、Kは、多角形内に含まれる道路のキロメーター数であり、そしてRは、多角形の境界が道路を横断する数である、請求項4に記載の方法。
【請求項6】
前記A、B、C、D及びα、β、γ、δは、重要インデックスIの値を調整するのに使用されるチューニング(tuning)変数である、請求項5に記載の方法。
【請求項7】
前記自治体のアフィニティドメインは、自治からの距離関数として指数関数的に減少する値の集合を定義する、請求項1に記載の方法。
【請求項8】
前記インデックスは地理的データベースの一部分である、請求項1に記載の方法。
【請求項9】
前記インデックスは行先を見つけるのに使用される、請求項1に記載の方法。
【請求項10】
前記インデックスはナビゲーションシステムの一部分である、請求項1に記載の方法。
【請求項11】
コンピューティングシステムで行先への案内を与える方法であって、
所望する実際の行先の近傍にある自治体を指示するユーザ入力を受け取るステップと、
前記所望する実際の行先の近傍にある自治体に対する第1ルートを計算するステップと、
前記所望する実際の行先の近傍にある自治体に対する第1ルートをたどるようにユーザに案内を与えるステップと、
前記所望する実際の行先の近傍にある自治体に対するルート上で、前記所望する実際の行先の正確な位置を指示するユーザ入力を受け取るステップと、
前記所望する実際の行先に対する第2ルートを計算するステップと、
前記所望する実際の行先に対する前記第2ルートをたどるようにユーザに案内を与えるステップと、を備えた方法。
【請求項12】
前記所望する実際の行先の近傍にある自治体に対する前記第1ルートを計算する前に、他の自治体の重要度に基づいて自治体を他の自治体に関連付けるアフィニティ関係インデックスを使用するステップを更に備えた、請求項11に記載の方法。
【請求項13】
前記第1ルートは、前記所望する実際の行先の近傍にある自治体に関連する位置を行先とする、請求項11に記載の方法。
【請求項14】
前記第1ルートは、前記所望する実際の行先の近傍にある自治体の管理境界に対応する多角形の中心を行先とする、請求項11に記載の方法。
【請求項15】
前記所望する実際の行先付近の自治体を指示するユーザ入力を受け取る前に、前記所望する行先を正確に特定するか又は近傍の自治体を指示することで特定するオプションをユーザに与えるステップを更に備えた、請求項11に記載の方法。
【請求項16】
前記所望する実際の行先の近傍にある自治体に対するルート上で、且つ前記所望する実際の行先の正確な位置を指示するユーザ入力を受け取る前に、前記所望する実際の行先の正確な位置を指示するようにユーザに要求するステップを更に備えた、請求項11に記載の方法。
【請求項17】
前記所望する実際の行先の正確な位置を指示するようにユーザに要求する前記ステップは、ユーザが前記ルートに沿った所定の閾値(threshold)に到達したときに行う、請求項16に記載の方法。
【請求項18】
前記所望する実際の行先の近傍にある自治体に対する前記ルート上で、且つ前記所望する実際の行先の正確な位置を指示するユーザからの入力を受け取る前に、前記所望する実際の行先の正確な位置を指示する、又は所望する実際の行先の近傍にある別の自治体を指示するオプションをユーザに与えるステップを更に備えた、請求項11に記載の方法。
【請求項19】
システムで行先を特定する方法であって、
所望する実際の行先が近くにある自治体を指示するステップと、
前記自治体へ走行するための案内を受け取るステップと、
前記自治体へのルートにある間に、前記実際の所望の行先の正確な住所を指示するステップと、
前記所望する実際の行先に対する前記正確な住所へ走行するための案内を受け取るステップと、を備えた方法。
【請求項20】
前記所望する実際の行先が近くにある自治体を指示する前に、行先を正確に選択するか、又は近傍の自治体を選択するオプションを受け取るステップを更に備えた、請求項19に記載の方法。
【図1】
【図2】
【図3A】
【図3B】
【図3C】
【図4】
【図5】
【図6】
【図7A】
【図7B】
【図8】
【図9】
【図10】
【図2】
【図3A】
【図3B】
【図3C】
【図4】
【図5】
【図6】
【図7A】
【図7B】
【図8】
【図9】
【図10】
【公開番号】特開2006−308579(P2006−308579A)
【公開日】平成18年11月9日(2006.11.9)
【国際特許分類】
【外国語出願】
【出願番号】特願2006−100125(P2006−100125)
【出願日】平成18年3月3日(2006.3.3)
【出願人】(504390584)ナヴテック ノース アメリカ リミテッド ライアビリティ カンパニー (12)
【Fターム(参考)】
【公開日】平成18年11月9日(2006.11.9)
【国際特許分類】
【出願番号】特願2006−100125(P2006−100125)
【出願日】平成18年3月3日(2006.3.3)
【出願人】(504390584)ナヴテック ノース アメリカ リミテッド ライアビリティ カンパニー (12)
【Fターム(参考)】
[ Back to top ]