コンピュータが領域を検索する際に用いられるインデックス情報であって複数の領域を含む領域情報とともに前記領域を管理するインデックス情報をツリー構造で表したインデックスツリーを用いて、所定の位置を含む領域を検索し、該位置を含む領域を検索できた場合、複数の領域のそれぞれについて領域と重複する重複領域の情報を記憶した記憶部に基づいて、検索できた領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索し、前記検索領域を包含する重複領域の情報とともに、検索できた領域の情報を出力することを実行する領域検索方法。該位置を含む領域を検索する処理は、複数の領域のそれぞれについて領域を包含する外部包含領域の情報、領域が包含する内部包含領域の情報および領域と部分的に重複する部分重複領域の情報を記憶した前記記憶部に基づいて、前記検索領域と重複する内部包含領域および部分重複領域の中から該位置を含む領域を検索することを特徴とする請求項1に記載の領域検索方法。該位置を含む領域を検索する処理は、前記検索領域と重複するいずれかの内部包含領域の中から該位置を含む領域を新たに検索できた場合、前記記憶部に基づいて、前記検索領域の残りの検索対象である内部包含領域の数および部分重複領域の数の和と、新たに検索できた領域の内部包含領域の数および部分重複領域の数の和とを比較し、前記比較する処理によって新たに検索できた領域に係る和の数が前記検索領域に係る和の数より小さい場合、前記検索領域における検索処理を中止し、新たに検索できた領域における検索処理を実行することを特徴とする請求項2に記載の領域検索方法。該位置を含む領域を検索する処理は、前記検索領域と重複する内部包含領域について、当該内部包含領域が包含する内部包含領域の数および当該内部包含領域の部分重複領域の数の和と、前記検索領域と重複する内部包含領域の数および部分重複領域の数の和との差分を算出し、算出した差分の大きい順に前記検索領域と重複する内部包含領域を選択し、選択した内部包含領域に該位置が含まれるか否かを検索することを特徴とする請求項2または請求項3に記載の領域検索方法。所定の位置を含む領域の問合せ要求を取得すると、該位置が前回検索できた領域に含まれるか否かを判定し、判定の結果、該位置が前回検索できた領域に含まれると判定された場合、前記記憶部に基づいて、含まれると判定された領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索することを特徴とする請求項1に記載の領域検索方法。コンピュータに、領域を検索する際に用いられるインデックス情報であって複数の領域を含む領域情報とともに前記領域を管理するインデックス情報をツリー構造で表したインデックスツリーを用いて、所定の位置を含む領域を検索し、該位置を含む領域を検索できた場合、複数の領域のそれぞれについて領域と重複する重複領域の情報を記憶した記憶部に基づいて、検索できた領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索し、前記検索領域を包含する重複領域の情報とともに、検索できた領域の情報を出力する各処理を実行させることを特徴とする領域検索プログラム。複数の領域のそれぞれについて領域と重複する重複領域の情報を記憶した記憶部と、領域を検索する際に用いられるインデックス情報であって複数の領域を含む領域情報とともに前記領域を管理するインデックス情報をツリー構造で表したインデックスツリーを用いて、所定の位置を含む領域を検索する第1の検索部と、前記第1の検索部によって該位置を含む領域を検索できた場合、前記記憶部に基づいて、検索できた領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索する第2の検索部と、前記検索領域を包含する重複領域の情報とともに、前記第2の検索部によって検索できた領域の情報を出力する出力部とを有することを特徴とする情報処理装置。しかしながら、インデックスを用いた従来の範囲検索では、検索時間を要してしまうという問題があった。すなわち、Rツリーを利用したデータ管理方式では、検索操作を実行する都度、ルートノードから検索を開始するので、常時logNオーダの検索回数が必要となり、検索時間を要してしまう。階層化された領域に関する座標情報を用いて範囲検索する場合であっても、現在の位置が測定される都度、測定される現在の位置に関する検索判定を、広い領域から順番に開始するので、検索時間を要してしまうことには変わりがない。開示の技術は、インデックスを用いた範囲検索の検索時間を高速化することができることを目的とする。1つの側面では、領域検索方法は、領域を検索する際に用いられるインデックス情報であって複数の領域を含む領域情報とともに前記領域を管理するインデックス情報をツリー構造で表したインデックスツリーを用いて、所定の位置を含む領域を検索し、該位置を含む領域を検索できた場合、複数の領域のそれぞれについて領域と重複する重複領域の情報を記憶した記憶部に基づいて、検索できた領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索し、前記検索領域を包含する重複領域の情報とともに、検索できた領域の情報を出力する。本願の開示する領域検索方法の一つの態様によれば、インデックスを用いた範囲検索の検索時間を高速化することができる。以下に、本願の開示する領域検索方法、領域検索プログラムおよび情報処理装置の実施例を図面に基づいて詳細に説明する。なお、実施例によりこの発明が限定されるものではない。[領域検索サーバ]図1は、実施例1に係る領域検索サーバの構成を示す機能ブロック図である。図1に示すように、領域検索サーバ1は、通信インタフェース11と、記憶部12と、制御部13とを有する。通信インタフェース11は、各端末装置との間で通信を確立して、各端末装置から領域検索要求を受信したり、各端末装置に領域検索応答を送信したりするインタフェースである。ここで、領域検索要求とは、端末装置の位置情報がいずれの領域に含まれるかを検索する要求である。位置情報は、例えば端末装置が存在する位置を示す緯度、経度の情報であるが、端末装置が存在する空間内の範囲を示す情報であっても良い。そして、領域検索要求は、例えば端末装置の位置情報や端末装置が持つセンサーの識別IDを含む内容となる。領域検索応答とは、領域検索要求に対応する応答であり、検索結果を含む内容となる。なお、通信インタフェース11は、例えば、LANやインターネット等と接続するネットワークインタフェースカードや、無線アンテナを有する無線通信部等である。記憶部12は、制御部13が実行するプログラム等を記憶するとともに、領域インデックスDB121と領域データDB122とを有する。なお、記憶部12は、例えば、RAMRandomAccessMemory、フラッシュメモリflashmemory等の半導体メモリ素子、または、ハードディスク、光ディスク等の記憶装置である。領域インデックスDB121は、空間内に存在する大量の領域から条件に合った領域を高速に検索するための索引情報である。例えば、領域インデックスDB121は、どの領域がどこにあるのかを示したインデックスをRツリーで保持する。ここで、領域インデックスDB121に記憶される情報の例を、図2を参照して説明する。図2は、領域インデックスDBに記憶される情報の例を示す図である。図2に示すように、領域インデックスDB121は、ルートノード、中間ノードおよび葉ノードのいずれかを示す領域データで形成されるRツリーを記憶する。ルートノードは、Rツリーに1つ存在する頂点の領域データである。また、葉ノードは、Rツリーの最底辺のノードであり、自らは子ノードを含まず、検索対象となる多次元の領域データを1つ以上持つ。それ以外の木の中間に存在するノードは、中間ノードであり、それぞれ子ノードを1つ以上持つ。図2の例では、ルートノードがR1であり、R1の子ノード且つ中間ノードがR10、R11である。R1がR10、R11の矩形領域を全て含む矩形領域となっている。中間ノードR10の子ノードである葉ノードがR100、R101である。R10がR100、R101の矩形領域を全て含む矩形領域となっている。中間ノードR11の子ノードである葉ノードがR110、R111である。R11がR110、R111の矩形領域を全て含む矩形領域となっている。そして、葉ノードであるR100は、検索対象となる領域データ1、2、3を持っている。葉ノードであるR101は、検索対象となる領域データ4、5を持っている。葉ノードであるR110は、検索対象となる領域データ6、7を持っている。葉ノードであるR111は、検索対象となる領域データ8、9を持っている。なお、領域データ1~9は、例えば領域データを識別可能なIDIDentificationである領域IDと一意に紐付くので、領域IDとしても良い。領域インデックスDB121は、Rツリーの実体としてルート、中間、葉の各ノードの情報を記憶する。図3は、領域インデックスDBに記憶されるルートノードの情報の例を示す図である。図3に示すように、領域インデックスDB121は、ルートノードR1の情報として、ノード種別、矩形領域、子ノードリストを記憶する。ノード種別は、ノードがルート、中間、葉のいずれかであるかを示す情報である。矩形領域は、子ノードの担当領域を全て含む最小外接矩形の情報である。最小外接矩形とは、子ノードの領域を全て含む最小の矩形領域をいう。子ノードリストは、当該ノードの子ノードへのリンクポインタのリストである。図3の例では、ルートノードR1は、x、yの2次元データを管理し、x1=35.5、y1=139.0が担当領域の最小点であり、x2=35.9、y2=139.5が担当領域の最大点であることを示す。すなわち、R1が担当する領域は、両点を頂点として各次元軸に直交した4直線で作られる領域である。また、R1は、子ノードR10、R11へのポインタのリストを記憶する。図4は、領域インデックスDBに記憶される中間ノードの情報の例を示す図である。図4に示すように、領域インデックスDB121は、中間ノードの情報として、ノード種別、矩形領域、子ノードリストを記憶する。ここで記憶されるノード種別、矩形領域、子ノードリストは、図3と同様であるので詳細な説明は省略する。領域インデックスDB121は、R10、R11について、図4の情報を記憶する。図4の場合、中間ノードR10は、x、yの2次元データを管理し、x1=35.5、y1=139.2が担当領域の最小点であり、x2=35.7、y2=139.3が担当領域の最大点であることを示す。すなわち、中間ノードR10が担当する領域は、両点を頂点として各次元軸に直交した4直線で作られる領域である。また、R10は、子ノードR100、R101へのポインタのリストを記憶する。図5は、領域インデックスDBに記憶される葉ノードの情報の例を示す図である。図5に示すように、領域インデックスDB121は、葉ノードの情報として、ノード種別、矩形領域、データリストを記憶する。ここで記憶されるノード種別、矩形領域は、図3と同様であるので詳細な説明は省略する。データリストは、管理する多次元の領域データである。領域インデックスDB121は、R100、R101、R110、R111について、図5の情報を記憶する。図5の場合、葉ノードR100は、x、yの2次元データを管理し、x1=35.5、y1=139.2が担当領域の最小点であり、x2=35.6、y2=139.3が担当領域の最大点であることを示す。すなわち、葉ノードR100が担当する領域は、両点を頂点として各次元軸に直交した4直線で作られる領域である。また、R100は、領域データX1、X2、X3、X4へのポインタのリストを記憶する。領域データへのポインタの一例として、領域データを識別する領域IDが用いられる。各領域データの実体は、後述する領域データDB122に格納されている。図1に戻って、領域データDB122は、複数の領域のそれぞれについて領域と重複する重複領域の情報を管理する。ここで、領域データDB122のデータ構造の一例を、図6を参照して説明する。図6は、領域データDBのデータ構造の一例を示す図である。図6に示すように、領域データDB122は、領域ID122a毎に、データ名122b、領域情報122c、内部包含122d、外部包含122eおよび部分重複122fを対応付けて記憶する。領域ID122aは、領域データを一意に識別可能なIDを示す。データ名122bは、領域IDで示される領域データのデータ名を示す。領域情報122cは、領域IDで示される領域データの実体である具体的な領域の範囲を示す。内部包含122dは、領域IDで示される領域データの領域の内部に包含される領域以降、内部包含領域という。の領域IDを示す。外部包含122eは、領域IDで示される領域データの領域を包含する領域以降、外部包含領域という。の領域IDを示す。部分重複122fは、領域IDで示される領域データの領域と部分的に重複する他の領域以降、部分重複領域という。の領域IDを示す。内部包含122d、外部包含122eおよび部分重複122fには、0個、1個または複数個の領域IDが記憶される。例えば、領域ID122aがX0である場合、データ名122bとしてAAA区BBB町付近、領域情報122cとして円領域:緯度A0、経度B0、半径R0mと記憶している。そして、内部包含122dとしてX1、X2、X3、X4、外部包含122eとして空白、部分重複122fとして空白と記憶している。また、領域ID122aがX1である場合、データ名122bとしてCCC工場、領域情報122cとして円領域:緯度A1、経度B1、半径R1mと記憶している。そして、内部包含122dとしてX2、X3、外部包含122eとしてX0、部分重複122fとしてX4と記憶している。また、領域ID122aがX2である場合、データ名122bとしてDDD研究所、領域情報122cとして円領域:緯度A2、経度B2、半径R2mと記憶している。そして、内部包含122dとしてX3、外部包含122eとしてX0、X1、部分重複122fとしてX4と記憶している。また、領域ID122aがX3である場合、データ名122bとしてNNN付近、領域情報122cとして円領域:緯度A3、経度B3、半径R3mと記憶している。そして、内部包含122dとして空白、外部包含122eとしてX0、X1、X2、部分重複122fとしてX4と記憶している。また、領域ID122aがX4である場合、データ名122bとしてFFF駅周辺、領域情報122cとして円領域:緯度A4、経度B4、半径R4mと記憶している。そして、内部包含122dとして空白、外部包含122eとしてX0、部分重複122fとしてX1、X2、X3と記憶している。ここで、図6の領域データDB122に記憶された領域IDが示す領域の重複関係について、図7を参照して説明する。図7は、領域の重複関係を示す図である。図7に示すように、領域IDがX0である場合、内部包含領域としてX1、X2、X3、X4がある。領域IDがX1である場合、外部包含領域としてX0があり、内部包含領域としてX2、X3があり、部分重複領域としてX4がある。領域IDがX2である場合、外部包含領域としてX0、X1があり、内部包含領域としてX3があり、部分重複領域としてX4がある。領域IDがX3である場合、外部包含領域としてX0、X1、X2があり、部分重複領域としてX4がある。領域IDがX4である場合、外部包含領域としてX0があり、部分重複領域としてX1、X2、X3がある。このように、領域データDB122は、複数の領域IDが示す領域のそれぞれについて、領域と重複する内部包含領域、外部包含領域および部分重複領域のそれぞれの領域IDを管理する。図1に戻って、制御部13は、リクエスト受付部131、レスポンス転送部132、ツリー検索部133、外包領域結果追加部134、重複領域検索部135および重複領域設定部136を有する。制御部13は、例えば、ASICApplicationSpecificIntegratedCircuitやFPGAFieldProgrammableGateArray等の集積回路またはCPUCentralProcessingUnitやMPUMicroProcessingUnit等の電子回路である。リクエスト受付部131は、通信インタフェース11によって受信された検索リクエストを受け付ける。レスポンス転送部132は、検索リクエストに対応する領域検索応答を通信インタフェース11を介して転送する。ツリー検索部133は、領域インデックスDB121を用いて、所定の位置情報を含む領域を検索する。例えば、ツリー検索部133は、リクエスト受付部131によって受け付けられた領域検索要求の中から位置情報を取り出す。そして、ツリー検索部133は、ルートノードから子ノードへトップダウンに辿り順番にノードを選択し、選択したノードの子ノードに、取り出した位置情報を含むものがあるか否かを、領域インデックスDB121を用いて判定する。そして、ツリー検索部133は、位置情報を含む子ノードがあれば、かかる子ノードを選択候補ノードとして追加する。さらに、ツリー検索部133は、選択候補ノードとして追加されたノードを1つずつ選択し、選択したノードが葉ノードであれば、葉ノードにある領域データ領域IDの内、取り出した位置情報を含むものがあるか否かを、領域インデックスDB121を用いて判定する。そして、ツリー検索部133は、領域データの内、取り出した位置情報を含むものが1つでもあれば、いずれか1つの領域データを検索結果に追加し、領域インデックスDB121を用いた検索を終了する。なお、ツリー検索部133は、位置情報を含む領域データが複数ある場合には、領域データの内部包含領域および部分重複領域の数の和が最も小さい領域データを検索結果に追加することが望ましい。これは、後述する重複領域検索部135がさらに検索結果に追加した領域データの重複領域から位置情報を含む領域を検索することとなるので、検索対象となる領域を減らすべく、検索対象となる重複領域の数が最も小さい領域データを検索結果に追加するものである。外包領域結果追加部134は、検索結果に追加した領域データの外部包含領域が示す領域データを検索対象としないで、検索結果に追加する。すなわち、外報領域結果追加部134は、検索結果に追加した領域データが位置情報を含むものであるので、位置情報を含む領域データを包含する外部包含領域について検索するまでもなく、位置情報を含むものであると判断する。これにより、位置情報を含む領域データの外部包含領域の検索処理を省略できるので、検索処理を高速化できる。重複領域検索部135は、ツリー検索部133によって所定の位置情報を含む領域を検索できた場合、検索できた領域以降、検索領域という。の内部包含領域および部分重複領域の中から位置情報を含む領域を検索する。例えば、重複領域検索部135は、ツリー検索部133によって追加された検索結果から領域データ領域IDを取り出す。そして、重複領域検索部135は、領域データDB122から、取り出した領域IDに対応する内部包含122dおよび部分重複122fの領域IDを読み出す。そして、重複領域検索部135は、読み出した領域IDを1つずつ選択し、選択した領域IDの領域が位置情報を含むか否かを判定する。そして、重複領域検索部135は、判定結果に基づき、位置情報を含む領域の領域IDを検索結果に追加する。なお、重複領域検索部135は、検索領域の内部包含領域の中から位置情報を含む領域を検索できたとき、検索領域における残りの検索対象である重複領域の数と新たに検索できた領域における検索対象である重複領域の数とを比較するようにしても良い。ここで、領域における検索対象である重複領域とは、領域の内部包含領域および部分重複領域を意味する。そして、重複領域検索部135は、検索対象の数が小さい方の領域の重複領域の検索に切り替える。すなわち、重複領域検索部135は、検索領域における残りの検索対象の数が新たに検索できた領域における検索対象の数より大きい場合、検索領域における残りの検索対象の検索を中止し、新たに検索できた領域における検索対象の検索を実行する。一方、重複領域検索部135は、検索領域における残りの検索対象の数が新たに検索できた領域における検索対象の数より小さいまたは等しい場合、検索領域における残りの検索対象の検索を継続して実行する。つまり、重複領域検索部135は、検索効率を上げるために、検索対象の数が小さい方の領域の重複領域を検索するのである。重複領域設定部136は、領域データDB122に重複領域の情報を設定する。なお、重複領域設定部136は、領域インデックスDB121に新たな領域の情報を追加する際に、この追加領域の情報として追加領域と重複する重複領域の情報を領域データDB122に追加するようにすれば良い。例えば、重複領域設定部136は、ルートノードから子ノードに向かって順番にノードを選択する。そして、重複領域設定部136は、選択したノードの子ノードに、追加領域を含むものがあるか否かを、領域インデックスDB121を用いて判定する。そして、重複領域設定部136は、追加領域を含む子ノードを選択候補ノードとして追加する。そして、重複領域設定部136は、選択候補ノードとして追加されたノードを1つずつ選択し、選択したノードが葉ノードであれば、葉ノードにある領域データの内、追加領域と重複する部分がある領域データを重複領域として抽出する。さらに、重複領域設定部136は、抽出した重複領域を1つずつ選択する。そして、重複領域設定部136は、選択した重複領域が追加領域の内側に完全に含まれる場合、選択した重複領域の領域IDを追加領域の内部包含領域として、領域データDB122に追加する。加えて、重複領域設定部136は、追加領域の領域IDを、選択した重複領域の外部包含領域として、領域データDB122に追加する。そして、重複領域設定部136は、追加領域が、選択した重複領域の内側に完全に含まれる場合、選択した重複領域の領域IDを追加領域の外部包含領域として、領域データDB122に追加する。加えて、重複領域設定部136は、追加領域の領域IDを、選択した重複領域の内部包含領域として、領域データDB122に追加する。そして、重複領域設定部136は、追加領域が、選択した重複領域と互いに部分的に重複している場合、選択した重複領域の領域IDを追加領域の部分重複領域として、領域データDB122に追加する。加えて、重複領域設定部136は、追加領域の領域IDを、選択した重複領域の部分重複領域として、領域データDB122に追加する。なお、重複領域設定部136は、領域の領域IDを内部包含領域として領域データDB122に追加する場合、領域データDB122の内部包含122d内に追加する位置を考慮するようにしても良い。すなわち、重複領域検索部135は、検索領域の内部包含領域の中から位置情報を含む領域を検索するが、検索する処理効率を上げるために内部包含領域を選択する順序を考慮するものである。1つの例として、重複領域検索部135が、検索領域と重複する内部包含領域内に位置情報を含む確率が高い順に、内部包含領域を選択できるようにしても良い。例えば、重複領域設定部136は、領域データDB122の内部包含122d内に内部包含領域として追加する領域の領域IDを、領域IDの領域の面積が大きい順となるように追加する。また、別の例として、重複領域検索部135が、検索領域と重複する内部包含領域内に位置情報を含むときに当該内部包含領域の重複領域の検索に切り替えた場合に削減できる処理量が多い順に内部包含領域を選択できるようにしても良い。例えば、重複領域設定部136は、検索領域における検索対象の数として、検索領域が包含する内部包含領域の数および検索領域の部分重複領域の数の和を算出する。そして、重複領域設定部136は、追加する内部包含領域における検索対象の数として、当該領域が内部に包含する内部包含領域の数および当該領域の部分重複領域の数の和を算出する。そして、重複領域設定部136は、領域データDB122の内部包含122d内に内部包含領域として追加する領域の領域IDを、算出した和の差分が大きい順となるように追加する。さらに、別の例として、重複領域検索部135は、上記2つの例を併合するように内部包含領域を選択できるようにしても良い。例えば、重複領域設定部136は、追加する内部包含領域の面積と、検索領域における検索対象の数と当該内部包含領域における検索対象の数との差分との積を算出する。そして、重複領域設定部136は、領域データDB122の内部包含122d内に内部包含領域として追加する領域の領域IDを、算出した結果値の大きい順となるように追加する。ここで、重複領域設定部136によって領域データDB122の内部包含122d内に内部包含領域の領域IDが追加される場合の具体例を、図8を参照して説明する。図8は、重複領域設定における内部包含領域追加の具体例を示す図である。なお、図8は、検索領域と重複する内部包含領域内に位置情報を含む確率と、検索領域と重複する内部包含領域の重複領域の検索に切り替えた場合に削減できる処理量とを考慮した順に内部包含領域を選択できるようにする場合の例である。図8左側に示すように、検索領域Aには、それぞれ領域IDをX1、X2、X3とした内部包含領域が存在している。図8右側に示すIDは、各領域における領域IDであるものとする。Inは、各領域における検索対象である内部包含領域および部分重複領域の数の和であるものとする。Snは、各領域における面積であるものとする。Iaは、検索領域Aの検索対象の数であるものとし、ここでは、10とする。このような前提のもと、領域IDがX1である領域について、Inが6、IaとInとの差分が4、Snが800を示している。そして、重複領域設定部136は、X1である領域について、領域X1の面積800と、検索領域Aにおける検索対象の数と領域X1における検索対象の数との差分4との積3200を、検索を優先させるか否かを示す評価値として算出する。また、領域IDがX2である領域について、Inが4、IaとInとの差分が6、Snが650を示している。そして、重複領域設定部136は、X2である領域について、領域X2の面積650と、検索領域Aにおける検索対象の数と領域X2における検索対象の数との差分6との積3900を、評価値として算出する。また、領域IDがX3である領域について、Inが0、IaとInとの差分が10、Snが25を示している。そして、重複領域設定部136は、X3である領域について、領域X3の面積25と、検索領域Aにおける検索対象の数と領域X3における検索対象の数との差分10との積250を、評価値として算出する。そして、重複領域設定部136は、領域データDB122に記憶された領域IDがAを示す内部包含122d内に内部包含領域として追加する領域の領域IDを、評価値の大きい順となるように追加する。仮にX1が追加する領域であるとすると、重複領域設定部136は、X2、X1、X3の順となるようにX1を追加する。X2が追加する領域であるとすると、重複領域設定部136は、X2、X1、X3の順となるようにX2を追加する。これにより、重複領域検索部135は、Pqが位置情報である場合、ツリー検索部133によってPqを含む領域を検索できた場合、検索できた領域検索領域Aの内部包含領域をX2、X1、X3の順でPqを含む領域を検索できる。この結果、重複領域検索部135は、内部包含領域の早い順でヒットできる確率が高いので、ヒットした内部包含領域の重複領域の検索に切り替えれば検索に要する処理量を削減することが可能となる。なお、重複領域設定部136は、評価値が同じ場合には、面積が大きいものを先の順にしても良いし、検索領域における検索対象の数と検索領域が包含する各内部包含領域における検索対象の数との差分が大きいものを先の順にしても良い。また、重複領域設定部136は、領域を追加する際、追加する領域の評価値を算出し、算出した評価値を、事前に算出された他の内部包含領域の評価値と比較し、追加する領域の領域IDを評価値に該当する位置に追加するようにしても良い。この場合、領域データDB122には、領域の領域ID毎に評価値を設定する項目を用意しておき、領域が追加される度に評価値を算出し、算出した値を当該項目に設定するようにすれば良い。また、重複領域設定部136は、領域を追加する際、追加する領域とともに他の内部包含領域の評価値を算出し、算出したそれぞれの評価値を比較し、追加する領域の領域IDを評価値に該当する位置に追加するようにしても良い。また、領域が追加される毎に各内部包含領域の評価値は変化する。このため、重複領域設定部136は、内部包含領域の追加する際にはリストの末尾に追加しておき、定期的に全ノードの内部包含領域を評価してソートする処理を実施しても良い。この場合、ソート処理は重複領域の追加削除処理が少ない時に行うことが望ましい。[領域検索要求のデータの一例]次に、リクエスト受付部131が通信インタフェース11を介して受け付ける領域検索要求の内容について、図9を参照して説明する。図9は、領域検索要求の内容の一例を示す図である。図9に示すように、領域検索要求には、センサーを識別するセンサーIDと、緯度および経度とを含む。緯度および経度は、位置情報の一例である。図9の例では、センサーIDとしてSensor000X、緯度として35.4134、経度として139.6252と設定している。なお、領域検索要求には、センサーIDを含むものとしたが、これに限定されず、領域検索を要求する端末装置の装置IDであっても良いし、領域検索を要求する携帯電話の携帯電話番号であっても良い。[領域検索応答のデータの一例]次に、レスポンス転送部132が通信インタフェース11を介して出力する領域検索応答の内容について、図10を参照して説明する。図10は、領域検索応答の内容の一例を示す図である。図10に示すように、領域検索応答は、領域検索の結果を示す領域情報のリストであり、領域情報に対応する領域IDと領域名とを含む。図10の例では、領域IDとしてX0、領域名としてAAA区BBB町付近と設定している。また、領域IDとしてX4、領域名としてFFF駅周辺と設定している。なお、領域情報のリストには、領域IDと領域名とを含むものとしたが、これに限定されず、領域の位置、大きさや形状等を含むものとしても良い。[リクエスト受付処理の手順]次に、検索に係るリクエスト受付処理の手順について、図11を参照して説明する。図11は、検索に係るリクエスト受付処理の手順を示すフローチャートである。まず、リクエスト受付部131は、領域検索要求を受け付けたか否かを判定するステップS10A。そして、領域検索要求を受け付けていないと判定した場合ステップS10A;No、リクエスト受付部131は、領域検索要求を受け付けるまで、判定処理を繰り返す。一方、領域検索要求を受け付けたと判定した場合ステップS10A;Yes、リクエスト受付部131は、検索処理を実行するステップS10B。そして、リクエスト受付部131は、リクエスト受付処理を終了したか否かを判定するステップS10C。リクエスト受付処理を終了していないと判定した場合ステップS10C;No、リクエスト受付部131は、ステップS10Aに移行する。一方、リクエスト受付処理を終了したと判定した場合ステップS10C;Yes、リクエスト受付部131は、処理を終了する。[検索処理の手順]次に、図11のステップS10Bに示した検索処理について、図12および図13を参照して説明する。図12は、実施例1に係る検索処理の手順を示すフローチャートであり、図13は、実施例1に係る検索処理内の重複領域判定処理の手順を示すフローチャートである。なお、図12および図13の例では、領域検索要求に含まれる位置情報を検索座標として説明する。リクエスト受付部131によって領域検索要求が受け付けられると、ツリー検索部133は、領域インデックスDB121に基づいて、ルートノードを選択するステップS11。そして、ツリー検索部133は、選択した選択ノードが葉ノードであるか否かを判定するステップS12。選択ノードが葉ノードでないと判定した場合ステップS12;No、ツリー検索部133は、選択ノードの子ノードに検索座標を含むものがあるか否かを、領域インデックスDB121を用いて判定するステップS13。一例として、ツリー検索部133は、領域インデックスDB121に基づいて、選択ノードの子ノードリストを読み出し、読み出した子ノードリストに含まれるそれぞれの子ノードの矩形領域を読み出す。そして、ツリー検索部133は、読み出したそれぞれの子ノードの矩形領域に、検索座標を含むものがあるか否かを判定する。選択ノードの子ノードに検索座標を含むものがあると判定した場合ステップS13;Yes、ツリー検索部133は、検索座標を含む子ノードを選択候補ノードに追加しステップS14、ステップS15に移行する。一方、選択ノードの子ノードに検索座標を含むものがないと判定した場合ステップS13;No、ツリー検索部133は、ステップS15に移行する。続いて、ツリー検索部133は、全ての選択候補ノードの検索を終えたか否かを判定するステップS15。全ての選択候補ノードの検索を終えていないと判定した場合ステップS15;No、ツリー検索部133は、選択候補ノード内の1つの未検索ノードを選択しステップS16、ステップS12に移行する。ステップS12では、選択ノードが葉ノードであると判定した場合ステップS12;Yes、ツリー検索部133は、選択した葉ノードが持つ領域データの内、検索座標を含むものがあるか否かを判定するステップS17。一例として、ツリー検索部133は、領域インデックスDB121に基づいて、葉ノードであるノードのデータリストを読み出し、読み出したデータリストに含まれる領域データへのポインタ、例えば領域IDを取り出す。そして、ツリー検索部133は、領域データDB122に基づいて、取り出した領域IDに対応する領域情報122cに検索座標を含むものがあるか否かを判定する。選択した葉ノードが持つ領域データの内、検索座標を含むものがないと判定した場合ステップS17;No、ツリー検索部133は、次の選択候補ノードを検索すべく、ステップS15に移行する。一方、選択した葉ノードが持つ領域データの内、検索座標を含むものがあると判定した場合ステップS17;Yes、ツリー検索部133は、該当領域データの内、内部包含領域および部分重複領域の数が最小の領域データを検索結果に追加するステップS18。一例として、ツリー検索部133は、領域データDB122に記憶された、該当領域データの領域ID122aに対応する内部包含122dおよび部分重複122fに基づいて、内部包含領域の数および部分重複領域の数を取得する。そして、ツリー検索部133は、該当領域データの領域ID122a毎に、取得した内部包含領域および部分重複領域の数の和を算出する。そして、ツリー検索部133は、該当領域データの領域ID122a毎に算出した和が最小のものを検索結果に追加する。ここで、領域インデックスDB121を用いた検索を終了し、重複領域判定処理に移行する。[重複領域判定処理の手順]重複領域判定処理では、外包領域結果追加部134が、検索結果に追加した該当領域データの外部包含領域の領域データ領域IDを、さらに検索結果に追加するステップS31。該当領域データの外部包含領域は、該当領域データの領域を包含するので、検索座標を含むか否かの検索処理を行うまでもなく、検索座標を含むからである。続いて、重複領域検索部135は、該当領域データの全内部包含領域の判定を終えたか否かを判定するステップS32。該当領域データの全内部包含領域の判定を終えていないと判定した場合ステップS32;No、重複領域検索部135は、該当領域データの内部包含領域の領域データを1つ選択するステップS33。そして、重複領域検索部135は、選択した内部包含領域が検索座標を含むか否かを判定するステップS34。選択した内部包含領域が検索座標を含むと判定した場合ステップS34;Yes、重複領域検索部135は、含むと判定した内部包含領域の領域IDを検索結果に追加しステップS35、ステップS32に移行する。一方、選択した内部包含領域が検索座標を含まないと判定した場合ステップS34;No、重複領域検索部135は、ステップS32に移行する。続いて、該当領域データの全内部包含領域の判定を終えたと判定した場合ステップS32;Yes、重複領域検索部135は、該当領域データの全部分重複領域の判定を終えたか否かを判定するステップS36。該当領域データの全部分重複領域の判定を終えていないと判定した場合ステップS36;No、重複領域検索部135は、該当領域データの部分重複領域の領域データを1つ選択するステップS37。そして、重複領域検索部135は、選択した部分重複領域が検索座標を含むか否かを判定するステップS38。選択した部分重複領域が検索座標を含むと判定した場合ステップS38;Yes、重複領域検索部135は、含むと判定した部分重複領域の領域IDを検索結果に追加しステップS39、ステップS36に移行する。続いて、該当領域データの全部分重複領域の判定を終えたと判定した場合ステップS36;Yes、重複領域検索部135は、ステップS19に移行する。そして、重複領域検索部135は、作成した検索結果を問合せ側へ返答すべく、レスポンス転送部132に出力するステップS19。その後、レスポンス転送部132は、検索結果を領域検索応答として領域検索要求の問合せ側へ送信する。ステップS15では、全ての選択候補ノードの検索を終えていると判定した場合ステップS15;Yes、ツリー検索部133は、選択ノードに検索座標を含むものがないので、検索結果無しとして問合せ側へ返答すべく、レスポンス転送部132に出力するステップS20。その後、レスポンス転送部132は、検索結果を領域検索応答として領域検索要求の問合せ側へ送信する。ところで、検索処理内の重複領域判定処理は、該当領域データの内部包含領域の中に検索座標を含むものがあると判定したとき、該当領域データにおける未判定の重複領域の数と、検索座標を含む内部包含領域における重複領域の数とを比較するようにしても良い。そして、重複領域判定処理は、比較した結果、検索対象である重複領域の数が小さい方の領域の重複領域の検索に切り替える。[重複領域判定処理の変形例の手順]そこで、重複領域判定処理の変形例として、該当領域データにおける未判定の重複領域の数と、検索座標を含む内部包含領域における重複領域の数とを比較し、検索対象である重複領域の数が小さい方の領域の重複領域の検索に切り替える場合の手順を説明する。図14は、実施例1に係る検索処理内の重複領域判定処理変形例の手順を示すフローチャートである。なお、図13に示す重複領域判定処理と同一の手順については同一符号を示すことで、その重複する動作の説明については簡略する。変形例の重複領域判定処理では、外包領域結果追加部134が、検索結果に追加した該当領域データの外部包含領域の領域データ領域IDを、さらに検索結果に追加するステップS31。続いて、重複領域検索部135は、該当領域データの全内部包含領域の判定を終えたか否かを判定するステップS32。該当領域データの全内部包含領域の判定を終えていないと判定した場合ステップS32;No、重複領域検索部135は、該当領域データの内部包含領域の領域データを1つ選択するステップS33。そして、重複領域検索部135は、選択した内部包含領域が検索座標を含むか否かを判定するステップS34。選択した内部包含領域が検索座標を含むと判定した場合ステップS34;Yes、重複領域検索部135は、選択した内部包含領域の検索対象の数が該当領域データの未判定の検索対象の数より小さいか否かを判定する。すなわち、重複領域検索部135は、選択した内部包含領域の内部包含領域数と部分重複領域数の和が該当領域データの未判定の内部包含領域数と部分重複領域数の和より小さいか否かを判定するステップS41。選択した内部包含領域の内部包含領域数と部分重複領域数の和が該当領域データの未判定の内部包含領域数と部分重複領域数の和より小さくない場合ステップS41;No、重複領域検索部135は、選択した内部包含領域の領域IDを、さらに検索結果に追加するステップS35。すなわち、重複領域検索部135は、検索対象の数が小さい方の該当領域データの重複領域を継続して検索する。そして、重複領域検索部135は、ステップS32に移行する。一方、選択した内部包含領域の内部包含領域数と部分重複領域数の和が該当領域データの未判定の内部包含領域数と部分重複領域数の和より小さい場合ステップS41;Yes、重複領域検索部135は、選択した内部包含領域を新しい該当領域データに設定するステップS42。すなわち、重複領域検索部135は、検索対象の数が小さい方の、選択した内部包含領域の重複領域の検索に切り替える。そして、重複領域検索部135は、検索結果をクリアしステップS43、ステップS31に移行する。続いて、該当領域データの全内部包含領域の判定を終えたと判定した場合ステップS32;Yes、重複領域検索部135は、該当領域データの全部分重複領域の判定を終えたか否かを判定するステップS36。該当領域データの全部分重複領域の判定を終えていないと判定した場合ステップS36;No、重複領域検索部135は、該当領域データの部分重複領域の領域データを1つ選択するステップS37。そして、重複領域検索部135は、選択した部分重複領域が検索座標を含むか否かを判定するステップS38。選択した部分重複領域が検索座標を含むと判定した場合ステップS38;Yes、重複領域検索部135は、含むと判定した部分重複領域の領域IDを検索結果に追加しステップS39、ステップS36に移行する。続いて、該当領域データの全部分重複領域の判定を終えたと判定した場合ステップS36;Yes、重複領域検索部135は、ステップS19に移行する。[重複領域設定処理の手順]次に、実施例1に係る重複領域設定処理の手順について、図15、図16を参照して説明する。図15は、実施例1に係る重複領域設定処理の手順を示すフローチャート1であり、図16は、実施例1に係る重複領域設定処理の手順を示すフローチャート2である。なお、リクエスト受付部131は、領域データDB122に追加する追加領域の領域情報を受け付け、受け付けた領域情報を重複領域設定部136に引き渡したものとする。すると、重複領域設定部136は、領域インデックスDB121に基づいて、ルートノードを選択するステップS51。そして、重複領域設定部136は、選択した選択ノードが葉ノードであるか否かを判定するステップS52。選択ノードが葉ノードであると判定した場合ステップS52;Yes、重複領域設定部136は、選択ノードにある領域データの内、追加領域と重なる領域データの領域を重複領域として抽出するステップS53。一例として、重複領域設定部136は、領域インデックスDB121に基づいて、選択ノードのデータリストを読み出し、読み出したデータリストに含まれる領域データへのポインタ、例えば領域IDを取り出す。そして、重複領域設定部136は、領域データDB122に基づいて、取り出した領域IDの内、追加領域と重なる部分がある領域IDを重複領域として抽出する。そして、重複領域設定部136は、ステップS56に移行する。一方、選択ノードが葉ノードでないと判定した場合ステップS52;No、重複領域設定部136は、領域インデックスDB121に基づいて、選択ノードの子ノードに追加領域と重なるものがあるか否かを判定するステップS54。選択ノードの子ノードに追加領域と重なるものがあると判定した場合ステップS54;Yes、重複領域設定部136は、重なった子ノードを選択候補ノードに加えステップS55、ステップS56に移行する。また、選択ノードの子ノードに追加領域と重なるものがないと判定した場合ステップS54;No、重複領域設定部136は、ステップS56に移行する。続いて、重複領域設定部136は、全ての選択候補ノードの検索を終えたか否かを判定するステップS56。全ての選択候補ノードの検索を終えていないと判定した場合ステップS56;No、重複領域設定部136は、選択候補ノード内の1つの未検索ノードを選択しステップS57、ステップS52に移行する。一方、全ての選択候補ノードの検索を終えたと判定した場合ステップS56;Yes、重複領域設定部136は、抽出済みの全重複領域の選択が終了したか否かを判定するステップS61。抽出済みの全重複領域の選択が終了したと判定した場合ステップS61;Yes、重複領域設定部136は、重複領域設定処理を終了する。一方、抽出済みの全重複領域の選択が終了していないと判定した場合ステップS61;No、重複領域設定部136は、抽出済みの重複領域から未選択の重複領域を1つ選択するステップS62。そして、重複領域設定部136は、選択した重複領域が追加領域の内側に完全に包含されるか否かを判定するステップS63。選択した重複領域が追加領域の内側に完全に含まれると判定した場合ステップS63;Yes、重複領域設定部136は、選択した重複領域を、追加領域の内部包含項目に追加するステップS64。例えば、重複領域設定部136は、選択した重複領域の領域IDを、領域データDB122の追加領域の領域IDに対応する内部包含122dに追加する。加えて、重複領域設定部136は、追加領域を、選択した重複領域の外部包含項目に追加するステップS65。例えば、重複領域設定部136は、追加領域の領域IDを、領域データDB122の選択した重複領域の領域IDに対応する外部包含122eに追加する。そして、重複領域設定部136は、ステップS61に移行する。一方、選択した重複領域が追加領域の内側に完全に含まれないと判定した場合ステップS63;No、重複領域設定部136は、追加領域が、選択した重複領域の内側に完全に含まれるか否かを判定するステップS66。追加領域が、選択した重複領域の内側に完全に含まれると判定した場合ステップS66;Yes、重複領域設定部136は、選択した重複領域を、追加領域の外部包含項目に追加するステップS67。例えば、重複領域設定部136は、選択した重複領域の領域IDを、領域データDB122の追加領域の領域IDに対応する外部包含122eに追加する。加えて、重複領域設定部136は、追加領域を、選択した重複領域の内部包含項目に追加するステップS68。例えば、重複領域設定部136は、追加領域の領域IDを、領域データDB122の選択した重複領域の領域IDに対応する内部包含122dに追加する。そして、重複領域設定部136は、ステップS61に移行する。一方、追加領域が、選択した重複領域の内側に完全に含まれないと判定した場合ステップS66;No、重複領域設定部136は、選択した重複領域を、追加領域の部分重複項目に追加するステップS69。例えば、重複領域設定部136は、選択した重複領域の領域IDを、領域データDB122の追加領域の領域IDに対応する部分重複122fに追加する。加えて、重複領域設定部136は、追加領域を、選択した重複領域の部分重複項目に追加するステップS70。例えば、重複領域設定部136は、追加領域の領域IDを、領域データDB122の選択した重複領域の領域IDに対応する部分重複122fに追加する。そして、重複領域設定部136は、ステップS61に移行する。[内部包含項目に追加する処理手順]次に、図16のステップS64およびステップS68に示した内部包含項目に追加する処理について、図17を参照して説明する。図17は、内部包含項目に追加する処理手順の一例を示すフローチャートである。なお、図17では、追加先とは、内部包含項目に追加される先の領域を意味し、追加対象とは、内部包含項目に追加する対象となる領域を意味する。図16のステップS64では、選択した重複領域が追加対象であり、追加領域が追加先である。図16のステップS68では、追加領域が追加対象であり、選択した重複領域が追加先である。重複領域設定部136は、追加先の領域データ領域IDにおいて検索対象である、内部包含領域および部分重複領域の数の和Iaを算出するステップS81。そして、重複領域設定部136は、追加対象の領域データ領域IDにおいて検索対象である、内部包含領域および部分重複領域の数の和Inを算出するステップS82。そして、重複領域設定部136は、双方の検索対象の数の差Ia-Inを算出するステップS83。続いて、重複領域設定部136は、追加対象の領域データにおける領域の面積Snと算出した検索対象の数の差との積を算出し、算出した値を評価値EnとするステップS84。ここで、評価値とは、検索を優先させるか否かを示す数値であり、数値が大きければ大きい程、検索をより優先させる。そして、重複領域設定部136は、追加先における内部包含項目内部包含122d内の評価値Enに該当する位置に追加対象の領域データ領域IDを追加するステップS85。例えば、重複領域設定部136は、領域データDB122の内部包含122d内に追加対象の領域IDを、評価値の大きい順となるように追加する。[実施例1の効果]上記実施例1によれば、領域データDB122は、複数の領域のそれぞれについて領域と重複する重複領域の情報を記憶する。そして、領域検索サーバ1は、領域インデックスDB121に記憶されたインデックス情報をツリー構造で表したインデックスツリーを用いて、所定の位置を含む領域を検索する。そして、領域検索サーバ1は、該位置を含む領域を検索できた場合、領域データDB122に基づいて、検索できた領域を示す検索領域と重複する重複領域のうち検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索する。さらに、領域検索サーバ1は、検索領域を包含する重複領域の情報とともに、検索できた領域の情報を出力する。かかる構成によれば、領域検索サーバ1は、インデックスツリーを用いて、所定の位置を含む領域を検索できた場合、インデックスツリーを用いた検索を終了し、検索できた検索領域の重複領域を用いた検索に移行する。さらに、領域検索サーバ1は、検索領域の重複領域を用いた検索のうち検索領域を包含する重複領域の検索を除外する。このため、領域検索サーバ1は、インデックスツリーを用いて所定の位置を含む領域を1個検索できれば、検索できた検索領域の重複領域を用いて該位置を含む領域を検索するので、該位置を含む領域の検索時間を高速化できる。加えて、領域検索サーバ1は、検索領域の重複領域のうち検索領域を包含する重複領域を検索対象から除くので、さらに該位置を含む領域の検索時間を高速化できる。また、上記実施例1によれば、領域データDB122は、複数の領域のそれぞれについて領域を包含する外部包含領域の情報、領域が包含する内部包含領域の情報および領域と部分的に重複する部分重複領域の情報を記憶する。そして、領域検索サーバ1は、領域データDB122に基づいて、検索領域と重複する内部包含領域および部分重複領域の中から該位置を含む領域を検索する。かかる構成によれば、領域検索サーバ1は、検索領域の重複領域のうち内部包含領域および部分重複領域の中から該位置を含む領域を検索するので、検索領域の全ての重複領域を検索対象とする場合と比べて検索効率を向上させることができる。ここで、検索領域の重複領域のうち内部包含領域および部分重複領域の中から領域検索が要求された位置を含む領域を検索する場合と、検索領域の全ての重複領域の中から該位置を含む領域を検索する場合との領域検索の検索回数の比較について説明する。1つの例として、検索領域の内部包含領域の数が30個、外部包含領域の数が30個、部分重複領域の数が80個の場合について説明する。かかる場合、検索領域の全ての重複領域の中から該位置を含む領域を検索する検索回数A1は、以下のようになる。A1=303080=140すなわち、A1は、該位置が内部包含領域に含まれるかを検索する30回と、該位置が外部包含領域に含まれるかを検索する30回と、該位置が部分重複領域に含まれるかを検索する80回とを加算した値140となる。一方、検索領域の重複領域のうち内部包含領域および部分重複領域の中から該位置を含む領域を検索する検索回数B1は、以下のようになる。B1=3080=110すなわち、B1は、該位置が内部包含領域に含まれるかを検索する30回と、該位置が部分重複領域に含まれるかを検索する80回とを加算した値110となる。検索回数B1は、検索回数A1と比べて、約20削減されている。よって、領域検索サーバ1は、外部包含領域を除外して検索するので、検索領域の全ての重複領域を検索対象とする場合と比べて検索効率を向上させることができる。また、上記実施例1によれば、領域検索サーバ1は、検索領域と重複するいずれかの内部包含領域の中から該位置を含む領域を新たに検索できたとする。この場合、領域検索サーバ1は、領域データDB122に基づいて、検索領域の残りの検索対象である内部包含領域の数および部分重複領域の数の和と、新たに検索できた領域の内部包含領域の数および部分重複領域の数の和とを比較する。そして、領域検索サーバ1は、比較の結果、新たに検索できた領域に係る和の数が検索領域に係る和の数より小さい場合、検索領域における検索処理を中止し、新たに検索できた領域における検索処理を実行する。かかる構成によれば、領域検索サーバ1は、検索領域より検索対象の数が小さい、新たに検索できた領域の重複領域の検索処理を改めて実行するので、検索領域の全ての重複領域を検索対象とする場合と比べて、さらに該位置を含む領域の検索時間を高速化できる。ここで、検索領域より検索対象の数が小さい、新たに検索できた領域の重複領域の検索処理を改めて実行する場合と、検索領域の全ての重複領域の検索処理を実行する場合との計算量の比較について説明する。1つの例として、検索領域の内部包含領域の数が30個、外部包含領域の数が80個の場合について説明する。なお、説明の便宜上、領域を2次元の矩形領域とし、要求された位置が当該領域に含まれるか否かを判定する計算回数を1つの領域毎に4回矩形領域の各頂点の座標との比較として4回とする。かかる場合に、検索領域の全ての重複領域の中から該位置を含むか否かの判定回数A ́1は、以下のようになる。A ́1=3080×4=440すなわち、A ́1は、該位置が内部包含領域に含まれるか否かを判定する30×4回と、該位置が外部包含領域に含まれるか否かを判定する80×4回とを加算した値440となる。一方、検索領域と重複する内部包含領域では、10番目に行われる内部包含領域の検索処理で該位置が含まれていたとする。つまり、10番目に検索処理される内部包含領域が新たに検索できた領域となる。また、10番目の内部包含領域が包含する内部包含領域の数が11個、部分重複領域の数が20個であるものとする。かかる場合に、仮に検索領域の残りの検索対象の数より新たに検索できた領域の検索対象の数の方が小さいとすると、新たに検索できた領域の重複領域の検索処理を改めて実行する検索回数B ́1は、以下のようになる。B ́1=1011×520×4=185すなわち、B ́1は、検索領域の内部包含領域のうち該位置が含まれていると判定される10番目に至るまでの内部包含領域毎の該位置を含むか否かの判定回数ならびに検索領域との検索対象の数値比較数を示す10×5回を算出する。そして、B ́1は、10番目の新たに検索できた内部包含領域が包含する内部包含領域毎の該位置を含むか否かの判定回数ならびに検索領域との検索対象の数値比較数を示す11×5回を算出する。さらに、B ́1は、10番目の新たに検索できた内部包含領域の部分重複領域毎の該位置を含むか否かの判定回数を示す20×4回を算出し、算出した全ての数を加算した値185回となる。計算量B ́1は、計算量A ́1と比べて、約60削減されている。よって、領域検索サーバ1は、検索領域の残りの検索対象の数より新たに検索できた領域の検索対象の数の方が小さい場合、新たに検索できた領域の重複領域の検索処理を改めて実行すれば、さらに該位置を含む領域の検索にかかる計算量が減るので、検索時間を高速化できる。また、上記実施例1によれば、領域検索サーバ1は、検索領域と重複する内部包含領域を、当該内部包含領域の面積の大きい順に選択し、選択した内部包含領域に該位置が含まれるか否かを検索する。かかる構成によれば、領域検索サーバ1は、検索領域と重複する内部包含領域の面積が大きければ、早期に内部包含領域に該位置が含まれる確率が高くなる。そうすると、領域検索サーバ1は、早期に内部包含領域に該位置が含まれれば、検索領域における検索処理を中止し、該位置が含まれた内部包含領域における検索処理に移行できるので、該位置を含む領域の検索時間を高速化できる。また、上記実施例1によれば、領域検索サーバ1は、検索領域と重複する内部包含領域について、当該内部包含領域が包含する内部包含領域の数および当該内部包含領域の部分重複領域の数の和を算出する。また、領域検索サーバ1は、検索領域と重複する内部包含領域の数および部分重複領域の数の和を算出する。そして、領域検索サーバ1は、双方の差分を算出する。さらに、領域検索サーバ1は、算出した差分の大きい順に検索領域と重複する内部包含領域を選択し、選択した内部包含領域に該位置が含まれるか否かを検索する。かかる構成によれば、領域検索サーバ1は、早期に内部包含領域に該位置が含まれていれば、検索領域の内部包含領域等の数と該位置が含まれた内部包含領域の内部包含領域等の数との差がより大きい。そうすると、領域検索サーバ1は、検索領域における検索処理を中止し、該位置が含まれた内部包含領域における検索処理に移行すれば、検索対象の数がより小さくなり検索処理が少なくなるので、該位置を含む領域の検索時間を高速化できる。ところで、実施例1に係る領域検索サーバ1では、インデックスツリーを用いて問合せ位置を含む領域を検索し、当該領域を検索できた場合、検索できた検索領域と重複する領域のうち検索領域を包含する領域を除くものを検索対象として検索する場合を説明した。しかしながら、領域検索サーバ1は、これに限定されず、問合せ位置を検索できた領域を次回の検索に活かすべく、前回検索できた領域として記録するようにしても良い。そこで、実施例2では、検索できた領域を前回検索できた領域として記録する領域検索サーバ2について説明する。[実施例2に係る領域検索サーバの構成]図18は、実施例2に係る領域検索サーバの構成を示す機能ブロック図である。なお、図1に示す領域検索サーバ1と同一の構成については同一符号を示すことで、その重複する構成および動作の説明については省略する。実施例1と実施例2とが異なるところは、記憶部12に前回位置DB201を追加した点にある。また、実施例1と実施例2とが異なるところは、制御部13に前回領域検索部202と前回領域記録部204とを追加した点にある。さらに、実施例1と実施例2とが異なるところは、制御部13のツリー検索部203を変更した点にある。前回位置DB201は、前回領域検索要求があったときに検索できた位置情報を当該要求元に対応付けて管理する。ここで、前回位置DB201のデータ構造の一例を、図19を参照して説明する。図19は、前回位置DB201のデータ構造の一例を示す図である。図19に示すように、前回位置DB201は、センサーID201a毎に、前回検索領域201bを対応付けて記憶する。センサーID201aは、領域検索要求の要求元のセンサーの識別IDを示す。前回検索領域201bは、前回領域検索要求があったときに検索できた領域情報を示す。例えば前回検索領域201bには、検索できた場合に検索できた領域の領域IDが記憶され、検索できなかった場合に未検出が記憶される。例えば、センサーID201aがSensor0001である場合、前回検索領域201bとして未検出と記憶している。また、センサーID201aがSensor0002である場合、前回検索領域201bとして領域ID00034と記憶している。図18に戻って、前回領域検索部202は、前回領域検索した際に検索できた領域を用いて、所定の位置情報を含む領域を検索する。例えば、前回領域検索部202は、リクエスト受付部131によって受け付けられた領域検索要求の中からセンサーIDおよび位置情報を取り出し、取り出したセンサーIDの前回検索領域を前回位置DB201に記憶しているか否かを判定する。また、前回領域検索部202は、センサーIDの前回検索領域を記憶している場合、領域検索要求の中から取り出した位置情報が前回検索領域に含まれるか否かを判定する。そして、前回領域検索部202は、取り出した位置情報が前回検索領域に含まれる場合、当該前回検索領域を検索結果に追加し、前回領域検索部202の検索処理を終了する。その後、外包領域結果追加部134および重複領域検索部135は、前回検索領域と重複する重複領域を検索対象として当該位置情報を含む重複領域を検索することとなる。ツリー検索部203は、位置情報が前回検索領域に含まれない場合、領域インデックスDB121を用いて、前回検索領域を領域データに持つ葉ノードの領域データの内、当該位置情報を含む領域データがあれば、検索できた領域データを検索結果に追加する。その後、外包領域結果追加部134および重複領域検索部135は、前回検索領域と重複する重複領域を検索対象として当該位置情報を含む重複領域を検索することとなる。また、ツリー検索部203は、前回検索領域を領域データに持つ葉ノードの領域データの内、当該位置情報を含む領域データがなければ、子ノードからルートノードへノードをボトムアップに順番に辿り、当該位置情報を含むノードを選択する。そして、ツリー検索部203は、選択したノードの子ノードに、当該位置情報を含むものがあるか否かを、領域インデックスDB121を用いて判定し、判定した結果、当該位置情報を含む子ノードを選択候補ノードとして追加する。そして、ツリー検索部203は、選択候補ノードとして追加されたノードを1つずつ選択し、選択したノードが葉ノードであれば、葉ノードの領域データの内、当該位置情報を含む領域データを検索結果に追加する。ここで、ツリー検索部203は、領域インデックスDB121を用いた検索を終了する。その後、外包領域結果追加部134および重複領域検索部135は、前回検索領域と重複する重複領域を検索対象として当該位置情報を含む重複領域を検索することとなる。前回領域記録部204は、領域検索要求があった要求元のセンサーIDに対応付けて検索結果を前回位置DB201に記録する。ここで、検索結果に検索できた領域IDが複数ある場合がある。かかる場合には、前回領域記録部204は、複数ある領域IDの内、領域IDが示す領域と重複する内部包含領域および部分重複領域の数が最小の領域IDを選択し、選択した領域IDを前回位置DB201に記録すれば良い。これにより、次回の領域検索要求で、当該領域検索要求の位置情報が前回記録された領域IDの領域に含まれていれば、続いて行われる当該領域と重複する重複領域に係る検索回数を減らせるからである。[検索処理の手順]次に、実施例2に係る検索処理の手順について、図20~図23を参照して説明する。図20~図22は、実施例2に係る検索処理の手順を示すフローチャートであり、図23は、検索処理内の重複領域判定処理の手順を示すフローチャートである。なお、図20~図23の例では、領域検索要求に含まれる位置情報を検索座標として説明する。また、図21のステップS111~S119は、実施例1における図12のステップS11~S18、S20と同様の動作となるので、その説明を簡略する。また、図23のステップS131~S139は、実施例1における図13のステップS31~S39と同様の動作となるので、その説明を簡略する。まず、リクエスト受付部131によって領域検索要求が受け付けられると、前回領域検索部202は、問合せのセンサーIDの前回データ前回検索領域を前回位置DB201に記憶しているか否かを判定するステップS101。問合せのセンサーIDの前回データを前回位置DB201に記憶していると判定した場合ステップS101;Yes、前回領域検索部202は、検索座標が前回データ内にあるか否かを判定するステップS102。検索座標が前回データ内にある場合ステップS102;Yes、前回領域検索部202は、前回データを該当データとして検索結果に追加するステップS103。そして、前回領域検索部202は、重複領域判定処理に遷移すべく、ステップSS131に移行する。ステップS101では、問合せのセンサーIDの前回データを前回位置DB201に記憶していないと判定した場合ステップS101;No、前回領域検索部202は、ノードをルートノードからトップダウンに辿る検索処理に移行すべく、ステップS111に移行する。ステップS102では、検索座標が前回データ内にない場合ステップS102;No、前回領域検索部202は、ノードをボトムアップに辿る検索処理に移行すべく、ステップS106に移行する。ステップS106では、ツリー検索部203が、領域インデックスDB121に基づいて、前回データを領域データとしてデータリストに持つ葉ノードまたは親ノードを選択するステップS106。そして、ツリー検索部203は、選択した選択ノードが検索座標を含むか否かを、領域インデックスDB121を用いて判定するステップS107。選択ノードが検索座標を含むと判定した場合ステップS107;Yes、ツリー検索部203は、さらにノードを選択ノードからトップダウンに辿る検索処理に移行すべく、ステップS121に移行する。一方、選択ノードが検索座標を含まないと判定した場合ステップS107;No、ツリー検索部203は、選択ノードがルートノードであるか否かを、領域インデックスDB121を用いて判定するステップS108。選択ノードがルートノードでなければステップS108;No、ツリー検索部203は、親ノードを検索すべく、ステップS106に移行する。一方、選択ノードがルートノードであればステップS108;Yes、ツリー検索部203は、検索結果無しとして問合せ側へ返答すべく、レスポンス転送部132に出力するステップS109。そして、前回領域記録部204は、問合せのセンサーIDに対応付けて未検出である旨を前回位置DB201に記録しステップS110、検索処理を終了する。[前回データを前回位置DB201に記憶していない場合の処理手順]ステップS111では、ツリー検索部203は、領域インデックスDB121に基づいて、ルートノードを選択するステップS111。そして、ツリー検索部203は、選択した選択ノードが葉ノードであるか否かを判定するステップS112。選択ノードが葉ノードでないと判定した場合ステップS112;No、ツリー検索部203は、選択ノードの子ノードに検索座標を含むものがあるか否かを、領域インデックスDB121を用いて判定するステップS113。選択ノードの子ノードに検索座標を含むものがあると判定した場合ステップS113;Yes、ツリー検索部203は、検索座標を含む子ノードを選択候補ノードに追加しステップS114、ステップS115に移行する。一方、選択ノードの子ノードに検索座標を含むものがないと判定した場合ステップS113;No、ツリー検索部203は、ステップS115に移行する。続いて、ツリー検索部203は、全ての選択候補ノードの検索を終えたか否かを判定するステップS115。全ての選択候補ノードの検索を終えていないと判定した場合ステップS115;No、ツリー検索部203は、選択候補ノード内の1つの未検索ノードを選択しステップS116、ステップS112に移行する。ステップS112では、選択ノードが葉ノードであると判定した場合ステップS112;Yes、ツリー検索部203は、選択した葉ノードが持つ領域データの内、検索座標を含むものがあるか否かを判定するステップS117。選択した葉ノードが持つ領域データの内、検索座標を含むものがないと判定した場合ステップS117;No、ツリー検索部203は、次の選択候補ノードを検索すべく、ステップS115に移行する。一方、選択した葉ノードが持つ領域データの内、検索座標を含むものがあると判定した場合ステップS117;Yes、ツリー検索部203は、該当領域データの内、内部包含領域および部分重複領域の数が最小の領域データを検索結果に追加するステップS118。ここで、ツリー検索部203は、領域インデックスDB121を用いた検索を終了し、重複領域判定処理に遷移すべく、ステップS131に移行する。ステップS115では、全ての選択候補ノードの検索を終えていると判定した場合ステップS115;Yes、ツリー検索部203は、選択ノードに検索座標を含むものがないので、検索結果無しとして問合せ側へ返答すべく、レスポンス転送部132に出力するステップS119。そして、前回領域記録部204は、問合せのセンサーIDに対応付けて未検出である旨を前回位置DB201に記録しステップS120、検索処理を終了する。[選択ノードが検索座標を含む場合の処理手順]ステップS121では、ツリー検索部203は、選択した選択ノードが葉ノードであるか否かを判定するステップS121。選択ノードが葉ノードでないと判定した場合ステップS121;No、ツリー検索部203は、選択ノードの子ノードに検索座標を含むものがあるか否かを、領域インデックスDB121を用いて判定するステップS122。選択ノードの子ノードに検索座標を含むものがあると判定した場合ステップS122;Yes、ツリー検索部203は、検索座標を含む子ノードを選択候補ノードに追加しステップS123、ステップS124に移行する。一方、選択ノードの子ノードに検索座標を含むものがないと判定した場合ステップS122;No、ツリー検索部203は、ステップS124に移行する。続いて、ツリー検索部203は、全ての選択候補ノードの検索を終えたか否かを判定するステップS124。全ての選択候補ノードの検索を終えていないと判定した場合ステップS124;No、ツリー検索部203は、選択候補ノード内の1つの未検索ノードを選択しステップS125、ステップS121に移行する。ステップS121では、選択ノードが葉ノードであると判定した場合ステップS121;Yes、ツリー検索部203は、選択した葉ノードが持つ領域データの内、検索座標を含むものがあるか否かを判定するステップS126。選択した葉ノードが持つ領域データの内、検索座標を含むものがないと判定した場合ステップS126;No、ツリー検索部203は、次の選択候補ノードを検索すべく、ステップS124に移行する。一方、選択した葉ノードが持つ領域データの内、検索座標を含むものがあると判定した場合ステップS126;Yes、ツリー検索部203は、該当領域データの内、内部包含領域および部分重複領域の数が最小の領域データを検索結果に追加するステップS127。ここで、ツリー検索部203は、領域インデックスDB121を用いた検索を終了し、重複領域判定処理に遷移すべく、ステップS131に移行する。ステップS124では、全ての選択候補ノードの検索を終えたと判定した場合ステップS124;Yes、ツリー検索部203は、選択ノードに検索座標を含むものがないので、さらに親ノードから検索すべく、ステップS106に移行する。[重複領域設定処理の手順]重複領域判定処理では、外包領域結果追加部134が、検索結果に追加した該当領域データの外部包含領域の領域データ領域IDを、さらに検索結果に追加するステップS131。該当領域データの外部包含領域は、該当領域データの領域を包含するので、検索座標を含むか否かの検索処理を行うまでもなく、検索座標を含むからである。続いて、重複領域検索部135は、該当領域データの全内部包含領域の判定を終えたか否かを判定するステップS132。該当領域データの全内部包含領域の判定を終えていないと判定した場合ステップS132;No、重複領域検索部135は、該当領域データの内部包含領域の領域データを1つ選択するステップS133。そして、重複領域検索部135は、選択した内部包含領域が検索座標を含むか否かを判定するステップS134。選択した内部包含領域が検索座標を含むと判定した場合ステップS134;Yes、重複領域検索部135は、含むと判定した内部包含領域の領域IDを検索結果に追加しステップS135、ステップS132に移行する。一方、選択した内部包含領域が検索座標を含まないと判定した場合ステップS134;No、重複領域検索部135は、ステップS132に移行する。続いて、該当領域データの全内部包含領域の判定を終えたと判定した場合ステップS132;Yes、重複領域検索部135は、該当領域データの全部分重複領域の判定を終えたか否かを判定するステップS136。該当領域データの全部分重複領域の判定を終えていないと判定した場合ステップS136;No、重複領域検索部135は、該当領域データの部分重複領域の領域データを1つ選択するステップS137。そして、重複領域検索部135は、選択した部分重複領域が検索座標を含むか否かを判定するステップS138。選択した部分重複領域が検索座標を含むと判定した場合ステップS138;Yes、重複領域検索部135は、含むと判定した部分重複領域の領域IDを検索結果に追加しステップS139、ステップS136に移行する。続いて、該当領域データの全部分重複領域の判定を終えたと判定した場合ステップS136;Yes、重複領域検索部135は、ステップS104に移行する。そして、重複領域検索部135は、作成した検索結果を問合せ側へ返答すべく、レスポンス転送部132に出力するステップS104。そして、前回領域記録部204は、重複領域検索部135によって作成された検索結果の内1つの領域IDを問合せのセンサーIDに対応付けて前回位置DB201に記録しステップS105、検索処理を終了する。なお、検索処理内の重複領域判定処理は、該当領域データの内部包含領域の中に検索座標を含むものがあると判定したとき、該当領域データにおける未判定の重複領域の数と、検索座標を含む内部包含領域における重複領域の数とを比較するようにしても良い。そして、重複領域判定処理は、比較した結果、検索対象である重複領域の数が小さい方の領域の重複領域の検索に切り替える。かかる重複領域判定処理の変形例は、実施例1における図14で説明した処理と同様であるので、その説明を省略する。[実施例2の効果]上記実施例2によれば、領域検索サーバ2は、所定の位置を含む領域検索要求を取得すると、該位置が前回検索できた領域に含まれるか否かを判定する。そして、領域検索サーバ2は、判定の結果、該位置が前回検索できた領域に含まれると判定された場合、領域データDB122に基づいて、検索できた領域を示す検索領域と重複する重複領域のうち検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索する。かかる構成によれば、領域検索サーバ2は、次回の領域検索を前回検索できた領域から行うこととした。仮に、領域検索要求を行う要求元が領域の大きさに対して小さい移動距離しか移動しないような場合には、次回の領域検索要求の位置が前回検索できた領域の近傍にある可能性が高くなる。このため、領域検索サーバ2は、前回検索できた領域から次回の領域検索を行うことにより次回の位置を含む領域検索の検索時間を高速化できる。また、上記実施例2によれば、領域検索サーバ2は、所定の位置を含む領域検索要求を取得すると、該位置が前回検索できた領域に含まれるか否かを判定する。そして、領域検索サーバ2は、判定の結果、該位置が前回検索できた領域に含まれないと判定された場合、ツリー構造を形成するノードの中で、含まれないと判定された領域を含むインデックスの葉ノードから該位置を含む領域を検索する。そして、領域検索サーバ2は、該位置を含む領域を検索できた場合、検索できた領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索する。かかる構成によれば、領域検索サーバ2は、次回の領域検索を前回検索できた領域から行うこととした。仮に、領域検索要求を行う要求元が領域の大きさに対して小さい移動距離しか移動しないような場合には、次回の領域検索要求の位置が前回検索できた領域の近傍にある可能性が高くなる。このため、領域検索サーバ2は、次回の領域検索要求の位置が前回検索できた領域に含まれていなくても、当該位置が前回検索できた領域の近傍を含むインデックスの葉ノードから次回の領域検索を行うことにより次回の位置を含む領域検索の検索時間を高速化できる。[プログラムなど]なお、前回位置DB201は、センサーID201aと前回検索領域201bとを対応付けるものとして説明した。しかしながら、前回位置DB201は、センサーID201aを、例えば、領域検索を要求する端末装置の装置IDに代えても良いし、領域検索を要求する携帯電話の携帯電話番号に代えても良い。すなわち、センサーID201aに相当するIDは、ユースケース毎に変えることができる。また、領域検索サーバ1は、既知のパーソナルコンピュータ、ワークステーションなどの情報処理装置に、上記したツリー検索部133、外包領域結果追加部134などの各機能を搭載することによって実現することができる。また、領域検索サーバ2は、既知のパーソナルコンピュータ、ワークステーションなどの情報処理装置に、上記した前回領域検索部202、ツリー検索部203などの各機能を搭載することによって実現することができる。また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散統合の具体的態様は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散統合して構成することができる。例えば、外包領域結果追加部134と重複領域検索部135とを1個の部として統合しても良い。一方、ツリー検索部133を、葉ノードにおける検索処理と葉ノード以外のノードにおける検索処理とに分散しても良い。また、領域データDB122などの記憶部を領域検索サーバ1、2の外部装置としてネットワーク経由で接続するようにしても良い。また、上記実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図1に示した領域検索サーバ1と同様の機能を実現する領域検索プログラムを実行するコンピュータの一例を説明する。図24は、領域検索プログラムを実行するコンピュータの一例を示す図である。図24に示すように、コンピュータ200は、各種演算処理を実行するCPU201と、ユーザからのデータの入力を受け付ける入力装置202と、ディスプレイ203を有する。また、コンピュータ200は、記憶媒体からプログラム等を読取る読み取り装置204と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインタフェース装置205とを有する。また、コンピュータ200は、各種情報を一時記憶するRAM206と、ハードディスク装置207を有する。そして、各装置201~207は、バス208に接続される。ハードディスク装置207は、領域検索プログラム207a、重複領域設定プログラム207bを記憶する。CPU201は、各プログラム207a~207bを読み出して、RAM206に展開する。領域検索プログラム207aは、領域検索プロセス206aとして機能する。重複領域設定プログラム207bは、重複領域設定プロセス206bとして機能する。例えば、領域検索プロセス206aは、ツリー検索部133、外包領域結果追加部134および重複領域検索部135に対応する。重複領域設定プロセス206bは、重複領域設定部136に対応する。なお、各プログラム207a~207bについては、必ずしも最初からハードディスク装置207に記憶させておかなくてもよい。例えば、コンピュータ200に挿入されるフレキシブルディスクFD、CD-ROM、DVDディスク、光磁気ディスク、ICカードなどの可搬用の物理媒体に各プログラムを記憶させておく。そして、コンピュータ200がこれらから各プログラム207a~207bを読み出して実行するようにしても良い。以上の実施例1~2を含む実施形態に関し、さらに以下の付記を開示する。付記1コンピュータが領域を検索する際に用いられるインデックス情報であって複数の領域を含む領域情報とともに前記領域を管理するインデックス情報をツリー構造で表したインデックスツリーを用いて、所定の位置を含む領域を検索し、該位置を含む領域を検索できた場合、複数の領域のそれぞれについて領域と重複する重複領域の情報を記憶した記憶部に基づいて、検索できた領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索し、前記検索領域を包含する重複領域の情報とともに、検索できた領域の情報を出力することを実行する領域検索方法。付記2該位置を含む領域を検索する処理は、複数の領域のそれぞれについて領域を包含する外部包含領域の情報、領域が包含する内部包含領域の情報および領域と部分的に重複する部分重複領域の情報を記憶した前記記憶部に基づいて、前記検索領域と重複する内部包含領域および部分重複領域の中から該位置を含む領域を検索することを特徴とする付記1に記載の領域検索方法。付記3該位置を含む領域を検索する処理は、前記検索領域と重複するいずれかの内部包含領域の中から該位置を含む領域を新たに検索できた場合、前記記憶部に基づいて、前記検索領域の残りの検索対象である内部包含領域の数および部分重複領域の数の和と、新たに検索できた領域の内部包含領域の数および部分重複領域の数の和とを比較し、前記比較する処理によって新たに検索できた領域に係る和の数が前記検索領域に係る和の数より小さい場合、前記検索領域における検索処理を中止し、新たに検索できた領域における検索処理を実行することを特徴とする付記2に記載の領域検索方法。付記4該位置を含む領域を検索する処理は、前記検索領域と重複する内部包含領域を、当該内部包含領域の面積の大きい順に選択し、選択した内部包含領域に該位置が含まれるか否かを検索することを特徴とする付記2または付記3に記載の領域検索方法。付記5該位置を含む領域を検索する処理は、前記検索領域と重複する内部包含領域について、当該内部包含領域が包含する内部包含領域の数および当該内部包含領域の部分重複領域の数の和と、前記検索領域と重複する内部包含領域の数および部分重複領域の数の和との差分を算出し、算出した差分の大きい順に前記検索領域と重複する内部包含領域を選択し、選択した内部包含領域に該位置が含まれるか否かを検索することを特徴とする付記2または付記3に記載の領域検索方法。付記6所定の位置を含む領域の問合せ要求を取得すると、該位置が前回検索できた領域に含まれるか否かを判定し、判定の結果、該位置が前回検索できた領域に含まれると判定された場合、前記記憶部に基づいて、含まれると判定された領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索することを特徴とする付記1に記載の領域検索方法。付記7前記判定の結果、該位置が前回検索できた領域に含まれないと判定された場合、前記ツリー構造を形成するノードの中で、含まれないと判定された領域を含むインデックス情報の葉ノードから該位置を含む領域を検索し、該位置を含む領域を検索できた場合、検索できた領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索することを特徴とする付記6に記載の領域検索方法。付記8コンピュータに、領域を検索する際に用いられるインデックス情報であって複数の領域を含む領域情報とともに前記領域を管理するインデックス情報をツリー構造で表したインデックスツリーを用いて、所定の位置を含む領域を検索し、該位置を含む領域を検索できた場合、複数の領域のそれぞれについて領域と重複する重複領域の情報を記憶した記憶部に基づいて、検索できた領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索し、前記検索領域を包含する重複領域の情報とともに、検索できた領域の情報を出力する各処理を実行させることを特徴とする領域検索プログラム。付記9複数の領域のそれぞれについて領域と重複する重複領域の情報を記憶した記憶部と、領域を検索する際に用いられるインデックス情報であって複数の領域を含む領域情報とともに前記領域を管理するインデックス情報をツリー構造で表したインデックスツリーを用いて、所定の位置を含む領域を検索する第1の検索部と、前記第1の検索部によって該位置を含む領域を検索できた場合、前記記憶部に基づいて、検索できた領域を示す検索領域と重複する重複領域のうち前記検索領域を包含する重複領域を除く重複領域の中から該位置を含む領域を検索する第2の検索部と、前記検索領域を包含する重複領域の情報とともに、前記第2の検索部によって検索できた領域の情報を出力する出力部とを有することを特徴とする情報処理装置。