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


【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
【課題を解決するための手段】
この発明の第一の特徴によると、所定の領域により包含されている点（ｐｏｉｎｔｓ）を検索する方法が提供されている。この方法は、
（ｉ）１又はそれ以上の点を取囲む区域を識別するデータを検索する段階であって、該区域はリンクデータと関係していて、リンクデータは各区域について、該区域により取囲まれた点を識別する段階と；
（ｉｉ）該区分についてプロセスを実行する段階と；
該プロセスは、該区域の広がりの程度を該所定の領域の広がりの程度と比較して、該区域が該所定の領域と重なっているかどうかを確立する段階と、重なりがある場合には、該区域についての部分区域を識別し、この部分区域のいずれかであってその広がりの程度が該所定の領域の中に完全に入っているものを識別する段階とを有し、
（ｉｉｉ）各部分区域について、該所定の領域内部に完全に入るすべての部分区域が識別されるまで上記プロセスを繰返す段階と；
（ｉｖ）該識別された部分区域に対応しているリンクデータにアクセスして、該部分区域により取囲まれた点を検索する段階とを備えている。


【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
該複数の点が該区域と部分区域との間の所定の関係により与えられる順序で、点のリストとして有効に予め記憶されている。さらに、リンクデータは該点のリスト内の対応している取囲まれた点の第一のものの位置を示している値を含んでいる。


【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
また、該アクセスする段階は、取囲まれた点の数を表わしている識別子を検索することと、該識別された区域または部分区域と関係している位置の値を検索することとを含んでいる。これが該位置の値と関係している該リスト中の位置から、取囲まれた点の数を検索できるようにする。




【国際調査報告】
2004516552.tif 000102
2004516552.tif 000103
2004516552.tif 000104