データ処理方法および装置並びにその処理プログラム
【課題】空間検索と補助条件検索を同時に指定された場合に、高速に空間検索処理を行う。
【解決手段】地図データベースの空間検索用インデクス内に、空間情報のほかに補助条件である属性条件（付加情報）を１つまたは複数格納したことで、ＤＢＭＳの複数検索条件結果のマージを行うことなく、空間検索用インデクスのアクセスだけで空間検索と補助条件検索の複合条件の検索を高速に行うことができる。また、ｎ次元空間検索用インデクスに、補助属性データとして（ｎ＋１）次元の情報を記憶することにより、ｎ次元の空間検索用インデクスで（ｎ＋１）次元の検索を可能とした。
【解決手段】地図データベースの空間検索用インデクス内に、空間情報のほかに補助条件である属性条件（付加情報）を１つまたは複数格納したことで、ＤＢＭＳの複数検索条件結果のマージを行うことなく、空間検索用インデクスのアクセスだけで空間検索と補助条件検索の複合条件の検索を高速に行うことができる。また、ｎ次元空間検索用インデクスに、補助属性データとして（ｎ＋１）次元の情報を記憶することにより、ｎ次元の空間検索用インデクスで（ｎ＋１）次元の検索を可能とした。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、蓄積したデータの処理技術に関する。
【背景技術】
【０００２】
近年、マルチメディアデータを取り扱うことができるＲＤＢＭＳ（Relational DataBase Management System：リレーショナル・データベース管理システム）が増加してきている。このマルチメディアデータの一種として、地図データを格納し、更新管理や、シンクライアントなどへの地図配信に利用されてきている。この地図データを高速に検索するための空間検索用インデクス技術が研究されてきた。
また、組込分野でも空間検索機能を有するＤＢＭＳ（DataBase Management System：データベース管理システム）が開発されてきており、カーナビゲーション分野などへの応用が期待されている。
【０００３】
空間検索用インデクスによく利用される空間分割手法として、Ｒ−ｔｒｅｅ（図１１）や四分木（図１２）が挙げられる。これらは、２次元空間を適切に分割していくことにより木構造を構成し、検索時のデータ処理件数を大幅に削減することを目的としている。
【０００４】
図１１のＲ−ｔｒｅｅは、部分領域を包囲長方形によって管理し、さらにその内側に階層的に包囲長方形を再帰的に管理することにより空間情報を管理する方法である。対象空間の１段目（１１０１）として部分領域の包囲長方形を決定し、その範囲内の管理対象図形の分布により、必要に応じて２段目（１１０２）の包囲長方形を決定する。さらに１段目（１１０１）と同様に、２段目（１１０２）の範囲内の管理対象図形の分布により、必要に応じて３段目（１１０３）の包囲長方形を決定する。この分割を再帰的に繰り返すことにより、空間情報を木構造で管理することができる。
【０００５】
図１２の四分木は、空間を既定の割合で規則的に４分割し、それを再帰的に繰り返すことにより空間情報を管理する方法である。対象空間の１段目（１２０１）を既定の割合で４分割したものを２段目（１２０２）とする。さらに１段目（１２０１）と同様に、２段目（１２０２）を既定の割合で４分割したものを３段目（１２０３）とする。この分割を再帰的に繰り返すことにより、空間情報を木構造で管理することができる。
【０００６】
図１１、図１２に示すような空間を木構造に分割するインデクスを用いて、空間検索を行う処理のフローチャートの一例を図１３に示す。空間検索条件を取得し（ステップ１３０１）、空間検索用インデクスの木構造を再帰的に探索して、空間検索条件に接触または内包される枝から検索対象とすべき葉（リーフ）を抽出し（ステップ１３０２）、その葉から対象図形を取得し（ステップ１３０３）、取得した図形を個別に空間検索条件と比較（対象の図形が空間検索範囲条件に適合しているか否かを判別）し（ステップ１３０４）、条件に適合していたら、対象の図形を検索結果として出力する（ステップ１３０５）。
続いて、対象の葉の中にまだ図形があるかどうかを判定し（ステップ１３０６）、まだ図形があるならステップ１３０３から繰り返す。葉内の図形の処理が終わったら、検索対象となる葉がまだあるかどうか判定し（ステップ１３０７）、まだ対象となる葉があるならステップ１３０２から繰り返す。このような処理により、空間上に分布する図形群から目的の空間範囲の図形を高速に検索することができる。
【０００７】
空間検索用インデクスを利用することにより、図９に示すような空間範囲での検索を高速に行うことができる。図９では、東京駅の座標（９０１）を中心に、指定の半径の円（９０２）内にあるランドマークをすべて検索した結果を示した。空間範囲外のランドマーク（９０３）は検索されず、空間範囲内のランドマーク（９０４）のみが検索される結果となる。この例で検索されるのは、Ｂレストラン神田店、Ｙ銀行大手町支店、Ｘ銀行有楽町支店となる。
このような技術は、特許文献１に開示されている。
【特許文献１】特許第３６４９４３０号公報（特開２００１−１４３３８号公報）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記の空間検索機能を有するＲＤＢＭＳを用いて、「空間的に検索する条件」と「その他の絞込み条件」とを複合した結果を検索することは良くある用途である。たとえばカーナビゲーション分野での「経路沿いのガソリンスタンド」、不動産検索システムでの「駅から半径１ｋｍ以内で３ＬＤＫ以上のマンション」、エリアマーケティング分野での「既存店舗から半径２ｋｍ以内の競合店」などの付加条件付きの空間検索条件が挙げられる。
【０００９】
図１０に、空間検索条件と属性条件の複合条件の検索例を示す。本願の処理結果の例を示す図１０では、東京駅の座標（１００１）を中心に、所定半径の円（１００２）内にあるランドマークのうち、ランドマークのカテゴリが銀行を表しているものを検索した結果を示している。一般的な空間検索の処理結果を示す図９と同様に空間範囲外のランドマーク（１００３）は検索されず、さらに図１０では、空間範囲内だが属性が条件に適合しないランドマーク（１００４）も検索されない。つまり、空間範囲内且つ属性（属性情報ともいう）が条件に適合するランドマーク（１００５）のみが検索される結果となっている。この例では、Ｂレストラン神田店は検索円の範囲内ではあるが属性条件が銀行ではないので検索されず、Ｙ銀行大手町支店とＸ銀行有楽町支店が検索される結果となる。
【００１０】
これらを検索する際に、従来型のＲＤＢＭＳでは空間データカラムのほかに属性カラムを持ち、ＳＱＬの条件句で複数の検索条件をＡＮＤ条件で結ぶことにより、ＲＤＢＭＳ内で検索結果をマージし出力するという方式が考えられる。この場合、空間検索だけではあまり絞り込めないが、その後の付加条件で大きく絞り込める条件で、各々の条件で単独の検索を行ってはあまり性能が期待できない。しかしながら、そのような条件は往々にしてよく利用される条件となっているため、検索処理に時間が掛かり、高速な検索処理技術が望まれていた。
【００１１】
本発明の目的は、空間検索用インデクス内に複合条件のヒントとなる付加情報を含めることにより、空間検索用インデクスの検索時に付加情報についても検索を可能とし、高速な空間検索処理を実現することにある。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明の空間検索用インデクス（空間インデクスともいう）に、空間情報のほかに属性条件（付加情報）を１つまたは複数格納できるように拡張する。
【００１３】
通常の空間検索用インデクスでは、２次元データを扱う場合、ｘ座標とｙ座標を用いて空間分割を行い、その情報をインデクスに格納しておくことで、空間検索時にインデクスの参照により空間条件を絞り込むことができるよう設計されている。空間検索条件と付加属性条件との複合条件での検索では、空間検索で絞り込んだ後、他のカラムに格納された属性情報で判定するか、または他のカラムに割り当てられたインデクス検索結果とマージし、両方に含まれている結果を出力する。
【００１４】
ここで、空間検索用インデクス内に属性条件のヒント情報を格納しておけば、空間検索で絞り込むとともに、属性条件についても絞り込むことができる。空間検索用インデクス内に格納する属性条件は、付加属性をキーワードや数値等の形式で格納しても良いが、インデクスの肥大化を避けるため、付加属性を項目別、ジャンル別などで分類し、その分類情報をヒント情報としてビット列として格納し、ビット列から特定のビット条件を満たすものだけ検索する方式を採ることもできる。
【００１５】
また、２次元の空間検索用インデクス内に属性条件としてｚ軸の情報を取り込み、補助属性条件にも範囲検索を実装することにより、２次元の空間検索用インデクスで３次元の検索が可能となる。
【発明の効果】
【００１６】
本発明によれば、空間検索用インデクス内に複合条件のヒントとなる付加情報を含めることにより、空間検索用インデクスの検索時に付加情報についても検索が可能なため、高速な空間検索処理が実現できる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明を適用した空間検索システムの一実施の形態について説明する。
【００１８】
図１は、本発明の実施の形態の一例を示すシステム構成図のうち、ホストシステム（データ処理装置）と通信端末で構成される例を示す。
本空間検索システムは、地図を格納する記録装置（記憶装置）１０１と、検索処理を行うホストシステム１０２と、ユーザからの指示を入力する入力装置１０３と、結果や状態を表示する表示装置１０４から構成される。ホストシステム１０２は、計算機や情報処理装置でも実現することが可能である。
【００１９】
記録装置１０１は、地図データを格納する地図データベース１０５と、空間検索の高速化のために構成された空間検索用インデクス１０６から構成される。
【００２０】
ホストシステム１０２は、演算処理を行うＣＰＵ１０７と、モジュール（プログラム）やデータを格納するメモリ１０８と、検索処理要求に従い記録装置１０１にアクセスするデータベース処理モジュール１０９と、検索処理結果を配信する通信装置１１０から構成される。
【００２１】
データベース処理モジュール（データ処理プログラム）１０９は、空間座標データ（位置情報ともいう）およびその付加属性データ（属性情報ともいう）についての検索要求（検索条件を含んでもよい）と更新要求もしくは追加要求、削除要求を処理する空間検索用インデクス処理部１１１と、記録装置１０１にアクセスするデータアクセスモジュール１１２から構成される。一般的なデータベース処理を行うデータベース処理モジュールは、その他の検索要求や更新要求を処理するモジュールも含む場合もあるが、図１からは省略している。
【００２２】
空間検索用インデクス処理部１１１は、空間座標による検索処理を実行する空間検索処理モジュール１１３と、付加属性の検索処理を実行する付加属性検索処理モジュール１１４と、更新要求時に使用するインデクス更新処理モジュール１１５から構成される。
空間検索用インデクス処理部１１１は、空間検索条件と属性条件の複合条件において、空間検索用インデクス１０６を用いて地図データベース１０５に格納されているデータの中から必要な（検索要求を満たす）レコードを高速に選択することができる。
【００２３】
インデクス更新処理モジュール１１５は、空間座標データおよびその付加属性データの更新要求時に、地図データベース１０５と同期して空間検索用インデクス１０６を更新する。空間検索用インデクスは、空間インデクスともいう。
【００２４】
このホストシステム１０２から地図データおよび地図関連データを受信する移動端末装置１１６は、無線回線によって基地局１１７と通信可能となっている。そして、基地局１１７は有線の公衆回線網によるネットワーク１１８と接続され、このネットワーク１１８にホストシステム１０２が接続されている。従って、移動端末装置１１６とホストシステム１０２とは、基地局１１７に到る無線回線およびネットワーク１１８を通じてホストシステム１０２に接続されている（通信可能となっている）ことになる。
【００２５】
図２は、本実施の形態の一例を示すシステム構成図のうち、組み込み機器として構成される例を示す。本空間検索システムは、地図を格納する記録装置２０１と、検索処理を行う組み込み機器２０２と、ユーザからの指示を入力する入力装置２０３と、結果や状態を表示する表示装置２０４から構成される。
【００２６】
記録装置２０１は、地図データを格納する地図データベース２０５と、空間検索の高速化のために構成された空間検索用インデクス２０６から構成される。
【００２７】
組み込み機器２０２は、モジュールを実行するための処理を行うＣＰＵ２０７と、モジュール（プログラム）やデータを格納するメモリ２０８と、入力した（もしくは、受け付けた）検索処理要求に従い記録装置２０１にアクセスするデータベース処理モジュール２０９と、ユーザからの入力やユーザへの地図表示や状態表示を管理するユーザインタフェース処理モジュール２１０から構成される。これらの処理部やモジュールは、プログラムやオブジェクト、プロセス、スレッドなどにより実現することができる。また、これら処理部やモジュールはハードウェアで実現することも可能である。組込み機器は、地図検索装置やナビゲーションシステム、カーナビゲーションシステムでも良い。
【００２８】
データベース処理モジュール２０９は、図１と同様に、空間座標データおよびその付加属性データについての検索要求と更新要求を処理する空間検索用インデクス処理部２１１と、記録装置２０１にアクセスするデータアクセスモジュール２１２から構成される。一般的なデータベース処理モジュールは、その他の検索要求や更新要求を処理するモジュールも含む場合もあるが、図２からは省略している。
【００２９】
空間検索用インデクス処理部２１１は、空間座標による検索処理を実行する空間検索処理モジュール２１３と、付加属性の検索処理を実行する付加属性検索処理モジュール２１４と、更新要求時に使用するインデクス更新処理モジュール２１５から構成される。
【００３０】
空間検索用インデクス処理部２１１は、空間検索条件と属性条件の複合条件において、空間検索用インデクス２０６を用いて地図データベース２０５に格納されているデータの中から必要なレコードを高速に選択することができる。
【００３１】
インデクス更新処理モジュール２１５は、空間座標データおよびその付加属性データの更新要求時に、地図データベース２０５と同期して空間検索用インデクス２０６を更新する。ただし、組込み機器の構成により更新機能を持たない場合は、インデクス更新処理モジュール２１５は省略することができる。
【００３２】
図１の空間検索用インデクス１０６および図２の空間検索用インデクス２０６には、各々の地図データベース１０５、２０５に格納されている空間座標データのほかに、付加属性を格納している。このデータ構造を図３および図４に示す。空間の分割状態を木構造（３０１、４０１）で表し、その中の個別の要素を枝（３０２、４０２）と呼ぶ。各々の枝には、その枝が管理するデータのリストを格納する領域として葉（３０３、４０３）を１つまたは複数持つ。木構造によっては枝が葉を持たない実装もある。
【００３３】
この葉のデータリストの中に、各図形の個別の図形領域を格納し、検索時に参照する。本実施の形態では、この葉のデータリストの中に、各図形の個別の図形領域（３０４、４０４）に追加して、補助属性（付加属性）（３０５、４０５）を格納する。例としてｘ座標、ｙ座標に補助属性（付加属性）を１つ付加したものを図示した。この座標領域部は例で図示した１点座標以外にも、図形の外接矩形などの概形を格納し検索に使用する方法もよく使用される。また本実施の形態で付加する属性は、例で図示した場合は１つの属性だが、複数の属性を付加する方法もある。
【００３４】
本実施の形態では、この補助属性（付加属性）に対し、空間検索条件のほかに、補助属性検索条件を含めて検索を行うことができる。この検索処理の概要のフローチャートを図５に示す。この図５のフローチャートは、図１３の点線枠１３１０の処理フローを置き換えるものである。
【００３５】
まず、対称の図形が空間検索範囲条件に適合しているか否かを判別することで、指定された空間検索条件で空間検索用インデクスを参照して候補を絞り込む（ステップ５０１）。空間検索範囲条件に適合していたら、空間検索用インデクス内から、空間検索で絞り込まれた候補レコードに付加されている補助属性の値を取得して補助属性検索条件と照らし合わせることで対称の図形の属性が補助属性検索条件に適合しているか否かを判別し（ステップ５０２）、補助属性検索条件も満たしていたなら対象の図形を検索結果として出力する（ステップ５０３）。
【００３６】
なお、ステップ５０１の処理は空間検索処理モジュール１１３（２１３）が機能し、ステップ５０２の処理は付加属性検索処理モジュール１１４（２１４）が機能する。
【００３７】
ステップ５０２で判定する補助属性検索条件には、値の一致、範囲比較、ビット判定異の条件を指定できる。各々の処理のフローチャートを図６〜図８に示す。図６〜図８のフローチャートも図５と同様に、図１３の点線枠１３１０の処理フローを置き換えるものである。
【００３８】
図６の値の一致判定では、補助属性検索条件として、１つまたは複数の値を指定できる。
まず、対象の図形は空間検索範囲条件に適合しているか否かを判別することで指定された空間検索条件で候補を絞り込む（ステップ６０１）。空間検索範囲条件に適合していたら、その候補に付加されている補助条件の値を取得し、その値が補助属性検索条件として指定された値と一致しているかを判定することで対象の図形の属性が補助属性検索条件と一致しているか否かを判別する（ステップ６０２）。一致していたら対象の図形を検索結果として出力する（ステップ６０３）。ここで、補助属性検索条件として複数の値が指定された場合、ステップ６０２では、複数の値と比較しどれか１つでも一致したら適合と判定する。この判定は、たとえば補助属性にカテゴリ値を格納しておき、「特定のカテゴリと一致する」という補助検索条件で検索する際に使用する。この場合のデータ構造の例としては図３が挙げられる。たとえば図３の付加属性（３０５）にランドマークのカテゴリ情報を格納する。例としてガソリンスタンドやコンビニなどの種別をカテゴリＩＤとして数値化して格納した場合、「カテゴリＩＤが５０と一致する」という付加属性条件を付加すると、空間検索条件の適合した中から、カテゴリＩＤが一致するレコードだけを抽出できる。一致する条件には複数指定できるので、例えば「カテゴリＩＤが５０または６０と一致する」という検索条件を指定することもできる。
【００３９】
なお、ステップ６０１の処理は空間検索処理モジュール１１３（２１３）が機能し、ステップ６０２の処理は付加属性検索処理モジュール１１４（２１４）が機能する。
【００４０】
図７のビット判定条件では、補助属性検索条件として、ＡＮＤやＯＲなどのビット演算子と、ビット演算値を指定できる。
まず、対称の図形が空間検索範囲条件に適合しているか否かを判別することで、指定された空間検索条件で候補を絞り込む（ステップ７０１）。空間検索範囲条件に適合していたら、補助属性検索条件として指定された値と、絞り込んだ候補に付加されている補助条件（対象の図形の属性）の値とのＡＮＤ演算を行う（ステップ７０２）。
そして、補助属性検索条件として指定された演算子によって判定を分け（ステップ７０３）、ＡＮＤ演算子が指定されていた場合は、必要な全ビットが一致（つまり、ステップ７０２の演算結果が補助属性検索条件の値と一致）しているかを判定し（ステップ７０４）、あるいはＯＲ演算子が指定されていた場合は、どれか１ビットでも一致している（つまり、ステップ７０２の演算結果が０以外）かを判定し（ステップ７０５）、一致していたら対象の図形を検索結果として出力する（ステップ７０６）。
【００４１】
この判定は、たとえば補助属性にカテゴリ値を格納するが、カテゴリを即値で表すと条件が足りなくなる場合に、カテゴリやジャンルなどで分類しておき、その分類結果を抽象化してビット列として表現し、必要なビットを割り当て、１回のビット演算だけで「特定のカテゴリ群と一致する」などの補助検索条件で検索する際に使用する。
【００４２】
また、ビット列の元になる情報は１つではなく、複数の属性データにビットを割り当て、複数の属性検索条件について一度に検索処理を行うことができる。この場合のデータ構造の例としては図４が挙げられる。たとえば図４の付加属性（４０５）にランドマークのカテゴリ情報や、その他の情報を抽象化してビット列として格納する。
【００４３】
例えば、下位７ビット目（01000000）に「銀行なら１」となるビットを配置し、下位３ビット目（00000100）に「レストランなら１」となるビットを配置した場合、「付加属性情報と、ビット列01000000とのＡＮＤ条件が成立する」という付加属性条件を付加すると、空間検索条件の適合した中から、付加属性のビット条件が一致するレコードだけを抽出できる。このビット条件には、たとえば「夜間に営業しているビット」、「駐車場が付属している施設ビット」、「トイレが利用可能ビット」など、各々全く異なる付加情報をビット列として配置することができる。そして付加属性条件として、指定した任意のビットを同時に満たすＡＮＤ条件、どれか１つを満たすＯＲ条件で検索することができる。
【００４４】
なお、ステップ７０１の処理は空間検索処理モジュール１１３（２１３）が機能し、ステップ７０２の処理は付加属性検索処理モジュール１１４（２１４）が機能する。
【００４５】
図８の範囲比較判定では、補助属性検索条件として、値の範囲を指定できる。
まず、対称の図形が空間検索範囲条件に適合しているか否かを判別することで、指定された空間検索条件で候補を絞り込む（ステップ８０１）。空間検索条件に適合していたら、その候補に付加されている補助条件の値を取得し、その値が補助属性検索条件として指定された値の範囲に含まれているかを判定することで、対称の図形の属性が補助属性検索条件の範囲に適合しているか否かを判別する（ステップ８０２）。値の範囲に含まれていたら、対象の図形を検索結果として出力する（ステップ８０３）。この判定は、たとえば補助属性にｚ座標の値を格納しておき、空間検索条件にｚ軸の検索範囲を付加して３次元で検索する際に使用する。この場合のデータ構造の例としては図３が挙げられる。たとえば図３の付加属性（３０５）に高さ情報としてｚ軸の値を格納した場合、「ｚ軸の値が４０〜５０の範囲にある」という付加属性条件を付加すると、空間検索条件の適合した中から、ｚ軸の値が指定範囲に適合するレコードだけを抽出できる。
【００４６】
このように、地図データベースの空間検索用インデクス内に補助条件のヒント情報を格納し、検索処理で適切に利用することにより、ＤＢＭＳの複数検索条件結果のマージを行うことなく、空間検索用インデクスのアクセスだけで空間検索と補助条件検索の複合条件の検索を高速に行うことができる。
【００４７】
なお、ステップ８０１の処理は空間検索処理モジュール１１３（２１３）が機能し、ステップ８０２の処理は付加属性検索処理モジュール１１４（２１４）が機能する。
【００４８】
以上によれば、空間検索条件と補助属性条件との複合検索条件において、従来のＲＤＢＭＳのように、代表の検索条件の後に残りの条件で個別に絞り込んだり、複数の検索条件の結果をマージしたりすることなく、空間検索と同時に属性検索を行うことができる。また、空間検索用インデクスに補助属性データをそのまま取り込むことも可能だが、項目別やジャンル別で分類し、分類情報をビット列として格納し検索することにより、空間検索用インデクスの肥大化を避けることができると共に、ビット演算を用いることで１度の演算で複数の付加条件の判定を行うことができる。
【００４９】
また、２次元空間検索用インデクスに補助属性データとしてｚ軸の情報を取り込み、補助属性条件にも範囲検索を実装することにより、２次元の空間検索用インデクスで３次元の検索を可能とする。つまり、（ｎ＋１）次元目の情報を補助属性データとしてｎ次元の空間検索用インデクスを作成することにより、ｎ次元の空間検索用インデクスで（ｎ＋１）次元の検索を実現することが可能となる。
【図面の簡単な説明】
【００５０】
【図１】本発明の一実施の形態例を示すシステム構成図（ホストシステム）
【図２】本発明の一実施の形態例を示すシステム構成図（組み込み機器）
【図３】空間検索用インデクスのデータ構造の一例（属性値）
【図４】空間検索用インデクスのデータ構造の一例（属性の抽象化ビット列）
【図５】空間検索処理の概要のフローチャート
【図６】補助属性検索条件の処理部分のフローチャート（値の一致条件）
【図７】補助属性検索条件の処理部分のフローチャート（ビット判定条件）
【図８】補助属性検索条件の処理部分のフローチャート（範囲比較条件）
【図９】一般的な空間検索の処理結果の例（空間検索のみ）
【図１０】本発明の処理結果の例（空間検索＋属性検索）
【図１１】空間検索用インデクスの空間分割例（Ｒ−ｔｒｅｅ）
【図１２】空間検索用インデクスの空間分割例（四分木）
【図１３】空間検索用インデクスを用いた一般的な空間検索処理のフローチャート
【符号の説明】
【００５１】
１０１ 記録装置（記憶装置）
１０２ ホストシステム（データ処理装置）
１０３ 入力装置
１０４ 表示装置
１０５ 地図データベース
１０６ 空間検索用インデクス
１０７ ＣＰＵ
１０８ メモリ
１０９ データベース処理モジュール
１１０ 通信装置
１１１ 空間検索用インデクス処理部
１１２ データアクセスモジュール
１１３ 空間検索処理モジュール
１１４ 付加属性検索処理モジュール
１１５ インデクス更新処理モジュール
１１６ 移動端末装置
１１７ 基地局
１１８ ネットワーク
【技術分野】
【０００１】
本発明は、蓄積したデータの処理技術に関する。
【背景技術】
【０００２】
近年、マルチメディアデータを取り扱うことができるＲＤＢＭＳ（Relational DataBase Management System：リレーショナル・データベース管理システム）が増加してきている。このマルチメディアデータの一種として、地図データを格納し、更新管理や、シンクライアントなどへの地図配信に利用されてきている。この地図データを高速に検索するための空間検索用インデクス技術が研究されてきた。
また、組込分野でも空間検索機能を有するＤＢＭＳ（DataBase Management System：データベース管理システム）が開発されてきており、カーナビゲーション分野などへの応用が期待されている。
【０００３】
空間検索用インデクスによく利用される空間分割手法として、Ｒ−ｔｒｅｅ（図１１）や四分木（図１２）が挙げられる。これらは、２次元空間を適切に分割していくことにより木構造を構成し、検索時のデータ処理件数を大幅に削減することを目的としている。
【０００４】
図１１のＲ−ｔｒｅｅは、部分領域を包囲長方形によって管理し、さらにその内側に階層的に包囲長方形を再帰的に管理することにより空間情報を管理する方法である。対象空間の１段目（１１０１）として部分領域の包囲長方形を決定し、その範囲内の管理対象図形の分布により、必要に応じて２段目（１１０２）の包囲長方形を決定する。さらに１段目（１１０１）と同様に、２段目（１１０２）の範囲内の管理対象図形の分布により、必要に応じて３段目（１１０３）の包囲長方形を決定する。この分割を再帰的に繰り返すことにより、空間情報を木構造で管理することができる。
【０００５】
図１２の四分木は、空間を既定の割合で規則的に４分割し、それを再帰的に繰り返すことにより空間情報を管理する方法である。対象空間の１段目（１２０１）を既定の割合で４分割したものを２段目（１２０２）とする。さらに１段目（１２０１）と同様に、２段目（１２０２）を既定の割合で４分割したものを３段目（１２０３）とする。この分割を再帰的に繰り返すことにより、空間情報を木構造で管理することができる。
【０００６】
図１１、図１２に示すような空間を木構造に分割するインデクスを用いて、空間検索を行う処理のフローチャートの一例を図１３に示す。空間検索条件を取得し（ステップ１３０１）、空間検索用インデクスの木構造を再帰的に探索して、空間検索条件に接触または内包される枝から検索対象とすべき葉（リーフ）を抽出し（ステップ１３０２）、その葉から対象図形を取得し（ステップ１３０３）、取得した図形を個別に空間検索条件と比較（対象の図形が空間検索範囲条件に適合しているか否かを判別）し（ステップ１３０４）、条件に適合していたら、対象の図形を検索結果として出力する（ステップ１３０５）。
続いて、対象の葉の中にまだ図形があるかどうかを判定し（ステップ１３０６）、まだ図形があるならステップ１３０３から繰り返す。葉内の図形の処理が終わったら、検索対象となる葉がまだあるかどうか判定し（ステップ１３０７）、まだ対象となる葉があるならステップ１３０２から繰り返す。このような処理により、空間上に分布する図形群から目的の空間範囲の図形を高速に検索することができる。
【０００７】
空間検索用インデクスを利用することにより、図９に示すような空間範囲での検索を高速に行うことができる。図９では、東京駅の座標（９０１）を中心に、指定の半径の円（９０２）内にあるランドマークをすべて検索した結果を示した。空間範囲外のランドマーク（９０３）は検索されず、空間範囲内のランドマーク（９０４）のみが検索される結果となる。この例で検索されるのは、Ｂレストラン神田店、Ｙ銀行大手町支店、Ｘ銀行有楽町支店となる。
このような技術は、特許文献１に開示されている。
【特許文献１】特許第３６４９４３０号公報（特開２００１−１４３３８号公報）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記の空間検索機能を有するＲＤＢＭＳを用いて、「空間的に検索する条件」と「その他の絞込み条件」とを複合した結果を検索することは良くある用途である。たとえばカーナビゲーション分野での「経路沿いのガソリンスタンド」、不動産検索システムでの「駅から半径１ｋｍ以内で３ＬＤＫ以上のマンション」、エリアマーケティング分野での「既存店舗から半径２ｋｍ以内の競合店」などの付加条件付きの空間検索条件が挙げられる。
【０００９】
図１０に、空間検索条件と属性条件の複合条件の検索例を示す。本願の処理結果の例を示す図１０では、東京駅の座標（１００１）を中心に、所定半径の円（１００２）内にあるランドマークのうち、ランドマークのカテゴリが銀行を表しているものを検索した結果を示している。一般的な空間検索の処理結果を示す図９と同様に空間範囲外のランドマーク（１００３）は検索されず、さらに図１０では、空間範囲内だが属性が条件に適合しないランドマーク（１００４）も検索されない。つまり、空間範囲内且つ属性（属性情報ともいう）が条件に適合するランドマーク（１００５）のみが検索される結果となっている。この例では、Ｂレストラン神田店は検索円の範囲内ではあるが属性条件が銀行ではないので検索されず、Ｙ銀行大手町支店とＸ銀行有楽町支店が検索される結果となる。
【００１０】
これらを検索する際に、従来型のＲＤＢＭＳでは空間データカラムのほかに属性カラムを持ち、ＳＱＬの条件句で複数の検索条件をＡＮＤ条件で結ぶことにより、ＲＤＢＭＳ内で検索結果をマージし出力するという方式が考えられる。この場合、空間検索だけではあまり絞り込めないが、その後の付加条件で大きく絞り込める条件で、各々の条件で単独の検索を行ってはあまり性能が期待できない。しかしながら、そのような条件は往々にしてよく利用される条件となっているため、検索処理に時間が掛かり、高速な検索処理技術が望まれていた。
【００１１】
本発明の目的は、空間検索用インデクス内に複合条件のヒントとなる付加情報を含めることにより、空間検索用インデクスの検索時に付加情報についても検索を可能とし、高速な空間検索処理を実現することにある。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明の空間検索用インデクス（空間インデクスともいう）に、空間情報のほかに属性条件（付加情報）を１つまたは複数格納できるように拡張する。
【００１３】
通常の空間検索用インデクスでは、２次元データを扱う場合、ｘ座標とｙ座標を用いて空間分割を行い、その情報をインデクスに格納しておくことで、空間検索時にインデクスの参照により空間条件を絞り込むことができるよう設計されている。空間検索条件と付加属性条件との複合条件での検索では、空間検索で絞り込んだ後、他のカラムに格納された属性情報で判定するか、または他のカラムに割り当てられたインデクス検索結果とマージし、両方に含まれている結果を出力する。
【００１４】
ここで、空間検索用インデクス内に属性条件のヒント情報を格納しておけば、空間検索で絞り込むとともに、属性条件についても絞り込むことができる。空間検索用インデクス内に格納する属性条件は、付加属性をキーワードや数値等の形式で格納しても良いが、インデクスの肥大化を避けるため、付加属性を項目別、ジャンル別などで分類し、その分類情報をヒント情報としてビット列として格納し、ビット列から特定のビット条件を満たすものだけ検索する方式を採ることもできる。
【００１５】
また、２次元の空間検索用インデクス内に属性条件としてｚ軸の情報を取り込み、補助属性条件にも範囲検索を実装することにより、２次元の空間検索用インデクスで３次元の検索が可能となる。
【発明の効果】
【００１６】
本発明によれば、空間検索用インデクス内に複合条件のヒントとなる付加情報を含めることにより、空間検索用インデクスの検索時に付加情報についても検索が可能なため、高速な空間検索処理が実現できる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明を適用した空間検索システムの一実施の形態について説明する。
【００１８】
図１は、本発明の実施の形態の一例を示すシステム構成図のうち、ホストシステム（データ処理装置）と通信端末で構成される例を示す。
本空間検索システムは、地図を格納する記録装置（記憶装置）１０１と、検索処理を行うホストシステム１０２と、ユーザからの指示を入力する入力装置１０３と、結果や状態を表示する表示装置１０４から構成される。ホストシステム１０２は、計算機や情報処理装置でも実現することが可能である。
【００１９】
記録装置１０１は、地図データを格納する地図データベース１０５と、空間検索の高速化のために構成された空間検索用インデクス１０６から構成される。
【００２０】
ホストシステム１０２は、演算処理を行うＣＰＵ１０７と、モジュール（プログラム）やデータを格納するメモリ１０８と、検索処理要求に従い記録装置１０１にアクセスするデータベース処理モジュール１０９と、検索処理結果を配信する通信装置１１０から構成される。
【００２１】
データベース処理モジュール（データ処理プログラム）１０９は、空間座標データ（位置情報ともいう）およびその付加属性データ（属性情報ともいう）についての検索要求（検索条件を含んでもよい）と更新要求もしくは追加要求、削除要求を処理する空間検索用インデクス処理部１１１と、記録装置１０１にアクセスするデータアクセスモジュール１１２から構成される。一般的なデータベース処理を行うデータベース処理モジュールは、その他の検索要求や更新要求を処理するモジュールも含む場合もあるが、図１からは省略している。
【００２２】
空間検索用インデクス処理部１１１は、空間座標による検索処理を実行する空間検索処理モジュール１１３と、付加属性の検索処理を実行する付加属性検索処理モジュール１１４と、更新要求時に使用するインデクス更新処理モジュール１１５から構成される。
空間検索用インデクス処理部１１１は、空間検索条件と属性条件の複合条件において、空間検索用インデクス１０６を用いて地図データベース１０５に格納されているデータの中から必要な（検索要求を満たす）レコードを高速に選択することができる。
【００２３】
インデクス更新処理モジュール１１５は、空間座標データおよびその付加属性データの更新要求時に、地図データベース１０５と同期して空間検索用インデクス１０６を更新する。空間検索用インデクスは、空間インデクスともいう。
【００２４】
このホストシステム１０２から地図データおよび地図関連データを受信する移動端末装置１１６は、無線回線によって基地局１１７と通信可能となっている。そして、基地局１１７は有線の公衆回線網によるネットワーク１１８と接続され、このネットワーク１１８にホストシステム１０２が接続されている。従って、移動端末装置１１６とホストシステム１０２とは、基地局１１７に到る無線回線およびネットワーク１１８を通じてホストシステム１０２に接続されている（通信可能となっている）ことになる。
【００２５】
図２は、本実施の形態の一例を示すシステム構成図のうち、組み込み機器として構成される例を示す。本空間検索システムは、地図を格納する記録装置２０１と、検索処理を行う組み込み機器２０２と、ユーザからの指示を入力する入力装置２０３と、結果や状態を表示する表示装置２０４から構成される。
【００２６】
記録装置２０１は、地図データを格納する地図データベース２０５と、空間検索の高速化のために構成された空間検索用インデクス２０６から構成される。
【００２７】
組み込み機器２０２は、モジュールを実行するための処理を行うＣＰＵ２０７と、モジュール（プログラム）やデータを格納するメモリ２０８と、入力した（もしくは、受け付けた）検索処理要求に従い記録装置２０１にアクセスするデータベース処理モジュール２０９と、ユーザからの入力やユーザへの地図表示や状態表示を管理するユーザインタフェース処理モジュール２１０から構成される。これらの処理部やモジュールは、プログラムやオブジェクト、プロセス、スレッドなどにより実現することができる。また、これら処理部やモジュールはハードウェアで実現することも可能である。組込み機器は、地図検索装置やナビゲーションシステム、カーナビゲーションシステムでも良い。
【００２８】
データベース処理モジュール２０９は、図１と同様に、空間座標データおよびその付加属性データについての検索要求と更新要求を処理する空間検索用インデクス処理部２１１と、記録装置２０１にアクセスするデータアクセスモジュール２１２から構成される。一般的なデータベース処理モジュールは、その他の検索要求や更新要求を処理するモジュールも含む場合もあるが、図２からは省略している。
【００２９】
空間検索用インデクス処理部２１１は、空間座標による検索処理を実行する空間検索処理モジュール２１３と、付加属性の検索処理を実行する付加属性検索処理モジュール２１４と、更新要求時に使用するインデクス更新処理モジュール２１５から構成される。
【００３０】
空間検索用インデクス処理部２１１は、空間検索条件と属性条件の複合条件において、空間検索用インデクス２０６を用いて地図データベース２０５に格納されているデータの中から必要なレコードを高速に選択することができる。
【００３１】
インデクス更新処理モジュール２１５は、空間座標データおよびその付加属性データの更新要求時に、地図データベース２０５と同期して空間検索用インデクス２０６を更新する。ただし、組込み機器の構成により更新機能を持たない場合は、インデクス更新処理モジュール２１５は省略することができる。
【００３２】
図１の空間検索用インデクス１０６および図２の空間検索用インデクス２０６には、各々の地図データベース１０５、２０５に格納されている空間座標データのほかに、付加属性を格納している。このデータ構造を図３および図４に示す。空間の分割状態を木構造（３０１、４０１）で表し、その中の個別の要素を枝（３０２、４０２）と呼ぶ。各々の枝には、その枝が管理するデータのリストを格納する領域として葉（３０３、４０３）を１つまたは複数持つ。木構造によっては枝が葉を持たない実装もある。
【００３３】
この葉のデータリストの中に、各図形の個別の図形領域を格納し、検索時に参照する。本実施の形態では、この葉のデータリストの中に、各図形の個別の図形領域（３０４、４０４）に追加して、補助属性（付加属性）（３０５、４０５）を格納する。例としてｘ座標、ｙ座標に補助属性（付加属性）を１つ付加したものを図示した。この座標領域部は例で図示した１点座標以外にも、図形の外接矩形などの概形を格納し検索に使用する方法もよく使用される。また本実施の形態で付加する属性は、例で図示した場合は１つの属性だが、複数の属性を付加する方法もある。
【００３４】
本実施の形態では、この補助属性（付加属性）に対し、空間検索条件のほかに、補助属性検索条件を含めて検索を行うことができる。この検索処理の概要のフローチャートを図５に示す。この図５のフローチャートは、図１３の点線枠１３１０の処理フローを置き換えるものである。
【００３５】
まず、対称の図形が空間検索範囲条件に適合しているか否かを判別することで、指定された空間検索条件で空間検索用インデクスを参照して候補を絞り込む（ステップ５０１）。空間検索範囲条件に適合していたら、空間検索用インデクス内から、空間検索で絞り込まれた候補レコードに付加されている補助属性の値を取得して補助属性検索条件と照らし合わせることで対称の図形の属性が補助属性検索条件に適合しているか否かを判別し（ステップ５０２）、補助属性検索条件も満たしていたなら対象の図形を検索結果として出力する（ステップ５０３）。
【００３６】
なお、ステップ５０１の処理は空間検索処理モジュール１１３（２１３）が機能し、ステップ５０２の処理は付加属性検索処理モジュール１１４（２１４）が機能する。
【００３７】
ステップ５０２で判定する補助属性検索条件には、値の一致、範囲比較、ビット判定異の条件を指定できる。各々の処理のフローチャートを図６〜図８に示す。図６〜図８のフローチャートも図５と同様に、図１３の点線枠１３１０の処理フローを置き換えるものである。
【００３８】
図６の値の一致判定では、補助属性検索条件として、１つまたは複数の値を指定できる。
まず、対象の図形は空間検索範囲条件に適合しているか否かを判別することで指定された空間検索条件で候補を絞り込む（ステップ６０１）。空間検索範囲条件に適合していたら、その候補に付加されている補助条件の値を取得し、その値が補助属性検索条件として指定された値と一致しているかを判定することで対象の図形の属性が補助属性検索条件と一致しているか否かを判別する（ステップ６０２）。一致していたら対象の図形を検索結果として出力する（ステップ６０３）。ここで、補助属性検索条件として複数の値が指定された場合、ステップ６０２では、複数の値と比較しどれか１つでも一致したら適合と判定する。この判定は、たとえば補助属性にカテゴリ値を格納しておき、「特定のカテゴリと一致する」という補助検索条件で検索する際に使用する。この場合のデータ構造の例としては図３が挙げられる。たとえば図３の付加属性（３０５）にランドマークのカテゴリ情報を格納する。例としてガソリンスタンドやコンビニなどの種別をカテゴリＩＤとして数値化して格納した場合、「カテゴリＩＤが５０と一致する」という付加属性条件を付加すると、空間検索条件の適合した中から、カテゴリＩＤが一致するレコードだけを抽出できる。一致する条件には複数指定できるので、例えば「カテゴリＩＤが５０または６０と一致する」という検索条件を指定することもできる。
【００３９】
なお、ステップ６０１の処理は空間検索処理モジュール１１３（２１３）が機能し、ステップ６０２の処理は付加属性検索処理モジュール１１４（２１４）が機能する。
【００４０】
図７のビット判定条件では、補助属性検索条件として、ＡＮＤやＯＲなどのビット演算子と、ビット演算値を指定できる。
まず、対称の図形が空間検索範囲条件に適合しているか否かを判別することで、指定された空間検索条件で候補を絞り込む（ステップ７０１）。空間検索範囲条件に適合していたら、補助属性検索条件として指定された値と、絞り込んだ候補に付加されている補助条件（対象の図形の属性）の値とのＡＮＤ演算を行う（ステップ７０２）。
そして、補助属性検索条件として指定された演算子によって判定を分け（ステップ７０３）、ＡＮＤ演算子が指定されていた場合は、必要な全ビットが一致（つまり、ステップ７０２の演算結果が補助属性検索条件の値と一致）しているかを判定し（ステップ７０４）、あるいはＯＲ演算子が指定されていた場合は、どれか１ビットでも一致している（つまり、ステップ７０２の演算結果が０以外）かを判定し（ステップ７０５）、一致していたら対象の図形を検索結果として出力する（ステップ７０６）。
【００４１】
この判定は、たとえば補助属性にカテゴリ値を格納するが、カテゴリを即値で表すと条件が足りなくなる場合に、カテゴリやジャンルなどで分類しておき、その分類結果を抽象化してビット列として表現し、必要なビットを割り当て、１回のビット演算だけで「特定のカテゴリ群と一致する」などの補助検索条件で検索する際に使用する。
【００４２】
また、ビット列の元になる情報は１つではなく、複数の属性データにビットを割り当て、複数の属性検索条件について一度に検索処理を行うことができる。この場合のデータ構造の例としては図４が挙げられる。たとえば図４の付加属性（４０５）にランドマークのカテゴリ情報や、その他の情報を抽象化してビット列として格納する。
【００４３】
例えば、下位７ビット目（01000000）に「銀行なら１」となるビットを配置し、下位３ビット目（00000100）に「レストランなら１」となるビットを配置した場合、「付加属性情報と、ビット列01000000とのＡＮＤ条件が成立する」という付加属性条件を付加すると、空間検索条件の適合した中から、付加属性のビット条件が一致するレコードだけを抽出できる。このビット条件には、たとえば「夜間に営業しているビット」、「駐車場が付属している施設ビット」、「トイレが利用可能ビット」など、各々全く異なる付加情報をビット列として配置することができる。そして付加属性条件として、指定した任意のビットを同時に満たすＡＮＤ条件、どれか１つを満たすＯＲ条件で検索することができる。
【００４４】
なお、ステップ７０１の処理は空間検索処理モジュール１１３（２１３）が機能し、ステップ７０２の処理は付加属性検索処理モジュール１１４（２１４）が機能する。
【００４５】
図８の範囲比較判定では、補助属性検索条件として、値の範囲を指定できる。
まず、対称の図形が空間検索範囲条件に適合しているか否かを判別することで、指定された空間検索条件で候補を絞り込む（ステップ８０１）。空間検索条件に適合していたら、その候補に付加されている補助条件の値を取得し、その値が補助属性検索条件として指定された値の範囲に含まれているかを判定することで、対称の図形の属性が補助属性検索条件の範囲に適合しているか否かを判別する（ステップ８０２）。値の範囲に含まれていたら、対象の図形を検索結果として出力する（ステップ８０３）。この判定は、たとえば補助属性にｚ座標の値を格納しておき、空間検索条件にｚ軸の検索範囲を付加して３次元で検索する際に使用する。この場合のデータ構造の例としては図３が挙げられる。たとえば図３の付加属性（３０５）に高さ情報としてｚ軸の値を格納した場合、「ｚ軸の値が４０〜５０の範囲にある」という付加属性条件を付加すると、空間検索条件の適合した中から、ｚ軸の値が指定範囲に適合するレコードだけを抽出できる。
【００４６】
このように、地図データベースの空間検索用インデクス内に補助条件のヒント情報を格納し、検索処理で適切に利用することにより、ＤＢＭＳの複数検索条件結果のマージを行うことなく、空間検索用インデクスのアクセスだけで空間検索と補助条件検索の複合条件の検索を高速に行うことができる。
【００４７】
なお、ステップ８０１の処理は空間検索処理モジュール１１３（２１３）が機能し、ステップ８０２の処理は付加属性検索処理モジュール１１４（２１４）が機能する。
【００４８】
以上によれば、空間検索条件と補助属性条件との複合検索条件において、従来のＲＤＢＭＳのように、代表の検索条件の後に残りの条件で個別に絞り込んだり、複数の検索条件の結果をマージしたりすることなく、空間検索と同時に属性検索を行うことができる。また、空間検索用インデクスに補助属性データをそのまま取り込むことも可能だが、項目別やジャンル別で分類し、分類情報をビット列として格納し検索することにより、空間検索用インデクスの肥大化を避けることができると共に、ビット演算を用いることで１度の演算で複数の付加条件の判定を行うことができる。
【００４９】
また、２次元空間検索用インデクスに補助属性データとしてｚ軸の情報を取り込み、補助属性条件にも範囲検索を実装することにより、２次元の空間検索用インデクスで３次元の検索を可能とする。つまり、（ｎ＋１）次元目の情報を補助属性データとしてｎ次元の空間検索用インデクスを作成することにより、ｎ次元の空間検索用インデクスで（ｎ＋１）次元の検索を実現することが可能となる。
【図面の簡単な説明】
【００５０】
【図１】本発明の一実施の形態例を示すシステム構成図（ホストシステム）
【図２】本発明の一実施の形態例を示すシステム構成図（組み込み機器）
【図３】空間検索用インデクスのデータ構造の一例（属性値）
【図４】空間検索用インデクスのデータ構造の一例（属性の抽象化ビット列）
【図５】空間検索処理の概要のフローチャート
【図６】補助属性検索条件の処理部分のフローチャート（値の一致条件）
【図７】補助属性検索条件の処理部分のフローチャート（ビット判定条件）
【図８】補助属性検索条件の処理部分のフローチャート（範囲比較条件）
【図９】一般的な空間検索の処理結果の例（空間検索のみ）
【図１０】本発明の処理結果の例（空間検索＋属性検索）
【図１１】空間検索用インデクスの空間分割例（Ｒ−ｔｒｅｅ）
【図１２】空間検索用インデクスの空間分割例（四分木）
【図１３】空間検索用インデクスを用いた一般的な空間検索処理のフローチャート
【符号の説明】
【００５１】
１０１ 記録装置（記憶装置）
１０２ ホストシステム（データ処理装置）
１０３ 入力装置
１０４ 表示装置
１０５ 地図データベース
１０６ 空間検索用インデクス
１０７ ＣＰＵ
１０８ メモリ
１０９ データベース処理モジュール
１１０ 通信装置
１１１ 空間検索用インデクス処理部
１１２ データアクセスモジュール
１１３ 空間検索処理モジュール
１１４ 付加属性検索処理モジュール
１１５ インデクス更新処理モジュール
１１６ 移動端末装置
１１７ 基地局
１１８ ネットワーク
【特許請求の範囲】
【請求項１】
記憶装置を備えたデータ処理装置におけるデータ処理方法において、
複数の検索対象物における位置情報と属性情報とをリーフに含む空間インデクスを生成して前記記憶装置に格納し、
前記検索対象物を検索するための位置情報と属性情報とを含む検索要求の入力に応じて、前記記憶装置に格納された空間インデクスを参照し、前記検索要求を満たす前記検索対象物を抽出することを特徴とするデータ処理方法。
【請求項２】
前記属性情報をビット情報で構成することを特徴とする請求項１記載のデータ処理方法。
【請求項３】
前記位置情報に前記検索対象物のｘ座標における位置情報とｙ座標における位置情報とを割り当て、前記属性情報に前記検索対象物のｚ座標における位置情報を割り当てることを特徴とする請求項１記載のデータ処理方法。
【請求項４】
ｎ次元空間検索用インデクスのリーフに属性情報として追加軸である（ｎ＋１）次元における位置情報を記憶することにより、前記ｎ次元の空間検索用インデクスを参照して（ｎ＋１）次元の空間検索を行うことを特徴とする請求項１記載のデータ処理方法。
【請求項５】
記憶装置を備えたデータ処理装置において、
複数の検索対象物における位置情報と属性情報とをリーフに含む空間インデクスを生成して前記記憶装置に格納する手段と、
前記検索対象物を検索するための位置情報と属性情報とを含む検索要求の入力に応じて、前記記憶装置に格納された空間インデクスを参照し、前記検索要求を満たす前記検索対象物を抽出する手段とを備えることを特徴とするデータ処理装置。
【請求項６】
記憶装置を備えたデータ処理装置にデータを処理させるためのデータ処理プログラムにおいて、
前記データ処理装置に、
複数の検索対象物における位置情報と属性情報とをリーフに含む空間インデクスを生成させて前記記憶装置に格納させ、
前記検索対象物を検索するための位置情報と属性情報とを含む検索要求の入力に応じて、前記記憶装置に格納された空間インデクスを参照させ、前記検索要求を満たす前記検索対象物を抽出させることを特徴とするデータ処理プログラム。
【請求項１】
記憶装置を備えたデータ処理装置におけるデータ処理方法において、
複数の検索対象物における位置情報と属性情報とをリーフに含む空間インデクスを生成して前記記憶装置に格納し、
前記検索対象物を検索するための位置情報と属性情報とを含む検索要求の入力に応じて、前記記憶装置に格納された空間インデクスを参照し、前記検索要求を満たす前記検索対象物を抽出することを特徴とするデータ処理方法。
【請求項２】
前記属性情報をビット情報で構成することを特徴とする請求項１記載のデータ処理方法。
【請求項３】
前記位置情報に前記検索対象物のｘ座標における位置情報とｙ座標における位置情報とを割り当て、前記属性情報に前記検索対象物のｚ座標における位置情報を割り当てることを特徴とする請求項１記載のデータ処理方法。
【請求項４】
ｎ次元空間検索用インデクスのリーフに属性情報として追加軸である（ｎ＋１）次元における位置情報を記憶することにより、前記ｎ次元の空間検索用インデクスを参照して（ｎ＋１）次元の空間検索を行うことを特徴とする請求項１記載のデータ処理方法。
【請求項５】
記憶装置を備えたデータ処理装置において、
複数の検索対象物における位置情報と属性情報とをリーフに含む空間インデクスを生成して前記記憶装置に格納する手段と、
前記検索対象物を検索するための位置情報と属性情報とを含む検索要求の入力に応じて、前記記憶装置に格納された空間インデクスを参照し、前記検索要求を満たす前記検索対象物を抽出する手段とを備えることを特徴とするデータ処理装置。
【請求項６】
記憶装置を備えたデータ処理装置にデータを処理させるためのデータ処理プログラムにおいて、
前記データ処理装置に、
複数の検索対象物における位置情報と属性情報とをリーフに含む空間インデクスを生成させて前記記憶装置に格納させ、
前記検索対象物を検索するための位置情報と属性情報とを含む検索要求の入力に応じて、前記記憶装置に格納された空間インデクスを参照させ、前記検索要求を満たす前記検索対象物を抽出させることを特徴とするデータ処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００７−２３３６５８（Ｐ２００７−２３３６５８Ａ）
【公開日】平成１９年９月１３日（２００７．９．１３）
【国際特許分類】
【出願番号】特願２００６−５４１６０（Ｐ２００６−５４１６０）
【出願日】平成１８年２月２８日（２００６．２．２８）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
【公開日】平成１９年９月１３日（２００７．９．１３）
【国際特許分類】
【出願日】平成１８年２月２８日（２００６．２．２８）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
[ Back to top ]