(57)【要約】  指定した位置に対応する情報を提供する場合に、従来技術では、同一位置に複数の異なる情報提供エリアを定義できない、また、エリアを定義するデータを４分木データで格納する場合には、対象となるすべてのエリアを同一の解像度で格納する必要があるために格納方法の最適化が図れない、などの問題が存在する。  「R*-tree」に基づく多段のインデックス構造を利用し、最小包囲矩形（ＭＢＲ）で表現された各エリアの中から候補となるエリアを高速に検索する。さらに、検索されたエリアから改良された４分木データを利用してエリアを特定し、ユーザおよびサービス提供者に関する情報に基づき、特定されたエリアに関連するサービスや情報を提供する。【特許請求の範囲】
【請求項１】
エリア管理データ構造、及び、エリア関連情報格納部を有し、任意の位置情報に対応するエリア関連情報を出力する装置であって、
前記エリア管理データ構造は、エリアを包含するエリア集合に対応するルートノード、中間ノード、及び、葉ノードを含むインデックスデータ構造、並びに、前記葉ノードに対応するデータ格納部を有し、また、
前記エリア関連情報格納部は、前記エリアに対応するエリア関連情報を格納し、以下の（ａ）から（ｄ）の手段を有する装置、
（ａ）前記位置情報を受け入れる手段、
（ｂ）前記インデックスデータ構造を検索し前記位置情報に対応する前記葉ノードを特定する手段、
（ｃ）前記特定された葉ノードに対応する前記データ格納部を検索し、前記位置情報に対応する前記エリアを特定する手段、
及び、
（ｄ）前記エリア関連情報格納部を検索し前記特定されたエリアに対応するエリア関連情  報を出力する手段。
【請求項２】
前記エリアが近似多角形で近似され、
前記インデックスデータ構造の前記葉ノードは前記近似多角形の第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記エリアの近似多角形の４分木データに基づいて構成される
請求の範囲第１項に記載の装置。
【請求項３】
前記エリアが一つ以上の矩形で近似され、
前記インデックスデータ構造の前記葉ノードは前記一つ以上の矩形からなる第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記エリアの矩形に基づいて構成される
請求の範囲第１項に記載の装置。
【請求項４】
前記エリアが一つ以上の直線からなる折れ線で近似され、
前記インデックスデータ構造の前記葉ノードは前記直線の第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記一つ以上の直線に基づいて構成される
請求の範囲第１項に記載の装置。
【請求項５】
前記エリアが曲線で近似され、さらに、前記曲線が一つ以上の直線からなる折れ線で近似され、
前記インデックスデータ構造の前記葉ノードは前記直線の第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記一つ以上の直線に基づいて構成される
請求の範囲第１項に記載の装置。
【請求項６】
前記エリアがスプライン補間によって曲線近似され、
前記インデックスデータ構造の前記葉ノードは前記スプライン補間された曲線のの第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記スプライン補間された曲線に基づいて構成される
請求の範囲第１項に記載の装置。
【請求項７】
サービス利用者の指定する一つ以上のエリア属性に基づき収集されたエリア情報から構築されたエリア属性に基づくエリア管理データ構造、及び、エリア関連情報格納部を有し、任意の位置情報に対応するエリア関連情報を出力する装置であって、
前記エリア属性に基づくエリア管理データ構造は、前記指定された一つ以上のエリア属性に基づき収集されたエリアを包含するエリア集合に対応するルートノード、中間ノード、及び、葉ノードを含むエリア属性に基づくインデックスデータ構造、並びに、前記葉ノードに対応するデータ格納部を有し、また、
前記エリア関連情報格納部は、前記エリアに対応するエリア関連情報を格納し、以下の（ａ）から（ｄ）の手段を有する装置、
（ａ）前記位置情報を受け入れる手段、
（ｂ）前記エリア属性に基づくインデックスデータ構造を検索し前記位置情報に対応する前記葉ノードを特定する手段、
（ｃ）前記特定された葉ノードに対応する前記データ格納部を検索し、前記位置情報に対応する前記エリアを特定する手段、及び、
（ｄ）前記エリア関連情報格納部を検索し前記特定されたエリアに対応するエリア関連情報を出力手段。
【請求項８】
二つ以上の前記インデックスデータ構造、及び、最下位のインデックスデータ構造のデータ格納部を含み、上位のインデックスデータ構造の葉ノードで特定されるエリアが、下位のインデックスデータ構造の前記ルートノードに対応する構造を有し、
さらに、
（ａ）前記上位インデックスデータ構造を検索し前記位置情報に対応する前記葉ノードを特定する手段、
（ｂ）前記特定された葉ノードに対応する下位のインデックスデータ構造を検索し前記位置情報に対応する葉ノードを特定する手段、及び、
（ｃ）最下位のインデックスデータ構造の葉ノードが得られるまで繰り返し、前記得られた最下位のインデックスデータ構造の葉ノードに対応する前記データ格納部を検索し、前記位置情報に対応する前記エリアを特定する手段
を有する請求の範囲第１〜７項のいずれかに記載の装置。
【請求項９】
さらに、前記インデックスデータ構造を構築するための第一のエリアの空間座標解像度が、他のインデックスデータ構造を構築するための第二のエリアの空間座標解像度から独立に設定されている
請求の範囲第８項に記載の装置。
【請求項１０】
さらに、
（ａ）下位のインデックスデータ構造の第一のエリア情報の変更要求を受け入れる手段、
（ｂ）前記第一のエリアに対応する上位インデックスデータ構造の第二のエリアが存在するか否か判断する手段、
（ｃ）前記第二のエリアが存在しない場合、前記第一のエリアに対応する上位インデックスデータ構造の第二のエリアを追加する手段、及び、
（ｄ）前記第二のエリアが存在するが、前記第一のエリアの全てを包含しない場合、全てを包含するように前記第二のエリアを拡張する手段
を有する請求の範囲第８項に記載の装置。
【請求項１１】
さらに、
（ａ）下位のインデックスデータ構造の第一のエリア情報の変更要求、及び、前記第一のエリアの属性を受け入れる手段、及び、
（ｂ）前記第一のエリアの属性に対応する下位のエリア属性に基づくインデックスデータ構造が存在している場合には、前記第一のエリア情報の変更を行い、また下位のエリア属性に基づくインデックスデータ構造を削除する手段、
を有する請求の範囲第８項に記載の装置。
【請求項１２】
前記エリア関連情報を出力する手段は、さらに、前記サービス利用者に関する情報、サービス提供者、又は、前記エリアの属性に関する情報のうち少なくとも一つを考慮して検索する
請求の範囲第１〜１１項のいずれかに記載の装置。
【請求項１３】
エリア管理データ構造、及び、エリア関連情報格納部を有するプログラムであって、
前記エリア管理データ構造は、エリアを包含するエリア集合に対応するルートノード、中間ノード、及び、葉ノードを含むインデックスデータ構造、並びに、前記葉ノードに対応するデータ格納部を有し、
前記エリア関連情報格納部は、前記エリアに対応するエリア関連情報を格納し、
さらに、（ａ）前記位置情報を受け入れるステップ、
（ｂ）前記インデックスデータ構造を検索し前記位置情報に対応する前記葉ノードを特定するステップ、
（ｃ）前記特定された葉ノードに対応する前記データ格納部を検索し、前記位置情報に対応する前記エリアを特定するステップ、及び、
（ｄ）前記エリア関連情報格納部を検索し前記特定されたエリアに対応するエリア関連情報を出力するステップ
をコンピュータを制御して実行させ、任意の位置情報に対応するエリア関連情報を出力する
プログラム。
【請求項１４】
サービス利用者の指定する一つ以上のエリア属性に基づき収集されたエリア情報から構築されたエリア属性に基づくエリア管理データ構造、及び、エリア関連情報格納部を有するプログラムであって、
前記エリア属性に基づくエリア管理データ構造は、前記指定された一つ以上のエリア属性に基づき収集されたエリアを包含するエリア集合に対応するルートノード、中間ノード、及び、葉ノードを含むエリア属性に基づくインデックスデータ構造、並びに、前記葉ノードに対応するデータ格納部を有し、
前記エリア関連情報格納部は、前記エリアに対応するエリア関連情報を格納し、さらに、（ａ）前記位置情報を受け入れるステップ、
（ｂ）前記エリア属性に基づくインデックスデータ構造を検索し前記位置情報に対応する前記葉ノードを特定するステップ、
（ｃ）前記特定された葉ノードに対応する前記データ格納部を検索し、前記位置情報に対応する前記エリアを特定するステップ、及び、
（ｄ）前記エリア関連情報格納部を検索し前記特定されたエリアに対応するエリア関連情報を出力ステップ
をコンピュータを制御して実行させ、任意の位置情報に対応するエリア関連情報を出力する
プログラム。
【請求項１５】
二つ以上の前記インデックスデータ構造、及び、最下位のインデックスデータ構造のデータ格納部を含むプログラムであって、
上位のインデックスデータ構造の葉ノードで特定されるエリアが、下位のインデックスデータ構造の前記ルートノードに対応する構造を有し、さらに、
（ａ）前記上位インデックスデータ構造を検索し前記位置情報に対応する前記葉ノードを特定するステップ、
（ｂ）前記特定された葉ノードに対応する下位のインデックスデータ構造を検索し前記位置情報に対応する葉ノードを特定するステップ、及び、
（ｃ）最下位のインデックスデータ構造の葉ノードが得られるまで繰り返し、前記得られた最下位のインデックスデータ構造の葉ノードに対応する前記データ格納部を検索し、前記位置情報に対応する前記エリアを特定するステップ
をコンピュータを制御して実行させる
請求の範囲第１３または１４項に記載のプログラム。
【請求項１６】
エリア管理データ構造、及び、エリア関連情報格納部を有する装置において、前記エリア管理データ構造は、エリアを包含するエリア集合に対応するルートノード、中間ノード、及び、葉ノードを含むインデックスデータ構造、並びに、前記葉ノードに対応するデータ格納部を有し、また、
前記エリア関連情報格納部は、前記エリアに対応するエリア関連情報を格納し、以下の（ａ）から（ｄ）のステップによって、任意の位置情報に対応するエリア関連情報を出力する方法、
（ａ）前記位置情報を受け入れるステップ、
（ｂ）前記インデックスデータ構造を検索し前記位置情報に対応する前記葉ノードを特定するステップ、
（ｃ）前記特定された葉ノードに対応する前記データ格納部を検索し、前記位置情報に対応する前記エリアを特定するステップ、及び、
（ｄ）前記エリア関連情報格納部を検索し前記特定されたエリアに対応するエリア関連情報を出力するステップ。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、所定の位置に関連するサービス等が提供される場合に、所定の位置から当該位置に関連するサービス等を検索する装置・方法・プログラムに関する。
【背景技術】
【０００２】
ユーザのいる位置情報に関連したサービスを提供する方法として様々な方法が存在する。
例えば、NTTドコモの「iモード」対応電話機で利用できる位置情報サービスである「ｉ-エリア」がある。
これは基地局からの携帯電話の現在地情報により全国を数百ヶ所余りに分割したエリアごとの情報を受けることができる。
このように分割したエリアごとの情報提供が可能なため、エリアに特化した天気予報、地図、交通情報、グルメや買い物情報などといったサービスが存在する。
同様のサービスとしてauのGPS位置情報サービス「eznavigation」、Jフォンの地図情報サービス「J-Navi」、NTTドコモのPHSの「いまどこサービス」、「mopera位置情報サービス」、DDIポケットの「位置情報サービス」、東京電話アステル(TTNet)の「Pナビ」などが存在する。【０００３】
しかしながら、これらは、広範囲のエリアに共通する情報、例えば、当該エリアの天気予報、地図、交通情報などは提供することが出来る。
しかし、これらは、携帯電話の基地局の情報をもとに、その基地局がどのエリアに属するかという位置情報によって情報を提供する。
この位置情報は、緯度経度のような詳細なポイントを示す情報ではなく、通信事業者が規定したエリアコードのみである。また、基地局の位置に対応する位置情報を利用するため、場合によっては、ユーザの利用場所と異なることもある。
さらに、事前に規定されたエリアのみを利用するため、より狭いエリアに特化したサービス情報の提供は出来ない。
また、携帯端末を所持したモバイルユーザに対して、位置・時間・数量限定で情報アクセスを許可するシステムが開発されている（http://www.spacetag.jp/）。
しかし、当該システムでも、情報の有効空間として中心座標（緯度・経度）と有効半径により定められる円形を利用しているため、より複雑な形状のエリアに対して情報・サービスを提供することが困難であるという問題がある。
また、時空間情報のみを用いて（時空間をインデックスとして）情報を管理しているため、実空間の具体的なオブジェクトに対して明示的に情報をリンクすることができないという問題点が残されている。【０００４】
さらに、ＧＰＳや、携帯電話のみならず、様々な無線通信デバイスを使用して得られる正確な位置情報に基づき、小まめなサービス及びそれらに関連する情報を提供することも検討されている。
例えば、米国特許6,212,392号において開示されている方法では、携帯電話を利用する無線通信システムにおいて、セルに対応付けられた位置情報を利用している。
この方法は、無線通信デバイスが指定エリア内にあるか否かを判定する方法であり、４分木データに基づくエリア表現を用いて、サービス提供者がエリアの定義および管理を行うことが出来る。
しかし当該方法ではデータ構造のもつ制約から、エリアの重複が許されないため、同一地点（領域）に複数の異なるサービスを割当てることができないという欠点がある。
【特許文献１】米国特許6,212,392号
【非特許文献１】ｉ-エリア
【非特許文献２】http://www.spacetag.jp/
【非特許文献３】H. Samet. The Quadtree and Related Hierarchical Data Structures. ACM Computing Surveys, Vol. 16, No. 2, 1984
【非特許文献４】N. Beckmann, H.-P. Kriegel, R. Schneider and B. Seeger. TheR*-tree: An Efficient and Robust Access Method for Points and Rectangles. Proceedings of ACM SIGMOD, pp.322-331, 1990
【非特許文献５】V. Gaede and O. Gunther. Multidimensional Access Methods. ACM Computing Surveys, Vol. 30, No. 2, June 1998
【非特許文献６】U.S. Patent Document. Method for determining if the location of a wireless communication device is within a specified area. Patent No. US 6,212,392 B1
【非特許文献７】A. Guttman. R-Trees: a dynamic index structure for spatial searching. Proceedings of the 13th ACM SIGMOD Conference, pp.47-57, 1984
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、以上のような従来技術に存在する問題を解決することである。以上の問題点をまとめると以下のようになる。
（１）複数の異なるサービス提供者が提供するエリア情報を統一的に管理すると、同一地域に複数の異なるサービスが割当てられる場合がある。また、同一のサービス提供者が複数のサービスを定義したいという要求も発生する。従来のエリア（空間データ）管理手法として用いられている４分木データでは、同一地点に複数の異なるサービス提供エリアを定義することができない、また、同一エリアに存在する複数のサービス情報を扱うことができない、という問題がある。
（２）４分木データでは事前に表現レベル数を指定する必要があるため、対象となるすべてのエリアを同一の解像度、すなわち同一の近似精度で表現することになる。サービスの種類によってはそれほど高精度で近似する必要がないことが在るにもかかわらず、４分木を用いてエリア情報を管理する場合にはサービスエリアごとに異なる表現レベルを設定できないという問題がある。【０００６】
所定の位置に依存したサービスおよび情報提供の実現において、
（１）サービス提供範囲（エリア）の設定・更新・変更などの管理、及び、
（２）モバイルユーザ（携帯端末）の位置とエリアの対応付け、
は重要であり必要不可欠な技術である。
本発明では、サービス提供エリアを柔軟かつ容易に管理するために多次元インデックスの１つである「R*-tree」に基づくデータ構造を用いたエリア（ｎ次元空間でも良い）表現を構築する方法を提供する。
また、個々のエリア表現に４分木（Quadtree）データ構造等を利用し、モバイルユーザの所持するGPSや携帯電話などの端末から得られた位置情報から、そのユーザが事前に定義されたどのサービス提供エリアに存在するかを高速に探索し、そのエリアを一意に同定する識別子を得る方法を示す。
さらに、得られたエリア識別子に基づき、ユーザのプロファイル情報やサービス提供者に関する情報、その他に隣接エリアとの空間的な位置関係なども参照しながら、エリアに関連付けられた様々なサービスやオブジェクトに関する情報を選択的に探索し、ユーザに提示する方法を提供する。
【課題を解決するための手段】
【０００７】
１．請求項１：
請求項１では、エリア管理データ構造、及び、エリア関連情報格納部を有し、任意の位置情報に対応するエリア関連情報を出力する装置を開示している。ここで、エリア管理データ構造は、エリアを包含するエリア集合に対応するルートノード、中間ノード、及び、葉ノードを含むインデックスデータ構造、並びに、葉ノードに対応するデータ格納部を有し、また、エリア関連情報格納部は、エリアに対応するエリア関連情報を格納し、以下の（ａ）から（ｄ）の手段を有している。
（ａ）前記位置情報を受け入れる手段、
（ｂ）前記インデックスデータ構造を検索し前記位置情報に対応する前記葉ノードを特定する手段、
（ｃ）前記特定された葉ノードに対応する前記データ格納部を検索し、前記位置情報に対応する前記エリアを特定する手段、
及び、
（ｄ）前記エリア関連情報格納部を検索し前記特定されたエリアに対応するエリア関連情報を出力する手段。【０００８】
２．請求項２：
請求項２では、請求項１の装置において、エリアが近似多角形で近似されている場合について開示している。ここで、インデックスデータ構造の葉ノードは前記近似多角形の第一の最小包囲矩形に基づくデータを含み、また、中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含んでいる。データ格納部は前記エリアの近似多角形の４分木データに基づいて構成されている。【０００９】
３．請求項３：
請求項３では、請求項１の装置において、エリアが一つ以上の矩形で近似されている場合について開示している。ここで、インデックスデータ構造の葉ノードは一つ以上の矩形からなる第一の最小包囲矩形に基づくデータを含み、また、中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含んでいる。データ格納部はエリアの矩形に基づいて構成されている。【００１０】
４．請求項４：
請求項４では、請求項１の装置において、前記エリアが一つ以上の直線からなる折れ線で近似されている場合について開示している。ここで、インデックスデータ構造の葉ノードは直線の第一の最小包囲矩形に基づくデータを含み、また、中間ノードは一つ以上の第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含んでいる。データ格納部は一つ以上の直線に基づいて構成されている。【００１１】
５．請求項５：
請求項５では、請求項１の装置において、エリアが曲線で近似され、さらに、この曲線が一つ以上の直線からなる折れ線で近似されている場合について開示している。ここで、インデックスデータ構造の葉ノードは直線の第一の最小包囲矩形に基づくデータを含み、また、中間ノードは一つ以上の第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含んでいる。データ格納部は一つ以上の直線に基づいて構成されている。【００１２】
６．請求項６：
請求項６では、請求項１の装置において、エリアがスプライン補間によって曲線近似されている場合について開示している。ここで、インデックスデータ構造の葉ノードはスプライン補間された曲線のの第一の最小包囲矩形に基づくデータを含み、また、中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含んでいる。データ格納部はスプライン補間された曲線に基づいて構成されている。【００１３】
７．請求項７：
請求項７では、基本的なデータ構造は請求項１と同様であるが、エリア管理データ構造のインデックスデータ構造がサービス利用者の指定する一つ以上のエリア属性に基づき収集されたエリア情報に基づいて構築されている。【００１４】
８．請求項８：
請求項８では、請求項１から７の装置において、二つ以上の前記インデックスデータ構造、及び、最下位のインデックスデータ構造のデータ格納部を含み、上位のインデックスデータ構造の葉ノードで特定されるエリアが、下位のインデックスデータ構造の前記ルートノードに対応する構造を有する場合について開示している。さらに、以下の手段によって、位置情報に対応するエリアを特定している。
（ａ）上位インデックスデータ構造を検索し位置情報に対応する葉ノードを特定する手段、
（ｂ）特定された葉ノードに対応する下位のインデックスデータ構造を検索し位置情報に対応する葉ノードを特定する手段、
（ｃ）最下位のインデックスデータ構造の葉ノードが得られるまで繰り返し、得られた最下位のインデックスデータ構造の葉ノードに対応するデータ格納部を検索し、位置情報に対応するエリアを特定する手段。【００１５】
９．請求項９：
請求項９では、請求項８の装置において、さらに、インデックスデータ構造を構築するための第一のエリアの空間座標解像度が、他のインデックスデータ構造を構築するための第二のエリアの空間座標解像度から独立に設定されることを開示している。【００１６】
１０．請求項１０：
請求項１０では、請求項８の装置において、以下の手段により、上位インデックスデータ構造の第二のエリアの追加または拡張について開示している。
（ａ）下位のインデックスデータ構造の第一のエリア情報の変更要求を受け入れる手段、
（ｂ）前記第一のエリアに対応する上位インデックスデータ構造の第二のエリアが存在するか否か判断する手段、
（ｃ）前記第二のエリアが存在しない場合、前記第一のエリアに対応する上位インデックスデータ構造の第二のエリアを追加する手段、
（ｄ）前記第二のエリアが存在するが、前記第一のエリアの全てを包含しない場合、前記第二のエリアを拡張する手段。【００１７】
１１．請求項１１：
請求項１１では、請求項８の装置において、以下の手段により、下位のエリア属性に基づくインデックスデータ構造を削除することについて開示している。
（ａ）下位のインデックスデータ構造の第一のエリア情報の変更要求、及び、第一のエリアの属性を受け入れる手段、
（ｂ）第一のエリアの属性に対応する下位のエリア属性に基づくインデックスデータ構造が存在している場合には、第一のエリア情報の変更を行い、また下位のエリア属性に基づくインデックスデータ構造を削除する手段。【００１８】
１２．請求項１２：
請求項１２では、請求項１から１１の装置において、エリア関連情報を出力する手段が、さらに、サービス利用者に関する情報、サービス提供者、又は、エリアの属性に関する情報のうち少なくとも一つを考慮して検索することを開示している。【００１９】
１３．請求項１３：
請求項１３は、請求項１の装置を、コンピュータを制御して、任意の位置情報に対応するエリア関連情報を出力するプログラムを開示している。【００２０】
１４．請求項１４：
請求項１４は、請求項７の装置を、コンピュータを制御して、任意の位置情報に対応するエリア関連情報を出力するプログラムを開示している。【００２１】
１５．請求項１５：
請求項１５では、請求項８の装置を、コンピュータを制御して、任意の位置情報に対応するエリア関連情報を出力するプログラムを開示している。【００２２】
１６．請求項１６：
請求項１６では、請求項１の装置において、任意の位置情報に対応するエリア関連情報を出力する方法を開示している。
【発明の効果】
【００２３】
（１）多次元インデックスの１つである「R-tree」はCAD等の分野で幅（広がり）をもつ物体群を対象とし、かつデータ更新の多い動的な環境での利用に適したデータ構造である。
検索効率を更に向上させた「R*-tree」に基づくデータ構造を用いてサービス提供エリアを表現・管理することにより、モバイルユーザの位置がどのエリアに属しているかという空間探索を高速に効率よく実行することができる。
（２）対象物体の表現に用いる包囲矩形の重複が可能である「R*-tree」を用いることにより、サービス提供エリアの重複定義が可能となるため、複数の異なるサービスを提供する提供者、あるいは複数のサービス提供者が利用できるエリア情報の管理システムとなる。
（３）エリア情報の管理において、街の区画、区画内にある建物、建物内のフロア、フロア内の各店舗、店舗内での特定の場所など、様々なタイプおよび粒度のエリアを定義することができ、それらに対して柔軟かつ容易にサービスを割当てることができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施概要を示す図である。
【図２】本発明の実施する装置を示すブロック図である。
【図３ａ】本発明の実施する装置の機能ブロック図である。
【図３ｂ】本発明の実施するエリア情報格納部のブロック図である。
【図４ａ】インデックッスデータ構造を示す図である。
【図４ｂ】４分木データを示す図である。
【図５】最小包囲矩形（ＭＢＲ）の概念を説明する図である。
【図６】インデックッスデータ構造に対応する領域を示す図である。
【図７】４分木データを説明する図である。
【図８】本発明の実施例１の流れ図を示す図である。
【図９ａ】複数の矩形で領域を近似する例を説明する図である。
【図９ｂ】複数の矩形で領域を近似する例を説明する図である。
【図１０ａ】本発明の実施例２の流れ図を示す図である。
【図１０ｂ】本発明の実施例３の流れ図を示す図である。
【図１１】エリアを直線領域として直線で近似する実施例を説明する図である。
【図１２】エリアを非直線領域として複数の直線で近似する実施例を説明する図である。
【図１３】エリアを曲線領域として近似する実施例を説明する図である。
【図１４】エリアを曲線領域として複数の曲線で近似する実施例を説明する図である。
【図１５】本発明の多段インデックス構造を示す図である。
【図１６】多段インデックス構造から地域管理インデックスを省いた例を示す図である。
【図１７】本発明のエリア属性に基づくインデックスを示す図である。
【図１８】本発明の二つのエリア属性に基づくインデックスを示す図である。
【図１９】本発明のブロック図である。
【図２０】本発明のブロック図である。
【図２１】本発明ではエリアの粒度が変えられることを示す図である。
【図２２ａ】本発明のエリア設定を示す図である。
【図２２ｂ】本発明の地域を拡張する例を示す図である。
【図２３】本発明の地域を拡張する例を示す図である。
【図２４】本発明の種地域を拡張する例を示す図である。
【図２５】本発明の好適実施例に関するフローチャートである。
【図２６】本発明の好適実施例に関するフローチャートである。
【図２７】本発明の好適実施例に関するフローチャートである。
【図２８】本発明の好適実施例に関するフローチャートである。
【図２９】本発明の好適実施例に関するフローチャートである。
【発明を実施するための最良の形態】
【００２５】
以下に本願発明の最良の実施形態を示す。
【実施例１】
【００２６】
図１は本願発明の一実施例について説明している。現在自分のいる位置情報に基づくサービスを受けたいユーザは、ＧＰＳ２０その他の手段によって、ユーザのいる現在の位置情報を取得する。
ユーザのいる現在の位置情報を取得する手段の一例としてＧＰＳについ
て説明する。ＧＰＳとは、人工衛星を利用して自分が地球上のどこにいるのかを正確に割り出すシステムであり、高度約２万kmの６つの円軌道に４つずつ配された米国防総省が管理するＧＰＳ衛星からの電波を利用し、緯度、経度などを高精度で割り出すことができるシステムである。
位置情報を取得したユーザは情報受信装置３０から無線基地局４０を経由して、ネットワーク上のエリア関連情報提供装置５０をアクセスすることが出来る。
ここで所定の位置情報に対応する一つ以上のサービス情報を取得できる。また、サービス提供者は自己の提供するサービスとそのサービス提供エリアに関する情報とを組とした情報を、サービス提供者端末機６０を使用してエリア関連情報提供装置５０に登録する。【００２７】
図２は、本願発明を実施するエリア関連情報提供装置５０を示している。エリア関連情報提供装置５０の中には、記憶部１１０、メインメモリー１２０、出力部１３０、中央制御部（ＣＰＵ）１４０、位置情報入力部１５０、エリア情報入力部１６０、ユーザ情報入力部１７０が含まれている。
サービス提供者は、提供するサービス内容とそれに対応するサービス提供エリアに関する情報を、ネットワーク等を経由しエリア情報入力部１６０から、予め入力しておく。ユーザも自己の性別・年齢・嗜好情報等の個人的な情報をネットワーク等を経由しユーザ情報入力部１７０から予め入力しておくことが出来る。
中央制御部１４０は、これらの情報を記憶部１１０に記憶する。ユーザは、現在の位置情報をネットワーク等を経由して位置情報入力部１５０から入力する。中央制御部１４０は記憶部１１０に記憶されている位置情報に対応するサービス情報を読み出し出力部１３０から結果を出力する。【００２８】
図３ａは、本願発明によるユーザの位置に基づくエリア関連情報提供装置５０の機能ブロック図を示している。２１０は位置情報入力部、２２０はエリア情報入力部、２２５はユーザ情報入力部、２３０はエリア情報検索部、２４０はエリア情報格納部、２５０はエリア情報管理部、２５５はユーザ情報管理部、２６０はエリア関連情報検索部、２７０はエリア関連情報格納部、２７５はユーザ関連情報格納部、２８０はエリア関連情報出力部を示す。以下、これらの詳細について説明する。
実施例１では、サービス提供エリアのデータを「ベクトル化処理法」によって構築し、これらのデータを検索する方法について説明する。【００２９】
（１）位置情報入力部（ブロック２１０）：
ユーザからの位置情報の入力部である。
ユーザは、ＧＰＳなどを利用して、自分のいる位置を検出し、その位置情報をネットワークを経由してエリア関連情報提供装置の位置情報入力部（ブロック２１０）へ入力する。
（２）エリア情報入力部（ブロック２２０）：
サービス提供者により提供されるサービスエリアに関する情報（形状、位置など）の入力部である。
サービス提供者は、デジタイザあるいはグラフィカルユーザインターフェース等を利用してサービス提供エリアのベクトル化処理を行い、当該データ及びこれらに対応するサービス内容とを入力する。
（３）ユーザ情報入力部（ブロック２２５）：
ユーザは自己の性別・年齢・嗜好情報・ユーザが参加しているキャンペーンプログラムのリスト等の個人的な情報を予め入力しておく。
これにより、ユーザが入力した位置情報に基づくサービス情報が選択されたとき、ユーザの必要とする情報のみを選択して出力することが出来る。【００３０】
（４）エリア情報格納部（ブロック２４０）：
エリア情報格納部は、図３ｂに示すように、第１のエリア情報格納部、及び、第２のエリア情報格納部を有している。第１のエリア情報格納部には広範なエリア情報が格納されており、ユーザの位置を広い範囲で検出することが出来る。
第２のエリア情報格納部には狭い範囲のエリア情報が格納されており、ユーザの位置を狭い範囲で検出し具体的なサービスエリアを特定することが出来る。
実施例１では、第１のエリア情報格納部には、図４ａに示す「R*-treeを用いたインデ
ックス構造」（以下本願明細書では「インデックス構造」と呼ぶ）が格納される。
また、第２のエリア情報格納部には、図４ｂに示される「４分木データ」が格納される。【００３１】
（５）エリア情報管理部（ブロック２５０）：
ここでは、サービス提供者により定義されるサービスの内容、及び、サービスエリアに関する情報（形状、位置など）が適正であるか否か確認し、これらのデータの登録・削除・更新の管理を行う。
（６）ユーザ情報管理部（ブロック２５５）：
ここでは、ユーザにより入力されるユーザ情報の管理を行う。すなわちユーザの登録、ユーザにより入力された個人的な情報が規則に従っているか等の確認を行い、これらのデータの登録・削除・更新の管理を行う。
（７）エリア情報検索部（ブロック２３０）：
ユーザの所持する情報受信装置によって特定された位置情報に基づき、ユーザが存在
するエリアをエリア情報格納部から探索し、該当するエリアを一意に特定する識別子を取得する。
一つの位置に複数のサービス提供エリアが重複して定義されている場合には、そ
の位置情報から複数のエリア識別子が得られる。【００３２】
（８）エリア関連情報検索部（ブロック２６０）：
ブロック２３０で得られたエリア識別子に基づき、当該エリアに関連付けられた様々
な情報を探索する。一つの位置に複数のサービスが提供されている場合には、その位置情報から取得された複数のエリア識別子に基づき検索することが出来る。さらに、ブロック２７５に格納されているユーザ関連情報に基づき、ユーザあるいはサービス提供者の条件に合致する情報のみを選択して提供することが出来る。
（９）エリア関連情報格納部（ブロック２７０）：
サービス提供者によって入力された各エリアで提供されるサービスなどの関連情報が
格納される。
これらの情報はブロック２５０のエリア情報管理部を経由して格納される。
（１０）ユーザ関連情報格納部（ブロック２７５）：
ユーザによって入力された各ユーザの個人情報が格納される。これらの情報はブロッ
ク２５５のユーザ情報管理部を経由して格納される。
（１１）エリア関連情報出力部（ブロック２８０）：
検索結果が出力され、ネットワークを経由してユーザへ送信される。【００３３】
[各部の説明]
以下、各部について詳細に説明する。【００３４】
１．最小包囲矩形（MBR：Minimum Bounding Rectangle）：
先ず、ＭＢＲについて説明する。ＭＢＲとは、所定のエリアを、ベクトル化処理を行
うことにより、当該エリアに外接する矩形で表現することを言う。
すなわち、図５に示されるように、エリアの境界線（図５左端）を複数の直線と頂点からなる多角形により近似し（図５中央）、この近似多角形を最小包囲矩形（MBR：Minimum Bounding Rectangle）により外接する矩形で表現すること（図５右端）を言う。
近似の精度は、データ量および許容できる誤差などから任意に設定できる。【００３５】
２．インデックス構造：
図６には、領域Ａ、領域Ｂ、領域ＣそれぞれのＭＢＲ、及び、それらを包括するＭＢＲとして領域１が示されている。また、領域Ｄ、領域Ｅ、領域ＦそれぞれのＭＢＲ、及び、それらを包括するＭＢＲとして領域２が示されている。図６に示される領域Ａ〜Ｆ、領
域１、及び、領域２の８つのＭＢＲにより表現されるデータを、図４ａに示す「インデックス構造」に格納する。ここで、領域１〜２を格納するノードを中間ノードと呼び、管理・格納の対象となる領域Ａ〜Ｆを格納するノードを葉ノードと呼ぶ。
図４ａに示される「インデックス構造」では対象となる全てのデータのＭＢＲを多分木構造で管理し、その最上部はルートノード（根ノード）である。二段目には中間ノードとして「領域１」および「領域２」が示されており、それぞれ図６の「領域１」および「領域２」に対応している。三段目のブロックには、葉ノードとして「領域Ａ」から「領域Ｆ」が示されて、それぞれ図６の「領域Ａ」から「領域Ｆ」に対応する。【００３６】
中間ノードは、下位に位置する「葉ノード」のＭＢＲの集合を包含するＭＢＲと、そ
れら複数の「葉ノード」へのポインタを有している。各葉ノードは、対象となるエリアのＭＢＲとそれに対応する４分木データへのポインタを有している。図４ａに示した例では、「中間ノード」には（式１）で示す情報が、「葉ノード」には（式２）で示す情報が含まれている。
（式１）  中間ノード＝（I，葉ノードへのポインタ）
（式２）  葉ノード＝（I，４分木データへのポインタ）
ここで、I ＝ (IS,IE)、但しIS＝（IS1, IS2, ..., ISn ）、IE＝（IE1, IE2, ..., IEn）である。
ISはｎ次元空間におけるＭＢＲの一方のコーナーの座標を表し、IEはISに対応する他方のコーナーの座標を表している。
二次元空間で考えると、I ＝ (IS,IE)であり、IS＝（IS1, IS2 ）、IE＝（IE1, IE2 ）となる。【００３７】
領域１を示す中間ノードには、領域１のＭＢＲを表す座標としてＰ(x１,y１)、及び、
Ｑ(x２,y２)（図６参照）が格納される。
領域Ａを示す葉ノードには、領域ＡのＭＢＲを表す座標としてＲ(x３,y３)、及び、Ｓ(x４,y４)（図６参照）が格納される。
ここで、ユーザが入力した位置情報について検索し、先ず、領域１にあるのか領域２にあるのかを検索する。
次に検索された領域に対応する中間ノードに含まれている「葉ノードへのポインタ」に従い、その下位にある全ての葉ノードについて検索する。
全ての葉ノードの検索をした結果、該当する葉ノードに含まれる「４分木データへのポインタ」に従い、４分木データ（図４ｂ）を検索する。【００３８】
３．４分木データ：
「インデックス構造」は、ＭＢＲで表現されているために、入力された位置が含まれる領域を高速に絞り込むことはできるが、サービス提供者が提供する個々のサービスエリアを特定することは出来ない。絞り込まれたエリアを正確に特定するために、葉ノードに含まれる４分木データへのポインタによって指定される「４分木データ」をさらに検索する。
４分木データとは、一種のデータ圧縮手法を用いた構造であり、かつ所定の位置が近似多角形の内側に位置するか否かを所定の精度で判別するのに適した構造を有する。近似多角形の情報は４分木データで表現すると図４ｂに示すようなツリー構造で表現できる。【００３９】
４分木データの最上位もルートノードとよばれ、図６に示される領域Ａを一意に特定する「エリア識別子」が格納される。図７は領域Ａに対応するサービス提供エリアの近似多角形とそのＭＢＲを例示した図である。
図４ｂに示される４分木データの２段目には、図７左図に示されるＭＢＲを４分割した第一象限（I）、第二象限（II）、第三象限（III）、第四象限（IV）に対応するデータが格納される。
三段目には、図７右図に示されるように第一象限（I）をさらに４分割した場合の各ブロック（1-1、1-2、1-3、1-4）が対応するデータが格納される。
格納されているデータには、近似された多角形の内側であるか、外側であるかによって、１（ワン）または０（ゼロ）が与えられる。図７右図を参照して説明すると、「1-1」は全ての領域が多角形の外側であるので、０（ゼロ）が与えられる。
「1-2」は外側の領域が内側の領域より多いので、０（ゼロ）が与えられる。
「1-3」は内側の領域が外側の領域より多いので、１（ワン）が与えられる。４段目には、「1-4」をさらに４分割したデータが格納される。すなわち、それぞれのノードには、０（ゼロ）、０（ゼロ）、１（ワン）、１（ワン）が格納される。ここで、４分木をどこまで分割するかは、データ量などからサービス提供者が任意に定めることができる。【００４０】
４．位置情報に基づくエリア関連情報の検索：
（ａ）エリア識別子の検索（ブロック２３０）
エリア識別子の検索は図３ａのブロック２３０に対応する。特定された位置情報に基づき、ユーザが存在するエリアをエリア情報格納部から探索し、該当するエリアを一意に同定するエリア識別子を取得する。以下に検索方法を示す。
（イ）ＧＰＳあるいは携帯端末などから得られた位置情報をユーザから受け取りエリア情報格納部への格納に用いる座標系にデータ変換する。
（ロ）インデックス構造（図４ａ）に対してGuttmanの探索アルゴリズム（非特許文献７）を実行し、位置情報に該当するＭＢＲデータを格納する葉ノードを全て検索し、４分木データへのポインターを読み出す。
（ハ）ステップ（ロ）で得られた葉ノードのポインタにより示される「４分木データ」に対して探索アルゴリズムを実行する。
ＭＢＲデータは近似した多角形を包含する矩形を表すデータであるので、入力された位置情報が、ＭＢＲデータに含まれる多角形（サービスエリア）の内側にあるか否かを４分木データを用いて確認する。【００４１】
（ニ）位置情報から得られる位置が、エリアの内側に存在する場合に、４分木のルートノードに格納されたエリア識別子を探索結果として返す。同様の検索をステップ（ロ）で得られた全ての葉ノードに対して繰り返し、当該位置情報の属する全てのエリア識別子を取得する。
なお、当該位置情報が全てのエリアの外側に存在する場合には「NULL」を返す。【００４２】
（ｂ）エリア関連情報の検索（ステップ２６０）：
エリア関連情報の検索は図３ａのブロック２６０に対応する。
（ａ）エリア識別子の検索で得られたエリア識別子に基づき、当該エリアに関連付けられた様々な情報を探索する。
一つの位置情報から複数のエリア識別子が検索された場合には、複数のサービス又は関連する情報を検索する。
ここで、ユーザ関連情報格納部（ブロック２７５）に格納されている当該ユーザの個人情報をもとに、検索された情報の中から、当該ユーザあるいはサービス提供者の条件と合致する情報のみを選択することが出来る。【００４３】
以下に例について示す。
同一地点にいるユーザＡおよびＢからの情報検索依頼により、その位置情報に対応するエリアとして複数のエリア１、２、３が特定されたとする。各
エリアには、それぞれ企業１、２、３がサービス提供者として登録されているものとする。
また、ユーザＡが参加しているキャンペーンリストとして｛企業１、３、５、６｝が、ユーザＢが参加しているキャンペーンとして｛企業２、３、４、７｝が、ユーザ関連情報格納部に記憶されているとする。
このとき、ユーザＡに対しては企業１、３に対応するエリア１、３の関連情報が選択され検索結果として出力される。同様に、ユーザＢに対しては企業２、３に対応するエリア２、３の関連情報が出力される。【００４４】
他の例では、ユーザＡは２０歳代の男性、ユーザＢは４０歳代の女性、であることが
ユーザ関連情報格納部に記憶されているとする。
また、エリア１，２に対応する関連情報として「男性に提供」、エリア３に対応する関連情報に「３０歳以上に提供」というアクセス制御情報が含まれているとする。
このとき、ユーザＡに対しては企業１に対応するエリア１の関連情報が選択され検索結果として出力される（「３０歳以上」という条件から、エリア３は選択されない）。
同様に、ユーザＢに対しては、企業３に対応するエリア３の関連情報が出力される（「男性」という条件から、エリア２は選択されない）。【００４５】
（ｃ）検索結果の出力（ステップ２８０）：
検索結果の出力は図３ａのブロック２８０に対応する。検索結果を出力し、ネットワ
ークを経由してユーザへ送信する。【００４６】
５．アルゴリズム：
本願発明による位置情報に基づく関連情報の検索方法のアルゴリズム（図８）につい
て説明する。
ステップ１０：位置情報、及び、ユーザ識別子を受け入れるステップ。
ユーザは、ユーザの存在する位置情報、及び、当該ユーザ識別子を情報受信装置からネットワーク経由して送信する。エリア関連情報提供装置はこれらの情報を受入れる。
ステップ２０：位置データに含まれる全ての葉ノードを検索するステップ。
インデックス構造（図４ａ）に対してGuttmanの探索アルゴリズムを実行し、当該位置データに対応するＭＢＲデータを有する葉ノードを全て検索する。【００４７】
ステップ３０：４分木データに対する探索結果からエリア識別子を取得するステップ
検出された全ての葉ノード対応する４分木データに対して探索アルゴリズムを実行し、葉ノードのポインタで指定される４分木データに対して、ユーザの位置が、サービス提供者の指定するエリアの内側にあるかどうかの判別を行う。内側にあるときには、当該４分木データのルートノードに格納されているエリア識別子を返す。
ユーザの位置が、エリアの外側に存在する場合には「NULL」を返す。【００４８】
ステップ４０：得られたエリア識別子に基づき、そのエリアに関連付けられた情報を探索するステップ。
当該エリアに関連する様々な情報、例えば、当該位置付近の地図、時刻表，乗り換え案内、電車の事故状況、気象情報、道路の混雑状態などの情報、あるいは、エリアで提供される様々なサービス、例えば、当該エリアのある商店で提供されている商品、価格、在庫状況などの情報が検索される。
ステップ５０：ユーザ関連情報に基づく関連情報の選択位置情報と共に送信されたユーザ識別子を用いて、予め格納されている当該ユーザの個人情報およびサービス提供者に関する情報を参照し、当該ユーザに対して提供され得るサービスまたは関連情報を選択的に検索することが出来る。
ステップ６０：検索結果を出力するステップ。
ステップ５０で検索されたこれらの情報を情報受信装置の表示部へ出力する。
【実施例２】
【００４９】
実施例２、及び、実施例３では、サービス提供エリアのデータ構築について「複数の矩形による組み合わせ処理」を用いる例について説明する。
実施例２では、第１のエリア情報格納部には、それぞれのエリアを近似する複数の矩形を全て包含するＭＢＲを管理する「インデックス構造」が格納され、第２のエリア情報格納部には複数の矩形の組み合わせによって近似されたエリア情報が格納される。第２のエリア情報格納部には「矩形集合データ」（式４、後述）を使用する。
実施例３では、第１のエリア情報格納部に、エリアを近似する複数の矩形をそれぞれ個別に管理する「インデックス構造」が格納され、第２のエリア情報格納部に相当するものは使用しない。【００５０】
以下、実施例２について説明する。図９ａ左端に示される図形を近似する場合に、図９ａ右端に示されるように、複数の矩形で近似することが出来る。近似の精度を向上させるためには、矩形の数を増やせばよいが、その分多くの矩形に関する情報を保持する必要がある。
図９ａ右端図では、矩形Ａから矩形Ｅまでの合計５個の矩形によって近似されている。
さらに、図９ｂ右端図に示すように、これらの矩形Ａから矩形Ｅを全て包含するＭＢＲを定義することが出来る。【００５１】
図４ａで示される葉ノードには、（式３）で定義される情報が含まれている。
（式３）  葉ノード＝（I，矩形集合データへのポインタ）
ここで、当該葉ノードはサービスエリアを近似するｍ個の矩形をすべて包含するＭＢＲの情報を格納する。図９ｂ右端図で説明すると破線で囲まれた部分がこれに相当する。
ここで、I ＝ (IS,IE)、但しIS＝（IS1, IS2, ...,ISn ）、IE＝（IE1, IE2, ...,IEn ）である。
ISはｎ次元空間における当該ＭＢＲの一方のコーナーの座標を表し、IEはISに対応する他方のコーナーの座標を表している。
二次元空間で考えると、I ＝ (IS,IE)であり、図９ｂで示すと、IS＝Ｖ（ｘ７，ｙ７）、IE＝Ｗ（ｘ８，ｙ８）である。
また、「矩形集合データ」は（式４）に示すように、エリア識別子とｍ個の矩形データとの組からなる。
（式４）  矩形集合データ＝（エリア識別子，（I１, I２ , ...,Iｍ））
但し、IJ はJ番目の矩形のＭＢＲの座標を表す。
ここでIＪ ＝ (IJS,IJE)  と表すことが出来る。
ｎ次元空間を考えると、IJS＝（IJS1, IJS2, ...,IJSn ）、IJE＝（IJE1, IJE2, . ..,IJEn）である。
IJSはJ番目の矩形のＭＢＲの一方のコーナーの座標を表し、IJEはIJSに対応する他方のコーナーの座標を表している。【００５２】
二次元平面として、図９ｂ左端図で説明すると、ここで示される図形は矩形Ａから矩形Ｅまでの５つの矩形から構成されているので、これらの矩形が矩形I１, I２ , ...,I５
に対応する。図形ＡがI１に対応するとして説明すると、I１ ＝ (I1S,I1E)と表すことが出来、矩形Ａの一方のコーナー座標、I1S＝Ｔ（x５，y５）であり、他方のコーナー座標、I1E＝Ｕ（x６，y６）と表すことが出来る。
従って、葉ノードのポインタで指定される矩形集合データの中に複数の矩形情報が含まれており、矩形集合データの中で、ユーザのいる位置が各矩形の内側にあるかどうかの判別を行う。何れかの矩形の内側ある場合に、当該矩形集合データに格納されているエリア識別子を返す。
エリアの外側に存在する場合には「NULL」を返す。【００５３】
図３ａで示される機能ブロック図の中で実施例１との違いを説明する。
（１）エリア情報入力部（ブロック２２０）：
サービス提供者は、デジタイザあるいはグラフィカルユーザインターフェース等を利用してサービス提供エリアの形状を近似する（図９ａ）。
ベクトル化とは異なり、定義すべきサービスエリアの形状をいくつかの矩形の組合せにより近似する。矩形の大きさ、配置などはサービス提供者が任意に設定できる。
（２）エリア情報格納部（ブロック２４０）：
サービス提供エリアに関する情報をエリア情報格納部に格納する。この場合は、形状近似に用いられる複数の矩形をすべて包含するＭＢＲをインデックス構造におけるＭＢＲデータとして、（式３）に示すように、当該ＭＢＲデータ、及び、矩形集合データへのポインタをインデックス構造の葉ノードに格納する。当該ポインタで指定される矩形集合データには、（式４）に示すように、該当するエリアのエリア識別子と、エリアの形状近似に用いられる複数の矩形データとの組が含まれる。【００５４】
（３）エリア情報検索部（ブロック２３０）：
位置情報に基づきユーザが存在する位置に対応するエリア識別子をエリア情報格納部から探索する。
実施例２では、インデックス構造に対してGuttmanの探索アルゴリズム（非特許文献７）を実行し、位置データに該当するＭＢＲデータを格納する葉ノードを見つけ出す。葉ノードのポインタで指定される矩形集合データの中に含まれている複数の矩形データの中で、ユーザのいる位置が各矩形の内側にあるかどうかの判別を行う。
何れかの矩形の内側ある場合には、矩形集合データ（式４）の中に格納されているエリア識別子を取得する。【００５５】
[アルゴリズム]
実施例２による位置情報に基づく関連情報の検索方法のアルゴリズム（図１０ａ）について説明する。
ステップ１０：位置情報、及び、ユーザ識別子を受け入れるステップ。
ユーザは、ユーザの存在する位置情報、及び、当該ユーザ識別子を情報受信装置からネットワーク経由して送信する。エリア関連情報提供装置はこれらの情報を受入れる。
ステップ２０：位置データに含まれる全ての葉ノードを検索するステップ。
インデックス構造（図４ａ）に対してGuttmanの探索アルゴリズムを実行し、当該位置
データに対応するＭＢＲデータを格納する葉ノードを全て検索し、当該ＭＢＲ内に存在する場合には、「矩形集合データ」へのポインタを取得する。【００５６】
ステップ３０：葉ノードのポインタで指定される「矩形集合データ」の中に含まれている矩形データに対して、ユーザの位置が各矩形の内側にあるか否かの判別を行う。
サービス提供者の指定するエリアの内側にあるときには、当該矩形集合データに格納されているエリア識別子を取得する。
ステップ４０：得られたエリア識別子に基づき、そのエリアに関連付けられた情報を探索するステップ。当該エリアに関連する様々な情報については、実施例１と同様である。
ステップ５０：検索結果を出力するステップ。
ステップ３０で検索されたこれらの情報を情報受信装置の表示部へ出力する。
【実施例３】
【００５７】
実施例３では、サービス提供エリアのデータ構築について「複数の矩形による組み合わせ処理」を用いる例について説明する。
第１のエリア情報格納部には、エリアを近似する複数の矩形をそれぞれ個別に管理する「インデックス構造」が格納され、第２のエリア情報格納部は使用しない。
実施例３では、サービス提供エリアを近似するｍ個の矩形をそれぞれ独立したＭＢＲとみなし、インデックス構造の葉ノードには、矩形毎に（式５）で定義される情報が格納される。
図９ａ右端図を例にとると、サービス提供エリアは、矩形Ａから矩形Ｅまでの５個の矩形によって近似されているので、これらに対応する５個の葉ノードが作成される。
（式５）  葉ノード＝（I，エリア識別子）
ここで、I ＝ (IS,IE)と表すことが出来る。ISは葉ノード内の矩形のＭＢＲの一方のコーナーの座標を表し、IEはISに対応する他方のコーナーの座標を表している。ｎ次元空間を考えると、IS＝（IS1, IS2, ...,ISn ）、IE＝（IE1, IE2, ...,IEn）である。
二次元空間で考え、図９a右端図の矩形Ａを例にとると、IS＝Ｔ（ｘ５，ｙ５）、IE＝Ｕ（ｘ６， ｙ６）である。【００５８】
[アルゴリズム]
実施例３による位置情報に基づく関連情報の検索方法のアルゴリズム（図１０ｂ）について説明する。
ステップ１０：位置情報、及び、ユーザ識別子を受け入れるステップ。
ユーザは、ユーザの存在する位置情報、及び、当該ユーザ識別子を情報受信装置からネットワーク経由して送信する。エリア関連情報提供装置はこれらの情報を受入れる。
ステップ２０：葉ノードを検索し、エリア識別子を取得するステップ。
インデックス構造（図４ａ）に対してGuttmanの探索アルゴリズムを実行し、位置デー
タに対応するＭＢＲデータを格納する葉ノードを検索し、ユーザの位置が矩形の内側にあるか否かの判別を行う。
内側にあるときには、当該葉ノードに格納されているエリア識別子を取得する。【００５９】
ステップ３０：得られたエリア識別子に基づき、そのエリアに関連付けられた情報を探索するステップ。
当該エリアに関連する情報については、実施例１と同様である。
ステップ４０：検索結果を出力するステップ。
ステップ３０で検索されたこれらの情報を情報受信装置の表示部へ出力する。
実施例３では、位置情報に基づきユーザが存在する位置をエリア情報格納部から探索する際、インデックス構造に対してGuttmanの探索アルゴリズムを実行し、位置データに対応するＭＢＲを格納する葉ノードが見つかった時点で、ユーザ位置がサービス提供エリア内に存在すると判定でき、直ちにエリア識別子を取得することが可能となる。
【実施例４】
【００６０】
実施例１、実施例２、及び、実施例３では、提供されるサービスエリアが、ある広がりを持った二次元平面として説明しているが、実施例４、及び、実施例５では、サービスエリアが、二次元平面ではなく直線、又は、曲線で近似することが出来る場合について説明する。実施例４では、サービスエリアが直線で近似することが出来る場合について説明する。
第１のエリア情報格納部には、所定のエリアを近似した直線のＭＢＲ、及び、当該直
線データへのポインタを一組として管理する「インデックス構造」が格納される。また、第２のエリア情報格納部には、エリア識別子を含む「直線データ」（式７、後述）が格納される。【００６１】
実施例４の好適実施例としては、直線で近似できるような道路を走行している車から、その場所を含むエリアに提供されるサービス等の情報を入手する場合が、考えられる。
この場合、ユーザは主に道路に沿って移動するため、その位置情報としては、ある程度予測可能な線上に存在することが多いと考えられる。サービス提供エリアとして、面積をもつ領域データではなく、道路などに対応する直線データによる定義で十分な場合もある。
サービスエリアを定義するための特殊な形状としては、直線、折れ線、曲線が考えられる。【００６２】
図１１は、直線で近似できるエリアを示している。ここでも実施例１と同様に、最小包囲矩形（ＭＢＲ）を適用することが出来る。地点ａ及び地点ｂを結ぶ直線を定め、地点ａ及び地点ｂを含む最小包囲矩形（ＭＢＲ）を定義する。現実には道路はある幅を有しており、また、位置情報の取得に関してある程度の誤差を許容する必要があるので、許容できる誤差範囲を定める。
葉ノードに格納する情報を（式６）によって定義される。
（式６）  葉ノード  ＝（I，直線データへのポインタ）
ここでは、実施例１と同様に、I ＝ (IS,IE)、但しIS＝（IS1, IS2, ...,ISn ）、IE＝（IE1, IE2, ...,IEn ）である。
ISはｎ次元空間におけるＭＢＲの一方のコーナーの座標を表し、IEはISに対応する他方のコーナーの座標を表している。【００６３】
「直線データ」は、データ型、フラグ、及び、エリア識別子を含むデータの組からなり、実施例４では（式７）で定義される。
（式７）  直線データ  ＝（データ型、フラグ、エリア識別子）
ここで、データ型とは直線データであることを示す情報、フラグとは直線の傾きがプラスであるかマイナスであるかを示す情報、エリア識別子は当該エリアを一意に特定する識別子である。
（式６）および（式７）によって与えられるＭＢＲの情報、データ型、及び、フラグの情報により、ＭＢＲの対角線を結ぶ直線は計算によって求めることが出来る。
対角線は傾きがプラスの場合とマイナスの場合との２つの直線が計算されるが、傾きを指定することにより一意に特定できる。
また、許容誤差範囲を予め決めておけば、ユーザの位置が当該直線の許容範囲内にあるかどうかは検出できる。
これにより、ユーザの位置が所定のサービスが提供される直線的なエリア上に存在するかどうかが判定される。
許容範囲内にあることが分かれば、その葉ノードのポインタで指定される直線データに定義されているエリア識別子を取得し、次のステップへ行くことが出来る。【００６４】
次に、サービスエリアを複数の直線で近似する場合について説明する。
実際には、道路上のサービスエリアを近似するためには、一つの直線だけではなく幾つかの直線を組合わせる場合が多い。
図１２に示されるように、複数の直線で近似する場合には複数の最小包囲矩形（ＭＢＲ）を適用する。この場合には、各直線に対応する各矩形が、図４ａで示す各葉ノードに対応する。これにより、一つの直線で表現される一つの最小包囲矩形（ＭＢＲ）が、一つの葉ノードに対応することにより、ある範囲に含まれる複数の直線全体を近似することができる。
近似の精度を向上させるためには、直線の数を増やせばよいが、その分多くの矩形が必要となる。
図１２では、地点ａから地点ｄまでを合計３つの直線によって近似している。【００６５】
図３ａで示される機能ブロック図の中で実施例１との違いを説明する。
（１）エリア情報入力部（ブロック２２０）：
サービス提供者は、デジタイザあるいはグラフィカルユーザインターフェース等を利用してサービス提供エリアを直線で近似する（図１２）。
直線で定義されたサービスエリアを含む複数の矩形の組合せにより近似する。矩形の大きさ、配置などはサービス提供者が任意に設定できる。
（２）エリア情報格納部（ブロック２４０）：
サービス提供エリアに関する情報をエリア情報格納部に格納する。
この場合は、第１のエリア情報格納部には、所定のエリアを近似した直線のＭＢＲ、及び、当該直線データへのポインタを一組として管理する「インデックス構造」が格納される。
また、第２のエリア情報格納部には、直線で近似されたエリアを定義する情報、及び、エリア識別子を含む「直線データ」が格納される。【００６６】
（３）エリア情報検索部（ブロック２３０）：
位置情報に基づきユーザが存在する位置に対応するエリア識別子をエリア情報格納部から探索する。
実施例４では、インデックス構造に対してGuttmanの探索アルゴリズム（非特許文献７）を実行し、位置情報に該当するＭＢＲを格納する葉ノードを全て検索し、直線データへのポインタを読み出す。
次にＭＢＲの情報、直線データとして格納されているデータ型、及び、フラグの情報、さらに、許容誤差の情報により、ユーザの位置が当該直線の許容範囲内にあるかどうかが検出できる。
これにより、ユーザの位置が所定のサービスが提供されるエリア上に存在するかどうかが判定される。
存在することが判定されると、そこに格納されているエリア識別子を取得し、エリア関連情報の検索へ進む。【００６７】
［アルゴリズム］
なお、アルゴリズムは、実施例１（図８）と同様になる。ここで、ステップ３０において、葉ノードのポインタで指定される「直線データ」で求められる近似された直線エリアの内側にあるか否かの判別を行い、該当する場合にはエリア識別子を取得する。
【実施例５】
【００６８】
実施例５では、サービスエリアが曲線で近似することが出来る場合について説明する。
第１のエリア情報格納部には、所定のエリアを近似した曲線のＭＢＲ、及び、当該曲線データへのポインタを含むデータを一組として管理する「インデックス構造」が格納される。
また、第２のエリア情報格納部には、エリア識別子を含む「曲線データ」（式９、後述）が格納される。
現実のエリア情報の管理においては、直線ではなく曲線によって近似される場合も必要となる。曲線的なエリアを近似する方法の一つとして、当該曲線を所定数の区間に分割し、各区間をそれぞれ直線で表現する方法、すなわち、曲線を折れ線で近似する方法がある。
この場合、実施例４で述べた方法を各直線に対して定義されるＭＢＲに適用することにより、曲線的なエリアを近似することができる。
以下では、別の方法として、曲線的なエリアを折れ線で近似するのではなく、曲線によって近似する場合について説明する。
曲線的なエリア上の複数の点をすべて通る曲線を近似する方法としては種々の方法が知られている。スプライン近似は離散データを区間多項式で近似する。すなわち、各データの間を所定の関数で近似することが出来る。
一般に２点間の座標と所定の係数を与えることによって曲線が近似できる。【００６９】
図１３に示す曲線を近似する場合について、スプライン関数補間による近似方法を説明する。
（１）与えられた曲線を所定数に分割する。
（２）各区間におけるスプライン関数の係数を求める。
（３）全区間の曲線を、分割点の座標及び（２）で導出された係数で近似する。
ここで、近似すべき曲線のＭＢＲに対応する葉ノードを（式８）によって定義する。
（式８）  葉ノード＝（I，曲線データへのポインタ）
ここでは、実施例１と同様に、I ＝ (IS,IE)、但しIS＝（IS1, IS2, ...,ISn ）、IE＝（IE1, IE2, ...,IEn ）である。
ISはｎ次元空間における矩形のＭＢＲの一方のコーナーの座標を表し、IEはISに対応する他方のコーナーの座標を表している。
「曲線データ」はデータ型、係数、及び、エリア識別子を含むデータの組からなり、実施例５では（式９）で定義される。
（式９）  曲線データ＝（データ型、係数、エリア識別子）
ここで、データ型とは曲線データであることを示す情報、係数はスプライン補間係数、エリア識別子は当該エリアを一意に特定する識別子である。【００７０】
（式８）および（式９）によって与えられるＭＢＲの情報、データ型、及び、係数の情報により、ＭＢＲの対角線を通る曲線は計算によって一意に特定される。また、許容誤差範囲を予め決めておけば、ユーザの位置が当該曲線の許容範囲内にあるかどうかは検出できる。
これにより、ユーザの位置が所定のサービスが提供されるエリア上に存在するかどう
かが判定される。
許容範囲内にあることが分かれば、その葉ノードのポインタで指定される曲線データに格納されているエリア識別子を取得し、エリア関連情報の検索へ行くことが出来る。【００７１】
実際には、道路上のサービスエリアを近似するためには、一つの曲線だけではなく幾つかの曲線を組合わせる場合が多い。
図１４に示されるように、複数の曲線で近似する場合には複数の最小包囲矩形（ＭＢＲ）を適用する。この場合には、曲線の各部分に対応する各矩形が、図４ａで示す各葉ノードに対応する。
これにより、一つの曲線の一部が表現される一つの最小包囲矩形（ＭＢＲ）が、一つの葉ノードに対応することにより、ある範囲に含まれる一つの曲線全体を近似することができる。
近似の精度を向上させるためには、曲線の分割数を増やせばよいが、その分多くの矩形が必要となる。図１４では、地点ａから地点ｄまでを合計３つの曲線で全体の曲線を近似している。【００７２】
図３ａで示される機能ブロック図の中で実施例１との違いを説明する。
（１）エリア情報入力部（ブロック２２０）：
サービス提供者は、デジタイザあるいはグラフィカルユーザインターフェース等を利用して曲線からなるサービス提供エリアを所定数に分割する（図１４）。次に、分割された曲線の各区間を含むＭＢＲを定義する。各ＭＢＲ内の曲線をＭＢＲの２点の座標及び各区間における所定の係数で近似する。曲線の分割、矩形の大きさ、配置などはサービス提供者が任意に設定できる。
（２）エリア情報格納部（ブロック２４０）：
サービス提供エリアに関する情報をエリア情報格納部に格納する。この場合は、第１のエリア情報格納部には、所定のエリアを近似した曲線のＭＢＲ、及び、当該曲線データへのポインタを一組として管理する「インデックス構造」が格納される。また、第２のエリア情報格納部には、エリア識別子を含む「曲線データ」が格納される。【００７３】
（３）エリア情報検索部（ブロック２３０）：
位置情報に基づきユーザが存在する位置に対応するエリア識別子をエリア情報格納部から探索する。
実施例５では、インデックス構造に対してGuttmanの探索アルゴリズム（非特許文献７）を実行し、位置情報に該当するＭＢＲを格納する葉ノードを全て検索し、曲線データへのポインタを読み出す。
次にＭＢＲの情報、曲線データとして格納されているデータ型、及び、係数の情報、さらに、許容誤差の情報により、ユーザの位置が当該曲線の許容範囲内にあるかどうかは検出できる。これにより、ユーザの位置が所定のサービスが提供されるエリア上に存在するかどうかが判定される。
存在することが判定されると、そこに格納されているエリア識別子を取得し、エリア関連情報の検索へ進む。【００７４】
［アルゴリズム］
なお、アルゴリズムは、実施例１（図８）と同様になる。ここで、ステップ３０において、葉ノードのポインタで指定される「曲線データ」を使用して求められる近似される曲線エリアの内側にあるか否かの判別を行い、該当する場合にはエリア識別子を取得する。  
【実施例６】
【００７５】
（１）多段インデックス構造の構成：
実施例１から５において、エリア情報格納部（２４０）が、単一のインデックス構造、すなわち、第一のエリア情報格納部、及び、第二のエリア情報格納部からなる場合について説明した。
実施例６では、さらに前述のインデックス木を多段に積み重ねた場合のデータ構造について説明する。
ここでは説明を簡単にする為に２段のインデックス木について説明するが、本願発明は、多段のインデックス構造についても適用出来る。
図１５に示すように、上段、及び、下段共にルートノード、中間ノード、及び、葉ノードからなるＲ*-tree構造が構築できる。
上段の葉ノードに格納されているポインターによって下段のルートノードが指定される。
以下、実施例６では便宜的に上段を地域管理インデックス、また、下段をエリア管理インデックスと呼ぶ。【００７６】
（２）エリア属性情報に基づくインデックス木（エリア属性インデックス木）：
実施例６では、エリア属性情報に基づくインデックス木について開示する。
各エリアに割り当てられた属性に着目し、特定の属性値をもつエリア集合に対してインデックス木を構築することにより、目的に応じた容易かつ迅速な検索が可能となる。
各エリアの登録者、エリアにおけるサービス提供者、サービスの種類などの情報が属性となる。
具体的な属性値としては、例えば、所定のレストラン、所定の映画館等がある。これに対して実施例１から実施例５で説明したインデックス木は地理的位置情報に基づくインデックス木である。
これらを区別するために、以下の説明では地理的位置情報に基づくインデックス木を「位置情報インデックス木」と、またエリア属性情報に基づくインデックス木を「エリア属性インデックス木」と呼ぶ。
従って、位置情報インデックス木は「位置情報地域管理インデックス木」及び「位置情報エリア管理インデックス木」からなり、また、エリア属性インデックス木は、「エリア属性地域管理インデックス木」及び「エリア属性エリア管理インデックス木」からなる。
図２０のエリア属性ＤＢ（４１０）には、エリア属性情報（属性タイプ、属性値など）が格納されている。【００７７】
（３）各地域での空間解像度：
各地域での空間解像度はそれぞれ独立に設定することが出来る。
これにより、地域によって必要とする情報の密度が異なる場合には、エリアを定義する局所座標系の空間解像度を変更することにより全体のメモリー効率を改善することが出来、また、それらの管理が容易になる。
図２１に示すように、地域Ａでは細かい解像度でエリア定義を行い、地域Ｃは粗い解像度でエリア定義を行う地域、また地域Ｂは中間程度の解像度でエリア定義を行う地域として、それぞれ設定することが出来る。
一例を示すと、対象とするエリアの密集している大都市のエリア管理と対象とするエリアの分散している郊外のエリア管理とを同じ空間解像度をもつ地域として実現することはメモリー管理上無駄が生じる。
そこで郊外のエリア管理を行う地域における空間解像度を粗く設定する。【００７８】
（４）登録地域の拡張：
インデックス木の構成時に定義した範囲を超えてエリアの範囲を拡張する場合がある。
例えば、ショッピングモールの拡張、市町村の合併などによりエリアが拡張する場合がある。
さらに当初の地域を超えてエリアが新規に登録される場合も考えられる。
この場合には、エリア管理インデックス木だけでなく、そのエリアを包含する地域を管理する地域管理インデックス木も変更する必要がある。
図２２及び２３を参照して説明する。
初期状態として、図２２ａに示す地域Ａ内にエリアａ１が定義（登録）されているとする。
その後、図２２ｂに示すように、地域Ａに含まれるエリアａ１が地域Ａの範囲を超えて拡大した場合には、拡大後のエリアａ１'を包含するように地域Ａを拡張する。この場合には、上段のＲ*-tree構造の葉ノードの中で地域Ａに対応する葉ノードに含まれるＭＢＲデータを変更し、下段のＲ*-tree構造でエリアａ１に対応するノードの変更を行う。【００７９】
続いて、エリアが新規に登録される場合について説明する。
図２３に示すように、登録されるエリアａ２が地域Ａに収まらない場合、エリアを包含するように地域を拡張する。
このとき同様に、上段のＲ*-tree構造の葉ノードの中で地域Ａに対応する葉ノードに含まれるＭＢＲデータを変更し、下段のＲ*-tree構造でエリアａ２に対応するノードの追加を行う。
また、地域として未定義の場所にエリアｂが新規に登録される場合、図２３に示すように、地域Ｂが新たな地域として定義され、上段および下段それぞれのＲ*-tree構造に対応するノードが追加される。
さらに、別の地域設定の方法を図２４に示す。
ここでは、システム管理者あるいはサービス提供者が、地理的要因などを考慮して、事前に初期地域（以下、「種地域」という）を設定する。種地域に収まるようにエリアが登録される場合、上述と同様の処理が行われる。
種地域の外にエリアｃが登録されるとき、新たな地域Ｃが定義され登録される。
また、登録されるエリアｄが種地域Ｄに収まらない場合、地域の拡張が行われる。【００８０】
（５）システム構成図：
図１９は実施例６のエリア管理システムのシステム構成図を示す。
エリア情報ＤＢ（３１０）には各エリアを定義する形状、位置などの情報及びそのエリアの識別子が格納されている。
エリア管理部（３１５）はエリア情報ＤＢ（３１０）の管理を行う。エリア管理制御部（３２０）はエリア管理部を管理し間接的にエリア情報ＤＢ（３１０）を制御する。
地域情報ＤＢ（３３０）には、複数のエリアを含むより広範囲の地域を定義する情報及びその地域の識別子が格納されている。
地域管理部（３３５）は地域情報ＤＢ（３３０）の管理を行う。地域管理制御部（３４５）は地域管理部を管理し間接的に地域情報ＤＢ（３３０）を制御する。
エリア情報操作部（３４０）でサービス提供者又はシステム管理者がエリア情報ＤＢ（３１０）又は地域情報ＤＢ（３３０）の内容を登録・削除・変更する場合の入力を行う。
利用者は、エリア検索操作部（３６０）を通して位置情報を入力し検索結果であるエリア識別子を得る。検索実行部（３５０）は実際の検索を実行する。【００８１】
図２０は、エリア属性を考慮した検索等を行うためのシステム構成部分を破線部分の内側で示している。
エリア属性ＤＢ（４１０）には、位置情報を含まないデータが格納されている。非空間検索実行（４２０）では位置情報を用いないでエリア属性に基づく検索を行う。
動的エリア管理格納部（４３０）にはエリア情報が一時的に格納される。
空間検索実行部（４４０）では、エリア属性から検索された各アイテムに対して、位置情報に関する検索を行う。
検索制御部（４５０）は空間検索実行部（４４０）、及び、非空間検索実行（４２０）の制御を行う。【００８２】
（６）アルゴリズム：
ここでは、先ず、エリア属性を利用しない場合について説明し、次に、エリア属性を使用する場合について説明する。【００８３】
１．エリア属性を使用しない場合：
（ａ）地域・エリア登録アルゴリズム：
ここでは、エリア属性を使用しない場合であって、サービス提供者が、位置情報インデックス木に、「エリア」を新たに登録する場合について説明する。
地域の登録は、システム管理者による事前設定、あるいはシステムによる自動設定・登録（地域拡張処理）で行う。
これにより、位置情報インデックス木の構築または更新が行われる（図２５）。
１０：登録するエリア情報の入力：
サービス提供者が登録する位置情報・形状などのエリア情報を入力する。
２０：エリアを包含する地域の登録：
当該「エリア」を包含する「地域」が登録されている場合にはステップ３０へ行く。
（ｉ）当該「エリア」を含む「地域」が登録されていない場合、
対応する「地域」を新たに設定し登録する。また、位置情報地域管理インデックス木にノードを追加する。
（ｉｉ）当該「エリア」の一部のみを含む「地域」が登録されている場合には、当該エリアが対応する地域に包含されるように、「地域の拡張」を行う。また、同時に位置情報地域管理インデックス木のノード情報（データ）を更新する。
３０：位置情報エリア管理インデックス木へのノードの追加：
位置情報エリア管理インデックス木に対応するノードを追加する。
４０：エリア情報の格納：
エリア情報をエリア情報格納部（図１９、３１０）へ格納する。【００８４】
（ｂ）エリア検索アルゴリズム：
次に、エリア属性を使用しない場合であって、サービス利用者が位置情報を入力した場合、位置情報インデックス木を用いその位置において利用可能なサービス等を検索するアルゴリズムについて説明する（図２６）。
１０：利用者による検索要件（位置情報）の入力：
サービス利用者が現在自分のいる位置情報を入力する。
２０：対応する地域の検索：
位置情報地域管理インデックス木を検索し位置情報に対応する「地域」を検出する。該当する地域が存在すれば、ステップ３０へ行く。該当する地域がなければ検索処理を終了する。
３０：検出された「地域」に対応するエリア管理部への位置情報の送信：
該当する地域が検索されると、検索された地域に対応するエリア管理部へ当該位置情報を送信する。
４０：位置情報エリア管理インデックス木の検索：
エリア管理部でエリア定義に用いられている空間座標解像度に基づき位置情報エリア管理インデックス木を用いてエリア検索を行う。
５０：検索されたエリア識別子の返信。【００８５】
２．エリア属性を使用する場合：
エリア属性としては、特定のレストラン名、特定の映画館名などがある。ここでは、これらのエリア属性を使用した実施例について説明する（図２７）。
（ａ）地域・エリア登録アルゴリズム：
ここでは、エリア属性を使用する場合であって、サービス提供者がエリアを新たに登録する場合について説明する。
１０：登録するエリア情報、及び、エリアの属性情報の入力：
サービス提供者が登録する位置情報・形状などのエリア情報、及び、エリアの属性情報を入力する。
２０：エリアを包含する地域の登録：
当該「エリア」を包含する「地域」が登録されている場合にはステップ３０へ行く。
（ｉ）当該「エリア」を含む「地域」が登録されていない場合、対応する「地域」を新たに設定し登録する。また、エリア属性地域管理インデックス木にノードを追加する。
（ｉｉ）当該「エリア」の一部のみを含む「地域」が登録されている場合には、当該エリアが対応する地域に包含されるように、「地域の拡張」を行う。また、同時にエリア属性地域管理インデックス木のノード情報（データ）を更新する。【００８６】
３０：同じエリア属性に基づくインデックス木の削除：
指定されたエリア属性と同じエリア属性に基づくエリア属性エリア管理インデックス木が存在する場合にはこれを削除する。
エリア属性エリア管理インデックス木が存在している場合には検索を迅速に行うことが出来る。しかしエリア属性エリア管理インデックス木のデータが更新された場合は、更新前のエリア属性エリア管理インデックス木は最新のデータを反映していないために使用できない。従ってこれを削除する必要がある。
４０：エリア情報の格納：
エリア情報をエリア情報格納部（図１９、３１０）へ格納する。【００８７】
（ｂ）エリア検索アルゴリズム：
次に、サービス利用者が、エリア属性、及び、位置情報を使用し、その位置において利用可能なサービス等を検索するアルゴリズムについて説明する。なお、エリア属性としては、複数のエリア属性を入力することが出来る。
図１８に示すように、エリア属性として、「レストラン」及び「映画館」を指定し、双方の条件を満足するサービスエリアを抽出することが出来る（図２８）。
また、その後同じエリア属性に基づく検索があった場合に効率よく検索できるように、新たなエリア属性インデックス木を構築する（図２９）。【００８８】
１０：サービス利用者による検索要件（位置情報及びエリア属性）の入力：
サービス利用者が現在自分のいる位置情報及びエリア属性を入力する。
２０：同じエリア属性インデックス木の存在の確認：
同じエリア属性インデックス木が既に存在している場合には、新たなエリア属性インデックス木を作成する必要は無いので、ステップ３０へ行く。
存在していない場合には、新たなエリア属性インデックス木を構築する。
新たなエリア属性インデックス木を構築するアルゴリズムは別途説明する。
３０：対応する地域の検索
エリア属性地域管理インデックス木を検索し位置情報に対応する「地域」を検出する。
該当する地域が存在すれば、ステップ４０へ行く。該当する地域がなければ検索処理を終了する。
４０：検出された「地域」に対応するエリア管理部への位置情報の送信：
該当する地域が検索されると、検索された地域に対応するエリア管理部へ当該位置情報を送信する。
５０：エリア属性エリア管理インデックス木の検索：
エリア管理部でエリア定義に用いられている空間座標解像度に基づきエリア属性エリア管理インデックス木を用いてエリア検索を行う。
６０：検索されたエリア識別子の返信。【００８９】
（ｃ）新たなエリア属性インデックス木を構築するアルゴリズム：
前述の（ｂ）において、同じエリア属性インデックス木が既に存在していない場合に新たなエリア属性インデックス木を構築するアルゴリズムについて説明する（図２９）。
１０：エリア属性に関する検索：
エリア属性に基づき検索を行い、該当するエリアを抽出する。
２０：対応する地域管理インデックス木の利用：
（ｉ）地域管理インデックス木を含まないエリア属性インデックス木を構築する場合（図１６）には、ステップ３０へ行く。
（ｉｉ）地域管理インデックス木を含むエリア属性インデックス木を構築する場合（図１７）には、既に存在するエリア属性地域管理インデックス木を取得する。
３０：エリア属性エリア管理インデックス木の構築：
４０：終了。
【符号の説明】
【００９０】
１０：ネットワーク
２０：ＧＰＳ
３０：情報受信装置
４０：無線基地局
５０：エリア関連情報提供装置
６０：サービス提供者端末機
１１０：記憶部
１２０：メインメモリー
１３０：出力部
１４０：中央制御部（ＣＰＵ）
１５０：操作部
１６０：位置情報入力部
１７０：サービス情報入力部
３１０：エリア情報ＤＢ
３１５：エリア管理部
３２０：エリア管理制御部
３３０：地域情報ＤＢ
３３５：地域管理部
３４５：地域管理制御部
３４０：エリア情報操作部
３６０：エリア検索操作部
３５０：検索実行部
４１０：エリア属性ＤＢ
４２０：非空間検索実行
４３０：動的エリア管理格納部
４４０：空間検索実行部
４５０：検索制御部
【図１】
2006059629.tif 000002
【図２】
2006059629.tif 000003
【図３ａ】
2006059629.tif 000004
【図３ｂ】
2006059629.tif 000005
【図４ａ】
2006059629.tif 000006
【図４ｂ】
2006059629.tif 000007
【図５】
2006059629.tif 000008
【図６】
2006059629.tif 000009
【図７】
2006059629.tif 000010
【図８】
2006059629.tif 000011
【図９ａ】
2006059629.tif 000012
【図９ｂ】
2006059629.tif 000013
【図１０ａ】
2006059629.tif 000014
【図１０ｂ】
2006059629.tif 000015
【図１１】
2006059629.tif 000016
【図１２】
2006059629.tif 000017
【図１３】
2006059629.tif 000018
【図１４】
2006059629.tif 000019
【図１５】
2006059629.tif 000020
【図１６】
2006059629.tif 000021
【図１７】
2006059629.tif 000022
【図１８】
2006059629.tif 000023
【図１９】
2006059629.tif 000024
【図２０】
2006059629.tif 000025
【図２１】
2006059629.tif 000026
【図２２ａ】
2006059629.tif 000027
【図２２ｂ】
2006059629.tif 000028
【図２３】
2006059629.tif 000029
【図２４】
2006059629.tif 000030
【図２５】
2006059629.tif 000031
【図２６】
2006059629.tif 000032
【図２７】
2006059629.tif 000033
【図２８】
2006059629.tif 000034
【図２９】
2006059629.tif 000035
【手続補正書】
【提出日】平成18年9月28日(2006.9.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】請求の範囲
【請求項１】第一のエリアデータ格納部、第二のエリアデータ格納部、エリア関連情報格納部、及び、地域データ格納部を有するエリア情報管理装置であって、
前記第一のエリアデータ格納部は、一つ以上の第一のエリア管理データ構造を格納し、
前記第一のエリア管理データ構造は、第一のエリアを包含する第一のエリア集合に対応する第一のルートノードと、第一の中間ノードと、第一の葉ノードとを含む第一のインデックスデータ構造、並びに、前記第一の葉ノードに対応する第一のデータ格納部を有し、
前記第二のエリアデータ格納部は、前記第一のエリアデータ格納部のデータからユーザの指定する一つ以上のエリア属性に基づき収集されたエリア情報に基づき構成された、一つ以上の第二のエリア管理データ構造を格納し、
前記第二のエリア管理データ構造は、前記指定された一つ以上のエリア属性に基づき収集された第二のエリアを包含する第二のエリア集合に対応する第二のルートノードと、第二の中間ノードと、第二の葉ノードとを含む第二のインデックスデータ構造、並びに、前記第二の葉ノードに対応する第二のデータ格納部を有し、
また、前記エリア関連情報格納部は、前記第一のエリア、及び、前記第二のエリアに対応するエリア関連情報を格納し、
さらに、前記地域データ格納部は、少なくとも一つ以上の前記第一のエリア集合を包含する地域に対応付けられたノードに基づき構成された地域管理データ構造を格納し、
前記地域管理データ構造は、前記地域を特定する少なくとも一つのノードが、前記第一のルートノード、または、前記第二のルートノードのいずれか一方にリンクするデータ構造を有するエリア情報管理装置。
【請求項２】前記地域管理データ構造は、前記地域を包含する地域集合に対応する第三のルートノードと、第三の中間ノードと、前記地域を特定するノードに対応する第三の葉ノードとを含む第三のインデックスデータ構造であり、
前記第三の葉ノードが、前記第一のルートノード、または、前記第二のルートノードのいずれか一方にリンクする構造を有する
請求の範囲第１項に記載のエリア情報管理装置。
【請求項３】前記地域管理データ構造の各ノードは、その位置情報に基づく所定の意味を有し、
前記ノードのうち少なくとも一つのノードが、前記第一のルートノード、または、前記第二のルートノードのいずれか一方にリンクする構造を有する
請求の範囲第１項に記載のエリア情報管理装置。
【請求項４】前記地域管理データ構造が、一つの階層を有し、前記一つの階層に含まれる、前記地域を特定する少なくとも一つのノードが
前記第一のルートノード、または、前記第二のルートノードのいずれか一方にリンクする構造を有する
請求の範囲第１項に記載のエリア情報管理装置。
【請求項５】前記エリア管理データ構造が以下の（ａ）から（ｅ）のいずれかの構造を含む請求の範囲第１項から第４項のいずれかに記載のエリア情報管理装置。
（ａ）前記エリアが近似多角形で近似され、
前記インデックスデータ構造の前記葉ノードは前記近似多角形の第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記エリアの近似多角形の４分木データに基づいて構成されている構造。
（ｂ）前記エリアが一つ以上の矩形で近似され、
前記インデックスデータ構造の前記葉ノードは前記一つ以上の矩形からなる第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記エリアの矩形に基づいて構成されている構造。
（ｃ）前記エリアが一つ以上の直線からなる折れ線で近似され、
前記インデックスデータ構造の前記葉ノードは前記直線の第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記一つ以上の直線に基づいて構成される構造。
（ｄ）前記エリアが曲線で近似され、さらに、前記曲線が一つ以上の直線からなる折れ線で近似され、
前記インデックスデータ構造の前記葉ノードは前記直線の第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記一つ以上の直線に基づいて構成される構造。
（ｅ）前記エリアがスプライン補間によって曲線近似され、
前記インデックスデータ構造の前記葉ノードは前記スプライン補間された曲線の第一の最小包囲矩形に基づくデータを含み、また、
前記中間ノードは一つ以上の前記第一の最小包囲矩形からなる集合を包含する第二の最小包囲矩形に基づくデータを含み、
前記データ格納部は、前記スプライン補間された曲線に基づいて構成される構造。
【請求項６】前記地域管理データ構造を構成するための前記地域の空間座標解像度が、前記第一のインデックスデータ構造、及び、前記第二のインデックスデータ構造を構成するための前記第一のエリア、及び、前記第二のエリアの空間座標解像度から独立に設定されたことを特徴とする
請求の範囲第１項に記載のエリア情報管理装置。
【請求項７】さらに、
（ａ）第一のインデックスデータ構造の第一のエリアに関する情報の変更要求を受け入れる手段、
（ｂ）前記第一のエリアに対応する地域が前記第三のインデックスデータ構造に存在するか否か判断する手段、
（ｃ）前記地域が存在しない場合、前記第一のエリアに対応する地域を前記第三のインデックスデータ構造に追加する手段、及び、
（ｄ）前記地域が存在するが、前記第一のエリアの全てを包含しない場合、全てを包含するように前記第一のエリアに対応する地域を拡張する手段、
を有する請求の範囲第２項に記載のエリア情報管理装置。
【請求項８】さらに、
（ａ）第一のインデックスデータ構造の第一のエリアに関する情報の変更要求、及び、前記エリアの属性を受け入れる手段、及び、
（ｂ）前記エリアの属性に対応する第二のインデックスデータ構造が存在している場合には、前記第一のエリアに関する情報の変更を行い、また前記第二のインデックスデータ構造を削除する手段、
を有する請求の範囲第２項に記載のエリア情報管理装置。
【請求項９】さらに、
（ａ）ユーザの指定する位置情報のデータを受け入れる手段、
（ｂ）前記受け入れたデータに基づき、前記地域管理データ構造、及び、前記第一のエリア管理データ構造にアクセスし、前記ノードのうち少なくとも一つを走査することによって、前記エリア関連情報格納部のデータを選択する手段、及び、
（ｃ）前記選択されたデータを出力する手段、
を有する請求の範囲第１項から第８項のいずれかに記載のエリア情報管理装置。
【請求項１０】さらに、ユーザに関する情報を格納するユーザ関連情報格納部を有し、
前記エリア関連情報格納部はサービス提供者に関する情報、及び、前記エリア属性に関する情報をさらに格納し、
（ａ）ユーザの指定する位置情報、前記ユーザに関する情報、前記サービス提供者に関する情報、及び、前記エリア属性に関する情報のうち少なくとも一つのデータを受け入れる手段、
（ｂ）前記受け入れたデータに基づき、前記地域管理データ構造、及び、前記第一のエリア管理データ構造、または、前記第二のエリア管理データ構造にアクセスし、前記ノードのうち少なくとも一つを走査することによって、前記エリア関連情報格納部のデータを選択する手段、及び、
（ｃ）前記選択されたデータを出力する手段、
を有する請求の範囲第９項に記載のエリア情報管理装置。
【請求項１１】第一のエリアデータ格納部、第二のエリアデータ格納部、エリア関連情報格納部、及び、地域データ格納部を管理するプログラムであって、
前記第一のエリアデータ格納部は、一つ以上の第一のエリア管理データ構造を格納し、
前記第一のエリア管理データ構造は、第一のエリアを包含する第一のエリア集合に対応する第一のルートノードと、第一の中間ノードと、第一の葉ノードとを含む第一のインデックスデータ構造、並びに、前記第一の葉ノードに対応する第一のデータ格納部を有し、
前記第二のエリアデータ格納部は、前記第一のエリアデータ格納部のデータからユーザの指定する一つ以上のエリア属性に基づき収集されたエリア情報に基づき構成された、一つ以上の第二のエリア管理データ構造を格納し、
前記第二のエリア管理データ構造は、前記指定された一つ以上のエリア属性に基づき収集された第二のエリアを包含する第二のエリア集合に対応する第二のルートノードと、第二の中間ノードと、第二の葉ノードとを含む第二のインデックスデータ構造、並びに、前記第二の葉ノードに対応する第二のデータ格納部を有し、
また、前記エリア関連情報格納部は、前記第一のエリア、及び、前記第二のエリアに対応するエリア関連情報を格納し、
さらに、前記地域データ格納部は、少なくとも一つ以上の前記第一のエリア集合を包含する地域に対応付けられたノードに基づき構成された地域管理データ構造を格納し、
前記地域管理データ構造は、前記地域を特定する少なくとも一つのノードが、前記第一のルートノード、または、前記第二のルートノードのいずれかにリンクするデータ構造を有する
エリア情報管理装置で実行されるプログラム。
【国際調査報告】
2006059629.tif 000036
2006059629.tif 000037
2006059629.tif 000038
2006059629.tif 000039