DEIM Forum 2017 A5-5

不完全な道路ネットワークにおけるマップマッチングとクラスタリング手法を用いた道路セグメントの補間手法の提案
余家豪†佐々木勇和††

石川 佳治†† 名古屋大学大学院情報科学研究科 〒 464–8601 愛知県名古屋市千種区不老町†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1 番 5 号
E-mail: †yu@db.ss.is.nagoya-u.ac.jp, ††sasaki@ist.osaka-u.ac.jp, †††ishikawa@is.nagoya-u.ac.jp
あらまし

近年，GPS を搭載しているデバイスが一般的となっている．GPS での位置測位では，誤差を含んでいることが多く，正確に位置を測定することは難しい．誤差を修正するための技術として，マップマッチングがある．多くのマップマッチングアルゴリズムでは，完全な道路ネットワーク（つまり，全ての道路が欠損していない道路ネットワーク）を前提としている．しかし，不完全な道路ネットワークも世の中には数多く存在している．不完全な道路ネットワークを想定した手法では，移動体が道路ネットワークから離れた場合に道路上以外を移動していると判断し，GPS データをそのまま出力する．このような手法では，GPS の位置を補正はするが，道路ネットワークを補間することは行わない．そこで，本研究では，不完全な道路ネットワークを考慮したマップマッチングを実行しながら，道路ネットワークを補間していくことを目的とする．実際の車両 GPS 軌跡データを用いて，提案手法が道路ネットワークを正しく補間できていることを確認する．
キーワード

不完全な道路ネットワーク, マップマッチング, クラスタリング,DBSCAN, 補間
一方，不完全な道路ネットワークを前提とするマップマッチ

1. は じ め に

ングアルゴリズムも提案されている [4] [6]．不完全な道路ネッ

近年，カーナビゲーションシステムやスマートフォン等，トワークを想定したマップマッチング手法では，移動体が道路GPS を搭載しているデバイスが一般的となっている．GPS でネットワークから離れた場合に道路上以外を移動していると判の位置測位では，誤差を含んでいることが多く，正確に位置を断し，GPS データをそのまま出力する．このような手法では，測定することは難しい．誤差を修正するための技術として，マッGPS の位置を補正はするが，道路ネットワークを補間するこプマッチングがある [2] [3] [5]．マップマッチングは，基本的に車とは行わない．道路ネットワーク上に補正されない GPS 点は，載 GPS を考慮し，自動車は道路上のみを移動するということをoﬀ-road と呼ばれ，この点が不完全な道路ネットワークを考慮前提に GPS の位置情報を道路上に修正するという技術である．

した手法の特徴である．図 3 は，不完全な道路ネットワークを多くのマップマッチングアルゴリズムでは，完全な道路ネット考慮したマッチング結果を示す．図 2 の結果とは異なり，道路ワーク（つまり，全ての道路が欠損していない道路ネットワー上を移動していないと判断された点をそのまま出力されることク）を前提としている．しかし，不完全な道路ネットワークもにより，自然な移動軌跡を出力できていることがわかる．
．

（注 1）

世の中には数多く存在している．例えば，OpenStreetMap

不完全な道路ネットワークを想定したマップマッチングでは，のような手動にて更新される道路図や，発展途上国の道路図な軌跡データを補正することはできるが，道路ネットワークそのどが考えられる．完全な道路ネットワークを前提とするマップものを補間することはできない．そこで，本研究では，不完全マッチングアルゴリズムに対して，不完全な道路ネットワークな道路ネットワークを考慮したマップマッチングを実行しながを入力すると，大きな誤差を含んだ結果となってしまう．図 1

ら，道路ネットワークを補間していくことを目的とする．実際

は，OpenStreetMap より抽出した道路ネットワーク上（黒色の車両 GPS 軌跡データを用いて，提案手法が道路ネットワーの線分）に北京のタクシーの GPS データ（赤色の点）をプロックを正しく補間できていることを確認する．単純に出力されたトしたものである [8] [9]．図の中心部分において，道路上を移

oﬀ-road を道路として補間する場合，三つの問題がある．先ず，動していない GPS データが存在する．地図データでは欠損し一つ目は，実際に道路が無いにも関わらず，GPS の誤差によりているが実際には存在する道路である．図 2 に，完全な道路

oﬀ-road と判定される場合である．この場合，道路を補間するネットワークを前提としたマップマッチングアルゴリズムを適ことは不適切である．oﬀ-road 軌跡で道路かどうかを判定する

応した結果を示す．緑色の点がマップマッチングの結果を示すと，この軌跡の連続な GPS 数が重要である．二つ目は，GPSが道路ネットワークにない道路を通った場合，マップマッチンデータに誤差が含まれるため，そのまま GPS データを補間すグした軌跡が切断されたようなありえない結果が返ってくる．

るだけでは，非現実的な形状で補間してしまうことである．そのため，現実的な形状に変換して補間を行う必要がある．三つ（注 1）：https://www.openstreetmap.org/

目は，複数の oﬀ-road が似たような位置に出力された場合であアルゴリズム [2] では，空間と時間の連続性をもとに枝の重みを決定する．Hidden Markov Model に基づく手法 [3] では，確率密度などをもとに枝に確率的な重みを与える．最後に，両手法とも候補点グラフにおける，経路上の重みが最も大きくなる一本の候補経路を取り出し，それをマッチした軌跡とする．これらの手法では，候補点グラフは，な道路上の点しか考慮して
図 1: 不完全な道路ネットワーク上の GPS軌跡いないため，GPS 点をそのまま出力することはい．
不完全な道路ネットワークを考慮した手法の一つ Pereira らの手法 [4] として, 遺伝的アルゴリズムを用いて，マッチング精度を改善している．しかし，遺伝的アルゴリズムを用いた手法は，NP 困難問題である．Pereira らの手法は最適な結果を得られることを保障できない．Hidden Markov Model に基づく手法を Jan-Henrik らが拡張している [6]．[6] のアイデアは，候補

図 2: 完全な道路ネットワークを前提とする点グラフに，GPS 点をそのまま候補点として追加することでマップマッチングの結果ある．候補点グラフ Gcand においては，枝の重みを計算する上で，三種類の要素: (1) GPS 点と候補点間のユークリッド距離，(2) 道路上の候補点における道路ネットワーク上での最短経路
距離，および (3) 連続する 2 つの候補点が生の GPS 点か道路上に修正した候補点かにより場合分けした値を考える．三つの要素の値を掛け合わせるものを枝の重みとする．候補点グラフ
図 3: 不完全な道路ネットワークを考慮したマップマッチングの結果

Gcand を作成した後は，他の手法と同様に一本の候補経路を取り出し，マッチング結果とする．本稿では，[6] の手法を用いてマップマッチングを実行する．
道路ネットワークデータを用いずに GPS 軌跡データから道る．この場合，同じ道路を表している可能性が高いため，統合路図を作成することを目的とする手法として，論文 [1] で提案して補間する必要がある．

された Mininng Transfer Network がある．Chen らは，GPS提案手法は，まずマップマッチングアルゴリズムを用いて，十軌跡データにより Tranfer Network を得るために，Coherence

分な個数の連続の GPS 点がある oﬀ-road 軌跡を抜き出す．そExpanding アルゴリズムを提案した．軌跡の交差点または端の後，oﬀ-road を簡単化により，現実的な形状に変換する．各点を頂点として連接する．このように，Transfer Network がoﬀ-road 軌跡の位置情報を代表する中心点をデータセットして作成される．しかし，この手法を利用して作成された Tranfer

DBSCAN でクラスタリングする．クラスタ中の軌跡を組合せ

Network は，実際の道路ネットワークに対して誤差が大きくて道路ネットワークのサブグラフを構築し，最後に補間を行う．

なる．

本稿の構成は以下のとおりである，まず，完全な道路ネットワークを前提としたマップマッチング手法と不完全な道路ネッ

3. 準

備

トワークを考慮したマップマッチング手法を 2. で論じる．3. に

本稿では，オフラインのマップマッチングを想定する．つまは，事前準備である．我々の提案手法は 4. で説明し，5. で実験り，GPS データの軌跡は始点から終点まで既に全て揃っておし，実験結果を示す．最後に，6. で本稿のまとめと今後の課題

り，新たな GPS 点が追加されることはない．GPS 点は，誤差について述べる．

を含む緯度・経度の情報，測定された時間情報，および機器の2. 関 連 研 究識別子から成っている．どの程度の誤差を含むかは自明ではないとする．GPS 点の集合を識別子毎に時間軸順に並べること

本章では完全な道路ネットワーク，不完全な道路ネットワーにより，軌跡を求めることが可能である．道路ネットワークは，クにおけるマップマッチングおよび，道路ネットワークの補間節点と枝から構成され，節点は緯度・経度情報を保持している．

手法に関する研究をそれぞれ紹介する．

そのため，GPS 点が道路ネットワーク上の節点もしくは枝か完全な道路ネットワークにおけるマップマッチングでは，Louらどの程度離れているかを計算することが可能である．この道らの ST-Matching アルゴリズム [2] と，Newson らの Hidden

路ネットワークは，不完全な道路ネットワークであり，一部がMarkov Model に基づく手法 [3] がある．両方の手法とも，ま欠損していることを想定する．ただし，完全な道路ネットワー

ず，GPS 点から道路ネットワーク上の複数個の点を候補点としクの場合でも動作し，この場合マップマッチング実行するだけて抽出する．各 GPS 点の候補点を時間軸上に並べ，それらをつとなる．

なぐことにより，候補点グラフ Gcand を構築する．二つのアル3. 1 表

ゴリズムでは，各候補点間の枝の重みが異なる．ST-Matching

本論文では道路ネットワークを有向グラフ G = (V, E) で表記

図 4: 提案手法の概観

す．V は頂点の集合であり，E は辺の集合である．タクシー点 pt1 と終点 ptn を基準として，全ての点の角度, と pt1 と ptn

軌跡を T = {pt1 , · · · , ptn } と書く．グラフ G 上の任意 2 点が成す線分までの距離を求め，角度が θ 以下かつ距離が δ 以下u, v ∈ V 間の最短路距離を distG (u, v) と書き，u から v へ経なら直線と判定する．終点から順に削除していき，直線と判定路が存在しない場合は distG (u, v) = ∞ とする．また，任意のするまで反復して計算する．次に，削除された点に関して，同二点 s, t 間のユークリッド距離は len(s, t) で表す．

様に直線判定を行い，最終的にすべての点をつなげることによ3. 2 マップマッチング

り，折線を作成する．簡単化の具体的な計算方法をアルゴリズ

本稿では，不完全な道路ネットワークを想定したマップマッ

ム 1 に示す．

チング手法 [6] に基づいて，道路ネットワークを補間する．こ4. 2 クラスタリング：DBSCANの手法では，まず，任意の pti ∈ T に対して，マッチングの候DBSCAN は密度をベースとしてクラスタリングの代表的な手補点の集合 Ci = c0i , ..., cKi を用意する．K はユーザが設定す法である．DBSCAN では，パラメータとして最小点数 M inP ts

るパラメータであり，候補点集合の最大サイズを表す．c0i は，と半径 ϵ を与え，ある点を中心とした半径 ϵ 内に M inpts 以上

pti の位置情報を持つ（つまり，GPS と同じ位置情報を持つ）の点があれば，半径内の点を同じクラスタと判断する．提案手

特殊な候補点である．まず，この手法では，2 つの連続な点で法では，簡単化した oﬀ-road を DBSCAN によりクラスタリンある pti−1 と pti に対応する候補点に対して，ユークリッド距離と道路ネットワーク上の最短距離を求める．これらの値はど

Algorithm 1 Simplication

ちらも近い方が候補点間の遷移の確率が高くなる．さらに，こInput: oﬀ-road 軌跡 Tof f = {pt1 , · · · , ptn }(n >= τ)の手法では，候補点が GPS 点がどうかも遷移確率の計算に用

Output: Simplied Sequence Tresult

いる．最終的に pt1 の候補点から ptn の候補点までの遷移にお1: function Simplify(Tof f )いて，確率が最も高い経路をマップマッチングの結果とする．

2:

4. 提 案 手 法
本手法では，[6] の手法をもとに oﬀ-road の GPS 点から道路

3:

Tresult ← Tof f .begin()while Tof f .size >= 2 do4:

Tbackup ← Tof f

5:

while !straight line(Tbackup ) do

ネットワークを補間する．図 4 に提案手法の概要を示す．提案7:

簡単化を行う．これにより，直線もしくは折れ線を取得するこ

8:の oﬀ-road と判定されたものを統合する．その後，道路ネット

4. 1 簡 単 化

end while
Tresult ← Tresult ∪ Tbackup .end(); ▷ 直線判定の条件を満たす点を結果に入れるとができる．次に，簡単化した oﬀ-road を DBSCAN[8] によワークを補間する．

▷ 直線判定関数▷ 直線判定の条件を満たさない点を削除手法では，マップマッチングにて抽出された oﬀ-road に対して，りクラスタリングを実行する．クラスタリングにより同一区域

Tbackup .pop();

6:

9:

Tof f .remove(Tbackup .begin(), Tbackup .end() − 1);oﬀ-road 軌跡を更新

10:

end while

11:

return Tresult

12: end function

簡単化は，[1] で提案されている Mininng Transfer Networkを改良して行う．Mininng Transfer Network では，地図データを用いずに GPS 軌跡データから道路図を作成することを目的としている．一方で，提案手法では，連続的な GPS 点を最低限の点数で折線近似を行う．ユーザは oﬀ-road 軌跡の GPSの最小点数 τ をパラメータとして設定する．τ 未満の oﬀ-roadは補間の対象外とする．簡単化では，まず直線判定を行う．始図 5: サブグラフにマップマッチング▷グを行い，接続している oﬀ-road を抽出する．まず，簡単化さする．一般に，このようなグラフの結合はどのように行うかがれた oﬀ-road の中心点を求め，この中心点を基に DBSCAN を問題となるが，本手法では oﬀ-road の特徴により結合を容易に実施する．中心点は，各点の座標の平均点とする．一番長い中実行できる．??項で述べたとおり，oﬀ-road 軌跡の少なくとも心点から各点までの距離を最小半径 r とする．提案手法では，片方の末端は道路ネットワーク上に存在する．したがって，そパラメータ ϵ を全ての oﬀ-road の最小半径 r のうち，最大のものような末端を道路ネットワークと自然に接続するだけで，道のとする．一方で，M inP ts は，道路の補間の信頼度に大きく路ネットワークとの結合が実現できる．

関わる．この値をユーザが大きく設定すれば，より正確な道路の補間を実現できるが，補間する道路の数は少なる．

以下，具体的な処理の手順を述べる．なお，図 7 は実際に，サブグラフ Gsub を道路ネットワーク G に結合する際の様子を4. 3 セグメントの組合せ示す．まず，サブグラフ中の頂点 v ′ ∈ V ′ に関して，道路ネックラスタリングにより同一区域内の道路と判定された oﬀ-road

トワーク上に存在するものを V に加える．このとき，必ずしも軌跡に対し，セグメントを組み合せることで最終的に補間する

v ′ が道路ネットワーク上の頂点と一致しないことに注意する．

道路を求める．同じ区域に存在する oﬀ-road 軌跡でも，その幾つまり，道路ネットワークの辺 e = (a, b) ∈ E 上に v ′ が配置

何的な情報は異なる可能性がある．例えば，住宅街にあるようされる可能性もある．なお，a, b はそれぞれ辺 e の始点と終点な小道を考える．大通りの道路とは異なり，そうした小道の場を表す．このような場合，一旦辺 e を辺集合 E から削除して，合いくつかの道路へと複雑につながっていることが多い．この挿入した点 v ′ を考慮した辺 (a, v ′ ), (v ′ , b) を追加する必要があような道路上を自動車が通った場合，得られる GPS 軌跡もどる．サブグラフの中で道路ネットワーク上に存在する点を全ての道からどの道へ抜けたかによって異なってくる．したがって，追加し終えたら，次は残りの oﬀ-road 上の点と辺を追加し，道複数の軌跡データを統合し，その区域の道路ネットワークを生路ネットワークの補間を完了する．

成する必要がある．
セグメントの組合せは，各 oﬀ-road 軌跡をグラフとみなし，統合することで実現する．まず，クラスタ内で最も頂点数が多い簡単化された oﬀ-road 軌跡を抽出し，サブグラフ Gsub = (E ′ , V ′ )とする．つまり，oﬀ-road 軌跡中の各点を頂点集合 V ′ ，各点間の図 7: 道路ネットワークに結合遷移を辺集合 E ′ とみなす．次に，クラスタ内の他の oﬀ-road 軌跡を一つずつサブグラフに統合する．具体的には，まず oﬀ-road
軌跡中の任意の点について，ユーザによって定められた半径 σ以内で一番近い頂点 v ∈ V ′ を選択し統合する．もし半径 σ に頂点が存在しない場合は，半径 σ 以内の辺に節点を作成し，その点を新たな頂点として頂点集合 V ′ に加える．つまり，この場合では辺上に新たな頂点が作成されるため，道路ネットワークとしては交差点が生成されることになる．もし半径 σ 以内に頂点も辺も存在しない場合は，その点を新たな頂点 vnew として V ′ に追加する．頂点の追加が終わったら，oﬀ-road 軌跡中の遷移を対応する頂点間の辺として辺集合 E ′ に追加する．以5. 実験

本章では，実データを用いて，提案手法の補間精度と効率性を検証する．補間精度に関しては，直線・折線・複数の折線という三つの場合の道路ネットワークの補間結果を評価する．
なお，不完全な道路ネットワークとしては OpenStreetMap のデータを用い，補間結果の確認には対象領域の Google Mapを用いた．一方で，提案手法の効率性については，パラメータM inP ts を変化させた際の生成されたクラスタの生成数と補間結果の正確性を評価した．

上の処理をクラスタ中の全ての oﬀ-road 軌跡に対して行うこと
で，統合されたサブグラフ Gsub が得られる．

表 1: タクシーデータ

表 2: 道路ネットワーク

図 4.3 で具体例を用いて説明する．まず，クラスタ内の oﬀ-タクシー台数

101

取得日時

road 軌跡のうち最も頂点数が多いものをサブグラフとする．距

最小 GPS 点数

6746

位置

北京市

離が σ 以内の点に関しては統合し，それ以外のものは新たな節

最大 GPS 点数

147739

節点数306311

点とする．これにより，補間する道路ネットワークを作成する

平均 GPS 点数30617

枝数3343152015 年 6 月 27 日

ことできる．

5. 1 実験データ
軌跡データセットとしては，北京市内のタクシーから得られた GPS の軌跡データを用いる [8] [9]．このデータセットには2008 年 2 月 2 日から 8 日まで北京市内を走行した 10,357 台のタクシーのデータが含まれており，タクシーの識別子，緯度経
図 6: サブグラフにマップマッチング

度とタイムスタンプから構成される．しかし，経緯度データやタイムスタンプデータの欠損，連続的なはずの二つの GPS 点

これまでの処理により oﬀ-road 軌跡から欠損道路を表すサブの距離が異常に離れていること，タイムスタンプの前後関係のグラフが生成できたため，これを元の道路ネットワークと結合間違いなど，いくつかの問題も含んでいる．そのため，前処理

図 8: 直線の場合

図 11: 図 8 の対象領域の Google map

図 9: 折線の場合

図 10: 複数の折線の場合

図 12: 図 9 の対象領域の Google map 図 13: 図 10 の対象領域の Google mapとしてこれらの異常となるデータを削除する．また，道路ネッ折線を補間した場所には車のサービスステーションがあり，広トワークの範囲外となるデータや GPS 点の数が少なすぎるタい駐車場があることが確認できる．道路ネットワークの補間とクシーのデータも除去した．表 1 にデータセットの中身を示す．

いう観点では，不正確な補間となる．一方で，提案手法は駐車道路ネットワークとしては，OpenStreetMap から北京市内場の検出および抜け道となっている駐車場を検出することがでのデータを抽出した．表 2 に道路ネットワークのデータを示す．

きることを示している．また，折線の数が狭い範囲で非常に多5. 2 実 験 環 境い場合，道路として補間しないということもできる．

提案手法を C++11 を用いて実装し，gcc 5.4.0 を用いて最適化オプション −O3 の設定でコンパイルした．本実験はUbuntu 16.04.1 LTS(CPU:Intel(R) Core(TM) i7 CPU 870 @2.93GHz, メモリ：8GB) で行った．
5. 3 補間の具体例
本実験では，まず OpenStreetMap の道路ネットワークとタクシーデータに対して，提案手法を用いて道路ネットワークの補間を行う．次に，道路ネットワークの補間の結果が実際の道路として存在するかどうかについて，Google Map を用いて検(a) 乱雑な折線補間の結果(b) 対象領域の Google map

証する．ここでは，直線・折線・複数の折線という三種類の道路

図 14: 乱雑な折線補間の結果と Google map の比較ネットワークの補間結果を示す．なお，クラスタリング手法で用いたパラメータ τ と M inP ts はそれぞれ 5 と 2 に設定した．
また，直線判定関数の中で用いるパラメータは θ = 15，δ = 20に設定した実験結果を図 8-9 に示す．図 8 では，直線の道路の補間，図5. 4 補間の精度評価
提案手法の補間の精度は，検出するクラスタの精度に大きく依存する．そのため，DBSCAN のパラメータである M inP tsを変化させて精度を評価する．補間の精度を評価するために，

9 では，曲がり角を含む道路の補間，図 9 では，複雑な形状の補間した道路ネットワークから少数をサンプリングし，Google道路の補間をそれぞれ表している．それぞれの道路図に対応すmap と比較することで正しい補間かどうかを検証する．表 3 にる Google Map の道路を図 11-13 に示す．それぞれの図を比M inP ts を変化させた場合の生成されるクラスタ数と補間さ較すると，OpenStreetMap 上には存在しない道路を適切に補れる道路のセグメントの種類の割合を示す（注 2）．まず M inP ts間できていることがわかる．以上の実験結果から，提案手法はが 1 の場合，oﬀ-road 軌跡が一つでもあればクラスタとして検様々な形状の道路ネットワークに対する補間の有効性が高いこ出されるため，生成されるクラスタ数が多い．また，ひとつのとが検証できた．

oﬀ-road 軌跡から補間される道路は，直線となることが多いた

一方，補間がうまくいかなかった場合も存在する．図 14 は，め，M inP ts が大きい場合と比較して，直線のセグメントが多乱雑な折線を補間した例となる．図 14a は補間結果，図 14b は対象領域の Google map を示す．図 14b が示すように，乱雑な（注 2）：生成されるクラスタ数と補間される道路は同数となる．

く検出される．M inP ts が大きくなるにつれて，検出されるク大きくなることが予想される．そこで，効率的に手法をマップラスタ数が減少する．特に，M inP ts が 3 以上になると，検出マッチングおよび道路ネットワークの補間を実行する手法を考されるクラスタ数は少なくなり，直線や折線はほぼ検出されず，提案する予定である．

複数の折線からなるセグメントの割合が大多数を占めることがわかる．M inP ts の値は，データセットのサイズに依存して決める必要があり，今回のデータセットでは，M inP ts は，1 も謝辞

本研究の一部は，科研費（16H01722, 15K21069）および文部科学省「実社会ビッグデータ利活用のためのデータ統合・解

しくは 2 と設定するのが妥当である．
次に，それぞれの M inP ts にて生成されるクラスタに対し析技術の研究開発」による.て，10%のサンプリングを実施し，Google map と比較することで補間の精度を検証した．表 4 にそれぞれの M inP ts におけるサンプリングしたセグメントの種類とその正解数，および全体での正解率を示す．ここで，正解とは，目視によってその道路が存在するかを確認し，図 14 のような道路以外のセグメントを補間した場合，不正解とした．まず，この表より，提案手法は高い正解率を達成していることがわかる．特に，直線の正解率が高い．これは，直線が一つの道路セグメントから形成されるため，正解となりやすいためである．M inP ts が 3 以上になると，多くの場合サービスステーションやガソリンスタンドのような道路以外の補間となるため，複雑な折線の補間が多くなる．そのため，精度が徐々に低下している．
表 3: 各 M inP ts に対するセグメントの種類の割合
MinPts 生成されるクラスタ数

直線

折線

複数の折線

16025734619922071716174386477546420625532051

表 4: 各 M inP ts に対する補間の精度
サンプ

MinPts リング

直線/折線/

正解数

正解数

複数の折線/

正解率

1の数
60

19/1724/18

正解数
17/1176.6%

2202/1

3/3

15/8

60.0%

382/00/0

6/4

50.0%

460/0

0/0

6/3

50.0%

550/0

0/0

5/2

40.0%

6. ま と め
本稿では，不完全な道路ネットワークを用いたマップマッチ
ングと道路ネットワークの補間手法を提案した．不完全な道路ネットワークにマップマッチング手法 [6] を利用して，oﬀ-road
軌跡を抜き出し，抜き出したデータを簡単化するし，簡単化された直線または折線の中心点をクラスタリングする．クラスタ
された中心点が二つ以上の場合，セグメントを組み合わせて,サブグラフにする．最後，合成されたサブグラフを道路ネットワークに補間する．今後，まず提案手法を実データを用いて評価する．さらに，大規模なデータを用いた場合，実行時間が文

献[1] Z. Chen, H. T. Shen, and X. Zhou, “Discovering Popular Routes from Trajectories”, In Proc. ICDE, pp. 900-911,2011.
[2] Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y.
Huang, “Map-Matching for Low-Sampling-Rate GPS Trajectories”, In Proc. ACM SIGSPATIAL GIS, pp. 352–361,
2009.
[3] P. Newson and J. Krumm, “Hidden Markov Map MatchingThrough Noise and Sparseness”， In Proc. ACM SIGSPATIAL GIS, pp. 336–343, 2009.
[4] F.C. Pereira, H. Costa, and N.M. Pereira, “An Oﬀ-line MapMatching Algorithm for Incomplete Map Databases”， In .
European Transport Research Review, 1(3):107–124, 2009.
[5] J.Eisner, S.Funke, A.Herbst, A.Spilner, and S.Storandt, “Algorithm for Matching and Predicting Trajectories”, In
ALENEX , pp. 84–95, 2011.
[6] J.-H Haunert and B. Budig, “An Algorithm for Map Matching Given Incomplete Road Data”, In Proc. ACM SIGSPATIAL GIS, pp. 510–513, 2012.
[7] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A Densitybased Algorithm for Discovering Clusters in Large Spatial
Databases with Noise”, In Proc. SIGKDD, pp. 226–231,1996.
[8] Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun,
“Driving with knowledge from the physical world”, In Proc.
SIGKDD ,pp. 316–324, 2011.
[9] Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, XingXie, Guangzhong Sun, and Yan Huang, “T-drive: driving directions based on taxi trajectories”, In Proc. ACM
SIGSPATIAL GIS, pp. 99–108, 2010.