(57)【要約】【課題】空間抽出向け多次元木構造インデックスでは静的もしくは動的なインデックスの最適化を必要となり、更新頻度が高いデータほどコストが増大する傾向にある。【解決手段】平面では２次元（２項）空間では３次元（３項）を１項に集約する。【選択図】図１
2010182097.tif 000002
【特許請求の範囲】
【請求項１】
空間データの各座標を、０埋めして大きな桁から順に１数字ずつ順に並べてＤＳＩとしてデータベースに格納するＤＳＩ格納手段と、
抽出条件に従って前記データベースからデータを抽出する抽出手段と、を備えることを特徴とする空間抽出装置。
【請求項２】
前記ＤＳＩ格納手段は、負値となる場合に取り得る範囲の最小値を基に前記各座標のオフセット値を加算して正のＤＳＩとすることを特徴とする請求項１記載の空間抽出装置。
【請求項３】
前記ＤＳＩ格納手段は、小数値となる場合にスケール因子を設定し乗じて全データを整数とすることを特徴とする請求項１又は２記載の空間抽出装置。
【請求項４】
空間データの各座標を、０埋めして大きな桁から順に１数字ずつ順に並べてＤＳＩとしてデータベースに格納するＤＳＩ格納ステップと、
抽出条件に従って前記データベースからデータを抽出する抽出ステップと、を備えることを特徴とする空間抽出装置の抽出方法。
【請求項５】
前記ＤＳＩ格納ステップは、負値となる場合に取り得る範囲の最小値を基に前記各座標のオフセット値を加算して正のＤＳＩとすることを特徴とする請求項４記載の空間抽出装置の抽出方法。
【請求項６】
前記ＤＳＩ格納ステップは、小数値となる場合にスケール因子を設定し乗じて全データを整数とすることを特徴とする請求項４又は５記載の空間抽出装置の抽出方法。
【請求項７】
空間データの各座標を、０埋めして大きな桁から順に１数字ずつ順に並べてＤＳＩとしてデータベースに格納するＤＳＩ格納処理と、
抽出条件に従って前記データベースからデータを抽出する抽出処理と、を備えることを特徴とするコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、１０進空間インデックス（Decimal Spatial Index）により空間抽出を行う空間抽出装置、空間抽出装置の抽出方法及びプログラムに関する。
【背景技術】
【０００２】
地理情報システム（Geographic Information System  以下ＧＩＳと表記）では地図データの空間抽出は必要不可欠であり、またそのレスポンスがＧＩＳそのものの性能といっても過言ではない。
【０００３】
近年、ＧＩＳへの認識が高まり、需要が大きくなってきたのと同期して、その扱う空間データ量は膨大になってきており、空間抽出処理への負荷はより大きいものとなっている。
【０００４】
その解決手法として、非特許文献１に記載されるようなR-treesを含め、多次元対応のインデックスが開発されている。
【０００５】
平面上にある図形データの位置はＸ，Ｙの２つの値で表され、それが分布している中で、矩形範囲で抽出するための条件は
【０００６】
矩形範囲最小Ｘ＜=Ｘ
ＡＮＤ  矩形範囲最大Ｘ＞=Ｘ
ＡＮＤ  矩形範囲最小Ｙ＜=Ｙ
ＡＮＤ  矩形範囲最大Ｙ＞=Ｙ
【０００７】
であり、また図形データは必ずしも１点で定義されるポイントだけではなく、ライン及びポリゴンもあるため、各図形データのＭＢＲをminＸ、minＹ、maxＸ、maxＹであらわすと
【０００８】
矩形範囲最小Ｘ＜=maxＸ
ＡＮＤ  矩形範囲最大Ｘ＞=minＸ
ＡＮＤ  矩形範囲最小Ｙ＜=maxＹ
ＡＮＤ  矩形範囲最大Ｙ＞=minＹ
【０００９】
が抽出条件となる。前記の条件式は数学的には、何ら問題はないが、図形データをデータベースに格納し、またそれが100万超の件数ともなると、検索レスポンスは大きく落ちてくる。
【００１０】
これは検索処理内部で各図形データのＭＢＲであるminＸ、minＹ、maxＸ、maxＹの４つの項目に対して不等号判定が行なわれることによるためであり、格納データ件数に比例、もしくはそれ以上にレスポンスに影響することになる。前出のR-Treeインデックス等の各種手法もこのレスポンス向上のための手段である。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Antonin Guttman、"R-TREES A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING"、[online]、Proceedings of the 1984 ACM SIGMOD international conference on Management of data、[平成２１年１月２６日検索]、インターネット＜URL: //www.sai.msu.su/~megera/postgres/gist/papers/gutman-rtree.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、多次元対応のインデックスにおいては、多次元木構造インデックスを持つため、静的もしくは動的なインデックスの最適化が必要となり、更新頻度が高いデータほどコストが増大する傾向にある。
【００１３】
ＧＩＳにおける空間抽出の条件としては、平面上座標軸に直交する任意の矩形内にある空間データの抽出が利用頻度での９０％以上を占める。矩形ではなく複雑な形状のポリゴンがその抽出範囲であっても、ポリゴンのＭＢＲ（最小外接矩形）を条件として抽出し、その結果を幾何学演算によりさらに絞り込むことが従来より行われている。
【００１４】
よって、平面上座標軸に直交する任意の矩形内にある空間データの抽出を効率良く運用でき、かつデータの更新時にも負荷の少ない手法が求められる。
【００１５】
そこで本発明は、上記問題点に鑑みてなされたもので、インデックスの再構築を低コストにて行うことを目的とする。
【課題を解決するための手段】
【００１６】
上記課題を解決するため、本発明における空間抽出装置は、空間データの各座標を、０埋めして大きな桁から順に１数字ずつ順に並べてＤＳＩとしてデータベースに格納するＤＳＩ格納手段と、抽出条件に従ってデータベースからデータを抽出する抽出手段と、を備えることを特徴とする。
【００１７】
また、本発明における空間抽出装置の抽出方法は、空間データの各座標を、０埋めして大きな桁から順に１数字ずつ順に並べてＤＳＩとしてデータベースに格納するＤＳＩ格納ステップと、抽出条件に従ってデータベースからデータを抽出する抽出ステップと、を備えることを特徴とする。
【００１８】
また、本発明におけるプログラムは、空間データの各座標を、０埋めして大きな桁から順に１数字ずつ順に並べてＤＳＩとしてデータベースに格納するＤＳＩ格納処理と、抽出条件に従ってデータベースからデータを抽出する抽出処理と、を備えることを特徴とするコンピュータに実行させることを特徴とする。
【発明の効果】
【００１９】
本発明により、平面では２次元（２項）空間では３次元（３項）を１項に集約することが可能となるため、アルゴリズムの簡素化を実現し、かつデータ更新時のインデックス再構築コストを一般的な単項目向けのインデックス構造で十分なレスポンスを得ることができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施形態に係る空間階層イメージ図である。
【図２】本発明の他の実施形態に係る空間階層イメージ図である。
【発明を実施するための形態】
【００２１】
（実施形態１）
本発明の実施形態における１０進空間インデックス（Decimal Spatial Index  以下ＤＳＩと表記）の求め方について説明する。
【００２２】
１．空間データのとりうる範囲はＸＹともに0から999までとする。
２．Ｘ、Ｙの座標値は正の整数とする。
この条件で  Ｘ＝571、Ｙ＝613のポイントのＤＳＩを求める。
【００２３】
１．Ｘ、Ｙ座標を最大とりうる範囲に０埋めした文字列とする。
Ｘ＝５７１
Ｙ＝６１３
【００２４】
２．Ｘ、Ｙの各桁を順に１桁ずつ並べた文字列を作る。
５６−７１−１３
※判りやすくするため各桁の間に−をつけてある。
【００２５】
左端の５６は１辺が１００の原点（0,0）からＸ方向に６番目（０から始まるため）、Ｙ方向に７つ目のエリアを表している。
【００２６】
次の７１は、そのエリア内の１辺が１０のＸ方向に８番目，Ｙ方向に２番目のエリアを、最後の１３は、そのエリア内の１辺が1のＸ方向に２番目，Ｙ方向に４番目のエリアをそれぞれ表す。
【００２７】
図１は、本実施例における模式図であり、左から１次エリア１、２次エリア２、３次エリア３をそれぞれ示す。
【００２８】
つまり、最初の１辺が１００のエリアを１次エリアとするとＸ，Ｙの座標から求めた５６−７１−１３は、１次エリア５６、２次エリア７１、３次エリア１３にそのポイントが存在していることが表現される。
【００２９】
次に、同じ条件でライン、ポリゴンについてＤＳＩを求める。ライン、ポリゴンの場合は図形データのＭＢＲのminＸ、minＹ、maxＸ、maxＹの値をもとにする。
【００３０】
minＸ＝571、minＹ＝613
maxＸ＝573、maxＹ＝615
【００３１】
の矩形をＭＢＲとするラインまたはポリゴンでは、minＸ＝571、minＹ＝613から５６−７１−１３
【００３２】
maxＸ＝573、maxＹ＝615から５６−７１−３５が求まり、２つの共通している部分は５６−７１である。
【００３３】
つまり、このラインまたはポリゴンは、１次エリア５６、２次エリア７１に存在している、言い換えれば、このラインまたはポリゴンを内包するエリアは５６−７１であるといえる。
【００３４】
また、別に
【００３５】
minＸ＝571、minＹ＝613
maxＸ＝573、maxＹ＝620
【００３６】
の矩形をＭＢＲとするラインまたはポリゴンでは、minＸ＝571、minＹ＝613から５６−７１−１３
【００３７】
maxＸ＝573、maxＹ＝620から５６−７２−３０が求まり、２つの共通している部分は５６だけである。
【００３８】
最初のラインまたはポリゴンは５６−７１、次のラインまたはポリゴンは５６、これが各図形データのＤＳＩとなる。
【００３９】
前記のポイントを含め３つの図形データをＤＳＩ順（文字列順）に並べると、
【００４０】
２つ目のラインまたはポリゴン  ５６
１つ目のラインまたはポリゴン  ５６−７１
ポイント                      ５６−７１−１３
となり、図形データは１次エリア、その内部の２次エリア、そのまた内部の３次エリア順に並ぶ。
【００４１】
（実施形態２）
次に、件数の多いデータでの検索方法について説明する。図２は、ＤＳＩ５３−６２におけるデータの模式図である。
【００４２】
Ａは５３−６２の次のレベルに収まっており、ＤＮＳＩは５３６２２７
Ｂは５３６２
ＣはＡよりさらに詳細なレベルに収まっており、５３６２２７６３
Ｄは５３６２
Ｅは５３６２１８
Ｆは５３６２３５
Ｇは５３６２５８
【００４３】
と表される。ＤＳＩ順で並べると
【００４４】
Ｂ  ５３６２
Ｄ  ５３６２
Ｅ  ５３６２１８
Ａ  ５３６２２７
Ｃ  ５３６２２７６３
Ｆ  ５３６２３５
Ｇ  ５３６２５８
【００４５】
抽出条件とするＸは、Ａ同様に５３６２２７とすると、
【００４６】
（１）抽出条件のＤＳＩより上位のエリアを持つ図形は全て対象とする場合
１．ＤＳＩが５３の図形を検索する。
本実施例ではなし
【００４７】
２．ＤＳＩが５３６２の図形を検索する。
Ｂ、Ｄが該当
【００４８】
（２）抽出条件のＤＳＩ以上、抽出条件ＤＳＩの次ＤＳＩ未満を対象とする場合
３．ＤＳＩが５３６２２７以上、５３６２２８未満の図形を検索する。
Ａ、Ｃが該当
【００４９】
が条件となる。目視では、ＤはＸの条件を満たしていないのは明らかであるが、抽出結果からの幾何学演算により判定される。
【００５０】
ここで、本発明の実施形態におけるＤＳＩは、
１．各図形が持つのは自身を内包する最小の１つのＤＳＩのみである。
基本的に大きい図形は、大きいエリアのＤＳＩをもち、小さい図形は小さいエリアのＤＳＩをもつこととなり、あえてレベルをそろえることはしない。
【００５１】
２．０から始まる１０進数でエリアが表現されるため小さいエリアと大きいエリアの比較が容易である。
２５４３８９の上位エリアは２５４３、その上位は２５となる。
【００５２】
３．他の図形との相対的なインデックスではないため、データの追加削除時インデックス再構築が不要。
【００５３】
４．標準的なＳＱＬ構文で問い合わせを行なうことが可能であるため応用範囲が広い。
【００５４】
５．ＤＳＩは図形データの座標値から一意に求まるため、実装時のチューニングが不要である。
【００５５】
また、実際の地図データにＤＳＩを適用する場合、以下の点に注意が必要である。
【００５６】
１．負値の座標
地図データでは、負値をとる場合もあるため、ＤＳＩ生成のためにはとりうる範囲の最小値をもとにＸ，Ｙのオフセット値を加算することで、全データを正値としてＤＳＩを求める。
【００５７】
２．小数値
負値同様に地図データでは小数値までもっている場合があるため、スケール因子を設定し乗じることで、全データを整数としてＤＳＩを求める。
【００５８】
ただし、実座標をオフセットおよびスケール因子で更新する必要は無く、あくまでＤＳＩを求める過程でのみである。
【００５９】
また、ＤＳＩの桁数（文字数）は平面直角座標系の１つの系の範囲±300km、±160kmをもとに1mm精度とするとＸ、Ｙは999,999.999m、各９桁であり、この環境では１８桁で1mmまで管理できることが推察される。
【００６０】
同様に地球の長半径約6,378kmをもとにしても２２桁で網羅できることがわかる。また、ＤＳＩは３次元データに容易に適用することが可能である。
【００６１】
Ｘ＝５７１
Ｙ＝６１３
Ｚ＝４８９
【００６２】
から、５６４−７１８−１３９と、Ｚ値も含めたＤＳＩを生成するだけで、立方体エリアでの検索が可能となる。
【００６３】
データベース管理システムとしてその抽出条件はインデックス項目となっている単項目のみが条件となる検索が最もレスポンスが良いため、本実施形態におけるＤＳＩはＸ，Ｙの値を１つにすることで、抽出条件を単項目とすることができる。
【００６４】
また、データの追加削除が頻繁に行なわれてもインデックス再構築に負荷がかからないように図形データ間での相対的位置関係によらない。
【産業上の利用可能性】
【００６５】
本発明によれば、ＧＩＳ、特に更新頻度の高い大規模なデータ量のシステムといった用途に適用できる。
【００６６】
以上、実施の形態を説明したが、特許請求の範囲に定義された本発明の広範囲な趣旨および範囲から逸脱することなく、これら実施の形態や具体例に様々な修正および変更が可能である。
【符号の説明】
【００６７】
１    １次エリア
２    ２次エリア
３    ３次エリア
【図１】
2010182097.tif 000003
【図２】
2010182097.tif 000004