(57)【要約】【課題】複数のデータベースのバージョンや、以前に全体的もしくは部分的に修正されたデータベースのバージョンによらず、更新されるべき道路ネットワーク要素を識別する方法を提供する。【解決手段】少なくとも１つの道路交差点を識別するデータベースの更新情報を受信し、その少なくとも１つの道路交差点を取り囲む道路地形の論理的な表現を構築し、及び、その論理的な表現と、ナビゲーションデータベースにおける論理的表現とを比較することによって、ナビゲーションデータベースにおけるその少なくとも１つの道路交差点を識別する。【選択図】      図３
2005078066.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーションデータベースにおいて、道路セクションを識別するための方法であって、
少なくとも１つの道路交差点を識別するデータベースの更新情報を受信するステップ、
前記少なくとも１つの道路交差点を取り囲む道路地形の論理的な表現を構築するステップ、及び、
前記論理的な表現と、前記ナビゲーションデータベースにおける論理的表現とを比較することによって、ナビゲーションデータベースにおけるその少なくとも１つの道路交差点を識別するステップを備えることを特徴とする方法。
【請求項２】
論理的な表現を構築するステップは、さらに、前記少なくとも１つの道路交差点の近傍における道路地形を表現するグラフを構築するステップを有し、そこにおいて、グラフのノードは道路交差点を表し、グラフのリンクは道路セグメントを表すことを特徴とする請求項１に記載の方法。
【請求項３】
前記データベースの更新情報は、前記少なくとも１つの道路交差点に関連付けられた属性を含み、前記ナビゲーションデータベース内の前記少なくとも１つの道路交差点を識別するために、その属性が用いられることを特徴とする請求項１に記載の方法。
【請求項４】
前記データベースの更新情報は、属性を有する少なくとも１つの道路セグメントを識別し、前記ナビゲーションデータベース内の前記少なくとも１つの道路交差点を識別するために、前記少なくとも１つの道路セグメントの属性が用いられることを特徴とする請求項１に記載の方法。
【請求項５】
論理的な表現を構築するステップは、前記少なくとも１つの道路交差点を取り囲む道路地形を表すためのツリーグラフを構築するステップを有し、ツリーグラフのノードは道路交差点を表し、ツリーグラフのリンクは道路セグメントを表すことを特徴とする請求項１に記載の方法。
【請求項６】
前記少なくとも１つの道路交差点は、前記ツリーグラフの根ノードとしての役割を果たすことを特徴とする請求項５に記載の方法。
【請求項７】
前記少なくとも１つの道路交差点を識別するステップは、最小スパンツリーマッチング操作を使用するステップを有することを特徴とする請求項５に記載の方法。
【請求項８】
前記少なくとも１つの道路交差点を識別するステップは、全スパンツリーマッチング操作を使用するステップを有することを特徴とする請求項５に記載の方法。
【請求項９】
前記論理的な表現を前記ナビゲーションデータベースの論理的表現と比較する前に、前記少なくとも１つの道路交差点に対する近接位置に基づいて前記ナビゲーションデータベース内において候補となる道路交差点を選択するステップをさらに備えることを特徴とする請求項５に記載の方法。
【請求項１０】
前記ツリーグラフの深さは、前記ツリーグラフによって表される１つもしくはそれ以上の道路交差点に接する道路セグメントの数の見込みに基づくことを特徴とする請求項５に記載の方法。
【請求項１１】
前記ツリーグラフの深さは、前記少なくとも１つの道路交差点を唯一のものとして識別するために、ツリーグラフに要求される最小の深さとして決定されることを特徴とする請求項５に記載の方法。
【請求項１２】
前記ナビゲーションデータベース内の識別された道路交差点に、前記データベースの更新情報を適用するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１３】
前記ナビゲーションデータベースに対して、前記データベースの更新情報を示すパッチを制定するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１４】
ナビゲーションデータベースに更新情報を適用するための方法であって、
２個のノードと１つのリンクを指定する更新指示を受信するステップ、そこにおいて、ノードは道路交差点を表し、リンクは、２個のノードを接続する道路セグメントを表すものであり、
論理的なパターンマッチング操作を使用して、指定されたノードの少なくとも１つに対応する、ナビゲーションデータベースに存在するノードを識別するステップ、
指定されたノードの各々を、ナビゲーションデータベースに存在するノード、もしくはリンクの少なくとも１つに対する関係に基づいて分類するステップ、及び
順序付けされた操作ルールセットに従って、更新指示を適用するステップとを備えることを特徴とする方法。
【請求項１５】
存在するノードを識別するステップは、少なくとも１つの指定されたノードの近傍における道路地形の論理的表現を構築するステップと、その論理的表現を前記ナビゲーションデータベースの論理的表現と比較するステップとを備えることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記論理的表現を比較するステップは、最小スパンツリーマッチング操作を実行するステップを有し、前記論理的表現はツリーグラフとして定義され、前記少なくとも１つの指定されたノードは、前記ツリーグラフの根ノードとしての役割を果たすことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記論理的表現を比較するステップは、全スパンツリーマッチング操作を実行するステップを有し、前記論理的表現はツリーグラフとして定義され、前記少なくとも１つの指定されたノードは、前記ツリーグラフの根ノードとしての役割を果たすことを特徴とする請求項１４に記載の方法。
【請求項１８】
指定されたノードの各々を分類するステップは、指定されたノードを、ナビゲーションデータベース内の現存するノードに対応するノード、ナビゲーションデータベース内の現存するリンク上の地点、ナビゲーションデータベースにまだ存在しない要素からなるグループの１つにグループ分けするステップを有することを特徴とする請求項１４に記載の方法。
【請求項１９】
順序付けされた操作ルールセットは、ナビゲーションデータベースに現存するノードに相関する２個のノードを有するリンクがナビゲーションデータベースに追加可能であることを規定することを特徴とする請求項１４に記載の方法。
【請求項２０】
順序付けされた操作ルールセットは、ナビゲーションデータベースに現存するリンク上の地点となるノードを有するリンクが、前記現存するリンクを削除し、かつ前記ノードをナビゲーションデータベースに現存する他のノードに接続する２つのリンクを追加することによって追加されることを規定することを特徴とする請求項１４に記載の方法。
【請求項２１】
順序付けされた操作ルールセットは、いずれのノードもナビゲーションデータベースに現存するノードに相関しない２個のノードを有するリンクは、ナビゲーションデータベースに追加されないことを規定することを特徴とする請求項１４に記載の方法。
【請求項２２】
更新指示の適用は、引き続く更新指示がナビゲーションデータベースに適用されるまで、前記順序付けされた操作ルールセットに従って遅延されることを特徴とする請求項１４に記載の方法。
【請求項２３】
ナビゲーションデータベースに対してデータベースの更新を行なう方法であって、
ナビゲーションデータベースにおいて更新されるべきリンクのリストを提供するステップ、そこにおいて、各リンクは、道路セグメントによって相互接続される２つの道路交差点として表されるものであり、
そのリンクのリストにおいて、唯一のものとして指定される各道路交差点に関して論理的表現を構築することにより、その論理的表現が、指定された道路交差点の近傍の道路地形を示すものとなるステップ、及び
前記リンクのリストに関して順序付けされた更新指示のセットを制定することにより、各更新指示が少なくとも１つの論理的表現を参照するステップとを備えることを特徴とする方法。
【請求項２４】
データベースの更新を形成するために、論理的表現の各々と順序付けされた更新指示のセットをコンパイルするステップをさらに備えることを特徴とする請求項２３に記載の方法。
【請求項２５】
前記リンクのリストにおいて指定された道路セグメントと道路交差点とのいずれかに関連付けられた属性データを識別するステップ、及び少なくとも１つの更新指示が属性データを参照するように前記順序付けされた更新指示のセットを制定するステップとをさらに備えることを特徴とする請求項２３に記載の方法。
【請求項２６】
論理的表現を構築するステップは、少なくとも１つの道路交差点の近傍における道路地形を表すグラフを構築するステップを有し、そこにおいて、グラフのノードは道路交差点を表し、グラフのリンクは道路セグメントを表すことを特徴とする請求項２３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーションシステムに関し、特に、反復的、論理的なグラフパッチングを用いた、ナビゲーション地図データベースの更新方法に関する。
【背景技術】
【０００２】
ナビゲーションシステムは、経路計算、経路案内、目的地探索、及びその他のナビゲーション機能をユーザに提供するためにナビゲーション地図データベースを用いる。ナビゲーション地図データベースは、通常、道路ネットワーク、及び、参照によりこれに援用される、ＫＩＷＩ−Ｗコンソーシアムによって２０００年５月にバージョン１．２２として公表されたＫＩＷＩフォーマットによって記述されるフォーマットにおけるような属性を示すデータを含んでいる。ナビゲーションシステムの性能は、有効なデータに依存し、それ故、道路ネットワークもしくはその要素が、例えば道路建設によって著しく変化したとき、ナビゲーション地図データベースを最新のものにしたり、更新したりすることが重要となる。ナビゲーション地図データベースの更新は、（１）データベースの交換、（２）データベースの修正、もしくは（３）データベースのパッチングによって達成することができる。広域ナビゲーション地図データベースのサイズの大きさにより、データベースの部分的な修正もしくはパッチングが、無線通信による更新のための好ましい方法とされている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
いくつかのナビゲーション地図データベースは、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭのような読出し専用メディアに格納される。これは、オリジナルの地図データベースは修正され得ず、パッチングに対して特有の課題を示す、との追加的な制限を加える。オリジナルのデータベースと更新情報とを相関させることは、メディアの種類を問わず共通の課題であるが、複数回の更新後にパッチングされるデータを築き上げることは、さらなる更新を複雑化させるかもしれない。さらに、パッチデータは、オリジナルのデータとは別に保存されることができるので、効率的な更新と、アプリケーションによるシームレスかつ安定したアクセスの方法も求められる。
【０００４】
ナビゲーション地図データベースのバージョンの相違及びナビゲーション地図データベースのデータソースの相違は、ナビゲーションシステムのデータベースにおいて詳細なデータ内容に多数の種類をもたらし、それらのバージョン依存性によって、既に変更した道路ネットワークの部分の識別を問題化させる。さらに、何人かのユーザは、最新のものへの更新をしそこなったり、しなかったり、あるいは興味のある領域のみ部分的にデータベースを最新のものにするかもしれないので、使用されている異なるデータベースのバージョンの数を増やすことになる。例えば、データベース間で、地理的な位置及び道路構造の属性が著しく異なり、道路構造に異なる識別が割り当てられたり、さらにはある意味でランダムとなったり、及び道路ネットワークセクションを表すために使用される道路ネットワーク構造が、異なったりするかもしれない。例えば、道路が名称をもたないことは、稀なことではない。しかしながら、全てのバージョンの行方を追跡し、特定のナビゲーションシステムに特化された更新情報を送信することは、保存及び通信帯域幅の使用において、ロバスト性を欠き、融通が効かず、非効率である。それ故、複数のデータベースのバージョンに対して機能するために、及び以前に全体的もしくは部分的に修正されたデータベースのバージョンに関して機能するために十分にフレキシブルである、更新されるべき道路ネットワーク要素を識別するため方法が求められている。
【０００５】
本発明は、データベースのバージョン固有の情報によらず、修正された道路ネットワーク要素を識別し、かつオリジナルのデータベースの修正を必ずしも必要としない、更新操作によって上述した問題を解決すること目的とするものである。
【課題を解決するための手段】
【０００６】
本発明によれば、ナビゲーションデータベースにおいて道路要素を識別するための改良された方法が提供される。その方法は、少なくとも１つの道路交差点を識別するデータベースの更新情報を受信し、その少なくとも１つの道路交差点を取り囲む道路地形の論理的な表現を構築し、そして、その論理的な表現と、ナビゲーションデータベースにおける論理的表現とを比較することによって、ナビゲーションデータベースにおけるその少なくとも１つの道路交差点を識別することを含む。
【０００７】
本発明の他の態様においては、ナビゲーションデータベースを更新するための改良された方法が提供される。その方法は、２個のノードと１つのリンクを指定する更新指示を受信し、そこにおいて、ノードは道路交差点を表し、リンクは、２個のノードを接続する道路セグメントを表すものであり、論理的なパターンマッチング処理操作を使用して、指定されたノードの少なくとも１つに対応する、ナビゲーションデータベースに存在するノードを識別し、指定された各々のノードを、ナビゲーションデータベースに存在するノード、もしくはリンクの少なくとも１つに対する関係に基づいて分類し、そして、順序付けされた操作ルールのセットに従って、更新指示を適用することを含む。
【０００８】
本発明のさらなる適用範囲は、以下に与えられる詳細な説明から明らかとなる。ただし、その詳細な説明及び特定の実施形態は、本発明の好ましい例を示すものではあるが、説明のみを目的とすることが意図されたものであり、本発明の範囲を制限することを何ら意図するものではないことを理解すべきである。
【発明を実施するための最良の形態】
【０００９】
地図データベースは、有向グラフとして表現され、そのグラフでは、方向が定められた１つ以上のエッジ（リンク）が、各々の道路セグメントを示し、隣接するエッジが、交差点もしくは道路セグメントの接続部を示す頂点（ノード）において接続される。ＫＩＷＩのような、通常のナビゲーション地図データベースのフォーマットは、当業者に良く知られているように、属性を伴なうリンクのリストを備えている。地図データベースの更新には、リンクに関する順序付けられた操作のセットが含まれ、各リンクは関連付けられた属性を有している。順序付けの重要性は、以下に説明される。各リンクは、方向が定められたエッジと２つの頂点として表せられる。頂点は、接続されたエッジに関する操作の一部として更新される。本発明は、更新データをオリジナルのデータにマッチングすることにより、更新するリンクを識別することによって適用可能となるとともに、その後、オリジナルのデータを修正したり、もしくはパッチングするリンクを基礎とする操作による段階的更新を含む。
【００１０】
ここで示される方法に従い、（１）オリジナルの、もしくは以前に改良されたデータベースへのパッチもしくは修正の適用と、（２）改良されたデータベースに対する、統合された観念的なインターフェースをアプリケーションに与えることとの、２つの別個の、ただし相互依存の機能が説明される。アプリケーションの観点からは、全ての過去のパッチや修正を組み込んだ１つの統合されたデータベースであるかのように、データベースにアクセスするための単一のインターフェースを有することが望ましい。更新は、データベースに対する修正としてあるいはパッチとして適用されることができる。パッチのメンテナンス操作は、オリジナルのデータベースを変更することなく、全ての受信されたパッチデータをパッチデータベースに充当する。しかし、アプリケーションは、これを知る必要はないし、異なる動作を行なう必要もない。
【００１１】
パッチの適用の問題は、反復的に、すなわち、セクション毎にあるいは一度に１つのリンクを追加することによって取り組まれることにある。好ましい実施形態においては、完全な更新が、リンク毎に適用される。これに関連して言えば、リンクは、本来的に２つの頂点を含む（すなわち、方向が定められたエッジに関する始点及び終点）。アプリケーションとは無関係に、位置、識別、もしくはその他によってリンクに関連する照会を検出することにより、及びパッチに基づいて修正されたフィードバックを与えることにより、単一のリンクの更新を組み込むようにグラフがパッチングされる。他の実施形態においては、完全な更新が、サブネットワーク（すなわち、関連するリンクとノードのセット）に対する識別と変化のシーケンス内において適用される。
【００１２】
経路計算、案内、あるいは目的地探索に必要なデータを検索する場合のように、グラフに関する照会への応答は、更新されたグラフに基づく応答と同一となるように、修正されていないオリジナルのグラフとは別個のパッチメモリを使用するように制御される。修正されていないオリジナルのグラフに関する照会への応答は、たとえそのグラフが変化されていない場合であっても、更新されたグラフと整合するように修正されることができる。これは、別個のパッチメモリを使用することによって実行され得る。従って、経路計算のようなアプリケーションは単一のデータベースインターフェースにアクセスし、パッチメモリやオリジナルのデータベースのどちらにも直接アクセスする必要がなくなる。すなわち、インターフェースが観念的なアクセスを与え、その実行の詳細を見えないようにする。アプリケーションは、与えられた位置に最も近いノードを要求することができ、その結果がオリジナルのデータベースからのものか、パッチングされたものか、さらにはデータベースがパッチングされたかどうかを知る必要はない。例示のための構造が、図１に示される。
【００１３】
１つの実施形態において、各々の新しいリンクは、最も新しくパッチングされるグラフを用いて追加される。従って、第１の新しいリンクの後に、第２の新しいリンクが追加され、両方が新しいノードで接続された場合、その第２の新しいリンクは、オリジナルのグラフに対してあたかも最初の追加であるかのように追加される（オリジナルのデータが全ての以前のパッチを備えている場合を除く）。これを達成する１つの方法は、パッチの重ね合わせ、すなわちパッチにパッチングすることを許容することである。本質的に、パッチの管理保守ソフトウエアは、アプリケーションと同様の観念的な観点を使用してデータベースを検分する。好ましい実施形態においては、処理操作は、セットにおける全ての要素の識別が、セットによって記述された変更に先立って行なわれるか、もしくは要素の識別が、そのセットにおける変更の何れかが適用される前に、オリジナルのデータベースのバージョンを使用して行なわれる。
【００１４】
各リンクを基礎とするグラフの更新には、（１）リンクの削除、（２）新しいリンクの追加、（３）存在するリンクの修正の、３つの手法の可能性がある。リンクの削除は、定められたリンクを含む応答要素を捨てることによって達成され得る。換言すれば、パッチマスクが、“パッチング”されたリンク又はノードをハイライトし、そして、もはや存在しない（削除された）ものとしてその登録事項に単にタグや印を付けても良い新たな登録事項を捜す。
【００１５】
存在するリンクの修正は、古いリンクを削除し、新たな追加リンクでそのリンクを置き換えるとのより一般的な処理操作によって行なうことができる。リンクの追加は、存在する頂点と新しいリンクの頂点との相関関係に依存して、可能性がある多くのケースがある。頂点が既に存在するか、存在するエッジ上の地点に対応するか、もしくは全く新しい場合などである。
【００１６】
最初に、リンクの両方の頂点がデータベースに既に存在するケースを考える。もし、新しいエッジに接続される両頂点が２個の存在する頂点（ここでは、クラス１の頂点として言及される）に相関するならば、その際、２個の存在する頂点が対応する新たな頂点と置き換えられ、接続される新たなエッジを追加することができる。基本的に、このケースにおいては、２個の古い頂点が、追加される新たなエッジに追加的に接続される２個の新しい頂点と置き換えられる。全ての新しい情報は、パッチデータベースに格納される。それらがパッチデータベースに格納されるとの事実は、当然、オリジナルのデータベースの登録事項が無視されることになるということを伴なう。換言すれば、パッチメモリ内の２個の修正された頂点が、オリジナルのデータベースにおける２個の頂点に取って代わる。オリジナルのデータベースの頂点は、削除もしくは修正されないが、その代わりに、パッチインターフェースがパッチメモリにおける取替えの事実の存在により、それらを無視する。
【００１７】
パッチデータベースの登録事項は、削除もしくは追加部分を識別するために使用できる。パッチデータベースは、アプリケーションには転送されない削除された頂点及び／又はエッジのリストを使用して削除部分を識別することができる。追加部分のリストは、オリジナルのデータベースに関連づけられ、適切な要求に基づいてアプリケーションへ転送される。しかしながら、１つの頂点がオリジナルのデータベースにおける頂点に対応しない（クラス２の頂点として言及される）ならば、その際、頂点の相関関係について、他の方法が使用される。
【００１８】
クラス２の頂点の１例は、存在するエッジの上の１地点に対応する新しい頂点である。新しい頂点が存在するエッジ上の1地点に対応する（クラス２ａの頂点として言及される）ならば、そのとき、そのエッジは、新しい頂点に接続する２本の新しい隣接するエッジによって取って代わられる。実際には、このケースにおける適切な処理操作は、古いエッジを削除し、２本の新しいエッジと、それらのエッジに接続する新しい頂点とを追加することである。オリジナルのデータベース内の２個の頂点は変更されないが、２個の取り替えられた頂点がパッチメモリ内に存在するので、パッチインターフェースによって無視される。古いエッジも、削除されたものとしてパッチメモリ内のリストに入れられているので無視される。パッチングされた頂点は、もはや直接的には繋がらないが、そのかわり、以前の古いエッジ上の位置に対応していた第３の新しいノードを介して繋がる。
【００１９】
１つの頂点についての第３のケースは、新しい頂点が、存在するエッジの上の地点に対応しない場合である（クラス２ｂの頂点として言及される）。新しいリンクが。２個のクラス２ｂの頂点を有するならば、その結果として更新されるグラフは、全く接続されないことになる。この場合、更新は、データベースに対する単なる補足となる。もし、新しいリンクがただ１個のクラス２ｂの頂点を有するならば、更新されるグラフは接続されることになる。つまり、新たな１個の頂点及び１本のエッジが生ずる。
【００２０】
本発明の１実施態様においては、２個の新たな頂点を有するリンクは、少なくとも１個の頂点が存在する頂点、もしくは存在するエッジ上の地点に対応するまで（すなわち、別の変更によって対応するまで）、パッチデータベースに追加されない。存在する経路から完全に分離しているリンクは、追加されないのである。それは、更新情報におけるリンクを適切に整理することによって、もしくは接続され得る（すなわち、少なくとも１個の頂点がクラス１又はクラス２ａとなる）まで、保存しておくことによって避けることができる。一旦、接続されたならば、クラス１又はクラス２ａの頂点は、エッジと他の頂点とをグラフに接続する。接続されないリンクは、オリジナルのデータベースと直接的には関係付けされない。しかしながら、パッチインターフェースは、改良されたデータベースの検索において保存される非接続リンクを含むことができるため、アプリケーションによって考慮されるかもしれない。これに対する対策は、保存データと改良データベース間の非接続を克服することである。孤立したエッジ、すなわち、メイングラフに接続されないエッジは、通常、ささいな近道の計算のためにのみ有用となり、従って、このパッチ順序規則を執行しても、否定的な結果が生じることはほとんどない。この規則は、第１のパッチ順序規則として言及される。
【００２１】
１個の頂点は、３つの異なるクラス（１，２ａ、２ｂ）の１つとなり、リンクは２個の頂点を持つので、（１）両方がクラス１、（２）両方がクラス２ａ、（３）両方がクラス２ｂ、（４）１個がクラス１で、他方がクラス２ａ、（５）１個がクラス１で、他方がクラス２ｂ、（６）１個がクラス２ａで、他方がクラス２ｂ、というように、リンクに関して６つのクラスの組合せがある。それらのケースの各々に対して、パッチング処理操作を確立する場合、パッチングの反復処理が、全体として考慮されることができる。全てのケースが列挙され、各ケースがパッチング処理操作によって取り組まれるので、完全なパッチング反復処理手順が特定され、それは、パッチの管理保守ソフトウエアに、順序付け規則に従ういずれの受信パッチデータを適用することを許容する。しかしながら、頂点のクラスは前もって知ることができない点に注意すべきである。従って、１本のリンクについてパッチング反復処理の最初のステップは、２個の頂点を識別するとともに、２個の頂点の各々のクラスを決定することである。１つのアプローチとして、各頂点を別個に考慮し、それをクラス分けするように試みることが挙げられる。他のアプローチとしては、同時に両方の頂点を識別することを試みることが挙げられる。個々の頂点の識別は、一旦識別された各々の頂点が他の頂点の可能性を狭めるため、もしくは識別を確認するために使用することができるので、実施形態として好ましい。各々の頂点は、その頂点の特定位置の定められた範囲内における候補頂点を最初にサーチすることによって、そしてその頂点が各候補頂点と整合するか順番に試行することによってクラス分けすることができる。
【００２２】
定められた頂点を、地図データベースに存在する他の頂点と関連付けるために、種々の代替手法がある。可能性がある代替手法は、高精度な位置のマッチング、識別マッチング、及び地理的なパターンマッチングを含む。本発明は、上述したアプローチの制約を克服する改良された論理的なパターンマッチング技術を提案する。
【００２３】
論理的なパターンマッチング処理操作は、ローカルエリアにおけるリンク間の論理的な関係をマッチングすることからなる。論理的なパターンは、単一のリンクあるいは頂点のための更新情報において供給され、予め定義された距離内（すなわち、頂点をホップする）における他のリンク（すなわち、頂点とエッジ）との関係のセットからなるものであっても良い。限られた情報のみが転送されれば良いので、帯域幅の要件は緩和され、マッチングは、単純な論理的、かつ初歩的な比較の数学的処理（例えば、頂点ｃの等級は頂点ｘの等級に等しいか？）で比較され得る、論理的なグラフの関係に基づくものであるため、パターンマッチングはより効率的になる。さらに、論理的なグラフの関係は、識別子，位置、道路形状の情報、及び他の地理的データよりも変化しにくい。例えば、論理的なパターンは、著しい地理的あるいは物理的な変化が道路や交差点に生じたとしても、必ずしも変化しない。道路ネットワークを示す論理的なパターンは、交差点や道路位置、属性及び他のパラメータにおける変化に対して不変であり得る。例えば、２つのデータベースもしくは１つのデータベースの２つのバージョンが道路と交差点の物理的位置においてのみ異なるものであるならば、単一の論理的パターンが、その両方を正確に表すことができる。
【００２４】
１つの実施形態において、パターンエリアの属性は、マッチングのための論理的パターンとともに含まれても良い。道路の等級、道路名称、信号灯の情報、レーン情報、道路幅、及び種々の他の道路属性のような道路属性が使用され、それによってパターンを増大することができる。高速道路の出口、入り口、あるいは田園地帯の道路のように、低い対称性を持つ道路ネットワークエリアに対する境界、新しい領域、変更がパッチングされる場合には、属性を用いた増大は不要である。
【００２５】
論理的なパターンマッチングは、マッチング部分を識別するために、頂点やエッジの論理的なパターンの比較のための論理的パターン構造を利用する。エッジ隣接グラフは、そのような論理的パターンの１例である。図２は、新しいエッジ“ｃｈ”（すなわち頂点ｈとｃを接続するエッジ）を備えた新しいリンクのための、局所的な（すなわち、１ホップ分）論理的関係の例を描写する。強調された頂点は、新しいエッジに隣接する１“ホップ”内に属する頂点である。しかしながら、他の種類の論理的パターン構造も本発明の範囲内に属することは考えられる。次のもの、すなわち、頂点の等級（つまり、頂点に接続される固有のエッジの数）、頂点の方向的に固有な等級（つまり、定められた方向に向いて接続された、固有の向きのエッジの数）、定められた深さにおける隣接するエッジのツリーパターン（交差点間の距離もしくは何ホップ分）、及び隣接するエッジのツリーパターンとリーフ頂点との組合せは、それらの種類のパターン構造に関するいくつかの変形例を示す関係の例である。
【００２６】
好ましい実施形態において、ツリー構造は、論理的パターンのマッチング処理操作を実行するために使用される。図３（ａ）は、頂点ｃに対する最小のスパンツリー（ＭＳＴ）構造の例を示す。このツリーグラフは、基礎となる地図データベースとパッチデータから各装置においてパッチ管理ソフトウエアによって生成することができる。リンク“ｃｈ”を追加するために、図３（ｂ）に示される最小スパンツリーが構築され、更新指示のセットの１部においてリンクｘの論理的識別として転送される。このグラフ（論理的パターン）と、同じ頂点に対してナビゲーションシステムのデータベースから構築されたグラフとの比較は、他の近傍の頂点のグラフとは異なりながら、それらが論理的に同一であることを示す。頂点ｘは、このようにして明確かつ唯一のものとして、頂点ｃとして識別される。最小のスパンツリーは、リーフから根元までのトータルの重さを最小化するが、いずれの固有のグラフツリーも、冗長的であるか否か、最小か、最小ではないかを問わず、使用することができる。好ましい実施形態において、リーフの順番は、重要なものではない。他の実施形態において、リーフの順番は、例えば上から見たときに道路（エッジ）の時計回りの順番を反映する。
【００２７】
類似の方法が頂点ｈのために使用される。一旦、２個の頂点が唯一のものとして決定されると、パッチデータベース（あるいは、もし修正可能ならば、オリジナルのデータベース）は、追加のエッジ“ｃｈ”を組み込むように更新されることができる。ツリーの深さは変化し、頂点間又はパッチングの反復間において異なるかもしれないことに注意すべきである。より浅い深さのツリーは、より単純な関係が唯一性を満足するのに十分であるときに比較のために使用することができ、ツリーの深さは、必要とされる唯一性を基礎として選択することができる。
【００２８】
代替の実施形態においては、頂点ｃのための最小スパンツリーが、テーブルもしくは入れ子式のリストの形式で表現され、以下のように論理的パターンマッチングのための頂点の等級を含んでいる
頂点ｃのための論理的パターン
Ｅ（等級  ３）
Ｇ（等級  ３）
Ｆ（等級  ４）
Ｈ（等級  ６）
Ｉ（等級  ３）
Ｋ（等級  ４）
Ｌ（等級  １）
Ｄ（等級  ２）
Ｂ（等級  ３）
Ｊ（等級  ３）
ここで、ノードの識別，すなわち識別子Ｅ，Ｆ，Ｇ等は、好ましい実施形態においては、パターンに含まれないことに注意すべきである（それらは、説明の目的のために上述したパターンに含まれている）。そのようなツリーは、望ましい確信が得られるまで、頂点より１ホップ分からｎホップ分にかけて行なわれる、迅速かつ簡単な論理演算処理において比較されることができる。
【００２９】
１つの実施形態において、ツリーパターンは、いずれの頂点の等級、もしくはある範囲内における等級に整合するワイルドカードを含むことができる。例えば、ワイルドカードは、２方向道路、３方向道路、４方向道路の交差点のいずれにも整合することができる。あるいは、最高のマッチングのための比較アルゴリズムは、ツリーパターンを、データベースにおける最も近いマッチングパターンに整合するように使用されることができる。最も近いマッチングパターンは、例えば、頂点の等級の異なる最も少ない数を持つものとして、もしくは、頂点の等級間の相違が最も少ないものとして定義することができる。「最も近い」については、多数の代替定義が可能である。そのような最高のマッチングあるいは最も近いマッチング方法は、データベースのバージョンに相違がある道路構造を整合させるための柔軟性を与える。
【００３０】
固有の最小スパンツリーは、達成可能ではあるが、そのようなツリーの生成は必ずしも必要ではない。全スパンツリー（ＡＳＴ）構造は、その他の実行可能な代替の例となる。全スパンツリー構造は、全てのリーフが定められたエッジのどれにも含まれるか、どのリーフもいずれの定められたエッジに含まれないかのどちらかであるような、冗長の頂点を備えたツリーである。図４は、典型的な全スパンツリー構造を図示している。全スパンツリーは、その大きさにおいて、最小スパンツリーよりも早く成長するが、簡単に生成されることが理解される。さらに、各頂点のために要求される保存は、最小スパンツリーの場合と同様であり、その結果、全体としての保存量は非常に小さいままである。各ツリーノードは、リーフノード（等級）の数の単なるリストによって示すことができる。（図４に示される）ｃのための深さ３の全スパンツリー構造のコンパクトな表現の例は、４(３(３，４，３)，４(４，６，３，３)，２(４，３)，６(３，４，４，３，４，２))、もしくは単純に、４，３，３，４，３，４，４，６，３，３，２，４，３，６，３，４，４，３，４，２のような整数の並びである。ここで、このコンパクトな形式は、リーフの等級のみを使用してツリーを定義するものであることに注意すべきである。最初の数字は、根ノードｃの等級である。２番目の数字（３）は、ｃの最初のリーフｅの等級であり、その後に、ｅの３個のリーフの各々の等級（３，４，３）が続く。次のグループは、ｃの第２のリーフｆの等級と、それに続く、ｆの４個のリーフの各々の等級などである。好ましい実施形態において、リーフの順番に重要性はない。
【００３１】
実用的な実施のため、ノードのおおまかな位置に関して誤差半径を用いることによって、事前に可能性のあるマッチングのリストを狭めておくと合理的である。例えば、リンク“ｘｙ”（すなわち、“ｃｈ”）の追加の要求が、ｘ及びｙの論理的な表現とｘ及びｙのおおまかな位置とを伴なうならば、そのとき、ｘ及びｙのための候補マッチング点が、それらの与えられた位置を囲むおおまかなエリア内に存在する頂点に狭めることができる。そのエリアの範囲は、予め定められるか、あるいは実施時に、パッチ要求において与えられた大まかな位置に対して最も近いＮ個の頂点を選択するようにしても良い。一旦、候補となる存在する頂点の数が特定されると、そのとき、論理的パターン（例えば、ツリー）が生成され、パッチ要求において与えられる論理的パターンと論理的に比較される。
【００３２】
上述したように、ツリー構造は論理的パターンマッチングのため有用なものである。ツリーの本質的な構造は、根頂点について道路ネットワークパターンを記述する。ツリー構造は、そのツリーにおいて、各頂点の等級を本来的に含み、それ故、そのツリーの根頂点に整合する頂点を唯一のものとして識別することができる（そして、副次的に、ツリーの他のノードを識別する）。高い対称性を備えた道路ネットワークは、パターンマッチングに対して困難な課題を示し、唯一のものとして整合する頂点のために、より深いツリーが必要とされるかもしれない。誤った頂点の整合は、ツリーが唯一のものとして頂点を識別しない（すなわち、２個以上の頂点がパターンに整合する）ときに結果として生じる。ツリーは、通常、所望の頂点と整合するように指定されるが、もし誤った整合が考慮されないならば、１個以上の追加的な頂点と同時に整合しても良い。また、ツリーの生成が、誤った整合を考慮しないならば、統計的な解析のような対策が用いられることができる。
【００３３】
誤った整合の可能性を計測する１つの手法は、地図データベースからツリーパターンに関する統計値を収集することである。ツリーの深さは、いくつのパターンの組合せがあるかを決定するが、ツリーの数は、計算すべき頂点と同じ数しかない。非常に深い、あるいは多くの深さのバリエーションについて統計値を収集することは、地図が、グラフのネットワークの接続性に実質的に影響を及ぼすたとえ１個の頂点によって変更される場合においても、時間を要し、限られた値になるかもしれない。それに代えて、予期されるパターンの蓋然性を、頂点等級の統計値から演算することができる。
【００３４】
各頂点が特定の出側等級（つまり、Ｕターンまたはループを含めた現在の頂点に続くことのできるエッジ）を備える、関連付けされた確率を有する道路ネットワークの確率的な見方について考える。Ｐ（ｄ）として表される出側等級ｄの確率分布は、場所に応じて多様になり得る。都市部エリアでは、一方通行の比率が大きくなり、各交差点におけるドライバの出側エッジの選択肢がより少なくなるかもしれない。都市部エリアに関する確率密度関数（ｐｄｆ）は、したがって、農村部または郊外エリアに対応する確率密度関数に比べてより低いｄ値に向けてより重く重み付けされることになろう。
【００３５】
別のノードと同一の出側等級を有するノードの確率ｐ０は、次式１のように、それらがそれぞれ同一の等級を有するという確率の合計として記述することができる。
【００３６】
【数１】
2005078066.tif 000003
【００３７】
ｐ０の値は、深さ０のツリーが１つの頂点に整合し、確率分布Ｐだけに依存する確率である。深さ１のツリーは、その等級に依存する整合の確率を考慮することによって決定することが可能な１つの頂点に整合する確率ｐ１を有する。ｐ１（ｄ）を、等級ｄを伴う根頂点に対して深さ１のツリーが整合する確率とする。リーフを相関させるために、一般性を失うことなく、リーフがその等級によって順序付けされ、したがって整合がある場合には、すべてが対応するリーフと整合すると考える。つまり、ｄ個のリーフは、整合する深さ０のツリーを有していなければならない。
【００３８】
【数２】
2005078066.tif 000004
【００３９】
深さ１のツリーが等級ｄを有する可能性がＰ（ｄ）であることから、全体的な確率ｐ１は、次式３のように表される。
【００４０】
【数３】
2005078066.tif 000005
【００４１】
また、深さｎのツリーは、次式４のように、１つの頂点と整合する確率ｐｎを有する。
【００４２】
【数４】
2005078066.tif 000006
【００４３】
これら２つの概念的なツリーマッチングの確率は、根が等級において整合し、かつそれぞれのリーフも整合する確率である。この再帰的表現は、ツリーの深さをｎ‐１からｎへ増加する際に、その演算にとって好都合である。
【００４４】
異なる地図および地図の異なるセクションは、幅広く変化する等級の統計を有すると見られるが、所定の地図に関しては、頂点の等級の統計Ｐ（ｄ）を収集することができる。表１は、ｄ＝１〜４の場合のＰ（ｄ）に関する５つの例示的なシナリオを一覧表にしている。なお、これらのシナリオにおいて、Ｐ（０）およびＰ（ｄ＞４）はゼロとする。
【００４５】
【表１】
2005078066.tif 000007
【００４６】
シナリオ１は、都市部の道路ネットワーク構成を大まかに表しており、そこにおいては、一方通行路およびターン規制が一般的である。その結果として、２方向の出側等級が強く重み付けされている。シナリオ２は、農村部の構成を表しており、そこにおいては、３方向および４方向（Ｕターン許可）の交差点が一般的である。シナリオ３〜５は、２つのｐｄｆ値だけが非ゼロであるという点において簡略化されており、ｐｄｆの重みの範囲にわたって全体的な誤り整合の確率の分析を示す上で好都合である。シナリオ３および４が確率の同一セットを有していることから、それらは異なる等級に関連付けされてはいるが、２つのシナリオは、誤り整合に関して同一の確率を有する。概して、ｐｄｆ内の確率だけが整合の可能性の計算に重要となる。
【００４７】
図５は、可能性のある整合の確率に対するツリーの深さの関係をシナリオ３〜５の範囲に関して示したプロットであり、比較のためにシナリオ１および２も含められている。この図から、よりバランスの高いＰ（ｄ）のｐｄｆほどより良好な（低い）誤り整合の確率をもたらすことが明らかである。約１００万個の頂点のうちの１つが誤り整合となる確率が、４の深さおよび５０：５０のｐｄｆで期待される値となる。また、シナリオ１および２によって例証されるように、ｐｄｆをさらに広げると、より良好な（低い）誤り整合の確率がもたらされることにも注意する必要がある。
【００４８】
図５は、また、よりバランスの低いｐｄｆ（１つの値の重み付けが高い）が、可能性のある整合の確率にどの程度の大きな影響を有するかも示している。このことは隣接するすべての曲線がｐｄｆ値において等しく１％の差を有していることから（つまり、最右翼の曲線は［０．９９  ０．０１］、その隣の曲線は［０．９８  ０．０２］となる）、右に行くほど曲線の間隔が広く、左に行くほど、視認可能であれば、曲線の間隔が狭いことによっても明らかとなる。
【００４９】
わずかに１％の頂点しか大半の共通する頂点タイプと（等級において）異ならない、非常に高い対称性がある場合（シナリオ５によって例証されるような場合）に、比較的シンプルなツリーを用いるならば、非常に低い整合の確率が予想される。たとえば、ツリーの深さ９の場合には、約１００万分の１となる偶発的な（不意の）整合の確率がもたらされる。さらに、もっとも一般的な等級をｄとすると、最大のツリーサイズは概略で次のようになることが期待される：
【００５０】
【数５】
2005078066.tif 000008
【００５１】
ここで、Ｄはツリーの深さであり、Ｎは最大の頂点の等級をｄとする地図に関するツリーにおける最大可能ノード数である。それに代えて、Ｎを、もっとも共通する頂点の等級がｄである地図内の可能ノード数の評価として定義しても良い。
【００５２】
たとえば、４のツリーの深さを使用すると、約１２０の頂点が最大ツリーサイズになり、これは一意的な表現に３０バイトを必要とすることになる（ツリーは、頂点等級の単純なフラットリスト表現によって一意的に表されることが可能であり、かつ、Ｎ個の頂点等級の値が、それぞれ等級値０〜３を表すために２ビットを必要とすることになるからである）。図４から、ツリーの深さ４が、もっとも対称性の高いシナリオを除き、非常に低い偶発的な整合の期待値を与えることは明らかである。［０．９０  ０．１０］のシナリオに関しても、偶発的な整合の確率は、１０００分の１台になる。しかしながら、約１０００万分の１もしくはさらに低い期待値が、もっとも対称性の高いシナリオを除くすべての場合に一般的である。
【００５３】
上に示したように、もっとも対称性の高いシナリオを除くすべての場合に、３〜５のツリーの深さが、通常、約１００万ないしは約１０００万分の１という低い偶発的な整合を達成する上で充分となる。また、この分析から、特定値を超える深さを伴うツリーが減少利得を提供することも明らかになる。これは、頂点またはエッジ属性を用いたツリーパターンの増加の動機付けとなる。
【００５４】
広範多岐にわたる属性が、経路計算、案内、マップマッチング、および地理的コーディングまたは逆地理的コーディング等の各種のアプリケーションに使用される。これらの属性は、パターンマッチング目的のための唯一性または有益性について、種々の程度を有する。表２は、キウィ（ＫＩＷＩ）ナビゲーション地図データベースフォーマットから抜粋した頂点およびエッジ属性の代表的なリストである。
【００５５】
【表２】
2005078066.tif 000009
【００５６】
広い範囲の値を有し、大きく変化し、あるいは高い唯一性を有する属性は、高く評価されているが、それに対して、冗長であり（内在的）、適用度が低く、まれ、あるいは低い唯一性を有する属性は、あまり高く評価されていない。表現に大量のメモリを必要とする属性についても、コンパクトな値より低く評価される。唯一性とメモリサイズ要件の間にはトレードオフが存在するが、ｎビット値が２ｎの組み合わせを有することから、このトレードオフは、小さいメモリサイズにおいてのみ関係してくる。
【００５７】
最新のものへの更新においては、ノードに関するツリーの伝達に加えて、属性情報がパターンマッチング処理操作を補助することができる。新しい頂点およびエッジの属性といったいくつかの属性情報は、明らかに最新のものへの更新に必要な部分となる。しかしながら、現在のデータベース内に存在する頂点の属性とのマッチングが行われることになる存在する頂点の属性を伝達することもできる。パッチングが行われないこれらの頂点またはエッジを、以下、無縁頂点または無縁エッジと呼ぶ。
【００５８】
概して言えば、属性タイプの値に加えて属性情報のサイズを考慮する必要がある。たとえば、道路または交差点の名前は、有用性が高いが、車線の数より多くのメモリもしくは送信帯域幅を必要とする。それに加えて、テキスト文字列または名称といった一部の属性は、かなりのメモリを必要とする。これらのサイズは、ツリーの深さの増加等の別の選択肢のメモリへの影響に応じて問題となることもあれば、ならないこともある。追加の属性より少ないメモリで誤り整合の可能性が下がるのであれば、ツリーの深さの増加の方が好ましいと言える。
【００５９】
無縁頂点またはエッジの属性を含めること、つまりパッチングされる頂点またはエッジ以外の属性を含めることは、いくつの頂点の属性を含ませるべきかという問題を呈することにもなる。メモリおよびパッチフォーマットの柔軟性が、ともに考慮されえる。ツリー内の各種の深さの頂点に関する属性といった、多様なタイプの属性および多様な量の属性をサポートする充分な柔軟性を持ったパッチフォーマットは、パッチ内にどのような情報が含まれているかについての記述を単に表現するだけで、かなりのオーバーヘッドを必要とする可能性がある。またこれは、パッチの適用およびパッチ生成ソフトウエアに関する追加的な複雑性を暗示している。一実施態様においては、もっとも小さいフィールドサイズを除いて、無縁属性を避け、より深いツリーが優先される。
【００６０】
パッチの最適内容、つまりパターンおよび属性は、統計的にあるいは決定論的に決定されることができる。統計的アプローチは、地図もしくは地図エリアに関する統計またはパッチングされるエリアに応じた動的統計（可変パッチフォーマットを必要とする）の決定を含む。考えられるところでは、これら両方のアプローチが使用されてパッチフォーマットおよび／または内容が構成される。決定論的アプローチは、特定のパッチング処理操作に関して適切なパッチ内容を決定する。
【００６１】
統計的アプローチは、所望の、あるいは目標とする誤り整合の確率の設定を必要とする。その後、蓋然論的方法が、目標値および収集した統計を使用するパッチ生成もしくはパッチフォーマット仕様に適用される。基本的な蓋然論的アプローチは、希望する誤り整合の確率とｐｎが等しくなるか、それより小さくなるように、ツリーの深さｎを決定する基礎として統計的に決定されたｐｄｆであるＰ（ｄ）を使用することができる。この方法は、特定の期待される誤り整合の確率ｐｆを含意する。図６は、所望のｐｆを達成するために必要となるツリーの深さを決定する方法を示したフローチャートである。基本的な蓋然論的アプローチを拡張し、属性の唯一性に関する統計についても収集を行うことによって属性を組み込むことができる。たとえば、統計的収集は、Ｌ車線を有する道路、または『メインストリート』という名前を有する道路の確率の決定を含むことができる。ツリーパターンを伴わない唯一的な道路名は、同一の道路セグメント上に複数の頂点が存在することがあるため、あるいは複数の頂点が１つの交差点を表すことがあるために、ゼロでないかなりの誤り整合の可能性を有することがある。統計を収集した後、それらをＰ（ｄ）のｐｄｆとともに使用し、図６に示した方法に類似の方法に従って、必要なツリーの深さおよび属性の内容を求める。
【００６２】
代替アプローチは、更新パラメータの選択に関する適応的方法を使用することである。ツリーの深さの選択、あるいは特定の属性を含めるべきか否かといった更新パラメータの決定は、更新の生成時に行なわれ、たとえば更新される特定の頂点もしくはエッジの唯一性に依存することがある。
【００６３】
一実施態様においては、個別のパッチ指示の内容が特定の時点において適用に充分であったとしても、自己矛盾のない状態が保証され、かつ意図されたとおりにパターンマッチングが生じることを保証するために、特定の時間が定義されるようにパッチの時間的な適用可能性が定義される。パッチは、ある意味では、整合を試みるパターンを変更する。
【００６４】
図７は、（ａ）現存するナビゲーション地図データベース、（ｂ）パッチングされる新しい高速道路およびランプ、および（ｃ）パッチングされた後のナビゲーション地図データベースを図示している。パッチ順序規則セットによれば、現存するデータベースの頂点に接続されるリンクで始まる順序に従ってリンクが追加される。したがってランプは、高速道路セクションより前に追加される。たとえばエッジ「ｄ」が追加され、それに続いてエッジ「ｅ」、その後にエッジ「ｆ」という形で追加される。さらに、当該規則によれば、頂点７が存在しないことから、まずエッジ「ａ」が、中間の新しい頂点７を経由して頂点１を頂点３に接続する２つの新しいエッジによって置き換えられる。
【００６５】
図８は、現存するエッジ「ａ」に沿って、その中間点において図６の高速道路の入口ランプエッジ「ｄ」を追加する累積効果を達成するパッチの更新のマルチステップ部分を図示している。この４ステップのプロセスは、オリジナルのエッジの削除、結合して削除済みのエッジに置き換わる２つのエッジの追加、およびランプを表す新しいエッジの追加を含む。ここで注意を要するが、第２のパッチ順序規則により、クラス２ａマッチングに関係する混乱ならびにパターンマッチングの複雑化が生じることを避けるために、ｚ等のクラス２ａの頂点が、エッジ置換ステップを介してクラス２ｂの頂点として追加されるので、ランプが直接追加されていない。
【００６６】
ｘ１を頂点１として認識すれば、エッジａ（ｉ）が削除され、頂点１が頂点３に接続されなくなることから、ｘ１とｘ２に関するパターングラフ（ツリー）は異なる。言い換えると、ステップ１は、ノード１（頂点１）が異なる等級およびツリーを有するように現存するデータベースを変更する。頂点１に対してｘ２を整合させるために新しいパターンマッチングが必要となった場合には、頂点１に関する最新のツリーに整合するｘ２のための有効なツリーが必要になる（つまり、ｘ２のツリーが頂点３に対するエッジを含まない）。幸いに、本発明を用いればこれが必要とならない。
【００６７】
ｘ２のための第２の異なるツリーが必要とならない理由は、パッチの適用がすでに頂点１に対してｘ１を整合させていることによる。したがって、更新ステップ２は、ｘ２がｘ１であることを指定するだけでよい。識別子またはポインタ／オフセットを使用して、その種の指定を達成することができる。一方、パッチの適用においては、ｘ１に整合するノードを調べて、ｘ２がそのノードに整合することを宣言する。つまり、好ましい実施態様においては、所定の頂点に関して、その頂点のツリーが１ないしは複数回にわたって変更されている場合であっても、１つのツリーを超えて送る必要がない。
【００６８】
したがって図８の更新は、以下の表３に示される内容を有するものとすることができる。ここで注意を要するが、直ちに関係付けされないステップについても同等の頂点の宣言が有効である。たとえば頂点３から伸びる新しい道路の追加を、同じ更新の部分とし、頂点３に整合する頂点に関するツリーを含めずに、ソースノードがｙ１に等しいとする宣言を含めることができる。
【００６９】
【表３】
2005078066.tif 000010
【００７０】
上記の表３内の更新ステップは、ｉ〜ｌとしてラベル付けされて、それらがパッチ指示のより大きなリストの部分であり、必ずしも一緒にまとめられる必要がないことを示す。実際、宣言が順序を反映する場合には指定された順序が重要になるが、それらは一緒にもしくは順番にグループ化することさえも必要ない。パッチの指示部分は、その種の指示およびそれらの関連するパラメータ、または関連するパラメータに対するポインタの順序づけされたリストによって表すことができる。たとえばツリーは、パッチの別のセクション内に格納されてもよい。
【００７１】
この種の宣言を使用して更新を系統化することは、基本的に圧縮もしくは帯域幅要件によって動機付けされるものではなく（ただし、結果的に非常にコンパクトな更新がもたらされる）、むしろ時間的な複雑化および因果関係の複雑化を避けるためである。更新ステップは、同一パターンがその後整合しなくなるようにグラフの構造または属性を修正する。それに加えて、その後に続く近隣の頂点を整合する試みが、構造的な変更に起因して失敗するようにもできる。
【００７２】
パッチ適用プロセス内におけるグラフ更新ステップの時間的な順序付けは、そのプロセスの間に、全体的なグラフ構造および限局的なグラフパターンにおいて、特定の、可能性としては異なるダイナミクスをもたらす。この問題の認識は、地図データベースの更新内容、すなわちパッチ生成の宣言規則、およびパッチ適用に関する識別優先順位規則を基礎とする。時間的な順序付けは、ＭＳＴ等のグラフパターンが、特定の時期においてのみ有効であることを示唆する。
【００７３】
宣言規則は、頂点Ｘの整合を要求している任意のグラフ更新ステップが、同じノード（頂点）に対応する頂点Ｙが、に対してが以前のステップにおいて整合されるべきであるとすでに要求されていた場合には、（頂点Ｘに関するグラフパターンを含める代わりに）以前の更新における対応する頂点Ｙに対して頂点Ｘの等価を宣言するものとして定義される。しかしながら、以前のステップにおいて頂点が修正されていない場合であっても、近隣の頂点が修正されており、実質的に限局的なグラフパターンが変更されていることがある。これにおいて「限局的」は、無修正頂点を取り巻くグラフパターンを言い、「近隣」はＭＳＴの深さによって定義されるような限局的グラフパターンの外延を言う。限局的なグラフパターンは、パッチ更新内に含まれていた可能性のある頂点に関する整合パターンが、無修正および修正された限局的グラフパターンのいずれにも整合しないときに実質的に修正される。本質的に、パターンは、特定の時間的適用可能性（または有効性）を有している。一実施態様においては、適用可能性の時間が、パッチが適用される前に定義されることになり、それが識別優先順位規則に関する基礎となっている。
【００７４】
識別優先順位規則は、頂点に整合するパターンの時間が、（ｉ）クラス１頂点の場合には、パッチのあらゆるステップの適用の前となること、および（ｉｉ）クラス２頂点の場合には、パターンマッチングが必要なく、むしろ宣言規則に従って、その後に続く同じ頂点に対するすべての参照が等価であると宣言されることを指定する。この識別優先順位規則の結果、各頂点に関するグラフパターン情報が、各パッチについて１度だけ伝達されればよく、すべてのクラス１頂点（整合が必要とされる唯一の頂点）は、パッチ適用の識別またはパターンマッチングステージと呼ぶことのできる部分内において、いかなる変更の前に整合されることが可能になる。
【００７５】
データベースが１回以上パッチングされた場合には、パッチ管理が非常に複雑になり得ることが予測される。一実施態様においては、パッチ間の互換性がパターンマッチングについてオリジナルのデータベースのみを常に使用することによって、及び新しい頂点の識別を維持することによって維持される。別の実施態様においては、次のパッチの適用前の改良済みデータベースを用いてパターンマッチングを行うことによってその後に続くパッチが適用される。
【００７６】
図９は、ナビゲーション地図データベースの更新内容の一例を図示している。更新９０は、３セットの情報からなる。すなわち、（ｉ）マッチングに使用される論理パターン９２、（ｉｉ）実際の、または暗示的な等価の宣言を含むリンクの追加または削除の指示９４、および（ｉｉｉ）修正後またはパッチング後のデータベースに格納されるべき新しい、もしくは置換（更新）データ９６である。各指示は、始点および終点ノードの両方の整合に使用するパターンのインデクスまたは識別子９７、指示のタイプ（追加または削除）９８、および該当する場合には新しい、あるいは置換データに対するポインタまたはインデクス９９を含むことができる。ナビゲーションデータベースに対する変更は、ステップ内に記述されている。各ステップ（指示）は、２つの交差点（ノード）間の１つのリンク（道路区間）に対する単一の追加または削除処理操作を記述する。変更は、影響を受ける道路および／または交差点を識別するために必要な論理パターンに関連付けされる。この論理パターンは、たとえばツリーパターンを含み、また識別の補助となる１ないしは複数の有用性の高い属性パターンで補足されることもあれば、補足されないこともある。なお、すでに示した原理ならびにパッチ規則に適合する、このほかの手順またはフォーマットが使用可能であることも容易に理解される。
【００７７】
図１０は、前述した原理ならびにパッチ規則に従ってナビゲーションデータベースに更新を適用するための手順の一例を示している。図１０は、パッチ内の各指示を循環するループを示している。一実施態様においては、すべてのパターンが、前述した時間的な規則ならびに原理に従って既に整合されている。別の実施態様においては、ステップ１０４に示されているように、１つの指示の開始および終了ノードのそれぞれに関して、必要であればパターンマッチングが実行される。しかしながら好ましい実施態様においては、パターンマッチングが、受信した論理パターンを、特定の時点、たとえばそのパッチからのいずれかの指示が適用されてしまう前にデータベースと比較する。開始および終了ノードが識別され、分類された後に、パッチ処理操作が決定される（すべてのパターンマッチングの完了まで実行を遅延させることができるため、必ずしもここで実行される必要はない）。クラス２ａノードは、ステップ１１０に示されているように、それらをクラス１ノードに変更する操作を挿入することによって処理される。ここで注意されたいが、追加時、すなわちパッチ処理操作の実際の実行時においては、すべてのクラス２（ａまたはｂ）ノードがクラス１ノードになる。パッチ順序付け規則によれば、孤立リンク（つまり、開始および終了ノードがともにクラス２ｂのリンク）の追加は、ステップ１１８に示されているように、少なくとも一方のノードがクラス２ｂノードでなくなるまで遅延される。なお、前述した原理およびパッチ規則に適合するこのほかの手順が使用できることが容易に理解される。
【００７８】
図１１は、パターンマッチングおよび分類に関する手順の一例を示している。パターンマッチング処理操作は、ステップ１２２に示されているようにまず、現存するデータベースから、更新されることになる頂点の全体的な近傍内に含まれる頂点を収集する。たとえば、これには、更新されることになる頂点に関して与えられた概略の位置の物理的な範囲内において頂点をサーチすることを含めることができる。手順は、オプションとして、概略の位置に対する近接度合によってこれらをソートしてもよい。その後、各候補頂点について、論理パターンがステップ１２４において現存するデータベースから構築され、ステップ１２６において更新により供給されたパターンと比較される。整合が見つかった場合には、その頂点がクラス１頂点として分類される。それに対して範囲内の頂点のいずれも整合しない場合には、ステップ１３２においてそのノードがクラス２頂点であると決定される。整合の可能性のある実施形態は、最初に『正確に』整合したツリー、または最良整合のツリーを含む。各種の変形が可能であり、それについてはすでに説明したとおりである。それに加えて、さらにクラス２頂点をクラス２ａまたは２ｂに分類することが、近隣内の各リンク上の始点と終点の間に頂点があるかのようにパターンを構築することによって達成される。その種の『仮想』頂点を用いて整合が得られた場合には、更新頂点がクラス２ａとして分類される。このほかの、前述した原理ならびにパッチ規則に適合する手順およびフォーマットが使用できることは容易に理解される。
【００７９】
本発明のパターンマッチングおよび分類の方法は、データベースバージョンの問題および更新バージョンの適用可能性の検出にも使用することができる。明らかに（パッチ順序規則に関して）順序外の指示は、ナビゲーションシステムが以前の更新を行わなかったことを示すことができる。すでに存在しないリンクの削除またはすでに存在するリンクの追加のための指示は、データベースバージョンがすでに更新を含んでいることの尺度となり得る。さらに本発明の方法は、複数形式のナビゲーション地図データベース記憶装置に適用することができる。ナビゲーション地図データベースは、キウィ（ＫＩＷＩ）データベースのパーセル（案内）および地域（経路計算）セクション等のように、特定のアプリケーション用に調整された複数の道路ネットワークの表現を含むことができる。その場合においては、代替表現を、パターンの整合（識別）およびノード（またはリンク）の分類の確認のため、あるいはパターン生成のための支援もしくは代替ソースとして使用することが可能になる。
【００８０】
変形実施態様においては、ナビゲーション地図データベースもしくはナビゲーション地図データベースの部分を記憶するためにランダムアクセスメモリが使用されてもよく、分離されたパッチメモリを維持する代わりにデータベースに対して更新を直接適用することができる。
【００８１】
以上の本発明の説明は、本質的に例示に過ぎず、本発明の要旨から逸脱することのない変形は、本発明の範囲内に含まれることが意図されている。その種の変形は、本発明の思想および範囲からの新しい発展とは見なされない。
【図面の簡単な説明】
【００８２】
【図１】本発明による改良されたナビゲーションデータベースのアーキテクチャを示す図である。
【図２】本発明による道路地形の論理表現の一例を表した図である。
【図３】（ａ）はナビゲーションシステムの地図データベース内に頂点ｃが存在するときの、その頂点ｃに関する、本発明に従った最小スパンツリー（ＭＳＴ）構造の一例を示した図であり、（ｂ）は本発明による更新指示に関して構築される論理表現を示した図である。
【図４】本発明よる頂点ｃに関する全スパンツリーの構造の一例を示した図である。
【図５】異なる道路ネットワーク対称シナリオに関する誤りパターン整合の確率を示したグラフである。
【図６】所望の整合確率を達成するために必要なツリーの深さを決定する方法を示したフローチャートである。
【図７】（ａ）はオリジナルの限局的グラフパターンを示し、（ｂ）はパッチグラフパターンを示し、および（ｃ）はパッチングされた限局的グラフパターンを示した図である。
【図８】本発明のパッチ順序規則に従うパッチ更新のマルチ‐ステップ部分を示した図である。
【図９】ナビゲーション地図データベース更新の内容の一例を示した図である。
【図１０】本発明に従ってナビゲーションデータベースに対して更新を適用するための手順の一例を示したフローチャートである。
【図１１】パターンマッチングおよび分類に関する手順の一例を示したフローチャートである。
【図１】
2005078066.tif 000011
【図２】
2005078066.tif 000012
【図３】
2005078066.tif 000013
【図４】
2005078066.tif 000014
【図５】
2005078066.tif 000015
【図６】
2005078066.tif 000016
【図７】
2005078066.tif 000017
【図８】
2005078066.tif 000018
【図９】
2005078066.tif 000019
【図１０】
2005078066.tif 000020
【図１１】
2005078066.tif 000021