トラジェクトリデータに対する効率良い近似パターン照合アルゴリズム

摘要

本稿では，拡張文字列パターンに対する文字列照合問題のd次元軌跡データに対する拡張を考え，その効率良い照合アルゴリズムについて考察する．ここで、正定数rに対して，パターン点とテキスト点の照合を，点同士のL_∞距離が閾値r以下であることと定める．提案アルゴリズムは，ビット並列計算に基づいて，定数次元のとき，長さnのテキスト軌跡に対する長さmの拡張トラジェクトリパターンに対する，閾値rによるすべての近似出現を，前処理O（m）時間と，領域O（m）語，O（nmloglogn/logn）照合時間で見つける．計算量は次元dに関して指数的である．