道路ネットワーク上の軌跡データに対する圧縮索引

小出 智士  肖 川  石川 佳治  
(データ工学研究専門委員会推薦論文)

誌名
電子情報通信学会論文誌 D   Vol.J103-D   No.5   pp.393-402
発行日: 2020/05/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2019DET0001
論文種別: 特集論文 (データ工学と情報マネジメント論文特集)
専門分野: 軌跡データ圧縮
キーワード: 
軌跡データ,  圧縮索引,  道路ネットワーク,  パターンマッチング,  

本文: PDF(1MB)>>
論文を購入




あらまし: 
道路ネットワーク G=(V,E) 上を走行する軌跡データに対する圧縮索引を提案する.軌跡データがエッジ集合 E をアルファベット集合とする文字列とみなせることに着目すると,圧縮文字列索引(FM-index)の技術が適用可能である.ところが,大都市のような大きな道路ネットワークを扱う場合,そのエッジの数 |E| は数万から数十万と非常に大きい.巨大なアルファベット集合上ではFM-indexの効率が低下することが知られており,軌跡データにFM-indexを適用する際にはこの点が問題になる.一方,道路ネットワークは交差点等の物理的な構造を反映するため,各頂点の次数が小さい,という疎グラフの性質をもつ.本研究ではこの性質に着目し,効率の低下を抑えるような圧縮データ構造を提案する.提案手法では検索速度が E のサイズに依存せず,G の最大流出次数のみに依存することが理論的に示される.実際の軌跡データを用いた実験では提案手法が従来の圧縮FM-indexと比較して数倍から数十倍程度高速であり,また圧縮率についても大幅に改善することを示す.