(57)【特許請求の範囲】
【請求項１】
地理データベースを使用し、メモリを有するナビゲーションシステムのためのキャッシュ管理システムであって、
地理データのパーセルのためのキャッシュをメモリの一部として備え、上記各パーセルは上記地理データベースを形成している複数のデータレコードの一部分を構成し、上記キャッシュは少なくとも１つのバッファで形成され、上記少なくとも１つのバッファは上記パーセルのサイズよりも実質的に大きく、それにより複数のパーセルが上記バッファを占めることが可能であり、
上記メモリ内のバッファとは別の領域に位置し、上記バッファを占める各パーセル毎のヘッダー情報を含んでいるヘッダープールと、
上記メモリ内のバッファとは別の領域に位置し、パーセル識別子の探索可能な索引を含み、上記パーセル識別子の各々が上記ヘッダープール内の上記ヘッダー情報を参照するハッシュテーブルと、
を更に備え、
上記キャッシュ内に含まれるパーセルを配置する、
ことを特徴とするキャッシュ管理システム。
【請求項２】
上記パーセルの各々は上記複数のデータレコードの地理的な位置に基づいて配置された部分からなる請求項１に記載のキャッシュ管理システム。
【請求項３】
上記キャッシュとして占められる上記メモリの部分は、上記ナビゲーションシステムの初期化時に割当てられる請求項１に記載のキャッシュ管理システム。
【請求項４】
上記少なくとも１つのバッファの各ブロックは、全て同一のサイズを有している複数のページで形成されている請求項１に記載のキャッシュ管理システム。
【請求項５】
上記ページは、２キロバイトである請求項４に記載のキャッシュ管理システム。
【請求項６】
上記地理データベースは、物理的媒体上に格納されている請求項１に記載のキャッシュ管理システム。
【請求項７】
上記物理的媒体は、ＣＤ−ＲＯＭディスクである請求項６に記載のキャッシュ管理システム。
【請求項８】
上記パーセルは、ｎを１より大きい整数値として２n キロバイトのサイズに形成されている請求項１に記載のキャッシュ管理システム。
【請求項９】
上記少なくとも１つのバッファの各ブロックは、ｍを１より大きい整数値として全てが２m キロバイトのサイズを有している複数のページで形成されている請求項８に記載のキャッシュ管理システム。
【請求項１０】
上記ページサイズは、２キロバイトである請求項９に記載のキャッシュ管理システム。
【請求項１１】
上記パーセルの各々のヘッダー情報は、上記それぞれのパーセルを格納するために使用される上記キャッシュ内のサイズに対応する情報を含む請求項１に記載のキャッシュ管理システム。
【請求項１２】
上記パーセルの各々は、上記ナビゲーションシステムによる１回の読み出し動作で一時にアクセスすることができる上記地理データの最小量を表している請求項１に記載のキャッシュ管理システム。
【請求項１３】
メモリを含むナビゲーションシステムを動作させる方法であって、上記ナビゲーションシステムは、ナビゲーション機能を提供するためにナビゲーション応用プログラムを実行し、且つある地理領域内の地理特色を表すデータレコードを有する地理データベースを使用し、上記地理データベースは記憶媒体上の複数のパーセルに編成されており、上記各パーセルは複数のデータレコードを含み、上記方法は、
パーセルキャッシュとして使用するために上記メモリの一部を準備するステップと、
上記ナビゲーション機能を提供するために上記ナビゲーション応用プログラムの実行中に、上記媒体から読み出されたデータレコードのパーセルを上記パーセルキャッシュ内に格納するステップと、
上記パーセルキャッシュ内に格納されている上記各パーセルに関係するデータを、上記パーセルとは分離して上記メモリの一部分内に記憶されているヘッダー構造内に格納するステップと、
を備えていることを特徴とする方法。
【請求項１４】
データをヘッダー構造内に格納するステップの後に、上記各パーセルを識別する索引を格納するステップを更に備え、上記索引は上記パーセルから分離して記憶されているそれぞれのヘッダー構造を参照する請求項１３に記載の方法。
【請求項１５】
上記索引は、ハッシュテーブルである請求項１４に記載の方法。
【請求項１６】
メモリを含むナビゲーションシステムを動作させる方法であって、上記ナビゲーションシステムは、ナビゲーション機能を提供するためにナビゲーション応用プログラムを実行し、且つある地理領域内の地理特色を表すデータレコードを有する地理データベースを使用し、上記地理データベースは複数のデータレコードを各々が含む複数のパーセルに編成され、上記方法は、
プロセッサが、メモリ上のパーセルキャッシュ又は媒体に対して、上記ナビゲーション機能を提供するために必要なデータレコードを含んでいるパーセルを要求するステップと、
上記要求されたパーセルの識別子が待ち行列に編成されていない場合には、上記要求されたパーセルの識別子をパーセル識別子の待ち行列に編成するステップと、
を備え、
同一のパーセルに対する多重要求は、上記待ち行列内で単一のパーセル識別子にリンクされる、
ことを特徴とする方法。
【請求項１７】
上記地理データベースから上記パーセルを読み出すために、上記編成するステップの後に、上記パーセル識別子の待ち行列を媒体デバイス層へ転送するステップを更に備えている請求項１６に記載の方法。
【請求項１８】
もし、ナビゲーション機能を遂行するために未だに必要ではないデータを表すパーセルを、上記地理データベースから読み出された全てのパーセルを格納するために使用される上記メモリ内のパーセルキャッシュへ追加した時に、上記ナビゲーション機能を遂行するために未だに必要ではないデータを表すパーセルのために使用できる上記パーセルキャッシュの部分として与えられた限度を超えれば、上記ナビゲーション機能を遂行するために未だに必要ではないデータを表すパーセルに対する要求は、上記待ち行列内の上記単一のパーセル識別子の１つにリンクされない請求項１６に記載の方法。
【請求項１９】
上記転送するステップの後に、上記メモリ内にハッシュテーブルを格納するステップを更に備え、上記ハッシュテーブルは上記パーセルキャッシュ内の各パーセルの識別データを指し示している請求項１７に記載の方法。
【請求項２０】
メモリを含むナビゲーションシステムを動作させる方法であって、上記ナビゲーションシステムは、ナビゲーション機能を提供するためにナビゲーション応用プログラムを実行し、且つある地理領域内の地理特色を表すデータレコードを有する地理データベースを使用し、上記地理データベースは記憶媒体上の複数のパーセルに編成され、上記各パーセルは複数のデータレコードを含み、上記メモリの一部は上記媒体からブロックで読み出されたパーセルを格納するためのパーセルキャッシュとして使用され、上記パーセルキャッシュ内の上記各パーセルに関係するデータは上記パーセルキャッシュとして使用される上記一部から分離した上記メモリの一部分内に記憶されているヘッダー構造内に格納され、上記方法は、
上記パーセルキャッシュが既に複数のパーセルを含んでいる時には、１つのパーセルを格納するために上記パーセルキャッシュをデフラグするステップを備え、
上記デフラグするステップは、
上記ヘッダー構造によって指示されたパーセルを含むロックされているブロックをスキップするステップと、
もし使用中のブロックが再配置されることにより上記メモリの上記一部の近接するフリーブロックを完全に充填することができれば、またはもし単一の使用中のブロックが上記メモリの上記一部の２つのフリーブロックの間にあれば、上記ヘッダー構造によって使用中であることが指示されたブロックを、上記ヘッダー構造内にフリーであることが指示された近接するブロックへ移動させるステップと、
を備えていることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はナビゲーションシステムに関し、詳しく述べれば、本発明は地理データベースの使用及びアクセスを容易ならしめるナビゲーションシステムのためのメモリ管理に関する。
【０００２】
【従来の技術】
エンドユーザにいろいろなナビゲーティグン機能及び特色を提供する、コンピュータをベースとするナビゲーション応用プログラムを使用することができる。例えば、若干のナビゲーションシステムはビークルに搭載され、エンドユーザ（即ち、ビークルの運転手）に地理領域内の複数の位置の間の道路を走行するための最適ルートを提供することができる。エンドユーザからの入力、及びオプションとしてユーザの物理的位置を決定できる機器（例えば、ＧＰＳシステム）からの入力を使用して、ナビゲーション応用プログラムは地理領域内の２つの位置の間のいろいろなルートを調べ、出発点から目的地まで走行するのに最適なルートを決定することができる。次いでナビゲーション応用プログラムは、出発点から目的地までエンドユーザが走行するのに必要な運転を識別する命令の形状で、最適ルートに関する情報をエンドユーザに提供することができる。もしナビゲーションシステムが自動車に設置されているのであれば、命令は、エンドユーザがルートを走行中に供給されるオーディオ命令の形状をとることができる。若干のナビゲーション応用プログラムは、目的地までのルートを示す詳細地図、ルートに沿ういろいろな位置においてとるべき運転の型、若干の型の特色の位置、等々をコンピュータディスプレイ上に表示することができる。
【０００３】
これらの、及び他のナビゲーティング機能を提供するために、ナビゲーション応用プログラムは、地理領域内の物理的特色を表すデータを含む１つまたはそれ以上の詳細なデータベースを使用する。この／これらの詳細なデータベースは、地理領域内の道路及び交差点を表すデータを含むことができ、また交差点における転回禁止、道路の速度制限、さまざまな道路の街路名、いろいろな道路に沿う番地範囲、等々のような、表された地理領域内の道路及び交差点に関する情報を含むこともできる。
【０００４】
合理的に高レベルの機能を提供するために、比較的大きいデータベースを設けることができる。ＣＤ−ＲＯＭディスク、またはＰＣＭＣＩＡカードのような記憶媒体は、適当な機能を提供するのに充分なサイズ及び複雑さのデータベースを取扱うことができる。しかしながら、コンピュータをベースとするナビゲーションシステムは、コンピュータハードウェア資源が比較的制限されているものを含むいろいろなプラットフォーム上に設置される。例えば、ビークルに搭載の、または手持ちのナビゲーションシステムのメモリ資源は制限され、また媒体アクセスレートは比較的遅い。これらの比較的制限されているハードウェア資源は、エンドユーザが期待または要求する比較的高レベルの機能、並びに適当に高速な性能を提供することが困難である。ナビゲーションシステムの性能が低いことは望ましいだけではなく、若干の環境においては、その意図した目的にとってシステムが無用になりかねない。例えば、もしナビゲーションシステムがビークルに搭載されていれば、運転手は運転中に情報を利用するために、１−２秒程度で所望ルートに関する情報をナビゲーションシステムから得たいであろう。もしナビゲーションシステムがルートを計算するのに数秒より多くを要すれば、運転手は既にナビゲーションシステムが提供するルーティング情報が関連している点を過ぎて移動してしまっていよう。従って、適当なレベルの性能を提供するためには、ナビゲーションシステムを効率的に使用することが必要がある。
【０００５】
若干のナビゲーション応用は、より大きいメモリ資源及び他のハードウェア資源を有するコンピュータプラットフォーム上に設置することができる。これらの種類のシステムにも同じ考え方が適用されるが、スケールは異なる。より大きいメモリ及び他のハードウェア資源を有するコンピュータプラットフォームにおいては、もし使用可能な資源が効率的に使用されれば、より大きい機能さえも得ることができる。
【０００６】
従って、ナビゲーションシステムの資源を効率的に使用し、それによってシステムがより良好な性能を提供できるようにする方法及びシステムを提供することが目的である。
【０００７】
【発明の概要】
上述した及び他の目的を達成するために、及び本発明の目的によれば、地理データにアクセスするナビゲーション応用プログラムと共に使用されるシステム内のメモリ資源を管理する方法及びシステムが提供される。地理データは、複数のデータレコードからなる。複数のデータレコードはパーセル、またはグルーピングに編成され、各パーセルまたはグルーピングは複数のデータレコードの一部分を含み、各パーセルを形成している複数のデータレコードの各部分内のデータレコードは一緒にアクセスされるようになっている。複数のパーセルを格納するためのキャッシュとして、各々がナビゲーションシステムのメモリの隣接する部分を形成している１つまたはそれ以上のバッファが設けられる。メモリの隣接する部分の外側に位置する１つまたはそれ以上のデータ構造は、キャッシュ内に格納されているデータのパーセルと、パーセルが格納されているキャッシュ内の位置とを識別する。パーセルがキャッシュされているメモリの隣接する部分の外側に位置する１つまたはそれ以上のデータ構造は、パーセルキャッシュを併合（デフラグメント）させるためにも使用される。
【０００８】
【実施例】
Ｉ．ナビゲーションシステム−概要
図１に、ナビゲーションシステム１０をブロック図で示す。ナビゲーションシステム１０は、乗用車またはトラックのようなビークル１１内に設置されているが、代替実施例では、ナビゲーションシステム１０は、後述するように、ビークル外に位置することも、または他のいろいろなプラットフォームまたは環境内に実現することもできる。
【０００９】
図１に示す実施例では、ナビゲーションシステム１０はハードウェア及びソフトウェア成分の組合せである。一実施例では、ナビゲーションシステム１０はプロセッサ１２、プロセッサ１２に接続されているドライブ１４、及びナビゲーション応用ソフトウェアプログラム１８並びに構成パラメータ１９のような他の情報を格納している不揮発性メモリ記憶装置１６を含んでいる。プロセッサ１２は、日立ＳＨ１、インテル 80386、インテル 960、モトローラ 68020（または、類似の、またはより大きいアドレス空間を有する他のプロセッサ）のようなフラットアドレス空間を使用する 32 ビットプロセッサのような、ナビゲーションシステム内に使用されるどのような型であることもできる。これら以外の型のプロセッサ、及び将来開発されるかも知れないプロセッサも適当であり得る。
【００１０】
ナビゲーションシステム１０は、測位システム２４を含むこともできる。測位システム２４は、当分野においては公知の、ＧＰＳ型技術、推測型システム、またはこれらの組合せ、または他のシステムを利用することができる。測位システム２４は、ビークルの走行距離、速度、方向、等々を測定する適当な感知デバイス２５を含むことができる。測位システム２４は、当分野においては公知の手法でＧＰＳ信号を入手する適切な技術を含むこともできる。測位システム２４は、信号２６をプロセッサ１２へ出力する。プロセッサ１２上で走るナビゲーション応用ソフトウェア１８はこの信号２６を使用して、ナビゲーションシステム１０の位置、方向、速度、等々を決定することができる。
【００１１】
ナビゲーションシステム１０は、ユーザインタフェース３１も含んでいる。ユーザインタフェース３１は、エンドユーザがナビゲーションシステム内へ情報を入力できるようにする適切な機器を含む。この入力情報は、ナビゲーションシステムのナビゲーション特色の使用の要求を含む。例えば、入力情報は、所望の目的地までのルートに関する要求を含むことができる。入力情報は、構成情報のような他の種類の情報を含むこともできる。ナビゲーションシステム内へ情報を入力するために使用される機器は、キーパッド、キーボード、マイクロホン、等々、並びに音声認識プログラムのような適切なソフトウェアを含むことができる。ユーザインタフェース３１は、エンドユーザへ情報を戻す適当な機器も含む。この機器は、ディスプレイ２７、スピーカ２９、または他の手段を含むことができる。
【００１２】
ナビゲーションシステム１０は、記憶媒体３２上に格納されている地図データベース４０を使用する。ナビゲーションシステムが地図データベース４０を読み出して使用することができるように、記憶媒体３２はドライブ１４内に設置されている。記憶媒体３２は取り外し可能であり、置換可能であるので、ビークルが走行している地理領域のための適切な地図データベースを有する記憶媒体を使用することができる。更に、記憶媒体３２は置換可能であるので、その上の地図データベース４０は容易に更新することができる。一実施例では、地理データはカリフォルニア州サニービルの Navigation Technologiesから出版されているものであることができる。
【００１３】
一実施例においては、記憶媒体３２はＣＤ−ＲＯＭディスクである。代替実施例においては、記憶媒体３２はＰＣＭＣＩＡカードであることができ、この場合ドライブ１４はＰＣＭＣＩＡスロットに置換される。固定またはハードディスク、ＤＶＤ（ディジタルビデオディスク）、または現在市販されている他の記憶媒体、並びに将来開発されるかも知れない記憶媒体を含む他のさまざまな記憶媒体を使用することができる。記憶媒体３２及び地理データベース４０は、物理的にナビゲーションシステムの位置に設ける必要はない。代替実施例においては、地理データベース４０の若干、または全てを格納している記憶媒体３２はナビゲーションシステムの残余から離して配置することができ、地理データの一部は必要に応じて通信リンクを介して供給される。
【００１４】
図２を参照する。ナビゲーション応用１８は、個々のナビゲーション機能（または、サブプログラム）２８を提供するソフトウェアプログラミングを含む。これらのナビゲーション機能２８は、例えば、ルート計算機能３３、地図表示機能３４、ルート案内機能３５（所望の目的地へ到達するための詳細な指令が供給される）を含む。ナビゲーション応用プログラム１８は、これらの他に、または代替として、ビークル位置決め機能（例えば、マップマッチング）のような他の機能またはサブプログラム３６を含むことができる。これらのナビゲーション応用機能２８は、ナビゲーション応用プログラム１８内に分離したサブプログラムまたは応用として表されているが、これらの機能２８は組合せたり、またはそれ以外に設けることもできる。ナビゲーション応用プログラム１８は、ユーザインタフェース機器３１（図１）を支援するユーザインタフェースプログラミング３７をも含む。例えば、このユーザインタフェースプログラミング３７は、ユーザインタフェース３１、メニューの表示、プロンプト、等々を介してエンドユーザへの情報の図形表示を提供することができる。ナビゲーション応用１８は、オペレーティングシステムを含むこともできる。ナビゲーション応用１８は、地理データベース４０へアクセスする特定機能３９をも含むことができる。好ましい実施例では、これらの機能３９はいろいろなナビゲーション応用２８と地理データベース４０との間、より詳しく言えば、ナビゲーション機能２８とオペレーティングシステム３８との間に位置している。これらの機能３９は、ナビゲーティング機能２８の間で地理データベース４０への共用アクセスを容易にするキャッシュ管理機能５９及び待ち行列機能４０４のようなメモリ管理機能を含む。
II. 地理データベース
ａ．概要。  地理データ４０は、１つまたはそれ以上のコンピュータ可読データファイル、またはデータベースの形状で媒体３２上に格納されている。地理データ４０は、特定の地理領域内の、またはそれに関係付けられた道路及び交差点の位置に関する情報を含むことも、または、一方通行道路、転回禁止のような道路及び交差点の属性に関する情報、または街路番地、ホテル、レストラン、博物館、スタジアム、オフィス、自動車販売会社、自動車修理工場、等のような他の情報を含むことができる。地理データベースのカバレッジ領域は、シカゴとその郊外、ニューヨークとその郊外、ロスアンジェルスとその郊外のような大都市圏を含むことができ、または代替として、領域はカリフォルニアのような州（ステート）全体、合衆国のような国全体、またはドイツ、フランス、及びイタリアもしくはこれらの組合せのような１つの国より多くの国を含むことができる。記憶媒体上には１つの領域より多くの領域を格納することができる。
【００１５】
記憶媒体３２上の地理データ４０を使用する時に、ナビゲーション応用プログラム１８内のナビゲーション機能２８の動作及び性能に影響を与え得る幾つかのファクタが存在する。合理的に高レベルの機能を提供するために、比較的大きいデータベースを設けることができる。ＣＤ−ＲＯＭディスク、またはＰＣＭＣＩＡカードのような記憶媒体は、適当な機能を提供するのに充分なサイズ及び複雑さのデータベースを取扱うことができる。しかしながら、これらの型の媒体のアクセシングは比較的遅い。ナビゲーションシステムはビークルに搭載することも、手持ちであることもできるので、ナビゲーションシステムのハードウェア資源は制限され得る。これらのナビゲーションシステムのメモリ資源が制限されているために、ナビゲーション応用プログラムが使用するためには、地理ディスクをＣＤ−ＲＯＭのような記憶媒体からナビゲーションシステムのメモリ内に必要に応じてロードする必要がある。不幸にも、前述したように、これらの型のシステムの媒体アクセスも比較的遅いことがあり得る。
【００１６】
ナビゲーションシステム資源が制限されていることによって賦課される制約に対処するために、地理データベース、またはデータベース内のデータを特定の手法で編成し、構成し、または配列することによってナビゲーションシステムの性能を改善するための技術が考案、または実現されている。ナビゲーションシステムは既知の機能を遂行するために、地理データを若干の既知の、そして予測できるような手法で使用するので、地理データはナビゲーションシステムによるこれらの既知の手法で使用するのを容易にするように編成し、構成し、または配列することができる。
【００１７】
ナビゲーション応用プログラムは、ネットワークを通してアクセス可能なパーソナルコンピュータまたは地理データベースサーバのような比較的多くのメモリ資源及び高速Ｉ／Ｏを有するコンピュータプラットフォーム上で走らせることもできる。これらのプラットフォームはより多くの、そしてより高速の資源を有することはできるが、それでも地理データベースの効率的な使用に関する考え方はスケールは異なるとしても適用される。これらの型のプラットフォームを用いると、もし地理データベースを効率的に形成し、使用することができれば、より多くの機能さえも提供することができる。
【００１８】
ｂ．パーセル化。  ナビゲーションシステムによる地理データの使用を容易にするために使用できる技術の中には、パーセル化が含まれる。ナビゲーション応用プログラムが走っているナビゲーションシステムのメモリ資源が制限されているために、所与の地理領域全体のための全てのデータレコードをナビゲーションシステムのメモリ内に同時にロードできないものとすれば、所望の機能を遂行するのに必要なデータだけをメモリ内へロードすることが望ましい。これを達成するために、地理データベース３０内のデータベースは、ナビゲーション機能を遂行するために媒体へアクセスし、媒体から読み出すのに必要な時間の長さを最短にするように編成される。このようにするために、データはパーセルに編成される。データベースがパーセル化される場合、一緒になって地理データを構成する複数のデータレコードが分離したグループ、即ちパーセルにグループ化される。データのパーセルは、パーセル内の全てのデータが一緒に、媒体から同時にアクセスされるように確立される。これは、１回のディスクアクセスでアクセスできるデータの量に関係するが、他のあるファクタに関係付けることもできる。ＣＤ−ＲＯＭディスクのような若干の型の媒体の場合には、パーセルは 16 キロバイトのデータ量であるように確立することができる。（１Ｋ、２Ｋ、４Ｋ、８Ｋ、32Ｋ等を含む他のデータサイズも使用可能である。地理データベースの部分は一般に２n キロバイトのサイズで形成される。但し、ｎは１より大きい整数値である。）
パーセル化と共に、地理データの使用を容易にするために、それらを編成できる別の方法は、データを空間的に編成することである。地理データが空間的に編成されていると、地理領域内で互いに物理的に近接している特色は、データベース内でも物理的に（または、論理的に）互いに近接しているデータレコードによって表される。地理データは、これらの両技術を利用するために、パーセル化し、空間的に編成することができる。
【００１９】
データをパーセルに形成する目的で、データは先ず、それらにアクセスするナビゲーション機能２８に基づいて異なる型に空間的に編成される。従って、ナビゲーション機能２８の若干、または全ては、地理データの分離した集まりであることができる。分離した各集まりは、それぞれの機能を遂行するために必要なデータの本質的な部分を含むが、その機能を遂行するために不要な部分は省かれる。従って、地理データベース内には、１つまたはそれ以上のナビゲーション機能２８に関連付けられたルーティング、地図作成（地図表示）、運転（ルート案内）、関心点、名前、等々のような分離した型のデータが存在し得る。
【００２０】
ナビゲーション機能２８によるデータの使用を容易ならしめるために、これらの種類のデータの若干は空間的にパーセル化することができる。空間的にパーセル化されたデータは、地理的に近接する特色を表すデータが、データベース４０及び／または媒体３２内で論理的に、及び／または物理的に近接して位置するように配列される。若干のナビゲーション応用機能の場合には、それらの関連データを空間的にパーセル化すると、それらを使用する時に密に関係している地理データを媒体からより迅速に読み出したり、関連地理データをメモリ内にロードすることができる。この種類の編成は、記憶媒体３２のアクセスを最小にし、これらのナビゲーション機能の動作をスピードアップさせることができる。ルーティング、地図作成、及び関心点データは、空間的に編成できる種類のデータに含まれる。
【００２１】
地理データを空間的にパーセル化するために使用できる多くの異なる手順が存在している。例えば、簡単なパーセル化方法では、データが複数のパーセル、またはグルーピングに分離される。各パーセル内のデータは、一緒になって地理領域上に規則的な矩形格子を形成する複数の規則的なサイズの矩形の分離した１つの中に含まれる特色を表す。別の空間パーセル化方法は、パーセルサイズが最大しきい値以下になるまで、領域の部分を包含する矩形を等分して行くことによって各矩形を形成するように、データを矩形領域内に含まれるパーセルに分離する。更に、パーセル化手順が 1996 年10月25日付同時出願第 08/740,295 号に開示され、その全文が参照として本明細書に採り入れられており、またパーセル化手順が 1997 年９月５日付同時出願第 08/935,809 号に開示され、その全文が参照として本明細書に採り入れられている。本願に適用できる更に他のパーセル化方法は、米国特許第 4,888,698号及び第 4,937,572号に開示されている。
【００２２】
空間的に編成されたデータのパーセル化を、図３及び４を参照して説明する。図３は地理領域１１２の地図１１１を示している。複数の位置１１４（ドットまたは点によって表されている）が地図１１１上に位置するように示されている。各位置１１４は地理領域１１２内の場所または点を表しており、この場所または点には、図１及び２の地理データベース４０内に含まれる情報に関する特色が位置している。例えば、位置１１４は、地理データベース４０内のデータによって表されている、道路セグメントの端点、道路セグメントに沿う点、関心点（ホテル、市民会館等）等々の物理的位置に対応させることができる。これらの各位置１１４は個々の物理的位置（緯度、経度、及びオプションとして絶対、または相対高度）を有し、各位置１１４はその二次元（または、三次元）地理座標（即ち、緯度、経度、及びオプションとして高度）によって個々に識別することができる。
【００２３】
図３では、地図１１１によって表されている地理領域１１２に格子１１７がオーバーレイされている。格子１１７は、地理領域１１２を複数の矩形領域１１９に分割している。格子１１７の格子線は、矩形領域１１９の境界を表す。境界の位置は、使用されるパーセル化手順に依存することができる。一般的に言えば、空間パーセル化にどのような手順を使用しても、各矩形領域１１９内に含まれる特色を表す特定のデータの型のデータレコードは、分離したデータのパーセル内に一緒にグループ化される。従って、空間的に編成されてデータの各パーセル１２０（図４）は、複数の矩形１１９の分離した１つ（図３に示すような）内に含まれる地理特色を表す１つまたはそれ以上のデータレコードを含む。
【００２４】
図４に示すように、パーセル１２０は、各パーセル１２０内のデータが論理的に、及び／または物理的に一緒にグループ化されてデータベース４０を形成するように格納される。パーセルは、ナビゲーションシステムによって媒体から同時にアクセスされるデータベースレコードの量を表しているから、データのパーセルがアクセスされた時、そのデータレコードの全てが同時にナビゲーションシステムのメモリ内に読み込まれる。図３の地図１１１について言えば、これは各矩形１１９内に含まれる空間的に編成されたデータの型の全てのデータレコードがグループとして一緒にアクセスされることを意味している。若干の種類のナビゲーション機能の場合には、地理領域内で互いに物理的に密である特色を表している全てのデータレコードを同時にメモリ内に有することが望ましいことは理解できよう。
【００２５】
パーセル１２０がこれらのデータの型のために形成される際に、パーセルは順序付けされる。いろいろな型の順序付けを使用することができる。一般的に言えば、データの探索を最小にするような手法でパーセルを順序付けすることが好ましい。空間的に編成されたパーセルを順序付けする１方法は、各データの型内のｋｄ木索引から深さ優先順序付けを使用することである。これはペアノ( Peano ) キー順序付けに類似した順序付けである。パーセルは、この近似ペアノキー順序でディスク（即ち、図１及び２の媒体３２）上に格納することができる。ｋｄ木のような１つまたはそれ以上の索引を使用して、空間的にパーセルにアクセスすることとができる。この索引は、ナビゲーションシステム内のプログラムが始めに現在のビークル位置に対応する地図データを探知する時のように、任意位置の初期探知にとって有用である。パーセル１２０を順序付した後に、各パーセルに独特のパーセル識別子（例えば、「パーセルＩＤ」）を割当てることもできる。パーセルＩＤは、パーセル及び／または媒体上のその位置を識別するために使用することができる。
【００２６】
前述したように、若干の種類のデータは、空間的に編成されていない（即ち、空間的に編成されていないデータの各パーセルは、必ずしも図３の矩形領域１１９の何れにも対応しない）。例えば、街路名を表すデータは、空間的にではなくアルファベット順に編成することができる。国、州、市、等々のような行政または政治的エンティティを表すデータは、空間的に編成されない他の種類のデータである。例えば、行政または政治的エンティティを表すデータは、行政階層によって編成することができる。一実施例では、これらの空間的に編成されない型のデータも、同じようにパーセル化される。
【００２７】
III ．  地理データベースのアクセス方法
ナビゲーション応用１８の分離したいろいろなナビゲーション機能２８は、有用なナビゲーション特色をナビゲーションシステム１０のエンドユーザに提供するために、記憶媒体３２上に格納されている地理データベース４０内のデータを使用する。前述したように、ナビゲーション応用１８は、地理データベース４０にアクセスする機能３９を含んでいる。これらのアクセス機能３９は、いろいろなナビゲーション応用２８及び地理データベース４０と共に動作する。詳しく述べると、これらの機能３９は、ナビゲーション機能２８とオペレーティングシステム３８との間で動作する。媒体３２上の地理データベース４０内のデータは、いろいろなナビゲーション機能がそれらを使用し易いように、媒体３２上に圧縮され、配列され、編成され、パーセル化され、索引付けされている。アクセス機能３９は、ナビゲーション機能２８が使用するデータを戻すために、記憶媒体３２上の地理データベース４０の編成及び配列を取扱う。
【００２８】
アクセス機能３９の中には照会変換機能５５が含まれている。この機能５５は、ナビゲーション機能からのデータに関する照会を、要求されたデータを含む媒体上のパーセルの識別に変換するために使用することができる。この照会変換機能５５は、データ探索機能５６を使用することができる。これらのデータ探索機能５６は、要求されたデータを探索するために、いろいろな索引（これらの索引の若干は媒体上に格納することができる）、並びに媒体上の地理データのファイル構造に関する情報を使用することができる。データ探索機能５６は、所望のデータのパーセルが媒体上に位置しているアドレス位置、またはファイルオフセットを決定することができる。データ探索機能５６は、パーセル内の所望のデータの位置を決定することもできる。ナビゲーション応用は、データ変換機能５７を更に含む。データ変換機能５７は、データを圧縮解除し、ナビゲーティング機能２８がデータを容易に使用できるフォーマットに変換するために設けられている。データ変換機能は、地理データベース４０の異なるバージョンまたはリリースから変換するためにも、並びに地理データベースを更新するためにも設けることができる。アクセス機能３９は、ある最小資源がナビゲーションシステムによって提供されることを条件に、地理データベース４０を使用するナビゲーションシステムに受容できるレベルの性能をも与える。更に、アクセス機能３９は、より向上した性能さえも与えるために、最小より多い付加的な資源の効率的な使用をも提供する。一実施例では、アクセス機能３９は（以下に説明するパーセルキャッシュメモリ以外に）ほぼ 128Ｋのメモリを使用するが、代替実施例では、それより小さいメモリでさえも（ 64 Ｋ、または 16 Ｋでさえも）使用することができる。
【００２９】
別の代替実施例では、地理データへの全てのアクセス機能は、この目的のために分離した機能を提供する代わりに、それぞれのナビゲーション機能２８によって実現することができる。この代替では、これらのアクセス機能の動作は類似していよう。
【００３０】
ＩＶ．パーセルキャッシュ
ａ．概要。  ナビゲーションシステムの性能を改善する１つの方法は、メモリ内にパーセルキャッシュを実現することである。図２を参照する。ナビゲーションシステムの動作中、いろいろなナビゲーティング機能２８は、機能を遂行するために必要な地理データを識別する照会をフォーミュレートする。媒体３２上のどのパーセル１２０（図４）が、ナビゲーティング機能２８が必要とするデータを含んでいるかを識別するために、データアクセス機能３９はこれらの照会を使用する。これらのパーセル１２０が識別されると、それらはデータアクセス機能３９によってアクセスされ、読み出される。不幸にも、前述したように、データのために媒体へのアクセスは比較的遅い。データのパーセルが媒体３２から読み出されると、照会を満足させるために、パーセル内のデータの若干、または全てを圧縮解除し、ナビゲーション機能２８へ供給しなければならない。
【００３１】
ナビゲーティング機能２８からのデータに関する若干の照会について言えば、１つより多くのパーセル内に含まれるデータに対する要望が存在し得る。更に、ナビゲーティング機能２８からのデータに関する若干の照会について言えば、先にアクセスしたパーセルからのデータに対する要望が存在し得る。先にアクセスしたパーセルからのデータに対する要望は、若干のナビゲーション機能がデータに空間的にアクセスする場合に生じ得る。例えばルート計算機能３３が遂行されている時に、どの経路が最適であるかを決定するために、地理領域内の道路交差点の位置から複数の可能経路が探査される。これらの複数の可能経路の探査は、その交差点から比較的近くに位置する特色を調べ、次にその交差点から比較的離れて位置する特色を調べ、次いでその交差点から比較的近くに位置する特色を再度調べることを要求し得る。これらの特色を表すデータは空間的に編成することができるから、互いに近接する特色を表すデータを再度調べることは、先にアクセスしたものと同一のパーセルにアクセスすることが必要になり得る。別の例として、空間的に編成されたデータのパーセルを探知するのに必要なグローバルｋｄ木パーセルのような、異なるデータベースレコードを探知するために索引パーセルを繰り返して必要とすることがあり得る。パーセルを、１回より多く識別し、探知し、アクセスし、そして読み出さなければならなくなる度に、この時間消費が重ねられて行く。これらの環境の下では、もしパーセルを、１回より多く媒体上で探知し、アクセスし、そして読み出さなければならないのであれば、かなりの時間が節約でき、それによってシステムの性能を改善することができる。
【００３２】
ナビゲーションシステムの性能を改善すべく、媒体からアクセスされ、読み出された地理データの複数のパーセルを格納するために、ナビゲーションシステムのメモリ内に特定的にキャッシュを設ける。図５−７にパーセルキャッシュのいろいろな面を示す。地理データのパーセルをパーセルキャッシュ内に格納することによって、複数の地理パーセルをメモリ内に維持し、何時でも使用できるようにしてナビゲーティング機能２８を支援する。パーセルキャッシュは、先に調べたデータを再び調べることが必要なナビゲーション機能を収容する。若干のナビゲーション機能は、比較的短時間の間に１回より多く同一のパーセルにアクセスする必要があるので、パーセルをメモリ内に格納して何時でも使用できるようにしておくと、再度媒体からのパーセルにアクセスするのに伴う比較的大きい遅れが回避される。パーセルキャッシュは、ナビゲーション機能が直ぐに必要とすることが予測される地理データのパーセルを格納するために使用することができる。また、パーセルキャッシュは、ナビゲーション機能２８の１つ、または別の機能が破棄すべきではないことを指示した最新使用済みパーセルを含むために使用することもできる。
【００３３】
一実施例では、パーセルキャッシュは、媒体から読み出された全てのデータのパーセルを含むために使用される。もしナビゲーション機能２８からの照会を満足させるのに必要なパーセルがパーセルキャッシュ内に存在しなければ、そのパーセルは媒体からパーセルキャッシュ内へ読み込まれ、次いでデータをナビゲーション機能２８へ送るためにそれはアクセス機能３９によって使用され、照会を満足させる。図２を参照する。パーセルキャッシュの形成及び動作は、キャッシュ管理者機能５９によって遂行させることができる。キャッシュ管理者機能５９は、データアクセス機能３９の中に含ませることができる。
【００３４】
図５は、ナビゲーションシステム１０におけるメモリの使用を示す図である。ＲＡＭ２０の部分２０２はナビゲーション機能２８が使用し、別の部分２０４はアクセス機能３９が使用する。これらの部分２０２及び２０４は、ナビゲーションシステム内に設けられているメモリの合計量に基づいて、ナビゲーションシステムの初期化時に決定することができる。更に、メモリ２０の部分２０６は、後述するようにパーセルキャッシュ２０７のために使用される。メモリ２０の更に別の部分２０８は再割当て可能である。この再割当て可能な部分２０８の若干、または全ては、ナビゲーションシステムの要望に基づいてナビゲーションシステムのランタイム中に、ナビゲーション機能２８またはアクセス機能２９、またはパーセルキャッシュ２０７によって交互に使用することができる。
【００３５】
パーセルキャッシュ２０７は、１つまたはそれ以上のバッファ２２０を含む。各バッファ２２０は、ナビゲーションシステムのメモリ２０の一部分を表している。図６は、図５のパーセルキャッシュ２０７を形成しているバッファ２２０の１つを示す図である。キャッシュ２０７には３つの基本的ユニット、即ち、ページ２２２、ブロック２２４、及びバッファ２２０が存在している。これらのアイテムの関係を図６に示す。図６に示すバッファに類似する複数のバッファ２２０が一緒に連鎖されて存在することができる。１つまたはそれ以上のブロック２２４が各バッファ２２０内に含まれるが、実際の数はキャッシュの使用に依存する。各ブロック２２４は、１つまたはそれ以上のページ２２２で形成されている。各ブロックはメモリの隣接範囲であり、このメモリの隣接範囲はパーセルを格納しているか、または最大隣接範囲のフリーメモリの何れかである。ページ２２２のサイズは固定されており、各パーセルはページサイズの倍数であるサイズを有している。ページサイズは、例えばＣＤ−ＲＯＭの場合の２Ｋのように、媒体の最小アドレス可能な量に選択することができる。ブロック２２４は２つの状態、即ちフリーか、または使用中の一方にある。使用中のブロックは、パーセルデータを含んでいるか、または現在その中へ読み込み中である。
【００３６】
ｂ．パーセルキャッシュのサイズ。  パーセルキャッシュのサイズは、幾つかのファクタに依存する。パーセルキャッシュのサイズに影響を与える１つのファクタは、パーセルの１つまたは複数のサイズに依存する。パーセルのサイズに対するパーセルキャッシュのサイズは、パーセルキャッシュ内にどれ程多くのパーセルを含むことができるかを決定する。前述したように、若干の実施例では、パーセルは例えば２Ｋ、４Ｋ、８Ｋ、16Ｋ、32Ｋ、等々のような正規サイズで媒体上に格納されている。従って、キャッシュのサイズは、格納できるこれらの各サイズの数、またはパーセルを限定する。例えば、384 Ｋパーセルキャッシュは、各々が 16 Ｋのサイズのパーセルを最大 24 格納することができる。大きいサイズのパーセルであれば格納できるパーセル数は相応に少なくなり、サイズが小さければ格納できるパーセルの数は相応に多くなる。一実施例では、媒体３２上の地理データベース４０は１つより多くのサイズを含んでいる。若干のパーセルは 32 Ｋであり、他のパーセルは 16 Ｋであり、他のパーセルは８Ｋであり、等々である。従って、一実施例では、物理媒体３２から読み出された変化するサイズのパーセルを保持するために、パーセルキャッシュ２０７を使用する。
【００３７】
パーセルキャッシュのサイズに影響を及ぼす別のファクタは、ナビゲーションシステムの合計使用可能メモリ資源である。メモリ資源が制限されているナビゲーションシステムは、パーセルキャッシュのために比較的小さい部分しか提供できない。より大きいメモリ資源を有するナビゲーションシステムは、パーセルキャッシュのために比較的大きい部分を提供することができる。
【００３８】
パーセルキャッシュのために設けられるメモリの量に影響する別のファクタは、パーセルに関する要求を発したナビゲーション機能内の１つまたは複数の探索アルゴリズムに関係している。先に調べたデータを異なる方法で再び調べることは、異なる探索アルゴリズムで実現することができる。例えば、若干の探索アルゴリズムは、先に検討した多くのパーセルを再びより多く調べることを要求するのに対して、他の探索アルゴリズムは、先に検討した僅かなパーセルを再び調べるだけでよい。更に、若干の探索アルゴリズムは、長い時間にわたって先に検討したパーセルを再び調べるように実現することができる。即ち、それらは始めに比較的多くのパーセルが調べられたパーセルに戻って、それらを更に再び調べることができる。
【００３９】
パーセルキャッシュのために設けられるメモリの量に影響する更に別のファクタは、若干の探索アルゴリズムが「プリキャッシュ」探索技術を実現していることである。「プリキャッシュする」とは、ナビゲーション応用機能が実際にパーセル内のデータを必要とする前に、パーセルキャッシュ内にパーセルを格納することを言う。プリキャッシュするために、ナビゲーション機能は、ある動作パターンを検出し、実際に必要とする前にどのデータが必要になるであろうかを予測するアルゴリズムを実現する。この検出したパターンに基づいて、ナビゲーション機能２８の１つは若干のデータにアクセスすることを要求し、それによってそれらのデータを含むパーセルをパーセルキャッシュに格納させ、何時でも使用できるようにする。
【００４０】
パーセルキャッシュのために使用されるメモリの量に影響する更に別のファクタは、パーセルキャッシュ２０７に割当てられるメモリと、ナビゲーション応用機能２８に割当てられるメモリとの相対サイズである。パーセルキャッシュ２０７にメモリを比較的大きく割当てても、ナビゲーション応用機能２８のために使用可能なメモリの量を考えた場合、またはその逆の場合、必ずしもナビゲーションシステムの性能の改善はもたらされない。
【００４１】
更に別のファクタは、小さいパーセルキャッシュを用いると、パーセルを圧縮された形状でキャッシュ内に格納し、パーセルからのデータが必要になる度毎にパーセルを圧縮解除する必要があり得る。大きいパーセルキャッシュを用いると、パーセルは圧縮解除された形状でキャッシュ内に格納することができる。
【００４２】
上述した諸ファクタを斟酌すると、パーセルキャッシュ２０７のために合理的なサイズは 384Ｋであることが分かった。代替実施例では、パーセルキャッシュは 384Ｋよりも小さくて差し支えない。例えば、一つの代替実施例では、パーセルキャッシュのために使用されるメモリの量は 256Ｋ（ 16 Ｋパーセルを最大 16 保持する）であることも、または 128Ｋであることさえもできる。384 Ｋよりも大きいパーセルキャッシュを設けることもできる。一般的に言えば、より大きいパーセルキャッシュは、より大きい性能便益をもたらす。パーセルキャッシュのために使用することができるメモリの量に関しては固定された上限はないが、パーセルキャッシュのために割当てられるメモリの量がナビゲーション応用機能２８のメモリ要求を制約すべきではない。例えば、１Ｍ（ほぼ 16 Ｋパーセルを 64 保持する）の比較的大きいキャッシュ、または数ギガバイトでさえも設けることができる。
【００４３】
ｃ．パーセルヘッダープール及びハッシュテーブル。  パーセルキャッシュ内にパーセルを格納すると、資源が制限されているナビゲーションシステム、並びにより大きい資源を有するナビゲーションシステムの両者にとって便益を得ることができる。しかしながら、パーセルキャッシュを効率的に使用すると、ナビゲーションシステムの性能をさらに向上させることが可能である。例えば、前述したように、パーセルは例えば８Ｋ、16Ｋ、32Ｋ等のような異なるサイズのパーセルであることができる。従って、所与のサイズのパーセルキャッシュが与えられた場合、そのキャッシュを異なるサイズのパーセルに割当てると、格納できるパーセルの数に影響し得る。別のファクタは、キャッシュ内のパーセルが絶えず変化することである。従って、もし 32 Ｋパーセルのためのメモリ空間が必要であり、２つの隣接していない 16 Ｋの空間が使用可能であれば、これらの使用可能な空間を合体させて 32 Ｋパーセルに使用させる手段が必要である。更に別のファクタは、キャッシュ内のパーセルを探索することに関係している。比較的大きい（例えば、１Ｍ）パーセルキャッシュにおいては、連続的に変化する数ダースのパーセルが存在し得る。所望のパーセルを迅速に探索することは、システムの性能の改善を援助する。
【００４４】
所望のパーセルを迅速に探索し、パーセルキャッシュを効率的に管理するために、キャッシュ内の各パーセルに関する情報を識別し、パーセルの索引を与える少なくとも１つのデータ構造が設けられている。多重タスキングまたは多重プロセッサシステムにおいては一般的であるように、例えばミューテックス( mutex ) ロッキングによって１つまたは複数のデータ構造の完全性を維持しなければならないことに注目されたい。一実施例では、２種類のデータ構造が使用されている。複数の第１のデータ構造は、キャッシュ内の各パーセルに関する情報を含むために使用され、第２のデータ構造は第１のデータ構造と組合せてパーセルを指し示し、探索するために使用される。いろいろな種類のデータ構造をこれらの目的のために使用することができる。図７及び８に示すように、この実施例では、複数のパーセルヘッダー２６４がヘッダープール２６２から割当てられ、バッファ内の各パーセルに関する情報を保持するために使用されている。これらのパーセルヘッダー２６４は、ハッシュテーブル２６６と組合せて使用される。
【００４５】
図７に、パーセルキャッシュ２０７のために使用されるメモリのバッファ２２０を示す。メモリのバッファ２２０は、メモリの隣接する部分（即ち、隣接するアドレス範囲）を表している。一実施例では、バッファ２２０のサイズは 384Ｋである。キャッシュ管理者機能５９（図２）は、ヘッダープール２６２として使用するための比較的小さいバッファ２２０の部分２６０を割当てる。ヘッダープール２６２は複数のパーセルヘッダー２６４からなり、各パーセルヘッダーはパーセルキャッシュ２０７のバッファ２２０（図７）内の分離したパーセルに関連付けられている。一実施例では、複数のパーセルヘッダーは割当て構造のアレイとして編成されている。
【００４６】
ヘッダープール２６２のために使用されるメモリの部分２６０は、それが位置しているバッファ２２０の合計サイズの関数として決定することができる。ヘッダープール２６０のために使用されるメモリの部分のサイズを決定する一方法は、小さいサイズのパーセルを保持するには小さ過ぎるバッファの残余のサイズを決定することである。例えば、500 Ｋのバッファは 31 の 16 Ｋパーセルを保持することができ、４Ｋが残される。残された４Ｋを、ヘッダープールとして使用することができる。
【００４７】
ヘッダープール２６２のために使用されるメモリの部分２６０のサイズを決定する別の方法は、各パーセルヘッダー毎に必要なバイトの数を推定し、次いでバッファ２２０内に格納することができるパーセルの最大数を、この数に乗ずることである。例えば、一実施例では、各パーセル毎のヘッダーは約 40 バイトを必要とすることができる。
【００４８】
一実施例では、ヘッダープール２６２のために使用されるメモリの部分２６０の最小サイズは、ほぼ４Ｋである。この４Ｋサイズは、約 384Ｋのパーセルキャッシュサイズに基づいている。もし異なるサイズのパーセルキャッシュが設けられれば、ヘッダープールのために要求されるメモリの部分２６０を相応に変化させることができる。例えば、もし１Ｍのパーセルキャッシュが使用されれば、メモリのより大きい部分がヘッダープールのために要求され得る。
【００４９】
パーセルキャッシュ２０７内に含まれるパーセルは絶えず変化し得るから、必要に応じてパーセルヘッダー２６４がヘッダープール２６２から割当てられ、パーセルキャッシュ内の各パーセルに関連付けられる。後述するように、各パーセルに関連付けられたパーセルヘッダー２６４内の情報の若干は、そのパーセルがパーセルキャッシュ内にある間に変化し得る。キャッシュ管理者機能５９は、パーセルがパーセルキャッシュ内に格納されると、ヘッダープール内のヘッダーの形成のためのデータを格納する。またキャッシュ管理者機能５９は、パーセルが移動、アンロック、フィード、等々されるとパーセルヘッダー内のデータの変更も行う。
【００５０】
図８に示すように、ハッシュテーブル２６６は、ヘッダープール２６２内のパーセルヘッダー２６４に関連付けられている。ハッシュテーブル２６６は、あるパーセルがパーセルキャッシュ内にあるか否かを迅速に決定するために使用される。ハッシュテーブル２６６は、パーセルキャッシュ２０７内に含まれる全てのパーセルのバッファＩＤ（パーセルＩＤに関係付けられている）の探索可能な索引を維持している。ハッシュテーブル２６６は、各バッファＩＤと、ヘッダープール２６２内の同一バッファＩＤを有するパーセルのパーセルヘッダーの二重にリンクされたリスト内の最初のパーセルに関連付けられているパーセルヘッダー２６４を指し示すポインタ２６８とを関連付ける。ハッシュテーブル２６６を使用すると、アクセス機能３９（図２）は、必要なパーセルが既にパーセルキャッシュ内にあるのか、または媒体３２から読み出さなければならないのかを迅速に決定することができる。ハッシュテーブル２６６は、パーセルキャッシュ内のパーセルの存在及び位置を迅速に識別することができるので、パーセルキャッシュを直線的に探索する必要はない。
【００５１】
一実施例においては、ハッシュテーブル２６６内に維持されているポインタ２６８は、パーセルキャッシュ２０７のために使用される全てのバッファ２２０（図６）内のパーセルを探索するポインタを含んでいる。従って、ハッシュテーブル２６６は必ずしも、パーセル、またはそれらを指し示すパーセルヘッダーと同一のバッファ２２０内に位置する必要はない。一実施例では、ハッシュテーブル２６６はバッファ２２０の１つの一部分の中に位置している。代替として、ハッシュテーブル２６６はアクセス機能３９のために使用されるメモリ２０（図５）の部分２０４内に位置することができる。一実施例では、ハッシュテーブルのためのメモリは、第１のバッファの末尾を利用する。好ましい実施例では、最初のバッファだけがハッシュテーブルを含んでいることに注目されたい。それは、ハッシュテーブルはランタイムを通して存続するが、初期化の後に割当てられるバッファは存続しないからである。
【００５２】
ハッシュテーブル２６６は初期化中に割当てられる。ハッシュテーブル２６６のサイズは、パーセルキャッシュ２０７の目的のために設けられるメモリ２０６（図５）に依存して変化する。一実施例では、それは以下のようにして計算される。キャッシュサイズを、パーセルヘッダーのサイズ＋ページのサイズによって除算する。キャッシュ内に残された空間の量を見出すために、得られた整数値に同じ定数を乗算する。もし残された空間が 64 Ｋハッシュバケットで除算したバッファキャッシュサイズに等しい値を受け入れれば、残された空間全体をハッシュテーブルのために使用する。そうでなければ、ハッシュテーブルのために付加的なページを使用する。ハッシュバケットの数は、それが偶数ではないように処理する。理想的には、この数は素数であるが、奇数でも充分である。
【００５３】
パーセルキャッシュ内の各パーセルは、ロックされているか、またはロックされていないの何れかの状態を有している。もしパーセルがロックされていれば、それは使用中である。もしパーセルがロックされていなければ（即ち「アンロック」であれば）、それはフリーリストまたは最低使用頻度（ＬＲＵ）リストの何れかに関連付けられている。各リスト内のアンロックパーセルは、ある順序で割当てられる。フリーリストまたはＬＲＵリスト上の各パーセルの状態、並びに各アンロックパーセルの順番は、そのパーセルに割当てられたパーセルヘッダー２６４内に含まれている情報によって決定される。この情報は、パーセルキャッシュ管理者５９によって維持されている。
【００５４】
図９は、図８のヘッダープール２６２内のパーセルヘッダー２６４の１つの構造を示している。パーセルヘッダー２６４は、ブロック２２０内に含まれている各パーセル、またはフリーブロックに関連付けられたデータ構造である。プール２６２内の全てのパーセルヘッダーは、類似の構造を有することができる。各パーセルヘッダー２６４は、その関連するパーセルの探索、及び使用を容易にする情報、及びパーセルキャッシュの使用を容易にする情報を含む。各パーセルヘッダー２６４は、以下の種類のデータを含んでいる。
【００５５】
最初に、各パーセルヘッダー２６４はそのパーセルのための独自の識別子（ “Buffer ID"とラベル付けされている）を含む。このフィールド内のデータ２８０は、もしブロックがフリーであれば“０”である。この Buffer IDデータ値は、パーセルＩＤ（例えば、媒体上のパーセルのためのＩＤ）から、領域のためのＩＤから、または両者の組合せから導出することができる。好ましい実施例では、２つの Buffer ID２８０はヘッダープール内で同一ではない。
【００５６】
次に、パーセルヘッダー２６４は、順序付けられたフリーリスト、または順序付けられたＬＲＵリストの何れかの中の先行パーセルに関連付けられたヘッダーを識別するデータ２８２（ “pPrev"とラベル付けられている）を含む。もし Buffer IDが“０”であってそのパーセルがフリーリスト上にあることを指示していれば、このアイテムのデータ２８２はフリーリスト上の先行ヘッダーを識別する。もし Buffer IDが“０”以外であってそのパーセルがＲＬＵリスト上にあることを指示していれば、このアイテムのデータ２８２はＲＬＵリスト上の先行ヘッダーを識別する。
【００５７】
次に、パーセルヘッダー２６４は、順序付けられたフリーリスト、または順序付けられたＬＲＵリストの何れかの中の次のパーセルに関連付けられたヘッダーを識別するデータ２８４（ “pNext"とラベル付けられている）を含む。もし Buffer IDが“０”であってそのパーセルがフリーリスト上にあることを指示していれば、このアイテムのデータ２８４はフリーリスト上の次のヘッダーを識別する。もし Buffer IDが“０”以外であってそのパーセルがＲＬＵリスト上にあることを指示していれば、このアイテムのデータ２８４はＲＬＵリスト上の次のヘッダーを識別する。（ pPrev２８２、及び pNext２８４は、ブロック文脈に依存して、それらのそれぞれのヘッダーをフリーリスト、またはＬＲＵに連鎖させるために使用される。）
次いで、パーセルヘッダー２６４は、同一の Buffer IDを有するパーセルのパーセルヘッダーの二重にリンクされたリスト内の先行パーセルヘッダーを識別するデータ２８６（ “pHashPrev"とラベル付けられている）を含んでいる。
【００５８】
次いで、パーセルヘッダー２６４は、同一の Buffer IDを有するパーセルのパーセルヘッダーの二重にリンクされたリスト内の次のパーセルヘッダーに関連付けられたヘッダーを識別するデータ２８８（ “pHashNext"とラベル付けられている）を含んでいる。
【００５９】
パーセルヘッダー２６４は、ヘッダーと、メモリアドレスによって格納されているリストとを連鎖させるデータ２９０（ “pAddPrev" とラベル付けられている）及びデータ２９２（ “pAddNext" とラベル付けられている）を含んでいる。後述するように、これは併合化及び合体を援助する。
【００６０】
次に、パーセルヘッダー２６４は、パーセルデータが位置しているバッファ内のアドレスを指し示すデータ２９４（ “pPages" とラベル付けられている）を含んでいる。図６を参照する。このデータ２９４は、パーセルが位置しているブロック２２４内のページ２２２を指し示すことができる。もしこのブロックがフリーであれば、このデータ２９４はフリーメモリブロックを指し示す。
【００６１】
パーセルヘッダー２６４は、次に、そのパーセルを含むバッファを参照するデータ２９６（ “pCache" とラベル付けられている）を含んでいる。
次いで、パーセルヘッダー２６４は、後述するようにパーセル待ち行列のためのターンスタイル対象( turnstile object )を指し示すデータ２９８（ “pTurnstile" とラベル付けられている）を含んでいる。この情報は、Ｉ／Ｏが進行中に同一のパーセルに対する第２の要求が発生した場合、パーセルの探索を排除するために使用される。
【００６２】
パーセルヘッダー２６４は、次に、ブロックのサイズを限定するデータ３００（ “pages"とラベル付けられている）を含んでいる。
【００６３】
次に、パーセルヘッダー２６４は、パーセルを移動または破棄することができるか否かを指示するデータ３０２（ “lockCount"とラベル付けられている）を含んでいる。この値が０以外であれば、そのパーセルは移動または破棄されない。このアイテムのデータは、そのパーセルに関する照会が行われる度毎に１つだけインクリメントされ、そのパーセルに関する照会が満足される度毎に１つだけデクレメントされる。従って、もしそのパーセルに対して１回より多くの要求がなされれば、このアイテムのデータは、そのパーセルに対する全ての要求が満足されてしまうまでは、そのパーセルが破棄されないことを保証する。
【００６４】
パーセルヘッダー２６４は、次に、ブロックが有効データを含んでいる場合にセットされるデータフィールド３０６（ “bLoaded"とラベル付けられている）を含んでいる。この値はパーセルヘッダーがフリーリスト上にある間は有効ではない。パーセルヘッダー内のこのアイテムのデータ３０６（ “bLoaded"）がクリアされると、それは関連ブロックが現在読み込み中であることを指示する。
【００６５】
最後に、パーセルヘッダー２６４は、それがロックされているか否かには関係なく、パーセルデータがスワッピングのために使用可能であるか否かを指示するデータ３０８（ “bWired" とラベル付けられている）を含んでいる。もしこのデータフィールド３０８がセットされていれば、たとえそれがアンロックであっても、そのパーセルをスワップすることはできない。
【００６６】
ｄ．パーセル待ち行列。  前述したように、もしナビゲーション機能２８からの照会に対して必要なデータのパーセルがパーセルキャッシュ２０７内に存在していなければ、そのパーセルは媒体からパーセルキャッシュ２０７内へ読み込まれ、それをアクセス機能が使用してナビゲーション機能２８からの照会を満足させるようになる。図１０及び１１を参照する。媒体からパーセルを入手するために、パーセルキャッシュ２０７はパーセル待ち行列４００と共働する。パーセル待ち行列４００は、パーセル待ち行列管理者機能４０４（図２）によって形成され、管理される。図２に示したように、パーセル待ち行列管理者４０４は、アクセス機能３９の中にあることができる。パーセルキャッシュとパーセル待ち行列との間の連絡は、双方向である。パーセル待ち行列４００は、パーセルキャッシュ２０７のためのパーセルに対する要求を含むために使用される。パーセル待ち行列管理者４０４はパーセル待ち行列４００を使用して、パーセルに対する要求を媒体デバイスソフトウェア層４０８へ引渡す。この層４０８は記憶媒体３２へアクセスする媒体デバイス（図１のドライブ１４のような）をインタフェースするのに使用される。
【００６７】
一実施例では、パーセル待ち行列管理者４０４は、媒体からのパーセルへのアクセスを効率的にする特色を提供する。例えば、パーセルキャッシュ２０７は同一パーセルに対する多重要求を受けることができる。パーセル待ち行列管理者４０４は、同一パーセルが２回読み出されないようにパーセル要求を濾過する。パーセル待ち行列管理者４０４は、これらの多重要求を認識し、単一の要求だけを媒体デバイス層４０８へ引渡す。
【００６８】
図１１を参照する。パーセル待ち行列管理者４０４は、パーセル待ち行列４００を維持している。対応する待ち行列４０９が媒体デバイス層４０８内に位置している。パーセル待ち行列管理者４０４は、パーセル待ち行列４００を管理するために２つのデータ対象を使用する。これらのデータ対象は、ターンスタイル対象４１２、及びパーセル要求対象４１４を含む。ターンスタイル対象４１２は、媒体デバイス層４０８へ転送されるパーセルに対する要求を同期させるために使用される。媒体デバイス層４０８内の対応する待ち行列４０９内の各要求毎に、１つのターンスタイル対象４１２が割当てられる。
【００６９】
ナビゲーティング機能が必要とするパーセルがパーセルキャッシュ２０７内に存在しない場合（ハッシュテーブル２６６を探索することによって決定される）には、パーセルキャッシュ管理者５９はパーセル要求対象４１４を作成する。パーセル要求対象４１４はパーセル待ち行列４００へ供給され、パーセル待ち行列４００においてパーセル待ち行列管理者４０４によってターンスタイル対象４１２が形成され、パーセル要求対象４１４に関連付けられる。ターンスタイル対象４１２は、ハンドルをパーセル要求対象４１２へ戻す。もし同一パーセルに対するターンスタイル対象４１２が、先行パーセル要求４１４を満足させるために既にパーセル待ち行列４００内に作成されていれば、同一パーセルに対する第２のパーセル要求４１４及びその後のパーセル要求４１４は、同一ターンスタイル対象４１２にリンクされる。従って、同一パーセルに対して多重要求がなされた場合には、図１１に示すように、多重パーセル要求対象４１４が単一のターンスタイル対象４１２に割当てられ、連鎖される。前述したように、パーセル要求を参照するために使用されるハンドルがターンスタイル対象４１２によって戻されるので、たとえ要求されたパーセルの読み出しが１回だけであっても、一旦それがパーセルキャッシュ内に入れられれば、それを要求した全ての機能はそのパーセルを使用することができる。
【００７０】
ターンスタイル対象４１２内の情報を使用して、パーセル待ち行列管理者４０４はパーセルに対する要求を媒体デバイス層４０８内の媒体待ち行列４０９へ転送する。詳述すれば、パーセル待ち行列管理者４０４は、特定の領域／オフセット／サイズ組合せ４２０に対する要求を媒体デバイス層４０８へ転送する。領域／オフセット／サイズ組合せの領域部分は、媒体上に格納されている１つまたはそれ以上のファイル（各々が分離した領域を表すことができる）のどのファイルを読み出すのかを識別するために使用される。領域／オフセット／サイズ組合せのオフセット部分は、識別された領域ファイルにおいて所望のパーセルデータが開始される位置を識別するために使用される。領域／オフセット／サイズ組合せのサイズ部分は、所望のパーセルを読み出すためには、オフセット位置から開始してどれ程多くのデータを読み出すのかを識別するために使用される。
【００７１】
図１１は、パーセル待ち行列４００及び３つのパーセルのためのトランザクション／要求レイアウトを示している。パーセル１に対しては１つの要求がなされており、パーセル２はそれに対してなされた２つの要求を有し、パーセル３はそれに対してなされた３つの要求を有している。（これらに加えて、他のパーセルに対する付加的な要求が存在し得る。）パーセル待ち行列４００を使用することによりこれら６つのパーセル要求４１４が、媒体待ち行列４０９においては僅か３つの要求にされている。
【００７２】
媒体デバイス分離層４０８は、パーセルに対する要求（領域／オフセット／サイズ組合せの表現で）をパーセル待ち行列４００から受ける。媒体デバイス分離層４０８においては、媒体からパーセルを読み出すデバイスの読み出しヘッドの走行を最小にするために、要求されたパーセルの順序を再配列することができる。例えば、ＣＤ−ＲＯＭのような低速媒体の場合には、散在させた、またはスキップされる読み出し支援が設けられていれば、性能を改善することができる。媒体デバイス分離層４０８は特定の型の媒体に合わせることができ、また特定のプラットフォームのために特定的に準備することができる。
【００７３】
あるパーセルのためのＩ／Ｏが完了すると、媒体デバイス層４０８は、Ｉ／Ｏ完了をパーセル待ち行列管理者４０４に連絡するために関連するセマフォを通知する。各ターンスタイル対象は、要求されたパーセルがロードされるまで、タスクまたプロセスが処理を中断させることを可能にする関連するセマフォを含んでいる。パーセル待ち行列管理者４０４は、Ｉ／Ｏの完了を検出するとパーセルキャッシュ管理者５９に通報する。パーセルキャッシュ管理者５９は、キャッシュ内に読み込まれたパーセルのための関連するパーセルヘッダー２６４内の bLoadedフラグ３０６（図９）をセットさせる。
【００７４】
ｅ．プリキャッシュ制限。  前述したように、若干のナビゲーション機能２８はプリキャッシングを行う。プリキャッシングはナビゲーションシステムの性能を強化する価値ある方法であることはできるが、もし中間データ要求のためにナビゲーションシステム資源が必要になれば、それは性能を損なう可能性がある。従って、プリキャッシュ要求を管理して、中間要求に対して優先順位を与えることができるようにする方法を提供することが望ましい。一実施例では、プリキャッシュ要求を管理して優先順位を与えるために、パーセル待ち行列管理者４０４を使用する。プリキャッシュ要求は、どのデータが必要とされ得るかの予測に基づいているから（しかし、実際には未だに要求されていない）、プリキャッシュ要求には、直ちに必要とされるパーセルに対する要求よりも低い優先順位を割当てることができる。パーセル待ち行列管理者４０４は、この目的のためにプリキャッシュ要求にハンドルを割当てる。これにより、もしナビゲーション機能２８からのデータの即時要求を満足させるためにナビゲーションシステム資源が必要であれば、プリキャッシュ要求を取り消すのが容易になる。
【００７５】
パーセル待ち行列管理者４０４の一実施例がプリキャッシュ使用を管理する一方法は、パーセルキャッシュがプリキャッシュ要求のために使用できる程度を制限することによっている。これは、パーセルキャッシュの少なくとも一部分を非プリキャッシュ要求のために常時保留する効果を有している。図１２は、プリキャッシュの使用を制限するために、パーセル待ち行列管理者４０４が実行するプログラミングステップを示している。プリキャッシュ要求のために使用することができる全パーセルキャッシュの部分の上限を確立するパーセンテージが限定される。このパーセンテージは、パーセルキャッシュ管理者４０４がセットすることができる。例えば、一実施例では、プリキャッシュ要求は、パーセルキャッシュのサイズの 70 ％に制限されている。この限度は構成可能である。
【００７６】
パーセル待ち行列管理者４０４はプリキャッシングのこの限度を実現するために、ペンディングになっているプリキャッシュ要求に対して使用される現在のバイト数を追跡する。パーセル待ち行列管理者４０４は、付加的なパーセル要求を受けると、この数を使用する。もし新しいプリキャッシュパーセルが要求され、プリキャッシュ要求に対して使用されているパーセルキャッシュの現在の合計量に追加された時に上限を超えれば、そのプリキャッシュ要求は取り消される。ペンディングになっているプリキャッシュ要求を追跡する際に、完了した要求は考慮に入れないか、またはプリキャッシュ及び非プリキャッシュの両要求に（ターンスタイル対象を介して）関連付けられたパーセルに対する要求でもない。
【００７７】
プリキャッシュを制限しても、照会が、不十分なメモリ資源に遭遇する可能性がある。これは、キャッシュフラグメンテーションに起因して、または例外的な数の同時データ要求が存在したために発生し得る。この潜在的な問題に対処するために、メモリ資源が不十分である時には全てのプリキャッシュ要求を破棄することができる。代替として、若干の選択されたプリキャッシュ要求のグループだけを取り消すことができる。
【００７８】
ｆ．併合化。  前述したように、媒体から読み出された地理データの各パーセルはパーセルキャッシュ内に格納され、パーセルキャッシュから要求中のナビゲーション機能へデータが供給されるようになっている。データパーセルに対する要求は、パーセル識別子（例えば、「パーセルＩＤ」）の表現でなされる。キャッシュメモリ２０７内のパーセルの探索は、ハッシュテーブル２６６を使用して遂行される。もしパーセルがキャッシュ内に存在していなければ、媒体からパーセルを読み出す要求が発生する。パーセルがパーセルキャッシュ２０７内に入れられると、バッファアドレスがナビゲーション応用へ戻された時にそのパーセルはバッファ内にロックされる。これは、要求が活動状態になった時にバッファがスワップされるのを阻止する。このロックは、パーセルがナビゲーション応用２８によって解放されると解除される。
【００７９】
殆どの時間、パーセルキャッシュは一杯であり、現在のブロックを破棄しなければ新しいパーセルを受入れることはできない。時には、現在のブロックを破棄することなく、キャッシュ内のブロックを再配列して到来するパーセルに適合する充分な空間を合体させることができる。パーセルキャッシュ管理者５９は、新しいパーセルを格納するのに充分な空間を得るのに併合化が必要であるか否かを決定するために、各バッファ２２０内のフリー空間の量を追跡している。
【００８０】
一実施例では、併合化が使用される程度は構成可能である。例えば、併合化は、比較的アグレッシブに、比較的非アグレッシブに、またはアグレッシブと非アグレッシブとの間にあるように構成することができる。非アグレッシブ併合化では、フリーメモリ（必ずしも隣接はしていない）の量が新しいパーセルのために必要なサイズの少なくとも２倍にならない限り併合化は発生しない。アグレッシブ併合化では、フリーメモリ（必ずしも隣接はしていない）の量が新しいパーセルのために必要なサイズの少なくとも２倍に等しいと併合化が実施される。
【００８１】
パーセルキャッシュ管理者５９が併合化を遂行する場合、それは、１つまたは２つの条件が真になった時にブロックを再配置する。第１に、図１３に示すように、フリーブロック２２４Ａに隣接する使用中のブロック２２４Ｂが、別のフリーブロック２２４Ｄを完全に満たすことができる場合には、パーセルキャッシュ管理者５９は併合化を遂行する。第２に、図１４に示すように、単一の使用中のブロック２２４Ｂが、２つのフリーブロック２２４Ａと２２４Ｃとの間にある時には、パーセルキャッシュ管理者５９は併合化を遂行する。
【００８２】
一実施例では、割当てられるメモリはキャッシュのトップ（アドレス順で）から下方へ成長する。これは、フリーブロックの端からメモリを割当てる方が、始まりから割当てるより（アンリンクし、再サイジングし、そして再リンクする代わりに、フリーブロックを再サイジングする方が）容易だからである。また、パーセルヘッダー２６４はアドレスで順序付けられたリストに配列され、各々は次のブロックを見出すのに使用することができるサイズ値（即ち、図９の「ページ２９４」）を保持している。フリーブロック内の最後のページ（即ち、ブロックのための境界タグを形成している）もサイズ値を含んでおり、これは、フリーブロックを合体させる目的のためにフリーブロックのリストを通して後方へ移動することができる。
【００８３】
パーセルキャッシュ管理者５９は、キャッシュのトップから開始し、始まりへ戻るように動作して併合化を遂行する。ロックされた（即ち、図９における “lockCount ３０２" ＞０であるような）ブロック、またはワイヤード（即ち、図９における “bWired３０８" ≠０であるような）ブロックは、再配置のために考慮されることはない。また、もし割当て要求を満足する充分なフリー空間が得られれば、併合化機能は終了する。
【００８４】
併合化プロセスのための擬似コードは以下の通りである。
【００８５】
0004489860.tif 000002
代替実施例では、パーセル管理者５９内の統計構造内に成功した併合化が、レコードされる。パーセル管理者５９はこれらの統計を使用して、併合化の頻度を知的に制御することができる。
【００８６】
代替実施例では、パーセルキャッシュ２０７は併合化なしに使用することができる。もしパーセルキャッシュが充分に大きければ、キャッシュを併合化させるためにパーセルを移動させるのではなく、パーセルを全て破棄する方がより効率的であるかも知れない。
【００８７】
ｇ．空間割当て。  典型的には、ナビゲーションシステムが暫時動作した後は、キャッシュ内のフリー空間だけが、異なるサイズのパーセルのフリーイング／割当てによっ作られた小さい断片である。キャッシュ内には存在しないパーセルに対する要求を満足させるために、パーセル管理者５９はキャッシュチェーンを通して多重パスを行い、割当てが完了すると直ちに戻すことができる。第１のパスにおいてパーセル管理者５９は、要求を満足するために充分に大きいブロックが使用可能であるか否かを調べる。もし充分に大きいブロックが使用可能でなければ、パーセル管理者５９はキャッシュを併合させる（もし併合化が可能化され、上述した基準に適合すれば）。
【００８８】
もし併合化によって新しいパーセルのための充分な空間が得られなければ、パーセル管理者５９は、以下に説明する最低使用頻度（ＬＲＵ）アルゴリズムを介して破棄する。ＬＲＵアルゴリズムは、パーセルの読み出し数を最小にすることを試み、エージ( age ) を斟酌する。ＬＲＵアルゴリズムは、要求されたページ数を満足させることを試みる際に、２回のパスを行う。第１のパスはＬＲＵの最古の 75 ％に作用し、以下の基準に合致するブロックを破棄し、割当てる。
【００８９】
１．ブロックは要求のサイズの２倍であるか、またはより大きく、それはキャッシュの最古の 25 ％以内である。
【００９０】
２．ブロックは、要求されたサイズに正確に一致する。
【００９１】
３．ブロックは、使用中のブロックをフリーにすることが充分なサイズのフリー空間をもたらすように、フリーブロックに隣接している。
【００９２】
第１のパスは、要求を満足させるために単一のパーセルを破棄することをシークする。もしこれが、キャッシュの最古の 75 ％を処理した後に充分な空間を設けることに失敗すれば、第２のパスが行われ、厳格にＬＲＵに基づいてそれらのブロックを破棄する。最後に、もし、それでも充分な空間が得られなければ、全てのプリキャッシュ要求は（パーセル待ち行列管理者４０４によって）取り消される。
【００９３】
Ｖ．開示した実施例の長所
上述した実施例は、メモリ資源を比較的効率的に使用するパーセルキャッシュを提供している。また、開示した実施例における断片化（フラグメンテーション）は比較的小さい。これらの長所は、部分的には、パーセルヘッダー情報をパーセルデータから分離したことによって達成される。これにより、使用可能なブロック内に概ね適合するパーセルサイズが得られ、メモリの未使用部分が比較的大きくなることを回避する。
【００９４】
開示した実施例によってもたらされる別の長所は、どのパーセルがキャッシュ内に位置しているのかを決定するためにハッシュテーブルを使用したことによって、キャッシュの内容を決定するのにキャッシュを直接調べないことである。比較的大きいキャッシュは、調べるのにかなりな長さの時間を必要とするから、これは、比較的大きいキャッシュを有する大きいシステムにおいては特に有利である。従って、数百キロバイトから数ギガバイトまでのキャッシュサイズが支援される。これにより、開示した実施例は汎用性を有するようになり、同一キャッシュシステムを、手持ちナビゲーションシステム及びビークル搭載システムのような比較的小さいメモリを有する比較的小さいシステムにも、大きいメモリを有するネットワークされたサーバのような比較的大きいシステムにも使用することができる。
【００９５】
開示した実施例によって提供される別の長所は、パーセルキャッシュを効率的に併合化できることである。メモリブロックは、必要な場合に移動する。併合化は、特定のハードウェアプラットフォーム及び使用の型の要求に合わせることができるように構成可能である。併合化は、大きいキャッシュ／高速媒体環境に対しては完全に遮断することができる。
【００９６】
開示した実施例によって提供される別の長所は、それらが異なるサイズのパーセルを比較的良好に処理することである。これにより地理データは、地理データを最も効率的に編成するパーセルサイズで媒体上に格納することができる。
【００９７】
ＶＩ．代替実施例
開示した実施例は、本発明の概念を特定的に実施したものに過ぎず、本発明の範囲内でいろいろな他の種類の実施を考案することができる。例えば、ハッシュテーブル及びヘッダープールの代わりに、他の種類の構造を使用してキャッシュ内のパーセルの索引、及びキャッシュ内のパーセルの位置の識別に関連する機能を実現することができる。
【００９８】
地理データのパーセルは、パーセルキャッシュ内に圧縮した、または圧縮解除された形状で格納することができる。例えば、もしパーセルが応用からの要求を満足させるために圧縮解除されていれば、この圧縮解除されたパーセルはその圧縮解除された形状でパーセルキャッシュ内に格納することができ、それによって次にそのパーセル内のデータが必要になった時に、パーセルを再び圧縮解除する必要はなくなる。パーセルヘッダは、パーセルの圧縮解除されたサイズを指示する情報を含むことができるので、パーセルキャッシュ内の充分な空間を、圧縮解除された形状のパーセルを保持するのに使用可能にすることができる。代替として、パーセルは、媒体上に格納されているものと同じ圧縮されたフォーマットでパーセルキャッシュ内に格納することができる。パーセルを圧縮された形状でパーセルキャッシュ内に格納することは、パーセル当たり少ないメモリでよく、それによってより多くのパーセルを格納することができるという長所が得られる。圧縮された、及び圧縮解除されたパーセルを、同時にキャッシュ内に格納することができる。例えば、もしプリキャッシュ要求に応答してパーセルをパーセルキャッシュ内に格納すれば、それらは圧縮された形状で格納し、実際に必要になった時にだけ圧縮解除することができる。応用からの要求を満足させるためにパーセルを圧縮解除した後は、そのパーセルはその圧縮解除された形状で格納することができ、そのパーセルの圧縮されたコピーは破棄される。
【００９９】
上述した実施例においては、各ヘッダープールは、パーセルキャッシュのために使用されるメモリの各バッファの一部で形成され、それぞれのメモリのバッファ内のパーセルを参照するヘッダを含んでいる。代替実施例では、ヘッダープールは、ヘッダープール内に含まれているパーセルヘッダーによって表されるパーセルを含むメモリのバッファの外側の、メモリの別の部分内に位置することができる。
【０１００】
代替実施例においては、ナビゲーションシステムは、ハードウェアプラットフォームまたはアーキテクチャには関係なく、エンドユーザにナビゲーション機能を提供する、どのようなコンピュータをベースとするシステムをも含むものと理解すべきである。例えば、ナビゲーションシステムは、手持ちシステム、またはパーソナルディジタル支援またはパーソナルコンピュータ上に設置されたシステムのような、どのような種類のポータブルシステムをも含むことができる。代替実施例では、ナビゲーションシステムは、デスクトップコンピュータのようなパーソナルコンピュータ上に設置されたナビゲーション応用ソフトウェアを含むことができる。更に、ナビゲーションシステムは、ネットワークされた環境、及びクライアントサーバプラットフォーム環境を含むさまざまな異なる環境内で実現することができる。ナビゲーション応用プログラム及び地理データベースは同一位置に配置する必要はなく、ネットワークを介して接続することができる。地理データベースをエンドユーザから離して配置し、データは無線ネットワークを通してエンドユーザに伝送することができる。
【０１０１】
上述した実施例では、キャッシュが地理データのパーセルを保持するものと説明した。代替実施例では、キャッシュはパーセル化されていない、または異なる種類の配列を使用して編成された地理データを保持することができる。例えば、キャッシュは、パーセルに編成されていない個々のデータレコードを保持するために使用することができる。これらのデータレコードは、圧縮することも、または圧縮しないこともできる。もしキャッシュ内の地理データがパーセル（または類似のグルーピング）に編成されていなければ、ハッシュテーブル及びパーセルヘッダーに類似のデータ構造を準備して、キャッシュ内のデータ及びキャッシュ内のデータの位置を識別する。他の面においては、この実施例は同じように動作し、使用される。
【０１０２】
上述した実施例においては、ナビゲーションシステム及び応用内の成分、データ構造、等々を呼ぶのにある用語を使用している。これらの種類の成分、データ構造、等々を呼ぶのに他の用語を使用することもでき、開示した主題は類似概念を表現するためにどのような特定の用語にも制限されるものではないことを理解されたい。
【０１０３】
パーセルキャッシュの再サイジング。  第１の実施例に関連して説明したように、パーセルキャッシュのための初期バッファは、初期化時に応用によってパーセルキャッシュサブシステム内へ渡される。後刻、パーセルキャッシュ内の空間の量を増加させるために、パーセルキャッシュのための付加的なバッファをパーセルキャッシュサブシステムへ渡すことができる。これは、パーセルをこのバッファから他のバッファ内へ再配置した後に限って、またはパーセルをこのバッファから破棄した後に限って、可能でないかも知れないし（もしバッファ内にロックされたパーセルが存在すれば）、可能であるかも知れない。従って、付加的なバッファを応用へ復帰させるための要求に関して、（本実施例では）ロックされたパーセルがアンロックになる（他のタスクまたはプロセスによって）まで要求タスクまたはプロセスを中断するオプションを含む幾つかのオプションを設けることができる。更に、付加的なバッファをパーセルキャッシュサブシステムへ渡すことに関して、（本実施例では）付加的なバッファをパーセルキャッシュサブシステム内へ渡すタスクまたはプロセスだけによって要求されたパーセルのための付加的なバッファを反転させる（これらのパーセルは、他のタスクまたはプロセスと共用されるが）オプション（このオプションは、後刻バッファを同一タスクまたはプロセスに復帰させることができる見込みを増加させる）を含む幾つかのオプションを設けることができる。
【０１０４】
サブセクタパーセル。  パーセルのサイズは、媒体の最小アドレス可能単位（「セクタ」として知られている）を細分した「サブセクタ」単位の倍数であることができる。これは、パーセルデータ内容がその記憶空間を正確に充填していないことに起因する浪費を減少させることによって、媒体の記憶空間を保存するために行うことができる。例えばＣＤ−ＲＯＭ媒体（セクタ単位は２Ｋｂである）用の実施例では、パーセルのサイズは 256バイトの倍数に制約されるので、パーセル内の浪費データは 256バイトより少ない量になる（代わりに、もしパーセルのサイズが２Ｋｂの倍数に制約されていれば、２Ｋより少ない量になる）。
【０１０５】
「サブセクタ」パーセルの場合には、パーセルをパーセルキャッシュ内にロードし、格納できる幾つかの可能方法が存在する。本実施例では、パーセルを構成している全てのセクタは、１つのＩ／Ｏ要求動作で直接キャッシュ内に読み込まれ、キャッシュ内に完全に格納されるが、パーセルの一部ではない最初と最後のセクタの部分が、キャッシュ内の浪費空間を占める。この実施例は、１つだけのＩ／Ｏ要求を使用し、臨時バッファからデータをコピーする必要はないが、あるキャッシュ空間を浪費する（平均で、約１セクタ／パーセル）。この実施例ではページサイズは１セクタであり、パーセルヘッダー構造はその最初のセクタ内のパーセルのオフセットを指示する特別フィールドを含んでいる。第２の実施例では、１つのＩ／Ｏ要求でパーセルが多重セクタ臨時バッファ内へ読み込まれ、次いでそのページだけがキャッシュ内にコピーされる。この後者の実施例では、ページサイズはサブセクタ単位である。浪費されるキャッシュ空間は存在しないが臨時バッファのための空間は必要であり、臨時バッファからキャッシュ内へコピーするために特別な処理が必要である。第３の実施例では、パーセルは３つまでのＩ／Ｏ要求で読み込まれる。最初と最後の要求は単一のセクタを臨時バッファに読み込むためのものであり、中間の要求は直接パーセルキャッシュに読み込むためのものである。この第３の実施例のページサイズはサブセクタ単位である。浪費されるキャッシュ空間は存在せず、臨時バッファ及びコピーイングは第１及び第３のＩ／Ｏ要求のみに制限されるが、３つの分離したＩ／Ｏ要求が必要になる。
【０１０６】
以上の詳細な説明は単なる例示に過ぎず、本発明は特許請求の範囲によってのみ限定されるものであることを理解されたい。
【図面の簡単な説明】
【図１】ナビゲーションシステムのブロック図である。
【図２】図１のナビゲーション応用ソフトウェアの部分を示すブロック図である。
【図３】地理データを空間的に編成するためのパーセル化方法の応用を説明するために使用される地理領域の地図を示す図である。
【図４】図３のパーセル化方法に従って図１及び２の地理データベース内のデータのパーセルの配列を示す図である。
【図５】図１のナビゲーションシステム内のメモリ資源の使用を示す図である。
【図６】図５のパーセルキャッシュ内のバッファの１つを示す図である。
【図７】図６内のバッファの１つの使用を示すブロック図である。
【図８】図７のヘッダープールの内容及びそれと共に使用される関連ハッシュテーブルを示す図である。
【図９】図８の各パーセルヘッダー内に格納されている情報を示す図である。
【図１０】図５−７に示すパーセル待ち行列とパーセルキャッシュとの間のデータの流れを示すブロック図である。
【図１１】図１０に示すパーセル待ち行列の成分を示すブロック図である。
【図１２】プリキャッシングを制限するために、図１１のパーセル待ち行列管理者によって遂行されるステップを示す流れ図である。
【図１３】図２及び１１のパーセルキャッシュ管理者によって遂行される併合化ステップを示す図である。
【図１４】別の併合化ステップを示す図である。
【符号の説明】
１０  ナビゲーションシステム
１１  ビークル
１２  プロセッサ
１４  ドライブ
１６  不揮発性メモリ記憶装置
１８  ナビゲーション応用ソフトウェアプログラム
２０  ＲＡＭ
２４  測位システム
２５  感知デバイス
２６  測位信号
２７  ディスプレイ
２８  ナビゲーション機能
２９  スピーカ
３１  ユーザインタフェース
３２  記憶媒体
３３  ルート計算機能
３４  地図表示機能
３５  ルート案内機能
３６  その他の機能
３７  ユーザインタフェースプログラミング
３８  オペレーティングシステム
３９  アクセス機能
４０  地理データベース
５５  照会変換機能
５６  データ探索機能
５７  データ変換機能
５９  キャッシュ管理者機能
１１１  地図
１１２  地理領域
１１４  位置
１１７  格子
１１９  矩形領域
２０２  ナビゲーション機能が使用する部分
２０４  アクセス機能が使用する部分
２０６  パーセルキャッシュのために使用される部分
２０７  パーセルキャッシュ
２０８  再割当て可能部分
２２０  バッファ
２２２  ページ
２２４  ブロック
２６０  ヘッダープールとして使用するバッファの部分
２６２  ヘッダープール
２６４  パーセルヘッダー
２６６  ハッシュテーブル
２６８  ポインタ
４００  パーセル待ち行列
４０４  待ち行列管理者機能
４０８  媒体デバイスソフトウェア層
４０９  媒体待ち行列
４１２  ターンスタイル
４１４  パーセル要求
【図１】
0004489860.tif 000003
【図２】
0004489860.tif 000004
【図３】
0004489860.tif 000005
【図４】
0004489860.tif 000006
【図５】
0004489860.tif 000007
【図６】
0004489860.tif 000008
【図７】
0004489860.tif 000009
【図８】
0004489860.tif 000010
【図９】
0004489860.tif 000011
【図１０】
0004489860.tif 000012
【図１１】
0004489860.tif 000013
【図１２】
0004489860.tif 000014
【図１３】
0004489860.tif 000015
【図１４】
0004489860.tif 000016