Indexing, Retrieval, and Compression of Moving Objects in Networks: A String Processing Approach

(邦訳:ネットワーク上の移動オブジェクトに対する索引,検索および圧縮: 文字列アルゴリズムによるアプローチ)
 
小出 智士
(株)豊田中央研究所 研究員
 
キーワード
空間データベース データ圧縮 文字列アルゴリズム

[背景] GPS等から得られる移動履歴情報(軌跡データ)の大規模化

[問題]大規模軌跡データに対する効率的な索引・検索・圧縮の実現
[貢献]文字列アルゴリズムの適用による効率的な手法群の提案


 自動車やスマホなどの「移動オブジェクト」から収集される軌跡データ(位置情報の時系列)は,データ駆動型のアプリケーション,たとえば自動運転開発,高度な車載ナビゲーションシステム,交通行動分析などにとって重要なものであり,生活の利便性の向上や社会的な課題の解決つながることが期待されるものである.

 一方で収集される軌跡データは大規模化している.少し古いデータになるが,米国で2011年に生成されたGPSデータは53テラバイトにものぼる,という試算がある.通常,我々が扱うデータはそれよりも小さいが,それでも軌跡データをテキストファイルとしてそのまま保管しても利用価値が低いことは想像できるだろう.そのため,本研究では大規模な軌跡データを効率良く扱うためのデータ格納や検索アルゴリズムなどの基盤的な操作に関する研究を行った.

 本研究は,通常は緯度経度の列として表現される軌跡データを道路リンクIDの列として表現する,という点が特徴である.この表現を用いることは,(1)ユーザの利便性(2)アルゴリズムの設計,の2つの観点において利点がある.

【1. ユーザの利便性】 道路リンクは渋滞情報などにおいても基本的な情報処理の単位であり,緯度経度情報よりも都合がよいことが多い.また,道路リンクID列表現を用いると,「ある経路を走行した軌跡を検索する」などの,「走行経路」を単位とした実用的かつ高度な問合せも可能になる.

【2. アルゴリズムの設計】 軌跡データを道路リンクID列,すなわち記号列として扱うことで「文字列アルゴリズム」の利用が可能になる.これらは従来,情報検索分野やゲノム情報処理の分野で研究されてきたものである.本研究ではFM-indexと呼ばれる,文字列索引を空間データベース分野の手法に整合的に統合できることを見出した.これにより,上述した「走行経路」を単位とする種々の問合せの効率な処理が可能になった.

 上述した方法論の提案に加えて,さらに本研究では軌跡データを格納するFM-index自体の改良も行った.FM-indexはインメモリ索引であるため,大規模データを扱うためにはデータ圧縮を行うことがある.本研究では以下で述べるような「軌跡データの特徴」を積極的に活かすことで,高性能化を実現した.

 たとえば約100万(≒2の20乗)種類の道路リンクを持つ道路ネットワークを考える.このとき,記号あたりに必要なビット数はlog2(2の20乗)=20ビットである.一方,道路ネットワークは十字路などの構造的特徴を持ち,これによって軌跡データを「直進,直進,右折,左折...」のような記号列に変換することができる.この表現では記号あたり2ビット以下で表現でき,大幅なデータの圧縮が可能になる.このアイディアをもとに新しい圧縮・検索アルゴリズムを提案し,従来の圧縮手法よりも大幅に高い圧縮率・高速な検索処理を実現した.

 

(2020年5月21日受付)
 
取得年月日:2020年3月
学位種別:博士(情報学)
大学:名古屋大学



推薦文
:(データベースシステム研究会)


今日では,カーナビやGPSの普及により,自動車などの移動軌跡データが大量に収集されている.本研究では,大規模な移動軌跡データから条件を満たす軌跡データを高速に検索する新たな索引手法を示している.文字列索引技術をこの問題に適用し発展させ,高速かつ優れた圧縮率も達成しており,高く評価されている.


研究生活


私は社会人博士として3年間,大学での研究活動を行いました.社会人博士は休日に執筆作業などを進めることになり,家族の理解が重要だと思います.私の場合は博士2年のときに子供が生まれてからはなかなか時間をとることができず,心理的なストレスもありましたが,家族の理解もあってなんとか博士号を取得することができました.入学前に十分に構想・準備した上で臨むことが心理的ストレスを軽減すると思います.

私は,進学前から企業研究所で研究開発を行ってきましたが,それでも大学での研究生活では非常に多くのものを得ることができました.第一に,大学での研究では,自分が興味の赴くままにアルゴリズムやデータ構造などの分野を突き詰めて勉強することができました.また「社会に発信する(=論文を書ききる)ために何をすべきか」ということを学ぶことができ,この点でも非常に有意義なものとなりました.お世話になった皆様方には深く感謝いたします.