Publication Type

Journal Article

Version

acceptedVersion

Publication Date

4-2018

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

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

30

Issue

4

First Page

613

Last Page

629

ISSN

1041-4347

Identifier

10.1109/TKDE.2017.2776927

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Copyright Owner and License

LARC and Authors

Additional URL

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

Download

Share

COinS