CiNCT: Compression and Retrieval for Massive Vehicular Trajectories via Relative Movement Labeling
Satoshi Koide, Yukihiro Tadokoro, Chuan Xiao, Yoshiharu Ishikawa · 2018
In this paper, we present a compressed data structure for moving object trajectories in a road network, which are represented as sequences of road edges. Unlike existing compression methods for trajectories in a network, our method supports pattern matching and decompression from an arbitrary position while retaining high compressibility with theoretical guarantees. Specifically, our method is based on FM-index, a fast and compact data structure for pattern matching. To further enhance the compression performance, we incorporate thesparsityof road networks. In particular, we present the novel concepts ofrelative movement labelingandPseudoRank, each contributing to significant reduction in data size and query processing time. Our theoretical analysis and experimental studies reveal the advantages of our proposed method as compared to existing trajectory compression methods and FM-index variants.