(57)【要約】空間的目標データのインデックス方法は、目標を含む空間を、空間内の目標のクラスタに応じて分割するものである。コンピュータにより読み取り可能なメディアは、コンピュータで実行可能な命令を含む。これらの命令により、コンピュータは、空間内の目標のクラスタに応じて空間的目標を含む空間を分割する。空間的目標データをサーチする方法は、空間的目標のクラスタに応じてグリッドに分割された空間的目標データを利用する。その後、グリッドを、それらが対象範囲をカバーしているか否かを確かめるために再帰的にチェックする。それらのグリッドが対象範囲とオーバーラップすれば、グリッド内の目標を、サーチ基準に合致するか否かを確かめるためにチェックする。
2004503838.tif 000002
【特許請求の範囲】
【請求項１】
空間的目標データをインデックスする方法であって、
所定の空間内の目標を特徴付ける空間的目標データを利用し、
目標のクラスタに応じてその空間を分割するステップより成る空間的目標データのインデックス方法。
【請求項２】
クラスタ限界値を設定し、
空間をレベル１のグリッドで取り囲み、
レベル１のグリッドのクラスタと、クラスタ限界値との比較結果に応じて、レベル１のグリッドを第２世代のグリッドに分割し、
第２世代またはそれに続く世代のグリッドのうちの少なくとも１つの世代の目標と、クラスタ限界値との比較結果に応じて、第２世代のグリッドの少なくとも１つのグリッドをそれに続く世代のグリッドに再帰的に分割するステップをさらに含む請求項１の方法。
【請求項３】
比較は、第２世代及びそれに続く世代のグリッドの各々のグリッドの目標と、クラスタ限界値との間で行なわれる請求項２の方法。
【請求項４】
グリッドはそれに続く世代の２ｎ個の等しいサイズのグリッドに分割され、ｎは整数である請求項３の方法。
【請求項５】
ｎは、空間的目標の空間的次元の最大数である請求項４の方法。
【請求項６】
ｎは、２または３に等しい請求項５の方法。
【請求項７】
所定の空間内の目標を特徴付ける空間的目標データを利用し、
目標のクラスタに応じてその空間を分割するステップをコンピュータに実行させるコンピュータにより実行可能な命令を有するコンピュータにより読み取り可能なメディア。
【請求項８】
クラスタ限界値を設定するか、または入力として受け取り、
空間をレベル１のグリッドで取り囲み、
そのグリッドを、少なくとも１つの次の世代のグリッドの目標と、クラスタ限界値との比較結果に応じて、少なくとも１つの次の世代のグリッドに分割するステップをコンピュータに実行させるコンピュータが実行可能な命令を有する請求項７のコンピュータにより読み取り可能なメディア。
【請求項９】
比較は、次に続く世代の各グリッドの目標と、クラスタ限界値との間で行なわれる請求項８のコンピュータにより読み取り可能なメディア。
【請求項１０】
親グリッドはそれに続く世代の２ｎ個の等しいサイズのグリッドに分割され、ｎは整数である請求項９のコンピュータにより読み取り可能なメディア。
【請求項１１】
ｎは２に等しい請求項１０のコンピュータにより読み取り可能なメディア。
【請求項１２】
ｎは３に等しい請求項１０のコンピュータにより読み取り可能なメディア。
【請求項１３】
メモリー及びプロセッサーを有するコンピュータと組み合わせて用いる請求項７のコンピュータにより読み取り可能なメディア。
【請求項１４】
メモリー及びプロセッサーを有するコンピュータと組み合わせて用いる請求項８のコンピュータにより読み取り可能なメディア。
【請求項１５】
空間的目標データをサーチする方法であって、
空間的目標のクラスタに応じてグリッド内でインデックスされた空間的目標データを利用し、
グリッドが対象範囲をカバーするか否かを再帰的にチェックし、
もしカバーすれば、グリッド内の目標がサーチ基準に合致するか否かチェックするステップより成る空間的目標データのサーチ方法。
【請求項１６】
サーチは、サーチ基準に合致する目標を検索する請求項１５の方法。
【請求項１７】
サーチの検索結果をグラフィックディスプレイ上に表示する請求項１６の方法。
【請求項１８】
グラフィックディスプレイはＧＰＳスクリーンである請求項１７の方法。
【請求項１９】
ＧＰＳスクリーンは、ＧＰＳ装置の現在位置を表示する請求項１８の方法。
【請求項２０】
グラフィックスディスプレイはビデオモニターである請求項１７の方法。
【請求項２１】
空間的目標のクラスタに応じてグリッド内でインデックスされた空間的目標データを利用し、
グリッドが対象範囲をカバーするか否かを再帰的にチェックし、
もしカバーすれば、グリッド内の目標がサーチ基準に合致するか否かチェックするステップをコンピュータに実行させるコンピュータにより実行可能な命令を有するコンピュータにより読み取り可能なメディア。
【請求項２２】
メモリー、プロセッサー及びディスプレイを有するコンピュータと組み合わせて用いる請求項２１のコンピュータにより読み取り可能なメディア。
【請求項２３】
全地球測位装置と組み合わせて用いる請求項２２のコンピュータにより読み取り可能なメディア。
【請求項２４】
車両と組み合わせて用いる請求項２３のコンピュータにより読み取り可能なメディア。
【請求項２５】
車両と、
空間的目標のクラスタに応じてグリッド内でインデックスされた空間的目標データを利用し、グリッドが対象範囲をカバーするか否かを再帰的にチェックし、もしカバーすれば、グリッド内の目標がサーチ基準に合致するか否かチェックするステップをコンピュータに実行させるコンピュータにより実行可能な命令を有するコンピュータにより読み取り可能なメディアと、
空間的目標データのクラスタに応じてグリッド内にインデックスされた空間的目標データと、
メモリーとプロセッサーとを有するコンピュータと、
全地球測位システムの装置と、
位置を示すように構成したディスプレイとより成る車両。
【請求項２６】
さらにルートマネジャーを有する請求項２５の車両。
【発明の詳細な説明】
【０００１】
【発明の背景】
【０００２】
【発明の分野】
本発明は、データのインデックス及び検索に関し、さらに詳細には、空間的目標データのインデックス方法及びインデックスされたデータのサーチ方法に関する。
【０００３】
【従来技術の問題点】
地図は、道路、河川、公園、地政学的領域などのような多量の地理的特徴部分より成る。ベクトルマップは、全ての地理的特徴部分をデジタル化し、デジタル検索可能なメディアに記憶した、記述的マップのデジタル化バージョンである。デジタル化したマップデータを含むベクトルマップまたはデータベースは、Ｎａｖｉｇａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｉｅｓ Ｃｏｒｐｏｒａｔｉｏｎ ｉｎ Ｒｏｓｅｍｏｎｔ， ＩｌｌｉｎｏｉｓまたはＥｔａｋ， Ｉｎｃ．， ｉｎ Ｍｅｎｌｏ Ｐａｒｋ， Ｃａｌｉｆｏｒｎｉａから購入できる。デジタル化された特徴部分として、例えばその名前のような非空間的属性だけでなく、座標形式（緯度及び経度）のその空間的情報を記録することができる。マップをデジタル化すると、多量のデータが発生する。従って、この全てのデータをサーチするには、かなりの大きさのＣＰＵパワーと、処理時間とが必要である。この空間的目標データを効率的にサーチするには、インデックスによりサーチできるようにデータをインデックスすることが望ましい。
【０００４】
空間的目標データは、ベクトルマップにおけるように二次元空間、または太陽系または銀河系マップのような三次元空間を特徴付けることができるだけでなく、四次元以上よりなる他の多次元空間の特徴付けも可能である。画定される空間は、所望の次元を有し、実行するサーチまたは記憶またはインデックスするデータによって境界付けられた空間である。
【０００５】
空間的目標データをインデックスするには、２つのありふれた方法がある。第１のデータインデックス方法は、データをインデックスアレイ（または、リスト）に記憶する方法である。インデックスアレイをサーチして所望の目標を発見するには、アレイ内の全ての目標をサーチしなければならず、多量のＣＰＵ時間が必要である。
【０００６】
空間的目標データのインデックスに常用される第２の方法は、空間的目標を含む空間に、全てのグリッドが同一サイズを有するグリッドシステムを適用するものである。このグリッド方式では、適当なグリッドサイズの決定が容易でない。グリッドが大きすぎると、多くの目標を取りこんでしまい、インデックスアレイ方式と比べてもサーチ時間を多量に節約できない。グリッドが小さすぎると、グリッド構造のサポートに多くのコンピュータメモリが必要となり、境界を跨る空間的目標が多くなる。従来技術のグリッド方式は、対象となる空間内の目標密度のばらつきには何の考慮も払っていない。例えば、田舎の領域をカバーする従来技術のグリッドセルは、都会の領域を包含する同じグリッドセルよりもその中に含まれる目標の数は少ない。この技術分野では、インデックスされたデータの迅速なサーチを可能にするデータインデックス方法が求められている。
【０００７】
従って、本発明の主要目的は、従来技術の問題点及び欠点を解消する空間的目標データのインデックス方法を提供することにある。
【０００８】
本発明の別の目的は、分布する空間的目標のクラスタを表わすデータに応じて空間を分割する方法を提供することにある。
【０００９】
本発明のさらに別の目的は、空間をクオッドツリー（ｑｕａｄｔｒｅｅｓ）の階層に基づき分割する方法を提供することにある。
【００１０】
本発明のさらに別の目的は、本発明の空間的目標インデックス方法と共に使用可能なサーチ方法を提供することにある。
【００１１】
本発明の上記及び他の目的、利点及び特徴は、添付図面を参照しながら以下の詳細の説明及び特許請求の範囲を読むと明らかになるであろう。
【００１２】
【発明の概要】
本発明は、所定の空間内の目標を特徴付ける空間的目標データを利用し、目標のクラスタに応じてその空間を分割するステップより成る空間的目標データのインデックス方法を包含する。
【００１３】
本発明は、空間的目標のクラスタに応じてグリッド内でインデックスされた空間的目標データを利用する、空間的目標データのサーチ方法を包含する。グリッドは対象範囲をカバーするか否かを再帰的にチェックし、もしカバーすれば、グリッド内の目標がサーチ基準に合致するか否かチェックする。
【００１４】
本発明は、所定の空間内の目標を特徴付ける空間的目標データを利用し、目標のクラスタに応じてその空間を分割するステップをコンピュータに実行させるコンピュータにより実行可能な命令を有するコンピュータにより読み取り可能なメディアを包含する。
【００１５】
【実施例の詳細な説明】
本発明を、地図に見られるような二次元の空間的目標データに関連して説明する。空間的目標データとは、河川や道路のような物理的目標を特徴付けるデジタル化されたデータのことである。しかしながら、本発明の方法は二次元の空間的データに限定されない。その原理は、単一次元の目標データだけでなく、三次元またはそれ以上の次元の目標にも適用可能であることを理解されたい。本発明の方法は、ディスプレイスクリーンを有し、地図データを表示するコンピュータスクリーンと共に使用されるＧＰＳ受信機に特に有用である。
【００１６】
図１は、本発明の方法を示すフローチャートである。第１のステップでは、クラスタ限界値を設定する。クラスタとは、所与の領域または体積部内の空間的目標の密度のことである。クラスタ限界値は、所与のグリッド内に存在可能な目標の数を制限する。クラスタ限界値は、空間的目標データのタイプ、ランダムアクセスメモリ（ＲＡＭ）のサイズ、目標が表示されるスクリーンのサイズ及び解像度（ピクセルサイズ）、ビデオ能力、視野スケール及び特定の用途のような多くの変数に応じて可変である。
【００１７】
クラスタ限界値を設定した後、レベル１（または、第１世代）のグリッドを作成する。このレベルの１のグリッドは、対象となる地理的領域を含む。例えば、対象となる地理的領域を、アメリカ合衆国とする。その場合、レベル１のグリッドは、アメリカ合衆国を包含する。目標データは、デジタル化された地図データであろう。レベル１のグリッド内の目標の数を、クラスタ限界値と比較する。目標の数がクラスタ限界値を超えると、レベル１のグリッド（親）を４つの低レベルのグリッド（子供）に分割する。後続レベルのグリッドをそれぞれ、グリッドのその次の世代と呼ぶ。レベル１のグリッド内の目標の数がクラスタ限界値より小さいかそれに等しい場合、空間的目標をレベル１のグリッドでインデックスする。
【００１８】
レベル１のグリッド内の目標の数がクラスタ限界値を超えると判定された場合、レベル１のグリッド（親）を、レベル２（または、第２世代）の４個のグリッド（子供）に分割し、レベル１のグリッドの目標を第２のレベルのグリッドへ下降させる。各第２レベルのグリッド内の目標の数を、クラスタ限界値と比較する。目標の数がクラスタ限界値より大きい第２レベルのグリッド（親）はそれぞれ、さらに４個の第３レベルのグリッド（子供）へ分割する。このプロセスは、全てのグリッドがクラスタ限界値より少ない目標を含むようになるまで再帰的に継続する。図１の特定の詳細事項を、図３を参照してさらに詳細に説明する。
【００１９】
図２は、クワッドツリー構造に基づき空間を分割する方法をグラフィック表示する概略図である。レベル１のグリッド１０は、興味対象としての領域を包含している。レベル１のグリッド１０は、４個のグリッド１２、１４、１６、１８に分割される。これら４個のグリッド１２、１４、１６、１８は、レベル２（または、レベル２または第２世代）のグリッドを構成する。図２では、連続する各世代の子供のグリッドを１つだけ示す。
【００２０】
第２レベルのグリッド１２の１つは、さらに、第３レベルの４個のグリッドに分割する。第３レベルのグリッド２０のうちの１つのグリッドはさらに、第４レベルの４個のグリッドに分割する。レベル４のグリッド２２は、空間的分割の最後のものである。
【００２１】
図３は、図１の方法の数値例を示す概略図である。図３の各グリッド内の数字は、各グリッド内の目標の数を表わす。例えば、図３において、クラスタ限界値は、任意の２０にセットされている。クラスタ限界値のセットは、図１に示す第１のステップで行う。
【００２２】
レベル１のグリッド３０は、興味対象の地理的領域、例えば、アメリカ合衆国を包含する。レベル１のグリッド３０内には１００個の目標が存在する。これはクラスタ限界値を超えるため、レベル１のグリッド３０を第２レベル（または、子供）の４個のグリッドの３２、３４、３６、３８に分割する。本発明の方法は通常、コンピュータプログラムにより実施するため、グリッドのさらなる分割が必要であるか否かをチェックするには多数の方法がある。グリッド内の目標の総数をカウントした後、クラスタ限界値と比較することができる。グリッド内の全ての目標をカウントするのではなくて、目標のカウントは、目標の数がクラスタ限界値を超えるまで行い、その時点でグリッドを分割することができる。本発明の方法は、Ｃ＋＋のような多くのコンピュータ言語での実施が可能である。
【００２３】
親のグリッドは必ず４個の子供グリッドに分割しなくてもよいことを理解されたい。子供のグリッドを異なる数にしてもよい。例えば、親のグリッドを２個の子供のグリッドに分割することが可能である。好ましい方法は、親のグリッドを、２ｎ個の等しいサイズの子供グリッドに分割することであるが、ｎは目標の空間的次元の最大数である。大部分の状況では、目標は二次元である。しかしながら、本発明は一次元の目標または三次元またはそれ以上の次元の目標に適用可能であることがわかるであろう。
【００２４】
図３を再び参照して、レベル１のグリッド３０の１００個の目標は、第２レベルのグリッド３０Ａへ下降させて、それぞれの子供グリッド３２、３４、３６、３８となる。第２レベルのグリッド３２、３４、３６、３８はそれぞれ、３６個、１５個、１７個及び３２個の目標を包含する。
【００２５】
それぞれの目標を包含する第２レベルのグリッドを作成すると、第１の第２レベルのグリッド３２内の目標の数をクラスタ限界値と比較する。グリッド３２内には３６個の目標がある。これはクラスタ限界値を超えているため、第２レベルのグリッド３２を第３レベルの４個のグリッド４０、４２、４４、４６に分割する。第２グリッドのレベル３２の目標を、グリッド３０Ｂ内のこれらの第３レベルのグリッドに下降させる。
【００２６】
次に、第３レベルの第１のグリッド４０について質問すると、グリッド４０内の目標の数２２はクラスタ限界値を超えている。従って、グリッド４０はグリッド３０Ｃに分割されて、４個の第４レベルのグリッド４８、５０、５２、５４となる。第３レベルのグリッド４０からの目標は、第４レベルのグリッド４８、５０、５２、５４に下降する。
【００２７】
第１の第４レベルのグリッド４８をチェックすると、目標の数４はクラスタ限界値より低いことがわかる。図１のフローチャートから分かるように、次のステップは、同じ世代及び同じ系列の全てのグリッドをチェックしたか否かを調べることである。同じ系列とは、「先祖」のグリッドからの直系グリッドのことである。同じ世代及び同じ系列の現在のグリッドは、第４レベルのグリッド４８、５０、５２、５４である。これらのグリッドは全てをチェックしていない。従って、図１のフローチャートから、次のステップは、グリッド５０をチェックする。
【００２８】
グリッド５０の目標の数、８個は、クラスタ限界値より少ない。グリッド５２、そしてその後、グリッド５４を同様にチェックする。各グリッド５２、５４内の目標の数は、クラスタ限界値より少ない。グリッド５４をクラスタ限界値と比較したら、同じ世代及び同じ系列のグリッドを全てチェックしたことになる。図１から、次のチェックは、レベル１のグリッドに到達したか否かである。レベル１のグリッドに到達していないため、１レベルまたは世代だけ上方へ、第３レベル、この例ではグリッド３０Ｂへ移動して、第３レベルの次のグリッドをチェックする。
【００２９】
第３のレベルの次のグリッドはグリッド４２である。このグリッド４２は８個の目標を有するため、その値はクラスタ限界値より小さい。次いで、グリッド４４、４６をチェックする。各グリッド４４、４６の目標の数は、クラスタ限界値より小さい。
【００３０】
グリッド４６をチェックした後、レベル１のグリッドにないため、１レベル上の第２レベルのグリッド３０Ａへ移動する。第２レベルの全てのグリッドのチェックは終了していない。第２のレベルの次のグリッド３４をチェックする。グリッド３４の目標の数は１５で、クラスタ限界値より小さいため、グリッド３４のさらなる分割は不要である。
【００３１】
現在のレベルの次のグリッド３６は、クラスタ限界値より小さい１７個の目標を有する。グリッド３６はさらに分割する必要はない。グリッド３４及び３６のチェックは、図３の例においてグリッド３０Ｃにおいて行なう。
【００３２】
次に、グリッド３８をチェックする。目標の数３２はクラスタ限界値を超えているため、グリッド３８をグリッド３０Ｄの第３レベルの４個のグリッド５６、５８、６０、６２へ分割する。これらの各グリッド５６、５８、６０、６２を次々にチェックするが、それらはいずれもクラスタ限界値よりも少ない数の目標を有する。
【００３３】
空間全体のチェックを確実に行なうために、この方法は、レベル１のグリッドに到達するまで上方へ進む。グリッド６２をチェックした後、１レベルだけ上のグリッド３０Ａへ移動する。レベル２のグリッド３０Ａの全てのグリッドをチェックした。従って、この方法は１つだけ上のレベルへ移動する。１つだけ上のレベルに移動すると、レベル１のグリッド３０へ来る。レベル１のグリッドのチェックを終わると、この方法は終了する。
【００３４】
図１の方法により得られると同じ結果を得るためのコンピュータプログラムを実行する方法には他のものがあることが、同業者にとって自明であろう。例えば、次の系列をチェックする前に１つの系列を完了するように上方及び下方に移動するのではなくて、世代間でグリッドをチェックしてもよい。従って、第３世代の任意のグリッドの問い合わせを行なう前に、第２世代の全てのグリッドの問い合わせをして、分割を行ってもよい。加えて、終了前にトップに戻るのではなくて、別の方法によりその空間を全て分割したか否かをチェックすることもできる。
【００３５】
グリッド内の目標の総数は、分割を指示するものか否かをチェックするために必ずしも使用する必要はないことも理解すべきである。当該技術分野で知られているように、目標は、その目標の地理的特徴に基づき積層状に記憶されることが多い。例えば、河川の目標を含む層があり、州間ハイウェイの目標を含む異なる層もある。ユーザーは、所与の領域内の全ての州間ハイウェイを探したい場合があろう。従って、図１の方法により、全ての州間ハイウェイをインデックスすることができる。
【００３６】
図３を再び参照すると、本発明による目標データのインデックス方式によりサーチの利点の一部が得られることがわかる。一例として、グリッド６２にある地点に近い全てのハイウェイを見つけたいと仮定する。この例では、この地点に近いハイウェイは、グリッド３８により境界付けられた領域内に存在する。インデックスされたデータをサーチするにあたり実行する第１のステップは、レベル１のグリッド３０がこの対象となる領域を包含しているか否かをチェックすることである。この場合、グリッド３０は、グリッド３８により囲まれた領域を含んでいる。
【００３７】
レベル１のグリッド３０がこの対象領域をカバーすると判断した後、次のステップは、次の何れの世代のグリッドがグリッド３８により囲まれる領域を含んでいるかを突き止めることである。グリッド３２、３４、３６を次々にチェックする。これらのグリッドは何れも対象領域をカバーしていない。これらのグリッドは対象範囲内にないため、これらのグリッド内の目標またはそれらの次の世代の目標の何れもチェックする必要はない。次に、グリッド３８をチェックすると、それは対象領域をカバーしている。しかしながら、目標は次の世代グリッド５６、５８、６０、６２へ降りてきているため、グリッド３８には目標が存在しない。
【００３８】
グリッド５６を、それが対象領域をカバーするか否かを確かめるためにチェックする。ＹＥＳであるため、このグリッド内の目標を、その中の任意の目標がサーチ基準を満たすか、即ち、この例ではハイウェイであるか否かチェックする。グリッド５６内の全てのハイウェイは、このサーチにより検索される。同様に、グリッド５８、６０、６２を、それらが対象範囲内にあるか否かを確かめるためにチェックする。それら全てがそうであるため、これらのグリッド５８、６０、６２内の全ての目標をチェックし、これらのグリッド内のハイウェイがサーチにより検索される。
【００３９】
グリッド方式のデータ内でのサーチは再帰的であることがわかるであろう。各グリッドまたは４分の１象限を、対象範囲をカバーするか否かチェックする。もしそのグリッドが対象範囲をカバーしておれば、そのグリッド内の目標をチェックする。グリッドをそれに続く世代にさらに分割する場合、それに続く世代の各グリッドを、対象範囲をカバーするか否か確かめるためにチェックする。サーチプロセスは、（１）グリッドが対象範囲内にあるか否か、（２）その範囲をカバーするグリッド内の目標がサーチ基準に合致するか否かをチェックする再帰的プロセスである。従って、対象範囲内にないグリッドについては、それらの次の世代をチェックしない。従って、チェックしなければならない目標が少なくなり、目標のサーチにかかる時間が短くなる。
【００４０】
当業者にとっては、クラスタを利用してインデックスされたデータをサーチする方法は、全地球測位システム（ＧＰＳ）及び所望の地点を表示する装置を備えた車両に容易に使用できることがわかるであろう。さらに、当業者にとっては、これらをルートマネジャーと組み合わせると、運転者または輸送エンジニアが表示された地形を辿るのを支援できることが容易に明らかになるであろう。これは、水路、陸路または空路、全ての交通手段を含むものであり、それらに限定されない。公共交通機関、緊急事態への応答または公衆の安全、商用の輸送または配達及び軍事用輸送を包含するものである。
【００４１】
ルートマネジャーは、位置により指示されたトリップのルートを決定する。
【００４２】
本発明を、特定の実施例につき説明した。しかしながら、本発明は図示説明した実施例に限定されるものではない。本発明は、その精神及び範囲内に含まれる全ての変形例、設計変更及び等価例を包含するものと意図されている。
【図面の簡単な説明】
【図１】
図１は、本発明による空間的目標データのインデックス方法を示すフローチャートである。
【図２】
図２は、本発明による方法による空間の分割態様を示す概略図である。
【図３】
図３は、図１の方法による空間の分割を、数値を用いた例で示す概略図である。
【図１】
2004503838.tif 000003
【国際公開パンフレット】
2004503838.tif 000004
2004503838.tif 000005
2004503838.tif 000006
2004503838.tif 000007
2004503838.tif 000008
2004503838.tif 000009
2004503838.tif 000010
2004503838.tif 000011
2004503838.tif 000012
2004503838.tif 000013
2004503838.tif 000014
2004503838.tif 000015
2004503838.tif 000016
2004503838.tif 000017
2004503838.tif 000018
2004503838.tif 000019