地図データ配信サーバ及び地図データ配信方法
【課題】任意の範囲内の地図データを、矛盾が生じないように更新する。
【解決手段】ネットワークに接続され、前記ネットワークを介して地図データを配信する地図データ配信サーバであって、前記地図データ配信サーバは、地図データを更新するための差分データとして、第１領域内のノード及びリンクの変更を指示する第１情報、前記第１領域に隣接する第２領域内のノード及びリンクの変更を指示する第２情報、前記第１領域と前記第２領域との境界上のノードの変更を指示する第３情報、及び、前記第３情報に基づいて変更された境界上のノードのさらなる変更を指示する第４情報を保持し、前記第１領域を含む一つ以上の領域の地図データを更新するための地図データ配信要求を受信すると、前記第１情報、前記第２情報及び前記第３情報の組、又は、前記第１情報、前記第３情報及び前記第４情報の組のいずれかを送信する。
【解決手段】ネットワークに接続され、前記ネットワークを介して地図データを配信する地図データ配信サーバであって、前記地図データ配信サーバは、地図データを更新するための差分データとして、第１領域内のノード及びリンクの変更を指示する第１情報、前記第１領域に隣接する第２領域内のノード及びリンクの変更を指示する第２情報、前記第１領域と前記第２領域との境界上のノードの変更を指示する第３情報、及び、前記第３情報に基づいて変更された境界上のノードのさらなる変更を指示する第４情報を保持し、前記第１領域を含む一つ以上の領域の地図データを更新するための地図データ配信要求を受信すると、前記第１情報、前記第２情報及び前記第３情報の組、又は、前記第１情報、前記第３情報及び前記第４情報の組のいずれかを送信する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データを利用したサービスを利用者に提供する技術に関し、特に、端末装置が保持する地図データを更新するためのデータを配信する技術に関する。
【背景技術】
【０００２】
自動車又は歩行者を対象とするナビゲーションサービスのような、地図データを用いたサービスが広く提供されている。このようなサービスを提供するために、ユーザが所持する端末は、道路ネットワークに関する情報を含む地図データを保持する。しかし、現実の道路は、新設又は付け替え等によって変更される場合がある。このような場合にも適切なサービスを提供するためには、端末が保持する地図データにもその変更を反映させる必要がある。しかし、広範囲の（例えば日本全国の）地図データをすべて更新する場合、更新対象のデータ量が多くなるため、相当の時間が必要になる。通常、端末は、地図データの更新を実行している間に、地図データを利用する処理（例えば経路探索等）を実行することができないため、そのような処理を実行していない時間帯に更新を実行することが望ましい。このため、現在では、所定の大きさの領域ごとに、差分データ（すなわち古いバージョンの地図データと新しいバージョンの地図データとの差分）のみを更新する方法が知られている。
【０００３】
一般に、地図データは、パーセルと呼ばれる地図上の所定の大きさの領域ごとに管理される。例えば、端末は、経路探索等の処理を実行していないある時間帯に、その時間内に更新が終了する分のパーセルの差分データを更新し、残りのパーセルについては、経路探索等の処理を実行していない別の時間帯に更新することもできる。これによって、経路探索等の処理を阻害しないように地図データを更新することができる。
【０００４】
しかし、上記のようにパーセルごとに地図データを更新すると、更新されたパーセルと更新されていないパーセルとの境界においてデータの矛盾が生じる場合がある。例えば、複数のパーセルにまたがる道路が新設された場合において、それらのうち一部のパーセルのみの地図データが更新されると、更新後の地図データにおいて道路がパーセルの境界で途切れる。端末がこのような矛盾した地図データを保持していると、誤ったデータが参照されるなどの問題が発生するため、経路探索等の処理を正常に実行できなくなる。このような矛盾の発生を防ぐために、例えば、指定された領域の地図データに加えて、その領域の更新の影響が及ぶ範囲の地図データも端末に送信する技術が開示されている（例えば特許文献１及び特許文献２参照）。あるいは、連続した道路の変更（追加又は削除等）を反映する更新データの集合を地図データ更新の最小単位として扱う技術が開示されている（例えば非特許文献１参照）。このような地図データ更新の最小単位は更新エレメントとも呼ばれ、更新エレメントごとに地図データが更新される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第０６／０１１２７８号
【特許文献２】特開２００６−３１７６４８号公報
【非特許文献】
【０００６】
【非特許文献１】“地図更新サービス／ソリューション”、［ｏｎｌｉｎｅ］、［平成２２年１１月１２日検索］、インターネット＜ＵＲＬ：http://www.hitachi-automotive.co.jp/products/cis/02.html＞
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記の文献に記載された方法では、地図データを更新する範囲を任意に決定することができない。これは、更新の影響が及ぶ範囲が更新の内容に依存するためである。例えば新しいバージョンの地図データにおける更新箇所が広範囲に及ぶ場合、更新の影響が及ぶ範囲（又は更新エレメント）も大きくなる。
【０００８】
しかし、実際には、地図データの更新範囲を任意に指定したい場合がある。例えば、端末のユーザが特定の地域のみの地図データのライセンスを購入した場合、ライセンスされた地域のみの地図データを更新する必要がある。しかし、従来は、ライセンスされた地域とそれ以外の地域とに跨る連続した道路が変更されている場合、ライセンスされた地域の地図データのみを矛盾が生じないように更新することはできなかった。あるいは、経路探索等の処理が実行されていない時間帯に更新を終了させるために、巨大な更新エレメントを分割する必要が生じる場合もある。このような場合にも、分割された更新エレメントに基づいて矛盾が生じないように地図データを更新することはできなかった。
【０００９】
本発明は上記の問題点に鑑みてなされたものであり、任意の範囲の地図データを、矛盾が生じないように更新することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の代表的な一例を示せば次の通りである。すなわち、ネットワークに接続され、前記ネットワークを介して地図データを配信する地図データ配信サーバであって、前記地図データ配信サーバは、前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、地図上の空間を分割することによって定義された複数の領域に対応する第１の地図データと、前記複数の領域に対応する、前記第１の地図データより新しいバージョンの第２の地図データと、を保持し、前記第１の地図データ及び第２の地図データは、道路上の地点に対応するノード及び前記地点を結ぶ道路上の区間に対応するリンクを示す情報を含み、前記複数の領域は、第１領域及び前記第１領域に隣接する第２領域を含み、前記地図データ配信サーバは、前記第１の地図データを前記第２の地図データに更新するための差分データとして、前記第１領域内のノード及びリンクの変更を指示する第１情報、前記第２領域内のノード及びリンクの変更を指示する第２情報、前記第１領域と前記第２領域との境界上のノードの変更を指示する第３情報、及び、前記第３情報に基づいて変更された境界上のノードのさらなる変更を指示する第４情報を保持し、前記第１領域を含む一つ以上の領域の地図データを更新するための地図データ配信要求を、前記ネットワークを介して受信すると、前記第１情報、前記第２情報及び前記第３情報の組、又は、前記第１情報、前記第３情報及び前記第４情報の組のいずれかを、前記ネットワークを介して送信することを特徴とする。
【発明の効果】
【００１１】
本発明の一実施形態によれば、任意の範囲の地図データを、矛盾が生じないように更新することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施形態の地図データ配信システムの構成を示すブロック図である。
【図２】従来の更新エレメントを用いた地図データの更新の説明図である。
【図３】本発明の実施形態の地図データ配信システムにおいて実行される、補正エレメントを用いた地図更新の説明図である。
【図４】本発明の実施形態の地図データ配信システムにおいて使用される地図データに含まれる道路ネットワークのデータ構造の説明図である。
【図５】本発明の実施形態における更新前の道路ネットワークのデータ構造の説明図である。
【図６】本発明の実施形態における更新後の道路ネットワークのデータ構造の説明図である。
【図７】本発明の実施形態における一部のみが更新された道路ネットワークのデータ構造の説明図である。
【図８】本発明の実施形態における別の一部のみが更新された道路ネットワークのデータ構造の説明図である。
【図９Ａ】従来の更新エレメントの説明図である。
【図９Ｂ】本発明の実施形態において使用される更新エレメント及び補正エレメントの説明図である。
【図１０】本発明の実施形態の管理データ記憶部に格納される更新権利管理テーブルの説明図である。
【図１１】本発明の実施形態の管理データ記憶部に格納される更新エレメント管理テーブルの説明図である。
【図１２】本発明の実施形態の管理データ記憶部に格納される補正エレメント管理テーブルの説明図である。
【図１３】本発明の実施形態のナビゲーション端末が保持する地図データを更新するために実行される処理を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、図面を用いて本発明の実施の形態を説明する。
【００１４】
図１は、本発明の実施形態の地図データ配信システムの構成を示すブロック図である。
【００１５】
本実施形態の地図データ配信システムは、ネットワーク４０に接続された地図配信サーバ１０と、ネットワーク４０を介して地図配信サーバ１０と通信するナビゲーション端末２０と、を備える。
【００１６】
地図配信サーバ１０は、互いに接続されたプロセッサ１６、メモリ１７、ネットワークインターフェース（Ｉ／Ｆ）１８、管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１９を備える計算機である。
【００１７】
プロセッサ１６は、メモリ１７に格納されたプログラムを実行する。
【００１８】
メモリ１７は、例えば半導体メモリであり、プロセッサ１６によって実行されるプログラム、プロセッサ１６によって参照されるデータ、及びプロセッサ１６から出力されたデータ等を格納する。本実施形態のメモリ１７には、少なくとも、プロセッサ１６によって実行されるプログラムである更新データ抽出部１４及び更新データ管理部１５が格納される。プロセッサ１６がプログラムを実行することによって実現される処理については後述する。以下の説明において更新データ抽出部１４等が実行する処理は、実際には、プロセッサ１６が更新データ抽出部１４等のプログラムに従って実行する。
【００１９】
ネットワークＩ／Ｆ１８は、ネットワーク４０に接続され、ナビゲーション端末２０等と通信する。
【００２０】
管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１９は、それぞれがハードディスクドライブ（ＨＤＤ）又はフラッシュメモリのような記憶装置であってもよいし、一つの記憶装置内の記憶領域であってもよい。
【００２１】
地図データ記憶部１９には、地図データが格納される。地図データは、地図の構成物（地物）の位置及び形状を示す座標値等を含む。現実の地物は随時更新される。その一例は、道路の新設、廃止又は付け替えのような道路ネットワークの更新である。地図データは、過去のある時点における地物に関する情報、及び、それより後の時点における地物に関する情報（言い換えると、旧バージョンの地図データ及び新バージョンの地図データ）を含んでもよい。
【００２２】
なお、一般に地図データは、地図上の所定の矩形の範囲ごとに管理される。この矩形の範囲は、パーセル又はメッシュと呼ばれる。各パーセルには固有の識別子（パーセルＩＤ）が付与される。
【００２３】
更新データ記憶部１２には、地物を単位とする地図更新データ（地図情報及び道路ネットワーク情報を含む）が格納される。地図更新データは、例えばナビゲーション端末２０があるバージョンの地図データを保持している場合に、それをより新しいバージョンの地図データに更新するために作成及び送信されるデータであり、具体的には、少なくともこれらのバージョンの差分データを含む。具体的には、更新データ記憶部１２には、少なくとも、地図データの更新を指示する情報を含む更新エレメント、及び、更新エレメントが指示する更新の内容をさらに変更する情報を含む補正エレメントが格納される。これらの詳細については後述する（図９Ｂ参照）。
【００２４】
管理データ記憶部１１には、地図更新データを管理するための情報が格納される。例えば、管理データ記憶部１１には、地図更新データのバージョン（すなわち差分の世代）を示す情報、及び、地図更新データが適用されるべき位置を示すパーセルＩＤ等が格納される。さらに、本実施形態の管理データ記憶部１１には、少なくとも、更新権利管理テーブル１０００（図１０参照）、更新エレメント管理テーブル１１００（図１１参照）及び補正エレメント管理テーブル１２００（図１２参照）が格納される。これらの詳細については後述する。
【００２５】
ナビゲーション端末２０は、ユーザを目的地まで誘導するために、経路検索及び検索結果の出力等を行う移動端末であり、例えば、自動車に搭載される車載用ナビゲーション端末又は歩行者に携帯される歩行者用ナビゲーション端末である。後者の場合、ナビゲーション端末２０は、ナビゲーション用のアプリケーションソフトウェアが組み込まれた携帯電話機等であってもよい。
【００２６】
図１では省略されているが、一般に、地図データ配信システムは、複数のナビゲーション端末２０を含む。また、本実施形態では、端末装置の典型的な例としてナビゲーション端末２０を示すが、地図情報を保持して利用するものである限り、いかなる種類の端末装置にも本発明を適用することができる。
【００２７】
本実施形態のナビゲーション端末２０は、互いに接続されたプロセッサ２８、メモリ２９、ネットワークＩ／Ｆ２１、画面入出力Ｉ／Ｆ２５、管理データ記憶部２６及び地図データ記憶部２７を備える。
【００２８】
プロセッサ２８は、メモリ２９に格納されたプログラムを実行する。
【００２９】
メモリ２９は、例えば半導体メモリであり、プロセッサ２８によって実行されるプログラム及びプロセッサ２８によって参照されるデータ等を格納する。本実施形態のメモリ２９には、プロセッサ２８によって実行されるプログラムである配信要求部２２、地図更新部２３及びナビゲーション処理部２４が格納される。
【００３０】
配信要求部２２は、地図更新データ配信要求を地図配信サーバ１０に送信する。地図更新部２３は、配信された地図更新データを用いて、地図データ記憶部２７に格納された地図データを更新する。これらの処理については後述する。以下の説明において配信要求部２２、地図更新部２３及びナビゲーション処理部２４によって実行される処理は、実際にはプロセッサ２８が各プログラムに従って実行する。
【００３１】
ナビゲーション処理部２４は、地図データ記憶部２７に格納された地図データに基づいて、目的地までの経路を検索し、その経路に沿ってユーザを誘導する。このような経路検索及び誘導は従来の車載用ナビゲーション端末と同様に公知の方法によって実行できるため、これらに関する詳細な説明は省略する。
【００３２】
画面入出力Ｉ／Ｆ２５は、ユーザに対して地図情報等を表示する画面と、ユーザからの入力を受け付ける入力装置と、を含む。例えば、画面入出力Ｉ／Ｆ２５は、液晶表示装置及びキーボード等であってもよいし、タッチパッド付きの液晶表示装置であってもよい。
【００３３】
ネットワークＩ／Ｆ２１は、無線通信装置３０に接続される。無線通信装置３０は、ネットワーク４０に接続された無線基地局３１と無線通信を行う。ネットワークＩ／Ｆ２１は、無線通信装置３０、無線基地局３１及びネットワーク４０を介して地図配信サーバ１０との間の通信を実行する。後述する地図データ配信要求の送信及び地図更新データの受信はこのような通信によって実現される。
【００３４】
なお、無線通信装置３０は、ナビゲーション端末２０に内蔵されてもよい。
【００３５】
管理データ記憶部２６及び地図データ記憶部２７は、それぞれがハードディスクドライブ（ＨＤＤ）又はフラッシュメモリのような記憶装置であってもよいし、一つの記憶装置内の記憶領域であってもよい。
【００３６】
地図データ記憶部２７には、ナビゲーション処理部２４によって参照される地図データが格納される。この地図データは、地図配信サーバ１０から送信された地図更新データに基づいて更新される。
【００３７】
管理データ記憶部２６には、地図データを管理するための情報が格納される。例えば、管理データ記憶部２６には、ナビゲーション端末２０自身の位置がどのパーセルに属するかを示す緯度経度−パーセルＩＤ対応情報、及び、地図に適用した地図更新データの識別情報等が格納される。
【００３８】
ネットワーク４０はインターネット４１に接続される。地図配信サーバ１０は、インターネット４１を介して新しいバージョンの地図データを取得してもよい。
【００３９】
続いて、地図データの更新の概要を説明する。
【００４０】
図２は、従来の更新エレメントを用いた地図データの更新の説明図である。
【００４１】
ここでは、例として、東京都に属するパーセル３０７と、それに隣接する千葉県に属するパーセル３０８とに跨る道路が新設され、その道路に対応する情報が追加される例を示す。なお、東京都及び千葉県は、地上に（及びそれに対応する地図上に）区切られた領域の例であり、これらは任意の領域、典型的には行政区画又は国によって置き換えることができる。例えば、ヨーロッパのように多くの国の国境が陸上にある場合、パーセル３０７がある国に属し、パーセル３０８がそれに隣接する別の国に属してもよい。
【００４２】
厳密に言えば、一般にパーセルの境界と都県境（又は国境）とは一致しないが、本実施形態ではデータを管理する便宜上、各パーセルがいずれかの都又は県に属するものとして扱われる。
【００４３】
一般に、地図データは種々の地物に関する情報を含むが、本発明はそれらのうち道路に関する情報の更新を対象としている。このため、以下、地図データとして道路に関する情報を説明し、その他の地物に関する説明は省略する。
【００４４】
周知のように、道路は、複数のノードと、それらを接続するリンクと、からなるネットワークとして記述され、それが地図データとして格納される。ノードは、一般には複数の道路の交差点に対応するが、道路上の交差点以外の点に対応する場合もある。例えばパーセルの境界線と道路とが交差する点もノードとして記述される。リンクは、二つのノードに対応する二つの地点を接続する道路の区間に対応する。各ノード及びリンクを記述する情報は、それぞれ地図データ内のノードテーブル及びリンクテーブルに含まれる。これらのテーブルの構造については後述する（図４Ｂ等参照）。
【００４５】
図２の例では、旧バージョンの地図データ２０１におけるパーセル３０７がノード４１０、４１１、４１２、リンク４１３及び４１４を含み、パーセル３０８がノード４２０、４２１、４２２、リンク４２３及び４２４を含む。リンク４１３はノード４１０と４１１とを接続し、リンク４１４はノード４１０と４１２とを接続し、リンク４２３はノード４２０と４２１とを接続し、リンク４２４はノード４２０と４２２とを接続する。なお、説明の便宜上、ノード４１１及び４１２をパーセル３０７に含まれるノードとして記載しているが、正確には、これらのノードはパーセル３０７とそれに隣接するパーセル（図示省略）との境界線上のノードである。ノード４２１及び４２２も同様に、パーセル３０８とそれに隣接するパーセルとの境界線上のノードである。
【００４６】
一方、新バージョンの地図データ２０２では、ノード４０２、リンク４０１及び４０３が追加されている。リンク４０１はノード４０２と４１０とを接続し、リンク４０３はノード４０２と４２０とを接続する。ノード４０２はパーセル３０７と３０８との境界線上のノードである。新たに追加されたノード及びリンクは、ノード４１０とノード４２０とを接続する。これは、ノード４１０に対応する地点とノード４２０に対応する地点とを接続する道路が新設されたことを意味する。
【００４７】
一般に、地図データは、現実の道路の変更が反映されるように所定のタイミングで（例えば数ヶ月ごとに）更新される。更新された地図データは、例えば、地図情報を扱う出版社によって作成され、インターネット４１を介して提供される。新しい地図データが提供された場合、地図配信サーバ１０の地図データ記憶部１９には、更新される前の（すなわち旧バージョンの）地図データ２０１と、更新された後の（すなわち新バージョンの）地図データ２０２の両方が格納される。
【００４８】
その時点で、ナビゲーション端末２０の地図データ記憶部２７には旧バージョンの地図データ２０１が格納されており、新バージョンの地図データ２０２は格納されていない。配信要求部２２は、地図データ配信要求を地図配信サーバ１０に送信し、それに応じて送信された地図データ（すなわち更新データ）を用いて地図更新部２３が地図データ記憶部２７内の地図を新バージョンに更新する。地図データ配信要求は、種々のイベント、例えば前回の配信から所定の時間が経過したこと、所定の日時が到来したこと、ユーザから更新要求を入力されたこと、などを契機として送信され得る。
【００４９】
地図データがノード及びリンクによって記述されるため、地図データの更新は、新たなノード若しくはリンクの追加、既存のノード若しくはリンクの削除、又は、既存のノード若しくはリンクを記述する情報の変更、のいずれか、又はそれらの組み合わせによって記述することができる。送信される更新データは、このようにして記述された情報を含む。
【００５０】
地図データの更新を実行する具体的な方法の一例として、パーセルごとの更新が挙げられる。例えば、配信要求部２２が更新対象のパーセルの指定を含む地図データ配信要求を地図配信サーバ１０に送信し、地図配信サーバ１０は指定されたパーセルの更新データを送信する。
【００５１】
しかし、パーセルごとの更新が行われた場合、例えば東京都側のノード４１０、４０２及びリンク４０１は更新されたが、千葉県側のノード４２０及びリンク４０３は更新されていない状態が出現し得る。その状態の地図データは、リンクの途切れ、例えば、ノード４０２は二つのリンクに接続されていることを示す情報を含むが、実際には一つのリンクの情報しか地図データ記憶部２７に格納されていない、といった矛盾を含んでいる。このような矛盾を含む地図データを用いると、誤ったデータが参照されることによって、経路探索が正常に終了しない場合がある。
【００５２】
このような矛盾を防ぐための更新方法として、更新エレメントごとの更新が知られている。更新エレメントは、連続したリンク及びそれらが接続されたノードに関する更新データの集合であり、これが地図データの更新単位として使用される。図２の例では、ノード４０２の追加、リンク４０１及び４０３の追加、及び、ノード４１０及び４２０を記述する情報の変更、を示す更新エレメント４３０が更新データ抽出部１４によって作成され、これが地図配信サーバ１０からナビゲーション端末２０に送信される。
【００５３】
更新エレメントごとに地図データを更新することによって、上記のような地図データの矛盾の発生を防止することができる。しかし、実際には、連続したリンク等の更新のうち一部のみを実行することが望まれる場合もある。その一例は、更新データ（言い換えると、地図データを更新する権利）を都道府県又は国等の領域ごとに販売したい場合である。例えばヨーロッパのように国境を跨る道路ネットワークが存在する領域において、国ごとに更新データを販売したいというニーズがあり得る。
【００５４】
別の一例は、地図データの更新時間が制限される場合である。一般にナビゲーション端末２０は潤沢なハードウェア資源を持たないため、地図データの更新を実行している間、地図データを使用する機能（例えば経路探索等）を使用できなくなるか、又は速度が大幅に低下するなどの制約を受ける。このため、地図データの更新は、経路探索等が実行されない時間帯（例えば夜間又は休憩中など）に実行されることが望ましい。しかし、更新エレメントのデータ量が多いために上記の時間帯に更新が終了しない場合もあり、そのような場合には連続したリンク等の更新データを含む一つの更新エレメントを複数に分割することが望まれる。
【００５５】
本発明の実施形態では、このようなニーズに対応するため、以下に説明する更新方法が採用される。
【００５６】
図３は、本発明の実施形態の地図データ配信システムにおいて実行される、補正エレメントを用いた地図更新の説明図である。
【００５７】
図３において、旧バージョンの地図データ２０１及び新バージョンの地図データ２０２は、いずれも図２に示したものと同じである。ただし、新バージョンの地図データ２０２の更新箇所をナビゲーション端末２０に反映させるための更新エレメントは図２に示したものと異なる。具体的には、図３において、地図データ２０２の更新箇所を反映させるための更新エレメントは、更新エレメント１＿４３１、更新エレメント２＿４３２、更新エレメント３＿４３３、補正エレメント１＿４３４及び補正エレメント２＿４３５からなる。
【００５８】
なお、図２に示した従来の更新エレメントは、例えば非特許文献１にも記載されているように、更新後の地図データに矛盾を生じさせない更新データの最小単位であった。一方、図３に示す本実施形態の更新エレメントは、単に更新データの管理単位であり、更新エレメントごとに更新を行っても更新後の地図データに矛盾が残る場合がある。更新後の地図データに矛盾を残さないためには、後述するように、複数の更新エレメント又は更新エレメントと補正エレメントを適切に組み合わせることが求められる場合がある。
【００５９】
更新エレメント１＿４３１、更新エレメント２＿４３２及び更新エレメント３＿４３３は、それぞれ、図２に示した更新エレメント４３０の一部に相当する。すなわち、更新エレメント１＿４３１はリンク４０１の追加及びノード４１０の変更を記述する情報を含み、更新エレメント２＿４３２はノード４０２の追加を記述する情報を含み、更新エレメント３＿４３３はリンク４０３の追加及びノード４２０の変更を記述する情報を含む。
【００６０】
更新エレメント１＿４３１から更新エレメント３＿４３３までの全てを用いてナビゲーション端末２０の地図データを更新した場合、その結果は、更新エレメント４３０を使用した結果と同じになり、地図データの矛盾は発生しない。ただし、これらの三つの更新エレメントのうち最初の一つに基づく更新が開始されてから、最後の一つに基づく更新が終了するまでの間は、一時的に地図データの矛盾が発生し得るため、その間に地図データを参照する処理（経路探索等）を実行しないように、ナビゲーション端末２０を制御する必要がある。
【００６１】
一方、これらの三つの更新エレメントの一部のみに基づいて地図データを更新した場合、既に説明したように、地図データの矛盾が発生する。補正エレメント１＿４３４及び補正エレメント２＿４３５は、このような場合に発生した地図データの矛盾を解消するために使用される。
【００６２】
例えば、更新エレメント１＿４３１及び更新エレメント２＿４３２に基づく更新を行い、更新エレメント３＿４３３に基づく更新は行わなかった場合、更新後の地図データには、ノード４０２を記述する情報として、ノード４０２にリンク４０１及び４０３の二つが接続されることを示す情報が含まれるが、リンク４０３そのものを記述する情報は含まれない。このような矛盾を解消するため、補正エレメント１＿４３４は、ノード４０２を記述する情報から、ノード４０２にリンク４０３が接続されることを示す情報を削除する指示を含む。同様に、補正エレメント２＿４３５は、ノード４０２を記述する情報から、ノード４０２にリンク４０１が接続されることを示す情報を削除する指示を含む。このような本実施形態の更新エレメント及び補正エレメントの詳細な内容については後述する。
【００６３】
なお、図３では、便宜上、補正エレメントを更新エレメント近傍の破線の楕円によって示しているが、その内容は、上記のように、更新エレメントに含まれる情報の補正（削除又は追加等）を指示する情報である。
【００６４】
図４は、本発明の実施形態の地図データ配信システムにおいて使用される地図データに含まれる道路ネットワークのデータ構造の説明図である。
【００６５】
図４には、例として、ノード１００〜１０３及びリンク１１０〜１１２からなるネットワークを示す。ここで、リンク１１０はノード１００及び１０３を、リンク１１１はノード１００及び１０１を、リンク１１２はノード１００及び１０２を接続する。
【００６６】
このようなネットワークは、ノードテーブル４４０及びリンクテーブル４６０に格納されたデータによって記述される。これらのテーブルのデータ構造は、従来のものと同様であってよいため、詳細な説明は省略するが、概要を説明すると次の通りである。
【００６７】
例えば、ノード１００は、ノードテーブル４００に格納されたノードデータレコード４４１Ａによって記述される。
【００６８】
ノードデータレコード４４１Ａは、ノードＩＤ４５１Ａ、ノード属性４５２Ａ、リンク数４５３Ａ、リンクＩＤ４５４Ａ、リンクＩＤ４５５Ａ及びリンクＩＤ４５６Ａを含む。
【００６９】
ノードＩＤ４５１Ａとして、ノードデータレコード４４１Ａが記述するノード（以下、「当該ノード」とも記載する。ノードデータレコード４４１Ａの場合、当該ノードはノード１００である）の識別子（ＩＤ）が格納される。本実施形態では、説明の便宜上、ノードの参照符号と同じ値をノードの識別子として使用する。すなわち、当該ノード（ノード１００）の識別子「１００」がノードＩＤ４５１Ａとして格納される。
【００７０】
ノード属性４５２Ａとして、当該ノードの属性を示す情報が格納される。
【００７１】
リンク数４５３Ａとして、当該ノードに接続されたリンクの数を示す値が格納される。図４の例では、ノード１００に三つのリンクが接続されているため、リンク数４５３Ａとして「３」が格納される。
【００７２】
リンクＩＤ４５４ＡからリンクＩＤ４５６Ａとして、当該ノードに接続されたリンクの識別子が格納される。本実施形態では、ノードの場合と同様、リンクの参照符号と同じ値がリンクの識別子として使用される。図４の例では、ノード１００に接続された三つのリンクの識別子「１１０」、「１１１」及び「１１２」がそれぞれリンクＩＤ４５４Ａ、リンクＩＤ４５５Ａ及びリンクＩＤ４５６Ａとして格納される。リンクＩＤ４５４ＡからリンクＩＤ４５６Ａは、各リンクを記述するリンクデータレコードが格納された領域のアドレスを示す値（ポインタ等）を含む。例えば、リンクＩＤ４５４Ａの値に基づいて、リンク１１０を記述するリンクデータレコード４６１Ａ（後述）を参照することができる。
【００７３】
なお、ノード１０１、１０２及び１０３を記述するノードデータレコードの図示は省略するが、それらのデータ構造は、ノードデータレコード４４１Ａのデータ構造と同様である。
【００７４】
一方、リンク１１０、１１１及び１１２は、それぞれ、リンクテーブル４６０に格納されたリンクデータレコード４６１Ａ、４６１Ｂ及び４６１Ｃによって記述される。
【００７５】
リンクデータレコード４６１Ａは、リンクＩＤ４７１Ａ、リンク属性４７２Ａ、リンクコスト４７３Ａ、リンク形状４７４Ａ及び接続ノードＩＤ４７５Ａを含む。
【００７６】
リンクＩＤ４７１Ａとして、リンクデータレコード４６１Ａが記述するリンク（ここでは当該リンクと記載する）の識別子が格納される。すなわち、当該リンク（この例ではリンク１１０）の識別子「１１０」がリンクＩＤ４７１Ａとして格納される。
【００７７】
リンク属性４７２Ａとして、当該リンクの属性を示す情報が格納される。当該リンクの属性を示す情報の一例は、通行規制（例えば通行可能か否か、及び、通行可能な時間帯等）を示す情報である。
【００７８】
リンクコスト４７３Ａとして、当該リンクに対応する区間の長さ又はその区間を通過するために要する時間等が格納される。
【００７９】
リンク形状４７４Ａとして、当該リンクの形状を示す値、例えば、座標値の列が格納される。
【００８０】
接続ノードＩＤ４７５Ａとして、当該リンクによって接続されるノードの識別子が格納される。図４の例ではリンク１１０がノード１０３に接続されるため、接続ノードＩＤ４７５Ａとして「１０３」が格納される。
【００８１】
なお、図４では、二つのノードを接続する一つの区間に対応して一つのリンクが図示されているが、実際には、図示された各リンクは、互いに対向する方向の二つの片方向リンクの組に相当する。図２及び図３等についても同様である。リンクテーブル４６０に含まれる各リンクデータレコードは、各片方向リンクを記述する。
【００８２】
例えば、ノード１０３とノード１００とを接続するリンク１１０は、実際には、ノード１００を始点とし、ノード１０３を終点とする方向のリンク（すなわち、リンク１１０に対応する道路の区間における、当該方向の通行に対応するリンク）と、その逆方向のリンクと、の組に相当する。リンクデータレコード４６１Ａは、ノード１００を記述するノードデータレコード４４１ＡのリンクＩＤ４５４Ａから参照され、リンクデータレコード４６１Ａ内の接続ノードＩＤ４７５Ａとしてノード１０３の識別子が格納される。これは、リンクデータレコード４６１Ａが、リンク１１０に相当する二つの片方向リンクのうち、ノード１００からノード１０３への方向のリンクを記述していることを意味する。
【００８３】
図４では省略されているが、リンクテーブル４６０は、リンク１１０に相当する二つの片方向リンクのうち、残る一方向のリンクを記述するリンクデータレコードも含む。そのリンクデータレコードは、ノード１０３を記述するノードデータレコード（図示省略）内のリンクＩＤ（図示省略）から参照され、接続ノードＩＤの値「１００」を含む。
【００８４】
道路の区間によっては、通行方向ごとに適用される通行規制及びコストが異なる場合があり（例えば一方通行等）、その場合は、図示された一つのリンクに対応する二つのリンクデータレコードのリンク属性及びコストの値が異なる。例えば、リンク１１０が一方通行区間である場合、リンク１１０に対応する二つのリンクデータレコードのうち一方のリンク属性として通行可能の属性が、もう一方のリンク属性として通行禁止の属性が与えられる。
【００８５】
リンクデータレコード４６１Ｂ及び４６１Ｃのデータ構造もリンクデータレコード４６１Ａと同様であるため、それらの詳細な説明は省略する。リンクデータレコード４６１Ｂは、ノードデータレコード４４１ＡのリンクＩＤ４５５Ａから参照され、リンクＩＤ４７１Ｂの値「１１１」及び接続ノードＩＤ４７５Ｂの値「１０１」を含む。リンクデータレコード４６１Ｃは、ノードデータレコード４４１ＡのリンクＩＤ４５６Ａから参照され、リンクＩＤ４７１Ｃの値「１１２」及び接続ノードＩＤ４７５Ｃの値「１０２」を含む。
【００８６】
なお、リンクデータレコード４６１Ｂは、リンク１１１のノード１００から１０１への方向の通行を記述するものであり、リンクデータレコード４６１Ｃは、リンク１１２のノード１００から１０２への方向の通行を記述するものである。図４では省略されているが、それぞれのリンクの逆方向の通行を記述するリンクデータレコードもリンクテーブル４６０に含まれる。
【００８７】
次に、図３を参照して説明した地図データの更新を、ノードテーブル及びリンクテーブルを参照しながら具体的に説明する。
【００８８】
図５は、本発明の実施形態における更新前の道路ネットワークのデータ構造の説明図である。
【００８９】
具体的には、図５は、図３の旧バージョンの地図データ２０１を記述するノードテーブル４４０及びリンクテーブル４６０を示す。これらのデータ構造は図４を参照して説明したものと同様であるため、以下、地図データの更新を説明するために必要な項目のみを説明し、その他の項目の説明は省略する。図６以降のテーブルについても同様である。
【００９０】
図５に示すノードテーブル４４０は、ノード４１０を記述するノードデータレコード４４１Ｂ及びノード４２０を記述するノードデータレコード４４１Ｃを含む。ノードテーブル４４０は、さらにノード４１１、４１２、４２１及び４２２を記述するノードデータレコードも含むが、これらの図示は省略する。
【００９１】
ノードデータレコード４４１ＢのノードＩＤ４５１Ｂとして、ノード４１０の識別子「４１０」が格納される。ノード４１０には二つのリンクすなわちリンク４１３及び４１４が接続されるため、ノードデータレコード４４１Ｂのリンク数４５３Ｂ、リンクＩＤ４５４Ｂ及びリンクＩＤ４５５Ｂには、それぞれ、「２」、「４１３」及び「４１４」が格納される。
【００９２】
ノードデータレコード４４１ＣのノードＩＤ４５１Ｃとして、ノード４２０の識別子「４２０」が格納される。ノード４２０には二つのリンクすなわちリンク４２３及び４２４が接続されるため、ノードデータレコード４４１Ｃのリンク数４５３Ｃ、リンクＩＤ４５４Ｃ及びリンクＩＤ４５５Ｃには、それぞれ、「２」、「４２３」及び「４２４」が格納される。
【００９３】
図５に示すリンクテーブル４６０は、リンク４１３、４１４、４２３及び４２４のそれぞれを記述するリンクデータレコード４６１Ｄ、４６１Ｅ、４６１Ｆ及び４６１Ｇを含む。
【００９４】
リンクＩＤ４５４Ｂ及び４５５Ｂの値から、それぞれ、リンクデータレコード４６１Ｄ及び４６１Ｅが参照される。
【００９５】
リンク４１３は、ノード４１１に接続される。このため、リンクデータレコード４６１ＤのリンクＩＤ４７１Ｄ及び接続ノードＩＤ４７５Ｄには、それぞれ、「４１３」及び「４１１」が格納される。同様に、リンク４１４は、ノード４１２に接続される。このため、リンクデータレコード４６１ＥのリンクＩＤ４７１Ｅ及び接続ノードＩＤ４７５Ｅには、それぞれ、「４１４」及び「４１２」が格納される。
【００９６】
一方、リンクＩＤ４５４Ｃ及び４５５Ｃの値から、それぞれ、リンクデータレコード４６１Ｆ及び４６１Ｇが参照される。
【００９７】
リンク４２３は、ノード４２１に接続される。このため、リンクデータレコード４６１ＦのリンクＩＤ４７１Ｆ及び接続ノードＩＤ４７５Ｆには、それぞれ、「４２３」及び「４２１」が格納される。同様に、リンク４２４は、ノード４２２に接続される。このため、リンクデータレコード４６１ＧのリンクＩＤ４７１Ｇ及び接続ノードＩＤ４７５Ｇには、それぞれ、「４２４」及び「４２２」が格納される。
【００９８】
なお、図５では省略されているが、実際には、リンク４１３のノード４１１からノード４１０への方向への通行、リンク４１４のノード４１２からノード４１０への方向への通行、リンク４２３のノード４２１からノード４２０への方向への通行、及び、リンク４２４のノード４２２からノード４２０への方向への通行のそれぞれを記述するリンクデータレコードもリンクテーブル４６０に含まれる。
【００９９】
図６は、本発明の実施形態における更新後の道路ネットワークのデータ構造の説明図である。
【０１００】
具体的には、図６は、図３の新バージョンの地図データ２０２、すなわち、図３に示した全ての更新が終了した後の地図データを記述するノードテーブル４４０及びリンクテーブル４６０を示す。
【０１０１】
図３を参照して説明したように、新バージョンの地図データ２０２においては、ノード４０２、リンク４０１及び４０３が追加され、これによってノード４１０及び４２０に接続されたリンクの数が変更されている。このため、ノードテーブル４４０及びリンクテーブル４６０において、ノード４０２、リンク４０１及び４０３を記述するノードデータレコード４４１Ｆ及びリンクデータレコード４６１Ｈ〜４６１Ｋが追加され、ノード４１０及び４２０のそれぞれを記述するノードデータレコード４４１Ｂ及び４４１Ｃが更新される。図６に示すノードデータレコード４４１Ｄ及び４４１Ｅは、それぞれ、更新されたノードデータレコード４４１Ｂ及び４４１Ｃに相当する。
【０１０２】
まず、更新後のノードテーブル４４０について説明する。
【０１０３】
ノードデータレコード４４１Ｄは、ノードデータレコード４４１Ｂのリンク数４５３Ｂを「２」から「３」に変更し、さらに、新たなリンクＩＤ４５６Ｄを追加することによって生成される。リンクＩＤ４５６Ｄの値は、新たにノード４１０に接続されたリンク４０１の識別子「４０１」である。
【０１０４】
ノードデータレコード４４１Ｅは、ノードデータレコード４４１Ｃのリンク数４５３Ｃを「２」から「３」に変更し、さらに、新たなリンクＩＤ４５６Ｅを追加することによって生成される。リンクＩＤ４５６Ｅの値は、新たにノード４２０に接続されたリンク４０３の識別子「４０３」である。
【０１０５】
ノード４０２を記述するノードデータレコード４４１Ｆは、他のノードデータレコードと同様の項目を含む。これらのうち、ノードＩＤ４５１Ｆの値は、ノード４０２の識別子「４０２」である。リンク数４５３Ｆの値は、ノード４０２に接続されたリンクの数「２」である。リンクＩＤ４５４Ｆ及び４５５Ｆの値は、ノード４０２に接続されたリンク４０３及び４０１の識別子「４０３」及び「４０１」である。
【０１０６】
次に、更新後のリンクテーブル４６０について説明する。
【０１０７】
リンクデータレコード４６１Ｄ〜４６１Ｇは、図５に示したものから変更されていない。一方、リンクデータレコード４６１Ｈ〜４６１Ｋは、新たに追加されたものである。これらのうち、リンクデータレコード４６１Ｈ及び４６１Ｊはリンク４０３を記述するものであり、リンクデータレコード４６１Ｉ及び４６１Ｋはリンク４０１を記述するものである。これらの追加されたリンクデータレコードは、他のリンクデータレコードと同様の項目を含む。
【０１０８】
リンクデータレコード４６１Ｈは、ノードデータレコード４４１ＦのリンクＩＤ４５４Ｆから参照される。リンクＩＤ４７１Ｈの値は、リンク４０３の識別子「４０３」である。接続ノードＩＤ４７５Ｈの値は、リンク４０３に接続されたノード４２０の識別子「４２０」である。すなわち、リンクデータレコード４６１Ｈは、リンク４０３におけるノード４０２からノード４２０への方向の通行を記述するものである。
【０１０９】
リンクデータレコード４６１Ｊは、ノードデータレコード４４１ＥのリンクＩＤ４５６Ｅから参照される。リンクＩＤ４７１Ｊの値は、リンク４０３の識別子「４０３」である。接続ノードＩＤ４７５Ｊの値は、リンク４０３に接続されたノード４０２の識別子「４０２」である。すなわち、リンクデータレコード４６１Ｊは、リンク４０３におけるノード４２０からノード４０２への方向の通行を記述するものである。
【０１１０】
リンクデータレコード４６１Ｉは、ノードデータレコード４４１ＦのリンクＩＤ４５５Ｆから参照される。リンクＩＤ４７１Ｉの値は、リンク４０１の識別子「４０１」である。接続ノードＩＤ４７５Ｉの値は、リンク４０１に接続されたノード４１０の識別子「４１０」である。すなわち、リンクデータレコード４６１Ｉは、リンク４０１におけるノード４０２からノード４１０への方向の通行を記述するものである。
【０１１１】
リンクデータレコード４６１Ｋは、ノードデータレコード４４１ＤのリンクＩＤ４５６Ｄから参照される。リンクＩＤ４７１Ｋの値は、リンク４０１の識別子「４０１」である。接続ノードＩＤ４７５Ｋの値は、リンク４０１に接続されたノード４０２の識別子「４０２」である。すなわち、リンクデータレコード４６１Ｋは、リンク４０１におけるノード４１０からノード４０２への方向の通行を記述するものである。
【０１１２】
ナビゲーション端末２０が保持する地図データが上記のように更新された場合、ナビゲーション処理部２４は、更新された地図データを参照して、経路探索等の処理を実行することができる。
【０１１３】
次に、上記のような更新の一部のみが反映された地図データについて説明する。このような地図データは、例えば、地図配信サーバ１０の地図データ記憶部１９に旧バージョンの地図データ（図５参照）及び新バージョンの地図データ（図６参照）の両方が格納された場合において、前述のライセンス又は更新時間等の制約のためにその更新の一部のみがナビゲーション端末２０の保持する地図データに反映された場合に生成される。
【０１１４】
図７は、本発明の実施形態における一部のみが更新された道路ネットワークのデータ構造の説明図である。
【０１１５】
具体的には、図７は、図３に示す更新のうち、東京都側の更新のみが反映された地図データを示す。具体的には、リンク４０１及びノード４０２が追加され、これによってノード４１０に接続されるリンク数が増加する。一方、リンク４０３は追加されず、したがってノード４２０に接続されるリンク数は増加しない。
【０１１６】
言い換えると、図７に示すノード４１０及びリンク４０１は、図６に示すものと同じである。このため、図７に示すノードテーブル４４０はノードデータレコード４４１Ｄを含み、リンクテーブル４６０はリンクデータレコード４６１Ｉ及び４６１Ｋを含む。一方、図７に示すノード４２０は、図５に示すものと同じである。このため、図７に示すノードテーブル４４０はノードデータレコード４４１Ｃを含む。さらに、図７においてリンク４０３が存在しないという点は、図５と同じである。このため、図７に示すリンクテーブル４６０はリンクデータレコード４６１Ｈ及び４６１Ｊを含まない。
【０１１７】
図６の場合と同様に、図７においてもノード４０２は存在しているが、そこに接続されているリンクの数は図６に示したものと異なる。このため、図７のノードテーブル４４０は、ノードデータレコード４４１Ｆの代わりに、図７のノード４０２を記述するノードデータレコード４４１Ｇを含む。ノードデータレコード４４１ＧのノードＩＤ４５１Ｇの値は、ノード４０２の識別子「４０２」である。ノード４０２にはリンク４０１のみが接続されるため、ノードデータレコード４４１Ｇのリンク数４５３Ｇ及びリンクＩＤ４５４Ｇの値はそれぞれ「１」及び「４０１」である。このリンクＩＤ４５４Ｇからリンクデータレコード４６１Ｉが参照される。
【０１１８】
図８は、本発明の実施形態における別の一部のみが更新された道路ネットワークのデータ構造の説明図である。
【０１１９】
具体的には、図８は、図３に示す更新のうち、千葉県側の更新のみが反映された地図データを示す。具体的には、リンク４０３及びノード４０２が追加され、これによってノード４２０に接続されるリンク数が増加する。一方、リンク４０１は追加されず、したがってノード４１０に接続されるリンク数は増加しない。
【０１２０】
言い換えると、図８に示すノード４２０及びリンク４０３は、図６に示すものと同じである。このため、図８に示すノードテーブル４４０はノードデータレコード４４１Ｅを含み、リンクテーブル４６０はリンクデータレコード４６１Ｈ及びＪを含む。一方、図８に示すノード４１０は、図５に示すものと同じである。このため、図８に示すノードテーブル４４０はノードデータレコード４４１Ｂを含む。さらに、図８においてリンク４０１が存在しないという点は、図５と同じである。このため、図８に示すリンクテーブル４６０はリンクデータレコード４６１Ｉ及び４６１Ｋを含まない。
【０１２１】
図６の場合と同様に、図８においてもノード４０２は存在しているが、そこに接続されているリンクの数は図６に示したものと異なる。このため、図８のノードテーブル４４０は、ノードデータレコード４４１Ｆの代わりに、図８のノード４０２を記述するノードデータレコード４４１Ｈを含む。ノードデータレコード４４１ＨのノードＩＤ４５１Ｈの値は、ノード４０２の識別子「４０２」である。ノード４０２にはリンク４０３のみが接続されるため、ノードデータレコード４４１Ｈのリンク数４５３Ｈ及びリンクＩＤ４５４Ｈの値はそれぞれ「１」及び「４０３」である。このリンクＩＤ４５４Ｈからリンクデータレコード４６１Ｈが参照される。
【０１２２】
図７及び図８のいずれの地図データも、図６に示したような最新の地図データとは相違するが、リンクとノードの接続関係に矛盾はないため、このような地図データを使用しても、経路探索が正常に終了しない等といった問題は発生しない。
【０１２３】
次に、上記のような地図データの更新を行うために地図配信サーバ１０からナビゲーション端末２０に送信される更新エレメントについて説明する。
【０１２４】
図９Ａは、従来の更新エレメントの説明図である。
【０１２５】
具体的には、図９Ａは、図２に示した更新エレメント４３０の説明図であり、図５に示した地図データを図６のように更新するために送信される。
【０１２６】
更新エレメント４３０は、ノードテーブル４４０のノードデータレコード４４１Ｂを４４１Ｄに更新することを指示する情報、ノードデータレコード４４１Ｃを４４１Ｅに更新することを指示する情報、ノードデータレコード４４１Ｆをノードテーブル４４０に追加することを指示する情報、及び、リンクデータレコード４６１Ｈ〜４６１Ｋをリンクテーブル４６０に追加することを指示する情報を含む。
【０１２７】
図５に示す地図データを保持しているナビゲーション端末２０が図９Ａに示す更新エレメント４３０を受信すると、これに基づいて地図更新部２３が更新を実行し、その結果、ナビゲーション端末２０が保持する地図データは図６のように更新される。
【０１２８】
図９Ｂは、本発明の実施形態において使用される更新エレメント及び補正エレメントの説明図である。
【０１２９】
具体的には、図９Ｂは、図３に示した更新エレメント１＿４３１〜更新エレメント３＿４３３及び補正エレメント１＿４３４〜補正エレメント２＿４３５の説明図であり、図５に示した地図データを図６、図７又は図８のように更新するために送信される。
【０１３０】
更新エレメント１＿４３１は、ノードテーブル４４０のノードデータレコード４４１Ｂを４４１Ｄに更新することを指示する情報、及び、リンクデータレコード４６１Ｉをリンクテーブル４６０に追加することを指示する情報を含む。
【０１３１】
更新エレメント３＿４３３は、ノードテーブル４４０のノードデータレコード４４１Ｃを４４１Ｅに更新することを指示する情報、及び、リンクデータレコード４６１Ｈをリンクテーブル４６０に追加することを指示する情報を含む。
【０１３２】
更新エレメント２＿４３２は、ノードデータレコード４４１Ｆをノードテーブル４４０に追加することを指示する情報、及び、リンクデータレコード４６１Ｊ及び４６１Ｋをリンクテーブル４６０に追加することを指示する情報を含む。
【０１３３】
補正エレメント１＿４３４は、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｇに更新することを指示する情報、及び、リンクデータレコード４６１Ｊを削除することを指示する情報を含む。なお、ノードデータレコード４４１Ｇは、ノードデータレコード４４１ＦからリンクＩＤ４５４Ｆを削除し、さらに、リンク数４５３Ｆの値を「２」から「１」に変更したものと同じである。すなわち、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｇに更新することを指示する情報は、ノードデータレコード４４１Ｆのリンク数４５３Ｆの値を「２」から「１」に変更し、さらに、リンクＩＤ４５４Ｆを削除することを指示する情報と等価である。
【０１３４】
補正エレメント２＿４３５は、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｈに更新することを指示する情報、及び、リンクデータレコード４６１Ｋを削除することを指示する情報を含む。なお、ノードデータレコード４４１Ｈは、ノードデータレコード４４１ＦからリンクＩＤ４５５Ｆを削除し、さらに、リンク数４５３Ｆの値を「２」から「１」に変更したものと同じである。すなわち、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｈに更新することを指示する情報は、ノードデータレコード４４１Ｆのリンク数４５３Ｆの値を「２」から「１」に変更し、さらに、リンクＩＤ４５５Ｆを削除することを指示する情報と等価である。
【０１３５】
更新エレメント１＿４３１〜更新エレメント３＿４３３の三つを組み合わせたものは、更新エレメント４３０と等価である。このため、更新エレメント１＿４３１〜更新エレメント３＿４３３に基づいて図５に示す地図データを更新することによって、図６に示す地図データが得られる。
【０１３６】
更新エレメント１＿４３１、更新エレメント２＿４３２及び補正エレメント１＿４３４に基づいて図５に示す地図データを更新することによって、図７に示す地図データが得られる。更新エレメント３＿４３３、更新エレメント２＿４３２及び補正エレメント２＿４３５に基づいて図５に示す地図データを更新することによって、図８に示す地図データが得られる。
【０１３７】
ここで、補正エレメントに基づく更新の必要性を説明する。例として、更新エレメント１＿４３１及び更新エレメント２＿４３２に基づく更新を行い、補正エレメント１＿４３４に基づく更新を行わなかった場合について説明する。
【０１３８】
補正エレメント１＿４３４に基づく更新が行われた場合の更新後の地図データは図７に示した通りである。これに対して、補正エレメント１＿４３４に基づく更新が行われなかった場合、ノードテーブル４４０はノードデータレコード４４１Ｇの代わりにノードデータレコード４４１Ｆを含み、リンクテーブル４６０には、リンクデータレコード４６１Ｊが削除されずに残る。ノードデータレコード４４１ＦはリンクＩＤ４５４Ｆを含むが、リンクＩＤ４５４Ｆから参照されるはずのリンクデータレコード４６１Ｈは、リンクテーブル４６０に格納されていない。このため、ナビゲーション処理部２４が例えば経路探索のためにリンクＩＤ４５４Ｆに基づいてリンクデータレコード４６１Ｈを参照しようとすると、別のデータが誤って参照される。また、リンクデータレコード４６１Ｊはどのノードデータレコードからも参照されないため、記憶領域を有効に利用するためには削除することが望ましい。
【０１３９】
このように、補正エレメント１＿４３４に基づく更新が行われなかった場合、地図データに矛盾が残り、このために経路探索を正常に実行することができなくなる。一方、補正エレメント１＿４３４に基づく更新によって、図７に示すように、参照先のないリンクＩＤがノードデータレコードから削除され、さらに、どこからも参照されないリンクデータレコードも削除される。このため、地図データの矛盾が解消され、これによって経路探索の正常な実行が可能になる。
【０１４０】
上記のような更新エレメント及び補正エレメントは、地図配信サーバ１０が新バージョンの地図データを取得した後、更新データ抽出部１４によって作成され、更新データ記憶部１２に格納される。
【０１４１】
なお、図９Ｂに示した更新エレメント及び補正エレメントは一例であり、実際には種々の変形例が考えられる。
【０１４２】
具体的には、図９Ｂの例は、２種類の更新エレメントを含む。第１の種類の更新エレメントは、一つのパーセルの内側の（すなわちパーセル境界上のノードを除く）ノードの変更を指示する情報、及び、当該パーセルの内側のノードを終点とするリンクの変更を指示する情報を含む。更新エレメント１＿４３１及び更新エレメント３＿４３３がこれに相当する。第２の種類の更新エレメントは、二つのパーセルの境界上のノードの変更を指示する情報、及び、当該ノードを終点とするリンクの変更を指示する情報を含む。更新エレメント２＿４３２がこれに相当する。
【０１４３】
さらに、図９Ｂの例は、上記の第２の種類の更新エレメントの内容を補正するための補正エレメントを含む。すなわち、補正エレメントは、第２の種類の更新エレメントによって変更されたノード及びリンクの少なくとも一方をさらに変更することを指示する情報を含む。補正エレメント１＿４３４及び補正エレメント２＿４３５がこれに相当する。
【０１４４】
一方、第１の変形例は、例えば次の通りである。すなわち、第１の変形例は、２種類の更新エレメントを含む。第１の種類の更新エレメントは、一つのパーセルの内側の（すなわちパーセル境界上のノードを除く）ノードの変更を指示する情報、及び、当該パーセルの内側のノードを始点とするリンクの変更を指示する情報を含む。第２の種類の更新エレメントは、二つのパーセルの境界上のノードの変更を指示する情報、及び、当該ノードを始点とするリンクの変更を指示する情報を含む。さらに、第１の変形例は、上記の第２の種類の更新エレメントの内容を補正するための補正エレメントを含む。すなわち、第１の変形例の補正エレメントは、第２の種類の更新エレメントによって変更されたノード及びリンクの少なくとも一方をさらに変更することを指示する情報を含む。
【０１４５】
第２の変形例は、例えば次の通りである。すなわち、第２の変形例は、３種類の更新エレメントを含む。第１の種類の更新エレメントは、一つのパーセルの内側の（すなわちパーセル境界上のノードを除く）ノードの変更を指示する情報を含む。例えば、図９Ｂに示す情報のうち、ノードデータレコード４４１Ｂをノードデータレコード４４１Ｄに更新することを指示する情報がこれに相当する。
【０１４６】
第２の種類の更新エレメントは、二つのパーセルの境界上のノードの変更を指示する情報を含む。例えば、図９Ｂに示す情報のうち、リンクデータレコード４６１Ｉ及び４６１Ｋを追加することを指示する情報がこれに相当する。第３の種類の更新エレメントは、一つのパーセルの内側のリンクの変更を指示する情報を含む。例えば、図９Ｂに示す情報のうち、ノードデータレコード４４１Ｆを追加することを指示する情報がこれに相当する。
【０１４７】
さらに、第２の変形例は、上記の第２の種類の更新エレメントの内容を補正するための補正エレメントを含む。すなわち、第２の変形例の補正エレメントは、第２の種類の更新エレメントによって変更されたノードをさらに変更することを指示する情報を含む。例えば、図９Ｂに示す情報のうち、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｇに更新することを指示する情報がこれに相当する。
【０１４８】
次に、地図配信サーバ１０の管理データ記憶部１１に格納される情報について説明する。
【０１４９】
図１０は、本発明の実施形態の管理データ記憶部１１に格納される更新権利管理テーブル１０００の説明図である。
【０１５０】
更新権利管理テーブル１０００は、各ナビゲーション端末２０が有する地図データの更新権利を示す情報を保持する。具体的には、更新権利管理テーブル１０００は、端末ＩＤ１００１及び都道府県コード１００２を含む。
【０１５１】
端末ＩＤ１００１は、各ナビゲーション端末２０の識別子である。
【０１５２】
都道府県コード１００２は、各都道府県を識別するコードである。図１０の例では日本工業規格Ｘ０４０１によって規定された都道府県コードが使用されるが、その他の識別子が使用されてもよい。
【０１５３】
例えば、端末ＩＤ「１０」によって識別されるナビゲーション端末２０のユーザが、東京都の地図データを更新する権利（ライセンス）を購入した場合、そのナビゲーション端末２０は東京都の地図データを更新する権利を有するため、端末ＩＤ１００１の値「１０」に対応する都道府県コード１００２として、東京都を識別するコード「１３」が格納される。同様に、例えば、千葉県の地図データを更新する権利を有するナビゲーション端末２０に対応する都道府県コード１００２として千葉県を識別するコード「１２」が、東京都と千葉県の両方の地図データを更新する権利を有するナビゲーション端末２０に対応する都道府県コード１００２としてコード「１２」及び「１３」が格納される。
【０１５４】
なお、地図データを更新する権利が都道府県以外の領域（例えば国）ごとに管理される場合には、更新権利管理テーブル１０００に都道府県コードの代わりにその領域を識別するコードが格納される。他のテーブルについても同様である（図１１及び図１２参照）。
【０１５５】
図１１は、本発明の実施形態の管理データ記憶部１１に格納される更新エレメント管理テーブル１１００の説明図である。
【０１５６】
更新エレメント管理テーブル１１００は、各領域（例えば都道府県）に属するパーセルの地図データを更新するために使用される更新エレメントを特定する情報を含む。具体的には、更新エレメント管理テーブル１１００は、更新エレメントＩＤ１１０１及び都道府県コード１１０２を含む。
【０１５７】
更新エレメントＩＤ１１０１は、各更新エレメントの識別子である。図９Ｂに示す更新エレメント１＿４３１、更新エレメント２＿４３２及び更新エレメント３＿４３３の識別子は、それぞれ、「１」、「２」及び「３」である。
【０１５８】
都道府県コード１１０２は、図１０の都道府県コード１００２と同様、各都道府県を識別するコードである。
【０１５９】
図１１の例では、更新エレメントＩＤ１１０１の値「１」に対応する都道府県コード１１０２として「１３」が格納されている。これは、更新エレメント１＿４３１が東京都に属するパーセルの地図データを更新するために使用されること、言い換えると、東京都に属するパーセル内のノード及びリンクの更新を指示する情報を含むことを意味する。
【０１６０】
一方、図１１において、更新エレメントＩＤ１１０１の値「２」に対応する都道府県コード１１０２として「１２」及び「１３」が格納されている。これは、更新エレメント２＿４３２が、東京都に属するパーセルの地図データ及び千葉県に属するパーセルの地図データのいずれを更新するためにも使用されること、言い換えると、東京都に属するパーセルと千葉県に属するパーセルとの境界上のノードの更新を指示する情報を含むことを意味する。
【０１６１】
図１２は、本発明の実施形態の管理データ記憶部１１に格納される補正エレメント管理テーブル１２００の説明図である。
【０１６２】
補正エレメント管理テーブル１２００は、各領域（例えば都道府県）の境界における更新エレメントの補正に使用される補正エレメントを特定する情報を含む。具体的には、補正エレメント管理テーブル１２００は、補正エレメントＩＤ１２０１、都道府県コード１２０２及び接続先都道府県コード１２０３を含む。
【０１６３】
補正エレメントＩＤ１２０１は、各補正エレメントの識別子である。図９Ｂに示す補正エレメント１＿４３４及び補正エレメント２＿４３５の識別子は、それぞれ、「１」及び「２」である。
【０１６４】
都道府県コード１２０２及び接続先都道府県コード１２０３は、いずれも、図１０の都道府県コード１００２と同様、各都道府県を識別するコードである。都道府県コード１２０２によって識別される領域と、接続先都道府県コード１２０３によって識別される領域との境界を跨る連続したリンク及びノードのうち、都道府県コード１２０２によって識別される領域側のリンク及びノードのみを更新する場合に、補正エレメントＩＤ１２０１によって識別される補正エレメントに基づいて、当該境界に対応する更新エレメントが補正される。
【０１６５】
図１２の例では、補正エレメントＩＤ１２０１の値「１」に対応する都道府県コード１２０２及び接続先都道府県コード１２０３としてそれぞれ「１３」及び「１２」が格納されている。これは、東京都と千葉県との境界を跨る連続したリンク及びノードのうち、東京都に属するパーセル内のリンク及びノードのみを更新する場合に、補正エレメント１＿４３４に基づいて更新エレメント２＿４３２が補正されることを意味する。
【０１６６】
一方、補正エレメントＩＤ１２０１の値「２」に対応する都道府県コード１２０２及び接続先都道府県コード１２０３としてそれぞれ「１２」及び「１３」が格納されている。これは、東京都と千葉県との境界を跨る連続したリンク及びノードのうち、千葉県に属するパーセル内のリンク及びノードのみを更新する場合に、補正エレメント２＿４３５に基づいて更新エレメント２＿４３２が補正されることを意味する。
【０１６７】
次に、地図配信サーバ１０及びナビゲーション端末２０が地図データを更新するために実行する処理について説明する。
【０１６８】
図１３は、本発明の実施形態のナビゲーション端末２０が保持する地図データを更新するために実行される処理を示すフローチャートである。
【０１６９】
最初に、ナビゲーション端末２０が、これから地図データを更新しようとする領域（すなわち更新対象の領域）の識別コード（例えば都道府県コード）と、自身を識別する端末ＩＤと、を含む地図データ配信要求を地図配信サーバ１０に送信する（ステップ１３０１）。複数の領域の地図データを更新したい場合には、それらの複数の領域の識別コードが地図データ配信要求に含まれる。なお、更新対象の領域は、任意の方法によって決定される。例えば、ナビゲーション端末２０のユーザによって決定されてもよいし、所定のアルゴリズムに基づいて自動的に決定されてもよい。
【０１７０】
地図配信サーバ１０は、ステップ１３０１において送信された地図データ配信要求を受信すると、当該要求に含まれる端末ＩＤと、更新対象の領域の識別コードとに基づいて、ナビゲーション端末２０が有している権利を確認し（ステップ１３０２）、当該要求を送信したナビゲーション端末２０が、更新対象の領域の少なくとも一つに関して、更新の権利を有しているか否かを判定する（ステップ１３０３）。地図配信サーバ１０は、この確認及び判定のために、更新権利管理テーブル１０００を参照する。
【０１７１】
ステップ１３０３において、地図データ配信要求を送信したナビゲーション端末２０が、更新対象のいずれの領域についても更新の権利を有していないと判定された場合、更新を実行することができないため、地図配信サーバ１０は、更新不可を示す通知をナビゲーション端末２０に送信する（ステップ１３０４）。この通知を受信したナビゲーション端末２０は、更新対象の領域について更新権利を有していないことを示す情報を、画面入出力Ｉ／Ｆ２５を介して出力してもよい。
【０１７２】
一方、ステップ１３０３において、地図データ配信要求を送信したナビゲーション端末２０が、更新対象である少なくとも一つの領域において更新の権利を有していると判定された場合、地図配信サーバ１０は、更新エレメント管理テーブル１１００を参照して、配信対象の領域に対応する更新エレメントを収集する（ステップ１３０５）。ここで、配信対象の領域とは、ナビゲーション端末２０によって更新対象として指定された領域のうち、当該ナビゲーション端末２０が更新の権利を有している領域である。
【０１７３】
次に、地図配信サーバ１０は、補正エレメント管理テーブル１２００を参照して、都道府県コード１２０２の値がいずれかの配信対象領域の識別コードであり、かつ、接続先都道府県コード１２０３の値がいずれの配信対象領域の識別コードとも異なるレコードの補正エレメントＩＤ１２０１の値を取得し、その値に対応する補正エレメントを収集する（ステップ１３０６）。
【０１７４】
次に、地図配信サーバ１０は、ステップ１３０５及び１３０６において収集された更新エレメント及び補正エレメントをナビゲーション端末２０に送信する（ステップ１３０７）。
【０１７５】
ナビゲーション端末２０は、更新エレメント及び補正エレメントを地図配信サーバ１０から受信すると、それらに従って地図データ記憶部２７に格納されている地図データを更新する（ステップ１３０８）。
【０１７６】
上記のように、地図配信サーバ１０は、ナビゲーション端末２０から更新対象として指定された領域のうち、配信対象の領域（すなわち当該ナビゲーション端末２０が更新の権利を有している領域）のみを更新するための更新エレメント及び補正エレメントをステップ１３０８において送信する。更新対象として指定された複数の領域の一部が配信対象とならなかった場合、地図配信サーバ１０は、当該配信対象でない領域について、更新権利の欠如を示す情報をステップ１３０８においてナビゲーション端末２０に送信してもよい。この情報を受信したナビゲーション端末２０は、更新対象の領域について更新権利を有していないことを示す情報を、画面入出力Ｉ／Ｆ２５を介して出力してもよい。
【０１７７】
なお、上記の処理のうち、ステップ１３０１及び１３０８は、例えば、ナビゲーション端末２０の配信要求部２２及び地図更新部２３によってそれぞれ実行され、ステップ１３０２〜１３０７は、例えば、地図配信サーバ１０の更新データ管理部１５によって実行される。
【０１７８】
ここで、図３及び図５〜図１２を参照して、図１３の処理の具体例を説明する。
【０１７９】
図３に示す旧バージョンの地図データ２０１及び新バージョンの地図データ２０２が地図配信サーバ１０の地図データ記憶部１９に格納され、ナビゲーション端末２０の地図データ記憶部２７には旧バージョンの地図データ２０１のみが格納されている時点において、ナビゲーション端末２０が東京都及び千葉県の両方を更新対象として指定する情報、及び、自身の識別子「１０」を含む地図データ配信要求を地図配信サーバ１０に送信した（ステップ１３０１）場合を例として説明する。
【０１８０】
更新権利管理テーブル１０００には、端末ＩＤ「１０」に対応する都道府県コード１００２として、東京都を識別する「１３」のみが格納されているため、要求元のナビゲーション端末２０は、東京都の地図データを更新する権利は有しているが、千葉県の地図データを更新する権利は有していない（ステップ１３０２、１３０３）。
【０１８１】
この場合、配信対象領域は東京都であるため、地図配信サーバ１０は、更新エレメント管理テーブル１１００を参照して、東京都に対応する更新エレメント１＿４３１及び更新エレメント２＿４３２を選択する（ステップ１３０５）。さらに、地図配信サーバ１０は、補正エレメント管理テーブル１２００を参照して、都道府県コード１２０２が配信対象である東京都を示し、かつ、接続先都道府県コード１２０３が配信対象でない（図１２の例では「千葉県」である）レコードに対応する補正エレメント１＿４３４を選択する（ステップ１３０６）。
【０１８２】
そして、地図配信サーバ１０は、選択された更新エレメント１＿４３１、更新エレメント２＿４３２及び補正エレメント１＿４３４をナビゲーション端末２０に送信する（ステップ１３０７）。
【０１８３】
ナビゲーション端末２０は、例えば、まず受信した更新エレメント１＿４３１及び更新エレメント２＿４３２に基づいて地図データを更新し、次に補正エレメント１＿４３４に基づいて地図データを更新する（ステップ１３０８）。あるいは、ナビゲーション端末２０は、受信した補正エレメント１＿４３４に基づいて更新エレメント２＿４３２を補正し、受信した更新エレメント１＿４３１及び補正された更新エレメント２＿４３２に基づいて地図データを更新してもよい。これによって、図７に示すような更新後の地図データが地図データ記憶部２７に格納される。
【０１８４】
なお、ステップ１３０８において更新エレメント１＿４３１及び更新エレメント２＿４３２に基づく更新が開始されてから、補正エレメント１＿４３４に基づく更新が終了するまでの間、地図データ記憶部２７内の地図データに一時的に矛盾が発生し得る。このため、ナビゲーション端末２０は、受信した更新エレメント及び補正エレメントに基づく更新が開始されてから終了するまでの間、経路探索等の地図データを参照する処理を実行しないようにナビゲーション処理部２４等を制御する必要がある。
【０１８５】
一方、上記の具体例において、地図データ配信要求を送信したナビゲーション端末２０の識別子が「１２」であった場合、このナビゲーション端末２０は東京都及び千葉県の両方の地図データを更新する権利を有している（ステップ１３０２、１３０３）。このため、ステップ１３０５では更新エレメント１＿４３１、更新エレメント２＿４３２及び更新エレメント３＿４３３が選択される。一方、東京都及び千葉県のいずれも配信対象領域であるため、ステップ１３０６では、いずれの補正エレメントも選択されない。このため、ステップ１３０５で選択された三つの更新エレメントがナビゲーション端末２０に送信され（ステップ１３０７）、補正エレメントは送信されない。送信された更新エレメントに基づいて、ナビゲーション端末２０の地図データが図６に示すように更新される（ステップ１３０８）。
【０１８６】
以上のように、本発明の実施形態によれば、任意の範囲の地図データを矛盾なく更新することができる。
【０１８７】
以上の本発明の実施形態は、地図データの更新範囲が更新権利（ライセンス）の有無によって制限される場合を例として説明したが、本発明は、更新権利以外の要因によって更新範囲が制限される場合にも適用することができる。例えば、所定の時間内に更新を終了させたい場合がある。従来の方法によって作成された更新エレメント（例えば図９Ａ参照）に基づく更新が当該所定の時間内に終了しないと予測される場合には、その更新エレメントを分割してもよい。この分割は、図９Ｂを参照して説明した方法によって実行することができる。
【０１８８】
より詳細には、上記のような更新エレメントの分割は、図２〜図１３において説明したように都道府県等の領域ごとに行われてもよいが、その他の領域、例えばパーセルごとに行われてもよい。パーセルごとに分割される場合、図１０〜図１２において、都道府県コードの代わりにパーセルの識別子が使用される。更新権利管理テーブル１０００は省略されてもよい。この例において、図１３のステップ１３０１の地図データ配信要求は、都道府県コードの代わりに更新対象のパーセルの識別子を含んでもよい。この場合、ステップ１３０２及び１３０３は省略され、ステップ１３０５以降において、更新対象のパーセルが配信対象の領域として扱われる。
【０１８９】
このようにして分割された更新エレメント及び作成された補正エレメントに基づく更新を実行することによって、任意の範囲の地図データを矛盾なく更新することができる。
【符号の説明】
【０１９０】
１０ 地図配信サーバ
１１、２６ 管理データ記憶部
１２ 更新データ記憶部
１３ 更新時間予測処理部
１４ 更新データ抽出部
１５ 更新データ管理部
１６、２８ プロセッサ
１７、２９ メモリ
１８、２１ ネットワークインターフェース（Ｉ／Ｆ）
１９、２７ 地図データ記憶部
２０ ナビゲーション端末
２２ 配信要求部
２３ 地図更新部
２４ ナビゲーション処理部
２５ 画面入出力Ｉ／Ｆ
３０ 無線通信装置
３１ 無線基地局
４０ ネットワーク
４１ インターネット
【技術分野】
【０００１】
本発明は、地図データを利用したサービスを利用者に提供する技術に関し、特に、端末装置が保持する地図データを更新するためのデータを配信する技術に関する。
【背景技術】
【０００２】
自動車又は歩行者を対象とするナビゲーションサービスのような、地図データを用いたサービスが広く提供されている。このようなサービスを提供するために、ユーザが所持する端末は、道路ネットワークに関する情報を含む地図データを保持する。しかし、現実の道路は、新設又は付け替え等によって変更される場合がある。このような場合にも適切なサービスを提供するためには、端末が保持する地図データにもその変更を反映させる必要がある。しかし、広範囲の（例えば日本全国の）地図データをすべて更新する場合、更新対象のデータ量が多くなるため、相当の時間が必要になる。通常、端末は、地図データの更新を実行している間に、地図データを利用する処理（例えば経路探索等）を実行することができないため、そのような処理を実行していない時間帯に更新を実行することが望ましい。このため、現在では、所定の大きさの領域ごとに、差分データ（すなわち古いバージョンの地図データと新しいバージョンの地図データとの差分）のみを更新する方法が知られている。
【０００３】
一般に、地図データは、パーセルと呼ばれる地図上の所定の大きさの領域ごとに管理される。例えば、端末は、経路探索等の処理を実行していないある時間帯に、その時間内に更新が終了する分のパーセルの差分データを更新し、残りのパーセルについては、経路探索等の処理を実行していない別の時間帯に更新することもできる。これによって、経路探索等の処理を阻害しないように地図データを更新することができる。
【０００４】
しかし、上記のようにパーセルごとに地図データを更新すると、更新されたパーセルと更新されていないパーセルとの境界においてデータの矛盾が生じる場合がある。例えば、複数のパーセルにまたがる道路が新設された場合において、それらのうち一部のパーセルのみの地図データが更新されると、更新後の地図データにおいて道路がパーセルの境界で途切れる。端末がこのような矛盾した地図データを保持していると、誤ったデータが参照されるなどの問題が発生するため、経路探索等の処理を正常に実行できなくなる。このような矛盾の発生を防ぐために、例えば、指定された領域の地図データに加えて、その領域の更新の影響が及ぶ範囲の地図データも端末に送信する技術が開示されている（例えば特許文献１及び特許文献２参照）。あるいは、連続した道路の変更（追加又は削除等）を反映する更新データの集合を地図データ更新の最小単位として扱う技術が開示されている（例えば非特許文献１参照）。このような地図データ更新の最小単位は更新エレメントとも呼ばれ、更新エレメントごとに地図データが更新される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第０６／０１１２７８号
【特許文献２】特開２００６−３１７６４８号公報
【非特許文献】
【０００６】
【非特許文献１】“地図更新サービス／ソリューション”、［ｏｎｌｉｎｅ］、［平成２２年１１月１２日検索］、インターネット＜ＵＲＬ：http://www.hitachi-automotive.co.jp/products/cis/02.html＞
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記の文献に記載された方法では、地図データを更新する範囲を任意に決定することができない。これは、更新の影響が及ぶ範囲が更新の内容に依存するためである。例えば新しいバージョンの地図データにおける更新箇所が広範囲に及ぶ場合、更新の影響が及ぶ範囲（又は更新エレメント）も大きくなる。
【０００８】
しかし、実際には、地図データの更新範囲を任意に指定したい場合がある。例えば、端末のユーザが特定の地域のみの地図データのライセンスを購入した場合、ライセンスされた地域のみの地図データを更新する必要がある。しかし、従来は、ライセンスされた地域とそれ以外の地域とに跨る連続した道路が変更されている場合、ライセンスされた地域の地図データのみを矛盾が生じないように更新することはできなかった。あるいは、経路探索等の処理が実行されていない時間帯に更新を終了させるために、巨大な更新エレメントを分割する必要が生じる場合もある。このような場合にも、分割された更新エレメントに基づいて矛盾が生じないように地図データを更新することはできなかった。
【０００９】
本発明は上記の問題点に鑑みてなされたものであり、任意の範囲の地図データを、矛盾が生じないように更新することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の代表的な一例を示せば次の通りである。すなわち、ネットワークに接続され、前記ネットワークを介して地図データを配信する地図データ配信サーバであって、前記地図データ配信サーバは、前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、地図上の空間を分割することによって定義された複数の領域に対応する第１の地図データと、前記複数の領域に対応する、前記第１の地図データより新しいバージョンの第２の地図データと、を保持し、前記第１の地図データ及び第２の地図データは、道路上の地点に対応するノード及び前記地点を結ぶ道路上の区間に対応するリンクを示す情報を含み、前記複数の領域は、第１領域及び前記第１領域に隣接する第２領域を含み、前記地図データ配信サーバは、前記第１の地図データを前記第２の地図データに更新するための差分データとして、前記第１領域内のノード及びリンクの変更を指示する第１情報、前記第２領域内のノード及びリンクの変更を指示する第２情報、前記第１領域と前記第２領域との境界上のノードの変更を指示する第３情報、及び、前記第３情報に基づいて変更された境界上のノードのさらなる変更を指示する第４情報を保持し、前記第１領域を含む一つ以上の領域の地図データを更新するための地図データ配信要求を、前記ネットワークを介して受信すると、前記第１情報、前記第２情報及び前記第３情報の組、又は、前記第１情報、前記第３情報及び前記第４情報の組のいずれかを、前記ネットワークを介して送信することを特徴とする。
【発明の効果】
【００１１】
本発明の一実施形態によれば、任意の範囲の地図データを、矛盾が生じないように更新することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施形態の地図データ配信システムの構成を示すブロック図である。
【図２】従来の更新エレメントを用いた地図データの更新の説明図である。
【図３】本発明の実施形態の地図データ配信システムにおいて実行される、補正エレメントを用いた地図更新の説明図である。
【図４】本発明の実施形態の地図データ配信システムにおいて使用される地図データに含まれる道路ネットワークのデータ構造の説明図である。
【図５】本発明の実施形態における更新前の道路ネットワークのデータ構造の説明図である。
【図６】本発明の実施形態における更新後の道路ネットワークのデータ構造の説明図である。
【図７】本発明の実施形態における一部のみが更新された道路ネットワークのデータ構造の説明図である。
【図８】本発明の実施形態における別の一部のみが更新された道路ネットワークのデータ構造の説明図である。
【図９Ａ】従来の更新エレメントの説明図である。
【図９Ｂ】本発明の実施形態において使用される更新エレメント及び補正エレメントの説明図である。
【図１０】本発明の実施形態の管理データ記憶部に格納される更新権利管理テーブルの説明図である。
【図１１】本発明の実施形態の管理データ記憶部に格納される更新エレメント管理テーブルの説明図である。
【図１２】本発明の実施形態の管理データ記憶部に格納される補正エレメント管理テーブルの説明図である。
【図１３】本発明の実施形態のナビゲーション端末が保持する地図データを更新するために実行される処理を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、図面を用いて本発明の実施の形態を説明する。
【００１４】
図１は、本発明の実施形態の地図データ配信システムの構成を示すブロック図である。
【００１５】
本実施形態の地図データ配信システムは、ネットワーク４０に接続された地図配信サーバ１０と、ネットワーク４０を介して地図配信サーバ１０と通信するナビゲーション端末２０と、を備える。
【００１６】
地図配信サーバ１０は、互いに接続されたプロセッサ１６、メモリ１７、ネットワークインターフェース（Ｉ／Ｆ）１８、管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１９を備える計算機である。
【００１７】
プロセッサ１６は、メモリ１７に格納されたプログラムを実行する。
【００１８】
メモリ１７は、例えば半導体メモリであり、プロセッサ１６によって実行されるプログラム、プロセッサ１６によって参照されるデータ、及びプロセッサ１６から出力されたデータ等を格納する。本実施形態のメモリ１７には、少なくとも、プロセッサ１６によって実行されるプログラムである更新データ抽出部１４及び更新データ管理部１５が格納される。プロセッサ１６がプログラムを実行することによって実現される処理については後述する。以下の説明において更新データ抽出部１４等が実行する処理は、実際には、プロセッサ１６が更新データ抽出部１４等のプログラムに従って実行する。
【００１９】
ネットワークＩ／Ｆ１８は、ネットワーク４０に接続され、ナビゲーション端末２０等と通信する。
【００２０】
管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１９は、それぞれがハードディスクドライブ（ＨＤＤ）又はフラッシュメモリのような記憶装置であってもよいし、一つの記憶装置内の記憶領域であってもよい。
【００２１】
地図データ記憶部１９には、地図データが格納される。地図データは、地図の構成物（地物）の位置及び形状を示す座標値等を含む。現実の地物は随時更新される。その一例は、道路の新設、廃止又は付け替えのような道路ネットワークの更新である。地図データは、過去のある時点における地物に関する情報、及び、それより後の時点における地物に関する情報（言い換えると、旧バージョンの地図データ及び新バージョンの地図データ）を含んでもよい。
【００２２】
なお、一般に地図データは、地図上の所定の矩形の範囲ごとに管理される。この矩形の範囲は、パーセル又はメッシュと呼ばれる。各パーセルには固有の識別子（パーセルＩＤ）が付与される。
【００２３】
更新データ記憶部１２には、地物を単位とする地図更新データ（地図情報及び道路ネットワーク情報を含む）が格納される。地図更新データは、例えばナビゲーション端末２０があるバージョンの地図データを保持している場合に、それをより新しいバージョンの地図データに更新するために作成及び送信されるデータであり、具体的には、少なくともこれらのバージョンの差分データを含む。具体的には、更新データ記憶部１２には、少なくとも、地図データの更新を指示する情報を含む更新エレメント、及び、更新エレメントが指示する更新の内容をさらに変更する情報を含む補正エレメントが格納される。これらの詳細については後述する（図９Ｂ参照）。
【００２４】
管理データ記憶部１１には、地図更新データを管理するための情報が格納される。例えば、管理データ記憶部１１には、地図更新データのバージョン（すなわち差分の世代）を示す情報、及び、地図更新データが適用されるべき位置を示すパーセルＩＤ等が格納される。さらに、本実施形態の管理データ記憶部１１には、少なくとも、更新権利管理テーブル１０００（図１０参照）、更新エレメント管理テーブル１１００（図１１参照）及び補正エレメント管理テーブル１２００（図１２参照）が格納される。これらの詳細については後述する。
【００２５】
ナビゲーション端末２０は、ユーザを目的地まで誘導するために、経路検索及び検索結果の出力等を行う移動端末であり、例えば、自動車に搭載される車載用ナビゲーション端末又は歩行者に携帯される歩行者用ナビゲーション端末である。後者の場合、ナビゲーション端末２０は、ナビゲーション用のアプリケーションソフトウェアが組み込まれた携帯電話機等であってもよい。
【００２６】
図１では省略されているが、一般に、地図データ配信システムは、複数のナビゲーション端末２０を含む。また、本実施形態では、端末装置の典型的な例としてナビゲーション端末２０を示すが、地図情報を保持して利用するものである限り、いかなる種類の端末装置にも本発明を適用することができる。
【００２７】
本実施形態のナビゲーション端末２０は、互いに接続されたプロセッサ２８、メモリ２９、ネットワークＩ／Ｆ２１、画面入出力Ｉ／Ｆ２５、管理データ記憶部２６及び地図データ記憶部２７を備える。
【００２８】
プロセッサ２８は、メモリ２９に格納されたプログラムを実行する。
【００２９】
メモリ２９は、例えば半導体メモリであり、プロセッサ２８によって実行されるプログラム及びプロセッサ２８によって参照されるデータ等を格納する。本実施形態のメモリ２９には、プロセッサ２８によって実行されるプログラムである配信要求部２２、地図更新部２３及びナビゲーション処理部２４が格納される。
【００３０】
配信要求部２２は、地図更新データ配信要求を地図配信サーバ１０に送信する。地図更新部２３は、配信された地図更新データを用いて、地図データ記憶部２７に格納された地図データを更新する。これらの処理については後述する。以下の説明において配信要求部２２、地図更新部２３及びナビゲーション処理部２４によって実行される処理は、実際にはプロセッサ２８が各プログラムに従って実行する。
【００３１】
ナビゲーション処理部２４は、地図データ記憶部２７に格納された地図データに基づいて、目的地までの経路を検索し、その経路に沿ってユーザを誘導する。このような経路検索及び誘導は従来の車載用ナビゲーション端末と同様に公知の方法によって実行できるため、これらに関する詳細な説明は省略する。
【００３２】
画面入出力Ｉ／Ｆ２５は、ユーザに対して地図情報等を表示する画面と、ユーザからの入力を受け付ける入力装置と、を含む。例えば、画面入出力Ｉ／Ｆ２５は、液晶表示装置及びキーボード等であってもよいし、タッチパッド付きの液晶表示装置であってもよい。
【００３３】
ネットワークＩ／Ｆ２１は、無線通信装置３０に接続される。無線通信装置３０は、ネットワーク４０に接続された無線基地局３１と無線通信を行う。ネットワークＩ／Ｆ２１は、無線通信装置３０、無線基地局３１及びネットワーク４０を介して地図配信サーバ１０との間の通信を実行する。後述する地図データ配信要求の送信及び地図更新データの受信はこのような通信によって実現される。
【００３４】
なお、無線通信装置３０は、ナビゲーション端末２０に内蔵されてもよい。
【００３５】
管理データ記憶部２６及び地図データ記憶部２７は、それぞれがハードディスクドライブ（ＨＤＤ）又はフラッシュメモリのような記憶装置であってもよいし、一つの記憶装置内の記憶領域であってもよい。
【００３６】
地図データ記憶部２７には、ナビゲーション処理部２４によって参照される地図データが格納される。この地図データは、地図配信サーバ１０から送信された地図更新データに基づいて更新される。
【００３７】
管理データ記憶部２６には、地図データを管理するための情報が格納される。例えば、管理データ記憶部２６には、ナビゲーション端末２０自身の位置がどのパーセルに属するかを示す緯度経度−パーセルＩＤ対応情報、及び、地図に適用した地図更新データの識別情報等が格納される。
【００３８】
ネットワーク４０はインターネット４１に接続される。地図配信サーバ１０は、インターネット４１を介して新しいバージョンの地図データを取得してもよい。
【００３９】
続いて、地図データの更新の概要を説明する。
【００４０】
図２は、従来の更新エレメントを用いた地図データの更新の説明図である。
【００４１】
ここでは、例として、東京都に属するパーセル３０７と、それに隣接する千葉県に属するパーセル３０８とに跨る道路が新設され、その道路に対応する情報が追加される例を示す。なお、東京都及び千葉県は、地上に（及びそれに対応する地図上に）区切られた領域の例であり、これらは任意の領域、典型的には行政区画又は国によって置き換えることができる。例えば、ヨーロッパのように多くの国の国境が陸上にある場合、パーセル３０７がある国に属し、パーセル３０８がそれに隣接する別の国に属してもよい。
【００４２】
厳密に言えば、一般にパーセルの境界と都県境（又は国境）とは一致しないが、本実施形態ではデータを管理する便宜上、各パーセルがいずれかの都又は県に属するものとして扱われる。
【００４３】
一般に、地図データは種々の地物に関する情報を含むが、本発明はそれらのうち道路に関する情報の更新を対象としている。このため、以下、地図データとして道路に関する情報を説明し、その他の地物に関する説明は省略する。
【００４４】
周知のように、道路は、複数のノードと、それらを接続するリンクと、からなるネットワークとして記述され、それが地図データとして格納される。ノードは、一般には複数の道路の交差点に対応するが、道路上の交差点以外の点に対応する場合もある。例えばパーセルの境界線と道路とが交差する点もノードとして記述される。リンクは、二つのノードに対応する二つの地点を接続する道路の区間に対応する。各ノード及びリンクを記述する情報は、それぞれ地図データ内のノードテーブル及びリンクテーブルに含まれる。これらのテーブルの構造については後述する（図４Ｂ等参照）。
【００４５】
図２の例では、旧バージョンの地図データ２０１におけるパーセル３０７がノード４１０、４１１、４１２、リンク４１３及び４１４を含み、パーセル３０８がノード４２０、４２１、４２２、リンク４２３及び４２４を含む。リンク４１３はノード４１０と４１１とを接続し、リンク４１４はノード４１０と４１２とを接続し、リンク４２３はノード４２０と４２１とを接続し、リンク４２４はノード４２０と４２２とを接続する。なお、説明の便宜上、ノード４１１及び４１２をパーセル３０７に含まれるノードとして記載しているが、正確には、これらのノードはパーセル３０７とそれに隣接するパーセル（図示省略）との境界線上のノードである。ノード４２１及び４２２も同様に、パーセル３０８とそれに隣接するパーセルとの境界線上のノードである。
【００４６】
一方、新バージョンの地図データ２０２では、ノード４０２、リンク４０１及び４０３が追加されている。リンク４０１はノード４０２と４１０とを接続し、リンク４０３はノード４０２と４２０とを接続する。ノード４０２はパーセル３０７と３０８との境界線上のノードである。新たに追加されたノード及びリンクは、ノード４１０とノード４２０とを接続する。これは、ノード４１０に対応する地点とノード４２０に対応する地点とを接続する道路が新設されたことを意味する。
【００４７】
一般に、地図データは、現実の道路の変更が反映されるように所定のタイミングで（例えば数ヶ月ごとに）更新される。更新された地図データは、例えば、地図情報を扱う出版社によって作成され、インターネット４１を介して提供される。新しい地図データが提供された場合、地図配信サーバ１０の地図データ記憶部１９には、更新される前の（すなわち旧バージョンの）地図データ２０１と、更新された後の（すなわち新バージョンの）地図データ２０２の両方が格納される。
【００４８】
その時点で、ナビゲーション端末２０の地図データ記憶部２７には旧バージョンの地図データ２０１が格納されており、新バージョンの地図データ２０２は格納されていない。配信要求部２２は、地図データ配信要求を地図配信サーバ１０に送信し、それに応じて送信された地図データ（すなわち更新データ）を用いて地図更新部２３が地図データ記憶部２７内の地図を新バージョンに更新する。地図データ配信要求は、種々のイベント、例えば前回の配信から所定の時間が経過したこと、所定の日時が到来したこと、ユーザから更新要求を入力されたこと、などを契機として送信され得る。
【００４９】
地図データがノード及びリンクによって記述されるため、地図データの更新は、新たなノード若しくはリンクの追加、既存のノード若しくはリンクの削除、又は、既存のノード若しくはリンクを記述する情報の変更、のいずれか、又はそれらの組み合わせによって記述することができる。送信される更新データは、このようにして記述された情報を含む。
【００５０】
地図データの更新を実行する具体的な方法の一例として、パーセルごとの更新が挙げられる。例えば、配信要求部２２が更新対象のパーセルの指定を含む地図データ配信要求を地図配信サーバ１０に送信し、地図配信サーバ１０は指定されたパーセルの更新データを送信する。
【００５１】
しかし、パーセルごとの更新が行われた場合、例えば東京都側のノード４１０、４０２及びリンク４０１は更新されたが、千葉県側のノード４２０及びリンク４０３は更新されていない状態が出現し得る。その状態の地図データは、リンクの途切れ、例えば、ノード４０２は二つのリンクに接続されていることを示す情報を含むが、実際には一つのリンクの情報しか地図データ記憶部２７に格納されていない、といった矛盾を含んでいる。このような矛盾を含む地図データを用いると、誤ったデータが参照されることによって、経路探索が正常に終了しない場合がある。
【００５２】
このような矛盾を防ぐための更新方法として、更新エレメントごとの更新が知られている。更新エレメントは、連続したリンク及びそれらが接続されたノードに関する更新データの集合であり、これが地図データの更新単位として使用される。図２の例では、ノード４０２の追加、リンク４０１及び４０３の追加、及び、ノード４１０及び４２０を記述する情報の変更、を示す更新エレメント４３０が更新データ抽出部１４によって作成され、これが地図配信サーバ１０からナビゲーション端末２０に送信される。
【００５３】
更新エレメントごとに地図データを更新することによって、上記のような地図データの矛盾の発生を防止することができる。しかし、実際には、連続したリンク等の更新のうち一部のみを実行することが望まれる場合もある。その一例は、更新データ（言い換えると、地図データを更新する権利）を都道府県又は国等の領域ごとに販売したい場合である。例えばヨーロッパのように国境を跨る道路ネットワークが存在する領域において、国ごとに更新データを販売したいというニーズがあり得る。
【００５４】
別の一例は、地図データの更新時間が制限される場合である。一般にナビゲーション端末２０は潤沢なハードウェア資源を持たないため、地図データの更新を実行している間、地図データを使用する機能（例えば経路探索等）を使用できなくなるか、又は速度が大幅に低下するなどの制約を受ける。このため、地図データの更新は、経路探索等が実行されない時間帯（例えば夜間又は休憩中など）に実行されることが望ましい。しかし、更新エレメントのデータ量が多いために上記の時間帯に更新が終了しない場合もあり、そのような場合には連続したリンク等の更新データを含む一つの更新エレメントを複数に分割することが望まれる。
【００５５】
本発明の実施形態では、このようなニーズに対応するため、以下に説明する更新方法が採用される。
【００５６】
図３は、本発明の実施形態の地図データ配信システムにおいて実行される、補正エレメントを用いた地図更新の説明図である。
【００５７】
図３において、旧バージョンの地図データ２０１及び新バージョンの地図データ２０２は、いずれも図２に示したものと同じである。ただし、新バージョンの地図データ２０２の更新箇所をナビゲーション端末２０に反映させるための更新エレメントは図２に示したものと異なる。具体的には、図３において、地図データ２０２の更新箇所を反映させるための更新エレメントは、更新エレメント１＿４３１、更新エレメント２＿４３２、更新エレメント３＿４３３、補正エレメント１＿４３４及び補正エレメント２＿４３５からなる。
【００５８】
なお、図２に示した従来の更新エレメントは、例えば非特許文献１にも記載されているように、更新後の地図データに矛盾を生じさせない更新データの最小単位であった。一方、図３に示す本実施形態の更新エレメントは、単に更新データの管理単位であり、更新エレメントごとに更新を行っても更新後の地図データに矛盾が残る場合がある。更新後の地図データに矛盾を残さないためには、後述するように、複数の更新エレメント又は更新エレメントと補正エレメントを適切に組み合わせることが求められる場合がある。
【００５９】
更新エレメント１＿４３１、更新エレメント２＿４３２及び更新エレメント３＿４３３は、それぞれ、図２に示した更新エレメント４３０の一部に相当する。すなわち、更新エレメント１＿４３１はリンク４０１の追加及びノード４１０の変更を記述する情報を含み、更新エレメント２＿４３２はノード４０２の追加を記述する情報を含み、更新エレメント３＿４３３はリンク４０３の追加及びノード４２０の変更を記述する情報を含む。
【００６０】
更新エレメント１＿４３１から更新エレメント３＿４３３までの全てを用いてナビゲーション端末２０の地図データを更新した場合、その結果は、更新エレメント４３０を使用した結果と同じになり、地図データの矛盾は発生しない。ただし、これらの三つの更新エレメントのうち最初の一つに基づく更新が開始されてから、最後の一つに基づく更新が終了するまでの間は、一時的に地図データの矛盾が発生し得るため、その間に地図データを参照する処理（経路探索等）を実行しないように、ナビゲーション端末２０を制御する必要がある。
【００６１】
一方、これらの三つの更新エレメントの一部のみに基づいて地図データを更新した場合、既に説明したように、地図データの矛盾が発生する。補正エレメント１＿４３４及び補正エレメント２＿４３５は、このような場合に発生した地図データの矛盾を解消するために使用される。
【００６２】
例えば、更新エレメント１＿４３１及び更新エレメント２＿４３２に基づく更新を行い、更新エレメント３＿４３３に基づく更新は行わなかった場合、更新後の地図データには、ノード４０２を記述する情報として、ノード４０２にリンク４０１及び４０３の二つが接続されることを示す情報が含まれるが、リンク４０３そのものを記述する情報は含まれない。このような矛盾を解消するため、補正エレメント１＿４３４は、ノード４０２を記述する情報から、ノード４０２にリンク４０３が接続されることを示す情報を削除する指示を含む。同様に、補正エレメント２＿４３５は、ノード４０２を記述する情報から、ノード４０２にリンク４０１が接続されることを示す情報を削除する指示を含む。このような本実施形態の更新エレメント及び補正エレメントの詳細な内容については後述する。
【００６３】
なお、図３では、便宜上、補正エレメントを更新エレメント近傍の破線の楕円によって示しているが、その内容は、上記のように、更新エレメントに含まれる情報の補正（削除又は追加等）を指示する情報である。
【００６４】
図４は、本発明の実施形態の地図データ配信システムにおいて使用される地図データに含まれる道路ネットワークのデータ構造の説明図である。
【００６５】
図４には、例として、ノード１００〜１０３及びリンク１１０〜１１２からなるネットワークを示す。ここで、リンク１１０はノード１００及び１０３を、リンク１１１はノード１００及び１０１を、リンク１１２はノード１００及び１０２を接続する。
【００６６】
このようなネットワークは、ノードテーブル４４０及びリンクテーブル４６０に格納されたデータによって記述される。これらのテーブルのデータ構造は、従来のものと同様であってよいため、詳細な説明は省略するが、概要を説明すると次の通りである。
【００６７】
例えば、ノード１００は、ノードテーブル４００に格納されたノードデータレコード４４１Ａによって記述される。
【００６８】
ノードデータレコード４４１Ａは、ノードＩＤ４５１Ａ、ノード属性４５２Ａ、リンク数４５３Ａ、リンクＩＤ４５４Ａ、リンクＩＤ４５５Ａ及びリンクＩＤ４５６Ａを含む。
【００６９】
ノードＩＤ４５１Ａとして、ノードデータレコード４４１Ａが記述するノード（以下、「当該ノード」とも記載する。ノードデータレコード４４１Ａの場合、当該ノードはノード１００である）の識別子（ＩＤ）が格納される。本実施形態では、説明の便宜上、ノードの参照符号と同じ値をノードの識別子として使用する。すなわち、当該ノード（ノード１００）の識別子「１００」がノードＩＤ４５１Ａとして格納される。
【００７０】
ノード属性４５２Ａとして、当該ノードの属性を示す情報が格納される。
【００７１】
リンク数４５３Ａとして、当該ノードに接続されたリンクの数を示す値が格納される。図４の例では、ノード１００に三つのリンクが接続されているため、リンク数４５３Ａとして「３」が格納される。
【００７２】
リンクＩＤ４５４ＡからリンクＩＤ４５６Ａとして、当該ノードに接続されたリンクの識別子が格納される。本実施形態では、ノードの場合と同様、リンクの参照符号と同じ値がリンクの識別子として使用される。図４の例では、ノード１００に接続された三つのリンクの識別子「１１０」、「１１１」及び「１１２」がそれぞれリンクＩＤ４５４Ａ、リンクＩＤ４５５Ａ及びリンクＩＤ４５６Ａとして格納される。リンクＩＤ４５４ＡからリンクＩＤ４５６Ａは、各リンクを記述するリンクデータレコードが格納された領域のアドレスを示す値（ポインタ等）を含む。例えば、リンクＩＤ４５４Ａの値に基づいて、リンク１１０を記述するリンクデータレコード４６１Ａ（後述）を参照することができる。
【００７３】
なお、ノード１０１、１０２及び１０３を記述するノードデータレコードの図示は省略するが、それらのデータ構造は、ノードデータレコード４４１Ａのデータ構造と同様である。
【００７４】
一方、リンク１１０、１１１及び１１２は、それぞれ、リンクテーブル４６０に格納されたリンクデータレコード４６１Ａ、４６１Ｂ及び４６１Ｃによって記述される。
【００７５】
リンクデータレコード４６１Ａは、リンクＩＤ４７１Ａ、リンク属性４７２Ａ、リンクコスト４７３Ａ、リンク形状４７４Ａ及び接続ノードＩＤ４７５Ａを含む。
【００７６】
リンクＩＤ４７１Ａとして、リンクデータレコード４６１Ａが記述するリンク（ここでは当該リンクと記載する）の識別子が格納される。すなわち、当該リンク（この例ではリンク１１０）の識別子「１１０」がリンクＩＤ４７１Ａとして格納される。
【００７７】
リンク属性４７２Ａとして、当該リンクの属性を示す情報が格納される。当該リンクの属性を示す情報の一例は、通行規制（例えば通行可能か否か、及び、通行可能な時間帯等）を示す情報である。
【００７８】
リンクコスト４７３Ａとして、当該リンクに対応する区間の長さ又はその区間を通過するために要する時間等が格納される。
【００７９】
リンク形状４７４Ａとして、当該リンクの形状を示す値、例えば、座標値の列が格納される。
【００８０】
接続ノードＩＤ４７５Ａとして、当該リンクによって接続されるノードの識別子が格納される。図４の例ではリンク１１０がノード１０３に接続されるため、接続ノードＩＤ４７５Ａとして「１０３」が格納される。
【００８１】
なお、図４では、二つのノードを接続する一つの区間に対応して一つのリンクが図示されているが、実際には、図示された各リンクは、互いに対向する方向の二つの片方向リンクの組に相当する。図２及び図３等についても同様である。リンクテーブル４６０に含まれる各リンクデータレコードは、各片方向リンクを記述する。
【００８２】
例えば、ノード１０３とノード１００とを接続するリンク１１０は、実際には、ノード１００を始点とし、ノード１０３を終点とする方向のリンク（すなわち、リンク１１０に対応する道路の区間における、当該方向の通行に対応するリンク）と、その逆方向のリンクと、の組に相当する。リンクデータレコード４６１Ａは、ノード１００を記述するノードデータレコード４４１ＡのリンクＩＤ４５４Ａから参照され、リンクデータレコード４６１Ａ内の接続ノードＩＤ４７５Ａとしてノード１０３の識別子が格納される。これは、リンクデータレコード４６１Ａが、リンク１１０に相当する二つの片方向リンクのうち、ノード１００からノード１０３への方向のリンクを記述していることを意味する。
【００８３】
図４では省略されているが、リンクテーブル４６０は、リンク１１０に相当する二つの片方向リンクのうち、残る一方向のリンクを記述するリンクデータレコードも含む。そのリンクデータレコードは、ノード１０３を記述するノードデータレコード（図示省略）内のリンクＩＤ（図示省略）から参照され、接続ノードＩＤの値「１００」を含む。
【００８４】
道路の区間によっては、通行方向ごとに適用される通行規制及びコストが異なる場合があり（例えば一方通行等）、その場合は、図示された一つのリンクに対応する二つのリンクデータレコードのリンク属性及びコストの値が異なる。例えば、リンク１１０が一方通行区間である場合、リンク１１０に対応する二つのリンクデータレコードのうち一方のリンク属性として通行可能の属性が、もう一方のリンク属性として通行禁止の属性が与えられる。
【００８５】
リンクデータレコード４６１Ｂ及び４６１Ｃのデータ構造もリンクデータレコード４６１Ａと同様であるため、それらの詳細な説明は省略する。リンクデータレコード４６１Ｂは、ノードデータレコード４４１ＡのリンクＩＤ４５５Ａから参照され、リンクＩＤ４７１Ｂの値「１１１」及び接続ノードＩＤ４７５Ｂの値「１０１」を含む。リンクデータレコード４６１Ｃは、ノードデータレコード４４１ＡのリンクＩＤ４５６Ａから参照され、リンクＩＤ４７１Ｃの値「１１２」及び接続ノードＩＤ４７５Ｃの値「１０２」を含む。
【００８６】
なお、リンクデータレコード４６１Ｂは、リンク１１１のノード１００から１０１への方向の通行を記述するものであり、リンクデータレコード４６１Ｃは、リンク１１２のノード１００から１０２への方向の通行を記述するものである。図４では省略されているが、それぞれのリンクの逆方向の通行を記述するリンクデータレコードもリンクテーブル４６０に含まれる。
【００８７】
次に、図３を参照して説明した地図データの更新を、ノードテーブル及びリンクテーブルを参照しながら具体的に説明する。
【００８８】
図５は、本発明の実施形態における更新前の道路ネットワークのデータ構造の説明図である。
【００８９】
具体的には、図５は、図３の旧バージョンの地図データ２０１を記述するノードテーブル４４０及びリンクテーブル４６０を示す。これらのデータ構造は図４を参照して説明したものと同様であるため、以下、地図データの更新を説明するために必要な項目のみを説明し、その他の項目の説明は省略する。図６以降のテーブルについても同様である。
【００９０】
図５に示すノードテーブル４４０は、ノード４１０を記述するノードデータレコード４４１Ｂ及びノード４２０を記述するノードデータレコード４４１Ｃを含む。ノードテーブル４４０は、さらにノード４１１、４１２、４２１及び４２２を記述するノードデータレコードも含むが、これらの図示は省略する。
【００９１】
ノードデータレコード４４１ＢのノードＩＤ４５１Ｂとして、ノード４１０の識別子「４１０」が格納される。ノード４１０には二つのリンクすなわちリンク４１３及び４１４が接続されるため、ノードデータレコード４４１Ｂのリンク数４５３Ｂ、リンクＩＤ４５４Ｂ及びリンクＩＤ４５５Ｂには、それぞれ、「２」、「４１３」及び「４１４」が格納される。
【００９２】
ノードデータレコード４４１ＣのノードＩＤ４５１Ｃとして、ノード４２０の識別子「４２０」が格納される。ノード４２０には二つのリンクすなわちリンク４２３及び４２４が接続されるため、ノードデータレコード４４１Ｃのリンク数４５３Ｃ、リンクＩＤ４５４Ｃ及びリンクＩＤ４５５Ｃには、それぞれ、「２」、「４２３」及び「４２４」が格納される。
【００９３】
図５に示すリンクテーブル４６０は、リンク４１３、４１４、４２３及び４２４のそれぞれを記述するリンクデータレコード４６１Ｄ、４６１Ｅ、４６１Ｆ及び４６１Ｇを含む。
【００９４】
リンクＩＤ４５４Ｂ及び４５５Ｂの値から、それぞれ、リンクデータレコード４６１Ｄ及び４６１Ｅが参照される。
【００９５】
リンク４１３は、ノード４１１に接続される。このため、リンクデータレコード４６１ＤのリンクＩＤ４７１Ｄ及び接続ノードＩＤ４７５Ｄには、それぞれ、「４１３」及び「４１１」が格納される。同様に、リンク４１４は、ノード４１２に接続される。このため、リンクデータレコード４６１ＥのリンクＩＤ４７１Ｅ及び接続ノードＩＤ４７５Ｅには、それぞれ、「４１４」及び「４１２」が格納される。
【００９６】
一方、リンクＩＤ４５４Ｃ及び４５５Ｃの値から、それぞれ、リンクデータレコード４６１Ｆ及び４６１Ｇが参照される。
【００９７】
リンク４２３は、ノード４２１に接続される。このため、リンクデータレコード４６１ＦのリンクＩＤ４７１Ｆ及び接続ノードＩＤ４７５Ｆには、それぞれ、「４２３」及び「４２１」が格納される。同様に、リンク４２４は、ノード４２２に接続される。このため、リンクデータレコード４６１ＧのリンクＩＤ４７１Ｇ及び接続ノードＩＤ４７５Ｇには、それぞれ、「４２４」及び「４２２」が格納される。
【００９８】
なお、図５では省略されているが、実際には、リンク４１３のノード４１１からノード４１０への方向への通行、リンク４１４のノード４１２からノード４１０への方向への通行、リンク４２３のノード４２１からノード４２０への方向への通行、及び、リンク４２４のノード４２２からノード４２０への方向への通行のそれぞれを記述するリンクデータレコードもリンクテーブル４６０に含まれる。
【００９９】
図６は、本発明の実施形態における更新後の道路ネットワークのデータ構造の説明図である。
【０１００】
具体的には、図６は、図３の新バージョンの地図データ２０２、すなわち、図３に示した全ての更新が終了した後の地図データを記述するノードテーブル４４０及びリンクテーブル４６０を示す。
【０１０１】
図３を参照して説明したように、新バージョンの地図データ２０２においては、ノード４０２、リンク４０１及び４０３が追加され、これによってノード４１０及び４２０に接続されたリンクの数が変更されている。このため、ノードテーブル４４０及びリンクテーブル４６０において、ノード４０２、リンク４０１及び４０３を記述するノードデータレコード４４１Ｆ及びリンクデータレコード４６１Ｈ〜４６１Ｋが追加され、ノード４１０及び４２０のそれぞれを記述するノードデータレコード４４１Ｂ及び４４１Ｃが更新される。図６に示すノードデータレコード４４１Ｄ及び４４１Ｅは、それぞれ、更新されたノードデータレコード４４１Ｂ及び４４１Ｃに相当する。
【０１０２】
まず、更新後のノードテーブル４４０について説明する。
【０１０３】
ノードデータレコード４４１Ｄは、ノードデータレコード４４１Ｂのリンク数４５３Ｂを「２」から「３」に変更し、さらに、新たなリンクＩＤ４５６Ｄを追加することによって生成される。リンクＩＤ４５６Ｄの値は、新たにノード４１０に接続されたリンク４０１の識別子「４０１」である。
【０１０４】
ノードデータレコード４４１Ｅは、ノードデータレコード４４１Ｃのリンク数４５３Ｃを「２」から「３」に変更し、さらに、新たなリンクＩＤ４５６Ｅを追加することによって生成される。リンクＩＤ４５６Ｅの値は、新たにノード４２０に接続されたリンク４０３の識別子「４０３」である。
【０１０５】
ノード４０２を記述するノードデータレコード４４１Ｆは、他のノードデータレコードと同様の項目を含む。これらのうち、ノードＩＤ４５１Ｆの値は、ノード４０２の識別子「４０２」である。リンク数４５３Ｆの値は、ノード４０２に接続されたリンクの数「２」である。リンクＩＤ４５４Ｆ及び４５５Ｆの値は、ノード４０２に接続されたリンク４０３及び４０１の識別子「４０３」及び「４０１」である。
【０１０６】
次に、更新後のリンクテーブル４６０について説明する。
【０１０７】
リンクデータレコード４６１Ｄ〜４６１Ｇは、図５に示したものから変更されていない。一方、リンクデータレコード４６１Ｈ〜４６１Ｋは、新たに追加されたものである。これらのうち、リンクデータレコード４６１Ｈ及び４６１Ｊはリンク４０３を記述するものであり、リンクデータレコード４６１Ｉ及び４６１Ｋはリンク４０１を記述するものである。これらの追加されたリンクデータレコードは、他のリンクデータレコードと同様の項目を含む。
【０１０８】
リンクデータレコード４６１Ｈは、ノードデータレコード４４１ＦのリンクＩＤ４５４Ｆから参照される。リンクＩＤ４７１Ｈの値は、リンク４０３の識別子「４０３」である。接続ノードＩＤ４７５Ｈの値は、リンク４０３に接続されたノード４２０の識別子「４２０」である。すなわち、リンクデータレコード４６１Ｈは、リンク４０３におけるノード４０２からノード４２０への方向の通行を記述するものである。
【０１０９】
リンクデータレコード４６１Ｊは、ノードデータレコード４４１ＥのリンクＩＤ４５６Ｅから参照される。リンクＩＤ４７１Ｊの値は、リンク４０３の識別子「４０３」である。接続ノードＩＤ４７５Ｊの値は、リンク４０３に接続されたノード４０２の識別子「４０２」である。すなわち、リンクデータレコード４６１Ｊは、リンク４０３におけるノード４２０からノード４０２への方向の通行を記述するものである。
【０１１０】
リンクデータレコード４６１Ｉは、ノードデータレコード４４１ＦのリンクＩＤ４５５Ｆから参照される。リンクＩＤ４７１Ｉの値は、リンク４０１の識別子「４０１」である。接続ノードＩＤ４７５Ｉの値は、リンク４０１に接続されたノード４１０の識別子「４１０」である。すなわち、リンクデータレコード４６１Ｉは、リンク４０１におけるノード４０２からノード４１０への方向の通行を記述するものである。
【０１１１】
リンクデータレコード４６１Ｋは、ノードデータレコード４４１ＤのリンクＩＤ４５６Ｄから参照される。リンクＩＤ４７１Ｋの値は、リンク４０１の識別子「４０１」である。接続ノードＩＤ４７５Ｋの値は、リンク４０１に接続されたノード４０２の識別子「４０２」である。すなわち、リンクデータレコード４６１Ｋは、リンク４０１におけるノード４１０からノード４０２への方向の通行を記述するものである。
【０１１２】
ナビゲーション端末２０が保持する地図データが上記のように更新された場合、ナビゲーション処理部２４は、更新された地図データを参照して、経路探索等の処理を実行することができる。
【０１１３】
次に、上記のような更新の一部のみが反映された地図データについて説明する。このような地図データは、例えば、地図配信サーバ１０の地図データ記憶部１９に旧バージョンの地図データ（図５参照）及び新バージョンの地図データ（図６参照）の両方が格納された場合において、前述のライセンス又は更新時間等の制約のためにその更新の一部のみがナビゲーション端末２０の保持する地図データに反映された場合に生成される。
【０１１４】
図７は、本発明の実施形態における一部のみが更新された道路ネットワークのデータ構造の説明図である。
【０１１５】
具体的には、図７は、図３に示す更新のうち、東京都側の更新のみが反映された地図データを示す。具体的には、リンク４０１及びノード４０２が追加され、これによってノード４１０に接続されるリンク数が増加する。一方、リンク４０３は追加されず、したがってノード４２０に接続されるリンク数は増加しない。
【０１１６】
言い換えると、図７に示すノード４１０及びリンク４０１は、図６に示すものと同じである。このため、図７に示すノードテーブル４４０はノードデータレコード４４１Ｄを含み、リンクテーブル４６０はリンクデータレコード４６１Ｉ及び４６１Ｋを含む。一方、図７に示すノード４２０は、図５に示すものと同じである。このため、図７に示すノードテーブル４４０はノードデータレコード４４１Ｃを含む。さらに、図７においてリンク４０３が存在しないという点は、図５と同じである。このため、図７に示すリンクテーブル４６０はリンクデータレコード４６１Ｈ及び４６１Ｊを含まない。
【０１１７】
図６の場合と同様に、図７においてもノード４０２は存在しているが、そこに接続されているリンクの数は図６に示したものと異なる。このため、図７のノードテーブル４４０は、ノードデータレコード４４１Ｆの代わりに、図７のノード４０２を記述するノードデータレコード４４１Ｇを含む。ノードデータレコード４４１ＧのノードＩＤ４５１Ｇの値は、ノード４０２の識別子「４０２」である。ノード４０２にはリンク４０１のみが接続されるため、ノードデータレコード４４１Ｇのリンク数４５３Ｇ及びリンクＩＤ４５４Ｇの値はそれぞれ「１」及び「４０１」である。このリンクＩＤ４５４Ｇからリンクデータレコード４６１Ｉが参照される。
【０１１８】
図８は、本発明の実施形態における別の一部のみが更新された道路ネットワークのデータ構造の説明図である。
【０１１９】
具体的には、図８は、図３に示す更新のうち、千葉県側の更新のみが反映された地図データを示す。具体的には、リンク４０３及びノード４０２が追加され、これによってノード４２０に接続されるリンク数が増加する。一方、リンク４０１は追加されず、したがってノード４１０に接続されるリンク数は増加しない。
【０１２０】
言い換えると、図８に示すノード４２０及びリンク４０３は、図６に示すものと同じである。このため、図８に示すノードテーブル４４０はノードデータレコード４４１Ｅを含み、リンクテーブル４６０はリンクデータレコード４６１Ｈ及びＪを含む。一方、図８に示すノード４１０は、図５に示すものと同じである。このため、図８に示すノードテーブル４４０はノードデータレコード４４１Ｂを含む。さらに、図８においてリンク４０１が存在しないという点は、図５と同じである。このため、図８に示すリンクテーブル４６０はリンクデータレコード４６１Ｉ及び４６１Ｋを含まない。
【０１２１】
図６の場合と同様に、図８においてもノード４０２は存在しているが、そこに接続されているリンクの数は図６に示したものと異なる。このため、図８のノードテーブル４４０は、ノードデータレコード４４１Ｆの代わりに、図８のノード４０２を記述するノードデータレコード４４１Ｈを含む。ノードデータレコード４４１ＨのノードＩＤ４５１Ｈの値は、ノード４０２の識別子「４０２」である。ノード４０２にはリンク４０３のみが接続されるため、ノードデータレコード４４１Ｈのリンク数４５３Ｈ及びリンクＩＤ４５４Ｈの値はそれぞれ「１」及び「４０３」である。このリンクＩＤ４５４Ｈからリンクデータレコード４６１Ｈが参照される。
【０１２２】
図７及び図８のいずれの地図データも、図６に示したような最新の地図データとは相違するが、リンクとノードの接続関係に矛盾はないため、このような地図データを使用しても、経路探索が正常に終了しない等といった問題は発生しない。
【０１２３】
次に、上記のような地図データの更新を行うために地図配信サーバ１０からナビゲーション端末２０に送信される更新エレメントについて説明する。
【０１２４】
図９Ａは、従来の更新エレメントの説明図である。
【０１２５】
具体的には、図９Ａは、図２に示した更新エレメント４３０の説明図であり、図５に示した地図データを図６のように更新するために送信される。
【０１２６】
更新エレメント４３０は、ノードテーブル４４０のノードデータレコード４４１Ｂを４４１Ｄに更新することを指示する情報、ノードデータレコード４４１Ｃを４４１Ｅに更新することを指示する情報、ノードデータレコード４４１Ｆをノードテーブル４４０に追加することを指示する情報、及び、リンクデータレコード４６１Ｈ〜４６１Ｋをリンクテーブル４６０に追加することを指示する情報を含む。
【０１２７】
図５に示す地図データを保持しているナビゲーション端末２０が図９Ａに示す更新エレメント４３０を受信すると、これに基づいて地図更新部２３が更新を実行し、その結果、ナビゲーション端末２０が保持する地図データは図６のように更新される。
【０１２８】
図９Ｂは、本発明の実施形態において使用される更新エレメント及び補正エレメントの説明図である。
【０１２９】
具体的には、図９Ｂは、図３に示した更新エレメント１＿４３１〜更新エレメント３＿４３３及び補正エレメント１＿４３４〜補正エレメント２＿４３５の説明図であり、図５に示した地図データを図６、図７又は図８のように更新するために送信される。
【０１３０】
更新エレメント１＿４３１は、ノードテーブル４４０のノードデータレコード４４１Ｂを４４１Ｄに更新することを指示する情報、及び、リンクデータレコード４６１Ｉをリンクテーブル４６０に追加することを指示する情報を含む。
【０１３１】
更新エレメント３＿４３３は、ノードテーブル４４０のノードデータレコード４４１Ｃを４４１Ｅに更新することを指示する情報、及び、リンクデータレコード４６１Ｈをリンクテーブル４６０に追加することを指示する情報を含む。
【０１３２】
更新エレメント２＿４３２は、ノードデータレコード４４１Ｆをノードテーブル４４０に追加することを指示する情報、及び、リンクデータレコード４６１Ｊ及び４６１Ｋをリンクテーブル４６０に追加することを指示する情報を含む。
【０１３３】
補正エレメント１＿４３４は、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｇに更新することを指示する情報、及び、リンクデータレコード４６１Ｊを削除することを指示する情報を含む。なお、ノードデータレコード４４１Ｇは、ノードデータレコード４４１ＦからリンクＩＤ４５４Ｆを削除し、さらに、リンク数４５３Ｆの値を「２」から「１」に変更したものと同じである。すなわち、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｇに更新することを指示する情報は、ノードデータレコード４４１Ｆのリンク数４５３Ｆの値を「２」から「１」に変更し、さらに、リンクＩＤ４５４Ｆを削除することを指示する情報と等価である。
【０１３４】
補正エレメント２＿４３５は、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｈに更新することを指示する情報、及び、リンクデータレコード４６１Ｋを削除することを指示する情報を含む。なお、ノードデータレコード４４１Ｈは、ノードデータレコード４４１ＦからリンクＩＤ４５５Ｆを削除し、さらに、リンク数４５３Ｆの値を「２」から「１」に変更したものと同じである。すなわち、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｈに更新することを指示する情報は、ノードデータレコード４４１Ｆのリンク数４５３Ｆの値を「２」から「１」に変更し、さらに、リンクＩＤ４５５Ｆを削除することを指示する情報と等価である。
【０１３５】
更新エレメント１＿４３１〜更新エレメント３＿４３３の三つを組み合わせたものは、更新エレメント４３０と等価である。このため、更新エレメント１＿４３１〜更新エレメント３＿４３３に基づいて図５に示す地図データを更新することによって、図６に示す地図データが得られる。
【０１３６】
更新エレメント１＿４３１、更新エレメント２＿４３２及び補正エレメント１＿４３４に基づいて図５に示す地図データを更新することによって、図７に示す地図データが得られる。更新エレメント３＿４３３、更新エレメント２＿４３２及び補正エレメント２＿４３５に基づいて図５に示す地図データを更新することによって、図８に示す地図データが得られる。
【０１３７】
ここで、補正エレメントに基づく更新の必要性を説明する。例として、更新エレメント１＿４３１及び更新エレメント２＿４３２に基づく更新を行い、補正エレメント１＿４３４に基づく更新を行わなかった場合について説明する。
【０１３８】
補正エレメント１＿４３４に基づく更新が行われた場合の更新後の地図データは図７に示した通りである。これに対して、補正エレメント１＿４３４に基づく更新が行われなかった場合、ノードテーブル４４０はノードデータレコード４４１Ｇの代わりにノードデータレコード４４１Ｆを含み、リンクテーブル４６０には、リンクデータレコード４６１Ｊが削除されずに残る。ノードデータレコード４４１ＦはリンクＩＤ４５４Ｆを含むが、リンクＩＤ４５４Ｆから参照されるはずのリンクデータレコード４６１Ｈは、リンクテーブル４６０に格納されていない。このため、ナビゲーション処理部２４が例えば経路探索のためにリンクＩＤ４５４Ｆに基づいてリンクデータレコード４６１Ｈを参照しようとすると、別のデータが誤って参照される。また、リンクデータレコード４６１Ｊはどのノードデータレコードからも参照されないため、記憶領域を有効に利用するためには削除することが望ましい。
【０１３９】
このように、補正エレメント１＿４３４に基づく更新が行われなかった場合、地図データに矛盾が残り、このために経路探索を正常に実行することができなくなる。一方、補正エレメント１＿４３４に基づく更新によって、図７に示すように、参照先のないリンクＩＤがノードデータレコードから削除され、さらに、どこからも参照されないリンクデータレコードも削除される。このため、地図データの矛盾が解消され、これによって経路探索の正常な実行が可能になる。
【０１４０】
上記のような更新エレメント及び補正エレメントは、地図配信サーバ１０が新バージョンの地図データを取得した後、更新データ抽出部１４によって作成され、更新データ記憶部１２に格納される。
【０１４１】
なお、図９Ｂに示した更新エレメント及び補正エレメントは一例であり、実際には種々の変形例が考えられる。
【０１４２】
具体的には、図９Ｂの例は、２種類の更新エレメントを含む。第１の種類の更新エレメントは、一つのパーセルの内側の（すなわちパーセル境界上のノードを除く）ノードの変更を指示する情報、及び、当該パーセルの内側のノードを終点とするリンクの変更を指示する情報を含む。更新エレメント１＿４３１及び更新エレメント３＿４３３がこれに相当する。第２の種類の更新エレメントは、二つのパーセルの境界上のノードの変更を指示する情報、及び、当該ノードを終点とするリンクの変更を指示する情報を含む。更新エレメント２＿４３２がこれに相当する。
【０１４３】
さらに、図９Ｂの例は、上記の第２の種類の更新エレメントの内容を補正するための補正エレメントを含む。すなわち、補正エレメントは、第２の種類の更新エレメントによって変更されたノード及びリンクの少なくとも一方をさらに変更することを指示する情報を含む。補正エレメント１＿４３４及び補正エレメント２＿４３５がこれに相当する。
【０１４４】
一方、第１の変形例は、例えば次の通りである。すなわち、第１の変形例は、２種類の更新エレメントを含む。第１の種類の更新エレメントは、一つのパーセルの内側の（すなわちパーセル境界上のノードを除く）ノードの変更を指示する情報、及び、当該パーセルの内側のノードを始点とするリンクの変更を指示する情報を含む。第２の種類の更新エレメントは、二つのパーセルの境界上のノードの変更を指示する情報、及び、当該ノードを始点とするリンクの変更を指示する情報を含む。さらに、第１の変形例は、上記の第２の種類の更新エレメントの内容を補正するための補正エレメントを含む。すなわち、第１の変形例の補正エレメントは、第２の種類の更新エレメントによって変更されたノード及びリンクの少なくとも一方をさらに変更することを指示する情報を含む。
【０１４５】
第２の変形例は、例えば次の通りである。すなわち、第２の変形例は、３種類の更新エレメントを含む。第１の種類の更新エレメントは、一つのパーセルの内側の（すなわちパーセル境界上のノードを除く）ノードの変更を指示する情報を含む。例えば、図９Ｂに示す情報のうち、ノードデータレコード４４１Ｂをノードデータレコード４４１Ｄに更新することを指示する情報がこれに相当する。
【０１４６】
第２の種類の更新エレメントは、二つのパーセルの境界上のノードの変更を指示する情報を含む。例えば、図９Ｂに示す情報のうち、リンクデータレコード４６１Ｉ及び４６１Ｋを追加することを指示する情報がこれに相当する。第３の種類の更新エレメントは、一つのパーセルの内側のリンクの変更を指示する情報を含む。例えば、図９Ｂに示す情報のうち、ノードデータレコード４４１Ｆを追加することを指示する情報がこれに相当する。
【０１４７】
さらに、第２の変形例は、上記の第２の種類の更新エレメントの内容を補正するための補正エレメントを含む。すなわち、第２の変形例の補正エレメントは、第２の種類の更新エレメントによって変更されたノードをさらに変更することを指示する情報を含む。例えば、図９Ｂに示す情報のうち、ノードデータレコード４４１Ｆをノードデータレコード４４１Ｇに更新することを指示する情報がこれに相当する。
【０１４８】
次に、地図配信サーバ１０の管理データ記憶部１１に格納される情報について説明する。
【０１４９】
図１０は、本発明の実施形態の管理データ記憶部１１に格納される更新権利管理テーブル１０００の説明図である。
【０１５０】
更新権利管理テーブル１０００は、各ナビゲーション端末２０が有する地図データの更新権利を示す情報を保持する。具体的には、更新権利管理テーブル１０００は、端末ＩＤ１００１及び都道府県コード１００２を含む。
【０１５１】
端末ＩＤ１００１は、各ナビゲーション端末２０の識別子である。
【０１５２】
都道府県コード１００２は、各都道府県を識別するコードである。図１０の例では日本工業規格Ｘ０４０１によって規定された都道府県コードが使用されるが、その他の識別子が使用されてもよい。
【０１５３】
例えば、端末ＩＤ「１０」によって識別されるナビゲーション端末２０のユーザが、東京都の地図データを更新する権利（ライセンス）を購入した場合、そのナビゲーション端末２０は東京都の地図データを更新する権利を有するため、端末ＩＤ１００１の値「１０」に対応する都道府県コード１００２として、東京都を識別するコード「１３」が格納される。同様に、例えば、千葉県の地図データを更新する権利を有するナビゲーション端末２０に対応する都道府県コード１００２として千葉県を識別するコード「１２」が、東京都と千葉県の両方の地図データを更新する権利を有するナビゲーション端末２０に対応する都道府県コード１００２としてコード「１２」及び「１３」が格納される。
【０１５４】
なお、地図データを更新する権利が都道府県以外の領域（例えば国）ごとに管理される場合には、更新権利管理テーブル１０００に都道府県コードの代わりにその領域を識別するコードが格納される。他のテーブルについても同様である（図１１及び図１２参照）。
【０１５５】
図１１は、本発明の実施形態の管理データ記憶部１１に格納される更新エレメント管理テーブル１１００の説明図である。
【０１５６】
更新エレメント管理テーブル１１００は、各領域（例えば都道府県）に属するパーセルの地図データを更新するために使用される更新エレメントを特定する情報を含む。具体的には、更新エレメント管理テーブル１１００は、更新エレメントＩＤ１１０１及び都道府県コード１１０２を含む。
【０１５７】
更新エレメントＩＤ１１０１は、各更新エレメントの識別子である。図９Ｂに示す更新エレメント１＿４３１、更新エレメント２＿４３２及び更新エレメント３＿４３３の識別子は、それぞれ、「１」、「２」及び「３」である。
【０１５８】
都道府県コード１１０２は、図１０の都道府県コード１００２と同様、各都道府県を識別するコードである。
【０１５９】
図１１の例では、更新エレメントＩＤ１１０１の値「１」に対応する都道府県コード１１０２として「１３」が格納されている。これは、更新エレメント１＿４３１が東京都に属するパーセルの地図データを更新するために使用されること、言い換えると、東京都に属するパーセル内のノード及びリンクの更新を指示する情報を含むことを意味する。
【０１６０】
一方、図１１において、更新エレメントＩＤ１１０１の値「２」に対応する都道府県コード１１０２として「１２」及び「１３」が格納されている。これは、更新エレメント２＿４３２が、東京都に属するパーセルの地図データ及び千葉県に属するパーセルの地図データのいずれを更新するためにも使用されること、言い換えると、東京都に属するパーセルと千葉県に属するパーセルとの境界上のノードの更新を指示する情報を含むことを意味する。
【０１６１】
図１２は、本発明の実施形態の管理データ記憶部１１に格納される補正エレメント管理テーブル１２００の説明図である。
【０１６２】
補正エレメント管理テーブル１２００は、各領域（例えば都道府県）の境界における更新エレメントの補正に使用される補正エレメントを特定する情報を含む。具体的には、補正エレメント管理テーブル１２００は、補正エレメントＩＤ１２０１、都道府県コード１２０２及び接続先都道府県コード１２０３を含む。
【０１６３】
補正エレメントＩＤ１２０１は、各補正エレメントの識別子である。図９Ｂに示す補正エレメント１＿４３４及び補正エレメント２＿４３５の識別子は、それぞれ、「１」及び「２」である。
【０１６４】
都道府県コード１２０２及び接続先都道府県コード１２０３は、いずれも、図１０の都道府県コード１００２と同様、各都道府県を識別するコードである。都道府県コード１２０２によって識別される領域と、接続先都道府県コード１２０３によって識別される領域との境界を跨る連続したリンク及びノードのうち、都道府県コード１２０２によって識別される領域側のリンク及びノードのみを更新する場合に、補正エレメントＩＤ１２０１によって識別される補正エレメントに基づいて、当該境界に対応する更新エレメントが補正される。
【０１６５】
図１２の例では、補正エレメントＩＤ１２０１の値「１」に対応する都道府県コード１２０２及び接続先都道府県コード１２０３としてそれぞれ「１３」及び「１２」が格納されている。これは、東京都と千葉県との境界を跨る連続したリンク及びノードのうち、東京都に属するパーセル内のリンク及びノードのみを更新する場合に、補正エレメント１＿４３４に基づいて更新エレメント２＿４３２が補正されることを意味する。
【０１６６】
一方、補正エレメントＩＤ１２０１の値「２」に対応する都道府県コード１２０２及び接続先都道府県コード１２０３としてそれぞれ「１２」及び「１３」が格納されている。これは、東京都と千葉県との境界を跨る連続したリンク及びノードのうち、千葉県に属するパーセル内のリンク及びノードのみを更新する場合に、補正エレメント２＿４３５に基づいて更新エレメント２＿４３２が補正されることを意味する。
【０１６７】
次に、地図配信サーバ１０及びナビゲーション端末２０が地図データを更新するために実行する処理について説明する。
【０１６８】
図１３は、本発明の実施形態のナビゲーション端末２０が保持する地図データを更新するために実行される処理を示すフローチャートである。
【０１６９】
最初に、ナビゲーション端末２０が、これから地図データを更新しようとする領域（すなわち更新対象の領域）の識別コード（例えば都道府県コード）と、自身を識別する端末ＩＤと、を含む地図データ配信要求を地図配信サーバ１０に送信する（ステップ１３０１）。複数の領域の地図データを更新したい場合には、それらの複数の領域の識別コードが地図データ配信要求に含まれる。なお、更新対象の領域は、任意の方法によって決定される。例えば、ナビゲーション端末２０のユーザによって決定されてもよいし、所定のアルゴリズムに基づいて自動的に決定されてもよい。
【０１７０】
地図配信サーバ１０は、ステップ１３０１において送信された地図データ配信要求を受信すると、当該要求に含まれる端末ＩＤと、更新対象の領域の識別コードとに基づいて、ナビゲーション端末２０が有している権利を確認し（ステップ１３０２）、当該要求を送信したナビゲーション端末２０が、更新対象の領域の少なくとも一つに関して、更新の権利を有しているか否かを判定する（ステップ１３０３）。地図配信サーバ１０は、この確認及び判定のために、更新権利管理テーブル１０００を参照する。
【０１７１】
ステップ１３０３において、地図データ配信要求を送信したナビゲーション端末２０が、更新対象のいずれの領域についても更新の権利を有していないと判定された場合、更新を実行することができないため、地図配信サーバ１０は、更新不可を示す通知をナビゲーション端末２０に送信する（ステップ１３０４）。この通知を受信したナビゲーション端末２０は、更新対象の領域について更新権利を有していないことを示す情報を、画面入出力Ｉ／Ｆ２５を介して出力してもよい。
【０１７２】
一方、ステップ１３０３において、地図データ配信要求を送信したナビゲーション端末２０が、更新対象である少なくとも一つの領域において更新の権利を有していると判定された場合、地図配信サーバ１０は、更新エレメント管理テーブル１１００を参照して、配信対象の領域に対応する更新エレメントを収集する（ステップ１３０５）。ここで、配信対象の領域とは、ナビゲーション端末２０によって更新対象として指定された領域のうち、当該ナビゲーション端末２０が更新の権利を有している領域である。
【０１７３】
次に、地図配信サーバ１０は、補正エレメント管理テーブル１２００を参照して、都道府県コード１２０２の値がいずれかの配信対象領域の識別コードであり、かつ、接続先都道府県コード１２０３の値がいずれの配信対象領域の識別コードとも異なるレコードの補正エレメントＩＤ１２０１の値を取得し、その値に対応する補正エレメントを収集する（ステップ１３０６）。
【０１７４】
次に、地図配信サーバ１０は、ステップ１３０５及び１３０６において収集された更新エレメント及び補正エレメントをナビゲーション端末２０に送信する（ステップ１３０７）。
【０１７５】
ナビゲーション端末２０は、更新エレメント及び補正エレメントを地図配信サーバ１０から受信すると、それらに従って地図データ記憶部２７に格納されている地図データを更新する（ステップ１３０８）。
【０１７６】
上記のように、地図配信サーバ１０は、ナビゲーション端末２０から更新対象として指定された領域のうち、配信対象の領域（すなわち当該ナビゲーション端末２０が更新の権利を有している領域）のみを更新するための更新エレメント及び補正エレメントをステップ１３０８において送信する。更新対象として指定された複数の領域の一部が配信対象とならなかった場合、地図配信サーバ１０は、当該配信対象でない領域について、更新権利の欠如を示す情報をステップ１３０８においてナビゲーション端末２０に送信してもよい。この情報を受信したナビゲーション端末２０は、更新対象の領域について更新権利を有していないことを示す情報を、画面入出力Ｉ／Ｆ２５を介して出力してもよい。
【０１７７】
なお、上記の処理のうち、ステップ１３０１及び１３０８は、例えば、ナビゲーション端末２０の配信要求部２２及び地図更新部２３によってそれぞれ実行され、ステップ１３０２〜１３０７は、例えば、地図配信サーバ１０の更新データ管理部１５によって実行される。
【０１７８】
ここで、図３及び図５〜図１２を参照して、図１３の処理の具体例を説明する。
【０１７９】
図３に示す旧バージョンの地図データ２０１及び新バージョンの地図データ２０２が地図配信サーバ１０の地図データ記憶部１９に格納され、ナビゲーション端末２０の地図データ記憶部２７には旧バージョンの地図データ２０１のみが格納されている時点において、ナビゲーション端末２０が東京都及び千葉県の両方を更新対象として指定する情報、及び、自身の識別子「１０」を含む地図データ配信要求を地図配信サーバ１０に送信した（ステップ１３０１）場合を例として説明する。
【０１８０】
更新権利管理テーブル１０００には、端末ＩＤ「１０」に対応する都道府県コード１００２として、東京都を識別する「１３」のみが格納されているため、要求元のナビゲーション端末２０は、東京都の地図データを更新する権利は有しているが、千葉県の地図データを更新する権利は有していない（ステップ１３０２、１３０３）。
【０１８１】
この場合、配信対象領域は東京都であるため、地図配信サーバ１０は、更新エレメント管理テーブル１１００を参照して、東京都に対応する更新エレメント１＿４３１及び更新エレメント２＿４３２を選択する（ステップ１３０５）。さらに、地図配信サーバ１０は、補正エレメント管理テーブル１２００を参照して、都道府県コード１２０２が配信対象である東京都を示し、かつ、接続先都道府県コード１２０３が配信対象でない（図１２の例では「千葉県」である）レコードに対応する補正エレメント１＿４３４を選択する（ステップ１３０６）。
【０１８２】
そして、地図配信サーバ１０は、選択された更新エレメント１＿４３１、更新エレメント２＿４３２及び補正エレメント１＿４３４をナビゲーション端末２０に送信する（ステップ１３０７）。
【０１８３】
ナビゲーション端末２０は、例えば、まず受信した更新エレメント１＿４３１及び更新エレメント２＿４３２に基づいて地図データを更新し、次に補正エレメント１＿４３４に基づいて地図データを更新する（ステップ１３０８）。あるいは、ナビゲーション端末２０は、受信した補正エレメント１＿４３４に基づいて更新エレメント２＿４３２を補正し、受信した更新エレメント１＿４３１及び補正された更新エレメント２＿４３２に基づいて地図データを更新してもよい。これによって、図７に示すような更新後の地図データが地図データ記憶部２７に格納される。
【０１８４】
なお、ステップ１３０８において更新エレメント１＿４３１及び更新エレメント２＿４３２に基づく更新が開始されてから、補正エレメント１＿４３４に基づく更新が終了するまでの間、地図データ記憶部２７内の地図データに一時的に矛盾が発生し得る。このため、ナビゲーション端末２０は、受信した更新エレメント及び補正エレメントに基づく更新が開始されてから終了するまでの間、経路探索等の地図データを参照する処理を実行しないようにナビゲーション処理部２４等を制御する必要がある。
【０１８５】
一方、上記の具体例において、地図データ配信要求を送信したナビゲーション端末２０の識別子が「１２」であった場合、このナビゲーション端末２０は東京都及び千葉県の両方の地図データを更新する権利を有している（ステップ１３０２、１３０３）。このため、ステップ１３０５では更新エレメント１＿４３１、更新エレメント２＿４３２及び更新エレメント３＿４３３が選択される。一方、東京都及び千葉県のいずれも配信対象領域であるため、ステップ１３０６では、いずれの補正エレメントも選択されない。このため、ステップ１３０５で選択された三つの更新エレメントがナビゲーション端末２０に送信され（ステップ１３０７）、補正エレメントは送信されない。送信された更新エレメントに基づいて、ナビゲーション端末２０の地図データが図６に示すように更新される（ステップ１３０８）。
【０１８６】
以上のように、本発明の実施形態によれば、任意の範囲の地図データを矛盾なく更新することができる。
【０１８７】
以上の本発明の実施形態は、地図データの更新範囲が更新権利（ライセンス）の有無によって制限される場合を例として説明したが、本発明は、更新権利以外の要因によって更新範囲が制限される場合にも適用することができる。例えば、所定の時間内に更新を終了させたい場合がある。従来の方法によって作成された更新エレメント（例えば図９Ａ参照）に基づく更新が当該所定の時間内に終了しないと予測される場合には、その更新エレメントを分割してもよい。この分割は、図９Ｂを参照して説明した方法によって実行することができる。
【０１８８】
より詳細には、上記のような更新エレメントの分割は、図２〜図１３において説明したように都道府県等の領域ごとに行われてもよいが、その他の領域、例えばパーセルごとに行われてもよい。パーセルごとに分割される場合、図１０〜図１２において、都道府県コードの代わりにパーセルの識別子が使用される。更新権利管理テーブル１０００は省略されてもよい。この例において、図１３のステップ１３０１の地図データ配信要求は、都道府県コードの代わりに更新対象のパーセルの識別子を含んでもよい。この場合、ステップ１３０２及び１３０３は省略され、ステップ１３０５以降において、更新対象のパーセルが配信対象の領域として扱われる。
【０１８９】
このようにして分割された更新エレメント及び作成された補正エレメントに基づく更新を実行することによって、任意の範囲の地図データを矛盾なく更新することができる。
【符号の説明】
【０１９０】
１０ 地図配信サーバ
１１、２６ 管理データ記憶部
１２ 更新データ記憶部
１３ 更新時間予測処理部
１４ 更新データ抽出部
１５ 更新データ管理部
１６、２８ プロセッサ
１７、２９ メモリ
１８、２１ ネットワークインターフェース（Ｉ／Ｆ）
１９、２７ 地図データ記憶部
２０ ナビゲーション端末
２２ 配信要求部
２３ 地図更新部
２４ ナビゲーション処理部
２５ 画面入出力Ｉ／Ｆ
３０ 無線通信装置
３１ 無線基地局
４０ ネットワーク
４１ インターネット
【特許請求の範囲】
【請求項１】
ネットワークに接続され、前記ネットワークを介して地図データを配信する地図データ配信サーバであって、
前記地図データ配信サーバは、
前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、
地図上の空間を分割することによって定義された複数の領域に対応する第１の地図データと、前記複数の領域に対応する、前記第１の地図データより新しいバージョンの第２の地図データと、を保持し、
前記第１の地図データ及び第２の地図データは、道路上の地点に対応するノード及び前記地点を結ぶ道路上の区間に対応するリンクを示す情報を含み、
前記複数の領域は、第１領域及び前記第１領域に隣接する第２領域を含み、
前記地図データ配信サーバは、
前記第１の地図データを前記第２の地図データに更新するための差分データとして、前記第１領域内のノード及びリンクの変更を指示する第１情報、前記第２領域内のノード及びリンクの変更を指示する第２情報、前記第１領域と前記第２領域との境界上のノードの変更を指示する第３情報、及び、前記第３情報に基づいて変更された境界上のノードのさらなる変更を指示する第４情報を保持し、
前記第１領域を含む一つ以上の領域の地図データを更新するための地図データ配信要求を、前記ネットワークを介して受信すると、前記第１情報、前記第２情報及び前記第３情報の組、又は、前記第１情報、前記第３情報及び前記第４情報の組のいずれかを、前記ネットワークを介して送信することを特徴とする地図データ配信サーバ。
【請求項２】
前記第３情報は、前記境界上のノードに接続される前記第１領域内のリンクを示す情報の参照先を示す情報、及び、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の参照先を示す情報の両方の追加を指示する情報を含み、
前記第４情報は、前記第３情報によって追加することを指示された情報のうち、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の参照先を示す情報を削除することを指示する情報を含むことを特徴とする請求項１に記載の地図データ配信サーバ。
【請求項３】
前記ネットワークには、複数の端末装置が接続され、
前記地図データ配信要求は、当該地図データ配信要求を送信した前記端末装置の識別子を含み、
前記地図データ配信サーバは、
前記各端末装置が前記各領域の地図データを更新する権利を有するか否かを示す更新権利情報を保持し、
前記更新権利情報及び受信した前記地図データ配信要求に含まれる識別子に基づいて、当該地図データ配信要求を送信した端末装置が前記各領域の地図データを更新する権利を有するか否かを判定し、
当該地図データ配信要求を送信した端末装置が前記第１領域及び前記第２領域の地図データを更新する権利を有する場合、前記第１情報、前記第２情報及び前記第３情報の組を、当該地図データ配信要求を送信した端末装置に送信し、
当該地図データ配信要求を送信した端末装置が前記第１領域の地図データを更新する権利を有するが前記第２領域の地図データを更新する権利を有しない場合、前記第１情報、前記第３情報及び前記第４情報の組を、当該地図データ配信要求を送信した端末装置に送信することを特徴とする請求項２に記載の地図データ配信サーバ。
【請求項４】
前記ネットワークには、前記地図データ配信要求を送信する端末装置が接続され、
前記地図データ配信サーバは、
前記地図データ配信要求による更新対象として前記第１領域及び前記第２領域が指定された場合、前記第１情報、前記第２情報及び前記第３情報の組を前記端末装置に送信し、
前記地図データ配信要求による更新対象として前記第１領域が指定されており、前記第２領域が指定されていない場合、前記第１情報、前記第３情報及び前記第４情報の組を前記端末装置に送信することを特徴とする請求項２に記載の地図データ配信サーバ。
【請求項５】
前記第３情報は、前記境界上のノードに接続される前記第１領域内のリンクを示す情報の追加を指示する情報、及び、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の追加を指示する情報をさらに含み、
前記第４情報は、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の削除を指示する情報をさらに含むことを特徴とする請求項２に記載の地図データ配信サーバ。
【請求項６】
ネットワークに接続された地図データ配信サーバが前記ネットワークを介して地図データを配信する方法であって、
前記地図データ配信サーバは、
前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、
地図上の空間を分割することによって定義された複数の領域に対応する第１の地図データと、前記複数の領域に対応する、前記第１の地図データより新しいバージョンの第２の地図データと、を保持し、
前記第１の地図データ及び第２の地図データは、道路上の地点に対応するノード及び前記地点を結ぶ道路上の区間に対応するリンクを示す情報を含み、
前記複数の領域は、第１領域及び前記第１領域に隣接する第２領域を含み、
前記地図データ配信サーバは、さらに、前記第１の地図データを前記第２の地図データに更新するための差分データとして、前記第１領域内のノード及びリンクの変更を指示する第１情報、前記第２領域内のノード及びリンクの変更を指示する第２情報、前記第１領域と前記第２領域との境界上のノードの変更を指示する第３情報、及び、前記第３情報に基づいて変更された境界上のノードのさらなる変更を指示する第４情報を保持し、
前記地図データ配信方法は、
前記地図データ配信サーバが、前記第１領域を含む一つ以上の領域の地図データを更新するための地図データ配信要求を、前記ネットワークを介して受信する第１手順と、
前記地図データ配信サーバが、前記第１情報、前記第２情報及び前記第３情報の組、又は、前記第１情報、前記第３情報及び前記第４情報の組のいずれかを、前記ネットワークを介して送信する第２手順と、を含むことを特徴とする地図データ配信方法。
【請求項７】
前記第３情報は、前記境界上のノードに接続される前記第１領域内のリンクを示す情報の参照先を示す情報、及び、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の参照先を示す情報の両方の追加を指示する情報を含み、
前記第４情報は、前記第３情報によって追加することを指示された情報のうち、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の参照先を示す情報を削除することを指示する情報を含むことを特徴とする請求項６に記載の地図データ配信方法。
【請求項８】
前記ネットワークには、複数の端末装置が接続され、
前記地図データ配信要求は、当該地図データ配信要求を送信した前記端末装置の識別子を含み、
前記地図データ配信サーバは、前記各端末装置が前記各領域の地図データを更新する権利を有するか否かを示す更新権利情報を保持し、
前記地図データ配信方法は、さらに、前記地図データ配信サーバが、前記更新権利情報及び受信した前記地図データ配信要求に含まれる識別子に基づいて、当該地図データ配信要求を送信した端末装置が前記各領域の地図データを更新する権利を有するか否かを判定する手順を含み、
当該地図データ配信要求を送信した端末装置が前記第１領域及び前記第２領域の地図データを更新する権利を有する場合、前記第２手順において、前記地図データ配信サーバは、前記第１情報、前記第２情報及び前記第３情報の組を、当該地図データ配信要求を送信した端末装置に送信し、
当該地図データ配信要求を送信した端末装置が前記第１領域の地図データを更新する権利を有するが前記第２領域の地図データを更新する権利を有しない場合、前記第２手順において、前記地図データ配信サーバは、前記第１情報、前記第３情報及び前記第４情報の組を、当該地図データ配信要求を送信した端末装置に送信することを特徴とする請求項７に記載の地図データ配信方法。
【請求項９】
前記ネットワークには、前記地図データ配信要求を送信する端末装置が接続され、
前記地図データ配信要求による更新対象として前記第１領域及び前記第２領域が指定された場合、前記第２手順において、前記地図データ配信サーバは、前記第１情報、前記第２情報及び前記第３情報の組を前記端末装置に送信し、
前記地図データ配信要求による更新対象として前記第１領域が指定されており、前記第２領域が指定されていない場合、前記第２手順において、前記地図データ配信サーバは、前記第１情報、前記第３情報及び前記第４情報の組を前記端末装置に送信することを特徴とする請求項７に記載の地図データ配信方法。
【請求項１０】
前記第３情報は、前記境界上のノードに接続される前記第１領域内のリンクを示す情報の追加を指示する情報、及び、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の追加を指示する情報をさらに含み、
前記第４情報は、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の削除を指示する情報をさらに含むことを特徴とする請求項７に記載の地図データ配信方法。
【請求項１】
ネットワークに接続され、前記ネットワークを介して地図データを配信する地図データ配信サーバであって、
前記地図データ配信サーバは、
前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、
地図上の空間を分割することによって定義された複数の領域に対応する第１の地図データと、前記複数の領域に対応する、前記第１の地図データより新しいバージョンの第２の地図データと、を保持し、
前記第１の地図データ及び第２の地図データは、道路上の地点に対応するノード及び前記地点を結ぶ道路上の区間に対応するリンクを示す情報を含み、
前記複数の領域は、第１領域及び前記第１領域に隣接する第２領域を含み、
前記地図データ配信サーバは、
前記第１の地図データを前記第２の地図データに更新するための差分データとして、前記第１領域内のノード及びリンクの変更を指示する第１情報、前記第２領域内のノード及びリンクの変更を指示する第２情報、前記第１領域と前記第２領域との境界上のノードの変更を指示する第３情報、及び、前記第３情報に基づいて変更された境界上のノードのさらなる変更を指示する第４情報を保持し、
前記第１領域を含む一つ以上の領域の地図データを更新するための地図データ配信要求を、前記ネットワークを介して受信すると、前記第１情報、前記第２情報及び前記第３情報の組、又は、前記第１情報、前記第３情報及び前記第４情報の組のいずれかを、前記ネットワークを介して送信することを特徴とする地図データ配信サーバ。
【請求項２】
前記第３情報は、前記境界上のノードに接続される前記第１領域内のリンクを示す情報の参照先を示す情報、及び、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の参照先を示す情報の両方の追加を指示する情報を含み、
前記第４情報は、前記第３情報によって追加することを指示された情報のうち、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の参照先を示す情報を削除することを指示する情報を含むことを特徴とする請求項１に記載の地図データ配信サーバ。
【請求項３】
前記ネットワークには、複数の端末装置が接続され、
前記地図データ配信要求は、当該地図データ配信要求を送信した前記端末装置の識別子を含み、
前記地図データ配信サーバは、
前記各端末装置が前記各領域の地図データを更新する権利を有するか否かを示す更新権利情報を保持し、
前記更新権利情報及び受信した前記地図データ配信要求に含まれる識別子に基づいて、当該地図データ配信要求を送信した端末装置が前記各領域の地図データを更新する権利を有するか否かを判定し、
当該地図データ配信要求を送信した端末装置が前記第１領域及び前記第２領域の地図データを更新する権利を有する場合、前記第１情報、前記第２情報及び前記第３情報の組を、当該地図データ配信要求を送信した端末装置に送信し、
当該地図データ配信要求を送信した端末装置が前記第１領域の地図データを更新する権利を有するが前記第２領域の地図データを更新する権利を有しない場合、前記第１情報、前記第３情報及び前記第４情報の組を、当該地図データ配信要求を送信した端末装置に送信することを特徴とする請求項２に記載の地図データ配信サーバ。
【請求項４】
前記ネットワークには、前記地図データ配信要求を送信する端末装置が接続され、
前記地図データ配信サーバは、
前記地図データ配信要求による更新対象として前記第１領域及び前記第２領域が指定された場合、前記第１情報、前記第２情報及び前記第３情報の組を前記端末装置に送信し、
前記地図データ配信要求による更新対象として前記第１領域が指定されており、前記第２領域が指定されていない場合、前記第１情報、前記第３情報及び前記第４情報の組を前記端末装置に送信することを特徴とする請求項２に記載の地図データ配信サーバ。
【請求項５】
前記第３情報は、前記境界上のノードに接続される前記第１領域内のリンクを示す情報の追加を指示する情報、及び、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の追加を指示する情報をさらに含み、
前記第４情報は、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の削除を指示する情報をさらに含むことを特徴とする請求項２に記載の地図データ配信サーバ。
【請求項６】
ネットワークに接続された地図データ配信サーバが前記ネットワークを介して地図データを配信する方法であって、
前記地図データ配信サーバは、
前記ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、
地図上の空間を分割することによって定義された複数の領域に対応する第１の地図データと、前記複数の領域に対応する、前記第１の地図データより新しいバージョンの第２の地図データと、を保持し、
前記第１の地図データ及び第２の地図データは、道路上の地点に対応するノード及び前記地点を結ぶ道路上の区間に対応するリンクを示す情報を含み、
前記複数の領域は、第１領域及び前記第１領域に隣接する第２領域を含み、
前記地図データ配信サーバは、さらに、前記第１の地図データを前記第２の地図データに更新するための差分データとして、前記第１領域内のノード及びリンクの変更を指示する第１情報、前記第２領域内のノード及びリンクの変更を指示する第２情報、前記第１領域と前記第２領域との境界上のノードの変更を指示する第３情報、及び、前記第３情報に基づいて変更された境界上のノードのさらなる変更を指示する第４情報を保持し、
前記地図データ配信方法は、
前記地図データ配信サーバが、前記第１領域を含む一つ以上の領域の地図データを更新するための地図データ配信要求を、前記ネットワークを介して受信する第１手順と、
前記地図データ配信サーバが、前記第１情報、前記第２情報及び前記第３情報の組、又は、前記第１情報、前記第３情報及び前記第４情報の組のいずれかを、前記ネットワークを介して送信する第２手順と、を含むことを特徴とする地図データ配信方法。
【請求項７】
前記第３情報は、前記境界上のノードに接続される前記第１領域内のリンクを示す情報の参照先を示す情報、及び、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の参照先を示す情報の両方の追加を指示する情報を含み、
前記第４情報は、前記第３情報によって追加することを指示された情報のうち、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の参照先を示す情報を削除することを指示する情報を含むことを特徴とする請求項６に記載の地図データ配信方法。
【請求項８】
前記ネットワークには、複数の端末装置が接続され、
前記地図データ配信要求は、当該地図データ配信要求を送信した前記端末装置の識別子を含み、
前記地図データ配信サーバは、前記各端末装置が前記各領域の地図データを更新する権利を有するか否かを示す更新権利情報を保持し、
前記地図データ配信方法は、さらに、前記地図データ配信サーバが、前記更新権利情報及び受信した前記地図データ配信要求に含まれる識別子に基づいて、当該地図データ配信要求を送信した端末装置が前記各領域の地図データを更新する権利を有するか否かを判定する手順を含み、
当該地図データ配信要求を送信した端末装置が前記第１領域及び前記第２領域の地図データを更新する権利を有する場合、前記第２手順において、前記地図データ配信サーバは、前記第１情報、前記第２情報及び前記第３情報の組を、当該地図データ配信要求を送信した端末装置に送信し、
当該地図データ配信要求を送信した端末装置が前記第１領域の地図データを更新する権利を有するが前記第２領域の地図データを更新する権利を有しない場合、前記第２手順において、前記地図データ配信サーバは、前記第１情報、前記第３情報及び前記第４情報の組を、当該地図データ配信要求を送信した端末装置に送信することを特徴とする請求項７に記載の地図データ配信方法。
【請求項９】
前記ネットワークには、前記地図データ配信要求を送信する端末装置が接続され、
前記地図データ配信要求による更新対象として前記第１領域及び前記第２領域が指定された場合、前記第２手順において、前記地図データ配信サーバは、前記第１情報、前記第２情報及び前記第３情報の組を前記端末装置に送信し、
前記地図データ配信要求による更新対象として前記第１領域が指定されており、前記第２領域が指定されていない場合、前記第２手順において、前記地図データ配信サーバは、前記第１情報、前記第３情報及び前記第４情報の組を前記端末装置に送信することを特徴とする請求項７に記載の地図データ配信方法。
【請求項１０】
前記第３情報は、前記境界上のノードに接続される前記第１領域内のリンクを示す情報の追加を指示する情報、及び、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の追加を指示する情報をさらに含み、
前記第４情報は、前記境界上のノードに接続される前記第２領域内のリンクを示す情報の削除を指示する情報をさらに含むことを特徴とする請求項７に記載の地図データ配信方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１２−１５５２８６（Ｐ２０１２−１５５２８６Ａ）
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願番号】特願２０１１−１６７６９（Ｐ２０１１−１６７６９）
【出願日】平成２３年１月２８日（２０１１．１．２８）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【Ｆターム（参考）】
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願日】平成２３年１月２８日（２０１１．１．２８）
【出願人】（５０９１８６５７９）日立オートモティブシステムズ株式会社 (2,205)
【Ｆターム（参考）】
[ Back to top ]