JP2006308579A - アフィニティのための地図データを編成する方法及びそれを使用するためのアプリケーション - Google Patents

Abstract

【課題】行先を特定するためにナビゲーションシステム又は他のコンピューティングプラットホームのアプリケーションに使用できるインデックス方法を提供する。
【解決手段】アフィニティ関係インデックス、及びこれを使用する方法が開示される。アフィニティ関係インデックスは、所与の場所の名前に対し、１つ以上の潜在的により重要な場所の名前に対するアフィニティを捕える。このようなより重要な各場所は、他の場所がその中にあると思われるところのアフィニティドメインを抱いている。インデックスは、これをハイアラーキー式に保持し、そしてユーザが意図する行先に対して迅速にサーチできる比較的意義のある且つ最小の構造体を生成するという作用を有する。アプリケーションは、これらのアフィニティドメインを使用して、案内される旅程に乗り出すに必要なインストラクションを決定するのであって、旅程を完了するに必要な全てのインストラクションを決定するのではない。
【選択図】図１

Description

本発明は、場所を特定する方法に係り、より詳細には、行先を特定するためのナビゲーションシステム又は他のコンピューティングプラットホームのアプリケーションに使用できるインデックス方法に係る。

ナビゲーションに関係した機能が種々の異なるコンピュータプラットホームに設けられている。例えば、ナビゲーションに関係した機能は、スタンドアローンシステム又はネットワークシステムと共に設けることができる。スタンドアローンシステムでは、ソフトウェアアプリケーション、地理的データ及びハードウェアが単一の位置において結合される。スタンドアローンシステムは、乗物にインストールしてもよいし又は個人が携帯してもよい。ネットワークシステムでは、ソフトウェア又は地理的データのあるものは、ユーザを伴うハードウェアと共に配置され、そしてソフトウェア又は地理的データのあるものは、遠隔に配置されて通信システムを経てアクセスされる。ナビゲーションに関係した機能は、専用プラットホームで実施されるシステムにより与えられ、ここでは、ハードウェア及びソフトウェアがナビゲーション目的で特に設計される。或いは又、ナビゲーションに関係した特徴を与えるシステムは、適切なソフトウェアアプリケーション及びデータを使用して汎用のコンピューティングプラットホーム（例えば、パーソナルコンピュータ、パーソナルデジタルアシスタント、又はネットワーク型コンピュータ）において実施することができる。

ナビゲーションアプリケーションを実行する専用のナビゲーションシステム及び汎用のコンピューティングプラットホーム（以下、集合的に「ナビゲーションシステム」と称する。）は、種々様々な有用な特徴及びサービスを提供する。例えば、乗物に使用されるナビゲーションシステムは、所望の行先へ運転するための詳細なインストラクションを与え、走行時間及び経費を減少することができる。又、ナビゲーションシステム及びナビゲーションアプリケーションは、所望のタイプの会社をサーチし、そしてその会社の位置へのルート案内を与えることもできる。

これらのシステムに関連した１つの事柄は、ユーザがどのようにしてシステムに場所を特定するかに関する。例えば、ユーザが行先へのルートをたどるためにナビゲーションシステムから案内を得たいときには、ユーザが何らかの手段によりシステムに行先を指示することが必要である。行先を特定する機能は、種々の理由で複雑なものとなる。多くのシステムは、行先の正確な位置がユーザにより完全に指示されるまで、ルートを計算しなかったり、案内を与えない。しかしながら、ある場合には、ユーザは、都市や街路の正確なつづりを知らないことがある。都市や町が同じ又は同様の名前をもつときには、別の複雑さが考えられる。

従って、ユーザがシステムに行先のような位置を特定できる方法を改善することが要望される。例えば、計算されたルートを得るためにユーザが行先を特定する方法を改善することが要望される。

これら及び他の目的に対処するために、本発明は、ナビゲーションシステムに対する迅速且つ便利な行先入力及び案内を可能にするようなデジタル地図データを編成するための実施形態を包含する。２つの関連するコンポーネントが含まれる。その第１は、所与の場所の名前に対し、１つ以上の潜在的により重要な場所の名前に対する密接な関係（アフィニティ：affinity）を捕える仕方で場所の名前をインデックスする手段である。このようなより重要な各場所は、他の場所がその中にあると思われるところのアフィニティドメインを抱いている。これは、ハイアラーキー式に保持され、そしてユーザが意図する行先に対して迅速にサーチできる比較的意義のある且つ最小の構造体を生成するという作用を有する。第２のコンポーネントは、これらのアフィニティドメインを使用して、案内される旅程に乗り出すに必要なインストラクションを決定するのであって、旅程を完了するに必要な全てのインストラクションを決定するのではない。

Ｉ．地理的データベース形成の概要
図１は、地理的データベースのマスター即ちソースバージョン１００を示す。地理的データベースのマスターバージョンは、地理的データベースデベロッパー１０１（「地図デベロッパー」、「地図データデベロッパー」等とも称される。）により所有され、開発される。（１つのソースデータベース及び地理的データベースデベロッパーしか示されていないが、ここに示す実施形態は、単一のソースデータベース又は単一の地理的データベースデベロッパーに限定されない。）

地理的データベースのマスターバージョン１００は、地理的カバレージエリアにおける特徴を表わすデータ１０２（「地理的データ」又は「空間的データ」とも称される。）を含む。地理的カバレージエリアは、米国のような国全体に対応してもよい。或いは又、地理的カバレージエリアは、多数の国々、例えば、米国、カナダ及びメキシコ、或いはフランス、ドイツ及びイタリア、等々に対応してもよい。別の態様によれば、地理的データベースのマスターバージョン１００の地理的カバレージエリアは、国内の単一領域、例えば、米国のウェストコースト又はミッドウェストを表わすだけでもよい。地理的データベースのマスターバージョン１００は、全地理的カバレージエリアにおける地理的特徴を表わすデータを含むが、地理的データベースのデータにより表わされない地理的特徴を含むか、又は地理的特徴の表示が希薄であるような地理的カバレージエリアの部分も存在し得る。

地理的データベースのマスターバージョン１００は、地理的カバレージエリア内に位置する道路網に関するデータを含む。道路網に関するデータは、色々な種類の情報、例えば、道路の位置の地理的座標、道路のストリート名、道路に沿った住所範囲、道路の交差点における転回制限、等々を含む。又、地理的データベースのマスターバージョン１００は、カバーされた地理的エリアにおける関心のあるポイントに関するデータも含む。関心のあるポイントは、ホテル、レストラン、美術館、スタジアム、オフィス、自動車販売店、自動車修理店、等々を含むことができる。地理的データベースのマスターバージョン１００は、これら関心のあるポイントの位置に関するデータを含むことができる。又、地理的データベースのマスターバージョン１００は、都市、町、又は他のコミュニティのような場所に関するデータや、水域、山脈等の他の地理的特徴を含むこともできる。更に、地理的データベースのマスターバージョン１００は、他の種類の情報を含んでもよい。

データを収集するために種々の方法が地理的データベースデベロッパー１０１により使用されている。これらの方法は、自治体や航空写真のような他のソースからデータを得ることを含む。更に、地理的データベースデベロッパー１０１は、現場要員を雇って地理的領域全体にわたり道路に沿って乗物で走行し、特徴を観察すると共に、それらに関する情報を記録することができる。地理的データベースデベロッパー１０１により収集されたデータは、地理的データベースのマスターバージョン１００に記憶される。

地理的データベースデベロッパー１０１は、地理的カバレージエリアにおける特徴を表わすデータを進行形態で収集し続ける。地理的データベースデベロッパーがデータを収集し続ける１つの理由は、カバレージエリアにおける特徴が時間と共に変化するからである。従って、地理的データベースデベロッパー１０１は、特徴に関する以前に収集したデータを更新又は確認するために、その同じ特徴に関するデータを収集する。地理的データベースデベロッパー１０１がデータを収集し続ける別の理由は、地理的データベースのマスターバージョン１００のカバレージ及び／又は詳細を拡張するためである。例えば、ある時点に、地理的データベースのマスターバージョン１００は、全カバレージエリアの一部分だけを表わすデータを含んでもよい。その時点以降に、地理的データベースデベロッパー１０１は、以前に表わされなかったエリアにおける特徴に関するデータを収集し、地理的データベースのマスターバージョン１００のカバレージを拡張する。

地理的データベースのマスターバージョン１００は、地理的カバレージエリアに関する最新のデータを有するコピーとして維持される。従って、地理的データベースのマスターバージョン１００は、規則的で且つ連続的なベースで、更新され、拡張され、及び／又はその他変更される。これらのオペレーションを容易にするために、地理的データベースのマスターバージョン１００は、更新、維持、及び開発を容易にするフォーマットで記憶される。例えば、マスターバージョン１００のデータは、非圧縮でもよい。適当なフォーマットは、例えば、バーチャル・ストレージ・アクセス・メソッド（ＶＳＡＭ）フォーマットを含むが、他の種類のフォーマット、独占的及び非独占的の両方、も適している。一般に、マスターデータベース１００のフォーマットは、ナビゲーションシステムに使用するのには適していない。

一実施形態では、地理的データベースのマスターバージョン１００は、１つ以上のハードドライブ、テープ又は他の媒体の位置に記憶され、そして適切なコンピュータでアクセスされる。メインフレームコンピュータ、複数のネットワーク型マイクロコンピュータ等の適当なコンピュータを使用することができる。

地理的データベースのマスターバージョン１００からのデータは、コンパイルされたデータベース製品１１０を形成するのに使用される。このコンパイルされたデータベース製品１１０は、コンパイラー１１１を使用して作られる。コンパイラー１１１は、適当なコンピュータプラットホームで実行されるソフトウェアプログラムである。コンパイルされたデータベース製品１１０は、地理的データベースデベロッパー１０１により形成されてもよいし、或いは別のエンティティ、例えば、地理的データベースデベロッパーからデータを取得するか又はライセンス契約する地理的データベースデベロッパーの顧客により形成されてもよい。コンパイルされたデータベース製品を形成する前に、地理的データベースのマスターバージョン１００からのデータは、ＧＤＦフォーマットのような１つ以上の中間フォーマットにコンパイルされ又は配送されてもよい。

コンパイルされたデータベース製品１１０は、地理的データベースのマスターバージョン１００における全データの一部分のみを含んでもよい。例えば、コンパイルされたデータベース製品１１０は、地理的データベースのマスターバージョン１００のカバレージエリア内の１つ以上の特定のサブエリアのみに関連したデータを含んでもよい。更に、コンパイルされたデータベース製品１１０は、地理的データベースのマスターバージョン１００で表わされる地理的特徴を記述する全てのデータ属性より少数のものを含んでもよい。

コンパイルされたデータベース製品１１０において、地理的データは、地理的データベースのマスターバージョン１００の場合とは異なる仕方で編成される。コンパイルされたデータベースは、それがインストールされるコンピューティングプラットホームにおけるデータの使用を容易にする形態で編成され、配列され、構造化されそして記憶される。例えば、コンパイルされたデータベース製品１１０では、データは、特定の機能を実行するに必要な属性のみを各々含む個別のデータ集合体１１８へと編成されてもよい。例えば、１つのデータ集合体は、ルート計算を実行するのに必要な属性のみを含み、別の集合体は、ポジショニングに必要な属性のみを含み、又、更に別の集合体は、行先選択に必要な属性のみを含んでもよい。

又、コンパイルされたデータベース製品１１０は、地理的データの集合体を異なるレベル又はスケールで含んでもよい。例えば、１つのデータ集合体は、カバレージエリア内の全ての道路を含んでもよく、そして同じデータベースの別のデータ集合体は、より高い機能クラスの道路、即ち制御されたアクセス道路のような比較的高い交通量を輸送する道路、のみを含んでもよい。

又、コンパイルされたデータベース１１０は、データ集合体の幾つかを空間的に編成してもよく、即ち物理的に互いに接近した地理的特徴が、データベース内で互いに接近配置されたデータにより表わされるように編成してもよい。

コンパイルされたデータベースは、マスター地理的データベース１００に見られないデータエンティティを含んでもよい。例えば、コンパイルされた地理的データベース１１０は、マスター地理的データベース１００内の多数の異なるデータエンティティの複合体であるか、又はマスター地理的データベース１００内のデータエンティティから導出されたものであるデータエンティティを含んでもよい。

又、コンパイルされたデータベース製品は、それが位置する媒体に圧縮フォーマットで記憶されてもよい。
又、コンパイルされたデータベースは、１つ以上のインデックス１２０を含んでもよい。種々のデータ集合体を互いに関連付けるインデックス、データをそれが記憶された媒体において見つけるためのインデックス、及びデータ集合体内で特定の情報を見つけるためのインデックスを含む種々の形式のインデックス１２０が含まれてもよい。

地理的データをコンピューティングプラットホームに使用するように編成できる幾つかの仕方が、参考としてここに全開示を援用する米国特許第５，９５３，７２２号、第５，９６８，１０９号、第５，９７４，４１９号、第６，０３８，５５９号、第６，１１２，２００号、第６，０８１，８０３号、第６，１１８，４０４号、第６，１２２，５９３号、第６，１８４，８２３号、第６，２４９，７４２号、第６，３０８，１７７号、第６，３２４，４７０号、第６，３３６，１１１号、第６，３９３，１４９号、第６，４６０，０４６号、第６，４７３，７７０号、第６，５０７，８５０号、第６，５９１，２７０号、第６，６００，８４１号、第６，７５１，６２９号、第６，７６８，８１８号、第６，７８２，３１９号、及び第６，８２９，６９０号に説明されている。

II．コンピューティングプラットホームにおける地理的データの使用
コンパイルされたデータベース製品１１０は、色々な種類のコンピューティングプラットホーム１２２において使用される。コンピューティングプラットホーム１２２は、乗物内ナビゲーションシステム、ハンドヘルドポータブルナビゲーションシステム、パーソナルコンピュータ（デスクトップ及びノードブックコンピュータを含む）、及び他の種類のデバイス、例えば、パーソナルデジタルアシスタント（ＰＤＡ）デバイス、ページャー、電話等を含む。又、コンパイルされたデータベース製品１１０は、インターネットに接続されたシステムを含むネットワーク型コンピューティングプラットホーム及び環境にも使用される。

コンピューティングプラットホーム１２２に使用されるコンパイルされたデータベース製品１１０は、適当な媒体に記憶される。例えば、コンパイルされたデータベースは、ＣＤ−ＲＯＭディスク、ハードドライブ、ＤＶＤディスク、フラッシュメモリ、メモリカード、或いは現在入手できるか又は将来入手できるようになる他の形式の媒体に記憶することができる。

コンピューティングプラットホーム１２２では、コンパイルされたデータベース製品１１０が種々のソフトウェアアプリケーションにより使用される。例えば、コンパイルされたデータベース製品１１０は、ナビゲーションに関連した機能、例えば、ルート計算、ルート案内、乗物のポジショニング、地図表示、及び電子的イエローページ、並びに他の種類の機能を与えるソフトウェアアプリケーションにより使用することができる。

図２は、コンピューティングプラットホーム１２２の幾つかのコンポーネントを示すブロック図である。図２に示すコンピューティングプラットホーム１２２は、ナビゲーション用の幾つかのコンポーネントを含むものである。コンピューティングプラットホーム１２２は、ポジショニングシステム１３４を備えている。このポジショニングシステム１３４は、ポータブルナビゲーションシステム１３０の現在位置を決定する。ポジショニングシステム１３４は、いかなる位置感知装置又は技術により実施されてもよい。例えば、ポジショニングシステムは、ＧＰＳユニット、或いは到着時間、到着方向、三角法、ＷｉＦｉ、ＲＦＩＤ、Ｌｏｒａｎ、デッドレコニング(dead reckoning)、或いはこれら又は他のシステムの組み合せを使用するシステムを含んでもよい。

この実施形態では、コンピューティングプラットホーム１２２は、ナビゲーションアプリケーション１３２を備えている。このナビゲーションアプリケーション１３２は、ナビゲーションに関連するか又は地図に関連したある機能を実行するソフトウェアプログラムである。これらのナビゲーションアプリケーション１３２は、コンピューティングプラットホーム１２２における適当なデータ記憶媒体に記憶される。ナビゲーションアプリケーション１３２は、必要なときに実行される。ナビゲーションアプリケーション１３２間に含まれるのは、ルート計算アプリケーション１３６、ルート案内アプリケーション１４０、地図表示アプリケーション１４４、ポジショニングアプリケーション１４８、及び行先選択アプリケーション１５２である。他の実施形態は、これらアプリケーションをより多く又はより少なく有してもよい。或いは又、ある実施形態では、これらアプリケーションの２つ以上を組み合せてもよい。

コンピューティングプラットホーム１２２は、コンパイルされたデータベース製品１１０の１つを含む。コンパイルされたデータベース製品１１０は、コンピューティングプラットホーム１２２においてデータ記憶媒体１６４に記憶される。コンパイルされたデータベース製品１１０は、ナビゲーション関連機能を与えるためにナビゲーションアプリケーション１３２により使用される。地図データベース１６０は、カバーされた地理的エリアにおける道路、交差点、関心のあるポイント、及び他の地理的特徴に関する情報を含む。カバーされた地理的エリアは、１つ以上の都会エリア、州、国、領域又はその組み合せを含んでもよい。

ナビゲーションアプリケーション１３２は、一緒に機能しコンパイルされたデータベース製品１１０を使用して、色々な種類のナビゲーション機能を与える。例えば、ナビゲーションアプリケーションは、所望の行先へのルートを得るのに使用できる。この例によれば、ユーザは、行先選択アプリケーション１５２を使用して、所望の場所を見つけることができる。ルートの出発点は、ポジショニングシステム１３４と一緒に使用されるポジショニングアプリケーション１４８により決定されるユーザの位置であると仮定される。所望の行先の位置及び出発点の位置を指示するデータは、ルート計算アプリケーション１３６へ転送される。このルート計算アプリケーション１３６は、出発点から行先までのルートを決定し、次いで、ルートを指示するデータをルート案内アプリケーション１４０へ転送する。ルート案内アプリケーション１４０は、ルートをたどるためにユーザに適した方向を発生する。

コンピューティングプラットホーム１２２を使用し、ユーザをルートに沿って行先へ案内するときには、ユーザが位置するエリアのグラフィック地図をユーザに示すことが有用である。地図表示アプリケーション１４４は、この目的で使用することができる。地図表示アプリケーション１４４は、ルート計算アプリケーション１３６からルートを指示するデータを受け取ると共に、ポジショニングアプリケーション１４８からユーザの現在位置を指示するデータを受け取る。地図表示アプリケーション１４４は、コンパイルされたデータベース製品１１０からのデータにアクセスして、ユーザの現在位置の周りの地理的エリアのグラフィック地図像を発生する。地図表示アプリケーション１４４は、コンピューティングプラットホーム１２２のディスプレイスクリーンに像をレンダリングし、ユーザの現在位置の周りの地理的エリアを示す。像は、ユーザの付近に位置する道路を示してもよい。ユーザの現在位置を指示するために、インジケータマークを像に重畳してもよい。又、ユーザがたどるべきルートを、ハイライトにより、像において指示してもよい。

III．アフィニティ関係インデックスの形成
図３Ａ、３Ｂ及び３Ｃは、アフィニティ関係インデックス２０２を形成するためのプロセス２００を示す。プロセス２００は、適当なコンピューティングプラットホーム１２２に使用される地図データベース製品１１０を形成するときにコンパイラー１１１（図１）により実行されるコンパイルプロセスの一部分でよい。プロセス２００は、ソースデータベース２０４からのデータを使用する。ソースデータベース２０４は、マスター地理的データベース１００、又はこのソースデータベース１００から派生したデータベース、例えば、中間、交換又は配送フォーマットのデータベースでよい。プロセス２００は、ソースデータベース２０４からのデータを入力として使用し、そして１つ以上のアフィニティ関係インデックス２０２の形態で出力を与える。アフィニティ関係インデックス２０２は、コンパイルされた地理的データベース製品１１０を形成するときに作られる図１のインデックス１３２の１つに含まれてもよい。

プロセス２００は、カバーされた領域内の各自治体に対して実行される一連のステップを含む。（説明上、自治体という語は、種々の形式の法的に編成されたコミュニティ、例えば、市、町、村、等を含む。）図３Ａを参照すれば、プロセス２００は、ソースデータベース２０４のカバレージ領域で表わされた全ての自治体から１つの自治体を選択する（ステップ２０８）。選択された自治体に対して、プロセスは、自治体の管理境界に対応する多角形内の人口を指示する情報をソースデータベース２０４からアクセスする（ステップ２１０）。次いで、プロセスは、ソースデータベース２０４にアクセスし、その多角形内に位置する道路網におけるノード（即ち交差点）の数Ｎのカウントを決定する（ステップ２２０）。次いで、プロセスは、ソースデータベース２０４にアクセスし、そして自治体の管理境界に対応する多角形内に包囲された道路のキロメーター数Ｋを計算する（ステップ２３０）。次いで、プロセスは、ソースデータベース２０４にアクセスし、そして自治体の管理境界に対応する多角形の道路横断の数Ｒをカウントする（ステップ２４０）。

ソースデータベース２０４から得られ又は導出されたこの情報を使用して、プロセスは、自治体に対する重要値Ｉを計算する（ステップ２５０）。プロセスは、次の式を使用する。
Ｉ＝ＡＰ^αｘＢＮ^βｘＣＫ^γｘＤＲ^δ
但し、Ｐは、自治体の管理境界多角形内の人口であり、Ｎは、同じ多角形内に存在する道路網におけるノードの数であり、Ｋは、多角形内に含まれる道路のキロメーター数であり、そしてＲは、多角形の境界が道路を横断する数である。大文字の係数及び小文字の指数は、重要度インデックスＩの値を調整するのに使用されるチューニング変数である。

プロセスが自治体に対する重要値を計算すると、その重要値に対する地理的な位置が決定される（ステップ２６０）。この実施形態では、自治体の管理境界に対応する多角形の中心の地理的座標が決定されて、重要値の地理的位置として使用される。重要値を指示するデータ、重要値に関連した中心位置、及び自治体の認識が、一時的に記憶される（ステップ２７０）。この目的のために、一時的データベース２８０又はスクラッチファイルを使用してもよい。プロセス２００は、ソースデータベース２０４により表わされたカバーされた領域における別の自治体を選択するように進み（ステップ２９０）、そしてソースデータベース２０４にアクセスして自治体に関する情報を得ると共に、重要値及びその重要値に対する関連位置（即ち中心）を計算するに必要な情報を導出するという同じステップ（即ち、ステップ２１０、２２０、２３０、２４０、２５０及び２６０）を実行する。この自治体に対する重要値、その関連位置、及びその関連自治体を識別する情報が記憶される（ステップ２７０）。このプロセスは、カバーされた領域における全ての自治体に対する重要値及びそれに関連した位置を決定して記憶するように続けられ、やがて、全ての自治体に対する重要値及びそれに関連した位置が計算されて一時的データベース２８０に記憶される（ステップ２９０）。

ソースデータベース２０４で表わされた全ての自治体に対して重要値及びそれに対応する位置が決定されて記憶された後、プロセス２００は、ソースデータベース２０４で表わされた自治体に対してアフィニティ関係のインデックスを決定することで続けられる。アフィニティ関係を決定する際に、プロセスは、各自治体間の距離と組み合せて各自治体に対して決定された重要値を使用して、アフィニティ関係インデックスのどのレベルを自治体が占有するか、及び他の地自体のどれが所与の自治体とのアフィニティ関係を有するか決定する。

図３Ｂは、アフィニティ関係のインデックスを決定するためのプロセス２００のステップを示す。このプロセスは、最も大きな重要値を決定しそしてそれに関連した自治体を選択することで継続される（ステップ３００及び３１０）。この自治体に対するアフィニティドメインが計算される（ステップ３２０）。このアフィニティドメインは、自治体に関連した位置、この実施形態では、自治体の管理境界により形成される多角形の中心、からの距離関数である値（即ち、アフィニティ値）を各ポイントが有するような円形領域を画成する。自治体の中心の位置にあるこのアフィニティ値は、自治体に対して決定される重要値に対応する。又、この値は、自治体に対するアフィニティドメインの最大値でもある。自治体に対するアフィニティ値は、あらゆる方向に等しく先細りとなる。アフィニティ値の先細りの割合は、指数関数、双曲線関数、又は他の適当な関数により定義することができる。

アフィニティドメインを画成するのに使用される関数に基づいて、アフィニティ値は、自治体の中心からの距離関数として減少し続ける。自治体の中心からのある距離において、アフィニティ値は、所定の最小スレッシュホールド値Ｔ_MINに対応する値へと先細りになる。アフィニティ値が最小閾値（スレッシュホールド値）Ｔ_MINに到達する位置は、その自治体に対するアフィニティドメインの水平境界を定義する（ステップ３３０）。ある実施形態では、大きな都市に対するアフィニティドメインの水平境界は、都市のより大きな都会エリア、即ち都市とその郊外にほぼ対応してもよい。

図４は、自治体、即ち都市Ａに対して計算されたアフィニティドメインを示す。このアフィニティドメインは、自治体の中心に位置する重要値に対応するピーク値を有することに注意されたい。アフィニティドメインは、ピークから最小閾値（スレッシュホールド）へと軸対称に先細りとなる。

再び図３Ｂを参照すれば、プロセスは、次いで、そのアフィニティドメインの地理的エリア（即ち足跡）内に包囲された他の自治体に関連した全ての重要値位置を決定する（ステップ３４０）。図５は、アフィニティドメイン内に位置する重要値位置を有する他の自治体を決定するステップを示す。図５において、都市Ｂ、Ｃ、Ｄ、Ｅ、Ｇ及びＨは、都市Ａのアフィニティドメイン内に位置する重要値を有する。都市Ｆの重要値は、都市Ａのアフィニティドメイン内にないことに注意されたい。（簡単化のために、図５では、６つの自治体が都市Ａのアフィニティドメイン内に重要値位置を有するものとして示されている。実際の実世界の例では、より多数の、例えば、百以上の自治体が大都市のアフィニティドメイン内に位置することがある。）

再び図３Ｂを参照すれば、アフィニティドメイン内に置かれた重要値位置を有する自治体の各々は、そのアフィニティドメインに関連した自治体とアフィニティ関係を有すると決定される。これら自治体が、アフィニティドメインに関連した自治体とアフィニティ関係を有すること（この関係において「優勢な自治体」と称される。）を指示するデータは、一時的データファイル３４４に記憶される（ステップ３５０）。図６は、一時的データファイル３４４に記憶されたアフィニティ関係情報を示す。

再び図３Ｂを参照すれば、プロセスは、アフィニティドメインに関連した自治体とアフィニティ関係を有すると決定された自治体が、そのアフィニティドメインに関連した自治体と同じインデックスレベルの位置を占有するに充分なほど重要であるかどうか決定する（ステップ３６０）。この決定を行うために、アフィニティドメインの足跡内に置かれた重要値を有する各自治体の重要値は、その位置におけるアフィニティ値と比較される。優勢な自治体のアフィニティ値を越える重要値を有する自治体は、その優勢な自治体と同じインデックスレベルの位置を占有するに充分なほど重要であると決定される。

図７Ａ及び７Ｂは、ある自治体がその優勢な自治体のアフィニティ値を越えるような重要値を有するかどうか決定するステップを示す。図７Ａは、図５の都市Ａに対するアフィニティドメインを、都市Ａ及び都市Ｈに対する重要値の位置を通る平面において示す縦断面図である。図７Ａにおいて、都市Ｈの重要値は、都市Ａのアフィニティ値ドメインを越えることが示されている。従って、都市Ｈは、都市Ａと同じインデックスレベルの位置を占有するに充分なほど重要である。図７Ｂは、図５の都市Ａに対するアフィニティドメインを、都市Ａ及び都市Ｇに対する重要値の位置を通る平面において示す縦断面図である。図７Ｂにおいて、都市Ｇの重要値は、都市Ａのアフィニティ値を越えるように示されていない。従って、都市Ｇは、都市Ａと同じインデックスレベルの位置を占有するに充分なほど重要でない。

再び図３を参照すれば、アフィニティドメイン内のどの自治体が、そのアフィニティドメインに関連した自治体と同じインデックスレベルの位置を占有するに充分なほど重要であり、且つアフィニティドメイン内のどの自治体が、そのアフィニティドメインに関連した自治体と同じインデックスレベルの位置を占有するに充分なほど重要でないかをプロセスが決定した後に、このような決定を指示するデータが一時的記憶ファイル３４４に記憶される（ステップ３７０）。

このプロセスは、アフィニティドメインに関連した自治体を一時的データベースファイル２８０から除去する（又は終了とマークする）ことで続けられる（ステップ３８０）。次いで、このプロセスは、ソースデータベース２０４のデータにより表わされた別の自治体を選択し、そして他の自治体のどれがその選択された自治体とアフィニティ関係を有するか決定することで続けられる。プロセスは、新たに選択された自治体で同じステップ（ステップ３００、３１０、３２０、３３０、３４０、３５０、３６０、３７０及び３８０）を実行する。

プロセス２００は、ソースデータベース２０４によりカバーされた領域で表わされる全ての自治体に対してアフィニティドメインが決定されるまで続けられる。選択された自治体に対するアフィニティドメインが他の自治体を包囲せず、即ちアフィニティドメインが他の自治体の重要値の位置を包囲しない場合には、選択された自治体に対してアフィニティを有する他の自治体がない。

自治体が２つ以上の他の自治体のアフィニティドメイン内にあってもよい。このような場合に、自治体は、アフィニティドメインがこれを包囲するところの各々の自治体と個別のアフィニティ関係を有する。

自治体が２つ以上の他の自治体とアフィニティ関係を有するときには、その２つ以上の他の自治体が互いの個別のものでよく、即ちそのいずれも他のものとアフィニティ関係をもたなくてもよい。というのは、そのいずれも他のもののアフィニティドメイン内にないからである。或いは又、自治体が２つ以上の他の自治体とアフィニティ関係を持つときには、その２つ以上の他の自治体は、他のものとアフィニティ関係をもってもよく、即ち一方が他方のアフィニティドメイン内にあってもよい。この後者の状態が図８に示されている。

図８において、都市Ｂは、都市Ａ及び都市Ｈの両方のアフィニティドメイン内にあることが示されている。従って、都市Ｂは、都市Ａ及び都市Ｈの両方とアフィニティ関係をもつと決定される。都市Ｈは、都市Ａのアフィニティドメイン内にある。従って、都市Ｈは、都市Ａとアフィニティ関係をもつと決定される。

図３Ｃを参照すれば、このプロセスは、ソースデータベースによりカバーされた領域で表わされた全ての自治体に対して決定されたアフィニティ関係を含む一時的データファイル３４４を使用してアフィニティ関係インデックス２０２を発生することで続けられる。このアフィニティ関係インデックス２０２は、ソースデータベース２０４によりカバーされた領域内の各自治体に対して決定されたアフィニティドメインにより決定されたアフィニティ関係を含むハイアラーキー構造を備えている。

アフィニティ関係インデックスにおいて、自治体に関連したアフィニティドメイン内に位置する他の全ての自治体は、アフィニティドメインに関連した自治体が他の自治体とのアフィニティ関係有すると予め決定されない限り、その自治体とアフィニティ関係をもつと思われる。換言すれば、２つの自治体が他の各々のアフィニティドメインに位置すると決定された場合に、小さい重要値をもつ自治体は、大きい重要値をもつ自治体とアフィニティ関係をもつと思われ、そしてその逆のことは考えられない。従って、大きい自治体及び小さい自治体が互いに物理的に接近して互いのアフィニティドメイン内にある場合には、小さい自治体は、大きい自治体とアフィニティ関係を有すると思われるが、大きい自治体は、小さい自治体に対してアフィニティをもつと思われない。

上述したように、アフィニティ関係インデックスは、積層ハイアラーキー構造を有する。この構造は、ルート（根）レイヤーに１つ以上のエントリーを含み、次に高いレイヤーに１つ以上のエントリーを含み、等々となる。各レベルのエントリーは、そのエントリーに対してアフィニティを有する自治体により指示される。

図９は、アフィニティ関係インデックスファイル２０２の編成を示す。アフィニティ関係インデックスは、ルートレイヤーを含む。ルートレイヤーは、複数のエントリーを含む。ルートレイヤーのエントリーは、（１）他の自治体のアフィニティドメイン内にない自治体、又は（２）他の自治体のアフィニティドメイン内にあるが、重要値が該他の自治体のアフィニティドメインの値を越えるような自治体を含む。例えば、図７Ａを参照すれば、都市Ｈの重要値は、都市Ａのアフィニティドメインの値を越える。それ故、都市Ａ及び都市Ｈは、両方とも、アフィニティ関係インデックスのルートレイヤー内の位置を占有する。

ルートレイヤー内の各エントリーに関連しているのは、そのエントリーとアフィニティ関係をもつ自治体である。データは、これらの自治体を識別し、そしてそれらがルートレイヤーの自治体とアフィニティ関係をもつことを指示する。

効果：
以上のプロセスは、ルートエントリーが一次コミュニティである一次インデックスで始めてアフィニティにより場所の名前をインデックスするための順序付け方法を提供する。一次コミュニティを見出しとするインデックス内には、上位及び下位レベルのコミュニティの更に別のサブインデックスがある。各レベルは、包含されたコミュニティのサブディレクトリーを表わす。下位レベルのコミュニティは、見掛け上、２つ以上の上位レベルコミュニティのアフィニティであって、それ自身、あるケースではあるレベルにあり、そして他のケースでは他のレベルにあってもよい。インデックスのこの実施形態は、重要な都市の比較的希薄な集合体、例えば、最大の都市圏がルートレベルディレクトリーを占有するのを許す。

アフィニティに基づくインデックスの結果として、この実施形態は、いかなる場所も、「接近(near)」に対してある公式な意味をもつようにして、「接近した」別の場所として記述されるのを許す。換言すれば、場所の名前「Ａ」は、それを「Ｂ」のディレクトリー内で見つけることができれば、接近した場所の名前「Ｂ」であり、そしてこれは、重要値位置が「Ａ」のアフィニティドメイン内に存在する場合に見つかる。更に別の実施形態では、参照が両方向でもよい。

IV．アフィニティ関係インデックスの使用
一実施形態において、アフィニティ関係インデックスは、コンピューティングプラットホームで実行されるナビゲーションアプリケーションにより使用される地理的データベースの一部分である。この実施形態では、アフィニティ関係インデックスは、ユーザがナビゲーションアプリケーションに対して場所（例えば、自治体）を特定するときに使用される。例えば、ユーザは、経路案内を所望する行先として場所を特定することができる。

上述したように、従来のナビゲーションシステム及びアプリケーションは、経路を計算して案内を与えることができる前に、行先の正確な位置を特定するに充分な情報をユーザが与えることを必要とした。ある従来のナビゲーションシステム及びアプリケーションでは、充分な情報は、行先の完全に正確な住所を含むものであった。アフィニティ関係インデックスを含む又は使用する地理的データベースでは、ユーザが場所を別々の仕方で特定することができる。ユーザは、従来のシステムの場合のように、完全に正確なアドレスを使用して場所を特定することもできるし、或いはユーザは、場所をおおよそ特定することもでき、例えば、実際の所望の場所に近い他の場所を指示することで特定することもできる。

図１０は、アフィニティ関係インデックスを使用するためのプロセス５００を示す。このプロセス５００は、ナビゲーションプラットホーム（図２の１２２）におけるナビゲーションアプリケーション（図２の１３２）の１つの一部分でよい。プロセス５００は、行先を特定するのに使用されるものとして説明するが、別の実施形態では、このプロセスは、何らかの目的で場所を特定するのに使用することができる。図１０に示すプロセスは、ユーザに情報を与えると共に、ユーザから入力を受け取ることを要求する。情報は、視覚的、又は聴覚的に、或いは視覚と聴覚の組み合せでユーザに与えることができる。ユーザからの入力は、聴覚的に、又は手動入力により、或いは他の手段により受け取ることができる。

プロセス５００によれば、ユーザには、場所を正確に特定するか又はおおよそ特定するオプションが与えられる（ステップ５１０）。ユーザが場所を正確に特定することを選択した場合には、アプリケーションは、その目的のための適切なメニュー及び／又はプロンプトをユーザに与えるように進む。場所を正確に特定するためのこれらメニュー及び／又はプロンプトは、従来のシステムにより行われていたものと同様でよい。

ユーザが場所をおおよそ特定することを選択した場合には、ユーザには、実際の所望の行先に近い場所（例えば、自治体）の識別を要求するプロンプトが与えられる（ステップ５２０）。ユーザの入力が得られ、そしてアフィニティ関係インデックス２０２のサーチに使用される。アフィニティ関係インデックス２０２をサーチするときには、ルートレベルのエントリーからスタートしてエントリーをサーチすることができる（ステップ５３０）。他のレベルをサーチすることもできる。ユーザにより指示された場所に対してアフィニティ関係インデックスがサーチされた後に、３つの考えられる結果が生じ、即ち、一致が生じないか、厳密に１つの一致が生じるか、又は２つ以上の一致が生じるかである（ステップ５４０）。一致が生じない場合には、ユーザに、指示された場所が見つからなかったという情報が与えられ、所望の行先の付近の場所の名前に対して再び促され、そしてアフィニティ関係インデックスが再びサーチされる（ステップ５５０及び５３０）。２つ以上の一致がある場合には、ユーザにより指示された名前をもつ自治体が２つ以上あることを意味する。この場合に、アフィニティ関係インデックスは、ユーザにより指示された名前をもつ場所の近くにある他の場所に関する付加的な情報を得るのに使用される（ステップ５６０）。例えば、アフィニティ関係インデックスは、同じ名前をもつ多数の場所の各々がアフィニティをもつ場所のうち、どれがより高いレベルかを識別するのに使用できる。次いで、この情報をユーザに与え、ユーザは、適当な場所を選択することができる（ステップ５７０及び５７４）。例えば、ユーザが「都市Ｙ」を指示し、そしてアフィニティ関係インデックスが、名前が「都市Ｙ」で都市Ｘとアフィニティ関係をもつ１つの都市と、名前が「都市Ｙ」で都市Ｚとアフィニティ関係をもつ別の都市とがあることを示す場合には、名前が「都市Ｙ」で都市Ｘ及び都市Ｚに近い都市があることを指示する情報がユーザに与えられる。ユーザには、これらの１つを選択するプロンプトが与えられる。

プロセスが、所望の行先に近い１つの場所を厳密に決定すると、その場所へのルートが計算される（ステップ５８０）。この機能は、経路（ルート）計算アプリケーション（図２の１３６）により実行される。ルートを計算するときには、ルート計算は、行先として指示された近傍の場所のポイントを使用する。例えば、近傍の場所に関連した重要値の位置（即ち、その場所の管理境界の中心）を使用することができる。ユーザの位置が得られる（ステップ５９０）。これは、もし利用できれば、ポジショニングシステム（図２の１３４）から得ることができる。或いは又、ユーザは、現在位置を指示するように促されてもよい。ユーザには、計算された経路（ルート）をたどるための案内が与えられる（ステップ６００）。

ユーザが、計算された経路をたどり続けるときに、ユーザの新たな現在位置が決定され、そしてその計算された経路をたどるために適切な案内がユーザに与えられる（再びステップ５９０及び６００）。ユーザが行先の閾値（スレッシュホールド）内を走行すると、所望の行先を正確に特定するか又は所望の行先の近くの場所を指示することで特定するオプションがユーザに再び与えられる（ステップ６１０及び５１０）。閾値（スレッシュホールド）距離は、計算経路のスタートポイントから指示された場所の行先までの全距離のパーセンテージとして決定されてもよい。或いは又、閾値（スレッシュホールド）は、走行時間に基づいて決定されてもよい。プロセスは、ユーザが所望の行先として正確な位置を特定するまで続けられる。

アフィニティ関係インデックスを使用するプロセスは、ユーザが経路に乗り出すときに正確なアドレスを特定しなくてよいという効果を発揮する。むしろ、ユーザは、実際の所望の行先の近くの場所を特定することができる。これは、ユーザが正確な全住所を行先として特定することが要求される場合よりも迅速に経路を計算して案内を与えるのを許す。

多くの場合、特に、実際の所望の行先が経路のスタートポイントから比較的遠い場合には、指示された近傍の場所への経路の最初の部分が、実際の所望の行先へのルートと同じになる。

前記プロセスにおいて、所望の行先の正確な住所を特定するようにユーザを促すためのスレッシュホールドが使用される。上述したように、このスレッシュホールドは、経路に沿って行先へ至る距離の割合でよい。或いは又、固定の距離又は別の距離を使用してもよい。又、スレッシュホールドは、走行時間に基づくものでもよい。上述したように、実際の所望の行先付近にある指示された場所への経路をたどるための案内がユーザに与えられる。多くの場合に、指示された場所への経路は、最初、実際の所望の行先への経路と同じである。しかしながら、指示された近傍の場所への経路に沿ったあるポイントにおいて、実際の所望の行先への経路がそれる。スレッシュホールドは、ユーザが実際の所望の行先の正確な住所を適時に与えることができるように決定される。

Ｖ．別の実施形態及び効果
上述したように、アフィニティ関係インデックスは、ナビゲーションシステムのようなシステムを使用するときに場所の特定を容易にする。アフィニティ関係システムは、手動或いはスピーチ又はボイスコマンドの使用によりユーザ入力を受け容れるシステムと共に使用することができる。スピーチ又はボイスコマンドと共に使用するときには、アフィニティ関係インデックスをインタラクティブに使用して、実際の所望の行先の付近の場所（自治体）を選択して、経路案内を迅速に受け取り、従って、ユーザが行先の正確な全住所をシステムに対して特定せずに行先に向かって乗り出すことができる。従来の方法は、一般に、その性質がアルファベット順であるか、さもなければ、ユーザが正確な行先を選択するために多数の特定レベルを横断するように強制する。アフィニティ関係インデックスは、行先をインタラクティブに特定するための比較的高速な、より直観的な仕方を与える。スピーチ認識システムと共にアフィニティ関係インデックスを使用する別の効果は、サーチする必要のある異なる都市名の数を減少し、これにより、スピーチ認識システムが正しい一致をなし得る確率を改善することである。

前記実施形態において、アフィニティ関係インデックスは、自治体の名前を、それらに接近し且つ相対的により重要な他の自治体と関連付けるのに使用された。アフィニティ関係インデックスの別の実施形態は、関心のあるポイントのような他の種類の場所に使用することができる。アフィニティ関係インデックスが他の種類の場所に使用される場合には、このような種類の場所の重要性を反映するファクタ及び／又はパラメータを含むように重要値アルゴリズムが変更される。アフィニティ関係インデックスの更に別の実施形態は、自治体を、関心のあるポイント、国立公園等の他の種類の場所に結合することができる。自治体を他の種類の場所に結合するアフィニティ関係インデックスが使用される場合には、このような種類の場所の相対的な重要値が自治体の重要値と一貫したものとなるようにファクタ及び／又はパラメータを含むよう重要値アルゴリズムが変更される。

アフィニティ関係インデックスは、ユーザが行先を取り巻く地理的エリアに馴染みがないか、又は行先に関する完全な情報をもたず、大都市や全国的／地域的に重要な関心ポイントのような近傍の重要位置の知識をある程度もつだけである状況に特に有用である。

アフィニティ関係インデックスは、全ての通常のサーチ方法を使用してサーチを行えるようにする。更に、アフィニティ関係インデックスは、ユーザが、大都市のみの参照を使用することにより行先選択プロセスを開始し、次いで、その特定を後で洗練することができるようにする。

場所を正確に特定するか又はおおよそ特定するオプションがユーザに与えられることは前記で述べた。このオプションは、ユーザに明確に与えられてもよいし、暗示的に与えられてもよい。例えば、ユーザには、行先住所を正確に特定するか又は行先をおおよそ特定するための別々のメニュー選択が与えられてもよい。或いは又、ユーザの入力を使用して、正確な行先住所が特定されるか、おおよその行先位置が特定されるか決定してもよい。例えば、ユーザがワード「ｏｎ」又は「ａｔ」を使用する場合には、プロセスは、ユーザが行先を正確に特定すると推論する。しかしながら、ユーザがワード「ｎｅａｒ」を使用する場合には、プロセスは、ユーザがおおよその行先を特定すると推論し、それ故、アフィニティ関係インデックスを使用して、行先に向かって経路に最初に乗り出す場所を決定する。

アフィニティ関係インデックスと、これを使用する関連プログラムは、あいまいな即ち不完全な行先入力を、重要性が次第に高くなるか又は低くなる位置と位置との間のアフィニティの自然特性を使用して、益々の洗練さでサポートする。

アフィニティ関係インデックスと、これを使用する関連プログラムは、空間的アフィニティ、即ち物理的な接近性しか一般的に使用しない従来のシステムに勝る効果を発揮する。アフィニティ関係インデックスの実施形態は、物理的な接近性を、重要性のハイアラーキー環境における成分として含む。付加的な実施形態は、政治的関係、空間的幾何学形状、及び歴史的重要性ファクタを含むハイアラーキーをサポートすることができる。

以上の詳細な説明は、本発明を例示するもので、限定するものではなく、又、あらゆる等効物を含む特許請求の範囲が本発明の範囲を規定することを理解されたい。

種々のコンピューティングプラットホームに使用するための地理的データベース製品を形成しそして配送するプロセスを示す図である。 地理的データベース製品を使用する図１のシステムの１つを示すブロック図である。 アフィニティ関係インデックスを形成するプロセスを示すフローチャートである。 アフィニティ関係インデックスを形成するプロセスを示すフローチャートである。 アフィニティ関係インデックスを形成するプロセスを示すフローチャートである。 図３Ａ、３Ｂ及び３Ｃのプロセスにより計算されたアフィニティドメインを示す図である。 図４のアフィニティドメインの別の図で、そこに示された他の自治体に対する重要値を付加した図である。 図３Ａ、３Ｂ及び３Ｃのプロセスにより形成されたアフィニティ関係データを含む一時的ファイルの編成を示すブロック図である。 都市に対する重要値と、図５に示すアフィニティドメインとの間の関係を示す図である。 別の都市に対する重要値と、図５に示すアフィニティドメインとの間の関係を示す別の図である。 自治体間のアフィニティ関係を示す図である。 図３Ａ、３Ｂ及び３Ｃのプロセスにより形成されたアフィニティ関係インデックスファイルデータのコンポーネントを示すブロック図である。 図９のアフィニティ関係インデックスファイルを使用するアプリケーションにより実行されるプロセスのフローチャートである。

符号の説明

１００：地理的データベース
１０１：地理的データベースデベロッパー
１０２：データ
１１０：コンパイルされたデータベース製品
１１８：データ集合体
１２０：インデックス
１２２：コンピューティングプラットホーム
１３２：ナビゲーションアプリケーション
１３４：ポジショニングシステム
１３６：経路（ルート）計算アプリケーション
１４０：経路（ルート）案内アプリケーション
１４４：地図表示アプリケーション
１４８：ポジショニングアプリケーション
１５２：行先選択アプリケーション
１６４：データ記憶媒体
２０２：アフィニティ関係インデックス
２０４：ソースデータベース

Claims (20)

1. 自治体のインデックスを編成する方法であって、
   第１の自治体集合を含むデータ構造体をハイアラーキー式で積層されるよう形成するステップと、
   前記第１の自治体集合内の各自治体に対し、１つ以上の他の自治体を、前記第１の自治体集合内の自治体と密接な関係(アフィニティ：affinity関係)を有するものとして指示するステップと、
   を含み、自治体は、それが前記第１の自治体集合内の自治体のアフィニティドメイン内にある場合に、前記第１の自治体集合内の自治体と密接な関係（アフィニティ関係）をもつよう決定されることを特徴とする方法。
2. 前記自治体のアフィニティドメインは、前記自治体からの距離関数として減少する値の集合を定義する、請求項１に記載の方法。
3. 前記自治体のアフィニティドメインは、前記自治体の管理境界によって形成された多角形の中心からの距離関数として減少する値の集合を定義する、請求項１に記載の方法。
4. 前記自治体のアフィニティドメインは、前記自治体に対して決定された重要値に関連した位置からの距離関数として減少する値の集合を定義する、請求項１に記載の方法。
5. 前記自治体の重要値は、次の式により決定され、
   Ｉ＝ＡＰ^αｘＢＮ^βｘＣＫ^γｘＤＲ^δ
   但し、Ｐは、自治体の管理境界に対応する多角形内の人口であり、Ｎは、多角形内の道路交差点の数であり、Ｋは、多角形内に含まれる道路のキロメーター数であり、そしてＲは、多角形の境界が道路を横断する数である、請求項４に記載の方法。
6. 前記Ａ、Ｂ、Ｃ、Ｄ及びα、β、γ、δは、重要インデックスＩの値を調整するのに使用されるチューニング(tuning)変数である、請求項５に記載の方法。
7. 前記自治体のアフィニティドメインは、自治からの距離関数として指数関数的に減少する値の集合を定義する、請求項１に記載の方法。
8. 前記インデックスは地理的データベースの一部分である、請求項１に記載の方法。
9. 前記インデックスは行先を見つけるのに使用される、請求項１に記載の方法。
10. 前記インデックスはナビゲーションシステムの一部分である、請求項１に記載の方法。
11. コンピューティングシステムで行先への案内を与える方法であって、
    所望する実際の行先の近傍にある自治体を指示するユーザ入力を受け取るステップと、
    前記所望する実際の行先の近傍にある自治体に対する第１ルートを計算するステップと、
    前記所望する実際の行先の近傍にある自治体に対する第１ルートをたどるようにユーザに案内を与えるステップと、
    前記所望する実際の行先の近傍にある自治体に対するルート上で、前記所望する実際の行先の正確な位置を指示するユーザ入力を受け取るステップと、
    前記所望する実際の行先に対する第２ルートを計算するステップと、
    前記所望する実際の行先に対する前記第２ルートをたどるようにユーザに案内を与えるステップと、を備えた方法。
12. 前記所望する実際の行先の近傍にある自治体に対する前記第１ルートを計算する前に、他の自治体の重要度に基づいて自治体を他の自治体に関連付けるアフィニティ関係インデックスを使用するステップを更に備えた、請求項１１に記載の方法。
13. 前記第１ルートは、前記所望する実際の行先の近傍にある自治体に関連する位置を行先とする、請求項１１に記載の方法。
14. 前記第１ルートは、前記所望する実際の行先の近傍にある自治体の管理境界に対応する多角形の中心を行先とする、請求項１１に記載の方法。
15. 前記所望する実際の行先付近の自治体を指示するユーザ入力を受け取る前に、前記所望する行先を正確に特定するか又は近傍の自治体を指示することで特定するオプションをユーザに与えるステップを更に備えた、請求項１１に記載の方法。
16. 前記所望する実際の行先の近傍にある自治体に対するルート上で、且つ前記所望する実際の行先の正確な位置を指示するユーザ入力を受け取る前に、前記所望する実際の行先の正確な位置を指示するようにユーザに要求するステップを更に備えた、請求項１１に記載の方法。
17. 前記所望する実際の行先の正確な位置を指示するようにユーザに要求する前記ステップは、ユーザが前記ルートに沿った所定の閾値(threshold)に到達したときに行う、請求項１６に記載の方法。
18. 前記所望する実際の行先の近傍にある自治体に対する前記ルート上で、且つ前記所望する実際の行先の正確な位置を指示するユーザからの入力を受け取る前に、前記所望する実際の行先の正確な位置を指示する、又は所望する実際の行先の近傍にある別の自治体を指示するオプションをユーザに与えるステップを更に備えた、請求項１１に記載の方法。
19. システムで行先を特定する方法であって、
    所望する実際の行先が近くにある自治体を指示するステップと、
    前記自治体へ走行するための案内を受け取るステップと、
    前記自治体へのルートにある間に、前記実際の所望の行先の正確な住所を指示するステップと、
    前記所望する実際の行先に対する前記正確な住所へ走行するための案内を受け取るステップと、を備えた方法。
20. 前記所望する実際の行先が近くにある自治体を指示する前に、行先を正確に選択するか、又は近傍の自治体を選択するオプションを受け取るステップを更に備えた、請求項１９に記載の方法。

Images