ｋ最近傍検索方法、ｋ最近傍検索プログラム及びｋ最近傍検索装置
【課題】空間データベースの検索時間を短縮しながら、検索処理中のメモリ使用量を抑制することを目的とする。
【解決手段】多次元の地点データから空間インデックスを作成するDBMSで任意地点から距離の近い上位ｋ件の地点データを検索するｋ最近傍検索方法であって、質問地点と質問件数を検索条件に設定し、質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定し、最下位枝の判定で最近領域が最下位枝となると、質問地点と最近領域の子領域との距離を計算し、領域距離計算の計算対象となった分割領域の情報を保持し、最近領域を取得し、最下位枝の判定で最近領域が中間枝となると質問地点と最近領域に内包される地点データの距離を計算し、距離計算の計算対象となった地点データを保持し、検索条件を満たす時点で検索処理を終了させ、DBMSから保持した地点データのレコードを結果として取得する。
【解決手段】多次元の地点データから空間インデックスを作成するDBMSで任意地点から距離の近い上位ｋ件の地点データを検索するｋ最近傍検索方法であって、質問地点と質問件数を検索条件に設定し、質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定し、最下位枝の判定で最近領域が最下位枝となると、質問地点と最近領域の子領域との距離を計算し、領域距離計算の計算対象となった分割領域の情報を保持し、最近領域を取得し、最下位枝の判定で最近領域が中間枝となると質問地点と最近領域に内包される地点データの距離を計算し、距離計算の計算対象となった地点データを保持し、検索条件を満たす時点で検索処理を終了させ、DBMSから保持した地点データのレコードを結果として取得する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意の多次元地点データから距離の近い上位ｋ件の地点データを、厳密かつ高速に検索するｋ最近傍検索技術に関する。特に、地図情報管理を想定し、2次元、または3次元空間の地点データを検索対象とする。
【背景技術】
【０００２】
これまでに、地図情報管理を目的とし、空間検索機能を有するデータベース管理システムが開発されている。このようなデータベース管理システムを空間データベースと呼ぶ。空間データベースは、地物を点、線、面などの図形要素と、地物の内容を示す文字や数値などの属性要素を管理できる。空間検索機能は、任意の範囲に内包、または接触する地物を取得する範囲指定検索を実現する。範囲指定検索の高速化のため、四分木、グリッドファイル、R−treeなどの空間インデックス技術が既に提案されている。空間インデックス技術は、空間領域における地物の配置分布に応じて、空間領域を分割する。
【０００３】
従来、空間データベースは、エンタープライズのアプリケーション向けに開発されてきた。ところが、近年、空間データベースが組込機器のアプリケーション向けにも開発されてきている。空間データベースを必要とする組込機器は、カーナビゲーション装置やＰＮＤ（Personal Navigation System）などの地図情報を管理する機器である。カーナビゲーション装置は、現在地や目的地などユーザの指定した地点付近の飲食店や駐車場などの地点データを検索する機能をもつ。その際、ユーザの指定した地点（以下、質問地点と呼ぶ）から距離の近い上位ｋ件（以下、質問件数と呼ぶ）の地点データを空間データベースから取得するｋ最近傍検索が知られている。
【０００４】
従来の空間データベースにおけるｋ最近傍検索は、範囲指定検索を用いて、実現される。従来のｋ最近傍検索では、まず、質問地点を中心とした任意の大きさをもつ検索範囲が設定される。検索範囲に含まれる地点データが質問件数以上ならば、質問地点と当該地点データとの距離を計算する。そして、距離の短い順に当該地点データをソートし、距離の短い上位ｋ件の地点データを、検索結果として取得する。一方、検索範囲に含まれる地点データが質問件数未満ならば、質問件数以上になるまで、検索範囲が大きく設定され、範囲指定検索が繰り返される。例えば、グリッドファイルによる範囲指定検索を用いた方法（例えば、特許文献１参照）や、四分木による範囲指定検索を用いる方法（例えば、特許文献２参照）などが知られている。
【特許文献１】特開２００３−２４２１５１号
【特許文献２】米国特許第６、８７９、９８０号
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記従来技術を組込機器に適用すると、以下のような問題があった。
【０００６】
まず、第１の問題として、ディスクアクセスと演算負荷により、検索時間が増大する。
【０００７】
一般に組込機器は小容量の主記憶装置を備えるため、検索実行時に空間インデックスのページを外部記憶装置から主記憶装置に読込むディスクアクセスが発生する。そのため、組込機器では、検索範囲に含まれる地点データの件数が非常に多い場合、ディスクアクセスが頻発し、検索時間が長くなる。特に、この問題は、地点データの存在密度が高い地域で、検索範囲が大きい場合に発生する。一方、エンタープライズ用のサーバは、大容量の主記憶装置を備えている。そのため、サーバは、空間インデックスの大部分のページを予め主記憶装置に格納できる。この場合、検索範囲に含まれる地点データが多い場合でも、ディスクアクセスが頻発せず、検索時間が長くならない。
【０００８】
また、組込機器は低速な中央処理装置を備えるため、質問地点と地点データまでの距離計算や、距離によるソート処理等の演算負荷が検索時間に影響を与える。特に、検索範囲に含まれる地点データの件数が非常に多い場合、演算負荷が増大し、検索時間が長くなる。一方、エンタープライズ用のサーバは、高速な中央処理装置を備えるため、演算負荷による検索時間の影響は小さいと言える。
【０００９】
上記では、検索範囲に含まれる地点データの件数が非常に多い場合に、ディスクアクセスと演算負荷の面で、問題があることを述べた。また、検索範囲に含まれる地点データが質問件数未満の場合でも、質問件数を満たすまで、検索処理を繰り返すため、上記と同様の問題が発生する。
【００１０】
この問題を解決するため、空間データベースが、質問件数と質問地点付近の地点データの存在密度に基づき、検索範囲を適切な大きさに設定する方法が考えられる。しかし、この方法は、組込機器に適切な方法とは言えない。それは、組込機器にとって、地点データの挿入や削除が発生する状況において、地点データの存在密度の管理は、負荷の大きい処理になるためである。
【００１１】
以上より、組込機器で従来の範囲指定検索を用いたｋ最近傍検索は、検索時間が増大する、という課題が生じる。
【００１２】
次に、第２の問題として、検索実行中のメモリ使用量が多くなる場合、検索処理を実行できない。または検索時間が長くなる。
【００１３】
従来技術では、検索範囲に含まれる全ての地点データを主記憶装置上に保持し、質問地点からの距離を用いて、ソートする。そのため、検索範囲に含まれる地点データが多いと、メモリ使用量が増大する。この場合、組込機器は小容量の主記憶装置を備えるため、従来技術を実行できない可能性がある。
【００１４】
この問題を解決するため、主記憶装置のメモリ空間から溢れた地点データを、外部記憶装置に退避する方法がある。この方法では、地点データのソート処理で、ディスクアクセスが発生するため、検索時間が長くなる。
【００１５】
また、第３の問題として、従来のｋ最近傍検索と属性指定検索を組合せた場合、件数がk件未満の不正確な検索結果になる可能性がある。
【００１６】
ｋ最近傍検索と属性指定検索の組合せは、多種類の地点データを含むテーブルに対して、実行される。例えば、カーナビゲーション装置が管理する施設テーブルには、レストラン、駐車場、ガソリンスタンドなどが含まれる。さらに、施設の種類がレストランの場合、施設テーブルには、日本料理、イタリア料理、フランス料理など、細かい種別が含まれる。その際、ユーザは、質問地点と質問件数に加え、地点種別を設定し、ｋ最近傍検索を実行する。通常の空間データベースでは、テーブルが属性情報と座標情報を別々の列として管理する。そのため、ＳＱＬ（Structured Query Language）のWHERE句で、ｋ最近傍検索と属性指定の条件をAND演算子で結合する。
【００１７】
このとき、k最近傍検索で質問件数分の結果が得られても、属性指定で、質問件数未満に絞り込まれる場合がある。これは、ｋ最近傍検索で得られた地点データの集合と、属性指定で得られた地点データの集合で、積集合を取るためである。
【００１８】
この問題を回避するため、エンタープライズ用のデータベース管理システムでは、質問件数をk件より多く設定する方法が採用されている。つまり、検索結果が属性指定で絞り込まれても、k件以上残る仕組みになっている。しかし、組込機器では、この方法は適切ではない。それは、質問件数が多い場合、必要な空間インデクスのページ数が増え、小容量の主記憶装置を備える組込機器では、ディスクアクセスが頻発し、検索時間が長くなるためである。一方、エンタープライズ用のサーバは大容量の主記憶装置を備えている。そのため、予め空間インデクスのページを主記憶装置に格納しておけば、質問件数が多くても、ディスクアクセスが頻発しない。
【００１９】
さらに、第４の問題として、上位k件の地点データが質問地点の付近に存在しない場合、検索時間が長くなる。
【００２０】
従来のｋ最近傍検索では、質問件数が満たされるまで、検索範囲が拡大される。質問地点の付近に所望の地点データが存在しない場合、検索結果が質問地点から数十キロも離れた地点データを含む可能性がある。検索範囲が拡大されると、必要な空間インデクスのページ数が増える。そのため、先に述べたように、小容量の主記憶装置を備えた組込機器では、検索時間が長くなる。
【００２１】
そこで本発明は、上記問題点に鑑みてなされたもので、空間データベースの検索時間を短縮しながら、検索処理中のメモリ使用量を抑制することを目的とする。
【課題を解決するための手段】
【００２２】
本発明は、多次元の地点データと、前記地点データを含む領域を複数の領域に分割して当該領域内に子領域を設定し、前記地点データと前記領域から枝と葉を含む木構造を作成した空間インデックスと、を含むデータベースと、前記データベースを管理するデータベース管理システムにおいて、検索の始点となる質問地点を受け付けて、前記質問地点から距離の近い上位ｋ件の質問件数の地点データを検索するｋ最近傍検索方法であって、前記質問地点と質問件数を検索条件に設定するステップと、前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定するステップと、前記最近領域が中間枝と判定されると、前記質問地点と最近領域の子領域との距離を領域距離として計算するステップと、前記領域距離の計算対象となった領域の情報を保持し、当該領域の最近領域を取得するステップと、前記最下位枝か中間枝かの判定結果で、前記最近領域が最下位枝と判定されると、前記質問地点と最近領域に内包される地点データの距離を地点距離として計算するステップと、前記地点距離の計算対象となった地点データの情報を保持するステップと、前記検索条件を満たすまで、前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定するステップ以降の検索処理を繰り返し、前記検索条件を満たした時点で前記検索処理を終了させるステップと、前記検索処理が終了した後に、前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得するステップと、を含む。
【発明の効果】
【００２３】
本発明は、範囲指定検索を用いた従来のｋ最近傍検索に比べ、空間インデックスのページへのディスクアクセス回数を削減できるため、検索時間を短縮できる。また、距離計算やソート処理の対象とする地点データを減らすため、プロセッサの演算負荷を軽減できる。さらに、検索実行中のメモリ使用量を抑制できる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の一実施形態を添付図面に基づいて説明する。
【００２５】
＜第１の実施形態＞
図１は、第１の実施形態を示し、本発明を適用するカーナビゲーション装置の一例を示すブロック図である。カーナビゲーション装置１は、演算処理を行うＣＰＵ（プロセッサ）３と、データやプログラムを一時的に格納するメモリ２と、データやプログラムを格納するストレージ装置５と、演算結果などを表示する表示装置４と、ユーザからの入力を受け付ける入力装置６と、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）衛星からの信号を受信するレシーバ１０を含んで構成される。
【００２６】
ストレージ装置５には、地図を構成する地物を点、線、面などの図形要素と、地物の内容を示す文字や数値などの属性要素を含む空間データベース１００が格納される。なお、空間データベース１００に格納された情報のうち、店舗や施設などひとつの地点の情報を地点データとする。
【００２７】
メモリ２には、空間データベース１００を管理するＤＢＭＳ（Ｄａｔａｂａｓｅ Ｍａｎａｇｅｍｅｎｔ Ｓｙｓｔｅｍ）８と、ＤＢＭＳ８を介して空間データベース１００を利用するアプリケーション９と、ＤＢＭＳ８とアプリケーション９を管理するＯＳ（オペレーティングシステム）７がロードされ、ＣＰＵ３により実行される。アプリケーション９は、レシーバ１０で受信したＧＰＳ衛星の信号から現在の位置を演算し、現在の地点データを空間データベース１００から検索し、地図情報を取得して表示装置４へ出力する。また、カーナビゲーション装置１では、入力装置６からユーザが検索の指令を受け付けると、アプリケーション９はＤＢＭＳ８を介して空間データベース１００を後述するように探索し、要求された検索結果を表示装置４に出力する。なお、ＯＳ７、ＤＢＭＳ８、アプリケーション９は記録媒体としてのストレージ装置５に格納され、カーナビゲーション装置１の起動時にメモリ２へロードされ、ＣＰＵ３によって実行される。
【００２８】
また、アプリケーション９は、ワークエリアとしてメモリ２上の領域を確保する。これらの領域は、後述する候補地点ヒープ９１、候補領域ヒープ９２、結果リスト９３等である。
【００２９】
ここで、本実施形態は、上記第１の問題と第２の問題を解決可能なｋ最近傍検索を実現する。本発明の適用範囲は、基本的に空間データの次元数と空間インデックス技術の種類によって、限定されない。本発明で利用可能な空間インデックス技術の要件は、
１．空間領域を再帰的に分割し、分割した領域の情報を記憶する枝を木構造の節とする
２．枝の領域範囲は前記枝の親の節にあたる枝の領域範囲に内包されるという階層的な構造をもつ
３．自身が小分割されない分割領域は当該分割領域が内包する地点データの情報を記憶する葉をもち、葉は木構造の最下位の節に接続していること
である。
【００３０】
以下の説明では、空間データベース１００に格納された２次元空間における地点データをカーナビゲーション装置１の検索対象とし、空間インデックス技術に四分木手法を適用する例を示す。
【００３１】
図１に示す空間データベース１００は、地図情報を構成する地点の座標と属性を格納した地点テーブル５０１と、地点テーブル５０１の索引情報を格納した空間インデックス１０１を含む。
【００３２】
まず、空間インデックス１０１は、空間データベース１００で管理する地点テーブル５０１に地点データを挿入する際に図示しない計算機によって作成される。本実施形態では、空間インデックス１０１の一例として、図４に示す領域分割テーブル４０１を採用した例を示す。また、地点テーブル５０１は、地点データの属性情報に加え、Ｘ座標とＹ座標から構成される座標情報を列に含む。例えば、カーナビゲーション装置１で管理する施設テーブルは、施設名、住所、電話番号などの属性情報と、施設の存在場所を平面直角座標系のＸ座標とＹ座標で表現した座標情報をもつことが考えられる。
【００３３】
四分木手法は、空間データベース１００への地点データの挿入に伴い、２次元空間のＸ軸とＹ軸に平行な面で４分割する。四分木手法では、一般に、分割領域で格納可能な地点データの最大個数を決め、地点データの挿入で、最大個数を超えた場合に、分割領域を４分割する。領域分割の方法には、４分割後の分割領域の面積を均等にする方法や、４分割後の分割領域内の地点データの個数をできるだけ均等にする方法などが提案されている。後者の方法は、例えば、分割対象の領域内の全ての地点データの重心座標で４分割することで、実現する。本発明のｋ最近傍検索は、領域の分割方法に依存せず、動作可能である。以下では、四分木手法のデータ構造について記載する。本発明は、空間インデックス技術の上で動作するｋ最近傍検索である。空間インデックス技術そのものに関する発明ではない。そのため、本実施例では、四分木の生成や探索の手順については公知の手法を適用すればよいので、これらの詳細な説明を省略する。
【００３４】
図２は、２次元空間内の一つの座標で位置を特定可能な地点データについて、四分木手法により空間領域２０１を階層的に分割した例を示す。空間領域２０１は分割線２０４で４分割される。各分割領域は、分割領域の識別子（領域ＩＤ）２０２をもつ。分割領域が、当該分割領域を４分割する領域をもたない場合、地点データ２０２を格納する。例えば、深さ３の分割領域３５は、地点データＧを格納する。この空間領域２０１は、多次元空間で各軸を通る面で階層的に分割した分割領域０〜３６を木構造で管理する空間インデックス１０１を構成する。
【００３５】
図３は、図２の領域分割に対応した木構造を示す。図３において、木構造の節に対応するものが枝３０１（図中円）であり、最下位の節と隣接するのが葉３０２（図中四角）である。枝３０１と分割領域は１対1の対応関係であり、枝３０１の数字は図２に示した領域ＩＤを指す。葉３０２内の英字は地点データＩＤを示す。地点データＩＤは、図２のＡ〜Ｍに対応する。実施形態の四分木手法は最下位の枝３０１が、当該枝に隣接する葉３０２の中に地点データの情報を格納する。
【００３６】
図４は、空間データベース１００の空間インデックス１０１に予め格納された分割領域テーブル４０１を示す。分割領域テーブル４０１は、四分木の枝３０１に格納される分割領域の情報を指す。図４は、分割領域テーブル４０１の属性４１１と、当該属性に対応する中間枝（図３では、分割領域０〜８に相当する）と最下位枝（図３では、分割領域２５〜２８、３３〜３６に相当する）の値を例示する。分割領域の情報は、領域ＩＤ４１２、領域範囲４１３、分割座標４１４、子領域ＩＤ４１５、子領域ポインタ４１６、葉ポインタ４１７、地点個数４１８を含む。
【００３７】
領域ＩＤ４１２は、分割領域を示す一意の識別子である。領域範囲４１３は、領域の左下頂点と右上頂点のＸ−Ｙ座標で表現する。分割座標４１４は領域を四分割した際の分割点の座標を示す。当該分割領域は、分割座標４１４を通り、かつＸ軸とＹ軸に平行な２本の直線で、４分割する。
【００３８】
子領域ＩＤ４１５は、当該領域を四分割した分割領域の識別子を示す。子領域ポインタ４１６は、子領域ＩＤ４１５が示す分割領域に対応した枝３０１を格納したストレージ装置５のアドレス値（例えば、ＬＢＡ（Logical Block Address））を示す。当該枝３０１が最下位枝である場合、当該枝３０１に対応した分割領域は子領域を持たない。最下位枝に対応する分割領域の分割座標４１４、子領域ＩＤ４１５、子領域ポインタ４１６はＮＵＬＬとする。葉ポインタ４１７は、当該枝３０１に隣接する葉３０２を格納したストレージ装置５のアドレス値を示す。地点個数４１８は、当該枝３０１に隣接する葉３０２が格納する地点データの個数を示す。当該枝３０１が中間枝である場合、当該枝３０１の葉ポインタ４１７はＮＵＬＬ、地点個数は０になる。
【００３９】
図５は、空間データベース１００の空間インデックス１０１に予め格納された地点テーブル５０１を示す。地点テーブル５０１は四分木の葉３０２に記憶され、地点データの情報を示す。この地点データは、葉３０２に隣接する最下位枝に対応する分割領域が内包する地点データである。各地点データの座標情報は、地点ＩＤ５１１、地点座標５１２、地点ポインタ５１３を含む。地点ＩＤ５１１は、当該地点データの一意の識別子である。地点座標５１２は、当該地点データの位置を特定する座標を示す。地点ポインタ５１３は、当該地点データに該当するレコードを格納したストレージ装置５のアドレス値を示す。
【００４０】
図６は、カーナビゲーション装置１のＣＰＵ３で実行されるｋ最近傍検索の手順を示すフローチャートである。この処理は、ＣＰＵ３で実行されるアプリケーション９が、入力装置６から質問地点を受信すると開始される。
【００４１】
ｋ最近傍検索の処理が開始されると、まず、初期設定部１１１ではＣＰＵ３が、質問地点や質問件数の設定及び候補領域管理部１１３や候補地点管理部１１６で利用するメモリ２の領域確保を行う（Ｓ１０１）。
【００４２】
次に、最下位枝判定部１１２では、最近領域が当該領域をさらに４分割する領域をもつか、つまり子領域をもつか否かを判定する（Ｓ１０２）。最近領域とは、結果候補に入るか否かを調査していない地点データを含む分割領域の中で、質問地点に距離が最も近い領域を示す。Ｓ１０２の条件を満たさない場合、最近領域が最下位枝でないと判定される。この場合、領域距離計算部１１３が、質問地点と最近領域の子領域との最短のユークリッド距離（領域距離ｄ）を計算する（Ｓ１０３）。
【００４３】
そして、候補領域管理部１１４が、最近領域の子領域を候補領域として、子領域の情報を記録する（Ｓ１０４）。候補領域とは、結果候補に入るか否かを調査していない地点データを含む分割領域を示す。その後、候補領域管理部１１４が、候補領域の中から領域距離ｄに基づき、次の最近領域を選択する（Ｓ１０５）。
【００４４】
一方、上記Ｓ１０２の条件を満たす場合、現在着目している最近領域が最下位枝であると判定される。この場合、地点距離計算部１１５が、質問地点と最近領域に含まれる地点データとの距離（地点距離ｄ’）を計算する（Ｓ１０６）。
【００４５】
次に、候補地点管理部１１６は、求めた地点距離ｄ’に基づき、質問地点に距離が近い上位ｋ件の地点データの情報を記録する（Ｓ１０７）。そして、終了判定部１１７は、候補領域内の地点データが候補になり得ないか否かを判定する（Ｓ１０８）。この終了条件を満たさない場合、Ｓ１０５の処理へ進み、検索処理を続行する。
【００４６】
一方、終了条件を満たす場合、結果取得部１１８は、候補地点管理部１１６が記憶した地点データに対応する結果レコードを取得する（Ｓ１０９）。
【００４７】
上記処理を終了条件が成立するまで繰り返すことで、検索結果を空間データベース１００から取得する。
【００４８】
図７は、ｋ最近傍検索の初期設定（Ｓ１０１：初期設定部１１１）の詳細な手順を示すサブルーチンのフローチャートである。
【００４９】
図７の初期設定処理は、図６の初期設定部１１１によって実行される。まず、初期設定部１１１は、質問地点と質問件数を、ｋ最近傍検索の入力値として設定する（Ｓ６０１）。質問地点と質問件数は、例えば、上記入力装置６から受け付けた値である。なお、質問地点は、入力装置６から検索指示を受け付けた時点のユーザの現在位置を用いても良い。
【００５０】
次に、初期設定部１１１は、メモリ２から、候補領域を記憶するメモリ領域をヒープ構造（以下、候補領域ヒープ９２）で確保する（Ｓ６０２）。ヒープ構造を用いる理由は、候補領域管理部１１４が最近領域の子領域の情報を記録する（Ｓ１０４）際の挿入操作と、次の最近領域を選択する際（Ｓ１０５）の選択操作で、効率の良いデータ構造だからである。
【００５１】
候補領域ヒープ９２は、領域ＩＤ４１２、領域情報ポインタ、領域距離ｄから構成される要素を格納する。領域情報ポインタは、当該領域に対応する枝３０１を格納したストレージ装置５のアドレス値を示す。領域距離ｄは、質問地点と当該領域までの最短距離を示す。候補領域ヒープ９２は木構造で管理される。候補領域ヒープ９２は、要素の挿入や削除があっても、各要素の領域距離ｄが、当該要素の子要素の領域距離ｄより小さいか等しいというヒープ条件を満たす。つまり、候補領域ヒープ９２の根要素は、最小の領域距離ｄをもつ分割領域の情報を格納する。
【００５２】
初期設定部１１１は、メモリ２から、候補地点を記憶するメモリ領域をヒープ構造（以下、候補地点ヒープ９１）で確保する（Ｓ６０３）。ヒープ構造を用いる理由は、候補地点管理部１１６が上位ｋ件の地点データの情報を記録する（Ｓ１０７）際の挿入操作で、効率の良いデータ構造だからである。候補地点ヒープ９１は、地点ＩＤ５１１、地点ポインタ５１３、地点距離ｄ’から構成される要素を格納する。候補地点ヒープ９１は、要素の挿入や削除があっても、各要素の地点距離ｄ’が、当該要素の子要素の地点距離ｄ’より大きいか等しいというヒープ条件を満たす。つまり、候補地点ヒープ９１の根要素は、最大の地点距離ｄ’をもつ地点データの情報を格納する。この特徴により、候補地点がｋ件存在する状況で、ｋ＋１件目以降の地点データが候補に入るか否かを判定する場合、根要素を参照するだけで候補となるか否かを容易に判定できる。具体的には、判定対象の地点データの地点距離ｄ’が、根要素の地点データの地点距離ｄ’より小さければ、根要素の地点データに代わって判定対象の地点データが候補に入る。本操作により、メモリ上には常に上位k件の地点データのみが保持されることになり、検索実行中のメモリ使用量を抑制できる。
【００５３】
初期設定部１１１は、四分木の根にあたる領域を最近領域に設定し（Ｓ２０４）、サブルーチンを終了する。この場合、最近領域は全体の領域となる。その後、図６に示した最近領域の最下位枝判定の処理に進む（Ｓ１０２）。
【００５４】
図８は、最近領域に対する最下位枝判定（Ｓ１０２）の詳細な手順を示すサブルーチンのフローチャートである。最下位判定の処理は、最下位枝判定部（１１２）によって実行される。まず、初期設定部１１１のＳ６０４で決定した最近領域に対応する四分木の枝情報を取得する（Ｓ７０１）。枝情報は、ストレージ装置５の空間データベース１００内に予め格納されている。次に、図４に示した分割領域テーブル４０１を参照して、当該枝情報の分割領域の座標がＮＵＬＬか否かを判定する。この条件により、最近領域が最下位枝であるか否かを判定できる。当該条件を満たさず、最近領域が中間枝の場合、質問地点と最近領域の子領域との領域距離ｄを計算する処理（Ｓ１０３）へ進むため、次の処理として領域距離計算部１１３を選択する（Ｓ７０３）。当該条件を満たし、最近領域が最下位枝である場合は、質問地点と最近領域に内包される地点データとの距離を計算する処理（Ｓ１０６）に進むため、次の処理として地点距離計算部１１５を選択する（Ｓ７０４）。そして、サブルーチンを終了するとステップＳ７０３またはＳ７０４の何れかで選択した処理に分岐する。
【００５５】
図９は、領域距離計算（Ｓ１０３）の詳細な手順を示すサブルーチンのフローチャートである。領域距離計算の処理は、領域距離計算部１１３よって実行される。領域距離計算部１１３は、分割領域テーブル４０１を参照して、質問地点と最近領域の子領域との領域距離ｄを計算する。領域距離ｄの計算には、子領域の領域範囲が必要になる。子領域の領域範囲は、最近領域の枝情報の領域範囲４１３と分割座標４１４の情報から求める。ここでは、図４で示したように、最近領域の左下頂点の座標を（Ｘｍｉｎ、 Ｙｍｉｎ）、右上頂点の座標を（Ｘｍａｘ、 Ｙｍａｘ）で表現する。また、分割座標４１４を（Ｘｄｉｖ、 Ｙｄｉｖ）で示す。
【００５６】
まず、領域距離計算部１１３は、最近領域の左下子領域の領域範囲を、左下頂点の座標が（Ｘｍｉｎ、 Ｙｍｉｎ）、右上頂点の座標が（Ｘｄｉｖ、 Ｙｄｉｖ）とする（Ｓ８０１）。
【００５７】
次に、最近領域の右下子領域の領域範囲を、左下頂点の座標が（Ｘｄｉｖ、 Ｙｍｉｎ）、右上頂点の座標が（Ｘｍａｘ、 Ｙｄｉｖ）とする（Ｓ８０２）。最近領域の左上子領域の領域範囲を、左下頂点の座標が（Ｘｍｉｎ、 Ｙｄｉｖ）、右上頂点の座標が（Ｘｄｉｖ、 Ｙｍａｘ）とする（Ｓ８０３）。最近領域の右上子領域の領域範囲を、左下頂点の座標が（Ｘｄｉｖ、 Ｙｄｉｖ）、右上頂点の座標が（Ｘｍａｘ、 Ｙｍａｘ）とする（Ｓ８０４）。
【００５８】
次に、領域距離計算部１１３は、次の式（１）を用いて、左下、右下、左上、右上の子領域の領域距離ｄをそれぞれ計算する（Ｓ８０５）。
【００５９】
【数１】
【００６０】
ただし、
分割領域Ｒと質問地点（ｘ、ｙ）との距離値ｄ
分割領域Ｒの範囲： 左下座標（Ｘｍｉｎ、 Ｙｍｉｎ）、右上座標（Ｘｍａｘ、 Ｙｍａｘ）
である。
【００６１】
上記式（１）では、質問地点の座標を（x、y）、分割領域の左下頂点の座標を（Ｘｍｉｎ、 Ｙｍｉｎ）、右上頂点の座標を（Ｘｍａｘ、 Ｙｍａｘ）で表記する。式（１）は、分割領域の境界線上の点の中で、質問地点に最も近い点と、質問地点との距離ｄの二乗を示す。分割領域が質問地点を含む場合、当該分割領域の距離は０になる。
【００６２】
図１０は、上記領域距離ｄを例示したものである。質問地点１００１から図中の分割領域１、２、３、４までの各距離ｄ1、ｄ2、ｄ3、ｄ4は矢印１００２で示される。本実施形態では、式（１）で計算した距離ｄを用いる。なお、実環境では、ｄの二乗をそのまま領域距離ｄに用いて、計算負荷を軽減する方法もある。Ｓ８０６の領域距離ｄの計算後、領域距離計算部１１３は、各子領域の領域ＩＤ４１２、領域ポインタ、領域距離ｄを候補領域管理部１１４に渡す（Ｓ８０６）。これらの処理が完了するとサブルーチンを終了し、図６のステップＳ１０４に進む。
【００６３】
図１１は、最近領域の子領域情報の記録（Ｓ１０４）の詳細な手順を示すサブルーチンのフローチャートである。当該処理は、候補領域管理部１１４によって実行される。まず、候補領域管理部１１４は、領域距離計算部１１３から受け付けた子領域ＩＤ４１５、子領域ポインタ４１６、領域距離ｄから構成される候補領域ヒープ９２の要素を生成する（Ｓ１１０１）。以下のステップでは、候補領域管理部１１４が子領域を一つずつ選択する。次に、候補領域管理部１１４は、Ｓ１１０２からＳ１１０４、Ｓ１１０７のステップで、候補領域ヒープ９２の条件を満たすように、子領域の情報を挿入する。子領域の情報を挿入する操作の前に、ヒープの実現方法について説明する。
【００６４】
図１２は、候補領域ヒープ９２に適用するヒープ木１２０１を一次元配列１２０２で実現した例を示す。図１２において、ヒープ木１２０１の節１２０３内の番号は要素の識別子を示し、節付近の<>１２０４内の数値は予め設定した基準値を示す。ヒープ木１２０１は、候補領域ヒープ９２と同じヒープ条件で、根要素の基準値が最小になるように管理されている。一次元配列１２０２は、ヒープ木１２０１の深さが浅いほど、深さが同じ場合は左から順に、先頭から要素を格納する。
【００６５】
次に、図１１において、候補領域管理部１１４は、まず、要素を候補領域ヒープ９２の末尾に要素を挿入する（Ｓ１１０２）。末尾とは、一次元配列の末尾を指す。次に、候補領域管理部１１４は挿入要素が根に格納されているか判定する。根の格納位置は、一次元配列の０番目になる。
【００６６】
当該条件を満たさない場合、挿入要素の領域距離ｄが親要素の領域距離ｄより小さいか否かを判定する（Ｓ１１０４）。当該条件を満たす場合、候補領域ヒープ９２のヒープ条件を満たさないことになる。この場合、候補領域管理部１１４は、挿入要素と親要素の格納位置を交換する（Ｓ１１０７）。一次元配列では、挿入要素の格納位置がｉの場合、格納位置がｉ／２を超える最小の整数に１を差し引いた値が親要素となる。
【００６７】
ステップＳ１１０３の条件を満たした場合、またはＳ１１０４の条件を満たさなかった場合には、候補領域ヒープ９２のヒープ条件を満たすことになる。この場合、候補領域管理部１１４は、全ての子領域の情報を候補領域ヒープ９２に挿入したかを否かを判定する。当該条件を満たさなければ、Ｓ１１０１の処理へ進み、子領域の情報をヒープに挿入する。一方、当該条件を満たせばサブルーチンを終了して、図６に示す次の最近領域の選択へ処理を進める（Ｓ１０５）。
【００６８】
図１３は、最近領域の選択（Ｓ１０５）の詳細な手順を示すサブルーチンのフローチャートである。最近領域の選択の処理は、候補領域管理部１１４によって実行される。まず、候補領域管理部１１４は、候補領域ヒープ９２の根要素に対応する領域を最近領域に設定する（Ｓ１３０１）。次に、候補領域管理部１１４は、候補領域ヒープ９２の根要素を削除する（Ｓ１３０２）。その後、候補領域管理部１１４は、候補領域ヒープ９２内に要素が存在するか判定する（Ｓ１３０３）。当該条件を満たす場合、候補領域管理部１１４は、ステップＳ１３０４からＳ１３０７の処理によって、根要素の削除に伴う候補領域ヒープ９２の再構築を実行する。ステップＳ１３０３の上記条件を満たさない場合、候補領域管理部１１４は候補領域ヒープ９２を再構築する必要がないためサブルーチンを終了して、図６に示した最近領域の最下位枝判定（Ｓ１０２）に進める。
【００６９】
一方、ステップＳ１３０３で要素が候補領域ヒープ９２に存在するときには、候補領域管理部１１４が、根要素に候補領域ヒープ９２の末尾（移動要素）を移動させる（Ｓ１３０４）。一次元配列では、格納位置が末尾の要素を、格納位置が０の場所に移動させることになる。次に、候補領域管理部１１４は、移動要素が子要素をもつか否かを判定する（Ｓ１３０５）。当該条件を満たさない場合、候補領域ヒープ９２のヒープ条件を満たす。この場合、候補領域管理部１１４はサブルーチンを終了して次の処理である最近領域の最下位枝判定（Ｓ１０２）に進む。一方、ステップＳ１３０５の当該条件を満たす場合、候補領域管理部１１４は、移動要素の領域距離ｄが子要素の領域距離ｄより大きい値か否かを判定する（Ｓ１３０６）。当該条件を満たす場合、候補領域ヒープ９２のヒープ条件を満たさない。この場合、候補領域管理部１１４は移動要素と子要素の格納位置を交換して、ステップＳ１３０５に戻る（Ｓ１３０７）。なお、二つの子要素がステップＳ１３０６の条件を満たす場合、領域距離ｄの小さい子要素が交換対象となる。一次元配列では、移動要素の格納位置がｉの場合、格納位置が２×ｉ＋１、または２×ｉ＋２の子要素と交換することになる。
【００７０】
上記ステップＳ１３０６の条件を満たさない場合、候補領域ヒープ９２がヒープ条件を満たす。この場合、候補領域管理部１１４はサブルーチンを終了して次の処理である図６に示す処理対象領域の最下位枝判定（Ｓ１０２）に進む。
【００７１】
図１４は、地点距離計算（Ｓ１０６）の詳細な手順を示すサブルーチンのフローチャートである。地点距離計算の処理は、地点距離計算部１１５によって実行される。まず、地点距離計算部１１５は、最近領域に隣接する葉情報を取得する（Ｓ１４０１）。地点距離計算部１１５は、分割領域テーブル４０１に格納された最近領域の領域情報の葉ポインタ４１７を参照することで、葉情報を取得できる。次に、地点距離計算部１１５は、葉情報における先頭の地点を座標情報読取ポインタに設定する（Ｓ１４０２）地点距離計算部１１５は、座標読取ポインタの指す地点を処理対象地点に設定する（Ｓ１４０３）。その後、地点距離計算部１１５は、ステップＳ１４０４において式（２）を用いて、質問地点と地点データの地点距離ｄ’を計算する。
【００７２】
【数２】
【００７３】
式（２）において、地点距離ｄ’は、質問地点（ｘ、ｙ）と処理対象地点（x’、y’）とのユークリッド距離になる。実環境では、平方根の計算が検索時間の遅延に大きく影響を及ぼす場合がある。この場合、地点距離ｄ’と領域距離ｄを二乗のままで、ｋ最近傍検索を実行しても良い。そして、地点距離計算部１１５は、サブルーチンを終了して図６に示した次の処理である、候補地点ヒープ９１に処理対象地点を候補地点として記録する処理（Ｓ１０７）に進む。なお、ステップＳ１４０５の処理は、後述のステップＳ１５０８から実行される処理であり、地点データを１点ずつ距離計算し、候補地点ヒープ９１に記録することを意味する。
【００７４】
図１５は、候補地点ヒープ９１への候補地点の記録（Ｓ１０７）の詳細な手順を示すサブルーチンのフローチャートである。候補地点の記録処理は、候補地点管理部１１６によって実行される。まず、候補地点管理部１１６は、処理対象地点の候補地点ヒープ９１用の要素を生成する（Ｓ１５０１）。当該要素は、処理対象地点の地点ＩＤ５１１、地点距離ｄ’、地点ポインタ５１３から構成される。次に、候補地点管理部１１６は、処理対象地点ヒープの要素数が質問件数と等しいかを判定する。既に候補地点ヒープ９１が上位ｋ件の地点データを記憶しているか否かで、これ以降の処理内容が異なる。
【００７５】
まず、ステップＳ１５０２の条件を満たす場合、既に候補地点ヒープ９１が質問件数を満たすことになる。この場合、候補地点管理部１１６は、処理対象地点の地点距離ｄ’が、候補地点ヒープ９１の中で質問地点に最も遠い地点データの地点距離ｄ’より小さいか否かを判定する（Ｓ１５０３）。候補地点ヒープ９１の中で質問地点に最も遠い地点データは、候補地点ヒープ９１の根要素になる。当該条件を満たす場合、候補地点ヒープ９１の根要素に代わり、処理対象地点が新しく候補地点に入ることを意味する。
【００７６】
ステップＳ１５０４からＳ１５０７までの処理で、候補地点管理部１１６が、ヒープ条件を満たしながら、処理対象地点を候補地点ヒープ９１に記録する。一方、Ｓ１５０３の条件を満たさない場合、処理対象地点が候補地点に入らないことを意味する。この場合、候補地点管理部１１６は、ステップＳ１５０８の処理へ進む。
【００７７】
次に、上記ステップＳ１５０２の条件を満たさない場合、まだ、候補地点ヒープ９１が質問件数を満たしていないことになる。この場合、候補地点管理部１１６は、処理対象地点の要素を候補地点ヒープ９１に挿入することを前提にする。候補地点管理部１１６は、ステップＳ１５１０からＳ１５１２の処理で、ヒープ条件を満たしながら、処理対象地点の要素を候補地点ヒープ９１に格納する。
【００７８】
次に、候補地点管理部１１６は、ステップＳ１５０８に進むと、最近領域の全ての地点データについて、候補地点になるか否かを調査したかを判定する。当該条件を満たす場合、候補地点管理部１１６はサブルーチンを終了して図６に示した終了判定（Ｓ１０８）へ進める。一方、Ｓ１５０８の条件を満たさない場合、候補地点管理部１１６は処理を図１４に示したステップＳ１４０５へ進ませて、ループの度に地点データを１点ずつ距離計算し、候補地点ヒープ９１に記録する。
【００７９】
図１６は、終了判定（Ｓ１０８）の手順を示すフローチャートである。終了判定の処理は、終了判定部１１７によって実行される。まず、終了判定部１１７は、候補地点ヒープ９１に要素が存在するか否かを判定する。当該条件を満たさない場合、次に調査すべき分割領域が存在しないことになる。したがって、終了判定部１１７は、次に行う処理として図６に示した処理として検索結果の取得（Ｓ１０９）を選択する（Ｓ１６０４）。
【００８０】
一方、ステップＳ１６０１の条件を満たす場合、候補領域ヒープ９２の根要素の領域距離ｄが候補地点ヒープ９１の根要素の地点距離ｄ’より大きいか否かを判定する（Ｓ１６０２）。当該条件を満たす場合、検索処理を終了とみなす。終了条件は、候補領域ヒープ９２の根要素の領域距離ｄが、候補地点ヒープ９１の根要素の地点距離ｄ’より大きいという条件である。この条件は、さらに広い範囲に存在する分割領域内の地点データを調査しても、候補地点に入る地点データを見つけることができないことを意味する。終了条件の判定は、候補領域と候補地点の記憶にヒープ構造を用いているため、候補地点ヒープ９１内をＯ（１）の探索回数で、実現できる。ステップＳ１６０２の条件を満たす場合、終了判定部１１７は次の処理として図６に示した検索結果の取得（Ｓ１０９）を選択してサブルーチンを終了する。一方、ステップＳ１６０２の条件を満たさない場合、別の分割領域に内包される地点データを調査するため、次に行う処理を図６に示した最近領域の選択（Ｓ１０５）としてサブルーチンを終了する。
【００８１】
図１７は、検索結果の取得（Ｓ１０９）の詳細な手順を示すサブルーチンのフローチャートである。検索結果の取得処理は、結果取得部１１８によって実行される。この処理によって、結果取得部１１８は、質問地点から距離の近い順に地点データを取得する。
【００８２】
まず、結果取得部１１８は、候補地点ヒープ９１の根要素を結果リスト９３の末尾に挿入する（Ｓ１７０１）。結果リスト９３は、候補地点ヒープ９１と同じ要素を格納可能な一次元配列であり、結果取得部１１８がメモリ２上に予め確保した領域である。次に、結果取得部１１８は、候補地点ヒープ９１の根要素を削除する（Ｓ１７０２）。その後、結果取得部１１８は、要素が候補地点ヒープ９１に存在するか否かを判定する（Ｓ１７０３）。当該条件を満たす場合、結果取得部１１８は、ステップＳ１７０４からＳ１７０７の処理で、根要素の削除に伴う候補地点ヒープ９１の再構築を行う。ステップＳ１７０３の条件を満たさない場合、結果取得部１１８は、結果リスト９３の末尾から先頭に向かい、地点データを一つずつ取得する（Ｓ１７０８）。当該地点データは、地点座標５１２と任意個数の属性を含む、空間データベース１００で管理されるレコードとなる。
【００８３】
以上より、本処理は、まず、地点距離ｄ’の大きい順にヒープソートを行い、その結果を一次元配列で構成した結果リスト９３の先頭から順に記憶しておく。そして、当該一次元配列の末尾から先頭に向かい地点データを取得することで、質問地点から距離の近い順に地点データを取得していく。地点データの要素数をＮとした場合に、ヒープソートの探索回数はＯ（Ｎ・ｌogＮ）となり、一次元配列内の探索回数はＯ（Ｎ）となり、結果を得るまでの探索回数をＯ（Ｎ・logＮ）に抑えることができる。結果取得部１１８がステップＳ１７０８の処理を終えると、ｋ最近傍検索が終了する。
【００８４】
上述したｋ最近傍検索の具体的なアルゴリズムの動作について、図１８ａ〜図１８ｃ、図１９、図２０を用いて、説明する。
【００８５】
まず、図１８ａは、上記図２に示した空間領域２０１を、図２に示した深さ０の階層の真上から鳥瞰した空間領域１８０３を示す。この空間領域８０３は、上記ｋ最近傍検索で質問地点１８０４と質問件数を５に設定した場合の例を示す。図中丸印の内部の数値は領域ＩＤ４１２を示し、図中方形の枠内の文字は地点ＩＤ５１１を示す。図１８ｂは、上記ｋ最近傍検索の処理過程で計算した空間領域１８０３における領域距離ｄを表形式で図示したテーブル１８０１である。図１８ｃは、上記ｋ最近傍検索の処理過程で計算した空間領域１８０３における地点距離ｄ’を表形式で図示したテーブル１８０２である。なお、テーブル１８０１、１８０２の情報は、メモリ２上の候補領域ヒープと候補地点ヒープにそれぞれ保持される。
【００８６】
図１９は、図１８ａの空間領域１８０３を用いて、ｋ最近傍検索を実行した際の候補領域ヒープ９２の格納状況を示す。候補領域ヒープ９２を木構造で表現する。ヒープ木の節１９０１内の数字は領域ＩＤ４１２、山括弧１９０２内の数値は領域ＩＤ４１２で示す分割領域間の距離を示す。
【００８７】
図２０は、図１８ａに示した空間領域１８０３を用いて、ｋ最近傍検索を実行した際の候補地点ヒープ９１の格納状況を示す。候補地点ヒープ９１を木構造で表現する。ヒープ木の節２００１内のアルファベットは地点ＩＤ５１１、山括弧２００２内の数値は地点ＩＤ５１１で示す地点データの地点距離ｄ’を示す。
【００８８】
ｋ最近傍検索を実行すると、まず、初期設定部１１１が最近領域を領域０に設定する。領域距離計算部１１３が領域０の子領域１、２、３、４の領域距離ｄを計算し、子領域の領域情報を候補領域ヒープ９２に格納する（図１９の（１））。次に、候補領域管理部１１４は最近領域を領域１に設定し、候補領域ヒープ９２から領域１の情報を削除する。そして、候補領域管理部１１４が領域１の子領域５、６、７、８の情報を候補領域ヒープ９２に格納する（図１９の（２））。上記と同様に候補領域管理部１１４は、最近領域を領域８に設定する。同様に、候補領域ヒープ９２から領域８の情報を削除し、領域８の子領域３３、３４、３５、３６の情報を候補領域ヒープ９２に挿入する（図１９の（３））。候補領域管理部１１４は最近領域を最下位枝の領域３３に設定する。この場合、領域３３の情報を候補領域ヒープ９２から削除し、領域３３に内包される地点データＥの情報を、候補地点ヒープ９１に挿入する。この時点の候補領域ヒープ９２の格納状況を図１９の（４）に示し、候補地点ヒープ９１の格納状況を図２０の（１）に示す。最近領域を領域３５に設定すると、領域３３と同様に、候補領域ヒープ９２と候補地点ヒープ９１が更新される（図１９（５）と図２０（２））。
【００８９】
以下、同様に処理を進めると、候補領域ヒープ９２と候補地点ヒープ９１の格納状況はそれぞれ図１９の（１１）と図２０の（６）に示すようになる。このとき、候補地点ヒープ９１の根要素（地点データＩ）の地点距離ｄ’が、候補領域ヒープ９２の根要素（領域２５）の領域距離ｄより小さくなる。終了条件を満たすため、ｋ最近傍検索の結果は、地点データＩ、Ｆ、Ｇ、Ｅ、Ｃとなる。
【００９０】
なお、実施の形態１と同等の機能をもつｋ最近傍検索プログラムを記録した媒体やｋ最近傍検索装置も、本発明に含まれる。この点は、以降の説明で記載する実施の第２の実施形態や第３の実施形態でも同様である。
【００９１】
以上のように本発明の第１の実施形態によれば、検索実行時の空間インデックス１０１へのディスクアクセス回数を削減することが可能となって、前記従来例のように範囲指定検索を用いたｋ最近傍検索に比べ、検索時間を短縮できる。さらに、第１の実施形態では、必要最低限の地点データのみ距離計算の対象とするため、従来のｋ最近傍検索に比べ、ＣＰＵ３の演算負荷を軽減することが可能となる。
【００９２】
＜第２の実施形態＞
第２の実施形態は、第１の実施形態を拡張し、上述の第３の問題を解決する属性指定のｋ最近傍検索を実現する。
【００９３】
具体的には、第１の実施形態の図５に示した地点テーブル５０１を拡張して、図２１に示す地点テーブル２１０１を採用する。地点テーブル２１０１は、地点データを格納するテーブルの座標情報に、地点ＩＤ５１１、Ｘ座標とＹ座標の地点座標５１２、地点ポインタ５１３に加え、地点種別５１４を追加する。例えば、カーナビゲーション装置１の施設テーブルの場合、地点種別に、レストラン、駐車場、ガソリンスタンドなどの地点データの種類を格納することが考えられる。座標情報への地点種別５１４の追加に伴い、四分木の葉情報において、各地点の座標情報にも地点種別５１４を追加する。
【００９４】
第２の実施形態の処理は、基本的に第１の実施形態に示した図６のフローチャートに従う。ただし、第２の実施形態は、図６に記載の検索の初期設定Ｓ１０１と、地点距離ｄ’の計算Ｓ１０６の処理内容の一部を変更した。以下では、本形態の実現のために変更した処理内容について説明する。
【００９５】
図２２は、第２の実施形態における検索の初期設定（Ｓ１０１）の手順を示すサブルーチンのフローチャートである。第１の実施形態の図７と異なる部分は、図７のステップＳ６０１をステップＳ２２０１のステップに変更した点である。ステップＳ２２０１において、初期設定部１１１は、質問地点の座標と質問件数に加えて、地点種別を設定する。本形態によるｋ最近傍検索の実行結果は、当該地点種別に一致する地点データのみを含む。なお、ステップＳ２２０２〜Ｓ２２０４は、第１の実施形態の図７のステップＳ６０２〜Ｓ６０４と同一である。
【００９６】
図２３は、第２の実施形態の地点距離計算（Ｓ１０６）の手順を示すサブルーチンのフローチャートである。図２３は、第１の実施形態の図１４のフローチャートに対して、ステップＳ２３０４とステップＳ２３０７を加え、ステップＳ２３０７の判定がＹＥＳの場合には、終了判定部１１７の処理（Ｓ１０８）へ移行するようにした点が異なる。
【００９７】
ステップＳ２３０４において、地点距離計算部１１５は、処理対象地点の地点種別が上記初期設定部１１１のステップＳ２２０１で設定した地点種別に一致するか判定する。この判定の結果、ＮＯであればステップＳ２３０６に進む、Ｓ２３０４により、第２の実施形態は、指定した属性値に一致する地点データのみを取得できる。なお、図２３において、ステップＳ２３０１〜Ｓ２３０３、Ｓ２３０５、Ｓ２３０６は、第１の実施形態に示した図１４のステップＳ１４０１〜Ｓ１４０４、Ｓ１４０５と同一である。
【００９８】
以上、本発明の第２の実施の形態によれば、属性指定検索とｋ最近傍検索を組み合わせた場合でも、従来のｋ最近傍検索に比べ、検索実行時間を短縮できる。これは、第２実施では、空間インデックス１０１の探索のみで、ｋ最近傍検索を実行できるためである。また、第２の実施の形態では、指定した属性値に一致するｋ件の地点データを正確に取得できる。これは、第２の実施の形態が、検索対象の地点テーブル２１０１において、座標情報と属性情報を含む一つの列に対して、ｋ最近傍検索を実行できるためである。
【００９９】
＜第３の実施形態＞
第３の実施の形態は、第１の実施形態を拡張し、上述の第４の問題を解決する最近傍検索を提供する。第３の実施形態の処理は、基本的に第１の実施形態に示した図６のフローチャートに従う。具体的には、検索処理中であっても、検索処理を中断できるように、検索条件に中断条件を設ける。例えば、中断条件は質問地点からの距離で記述する。この場合、当該距離の範囲に存在する地点データが見つからない時点で、検索処理を中断する。また、中断条件として、最大処理時間の設定も効果的である。この場合、検索処理に費やすことができる時間を最大処理時間に設定し、検索処理の経過時間が最大処理時間と等しくなった時点で、検索処理を中断する。以下では、第３の実施形態の中断条件に距離を用いた場合で説明する。
【０１００】
初期設定部１１１で質問地点からの最大距離値（以下、質問距離と呼ぶ）を設定し、質問距離以下の地点データを発見できない時点で、質問件数を満たさずとも、検索処理を終了させる。なお、第３の実施形態による第１の実施形態への拡張は、第２の実施形態でも同様に適用でき、上述の第４の問題を解決できる。第３の実施形態は、第１の実施形態に示した図７に記載の検索の初期設定Ｓ１０１、領域距離ｄの計算を行うステップＳ１０３、地点距離ｄ’の計算を行うステップＳ１０６の処理内容を変更する。以下では、第３の実施形態の実現のために変更した処理内容について説明する。
【０１０１】
図２４は、第３の実施の形態における初期設定（Ｓ１０１）の手順を示すサブルーチンのフローチャートである。このフローチャートは、第１の実施形態に示した図７のステップＳ６０１を、ステップＳ２４０１に置き換えたものである。ステップＳ２４０１において、初期設定部１１１は、質問地点の座標と質問件数に加えて、質問距離を設定する。第３の実施形態によるｋ最近傍検索の実行結果は、質問地点からの距離値が質問距離以下の地点データのみを含む。なお、ステップＳ２４０２〜Ｓ２４０４は、第１の実施形態の図７のステップＳ６０２〜Ｓ６０４よ同一である。
【０１０２】
図２５は、第３の実施の形態における領域距離計算の手順を示すサブルーチンのフローチャートである。このフローチャートは、第１の実施形態に示した図９のステップＳ８０６を、ステップＳ２５０６に置き換えたものである。ステップＳ２５０６の処理において、領域距離計算部１１３は、質問距離以下の領域距離ｄをもつ子領域を対象に、領域ＩＤ４１２、領域ポインタ、領域距離ｄを候補領域管理部に渡すことにしている。Ｓ２５０６の処理によって、候補領域ヒープ９２は、質問距離以下の領域距離ｄをもつ分割領域の情報のみを記録することになる。質問距離以下の領域距離ｄをもつ分割領域は、質問距離の条件を満たし、結果候補に入る可能性のある地点データを内包する。なお、ステップＳ２５０１〜Ｓ２５０５は、第１の実施形態の図９に示したステップＳ８０１〜Ｓ８０５と同一である。
【０１０３】
図２６は、第３の実施の形態における地点距離の計算の手順を示すサブルーチンのフローチャートである。このフローチャートは、第１の実施形態に示した図１４のステップＳ１４０４以降に、ステップＳ２６０５、Ｓ２６０７を加えたものである。
【０１０４】
ステップＳ２６０４で処理対象地点の地点距離ｄ’を計算した後で、当該地点距離ｄ’が質問距離以下であるかを判断する処理（Ｓ２６０５）を追加し、該条件を満たす場合、候補地点の記録の処理（Ｓ１０７）へ進む。当該条件を満たさない場合、処理対象地点が検索結果に入らないため、すべての地点データを処理していなければ（Ｓ２６０７でＮＯを選択）、次の地点データの地点距離ｄ’の計算へ進める。なお、ステップＳ２６０１〜Ｓ２６０４、Ｓ２６０６は、第１の実施形態に示した図１４のステップＳ１４０１〜１４０４、Ｓ１４０５と同一である。
【０１０５】
以上、本発明の第３の実施の形態によれば、ｋ最近傍検索の実行結果の近傍性を保証できる。これは、第３の実施の形態が、検索条件に中断条件を設定できるためである。中断条件は、例えば、質問地点からの最大距離や検索処理に費やすことのできる最大処理時間である。
【０１０６】
＜第４の実施形態＞
第４の実施形態は、ｋ最近傍検索をデータベース管理システム８で実行する場合に記述する問合せ言語、または関数に関する。第４の実施形態は、例えば、アプリケーション開発者が、アプリケーションプログラムからデータベース管理システム８にｋ最近傍検索を要求する場合のＳＱＬに相当する。以下では、データベース管理システム８の一般的な問合せ言語であるＳＱＬを用いて、第４の実施形態について説明する。
【０１０７】
図２７ａ〜図２７ｄは、第１の実施形態、第２の実施形態または第３の実施形態のいずれかで実現されるｋ最近傍検索のためのＳＱＬの記述方法である。なお、図２７ａ〜図２７ｄでは、空間データベース１００が、地点データを格納する一つのテーブルに対して、ｋ最近傍検索に合致するレコードの全ての列を取得する場合を示す。
【０１０８】
図２７ａの２７０１に記載のＳＱＬは、第１の実施形態で実現したｋ最近傍検索のみで利用可能である。２７０１において、ＷＨＥＲＥ句のｋＮＮ（ｋ−Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ）は、ｋ最近傍検索のためのスカラー関数を示す。ｋＮＮ関数の第１引数は検索対象テーブルの座標列名、第２引数は質問地点、第３引数は質問件数となる。
【０１０９】
図２７ｂの２７０２に記載のＳＱＬは、第１の実施形態または第２の実施形態で実現したｋ最近傍検索で利用可能である。２７０２のｋＮＮ関数の第１引数は検索対象テーブルの座標列名、第２引数は質問地点、第３引数は質問件数、第４引数は地点データの種別となる。なお、第１の実施形態で実現したｋ最近傍検索は、種別を設定する必要がないため、第４引数にＮＵＬＬを設定する。
【０１１０】
図２７ｃの２７０３に記載のＳＱＬは、第１の実施形態または第３の実施形態で実現したｋ最近傍検索で利用可能である。２７０３のｋＮＮ関数の第１引数は検索対象テーブルの座標列名、第２引数は質問地点、第３引数は質問件数、第４引数は質問距離となる。なお、第３の実施形態で実現したｋ最近傍検索は、質問距離を設定する必要がないため、第４引数にＮＵＬＬを設定する。
【０１１１】
図２７ｃの２７０４に記載のＳＱＬは、第１の実施形態、第２の実施形態、第３の実施形態のどの場合で実現したｋ最近傍検索でも利用可能である。２７０４のｋＮＮ関数の第１引数は検索対象テーブルの座標列名、第２引数は質問地点、第３引数は質問件数、第４引数は地点データの種別、第５引数は質問距離となる。また、この記載方法は、第３の実施形態２と形態３を組み合わせたｋ最近傍検索でも利用可能である。なお、第３の実施形態で実現したｋ最近傍検索は、質問距離を指定する必要がないため、第４引数と第５引数にＮＵＬＬを設定する。形態２で実現したｋ最近傍検索は、質問距離を設定する必要がないため、第５引数にＮＵＬＬを設定する。形態３で実現したｋ最近傍検索は、種別を設定する必要がないため、第４引数にＮＵＬＬを設定する。
【０１１２】
以上、本発明の第４の実施の形態によれば、アプリケーションプログラム開発者がｋ最近傍検索をＳＱＬで記述できることで、プログラムの開発期間を短縮できる。
【０１１３】
以上の四つの実施の形態では、地理空間内の地点データを対象に、ｋ最近傍検索方法について説明した。ここで、本発明は、地理空間内の地点データへの適用に限るものではない。本発明は、テレビ番組や楽曲など、特徴ベクトルで表現可能なデータにも適用でき、類似検索を実現できる。例えば、テレビ番組の場合、第一特徴ベクトルにシリアスとバラエティを軸に取り、第二特徴ベクトルにフィクションとノンフィクションを軸に取る。そして、これらを軸とした二次元空間にテレビ番組を対応付け、指定した地点から距離の近い番組を検索できれば、特徴が類似しているテレビ番組を検索できる。
【０１１４】
なお、上記各実施形態では本発明をカーナビゲーション装置１へ適用した例を示したが、この他ＰＮＤや携帯電話あるいは携帯ゲーム機等の組込機器に適用することができる。また、空間データベース１００としては、２次元、または３次元空間の地点データを検索対象とすることができる。
【０１１５】
また、上記各実施形態では、空間インデックス１０１に四分木を適用した例を示したが、Ｒ−ｔｒｅｅ等の他の空間インデックスを適用しても良い。
【０１１６】
また、上記各実施形態では、地点データを２次元空間内の座標とした例を示したが、多次元の座標で構成された地点データに本発明を適用しても良い。 例えば、多次元の地点データが３次元で構成され、３次元空間内の一つの座標で位置を特定可能な地点データである場合、空間インデックス１０１が八分木またはＲ−ｔｒｅｅの何れか一方により地点データを複数の領域に分割して上述のような検索処理を行うことができる。
＜補足＞
７．前記候補領域管理部は、分割領域の情報をヒープ構造で管理し、前記ヒープ構造の節に対応する分割領域の領域距離は、前記節の子に対応する分割領域の領域距離より小さいか等しいというヒープ条件を設ける請求項６に記載のｋ最近傍検索方法。
【０１１７】
１０．前記候補地点管理部は、前記地点データの情報をヒープ構造で管理し、前記ヒープ構造に、前記ヒープ構造の節に対応する地点データの地点距離は、前記節の子に対応する地点データの地点距離より大きいか等しいというヒープ条件を設ける請求項９に記載のｋ最近
１２．前記終了判定部は、前記候補領域管理部のヒープ構造の根に位置する分割領域の領域距離が、前記候補地点管理部のヒープ構造の根に位置する地点データの地点距離より大きい場合に、検索を終了させる請求項１０に記載のｋ最近傍検索方法。
【０１１８】
１４．前記初期設定部は、質問地点、質問件数、中断条件を検索条件として設定し、
前記質問件数に満たない状況でも、前記中断条件を満たす場合に検索処理を中断し、
前記結果取得部が、前記質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項２に記載のｋ最近傍検索方法。
【０１１９】
１５．前記中断条件は、検索結果となる地点データの最大距離を示す質問距離で記述し、
前記領域距離計算部は、前記質問距離より小さいか等しい分割領域に関する情報のみを 前記候補領域管理部に記録するように処理し、
前記地点距離計算部は、質問距離より小さいか等しい地点データに関する情報のみを前 記候補地点管理部に記録するように処理することで、
前記結果取得部が、データベース管理システムから、前記質問距離より小さいか等しく、かつ質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項１４に記載のｋ最近傍検索方法。
【０１２０】
１６．前記中断条件は、検索処理に費やすことができる最大時間を示す最大処理時間で記述し、
検索処理の実行経過時間が前記最大処理時間と等しくなると、前記検索処理を中断して、
前記結果取得部が、データベース管理システムから、質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項１４に記載のｋ最近傍検索方法。
【０１２１】
１７．前記初期設定部は、質問地点、質問件数、属性情報、中断条件を検索条件として設定し、
前記地点距離計算部は、前記検索条件の属性情報に一致する地点データのみを前記候補地点管理部に記録するように処理すると共に、
前記質問件数に満たない状況でも、前記中断条件を満たす場合に検索処理を中断し、
前記結果取得部が、前記データベース管理システムから、前記属性情報に一致する最大ｋ件の地点データを取得可能な請求項２に記載のｋ最近傍検索方法。
【０１２２】
１８．前記中断条件は、検索結果となる地点データの最大距離を示す質問距離で記述し、
前記領域距離計算部は、前記質問距離より小さいか等しい分割領域に関する情報のみを前記候補領域管理部に記録するように処理し、
前記地点距離計算部は、前記質問距離より小さいか等しい地点データに関する情報のみを前記候補地点管理部に記録するように処理することで、
前記結果取得部が、前記データベース管理システムから、前記属性情報に一致し、かつ前記質問距離より小さいか等しく、かつ質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項１７に記載のｋ最近傍検索方法。
【０１２３】
１９．前記中断条件は、検索処理に費やすことができる最大時間を示す最大処理時間で記述し、
検索処理の実行経過時間が前記最大処理時間と等しくなると、前記検索処理を中断して、
前記結果取得部が、前記データベース管理システムから、前記属性情報に一致し、かつ前記質問距離より小さいか等しく、かつ質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項１７に記載のｋ最近傍検索方法。
【０１２４】
２１．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、属性情報を引数に取る問合せ言語、または関数で記述可能な請求項１３に記載のｋ最近傍検索方法。
【０１２５】
２２．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、中断条件を引数に取る問合せ言語、または関数で記述可能な請求項１４に記載のｋ最近傍検索方法。
【０１２６】
２３．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、質問距離を引数に取る問合せ言語、または関数で記述可能な請求項１５に記載のｋ最近傍検索方法。
【０１２７】
２４．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、最大処理時間を引数に取る問合せ言語、または関数で記述可能な請求項１６に記載のｋ最近傍検索方法。
【０１２８】
２５．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、属性情報、中断条件を引数に取る問合せ言語、または関数で記述可能な請求項１７に記載のｋ最近傍検索方法。
【０１２９】
２６．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、属性情報、質問距離を引数に取る問合せ言語、または関数で記述可能な請求項１８に記載のｋ最近傍検索方法。
【０１３０】
２７．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、属性情報、最大処理時間を引数に取る問合せ言語、または関数で記述可能な請求項１９に記載のｋ最近傍検索方法。
【産業上の利用可能性】
【０１３１】
以上のように、本発明は空間データベースを利用する計算機システムに適用することができ、特に、カーナビゲーション装置などの組込装置に適用することができる。
【図面の簡単な説明】
【０１３２】
【図１】第１の実施形態を示し、本発明を適用するカーナビゲーション装置の構成を示すブロック図。
【図２】第１の実施形態を示し、空間インデックスに適用する四分木の階層構造を示す説明図。
【図３】第１の実施形態を示し、空間インデックスに適用する四分木の木構造を示す説明図。
【図４】第１の実施形態を示し、四分木の枝情報を格納する分割領域テーブルの一例を示す説明図。
【図５】第１の実施形態を示し、四分木の葉情報を格納する地点テーブルの一例を示す説明図。
【図６】第１の実施形態を示し、カーナビゲーション装置で実行されるｋ最近傍検索の手順の一例を示すフローチャート。
【図７】第１の実施形態を示し、図６に示した初期設定部のサブルーチンの一例を示すフローチャート。
【図８】第１の実施形態を示し、図６に示した最下位判定部のサブルーチンの一例を示すフローチャート。
【図９】第１の実施形態を示し、図６に示した領域距離計算部のサブルーチンの一例を示すフローチャート。
【図１０】第１の実施形態を示し、分割領域の領域距離の計算方法を示す説明図。
【図１１】第１の実施形態を示し、図６に示した最近領域の子領域の情報を記録する処理のサブルーチンの一例を示すフローチャート。
【図１２】第１の実施形態を示し、一次元配列によるヒープ木の説明図。
【図１３】第１の実施形態を示し、図６に示した最近領域の子領域の情報を記録する処理のサブルーチンの一例を示すフローチャート。
【図１４】第１の実施形態を示し、図６に示した地点距離計算部のサブルーチンの一例を示すフローチャート。
【図１５】第１の実施形態を示し、図６に示した候補地点管理部のサブルーチンの一例を示すフローチャート。
【図１６】第１の実施形態を示し、図６に示した終了判定部のサブルーチンの一例を示すフローチャート。
【図１７】第１の実施形態を示し、図６に示した結果取得部のサブルーチンの一例を示すフローチャート。
【図１８ａ】第１の実施形態を示し、図２に示した空間領域の平面図。
【図１８ｂ】第１の実施形態を示し、ｋ最近傍検索で得られた空間領域における領域ＩＤと領域距離ｄを保持するテーブルの説明図。
【図１８ｃ】第１の実施形態を示し、ｋ最近傍検索で得られた空間領域における地点ＩＤと地点距離ｄ’を保持するテーブルの説明図。
【図１９】第１の実施形態を示し、図１８ａの空間領域でｋ最近傍検索を実行した際の候補領域ヒープ９２の木構造の一例を示す説明図。
【図２０】第１の実施形態を示し、図１８ａの空間領域でｋ最近傍検索を実行した際の候補地点ヒープ９１の木構造の一例を示す説明図。
【図２１】第２の実施形態を示し、四分木の葉情報を格納する地点テーブルの一例を示す説明図。
【図２２】第２の実施形態を示し、初期設定部のサブルーチンの一例を示すフローチャート。
【図２３】第２の実施形態を示し、地点距離計算部のサブルーチンの一例を示すフローチャート。
【図２４】第３の実施形態を示し、初期設定部のサブルーチンの一例を示すフローチャート。
【図２５】第３の実施形態を示し、領域距離計算部のサブルーチンの一例を示すフローチャート。
【図２６】第３の実施形態を示し、地点距離計算部のサブルーチンの一例を示すフローチャート。
【図２７ａ】第４の実施形態を示し、前記第１実施形態に適用可能なＳＱＬを示す説明図。
【図２７ｂ】第４の実施形態を示し、前記第１実施形態と第２実施形態に適用可能なＳＱＬを示す説明図。
【図２７ｃ】第４の実施形態を示し、前記第１実施形態と第３実施形態に適用可能なＳＱＬを示す説明図。
【図２７ｄ】第４の実施形態を示し、前記第１実施形態と第２実施形態及び第３実施形態に適用可能なＳＱＬを示す説明図。
【符号の説明】
【０１３３】
１ カーナビゲーション装置
２ メモリ
３ ＣＰＵ
５ ストレージ装置
７ ＯＳ
８ ＤＢＭＳ
９ アプリケーション
１００ 空間データベース
１０１ 空間インデックス
１１１初期設定部
１１２ 最下位枝判定部
１１３ 領域距離計算部
１１４ 候補領域管理部
１１５ 地点距離計算部
１１６ 候補地点管理部
１１７ 終了判定部
１１８ 結果取得部
５０１ 地点テーブル
【技術分野】
【０００１】
本発明は、任意の多次元地点データから距離の近い上位ｋ件の地点データを、厳密かつ高速に検索するｋ最近傍検索技術に関する。特に、地図情報管理を想定し、2次元、または3次元空間の地点データを検索対象とする。
【背景技術】
【０００２】
これまでに、地図情報管理を目的とし、空間検索機能を有するデータベース管理システムが開発されている。このようなデータベース管理システムを空間データベースと呼ぶ。空間データベースは、地物を点、線、面などの図形要素と、地物の内容を示す文字や数値などの属性要素を管理できる。空間検索機能は、任意の範囲に内包、または接触する地物を取得する範囲指定検索を実現する。範囲指定検索の高速化のため、四分木、グリッドファイル、R−treeなどの空間インデックス技術が既に提案されている。空間インデックス技術は、空間領域における地物の配置分布に応じて、空間領域を分割する。
【０００３】
従来、空間データベースは、エンタープライズのアプリケーション向けに開発されてきた。ところが、近年、空間データベースが組込機器のアプリケーション向けにも開発されてきている。空間データベースを必要とする組込機器は、カーナビゲーション装置やＰＮＤ（Personal Navigation System）などの地図情報を管理する機器である。カーナビゲーション装置は、現在地や目的地などユーザの指定した地点付近の飲食店や駐車場などの地点データを検索する機能をもつ。その際、ユーザの指定した地点（以下、質問地点と呼ぶ）から距離の近い上位ｋ件（以下、質問件数と呼ぶ）の地点データを空間データベースから取得するｋ最近傍検索が知られている。
【０００４】
従来の空間データベースにおけるｋ最近傍検索は、範囲指定検索を用いて、実現される。従来のｋ最近傍検索では、まず、質問地点を中心とした任意の大きさをもつ検索範囲が設定される。検索範囲に含まれる地点データが質問件数以上ならば、質問地点と当該地点データとの距離を計算する。そして、距離の短い順に当該地点データをソートし、距離の短い上位ｋ件の地点データを、検索結果として取得する。一方、検索範囲に含まれる地点データが質問件数未満ならば、質問件数以上になるまで、検索範囲が大きく設定され、範囲指定検索が繰り返される。例えば、グリッドファイルによる範囲指定検索を用いた方法（例えば、特許文献１参照）や、四分木による範囲指定検索を用いる方法（例えば、特許文献２参照）などが知られている。
【特許文献１】特開２００３−２４２１５１号
【特許文献２】米国特許第６、８７９、９８０号
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記従来技術を組込機器に適用すると、以下のような問題があった。
【０００６】
まず、第１の問題として、ディスクアクセスと演算負荷により、検索時間が増大する。
【０００７】
一般に組込機器は小容量の主記憶装置を備えるため、検索実行時に空間インデックスのページを外部記憶装置から主記憶装置に読込むディスクアクセスが発生する。そのため、組込機器では、検索範囲に含まれる地点データの件数が非常に多い場合、ディスクアクセスが頻発し、検索時間が長くなる。特に、この問題は、地点データの存在密度が高い地域で、検索範囲が大きい場合に発生する。一方、エンタープライズ用のサーバは、大容量の主記憶装置を備えている。そのため、サーバは、空間インデックスの大部分のページを予め主記憶装置に格納できる。この場合、検索範囲に含まれる地点データが多い場合でも、ディスクアクセスが頻発せず、検索時間が長くならない。
【０００８】
また、組込機器は低速な中央処理装置を備えるため、質問地点と地点データまでの距離計算や、距離によるソート処理等の演算負荷が検索時間に影響を与える。特に、検索範囲に含まれる地点データの件数が非常に多い場合、演算負荷が増大し、検索時間が長くなる。一方、エンタープライズ用のサーバは、高速な中央処理装置を備えるため、演算負荷による検索時間の影響は小さいと言える。
【０００９】
上記では、検索範囲に含まれる地点データの件数が非常に多い場合に、ディスクアクセスと演算負荷の面で、問題があることを述べた。また、検索範囲に含まれる地点データが質問件数未満の場合でも、質問件数を満たすまで、検索処理を繰り返すため、上記と同様の問題が発生する。
【００１０】
この問題を解決するため、空間データベースが、質問件数と質問地点付近の地点データの存在密度に基づき、検索範囲を適切な大きさに設定する方法が考えられる。しかし、この方法は、組込機器に適切な方法とは言えない。それは、組込機器にとって、地点データの挿入や削除が発生する状況において、地点データの存在密度の管理は、負荷の大きい処理になるためである。
【００１１】
以上より、組込機器で従来の範囲指定検索を用いたｋ最近傍検索は、検索時間が増大する、という課題が生じる。
【００１２】
次に、第２の問題として、検索実行中のメモリ使用量が多くなる場合、検索処理を実行できない。または検索時間が長くなる。
【００１３】
従来技術では、検索範囲に含まれる全ての地点データを主記憶装置上に保持し、質問地点からの距離を用いて、ソートする。そのため、検索範囲に含まれる地点データが多いと、メモリ使用量が増大する。この場合、組込機器は小容量の主記憶装置を備えるため、従来技術を実行できない可能性がある。
【００１４】
この問題を解決するため、主記憶装置のメモリ空間から溢れた地点データを、外部記憶装置に退避する方法がある。この方法では、地点データのソート処理で、ディスクアクセスが発生するため、検索時間が長くなる。
【００１５】
また、第３の問題として、従来のｋ最近傍検索と属性指定検索を組合せた場合、件数がk件未満の不正確な検索結果になる可能性がある。
【００１６】
ｋ最近傍検索と属性指定検索の組合せは、多種類の地点データを含むテーブルに対して、実行される。例えば、カーナビゲーション装置が管理する施設テーブルには、レストラン、駐車場、ガソリンスタンドなどが含まれる。さらに、施設の種類がレストランの場合、施設テーブルには、日本料理、イタリア料理、フランス料理など、細かい種別が含まれる。その際、ユーザは、質問地点と質問件数に加え、地点種別を設定し、ｋ最近傍検索を実行する。通常の空間データベースでは、テーブルが属性情報と座標情報を別々の列として管理する。そのため、ＳＱＬ（Structured Query Language）のWHERE句で、ｋ最近傍検索と属性指定の条件をAND演算子で結合する。
【００１７】
このとき、k最近傍検索で質問件数分の結果が得られても、属性指定で、質問件数未満に絞り込まれる場合がある。これは、ｋ最近傍検索で得られた地点データの集合と、属性指定で得られた地点データの集合で、積集合を取るためである。
【００１８】
この問題を回避するため、エンタープライズ用のデータベース管理システムでは、質問件数をk件より多く設定する方法が採用されている。つまり、検索結果が属性指定で絞り込まれても、k件以上残る仕組みになっている。しかし、組込機器では、この方法は適切ではない。それは、質問件数が多い場合、必要な空間インデクスのページ数が増え、小容量の主記憶装置を備える組込機器では、ディスクアクセスが頻発し、検索時間が長くなるためである。一方、エンタープライズ用のサーバは大容量の主記憶装置を備えている。そのため、予め空間インデクスのページを主記憶装置に格納しておけば、質問件数が多くても、ディスクアクセスが頻発しない。
【００１９】
さらに、第４の問題として、上位k件の地点データが質問地点の付近に存在しない場合、検索時間が長くなる。
【００２０】
従来のｋ最近傍検索では、質問件数が満たされるまで、検索範囲が拡大される。質問地点の付近に所望の地点データが存在しない場合、検索結果が質問地点から数十キロも離れた地点データを含む可能性がある。検索範囲が拡大されると、必要な空間インデクスのページ数が増える。そのため、先に述べたように、小容量の主記憶装置を備えた組込機器では、検索時間が長くなる。
【００２１】
そこで本発明は、上記問題点に鑑みてなされたもので、空間データベースの検索時間を短縮しながら、検索処理中のメモリ使用量を抑制することを目的とする。
【課題を解決するための手段】
【００２２】
本発明は、多次元の地点データと、前記地点データを含む領域を複数の領域に分割して当該領域内に子領域を設定し、前記地点データと前記領域から枝と葉を含む木構造を作成した空間インデックスと、を含むデータベースと、前記データベースを管理するデータベース管理システムにおいて、検索の始点となる質問地点を受け付けて、前記質問地点から距離の近い上位ｋ件の質問件数の地点データを検索するｋ最近傍検索方法であって、前記質問地点と質問件数を検索条件に設定するステップと、前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定するステップと、前記最近領域が中間枝と判定されると、前記質問地点と最近領域の子領域との距離を領域距離として計算するステップと、前記領域距離の計算対象となった領域の情報を保持し、当該領域の最近領域を取得するステップと、前記最下位枝か中間枝かの判定結果で、前記最近領域が最下位枝と判定されると、前記質問地点と最近領域に内包される地点データの距離を地点距離として計算するステップと、前記地点距離の計算対象となった地点データの情報を保持するステップと、前記検索条件を満たすまで、前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定するステップ以降の検索処理を繰り返し、前記検索条件を満たした時点で前記検索処理を終了させるステップと、前記検索処理が終了した後に、前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得するステップと、を含む。
【発明の効果】
【００２３】
本発明は、範囲指定検索を用いた従来のｋ最近傍検索に比べ、空間インデックスのページへのディスクアクセス回数を削減できるため、検索時間を短縮できる。また、距離計算やソート処理の対象とする地点データを減らすため、プロセッサの演算負荷を軽減できる。さらに、検索実行中のメモリ使用量を抑制できる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の一実施形態を添付図面に基づいて説明する。
【００２５】
＜第１の実施形態＞
図１は、第１の実施形態を示し、本発明を適用するカーナビゲーション装置の一例を示すブロック図である。カーナビゲーション装置１は、演算処理を行うＣＰＵ（プロセッサ）３と、データやプログラムを一時的に格納するメモリ２と、データやプログラムを格納するストレージ装置５と、演算結果などを表示する表示装置４と、ユーザからの入力を受け付ける入力装置６と、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）衛星からの信号を受信するレシーバ１０を含んで構成される。
【００２６】
ストレージ装置５には、地図を構成する地物を点、線、面などの図形要素と、地物の内容を示す文字や数値などの属性要素を含む空間データベース１００が格納される。なお、空間データベース１００に格納された情報のうち、店舗や施設などひとつの地点の情報を地点データとする。
【００２７】
メモリ２には、空間データベース１００を管理するＤＢＭＳ（Ｄａｔａｂａｓｅ Ｍａｎａｇｅｍｅｎｔ Ｓｙｓｔｅｍ）８と、ＤＢＭＳ８を介して空間データベース１００を利用するアプリケーション９と、ＤＢＭＳ８とアプリケーション９を管理するＯＳ（オペレーティングシステム）７がロードされ、ＣＰＵ３により実行される。アプリケーション９は、レシーバ１０で受信したＧＰＳ衛星の信号から現在の位置を演算し、現在の地点データを空間データベース１００から検索し、地図情報を取得して表示装置４へ出力する。また、カーナビゲーション装置１では、入力装置６からユーザが検索の指令を受け付けると、アプリケーション９はＤＢＭＳ８を介して空間データベース１００を後述するように探索し、要求された検索結果を表示装置４に出力する。なお、ＯＳ７、ＤＢＭＳ８、アプリケーション９は記録媒体としてのストレージ装置５に格納され、カーナビゲーション装置１の起動時にメモリ２へロードされ、ＣＰＵ３によって実行される。
【００２８】
また、アプリケーション９は、ワークエリアとしてメモリ２上の領域を確保する。これらの領域は、後述する候補地点ヒープ９１、候補領域ヒープ９２、結果リスト９３等である。
【００２９】
ここで、本実施形態は、上記第１の問題と第２の問題を解決可能なｋ最近傍検索を実現する。本発明の適用範囲は、基本的に空間データの次元数と空間インデックス技術の種類によって、限定されない。本発明で利用可能な空間インデックス技術の要件は、
１．空間領域を再帰的に分割し、分割した領域の情報を記憶する枝を木構造の節とする
２．枝の領域範囲は前記枝の親の節にあたる枝の領域範囲に内包されるという階層的な構造をもつ
３．自身が小分割されない分割領域は当該分割領域が内包する地点データの情報を記憶する葉をもち、葉は木構造の最下位の節に接続していること
である。
【００３０】
以下の説明では、空間データベース１００に格納された２次元空間における地点データをカーナビゲーション装置１の検索対象とし、空間インデックス技術に四分木手法を適用する例を示す。
【００３１】
図１に示す空間データベース１００は、地図情報を構成する地点の座標と属性を格納した地点テーブル５０１と、地点テーブル５０１の索引情報を格納した空間インデックス１０１を含む。
【００３２】
まず、空間インデックス１０１は、空間データベース１００で管理する地点テーブル５０１に地点データを挿入する際に図示しない計算機によって作成される。本実施形態では、空間インデックス１０１の一例として、図４に示す領域分割テーブル４０１を採用した例を示す。また、地点テーブル５０１は、地点データの属性情報に加え、Ｘ座標とＹ座標から構成される座標情報を列に含む。例えば、カーナビゲーション装置１で管理する施設テーブルは、施設名、住所、電話番号などの属性情報と、施設の存在場所を平面直角座標系のＸ座標とＹ座標で表現した座標情報をもつことが考えられる。
【００３３】
四分木手法は、空間データベース１００への地点データの挿入に伴い、２次元空間のＸ軸とＹ軸に平行な面で４分割する。四分木手法では、一般に、分割領域で格納可能な地点データの最大個数を決め、地点データの挿入で、最大個数を超えた場合に、分割領域を４分割する。領域分割の方法には、４分割後の分割領域の面積を均等にする方法や、４分割後の分割領域内の地点データの個数をできるだけ均等にする方法などが提案されている。後者の方法は、例えば、分割対象の領域内の全ての地点データの重心座標で４分割することで、実現する。本発明のｋ最近傍検索は、領域の分割方法に依存せず、動作可能である。以下では、四分木手法のデータ構造について記載する。本発明は、空間インデックス技術の上で動作するｋ最近傍検索である。空間インデックス技術そのものに関する発明ではない。そのため、本実施例では、四分木の生成や探索の手順については公知の手法を適用すればよいので、これらの詳細な説明を省略する。
【００３４】
図２は、２次元空間内の一つの座標で位置を特定可能な地点データについて、四分木手法により空間領域２０１を階層的に分割した例を示す。空間領域２０１は分割線２０４で４分割される。各分割領域は、分割領域の識別子（領域ＩＤ）２０２をもつ。分割領域が、当該分割領域を４分割する領域をもたない場合、地点データ２０２を格納する。例えば、深さ３の分割領域３５は、地点データＧを格納する。この空間領域２０１は、多次元空間で各軸を通る面で階層的に分割した分割領域０〜３６を木構造で管理する空間インデックス１０１を構成する。
【００３５】
図３は、図２の領域分割に対応した木構造を示す。図３において、木構造の節に対応するものが枝３０１（図中円）であり、最下位の節と隣接するのが葉３０２（図中四角）である。枝３０１と分割領域は１対1の対応関係であり、枝３０１の数字は図２に示した領域ＩＤを指す。葉３０２内の英字は地点データＩＤを示す。地点データＩＤは、図２のＡ〜Ｍに対応する。実施形態の四分木手法は最下位の枝３０１が、当該枝に隣接する葉３０２の中に地点データの情報を格納する。
【００３６】
図４は、空間データベース１００の空間インデックス１０１に予め格納された分割領域テーブル４０１を示す。分割領域テーブル４０１は、四分木の枝３０１に格納される分割領域の情報を指す。図４は、分割領域テーブル４０１の属性４１１と、当該属性に対応する中間枝（図３では、分割領域０〜８に相当する）と最下位枝（図３では、分割領域２５〜２８、３３〜３６に相当する）の値を例示する。分割領域の情報は、領域ＩＤ４１２、領域範囲４１３、分割座標４１４、子領域ＩＤ４１５、子領域ポインタ４１６、葉ポインタ４１７、地点個数４１８を含む。
【００３７】
領域ＩＤ４１２は、分割領域を示す一意の識別子である。領域範囲４１３は、領域の左下頂点と右上頂点のＸ−Ｙ座標で表現する。分割座標４１４は領域を四分割した際の分割点の座標を示す。当該分割領域は、分割座標４１４を通り、かつＸ軸とＹ軸に平行な２本の直線で、４分割する。
【００３８】
子領域ＩＤ４１５は、当該領域を四分割した分割領域の識別子を示す。子領域ポインタ４１６は、子領域ＩＤ４１５が示す分割領域に対応した枝３０１を格納したストレージ装置５のアドレス値（例えば、ＬＢＡ（Logical Block Address））を示す。当該枝３０１が最下位枝である場合、当該枝３０１に対応した分割領域は子領域を持たない。最下位枝に対応する分割領域の分割座標４１４、子領域ＩＤ４１５、子領域ポインタ４１６はＮＵＬＬとする。葉ポインタ４１７は、当該枝３０１に隣接する葉３０２を格納したストレージ装置５のアドレス値を示す。地点個数４１８は、当該枝３０１に隣接する葉３０２が格納する地点データの個数を示す。当該枝３０１が中間枝である場合、当該枝３０１の葉ポインタ４１７はＮＵＬＬ、地点個数は０になる。
【００３９】
図５は、空間データベース１００の空間インデックス１０１に予め格納された地点テーブル５０１を示す。地点テーブル５０１は四分木の葉３０２に記憶され、地点データの情報を示す。この地点データは、葉３０２に隣接する最下位枝に対応する分割領域が内包する地点データである。各地点データの座標情報は、地点ＩＤ５１１、地点座標５１２、地点ポインタ５１３を含む。地点ＩＤ５１１は、当該地点データの一意の識別子である。地点座標５１２は、当該地点データの位置を特定する座標を示す。地点ポインタ５１３は、当該地点データに該当するレコードを格納したストレージ装置５のアドレス値を示す。
【００４０】
図６は、カーナビゲーション装置１のＣＰＵ３で実行されるｋ最近傍検索の手順を示すフローチャートである。この処理は、ＣＰＵ３で実行されるアプリケーション９が、入力装置６から質問地点を受信すると開始される。
【００４１】
ｋ最近傍検索の処理が開始されると、まず、初期設定部１１１ではＣＰＵ３が、質問地点や質問件数の設定及び候補領域管理部１１３や候補地点管理部１１６で利用するメモリ２の領域確保を行う（Ｓ１０１）。
【００４２】
次に、最下位枝判定部１１２では、最近領域が当該領域をさらに４分割する領域をもつか、つまり子領域をもつか否かを判定する（Ｓ１０２）。最近領域とは、結果候補に入るか否かを調査していない地点データを含む分割領域の中で、質問地点に距離が最も近い領域を示す。Ｓ１０２の条件を満たさない場合、最近領域が最下位枝でないと判定される。この場合、領域距離計算部１１３が、質問地点と最近領域の子領域との最短のユークリッド距離（領域距離ｄ）を計算する（Ｓ１０３）。
【００４３】
そして、候補領域管理部１１４が、最近領域の子領域を候補領域として、子領域の情報を記録する（Ｓ１０４）。候補領域とは、結果候補に入るか否かを調査していない地点データを含む分割領域を示す。その後、候補領域管理部１１４が、候補領域の中から領域距離ｄに基づき、次の最近領域を選択する（Ｓ１０５）。
【００４４】
一方、上記Ｓ１０２の条件を満たす場合、現在着目している最近領域が最下位枝であると判定される。この場合、地点距離計算部１１５が、質問地点と最近領域に含まれる地点データとの距離（地点距離ｄ’）を計算する（Ｓ１０６）。
【００４５】
次に、候補地点管理部１１６は、求めた地点距離ｄ’に基づき、質問地点に距離が近い上位ｋ件の地点データの情報を記録する（Ｓ１０７）。そして、終了判定部１１７は、候補領域内の地点データが候補になり得ないか否かを判定する（Ｓ１０８）。この終了条件を満たさない場合、Ｓ１０５の処理へ進み、検索処理を続行する。
【００４６】
一方、終了条件を満たす場合、結果取得部１１８は、候補地点管理部１１６が記憶した地点データに対応する結果レコードを取得する（Ｓ１０９）。
【００４７】
上記処理を終了条件が成立するまで繰り返すことで、検索結果を空間データベース１００から取得する。
【００４８】
図７は、ｋ最近傍検索の初期設定（Ｓ１０１：初期設定部１１１）の詳細な手順を示すサブルーチンのフローチャートである。
【００４９】
図７の初期設定処理は、図６の初期設定部１１１によって実行される。まず、初期設定部１１１は、質問地点と質問件数を、ｋ最近傍検索の入力値として設定する（Ｓ６０１）。質問地点と質問件数は、例えば、上記入力装置６から受け付けた値である。なお、質問地点は、入力装置６から検索指示を受け付けた時点のユーザの現在位置を用いても良い。
【００５０】
次に、初期設定部１１１は、メモリ２から、候補領域を記憶するメモリ領域をヒープ構造（以下、候補領域ヒープ９２）で確保する（Ｓ６０２）。ヒープ構造を用いる理由は、候補領域管理部１１４が最近領域の子領域の情報を記録する（Ｓ１０４）際の挿入操作と、次の最近領域を選択する際（Ｓ１０５）の選択操作で、効率の良いデータ構造だからである。
【００５１】
候補領域ヒープ９２は、領域ＩＤ４１２、領域情報ポインタ、領域距離ｄから構成される要素を格納する。領域情報ポインタは、当該領域に対応する枝３０１を格納したストレージ装置５のアドレス値を示す。領域距離ｄは、質問地点と当該領域までの最短距離を示す。候補領域ヒープ９２は木構造で管理される。候補領域ヒープ９２は、要素の挿入や削除があっても、各要素の領域距離ｄが、当該要素の子要素の領域距離ｄより小さいか等しいというヒープ条件を満たす。つまり、候補領域ヒープ９２の根要素は、最小の領域距離ｄをもつ分割領域の情報を格納する。
【００５２】
初期設定部１１１は、メモリ２から、候補地点を記憶するメモリ領域をヒープ構造（以下、候補地点ヒープ９１）で確保する（Ｓ６０３）。ヒープ構造を用いる理由は、候補地点管理部１１６が上位ｋ件の地点データの情報を記録する（Ｓ１０７）際の挿入操作で、効率の良いデータ構造だからである。候補地点ヒープ９１は、地点ＩＤ５１１、地点ポインタ５１３、地点距離ｄ’から構成される要素を格納する。候補地点ヒープ９１は、要素の挿入や削除があっても、各要素の地点距離ｄ’が、当該要素の子要素の地点距離ｄ’より大きいか等しいというヒープ条件を満たす。つまり、候補地点ヒープ９１の根要素は、最大の地点距離ｄ’をもつ地点データの情報を格納する。この特徴により、候補地点がｋ件存在する状況で、ｋ＋１件目以降の地点データが候補に入るか否かを判定する場合、根要素を参照するだけで候補となるか否かを容易に判定できる。具体的には、判定対象の地点データの地点距離ｄ’が、根要素の地点データの地点距離ｄ’より小さければ、根要素の地点データに代わって判定対象の地点データが候補に入る。本操作により、メモリ上には常に上位k件の地点データのみが保持されることになり、検索実行中のメモリ使用量を抑制できる。
【００５３】
初期設定部１１１は、四分木の根にあたる領域を最近領域に設定し（Ｓ２０４）、サブルーチンを終了する。この場合、最近領域は全体の領域となる。その後、図６に示した最近領域の最下位枝判定の処理に進む（Ｓ１０２）。
【００５４】
図８は、最近領域に対する最下位枝判定（Ｓ１０２）の詳細な手順を示すサブルーチンのフローチャートである。最下位判定の処理は、最下位枝判定部（１１２）によって実行される。まず、初期設定部１１１のＳ６０４で決定した最近領域に対応する四分木の枝情報を取得する（Ｓ７０１）。枝情報は、ストレージ装置５の空間データベース１００内に予め格納されている。次に、図４に示した分割領域テーブル４０１を参照して、当該枝情報の分割領域の座標がＮＵＬＬか否かを判定する。この条件により、最近領域が最下位枝であるか否かを判定できる。当該条件を満たさず、最近領域が中間枝の場合、質問地点と最近領域の子領域との領域距離ｄを計算する処理（Ｓ１０３）へ進むため、次の処理として領域距離計算部１１３を選択する（Ｓ７０３）。当該条件を満たし、最近領域が最下位枝である場合は、質問地点と最近領域に内包される地点データとの距離を計算する処理（Ｓ１０６）に進むため、次の処理として地点距離計算部１１５を選択する（Ｓ７０４）。そして、サブルーチンを終了するとステップＳ７０３またはＳ７０４の何れかで選択した処理に分岐する。
【００５５】
図９は、領域距離計算（Ｓ１０３）の詳細な手順を示すサブルーチンのフローチャートである。領域距離計算の処理は、領域距離計算部１１３よって実行される。領域距離計算部１１３は、分割領域テーブル４０１を参照して、質問地点と最近領域の子領域との領域距離ｄを計算する。領域距離ｄの計算には、子領域の領域範囲が必要になる。子領域の領域範囲は、最近領域の枝情報の領域範囲４１３と分割座標４１４の情報から求める。ここでは、図４で示したように、最近領域の左下頂点の座標を（Ｘｍｉｎ、 Ｙｍｉｎ）、右上頂点の座標を（Ｘｍａｘ、 Ｙｍａｘ）で表現する。また、分割座標４１４を（Ｘｄｉｖ、 Ｙｄｉｖ）で示す。
【００５６】
まず、領域距離計算部１１３は、最近領域の左下子領域の領域範囲を、左下頂点の座標が（Ｘｍｉｎ、 Ｙｍｉｎ）、右上頂点の座標が（Ｘｄｉｖ、 Ｙｄｉｖ）とする（Ｓ８０１）。
【００５７】
次に、最近領域の右下子領域の領域範囲を、左下頂点の座標が（Ｘｄｉｖ、 Ｙｍｉｎ）、右上頂点の座標が（Ｘｍａｘ、 Ｙｄｉｖ）とする（Ｓ８０２）。最近領域の左上子領域の領域範囲を、左下頂点の座標が（Ｘｍｉｎ、 Ｙｄｉｖ）、右上頂点の座標が（Ｘｄｉｖ、 Ｙｍａｘ）とする（Ｓ８０３）。最近領域の右上子領域の領域範囲を、左下頂点の座標が（Ｘｄｉｖ、 Ｙｄｉｖ）、右上頂点の座標が（Ｘｍａｘ、 Ｙｍａｘ）とする（Ｓ８０４）。
【００５８】
次に、領域距離計算部１１３は、次の式（１）を用いて、左下、右下、左上、右上の子領域の領域距離ｄをそれぞれ計算する（Ｓ８０５）。
【００５９】
【数１】
【００６０】
ただし、
分割領域Ｒと質問地点（ｘ、ｙ）との距離値ｄ
分割領域Ｒの範囲： 左下座標（Ｘｍｉｎ、 Ｙｍｉｎ）、右上座標（Ｘｍａｘ、 Ｙｍａｘ）
である。
【００６１】
上記式（１）では、質問地点の座標を（x、y）、分割領域の左下頂点の座標を（Ｘｍｉｎ、 Ｙｍｉｎ）、右上頂点の座標を（Ｘｍａｘ、 Ｙｍａｘ）で表記する。式（１）は、分割領域の境界線上の点の中で、質問地点に最も近い点と、質問地点との距離ｄの二乗を示す。分割領域が質問地点を含む場合、当該分割領域の距離は０になる。
【００６２】
図１０は、上記領域距離ｄを例示したものである。質問地点１００１から図中の分割領域１、２、３、４までの各距離ｄ1、ｄ2、ｄ3、ｄ4は矢印１００２で示される。本実施形態では、式（１）で計算した距離ｄを用いる。なお、実環境では、ｄの二乗をそのまま領域距離ｄに用いて、計算負荷を軽減する方法もある。Ｓ８０６の領域距離ｄの計算後、領域距離計算部１１３は、各子領域の領域ＩＤ４１２、領域ポインタ、領域距離ｄを候補領域管理部１１４に渡す（Ｓ８０６）。これらの処理が完了するとサブルーチンを終了し、図６のステップＳ１０４に進む。
【００６３】
図１１は、最近領域の子領域情報の記録（Ｓ１０４）の詳細な手順を示すサブルーチンのフローチャートである。当該処理は、候補領域管理部１１４によって実行される。まず、候補領域管理部１１４は、領域距離計算部１１３から受け付けた子領域ＩＤ４１５、子領域ポインタ４１６、領域距離ｄから構成される候補領域ヒープ９２の要素を生成する（Ｓ１１０１）。以下のステップでは、候補領域管理部１１４が子領域を一つずつ選択する。次に、候補領域管理部１１４は、Ｓ１１０２からＳ１１０４、Ｓ１１０７のステップで、候補領域ヒープ９２の条件を満たすように、子領域の情報を挿入する。子領域の情報を挿入する操作の前に、ヒープの実現方法について説明する。
【００６４】
図１２は、候補領域ヒープ９２に適用するヒープ木１２０１を一次元配列１２０２で実現した例を示す。図１２において、ヒープ木１２０１の節１２０３内の番号は要素の識別子を示し、節付近の<>１２０４内の数値は予め設定した基準値を示す。ヒープ木１２０１は、候補領域ヒープ９２と同じヒープ条件で、根要素の基準値が最小になるように管理されている。一次元配列１２０２は、ヒープ木１２０１の深さが浅いほど、深さが同じ場合は左から順に、先頭から要素を格納する。
【００６５】
次に、図１１において、候補領域管理部１１４は、まず、要素を候補領域ヒープ９２の末尾に要素を挿入する（Ｓ１１０２）。末尾とは、一次元配列の末尾を指す。次に、候補領域管理部１１４は挿入要素が根に格納されているか判定する。根の格納位置は、一次元配列の０番目になる。
【００６６】
当該条件を満たさない場合、挿入要素の領域距離ｄが親要素の領域距離ｄより小さいか否かを判定する（Ｓ１１０４）。当該条件を満たす場合、候補領域ヒープ９２のヒープ条件を満たさないことになる。この場合、候補領域管理部１１４は、挿入要素と親要素の格納位置を交換する（Ｓ１１０７）。一次元配列では、挿入要素の格納位置がｉの場合、格納位置がｉ／２を超える最小の整数に１を差し引いた値が親要素となる。
【００６７】
ステップＳ１１０３の条件を満たした場合、またはＳ１１０４の条件を満たさなかった場合には、候補領域ヒープ９２のヒープ条件を満たすことになる。この場合、候補領域管理部１１４は、全ての子領域の情報を候補領域ヒープ９２に挿入したかを否かを判定する。当該条件を満たさなければ、Ｓ１１０１の処理へ進み、子領域の情報をヒープに挿入する。一方、当該条件を満たせばサブルーチンを終了して、図６に示す次の最近領域の選択へ処理を進める（Ｓ１０５）。
【００６８】
図１３は、最近領域の選択（Ｓ１０５）の詳細な手順を示すサブルーチンのフローチャートである。最近領域の選択の処理は、候補領域管理部１１４によって実行される。まず、候補領域管理部１１４は、候補領域ヒープ９２の根要素に対応する領域を最近領域に設定する（Ｓ１３０１）。次に、候補領域管理部１１４は、候補領域ヒープ９２の根要素を削除する（Ｓ１３０２）。その後、候補領域管理部１１４は、候補領域ヒープ９２内に要素が存在するか判定する（Ｓ１３０３）。当該条件を満たす場合、候補領域管理部１１４は、ステップＳ１３０４からＳ１３０７の処理によって、根要素の削除に伴う候補領域ヒープ９２の再構築を実行する。ステップＳ１３０３の上記条件を満たさない場合、候補領域管理部１１４は候補領域ヒープ９２を再構築する必要がないためサブルーチンを終了して、図６に示した最近領域の最下位枝判定（Ｓ１０２）に進める。
【００６９】
一方、ステップＳ１３０３で要素が候補領域ヒープ９２に存在するときには、候補領域管理部１１４が、根要素に候補領域ヒープ９２の末尾（移動要素）を移動させる（Ｓ１３０４）。一次元配列では、格納位置が末尾の要素を、格納位置が０の場所に移動させることになる。次に、候補領域管理部１１４は、移動要素が子要素をもつか否かを判定する（Ｓ１３０５）。当該条件を満たさない場合、候補領域ヒープ９２のヒープ条件を満たす。この場合、候補領域管理部１１４はサブルーチンを終了して次の処理である最近領域の最下位枝判定（Ｓ１０２）に進む。一方、ステップＳ１３０５の当該条件を満たす場合、候補領域管理部１１４は、移動要素の領域距離ｄが子要素の領域距離ｄより大きい値か否かを判定する（Ｓ１３０６）。当該条件を満たす場合、候補領域ヒープ９２のヒープ条件を満たさない。この場合、候補領域管理部１１４は移動要素と子要素の格納位置を交換して、ステップＳ１３０５に戻る（Ｓ１３０７）。なお、二つの子要素がステップＳ１３０６の条件を満たす場合、領域距離ｄの小さい子要素が交換対象となる。一次元配列では、移動要素の格納位置がｉの場合、格納位置が２×ｉ＋１、または２×ｉ＋２の子要素と交換することになる。
【００７０】
上記ステップＳ１３０６の条件を満たさない場合、候補領域ヒープ９２がヒープ条件を満たす。この場合、候補領域管理部１１４はサブルーチンを終了して次の処理である図６に示す処理対象領域の最下位枝判定（Ｓ１０２）に進む。
【００７１】
図１４は、地点距離計算（Ｓ１０６）の詳細な手順を示すサブルーチンのフローチャートである。地点距離計算の処理は、地点距離計算部１１５によって実行される。まず、地点距離計算部１１５は、最近領域に隣接する葉情報を取得する（Ｓ１４０１）。地点距離計算部１１５は、分割領域テーブル４０１に格納された最近領域の領域情報の葉ポインタ４１７を参照することで、葉情報を取得できる。次に、地点距離計算部１１５は、葉情報における先頭の地点を座標情報読取ポインタに設定する（Ｓ１４０２）地点距離計算部１１５は、座標読取ポインタの指す地点を処理対象地点に設定する（Ｓ１４０３）。その後、地点距離計算部１１５は、ステップＳ１４０４において式（２）を用いて、質問地点と地点データの地点距離ｄ’を計算する。
【００７２】
【数２】
【００７３】
式（２）において、地点距離ｄ’は、質問地点（ｘ、ｙ）と処理対象地点（x’、y’）とのユークリッド距離になる。実環境では、平方根の計算が検索時間の遅延に大きく影響を及ぼす場合がある。この場合、地点距離ｄ’と領域距離ｄを二乗のままで、ｋ最近傍検索を実行しても良い。そして、地点距離計算部１１５は、サブルーチンを終了して図６に示した次の処理である、候補地点ヒープ９１に処理対象地点を候補地点として記録する処理（Ｓ１０７）に進む。なお、ステップＳ１４０５の処理は、後述のステップＳ１５０８から実行される処理であり、地点データを１点ずつ距離計算し、候補地点ヒープ９１に記録することを意味する。
【００７４】
図１５は、候補地点ヒープ９１への候補地点の記録（Ｓ１０７）の詳細な手順を示すサブルーチンのフローチャートである。候補地点の記録処理は、候補地点管理部１１６によって実行される。まず、候補地点管理部１１６は、処理対象地点の候補地点ヒープ９１用の要素を生成する（Ｓ１５０１）。当該要素は、処理対象地点の地点ＩＤ５１１、地点距離ｄ’、地点ポインタ５１３から構成される。次に、候補地点管理部１１６は、処理対象地点ヒープの要素数が質問件数と等しいかを判定する。既に候補地点ヒープ９１が上位ｋ件の地点データを記憶しているか否かで、これ以降の処理内容が異なる。
【００７５】
まず、ステップＳ１５０２の条件を満たす場合、既に候補地点ヒープ９１が質問件数を満たすことになる。この場合、候補地点管理部１１６は、処理対象地点の地点距離ｄ’が、候補地点ヒープ９１の中で質問地点に最も遠い地点データの地点距離ｄ’より小さいか否かを判定する（Ｓ１５０３）。候補地点ヒープ９１の中で質問地点に最も遠い地点データは、候補地点ヒープ９１の根要素になる。当該条件を満たす場合、候補地点ヒープ９１の根要素に代わり、処理対象地点が新しく候補地点に入ることを意味する。
【００７６】
ステップＳ１５０４からＳ１５０７までの処理で、候補地点管理部１１６が、ヒープ条件を満たしながら、処理対象地点を候補地点ヒープ９１に記録する。一方、Ｓ１５０３の条件を満たさない場合、処理対象地点が候補地点に入らないことを意味する。この場合、候補地点管理部１１６は、ステップＳ１５０８の処理へ進む。
【００７７】
次に、上記ステップＳ１５０２の条件を満たさない場合、まだ、候補地点ヒープ９１が質問件数を満たしていないことになる。この場合、候補地点管理部１１６は、処理対象地点の要素を候補地点ヒープ９１に挿入することを前提にする。候補地点管理部１１６は、ステップＳ１５１０からＳ１５１２の処理で、ヒープ条件を満たしながら、処理対象地点の要素を候補地点ヒープ９１に格納する。
【００７８】
次に、候補地点管理部１１６は、ステップＳ１５０８に進むと、最近領域の全ての地点データについて、候補地点になるか否かを調査したかを判定する。当該条件を満たす場合、候補地点管理部１１６はサブルーチンを終了して図６に示した終了判定（Ｓ１０８）へ進める。一方、Ｓ１５０８の条件を満たさない場合、候補地点管理部１１６は処理を図１４に示したステップＳ１４０５へ進ませて、ループの度に地点データを１点ずつ距離計算し、候補地点ヒープ９１に記録する。
【００７９】
図１６は、終了判定（Ｓ１０８）の手順を示すフローチャートである。終了判定の処理は、終了判定部１１７によって実行される。まず、終了判定部１１７は、候補地点ヒープ９１に要素が存在するか否かを判定する。当該条件を満たさない場合、次に調査すべき分割領域が存在しないことになる。したがって、終了判定部１１７は、次に行う処理として図６に示した処理として検索結果の取得（Ｓ１０９）を選択する（Ｓ１６０４）。
【００８０】
一方、ステップＳ１６０１の条件を満たす場合、候補領域ヒープ９２の根要素の領域距離ｄが候補地点ヒープ９１の根要素の地点距離ｄ’より大きいか否かを判定する（Ｓ１６０２）。当該条件を満たす場合、検索処理を終了とみなす。終了条件は、候補領域ヒープ９２の根要素の領域距離ｄが、候補地点ヒープ９１の根要素の地点距離ｄ’より大きいという条件である。この条件は、さらに広い範囲に存在する分割領域内の地点データを調査しても、候補地点に入る地点データを見つけることができないことを意味する。終了条件の判定は、候補領域と候補地点の記憶にヒープ構造を用いているため、候補地点ヒープ９１内をＯ（１）の探索回数で、実現できる。ステップＳ１６０２の条件を満たす場合、終了判定部１１７は次の処理として図６に示した検索結果の取得（Ｓ１０９）を選択してサブルーチンを終了する。一方、ステップＳ１６０２の条件を満たさない場合、別の分割領域に内包される地点データを調査するため、次に行う処理を図６に示した最近領域の選択（Ｓ１０５）としてサブルーチンを終了する。
【００８１】
図１７は、検索結果の取得（Ｓ１０９）の詳細な手順を示すサブルーチンのフローチャートである。検索結果の取得処理は、結果取得部１１８によって実行される。この処理によって、結果取得部１１８は、質問地点から距離の近い順に地点データを取得する。
【００８２】
まず、結果取得部１１８は、候補地点ヒープ９１の根要素を結果リスト９３の末尾に挿入する（Ｓ１７０１）。結果リスト９３は、候補地点ヒープ９１と同じ要素を格納可能な一次元配列であり、結果取得部１１８がメモリ２上に予め確保した領域である。次に、結果取得部１１８は、候補地点ヒープ９１の根要素を削除する（Ｓ１７０２）。その後、結果取得部１１８は、要素が候補地点ヒープ９１に存在するか否かを判定する（Ｓ１７０３）。当該条件を満たす場合、結果取得部１１８は、ステップＳ１７０４からＳ１７０７の処理で、根要素の削除に伴う候補地点ヒープ９１の再構築を行う。ステップＳ１７０３の条件を満たさない場合、結果取得部１１８は、結果リスト９３の末尾から先頭に向かい、地点データを一つずつ取得する（Ｓ１７０８）。当該地点データは、地点座標５１２と任意個数の属性を含む、空間データベース１００で管理されるレコードとなる。
【００８３】
以上より、本処理は、まず、地点距離ｄ’の大きい順にヒープソートを行い、その結果を一次元配列で構成した結果リスト９３の先頭から順に記憶しておく。そして、当該一次元配列の末尾から先頭に向かい地点データを取得することで、質問地点から距離の近い順に地点データを取得していく。地点データの要素数をＮとした場合に、ヒープソートの探索回数はＯ（Ｎ・ｌogＮ）となり、一次元配列内の探索回数はＯ（Ｎ）となり、結果を得るまでの探索回数をＯ（Ｎ・logＮ）に抑えることができる。結果取得部１１８がステップＳ１７０８の処理を終えると、ｋ最近傍検索が終了する。
【００８４】
上述したｋ最近傍検索の具体的なアルゴリズムの動作について、図１８ａ〜図１８ｃ、図１９、図２０を用いて、説明する。
【００８５】
まず、図１８ａは、上記図２に示した空間領域２０１を、図２に示した深さ０の階層の真上から鳥瞰した空間領域１８０３を示す。この空間領域８０３は、上記ｋ最近傍検索で質問地点１８０４と質問件数を５に設定した場合の例を示す。図中丸印の内部の数値は領域ＩＤ４１２を示し、図中方形の枠内の文字は地点ＩＤ５１１を示す。図１８ｂは、上記ｋ最近傍検索の処理過程で計算した空間領域１８０３における領域距離ｄを表形式で図示したテーブル１８０１である。図１８ｃは、上記ｋ最近傍検索の処理過程で計算した空間領域１８０３における地点距離ｄ’を表形式で図示したテーブル１８０２である。なお、テーブル１８０１、１８０２の情報は、メモリ２上の候補領域ヒープと候補地点ヒープにそれぞれ保持される。
【００８６】
図１９は、図１８ａの空間領域１８０３を用いて、ｋ最近傍検索を実行した際の候補領域ヒープ９２の格納状況を示す。候補領域ヒープ９２を木構造で表現する。ヒープ木の節１９０１内の数字は領域ＩＤ４１２、山括弧１９０２内の数値は領域ＩＤ４１２で示す分割領域間の距離を示す。
【００８７】
図２０は、図１８ａに示した空間領域１８０３を用いて、ｋ最近傍検索を実行した際の候補地点ヒープ９１の格納状況を示す。候補地点ヒープ９１を木構造で表現する。ヒープ木の節２００１内のアルファベットは地点ＩＤ５１１、山括弧２００２内の数値は地点ＩＤ５１１で示す地点データの地点距離ｄ’を示す。
【００８８】
ｋ最近傍検索を実行すると、まず、初期設定部１１１が最近領域を領域０に設定する。領域距離計算部１１３が領域０の子領域１、２、３、４の領域距離ｄを計算し、子領域の領域情報を候補領域ヒープ９２に格納する（図１９の（１））。次に、候補領域管理部１１４は最近領域を領域１に設定し、候補領域ヒープ９２から領域１の情報を削除する。そして、候補領域管理部１１４が領域１の子領域５、６、７、８の情報を候補領域ヒープ９２に格納する（図１９の（２））。上記と同様に候補領域管理部１１４は、最近領域を領域８に設定する。同様に、候補領域ヒープ９２から領域８の情報を削除し、領域８の子領域３３、３４、３５、３６の情報を候補領域ヒープ９２に挿入する（図１９の（３））。候補領域管理部１１４は最近領域を最下位枝の領域３３に設定する。この場合、領域３３の情報を候補領域ヒープ９２から削除し、領域３３に内包される地点データＥの情報を、候補地点ヒープ９１に挿入する。この時点の候補領域ヒープ９２の格納状況を図１９の（４）に示し、候補地点ヒープ９１の格納状況を図２０の（１）に示す。最近領域を領域３５に設定すると、領域３３と同様に、候補領域ヒープ９２と候補地点ヒープ９１が更新される（図１９（５）と図２０（２））。
【００８９】
以下、同様に処理を進めると、候補領域ヒープ９２と候補地点ヒープ９１の格納状況はそれぞれ図１９の（１１）と図２０の（６）に示すようになる。このとき、候補地点ヒープ９１の根要素（地点データＩ）の地点距離ｄ’が、候補領域ヒープ９２の根要素（領域２５）の領域距離ｄより小さくなる。終了条件を満たすため、ｋ最近傍検索の結果は、地点データＩ、Ｆ、Ｇ、Ｅ、Ｃとなる。
【００９０】
なお、実施の形態１と同等の機能をもつｋ最近傍検索プログラムを記録した媒体やｋ最近傍検索装置も、本発明に含まれる。この点は、以降の説明で記載する実施の第２の実施形態や第３の実施形態でも同様である。
【００９１】
以上のように本発明の第１の実施形態によれば、検索実行時の空間インデックス１０１へのディスクアクセス回数を削減することが可能となって、前記従来例のように範囲指定検索を用いたｋ最近傍検索に比べ、検索時間を短縮できる。さらに、第１の実施形態では、必要最低限の地点データのみ距離計算の対象とするため、従来のｋ最近傍検索に比べ、ＣＰＵ３の演算負荷を軽減することが可能となる。
【００９２】
＜第２の実施形態＞
第２の実施形態は、第１の実施形態を拡張し、上述の第３の問題を解決する属性指定のｋ最近傍検索を実現する。
【００９３】
具体的には、第１の実施形態の図５に示した地点テーブル５０１を拡張して、図２１に示す地点テーブル２１０１を採用する。地点テーブル２１０１は、地点データを格納するテーブルの座標情報に、地点ＩＤ５１１、Ｘ座標とＹ座標の地点座標５１２、地点ポインタ５１３に加え、地点種別５１４を追加する。例えば、カーナビゲーション装置１の施設テーブルの場合、地点種別に、レストラン、駐車場、ガソリンスタンドなどの地点データの種類を格納することが考えられる。座標情報への地点種別５１４の追加に伴い、四分木の葉情報において、各地点の座標情報にも地点種別５１４を追加する。
【００９４】
第２の実施形態の処理は、基本的に第１の実施形態に示した図６のフローチャートに従う。ただし、第２の実施形態は、図６に記載の検索の初期設定Ｓ１０１と、地点距離ｄ’の計算Ｓ１０６の処理内容の一部を変更した。以下では、本形態の実現のために変更した処理内容について説明する。
【００９５】
図２２は、第２の実施形態における検索の初期設定（Ｓ１０１）の手順を示すサブルーチンのフローチャートである。第１の実施形態の図７と異なる部分は、図７のステップＳ６０１をステップＳ２２０１のステップに変更した点である。ステップＳ２２０１において、初期設定部１１１は、質問地点の座標と質問件数に加えて、地点種別を設定する。本形態によるｋ最近傍検索の実行結果は、当該地点種別に一致する地点データのみを含む。なお、ステップＳ２２０２〜Ｓ２２０４は、第１の実施形態の図７のステップＳ６０２〜Ｓ６０４と同一である。
【００９６】
図２３は、第２の実施形態の地点距離計算（Ｓ１０６）の手順を示すサブルーチンのフローチャートである。図２３は、第１の実施形態の図１４のフローチャートに対して、ステップＳ２３０４とステップＳ２３０７を加え、ステップＳ２３０７の判定がＹＥＳの場合には、終了判定部１１７の処理（Ｓ１０８）へ移行するようにした点が異なる。
【００９７】
ステップＳ２３０４において、地点距離計算部１１５は、処理対象地点の地点種別が上記初期設定部１１１のステップＳ２２０１で設定した地点種別に一致するか判定する。この判定の結果、ＮＯであればステップＳ２３０６に進む、Ｓ２３０４により、第２の実施形態は、指定した属性値に一致する地点データのみを取得できる。なお、図２３において、ステップＳ２３０１〜Ｓ２３０３、Ｓ２３０５、Ｓ２３０６は、第１の実施形態に示した図１４のステップＳ１４０１〜Ｓ１４０４、Ｓ１４０５と同一である。
【００９８】
以上、本発明の第２の実施の形態によれば、属性指定検索とｋ最近傍検索を組み合わせた場合でも、従来のｋ最近傍検索に比べ、検索実行時間を短縮できる。これは、第２実施では、空間インデックス１０１の探索のみで、ｋ最近傍検索を実行できるためである。また、第２の実施の形態では、指定した属性値に一致するｋ件の地点データを正確に取得できる。これは、第２の実施の形態が、検索対象の地点テーブル２１０１において、座標情報と属性情報を含む一つの列に対して、ｋ最近傍検索を実行できるためである。
【００９９】
＜第３の実施形態＞
第３の実施の形態は、第１の実施形態を拡張し、上述の第４の問題を解決する最近傍検索を提供する。第３の実施形態の処理は、基本的に第１の実施形態に示した図６のフローチャートに従う。具体的には、検索処理中であっても、検索処理を中断できるように、検索条件に中断条件を設ける。例えば、中断条件は質問地点からの距離で記述する。この場合、当該距離の範囲に存在する地点データが見つからない時点で、検索処理を中断する。また、中断条件として、最大処理時間の設定も効果的である。この場合、検索処理に費やすことができる時間を最大処理時間に設定し、検索処理の経過時間が最大処理時間と等しくなった時点で、検索処理を中断する。以下では、第３の実施形態の中断条件に距離を用いた場合で説明する。
【０１００】
初期設定部１１１で質問地点からの最大距離値（以下、質問距離と呼ぶ）を設定し、質問距離以下の地点データを発見できない時点で、質問件数を満たさずとも、検索処理を終了させる。なお、第３の実施形態による第１の実施形態への拡張は、第２の実施形態でも同様に適用でき、上述の第４の問題を解決できる。第３の実施形態は、第１の実施形態に示した図７に記載の検索の初期設定Ｓ１０１、領域距離ｄの計算を行うステップＳ１０３、地点距離ｄ’の計算を行うステップＳ１０６の処理内容を変更する。以下では、第３の実施形態の実現のために変更した処理内容について説明する。
【０１０１】
図２４は、第３の実施の形態における初期設定（Ｓ１０１）の手順を示すサブルーチンのフローチャートである。このフローチャートは、第１の実施形態に示した図７のステップＳ６０１を、ステップＳ２４０１に置き換えたものである。ステップＳ２４０１において、初期設定部１１１は、質問地点の座標と質問件数に加えて、質問距離を設定する。第３の実施形態によるｋ最近傍検索の実行結果は、質問地点からの距離値が質問距離以下の地点データのみを含む。なお、ステップＳ２４０２〜Ｓ２４０４は、第１の実施形態の図７のステップＳ６０２〜Ｓ６０４よ同一である。
【０１０２】
図２５は、第３の実施の形態における領域距離計算の手順を示すサブルーチンのフローチャートである。このフローチャートは、第１の実施形態に示した図９のステップＳ８０６を、ステップＳ２５０６に置き換えたものである。ステップＳ２５０６の処理において、領域距離計算部１１３は、質問距離以下の領域距離ｄをもつ子領域を対象に、領域ＩＤ４１２、領域ポインタ、領域距離ｄを候補領域管理部に渡すことにしている。Ｓ２５０６の処理によって、候補領域ヒープ９２は、質問距離以下の領域距離ｄをもつ分割領域の情報のみを記録することになる。質問距離以下の領域距離ｄをもつ分割領域は、質問距離の条件を満たし、結果候補に入る可能性のある地点データを内包する。なお、ステップＳ２５０１〜Ｓ２５０５は、第１の実施形態の図９に示したステップＳ８０１〜Ｓ８０５と同一である。
【０１０３】
図２６は、第３の実施の形態における地点距離の計算の手順を示すサブルーチンのフローチャートである。このフローチャートは、第１の実施形態に示した図１４のステップＳ１４０４以降に、ステップＳ２６０５、Ｓ２６０７を加えたものである。
【０１０４】
ステップＳ２６０４で処理対象地点の地点距離ｄ’を計算した後で、当該地点距離ｄ’が質問距離以下であるかを判断する処理（Ｓ２６０５）を追加し、該条件を満たす場合、候補地点の記録の処理（Ｓ１０７）へ進む。当該条件を満たさない場合、処理対象地点が検索結果に入らないため、すべての地点データを処理していなければ（Ｓ２６０７でＮＯを選択）、次の地点データの地点距離ｄ’の計算へ進める。なお、ステップＳ２６０１〜Ｓ２６０４、Ｓ２６０６は、第１の実施形態に示した図１４のステップＳ１４０１〜１４０４、Ｓ１４０５と同一である。
【０１０５】
以上、本発明の第３の実施の形態によれば、ｋ最近傍検索の実行結果の近傍性を保証できる。これは、第３の実施の形態が、検索条件に中断条件を設定できるためである。中断条件は、例えば、質問地点からの最大距離や検索処理に費やすことのできる最大処理時間である。
【０１０６】
＜第４の実施形態＞
第４の実施形態は、ｋ最近傍検索をデータベース管理システム８で実行する場合に記述する問合せ言語、または関数に関する。第４の実施形態は、例えば、アプリケーション開発者が、アプリケーションプログラムからデータベース管理システム８にｋ最近傍検索を要求する場合のＳＱＬに相当する。以下では、データベース管理システム８の一般的な問合せ言語であるＳＱＬを用いて、第４の実施形態について説明する。
【０１０７】
図２７ａ〜図２７ｄは、第１の実施形態、第２の実施形態または第３の実施形態のいずれかで実現されるｋ最近傍検索のためのＳＱＬの記述方法である。なお、図２７ａ〜図２７ｄでは、空間データベース１００が、地点データを格納する一つのテーブルに対して、ｋ最近傍検索に合致するレコードの全ての列を取得する場合を示す。
【０１０８】
図２７ａの２７０１に記載のＳＱＬは、第１の実施形態で実現したｋ最近傍検索のみで利用可能である。２７０１において、ＷＨＥＲＥ句のｋＮＮ（ｋ−Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ）は、ｋ最近傍検索のためのスカラー関数を示す。ｋＮＮ関数の第１引数は検索対象テーブルの座標列名、第２引数は質問地点、第３引数は質問件数となる。
【０１０９】
図２７ｂの２７０２に記載のＳＱＬは、第１の実施形態または第２の実施形態で実現したｋ最近傍検索で利用可能である。２７０２のｋＮＮ関数の第１引数は検索対象テーブルの座標列名、第２引数は質問地点、第３引数は質問件数、第４引数は地点データの種別となる。なお、第１の実施形態で実現したｋ最近傍検索は、種別を設定する必要がないため、第４引数にＮＵＬＬを設定する。
【０１１０】
図２７ｃの２７０３に記載のＳＱＬは、第１の実施形態または第３の実施形態で実現したｋ最近傍検索で利用可能である。２７０３のｋＮＮ関数の第１引数は検索対象テーブルの座標列名、第２引数は質問地点、第３引数は質問件数、第４引数は質問距離となる。なお、第３の実施形態で実現したｋ最近傍検索は、質問距離を設定する必要がないため、第４引数にＮＵＬＬを設定する。
【０１１１】
図２７ｃの２７０４に記載のＳＱＬは、第１の実施形態、第２の実施形態、第３の実施形態のどの場合で実現したｋ最近傍検索でも利用可能である。２７０４のｋＮＮ関数の第１引数は検索対象テーブルの座標列名、第２引数は質問地点、第３引数は質問件数、第４引数は地点データの種別、第５引数は質問距離となる。また、この記載方法は、第３の実施形態２と形態３を組み合わせたｋ最近傍検索でも利用可能である。なお、第３の実施形態で実現したｋ最近傍検索は、質問距離を指定する必要がないため、第４引数と第５引数にＮＵＬＬを設定する。形態２で実現したｋ最近傍検索は、質問距離を設定する必要がないため、第５引数にＮＵＬＬを設定する。形態３で実現したｋ最近傍検索は、種別を設定する必要がないため、第４引数にＮＵＬＬを設定する。
【０１１２】
以上、本発明の第４の実施の形態によれば、アプリケーションプログラム開発者がｋ最近傍検索をＳＱＬで記述できることで、プログラムの開発期間を短縮できる。
【０１１３】
以上の四つの実施の形態では、地理空間内の地点データを対象に、ｋ最近傍検索方法について説明した。ここで、本発明は、地理空間内の地点データへの適用に限るものではない。本発明は、テレビ番組や楽曲など、特徴ベクトルで表現可能なデータにも適用でき、類似検索を実現できる。例えば、テレビ番組の場合、第一特徴ベクトルにシリアスとバラエティを軸に取り、第二特徴ベクトルにフィクションとノンフィクションを軸に取る。そして、これらを軸とした二次元空間にテレビ番組を対応付け、指定した地点から距離の近い番組を検索できれば、特徴が類似しているテレビ番組を検索できる。
【０１１４】
なお、上記各実施形態では本発明をカーナビゲーション装置１へ適用した例を示したが、この他ＰＮＤや携帯電話あるいは携帯ゲーム機等の組込機器に適用することができる。また、空間データベース１００としては、２次元、または３次元空間の地点データを検索対象とすることができる。
【０１１５】
また、上記各実施形態では、空間インデックス１０１に四分木を適用した例を示したが、Ｒ−ｔｒｅｅ等の他の空間インデックスを適用しても良い。
【０１１６】
また、上記各実施形態では、地点データを２次元空間内の座標とした例を示したが、多次元の座標で構成された地点データに本発明を適用しても良い。 例えば、多次元の地点データが３次元で構成され、３次元空間内の一つの座標で位置を特定可能な地点データである場合、空間インデックス１０１が八分木またはＲ−ｔｒｅｅの何れか一方により地点データを複数の領域に分割して上述のような検索処理を行うことができる。
＜補足＞
７．前記候補領域管理部は、分割領域の情報をヒープ構造で管理し、前記ヒープ構造の節に対応する分割領域の領域距離は、前記節の子に対応する分割領域の領域距離より小さいか等しいというヒープ条件を設ける請求項６に記載のｋ最近傍検索方法。
【０１１７】
１０．前記候補地点管理部は、前記地点データの情報をヒープ構造で管理し、前記ヒープ構造に、前記ヒープ構造の節に対応する地点データの地点距離は、前記節の子に対応する地点データの地点距離より大きいか等しいというヒープ条件を設ける請求項９に記載のｋ最近
１２．前記終了判定部は、前記候補領域管理部のヒープ構造の根に位置する分割領域の領域距離が、前記候補地点管理部のヒープ構造の根に位置する地点データの地点距離より大きい場合に、検索を終了させる請求項１０に記載のｋ最近傍検索方法。
【０１１８】
１４．前記初期設定部は、質問地点、質問件数、中断条件を検索条件として設定し、
前記質問件数に満たない状況でも、前記中断条件を満たす場合に検索処理を中断し、
前記結果取得部が、前記質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項２に記載のｋ最近傍検索方法。
【０１１９】
１５．前記中断条件は、検索結果となる地点データの最大距離を示す質問距離で記述し、
前記領域距離計算部は、前記質問距離より小さいか等しい分割領域に関する情報のみを 前記候補領域管理部に記録するように処理し、
前記地点距離計算部は、質問距離より小さいか等しい地点データに関する情報のみを前 記候補地点管理部に記録するように処理することで、
前記結果取得部が、データベース管理システムから、前記質問距離より小さいか等しく、かつ質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項１４に記載のｋ最近傍検索方法。
【０１２０】
１６．前記中断条件は、検索処理に費やすことができる最大時間を示す最大処理時間で記述し、
検索処理の実行経過時間が前記最大処理時間と等しくなると、前記検索処理を中断して、
前記結果取得部が、データベース管理システムから、質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項１４に記載のｋ最近傍検索方法。
【０１２１】
１７．前記初期設定部は、質問地点、質問件数、属性情報、中断条件を検索条件として設定し、
前記地点距離計算部は、前記検索条件の属性情報に一致する地点データのみを前記候補地点管理部に記録するように処理すると共に、
前記質問件数に満たない状況でも、前記中断条件を満たす場合に検索処理を中断し、
前記結果取得部が、前記データベース管理システムから、前記属性情報に一致する最大ｋ件の地点データを取得可能な請求項２に記載のｋ最近傍検索方法。
【０１２２】
１８．前記中断条件は、検索結果となる地点データの最大距離を示す質問距離で記述し、
前記領域距離計算部は、前記質問距離より小さいか等しい分割領域に関する情報のみを前記候補領域管理部に記録するように処理し、
前記地点距離計算部は、前記質問距離より小さいか等しい地点データに関する情報のみを前記候補地点管理部に記録するように処理することで、
前記結果取得部が、前記データベース管理システムから、前記属性情報に一致し、かつ前記質問距離より小さいか等しく、かつ質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項１７に記載のｋ最近傍検索方法。
【０１２３】
１９．前記中断条件は、検索処理に費やすことができる最大時間を示す最大処理時間で記述し、
検索処理の実行経過時間が前記最大処理時間と等しくなると、前記検索処理を中断して、
前記結果取得部が、前記データベース管理システムから、前記属性情報に一致し、かつ前記質問距離より小さいか等しく、かつ質問地点に距離の近い最大ｋ件の地点データを取得可能な請求項１７に記載のｋ最近傍検索方法。
【０１２４】
２１．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、属性情報を引数に取る問合せ言語、または関数で記述可能な請求項１３に記載のｋ最近傍検索方法。
【０１２５】
２２．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、中断条件を引数に取る問合せ言語、または関数で記述可能な請求項１４に記載のｋ最近傍検索方法。
【０１２６】
２３．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、質問距離を引数に取る問合せ言語、または関数で記述可能な請求項１５に記載のｋ最近傍検索方法。
【０１２７】
２４．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、最大処理時間を引数に取る問合せ言語、または関数で記述可能な請求項１６に記載のｋ最近傍検索方法。
【０１２８】
２５．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、属性情報、中断条件を引数に取る問合せ言語、または関数で記述可能な請求項１７に記載のｋ最近傍検索方法。
【０１２９】
２６．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、属性情報、質問距離を引数に取る問合せ言語、または関数で記述可能な請求項１８に記載のｋ最近傍検索方法。
【０１３０】
２７．前記データベース管理システムで実行する前記ｋ最近傍検索は、検索対象となるテーブルの座標列名、質問地点、質問件数、属性情報、最大処理時間を引数に取る問合せ言語、または関数で記述可能な請求項１９に記載のｋ最近傍検索方法。
【産業上の利用可能性】
【０１３１】
以上のように、本発明は空間データベースを利用する計算機システムに適用することができ、特に、カーナビゲーション装置などの組込装置に適用することができる。
【図面の簡単な説明】
【０１３２】
【図１】第１の実施形態を示し、本発明を適用するカーナビゲーション装置の構成を示すブロック図。
【図２】第１の実施形態を示し、空間インデックスに適用する四分木の階層構造を示す説明図。
【図３】第１の実施形態を示し、空間インデックスに適用する四分木の木構造を示す説明図。
【図４】第１の実施形態を示し、四分木の枝情報を格納する分割領域テーブルの一例を示す説明図。
【図５】第１の実施形態を示し、四分木の葉情報を格納する地点テーブルの一例を示す説明図。
【図６】第１の実施形態を示し、カーナビゲーション装置で実行されるｋ最近傍検索の手順の一例を示すフローチャート。
【図７】第１の実施形態を示し、図６に示した初期設定部のサブルーチンの一例を示すフローチャート。
【図８】第１の実施形態を示し、図６に示した最下位判定部のサブルーチンの一例を示すフローチャート。
【図９】第１の実施形態を示し、図６に示した領域距離計算部のサブルーチンの一例を示すフローチャート。
【図１０】第１の実施形態を示し、分割領域の領域距離の計算方法を示す説明図。
【図１１】第１の実施形態を示し、図６に示した最近領域の子領域の情報を記録する処理のサブルーチンの一例を示すフローチャート。
【図１２】第１の実施形態を示し、一次元配列によるヒープ木の説明図。
【図１３】第１の実施形態を示し、図６に示した最近領域の子領域の情報を記録する処理のサブルーチンの一例を示すフローチャート。
【図１４】第１の実施形態を示し、図６に示した地点距離計算部のサブルーチンの一例を示すフローチャート。
【図１５】第１の実施形態を示し、図６に示した候補地点管理部のサブルーチンの一例を示すフローチャート。
【図１６】第１の実施形態を示し、図６に示した終了判定部のサブルーチンの一例を示すフローチャート。
【図１７】第１の実施形態を示し、図６に示した結果取得部のサブルーチンの一例を示すフローチャート。
【図１８ａ】第１の実施形態を示し、図２に示した空間領域の平面図。
【図１８ｂ】第１の実施形態を示し、ｋ最近傍検索で得られた空間領域における領域ＩＤと領域距離ｄを保持するテーブルの説明図。
【図１８ｃ】第１の実施形態を示し、ｋ最近傍検索で得られた空間領域における地点ＩＤと地点距離ｄ’を保持するテーブルの説明図。
【図１９】第１の実施形態を示し、図１８ａの空間領域でｋ最近傍検索を実行した際の候補領域ヒープ９２の木構造の一例を示す説明図。
【図２０】第１の実施形態を示し、図１８ａの空間領域でｋ最近傍検索を実行した際の候補地点ヒープ９１の木構造の一例を示す説明図。
【図２１】第２の実施形態を示し、四分木の葉情報を格納する地点テーブルの一例を示す説明図。
【図２２】第２の実施形態を示し、初期設定部のサブルーチンの一例を示すフローチャート。
【図２３】第２の実施形態を示し、地点距離計算部のサブルーチンの一例を示すフローチャート。
【図２４】第３の実施形態を示し、初期設定部のサブルーチンの一例を示すフローチャート。
【図２５】第３の実施形態を示し、領域距離計算部のサブルーチンの一例を示すフローチャート。
【図２６】第３の実施形態を示し、地点距離計算部のサブルーチンの一例を示すフローチャート。
【図２７ａ】第４の実施形態を示し、前記第１実施形態に適用可能なＳＱＬを示す説明図。
【図２７ｂ】第４の実施形態を示し、前記第１実施形態と第２実施形態に適用可能なＳＱＬを示す説明図。
【図２７ｃ】第４の実施形態を示し、前記第１実施形態と第３実施形態に適用可能なＳＱＬを示す説明図。
【図２７ｄ】第４の実施形態を示し、前記第１実施形態と第２実施形態及び第３実施形態に適用可能なＳＱＬを示す説明図。
【符号の説明】
【０１３３】
１ カーナビゲーション装置
２ メモリ
３ ＣＰＵ
５ ストレージ装置
７ ＯＳ
８ ＤＢＭＳ
９ アプリケーション
１００ 空間データベース
１０１ 空間インデックス
１１１初期設定部
１１２ 最下位枝判定部
１１３ 領域距離計算部
１１４ 候補領域管理部
１１５ 地点距離計算部
１１６ 候補地点管理部
１１７ 終了判定部
１１８ 結果取得部
５０１ 地点テーブル
【特許請求の範囲】
【請求項１】
多次元の地点データと、前記地点データを含む領域を複数の領域に分割して当該領域内に子領域を設定し、前記地点データと前記領域から枝と葉を含む木構造を作成した空間インデックスと、を含むデータベースと、前記データベースを管理するデータベース管理システムにおいて、検索の始点となる質問地点を受け付けて、前記質問地点から距離の近い上位ｋ件の質問件数の地点データを検索するｋ最近傍検索方法であって、
前記質問地点と質問件数を検索条件に設定するステップと、
前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定するステップと、
前記最近領域が子領域をもつ中間枝と判定されると、前記質問地点と最近領域の子領域との距離を領域距離として計算するステップと、
前記領域距離の計算対象となった領域の情報を保持し、当該領域の最近領域を取得するステップと、
前記最下位枝か中間枝かの判定結果で、前記最近領域が子領域をもたない最下位枝と判定されると、前記質問地点と最近領域に内包される地点データの距離を地点距離として計算するステップと、
前記地点距離の計算対象となった地点データの情報を保持するステップと、
前記検索条件を満たすまで、前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定するステップから前記地点距離の計算対象となった地点データの情報を保持するステップまでの検索処理を繰り返し、前記検索条件を満たした時点で前記検索処理を終了させるステップと、
前記検索処理が終了した後に、前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得するステップと、
を含むことを特徴とするｋ最近傍検索方法。
【請求項２】
前記空間インデックスは、多次元空間を各軸を通る面で階層的に分割した領域を木構造で管理し、前記分割領域に関する情報を枝に格納し、前記枝に対応する分割領域は前記枝の子に位置する枝に対応する分割領域を内包し、最下位の枝に対応する分割領域に内包される地点データに関する情報を前記枝に隣接する葉に格納する空間インデックスである請求項１に記載のｋ最近傍検索方法。
【請求項３】
前記多次元の地点データは、２次元空間内の一つの座標で位置を特定可能な地点データで構成され、
前記空間インデックスが四分木またはＲ−ｔｒｅｅの何れか一方により前記地点データを複数の領域に分割されたことを特徴とする請求項２に記載のｋ最近傍検索方法。
【請求項４】
前記多次元の地点データは、３次元空間内の一つの座標で位置を特定可能な地点データで構成され、
前記空間インデックスが八分木またはＲ−ｔｒｅｅの何れか一方により前記地点データを複数の領域に分割されたことを特徴とする請求項２に記載のｋ最近傍検索方法。
【請求項５】
前記質問地点と最近領域の子領域との距離を計算するステップは、
前記質問地点と子領域との距離を、前記質問地点と前記子領域の境界線上の点の中で、前記質問地点に最も距離が近い点との距離を領域距離として求め、前記子領域が前記質問地点を内包する場合は、前記領域距離を０とすることを特徴とする請求項１に記載のｋ最近傍検索方法。
【請求項６】
前記当該領域の最近領域を取得するステップは、
前記領域に関する情報として、前記データベース管理システムにおける領域または子領域の情報の格納位置を示す領域ポインタと、前記領域の領域距離を保持して、前記最近領域が空間インデックスの最下位枝か中間枝かを判定するステップで判定の対象となる最近領域に関する情報を選択してから、当該領域を削除することを特徴とする請求項５に記載のｋ最近傍検索方法。
【請求項７】
前記質問地点と最近領域に内包される地点データの距離を計算するステップは、
前記質問地点と地点データの最短距離を地点距離として定義し、前記地点距離を計算することを特徴とする請求項５に記載のｋ最近傍検索方法。
【請求項８】
前記地点距離の計算対象となった地点データの情報を保持するステップは、
前記地点データに関する情報として、前記データベース管理システムにおける地点データの格納位置を示す地点ポインタと、前記地点距離を最大でｋ件まで保持し、既にｋ件分の地点データに関する情報を保持している状態で、地点距離を計算し終えた地点データを保持する場合、前記ｋ＋１件の地点データの中で、最大の地点距離をもつ地点データに関する情報を削除し、残りのｋ件分の地点データに関する情報を保持することを特徴とする請求項７に記載のｋ最近傍検索方法。
【請求項９】
前記検索処理を終了させるステップは、前記領域距離の計算対象となった領域の情報を保持するステップで保持されている領域の中での最短の領域距離が、前記地点距離の計算対象となった地点データの情報を保持するステップで保持されている地点データの中での最長の地点距離より大きくなる場合に、検索処理を終了させることを特徴とする請求項７に記載のｋ最近傍検索方法。
【請求項１０】
前記空間インデックスは、前記地点データに関する情報に、前記地点データの属性情報を含めて、葉で管理し、
前記質問地点と質問件数を検索条件に設定するステップは、前記質問地点と、質問件数と、属性情報を検索条件として設定し、
前記質問地点と最近領域に内包される地点データの距離を計算するステップは、
前記検索条件の属性情報に一致する地点データのみを保持し、
前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得するステップは、
前記属性情報に一致し、かつ質問地点に距離の近い上位ｋ件の地点データを取得することを特徴とする請求項２に記載のｋ最近傍検索方法。
【請求項１１】
前記質問地点と質問件数を検索条件に設定するステップは、検索対象となる前記データベースのテーブルの座標列名と、質問地点と、質問件数とを引数に含む問合せ言語または関数で受け付けることを特徴とする請求項２に記載のｋ最近傍検索方法。
【請求項１２】
多次元の地点データと、前記地点データを含む領域を複数の領域に分割して当該領域内に子領域を設定し、前記地点データと前記領域から枝と葉を含む木構造を作成した空間インデックスと、を含むデータベースと、前記データベースを管理するデータベース管理システムにおいて、検索の始点となる質問地点を受け付けて、前記質問地点から距離の近い上位ｋ件の質問件数の地点データを検索するプログラムにおいて、
前記質問地点と質問件数を検索条件に設定する手順と、
前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定する手順と、
前記最近領域が子領域をもつ中間枝と判定されると、前記質問地点と最近領域の子領域との距離を領域距離として計算する手順と、
前記領域距離の計算対象となった領域の情報を保持し、当該領域の最近領域を取得する手順と、
前記最下位枝か中間枝かの判定結果で、前記最近領域が子領域をもたない最下位枝と判定されると、前記質問地点と最近領域に内包される地点データの距離を地点距離として計算する手順と、
前記地点距離の計算対象となった地点データの情報を保持する手順と、
前記検索条件を満たすまで、前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定する手順から前記地点距離の計算対象となった地点データの情報を保持する手順の検索処理を繰り返し、前記検索条件を満たした時点で前記検索処理を終了させる手順と、
前記検索処理が終了した後に、前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得する手順と、
を計算機に機能させることを特徴とするプログラム。
【請求項１３】
演算処理を行うプロセッサと、
情報を記憶する記憶装置と、
多次元の地点データと、前記地点データを含む領域を複数の領域に分割して当該領域内に子領域を設定し、前記地点データと前記領域から枝と葉を含む木構造を作成した空間インデックスと、を含むデータベースと、
前記データベースを管理するデータベース管理システムと、
を備え、検索の始点となる質問地点を受け付けて、前記質問地点から距離の近い上位ｋ件の質問件数の地点データを検索するｋ最近傍検索装置であって、
前記プロセッサが前記質問地点と質問件数を検索条件に設定する初期設定部と、
前記プロセッサが前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定する最下位枝判定部と、
前記プロセッサは前記最近領域が子領域をもつ中間枝であると判定すると、前記質問地点と最近領域の子領域との距離を領域距離として計算する領域距離計算部と、
前記プロセッサが前記領域距離の計算対象となった領域の情報を前記記憶装置に保持し、当該領域の最近領域を取得する候補領域管理部と、
前記最下位枝か中間枝かの判定結果で、前記プロセッサは前記最近領域が子領域をもたない最下位枝であると判定すると、前記質問地点と最近領域に内包される地点データの距離を地点距離として計算する候補地点管理部と、
前記プロセッサが前記地点距離の計算対象となった地点データの情報を前記記憶装置に保持する地点距離計算部と、
前記プロセッサが前記検索条件を満たすまで、最下位枝判定部から候補地点管理部までの検索処理を繰り返し、前記検索条件を満たした時点で前記検索処理を終了させる終了判定部と、
前記検索処理が終了した後に、前記プロセッサが前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得する結果取得部と、
を備えたことを特徴とするｋ最近傍検索装置。
【請求項１４】
前記初期設定部は、前記質問地点と、前記質問件数と、中断条件を検索条件として設定し、
前記終了判定部は、前記質問件数に満たない状況でも、前記中断条件を満たす場合に前記検索処理を中断し、
前記結果取得部が、前記質問地点に地点距離の近い最大ｋ件の地点データを取得することを特徴とする請求項１３に記載のｋ最近傍検索装置。
【請求項１５】
前記中断条件は、前記質問地点から地点データまでの最大距離を示す質問距離または検索処理に費やすことのできる最大時間を示す最大処理時間の何れか一方を含み、
前記中断条件が質問距離のときには、
前記領域距離計算部は、前記質問距離より小さいか等しい分割領域に関する情報のみを前記候補領域管理部に保持し、
前記地点距離計算部は、前記質問距離以下の地点データに関する情報のみを前記候補地点管理部に保持し、
前記結果取得部が、前記データベース管理システムから、前記質問距離以下で、かつ質問地点から距離の近い最大ｋ件の地点データを取得し、
前記中断条件が最大処理時間のときには、
前記終了判定部は、前記検索処理の経過時間が前記最大処理時間と等しくなると、前記検索処理を中断し、
前記結果取得部が、データベース管理システムから、質問地点から距離の近い最大ｋ件の地点データを取得可能にする請求項１４に記載のｋ最近傍検索装置。
【請求項１】
多次元の地点データと、前記地点データを含む領域を複数の領域に分割して当該領域内に子領域を設定し、前記地点データと前記領域から枝と葉を含む木構造を作成した空間インデックスと、を含むデータベースと、前記データベースを管理するデータベース管理システムにおいて、検索の始点となる質問地点を受け付けて、前記質問地点から距離の近い上位ｋ件の質問件数の地点データを検索するｋ最近傍検索方法であって、
前記質問地点と質問件数を検索条件に設定するステップと、
前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定するステップと、
前記最近領域が子領域をもつ中間枝と判定されると、前記質問地点と最近領域の子領域との距離を領域距離として計算するステップと、
前記領域距離の計算対象となった領域の情報を保持し、当該領域の最近領域を取得するステップと、
前記最下位枝か中間枝かの判定結果で、前記最近領域が子領域をもたない最下位枝と判定されると、前記質問地点と最近領域に内包される地点データの距離を地点距離として計算するステップと、
前記地点距離の計算対象となった地点データの情報を保持するステップと、
前記検索条件を満たすまで、前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定するステップから前記地点距離の計算対象となった地点データの情報を保持するステップまでの検索処理を繰り返し、前記検索条件を満たした時点で前記検索処理を終了させるステップと、
前記検索処理が終了した後に、前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得するステップと、
を含むことを特徴とするｋ最近傍検索方法。
【請求項２】
前記空間インデックスは、多次元空間を各軸を通る面で階層的に分割した領域を木構造で管理し、前記分割領域に関する情報を枝に格納し、前記枝に対応する分割領域は前記枝の子に位置する枝に対応する分割領域を内包し、最下位の枝に対応する分割領域に内包される地点データに関する情報を前記枝に隣接する葉に格納する空間インデックスである請求項１に記載のｋ最近傍検索方法。
【請求項３】
前記多次元の地点データは、２次元空間内の一つの座標で位置を特定可能な地点データで構成され、
前記空間インデックスが四分木またはＲ−ｔｒｅｅの何れか一方により前記地点データを複数の領域に分割されたことを特徴とする請求項２に記載のｋ最近傍検索方法。
【請求項４】
前記多次元の地点データは、３次元空間内の一つの座標で位置を特定可能な地点データで構成され、
前記空間インデックスが八分木またはＲ−ｔｒｅｅの何れか一方により前記地点データを複数の領域に分割されたことを特徴とする請求項２に記載のｋ最近傍検索方法。
【請求項５】
前記質問地点と最近領域の子領域との距離を計算するステップは、
前記質問地点と子領域との距離を、前記質問地点と前記子領域の境界線上の点の中で、前記質問地点に最も距離が近い点との距離を領域距離として求め、前記子領域が前記質問地点を内包する場合は、前記領域距離を０とすることを特徴とする請求項１に記載のｋ最近傍検索方法。
【請求項６】
前記当該領域の最近領域を取得するステップは、
前記領域に関する情報として、前記データベース管理システムにおける領域または子領域の情報の格納位置を示す領域ポインタと、前記領域の領域距離を保持して、前記最近領域が空間インデックスの最下位枝か中間枝かを判定するステップで判定の対象となる最近領域に関する情報を選択してから、当該領域を削除することを特徴とする請求項５に記載のｋ最近傍検索方法。
【請求項７】
前記質問地点と最近領域に内包される地点データの距離を計算するステップは、
前記質問地点と地点データの最短距離を地点距離として定義し、前記地点距離を計算することを特徴とする請求項５に記載のｋ最近傍検索方法。
【請求項８】
前記地点距離の計算対象となった地点データの情報を保持するステップは、
前記地点データに関する情報として、前記データベース管理システムにおける地点データの格納位置を示す地点ポインタと、前記地点距離を最大でｋ件まで保持し、既にｋ件分の地点データに関する情報を保持している状態で、地点距離を計算し終えた地点データを保持する場合、前記ｋ＋１件の地点データの中で、最大の地点距離をもつ地点データに関する情報を削除し、残りのｋ件分の地点データに関する情報を保持することを特徴とする請求項７に記載のｋ最近傍検索方法。
【請求項９】
前記検索処理を終了させるステップは、前記領域距離の計算対象となった領域の情報を保持するステップで保持されている領域の中での最短の領域距離が、前記地点距離の計算対象となった地点データの情報を保持するステップで保持されている地点データの中での最長の地点距離より大きくなる場合に、検索処理を終了させることを特徴とする請求項７に記載のｋ最近傍検索方法。
【請求項１０】
前記空間インデックスは、前記地点データに関する情報に、前記地点データの属性情報を含めて、葉で管理し、
前記質問地点と質問件数を検索条件に設定するステップは、前記質問地点と、質問件数と、属性情報を検索条件として設定し、
前記質問地点と最近領域に内包される地点データの距離を計算するステップは、
前記検索条件の属性情報に一致する地点データのみを保持し、
前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得するステップは、
前記属性情報に一致し、かつ質問地点に距離の近い上位ｋ件の地点データを取得することを特徴とする請求項２に記載のｋ最近傍検索方法。
【請求項１１】
前記質問地点と質問件数を検索条件に設定するステップは、検索対象となる前記データベースのテーブルの座標列名と、質問地点と、質問件数とを引数に含む問合せ言語または関数で受け付けることを特徴とする請求項２に記載のｋ最近傍検索方法。
【請求項１２】
多次元の地点データと、前記地点データを含む領域を複数の領域に分割して当該領域内に子領域を設定し、前記地点データと前記領域から枝と葉を含む木構造を作成した空間インデックスと、を含むデータベースと、前記データベースを管理するデータベース管理システムにおいて、検索の始点となる質問地点を受け付けて、前記質問地点から距離の近い上位ｋ件の質問件数の地点データを検索するプログラムにおいて、
前記質問地点と質問件数を検索条件に設定する手順と、
前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定する手順と、
前記最近領域が子領域をもつ中間枝と判定されると、前記質問地点と最近領域の子領域との距離を領域距離として計算する手順と、
前記領域距離の計算対象となった領域の情報を保持し、当該領域の最近領域を取得する手順と、
前記最下位枝か中間枝かの判定結果で、前記最近領域が子領域をもたない最下位枝と判定されると、前記質問地点と最近領域に内包される地点データの距離を地点距離として計算する手順と、
前記地点距離の計算対象となった地点データの情報を保持する手順と、
前記検索条件を満たすまで、前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定する手順から前記地点距離の計算対象となった地点データの情報を保持する手順の検索処理を繰り返し、前記検索条件を満たした時点で前記検索処理を終了させる手順と、
前記検索処理が終了した後に、前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得する手順と、
を計算機に機能させることを特徴とするプログラム。
【請求項１３】
演算処理を行うプロセッサと、
情報を記憶する記憶装置と、
多次元の地点データと、前記地点データを含む領域を複数の領域に分割して当該領域内に子領域を設定し、前記地点データと前記領域から枝と葉を含む木構造を作成した空間インデックスと、を含むデータベースと、
前記データベースを管理するデータベース管理システムと、
を備え、検索の始点となる質問地点を受け付けて、前記質問地点から距離の近い上位ｋ件の質問件数の地点データを検索するｋ最近傍検索装置であって、
前記プロセッサが前記質問地点と質問件数を検索条件に設定する初期設定部と、
前記プロセッサが前記質問地点に最も近い最近領域が空間インデックスの最下位枝か中間枝かを判定する最下位枝判定部と、
前記プロセッサは前記最近領域が子領域をもつ中間枝であると判定すると、前記質問地点と最近領域の子領域との距離を領域距離として計算する領域距離計算部と、
前記プロセッサが前記領域距離の計算対象となった領域の情報を前記記憶装置に保持し、当該領域の最近領域を取得する候補領域管理部と、
前記最下位枝か中間枝かの判定結果で、前記プロセッサは前記最近領域が子領域をもたない最下位枝であると判定すると、前記質問地点と最近領域に内包される地点データの距離を地点距離として計算する候補地点管理部と、
前記プロセッサが前記地点距離の計算対象となった地点データの情報を前記記憶装置に保持する地点距離計算部と、
前記プロセッサが前記検索条件を満たすまで、最下位枝判定部から候補地点管理部までの検索処理を繰り返し、前記検索条件を満たした時点で前記検索処理を終了させる終了判定部と、
前記検索処理が終了した後に、前記プロセッサが前記保持された地点データのレコードを検索結果として前記データベース管理システムから取得する結果取得部と、
を備えたことを特徴とするｋ最近傍検索装置。
【請求項１４】
前記初期設定部は、前記質問地点と、前記質問件数と、中断条件を検索条件として設定し、
前記終了判定部は、前記質問件数に満たない状況でも、前記中断条件を満たす場合に前記検索処理を中断し、
前記結果取得部が、前記質問地点に地点距離の近い最大ｋ件の地点データを取得することを特徴とする請求項１３に記載のｋ最近傍検索装置。
【請求項１５】
前記中断条件は、前記質問地点から地点データまでの最大距離を示す質問距離または検索処理に費やすことのできる最大時間を示す最大処理時間の何れか一方を含み、
前記中断条件が質問距離のときには、
前記領域距離計算部は、前記質問距離より小さいか等しい分割領域に関する情報のみを前記候補領域管理部に保持し、
前記地点距離計算部は、前記質問距離以下の地点データに関する情報のみを前記候補地点管理部に保持し、
前記結果取得部が、前記データベース管理システムから、前記質問距離以下で、かつ質問地点から距離の近い最大ｋ件の地点データを取得し、
前記中断条件が最大処理時間のときには、
前記終了判定部は、前記検索処理の経過時間が前記最大処理時間と等しくなると、前記検索処理を中断し、
前記結果取得部が、データベース管理システムから、質問地点から距離の近い最大ｋ件の地点データを取得可能にする請求項１４に記載のｋ最近傍検索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８ａ】
【図１８ｂ】
【図１８ｃ】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７ａ】
【図２７ｂ】
【図２７ｃ】
【図２７ｄ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８ａ】
【図１８ｂ】
【図１８ｃ】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７ａ】
【図２７ｂ】
【図２７ｃ】
【図２７ｄ】
【公開番号】特開２００９−１９９１５１（Ｐ２００９−１９９１５１Ａ）
【公開日】平成２１年９月３日（２００９．９．３）
【国際特許分類】
【出願番号】特願２００８−３７３６２（Ｐ２００８−３７３６２）
【出願日】平成２０年２月１９日（２００８．２．１９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
【公開日】平成２１年９月３日（２００９．９．３）
【国際特許分類】
【出願日】平成２０年２月１９日（２００８．２．１９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
[ Back to top ]