[2C4-OS-7a] 移動系列のデータマイニングと機械学習 (1)

[2C4-OS-7a-01] 高速かつ省メモリな軌跡類似検索のための簡潔トライ索引

〇神田 峻介¹、竹内 孝²、藤井 慶輔^3,1、田部井 靖生¹ (1. 理化学研究所革新知能統合研究センター、2. 京都大学、3. 名古屋大学)

キーワード：軌跡類似検索、簡潔データ構造

本稿では、大規模な軌跡データに対する効率的な類似検索手法を提案する。本手法はLocality Sensitive HashingとTrie木を活用し高速な類似検索を実現する。高いメモリ効率を実現するために、冗長なTrie木の節点を削減する手法を提案する。さらに、三進数配列を用いたTrie木の簡潔表現であるSuccinct Trit-Array Trieを提案する。大規模な実データを用いた実験において、既存手法と比べて提案手法は検索速度とメモリ効率に関して高い性能を示した。