JPH11327979A - ナビゲーションシステムのための改良されたメモリ管理 - Google Patents

Abstract

(57)【要約】 【課題】 地理データにアクセスするナビゲーション応
用プログラムと共に使用されるシステム内のメモリ資源
を管理する方法及びシステムを提供する。 【解決手段】 地理データは複数のデータレコードから
なる。これらはパーセルに編成され、各パーセルは複数
のデータレコードの一部分を含み、各パーセルを形成し
ている複数のデータレコードの各部分は一緒にアクセス
される。ナビゲーションシステムのメモリの隣接する部
分を形成している１つまたはそれ以上のバッファが、複
数のパーセルを格納するキャッシュとして設けられる。
メモリの隣接する部分の外側に位置する１つまたはそれ
以上のデータ構造は、キャッシュ内に格納されているデ
ータのパーセルと、パーセルが格納されているキャッシ
ュ内の位置を識別する他に、パーセルキャッシュの使用
を効率的にするように管理するためと、パーセルキャッ
シュを併合するためにも使用される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はナビゲーションシス
テムに関し、詳しく述べれば、本発明は地理データベー
スの使用及びアクセスを容易ならしめるナビゲーション
システムのためのメモリ管理に関する。

【０００２】

【従来の技術】エンドユーザにいろいろなナビゲーティ
グン機能及び特色を提供する、コンピュータをベースと
するナビゲーション応用プログラムを使用することがで
きる。例えば、若干のナビゲーションシステムはビーク
ルに搭載され、エンドユーザ（即ち、ビークルの運転
手）に地理領域内の複数の位置の間の道路を走行するた
めの最適ルートを提供することができる。エンドユーザ
からの入力、及びオプションとしてユーザの物理的位置
を決定できる機器（例えば、ＧＰＳシステム）からの入
力を使用して、ナビゲーション応用プログラムは地理領
域内の２つの位置の間のいろいろなルートを調べ、出発
点から目的地まで走行するのに最適なルートを決定する
ことができる。次いでナビゲーション応用プログラム
は、出発点から目的地までエンドユーザが走行するのに
必要な運転を識別する命令の形状で、最適ルートに関す
る情報をエンドユーザに提供することができる。もしナ
ビゲーションシステムが自動車に設置されているのであ
れば、命令は、エンドユーザがルートを走行中に供給さ
れるオーディオ命令の形状をとることができる。若干の
ナビゲーション応用プログラムは、目的地までのルート
を示す詳細地図、ルートに沿ういろいろな位置において
とるべき運転の型、若干の型の特色の位置、等々をコン
ピュータディスプレイ上に表示することができる。

【０００３】これらの、及び他のナビゲーティング機能
を提供するために、ナビゲーション応用プログラムは、
地理領域内の物理的特色を表すデータを含む１つまたは
それ以上の詳細なデータベースを使用する。この／これ
らの詳細なデータベースは、地理領域内の道路及び交差
点を表すデータを含むことができ、また交差点における
転回禁止、道路の速度制限、さまざまな道路の街路名、
いろいろな道路に沿う番地範囲、等々のような、表され
た地理領域内の道路及び交差点に関する情報を含むこと
もできる。

【０００４】合理的に高レベルの機能を提供するため
に、比較的大きいデータベースを設けることができる。
ＣＤ−ＲＯＭディスク、またはＰＣＭＣＩＡカードのよ
うな記憶媒体は、適当な機能を提供するのに充分なサイ
ズ及び複雑さのデータベースを取扱うことができる。し
かしながら、コンピュータをベースとするナビゲーショ
ンシステムは、コンピュータハードウェア資源が比較的
制限されているものを含むいろいろなプラットフォーム
上に設置される。例えば、ビークルに搭載の、または手
持ちのナビゲーションシステムのメモリ資源は制限さ
れ、また媒体アクセスレートは比較的遅い。これらの比
較的制限されているハードウェア資源は、エンドユーザ
が期待または要求する比較的高レベルの機能、並びに適
当に高速な性能を提供することが困難である。ナビゲー
ションシステムの性能が低いことは望ましいだけではな
く、若干の環境においては、その意図した目的にとって
システムが無用になりかねない。例えば、もしナビゲー
ションシステムがビークルに搭載されていれば、運転手
は運転中に情報を利用するために、１−２秒程度で所望
ルートに関する情報をナビゲーションシステムから得た
いであろう。もしナビゲーションシステムがルートを計
算するのに数秒より多くを要すれば、運転手は既にナビ
ゲーションシステムが提供するルーティング情報が関連
している点を過ぎて移動してしまっていよう。従って、
適当なレベルの性能を提供するためには、ナビゲーショ
ンシステムを効率的に使用することが必要がある。

【０００５】若干のナビゲーション応用は、より大きい
メモリ資源及び他のハードウェア資源を有するコンピュ
ータプラットフォーム上に設置することができる。これ
らの種類のシステムにも同じ考え方が適用されるが、ス
ケールは異なる。より大きいメモリ及び他のハードウェ
ア資源を有するコンピュータプラットフォームにおいて
は、もし使用可能な資源が効率的に使用されれば、より
大きい機能さえも得ることができる。

【０００６】従って、ナビゲーションシステムの資源を
効率的に使用し、それによってシステムがより良好な性
能を提供できるようにする方法及びシステムを提供する
ことが目的である。

【０００７】

【発明の概要】上述した及び他の目的を達成するため
に、及び本発明の目的によれば、地理データにアクセス
するナビゲーション応用プログラムと共に使用されるシ
ステム内のメモリ資源を管理する方法及びシステムが提
供される。地理データは、複数のデータレコードからな
る。複数のデータレコードはパーセル、またはグルーピ
ングに編成され、各パーセルまたはグルーピングは複数
のデータレコードの一部分を含み、各パーセルを形成し
ている複数のデータレコードの各部分内のデータレコー
ドは一緒にアクセスされるようになっている。複数のパ
ーセルを格納するためのキャッシュとして、各々がナビ
ゲーションシステムのメモリの隣接する部分を形成して
いる１つまたはそれ以上のバッファが設けられる。メモ
リの隣接する部分の外側に位置する１つまたはそれ以上
のデータ構造は、キャッシュ内に格納されているデータ
のパーセルと、パーセルが格納されているキャッシュ内
の位置とを識別する。パーセルがキャッシュされている
メモリの隣接する部分の外側に位置する１つまたはそれ
以上のデータ構造は、パーセルキャッシュを併合（デフ
ラグメント）させるためにも使用される。

【０００８】

【実施例】Ｉ．ナビゲーションシステム−概要 図１に、ナビゲーションシステム１０をブロック図で示
す。ナビゲーションシステム１０は、乗用車またはトラ
ックのようなビークル１１内に設置されているが、代替
実施例では、ナビゲーションシステム１０は、後述する
ように、ビークル外に位置することも、または他のいろ
いろなプラットフォームまたは環境内に実現することも
できる。

【０００９】図１に示す実施例では、ナビゲーションシ
ステム１０はハードウェア及びソフトウェア成分の組合
せである。一実施例では、ナビゲーションシステム１０
はプロセッサ１２、プロセッサ１２に接続されているド
ライブ１４、及びナビゲーション応用ソフトウェアプロ
グラム１８並びに構成パラメータ１９のような他の情報
を格納している不揮発性メモリ記憶装置１６を含んでい
る。プロセッサ１２は、日立ＳＨ１、インテル 80386、
インテル 960、モトローラ 68020（または、類似の、ま
たはより大きいアドレス空間を有する他のプロセッサ）
のようなフラットアドレス空間を使用する 32 ビットプ
ロセッサのような、ナビゲーションシステム内に使用さ
れるどのような型であることもできる。これら以外の型
のプロセッサ、及び将来開発されるかも知れないプロセ
ッサも適当であり得る。

【００１０】ナビゲーションシステム１０は、測位シス
テム２４を含むこともできる。測位システム２４は、当
分野においては公知の、ＧＰＳ型技術、推測型システ
ム、またはこれらの組合せ、または他のシステムを利用
することができる。測位システム２４は、ビークルの走
行距離、速度、方向、等々を測定する適当な感知デバイ
ス２５を含むことができる。測位システム２４は、当分
野においては公知の手法でＧＰＳ信号を入手する適切な
技術を含むこともできる。測位システム２４は、信号２
６をプロセッサ１２へ出力する。プロセッサ１２上で走
るナビゲーション応用ソフトウェア１８はこの信号２６
を使用して、ナビゲーションシステム１０の位置、方
向、速度、等々を決定することができる。

【００１１】ナビゲーションシステム１０は、ユーザイ
ンタフェース３１も含んでいる。ユーザインタフェース
３１は、エンドユーザがナビゲーションシステム内へ情
報を入力できるようにする適切な機器を含む。この入力
情報は、ナビゲーションシステムのナビゲーション特色
の使用の要求を含む。例えば、入力情報は、所望の目的
地までのルートに関する要求を含むことができる。入力
情報は、構成情報のような他の種類の情報を含むことも
できる。ナビゲーションシステム内へ情報を入力するた
めに使用される機器は、キーパッド、キーボード、マイ
クロホン、等々、並びに音声認識プログラムのような適
切なソフトウェアを含むことができる。ユーザインタフ
ェース３１は、エンドユーザへ情報を戻す適当な機器も
含む。この機器は、ディスプレイ２７、スピーカ２９、
または他の手段を含むことができる。

【００１２】ナビゲーションシステム１０は、記憶媒体
３２上に格納されている地図データベース４０を使用す
る。ナビゲーションシステムが地図データベース４０を
読み出して使用することができるように、記憶媒体３２
はドライブ１４内に設置されている。記憶媒体３２は取
り外し可能であり、置換可能であるので、ビークルが走
行している地理領域のための適切な地図データベースを
有する記憶媒体を使用することができる。更に、記憶媒
体３２は置換可能であるので、その上の地図データベー
ス４０は容易に更新することができる。一実施例では、
地理データはカリフォルニア州サニービルの Navigatio
n Technologiesから出版されているものであることがで
きる。

【００１３】一実施例においては、記憶媒体３２はＣＤ
−ＲＯＭディスクである。代替実施例においては、記憶
媒体３２はＰＣＭＣＩＡカードであることができ、この
場合ドライブ１４はＰＣＭＣＩＡスロットに置換され
る。固定またはハードディスク、ＤＶＤ（ディジタルビ
デオディスク）、または現在市販されている他の記憶媒
体、並びに将来開発されるかも知れない記憶媒体を含む
他のさまざまな記憶媒体を使用することができる。記憶
媒体３２及び地理データベース４０は、物理的にナビゲ
ーションシステムの位置に設ける必要はない。代替実施
例においては、地理データベース４０の若干、または全
てを格納している記憶媒体３２はナビゲーションシステ
ムの残余から離して配置することができ、地理データの
一部は必要に応じて通信リンクを介して供給される。

【００１４】図２を参照する。ナビゲーション応用１８
は、個々のナビゲーション機能（または、サブプログラ
ム）２８を提供するソフトウェアプログラミングを含
む。これらのナビゲーション機能２８は、例えば、ルー
ト計算機能３３、地図表示機能３４、ルート案内機能３
５（所望の目的地へ到達するための詳細な指令が供給さ
れる）を含む。ナビゲーション応用プログラム１８は、
これらの他に、または代替として、ビークル位置決め機
能（例えば、マップマッチング）のような他の機能また
はサブプログラム３６を含むことができる。これらのナ
ビゲーション応用機能２８は、ナビゲーション応用プロ
グラム１８内に分離したサブプログラムまたは応用とし
て表されているが、これらの機能２８は組合せたり、ま
たはそれ以外に設けることもできる。ナビゲーション応
用プログラム１８は、ユーザインタフェース機器３１
（図１）を支援するユーザインタフェースプログラミン
グ３７をも含む。例えば、このユーザインタフェースプ
ログラミング３７は、ユーザインタフェース３１、メニ
ューの表示、プロンプト、等々を介してエンドユーザへ
の情報の図形表示を提供することができる。ナビゲーシ
ョン応用１８は、オペレーティングシステムを含むこと
もできる。ナビゲーション応用１８は、地理データベー
ス４０へアクセスする特定機能３９をも含むことができ
る。好ましい実施例では、これらの機能３９はいろいろ
なナビゲーション応用２８と地理データベース４０との
間、より詳しく言えば、ナビゲーション機能２８とオペ
レーティングシステム３８との間に位置している。これ
らの機能３９は、ナビゲーティング機能２８の間で地理
データベース４０への共用アクセスを容易にするキャッ
シュ管理機能５９及び待ち行列機能４０４のようなメモ
リ管理機能を含む。 II. 地理データベース ａ．概要。 地理データ４０は、１つまたはそれ以上の
コンピュータ可読データファイル、またはデータベース
の形状で媒体３２上に格納されている。地理データ４０
は、特定の地理領域内の、またはそれに関係付けられた
道路及び交差点の位置に関する情報を含むことも、また
は、一方通行道路、転回禁止のような道路及び交差点の
属性に関する情報、または街路番地、ホテル、レストラ
ン、博物館、スタジアム、オフィス、自動車販売会社、
自動車修理工場、等のような他の情報を含むことができ
る。地理データベースのカバレッジ領域は、シカゴとそ
の郊外、ニューヨークとその郊外、ロスアンジェルスと
その郊外のような大都市圏を含むことができ、または代
替として、領域はカリフォルニアのような州（ステー
ト）全体、合衆国のような国全体、またはドイツ、フラ
ンス、及びイタリアもしくはこれらの組合せのような１
つの国より多くの国を含むことができる。記憶媒体上に
は１つの領域より多くの領域を格納することができる。

【００１５】記憶媒体３２上の地理データ４０を使用す
る時に、ナビゲーション応用プログラム１８内のナビゲ
ーション機能２８の動作及び性能に影響を与え得る幾つ
かのファクタが存在する。合理的に高レベルの機能を提
供するために、比較的大きいデータベースを設けること
ができる。ＣＤ−ＲＯＭディスク、またはＰＣＭＣＩＡ
カードのような記憶媒体は、適当な機能を提供するのに
充分なサイズ及び複雑さのデータベースを取扱うことが
できる。しかしながら、これらの型の媒体のアクセシン
グは比較的遅い。ナビゲーションシステムはビークルに
搭載することも、手持ちであることもできるので、ナビ
ゲーションシステムのハードウェア資源は制限され得
る。これらのナビゲーションシステムのメモリ資源が制
限されているために、ナビゲーション応用プログラムが
使用するためには、地理ディスクをＣＤ−ＲＯＭのよう
な記憶媒体からナビゲーションシステムのメモリ内に必
要に応じてロードする必要がある。不幸にも、前述した
ように、これらの型のシステムの媒体アクセスも比較的
遅いことがあり得る。

【００１６】ナビゲーションシステム資源が制限されて
いることによって賦課される制約に対処するために、地
理データベース、またはデータベース内のデータを特定
の手法で編成し、構成し、または配列することによって
ナビゲーションシステムの性能を改善するための技術が
考案、または実現されている。ナビゲーションシステム
は既知の機能を遂行するために、地理データを若干の既
知の、そして予測できるような手法で使用するので、地
理データはナビゲーションシステムによるこれらの既知
の手法で使用するのを容易にするように編成し、構成
し、または配列することができる。

【００１７】ナビゲーション応用プログラムは、ネット
ワークを通してアクセス可能なパーソナルコンピュータ
または地理データベースサーバのような比較的多くのメ
モリ資源及び高速Ｉ／Ｏを有するコンピュータプラット
フォーム上で走らせることもできる。これらのプラット
フォームはより多くの、そしてより高速の資源を有する
ことはできるが、それでも地理データベースの効率的な
使用に関する考え方はスケールは異なるとしても適用さ
れる。これらの型のプラットフォームを用いると、もし
地理データベースを効率的に形成し、使用することがで
きれば、より多くの機能さえも提供することができる。

【００１８】ｂ．パーセル化。 ナビゲーションシステ
ムによる地理データの使用を容易にするために使用でき
る技術の中には、パーセル化が含まれる。ナビゲーショ
ン応用プログラムが走っているナビゲーションシステム
のメモリ資源が制限されているために、所与の地理領域
全体のための全てのデータレコードをナビゲーションシ
ステムのメモリ内に同時にロードできないものとすれ
ば、所望の機能を遂行するのに必要なデータだけをメモ
リ内へロードすることが望ましい。これを達成するため
に、地理データベース３０内のデータベースは、ナビゲ
ーション機能を遂行するために媒体へアクセスし、媒体
から読み出すのに必要な時間の長さを最短にするように
編成される。このようにするために、データはパーセル
に編成される。データベースがパーセル化される場合、
一緒になって地理データを構成する複数のデータレコー
ドが分離したグループ、即ちパーセルにグループ化され
る。データのパーセルは、パーセル内の全てのデータが
一緒に、媒体から同時にアクセスされるように確立され
る。これは、１回のディスクアクセスでアクセスできる
データの量に関係するが、他のあるファクタに関係付け
ることもできる。ＣＤ−ＲＯＭディスクのような若干の
型の媒体の場合には、パーセルは 16 キロバイトのデー
タ量であるように確立することができる。（１Ｋ、２
Ｋ、４Ｋ、８Ｋ、32Ｋ等を含む他のデータサイズも使用
可能である。地理データベースの部分は一般に２ⁿ キロ
バイトのサイズで形成される。但し、ｎは１より大きい
整数値である。） パーセル化と共に、地理データの使用を容易にするため
に、それらを編成できる別の方法は、データを空間的に
編成することである。地理データが空間的に編成されて
いると、地理領域内で互いに物理的に近接している特色
は、データベース内でも物理的に（または、論理的に）
互いに近接しているデータレコードによって表される。
地理データは、これらの両技術を利用するために、パー
セル化し、空間的に編成することができる。

【００１９】データをパーセルに形成する目的で、デー
タは先ず、それらにアクセスするナビゲーション機能２
８に基づいて異なる型に空間的に編成される。従って、
ナビゲーション機能２８の若干、または全ては、地理デ
ータの分離した集まりであることができる。分離した各
集まりは、それぞれの機能を遂行するために必要なデー
タの本質的な部分を含むが、その機能を遂行するために
不要な部分は省かれる。従って、地理データベース内に
は、１つまたはそれ以上のナビゲーション機能２８に関
連付けられたルーティング、地図作成（地図表示）、運
転（ルート案内）、関心点、名前、等々のような分離し
た型のデータが存在し得る。

【００２０】ナビゲーション機能２８によるデータの使
用を容易ならしめるために、これらの種類のデータの若
干は空間的にパーセル化することができる。空間的にパ
ーセル化されたデータは、地理的に近接する特色を表す
データが、データベース４０及び／または媒体３２内で
論理的に、及び／または物理的に近接して位置するよう
に配列される。若干のナビゲーション応用機能の場合に
は、それらの関連データを空間的にパーセル化すると、
それらを使用する時に密に関係している地理データを媒
体からより迅速に読み出したり、関連地理データをメモ
リ内にロードすることができる。この種類の編成は、記
憶媒体３２のアクセスを最小にし、これらのナビゲーシ
ョン機能の動作をスピードアップさせることができる。
ルーティング、地図作成、及び関心点データは、空間的
に編成できる種類のデータに含まれる。

【００２１】地理データを空間的にパーセル化するため
に使用できる多くの異なる手順が存在している。例え
ば、簡単なパーセル化方法では、データが複数のパーセ
ル、またはグルーピングに分離される。各パーセル内の
データは、一緒になって地理領域上に規則的な矩形格子
を形成する複数の規則的なサイズの矩形の分離した１つ
の中に含まれる特色を表す。別の空間パーセル化方法
は、パーセルサイズが最大しきい値以下になるまで、領
域の部分を包含する矩形を等分して行くことによって各
矩形を形成するように、データを矩形領域内に含まれる
パーセルに分離する。更に、パーセル化手順が 1996 年
10月25日付同時出願第 08/740,295 号に開示され、その
全文が参照として本明細書に採り入れられており、また
パーセル化手順が 1997 年９月５日付同時出願第 08/93
5,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を有するパーセルのパーセルヘッダーの二
重にリンクされたリスト内の次のパーセルヘッダーに関
連付けられたヘッダーを識別するデータ２８８（ “pHa
shNext"とラベル付けられている）を含んでいる。

【００５９】パーセルヘッダー２６４は、ヘッダーと、
メモリアドレスによって格納されているリストとを連鎖
させるデータ２９０（ “pAddPrev" とラベル付けられ
ている）及びデータ２９２（ “pAddNext" とラベル付
けられている）を含んでいる。後述するように、これは
併合化及び合体を援助する。

【００６０】次に、パーセルヘッダー２６４は、パーセ
ルデータが位置しているバッファ内のアドレスを指し示
すデータ２９４（ “pPages" とラベル付けられてい
る）を含んでいる。図６を参照する。このデータ２９４
は、パーセルが位置しているブロック２２４内のページ
２２２を指し示すことができる。もしこのブロックがフ
リーであれば、このデータ２９４はフリーメモリブロッ
クを指し示す。

【００６１】パーセルヘッダー２６４は、次に、そのパ
ーセルを含むバッファを参照するデータ２９６（ “pCa
che" とラベル付けられている）を含んでいる。次い
で、パーセルヘッダー２６４は、後述するようにパーセ
ル待ち行列のためのターンスタイル対象( turnstile ob
ject )を指し示すデータ２９８（ “pTurnstile" とラ
ベル付けられている）を含んでいる。この情報は、Ｉ／
Ｏが進行中に同一のパーセルに対する第２の要求が発生
した場合、パーセルの探索を排除するために使用され
る。

【００６２】パーセルヘッダー２６４は、次に、ブロッ
クのサイズを限定するデータ３００（ “pages"とラベ
ル付けられている）を含んでいる。

【００６３】次に、パーセルヘッダー２６４は、パーセ
ルを移動または破棄することができるか否かを指示する
データ３０２（ “lockCount"とラベル付けられてい
る）を含んでいる。この値が０以外であれば、そのパー
セルは移動または破棄されない。このアイテムのデータ
は、そのパーセルに関する照会が行われる度毎に１つだ
けインクリメントされ、そのパーセルに関する照会が満
足される度毎に１つだけデクレメントされる。従って、
もしそのパーセルに対して１回より多くの要求がなされ
れば、このアイテムのデータは、そのパーセルに対する
全ての要求が満足されてしまうまでは、そのパーセルが
破棄されないことを保証する。

【００６４】パーセルヘッダー２６４は、次に、ブロッ
クが有効データを含んでいる場合にセットされるデータ
フィールド３０６（ “bLoaded"とラベル付けられてい
る）を含んでいる。この値はパーセルヘッダーがフリー
リスト上にある間は有効ではない。パーセルヘッダー内
のこのアイテムのデータ３０６（ “bLoaded"）がクリ
アされると、それは関連ブロックが現在読み込み中であ
ることを指示する。

【００６５】最後に、パーセルヘッダー２６４は、それ
がロックされているか否かには関係なく、パーセルデー
タがスワッピングのために使用可能であるか否かを指示
するデータ３０８（ “bWired" とラベル付けられてい
る）を含んでいる。もしこのデータフィールド３０８が
セットされていれば、たとえそれがアンロックであって
も、そのパーセルをスワップすることはできない。

【００６６】ｄ．パーセル待ち行列。 前述したよう
に、もしナビゲーション機能２８からの照会に対して必
要なデータのパーセルがパーセルキャッシュ２０７内に
存在していなければ、そのパーセルは媒体からパーセル
キャッシュ２０７内へ読み込まれ、それをアクセス機能
が使用してナビゲーション機能２８からの照会を満足さ
せるようになる。図１０及び１１を参照する。媒体から
パーセルを入手するために、パーセルキャッシュ２０７
はパーセル待ち行列４００と共働する。パーセル待ち行
列４００は、パーセル待ち行列管理者機能４０４（図
２）によって形成され、管理される。図２に示したよう
に、パーセル待ち行列管理者４０４は、アクセス機能３
９の中にあることができる。パーセルキャッシュとパー
セル待ち行列との間の連絡は、双方向である。パーセル
待ち行列４００は、パーセルキャッシュ２０７のための
パーセルに対する要求を含むために使用される。パーセ
ル待ち行列管理者４０４はパーセル待ち行列４００を使
用して、パーセルに対する要求を媒体デバイスソフトウ
ェア層４０８へ引渡す。この層４０８は記憶媒体３２へ
アクセスする媒体デバイス（図１のドライブ１４のよう
な）をインタフェースするのに使用される。

【００６７】一実施例では、パーセル待ち行列管理者４
０４は、媒体からのパーセルへのアクセスを効率的にす
る特色を提供する。例えば、パーセルキャッシュ２０７
は同一パーセルに対する多重要求を受けることができ
る。パーセル待ち行列管理者４０４は、同一パーセルが
２回読み出されないようにパーセル要求を濾過する。パ
ーセル待ち行列管理者４０４は、これらの多重要求を認
識し、単一の要求だけを媒体デバイス層４０８へ引渡
す。

【００６８】図１１を参照する。パーセル待ち行列管理
者４０４は、パーセル待ち行列４００を維持している。
対応する待ち行列４０９が媒体デバイス層４０８内に位
置している。パーセル待ち行列管理者４０４は、パーセ
ル待ち行列４００を管理するために２つのデータ対象を
使用する。これらのデータ対象は、ターンスタイル対象
４１２、及びパーセル要求対象４１４を含む。ターンス
タイル対象４１２は、媒体デバイス層４０８へ転送され
るパーセルに対する要求を同期させるために使用され
る。媒体デバイス層４０８内の対応する待ち行列４０９
内の各要求毎に、１つのターンスタイル対象４１２が割
当てられる。

【００６９】ナビゲーティング機能が必要とするパーセ
ルがパーセルキャッシュ２０７内に存在しない場合（ハ
ッシュテーブル２６６を探索することによって決定され
る）には、パーセルキャッシュ管理者５９はパーセル要
求対象４１４を作成する。パーセル要求対象４１４はパ
ーセル待ち行列４００へ供給され、パーセル待ち行列４
００においてパーセル待ち行列管理者４０４によってタ
ーンスタイル対象４１２が形成され、パーセル要求対象
４１４に関連付けられる。ターンスタイル対象４１２
は、ハンドルをパーセル要求対象４１２へ戻す。もし同
一パーセルに対するターンスタイル対象４１２が、先行
パーセル要求４１４を満足させるために既にパーセル待
ち行列４００内に作成されていれば、同一パーセルに対
する第２のパーセル要求４１４及びその後のパーセル要
求４１４は、同一ターンスタイル対象４１２にリンクさ
れる。従って、同一パーセルに対して多重要求がなされ
た場合には、図１１に示すように、多重パーセル要求対
象４１４が単一のターンスタイル対象４１２に割当てら
れ、連鎖される。前述したように、パーセル要求を参照
するために使用されるハンドルがターンスタイル対象４
１２によって戻されるので、たとえ要求されたパーセル
の読み出しが１回だけであっても、一旦それがパーセル
キャッシュ内に入れられれば、それを要求した全ての機
能はそのパーセルを使用することができる。

【００７０】ターンスタイル対象４１２内の情報を使用
して、パーセル待ち行列管理者４０４はパーセルに対す
る要求を媒体デバイス層４０８内の媒体待ち行列４０９
へ転送する。詳述すれば、パーセル待ち行列管理者４０
４は、特定の領域／オフセット／サイズ組合せ４２０に
対する要求を媒体デバイス層４０８へ転送する。領域／
オフセット／サイズ組合せの領域部分は、媒体上に格納
されている１つまたはそれ以上のファイル（各々が分離
した領域を表すことができる）のどのファイルを読み出
すのかを識別するために使用される。領域／オフセット
／サイズ組合せのオフセット部分は、識別された領域フ
ァイルにおいて所望のパーセルデータが開始される位置
を識別するために使用される。領域／オフセット／サイ
ズ組合せのサイズ部分は、所望のパーセルを読み出すた
めには、オフセット位置から開始してどれ程多くのデー
タを読み出すのかを識別するために使用される。

【００７１】図１１は、パーセル待ち行列４００及び３
つのパーセルのためのトランザクション／要求レイアウ
トを示している。パーセル１に対しては１つの要求がな
されており、パーセル２はそれに対してなされた２つの
要求を有し、パーセル３はそれに対してなされた３つの
要求を有している。（これらに加えて、他のパーセルに
対する付加的な要求が存在し得る。）パーセル待ち行列
４００を使用することによりこれら６つのパーセル要求
４１４が、媒体待ち行列４０９においては僅か３つの要
求にされている。

【００７２】媒体デバイス分離層４０８は、パーセルに
対する要求（領域／オフセット／サイズ組合せの表現
で）をパーセル待ち行列４００から受ける。媒体デバイ
ス分離層４０８においては、媒体からパーセルを読み出
すデバイスの読み出しヘッドの走行を最小にするため
に、要求されたパーセルの順序を再配列することができ
る。例えば、ＣＤ−ＲＯＭのような低速媒体の場合に
は、散在させた、またはスキップされる読み出し支援が
設けられていれば、性能を改善することができる。媒体
デバイス分離層４０８は特定の型の媒体に合わせること
ができ、また特定のプラットフォームのために特定的に
準備することができる。

【００７３】あるパーセルのためのＩ／Ｏが完了する
と、媒体デバイス層４０８は、Ｉ／Ｏ完了をパーセル待
ち行列管理者４０４に連絡するために関連するセマフォ
を通知する。各ターンスタイル対象は、要求されたパー
セルがロードされるまで、タスクまたプロセスが処理を
中断させることを可能にする関連するセマフォを含んで
いる。パーセル待ち行列管理者４０４は、Ｉ／Ｏの完了
を検出するとパーセルキャッシュ管理者５９に通報す
る。パーセルキャッシュ管理者５９は、キャッシュ内に
読み込まれたパーセルのための関連するパーセルヘッダ
ー２６４内の bLoadedフラグ３０６（図９）をセットさ
せる。

【００７４】ｅ．プリキャッシュ制限。 前述したよう
に、若干のナビゲーション機能２８はプリキャッシング
を行う。プリキャッシングはナビゲーションシステムの
性能を強化する価値ある方法であることはできるが、も
し中間データ要求のためにナビゲーションシステム資源
が必要になれば、それは性能を損なう可能性がある。従
って、プリキャッシュ要求を管理して、中間要求に対し
て優先順位を与えることができるようにする方法を提供
することが望ましい。一実施例では、プリキャッシュ要
求を管理して優先順位を与えるために、パーセル待ち行
列管理者４０４を使用する。プリキャッシュ要求は、ど
のデータが必要とされ得るかの予測に基づいているから
（しかし、実際には未だに要求されていない）、プリキ
ャッシュ要求には、直ちに必要とされるパーセルに対す
る要求よりも低い優先順位を割当てることができる。パ
ーセル待ち行列管理者４０４は、この目的のためにプリ
キャッシュ要求にハンドルを割当てる。これにより、も
しナビゲーション機能２８からのデータの即時要求を満
足させるためにナビゲーションシステム資源が必要であ
れば、プリキャッシュ要求を取り消すのが容易になる。

【００７５】パーセル待ち行列管理者４０４の一実施例
がプリキャッシュ使用を管理する一方法は、パーセルキ
ャッシュがプリキャッシュ要求のために使用できる程度
を制限することによっている。これは、パーセルキャッ
シュの少なくとも一部分を非プリキャッシュ要求のため
に常時保留する効果を有している。図１２は、プリキャ
ッシュの使用を制限するために、パーセル待ち行列管理
者４０４が実行するプログラミングステップを示してい
る。プリキャッシュ要求のために使用することができる
全パーセルキャッシュの部分の上限を確立するパーセン
テージが限定される。このパーセンテージは、パーセル
キャッシュ管理者４０４がセットすることができる。例
えば、一実施例では、プリキャッシュ要求は、パーセル
キャッシュのサイズの 70 ％に制限されている。この限
度は構成可能である。

【００７６】パーセル待ち行列管理者４０４はプリキャ
ッシングのこの限度を実現するために、ペンディングに
なっているプリキャッシュ要求に対して使用される現在
のバイト数を追跡する。パーセル待ち行列管理者４０４
は、付加的なパーセル要求を受けると、この数を使用す
る。もし新しいプリキャッシュパーセルが要求され、プ
リキャッシュ要求に対して使用されているパーセルキャ
ッシュの現在の合計量に追加された時に上限を超えれ
ば、そのプリキャッシュ要求は取り消される。ペンディ
ングになっているプリキャッシュ要求を追跡する際に、
完了した要求は考慮に入れないか、またはプリキャッシ
ュ及び非プリキャッシュの両要求に（ターンスタイル対
象を介して）関連付けられたパーセルに対する要求でも
ない。

【００７７】プリキャッシュを制限しても、照会が、不
十分なメモリ資源に遭遇する可能性がある。これは、キ
ャッシュフラグメンテーションに起因して、または例外
的な数の同時データ要求が存在したために発生し得る。
この潜在的な問題に対処するために、メモリ資源が不十
分である時には全てのプリキャッシュ要求を破棄するこ
とができる。代替として、若干の選択されたプリキャッ
シュ要求のグループだけを取り消すことができる。

【００７８】ｆ．併合化。 前述したように、媒体から
読み出された地理データの各パーセルはパーセルキャッ
シュ内に格納され、パーセルキャッシュから要求中のナ
ビゲーション機能へデータが供給されるようになってい
る。データパーセルに対する要求は、パーセル識別子
（例えば、「パーセルＩＤ」）の表現でなされる。キャ
ッシュメモリ２０７内のパーセルの探索は、ハッシュテ
ーブル２６６を使用して遂行される。もしパーセルがキ
ャッシュ内に存在していなければ、媒体からパーセルを
読み出す要求が発生する。パーセルがパーセルキャッシ
ュ２０７内に入れられると、バッファアドレスがナビゲ
ーション応用へ戻された時にそのパーセルはバッファ内
にロックされる。これは、要求が活動状態になった時に
バッファがスワップされるのを阻止する。このロック
は、パーセルがナビゲーション応用２８によって解放さ
れると解除される。

【００７９】殆どの時間、パーセルキャッシュは一杯で
あり、現在のブロックを破棄しなければ新しいパーセル
を受入れることはできない。時には、現在のブロックを
破棄することなく、キャッシュ内のブロックを再配列し
て到来するパーセルに適合する充分な空間を合体させる
ことができる。パーセルキャッシュ管理者５９は、新し
いパーセルを格納するのに充分な空間を得るのに併合化
が必要であるか否かを決定するために、各バッファ２２
０内のフリー空間の量を追跡している。

【００８０】一実施例では、併合化が使用される程度は
構成可能である。例えば、併合化は、比較的アグレッシ
ブに、比較的非アグレッシブに、またはアグレッシブと
非アグレッシブとの間にあるように構成することができ
る。非アグレッシブ併合化では、フリーメモリ（必ずし
も隣接はしていない）の量が新しいパーセルのために必
要なサイズの少なくとも２倍にならない限り併合化は発
生しない。アグレッシブ併合化では、フリーメモリ（必
ずしも隣接はしていない）の量が新しいパーセルのため
に必要なサイズの少なくとも２倍に等しいと併合化が実
施される。

【００８１】パーセルキャッシュ管理者５９が併合化を
遂行する場合、それは、１つまたは２つの条件が真にな
った時にブロックを再配置する。第１に、図１３に示す
ように、フリーブロック２２４Ａに隣接する使用中のブ
ロック２２４Ｂが、別のフリーブロック２２４Ｄを完全
に満たすことができる場合には、パーセルキャッシュ管
理者５９は併合化を遂行する。第２に、図１４に示すよ
うに、単一の使用中のブロック２２４Ｂが、２つのフリ
ーブロック２２４Ａと２２４Ｃとの間にある時には、パ
ーセルキャッシュ管理者５９は併合化を遂行する。

【００８２】一実施例では、割当てられるメモリはキャ
ッシュのトップ（アドレス順で）から下方へ成長する。
これは、フリーブロックの端からメモリを割当てる方
が、始まりから割当てるより（アンリンクし、再サイジ
ングし、そして再リンクする代わりに、フリーブロック
を再サイジングする方が）容易だからである。また、パ
ーセルヘッダー２６４はアドレスで順序付けられたリス
トに配列され、各々は次のブロックを見出すのに使用す
ることができるサイズ値（即ち、図９の「ページ２９
４」）を保持している。フリーブロック内の最後のペー
ジ（即ち、ブロックのための境界タグを形成している）
もサイズ値を含んでおり、これは、フリーブロックを合
体させる目的のためにフリーブロックのリストを通して
後方へ移動することができる。

【００８３】パーセルキャッシュ管理者５９は、キャッ
シュのトップから開始し、始まりへ戻るように動作して
併合化を遂行する。ロックされた（即ち、図９における
“lockCount ３０２" ＞０であるような）ブロック、
またはワイヤード（即ち、図９における “bWired３０
８" ≠０であるような）ブロックは、再配置のために考
慮されることはない。また、もし割当て要求を満足する
充分なフリー空間が得られれば、併合化機能は終了す
る。

【００８４】併合化プロセスのための擬似コードは以下
の通りである。

【００８５】 FOREACH block(a), scanning from highest to lowest IF block(a) is in-use THEN IF adjacent blocks are free THEN relocate block to the highest free block ELSE FOREACH in-use blodk(b), scanning from lowest to previous(block(a)) IF size of block(a) ＝size of blodk(b) AND blodk(b) is adjacent to a free block THEN relocate block(b) to block(a) ENDIF 代替実施例では、パーセル管理者５９内の統計構造内に
成功した併合化が、レコードされる。パーセル管理者５
９はこれらの統計を使用して、併合化の頻度を知的に制
御することができる。

【００８６】代替実施例では、パーセルキャッシュ２０
７は併合化なしに使用することができる。もしパーセル
キャッシュが充分に大きければ、キャッシュを併合化さ
せるためにパーセルを移動させるのではなく、パーセル
を全て破棄する方がより効率的であるかも知れない。

【００８７】ｇ．空間割当て。 典型的には、ナビゲー
ションシステムが暫時動作した後は、キャッシュ内のフ
リー空間だけが、異なるサイズのパーセルのフリーイン
グ／割当てによっ作られた小さい断片である。キャッシ
ュ内には存在しないパーセルに対する要求を満足させる
ために、パーセル管理者５９はキャッシュチェーンを通
して多重パスを行い、割当てが完了すると直ちに戻すこ
とができる。第１のパスにおいてパーセル管理者５９
は、要求を満足するために充分に大きいブロックが使用
可能であるか否かを調べる。もし充分に大きいブロック
が使用可能でなければ、パーセル管理者５９はキャッシ
ュを併合させる（もし併合化が可能化され、上述した基
準に適合すれば）。

【００８８】もし併合化によって新しいパーセルのため
の充分な空間が得られなければ、パーセル管理者５９
は、以下に説明する最低使用頻度（ＬＲＵ）アルゴリズ
ムを介して破棄する。ＬＲＵアルゴリズムは、パーセル
の読み出し数を最小にすることを試み、エージ( age )
を斟酌する。ＬＲＵアルゴリズムは、要求されたページ
数を満足させることを試みる際に、２回のパスを行う。
第１のパスはＬＲＵの最古の 75 ％に作用し、以下の基
準に合致するブロックを破棄し、割当てる。

【００８９】１．ブロックは要求のサイズの２倍である
か、またはより大きく、それはキャッシュの最古の 25
％以内である。

【００９０】２．ブロックは、要求されたサイズに正確
に一致する。

【００９１】３．ブロックは、使用中のブロックをフリ
ーにすることが充分なサイズのフリー空間をもたらすよ
うに、フリーブロックに隣接している。

【００９２】第１のパスは、要求を満足させるために単
一のパーセルを破棄することをシークする。もしこれ
が、キャッシュの最古の 75 ％を処理した後に充分な空
間を設けることに失敗すれば、第２のパスが行われ、厳
格にＬＲＵに基づいてそれらのブロックを破棄する。最
後に、もし、それでも充分な空間が得られなければ、全
てのプリキャッシュ要求は（パーセル待ち行列管理者４
０４によって）取り消される。

【００９３】Ｖ．開示した実施例の長所 上述した実施例は、メモリ資源を比較的効率的に使用す
るパーセルキャッシュを提供している。また、開示した
実施例における断片化（フラグメンテーション）は比較
的小さい。これらの長所は、部分的には、パーセルヘッ
ダー情報をパーセルデータから分離したことによって達
成される。これにより、使用可能なブロック内に概ね適
合するパーセルサイズが得られ、メモリの未使用部分が
比較的大きくなることを回避する。

【００９４】開示した実施例によってもたらされる別の
長所は、どのパーセルがキャッシュ内に位置しているの
かを決定するためにハッシュテーブルを使用したことに
よって、キャッシュの内容を決定するのにキャッシュを
直接調べないことである。比較的大きいキャッシュは、
調べるのにかなりな長さの時間を必要とするから、これ
は、比較的大きいキャッシュを有する大きいシステムに
おいては特に有利である。従って、数百キロバイトから
数ギガバイトまでのキャッシュサイズが支援される。こ
れにより、開示した実施例は汎用性を有するようにな
り、同一キャッシュシステムを、手持ちナビゲーション
システム及びビークル搭載システムのような比較的小さ
いメモリを有する比較的小さいシステムにも、大きいメ
モリを有するネットワークされたサーバのような比較的
大きいシステムにも使用することができる。

【００９５】開示した実施例によって提供される別の長
所は、パーセルキャッシュを効率的に併合化できること
である。メモリブロックは、必要な場合に移動する。併
合化は、特定のハードウェアプラットフォーム及び使用
の型の要求に合わせることができるように構成可能であ
る。併合化は、大きいキャッシュ／高速媒体環境に対し
ては完全に遮断することができる。

【００９６】開示した実施例によって提供される別の長
所は、それらが異なるサイズのパーセルを比較的良好に
処理することである。これにより地理データは、地理デ
ータを最も効率的に編成するパーセルサイズで媒体上に
格納することができる。

【００９７】ＶＩ．代替実施例 開示した実施例は、本発明の概念を特定的に実施したも
のに過ぎず、本発明の範囲内でいろいろな他の種類の実
施を考案することができる。例えば、ハッシュテーブル
及びヘッダープールの代わりに、他の種類の構造を使用
してキャッシュ内のパーセルの索引、及びキャッシュ内
のパーセルの位置の識別に関連する機能を実現すること
ができる。

【００９８】地理データのパーセルは、パーセルキャッ
シュ内に圧縮した、または圧縮解除された形状で格納す
ることができる。例えば、もしパーセルが応用からの要
求を満足させるために圧縮解除されていれば、この圧縮
解除されたパーセルはその圧縮解除された形状でパーセ
ルキャッシュ内に格納することができ、それによって次
にそのパーセル内のデータが必要になった時に、パーセ
ルを再び圧縮解除する必要はなくなる。パーセルヘッダ
は、パーセルの圧縮解除されたサイズを指示する情報を
含むことができるので、パーセルキャッシュ内の充分な
空間を、圧縮解除された形状のパーセルを保持するのに
使用可能にすることができる。代替として、パーセル
は、媒体上に格納されているものと同じ圧縮されたフォ
ーマットでパーセルキャッシュ内に格納することができ
る。パーセルを圧縮された形状でパーセルキャッシュ内
に格納することは、パーセル当たり少ないメモリでよ
く、それによってより多くのパーセルを格納することが
できるという長所が得られる。圧縮された、及び圧縮解
除されたパーセルを、同時にキャッシュ内に格納するこ
とができる。例えば、もしプリキャッシュ要求に応答し
てパーセルをパーセルキャッシュ内に格納すれば、それ
らは圧縮された形状で格納し、実際に必要になった時に
だけ圧縮解除することができる。応用からの要求を満足
させるためにパーセルを圧縮解除した後は、そのパーセ
ルはその圧縮解除された形状で格納することができ、そ
のパーセルの圧縮されたコピーは破棄される。

【００９９】上述した実施例においては、各ヘッダープ
ールは、パーセルキャッシュのために使用されるメモリ
の各バッファの一部で形成され、それぞれのメモリのバ
ッファ内のパーセルを参照するヘッダを含んでいる。代
替実施例では、ヘッダープールは、ヘッダープール内に
含まれているパーセルヘッダーによって表されるパーセ
ルを含むメモリのバッファの外側の、メモリの別の部分
内に位置することができる。

【０１００】代替実施例においては、ナビゲーションシ
ステムは、ハードウェアプラットフォームまたはアーキ
テクチャには関係なく、エンドユーザにナビゲーション
機能を提供する、どのようなコンピュータをベースとす
るシステムをも含むものと理解すべきである。例えば、
ナビゲーションシステムは、手持ちシステム、またはパ
ーソナルディジタル支援またはパーソナルコンピュータ
上に設置されたシステムのような、どのような種類のポ
ータブルシステムをも含むことができる。代替実施例で
は、ナビゲーションシステムは、デスクトップコンピュ
ータのようなパーソナルコンピュータ上に設置されたナ
ビゲーション応用ソフトウェアを含むことができる。更
に、ナビゲーションシステムは、ネットワークされた環
境、及びクライアントサーバプラットフォーム環境を含
むさまざまな異なる環境内で実現することができる。ナ
ビゲーション応用プログラム及び地理データベースは同
一位置に配置する必要はなく、ネットワークを介して接
続することができる。地理データベースをエンドユーザ
から離して配置し、データは無線ネットワークを通して
エンドユーザに伝送することができる。

【０１０１】上述した実施例では、キャッシュが地理デ
ータのパーセルを保持するものと説明した。代替実施例
では、キャッシュはパーセル化されていない、または異
なる種類の配列を使用して編成された地理データを保持
することができる。例えば、キャッシュは、パーセルに
編成されていない個々のデータレコードを保持するため
に使用することができる。これらのデータレコードは、
圧縮することも、または圧縮しないこともできる。もし
キャッシュ内の地理データがパーセル（または類似のグ
ルーピング）に編成されていなければ、ハッシュテーブ
ル及びパーセルヘッダーに類似のデータ構造を準備し
て、キャッシュ内のデータ及びキャッシュ内のデータの
位置を識別する。他の面においては、この実施例は同じ
ように動作し、使用される。

【０１０２】上述した実施例においては、ナビゲーショ
ンシステム及び応用内の成分、データ構造、等々を呼ぶ
のにある用語を使用している。これらの種類の成分、デ
ータ構造、等々を呼ぶのに他の用語を使用することもで
き、開示した主題は類似概念を表現するためにどのよう
な特定の用語にも制限されるものではないことを理解さ
れたい。

【０１０３】パーセルキャッシュの再サイジング。 第
１の実施例に関連して説明したように、パーセルキャッ
シュのための初期バッファは、初期化時に応用によって
パーセルキャッシュサブシステム内へ渡される。後刻、
パーセルキャッシュ内の空間の量を増加させるために、
パーセルキャッシュのための付加的なバッファをパーセ
ルキャッシュサブシステムへ渡すことができる。これ
は、パーセルをこのバッファから他のバッファ内へ再配
置した後に限って、またはパーセルをこのバッファから
破棄した後に限って、可能でないかも知れないし（もし
バッファ内にロックされたパーセルが存在すれば）、可
能であるかも知れない。従って、付加的なバッファを応
用へ復帰させるための要求に関して、（本実施例では）
ロックされたパーセルがアンロックになる（他のタスク
またはプロセスによって）まで要求タスクまたはプロセ
スを中断するオプションを含む幾つかのオプションを設
けることができる。更に、付加的なバッファをパーセル
キャッシュサブシステムへ渡すことに関して、（本実施
例では）付加的なバッファをパーセルキャッシュサブシ
ステム内へ渡すタスクまたはプロセスだけによって要求
されたパーセルのための付加的なバッファを反転させる
（これらのパーセルは、他のタスクまたはプロセスと共
用されるが）オプション（このオプションは、後刻バッ
ファを同一タスクまたはプロセスに復帰させることがで
きる見込みを増加させる）を含む幾つかのオプションを
設けることができる。

【０１０４】サブセクタパーセル。 パーセルのサイズ
は、媒体の最小アドレス可能単位（「セクタ」として知
られている）を細分した「サブセクタ」単位の倍数であ
ることができる。これは、パーセルデータ内容がその記
憶空間を正確に充填していないことに起因する浪費を減
少させることによって、媒体の記憶空間を保存するため
に行うことができる。例えばＣＤ−ＲＯＭ媒体（セクタ
単位は２Ｋｂである）用の実施例では、パーセルのサイ
ズは 256バイトの倍数に制約されるので、パーセル内の
浪費データは 256バイトより少ない量になる（代わり
に、もしパーセルのサイズが２Ｋｂの倍数に制約されて
いれば、２Ｋより少ない量になる）。

【０１０５】「サブセクタ」パーセルの場合には、パー
セルをパーセルキャッシュ内にロードし、格納できる幾
つかの可能方法が存在する。本実施例では、パーセルを
構成している全てのセクタは、１つのＩ／Ｏ要求動作で
直接キャッシュ内に読み込まれ、キャッシュ内に完全に
格納されるが、パーセルの一部ではない最初と最後のセ
クタの部分が、キャッシュ内の浪費空間を占める。この
実施例は、１つだけのＩ／Ｏ要求を使用し、臨時バッフ
ァからデータをコピーする必要はないが、あるキャッシ
ュ空間を浪費する（平均で、約１セクタ／パーセル）。
この実施例ではページサイズは１セクタであり、パーセ
ルヘッダー構造はその最初のセクタ内のパーセルのオフ
セットを指示する特別フィールドを含んでいる。第２の
実施例では、１つのＩ／Ｏ要求でパーセルが多重セクタ
臨時バッファ内へ読み込まれ、次いでそのページだけが
キャッシュ内にコピーされる。この後者の実施例では、
ページサイズはサブセクタ単位である。浪費されるキャ
ッシュ空間は存在しないが臨時バッファのための空間は
必要であり、臨時バッファからキャッシュ内へコピーす
るために特別な処理が必要である。第３の実施例では、
パーセルは３つまでのＩ／Ｏ要求で読み込まれる。最初
と最後の要求は単一のセクタを臨時バッファに読み込む
ためのものであり、中間の要求は直接パーセルキャッシ
ュに読み込むためのものである。この第３の実施例のペ
ージサイズはサブセクタ単位である。浪費されるキャッ
シュ空間は存在せず、臨時バッファ及びコピーイングは
第１及び第３のＩ／Ｏ要求のみに制限されるが、３つの
分離したＩ／Ｏ要求が必要になる。

【０１０６】以上の詳細な説明は単なる例示に過ぎず、
本発明は特許請求の範囲によってのみ限定されるもので
あることを理解されたい。

【図面の簡単な説明】

【図１】ナビゲーションシステムのブロック図である。

【図２】図１のナビゲーション応用ソフトウェアの部分
を示すブロック図である。

【図３】地理データを空間的に編成するためのパーセル
化方法の応用を説明するために使用される地理領域の地
図を示す図である。

【図４】図３のパーセル化方法に従って図１及び２の地
理データベース内のデータのパーセルの配列を示す図で
ある。

【図５】図１のナビゲーションシステム内のメモリ資源
の使用を示す図である。

【図６】図５のパーセルキャッシュ内のバッファの１つ
を示す図である。

【図７】図６内のバッファの１つの使用を示すブロック
図である。

【図８】図７のヘッダープールの内容及びそれと共に使
用される関連ハッシュテーブルを示す図である。

【図９】図８の各パーセルヘッダー内に格納されている
情報を示す図である。

【図１０】図５−７に示すパーセル待ち行列とパーセル
キャッシュとの間のデータの流れを示すブロック図であ
る。

【図１１】図１０に示すパーセル待ち行列の成分を示す
ブロック図である。

【図１２】プリキャッシングを制限するために、図１１
のパーセル待ち行列管理者によって遂行されるステップ
を示す流れ図である。

【図１３】図２及び１１のパーセルキャッシュ管理者に
よって遂行される併合化ステップを示す図である。

【図１４】別の併合化ステップを示す図である。

【符号の説明】

１０ ナビゲーションシステム １１ ビークル １２ プロセッサ １４ ドライブ １６ 不揮発性メモリ記憶装置 １８ ナビゲーション応用ソフトウェアプログラム ２０ ＲＡＭ ２４ 測位システム ２５ 感知デバイス ２６ 測位信号 ２７ ディスプレイ ２８ ナビゲーション機能 ２９ スピーカ ３１ ユーザインタフェース ３２ 記憶媒体 ３３ ルート計算機能 ３４ 地図表示機能 ３５ ルート案内機能 ３６ その他の機能 ３７ ユーザインタフェースプログラミング ３８ オペレーティングシステム ３９ アクセス機能 ４０ 地理データベース ５５ 照会変換機能 ５６ データ探索機能 ５７ データ変換機能 ５９ キャッシュ管理者機能 １１１ 地図 １１２ 地理領域 １１４ 位置 １１７ 格子 １１９ 矩形領域 ２０２ ナビゲーション機能が使用する部分 ２０４ アクセス機能が使用する部分 ２０６ パーセルキャッシュのために使用される部分 ２０７ パーセルキャッシュ ２０８ 再割当て可能部分 ２２０ バッファ ２２２ ページ ２２４ ブロック ２６０ ヘッダープールとして使用するバッファの部分 ２６２ ヘッダープール ２６４ パーセルヘッダー ２６６ ハッシュテーブル ２６８ ポインタ ４００ パーセル待ち行列 ４０４ 待ち行列管理者機能 ４０８ 媒体デバイスソフトウェア層 ４０９ 媒体待ち行列 ４１２ ターンスタイル ４１４ パーセル要求

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成１１年２月１５日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】発明の名称

【補正方法】変更

【補正内容】

【発明の名称】 ナビゲーションシステムのための改良
されたメモリ管理

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号 ＦＩ Ｇ０９Ｂ 29/00 Ｇ０９Ｂ 29/10 Ａ 29/10 Ｇ０６Ｆ 15/40 ３５０Ｂ ３７０Ｃ (72)発明者 ジョン ジャクラス アメリカ合衆国 イリノイ州 60148 ロ ンバード ノース メイン ストリート 135 (72)発明者 アレックス ナッシュ アメリカ合衆国 イリノイ州 60031 カ ントリー トレイルズ ガルニー 4481 (72)発明者 センティル ケイ ナーテサン アメリカ合衆国 イリノイ州 60188 キ ャロル ストリーム バーク ドライヴ 397 (72)発明者 ディヴィッド エス ランパート アメリカ合衆国 イリノイ州 60035 ハ イランド パーク ブラックストーン プ レイス 650

Claims (29)

【特許請求の範囲】
1. 【請求項１】 地理データを使用するナビゲーションシ
   ステムのためのメモリを管理するシステムであって、 上記メモリの一部分を占め、上記地理データの複数の部
   分を保持するために使用されるキャッシュと、 上記キャッシュ内に含まれている地理データの各部分を
   識別し、そのように識別された上記各部分と、上記部分
   が位置している上記キャッシュ内の位置とを関連付ける
   少なくとも１つのデータ構造と、を備えていることを特
   徴とするメモリ管理システム。
2. 【請求項２】 上記少なくとも１つのデータ構造は、 上記地理データの上記部分の関連する１つが格納されて
   いる上記キャッシュ内の位置を各々が識別する複数の第
   １のデータ構造と、 上記キャッシュ内に含まれている上記地理データの上記
   各部分の識別を含む第２のデータ構造と、を備え、 上記各識別は、上記複数の第１のデータ構造の１つに関
   連付けられている請求項１に記載の発明。
3. 【請求項３】 上記地理データは複数のデータレコード
   からなり、上記地理データの上記各部分は上記複数のデ
   ータレコードの一部分からなる請求項１に記載の発明。
4. 【請求項４】 上記地理データは複数のデータレコード
   からなり、上記地理データの上記各部分は上記複数のデ
   ータレコードの空間的に編成された部分からなり、上記
   各部分内のデータレコードは、一緒になってある地理領
   域全体を包含する複数の矩形領域の分離した１つ内に含
   まれる地理特色を表している請求項１に記載の発明。
5. 【請求項５】 上記キャッシュによって占められる上記
   メモリの部分は、上記ナビゲーションシステムの初期化
   時に割当てられる請求項１に記載の発明。
6. 【請求項６】 上記キャッシュによって占められる上記
   メモリの部分は、ランタイム中に少なくとも１つのバッ
   ファの追加によって増補することができる請求項１に記
   載の発明。
7. 【請求項７】 上記キャッシュは、上記メモリ内の隣接
   アドレス範囲を形成する少なくとも１つのバッファを備
   えている請求項１に記載の発明。
8. 【請求項８】 上記メモリは、全て同一のサイズを有し
   ている複数のページで形成されている請求項１に記載の
   発明。
9. 【請求項９】 上記ページは、２Ｋである請求項８に記
   載の発明。
10. 【請求項１０】 上記地理データベースは、物理的媒体
    上に格納されている請求項１に記載の発明。
11. 【請求項１１】 上記物理的媒体は、ＣＤ−ＲＯＭディ
    スクである請求項１０に記載の発明。
12. 【請求項１２】 上記ナビゲーションシステムは、多重
    パーセルキャッシュを備えている請求項１に記載の発
    明。
13. 【請求項１３】 上記地理データベースの上記部分は、
    一般に、ｎを１より大きい整数値として２ⁿ キロバイト
    のサイズに形成されている請求項１に記載の発明。
14. 【請求項１４】 上記メモリは、ｍを１より大きい整数
    値として全てが２^mキロバイトのサイズを有している複
    数のページで形成されている請求項１３に記載の発明。
15. 【請求項１５】 上記ページサイズは、２Ｋである請求
    項１４に記載の発明。
16. 【請求項１６】 上記少なくとも１つのデータ構造が、
    上記キャッシュによって占められる上記メモリの部分以
    外の上記メモリの一部分を占めている請求項１に記載の
    発明。
17. 【請求項１７】 上記キャッシュは複数のバッファから
    なり、上記複数の各バッファは上記メモリの隣接アドレ
    ス範囲を構成し、且つ上記地理データの上記部分の少な
    くとも１つを保持するために使用され、 上記少なくとも１つのデータ構造は、 第１のデータ構造の複数のプールを備え、上記複数の各
    プールは上記複数のバッファの分離した１つに関連して
    おり、上記各プール内の上記各第１のデータ構造はそれ
    ぞれのプールが関連付けられている上記バッファ内に含
    まれる地理データの上記部分の１つを識別するようにな
    っており、 上記キャッシュ内に含まれる地理データの上記各部分の
    識別を含む第２のデータ構造を更に備え、 上記各識別は上記複数の第１のデータ構造の１つに関連
    付けられている請求項１に記載の発明。
18. 【請求項１８】 上記各第１のデータ構造は、上記地理
    データのそれぞれの部分の格納が開始される上記キャッ
    シュ内の位置を識別する情報を含んでいる請求項２に記
    載の発明。
19. 【請求項１９】 上記各第１のデータ構造は、上記地理
    データのそれぞれの部分を格納するために使用される上
    記キャッシュ内のサイズを識別する請求項２に記載の発
    明。
20. 【請求項２０】 上記地理データの上記各部分は、上記
    ナビゲーションシステムによる１回の読み出し動作で一
    時にアクセスすることができる上記地理データの最小量
    を表している請求項１に記載の発明。
21. 【請求項２１】 地理データベースを使用し、メモリを
    有するナビゲーションシステムのためのキャッシュ管理
    システムであって、 地理データのパーセルのためのキャッシュを備え、上記
    各パーセルは上記地理データベースを形成している複数
    のデータレコードの一部分を構成し、上記キャッシュは
    上記メモリの少なくとも１つの隣接バッファで形成さ
    れ、上記少なくとも１つのバッファは上記パーセルのサ
    イズよりも実質的に大きく、それにより複数のパーセル
    が上記バッファを占めることが可能であり、 上記メモリの隣接バッファの外側に位置し、上記バッフ
    ァを占める各パーセル毎のヘッダー情報を含んでいるヘ
    ッダープールと、 上記メモリの隣接バッファの外側に位置し、上記ヘッダ
    ープール内の上記ヘッダー情報を各々が参照するパーセ
    ル識別子の探索可能な索引を含んでいるハッシュテーブ
    ルと、 を更に備え、 それによって、上記キャッシュ内に含まれるパーセルを
    探知することができるようになっている、ことを特徴と
    するキャッシュ管理システム。
22. 【請求項２２】 メモリを含むナビゲーションシステム
    を動作させる方法であって、上記ナビゲーションシステ
    ムは、ナビゲーション機能を提供するためにナビゲーシ
    ョン応用プログラムを実行し、且つある地理領域内の地
    理特色を表すデータレコードを有する地理データベース
    を使用し、上記地理データベースはある媒体上の複数の
    パーセルに編成されており、上記各パーセルは複数のデ
    ータレコードを含み、上記方法は、 パーセルキャッシュとして使用するために上記メモリの
    隣接部分を準備するステップと、 上記ナビゲーション機能を提供するために上記ナビゲー
    ション応用プログラムの実行中に、上記媒体から読み出
    されたデータのパーセルを上記パーセルキャッシュ内に
    格納するステップと、 上記パーセルキャッシュ内に格納されている上記各パー
    セルに関係するデータを、上記パーセルとは分離して上
    記メモリの一部分内に維持されているヘッダー構造内に
    格納するステップと、を備えていることを特徴とする方
    法。
23. 【請求項２３】 上記各パーセルを識別する索引を格納
    するステップを更に備え、上記索引は上記パーセルから
    分離して維持されているそれぞれのヘッダー構造を参照
    する請求項２２に記載の方法。
24. 【請求項２４】 上記索引は、ハッシュテーブルである
    請求項２３に記載の方法。
25. 【請求項２５】 メモリを含むナビゲーションシステム
    を動作させる方法であって、上記ナビゲーションシステ
    ムは、ナビゲーション機能を提供するためにナビゲーシ
    ョン応用プログラムを実行し、且つある地理領域内の地
    理特色を表すデータレコードを有する地理データベース
    を使用し、上記地理データベースは複数のデータレコー
    ドを各々が含む複数のパーセルに編成され、上記方法
    は、 上記ナビゲーション機能を提供するために必要なデータ
    を含んでいるパーセルを要求するステップと、 上記要求されたパーセルをパーセル識別の待ち行列に編
    成するステップと、を備え、 同一のパーセルに対する多重要求は、上記待ち行列内で
    単一のパーセル識別にリンクされる、ことを特徴とする
    方法。
26. 【請求項２６】 上記地理データベースから上記パーセ
    ルを読み出すために、上記パーセル識別子の待ち行列を
    媒体デバイス層へ転送するステップを更に備えている請
    求項２５に記載の方法。
27. 【請求項２７】 もし、ナビゲーション機能を遂行する
    ために未だに必要ではないデータを表すパーセルを、上
    記地理データから読み出された全てのパーセルを格納す
    るために使用される上記メモリ内のパーセルキャッシュ
    へ追加した時に、上記ナビゲーション機能を遂行するた
    めに未だに必要ではないデータを表すパーセルのために
    使用できる上記パーセルキャッシュの部分に課せられた
    限度を超えれば、上記ナビゲーション機能を遂行するた
    めに未だに必要ではないデータを表すパーセルに対する
    要求は、上記待ち行列内の上記単一のパーセル識別の１
    つにリンクされない請求項２５に記載の方法。
28. 【請求項２８】 上記メモリ内にハッシュテーブルを格
    納するステップを更に備え、上記ハッシュテーブルは上
    記パーセルキャッシュ内の各パーセルの識別データを指
    し示している請求項２５に記載の方法。
29. 【請求項２９】 メモリを含むナビゲーションシステム
    を動作させる方法であって、上記ナビゲーションシステ
    ムは、ナビゲーション機能を提供するためにナビゲーシ
    ョン応用プログラムを実行し、且つある地理領域内の地
    理特色を表すデータレコードを有する地理データベース
    を使用し、上記地理データベースは媒体上の複数のパー
    セルに編成され、上記各パーセルは複数のデータレコー
    ドを含み、上記メモリの隣接部分は上記媒体からブロッ
    クで読み出されたパーセルを格納するためのパーセルキ
    ャッシュとして使用され、上記パーセルキャッシュ内の
    上記各パーセルに関係するデータは上記パーセルキャッ
    シュとして使用される上記隣接部分から分離した上記メ
    モリの一部分内に維持されているヘッダー構造内に格納
    され、上記方法は、 上記パーセルキャッシュが既に複数のパーセルを含んで
    いる時には、１つのパーセルを格納するめに上記パーセ
    ルキャッシュを併合させるステップを備え、 上記併合ステップは、 上記ヘッダー構造によって指示されたパーセルを含むど
    のブロックもロックするようにスキップするステップ
    と、 もし使用中のブロックが上記メモリの上記隣接部分の近
    接するフリーブロックを完全に充填することができれ
    ば、またはもし単一の使用中のブロックが上記メモリの
    上記隣接部分の２つのフリーブロックの間にあれば、上
    記ヘッダー構造によって使用中であることが指示された
    ブロックを、上記ヘッダー構造内にフリーであることが
    指示された近接するブロックへ移動させるステップと、
    を備えていることを特徴とする方法。