Publication Type

Journal Article

Publication Date

11-2017

Abstract

Recording and querying time-stamped trajectories incurs high cost of data storage and computing. In this paper, we explore several characteristics of the trajectories in road mbox{networks}, which have motivated the idea of coding trajectories by associating timestamps with relative spatial path and locations. Such a representation contains large number of duplicate information to achieve a lower entropy compared with the existing representations, thereby drastically cutting the storage cost. We propose several techniques to compress spatial path and locations separately, which can support fast positioning and achieve better compression ratio. For locations, we propose two novel encoding schemes such that the binary code can preserve distance information, which is very helpful for mbox{LBS} applications. In addition, an unresolved question in this area is whether it is possible to perform search directly on the compressed trajectories, and if the answer is yes, then how. Here we show that directly querying compressed trajectories based on our encoding scheme is possible and can be done efficiently. We design a set of primitive operations for this purpose, and propose index structures to reduce query response time. We demonstrate the advantage of our method and compare it against existing ones through a thorough experimental study on real trajectories in road network. IEEE

Keywords

Compression, Encoding, Entropy, Memory, Presses, Query processing, Representation, Road network, Roads Trajectory

Discipline

Digital Communications and Networking | OS and Networks

Research Areas

Data Management and Analytics

Publication

IEEE Transactions on Knowledge and Data Engineering

Issue

99

First Page

1

Last Page

17

ISSN

1041-4347

Identifier

10.1109/TKDE.2017.2776927

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

https://doi.org/10.1109/TKDE.2017.2776927

Share

COinS