抄録

◎山本雅大・栗田和宏・笹川裕人・有村博紀（北大）

カーナビゲーションシステムやスマートフォンの普及により、2000年頃から自動車や、人、野生動物などの移動データに代表される、軌跡データの種類と量が増え続けており、これらのデータを効率よく利用するための技術が望まれている。本稿では、2次元軌跡データに対する、高速なパターン照合アルゴリズムを提案する。提案アルゴリズムは、空間パターン索引とビット並列法と呼ばれる文字列照合アルゴリズムを組み合わせ、長さmの軌跡パターンPと、長さnの軌跡テキストTに対して、O(m^3/log n)前処理時間とO(m^3/log n)領域を用いて、O(nlog m + mn/log n + occ)実行時間でPのT中の出現をすべて見つける。