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