Details

Autor(en) / Beteiligte

• Koide, Satoshi
• Tadokoro, Yukihiro
• Chuan Xiao
• Ishikawa, Yoshiharu

Titel

CiNCT: Compression and Retrieval for Massive Vehicular Trajectories via Relative Movement Labeling

Ist Teil von

• 2018 IEEE 34th International Conference on Data Engineering (ICDE), 2018, p.1097-1108

Ort / Verlag

IEEE

Erscheinungsjahr

2018

Quelle

IEEE Electronic Library (IEL)

Beschreibungen/Notizen

• 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 the sparsity of road networks. In particular, we present the novel concepts of relative movement labeling and PseudoRank , 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.