(57)【要約】【課題】蓄積情報の更新に関わる処理を簡略化する技術の提供。【解決手段】ＩＤで識別される地図に関する要素を示す蓄積情報を記録する記録媒体と、更新前の前記蓄積情報を最新バージョンにするために基準バージョンより後に更新されるべき要素の全てと、前記更新されるべき要素のＩＤとを示す更新情報を取得する更新情報取得手段と、更新前の前記蓄積情報が示す要素と前記更新情報が示す要素の中からＩＤ順に処理対象の要素を選択するとともに、前記更新情報に基づいて前記処理対象の要素を更新後の前記蓄積情報とすべきか否かを判断し、更新後の前記蓄積情報とすべきと判断された前記処理対象の要素を前記記録媒体に記録して、ＩＤ順に要素が記録された更新後の前記蓄積情報を作成する蓄積情報更新手段とを構成する。【選択図】図３
2014182678.tif 000002
【特許請求の範囲】
【請求項１】
ＩＤで識別される地図に関する要素を示す蓄積情報を記録する記録媒体と、
更新前の前記蓄積情報を最新バージョンにするために基準バージョンより後に更新されるべき要素の全てと、前記更新されるべき要素のＩＤとを示す更新情報を取得する更新情報取得手段と、
更新前の前記蓄積情報が示す要素と前記更新情報が示す要素の中からＩＤ順に処理対象の要素を選択するとともに、
前記更新情報に基づいて前記処理対象の要素を更新後の前記蓄積情報とすべきか否かを判断し、更新後の前記蓄積情報とすべきと判断された前記処理対象の要素を前記記録媒体に記録して、
ＩＤ順に要素が記録された更新後の前記蓄積情報を作成する蓄積情報更新手段と、
を備えることを特徴とする地図情報更新システム。
【請求項２】
前記更新情報取得手段は、
更新前の前記蓄積情報を最新バージョンにするために基準バージョンより後に追加すべき要素の全てと削除すべき要素の全てとを示す前記更新情報を取得し、
前記蓄積情報更新手段は、
前記処理対象の要素が、前記更新情報が示す要素でなければ前記処理対象の要素を前記記録媒体に記録し、
前記処理対象の要素が、前記更新情報が示す前記追加すべき要素であれば前記処理対象の要素を前記記録媒体に記録し、
前記処理対象の要素が、前記更新情報が示す前記削除すべき要素であれば前記処理対象の要素は前記記録媒体に記録しない、
請求項１に記載の地図情報更新システム。
【請求項３】
前記蓄積情報更新手段は、
ＩＤの昇順あるいは降順を処理順序とし、
未処理の要素であるとともに前記処理順序が最も早いＩＤが対応づけられた要素を更新前の前記蓄積情報が示す要素および前記更新情報が示す前記追加すべき要素から一つずつ取得してＩＤを比較し、前記処理順序が早いＩＤの要素を前記処理対象の要素として選択する、
請求項２に記載の地図情報更新システム。
【請求項４】
前記蓄積情報更新手段は、
前記処理対象の要素が、更新前の前記蓄積情報が示す要素であり、かつ、前記更新情報が示す前記追加すべき要素ではない場合、前記処理対象の要素が、前記更新情報が示す前記削除すべき要素であるか否かを前記更新情報に基づいて判定する、
請求項３に記載の地図情報更新システム。
【請求項５】
前記蓄積情報更新手段は、
ＩＤの昇順あるいは降順を処理順序とし、
未処理の要素であるとともに前記処理順序が最も早いＩＤが対応づけられた要素を更新前の前記蓄積情報が示す要素および前記更新情報が示す要素から一つずつ取得してＩＤを比較し、前記処理順序が早いＩＤの要素を前記処理対象の要素として選択する、
請求項１または請求項２のいずれかに記載の地図情報更新システム。
【請求項６】
前記蓄積情報更新手段は、
前記処理対象の要素が、前記更新情報が示す要素である場合、前記処理対象の要素が追加すべき要素であるか否かを前記更新情報に基づいて判定する、
請求項１，請求項２，請求項５のいずれかに記載の地図情報更新システム。
【請求項７】
記録媒体に記録された、ＩＤで識別される地図に関する要素を示す蓄積情報を更新する蓄積情報更新方法であって、
更新前の前記蓄積情報を最新バージョンにするために基準バージョンより後に更新されるべき要素の全てと、前記更新されるべき要素のＩＤとを示す更新情報を取得する更新情報取得工程と、
更新前の前記蓄積情報が示す要素と前記更新情報が示す要素の中からＩＤ順に処理対象の要素を選択するとともに、
前記更新情報に基づいて前記処理対象の要素を更新後の前記蓄積情報とすべきか否かを判断し、更新後の前記蓄積情報とすべきと判断された前記処理対象の要素を前記記録媒体に記録して、
ＩＤ順に要素が記録された更新後の前記蓄積情報を作成する蓄積情報更新工程と、
を含むことを特徴とする地図情報更新方法。
【請求項８】
記録媒体に記録された、ＩＤで識別される地図に関する要素を示す蓄積情報を更新する機能をコンピュータに実現させる蓄積情報更新プログラムであって、
更新前の前記蓄積情報を最新バージョンにするために基準バージョンより後に更新されるべき要素の全てと、前記更新されるべき要素のＩＤとを示す更新情報を取得する更新情報取得機能と、
更新前の前記蓄積情報が示す要素と前記更新情報が示す要素の中からＩＤ順に処理対象の要素を選択するとともに、
前記更新情報に基づいて前記処理対象の要素を更新後の前記蓄積情報とすべきか否かを判断し、更新後の前記蓄積情報とすべきと判断された前記処理対象の要素を前記記録媒体に記録して、
ＩＤ順に要素が記録された更新後の前記蓄積情報を作成する蓄積情報更新機能と、
をコンピュータに実現させることを特徴とする地図情報更新プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記録媒体に記録された蓄積情報を更新する地図情報更新システム、方法およびプログラムに関する。
【背景技術】
【０００２】
従来、記録媒体に記録された蓄積情報を利用して運用されるシステムにおいて、運用過程で差分情報を配信し、当該蓄積情報を更新する技術が知られている。例えば、特許文献１においては、ナビゲーションシステム等において利用される地図情報を差分データで更新する技術が開示されている。また、当該特許文献１においては、地図情報および差分データをバージョンで管理し、ローカルに保存されているバージョンより新しいバージョンの差分データの全てを取得し、取得した差分データを全て適用することで、地図情報を最新の状態にすることができる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−３２８７３９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述した従来技術のように、蓄積情報を更新する度に差分データを定義する構成においては、複数のバージョンに渡る更新を行うための処理が煩雑になる。すなわち、各差分データは、互いに内容が異なるため、蓄積情報を最新の情報に更新するためには、ローカルに保存されているバージョンより新しいバージョンの差分データの全てを取得し、それぞれの差分データによる更新処理をバージョン順に全て実行する必要があった。そして、複数の（多数の）配信対象端末が運用されている環境において、配信対象端末が利用されるタイミングは一定ではなく、差分データの適用状態（ローカルに保持された蓄積情報のバージョン）も一定ではない。従って、差分データの配信を行うサーバにおいては、配信対象端末毎に異なり得る差分データを送信対象とする処理を、配信対象毎に異なるタイミングで実行する必要があり、処理が極めて煩雑になる。
【０００５】
また、配信対象端末において複数のバージョンの差分データを取得した場合、あるバージョンの差分データによる更新を完了させた後に、次のバージョンの差分データによる更新を完了させるという処理を順次実行する必要があり、処理が極めて複雑になる。そして、この場合において更新後の蓄積情報を高速で参照可能にするためには、さらに複雑な処理が必要になってしまう。すなわち、蓄積情報が道路区間などの多数の要素を示している場合、経路探索等の処理で要素を利用する際には多数の要素の中から利用対象の要素を検索する必要がある。
【０００６】
このような場合、検索速度を高速化するため、要素が所定の順序に並ぶように蓄積情報を定義することが一般的である。すなわち、要素を示す情報には、要素を一義的に特定可能な情報（ＩＤ）が含まれ、ＩＤが昇順（あるいは降順）に並ぶように蓄積情報を定義するのが一般的である。しかし、特許文献１に開示された従来技術においては、バージョン毎の差分データに基づいて「追加」「変更」「削除」を行う場合、ＩＤが昇順（あるいは降順）に維持されたまま「追加」「変更」「削除」を行うことはできない。例えば、既存の要素の変更を行う場合、変更前後の要素の情報量が異なり得るため、変更前の要素を変更後の要素で上書きすることはできず、既存の要素を削除し、別の記憶領域に変更後の要素の情報を記録せざるを得ない。従って、バージョン毎の差分データに基づいて「追加」「変更」「削除」を行う場合、「追加」「変更」「削除」が全ての要素について終了した後に、全ての要素をＩＤ順に並び替える必要があり、処理が極めて複雑になってしまう。
本発明は、前記課題にかんがみてなされたもので、蓄積情報の更新に関わる処理を簡略化する技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
前記の目的を達成するため、本発明においては、ＩＤで識別される地図に関する要素を示す蓄積情報を記録する記録媒体と、更新前の蓄積情報を最新バージョンにするために基準バージョンより後に更新されるべき要素の全てと、更新されるべき要素のＩＤとを示す更新情報を取得する更新情報取得手段と、更新前の蓄積情報が示す要素と更新情報が示す要素の中からＩＤ順に処理対象の要素を選択するとともに、更新情報に基づいて処理対象の要素を更新後の蓄積情報とすべきか否かを判断し、更新後の蓄積情報とすべき処理対象の要素を記録媒体に記録して、ＩＤ順に要素が記録された更新後の蓄積情報を作成する蓄積情報更新手段と、が構成される。
【０００８】
すなわち、更新前の蓄積情報を最新バージョンにするために基準バージョンより後に更新されるべき要素の全てと、更新されるべき要素のＩＤとを示す更新情報を定義する。このため、当該更新情報を参照すれば、基準バージョンより後のいかなるバージョンの蓄積情報であっても、更新すべき要素を更新することが可能になり、基準バージョンより後のバージョンの蓄積情報が記録媒体に記録された全ての端末において蓄積情報を更新することが可能になる。
【０００９】
従って、更新情報を配信するサーバにおいては、配信先の端末の記録媒体に、基準バージョン以後のバージョンの蓄積情報が記録されている限り、配信先の端末の記録媒体に記録された蓄積情報のバージョンを考慮することなく、共通の更新情報を配信すれば良く、極めて簡易な処理によって更新情報を配信することが可能になる。また、更新情報を取得する地図情報更新システムにおいては、異なるバージョンの蓄積情報を順次更新するための更新情報を複数個取得することはなく、蓄積情報の更新においても複数のバージョンについての更新を累積的に実行する必要はない。従って、どのタイミングで更新情報を取得したとしても、同じフォーマットの更新情報に基づいて同じ処理を一回実行すれば更新を完了することができ、簡易な処理で蓄積情報を更新することができる。
【００１０】
さらに、本発明においては、処理対象の要素のそれぞれについて、処理対象の要素を更新後の蓄積情報とすべきか否かを判断し、判断結果に応じて処理対象の要素を記録媒体に記録し、または記録しない処理を行う。そして、処理対象の要素は、更新前の蓄積情報が示す要素と更新情報が示す要素の中からＩＤ順に選択されるため、ＩＤ順に蓄積情報が記録された状態で更新後の蓄積情報が構築される。従って、記録媒体への記録と同時にＩＤの順序によるソートもなされるように蓄積情報が構築され、ＩＤ順に要素が記録された更新後の蓄積情報を容易に作成することができる。
【００１１】
ここで、記録媒体は、ＩＤで識別される地図に関する要素を示す蓄積情報を記録できれば良く、記録媒体の種類は特に限定されない。また、蓄積情報が示す要素は、ＩＤ順に記録されていることによって検索が高速化されるような要素であれば良く、数が極めて多い要素や複数の要素が複雑に関係している要素であることが好ましい。このような要素としては、例えば、地図情報が示す道路区間に関する情報や交差点に関する情報等が挙げられる。ＩＤは、要素に対して一対一に対応づけられていれば良いが、蓄積情報が利用される態様に応じてＩＤ付与の指針が決定されていても良い。例えば、道路区間の連結順にＩＤを付与するなどの構成を採用可能である。
【００１２】
更新情報取得手段は、更新前の蓄積情報を最新バージョンにするために基準バージョンより後に更新されるべき要素の全てと、更新されるべき要素のＩＤとを示す更新情報を取得することができればよい。すなわち、蓄積情報を基準バージョンから最新バージョンにするために必要な要素の変更の全てを特定できるように定義された更新情報を取得することができればよい。なお、基準バージョンは、ある基準時点における蓄積情報であれば良く、作成された当初の蓄積情報のバージョンであっても良いし、ある時点（例えば、蓄積情報を参照するナビゲーション装置を搭載した車両の販売開始時点）における蓄積情報のバージョンであっても良い。なお、更新されるべき要素のＩＤは、更新情報が示す要素に対応づけられた状態で定義されても良いし、更新されるべき要素のＩＤを抽出した状態（リスト化した状態）で定義されても良い。
【００１３】
蓄積情報更新手段は、更新前の蓄積情報が示す要素と更新情報が示す要素の中からＩＤ順に処理対象の要素を選択するとともに、更新情報に基づいて処理対象の要素を更新後の蓄積情報とすべきか否かを判断し、更新後の蓄積情報とすべき処理対象の要素を記録媒体に記録して、ＩＤ順に要素が記録された更新後の蓄積情報を作成することができればよい。すなわち、更新前の蓄積情報が示す要素がＩＤ順に並んでいたとしても、更新情報が示す要素を更新前の蓄積情報の最後に対して単に追加するのみでは、各要素をＩＤ順に並べることはできない（追加する要素のＩＤが更新前の蓄積情報のいずれかより先の順序である場合等があり得る）。
【００１４】
そこで、更新前の蓄積情報と更新情報との双方を対象とし、ＩＤをキーにして処理対象を特定することにより、更新前の蓄積情報と更新情報との双方が示す要素の全てをＩＤ順に処理対象とする。このように、更新前の蓄積情報と更新情報との双方が示す要素の全てをＩＤ順に処理対象として、更新後の蓄積情報を構築していけば、更新前の蓄積情報と更新情報との双方が示す要素の全てをもれなくＩＤ順に処理対象とすることができ、ＩＤ順に要素が記録された更新後の蓄積情報を容易に作成することができる。
【００１５】
処理対象の要素を更新後の蓄積情報とすべきか否かを判断する際には、更新情報が示す要素に基づいて論理的に判断が可能である。すなわち、更新情報には更新されるべき要素の全てが含まれているため、更新情報に含まれる要素の全ては更新対象となり、更新情報が示すとおりの更新が行われるべきであると判断される。更新情報に含まれない要素は更新対象でないため、更新情報に含まれないが更新前の蓄積情報に含まれる要素は、更新前の蓄積情報と同一の情報が更新後の蓄積情報とすべきと判断される。
【００１６】
処理対象の要素を更新後の蓄積情報とすべきか否かを判断するための具体的な構成としては種々の構成を採用可能である。例えば、更新前の蓄積情報を最新バージョンにするために基準バージョンより後に追加すべき要素の全てと削除すべき要素の全てとを示す更新情報を取得し、処理対象の要素が、更新情報が示す要素でなければ処理対象の要素を記録媒体に記録し、処理対象の要素が、更新情報が示す追加すべき要素であれば処理対象の要素を記録媒体に記録し、処理対象の要素が、更新情報が示す削除すべき要素であれば処理対象の要素は記録媒体に記録しない構成としても良い。
【００１７】
すなわち、更新情報が追加すべき要素と削除すべき要素とを示すように構成すれば、処理対象の要素が、更新情報が示す要素でない場合に、処理対象の要素は追加されず削除もされないこと、すなわち、更新前の蓄積情報と同一の情報となるべきであると判断することができる。そこで、処理対象の要素が、更新情報が示す要素でない場合に、処理対象の要素（＝更新前の蓄積情報が示す要素）を記録媒体に記録すれば、更新されていない要素が適切に更新後の蓄積情報に含まれた状態で更新後の蓄積情報を記録媒体に記録することができる。
【００１８】
さらに、処理対象の要素が追加すべき要素として更新情報に示された要素であれば、処理対象の要素は更新後の蓄積情報として記録されるべきと判断することができる。そこで、処理対象の要素が追加すべき要素として更新情報に示された要素である場合に、処理対象の要素を記録媒体に記録すれば、追加された要素を容易に更新後の蓄積情報に対して記録媒体に記録することができる。さらに、処理対象の要素が削除すべき要素として更新情報に示された要素であれば、処理対象の要素は更新後の蓄積情報として記録されるべきでないと判断することができる。そこで、処理対象の要素が削除すべき要素として更新情報に示された要素である場合に、処理対象の要素を記録媒体に記録しないようにすれば、削除された要素を確実に更新前の蓄積情報から除外した状態で更新後の蓄積情報を記録媒体に記録することができる。
【００１９】
さらに、更新前の蓄積情報が示す要素と更新情報が示す要素の中からＩＤ順に処理対象の要素を選択するための構成としては種々の構成を採用可能であり、例えば、ＩＤの昇順あるいは降順を処理順序とし、未処理の要素であるとともに処理順序が最も早いＩＤが対応づけられた要素を更新前の蓄積情報が示す要素および更新情報が示す追加すべき要素から一つずつ取得してＩＤを比較し、処理順序が早いＩＤの要素を処理対象の要素として選択する構成であっても良い。すなわち、この処理によれば、更新前の蓄積情報が示す要素および更新情報が示す追加すべき要素の全てをＩＤ順にもれなく選択して処理対象とすることができる。削除すべき要素が存在する場合、当該要素は必ず更新前の蓄積情報に含まれるため、削除すべき要素を除いて、更新前の蓄積情報が示す要素および更新情報が示す追加すべき要素から一つずつ取得してＩＤを比較したとしても、全ての要素をＩＤ順にもれなく選択して処理対象とすることができる。なお、未処理の要素であるとともに処理順序が最も早いＩＤが対応づけられた要素を更新前の蓄積情報が示す要素および更新情報が示す追加すべき要素から一つずつ取得してＩＤを比較した結果、両者のＩＤが同一である場合、当該ＩＤの要素が追加されるべきことが更新情報で示されるため、更新情報に含まれる追加すべき要素を処理対象の要素として選択すればよい。
【００２０】
要素を更新前の蓄積情報が示す要素および更新情報が示す追加すべき要素から一つずつ取得してＩＤを比較する構成の場合、処理対象の要素が、更新前の蓄積情報が示す要素であり、かつ、更新情報が示す追加すべき要素ではない場合、処理対象の要素が、更新情報が示す削除すべき要素であるか否かを更新情報に基づいて判定する構成としても良い。すなわち、更新前の蓄積情報が示す要素は、削除されるか更新後の蓄積情報に記録されるかのいずれかであるため、処理対象の要素が、更新前の蓄積情報が示す要素であり、かつ、更新情報が示す追加すべき要素ではない場合には、削除すべき要素であるか否かを判定すれば、蓄積情報の更新に際して処理対象の要素をどのように扱うべきか確定することが可能である。
【００２１】
さらに、ＩＤの昇順あるいは降順を処理順序とし、未処理の要素であるとともに処理順序が最も早いＩＤが対応づけられた要素を更新前の蓄積情報が示す要素および更新情報が示す要素から一つずつ取得してＩＤを比較し、処理順序が早いＩＤの要素を処理対象の要素として選択する構成としても良い。以上の構成によれば、全ての要素をＩＤ順にもれなく選択して処理対象とすることができる。また、ＩＤが仮に連続する番号でなくても、容易に各要素をＩＤ順に処理対象とすることができる。なお、未処理の要素であるとともに処理順序が最も早いＩＤが対応づけられた要素を更新前の蓄積情報が示す要素および更新情報が示す要素から一つずつ取得してＩＤを比較した結果、両者のＩＤが同一である場合、当該ＩＤの要素が追加されるべきか否かが確定されれば、当該ＩＤの要素の扱いを確定することができるため、更新情報が示す要素を処理対象の要素として選択すればよい。
【００２２】
要素を更新前の蓄積情報が示す要素および更新情報が示す要素から一つずつ取得してＩＤを比較する構成の場合、処理対象の要素が、更新情報が示す要素である場合、処理対象の要素が追加すべき要素であるか否かを更新情報に基づいて判定する構成としても良い。すなわち、更新情報が示す要素は、追加されるか削除されるかのいずれかであるため、追加すべき要素であるか否かを判定すれば、蓄積情報の更新に際して処理対象の要素をどのように扱うべきか確定することが可能である。そこで、処理対象の要素が、更新情報が示す要素である場合、処理対象の要素が追加すべき要素であるか否かを更新情報に基づいて判定する構成とすれば、簡易な処理により、更新情報が示す要素の扱いを特定することが可能である。むろん、処理対象の要素が、更新情報が示す要素である場合、当該要素が削除すべき要素であるか否かを更新情報に基づいて判定することで処理対象の要素をどのように扱うべきか確定する構成であっても良い。
【００２３】
さらに、本発明のように、更新前の蓄積情報が示す要素と更新情報が示す要素の中からＩＤ順に処理対象の要素を選択して蓄積情報を記録媒体に記録するための処理を行うことでＩＤ順に要素が記録された更新後の蓄積情報を作成する手法は、プログラムや方法としても適用可能である。また、以上のようなシステム、プログラム、方法は、単独の装置として実現される場合や、複数の装置によって実現される場合、他の装置と共有の部品を利用して実現される場合が想定可能であり、各種の態様を含むものである。また、一部がソフトウェアであり一部がハードウェアであったりするなど、適宜、変更可能である。さらに、システムを制御するプログラムの記録媒体としても発明は成立する。むろん、そのソフトウェアの記録媒体は、磁気記録媒体であってもよいし光磁気記録媒体であってもよいし、今後開発されるいかなる記録媒体においても全く同様に考えることができる。
【図面の簡単な説明】
【００２４】
【図１】地図情報更新システムを示すブロック図である。
【図２】蓄積情報更新処理を示すフローチャートである。
【図３】（３Ａ）は更新前の蓄積情報、（３Ｂ）は更新情報、（３Ｃ）は更新後の蓄積情報を模式的に示す図である。
【発明を実施するための形態】
【００２５】
ここでは、下記の順序に従って本発明の実施の形態について説明する。
（１）ナビゲーション端末の構成：
（２）蓄積情報更新処理：
（３）他の実施形態：
【００２６】
（１）ナビゲーション端末の構成：
図１は、車両Ｃに搭載された地図情報更新システムの構成を示すブロック図である。本実施形態において地図情報更新システムは、車両Ｃに搭載されるナビゲーション端末１０によって実現される。ナビゲーション端末１０は、ＣＰＵ、ＲＡＭ、ＲＯＭ等を備える制御部２０を備えており、ＲＯＭに記憶されたプログラムを制御部２０で実行することができる。本実施形態においては、このプログラムとしてナビゲーションプログラムおよび蓄積情報更新プログラムを実行可能である。
【００２７】
本実施形態にかかるナビゲーション端末１０は、ＧＰＳ受信部４１と車速センサ４２とジャイロセンサ４３とユーザＩ／Ｆ部４４と通信部４５とを備えている。ＧＰＳ受信部４１は、ＧＰＳ衛星からの電波を受信し、図示しないインタフェースを介して車両Ｃの現在地を算出するための信号を示す信号を出力する。制御部２０は、この信号を取得して車両Ｃの現在地を取得する。車速センサ４２は、車両Ｃが備える車輪の回転速度に対応した信号を出力する。制御部２０は、図示しないインタフェースを介してこの信号を取得し、車速を取得する。ジャイロセンサ４３は、車両Ｃの水平面内の旋回についての角加速度を検出し、車両Ｃの向きに対応した信号を出力する。制御部２０は、この信号を取得して車両Ｃの進行方向を取得する。車速センサ４２およびジャイロセンサ４３等は、車両Ｃの走行軌跡を特定するために利用され、本実施形態においては、車両Ｃの出発地と走行軌跡とに基づいて現在地が特定され、当該出発地と走行軌跡とに基づいて特定された車両Ｃの現在地がＧＰＳ受信部４１の出力信号に基づいて補正される。
【００２８】
ユーザＩ／Ｆ部４４は、運転者の指示を入力し、また運転者に各種の情報を提供するためのインタフェース部であり、図示しないタッチパネルディスプレイからなる入力部を兼ねた表示部やスピーカー等の出力音の出力部を備えている。ユーザＩ／Ｆ部４４は制御信号を制御部２０から受信し、各種案内を行うための画像をタッチパネルディスプレイに表示し、各種案内を行うための出力音をスピーカーから出力する。また、ユーザＩ／Ｆ部４４は、タッチパネルを介した入力内容を示す信号を制御部２０に送信し、制御部２０は当該信号に基づいて利用者の操作内容を特定する。通信部４５は、無線通信を行うための回路にて構成され、制御部２０は通信部４５を制御して蓄積情報管理サーバＳと通信を行うことができる。
【００２９】
記録媒体３０には蓄積情報３０ａが予め記録されている。蓄積情報３０ａは、ＩＤで識別される地図に関する要素を示す情報であり、車両Ｃが走行する道路の端点に対応するノードの位置等を示すノードデータ、ノード間の道路の形状を特定するための形状補間点の位置等を示す形状補間点データ、ノード同士の連結を示すリンクデータ等を示している。なお、本実施形態においてリンクデータは、ノード間に存在するリンク（道路区間）を示しており、要素である道路区間を示すデータである。
【００３０】
本実施形態においては、リンクデータに対して一対一にＩＤ（リンク毎にユニークな数値）が対応づけられている。さらに、本実施形態においては、リンクデータがＩＤ順に記録媒体３０に記録されている。すなわち、地図を構成するために必要なリンクの数は極めて多数であるとともにリンク同士が複雑に関係しているため、上述の経路探索や地図表示のために記録媒体３０からリンクデータが検索される際に、リンクデータをＩＤ順に検索することによって所望のＩＤを高速に検索できるように構成されている。
【００３１】
図３Ａは、更新前の蓄積情報３０ａの例を模式的に示す図である。同図３Ａの左側には細い実線の矩形でメッシュを示しており、太い実線で代表的なリンクを示している。また、各リンクにはＩＤ（図３Ａ内で＃の横に付された数値）を付記して示している。図３Ａの右側には、太い実線の矩形内にリンクデータが記録媒体３０に記録される順序を示しており、当該図３Ａの右側に示す通り、ＩＤの昇順にリンクデータが記録媒体３０に記録されている。
【００３２】
ナビゲーションプログラムは、表示部に車両Ｃの現在地が含まれる地図を表示し、運転者が指定した出発地から目的地までの走行予定経路を探索し、走行予定経路に沿って運転者を目的地まで案内する機能を制御部２０に実現させるプログラムである。すなわち、制御部２０は、ナビゲーションプログラムの処理により、ＧＰＳ受信部４１、車速センサ４２、ジャイロセンサ４３の出力信号に基づいて車両の現在地を取得する。また、制御部２０は、ナビゲーションプログラムの処理により、蓄積情報３０ａを参照して現在地周辺の地図を描画するための画像データを生成し、ユーザＩ／Ｆ部４４の表示部に対して出力する。この結果、ユーザＩ／Ｆ部４４の表示部に現在地周辺の地図が表示される。さらに、制御部２０は、ユーザＩ／Ｆ部４４の入力部に対する利用者の入力に応じて目的地を取得し、蓄積情報３０ａを参照して現在地から目的地までの経路を探索する。
【００３３】
以上のように、本実施形態における蓄積情報３０ａは地図情報として利用される。そして、道路の新設や改修などが行われると、蓄積情報３０ａが示す道路と現実の道路とが異なる状態になるため、本実施形態においては蓄積情報管理サーバＳにおいて所定期間毎に蓄積情報３０ａを更新し、ナビゲーション端末１０に配信するように構成されている。
【００３４】
制御部２０は、蓄積情報更新プログラム２１を実行することにより、更新情報と更新前の蓄積情報３０ａとから更新後の蓄積情報３０ａを生成する処理を行う。この処理を実行するため、蓄積情報更新プログラム２１は、更新情報取得部２１ａと蓄積情報更新部２１ｂとを備えている。
【００３５】
更新情報取得部２１ａは、更新前の蓄積情報３０ａを最新バージョンにするために基準バージョンより後に更新されるべきリンクの全てと、更新されるべきリンクのＩＤとを示す更新情報を取得する機能を制御部２０に実現させるプログラムモジュールである。すなわち、制御部２０は、更新情報取得部２１ａの処理により、通信部４５を介して蓄積情報管理サーバＳから更新情報を取得し、記録媒体３０に記録する（更新情報３０ｂ）。
【００３６】
本実施形態において、更新情報３０ｂは、蓄積情報３０ａを基準バージョンから最新バージョンにするために必要なリンクの変更の全てを特定できるように定義されている。具体的には、更新前の蓄積情報３０ａを最新バージョンにするために基準バージョンより後に追加すべきリンクの全についてのリンクデータと、追加すべきリンクの全についてのリンクデータに対応づけられたＩＤのリスト（追加リンクリストと呼ぶ）と、更新前の蓄積情報３０ａから削除すべきリンクの全てについてのリンクデータに対応づけられたＩＤのリスト（削除リンクリストと呼ぶ）とによって、更新情報３０ｂが構成されている。
【００３７】
図３Ｂは、更新情報３０ｂの例を模式的に示す図である。同図３Ｂの左側には細い実線の矩形で図３Ａに示すメッシュと同一のメッシュを示しており、太い破線で追加すべきリンクを示している。また、各リンクに対応づけられたＩＤを＃の横に付された数値で各リンクに付記して示している。図３Ｂの右側には、追加リンクリストと削除リンクリストの例を示しており、追加リンクリストにおいては図３Ｂの左側に含まれる追加リンクの全てについてのＩＤが昇順に記述されている。削除リンクにおいては図３Ａに示す更新前の蓄積情報３０ａから削除すべき削除リンクの全てについてのＩＤが昇順に記述されている。
【００３８】
なお、本実施形態における追加リンクおよび削除リンクは、基準バージョンの蓄積情報３０ａに追加すべきリンク、あるいは削除すべきリンクである。また、基準バージョンは、ある基準時点における蓄積情報のバージョンであれば良く、本実施形態においては、蓄積情報３０ａが作成された当初のバージョンである。
【００３９】
蓄積情報更新部２１ｂは、更新前の蓄積情報３０ａが示すリンクと更新情報３０ｂが示すリンクの中からＩＤ順に処理対象のリンクを選択するとともに、更新情報３０ｂに基づいて処理対象のリンクを更新後の蓄積情報３０ａとすべきか否かを判断し、更新後の蓄積情報３０ａとすべき処理対象のリンクを記録媒体に記録して、ＩＤ順にリンクが記録された更新後の蓄積情報３０ａを作成する機能を制御部２０に実現させるプログラムモジュールである。すなわち、更新前の蓄積情報３０ａが示すリンクがＩＤ順に並んでいたとしても、更新情報３０ｂが示すリンクを更新前の蓄積情報３０ａの最後に対して単に追加するのみでは、各リンクをＩＤ順に並べることはできない。例えば、ＩＤ＃１〜＃５のリンクが更新前の蓄積情報３０ａに含まれ、ＩＤ＃３の追加すべきリンクが更新情報３０ｂに含まれる場合、更新前の蓄積情報３０ａからＩＤ＃３のリンクを削除して更新情報３０ｂに示された＃ＩＤのリンクを単に追加してもＩＤは＃１，２，４，５，３となり、ＩＤ順にはならない。
【００４０】
そこで、制御部２０は、更新前の蓄積情報３０ａと更新情報３０ｂとの双方を対象とし、ＩＤをキーにして処理対象を特定することにより、更新前の蓄積情報３０ａと更新情報３０ｂとの双方が示すリンクの全てをＩＤ順に処理対象とする。このように、更新前の蓄積情報３０ａと更新情報３０ｂとの双方が示すリンクの全てをＩＤ順に処理対象として、更新後の蓄積情報３０ａをＩＤ順に構築していけば、更新前の蓄積情報３０ａと更新情報３０ｂとの双方が示すリンクの全てをもれなくＩＤ順に処理対象とすることができ、ＩＤ順にリンクが記録された更新後の蓄積情報３０ａを容易に作成することができる。
【００４１】
処理対象のリンクを更新後の蓄積情報３０ａとすべきか否かを判断する際には、更新情報３０ｂが示すリンクに基づいて論理的に判断が可能である。すなわち、更新情報３０ｂには更新されるべきリンクの全てが含まれているため、更新情報３０ｂに含まれるリンクの全ては更新対象となり、更新情報３０ｂが示すとおりの更新が行われるべきであると判断される。更新情報３０ｂに含まれないリンクは更新対象でないため、更新情報３０ｂに含まれないが更新前の蓄積情報３０ａに含まれるリンクは、更新前の蓄積情報３０ａと同一の情報が更新後の蓄積情報３０ａとすべきと判断される。
【００４２】
より具体的には、本実施形態において制御部２０は、蓄積情報更新部２１ｂの処理により、処理対象のリンクが、更新情報３０ｂが示すリンクでなければ処理対象のリンク（＝更新前の蓄積情報３０ａが示すリンク）を記録媒体３０に記録する。さらに、制御部２０は、蓄積情報更新部２１ｂの処理により、処理対象のリンクが更新情報３０ｂの追加リンクリストが示すリンクであれば処理対象のリンクを記録媒体３０に記録する。一方、制御部２０は、処理対象のリンクが更新情報３０ｂの削除リンクリストが示すリンクであれば処理対象のリンクは記録媒体３０に記録しない。
【００４３】
すなわち、追加リンクリストと削除リンクリストとを含む更新情報３０ｂを定義しておけば、処理対象のリンクが、更新情報３０ｂが示すリンクでない場合に、処理対象のリンクは追加されず削除もされないこと、すなわち、更新前の蓄積情報３０ａと同一の情報となるべきであると判断することができる。例えば、図３Ａに示すＩＤ＃２，＃４，＃３０等のリンクは、図３Ｂに示す追加リンクリスト、削除リンクリストの双方に記述されていないため、これらのリンクについては更新前の蓄積情報３０ａと同一の情報が再度更新後の蓄積情報３０ａとして記録されるべきであると判断することができる。そこで、処理対象のリンクが、更新情報３０ｂが示すリンクでない場合に、制御部２０が、更新前の蓄積情報３０ａが示す処理対象のリンクを記録媒体３０に記録する構成とすれば、更新されていないリンクが適切に更新後の蓄積情報３０ａに含まれた状態で更新後の蓄積情報３０ａを記録媒体３０に記録することができる。
【００４４】
さらに、処理対象のリンクが、更新情報３０ｂの追加リンクリストが示すリンクであれば、処理対象のリンクは更新後の蓄積情報３０ａとして記録されるべきと判断することができる。例えば、図３Ｂの追加リンクリストに示されたＩＤ＃３，＃６，＃１０１，＃１０２等のリンクは、当該リンクについてのリンクデータが更新後の蓄積情報３０ａとして記録されるべきであると判断することができる。そこで、処理対象のリンクが追加リンクリストに示されたリンクである場合に、制御部２０が、処理対象のリンクを記録媒体３０に記録する構成とすれば、追加されたリンクを容易に更新後の蓄積情報３０ａに対して記録媒体３０に記録することができる。
【００４５】
さらに、処理対象のリンクが、更新情報３０ｂの削除リンクリストが示すリンクであれば、処理対象のリンクは更新後の蓄積情報３０ａとして記録されるべきでないと判断することができる。例えば、図３Ｂの削除リンクリストに示されたＩＤ＃１，＃５のリンクは、当該リンクについてのリンクデータが更新後の蓄積情報３０ａとして記録されるべきでないと判断することができる。そこで、処理対象のリンクが削除リンクリストに示されたリンクである場合に、制御部２０が、処理対象のリンクを記録媒体３０に記録しない構成とすれば、削除されたリンクを確実に更新前の蓄積情報３０ａから除外した状態で更新後の蓄積情報３０ａを記録媒体３０に記録することができる。
【００４６】
図３Ｃは、図３Ａに示す更新前の蓄積情報３０ａと図３Ｂに示す更新情報３０ｂとに基づいて更新された更新後の蓄積情報３０ａの例を模式的に示す図である。同図３Ｃの左側には細い実線の矩形で図３Ａに示すメッシュと同一のメッシュを示している。また、太い実線で更新前の蓄積情報３０ａと同一の情報で構成された蓄積情報３０ａを示し、太い破線で更新情報３０ｂに基づいて構成された蓄積情報３０ａを示している。また、各リンクにはＩＤ（図３Ｃ内で＃の横に付された数値）を付記して示している。図３Ｃの右側には、太い実線の矩形内にリンクデータが記録媒体３０に記録される順序を示しており、当該図３Ｃの右側に示す通り、ＩＤの昇順にリンクデータが記録媒体３０に記録されている。
【００４７】
そして、更新後の蓄積情報３０ａが示すリンクは、更新情報３０ｂが示す更新が適切に適用された状態となっている。例えば、リンクＩＤ＃１は、図３Ｂに示す削除リンクリストに含まれているため、更新後の蓄積情報３０ａとしては記録されていない。リンクＩＤ＃２は、図３Ｂに示す追加リンクリスト、削除リンクリストのいずれにも含まれていないため、更新前の蓄積情報３０ａと同一の情報が更新後の蓄積情報３０ａとして記録されていることになる。リンクＩＤ＃３は、図３Ｂに示す追加リンクリストに含まれているため、更新情報３０ｂが示すリンクデータが更新後の蓄積情報３０ａとして記録されていることになる。
【００４８】
以上のように、本実施形態においては、更新前の蓄積情報３０ａと更新情報３０ｂとに基づいて更新後の蓄積情報３０ａを記録媒体に３０記録する。ここで、更新情報３０ｂは、更新前の蓄積情報３０ａを最新バージョンにするために基準バージョンより後に更新されるべきリンクの全てと、更新されるべきリンクのＩＤとを示す更新情報３０ｂを定義する。このため、当該更新情報３０ｂを参照すれば、基準バージョンより後のいかなるバージョンの蓄積情報３０ａであっても、更新すべきリンクを更新することが可能になり、基準バージョンより後のバージョンの蓄積情報３０ａが記録媒体３０に記録された全ての端末において蓄積情報３０ａを更新することが可能になる。
【００４９】
従って、更新情報３０ｂを配信する蓄積情報管理サーバＳにおいては、配信先の端末の記録媒体３０に、基準バージョン以後のバージョンの蓄積情報３０ａが記録されている限り、配信先の端末の記録媒体３０に記録された蓄積情報３０ａのバージョンを一切考慮することなく、共通の更新情報３０ｂを配信すれば良く、極めて簡易な処理によって更新情報３０ｂを配信することが可能になる。また、更新情報３０ｂを取得するナビゲーション端末１０においては、異なるバージョンの蓄積情報３０ａを順次更新するための更新情報を複数個取得することはなく、蓄積情報３０ａの更新も複数のバージョンについての更新を累積的に実行する必要はない。従って、どのタイミングで更新情報３０ｂを取得したとしても、同じフォーマットの更新情報３０ｂに基づいて同じ処理を一回実行すれば更新を完了することができ、簡易な処理で蓄積情報３０ａを更新することができる。
【００５０】
さらに、本発明においては、処理対象のリンクのそれぞれについて、処理対象のリンクを更新後の蓄積情報３０ａとすべきか否かを判断し、判断結果に応じて処理対象のリンクを記録媒体３０に記録し、または記録しない処理を行う。そして、処理対象のリンクは、更新前の蓄積情報３０ａが示すリンクと更新情報３０ｂが示すリンクの中からＩＤ順に選択されるため、ＩＤ順に蓄積情報が記録された状態で更新後の蓄積情報３０ａが構築される。従って、記録媒体３０への記録と同時にＩＤの順序によるソートもなされるように蓄積情報３０ａが構築され、ＩＤ順にリンクが記録された更新後の蓄積情報３０ａを容易に作成することができる。
【００５１】
（２）蓄積情報更新処理：
次に、蓄積情報更新処理について詳細に説明する。図２は、蓄積情報更新処理のフローチャートである。本実施形態において、蓄積情報更新処理は、蓄積情報の更新要求が行われた場合に実行される。なお、蓄積情報の更新要求は、種々のタイミングで実行可能であり、例えば、利用者が指示を行ったタイミングやナビゲーション端末１０が起動されたタイミング、更新要求が行われてから所定期間経過後のタイミング等で実行可能である。
【００５２】
蓄積情報更新処理において、制御部２０は、更新情報取得部２１ａの処理により、更新情報を取得する（ステップＳ１００）。すなわち、蓄積情報の更新要求が行われると当該蓄積情報の更新要求が蓄積情報管理サーバＳに対して送信され、蓄積情報の更新要求を受信した蓄積情報管理サーバＳは更新情報３０ｂをナビゲーション端末１０に対して送信する。そこで、制御部２０は、通信部４５を介して蓄積情報管理サーバＳが送信する更新情報３０ｂを取得し、記録媒体３０に記録する。
【００５３】
次に、制御部２０は、更新前の蓄積情報３０ａが示すリンクと更新情報３０ｂが示すリンクの中からＩＤ順に処理対象のリンクを選択するための処理を行う。本実施形態においては、当該選択を行うため、ＩＤの昇順を処理順序としており（降順を処理順序とすることも可能）、未処理のリンクであるとともに処理順序が最も早いＩＤが対応づけられたリンクを更新前の蓄積情報３０ａが示すリンクおよび更新情報３０ｂの追加リンクリストが示すリンクから一つずつ取得してＩＤを比較し、ＩＤが小さい方のリンクを処理対象のリンクとして選択する。
【００５４】
このために、制御部２０は、蓄積情報更新部２１ｂの処理により、更新情報３０ｂの追加リンクリストが示すリンクから最小のＩＤが対応づけられたリンクを取得し（ステップＳ１０５）、取得されたリンクのＩＤを更新ＩＤ（更新情報３０ｂの追加リンクリストが示すリンクのＩＤを代入するための変数）に代入する（ステップＳ１１０）。例えば、図３Ｂに示す例において、更新情報３０ｂの追加リンクリストが示すリンクに対応づけられたＩＤの中で最小のＩＤはＩＤ＃３であるため、＃３が更新ＩＤに代入される。
【００５５】
次に、制御部２０は、蓄積情報更新部２１ｂの処理により、更新前の蓄積情報３０ａが示すリンクから最小のＩＤが対応づけられたリンクを取得し（ステップＳ１１５）、取得されたリンクのＩＤを蓄積ＩＤ（更新前の蓄積情報３０ａが示すリンクのＩＤを代入するための変数）に代入する（ステップＳ１２０）。例えば、図３Ａに示す例においては、更新前の蓄積情報３０ａが示すリンクに対応づけられたＩＤの中で最小のＩＤはＩＤ＃１であるため、＃１が蓄積ＩＤに代入される。
【００５６】
次に、制御部２０は、蓄積情報更新部２１ｂの処理により、更新ＩＤが蓄積ＩＤよりも小さいか否かを判定する（ステップＳ１２５）。ステップＳ１２５において、更新ＩＤが蓄積ＩＤよりも小さいと判定されない場合、制御部２０は、蓄積情報更新部２１ｂの処理により、さらに、更新ＩＤと蓄積ＩＤとが等しいか否かを判定する（ステップＳ２００）。ステップＳ１２５において、更新ＩＤが蓄積ＩＤよりも小さいと判定された場合、制御部２０は、蓄積情報更新部２１ｂの処理により、更新ＩＤで特定され、更新情報３０ｂが示すリンクを処理対象のリンクとしてステップＳ１３０〜Ｓ１５０の処理を行う。
【００５７】
また、ステップＳ２００において、更新ＩＤと蓄積ＩＤとが等しいと判定された場合、制御部２０は、蓄積情報更新部２１ｂの処理により、更新ＩＤで特定され、更新情報３０ｂが示すリンクを処理対象のリンクとしてステップＳ２０５〜Ｓ２５０の処理を行う。
【００５８】
さらに、ステップＳ２００において、更新ＩＤと蓄積ＩＤとが等しいと判定されない場合（すなわち、更新ＩＤが蓄積ＩＤよりも大きい場合）、制御部２０は、蓄積情報更新部２１ｂの処理により、蓄積ＩＤで特定され、更新前の蓄積情報３０ａが示すリンクを処理対象のリンクとしてステップＳ３００〜Ｓ３２０の処理を行う。
【００５９】
以上の処理によれば、更新ＩＤと蓄積ＩＤのうち、小さい方のＩＤが示すリンクが常に処理対象となり、更新ＩＤと蓄積ＩＤが等しければ更新ＩＤが示すリンクが処理対象となる。従って、全てのＩＤをＩＤ順にもれなく選択して処理対象とすることができる。また、ＩＤが仮に連続する番号でなくても、容易に各リンクをＩＤ順に処理対象とすることができる。なお、更新ＩＤと蓄積ＩＤが等しい場合においては、更新ＩＤが示すリンクが処理対象となるが、当該ＩＤのリンクについては追加されるべきことが更新情報３０ｂで示されるため、当該ＩＤが示す更新前の蓄積情報３０ａについては考慮するまでもなく、当該ＩＤのリンクの扱いを特定することが可能である。従って、更新ＩＤが示すリンクを処理対象のリンクとして選択すればよい。
【００６０】
このように処理対象を選択する構成において、更新ＩＤ＝蓄積ＩＤとならない場合（更新ＩＤが蓄積ＩＤより小さい場合、または、大きい場合）、小さい方のＩＤは更新前の蓄積情報３０ａが示すリンクと更新情報３０ｂの追加リンクリストが示すリンクとのいずれか一方のみを指定するＩＤである。そして、更新前の蓄積情報３０ａが示すリンクは、削除されるか更新後の蓄積情報３０ａに記録されるかのいずれかであるため、処理対象のリンクが、更新前の蓄積情報３０ａが示すリンクであり、かつ更新情報３０ｂの追加リンクリストが示すリンクではない場合には、削除すべきリンクであるか否かを判定すれば、蓄積情報３０ａの更新に際して処理対象のリンクをどのように扱うべきか確定することが可能である。
【００６１】
そこで、制御部２０は、更新ＩＤが蓄積ＩＤよりも大きい場合、制御部２０は、蓄積情報更新部２１ｂの処理により、蓄積ＩＤが削除リンクリストに含まれるか否かを判定し（ステップＳ３００）、ステップＳ３００において、蓄積ＩＤが追加リンクリストに含まれると判定されない場合、蓄積ＩＤが示すリンクを更新後の蓄積情報３０ａとして記録媒体３０に記録する（ステップＳ３０５）。すなわち、制御部２０は、蓄積ＩＤが示すリンクを削除せず、更新後の蓄積情報３０ａに記録する。ステップＳ３００において、蓄積ＩＤが削除リンクリストに含まれると判定された場合、制御部２０は、ステップＳ３０５をスキップする。すなわち、制御部２０は、蓄積ＩＤが示すリンクを更新前の蓄積情報３０ａから削除して更新後の蓄積情報３０ａを構築する。
【００６２】
ここで、ステップＳ３０５（後述するステップＳ１３５，ステップＳ２１０，Ｓ２２０も同様）において更新後の蓄積情報３０ａを記録媒体３０に記録する際には、記録媒体３０上における更新前の蓄積情報３０ａを書き換えるのではなく、記録媒体３０に新たに設定された更新後の蓄積情報３０ａの記録領域に随時追記していく。このため、図２に示す蓄積情報更新処理が終了した時点でＩＤ順に処理対象のリンクについての情報が記録された更新後の蓄積情報３０ａが作成されることになる。
【００６３】
なお、上述のように、更新ＩＤが＃３、蓄積ＩＤが＃１である状態でステップＳ３００が実行される場合、処理対象のリンクは蓄積ＩＤ＃１で示されるリンクである。そして、図３Ｂに示すように蓄積ＩＤ＃１は削除リンクリストに含まれるため、図３Ｃに示すように蓄積ＩＤ＃１は更新後の蓄積情報３０ａとして記録されない。
【００６４】
ステップＳ３００において蓄積ＩＤが削除リンクリストに含まれると判定された場合、あるいは、ステップＳ３０５が実行された場合、制御部２０は、蓄積情報更新部２１ｂの処理により、全リンクの処理が終了したか否かを判定する（ステップＳ３１０）。すなわち、制御部２０は、更新前の蓄積情報３０ａが示すリンクの中で最大値のＩＤが対応づけられたリンクを処理対象のリンクとした処理が終了し、かつ、更新情報３０ｂが示すリンクの中で最大値のＩＤが対応づけられたリンクを処理対象のリンクとした処理が終了した場合に全リンクの処理が終了したと判定する。
【００６５】
ステップＳ３１０において、全リンクの処理が終了したと判定されない場合、更新前の蓄積情報３０ａから次のＩＤが対応づけられたリンクを取得し（ステップＳ３１５）、取得されたリンクのＩＤを蓄積ＩＤに代入する（ステップＳ３２０）。ステップＳ３２０が実行されると、ステップＳ１２５以降の処理が繰り返される。ステップＳ３１０において、全リンクの処理が終了したと判定された場合、制御部２０は、蓄積情報更新処理を終了する。なお、ステップＳ３１５において、次のＩＤが存在しない場合、非常に大きい値のＩＤ（例えば、ＩＤの上限値）のＩＤを次のＩＤとして蓄積ＩＤに代入すれば良い。
【００６６】
上述のように、更新ＩＤが＃３、蓄積ＩＤが＃１である状態でステップＳ３１０が実行された場合、ステップＳ３１５，Ｓ３２０の処理により、蓄積ＩＤが＃２となる。この場合、更新ＩＤが蓄積ＩＤより大きいため、再度ステップＳ３００が実行され、図３Ｂに示すように蓄積ＩＤ＃２が削除リンクリストに含まれないため、図３Ｃに示すように蓄積ＩＤ＃２は更新後の蓄積情報３０ａとして記録される。この後に、ステップＳ３１５，Ｓ３２０が実行されると、蓄積ＩＤが＃３となり、更新ＩＤと蓄積ＩＤとが等しくなるため、ステップＳ２００の判定を経て、ステップＳ２０５以降の処理が実行される。
【００６７】
ステップＳ２０５において、制御部２０は、蓄積情報更新部２１ｂの処理により、更新ＩＤが追加リンクリストに含まれるか否かを判定する（ステップＳ２０５）。すなわち、制御部２０は、更新ＩＤで特定される更新情報３０ｂが示すリンクを処理対象のリンクとし、当該処理対象のリンクが追加リンクリストに含まれるか否かを判定する。ステップＳ２０５において、更新ＩＤが追加リンクリストに含まれると判定されない場合、ステップＳ２１０をスキップする。この場合、制御部２０は、蓄積情報更新部２１ｂの処理により、蓄積ＩＤが削除リンクリストに含まれるか否かを判定する（ステップＳ２１５）。すなわち、制御部２０は、蓄積ＩＤで特定される更新前の蓄積情報３０ａが示すリンクを処理対象のリンクとし、当該処理対象のリンクが削除リンクリストに含まれるか否かを判定する。ステップＳ２１５において、蓄積ＩＤが削除リンクリストに含まれると判定された場合、ステップＳ２２０をスキップする。
【００６８】
ステップＳ２０５において、更新ＩＤが追加リンクリストに含まれると判定された場合、制御部２０は、蓄積情報更新部２１ｂの処理により、更新ＩＤが示すリンクを更新後の蓄積情報３０ａとして記録媒体３０に記録する（ステップＳ２１０）。すなわち、制御部２０は、更新ＩＤが示すリンクを更新情報３０ｂから抽出し、更新ＩＤを対応づけて更新後の蓄積情報３０ａに記録する。また、ステップＳ２１５において、蓄積ＩＤが追加リンクリストに含まれると判定されない場合、制御部２０は、蓄積情報更新部２１ｂの処理により、蓄積ＩＤが示すリンクを更新後の蓄積情報３０ａとして記録媒体３０に記録する（ステップＳ２２０）。すなわち、制御部２０は、蓄積ＩＤが示すリンクを更新前の蓄積情報３０ａから抽出し、蓄積ＩＤを対応づけて更新後の蓄積情報３０ａに記録する。なお、本実施形態においては、ステップＳ２２０がスキップされると、蓄積ＩＤが示すリンクが更新後の蓄積情報３０ａに記録されないため、当該蓄積ＩＤが示すリンクが更新前の蓄積情報３０ａから削除されることになる。
【００６９】
以上のように、本実施形態においては、更新ＩＤで特定される更新情報３０ｂが示すリンクが追加すべきリンクであるか否かを更新情報３０ｂの追加リンクリストに基づいて判定し、追加すべきリンクでなかった場合、蓄積ＩＤで特定される更新前の蓄積情報３０ａが示すリンクが削除すべきリンクであるか否かを更新情報３０ｂの削除リンクリストに基づいて判定する構成となっている。なお、本実施形態において、更新ＩＤは、更新情報３０ｂの追加リンクリストが示すリンクを示すＩＤのいずれかである。従って、原則として（更新情報３０ｂのリンクデータと追加リンクリストの不整合がない限り）ステップＳ２０５では、更新ＩＤが追加リンクリストに含まれると判定される。従って、Ｓ２０５，Ｓ２１５，Ｓ２２０を省略してもよい。
【００７０】
ステップＳ２１０あるいはＳ２２０が実行されると、制御部２０は、蓄積情報更新部２１ｂの処理により、全リンクの処理が終了したか否かを判定する（ステップＳ２２５）。すなわち、制御部２０は、更新前の蓄積情報３０ａが示すリンクの中で最大値のＩＤが対応づけられたリンクを処理対象のリンクとした処理が終了し、かつ、更新情報３０ｂが示すリンクの中で最大値のＩＤが対応づけられたリンクを処理対象のリンクとした処理が終了した場合に全リンクの処理が終了したと判定する。そして、ステップＳ２２５において、全リンクの処理が終了したと判定された場合、制御部２０は、蓄積情報更新処理を終了する。
【００７１】
一方、ステップＳ２２５において、全リンクの処理が終了したと判定されない場合、制御部２０は、蓄積情報更新部２１ｂの処理により、更新情報３０ｂの追加リンクリストが示すリンクから次のＩＤが対応づけられたリンクを取得し（ステップＳ２３０）、取得されたリンクのＩＤを更新ＩＤに代入する（ステップＳ２３５）。例えば、図３Ｂに示す例において、更新ＩＤに＃３が代入された状態でステップＳ２３０，Ｓ２３５が実行された場合、追加リンクリストに記述されたＩＤの中で＃３の次のＩＤはＩＤ＃６であるため、＃６が更新ＩＤに代入される。
【００７２】
次に、制御部２０は、蓄積情報更新部２１ｂの処理により、更新前の蓄積情報３０ａから次のＩＤが対応づけられたリンクを取得し（ステップＳ２４０）、取得されたリンクのＩＤを蓄積ＩＤに代入する（ステップＳ２５０）。例えば、図３Ａに示す例において、蓄積ＩＤに＃３が代入された状態でステップＳ２４０，Ｓ２５０が実行された場合、更新前の蓄積情報３０ａが示すリンクに対応づけられたＩＤの中で＃３の次のＩＤはＩＤ＃４であるため、＃４が蓄積ＩＤに代入される。ステップＳ２５０が実行されると、ステップＳ１２５以降の処理が繰り返される。この場合、再度ステップＳ３００以降の処理が実行され、図３Ｂに示すように蓄積ＩＤ＃４が削除リンクリストに含まれないため、図３Ｃに示すように蓄積ＩＤ＃４は更新後の蓄積情報３０ａとして記録される。なお、ステップＳ２３５，２５０において、次のＩＤが存在しない場合、非常に大きい値のＩＤ（例えば、ＩＤの上限値）のＩＤを次のＩＤとして蓄積ＩＤに代入すれば良い。
【００７３】
その後、更新ＩＤ＃６，蓄積ＩＤ＃５となり、再度ステップＳ３００以降の処理が実行され、図３Ｂに示すように蓄積ＩＤ＃５が削除リンクリストに含まれるため、図３Ｃに示すように蓄積ＩＤ＃５は更新後の蓄積情報３０ａとして記録されない。その後、更新ＩＤ＃６，蓄積ＩＤ＃３０となる。
【００７４】
この場合、制御部２０は、ステップＳ１２５で更新ＩＤが蓄積ＩＤより小さいと判定することによって、ステップＳ１３０を実行する。ステップＳ１３０において、制御部２０は、蓄積情報更新部２１ｂの処理により、更新ＩＤが追加リンクリストに含まれるか否かを判定する。すなわち、制御部２０は、更新ＩＤで特定され、更新情報３０ｂが示すリンクを処理対象のリンクとし、当該処理対象のリンクが追加すべきリンクであるか否かを判定する。ステップＳ１３０において、更新ＩＤが追加リンクリストに含まれると判定された場合、制御部２０は、蓄積情報更新部２１ｂの処理により、更新ＩＤが示すリンクを更新後の蓄積情報３０ａとして記録媒体３０に記録する（ステップＳ１３５）。すなわち、制御部２０は、更新ＩＤが示すリンクを更新情報３０ｂから取得し、記録媒体３０に記録することで更新後の蓄積情報３０ａを構築する。ステップＳ１３０において、更新ＩＤが追加リンクリストに含まれると判定されない場合、制御部２０は、ステップＳ１３５をスキップする。なお、更新ＩＤは、更新情報３０ｂの追加リンクリストが示すリンクを示すＩＤのいずれかである。従って、原則として（更新情報３０ｂのリンクデータと追加リンクリストの不整合がない限り）ステップＳ１３０では、更新ＩＤが追加リンクリストに含まれると判定される。従って、Ｓ１３０を省略してもよい。
【００７５】
なお、上述のように、更新ＩＤが＃６，蓄積ＩＤが＃３０である状態でステップＳ１３０が実行された場合、図３Ｂに示すように、更新ＩＤ＃６は追加リンクリストに含まれるため、更新ＩＤ＃６を示すリンクが図３Ｂに示す更新情報３０ｂから取得される。そして、当該取得されたリンクが更新後の蓄積情報３０ａとして記録され、図３Ｃに示すようにＩＤ＃６が対応づけられる。
【００７６】
ステップＳ１３０において更新ＩＤが追加リンクリストに含まれると判定されない場合、あるいは、ステップＳ１３５が実行された場合、制御部２０は、蓄積情報更新部２１ｂの処理により、全リンクの処理が終了したか否かを判定する（ステップＳ１４０）。ステップＳ１４０において、全リンクの処理が終了したと判定されない場合、制御部２０は、蓄積情報更新部２１ｂの処理により、更新情報３０ｂの追加リンクリストが示すリンクから次のＩＤが対応づけられたリンクを取得し（ステップＳ１４５）、取得されたリンクのＩＤを更新ＩＤに代入する（ステップＳ１５０）。例えば、図３Ｂに示す例において、更新ＩＤに＃６が代入された状態でステップＳ１４５，Ｓ１５０が実行された場合、追加リンクリストに記述されたＩＤの中で＃６の次のＩＤはＩＤ＃１０１であるため、＃１０１が更新ＩＤに代入される。ステップＳ１５０が実行されると、ステップＳ１２５以降の処理が繰り返される。ステップＳ１４０において、全リンクの処理が終了したと判定された場合、制御部２０は、蓄積情報更新処理を終了する。なお、ステップＳ１５０において、次のＩＤが存在しない場合、非常に大きい値のＩＤ（例えば、ＩＤの上限値）のＩＤを次のＩＤとして蓄積ＩＤに代入すれば良い。
【００７７】
（３）他の実施形態：
以上の実施形態は本発明を実施するための一例であり、更新前の蓄積情報が示す要素と更新情報が示す要素の中からＩＤ順に処理対象の要素を選択して蓄積情報を記録媒体に記録するための処理を行うことでＩＤ順に要素が記録された更新後の蓄積情報を作成する限りにおいて、他にも種々の実施形態を採用可能である。例えば、ナビゲーション端末１０は、車両Ｃに固定的に搭載されていても良いし、持ち運び可能なナビゲーション端末１０が車両Ｃ内に持ち込まれて利用される態様であっても良い。
【００７８】
さらに、更新対象の要素はリンクを示す情報に限定されず、交差点に関する情報等を更新対象としても良い。さらに、蓄積情報の更新に付随して上述の実施形態に示した処理以外の処理を行ってもよい。例えば、リンクデータは道路ネットワークを示すため、リンク同士が互いに関連している。従って、蓄積情報の更新に際しては、リンク同士の接続関係も更新後の状態となるように更新を行う。このための手法は種々の手法が想定可能であり、例えば、各リンクのリンクデータを記録媒体３０に記録していく際に、接続関係を示すデータも再構築するように構成可能である。むろん、更新前と更新後において接続関係が変化する部分については、接続関係を更新した後のデータを１メッシュ分配信して置き換える構成であっても良い。
【００７９】
さらに、ＩＤは、リンクに対して一対一に対応づけられていれば良いが、蓄積情報３０ａが利用される態様に応じてＩＤ付与の指針が決定されていても良い。例えば、道路区間の連結順にＩＤを付与するなどの構成を採用可能である。
【００８０】
さらに、基準バージョンは、ある基準時点における蓄積情報３０ａであれば良く、ある時点（例えば、蓄積情報３０ａを参照するナビゲーション装置を搭載した車両の販売開始時点）における蓄積情報３０ａのバージョンであっても良い。
【００８１】
さらに、上述の実施形態においては、更新前の蓄積情報３０ａが示すリンクと更新情報３０ｂの追加リンクリストが示すリンクの中からＩＤ順に処理対象のリンクを選択していたが、更新前の蓄積情報３０ａが示すリンクと更新情報３０ｂが示すリンクの中からＩＤ順に処理対象のリンクを選択するための処理を行ってもよい。すなわち、ＩＤの昇順を処理順序とし（降順を処理順序とすることも可能）、未処理のリンクであるとともに処理順序が最も早いＩＤが対応づけられたリンクを更新前の蓄積情報３０ａが示すリンクおよび更新情報３０ｂが示すリンクから一つずつ取得してＩＤを比較し、ＩＤが小さい方のリンクを処理対象のリンクとして選択する。以上の構成によれば、全ての要素をＩＤ順にもれなく選択して処理対象とすることができる。また、ＩＤが仮に連続する番号でなくても、容易に各要素をＩＤ順に処理対象とすることができる。
【００８２】
また、この例の場合、図１と同様の構成において、制御部２０が図２に示す蓄積情報更新処理の一部を修正して処理を行う。すなわち、ステップＳ１０５において、制御部２０は、更新情報３０ｂの追加リンクリストが示すリンクおよび更新情報３０ｂの削除リンクリストが示すリンクから最小のＩＤが対応づけられたリンクを取得する。また、ステップＳ１４５，Ｓ２３０において、制御部２０は、更新情報３０ｂの追加リンクリストが示すリンクおよび更新情報３０ｂの削除リンクリストが示すリンクから次のＩＤが対応づけられたリンクを取得する。さらに、この例の場合には、ステップＳ１３０やステップＳ２０５は省略されないが、ステップＳ２１５およびＳ２２０の組み合わせやステップＳ３００は省略可能である。
【００８３】
そして、図３Ａに示す更新前の蓄積情報３０ａと図３Ｂに示す更新情報３０ｂについて、この例にかかる処理を実行すると、まずステップＳ１０５〜Ｓ１２０において更新ＩＤに＃１、蓄積ＩＤに＃１が代入される。この場合、ステップＳ２００において更新ＩＤ＝蓄積ＩＤであると判定され、ステップＳ２０５において更新ＩＤ＃１が追加リンクリストに含まれないと判定され、ステップＳ２１５において蓄積ＩＤ＃１が削除リンクリストに含まれると判定される。従って、図３Ｃに示すように、蓄積ＩＤ＃１は更新後の蓄積情報３０ａに記録されない。
【００８４】
次に、ステップＳ２３０〜Ｓ２５０において更新ＩＤに＃３，蓄積ＩＤに＃２が代入される。この場合、更新ＩＤ＞蓄積ＩＤであることによってステップＳ３００の判定が行われ、蓄積ＩＤ＃２が削除リンクリストに含まれると判定されない。従って、図３Ｃに示すように、蓄積ＩＤ＃２は更新後の蓄積情報３０ａに記録される。次に、ステップＳ３１５，Ｓ３２０において蓄積ＩＤに＃３が代入される。この場合、ステップＳ２００において更新ＩＤ＝蓄積ＩＤであると判定され、ステップＳ２０５において更新ＩＤ＃３が追加リンクリストに含まれると判定される。従って、図３Ｃに示すように、更新ＩＤ＃３は更新後の蓄積情報３０ａに記録される。
【００８５】
次に、ステップＳ２３０〜Ｓ２５０において更新ＩＤに＃５，蓄積ＩＤに＃４が代入される。この場合、更新ＩＤ＞蓄積ＩＤであることによってステップＳ３００の判定が行われ、蓄積ＩＤ＃４が削除リンクリストに含まれると判定されない。従って、図３Ｃに示すように、蓄積ＩＤ＃４は更新後の蓄積情報３０ａに記録される。次に、ステップＳ３１５，Ｓ３２０において蓄積ＩＤに＃５が代入される。この場合、更新ＩＤ＝蓄積ＩＤであることによってステップＳ２０５の判定が行われ、蓄積ＩＤ＃５が削除リンクリストに含まれると判定される。従って、図３Ｃに示すように、蓄積ＩＤ＃５は更新後の蓄積情報３０ａに記録されない。
【００８６】
次に、ステップＳ２３０〜Ｓ２５０において更新ＩＤに＃６，蓄積ＩＤに＃３０が代入される。この場合、更新ＩＤ＜蓄積ＩＤであることによってステップＳ１３０の判定が行われ、更新ＩＤ＃６が追加リンクリストに含まれると判定される。従って、図３Ｃに示すように、更新ＩＤ＃６は更新後の蓄積情報３０ａに記録される。次に、ステップＳ１４５，１５０において更新ＩＤに＃１０１が代入される。以後、全てのＩＤが処理対象となった処理が完了するまで処理が続けられる。
【００８７】
以上の処理において、ステップＳ１２５において更新ＩＤ＜蓄積ＩＤであると判定される場合、または、ステップＳ２００において更新ＩＤ＝蓄積ＩＤであると判定される場合は、更新情報３０ｂが示すリンクが処理対象のリンクとなる。そして、この例においては、処理対象のリンクが追加すべきリンクであるか否かを追加リンクリストに基づいて判定する構成（ステップＳ１３０，Ｓ２０５）となる。すなわち、更新情報３０ｂが示すリンクは、追加されるか削除されるかのいずれかであるため、追加すべきリンクであるか否かを判定すれば、蓄積情報３０ａの更新に際して処理対象のリンクをどのように扱うべきか確定することが可能である（追加されないのであれば削除される）。この結果、簡易な処理により、更新情報３０ｂが示すリンクの扱いを特定することが可能である。むろん、処理対象のリンクが、更新情報３０ｂが示すリンクである場合、処理対象のリンクが削除すべきリンクであるか否かを更新情報３０ｂに基づいて判定することで処理対象のリンクをどのように扱うべきか確定する構成であっても良い。
【符号の説明】
【００８８】
１０…ナビゲーション端末、２０…制御部、２１…蓄積情報更新プログラム、２１ａ…更新情報取得部、２１ｂ…蓄積情報更新部、３０…記録媒体、３０ａ…蓄積情報、３０ｂ…更新情報、４１…ＧＰＳ受信部、４２…車速センサ、４３…ジャイロセンサ、４４…ユーザＩ／Ｆ部、４５…通信部
【図１】
2014182678.tif 000003
【図２】
2014182678.tif 000004
【図３】
2014182678.tif 000005