地図データ配信サーバ、地図更新方法、及び地図データ配信システム
【課題】地図データの更新の際に、通信するデータ量の増加を抑制しつつ、リンクの属性の矛盾が発生することを防止する。
【解決手段】ネットワークに接続される地図データ配信サーバであって、前記地図データ配信サーバは、第１の道路データと、それより新しい第２の道路データとの間の差分データ項目を作成し、各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成し、第１の更新エレメントが第１のリンク列の属性に関する差分データ項目を含み、かつ、第２の更新エレメントが前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記第１及び第２の更新エレメントを含む第３の更新エレメントを作成し、地図更新要求によって、前記第３の更新エレメント内の前記差分データ項目に関するリンクを含む地図上の範囲が指定された場合、前記第３の更新エレメントを送信する。
【解決手段】ネットワークに接続される地図データ配信サーバであって、前記地図データ配信サーバは、第１の道路データと、それより新しい第２の道路データとの間の差分データ項目を作成し、各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成し、第１の更新エレメントが第１のリンク列の属性に関する差分データ項目を含み、かつ、第２の更新エレメントが前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記第１及び第２の更新エレメントを含む第３の更新エレメントを作成し、地図更新要求によって、前記第３の更新エレメント内の前記差分データ項目に関するリンクを含む地図上の範囲が指定された場合、前記第３の更新エレメントを送信する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データを利用したサービスを利用者に提供する技術に関し、特に、ナビゲーション装置が保持する地図データを更新する技術に関する。
【背景技術】
【０００２】
ナビゲーション装置等が保持する地図データを更新する技術として、例えば特許文献１から特許文献３が知られている。
【０００３】
特許文献１によれば、更新される複数のリンクデータのうち、互いにネットワークとして接続されているものが一つの地図更新データとして管理される。指定された領域の地図データの更新が要求された場合、その領域に少なくとも一部が属する地図更新データによって地図データが更新される。これによって、更新後の道路ネットワークの接続性を保証しつつ、更新のために通信されるデータサイズを小さくすることができる。
【０００４】
特許文献２によれば、指定された領域の地図データの更新が要求された場合、指定された領域の差分更新データと、それが依存する更新データとが特定され、それらのうち古いものから順に更新が行われる。これによって、更新データ量を抑えつつ、所望の領域の地図データを最新の状態に更新し、かつ、指定された領域とそれに隣接する更新されない領域との整合性も保つことができる。
【０００５】
特許文献３によれば、リンクごとに、リンクデータが更新された日時を示す情報、及び、更新の影響が及ぶ範囲を示す情報がサーバに保持される。そして、端末が、指定された領域の地図データの更新を要求すると、サーバは、その領域内のリンク、及び、それらのリンクの更新の影響が及ぶリンクのうち、前回の更新要求より後に更新されたリンクのデータのみを端末に送信する。これによって、不要な通信トラフィックの発生を抑制し、かつ、更新後の地図に矛盾が生じないように地図データを更新することができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−９０１９５号公報
【特許文献２】特開２００７−２４１００３号公報
【特許文献３】国際公開第０６／０１１２７８号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
現在普及している一般的な車載用ナビゲーションシステムの地図データのフォーマットによれば、道路の属性（例えば、その道路が有料道路であるか否か、等）を示す情報は、道路の各区間に対応する各リンクデータにではなく、複数のリンクからなるリンク列に付与されたリンク列ヘッダに含まれる。このような場合において、リンク列の属性が変更された場合、上記特許文献１〜３に記載されたように地図データを更新すると、変更されたリンクの属性が正しく地図データに反映されない場合がある。
【０００８】
例えば、一続きの道路の一部が有料区間であり、それに続く残りの部分が無料区間である場合、有料区間と無料区間はそれぞれ別のリンク列として管理される。この場合、それぞれのリンク列に対応するリンク列ヘッダが保持され、有料区間に対応するリンク列ヘッダは有料道路を示す属性情報を含み、無料区間に対応するリンク列ヘッダは無料道路を示す属性情報を含む。その後、有料区間が無料区間に変更された場合、有料区間に対応するリンク列ヘッダの属性を無料道路に更新し、以前の無料区間に対応するリンク情報を削除し、その削除された無料区間に対応するリンク情報を、新たに無料区間に変更されたリンク列に追加する必要がある。これによって、属性の変更が正しく地図データに反映される。しかし、上記特許文献１〜３に記載された方法によれば、上記のリンク列ヘッダの更新、リンク情報の削除及び追加のうち一部のみが実行される場合がある。その場合、例えば更新後のすべてのリンクが有料区間として扱われるなど、地図データと実際の道路の状況との間に矛盾が発生することがある。
【０００９】
このようなフォーマットが使用される場合、リンクデータごとの更新を禁止し、常にリンク列ヘッダを含むリンク列全体を更新すれば、上記のような矛盾の発生を防ぐことができる。しかし、この場合、少数のリンクデータのみを更新する場合であっても常にリンク列全体のデータを通信する必要がある。加えて、上記特許文献１〜３に示すように、リンクの不連続などの問題の発生を防ごうとすれば、さらに多くのリンクデータを通信する必要が生じる。
【００１０】
本発明は上記の問題点に鑑みてなされたものであり、通信するデータ量の増加を抑制しつつ、上記のようなリンクの属性の矛盾の発生を防止する地図データの更新を実現することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、ネットワークに接続される地図データ配信サーバであって、前記地図データ配信サーバは、前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、第１の道路データと、前記第１の道路データより新しいバージョンである第２の道路データと、を保持し、前記第１の道路データと第２の道路データとをデータ項目ごとに比較することによって、前記第１の道路データと前記第２の道路データとの間の差分データ項目を作成し、各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成し、前記複数の更新エレメントのうち第１の更新エレメントが、第１のリンク列の属性に関する差分データ項目を含み、かつ、前記複数の更新エレメントのうち第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記第１の更新エレメント及び前記第２の更新エレメントに含まれる全ての前記差分データ項目を含む第３の更新エレメントを作成し、前記ネットワークに接続された端末装置から受信した地図更新要求が、前記第３の更新エレメント内の前記差分データ項目に関するリンクを含む地図上の範囲を指定した場合、前記第３の更新エレメントを前記端末装置に送信することを特徴とする。
【発明の効果】
【００１２】
本発明の一実施形態によれば、地図データの更新の際に、通信するデータ量の増加を抑制しつつ、リンクの属性の矛盾が発生することを防止することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態の地図データ配信システムの構成を示すブロック図である。
【図２】本発明の実施形態の地図データ配信システムにおける道路データの説明図である。
【図３】道路データを更新するための更新エレメントの説明図である。
【図４】本発明の実施形態の地図データ配信システムにおける道路データの別の例の説明図である。
【図５】道路データを更新するための更新エレメントの別の例の説明図である。
【図６】更新エレメントごとの地図データの更新の説明図である。
【図７】本発明の実施形態の地図データ配信システムにおける道路データを更新するための更新エレメントの説明図である。
【図８】更新エレメントを作成する手順を示すフローチャートである。
【図９】本発明の実施形態の地図配信サーバが更新エレメントを作成する手順を示すフローチャートである。
【図１０】本発明の実施形態の地図配信サーバによってリンクの識別子が付加された道路データを示す説明図である。
【図１１】本発明の実施形態の更新エレメント作成処理の途中で作成されるデータの説明図である。
【図１２】本発明の実施形態の更新エレメント作成処理の途中で作成される別のデータの説明図である。
【発明を実施するための形態】
【００１４】
以下、図面を用いて本発明の実施の形態を説明する。
【００１５】
図１は、本発明の実施形態の地図データ配信システムの構成を示すブロック図である。
【００１６】
本実施形態の地図データ配信システムは、ネットワーク４０に接続された地図配信サーバ１０と、ネットワーク４０を介して地図配信サーバ１０と通信するナビゲーション端末２０と、を備える。
【００１７】
地図配信サーバ１０は、互いに接続されたプロセッサ１７、メモリ１８、ネットワークインターフェース（Ｉ／Ｆ）１５、管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１６を備える計算機である。
【００１８】
プロセッサ１７は、メモリ１８に格納されたプログラムを実行する。
【００１９】
メモリ１８は、例えば半導体メモリであり、プロセッサ１７によって実行されるプログラム及びプロセッサ１７によって参照されるデータ等を格納する。本実施形態のメモリ１８には、更新データ抽出部１３及び更新データ管理部１４が格納される。これらのプログラムの処理については後述する。以下の説明において更新データ抽出部１３及び更新データ管理部１４が実行する処理は、実際には、プロセッサ１７によって実行される。
【００２０】
ネットワークＩ／Ｆ１５は、ネットワーク４０に接続され、ナビゲーション端末２０等と通信する。
【００２１】
管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１６は、ハードディスクドライブ（ＨＤＤ）またはフラッシュメモリのような記憶装置であってもよいし、そのような記憶装置内の記憶領域であってもよい。
【００２２】
地図データ記憶部１６には、地図データが格納される。地図データは、地図の構成物（地物）の位置及び形状を示す座標値等を含む。現実の地物は随時更新される。その一例は、道路の新設、廃止又は付け替えのような道路ネットワークの更新である。地図データは、過去のある時点における地物に関する情報（例えば後述するバージョン１の道路データ）と、それより後の時点における地物に関する情報（例えば後述するバージョン２の道路データ）と、を含んでもよい。
【００２３】
なお、一般に地図データは、地図上の所定の矩形の範囲ごとに管理される。この矩形の範囲は、パーセル又はメッシュと呼ばれる。各パーセルには固有の識別子（パーセルＩＤ）が付与される。
【００２４】
更新データ記憶部１２には、地物を単位とする地図更新データ（地図情報及び道路ネットワーク情報を含む）が格納される。地図更新データは、例えばナビゲーション端末２０がバージョン１の地図データを保持している場合に、それをより新しいバージョン２の地図データに更新するために作成及び送信されるデータであり、具体的には、少なくともこれらのバージョンの差分データを含む。地図更新データの詳細については後述する。
【００２５】
管理データ記憶部１１には、地図更新データを管理するための情報が格納される。例えば、管理データ記憶部１１には、地図更新データのバージョン（すなわち差分の世代）を示す情報、及び、地図更新データが適用されるべき位置を示すパーセルＩＤ等が格納される。
【００２６】
ナビゲーション端末２０は、ユーザを目的地まで誘導するために、経路検索及び検索結果の出力等を行う移動端末である。本実施形態では典型的な例として、ナビゲーション端末２０が自動車に搭載される車載用ナビゲーション端末である場合について説明するが、例えば歩行者に携帯されるナビゲーション端末等、種々の移動端末に本発明を適用することができる。
【００２７】
本実施形態のナビゲーション端末２０は、互いに接続されたプロセッサ２８、メモリ２９、ネットワークＩ／Ｆ２１、画面入出力Ｉ／Ｆ２５、管理データ記憶部２６及び地図データ記憶部２７を備える。
【００２８】
プロセッサ２８は、メモリ２９に格納されたプログラムを実行する。
【００２９】
メモリ２９は、例えば半導体メモリであり、プロセッサ２８によって実行されるプログラム及びプロセッサ２８によって参照されるデータ等を格納する。本実施形態のメモリ２９には、配信要求部２２、地図更新部２３及びナビゲーション処理部２４が格納される。
【００３０】
配信要求部２２は、地図更新データの配信要求（以下、地図データ更新要求と記載）を地図配信サーバ１０に送信する。地図更新部２３は、配信された地図更新データを用いて、地図データ記憶部２７に格納された地図データを更新する。これらの処理については後述する。以下の説明において配信要求部２２、地図更新部２３及びナビゲーション処理部２４が実行する処理は、実際にはプロセッサ２８によって実行される。
【００３１】
ナビゲーション処理部２４は、地図データ記憶部２７に格納された地図データに基づいて、目的地までの経路を検索し、その経路に沿ってユーザを誘導する。このような経路検索及び誘導は従来の車載用ナビゲーション端末と同様であるため、これらに関する詳細な説明は省略する。
【００３２】
画面入出力Ｉ／Ｆ２５は、ユーザに対して地図情報等を表示する画面と、ユーザからの入力を受け付ける入力装置と、を含む。例えば、画面入出力Ｉ／Ｆ２５は、タッチパッド付きの液晶表示装置であってもよい。
【００３３】
ネットワークＩ／Ｆ２１は、無線通信装置３０に接続される。無線通信装置３０は、ネットワーク４０に接続された無線基地局３１と無線通信を行う。ネットワークＩ／Ｆ２１は、無線通信装置３０、無線基地局３１及びネットワーク４０を介して地図配信サーバ１０との間の通信を実行する。後述する地図データ更新要求の送信（５１）及び地図更新データの受信（５２）はこのような通信によって実現される。
【００３４】
なお、無線通信装置３０は、ナビゲーション端末２０に内蔵されてもよい。
【００３５】
管理データ記憶部２６及び地図データ記憶部２７は、ハードディスクドライブ（ＨＤＤ）またはフラッシュメモリのような記憶装置であってもよいし、そのような記憶装置内の記憶領域であってもよい。
【００３６】
地図データ記憶部２７には、ナビゲーション処理部２４によって参照される地図データが格納される。この地図データは、地図配信サーバ１０から送信された地図更新データに基づいて更新される。
【００３７】
管理データ記憶部２６には、地図データを管理するための情報が格納される。例えば、管理データ記憶部２６には、自車（すなわちナビゲーション端末２０を搭載している車）の位置がどのパーセルに属するかを示す緯度経度−パーセルＩＤ対応情報、及び、地図に適用した地図更新データの識別情報等が格納される。
【００３８】
ネットワーク４０はインターネット４１に接続される。地図配信サーバ１０は、インターネット４１を介して新しいバージョンの地図データを取得してもよい。
【００３９】
図２は、本発明の実施形態の地図データ配信システムにおける道路データの説明図である。
【００４０】
ナビゲーション端末２０は、地図データ記憶部２７に地図データを保持し、それに基づいて経路検索等を実行する。一方、地図配信サーバ１０は、現実の道路ネットワークの変更等が反映された新バージョンの地図データを取得すると、それに基づいて、ナビゲーション端末２０が保持している旧バージョンの地図データを新バージョンに更新するための地図更新データを作成し、それを更新データ記憶部１２に格納する。図２には、地図データ記憶部１６に格納される地図データの例として、旧バージョン（Ｖｅｒ．１）と新バージョン（Ｖｅｒ．２）の地図データを示す。
【００４１】
なお、一般に地図データは、道路ネットワークに関するデータ（道路データ）に加えて、道路以外の地物、例えば建物、河川及び行政区等に関するデータも含む。しかし、図２には本実施形態の説明のために必要な道路データのみを示し、その他のデータについては図示を省略する。図３以降についても同様である。
【００４２】
周知のように、地図データ上で、道路は、ノードとリンクとの組み合わせによって表現される。ノードは交差点に、リンクは二つの交差点を接続する道路の区間に対応する。
【００４３】
図２（ａ）は、例として、五つの交差点と、それらを接続する四つの区間と、からなる有料道路を表現するノード及びリンクを示す。図２（ａ）に示すバージョン１（Ｖｅｒ．１）の道路データは、ｎｏｄｅ１＿２０１Ａ〜ｎｏｄｅ５＿２０５Ａの五つのノードと、ｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａの四つのリンクによって表現される。ｌｉｎｋ１＿２１１Ａはｎｏｄｅ１＿２０１Ａとｎｏｄｅ２＿２０２Ａとを接続し、ｌｉｎｋ２＿２１２Ａはｎｏｄｅ２＿２０２Ａとｎｏｄｅ３＿２０３Ａとを接続し、ｌｉｎｋ３＿２１３Ａはｎｏｄｅ３＿２０３Ａとｎｏｄｅ４＿２０４Ａとを接続し、ｌｉｎｋ４＿２１４Ａはｎｏｄｅ４＿２０４Ａとｎｏｄｅ５＿２０５Ａとを接続する。
【００４４】
以下の説明において、二つの区間が一つの交差点に接続されている場合、それらの区間を連続する区間と記載し、それらの区間に対応するリンクを連続するリンクと記載する。例えば図２（ａ）においてｎｏｄｅ２＿２０２Ａに接続されるｌｉｎｋ１＿２１１Ａとｌｉｎｋ２＿２１２Ａとは連続する。同様に、ｌｉｎｋ２＿２１２Ａとｌｉｎｋ３＿２１３Ａとは連続し、ｌｉｎｋ３＿２１３Ａとｌｉｎｋ４＿２１４Ａとは連続する。結局、ｌｉｎｋ１＿２１１Ａからｌｉｎｋ４＿２１４Ａまでの四つのリンクは連続している。
【００４５】
バージョン１の道路データが作成された後、実際の道路が付け替え等によって変更された場合、その変更が反映された道路データ、すなわちバージョン２（Ｖｅｒ．２）の道路データが作成される。図２の例では、ｌｉｎｋ１＿２１１Ａ、ｌｉｎｋ３＿２１３Ａ及びｌｉｎｋ４＿２１４Ａに対応する区間の道路の形状が変更されたため、これらのリンクがバージョン２ではそれぞれｌｉｎｋ１＿２１１Ｂ、ｌｉｎｋ３＿２１３Ｂ及びｌｉｎｋ４＿２１４Ｂによって置き換えられている。バージョン２のその他のリンク及びノードはバージョン１と同じである。
【００４６】
道路データは、さらに、道路の属性を示す情報を含む。道路の属性を示す情報は、例えば道路の種別（例えば国道又は県道）、路線番号、又はその道路が有料道路又は無料道路のいずれであるか、等の属性を示す情報を含むが、上記以外の属性を示す情報を含んでもよい。一般に、連続する複数のリンクの属性が共通する場合が多い。例えば、ある有料道路の始点から終点までのすべてのリンクは、有料道路という属性を有する。
【００４７】
図２に示す道路データにおいて、属性が共通する複数の連続したリンク及びそれらに接続されるノードが一つのリンク列として扱われ、属性を示す情報はリンク列ごとに付与される。図２（ａ）の例において、バージョン１のｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａの四つのリンクは一つのリンク列（すなわちバージョン１のリンク列１＿２１０Ａ）として扱われ、バージョン２のｌｉｎｋ１＿２１１Ｂ〜ｌｉｎｋ４＿２１４Ｂの四つのリンクも一つのリンク列（すなわちバージョン２のリンク列１＿２１０Ｂ）として扱われる。
【００４８】
図２（ｂ）は、図２（ａ）のノード及びリンクによって表現される道路データの具体的なフォーマットを示す。
【００４９】
図２（ｂ）の例において、バージョン１の道路データ２２０Ａは、リンク列１ヘッダ情報２２１Ａ及びリンク列１リンク情報２２２Ａからなる。
【００５０】
リンク列１ヘッダ情報２２１Ａは、リンク列１＿２１０Ａの属性（すなわち、リンク列１＿２１０Ａに含まれるすべてのリンクの属性）を示す情報を含む。図２（ｂ）の例において、リンク列１ヘッダ情報２２１Ａは、道路種別２３１Ａ、路線番号２３２Ａ、及び、有料フラグ２３３Ａを含む。道路種別２３１Ａは、そのリンク列１＿２１０Ａに対応する道路の種別、例えばそれが国道であるか県道であるか等を示す情報である。路線番号２３２Ａは、その道路に付与された番号、例えば国道番号を示す情報である。有料フラグ２３３Ａは、その道路が有料道路であるか無料道路であるかを示す情報である。図２（ｂ）の例の有料フラグ２３３Ａは、その道路が有料道路であることを示している。
【００５１】
リンク列１リンク情報２２２Ａは、リンク列１＿２１０Ａに含まれるノード及びリンクに関する情報を含む。図２（ｂ）の例において、リンク列１リンク情報２２２Ａは、ｎｏｄｅ１ノード情報２４１Ａ〜ｎｏｄｅ５ノード情報２４５Ａ、ｌｉｎｋ１形状情報２５１Ａ〜ｌｉｎｋ４形状情報２５４Ａ、ｌｉｎｋ１通行規制情報２６１Ａ〜ｌｉｎｋ４通行規制情報２６４Ａ、及びｌｉｎｋ１その他情報２７１Ａ〜ｌｉｎｋ４その他情報２７４Ａを含む。
【００５２】
ｎｏｄｅ１ノード情報２４１Ａ〜ｎｏｄｅ５ノード情報２４５Ａは、それぞれ、ｎｏｄｅ１＿２０１Ａ〜ｎｏｄｅ５＿２０５Ａに対応する交差点に関する情報、例えばそれらの交差点の座標を示す情報等を含む。
【００５３】
ｌｉｎｋ１形状情報２５１Ａ〜ｌｉｎｋ４形状情報２５４Ａは、それぞれ、ｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａに対応する区間の道路の形状を示す情報を含む。例えば、この情報は、それらの区間の道路上の一つ以上の点の座標を示す情報等を含んでもよい。
【００５４】
ｌｉｎｋ１通行規制情報２６１Ａ〜ｌｉｎｋ４通行規制情報２６４Ａは、それぞれ、ｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａに対応する区間の通行規制に関する情報を含む。
【００５５】
ｌｉｎｋ１その他情報２７１Ａ〜ｌｉｎｋ４その他情報２７４Ａは、それぞれ、ｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａに対応する区間に関するその他の情報、例えばそれらの区間の通過に要する時間に関する情報等を含む。
【００５６】
なお、上記は道路データに含まれる情報の一例に過ぎず、実際の道路データは道路に関するさらに詳細な情報を含んでもよい。
【００５７】
図２（ａ）に示すように、バージョン１のリンク列１＿２１０Ａのｌｉｎｋ１＿２１１Ａ、ｌｉｎｋ３＿２１３Ａ及びｌｉｎｋ４＿２１４Ａに対応する区間の道路の形状が変更されたため、これらのリンクが、バージョン２ではそれぞれｌｉｎｋ１＿２１１Ｂ、ｌｉｎｋ３＿２１３Ｂ及びｌｉｎｋ４＿２１４Ｂによって置き換えられている。このため、バージョン２の道路データ２２０Ｂは、上記の三つのリンクの形状を示す情報を除いてバージョン１の道路データ２２０Ａと同じである。
【００５８】
具体的には、ｌｉｎｋ１形状情報２５１Ａ、ｌｉｎｋ３形状情報２５３Ａ及びｌｉｎｋ４形状情報２５４Ａが、それぞれ、変更された後の形状を示すｌｉｎｋ１形状情報−２＿２５１Ｂ、ｌｉｎｋ３形状情報−２＿２５３Ｂ及びｌｉｎｋ４形状情報−２＿２５４Ｂによって置き換えられる。リンク列１リンク情報２２２Ｂのうち、これらの三つのリンクの形状情報以外の部分は、リンク列１リンク情報２２２Ａと同じである。
【００５９】
図２に示したようにリンク列ごとに属性情報が付与される道路データのフォーマットとして、ＫＩＷＩフォーマットが知られている。本発明は、ＫＩＷＩフォーマットに適用することができるが、リンク列ごとに属性情報が付与される限り、ＫＩＷＩフォーマット以外のフォーマットにも適用することができる。
【００６０】
図３は、道路データを更新するための更新エレメントの説明図である。
【００６１】
具体的には、図３は、図２に示す道路データに対応する更新エレメントの例を示す。
【００６２】
図２に示すバージョン１の道路データ２２０Ａを保持している地図配信サーバ１０は、新たにバージョン２の道路データ２２０Ｂを取得すると、バージョン１の道路データ２２０Ａをバージョン２の道路データ２２０Ｂに更新するための地図更新データを作成して更新データ記憶部１２に格納する。格納された地図更新データは、ナビゲーション端末２０からの要求に応じて送信される。
【００６３】
このような地図更新データは、バージョン２の道路データ２２０Ｂ全体を含んでもよい。しかし、例えばナビゲーション端末２０が移動しながら無線によるパケット通信等を利用して現在地周辺の地図データを更新する場合には、迅速性が要求される。また、通信するデータ量に課金される場合、通信コストを抑制するためにデータ量を抑制することが望ましい。これらの観点から、地図更新データの量は少ないことが望ましい。このため、本実施形態の地図配信サーバ１０は、新旧の道路データの差分のみを地図更新データとして作成する。
【００６４】
図２の例では、二つの道路データの差分はｌｉｎｋ１形状情報−２＿２５１Ｂ、ｌｉｎｋ３形状情報−２＿２５３Ｂ及びｌｉｎｋ４形状情報−２＿２５４Ｂのみである。このため、地図配信サーバ１０は、ｌｉｎｋ１形状情報２５１Ａをｌｉｎｋ１形状情報−２＿２５１Ｂに更新することを指示する情報を地図更新データとして作成する。この情報は、例えば、更新されたｌｉｎｋ１＿２１１Ｂに対応する区間の道路の座標値を示す情報を含む。同様に、地図配信サーバ１０は、ｌｉｎｋ３形状情報２５３Ａをｌｉｎｋ３形状情報−２＿２５３Ｂに更新することを指示する情報、及び、ｌｉｎｋ４形状情報２５４Ａをｌｉｎｋ４形状情報−２＿２５４Ｂに更新することを指示する情報を地図更新データとして作成する。
【００６５】
本実施形態では、原則として、一つのデータ項目を更新するための地図更新データが一つの更新エレメントとして扱われる。ここで一つのデータ項目とは、図２（ｂ）に示す地図データの各項目、すなわち、各行に対応する項目である。例えば、有料フラグ２３３Ａ、ｌｉｎｋ１形状情報２５１Ａ及びｎｏｄｅ３ノード情報２４３Ａは、それぞれ、一つのデータ項目である。図３の例では、ｌｉｎｋ１形状情報２５１Ａをｌｉｎｋ１形状情報−２＿２５１Ｂに更新することを指示する情報が更新エレメント１＿３０１として扱われる。
【００６６】
ただし、上記のように作成した地図更新データが、単一の区間又は連続した複数の区間に関する情報を含む場合、それらの区間に関する更新データが一つの更新エレメントとして扱われる。ここで、ある区間に関する情報には、その区間に対応するリンクの形状等に関する情報、そのリンクの始点ノード及び終点ノードに関する情報が含まれ、そのリンクがリンク列の先頭リンクである場合、そのリンク列のヘッダ情報も含まれる。
【００６７】
図３の例では、ｌｉｎｋ３形状情報２５３Ａをｌｉｎｋ３形状情報−２＿２５３Ｂに更新することを指示する情報、及び、ｌｉｎｋ４形状情報２５４Ａをｌｉｎｋ４形状情報−２＿２５４Ｂに更新することを指示する情報が、一つの更新エレメント、すなわち更新エレメント２＿３０２として扱われる。地図配信サーバ１０は、このように作成した更新エレメントをナビゲーション端末２０に送信する。
【００６８】
例えばナビゲーション端末２０は、自車の現在地（又は目的地）の周辺の所定の範囲内の地図データの更新を地図配信サーバ１０に要求してもよい（図１のステップ５１）。具体的には、例えばユーザが地図データの更新要求を画面入出力Ｉ／Ｆに入力すると、ナビゲーション端末２０の配信要求部２２が管理データ記憶部２６を参照して自車の位置を含むパーセルのＩＤを特定し、そのパーセルの地図データの更新要求を地図配信サーバ１０に送信する。あるいは配信要求部２２が自動的に（例えば定期的に又は所定の条件が満たされたときに）地図データの更新要求を地図配信サーバに送信してもよい。
【００６９】
更新要求を受信した地図配信サーバ１０は、更新要求によって指定されたパーセル内の地物に関するデータを含む更新エレメントをナビゲーション端末２０に送信する（図１のステップ５２）。例えば、指定されたパーセルにｌｉｎｋ１＿２１１Ａに対応する区間とｌｉｎｋ３＿２１３Ａに対応する区間との両方が含まれる場合、地図配信サーバ１０は更新エレメント１＿３０１及び更新エレメント２＿３０２の両方を地図更新データとしてナビゲーション端末２０に送信する。一方、指定されたパーセルにｌｉｎｋ１＿２１１Ａに対応する区間が含まれるが、ｌｉｎｋ３＿２１３Ａに対応する区間は含まれない場合、地図配信サーバ１０は更新エレメント１＿３０１をナビゲーション端末２０に送信するが、更新エレメント２＿３０２は送信しない。
【００７０】
なお、地図配信サーバ１０は、各差分データ項目を含む更新エレメントを識別する情報（すなわち、各差分データ項目がどの更新エレメントに含まれるかを識別する情報）を更新エレメントに含めて送信する。この情報はどのようなものであってもよい。典型的には、従来から知られているように、各更新エレメントを区切る区切り文字、及び、各更新エレメントの識別子が、各更新エレメントに含めて送信される。このような情報に基づいて、ナビゲーション端末２０は、受信した地図更新データのどこからどこまでが一つの更新エレメントに含まれるのかを特定することができ、それによって、一つの更新エレメントに含まれる全ての差分データ項目の、地図データへの反映が終了したか否かを判定することができる。
【００７１】
ナビゲーション端末２０の地図更新部２３は、更新エレメントを受信すると、それに基づいて地図データ記憶部２７に格納された地図データを更新する。このとき、地図更新部２３は、一つの更新エレメントに基づく地図データの更新を開始してからそれが終了するまで、ナビゲーション処理部２４がその地図データを用いた経路検索を実行することを禁止する。具体的には、例えば、ｌｉｎｋ１形状情報２５１Ａのｌｉｎｋ１形状情報−２＿２５１Ｂへの更新が終了したが、ｌｉｎｋ３形状情報２５３Ａ及びｌｉｎｋ４形状情報２５４Ａがまだ更新されていない時点の道路データを用いて経路検索をすることは許可される。しかし、ｌｉｎｋ３形状情報２５３Ａのｌｉｎｋ３形状情報−２＿２５３Ｂへの更新が終了したが、ｌｉｎｋ４形状情報２５４Ａのｌｉｎｋ４形状情報−２＿２５４Ｂへの更新が終了していない時点の道路データを用いて経路検索をすることは許可されない。
【００７２】
連続したリンクの形状を更新する必要があるにもかかわらず、その一部の更新のみが反映されている場合、実際の道路は連続しているにもかかわらず、その道路に対応する地図データ上のリンクが途切れているという矛盾が発生し得る。しかし、上記のように更新エレメントごとに更新を管理することによって、上記のような矛盾を含んだ地図データに基づく経路検索を避けることができる。
【００７３】
図４は、本発明の実施形態の地図データ配信システムにおける道路データの別の例の説明図である。
【００７４】
図４（ａ）には、有料区間とそれに連続する無料区間とを含む道路に関する道路データ（バージョン１）と、それらのうち有料区間が無料区間に変更された後の道路データ（バージョン２）と、を示す。
【００７５】
具体的には、バージョン１の道路データは、ｎｏｄｅ１＿４０１Ａ〜ｎｏｄｅ５＿４０５Ａの五つのノードと、ｌｉｎｋ１＿４１１Ａ〜ｌｉｎｋ３＿４１３Ａの三つのリンクによって表現される。ｌｉｎｋ１＿４１１Ａはｎｏｄｅ１＿４０１Ａとｎｏｄｅ２＿４０２Ａとを接続し、ｌｉｎｋ２＿４１２Ａはｎｏｄｅ２＿４０２Ａとｎｏｄｅ３＿４０３Ａとを接続し、ｌｉｎｋ３＿４１３Ａはｎｏｄｅ４＿４０４Ａとｎｏｄｅ５＿４０５Ａとを接続する。
【００７６】
この例において、ｌｉｎｋ２＿４１２Ａに対応する区間と、ｌｉｎｋ３＿４１３Ａに対応する区間とは、実際には連続しているが、それぞれの属性が異なる（前者の属性が有料道路、後者の属性が無料道路である）ため、これらは異なるリンク列に属する。すなわち、ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａはリンク列１＿４１０Ａに属し、ｌｉｎｋ３＿４１３Ａはリンク列２＿４３０Ａに属する。
【００７７】
このため、ｌｉｎｋ２＿４１２Ａに対応する区間とｌｉｎｋ３＿４１３Ａに対応する区間とを接続する交差点は、実際には単一の交差点であるが、地図データ上では、有料区間の終点であるｎｏｄｅ３＿４０３Ａ、及び、無料区間の始点であるｎｏｄｅ４＿４０４Ａ、の二つのノードとして扱われる。しかし、上記のように実際にはこれらのノードは同一の交差点に対応するため、実質的には同一のノードである。このため、本実施形態では、ｌｉｎｋ２＿４１２Ａとｌｉｎｋ３＿４１３Ａとは連続するリンクとして扱われる。
【００７８】
ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａに対応する区間が有料区間から無料区間に変更されると、この変更が反映されたバージョン２の道路データが作成される。具体的には、ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａを含むリンク列１＿４１０Ａのヘッダに含まれる属性情報が有料道路から無料道路に変更される。これによって図４に示す三つの区間の属性が同一になるため、ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａを含むリンク列１＿４１０Ａは、上記の三つの区間に対応する三つのリンクを含むリンク列１＿４１０Ｂに更新され、リンク列２＿４３０Ａは削除される。
【００７９】
具体的には、図４（ａ）に示すバージョン２のリンク列１＿４１０Ｂは、ｎｏｄｅ１＿４０１Ａ、ｎｏｄｅ２＿４０２Ａ、ｎｏｄｅ６＿４０６Ｂ及びｎｏｄｅ７＿４０７Ｂの四つのノードと、ｌｉｎｋ１＿４１１Ａ、ｌｉｎｋ２＿４１２Ａ及びｌｉｎｋ４＿４１４Ｂの三つのリンクと、を含む。
【００８０】
ｎｏｄｅ１＿４０１Ａ、ｎｏｄｅ２＿４０２Ａ、ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａはバージョン１と同じである。
【００８１】
ｎｏｄｅ６＿４０６Ｂは、ｌｉｎｋ２＿４１２Ａの終点ノードであり、バージョン１のｎｏｄｅ３＿４０３Ａ及びｎｏｄｅ４＿４０４Ａと同一の交差点に対応する。ｌｉｎｋ４＿４１４Ｂは、ｎｏｄｅ６＿４０６Ｂに接続されるリンクであり、バージョン１のｌｉｎｋ３＿４１３Ａと同一の区間に対応する。ｎｏｄｅ７＿４０７Ｂは、ｌｉｎｋ４＿４１４Ｂの終点ノードであり、ｎｏｄｅ５＿４０５Ａと同一の交差点に対応する。
【００８２】
図４（ｂ）は、図４（ａ）のノード及びリンクによって表現される道路データの具体的なフォーマットを示す。
【００８３】
図４（ｂ）の例において、バージョン１の道路データ４２０Ａは、リンク列１ヘッダ情報４２１Ａ、リンク列１リンク情報４２２Ａ、リンク列２ヘッダ情報４２３Ａ及びリンク列２リンク情報４２４Ａからなる。これらの情報に含まれる各項目の意味については、図２（ｂ）を参照して説明したとおりであるため、ここでは詳細な説明を省略する。
【００８４】
リンク列１ヘッダ情報４２１Ａは、道路種別４３１Ａ、路線番号４３２Ａ、及び、有料フラグ４３３Ａを含む。図４（ｂ）の例の有料フラグ４３３Ａは、リンク列１＿４１０Ａに対応する道路が有料道路であることを示している。
【００８５】
リンク列１リンク情報４２２Ａは、ｎｏｄｅ１ノード情報４４１Ａ〜ｎｏｄｅ３ノード情報４４３Ａ、ｌｉｎｋ１形状情報４５１Ａ〜ｌｉｎｋ２形状情報４５２Ａ、ｌｉｎｋ１通行規制情報４６１Ａ〜ｌｉｎｋ２通行規制情報４６２Ａ、及びｌｉｎｋ１その他情報４７１Ａ〜ｌｉｎｋ２その他情報４７２Ａを含む。
【００８６】
リンク列２ヘッダ情報４２３Ａは、道路種別４３４Ａ、路線番号４３５Ａ、及び、有料フラグ４３６Ａを含む。図４（ｂ）の例の有料フラグ４３６Ａは、リンク列２＿４３０Ａに対応する道路が無料道路であることを示している。
【００８７】
リンク列２リンク情報４２４Ａは、ｎｏｄｅ４ノード情報４４４Ａ〜ｎｏｄｅ５ノード情報４４５Ａ、ｌｉｎｋ３形状情報４５３Ａ、ｌｉｎｋ３通行規制情報４６３Ａ、及びｌｉｎｋ３その他情報４７３Ａを含む。
【００８８】
なお、既に説明したように、ｎｏｄｅ３＿４０３Ａとｎｏｄｅ４＿４０４Ａとは同一の交差点に対応する。このため、ｎｏｄｅ３＿４０３Ａに対応するｎｏｄｅ３ノード情報４４３Ａは、ｎｏｄｅ３＿４０３Ａがｎｏｄｅ４＿４０４Ａに接続していることを示す情報を含み、ｎｏｄｅ４＿４０４Ａに対応するｎｏｄｅ４ノード情報４４４Ａは、ｎｏｄｅ４＿４０４Ａがｎｏｄｅ３＿４０３Ａに接続していることを示す情報を含む。これらの情報を参照することによって、ｌｉｎｋ２＿４１２Ａとｌｉｎｋ３＿４１３Ａとが連続している、すなわち、図４の例においてｌｉｎｋ１＿４１１Ａからｌｉｎｋ３＿４１３Ａまでが連続している、と判定することができる。
【００８９】
一方、図４（ｂ）の例において、バージョン２の道路データ４２０Ｂは、リンク列１ヘッダ情報４２１Ｂ及びリンク列１リンク情報４２２Ｂからなる。
【００９０】
リンク列１ヘッダ情報４２１Ａは、道路種別４３１Ｂ、路線番号４３２Ｂ、及び、有料フラグ４３３Ｂを含む。図４（ｂ）の例の有料フラグ４３３Ｂは、リンク列１＿４１０Ｂに対応する道路が無料道路であることを示している。道路種別４３１Ｂ及び路線番号４３２Ｂは、それぞれ、バージョン１の道路種別４３１Ａ及び路線番号４３２Ａと同じである。
【００９１】
リンク列１リンク情報４２２Ｂは、ｎｏｄｅ１ノード情報４４１Ｂ〜ｎｏｄｅ２ノード情報４４２Ｂ、ｎｏｄｅ６ノード情報４４６Ｂ〜ｎｏｄｅ７ノード情報４４７Ｂ、ｌｉｎｋ１形状情報４５１Ｂ〜ｌｉｎｋ２形状情報４５２Ｂ、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ１通行規制情報４６１Ｂ〜ｌｉｎｋ２通行規制情報４６２Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、ｌｉｎｋ１その他情報４７１Ｂ〜ｌｉｎｋ２その他情報４７２Ｂ、及びｌｉｎｋ４その他情報４７４Ｂを含む。
【００９２】
ｎｏｄｅ１ノード情報４４１Ｂ〜ｎｏｄｅ２ノード情報４４２Ｂは、それぞれ、バージョン１のｎｏｄｅ１ノード情報４４１Ａ〜ｎｏｄｅ２ノード情報４４２Ａと同じである。ｌｉｎｋ１形状情報４５１Ｂ〜ｌｉｎｋ２形状情報４５２Ｂは、それぞれ、バージョン１のｌｉｎｋ１形状情報４５１Ａ〜ｌｉｎｋ２形状情報４５２Ａと同じである。ｌｉｎｋ１通行規制情報４６１Ｂ〜ｌｉｎｋ２通行規制情報４６２Ｂは、それぞれ、バージョン１のｌｉｎｋ１通行規制情報４６１Ａ〜ｌｉｎｋ２通行規制情報４６２Ａと同じである。ｌｉｎｋ１その他情報４７１Ｂ〜ｌｉｎｋ２その他情報４７２Ｂは、それぞれ、バージョン１のｌｉｎｋ１その他情報４７１Ａ〜ｌｉｎｋ２その他情報４７２Ａと同じである。
【００９３】
ｎｏｄｅ６ノード情報４４６Ｂは、ｎｏｄｅ６＿４０６Ｂに対応する交差点に関する情報を含む。ｎｏｄｅ６＿４０６Ｂに対応する交差点は、実際にはｎｏｄｅ３＿４０３Ａ及びｎｏｄｅ３＿４０３Ａに対応する交差点と同一であるため、ｎｏｄｅ６ノード情報４４６Ｂの内容は、ｎｏｄｅ３ノード情報４４３Ａ又はｎｏｄｅ４ノード情報４４４Ａの内容と同一である。
【００９４】
ｎｏｄｅ７ノード情報４４７Ｂは、ｎｏｄｅ７＿４０７Ｂに対応する交差点に関する情報を含む。ｎｏｄｅ７＿４０７Ｂに対応する交差点は、実際にはｎｏｄｅ５＿４０５Ａに対応する交差点と同一であるため、ｎｏｄｅ７ノード情報４４７Ｂの内容は、ｎｏｄｅ５ノード情報４４５Ａの内容と同一である。
【００９５】
ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、及びｌｉｎｋ４その他情報４７４Ｂは、それぞれ、ｌｉｎｋ４＿４１４Ｂに対応する区間の形状、通行規制及びその他の情報を含む。ｌｉｎｋ４＿４１４Ｂに対応する区間は、ｌｉｎｋ３＿４１３Ａに対応する区間と同一であるため、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、及びｌｉｎｋ４その他情報４７４Ｂの内容は、それぞれ、ｌｉｎｋ３形状情報４５３Ａ、ｌｉｎｋ３通行規制情報４６３Ａ、及びｌｉｎｋ３その他情報４７３Ａの内容と同一である。
【００９６】
図５は、道路データを更新するための更新エレメントの別の例の説明図である。
【００９７】
具体的には、図５は、図４に示す道路データに対応する更新エレメントの例を示す。この更新エレメントは、後述する図８に示す手順によって作成される。ただし、後述するように（図６参照）、図５に示す更新エレメントを用いた場合、リンク情報の更新に関する矛盾は発生しないが、ヘッダ情報の更新に関する矛盾が発生する可能性がある。以下、説明の便宜上、地図配信サーバ１０が図５に示す更新エレメントを作成するように説明するが、実際には、本発明の実施形態の地図配信サーバ１０は、さらに改善された更新エレメントを作成する（図７及び図９参照）。
【００９８】
ナビゲーション端末２０が図４に示すバージョン１の道路データ４２０Ａを保持している場合に、それをバージョン２の道路データ４２０Ｂに更新するためには、有料道路を示す有料フラグ４３３Ａを、無料道路を示す有料フラグ４３３Ｂに置き換えることを指示する情報、リンク列１リンク情報４２２Ａからｎｏｄｅ３ノード情報４４３Ａを削除することを指示する情報、リンク列２ヘッダ情報４２３Ａ及びリンク列２リンク情報４２４Ａの各項目を削除することを指示する情報、及び、リンク列１リンク情報４２２Ａにｎｏｄｅ６ノード情報４４６Ｂ、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、ｌｉｎｋ４その他情報４７４Ｂ及びｎｏｄｅ７ノード情報４４７Ｂを追加することを指示する情報を含む地図更新データが作成される。
【００９９】
この場合も、図３の場合と同様、単一の又は連続した区間に関する地図更新データが一つの更新エレメントとして作成される。
【０１００】
図５の例では、リンク列１＿４１０Ａの先頭に付与されたリンク列１ヘッダ情報４２１Ａに関する地図更新データが更新エレメント１＿５０１として作成される。すなわち、更新エレメント１＿５０１には、有料フラグ４３３Ａを有料フラグ４３３Ｂに更新することを指示する情報が含まれる。
【０１０１】
一方、ｌｉｎｋ３＿４１３Ａに関する情報が更新エレメント２＿５０２として作成される。
【０１０２】
具体的には、ｌｉｎｋ３形状情報４５３Ａ、ｌｉｎｋ３通行規制情報４６３Ａ及びｌｉｎｋ３その他情報４７３Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０３】
さらに、ｌｉｎｋ３＿４１３Ａの始点ノードであるｎｏｄｅ４＿４０４Ａに関するｎｏｄｅ４ノード情報４４４Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０４】
さらに、ｎｏｄｅ４＿４０４Ａと実質的に同一のノードであるｎｏｄｅ４＿４０４Ａに関するｎｏｄｅ３ノード情報４４３Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０５】
さらに、ｌｉｎｋ３＿４１３Ａの終点ノードであるｎｏｄｅ５＿４０５Ａに関するｎｏｄｅ５ノード情報４４５Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０６】
さらに、ｌｉｎｋ３＿４１３Ａがリンク列２＿４３０Ａの先頭のリンクであるであるため、リンク列２ヘッダ情報４２３Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０７】
道路データ４２０Ａ及び４２０Ｂを参照すると、ｎｏｄｅ４＿４０４Ａ及びｎｏｄｅ６＿４０６Ｂがいずれもｌｉｎｋ２＿４１２Ａの終点ノードであることがわかる。このため、これらのノードに接続されたｌｉｎｋ３＿４１３Ａ及びｌｉｎｋ４＿４１４Ｂは、同一の区間に対応するか、又は、連続する二つの区間にそれぞれ対応するか、のいずれかであると判定することができる（図４の例では同一の区間に対応している）。このため、更新エレメント２＿５０２は、さらに、ｌｉｎｋ４＿４１４Ｂに関する情報を含む。
【０１０８】
具体的には、さらに、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ及びｌｉｎｋ４その他情報４７４Ｂを追加することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０９】
さらに、ｌｉｎｋ４＿４１４Ｂの始点ノードであるｎｏｄｅ６＿４０６Ｂに関するｎｏｄｅ６ノード情報４４６Ｂを追加することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１１０】
さらに、ｌｉｎｋ４＿４１４Ｂの終点ノードであるｎｏｄｅ７＿４０７Ｂに関するｎｏｄｅ７ノード情報４４７Ｂを追加することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１１１】
図３の場合と同様、ナビゲーション端末２０は、自車の現在地（又は目的地）の周辺の所定の範囲内の地図データの更新を地図配信サーバ１０に要求してもよい。更新要求を受信した地図配信サーバ１０は、更新要求によって指定された範囲内の地物に関するデータを含む更新エレメントをナビゲーション端末２０に送信する。しかし、これによって更新後の地図データに矛盾が発生する場合がある。次に、この矛盾について説明する。
【０１１２】
図６は、更新エレメントごとの地図データの更新の説明図である。
【０１１３】
例えば、指定された範囲にｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ３＿４１３Ａの両方が含まれる場合、これらのリンクに関する更新データを含む更新エレメント１＿５０１及び更新エレメント２＿５０２の両方がナビゲーション端末２０に送信される。これらの更新エレメントに基づいて、ナビゲーション端末２０が保持する地図データは、図４に示すバージョン２に更新される。この場合、地図データに矛盾は発生しない。
【０１１４】
一方、例えば、指定された範囲にｌｉｎｋ１＿４１１Ａが含まれるが、ｌｉｎｋ３＿４１３Ａは含まれない場合、ｌｉｎｋ１＿４１１Ａに関する更新データを含む更新エレメント１＿５０１は送信されるが、それを含まない更新エレメント２＿５０２は送信されない。この場合、図６（ａ）に示すように、リンク列１＿４１０Ａのヘッダ情報が更新されるが、リンク列２＿４３０Ａ等の削除、及び、リンク列１＿４１０Ａへのｌｉｎｋ４＿４１４Ｂ等の追加は行われない。その結果、更新後のバージョン２の道路データは、図４に示したバージョン２とは異なっている。すなわち、図４に示すバージョン２の道路データがリンク列１＿４１０Ｂのみからなるのに対して、図６（ａ）のバージョン２の道路データは、リンク列１＿４１０Ｃ及びリンク列２＿４３０Ａからなる。
【０１１５】
しかし、図６（ａ）のバージョン２の各リンクの形状及び通行規制等に関する情報は、図４のバージョン２の各リンクのものと同一である。さらに、図６（ａ）に示す二つのリンク列の属性は、図４のバージョン２のリンク列１＿４１０Ｂと同様、無料道路である。このため、図６（ａ）のバージョン２の道路データを用いて経路検索を行ったとしても、図４のバージョン２の道路データを用いた場合と同様の結果を得ることができる。
【０１１６】
一方、例えば、指定された範囲にｌｉｎｋ１＿４１１Ａが含まれないが、ｌｉｎｋ３＿４１３Ａは含まれる場合、ｌｉｎｋ３＿４１３Ａに関する更新データを含む更新エレメント２＿５０２は送信されるが、それを含まない更新エレメント１＿５０１は送信されない。この場合、図６（ｂ）に示すように、リンク列２＿４３０Ａ等の削除、及び、リンク列１＿４１０Ａへのｌｉｎｋ４＿４１４Ｂ等の追加は行われるが、リンク列１＿４１０Ａのヘッダ情報は更新されない。その結果、更新後のバージョン２の道路データは、図４に示したバージョン２とは異なっている。すなわち、図４に示すバージョン２の道路データが無料道路であるリンク列１＿４１０Ｂからなるのに対して、図６（ｂ）のバージョン２の道路データは、有料道路であるリンク列１＿４１０Ｄからなる。
【０１１７】
図６（ｂ）の場合、更新要求がされた範囲内にｌｉｎｋ３＿４１３Ａが含まれていたということは、ｌｉｎｋ３＿４１３Ａに対応する更新後のｌｉｎｋ４＿４１４Ｂが経路検索の対象になる可能性があることを意味する。しかし、上記のように、更新後の道路データには、本来無料区間であるべきｌｉｎｋ４＿４１４Ｂが有料区間として扱われるという矛盾がある。このため、図６（ｂ）のバージョン２の道路データを用いて経路検索を行うと、図４のバージョン２の道路データを用いた場合と異なる結果が得られることになる。
【０１１８】
以下、このような矛盾の発生を防ぐ更新エレメントの作成について説明する。
【０１１９】
図７は、本発明の実施形態の地図データ配信システムにおける道路データを更新するための更新エレメントの説明図である。
【０１２０】
具体的には、図７は、ナビゲーション端末２０が図４に示すバージョン１の道路データ４２０Ａを保持している場合に、それをバージョン２に更新するために、本実施形態の地図配信サーバ１０が作成する更新エレメントを示す。
【０１２１】
図５に示す更新エレメント１＿５０１は、リンク列１＿４１０Ａのヘッダに含まれる項目の置き換えを指示する情報を含む。一方、更新エレメント２＿５０２は、リンク列１＿４１０Ａからノードを削除することを指示する情報、及び、リンク列１＿４１０Ａ（すなわち更新後のリンク列１＿４１０Ｂ）に新たなノード及びリンクを追加することを指示する情報を含む。このように、一つの更新エレメントがいずれかのリンク列のヘッダ情報の更新を指示する情報を含み、さらに、そのリンク列に含まれる別のデータ項目の更新を指示する情報が別の更新エレメントに含まれる場合、本実施形態の地図配信サーバ１０の更新データ抽出部１３は、それらの更新エレメントを一つの更新エレメントに統合する。
【０１２２】
具体的には、図７に示す更新エレメント１＿７０１は、図５に示す更新エレメント１＿５０１及び更新エレメント２＿５０２の両方の内容（すなわち、それらの更新エレメントに含まれる全ての差分データ項目）を含む。その結果、例えば、ナビゲーション端末２０からの更新要求によって指定された範囲にｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ３＿４１３Ａの両方が含まれる場合、ｌｉｎｋ１＿４１１Ａが含まれるがｌｉｎｋ３＿４１３Ａは含まれない場合、及び、指定された範囲にｌｉｎｋ１＿４１１Ａは含まれないがｌｉｎｋ３＿４１３Ａは含まれる場合、のいずれの場合であっても、本実施形態の地図配信サーバ１０は更新エレメント１＿７０１を送信する。
【０１２３】
図３の場合と同様、更新エレメント１＿７０１は、区切り文字及び更新エレメントの識別子のような、各差分データ項目が更新エレメント１＿７０１に含まれることを識別する情報を含む。既に説明したように、ナビゲーション端末２０のナビゲーション処理部２４は、一つの更新エレメントに基づく地図データの更新が開始されてからそれが終了するまでの間、その地図データに基づく経路検索を実行しない。すなわち、図７に示す更新エレメント１＿７０１を受信したナビゲーション端末２０は、更新エレメント１＿７０１に含まれる全ての差分データ項目の地図データへの反映が終了するまで、ナビゲーション処理部２４による経路検索を禁止する。
【０１２４】
このため、ナビゲーション端末２０からの更新要求によって指定された範囲にｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ３＿４１３Ａの両方が含まれる場合、又は、それらのうち一方のみが含まれる場合、のいずれの場合であっても、図６に示すものではなく、図４に示すバージョン２の道路データ４２０Ｂに基づく経路検索が実行される。これによって、図６に示すような矛盾した道路データに基づく誤った経路検索を防ぐことができる。
【０１２５】
図８は、更新エレメントを作成する手順を示すフローチャートである。
【０１２６】
図８に示す手順によって、図５に示す更新エレメントが作成される。本実施形態の地図配信サーバ１０の更新データ抽出部１３は、実際には、より改善された図９に示す手順によって更新エレメントを作成する。しかし、ここでは、説明の便宜上、図８に示す手順を更新データ抽出部１３が実行するように記載する。
【０１２７】
最初に、更新データ抽出部１３は、地図データ記憶部１６に格納されている新バージョンの道路データの各データ項目と、それぞれに対応する旧バージョンの道路データの各データ項目と、を対照して、差分項目を抽出する（ステップ８０１）。ここでは、例として、図４に示すバージョン１（旧バージョン）の道路データ４２０Ａ及びバージョン２（新バージョン）の道路データ４２０Ｂが地図データ記憶部１６に格納されている場合について説明する。
【０１２８】
図４に表示されている「リンク列１」の「１」、「ｎｏｄｅ１」の「１」、及び「ｌｉｎｋ１」の「１」等は、それぞれ、リンク列、ノード及びリンクの識別子である。図２等についても同様である。更新データ抽出部１３は、同一の識別子が付与された新旧のデータ項目を、対応するデータ項目として対照する。
【０１２９】
上記の対照の結果、新バージョンの項目の内容が旧バージョンと異なる場合、更新データ抽出部１３は、その項目を変更差分項目として抽出する。旧バージョンの項目が新バージョンでは削除されている場合、その項目を削除差分項目として抽出する。旧バージョンでは存在しない項目が新バージョンに含まれている場合、その項目を追加差分項目として抽出する。
【０１３０】
なお、ナビゲーション端末２０の地図更新部２３は、受信した更新エレメントに変更差分項目が含まれる場合、それが示すデータ項目の内容を新バージョンの内容に更新する。削除差分項目が含まれる場合、それが示す旧バージョンのデータ項目を地図データから削除する。追加差分項目が含まれる場合、それが示す新バージョンのデータ項目を地図データに追加する。
【０１３１】
図４の例では、有料道路を示す有料フラグ４３３Ａが無料道路を示す有料フラグ４３３Ｂによって置き換えられる。このため、これらのデータ項目が変更差分項目として抽出される。
【０１３２】
さらに、図４の例では、ｎｏｄｅ３ノード情報４４３Ａ、リンク列２ヘッダ情報４２３Ａに含まれる全データ項目、及び、リンク列２リンク情報４２４Ａに含まれる全データ項目が削除される。このため、これらのデータ項目が削除差分項目として抽出される。
【０１３３】
さらに、図４の例では、ｎｏｄｅ６ノード情報４４６Ｂ、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、ｌｉｎｋ４その他情報４７４Ｂ及びｎｏｄｅ７ノード情報４４７Ｂが追加される。このため、これらのデータ項目が追加差分項目として抽出される。
【０１３４】
次に、更新データ抽出部１３は、ステップ８０１が全てのデータ項目について終了したか否かを判定する（ステップ８０２）。全てのデータ項目についてステップ８０１が終了していない場合、更新データ抽出部１３は、残りのデータ項目についてステップ８０１を実行する。
【０１３５】
全てのデータ項目についてステップ８０１が終了した場合、更新データ抽出部１３は、ステップ８０１で抽出した差分項目のうち、同一の又は連続する区間に関する差分項目をまとめることによって、一つの更新エレメントを作成する（ステップ８０３）。
【０１３６】
図４の例では、ｎｏｄｅ３ノード情報４４３Ａ、リンク列２ヘッダ情報４２３Ａに含まれる全データ項目、及び、リンク列２リンク情報４２４Ａに含まれる全データ項目を削除することを指示する情報、及び、ｎｏｄｅ６ノード情報４４６Ｂ、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、ｌｉｎｋ４その他情報４７４Ｂ及びｎｏｄｅ７ノード情報４４７Ｂを追加することを指示する情報が、一つの更新エレメントとして作成される。これは、図５を参照して説明したとおりである。
【０１３７】
次に、更新データ抽出部１３は、ステップ８０３が全ての差分項目について終了したか否かを判定する（ステップ８０４）。全ての差分項目についてステップ８０３が終了していない場合、更新データ抽出部１３は、残りの差分項目についてステップ８０３を実行する。
【０１３８】
全ての差分項目についてステップ８０３が終了した場合、更新データ抽出部１３は、更新エレメントの作成を終了する。作成された更新エレメントは、更新データ記憶部１２に格納される。
【０１３９】
図４に示すデータが地図データ記憶部１６に格納されている場合、図５に示す二つの更新エレメントが作成され、更新データ記憶部１２に格納される。
【０１４０】
図９は、本発明の実施形態の地図配信サーバ１０が更新エレメントを作成する手順を示すフローチャートである。
【０１４１】
最初に、更新データ抽出部１３は、地図データ記憶部１６に格納されている新バージョン及び旧バージョンの道路データのデータ項目のうち、リンク情報に含まれる各データ項目に、各データ項目が属するリンク列のヘッダの識別子（リンク列ヘッダＩＤ）を付加する（ステップ９０１）。図８の説明と同様、例として、図４に示すバージョン１（旧バージョン）の道路データ４２０Ａ及びバージョン２（新バージョン）の道路データ４２０Ｂが地図データ記憶部１６に格納されている場合について説明する。
【０１４２】
図１０は、本発明の実施形態の地図配信サーバ１０によってリンクの識別子が付加された道路データを示す説明図である。
【０１４３】
図９のステップ９０１において、更新データ抽出部１３は、バージョン１の道路データ４２０Ａのリンク列１リンク情報４２２Ａの各データ項目に、それらのデータ項目が属するリンク列のヘッダ情報の識別子（すなわちリンク列ヘッダＩＤ）として「１」を付加する。これは、リンク列１＿４１０Ａの識別子に対応する。
【０１４４】
さらに、更新データ抽出部１３は、バージョン２の道路データ４２０Ｂのリンク列１リンク情報４２２Ｂの各データ項目に、それらのデータ項目が属するリンク列のヘッダ情報の識別子として「１」を付加する。これは、リンク列１＿４１０Ｂの識別子に対応する。
【０１４５】
さらに、更新データ抽出部１３は、バージョン１の道路データ４２０Ａのリンク列２リンク情報４２４Ａの各データ項目に、それらのデータ項目が属するリンク列のヘッダ情報の識別子として「２」を付加する。これは、リンク列２＿４３０Ａの識別子に対応する。
【０１４６】
次に、更新データ抽出部１３は、地図データ記憶部１６に格納されている新バージョンの道路データの各データ項目と、それぞれに対応する旧バージョンの道路データの各データ項目と、を対照して、差分項目を抽出する（ステップ９０２）。この手順は、リンク情報に含まれる各データ項目にリンク列ヘッダＩＤが付加されている点を除いて図８のステップ８０１と同じであるため、説明を省略する。
【０１４７】
次に、更新データ抽出部１３は、ステップ９０２が全てのデータ項目について終了したか否かを判定する（ステップ９０３）。全てのデータ項目についてステップ９０２が終了していない場合、更新データ抽出部１３は、残りのデータ項目についてステップ９０２を実行する。
【０１４８】
全てのデータ項目についてステップ９０２が終了した場合、更新データ抽出部１３は、ステップ９０２で抽出した差分項目のうち、同一の又は連続する区間に関する差分項目をまとめることによって、一つの更新エレメントを作成する（ステップ９０４）。この手順は、データ項目にリンク列ヘッダＩＤが付加されている点を除いて図８のステップ８０３と同じであるため、説明を省略する。ステップ９０４が終了した時点の更新エレメントの例を図１１に示す。
【０１４９】
図１１は、本発明の実施形態の更新エレメント作成処理の途中で作成されるデータの説明図である。
【０１５０】
図１１に示す更新エレメント１＿１１０１及び更新エレメント２＿１１０２は、リンク情報に含まれる各データ項目にリンク列ヘッダＩＤ（図１０参照）が付加されている点を除いて、それぞれ図５に示した更新エレメント１＿５０１及び更新エレメント２＿５０２と同じであるため、これらについての説明は省略する。
【０１５１】
次に、更新データ抽出部１３は、ステップ９０４が全ての差分項目について終了したか否かを判定する（ステップ９０５）。全ての差分項目についてステップ９０４が終了していない場合、更新データ抽出部１３は、残りの差分項目についてステップ９０４を実行する。
【０１５２】
全ての差分項目についてステップ９０４が終了した場合、更新データ抽出部１３は、リンク列ヘッダに関する差分データ項目がいずれかの更新エレメントに含まれるか否かを判定し、含まれる場合は、そのリンク列ヘッダの識別子が付加されたデータ項目を含む更新エレメントを検索する。この検索の結果、上記のリンク列ヘッダに関する差分データ項目を含む更新エレメント以外の更新エレメントが得られた場合、それらの更新エレメントを一つの更新エレメントにまとめることによって、一つの更新エレメントを作成する（ステップ９０６）。ステップ９０６が終了した時点の更新エレメントの例を図１２に示す。
【０１５３】
図１２は、本発明の実施形態の更新エレメント作成処理の途中で作成される別のデータの説明図である。
【０１５４】
図１１の例では、更新エレメント１＿１１０１に、リンク列１ヘッダ情報に含まれる有料フラグ４３３Ａ及び４３３Ｂが差分データ項目として含まれる。このため、更新データ抽出部１３は、リンク列１ヘッダ情報４２１Ａのリンク列ヘッダＩＤ「１」が付加されたデータ項目を含む更新エレメントを検索する。図１１の例では、更新エレメント２＿１１０２のリンク列１リンク情報４２２Ａ及び４２２Ｂの各データ項目にリンク列ヘッダＩＤ「１」が付加されている。このため、更新データ抽出部１３は、更新エレメント１＿１１０１及び更新エレメント２＿１１０２をまとめることによって、図１２に示す更新エレメント１＿１２０１を作成する。更新エレメント１＿１２０１は、リンク情報に含まれる各データ項目にリンク列ヘッダＩＤが付加されている点を除いて図７に示したものと同じであるため、これらについての説明は省略する。
【０１５５】
最後に、作成された更新エレメントに含まれる各データ項目から、ステップ９０１で付加したリンク列ヘッダＩＤを削除することによって、図７に示すような更新エレメントを作成し、更新データ記憶部１２に格納する（ステップ９０７）。以上で本実施形態の更新エレメントの作成処理が終了する。
【０１５６】
なお、図２に示す道路データが地図データ記憶部１６に格納されている場合、図８及び図９のいずれの手順を用いても、図３に示す更新エレメントを作成することができる。それらの更新エレメントがリンク列ヘッダに関するデータ項目を含まない（すなわち、新旧データのリンク列ヘッダが同一である）ためである。しかし、本実施形態の更新データ抽出部１３は、新旧データのリンク列ヘッダが異なる場合に図７のような更新エレメントを作成できるように、図９に示す手順によって更新エレメントを作成する。
【０１５７】
以上、本発明の実施形態によれば、通信する地図更新データの量を抑制しつつ、リンク列の属性の変更に起因する道路データの矛盾の発生を防止することができる。これによって、矛盾した道路データに基づく誤った経路検索が防止される。
【符号の説明】
【０１５８】
１０ 地図配信サーバ
１１、２６ 管理データ記憶部
１２ 更新データ記憶部
１３ 更新データ抽出部
１４ 更新データ管理部
１５、２１ ネットワークインターフェース（Ｉ／Ｆ）
１６、２７ 地図データ記憶部
１７、２８ プロセッサ
１８、２９ メモリ
２０ ナビゲーション端末
２２ 配信要求部
２３ 地図更新部
２４ ナビゲーション処理部
２５ 画面入出力Ｉ／Ｆ
３０ 無線通信装置
３１ 無線基地局
４０ ネットワーク
４１ インターネット
【技術分野】
【０００１】
本発明は、地図データを利用したサービスを利用者に提供する技術に関し、特に、ナビゲーション装置が保持する地図データを更新する技術に関する。
【背景技術】
【０００２】
ナビゲーション装置等が保持する地図データを更新する技術として、例えば特許文献１から特許文献３が知られている。
【０００３】
特許文献１によれば、更新される複数のリンクデータのうち、互いにネットワークとして接続されているものが一つの地図更新データとして管理される。指定された領域の地図データの更新が要求された場合、その領域に少なくとも一部が属する地図更新データによって地図データが更新される。これによって、更新後の道路ネットワークの接続性を保証しつつ、更新のために通信されるデータサイズを小さくすることができる。
【０００４】
特許文献２によれば、指定された領域の地図データの更新が要求された場合、指定された領域の差分更新データと、それが依存する更新データとが特定され、それらのうち古いものから順に更新が行われる。これによって、更新データ量を抑えつつ、所望の領域の地図データを最新の状態に更新し、かつ、指定された領域とそれに隣接する更新されない領域との整合性も保つことができる。
【０００５】
特許文献３によれば、リンクごとに、リンクデータが更新された日時を示す情報、及び、更新の影響が及ぶ範囲を示す情報がサーバに保持される。そして、端末が、指定された領域の地図データの更新を要求すると、サーバは、その領域内のリンク、及び、それらのリンクの更新の影響が及ぶリンクのうち、前回の更新要求より後に更新されたリンクのデータのみを端末に送信する。これによって、不要な通信トラフィックの発生を抑制し、かつ、更新後の地図に矛盾が生じないように地図データを更新することができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−９０１９５号公報
【特許文献２】特開２００７−２４１００３号公報
【特許文献３】国際公開第０６／０１１２７８号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
現在普及している一般的な車載用ナビゲーションシステムの地図データのフォーマットによれば、道路の属性（例えば、その道路が有料道路であるか否か、等）を示す情報は、道路の各区間に対応する各リンクデータにではなく、複数のリンクからなるリンク列に付与されたリンク列ヘッダに含まれる。このような場合において、リンク列の属性が変更された場合、上記特許文献１〜３に記載されたように地図データを更新すると、変更されたリンクの属性が正しく地図データに反映されない場合がある。
【０００８】
例えば、一続きの道路の一部が有料区間であり、それに続く残りの部分が無料区間である場合、有料区間と無料区間はそれぞれ別のリンク列として管理される。この場合、それぞれのリンク列に対応するリンク列ヘッダが保持され、有料区間に対応するリンク列ヘッダは有料道路を示す属性情報を含み、無料区間に対応するリンク列ヘッダは無料道路を示す属性情報を含む。その後、有料区間が無料区間に変更された場合、有料区間に対応するリンク列ヘッダの属性を無料道路に更新し、以前の無料区間に対応するリンク情報を削除し、その削除された無料区間に対応するリンク情報を、新たに無料区間に変更されたリンク列に追加する必要がある。これによって、属性の変更が正しく地図データに反映される。しかし、上記特許文献１〜３に記載された方法によれば、上記のリンク列ヘッダの更新、リンク情報の削除及び追加のうち一部のみが実行される場合がある。その場合、例えば更新後のすべてのリンクが有料区間として扱われるなど、地図データと実際の道路の状況との間に矛盾が発生することがある。
【０００９】
このようなフォーマットが使用される場合、リンクデータごとの更新を禁止し、常にリンク列ヘッダを含むリンク列全体を更新すれば、上記のような矛盾の発生を防ぐことができる。しかし、この場合、少数のリンクデータのみを更新する場合であっても常にリンク列全体のデータを通信する必要がある。加えて、上記特許文献１〜３に示すように、リンクの不連続などの問題の発生を防ごうとすれば、さらに多くのリンクデータを通信する必要が生じる。
【００１０】
本発明は上記の問題点に鑑みてなされたものであり、通信するデータ量の増加を抑制しつつ、上記のようなリンクの属性の矛盾の発生を防止する地図データの更新を実現することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、ネットワークに接続される地図データ配信サーバであって、前記地図データ配信サーバは、前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、第１の道路データと、前記第１の道路データより新しいバージョンである第２の道路データと、を保持し、前記第１の道路データと第２の道路データとをデータ項目ごとに比較することによって、前記第１の道路データと前記第２の道路データとの間の差分データ項目を作成し、各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成し、前記複数の更新エレメントのうち第１の更新エレメントが、第１のリンク列の属性に関する差分データ項目を含み、かつ、前記複数の更新エレメントのうち第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記第１の更新エレメント及び前記第２の更新エレメントに含まれる全ての前記差分データ項目を含む第３の更新エレメントを作成し、前記ネットワークに接続された端末装置から受信した地図更新要求が、前記第３の更新エレメント内の前記差分データ項目に関するリンクを含む地図上の範囲を指定した場合、前記第３の更新エレメントを前記端末装置に送信することを特徴とする。
【発明の効果】
【００１２】
本発明の一実施形態によれば、地図データの更新の際に、通信するデータ量の増加を抑制しつつ、リンクの属性の矛盾が発生することを防止することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態の地図データ配信システムの構成を示すブロック図である。
【図２】本発明の実施形態の地図データ配信システムにおける道路データの説明図である。
【図３】道路データを更新するための更新エレメントの説明図である。
【図４】本発明の実施形態の地図データ配信システムにおける道路データの別の例の説明図である。
【図５】道路データを更新するための更新エレメントの別の例の説明図である。
【図６】更新エレメントごとの地図データの更新の説明図である。
【図７】本発明の実施形態の地図データ配信システムにおける道路データを更新するための更新エレメントの説明図である。
【図８】更新エレメントを作成する手順を示すフローチャートである。
【図９】本発明の実施形態の地図配信サーバが更新エレメントを作成する手順を示すフローチャートである。
【図１０】本発明の実施形態の地図配信サーバによってリンクの識別子が付加された道路データを示す説明図である。
【図１１】本発明の実施形態の更新エレメント作成処理の途中で作成されるデータの説明図である。
【図１２】本発明の実施形態の更新エレメント作成処理の途中で作成される別のデータの説明図である。
【発明を実施するための形態】
【００１４】
以下、図面を用いて本発明の実施の形態を説明する。
【００１５】
図１は、本発明の実施形態の地図データ配信システムの構成を示すブロック図である。
【００１６】
本実施形態の地図データ配信システムは、ネットワーク４０に接続された地図配信サーバ１０と、ネットワーク４０を介して地図配信サーバ１０と通信するナビゲーション端末２０と、を備える。
【００１７】
地図配信サーバ１０は、互いに接続されたプロセッサ１７、メモリ１８、ネットワークインターフェース（Ｉ／Ｆ）１５、管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１６を備える計算機である。
【００１８】
プロセッサ１７は、メモリ１８に格納されたプログラムを実行する。
【００１９】
メモリ１８は、例えば半導体メモリであり、プロセッサ１７によって実行されるプログラム及びプロセッサ１７によって参照されるデータ等を格納する。本実施形態のメモリ１８には、更新データ抽出部１３及び更新データ管理部１４が格納される。これらのプログラムの処理については後述する。以下の説明において更新データ抽出部１３及び更新データ管理部１４が実行する処理は、実際には、プロセッサ１７によって実行される。
【００２０】
ネットワークＩ／Ｆ１５は、ネットワーク４０に接続され、ナビゲーション端末２０等と通信する。
【００２１】
管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１６は、ハードディスクドライブ（ＨＤＤ）またはフラッシュメモリのような記憶装置であってもよいし、そのような記憶装置内の記憶領域であってもよい。
【００２２】
地図データ記憶部１６には、地図データが格納される。地図データは、地図の構成物（地物）の位置及び形状を示す座標値等を含む。現実の地物は随時更新される。その一例は、道路の新設、廃止又は付け替えのような道路ネットワークの更新である。地図データは、過去のある時点における地物に関する情報（例えば後述するバージョン１の道路データ）と、それより後の時点における地物に関する情報（例えば後述するバージョン２の道路データ）と、を含んでもよい。
【００２３】
なお、一般に地図データは、地図上の所定の矩形の範囲ごとに管理される。この矩形の範囲は、パーセル又はメッシュと呼ばれる。各パーセルには固有の識別子（パーセルＩＤ）が付与される。
【００２４】
更新データ記憶部１２には、地物を単位とする地図更新データ（地図情報及び道路ネットワーク情報を含む）が格納される。地図更新データは、例えばナビゲーション端末２０がバージョン１の地図データを保持している場合に、それをより新しいバージョン２の地図データに更新するために作成及び送信されるデータであり、具体的には、少なくともこれらのバージョンの差分データを含む。地図更新データの詳細については後述する。
【００２５】
管理データ記憶部１１には、地図更新データを管理するための情報が格納される。例えば、管理データ記憶部１１には、地図更新データのバージョン（すなわち差分の世代）を示す情報、及び、地図更新データが適用されるべき位置を示すパーセルＩＤ等が格納される。
【００２６】
ナビゲーション端末２０は、ユーザを目的地まで誘導するために、経路検索及び検索結果の出力等を行う移動端末である。本実施形態では典型的な例として、ナビゲーション端末２０が自動車に搭載される車載用ナビゲーション端末である場合について説明するが、例えば歩行者に携帯されるナビゲーション端末等、種々の移動端末に本発明を適用することができる。
【００２７】
本実施形態のナビゲーション端末２０は、互いに接続されたプロセッサ２８、メモリ２９、ネットワークＩ／Ｆ２１、画面入出力Ｉ／Ｆ２５、管理データ記憶部２６及び地図データ記憶部２７を備える。
【００２８】
プロセッサ２８は、メモリ２９に格納されたプログラムを実行する。
【００２９】
メモリ２９は、例えば半導体メモリであり、プロセッサ２８によって実行されるプログラム及びプロセッサ２８によって参照されるデータ等を格納する。本実施形態のメモリ２９には、配信要求部２２、地図更新部２３及びナビゲーション処理部２４が格納される。
【００３０】
配信要求部２２は、地図更新データの配信要求（以下、地図データ更新要求と記載）を地図配信サーバ１０に送信する。地図更新部２３は、配信された地図更新データを用いて、地図データ記憶部２７に格納された地図データを更新する。これらの処理については後述する。以下の説明において配信要求部２２、地図更新部２３及びナビゲーション処理部２４が実行する処理は、実際にはプロセッサ２８によって実行される。
【００３１】
ナビゲーション処理部２４は、地図データ記憶部２７に格納された地図データに基づいて、目的地までの経路を検索し、その経路に沿ってユーザを誘導する。このような経路検索及び誘導は従来の車載用ナビゲーション端末と同様であるため、これらに関する詳細な説明は省略する。
【００３２】
画面入出力Ｉ／Ｆ２５は、ユーザに対して地図情報等を表示する画面と、ユーザからの入力を受け付ける入力装置と、を含む。例えば、画面入出力Ｉ／Ｆ２５は、タッチパッド付きの液晶表示装置であってもよい。
【００３３】
ネットワークＩ／Ｆ２１は、無線通信装置３０に接続される。無線通信装置３０は、ネットワーク４０に接続された無線基地局３１と無線通信を行う。ネットワークＩ／Ｆ２１は、無線通信装置３０、無線基地局３１及びネットワーク４０を介して地図配信サーバ１０との間の通信を実行する。後述する地図データ更新要求の送信（５１）及び地図更新データの受信（５２）はこのような通信によって実現される。
【００３４】
なお、無線通信装置３０は、ナビゲーション端末２０に内蔵されてもよい。
【００３５】
管理データ記憶部２６及び地図データ記憶部２７は、ハードディスクドライブ（ＨＤＤ）またはフラッシュメモリのような記憶装置であってもよいし、そのような記憶装置内の記憶領域であってもよい。
【００３６】
地図データ記憶部２７には、ナビゲーション処理部２４によって参照される地図データが格納される。この地図データは、地図配信サーバ１０から送信された地図更新データに基づいて更新される。
【００３７】
管理データ記憶部２６には、地図データを管理するための情報が格納される。例えば、管理データ記憶部２６には、自車（すなわちナビゲーション端末２０を搭載している車）の位置がどのパーセルに属するかを示す緯度経度−パーセルＩＤ対応情報、及び、地図に適用した地図更新データの識別情報等が格納される。
【００３８】
ネットワーク４０はインターネット４１に接続される。地図配信サーバ１０は、インターネット４１を介して新しいバージョンの地図データを取得してもよい。
【００３９】
図２は、本発明の実施形態の地図データ配信システムにおける道路データの説明図である。
【００４０】
ナビゲーション端末２０は、地図データ記憶部２７に地図データを保持し、それに基づいて経路検索等を実行する。一方、地図配信サーバ１０は、現実の道路ネットワークの変更等が反映された新バージョンの地図データを取得すると、それに基づいて、ナビゲーション端末２０が保持している旧バージョンの地図データを新バージョンに更新するための地図更新データを作成し、それを更新データ記憶部１２に格納する。図２には、地図データ記憶部１６に格納される地図データの例として、旧バージョン（Ｖｅｒ．１）と新バージョン（Ｖｅｒ．２）の地図データを示す。
【００４１】
なお、一般に地図データは、道路ネットワークに関するデータ（道路データ）に加えて、道路以外の地物、例えば建物、河川及び行政区等に関するデータも含む。しかし、図２には本実施形態の説明のために必要な道路データのみを示し、その他のデータについては図示を省略する。図３以降についても同様である。
【００４２】
周知のように、地図データ上で、道路は、ノードとリンクとの組み合わせによって表現される。ノードは交差点に、リンクは二つの交差点を接続する道路の区間に対応する。
【００４３】
図２（ａ）は、例として、五つの交差点と、それらを接続する四つの区間と、からなる有料道路を表現するノード及びリンクを示す。図２（ａ）に示すバージョン１（Ｖｅｒ．１）の道路データは、ｎｏｄｅ１＿２０１Ａ〜ｎｏｄｅ５＿２０５Ａの五つのノードと、ｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａの四つのリンクによって表現される。ｌｉｎｋ１＿２１１Ａはｎｏｄｅ１＿２０１Ａとｎｏｄｅ２＿２０２Ａとを接続し、ｌｉｎｋ２＿２１２Ａはｎｏｄｅ２＿２０２Ａとｎｏｄｅ３＿２０３Ａとを接続し、ｌｉｎｋ３＿２１３Ａはｎｏｄｅ３＿２０３Ａとｎｏｄｅ４＿２０４Ａとを接続し、ｌｉｎｋ４＿２１４Ａはｎｏｄｅ４＿２０４Ａとｎｏｄｅ５＿２０５Ａとを接続する。
【００４４】
以下の説明において、二つの区間が一つの交差点に接続されている場合、それらの区間を連続する区間と記載し、それらの区間に対応するリンクを連続するリンクと記載する。例えば図２（ａ）においてｎｏｄｅ２＿２０２Ａに接続されるｌｉｎｋ１＿２１１Ａとｌｉｎｋ２＿２１２Ａとは連続する。同様に、ｌｉｎｋ２＿２１２Ａとｌｉｎｋ３＿２１３Ａとは連続し、ｌｉｎｋ３＿２１３Ａとｌｉｎｋ４＿２１４Ａとは連続する。結局、ｌｉｎｋ１＿２１１Ａからｌｉｎｋ４＿２１４Ａまでの四つのリンクは連続している。
【００４５】
バージョン１の道路データが作成された後、実際の道路が付け替え等によって変更された場合、その変更が反映された道路データ、すなわちバージョン２（Ｖｅｒ．２）の道路データが作成される。図２の例では、ｌｉｎｋ１＿２１１Ａ、ｌｉｎｋ３＿２１３Ａ及びｌｉｎｋ４＿２１４Ａに対応する区間の道路の形状が変更されたため、これらのリンクがバージョン２ではそれぞれｌｉｎｋ１＿２１１Ｂ、ｌｉｎｋ３＿２１３Ｂ及びｌｉｎｋ４＿２１４Ｂによって置き換えられている。バージョン２のその他のリンク及びノードはバージョン１と同じである。
【００４６】
道路データは、さらに、道路の属性を示す情報を含む。道路の属性を示す情報は、例えば道路の種別（例えば国道又は県道）、路線番号、又はその道路が有料道路又は無料道路のいずれであるか、等の属性を示す情報を含むが、上記以外の属性を示す情報を含んでもよい。一般に、連続する複数のリンクの属性が共通する場合が多い。例えば、ある有料道路の始点から終点までのすべてのリンクは、有料道路という属性を有する。
【００４７】
図２に示す道路データにおいて、属性が共通する複数の連続したリンク及びそれらに接続されるノードが一つのリンク列として扱われ、属性を示す情報はリンク列ごとに付与される。図２（ａ）の例において、バージョン１のｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａの四つのリンクは一つのリンク列（すなわちバージョン１のリンク列１＿２１０Ａ）として扱われ、バージョン２のｌｉｎｋ１＿２１１Ｂ〜ｌｉｎｋ４＿２１４Ｂの四つのリンクも一つのリンク列（すなわちバージョン２のリンク列１＿２１０Ｂ）として扱われる。
【００４８】
図２（ｂ）は、図２（ａ）のノード及びリンクによって表現される道路データの具体的なフォーマットを示す。
【００４９】
図２（ｂ）の例において、バージョン１の道路データ２２０Ａは、リンク列１ヘッダ情報２２１Ａ及びリンク列１リンク情報２２２Ａからなる。
【００５０】
リンク列１ヘッダ情報２２１Ａは、リンク列１＿２１０Ａの属性（すなわち、リンク列１＿２１０Ａに含まれるすべてのリンクの属性）を示す情報を含む。図２（ｂ）の例において、リンク列１ヘッダ情報２２１Ａは、道路種別２３１Ａ、路線番号２３２Ａ、及び、有料フラグ２３３Ａを含む。道路種別２３１Ａは、そのリンク列１＿２１０Ａに対応する道路の種別、例えばそれが国道であるか県道であるか等を示す情報である。路線番号２３２Ａは、その道路に付与された番号、例えば国道番号を示す情報である。有料フラグ２３３Ａは、その道路が有料道路であるか無料道路であるかを示す情報である。図２（ｂ）の例の有料フラグ２３３Ａは、その道路が有料道路であることを示している。
【００５１】
リンク列１リンク情報２２２Ａは、リンク列１＿２１０Ａに含まれるノード及びリンクに関する情報を含む。図２（ｂ）の例において、リンク列１リンク情報２２２Ａは、ｎｏｄｅ１ノード情報２４１Ａ〜ｎｏｄｅ５ノード情報２４５Ａ、ｌｉｎｋ１形状情報２５１Ａ〜ｌｉｎｋ４形状情報２５４Ａ、ｌｉｎｋ１通行規制情報２６１Ａ〜ｌｉｎｋ４通行規制情報２６４Ａ、及びｌｉｎｋ１その他情報２７１Ａ〜ｌｉｎｋ４その他情報２７４Ａを含む。
【００５２】
ｎｏｄｅ１ノード情報２４１Ａ〜ｎｏｄｅ５ノード情報２４５Ａは、それぞれ、ｎｏｄｅ１＿２０１Ａ〜ｎｏｄｅ５＿２０５Ａに対応する交差点に関する情報、例えばそれらの交差点の座標を示す情報等を含む。
【００５３】
ｌｉｎｋ１形状情報２５１Ａ〜ｌｉｎｋ４形状情報２５４Ａは、それぞれ、ｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａに対応する区間の道路の形状を示す情報を含む。例えば、この情報は、それらの区間の道路上の一つ以上の点の座標を示す情報等を含んでもよい。
【００５４】
ｌｉｎｋ１通行規制情報２６１Ａ〜ｌｉｎｋ４通行規制情報２６４Ａは、それぞれ、ｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａに対応する区間の通行規制に関する情報を含む。
【００５５】
ｌｉｎｋ１その他情報２７１Ａ〜ｌｉｎｋ４その他情報２７４Ａは、それぞれ、ｌｉｎｋ１＿２１１Ａ〜ｌｉｎｋ４＿２１４Ａに対応する区間に関するその他の情報、例えばそれらの区間の通過に要する時間に関する情報等を含む。
【００５６】
なお、上記は道路データに含まれる情報の一例に過ぎず、実際の道路データは道路に関するさらに詳細な情報を含んでもよい。
【００５７】
図２（ａ）に示すように、バージョン１のリンク列１＿２１０Ａのｌｉｎｋ１＿２１１Ａ、ｌｉｎｋ３＿２１３Ａ及びｌｉｎｋ４＿２１４Ａに対応する区間の道路の形状が変更されたため、これらのリンクが、バージョン２ではそれぞれｌｉｎｋ１＿２１１Ｂ、ｌｉｎｋ３＿２１３Ｂ及びｌｉｎｋ４＿２１４Ｂによって置き換えられている。このため、バージョン２の道路データ２２０Ｂは、上記の三つのリンクの形状を示す情報を除いてバージョン１の道路データ２２０Ａと同じである。
【００５８】
具体的には、ｌｉｎｋ１形状情報２５１Ａ、ｌｉｎｋ３形状情報２５３Ａ及びｌｉｎｋ４形状情報２５４Ａが、それぞれ、変更された後の形状を示すｌｉｎｋ１形状情報−２＿２５１Ｂ、ｌｉｎｋ３形状情報−２＿２５３Ｂ及びｌｉｎｋ４形状情報−２＿２５４Ｂによって置き換えられる。リンク列１リンク情報２２２Ｂのうち、これらの三つのリンクの形状情報以外の部分は、リンク列１リンク情報２２２Ａと同じである。
【００５９】
図２に示したようにリンク列ごとに属性情報が付与される道路データのフォーマットとして、ＫＩＷＩフォーマットが知られている。本発明は、ＫＩＷＩフォーマットに適用することができるが、リンク列ごとに属性情報が付与される限り、ＫＩＷＩフォーマット以外のフォーマットにも適用することができる。
【００６０】
図３は、道路データを更新するための更新エレメントの説明図である。
【００６１】
具体的には、図３は、図２に示す道路データに対応する更新エレメントの例を示す。
【００６２】
図２に示すバージョン１の道路データ２２０Ａを保持している地図配信サーバ１０は、新たにバージョン２の道路データ２２０Ｂを取得すると、バージョン１の道路データ２２０Ａをバージョン２の道路データ２２０Ｂに更新するための地図更新データを作成して更新データ記憶部１２に格納する。格納された地図更新データは、ナビゲーション端末２０からの要求に応じて送信される。
【００６３】
このような地図更新データは、バージョン２の道路データ２２０Ｂ全体を含んでもよい。しかし、例えばナビゲーション端末２０が移動しながら無線によるパケット通信等を利用して現在地周辺の地図データを更新する場合には、迅速性が要求される。また、通信するデータ量に課金される場合、通信コストを抑制するためにデータ量を抑制することが望ましい。これらの観点から、地図更新データの量は少ないことが望ましい。このため、本実施形態の地図配信サーバ１０は、新旧の道路データの差分のみを地図更新データとして作成する。
【００６４】
図２の例では、二つの道路データの差分はｌｉｎｋ１形状情報−２＿２５１Ｂ、ｌｉｎｋ３形状情報−２＿２５３Ｂ及びｌｉｎｋ４形状情報−２＿２５４Ｂのみである。このため、地図配信サーバ１０は、ｌｉｎｋ１形状情報２５１Ａをｌｉｎｋ１形状情報−２＿２５１Ｂに更新することを指示する情報を地図更新データとして作成する。この情報は、例えば、更新されたｌｉｎｋ１＿２１１Ｂに対応する区間の道路の座標値を示す情報を含む。同様に、地図配信サーバ１０は、ｌｉｎｋ３形状情報２５３Ａをｌｉｎｋ３形状情報−２＿２５３Ｂに更新することを指示する情報、及び、ｌｉｎｋ４形状情報２５４Ａをｌｉｎｋ４形状情報−２＿２５４Ｂに更新することを指示する情報を地図更新データとして作成する。
【００６５】
本実施形態では、原則として、一つのデータ項目を更新するための地図更新データが一つの更新エレメントとして扱われる。ここで一つのデータ項目とは、図２（ｂ）に示す地図データの各項目、すなわち、各行に対応する項目である。例えば、有料フラグ２３３Ａ、ｌｉｎｋ１形状情報２５１Ａ及びｎｏｄｅ３ノード情報２４３Ａは、それぞれ、一つのデータ項目である。図３の例では、ｌｉｎｋ１形状情報２５１Ａをｌｉｎｋ１形状情報−２＿２５１Ｂに更新することを指示する情報が更新エレメント１＿３０１として扱われる。
【００６６】
ただし、上記のように作成した地図更新データが、単一の区間又は連続した複数の区間に関する情報を含む場合、それらの区間に関する更新データが一つの更新エレメントとして扱われる。ここで、ある区間に関する情報には、その区間に対応するリンクの形状等に関する情報、そのリンクの始点ノード及び終点ノードに関する情報が含まれ、そのリンクがリンク列の先頭リンクである場合、そのリンク列のヘッダ情報も含まれる。
【００６７】
図３の例では、ｌｉｎｋ３形状情報２５３Ａをｌｉｎｋ３形状情報−２＿２５３Ｂに更新することを指示する情報、及び、ｌｉｎｋ４形状情報２５４Ａをｌｉｎｋ４形状情報−２＿２５４Ｂに更新することを指示する情報が、一つの更新エレメント、すなわち更新エレメント２＿３０２として扱われる。地図配信サーバ１０は、このように作成した更新エレメントをナビゲーション端末２０に送信する。
【００６８】
例えばナビゲーション端末２０は、自車の現在地（又は目的地）の周辺の所定の範囲内の地図データの更新を地図配信サーバ１０に要求してもよい（図１のステップ５１）。具体的には、例えばユーザが地図データの更新要求を画面入出力Ｉ／Ｆに入力すると、ナビゲーション端末２０の配信要求部２２が管理データ記憶部２６を参照して自車の位置を含むパーセルのＩＤを特定し、そのパーセルの地図データの更新要求を地図配信サーバ１０に送信する。あるいは配信要求部２２が自動的に（例えば定期的に又は所定の条件が満たされたときに）地図データの更新要求を地図配信サーバに送信してもよい。
【００６９】
更新要求を受信した地図配信サーバ１０は、更新要求によって指定されたパーセル内の地物に関するデータを含む更新エレメントをナビゲーション端末２０に送信する（図１のステップ５２）。例えば、指定されたパーセルにｌｉｎｋ１＿２１１Ａに対応する区間とｌｉｎｋ３＿２１３Ａに対応する区間との両方が含まれる場合、地図配信サーバ１０は更新エレメント１＿３０１及び更新エレメント２＿３０２の両方を地図更新データとしてナビゲーション端末２０に送信する。一方、指定されたパーセルにｌｉｎｋ１＿２１１Ａに対応する区間が含まれるが、ｌｉｎｋ３＿２１３Ａに対応する区間は含まれない場合、地図配信サーバ１０は更新エレメント１＿３０１をナビゲーション端末２０に送信するが、更新エレメント２＿３０２は送信しない。
【００７０】
なお、地図配信サーバ１０は、各差分データ項目を含む更新エレメントを識別する情報（すなわち、各差分データ項目がどの更新エレメントに含まれるかを識別する情報）を更新エレメントに含めて送信する。この情報はどのようなものであってもよい。典型的には、従来から知られているように、各更新エレメントを区切る区切り文字、及び、各更新エレメントの識別子が、各更新エレメントに含めて送信される。このような情報に基づいて、ナビゲーション端末２０は、受信した地図更新データのどこからどこまでが一つの更新エレメントに含まれるのかを特定することができ、それによって、一つの更新エレメントに含まれる全ての差分データ項目の、地図データへの反映が終了したか否かを判定することができる。
【００７１】
ナビゲーション端末２０の地図更新部２３は、更新エレメントを受信すると、それに基づいて地図データ記憶部２７に格納された地図データを更新する。このとき、地図更新部２３は、一つの更新エレメントに基づく地図データの更新を開始してからそれが終了するまで、ナビゲーション処理部２４がその地図データを用いた経路検索を実行することを禁止する。具体的には、例えば、ｌｉｎｋ１形状情報２５１Ａのｌｉｎｋ１形状情報−２＿２５１Ｂへの更新が終了したが、ｌｉｎｋ３形状情報２５３Ａ及びｌｉｎｋ４形状情報２５４Ａがまだ更新されていない時点の道路データを用いて経路検索をすることは許可される。しかし、ｌｉｎｋ３形状情報２５３Ａのｌｉｎｋ３形状情報−２＿２５３Ｂへの更新が終了したが、ｌｉｎｋ４形状情報２５４Ａのｌｉｎｋ４形状情報−２＿２５４Ｂへの更新が終了していない時点の道路データを用いて経路検索をすることは許可されない。
【００７２】
連続したリンクの形状を更新する必要があるにもかかわらず、その一部の更新のみが反映されている場合、実際の道路は連続しているにもかかわらず、その道路に対応する地図データ上のリンクが途切れているという矛盾が発生し得る。しかし、上記のように更新エレメントごとに更新を管理することによって、上記のような矛盾を含んだ地図データに基づく経路検索を避けることができる。
【００７３】
図４は、本発明の実施形態の地図データ配信システムにおける道路データの別の例の説明図である。
【００７４】
図４（ａ）には、有料区間とそれに連続する無料区間とを含む道路に関する道路データ（バージョン１）と、それらのうち有料区間が無料区間に変更された後の道路データ（バージョン２）と、を示す。
【００７５】
具体的には、バージョン１の道路データは、ｎｏｄｅ１＿４０１Ａ〜ｎｏｄｅ５＿４０５Ａの五つのノードと、ｌｉｎｋ１＿４１１Ａ〜ｌｉｎｋ３＿４１３Ａの三つのリンクによって表現される。ｌｉｎｋ１＿４１１Ａはｎｏｄｅ１＿４０１Ａとｎｏｄｅ２＿４０２Ａとを接続し、ｌｉｎｋ２＿４１２Ａはｎｏｄｅ２＿４０２Ａとｎｏｄｅ３＿４０３Ａとを接続し、ｌｉｎｋ３＿４１３Ａはｎｏｄｅ４＿４０４Ａとｎｏｄｅ５＿４０５Ａとを接続する。
【００７６】
この例において、ｌｉｎｋ２＿４１２Ａに対応する区間と、ｌｉｎｋ３＿４１３Ａに対応する区間とは、実際には連続しているが、それぞれの属性が異なる（前者の属性が有料道路、後者の属性が無料道路である）ため、これらは異なるリンク列に属する。すなわち、ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａはリンク列１＿４１０Ａに属し、ｌｉｎｋ３＿４１３Ａはリンク列２＿４３０Ａに属する。
【００７７】
このため、ｌｉｎｋ２＿４１２Ａに対応する区間とｌｉｎｋ３＿４１３Ａに対応する区間とを接続する交差点は、実際には単一の交差点であるが、地図データ上では、有料区間の終点であるｎｏｄｅ３＿４０３Ａ、及び、無料区間の始点であるｎｏｄｅ４＿４０４Ａ、の二つのノードとして扱われる。しかし、上記のように実際にはこれらのノードは同一の交差点に対応するため、実質的には同一のノードである。このため、本実施形態では、ｌｉｎｋ２＿４１２Ａとｌｉｎｋ３＿４１３Ａとは連続するリンクとして扱われる。
【００７８】
ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａに対応する区間が有料区間から無料区間に変更されると、この変更が反映されたバージョン２の道路データが作成される。具体的には、ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａを含むリンク列１＿４１０Ａのヘッダに含まれる属性情報が有料道路から無料道路に変更される。これによって図４に示す三つの区間の属性が同一になるため、ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａを含むリンク列１＿４１０Ａは、上記の三つの区間に対応する三つのリンクを含むリンク列１＿４１０Ｂに更新され、リンク列２＿４３０Ａは削除される。
【００７９】
具体的には、図４（ａ）に示すバージョン２のリンク列１＿４１０Ｂは、ｎｏｄｅ１＿４０１Ａ、ｎｏｄｅ２＿４０２Ａ、ｎｏｄｅ６＿４０６Ｂ及びｎｏｄｅ７＿４０７Ｂの四つのノードと、ｌｉｎｋ１＿４１１Ａ、ｌｉｎｋ２＿４１２Ａ及びｌｉｎｋ４＿４１４Ｂの三つのリンクと、を含む。
【００８０】
ｎｏｄｅ１＿４０１Ａ、ｎｏｄｅ２＿４０２Ａ、ｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ２＿４１２Ａはバージョン１と同じである。
【００８１】
ｎｏｄｅ６＿４０６Ｂは、ｌｉｎｋ２＿４１２Ａの終点ノードであり、バージョン１のｎｏｄｅ３＿４０３Ａ及びｎｏｄｅ４＿４０４Ａと同一の交差点に対応する。ｌｉｎｋ４＿４１４Ｂは、ｎｏｄｅ６＿４０６Ｂに接続されるリンクであり、バージョン１のｌｉｎｋ３＿４１３Ａと同一の区間に対応する。ｎｏｄｅ７＿４０７Ｂは、ｌｉｎｋ４＿４１４Ｂの終点ノードであり、ｎｏｄｅ５＿４０５Ａと同一の交差点に対応する。
【００８２】
図４（ｂ）は、図４（ａ）のノード及びリンクによって表現される道路データの具体的なフォーマットを示す。
【００８３】
図４（ｂ）の例において、バージョン１の道路データ４２０Ａは、リンク列１ヘッダ情報４２１Ａ、リンク列１リンク情報４２２Ａ、リンク列２ヘッダ情報４２３Ａ及びリンク列２リンク情報４２４Ａからなる。これらの情報に含まれる各項目の意味については、図２（ｂ）を参照して説明したとおりであるため、ここでは詳細な説明を省略する。
【００８４】
リンク列１ヘッダ情報４２１Ａは、道路種別４３１Ａ、路線番号４３２Ａ、及び、有料フラグ４３３Ａを含む。図４（ｂ）の例の有料フラグ４３３Ａは、リンク列１＿４１０Ａに対応する道路が有料道路であることを示している。
【００８５】
リンク列１リンク情報４２２Ａは、ｎｏｄｅ１ノード情報４４１Ａ〜ｎｏｄｅ３ノード情報４４３Ａ、ｌｉｎｋ１形状情報４５１Ａ〜ｌｉｎｋ２形状情報４５２Ａ、ｌｉｎｋ１通行規制情報４６１Ａ〜ｌｉｎｋ２通行規制情報４６２Ａ、及びｌｉｎｋ１その他情報４７１Ａ〜ｌｉｎｋ２その他情報４７２Ａを含む。
【００８６】
リンク列２ヘッダ情報４２３Ａは、道路種別４３４Ａ、路線番号４３５Ａ、及び、有料フラグ４３６Ａを含む。図４（ｂ）の例の有料フラグ４３６Ａは、リンク列２＿４３０Ａに対応する道路が無料道路であることを示している。
【００８７】
リンク列２リンク情報４２４Ａは、ｎｏｄｅ４ノード情報４４４Ａ〜ｎｏｄｅ５ノード情報４４５Ａ、ｌｉｎｋ３形状情報４５３Ａ、ｌｉｎｋ３通行規制情報４６３Ａ、及びｌｉｎｋ３その他情報４７３Ａを含む。
【００８８】
なお、既に説明したように、ｎｏｄｅ３＿４０３Ａとｎｏｄｅ４＿４０４Ａとは同一の交差点に対応する。このため、ｎｏｄｅ３＿４０３Ａに対応するｎｏｄｅ３ノード情報４４３Ａは、ｎｏｄｅ３＿４０３Ａがｎｏｄｅ４＿４０４Ａに接続していることを示す情報を含み、ｎｏｄｅ４＿４０４Ａに対応するｎｏｄｅ４ノード情報４４４Ａは、ｎｏｄｅ４＿４０４Ａがｎｏｄｅ３＿４０３Ａに接続していることを示す情報を含む。これらの情報を参照することによって、ｌｉｎｋ２＿４１２Ａとｌｉｎｋ３＿４１３Ａとが連続している、すなわち、図４の例においてｌｉｎｋ１＿４１１Ａからｌｉｎｋ３＿４１３Ａまでが連続している、と判定することができる。
【００８９】
一方、図４（ｂ）の例において、バージョン２の道路データ４２０Ｂは、リンク列１ヘッダ情報４２１Ｂ及びリンク列１リンク情報４２２Ｂからなる。
【００９０】
リンク列１ヘッダ情報４２１Ａは、道路種別４３１Ｂ、路線番号４３２Ｂ、及び、有料フラグ４３３Ｂを含む。図４（ｂ）の例の有料フラグ４３３Ｂは、リンク列１＿４１０Ｂに対応する道路が無料道路であることを示している。道路種別４３１Ｂ及び路線番号４３２Ｂは、それぞれ、バージョン１の道路種別４３１Ａ及び路線番号４３２Ａと同じである。
【００９１】
リンク列１リンク情報４２２Ｂは、ｎｏｄｅ１ノード情報４４１Ｂ〜ｎｏｄｅ２ノード情報４４２Ｂ、ｎｏｄｅ６ノード情報４４６Ｂ〜ｎｏｄｅ７ノード情報４４７Ｂ、ｌｉｎｋ１形状情報４５１Ｂ〜ｌｉｎｋ２形状情報４５２Ｂ、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ１通行規制情報４６１Ｂ〜ｌｉｎｋ２通行規制情報４６２Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、ｌｉｎｋ１その他情報４７１Ｂ〜ｌｉｎｋ２その他情報４７２Ｂ、及びｌｉｎｋ４その他情報４７４Ｂを含む。
【００９２】
ｎｏｄｅ１ノード情報４４１Ｂ〜ｎｏｄｅ２ノード情報４４２Ｂは、それぞれ、バージョン１のｎｏｄｅ１ノード情報４４１Ａ〜ｎｏｄｅ２ノード情報４４２Ａと同じである。ｌｉｎｋ１形状情報４５１Ｂ〜ｌｉｎｋ２形状情報４５２Ｂは、それぞれ、バージョン１のｌｉｎｋ１形状情報４５１Ａ〜ｌｉｎｋ２形状情報４５２Ａと同じである。ｌｉｎｋ１通行規制情報４６１Ｂ〜ｌｉｎｋ２通行規制情報４６２Ｂは、それぞれ、バージョン１のｌｉｎｋ１通行規制情報４６１Ａ〜ｌｉｎｋ２通行規制情報４６２Ａと同じである。ｌｉｎｋ１その他情報４７１Ｂ〜ｌｉｎｋ２その他情報４７２Ｂは、それぞれ、バージョン１のｌｉｎｋ１その他情報４７１Ａ〜ｌｉｎｋ２その他情報４７２Ａと同じである。
【００９３】
ｎｏｄｅ６ノード情報４４６Ｂは、ｎｏｄｅ６＿４０６Ｂに対応する交差点に関する情報を含む。ｎｏｄｅ６＿４０６Ｂに対応する交差点は、実際にはｎｏｄｅ３＿４０３Ａ及びｎｏｄｅ３＿４０３Ａに対応する交差点と同一であるため、ｎｏｄｅ６ノード情報４４６Ｂの内容は、ｎｏｄｅ３ノード情報４４３Ａ又はｎｏｄｅ４ノード情報４４４Ａの内容と同一である。
【００９４】
ｎｏｄｅ７ノード情報４４７Ｂは、ｎｏｄｅ７＿４０７Ｂに対応する交差点に関する情報を含む。ｎｏｄｅ７＿４０７Ｂに対応する交差点は、実際にはｎｏｄｅ５＿４０５Ａに対応する交差点と同一であるため、ｎｏｄｅ７ノード情報４４７Ｂの内容は、ｎｏｄｅ５ノード情報４４５Ａの内容と同一である。
【００９５】
ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、及びｌｉｎｋ４その他情報４７４Ｂは、それぞれ、ｌｉｎｋ４＿４１４Ｂに対応する区間の形状、通行規制及びその他の情報を含む。ｌｉｎｋ４＿４１４Ｂに対応する区間は、ｌｉｎｋ３＿４１３Ａに対応する区間と同一であるため、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、及びｌｉｎｋ４その他情報４７４Ｂの内容は、それぞれ、ｌｉｎｋ３形状情報４５３Ａ、ｌｉｎｋ３通行規制情報４６３Ａ、及びｌｉｎｋ３その他情報４７３Ａの内容と同一である。
【００９６】
図５は、道路データを更新するための更新エレメントの別の例の説明図である。
【００９７】
具体的には、図５は、図４に示す道路データに対応する更新エレメントの例を示す。この更新エレメントは、後述する図８に示す手順によって作成される。ただし、後述するように（図６参照）、図５に示す更新エレメントを用いた場合、リンク情報の更新に関する矛盾は発生しないが、ヘッダ情報の更新に関する矛盾が発生する可能性がある。以下、説明の便宜上、地図配信サーバ１０が図５に示す更新エレメントを作成するように説明するが、実際には、本発明の実施形態の地図配信サーバ１０は、さらに改善された更新エレメントを作成する（図７及び図９参照）。
【００９８】
ナビゲーション端末２０が図４に示すバージョン１の道路データ４２０Ａを保持している場合に、それをバージョン２の道路データ４２０Ｂに更新するためには、有料道路を示す有料フラグ４３３Ａを、無料道路を示す有料フラグ４３３Ｂに置き換えることを指示する情報、リンク列１リンク情報４２２Ａからｎｏｄｅ３ノード情報４４３Ａを削除することを指示する情報、リンク列２ヘッダ情報４２３Ａ及びリンク列２リンク情報４２４Ａの各項目を削除することを指示する情報、及び、リンク列１リンク情報４２２Ａにｎｏｄｅ６ノード情報４４６Ｂ、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、ｌｉｎｋ４その他情報４７４Ｂ及びｎｏｄｅ７ノード情報４４７Ｂを追加することを指示する情報を含む地図更新データが作成される。
【００９９】
この場合も、図３の場合と同様、単一の又は連続した区間に関する地図更新データが一つの更新エレメントとして作成される。
【０１００】
図５の例では、リンク列１＿４１０Ａの先頭に付与されたリンク列１ヘッダ情報４２１Ａに関する地図更新データが更新エレメント１＿５０１として作成される。すなわち、更新エレメント１＿５０１には、有料フラグ４３３Ａを有料フラグ４３３Ｂに更新することを指示する情報が含まれる。
【０１０１】
一方、ｌｉｎｋ３＿４１３Ａに関する情報が更新エレメント２＿５０２として作成される。
【０１０２】
具体的には、ｌｉｎｋ３形状情報４５３Ａ、ｌｉｎｋ３通行規制情報４６３Ａ及びｌｉｎｋ３その他情報４７３Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０３】
さらに、ｌｉｎｋ３＿４１３Ａの始点ノードであるｎｏｄｅ４＿４０４Ａに関するｎｏｄｅ４ノード情報４４４Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０４】
さらに、ｎｏｄｅ４＿４０４Ａと実質的に同一のノードであるｎｏｄｅ４＿４０４Ａに関するｎｏｄｅ３ノード情報４４３Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０５】
さらに、ｌｉｎｋ３＿４１３Ａの終点ノードであるｎｏｄｅ５＿４０５Ａに関するｎｏｄｅ５ノード情報４４５Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０６】
さらに、ｌｉｎｋ３＿４１３Ａがリンク列２＿４３０Ａの先頭のリンクであるであるため、リンク列２ヘッダ情報４２３Ａを削除することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０７】
道路データ４２０Ａ及び４２０Ｂを参照すると、ｎｏｄｅ４＿４０４Ａ及びｎｏｄｅ６＿４０６Ｂがいずれもｌｉｎｋ２＿４１２Ａの終点ノードであることがわかる。このため、これらのノードに接続されたｌｉｎｋ３＿４１３Ａ及びｌｉｎｋ４＿４１４Ｂは、同一の区間に対応するか、又は、連続する二つの区間にそれぞれ対応するか、のいずれかであると判定することができる（図４の例では同一の区間に対応している）。このため、更新エレメント２＿５０２は、さらに、ｌｉｎｋ４＿４１４Ｂに関する情報を含む。
【０１０８】
具体的には、さらに、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ及びｌｉｎｋ４その他情報４７４Ｂを追加することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１０９】
さらに、ｌｉｎｋ４＿４１４Ｂの始点ノードであるｎｏｄｅ６＿４０６Ｂに関するｎｏｄｅ６ノード情報４４６Ｂを追加することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１１０】
さらに、ｌｉｎｋ４＿４１４Ｂの終点ノードであるｎｏｄｅ７＿４０７Ｂに関するｎｏｄｅ７ノード情報４４７Ｂを追加することを指示する情報が更新エレメント２＿５０２に含まれる。
【０１１１】
図３の場合と同様、ナビゲーション端末２０は、自車の現在地（又は目的地）の周辺の所定の範囲内の地図データの更新を地図配信サーバ１０に要求してもよい。更新要求を受信した地図配信サーバ１０は、更新要求によって指定された範囲内の地物に関するデータを含む更新エレメントをナビゲーション端末２０に送信する。しかし、これによって更新後の地図データに矛盾が発生する場合がある。次に、この矛盾について説明する。
【０１１２】
図６は、更新エレメントごとの地図データの更新の説明図である。
【０１１３】
例えば、指定された範囲にｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ３＿４１３Ａの両方が含まれる場合、これらのリンクに関する更新データを含む更新エレメント１＿５０１及び更新エレメント２＿５０２の両方がナビゲーション端末２０に送信される。これらの更新エレメントに基づいて、ナビゲーション端末２０が保持する地図データは、図４に示すバージョン２に更新される。この場合、地図データに矛盾は発生しない。
【０１１４】
一方、例えば、指定された範囲にｌｉｎｋ１＿４１１Ａが含まれるが、ｌｉｎｋ３＿４１３Ａは含まれない場合、ｌｉｎｋ１＿４１１Ａに関する更新データを含む更新エレメント１＿５０１は送信されるが、それを含まない更新エレメント２＿５０２は送信されない。この場合、図６（ａ）に示すように、リンク列１＿４１０Ａのヘッダ情報が更新されるが、リンク列２＿４３０Ａ等の削除、及び、リンク列１＿４１０Ａへのｌｉｎｋ４＿４１４Ｂ等の追加は行われない。その結果、更新後のバージョン２の道路データは、図４に示したバージョン２とは異なっている。すなわち、図４に示すバージョン２の道路データがリンク列１＿４１０Ｂのみからなるのに対して、図６（ａ）のバージョン２の道路データは、リンク列１＿４１０Ｃ及びリンク列２＿４３０Ａからなる。
【０１１５】
しかし、図６（ａ）のバージョン２の各リンクの形状及び通行規制等に関する情報は、図４のバージョン２の各リンクのものと同一である。さらに、図６（ａ）に示す二つのリンク列の属性は、図４のバージョン２のリンク列１＿４１０Ｂと同様、無料道路である。このため、図６（ａ）のバージョン２の道路データを用いて経路検索を行ったとしても、図４のバージョン２の道路データを用いた場合と同様の結果を得ることができる。
【０１１６】
一方、例えば、指定された範囲にｌｉｎｋ１＿４１１Ａが含まれないが、ｌｉｎｋ３＿４１３Ａは含まれる場合、ｌｉｎｋ３＿４１３Ａに関する更新データを含む更新エレメント２＿５０２は送信されるが、それを含まない更新エレメント１＿５０１は送信されない。この場合、図６（ｂ）に示すように、リンク列２＿４３０Ａ等の削除、及び、リンク列１＿４１０Ａへのｌｉｎｋ４＿４１４Ｂ等の追加は行われるが、リンク列１＿４１０Ａのヘッダ情報は更新されない。その結果、更新後のバージョン２の道路データは、図４に示したバージョン２とは異なっている。すなわち、図４に示すバージョン２の道路データが無料道路であるリンク列１＿４１０Ｂからなるのに対して、図６（ｂ）のバージョン２の道路データは、有料道路であるリンク列１＿４１０Ｄからなる。
【０１１７】
図６（ｂ）の場合、更新要求がされた範囲内にｌｉｎｋ３＿４１３Ａが含まれていたということは、ｌｉｎｋ３＿４１３Ａに対応する更新後のｌｉｎｋ４＿４１４Ｂが経路検索の対象になる可能性があることを意味する。しかし、上記のように、更新後の道路データには、本来無料区間であるべきｌｉｎｋ４＿４１４Ｂが有料区間として扱われるという矛盾がある。このため、図６（ｂ）のバージョン２の道路データを用いて経路検索を行うと、図４のバージョン２の道路データを用いた場合と異なる結果が得られることになる。
【０１１８】
以下、このような矛盾の発生を防ぐ更新エレメントの作成について説明する。
【０１１９】
図７は、本発明の実施形態の地図データ配信システムにおける道路データを更新するための更新エレメントの説明図である。
【０１２０】
具体的には、図７は、ナビゲーション端末２０が図４に示すバージョン１の道路データ４２０Ａを保持している場合に、それをバージョン２に更新するために、本実施形態の地図配信サーバ１０が作成する更新エレメントを示す。
【０１２１】
図５に示す更新エレメント１＿５０１は、リンク列１＿４１０Ａのヘッダに含まれる項目の置き換えを指示する情報を含む。一方、更新エレメント２＿５０２は、リンク列１＿４１０Ａからノードを削除することを指示する情報、及び、リンク列１＿４１０Ａ（すなわち更新後のリンク列１＿４１０Ｂ）に新たなノード及びリンクを追加することを指示する情報を含む。このように、一つの更新エレメントがいずれかのリンク列のヘッダ情報の更新を指示する情報を含み、さらに、そのリンク列に含まれる別のデータ項目の更新を指示する情報が別の更新エレメントに含まれる場合、本実施形態の地図配信サーバ１０の更新データ抽出部１３は、それらの更新エレメントを一つの更新エレメントに統合する。
【０１２２】
具体的には、図７に示す更新エレメント１＿７０１は、図５に示す更新エレメント１＿５０１及び更新エレメント２＿５０２の両方の内容（すなわち、それらの更新エレメントに含まれる全ての差分データ項目）を含む。その結果、例えば、ナビゲーション端末２０からの更新要求によって指定された範囲にｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ３＿４１３Ａの両方が含まれる場合、ｌｉｎｋ１＿４１１Ａが含まれるがｌｉｎｋ３＿４１３Ａは含まれない場合、及び、指定された範囲にｌｉｎｋ１＿４１１Ａは含まれないがｌｉｎｋ３＿４１３Ａは含まれる場合、のいずれの場合であっても、本実施形態の地図配信サーバ１０は更新エレメント１＿７０１を送信する。
【０１２３】
図３の場合と同様、更新エレメント１＿７０１は、区切り文字及び更新エレメントの識別子のような、各差分データ項目が更新エレメント１＿７０１に含まれることを識別する情報を含む。既に説明したように、ナビゲーション端末２０のナビゲーション処理部２４は、一つの更新エレメントに基づく地図データの更新が開始されてからそれが終了するまでの間、その地図データに基づく経路検索を実行しない。すなわち、図７に示す更新エレメント１＿７０１を受信したナビゲーション端末２０は、更新エレメント１＿７０１に含まれる全ての差分データ項目の地図データへの反映が終了するまで、ナビゲーション処理部２４による経路検索を禁止する。
【０１２４】
このため、ナビゲーション端末２０からの更新要求によって指定された範囲にｌｉｎｋ１＿４１１Ａ及びｌｉｎｋ３＿４１３Ａの両方が含まれる場合、又は、それらのうち一方のみが含まれる場合、のいずれの場合であっても、図６に示すものではなく、図４に示すバージョン２の道路データ４２０Ｂに基づく経路検索が実行される。これによって、図６に示すような矛盾した道路データに基づく誤った経路検索を防ぐことができる。
【０１２５】
図８は、更新エレメントを作成する手順を示すフローチャートである。
【０１２６】
図８に示す手順によって、図５に示す更新エレメントが作成される。本実施形態の地図配信サーバ１０の更新データ抽出部１３は、実際には、より改善された図９に示す手順によって更新エレメントを作成する。しかし、ここでは、説明の便宜上、図８に示す手順を更新データ抽出部１３が実行するように記載する。
【０１２７】
最初に、更新データ抽出部１３は、地図データ記憶部１６に格納されている新バージョンの道路データの各データ項目と、それぞれに対応する旧バージョンの道路データの各データ項目と、を対照して、差分項目を抽出する（ステップ８０１）。ここでは、例として、図４に示すバージョン１（旧バージョン）の道路データ４２０Ａ及びバージョン２（新バージョン）の道路データ４２０Ｂが地図データ記憶部１６に格納されている場合について説明する。
【０１２８】
図４に表示されている「リンク列１」の「１」、「ｎｏｄｅ１」の「１」、及び「ｌｉｎｋ１」の「１」等は、それぞれ、リンク列、ノード及びリンクの識別子である。図２等についても同様である。更新データ抽出部１３は、同一の識別子が付与された新旧のデータ項目を、対応するデータ項目として対照する。
【０１２９】
上記の対照の結果、新バージョンの項目の内容が旧バージョンと異なる場合、更新データ抽出部１３は、その項目を変更差分項目として抽出する。旧バージョンの項目が新バージョンでは削除されている場合、その項目を削除差分項目として抽出する。旧バージョンでは存在しない項目が新バージョンに含まれている場合、その項目を追加差分項目として抽出する。
【０１３０】
なお、ナビゲーション端末２０の地図更新部２３は、受信した更新エレメントに変更差分項目が含まれる場合、それが示すデータ項目の内容を新バージョンの内容に更新する。削除差分項目が含まれる場合、それが示す旧バージョンのデータ項目を地図データから削除する。追加差分項目が含まれる場合、それが示す新バージョンのデータ項目を地図データに追加する。
【０１３１】
図４の例では、有料道路を示す有料フラグ４３３Ａが無料道路を示す有料フラグ４３３Ｂによって置き換えられる。このため、これらのデータ項目が変更差分項目として抽出される。
【０１３２】
さらに、図４の例では、ｎｏｄｅ３ノード情報４４３Ａ、リンク列２ヘッダ情報４２３Ａに含まれる全データ項目、及び、リンク列２リンク情報４２４Ａに含まれる全データ項目が削除される。このため、これらのデータ項目が削除差分項目として抽出される。
【０１３３】
さらに、図４の例では、ｎｏｄｅ６ノード情報４４６Ｂ、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、ｌｉｎｋ４その他情報４７４Ｂ及びｎｏｄｅ７ノード情報４４７Ｂが追加される。このため、これらのデータ項目が追加差分項目として抽出される。
【０１３４】
次に、更新データ抽出部１３は、ステップ８０１が全てのデータ項目について終了したか否かを判定する（ステップ８０２）。全てのデータ項目についてステップ８０１が終了していない場合、更新データ抽出部１３は、残りのデータ項目についてステップ８０１を実行する。
【０１３５】
全てのデータ項目についてステップ８０１が終了した場合、更新データ抽出部１３は、ステップ８０１で抽出した差分項目のうち、同一の又は連続する区間に関する差分項目をまとめることによって、一つの更新エレメントを作成する（ステップ８０３）。
【０１３６】
図４の例では、ｎｏｄｅ３ノード情報４４３Ａ、リンク列２ヘッダ情報４２３Ａに含まれる全データ項目、及び、リンク列２リンク情報４２４Ａに含まれる全データ項目を削除することを指示する情報、及び、ｎｏｄｅ６ノード情報４４６Ｂ、ｌｉｎｋ４形状情報４５４Ｂ、ｌｉｎｋ４通行規制情報４６４Ｂ、ｌｉｎｋ４その他情報４７４Ｂ及びｎｏｄｅ７ノード情報４４７Ｂを追加することを指示する情報が、一つの更新エレメントとして作成される。これは、図５を参照して説明したとおりである。
【０１３７】
次に、更新データ抽出部１３は、ステップ８０３が全ての差分項目について終了したか否かを判定する（ステップ８０４）。全ての差分項目についてステップ８０３が終了していない場合、更新データ抽出部１３は、残りの差分項目についてステップ８０３を実行する。
【０１３８】
全ての差分項目についてステップ８０３が終了した場合、更新データ抽出部１３は、更新エレメントの作成を終了する。作成された更新エレメントは、更新データ記憶部１２に格納される。
【０１３９】
図４に示すデータが地図データ記憶部１６に格納されている場合、図５に示す二つの更新エレメントが作成され、更新データ記憶部１２に格納される。
【０１４０】
図９は、本発明の実施形態の地図配信サーバ１０が更新エレメントを作成する手順を示すフローチャートである。
【０１４１】
最初に、更新データ抽出部１３は、地図データ記憶部１６に格納されている新バージョン及び旧バージョンの道路データのデータ項目のうち、リンク情報に含まれる各データ項目に、各データ項目が属するリンク列のヘッダの識別子（リンク列ヘッダＩＤ）を付加する（ステップ９０１）。図８の説明と同様、例として、図４に示すバージョン１（旧バージョン）の道路データ４２０Ａ及びバージョン２（新バージョン）の道路データ４２０Ｂが地図データ記憶部１６に格納されている場合について説明する。
【０１４２】
図１０は、本発明の実施形態の地図配信サーバ１０によってリンクの識別子が付加された道路データを示す説明図である。
【０１４３】
図９のステップ９０１において、更新データ抽出部１３は、バージョン１の道路データ４２０Ａのリンク列１リンク情報４２２Ａの各データ項目に、それらのデータ項目が属するリンク列のヘッダ情報の識別子（すなわちリンク列ヘッダＩＤ）として「１」を付加する。これは、リンク列１＿４１０Ａの識別子に対応する。
【０１４４】
さらに、更新データ抽出部１３は、バージョン２の道路データ４２０Ｂのリンク列１リンク情報４２２Ｂの各データ項目に、それらのデータ項目が属するリンク列のヘッダ情報の識別子として「１」を付加する。これは、リンク列１＿４１０Ｂの識別子に対応する。
【０１４５】
さらに、更新データ抽出部１３は、バージョン１の道路データ４２０Ａのリンク列２リンク情報４２４Ａの各データ項目に、それらのデータ項目が属するリンク列のヘッダ情報の識別子として「２」を付加する。これは、リンク列２＿４３０Ａの識別子に対応する。
【０１４６】
次に、更新データ抽出部１３は、地図データ記憶部１６に格納されている新バージョンの道路データの各データ項目と、それぞれに対応する旧バージョンの道路データの各データ項目と、を対照して、差分項目を抽出する（ステップ９０２）。この手順は、リンク情報に含まれる各データ項目にリンク列ヘッダＩＤが付加されている点を除いて図８のステップ８０１と同じであるため、説明を省略する。
【０１４７】
次に、更新データ抽出部１３は、ステップ９０２が全てのデータ項目について終了したか否かを判定する（ステップ９０３）。全てのデータ項目についてステップ９０２が終了していない場合、更新データ抽出部１３は、残りのデータ項目についてステップ９０２を実行する。
【０１４８】
全てのデータ項目についてステップ９０２が終了した場合、更新データ抽出部１３は、ステップ９０２で抽出した差分項目のうち、同一の又は連続する区間に関する差分項目をまとめることによって、一つの更新エレメントを作成する（ステップ９０４）。この手順は、データ項目にリンク列ヘッダＩＤが付加されている点を除いて図８のステップ８０３と同じであるため、説明を省略する。ステップ９０４が終了した時点の更新エレメントの例を図１１に示す。
【０１４９】
図１１は、本発明の実施形態の更新エレメント作成処理の途中で作成されるデータの説明図である。
【０１５０】
図１１に示す更新エレメント１＿１１０１及び更新エレメント２＿１１０２は、リンク情報に含まれる各データ項目にリンク列ヘッダＩＤ（図１０参照）が付加されている点を除いて、それぞれ図５に示した更新エレメント１＿５０１及び更新エレメント２＿５０２と同じであるため、これらについての説明は省略する。
【０１５１】
次に、更新データ抽出部１３は、ステップ９０４が全ての差分項目について終了したか否かを判定する（ステップ９０５）。全ての差分項目についてステップ９０４が終了していない場合、更新データ抽出部１３は、残りの差分項目についてステップ９０４を実行する。
【０１５２】
全ての差分項目についてステップ９０４が終了した場合、更新データ抽出部１３は、リンク列ヘッダに関する差分データ項目がいずれかの更新エレメントに含まれるか否かを判定し、含まれる場合は、そのリンク列ヘッダの識別子が付加されたデータ項目を含む更新エレメントを検索する。この検索の結果、上記のリンク列ヘッダに関する差分データ項目を含む更新エレメント以外の更新エレメントが得られた場合、それらの更新エレメントを一つの更新エレメントにまとめることによって、一つの更新エレメントを作成する（ステップ９０６）。ステップ９０６が終了した時点の更新エレメントの例を図１２に示す。
【０１５３】
図１２は、本発明の実施形態の更新エレメント作成処理の途中で作成される別のデータの説明図である。
【０１５４】
図１１の例では、更新エレメント１＿１１０１に、リンク列１ヘッダ情報に含まれる有料フラグ４３３Ａ及び４３３Ｂが差分データ項目として含まれる。このため、更新データ抽出部１３は、リンク列１ヘッダ情報４２１Ａのリンク列ヘッダＩＤ「１」が付加されたデータ項目を含む更新エレメントを検索する。図１１の例では、更新エレメント２＿１１０２のリンク列１リンク情報４２２Ａ及び４２２Ｂの各データ項目にリンク列ヘッダＩＤ「１」が付加されている。このため、更新データ抽出部１３は、更新エレメント１＿１１０１及び更新エレメント２＿１１０２をまとめることによって、図１２に示す更新エレメント１＿１２０１を作成する。更新エレメント１＿１２０１は、リンク情報に含まれる各データ項目にリンク列ヘッダＩＤが付加されている点を除いて図７に示したものと同じであるため、これらについての説明は省略する。
【０１５５】
最後に、作成された更新エレメントに含まれる各データ項目から、ステップ９０１で付加したリンク列ヘッダＩＤを削除することによって、図７に示すような更新エレメントを作成し、更新データ記憶部１２に格納する（ステップ９０７）。以上で本実施形態の更新エレメントの作成処理が終了する。
【０１５６】
なお、図２に示す道路データが地図データ記憶部１６に格納されている場合、図８及び図９のいずれの手順を用いても、図３に示す更新エレメントを作成することができる。それらの更新エレメントがリンク列ヘッダに関するデータ項目を含まない（すなわち、新旧データのリンク列ヘッダが同一である）ためである。しかし、本実施形態の更新データ抽出部１３は、新旧データのリンク列ヘッダが異なる場合に図７のような更新エレメントを作成できるように、図９に示す手順によって更新エレメントを作成する。
【０１５７】
以上、本発明の実施形態によれば、通信する地図更新データの量を抑制しつつ、リンク列の属性の変更に起因する道路データの矛盾の発生を防止することができる。これによって、矛盾した道路データに基づく誤った経路検索が防止される。
【符号の説明】
【０１５８】
１０ 地図配信サーバ
１１、２６ 管理データ記憶部
１２ 更新データ記憶部
１３ 更新データ抽出部
１４ 更新データ管理部
１５、２１ ネットワークインターフェース（Ｉ／Ｆ）
１６、２７ 地図データ記憶部
１７、２８ プロセッサ
１８、２９ メモリ
２０ ナビゲーション端末
２２ 配信要求部
２３ 地図更新部
２４ ナビゲーション処理部
２５ 画面入出力Ｉ／Ｆ
３０ 無線通信装置
３１ 無線基地局
４０ ネットワーク
４１ インターネット
【特許請求の範囲】
【請求項１】
ネットワークに接続される地図データ配信サーバであって、
前記地図データ配信サーバは、
前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、
第１の道路データと、前記第１の道路データより新しいバージョンである第２の道路データと、を保持し、
前記第１の道路データと第２の道路データとをデータ項目ごとに比較することによって、前記第１の道路データと前記第２の道路データとの間の差分データ項目を作成し、
各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成し、
前記複数の更新エレメントのうち第１の更新エレメントが、第１のリンク列の属性に関する差分データ項目を含み、かつ、前記複数の更新エレメントのうち第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記第１の更新エレメント及び前記第２の更新エレメントに含まれる全ての前記差分データ項目を含む第３の更新エレメントを作成し、
前記ネットワークに接続された端末装置から受信した地図更新要求が、前記第３の更新エレメント内の前記差分データ項目に関するリンクを含む地図上の範囲を指定した場合、前記第３の更新エレメントを前記端末装置に送信することを特徴とする地図データ配信サーバ。
【請求項２】
前記第１の道路データ及び前記第２の道路データの少なくとも一方は、前記第１のリンク列の属性を示す情報を含むリンク列ヘッダを含み、
前記地図データ配信サーバは、
前記作成された差分データ項目のうち、前記第１のリンク列に属するノードに関する差分データ項目、及び、前記第１のリンク列に属するノードに関する差分データ項目に、前記第１のリンク列のリンク列ヘッダの識別子を付加し、
前記第２の更新エレメントが、前記第１のリンク列のリンク列ヘッダの識別子が付加された前記差分データ項目を含む場合、第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含むと判定し、
前記作成された第３の更新エレメントに含まれる前記各差分データ項目から、前記付加されたリンク列ヘッダの識別子を削除することを特徴とする請求項１に記載の地図データ配信サーバ。
【請求項３】
前記地図データ配信サーバは、前記第１の道路データに含まれるデータ項目に対応するデータ項目が前記第２の道路データに含まれない場合、データ項目の削除を示す差分データ項目を作成し、前記第２の道路データに含まれるデータ項目に対応するデータ項目が前記第１の道路データに含まれない場合、データ項目の追加を示す差分データ項目を作成し、前記第１の道路データに含まれるデータ項目の内容とそのデータ項目に対応する前記第２の道路データに含まれるデータ項目との内容が異なる場合、データ項目の変更を示す差分データ項目を作成することを特徴とする請求項２に記載の地図データ配信サーバ。
【請求項４】
前記各データ項目は、各リンク列の属性を示す情報、前記各リンク列に属する各リンクの形状を示す情報、前記各リンクの通行規制情報を示す情報、又は前記各リンクに接続される各ノードの位置を示す情報を含み、
前記各リンク列の属性を示す情報は、前記各リンク列に対応する道路の種別を示す情報、前記道路の路線番号を示す情報、又は、前記道路が有料道路であるか否かを示す情報を含むことを特徴とする請求項３に記載の地図データ配信サーバ。
【請求項５】
ネットワークに接続される地図データ配信サーバによって実行される地図更新方法であって、
前記地図データ配信サーバは、
前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、
第１の道路データと、前記第１の道路データより新しいバージョンである第２の道路データと、を保持し、
前記地図更新方法は、
前記地図データ配信サーバが、前記第１の道路データと第２の道路データとをデータ項目ごとに比較することによって、前記第１の道路データと前記第２の道路データとの間の差分データ項目を作成する第１の手順と、
前記地図データ配信サーバが、各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成する第２の手順と、
前記複数の更新エレメントのうち第１の更新エレメントが、第１のリンク列の属性に関する差分データ項目を含み、かつ、前記複数の更新エレメントのうち第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記地図データ配信サーバが、前記第１の更新エレメント及び前記第２の更新エレメントに含まれる全ての前記差分データ項目を含む第３の更新エレメントを作成する第３の手順と、
前記ネットワークに接続された端末装置から受信した地図更新要求が、前記第３の更新エレメント内の前記差分データ項目に関するリンクを含む地図上の範囲を指定した場合、前記地図データ配信サーバが前記第３の更新エレメントを前記端末装置に送信する第４の手順と、を含むことを特徴とする地図更新方法。
【請求項６】
前記第１の道路データ及び前記第２の道路データの少なくとも一方は、前記第１のリンク列の属性を示す情報を含むリンク列ヘッダを含み、
前記地図更新方法は、さらに、前記地図データ配信サーバが、前記作成された差分データ項目のうち、前記第１のリンク列に属するノードに関する差分データ項目、及び、前記第１のリンク列に属するノードに関する差分データ項目に、前記第１のリンク列のリンク列ヘッダの識別子を付加する手順を含み、
前記第３の手順は、前記第２の更新エレメントが、前記第１のリンク列のリンク列ヘッダの識別子が付加された前記差分データ項目を含む場合、前記地図データ配信サーバが、第２の更新エレメントが前記第１のリンク列に属するリンクに関する差分データ項目を含むと判定する手順を含み、
前記地図更新方法は、さらに、前記地図データ配信サーバが、前記作成された第３の更新エレメントに含まれる前記各差分データ項目から、前記付加されたリンク列ヘッダの識別子を削除する手順を含むことを特徴とする請求項５に記載の地図更新方法。
【請求項７】
前記第１の手順は、
前記第１の道路データに含まれるデータ項目に対応するデータ項目が前記第２の道路データに含まれない場合、前記地図データ配信サーバが、データ項目の削除を示す差分データ項目を作成する手順と、
前記第２の道路データに含まれるデータ項目に対応するデータ項目が前記第１の道路データに含まれない場合、前記地図データ配信サーバが、データ項目の追加を示す差分データ項目を作成する手順と、
前記第１の道路データに含まれるデータ項目の内容とそのデータ項目に対応する前記第２の道路データに含まれるデータ項目との内容が異なる場合、前記地図データ配信サーバが、データ項目の変更を示す差分データ項目を作成する手順と、
の少なくとも一つを含むことを特徴とする請求項６に記載の地図更新方法。
【請求項８】
前記各データ項目は、各リンク列の属性を示す情報、前記各リンク列に属する各リンクの形状を示す情報、前記各リンクの通行規制情報を示す情報、又は前記各リンクに接続される各ノードの位置を示す情報を含み、
前記各リンク列の属性を示す情報は、前記各リンク列に対応する道路の種別を示す情報、前記道路の路線番号を示す情報、又は、前記道路が有料道路であるか否かを示す情報を含むことを特徴とする請求項７に記載の地図更新方法。
【請求項９】
ネットワークに接続される地図データ配信サーバと、前記ネットワークを介して前記地図データ配信サーバと通信する端末装置と、を備える地図データ配信システムであって、
前記地図データ配信サーバは、
前記ネットワークに接続される第１インターフェースと、前記第１インターフェースに接続される第１プロセッサと、前記第１プロセッサに接続される第１記憶装置と、を備え、
第１の道路データと、前記第１の道路データより新しいバージョンである第２の道路データと、を保持し、
前記端末装置は、
前記地図データ配信サーバと通信する第２インターフェースと、前記第２インターフェースに接続される第２プロセッサと、前記第２プロセッサに接続される第２記憶装置と、を備え、
前記第１の道路データを保持し、
前記地図データ配信サーバは、
前記第１の道路データと第２の道路データとをデータ項目ごとに比較することによって、前記第１の道路データと前記第２の道路データとの間の差分データ項目を作成し、
各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成し、
前記複数の更新エレメントのうち第１の更新エレメントが、第１のリンク列の属性に関する差分データ項目を含み、かつ、前記複数の更新エレメントのうち第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記第１の更新エレメント及び前記第２の更新エレメントに含まれる全ての前記差分データ項目を含む第３の更新エレメントを作成し、
前記端末装置は、地図上の範囲の指定を含む地図更新要求を前記地図データ配信サーバに送信し、
前記地図データ配信サーバは、前記地図更新要求によって指定された範囲に、前記第３の更新エレメント内の前記差分データ項目に関するリンクが含まれる場合、前記第３の更新エレメントを前記端末装置に送信することを特徴とする地図データ配信システム。
【請求項１０】
前記第１の道路データ及び前記第２の道路データの少なくとも一方は、前記第１のリンク列の属性を示す情報を含むリンク列ヘッダを含み、
前記地図データ配信サーバは、
前記作成された差分データ項目のうち、前記第１のリンク列に属するノードに関する差分データ項目、及び、前記第１のリンク列に属するノードに関する差分データ項目に、前記第１のリンク列のリンク列ヘッダの識別子を付加し、
前記第２の更新エレメントが、前記第１のリンク列のリンク列ヘッダの識別子が付加された前記差分データ項目を含む場合、第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含むと判定し、
前記作成された第３の更新エレメントに含まれる前記各差分データ項目から、前記付加されたリンク列ヘッダの識別子を削除することを特徴とする請求項９に記載の地図データ配信システム。
【請求項１１】
前記第３の更新エレメントは、前記第３の更新エレメントに含まれる前記差分データ項目が、前記第３の更新エレメントに含まれることを識別する情報を含み、
前記端末装置は、
前記第３の更新エレメントに基づいて、前記端末装置が保持する前記第１の道路データを前記第２の道路データに更新し、
前記第３の更新エレメントに基づく前記更新が開始されてから終了するまでの間、前記第１の道路データに基づく経路検索を禁止することを特徴とする請求項１０に記載の地図データ配信システム。
【請求項１２】
前記地図データ配信サーバは、前記第１の道路データに含まれるデータ項目に対応するデータ項目が前記第２の道路データに含まれない場合、データ項目の削除を示す差分データ項目を作成し、前記第２の道路データに含まれるデータ項目に対応するデータ項目が前記第１の道路データに含まれない場合、データ項目の追加を示す差分データ項目を作成し、前記第１の道路データに含まれるデータ項目の内容とそのデータ項目に対応する前記第２の道路データに含まれるデータ項目との内容が異なる場合、データ項目の変更を示す差分データ項目を作成することを特徴とする請求項１１に記載の地図データ配信システム。
【請求項１３】
前記各データ項目は、各リンク列の属性を示す情報、前記各リンク列に属する各リンクの形状を示す情報、前記各リンクの通行規制情報を示す情報、又は前記各リンクに接続される各ノードの位置を示す情報を含み、
前記各リンク列の属性を示す情報は、前記各リンク列に対応する道路の種別を示す情報、前記道路の路線番号を示す情報、又は、前記道路が有料道路であるか否かを示す情報を含むことを特徴とする請求項１２に記載の地図データ配信システム。
【請求項１】
ネットワークに接続される地図データ配信サーバであって、
前記地図データ配信サーバは、
前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、
第１の道路データと、前記第１の道路データより新しいバージョンである第２の道路データと、を保持し、
前記第１の道路データと第２の道路データとをデータ項目ごとに比較することによって、前記第１の道路データと前記第２の道路データとの間の差分データ項目を作成し、
各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成し、
前記複数の更新エレメントのうち第１の更新エレメントが、第１のリンク列の属性に関する差分データ項目を含み、かつ、前記複数の更新エレメントのうち第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記第１の更新エレメント及び前記第２の更新エレメントに含まれる全ての前記差分データ項目を含む第３の更新エレメントを作成し、
前記ネットワークに接続された端末装置から受信した地図更新要求が、前記第３の更新エレメント内の前記差分データ項目に関するリンクを含む地図上の範囲を指定した場合、前記第３の更新エレメントを前記端末装置に送信することを特徴とする地図データ配信サーバ。
【請求項２】
前記第１の道路データ及び前記第２の道路データの少なくとも一方は、前記第１のリンク列の属性を示す情報を含むリンク列ヘッダを含み、
前記地図データ配信サーバは、
前記作成された差分データ項目のうち、前記第１のリンク列に属するノードに関する差分データ項目、及び、前記第１のリンク列に属するノードに関する差分データ項目に、前記第１のリンク列のリンク列ヘッダの識別子を付加し、
前記第２の更新エレメントが、前記第１のリンク列のリンク列ヘッダの識別子が付加された前記差分データ項目を含む場合、第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含むと判定し、
前記作成された第３の更新エレメントに含まれる前記各差分データ項目から、前記付加されたリンク列ヘッダの識別子を削除することを特徴とする請求項１に記載の地図データ配信サーバ。
【請求項３】
前記地図データ配信サーバは、前記第１の道路データに含まれるデータ項目に対応するデータ項目が前記第２の道路データに含まれない場合、データ項目の削除を示す差分データ項目を作成し、前記第２の道路データに含まれるデータ項目に対応するデータ項目が前記第１の道路データに含まれない場合、データ項目の追加を示す差分データ項目を作成し、前記第１の道路データに含まれるデータ項目の内容とそのデータ項目に対応する前記第２の道路データに含まれるデータ項目との内容が異なる場合、データ項目の変更を示す差分データ項目を作成することを特徴とする請求項２に記載の地図データ配信サーバ。
【請求項４】
前記各データ項目は、各リンク列の属性を示す情報、前記各リンク列に属する各リンクの形状を示す情報、前記各リンクの通行規制情報を示す情報、又は前記各リンクに接続される各ノードの位置を示す情報を含み、
前記各リンク列の属性を示す情報は、前記各リンク列に対応する道路の種別を示す情報、前記道路の路線番号を示す情報、又は、前記道路が有料道路であるか否かを示す情報を含むことを特徴とする請求項３に記載の地図データ配信サーバ。
【請求項５】
ネットワークに接続される地図データ配信サーバによって実行される地図更新方法であって、
前記地図データ配信サーバは、
前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、
第１の道路データと、前記第１の道路データより新しいバージョンである第２の道路データと、を保持し、
前記地図更新方法は、
前記地図データ配信サーバが、前記第１の道路データと第２の道路データとをデータ項目ごとに比較することによって、前記第１の道路データと前記第２の道路データとの間の差分データ項目を作成する第１の手順と、
前記地図データ配信サーバが、各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成する第２の手順と、
前記複数の更新エレメントのうち第１の更新エレメントが、第１のリンク列の属性に関する差分データ項目を含み、かつ、前記複数の更新エレメントのうち第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記地図データ配信サーバが、前記第１の更新エレメント及び前記第２の更新エレメントに含まれる全ての前記差分データ項目を含む第３の更新エレメントを作成する第３の手順と、
前記ネットワークに接続された端末装置から受信した地図更新要求が、前記第３の更新エレメント内の前記差分データ項目に関するリンクを含む地図上の範囲を指定した場合、前記地図データ配信サーバが前記第３の更新エレメントを前記端末装置に送信する第４の手順と、を含むことを特徴とする地図更新方法。
【請求項６】
前記第１の道路データ及び前記第２の道路データの少なくとも一方は、前記第１のリンク列の属性を示す情報を含むリンク列ヘッダを含み、
前記地図更新方法は、さらに、前記地図データ配信サーバが、前記作成された差分データ項目のうち、前記第１のリンク列に属するノードに関する差分データ項目、及び、前記第１のリンク列に属するノードに関する差分データ項目に、前記第１のリンク列のリンク列ヘッダの識別子を付加する手順を含み、
前記第３の手順は、前記第２の更新エレメントが、前記第１のリンク列のリンク列ヘッダの識別子が付加された前記差分データ項目を含む場合、前記地図データ配信サーバが、第２の更新エレメントが前記第１のリンク列に属するリンクに関する差分データ項目を含むと判定する手順を含み、
前記地図更新方法は、さらに、前記地図データ配信サーバが、前記作成された第３の更新エレメントに含まれる前記各差分データ項目から、前記付加されたリンク列ヘッダの識別子を削除する手順を含むことを特徴とする請求項５に記載の地図更新方法。
【請求項７】
前記第１の手順は、
前記第１の道路データに含まれるデータ項目に対応するデータ項目が前記第２の道路データに含まれない場合、前記地図データ配信サーバが、データ項目の削除を示す差分データ項目を作成する手順と、
前記第２の道路データに含まれるデータ項目に対応するデータ項目が前記第１の道路データに含まれない場合、前記地図データ配信サーバが、データ項目の追加を示す差分データ項目を作成する手順と、
前記第１の道路データに含まれるデータ項目の内容とそのデータ項目に対応する前記第２の道路データに含まれるデータ項目との内容が異なる場合、前記地図データ配信サーバが、データ項目の変更を示す差分データ項目を作成する手順と、
の少なくとも一つを含むことを特徴とする請求項６に記載の地図更新方法。
【請求項８】
前記各データ項目は、各リンク列の属性を示す情報、前記各リンク列に属する各リンクの形状を示す情報、前記各リンクの通行規制情報を示す情報、又は前記各リンクに接続される各ノードの位置を示す情報を含み、
前記各リンク列の属性を示す情報は、前記各リンク列に対応する道路の種別を示す情報、前記道路の路線番号を示す情報、又は、前記道路が有料道路であるか否かを示す情報を含むことを特徴とする請求項７に記載の地図更新方法。
【請求項９】
ネットワークに接続される地図データ配信サーバと、前記ネットワークを介して前記地図データ配信サーバと通信する端末装置と、を備える地図データ配信システムであって、
前記地図データ配信サーバは、
前記ネットワークに接続される第１インターフェースと、前記第１インターフェースに接続される第１プロセッサと、前記第１プロセッサに接続される第１記憶装置と、を備え、
第１の道路データと、前記第１の道路データより新しいバージョンである第２の道路データと、を保持し、
前記端末装置は、
前記地図データ配信サーバと通信する第２インターフェースと、前記第２インターフェースに接続される第２プロセッサと、前記第２プロセッサに接続される第２記憶装置と、を備え、
前記第１の道路データを保持し、
前記地図データ配信サーバは、
前記第１の道路データと第２の道路データとをデータ項目ごとに比較することによって、前記第１の道路データと前記第２の道路データとの間の差分データ項目を作成し、
各々が単一の又は連続するリンクに関する一つ以上の前記差分データ項目を含む、複数の更新エレメントを作成し、
前記複数の更新エレメントのうち第１の更新エレメントが、第１のリンク列の属性に関する差分データ項目を含み、かつ、前記複数の更新エレメントのうち第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含む場合、前記第１の更新エレメント及び前記第２の更新エレメントに含まれる全ての前記差分データ項目を含む第３の更新エレメントを作成し、
前記端末装置は、地図上の範囲の指定を含む地図更新要求を前記地図データ配信サーバに送信し、
前記地図データ配信サーバは、前記地図更新要求によって指定された範囲に、前記第３の更新エレメント内の前記差分データ項目に関するリンクが含まれる場合、前記第３の更新エレメントを前記端末装置に送信することを特徴とする地図データ配信システム。
【請求項１０】
前記第１の道路データ及び前記第２の道路データの少なくとも一方は、前記第１のリンク列の属性を示す情報を含むリンク列ヘッダを含み、
前記地図データ配信サーバは、
前記作成された差分データ項目のうち、前記第１のリンク列に属するノードに関する差分データ項目、及び、前記第１のリンク列に属するノードに関する差分データ項目に、前記第１のリンク列のリンク列ヘッダの識別子を付加し、
前記第２の更新エレメントが、前記第１のリンク列のリンク列ヘッダの識別子が付加された前記差分データ項目を含む場合、第２の更新エレメントが、前記第１のリンク列に属するリンクに関する差分データ項目を含むと判定し、
前記作成された第３の更新エレメントに含まれる前記各差分データ項目から、前記付加されたリンク列ヘッダの識別子を削除することを特徴とする請求項９に記載の地図データ配信システム。
【請求項１１】
前記第３の更新エレメントは、前記第３の更新エレメントに含まれる前記差分データ項目が、前記第３の更新エレメントに含まれることを識別する情報を含み、
前記端末装置は、
前記第３の更新エレメントに基づいて、前記端末装置が保持する前記第１の道路データを前記第２の道路データに更新し、
前記第３の更新エレメントに基づく前記更新が開始されてから終了するまでの間、前記第１の道路データに基づく経路検索を禁止することを特徴とする請求項１０に記載の地図データ配信システム。
【請求項１２】
前記地図データ配信サーバは、前記第１の道路データに含まれるデータ項目に対応するデータ項目が前記第２の道路データに含まれない場合、データ項目の削除を示す差分データ項目を作成し、前記第２の道路データに含まれるデータ項目に対応するデータ項目が前記第１の道路データに含まれない場合、データ項目の追加を示す差分データ項目を作成し、前記第１の道路データに含まれるデータ項目の内容とそのデータ項目に対応する前記第２の道路データに含まれるデータ項目との内容が異なる場合、データ項目の変更を示す差分データ項目を作成することを特徴とする請求項１１に記載の地図データ配信システム。
【請求項１３】
前記各データ項目は、各リンク列の属性を示す情報、前記各リンク列に属する各リンクの形状を示す情報、前記各リンクの通行規制情報を示す情報、又は前記各リンクに接続される各ノードの位置を示す情報を含み、
前記各リンク列の属性を示す情報は、前記各リンク列に対応する道路の種別を示す情報、前記道路の路線番号を示す情報、又は、前記道路が有料道路であるか否かを示す情報を含むことを特徴とする請求項１２に記載の地図データ配信システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１１−１６４４５３（Ｐ２０１１−１６４４５３Ａ）
【公開日】平成２３年８月２５日（２０１１．８．２５）
【国際特許分類】
【出願番号】特願２０１０−２８６４３（Ｐ２０１０−２８６４３）
【出願日】平成２２年２月１２日（２０１０．２．１２）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【Ｆターム（参考）】
【公開日】平成２３年８月２５日（２０１１．８．２５）
【国際特許分類】
【出願日】平成２２年２月１２日（２０１０．２．１２）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【Ｆターム（参考）】
[ Back to top ]