(57)【要約】【課題】  ナビゲーション装置において使用する検索データの効率のよい更新方法および更新システムを提供すること。【解決手段】  検索データの更新システムは、検索データを使用するナビゲーション装置１と、ナビゲーション装置へ検索データの更新データを提供するデータ提供センタ９からなる。ナビゲーション装置１は、検索木データと検索木データから指定される複数の実体データとからなる検索データ本体を記録媒体２から読み込む。データ提供センタ９は、ナビゲーション装置１へ検索データの更新データを提供する。更新データは、実体データごとに提供されかつ実体データごとに検索に使用されるインデックスが付加されている。ナビゲーション装置１は、データ提供センタ９から更新データを取得すると、取得した更新データを、検索データ本体とは別に不揮発性メモリ１２に記憶する。【選択図】        図１
2005208744.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーション装置用検索データの更新方法であって、
更新前の検索データは、検索木データと検索木データから指定される複数の実体データとからなるデータであり、
検索データの実体データを更新あるいは追加するとき、前記検索木データと検索木データから指定される複数の実体データとからなるデータとは別に、実体データごとに検索に関係する情報が付加され実体データを提供することを特徴とするナビゲーション装置用検索データの更新方法。
【請求項２】
請求項１に記載のナビゲーション装置用検索データの更新方法において、
ナビゲーション装置において、前記提供された実体データごとに検索に関係する情報が付加され実体データを、前記検索木データと検索木データから指定される複数の実体データとは別に更新データとして保存することを特徴とするナビゲーション装置用検索データの更新方法。
【請求項３】
検索データの更新システムであって、
検索データを使用するナビゲーション装置と、
前記ナビゲーション装置へ検索データの更新データを提供する検索データ提供装置とからなり、
前記ナビゲーション装置は、検索木データと検索木データから指定される複数の実体データとからなる第１の検索データを記憶する第１の記憶手段と、第２の記憶手段と、前記検索データ提供装置から検索データの更新データを取得する更新データ取得手段とを備え、
前記更新データは、実体データごとに提供されかつ実体データごとに検索に使用される情報が付加されたデータであり、
前記更新データ取得手段は、前記検索データ提供装置から前記更新データを取得すると、前記取得した更新データを、前記第１の検索データとは別に前記第２の記憶手段に記憶し、
前記ナビゲーション装置は、  前記第１の記憶手段に記憶された前記第１の検索データと前記第２の記憶手段に記憶された前記更新データを使用して、実体データの検索を行う検索手段をさらに備えることを特徴とする検索データの更新システム。
【請求項４】
請求項３に記載の検索データの更新システムにおいて、
前記ナビゲーション装置の更新データ取得手段は、新たに更新データを取得すると、すでに前記第２の記憶手段に記憶している更新データと合わせて前記検索に使用される情報に基づいてソートをかけ、ソート後の更新データを前記第２の記憶手段に記憶することを特徴とする検索データの更新システム。
【請求項５】
請求項３から４のいずれかに記載の検索データの更新システムにおいて、
前記ナビゲーション装置は、前記検索手段により得られた実体データを使用して、経路探索および経路誘導を含むナビゲーション処理を行う制御手段をさらに備えることを特徴とする検索データの更新システム。
【請求項６】
請求項３から５のいずれかに記載の検索データの更新システムにおいて、
前記ナビゲーション装置の更新データ取得手段は、取得した更新データの数が所定の数以上になると、その旨を音声あるいは表示により知らせる出力をすることを特徴とする検索データの更新システム。
【請求項７】
請求項３から５のいずれかに記載の検索データの更新システムにおいて、
前記ナビゲーション装置の更新データ取得手段は、取得した更新データの数が所定の数以上になると、前記更新データの実体データを含んだ新たな検索木データと検索木データから指定される複数の実体データとからなる新たな第１の検索データを取得し、取得した新たな第１の検索データを前記第１の記憶手段に記憶することを特徴とする検索データの更新システム。
【請求項８】
請求項５に記載の検索データの更新システムにおいて、
前記ナビゲーション装置は、検索キーを１文字ごとに入力することが可能な入力手段をさらに備え、
前記検索手段は、前記入力手段により１文字入力されるごとに、前記第１の検索データの検索木を使用した検索を進め、同時に、前記第２の記憶手段に記憶された複数の更新データの前記検索に使用される情報との比較を行い、前記比較の結果対象から外れた更新データには対象外を示す指標を施すことを特徴とする検索データの更新システム。
【請求項９】
請求項３から８のいずれかに記載の検索データの更新システムにおいて、
前記ナビゲーション装置の更新データ取得手段は、更新すべき検索データの範囲に関する情報を前記検索データ提供装置へ送信し、
前記検索データ提供装置は、前記受信した更新すべき検索データの範囲について更新データがある場合、前記ナビゲーション装置へ該範囲の更新データを提供することを特徴とする検索データの更新システム。
【請求項１０】
請求項３から９のいずれかに記載の検索データの更新システムにおいて、
前記ナビゲーション装置の更新データ取得手段は、前記第２の記憶手段に格納している更新データのバージョンに関する情報を前記検索データ提供装置へ送信し、
前記検索データ提供装置は、前記受信したバージョンに関する情報に基づくバージョンより新しい実体データがある場合、該新しい実体データに関する更新データを前記ナビゲーション装置へ提供することを特徴とする検索データの更新システム。
【請求項１１】
請求項３から１０のいずれかに記載のナビゲーション装置。
【請求項１２】
請求項３から１０のいずれかに記載の検索データ提供装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置に使用する検索データの更新方法および更新システムに関する。
【背景技術】
【０００２】
カーナビゲーション装置において、地図を複数のユニットに分割し、各ユニット単位で地図データファイルを作成し、各ユニット単位で地図データファイルを更新する技術が知られている（例えば、特許文献１）。また、コンピュータ通信を用いた地図情報サービスにおいて、地図データ表示端末中の表示メモリに既に存在する地図データの送信を省略し新規に送出する必要のある地図データのみを送る技術が知られている（例えば、特許文献２参照）。
【０００３】
【特許文献１】特開２００１−５６８２３号公報
【特許文献２】特開平１１−２９５０８４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、これらは地図データの更新に関する技術であり、ナビゲーション装置で使用する検索データの更新について考慮されたものではない。通信などにより地図データや検索データを提供する場合、検索データにおいても効率のよい更新方法が望まれる。
【０００５】
本発明は、ナビゲーション装置において使用する検索データの効率のよい更新方法および更新システムを提供する。
【課題を解決するための手段】
【０００６】
請求項１の発明は、ナビゲーション装置用検索データの更新方法に適用され、更新前の検索データは、検索木データと検索木データから指定される複数の実体データとからなるデータであり、検索データの実体データを更新あるいは追加するとき、検索木データと検索木データから指定される複数の実体データとからなるデータとは別に、実体データごとに検索に関係する情報が付加され実体データを提供することを特徴とするものである。
請求項２の発明は、請求項１に記載のナビゲーション装置用検索データの更新方法において、ナビゲーション装置において、提供された実体データごとに検索に関係する情報が付加され実体データを、検索木データと検索木データから指定される複数の実体データとは別に更新データとして保存することを特徴とするものである。
請求項３の発明は、検索データの更新システムに適用され、検索データを使用するナビゲーション装置と、ナビゲーション装置へ検索データの更新データを提供する検索データ提供装置とからなり、ナビゲーション装置は、検索木データと検索木データから指定される複数の実体データとからなる第１の検索データを記憶する第１の記憶手段と、第２の記憶手段と、検索データ提供装置から検索データの更新データを取得する更新データ取得手段とを備え、更新データは、実体データごとに提供されかつ実体データごとに検索に使用される情報が付加されたデータであり、更新データ取得手段は、検索データ提供装置から更新データを取得すると、取得した更新データを、第１の検索データとは別に第２の記憶手段に記憶し、ナビゲーション装置は、第１の記憶手段に記憶された第１の検索データと第２の記憶手段に記憶された更新データを使用して、実体データの検索を行う検索手段をさらに備えることを特徴とするものである。
請求項４の発明は、請求項３に記載の検索データの更新システムにおいて、ナビゲーション装置の更新データ取得手段は、新たに更新データを取得すると、すでに第２の記憶手段に記憶している更新データと合わせて検索に使用される情報に基づいてソートをかけ、ソート後の更新データを第２の記憶手段に記憶することを特徴とするものである。
請求項５の発明は、請求項３から４のいずれかに記載の検索データの更新システムにおいて、ナビゲーション装置は、検索手段により得られた実体データを使用して、経路探索および経路誘導を含むナビゲーション処理を行う制御手段をさらに備えることを特徴とするものである。
請求項６の発明は、請求項３から５のいずれかに記載の検索データの更新システムにおいて、ナビゲーション装置の更新データ取得手段は、取得した更新データの数が所定の数以上になると、その旨を音声あるいは表示により知らせる出力をすることを特徴とするものである。
請求項７の発明は、請求項３から５のいずれかに記載の検索データの更新システムにおいて、ナビゲーション装置の更新データ取得手段は、取得した更新データの数が所定の数以上になると、更新データの実体データを含んだ新たな検索木データと検索木データから指定される複数の実体データとからなる新たな第１の検索データを取得し、取得した新たな第１の検索データを第１の記憶手段に記憶することを特徴とするものである。
請求項８の発明は、請求項５に記載の検索データの更新システムにおいて、ナビゲーション装置は、検索キーを１文字ごとに入力することが可能な入力手段をさらに備え、検索手段は、入力手段により１文字入力されるごとに、第１の検索データの検索木を使用した検索を進め、同時に、第２の記憶手段に記憶された複数の更新データの検索に使用される情報との比較を行い、比較の結果対象から外れた更新データには対象外を示す指標を施すことを特徴とするものである。
請求項９の発明は、請求項３から８のいずれかに記載の検索データの更新システムにおいて、ナビゲーション装置の更新データ取得手段は、更新すべき検索データの範囲に関する情報を検索データ提供装置へ送信し、検索データ提供装置は、受信した更新すべき検索データの範囲について更新データがある場合、ナビゲーション装置へ該範囲の更新データを提供することを特徴とするものである。
請求項１０の発明は、請求項３から９のいずれかに記載の検索データの更新システムにおいて、ナビゲーション装置の更新データ取得手段は、第２の記憶手段に格納している更新データのバージョンに関する情報を検索データ提供装置へ送信し、検索データ提供装置は、受信したバージョンに関する情報に基づくバージョンより新しい実体データがある場合、該新しい実体データに関する更新データをナビゲーション装置へ提供することを特徴とするものである。
請求項１１の発明は、ナビゲーション装置に適用され、請求項３から１０のいずれかに記載のナビゲーション装置とするものである。
請求項１２の発明は、検索データ提供装置に適用され、請求項３から１０のいずれかに記載の検索データ提供装置とするものである。
【発明の効果】
【０００７】
本発明は、以上説明したように構成しているので、次のような効果を奏する。
検索木データと検索木データから指定される複数の実体データとからなる検索データとは別に、実体データごとに提供される更新データを取得して保存するので、更新データの容量が極めて小さくてすむ。また、最新の検索データを使用することができる。特に、通信で更新データを提供する場合に、送信データはわずかな量で済み通信コストが低減される。
【発明を実施するための最良の形態】
【０００８】
図１は、本実施の形態の、ナビゲーション装置に使用する検索データの更新システムを示す図である。車載用ナビゲーション装置１は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体２から、地図データや検索データ（案内検索データ）などを読み取る。データ提供センタ９のサーバ６は、地図データベース７や検索データベース８から地図データや検索データを読み取り、地図データや検索データの更新データをナビゲーション装置へ提供する。
【０００９】
ナビゲーション装置１は、携帯電話などの通信装置４と接続可能である。ナビゲーション装置１は、通信装置４を介して電話回線網５に接続し、さらに電話回線網５を介してサーバ６に接続することができる。サーバ６は、古い地図データから最新の地図データまでを地図データベース７に保有し、また、古い検索データから最新の検索データまでを検索データベース８に保有する。従って、サーバ６は、地図データや検索データの一部を更新する更新データを電話回線網５を介してナビゲーション装置１に提供することができる。
【００１０】
ナビゲーション装置１は、制御装置１１と不揮発性メモリ１２を有する。制御装置１１は、マイクロプロセッサおよびその周辺回路から構成される。不揮発性メモリ１２は、ナビゲーション装置１の内部に設けられたハードディスクや、フラッシュメモリなどの不揮発性メモリである。不揮発性メモリ１２は、ナビゲーション装置１の電源が落とされても、書きこまれたデータが消えない記憶装置であればどのようなものでもよい。
【００１１】
データ提供センタ９の地図データベース７や検索データベース８は、新旧すべての地図データや検索データなどを有しているためマザーデータのデータベースである。サーバ６は、地図データベース７や検索データベース８を使用して、初期の（更新前の）地図データや検索データなどを有する記録媒体２を準備することもできる。
【００１２】
図２は、車載用ナビゲーション装置１のブロック図である。ナビゲーション装置１は、制御装置１１、不揮発性メモリ１２、現在地検出装置１３、ＤＶＤ駆動装置１４、メモリ１５、通信インターフェース１６、入力装置１７、モニタ１８などを有する。
【００１３】
現在地検出装置１３は車両の現在地を検出する現在地検出装置であり、例えば車両の進行方位を検出する方位センサや車速を検出する車速センサやＧＰＳ（Global Positioning System）衛星からのＧＰＳ信号を検出するＧＰＳセンサ等から成る。ＤＶＤ駆動装置１４は、記録媒体２を搭載して地図データなどを読み込む装置である。本実施の形態では、記録媒体２はＤＶＤ−ＲＯＭとする。なお、ＣＤ−ＲＯＭや他の記録媒体であってもよい。
【００１４】
メモリ１５は、現在地検出装置１３によって検出された車両位置情報等を格納したり、制御装置１１が演算した推奨経路上のノード情報やリンク情報等を格納するメモリである。メモリ１５は制御装置１１のワーキングエリアである。通信インターフェース１６は、通信装置４を接続するインターフェースである。通信インターフェース１６を介して携帯電話の利用や、インターネットとの接続が可能である。
【００１５】
モニタ１８は、地図や推奨経路や各種情報を表示する表示装置である。モニタ１８は、ナビゲーション装置本体の一部として一体に設けてもよいし、筐体としては別々に設けてもよい。さらに、モニタ１８のみを、ナビゲーション装置本体とケーブルなどによって接続し、分離した位置に設けるようにしてもよい。入力装置１７は、経路探索時に車両の目的地等を入力したりする入力装置である。検索キーを入力するときにも使用する。リモコンであってもよいし、モニタ１８の画面上に設けられたタッチパネルなどで構成してもよい。
【００１６】
制御装置１１は、現在地検出装置１３で検出された車両の現在地情報と記録媒体２や不揮発性メモリ１２に格納された地図データや検索データなどを使用して、道路地図の表示、経路計算（経路探索）、経路誘導等の各種のナビゲーション処理を行う。なお、制御装置１１が実行する各種の処理プログラムは、制御装置１１内部に設けられたＲＯＭ（不図示）に組み込まれている。
【００１７】
データ提供センタ９のサーバ６はコンピュータシステムであり、地図データベース７や検索データベース８を使用して、更新データの提供をはじめ各種の処理を行う。サーバ６のコンピュータシステムは、汎用コンピュータやワークステーションやパソコンなど各種のコンピュータにより構成できる。
【００１８】
次に、ナビゲーション装置１で使用される地図データと検索データについて説明する。
【００１９】
−地図データ−
地図データは、地図に関する情報であり、背景（地図表示用）データ、道路（ロケータ用）データ、経路探索用データ（ネットワークデータ）、経路誘導用データ（交差点名称・道路名称・方面名称・方向ガイド施設情報など）などのデータ種別がある。背景データは、道路や道路地図の背景を表示するためのデータである。道路データは、車両の道路上の位置（現在地）の特定やマップマッチングなどに使用されるデータである。経路探索用データは、道路形状とは直接関係しない分岐情報などから成るデータであり、主に推奨経路を演算（経路探索）する際に用いられる。経路誘導用データは、交差点の名称などから成るデータであり、演算された推奨経路に基づき運転者等に推奨経路を誘導する際に用いられる。
【００２０】
道路データ（ロケータ用データ）は、例えば道路をリンクとノードとリンク列という概念で表した場合のリンク列データである。ノードは交差点や道路上特に指定された点を言う。リンクはノード間の道路に該当し、リンク列は１本の道路を複数のリンクで表したものである。リンク列データは、公知な内容である。背景データは、例えば、ポリゴンやポリラインなどのデータである。道路の表示は、ポリラインなどのデータを使用して行う。
【００２１】
−検索データ−
検索データは、所望の地点を地図上で設定するのではなく、検索して求めるときに使用されるデータである。例えば、経路探索の目的地を設定するときに、施設の名称や電話番号や住所などを入力することにより、その施設の位置を検索データを使用して求める。制御装置１１は、検索データを使用して求めた地点を例えば目的地として設定し、経路探索などの処理を行う。
【００２２】
検索データは、種別として、名称（読み）検索データ、電話番号検索データ、住所検索データなどがある。名称検索データは、施設名称により地図上の位置を特定するために使用されるデータであり、カテゴリ（ジャンル）ごとに都道府県単位でデータファイルが作成されている。カテゴリには、例えば「駅」「空港」「フェリー」「デパート」「ホテル」などがある。各ファイルの中には、名称により検索できる検索木（ツリー）データと実体データが格納されている。
【００２３】
電話番号検索データは、電話番号により地図上の位置を特定するために使用されるデータであり、市外局番の上２けた単位でデータファイルが作成されている。各ファイルの中には、電話番号により検索できる検索木データと実体データが格納されている。住所検索データは、住所により地図上の位置を特定するために使用されるデータであり、各都道府県の市区町村単位でデータファイルが作成されている。各ファイルの中には、住所により検索できる検索木データと実体データが格納されている。上記各検索データの実体データは、各施設の名称情報、電話番号情報、住所情報、位置情報などのデータを有する。なお、検索データにおける位置情報とは、緯度経度などで特定される位置座標データである。
【００２４】
−検索データの更新−
次に、本発明の特徴である検索データの更新について説明する。図３は、検索データの更新に関するナビゲーション装置１とデータ提供センタ９との情報のやり取りを示す図である。ナビゲーション装置１の処理は、制御装置１１が所定のプログラムを実行することにより行う。データ提供センタ９の処理は、サーバ６が所定のプログラムを実行することにより行う。
【００２５】
図３のナビゲーション装置１側の処理は、ナビゲーション装置１のメニュー画面などで「検索データの更新」というメニューが選択されることにより開始する。また、更新したい検索データの種別も予め選択されているものとする。検索データの種別の選択では、データ種別（種類）の選択画面をモニタ１８に表示する。その後、ユーザが入力装置１７を使用して更新データの種別を選択するのを待つ。データ種別の選択画面は、例えば「名称検索データ」「電話番号検索データ」「住所検索データ」の表示を行い、ユーザがいずれかを選択可能とする。ユーザの選択操作に基づきデータ種別を特定（選択）する。
【００２６】
ステップＳ１では、ナビゲーション装置１の制御装置１１は、まず通信インターフェース１６を介して通信装置４である携帯電話に、データ提供センタ９の電話番号に電話させるように制御する。電話がつながると、更新要求を送信する。更新要求は、更新すべき検索データの種別、ナビゲーション装置１に格納されている検索データのバージョン情報（版、更新日付、データ作成日付等）を送信することにより行う。検索データのバージョン情報は、制御装置１１が、記録媒体２および不揮発性メモリ１２に格納されている検索データの最新バージョンを確認することにより取得される。なお、本実施の形態では、記録媒体２のオリジナルデータのバージョン情報と更新データすべてのバージョン情報を送信する。また、ナビゲーション装置１とデータ提供センタ９の間は、携帯電話のデジタルデータの通信機能を利用して行う。
【００２７】
ステップＳ１１では、データ提供センタ９のサーバ６は、送信されてきた要求の確認を行う。具体的には、送信されてきた検索データの種別とバージョン情報に基づき、検索データベース８にアクセスし、そのバージョンより新しい検索データ（実体データ）があるかどうかを確認する。その後、確認結果をナビゲーション装置１に送信する。
【００２８】
ステップＳ２では、最新データがあるという結果が戻ってきた場合、ナビゲーション装置１の制御装置１１は、更新地域をユーザに確認する。具体的には、「検索データの更新する地域を指定してください」のようなメッセージを、音声により出力したり、モニタ１８上に表示したりする。モニタ１８には地図画面が表示され、カーソルが表示される。ユーザは、入力装置１７を使用して地図画面を上下左右にスクロールし、カーソルが所望の地域（地点)上にくるように操作する。カーソルが所望の地域（地点）にくると決定ボタンを操作し、更新地域（地点、位置）を特定する。ナビゲーション装置１の制御装置１１は、特定された更新地域（地点）およびその更新範囲の情報をデータ提供センタ９へ送信する。
【００２９】
更新範囲は、予め決められていて、例えば、特定された地域を中心として半径１０Ｋｍの範囲などとする。また、更新範囲は、更新地域が特定されたときに表示されていた地図の表示レベルや表示縮尺に応じて変化させるようにしてもよい。なお、最新データがないという結果が戻ってきた場合は、ステップＳ２で処理を終了する。
【００３０】
ステップＳ１２では、データ提供センタ９のサーバ６は、更新データの抽出を行い、抽出したデータをナビゲーション装置１へ送信する。具体的には、ステップＳ１１で受信した検索データ種別および今回送信されてきた更新位置、更新範囲に基づき、検索データベース８にアクセスし、更新データを抽出する。更新データは、ナビゲーション装置１が保有している検索データより新しいバージョンのデータが検索データベース８にある場合に、抽出される。
【００３１】
図４は、サーバ６がナビゲーション装置１へ送信する検索データの更新データのデータフォーマット（構造）を示す図である。図４（ａ）は名称検索データ、図４（ｂ）は電話番号検索データ、図４（ｃ）は住所検索データの更新データのデータフォーマットである。各更新データは、インデックス３１、ジャンル３２、実体データの名称３３、実体データの位置情報３４、バージョン３５などからなる。
【００３２】
記録媒体２に記録された検索データは、検索木と複数の実体データ（名称、電話番号、住所、位置情報）とからなる。しかし、更新データは、実体データごとに、実体データに検索キーであるインデックスが付加されたデータからなる。更新される実体データが１つの場合、図４のフォーマットの更新データが１つ送信される。複数の場合は、図４のフォーマットの更新データが複数送信される。すなわち、検索木と実体データという形式では送信されない。
【００３３】
ステップＳ３では、ナビゲーション装置１の制御装置１１は、更新データを受信し、データ提供センタ９へ受信完了メッセージを送信する。ステップＳ１３では、データ提供センタ９のサーバ６は、受信完了メッセージを受信し、送信処理を終了する。
【００３４】
一方、ナビゲーション装置１の制御装置１１は、ステップＳ３で、受信した更新データと以前に受信し不揮発性メモリ１２にすでに格納している更新データとを合わせて、インデックスに従って並べ替える、すなわち、ソートする。ソートした後の更新データを再び不揮発性メモリ１２へ記録する。
【００３５】
図５は、更新データの並べ替えの様子を説明する図である。図５（ａ）は、すでに不揮発性メモリ１２に格納されている更新データである。この例の場合、１つの更新データが格納されている。図５（ｂ）は、新たに追加される更新データである。図５（ｃ）は、すでに記録さていた更新データと新たに追加された更新データとをあわせて、五十音順にソートをして並べ替えた更新データである。ソート後の図５（ｃ）の更新データが、再び不揮発性メモリ１２に格納される。なお、不揮発性メモリ１２に記録される更新データの対象外フラグについては後述する。
【００３６】
−検索処理−
図６は、ナビゲーション装置１における検索処理のフローチャートを示す図である。図６は、名称検索データを使用した例を示す。ユーザは、入力装置１７を使用して１文字ずつ入力し、入力した文字と一致する施設名称が検索される。
【００３７】
ステップＳ２１では、制御装置１１は、ユーザが入力装置１７を使用して入力した１文字を取得する。ステップＳ２２では、検索データを使用して入力した１文字について比較処理を行う。すなわち、記録媒体２に記録された検索データの検索木を使用して１文字の比較処理を行う。なお、記録媒体２のデータは、いったんメモリ１５に読み込まれ、メモリ１５上のデータを使用して比較処理等が行われる。なお、記録媒体２のデータをいったん不揮発性メモリ１２に読み出し、その後は、不揮発性メモリ１２からメモリ１５に読み込むようにしてもよい。
【００３８】
図７は、名称検索データの検索木を使用した比較処理を説明する図である。検索木は、１つのルートセルテーブル４１と複数のセルテーブル４２〜４４から構成される。
【００３９】
ルートセルテーブル４１は施設名称の１文字目（先頭文字）のテーブルである。ルートセルテーブルのシンボル５１は、１文字目の文字の種類を示し、図７の例では「あ」「か」「さ」「た」の４文字があることを示している。検索数５２は、それぞれの文字に該当する実体データの数を示している。ポインタ５３は、下位セルテーブルへのポインタあるいは実体レコードへのポインタが入る。図７の例では、黒丸の場合は下位セルテーブルへのポインタを示し、白丸の場合は実体テーブル４６の実体レコードへのポインタを示している。
【００４０】
セルテーブルＡ４２は、ルートセルテーブル４１のシンボル「あ」のポインタによって指定されるテーブルである。この例の場合は「あ」に続く文字として「あ」「い」「ま」があり、実体データの数はそれぞれ１１、１０、７を示している。「ＢＬＡＮＫＳ」は続く文字がないことを意味し、この例の場合は「あ」だけの名称を有する実体データが３つ存在することを示している。そして、「ＢＬＡＮＫＳ」のポインタにより実体テーブルの該当実体レコードの先頭が指定される。「ＢＬＡＮＫＳ」には、また、上位セルテーブルのポインタデータも保有する。
【００４１】
セルテーブルＢ４３は、セルテーブル４２のシンボル「あ」のポインタによって指定されるテーブルである。この例の場合は「ああ」に続く文字として「す」「ち」「わ」があり、実体データの数はそれぞれ１、３、５を示している。「ＢＬＡＮＫＳ」は続く文字がないことを意味し、この例の場合は「ああ」の名称を有する実体データが２つ存在することを示している。そして、「ＢＬＡＮＫＳ」のポインタにより実体テーブルの該当実体レコードの先頭が指定される。
【００４２】
同様にして、セルテーブルＤ４５、セルテーブルＣ４４がある。ステップＳ２２では、上記の検索木のセルテーブルを使用して、入力された１文字ごとにセルテーブルを特定し、検索を進めていく。
【００４３】
次に、ステップＳ２３で、更新データのインデックス部の先頭文字から順次比較する。更新データは、前述したように、図４のデータフォーマットで不揮発性メモリ１２に格納されている。更新データは、検索木＋実体データ（検索データ本体と言ってもよい）のデータとは別に格納されている。
【００４４】
図８は、更新データのインデックスの比較処理について説明する図である。図５（ｃ）に記載された更新データを示している。図５（ｃ）では、各更新データごとに、インデックス部の前に対象外フラグを設けている。対象外フラグは、対象「０」、対象外「１」の値が格納される。ステップＳ２３での先頭からの１文字ごとの比較により、対象から外れた更新データについて対象外フラグを「１」にセットする。これにより、ステップＳ２３を実行するたびに、すべての更新データと比較処理する必要がなくなり、検索効率の向上、処理の高速化が図られる。
【００４５】
ステップＳ２４では、ステップＳ２２、Ｓ２３の処理により検索可能な検索数をモニタ１８に表示する。すなわち、今までに入力された文字を先頭から含む名称の施設数を表示する。この場合、検索木で検索される数と更新データでヒットした数の両方を合わせた数となる。
【００４６】
ステップＳ２５では、文字入力が終了したかどうかを判断する。具体的には、入力装置１７などに設けられた検索ボタンが押されたかどうかを判断する。まだ、文字入力が終了していないと判断すると、ステップＳ２１に戻り処理を続行する。文字入力が終了したと判断すると、ステップＳ２６に進む。
【００４７】
ステップＳ２６では、該当する実体データを抽出してその内容を表示する。すなわち、ステップＳ２２の検索木の比較により抽出される実体レコードと更新データのインデックス部の比較により抽出される更新データをリスト化してモニタ１８に表示する。
【００４８】
ユーザは、表示された検索結果から１つを選択する。具体的には、入力装置１７を使用してモニタ１８上のカーソルを移動させ、所望の検索候補に合わせ、決定ボタンを押す。これにより、１つの検索結果が選択される。これにより、例えば目的地の設定を検索データを使用して行うことができる。
【００４９】
−更新データの確認−
次に、更新データの確認について説明する。ナビゲーション装置１のメニュー画面などで「検索データの更新の確認」というメニューが選択されることにより、更新データの確認が行われる。例えば、入力装置１７を使用して「検索データの更新の確認」のメニューを選択し、次に、確認したい検索データの種別を選択する。データデータ種別の選択画面では、検索データの更新のときと同様に、例えば「名称検索データ」「電話番号検索データ」「住所検索データ」の表示が行われ、ユーザがいずれかを選択可能とする。ユーザの選択操作に基づきデータ種別を選択する。
【００５０】
図９は、「名称検索データ」の確認画面である。「名称検索データ」の確認画面では、さらに確認したいカテゴリを入力装置１７を使用して選択する。図９では、強調表示されている地域で、強調表示されているカテゴリの名称検索データに更新があることが示されている。すなわち、「茨城県」「栃木県」等で、カテゴリ「デパート」の名称検索データについて、更新データが不揮発性メモリ１２に格納されていることが分かる。
【００５１】
図１０は、「電話番号検索データ」の確認画面である。図１０では、強調表示されている先頭２桁の電話番号で、検索データに更新があることが示されている。すなわち、「０３」「０４」で始まる電話番号について、更新データが不揮発性メモリ１２に格納されていることが分かる。
【００５２】
図１１は、「住所検索データ」の確認画面である。「住所検索データ」の確認画面では、さらに確認したい都道府県を入力装置１７を使用して選択する。図１１では、強調表示されている都道府県内の強調表示されている市町村の地域で、住所検索データに更新があることが示されている。すなわち、「神奈川県」の「厚木市」「綾瀬市」「座間市」等で、住所検索データについて、更新データが不揮発性メモリ１２に格納されていることが分かる。
【００５３】
本実施の形態では、更新データの数が所定の数（例えば１０００件）以上になると、検索データの更新を促す表示をする。例えば「更新データが１０００件を越しましたので、最新の検索データに更新してください」というような表示、あるいは音声によるガイドを行う。これにより、ユーザは最新の検索データを更新用記録媒体２あるいは通信装置４を介して取得する。この場合の最新の検索データとは、最新の検索木と実体データからなる検索データである。このようにして取得した最新の検索木と実体データからなる検索データ本体は、不揮発性メモリ１２に格納され、今後検索データ本体は、当初の記録媒体２にはアクセスせず、不揮発性メモリ１２にアクセスして検索データ本体が取得される。
【００５４】
なお、更新データの数が所定の数以上になると、ナビゲーション装置１の制御装置１１は自動的にデータ提供センタ９に接続し、最新検索木と実体データからなる検索データを取得するようにしてもよい。また、更新データの数が所定の数以上になると、自動的に、「更新データが１０００件を越しましたので、最新の検索データに更新しますか？」というような表示、あるいは音声によるガイドを行ってもよい。これに応答して、ユーザが入力装置１７を使用して更新する旨を入力すると、制御装置１１は、データ提供センタ９に接続し、最新検索木と実体データからなる検索データを取得するようにしてもよい。
【００５５】
さらには、データ提供センタ９において検索データの更新があると、更新された検索データについて自動的にナビゲーション装置１へ送信するようにしてもよい。この場合は、図４のフォーマットで、更新のあった実体データのみが送信される。このとき、ナビゲーション装置１を所有するユーザとの間で、更新データの提供契約があるユーザに対してのみ送信するようにしてもよい。
【００５６】
以上説明した検索データの更新システムを使用すると、次のような効果を奏する。
（１）検索データに更新があった場合、検索木および検索木から指定される実体データからなる検索データ本体を更新するのではなく、更新のあった実体データのみをインデックスとともに送信するようにした。これにより、更新データの容量が極めて小さくてすみ、同時に最新の検索データを使用することができる。特に、通信で更新データを提供する場合に、送信データはわずかな量で済み通信コストが低減される。
（２）ナビゲーション装置１では、元の検索データ本体とは別に更新データを記憶するので、データの管理を容易に行うことができる。また、更新データ用の記憶容量は少なくてよい。
（３）ナビゲーション装置１では、更新データを随時蓄積していくので、常に最新の検索データをナビゲーション装置１に保持しておくことができる。また、当初の検索データ本体と更新データの双方を利用して検索を行うので、最新の検索データで検索を行うことができる。
（４）更新したい地域を指定するようにしたので、必要最低限の更新データのみを取得することができ、更新データの取得のための手間や時間やコストがかからない。また、更新したい範囲をビジュアルに指定することができ、操作が容易で分かりやすい。
（５）データ提供センタ９では、ナビゲーション装置１で保有している最新のバージョンを調べて、それよりも新しいデータがある場合のみ送信するようにしたので、無駄な更新データの提供を防止することができる。
（６）更新データは、ソートをかけてから不揮発性メモリ１２に格納するようにしたので、検索効率が向上し、処理速度が向上する。
（７）更新データには、１文字比較ごとに、対象外になった更新データを識別するフラグを設けるようにしたので、検索効率が向上し、処理速度が向上する。
（８）当初の検索データ本体と更新データとを両方保有しているので、古い検索データを参照する場合も、容易に行うことができる。
【００５７】
上記実施の形態では、ナビゲーション装置１とデータ提供センタ９とを電話回線網５で接続する例を説明したが、必ずしもこの内容に限定する必要はない。インターネットを介して接続するようにしてもよい。他の専用回線などを使用するようにしてもよい。
【００５８】
上記実施の形態では、ナビゲーション装置１側にＤＶＤ駆動装置１４を搭載する例を説明したが、必ずしもこの内容に限定する必要はない。ハードディスクなどの不揮発性メモリ１２のみを有し、地図データや検索データはすべて通信により取得するようにしてもよい。また、ナビゲーション装置１にＩＣカードなどのスロットを設け、ＩＣカードなどのリムーバブルメモリを使用して、検索データの更新データを提供するようにしてもよい。
【００５９】
上記実施の形態では、車両に搭載するナビゲーション装置の例を説明したが、必ずしもこの内容に限定する必要はない。ポータブルなナビゲーション装置にも本発明は適用できる。
【００６０】
上記実施の形態では、バージョン情報として、版、更新日付、データ作成日付等を示したが、必ずしもこの内容に限定する必要はない。数字の並びやアルファベットの並び、あるいは数字とアルファベットの組み合わせによって表されるものでもよい。すなわち、データの新旧が識別できる情報であればどのようなものでもよい。なお、本明細書ではこのような情報をバージョン情報という。
【００６１】
上記実施の形態では、ナビゲーション装置１やサーバ６が実行するプログラムは、すでに各装置に搭載されている例で説明をしたが、この内容に限定する必要はない。これらのプログラムを、ＤＶＤやＣＤ−ＲＯＭなどの記録媒体で提供するようにしてもよい。この場合には、各装置がそれらの記録媒体からデータを読み込む装置が必要となる。また、それらのプログラムをインターネットなどに代表される通信回線などの伝送媒体を介して提供するようにしてもよい。すなわち、プログラムを、伝送媒体を搬送する搬送波上の信号に変換して送信することも可能である。
【００６２】
上記実施の形態では、車両に搭載される専用ナビゲーション装置の例を説明したが、必ずしもこの内容に限定する必要はない。上述したナビゲーション装置１用の制御プログラムをパソコン上で実行させてナビゲーション装置を実現するようにしてもよい。その場合、現在地検出装置１３などはパソコンの所定のＩ／Ｏポートなどに接続するようにすればよい。
【００６３】
上記実施の形態では、検索データとして名称検索データ、電話番号検索データ、住所検索データの例を説明したが、必ずしもこの内容に限定する必要はない。その他の検索データであってもよい。すなわち、位置の特定に使用される検索データであれば、どのようなものでもよい。
【００６４】
上記実施の形態では、図６のステップＳ２６で、該当する実体データを抽出してその内容を表示する。このとき、同じ施設について、検索木の比較により抽出される実体レコードと更新データのインデックス部の比較により抽出される更新データの両方が抽出されてモニタ１８に表示される場合が生じる。この場合、抽出された実体レコードの実体データと更新データの実体データが一致していれば、更新データの実体データのみを表示するようにしてもよい。なお、更新データは、古い実体データを更新するものであるので、実体レコードの実体データと更新データの実体データとは完全一致するものではない。従って、実体データが実質的に一致するとみなせる場合に一致するとすればよい。例えば、名称、住所、電話番号、位置情報のうち、２つ以上（複数）が一致していれば一致するとしてもよいし、それぞれのデータがほぼ（例えば８割以上）一致していれば一致するとしてもよい。
【００６５】
上記では、種々の実施の形態および変形例を説明したが、本発明はこれらの内容に限定されるものではない。本発明の技術的思想の範囲内で考えられるその他の態様も本発明の範囲内に含まれる。
【図面の簡単な説明】
【００６６】
【図１】本実施の形態の、ナビゲーション装置に使用する検索データの更新システムを示す図である。
【図２】車載用ナビゲーション装置のブロック図である。
【図３】検索データの更新に関するナビゲーション装置とデータ提供センタとの情報のやり取りを示す図である。
【図４】サーバがナビゲーション装置へ送信する検索データの更新データのデータフォーマット（構造）を示す図である。
【図５】更新データの並べ替えの様子を説明する図である。
【図６】ナビゲーション装置における検索処理のフローチャートを示す図である。
【図７】名称検索データの検索木を使用した比較処理を説明する図である。
【図８】更新データのインデックスの比較処理について説明する図である。
【図９】「名称検索データ」の確認画面を示す図である。
【図１０】「電話番号検索データ」確認画面を示す図である。
【図１１】「住所検索データ」確認画面を示す図である。
【符号の説明】
【００６７】
１  ナビゲーション装置
２  記録媒体
４  通信装置
５  電話回線網
６  サーバ
７  地図データベース
８  検索データベース
１１  制御装置
１２  不揮発性メモリ
１３  現在地検出装置
１４  ＤＶＤ駆動装置
１５  メモリ
１６  通信インターフェース
１７  入力装置
１８  モニタ
【図１】
2005208744.tif 000003
【図２】
2005208744.tif 000004
【図３】
2005208744.tif 000005
【図４】
2005208744.tif 000006
【図５】
2005208744.tif 000007
【図６】
2005208744.tif 000008
【図７】
2005208744.tif 000009
【図８】
2005208744.tif 000010
【図９】
2005208744.tif 000011
【図１０】
2005208744.tif 000012
【図１１】
2005208744.tif 000013