(57)【要約】この発明は複数のエンティテイに対してインデックスを構築するための方法に関し、各エンティテイは空間内で定義された点によって表わされている。この方法は：ｉ）一番遠く離れている点をもつエンティテイを識別する段階と；ｉｉ）第一の領域を作り、この第一の領域の末端は該識別されたエンティテイを表わしている点によって与えられるようにする段階と；ｉｉｉ）該第一の領域内に入るエンティテイを該第一の領域に対応している記憶領域に割当てる段階と；ｉｖ）該第一の領域を複数の第二の領域に分割する段階と；ｖ）該複数の第二の領域の各々について：ａ）該各第二の領域を該第一の領域にリンクし、かつ、ｂ）段階ｉ）ないしｖ）を該第一の領域が単一の点を含むまで繰返す段階と；ｖｉ）該第一の領域の各々に対応している該記憶領域をインデックスに書込む段階とを備えている。【選択図】図２
2004516553.tif 000002
【特許請求の範囲】
【請求項１】
複数のエンティテイに対してインデックスを構築する方法であって、各エンティテイは空間内で定義された点により表わされており、該方法は：
ｉ）一番遠く離れている点をもつエンティテイを識別する段階と；
ｉｉ）第一の領域を作り、この第一の領域の極値が該識別したエンティテイを表わす点によって与えられるようにする段階と；
ｉｉｉ）該第一の領域に入るエンティテイを該第一の領域に対応している記憶領域に割当てる段階と；
ｉｖ）該第一の領域を複数の第二の領域に分割する段階と；
ｖ）該複数の第二の領域の各々について、
ａ．該各第二の領域を該第一の領域にリンクし、かつ、
ｂ．該第一の領域が単一の点を含むまで段階（ｉ）ないし（ｖ）を繰返す段階と；
ｖｉ）該各第一の領域に対応している記憶領域を該インデックスに対して書込む段階とを備えている方法。
【請求項２】
請求項１記載の方法であって、該識別する段階（ｉ）は、二次元の各次元でエンティテイ間の距離を計算する段階と；
各該次元について、どのエンティテイが一番大きな距離をエンティテイ間で有しているかを識別して、それにより、二つの次元が互に他と垂直であるときには、段階（ｉｉ）で作られた第一の領域が少くとも二つの点で定義される矩形であるようにする段階とを備えている方法。
【請求項３】
請求項１または２記載の方法であって、該第一の領域は段階（ｉｖ）で四つの第二の領域に分割される方法。
【請求項４】
請求項１ないし３のいずれか１項記載の方法であって、段階（ｖ）が該第二の領域の各々について反復して繰返される方法。
【請求項５】
請求項１ないし４のいずれか１項記載の方法であって、さらに、該各第一の領域内部の各エンティテイをデータベースに書込む段階と、該データベースに書込まれたエンティテイの数のレジスタを維持する段階と、該第一の領域の各々について、現在のレジスタの数を該第一の領域に対応する該記憶領域に書込む段階とを備えている方法。
【請求項６】
請求項５記載の方法であって、エンティテイは第一の領域のサイズに従ってデータベースに書込まれていて、一番小さな第一の領域に入るエンティテイがデータベースに最初に書込まれる方法。
【請求項７】
請求項１ないし請求項６のいずれか１項記載の方法であって、段階（ｉ）ないし（ｖｉ）を発動するためのトリガを示す信号を受信することを含んでいる方法。
【請求項８】
所定の領域によって包含される１又はそれ以上のエンティテイを検索する方法であって、各エンティテイは請求項１ないし７のいずれか１項記載の方法によりインデックス付けがされていて、
（ａ）該所定の領域によって包含される１又はそれ以上の区域を識別し、各区域は１又はそれ以上の点を取囲んでいて、リンクデータと関係しており、リンクデータは、各区域について、その区域により取囲まれている点を識別する段階と；
（ｂ）該識別した区域に対応しているリンクデータにアクセスして該識別した区域により取囲まれた点を検索するようにする段階とを含む方法。
【請求項９】
請求項８記載の方法であって、該識別する段階（ａ）は、
（ｉ）第一の区域を検索する段階と；
（ｉｉ）該第一の区域の広がりの程度を該所定の領域の広がりの程度と比較して、該第一の区域が該所定の領域と重なるかどうかを確定するようにする段階と；もし重なりが存在するときは、
（ｉｉｉ）継続して第二の区域を検索し、ここで第二の区域の各々は該第一の区域により包含されるものであるとし、また、各第二の区域について、該第二の区域が該所定の領域により完全に包含されているような重なりとなるまで、段階（ｉｉ）と（ｉｉｉ）とを繰返す段階とを含む方法。
【請求項１０】
請求項９記載の方法であって、該複数の点が、それぞれ第一と第二の区域の間の関係に従って、点のリストとして前もって記憶されていて、しかも該リンクデータは該点のリスト内の対応している取囲まれた点の第一のものの位置を示している値を含んでおり、さらに該アクセスする段階（ｂ）は、該識別された区域の各々について；
取囲まれた点の数を表わしている識別子を検索し、また該識別した区域と関係する位置の値を検索する段階と；
該点のリストにアクセスして該位置の値により与えられる該リスト内の位置から取囲まれた点の数を検索する段階とを備えている方法。
【請求項１１】
請求項８ないし請求項１０のいずれか１項記載の方法であって、該区域と、対応しているリンクデータとがインデックス内に記憶される方法。
【請求項１２】
請求項８ないし請求項１１のいずれか１項記載の方法であって、該所定の領域がレンジ情報に対応する方法。
【請求項１３】
請求項１２記載の方法であって、該レンジ情報は地理的レンジ情報、動作時間情報、配信時間情報、及び医療情報のいずれか一つを含んでいる方法。
【請求項１４】
計算機プログラムもしくは計算機プログラムの組であって、計算機又は計算機の組に対して、請求項１ないし請求項６項記載の方法を実行させるようにする一組の命令を備えている計算機プログラムもしくは計算機プログラムの組。
【請求項１５】
計算機プログラムもしくは計算機プログラムの組であって、計算機又は計算機の組に対して、請求項８ないし請求項１３に記載の方法を実行するようにする一組の命令を備えている計算機プログラムもしくは計算機プログラムの組。
【請求項１６】
搬送波内に組込まれて、命令のシーケンスを表わしている計算機データ信号であって、該命令は、プロセッサによって実行されるときには請求項１ないし請求項６記載の方法を該プロセッサに実行させるものである信号。
【請求項１７】
搬送波内に組込まれて、命令のシーケンスを表わす計算機データ信号であって、該命令はプロセッサによって実行されるときには、請求項８ないし請求項１３に記載の方法を該プロセッサに実行させるものである信号。
【請求項１８】
一組のアイテムにインデックスを付ける方法であって、各アイテムは空間内の位置によって提示可能であり、かつ該アイテムの組は該組内での該アイテムの位置の該空間内での分布によって提示可能なものであり、該方法は；
ｉ）該空間の一部を定義して、この一部が該アイテムの組の位置を含む段階と；
ｉｉ）この部分をサブ部分に分割する段階と；
ｉｉｉ）１又はそれ以上のサブ部分をそれが含んでいる位置の数により選ぶ段階と；
ｉｖ）各選ばれたサブ部分について、それが分割された前の部分を記録する段階と；
ｖ）該アイテムの位置を含んでいるそれぞれのサブ部分により該アイテムにインデックスを付ける段階とを含む。
【請求項１９】
請求項１８記載の方法であって、該空間の一部についての定義は該空間内での境界を生成するのに適応されていて、この境界は前記分布の外側の限界と少くとも実質的に一致している方法。
【請求項２０】
請求項１９記載の方法であって、該１又はそれ以上のサブ部分は該サブ部分がもし１又はそれ以上の位置を含むならば選ばれる方法。
【請求項２１】
請求項１８ないし請求項２１のいずれか１項記載の方法であって、さらに各選ばれたサブ部分をさらにサブ部分に分割して、さらに分割したサブ部分が異なる数の位置を含むものとし、また各さらに分割したサブ部分について、各選ばれたサブ部分が少くとも実質的には単一の位置と一致するようになるまで、段階ｉｉｉ）とｉｖ）とを繰返し、前記アイテムについてのインデックス付けがそれぞれのサブ部分に従って行なわれて、各アイテムについて単一の位置と少くとも実質的には一致するようにする方法。
【請求項２２】
請求項１８ないし請求項２１のいずれか１項記載の方法であって、該部分とサブ部分とが領域であり、該アイテムを表わしている位置が二次元の値によって識別される方法。
【請求項２３】
請求項２２に記載の方法であって、前記領域は正方形または長方形である方法。
【請求項２４】
請求項１８ないし請求項２３のいずれか１項記載の方法であって、各位置が点を備えている方法。
【請求項２５】
複数のエンティテイに対してインデックスを構築する方法であって、各エンティテイは空間内で定義された点により表わされており、該方法は：
ｉ）インデックスを付けることになるエンティテイを示すデータを入力する段階と；
ｉｉ）該入力したデータの中で点が一番遠く離れているエンティテイを識別する段階と；
ｉｉｉ）第一の領域を創り、この第一の領域の極値が該識別したエンティテイを表わしている点により与えられるようにする段階と；
ｉｖ）該第一の領域内部に入るエンティテイを該第一の領域に対応している記憶領域に割当てる段階と；
ｖ）該第一の領域を複数の第二の領域に分割する段階と；
ｖｉ）該複数の第二の領域の各々について、
ａ．各該第二の領域を該第一の領域にリンクし、かつ
ｂ．段階（ｉｉ）ないし段階（ｖｉ）を該第一の領域が単一の点を含むまで繰返す段階と；
ｖｉｉ）各該第一の領域に対応している該記憶領域を該インデックスに書込む段階とを備えている。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、データベース内に記憶されるエンティティ（ｅｎｔｉｔｉｅｓ）とともに使用するインデックスを付ける方法に関する。
【０００２】
【従来の技術】
あるデータベース内に莫大な数のエンティテイが存在しているときには、そのデータベース内のデータに関する問合せと合理的な時間的期間の中で調和をとりながらエンティテイを識別することが決して些細な活動でないことはすぐに分ることである。検索プロセスを容易にするために、データベース内のデータは、一般に何らかの方法でインデックスを付けられ、問合せはそこでインデックスについて実行される。エンティテイがインデックスを付けられるやり方は検索することの品質と速度について重要な意味をもつと期待できるのであり、情報がデータベース内に次第に増すように記憶されると、データにインデックスを付ける改良方法を見付けることが重要な関心事となる。
【０００３】
場所の名称に基づいて、位置データにインデックスを付けることは知られている。また場所の名称から地理的な一組の座標を検索して、この座標から抽出された地形学的（ｔｏｐｏｌｏｇｉｃａｌ）情報に基づいたインデックスを構築することも知られている（例えば、“ＧＩＰＳＹ”はＵＣバークレイ校でジョイントＮＳＦ／ＮＡＳＡ／ＡＲＰＡ（Ｗｉｌｅｎｓｋｙ他，１９９４）主導で共同開発されている）。さらに、地理的な座標自体に基づいてインデックスを構築することも知られている。ＯｒａｃｌｅＴＭのようなデータベースベンダ（ｖｅｎｄｏｒｓ）は幾何学的なデータを記憶してインデックスを付けるためのシステムを開発しており、例えばＯｒａｃｌｅ空間データカートリッジがそれであり、これは空間的な問合せがＳＱＬの拡張された（標準形ではない）形式を用いて実行されるようにしている。その他のベンダはＭａｐＩｎｆｏＴＭ，ＳｐａｔｉａｌＷａｒｅＴＭ，ＩｎｎｏｇｉｓｔｉｃＴＭ，及びＩｎｆｏｒｍｉｘＴＭのようなもので、空間データを処理するのに類似の専有のやり方を有している。とくに、ＩｎｎｏｇｉｓｔｉｃＴＭはＣａｒｔｏｌｏｇｙ ＤＳＩとして知られている製品を開発し、これが幾何学的なベクトルデータをブロブ（ｂｌｏｂｓ）として記憶する（これは二値の大きなオブジェクトであり、基礎に置かれたデータベースによっては真性な（ｉｎｔｒｉｎｓｉｃａｌｌｙ）ものとして認識できないものである。ＩｎｎｏｇｉｓｔｉｃＴＭはよく知られた“クアッド−ツリー（ｑｕａｄ ｔｒｅｅ）”というアイデアに基づいてデータベースの外部でインデックスを創ることもする。このインデックスデータはバイナリ−ツリー（ｂｉｎａｒｙ−ｔｒｅｅ）の構造の中に記憶されて、ＤＣＯＭミドルウェアサービスによってアクセスされる。
【０００４】
【発明が解決しようとする課題】
ＯｒａｃｌｅＴＭとＩｎｎｏｇｉｓｔｉｃＴＭの両システムは、クアッド−ツリー方法の使用を行ない、この方法ではレイヤ（ｌａｙｅｒ）の全領域が分割されまた部分分割（ｓｕｂｄｉｖｉｄｅｄ）されて一連の四つがネストした（ｎｅｓｔｅｄ）正方形とされる。全体の領域は０，１，２，３と指定された四つの正方形の一つに対して指定されている。こういった正方形の各々は四つのもっと小さな正方形に部分分割される。正方形１の領域は１０，１１，１２，１３となる。こういったものの各々がさらに部分分割され、これが意味しているのは、例えば正方形１１の部分分割がインデックス値１１０，１１１，１１２，１１３を指定されるということである。結果として、地図の中のいずれの場所も単一のインデックス番号によって参照することができる。このクアッドツリーの方法での不都合な点は、部分分割された正方形の内部に点が一つも存在しないとすると処理時間が浪費されるということである。もしインデックス付けが大きな領域にわたって実行されるとすると、この浪費した処理時間は些細なものとはならずコスト高のものとなる。
【０００５】
【課題を解決するための手段】
この発明の第一の特徴によると、複数のエンティテイに対してインデックスを構築する方法が提供され、各エンティテイは空間内で定義された点により表わされており、該方法はｉ）一番遠く離れている点をもつエンティテイを識別する段階と；
ｉｉ）第一の領域を作り、この第一の領域の極値が該識別したエンティテイを表わす点によって与えられるようにする段階と；
ｉｉｉ）該第一の領域に入るエンティテイを該第一の領域に対応している記憶領域に割当てる段階と；
ｉｖ）該第一の領域を複数の第二の領域に分割する段階と；
ｖ）該複数の第二の領域の各々について、
ａ．該各第二の領域を該第一の領域にリンクし、かつ、
ｂ．該第一の領域が単一の点を含むまで、段階（ｉ）ないし（ｖ）を繰返す段階と；
ｖｉ）該各第一の領域に対応している記憶領域を該インデックスに対して書込む段階とを備えている。
【０００６】
一番遠くに離れている点を識別することによって、このインデックスを付ける方法はインデックス用空間を本質的に“シュリンク（ｓｈｒｉｎｋｓ）”して、それにより、点を含む領域上でのみインデックスを付けるようにする。したがって、記憶領域は相応じてコンパクトなものとなり、これが記憶空間の使用を最小にするという面で好都合となる。
【０００７】
第二の領域は、いわゆる点の“リンクしたリスト”を介して第一の領域とリンクすることができ、このリストは当業者にとって知られている効果的なリンク機構（ｍｅｃｈａｎｉｓｍ）である。
【０００８】
好ましくは、該第一の領域は段階（ｉｖ）で四つの第二の領域に分割され、また段階（ｖ）が該第二の領域の各々について反復して繰返される。好都合なのは、該識別する段階（ｉ）は、二次元の各次元でエンティテイ間の距離を計算する段階と；各該次元について、どのエンティテイが一番大きな距離をエンティテイ間で有しているかを識別して、それにより、二つの次元が互に他と垂直であるときには、段階（ｉｉ）で作られた第一の領域が少くとも二つの点で定義される矩形であるようにする段階とを備えていることである。
【０００９】
便利なのは、この方法がさらに、該各第一の領域内の各エンティテイをデータベースに書込む段階と、該データベースに書込まれたエンティテイの数のレジスタを維持する段階と、該第一の領域の各々について、現在のレジスタの数を該第一の領域に対応している該記憶領域に書込む段階とを備えていることである。
【００１０】
好都合なのはこの発明の前記第一の特徴に従ってインデックスを付けられたエンティテイが検索されるようにできることである。とくに該エンティテイに対応している点についてみれば、所定の領域により包含されている点は次の段階を実行することによって検索できる。すなわち
（ａ）該所定の領域によって包含される１またはそれ以上の区域を識別し、各区域は１またはそれ以上の点を取囲んでいて、リンクデータと関係しており、リンクデータは、各区域について、その区域により取囲まれている点を識別する段階と；
（ｂ）該識別した区域に対応しているリンク用データにアクセスして該識別した区域により取囲まれた点を検索するようにする段階である。
【００１１】
この区域は、この発明の第一の特徴によりインデックスを付けられた記憶領域に対応している。したがって記憶領域がコンパクトであるので、上述したように区域は点の周りに“シュリンクラップ（ｓｈｒｉｎｋ ｗｒａｐｐｅｄ）”されていて、インデックス内での点の識別は効果的なプロセスとなっている。
【００１２】
好ましくは、該識別する段階（ａ）は、第一の区域を検索する段階と；該第一の区域の広がりの程度を該所定の領域の広がりの程度と比較して、該第一の区域が該所定の領域と重なるかどうかを確定するようにする段階と；もし重なりが存在するときは、継続して第二の区域を検索し、第二の区域の各々は該第一の区域により包含されるものであるとする。これらの比較と検索の段階は、該第二の区域が該所定の領域により完全に包含されているような重なりとなるまで、各第二の区域について繰返すことができる。
【００１３】
便利なのは、該複数の点が、それぞれ第一と第二の区域の間の関係に従って、点のリストとして前もって記憶されていて、しかも該リンクデータは該点のリスト内の対応している取囲まれた点の第一のものの位置を示している値を含むことである。該アクセスする段階（ｂ）は、該識別した領域の各々について；取囲まれた点の数を表わしている識別子を検索し、また該識別した区域に関係する位置の値を検索する段階と；該点のリストをアクセスして該位置の値により与えられる該リスト内の位置から取囲まれた点の数を検索する段階とを備えている。
【００１４】
好ましくは、リンクデータ内に包まれた値が該記憶領域に書込まれたレジスタの数と対応していることである。
【００１５】
この方法の段階は好ましくは１又はそれ以上の計算機プログラム内で実施され、このプログラムは全部があるいは一部が通信網上での伝送のために搬送波で信号として実施されているか、あるいは計算機が読取り可能な媒体の中で計算機プログラム製品として実施されているか、あるいはその両方として実施できるものである。
【００１６】
便利なのは、点が二次元で表現できるデータと対応していることで、例えば位置（緯度と経度）データまたはレンジデータであることである。レンジデータは、営業時間（例えば始業及び終業時刻）、価格のマージン（例えば最高及び最低価格）、及び／又は医用データ（例えば、最高と最低血圧）を含んでいる。したがって、所定の領域は価格のレンジとすることができ、最高の家の価格と最低の家の価格といったものとすることができる。上で記述した検索方法によると、所定の領域の広がりは（すなわち、価格レンジ）はインデックスから検索された領域と比較される。特定の価格レンジの内に完全に入るある区域が識別されるまでこの価格のレンジと重なっているすべての領域はそこで継続して検索され、この識別された区域内に入るすべての点は、こうして特定された最大と最小の価格レンジ内に入るある価格をしている商品を表わす。
【００１７】
【実施の形態】
この発明のさらなる様相、特徴、利点は添付の図面を参照して以下の好ましい実施形態の記述から明らかになる。
【００１８】
概要
図１に示したようなデータベースサーバＤＢ１，ＤＢ２は一般にユーザによる検索のための情報を記憶する。物理的なレベルでは、データベースサーバＤＢ１，ＤＢ２が置かれている通信環境は少くとも一つのユーザインターフェースを含み、これが普通は計算機端末又はワークステーションＴ３により用意される。
【００１９】
この発明の実施形態は、ワークステーションＴ３上で実施することができ、ワークステーションＴ３はデータベースサーバＤＢ１，ＤＢ２に接続されている。データベースサーバＤＢ１，ＤＢ２は端末Ｔ３と同じＬＡＮ  Ｎ１上に示されてはいるが、データベースサーバＤＢ１，ＤＢ２は異なる網に接続されるようにできて、異なる網が今度は１又はそれ以上のスイッチ及び／又はルータ（図示せず）を経由してＬＡＮ  Ｎ１に接続されるようになると理解される。実施形態は入力として、例えばファイルとしてデータを受領して、データに対するインデックスを構築するが、その詳細は後述するところである。構築されたインデックスはそこでデータベースＤＢ１，ＤＢ２の一つの中にセーブ（保管）され、またインデックスを付けたデータもセーブされ、その順序は構築されたインデックスの構造により与えられ、データベースＤＢ１，ＤＢ２の一つにセーブされる。構築されたインデックスは、そのデータが記憶されていたデータベースと同じか異なるデータベース上にセーブすることができる。
【００２０】
この発明の実施形態は、二次元で定義されているエンティテイにインデックス付けをすることに関係している。実施形態によりインデックス付けができるエンティテイの明白な例にはオブジェクト（ｏｂｊｅｃｔｓ）の場所、例えば給油所、現金出納機等のあるところであって、オブジェクトの位置は通常は緯度と経度とによって定義されているところである。数多くの他のエンティテイが二次元によって提示できる。例えば、モーターバイクの加速度は時間と速度との関数であり、ある材料の伝導率は材料の性質と温度との関数であり、オブジェクトの変形は材料の性質とオブジェクトに加えられる力との関数である等という具合である。さらに、変換をｎ次元パラメータに適用してこのパラメータを二次元パラメータにすることができて、二次元パラメータを二次元空間で表示することができる。
【００２１】
この発明の実施形態を用いてインデックス付けができるエンティテイのさらなる例はレンジ情報を含んでいて、例えば時間的な情報、価格情報及び医用状態情報などを含んでいる。
【００２２】
時間的なレンジ（ｒａｎｇｅ）情報の例は営業（ｂｕｓｉｎｅｓｓ）とかレジャー施設の開始と終了の時間であり、こういった時間は二次元で表現できる。例えば終了と開始の時刻とがそれぞれ縦軸と横軸とで表現できる。同じように、一番速い時刻と一番遅いデリバリー時刻とが二次元で表現できる。
【００２３】
価格情報の例は商品の価格を含み、したがって、例えば商品の最高価格と最低価格とが二次元の一方上でそれぞれ表現できて、この発明の実施形態を用いてインデックス付けができる。価格情報はまた取引情報を含んでいて、株式、債券などの売買に使用されるところとなる。
【００２４】
医用状態情報の例は、体温と血圧といった測定可能な状態に関する統計を含んでいるし、癌の部位といった数値表示に変換可能な状態を含んでいる。
【００２５】
以下の記述では、エンティテイは一般に“点（ｐｏｉｎｔｓ）”と呼ばれ、エンティテイのコンテクスト（例えば給油所、現金出納機など）を実施形態の機構から分離するのにあてている。
【００２６】
全体を概観するとして、点にインデックスを付ける方法の実施例は、図２を参照して記述される。図２は領域Ｒ１を示し、この領域の内部では、複数の点２００が置かれている。各点はｘ，ｙ座標空間で定義される。本質的に、領域Ｒ１がインデックスを付けられることになる点を含んでいて、領域Ｒ１が調べられて、点を含んでいる領域Ｒ３，Ｒ４と、点を含んでいない領域Ｒ２に分割される（領域はどんな形に分けることもでき、矩形、三角形、条（ｓｔｒｉｐｓ）のようになってよいが、図２はこの発明の発明思想を記述する目的で条に分けられた領域を示している）。この実施形態は、次に領域Ｒ３とＲ４との中の点の分布を調べ、領域Ｒ１について考慮されたよりも小さな規模（ｓｃａｌｅ）についての識別し、Ｒ３とＲ４との領域には点が含まれている。図３を参照すると、Ｒ４は本質的にＲ１１となり、Ｒ１１内部での点の分布が調べられる。このやり方で点の分布に集中してみると、いずれの点も含んでいない領域である、図２の領域Ｒ２と、図３の領域Ｒ１２とは黙示的に無視されている。プロセスは継続して繰返されて、小さくなって行くサイズの一連の領域を介して実効的に“掘り下げ（ｂｕｒｒｏｗｉｎｇ ｄｏｗｎ）”が進み、領域のサイズが単一の点のサイズを破壊してしまうところまで行く。実施形態の“掘り下げ”として、各領域がその上の領域とリンクされていて、それにより各点は一連の領域によってリンクされている。こういった点に対するインデックスは、一連の領域を含んでいて、こういった領域と点とはインデックスを創るために使用される（後により詳述する）が、このインデックスがデータベースＤＢ１内にセーブされる。点と領域との間の関係はインデックス内の領域の識別子によって識別されることになる。
【００２７】
上述したように、インデックスを創る利点の一つは問合せ探索ドメインが領域に限られていて、この領域は点を含むことが既知であることである。すなわち、問合せはデータベースＤＢ１内にセーブされた領域上でのみ実行されることになり、またこういった領域は定義により点を含んでいるので、探索ドメインは相対的にコンパクトなものとなっている。もう一度図２の参照に戻ると、ある問合せに関して点を識別するプロセスは上述の実施形態によると、領域Ｒ１全体に係る情報を備えたインデックスの場合よりも高速となる。
【００２８】
実施形態の特定形式が図４〜１２を参照して提示されているが、そこでは、点はｘ，ｙ空間内の二次元座標となっている。インデックスを付けることになるエンティテイが加速度値であるとすると、この加速度値は時間と速度との値についての対応している組によって定義されていて、この時間と速度との値はｘ，ｙ座標空間上に直接写像されて、それにより（ｔ１，ｖ１），（ｔ２，ｖ２）…（ｔｎ，ｖｎ）が加速度値に対応している点の座標となる。同様に、もしインデックスを付けることになるエンティテイが位置の値であって緯度と経度との値の対応する組により定義される値であれば、緯度と経度との値がｘ，ｙ座標空間上に直接写像されて、（ｌａｔ＿１，ｌｏｎｇ＿１）…（ｌａｔ＿ｎ，ｌｏｎｇ＿ｎ）が位置の値に対応している点の座標となる。点は記憶されている（例えばあるファイルに書込まれている）と仮定されていて、それによりこの発明の実施例はファイルから点を読出す。代りの実施例ではユーザが点を入力できるものとし、その条件として点についてのインデックスが構築されそうになっているときとしている。
【００２９】
さらに、以下に示す実施例では、領域は正方形であって、以下の記述では“クアッド（ｑｕａｄｓ）”とが“サブクアッド（ｓｕｂ−ｑｕａｄｓ）”と呼ぶこととし、各クアッド（ｑｕａｄ）は継続して四つのサブクアッド（ｓｕｂ−ｑｕａｄ）に分割されている。各サブクアッドは点の存在について調べられる。点のないものは無視されて、このことは図２と図３とを参照して記載された領域Ｒ２を無視することと同じプロセスであり、各新しいサブクアッドで点を含んでいるものがそのサブクアッド内の点を含んでいる一番小さな領域の周囲に“シュランク・ラップト（ｓｈｒｕｎｋｗｒａｐｐｅｄ）”される。この実施例は正方形に従って領域を解析するが、数多くの他の形状も点の周りで“シュリンク・ラップ（ｓｈｒｉｎｋ−ｗｒａｐ）”するのに使用できる。各サブクアッドは次に再び四つのサブクアッドに分けられて、空のサブクアッドが再び無視されて、各残っているサブクアッドが点を含んでいる一番小さな領域の周りで“シュリンク・ラップ”される。結果的に、各残っているサブクアッドは単一の点に“シュリンク・ラップ”されて、その座標が関与している点の座標となる。一旦クアッドとすべてのサブクアッドであって、無視されずに介在しているサブクアッドと単一の点と一致しているサブクアッドの両方を含んでいるものが識別されると、その点に対するインデックスでそれぞれのものと関連のあるクアッドとサブクアッドを備えているものが作られる。これが図６〜図１１を参照して後に詳しく論じられる。
【００３０】
以下では、段階Ｓ４．１ないしＳ．４．９が図４と図５との流れ図で連続して示されており、また図６ないし図１２で示すように同じ参照番号で動作により示されている。
【００３１】
図６
・段階Ｓ４．１  インデックスを付けることになるすべての点のｘ，ｙ座標を読み込む。（上述したように、これらの点は記憶場所であるファイルなどから読出されてよいし、あるいはユーザから直接であってもよい）；
・段階Ｓ４．２  すべての点について境界を形成している（ｂｏｕｎｄｉｎｇ）箱を製図し、識別し、その周りを“シュリンクラッピング（ｓｈｒｉｎｋ ｗｒａｐｐｉｎｇ）”する。ｘ次元，ｙ次元の両方における一番外側の点の座標間の差、それぞれｄｘとｄｙによって境界を形成している箱が与えられる。この箱は一番外側のクアッド５０１である；・段階Ｓ４．３及びＳ４．４  クアッド５０１の広がりの程度（ｅｘｔｅｎｔ）をセーブする。すなわちｄｘ，ｄｙをセーブし、その中の点の座標をセーブする；
・段階Ｓ４．５  一番外側のクアッド５０１は正の寸法を有しているか（すなわち、クアッド５０１のｄｘとｄｙとはゼロに等しいか？）どうかをチェックする。図６に示した例では、一番外側のクアッド５０１が存在し、その理由はこのクアッドがその中に複数の点を有していて、ｄｘ，ｄｙはゼロでなく、したがってクアッド５０１が正の寸法（ｓｉｚｅ）をもつことによる；
・段階Ｓ４．６  一番外側のクアッド５０１を四つのサブクアッド５０３ａ，５０３ｂ，５０３ｃ，５０３ｄに分割する；
・段階Ｓ４．６．１  それぞれのサブクアッドで各点をタグ付けして、各サブクアッド内の点の数を記録する；
・段階Ｓ４．７  サブクアッド０（５０３ａ）から始まって、サブクアッド５０３ａ内にいずれかの点が存在するかどうかチェックする。
点があるときには、このサブクアッド０（５０３ａ）内部の点を段階Ｓ４．１に対して入れて、段階Ｓ４．１を介してサブクアッド０（５０３ａ）について進行させることとし、図７を参照して後述するように、実行する。
【００３２】
図７
・段階Ｓ４．１  サブクアッド５０３ａに対応している点のｘ，ｙ座標を読み込む；
・段階Ｓ４．２  ５０３ａ内のすべての点について境界を形成している箱を製図し、“シュリンクラップ”したサブクアッド０（６０１）を創る。これが上述した原理を示していて、実施例はサブクアッド０内部の領域で点のないところを識別し、この領域はそこで無視される；
・段階Ｓ４．３及び段階Ｓ４．４  サブクアッド０（６０１）の広がりの程度すなわち、ｄｘ，ｄｙと、その中の点の座標とをセーブする；
・段階Ｓ４．５  サブクアッド６０１が正の寸法をもつかどうか（すなわち、クアッド６０１のｄｘ，ｄｙがゼロに等しいかどうか？）をチェックする。図７で見るように、クアッド６０１はその中に複数の点を有していて、クアッド６０１についてはｄｘ，ｄｙはゼロではなく、したがってサブクアッド６０１は正の寸法（サイズ）を有している；
・段階Ｓ４．６  サブクアッド０（６０１）を四つのサブクアッド、すなわち０，０（６０３ａ），０，１（６０３ｂ），０，２（６０３ｃ），０，３（６０３ｄ）に分割する；・段階Ｓ４．６．１  各点に関連するサブクアッドでタグ付けをして、各サブクアッド内の点の数を記録する；
・段階Ｓ４．７  サブクアッド０，０（６０３ａ）から始まって、サブクアッド０，０（６０３ａ）内にいずれかの点が存在するかどうかチェックする：点があるときには、このサブクアッド０，０（６０３ａ）内部の点を段階Ｓ４．１に入れて、段階Ｓ４．１を介してサブクアッド０，０（６０３ａ）について進行させることとし、このことは図８を参照して後述する。
【００３３】
図８
・段階Ｓ４．１  サブクアッド６０３ａに対応している点のｘ，ｙ座標を読み込む；
・段階Ｓ４．２  サブクアッド０，０（６０３ａ）内のすべての点について境界を形成している（取囲んでいる）箱を製図し、“シュリンクラップ”したサブクアッド０，０（７０１）を創る。サブクアッド０について、サブクアッド６０３ａ内部で点がない領域は無視される；
・段階Ｓ４．３及び段階Ｓ４．４  サブクアッド０，０（７０１）の広がりの程度すなわち、ｄｘ，ｄｙをセーブして、その中の点の座標をセーブする；
・段階Ｓ４．５  サブクアッド７０１が正の寸法を持っているかどうか？をチェックする（すなわち、クアッド７０１のｄｘ，ｄｙがゼロに等しくないか？をチェックする）。図８から分るように、クアッド７０１はその中に複数の点を有していて、クアッド７０１についてｄｘ，ｄｙはゼロではなく、このサブクアッド７０１は正の寸法をもつ。
・段階Ｓ４．６  サブクアッド０，０（７０１）を四つのサブクアッド：０，０，０（７０３ａ）、０，０，１（７０３ｂ）、０，０，２（７０３ｃ）、０，０，３（７０３ｄ）に分割する。
・段階Ｓ４．６．１  各点に関連のサブクアッドでタグ付けをして、各サブクアッド内の点の数を記録する；
・段階Ｓ４．７  サブクアッド０，０，０（７０３ａ）で開始して、サブクアッド０，０，０（７０３ａ）内にいずれかの点が存在するかどうかチェックする：サブクアッド０，０，０（７０３ａ）内に一つの点が存在すれば、このサブクアッド０，０，０内部の点を段階Ｓ４．１に入れて、段階Ｓ４．１を介してサブクアッド０，０，０（７０３ａ）について進行することとし、それについては図８を参照してさらに以下で記述する。
【００３４】
図８についても
・段階Ｓ４．１  サブクアッド７０３ａに対応している点をｘ，ｙ座標で読み込む；
・段階Ｓ４．２  サブクアッド０，０，０（７０３ａ）内のすべての点について取囲んでいる箱を製図して、“シュリンクラップ”したサブクアッド０，０，０を作る：ここでは単一の点の周りに作ることになる。
・段階Ｓ４．３及び段階Ｓ４．４  “シュリンクラップ”したサブクアッド０，０，０の広がりの程度をセーブし、ここでは単一点となるまでにしてあるのでｄｘとｄｙとはゼロに等しく、この点の座標をセーブする；
・段階Ｓ４．５  この点をもつサブクアッドが正の寸法を有するかどうかをチェックする。（すなわちこの点のｄｘとｄｙがゼロに等しいかどうかをチェックする。）事実ｄｘとｄｙとは共にゼロであり、その理由はサブクアッド７０３ａが単一の点にまで分解されていることによる。そこで段階Ｓ４．８へ進む；
・段階Ｓ４．８  サブクアッドカウンタｉをこのレベル（０，０，ｉ）でインクレメントし、サブクアッド０，０，１（７０３ｂ）内部の点を段階Ｓ４．１に入れて（段階Ｓ４．７）、段階Ｓ４．１を介してサブクアッド０，０，１（７０３ｂ）について進行する。これについては図９を参照して以下に記述する。
【００３５】
図９
・段階Ｓ４．１  サブクアッド７０３ｂに対応している点のｘ，ｙ座標を読み込む；
・段階Ｓ４．２  サブクアッド０，０，１（７０３ｂ）内のすべての点について取囲んでいる箱を製図して、“シュリンクラップ”したサブクアッド０，０，１（８０１）を創る。サブクアッド０についてと同様に、サブクアッド７０３ｂ内部で点のない領域は無視される；
・段階Ｓ４．３及び段階Ｓ４．４  サブクアッド８０１についての広がりの程度すなわち、ｄｘ，ｄｙをセーブし、またその中の点の座標をセーブする；
・段階Ｓ４．５  サブクアッド８０１が正の寸法かどうか（すなわち、クアッド７０３ａのｄｘ，ｄｙがゼロに等しいかどうか）をチェックする。サブクアッド８０１がその中に複数の点をもっていれば、クアッド８０１についてのｄｘ，ｄｙはゼロでなく、したがってサブクアッド８０１は正の寸法を有する；
・段階Ｓ４．６  サブクアッド０，０，１（８０１）を四つのサブクアッド、０，０，１，０（８０３ａ）、０，０，１，１（８０３ｂ）、０，０，１，２（８０３ｃ）、０，０，１，３（８０３ｄ）に分割する。
・段階Ｓ４．６．１  関連するサブクアッドで各点をタグ付けし、各サブクアッド内の点の数を記録する；
・段階Ｓ４．７  サブクアッド０，０，１，０（８０３ａ）で開始して、サブクアッド０，０，１，０（８０３ａ）内にいずれかの点があるかどうかをチェックする：サブクアッド０，０，１，０（８０３ａ）には点は存在しない；
・段階Ｓ４．８  サブクアッドカウンタｉをこのレベル（０，０，１，ｉ）でインクレメントして、サブクアッド０，０，１，１（８０３ｂ）内部の点を段階Ｓ４．１に加えて（段階Ｓ４．７）、段階Ｓ４．１を介して、サブクアッド０，０，１，１（８０３ｂ）について進行していく。このことについては図１０を参照して以下で記述する。
【００３６】
図１０
・段階Ｓ４．１  サブクアッド８０３ｂに対応している点のｘ，ｙ座標を読み込む；
・段階Ｓ４．２  サブクアッド０，０，１，１（８０３ｂ）内のすべての点について取囲んだ箱を製図し、“シュリンクラップ”したサブクアッド０，０，１，１を作り、これが単一の点となる；
・段階Ｓ４．３及び段階Ｓ４．４  この単一の点の広がりの程度（ｅｘｔｅｎｔ）、すなわちｄｘ，ｄｙをセーブし、この点の座標をセーブする；
・段階Ｓ４．５  この点が正の寸法をもっているかどうか、すなわちこの点のｄｘ，ｄｙがゼロに等しいかどうかをチェックする。事実は、サブクアッド８０３ｂが単一の点に分解されているので、ｄｘもｄｙも共にゼロであり、段階Ｓ４．８に進む；
・段階Ｓ４．８  このレベル（０，０，１，ｉ）でサブクアッドカウンタｉをインクレメントし、サブクアッド０，０，１，２（８０３ｂ）内部の点を段階Ｓ４．１に入れて、段階Ｓ４．１を介してサブクアッド０，０，１，２（８０３ｂ）に進行する。このことはさらに図１０を参照して記述して行く。
【００３７】
また図１０について
・段階Ｓ４．１  サブクアッド８０３ｃに対応している点のｘ，ｙ座標を読み込む；
・段階Ｓ４．２  サブクアッド０，０，１，２（８０３ｃ）内のすべての点について取囲んでいる箱を製図して、“シュリンクラップ”したサブクアッド０，０，１，２（これは単一の点である）を作る；
・段階Ｓ４．３及び段階Ｓ４．４  この単一の点についての広がりの程度すなわちｄｘ，ｄｙをセーブし、またこの点の座標をセーブする；
・段階Ｓ４．５  この点が正の寸法であるかどうか、すなわちこの点のｄｘ，ｄｙがゼロに等しいかどうかをチェックする。事実は、サブクアッド８０３ｃが単一の点に分解しているのでｄｘとｄｙとは共にゼロである。そこで段階Ｓ４．８へ進む；
・段階Ｓ４．８  このレベル（０，０，１，ｉ）でサブクアッドカウンタｉをインクレメントする。サブクアッド０，０，１，３（８０３ｄ）内部には点は存在しないので（段階Ｓ４．７）、そこで段階Ｓ４．８に戻り：サブクアッドカウンタｉをこのレベル（０，０，１，ｉ）でインクレメントする：しかしｉ＞３であるから、
・段階Ｓ４．９  サブクアッドレベル０，０，ｉに戻って、サブクアッドカウンタを１から２へインクレメントして、ここでサブクアッド０，０，２（７０３ｃ）を考える：サブクアッド０，０，２（７０３ｃ）には一つ点があり、したがってサブクアッド０，０，２（７０３ｃ）内部にこの点を入れ（段階Ｓ４．７）て、段階Ｓ４．１へ向い、段階Ｓ４．１を介してサブクアッド０，０，２（７０３ｃ）について進行する。このことは図１１を参照して説明するところである。
【００３８】
図１１
・段階Ｓ４．１  サブクアッド７０３ｃに対応している点のｘ，ｙ座標を読み込む；
・段階Ｓ４．２  サブクアッド０，０，２（７０３ｃ）内のすべての点について取囲んでいる箱を製図して、“シュリンクラップ”したサブクアッド０，０，２（これは単一の点である）を創る。
・段階Ｓ４．３及び段階Ｓ４．４  この単一の点の広がりの程度すなわちｄｘ，ｄｙをセーブし、この点の座標をセーブする；
・段階Ｓ４．５  この点が正の寸法をもっているかどうか、すなわちこの点のｄｘ，ｄｙがゼロに等しいかどうかをチェックする。事実は、サブクアッド７０３ｃは単一の点にまで分解されているのでｄｘとｄｙとは共にゼロである。したがって段階Ｓ４．８となる；・段階Ｓ４．８  このレベル（０，０，ｉ）でサブクアッドカウンタｉをインクレメントする。サブクアッド０，０，３（７０３ｄ）内部には点は存在しない（段階Ｓ４．７）ので段階Ｓ４．８へ戻る：このレベル（０，０，ｉ）でサブクアッドカウンタｉをインクレメントする：しかしｉ＞３であるからそこで
・段階Ｓ４．９  サブクアッドレベル０，ｉに戻り、サブクアッドカウンタｉを０から１へインクレメントして、これによりサブクアッド０，１（６０３ｂ）を考慮する。このことが図１２を参照して記述される。
【００３９】
図１２
図７〜１１で記述したプロセスが繰返されるが、サブクアッド０，１については、サブクアッド０，ｎ内部のすべての点が一度サブクアッドに指定されてしまうと、このプロセスはサブクアッド１に向けて移動することになる。
【００４０】
始めに記述したように、こういった点に向けてのインデックスを構築することは、サブクアッド情報をセーブすることという事項である。このことについてはたくさんのやり方が工夫考案されているが、好ましいのは、インデックスが段階Ｓ４．３とＳ４．４とでセーブされたサブクアッド情報を備えていることであり、言い換えると、ｘ，ｙ座標でのサブクアッドの広がりの程度（ｅｘｔｅｎｔ）と、その中に落ち込むことになる点の座標であり、またそのサブクアッド内部の四つのサブクォードラント（ｓｕｂ−ｑｕａｄｒａｎｔｓ）へのリンクであることとされる。したがって、このインデックスは本質的にはサブクアッド構造の階層構造を備え、この構造は階層構造が各継続するサブクアッドとその四つのサブクアッドとの間の関係によって与えられるものとなっている。サブクアッドはサブクアッド階層構造に従ってインデックスに書込まれ、このサブクアッド階層構造は最大のサブクアッド（ここでは図６の５０１）から一番小さいサブクアッドに下っていくものである。
【００４１】
データベースＤＢ１内にサブクアッド構造をセーブすることに加えて、点がこのデータベースに書込まれる。このデータベースは同じものでも異なるものでもよく、例えばファイル内にサブクアッド階層構造の反転したもので与えられる順序で書込まれる。したがって、この場合には、階層構造の底のサブクアッド内の点が先ずファイル内に書込まれる。点がファイルに書込まれるにつれて、点の全数についての移動書付け記録（ｒｕｎｎｉｎｇ ｔａｌｌｙ）（点の数のレジスタ）が維持されて、ファイルに各点が書かれると、カウンタが次のように提示する：“ｃｕｒｒｅｎｔ ｎｕｍｂｅｒ ｏｆ ｐｏｉｎｔｓ ｅｎｃｏｕｎｔｅｒｅｄ ｓｏ ｆａｒ＋１”（これまでに出逢った点の現在数プラス１）であり、これがそれぞれのサブクアッド構造に書込まれる。移動書付け記録は一番小さなサブクアッドから上方へ作業をして行き、各サブクアッドについては、そのサブクアッド内のすべての点の第一のものの位置をインデックスを付けられているすべての点によって（Ｐｏｓｓｕｂ＿ｑｕａｄ）本質的に表示する。例えば、図１３を参照すると、次のようになる。
【００４２】
【表１】
2004516553.tif 000003
【００４３】
こうして、サブクアッド５０１（一番外側のクアッド、図６を参照）についての点のファイルはｎ，ｍ，ｐ，ｏ…を読む（これが一番小さいサブクアッド０，０，１，１から始まっている）。点の数（Ｎ）と、点のサブクアッド内の第一の点に対応している移動書付け記録（Ｐｏｓｓｕｂ＿ｑｕａｄ）の数の両方がそのサブクアッドに対して書かれるので、次に、関心のあるサブクアッドが一旦識別されると、識別されたサブクアッド内部に存在する点が点ファイル内でＰｏｓｓｕｂ＿ｑｕａｄへ移動してその位置からＮ個の点を抽出することによって抽出ができる。このことが点の検索を示している実施例の中で示されている。
【００４４】
情報の検索（Ｒｅｔｒｉｅｖａｌ）
第二の発明は、各要素と他の要素でそのインデックス内のものとの間の関係と、インデックス内の要素とインデックスを付けられているエンティテイとの間の関係とが既知のときに、エンティテイと関係している要素のインデックスによってエンティテイを検索する方法に関するものである。この方法は上で提示したインデックス付けの方法に従って創り出されたインデックスに対して直ちに適用ができるのであり、その理由は、このインデックスがサブクアッド構造の階層構造を備えていて、またこの階層構造が（クアッド＞サブクアッド関係により）よく定義されていることによる。しかしながら、この方法は、こういった条件を満足するいずれの形式のインデックスに対して等しく適用できることに留意されたい。
【００４５】
以下の記述では、検索プロセスの実施例が記述され、そこでは点に対するインデックスが問合せが“関心のある区域（ｒｅｇｉｏｎ ｏｆ ｉｎｔｅｒｅｓｔ）”を特定する問合せで照合される。次のことが仮定される：
・インデックス内の要素は所定領域内部の複数の領域である；
・インデックスを付けられるエンティテイは、二次元によって定義される点である；
・領域間には所定の関係が存在する；また
・領域と点との間には所定の関係が存在する。
本質的なことは、実施例が領域のどれが次のものであるかを識別するというのである：
ａ）関心のある区域と重なる、また
ｂ）関心のある区域と重なるこういった領域内部に点を含んでいる。
領域と点との間の所定の関係がそこで使用されて識別された領域内部に落ち込む点を抽出する。
【００４６】
関心のある領域はエンティテイの二次元提示内部の区域を指している。したがって、上述の時間的なレンジ（ｒａｎｇｅ）（すなわち、営業やレジャー施設の閉じたり開いたりする時間）については、関心のある区域は関心のある時間期間であって、“店は１０時と１３時の間開いている”といったものである。関心のある区域はそこである区域（好ましいのは正方形）によって定義されることで、この区域は前もって特定された点の内部に取囲まれている。図３５ａ〜ｅを参照すると、関心のある領域は次のいずれか一つとなることができる：
（０，１０），（１３，２４）≡１０時と１３時との間のある時間開いている機関（図３５ａ）
（０，１３），（１０，２４）≡１０時と１３時との間連続して開いている機関（図３５ｂ）
（０，１０），（１０，１３）≡１０時前に開くが１３時前に閉じる機関（図３３ｃ）
（１０，１３），（１３，２４）≡１０時後に開くが１３時後に閉じる機関（図３３ｄ）（１０，１０），（１３，１３）≡１０時後に開きしかも１３時前に閉じる機関（図３３ｅ）
同じように、上述した値段付け範囲については、関心のある区域は価格のレンジ（範囲）であり、それ故に、「範囲が英ポンド５０．００ないし８０．００の範囲のどこかに入ることになるすべてのアイテム」についての検索要件については、関心のある区域は点（０，５０）と（８０，８０）との内部に限定されてた区域によって定義できる。
【００４７】
上述した位置情報については、関心のある区域は場所の範囲であり、例えば「第一の場所（（ｌａｔ，ｌｏｎｇ）１ ）と第二の場所（（ｌａｔ，ｌｏｎｇ）２ ）の間に置かれた全アイテム」のようなものである。
【００４８】
関心のある区域と重なる領域を識別する方法の段階を示している流れ図は、関心のある区域が位置情報と関係しているときに、図１４と図１５とに示されている。これらの段階は、図１６に示した関心のある区域については、図１６ないし図３３で示されている。この実施例では、所定区域内部の領域の特定例がクアッドとサブクアッドとして呼ばれている。図１４，図１５に示した方法の段階は以下に図１６ないし図３３の各々を参照して記述されている。
【００４９】
図１６
・Ｓ１３．１．１  関心のある区域（ｘ１，ｙ１）（ｘ２，ｙ２）のｘ，ｙ座標を読み込む。例をあげると、もしユーザがある領域内のガレージ（ｇａｒａｇｅｓ）を位置決めしたいとすると、これが緯度／経度の対としてインデックス付けされて、二次元の空間内の点を定義するものとなり、またユーザが関心をもっている地理的領域が、その二次元の空間内で「関心のある区域」として表現されることができる。
・Ｓ１３．１．２  点の座標と一番外側のクアッドについてのクアッドの寸法とを検索し、一番外側のクアッドの寸法に対して（Ｘ１＿Ｑ，Ｙ１＿Ｑ），（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を設定する；
・Ｓ１３．２  関心のある区域が切取り（ｃｒｏｐｐｉｎｇ）を必要とするかどうか評価する：もしｘ１＜Ｘ１＿Ｑであればｘ１＝Ｘ１＿Ｑと設定し；もしｙ１＜Ｙ１＿Ｑであればｙ１＝Ｙ１＿Ｑと設定し；もしｘ２＞Ｘ２＿Ｑであればｘ２＝Ｘ２＿Ｑと設定し；もしｙ２＞Ｙ２＿Ｑであればｙ２＝Ｙ２＿Ｑと設定する。例としての関心のある区域で図１６に示したものは、これらの条件のいずれも満足していないと；
・Ｓ１３．３  ｘ１＞ｘ２もしくはｙ１＞ｙ２かどうかを評価する。この場合、いずれの条件も満足されていないと；
段階Ｓ１３．２とＳ１３．３とは条件の唯一の例であり、この条件は関心のある区域とＳ１３．１．２で検索されたサブクアッドが重なるかどうか、また、もし重なりが存在すれば重なっている区域内にいずれかの点が存在するかどうかを確定するために適用できるものである；この確定に適用するために代りの方法が適用できるものと考えている。
・Ｓ１３．４  関心のある区域がそのクアッドと正確に重なっているかどうか評価する。否（ＮＯ）であれば：
・Ｓ１３．５  図１７を参照して記述するように、Ｓ１３．１．２に従って現在のクアッド（５０１）のサブクアッド（５０３ａ）を検索する。
【００５０】
図１７
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０（６０１）から点の座標とサブクアッドの寸法とを検索する：  “シュリンクラップ”したサブクアッド６０１の寸法に、（Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を設定する；
・Ｓ１３．２  関心のある区域が切取り（ｃｒｏｐｐｉｎｇ）を必要としているかどうか評価する：もしｘ１＜Ｘ１＿Ｑであればｘ１＝Ｘ１＿Ｑと設定し；もしｙ１＜Ｙ１＿Ｑであればｙ１＝Ｙ１＿Ｑと設定し；もしｘ２＞Ｘ２＿Ｑであればｘ２＝Ｘ２＿Ｑと設定し；もしｙ２＞Ｙ２＿Ｑであればｙ２＝Ｙ２＿Ｑと設定する。この場合こういった条件がいずれも満足されていないと；
・Ｓ１３．３  ｘ１＞ｘ２またはｙ１＞ｙ２かどうか評価する。この場合にいずれの条件も満足されていないと；
・Ｓ１３．４  関心のある区域がそのクアッドと正確に重なっているかどうか評価する。否であれば：
・Ｓ１３．５  図１８と１９を参照して記述するように、Ｓ１３．１．２に従って現在のサブクアッドのサブクアッドを検索する。
【００５１】
図１８及び図１９
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，０（７０１）から点の座標とサブクアッドの寸法とを検索する：（Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を“シュリンクラップ”したサブクアッド７０１の寸法に設定する；
・Ｓ１３．２  関心のある区域が切取り（ｃｒｏｐｐｉｎｇ）を必要としているかどうか評価する：ｘ２＞Ｘ２＿Ｑであればｘ２＝Ｘ２＿Ｑと設定し；またｙ２＞Ｙ２＿Ｑであればｙ２＝Ｙ２＿Ｑと設定する；
・Ｓ１３．３  ｘ１＞ｘ２あるいはｙ１＞ｙ２かどうかを評価する。この場合（図１９）両条件が満足されているならば、これが関心のある区域内部に落込むサブクアッド０，０（７０１）内の点が存在しないことを意味する；
・Ｓ１３．６  このレベル（０，ｉ）でサブクアッドカウンタｉをインクレメントし、図２０と２１を参照して記述するようにＳ１３．１．２に従ってサブクアッド（０，１）を検索する。
【００５２】
図２０及び図２１
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，１から、点の座標とサブクアッドの寸法とを検索する：  （Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を“シュリンクラップ”したサブクアッド０，１の寸法に対して設定する；
・Ｓ１３．２  関心のある区域が切取り（ｃｒｏｐｐｉｎｇ）を必要としているかどうか評価する：ｘ１＜Ｘ１＿Ｑであればｘ１＝Ｘ１＿Ｑと設定し、またｙ２＞Ｙ２＿Ｑであればｙ２＝Ｙ２＿Ｑと設定する；
・Ｓ１３．３  ｘ１＞ｘ２もしくはｙ１＞ｙ２であるかどうか評価する。いずれの条件も満足されていない場合には；
・Ｓ１３．４  関心のある区域（今では切取りがされている）がサブクアッドと正確に重なっているかどうか評価する。否であれば：
・Ｓ１３．５  図２２（ａ）と図２２（ｂ）とを参照して記述するように、Ｓ１３．１．２に従って現在のサブクアッド０，１のサブクアッド０，１，０を検索する。
【００５３】
図２２（ａ）及び図２２（ｂ）
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，１，０から、点の座標とサブクアッドの寸法を検索する：  （Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を“シュリンクラップ”したサブクアッド０，１，０の寸法に設定する；
・Ｓ１３．２  関心のある区域が切取り（ｃｒｏｐｐｉｎｇ）を必要とするかどうか評価する：ｘ２＞Ｘ２＿Ｑであればｘ２＝Ｘ２＿Ｑと設定し、またｙ２＞Ｙ２＿Ｑであればｙ２＝Ｙ２＿Ｑと設定する；
・Ｓ１３．３  ｘ１＞ｘ２あるいはｙ１＞ｙ２かどうか評価する。この場合（図２２ｂ）両条件が満足されたならば、すなわち関心のある区域内に入るサブクアッド０，１，０内に点が存在していないことを意味する；
・Ｓ１３．６  このレベル（０，１，ｉ）でサブクアッドカウンタｉをインクレメントし、図２３（ａ），２３図（ｂ）を参照して記述するように、Ｓ１３．１．２に従ってサブクアッド（０，１，１）を検索する（Ｓ１３．６．１）。
【００５４】
図２３（ａ）及び２３図（ｂ）
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，１，１から点の座標とサブクアッドの寸法とを検索する：“シュリンクラップ”したサブクアッド０，１，１（すなわち単一の点）の寸法に（Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を設定する。・Ｓ１３．２  関心のある区域が切取り（ｃｒｏｐｐｉｎｇ）を必要としているかどうか評価する：ｘ１＜Ｘ１＿Ｑであればｘ１＝Ｘ１＿Ｑと設定し、ｙ２＞Ｙ２＿Ｑであればｙ２＝Ｙ２＿Ｑと設定する；
・Ｓ１３．３  ｘ１＞ｘ２あるいはｙ１＞ｙ２であるかどうか評価する。この場合（図２３（ｂ））に両方の条件が満足されれば、関心のある区域内に入るサブクアッド０，１，１内に点が存在しないことを意味する；
・Ｓ１３．６  このレベル（０，１，ｉ）でサブクアッドカウンタｉをインクレメントし、Ｓ１３．１．２に従ってサブクアッド（０，１，２）を検索する（Ｓ１３．６．１）。このことは図２４（ａ）と２４（ｂ）とを参照して記述するところである。
【００５５】
図２４（ａ）及び図２４（ｂ）
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，１，２から点の座標とサブクアッドの寸法とを検索する：（Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を“シュリンクラップ”したサブクアッド０，１，２すなわち単一の点に設定する；
・Ｓ１３．２  関心のある区域が切取り（ｃｒｏｐｐｉｎｇ）を要求しているかどうか評価する：ｘ１＜Ｘ１＿Ｑであればｘ１＝Ｘ１＿Ｑと設定し、ｙ１＜Ｙ１＿Ｑ，ｘ２＞Ｘ２＿Ｑ及びｙ２＞Ｙ２＿Ｑであればｘ１＝Ｘ１＿Ｑ，ｙ１＝Ｙ１＿Ｑ，ｘ２＝Ｘ２＿Ｑ，ｙ２＝Ｙ２＿Ｑと設定する。
・Ｓ１３．３  ｘ１＞ｘ２もしくはｙ１＞ｙ２であるかどうか評価する。否であれば
・Ｓ１３．４  関心のある区域（今までは切取られている）がサブクアッドと正確に重なるかどうか評価する：肯定（ＹＥＳ）であれば
・Ｓ１３．４．２  サブクアッドとそのサブクアッド内の点の数（ここでは１）とを記録する；
・Ｓ１３．６  このレベル（０，１，ｉ）でサブクアッドカウンタｉをインクレメントし、図２５（ａ）及び２５図（ｂ）を参照して記述するようにＳ１３．１．２に従ってサブクアッド（０，１，３）を検索する（Ｓ１３．６．１）。
【００５６】
図２５（ａ）及び図２５（ｂ）
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，１，３から点の座標とサブクアッドの寸法とを検索する：（Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を“シュリンクラップ”したサブクアッド０，１，３すなわち単一の点に対して設定する；
・Ｓ１３．２  関心のある区域が切取り（クロッピング）を必要としているかどうか評価する：ｘ１＜Ｘ１＿Ｑであればｘ１＝Ｘ１＿Ｑと設定し、ｙ１＜Ｙ１＿Ｑ，ｘ２＞Ｘ２＿Ｑ及びｙ２＞Ｙ２＿Ｑであればｘ１＝Ｘ１＿Ｑ，ｙ１＝Ｙ１＿Ｑ，ｘ２＝Ｘ２＿Ｑ，ｙ２＝Ｙ２＿Ｑと設定する；
・Ｓ１３．３  ｘ１＞ｘ２もしくはｙ１＞ｙ２であるかどうか評価する。否であると
・Ｓ１３．４  関心のある区域（今では切取られている）がサブクアッドと正確に重なるかどうか評価する：肯定（ＹＥＳ）であれば
・Ｓ１３．４．２  サブクアッドとサブクアッド内の点の数（ここでは１）とを記録する；
・Ｓ１３．６  このレベル（０，１，ｉ）…ｉ＞３でサブクアッドカウンタｉをインクレメントし、図２６，２７を参照して記述するようにＳ１３．１．２に従ってサブクアッド（０，２）を検索する（Ｓ１３．６．２）。
【００５７】
図２６及び図２７
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，２から、点の座標とサブクアッドの寸法とを検索する：  （Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を“シュリンクラップ”したサブクアッド０，２の寸法に対して設定する；
・Ｓ１３．２  関心のある区域が切取り（クロッピング）を要求するかどうかを評価する：ｙ１＜Ｙ１＿Ｑであればｙ１＝Ｙ１＿Ｑと設定し、またｘ２＞Ｘ２＿Ｑであればｘ２＝Ｘ２＿Ｑと設定する。
・Ｓ１３．３  ｘ１＞ｘ２もしくはｙ１＞ｙ２であるかどうか評価する。この場合にいずれの条件も満足されていなければ；
・Ｓ１３．４  関心のある区域（今では切取りがされている）がサブクアッドと正確に重なるかどうか評価する。否であると：
・Ｓ１３．５  現在のサブクアッド０，２のサブクアッド０，２，０をＳ１３．１．２に従って、図２８（ａ）と図２８（ｂ）とを参照して記述するように検索引出しする。
【００５８】
図２８（ａ）及び図２８（ｂ）
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，２，０から点の座標とサブクアッドの寸法とを検索する：（Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を“シュリンクラップ”したサブクアッド０，２，０の寸法に対して設定する；
・Ｓ１３．２  関心のある区域が切取り（クロッピング）を必要としているかどうか評価する：ｘ２＞Ｘ２＿Ｑであればｘ２＝Ｘ２＿Ｑと設定し、またｙ２＞Ｙ２＿Ｑであればｙ２＝Ｙ２＿Ｑと設定する；
・Ｓ１３．３  ｘ１＞ｘ２もしくはｙ１＞ｙ２かどうかを評価する。この場合（図２８（ｂ））、両方の条件が満足されると、関心のある区域内部に入るサブクアッド０，２，０内に点が存在しないことを意味する；
・Ｓ１３．６  このレベル（０，２，ｉ）でサブクアッドカウンタｉをインクレメントし、図２９（ａ）と図２９（ｂ）とを参照して記述するように、Ｓ１３．１．２に従ってサブクアッド（０，２，１）を検索する（Ｓ１３．６．１）。
【００５９】
図２９（ａ）及び図２９（ｂ）
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，２，１から点の座標とサブクアッドの寸法とを検索する：（Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を“シュリンクラップ”したサブクアッド０，２，１すなわち単一の点の寸法に設定する；
・Ｓ１３．２  関心のある区域が切取り（クロッピング）を必要としているかどうか評価する：ｘ１＜Ｘ１＿Ｑであればｘ１＝Ｘ１＿Ｑと設定し、ｙ１＜Ｙ１＿Ｑ，ｘ２＝Ｘ２＿Ｑ及びｙ２＞Ｙ２＿Ｑであればｘ１＝Ｘ１＿Ｑ，ｙ１＝Ｙ１＿Ｑ，ｘ２＝Ｘ２＿Ｑ，ｙ２＝Ｙ２＿Ｑと設定する；
・Ｓ１３．３  ｘ１＞ｘ２或いはｙ１＞ｙ２かどうか評価する。否であれば
・Ｓ１３．４  関心のある区域（今では切取られている）がサブクアッドと正確に重なるかどうか評価する：肯定であれば
・Ｓ１３．４．２  サブクアッドとサブクアッド内部の点の数（ここでは１）とを記録する；
・Ｓ１３．６  このレベル（０，１，ｉ）…ｉ＜３でサブクアッドカウンタｉをインクレメントして、図３０（ａ）と図３０（ｂ）とを参照して記述するようにＳ１３．１．２に従ってサブクアッド（０，２，２）を検索する（Ｓ１３．６．１）。
【００６０】
図３０（ａ）及び図３０（ｂ）
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，２，２から点の座標とサブクアッドの寸法とを検索する：（Ｘ１＿Ｑ，Ｙ１＿Ｑ）（Ｘ２＿Ｑ，Ｙ２＿Ｑ）を“シュリンクラップ”したサブクアッド０，２，２のサイズに対して設定する；
・Ｓ１３．２  関心のある区域が切取り（クロッピング）を必要としているかどうか評価する：ｘ２＞Ｘ２＿Ｑであればｘ２＝Ｘ２＿Ｑと設定し、またｙ１＜Ｙ１＿Ｑであればｙ１＝Ｙ１＿Ｑと設定する；
・Ｓ１３．３  ｘ１＞ｘ２あるいはｙ１＞ｙ２かどうか評価する。この場合（図３０（ｂ））両方の条件が満足されていれば、関心のある区域内に落込むサブクアッド０，２，２内の点は存在しないことを意味する；
・Ｓ１３．６  このレベル（０，２，ｉ）でサブクアッドカウンタｉをインクレメントし、また図３１を参照して記述するように、Ｓ１３．１．２に従ってサブクアッド（０，２，３）を検索する（Ｓ１３．６．１）。
【００６１】
図３１
・Ｓ１３．１．２  “シュリンクラップ”したサブクアッド０，２，３から点の座標とサブクアッドの寸法とを検索する：０，２，３に対応しているサブクアッドは存在しないがその理由はこのサブクアッドに対応している領域内に点が存在しないことであり、そこでＳ１３．６へ跳び
・Ｓ１３．６．２  このレベル（０，２，ｉ）：ｉ＞３でサブクアッドカウンタｉをインクレメントして、それにより図３２及び図３３を参照して記述するようにＳ１３．１．２に従ってサブクアッド（０，３）を検索する（Ｓ１３．６．２）。
【００６２】
図３２及び図３３
・Ｓ１３．２  関心のある区域が切取り（クロッピング）を必要とするかどうか評価する：ｘ１＜Ｘ１＿Ｑであればｘ１＝Ｘ１＿Ｑと設定し、ｙ１＜Ｙ１＿Ｑ，ｘ２＞Ｘ２＿Ｑ及びｙ２＞Ｙ２＿Ｑであればｘ１＝Ｘ１＿Ｑ，ｙ１＝Ｙ１＿Ｑ，ｘ２＝Ｘ２＿Ｑ，ｙ２＝Ｙ２＿Ｑと設定する。
・Ｓ１３．３  ｘ１＞ｘ２かｙ１＞ｙ２かどうかを評価する：否であれば
・Ｓ１３．４  関心のある区域（今では切取られている）が正確にサブクアッドと重なるかどうか評価する：肯定であれば
・Ｓ１３．４．２  サブクアッドとサブクアッド内部の点の数（ここでは２）を記録する；
・Ｓ１３．６  このレベル（０，ｉ）…ｉ＞３でサブクアッドカウンタｉをインクレメントし、それによりＳ１３．１．２に従ってサブクアッド１を検索する（Ｓ１３．６．２）。
【００６３】
図１６から見ることができるように、関心のある区域はサブクアッド０とその中にあるサブクアッドの内部にだけに入ることになり、それにより、図１４と図１５とに記述したプロセスがサブクアッド１，２，３に適用されるときには、段階Ｓ１３．２とＳ１３．３で適用された条件２〜３段階（ａ ｆｅｗ ｓｔｅｐｓ）以内で該プロセスを終結する。
【００６４】
関心のある区域と重なっているサブクアッドを識別するためのプロセスの終りでは、サブクアッドと、こういったサブクアッド内部の点の数であって段階Ｓ１３．４．２で記録されたものが復帰される。この例は：
サブクアッド０，１，２，点の数：１点
サブクアッド０，１，３，点の数：１点
サブクアッド０，２，１，点の数：１点
サブクアッド０，３，    点の数：２点
ひとたびサブクアッドが識別されると、実際の点が検索される。この実施例では、上述したように、点はフラットファイル内に記憶されている。さらに、各サブクアッド構造は位置を示している数を記憶していて、それぞれのサブクアッド内部の第一の点についての、インデックスを付けられた点の全数と関係している（例えば図４，図５の例を参照するとクアッド５０１内部の点の全部の数と関係している）。点を実際に検索するためのプロセスは図３４に示されている：
段階Ｓ１３．４．２で記録された各クアッドについては：
・Ｓ３２．１  サブクアッド（Ｎ）の中に入る点の数をそのサブクアッドについて検索する；
・Ｓ３２．２  対応しているサブクアッド構造（Ｐｏｓｓｕｂ＿ｑｕａｄ）から第一の点の位置を検索する；
・Ｓ３２．３  Ｐｏｓｓｕｂ＿ｑｕａｄによって与えられる点のファイル内の位置にファイルポインタを移動する；
・Ｓ３２．４  この位置から、ファイルからＮ個の点を抽出する。
【００６５】
実施
図４及び図５、図１４及び図１５、また図３４で記述したプロセスは、ソフトウェアで実施され、端末Ｔ３，Ｔ４の１つで実行されるか、端末Ｔ３，Ｔ４の間で分散される。端末Ｔ３，Ｔ４はしたがって複数の電算機の一つまたは複数を代表していて、好ましくはサーバコンピュータである。
【００６６】
インデックスを付けられることになる点は端末Ｔ３，Ｔ４にファイルもしくは類似のものを介して入力されることができ、上述したように創られたインデックスがデータベースＤＢ１内に記憶されるようにでき、また点のファイルもデータベースＤＢ１内に記憶されるようにできる。関心のある領域はデータベース問合せの形式で入力されることができ、クライアント端末（図示せず）を介して入力され、既知のやり方で網Ｎ１上で通信される。
【００６７】
好ましくは、上述のプロセスがＣプログラム用言語で実施され、また反復的なプログラミング方法を使用して“バロウダウン（ｂｕｒｒｏｗ ｄｏｗｎ）”がサブクアッド内部のサブクアッドに対して行なわれることである。このような方法はこの発明にとって本質的なことではないと理解されたい。
【００６８】
追加的な詳記事項及び変形
上述したように、この発明は二次元で表現されたデータにインデックス付けをし検索するために使用できる。この発明はまた、二次元よりも高次元のデータをインデックス付けして検索するためにも使用できるのであって、ｎ＞２であるｎ次元データが二次元に変換できるようにする。この場合に、変換された、二次元データはこの発明によってインデックスが付けられて検索される。例えば、三次元空間内で定義されたオブジェクトはＮＣＡＲグラヒックスのようなパッケージを用いる二次元に変換されることができ、ＮＣＡＲグラヒックスはＵｎｉｘに基づくグラヒックスパッケージであって、これが広範囲にわたる能力を数値データについての表示と処理とについて提供していて、大気研究用の大学共同体（ｔｈｅ Ｕｎｉｖｅｒｓｉｔｙ Ｃｏｒｐｏｒａｔｉｏｎ ｆｏｒ Ａｔｍｏｓｐｈｅｒｉｃ Ｒｅｓｅａｒｃｈ）によって開発されたものである。（これに関して、ｈｔｔｐ：／／ｗｗｗ．ｄｋｒｚ．ｄｅ／ｎｇｄｏｃ／ｎｇ４．０．１をＮＣＡＲグラヒックスに関係する情報について参照し、また、ｈｔｔｐ：／／ｎｇｗｗｗ．ｕｃａｒ．ｅｄｕ／ｎｇｄｏｃ／ｎｇ／ｆｕｎｄ／ｃｈｐ１６−２１／ｔｈｒｅｅｄ．ｈｔｍｌを３次元から２次元変換という問題に係る情報について参照されたい。）
その他の変形修正も可能であり、例えば、簡単なものにクアッドとサブクアッドとを各反復で異なる数の領域へ分割することを用いることがあり、４に代って８とか１０とすることが挙げられる。
【図面の簡単な説明】
【図１】
この発明により使用される通信システムの特徴を示す模式図。
【図２】
この発明によりインデックスを付けされる点（ポイント）の例を示す模式図。
【図３】
図２の拡大図を示す模式図。
【図４】
図４（４ａ）は、図５（４ｂ）と組合わせて流れ図を構成し、図２で示した点にインデックス付けをするときの、この発明によるインデックス付けプロセスの実施例を示す。
【図５】
図５（４ｂ）は、図４（４ａ）と組合わせて流れ図を構成し、図２で示した点にインデックス付けをするときの、この発明によるインデックス付けプロセスの実施例を示す。
【図６】
図２に示した点の周りにクアッドを創るための図４と図５のプロセスの適用を示す模式図。
【図７】
図６により創られたクアッドのサブクアッドを創るための図４と図５とのプロセスの適用を示す模式図。
【図８】
図７のサブクアッドの一つのサブクアッドを創るための図４と図５とのプロセスの適用を示す模式図。
【図９】
図８の拡大図。
【図１０】
図８に示したサブクアッドとは別なものを創るための図４と図５とのプロセスの適用を示す図９の拡大図。
【図１１】
図８に示したサブクアッドとは別なものを創るための図４と図５とのプロセスの適用を示す図９の拡大図。
【図１２】
図７のサブクアッドの一つの別のサブクアッドを創るための図４と図５とのプロセスの適用を示す模式図。
【図１３】
この発明による点を記憶するプロセスを示す模式図。
【図１４】
図１４（１３ａ）は図１５（１３ｂ）との組合わせにより流れ図を構成し、関心のある領域に従って点を検索するときのこの発明による検索プロセスの実施形態を示す。
【図１５】
図１５（１３ｂ）は図１４（１３ａ）との組合わせにより流れ図を構成し、関心のある領域に従って点を検索するときのこの発明による検索プロセスの実施形態を示す。
【図１６】
点が検索されることになる関心のある領域の例を示す模式図。
【図１７】
図７のサブクアッドの一つに対する図１４と図１５のプロセスの適用を示す模式図。
【図１８】
図１７の拡大図であり、図８のサブクアッドの第一のものに対して図１４と図１５のプロセスの適用を示す模式図。
【図１９】
図１７の拡大図であり、図８のサブクアッドの第一のものに対して図１４と図１５のプロセスの適用を示す模式図。
【図２０】
図１７の拡大図であり、関心のある領域と図８のサブクアッドの第二のものとを示す図。
【図２１】
図２０に対応している模式図であり、図８のサブクアッドの第二のものに対して図１４と図１５のプロセスの適用を示す図。
【図２２】
（ａ）と（ｂ）とは図２０に示したサブクアッドの（第一の）サブクアッドに対して図１４と図１５のプロセスの適用を示す模式図。
【図２３】
（ａ）と（ｂ）とは図２０に示したサブクアッドの別の（第二の）サブクアッドに対して図１４と図１５のプロセスの適用を示す模式図。
【図２４】
（ａ）と（ｂ）とは図２０に示したサブクアッドの別の（第三の）サブクアッドに対して図１４と図１５のプロセスの適用を示す模式図。
【図２５】
（ａ）と（ｂ）とは図２０に示したサブクアッドの別の（第四の）サブクアッドに対して図１４と図１５のプロセスの適用を示す模式図。
【図２６】
図１７の拡大図であり、関心のある領域と、図８のサブクアッドの第三のものとを示す図。
【図２７】
図２６に対応している模式図であって、図８のサブクアッドの第三のものに対して図１４と図１５のプロセスの適用を示す図。
【図２８】
（ａ）と（ｂ）とは図２６に示したサブクアッドの（第一の）サブクアッドに対して図１４と図１５のプロセスの適用を示す模式図。
【図２９】
（ａ）と（ｂ）とは図２６に示したサブクアッドの別の（第二の）サブクアッドに対して図１４と図１５のプロセスの適用を示す模式図。
【図３０】
（ａ）と（ｂ）とは図２６に示したサブクアッドの別の（第三の）サブクアッドに対して図１４と図１５のプロセスの適用を示す模式図。
【図３１】
（ａ）と（ｂ）とは図２６に示したサブクアッドの別の（第四の）サブクアッドに対して図１４と図１５のプロセスの適用を示す模式図。
【図３２】
図１７の拡大図であり、関心のある領域と図８のサブクアッドの第四のものとを示す図。
【図３３】
図３２に対応している模式図であり、図８のサブクアッドの第四のものに対して図１４と図１５のプロセスの適用を示す図。
【図３４】
図１４と図１５の検索プロセスに含まれるさらなるステップを示す流れ図。
【図３５】
（ａ）ないし（ｅ）の各図は関心のある領域についての模式的な例示であり、関心のある領域についてこの発明により点が検索されることになる。
【図１】
2004516553.tif 000004
【図２】
2004516553.tif 000005
【図３】
2004516553.tif 000006
【図４】
2004516553.tif 000007
【図５】
2004516553.tif 000008
【図６】
2004516553.tif 000009
【図７】
2004516553.tif 000010
【図８】
2004516553.tif 000011
【図９】
2004516553.tif 000012
【図１０】
2004516553.tif 000013
【図１１】
2004516553.tif 000014
【図１２】
2004516553.tif 000015
【図１３】
2004516553.tif 000016
【図１４】
2004516553.tif 000017
【図１５】
2004516553.tif 000018
【図１６】
2004516553.tif 000019
【図１７】
2004516553.tif 000020
【図１８】
2004516553.tif 000021
【図１９】
2004516553.tif 000022
【図２０】
2004516553.tif 000023
【図２１】
2004516553.tif 000024
【図２２】
2004516553.tif 000025
【図２３】
2004516553.tif 000026
【図２４】
2004516553.tif 000027
【図２５】
2004516553.tif 000028
【図２６】
2004516553.tif 000029
【図２７】
2004516553.tif 000030
【図２８】
2004516553.tif 000031
【図２９】
2004516553.tif 000032
【図３０】
2004516553.tif 000033
【図３１】
2004516553.tif 000034
【図３２】
2004516553.tif 000035
【図３３】
2004516553.tif 000036
【図３４】
2004516553.tif 000037
【図３５】
2004516553.tif 000038
【国際公開パンフレット】
2004516553.tif 000039
2004516553.tif 000040
2004516553.tif 000041
2004516553.tif 000042
2004516553.tif 000043
2004516553.tif 000044
2004516553.tif 000045
2004516553.tif 000046
2004516553.tif 000047
2004516553.tif 000048
2004516553.tif 000049
2004516553.tif 000050
2004516553.tif 000051
2004516553.tif 000052
2004516553.tif 000053
2004516553.tif 000054
2004516553.tif 000055
2004516553.tif 000056
2004516553.tif 000057
2004516553.tif 000058
2004516553.tif 000059
2004516553.tif 000060
2004516553.tif 000061
2004516553.tif 000062
2004516553.tif 000063
2004516553.tif 000064
2004516553.tif 000065
2004516553.tif 000066
2004516553.tif 000067
2004516553.tif 000068
2004516553.tif 000069
2004516553.tif 000070
2004516553.tif 000071
2004516553.tif 000072
2004516553.tif 000073
2004516553.tif 000074
2004516553.tif 000075
2004516553.tif 000076
2004516553.tif 000077
2004516553.tif 000078
2004516553.tif 000079
2004516553.tif 000080
2004516553.tif 000081
2004516553.tif 000082
2004516553.tif 000083
2004516553.tif 000084
2004516553.tif 000085
2004516553.tif 000086
2004516553.tif 000087
2004516553.tif 000088
2004516553.tif 000089
2004516553.tif 000090
2004516553.tif 000091
2004516553.tif 000092
2004516553.tif 000093
2004516553.tif 000094
2004516553.tif 000095
2004516553.tif 000096
2004516553.tif 000097
2004516553.tif 000098
2004516553.tif 000099
2004516553.tif 000100
2004516553.tif 000101
2004516553.tif 000102
2004516553.tif 000103
【手続補正書】
【提出日】平成14年6月3日(2002.6.3)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のエンティテイに対してインデックスを構築する方法であって、各エンティテイは空間内で定義された点を識別するデータによって表わされており、該方法は：
（ｉ）該エンティテイを表わしている点の周りに区域を作ることと；
（ｉｉ）該創られた区域に係るプロセスを実行することを含んでおり、該プロセスは、記憶領域内に該区域を識別するデータを記憶する段階と、該記憶領域内に、該区域内に入る点へのリンクを識別するリンクデータを記憶する段階と、複数の部分区域に該区域を分割する段階とを備えており；
該方法は、該複数の部分区域の各々について、さらに
（ｉｉｉ）所定の規準が満足されることとなるまで関係する該プロセスを繰返し実行することを含んでおり；
該記憶領域は該エンティテイに対するインデックスを構成し；
該プロセスが該区域の外に入る点の一つを生ずることとなるまで区域を減らすことを含んでいることを特徴とする。
【請求項２】
請求項１記載の方法であって、該所定の規準は部分区域が単一の点を含むものとする方法。
【請求項３】
請求項１または２記載の方法であって、ある区域とその部分区域との間の関係を識別するリンクデータを記憶することを含んでいる方法。
【請求項４】
請求項１ないし請求項３のいずれか１項記載の方法であって、区域を減らす段階が、二次元の各々についてエンティテイに対応している点間の距離を計算することと；
該次元の各々について、どの点が点間で最大の距離を有するかを識別し、該二次元が互に直交しているときには、段階（ｉ）で創られた区域が矩形であり、少くとも二つのエンティテイに対応する点によって定義されるようにすることとを含んでいる方法。
【請求項５】
請求項１ないし請求項４のいずれか１項記載の方法であって、該区域が四つの部分区域に分割されている方法。
【請求項６】
請求項１ないし請求項５のいずれか１項記載の方法であって、段階（ｉｉ）及び（ｉｉｉ）が反復して繰返される方法。
【請求項７】
請求項１ないし請求項６のいずれか一項記載の方法であって、データベース内にリンクデータを記憶することと、該データベース内に記憶されたエンティテイの数のレジスタを維持することと、各部分区域について、現在のレジスタの数を対応する該記憶領域に書込むこととを含んでいる方法。
【請求項８】
請求項７記載の方法であって、エンティテイが該データベースに部分区域のサイズに従って書込まれて、一番小さな部分区域内に入るエンティテイが該データベースに最初に書込まれるようにする方法。
【請求項９】
請求項１ないし請求項８のいずれか１項記載の方法であって、段階（ｉ）ないし（ｉｉｉ）を発動させるためのトリガ信号を受信することを含んでいる方法。
【請求項１０】
所定領域内部に含まれている１又はそれ以上のエンティテイを検索する方法であって、各エンティテイは請求項１ないし請求項９のいずれか１項記載の方法によりインデックスが付けられており、本項記載の方法は、
（ａ）該所定領域内部に含まれている１又はそれ以上の区域を識別し、各区域が１又はそれ以上の点を取囲んでいて、しかも、各区域について、その区域によって取囲まれた点を識別するリンクデータと関係付けがされているようにする段階と；
（ｂ）該識別された区域に対応しているリンクデータにアクセスして、それにより該識別された区域により取囲まれた点を検索するようにする段階とを含んでいる。
【請求項１１】
請求項１０に記載の方法であって、該識別する段階（ａ）は、
（ｉ）ある区域を識別するデータを検索する段階と；
（ｉｉ）該区域に関して、次の段階を備えたプロセスを実行する段階とを含み、
該プロセスは、該区域の広がりの程度を該所定領域の広がりの程度と比較して該区域が該所定領域と重なるかどうかを確定する段階と、もし重なりがあれば、該区域の部分区域を識別するデータを検索して、かつ広がりの程度が該所定領域内部に完全にある部分区域を識別する段階とを含んでおり；また
（ｉｉｉ）各部分区域について、すべての部分区域が完全に該所定領域内に入ることが識別されるまで該プロセスを繰返す段階も含んでいて、
さらに、該アクセスする段階（ｂ）は該識別された部分区域に対応しているリンクデータにアクセスすることを含んでいて、それにより該部分区域により取囲まれた点を検索するようにした方法。
【請求項１２】
請求項１１記載の方法であって、該複数の点は、それぞれの区域とその区域の部分区域との間の関係に従って点のリストとして予め記憶されていて、該リンクデータは該点のリスト内の該対応している取囲まれた点の第一のものの位置を表示する値を含み、
また、該アクセスする段階（ｂ）は、該識別した区域の各々について：
取囲んだ点の数を表わす識別子を検索し、かつ該識別した区域と関係する位置の値を検索することと；
該点のリストにアクセスして、該位置の値により与えられるリスト内の位置から取囲まれた点の数を検索することを含んでいる方法。
【請求項１３】
請求項１０ないし請求項１２のいずれか１項記載の方法であって、該区域と、対応しているリンクデータとがインデックス内に記憶される方法。
【請求項１４】
請求項１０ないし請求項１３のいずれか１項記載の方法であって、該所定の領域がレンジ情報に対応する方法。
【請求項１５】
請求項１４記載の方法であって、該レンジ情報は地理的レンジ情報、動作時間情報、配信時間情報、及び医療情報のいずれか一つを含んでいる方法。
【請求項１６】
計算機プログラムもしくは計算機プログラムの組であって、計算機又は計算機の組に対して、請求項１ないし請求項９記載の方法を実行させるようにする一組の命令を備えている計算機プログラムもしくは計算機プログラムの組。
【請求項１７】
計算機プログラムもしくは計算機プログラムの組であって、計算機又は計算機の組に対して、請求項１０ないし請求項１６に記載の方法を実行するようにする一組の命令を備えている計算機プログラムもしくは計算機プログラムの組。
【請求項１８】
搬送波内に組込まれて、命令のシーケンスを表わしている計算機データ信号であって、該命令は、プロセッサによって実行されるときには請求項１ないし請求項９記載の方法を該プロセッサに実行させるものである信号。
【請求項１９】
搬送波内に組込まれて、命令のシーケンスを表わす計算機データ信号であって、該命令は、プロセッサによって実行されるときには、請求項１０ないし請求項１５に記載の方法を該プロセッサに実行させるものである信号。
【請求項２０】
一組のアイテムにインデックスを付ける方法であって、各アイテムは空間内の位置によって提示可能であり、かつ該アイテムの組は該組内での該アイテムの位置の該空間内での分布によって提示可能なものであり、該方法は；
ｉ）該空間の一部を定義して、この一部が該アイテムの組の位置を含む段階と；
ｉｉ）この部分をサブ部分に分割する段階と；
ｉｉｉ）１又はそれ以上のサブ部分をそれが含んでいる位置の数によって選ぶ段階と；
ｉｖ）各選ばれたサブ部分について、それが分割された前の部分を記録する段階と；
ｖ）該アイテムの位置を含んでいるそれぞれのサブ部分により該アイテムにインデックスを付ける段階とを含み、
該空間の一部の定義は、該空間内での境界を生成するのに適応されていて、この境界は前記分布の外側の限界と少くとも実質的に一致している。
【請求項２１】
請求項２０記載の方法であって、該１又はそれ以上のサブ部分は該サブ部分がもし１又はそれ以上の位置を含むならば選ばれる方法。
【請求項２２】
請求項２０または請求項２１に記載の方法であって、さらに各選ばれたサブ部分をさらにサブ部分に分割して、さらに分割したサブ部分が異なる数の位置を含むものとし、また各さらに分割したサブ部分について、各選ばれたサブ部分が少くとも実質的には単一の位置と一致するようになるまで、段階ｉｉｉ）とｉｖ）とを繰返し、
前記アイテムについてのインデックス付けがそれぞれのサブ部分に従って行なわれて、各アイテムについて単一の位置と少くとも実質的には一致するようにする方法。
【請求項２３】
請求項２０ないし請求項２２のいずれか１項記載の方法であって、該部分とサブ部分とが領域であり、該アイテムを表わしている位置が二次元の値によって識別される方法。
【請求項２４】
請求項２３に記載の方法であって、前記領域は正方形または長方形である方法。
【請求項２５】
請求項１８ないし請求項２３のいずれか１項記載の方法であって、各位置が点を備えている方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
場所の名称に基づいて、位置データにインデックスを付けることは知られている。また場所の名称から地理的な一組の座標を検索して、この座標から抽出された地形学的（ｔｏｐｏｌｏｇｉｃａｌ）情報に基づいたインデックスを構築することも知られている（例えば、“ＧＩＰＳＹ”はＵＣバークレイ校でジョイントＮＳＦ／ＮＡＳＡ／ＡＲＰＡ（Ｗｉｌｅｎｓｋｙ他，１９９４）主導で共同開発されている）。さらに、地理的な座標自体に基づいてインデックスを構築することも知られている。ＯｒａｃｌｅＴＭのようなデータベースベンダ（ｖｅｎｄｏｒｓ）は幾何学的なデータを記憶してインデックスを付けるためのシステムを開発しており、例えばＯｒａｃｌｅ空間データカートリッジがそれであり、これは空間的な問合せがＳＱＬの拡張された（標準形ではない）形式を用いて実行されるようにしている。その他のベンダはＭａｐＩｎｆｏＴＭ，ＳｐａｔｉａｌＷａｒｅＴＭ，ＩｎｎｏｇｉｓｔｉｃＴＭ，及びＩｎｆｏｒｍｉｘＴＭのようなもので、空間データを処理するのに類似の専有のやり方を有している。とくに、ＩｎｎｏｇｉｓｔｉｃＴＭはＣａｒｔｏｌｏｇｙ ＤＳＩとして知られている製品を開発し、これが幾何学的なベクトルデータをブロブ（ｂｌｏｂｓ）として記憶する（これは二値の大きなオブジェクトであり、基礎に置かれたデータベースによっては真性な（ｉｎｔｒｉｎｓｉｃａｌｌｙ）ものとして認識できないものである。ＩｎｎｏｇｉｓｔｉｃＴＭはよく知られた“クアッド−ツリー（ｑｕａｄ ｔｒｅｅ）”というアイデアに基づいてデータベースの外部でインデックスを創ることもする。このインデックスデータはバイナリ−ツリー（ｂｉｎａｒｙ−ｔｒｅｅ）の構造の中に記憶されて、Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｏｎｅｎｔ Ｏｂｊｅｃｔ Ｍｏｄｅｌ（ＤＣＯＭ）ミドルウェアサービスによってアクセスされる。


【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
米国特許ＵＳ ６，１６１，１０５はシステムを記述していて、それによると、多次元データが二進ハイパースペイシャル（ｈｙｐｅｒｓｐａｔｉａｌ）コード（ＢＨ ｃｏｄｅ）によって提示されていて、このコードはクアッドツリー（ｑｕａｄ ｔｒｅｅ）方法を用いてインデックス付けができる。
代りのインデックス付け方法は、ｋ次元（ｋ−ｄｉｍｅｎｓｉｏｎａｌ）バイナリ−サーチツリー（ｂｉｎａｒｙ ｓｅａｒｃｈ ｔｒｅｅ）方法であって、Ｊ．Ｌ．Ｂｅｎｔｌｅｙ“Ｍｕｌｔｉｄｉｍｅｎｔｉｏｎａｌ ｂｉｎａｒｙ ｓｅａｒｃｈ ｔｒｅｅ ｆｏｒ ａｓｓｏｃｉａｔｉｖｅ ｓｅａｒｃｈｉｎｇ”Ｃｏｍｍｕｎ．ＡＣＭ１８（９），１９７５，ｐｐ．５０９〜５１７に記述されている。この方法では、インデックスを付けられることになる点を含んでいる区域の垂直と水平の側部が比較されて、この区域が長い方の側部と垂直な直線によって二つの部分に分割されている。分割、もしくは区分け、線の位置は各結果として生じた部分がデータの同量を含むように決められている。この方法は、所定規準に合致するまで、反復して二つの部分の各々に適用される。一般に、この規準はリレーショナルデータベース内のページの容量（言い換えればデータベースの記憶拘束条件）に関係している。区分けされた部分はバイナリ−ツリーではノード（ｎｏｄｅｓ）として提示され、区分間を分けている線の位置はそのツリーの中のノードの位置（他のノードに関する）となっている。この方法は関心のある領域に関する点の検索にとってとくに効果的なものであり、その理由はサーチ空間（バイナリ−ツリー）の部分が関心のある領域と部分を分けている線との間の単純な比較によって除去されるようにできることによる。
ｋ−ｄツリー方法を地理的データに適用することは、“Ａ ｆｉｌｅ ｏｒｇａｎｉｓａｔｉｏｎ ｆｏｒ ｇｅｏｇｒａｐｈｉｃ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｓｐａｔｉａｌ ｐｒｏｘｉｍｉｔｙ”ｂｙ Ｍａｔｓｕｙａｍａ ｅｔ ａｌ，“Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，Ｇｒａｐｈｉｃｓ ａｎｄ ｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ ２６ ｐｐ．３０３〜３１８（１９８４）”に記述されている。とくに、Ｍａｔｓｕｙａｍａらはｋ−ｄツリー法の効果をクアッドツリー方法と比較し、ｋ−ｄツリー方法は記憶空間の使用とデータ検索という両方の点ではるかに効果的な方法であることを見付けている。このうち記憶空間の使用については、クアッドツリー方法は一般に点のない地区に対しクアッドをしたがって記憶領域を割当てることが理由であり、またデータ検索は、サーチ空間が、上述のようにｋ−ｄツリー方法を用いて効果的に減らされるようにできることによる。
ｋ−ｄツリー方法が標準のクアッドツリー方法よりも一層効果的であるという事実にも拘らず、以前として実際に必要とされるよりも多い領域に記憶領域を割当てる。上述のように、区域を区分するときに（バイナリ−ツリーの中にノードを作るときに）、区分けしている線は、結果として生ずる各部分が同じデータ量を含むように決められていて；その結果、必要とされるものよりも部分は大きなサイズとなり、終局的にはバイナリ−ツリーが必要以上に多くのノードをもつことになる。


【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
【課題を解決するための手段】
この発明の第一の特徴によると、複数のエンティテイに対してインデックスを構築する方法が提供され、各エンティテイは空間内で定義された点によって表わされている。該方法は：
（ｉ）該エンティテイを表わしている点の周りに区域を作ることと；
（ｉｉ）該創られた区域に係るプロセスを実行することを含んでおり、該プロセスは、記憶領域内に該区域を識別するデータを記憶する段階と、該記憶領域内に、該区域内に入る点へのリンクを識別するリンクデータを記憶する段階と、複数の部分区域に該区域を分割する段階とを備えており；
該方法は、該複数の部分区域の各々について、さらに
（ｉｉｉ）所定の規準が満足されることとなるまで関係する該プロセスを繰返し実行することを含んでおり；
該記憶領域は該エンティテイに対するインデックスを構成し；
該プロセスが該区域の外に入る点の一つを生ずることとなるまで区域を減らすことを含んでいることを特徴とする。


【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
こうして、既知のインデックス付け方法との比較では、この発明は先ずインデックス付け空間を“シュリンク（ｓｈｒｉｎｋｓ）”して、それにより、点を含む領域上にだけインデックスを付けるようにする。したがって記録領域は対応してコンパクトになり、これが記憶空間の使用を最小とするという面で利点がある。


【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
実際、“Ａ ｆｉｌｅ ｏｒｇａｎｉｓａｔｉｏｎ ｆｏｒ ｇｅｏｇｒａｐｈｉｃ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｓｐａｔｉａｌ ｐｒｏｘｉｍｉｔｙ”と題した前記書面を参照して、Ｍａｔｓｕｙａｍａらはクワッドツリー方法に関連する問題、すなわち空のデータベースページ（ｐ３１２参照）のインデックス付けを識別するが、しかし本発明の方法（ｋ−ｄツリー方法）とは全く異なる方法を適用することによって問題を解決する。


【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
好都合なことは、区域を減らす段階が二次元の各々の次元でエンティテイ間の距離を計算することを含んでいて；また該次元の各々について、どのエンティテイがエンティテイ間で一番大きな距離を有しているかを識別することを含み、それによって該二つの次元が互に垂直であるときには、段階（ｉｉ）で創られた区域が少くとも二つの点により定義された矩形であるようにすることである。
部分区域（ｓｕｂ−ｒｅｇｉｏｎｓ）はいわゆる点の“リンクしたリスト（ｌｉｎｋｅｄ ｌｉｓｔ）”を介してリンクされるようにできて、このリストは当業者に知られている効果的なリンク機構（ｌｉｎｋｉｎｇ ｍｅｃｈａｎｉｓｍ）となっている。
好ましくは、この地区が四つの部分区域に分けられて、段階（ｉｉ）と（ｉｉｉ）とが第二の区域の各々について反復して繰返される。
便利なのは、この方法がデータベース内にリンクデータを記憶することと、該データベース内に記憶されたエンティテイの数のレジスタを維持することと、各部分区域について、現在のレジスタの数を対応する該記憶領域に書込むこととを含んでいることである。


【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
好ましくは識別する段階（ａ）はある区域を検索して、その区域に関してプロセスを実行する段階を含んでおり、このプロセスは次の段階を含んでいる：すなわち、該領域の広がりの程度を該所定領域の広がりの程度と比較して第一の地域が該所定領域と重なるかどうか確定するようにし；そしてもし重なりが存在すれば該地区の部分区域を検索して、該所定領域内部に完全に入る広がりの程度をもつようなどんな部分区域をも識別する段階を含んでいる。このプロセスは各部分区域について、すべての部分区域が該所定領域内に完全に入ると識別されるまで繰返すことができる。


【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
便利なのは、複数の点が、それぞれの区域とその部分区域との間の関係に従って点のリストとして、前もって記憶されていて、またリンクデータは点のリスト内で対応している取囲まれた点の第一のものの位置を示している値を含んでいることである。アクセス段階（ｂ）はそこで各識別された地区と部分区域とについて次のことを備えている：つまり取囲まれている点の数を表わしている識別子を検索すること、識別された部分区域と関係している位置の値を検索すること；及び、該点のリストにアクセスして、該位置の値により与えられる該リスト内の位置から取囲まれた点の数を検索することとを備えている。




【国際調査報告】
2004516553.tif 000104
2004516553.tif 000105
2004516553.tif 000106