(57)【特許請求の範囲】
【請求項１】
ネットワークに接続される地図データ配信サーバと、前記ネットワークを介して前記地図データ配信サーバと通信する端末装置と、を備える地図データ配信システムであって、
前記地図データ配信サーバは、
前記ネットワークに接続される第１インターフェースと、前記第１インターフェースに接続される第１プロセッサと、前記第１プロセッサに接続される第１記憶装置と、を備え、
地図上の空間を分割することによって定義された複数の矩形領域に対応する第１の地図データと、前記複数の矩形領域に対応する、前記第１の地図データより新しいバージョンの第２の地図データと、前記端末装置の機種と所定の係数とを対応付ける情報と、を保持し、
前記第１の地図データ及び第２の地図データは、地図上の交差点に対応するノード及び前記交差点を結ぶ道路に対応するリンクを示す情報を含み、
前記端末装置は、
前記地図データ配信サーバと通信する第２インターフェースと、前記第２インターフェースに接続される第２プロセッサと、前記第２プロセッサに接続される第２記憶装置と、を備え、
前記複数の矩形領域に対応する前記第１の地図データを保持し、
前記地図データ配信サーバは、
前記第１の地図データを前記第２の地図データに更新するための差分データとして、各々が単一の又は複数の前記矩形領域に属する単一の又は連続する複数の前記リンクの追加、削除又は変更を示すデータを含む、複数の更新エレメントを作成し、
前記各更新エレメントに含まれるデータの量、及び前記各更新エレメントによって更新される前記矩形領域の数の双方に基づいて、前記各更新エレメントに含まれる前記差分データの量が多いほど長く、かつ、前記各更新エレメントによって更新される前記矩形領域の数が多いほど長くなるように、前記各更新エレメントに基づく前記第１の地図データの更新に要する時間を算出し、
前記端末装置は、前記第１の地図データの更新対象の矩形領域を指定する情報と、前記端末装置の機種を示す情報と、更新時間を指定する情報と、を含む地図データ配信要求を前記地図データ配信サーバに送信し、
前記地図データ配信サーバは、
前記更新対象の矩形領域を更新する各更新エレメントについての前記算出された更新に要する時間に対して、送信された前記端末装置の機種を示す情報に基づいて特定した前記端末装置の機種に対応した係数を乗じることによって、前記端末装置による前記各更新エレメントに基づく前記第１の地図データの更新に要する時間を算出し、
前記更新対象の矩形領域を更新する前記更新エレメントから、前記算出された前記端末装置による更新に要する時間の合計値が前記指定された更新時間を超えないように一つ以上の前記更新エレメントを選択し、
前記選択された一つ以上の更新エレメントを前記端末装置に送信し、
前記端末装置は、前記送信された更新エレメントに基づいて前記第１の地図データを更新することを特徴とする地図データ配信システム。
【請求項２】
地図データ配信サーバが実行する地図データ配信方法であって、
前記地図データ配信サーバは、
ネットワークに接続されるインターフェースと、前記インターフェースに接続されるプロセッサと、前記プロセッサに接続される記憶装置と、を備え、
地図上の空間を分割することによって定義された複数の矩形領域に対応する第１の地図データと、前記複数の矩形領域に対応する、前記第１の地図データより新しいバージョンの第２の地図データと、前記端末装置の機種と所定の係数とを対応付ける情報と、を保持し、
前記第１の地図データ及び第２の地図データは、地図上の交差点に対応するノード及び前記交差点を結ぶ道路に対応するリンクを示す情報を含み、
前記地図データ配信方法は、
前記地図データ配信サーバが、前記第１の地図データを前記第２の地図データに更新するための差分データとして、各々が単一の又は複数の前記矩形領域に属する単一の又は連続する複数の前記リンクの追加、削除又は変更を示すデータを含む、複数の更新エレメントを作成する第１手順と、
前記地図データ配信サーバが、前記各更新エレメントに含まれるデータの量、及び前記各更新エレメントによって更新される前記矩形領域の数の双方に基づいて、前記各更新エレメントに含まれる前記差分データの量が多いほど長く、かつ、前記各更新エレメントによって更新される前記矩形領域の数が多いほど長くなるように、前記各更新エレメントに基づく前記第１の地図データの更新に要する時間を算出する第２手順と、
前記地図データ配信サーバが、前記ネットワークに接続された端末装置から前記第１の地図データの更新対象の前記矩形領域を指定する情報と、前記端末装置の機種を示す情報と、更新時間を指定する情報と、を含む地図データ配信要求を受信すると、前記更新対象の矩形領域を更新する前記更新エレメントを前記端末装置に送信する第３手順と、を含み、
前記第３手順は、
前記地図データ配信要求が更新時間を指定する情報を含む場合、前記地図データ配信サーバが、前記更新対象の矩形領域を更新する各更新エレメントについての前記算出された更新に要する時間に対して、送信された前記端末装置の機種を示す情報に基づいて特定した前記端末装置の機種に対応した係数を乗じることによって、前記端末装置による前記各更新エレメントに基づく前記第１の地図データの更新に要する時間を算出する手順と、
前記地図データ配信サーバが、前記更新対象の矩形領域を更新する前記更新エレメントから、前記算出された前記端末装置による更新に要する時間の合計値が前記指定された更新時間を超えないように一つ以上の前記更新エレメントを選択し、前記選択された一つ以上の更新エレメントを前記端末装置に送信する手順、又は、前記算出された前記端末装置による各更新エレメントに基づく前記第１の地図データの更新に要する時間を前記端末装置に送信する手順、の一方と、を含むことを特徴とする地図データ配信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データを利用したサービスを利用者に提供する技術に関し、特に、ナビゲーション装置が保持する地図データを更新する技術に関する。
【背景技術】
【０００２】
車載用ナビゲーション装置に代表される種々のナビゲーション装置は、経路の検索及び表示等のサービスを提供するために、地図データを保持している。現実の道路が新設又は付け替え等によって変更された場合、適切なサービスを提供するためには、保持された地図データにもその変更を反映させる必要がある。しかし、例えば日本全国の地図データをすべて更新するには相当の時間を要する。このため、地図データを地図上の所定の領域ごとに更新することによって、所望の地域の最新の地図データを短時間で取得する技術が提案されている。
【０００３】
例えば、特許文献１及び３には、地図データの更新が必要な領域を管理する情報を保持し、その情報に基づいて地図データを更新する技術が記載されている。さらに、これらの特許文献には、地図情報処理装置が保持する地図データを更新するための更新情報を取得するために要する時間を提示する技術が記載されている。
【０００４】
特許文献２には、メッシュに含まれる地図データの量に基づいて、地図データを取得するための通信時間を考慮することによって、効率的なデータ取得を実現する技術が記載されている。
【０００５】
上記の特許文献では、一般にメッシュ又はパーセルと呼ばれる所定の領域ごとに地図データが更新される。しかし、例えば複数の領域にまたがる道路が変更された場合において、それらの一部の領域の地図データのみが更新されると、更新後の地図データにおいて道路が領域の境界で途切れるなどの矛盾が発生する場合がある。このような矛盾の発生を防ぐための技術は、例えば、特許文献４又は非特許文献１に記載されている。特許文献４によれば、道路の途切れを防ぐために、指定された領域に隣接する領域の地図データも必要に応じて更新される。非特許文献１によれば、連続した道路の変更（追加又は削除等）を反映する更新データの集合が地図データ更新の最小単位（すなわち更新エレメント）として扱われる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−６５７７０号公報
【特許文献２】特開２００４−３４７６８５号公報
【特許文献３】特開２００９−２５８１２４号公報
【特許文献４】特開２００７−２４１００３号公報
【非特許文献】
【０００７】
【非特許文献１】“地図更新サービス／ソリューション”、［ｏｎｌｉｎｅ］、［平成２２年０７月０１日検索］、インターネット＜ＵＲＬ：http://www.hitachi-automotive.co.jp/products/cis/02.html＞
【発明の概要】
【発明が解決しようとする課題】
【０００８】
一般に、車載用ナビゲーション装置は、地図データの更新処理を行っている間、ユーザに経路検索等のサービスを提供することができないか、又は、提供できるサービスが大幅に制限される。したがって、ユーザの利便性を損なわないために、地図データの更新は、ユーザが自動車を運転していない時間帯に実行することが望ましい。しかし、ユーザが自動車を運転していない時間帯は、例えば自動車の運転者が休憩している時間帯、又は給油している時間帯のように、比較的短時間に制限される場合が多い。さらに、エンジンが停止している場合には、更新のための電力消費によって車載バッテリの残容量が不足すると、エンジンを起動できなくなるなどの問題が発生し、ユーザの利便性が損なわれる。したがって、ユーザの利便性を損なわないためには、更新時間を制限する必要がある。しかし、従来、指定された時間内に終了するように更新処理を制御することはできなかった。例えば、上記の特許文献１〜３には、地図データの通信に要する時間を考慮することは記載されているが、更新処理に要する時間については記載されていない。
【０００９】
さらに、地図データの更新は、道路の途切れのような地図データの矛盾が生じないように実行されることが望ましい。例えば更新がメッシュごとに行われる場合、矛盾の発生を防ぐために、特許文献４に示すように、更新を要求されたメッシュだけでなく、その周囲のメッシュの更新も必要になる場合がある。矛盾の発生を防ぐためにいくつのメッシュを更新する必要があるかを事前に予測することは困難であるため、指定された時間内に更新が終了することを保証することができない。
【００１０】
非特許文献１に示すように、更新エレメントごとに地図データを更新すれば、地図データの矛盾は発生しない。しかし、更新エレメントのデータサイズには大きなばらつきがあるため、更新に要する時間を更新エレメントごとに予測する必要がある。非特許文献１には、そのような更新時間の予測について記載されていない。
【００１１】
本発明は上記の問題点に鑑みてなされたものであり、許容される更新時間に応じて、矛盾が生じないように地図データの更新処理を実行することによって、利便性の高いナビゲーション装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の代表的な一例を示せば次の通りである。すなわち、ネットワークに接続される地図データ配信サーバと、前記ネットワークを介して前記地図データ配信サーバと通信する端末装置と、を備える地図データ配信システムであって、前記地図データ配信サーバは、前記ネットワークに接続される第１インターフェースと、前記第１インターフェースに接続される第１プロセッサと、前記第１プロセッサに接続される第１記憶装置と、を備え、地図上の空間を分割することによって定義された複数の矩形領域に対応する第１の地図データと、前記複数の矩形領域に対応する、前記第１の地図データより新しいバージョンの第２の地図データと、前記端末装置の機種と所定の係数とを対応付ける情報と、を保持し、前記第１の地図データ及び第２の地図データは、地図上の交差点に対応するノード及び前記交差点を結ぶ道路に対応するリンクを示す情報を含み、前記端末装置は、前記地図データ配信サーバと通信する第２インターフェースと、前記第２インターフェースに接続される第２プロセッサと、前記第２プロセッサに接続される第２記憶装置と、を備え、前記複数の矩形領域に対応する前記第１の地図データを保持し、前記地図データ配信サーバは、前記第１の地図データを前記第２の地図データに更新するための差分データとして、各々が単一の又は複数の前記矩形領域に属する単一の又は連続する複数の前記リンクの追加、削除又は変更を示すデータを含む、複数の更新エレメントを作成し、前記各更新エレメントに含まれるデータの量、及び前記各更新エレメントによって更新される前記矩形領域の数の双方に基づいて、前記各更新エレメントに含まれる前記差分データの量が多いほど長く、かつ、前記各更新エレメントによって更新される前記矩形領域の数が多いほど長くなるように、前記各更新エレメントに基づく前記第１の地図データの更新に要する時間を算出し、前記端末装置は、前記第１の地図データの更新対象の矩形領域を指定する情報と、前記端末装置の機種を示す情報と、更新時間を指定する情報と、を含む地図データ配信要求を前記地図データ配信サーバに送信し、前記地図データ配信サーバは、前記更新対象の矩形領域を更新する各更新エレメントについての前記算出された更新に要する時間に対して、送信された前記端末装置の機種を示す情報に基づいて特定した前記端末装置の機種に対応した係数を乗じることによって、前記端末装置による前記各更新エレメントに基づく前記第１の地図データの更新に要する時間を算出し、前記更新対象の矩形領域を更新する前記更新エレメントから、前記算出された前記端末装置による更新に要する時間の合計値が前記指定された更新時間を超えないように一つ以上の前記更新エレメントを選択し、前記選択された一つ以上の更新エレメントを前記端末装置に送信し、前記端末装置は、前記送信された更新エレメントに基づいて、前記第１の地図データを更新することを特徴とする。
【発明の効果】
【００１３】
本発明の一実施形態によれば、許容される更新時間に応じて矛盾が生じないように地図データの更新処理を実行することによって、利便性の高いナビゲーション装置を提供することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の第１の実施形態の地図データ配信システムの構成を示すブロック図である。
【図２】本発明の第１の実施形態のナビゲーション端末を含む自動車内機器の説明図である。
【図３】本発明の第１の実施形態におけるパーセル及び更新エレメントの説明図である。
【図４】本発明の第１の実施形態の地図配信サーバが保持するパーセルＩＤ−エレメント対応テーブルの説明図である。
【図５】本発明の第１の実施形態の地図配信サーバが保持するナビ型番−更新時間係数対応テーブルの説明図である。
【図６】本発明の第１の実施形態の地図配信サーバが保持する更新エレメント管理テーブルの説明図である。
【図７】本発明の第１の実施形態の地図配信サーバが実行する更新時間計算処理を示すフローチャートである。
【図８】本発明の第１の実施形態の地図配信サーバ及びナビゲーション端末が実行する端末地図更新処理を示すフローチャートである。
【図９】本発明の第２の実施形態の地図データ配信システムの構成を示すブロック図である。
【図１０】本発明の第２の実施形態の地図配信サーバが保持するパーセルＩＤ−エレメント対応テーブルの説明図である。
【図１１】本発明の第２の実施形態の地図配信サーバ及びナビゲーション端末が実行する端末地図更新処理を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、図面を用いて本発明の実施の形態を説明する。
【００１６】
＜第１の実施形態＞
図１は、本発明の第１の実施形態の地図データ配信システムの構成を示すブロック図である。
【００１７】
本実施形態の地図データ配信システムは、ネットワーク４０に接続された地図配信サーバ１０と、ネットワーク４０を介して地図配信サーバ１０と通信するナビゲーション端末２０と、を備える。
【００１８】
地図配信サーバ１０は、互いに接続されたプロセッサ１６、メモリ１７、ネットワークインターフェース（Ｉ／Ｆ）１８、管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１９を備える計算機である。
【００１９】
プロセッサ１６は、メモリ１７に格納されたプログラムを実行する。
【００２０】
メモリ１７は、例えば半導体メモリであり、プロセッサ１６によって実行されるプログラム及びプロセッサ１６によって参照されるデータ等を格納する。本実施形態のメモリ１７には、少なくとも更新時間予測処理部１３、更新データ抽出部１４及び更新データ管理部１５が格納される。プロセッサ１６がプログラムを実行することによって実現される処理については後述する。以下の説明において更新時間予測処理部１３等が実行する処理は、実際には、プロセッサ１６によって実行される。
【００２１】
ネットワークＩ／Ｆ１８は、ネットワーク４０に接続され、ナビゲーション端末２０等と通信する。
【００２２】
管理データ記憶部１１、更新データ記憶部１２及び地図データ記憶部１９は、それぞれがハードディスクドライブ（ＨＤＤ）又はフラッシュメモリのような記憶装置であってもよいし、一つの記憶装置内の記憶領域であってもよい。
【００２３】
地図データ記憶部１９には、地図データが格納される。地図データは、地図の構成物（地物）の位置及び形状を示す座標値等を含む。現実の地物は随時更新される。その一例は、道路の新設、廃止又は付け替えのような道路ネットワークの更新である。地図データは、過去のある時点における地物に関する情報と、それより後の時点における地物に関する情報と、を含んでもよい。
【００２４】
なお、一般に地図データは、地図上の所定の矩形の範囲ごとに管理される。この矩形の範囲は、パーセル又はメッシュと呼ばれる。各パーセルには固有の識別子（パーセルＩＤ）が付与される。
【００２５】
更新データ記憶部１２には、地物を単位とする地図更新データ（地図情報及び道路ネットワーク情報を含む）が格納される。地図更新データは、例えばナビゲーション端末２０があるバージョンの地図データを保持している場合に、それをより新しいバージョンの地図データに更新するために作成及び送信されるデータであり、具体的には、少なくともこれらのバージョンの差分データを含む。具体的には、更新データ記憶部１２には、少なくとも更新エレメント管理テーブル６００が格納される。更新エレメント及び更新エレメント管理テーブルの詳細については後述する（図３及び図６参照）。
【００２６】
管理データ記憶部１１には、地図更新データを管理するための情報が格納される。例えば、管理データ記憶部１１には、地図更新データのバージョン（すなわち差分の世代）を示す情報、及び、地図更新データが適用されるべき位置を示すパーセルＩＤ等が格納される。具体的には、管理データ記憶部１１には、少なくともパーセルＩＤ−エレメント対応テーブル４００及びナビ型番−更新時間係数対応テーブル５００が格納される。これらの詳細については後述する（図４及び図５参照）。
【００２７】
ナビゲーション端末２０は、ユーザを目的地まで誘導するために、経路検索及び検索結果の出力等を行う移動端末である。本実施形態では典型的な例として、ナビゲーション端末２０が自動車内機器６０の一部として自動車に搭載される車載用ナビゲーション端末である場合について説明するが（図２参照）、例えば歩行者に携帯されるナビゲーション端末等、種々の移動端末に本発明を適用することができる。
【００２８】
本実施形態のナビゲーション端末２０は、互いに接続されたプロセッサ２８、メモリ２９、ネットワークＩ／Ｆ２１、画面入出力Ｉ／Ｆ２５、管理データ記憶部２６及び地図データ記憶部２７を備える。
【００２９】
プロセッサ２８は、メモリ２９に格納されたプログラムを実行する。
【００３０】
メモリ２９は、例えば半導体メモリであり、プロセッサ２８によって実行されるプログラム及びプロセッサ２８によって参照されるデータ等を格納する。本実施形態のメモリ２９には、配信要求部２２、地図更新部２３及びナビゲーション処理部２４が格納される。
【００３１】
配信要求部２２は、地図更新データ配信要求を地図配信サーバ１０に送信する。地図更新部２３は、配信された地図更新データを用いて、地図データ記憶部２７に格納された地図データを更新する。これらの処理については後述する。以下の説明において配信要求部２２、地図更新部２３及びナビゲーション処理部２４が実行する処理は、実際にはプロセッサ２８によって実行される。
【００３２】
ナビゲーション処理部２４は、地図データ記憶部２７に格納された地図データに基づいて、目的地までの経路を検索し、その経路に沿ってユーザを誘導する。このような経路検索及び誘導は従来の車載用ナビゲーション端末と同様であるため、これらに関する詳細な説明は省略する。
【００３３】
画面入出力Ｉ／Ｆ２５は、ユーザに対して地図情報等を表示する画面と、ユーザからの入力を受け付ける入力装置と、を含む。例えば、画面入出力Ｉ／Ｆ２５は、タッチパッド付きの液晶表示装置であってもよい。
【００３４】
ネットワークＩ／Ｆ２１は、無線通信装置３０に接続される。無線通信装置３０は、ネットワーク４０に接続された無線基地局３１と無線通信を行う。ネットワークＩ／Ｆ２１は、無線通信装置３０、無線基地局３１及びネットワーク４０を介して地図配信サーバ１０との間の通信を実行する。後述する地図データ配信要求の送信及び地図更新データの受信はこのような通信によって実現される。
【００３５】
なお、無線通信装置３０は、ナビゲーション端末２０に内蔵されてもよい。
【００３６】
管理データ記憶部２６及び地図データ記憶部２７は、それぞれがハードディスクドライブ（ＨＤＤ）又はフラッシュメモリのような記憶装置であってもよいし、一つの記憶装置内の記憶領域であってもよい。
【００３７】
地図データ記憶部２７には、ナビゲーション処理部２４によって参照される地図データが格納される。この地図データは、地図配信サーバ１０から送信された地図更新データに基づいて更新される。
【００３８】
管理データ記憶部２６には、地図データを管理するための情報が格納される。例えば、管理データ記憶部２６には、自車（すなわちナビゲーション端末２０を搭載している車）の位置がどのパーセルに属するかを示す緯度経度−パーセルＩＤ対応情報、及び、地図に適用した地図更新データの識別情報等が格納される。
【００３９】
ネットワーク４０はインターネット４１に接続される。地図配信サーバ１０は、インターネット４１を介して新しいバージョンの地図データを取得してもよい。
【００４０】
図２は、本発明の第１の実施形態のナビゲーション端末２０を含む自動車内機器６０の説明図である。
【００４１】
本実施形態のナビゲーション端末２０は、自動車内機器６０の一部として自動車内に設置される。自動車内機器６０は、少なくとも、ナビゲーション端末２０、車載制御装置５０、バッテリ５５及び各種センサ（例えばハンドル角度センサ５１、ブレーキペダルセンサ５２、アクセルペダルセンサ５３及び電圧・電流センサ５４等）を含む。
【００４２】
バッテリ５５は、ナビゲーション端末２０を含む自動車内機器６０に電力を供給する電源である。自動車内機器６０が内燃機関を動力源とする自動車に設置される場合、バッテリ５５は、自動車内機器６０だけでなく、内燃機関を始動するモータへも電力を供給する。自動車内機器６０が電気モータを動力源とする自動車（例えばいわゆるハイブリッド車又は電気自動車）に設置される場合、バッテリ５５は、自動車内機器６０だけでなく、さらに動力源である電気モータにも電力を供給する。
【００４３】
電圧・電流センサ５４は、バッテリ５５の出力電圧及び出力電流の少なくとも一方を測定する。
【００４４】
車載制御装置５０は、一般に、プロセッサ及びメモリ等を含む処理装置であり、各種センサに接続され、各種センサから取得したデータに基づく処理を実行することができる。車載制御装置５０は、さらにネットワークＩ／Ｆ２１に接続され、各種センサから取得したデータ又はそれらに基づく処理の結果をナビゲーション端末２０に送信することができる。例えば、車載制御装置５０は、電圧・電流センサ５４から取得した電圧及び電流の値をナビゲーション端末２０に送信してもよいし、それらの値に基づいてバッテリ５５の残容量を計算し、計算された残容量の値をナビゲーション端末２０に送信してもよい。
【００４５】
車載制御装置５０は、公知の方法によってバッテリ５５の残容量を計算することができる。例えば、車載制御装置５０は、電圧・電流センサ５４が測定した出力電圧の変動に基づいて残容量を計算してもよいし、出力電流の積算値に基づいて残容量を計算してもよい。
【００４６】
図２には代表的な例として自動車に設置されるナビゲーション端末２０を示したが、本実施形態はその他の種類のナビゲーション端末、例えば歩行者に携帯される端末にも適用することができる。その場合も、図２と同様、ナビゲーション端末２０はバッテリ５５に接続され、そこから電力の供給を受ける。また、バッテリ５５には電圧・電流センサ５４が接続される。
【００４７】
図３は、本発明の第１の実施形態におけるパーセル及び更新エレメントの説明図である。具体的には、図３は、地図データ記憶部１９又は地図データ記憶部２７に格納される地図データに含まれる道路ネットワークの更新の一例を示す。
【００４８】
周知のように、地図データは道路ネットワークに関する情報を含み、道路ネットワークは、ノードとリンクとの組み合わせによって表現される。ノードは交差点等に、リンクは二つの交差点等を接続する道路の区間に対応する。すなわち、地図データは、各ノードの座標を示す情報、及び、ノード間を接続するリンクの形状を示す情報等を含む。このような地図データの具体的な形式は従来のナビゲーションシステムにおいて使用されるものと同様であってよいため、詳細な説明は省略する。
【００４９】
前述のように、パーセルとは、地図上の空間を区切ることによって定義された、所定の大きさの領域である。地図データは、パーセルごとに管理される。より具体的には、例えば、一つのパーセル内のノード及びリンクに関する情報が、地図データを格納するデータベースの一つのレコードであってもよい。例えば、図３に示す道路ネットワーク３００Ａは、９個の矩形のパーセル３０１〜３０９ごとに管理される。この例において、円形の標識がノードを、ノード間を接続する太い線がリンクを表す。
【００５０】
ここで、パーセルごとの地図データの管理について説明する。
【００５１】
例えば、道路ネットワーク３００Ａのパーセル３０１には、ノード３２２及びそれに接続されるリンク３６２〜３６４が含まれる。パーセル３０２には、ノード３２３及びそれに接続されるリンク３６５〜３６８が含まれる。通常、一つのパーセルに含まれるデータは、地図データ記憶部２７の連続した領域に格納される。これに対して、異なるパーセルに含まれるデータは連続した領域に書き込まれるとは限らない。このため、対象のデータ量が同じであっても、一般に、複数のパーセルに含まれるデータの読み出し及び書き込みに要する時間は、一つのパーセルに含まれるデータの読み出し及び書き込みに要する時間より長くなる。
【００５２】
また、上記のように一つのパーセルに対応する地図データが一つのレコードとして扱われる場合、一つのパーセル内の一部のデータのみを更新するためであっても、そのパーセルに対応する地図データ全体を読み出して、更新し、更新されたデータを元のデータに上書きする必要がある。したがって、実際に更新されるデータ量が同じであっても、そのデータが一つのパーセル内に集中している場合より、複数のパーセルに分散している場合の方が読み出し及び書き込みを行うデータ量が多く、そのために要する時間も長くなる。
【００５３】
さらに、このような場合において、複数のパーセルに対応するデータの読み出し及び書き込みをするために、パーセルごとにＩ／Ｏコマンドを発行する必要がある場合がある。その場合、例えば一つのパーセルに含まれるデータの読み出し及び書き込みは、それぞれ１回のＩ／Ｏによって実行することができるが、二つのパーセルに含まれるデータの読み出し及び書き込みは、それぞれ２回のＩ／Ｏによって実行される。
【００５４】
例えば、地図データ記憶部２７に格納された地図データのうち、リンク３６３及び３６４の形状を更新する必要がある場合、ナビゲーション端末２０の地図更新部２３は、パーセル３０１に含まれる全てのノード及びリンクのデータを地図データ記憶部２７から読み出し、読み出されたデータのうちリンク３６３及び３６４の形状を示すデータを更新し、更新されたデータを含む全てのノード及びリンクのデータを地図データ記憶部２７に上書きしてもよい。
【００５５】
一方、リンク３６４及び３６５の形状を更新する必要がある場合、地図更新部２３は、例えば、パーセル３０１及び３０２に含まれる全てのノード及びリンクのデータを地図データ記憶部２７から読み出し、読み出されたデータのうちリンク３６４及び３６５の形状を示すデータを更新し、更新されたデータを含む全てのノード及びリンクのデータを地図データ記憶部２７に上書きする。
【００５６】
仮に各パーセル全体のデータ量が概ね同じであるとすると、上記の二つの場合のうち後者の場合に読み出され、書き込まれるデータ量は、実際に更新されるリンクのデータ量にかかわらず、前者の場合の約２倍となる。
【００５７】
更新のために地図データ記憶部２７から読み出されたデータはメモリ２９に一時的に格納され、地図更新部２３によって更新される。典型的なメモリ２９はダイナミックランダムアクセスメモリ（ＤＲＡＭ）であり、典型的な地図データ記憶部２７はＨＤＤ又はフラッシュメモリのような不揮発性の記憶装置である。したがって、一般に、メモリ２９に対するＩ／Ｏ処理と比較して、地図データ記憶部２７に対するＩ／Ｏ処理はずっと低速である。このため、地図データ記憶部２７から読み出され、その後書き込まれるデータ量、及びそのためのＩ／Ｏ処理の回数は、地図データ記憶部２７内の地図データの更新処理に要する時間の全体に対して無視できない程度の影響を与える。
【００５８】
次に、更新エレメントについて説明する。
【００５９】
一般に、地図データは、現実の道路の変更が反映されるように所定のタイミングで（例えば数ヶ月ごとに）更新される。更新された地図データは、例えば、地図情報を扱う出版社によって作成され、インターネット４１を介して提供される。新しい地図データが提供された場合、地図配信サーバ１０の地図データ記憶部１９には、更新される前の（すなわち旧バージョンの）地図データと、更新された後の（すなわち新バージョンの）地図データの両方が格納される。図３の道路ネットワーク３００Ａ及び３００Ｂは、それぞれ、旧バージョン（Ｖｅｒ．１）及び新バージョン（Ｖｅｒ．２）の地図データが示す道路ネットワークの例である。
【００６０】
道路ネットワーク３００Ａ及び３００Ｂを比較すると、パーセル３０１、３０２、３０３、３０７及び３０８に含まれるノード及びリンクは変更されていない。
【００６１】
道路ネットワーク３００Ａにおいて、パーセル３０５はノード３１１と３１２とを接続するリンク３５１を含み、パーセル３０６はノード３１３と３１４とを接続するリンク３５２を含む。
【００６２】
道路ネットワーク３００Ｂにおいて、リンク３５１及び３５２は削除され、ノード３１６、３１７、３１８、３１９、３２０、３２１、リンク３５３、３５４、３５５、３５６、３５７、３５８、３５９、３６０及び３６１が追加されている。
【００６３】
地図配信サーバ１０が新バージョンの地図データを取得した時点で、ナビゲーション端末２０の地図データ記憶部２７には旧バージョンの地図データ（すなわち道路ネットワーク３００Ａ）が格納されている。このため、配信要求部２２が地図データ配信要求を地図配信サーバ１０に送信し、それに応じて送信された地図データ（すなわち更新データ）を用いて地図更新部２３が地図データ記憶部２７内の地図を更新する。地図データ配信要求は、種々のイベント、例えば前回の配信から所定の時間が経過したこと、所定の日時が到来したこと、ユーザから更新要求を入力されたこと、などを契機として送信され得る。
【００６４】
従来の地図データの更新方法として、パーセルごとの更新及び更新エレメントごとの更新が知られている。本実施形態では更新エレメントごとの更新が実行される。
【００６５】
仮にパーセルごとの更新が実行されるとすると、例えばパーセル３０５の更新が要求された場合、リンク３５１が削除され、ノード３１６、３１７、３１８、リンク３５４、３５５、及び３５７が追加される。この場合、リンク３５３及び３５８は追加されないため、リンク３５４及び３５７はそれぞれノード３１６及び３１８で途切れる。
【００６６】
一方、本実施形態では、連続するリンクに関する更新データが更新エレメントとしてまとめられ、更新エレメントごとに更新が実行される。なお、本実施形態において、二つのリンクが一つのノードに接続される場合、それらのリンクが連続すると記載する。例えば、リンク３５３及び３５４は、一つのノード３１６に接続されるため、連続する。同様に、リンク３５４、３５５、３５６及び３５７は一つのノード３１７に接続されるため、連続する。リンク３５７及び３５８は一つのノード３１８に接続されるため、連続する。リンク３５８、３５９及び３６０は一つのノード３１９に接続されるため、連続する。結局、リンク３５３〜３６０は連続する。このため、リンク３５３〜３６０の追加を示す更新データが一つの更新エレメント３７１としてまとめられる。
【００６７】
この更新エレメント３７１は、さらに、これらのリンクに接続されるノードの追加、削除又は変更を示す更新データも含む。図３の例では、ノード３１６〜３１９の追加を示す更新データが更新エレメント３７１に含まれる。ノード３１１〜３１５は上記のリンクのいずれかに接続されるノードであり、かつ、新バージョン及び旧バージョンの道路ネットワークのいずれにも含まれている。しかし、これらのノードの座標又はその他の属性値が変更される場合には、その変更を示す更新データも更新エレメント３７１に含まれる。
【００６８】
新バージョンで削除されるリンク３５１と、追加されるリンク３５５とは、同時に存在し得ないが、いずれも一つのノード３１１に接続されているため、リンク３５１の削除を示す更新データも更新エレメント３７１に含まれる。同様に、リンク３５２の削除を示す更新データも更新エレメント３７１に含まれる。
【００６９】
リンク３６１は更新エレメント３７１に含まれるいずれのリンクとも連続しない。このため、リンク３６１及びその両端のノード３２０及び３２１の追加を示す更新データは別の更新エレメント３７２に含まれる。
【００７０】
この例において、配信要求部２２がパーセル３０５を対象とする地図データ配信要求を地図配信サーバ１０に送信すると、地図配信サーバ１０の更新データ管理部１５は、パーセル３０５内のリンク又はノードに関する更新データを含む更新エレメント３７１をナビゲーション端末２０に送信する。ナビゲーション端末２０の地図更新部２３は、送信された更新エレメント３７１に従って、リンク３５１及び３５２の削除、並びに、リンク３５３〜３６０及びノード３１６〜３１９の追加を実行する。これによって、地図データ記憶部２７に格納された地図データが更新される。なお、この時点でまだ更新エレメント３７２が反映されていないとしても、道路の途切れのような矛盾は発生しない。
【００７１】
なお、以下の説明において、あるパーセル内のリンク又はノードの更新を示す情報を含む更新エレメントを、そのパーセルに対応する更新エレメントと記載する。例えば、更新エレメント３７１は、パーセル３０４にリンク３５３を追加することを示す情報を含むため、パーセル３０４に対応する。同様に、更新エレメント３７１は、パーセル３０５及び３０６にも対応する。同様に、更新エレメント３７２はパーセル３０６及び３０９に対応する。言い換えると、パーセル３０４、３０５及び３０６は、更新エレメント３７１によって更新される。同様に、パーセル３０６及び３０９は更新エレメント３７２によって更新される。
【００７２】
図３は説明のために単純化されているが、実際には一つのパーセルに複数の更新エレメントが対応する場合があり、また、１回の地図データ配信要求において複数のパーセルが更新対象として指定される場合がある。したがって、実際には１回の地図データ配信要求に応じて多数の更新エレメントが送信される可能性がある。本実施形態の更新データ管理部１５は、指定されたパーセルに関連する複数の更新エレメントのうち、指定された時間内に更新が終了すると予測されるもののみを送信する。その詳細については後述する。
【００７３】
続いて、本実施形態の地図配信サーバ１０が保持するデータ及びそれに基づく更新エレメントの送信について説明する。
【００７４】
図４は、本発明の第１の実施形態の地図配信サーバ１０が保持するパーセルＩＤ−エレメント対応テーブル４００の説明図である。
【００７５】
パーセルＩＤ−エレメント対応テーブル４００は、パーセルと更新エレメントとを対応付ける情報及び各更新エレメントの更新時間等を示す情報を含む。このテーブルは、ナビゲーション端末２０からの地図データ配信要求を受けた更新データ管理部１５によって参照される。
【００７６】
具体的には、パーセルＩＤ−エレメント対応テーブル４００は、パーセルＩＤ４０１、更新エレメントＩＤ４０２、更新時間４０３及びサイズ４０４を含む。
【００７７】
パーセルＩＤ４０１は、各パーセルの識別子である。
【００７８】
更新エレメントＩＤ４０２は、各パーセルに対応する更新エレメントの識別子である。
【００７９】
更新時間４０３は、各更新エレメントをナビゲーション端末２０に反映させるために要すると予測される時間である。この時間の算出方法については後述する。
【００８０】
サイズ４０４は、各更新エレメントのデータサイズである。
【００８１】
例えば、行４１２にはパーセルＩＤ「０００１」に対応する更新エレメントＩＤ「１１」が格納され、行４１３にはパーセルＩＤ「０００２」に対応する更新エレメントＩＤ「１１」が格納される。これは、識別子「１１」によって識別される一つの更新エレメント（ここでは「更新エレメント「１１」」と記載する。他の更新エレメントＩＤについても同様）が、二つのパーセル、すなわち識別子「０００１」によって識別されるパーセル及び識別子「０００２」によって識別されるパーセルに跨っていることを示す。
【００８２】
また、行４１１及び４１２を参照して、更新エレメントＩＤ「１０」で識別される更新エレメント「１０」と更新エレメント「１１」とを比較すると、前者のサイズ４０４は後者のそれより大きいが、前者の更新時間４０３は後者のそれより短い。一般にサイズ４０４が大きいほど更新時間４０３が長くなるが、前者が跨るパーセルの数が後者のそれより小さい場合には上記のような更新時間の逆転が起こりうる。
【００８３】
図５は、本発明の第１の実施形態の地図配信サーバ１０が保持するナビ型番−更新時間係数対応テーブル５００の説明図である。
【００８４】
ナビ型番−更新時間係数対応テーブル５００は、ナビゲーション端末２０の機種と、各更新エレメントの更新時間を計算するときに使用される係数とを対応付ける情報を保持する。具体的には、ナビ型番−更新時間係数対応テーブル５００は、ナビ型番５０１及び係数５０２を含む。
【００８５】
ナビ型番５０１は、ナビゲーション端末２０の機種を識別する情報である。図１には一つのナビゲーション端末２０のみを示したが、実際には多数のナビゲーション端末２０がネットワーク４０を経由して地図配信サーバに地図データ配信要求を送信する。これらは、互いに機種の異なるナビゲーション端末２０を含んでもよい。ナビ型番５０１には、地図配信サーバ１０に地図データ配信要求を送信する可能性があるナビゲーション端末２０の機種を識別する情報が格納される。
【００８６】
係数５０２は、各ナビゲーション端末２０の機種に対応する更新時間係数である。ナビゲーション端末２０の処理性能は搭載されたプロセッサ２８等のハードウェア性能及びそれらを制御するソフトウェアの仕様等に依存するため、同一の更新エレメントに基づく更新に要する時間が機種ごとに異なる場合がある。例えば、ある機種のナビゲーション端末２０がある更新エレメントに基づく地図データの更新に要した時間を基準として、各機種のナビゲーション端末２０が同じ更新エレメントに基づく地図データの更新に要した時間と基準更新時間との比率を係数５０２として格納してもよい。
【００８７】
図５の例では、ナビ型番５０１の値「ＮＡＶＩ−１０００」及び「ＮＡＶＩ−１００１」に対応する係数５０２として、それぞれ「１．０」及び「１．１」が格納されている。これは、「ＮＡＶＩ−１００１」によって識別される機種のナビゲーション端末２０がある更新エレメントに基づく更新をするために要する時間が、「ＮＡＶＩ−１００１」によって識別される機種のナビゲーション端末２０が同じ更新エレメントに基づく更新をするために要する時間の１．１倍であることを示す。
【００８８】
図６は、本発明の第１の実施形態の地図配信サーバ１０が保持する更新エレメント管理テーブル６００の説明図である。
【００８９】
地図配信サーバ１０は、新しいバージョンの地図データを取得すると、古いバージョンの地図データを新しいバージョンに更新するための更新エレメントを作成する（図３参照）。作成された更新エレメントは、更新エレメント管理テーブル６００に格納される。
【００９０】
更新エレメント管理テーブル６００は、更新エレメントＩＤ６０１及び更新データ６０２を含む。
【００９１】
更新エレメントＩＤ６０１は、各更新エレメントを一意に識別する。
【００９２】
更新データ６０２は、各更新エレメントに含まれる更新データである。この更新データは、具体的には、ノード又はリンクの追加、削除及び変更等を示す情報を含む。このような更新データのフォーマットは従来のナビゲーションシステムにおいて適用されるものと同様であってよいため、詳細な説明は省略する。
【００９３】
図７は、本発明の第１の実施形態の地図配信サーバ１０が実行する更新時間計算処理を示すフローチャートである。
【００９４】
この処理は、地図配信サーバ１０が新しいバージョンの地図データを取得した後、ナビゲーション端末にそのバージョンの更新データを送信するまでの間のいずれかの時点で実行される。
【００９５】
最初に、更新データ管理部１５が新しいバージョンの地図データ（例えば図３の道路ネットワーク３００Ｂに対応する地図データ）を取得し、それを地図データ記憶部１９に格納する（Ｓ７０１）。
【００９６】
次に、更新データ抽出部１４が、新しいバージョンの地図データと、地図データ記憶部１９に格納されている古いバージョンの地図データ（例えば図３の道路ネットワーク３００Ａに対応する地図データ）とを比較し、古いバージョンの地図データを新しいバージョンの地図データに更新するための差分データとして、更新エレメントを作成し、それを更新エレメント管理テーブル６００に格納する（Ｓ７０２）。更新エレメントは、図３を参照して説明した通りである。
【００９７】
なお、上記のＳ７０１及びＳ７０２は従来の地図配信サーバが実行するものと同様であってよい。
【００９８】
次に、更新時間予測処理部１３が、作成された更新エレメントごとに、その更新エレメントを用いてナビゲーション端末２０内の地図データを更新するために要する時間を計算し、計算された時間をパーセルＩＤ−エレメント対応テーブル４００に更新時間４０３として格納する（Ｓ７０３）。
【００９９】
図３及び図５を参照して説明したように、地図データの更新に要する時間は、主に、更新エレメントに含まれるデータの量、更新エレメントが跨るパーセルの数、及び、ナビゲーション端末２０の機種に依存する。ここで、更新エレメントが跨るパーセルの数とは、言い換えると、その更新エレメントによって更新されるパーセルの数である。例えば、図３の更新エレメント３７１は、少なくとも、パーセル３０４にリンク３５３を追加することを示す情報、パーセル３０５にリンク３５４等を追加することを示す情報、及び、パーセル３０６にリンク３５８等を追加することを示す情報を含む。この場合、更新エレメント３７１は、少なくとも三つのパーセルに跨る。
【０１００】
更新時間予測処理部１３は、更新エレメントに含まれるデータの量が多いほど長く、かつ、更新エレメントが跨るパーセルの数が多いほど長くなるように、各更新エレメントに対応する更新時間を計算する。例えば、更新時間予測処理部１３は、
更新時間＝Ａ×（更新エレメントに含まれるデータの量）＋Ｂ×（更新エレメントが跨るパーセルの数）  ・・・（１）
によって更新時間を計算してもよい。ここで、Ａ及びＢはナビゲーション端末２０の機種に依存する係数である。本実施形態では代表的な機種（例えば図５のナビ型番「ＮＡＶＩ−１０００」によって識別される機種）を用いてＡ及びＢの値を決定し、その他の機種による更新時間は図５の係数５０２を用いて算出する。
【０１０１】
なお、上記の式（１）は一例に過ぎず、本実施形態には種々の計算方法が適用され得る。
【０１０２】
図８は、本発明の第１の実施形態の地図配信サーバ１０及びナビゲーション端末２０が実行する端末地図更新処理を示すフローチャートである。
【０１０３】
最初に、ナビゲーション端末２０の配信要求部２２は、地図データ配信要求を地図配信サーバ１０に送信する（Ｓ８０１）。地図データ配信要求は、少なくとも、希望更新時間、更新対象のパーセルの識別子、及び、現在保持している地図データのバージョン、を指定する情報を含む。
【０１０４】
希望更新時間は、今回の地図データ配信要求に基づく地図データの更新処理に利用することが許容される時間である。後述するように、指定された希望更新時間内に終了するように更新処理が制御される。
【０１０５】
既に説明したように、ナビゲーション端末２０が地図データの更新処理を行っている間、他の機能（例えば経路検索又は経路案内）が大幅に制限される。本実施形態のナビゲーション端末２０は、このような機能制限によってユーザの利便性が損なわれないように、種々の基準に基づいて希望更新時間を決定することができる。
【０１０６】
例えば、ナビゲーション端末２０は、ユーザから画面入出力Ｉ／Ｆ２５を介して入力された希望更新時間をそのまま地図データ配信要求に含めて送信してもよい。ユーザは、ナビゲーション端末２０の経路検索等の機能を使用しない時間、典型的にはナビゲーション端末２０が搭載された自動車を運転しない時間を希望更新時間として入力することができる。例えば、ユーザは、休憩するとき、又は自動車に給油するとき等に、休憩又は給油が終了するまでの予定時間を希望更新時間として入力してもよいし、夜間などの自動車を使用しない時間を希望更新時間として入力してもよい。ナビゲーション端末２０が電気自動車に搭載される場合、ユーザは、バッテリ５５への充電を行う時間を希望更新時間として入力してもよい。
【０１０７】
ただし、内燃機関を動力源とする自動車において、エンジンが停止している場合、地図データ更新のための電力消費によってバッテリ５５の残容量が不足しないように更新時間を制限する必要がある。このため、ナビゲーション端末２０は、車載制御装置５０からバッテリ５５の残容量を示す情報を取得し、取得した残容量とナビゲーション端末２０自身の消費電力とに基づいて、取得した残容量を全て消費する更新時間より短い時間を希望更新時間として算出し、それを地図配信サーバ１０に送信してもよい。このとき、少なくともエンジンの起動に必要な容量がバッテリ５５に残るように希望更新時間を算出することが望ましい。
【０１０８】
なお、ナビゲーション端末２０が自動車に設置されない場合（例えば歩行者によって携帯される場合、）ナビゲーション端末２０のプロセッサ２８が電圧・電流センサ５４から取得した情報に基づいてバッテリ５５の残容量を計算してもよい。
【０１０９】
地図データ配信要求によって指定される更新対象のパーセルは、どのように決定されてもよい。例えば、ユーザが画面入出力Ｉ／Ｆ２５を介して任意のパーセルを更新対象として選択してもよい。具体的には、例えば、ユーザが現在地周辺又はこれから行く目的地の周辺のパーセルを更新対象として選択してもよい。あるいは、ナビゲーション端末２０が自動的に更新対象を選択してもよい。具体的には、例えば、夜間に更新処理を行う場合、ナビゲーション端末２０は、日本全国又は特定の地方のパーセルを更新対象として指定してもよい。
【０１１０】
地図データ配信要求に含まれる地図データのバージョンを示す情報は、少なくとも、更新対象として指定されたパーセルのバージョンを示す情報を含む。なお、本実施形態では地図データが更新エレメントごとに更新される。したがって、古いバージョンのパーセルに対応する複数の更新エレメントのいくつかが既にナビゲーション端末２０内の地図データに反映されている場合がある。このような更新エレメントを識別するため、上記の地図データのバージョンを示す情報は、各パーセルのバージョンを示す情報に加えて、そのパーセルに対応する更新エレメントのうち既に更新が終了したものを識別する情報を含んでもよい。
【０１１１】
さらに、Ｓ８０１において送信される地図データ配信要求は、それを送信したナビゲーション端末２０の機種を識別する情報を含んでもよい。
【０１１２】
ナビゲーション端末２０から地図データ配信要求を受信した地図配信サーバ１０の更新データ管理部１５は、指定された更新対象のパーセルの識別子、地図データのバージョン及び希望更新時間に基づいて、希望更新時間内に更新が終了する更新エレメントのリストを作成する（Ｓ８０２）。
【０１１３】
更新対象として指定されたパーセルであっても、ナビゲーション端末２０が保持しているそのパーセルの地図データのバージョンが最新である場合、そのパーセルの地図データを更新する必要がないため、そのパーセルに対応する更新エレメントはリストに登録されない。また、更新対象として指定されたパーセルの地図バージョンが最新でない場合であっても、そのパーセルに対応する更新エレメントが既にナビゲーション端末２０の地図データに反映されている場合、その更新エレメントに基づく更新をもう一度実行する必要はないため、その更新エレメントはリストに登録されない。このようなバージョンに基づく更新の要否判定及びそれに基づく更新エレメントの選択は、従来の地図データ配信方法と同様であるため、詳細な説明は省略する。
【０１１４】
更新データ管理部１５は、更新対象として指定されたパーセルに対応する、まだナビゲーション端末に反映されていない更新エレメントについて、パーセルＩＤ−エレメント対応テーブル４００の更新時間４０３を参照して、リストに登録された更新エレメントの更新時間の合計値が指定された希望更新時間を超えないように、リストに登録する更新エレメントを選択する。
【０１１５】
例えば、更新データ管理部１５は、更新対象として指定されたパーセルに対応する、まだナビゲーション端末２０に反映されていない更新エレメントの更新時間４０３を順次参照して、既にリストに登録されている更新エレメントの更新時間と、今回参照した更新エレメントの更新時間との合計値が希望更新時間を超えるか否かを判定し、希望更新時間を超えない場合には今回参照された更新エレメントをリストに追加する。この処理を、更新対象として指定されたパーセルに対応する、まだナビゲーション端末に反映されていない全ての更新エレメントについて行うことによって、リストを作成してもよい。
【０１１６】
なお、このような処理において、更新データ管理部１５は、例えばサイズ４０４の値が大きい順に更新エレメントの更新時間を参照してもよいし、サイズ４０４の値が小さい順に参照してもよいし、ランダムな順序で参照してもよい。
【０１１７】
図３を参照してＳ８０２の具体例を説明する。例えば更新対象としてパーセル３０４が指定された場合、更新データ管理部１５は、地図データ配信要求に含まれるパーセル３０４のバージョン情報に基づいて、ナビゲーション端末２０に格納されているパーセル３０４が最新か否かを判定する。例えばナビゲーション端末２０内のパーセル３０４が道路ネットワーク３００Ａの通りであり、まだ更新エレメント３７１が反映されていない場合、更新データ管理部１５は、更新エレメント３７１の更新時間４０３が希望更新時間を超えるか否かを判定する。既にリストに別の更新エレメントが登録されている場合、それらの更新エレメントの更新時間４０３と更新エレメント３７１の更新時間４０３との合計値が希望更新時間を超えるか否かを判定する。その結果が希望更新時間を超えない場合、更新エレメント３７１をリストに追加する。
【０１１８】
地図データ配信要求にナビゲーション端末２０の機種を識別する情報が含まれる場合、更新データ管理部１５は、更新時間４０３の値にその機種に対応する係数５０２を乗じることによってその機種による更新時間を算出し、その値に基づいて、リストに登録される更新エレメントを選択する。
【０１１９】
次に、更新データ管理部１５は、Ｓ８０２で作成したリスト（更新エレメントリスト）及び更新エレメントデータをナビゲーション端末２０に送信する（Ｓ８０３）。ここで、更新エレメントデータとは、更新エレメントリストに登録された更新エレメントの更新データ６０２である。
【０１２０】
地図配信サーバ１０から更新エレメントデータ等を受信したナビゲーション端末２０の地図更新部２３は、送信された更新エレメントデータに基づいて、地図データ記憶部２７に格納されている地図データを更新する（Ｓ８０４）。これによって、送信された更新エレメントが指示するリンク及びノードの追加、削除及び変更等が地図データに反映される。
【０１２１】
なお、上記の処理は一例であり、実際の更新に要する時間が希望更新時間を超えないように制御される限り、種々の処理が許容される。例えば、Ｓ８０２〜Ｓ８０４は次のように実行されてもよい。
【０１２２】
Ｓ８０２において、更新データ管理部１５は、更新時間にかかわらず、更新対象として指定されたパーセルに対応する、まだナビゲーション端末に反映されていない全ての更新エレメントを更新エレメントリストに登録する。Ｓ８０３において、更新データ管理部１５は、Ｓ８０２で作成した更新エレメントリスト、それに対応する更新エレメントデータ、及び、更新エレメントリストに格納された各更新エレメントの更新時間をナビゲーション端末２０に送信する。Ｓ８０４において、地図更新部２３は、送信された更新エレメントリストに登録されている更新エレメントから、更新時間の合計値が希望更新時間を超えないように一つ以上の更新エレメントを選択し、それらに基づいて地図データを更新する。
【０１２３】
以上の本発明の第１の実施形態によれば、更新エレメントごとに地図データが更新されるため、更新後の地図データに道路の途切れのような矛盾が生じない。さらに、指定された更新時間以内に更新が終了するように、反映すべき更新エレメントが選択されるため、ユーザの利便性を損なわずに地図データを更新することができる。
【０１２４】
＜第２の実施形態＞
図９は、本発明の第２の実施形態の地図データ配信システムの構成を示すブロック図である。
【０１２５】
第２の実施形態の地図データ配信システムは、次に挙げる相違点を除き、第１の実施形態と同様である。第１に、更新時間予測処理部が地図配信サーバ１０ではなくナビゲーション端末２０に含まれる。第２に、管理データ記憶部１１がナビ型番−更新時間係数対応テーブル５００を保持しない。第３に、管理データ記憶部１１がパーセルＩＤ−エレメント対応テーブル４００の更新時間４０３に相当する情報を保持しない。第４に、上記第１〜第３の相違点に対応するため、ナビゲーション端末２０の地図データを更新する手順が第１の実施形態と異なる。以下、これらの相違点について説明する。第２の実施形態のうち第１の実施形態と同様の部分についての説明は省略する。
【０１２６】
図１０は、本発明の第２の実施形態の地図配信サーバ１０が保持するパーセルＩＤ−エレメント対応テーブル１０００の説明図である。
【０１２７】
第２の実施形態の地図配信サーバ１０は、パーセルＩＤ−エレメント対応テーブル４００の代わりに、図１０に示すパーセルＩＤ−エレメント対応テーブル１０００を保持する。
【０１２８】
パーセルＩＤ−エレメント対応テーブル１０００は、パーセルＩＤ１００１、更新エレメントＩＤ１００２及びサイズ１００３を含む。これらは、それぞれ図４に示すパーセルＩＤ４０１、更新エレメントＩＤ４０２及びサイズ４０４と同様であるため、説明を省略する。
【０１２９】
なお、本実施形態のパーセルＩＤ−エレメント対応テーブル１０００は、従来の更新エレメントごとの地図データ配信を行う地図配信サーバが保持するものと同様であってよい。
【０１３０】
続いて、本実施形態の地図配信サーバ１０及びナビゲーション端末２０が実行する処理について説明する。
【０１３１】
本実施形態の地図配信サーバは、新しいバージョンの地図データを取得すると、それを地図データ記憶部１９に格納し、それに基づいて更新エレメントを作成する。これらの手順は、図７のＳ７０１及びＳ７０２を参照して説明した通りであり、従来の更新エレメントごとの地図データ配信を行う地図配信サーバが実行する手順と同じである。
【０１３２】
すなわち、本実施形態の地図配信サーバ１０は、従来の地図配信サーバと同じものであってもよい。
【０１３３】
図１１は、本発明の第２の実施形態の地図配信サーバ１０及びナビゲーション端末２０が実行する端末地図更新処理を示すフローチャートである。
【０１３４】
最初に、ナビゲーション端末２０の配信要求部２２は、地図データ配信要求を地図配信サーバ１０に送信する（Ｓ１１０１）。地図データ配信要求は、少なくとも、更新対象のパーセルの識別子、及び、現在保持している地図データのバージョン、を指定する情報を含む。この地図データ配信要求は、希望更新時間を含まないことを除いて、図８のＳ８０１で送信されるものと同じである。
【０１３５】
ナビゲーション端末２０から地図データ配信要求を受信した地図配信サーバ１０の更新データ管理部１５は、指定された更新対象のパーセルの識別子、及び地図データのバージョンに基づいて、ナビゲーション端末２０に送信する更新エレメントのリストを作成する（Ｓ１１０２）。具体的には、更新データ管理部１５は、更新対象として指定されたパーセルに対応する、まだナビゲーション端末に反映されていない更新エレメントを全てリストに登録する。この手順は、各更新エレメントの更新時間にかかわらず、上記の条件を満たす全ての更新エレメントが登録されることを除いて、図８のＳ８０２と同様である。
【０１３６】
次に、更新データ管理部１５は、Ｓ１１０２で作成したリスト（更新エレメントリスト）及び更新エレメントデータをナビゲーション端末２０に送信する（Ｓ１１０３）。このとき、更新データ管理部１５は、更新エレメントリストに登録された更新エレメントによって更新されるパーセルの識別子及びそれらの更新エレメントのサイズを示す情報を、更新エレメントデータ等に追加して送信する。これらの情報は、パーセルＩＤ−エレメント対応テーブル１０００から取得される。
【０１３７】
地図配信サーバ１０から更新エレメントデータ等を受信したナビゲーション端末２０の更新時間予測処理部１３は、更新エレメントリストに登録された更新エレメントのサイズ及びそれらによって更新されるパーセルの数に基づいて、各更新エレメントに基づく更新に要する時間（更新時間）を計算する。そして、更新時間予測処理部１３は、計算された更新時間の合計値が希望更新時間を超えないように、適用すべき更新エレメントを選択する（Ｓ１１０４）。
【０１３８】
Ｓ１１０４において行われる更新時間の計算は、図７のＳ７０３において実行されるものと同様である。例えば、式（１）によって更新時間が計算されてもよい。ただし、その場合、係数Ａ及びＢはＳ１１０４を実行するナビゲーション端末２０自体のハードウェア性能等に基づいて決定される。
【０１３９】
更新時間の計算に用いられる各更新エレメントのサイズ及び各更新エレメントが跨るパーセルの数は、Ｓ１１０３で送信された、更新エレメントによって更新されるパーセルの識別子及びそれらの更新エレメントのサイズから取得される。なお、これらの情報が地図配信サーバ１０から送信されなくても、更新時間予測処理部１３は、更新エレメントデータから同様の情報を抽出することができる。しかし、その抽出に要する時間を省略するために、地図配信サーバ１０がこれらの情報を送信することが望ましい。
【０１４０】
Ｓ１１０４において行われる更新エレメントの選択は、図８のＳ８０２において行われるものと同様であってよい。希望更新時間は、第１の実施形態と同様に決定される（Ｓ８０１参照）。
【０１４１】
次に、ナビゲーション端末２０の地図更新部２３は、Ｓ１１０４において選択された更新エレメントデータに基づいて、地図データ記憶部２７に格納されている地図データを更新する（Ｓ１１０５）。
【０１４２】
なお、上記の処理は一例であり、実際の更新に要する時間が希望更新時間を超えないように制御される限り、種々の処理が許容される。例えば、Ｓ１１０４及びＳ１１０５は次のように実行されてもよい。
【０１４３】
Ｓ１１０４において、更新時間予測処理部１３は、各更新エレメントの更新時間を計算する。そして、まだ地図データに反映されていない更新エレメントのいずれか一つを選択して、選択した更新エレメントの更新時間が希望更新時間の残り時間（後述）を超えるか否かを判定する。選択した更新エレメントの更新時間が残り時間を超えない場合、地図更新部２３が、選択した更新エレメントデータに基づいて地図データを更新する（Ｓ１１０５）。そして、処理は再びＳ１１０４に戻り、まだ地図データに反映されていない更新エレメントのいずれか一つが選択される。
【０１４４】
一方、選択した更新エレメントの更新時間が残り時間を超える場合、更新時間予測処理部１３は、まだ地図データに反映されていない別の更新エレメントを選択する。まだ地図データに反映されていないいずれの更新エレメントの更新時間も残り時間を超える場合、いずれの更新エレメントを選択しても希望更新時間内に更新を終了させることができないため、残りの更新エレメントに基づく更新を実行せずに、ナビゲーション端末２０は端末地図更新処理を終了する。
【０１４５】
なお、Ｓ１１０４において残り時間が０以下になった場合、まだ地図データに反映されていないいずれの更新エレメントの更新時間も残り時間を超えるため、その時点でナビゲーション端末２０は端末地図更新処理を終了する。
【０１４６】
なお、希望更新時間の残り時間とは、更新希望時間から、地図データの更新が開始されてから現在までの時間を減じた残り、すなわち、更新時間から、既に選択された更新エレメントに基づく更新に実際に要した時間の合計値を減じた残りである。
【０１４７】
上記のような残り時間に基づく更新の制御は、第１の実施形態のＳ８０４（図８）において実行されてもよい。
【０１４８】
以上の本発明の第２の実施形態によれば、従来と同じ地図配信サーバを用いて、第１の実施形態と同様、更新後の地図データに矛盾が生じず、かつ、ユーザの利便性を損なわないように地図データを更新することができる。
【符号の説明】
【０１４９】
１０  地図配信サーバ
１１、２６  管理データ記憶部
１２  更新データ記憶部
１３  更新時間予測処理部
１４  更新データ抽出部
１５  更新データ管理部
１６、２８  プロセッサ
１７、２９  メモリ
１８、２１  ネットワークインターフェース（Ｉ／Ｆ）
１９、２７  地図データ記憶部
２０  ナビゲーション端末
２２  配信要求部
２３  地図更新部
２４  ナビゲーション処理部
２５  画面入出力Ｉ／Ｆ
３０  無線通信装置
３１  無線基地局
４０  ネットワーク
４１  インターネット
【図１】
0005662729.tif 000002
【図２】
0005662729.tif 000003
【図３】
0005662729.tif 000004
【図４】
0005662729.tif 000005
【図５】
0005662729.tif 000006
【図６】
0005662729.tif 000007
【図７】
0005662729.tif 000008
【図８】
0005662729.tif 000009
【図９】
0005662729.tif 000010
【図１０】
0005662729.tif 000011
【図１１】
0005662729.tif 000012