(57)【要約】      （修正有）【課題】特定の対象に関する時空間データから、条件を満たす時空間データの抽出を効率的に行う技術を提供する。【解決手段】移動する対象の位置情報と時刻情報とを管理する移動履歴管理装置１００において、対象の位置情報と時刻情報とを取得する手段と、位置情報を位置の粒度に基づき階層化して得られた位置情報と時刻情報とを有する階層化情報を、対象を特定する対象識別情報と関連付けて移動履歴記憶部１０３に格納する手段と、検索指定情報における上位の階層の情報に基づいて、移動履歴記憶部に格納された階層化情報における上位の階層の情報を検索した後に、検索指定情報における下位の階層の情報に基づいて、階層化情報における下位の階層の情報を検索することにより、検索指定情報に該当する対象の移動履歴としての位置情報と時刻情報を抽出する手段と、移動履歴としての位置情報と時刻情報を出力する手段とを備える。【選択図】図１
2017078996.tif 000002
【特許請求の範囲】
【請求項１】
移動する対象の位置情報と時刻情報とを管理する移動履歴管理装置であって、
前記対象の位置情報と時刻情報とを取得する手段と、
前記位置情報を位置の粒度に基づき階層化して得られた位置情報と前記時刻情報とを有する階層化情報を、前記対象を特定する対象識別情報と関連付けて移動履歴記憶部に格納する移動履歴登録手段と、
前記対象に関する検索指定情報を受け付け、当該検索指定情報における上位の階層の情報に基づいて、前記移動履歴記憶部に格納された階層化情報における上位の階層の情報を検索した後に、前記検索指定情報における下位の階層の情報に基づいて、前記階層化情報における下位の階層の情報を検索することにより、前記検索指定情報に該当する前記対象の移動履歴としての位置情報と時刻情報を抽出する移動履歴検索手段と、
前記移動履歴としての位置情報と時刻情報を出力する出力手段と
を備えることを特徴とする移動履歴管理装置。
【請求項２】
前記移動履歴登録手段は、新たな階層化情報である新階層化情報を取得した場合に、前記移動履歴記憶部に格納された最新の階層化情報と、前記新階層化情報とを比較し、当該新階層化情報において、位置情報に変化がある最上位の階層以下の階層の情報を前記移動履歴記憶部に格納する
ことを特徴とする請求項１に記載の移動履歴管理装置。
【請求項３】
前記移動履歴記憶部に格納された各時刻の階層化情報のうち、現在時刻から所定時間遡った時刻以前の階層化情報を削除する移動履歴削除手段
を更に備えることを特徴とする請求項１又は２に記載の移動履歴管理装置。
【請求項４】
前記移動履歴検索手段は、前記検索指定情報として時刻範囲を受け付けた場合に、当該時刻範囲の開始時刻に該当する階層化情報を特定し、当該階層化情報から時刻の順方向に向けて、前記時刻範囲の中で、下位の階層の情報を順次取得する
ことを特徴とする請求項１ないし３のうちいずれか１項に記載の移動履歴管理装置。
【請求項５】
前記移動履歴検索手段は、前記検索指定情報として位置範囲を受け付けた場合に、当該位置範囲に該当する階層化情報を特定し、当該階層化情報から時刻の順方向に向けて、下位の階層の情報を順次取得する
ことを特徴とする請求項１ないし４のうちいずれか１項に記載の移動履歴管理装置。
【請求項６】
移動する対象の位置情報と時刻情報とを管理する移動履歴管理装置が実行する移動履歴検索方法であって、
前記対象の位置情報と時刻情報とを取得するステップと、
前記位置情報を位置の粒度に基づき階層化して得られた位置情報と前記時刻情報とを有する階層化情報を、前記対象を特定する対象識別情報と関連付けて移動履歴記憶部に格納する移動履歴登録ステップと、
前記対象に関する検索指定情報を受け付け、当該検索指定情報における上位の階層の情報に基づいて、前記移動履歴記憶部に格納された階層化情報における上位の階層の情報を検索した後に、前記検索指定情報における下位の階層の情報に基づいて、前記階層化情報における下位の階層の情報を検索することにより、前記検索指定情報に該当する前記対象の移動履歴としての位置情報と時刻情報を抽出する移動履歴検索ステップと、
前記移動履歴としての位置情報と時刻情報を出力する出力ステップと
を備えることを特徴とする移動履歴検索方法。
【請求項７】
前記移動履歴登録ステップにおいて、前記移動履歴管理装置は、新たな階層化情報である新階層化情報を取得した場合に、前記移動履歴記憶部に格納された最新の階層化情報と、前記新階層化情報とを比較し、当該新階層化情報において、位置情報に変化がある最上位の階層以下の階層の情報を前記移動履歴記憶部に格納する
ことを特徴とする請求項６に記載の移動履歴検索方法。
【請求項８】
コンピュータを、請求項１ないし５のうちいずれか１項に記載された移動履歴管理装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特定の人や物が過去において存在した時・場所に関する検索を行う技術に関連するものである。
【背景技術】
【０００２】
現在位置に対して検索を行う従来技術として、例えば、携帯電話の着信制御や、特定の場所にいる人に、当該場所に関わる情報を提供するロケーションサービス等がある。
【０００３】
ところで、近年、GPSや携帯電話等の技術の発展により、特定の人・物の移動履歴が容易に記録できるようになってきており、移動履歴を大規模に利用することも考えられるようになってきている。
【０００４】
例えば、特許文献１には、過去の時空間上の条件を指定して、条件に該当する人物や移動機等と通信を行う技術が開示されている。当該技術は、過去の時空間上の条件に合致する対象を多数の候補の中から、効率的に検索・抽出を行うことを目的としている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開2013-98893号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
移動履歴を利用し、特定の人や物等の対象に関して、時空間上の条件を満たすか否か等の検索を効率的に行うことが必要となる場合がある。例えば、(1)どこかで落し物をした場合に、自分の過去の移動履歴を引き出したい、(2)患者が新型インフルエンザに感染し、気が付かずに、広範に移動したので、移動履歴を引出し、同時期に、当該位置に居た人に注意喚起したい、等の場合である。このような場合、「人」を特定した上で、条件を満たす時空間データの抽出が必要であるが、複数の人が同期せずに移動している移動履歴データを扱うこととなるため、大量のデータから、目的の情報を抽出することが困難であった。
【０００７】
本発明は、上記の点に鑑みてなされたものであり、特定の対象に関する時空間データから、条件を満たす時空間データの抽出を効率的に行う技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の実施の形態によれば、移動する対象の位置情報と時刻情報とを管理する移動履歴管理装置であって、
前記対象の位置情報と時刻情報とを取得する手段と、
前記位置情報を位置の粒度に基づき階層化して得られた位置情報と前記時刻情報とを有する階層化情報を、前記対象を特定する対象識別情報と関連付けて移動履歴記憶部に格納する移動履歴登録手段と、
前記対象に関する検索指定情報を受け付け、当該検索指定情報における上位の階層の情報に基づいて、前記移動履歴記憶部に格納された階層化情報における上位の階層の情報を検索した後に、前記検索指定情報における下位の階層の情報に基づいて、前記階層化情報における下位の階層の情報を検索することにより、前記検索指定情報に該当する前記対象の移動履歴としての位置情報と時刻情報を抽出する移動履歴検索手段と、
前記移動履歴としての位置情報と時刻情報を出力する出力手段と
を備えることを特徴とする移動履歴管理装置が提供される。
【０００９】
また、本発明の実施の形態によれば、移動する対象の位置情報と時刻情報とを管理する移動履歴管理装置が実行する移動履歴検索方法であって、
前記対象の位置情報と時刻情報とを取得するステップと、
前記位置情報を位置の粒度に基づき階層化して得られた位置情報と前記時刻情報とを有する階層化情報を、前記対象を特定する対象識別情報と関連付けて移動履歴記憶部に格納する移動履歴登録ステップと、
前記対象に関する検索指定情報を受け付け、当該検索指定情報における上位の階層の情報に基づいて、前記移動履歴記憶部に格納された階層化情報における上位の階層の情報を検索した後に、前記検索指定情報における下位の階層の情報に基づいて、前記階層化情報における下位の階層の情報を検索することにより、前記検索指定情報に該当する前記対象の移動履歴としての位置情報と時刻情報を抽出する移動履歴検索ステップと、
前記移動履歴としての位置情報と時刻情報を出力する出力ステップと
を備えることを特徴とする移動履歴検索方法が提供される。
【発明の効果】
【００１０】
本発明の実施の形態によれば、特定の対象に関する時空間データから、条件を満たす時空間データの抽出を効率的に行う技術が提供される。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施の形態におけるシステム構成例を示す図である。
【図２】各移動機の時空間履歴管理の例を説明するための図である。
【図３】位置情報取得時のデータ操作例を説明するための図である。
【図４】情報削除時のデータ操作例を説明するための図である。
【図５】時刻指定検索の例を説明するための図である。
【図６】位置指定検索の例を説明するための図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１３】
本発明において、検索の対象に限定はないが、以下で説明する本実施の形態では、人あるいは物に移動機が付帯し、当該移動機の位置と、その人あるいは物の位置が、移動機と同一視できるものとして、移動機を検索の対象としている。
【００１４】
また、本実施の形態では、特定のサービス事業者における装置（後述する移動履歴管理装置）が移動機の移動履歴を保持し、時空間上の条件に合致するデータを回答する例を説明するが、移動機内に移動履歴を保持し、移動機内で時空間上の条件に合致するデータを検索することとしてもよい。
【００１５】
（システム構成）
図１に、本実施の形態におけるシステムの構成例を示す。図１に示すように、本実施の形態におけるシステムは、移動履歴管理装置１００と移動機２００を有し、それぞれがネットワーク３００に接続された構成を有する。
【００１６】
移動履歴管理装置１００は、移動機２００の移動履歴を保持し、当該移動履歴から条件を満たす時空間データを抽出する装置である。移動機２００は、例えば、スマートフォン、タブレット、携帯電話機、ＰＣ等であり、自分の位置を時刻とともに移動履歴管理装置１００に送信する機能を有する。ネットワーク３００は、特定の種類のネットワークに限定されないが、例えば、インターネット等のパブリックネットワーク、プライベートネットワーク、パブリックネットワークとプライベートネットワークが混在したネットワーク等である。
【００１７】
なお、図１には、１つの移動機２００が示されているが、これは説明のための便宜上のものであり、一般には、多数の移動機が存在し、移動履歴管理装置１００は多数の移動機の移動履歴を管理する。以下、装置構成をより詳細に説明する。
【００１８】
図１に示すとおり、移動履歴管理装置１００は、通信部１０１、移動履歴登録部１０２、移動履歴記憶部１０３、位置情報変換部１０４、位置情報変換データ記憶部１０５、移動履歴削除部１０６、移動履歴検索部１０７、及び入出力部１０８を有する。各部の機能の概要は以下のとおりである。
【００１９】
通信部１０１は、移動機２００からネットワーク３００経由で、移動機２００を特定する情報、位置情報、及び時刻情報を受信する。移動履歴登録部１０２は、通信部１０１より取得した位置情報を、位置情報変換部１０４により位置の粒度に基づく階層化された位置情報に変換し、移動機２００を特定する情報と階層化された位置情報と時刻情報とを関連付けて移動履歴記憶部１０３に登録する。
【００２０】
位置情報変換部１０４は、予め位置情報変換データ記憶部１０５に保持する位置情報変換データを用いて、位置情報を階層化された位置情報に変換する。移動履歴削除部１０６は、移動履歴記憶部１０３に保持された特定の時刻よりも古い移動履歴情報の削除を行う。
【００２１】
入出力部１０８は、サービスユーザより検索条件（移動機を特定する情報と、指定する位置情報と、時刻情報とを含む）を指定した検索依頼を受け付け、移動履歴検索部１０７により抽出した移動履歴（時間データと空間（位置）データを含む時空間データ）を返却する。
【００２２】
移動履歴検索部１０７は、入出力部１０８から取得した検索条件の位置情報を必要に応じて階層化された位置情報に変換し、移動機２００を特定する情報、位置情報、時刻情報をもとに、移動履歴記憶部１０３から検索条件に合致する移動履歴を抽出する。
【００２３】
図１に示すように、移動機２００は、測位部２０１と通信部２０２を有する。測位部２０１は、GPS等で測位した自身の位置情報と時刻情報を取得する。通信部２０２は、移動機２００を特定する情報、取得した位置情報、及び時刻情報をネットワーク３００経由で移動履歴管理装置１００に送信する。
【００２４】
なお、前述したように、移動機２００内に移動履歴を保持し、移動機２００内で時空間上の条件に合致するデータを検索することとしてもよく、その場合、当該移動機２００は、移動履歴管理装置１００と同様の構成を備える。
【００２５】
移動履歴管理装置１００（移動機２００が移動履歴管理装置１００の機能を備える場合を含む）は、例えば、１つ又は複数のコンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、移動履歴管理装置１００が有する機能は、当該コンピュータに内蔵されるＣＰＵやメモリなどのハードウェア資源を用いて、移動履歴管理装置１００で実施される処理に対応するプログラムを実行することによって実現することが可能である。上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【００２６】
（移動履歴管理装置１００が管理するデータ、及び動作概要）
本実施の形態に係る移動履歴管理装置１００を運用するサービス事業者は、予め、位置の粒度の階層を定めておく。例えば、自治体単位であれば、(1)県レベル、(2)市町村レベル、(3)町丁目レベル、等とする。緯度経度であれば、(1)度レベル、(2)分レベル、(3)秒レベル、等とする。なお、自治体レベル等については、直接自治体情報が位置情報から得られるわけではないので、位置情報として得られた緯度経度情報から変換する。この変換自体は、従来技術で実施可能である。また、本実施の形態では、例として、現在時刻から時間T遡った時刻以降の履歴を管理することとしている。
【００２７】
移動履歴管理装置１００は、各移動機の移動履歴（時間と空間の履歴である時空間履歴）を、上記の階層毎に管理する。このように、階層毎に移動履歴を管理することで、効率的に時空間検索を実施することを可能としている。
【００２８】
図２に、移動履歴管理装置１００の移動履歴記憶部１０３において管理（格納）される移動履歴のデータ構造の一例を示す。図２は、例として、１つの移動機２００についてのデータを示している。
【００２９】
図２に示すように、階層のレベル（図２の例ではレベル１、レベル２）毎に、移動機２００が存在した位置（地名）と時刻が格納される。また、上位階層（図２の例ではレベル１）の位置が変わる度に上位階層のデータ及び下位階層のデータ（図２の例ではレベル２）が追加され、当該上位階層のデータから下位階層のデータにポインタが張られる。また、上位階層での位置が変化しない間、下位階層において位置が変換する度に下位階層のデータが追加され、前の時刻のデータ（例：レベル２の時刻１１のデータ）から、追加データ（例：レベル２の時刻１２のデータ）にポインタが張られる。
【００３０】
また、上位階層のデータの間において、前の時刻のデータ（例：レベル１の時刻１１のデータ）から、追加データ（例：レベル１の時刻２１のデータ）にポインタが張られる。また、上位階層での位置が変化した場合（例：レベル１の地名１１が地名１２に変化した場合）、直前の下位階層のデータ（例：レベル２の時刻１３のデータ）から、追加された上位階層のデータ（例：レベル１の時刻２１のデータ）にポインタが張られる。
【００３１】
更に、移動機IDから、存在する最も古い上位階層のデータ（例：レベル１の時刻１１のデータ）にポインタが張られるとともに、最も新しい上位階層のデータ（例：レベル１の時刻３１のデータ）にポインタが張られる。
【００３２】
上記のような移動履歴のデータ構造を採用したことで、移動機２００の位置が、どの階層で変化しているか等を、ポインタを辿ることで迅速に把握することが可能である。これにより、例えば、移動機２００の大まかな移動については、細かな移動の検索をスキップすることで、迅速に検索することができる。また、移動機２００の詳細な位置の検索が必要な場合には、まず、大まかな位置で検索し、該当する位置の周辺に来たら詳細なレベルで検索すればよく、効率的で迅速な検索を実現できる。
【００３３】
本実施の形態では、位置の粒度は、時刻の粒度でもある。そのため、特定の時刻における位置の検索が必要な場合に、まず、上位階層を検索することで、特定の時刻におおよそ近いデータを探し、当該データを特定できたら、下位階層で検索する、という効率的な検索が可能である。
【００３４】
より具体的には、例えば、10月21日、8時12分における移動機２００の位置を探したい場合、まず、10月21日という大きな時刻粒度について、大きな位置粒度（例：県や市）のレベル（上位階層のレベル）で検索し、10月21日のデータを見つけたら、階層を下げて、8時、8時12分という細かな時刻粒度について、より細かな位置粒度（例：町や丁目）のレベルで検索する、という効率的な検索が可能である。
【００３５】
（移動履歴管理装置１００の動作例）
以下、移動履歴管理装置１００の動作をより詳細に説明する。移動履歴管理装置１００が実行する基本的な処理として、 (1)位置情報取得、(2) 情報削除、(3) 検索がある。以下、それぞれについて説明する。
【００３６】
＜(1)位置情報取得＞
移動履歴管理装置１００は、通信部１０１により移動機２００の位置情報（例：緯度経度）を移動機ID、及び、現在時刻（ここでは時刻uとする）とともに得る。移動履歴登録部１０２は、通信部１０１より移動機ID、位置情報、及び時刻uを取得すると、位置情報を位置情報変換部１０４に通知する。
【００３７】
位置情報変換部１０４は、予め位置情報変換データ記憶部１０５に保持する位置情報変換データを用いて、当該位置情報を、位置情報の階層を定義する形式（例えば、自治体単位）の位置情報に変換する。変換後の位置情報は、例えば、D県E市F丁目であるとする。当該変換後の位置情報は、位置情報変換部１０４から移動履歴登録部１０２に返される。
【００３８】
ここで、各階層において、変換後の位置情報と時刻とを有する情報を階層化情報と呼ぶことにする。例えば、D県と時刻uからなる情報は第１階層の階層化情報であり、E市と時刻uからなる情報は第２階層の階層化情報であり、F丁目と時刻uからなる情報は第３階層の階層化情報である。なお、同時刻の複数階層の階層化情報をまとめた情報を階層化情報と呼んでもよい。
【００３９】
図３は、移動履歴記憶部１０３に格納されるデータの例を示す。図３を適宜参照しながら、上記のようにして取得された階層化情報の格納処理を説明する。
【００４０】
なお、図３は、位置情報（D県E市F丁目）が格納された後の状態を示している。位置情報（D県E市F丁目）が取得された時点（格納される前の時点）では、図３において、点線で囲んだデータは未だ存在しないものとする。また、位置情報（D県E市F丁目）が取得された時点（格納される前の時点）では、図３に示す「最も古い階層化情報へのポインタ」は、「最も新しい階層化情報へのポインタ」であるとする。
【００４１】
移動履歴登録部１０２は、移動履歴記憶部１０３上で移動機IDを検索し、特定する。既に説明したように、移動機IDからのポインタは、最も古い階層化情報（第１階層）と、最も新しい階層化情報（第１階層）を指している。
【００４２】
移動履歴登録部１０２は、まず、最新の階層化情報を辿り、（必要に応じて、下位階層のポインタを更に辿り）、各階層の最新の階層化情報（位置と時刻）を得る。
【００４３】
そして、最新の第i階層の階層化情報における位置がx_i、時刻がs_iであるとすると、移動履歴登録部１０２は、登録しようとする各階層化情報の位置と、対応する各階層のx_iとを比較し、どの階層で異なるかを判定し、異なっている最上位の階層jを特定する。移動履歴登録部１０２は、特定されたj以下の階層について、新階層化情報を、時刻とともに追加し、ポインタを設定する。以下、図３を参照してより具体的に説明する。
【００４４】
D県E市F丁目が新たに取得され、格納される前において、図３の「x_1=A県、s_1=0」へのポインタが最も新しい階層化情報へのポインタであるとすると、移動履歴登録部１０２は、x_1=A県とD県とを比較した時点で、異なっている最上位の階層として、第１階層において位置が異なることを検知する。そして、第１階層以下の階層（すなわち、第１階層、第２階層、及び第３階層）のそれぞれについて、階層化情報を時刻とともに追加し、上位階層から下位階層へのポインタを設定する。すなわち、図３の点線枠で囲んだように、「x_1=D県、s_1=u」、「x_2=E市、s_2=u」、「x_3=F丁目、s_3=u」が追加される。更に、「最も新しい階層化情報へのポインタ」が、当該新たに追加された階層化情報（第１階層）へのポインタに更新される。
【００４５】
別の例として、図３において、点線枠で囲んだデータが存在せず、更に、「x_2=P市、s_2=t」、「x_3=Q丁目、s_3=t」が存在していない状態から、位置情報（A県P市Q丁目）と時刻tが新たに取得された場合を考える。上記と同様に、この場合は、図３の「x_1=A県、s_1=0」へのポインタが最も新しい階層化情報へのポインタになっている。
【００４６】
この場合、移動履歴登録部１０２は、x_1=A県だが、x_2=B市でないことを検知し、第２階層に、新たな階層化情報「P市、時刻t」のデータを登録し、第２階層の前の時刻の階層化情報「x_2=B市、s_2=0」からポインタを張る。更に、移動履歴登録部１０２は、第３階層に、新たな階層化情報「Q丁目、時刻t」のデータを登録する。
【００４７】
この場合、第２階層と同時に第３階層が更新されたので、元の第３階層の「x_3=C丁目,s_3=0」から、新たな第２階層の階層化情報「P市、時刻t」へポインタを張り、「P市、時刻t」から「Q丁目、時刻t」にポインタを張る。第１階層は変わらないので、移動機IDからの最も新しい階層化情報へのポインタは変えない。なお、前述した例（点線枠が追加された例）では、第１階層が変更されたので、このポインタも更新している。
【００４８】
＜(2)情報削除＞
上述した (1) 位置情報取得の処理により、階層化情報のデータは際限なく増加するため、本実施の形態では、移動履歴削除部１０６が、現在時刻よりも時間Tだけ過去に遡った時刻以前の古い情報を削除するものとする。この情報削除処理は、定期的に行ってもよいし、(1)の位置情報取得や(3)の検索の実行に際して実行してもよい。例えば、(1)又は(3)と合わせて行う際には、(1)又は(3)において対象とする移動機IDを特定して削除処理を行う。また、例えば、定期的に行う際には、削除処理の対象となる移動機IDを乱数により特定してもよい。
【００４９】
削除処理において、まず、移動履歴削除部１０６は、特定された移動機IDからのポインタのうち、最も古い階層化情報（第１階層）を指すポインタを辿り、最も古い階層化情報（第１階層）の移動時刻を取得する。その値が現在時刻よりT以上古ければ、移動履歴削除部１０６は、以下の処理を行う。
【００５０】
最も古い第i階層の階層化情報をa_iとする。最も古い第i階層の階層化情報からポインタを辿り、最下位層まで至る。そして、その最下層の階層化情報からポインタを１つ辿る。ポインタを辿った先の階層に応じて、(i)と(ii)の場合に分けられる。
【００５１】
(i)ポインタを辿った先が第１階層の階層化情報であれば、移動機IDから最も古い階層化情報を指すポインタを、その（辿った先の）第１階層の階層化情報を指すようセットする。その結果、これまでの最も古い階層化情報は、使われなくなったので、消去してもよい。
【００５２】
(ii) ポインタを辿った先が第１階層の階層化情報でなく、第i階層（iは２以上の整数）であれば、a_{i-1}からa_iへのポインタを、a_{i-1}からこの第i階層データへと付け替える。更に、a_1からa_{i-1}の時刻データを、この第i階層の時刻データへ修正する。その結果、これまでの最も古い階層化情報a_iから下は、使われなくなったので、消去してもよい。
【００５３】
(i)のケースは、最も古い階層化情報の時刻から次の時刻の間に、最上位階層のレベルで位置の変化があった場合に相当し、(ii)のケースは、最も古い階層化情報の時刻から次の時刻の間に、上位階層（a_1〜a_{i-1}、例：県レベル）では位置の変化はないが、下位階層（最下位〜a_i、例：丁目レベル）において位置の変化があった場合に相当する。
【００５４】
なお、上記手順により、データは更新されたが、必ずしも、現在時刻よりT以上古い部分がすべて外されたとは限らない。このため、移動機IDが指す最も古いデータの移動時刻が現在時刻よりT以上古くなくなるまで、上記を繰り返し実施する。
【００５５】
具体例として、図３に示した階層化情報が格納されている状態から、最も古い階層化情報（時刻0）を削除する場合の例を図４を参照して説明する。
【００５６】
まず、移動履歴削除部１０６は、最も古い階層化情報（第1階層）を指すポインタを辿ることで、最も古い階層化情報「x_1=A県、s_1=0」に至り、その時刻0を取得する。その値は現在時刻よりT以上古いものとする。
【００５７】
移動履歴削除部１０６は、第１階層「x_1=A県、s_1=0」からポインタを辿り、最下位層「x_3=C丁目、s_3=0」まで至る。そして、当該最下位層「x_3=C丁目、s_3=0」からポインタを１つ辿ることで、時刻tの第２階層の階層化情報「x_2=P市、s_2=t」に至る。このケースは、前述した(ii)のケースに該当する。
【００５８】
よって、移動履歴削除部１０６は、時刻0の第1階層の階層化情報（ここではa_{i-1}に相当）から時刻0の第２階層の階層化情報（a_i）へのポインタを、当該a_{i-1}から、この第i階層の階層化情報「x_2=P市、s_2=t」へと付け替える。更に、第1階層の階層化情報の時刻データを、この第i階層の時刻データである時刻tへ修正する。
【００５９】
＜(3)検索＞
検索処理では、まず、移動履歴管理装置１００は、本サービスのユーザ（あるいは、当該ユーザの端末）から、入出力部１０８より移動機ID、指定時刻、指定位置の形で検索依頼を受ける。
【００６０】
指定時刻は、特定の時刻でもよいし、時刻の範囲（例えば、2015年8月1日10:00から11:00）でもよい。なお、例えば、「2015年8月1日」を指定した場合、2015年8月1日00:00から24:00の範囲を指定したことと見なしてもよい。また、指定位置も、特定の位置でもよいし、位置の範囲（例えば、A県B市１~３丁目）でもよい。なお、例えば、「A県B市」を指定した場合、A県B市における全部の丁目の範囲を指定したことと見なしてもよい。
【００６１】
指定位置、指定時刻は、いずれかが空集合でもよい。通常は、いずれかが空集合である。指定時刻が空集合の（指定されない）場合、移動履歴管理装置１００は、検索結果として、検索対象が指定位置に居た時刻及び詳細位置を含む履歴を回答する。また、指定位置が空集合の（指定されない）場合、移動履歴管理装置１００は、検索結果として、検索対象が指定時刻に居た位置及び指定時刻範囲での移動履歴を回答する。
【００６２】
検索依頼を受けた移動履歴管理装置１００において、移動履歴検索部１０７が、当該検索依頼を基に移動履歴記憶部１０３を検索し、移動機IDを見つける。以下、当該移動機IDに対する検索に関して、(A)時刻指定検索と(B)位置指定検索とに分けて説明する。
【００６３】
＜＜(A)時刻指定検索＞＞
図５は、時刻指定検索の例を示す図である。まずは、移動履歴検索部１０７による処理内容を説明し、次に、図５の例に沿った具体的な処理の例を説明する。
【００６４】
検索依頼の中に、ある時刻の範囲（t_1,t_2）（t_1からt_2までを意味する）を指定する時刻指定がある場合、移動履歴検索部１０７は、当該移動機IDからポインタを辿り、第１階層上で、t_1に近い時刻を持つ階層化情報を探す。より詳細には、第１階層の第i階層化情報（iは、古いものから数えてi番目を意味する）が、位置y_i、時刻s_iであるとき、移動履歴検索部１０７は、s_i<=t_1<s_{i+1}となるs_iの階層化情報を探す。
【００６５】
s_iの階層化情報が得られたら、位置y_iの第２階層をポインタで辿り、第２階層上で、t_1に近い時刻を持つ階層化情報を探す。より詳細には、位置y_iの第２階層の第j階層化情報（jは、古いものから数えてj番目を意味する）が、位置z_j、時刻u_jであるとき、u_j<=t_1<u_{j+1}となるu_jを探す。同様にして、最下位層まで特定する。
【００６６】
次に、移動履歴検索部１０７は、特定された階層化情報から、時刻の順方向に、時刻がt_2になるまでポインタを辿る。つまり、ポインタを辿り、到達した階層化情報から得た時刻がt_2に達していなければ、更に、ポインタを辿るという処理を実行する。ポインタが階層を上がる場合があるが、その場合は、その直後にポインタで階層を下ることができるので、階層を下ることができる場合は必ずポインタを下る。こうして得た、位置、時刻データが、当該移動機の指定時間範囲での移動履歴であるので、移動履歴検索部１０７はこれを入出力部１０８に回答する。回答する際には、例えば、最下層で得られた階層化情報の時刻に基づき、指定時刻を満たす検索結果を回答する。
【００６７】
上記のように、t_1に近い時刻を持つ第１階層の階層化情報をまず検索し、当該階層化情報が見つかれば、徐々に階層を下げて、時刻粒度を細かくすることで効率的に検索を行うことができる。
【００６８】
＜＜＜(A)時刻指定検索の具体例＞＞＞
図５を参照して、上述した時刻指定検索の処理をより具体的に説明する。図５に示すように、この例では、指定時刻として、2015年8月1日10:00から11:00が指定されたとする。すなわち、t_1=2015年8月1日10:00、t_2=2015年8月1日11:00が指定されたとする。この場合、まず、移動履歴検索部１０７は、s_i<=t_1<s_{i+1}となるs_iを探した結果、s_iの第１階層の階層化情報として、階層化情報「y1=A県、s1=8/1 9:40」を見つける。
【００６９】
移動履歴検索部１０７は、第２階層、第３階層のそれぞれでt_1に近い時刻を持つ階層化情報を探すことにより、最下位層として、階層化情報「C1丁目、8/1 9:40」を特定する。
【００７０】
次に、移動履歴検索部１０７は、「C1丁目、8/1 9:40」から、時刻の順方向にポインタを順に辿ることで、t_2=2015年8月1日11:00になるまでに、「C2丁目、8/1 10:10」、「C3丁目、8/1 10:30」、「B4市、8/1 10:50」、「C4丁目、8/1 10:50」を得る。ここで、「B4市、8/1 10:50」から「C4丁目、8/1 10:50」へのポインタ遷移は、「階層を下ることができる場合は必ずポインタを下る」というルールに従った処理である。
【００７１】
更に、t_1の直前の階層化情報が「C1丁目、8/1 9:40」であることから、t_1からt_1直後の階層化情報「C2丁目、8/1 10:10」までの時間、すなわち8/1 10:00〜10:10は、C1丁目とみなし、t_1時点の階層化情報として「C1丁目、8/1 10:00」を得る。また、t_2の直前の階層化情報が、「C4丁目、8/1 10:50」であることから、t_2直前の階層化情報「C4丁目、8/1 10:50」からt_2までの時間、すなわち8/1 10:50〜11:00は、C4丁目とみなし、t_2時点の階層化情報として、「C4丁目、8/1 11:00」を得る。
【００７２】
上記の処理の結果、例えば、移動履歴検索部１０７は、「C1丁目、8/1 10:00」、「C2丁目、8/1 10:10」、「C3丁目、8/1 10:30」、「B4市C4丁目、8/1 10:50」、「B4市C4丁目、8/1 11:00」 を含む情報を入出力部１０８に通知し、入出力部１０８が当該情報を出力する。出力にあたっては、このようなデータの羅列形式で出力してもよいし、移動履歴を地図上にマッピングした地図画面で出力してもよい。
【００７３】
＜＜(B)位置指定検索＞＞
図６は、位置指定検索の例を示すための図である。まずは、移動履歴検索部１０７による処理内容を説明し、次に、図６の例に沿った具体的な処理の例を説明する。
【００７４】
ユーザから指定された位置が、所定の階層表現に適合した形式でない場合、移動履歴管理装置１００は、当該指定された位置を階層表現に適合した形式に変換する。もしくは、位置の指定方法を階層表現に適合した形式（例えば、住所のような自治体単位形式）で入出力部１０８より入力するようユーザに要求する。階層表現に適合した形式で指定された位置（例えば、A県B市C1~3丁目）を得て、移動履歴管理装置１００は、以下のような手順を実施する。
【００７５】
検索依頼の中に、時刻範囲指定(t_1,t_2)が含まれている場合は、前述のように、移動履歴検索部１０７は当該移動機IDからポインタを辿り、まず、t_1にあたる各階層の階層化情報を特定し、以下の手順をそこから開始する。時刻範囲指定がなければ、当該移動機IDが指す、最も古い階層化情報から以下を開始する。
【００７６】
まず、移動履歴検索部１０７は、第１階層上で、開始点（対象の中で最も古い時刻）の階層化情報からポインタを辿り、第１階層の指定位置（例：指定位置がA県B市C1~3丁目の場合、「A県」）を持つ階層化情報を探す。ここで、第１階層の指定位置（例：「A県」）を持つ階層化情報が複数、得られた場合、以下の処理は、時刻の古い階層化情報、次に古い階層化情報、といったように、時刻順に繰り返し行われる（時刻指定がある場合は指定時刻の範囲で行う）。
【００７７】
第１階層の指定位置を持つ階層化情報からポインタを下位方向に辿って、第２階層に至り、第２階層上でポインタを辿りながら、第２階層の指定位置（例：指定位置がA県B市１~３丁目の場合、「B市」）を持つ階層化情報を探す。このとき、もしも第２階層の指定位置を持つ階層化情報が見つからない場合、第２階層が終了し、ポインタが第１階層に戻る。
【００７８】
第２階層の指定位置（例：「B市」）を持つ階層化情報が見つかれば、第３階層に下り、第３階層上でポインタを順次辿りながら、第３階層の指定位置（例：指定位置がA県B市C1~3丁目の場合、「C1丁目」、「C2丁目」、「C3丁目」のいずれか）を持つ階層化情報を探す。第３階層の指定位置を持つ階層化情報が得られたら、そのときの位置（例：「C1丁目」、「C2丁目」、「C3丁目」のいずれか）と時刻を移動履歴記憶部１０３に保持する。
【００７９】
更に、ポインタを辿り、ポインタを辿った先の階層化情報における位置が、指定位置（例： A県B市C1~3丁目）から外れた場合、その外れた位置を持つ階層化情報にある時刻を、指定位置の終了時刻として移動履歴記憶部１０３に保持する。
【００８０】
その後、t_2に至るか（時刻範囲の指定がある場合）、最新の階層化情報まで到達する（時刻範囲の指定がない場合）まで、ポインタを辿り、上記と同じことを繰り返す。こうして得た、位置、時刻データが、当該移動機の指定時間範囲での移動履歴であるので、入出力部１０８によりこれを回答する。本例では、上位階層で、指定位置（例：「A県」）に該当する階層化情報が見つかるまで、下位階層の細かい粒度で検索することなく検索を行うため、効率的に検索を行うことができる。
【００８１】
＜＜＜(B)位置指定検索の具体例＞＞＞
図６を参照して、上述した位置指定検索の処理をより具体的に説明する。図６に示すように、この例では、指定時刻として、2015年8月1日10:00から11:00が指定され、指定位置として、A県B市C1~3丁目が指定される。
【００８２】
まず、移動履歴検索部１０７は、2015年8月1日10:00に近い、第１階層の階層化情報「A県、8/1 9:40」を特定し、当該階層化情報が、第１階層の指定位置「A県」を持つことを特定する。階層化情報「A県、8/1 9:40」からポインタを下方向に辿って、第２階層の階層化情報「B市、8/1 9:40」が、第２階層の指定位置「B市」を持つ階層化情報に該当することを特定し、更にポインタを下方向に辿って、第３階層の階層化情報「C1丁目、8/1 9:40」が、第３階層の指定位置「C1丁目」を持つ階層化情報に該当することを特定する。
【００８３】
続いて、移動履歴検索部１０７は、第３階層上で、階層化情報「C1丁目、8/1 9:40」からポインタを辿り、第３階層の指定位置を持つ階層化情報として、順次、階層化情報「C2丁目、8/1 10:10」、階層化情報「C3丁目、8/1 10:30」を取得する。移動履歴検索部１０７は、取得した情報を移動履歴記憶部１０３に保持する。
【００８４】
階層化情報「C3丁目、8/1 10:30」からポインタを辿ると、階層化情報「B4市、8/1 10:50」に至るが、「B4市」は、指定位置（A県B市C１~３丁目）から外れるため、移動履歴検索部１０７は、階層化情報「B4市、8/1 10:50」の時刻「8/1 10:50」を指定位置の終了時刻として移動履歴記憶部１０３に保持する。
【００８５】
上記の処理の結果、例えば、移動履歴検索部１０７は、「C1丁目、8/1 9:40」、「C2丁目、8/1 10:10」、「C3丁目、8/1 10:30」、「終了時刻8/1 10:50」を含む情報を入出力部１０８に通知し、入出力部１０８が当該情報を出力する。出力にあたっては、このようなデータの羅列形式で出力してもよいし、移動履歴を地図上にマッピングした地図画面で出力してもよい。
【００８６】
（実施の形態のまとめ）
以上、説明したように、本実施の形態においては、移動する対象の位置情報と時刻情報とを管理する移動履歴管理装置であって、前記対象の位置情報と時刻情報とを取得する手段と、前記位置情報を位置の粒度に基づき階層化して得られた位置情報と前記時刻情報とを有する階層化情報を、前記対象を特定する対象識別情報と関連付けて移動履歴記憶部に格納する移動履歴登録手段と、前記対象に関する検索指定情報を受け付け、当該検索指定情報における上位の階層の情報に基づいて、前記移動履歴記憶部に格納された階層化情報における上位の階層の情報を検索した後に、前記検索指定情報における下位の階層の情報に基づいて、前記階層化情報における下位の階層の情報を検索することにより、前記検索指定情報に該当する前記対象の移動履歴としての位置情報と時刻情報を抽出する移動履歴検索手段と、前記移動履歴としての位置情報と時刻情報を出力する出力手段とを備えることを特徴とする移動履歴管理装置が提供される。
【００８７】
前記移動履歴登録手段は、例えば、新たな階層化情報である新階層化情報を取得した場合に、前記移動履歴記憶部に格納された最新の階層化情報と、前記新階層化情報とを比較し、当該新階層化情報において、位置情報に変化がある最上位の階層以下の階層の情報を前記移動履歴記憶部に格納する。
【００８８】
前記移動履歴管理装置は、前記移動履歴記憶部に格納された各時刻の階層化情報のうち、現在時刻から所定時間遡った時刻以前の階層化情報を削除する移動履歴削除手段を更に備えてもよい。
【００８９】
前記移動履歴検索手段は、前記検索指定情報として時刻範囲を受け付けた場合に、当該時刻範囲の開始時刻に該当する階層化情報を特定し、当該階層化情報から時刻の順方向に向けて、前記時刻範囲の中で、下位の階層の情報を順次取得することとしてもよい。
【００９０】
前記移動履歴検索手段は、前記検索指定情報として位置範囲を受け付けた場合に、当該位置範囲に該当する階層化情報を特定し、当該階層化情報から時刻の順方向に向けて、下位の階層の情報を順次取得することとしてもよい。
【００９１】
本実施の形態により、特定の対象に関する時空間データから、条件を満たす時空間データの抽出を効率的に行うことができる。
【００９２】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００９３】
１００  移動履歴管理装置
１０１  通信部
１０２  移動履歴登録部
１０３  移動履歴記憶部
１０４  位置情報変換部
１０５  位置情報変換データ記憶部
１０６  移動履歴削除部
１０７  移動履歴検索部
１０８  入出力部
２００  移動機
２０１  測位部２
２０２  通信部
３００  ネットワーク
【図１】
2017078996.tif 000003
【図２】
2017078996.tif 000004
【図３】
2017078996.tif 000005
【図４】
2017078996.tif 000006
【図５】
2017078996.tif 000007
【図６】
2017078996.tif 000008