分散型計算アーキテクチャによるナビゲーション・システム
【課題】エンドユーザのコンピュータに地理データを提供する。
【解決手段】サーバは、ダウンロード可能な地理データを管理し、該データは、該サーバによるサービス地域全体を分割する所定の副区分に対応している予め計算されたデータの集合に系統化される。サーバは、選択された地理データの予め計算されたデータの集合をエンドユーザのコンピュータに送信することで、該エンドユーザのコンピュータからのナビゲーション・サービスとデータの要求に応答する。エンドユーザのコンピュータは、サーバから受信した予め計算されたデータの集合をキャッシュ・メモリに保存する。エンドユーザのコンピュータは、予め計算されたデータの集合の中のデータを使用して、ナビゲーション関連の特徴を局所的に提供する。
【解決手段】サーバは、ダウンロード可能な地理データを管理し、該データは、該サーバによるサービス地域全体を分割する所定の副区分に対応している予め計算されたデータの集合に系統化される。サーバは、選択された地理データの予め計算されたデータの集合をエンドユーザのコンピュータに送信することで、該エンドユーザのコンピュータからのナビゲーション・サービスとデータの要求に応答する。エンドユーザのコンピュータは、サーバから受信した予め計算されたデータの集合をキャッシュ・メモリに保存する。エンドユーザのコンピュータは、予め計算されたデータの集合の中のデータを使用して、ナビゲーション関連の特徴を局所的に提供する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、地域にわたるエンドユーザに、ナビゲーション関連のサービスとデータを提供するシステムに関し、より詳細には、本発明は、中央に設置されたサーバを含み、該サーバは、それに関連した地理データベースを有し、サービス地域にわたって配置されたエンドユーザのコンピュータに、ナビゲーション関連のサービスとデータを提供するようになったシステムに関する。
【背景技術】
【0002】
ナビゲーション・システムは、所望の目的地までの経路を計算し、計算した経路に従って指針を与え、地図を表示すること等のような種々の有用な特徴を提供する。ナビゲーション関連及び地図関連の特徴を配信するナビゲーション・システムのための様々なコンピュータ・アーキテクチャがある。ナビゲーション・システムのためのアーキテクチャの形式の1つは、エンドユーザ(乗物の運転者等)が有するローカル・ナビゲーション・システム装置である。これらのエンドユーザのローカル・ナビゲーション・システム装置は、遠隔配置された地理データベースから地理データを入手する。遠隔配置された地理データベースは、比較的大量の地理データを所有している。遠隔配置された地理データベースに関連するサーバは、エンドユーザのローカル・ナビゲーション・システム装置からのナビゲーション関連又は地図関連データに対する要求を処理する。エンドユーザのローカル・ナビゲーション・システム装置がデータを要求すると、サーバがそれに関連した地理データベースにアクセスして、要求に応えるのに必要なデータを入手し、次いでこのデータを、要求しているエンドユーザのローカル・ナビゲーション・システム装置に送信する。
【0003】
この種のナビゲーション・システム・アーキテクチャは、幾つかの利点を与える。利点の1つは、更新された地理データを提供することに関連する。ナビゲーション・システムで使用する地理データは、継続的に更新される必要がある。例えば、新しい道ができたり、道路工事で道が閉鎖されたり、迂回路が設けられたり、新しい店舗が開店したり、標示されている速度制限が変更されたり、交差点に新しい転回制限が設けられたり、通りの名前が変更されること等がある。この種の変化は、地域を通る移動に影響を及ぼすことがある。したがって、ナビゲーション・システムで使用する地理データは、表示される地理的特徴の変化を正確に反映するために、定期的に更新されるべきである。個々のローカル・ナビゲーション・システム装置が単一の地理データベースから地理データを入手するコンピュータ・アーキテクチャは、地理データを更新することに関する利点を与える。個々のローカル・ナビゲーション・システム装置が、中央サーバに関連した単一の地理データベースからデータを入手するコンピュータ・アーキテクチャでは、更新の必要性は中央データベースにのみ生じる。
【0004】
個々のローカル・ナビゲーション・システム装置が、中央サーバに関連した単一の地理データベースからデータを入手するようになったナビゲーション・システム・アーキテクチャでは、それに関連した利点があるが、さらに考慮すべき事項がある。考慮事項の1つは、エンドユーザが使用する種々の異なるコンピュータ・プラットフォームに、データを提供することに関連する。中央サーバは、様々な異なる種類のエンドユーザ・コンピュータ・プラットフォームに対応していることが好ましい。これらの異なるエンドユーザ・コンピュータ・プラットフォームは、異なる容量のメモリ、異なる処理速度、異なるオペレーティングシステムその他のような異なるリソースを有することがある。これらの異なる種類のエンドユーザ・コンピュータ・プラットフォームの幾つかは、ナビゲーション・アプリケーションを実行する多目的計算装置を含むことがある。他のエンドユーザ・コンピュータ・プラットフォームは、車載ナビゲーション・システムのような専用装置を含むことがある。これらの異なるエンドユーザ・コンピュータ・プラットフォームの幾つかは、音声情報と可視情報の両方をエンドユーザに提供することができるが、他のエンドユーザ・コンピュータ・プラットフォームは、音声のみ又は映像のみを提供する。コンピュータ・プラットフォームの各々が、該プラットフォームのリソースに適した地理データを受信することが好ましい。これは、コンピュータの利用可能なリソースを有意義な方法で利用するために十分なデータを送信するが、該プラットフォームで使用できないデータは送信しないようにすることを含む。
【発明の開示】
【発明が解決しようとする課題】
【0005】
したがって、サーバが、異なる種類のエンドユーザ・コンピュータに対応するために、ナビゲーション関連のサービス及びデータを提供できるようにする、という改良の必要性がある。
【0006】
さらに、データが中央サーバからエンドユーザ・コンピュータに送信されるナビゲーション・システム・アーキテクチャにおいて、データが、サーバとエンドユーザ・コンピュータの両方で効果的に管理されるようにする、という改良の必要性がある。
【課題を解決するための手段】
【0007】
これらの及び他の目的に応えるために、本発明は、ナビゲーション関連のサービスをエンドユーザのコンピュータに提供するためのシステム及び方法からなる。サーバは、ダウンロード可能な地理データを管理し、該データは、該サーバによるサービス地域全体を分割する所定の副区分に対応している予め計算されたデータの集合に系統化される。サーバは、予め計算され選択された地理データのデータの集合をエンドユーザのコンピュータに送信することで、ナビゲーション・サービスとデータに対する要求に応える。エンドユーザのコンピュータの各々は、サーバから受信したデータの集合を、メモリ・キャッシュに保存する。エンドユーザのコンピュータは、データの集合の中のデータを使用して、ナビゲーション関連の特徴を局所的に提供する。
【発明を実施するための最良の形態】
【0008】
I.分散型ナビゲーション・システムの概要
図1は、地域100を示す。地域100は、大都市地域又は農村地域、州、国又はこれらの組み合わせ、或いは他の類似の規模の地域のいずれかに対応させることができる。この地域100には、道路網104がある。
【0009】
ナビゲーション・システム110が、この地域100内のエンドユーザ(例えば、乗り物の運転者及び乗客並びにその他の者)にサービスを提供する。このナビゲーション・システム110は、地域100についてのナビゲーション関連のサービスと地図関連のサービスを得るために、エンドユーザによって使用される。ナビゲーション関連のサービスと地図関連のサービスは、経路計算及び案内、個人及び企業検索サービス(例えばエレクトロニック・イエロー及びホワイトページズ)、地図、関心のある地点の検索、目的地選択その他を含む道路網104沿いの移動に関する情報を含む。
【0010】
ナビゲーション・システム110は、ハードウェアとソフトウェアとデータとの組み合わせである。ナビゲーション・システム110は、遠隔コンポーネント(例えば、エンドユーザから離れた中心位置にあるハードウェア、ソフトウェア又はデータ)と局所的コンポーネント(例えば、物理的に各エンドユーザと共に位置するハードウェア、ソフトウェア又はデータ)を含む。
【0011】
ナビゲーション・システム110の遠隔コンポーネントの中には、ナビゲーション・サービス・サーバ120が含まれる。ナビゲーション・サービス・サーバ120に関連するのは、作業地理データベース122と、ダウンロード可能な地理データ記憶装置(すなわち保存庫)124である。ナビゲーション・サービス・サーバ120と、作業地理データベース122と、ダウンロード可能な地理データ記憶装置124は、ナビゲーション・サービス・プロバイダ128により管理され、動作される。
【0012】
ナビゲーション・システム110の局所的コンポーネントには、エンドユーザにより、ナビゲーション関連及び地図関連の特徴と地理データをナビゲーション・サービス・プロバイダ128に要求して入手するように作動される、様々なコンピュータ・プラットフォーム130が含まれる。これらの様々なコンピュータ・プラットフォーム130(「エンドユーザ・コンピュータ」又は「顧客のコンピュータ」とも呼ばれる)は、データ・ネットワーク170を介してナビゲーション・サービス・プロバイダ128にアクセスするのに適したハードウェアとソフトウェアを有し、乗物134、パーソナルコンピュータ140、個人用整理手帳(例えばPDA、PalmPilot(登録商標)型の装置)150、携帯電話160、又は他の種類の計算装置に搭載されたナビゲーション・システム装置132を含むことができる。
【0013】
データ・ネットワーク170は、現在利用可能な適当な技術及び/又はプロトコル、並びに将来利用可能となる技術及び/又はプロトコルのいずれをも使用することができる。例えば、データ・ネットワークは、WAP、TCP/IPその他を使用することができる。データ・ネットワーク170には、適当な変換により、1つより多いプロトコルを使用することができる。
【0014】
データ・ネットワーク170は、インターネットの一部とすることもできるし、インターネットに接続できるようにすることもできる。
【0015】
ネットワーク170は、無線部分172を含むことができる。データ・ネットワーク170の無線部分172は、エンドユーザのモバイル・コンピュータ130とサービスプロバイダ128との間で双方向通信できるようにする。無線部分172は、セルラー方式、PCS、衛星、FM、無線、又は将来開発されることとなる技術の適当な形式で実行することができる。無線部分172は、トランスポンダ塔、アンテナ塔、FM塔、衛星その他適当な手段のような1つ又はそれ以上の送波器174を含むことができる。送波器174は、ネットワーク170及び/又はサービスプロバイダ128との適当な通信リンク176を有する。このリンク176は、地上回線とすることもできるし、無線とすることもできる。送波器174は、サービスプロバイダ128とエンドユーザのモバイル・コンピュータ130との間で双方向通信できるようにする適当な技術を含む。
【0016】
図1のナビゲーション・システム110における特徴の1つは、異なる形式のエンドユーザ・コンピュータ130に対応しているということである。図1のナビゲーション・システム110は、異なる形式のコンピュータ130を有するエンドユーザが、ナビゲーション・サービス・プロバイダ128からナビゲーション・サービスを受け、該ナビゲーション・サービス・プロバイダ128から地理データを入手して使用することができるようにする。
【0017】
II.ナビゲーション・サービス・サーバ
A.概要
図2は、ナビゲーション・サービス・プロバイダ128のコンポーネントの幾つかを示すブロック図である。ナビゲーション・サービス・プロバイダ128のナビゲーション・サービス・サーバ120には、サーバ・アプリケーション200が含まれる。サーバ・アプリケーション200の1つは、加入者用サービス・アプリケーション204である。ナビゲーション・サービス・プロバイダ128により提供される他のサービスの幾つか又は全てを使用するためには、エンドユーザが加入者になることが必要とされる。加入者用サービス・アプリケーション204は、この機能に対応するサービスを提供する。加入者用サービスの幾つかは、登録、支払い、更新、加入者身分確認、対象広告その他を含む。加入者用サービス・アプリケーション204は、様々な加入者に関する様々な種類の情報を保有している加入者データベース208を管理し、使用する。
【0018】
サーバ・アプリケーション200のその他には、通信用アプリケーション212がある。通信用アプリケーション212は、エンドユーザとメッセージを送受信するために、データ・ネットワーク(図1の170)とインターフェースしている。通信用アプリケーション212はまた、エンドユーザとの通信セッションを維持管理する。
【0019】
サーバ・アプリケーション200には、ナビゲーション関連アプリケーション216が含まれる。ナビゲーション関連アプリケーション216は、様々な異なる種類のナビゲーション関連のサービスを提供するために、ナビゲーション・サービス・サーバ120に関連する作業地理データベース122を使用する。ナビゲーション関連アプリケーション216の1つは、経路計算アプリケーション220である。出発地と目的地の位置を特定するデータが与えられると、経路計算アプリケーション220は、出発地と目的地との間の経路を計算する。経路計算アプリケーション220は、この目的に合う様々な手段又はアルゴリズムのいずれをも使用することができる。経路を計算する方法は、米国特許第6,192,314号に開示されており、その開示全体を引用によりここに組み入れる。例えば、経路の計算方法は、A*アルゴリズムか又はディクストラ・アルゴリズムのいずれかを含むことができる。(上述の特許に開示されている方法には、経路を計算することができる方法のうちの幾つかのみしか記載されていないが、ここで特許請求される内容は、特定の経路計算方法のいずれにも限定されるものではない。既知の又は将来開発されることとなる好適な経路計算方法のいずれも使用することができる。)
【0020】
使用する方法に関係なく、経路計算アプリケーション220は、出発地と目的地との間の合法的解答経路を形成する連続する一続きの道(又はこれらの区分)を特定する、リストの形態の出力を与える。「合法的解答経路」は、一方通行路、転回制限その他のような確認されている交通規制に従う。経路計算アプリケーション220で用いられる方法は、解答経路が1つ又はそれ以上の所定の基準を満たすよう最適化されるように設計することができる。このような基準は、最短移動時間、最短距離、最少回数の転回その他を含むことができる。経路計算アプリケーション220で用いられる方法が、1つ又はそれ以上の基準のために最適化された解答経路を見つけるように設計される場合には、解答経路も、理想的にはこれらの1つ又はそれ以上の基準を満たす。
【0021】
ナビゲーション関連アプリケーション216のその他には、企業及び個人検索アプリケーション224がある。企業及び個人検索アプリケーション224は、イエロー及びホワイトページ形式の機能を含む。企業及び個人検索アプリケーション224は、特定の企業又は個人の位置或いは住所を見つけるか、或いは特定の企業又は個人についての他の情報を見つける。企業及び個人検索アプリケーション224はまた、種々の基準に基づいて、企業又は個人のカテゴリの位置又は住所を検索することも提供する。例えば、企業及び個人検索アプリケーション224は、特定の位置(例えばエンドユーザの位置)から特定の距離内(例えば5マイル)の、特定のエスニック風(例えば中華)又はチェーン店(例えばマクドナルド)の飲食店の全てを検索することを提供する。企業及び個人検索アプリケーション224は、エンドユーザが、目的地として使用可能な関心のある企業、個人又は地点を見つけるのを支援することができ、次いで、経路計算アプリケーション220が、そこまでの解答経路を求めることができる。
【0022】
ナビゲーション関連の特徴を提供するために、経路計算アプリケーション220と検索アプリケーション224は、作業地理データベース122からのデータを使用する。作業地理データベース122は、地域(図1の100)の道路と交差点を表すデータを含み、さらに、交差点での転回制限、道路沿いの速度制限、様々な道路の通りの名前、道路沿いの住所範囲その他のような表された道路と交差点に関する情報も含んでいる。作業地理データベース122はまた、関心のある地点と企業についての情報とその他の情報も保有している。作業地理データベース122は、ナビゲーション関連機能の実行を容易にするために系統化することができる。ある種のナビゲーション関連機能の性能を向上させるため地理データベースを系統化する方法は、米国特許第5,974,419号と、米国特許第5,968,109号と、米国特許第5,953,722号に記載されており、その開示全体を引用によりここに組み入れる。
【0023】
ナビゲーション・サービス・サーバ120におけるナビゲーション関連アプリケーション216のその他は、地理データ提供アプリケーション228である。
地理データ提供アプリケーション228は、地理データをエンドユーザのコンピュータ130にダウンロードするのを管理する。ナビゲーション・システム(図1の110)の一実施形態によれば、ある種のナビゲーション関連機能は、ナビゲーション・サービス・サーバ120上で遠隔的にエンドユーザに向けて実行され、他のナビゲーション関連機能は、エンドユーザ・コンピュータ130上で局所的にエンドユーザに向けて実行される。例えば、一実施形態によれば、経路計算は、最新の交通情報を利用するために、ナビゲーション・サービス・サーバ120上で実行される。経路案内は、各エンドユーザが好む方法で情報を与え、各エンドユーザのコンピュータ130の各々のリソースに対応させるために、各エンドユーザのコンピュータ130上で局所的に実行される。
【0024】
エンドユーザのコンピュータ上のナビゲーション・アプリケーションは、該エンドユーザのコンピュータ上で局所的にある種のナビゲーション関連機能を実行するために、地理データを要求することができる。この実施形態において、エンドユーザのコンピュータの各々は、ある種のナビゲーション関連機能を局所的に実行するのに必要な地理データを、ナビゲーション・サービス・サーバ120から入手する。ナビゲーション・サービス・サーバ120がエンドユーザのコンピュータ130に送信するデータは、ダウンロード可能な地理データ記憶装置124から入手される。ナビゲーション・サーバ120の地理データ提供アプリケーション228は、ダウンロード可能な地理データ記憶装置124からエンドユーザのコンピュータ130までの、地理データの供給を管理する。
【0025】
地理データ提供アプリケーション228は、幾つかの機能を実行する。地理データ提供アプリケーション228が実行する機能の1つは、ダウンロード可能な地理データ記憶装置124からエンドユーザのコンピュータに送信するのに適したデータを決定することである。この決定は、幾つかの要素を考慮に入れることができる。一実施形態によれば、エンドユーザのコンピュータは、地理データのコレクションを特定する。
ナビゲーション・サービス・プロバイダ128は、ダウンロード可能な地理データ記憶装置124の中で、地理データの異なるコレクション232を保管することができる。個々のコレクション232の各々は、全地域(図1の100)の個々の表示である。これらの異なるコレクション232の構成は、後でより詳細に説明する。地理データのコレクション232からどのデータを送信するかが決定されると、地理データ提供アプリケーション228が、後でより詳細に説明するように、コレクション232から特定のデータ部分を選択し、選択されたデータ部分をエンドユーザのコンピュータに送信する。
【0026】
別の実施形態によれば、地理データ提供アプリケーション228は、加入者データベース208を参照することで、特定のエンドユーザに送信するデータを選択するのに適した地理データのコレクション232を決定することができる。加入者データベース208は、各エンドユーザに送信するデータが選択される地理データのコレクションを識別する情報を、管理することができる。さらに別の実施形態によれば、地理データ提供アプリケーション228は、その他の手段により特定のエンドユーザに送信するデータを選択するのに適した地理データのコレクションを決定することができる。
【0027】
ダウンロード可能な地理データ記憶装置124から、エンドユーザのコンピュータに送信する地理データが選択されるコレクション232を決定した後に、送信する地理データの特定部分が選択される。この機能を実行するために、地理データ提供アプリケーション228は、(1)エンドユーザのコンピュータの位置と、(2)エンドユーザのプラットフォームがどこへ行くのかということと、(3)他の要素と、を考慮に入れる。エンドユーザが、経路計算アプリケーション220により計算された経路に追従する場合には、地理データ提供アプリケーション228が、この経路沿いの区域を表すデータを選択する。経路沿いの区域は、「進路要図」と呼ぶことができる。進路要図の尺度は、地理データ提供アプリケーション228によって決定される。この決定は、エンドユーザによる進路要図の尺度の指定を考慮に入れることができる。或いは、地理データ提供アプリケーション228が、エンドユーザの好みやコンピュータ・プラットフォームのリソースに関する保存された情報に基づいて、適した進路要図の尺度を決定することができる。この保存された情報は、加入者データベース208で管理される。
【0028】
B.ダウンロード可能な地理データ
上述のように、地理データ提供アプリケーション228は、どのデータをエンドユーザのコンピュータ130に送信するかを決定する。地理データ提供アプリケーション228がエンドユーザのコンピュータに送信するデータは、ナビゲーション・サービス・サーバ120で管理されるダウンロード可能な地理データ記憶装置124から入手する。ナビゲーション・サービス・サーバ120からエンドユーザのコンピュータ130にデータをダウンロードするのを容易にするために、該データは、1つ又はそれ以上の所定のコレクション232に系統化される。さらに、ダウンロード可能な地理データ記憶装置124の中のデータのコレクション232の各々は、複数のグループ分け(すなわち「データの集合」)に系統化される。一実施形態において、各データの集合に格納されるデータは、空間的に決定されるものであり、すなわち、地理的特徴を表す各データの集合の中のデータは、互いに近接するものである。より具体的には、各データの集合に格納されるデータは、表された全地域(図1の100)を分割する複数の別個の地理的区分のうちの別個の区別されるものが所有している地理的特徴を表す。
【0029】
上述のように、この実施形態によれば、ダウンロード可能な地理データ記憶装置124は、種々の異なるコレクション232を含む。これらのコレクション232の各々は、全地域100の別個の表示からなる。これらのコレクション232の各々は、複数のデータの集合に系統化される。
【0030】
図3及び図4は、ダウンロード可能な地理データ記憶装置124のコレクション232の各々に格納されるデータが、一実施形態によってどのように系統化されるのかを示している。図3は、図1に既に示されている地域100の地図300を示す。図3では、地域100を表す地図300にグリッド304が重ね合わされている。グリッド304は、グリッド線308で構成されている。グリッド線308は、表された地域100を複数の区域312に分割する。この実施形態において、区域312は長方形であるが、しかしながら、別の実施形態において区域312を別の形状にすることもできる。グリッド304のグリッド線308は、区域312の境界を表す。これらの区域312は、図3に示すように異なる大きさにすることができる。或いは、区域312は、全て同じ大きさにすることもできる。区域312の大きさ、及び、該区域312の大きさが全て同じかどうかということは、これらの地理的区分に含まれている地理的特徴を表すデータをデータの集合に系統化するのに用いる手順により定まる。同様に、区域312の境界の位置は、これらの地理的区分に含まれている地理的特徴を表すデータをデータの集合に系統化するのに用いる手順により定まる。データの集合を生成するため区域の境界を決定する方法は、米国特許第5,974,419号に記載されており、その開示全体を引用によりここに組み入れる。
【0031】
各データの集合312の生成において、別個の区域312の各々に含まれている地理的特徴を表す個々のデータ・レコード336は、データの別個のデータの集合320(又はグループ分け)に一緒に集められる。すなわち、(各コレクション232の)データのデータの集合320の各々は、対応する地理的区分312に含まれている地理的特徴を表す全てのデータ・レコード336を含んでいる。したがって、(コレクション232の全てのデータの集合320に対応している)全ての地理的区分312は、地域全体100を構成する。すなわち、データのデータの集合320の各々は、道路、交差点、関心のある地点及び該データの集合に対応する地理的区分312内にある他の特徴を表す、複数のデータ・レコード336を含むことができる。
【0032】
一実施形態によれば、各コレクション232内の全てのデータの集合320は、均一なデータの集合・サイズを有する。例えば、データのデータの集合320の各々は、1K、2K、4K、8K、16K、32Kその他のサイズを有することができる。
コレクション232の各々のデータの集合・サイズは、データを使用することになるエンドユーザのコンピュータのメモリ・リソースを含む幾つかの要素に基づいて決定することができる。この実施形態によれば、1つのコレクション232のデータの集合320は、別のコレクション232のデータの集合320と異なるサイズにすることができる。例えば、1つのコレクション232は、サイズが32Kのデータの集合を有することができ、その一方で、別のコレクション232は、サイズが16Kのデータの集合を有することができる。
【0033】
図3及び図4に示すように、コレクション232の各々は、複数のデータの集合320を含むことができる。コレクション232のデータの集合320の各々は、全地域100内に位置する地理的区分312の別個の1つに対応する。ダウンロード可能なデータ記憶装置124において、コレクション232の各々と該コレクション232のデータの集合320の各々は、予め計算されている。言い換えれば、各コレクション232の決定及び生成と、各コレクション232を構成する全てのデータの集合320の決定及び生成は、ダウンロード可能なデータ記憶装置124のデータのいずれかが、エンドユーザのコンピュータ130のいずれかにダウンロードできるようになる前に行われる。これにより、どのデータをエンドユーザに送信するかの決定が容易になる。エンドユーザが、彼又は彼女のコンピュータで局所的に使用するためにデータを要求する時には、ナビゲーション・サービス・サーバ120が、どの特定のデータ・レコードを該エンドユーザが必要とし、これらのデータ・レコードを該エンドユーザに送信するかを判断する必要はない。代わりに、ナビゲーション・サービス・サーバ120は、どの地理的区分312がエンドユーザに要求され、これらの地理的区分312における全ての地理的特徴を表すデータを含んでいる全てのデータの集合320をエンドユーザに送信するかを判断する。エンドユーザに送信されるデータの集合320は、地域を表す全てのデータのクリップ又はスライスを表す。これらのデータの集合320は、エンドユーザに必要とされる個々のデータ・レコードの全てを含んでいる。この系統化と処理は、ナビゲーション・サービス・サーバ120での演算を容易にする。ナビゲーション・サービス・サーバ120における地理データ提供アプリケーション228は、エンドユーザがデータの集合に対応する定義された地理的区分312に対応するいずれかのデータを必要としているかどうかを判断し、必要としている場合には、地理的区分312に対応するデータの集合の全部をエンドユーザに送信する。この系統化と処理はまた、後でより詳細に説明するようなメモリ・リソースを管理する方法を与えることで、エンドユーザのコンピュータでの演算を容易にする。
【0034】
後で説明するのを除いて、ダウンロード可能なデータ記憶装置124からエンドユーザのコンピュータにデータがダウンロードされる時に、該データは、全てのデータの集合にダウンロードされる。これは、地理的区分312の各々に含まれている地理的特徴を表す全てのデータ・レコード336は、グループとして一緒にアクセスされるということを意味する。したがって、データの集合320は、エンドユーザのコンピュータで使用するため同時にダウンロードされたデータ・レコードの量を表す。データのデータの集合がエンドユーザのコンピュータに送信されると、該データの集合のデータ・レコードは全て、該エンドユーザのコンピュータで利用可能である。一実施形態において、データの集合の中の全てのデータ・レコードは、エンドユーザのコンピュータ・システムのメモリに同時に保管される。
【0035】
C.異なる種類のデータの集合
前述のように、ダウンロード可能な地理データ記憶装置124は、地理データの異なるコレクション232を含む。これらの異なるコレクション232は、全て同じ地域(図1の100)を表すが、異なる形式のデータ(すなわち別に系統化されたデータ)を含むことができる。これらの異なるデータのコレクション232は全て、前述のようにデータの集合に系統化される。前述のように、コレクションの中のデータの集合232は、均一なデータの集合・サイズに合わせることが好ましい。しかしながら、1つのコレクション232の中のデータの集合の均一サイズは、別のコレクション232の中のデータの集合の均一サイズと異なっていてもよい。コレクション232の幾つかのコンテンツについて、次に説明する。
【0036】
(1)ダウンロード可能な地理データの第1コレクション
図5は、コレクション232(1)の1つの中の地理データ336のデータの集合320の1つの中のコンテンツを説明するのに使用する概略図である。データの集合320の中のデータ336は、地理的区分312(1)の1つに対応する。この実施形態において、データの集合320は、地理的区分312(1)に含まれている全ての特徴を表す全てのデータ336を含んでいる。一例として、データの集合320は、該データの集合320に対応する地理的区分312(1)にある全ての道路を表すデータを含んでいる。各道路は、一続きの連結された区間として表され、該区間は、道路沿いの隣接する交差点の間の道路区間か又は交差点と道路の行き止まり位置との間の道路区間に対応する。この実施形態において、各道路区間は、別個のデータ・エンティティ(又はデータ・レコード)で表される。道路区間を表す各データ・レコードは、該道路区間の速度制限(又は速度圏)、該道路区間の機能的分類(すなわちランク)、該道路区間沿いの車線の数その他のような表示された道路区間についてのデータを含む(又は示す)。
【0037】
道路区間を表すデータ・レコードはまた、道路区間の位置を示すデータも含んでいる。一実施形態において、この情報は、道路区間の終点を表すノード・レコードの記述を含む。ノード・レコードに関連するのは、道路区間の終点(すなわちノード)の位置(例えば緯度、経度、及び必要であれば高度)を示すデータである。直線ではない道路区間については、道路区間の形状を示すために付加的なデータが含まれる。一実施形態において、この目的のために形状ポイントデータが使用される。形状ポイントは、道路区間の終点の間の該道路区間沿いの地点の位置(例えば緯度、経度、及び必要であれば高度)を特定する。1つ又はそれ以上の形状ポイントを使用することで、直線以外の道路区間の形状を表すことができる。
【0038】
道路区間を表すレコードはまた、道路区間の1つ又はそれ以上の名前を示すデータも含んでいる。一実施形態において、この情報は、1つ又はそれ以上の名前レコードの記述を含む。この実施形態において、道路の名前レコードと他の名前の付いた地理的特徴は、同じデータの集合に含まれる。
【0039】
図5に示す実施形態において、データの集合320はまた、関心のある地点のデータも含んでいる。関心のある地点のデータは、関心のある地点に関する情報を含んでいる。関心のある地点は、企業、公共施設その他を含む。関心のある地点のデータは、名前、種類(例えば、ホテル、飲食店、チェーン店、博物館、警察署その他)、住所、電話番号その他のような表示された関心のある地点に関する情報を含む。この実施形態において、地理的区分に含まれている関心のある地点のデータ・レコードは、道路区間データと、ノード・データと、名前データと共に、同じデータ・データの集合に含まれる。
【0040】
図5のデータ・コレクション232(1)では、全てのデータの集合が16Kのサイズである(しかし、他のどのデータサイズを使用することもできる)。図6は、別のデータ・コレクション232(2)を示す。図6において、コレクション232(2)は、同じ種類のデータ、例えば道路区間レコード、ノード・レコード、名前レコード、関心のある地点レコードその他を含むデータの集合320に分割される。しかしながら、図6のコレクション232(2)を生成するデータの集合320は、図5のコレクション232(1)の中のデータの集合と異なるサイズを有する。図6のコレクション232(2)の中のデータの集合は、それぞれ32Kのサイズである。図6のデータの集合320の各々は、図5のデータの集合の各々より多くデータが含まれているので、各データの集合は、より広い地理的区分を表すことができる。したがって、図6に示すように、データの集合320に対応する地理的区分312(2)は、図5のデータの集合320に対応する地理的区分312(1)より寸法が大きい。
【0041】
図7は、別のデータ・コレクション232(3)を示す。図7に示すデータのコレクション232(3)は、図5及び図6に示すそれぞれコレクション232(1)及び232(2)のように、同じ種類のデータ、例えば、道路区間レコード、ノード・レコード、名前レコード、関心のある地点レコードその他を含む。
さらに、図7のデータ・コレクション232(3)の中の各データの集合は、発音データも含んでいる。発音データは、表示された地理的区分における地理的特徴及び/又は関心のある地点の名前に対応している。発音データは、エンドユーザのコンピュータ130の適当なハードウェア及びソフトウェアを使用してこれらの名前を聞き取り可能に再生できるように、データの集合320の中に、表された地理的区分における地理的特徴及び/又は関心のある地点の名前に対応する音声表現を含んでいる。図7のデータ・コレクション232(3)において、各データの集合320は64Kのデータを含んでいるが、他のデータサイズを使用することもできる。
【0042】
図8は、さらに3つのデータ・コレクション232(4)(1)、232(4)(2)、及び232(4)(3)を示す。この実施形態において、コレクション232(4)(1)、232(4)(2)、及び232(4)(3)の各々は、幾つかの種類(又は属性)のデータのみを含んでいる。例えば、コレクション232(4)(1)は、経路データ、例えば区間レコードとノード・レコードのみを含む。コレクション232(4)(2)は、名前レコードのみを含む。コレクション232(4)(3)は、関心のある地点レコードのみを含む。これらのコレクション232(4)(1)、232(4)(2)、及び232(4)(3)の各々は、別個の地理的区分312の各々に対応している別個のデータの集合320に系統化される。したがって、コレクション232(4)(1)のデータの集合320は、地理的区分312(4)における道路と交差点を表す区間レコードとノード・レコードを含む。コレクション232(4)(2)は、地理的区分312(4)における地理的特徴及び/又は関心のある地点の名前を表す名前レコードを含む。コレクション232(4)(3)は、地理的区分312(4)における関心のある地点の位置を表す関心のある地点レコードを含む。図8のデータ・コレクション232(4)(1)、232(4)(2)、及び232(4)(3)において、各データの集合320は、16Kのデータを含む(しかし、他の均一なデータサイズを使用することもできる)。
【0043】
図5から図8までに示されている異なるデータ・コレクションの実施形態は、ナビゲーション・サービス・サーバ120上のダウンロード可能な地理データ記憶装置(図2の124)に保管できるデータ・コレクションの幾つかの異なる形式のみを表している。ダウンロード可能な地理データ記憶装置124は、異なるサイズのデータの集合を保有するデータのコレクションを含むことができる。さらに、ダウンロード可能な地理データ記憶装置124は、互いに別々に系統化されたデータの集合を保有するデータ・コレクションを含むことができる。例えば、ダウンロード可能な地理データ記憶装置124は、アルファベット順に又は行政体系(例えば市、郡、州及び国)により系統化されたデータのデータの集合を保有するコレクションを含むことができる。
【0044】
III.エンドユーザのコンピュータ
A.概要
前述のように、各エンドユーザは、コンピュータ(図1の130)を使用して、ナビゲーション・サービス・サーバ120からデータを入手する。また、前述のように、ナビゲーション・サービス・サーバ120から入手したデータを用いて、エンドユーザのコンピュータ上で幾つかのナビゲーション関連機能が局所的に実行される。異なるエンドユーザのコンピュータは、異なるハードウェアとソフトウェアを有するので、エンドユーザのコンピュータ上で実行されるナビゲーション関連機能は、該エンドユーザのプラットフォーム毎に変化させることができる。したがって、次のセクションでは、エンドユーザのコンピュータの構成について説明する。全てのエンドユーザのコンピュータが、必ず後述の全ての機能を提供するとは限らず、また、幾つかのエンドユーザ・コンピュータは、付加的な又は他の機能を提供することができる、ということについて理解されたい。
【0045】
異なるエンドユーザのコンピュータは、異なるハードウェア及びソフトウェア・リソースを有していても良いが、全てのエンドユーザ・コンピュータは、ナビゲーション・サービス・サーバ(図1の120)からデータを受信する。エンドユーザ・コンピュータの幾つか又は全ては、ナビゲーション・サービス・サーバ120上のダウンロード可能な地理データ記憶装置124から地理データを受信する。ダウンロード可能な地理データ記憶装置124から地理データを受信するエンドユーザ・コンピュータ130は、後述のメモリ管理特徴を用いて、ナビゲーション・サービス・サーバ120から入手したデータのデータの集合を処理することができる。
【0046】
B.エンドユーザのコンピュータのコンポーネント
図9は、エンドユーザのコンピュータ130の1つにおけるコンポーネントの幾つかのブロック図である。エンドユーザのコンピュータ130は、通信システム400を含む。エンドユーザのコンピュータ130における通信システム400は、データ・ネットワーク170を介してナビゲーション・サーバ(図1の120)との間でメッセージを送受信するのに必要とされるハードウェアとソフトウェア・コンポーネントを含む。通信システム400は、エンドユーザのコンピュータ130における他のコンポーネントとインターフェースする。
【0047】
エンドユーザのコンピュータ130はまた、ユーザ・インターフェース410も含んでいる。ユーザ・インターフェース410は、エンドユーザが、エンドユーザのコンピュータ130に情報を入力し、該エンドユーザのコンピュータ130から情報を受け取ることができるようにする。ユーザ・インターフェース410は、ハードウェアとソフトウェア・コンポーネントを含んでいる。例えば、ユーザ・インターフェース410は、ディスプレイ、マイクロホン、スピーカ、キーパッド、又は情報をコンピュータに入力し、そこから情報を出力するための他の種類の手段を含むことができる。ユーザ・インターフェース410は、メニュー、プロンプト、音声その他を提供することができる支援ソフトウェアを含む。ユーザ・インターフェース410は、エンドユーザのコンピュータ130における他のコンポーネントとインターフェースする。
【0048】
エンドユーザのコンピュータ130には、ナビゲーション関連アプリケーション420が含まれる。ナビゲーション関連アプリケーション420は、ナビゲーション・サーバ120から入手した地理データを使用して、様々な異なる種類のナビゲーション関連のサービスを提供する。ナビゲーション関連アプリケーション420の1つは、測位アプリケーション420(1)である。測位アプリケーション420(1)は、ナビゲーション・サーバ120から入手した地理データを使用して、道路網を表すデータに対するエンドユーザのコンピュータ130の位置を求める。測位アプリケーション420(1)はまた、エンドユーザのコンピュータ130の一部である測位システム430からデータを入手することもできる。測位システム430は、GPS、推測航法、或いはこれらの又は他の技術の組み合わせを使用して、エンドユーザのコンピュータ130の位置を求めることができる。測位を行う方法は、米国特許第6,192,312号に開示されており、その開示全体を引用によりここに組み入れる。
測位アプリケーション420(1)は、必要であれば、すなわち、全てではないエンドユーザのコンピュータは、測位を提供するか又は測位を支援することができる。
【0049】
エンドユーザのコンピュータにおけるナビゲーション・アプリケーション420のその他には、経路案内420(2)がある。経路案内アプリケーション420(2)は、ナビゲーション・サーバ120からのデータを使用して、エンドユーザに所望の目的地まで移動するための指示を与える。
【0050】
地理データを使用して経路案内を行う方法は、米国特許第6,199,013号に記載されており、その開示全体を引用によりここに組み入れる。
【0051】
エンドユーザのコンピュータにおけるナビゲーション・アプリケーション420のその他には、地図表示420(3)がある。地図表示420(3)は、ナビゲーション・サービス・サーバ120からのデータを使用して、エンドユーザのコンピュータにおけるユーザ・インターフェース410の表示画面に写実的な地図を提供する。この地図は、エンドユーザのコンピュータの位置周辺の区分、エンドユーザが追従する経路沿いの区分、エンドユーザにより指定された位置周辺の区分、又はその他指定された区分を示すことができる。地理データを使用して画面表示を行う方法は、米国特許第6,092,076号と米国特許第6,163,749号に開示されており、その開示全体を引用によりここに組み入れる。
【0052】
エンドユーザのコンピュータ上のナビゲーション・アプリケーション420のその他には、経路再指定アプリケーション420(4)がある。経路再指定アプリケーション420(4)は、エンドユーザが目的地までの経路から逸脱した時に、該エンドユーザが追従できるように案内を受けるために使用される。経路再指定アプリケーション420(4)は、ナビゲーション・サーバ120からのデータを使用して、目的地までの新たな経路か又は元の経路に引き返す経路を計算する。経路再計算アプリケーション420(4)は、米国特許第6,129,314号に記載されているのと同じ方法を使用して経路計算を行うことができ、その開示全体を引用によりここに組み入れる。
【0053】
エンドユーザのコンピュータ上のナビゲーション・アプリケーション420のその他には、照会アプリケーション420(5)がある。照会アプリケーション420(5)は、ナビゲーション・サービス・サーバ120のナビゲーション・アプリケーション(図2の216)への照会(すなわち情報の要求)を生成するのに使用される。照会は、経路計算アプリケーション220を使用して経路を計算するための要求とすることもできるし、検索サービス224又はナビゲーション・サービス・サーバ120により提供されたその他のサービス又はアプリケーションを使用した企業、個人、又は関心のある地点に関する情報の要求とすることもできる。照会アプリケーション420(5)は、ナビゲーション・サービス・サーバ120にメッセージを送信し、応答を待ち、応答を受信し、次いで要求したデータを局所的に、例えばローカル・アプリケーション420で使用することを管理する。
【0054】
エンドユーザのコンピュータ上のナビゲーション・アプリケーション420のその他には、関心のある地点の参照アプリケーション420(6)がある。関心のある地点の参照アプリケーション420(6)は、関心のある地点の参照(すなわち検索)を使用する。関心のある地点を説明するデータは、ナビゲーション・サービス・サーバ120に、又は局所的に保存される。
【0055】
C.エンドユーザのコンピュータのメモリ管理機能
エンドユーザのコンピュータ130は、メモリ管理アプリケーション500を含む。メモリ管理アプリケーション500は、エンドユーザのコンピュータ130のメモリ・リソースを管理する。メモリ管理アプリケーション500により実行される機能には、ナビゲーション・サーバ120から受信した地理データの管理がある。この機能の一部として、メモリ管理アプリケーション500は、ナビゲーション・サービス・サーバ120のダウンロード可能な地理データ記憶装置124からエンドユーザのコンピュータで受信した地理データのデータの集合320を管理する。地理データのデータの集合をメモリで管理する方法は、米国特許第6,073,076号と米国特許第6,047,280号に開示されており、その開示全体を引用によりここに組み入れる。
【0056】
図9を参照すると、メモリ管理アプリケーション500は、ナビゲーション関連アプリケーション420で使用するためエンドユーザのコンピュータ130のメモリ506の一部504を予約し、さらに、データの集合のキャッシュ520として使用するため別の部分514を予約する。メモリ管理アプリケーション500は、エンドユーザのコンピュータ130の初期化の時に又はこの後のいつでも、これらの部分504及び514のサイズを決定することができる。この決定は、インストールした利用可能なメモリの全容量を考慮に入れることができる。さらに、メモリ管理アプリケーション500は、メモリ506の再割当て可能な部分528を決定することができる。この再割当て可能な部分528の幾つか又は全ては、ナビゲーション・アプリケーション420のために使用したり、データの集合のキャッシュ520のために使用したりすることができる。再割当て可能な部分528の使用は、エンドユーザのコンピュータ130の実行時に、メモリ管理アプリケーション500により、エンドユーザの要求に基づいて決定される。
【0057】
エンドユーザのコンピュータ130の動作中に、該エンドユーザのコンピュータ130におけるナビゲーション関連アプリケーション420は、ナビゲーション・サービス・サーバ120からダウンロードしたデータの集合320に含まれているデータを使用する。エンドユーザのコンピュータ130の性能を向上させるために、エンドユーザのコンピュータ130のメモリ506の中にキャッシュ520が設けられる。キャッシュ520は特に、ナビゲーション・サービス・サーバ120からダウンロードした多くの地理データのデータの集合320を保存するのに使用される。キャッシュ520に地理データのデータの集合を保存することにより、多くのデータの集合を使える状態でメモリに保管することにより、エンドユーザのコンピュータ130におけるナビゲーション関連アプリケーション420を支援する。データの集合を使える状態でメモリに保有することは、ナビゲーション・サービス・サーバ120からデータの集合を入手することに関連する比較的大きい遅延が回避される。データの集合のキャッシュ520はまた、ナビゲーション機能がすぐに必要とすると予測される地理データのデータの集合を保存するために使用することもできる。前述のように、データの集合のキャッシュ520の構成と動作は、メモリ管理アプリケーション500により実行される。
【0058】
データの集合のキャッシュのサイズは、種々の要素に基づいている。データの集合のキャッシュのサイズに影響を及ぼす要素の1つは、データの集合のサイズである。データの集合のサイズに対するデータの集合のキャッシュのサイズにより、データの集合のキャッシュにどの位のデータの集合を確保できるかが決まる。上述のように、幾つかの実施形態において、データの集合は、ナビゲーション・サービス・サーバ120のダウンロード可能な地理データ記憶装置124に、標準サイズ例えば2K、4K、8K、16K、32Kその他で保存される。したがって、エンドユーザのコンピュータのデータの集合のキャッシュ520のサイズにより、局所的に保存可能なデータの集合の数が定められる。例えば、384Kのデータの集合のキャッシュは、サイズがそれぞれ16Kのデータの集合を最大24個保存できる。同様に、より大きいサイズのデータの集合をより少なく保存することもできるし、これに対して、より小さいサイズのデータの集合をより多く保存することもできる。一実施形態において、データの集合のキャッシュ520は、全て同じサイズのデータの集合を保有するのに使用され、或いは別の実施形態において、データの集合のキャッシュ520は種々のサイズのデータの集合を保有することができる。
【0059】
データの集合のキャッシュのサイズに影響を及ぼす別の要素は、エンドユーザのコンピュータ130の利用可能な全てのメモリ・リソースである。制限されたメモリ・リソースのコンピュータは、データの集合のキャッシュに比較的小さい部分しか提供しないが、これに対して、大きいメモリ・リソースを有するコンピュータは、比較的多くのメモリをデータの集合のキャッシュに提供することができる。
【0060】
データの集合のキャッシュ520に使用されるメモリの量に影響を及ぼすと考えられる更に別の要素は、データの集合のキャッシュ520に割り当てられたメモリ514と、ナビゲーション・アプリケーション420に割り当てられたメモリ504との相対的サイズである。データの集合のキャッシュ520に対する相対的に多いメモリが割り当てられると、ナビゲーション・アプリケーション420で利用可能なメモリ504の量が制約される場合には、また逆の場合も同様に、エンドユーザのコンピュータの性能を必ずしも向上させることにはならない。メモリ管理アプリケーション500は、ナビゲーション・アプリケーション420のためのメモリの割り当てと、データの集合のキャッシュで使用するためのメモリの割り当てとの間の適切なバランスを決定するアルゴリズムを含むことができる。ナビゲーション・アプリケーションで必要とされるデータの集合が(メモリ・マネージャ500で決定されたような)データの集合のキャッシュ520にない場合には、メモリ・マネージャ500は、ナビゲーション・サービス・サーバ120からデータの集合を要求する。
【0061】
IV.動作
A.経路案内
(1)概要
ナビゲーション・システム110で実行される機能の1つは、経路案内である。経路案内は、エンドユーザに所望の目的地に到着するための命令を与える。図10は、図1のナビゲーション・システム110で実行される所望の目的地までの経路に追従するための情報をエンドユーザに提供するためのプロセス600におけるステップを示すフローチャートである。
【0062】
(2)経路案内に先立つ機能
a.目的地の選択
経路案内は、ナビゲーション・システム110で実行される1つ又はそれ以上の他の機能と関連する、すなわち該機能から始められる。経路に追従するための情報がエンドユーザに提供される前に、経路の出発地と目的地を決定するステップが存在する(図10のステップ610)。目的地の決定は、地域100における位置を選択する手段をエンドユーザに提供することを含んでいる。目的地の選択は、住所、通りの交差点、地図位置、又は他の位置特定手段を含むことができる。或いは、目的地の選択は、エンドユーザの指定基準又はカテゴリ、例えば指定距離内に位置する特定の形式のレストランに合致するエンドユーザの位置の特定を含むことができる。
【0063】
図1と図10の実施形態において、目的地選択機能は、局所的に利用可能なデータ、ハードウェア又はソフトウェアと、遠隔位置のデータ、ハードウェア又はソフトウェアとの組み合わせを用いて実行することができる。一実施形態によれば、エンドユーザは、彼又は彼女のコンピュータ130で、局所的に利用可能なハードウェア及びソフトウェア(例えば図9の照会アプリケーション420(5))を使用して、ナビゲーション・サービス・サーバ120の検索アプリケーション(図2の224)にアクセスする。エンドユーザは、局所的なハードウェア及びソフトウェアと遠隔的なハードウェア及びソフトウェアとのこの組み合わせを使用して、ナビゲーション・サービス・サーバ120の作業データベース122にアクセスし、目的地としての位置を特定する。目的地は、住所、人名、企業住所、又は企業名とすることができる。或いは、エンドユーザは、検索アプリケーション(図2の224)を使用して、位置例えば指定位置に近い銀行により、個人、企業、又は関心のある地点を見つけることができる。
【0064】
場合によっては、エンドユーザは、エンドユーザのコンピュータに局所的に搭載された測位アプリケーション(図9の420(1))を最初に使用して、彼又は彼女の現在位置を識別し、次いでこの位置をナビゲーション・サービス・サーバ120の検索アプリケーション224に指定して、個人、企業又は関心のある地点を位置ベースで検索するのに使用することができる。
【0065】
別の実施形態において、エンドユーザは、局所的に利用可能なデータ、ハードウェア又はソフトウェアを使用して、目的地を決定することができる。更に別の実施形態によれば、目的地選択機能は、局所的に利用可能なデータ、ハードウェア又はソフトウェアと、遠隔位置のナビゲーション・サービス・サーバから入手したデータを使用して、エンドユーザのコンピュータ上で実行することができる。
【0066】
b.出発地の指定
経路を計算するには、出発地点(すなわち出発地)も必要とされる。場合によっては、エンドユーザの現在位置を出発地として使用することもできる。エンドユーザの現在位置は、エンドユーザのコンピュータ130のナビゲーション・アプリケーション420の中に局所的に搭載された測位アプリケーション420(1)を使用して求めることができる。この機能を実行する時に、測位アプリケーション420(1)は、局所的に利用可能なデータを使用することができる。これらの局所的に利用可能なデータは、エンドユーザのコンピュータに内蔵された地理データベースの一部とすることができる。或いは、局所的に利用可能なデータは、照会アプリケーション420(5)を使用してエンドユーザにより作製された前の要求に対応して、ナビゲーション・サービス・サーバ120から予め入手されている。さらに別の実施形態によれば、出発地は、目的地と同じ方法で求めることができる。さらに別の実施形態によれば、エンドユーザの現在位置は、エンドユーザのコンピュータにおける測位システム(図9の430)を使用して求められた座標を用いて指定することができる。さらに別の実施形態によれば、ユーザは、経路がどこで始まるのか明示的に示すことができる。これは、前述の目的地選択と同様である。
【0067】
(3)経路計算
出発地と目的地が指定された後に、プロセス600は、出発地と目的地を示すデータがナビゲーション・サーバ120(図10のステップ622)の経路計算アプリケーション220で受信されるステップを含む。上述のように、経路計算アプリケーション220は、指定された出発地と目的地との間の法的に有効な連続する一続きの道路(又はその区分)である解答経路を求める。経路計算アプリケーション220は、作業地理データベース122のデータを使用する。経路計算アプリケーション220の動作については既に説明した。解答経路が計算されると、連続的な法的に有効な出発地から目的地までの経路を生成する一続きの道又はその区分が特定される。
【0068】
経路計算アプリケーション220が解答経路を計算した後に、出力650が与えられる。図11は、経路計算アプリケーション220の出力650のコンポーネントを表す概略図である。経路計算出力650は、複数の道路区間を特定する番号付きリストを含む。図11において、複数の道路区間がデータ・エンティティIDにより特定される。これらのIDは、作業地理データベース122の開発者によりこれらの道路区間を表すデータ・エンティティに割り当てられる。経路計算アプリケーション220の出力650における複数の道路区間データ・エンティティは、seg1、seg2、seg3、...seg(n)のラベルが付けられる。複数のデータ・エンティティは、経路計算アプリケーション220で計算された連続的なナビゲーション可能な出発地と目的地の間の経路を生成する道路区間を表す。データ・エンティティIDを使用する代わりに、経路計算アプリケーション220は、解答経路を作り出す道路区間を特定するためのその他の手段を使用することもできる。
【0069】
経路計算出力650は、道路区間のリストに加えて、他の情報を含むことができる。
【0070】
(4)エンドユーザに経路(及び付加的データ)を提供する
ナビゲーション・サービス・サーバ120の経路計算アプリケーション220で解答経路を計算した後に、ナビゲーション・サービス・サーバ120は、解答経路に追従するための案内をエンドユーザに提供できるように、エンドユーザのコンピュータ130にデータを送信する。ナビゲーション・サービス・サーバ120は、エンドユーザのコンピュータ130に2種類のデータを送信する。最初に、ナビゲーション・サービス・サーバ120は、解答経路を生成する道路区間を示す経路計算アプリケーション220の出力650を、エンドユーザのコンピュータ130に送信する(図10のステップ656)。ナビゲーション・サービス・サーバ120は、解答経路を示すデータ650に加えて、解答経路に関連する付加的データ660も送信する。解答経路に関連する付加的データ660は、経路を移動するための有意義な案内をエンドユーザに提供するために、解答経路を示すデータ650と組み合わせて使用される。
【0071】
ナビゲーション・サービス・サーバ120によりエンドユーザのコンピュータ130に送信される付加的データ660は、ダウンロード可能な地理データ記憶装置124から入手される。解答経路が(ステップ636で)計算された後に、地理データ提供アプリケーション(図2の228)は、どのデータがダウンロード可能な地理データ記憶装置124からエンドユーザのコンピュータ130に送信されるのかを決定する(図10のステップ668)。上述のように、ダウンロード可能な地理データ記憶装置124に含まれているデータは、複数のコレクション232に系統化され、該コレクション232の各々は、複数のデータの集合に系統化される(図4の320)。したがって、どの地理データをエンドユーザのコンピュータ130に送信するかを決定する時に、地理データ提供アプリケーション228が、どのデータ・データの集合320を特定のコレクション232から送信するかを決定する。
【0072】
上述のように、地理データを送信する時にどのコレクション232を使用するかの決定は、様々な異なる方法で決定することができる。1つの方法は、エンドユーザのコンピュータに、データがそこから送信されることになるコレクションを特定するアプリケーションを搭載することである。
コレクション232は、IDか又は記述により特定することができる。或いは、地理データ提供アプリケーション228は、図2における加入者データベース208に照会して、どのコレクション232を特定のエンドユーザに使用するかを決定することができる。或いは、地理データ提供アプリケーション228は、1つのコレクションをデフォルトで使用することができる。使用に適したコレクションを決定するために、他のどのような手段をも使用することができる。
【0073】
地理データを送信する時にどのコレクション232を使用するかを指定することに加えて、エンドユーザのコンピュータにおけるアプリケーションも、ナビゲーション・サービス・サーバから受信したデータを保存するためエンドユーザのコンピュータで利用可能なメモリ・リソースを、地理データ提供アプリケーション228に示すことができる。或いは、エンドユーザのコンピュータで利用可能なメモリ・リソースのサイズは、図2の加入者データベース208における設定パラメータとして保存することもできるし、別の手法では、デフォルトのメモリサイズを使用することもできる。
【0074】
使用するデータのコレクション232が決定された後に、コレクション232における特定のデータの集合320が選択される。図12は、地理データ提供アプリケーション228が、エンドユーザのコンピュータにどのデータ・データの集合を送信するかをどのようにして決定するのか説明している。図12は、領域100の一部の地図690を示す。経路700は、地図690に示されている。経路700は、複数の連結された道路区間706として示されている。また、地図690には、地理的区分312(A)から312(L)までのアウトライン710が示されている。上述のように、これらの地理的区分312(A)から312(L)までの各々は、データの別個のデータの集合320に含まれているデータにより表される地理的特徴を含んでおり、該データの集合の中で地理データのコレクション232の全体が分割される。地理データ提供アプリケーション228は、経路計算アプリケーション220で計算されるような解答経路650における道路区間の位置を使用して、解答経路が横切るか又は解答経路における道路区間から指定距離内の地理的区分312を特定する。(指定距離は、設定可能である。)解答経路が横切るか又は該解答経路に近接した地理的区分は、好適な手段のいずれかにより決定することができる。例えば、経路計算アプリケーション220は、解答経路が計算される際に、これらの地理的区分のID(又はこれら自体のデータの集合のID)を保存することができる。
【0075】
解答経路が横切るか又は該解答経路に近接した地理的区分312(A)から312(L)までが決定されると、エンドユーザのコンピュータ130に送信するために、該地理的区分に含まれている地理的特徴を表すデータを含んでいるデータの集合320が決定される。
【0076】
地理データ提供アプリケーション228が解答経路に対応するデータの集合をエンドユーザのコンピュータに送信する時に、該データの集合は、出発地から始まる経路に対応する順に送信される。このようにして、エンドユーザのコンピュータは、出発地周辺の特徴を表すデータを含んでいるデータの集合を最初に受信し、次いで、経路の次の部分周辺の特徴を表すデータを含んでいるデータの集合を受信する。
【0077】
解答経路に対応するデータの集合をエンドユーザのコンピュータに送信する時に、地理データ提供アプリケーション228は、解答経路に対応する全てのデータの集合をエンドユーザのコンピュータに直ちに送信することができる。或いは、地理データ提供アプリケーション228は、データの集合の幾つかのみを最初に送信し、次いで、データの集合の残りを1つ又はそれ以上の次の時間に送信することができる。エンドユーザのコンピュータが、解答経路に対応するものとして特定された全てのデータの集合を保有するのに十分なメモリ・リソースを備えている場合には、地理データ提供アプリケーション228は、全てのデータの集合を直ちにエンドユーザのコンピュータに送信することができる。しかしながら、エンドユーザのコンピュータが、解答経路に対応するものとして特定された全てのデータの集合を保有するのに十分なメモリ・リソースを備えていない場合には、地理データ提供アプリケーション228は、エンドユーザのコンピュータがメモリに保有できるデータの集合の数だけ送信することができる。地理データ提供アプリケーション228により最初に送信されたデータの集合は、経路の最初の部分に対応する。地理データ提供アプリケーション228が、解答経路に対応するデータの集合の幾つかのみを最初に送信する時には、該地理データ提供アプリケーション228は、送信されていないデータの集合を特定するリストを維持する。この実施形態によれば、エンドユーザが、最初にメモリに保存されたデータの集合によって表された区域を通る経路に沿って進んだ後に、エンドユーザのコンピュータは、ナビゲーション・サービス・サーバに、経路の次の部分に対応するデータの集合を送信するよう要求する。地理データ提供アプリケーション228に保管された解答経路に対応するデータの集合のリストを使用して、次にどのデータの集合をエンドユーザのコンピュータに送信するかを迅速に特定する。
【0078】
図10のプロセス600に戻ると、解答経路に対応する全てのデータの集合がエンドユーザのコンピュータに送信される場合には、該プロセスは終了する(ステップ722及び724)。解答経路に対応する全てのデータの集合がエンドユーザのコンピュータに送信されない場合(例えばエンドユーザのコンピュータが全てのデータの集合を保有するのに十分なメモリを備えていない場合)には、送信されていないデータの集合を特定するデータが保存される(ステップ725)。次いで、このプロセスは、エンドユーザのコンピュータが経路の次の部分に対応するデータの集合を要求するまで待機する。経路の次の部分に対する要求を受信すると、追加のデータのデータの集合がエンドユーザのコンピュータに送信される(再びステップ720)。これらのステップは、解答経路に対応するデータの集合が全て送信されるまで繰り返される(ステップ722及び724)。
【0079】
(5)エンドユーザのコンピュータ上でのナビゲーション関連機能の提供
図13は、ナビゲーション・サービス・サーバ120から経路を示すデータ650と付加的データ660を受信した時に、エンドユーザのコンピュータ上で実行されるプロセス750を示す。最初に、データ650及び660が、エンドユーザのコンピュータ130で受信される(ステップ760)。
【0080】
メモリ管理アプリケーション500は、既に行われていない場合には、データの集合のキャッシュ520として使用するためエンドユーザのコンピュータのメモリの一部を予約する(ステップ764)。データの集合のキャッシュを生成する時に、メモリ管理アプリケーション500は、受信するデータの集合のサイズを考慮に入れる。例えば、データの集合が64Kのサイズである場合には、メモリ管理アプリケーション500は、200個のデータの集合を保有するに十分な1280Kのメモリを予約することができる。メモリ管理アプリケーション500は、データの集合320の形態の付加的データ660を、データの集合のキャッシュ520に保存する(ステップ770)。
【0081】
メモリ管理アプリケーション500により生成されたデータの集合のキャッシュ520は、全経路についての全データの集合を確保するのに十分に大きくすることはできない。この場合には、メモリ管理アプリケーション500は、ナビゲーション・サービス・サーバ120から送信された順にデータの集合を保存し、データの集合のキャッシュが満杯になった時にそれ以上のデータの集合を保存するのを止める。このようにして、経路の始まりに対応する付加的データのデータの集合660が、データの集合のキャッシュに保存される。このとき、経路の次の部分に対応する付加的データのデータの集合660は、データの集合のキャッシュに保存されない。メモリ管理アプリケーション500は、地理データ提供アプリケーション228にキャッシュのサイズ(又は保存できるデータの集合の数)を示すメッセージを送信することができる。或いは、メモリ管理アプリケーション500は、地理データ提供アプリケーション228に、データの集合のキャッシュが満杯の時にデータの集合を送信するのを止めるようにメッセージを送信することができる。
【0082】
エンドユーザのコンピュータにおいて、解答経路を示すデータ650は、データの集合のキャッシュ520には保存されない。その代わりに、解答経路を示すデータ650は、メモリの作業部分に保存され(図9の504)、該データは、エンドユーザのコンピュータ130の種々のナビゲーション・アプリケーション420で使用される。
【0083】
エンドユーザのコンピュータにおいて、ナビゲーション・アプリケーション(図9の420)は、解答経路に関連する付加的データ660を、解答経路を示すデータ650と組み合わせて使用して、ナビゲーション関連機能を提供する(ステップ776)。例えば、エンドユーザのコンピュータ130の経路案内アプリケーション420(2)で経路データ650と付加的データ660を使用して、解答経路沿いの特定の位置で移動命令を与えることができる。一例として、経路案内アプリケーション420(2)は、経路データ650と付加的データ660を使用して、「次の交差点、左折です」のような移動命令を与える。これらの付加的データ660は、表示画面上の文字か又は音声命令としてこれらの命令を与えるのに使用される。
【0084】
別の実施例によれば、解答経路に関連する経路データ650と付加的データ660を、エンドユーザのコンピュータ130の地図表示アプリケーション420(3)で使用して、エンドユーザのコンピュータのユーザ・インターフェース(図9の410)の表示画面に経路の地図を与えることができる。経路の地図は、「進路要図」の形式にすることができる。
【0085】
さらに別の実施形態によれば、経路データ650と付加的データ660は、解答経路の一部ではないが解答経路に隣接している道路区間の位置を示すのに使用できる。これらのデータは、車両測位ハードウェア及びソフトウェア、例えばエンドユーザのコンピュータの測位アプリケーション420(1)で使用して、エンドユーザが解答経路から逸脱しているかどうかを判断し、逸脱している場合には、(例えば経路再指定アプリケーション420(4)を使用して)どのようにして解答経路に戻れば良いのか判断することができる。
【0086】
上述のように、データ650により表される全解答経路に関連する全てのデータ・データの集合320を最初に保存することは不可能である。この場合には、経路の最初の部分沿いの地理的特徴を表すデータを含んでいるデータの集合のみが、エンドユーザのコンピュータのデータの集合のキャッシュに最初に保存される。次いで、エンドユーザが、経路に沿って中途まで移動した後に、該エンドユーザは、最終的には、データの集合のキャッシュ・エンドにおけるデータの適用範囲の位置に接近する。例えば、再び図12を参照すると、エンドユーザのコンピュータのデータの集合のキャッシュが、6つのデータ・データの集合のみを格納するスペースを備える場合には、区域312(A)から312(F)までに対応する6つのデータの集合が、最初にデータの集合のキャッシュに保存されることになる。次いで、エンドユーザが経路に沿ってBで示される地点まで移動した後に、該エンドユーザは、データの集合のキャッシュに保存された付加的データの適用範囲が終了する位置に近接するようになる。エンドユーザがこの位置にいる時に、エンドユーザのコンピュータの照会アプリケーション420は、ナビゲーション・サービス・サーバ120にナビゲーション関連のサービスとデータについての新たな要求を送信する(ステップ790及び792)。この新たな要求は、前の要求を基準にすることもできるし、新たな経路に対する要求として処理することもできる。
【0087】
1つの方法によれは、エンドユーザのコンピュータが、そのデータの集合のキャッシュに局所的に含まれるデータの集合に対応する適用範囲の端に接近し、ナビゲーション・サービス・サーバから更にデータの集合を要求した時(ステップ792)に、この新たな要求は、前の要求を基準にすることができる。新たな要求が、前の要求を基準にしている場合には、ナビゲーション・サービス・サーバにおけるプロセスは、(図10のステップ725において)エンドユーザのコンピュータに予め送信されていないデータの集合を特定するリストを使用して、どのデータの集合を次に送信するかを決定する。これらのデータの集合は、ダウンロード可能なデータ記憶装置124から入手され、エンドユーザのコンピュータに送信される。これらの新たなデータの集合がエンドユーザのコンピュータで受信されると、ステップ760によりプロセス750が開始される。
【0088】
別の方法によれば、エンドユーザのコンピュータが該データの集合のキャッシュに局所的に含まれるデータの集合に対応する適用範囲の縁に接近し、ナビゲーション・サービス・サーバから更にデータの集合を要求した時(ステップ792)に、該要求は、全く新たな経路に対する要求としてナビゲーション・サービス・サーバで処理することができる。ナビゲーション・サービス・サーバは、図10のステップ622で始まるプロセス600を実行する。ナビゲーション・サービス・サーバ120は、経路計算アプリケーション220を使用して、B地点を新たな出発地として用いて、目的地までの新たな経路を計算する(同じく図10におけるステップ636)。新たな経路に対する要求として経路の次の脚に対する要求を処理することで、ナビゲーション・サービス・サーバの経路計算アプリケーション220は、前の経路が計算されてから発生しうる道路状況の変化を考慮に入れることができる。次いで、ナビゲーション・サービス・サーバ120は、エンドユーザのコンピュータに(新たな経路データ650の形態で)新たな経路と、(データの集合の形態で)新たな付加的データ660のデータの集合を送信する(同じく図10のステップ656及び720)。新たな経路データ650と新たな付加的データ660がエンドユーザのコンピュータで受信される時に、これらは全く新たな経路として処理される。データの集合のキャッシュに保存されていたデータの集合は、経路の次の脚に関連して受信された新たなデータの集合で書き換えられる。
【0089】
B.経路案内なしの地図表示
別の実施形態において、エンドユーザは、必ずしも経路を要求せずに、地図表示のための地理データを要求することができる。例えば、エンドユーザは、彼又は彼女が存在している位置周辺区域の地図表示を得ようとすることができる。この場合には、エンドユーザは、彼又は彼女の地理的位置周辺の地図表示を要求するよう彼又は彼女のコンピュータを動作させる。エンドユーザは、この目的のために照会アプリケーション420(5)を使用することができる。エンドユーザは、彼又は彼女の位置を指定することもできるし、或いは、照会アプリケーション420(5)が、(存在する場合には)測位システム430からエンドユーザの現在位置を示すデータを入手し、地図表示データに対する要求の中にこの情報を入れることができる。
【0090】
地図表示データに対する要求は、前述の経路情報に対する要求と同様の方法でナビゲーション・サービス・サーバ120で処理される。この場合には、経路を計算する必要はない。ナビゲーション・サービス・サーバは、指定位置周辺の特徴を表す地理データを含むデータの集合を特定する。次いで、ナビゲーション・サービス・サーバは、前述のように、これらのデータの集合をエンドユーザのコンピュータに送信する。エンドユーザのコンピュータにおいて、これらのデータの集合は、図14に関して既に説明したのと同様の手法で処理される。
【0091】
彼又は彼女のエンドユーザの現在位置に関する地図データを要求する代わりに、該エンドユーザは、どの位置に関する地図データも要求することができる。エンドユーザは、地図データが要求される位置を特定するために、好適な手段のいずれをも使用することができる。
【0092】
C.他の機能
エンドユーザのコンピュータに提供される機能のどれも、互いに組み合わせて使用することもできるし、別個に使用することもできる。例えば、測位機能(すなわち、図9の測位アプリケーション420(1)を使用する)は、地図表示機能又は経路案内機能なしで実行することができる。
【0093】
III.別の実施形態
A.機能に基づくデータ・コレクションの選択
図8に関連して、形式(又は機能)により系統化されたデータのコレクションを説明した。データ・コレクションについての種々の種類と機能が提供される。
例えば、経路案内、地図表示、車両測位、音声データ、非音声データその他に、異なるコレクションのデータを与えることができる。エンドユーザのコンピュータが地理データを要求する時には、ナビゲーション・サービス・サーバにデータの種類が示される。この種類は、エンドユーザのコンピュータが対応しているリソースに応じて指定することができる。この種類はまた、エンドユーザのプラットフォームが実行するのに必要とするデータを、機能に応じて指定することができる。例えば、エンドユーザが、地図表示を行うことのみを意図し、経路案内を行うことを意図しない場合には、エンドユーザのコンピュータは、地図表示コレクションから送信されるデータを指定することができる。この方法において、エンドユーザのコンピュータは、必要のないデータは送信せず、これにより、指定された種類のさらに多くのデータを送信できるようにする。
【0094】
B.レイヤに基づくデータ・コレクション
前述のデータ・コレクションの種類(図5から図8までの232)に加えて、図2におけるダウンロード可能なデータ記憶装置124は、レイヤに基づくコレクションを含むことができる。レイヤに基づくコレクションは、地域における道路に割り当てられた順位を使用する。順位は、道路の機能的分類に関連させることができる。移動が一般により速くなる幹線道路は、高次の順序に割り当てられ、移動が一般に遅くなる小さな道路は、低次の順序に割り当てられる。高次の順位の付いた道路を表すデータは、これらの順位を用いて、低い順位の付いた道路とは別の1つ又はそれ以上のコレクションに保存される。
【0095】
C.アプレットとプラグインのダウンロード
経路を表すデータと、経路沿い(又は他の位置周辺)の地理的特徴を表す付加的データに加えて、エンドユーザのコンピュータがナビゲーション・サービス・プロバイダから入手可能な他の種類のデータと情報がある。一実施形態によれば、ナビゲーション・サービス・プロバイダは、ナビゲーション・アプリケーションをエンドユーザのコンピュータに送信することができる。ナビゲーション・サービス・サーバがエンドユーザのコンピュータに送信するナビゲーション・アプリケーションは、新たなアプリケーションとすることもできるし、該ナビゲーション・アプリケーションの前のバージョンの更新版とすることもできる。ナビゲーション・サービス・プロバイダが送信するナビゲーション・アプリケーションは、経路案内、地図表示、測位、照会サービス、経路再指定、メモリ管理その他を含むエンドユーザのコンピュータ・プラットフォームで実行されるアプリケーションのいずれかを含むことができる。一実施形態において、これらのナビゲーション・アプリケーションは、アプレットか又はプラグインとして送信される。
図2を再び参照すると、一実施形態において、ナビゲーション・サービス・プロバイダ128は、ナビゲーション・サービス・サーバ120のダウンロード可能な記憶装置802に、ナビゲーション・アプレット(又はプラグイン)800を保管する。次いで、エンドユーザからの要求を受けると、ナビゲーション・サービス・サーバ120は、ナビゲーション・アプレットか又はプラグインをエンドユーザのコンピュータに送信する。アプレット又はプラグインは、エンドユーザのコンピュータで使用できる。アプレット又はプラグインは、エンドユーザのコンピュータにインストールされたブラウザのような別のアプリケーションで使用できる。この実施形態において、エンドユーザは、所望のナビゲーション機能の種類を特定し、次いでナビゲーション・サービス・サーバが、ナビゲーション・アプレット(又はプラグイン)だけでなく該アプレット(又はプラグイン)で使用されることになるデータも送信する。一例として、エンドユーザが、経路案内を入手したいと思っている場合には、ナビゲーション・サービス・サーバは、経路案内アプレットと、経路を示すデータと、経路沿いの地理的特徴を表す付加的データを送信する。経路案内アプレットは、エンドユーザのコンピュータにダウンロードされ、適正にインストールされると、経路案内アプリケーション(図9の420(2))と同様に動作する。このようにして、エンドユーザが望む機能についてのソフトウェアとデータの両方が、ナビゲーション・サービス・プロバイダから提供される。
【0096】
IV.利点
開示したシステムの実施形態から種々の利点が得られる。前述のように、ナビゲーション・システム110は、多くの異なる種類のエンドユーザのコンピュータに対応している。ナビゲーション・サーバが、異なる種類のコンピュータの各々に送信するのに適したデータ形式を判断しなければならない場合には、ナビゲーション・サーバに、相当の負荷がかかる。したがって、ナビゲーション・サーバは、予め計算されたデータ・データの集合を使用し、これによりこのプロセスを容易にする。
【0097】
予め計算されたデータ・データの集合は、ナビゲーション・サーバからエンドユーザのコンピュータで使用するために転送されるデータの最小サイズ単位として扱われるように設計される。予め計算されたデータの集合は、均一なサイズを有していることから、エンドユーザのコンピュータは、これらを容易に管理することができる。
【0098】
ナビゲーション・サービス・サーバで使用される別個の作業データベース(図2の122)と、エンドユーザのコンピュータで使用するためのダウンロード可能な地理データ(図2の124)とを有することから別の利点が得られる。作業データベースは、サーバで使用するのに最適化することができ、ダウンロード可能な地理データ記憶装置に含まれているデータは、エンドユーザのコンピュータで使用するのに最適化することができる。
【0099】
開示された実施形態の別の利点は、予め計算され、ナビゲーション・サービス・プロバイダからエンドユーザに送信されたデータ・データの集合は、接続性を有することが保証できるということである。経路沿いの特徴を表すデータがエンドユーザに送信される時には、エンドユーザが到達できる全ての道路区間が表されることが好ましい。これは、相当量の処理を含むことができる。開示された実施形態のいずれかを用いて、予め計算されたデータ・データの集合が生成されると、表された全ての道路の接続性が保証される。
【0100】
上記の詳細な説明は、限定的なものではなく説明のためのものとみなされることを意図しており、さらに、付属の請求項は、全ての均等物を含むものであり、本発明の範囲を定めることを意図しているということを理解すべきである。
【図面の簡単な説明】
【0101】
【図1】地理データを、地域にわたって位置しているエンドユーザ・コンピュータに送信するナビゲーション・システムのコンポーネントを説明する図である。
【図2】図1のナビゲーション・サービス・プロバイダのコンポーネントを示すブロック図である。
【図3】図1における地域の地図と、この地図を使用した、ナビゲーション・サーバに格納されたダウンロード可能な地理データを系統化するための実施形態についての説明を示す。
【図4】図2に示すダウンロード可能な地理データ記憶装置に格納された、地理データのコレクションの中の幾つかのコンポーネントを示す図である。
【図5】図4に示すダウンロード可能な地理データ記憶装置に格納された、地理データのコレクションの中の1つのコンポーネントを示す図である。
【図6】図4に示すダウンロード可能な地理データ記憶装置に格納された、地理データのコレクションの中の別のコンポーネントを示す図である。
【図7】図4に示すダウンロード可能な地理データ記憶装置に格納された、地理データのコレクションの中の別のコンポーネントを示す図である。
【図8】図4に示すダウンロード可能な地理データ記憶装置に格納された、地理データの付加的なコレクションのコンポーネントを示す図である。
【図9】図1に示すエンドユーザ・コンピュータのうちの1つのコンポーネントを示すブロック図である。
【図10】図1のナビゲーション・サービス・サーバで実行されるプロセスにおけるステップを示すフローチャートである。
【図11】図10に示すプロセスに係るナビゲーション・サービス・サーバからエンドユーザ・コンピュータに送信される経路データのコンポーネントを示すブロック図である。
【図12】図10におけるプロセスの一部を説明するために使用された地図である。
【図13】ナビゲーション・サービス・サーバが図10におけるプロセスを実行した後に、エンドユーザ・コンピュータで実行されるステップのフローチャートである。
【技術分野】
【0001】
本発明は、地域にわたるエンドユーザに、ナビゲーション関連のサービスとデータを提供するシステムに関し、より詳細には、本発明は、中央に設置されたサーバを含み、該サーバは、それに関連した地理データベースを有し、サービス地域にわたって配置されたエンドユーザのコンピュータに、ナビゲーション関連のサービスとデータを提供するようになったシステムに関する。
【背景技術】
【0002】
ナビゲーション・システムは、所望の目的地までの経路を計算し、計算した経路に従って指針を与え、地図を表示すること等のような種々の有用な特徴を提供する。ナビゲーション関連及び地図関連の特徴を配信するナビゲーション・システムのための様々なコンピュータ・アーキテクチャがある。ナビゲーション・システムのためのアーキテクチャの形式の1つは、エンドユーザ(乗物の運転者等)が有するローカル・ナビゲーション・システム装置である。これらのエンドユーザのローカル・ナビゲーション・システム装置は、遠隔配置された地理データベースから地理データを入手する。遠隔配置された地理データベースは、比較的大量の地理データを所有している。遠隔配置された地理データベースに関連するサーバは、エンドユーザのローカル・ナビゲーション・システム装置からのナビゲーション関連又は地図関連データに対する要求を処理する。エンドユーザのローカル・ナビゲーション・システム装置がデータを要求すると、サーバがそれに関連した地理データベースにアクセスして、要求に応えるのに必要なデータを入手し、次いでこのデータを、要求しているエンドユーザのローカル・ナビゲーション・システム装置に送信する。
【0003】
この種のナビゲーション・システム・アーキテクチャは、幾つかの利点を与える。利点の1つは、更新された地理データを提供することに関連する。ナビゲーション・システムで使用する地理データは、継続的に更新される必要がある。例えば、新しい道ができたり、道路工事で道が閉鎖されたり、迂回路が設けられたり、新しい店舗が開店したり、標示されている速度制限が変更されたり、交差点に新しい転回制限が設けられたり、通りの名前が変更されること等がある。この種の変化は、地域を通る移動に影響を及ぼすことがある。したがって、ナビゲーション・システムで使用する地理データは、表示される地理的特徴の変化を正確に反映するために、定期的に更新されるべきである。個々のローカル・ナビゲーション・システム装置が単一の地理データベースから地理データを入手するコンピュータ・アーキテクチャは、地理データを更新することに関する利点を与える。個々のローカル・ナビゲーション・システム装置が、中央サーバに関連した単一の地理データベースからデータを入手するコンピュータ・アーキテクチャでは、更新の必要性は中央データベースにのみ生じる。
【0004】
個々のローカル・ナビゲーション・システム装置が、中央サーバに関連した単一の地理データベースからデータを入手するようになったナビゲーション・システム・アーキテクチャでは、それに関連した利点があるが、さらに考慮すべき事項がある。考慮事項の1つは、エンドユーザが使用する種々の異なるコンピュータ・プラットフォームに、データを提供することに関連する。中央サーバは、様々な異なる種類のエンドユーザ・コンピュータ・プラットフォームに対応していることが好ましい。これらの異なるエンドユーザ・コンピュータ・プラットフォームは、異なる容量のメモリ、異なる処理速度、異なるオペレーティングシステムその他のような異なるリソースを有することがある。これらの異なる種類のエンドユーザ・コンピュータ・プラットフォームの幾つかは、ナビゲーション・アプリケーションを実行する多目的計算装置を含むことがある。他のエンドユーザ・コンピュータ・プラットフォームは、車載ナビゲーション・システムのような専用装置を含むことがある。これらの異なるエンドユーザ・コンピュータ・プラットフォームの幾つかは、音声情報と可視情報の両方をエンドユーザに提供することができるが、他のエンドユーザ・コンピュータ・プラットフォームは、音声のみ又は映像のみを提供する。コンピュータ・プラットフォームの各々が、該プラットフォームのリソースに適した地理データを受信することが好ましい。これは、コンピュータの利用可能なリソースを有意義な方法で利用するために十分なデータを送信するが、該プラットフォームで使用できないデータは送信しないようにすることを含む。
【発明の開示】
【発明が解決しようとする課題】
【0005】
したがって、サーバが、異なる種類のエンドユーザ・コンピュータに対応するために、ナビゲーション関連のサービス及びデータを提供できるようにする、という改良の必要性がある。
【0006】
さらに、データが中央サーバからエンドユーザ・コンピュータに送信されるナビゲーション・システム・アーキテクチャにおいて、データが、サーバとエンドユーザ・コンピュータの両方で効果的に管理されるようにする、という改良の必要性がある。
【課題を解決するための手段】
【0007】
これらの及び他の目的に応えるために、本発明は、ナビゲーション関連のサービスをエンドユーザのコンピュータに提供するためのシステム及び方法からなる。サーバは、ダウンロード可能な地理データを管理し、該データは、該サーバによるサービス地域全体を分割する所定の副区分に対応している予め計算されたデータの集合に系統化される。サーバは、予め計算され選択された地理データのデータの集合をエンドユーザのコンピュータに送信することで、ナビゲーション・サービスとデータに対する要求に応える。エンドユーザのコンピュータの各々は、サーバから受信したデータの集合を、メモリ・キャッシュに保存する。エンドユーザのコンピュータは、データの集合の中のデータを使用して、ナビゲーション関連の特徴を局所的に提供する。
【発明を実施するための最良の形態】
【0008】
I.分散型ナビゲーション・システムの概要
図1は、地域100を示す。地域100は、大都市地域又は農村地域、州、国又はこれらの組み合わせ、或いは他の類似の規模の地域のいずれかに対応させることができる。この地域100には、道路網104がある。
【0009】
ナビゲーション・システム110が、この地域100内のエンドユーザ(例えば、乗り物の運転者及び乗客並びにその他の者)にサービスを提供する。このナビゲーション・システム110は、地域100についてのナビゲーション関連のサービスと地図関連のサービスを得るために、エンドユーザによって使用される。ナビゲーション関連のサービスと地図関連のサービスは、経路計算及び案内、個人及び企業検索サービス(例えばエレクトロニック・イエロー及びホワイトページズ)、地図、関心のある地点の検索、目的地選択その他を含む道路網104沿いの移動に関する情報を含む。
【0010】
ナビゲーション・システム110は、ハードウェアとソフトウェアとデータとの組み合わせである。ナビゲーション・システム110は、遠隔コンポーネント(例えば、エンドユーザから離れた中心位置にあるハードウェア、ソフトウェア又はデータ)と局所的コンポーネント(例えば、物理的に各エンドユーザと共に位置するハードウェア、ソフトウェア又はデータ)を含む。
【0011】
ナビゲーション・システム110の遠隔コンポーネントの中には、ナビゲーション・サービス・サーバ120が含まれる。ナビゲーション・サービス・サーバ120に関連するのは、作業地理データベース122と、ダウンロード可能な地理データ記憶装置(すなわち保存庫)124である。ナビゲーション・サービス・サーバ120と、作業地理データベース122と、ダウンロード可能な地理データ記憶装置124は、ナビゲーション・サービス・プロバイダ128により管理され、動作される。
【0012】
ナビゲーション・システム110の局所的コンポーネントには、エンドユーザにより、ナビゲーション関連及び地図関連の特徴と地理データをナビゲーション・サービス・プロバイダ128に要求して入手するように作動される、様々なコンピュータ・プラットフォーム130が含まれる。これらの様々なコンピュータ・プラットフォーム130(「エンドユーザ・コンピュータ」又は「顧客のコンピュータ」とも呼ばれる)は、データ・ネットワーク170を介してナビゲーション・サービス・プロバイダ128にアクセスするのに適したハードウェアとソフトウェアを有し、乗物134、パーソナルコンピュータ140、個人用整理手帳(例えばPDA、PalmPilot(登録商標)型の装置)150、携帯電話160、又は他の種類の計算装置に搭載されたナビゲーション・システム装置132を含むことができる。
【0013】
データ・ネットワーク170は、現在利用可能な適当な技術及び/又はプロトコル、並びに将来利用可能となる技術及び/又はプロトコルのいずれをも使用することができる。例えば、データ・ネットワークは、WAP、TCP/IPその他を使用することができる。データ・ネットワーク170には、適当な変換により、1つより多いプロトコルを使用することができる。
【0014】
データ・ネットワーク170は、インターネットの一部とすることもできるし、インターネットに接続できるようにすることもできる。
【0015】
ネットワーク170は、無線部分172を含むことができる。データ・ネットワーク170の無線部分172は、エンドユーザのモバイル・コンピュータ130とサービスプロバイダ128との間で双方向通信できるようにする。無線部分172は、セルラー方式、PCS、衛星、FM、無線、又は将来開発されることとなる技術の適当な形式で実行することができる。無線部分172は、トランスポンダ塔、アンテナ塔、FM塔、衛星その他適当な手段のような1つ又はそれ以上の送波器174を含むことができる。送波器174は、ネットワーク170及び/又はサービスプロバイダ128との適当な通信リンク176を有する。このリンク176は、地上回線とすることもできるし、無線とすることもできる。送波器174は、サービスプロバイダ128とエンドユーザのモバイル・コンピュータ130との間で双方向通信できるようにする適当な技術を含む。
【0016】
図1のナビゲーション・システム110における特徴の1つは、異なる形式のエンドユーザ・コンピュータ130に対応しているということである。図1のナビゲーション・システム110は、異なる形式のコンピュータ130を有するエンドユーザが、ナビゲーション・サービス・プロバイダ128からナビゲーション・サービスを受け、該ナビゲーション・サービス・プロバイダ128から地理データを入手して使用することができるようにする。
【0017】
II.ナビゲーション・サービス・サーバ
A.概要
図2は、ナビゲーション・サービス・プロバイダ128のコンポーネントの幾つかを示すブロック図である。ナビゲーション・サービス・プロバイダ128のナビゲーション・サービス・サーバ120には、サーバ・アプリケーション200が含まれる。サーバ・アプリケーション200の1つは、加入者用サービス・アプリケーション204である。ナビゲーション・サービス・プロバイダ128により提供される他のサービスの幾つか又は全てを使用するためには、エンドユーザが加入者になることが必要とされる。加入者用サービス・アプリケーション204は、この機能に対応するサービスを提供する。加入者用サービスの幾つかは、登録、支払い、更新、加入者身分確認、対象広告その他を含む。加入者用サービス・アプリケーション204は、様々な加入者に関する様々な種類の情報を保有している加入者データベース208を管理し、使用する。
【0018】
サーバ・アプリケーション200のその他には、通信用アプリケーション212がある。通信用アプリケーション212は、エンドユーザとメッセージを送受信するために、データ・ネットワーク(図1の170)とインターフェースしている。通信用アプリケーション212はまた、エンドユーザとの通信セッションを維持管理する。
【0019】
サーバ・アプリケーション200には、ナビゲーション関連アプリケーション216が含まれる。ナビゲーション関連アプリケーション216は、様々な異なる種類のナビゲーション関連のサービスを提供するために、ナビゲーション・サービス・サーバ120に関連する作業地理データベース122を使用する。ナビゲーション関連アプリケーション216の1つは、経路計算アプリケーション220である。出発地と目的地の位置を特定するデータが与えられると、経路計算アプリケーション220は、出発地と目的地との間の経路を計算する。経路計算アプリケーション220は、この目的に合う様々な手段又はアルゴリズムのいずれをも使用することができる。経路を計算する方法は、米国特許第6,192,314号に開示されており、その開示全体を引用によりここに組み入れる。例えば、経路の計算方法は、A*アルゴリズムか又はディクストラ・アルゴリズムのいずれかを含むことができる。(上述の特許に開示されている方法には、経路を計算することができる方法のうちの幾つかのみしか記載されていないが、ここで特許請求される内容は、特定の経路計算方法のいずれにも限定されるものではない。既知の又は将来開発されることとなる好適な経路計算方法のいずれも使用することができる。)
【0020】
使用する方法に関係なく、経路計算アプリケーション220は、出発地と目的地との間の合法的解答経路を形成する連続する一続きの道(又はこれらの区分)を特定する、リストの形態の出力を与える。「合法的解答経路」は、一方通行路、転回制限その他のような確認されている交通規制に従う。経路計算アプリケーション220で用いられる方法は、解答経路が1つ又はそれ以上の所定の基準を満たすよう最適化されるように設計することができる。このような基準は、最短移動時間、最短距離、最少回数の転回その他を含むことができる。経路計算アプリケーション220で用いられる方法が、1つ又はそれ以上の基準のために最適化された解答経路を見つけるように設計される場合には、解答経路も、理想的にはこれらの1つ又はそれ以上の基準を満たす。
【0021】
ナビゲーション関連アプリケーション216のその他には、企業及び個人検索アプリケーション224がある。企業及び個人検索アプリケーション224は、イエロー及びホワイトページ形式の機能を含む。企業及び個人検索アプリケーション224は、特定の企業又は個人の位置或いは住所を見つけるか、或いは特定の企業又は個人についての他の情報を見つける。企業及び個人検索アプリケーション224はまた、種々の基準に基づいて、企業又は個人のカテゴリの位置又は住所を検索することも提供する。例えば、企業及び個人検索アプリケーション224は、特定の位置(例えばエンドユーザの位置)から特定の距離内(例えば5マイル)の、特定のエスニック風(例えば中華)又はチェーン店(例えばマクドナルド)の飲食店の全てを検索することを提供する。企業及び個人検索アプリケーション224は、エンドユーザが、目的地として使用可能な関心のある企業、個人又は地点を見つけるのを支援することができ、次いで、経路計算アプリケーション220が、そこまでの解答経路を求めることができる。
【0022】
ナビゲーション関連の特徴を提供するために、経路計算アプリケーション220と検索アプリケーション224は、作業地理データベース122からのデータを使用する。作業地理データベース122は、地域(図1の100)の道路と交差点を表すデータを含み、さらに、交差点での転回制限、道路沿いの速度制限、様々な道路の通りの名前、道路沿いの住所範囲その他のような表された道路と交差点に関する情報も含んでいる。作業地理データベース122はまた、関心のある地点と企業についての情報とその他の情報も保有している。作業地理データベース122は、ナビゲーション関連機能の実行を容易にするために系統化することができる。ある種のナビゲーション関連機能の性能を向上させるため地理データベースを系統化する方法は、米国特許第5,974,419号と、米国特許第5,968,109号と、米国特許第5,953,722号に記載されており、その開示全体を引用によりここに組み入れる。
【0023】
ナビゲーション・サービス・サーバ120におけるナビゲーション関連アプリケーション216のその他は、地理データ提供アプリケーション228である。
地理データ提供アプリケーション228は、地理データをエンドユーザのコンピュータ130にダウンロードするのを管理する。ナビゲーション・システム(図1の110)の一実施形態によれば、ある種のナビゲーション関連機能は、ナビゲーション・サービス・サーバ120上で遠隔的にエンドユーザに向けて実行され、他のナビゲーション関連機能は、エンドユーザ・コンピュータ130上で局所的にエンドユーザに向けて実行される。例えば、一実施形態によれば、経路計算は、最新の交通情報を利用するために、ナビゲーション・サービス・サーバ120上で実行される。経路案内は、各エンドユーザが好む方法で情報を与え、各エンドユーザのコンピュータ130の各々のリソースに対応させるために、各エンドユーザのコンピュータ130上で局所的に実行される。
【0024】
エンドユーザのコンピュータ上のナビゲーション・アプリケーションは、該エンドユーザのコンピュータ上で局所的にある種のナビゲーション関連機能を実行するために、地理データを要求することができる。この実施形態において、エンドユーザのコンピュータの各々は、ある種のナビゲーション関連機能を局所的に実行するのに必要な地理データを、ナビゲーション・サービス・サーバ120から入手する。ナビゲーション・サービス・サーバ120がエンドユーザのコンピュータ130に送信するデータは、ダウンロード可能な地理データ記憶装置124から入手される。ナビゲーション・サーバ120の地理データ提供アプリケーション228は、ダウンロード可能な地理データ記憶装置124からエンドユーザのコンピュータ130までの、地理データの供給を管理する。
【0025】
地理データ提供アプリケーション228は、幾つかの機能を実行する。地理データ提供アプリケーション228が実行する機能の1つは、ダウンロード可能な地理データ記憶装置124からエンドユーザのコンピュータに送信するのに適したデータを決定することである。この決定は、幾つかの要素を考慮に入れることができる。一実施形態によれば、エンドユーザのコンピュータは、地理データのコレクションを特定する。
ナビゲーション・サービス・プロバイダ128は、ダウンロード可能な地理データ記憶装置124の中で、地理データの異なるコレクション232を保管することができる。個々のコレクション232の各々は、全地域(図1の100)の個々の表示である。これらの異なるコレクション232の構成は、後でより詳細に説明する。地理データのコレクション232からどのデータを送信するかが決定されると、地理データ提供アプリケーション228が、後でより詳細に説明するように、コレクション232から特定のデータ部分を選択し、選択されたデータ部分をエンドユーザのコンピュータに送信する。
【0026】
別の実施形態によれば、地理データ提供アプリケーション228は、加入者データベース208を参照することで、特定のエンドユーザに送信するデータを選択するのに適した地理データのコレクション232を決定することができる。加入者データベース208は、各エンドユーザに送信するデータが選択される地理データのコレクションを識別する情報を、管理することができる。さらに別の実施形態によれば、地理データ提供アプリケーション228は、その他の手段により特定のエンドユーザに送信するデータを選択するのに適した地理データのコレクションを決定することができる。
【0027】
ダウンロード可能な地理データ記憶装置124から、エンドユーザのコンピュータに送信する地理データが選択されるコレクション232を決定した後に、送信する地理データの特定部分が選択される。この機能を実行するために、地理データ提供アプリケーション228は、(1)エンドユーザのコンピュータの位置と、(2)エンドユーザのプラットフォームがどこへ行くのかということと、(3)他の要素と、を考慮に入れる。エンドユーザが、経路計算アプリケーション220により計算された経路に追従する場合には、地理データ提供アプリケーション228が、この経路沿いの区域を表すデータを選択する。経路沿いの区域は、「進路要図」と呼ぶことができる。進路要図の尺度は、地理データ提供アプリケーション228によって決定される。この決定は、エンドユーザによる進路要図の尺度の指定を考慮に入れることができる。或いは、地理データ提供アプリケーション228が、エンドユーザの好みやコンピュータ・プラットフォームのリソースに関する保存された情報に基づいて、適した進路要図の尺度を決定することができる。この保存された情報は、加入者データベース208で管理される。
【0028】
B.ダウンロード可能な地理データ
上述のように、地理データ提供アプリケーション228は、どのデータをエンドユーザのコンピュータ130に送信するかを決定する。地理データ提供アプリケーション228がエンドユーザのコンピュータに送信するデータは、ナビゲーション・サービス・サーバ120で管理されるダウンロード可能な地理データ記憶装置124から入手する。ナビゲーション・サービス・サーバ120からエンドユーザのコンピュータ130にデータをダウンロードするのを容易にするために、該データは、1つ又はそれ以上の所定のコレクション232に系統化される。さらに、ダウンロード可能な地理データ記憶装置124の中のデータのコレクション232の各々は、複数のグループ分け(すなわち「データの集合」)に系統化される。一実施形態において、各データの集合に格納されるデータは、空間的に決定されるものであり、すなわち、地理的特徴を表す各データの集合の中のデータは、互いに近接するものである。より具体的には、各データの集合に格納されるデータは、表された全地域(図1の100)を分割する複数の別個の地理的区分のうちの別個の区別されるものが所有している地理的特徴を表す。
【0029】
上述のように、この実施形態によれば、ダウンロード可能な地理データ記憶装置124は、種々の異なるコレクション232を含む。これらのコレクション232の各々は、全地域100の別個の表示からなる。これらのコレクション232の各々は、複数のデータの集合に系統化される。
【0030】
図3及び図4は、ダウンロード可能な地理データ記憶装置124のコレクション232の各々に格納されるデータが、一実施形態によってどのように系統化されるのかを示している。図3は、図1に既に示されている地域100の地図300を示す。図3では、地域100を表す地図300にグリッド304が重ね合わされている。グリッド304は、グリッド線308で構成されている。グリッド線308は、表された地域100を複数の区域312に分割する。この実施形態において、区域312は長方形であるが、しかしながら、別の実施形態において区域312を別の形状にすることもできる。グリッド304のグリッド線308は、区域312の境界を表す。これらの区域312は、図3に示すように異なる大きさにすることができる。或いは、区域312は、全て同じ大きさにすることもできる。区域312の大きさ、及び、該区域312の大きさが全て同じかどうかということは、これらの地理的区分に含まれている地理的特徴を表すデータをデータの集合に系統化するのに用いる手順により定まる。同様に、区域312の境界の位置は、これらの地理的区分に含まれている地理的特徴を表すデータをデータの集合に系統化するのに用いる手順により定まる。データの集合を生成するため区域の境界を決定する方法は、米国特許第5,974,419号に記載されており、その開示全体を引用によりここに組み入れる。
【0031】
各データの集合312の生成において、別個の区域312の各々に含まれている地理的特徴を表す個々のデータ・レコード336は、データの別個のデータの集合320(又はグループ分け)に一緒に集められる。すなわち、(各コレクション232の)データのデータの集合320の各々は、対応する地理的区分312に含まれている地理的特徴を表す全てのデータ・レコード336を含んでいる。したがって、(コレクション232の全てのデータの集合320に対応している)全ての地理的区分312は、地域全体100を構成する。すなわち、データのデータの集合320の各々は、道路、交差点、関心のある地点及び該データの集合に対応する地理的区分312内にある他の特徴を表す、複数のデータ・レコード336を含むことができる。
【0032】
一実施形態によれば、各コレクション232内の全てのデータの集合320は、均一なデータの集合・サイズを有する。例えば、データのデータの集合320の各々は、1K、2K、4K、8K、16K、32Kその他のサイズを有することができる。
コレクション232の各々のデータの集合・サイズは、データを使用することになるエンドユーザのコンピュータのメモリ・リソースを含む幾つかの要素に基づいて決定することができる。この実施形態によれば、1つのコレクション232のデータの集合320は、別のコレクション232のデータの集合320と異なるサイズにすることができる。例えば、1つのコレクション232は、サイズが32Kのデータの集合を有することができ、その一方で、別のコレクション232は、サイズが16Kのデータの集合を有することができる。
【0033】
図3及び図4に示すように、コレクション232の各々は、複数のデータの集合320を含むことができる。コレクション232のデータの集合320の各々は、全地域100内に位置する地理的区分312の別個の1つに対応する。ダウンロード可能なデータ記憶装置124において、コレクション232の各々と該コレクション232のデータの集合320の各々は、予め計算されている。言い換えれば、各コレクション232の決定及び生成と、各コレクション232を構成する全てのデータの集合320の決定及び生成は、ダウンロード可能なデータ記憶装置124のデータのいずれかが、エンドユーザのコンピュータ130のいずれかにダウンロードできるようになる前に行われる。これにより、どのデータをエンドユーザに送信するかの決定が容易になる。エンドユーザが、彼又は彼女のコンピュータで局所的に使用するためにデータを要求する時には、ナビゲーション・サービス・サーバ120が、どの特定のデータ・レコードを該エンドユーザが必要とし、これらのデータ・レコードを該エンドユーザに送信するかを判断する必要はない。代わりに、ナビゲーション・サービス・サーバ120は、どの地理的区分312がエンドユーザに要求され、これらの地理的区分312における全ての地理的特徴を表すデータを含んでいる全てのデータの集合320をエンドユーザに送信するかを判断する。エンドユーザに送信されるデータの集合320は、地域を表す全てのデータのクリップ又はスライスを表す。これらのデータの集合320は、エンドユーザに必要とされる個々のデータ・レコードの全てを含んでいる。この系統化と処理は、ナビゲーション・サービス・サーバ120での演算を容易にする。ナビゲーション・サービス・サーバ120における地理データ提供アプリケーション228は、エンドユーザがデータの集合に対応する定義された地理的区分312に対応するいずれかのデータを必要としているかどうかを判断し、必要としている場合には、地理的区分312に対応するデータの集合の全部をエンドユーザに送信する。この系統化と処理はまた、後でより詳細に説明するようなメモリ・リソースを管理する方法を与えることで、エンドユーザのコンピュータでの演算を容易にする。
【0034】
後で説明するのを除いて、ダウンロード可能なデータ記憶装置124からエンドユーザのコンピュータにデータがダウンロードされる時に、該データは、全てのデータの集合にダウンロードされる。これは、地理的区分312の各々に含まれている地理的特徴を表す全てのデータ・レコード336は、グループとして一緒にアクセスされるということを意味する。したがって、データの集合320は、エンドユーザのコンピュータで使用するため同時にダウンロードされたデータ・レコードの量を表す。データのデータの集合がエンドユーザのコンピュータに送信されると、該データの集合のデータ・レコードは全て、該エンドユーザのコンピュータで利用可能である。一実施形態において、データの集合の中の全てのデータ・レコードは、エンドユーザのコンピュータ・システムのメモリに同時に保管される。
【0035】
C.異なる種類のデータの集合
前述のように、ダウンロード可能な地理データ記憶装置124は、地理データの異なるコレクション232を含む。これらの異なるコレクション232は、全て同じ地域(図1の100)を表すが、異なる形式のデータ(すなわち別に系統化されたデータ)を含むことができる。これらの異なるデータのコレクション232は全て、前述のようにデータの集合に系統化される。前述のように、コレクションの中のデータの集合232は、均一なデータの集合・サイズに合わせることが好ましい。しかしながら、1つのコレクション232の中のデータの集合の均一サイズは、別のコレクション232の中のデータの集合の均一サイズと異なっていてもよい。コレクション232の幾つかのコンテンツについて、次に説明する。
【0036】
(1)ダウンロード可能な地理データの第1コレクション
図5は、コレクション232(1)の1つの中の地理データ336のデータの集合320の1つの中のコンテンツを説明するのに使用する概略図である。データの集合320の中のデータ336は、地理的区分312(1)の1つに対応する。この実施形態において、データの集合320は、地理的区分312(1)に含まれている全ての特徴を表す全てのデータ336を含んでいる。一例として、データの集合320は、該データの集合320に対応する地理的区分312(1)にある全ての道路を表すデータを含んでいる。各道路は、一続きの連結された区間として表され、該区間は、道路沿いの隣接する交差点の間の道路区間か又は交差点と道路の行き止まり位置との間の道路区間に対応する。この実施形態において、各道路区間は、別個のデータ・エンティティ(又はデータ・レコード)で表される。道路区間を表す各データ・レコードは、該道路区間の速度制限(又は速度圏)、該道路区間の機能的分類(すなわちランク)、該道路区間沿いの車線の数その他のような表示された道路区間についてのデータを含む(又は示す)。
【0037】
道路区間を表すデータ・レコードはまた、道路区間の位置を示すデータも含んでいる。一実施形態において、この情報は、道路区間の終点を表すノード・レコードの記述を含む。ノード・レコードに関連するのは、道路区間の終点(すなわちノード)の位置(例えば緯度、経度、及び必要であれば高度)を示すデータである。直線ではない道路区間については、道路区間の形状を示すために付加的なデータが含まれる。一実施形態において、この目的のために形状ポイントデータが使用される。形状ポイントは、道路区間の終点の間の該道路区間沿いの地点の位置(例えば緯度、経度、及び必要であれば高度)を特定する。1つ又はそれ以上の形状ポイントを使用することで、直線以外の道路区間の形状を表すことができる。
【0038】
道路区間を表すレコードはまた、道路区間の1つ又はそれ以上の名前を示すデータも含んでいる。一実施形態において、この情報は、1つ又はそれ以上の名前レコードの記述を含む。この実施形態において、道路の名前レコードと他の名前の付いた地理的特徴は、同じデータの集合に含まれる。
【0039】
図5に示す実施形態において、データの集合320はまた、関心のある地点のデータも含んでいる。関心のある地点のデータは、関心のある地点に関する情報を含んでいる。関心のある地点は、企業、公共施設その他を含む。関心のある地点のデータは、名前、種類(例えば、ホテル、飲食店、チェーン店、博物館、警察署その他)、住所、電話番号その他のような表示された関心のある地点に関する情報を含む。この実施形態において、地理的区分に含まれている関心のある地点のデータ・レコードは、道路区間データと、ノード・データと、名前データと共に、同じデータ・データの集合に含まれる。
【0040】
図5のデータ・コレクション232(1)では、全てのデータの集合が16Kのサイズである(しかし、他のどのデータサイズを使用することもできる)。図6は、別のデータ・コレクション232(2)を示す。図6において、コレクション232(2)は、同じ種類のデータ、例えば道路区間レコード、ノード・レコード、名前レコード、関心のある地点レコードその他を含むデータの集合320に分割される。しかしながら、図6のコレクション232(2)を生成するデータの集合320は、図5のコレクション232(1)の中のデータの集合と異なるサイズを有する。図6のコレクション232(2)の中のデータの集合は、それぞれ32Kのサイズである。図6のデータの集合320の各々は、図5のデータの集合の各々より多くデータが含まれているので、各データの集合は、より広い地理的区分を表すことができる。したがって、図6に示すように、データの集合320に対応する地理的区分312(2)は、図5のデータの集合320に対応する地理的区分312(1)より寸法が大きい。
【0041】
図7は、別のデータ・コレクション232(3)を示す。図7に示すデータのコレクション232(3)は、図5及び図6に示すそれぞれコレクション232(1)及び232(2)のように、同じ種類のデータ、例えば、道路区間レコード、ノード・レコード、名前レコード、関心のある地点レコードその他を含む。
さらに、図7のデータ・コレクション232(3)の中の各データの集合は、発音データも含んでいる。発音データは、表示された地理的区分における地理的特徴及び/又は関心のある地点の名前に対応している。発音データは、エンドユーザのコンピュータ130の適当なハードウェア及びソフトウェアを使用してこれらの名前を聞き取り可能に再生できるように、データの集合320の中に、表された地理的区分における地理的特徴及び/又は関心のある地点の名前に対応する音声表現を含んでいる。図7のデータ・コレクション232(3)において、各データの集合320は64Kのデータを含んでいるが、他のデータサイズを使用することもできる。
【0042】
図8は、さらに3つのデータ・コレクション232(4)(1)、232(4)(2)、及び232(4)(3)を示す。この実施形態において、コレクション232(4)(1)、232(4)(2)、及び232(4)(3)の各々は、幾つかの種類(又は属性)のデータのみを含んでいる。例えば、コレクション232(4)(1)は、経路データ、例えば区間レコードとノード・レコードのみを含む。コレクション232(4)(2)は、名前レコードのみを含む。コレクション232(4)(3)は、関心のある地点レコードのみを含む。これらのコレクション232(4)(1)、232(4)(2)、及び232(4)(3)の各々は、別個の地理的区分312の各々に対応している別個のデータの集合320に系統化される。したがって、コレクション232(4)(1)のデータの集合320は、地理的区分312(4)における道路と交差点を表す区間レコードとノード・レコードを含む。コレクション232(4)(2)は、地理的区分312(4)における地理的特徴及び/又は関心のある地点の名前を表す名前レコードを含む。コレクション232(4)(3)は、地理的区分312(4)における関心のある地点の位置を表す関心のある地点レコードを含む。図8のデータ・コレクション232(4)(1)、232(4)(2)、及び232(4)(3)において、各データの集合320は、16Kのデータを含む(しかし、他の均一なデータサイズを使用することもできる)。
【0043】
図5から図8までに示されている異なるデータ・コレクションの実施形態は、ナビゲーション・サービス・サーバ120上のダウンロード可能な地理データ記憶装置(図2の124)に保管できるデータ・コレクションの幾つかの異なる形式のみを表している。ダウンロード可能な地理データ記憶装置124は、異なるサイズのデータの集合を保有するデータのコレクションを含むことができる。さらに、ダウンロード可能な地理データ記憶装置124は、互いに別々に系統化されたデータの集合を保有するデータ・コレクションを含むことができる。例えば、ダウンロード可能な地理データ記憶装置124は、アルファベット順に又は行政体系(例えば市、郡、州及び国)により系統化されたデータのデータの集合を保有するコレクションを含むことができる。
【0044】
III.エンドユーザのコンピュータ
A.概要
前述のように、各エンドユーザは、コンピュータ(図1の130)を使用して、ナビゲーション・サービス・サーバ120からデータを入手する。また、前述のように、ナビゲーション・サービス・サーバ120から入手したデータを用いて、エンドユーザのコンピュータ上で幾つかのナビゲーション関連機能が局所的に実行される。異なるエンドユーザのコンピュータは、異なるハードウェアとソフトウェアを有するので、エンドユーザのコンピュータ上で実行されるナビゲーション関連機能は、該エンドユーザのプラットフォーム毎に変化させることができる。したがって、次のセクションでは、エンドユーザのコンピュータの構成について説明する。全てのエンドユーザのコンピュータが、必ず後述の全ての機能を提供するとは限らず、また、幾つかのエンドユーザ・コンピュータは、付加的な又は他の機能を提供することができる、ということについて理解されたい。
【0045】
異なるエンドユーザのコンピュータは、異なるハードウェア及びソフトウェア・リソースを有していても良いが、全てのエンドユーザ・コンピュータは、ナビゲーション・サービス・サーバ(図1の120)からデータを受信する。エンドユーザ・コンピュータの幾つか又は全ては、ナビゲーション・サービス・サーバ120上のダウンロード可能な地理データ記憶装置124から地理データを受信する。ダウンロード可能な地理データ記憶装置124から地理データを受信するエンドユーザ・コンピュータ130は、後述のメモリ管理特徴を用いて、ナビゲーション・サービス・サーバ120から入手したデータのデータの集合を処理することができる。
【0046】
B.エンドユーザのコンピュータのコンポーネント
図9は、エンドユーザのコンピュータ130の1つにおけるコンポーネントの幾つかのブロック図である。エンドユーザのコンピュータ130は、通信システム400を含む。エンドユーザのコンピュータ130における通信システム400は、データ・ネットワーク170を介してナビゲーション・サーバ(図1の120)との間でメッセージを送受信するのに必要とされるハードウェアとソフトウェア・コンポーネントを含む。通信システム400は、エンドユーザのコンピュータ130における他のコンポーネントとインターフェースする。
【0047】
エンドユーザのコンピュータ130はまた、ユーザ・インターフェース410も含んでいる。ユーザ・インターフェース410は、エンドユーザが、エンドユーザのコンピュータ130に情報を入力し、該エンドユーザのコンピュータ130から情報を受け取ることができるようにする。ユーザ・インターフェース410は、ハードウェアとソフトウェア・コンポーネントを含んでいる。例えば、ユーザ・インターフェース410は、ディスプレイ、マイクロホン、スピーカ、キーパッド、又は情報をコンピュータに入力し、そこから情報を出力するための他の種類の手段を含むことができる。ユーザ・インターフェース410は、メニュー、プロンプト、音声その他を提供することができる支援ソフトウェアを含む。ユーザ・インターフェース410は、エンドユーザのコンピュータ130における他のコンポーネントとインターフェースする。
【0048】
エンドユーザのコンピュータ130には、ナビゲーション関連アプリケーション420が含まれる。ナビゲーション関連アプリケーション420は、ナビゲーション・サーバ120から入手した地理データを使用して、様々な異なる種類のナビゲーション関連のサービスを提供する。ナビゲーション関連アプリケーション420の1つは、測位アプリケーション420(1)である。測位アプリケーション420(1)は、ナビゲーション・サーバ120から入手した地理データを使用して、道路網を表すデータに対するエンドユーザのコンピュータ130の位置を求める。測位アプリケーション420(1)はまた、エンドユーザのコンピュータ130の一部である測位システム430からデータを入手することもできる。測位システム430は、GPS、推測航法、或いはこれらの又は他の技術の組み合わせを使用して、エンドユーザのコンピュータ130の位置を求めることができる。測位を行う方法は、米国特許第6,192,312号に開示されており、その開示全体を引用によりここに組み入れる。
測位アプリケーション420(1)は、必要であれば、すなわち、全てではないエンドユーザのコンピュータは、測位を提供するか又は測位を支援することができる。
【0049】
エンドユーザのコンピュータにおけるナビゲーション・アプリケーション420のその他には、経路案内420(2)がある。経路案内アプリケーション420(2)は、ナビゲーション・サーバ120からのデータを使用して、エンドユーザに所望の目的地まで移動するための指示を与える。
【0050】
地理データを使用して経路案内を行う方法は、米国特許第6,199,013号に記載されており、その開示全体を引用によりここに組み入れる。
【0051】
エンドユーザのコンピュータにおけるナビゲーション・アプリケーション420のその他には、地図表示420(3)がある。地図表示420(3)は、ナビゲーション・サービス・サーバ120からのデータを使用して、エンドユーザのコンピュータにおけるユーザ・インターフェース410の表示画面に写実的な地図を提供する。この地図は、エンドユーザのコンピュータの位置周辺の区分、エンドユーザが追従する経路沿いの区分、エンドユーザにより指定された位置周辺の区分、又はその他指定された区分を示すことができる。地理データを使用して画面表示を行う方法は、米国特許第6,092,076号と米国特許第6,163,749号に開示されており、その開示全体を引用によりここに組み入れる。
【0052】
エンドユーザのコンピュータ上のナビゲーション・アプリケーション420のその他には、経路再指定アプリケーション420(4)がある。経路再指定アプリケーション420(4)は、エンドユーザが目的地までの経路から逸脱した時に、該エンドユーザが追従できるように案内を受けるために使用される。経路再指定アプリケーション420(4)は、ナビゲーション・サーバ120からのデータを使用して、目的地までの新たな経路か又は元の経路に引き返す経路を計算する。経路再計算アプリケーション420(4)は、米国特許第6,129,314号に記載されているのと同じ方法を使用して経路計算を行うことができ、その開示全体を引用によりここに組み入れる。
【0053】
エンドユーザのコンピュータ上のナビゲーション・アプリケーション420のその他には、照会アプリケーション420(5)がある。照会アプリケーション420(5)は、ナビゲーション・サービス・サーバ120のナビゲーション・アプリケーション(図2の216)への照会(すなわち情報の要求)を生成するのに使用される。照会は、経路計算アプリケーション220を使用して経路を計算するための要求とすることもできるし、検索サービス224又はナビゲーション・サービス・サーバ120により提供されたその他のサービス又はアプリケーションを使用した企業、個人、又は関心のある地点に関する情報の要求とすることもできる。照会アプリケーション420(5)は、ナビゲーション・サービス・サーバ120にメッセージを送信し、応答を待ち、応答を受信し、次いで要求したデータを局所的に、例えばローカル・アプリケーション420で使用することを管理する。
【0054】
エンドユーザのコンピュータ上のナビゲーション・アプリケーション420のその他には、関心のある地点の参照アプリケーション420(6)がある。関心のある地点の参照アプリケーション420(6)は、関心のある地点の参照(すなわち検索)を使用する。関心のある地点を説明するデータは、ナビゲーション・サービス・サーバ120に、又は局所的に保存される。
【0055】
C.エンドユーザのコンピュータのメモリ管理機能
エンドユーザのコンピュータ130は、メモリ管理アプリケーション500を含む。メモリ管理アプリケーション500は、エンドユーザのコンピュータ130のメモリ・リソースを管理する。メモリ管理アプリケーション500により実行される機能には、ナビゲーション・サーバ120から受信した地理データの管理がある。この機能の一部として、メモリ管理アプリケーション500は、ナビゲーション・サービス・サーバ120のダウンロード可能な地理データ記憶装置124からエンドユーザのコンピュータで受信した地理データのデータの集合320を管理する。地理データのデータの集合をメモリで管理する方法は、米国特許第6,073,076号と米国特許第6,047,280号に開示されており、その開示全体を引用によりここに組み入れる。
【0056】
図9を参照すると、メモリ管理アプリケーション500は、ナビゲーション関連アプリケーション420で使用するためエンドユーザのコンピュータ130のメモリ506の一部504を予約し、さらに、データの集合のキャッシュ520として使用するため別の部分514を予約する。メモリ管理アプリケーション500は、エンドユーザのコンピュータ130の初期化の時に又はこの後のいつでも、これらの部分504及び514のサイズを決定することができる。この決定は、インストールした利用可能なメモリの全容量を考慮に入れることができる。さらに、メモリ管理アプリケーション500は、メモリ506の再割当て可能な部分528を決定することができる。この再割当て可能な部分528の幾つか又は全ては、ナビゲーション・アプリケーション420のために使用したり、データの集合のキャッシュ520のために使用したりすることができる。再割当て可能な部分528の使用は、エンドユーザのコンピュータ130の実行時に、メモリ管理アプリケーション500により、エンドユーザの要求に基づいて決定される。
【0057】
エンドユーザのコンピュータ130の動作中に、該エンドユーザのコンピュータ130におけるナビゲーション関連アプリケーション420は、ナビゲーション・サービス・サーバ120からダウンロードしたデータの集合320に含まれているデータを使用する。エンドユーザのコンピュータ130の性能を向上させるために、エンドユーザのコンピュータ130のメモリ506の中にキャッシュ520が設けられる。キャッシュ520は特に、ナビゲーション・サービス・サーバ120からダウンロードした多くの地理データのデータの集合320を保存するのに使用される。キャッシュ520に地理データのデータの集合を保存することにより、多くのデータの集合を使える状態でメモリに保管することにより、エンドユーザのコンピュータ130におけるナビゲーション関連アプリケーション420を支援する。データの集合を使える状態でメモリに保有することは、ナビゲーション・サービス・サーバ120からデータの集合を入手することに関連する比較的大きい遅延が回避される。データの集合のキャッシュ520はまた、ナビゲーション機能がすぐに必要とすると予測される地理データのデータの集合を保存するために使用することもできる。前述のように、データの集合のキャッシュ520の構成と動作は、メモリ管理アプリケーション500により実行される。
【0058】
データの集合のキャッシュのサイズは、種々の要素に基づいている。データの集合のキャッシュのサイズに影響を及ぼす要素の1つは、データの集合のサイズである。データの集合のサイズに対するデータの集合のキャッシュのサイズにより、データの集合のキャッシュにどの位のデータの集合を確保できるかが決まる。上述のように、幾つかの実施形態において、データの集合は、ナビゲーション・サービス・サーバ120のダウンロード可能な地理データ記憶装置124に、標準サイズ例えば2K、4K、8K、16K、32Kその他で保存される。したがって、エンドユーザのコンピュータのデータの集合のキャッシュ520のサイズにより、局所的に保存可能なデータの集合の数が定められる。例えば、384Kのデータの集合のキャッシュは、サイズがそれぞれ16Kのデータの集合を最大24個保存できる。同様に、より大きいサイズのデータの集合をより少なく保存することもできるし、これに対して、より小さいサイズのデータの集合をより多く保存することもできる。一実施形態において、データの集合のキャッシュ520は、全て同じサイズのデータの集合を保有するのに使用され、或いは別の実施形態において、データの集合のキャッシュ520は種々のサイズのデータの集合を保有することができる。
【0059】
データの集合のキャッシュのサイズに影響を及ぼす別の要素は、エンドユーザのコンピュータ130の利用可能な全てのメモリ・リソースである。制限されたメモリ・リソースのコンピュータは、データの集合のキャッシュに比較的小さい部分しか提供しないが、これに対して、大きいメモリ・リソースを有するコンピュータは、比較的多くのメモリをデータの集合のキャッシュに提供することができる。
【0060】
データの集合のキャッシュ520に使用されるメモリの量に影響を及ぼすと考えられる更に別の要素は、データの集合のキャッシュ520に割り当てられたメモリ514と、ナビゲーション・アプリケーション420に割り当てられたメモリ504との相対的サイズである。データの集合のキャッシュ520に対する相対的に多いメモリが割り当てられると、ナビゲーション・アプリケーション420で利用可能なメモリ504の量が制約される場合には、また逆の場合も同様に、エンドユーザのコンピュータの性能を必ずしも向上させることにはならない。メモリ管理アプリケーション500は、ナビゲーション・アプリケーション420のためのメモリの割り当てと、データの集合のキャッシュで使用するためのメモリの割り当てとの間の適切なバランスを決定するアルゴリズムを含むことができる。ナビゲーション・アプリケーションで必要とされるデータの集合が(メモリ・マネージャ500で決定されたような)データの集合のキャッシュ520にない場合には、メモリ・マネージャ500は、ナビゲーション・サービス・サーバ120からデータの集合を要求する。
【0061】
IV.動作
A.経路案内
(1)概要
ナビゲーション・システム110で実行される機能の1つは、経路案内である。経路案内は、エンドユーザに所望の目的地に到着するための命令を与える。図10は、図1のナビゲーション・システム110で実行される所望の目的地までの経路に追従するための情報をエンドユーザに提供するためのプロセス600におけるステップを示すフローチャートである。
【0062】
(2)経路案内に先立つ機能
a.目的地の選択
経路案内は、ナビゲーション・システム110で実行される1つ又はそれ以上の他の機能と関連する、すなわち該機能から始められる。経路に追従するための情報がエンドユーザに提供される前に、経路の出発地と目的地を決定するステップが存在する(図10のステップ610)。目的地の決定は、地域100における位置を選択する手段をエンドユーザに提供することを含んでいる。目的地の選択は、住所、通りの交差点、地図位置、又は他の位置特定手段を含むことができる。或いは、目的地の選択は、エンドユーザの指定基準又はカテゴリ、例えば指定距離内に位置する特定の形式のレストランに合致するエンドユーザの位置の特定を含むことができる。
【0063】
図1と図10の実施形態において、目的地選択機能は、局所的に利用可能なデータ、ハードウェア又はソフトウェアと、遠隔位置のデータ、ハードウェア又はソフトウェアとの組み合わせを用いて実行することができる。一実施形態によれば、エンドユーザは、彼又は彼女のコンピュータ130で、局所的に利用可能なハードウェア及びソフトウェア(例えば図9の照会アプリケーション420(5))を使用して、ナビゲーション・サービス・サーバ120の検索アプリケーション(図2の224)にアクセスする。エンドユーザは、局所的なハードウェア及びソフトウェアと遠隔的なハードウェア及びソフトウェアとのこの組み合わせを使用して、ナビゲーション・サービス・サーバ120の作業データベース122にアクセスし、目的地としての位置を特定する。目的地は、住所、人名、企業住所、又は企業名とすることができる。或いは、エンドユーザは、検索アプリケーション(図2の224)を使用して、位置例えば指定位置に近い銀行により、個人、企業、又は関心のある地点を見つけることができる。
【0064】
場合によっては、エンドユーザは、エンドユーザのコンピュータに局所的に搭載された測位アプリケーション(図9の420(1))を最初に使用して、彼又は彼女の現在位置を識別し、次いでこの位置をナビゲーション・サービス・サーバ120の検索アプリケーション224に指定して、個人、企業又は関心のある地点を位置ベースで検索するのに使用することができる。
【0065】
別の実施形態において、エンドユーザは、局所的に利用可能なデータ、ハードウェア又はソフトウェアを使用して、目的地を決定することができる。更に別の実施形態によれば、目的地選択機能は、局所的に利用可能なデータ、ハードウェア又はソフトウェアと、遠隔位置のナビゲーション・サービス・サーバから入手したデータを使用して、エンドユーザのコンピュータ上で実行することができる。
【0066】
b.出発地の指定
経路を計算するには、出発地点(すなわち出発地)も必要とされる。場合によっては、エンドユーザの現在位置を出発地として使用することもできる。エンドユーザの現在位置は、エンドユーザのコンピュータ130のナビゲーション・アプリケーション420の中に局所的に搭載された測位アプリケーション420(1)を使用して求めることができる。この機能を実行する時に、測位アプリケーション420(1)は、局所的に利用可能なデータを使用することができる。これらの局所的に利用可能なデータは、エンドユーザのコンピュータに内蔵された地理データベースの一部とすることができる。或いは、局所的に利用可能なデータは、照会アプリケーション420(5)を使用してエンドユーザにより作製された前の要求に対応して、ナビゲーション・サービス・サーバ120から予め入手されている。さらに別の実施形態によれば、出発地は、目的地と同じ方法で求めることができる。さらに別の実施形態によれば、エンドユーザの現在位置は、エンドユーザのコンピュータにおける測位システム(図9の430)を使用して求められた座標を用いて指定することができる。さらに別の実施形態によれば、ユーザは、経路がどこで始まるのか明示的に示すことができる。これは、前述の目的地選択と同様である。
【0067】
(3)経路計算
出発地と目的地が指定された後に、プロセス600は、出発地と目的地を示すデータがナビゲーション・サーバ120(図10のステップ622)の経路計算アプリケーション220で受信されるステップを含む。上述のように、経路計算アプリケーション220は、指定された出発地と目的地との間の法的に有効な連続する一続きの道路(又はその区分)である解答経路を求める。経路計算アプリケーション220は、作業地理データベース122のデータを使用する。経路計算アプリケーション220の動作については既に説明した。解答経路が計算されると、連続的な法的に有効な出発地から目的地までの経路を生成する一続きの道又はその区分が特定される。
【0068】
経路計算アプリケーション220が解答経路を計算した後に、出力650が与えられる。図11は、経路計算アプリケーション220の出力650のコンポーネントを表す概略図である。経路計算出力650は、複数の道路区間を特定する番号付きリストを含む。図11において、複数の道路区間がデータ・エンティティIDにより特定される。これらのIDは、作業地理データベース122の開発者によりこれらの道路区間を表すデータ・エンティティに割り当てられる。経路計算アプリケーション220の出力650における複数の道路区間データ・エンティティは、seg1、seg2、seg3、...seg(n)のラベルが付けられる。複数のデータ・エンティティは、経路計算アプリケーション220で計算された連続的なナビゲーション可能な出発地と目的地の間の経路を生成する道路区間を表す。データ・エンティティIDを使用する代わりに、経路計算アプリケーション220は、解答経路を作り出す道路区間を特定するためのその他の手段を使用することもできる。
【0069】
経路計算出力650は、道路区間のリストに加えて、他の情報を含むことができる。
【0070】
(4)エンドユーザに経路(及び付加的データ)を提供する
ナビゲーション・サービス・サーバ120の経路計算アプリケーション220で解答経路を計算した後に、ナビゲーション・サービス・サーバ120は、解答経路に追従するための案内をエンドユーザに提供できるように、エンドユーザのコンピュータ130にデータを送信する。ナビゲーション・サービス・サーバ120は、エンドユーザのコンピュータ130に2種類のデータを送信する。最初に、ナビゲーション・サービス・サーバ120は、解答経路を生成する道路区間を示す経路計算アプリケーション220の出力650を、エンドユーザのコンピュータ130に送信する(図10のステップ656)。ナビゲーション・サービス・サーバ120は、解答経路を示すデータ650に加えて、解答経路に関連する付加的データ660も送信する。解答経路に関連する付加的データ660は、経路を移動するための有意義な案内をエンドユーザに提供するために、解答経路を示すデータ650と組み合わせて使用される。
【0071】
ナビゲーション・サービス・サーバ120によりエンドユーザのコンピュータ130に送信される付加的データ660は、ダウンロード可能な地理データ記憶装置124から入手される。解答経路が(ステップ636で)計算された後に、地理データ提供アプリケーション(図2の228)は、どのデータがダウンロード可能な地理データ記憶装置124からエンドユーザのコンピュータ130に送信されるのかを決定する(図10のステップ668)。上述のように、ダウンロード可能な地理データ記憶装置124に含まれているデータは、複数のコレクション232に系統化され、該コレクション232の各々は、複数のデータの集合に系統化される(図4の320)。したがって、どの地理データをエンドユーザのコンピュータ130に送信するかを決定する時に、地理データ提供アプリケーション228が、どのデータ・データの集合320を特定のコレクション232から送信するかを決定する。
【0072】
上述のように、地理データを送信する時にどのコレクション232を使用するかの決定は、様々な異なる方法で決定することができる。1つの方法は、エンドユーザのコンピュータに、データがそこから送信されることになるコレクションを特定するアプリケーションを搭載することである。
コレクション232は、IDか又は記述により特定することができる。或いは、地理データ提供アプリケーション228は、図2における加入者データベース208に照会して、どのコレクション232を特定のエンドユーザに使用するかを決定することができる。或いは、地理データ提供アプリケーション228は、1つのコレクションをデフォルトで使用することができる。使用に適したコレクションを決定するために、他のどのような手段をも使用することができる。
【0073】
地理データを送信する時にどのコレクション232を使用するかを指定することに加えて、エンドユーザのコンピュータにおけるアプリケーションも、ナビゲーション・サービス・サーバから受信したデータを保存するためエンドユーザのコンピュータで利用可能なメモリ・リソースを、地理データ提供アプリケーション228に示すことができる。或いは、エンドユーザのコンピュータで利用可能なメモリ・リソースのサイズは、図2の加入者データベース208における設定パラメータとして保存することもできるし、別の手法では、デフォルトのメモリサイズを使用することもできる。
【0074】
使用するデータのコレクション232が決定された後に、コレクション232における特定のデータの集合320が選択される。図12は、地理データ提供アプリケーション228が、エンドユーザのコンピュータにどのデータ・データの集合を送信するかをどのようにして決定するのか説明している。図12は、領域100の一部の地図690を示す。経路700は、地図690に示されている。経路700は、複数の連結された道路区間706として示されている。また、地図690には、地理的区分312(A)から312(L)までのアウトライン710が示されている。上述のように、これらの地理的区分312(A)から312(L)までの各々は、データの別個のデータの集合320に含まれているデータにより表される地理的特徴を含んでおり、該データの集合の中で地理データのコレクション232の全体が分割される。地理データ提供アプリケーション228は、経路計算アプリケーション220で計算されるような解答経路650における道路区間の位置を使用して、解答経路が横切るか又は解答経路における道路区間から指定距離内の地理的区分312を特定する。(指定距離は、設定可能である。)解答経路が横切るか又は該解答経路に近接した地理的区分は、好適な手段のいずれかにより決定することができる。例えば、経路計算アプリケーション220は、解答経路が計算される際に、これらの地理的区分のID(又はこれら自体のデータの集合のID)を保存することができる。
【0075】
解答経路が横切るか又は該解答経路に近接した地理的区分312(A)から312(L)までが決定されると、エンドユーザのコンピュータ130に送信するために、該地理的区分に含まれている地理的特徴を表すデータを含んでいるデータの集合320が決定される。
【0076】
地理データ提供アプリケーション228が解答経路に対応するデータの集合をエンドユーザのコンピュータに送信する時に、該データの集合は、出発地から始まる経路に対応する順に送信される。このようにして、エンドユーザのコンピュータは、出発地周辺の特徴を表すデータを含んでいるデータの集合を最初に受信し、次いで、経路の次の部分周辺の特徴を表すデータを含んでいるデータの集合を受信する。
【0077】
解答経路に対応するデータの集合をエンドユーザのコンピュータに送信する時に、地理データ提供アプリケーション228は、解答経路に対応する全てのデータの集合をエンドユーザのコンピュータに直ちに送信することができる。或いは、地理データ提供アプリケーション228は、データの集合の幾つかのみを最初に送信し、次いで、データの集合の残りを1つ又はそれ以上の次の時間に送信することができる。エンドユーザのコンピュータが、解答経路に対応するものとして特定された全てのデータの集合を保有するのに十分なメモリ・リソースを備えている場合には、地理データ提供アプリケーション228は、全てのデータの集合を直ちにエンドユーザのコンピュータに送信することができる。しかしながら、エンドユーザのコンピュータが、解答経路に対応するものとして特定された全てのデータの集合を保有するのに十分なメモリ・リソースを備えていない場合には、地理データ提供アプリケーション228は、エンドユーザのコンピュータがメモリに保有できるデータの集合の数だけ送信することができる。地理データ提供アプリケーション228により最初に送信されたデータの集合は、経路の最初の部分に対応する。地理データ提供アプリケーション228が、解答経路に対応するデータの集合の幾つかのみを最初に送信する時には、該地理データ提供アプリケーション228は、送信されていないデータの集合を特定するリストを維持する。この実施形態によれば、エンドユーザが、最初にメモリに保存されたデータの集合によって表された区域を通る経路に沿って進んだ後に、エンドユーザのコンピュータは、ナビゲーション・サービス・サーバに、経路の次の部分に対応するデータの集合を送信するよう要求する。地理データ提供アプリケーション228に保管された解答経路に対応するデータの集合のリストを使用して、次にどのデータの集合をエンドユーザのコンピュータに送信するかを迅速に特定する。
【0078】
図10のプロセス600に戻ると、解答経路に対応する全てのデータの集合がエンドユーザのコンピュータに送信される場合には、該プロセスは終了する(ステップ722及び724)。解答経路に対応する全てのデータの集合がエンドユーザのコンピュータに送信されない場合(例えばエンドユーザのコンピュータが全てのデータの集合を保有するのに十分なメモリを備えていない場合)には、送信されていないデータの集合を特定するデータが保存される(ステップ725)。次いで、このプロセスは、エンドユーザのコンピュータが経路の次の部分に対応するデータの集合を要求するまで待機する。経路の次の部分に対する要求を受信すると、追加のデータのデータの集合がエンドユーザのコンピュータに送信される(再びステップ720)。これらのステップは、解答経路に対応するデータの集合が全て送信されるまで繰り返される(ステップ722及び724)。
【0079】
(5)エンドユーザのコンピュータ上でのナビゲーション関連機能の提供
図13は、ナビゲーション・サービス・サーバ120から経路を示すデータ650と付加的データ660を受信した時に、エンドユーザのコンピュータ上で実行されるプロセス750を示す。最初に、データ650及び660が、エンドユーザのコンピュータ130で受信される(ステップ760)。
【0080】
メモリ管理アプリケーション500は、既に行われていない場合には、データの集合のキャッシュ520として使用するためエンドユーザのコンピュータのメモリの一部を予約する(ステップ764)。データの集合のキャッシュを生成する時に、メモリ管理アプリケーション500は、受信するデータの集合のサイズを考慮に入れる。例えば、データの集合が64Kのサイズである場合には、メモリ管理アプリケーション500は、200個のデータの集合を保有するに十分な1280Kのメモリを予約することができる。メモリ管理アプリケーション500は、データの集合320の形態の付加的データ660を、データの集合のキャッシュ520に保存する(ステップ770)。
【0081】
メモリ管理アプリケーション500により生成されたデータの集合のキャッシュ520は、全経路についての全データの集合を確保するのに十分に大きくすることはできない。この場合には、メモリ管理アプリケーション500は、ナビゲーション・サービス・サーバ120から送信された順にデータの集合を保存し、データの集合のキャッシュが満杯になった時にそれ以上のデータの集合を保存するのを止める。このようにして、経路の始まりに対応する付加的データのデータの集合660が、データの集合のキャッシュに保存される。このとき、経路の次の部分に対応する付加的データのデータの集合660は、データの集合のキャッシュに保存されない。メモリ管理アプリケーション500は、地理データ提供アプリケーション228にキャッシュのサイズ(又は保存できるデータの集合の数)を示すメッセージを送信することができる。或いは、メモリ管理アプリケーション500は、地理データ提供アプリケーション228に、データの集合のキャッシュが満杯の時にデータの集合を送信するのを止めるようにメッセージを送信することができる。
【0082】
エンドユーザのコンピュータにおいて、解答経路を示すデータ650は、データの集合のキャッシュ520には保存されない。その代わりに、解答経路を示すデータ650は、メモリの作業部分に保存され(図9の504)、該データは、エンドユーザのコンピュータ130の種々のナビゲーション・アプリケーション420で使用される。
【0083】
エンドユーザのコンピュータにおいて、ナビゲーション・アプリケーション(図9の420)は、解答経路に関連する付加的データ660を、解答経路を示すデータ650と組み合わせて使用して、ナビゲーション関連機能を提供する(ステップ776)。例えば、エンドユーザのコンピュータ130の経路案内アプリケーション420(2)で経路データ650と付加的データ660を使用して、解答経路沿いの特定の位置で移動命令を与えることができる。一例として、経路案内アプリケーション420(2)は、経路データ650と付加的データ660を使用して、「次の交差点、左折です」のような移動命令を与える。これらの付加的データ660は、表示画面上の文字か又は音声命令としてこれらの命令を与えるのに使用される。
【0084】
別の実施例によれば、解答経路に関連する経路データ650と付加的データ660を、エンドユーザのコンピュータ130の地図表示アプリケーション420(3)で使用して、エンドユーザのコンピュータのユーザ・インターフェース(図9の410)の表示画面に経路の地図を与えることができる。経路の地図は、「進路要図」の形式にすることができる。
【0085】
さらに別の実施形態によれば、経路データ650と付加的データ660は、解答経路の一部ではないが解答経路に隣接している道路区間の位置を示すのに使用できる。これらのデータは、車両測位ハードウェア及びソフトウェア、例えばエンドユーザのコンピュータの測位アプリケーション420(1)で使用して、エンドユーザが解答経路から逸脱しているかどうかを判断し、逸脱している場合には、(例えば経路再指定アプリケーション420(4)を使用して)どのようにして解答経路に戻れば良いのか判断することができる。
【0086】
上述のように、データ650により表される全解答経路に関連する全てのデータ・データの集合320を最初に保存することは不可能である。この場合には、経路の最初の部分沿いの地理的特徴を表すデータを含んでいるデータの集合のみが、エンドユーザのコンピュータのデータの集合のキャッシュに最初に保存される。次いで、エンドユーザが、経路に沿って中途まで移動した後に、該エンドユーザは、最終的には、データの集合のキャッシュ・エンドにおけるデータの適用範囲の位置に接近する。例えば、再び図12を参照すると、エンドユーザのコンピュータのデータの集合のキャッシュが、6つのデータ・データの集合のみを格納するスペースを備える場合には、区域312(A)から312(F)までに対応する6つのデータの集合が、最初にデータの集合のキャッシュに保存されることになる。次いで、エンドユーザが経路に沿ってBで示される地点まで移動した後に、該エンドユーザは、データの集合のキャッシュに保存された付加的データの適用範囲が終了する位置に近接するようになる。エンドユーザがこの位置にいる時に、エンドユーザのコンピュータの照会アプリケーション420は、ナビゲーション・サービス・サーバ120にナビゲーション関連のサービスとデータについての新たな要求を送信する(ステップ790及び792)。この新たな要求は、前の要求を基準にすることもできるし、新たな経路に対する要求として処理することもできる。
【0087】
1つの方法によれは、エンドユーザのコンピュータが、そのデータの集合のキャッシュに局所的に含まれるデータの集合に対応する適用範囲の端に接近し、ナビゲーション・サービス・サーバから更にデータの集合を要求した時(ステップ792)に、この新たな要求は、前の要求を基準にすることができる。新たな要求が、前の要求を基準にしている場合には、ナビゲーション・サービス・サーバにおけるプロセスは、(図10のステップ725において)エンドユーザのコンピュータに予め送信されていないデータの集合を特定するリストを使用して、どのデータの集合を次に送信するかを決定する。これらのデータの集合は、ダウンロード可能なデータ記憶装置124から入手され、エンドユーザのコンピュータに送信される。これらの新たなデータの集合がエンドユーザのコンピュータで受信されると、ステップ760によりプロセス750が開始される。
【0088】
別の方法によれば、エンドユーザのコンピュータが該データの集合のキャッシュに局所的に含まれるデータの集合に対応する適用範囲の縁に接近し、ナビゲーション・サービス・サーバから更にデータの集合を要求した時(ステップ792)に、該要求は、全く新たな経路に対する要求としてナビゲーション・サービス・サーバで処理することができる。ナビゲーション・サービス・サーバは、図10のステップ622で始まるプロセス600を実行する。ナビゲーション・サービス・サーバ120は、経路計算アプリケーション220を使用して、B地点を新たな出発地として用いて、目的地までの新たな経路を計算する(同じく図10におけるステップ636)。新たな経路に対する要求として経路の次の脚に対する要求を処理することで、ナビゲーション・サービス・サーバの経路計算アプリケーション220は、前の経路が計算されてから発生しうる道路状況の変化を考慮に入れることができる。次いで、ナビゲーション・サービス・サーバ120は、エンドユーザのコンピュータに(新たな経路データ650の形態で)新たな経路と、(データの集合の形態で)新たな付加的データ660のデータの集合を送信する(同じく図10のステップ656及び720)。新たな経路データ650と新たな付加的データ660がエンドユーザのコンピュータで受信される時に、これらは全く新たな経路として処理される。データの集合のキャッシュに保存されていたデータの集合は、経路の次の脚に関連して受信された新たなデータの集合で書き換えられる。
【0089】
B.経路案内なしの地図表示
別の実施形態において、エンドユーザは、必ずしも経路を要求せずに、地図表示のための地理データを要求することができる。例えば、エンドユーザは、彼又は彼女が存在している位置周辺区域の地図表示を得ようとすることができる。この場合には、エンドユーザは、彼又は彼女の地理的位置周辺の地図表示を要求するよう彼又は彼女のコンピュータを動作させる。エンドユーザは、この目的のために照会アプリケーション420(5)を使用することができる。エンドユーザは、彼又は彼女の位置を指定することもできるし、或いは、照会アプリケーション420(5)が、(存在する場合には)測位システム430からエンドユーザの現在位置を示すデータを入手し、地図表示データに対する要求の中にこの情報を入れることができる。
【0090】
地図表示データに対する要求は、前述の経路情報に対する要求と同様の方法でナビゲーション・サービス・サーバ120で処理される。この場合には、経路を計算する必要はない。ナビゲーション・サービス・サーバは、指定位置周辺の特徴を表す地理データを含むデータの集合を特定する。次いで、ナビゲーション・サービス・サーバは、前述のように、これらのデータの集合をエンドユーザのコンピュータに送信する。エンドユーザのコンピュータにおいて、これらのデータの集合は、図14に関して既に説明したのと同様の手法で処理される。
【0091】
彼又は彼女のエンドユーザの現在位置に関する地図データを要求する代わりに、該エンドユーザは、どの位置に関する地図データも要求することができる。エンドユーザは、地図データが要求される位置を特定するために、好適な手段のいずれをも使用することができる。
【0092】
C.他の機能
エンドユーザのコンピュータに提供される機能のどれも、互いに組み合わせて使用することもできるし、別個に使用することもできる。例えば、測位機能(すなわち、図9の測位アプリケーション420(1)を使用する)は、地図表示機能又は経路案内機能なしで実行することができる。
【0093】
III.別の実施形態
A.機能に基づくデータ・コレクションの選択
図8に関連して、形式(又は機能)により系統化されたデータのコレクションを説明した。データ・コレクションについての種々の種類と機能が提供される。
例えば、経路案内、地図表示、車両測位、音声データ、非音声データその他に、異なるコレクションのデータを与えることができる。エンドユーザのコンピュータが地理データを要求する時には、ナビゲーション・サービス・サーバにデータの種類が示される。この種類は、エンドユーザのコンピュータが対応しているリソースに応じて指定することができる。この種類はまた、エンドユーザのプラットフォームが実行するのに必要とするデータを、機能に応じて指定することができる。例えば、エンドユーザが、地図表示を行うことのみを意図し、経路案内を行うことを意図しない場合には、エンドユーザのコンピュータは、地図表示コレクションから送信されるデータを指定することができる。この方法において、エンドユーザのコンピュータは、必要のないデータは送信せず、これにより、指定された種類のさらに多くのデータを送信できるようにする。
【0094】
B.レイヤに基づくデータ・コレクション
前述のデータ・コレクションの種類(図5から図8までの232)に加えて、図2におけるダウンロード可能なデータ記憶装置124は、レイヤに基づくコレクションを含むことができる。レイヤに基づくコレクションは、地域における道路に割り当てられた順位を使用する。順位は、道路の機能的分類に関連させることができる。移動が一般により速くなる幹線道路は、高次の順序に割り当てられ、移動が一般に遅くなる小さな道路は、低次の順序に割り当てられる。高次の順位の付いた道路を表すデータは、これらの順位を用いて、低い順位の付いた道路とは別の1つ又はそれ以上のコレクションに保存される。
【0095】
C.アプレットとプラグインのダウンロード
経路を表すデータと、経路沿い(又は他の位置周辺)の地理的特徴を表す付加的データに加えて、エンドユーザのコンピュータがナビゲーション・サービス・プロバイダから入手可能な他の種類のデータと情報がある。一実施形態によれば、ナビゲーション・サービス・プロバイダは、ナビゲーション・アプリケーションをエンドユーザのコンピュータに送信することができる。ナビゲーション・サービス・サーバがエンドユーザのコンピュータに送信するナビゲーション・アプリケーションは、新たなアプリケーションとすることもできるし、該ナビゲーション・アプリケーションの前のバージョンの更新版とすることもできる。ナビゲーション・サービス・プロバイダが送信するナビゲーション・アプリケーションは、経路案内、地図表示、測位、照会サービス、経路再指定、メモリ管理その他を含むエンドユーザのコンピュータ・プラットフォームで実行されるアプリケーションのいずれかを含むことができる。一実施形態において、これらのナビゲーション・アプリケーションは、アプレットか又はプラグインとして送信される。
図2を再び参照すると、一実施形態において、ナビゲーション・サービス・プロバイダ128は、ナビゲーション・サービス・サーバ120のダウンロード可能な記憶装置802に、ナビゲーション・アプレット(又はプラグイン)800を保管する。次いで、エンドユーザからの要求を受けると、ナビゲーション・サービス・サーバ120は、ナビゲーション・アプレットか又はプラグインをエンドユーザのコンピュータに送信する。アプレット又はプラグインは、エンドユーザのコンピュータで使用できる。アプレット又はプラグインは、エンドユーザのコンピュータにインストールされたブラウザのような別のアプリケーションで使用できる。この実施形態において、エンドユーザは、所望のナビゲーション機能の種類を特定し、次いでナビゲーション・サービス・サーバが、ナビゲーション・アプレット(又はプラグイン)だけでなく該アプレット(又はプラグイン)で使用されることになるデータも送信する。一例として、エンドユーザが、経路案内を入手したいと思っている場合には、ナビゲーション・サービス・サーバは、経路案内アプレットと、経路を示すデータと、経路沿いの地理的特徴を表す付加的データを送信する。経路案内アプレットは、エンドユーザのコンピュータにダウンロードされ、適正にインストールされると、経路案内アプリケーション(図9の420(2))と同様に動作する。このようにして、エンドユーザが望む機能についてのソフトウェアとデータの両方が、ナビゲーション・サービス・プロバイダから提供される。
【0096】
IV.利点
開示したシステムの実施形態から種々の利点が得られる。前述のように、ナビゲーション・システム110は、多くの異なる種類のエンドユーザのコンピュータに対応している。ナビゲーション・サーバが、異なる種類のコンピュータの各々に送信するのに適したデータ形式を判断しなければならない場合には、ナビゲーション・サーバに、相当の負荷がかかる。したがって、ナビゲーション・サーバは、予め計算されたデータ・データの集合を使用し、これによりこのプロセスを容易にする。
【0097】
予め計算されたデータ・データの集合は、ナビゲーション・サーバからエンドユーザのコンピュータで使用するために転送されるデータの最小サイズ単位として扱われるように設計される。予め計算されたデータの集合は、均一なサイズを有していることから、エンドユーザのコンピュータは、これらを容易に管理することができる。
【0098】
ナビゲーション・サービス・サーバで使用される別個の作業データベース(図2の122)と、エンドユーザのコンピュータで使用するためのダウンロード可能な地理データ(図2の124)とを有することから別の利点が得られる。作業データベースは、サーバで使用するのに最適化することができ、ダウンロード可能な地理データ記憶装置に含まれているデータは、エンドユーザのコンピュータで使用するのに最適化することができる。
【0099】
開示された実施形態の別の利点は、予め計算され、ナビゲーション・サービス・プロバイダからエンドユーザに送信されたデータ・データの集合は、接続性を有することが保証できるということである。経路沿いの特徴を表すデータがエンドユーザに送信される時には、エンドユーザが到達できる全ての道路区間が表されることが好ましい。これは、相当量の処理を含むことができる。開示された実施形態のいずれかを用いて、予め計算されたデータ・データの集合が生成されると、表された全ての道路の接続性が保証される。
【0100】
上記の詳細な説明は、限定的なものではなく説明のためのものとみなされることを意図しており、さらに、付属の請求項は、全ての均等物を含むものであり、本発明の範囲を定めることを意図しているということを理解すべきである。
【図面の簡単な説明】
【0101】
【図1】地理データを、地域にわたって位置しているエンドユーザ・コンピュータに送信するナビゲーション・システムのコンポーネントを説明する図である。
【図2】図1のナビゲーション・サービス・プロバイダのコンポーネントを示すブロック図である。
【図3】図1における地域の地図と、この地図を使用した、ナビゲーション・サーバに格納されたダウンロード可能な地理データを系統化するための実施形態についての説明を示す。
【図4】図2に示すダウンロード可能な地理データ記憶装置に格納された、地理データのコレクションの中の幾つかのコンポーネントを示す図である。
【図5】図4に示すダウンロード可能な地理データ記憶装置に格納された、地理データのコレクションの中の1つのコンポーネントを示す図である。
【図6】図4に示すダウンロード可能な地理データ記憶装置に格納された、地理データのコレクションの中の別のコンポーネントを示す図である。
【図7】図4に示すダウンロード可能な地理データ記憶装置に格納された、地理データのコレクションの中の別のコンポーネントを示す図である。
【図8】図4に示すダウンロード可能な地理データ記憶装置に格納された、地理データの付加的なコレクションのコンポーネントを示す図である。
【図9】図1に示すエンドユーザ・コンピュータのうちの1つのコンポーネントを示すブロック図である。
【図10】図1のナビゲーション・サービス・サーバで実行されるプロセスにおけるステップを示すフローチャートである。
【図11】図10に示すプロセスに係るナビゲーション・サービス・サーバからエンドユーザ・コンピュータに送信される経路データのコンポーネントを示すブロック図である。
【図12】図10におけるプロセスの一部を説明するために使用された地図である。
【図13】ナビゲーション・サービス・サーバが図10におけるプロセスを実行した後に、エンドユーザ・コンピュータで実行されるステップのフローチャートである。
【特許請求の範囲】
【請求項1】
サーバを作動させる方法であって、
クライアント・コンピュータから、地理的データのための要求を受信するステップ、
サーバに記憶される、どの事前に計算された地理的データの集合を、前記要求に応答するためにクライアント・コンピュータに送るかを決定するステップであって、事前に計算された地理的データの集合の各々が、複数の地理的副領域の別個の1つに対応するものであり、当該地理的副領域の中に地理的領域が分割されるものであり、事前に計算された集合が実質的に均等のバイト・サイズを有し、及び、
クライアントコンピュータに送ると決定された、事前に計算された地理的データの集合を発送するステップ、
を含む方法。
【請求項2】
起点と目的地の間のルートを決定するステップ、及び、
前記クライアント・コンピュータへのルートを指示するデータを発送するステップ、
を更に含む、請求項1に記載の方法。
【請求項3】
ルートを決定するステップが、
地理的副領域のどれが、ルートに沿って配置されるかを特定するステップ、及び、
ルートに沿って配置されるものとして特定された地理的副領域を表す、事前に計算された地理的データの集合を発送することを決定するステップ、
を含む、請求項2に記載の方法。
【請求項4】
クライアント・コンピュータが、ルートから離れたか否かを決定するステップ、及び、
もし、クライアント・コンピュータがルートから離れたならば、クライアント・コンピュータに送られた、事前に計算された地理的データの集合に含まれるデータを用いて、ルートに戻る道筋を計算し、ルートに戻る道筋を指示するデータを、クライアント・コンピュータに発送するステップ、
を更に含む、請求項2に記載の方法。
【請求項5】
事前に計算された地理的データの集合内に包含されるデータによって表される道に対する、クライアント・コンピュータの位置を決定するステップ、
クライアント・コンピュータの位置を用いて、ビジネス、及び/又は、人に関する情報を発見するステップ、及び、
ビジネス、及び/又は、人に関する情報を指示するデータを、クライアント・コンピュータに発送するステップ、
を更に含む、請求項1に記載の方法。
【請求項6】
加入者サービスを、サーバにアクセスするエンド・ユーザに提供するステップ、を更に含む、請求項1に記載の方法。
【請求項7】
前記サーバが、データ・サイズによって系統化された(organized)地理的データの保存庫を含み、保存庫内の地理的データの第1の集合が、事前に計算された、第1のバイト・サイズの地理的データの集合を含み、保存庫内の地理的データの第2の集合が、事前に計算された、第2のバイト・サイズの地理的データの集合を含む、
請求項1に記載の方法。
【請求項8】
前記サーバが、データ属性によって系統化された、地理的データの保存庫を含み、保存庫内の地理的データの第1のグループが、事前に計算された、第1のデータ属性の地理的データの集合を含み、保存庫内の地理的データの第2のグループが、事前に計算された、第2のデータ属性の地理的データの集合を含む、
請求項1に記載の方法。
【請求項9】
アプリケーションを、クライアント・コンピュータにダウンロードするステップを更に含む、請求項1に記載の方法。
【請求項10】
前記アプリケーションが、アプレット、プラグイン、メモリ・マネジャ・アプリケーション、及び、クライアント・コンピュータの上に既にインストールされた、アップリケーションに対する更新、の1つである、
請求項9に記載の方法。
【請求項1】
サーバを作動させる方法であって、
クライアント・コンピュータから、地理的データのための要求を受信するステップ、
サーバに記憶される、どの事前に計算された地理的データの集合を、前記要求に応答するためにクライアント・コンピュータに送るかを決定するステップであって、事前に計算された地理的データの集合の各々が、複数の地理的副領域の別個の1つに対応するものであり、当該地理的副領域の中に地理的領域が分割されるものであり、事前に計算された集合が実質的に均等のバイト・サイズを有し、及び、
クライアントコンピュータに送ると決定された、事前に計算された地理的データの集合を発送するステップ、
を含む方法。
【請求項2】
起点と目的地の間のルートを決定するステップ、及び、
前記クライアント・コンピュータへのルートを指示するデータを発送するステップ、
を更に含む、請求項1に記載の方法。
【請求項3】
ルートを決定するステップが、
地理的副領域のどれが、ルートに沿って配置されるかを特定するステップ、及び、
ルートに沿って配置されるものとして特定された地理的副領域を表す、事前に計算された地理的データの集合を発送することを決定するステップ、
を含む、請求項2に記載の方法。
【請求項4】
クライアント・コンピュータが、ルートから離れたか否かを決定するステップ、及び、
もし、クライアント・コンピュータがルートから離れたならば、クライアント・コンピュータに送られた、事前に計算された地理的データの集合に含まれるデータを用いて、ルートに戻る道筋を計算し、ルートに戻る道筋を指示するデータを、クライアント・コンピュータに発送するステップ、
を更に含む、請求項2に記載の方法。
【請求項5】
事前に計算された地理的データの集合内に包含されるデータによって表される道に対する、クライアント・コンピュータの位置を決定するステップ、
クライアント・コンピュータの位置を用いて、ビジネス、及び/又は、人に関する情報を発見するステップ、及び、
ビジネス、及び/又は、人に関する情報を指示するデータを、クライアント・コンピュータに発送するステップ、
を更に含む、請求項1に記載の方法。
【請求項6】
加入者サービスを、サーバにアクセスするエンド・ユーザに提供するステップ、を更に含む、請求項1に記載の方法。
【請求項7】
前記サーバが、データ・サイズによって系統化された(organized)地理的データの保存庫を含み、保存庫内の地理的データの第1の集合が、事前に計算された、第1のバイト・サイズの地理的データの集合を含み、保存庫内の地理的データの第2の集合が、事前に計算された、第2のバイト・サイズの地理的データの集合を含む、
請求項1に記載の方法。
【請求項8】
前記サーバが、データ属性によって系統化された、地理的データの保存庫を含み、保存庫内の地理的データの第1のグループが、事前に計算された、第1のデータ属性の地理的データの集合を含み、保存庫内の地理的データの第2のグループが、事前に計算された、第2のデータ属性の地理的データの集合を含む、
請求項1に記載の方法。
【請求項9】
アプリケーションを、クライアント・コンピュータにダウンロードするステップを更に含む、請求項1に記載の方法。
【請求項10】
前記アプリケーションが、アプレット、プラグイン、メモリ・マネジャ・アプリケーション、及び、クライアント・コンピュータの上に既にインストールされた、アップリケーションに対する更新、の1つである、
請求項9に記載の方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【公開番号】特開2008−175830(P2008−175830A)
【公開日】平成20年7月31日(2008.7.31)
【国際特許分類】
【出願番号】特願2008−80957(P2008−80957)
【出願日】平成20年3月26日(2008.3.26)
【分割の表示】特願2002−154729(P2002−154729)の分割
【原出願日】平成14年4月19日(2002.4.19)
【出願人】(597011544)ナヴィゲイション テクノロジーズ コーポレイション (8)
【Fターム(参考)】
【公開日】平成20年7月31日(2008.7.31)
【国際特許分類】
【出願日】平成20年3月26日(2008.3.26)
【分割の表示】特願2002−154729(P2002−154729)の分割
【原出願日】平成14年4月19日(2002.4.19)
【出願人】(597011544)ナヴィゲイション テクノロジーズ コーポレイション (8)
【Fターム(参考)】
[ Back to top ]