(57)【特許請求の範囲】
【請求項１】
複数の軌跡データのペア数の指定を受け付け、
相互に異なる識別情報に対応付けられた複数のノードのうちの何れかのノードにそれぞれが対応付けられた複数の位置情報を含む複数の軌跡データを記憶する記憶部を参照して、特定のノード数以上のノード数の軌跡データを取得し、
取得した前記軌跡データのペアごとに、各ペアに含まれる軌跡データ間で識別情報が共通である共通ノード数を算出し、
算出した前記共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成し、
生成した前記分布情報から、前記記憶部に記憶された前記複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定し、推定されたペア数が、受け付けた前記ペア数に最も近い共通ノード数を他のノード数と決定し、
共通ノード数が、決定した前記他のノード以上の軌跡データのペアを出力する
処理をコンピュータが実行することを特徴とする軌跡データ処理方法。 
【請求項２】
前記決定する処理は、前記分布情報の共通ノード数ごとのペア数と、前記記憶部に記憶された前記複数の軌跡データを組み合わせたペアの総数から、幾何分布又は指数分布を用いて共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定し、推定されたペア数が、受け付けた前記ペア数に最も近い共通ノード数を他のノード数と決定し、
前記取得する処理は、前記特定のノード数から、決定した前記他のノード数となるまでノード数を順に減らして当該ノード数以上のノード数の軌跡データの取得を繰り返す
ことを特徴とする請求項１に記載の軌跡データ処理方法。 
【請求項３】
前記決定する処理は、前記分布情報の最大の共通ノード数から、幾何分布を用いて共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定し、推定されたペア数が、受け付けた前記ペア数に最も近い共通ノード数を他のノード数と決定し、
前記取得する処理は、決定した前記他のノード数以上のノード数の軌跡データを取得する
ことを特徴とする請求項１に記載の軌跡データ処理方法。 
【請求項４】
前記記憶部に記憶された前記複数の軌跡データの最大のノード数、又は、ノード数の多い順に前記複数の軌跡データを組み合わせした組み合わせ数が、受け付けた前記ペア数以上となるノード数に、前記特定のノード数を設定する
処理をさらにコンピュータが実行することを特徴とする請求項１又は２に記載の軌跡データ処理方法。 
【請求項５】
複数の軌跡データのペア数の指定を受け付け、
相互に異なる識別情報に対応付けられた複数のノードのうちの何れかのノードにそれぞれが対応付けられた複数の位置情報を含む複数の軌跡データを記憶する記憶部を参照して、特定のノード数以上のノード数の軌跡データを取得し、
取得した前記軌跡データのペアごとに、各ペアに含まれる軌跡データ間で識別情報が共通である共通ノード数を算出し、
算出した前記共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成し、
生成した前記分布情報から、前記記憶部に記憶された前記複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定し、推定されたペア数が、受け付けた前記ペア数に最も近い共通ノード数を他のノード数と決定し、
共通ノード数が、決定した前記他のノード以上の軌跡データのペアを出力する
処理をコンピュータに実行させることを特徴とする軌跡データ処理プログラム。 
【請求項６】
複数の軌跡データのペア数の指定を受け付ける受付部と、
相互に異なる識別情報に対応付けられた複数のノードのうちの何れかのノードにそれぞれが対応付けられた複数の位置情報を含む複数の軌跡データを記憶する記憶部を参照して、特定のノード数以上のノード数の軌跡データを取得する取得部と、
前記取得部により取得した前記軌跡データのペアごとに、各ペアに含まれる軌跡データ間で識別情報が共通である共通ノード数を算出する算出部と、
前記算出部により算出した前記共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成する生成部と、
前記生成部により生成した前記分布情報から、前記記憶部に記憶された前記複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定し、推定されたペア数が、受け付けた前記ペア数に最も近い共通ノード数を他のノード数と決定する決定部と、
共通ノード数が、前記決定部により決定した前記他のノード数以上の軌跡データのペアを出力する出力部と、
を有することを特徴とする軌跡データ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、軌跡データ処理方法、軌跡データ処理プログラム及び軌跡データ処理装置に関する。
【背景技術】
【０００２】
従来から、複数の軌跡データを用いた経路分析が行われている。例えば、経路分析では、複数の軌跡データの集合の中から、２つの軌跡データの組み合わせたペアごとに経路を比較して経路の共通部分を求め、類似度の高い軌跡データのペアを抽出する。これにより、例えば、軌跡データの類似度の高いユーザ同士を友達として提案したり、タクシーの相乗りを提案するなどに利用できる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１４−４１６１７号公報
【特許文献２】特開２０１１−４００６４号公報
【特許文献３】特開２０１４−２２９０６９号公報
【特許文献４】特開２０１２−２０２７９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、軌跡データの数が多くなるほど、軌跡データのペア数が急増し、経路分析が現実的な時間で処理できなくなる場合がある。例えば、日々得られる軌跡データの集合の経路分析の処理がそれぞれ１日で完了しなくなる場合がある。
【０００５】
一般的に、経路分析では、経路の共通部分が長いペアほど重要である。経路の共通部分は、比較する軌跡データのペアの経路が一致する部分である。このため、経路の共通部分は、比較する軌跡データそれぞれの経路の長さよりも短い。そこで、軌跡の長い軌跡データから経路分析の計算を行い、所定の基準で経路分析の計算を打ち切ることで、計算量を削減することが考えられる。しかし、計算を打ち切る基準を事前に適切に設定することが困難であるため、計算量を適切に削減できない。
【０００６】
一つの側面では、計算量を適切に削減できる軌跡データ処理方法、軌跡データ処理プログラム及び軌跡データ処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
第１の案では、軌跡データ処理方法は、コンピュータが、複数の軌跡データのペア数の指定を受け付ける処理を実行する。軌跡データ処理方法は、コンピュータが、相互に異なる識別情報に対応付けられた複数のノードのうちの何れかのノードにそれぞれが対応付けられた複数の位置情報を含む複数の軌跡データを記憶する記憶部を参照する。軌跡データ処理方法は、コンピュータが、記憶部から特定のノード数以上のノード数の軌跡データを取得する処理を実行する。軌跡データ処理方法は、コンピュータが、取得した軌跡データのペアごとに、各ペアに含まれる軌跡データ間で識別情報が共通である共通ノード数を算出する処理を実行する。軌跡データ処理方法は、コンピュータが、算出した共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成する処理を実行する。軌跡データ処理方法は、コンピュータが、生成した分布情報と、受け付けたペア数とに基づき、特定のノード数未満である他のノード数を決定する処理を実行する。軌跡データ処理方法は、コンピュータが、特定のノード数及び他のノード数間のノード数の軌跡データのペアを出力する処理を実行する。
【発明の効果】
【０００８】
本発明の一の実施態様によれば、計算量を適切に削減できるという効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】図１は、システム構成の一例を説明する図である。
【図２】図２は、軌跡データ処理装置の機能的な構成を概略的に示した図である。
【図３】図３は、移動軌跡データのデータ構成の一例を示す図である。
【図４】図４は、ノード情報のデータ構成の一例を示す図である。
【図５】図５は、リンク情報のデータ構成の一例を示す図である。
【図６】図６は、正規化軌跡データのデータ構成の一例を示す図である。
【図７】図７は、正規化の一例を説明する図である。
【図８】図８は、正規化した軌跡間の共通部分の一例を説明する図である。
【図９】図９は、共通ノード数ごとのペア数の分布の一例を示す図である。
【図１０Ａ】図１０Ａは、共通ノード数ごとのペア数の分布の一例を示す図である。
【図１０Ｂ】図１０Ｂは、共通ノード数ごとのペア数の分布の一例を示す図である。
【図１１Ａ】図１１Ａは、従来の基準を事前に適切に設定することが困難な一例を説明する図である。
【図１１Ｂ】図１１Ｂは、従来の基準を事前に適切に設定することが困難な一例を説明する図である。
【図１１Ｃ】図１１Ｃは、従来の基準を事前に適切に設定することが困難な一例を説明する図である。
【図１２】図１２は、分布の推定の流れを説明する図である。
【図１３】図１３は、第１方式によりペア数の分布を推定した結果の一例を示す図である。
【図１４】図１４は、第２方式の推定を説明する図である。
【図１５】図１５は、移動軌跡データの一例を示す図である。
【図１６】図１６は、道路ノードの構成の一例を示す図である。
【図１７】図１７は、正規化軌跡データの一例を示す図である。
【図１８Ａ】図１８Ａは、処理状況の一例を示す図である。
【図１８Ｂ】図１８Ｂは、処理状況の一例を示す図である。
【図１８Ｃ】図１８Ｃは、処理状況の一例を示す図である。
【図１８Ｄ】図１８Ｄは、処理状況の一例を示す図である。
【図１８Ｅ】図１８Ｅは、処理状況の一例を示す図である。
【図１９】図１９は、正規化処理の流れの一例を示すフローチャートである。
【図２０】図２０は、軌跡データ処理の流れの一例を示すフローチャートである。
【図２１】図２１は、軌跡データ処理プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１０】
以下に、本発明にかかる軌跡データ処理方法、軌跡データ処理プログラム及び軌跡データ処理装置の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。そして、各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１１】
［システム構成］
最初に、システムの一例を説明する。図１は、システム構成の一例を説明する図である。システム１０は、軌跡の経路分析を行うシステムである。システム１０は、軌跡データ処理装置１１と、軌跡記録装置１２とを有する。軌跡データ処理装置１１及び軌跡記録装置１２は、ネットワークＮに通信可能に接続されている。かかるネットワークＮの一態様としては、有線又は無線を問わず、携帯電話などの移動体通信網、インターネット（Internet）、ＬＡＮ（Local  Area  Network）やＶＰＮ（Virtual  Private  Network）などの任意の種類の通信網を採用できる。なお、図１の例では、軌跡記録装置１２を１台ずつ設けた場合を例示したが、これに限定されず、軌跡記録装置１２を任意の数とすることができる。
【００１２】
軌跡記録装置１２は、移動の軌跡を記録する装置である。例えば、軌跡記録装置１２は、スマートフォンやタブレット端末などの携帯型の情報処理装置、電車や車などの車両に搭載される車載器などである。軌跡記録装置１２は、ＧＰＳ（global  positioning  system）モジュールなどの位置を検出可能なセンサが設けられており、周期的に現在位置を検出し、検出した現在位置の位置情報を軌跡データとして記録する。軌跡記録装置１２は、所定のタイミングで軌跡データを軌跡データ処理装置１１へアップロードする。例えば、軌跡記録装置１２は、ネットワークＮを介して軌跡データをアップロードする。なお、軌跡記録装置１２は、メモリカード等の記憶媒体を介して軌跡データを軌跡データ処理装置１１へアップロードしてもよい。
【００１３】
軌跡データ処理装置１１は、軌跡データの経路分析を行う装置である。軌跡データ処理装置１１は、例えば、パーソナルコンピュータやサーバコンピュータなどのコンピュータである。軌跡データ処理装置１１は、１台のコンピュータとして実装してもよく、また、複数台のコンピュータにより実装してもよい。なお、本実施例では、軌跡データ処理装置１１を１台のコンピュータとした場合を例として説明する。
【００１４】
［軌跡データ処理装置の構成］
次に、軌跡データ処理装置１１の構成について説明する。図２は、軌跡データ処理装置の機能的な構成を概略的に示した図である。軌跡データ処理装置１１は、通信Ｉ／Ｆ（インタフェース）部２０と、入力部２１と、表示部２２と、記憶部２３と、制御部２４とを有する。なお、軌跡データ処理装置１１は、上記の機器以外の他の機器を有してもよい。
【００１５】
通信Ｉ／Ｆ部２０は、他の装置との間で通信制御を行うインタフェースである。通信Ｉ／Ｆ部２０は、ネットワークＮを介して他の装置と各種情報を送受信する。例えば、通信Ｉ／Ｆ部２０は、ネットワークＮを介して軌跡記録装置１２から軌跡データを受信する。通信Ｉ/Ｆ部２０としては、ＬＡＮカードなどのネットワークインタフェースカードを採用できる。
【００１６】
入力部２１は、各種の情報を入力する入力デバイスである。入力部２１としては、マウスやキーボードなどの操作の入力を受け付ける入力デバイスが挙げられる。入力部２１は、経路分析に関する各種の入力を受け付ける。
【００１７】
表示部２２は、各種情報を表示する表示デバイスである。表示部２２としては、ＬＣＤ（Liquid  Crystal  Display）やＣＲＴ（Cathode  Ray  Tube）などの表示デバイスが挙げられる。表示部２２は、各種情報を表示する。例えば、表示部２２は、操作画面など各種の画面を表示する。
【００１８】
記憶部２３は、各種のデータを記憶する記憶デバイスである。例えば、記憶部２３は、ハードディスク、ＳＳＤ（Solid  State  Drive）、光ディスクなどの記憶装置である。なお、記憶部２３は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ、ＮＶＳＲＡＭ（Non  Volatile  Static  Random  Access  Memory）などのデータを書き換え可能な半導体メモリであってもよい。
【００１９】
記憶部２３は、制御部２４で実行されるＯＳ（Operating  System）や各種プログラムを記憶する。例えば、記憶部２３は、後述する正規化処理及び軌跡データ処理を実行するプログラムを含む各種のプログラムを記憶する。さらに、記憶部２３は、制御部２４で実行されるプログラムで用いられる各種データを記憶する。例えば、記憶部２３は、移動軌跡データ３０と、ノード情報３１と、リンク情報３２と、正規化軌跡データ３３と、ペア共通部分情報３４と、分析結果情報３５とを記憶する。
【００２０】
移動軌跡データ３０は、軌跡記録装置１２からアップロードされた軌跡データを記憶したデータである。図３は、移動軌跡データのデータ構成の一例を示す図である。図３に示すように、移動軌跡データ３０は、「軌跡ＩＤ」、「Ｘ座標」、「Ｙ座標」の項目を有する。なお、図３に示した移動軌跡データ３０の各項目は、一例であり、その他の項目を有してもよい。また、移動軌跡データ３０のデータ構成も一例であり、これに限定されるものではない。
【００２１】
軌跡ＩＤの項目は、それぞれの軌跡を識別する識別情報を記憶する領域である。軌跡には、識別情報として、ユニークな軌跡ＩＤ（identification）が付与される。軌跡ＩＤは、例えば、アップロードされた軌跡データごとに付与してもよく、軌跡記録装置１２ごとに付与してもよく、軌跡記録装置１２を操作するユーザごとに付与してもよい。また、軌跡ＩＤは、例えば、軌跡記録装置１２ごとに日別に新たに付与してもよく、所定期間や所定の移動範囲ごと新たに付与してもよい。軌跡ＩＤは、１つの軌跡を区切る単位で付与されていればよい。Ｘ座標及びＹ座標の項目は、位置を示す位置情報を記憶する領域である。例えば、Ｘ座標及びＹ座標の項目には、ＧＰＳで測位された緯度及び経度の情報が格納される。図３の例では、軌跡ＩＤ「ｔ１」は、Ｘ座標が「ｚ１」、Ｙ座標が「ｗ１」であることを示す。
【００２２】
図２に戻り、ノード情報３１は、軌跡を正規化する際のノードの位置を記憶したデータである。図４は、ノード情報のデータ構成の一例を示す図である。図４に示すように、ノード情報３１は、「ノード」、「Ｘ座標」、「Ｙ座標」の項目を有する。なお、図４に示したノード情報３１の各項目は、一例であり、その他の項目を有してもよい。また、ノード情報３１のデータ構成も一例であり、これに限定されるものではない。
【００２３】
ノードの項目は、それぞれのノードを識別する識別情報を記憶する領域である。ノードには、識別情報が付与される。Ｘ座標及びＹ座標の項目は、ノードの位置を示す位置情報を記憶する領域である。例えば、Ｘ座標及びＹ座標の項目には、ノードの位置を示す緯度及び経度の情報が格納される。図４の例では、ノードＮ１は、Ｘ座標が「ｘ１」、Ｙ座標が「ｙ１」であることを示す。
【００２４】
図２に戻り、リンク情報３２は、ノード間のリンクに関する情報を記憶したデータである。図５は、リンク情報のデータ構成の一例を示す図である。図５に示すように、リンク情報３２は、「リンク」の項目を有する。なお、図５に示したリンク情報３２の各項目は、一例であり、その他の項目を有してもよい。また、リンク情報３２のデータ構成も一例であり、これに限定されるものではない。
【００２５】
リンクの項目は、接続関係にある各ノードの識別情報を記憶する領域である。リンクの項目には、接続関係にある各ノードの識別情報がリンクとして格納される。図５の例では、ノードＮｉとノードＮｊが、接続関係があることを示す。
【００２６】
図２に戻り、正規化軌跡データ３３は、移動軌跡データ３０の位置情報をノードに正規化したデータである。図６は、正規化軌跡データのデータ構成の一例を示す図である。図６に示すように、正規化軌跡データ３３は、「ＩＤ」、「正規化軌跡」の項目を有する。なお、図６に示した正規化軌跡データ３３の各項目は、一例であり、その他の項目を有してもよい。また、正規化軌跡データ３３のデータ構成も一例であり、これに限定されるものではない。
【００２７】
ＩＤの項目は、正規化された軌跡の軌跡ＩＤを記憶する領域である。正規化軌跡の項目は、軌跡に沿って、軌跡の各位置に対応するノードの識別情報を記憶する領域である。図６の例では、ＩＤ「ｔ１」の軌跡は、ノードＮ１１、Ｎ１２、Ｎ１３、Ｎ１４を順に通過していることを示す。
【００２８】
図２に戻り、ペア共通部分情報３４は、移動軌跡データ３０に対して経路分析を行って、軌跡のペアごとの共通部分に関する情報を記憶したデータである。分析結果情報３５は、経路分析の分析結果に関する情報を記憶したデータである。ペア共通部分情報３４及び分析結果情報３５について、データ構成の一例は、後述する。
【００２９】
制御部２４は、軌跡データ処理装置１１を制御するデバイスである。制御部２４としては、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）等の電子回路や、ＡＳＩＣ（Application  Specific  Integrated  Circuit）、ＦＰＧＡ（Field  Programmable  Gate  Array）等の集積回路を採用できる。制御部２４は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部２４は、各種のプログラムが動作することにより各種の処理部として機能する。例えば、制御部２４は、格納部４０と、正規化部４１と、受付部４２と、取得部４３と、算出部４４と、生成部４５と、決定部４６と、出力部４７とを有する。
【００３０】
格納部４０は、軌跡記録装置１２からアップロードされた軌跡データを移動軌跡データ３０に格納する。例えば、格納部４０は、軌跡データがアップロードされるごとに軌跡ＩＤを付与して軌跡データを移動軌跡データ３０に格納する。
【００３１】
正規化部４１は、移動軌跡データ３０に記憶された位置情報をノードに正規化する。例えば、正規化部４１は、ノード情報３１及びリンク情報３２に基づき、移動軌跡データ３０に記憶された軌跡の各位置情報を、位置が対応するノードで示したデータに正規化する。例えば、正規化部４１は、移動軌跡データ３０に記憶された軌跡の各位置情報を、ノード情報３１の各ノードの位置情報とマップマッチングを行って、軌跡の位置をノードで示したデータに正規化する。正規化部４１は、正規化した軌跡データを正規化軌跡データ３３に格納する。
【００３２】
ここで、正規化の一例を説明する。図７は、正規化の一例を説明する図である。図７には、軌跡Ｌ１、Ｌ２が示されている。また、図７には、ノードＡ〜Ｈが示されている。正規化部４１は、軌跡Ｌ１、Ｌ２の各位置情報を、ノードＡ〜Ｈの各位置情報とマップマッチングを行って、軌跡Ｌ１、Ｌ２をノードで示したデータに正規化する。図７の例では、軌跡Ｌ１は、＜Ａ，Ｅ，Ｆ，Ｂ，Ｃ，Ｄ＞に正規化される。＜Ａ，Ｅ，Ｆ，Ｂ，Ｃ，Ｄ＞は、ノードＡ、ノードＥ、ノードＦ、ノードＢ、ノードＣ、ノードＤを順に通過することを示している。また、軌跡Ｌ２は、＜Ａ，Ｆ，Ｇ，Ｃ，Ｄ＞に正規化される。＜Ａ，Ｆ，Ｇ，Ｃ，Ｄ＞は、ノードＡ、ノードＦ、ノードＧ、ノードＣ、ノードＤを順に通過することを示している。
【００３３】
このように軌跡をノードに正規化することにより、軌跡間の共通部分を特定し易くなる。図８は、正規化した軌跡間の共通部分の一例を説明する図である。図８には、図７に示した軌跡Ｌ１の正規化した軌跡＜Ａ，Ｅ，Ｆ，Ｂ，Ｃ，Ｄ＞と、軌跡Ｌ２の正規化した軌跡＜Ａ，Ｆ，Ｇ，Ｃ，Ｄ＞とが示されている。正規化した軌跡間の共通部分は、一致するノードを求めることにより特定できる。軌跡間の共通部分は、一致するノードの間や前後に、一致しないノードがあってもよい。図８の例では、軌跡Ｌ１の＜Ａ，Ｅ，Ｆ，・・・＞と、軌跡Ｌ２の＜Ａ，Ｆ，・・・＞では軌跡Ｌ１のノードＡとノードＦの間にノードＥがあるが、ノードＡとノードＦは共通部分となる。図８の例では、軌跡Ｌ１の＜Ａ，Ｅ，Ｆ，Ｂ，Ｃ，Ｄ＞と、軌跡Ｌ２の＜Ａ，Ｆ，Ｇ，Ｃ，Ｄ＞の共通文は、＜Ａ，Ｆ，Ｃ，Ｄ＞と特定される。以下、本実施例では、軌跡の長さをノード数により表すものとする。例えば、軌跡の長さは、正規化した軌跡データに含まれるノードのノード数で表す。例えば、軌跡Ｌ１は、正規化した軌跡が＜Ａ，Ｅ，Ｆ，Ｂ，Ｃ，Ｄ＞であるため、長さをノード数の６とする。また、軌跡データの共通部分の長さは、共通部分に含まれるノードのノード数で表す。例えば、軌跡Ｌ１と軌跡Ｌ２の共通部分は、＜Ａ，Ｆ，Ｃ，Ｄ＞であるため、長さをノード数の４とする。
【００３４】
受付部４２は、各種の操作を行う。例えば、受付部４２は、経路分析に関する各種の情報の入力を受け付ける。例えば、受付部４２は、操作画面を表示して、経路分析で抽出する軌跡データのペアの目標数として、複数の軌跡データのペア数の指定を受け付ける。
【００３５】
取得部４３は、記憶部２３の正規化軌跡データ３３を参照して、特定のノード数以上のノード数の軌跡データを取得する。例えば、取得部４３は、正規化軌跡データ３３に記憶された軌跡の最大のノード数から、後述する決定部４６により決定したノード数となるまで、ノード数を順に減らして当該ノード数以上のノード数の軌跡データを取得する。例えば、取得部４３は、正規化軌跡データ３３に記憶された軌跡の最大のノード数が６である場合、最初に、正規化軌跡データ３３からノード数が６の軌跡データを読み出す。最大のノード数が６である場合、ノード数が６の軌跡データを読み出すことで、ノード数が６以上の軌跡データが取得される。次に、取得部４３は、ノード数が５の軌跡データを読み出す。ノード数が６以上の軌跡データが最初に取得されているため、ノード数が５の軌跡データを読み出すことで、ノード数が５以上の軌跡データが取得される。取得部４３は、同様に、後述する決定部４６により決定したノード数となるまで、ノード数を１ずつ順に減らして当該ノード数の軌跡データを読み出す。
【００３６】
算出部４４は、取得部４３により取得した軌跡データのペアごとに、各ペアに含まれる軌跡データ間でノードの識別情報が共通である共通ノード数を算出する。例えば、算出部４４は、取得部４３により軌跡データを取得すると、取得した軌跡データを組み合わせたペアごとに、各ペアに含まれる軌跡データ間の共通ノード数を算出する。例えば、算出部４４は、ノード数が６の軌跡データが取得されると、ノード数が６の軌跡データのペアごとに、各ペアに含まれる軌跡データ間の共通ノード数を算出する。次に、算出部４４は、ノード数が５の軌跡データが取得されると、ノード数が６及び５の軌跡データのペアごとに、各ペアに含まれる軌跡データ間の共通ノード数を算出する。ここで、ノード数が６のみの軌跡データのペアの共通ノード数は、最初に算出されている。このため、算出部４４は、共通ノード数を算出済みのペアを除いて、軌跡データのペアごとに、共通ノード数を算出する。例えば、算出部４４は、ノード数が６の軌跡データとノード数が５の軌跡データとを組み合わせたペア、及び、ノード数が５の軌跡データのみを組み合わせたペアごとに、共通ノード数を算出する。
【００３７】
生成部４５は、算出部４４により算出した共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成する。
【００３８】
ここで、一般的に、経路分析では、経路の共通部分が長いペアほど重要である。経路の共通部分は、比較する軌跡データのペアの経路が一致する部分である。このため、経路の共通部分は、比較する軌跡データそれぞれの経路の長さよりも短い。例えば、ノード数が３の２つの軌跡データを比較した場合、経路の共通部分は、ノード数が３以下であり、ノード数が４以上となることはない。このため、ノード数の多い軌跡データから順に経路の共通部分である共通ノード数を算出すると、共通ノード数が多いものからペア数が確定する。
【００３９】
図９は、共通ノード数ごとのペア数の分布の一例を示す図である。図９の例は、取得対象のノード数を６から１へ１ずつ順に減らして、取得対象のノード数以上の軌跡データ間の共通ノード数を求め、共通ノード数ごとのペア数の分布を示したものである。図９の各グラフの縦軸は、ペア数を対数目盛で示している。図９の各グラフの横軸は、共通ノード数を示している。
【００４０】
図９の例では、最初に、ノード数が６以上の軌跡データのペアの共通ノード数が算出され、ノード数が６以上の軌跡データによるペア数の分布が生成される。ノード数が６以上の軌跡データによるペア数の分布は、共通ノード数が５のペア数が１であり、共通ノード数が１のペア数が２となっている。次に、図９の例では、ノード数が５以上の軌跡データのペアの共通ノード数が算出され、ノード数が５以上の軌跡データによるペア数の分布が生成される。ノード数が５以上の軌跡データによるペア数の分布は、共通ノード数が５のペア数が１であり、共通ノード数が０のペア数が２となっている。ここで、ノード数が４以下の軌跡データのペアは、経路の共通部分のノード数が４以下であり、経路の共通部分のノード数が５以上となることはない。このため、ノード数が５以上の軌跡データによるペア数の分布では、経路の共通部分のノード数が５以上のペア数が確定する。図９の例では、共通ノード数が５のペア数が１と確定する。
【００４１】
次に、図９の例では、ノード数が４以上の軌跡データのペアの共通ノード数が算出され、ノード数が４以上の軌跡データによるペア数の分布が生成される。これにより、経路の共通部分のノード数が４以上となるペア数が確定する。図９の例では、共通ノード数が４のペア数が０と確定する。次に、図９の例では、ノード数が３以上の軌跡データのペアの共通ノード数が算出され、ノード数が３以上の軌跡データによるペア数の分布が生成される。これにより、経路の共通部分のノード数が３以上となるペア数が確定する。図９の例では、共通ノード数が３のペア数が４と確定する。次に、図９の例では、ノード数が２以上の軌跡データのペアの共通ノード数が算出され、ノード数が２以上の軌跡データによるペア数の分布が生成される。これにより、経路の共通部分のノード数が２以上となるペア数が確定する。図９の例では、共通ノード数が２のペア数が１９と確定する。次に、図９の例では、ノード数が１以上の軌跡データのペアの共通ノード数が算出され、ノード数が１以上の軌跡データによるペア数の分布が生成される。これにより、経路の共通部分のノード数が１以上となるペア数が確定する。図９の例では、共通ノード数が１のペア数が６７と確定する。また、経路の共通部分のノード数が０となる何れもとも経路が共通しないペア数も確定する。図９の例では、共通ノード数が０のペア数が２０９と確定する。このように、ノード数の多い軌跡データから順に経路の共通部分である共通ノード数を算出すると、共通ノード数が多いものからペア数が確定する。
【００４２】
一般的に、複数の軌跡データを組み合わせたペアごとに経路の共通部分を求めた場合、共通ノード数ごとのペア数の分布は、共通ノード数が多いほどペア数が急激に減少しており、指数的な分布になっている場合が多い。図１０Ａ及び図１０Ｂは、共通ノード数ごとのペア数の分布の一例を示す図である。図１０Ａ及び図１０Ｂに示すように、共通ノード数が多いほど、ペア数が急激に減少しており、指数的な分布になっている。しかし、分布ごとに、分布の最大値や、共通ノード数に対するペア数の減り方が異なる。このため、計算を打ち切る基準を事前に適切に設定することが困難である。
【００４３】
例えば、抽出するペア数の目標数を６０とする。このような場合に、例えば、事前に、計算を打ち切る基準として、軌跡データの長さをノード数が３と定める。図１１Ａ及び図１１Ｂは、従来の基準を事前に適切に設定することが困難な一例を説明する図である。図１１Ａ及び図１１Ｂには、共通ノード数ごとのペア数の分布の一例が示されており、分布が異なる。図１１Ａの例では、共通部分のノード数が３まで軌跡データのペアを抽出すると、ペア数が７９となり、目標の６０よりも多く、軌跡データのペアの絞込みができない。一方、図１１Ｂの例では、共通部分のノード数が３まで軌跡データのペアを抽出すると、ペア数が１と目標の６０よりも少なくなり、十分なペア数が得られない。
【００４４】
また、例えば、目標数の６０が得られるまで計算を行うものとする。図１１Ｃは、従来の基準を事前に適切に設定することが困難な一例を説明する図である。図１１Ｃには、共通ノード数ごとのペア数の分布の一例が示されている。図１１Ｃの分布では、共通部分のノード数が１以上の軌跡データのペア数は、５４となり、目標の６０よりも少ない。そこで、共通部分のノード数が０まで含めるとペア数が多くなり、軌跡データのペアの絞込みができない。
【００４５】
そこで、決定部４６は、生成部４５により生成した分布情報と、指定された目標数とに基づき、特定のノード数未満である他のノード数を決定する。例えば、決定部４６は、分布情報から、正規化軌跡データ３３に記憶された複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する。そして、決定部４６は、推定されたペア数が、指定された目標数に最も近い共通ノード数を他のノード数と決定する。すなわち、決定部４６は、他のノード数として、計算を打ち切る基準とする共通ノード数を決定する。
【００４６】
出力部４７は、各種の出力を行う。例えば、出力部４７は、特定のノード数及び他のノード数間のノード数の軌跡データのペアを出力する。例えば、出力部４７は、特定のノード数と、計算を打ち切る基準とされた共通ノード数間のノード数の軌跡データのペアを経路分析の結果として分析結果情報３５に出力する。なお、出力部４７は、経路分析の結果を他の装置や他のプログラムへ出力してもよい。また、出力部４７は、経路分析の結果を表示した画面を表示部２２へ出力してもよい。
【００４７】
上述したように、一般的に、複数の軌跡データを組み合わせたペアごとに経路の共通部分を求めた場合、共通ノード数ごとのペア数の分布は、指数的な分布になる。このため、分布の一部の情報から分布全体を推定できる。決定部４６は、生成部４５により生成した分布情報の分布に基づき、全ての軌跡データでの分布全体を推定し、計算を進めるかどうかを判断し、計算を行う範囲とするノード数を決定する。図１２は、分布の推定の流れを説明する図である。図１２には、ノード数が２以上の軌跡データについて、共通ノード数ごとのペア数の分布が示されている。ノード数が２以上のペア数は、確定している。図１２の例では、目標数を４０とする。図１２の例では、共通ノード数が２以上のペア数は、２４である。例えば、決定部４６は、ノード数が２以上のペア数の分布を用いて、全ての軌跡データでの分布全体を推定する。図１２の例では、推定された分布から、共通ノード数が１以上のペア数は、７０と推定される。決定部４６は、共通ノード数が２以上のペア数の２４の方が、推定された共通ノード数が１以上のペア数の７０よりも、目標数を４０に近いため、目標数に最も近い共通ノード数を２と決定する。これにより、ノード数が１以上の軌跡データについて、計算が行われずに計算を終了するため、計算量を削減できる。
【００４８】
ここで、軌跡データのペア数を推定する計算方法について説明する。軌跡データのペア数を推定する計算方法として複数の方式を例示する。
【００４９】
最初に、第１方式を説明する。第１方式では、計算済みの分布で確定部分と未確定部分の値を用いて幾何分布により近似する。幾何分布は、一般的に以下の式（１）のように表せる。
【００５０】
Ｐ（Ｘ＝ｋ）＝ｐ・ｑｋ      （１）
【００５１】
この幾何分布の式（１）は、以下の式（２）から以下の式（３）、（４）のように近似できる。
【数１】
0006677040.tif 000002
【００５２】
式（３）、（４）についてｋ＝１,・・・,Ｋで平均を取とると、以下の式（５）、（６）のように表せる。
【００５３】
【数２】
0006677040.tif 000003
【００５４】
ここで、
Ｋ：計算済みの共通ノード数の最大値
Ｎ：推定対象の軌跡データの組み合わせの総数
Ｎｋ：計算済みの共通ノード数がｋ以上のペア数
Ｎ~ｋ：共通ノード数がｋ以上の組の数の推定値
【００５５】
図１３は、第１方式によりペア数の分布を推定した結果の一例を示す図である。図１３の例では、ノード数が３以上、ノード数が２以上、ノード数が１以上（全ての軌跡データ計算）と順に、共通ノード数ごとのペア数の分布を計算した場合を示している。図１３の例では、それぞれの分布で共通ノード数ｋごとに、共通ノード数ｋ以上のペア数を累計したペア数がＮｋとなる。また、図１３の例では、ペア数の分布を推定した推定値が示されている。推定値は、次のように算出する。図１３の例では、計算済みの共通ノード数の最大値Ｋは、５である。また、図１３の例では、推定対象の軌跡データの組み合わせの総数Ｎは、３００である。図１３の例では、Ｋ＝５、Ｎ＝３００として、計算済みの共通ノード数がｋ以上のペア数Ｎｋを用いて、式（６）からｑの値を求める。そして、図１３の例では、求めたｑの値を用いて式（５）から共通部分のノード数ｋの場合の推定値Ｎ~ｋを求めている。
【００５６】
ここで、式（５）では、共通ノード数ｋ以上となる軌跡データのペア数の推定値Ｎ~ｋが算出される。例えば、ｋ＝３とした場合、共通ノード数が３以上となる軌跡データのペア数の推定値Ｎ~３が算出される。また、ｋ＝２とした場合、共通ノード数が２以上となる軌跡データのペア数の推定値Ｎ~２が算出される。共通ノード数ｋのペア数の推定値は、共通ノード数ｋ以上となる軌跡データのペア数の推定値Ｎ~ｋから、共通ノード数ｋ＋１以上となる軌跡データのペア数の推定値Ｎ~ｋ＋１を減算して求める。例えば、共通ノード数が２のペア数の推定値は、共通ノード数が２以上となる軌跡データのペア数の推定値Ｎ~２から、共通ノード数が３以上となる軌跡データのペア数の推定値Ｎ~３を減算して求める。
【００５７】
第１方式では、分布の下限を推定している。Ｎｋの値は、例えば、ノード数が３以上や、ノード数が２以上のように、全ての軌跡データの計算が行われていない途中の段階で、全ての軌跡データを計算したときの値（真の値）以下となっている。このため、途中の段階では、Ｎｋの値を使って計算したＮ~ｋの値は、真の値を用いて計算したＮ~ｋの値の下限になる。
【００５８】
また、第１方式では、推定の計算には、全ての共通ノード数ｋについて、共通ノード数ｋ以上のペア数を累計したペア数Ｎｋを用いている。このように、未確定部分のペア数Ｎｋも加えて推定値Ｎ~ｋを計算することにより、加えない場合よりも、ペア数Ｎｋに真の値を用いて計算した推定値Ｎ~ｋに値が近くなる。すなわち、第１方式では、計算済みの分布で確定部分と未確定部分の値を用いることが精度を向上させている。
【００５９】
次に、第２方式を説明する。第２方式では、計算済みの共通ノード数の最大値を用いて幾何分布により近似する。
【００６０】
目標数をＮ０とする。基準ｋ０に対して、Ｎｑｋ０≒Ｎ０とおくと、以下の式（７）より式（８）のように表せる。
【００６１】
【数３】
0006677040.tif 000004
【００６２】
この式（８）は、推定対象の軌跡データの組み合わせの総数Ｎと、目標数Ｎ０のみから計算できる。これは、第１方式では、Logｑを式（６）のように近似したのに対し、第２方式では、Logｑを以下の式（９）のように近似している。すなわち、第２方式では、分布のパラメータｑを、計算済みの共通ノード数の最大値Ｋと、推定対象の軌跡データの組み合わせの総数Ｎのみで近似している。
【００６３】
【数４】
0006677040.tif 000005
【００６４】
図１４は、第２方式の推定を説明する図である。図１４の例では、ノード数が２以上の軌跡データについて、共通ノード数ごとのペア数の分布が示されている。図１４の例では、計算済みの分布から共通ノード数の最大値Ｋが５と求まる。図１４の例では、指定された目標数Ｎ０を４０とする。また、図１４の例では、推定対象の軌跡データの組み合わせの総数Ｎを３００とする。これにより、式（８）の右辺の値を算出できる。例えば、右辺は、０．３５となる。この値は、総数Ｎと目標数Ｎから事前に算出できる。第２方式では、共通部分の最大値Ｋ＝５を使って分布の下限を推定する。図１４には、推定された共通ノード数に対するペア数の分布が示されている。また、図１４には、共通ノード数ごとに、共通ノード数以上のペア数を累計したペア数の分布が示されている。第２方式では、共通ノード数の最大値Ｋを用いて、式（８）から基準ｋ０の値を計算する。図１４の例では、基準ｋ０が１．７５と算出される。これは、目標数である４０に対応する基準ｋ０の値を求めることに該当する。第２方式では、基準ｋ０が１．７５を四捨五入して、目標数に最も近い共通ノード数を２と決定する。すなわち、第２方式では、共通部分の最大値Ｋが定まった段階で、目標数Ｎ０に最も近い共通ノード数が決定する。
【００６５】
決定部４６により決定された共通ノード数が、現在の取得が完了しているノード数以下である場合、取得部４３は、決定した最も近い共通ノード数となるまでノード数を順に減らして当該ノード数以上のノード数の軌跡データの取得を繰り返す。これにより、算出部４４、生成部４５、決定部４６は、再度取得された軌跡データに対して再度を同様の処理を行う。すなわち、取得部４３、算出部４４、生成部４５、決定部４６は、決定部４６により決定された共通ノード数が、現在の取得が完了しているノード数となるまでノード数を順に減らして処理を繰り返す。
【００６６】
次に、具体例を用いて説明する。図１５は、移動軌跡データの一例を示す図である。例えば、図１５に示す移動軌跡データ３０が記憶されているものとする。図１６は、道路ノードの構成の一例を示す図である。例えば、道路などのネットワークは、図１６に示すノードの接続関係があるものとする。図１６には、ネットワークに対応したノード情報３１とリンク情報３２のデータが示されている。
【００６７】
正規化部４１は、移動軌跡データ３０に記憶された軌跡の各位置情報を、ノード情報３１及びリンク情報３２に基づき、軌跡の位置をノードで示したデータに正規化する。図１７は、正規化軌跡データの一例を示す図である。図１７には、軌跡の位置をノードで示した正規化軌跡データ３３が示されている。図１７の例では、ＩＤが１から２５の正規化された軌跡が示されている。また、図１７の例では、ノード数の多い順（軌跡の長い順）に、軌跡をソートした結果が示されている。
【００６８】
受付部４２は、抽出するペア数の目標数の指定を受け付ける。ここでは、目標数は、４０と指定されたものとする。
【００６９】
取得部４３は、正規化軌跡データ３３を参照して、特定のノード数以上のノード数の軌跡データを取得する。例えば、取得部４３は、正規化軌跡データ３３に記憶された軌跡の最大のノード数から、ノード数を順に減らして当該ノード数以上のノード数の軌跡データを取得する。図１７の例では、取得部４３は、最初に、正規化軌跡データ３３に記憶された軌跡の最大のノード数であるノードが６以上のノード数の軌跡データを読み出す。
【００７０】
ここで、処理中の状況をわかり易くするため、データ及びパラメータなどの処理状況を図示して説明する。図１８Ａは、処理状況の一例を示す図である。図１８Ａの例は、ノードが６以上のノード数の軌跡データに対する処理状況を示している。
【００７１】
処理ノード数ｘには、読み出しを行った軌跡のノード数が記憶される。図１７の例では、処理ノード数ｘに最大のノード数である６が設定される。候補リストは、読み出された軌跡が記憶される。処理ノード数ｘが６の場合、候補リストには、ノード数が６以上のＩＤが６、７、２１の軌跡が記憶される。
【００７２】
算出部４４は、取得した軌跡データのペアごとに、各ペアに含まれる軌跡データ間の共通ノード数を算出する。図１７の例では、算出部４４は、ＩＤが６、７、２１の軌跡を組み合わせたペアごとに、共通ノード数を算出する。例えば、算出部４４は、ＩＤが６の軌跡＜Ｂ，Ａ，Ｆ，Ａ，Ｂ，Ｃ＞と、ＩＤが７の軌跡＜Ｂ，Ａ，Ｆ，Ｇ，Ｂ，Ｃ＞を比較して、共通ノード数を５と算出する。
【００７３】
図１８Ａには、共通ノードの計算結果が表形式で示されている。共通ノードの計算結果は、比較した軌跡のＩＤを縦横の項目として、軌跡間で算出された共通ノード数が示さている。例えば、ＩＤが６、７、２１の軌跡を組み合わせるため、図１８Ａの共通ノードの計算結果には、横の項目にＩＤの６、７が並び、縦の項目にＩＤの７、２１が並んでいる。図１８Ａの共通ノードの計算結果では、横の項目が６、縦の項目が７に対応する領域の値が５であることから、ＩＤが６とＩＤが７の軌跡間で算出された共通ノード数が５であることを示している。
【００７４】
生成部４５は、算出部４４により算出した共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成する。図１８Ａには、分布情報に、共通ノード数ごとのペア数が示されている。図１８Ａには、共通ノード数が５についてペア数が１と格納されている。また、共通ノード数が４から１についてペア数が０と格納されている。また、共通ノード数が０についてペア数が２と格納されている。
【００７５】
決定部４６は、分布情報から、正規化軌跡データ３３に記憶された複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する。そして、決定部４６は、推定されたペア数が、指定された目標数に最も近い共通ノード数を、計算を打ち切る基準の共通ノード数と決定する。
【００７６】
図１８Ａには、第１方式と第２方式でそれぞれ推定する場合のパラメータと推定結果が示さている。図１８Ａの例では、ＩＤが１から２５の軌跡を組み合わせたペアについて推定を行うため、推定対象の軌跡データの組み合わせの総数Ｎは、３００となる。
【００７７】
第１方式では、分布情報から、計算済みの共通ノード数がｋ以上のペア数Ｎｋを求める。例えば、共通ノード数が５以上のペア数Ｎ５は、共通ノード数が５のペア数が１であるため、１となる。共通ノード数が０以上のペア数Ｎ０は、共通ノード数が５のペア数の１と共通ノード数が０のペア数の２を加算して、３となる。また、計算済みの共通ノード数の最大値Ｋは、共通ノード数が５が最大であるため、５となる。第１方式では、式（６）からｑの値を算出し、算出されたｑの値を用いて式（５）から共通部分のノード数ｋの場合の推定値Ｎ~ｋをそれぞれ算出する。図１８Ａの例では、推定値Ｎ~１が、２２．２であり、推定値Ｎ~０が、３００．０である。決定部４６は、共通ノード数が１の推定値Ｎ~１が目標数の４０に最も近いため、計算を打ち切る基準を１と決定する。
【００７８】
一方、第２方式では、分布情報から、計算済みの共通ノード数の最大値Ｋが５となる。また、推定対象の軌跡データの組み合わせの総数Ｎは、３００である。また、目標数Ｎ０は、４０である。第２方式では、式（８）から基準ｋ０の値が算出し、基準ｋ０の値を四捨五入した値を計算を打ち切る基準と決定する。図１８Ａの例では、基準は、２と決定する。第２方式では、図１８Ａに示すように、計算済みの共通ノード数の最大値Ｋが定まった段階で、式（８）の各パラメータが以降変化しないため、計算を打ち切る基準が確定する。
【００７９】
出力部４７は、共通ノード数が基準のノード数以上となる軌跡データのペアの各ＩＤ、及び、共通ノード数をペア共通部分情報３４に格納する。図１８Ａの例では、ペア共通部分情報３４には、ＩＤの６とＩＤの７に対応づけて軌跡の共通ノード数の５が格納される。
【００８０】
図１８Ａの例では、第１方式及び第２方式とも、処理ノード数ｘの値「６」が、基準の値となっていない。この場合、取得部４３は、処理ノード数ｘの値を１減算して「５」とし、ノード数が５以上のノード数の軌跡データを取得する。例えば、ノード数が６以上の軌跡データが既に取得されているため、取得部４３は、ノード数が５の軌跡データを読み出す。
【００８１】
ここで、図１７に示した正規化軌跡データ３３には、ノード数が５の軌跡が無い。新しく読み出される軌跡が無い場合、分布情報は、変化しない。このため、第１方式の基準は、図１８Ａの状態のままである。取得部４３は、処理ノード数ｘの値「５」が、基準の値となっていない。この場合、取得部４３は、処理ノード数ｘの値を１減算して「４」とし、ノード数が４以上のノード数の軌跡データを取得する。例えば、ノード数が５以上の軌跡データが既に取得されているため、取得部４３は、ノード数が４の軌跡データを読み出す。
【００８２】
図１８Ｂは、処理状況の一例を示す図である。図１８Ｂの例では、候補リストに、ノード数が４のＩＤが８、１２、１８の軌跡が追加されている。
【００８３】
算出部４４は、共通ノード数を算出済みのペアを除いて、軌跡データのペアごとに、共通ノード数を算出する。例えば、算出部４４は、ノード数が６の軌跡データとノード数が４の軌跡データとを組み合わせたペア、及び、ノード数が４の軌跡データのみを組み合わせたペアごとに、共通ノード数を算出する。図１８Ｂには、共通ノードの計算結果が示されている。
【００８４】
生成部４５は、算出部４４により算出した共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成する。図１８Ｂには、分布情報が示されている。
【００８５】
決定部４６は、分布情報から、正規化軌跡データ３３に記憶された複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する。
【００８６】
第１方式では、分布情報から、計算済みの共通ノード数がｋ以上のペア数Ｎｋを求めて、式（６）からｑの値が再度算出し、式（５）から共通部分のノード数ｋの場合の推定値Ｎ~ｋをそれぞれ算出する。図１８Ｂの例では、推定値Ｎ~２が、６．２であり、推定値Ｎ~１が、４３．３であり、推定値Ｎ~０が、３００．０である。決定部４６は、共通ノード数が１の推定値Ｎ~１が目標数の４０に最も近いため、計算を打ち切る基準を１と決定する。
【００８７】
一方、第２方式では、計算を打ち切る基準が２と確定されている。
【００８８】
出力部４７は、共通ノード数が基準のノード数以上となる軌跡データのペアの各ＩＤ、及び、共通ノード数をペア共通部分情報３４に格納する。図１８Ｂの例では、ペア共通部分情報３４には、例えば、ＩＤの６とＩＤの８に対応づけて軌跡の共通ノード数の３などが追加されている。
【００８９】
図１８Ｂの例では、第１方式及び第２方式とも、処理ノード数ｘの値「４」が、基準の値となっていない。この場合、取得部４３は、処理ノード数ｘの値を１減算して「３」とし、ノード数が３以上のノード数の軌跡データを取得する。例えば、ノード数が４以上の軌跡データが既に取得されているため、取得部４３は、ノード数が３の軌跡データを読み出す。
【００９０】
図１８Ｃは、処理状況の一例を示す図である。図１８Ｃの例では、候補リストに、ノード数が３のＩＤが２、３、１０、２３、２５の軌跡が追加されている。
【００９１】
算出部４４は、上記と同様に、共通ノード数を算出済みのペアを除いて、軌跡データのペアごとに、共通ノード数を算出する。図１８Ｃには、共通ノードの計算結果が示されている。
【００９２】
生成部４５は、算出部４４により算出した共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成する。図１８Ｃには、分布情報が示されている。
【００９３】
決定部４６は、分布情報から、正規化軌跡データ３３に記憶された複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する。
【００９４】
第１方式では、分布情報から、計算済みの共通ノード数がｋ以上のペア数Ｎｋを求めて、式（６）からｑの値が再度算出し、式（５）から共通部分のノード数ｋの場合の推定値Ｎ~ｋをそれぞれ算出する。図１８Ｃの例では、推定値Ｎ~２が１３．３であり、推定値Ｎ~１が６３．２であり、推定値Ｎ~０が３００．０である。決定部４６は、共通ノード数が１の推定値Ｎ~１が目標数の４０に最も近いため、計算を打ち切る基準を１と決定する。
【００９５】
一方、第２方式では、計算を打ち切る基準が２と確定されている。
【００９６】
出力部４７は、共通ノード数が基準のノード数以上となる軌跡データのペアの各ＩＤ、及び、共通ノード数をペア共通部分情報３４に格納する。図１８Ｃの例では、ペア共通部分情報３４には、例えば、ＩＤの６とＩＤの３に対応づけて軌跡の共通ノード数の３などが追加されている。
【００９７】
図１８Ｃの例では、第１方式及び第２方式とも、処理ノード数ｘの値「３」が、基準の値となっていない。この場合、取得部４３は、処理ノード数ｘの値を１減算して「２」とし、ノード数が２以上のノード数の軌跡データを取得する。例えば、ノード数が３以上の軌跡データが既に取得されているため、取得部４３は、ノード数が２の軌跡データを読み出す。
【００９８】
図１８Ｄは、処理状況の一例を示す図である。図１８Ｄの例では、候補リストに、ノード数が２のＩＤが４、１３、１５、１９の軌跡が追加されている。
【００９９】
算出部４４は、上記と同様に、共通ノード数を算出済みのペアを除いて、軌跡データのペアごとに、共通ノード数を算出する。図１８Ｄには、共通ノードの計算結果が示されている。
【０１００】
生成部４５は、算出部４４により算出した共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成する。図１８Ｄには、分布情報が示されている。
【０１０１】
決定部４６は、分布情報から、正規化軌跡データ３３に記憶された複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する。
【０１０２】
第１方式では、分布情報から、計算済みの共通ノード数がｋ以上のペア数Ｎｋを求めて、式（６）からｑの値が再度算出し、式（５）から共通部分のノード数ｋの場合の推定値Ｎ~ｋをそれぞれ算出する。図１８Ｄの例では、推定値Ｎ~２が１７．６であり、推定値Ｎ~１が７２．６であり、推定値Ｎ~０が３００．０である。決定部４６は、共通ノード数が２の推定値Ｎ~２が目標数の４０に最も近いため、計算を打ち切る基準を２と決定する。
【０１０３】
一方、第２方式では、計算を打ち切る基準が２と確定されている。
【０１０４】
出力部４７は、共通ノード数が基準のノード数以上となる軌跡データのペアの各ＩＤ、及び、共通ノード数をペア共通部分情報３４に格納する。図１８Ｄの例では、ペア共通部分情報３４には、例えば、ＩＤの６とＩＤの４に対応づけて軌跡の共通ノード数の２などが追加されている。
【０１０５】
図１８Ｄの例では、第１方式及び第２方式とも、処理ノード数ｘの２が、基準となっている。これにより、ノード数が１の軌跡については、読み出しが行われず、共通部分の計算が打ち切れる。
【０１０６】
出力部４７は、図１８Ｄに示したペア共通部分情報３４から、特定のノード数と、計算を打ち切る基準とされた共通ノード数間のノード数の軌跡データのペアを経路分析の結果として分析結果情報３５に出力する。図１８Ｅは、処理状況の一例を示す図である。図１８Ｅでは、共通ノード数が、基準とされたノード数の２以上の軌跡データのペアが示されている。なお、出力部４７は、図１８Ｅの右側に示すように、軌跡ごとに、共通ノード数が基準以上となる軌跡を対応付けて分析結果情報３５に出力してもよい。
【０１０７】
このように、本実施例に係る軌跡データ処理装置１１は、計算済みの分布情報から、全ての軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する。そして、軌跡データ処理装置１１は、推定されたペア数が、指定された目標数に最も近い共通ノード数に、計算を打ち切る基準を動的に変更する。これにより、軌跡データ処理装置１１は、目標数に近いペア数に、軌跡データのペアを適切に絞込むことができる。また、軌跡データ処理装置１１は、特定のノード数からノード数を順に減らして当該ノード数以上のノード数の軌跡データを取得する。そして、軌跡データ処理装置１１は、取得した軌跡データの共通部分を順に算出する。その際、軌跡データ処理装置１１は、ノード数の少ない軌跡データに対して共通部分を算出すると、ペア数が目標値から離れることが推定される場合、計算を打ち切ることができるため、計算量を適切に削減できる。
【０１０８】
次に、本実施例に係る軌跡データ処理装置１１による各種の処理の流れを説明する。最初に、本実施例に係る軌跡データ処理装置１１が軌跡を正規化する正規化処理の流れを説明する。図１９は、正規化処理の流れの一例を示すフローチャートである。この正規化処理は、所定のタイミング、例えば、軌跡記録装置１２から軌跡データがアップロードされたタイミングで実行される。なお、軌跡記録装置１２からアップロードされた軌跡データの格納と、軌跡データの正規化とは、別なタイミングで処理されてもよい。例えば、軌跡データの正規化は、入力部２１から正規化の開始を指示する所定操作が行われたタイミングで実行されてもよい。
【０１０９】
図１９に示すように、格納部４０は、軌跡記録装置１２から軌跡データがアップロードされると、アップロードされた軌跡データに軌跡ＩＤを付与して移動軌跡データ３０に格納する（Ｓ１０）。
【０１１０】
正規化部４１は、移動軌跡データ３０に記憶された軌跡の各位置情報を、ノード情報３１の各ノードの位置情報とマップマッチングを行って、軌跡の位置をノードで示したデータに正規化する（Ｓ１１）。
【０１１１】
正規化部４１は、正規化が完了した軌跡データを移動軌跡データ３０から削除し、処理を終了する（Ｓ１２）。
【０１１２】
次に、本実施例に係る軌跡データ処理装置１１が複数の軌跡データの集合の中から、類似度の高い軌跡データのペアを抽出する軌跡データ処理の流れを説明する。図２０は、軌跡データ処理の流れの一例を示すフローチャートである。この軌跡データ処理は、所定のタイミング、例えば、入力部２１から軌跡データ処理の開始を指示する所定操作が行われたタイミングで実行される。
【０１１３】
図２０に示すように、受付部４２は、操作画面を表示して、経路分析で抽出する軌跡データのペアの目標数として、複数の軌跡データのペア数の指定を受け付ける（Ｓ２０）。
【０１１４】
取得部４３は、記憶部２３の正規化軌跡データ３３に記憶された軌跡データをノード数の多い順にソートする（Ｓ２１）。取得部４３は、正規化軌跡データ３３を参照して、軌跡データの最大のノード数を求め、求めた最大のノード数を処理ノード数ｘに設定する（Ｓ２２）。また、取得部４３は、候補リストを空に初期化する（Ｓ２３）。
【０１１５】
取得部４３は、正規化軌跡データ３３を参照して、ノード数が処理ノード数ｘの軌跡データを読み出し、候補リストに追加する（Ｓ２４）。算出部４４は、候補リストに格納された軌跡データのペアごとに、共通ノード数を算出する（Ｓ２５）。生成部４５は、算出部４４により算出した共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成する（Ｓ２６）。
【０１１６】
決定部４６は、分布情報から、正規化軌跡データ３３に記憶された複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する（Ｓ２７）。決定部４６は、推定されたペア数が、指定された目標数に最も近い共通ノード数を、計算を打ち切る基準の共通ノード数と決定する（Ｓ２８）。
【０１１７】
出力部４７は、共通ノード数が計算を打ち切る基準のノード数以上の軌跡データのペアの各ＩＤ、及び、共通ノード数をペア共通部分情報３４に格納する（Ｓ２９）。
【０１１８】
取得部４３は、処理ノード数ｘが基準の共通ノード数となったか否かを判定する（Ｓ３０）。処理ノード数ｘが基準の共通ノード数となっていない場合（Ｓ３０否定）、取得部４３は、処理ノード数ｘの値から１を減算し（Ｓ３１）、上記のＳ２４へ移行する。
【０１１９】
処理ノード数ｘが基準の共通ノード数となった場合（Ｓ３０肯定）、出力部４７は、次の処理を行う。すなわち、出力部４７は、ペア共通部分情報３４から、計算を打ち切る基準とされた共通ノード数以上のノード数の軌跡データのペアを経路分析の結果として分析結果情報３５に出力し（Ｓ３２）、処理を終了する。
【０１２０】
［効果］
軌跡データ処理装置１１は、複数の軌跡データのペア数の指定を受け付ける。軌跡データ処理装置１１は、記憶部２３の正規化軌跡データ３３を参照して、特定のノード数以上のノード数の軌跡データを取得する。軌跡データ処理装置１１は、取得した軌跡データのペアごとに、各ペアに含まれる軌跡データ間で識別情報が共通である共通ノード数を算出する。軌跡データ処理装置１１は、算出した共通ノード数に基づき、共通ノード数ごとのペア数の分布情報を生成する。軌跡データ処理装置１１は、生成した分布情報と、受け付けたペア数とに基づき、特定のノード数未満である他のノード数を決定する。軌跡データ処理装置１１は、特定のノード数及び他のノード数間のノード数の軌跡データのペアを出力する。これにより、軌跡データ処理装置１１は、計算量を適切に削減できる。また、軌跡データ処理装置１１は、多数の軌跡データの中から、類似度の高い軌跡を計算する際に、分布に基づいて適度な絞り込みができるため、処理時間の長期化を抑制できる。
【０１２１】
また、軌跡データ処理装置１１は、分布情報から、記憶部２３の正規化軌跡データ３３に記憶された複数の軌跡データを推定の対象として、共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する。軌跡データ処理装置１１は、推定されたペア数が、受け付けたペア数に最も近い共通ノード数を他のノード数と決定する。これにより、軌跡データ処理装置１１は、複数の軌跡データでの共通ノード数のペア数の分布について、指数的な分布の形状がどのような場合であっても、計算を打ち切る基準を適切に変更できる。
【０１２２】
また、軌跡データ処理装置１１は、分布情報の共通ノード数ごとのペア数と、正規化軌跡データ３３に記憶された複数の軌跡データを組み合わせたペアの総数から、幾何分布を用いて共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する。軌跡データ処理装置１１は、推定されたペア数が、受け付けたペア数に最も近い共通ノード数を他のノード数と決定する。軌跡データ処理装置１１は、特定のノード数から、決定した他のノード数となるまでノード数を順に減らして当該ノード数以上のノード数の軌跡データの取得を繰り返す。これにより、軌跡データ処理装置１１は、共通ノード数以上となる軌跡データのペア数を精度よく推定できる。
【０１２３】
また、軌跡データ処理装置１１は、最大の共通ノード数から、幾何分布を用いて共通ノード数ごとに、共通ノード数以上となる軌跡データのペア数を推定する。軌跡データ処理装置１１は、推定されたペア数が、受け付けたペア数に最も近い共通ノード数を他のノード数と決定する。軌跡データ処理装置１１は、決定した他のノード数以上のノード数の軌跡データを取得する。これにより、軌跡データ処理装置１１は、読み出す範囲となる他のノード数を速やかに求めることができる。
【実施例２】
【０１２４】
さて、これまで開示の装置に関する実施例について説明したが、開示の技術は上述した実施例以外にも、種々の異なる形態にて実施されてよい。そこで、以下では、本発明に含まれる他の実施例を説明する。
【０１２５】
例えば、上記の実施例では、幾何分布を用いた第１方式、第２方式により軌跡データのペア数を推定する場合を例に説明したが、開示の装置はこれに限定されない。例えば、指数分布を用いて軌跡データのペア数を推定してもよい。指数分布を用いた第３方式を説明する。指数分布は、一般的に以下の式（１０）のように表せる。
【０１２６】
【数５】
0006677040.tif 000006
【０１２７】
この指数分布の式（１０）は、以下の式（１１）から以下の式（１２）、（１３）のように近似できる。
【数６】
0006677040.tif 000007
【０１２８】
式（１２）、（１３）についてｋ＝１,・・・,Ｋで平均を取とると、以下の式（１４）、（１５）のように表せる。
【０１２９】
【数７】
0006677040.tif 000008
【０１３０】
ここで、
Ｋ：計算済みの共通ノード数の最大値
Ｎ：推定対象の軌跡データの組み合わせの総数
Ｎｋ：計算済みの共通ノード数がｋ以上のペア数
Ｎ~ｋ：共通ノード数がｋ以上の組の数の推定値
【０１３１】
計算済みの共通ノード数の最大値Ｋは、ノード数の多い軌跡データから順に共通ノード数の分布を求めることで、定めることができる。推定対象の軌跡データの組み合わせの総数Ｎは、軌跡データの数が定まる。第３方式でも、第１方式と同様に、ノード数の多い軌跡データから順に共通ノード数の分布を求めた際に、計算済みの共通ノード数がｋ以上のペア数Ｎｋを用いて、式（１５）からλの値を求める。そして、第３方式でも、求めたλの値を用いて式（１４）から共通部分のノード数ｋの場合の推定値Ｎ~ｋを求める。
【０１３２】
第３方式は、第１方式と同様に、分布の下限を推定している。また、第３方式は、第１方式と同様に、計算済みの分布で確定部分と未確定部分の値を用いることが精度を向上させている。
【０１３３】
幾何分布と指数分布の主な違いは、幾何分布が離散型の分布に対し、指数分布が連続型の分布である。本実施例の共通部分の長さは、離散型の分布を取るものであるため、幾何分布で近似するのが望ましい。しかし、上述の式（１１）のような近似法を用いることで、同様の計算結果を得ることができる。
【０１３４】
また、上記の実施例では、特定のノード数として、軌跡の最大のノード数を用いる場合を例に説明したが、開示の装置はこれに限定されない。例えば、軌跡データのペアの目標数が４０と指定されている場合に、例えば、６個の軌跡データを組み合わせてもペア数が１５であるため、十分なペア数が得られない。そこで、ノード数の多い順に複数の軌跡データを組み合わせした組み合わせ数が、受け付けた目標値以上となるノード数を特定のノード数として最初に設定してもよい。例えば、６個の軌跡データを組み合わせは、４５となる。このため、軌跡データのペアの目標数が４０と指定されている場合に、特定のノード数に１０を設定してもよい。
【０１３５】
また、上記の実施例では、第２方式においても目標数Ｎ０に最も近い共通ノード数が決定しても、ノード数を順に減らして当該ノード数以上のノード数の軌跡データの取得を繰り返す場合を例に説明したが、開示の装置はこれに限定されない。例えば、第２方式では、目標数Ｎ０に最も近い共通ノード数が決定すると、取得部４３は、目標数Ｎ０に最も近い共通ノード数以上のノード数の軌跡データをまとめて取得してもよい。
【０１３６】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。例えば、格納部４０、正規化部４１、受付部４２、取得部４３、算出部４４、生成部４５、決定部４６及び出力部４７の各処理部が適宜統合されてもよい。さらに、各処理部にて行なわれる各処理機能は、その全部又は任意の一部が、ＣＰＵ及び該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１３７】
［軌跡データ処理プログラム］
また、上記の実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、上記の実施例と同様の機能を有するプログラムを実行するコンピュータシステムの一例を説明する。図２１は、軌跡データ処理プログラムを実行するコンピュータの一例を示す図である。
【０１３８】
図２１に示すように、コンピュータ３００は、ＣＰＵ（Central  Processing  Unit）３１０、ＨＤＤ（Hard  Disk  Drive）３２０、ＲＡＭ（Random  Access  Memory）３４０を有する。これら３００〜３４０の各部は、バス４００を介して接続される。
【０１３９】
ＨＤＤ３２０には上記の格納部４０、正規化部４１、受付部４２、取得部４３、算出部４４、生成部４５、決定部４６及び出力部４７と同様の機能を発揮する軌跡データ処理プログラム３２０Ａが予め記憶される。なお、軌跡データ処理プログラム３２０Ａについては、適宜分離してもよい。
【０１４０】
また、ＨＤＤ３２０は、各種情報を記憶する。例えば、ＨＤＤ３２０は、ＯＳや各種の処理に用いる各種データを記憶する。
【０１４１】
そして、ＣＰＵ３１０が、軌跡データ処理プログラム３２０ＡをＨＤＤ３２０から読み出して実行することで、実施例の各処理部と同様の動作を実行する。すなわち、軌跡データ処理プログラム３２０Ａは、格納部４０、正規化部４１、受付部４２、取得部４３、算出部４４、生成部４５、決定部４６及び出力部４７と同様の動作を実行する。
【０１４２】
なお、上記した軌跡データ処理プログラム３２０Ａは、必ずしも最初からＨＤＤ３２０に記憶させることを要しない。
【０１４３】
また、例えば、軌跡データ処理プログラム３２０Ａは、コンピュータ３００に挿入されるＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラムを記憶させてもよい。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【０１４４】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（又はサーバ）」などにプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【０１４５】
１０  システム
１１  軌跡データ処理装置
１２  軌跡記録装置
２１  入力部
２２  表示部
２３  記憶部
２４  制御部
３０  移動軌跡データ
３１  ノード情報
３２  リンク情報
３３  正規化軌跡データ
３５  分析結果情報
４０  格納部
４１  正規化部
４２  受付部
４３  取得部
４４  算出部
４５  生成部
４６  決定部
４７  出力部
【図１】
0006677040.tif 000009
【図２】
0006677040.tif 000010
【図３】
0006677040.tif 000011
【図４】
0006677040.tif 000012
【図５】
0006677040.tif 000013
【図６】
0006677040.tif 000014
【図７】
0006677040.tif 000015
【図８】
0006677040.tif 000016
【図９】
0006677040.tif 000017
【図１０Ａ】
0006677040.tif 000018
【図１０Ｂ】
0006677040.tif 000019
【図１１Ａ】
0006677040.tif 000020
【図１１Ｂ】
0006677040.tif 000021
【図１１Ｃ】
0006677040.tif 000022
【図１２】
0006677040.tif 000023
【図１３】
0006677040.tif 000024
【図１４】
0006677040.tif 000025
【図１５】
0006677040.tif 000026
【図１６】
0006677040.tif 000027
【図１７】
0006677040.tif 000028
【図１８Ａ】
0006677040.tif 000029
【図１８Ｂ】
0006677040.tif 000030
【図１８Ｃ】
0006677040.tif 000031
【図１８Ｄ】
0006677040.tif 000032
【図１８Ｅ】
0006677040.tif 000033
【図１９】
0006677040.tif 000034
【図２０】
0006677040.tif 000035
【図２１】
0006677040.tif 000036