[2C4-OS-7a] OS-7 (1)

[2C4-OS-7a-01] Succinct Trie Index for Fast and Memory-Efficient Trajectory Similarity Search

〇Shunsuke Kanda¹, Koh Takeuchi², Keisuke Fujii^3,1, Yasuo Tabei¹ (1. RIKEN Center for Advanced Intelligence Project, 2. Kyoto University, 3. Nagoya University)

Keywords:Trajectory Similarity Search, Succinct Data Structures

This paper proposes an efficient similarity search method for massive collections of trajectories. This method enables fast similarity searches by leveraging locality sensitive hashing and tries. To achieve memory efficiency, we propose two novel techniques of node reduction and a space-efficient representation for tries. We experimentally test our method on its ability to retrieve similar trajectories for a query from large collections of trajectories and show that our method performs superiorly with respect to search time and memory efficiency.