(57)【要約】【課題】車両用ナビゲーション装置に備えられた地図記憶装置の地図データ記憶領域の残容量を有効に活用することができる地図差分データ配信装置を提供する。【解決手段】ナビゲーション装置３のナビ側記憶装置３４の地図データ記憶領域の残容量が少なくなり、次回の配信に対する配信計画に含まれている差分グループを全部は配信できないと判断した場合（Ｓ１３：ＮＯ）、残容量を超えない範囲でデータ量が最大のレコードの組み合わせを、配信する組み合わせに決定する（Ｓ２２）。これにより、ナビ側記憶装置３４の地図データ記憶領域に、より多くの差分グループを記憶することができる。【選択図】図１０
2014209073.tif 000002
【特許請求の範囲】
【請求項１】
車両用ナビゲーション装置（３）に備えられた地図記憶装置（３４）の地図データ記憶領域に基準となる全体地図である元地図データとともに記憶される、前記元地図データに含まれていない更新部分の地図データである複数の差分データを、予め定められた規則によりまとめた差分グループデータとして、前記車両用ナビゲーション装置に配信するために複数記憶しており、且つ、それら複数の差分グループデータのうち、依存先差分グループデータが更新されないとその依存先差分グループデータに依存する差分グループデータと他の地図要素との間で不整合が生じてしまう関係である依存関係を記述した依存リストを記憶しており、且つ、それら差分グループデータおよび依存リストが、所定の差分更新周期が経過する毎に更新される差分データ記憶部（１２）と、
複数の前記車両用ナビゲーション装置からそれぞれ座標情報と前記ナビゲーション装置を特定する装置特定情報を取得して、前記差分データ記憶部に記憶されている差分グループデータのうち、前記装置特定情報を取得した前記車両用ナビゲーション装置に未配信であって、且つ、前記座標情報に基づいて定まる範囲に含まれる差分グループデータ、および、その差分グループデータと前記依存リストに基づいて定まる依存先差分グループデータを、前記装置特定情報を取得した前記車両用ナビゲーション装置に配信する配信処理部（１３）と、
前記差分データ記憶部に記憶された差分グループデータのうち、未配信の差分グループデータであって、且つ、前記車両用ナビゲーション装置のユーザの居所と、前記未配信の差分グループデータごとに定まるデータ基準点との距離に基づいて、その未配信の差分グループデータが、前記配信処理部の処理により配信されるか否かを予測し、さらに、前記距離に基づいて配信されると予測した差分グループデータと前記依存リストから、配信される依存先差分グループデータも予測して、それら差分グループデータと依存先差分グループデータの合計データ量である予測配信データ量を、前記差分更新周期により定まる次回の配信期間に対して予測する予測部（２３１  Ｓ１２）と、
前記地図データ記憶領域の現時点での残容量を決定する残容量決定部（２３３  Ｓ１１）と、
前記予測部が予測した前記予測配信データ量と、前記残容量決定部が決定した前記残容量とから、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあるか否かを判定する容量オーバー判定部（２３２ａ  Ｓ１３、Ｓ１５）とを備え、
前記配信処理部は、前記容量オーバー判定部が、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあると判定したことに基づいて、前記残容量決定部が決定した残容量を超えないデータ量としつつ、残容量を活用するために予め定められた規則に基づいて、次回の前記配信期間に配信するデータを、前記差分データ記憶部に記憶されている差分グループデータのうちの一部に限定することを特徴とする地図差分データ配信装置（１００）。
【請求項２】
請求項１において、
前記配信処理部は、
前記容量オーバー判定部が、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあると判定したことに基づいて、前記差分グループデータ、および、その差分グループデータと前記依存リストに基づいて定まる依存先差分グループデータを配信単位としてまとめたレコードのうち、前記車両用ナビゲーション装置に未配信の全てのレコードを対象として、前記残容量決定部が決定した残容量を超えない組み合わせを全て設定し、設定した組み合わせの中でデータ量が最大となったレコードの組み合わせを、次回の前記配信期間に配信するデータとする第１限定部（１３１）を備えることを特徴とする地図差分データ配信装置。
【請求項３】
請求項２において、
前記配信処理部は、
前記第１限定部で限定したデータを全て配信したとした場合の前記地図データ記憶領域の残容量である限定後残容量を算出し、前記第１限定部で除外した未配信の前記レコードを構成する前記差分データを、その差分データのカテゴリおよびサブカテゴリの少なくとも一方に対して設定された優先度に基づいて並べ替えて、優先度の高い側から順に、前記限定後残容量を超えない範囲で最大数の前記差分データも、次回の前記配信期間に配信するデータとする第２限定部（１３２）を備えることを特徴とする地図差分データ配信装置。
【請求項４】
請求項１において、
前記配信処理部は、
前記容量オーバー判定部が、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあると判定したことに基づいて、
前記差分グループデータ、および、その差分グループデータと前記依存リストに基づいて定まる依存先差分グループデータを配信単位としてまとめたレコードのうち、未配信のレコードを構成する前記差分データを、その差分データのカテゴリおよびサブカテゴリの少なくとも一方に対して設定された優先度に基づいて並べ替えて、優先度の高い側から順に、前記残容量決定部が決定した前記残容量を超えない範囲で最大数の前記差分データを、次回の前記配信期間に配信するデータとすることを特徴とする地図差分データ配信装置。
【請求項５】
車両用ナビゲーション装置（３）に備えられた地図記憶装置（３４）の地図データ記憶領域に基準となる全体地図である元地図データとともに記憶される、前記元地図データに含まれていない更新部分の地図データである複数の差分データを、予め定められた規則によりまとめた差分グループデータとして、前記車両用ナビゲーション装置に配信するために複数記憶しており、且つ、それら複数の差分グループデータのうち、依存先差分グループデータが更新されないとその依存先差分グループデータに依存する差分グループデータと他の地図要素との間で不整合が生じてしまう関係である依存関係を記述した依存リストを記憶しており、且つ、それら差分グループデータおよび依存リストが、所定の差分更新周期が経過する毎に更新される差分データ記憶部（１２）と、
複数の前記車両用ナビゲーション装置からそれぞれ座標情報と前記ナビゲーション装置を特定する装置特定情報を取得して、前記差分データ記憶部に記憶されている差分グループデータのうち、前記装置特定情報を取得した前記車両用ナビゲーション装置に未配信であって、且つ、前記座標情報に基づいて定まる範囲に含まれる差分グループデータ、および、その差分グループデータと前記依存リストに基づいて定まる依存先差分グループデータを、前記装置特定情報を取得した前記車両用ナビゲーション装置に配信する配信処理部（１３）と、を備えた地図差分データ配信システムを用いる地図差分データ配信方法であって、
前記差分データ記憶部に記憶された差分グループデータのうち、未配信の差分グループデータであって、且つ、前記車両用ナビゲーション装置のユーザの居所と、前記未配信の差分グループデータごとに定まるデータ基準点との距離に基づいて、その未配信の差分グループデータが、前記配信処理部の処理により配信されるか否かを予測し、さらに、前記距離に基づいて配信されると予測した差分グループデータと前記依存リストから、配信される依存先差分グループデータも予測して、それら差分グループデータと依存先差分グループデータの合計データ量である予測配信データ量を、前記差分更新周期により定まる次回の配信期間に対して予測する予測工程（Ｓ１２）と、
前記地図データ記憶領域の現時点での残容量を決定する残容量決定工程（Ｓ１１）と、
前記予測工程で予測した前記予測配信データ量と、前記残容量決定工程で決定した前記残容量とから、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあるか否かを判定する容量オーバー判定工程（Ｓ１３、Ｓ１５）と、
前記容量オーバー判定工程において、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあると判定したことに基づいて、前記残容量決定工程で決定した残容量を超えないデータ量としつつ、残容量を活用するために予め定められた規則に基づいて、次回の前記配信期間に配信するデータを、前記差分データ記憶部に記憶されている差分グループデータのうちの一部に予め限定する配信処理工程（Ｓ２１−Ｓ２６）と、を備えることを特徴とする地図差分データ配信方法。
【請求項６】
基準となる全体地図である元地図データを地図データ記憶領域に記憶している地図記憶装置（３４）と、
前記元地図データに含まれていない更新部分の地図データであって前記元地図データとともに前記地図記憶装置の地図データ記憶領域に記憶される差分データを地図差分データ配信装置から受信して、その受信した差分データを前記地図データ記憶領域に格納する更新処理部（４１）と、
を備えた車両用ナビゲーション装置（３）であって、
前記地図差分データ配信装置が配信するために差分データ記憶部に記憶している差分グループデータのうち、次回の配信期間にこの車両用ナビゲーション装置に配信される差分グループデータの合計データ量である予測配信データ量を予測する予測部（２３１  Ｓ１２）と、
前記地図データ記憶領域の現時点での残容量を決定する残容量決定部（２３３  Ｓ１１）と、
前記予測部が予測した前記予測配信データ量と、前記残容量決定部が決定した前記残容量とから、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあるか否かを判定する容量オーバー判定部（２３２ａ  Ｓ１３、Ｓ１５）とを備え、
前記更新処理部は、前記容量オーバー判定部が、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあると判定したことに基づいて、前記残容量決定部が決定した残容量を超えないデータ量としつつ、残容量を活用するために予め定められた規則に基づいて、次回の前記配信期間に格納するデータを、前記差分データ記憶部に記憶されている差分グループデータのうちの一部に限定することを特徴とするナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車両用ナビゲーション装置において使用される地図記憶装置に、差分データを配信する地図差分データ配信装置、地図差分データ配信方法、車両用ナビゲーション装置に関する。
【背景技術】
【０００２】
新しく作られた道路に対応して、地図データの一部分を更新する技術が知られている（たとえば特許文献１）。特許文献１では、地図データは、車両用ナビゲーション装置が備える記憶装置に記憶されている。そして、地図作成会社において逐次作成された更新分の地図データが無線で車両用ナビゲーション装置に配信される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第４６８２０８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、車両用ナビゲーション装置の記憶装置に最初から記憶されている地図データ（以下、元地図データ）が備えていない更新部分の地図データ（以下、差分データ）を配信する際には、いくつかの差分データを一つのデータにまとめて配信することが考えられる。以下では、いくつかの差分データをまとめたデータを差分グループデータという。
【０００５】
差分グループデータにまとめる一つの理由としては、道路とその道路に面する施設を考えたときに、その施設に対応する施設データのみを配信してしまうと、道路のないところに施設が存在することになってしまうなど、現実にはありえない状態を地図データが示すことになってしまうからという理由がある。そこで、差分グループデータとして、道路データとその道路データが示す道路に面する施設のデータとを一つの差分グループデータにまとめることが考えられる。
【０００６】
また、独立した１つ１つのデータにはヘッダデータなどの付随データが必要となるため、あまりにデータを細分化してしまうと、通信データ量が多くなってしまう。これを回避するために、データをグループにまとめるという理由もある。
【０００７】
また、車両用ナビゲーション装置に差分グループデータを全部は配信できない場合がある。たとえば、差分グループデータを全部配信しようとすると、通信量が膨大になってしまうという理由や、車両用ナビゲーション装置の記憶装置に、差分グループデータを全部記憶するほどの残容量がない場合、差分グループデータを全部は配信できない。
【０００８】
特に、差分グループデータを車両用ナビゲーション装置が取得しても、その差分グループデータにより元地図データを更新せず、両データを併存して記憶する場合には、残容量の問題で差分グループデータを全部は配信できない可能性が高くなる。
【０００９】
たとえば、新しく地図を作成した場合にはその新しい地図について行政機関の認可を得なければならないという法制度を有する国では、地図データを更新した場合、地図データの更新が新しい地図を作成することに該当し、更新した地図データについて行政機関の認可を得なければならない。しかし、差分データにより元地図データを更新するたびに行政機関の認可を得ることは不可能である。そのため、差分データにより元地図データを更新せずに、差分データをそのまま記憶することになる。これは差分データをそのまま記憶する理由の一例である。
【００１０】
差分グループデータを車両用ナビゲーション装置に全部は配信できない場合、差分グループデータから一部を選択して車両用ナビゲーション装置に配信しなければならない。そこで、たとえば、車両用ナビゲーション装置から現在地などの座標を示す座標情報を取得して、その座標に基づいて定まる範囲に含まれている差分グループデータであって、その車両用ナビゲーション装置に未配信の差分グループデータを選択して配信することが考えられる。
【００１１】
このように全部の差分グループデータのうちの一部を配信する場合には、次に配信する差分グループデータを配信することにより、ベース地図データと差分グループデータとを合わせた地図データ（以下、単に地図データということもある）に不整合が生じないようにすべきである。地図データに生じる不整合の代表例は、ある地図要素が他の地図要素から孤立することである。たとえば、互いに連続する道路が順次開通していく場合に、先に開通した区間の道路データ（第１道路データとする）を配信せずに、後に開通した区間の道路データ（第２道路データとする）だけを配信してしまうと、第２道路データが示す区間は、他の道路から孤立してしまう。
【００１２】
孤立以外の不整合の例として、ある場所で、ある画像（すなわち地図要素）を表示するという案内を行う場合にも、その案内を行うデータである案内データは、上記画像のデータが存在しないと案内ができないという不整合が生じる。
【００１３】
この不整合を避けるために、配信する差分グループの依存関係を定めておくことが考えられる。上記の例では、第２道路データは第１道路データに依存することを定めておくことになる。この依存関係を記述した依存リストを参照して、配信する差分グループを決定すれば、地図データの不整合を避けることができる。依存リストを利用して配信する差分グループデータを決定する場合、新しい差分グループデータを作成する都度、依存リストを更新することになる。
【００１４】
しかし、依存リストを参照しつつ、車両用ナビゲーション装置から取得した座標情報に基づいて定まる範囲に含まれており且つ未配信であれば、差分グループデータを配信してしまうとすると、次のような問題が生じる恐れがある。
【００１５】
すなわち、あまり重要でないデータを配信してしまって、より重要な差分グループデータが容量オーバーにより配信できないなど、車両用ナビゲーション装置の記憶装置の残容量を有効に活用できないという問題が生じる。
【００１６】
また、車両用ナビゲーション装置にとっては、あまり重要でないデータを格納してしまって、より重要な差分グループデータが容量オーバーにより格納できないなど、車両用ナビゲーション装置の記憶装置の残容量を有効に活用できないという問題が生じる。
【００１７】
本発明は、この事情に基づいて成されたものであり、その目的とするところは、車両用ナビゲーション装置に備えられた地図記憶装置の地図データ記憶領域の残容量を有効に活用することができる地図差分データ配信装置、地図差分データ配信方法、自身に備えられた地図記憶装置の地図データ記憶領域の残容量を有効に活用することができる車両用ナビゲーション装置を提供することにある。
【課題を解決するための手段】
【００１８】
その目的を達成するための第１発明は、車両用ナビゲーション装置（３）に備えられた地図記憶装置（３４）の地図データ記憶領域に基準となる全体地図である元地図データとともに記憶される、前記元地図データに含まれていない更新部分の地図データである複数の差分データを、予め定められた規則によりまとめた差分グループデータとして、前記車両用ナビゲーション装置に配信するために複数記憶しており、且つ、それら複数の差分グループデータのうち、依存先差分グループデータが更新されないとその依存先差分グループデータに依存する差分グループデータと他の地図要素との間で不整合が生じてしまう関係である依存関係を記述した依存リストを記憶しており、且つ、それら差分グループデータおよび依存リストが、所定の差分更新周期が経過する毎に更新される差分データ記憶部（１２）と、
複数の前記車両用ナビゲーション装置からそれぞれ座標情報と前記ナビゲーション装置を特定する装置特定情報を取得して、前記差分データ記憶部に記憶されている差分グループデータのうち、前記装置特定情報を取得した前記車両用ナビゲーション装置に未配信であって、且つ、前記座標情報に基づいて定まる範囲に含まれる差分グループデータ、および、その差分グループデータと前記依存リストに基づいて定まる依存先差分グループデータを、前記装置特定情報を取得した前記車両用ナビゲーション装置に配信する配信処理部（１３）と、
前記差分データ記憶部に記憶された差分グループデータのうち、未配信の差分グループデータであって、且つ、前記車両用ナビゲーション装置のユーザの居所と、前記未配信の差分グループデータごとに定まるデータ基準点との距離に基づいて、その未配信の差分グループデータが、前記配信処理部の処理により配信されるか否かを予測し、さらに、前記距離に基づいて配信されると予測した差分グループデータと前記依存リストから、配信される依存先差分グループデータも予測して、それら差分グループデータと依存先差分グループデータの合計データ量である予測配信データ量を、前記差分更新周期により定まる次回の配信期間に対して予測する予測部（２３１  Ｓ１２）と、
前記地図データ記憶領域の現時点での残容量を決定する残容量決定部（２３３  Ｓ１１）と、
前記予測部が予測した前記予測配信データ量と、前記残容量決定部が決定した前記残容量とから、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあるか否かを判定する容量オーバー判定部（２３２ａ  Ｓ１３、Ｓ１５）とを備え、
前記配信処理部は、前記容量オーバー判定部が、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあると判定したことに基づいて、前記残容量決定部が決定した残容量を超えないデータ量としつつ、残容量を活用するために予め定められた規則に基づいて、次回の前記配信期間に配信するデータを、前記差分データ記憶部に記憶されている差分グループデータのうちの一部に予め限定することを特徴とする。
【００１９】
また、第２発明は、車両用ナビゲーション装置（３）に備えられた地図記憶装置（３４）の地図データ記憶領域に基準となる全体地図である元地図データとともに記憶される、前記元地図データに含まれていない更新部分の地図データである複数の差分データを、予め定められた規則によりまとめた差分グループデータとして、前記車両用ナビゲーション装置に配信するために複数記憶しており、且つ、それら複数の差分グループデータのうち、依存先差分グループデータが更新されないとその依存先差分グループデータに依存する差分グループデータと他の地図要素との間で不整合が生じてしまう関係である依存関係を記述した依存リストを記憶しており、且つ、それら差分グループデータおよび依存リストが、所定の差分更新周期が経過する毎に更新される差分データ記憶部（１２）と、
複数の前記車両用ナビゲーション装置からそれぞれ座標情報と前記ナビゲーション装置を特定する装置特定情報を取得して、前記差分データ記憶部に記憶されている差分グループデータのうち、前記装置特定情報を取得した前記車両用ナビゲーション装置に未配信であって、且つ、前記座標情報に基づいて定まる範囲に含まれる差分グループデータ、および、その差分グループデータと前記依存リストに基づいて定まる依存先差分グループデータを、前記装置特定情報を取得した前記車両用ナビゲーション装置に配信する配信処理部（１３）と、を備えた地図差分データ配信システムを用いる地図差分データ配信方法であって、
前記差分データ記憶部に記憶された差分グループデータのうち、未配信の差分グループデータであって、且つ、前記車両用ナビゲーション装置のユーザの居所と、前記未配信の差分グループデータごとに定まるデータ基準点との距離に基づいて、その未配信の差分グループデータが、前記配信処理部の処理により配信されるか否かを予測し、さらに、前記距離に基づいて配信されると予測した差分グループデータと前記依存リストから、配信される依存先差分グループデータも予測して、それら差分グループデータと依存先差分グループデータの合計データ量である予測配信データ量を、前記差分更新周期により定まる次回の配信期間に対して予測する予測工程（Ｓ１２）と、
前記地図データ記憶領域の現時点での残容量を決定する残容量決定工程（Ｓ１１）と、
前記予測工程で予測した前記予測配信データ量と、前記残容量決定工程で決定した前記残容量とから、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあるか否かを判定する容量オーバー判定工程（Ｓ１３、Ｓ１５）と、
前記容量オーバー判定工程において、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあると判定したことに基づいて、前記残容量決定工程で決定した残容量を超えないデータ量としつつ、残容量を活用するために予め定められた規則に基づいて、次回の前記配信期間に配信するデータを、前記差分データ記憶部に記憶されている差分グループデータのうちの一部に予め限定する配信処理工程（Ｓ２１−Ｓ２６）と、を備えることを特徴とする。
【００２０】
これら第１発明、第２発明では、残容量を活用するために予め定められた規則に基づいて、差分データ記憶部に記憶されている差分グループデータのうちの一部に、配信するデータを予め限定している。そのため、車両用ナビゲーション装置から取得した座標情報に基づいて定まる範囲に含まれており且つ未配信であれば、差分グループデータを配信してしまう場合に比較して、残容量を有効に活用できる差分データを配信することができる。
【００２１】
第３発明は、基準となる全体地図である元地図データを地図データ記憶領域に記憶している地図記憶装置（３４）と、前記元地図データに含まれていない更新部分の地図データであって前記元地図データとともに前記地図記憶装置の地図データ記憶領域に記憶される差分データを地図差分データ配信装置から受信して、その受信した差分データを前記地図データ記憶領域に格納する更新処理部（４１）と、を備えた車両用ナビゲーション装置（３）であって、
前記地図差分データ配信装置が配信するために差分データ記憶部に記憶している差分グループデータのうち、次回の配信期間にこの車両用ナビゲーション装置に配信される差分グループデータの合計データ量である予測配信データ量を予測する予測部（２３１  Ｓ１２）と、前記地図データ記憶領域の現時点での残容量を決定する残容量決定部（２３３  Ｓ１１）と、前記予測部が予測した前記予測配信データ量と、前記残容量決定部が決定した前記残容量とから、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあるか否かを判定する容量オーバー判定部（２３２ａ  Ｓ１３、Ｓ１５）とを備え、
前記更新処理部は、前記容量オーバー判定部が、次回の前記配信期間に前記地図データ記憶領域の容量オーバーが生じる恐れがあると判定したことに基づいて、前記残容量決定部が決定した残容量を超えないデータ量としつつ、残容量を活用するために予め定められた規則に基づいて、次回の前記配信期間に格納するデータを、前記差分データ記憶部に記憶されている差分グループデータのうちの一部に限定することを特徴とする。
【００２２】
第３発明の車両用ナビゲーション装置は、残容量を活用するために予め定められた規則に基づいて、地図記憶装置の地図データ記憶領域に格納するデータを、地図差分データ配信装置が配信するために差分データ記憶部に記憶している差分グループデータのうちの一部に限定している。そのため、残容量を有効に活用できる差分データを格納することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明が適用された地図差分データ配信システム１００の概略的な構成の一例を示す図である。
【図２】地図要素のカテゴリおよびサブカテゴリを例示する図である。
【図３】依存関係を具体的に説明する図である。
【図４】予測部２３１が行う処理の一部を示す図である。
【図５】図４のステップＳ２で作成する長期予測配信データ量のグラフである。
【図６】配信データが配信される処理の流れを示すシーケンス図である。
【図７】予測部２３１が行う処理の一部を示す図である。
【図８】図７のステップＳ１２の処理の詳細を示すフローチャートである。
【図９】次々回以降の配信データ量予測を修正する処理を示すフローチャートである。
【図１０】図７のステップＳ１３がＮＯとなった場合に実行する処理を示すフローチャートである。
【図１１】依存リストの例である。
【図１２】処理時間判定処理を説明するフローチャートである。
【図１３】第２実施形態における抽出サーバ側制御部１３の機能を示すブロック図である。
【図１４】図１０の処理に代えて実行する処理を示すフローチャートである。
【図１５】一つの差分グループを概念的に説明する図である。
【図１６】カテゴリおよびサブカテゴリの優先度を定義したリストの例である。
【図１７】図１０、１３の処理に代えて実行する処理を示すフローチャートである。
【発明を実施するための形態】
【００２４】
以下、本発明の実施形態１について図面を用いて説明する。
【００２５】
＜地図差分データ配信システム１００＞
図１は、本発明が適用された地図差分データ配信システム１００の概略的な構成の一例を示す図である。図１に示す地図差分データ配信システム１００は、地図差分抽出サーバ１、更新管理サーバ２を備えた構成であり、地図差分データ配信システム１００は車両用ナビゲーション装置３（以下、単にナビゲーション装置３）に差分データを配信する。
【００２６】
＜地図差分抽出サーバ１＞
図１に示すように、地図差分抽出サーバ１は、抽出サーバ側通信部１１、地図差分データベース（ＤＢ）１２、および抽出サーバ側制御部１３を備える。なお、データベースはデータが所定の形式で配列された無体情報を意味することもあるが、図１では、データベースは無体情報であるデータベースおよびそれを記憶する記憶装置を含めた意味である。しかし、以降の説明では、装置構成図および特に説明する場合を除き、データベースは記憶装置に記憶されている無体情報を指す。
【００２７】
抽出サーバ側通信部１１は、通信網を介して、更新管理サーバ２やナビゲーション装置３との間で通信を行う。
【００２８】
地図差分ＤＢ１２は、地図差分データを格納するデータベースである。地図差分データは、ベース地図データから更新する必要が生じた地図要素のデータである。ベース地図データは、請求項の元地図データに相当し、この地図差分データ配信システム１００が適用される国の国土全体など、予め決定されている全範囲に対する地図（すなわち全体地図）のデータである。
【００２９】
上記地図要素は、例えば道路、ＰＯＩ（Points Of Interest）、背景、地名等を示す文字などであり、これらの地図要素のデータは、例えばノードデータおよびリンクデータからなる道路データ、地形等を示す背景データ、地名等を表示するための文字データ、各種施設のＰＯＩデータ等である。
【００３０】
よって、ベース地図が作成された後に道路、ＰＯＩの追加変更などが生じた場合に、地図差分データとして、道路データ、ＰＯＩデータなどが作成されることになる。地図差分データは、たとえば、図示しない外部サーバからこの地図差分抽出サーバに提供される。なお、地図差分データは最小単位差分にまとめられる。最小単位差分にまとめられた地図差分データを差分グループデータといい、差分グループデータにまとめられた地図差分データのそれぞれに対応する地図要素のまとまりを差分グループという。差分グループデータの詳細は後述する。
【００３１】
抽出サーバ側制御部１３は、ＣＰＵ、ＲＯＭ、ＲＡＭ、バックアップＲＡＭ、Ｉ／Ｏ等（いずれも図示せず）よりなるマイクロコンピュータを主体として構成される。この抽出サーバ側制御部１３は、抽出サーバ側通信部１１から入力された各種情報に基づき、ＲＯＭに記憶された各種の制御プログラムを実行することで、後述する図６の処理を実行する。その図６の処理により抽出サーバ側制御部１３は配信処理部として機能する。
【００３２】
＜更新管理サーバ２＞
更新管理サーバ２は、管理サーバ側通信部２１、更新管理ＤＢ２２、管理サーバ側制御部２３を備える。管理サーバ側通信部２１は、通信網を介して、地図差分抽出サーバ１やナビゲーション装置３との間で通信を行う。
【００３３】
更新管理ＤＢ２２は、地図差分抽出サーバ１からナビゲーション装置３に配信済みの地図差分データを判別するための判別用情報を格納しており、複数のナビゲーション装置３が存在する場合に、各ナビゲーション装置３のユーザごとに判別用情報を格納する。判別用情報は、例えばナビゲーション装置３に配信済みの差分グループＩＤである。差分グループＩＤは、差分グループのそれぞれに付与されるＩＤである。また、更新管理ＤＢ２２には、差分グループ間の依存関係を示した依存リストも格納される。差分グループの内容および依存リストについては後述する。
【００３４】
更新管理ＤＢ２２には、さらに、ナビゲーション装置３を特定するＩＤと、そのナビゲーション装置３に対応する居所情報を格納している。ナビゲーション装置３を特定するＩＤは、そのナビゲーション装置３のＩＤ（以下、ナビＩＤ）でも良いし、ナビゲーション装置３が車両に固定される形式であれば車両ＩＤでもよいが、以下では、ナビＩＤを格納しているものとする。ナビＩＤや車両ＩＤは装置特定情報に相当する。
【００３５】
居所情報は、ナビゲーション装置３ごとに設定され、たとえば、ナビゲーション装置３を使用するユーザの住所、あるいは、ナビゲーション装置３が用いられる車両の登録地点である。この居所情報は、ユーザがナビゲーション装置３を購入する時（車載のナビゲーション装置３であれば、車両購入時）にユーザから得る。さらに、更新管理ＤＢ２２には、ナビＩＤと対応させて、ベース地図のバージョンも格納される。
【００３６】
管理サーバ側制御部２３は、ＣＰＵ、ＲＯＭ、ＲＡＭ、バックアップＲＡＭ、Ｉ／Ｏ等（いずれも図示せず）よりなるマイクロコンピュータを主体として構成される。この管理サーバ側制御部２３は、管理サーバ側通信部２１、更新管理ＤＢ２２から入力された各種情報に基づき、ＲＯＭに記憶された各種の制御プログラムを実行することで、図１に示す予測部２３１、機能低下判定部２３２、残容量決定部２３３として機能する。また、機能低下判定部２３２は、容量オーバー判定部２３２ａ、処理時間判定部２３２ｂからなる。管理サーバ側制御部２３での処理の詳細については後述する。なお、更新管理サーバ２と地図差分抽出サーバ１とは通信網で接続されており、互いにデータの送受信が可能である。そして、管理サーバ側制御部２３の各部２３１、２３２、２３３は、必要なデータが取得できれば他のコンピュータが実行することも可能である。従って、管理サーバ側制御部２３の機能の一部または全部を、地図差分抽出サーバ１の抽出サーバ側制御部１３が実行してもよい。また、ナビゲーション装置３も通信網で更新管理サーバ２、地図差分抽出サーバ１と接続されているので、それらの機能の一部をナビゲーション装置３の制御装置４１が実行してもよい。
【００３７】
＜ナビゲーション装置３＞
ナビゲーション装置３は、車載のナビゲーション装置であってもよいし、車両に持ち込み可能な携帯型のナビゲーション装置であってもよい。以降では、ナビゲーション装置３として車載のナビゲーション装置を用いた場合を例に挙げて説明を行う。
【００３８】
まず、ナビゲーション装置３の概略的な構成について説明を行う。図１に示すようにナビゲーション装置３は、通信装置３１、位置検出器３２、外部入力インターフェース（Ｉ／Ｆ）部３３、ナビ側記憶装置３４、表示装置３６、音声出力装置３７、操作スイッチ群３８、リモートコントロール端末（以下リモコン）３９、リモコンセンサ４０、および制御装置４１を備えている。
【００３９】
通信装置３１は、通信網を介して、地図差分抽出サーバ１や更新管理サーバ２との間で通信を行う。通信装置３１としては、例えばテレマティクス通信に用いられるＤＣＭ（data communication module）といった車載通信モジュールなどの様々なものを採用することができる。
【００４０】
位置検出器３２は、いずれも周知の加速度センサ、ジャイロスコープ、および衛星からの電波に基づいて自装置の位置を検出するＧＰＳ（Global Positioning System）等の衛星測位システムのための受信機を有しており、自装置のユーザの現在位置（以下、ユーザ位置）を逐次検出する。例えば、ユーザ位置は、緯度・経度で表される座標であるものとする。なお、位置検出器３２を上述したセンサのうちの一部で構成してもよいし、他のセンサを用いる構成としてもよい。
【００４１】
外部入力Ｉ／Ｆ部３３は、車両に搭載されたＥＣＵやセンサから、車両状態の情報を制御装置４１が取得するためのインターフェースである。例えば、外部入力Ｉ／Ｆ部３３には、車載ＬＡＮ等を介して車両に搭載されたＥＣＵやセンサから車両状態の情報が入力されてくるものとする。車両状態の情報の一例としては、アクセサリ（ＡＣＣ）電源のオンオフの信号等がある。
【００４２】
ナビ側記憶装置３４は、本実施形態では、ＳＤカードおよびそのＳＤカードを収容するインターフェースからなる。もちろん、ＳＤカードに代えて、その他の書き換え可能な記憶媒体を用いてもよい。このナビ側記憶装置３４には地図データ記憶領域が設定されている。地図データ記憶領域はたとえばパーティションにより設定されている。
【００４３】
この地図データ記憶領域に、前述のベース地図データ、地図差分データなどが記憶される。ベース地図データは出荷時に予め地図データ記憶領域に記憶されている。一方、地図差分データは、逐次、外部から取得して記憶する。
【００４４】
表示装置３６は、例えばフルカラー表示が可能なものであり、液晶ディスプレイ、有機ＥＬディスプレイ等を用いて構成することができる。また、音声出力装置３７は、スピーカ等から構成され、制御装置４１の指示に基づいて案内音声等を出力する。
【００４５】
操作スイッチ群３８は、例えば表示装置３６と一体になったタッチスイッチ若しくはメカニカルなスイッチ等が用いられ、スイッチ操作により制御装置４１へ各種機能の操作指示を行う。リモコン３９には複数の操作スイッチ（図示せず）が設けられ、スイッチ操作によりリモコンセンサ４０を介して各種指令信号を制御装置４１に入力することにより、操作スイッチ群３８と同じ機能を制御装置４１に対して実行させることが可能である。
【００４６】
制御装置４１は、ＣＰＵ、ＲＯＭ、ＲＡＭ、バックアップＲＡＭ等よりなるマイクロコンピュータを主体として構成される。そして、制御装置４１は、通信装置３１、位置検出器３２、外部入力Ｉ／Ｆ３３、ナビ側記憶装置３４、操作スイッチ群３８、リモコンセンサ３９から入力された各種情報に基づき、各種処理を実行する。制御装置４１での処理の詳細については後述する。
【００４７】
＜差分グループデータの説明＞
次に、差分グループデータについて説明する。差分グループデータは複数の地図差分データを含む。各地図差分データは、道路や施設などの地図要素が更新されたことに基づいて作成される。地図要素の更新は、たとえば、道路の開通や閉鎖、施設の追加や削除などによって生じる。
【００４８】
差分グループデータは、地図データを複数に分割した区画（以下、メッシュという）を示すメッシュＩＤと対応づけられており、これにより、差分グループデータはメッシュ単位で管理される。差分グループデータには、その差分グループデータを特定するＩＤ（以下、差分グループＩＤ）が付与されている。なお、メッシュには複数の大きさが定義されており、相対的に大きなメッシュは、それよりも小さな複数のメッシュからなる。本実施形態において用いるメッシュの大きさは、それら複数の大きさのうちの最も小さい大きさのメッシュとする。ただし、より大きいメッシュとすることもできる。
【００４９】
差分グループデータは、例えば更新された地図要素が交差点を挟んだ道路区間だった場合、道路区間を表すリンクデータおよびノードデータの集合になる。他の例として、更新された地図要素が施設であった場合には、施設を表すＰＯＩデータや文字データなどの集合になる。
【００５０】
差分グループは、地図要素のカテゴリおよびサブカテゴリに基づいて形成される。図２は、地図要素のカテゴリおよびサブカテゴリを例示する図である。どのカテゴリ（あるいはサブカテゴリ）と、どのカテゴリ（あるいはサブカテゴリ）を同一のグループとするかは予め設定されている。一例としては、ある道路を示すリンクと、そのリンクの周囲にある背景は同一の差分グループとする、などの規則が決められている。差分グループは原則としてこの規則に基づいて形成される。
【００５１】
＜依存リストの説明＞
次に、依存リストを説明する。依存リストは、差分グループ間の依存関係を示したリストである。依存関係とは、差分グループＡを更新する場合に予め差分グループＢを更新しておかなければ、ベース地図データと差分グループデータとを合わせた地図データ（以下、単に地図データということもある）において、差分グループＡと他の地図要素との間で不整合が生じてしまう関係をいう。地図データに生じる不整合の代表例は、ある地図要素が他の地図要素から孤立することである。孤立とは、たとえばその地図要素が道路であれば、その道路が他の道路と接続していないことを意味する。差分グループＢが更新されないことにより差分グループＡが他の地図要素から孤立してしまう関係にある場合、差分データＡと差分データＢは互いに依存関係にある。より詳しくは、差分グループＡは差分グループＢを依存先とし、差分グループＢは差分グループＡに依存される（被依存）関係にある。この依存関係は、差分グループを構成する地図要素として道路を含んでいる差分グループ同士に対して主として設定される。
【００５２】
図３を用いて依存関係を具体的に説明する。図３では、初版地図データから、第２版地図データ、第３版地図データの順に地図データの更新が行われている。
【００５３】
初版地図データが作成される当初から道路区間「ａ」〜「ｄ」が敷設されている場合には、図３に示すように、道路区間「ａ」〜「ｄ」が含まれる初版地図データが作成される。この状態から道路区間「ｅ」〜「ｈ」が開通した場合に、道路区間「ｅ」〜「ｈ」の追加を初版地図データに反映した第２版地図データが作成される。以降では、更新された地図要素である道路区間「ｅ」を示すデータのグループを差分グループＡ１、道路区間「ｆ」を示すデータのグループを差分グループＡ２、道路区間「ｇ」を示すデータのグループを差分グループＡ３、道路区間「ｈ」を示すデータのグループを差分グループＡ４とする。
【００５４】
図３に示すように、道路区間「ｅ」は道路区間「ｃ」から分岐するように開通し、道路区間「ｆ」は道路区間「ｅ」から伸長するように開通し、道路区間「ｇ」は道路区間「ｂ」に交差するように開通し、道路区間「ｈ」は道路区間「ｇ」から伸長するように開通するものとする。
【００５５】
さらに、この状態から道路区間「ｉ」〜「ｌ」が開通した場合に、道路区間「ｉ」〜「ｌ」の追加を第２版地図データに反映した第３版地図データが作成される。以降では、更新された地図要素である道路区間「ｉ」を示すデータのグループを差分グループＢ１、道路区間「ｊ」を示すデータのグループを差分グループＢ２、道路区間「ｋ」を示すデータのグループを差分グループＢ３、道路区間「ｌ」を示すデータのグループを差分グループＢ４とする。
【００５６】
図３に示すように、道路区間「ｉ」は道路区間「ｆ」から伸長するように開通し、道路区間「ｊ」は道路区間「ｉ」から伸長するように開通し、道路区間「ｋ」、「ｌ」のそれぞれは道路区間「ｇ」から伸長するように開通するものとする。
【００５７】
第２版地図データで更新された地図要素のうち、道路区間「ｆ」は、道路区間「ｅ」の追加がなければ他の道路区間から孤立した状態となってしまうので、道路区間「ｆ」と道路区間「ｅ」との間には、道路区間「ｆ」が道路区間「ｅ」を依存先とする依存関係がある。よって、差分グループＡ１と差分グループＡ２とは依存関係にある。以降では、依存先を「親」と呼び、依存する側を「子」と呼ぶ。差分グループＡ１と差分グループＡ２との依存関係を親子で表すと、差分グループＡ１が「親」、差分グループＡ２が「子」となる。
【００５８】
第２版地図データで更新された地図要素のうち、道路区間「ｈ」は、道路区間「ｇ」の追加がなければ他の道路区間から孤立した状態となってしまうので、道路区間「ｈ」と道路区間「ｇ」との間にも、道路区間「ｈ」が道路区間「ｇ」を依存先とする依存関係がある。よって、差分グループＡ３が「親」、差分グループＡ４が「子」となる依存関係がある。
【００５９】
第３版地図データで更新された地図要素のうち、道路区間「ｉ」は、第２版地図データで更新された地図要素である道路区間「ｆ」の追加がなければ他の道路区間から孤立した状態となってしまうので、道路区間「ｆ」と道路区間「ｉ」との間にも、道路区間「ｉ」が道路区間「ｆ」を依存先とする、バージョンを跨いだ依存関係がある。よって、差分グループＡ２が「親」、差分グループＢ１が「子」となる依存関係がある。
【００６０】
第３版地図データで更新された地図要素のうち、道路区間「ｊ」は、道路区間「ｉ」の追加がなければ他の道路区間から孤立した状態となってしまうので、道路区間「ｉ」と道路区間「ｊ」との間にも、道路区間「ｊ」が道路区間「ｉ」を依存先とする依存関係がある。よって、差分グループＢ１が「親」、差分グループＢ２が「子」となる依存関係がある。
【００６１】
また、第３版地図データで更新された地図要素のうち、道路区間「ｋ」、「ｌ」は、第２版地図データで更新された地図要素である道路区間「ｈ」の追加がなければ他の道路区間から孤立した状態となってしまうので、道路区間「ｋ」、「ｌ」と道路区間「ｉ」との間にも、道路区間「ｋ」、「ｌ」が道路区間「ｈ」を依存先とする、バージョンを跨いだ依存関係がある。よって、差分グループＡ４が「親」、差分グループＢ３、Ｂ４が「子」となる依存関係がある。なお、差分グループＢ３と差分グループＢ４との間には依存関係はない。
【００６２】
以上の説明からも分かるように、差分グループＡ１〜Ａ４、Ｂ１〜Ｂ４の依存関係は、異なるバージョンについての差分グループにまで遡ることもある。図３の例では、「親」から順にＡ１−Ａ２−Ｂ１−Ｂ２、Ａ３−Ａ４−Ｂ３・Ｂ４という依存関係になる。地図差分ＤＢ１２に格納される依存リストは、このような依存関係を示したリストである。
【００６３】
＜初回の配信データ量長期予測＞
図４は、管理サーバ側制御部２３の予測部２３１が行う処理のうち、各ナビゲーション装置３に対して１回行う処理である。この処理は、たとえば、ナビゲーション装置３が車両で用いられる初回の電源オン時に実行する。あるいは、出荷前に事前に実行しておいてもよい。さらには、この処理は、ベース地図のバージョンが同じであれば同一の処理になるので、ベース地図のバージョン毎に１回実行し、実行結果を、ベース地図が同じである他のナビゲーション装置３で利用してもよい。
【００６４】
ステップＳ１では、地図データ記憶領域の初期残量を設定する。この初期残量は、地図データ記憶領域の全体容量から、ベース地図データの容量を引くことで求める。あるいは、ベース地図データを記憶した記憶媒体をパーソナルコンピュータ等に接続して、地図データ記憶領域の残量を表示させることで、初期残量を把握してもよい。
【００６５】
ステップＳ２では、配信データ量の長期予測をナビＩＤごとに行う。この予測は図５に例示した配信データ量の長期予測データに基づいて行う。図５に例示したグラフは、今後、各配信期間において配信すると予測されるデータ量（以下、予測配信データ量）を長期間にわたり予測したグラフである。上記配信期間とは、新しく作成された地図差分データの配信が開始される日により区切られる期間であり、地図差分データは差分更新周期（以下、リリース周期）が経過するごとに新しいデータの配信が開始される。なお、新しいデータの配信が開始されても、それまでのデータの配信が終了するわけではなく、それまでのデータに加えて最新のデータも配信可能な状態となる。
【００６６】
上記グラフを、以下では長期予測配信データ量のグラフ、あるいは、単に、長期予測配信データ量ということもある。この長期予測配信データ量のグラフは更新管理サーバ２を管理する会社が作成して、更新管理ＤＢ２２に格納する。
【００６７】
図５のグラフを作成するための情報としては、過去の地図差分データ配信実績、および、今後の新たに変更が生じる地図要素（新たに作られる道路や施設、取り壊される施設）の情報がある。
【００６８】
図５のグラフは、本実施形態では、少なくとも３年分を作成する。３年としたのは、地図差分データを配信することを保証する期間（２年）に、ベース地図が作成されてからユーザがナビゲーション装置３を所有するまでの期間を加えた期間とするためである。
【００６９】
地図要素に今後の変更が生じることが分かる期間は、国や地域によって異なるが、３年もの期間にわたり、将来の変更が精度よく分かることは少ない。そこで、過去の地図差分データ配信実績も用いて図５のグラフを作成するのである。過去の配信実績を利用することができる理由は、ある月には新規道路の開通が多いなどの傾向があることが判明しているからである。したがって、過去の数年分の配信実績を月別に平均するなどして、仮の長期予測データを作成する。そして、その仮の長期予測データを、その時点で確定している今後の地図要素の変更に基づいて補正して、最終的な長期予測データを作成する。なお、本実施形態では、この長期予測データを地域別に作成するものとする。その理由は、本実施形態では、配信する地図差分データのデータ量は地域により異なるからである。
【００７０】
図５に示したグラフに基づいたナビＩＤごとの配信データ量の長期予測の処理は、図５に例示したように、ナビＩＤから定まるバージョンのベース地図に反映済みの最新時点を起算時点として、３年分の予測配信データ量を取得する処理となる。
【００７１】
なお、道路の新規開通がすでに分かっているなど、地図要素に新たに変更が生じることが分かっている場合、その情報を予測配信データ量に反映させるためには、道路の新規開通等に対応するデータ量を予測する必要がある。
【００７２】
そこで、本実施形態では、差分に関する道路の情報から予測配信データ量を演算することができる演算ツールを利用する。差分に関する道路の情報には、新規道路の開通距離や、新規道路が通る地図データ上のメッシュの数などがあり、道路種別により、どのような具体的情報を、差分に関する道路の情報として用いるかは予め設定されている。たとえば、高速道路では、新規道路の開通距離を差分に関する道路の情報として用い、一般道路であれば、新規道路を含むメッシュの数を差分に関する道路の情報として用いる。ただし、これは一例であり、たとえば、高速道路であっても、その他の情報を、差分に関する道路の情報に含めてもよい。
【００７３】
上記ツールは、差分に関する道路の情報に係数を乗じ、さらには、必要に応じて定数を加えることで、予測配信データ量を演算する。これら係数や定数は、これまでの実績から決定する。このツールについては、図９でさらに詳しく説明する。
【００７４】
＜配信データが配信される処理の流れ＞
次に、図６のシーケンス図を用いて、配信データが配信される処理の流れを説明する。
【００７５】
＜ｔ１．抽出用情報送信処理（ナビゲーション装置３）＞
まず、ナビゲーション装置３の制御装置４１（この図６においては、以下、単にナビゲーション装置３と記載）が、差分抽出用情報送信処理を行う（ｔ１時点）。差分抽出用情報送信処理は、所定のトリガを検出した場合に行う。所定のトリガは、例えば自車両のＡＣＣ電源オンやナビゲーション装置３での目的地設定である。自車両のＡＣＣ電源オンは、外部入力Ｉ／Ｆ部３３を介して取得したＡＣＣ電源のオンオフの信号をもとに検出すればよい。
【００７６】
差分抽出用情報送信処理では、ナビ側記憶装置３４に記憶されているベース地図よりも後に作成された地図差分データを地図差分抽出サーバ１および更新管理サーバ２で抽出するための情報（以下、差分抽出用情報）を、更新管理サーバ２に送信する。
【００７７】
差分抽出用情報は、たとえば、自車両のＡＣＣ電源オンを検出した場合には、位置検出器３２で検出したユーザ位置（緯度・経度）、ベース地図データのバージョン、および送信元を特定するための識別情報としてのナビＩＤを含む。
【００７８】
また、目的地設定を検出した場合の差分抽出用情報は、たとえば、位置検出器３２で検出したユーザ位置の座標（緯度・経度）、目的地の座標（緯度・経度）、ベース地図データのバージョン、およびナビＩＤを含む。経由地の設定も行われていた場合には、経由地の座標（緯度・経度）も含む差分抽出用情報を送信する。以降では、自車両のＡＣＣ電源オンを検出した場合の処理をＡＣＣオン時、目的地設定を検出した場合の処理を目的地設定時として区別する。
【００７９】
＜ｔ２．指定情報決定処理（更新管理サーバ２）＞
更新管理サーバ２の管理サーバ側制御部２３（この図６においては、以下、更新管理サーバ２と記載）は差分抽出用情報を受信すると、その差分抽出用情報と、更新管理ＤＢ２２でナビＩＤ別に管理している配信済み差分グループデータとを照らし合わせる。そして、照らし合わせた結果から、今回配信すべき差分グループデータが定まる差分グループ指定情報を決定する（ｔ２時点）。
【００８０】
＜ｔ３．指定情報送信処理（更新管理サーバ２）＞
更新管理サーバ２は、ｔ２時点で決定した差分グループ指定情報を、管理サーバ側通信部２１を介して地図差分抽出サーバ１へ送信する（ｔ３時点）。
【００８１】
＜ｔ４．差分グループ抽出処理（地図差分抽出サーバ１）＞
差分グループ指定情報を、抽出サーバ側通信部１１を介して地図差分抽出サーバ１の抽出サーバ側制御部１３が受信すると、地図差分抽出サーバ１の抽出サーバ側制御部１３（この図６においては、以下、地図差分抽出サーバ１と記載）は差分グループ抽出処理を行う（ｔ４時点）。
【００８２】
差分グループ抽出処理では、受信した差分グループ指定情報をもとに、地図差分ＤＢ１２に格納されている差分グループデータに対応する差分グループＩＤのうちから、更新管理サーバ２に送信する差分グループＩＤを抽出する。一例として、差分グループＩＤの抽出は以下のようにして行う。
【００８３】
ＡＣＣオン時か目的地設定時かに関わらず、差分グループ抽出処理では、今回配信する全国配信差分グループを抽出する。全国配信差分グループとは、高速道路のように、広い範囲に跨る地図要素であって全てのユーザにとって更新が望ましいと推定される差分グループである。この全国配信差分グループのうち、指定情報において配信済みであることが示されている差分グループを除いたものを、今回配信する全国配信差分グループとして抽出する。
【００８４】
一例として、道路種別が高速道路であるリンクを含む差分グループは、全国配信対象差分グループと判別する。全国配信対象差分グループの差分グループＩＤを、以降では全国配信ＩＤと呼ぶ。
【００８５】
ＡＣＣオン時の差分グループ抽出処理では、差分抽出用情報に含まれるユーザ位置の緯度・経度を中心とした所定の矩形範囲（以下、要求矩形範囲）に少なくともメッシュの一部が含まれる前述のメッシュＩＤを決定する。所定の矩形範囲は、ユーザの平均的な一日の行動範囲に基づいて決定する。そして、決定したメッシュＩＤが示すメッシュ内に含まれ、且つ、まだ配信していない差分グループ（以下、個人配信差分グループ）を抽出する。なお、今回配信する全国配信対象差分グループと重複するものについては、抽出対象外とする。
【００８６】
目的地設定時の差分グループ抽出処理では、差分抽出用情報に含まれるユーザ位置の緯度・経度および目的地の緯度・経度を中心とした要求矩形範囲に少なくともメッシュの一部が含まれるメッシュＩＤを決定する。差分抽出用情報に経由地の緯度・経度も含まれる場合には、経由地の緯度・経度を中心とした要求矩形範囲に少なくともメッシュの一部が含まれるメッシュＩＤも決定する。
【００８７】
また、ユーザ位置から目的地までの経路探索を実施し、探索した経路がのったメッシュのメッシュＩＤも決定する。経路探索については、公知の経路探索方法に従って行う構成とすればよい。そして、決定したメッシュＩＤが示すメッシュ内に含まれ、且つ、まだ配信していない差分グループを抽出する。この差分グループも以降は個人配信差分グループと呼ぶ。なお、全国配信対象差分グループと重複するものについては、抽出対象外とする。個人配信差分グループの差分グループＩＤを、以降では個人配信ＩＤと呼ぶ。
【００８８】
＜ｔ５．依存先差分グループ抽出処理（地図差分抽出サーバ１）＞
差分グループが抽出された場合には、地図差分抽出サーバ１は、次に依存先差分グループ抽出処理を行う（ｔ５時点）。この処理では、依存リストを参照して、差分グループ抽出処理で抽出した差分グループが依存する先である依存先差分グループを抽出する。依存先差分グループの差分グループＩＤを、以降では依存先差分ＩＤと呼ぶ。
【００８９】
なお、差分グループ抽出処理で差分グループが抽出されなかった場合には、差分グループなしとして結果を更新管理サーバ２に返し、ｔ５以降の処理は行わない。
【００９０】
＜ｔ６．配信データ作成処理（地図差分抽出サーバ１）＞
地図差分抽出サーバ１は、次に、配信データ作成処理を行う（ｔ６時点）。配信データ作成処理では、差分グループ抽出処理、依存先差分グループ抽出処理で抽出した差分グループ、依存先差分グループを、必要に応じて規定の通信サイズに収まるデータに分割・圧縮等して、配信データを作成する。作成した配信データはＨＤＤ等の大容量の記憶装置に格納する。
【００９１】
＜ｔ７．データＵＲＬ送信処理（地図差分抽出サーバ１）＞
地図差分抽出サーバ１は次にデータＵＲＬ送信処理を行う（ｔ７時点）。データＵＲＬ送信処理では、前述の配信データ作成処理で作成して記憶装置に格納した配信データのアドレスを示すデータＵＲＬおよび配信データに含む差分グループＩＤを、抽出サーバ側通信部１１を介して更新管理サーバ２へ送信する。
【００９２】
＜ｔ８．データＵＲＬ中継処理（更新管理サーバ２）＞
地図差分抽出サーバ１から送信されたデータＵＲＬを、管理サーバ側通信部２１を介して更新管理サーバ２の管理サーバ側制御部２３が受信すると、更新管理サーバ２はデータＵＲＬ中継処理を行う（ｔ８）。データＵＲＬ中継処理では、受信したデータＵＲＬを、管理サーバ側通信部２１を介してナビゲーション装置３へ送信する。また、更新管理サーバ２は、地図差分抽出サーバ１から送信された差分グループＩＤを、配信済みの差分グループＩＤとして更新管理ＤＢ２２に格納する。
【００９３】
＜ｔ９．差分データ取得処理（ナビゲーション装置３）＞
更新管理サーバ２から送信されたデータＵＲＬをナビゲーション装置３が受信すると、ナビゲーション装置３は差分データ取得処理を行う（ｔ１３）。差分データ取得処理では、受信したデータＵＲＬが示すアドレスにアクセスを行い、そのアドレスに格納されている配信データの送信を要求する。
【００９４】
＜ｔ１０．配信処理（地図差分抽出サーバ１）＞
上記要求を受信した地図差分抽出サーバ１は配信処理を行う（ｔ１０）。ナビゲーション装置３から要求された配信データを、抽出サーバ側通信部１１を介してナビゲーション装置３へ配信する。
【００９５】
＜ｔ１１．更新処理（ナビゲーション装置３）＞
地図差分抽出サーバ１から配信された配信データを受信すると、ナビゲーション装置３は、その配信データをナビ側記憶装置３４の地図データ記憶領域に格納する（ｔ１１時点）。この時点で行うのは格納までであり、ベース地図と差分グループの合成は、地図データをもとにして案内を行うアプリケーションプログラムで必要となるタイミングで行う。
【００９６】
なお、配信データ作成処理で作成した配信データは、地図差分抽出サーバ１以外のサーバに格納する構成としてもよい。この場合には、差分データ取得処理において、配信データが格納されたサーバにナビゲーション装置３が配信データの送信を要求し、配信データが格納されたサーバが配信データを配信する。
【００９７】
＜長期予測配信データ量の修正＞
図７は、管理サーバ側制御部２３の予測部２３１が行う処理のうち、新しい地図差分データの配信を開始する都度、その配信開始前に行う処理であり、ナビゲーション装置別に行う処理である。なお、ナビゲーション装置別ではなく、地域別に行う変形例も後述する。
【００９８】
新しい地図差分データは、前述のように、リリース周期経過ごとに配信が開始される。リリース周期は、ベース地図の更新周期よりも短い周期であり、たとえばベース地図の更新周期が１年であるのに対して、地図差分データのリリース周期は１月あるいは３週間などに設定される。
【００９９】
この図７に示す処理を実行することにしている理由は、ナビ側記憶装置３４の地図データ記憶領域に記憶できる容量には上限があり、地図差分データを記憶し続けて行くと、容量オーバーになる恐れがあるからである。この図７の処理を行うことで、容量オーバーになる可能性があるか否かを事前に確認するのである。
【０１００】
ステップＳ１１では、ナビ側記憶装置３４の地図データ記憶領域の残容量を算出する。この計算は、前回この図７を実行してから現時点までに配信した差分データの容量を、前回、このステップＳ１１で算出した残容量から引くことで算出する。なお、これに代えて、各ナビゲーション装置３から、ナビ側記憶装置３４の地図データ記憶領域の残容量を取得してもよい。
【０１０１】
続くステップＳ１２では、計画済みバージョンの配信データ量予測を行う。ここで計画済みバーションについて説明する。道路の開通など、地図データにおける地図要素を変更する必要がある事象が生じたことは、現地調査などにより逐次取得しており、取得の都度、地図差分データを作成して配信することも可能である。
【０１０２】
しかし、本実施形態では、作成した地図差分データを差分グループデータにまとめる必要がある等の理由で即座に配信可能とはしない。配信可能とする差分グループデータを、上述のリリース周期で更新する。また、リリース周期で更新する際も、必ず次の更新から配信可能とするとは限らず、次々回の更新以降に配信可能とすることもある。その理由は、同じ地域に対する差分グループデータが多くなり過ぎないようにするためである。前述のように、差分グループデータを配信するか否かは、ユーザの位置に基づいて決まる。よって、同じ地域に対する差分グループデータが多いと、その地域にいるユーザやその地域に向かうユーザは配信量が多くなってしまう一方で、他の地域にいるユーザは配信量が少なくなってしまうからである。
【０１０３】
これらのことから、地図差分抽出サーバ１を管理する会社は、次回、あるいは、次々回以降の更新においてどの差分グループデータを配信するかを定めた配信計画を立てる。なお、各配信計画は、バージョン１、バージョン２など、バージョンに続く数字で区別する。
【０１０４】
ステップＳ１２では、配信計画が立てられたバージョンに対して、各ナビゲーション装置３に配信されると予測される配信データ量を予測する。そして、予測の結果を長期予測配信データ量のグラフに反映する。
【０１０５】
＜計画済みバージョンの配信データ量の予測＞
ステップＳ１２の処理の詳細は図８に示している。次に図８を説明する。なお、上述したように、この図８を実行する時点では、次回のバージョンの配信計画が決定されており、次々回以降のバージョンの配信計画が決定されている場合もある。
【０１０６】
そして決定されたバージョンの配信計画に対応する地図差分データが作成されて、地図差分ＤＢ１２に格納されている。また、地図差分ＤＢ１２に格納されている地図差分データは、前述のように差分グループデータにまとめられている。加えて、新たに格納された差分グループに対応して依存リストも更新されている。この状態で図８は実行される。
【０１０７】
ステップＳ１２１では、未配信の差分グループ（すなわち最小単位差分）ごとに重心座標を決定する。詳しくは、差分グループを構成する地図差分データを含むメッシュを特定し、特定したメッシュ全部の面積重心点をその差分グループの重心座標とする。この重心座標は請求項のデータ基準点に相当する。
【０１０８】
続くステップＳ１２２では、ユーザの居所と、ステップＳ１２１で決定した差分グループの重心座標との距離を、ユーザごと且つ差分グループごとに算出する。そして、その距離が予め設定してある上限距離以下であれば、その差分グループは配信されると決定し、算出した距離が上限距離よりも長ければ、その差分グループは配信されないとする。ユーザの居所は、更新管理ＤＢ２２に記憶されており、前述のようにユーザの住所や車両の登録地点である。
【０１０９】
実際にナビゲーション装置３に配信される差分グループは、ＡＣＣオン時の車両の座標や、設定した目的地、経由地等の座標から定まる範囲の差分グループである。ここでのユーザの居所は、それらＡＣＣオン時の車両の座標等の代用として用いている。
【０１１０】
ステップＳ１２３では、ステップＳ１２２で配信されると予測した差分グループ、およびその差分グループと依存リストから、配信される依存先差分グループも予測する。そして、両方の差分グループのデータ量をユーザ別に合計する。合計したデータ量を、以下では予測配信データ量という。なお、複数のバージョンの配信計画に対して予測を行なっている場合には、各バージョンの配信計画別に予測配信データ量を計算する。
【０１１１】
さらに、ここで算出する予測配信データ量は、配信時に差分グループデータに付与されるヘッダ情報等の付随情報のサイズも考慮して行う。たとえば、配信されると予測した差分グループの数に所定の係数を乗じて付随情報のデータ量を計算し、この付随情報のデータ量を差分グループデータの合計量に加えた値を予測配信データ量とする。もちろん、ステップＳ１２３の演算に用いた差分グループデータがすでに付随情報を含んだデータであれば、単に差分グループデータのデータ量を合計する。
【０１１２】
ステップＳ１２４では、ステップＳ１２３で得た予測配信データ量を配信すると、それにより、その月の配信上限データ量を超えてしまうか否かを判断する。新しいバージョンの配信開始が月に１回である場合には、１回のバージョンの配信計画に含まれる地図差分データの予測配信データ量と配信上限データ量とを比較してこの判断を行う。
【０１１３】
新たなバージョンの配信開始時点が月に複数回存在する場合には、複数回分の予測配信データ量の合計値と一ヶ月の配信上限データ量とを比較してこの判断を行う。また、複数回の配信開始時点が一ヶ月の中に存在するが、予測配信データ量を算出しているのはそのうちの一部（たとえば次の１回）のバージョンについてのみである場合、予測配信データ量を算出していないバージョンについては、図４のステップＳ２で予測したデータ量を用いる。
【０１１４】
ステップＳ１２４の判断がＹＥＳであれば、ステップ１２５へ進んで、予測を行った月の予測合計データ量（一ヶ月に配信すると予測した合計のデータ量）を一ヶ月の配信上限データ量とする。この場合、総予測配信データ量のグラフにおいて該当月の予測配信データ量を補正する。一方、ステップＳ１２４の判断がＮＯであればステップＳ１２６へ進んで、予測を行った月の予測合計データ量を、ステップＳ１２４において一ヶ月の配信上限データ量と比較したデータ量（すなわち、１回分あるいは複数回分の予測配信データ量）とする。
【０１１５】
ステップＳ１２５またはＳ１２６を実行したら図７に戻り、ステップＳ１３を実行する。ステップＳ１３では、次回の配信期間において、ステップＳ１２で予測した予測配信データ量を配信しても地図データ記憶領域の残容量オーバーとならないかを判断する。なお、配信期間は、前述したように、新しく作成された地図差分データの配信が開始される日により区切られる期間である。
【０１１６】
ステップＳ１３の判断は具体的には、ステップＳ１１で算出した残容量が、ステップＳ１２で予測した次回の予測配信データ量よりも大きいか否かを判断するものである。残容量のほうが次回の予測配信データ量よりも大きい場合にはステップＳ１３はＹＥＳとなり、ステップＳ１４へ進む。一方、予測配信データ量が残容量以上であれば、ステップＳ１３はＮＯ、すなわち、ナビ側記憶装置３４の地図データ記憶領域の容量オーバーにより、次回の予測配信データ量を全部は配信することができないと判断する。この場合には図１０へ進む。
【０１１７】
図１０は、実際に差分グループデータを配信する際に、既に計画された配信予定の差分グループデータのうちの一部のデータを配信しないように計画を修正して配信する処理であり、配信処理部として機能する抽出サーバ側制御部１３が実行する。この図１０の詳細は後述する。
【０１１８】
ステップＳ１４では、次々回以降の予測配信データ量を修正する。この処理は詳しくは図９に示す処理になる。
【０１１９】
＜次々回以降の予測配信データ量の修正＞
図９において、ステップＳ１４１では、地図差分データ作成見込みの道路の情報から、配信データ量の予測を行う。
【０１２０】
地図差分データ作成見込みの道路の情報とは、たとえば、まだ開通はしていないが地点Ｐ１から地点Ｐ２まで新規道路が開通する予定であるという情報である。開通前であることから、地図差分データは作成されていないが、その道路が開通すれば、その道路を反映した地図差分データが作成されることになる。
【０１２１】
ここでの配信データ量の予測は、道路の種別により方法が異なる。高速道路の場合には、道路の差分距離に、過去の実績から予め求めておいた高速道路用の係数を乗じて、予測される配信データ量を算出する。なお、道路の差分距離は、新規に開通した高速道路であれば開通距離である。また、古くなった高速道路の削除・閉鎖であれば、削除・閉鎖距離である。一般道路の場合には、その道路が通るメッシュの数に、過去の実績から予め求めておいた一般道路用の係数を乗じて、予測される配信データ量を算出する。これらは一例であり、たとえば、一般道路の場合に、さらに、メッシュ内に存在する道路に対する新規道路の割合を考慮するようにしてもよい。
【０１２２】
このステップＳ１４１で予測を行うことができるのは、たとえば数ヶ月先までなど、近い将来のみである。それより先になると、新規に道路が開通するなどの情報は得にくい。したがって、このステップＳ１４１では、数ヶ月先までなど、近い将来のバージョンの配信計画に対する予測配信データ量だけを予測する。それよりもさらに先の予測は、次のステップＳ１４２、Ｓ１４３により行う。ステップＳ１４１でいつまでの予測を行うかは予め設定されていてもよいし、このステップＳ１４１で用いる情報が得られている期間を、このステップＳ１４１の実行時点で判断して決定してもよい。
【０１２３】
このステップＳ１４１で予測を行ったバージョンは、予測を行う前のそのバージョンに対する予測配信データ量を、今回、このステップＳ１４１で予測した予測配信データ量に置き換える。
【０１２４】
続くステップＳ１４２では、ステップＳ１４１で予測をしていない期間の予測配信データ量を補正するための補正係数を算出する。この処理は、具体的には、前回の配信期間（すなわち、既に経過した配信期間のうちの最新のもの）に対して予測していた予測配信データ量に対する、実際にその配信期間に配信した配信データの実績データ量の比を補正係数として算出する。
【０１２５】
続くステップＳ１４３では、長期予測配信データ量に含まれる各配信期間の予測配信データ量のうち、ステップＳ１４１で修正していない配信期間の予測配信データ量に、ステップＳ１４２で算出した補正係数を乗じる。ステップＳ１４３を実行したら、図７に戻り、ステＳ１５へ進む。
【０１２６】
図７のステップＳ１５では、総予測配信データ量が残容量を超えるか否かを判断する。総予測配信データ量とは、ステップＳ１２およびステップＳ１４を実行して修正した長期予測配信データ量のグラフ（図５）において、今後の部分であって、図４を実施したときを起算点として３年経過時点までの各配信期間の予測配信データ量の合計値である。総予測配信データ量が、ステップＳ１１で算出した残容量を超えない場合には（Ｓ１５：ＮＯ）、今までと同じようにして地図差分データをナビゲーション装置３に配信しても、ナビ側記憶装置３４の地図データ記憶領域の残容量がなくなってしまうことはないと予測できるので、そのまま図７を終了する。
【０１２７】
ステップＳ１５がＹＥＳとなった場合には、ステップＳ１６に進む。ステップＳ１６では、今まで通りに配信を続けていった場合に残容量を超える配信期間を決定する。そして、図示しない表示部に、残容量を超える旨と、残容量を超える配信期間と、残容量を超えると予測したナビゲーション装置３を特定した警告を出す。図７の処理は、更新管理サーバ２における処理であり、上記警告は、更新管理サーバ２を管理する管理者に通知されることになる。
【０１２８】
管理者は、警告が通知された場合、残容量を超えてしまう予測となったナビゲーション装置３のナビ側記憶装置３４が、残容量を超えないようにする処置を行うことになる。この処置は、たとえば、そのナビ側記憶装置３４に記憶されている地図差分データのうち、使用頻度が低いデータの削除を、ナビゲーション装置３の制御装置４１へ指示する処置がある。
【０１２９】
＜配信データ量の抑制＞
次に、図７のステップＳ１３がＮＯとなった場合に実行する図１０を説明する。図７のステップＳ１３がＮＯとなった場合には、次回の配信予定のバージョンに含まれている差分グループを全部は配信できないと判断したことになる。そこで、図１０では、既に計画された配信予定の差分グループデータのうちの一部のデータを配信しないように計画を修正する。
【０１３０】
まず、ステップＳ２１では、最小配信単位をもとにして、残容量を超えない組み合わせを全て決定する。最小配信単位とは、図６のｔ４〜ｔ５で決定する複数の差分グループデータ、すなわち、ある差分グループデータおよびその差分グループデータの依存先である依存先差分グループデータからなる単位である。
【０１３１】
図１１は、依存リストの例である。図１１に示すように、最小配信単位は、レコードとして記述される。図１１の例では、レコード１は、ＩＤ１１とＩＤ１２の差分グループからなることなどが記述されている。
【０１３２】
続くステップＳ２２では、ステップＳ２１で決定した組み合わせの中で、データ量が最大の組み合わせを、配信する組み合わせに決定する。配信する組み合わせに含まれないことになったレコードは、図６のｔ４において、ユーザ位置（緯度・経度）を中心とした要求矩形範囲に含まれるとしても配信しないことになる。
【０１３３】
＜ＰＣによるダウンロード＞
本実施形態では、地図差分データを通信装置３１を介した無線通信で取得できるだけでなく、ナビ側記憶装置３４を構成するＳＤカードを、インターネット通信網につながっているパーソナルコンピュータに接続して地図差分データをダウンロードすることもできる。
【０１３４】
無線通信により取得する地図差分データは、図６を用いて説明したように、ユーザ位置の周辺、目的地の周辺、経由地の周辺など、比較的狭い地域の地図差分データであった。これは無線通信の通信速度を考慮したものである。
【０１３５】
パーソナルコンピュータを用いたインターネット通信網を経由するダウンロードは、有線回線が多く、車両に搭載された無線通信装置よりも、パーソナルコンピュータを用いた通信の方が、通信速度が速いことが一般的である。
【０１３６】
そこで、本実施形態においては、パーソナルコンピュータを用いて地図差分データをダウンロードする場合には、通信装置３１を用いて行う場合の地域よりも広い地域（たとえば、県全部、省全部など）の地図差分データをダウンロードする。また、パーソナルコンピュータによるダウンロードにおいても、全国配信差分グループはダウンロードする。
【０１３７】
パーソナルコンピュータによるダウンロードの場合において、地図差分データをダウンロードする地域を決定するための情報には、予め登録してあるユーザの居所を用いる。ユーザの居所の特定にはＳＤカードに記憶されているナビＩＤを用い、ナビＩＤから、そのナビＩＤに対応する登録情報を特定することで、ユーザの居所を決定する。
【０１３８】
パーソナルコンピュータによる地図差分データのダウンロードは、ユーザがパーソナルコンピュータを操作して行い、このダウンロードを行うかどうかは、ユーザが任意に決定する。
【０１３９】
＜処理時間判定＞
次に、図１２を用いて、機能低下判定処理の具体的処理である処理時間判定処理を説明する。この処理時間判定処理は、地図差分データがナビ側記憶装置３４に記憶されることによって、ナビゲーション装置３の制御装置４１の処理時間が許容できる範囲を超えて長くなってしまうかどうかを判定する処理である。この処理も、図７と同様、管理サーバ側制御部２３が行う処理であり、登録してある各ナビゲーション装置３を対象として行う。この処理は、図１２に示すように、図７のステップＳ１４の結果を用いる。したがって、図７を実施する都度、この図１２も実施する。
【０１４０】
ステップＳ３１では、累積予測配信データ量を配信期間ごとに演算する。累積予測配信データ量は、ナビ側記憶装置３４に記憶されているベース地図データの作成時から起算して３年を経過するまでの各配信期間に対して演算する。過去分については実際に配信した地図差分データのデータ量を合計する。将来分については、図５、図７で予測したデータ量を用い、それらのデータ量を加算することで、累積予測配信データ量を演算する。
【０１４１】
ステップＳ３２では、配信期間ごとに、（１）更新時間（無線）、（２）更新時間（ＰＣＤＬ）、（３）経路計算時間、（４）地図描画時間を求める。（１）更新時間（無線）は、通信装置３１を用いた地図差分データのダウンロードに要する時間とダウンロードした地図差分データをベース地図データに重ね合わせる重ね合わせ処理に要する時間の合計である。（２）更新時間（ＰＣＤＬ）はパーソナルコンピュータを用いた地図差分データのダウンロードに要する時間とダウンロードした地図差分データをベース地図データに重ね合わせる重ね合わせ処理に要する時間の合計である。（３）経路計算時間は、ベース地図データおよびダウンロードした全ての地図差分データを用いた経路計算に要する時間である。（４）地図描画時間は、ベース地図データおよびダウンロードした全ての地図差分データを用いた地図描画に要する時間である。
【０１４２】
（１）〜（４）のうち、（１）、（２）は、地図差分データ作成見込みの道路の情報を、予め設定してある更新時間予測ツールに入力することで求める。地図差分データ作成見込みの道路の情報の意味は、図９のステップＳ１４１と同じである。よって、図９のステップＳ１４１を実行するときに、同時に、上記（１）、（２）も求めればよい。更新時間予測ツールは、過去に地図差分データを配信したときの配信時間の実績に基づいて、入力する道路の情報（距離やメッシュ数など）と、更新時間との対応関係が設定される。
【０１４３】
（３）、（４）は、ステップＳ３１で求めた累積予測配信データ量を、予め設定してある経路時間および描画時間予測ツールに入力することで求める。このツールも、過去の実績時間に基づいて作成する。
【０１４４】
なお、図９で説明したように、予測配信データ量はツールにより、地図差分データ作成見込みの道路の情報から求めることができる。そして、そのツールにより予測した予測配信データ量を累積すれば累積予測配信データ量となる。つまり、累積予測配信データ量も、地図差分データ作成見込みの道路の情報から求めることができる。そこで、（３）、（４）についても、地図差分データ作成見込みの道路の情報から求めるようにしてもよい。
【０１４５】
ステップＳ３３では、ステップＳ３２で演算した各時間のいずれか一つが、それらについて予め設定してある許容時間を超えるか否かを判断する。この判断がＮＯ、つまり、ステップＳ３２で演算した各時間が全て許容時間内であれば、今までと同じようにして地図差分データをナビゲーション装置３に配信しても、処理時間は、許容できないほどには長くならないと予測できるので、そのまま図１２を終了する
ステップＳ３３がＹＥＳとなった場合には、ステップＳ３４に進む。ステップＳ３４では、今まで通りに配信を続けていった場合に許容時間を超える配信期間を決定する。なお、（１）、（２）については次回の配信である。
【０１４６】
そして、図示しない表示部に、許容時間を超える旨、許容時間を超える配信期間、および許容時間を超えると予測したナビゲーション装置３を特定した警告を出す。図１２の処理は、更新管理サーバ２における処理であり、上記警告は、更新管理サーバ２を管理する管理者に通知されることになる。
【０１４７】
管理者は、警告が通知された場合、許容時間を超えてしまう予測となったナビゲーション装置３のナビ側記憶装置３４が、許容時間を超えないようにする処置を行うことになる。この処置は、たとえば、そのナビ側記憶装置３４に記憶されている地図差分データのうち、使用頻度が低いデータの削除を、ナビゲーション装置３の制御装置４１へ指示する処置や、次回の配信データ量を制限する処置がある。
【０１４８】
以上、説明した第１実施形態によれば、予測配信データ量を予測しており（Ｓ２、Ｓ１２、Ｓ１４）、次回の予測配信データ量あるいは総予測配信データ量とその時点での残容量とを比較し、比較結果に基づいて、容量オーバーという機能低下を判定するステップＳ１３、Ｓ１５の処理を備える。よって、ナビ側記憶装置３４の地図データ記憶領域の容量オーバーを事前に把握することができる。
【０１４９】
また、次回の予測配信データ量あるいは総予測配信データ量から、（１）更新時間（無線）、（２）更新時間（ＰＣＤＬ）、（３）経路計算時間、（４）地図描画時間が、許容時間を超えてしまうか否かを判断するステップＳ３１〜Ｓ３３の処理を備える。よって、ナビゲーション装置３における上記（１）〜（４）の演算処理時間が許容できないほどに長くなってしまうかどうかを事前に把握することができる。
【０１５０】
さらに、第１実施形態では、ナビゲーション装置３のナビ側記憶装置３４の地図データ記憶領域の残容量が少なくなり、次回の配信に対する配信計画に含まれている差分グループを全部は配信できないと判断した場合（Ｓ１３：ＮＯ）、残容量を超えない範囲でデータ量が最大のレコードの組み合わせを、配信する組み合わせに決定する（Ｓ２２）。これにより、ナビ側記憶装置３４の地図データ記憶領域に、より多くの差分グループを記憶することができる。
【０１５１】
＜第２実施形態＞
次に、第２実施形態を説明する。なお、この第２実施形態以下の説明において、それまでに使用した符号と同一番号の符号を有する要素は、特に言及する場合を除き、それ以前の実施形態における同一符号の要素と同一である。また、構成の一部のみを説明している場合、構成の他の部分については先に説明した実施形態を適用することができる。
【０１５２】
第２実施形態では、図１３に示すように、配信処理部である抽出側サーバ制御部１３は、第１限定部１３１、第２限定部１３２を備える。第１限定部１３１の処理は、次の図１４のステップＳ２１〜Ｓ２２であり、第２限定部１３２の処理は、図１４のステップＳ２３〜Ｓ２６の処理である。また、図１４の処理は、第１実施形態の図１０の処理に代えて実行する処理である。
【０１５３】
ただし、図１４においても、最初は図１０と同じステップＳ２１、Ｓ２２を実行する。このステップＳ２１、Ｓ２２を実行することで、どのレコード（最小配信単位）を配信するかを決定する。
【０１５４】
図１０はステップＳ２２で処理が終了であったが、図１４ではさらにステップＳ２３以降を実行する。ステップＳ２３では、ステップＳ２２で配信することに決定したレコードを全て配信し、ナビ側記憶装置３４の地図データ記憶領域にそれらのレコードが全て記憶されたと仮定して、その地図データ記憶領域にまだ存在する残容量を算出する。ここで算出する残容量が請求項の限定後残容量に相当する。
【０１５５】
続くステップＳ２４では、残りの配信すべきレコードを地図差分データに分解し、各地図差分データを、カテゴリあるいはサブカテゴリの優先度をもとに並べ替える。
【０１５６】
レコードは、すでに説明したように、差分グループおよび依存差分グループにより構成され、差分グループは複数の地図差分データからなる。ここで差分グループを構成する地図差分データを具体的に説明する。
【０１５７】
図１５は、一つの差分グループ（すなわち最小単位差分）を概念的に説明する図である。図１５においてＩＤ１、ＩＤ２、ＩＤ３はそれぞれ差分グループＩＤである。各差分グループは複数の地図差分データ、すなわち、複数の地図要素を表すデータからなるが、説明を分かりやすくするため、図１５には、ＩＤ１の差分グループを構成する地図要素のみ具体的に示している。ＩＤ１の差分グループは、道路１０１、道路１０２、施設１０３、池１０４の４つの地図要素を含んだ構成である。なお、道路１０１は国道であり、道路１０２は細街路であるとする。
【０１５８】
図１６は、カテゴリおよびサブカテゴリの優先度を定義したリストの例である。図１６の例では、カテゴリ「道路」のうちサブカテゴリ「クラス５」以外のクラスは優先度１に設定されており、カテゴリ「道路」でもサブカテゴリ「クラス５」は優先度２に設定されている。クラス５の道路は、ここでは細街路を意味する。また、施設を意味するＰＯＩのうちの一部のサブクラスがそれに続く優先度３に設定され、ＰＯＩの残りのサブクラスが優先度４に設定されている。優先度５はカテゴリ「背景」のうちのサブカテゴリ「３Ｄランドマーク」であり、優先度６はカテゴリ「背景」のサブカテゴリ「文字」であり、優先度７はカテゴリ「背景」のあるサブカテゴリである。また、優先度８はカテゴリ「道路」、「背景」、「ＰＯＩ」とは別のあるカテゴリ全体である。
【０１５９】
これらの優先度は、ユーザがナビゲーション装置３の機能を利用して、あるいは、自宅のパーソナルコンピュータを用いてインターネット回線を通じて更新管理サーバ２に接続する等して、任意のタイミングで設定することができる。購入時に登録してもらうようにしてもよい。
【０１６０】
また、この優先度は、デフォルトでの優先度が設定されており、変更したい部分のみユーザが変更できるようにしてもよいし、空白の状態から、必要な部分にユーザが優先度を入力するようにしてもよい。
【０１６１】
図１６に示した優先度に従うと、図１５のＩＤ１の差分グループを構成する地図要素は、道路１０１は優先度１、道路１０２は優先度２、施設１０３は優先度３、池１０４は優先度７となる。
【０１６２】
ステップＳ２４では、このようにして付与した優先度に従い、地図要素である道路１０１、１０２、施設１０３、池１０４をそれぞれ示す地図差分データを並べ替える。
【０１６３】
ステップＳ２５では、ステップＳ２４で並べ替えた地図差分データを優先度の高い側から順に選択し、ステップＳ２３で算出した残容量を超えない範囲で最大数の地図差分データを選択する。そして、選択した地図差分データを配信する地図差分データに決定する。
【０１６４】
ステップＳ２６では、ステップＳ２５で配信すると決定した地図差分データをもとの差分グループの単位内でまとめ、それを各配信用データとする。
【０１６５】
この配信用データは、ＡＣＣオン時等に、他の差分グループデータと同様の条件で配信データとして抽出されて、ナビゲーション装置３に配信される。
【０１６６】
この第２実施形態では、ナビゲーション装置３のナビ側記憶装置３４の地図データ記憶領域の残容量が少なくなり、次回のバージョンの配信計画に含まれている差分グループを全部は配信できないと判断した場合（Ｓ１３：ＮＯ）、ナビ側記憶装置３４の地図データ記憶領域により多くの差分グループを記憶するため、第１実施形態と同様の処理Ｓ２１〜Ｓ２２を行う。
【０１６７】
さらに、第２実施形態では、第１実施形態における最小配信単位であるレコード、すなわち、複数の差分グループよりなるデータのまとまりを、差分グループよりもさらに小さい単位いである地図差分データに分解する（Ｓ２４）。そして、地図差分データをカテゴリやサブカテゴリの優先度に基づいて選択して、配信用データを作成する（Ｓ２５〜Ｓ２６）。これにより、レコードを記憶することができない僅かな残容量（ステップＳ２３で算出した残容量）にも、地図差分データを記憶することができる。
【０１６８】
＜第３実施形態＞
第３実施形態は、第２実施形態の図１４の処理に代えて、図１７の処理を実行する。図１７の処理は、図１４のステップＳ２１〜Ｓ２３を実行しない点、および、ステップＳ２４に代えて、それに類似する処理であるステップＳ２４−１を実行する点で、図１４と相違する。
【０１６９】
ステップＳ２４−１では、当初計画した次回の配信計画に含まれている全てのレコードを地図差分データに分解し、各地図差分データを、カテゴリあるいはサブカテゴリの優先度をもとに並べ替える。続くステップＳ２５、Ｓ２６は図１４と同じである。
【０１７０】
この第３実施形態では、次回のバージョンの配信計画に含まれている差分グループを全部は配信できないと判断した場合に（Ｓ１３：ＮＯ）、レコードを地図差分データに分解する対象が、当初計画した次回の配信計画に含まれている全てのレコードである（Ｓ２４−１）。よって、第２実施形態よりも、ユーザが重視するカテゴリあるいはサブカテゴリの地図差分データについては、より多くのデータを配信することができる。
【０１７１】
以上、本発明の実施形態を説明したが、本発明は上述の実施形態に限定されるものではなく、次の実施形態も本発明の技術的範囲に含まれ、さらに、下記以外にも要旨を逸脱しない範囲内で種々変更して実施することができる。
【０１７２】
＜変形例１＞
たとえば、前述の実施形態では、車両用ナビゲーション装置３ごとに、容量オーバーが生じる恐れの判定や、処理時間が許容時間を超える恐れがあるかの判定を行なっていたが、同じ地域に存在する車両用ナビゲーション装置３に配信される差分データはある程度は類似する。そこで、市、県、省など予め設定された地域に各車両用ナビゲーション装置３を対応付けておき、上記地域ごとに上記判定を行うようにしてもよい。ただし、ベース地図のバージョンは区別する必要があるので、地域ごと、且つ、ベース地図のバージョン別に判定を行う。
【０１７３】
そして、ある地域のあるベース地図のバージョンが記憶された車両用ナビゲーション装置３において機能低下が生じる恐れがあると判定した場合には、その地域およびそのベース地図のバージョンに該当する車両用ナビゲーション装置３の全部に対して、機能低下が生じる恐れがあると判定する。
【０１７４】
なお、地域別に判定を行う場合には、図８のステップＳ１２２におけるユーザの居所として、その地域において予め設定した地点（たとえば重心地点など）を用いる。
【０１７５】
＜その他の変形例＞
前述したステップの一部（たとえばステップＳ１４１など）を人が行うようにしてもよい（変形例２）。長期予測データを地域別とせずに、全国共通の一つの長期予測データとしてもよい（変形例３）。
【０１７６】
図８のステップＳ１２１において重心座標をデータ基準点としていたが、（ｘ，ｙ）＝（ｘ座標範囲の中点、ｙ座標範囲の中点）とするなど、重心座標以外をデータ基準点としてもよい（変形例４）。
【０１７７】
図９のステップＳ１４２、Ｓ１４３では、補正係数により補正を行なっていたが、実績データ量と予測配信データ量との差を補正量として算出し、その補正量により、予測配信データ量を補正してもよい（変形例５）。
【０１７８】
また、前述の実施形態では、地図差分データ配信システム１００側にて、ナビゲーション装置３に配信されると予測される予測配信データ量等の予測量を推測し、さらに、地図差分データ配信システム１００側にて、その予測量からナビゲーション装置３の機能低下を判定していた。すなわち、前述の実施形態では、地図差分データ配信システム１００の装置である更新管理サーバ２が予測部２３１、機能低下判定部２３２を備えていた。しかし、既に説明したように、ナビゲーション装置３が地図差分データ配信システム１００の一部の機能を実行することも可能である。よって、ナビゲーション装置３が予測部２３１を備えてもよい。つまり、車両用ナビゲーション装置３が、過去の差分データの配信実績に基づいて、予測配信データ量等を推測するようにしても良い（変形例６）。さらに、車両用ナビゲーション装置３が機能低下判定部２３２を備えても良い。なお、機能低下判定部２３２として容量オーバー判定部２３２ａを備える場合には、残容量決定部２３３も車両用ナビゲーション装置が備える（変形例７）。
【０１７９】
そして、推測結果から、自身の機能低下が生じる恐れがあると判定されると、地図差分データ配信システム１００にて配信量を制限してもらうように、地図差分データ配信システム１００に通知するようにしても良い（変形例８）。また、地図差分データ配信システム１００から配信された差分データの一部または全部を受信しないように制限しても良い（変形例９）。また、全部の配信データを受信した後、第１〜第３実施形態で地図差分抽出サーバ１が行ったものと同様の処理を行なって、ナビ側記憶装置３４の地図データ記憶領域に格納するデータを配信データの一部に制限してもよい（変形例１０）。なお、第１実施形態〜第３実施形態のように、地図差分抽出サーバ１にて、ナビ側記憶装置３４の地図データ記憶領域の残容量を超えないデータ量に予め調整された配信データを受信して更新処理（図６のｔ１１）を行う態様も、ナビゲーション装置に係る発明における更新処理部の一実施態様である。
【符号の説明】
【０１８０】
１００：地図差分データ配信システム、      １：地図差分抽出サーバ、      ２：更新管理サーバ、      ３：車両用ナビゲーション装置、      １１：抽出サーバ側通信部、      １２：地図差分データベース、      １３：抽出サーバ側制御部（配信処理部）、      ２１：管理サーバ側通信部、      ２２：更新管理ＤＢ、      ２３：管理サーバ側制御部、      ３１：通信装置、      ３２：位置検出器、      ３４：ナビ側記憶装置（地図記憶装置）、      ４１：制御装置、      １３１：第１限定部、      １３２：第２限定部、      ２３１：予測部、      ２３２：機能低下判定部、      ２３２ａ：容量オーバー判定部、      ２３２ｂ：処理時間判定部、      ２３３：残容量決定部
【図１】
2014209073.tif 000003
【図２】
2014209073.tif 000004
【図３】
2014209073.tif 000005
【図４】
2014209073.tif 000006
【図５】
2014209073.tif 000007
【図６】
2014209073.tif 000008
【図７】
2014209073.tif 000009
【図８】
2014209073.tif 000010
【図９】
2014209073.tif 000011
【図１０】
2014209073.tif 000012
【図１１】
2014209073.tif 000013
【図１２】
2014209073.tif 000014
【図１３】
2014209073.tif 000015
【図１４】
2014209073.tif 000016
【図１５】
2014209073.tif 000017
【図１６】
2014209073.tif 000018
【図１７】
2014209073.tif 000019