(57)【特許請求の範囲】
【請求項１】
緯度及び経度が指定された検索要求を受け付け、
前記検索要求に指定された前記緯度及び経度のそれぞれの全部又は最下位桁からの一部の上位桁から順に同じ桁を１桁ずつ交互に配列した一つの文字列と、前記文字列において前記緯度及び経度の小数点以下に係る部分が無くなるまで繰り返し当該文字列の末尾から２文字ずつ削除するたびに得られる文字列とを生成し、
前記生成する処理において生成された全ての文字列を使用して、キーに対応付けて情報を記憶する記憶部より、いずれかの前記文字列に完全一致するキーを検索する処理をコンピュータが実行する情報管理方法。
【請求項２】
前記検索要求に指定された緯度及び経度が示す範囲を含む範囲に係る情報を検索する場合には、前記生成する処理及び前記検索する処理を前記コンピュータが実行し、
前記検索要求に指定された緯度及び経度が示す範囲に含まれる範囲に係る情報を検索する場合には、
前記検索要求に指定された前記緯度及び経度のそれぞれの全部の桁を又は前記緯度及び経度のそれぞれの最下位桁からの一部の桁を、同じ桁を１桁ずつ交互に配列して一つの文字列を生成し、
キーに対応付けて情報を記憶する記憶部より、前記文字列に前方一致するキーを検索する処理を前記コンピュータが実行する請求項１記載の情報管理方法。
【請求項３】
前記検索要求に指定された緯度及び経度が示す範囲を当該範囲の指定に用いられた前記緯度及び経度の精度に応じた単位領域に分割した場合の各単位領域の緯度の最小値及び経度の最小値の集合を生成する処理を前記コンピュータが実行し、
前記一つの文字列を生成する処理は、前記緯度の最小値及び経度の最小値の集合に含まれるそれぞれの緯度及び経度に関して、前記一つの文字列を生成し、
前記前方一致するキーを検索する処理は、前記緯度の最小値及び経度の最小値ごとに生成されたいずれかの前記文字列に前方一致するキーを検索する請求項２記載の情報管理方法。
【請求項４】
前記集合を生成する処理は、前記範囲を当該範囲の指定に用いられた前記緯度及び経度の精度に応じた第一の単位領域のうち、該精度より上位の桁を単位とする第二の単位領域を構成する前記第一の単位領域群を前記第二の単位領域に統合し、前記第二の単位領域に統合されなかった前記各第一の単位領域の緯度の最小値及び経度の最小値、並びに前記各第二の単位領域の緯度の最小値及び経度の最小値の集合を生成する請求項３記載の情報管理方法。
【請求項５】
緯度及び経度が指定された検索要求を受け付ける受付部と、
前記検索要求に指定された前記緯度及び経度のそれぞれの全部又は最下位桁からの一部の上位桁から順に同じ桁を１桁ずつ交互に配列した一つの文字列と、前記文字列において前記緯度及び経度の小数点以下に係る部分が無くなるまで繰り返し当該文字列の末尾から２文字ずつ削除するたびに得られる文字列とを生成する生成部と、
前記生成部によって生成された全ての文字列を使用して、キーに対応付けて情報を記憶する記憶部より、いずれかの前記文字列に完全一致するキーを検索する検索部とを有する情報管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報管理方法及び情報管理装置に関する。
【背景技術】
【０００２】
本願発明者は、移動体や施設等の位置情報として緯度及び経度を収集及び管理し、位置情報に関する高速な検索サービスを提供することを検討していた。移動体とは、車載器、携帯電話、又はタブレット型端末等、主に、移動体通信網を利用した通信機能を有し、移動可能な端末、又はそのような端末を携帯する機器若しくは人等をいう。検索サービスの内容の一例として、或る範囲（例えば、施設）に含まれる移動体群の検索等が挙げられる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−４１１８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
移動体や施設等の位置情報の管理手段として、ＲＤＢ（Relational Database）を用いることが考えられる。例えば、移動体や施設等の属性として、移動体又は施設等のＩＤ及び位置情報等がＲＤＢに登録されることが考えられる。
【０００５】
しかしながら、この場合、例えば、或る範囲に含まれる移動体群を検索することを考えると、当該範囲と全てのレコードの位置情報とを比較する必要がある。上記したように、管理対象となる移動体は、車両に搭載される車載器のみならず、人が携帯する端末も含まれる。したがって、レコード数は数千万台に及び、又は数千万台を超える可能性がある。そうすると、全てのレコードの位置情報と或る範囲とを比較していたのは、実用性の或る検索性能を得るのは困難であると考えられる。
【０００６】
検索性能の向上のために、位置情報に関して、インデックスを作成することが考えられる。しかし、この場合、移動体の位置情報は刻々と変化するため、インデックスの再編成が頻発してしまい、当該再編成による処理負荷が、無視できない程度に大きくなる可能性が考えられる。
【０００７】
そこで、１側面では、上記の点に鑑みてなされたものであって、実用的な検索性能を確保しつつ位置情報を管理することのできる情報管理方法及び情報管理装置の提供を目的とする。
【課題を解決するための手段】
【０００８】
一つの案では、情報管理方法は、緯度及び経度を含む位置情報と、前記位置情報に対応する対応情報とを含む登録要求を受け付け、前記緯度及び経度のそれぞれの全部の桁を又は前記緯度及び経度のそれぞれの最下位桁からの一部の桁を、同じ桁を１桁ずつ交互に配列して一つの文字列を生成し、前記文字列をキーとし、前記対応情報を前記キーに対応付けて記憶部に記憶する処理をコンピュータが実行する。
【発明の効果】
【０００９】
一態様によれば、実用的な検索性能を確保しつつ位置情報を管理することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態における情報管理システムの構成例を示す図である。
【図２】本発明の実施の形態における情報管理装置のハードウェア構成例を示す図である。
【図３】本発明の実施の形態における情報管理装置の機能構成例を示す図である。
【図４】位置キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【図５】移動体情報の登録処理の処理手順の一例を説明するためのフローチャートである。
【図６】移動体の範囲を構成する各矩形領域の指定方法の一例を示す図である
【図７】サイズ情報のデータ構造の例を示す図である。
【図８】移動体情報記憶部の構成例を示す図である。
【図９】矩形領域の集合を構成する正規化された各セルの位置キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【図１０】矩形領域の集合を構成する正規化された各セルの位置キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【図１１】矩形領域の集合を構成する正規化された各セルの位置キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【図１２】矩形領域の集合を構成する正規化された各セルの位置キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【図１３】矩形領域の集合の一例を示す図である。
【図１４】矩形領域のセル群への分割の一例を示す図である。
【図１５】指定された全ての矩形領域を含む最小の矩形領域を説明するための図である。
【図１６】包含領域において特定される統合粒度ＣＳＩＺＥ単位のセルの例を示す図である。
【図１７】指定された矩形領域を跨いだセル群の統合結果の一例を示す図である。
【図１８】移動体情報の検索処理の処理手順の一例を説明するためのフローチャートである。
【図１９】検索範囲に対応する検索キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【図２０】検索範囲が含まれる移動体を検索するための位置キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【図２１】検索範囲が含む移動体の検索処理の処理手順の一例を説明するためのフローチャートである。
【図２２】検索キーとの前方一致の意義を説明するための図である。
【図２３】検索範囲が含まれる移動体の検索処理の処理手順の一例を説明するためのフローチャートである。
【図２４】管理テーブルの構成例を示す図である。
【図２５】一つの丸め検索キーが複数の当初検索キーに対して共通する例を示す図である。
【図２６】移動体情報の検索処理の第一の具体例を示す図である。
【図２７】移動体情報の検索処理の第二の具体例を示す図である。
【図２８】移動体情報の検索処理の第三の具体例を示す図である。
【図２９】移動体情報の検索処理の第四の具体例を示す図である。
【図３０】移動体情報の検索処理の第五の具体例を示す図である。
【図３１】移動体情報の検索処理の第六の具体例を示す図である。
【図３２】移動体情報の検索処理の第七の具体例を示す図である。
【発明を実施するための形態】
【００１１】
以下、図面に基づいて本発明の実施の形態を説明する。図１は、本発明の実施の形態における情報管理システムの構成例を示す図である。同図の情報管理システム１において、移動体端末２０ａ、２０ｂ、及び２０ｃ等の複数の移動体端末２０と情報管理装置１０とは、例えば、移動体通信網等を介して通信可能とされている。
【００１２】
移動体端末２０は、管理対象とされる移動体の位置を把握するために用いられる。したがって、移動体端末２０は、車載器、携帯電話、スマートフォン、又はタブレット型端末等、移動体通信網を利用した通信機能及びＧＰＳ（Global Positioning System）機能を有し、移動可能な端末であるのが好適である。移動体とは、移動体端末２０が設置された車両、や移動体端末２０を携帯する人等、移動体端末２０を移動させる主体である。但し、移動体端末２０自体が移動体として把握されてもよい。また、台風、雨雲、雷雲、前線等、それ自体に位置を計測するための機器は設置されなくても、その位置を外部から観測又は計測可能なものが移動体として把握されてもよい。
【００１３】
情報管理装置１０は、各移動体や、非図示の施設又はエリアに関する位置情報（緯度及び経度）等を管理するコンピュータである。複数のコンピュータが情報管理装置１０を構成してもよい。情報管理装置１０が管理する情報は、各移動体端末２０を用いて検索可能である。又は、ＰＣ（Personal Computer）等、固定端末から検索可能であってもよい。なお、エリアは、行政区画のように、予め定まっている範囲でもよいし、任意に定義される範囲でもよい。
【００１４】
図２は、本発明の実施の形態における情報管理装置のハードウェア構成例を示す図である。図２の情報管理装置１０は、それぞれバスBで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有する。
【００１５】
情報管理装置１０での処理を実現するプログラムは、記録媒体１０１によって提供される。プログラムを記録した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００１６】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従って情報管理装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００１７】
なお、記録媒体１０１の一例としては、ＣＤ−ＲＯＭ、ＤＶＤディスク、又はＵＳＢメモリ等の可搬型の記録媒体が挙げられる。また、補助記憶装置１０２の一例としては、ＨＤＤ（Hard Disk Drive）又はフラッシュメモリ等が挙げられる。記録媒体１０１及び補助記憶装置１０２のいずれについても、コンピュータ読み取り可能な記録媒体に相当する。
【００１８】
図３は、本発明の実施の形態における情報管理装置の機能構成例を示す図である。同図において、情報管理装置１０は、サービス部１１及び基盤部１２を有する。
【００１９】
基盤部１２は、情報管理装置１０における情報管理機能において基盤的又は基本的な機能をサービス部１１に提供する。したがって、基本的に、基盤部１２のクライアントは、サービス部１１である。サービス部１１は、基盤部１２が提供する機能を利用して、応用的な機能（サービス）を移動体端末２０等に提供する。たがって、基本的に、サービス部１１のクライアントは、移動体端末２０等である。なお、基盤部１２の機能は、基盤部１２が備えるＡＰＩ（Application Program Interface）を介して利用することができる。
【００２０】
基盤部１２は、移動体情報受信部１２１、登録要求受付部１２２、位置キー生成部１２３、登録部１２４、検索要求受付部１２５、検索条件生成部１２６、検索部１２７等を含む。これら各部は、情報管理装置１０にインストールされたプログラムがＣＰＵ１０４に実行させる処理により実現される。基盤部１２は、また、移動体情報記憶部１３１、施設情報記憶部１３２、及びエリア情報記憶部１３３等を含む。これら各記憶部は、補助記憶装置１０２又は情報管理装置１０とネットワークを介して接続される記憶装置等を用いて実現可能である。
【００２１】
移動体情報受信部１２１は、移動体の位置情報及び属性情報等を逐次的に受信する。以下、移動体の位置情報及び属性情報等を移動体情報という。移動体情報は、移動体端末２０ごとに、適当なタイミングで受信される。例えば、移動体情報は、一定周期ごと、又は位置が所定量変化するたびに受信される。移動体情報は、移動体通信網を介して各移動体端末２０から直接的に受信されてもよいし、移動体情報を管理している他のコンピュータシステムより取得又は受信されてもよい。後者の場合、他のコンピュータシステムは、一種類に限定されなくてもよい。他のコンピュータシステムの一例として、テレマティクスサービスを提供するコンピュータシステムが挙げられる。
【００２２】
なお、移動体情報が取得されるタイミングは、移動体端末２０ごとに異なっていてもよい。すなわち、全ての移動体端末２０に関して、同じ日時における移動体情報が受信されなくてもよい。
【００２３】
登録要求受付部１２２は、施設の位置情報及び属性情報（以下、「施設情報」という。）やエリアの位置情報及び属性情報（以下、「エリア情報」という。）の登録要求をサービス部１１より受け付ける。すなわち、登録要求受付部１２２は、基盤部１２が提供するＡＰＩの一部を構成する。但し、登録要求受付部１２２が、積極的に、施設情報やエリア情報等を他のコンピュータシステムより取得してもよい。
【００２４】
位置キー生成部１２３は、移動体情報受信部１２１によって受信された、即ち受け付けられた移動体情報や、登録要求受付部１２２によって受け付けられた施設情報又はエリア情報に関するキーを生成する。キーとは、ＫＶＳ（Key-Value Store）におけるキーである。すなわち、本実施の形態では、ＫＶＳを用いて、移動体情報、施設情報、及びエリア情報が管理される。なお、本実施の形態では、移動体、施設、又はエリアの位置の緯度及び経度に基づいてキーが生成される。当該キーを、「位置キー」と呼ぶ。
【００２５】
登録部１２４は、位置キー生成部１２３によって生成された位置キーに対応付けて、移動体情報、施設情報、又はエリア情報を、移動体情報記憶部１３１、施設情報記憶部１３２、又はエリア情報記憶部１３３に登録する。
【００２６】
移動体情報記憶部１３１は、位置キーに対応付けて移動体情報を記憶するＫＶＳ型のデータベースである。施設情報記憶部１３２は、位置キーに対応付けて施設情報を記憶するＫＶＳ型のデータベースである。エリア情報記憶部１３３は、位置キーに対応付けてエリア情報を記憶するＫＶＳ型のデータベースである。
【００２７】
検索要求受付部１２５は、移動体情報、施設情報、又はエリア情報の検索要求をサービス部１１より受け付ける。検索条件生成部１２６は、検索要求に指定されたパラメータに基づいて、移動体情報記憶部１３１、施設情報記憶部１３２、又はエリア情報記憶部１３３に対する検索に適した検索条件を生成する。より詳しくは、検索条件生成部１２６によって、検索要求に指定されたパラメータに基づいて、一以上の位置キーが生成される。検索部１２７は、検索条件生成部１２６によって生成された位置キーを用いて、移動体情報、施設情報、又はエリア情報の検索を行う。
【００２８】
以下、情報管理装置１０が実行する処理手順について説明する。まず、位置キーの生成処理について説明する。
【００２９】
図４は、位置キーの生成処理の処理手順の一例を説明するためのフローチャートである。当該処理手順は、移動体情報等の登録時や検索時における上位の処理手順から呼び出されるものであるが、説明の便宜上、上位の処理手順よりも先に説明する。
【００３０】
ステップＳ３０１において、位置キー生成部１２５は、処理対象の緯度及び経度のそれぞれを、数値から文字列に変換する。したがって、緯度を示す文字列（以下、「緯度文字列」という。）と、経度を示す文字列（以下、「経度文字列」という。）とが生成される。ここでは、処理対象の緯度及び経度は、（３５．５６７８，１３９．１２３４）であるとする。したがって、緯度文字列は、「３５．５６７８」であり、経度文字列は、「１３９．１２３４」である。なお、緯度の範囲は、＋９０度（北緯）〜−９０度（南緯）であるとする。すなわち、南緯は、マイナス（−）で表現されることとする。また、経度の範囲は、＋１８０度（東経）〜−１８０度（西経）であるとする。すなわち、西経は、マイナス（−）で表現されることとする。なお、北緯及び東経は、プラス（＋）で表現されるが、数値である北緯及び東経には、「＋」は明示的には付加されていなくてもよい。また、緯度および経度の、どの角度範囲を「＋」とし、どの角度範囲をマイナス（−）とするかは、上記例に限るものではない。
【００３１】
続いて、位置キー生成部１２５は、緯度文字列及び経度文字列を所定の形式に変換する（Ｓ３０２）。まず、整数部分が３桁となるように、整数部分が１桁または２桁の場合には文字「０（ゼロ）」が先頭に挿入される。したがって、緯度文字列は「０３５．５６７８」となる。経度文字列は、この例では整数部分は当初から３桁であるため、「１３９．１２３４」のままである。また、元の数値としての緯度及び経度に基づいて、緯度文字列及び経度文字列の先頭に「＋」又は「−」が付加される。したがって、緯度文字列は「＋０３５．５６７８」となり、経度文字列は、「＋１３９．１２３４」となる。また、小数点を示す文字（「．」）が除去される。したがって、緯度文字列は「＋０３５５６７８」となる。経度文字列は、「＋１３９１２３４」となる。
【００３２】
以上で所定の形式への変換は完了する。
【００３３】
続いて、位置キー生成部１２５は、経度文字列の最上位桁から順に１つの文字を取得し、当該文字を作業用の文字列変数（以下、「作業用変数」という。）の先頭に追加する（Ｓ３０３）。したがって、最初にステップＳ３０４が実行されるときは、「＋１３９１２３４」より「＋」が取得され、作業用変数に追加される。
【００３４】
続いて、位置キー生成部１２５は、緯度文字列の最上位桁から順に１つの文字を取得し、当該文字を作業用変数の先頭に追加する（Ｓ３０４）。したがって、最初にステップＳ３０３が実行されるときは、「＋０３５５６７８」より「＋」が取得され、作業用変数に追加される。なお、ステップＳ３０４における作業容変数は、ステップＳ３０３における作業用変数は同一のものである。したがって、最初にステップＳ３０３及びＳ３０４が終了した時点において、作業用変数の内容は、「＋＋」となる。なお、ステップＳ３０３とステップＳ３０４とは実行される順序を問わない。
【００３５】
ステップＳ３０３及びＳ３０４は、緯度文字列及び経度文字列の全ての桁（全ての文字）が処理されるまで繰り返し実行される（Ｓ３０５）。その結果、緯度文字列及び経度文字列のそれぞれの最上位桁から順に同じ桁の文字が１桁ずつ交互に配列された一つの文字列が作業用変数に格納される。上記の例では、「＋＋１０３３９５１５２６３７４８」という文字列が作業用変数に格納される。当該文字列が、位置キーとしての文字列である。したがって、位置キー生成部１２５は、作業用変数に格納された値、すなわち位置キーを返却する（Ｓ３０６）。
【００３６】
上記のように生成される位置キーでは、一方の位置キーに他方の位置キーが前方一致する場合、当該他方の位置キーに係る範囲は、当該一方の位置キーに係る範囲に含まれることを意味する。この点については、後述される。なお、位置キーに係る範囲とは、当該位置キーの緯度及び経度の精度に応じた単位を一辺とする矩形領域をいう。
【００３７】
続いて、移動体情報の登録処理の処理手順について説明する。図５は、移動体情報の登録処理の処理手順の一例を説明するためのフローチャートである。
【００３８】
ステップＳ１０１において、移動体情報受信部１２１は、移動体情報の登録要求を受信する（Ｓ１０１）。移動体情報には、例えば、移動体の識別情報（以下、「移動体ＩＤ」という。）、代表位置の位置情報、及び移動体のサイズ情報等が含まれている。移動体に関するその他の属性情報が、移動体情報に含まれていてもよい。
【００３９】
サイズ情報は、緯度及び経度の２次元座標系に対して移動体が占める範囲を一以上の矩形領域の集合によって表現した情報である。移動体の範囲を構成する各矩形領域の指定方法は、例えば、図６に示されるような三つの方法が有る。
【００４０】
図６は、移動体の範囲を構成する各矩形領域の指定方法の一例を示す図である。図６においては、図の左右方向が経度、図の上下方向が緯度を便宜的に表している。同図では、（１）〜（３）の三つの方法が例示されている。
【００４１】
（１）の方法は、一組の緯度及び経度を指定する方法である。この場合、当該緯度及び経度を左下頂点ｐ１とし、当該緯度及び経度の精度（小数点以下の有効桁数）に応じた単位を一辺とする矩形領域が指定されたことになる。例えば、緯度及び経度の精度が１０００分の１であれば、一辺が１０００分の１度の矩形領域が指定されたことになる。また、緯度及び経度の精度が１００００分の１であれば、一辺が１００００分の１度の矩形領域が指定されたことになる。なお、本実施の形態において、或る範囲に関して左下頂点とは、当該範囲において緯度の最小値及び経度の最小値が示す位置をいう。また、或る範囲に関して右上頂点とは、当該範囲において緯度の最大値及び経度の最大値が示す位置をいう。
【００４２】
（２）の方法は、二組の緯度及び経度を指定する方法である。この場合、一組目の緯度及び経度を左下頂点ｐ２とし、二組目の緯度及び経度を右上頂点ｐ３とする矩形領域が指定されたことになる。
【００４３】
（３）の方法は、一つの緯度及び経度と、半辺を指定する方法である。この場合、当該緯度及び経度を中心点ｐ４（対角線の交点）とし、当該半辺ｒを中心点からの四方への距離とする矩形領域が指定されたことになる。例えば、半辺として指定される距離の単位としては、メートルが考えられる。
【００４４】
なお、上記（１）〜（３）以外の方法で、矩形領域が指定されてもよい。また、サイズ情報において複数の矩形領域が指定される場合（すなわち、移動体の範囲が、複数の矩形領域の集合である場合）、上記（１）〜（３）の指定方法が混在していてもよい。したがって、サイズ情報は、例えば、図７に示されるようなデータ構造を有する。
【００４５】
図７は、サイズ情報のデータ構造の例を示す図である。同図に示されるように、サイズ情報は、矩形領域ごとに、代表位置の位置と大きさの指定方法と値とが指定される。大きさの指定方法は例えば、上記の（１）〜（３）のいずれに該当する指定方法である。値は例えば、上記の（１）〜（３）に応じた値である。
【００４６】
代表位置の位置情報は、移動体の代表位置の緯度及び経度である。代表位置は、移動体を一点で表現する場合の当該一点の位置をいう。
【００４７】
続いて、位置キー生成部１２３は、サイズ情報が示す矩形領域の集合を構成する正規化された各セルの位置キーの生成処理を実行する（Ｓ１０２）。本実施の形態において、セルとは、或る範囲を表現するために使用される単位領域あり、緯度と経度との２次元座標系において、同一の桁（精度）の緯線及び経線のメッシュ又は格子若しくは交差によって形成される正方形をいう。セルの一辺の長さは、セルの左下頂点の緯度及び経度の精度に基づいて定まる。例えば、左下頂点の緯度及び経度の精度が１０００分の１度で指定されていれば、一辺が１０００分の１度の矩形領域が指定されたことになる。また、左下頂点の緯度及び経度の精度が１００００分の１度で指定されていれば、一辺が１００００分の１度の矩形領域が指定されたことになる。また、セル群の正規化とは、或る精度のセル群に関して、上位の桁に統合できるセル群が有れば統合することをいう。上位の桁に統合できるセル群とは、例えば、１００００分の１のセル群が有る場合、１０００分の１の単位のセルに含まれる１００個のセル群をいう。また、セルの位置キー又はセルに対応する位置キーとは、セルの左下頂点の緯度及び経度に基づいて生成される位置キーをいう。
【００４８】
したがって、ステップＳ１０２では、サイズ情報が示す範囲を構成する矩形領域が一以上のセルに変換され、当該セルごとに、左下頂点の位置キーが生成される。なお、当該セルが複数の場合、各セルの精度（単位又は大きさ）は、必ずしも共通ではない。上記したように、セル群の正規化が行われる可能性が有るからである。
【００４９】
続いて、登録部１２４は、生成された位置キーごとに、移動体情報に含まれている移動体ＩＤ、代表位置、サイズ情報、及び属性情報等を値（Ｖａｌｕｅ）として対応付けて、移動体情報記憶部１３１に登録する（Ｓ１０３）。
【００５０】
図８は、移動体情報記憶部の構成例を示す図である。同図に示されるように、移動体情報記憶部１３１は、キーに対応付けて値を記憶する。キーには、緯度文字列及び経度文字列に基づいて生成された位置キーが記憶される。位置キーの生成方法については、後述される。値は、一以上の行を含む。各行は、一つの移動体に対応し、ｉｄ、データ、及び登録日時の三つの項目（列）を含む。ｉｄには、各移動体を一意に識別可能な移動体ＩＤが記憶される。データには、代表位置を示す緯度及び経度、サイズ情報等、並びにその他の属性情報等が記憶される。登録日時は、行が登録された日時である。サイズ情報は、例えば図７に例示したデータ構造を有していても良い。なお、一つの位置キーに対して、複数の行（複数の移動体）が対応付けられうるのは、異なる時期に、同じ緯度及び経度に対して複数の移動体が位置しうるからである。
【００５１】
また、その範囲が、複数のセルにまたがる移動体に関しては、セルごとに、当該セルの左下頂点に対応する位置キーに対応づけられて、値が記憶される。同図では、移動体ＩＤが、「ｉｄ６６６６」である移動体に関して、三つの位置キーが割り当てられている例が示されている。
【００５２】
なお、図８に示される構成は一例であり、値の構成は適宜変更されてよい。
【００５３】
図５の処理は、移動体情報が受信されるたびに実行される。したがって、複数の移動体のそれぞれに関して、刻々と移動体情報が受信され、図８に示されるような形態で、移動体情報記憶部１３１に登録される。
【００５４】
一方、移動体情報記憶部１３１は、ＫＶＳエンジンの機能として、登録後所定時間が経過したデータは削除するように設定されている。したがって、移動体情報記憶部１３１に登録されたデータは、所定時間経過後に削除される。このことは、基本的に、各移動体に関して、最後に受信された位置情報が、移動体情報記憶部１３１において管理されることを意味する。
【００５５】
なお、図５では、移動体情報の登録処理を説明したが、登録要求受付部１２２が、施設情報又はエリア情報の登録要求を受け付けた場合も、基本的に同様の処理手順が実行される。ただし、施設情報に関しては、移動体ＩＤは施設の識別情報（施設ＩＤ）に置き換えられ、登録先は施設情報記憶部１３２である。また、エリア情報に関しては、移動体ＩＤはエリアの識別情報（エリアＩＤ）に置き換えられ、登録先はエリア情報記憶部１３３である。更に、施設情報記憶部１３２及びエリア情報記憶部１３３は、登録後所定時間経過したデータの自動削除は行わないように設定されている。施設やエリアは、基本的に、移動体と異なり、位置情報が刻々と変化するものではないからである。
【００５６】
続いて、ステップＳ１０２の詳細について説明する。図９〜図１２は、矩形領域の集合を構成する正規化された各セルの位置キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【００５７】
ステップＳ２０１において、位置キー生成部は、図７に示されるようなデータ構造によって指定された矩形領域の集合の中の一つの矩形領域（以下、「対象矩形領域」という。）を処理対象とする。
【００５８】
ここでは、図１３に示されるような矩形領域の集合が指定されたとする。図１３は、矩形領域の集合の一例を示す図である。同図において、最小の目盛りは、緯度方向及び経度方向共に１／１００００度であるとする。同図では、矩形領域Ｒ１、矩形領域Ｒ２、矩形領域群Ｒ３、矩形領域群Ｒ４、矩形領域Ｒ５、矩形領域群Ｒ６、矩形領域Ｒ７、及び矩形領域群Ｒ８が、指定された矩形領域の集合を構成する。
【００５９】
矩形領域Ｒ１は、１００００分の１度の精度の二組の緯度及び経度によって指定された１００００分の１度を１辺とする矩形領域である。矩形領域Ｒ２は、一組目の緯度及び経度が１０００分の１度で指定され、二組目の緯度及び経度が１００００分の１度の精度で指定された、緯度方向の長さを１０００分の１度とし、経度方向の長さを１００００分の８度とする矩形領域である。矩形領域群Ｒ３は、それぞれ、１００００分の１度の精度の一組の緯度及び経度によって指定された、４個の矩形領域の集合である。矩形領域群Ｒ４は、それぞれ、１００００分の１度の精度の一組の緯度及び経度によって指定された、２０個の矩形領域の集合である。矩形領域Ｒ５は、１００００分の１度の精度の一組の緯度及び経度によって指定された、１個の矩形領域である。矩形領域群Ｒ６は、それぞれ、１００００分の１度の精度の一組の緯度及び経度によって指定された、９個の矩形領域の集合である。矩形領域Ｒ７は、中心点ｐ５と半辺ｒ５とによって指定された、一辺を１０００分の１度とする矩形領域である。矩形領域群Ｒ８は、それぞれ、１００００分の１度の精度の一組の緯度及び経度によって指定された、９９個の矩形領域の集合である。すなわち、Ｂによって示される部分は、矩形領域群Ｒ８には含まれない。
【００６０】
ステップＳ２０１では、このような矩形領域のうちの一つが対象矩形領域とされる。矩形領域群Ｒ３、Ｒ４、Ｒ６、及びＲ８に含まれる矩形領域に関しても、それぞれ、一つずつ処理対象とされる。
【００６１】
続いて、位置キー生成部１２３は、対象矩形領域が、中心点及び半辺によって指定されているか否かを判定する（Ｓ２０２）。中心点及び半辺によって対象矩形領域が指定されている場合（Ｓ２０２でＹｅｓ）、位置キー生成部１２３は、中心点（緯度及び経度）及び半辺（メートル）によって特定される範囲の左下頂点の緯度及び経度と、右上頂点の緯度及び経度とを算出する（Ｓ２０３）。算出方法は、公知の方法に従えばよい。
【００６２】
一方、対象矩形領域の指定が、中心点及び半辺ではない場合（Ｓ２０２でＮｏ）、位置キー生成部１２３は、対象矩形領域は、一組の緯度及び経度によって指定されているか否かを判定する（Ｓ２０４）。一組の緯度及び経度によって対象矩形領域が指定されている場合（Ｓ２０４でＹｅｓ）、位置キー生成部１２３は、当該緯度及び経度を左下頂点とし、当該緯度及び経度の精度に応じた長さを一辺とするセルの右上頂点の緯度及び経度を求める（Ｓ２０５）。
【００６３】
一組の緯度及び経度によって対象矩形領域が指定されていない場合（Ｓ２０４でＮｏ）、本実施の形態では、二組の緯度及び経度によって対象矩形領域が指定されていることになる。したがって、この場合、位置キー生成部１２３は、特別な処理は行わない。
【００６４】
すなわち、ステップＳ２０６以降において、対象矩形領域は、左下頂点及び右上頂点のそれぞれの緯度及び経度によって特定されることとなる。
【００６５】
続いて、位置キー生成部１２３は、対象矩形領域の右上頂点の緯度から左下頂点の緯度を引いた値を変数ＷＬＡＴ（以下、「緯度幅ＷＬＡＴ」という。）に代入する。続いて、位置キー生成部１２３は、対象矩形領域の右上頂点の経度から左下頂点の経度を引いた値を変数ＷＬＯＮ（以下、「経度幅ＷＬＯＮ」という。）に代入する（Ｓ２０７）。続いて、位置キー生成部１２３は、緯度幅ＷＬＡＴの小数点以下の桁数を変数ＫＬＡＴに代入する（Ｓ２０８）。続いて、位置キー生成部１２３は、経度幅ＷＬＯＮの小数点以下の桁数を変数ＫＬＯＮに代入する（Ｓ２０９）。続いて、位置キー生成部１２３は、変数ＫＬＡＴの値と変数ＫＬＯＮの値とのうちの最大値を、変数ＫＭＡＸ（以下、「有効桁数ＫＭＡＸ」という。）に代入する（Ｓ２１０〜Ｓ２１２）。
【００６６】
続いて、位置キー生成部１２３は、有効桁数ＫＭＡＸが、小数点以下の桁数の限度値（例えば、「５」等）より大きい場合は（Ｓ２１３でＹｅｓ）、有効桁数ＫＭＡＸの値を、当該限度値に補正する（Ｓ２１４）。
【００６７】
続いて、位置キー生成部１２３は、ステップＳ２１５〜Ｓ２２２において、対象矩形領域を、有効桁数ＫＭＡＸの精度に応じた大きさのセル群に分割し、各セルに対する位置キーの生成を実行する。この点に関して、図を用いて説明する。
【００６８】
図１４は、矩形領域のセル群への分割の一例を示す図である。例えば、矩形領域Ｒ２が対象矩形領域である場合、有効桁数ＫＭＡＸは、４（すなわち、１００００分の１）である。したがって、矩形領域Ｒ２は１００００分の１度の粒度の８０個のセル群に分割される。また、矩形領域Ｒ５が対象矩形領域である場合、有効桁数ＫＭＡＸは、５（すなわち、１０００００分の１）である。したがって、矩形領域Ｒ５は１０００００分の１度の粒度の１００個のセル群に分割される。このような分割処理が、ステップＳ２１５〜Ｓ２２２において行われる。
【００６９】
ステップＳ２１５において、位置キー生成部１２３は、対象矩形領域の左下頂点の経度を変数ＬＬＯＮ（以下、「対象経度ＬＬＯＮ」という。）に代入する。続いて、位置キー生成部１２３は、左下頂点の緯度を変数ＬＬＡＴ（以下、「対象緯度ＬＬＡＴ」という。）に代入する（Ｓ２１６）。続いて、位置キー生成部１２３は、対象緯度ＬＬＡＴ及び対象経度ＬＬＯＮに基づく位置キーの生成処理（図４）を実行する（Ｓ２１７）。
【００７０】
続いて、位置キー生成部１２３は、生成された位置キーをリストＬに追加する（Ｓ２１８）。リストＬは、位置キーが記憶される一時的な記憶領域である。リストＬは、例えば、メモリ装置１０３又は補助記憶装置１０２等を用いて実現可能である。続いて、位置キー生成部１２３は、対象緯度ＬＬＡＴに対して、０．１の有効桁数ＫＭＡＸ乗（図１４の矩形領域Ｒ２では、０．１の４乗＝０．０００１）を乗じた値を加算する（Ｓ２１９）。続いて、位置キー生成部１２３は、対象緯度ＬＬＡＴの値が、対象矩形領域の右上頂点の緯度に達している否かを判定する（Ｓ２２０）。対象緯度ＬＬＡＴの値が、対象矩形領域の右上頂点の緯度に達していない場合（Ｓ２２０でＮｏ）、位置キー生成部１２３は、ステップＳ２１７以降を繰り返す。
【００７１】
対象緯度ＬＬＡＴの値が、対象矩形領域の右上頂点の緯度に達している場合（Ｓ２２０でＹｅｓ）、位置キー生成部１２３は、対象経度ＬＬＯＴに対して、０．１の有効桁数ＫＭＡＸ乗（図１４の矩形領域Ｒ２では、０．０００１）を加算する（Ｓ２２１）。続いて、位置キー生成部１２３は、対象経度ＬＬＯＮの値が、対象矩形領域の右上頂点の経度に達している否かを判定する（Ｓ２２２）。対象経度ＬＬＯＮの値が、対象矩形領域の右上頂点の経度に達していない場合（Ｓ２２２でＮｏ）、位置キー生成部１２３は、ステップＳ２１６以降を繰り返す。
【００７２】
対象経度ＬＬＯＮの値が、対象矩形領域の右上頂点の経度に達している場合（Ｓ２２２でＹｅｓ）、対象矩形領域は、図１４の矩形領域Ｒ２のように、有効桁数ＫＭＡＸの精度に応じた大きさのセルに分割され、各セルの左下頂点に対応する位置キーがリストＬに記録された状態となる。
【００７３】
続いて、位置キー生成部１２３は、図１０のステップＳ２２３〜Ｓ２４５において、上記で生成されたセル群のうち、上位の桁の精度のセルに統合できるものがあれば、統合するための処理を実行する。例えば、矩形領域Ｒ５が対象矩形領域である場合、図１４の矩形領域Ｒ５に含まれる１００個のセル群は、１００００分の１度の１個のセルに統合される。すなわち、元々１０００００分の１度の精度で指定されていた矩形領域Ｒ５は、１００００分の１度の精度のセルに変換されることになる。このような処理が、ステップＳ２２３〜Ｓ２４５において実行される。
【００７４】
ステップＳ２２３において、位置キー生成部１２３は、変数ＣＳＩＺＥに１．０を代入する（Ｓ２２３）。変数ＣＳＩＺＥは、統合予定のセルの粒度（一辺の長）さである。すなわち、最初は、一辺が１．０度のセルに統合可能であるか否かが試行される。以下、変数ＣＳＩＺＥを、「統合粒度ＣＳＩＺＥ」という。続いて、位置キー生成部１２３は、変数ｉに０を代入する（Ｓ２２４）。変数ｉは、ステップＳ２２５〜Ｓ２４４の実行回数を保持するための変数である。なお、ステップＳ２２５〜Ｓ２４４は、有効桁数ＫＭＡＸが示す回数繰り返される。
【００７５】
続いて、位置キー生成部１２３は、緯度幅ＷＬＡＴを統合粒度ＣＳＩＺＥによって除した値の整数部分を変数ＷＬＡＴＳＩＺＥに代入する（Ｓ２２５）。すなわち、緯度幅ＷＬＡＴに関して、統合粒度ＣＳＩＺＥを単位とした大きさが変数ＷＬＡＴＳＩＺＥに代入される。続いて、位置キー生成部１２３は、経度幅ＷＬＯＮを統合粒度ＣＳＩＺＥによって除した値の整数部分を変数ＷＬＯＮＳＩＺＥに代入する（Ｓ２２５）。すなわち、経度幅ＷＬＯＮに関して、統合粒度ＣＳＩＺＥを単位とした大きさが変数ＷＬＯＮＳＩＺＥに代入される。
【００７６】
続いて、位置キー生成部１２３は、変数ＷＬＡＴＳＩＺＥの値及び変数ＷＬＯＮＳＩＺＥの値が、それぞれ１以上であるか否かを判定する（Ｓ２２７、Ｓ２２８）。すなわち、対象矩形領域が、統合粒度ＣＳＩＺＥのセルを含む大きさを有するか否かが判定される
変数ＷＬＡＴＳＩＺＥの値及び変数ＷＬＯＮＳＩＺＥの値のいずれか一方が１未満である場合（Ｓ２２７でＮｏ又はＳ２２８でＮｏ）、ステップＳ２４３に進み、位置キー生成部１２３は、統合粒度ＣＳＩＺＥの値を１０．０によって除する。続いて、位置キー生成部１２３は、変数ｉに１を加算する（Ｓ２４４）。続いて、位置キー生成部１２３は、変数ｉの値が有効桁数ＫＭＡＸに達したか否かを判定する（Ｓ２４５）。変数ｉが有効桁数ＫＭＡＸに達してない場合（Ｓ２４５でＮｏ）、位置キー生成部１２３は、ステップＳ２２５以降を繰り返す。したがって、統合粒度ＣＳＩＺＥの値は、ステップＳ２２５以降が繰り返されるたびに１０分の１となる。
【００７７】
ステップＳ２２５以降が繰り返される過程において、変数ＷＬＡＴＳＩＺＥ及び変数ＷＬＯＮＳＩＺＥの双方の値が、１以上となった場合（Ｓ２２７でＹｅｓ、かつ、Ｓ２２８でＹｅｓ）、位置キー生成部１２３は、対象矩形領域の左下頂点の緯度に統合粒度ＣＳＩＺＥを加算した結果に関して、統合粒度ＣＳＩＺＥの単位未満（統合粒度の有効桁未満）を切り捨てることによって得られる値を変数ＳＬＡＴに代入する（Ｓ２２９）。すなわち、変数ＳＬＡＴ（以下、「統合左下緯度ＳＬＡＴ」という。）には、対象矩形領域の左下頂点の緯度より大きな値であって、統合粒度ＣＳＩＺＥの単位（精度）の最小値が格納される。例えば、統合粒度ＣＳＩＺＥの値が「０．００１」であり、対象矩形領域の左下頂点の緯度が「１３９．１２１９」である場合、「１３９．１２２」が統合左下緯度ＳＬＡＴに代入される。
【００７８】
続いて、位置キー生成部１２３は、対象矩形領域の右上頂点の緯度に関して、統合粒度ＣＳＩＺＥの単位未満（統合粒度の有効桁未満）を切り捨てることによって得られる値を変数ＥＬＡＴに代入する（Ｓ２３０）。すなわち、変数ＥＬＡＴ（以下、「統合右上緯度ＥＬＡＴ」という。）には、対象矩形領域の右上頂点の緯度以下の値であって、統合粒度ＣＳＩＺＥの単位の最大値が格納される。例えば、統合粒度ＣＳＩＺＥの値が「０．００１」であり、対象矩形領域の右上頂点の緯度が「１３９．１２３１」である場合、「１３９．１２３」が統合左下緯度ＳＬＡＴに代入される。
【００７９】
続いて、位置キー生成部１２３は、対象矩形領域の左下頂点の経度に統合粒度ＣＳＩＺＥを加算した結果に関して、統合粒度ＣＳＩＺＥの単位未満（統合粒度の有効桁未満）を切り捨てることによって得られる値を変数ＳＬＯＮに代入する（Ｓ２３１）。すなわち、変数ＳＬＯＮ（以下、「統合左下経度ＳＬＯＮ」という。）には、対象矩形領域の左下頂点の経度より大きな値であって、統合粒度ＣＳＩＺＥの単位（精度）の最小値が格納される。例えば、統合粒度ＣＳＩＺＥの値が「０．００１」であり、対象矩形領域の左下頂点の経度が「３５．５６０９」である場合、「３５．５６１」が統合左下経度ＳＬＯＮに代入される。
【００８０】
続いて、位置キー生成部１２３は、対象矩形領域の右上頂点の経度に関して、統合粒度ＣＳＩＺＥの単位未満（統合粒度の有効桁未満）を切り捨てることによって得られる値を変数ＥＬＯＮに代入する（Ｓ２３２）。すなわち、変数ＥＬＯＮ（以下、「統合右上経度ＥＬＯＮ」という。）には、対象矩形領域の右上頂点の経度以下の値であって、統合粒度ＣＳＩＺＥの単位の最大値が格納される。例えば、統合粒度ＣＳＩＺＥの値が「０．００１」であり、対象矩形領域の右上頂点の経度が「３５．５６２１」である場合、「３５．５６２」が統合左下経度ＳＬＯＮに代入される。
【００８１】
続いて、位置キー生成部１２３は、統合右上緯度ＥＬＡＴ−統合左下緯度ＳＬＡＴの値が０であるか、又は統合右上経度ＥＬＯＮ−統合左下経度ＳＬＯＮの値が０であるかを判定する（Ｓ２３３）。当該判定が肯定的な場合（Ｓ２３３でＹｅｓ）、ステップＳ２４３に進む。当該判定が否定的な場合（Ｓ２３３でＮｏ）、（統合左下緯度ＳＬＡＴ，統合左下経度ＳＬＯＮ）を左下頂点とし、（統合右上緯度ＥＬＡＴ，統合右上経度ＥＬＯＮ）を右上頂点とする矩形領域は、１以上の統合粒度ＣＳＩＺＥの単位のセルを含むことになる。そこで、位置キー生成部１２３は、ステップＳ２３４以降において、当該矩形領域に含まれるセル群を、統合粒度ＣＳＩＺＥの単位のセルに統合する。
【００８２】
ステップＳ２３４において、位置キー生成部１２３は、統合左下経度ＳＬＯＮを変数Ｋ１（以下、「対象左下経度Ｋ１」という。）に代入する。続いて、位置キー生成部１２３は、統合左下緯度ＳＬＡＴを変数Ｋ２（以下、「対象左下緯度Ｋ２」という。）に代入する（Ｓ２３５）。続いて、位置キー生成部１２３は、対象緯度Ｋ２及び対象経度Ｋ１に基づく位置キーの生成処理（図４）を実行する（Ｓ２３６）。続いて、位置キー生成部１２３は、生成された位置キーに前方一致する位置キー群をリストＬより削除する（Ｓ２３７）。すなわち、生成された位置キーが示すセルに含まれるセル群の位置キーがリストＬより削除される。続いて、位置キー生成部１２３は、生成された位置キーをリストＬに追加する（Ｓ２３８）。
【００８３】
続いて、位置キー生成部１２３は、対象左下緯度Ｋ２に統合粒度ＣＳＩＺＥを加算する（Ｓ２３９）。続いて、位置キー生成部１２３は、対象左下緯度Ｋ２が、統合右上緯度ＥＬＡＴに達しているか否かを判定する（Ｓ２４０）。対象左下緯度Ｋ２が、統合右上緯度ＥＬＡＴに達していない場合（Ｓ２４０でＮｏ）、位置キー生成部１２３は、ステップＳ２３６以降を繰り返す。
【００８４】
対象左下緯度Ｋ２が、統合右上経度ＥＬＡＴに達している場合（Ｓ２４０でＹｅｓ）、位置キー生成部１２３は、対象左下経度Ｋ１に統合粒度ＣＳＩＺＥを加算する（Ｓ２４１）。続いて、位置キー生成部１２３は、対象左下経度Ｋ１が、統合右上経度ＥＬＯＮに達しているか否かを判定する（Ｓ２４２）。対象左下経度Ｋ１が、統合右上経度ＥＬＯＮに達していない場合（Ｓ２４２でＮｏ）、位置キー生成部１２３は、ステップＳ２３５以降を繰り返す。
【００８５】
対象左下経度Ｋ１が、統合右上経度ＥＬＯＮに達している場合（Ｓ２４２でＹｅｓ）、位置キー生成部１２３は、上述したステップＳ２４３〜Ｓ２４５を実行する。統合粒度ＣＳＩＺＥを、対象矩形領域の緯度及び経度の精度よりも１桁上位の桁の単位まで変化させつつ、統合粒度ＣＳＩＺＥのセルへの統合が行われる。
【００８６】
ステップＳ２０１〜Ｓ２４６が、処理対象の全ての矩形領域に関して実行されると（Ｓ２４６でＹｅｓ）、対象矩形領域内に含まれるセル群のうち、上位の桁に統合可能なセル群は、上位の桁のセル群に統合された状態になる。
【００８７】
しかし、例えば、図１４の矩形領域Ｒ２とＲ４とを合わせた矩形領域は、１０００分の１度の単位の矩形領域１個に統合可能であるが、ステップＳ２０１〜Ｓ２４６では、統合されない。ステップＳ２０１〜Ｓ２４６は、指定された矩形領域ごとに処理が行われるため、矩形領域を跨った、言い換えれば矩形領域を超えたセル群の統合は行われないからである。
【００８８】
そこで、位置キー生成部１２３は、指定された矩形領域を跨ったセル群の統合処理を図１１のステップＳ２４７以降において実行する。
【００８９】
ステップＳ２４７において、位置キー生成部１２３は、リストＬに含まれている各位置キーに対応する全てのセル群を包含する最小の矩形領域を求める。すなわち、指定された全ての矩形領域を含む最小の矩形領域が求められる。
【００９０】
図１５は、指定された全ての矩形領域を含む最小の矩形領域を説明するための図である。同図に示されるように、指定された矩形領域を含む最小の矩形領域は、指定された矩形領域の左下頂点のうちの最小の緯度及び経度を左下頂点Ｐａとし、指定された矩形領域の右上頂点のうちの最大の緯度及び経度を右上頂点Ｐｂとする矩形領域Ｒａ（以下、「包含領域Ｒａ」という。）である。ステップＳ２４７では、左下頂点Ｐａの緯度及び経度と、右上頂点Ｐｂの緯度及び経度とが求められる。
【００９１】
続くステップＳ２４８〜図１２のＳ２９１では、図１２において破線で囲まれたステップを除いて、包含領域Ｒａに関して、図９のステップＳ２０６〜図１０のＳ２４５と同様の処理が実行される。したがって、図１２のステップＳ２６７でＮｏ（図１０のステップＳ２３３でＮｏに対応）と判定されたときは、図１６に示されるような状態が特定されている。
【００９２】
図１６は、包含領域において特定される統合粒度ＣＳＩＺＥ単位のセルの例を示す図である。同図に示されるように、（統合左下緯度ＳＬＡＴ，統合左下経度ＳＬＯＮ）を左下頂点とし、（統合右上緯度ＥＬＡＴ，統合右上経度ＥＬＯＮ）を右上頂点とする矩形領域内において、１０００分の１度の単位の３つのセルＣａ、Ｃｂ、及びＣｃが含まれていること特定される。
【００９３】
したがって、これら３つのセルごとに、当該セルに含まれるセル群について当該セルへの統合の可否が判定される。ここでは、図１２の破線で囲まれたステップについて説明する。
【００９４】
ステップＳ２７０において、位置キー生成部１２３は、対象緯度Ｋ２及び対象経度Ｋ１に基づく位置キーの生成を実行する（図４）。図１６の例では、最初にステップＳ２７０が実行されるときの対象緯度Ｋ２の値は、統合左下緯度ＳＬＡＴの値であり、対象経度Ｋ１の値は、統合左下経度ＳＬＯＮの値である。すなわち、対象緯度Ｋ２及び対象経度Ｋ１は、セルＣａの左下頂点の緯度及び経度である。
【００９５】
続いて、位置キー生成部１２３は、生成された位置キーに前方一致する位置キー群をリストＬより抽出する（Ｓ２７１）。本実施の形態において、一方の位置キーに他方の位置キーが前方一致する場合、当該他方の位置キーに係るセルは、当該一方の位置キーに係るセルに含まれることを意味する。したがって、ここでは、セルＣａに含まれるセル群の位置キー群が抽出される。続いて、位置キー生成部１２３は、生成された位置キーに完全一致する位置キーと、生成された位置キーよりも４文字以上長い位置キーとを、ステップＳ２７１において抽出された位置キー群より除去する（Ｓ２７２）。続いて、位置キー生成部１２３は、残った位置キー群の数が１００個であるか否かを判定する（Ｓ２７３）。すなわち、セルＣａよりも１桁精度の高い（１桁粒度の小さい）セル群をセルＣａに統合する場合、統合後のセルＣａには、１桁精度の高いセルが１０×１０＝１００個含まれている必要がある。したがって、１００個のセル群が、セルＣａ内に存在するか否かが判定される。
【００９６】
なお、ステップＳ２７２において、生成された位置キーよりも４文字以上長い位置キーとは、生成された位置キーに対応するセルよりも、２桁以上精度の高い、言い換えれば２桁以上粒度の小さいセルの位置キーである。２桁以上精度の高いセルを除くのは、例えば、１桁精度の高いセルが９９個存在し、残りの１個分のセルの領域には、２桁以上精度の高いセルが１個以上有るようなケースを考慮してのことである。仮に、２桁以上精度の高いセルが１個である場合、統合予定のセルには１００個のセルが含まれていると判定されてしまう。すなわち、統合予定のセルに対して１桁精度の高いセル群の数を得るために、生成された位置キーよりも４文字以上長い位置キーが除去されるのである。また、生成された位置キーに完全一致する位置キーに係るセルも、統合予定のセルに対して１桁精度の高いセルではない。したがって、生成された位置キーに完全一致する位置キーも除去される。
【００９７】
残った位置キー群の数が１００個である場合（Ｓ２７３でＹｅｓ）、位置キー生成部１２３は、生成された位置キーに前方一致する位置キーをリストＬから削除する（Ｓ２７４）。続いて、位置キー生成部１２３は、生成された位置キーをリストＬに追加する（Ｓ２７５）。一方、残った位置キー群の数が１００個である場合（Ｓ２７３Ｎｏ）、ステップＳ２７４及びＳ２７５は実行されない。
【００９８】
以上のような処理により、図１５に示されるセル群は、図１７に示されるように統合される。
【００９９】
図１７は、指定された矩形領域を跨いだセル群の統合結果の一例を示す図である。同図に示されるように、図１６のセルＣａに含まれる１００００分の１度の１００個のセル群は、一つのセルＣａに統合される。一方、セルＣｃに含まれる１００００分の１度のセル群は、９９個であるため、セルＣｃには統合されない。
【０１００】
このように、図９〜図１２の処理により、図１３に示される矩形領域群は、図１７に示されるようなセル群に分割される。
【０１０１】
なお、ステップＳ２８３において、位置キー生成部１２３は、処理結果としての位置キー群を含むリストＬを返却する。
【０１０２】
続いて、移動体情報の検索処理について説明する。図１８は、移動体情報の検索処理の処理手順の一例を説明するためのフローチャートである。
【０１０３】
ステップＳ５０１において、検索要求受付部１２５は、移動体情報の検索要求をサービス部１１より受け付ける。なお、サービス部１１は、例えば、移動体端末２０や、非図示の固定端末からの検索要求に応じて、検索要求受付部１２５に対して検索要求を入力する。
【０１０４】
検索要求には、移動体情報の検索範囲を示す情報及び該検索範囲の意味が指定される。検索範囲は、移動体のサイズ情報と同じ形式で指定される。すなわち、検索範囲は、矩形領域の集合によって指定される。各矩形領域の指定方法も、サイズ情報の場合と同様である。したがって、検索範囲は、図７に示されるようなデータ構造によって表現される。
【０１０５】
検索範囲の意味とは、当該検索範囲が含むもの、すなわち、検索範囲に含まれるものを検索するのか、又は当該検索範囲が含まれるもの、すなわち、検索範囲を含むものを検索するのかを示す情報である。なお、後者に関しては、特に、施設情報やエリア情報に関する検索時に有効である。例えば、ある移動体の範囲に含まれる他の移動体の情報を検索するような場合は、前者の検索に該当する。また例えば、予め設定されたＸＸエリア内の移動体はいずれであるかというような検索を行なう場合が後者の検索に該当する。
【０１０６】
続いて、検索条件生成部１２６は、検索要求に指定された検索範囲に対応する一以上の位置キーを生成する（Ｓ５０２）。具体的には、検索範囲を、検索要求に指定された緯度及び経度の精度に応じたセルに分割した場合の各セルの左下頂点の緯度及び経度の集合が生成される。また、検索要求に指定された緯度及び経度の精度よりも上位の桁のセルが、検索範囲に含まれる場合は、当該上位の桁のセルによって、下位の桁のセル群が置き換えられる。すなわち、セル群の正規化が行われる。したがって、変換後の各位置キーの精度、すなわち小数点以下の有効桁数は、必ずしも共通ではない。
【０１０７】
生成された位置キーは、検索に用いられるキーである。当該位置キーと、移動体情報記憶部１３１に登録されている被検索情報としての位置キーとの混同を避けるため、生成された位置キーを、以下、「検索キー」という。なお、後述されるように、生成される検索キーの集合に含まれる検索キーは、検索要求に指定された検索範囲の意味に応じて異なる。
【０１０８】
続いて、検索条件生成部１２６は、検索要求に指定された検索範囲の意味に基づいて、検索範囲が含む移動体の検索か、検索範囲が含まれる移動体の検索かを判定する（Ｓ５０３）。検索範囲が含む移動体の検索である場合（Ｓ５０３でＹｅｓ）、検索部１２７は、検索範囲が含む移動体の検索処理を実行する（Ｓ５０４）。一方、検索範囲が含まれる移動体の検索である場合（Ｓ５０３でＮｏ）、検索部１２７は、検索範囲が含まれる移動体の検索処理を実行する（Ｓ５０５）。続いて、検索部１２７は、結果データを検索結果としてサービス部１１に応答する（Ｓ５０６）。結果データとは、ステップＳ５０４又はＳ５０５の検索処理において、検索結果の移動体情報が格納されるデータである。その後、サービス部１１によって、検索結果が検索要求元の移動体端末２０又は非図示の固定端末等に返信される。但し、検索結果がそのまま返信されなくてもよい。サービス部１１によって、検索結果の加工が行われたり、当該検索結果に基づいて、基盤部１２に対して更なる検索等が行われたりした結果が、検索要求元に返信されてもよい。
【０１０９】
続いて、ステップＳ５０２の詳細について説明する。図１９は、検索範囲に対応する検索キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【０１１０】
ステップＳ５１１において、検索条件生成部１２６は、検索要求に指定された検索範囲の意味に基づいて、検索範囲が含む移動体の検索か、検索範囲が含まれる移動体の検索かを判定する。検索範囲が含む移動体の検索である場合（Ｓ５１１でＹｅｓ）、位置キー生成部１２３は、検索範囲に係る矩形領域の集合を構成する正規化された各セルの位置キーの生成処理を実行する（Ｓ５１２）。すなわち、検索範囲に係る矩形領域の集合に関して、図９〜図１２において説明した処理が実行される。その結果、検索範囲に係る矩形領域を構成する正規化されたセル群に含まれるセルごとに、位置キーが生成され、リストＬに格納される。当該位置キーが、検索範囲が含む移動体を検索するための検索キーとして用いられる。
【０１１１】
一方、検索範囲が含まれる移動体の検索である場合（Ｓ５１１でＮｏ）、検索条件生成部１２６は、検索範囲が含まれる移動体を検索するための位置キーの生成処理を実行する（Ｓ５１３）。生成された位置キーは、検索範囲が含まれる移動体を検索するための検索キーとして用いられる。
【０１１２】
続いて、検索条件生成部１２６は、ステップＳ５１２又はＳ５１３において生成された位置キー群（検索キー群）を格納するリストＬを返却する（Ｓ５１４）。
【０１１３】
続いて、図１９のステップＳ５１３の詳細について説明する。図２０は、検索範囲が含まれる移動体を検索するための位置キーの生成処理の処理手順の一例を説明するためのフローチャートである。
【０１１４】
ステップＳ５２１において、位置キー生成部１２３は、検索範囲に係る矩形領域の集合を構成する正規化された各セルの位置キーの生成処理を実行する。すなわち、検索範囲に係る矩形領域の集合に関して、図９〜図１２において説明した処理が実行される。その結果、検索範囲に係る矩形領域を構成する正規化されたセル群に含まれるセルごとに、位置キーが生成され、リストＬに格納される。
【０１１５】
続いて、検索条件生成部１２６は、リストＬに含まれる位置キー群うちの一つの位置キー（以下、「対象キー」という。）を処理対象とする（Ｓ５２２）。続いて、検索条件生成部１２６は、対象キーの小数点以下の部分の文字数−２を、変数ＫＭＡＸに代入する（Ｓ５２３）。本実施の形態の位置キーは、整数部分が６文字（緯度の３文字＋経度の３文字）であり、符号部分（「＋＋」）が２文字である。したがって、対象キーの文字数から８を引いて更に２を引いた値が変数ＫＭＡＸに代入される。
【０１１６】
続いて、検索条件生成部１２６は、対象キーの先頭から８＋変数ＫＭＡＸまでの文字数の文字列を位置キーとして作業用の記憶領域（作業用領域）に記録する（Ｓ５２４）。したがって、最初は、対象キーの末尾の２文字分が除去された位置キーが作業用領域に追加される。なお、末尾の２文字分が除去された位置キーは、対象キーが示す緯度及び経度の末尾の１桁が除去された緯度及び経度に対応する位置キーである。すなわち、対象キーよりも１桁上位の桁に対応する（１桁上位の桁に丸められた）位置キーである。
【０１１７】
続いて、検索条件生成部１２６は、変数ＫＭＡＸから２を減算する（Ｓ５２５）。ステップＳ５２４及びＳ５２５は、変数ＫＭＡＸの値が０未満になるまで繰り返される（Ｓ５２６）。その結果、対象キーの緯度及び経度に関して、整数部分の桁までの１桁ごとに、位置キーが生成され、作業用領域に追加される。具体例として、対象キーが、「＋＋１０３３９５１５２６２１３２」であるとすると、更に以下の位置キーが、リストＬに追加される。
＋＋１０３３９５１５２６２１３２
＋＋１０３３９５１５２６２１
＋＋１０３３９５１５２６
＋＋１０３３９５１５
＋＋１０３３９５
ステップＳ５２２〜ＳＳ５２６が、リストＬに含まれている全ての位置キーに関して実行されると（Ｓ５２７でＹｅｓ）、検索条件生成部１２６は、作業用領域に記録されている位置キー群をリストＬに追加する（Ｓ５２８）。すなわち、ステップＳ５２２〜ＳＳ５２６において新たに生成された位置キーが、検索キーとされる。
【０１１８】
このように、検索範囲を含む移動体の検索の場合、リストＬには、当初からリストＬに含まれている位置キー群に加え、当該各位置キーが上位の桁に丸められた位置キー群が検索キーとされる。この理由については後述される。なお、当初からリストＬに含まれている位置キーと、丸められた位置キーとを区別する場合、前者を「当初検索キー」といい、後者を「丸め検索キー」という。
【０１１９】
続いて、図１８のステップＳ５０４の詳細について説明する。図２１は、検索範囲が含む移動体の検索処理の処理手順の一例を説明するためのフローチャートである。
【０１２０】
ステップＳ５３１において、検索部１２７は、図１８のステップＳ５０２において生成されたリストＬに含まれる検索キー群のうちの一つの検索キーを処理対象とする。続いて、検索部１２７は、検索キーに前方一致する位置キーを、移動体情報記憶部１３１より検索する（Ｓ５３２）。なお、検索キーに前方一致する位置キーとは、当該検索キーの全てを、前方からの一部又は全部に含む位置キーである。前方からの全部に含む場合は、完全一致に該当する。
【０１２１】
検索キーに前方一致する位置キーは、検索キーが示す範囲（セル）が含む移動体を構成するセルの左下頂点に対応する位置キーに相当する。位置キーが検索キーに前方一致することは、当該検索キーの示す範囲（セル）が当該位置キーに係るセルを含むこととなる理由について説明する。
【０１２２】
図２２は、検索キーとの前方一致の意義を説明するための図である。同図では、検索キーに対応する緯度及び経度が、（３５．５６１，１３９．１２２）であり、移動体情報記憶部１３１に記憶されている移動体の位置キーに対応する緯度及び経度が（３５．５６１２，１３９．１２２３）である例が示されている。この場合、検索キーが示すセルは、図中太線で囲まれたセルｃ１に相当する。一方、移動体の位置キーが示すセルは、図中の黒い矩形で示されたセルｃ２に相当する。同図より明らかなように、セルｃ１はセルｃ２を含む。
【０１２３】
また、（３５．５６１，１３９．１２２）を位置キー（すなわち検索キー）に変換すると、「＋＋１０３３９５１５２６２１」となる。（３５．５６１２，１３９．１２２３）を位置キーに変換すると、「＋＋１０３３９５１５２６２１３２」となる。そして、当該位置キーは、当該検索キーに前方一致する。
【０１２４】
このように、位置キーが検索キーに前方一致する場合、当該位置キーが示すセルは、当該検索キーが示すセルに含まれるか又は一致することになる。位置キーのこのような特性によって、本実施の形態では、或る範囲に含まれる移動体を高速に検索することができる。
【０１２５】
換言すれば、本実施の形態では、緯度及び経度をＫＶＳのキーとする場合において、或る範囲に含まれるキーを検索する際に、このような前方一致による高速な検索を可能とするために、緯度及び経度は、位置キーの形式に変換されて、ＫＳＶのキーとされるのである。仮に、緯度及び経度の順に単純に接続した文字列を位置キーとした場合、上記のような前方一致による高速な検索は困難である。緯度及び経度の順に単純に接続した場合の文字列は、図２２の例において、検索キーは、「＋３５５６１＋１３９１２２」となる。また、移動体の位置キーは、「＋３５５６１２＋１３９１２２３」となる。当該位置キーは、当該検索キーに前方一致しない。また、ＫＶＳの特性上、「＋３５５６１＊＋１３９１２２＊」といった正規表現によるキーの検索を行うのは困難である。なお、ここで、「＊」は、ワイルドカードを示す。
【０１２６】
なお、上記したように、セルの大きさは、当該セルの左下頂点を示す緯度及び経度の精度に依存する。セルｃ１に関しては、左下頂点の緯度及び経度が、１０００分の１度単位である。したがって、セルｃ１は、１辺が１０００分の一度である矩形領域に相当する。一方、セルｃ２に関しては、左下頂点の緯度及び経度が、１００００分の１度単位である。したがって、セルｃ１は、１辺が１００００分の一度である矩形領域に相当する。仮に、セルｃ１と同じ位置を左下頂点とし、１辺が１００００分の一度であるセルを示したい場合、当該セルの左下頂点は、（３５．５６１０，１３９．１２２０）として指定されればよい。一方、セルｃ１と同じ大きさであって、左下頂点が（３５．５６１１，１３９．１２２１）とする範囲を指定したい場合、当該緯度及び経度を左下頂点とし、セルｃ１と同じ大きさの矩形領域に含まれる、一辺が１００００分の一度の１００個のセルによって、当該範囲が指定される。
【０１２７】
続いて、検索部１２７は、検索された位置キー群のうちの一つを処理対象（以下、「対象キー」という。）とする（Ｓ５３３）。続いて、検索部１２７は、対象キーに対する値を移動体情報記憶部１３１より取得する（Ｓ５３４）。続いて、検索部１２７は、取得された値より、移動体ＩＤのリストを抽出する（Ｓ５３５）。すなわち、当該値に含まれる各行から、ｉｄの値が取得される。続いて、検索部１２７は、当該移動体ＩＤ群のリストから、一つの移動体ＩＤを処理対象とする（Ｓ５３６）。続いて、検索部１２７は、処理対象とされた移動体ＩＤに対応付けられて代表位置を取得する（Ｓ５３７）。続いて、検索部１２７は、処理対象とされた移動体ＩＤに対応付けられているサイズ情報を取得する（Ｓ５３８）。続いて、検索部１２７は、処理対象とされた移動体ＩＤに対応付けられて属性情報を取得する（Ｓ５３９）。続いて、検索部１２７は、ステップＳ５３７〜Ｓ５３９において取得されたデータを結果データに追加する（Ｓ５４０）。結果データは、検索結果を格納するためのデータである。ステップＳ５３６〜Ｓ５４０は、ステップＳ５３５において抽出された全ての移動体ＩＤに関して実行される（Ｓ５４１）。また、ステップＳ５３４〜Ｓ５４１は、ステップＳ５３２において検索された全ての位置キーに関して実行される（Ｓ５４２）。
【０１２８】
ステップＳ５３１〜Ｓ５４２が、全ての検索キーに関して実行されると（Ｓ５４３でＹｅｓ）、図２１の処理は終了する。したがって、この時点の結果データが、図１８のステップＳ５０６において返信される。
【０１２９】
続いて、図１８のステップＳ５０５の詳細について説明する。図２３は、検索範囲が含まれる移動体の検索処理の処理手順の一例を説明するためのフローチャートである。
【０１３０】
ステップＳ５５１において、検索部１２７は、図１８のステップＳ５０２において生成されたリストＬに含まれる検索キー群のうちの一つの検索キーを処理対象とする。続いて、検索部１２７は、検索キーに完全一致する位置キーを、移動体情報記憶部１３１より検索する（Ｓ５５２）。
【０１３１】
図２０において説明した処理により、リストＬには、当初検索キーに加え、丸め検索キーが含まれている。したがって、例えば、丸め検索キーが、ステップＳ５５２における検索キーである場合、当該検索キーに完全一致する位置キーは、当初検索キーに対応するセルを含むセルに対応する位置キーということになる。また、当初検索キーが、ステップＳ５５２における検索キーである場合、当該検索キーに完全一致する位置キーは、当初検索キーに対応するセルと一致するセルに対応する位置キーということになる。
【０１３２】
なお、一つの検索キーに対応するセルは、検索範囲として指定された矩形領域群の全てを含む範囲であるとは限らない。一つの検索キーに対応するセルは、検索範囲の少なくとも一部を含むセルである。したがって、ステップＳ５５２では、検索範囲の少なくとも一部を含むセルに対応する位置キーが検索される。続くステップＳ５５３〜Ｓ５５９は、図２１のステップＳ５３３〜Ｓ５３９と同様である。
【０１３３】
続いて、検索部１２７は、処理対象とされた移動体ＩＤを管理テーブルに登録する（Ｓ５６０）。
【０１３４】
図２４は、管理テーブルの構成例を示す図である。同図において、管理テーブルの一つのレコードは、移動体ＩＤ、カウンタ、及び属性情報等を記憶可能である。カウンタの初期値は「０」である。なお、管理テーブルは、一時的に生成される記憶領域であり、例えば、メモリ装置１０３又は補助記憶装置１０２等を用いて実現可能である。
【０１３５】
ステップＳ５６０では、処理対象とされた移動体ＩＤと同じ移動体ＩＤを有するレコードが無い場合、新たなレコードが生成され、当該レコードに、処理対象の移動体ＩＤが記録される。また、当該レコードに、ステップＳ５５７〜Ｓ５５９において取得された情報が属性情報等として記録される。
【０１３６】
一方、処理対象とされた移動体ＩＤと同じ移動体ＩＤを有するレコードが有る場合、レコードの生成は行われない。すなわち、同じ移動体ＩＤに対して管理テーブルに登録されるレコードは最大で一つである。
【０１３７】
続いて、検索部１２７は、検索キーに前方一致する位置キーをリストＬから抽出する（Ｓ５６１）。続いて、検索部１２７は、抽出された位置キーの中で、文字数が最大のもの（最長の位置キー）の個数を、管理テーブルにおいて、処理対象とされた移動体ＩＤに対応するレコードのカウンタに加算する（Ｓ５６２）。ここで、抽出された位置キーの中で、文字数が最大のものとは、当該検索キーに対する当初検索キーである。したがって、カウンタには、当該検索キーに対する当初検索キーの数が加算される。
【０１３８】
ステップＳ５６０〜Ｓ５６２の処理の意義について説明する。検索範囲が含まれる移動体の検索では、検索範囲を構成するセルの全てを含む移動体が検索される必要がある。そして、検索範囲を構成するセルに対応する検索キーは、当初検索キーである。したがって、全部の当初検索キーに対応するセルをその範囲の一部又は全部とする移動体が有れば、それが目的とする移動体である。但し、当初検索キーでは、検索範囲を含む移動体を高速に検索するのは困難である。
【０１３９】
そこで、本実施の形態では、丸め検索キーが利用される。丸め検索キーの存在意義は、当初検索キーに対応するセルを含み、当該セルより大きな移動体のセルを高速に検索することにある。すなわち、或る位置キーが丸め検索キーに完全一致したということは、当該位置キーに対応するセルは、当該丸め検索キーの元である当初検索キーに対応するセルを含むということを意味する。そうすると、丸め検索キーによる検索結果は、当初検索キーの検索結果であるといえる。
【０１４０】
上記より、移動体ごとに、丸め検索キーに基づく検索のヒット回数を記録した場合に、その回数の累積値が、当初検索キーの総数と一致する移動体は、検索範囲を構成するセルの全てを含む移動体であるといえる。この検索のヒット回数を記録するための項目が、管理テーブルのカウンタである。
【０１４１】
但し、一つの丸め検索キーは、図２５に示されるように、複数の当初検索キーに対して共通である場合がある。
【０１４２】
図２５は、一つの丸め検索キーが複数の当初検索キーに対して共通する例を示す図である。
【０１４３】
同図には、１００００分の１度の単位のセルとして、図中の黒い四角で示されているセルｃ２１、ｃ２２、及びｃ２３と、これらのセルを包含する、１０００分の１度の単位のセルとして、図中の太線で示されているセルｃ１１とが示されている。ここで、セルｃ２１、ｃ２２、及びｃ２３のそれぞれの位置キーが当初検索キーであるとすると、セルｃ１１の位置キーは、セルｃ２１、ｃ２２、及びｃ２３に共通な丸め検索キーの一つである。
【０１４４】
したがって、セルｃ１１に係る丸め検索キーに基づく検索にヒットしたということは、三つの当初検索キーに基づく検索にヒットしたということになる。
【０１４５】
ステップＳ５６２では、このようなケースを考慮して、カウンタに単に１を加算するのではなく、抽出された位置キーの中で、文字数が最大のもの、すなわち最長の位置キーの個数を、カウンタに加算しているのである。なお、文字数が最大のものとは、当初検索キーを意味する。具体的には、図２５のセルｃ２１、２２、ｃ２３に関しては、１０００分の１度、１００分の１度、１０分の１度、又は１度を単位とする丸め検索キーが生成される。仮に、処理対象とされている検索キーが１００分の１度の丸め検索キーであったとする。この場合、当該丸め検索キーに前方一致するものとしてリストＬより抽出される位置キー群には、セルｃ２１、ｃ２２、又はｃ２３に係る当初検索キーのみならず、１００分の１度又は１０００分の１度のぞれぞれの丸め検索キーも含まれる。斯かる位置キー群の中で、セルｃ２１、ｃ２２、又はｃ２３に係る当初検索キーの文字数は、最長であるはずである。したがって、ステップＳ５６２において、抽出された位置キーの中で、文字数が最大のもの、すなわち最長の位置キーの個数をカウンタに加算するということは、当初検索キーのみの個数をカウンタに加算することを意味する。
【０１４６】
続くステップＳ５６３〜Ｓ５６５は、図２１のステップＳ５４１〜Ｓ５４３と同じである。すなわち、ステップＳ５５６〜Ｓ５６２は、ステップＳ５５５において抽出された全ての移動体ＩＤに関して実行される（Ｓ５６３）。また、ステップＳ５５４〜Ｓ５６３は、ステップＳ５５２において検索された全ての位置キーに関して実行される（Ｓ５６４）。更に、ステップＳ５５１〜Ｓ５６４は、リストＬに含まれている全ての検索キーに関して実行される（Ｓ５６５）。
【０１４７】
続いて、検索部１２７は、管理テーブルのレコード数が１以上であるか否かを判定する（Ｓ５６６）。管理テーブルのレコード数が１以上である場合（Ｓ５６６でＹｅｓ）、検索部１２７は、一つのレコードを処理対象とする（Ｓ５６７）。続いて、検索部１２７は、当該レコードのカウンタの値が、当初検索キーの数と同じであるか否かを判定する（Ｓ５６８）。Ｓ５６０〜Ｓ５６２に関して説明したように、当該カウンタの値が、当初検索キーの数と同じであるということは、当該レコードに記録されている移動体ＩＤに係る移動体は、検索範囲を含むこと、すなわち、当該検索範囲は、当該移動体に含まれることを意味する。したがって、当該カウンタの値が、当初検索キーの数と同じである場合（Ｓ５６８でＹｅｓ）、検索部１２７は、当該レコードの属性情報等を結果データに追加する（Ｓ５６９）。ステップＳ５６７〜Ｓ５６９が、管理テーブルに登録されている全てレコードに関して実行されると（Ｓ５７０でＹｅｓ）、図２３の処理は終了する。
【０１４８】
なお、上記では、移動体情報の検索処理を説明したが、検索要求受付部１２５が、施設情報又はエリア情報の検索要求を受け付けた場合も、検索先が施設情報記憶部１３２又はエリア情報記憶部１３３となる点を除き、基本的に同様の処理手順が実行される。すなわち、１台の車、一人の人が持っている移動体端末２０は、本システムにおいては、一番精度が細かい矩形領域として表現される。したがって、移動体よりも広い面積を持つ店舗やエリアの検索であっても考え方は同じである
移動体情報の検索処理に関して、具体例を示して説明する。図２６は、移動体情報の検索処理の第一の具体例を示す図である。同図では、検索要求Ｒｅｑ１において、検索範囲Ａ１の左下頂点として（１３９．１２１９，３５．５６０９）が指定され、右上頂点として（１３９．１２３１，３５．５６２１）が指定され、当該検索範囲が含む移動体の検索が要求された例が示されている。
【０１４９】
この場合、有効桁数ＫＭＡＸは、「４」となる。すなわち、検索範囲Ａ１の精度は、０．０００１度である。したがって、検索範囲Ａ１は、同図の（１）に示されるように、１辺を０．０００１度とする１４４個のセル群に分割される。但し、（３５．５６１，１３９．１２２）を左下頂点とし、（３５．５６２，１２９．１２３）を右上頂点とするセルに含まれるセル群は、同図の（２）に示されるセルＣ１ａに統合される。すなわち、セルＣ１ａの左下頂点（３５．５６１，１３９．１２２）に対応する一つの位置キーと、４４個のセル群Ｃ１ｂのそれぞれの左下頂点に対応する４４個の位置キーとが、検索キーとしてリストＬに追加される。
【０１５０】
その結果、リストＬに含まれているいずれかの検索キーに前方一致する位置キーが、移動体情報記憶部１３１より検索される。例えば、同図の（３）に示されるように三つの移動体Ａ、Ｂ、及びＣの移動体情報が移動体情報記憶部１３１に記憶されている場合、検索範囲Ａ１内に位置する移動体Ａの位置キーと、移動体Ｂの位置キーとは、リストＬに含まれるいずれかの検索キーに前方一致する。一方、検索範囲Ａ１外に位置する移動体Ｃの位置キーは、リストＬに含まれるいずれの検索キーにも前方一致しない。したがって、結果データＲｅｓ１には、移動体Ａの位置キーと、移動体Ｂの位置キーとが含まれる。
【０１５１】
図２７は、移動体情報の検索処理の第二の具体例を示す図である。同図では、検索要求Ｒｅｑ２において、検索範囲Ａ２の左下頂点の緯度及び経度として（１３９．１２２，３５．５６１）が指定され、右上頂点として（１３９．１２３，３５．５６２）が指定され、当該検索範囲が含む移動体の検索が要求された例が示されている。
【０１５２】
この場合、有効桁数ＫＭＡＸは、「３」となる。すなわち、検索範囲Ａ２の精度は、０．００１度である。したがって、検索範囲Ａ２は、同図の（２）に示されるように、１辺を０．００１度とする一つのセルＣ２として扱われる。すなわち、セルＣ２の左下頂点（１３９．１２２，３５．５６１）に対応する一つの位置キーが、検索キーとしてリストＬに追加される。
【０１５３】
その結果、リストＬに含まれているいずれかの検索キーに前方一致する位置キーが、移動体情報記憶部１３１より検索される。例えば、同図の（３）に示されるように三つの移動体Ａ、Ｂ、及びＣの移動体情報が移動体情報記憶部１３１に記憶されている場合、検索範囲Ａ２内に位置する移動体Ａの位置キーと、移動体Ｂの位置キーとは、リストＬに含まれる検索キーに前方一致する。一方、検索範囲Ａ２外に位置する移動体Ｃの位置キーは、リストＬに含まれる検索キーに前方一致しない。したがって、結果データＲｅｓ２には、移動体Ａの位置キーと、移動体Ｂの位置キーとが含まれる。
【０１５４】
図２８は、移動体情報の検索処理の第三の具体例を示す図である。同図では、検索要求Ｒｅｑ３において、検索範囲Ａ３の左下頂点の緯度及び経度として（１３９．１２２１，３５．５６１１）が指定され、右上頂点として（１３９．１２３，３５．５６２）が指定され、当該検索範囲が含む移動体の検索が要求された例が示されている。
【０１５５】
この場合、有効桁数ＫＭＡＸは、「４」となる。すなわち、検索範囲Ａ３の精度は、０．０００１度である。したがって、検索範囲Ａ３は、同図の（２）に示されるように、１辺を０．０００１度とする８１個のセル群Ｃ３に分割される。すなわち、セル群Ｃ３に含まれる各セルに対応する８１個の位置キーが、検索キーとしてリストＬに追加される。
【０１５６】
その結果、リストＬに含まれているいずれかの検索キーに前方一致する位置キーが、移動体情報記憶部１３１より検索される。例えば、同図の（３）に示されるように三つの移動体Ａ、Ｂ、及びＣの移動体情報が移動体情報記憶部１３１に記憶されている場合、検索範囲Ａ３内に位置する移動体Ａの位置キーと、移動体Ｂの位置キーとは、リストＬに含まれるいずれかの検索キーに前方一致する。一方、検索範囲Ａ３外に位置する移動体Ｃの位置キーは、リストＬに含まれるいずれの検索キーにも前方一致しない。したがって、結果データＲｅｓ３には、移動体Ａの位置キーと、移動体Ｂの位置キーとが含まれる。
【０１５７】
図２９は、移動体情報の検索処理の第四の具体例を示す図である。同図では、検索要求Ｒｅｑ４において、検索範囲Ａ４の左下頂点の緯度及び経度として（１３９．１２２１，３５．５６１１）が指定され、右上頂点として（１３９．１２２５，３５．５６１４）が指定され、当該検索範囲が含む移動体の検索が要求された例が示されている。
【０１５８】
この場合、有効桁数ＫＭＡＸは、「４」となる。すなわち、検索範囲Ａ４の精度は、０．０００１度である。したがって、検索範囲Ａ４は、同図の（２）に示されるように、１辺を０．０００１度とする１２個のセル群Ｃ４に分割される。すなわち、セル群Ｃ４に含まれる各セルに対応する１２個の位置キーが、検索キーとしてリストＬに追加される。
【０１５９】
その結果、リストＬに含まれているいずれかの検索キーに前方一致する位置キーが、移動体情報記憶部１３１より検索される。例えば、同図の（３）に示されるように三つの移動体Ａ、Ｂ、及びＣの移動体情報が移動体情報記憶部１３１に記憶されている場合、検索範囲Ａ４内に位置する移動体Ａの位置キーは、リストＬに含まれるいずれかの検索キーに前方一致する。一方、検索範囲Ａ４外に位置する移動体Ｂ及び移動体Ｃのそれぞれの位置キーは、リストＬに含まれるいずれの検索キーにも前方一致しない。したがって、結果データＲｅｓ４には、移動体Ａの位置キーが含まれる。
【０１６０】
図３０は、移動体情報の検索処理の第五の具体例を示す図である。同図では、検索要求Ｒｅｑ５において、検索範囲Ａ５の左下頂点の緯度及び経度として（１３９．１２１９，３５．５６０９）が指定され、右上頂点として（１３９．１２２５，３５．５６１４）が指定され、当該検索範囲が含む移動体の検索が要求された例が示されている。
【０１６１】
この場合、有効桁数ＫＭＡＸは、「４」となる。すなわち、検索範囲Ａ５の精度は、０．０００１度である。したがって、検索範囲Ａ５は、同図の（２）に示されるように、１辺を０．０００１度とする３０個のセル群Ｃ５に分割される。すなわち、セル群Ｃ５に含まれる各セルに対応する３０個の位置キーが、検索キーとしてリストＬに追加される。
【０１６２】
その結果、リストＬに含まれているいずれかの検索キーに前方一致する位置キーが、移動体情報記憶部１３１より検索される。例えば、同図の（３）に示されるように三つの移動体Ａ、Ｂ、及びＣの移動体情報が移動体情報記憶部１３１に記憶されている場合、検索範囲Ａ５内に位置する移動体Ａの位置キーは、リストＬに含まれるいずれかの検索キーに前方一致する。一方、検索範囲Ａ５外に位置する移動体Ｂ及び移動体Ｃのそれぞれの位置キーは、リストＬに含まれるいずれの検索キーにも前方一致しない。したがって、結果データＲｅｓ５には、移動体Ａの位置キーが含まれる。
【０１６３】
図３１は、移動体情報の検索処理の第六の具体例を示す図である。同図では、検索要求Ｒｅｑ６において、検索範囲Ａ６の左下頂点の緯度及び経度として（１３９．１２１９，３５．５６０９）が指定され、右上頂点として（１３９．１２２５，３５．５６１４）が指定され、当該検索範囲が含む移動体の検索が要求された例が示されている。
【０１６４】
この場合、有効桁数ＫＭＡＸは、「４」となる。すなわち、検索範囲Ａ６の精度は、０．０００１度である。したがって、検索範囲Ａ６は、同図の（２）に示されるように、１辺を０．０００１度とする３０個のセル群Ｃ６に分割される。すなわち、セル群Ｃ６に含まれる各セルに対応する３０個の位置キーが、検索キーとしてリストＬに追加される。
【０１６５】
その結果、リストＬに含まれているいずれかの検索キーに前方一致する位置キーが、移動体情報記憶部１３１より検索される。例えば、同図の（３）に示されるように二つの移動体Ａ及びＢの移動体情報が移動体情報記憶部１３１に記憶されているとする。移動体Ａの範囲は、五つのセルを含む。したがって、移動体Ａに関しては、五つの位置キーが移動体情報記憶部１３１に記憶されている。一方、移動体Ｂの範囲は、三つのセルを含む。したがって、移動体Ｂに関しては、三つの位置キーが移動体情報記憶部１３１に記憶されている。
【０１６６】
移動体Ａの範囲を構成する一つセルＡａは、検索結果Ａ６内に含まれる。したがって、セルＡａの位置キーは、リストＬに含まれるいずれかの検索キーに前方一致する。一方、検索範囲Ａ６外に位置する移動体Ａを構成する他のセルの位置キー、及び移動体Ｂを構成する全てのセルの位置キーは、リストＬに含まれるいずれの検索キーにも前方一致しない。したがって、結果データＲｅｓ６には、セルＡａの位置キーが含まれる。セルＡａは、移動体Ａを構成するセルであるため、移動体Ａが検索範囲に含まれる移動体とされる。
【０１６７】
すなわち、本実施の形態では、検索範囲に完全に含まれる移動体のみならず、その一部が検索範囲と重複する移動体も、検索結果に含まれる。仮に、検索範囲に完全に含まれる移動体のみを検索結果としたい場合、検索部１２７は、当該移動体を構成する全てのセルの位置キーが検索キーに前方一致する場合に、当該全てのセルの位置キーを検索結果とするようにすればよい。
【０１６８】
図３２は、移動体情報の検索処理の第七の具体例を示す図である。同図では、検索要求Ｒｅｑ７ａにおいて、検索範囲Ａ７の左下頂点の緯度及び経度として（１３９．１２２３，３５．５６１２）が指定され、右上頂点として（１３９．１２２４，３５．５６１３）が指定され、当該検索範囲を含む移動体の検索が要求された例が示されている。なお、検索要求Ｒｅｑ７ｂに示されるように、１００００分の１度を単位とする一組の緯度経度として（１３９．１２２３，３５．５６１２）が指定された場合も、検索範囲Ａ７と同じ矩形領域が指定されたことになる。
【０１６９】
この場合、有効桁数ＫＭＡＸは、「４」となる。すなわち、検索範囲Ａ７の精度は、０．０００１度である。したがって、検索範囲Ａ７に関して、同図の（２）に示されるように、１辺を０．０００１度とする１個のセルＣ７が生成される。ここでは、検索範囲Ａ７を含む移動体の検索であるため、セルＣ７に対応する当初検索キーのみならず、当初検索キーの小数点以下の部分を１桁ずつ（２文字ずつ）削除した丸め検索キーもリストＬに追加される（図２０参照）。同図では、セルＣ７より１桁上位のセルＣ８と、セルＣ７より２桁上位のセルＣ９とが図示されている。それより上位の桁のセルに関しては、便宜上、省略されているが、このような上位桁の各セルに対応する位置キーが、丸め検索キーとしてリストＬに追加される。
【０１７０】
その結果、リストＬに含まれているいずれかの検索キーに完全一致する位置キーが、移動体情報記憶部１３１より検索される。例えば、同図の（３）に示されるように二つの移動体Ｍ及びＮの移動体情報が移動体情報記憶部１３１に記憶されている場合、検索範囲Ａ７を含む移動体Ｍの位置キーは、リストＬに含まれる、１０００分の１度の丸め検索キーに完全一致する。検索範囲Ａ７のセルの数は「１」であるところ、移動体Ｍの位置キーに関して、リストＬに含まれる検索キーと完全一致する回数は１回である。一方、検索範囲Ａ７を含まない移動体Ｎの位置キーは、リストＬに含まれるいずれの検索キーにも完全一致しない。したがって、結果データＲｅｓ７には、移動体Ｍの位置キーが含まれる。
【０１７１】
上述したように、本実施の形態によれば、緯度及び経度が、位置キーの形式でキーとしてＫＶＳに登録される。したがって、当該位置キーに対応する対応情報（移動体情報、施設情報、又はエリア情報等）に関して、高速な検索を行うことができる。すなわち、例えば、検索範囲に含まれる移動体情報を検索する場合、指定された検索範囲に対応する位置キー群（検索キー群）のいずれかに前方一致する位置キー群を検索することで、目的とする移動体情報を検索することができる。
【０１７２】
なお、本実施の形態では、位置キーの形式は、経度、緯度の順に緯度及び経度の各桁が交互に配列される例を示したが、経度と緯度との順が逆であってもよい。
【０１７３】
また、必ずしも、緯度及び経度の全ての桁が交互に配列されなくてもよい。すなわち、検索時の精度（検索キーの精度）より上位の桁に関しては、交互に配列されなくてもよい。例えば、図２２の例では、検索キーの精度は、小数点以下第３位である。したがって、小数点以下第３位より上位の桁に関しては、経度文字列と緯度文字列とが順番に配列されてもよい。具体的には、図２２の例によればこの場合の検索キーは、「＋３５５６＋１３９１２２１」となる。また、移動体の位置キーは、「＋３５５６＋１３９１２２１３２」となる。これらは、いずれも、小数点以下第３位以下に関して、緯度文字列と経度文字列の文字を交互に配列したものである。この場合、当該位置キーは、当該検索キーに前方一致する。
【０１７４】
上記より、本実施の形態の位置キーは、緯度及び経度のそれぞれの全部又は最下位桁からの一部の桁の上位から順に同じ桁を１桁ずつ交互に配列した文字列ということになる。ここで、最下位桁からの一部の桁とは、直前の例において、小数点以下第３位以下の桁をいう。
【０１７５】
また、本実施の形態では、緯度の範囲は、＋９０度（北緯）〜−９０度（南緯）であるとし、経度の範囲は、＋１８０度（東経）〜−１８０度（西経）であるとした。しかし、緯度の範囲は、０度から１８０度とし、経度の範囲は、０度から３６０度としてもよい。この場合、符号を示す文字（＋又は−）は、位置キーの先頭の２文字に含まれなくてもよい。
【０１７６】
なお、検索範囲を構成する矩形領域群に関して生成されるセル群に関して、上位桁のセルへの統合を行うのは、移動体情報記憶部１３１に登録されている位置キーの精度に拘わらず、検索キーの前方一致による検索によって、検索範囲が含む移動体の検索を常に可能とするために行われる。例えば、図２６の（２）に示されるセルＣ１ａの範囲を有する移動体の移動体情報が移動体情報記憶部１３１に登録されているとする。この場合、セルＣ１ａに関する位置キーは、１０００分の１度の単位である。
【０１７７】
一方、検索範囲Ａ１を構成する矩形領域が１００００分の１度の単位で指定されていたとすると、当該矩形領域は、まず、同図の（１）に示されるように、１００００分の１度の単位のセル群に分割される。そのままの状態で、当該セル群のそれぞれに対応する位置キー（検索キー）に前方一致する位置キーを検索したとしても、セルＣ１ａに対応する位置キーは検索すされない。検索キーの方が、被検索対象の位置キーよりも長いからである。
【０１７８】
このような状況を排除するため、検索範囲を構成する矩形領域群を構成するセル群は、可能な限り上位の桁のセルへと統合されるのである。
【０１７９】
一方、移動体情報の登録時において、移動体のサイズ情報（移動体の範囲）を示す矩形領域群に関して生成されるセル群について上位桁への統合が行われるのは、検索範囲を含む移動体の検索時において、検索キーとの完全一致によって、検索範囲を含む移動体の少なくとも一部分の検索を常に有効なものとするためである。
【０１８０】
例えば、図２６のＡ１で示される矩形領域（すなわち、検索範囲Ａ１であるが、ここでは移動体の範囲Ａ１とする。）が、移動体のサイズ情報（範囲）を示す矩形領域として指定されて登録が要求されたとする。この場合、当該矩形領域が１００００分の１度の単位で指定されていたとすると、当該矩形領域は、まず、（１）に示されるように、１００００分の１度の単位のセル群に分割される。当該セル群が統合されずに当該移動体情報が登録されたとすると、当該移動体情報は、１００００分の１度の精度の１４４個の位置キーに対応付けられる。
【０１８１】
このような状態で、検索範囲を含む移動体の検索要求において、当該検索範囲の左下頂点として、図２６の（２）のセルＣ１ａの左下頂点と同じ緯度及び経度が指定されたとする。すなわち、セルＣ１ａと同じ範囲が検索範囲として指定されたとする。当該緯度及び経度は、１０００分の１度である。したがって、当該検索範囲に係る検索キーは、１０００分の１度、１００分の１度、１０分の１度、及び１度のそれぞれの単位で生成される。これらのいずれかの検索キーと完全一致する位置キーを検索しようとした場合、上記の１００００分の１度の精度の１４４個の位置キーの中で、これらの検索キーに完全一致する位置キーは無い。すなわち、範囲Ａ１に係る移動体は、セルＣ１ａを包含するにも拘わらず、セルＣ１ａを含むものの検索結果に含まれなくなってしまう。
【０１８２】
一方、範囲Ａ１に含まれる一部のセル群が、図２６の（２）のように、１０００分の１度の単位のセルＣ１ａに統合されていれば、当該セルＣ１ａに対応する位置キーが、上記の検索キーのうちの１０００分の１度の検索キーと完全一致する。したがって、範囲Ａ１に係る移動体は、セルＣ１ａを含むものとして検索される。
【０１８３】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【０１８４】
１            情報管理システム
１０          情報管理装置
１１          サービス部
１２          基盤部
２０          移動体端末
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
１２１        移動体情報受信部
１２２        登録要求受付部
１２３        位置キー生成部
１２４        登録部
１２５        検索要求受付部
１２６        検索条件生成部
１２７        検索部
１３１        移動体情報記憶部
１３２        施設情報記憶部
１３３        エリア情報記憶部
Ｂ            バス
【図１】
0005782948.tif 000002
【図２】
0005782948.tif 000003
【図３】
0005782948.tif 000004
【図４】
0005782948.tif 000005
【図５】
0005782948.tif 000006
【図６】
0005782948.tif 000007
【図７】
0005782948.tif 000008
【図８】
0005782948.tif 000009
【図９】
0005782948.tif 000010
【図１０】
0005782948.tif 000011
【図１１】
0005782948.tif 000012
【図１２】
0005782948.tif 000013
【図１３】
0005782948.tif 000014
【図１４】
0005782948.tif 000015
【図１５】
0005782948.tif 000016
【図１６】
0005782948.tif 000017
【図１７】
0005782948.tif 000018
【図１８】
0005782948.tif 000019
【図１９】
0005782948.tif 000020
【図２０】
0005782948.tif 000021
【図２１】
0005782948.tif 000022
【図２２】
0005782948.tif 000023
【図２３】
0005782948.tif 000024
【図２４】
0005782948.tif 000025
【図２５】
0005782948.tif 000026
【図２７】
0005782948.tif 000027
【図３２】
0005782948.tif 000028
【図２６】
0005782948.tif 000029
【図２８】
0005782948.tif 000030
【図２９】
0005782948.tif 000031
【図３０】
0005782948.tif 000032
【図３１】
0005782948.tif 000033