(57)【特許請求の範囲】
【請求項１】
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力方法。
【請求項２】
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、位置が対応するノード数が多い配置から順に、対応するノード同士で識別情報が共通するノード組の数を算出し、前記位置が対応するノード数が、既に算出されたノード組の数の最大値以下となった段階で、前記ノード組の数の算出を終了し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力方法。
【請求項３】
前記数に応じた出力を行うことは、前記配置毎に算出されたノード組の数が最大となる場合の該ノード組を、前記第１の軌跡情報と前記第２の軌跡情報との共通部分として出力することを含む請求項１又は請求項２記載の共通情報出力方法。
【請求項４】
前記数に応じた出力を行うことは、前記配置毎に算出されたノード組の数の最大値を、前記第１の軌跡情報と前記第２の軌跡情報との共通部分の長さとして出力することを含む請求項１〜請求項３のいずれか１項記載の共通情報出力方法。
【請求項５】
前記コンピュータに、前記共通部分の長さと予め定めた閾値とに基づいて、前記第１の軌跡情報と前記第２の軌跡情報との類否判定を行うことをさらに含む処理を実行させる請求項４記載の共通情報出力方法。
【請求項６】
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得する取得部と、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出する算出部と、
算出した前記数に応じた出力を行う出力部と、
を含む共通情報出力装置。
【請求項７】
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得する取得部と、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、位置が対応するノード数が多い配置から順に、対応するノード同士で識別情報が共通するノード組の数を算出し、前記位置が対応するノード数が、既に算出されたノード組の数の最大値以下となった段階で、前記ノード組の数の算出を終了する算出部と、
算出した前記数に応じた出力を行う出力部と、
を含む共通情報出力装置。
【請求項８】
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力プログラム。
【請求項９】
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、位置が対応するノード数が多い配置から順に、対応するノード同士で識別情報が共通するノード組の数を算出し、前記位置が対応するノード数が、既に算出されたノード組の数の最大値以下となった段階で、前記ノード組の数の算出を終了し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力プログラム。
【請求項１０】
コンピュータに、
位置情報の系列で表される複数の移動軌跡情報を統合して、位置情報に対応付けられた複数のノードと、該ノード間を連結する複数のリンクとを含む経路グラフを生成し、
前記複数の移動軌跡情報の各々を、前記経路グラフに対応させることにより、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む複数の軌跡情報の各々に変換し、
前記複数の軌跡情報に含まれるいずれかの軌跡情報を第１の軌跡情報とし、他のいずれかの軌跡情報を第２の軌跡情報として取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる経路グラフ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通情報出力方法、共通情報出力装置、及び共通情報出力プログラム、並びに経路グラフ生成方法に関する。
【背景技術】
【０００２】
空間情報分析として、移動体の経路に関する分析を行う技術が存在する。例えば、実際の観測データである複数の軌跡データが示す軌跡の各々から、指定された地点を出発地点または到着地点とする経路を検索するＯＤ（Ｏ＝“Origin”：出発地点、Ｄ＝“Destination”：到着地点）検索を行う技術が存在する。また、複数の軌跡から、所定回数（例えば、１０回）以上出現する出発地点と到着地点との組み合わせ（例えば、（新宿駅−渋谷駅）、（品川駅−池袋駅）等）を示す頻出ＯＤを分析する技術が存在する。また、軌跡の中から、例えば、品川駅→（山手線外回り）→池袋駅を通過する経路のように、部分経路を検索する技術が存在する。さらに、軌跡の中に、所定回数（例えば、１０回）以上出現する部分経路を示す頻出部分経路を分析する技術が存在する。
【０００３】
上記のような経路分析を行うにあたって、移動体が同じ経路を通っていることを把握するために、複数の軌跡間の共通部分や類似度を求めることが行われる。例えば、２人のユーザの各々の移動履歴が示す軌跡を、意味的な軌跡（semantic trajectory）に変換し、２つの意味的な軌跡の最長共通部分列（ＬＣＳ：Longest Common Subsequence）を計算する技術が提案されている。この技術では、計算したＬＣＳを用いて、ユーザ同士の類似度を算出している。
【０００４】
また、ＬＣＳを計算する技術として、動的計画を用いたアルゴリズムが知られている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】J. J. Ying, E. H. -C. Lu, W. -C. Lee, T. -C. Weng and V. S. Tseng, "Mining user similarity from semantic trajectories", Proc. LBSN '10, pp. 19-26, 2010.
【非特許文献２】D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences", Comm. of ACM, 18(6), 341-343, 1975.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、軌跡データ間の共通部分を正確に特定するためには、多くの計算量を要し、特に、大規模な軌跡データを対象とする場合には、軌跡データの組み合わせが爆発し、さらに計算量が増大する。例えば、従来のアルゴリズムを用いて、約１万件の軌跡データについて、各軌跡データ間の共通部分を特定するためには、約１日程度かかることが見込まれる。
【０００７】
本発明は、一つの側面として、軌跡データ間の共通部分の特定に要する計算量を抑制することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、一つの側面として、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報を取得する。また、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報を取得する。そして、前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列とする。また、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とする。第１のノード列と第２のノード列を並列させた配置のうち、第１の配置から第２の配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出する。第１の配置は、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置である。第２の配置は、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置である。そして、算出した前記数に応じた出力を行う。
【発明の効果】
【０００９】
一つの側面として、軌跡データ間の共通部分の特定に要する計算量を抑制することができる、という効果を有する。
【図面の簡単な説明】
【００１０】
【図１】第１及び第２実施形態に係る共通情報出力装置の概略構成を示す機能ブロック図である。
【図２】移動軌跡の一例を示す図である。
【図３】移動軌跡データベース（ＤＢ）の一例を示す図である。
【図４】道路ネットワークの一例を示す図である。
【図５】道路ネットワークＤＢの一例を示す図である。
【図６】移動軌跡データの正規化を説明するための図である。
【図７】正規化軌跡ＤＢの一例を示す図である。
【図８】ネットワークグラフにおけるパスの共通部分を説明するための図である。
【図９】パスのノード列において特定された共通部分の一例を示す図である。
【図１０】道路ネットワークにおける移動軌跡の共通部分を説明するための図である。
【図１１】パスのノード列において特定された共通部分の一例を示す図である。
【図１２】正規化軌跡のノード列において特定された共通部分の一例を示す図である。
【図１３】出力情報ＤＢの一例を示す図である。
【図１４】第１〜第３実施形態に係る共通情報出力装置として機能するコンピュータの概略構成を示すブロック図である。
【図１５】共通情報出力処理の一例を示すフローチャートである。
【図１６】第１実施形態における共通部分情報算出処理の一例を示すフローチャートである。
【図１７】第１実施形態における共通部分の特定を説明するための図である。
【図１８】第２実施形態における共通部分情報算出処理の一例を示すフローチャートである。
【図１９】第２実施形態における共通部分の特定を説明するための図である。
【図２０】第３実施形態に係る経路グラフ生成システムの概略構成を示す機能ブロック図である。
【図２１】経路グラフの生成を説明するための図である。
【図２２】経路グラフＤＢの一例を示す図である。
【図２３】経路グラフ生成処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施形態の一例を詳細に説明する。
【００１２】
＜第１実施形態＞
図１に示すように、第１実施形態に係る共通情報出力装置１０は、機能的には、取得部１１と、正規化部１２と、算出部１３と、判定部１４とを含む。また、共通情報出力装置１０の所定の記憶領域には、移動軌跡データベース（ＤＢ）２１と、道路ネットワークＤＢ２２と、正規化軌跡ＤＢ２３と、出力情報ＤＢ２４とが記憶される。なお、これらのデータベースは、共通情報出力装置１０と接続された外部の記憶装置に記憶されてもよい。
【００１３】
移動軌跡ＤＢ２１には、例えば、図２に示すような移動軌跡を示す移動軌跡データが記憶される。移動軌跡は、定期的に観測された移動体の位置を示す観測データに基づいて、観測点毎の位置情報を時系列に連結して表される。図２の例では、観測点を四角マークで表しており、四角内の数字ｉｊは、移動軌跡の識別情報（移動軌跡ＩＤ）がｉの移動軌跡のｊ番目の観測点であることを表している。なお、以下では、移動軌跡ＩＤ＝ｉの移動軌跡を「移動軌跡ｉ」とも表記する。移動軌跡ＤＢ２１には、例えば、図３に示すように、移動軌跡ＩＤと、その移動軌跡ＩＤが示す移動軌跡に含まれる各観測点の番号（観測点Ｎｏ．）と、各観測点のｘ座標及びｙ座標とが対応付けて記憶される。なお、ｘ座標及びｙ座標は、例えば緯度及び経度である。
【００１４】
道路ネットワークＤＢ２２には、道路ネットワークを示すデータが記憶される。道路ネットワークは、例えば、図４に示すように、それぞれが位置情報に対応付けられた複数のノード（図４中の丸印）と、ノード間を結ぶリンクで表される。道路ネットワークＤＢ２２には、例えば、図５に示すように、各ノードの識別情報（ノードＩＤ）と、各ノードのｘ座標及びｙ座標とが対応付けて記憶され、さらに、リンク情報が記憶される。図５の例では、リンク情報は、リンクの一端のノードのノードＩＤである「ノードＩＤ１」と、他端のノードのノードＩＤである「ノードＩＤ２」とを対応付けたものである。なお、以下では、ノードＩＤがＸのノードを「ノードＸ」とも表記する。
【００１５】
取得部１１は、移動軌跡ＤＢ２１から、移動軌跡データの各々を取得する。なお、移動軌跡ＤＢ２１において、移動軌跡ＩＤが同一の一群のデータが、１つの移動軌跡データに相当する。また、取得部１１は、道路ネットワークＤＢ２２から、対象範囲の道路ネットワークを示すデータを取得する。対象範囲か否かは、道路ネットワークＤＢ２２の「ｘ座標」及び「ｙ座標」から判断する。取得部１１は、取得した移動軌跡データと、道路ネットワークを示すデータとを、正規化部１２へ受け渡す。
【００１６】
正規化部１２は、図６に示すように、移動軌跡データの各々が示す移動軌跡の各々を、マップマッチング等により、道路ネットワークに含まれるいずれかの経路（パス）に対応付け、移動軌跡が通るノードを抽出する。正規化部１２は、抽出したノードのノードＩＤを羅列したノード列を、正規化軌跡として取得する。すなわち、正規化部１２は、移動軌跡データの各々を正規化することにより、正規化軌跡の各々に変換する。例えば、図６の例では、移動軌跡１は、Ａ→Ｂ→Ｃ→Ｇ→Ｈ→Ｄの経路を通る。また、移動軌跡２は、Ａ→Ｂ→Ｆ→Ｇ→Ｃの経路を通る。したがって、正規化部１２は、移動軌跡１を示す移動軌跡データを＜Ａ，Ｂ，Ｃ，Ｇ，Ｈ，Ｄ＞という正規化軌跡に変換し、移動軌跡２を示す移動軌跡データを＜Ａ，Ｂ，Ｆ，Ｇ，Ｃ＞という正規化軌跡に変換する。正規化部１２は、変換した正規化軌跡の各々に正規化軌跡ＩＤを付与し、例えば図７に示すような正規化軌跡ＤＢ２３に記憶する。
【００１７】
算出部１３は、正規化軌跡ＤＢ２３から、共通部分を特定する対象となる１組の正規化軌跡を取得する。１組の正規化軌跡には、２つの正規化軌跡が含まれる。そして、算出部１３は、１組の正規化軌跡における共通性に関する情報を算出する。本実施形態では、共通性に関する情報として、２つの正規化軌跡間の共通部分を特定した情報、及び共通部分の長さ（以下、「共通部分長」という）を算出する。
【００１８】
ここで、本実施形態における正規化軌跡間の共通部分について説明する。
【００１９】
例えば、図８に示すようなノードＡ〜Ｈを含むネットワークグラフ内のパス１（Ａ→Ｂ→Ｆ→Ｇ→Ｃ→Ｄ→Ｈ）と、パス２（Ａ→Ｅ→Ｆ→Ｇ→Ｈ）との共通部分を例に説明する。パス間の共通部分とは、図８中の点線の楕円で示す部分のように、両パスが共通して通るノードである。共通部分が不連続に複数存在する場合、各共通部分をパスでの出現順に羅列したものが共通部分となる。図９に、各パスが通るノードのノードＩＤを羅列したノード列で、両パスの共通部分（図９中の点線部分）を特定した例を示す。共通部分を特定する際には、図９に示すように、不連続に存在する共通部分間のノードは異なっていてもよいし（図９中の矢印Ｐの箇所）、共通部分間のノード数が異なっていてもよい（図９中の矢印Ｑの箇所）。この場合、パス１とパス２との共通部分は、＜Ａ，Ｆ，Ｇ，Ｈ＞であり、共通部分に含まれるノードの数で表される共通部分長は、４である。
【００２０】
図８及び図９では、両パスの始点及び終点が共通している例を示しているが、実際には、両パスの始点及び終点が共通しているとは限らない。そのため、パスの共通部分を見つけるためには、上記のような共通部分間でのノード数の異なりも考慮して、空白文字を挿入するなどして、両パス間でのノードの対応付けを様々に組み替えながら、共通部分長が最も長くなる共通部分を探索しなければならない。このため、共通部分の特定に要する計算量が多くなってしまう。
【００２１】
本実施形態では、移動体の移動軌跡を正規化した正規化軌跡が、図８のパスに相当する。図８に示すように、一般的なネットワークグラフにおけるパスを考えた場合、あるノードから他のノードまでは様々なパスが想定される。一方、図１０に、ノードＡに相当する位置からノードＨに相当する位置までの移動軌跡１０１及び移動軌跡１０２の各々を、道路ネットワークに対応付けた例を示す。なお、図１０中の点線の楕円で示す部分は、移動軌跡１と移動軌跡２との共通部分である。この例に示すように、移動体は、例えば遠回りとなるような不自然な経路を選択する場合は少ないと考えられる。そのため、移動軌跡が分かれてから再び一緒になるまでの間（不連続に存在する共通部分間）において、各移動軌跡が通るノードの数は同じになる傾向が強い。
【００２２】
そこで、本実施形態では、このような移動軌跡の特徴を利用して、正規化軌跡間の共通部分を近似的に算出することで、共通部分の特定に要する計算量の抑制を図る。
【００２３】
具体的には、算出部１３は、１組の正規化軌跡に含まれる一方の正規化軌跡を上に、他方の正規化軌跡を下にして、各列にノードＩＤが１ずつ対応するように並列に配置する。以下では、一方の正規化軌跡と他方の正規化軌跡とで重複する部分において、位置が対応するノードＩＤ同士、すなわち同一列に存在する一方の正規化軌跡のノードＩＤと他方の正規化軌跡のノードＩＤとの組を「ノード組」という。そして、算出部１３は、一方の正規化軌跡と他方の正規化軌跡とで重複するノード数、すなわちノード組の数が各々異なる配置毎に、ノードＩＤが共通するノード組の数を算出する。
【００２４】
より具体的には、両正規化軌跡の並列配置のうち、一方の正規化軌跡の左端（先頭）のノードＩＤと、他方の正規化軌跡の右端（末尾）のノードＩＤとが対応する配置を初期の配置とする。また、一方の正規化軌跡の右端のノードＩＤと、他方の正規化軌跡の左端のノードＩＤとが対応する配置を最終の配置とする。算出部１３は、初期の配置から最終の配置まで、他方の正規化軌跡を右側に１列ずつずらした配置毎に、ノードＩＤが共通するノード組の数を算出する。算出部１３は、配置毎に算出したノードＩＤが共通するノード組の数が最大となる場合のノード組の各々が示すノードＩＤを羅列したノード列を、両正規化軌跡の共通部分として特定する。
【００２５】
図８及び図９で説明した一般的なネットワークグラフのパスの場合、不連続に存在する共通部分間のノード数は不定である。そのため、上記のように各パスのノード列を単純に１列ずつずらしながら近似的に共通部分を特定する場合には、精度良く共通部分を特定することができない場合がある。図１１に、図８及び図９の例のパス１とパス２との共通部分を近似的に特定した例を示す。図１１に示すように、この例では、パス１とパス２とでは、ノードＧとノードＨとの間のノード数が異なるため、本来は共通部分であるノードＨが共通部分として特定されない。
【００２６】
一方、本実施形態のように、正規化軌跡間の共通部分を特定する場合、上述したように、不連続に存在する共通部分間のノード数が同じである傾向が強い。そのため、各正規化軌跡のノード列を単純に１列ずつずらしながら近似的に共通部分を特定する場合でも、図１２に示すように、精度良く共通部分を特定することができる。
【００２７】
また、算出部１３は、特定した共通部分に含まれるノードＩＤの数を、共通部分長として算出する。共通部分長の算出は、下記（１）式で表すことができる。なお、ｔｉは、一方の正規化軌跡のｉ番目のノードＩＤ、ｓｉは、他方の正規化軌跡のｉ番目のノードＩＤ、｜ｔ｜は、一方の正規化軌跡の長さ（ノードＩＤの個数）、｜ｓ｜は、他方の正規化軌跡の長さである。また、｛ｉ：ｔｉ＝ｓｉ＋ｋ｝は、ｔｉ＝ｓｉ＋ｋとなるノード組の数である。
【００２８】
【数１】
0006555049.tif 000002
【００２９】
算出部１３は、算出した共通部分長を判定部１４に通知すると共に、特定した共通部分、及び算出した共通部分長を、例えば、図１３に示すような出力情報ＤＢ２４に記憶する。図１３の出力情報ＤＢ２４では、１組の正規化軌跡に含まれる一方の正規化軌跡の正規化軌跡ＩＤである「正規化軌跡ＩＤ１」、及び他方の正規化軌跡の正規化軌跡ＩＤである「正規化軌跡ＩＤ２」に、共通部分及び共通部分長が対応付けて記憶されている。なお、「類否」の項目については後述する。
【００３０】
判定部１４は、算出部１３から通知された共通部分長と、予め定めた閾値とを比較し、共通部分長が閾値以上の場合には、１組の正規化軌跡に含まれる両正規化軌跡は類似すると判定する。また、判定部１４は、共通部分長が閾値未満の場合には、両正規化軌跡は非類似であると判定する。判定部１４は、判定結果を、出力情報ＤＢ２４の「類否」の項目に記憶する。
【００３１】
共通情報出力装置１０は、例えば図１４に示すコンピュータ４０で実現することができる。コンピュータ４０はＣＰＵ４１、一時記憶領域としてのメモリ４２、及び不揮発性の記憶部４３を備える。また、コンピュータ４０は、入出力装置４４と、記録媒体４９に対するデータの読み込み及び書き込みを制御するｒｅａｄ／ｗｒｉｔｅ（Ｒ／Ｗ）部４５と、インターネット等のネットワークに接続されるネットワークＩ／Ｆ４６とを備える。ＣＰＵ４１、メモリ４２、記憶部４３、入出力装置４４、Ｒ／Ｗ部４５、及びネットワークＩ／Ｆ４６は、バス４７を介して互いに接続される。
【００３２】
記憶部４３は、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（solid state drive）、フラッシュメモリ等によって実現できる。記憶媒体としての記憶部４３には、コンピュータ４０を共通情報出力装置１０として機能させるための共通情報出力プログラム５０が記憶される。
【００３３】
ＣＰＵ４１は、共通情報出力プログラム５０を記憶部４３から読み出してメモリ４２に展開し、共通情報出力プログラム５０が有するプロセスを順次実行する。共通情報出力プログラム５０は、取得プロセス５１と、正規化プロセス５２と、算出プロセス５３と、判定プロセス５４とを有する。
【００３４】
ＣＰＵ４１は、取得プロセス５１を実行することで、図１に示す取得部１１として動作する。また、ＣＰＵ４１は、正規化プロセス５２を実行することで、図１に示す正規化部１２として動作する。また、ＣＰＵ４１は、算出プロセス５３を実行することで、図１に示す算出部１３として動作する。また、ＣＰＵ４１は、判定プロセス５４を実行することで、図１に示す判定部１４として動作する。これにより、共通情報出力プログラム５０を実行したコンピュータ４０が、共通情報出力装置１０として機能することになる。
【００３５】
なお、共通情報出力プログラム５０により実現される機能は、例えば半導体集積回路、より詳しくはＡＳＩＣ（Application Specific Integrated Circuit）等で実現することも可能である。
【００３６】
次に、第１実施形態に係る共通情報出力装置１０の作用について説明する。複数の移動軌跡データが記憶された移動軌跡ＤＢ２１、及び道路ネットワークを示す道路ネットワークＤＢ２２が用意されている状態で、共通情報出力装置１０において、図１５に示す共通情報出力処理が実行される。ここでは、図３に示す移動軌跡ＤＢ２１、及び図５に示す道路ネットワークＤＢ２２が用意されているものとする。
【００３７】
図１５に示す共通情報出力処理のステップＳ２０で、取得部１１が、移動軌跡ＤＢ２１から、移動軌跡データの各々を取得し、道路ネットワークＤＢ２２から、対象範囲の道路ネットワークを示すデータを取得し、これらを正規化部１２へ受け渡す。
【００３８】
次に、ステップＳ３０で、正規化部１２が、移動軌跡データが示す移動軌跡を道路ネットワークに対応付けることにより正規化して、移動軌跡データの各々を正規化軌跡の各々に変換する。そして、正規化部１２は、変換した正規化軌跡の各々に正規化軌跡ＩＤを付与し、例えば図７に示すような正規化軌跡ＤＢ２３に記憶する。
【００３９】
次に、ステップＳ４０で、図１６に詳細を示す共通部分情報算出処理が実行される。
【００４０】
図１６に示す共通部分情報算出処理のステップＳ４１で、算出部１３が、共通部分長の算出に用いる変数ｍａｘを０に設定し、共通部分を示すノード列を格納する配列ＣＳを空に設定する。
【００４１】
次に、ステップＳ４２で、算出部１３が、正規化軌跡ＤＢ２３から１組の正規化軌跡を取得し、１組の正規化軌跡に含まれる一方の正規化軌跡を上に、他方の正規化軌跡を下にして、初期の配置となるように並列に配置する。ここでは、算出部１３は、２つの正規化軌跡のうち、長い方（ノードＩＤ数が多い方）の正規化軌跡１を上に、短い方（ノードＩＤ数が少ない方）の正規化軌跡２を下に配置する。また、算出部１３は、図１７の最上段及びループ１の段に示すように、正規化軌跡１の左端のノードＩＤ「Ａ」と、正規化軌跡２の右端のノードＩＤ「Ｃ」とが同じ列となるように対応させて、正規化軌跡１と正規化軌跡２とを並列配置する。
【００４２】
次に、ステップＳ４３で、算出部１３が、正規化軌跡１と正規化軌跡２とで、ノードＩＤが共通するノード組の数を算出する。ここでは、図１７の最上段及びループ１の段に示すように、１つのノード組が存在するが、そのノード組の２つのノードＩＤは共通しないため、算出部１３は、ノードＩＤが共通するノード組の数を「０」と算出する。
【００４３】
次に、ステップＳ４４で、算出部１３が、上記ステップＳ４３で算出したノードＩＤが共通するノード組の数がｍａｘより大きい場合には、ｍａｘの値を、算出したノードＩＤが共通するノード組の数で更新する。また、算出部１３は、ｍａｘを更新した場合には、ノードＩＤが共通するノード組の各々が示すノードＩＤを羅列したノード列で、配列ＣＳを更新する。ここでは、算出したノードＩＤが共通するノード組の数＝０、及びｍａｘ＝０であるため、ｍａｘ及びＣＳの更新は行われない。
【００４４】
次に、ステップＳ５０で、算出部１３が、図１７のループ２の段に示すように、下に配置した正規化軌跡２を右側に１列ずらす。
【００４５】
次に、ステップＳ５１で、算出部１３が、正規化軌跡間に重複部分、すなわちノード組が存在するか否かを判定する。重複部分が存在する場合には、処理はステップＳ４３に戻り、重複部分が存在しない場合には、処理はステップＳ５２へ移行する。ここでは、重複部分が存在するため、処理はステップＳ４３に戻り、ステップＳ４３、Ｓ４４、及びＳ５０の処理を繰り返す。図１７のループ２の段に示す配置でも、正規化軌跡１と正規化軌跡２との間には、ノードＩＤが共通するノード組が存在しないため、ｍａｘ及びＣＳは更新されない。そして、ステップＳ５０で、算出部１３が、正規化軌跡２の配置をさらに右側に１列ずらし、図１７のループ３の段に示す配置とし、再び処理はステップＳ４３に戻る。
【００４６】
図１７の最上段及びループ３の段に示す正規化軌跡１と正規化軌跡２との配置では、ノードＩＤが共通するノード組が１組存在する（図１７中の点線太枠部分）。したがって、ステップＳ４３で、算出部１３が、ノードＩＤが共通するノード組の数を「１」と算出する。この値は、現在のｍａｘ（＝０）より大きいため、次のステップＳ４４で、算出部１３が、ｍａｘ＝１に更新する。また、算出部１３が、ノードＩＤが共通するノード組が示すノードＩＤ「Ｃ」を配列ＣＳに格納し、ＣＳ＝＜Ｃ＞とする。
【００４７】
次に、正規化軌跡２を、図１７のループ４の段に示す配置とした場合には、正規化軌跡１と正規化軌跡２との間には、ノードＩＤが共通するノード組が存在しないため、ｍａｘ及びＣＳは更新されない。
【００４８】
次に、正規化軌跡２を、図１７のループ５の段に示す配置とした場合には、ノードＩＤが共通するノード組が３組存在する（図１７中の実線太枠部分）。したがって、ステップＳ４３で、算出部１３が、ノードＩＤが共通するノード組の数を「３」と算出する。この値は、現在のｍａｘ（＝１）より大きいため、次のステップＳ４４で、算出部１３が、ｍａｘ＝３に更新する。また、算出部１３が、ノードＩＤが共通するノード組の各々が示すノードＩＤ「Ａ」、「Ｂ」、及び「Ｇ」を羅列したノード列で配列ＣＳを更新し、ＣＳ＝＜Ａ，Ｂ，Ｇ＞とする。
【００４９】
以下、正規化軌跡２を、図１７のループ６〜１０の段に示す配置の各々とした場合には、正規化軌跡１と正規化軌跡２との間には、ノードＩＤが共通するノード組が存在しないため、ｍａｘ及びＣＳは更新されない。ステップＳ５０で、図１７のループ１０の段に示す配置から、正規化軌跡２を右に１列ずらすと、正規化軌跡１と正規化軌跡２との間には重複部分が存在しなくなるため、次のステップＳ５１で否定判定されて、処理はステップＳ５２へ移行する。
【００５０】
ステップＳ５２では、算出部１３が、現在ｍａｘに格納されている値を共通部分長とし、配列ＣＳに格納されているノード列を共通部分として、１組の正規化軌跡に含まれる正規化軌跡の正規化軌跡ＩＤに対応付けて、出力情報ＤＢ２４に記憶する。また、算出部１３は、算出した共通部分長を判定部１４に通知する。そして、共通部分情報算出処理は終了し、処理は図１５に示す共通情報出力処理に戻る。
【００５１】
次に、図１５に示す共通情報出力処理のステップＳ６０で、判定部１４が、算出部１３から通知された共通部分長が、予め定めた閾値（例えば、３）以上か否かを判定する。共通部分長が閾値以上の場合には、処理はステップＳ７０へ移行し、判定部１４が、１組の正規化軌跡に含まれる両正規化軌跡は類似するとの判定結果を、出力情報ＤＢ２４の「類否」の項目に記憶する。一方、共通部分長が閾値未満の場合には、処理はステップＳ７５へ移行し、判定部１４が、１組の正規化軌跡に含まれる両正規化軌跡は非類似であるとの判定結果を、出力情報ＤＢ２４の「類否」の項目に記憶する。そして、共通情報出力処理は終了する。
【００５２】
以上説明したように、第１実施形態に係る共通情報出力装置によれば、移動軌跡間の共通部分間のノード数は同一である傾向が強いという特徴を利用して、正規化した移動軌跡間の共通部分を近似的に特定する。具体的には、２つの正規化した移動軌跡を並列配置し、重複するノード数が各々異なる配置毎に算出した、ノードＩＤが共通するノード組の数の最大値を、共通部分長として算出する。これにより、不連続に存在する共通部分間でのノード数の異なりも考慮して、両移動軌跡間でのノードの対応付けを様々に組み替えながら共通部分を探索する場合に比べ、移動軌跡間の共通部分の特定に要する計算量を抑制することができる。
【００５３】
このように、移動軌跡間の共通部分の特定に要する計算量を抑制することができることにより、移動軌跡の分析時間の短縮にもつながり、大規模なデータを対象とする分析も可能になる。
【００５４】
また、一方の移動軌跡の左端と他方の移動軌跡の右端とを対応させた初期の配置から、他方の移動軌跡を１列ずつずらしながら、ノードＩＤが共通するノード組の数を算出する。これにより、重複するノード数が各々異なる各配置を簡易な処理で網羅することができる。
【００５５】
なお、第１実施形態では、一方の移動軌跡の左端と他方の移動軌跡の右端とを対応させた配置を初期の配置とし、他方の移動軌跡を一方の移動軌跡に対して相対的に右側へずらしながら配置を変更する場合について説明したが、これに限定されない。一方の移動軌跡の右端と他方の移動軌跡の左端とを対応させた配置を初期の配置とし、他方の移動軌跡を一方の移動軌跡に対して相対的に左側へずらしながら配置を変更してもよい。
【００５６】
＜第２実施形態＞
次に、第２実施形態について説明する。第２実施形態に係る共通情報出力装置において、第１実施形態に係る共通情報出力装置１０と同様の部分については、同一符号を付して、詳細な説明を省略する。
【００５７】
図１に示すように、第２実施形態に係る共通情報出力装置２１０は、機能的には、取得部１１と、正規化部１２と、算出部２１３と、判定部１４とを含む。また、共通情報出力装置２１０の所定の記憶領域には、移動軌跡ＤＢ２１と、道路ネットワークＤＢ２２と、正規化軌跡ＤＢ２３と、出力情報ＤＢ２４とが記憶される。
【００５８】
算出部２１３は、第１実施形態における算出部１３と同様に、１組の正規化軌跡の共通性に関する情報を算出する。以下では、第１実施形態における算出部１３と異なる点について説明する。第２実施形態における算出部２１３は、配置毎に、ノードＩＤが共通するノード組の数を算出する際に、重複するノード数が多い配置から順に算出する。
【００５９】
具体的には、両正規化軌跡の並列配置のうち、一方の正規化軌跡の左端（先頭）のノードＩＤと、他方の正規化軌跡の左端（先頭）のノードＩＤとが対応する配置を初期の配置とする。現在の配置が、他方の正規化軌跡が一方の正規化軌跡の左側にはみ出している配置であるとする。この場合、算出部２１３は、はみ出しているノード数と同じ数のノードが一方の正規化軌跡の右側にはみ出すように、他方の正規化軌跡の配置をずらして、次にノードＩＤが共通するノード組の数の算出する配置とする。また、現在の配置が、他方の正規化軌跡が一方の正規化軌跡の右側にはみ出している配置であるとする。この場合、算出部２１３は、はみ出しているノード数より１つ多い数のノードが一方の正規化軌跡の左側にはみ出すように、他方の正規化軌跡の配置をずらして、次にノードＩＤが共通するノード組の数の算出する配置とする。
【００６０】
これにより、重複するノード数が各々異なる各配置を、重複するノード数が多い配置から順に網羅することができる。そして、算出部２１３は、重複するノード数が、既に算出されたノードＩＤが共通するノード組の数の最大値以下となった段階で、ノードＩＤが共通するノード組の数の算出を終了する。
【００６１】
共通情報出力装置２１０は、例えば図１４に示すコンピュータ４０で実現することができる。コンピュータ４０の記憶部４３には、コンピュータ４０を共通情報出力装置２１０として機能させるための共通情報出力プログラム２５０が記憶される。
【００６２】
ＣＰＵ４１は、共通情報出力プログラム２５０を記憶部４３から読み出してメモリ４２に展開し、共通情報出力プログラム２５０が有するプロセスを順次実行する。共通情報出力プログラム２５０は、取得プロセス５１と、正規化プロセス５２と、算出プロセス２５３と、判定プロセス５４とを有する。
【００６３】
ＣＰＵ４１は、算出プロセス２５３を実行することで、図１に示す算出部２１３として動作する。他のプロセスについては、第１実施形態における共通情報出力プログラム５０と同様である。これにより、共通情報出力プログラム２５０を実行したコンピュータ４０が、共通情報出力装置２１０として機能することになる。
【００６４】
なお、共通情報出力プログラム２５０により実現される機能は、例えば半導体集積回路、より詳しくはＡＳＩＣ等で実現することも可能である。
【００６５】
次に、第２実施形態に係る共通情報出力装置２１０の作用について説明する。第２実施形態においても、第１実施形態と同様に、図１５に示す共通情報出力処理が実行される。ただし、第２実施形態における共通情報出力処理では、ステップＳ４０で実行される共通部分情報算出処理が、第１実施形態とは異なる。以下では、図１８を参照して、第２実施形態における共通部分情報算出処理について説明する。なお、第１実施形態における共通部分情報算出処理（図１６）と同様の処理については、同一符号を付して詳細な説明を省略する。なお、第２実施形態においても、第１実施形態と同様に、図３に示す移動軌跡ＤＢ２１、及び図５に示す道路ネットワークＤＢ２２が用意されているものとする。また、図１５に示す共通情報出力処理のステップＳ３０で、図７に示すような正規化軌跡が得られているものとする。
【００６６】
図１８に示す共通部分情報算出処理のステップＳ４１で、算出部２１３が、ｍａｘを「０」に設定し、配列ＣＳを空に設定する。次に、ステップＳ２４２で、算出部２１３が、正規化軌跡ＤＢ２３から１組の正規化軌跡を取得し、１組の正規化軌跡に含まれる一方の正規化軌跡を上に、他方の正規化軌跡を下にして、初期の配置となるように並列に配置する。ここでは、算出部２１３は、２つの正規化軌跡のうち、長い方（ノードＩＤ数が多い方）の正規化軌跡１を上に、短い方（ノードＩＤ数が少ない方）の正規化軌跡２を下に配置する。また、算出部２１３は、図１９の最上段及びループ１の段に示すように、正規化軌跡１の左端のノードＩＤ「Ａ」と、正規化軌跡２の左端のノードＩＤ「Ａ」とが同じ列となるように対応させて、正規化軌跡１と正規化軌跡２とを並列配置する。
【００６７】
次に、ステップＳ４３で、算出部２１３が、正規化軌跡１と正規化軌跡２とで、ノードＩＤが共通するノード組の数を算出する。ここでは、図１９の最上段及びループ１の段に示すように、ノードＩＤが共通するノード組が３組存在する（図１９中の点線太枠部分）。したがって、ステップＳ４３で、算出部２１３が、ノードＩＤが共通するノード組の数を「３」と算出する。この値は、現在のｍａｘ（＝０）より大きいため、次のステップＳ４４で、算出部２１３が、ｍａｘ＝３に更新する。また、算出部２１３が、ノードＩＤが共通するノード組の各々が示すノードＩＤ「Ａ」、「Ｂ」、及び「Ｇ」を羅列したノード列で配列ＣＳを更新し、ＣＳ＝＜Ａ，Ｂ，Ｇ＞とする。
【００６８】
次に、ステップＳ４５で、算出部２１３が、１組の正規化軌跡の現在の配置において、他方の正規化軌跡の左端が、一方の正規化軌跡の左端と対応しているか、又は右にあるか否かを判定する。すなわち、算出部２１３は、他方の正規化軌跡が、一方の正規化軌跡に対して、相対的に左側にはみ出しているか否かを判定する。他方の正規化軌跡が左側にはみ出していない場合には、処理はステップＳ４６へ移行し、はみ出している場合には、処理はステップＳ４８へ移行する。ここでは、図１９の最上段及びループ１の段に示すように、正規化軌跡２は、正規化軌跡１の左側にはみ出していないため、処理はステップＳ４６へ移行する。
【００６９】
ステップＳ４６では、算出部２１３が、１組の正規化軌跡の現在の配置において、他方の正規化軌跡の右端が、一方の正規化軌跡の右端より左にあるか否かを判定する。すなわち、算出部２１３は、他方の正規化軌跡の右端と他方の正規化軌跡の右端とが一致しているか否か、又は、他方の正規化軌跡が、一方の正規化軌跡に対して、相対的に右側にはみ出しているか否かを判定する。他方の正規化軌跡の右端が一方の正規化軌跡の右端より左にある場合には、処理はステップＳ５０へ移行し、両正規化軌跡の右端が一致又は他方の正規化軌跡が右側にはみ出している場合には、処理はステップＳ４７へ移行する。ここでは、図１９の最上段及びループ１の段に示すように、正規化軌跡２の右端は、正規化軌跡１の右端より左にあるため、処理はステップＳ５０へ移行する。
【００７０】
ステップＳ５０では、算出部２１３が、図１９のループ２の段に示すように、下に配置した正規化軌跡２を右側に１列ずらす。
【００７１】
次に、ステップＳ２５１で、算出部２１３が、正規化軌跡間の重複部分の長さ、すなわちノード組の数が、現在のｍａｘの値以下か否かを判定する。重複部分の長さ≦ｍａｘの場合には、処理はステップＳ５２へ移行し、重複部分の長さ＞ｍａｘの場合には、処理はステップＳ４３に戻る。ここでは、図１９の最上段及びループ２の段に示すように、正規化軌跡１と正規化軌跡２との重複部分の長さは「５」であり、現在のｍａｘ（＝３）より大きいため、処理はステップＳ４３に戻り、ステップＳ４３〜Ｓ５０の処理を繰り返す。
【００７２】
図１９のループ２の段に示す配置では、正規化軌跡１と正規化軌跡２との間には、ノードＩＤが共通するノード組が存在しないため、ｍａｘ及びＣＳは更新されない。そして、図１９のループ２の段に示す配置では、正規化軌跡２は正規化軌跡１の左側にはみ出していないが、正規化軌跡２の右端と正規化軌跡１の右端が対応しているため、ステップＳ４６で否定判定され、処理はステップＳ４７へ移行する。
【００７３】
ステップＳ４７では、算出部２１３が、一方の正規化軌跡に対して右側にはみ出た他方の正規化軌跡のノードＩＤの数より１つ多く、他方の正規化軌跡が一方の正規化軌跡に対して左側にはみ出すように、他方の正規化軌跡をずらす。ここでは、図１９のループ２の段に示す配置では、正規化軌跡１に対して右側にはみ出た正規化軌跡２のノードＩＤの数は０であるので、正規化軌跡２が正規化軌跡１の左側に、ノードＩＤ１つ分はみ出すように正規化軌跡２をずらす。したがって、正規化軌跡２が、図１９のループ３の段に示す配置となる。この配置の重複部分の長さは「４」であり、現在のｍａｘ（＝３）より大きいため、処理はステップＳ４３に戻る。
【００７４】
図１９のループ３の段に示す配置では、正規化軌跡１と正規化軌跡２との間には、ノードＩＤが共通するノード組が存在しないため、ｍａｘ及びＣＳは更新されない。そして、図１９のループ３の段に示す配置では、正規化軌跡２が正規化軌跡１の左側にはみ出しているため、ステップＳ４５で否定判定され、処理はステップＳ４８へ移行する。
【００７５】
ステップＳ４８では、算出部２１３が、一方の正規化軌跡に対して左側にはみ出た他方の正規化軌跡のノードＩＤの数だけ、他方の正規化軌跡が一方の正規化軌跡に対して右側にはみ出すように、他方の正規化軌跡をずらす。ここでは、図１９のループ３の段に示す配置では、正規化軌跡１に対して左側にはみ出た正規化軌跡２のノードＩＤの数は１であるので、正規化軌跡２が正規化軌跡１の右側に、ノードＩＤ１つ分はみ出すように正規化軌跡２をずらす。したがって、正規化軌跡２が、図１９のループ４の段に示す配置となる。この配置の重複部分の長さは「４」であり、現在のｍａｘ（＝３）より大きいため、処理はステップＳ４３に戻る。
【００７６】
図１９のループ４の段に示す配置では、正規化軌跡１と正規化軌跡２との間には、ノードＩＤが共通するノード組が存在しないため、ｍａｘ及びＣＳは更新されない。そして、図１９のループ４の段に示す配置では、正規化軌跡２が正規化軌跡１の右側にはみ出しているため、処理はステップＳ４５及びステップＳ４６を経て、ステップＳ４７へ移行する。そして、ステップＳ４７で、算出部２１３が、図１９の「重複部分：３」の上段に示す配置に、正規化軌跡２をずらす。この配置の重複部分の長さは「３」であり、現在のｍａｘ以下となる。正規化軌跡間でノードＩＤが共通するノード組の数が、正規化軌跡間の重複部分の長さを超えることはないため、これ以上処理を繰り返してもｍａｘが更新されることはない。したがって、ここで、正規化軌跡間でノードＩＤが共通するノード組の数の算出、並びにｍａｘ及びＣＳの更新の処理を終了し、処理はステップＳ５２へ移行する。
【００７７】
ステップＳ５２では、算出部２１３が、共通部分長及び共通部分の情報を、出力情報ＤＢ２４に記憶する。そして、共通部分情報算出処理は終了し、処理は図１５に示す共通情報出力処理に戻る。
【００７８】
以上説明したように、第２実施形態に係る共通情報出力装置によれば、２つの正規化した移動軌跡を並列配置し、重複するノード数が各々異なる配置毎に、ノードＩＤが共通するノード組の数の最大値を、共通部分長として算出する。この際、重複するノード数が多い配置から順に算出し、重複するノード数が、既に算出されたノードＩＤが共通するノード組の数の最大値以下となった段階で、処理を終了する。これにより、移動軌跡間の共通部分の特定に要する計算量をさらに抑制することができる。
【００７９】
なお、第２実施形態では、一方の移動軌跡の左端と他方の移動軌跡の左端とを対応させた配置を初期の配置とする場合について説明したが、これに限定されない。一方の移動軌跡の右端と他方の移動軌跡の右端とを対応させた配置を初期の配置としてもよい。この場合、他方の正規化軌跡の右端が一方の正規化軌跡の右端より左側にあり、かつ他方の正規化軌跡の左端が一方の正規化軌跡の左端より右側にある場合、他方の移動軌跡を右側に１列分ずらす。また、他方の正規化軌跡が一方の正規化軌跡の右側にはみ出している場合、はみ出している分だけ、他方の正規化軌跡が一方の正規化軌跡の左側にはみ出すように他方の正規化軌跡をずらす。また、他方の正規化軌跡が一方の正規化軌跡の左側にはみ出している場合、はみ出している分より１つ多く、他方の正規化軌跡が一方の正規化軌跡の右側にはみ出すように他方の正規化軌跡をずらす。
【００８０】
＜第３実施形態＞
次に、第３実施形態について説明する。第３実施形態では、共通情報出力装置を含む経路グラフ生成システムについて説明する。なお、第３実施形態において、第１実施形態に係る共通情報出力装置１０と同様の部分については、同一符号を付して、詳細な説明を省略する。
【００８１】
図２０に示すように、第３実施形態に係る経路グラフ生成システム３０は、移動軌跡生成装置３２と、記憶装置２０と、共通情報出力装置３１０とを含む。記憶装置２０には、移動軌跡ＤＢ２１と、経路グラフＤＢ３２２と、正規化軌跡ＤＢ２３と、出力情報ＤＢ２４とが記憶される。
【００８２】
移動軌跡生成装置３２は、移動体の位置を観測するセンサ３６の各々で定期的に観測された移動体の位置を示す観測データを、ネットワーク３８を介して取得する。センサ３６は、移動体の一例である人が保持する携帯電話、スマートフォン等の端末や、移動体の一例である車両に搭載されたカーナビゲーションシステム等で利用されるＧＰＳ等とすることができる。観測データには、観測点毎の緯度及び経度で示される位置データと観測時刻、並びにセンサ３６を識別するセンサＩＤが含まれる。移動軌跡生成装置３２は、取得した複数の観測データを、センサＩＤ毎に抽出し、各観測データに含まれる位置データを、観測時刻に基づいて時系列に並べて移動軌跡データを生成する。移動軌跡生成装置３２は、生成した複数の移動軌跡データを、移動軌跡ＤＢ２１に記憶する。
【００８３】
共通情報出力装置３１０は、機能的には、取得部３１１と、生成部１５と、正規化部１２と、算出部１３と、判定部１４とを含む。
【００８４】
取得部３１１は、移動軌跡ＤＢ２１から取得した移動軌跡データを生成部１５に受け渡す。また、取得部３１１は、第１実施形態における取得部１１と同様に、移動軌跡ＤＢ２１から取得した移動軌跡データ、及び後述する経路グラフＤＢ３２２から取得した経路グラフを示すデータを、正規化部１２へ受け渡す。
【００８５】
生成部１５は、取得部３１１から受け渡された移動軌跡データから経路グラフを生成する。経路グラフは、第１実施形態の道路ネットワークと同様に、それぞれが位置情報に対応付けられた複数のノードと、ノード間を結ぶリンクで表される。例えば、生成部１５は、図２１の上図に示すように、複数の移動軌跡の距離が近い部分（例えば、図２１上図中の破線の楕円部分）を統合することにより、図２１の下図に示すような経路グラフを生成する。経路グラフの生成方法は、例えば、特開２０１５−０７６０６９号公報等に記載の方法を用いることができるため、ここでは詳細な説明を省略する。なお、経路グラフの生成方法は、上記の方法に限定されない。
【００８６】
生成部１５は、生成した経路グラフを示すデータを、例えば、図２２に示すような経路グラフＤＢ３２２として、記憶装置２０に記憶する。経路グラフＤＢ３２２のデータ形式は、第１実施形態における道路ネットワークＤＢ２２と同様である。
【００８７】
経路グラフ生成システム３０に含まれる共通情報出力装置３１０は、例えば図１４に示すコンピュータ４０で実現することができる。コンピュータ４０の記憶部４３には、コンピュータ４０を共通情報出力装置３１０として機能させるための共通情報出力プログラム３５０が記憶される。
【００８８】
ＣＰＵ４１は、共通情報出力プログラム３５０を記憶部４３から読み出してメモリ４２に展開し、共通情報出力プログラム３５０が有するプロセスを順次実行する。共通情報出力プログラム３５０は、取得プロセス３５１と、正規化プロセス５２と、算出プロセス５３と、判定プロセス５４と、生成プロセス５５とを有する。
【００８９】
ＣＰＵ４１は、取得プロセス３５１を実行することで、図２０に示す取得部３１１として動作する。また、ＣＰＵ４１は、生成プロセス５５を実行することで、図２０に示す生成部１５として動作する。他のプロセスについては、第１実施形態における共通情報出力プログラム５０と同様である。これにより、共通情報出力プログラム３５０を実行したコンピュータ４０が、共通情報出力装置３１０として機能することになる。
【００９０】
なお、共通情報出力プログラム３５０により実現される機能は、例えば半導体集積回路、より詳しくはＡＳＩＣ等で実現することも可能である。
【００９１】
次に、第３実施形態に係る経路グラフ生成システム３０の作用について説明する。移動軌跡生成装置３２が、複数のセンサ３６の各々で観測された観測データを、ネットワーク３８を介して取得し、観測データから移動軌跡データを生成して、移動軌跡ＤＢ２１に記憶する。そして、共通情報出力装置３１０が、図２３に示す経路グラフ生成処理を実行する。なお、経路グラフ生成処理において、第１実施形態における共通情報出力処理と同様の処理については、同一符号を付して詳細な説明を省略する。
【００９２】
図２３に示す経路グラフ生成処理のステップＳ１０で、取得部３１１が、移動軌跡ＤＢ２１から移動軌跡データを取得し、生成部１５へ受け渡す。生成部１５は、取得部３１１から受け渡された移動軌跡データを統合するなどして経路グラフを生成し、経路グラフＤＢ３２２に記憶する。
【００９３】
以降の処理では、道路ネットワークに変えて、上記ステップＳ１０で生成された経路グラフが用いられる点が、第１実施形態における共通情報出力処理と異なるだけであるため、説明を省略する。
【００９４】
以上説明したように、第３実施形態によれば、移動軌跡を用いて経路グラフを生成すると共に、経路グラフの生成に用いた移動軌跡を経路グラフに対応付けて正規化した移動軌跡間の共通部分の情報を出力する。これにより、経路グラフと共に、経路グラフの生成に用いた移動軌跡間の共通部分の情報も得ることができる。共通部分は、第１実施形態と同様に、移動軌跡の特徴を利用して近似的に算出されるため、移動軌跡間の共通部分の特定に要する計算量を抑制することができる。
【００９５】
なお、第３実施形態では、第１実施形態の共通部分情報算出処理を適用する場合について説明したが、第２実施形態の共通部分情報算出処理を適用してもよい。
【００９６】
また、第１〜第３実施形態では、共通性に関する情報として、特定した共通部分の情報、共通部分長、及び移動軌跡間の類否判定結果を出力する場合について説明したが、これら全てを出力する場合に限定されない。いずれか１つ又は２つを出力するようにしてもよい。また、これら以外の共通性に関する情報を出力するようにしてもよい。
【００９７】
第１〜第３実施形態の各々で得られる移動軌跡間の共通性に関する情報を利用して、様々なサービスを提供することが可能である。例えば、類似すると判定された移動軌跡同士に対応するユーザ同士に、お互いが知り合いである可能性があることを示す情報や、友達になることを提案する情報を提供することができる。また、例えば、共通部分長が長い移動軌跡同士に対応するユーザに、タクシーの相乗りを提案する情報を提供することができる。
【００９８】
なお、上記実施形態では、共通情報出力プログラム５０、２５０、３５０が記憶部４３に予め記憶（インストール）されている態様を説明したが、これに限定されない。本発明に係る共通情報出力プログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ等の記録媒体に記録された形態で提供することも可能である。
【００９９】
以上の各実施形態に関し、更に以下の付記を開示する。
【０１００】
（付記１）
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力方法。
【０１０１】
（付記２）
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、位置が対応するノード数が多い配置から順に、対応するノード同士で識別情報が共通するノード組の数を算出し、前記位置が対応するノード数が、既に算出されたノード組の数の最大値以下となった段階で、前記ノード組の数の算出を終了し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力方法。
【０１０２】
（付記３）
前記数に応じた出力を行うことは、前記配置毎に算出されたノード組の数が最大となる場合の該ノード組を、前記第１の軌跡情報と前記第２の軌跡情報との共通部分として出力することを含む付記１又は付記２記載の共通情報出力方法。
【０１０３】
（付記４）
前記数に応じた出力を行うことは、前記配置毎に算出されたノード組の数の最大値を、前記第１の軌跡情報と前記第２の軌跡情報との共通部分の長さとして出力することを含む付記１〜付記３のいずれか１項記載の共通情報出力方法。
【０１０４】
（付記５）
前記コンピュータに、前記共通部分の長さと予め定めた閾値とに基づいて、前記第１の軌跡情報と前記第２の軌跡情報との類否判定を行うことをさらに含む処理を実行させる付記４記載の共通情報出力方法。
【０１０５】
（付記６）
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得する取得部と、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出する算出部と、
算出した前記数に応じた出力を行う出力部と、
を含む共通情報出力装置。
【０１０６】
（付記７）
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得する取得部と、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、位置が対応するノード数が多い配置から順に、対応するノード同士で識別情報が共通するノード組の数を算出し、前記位置が対応するノード数が、既に算出されたノード組の数の最大値以下となった段階で、前記ノード組の数の算出を終了する算出部と、
算出した前記数に応じた出力を行う出力部と、
を含む共通情報出力装置。
【０１０７】
（付記８）
前記出力部は、前記配置毎に算出されたノード組の数が最大となる場合の該ノード組を、前記第１の軌跡情報と前記第２の軌跡情報との共通部分として出力する付記６又は付記７記載の共通情報出力装置。
【０１０８】
（付記９）
前記出力部は、前記配置毎に算出されたノード組の数の最大値を、前記第１の軌跡情報と前記第２の軌跡情報との共通部分の長さとして出力する付記６〜付記８のいずれか１項記載の共通情報出力装置。
【０１０９】
（付記１０）
前記共通部分の長さと予め定めた閾値とに基づいて、前記第１の軌跡情報と前記第２の軌跡情報との類否を判定する判定部をさらに含む付記９記載の共通情報出力装置。
【０１１０】
（付記１１）
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力プログラム。
【０１１１】
（付記１２）
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、位置が対応するノード数が多い配置から順に、対応するノード同士で識別情報が共通するノード組の数を算出し、前記位置が対応するノード数が、既に算出されたノード組の数の最大値以下となった段階で、前記ノード組の数の算出を終了し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力プログラム。
【０１１２】
（付記１３）
前記数に応じた出力を行うことは、前記配置毎に算出されたノード組の数が最大となる場合の該ノード組を、前記第１の軌跡情報と前記第２の軌跡情報との共通部分として出力することを含む付記１１又は付記１２記載の共通情報出力プログラム。
【０１１３】
（付記１４）
前記数に応じた出力を行うことは、前記配置毎に算出されたノード組の数の最大値を、前記第１の軌跡情報と前記第２の軌跡情報との共通部分の長さとして出力することを含む付記１１〜付記１３のいずれか１項記載の共通情報出力プログラム。
【０１１４】
（付記１５）
前記コンピュータに、前記共通部分の長さと予め定めた閾値とに基づいて、前記第１の軌跡情報と前記第２の軌跡情報との類否判定を行うことをさらに含む処理を実行させる付記１４記載の共通情報出力プログラム。
【０１１５】
（付記１６）
コンピュータに、
位置情報の系列で表される複数の移動軌跡情報を統合して、位置情報に対応付けられた複数のノードと、該ノード間を連結する複数のリンクとを含む経路グラフを生成し、
前記複数の移動軌跡情報の各々を、前記経路グラフに対応させることにより、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む複数の軌跡情報の各々に変換し、
前記複数の軌跡情報に含まれるいずれかの軌跡情報を第１の軌跡情報とし、他のいずれかの軌跡情報を第２の軌跡情報として取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる経路グラフ生成方法。
【０１１６】
（付記１７）
位置情報の系列で表される複数の移動軌跡情報を統合して、位置情報に対応付けられた複数のノードと、該ノード間を連結する複数のリンクとを含む経路グラフを生成する生成部と、
前記複数の移動軌跡情報の各々を、前記経路グラフに対応させることにより、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む複数の軌跡情報の各々に変換する変換部と、
前記複数の軌跡情報に含まれるいずれかの軌跡情報を第１の軌跡情報とし、他のいずれかの軌跡情報を第２の軌跡情報として取得する取得部と、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出する算出部と、
算出した前記数に応じた出力を行う出力部と、
を含む経路グラフ生成装置。
【０１１７】
（付記１８）
コンピュータに、
位置情報の系列で表される複数の移動軌跡情報を統合して、位置情報に対応付けられた複数のノードと、該ノード間を連結する複数のリンクとを含む経路グラフを生成し、
前記複数の移動軌跡情報の各々を、前記経路グラフに対応させることにより、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む複数の軌跡情報の各々に変換し、
前記複数の軌跡情報に含まれるいずれかの軌跡情報を第１の軌跡情報とし、他のいずれかの軌跡情報を第２の軌跡情報として取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる経路グラフ生成プログラム。
【０１１８】
（付記１９）
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力プログラムを記憶した記憶媒体。
【０１１９】
（付記２０）
コンピュータに、
それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第１の軌跡情報と、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む第２の軌跡情報とを取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、位置が対応するノード数が多い配置から順に、対応するノード同士で識別情報が共通するノード組の数を算出し、前記位置が対応するノード数が、既に算出されたノード組の数の最大値以下となった段階で、前記ノード組の数の算出を終了し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる共通情報出力力プログラムを記憶した記憶媒体。
【０１２０】
（付記２１）
コンピュータに、
位置情報の系列で表される複数の移動軌跡情報を統合して、位置情報に対応付けられた複数のノードと、該ノード間を連結する複数のリンクとを含む経路グラフを生成し、
前記複数の移動軌跡情報の各々を、前記経路グラフに対応させることにより、それぞれが位置情報に対応付けられた複数のノードの各々の識別情報と、前記複数のノードの順序情報と、を含む複数の軌跡情報の各々に変換し、
前記複数の軌跡情報に含まれるいずれかの軌跡情報を第１の軌跡情報とし、他のいずれかの軌跡情報を第２の軌跡情報として取得し、
前記第１の軌跡情報に含まれる前記複数のノードを前記第１の軌跡情報に含まれる前記順序情報に基づいて並べた第１のノード列と、前記第２の軌跡情報に含まれる前記複数のノードを前記第２の軌跡情報に含まれる前記順序情報に基づいて並べられた第２のノード列とを並列させた配置のうち、前記第１の軌跡情報の先頭のノードの識別情報と、前記第２の軌跡情報の末尾のノードの識別情報とが対応する配置から、前記第１の軌跡情報の末尾のノードの識別情報と、前記第２の軌跡情報の先頭のノードの識別情報とが対応する配置まで、対応するノードを１つずつずらした配置毎に、対応するノード同士で識別情報が共通するノード組の数を算出し、
算出した前記数に応じた出力を行う、
ことを含む処理を実行させる経路グラフ生成プログラムを記憶した記憶媒体。
【符号の説明】
【０１２１】
１０、２１０、３１０ 共通情報出力装置
１１、３１１  取得部
１２   正規化部
１３、２１３  算出部
１４   判定部
１５   生成部
２０   記憶装置
２１   移動軌跡データベース（ＤＢ）
２２   道路ネットワークＤＢ
２３   正規化軌跡ＤＢ
２４   出力情報ＤＢ
３２２ 経路グラフＤＢ
３０   経路グラフ生成システム
３２   移動軌跡生成装置
４０   コンピュータ
４１   ＣＰＵ
４２   メモリ
４３   記憶部
５０、２５０、３５０ 共通情報出力プログラム
【図１】
0006555049.tif 000003
【図２】
0006555049.tif 000004
【図３】
0006555049.tif 000005
【図４】
0006555049.tif 000006
【図５】
0006555049.tif 000007
【図６】
0006555049.tif 000008
【図７】
0006555049.tif 000009
【図８】
0006555049.tif 000010
【図９】
0006555049.tif 000011
【図１０】
0006555049.tif 000012
【図１１】
0006555049.tif 000013
【図１２】
0006555049.tif 000014
【図１３】
0006555049.tif 000015
【図１４】
0006555049.tif 000016
【図１５】
0006555049.tif 000017
【図１６】
0006555049.tif 000018
【図１７】
0006555049.tif 000019
【図１８】
0006555049.tif 000020
【図１９】
0006555049.tif 000021
【図２０】
0006555049.tif 000022
【図２１】
0006555049.tif 000023
【図２２】
0006555049.tif 000024
【図２３】
0006555049.tif 000025