A Hybrid Compression Framework for Large Scale Trajectory Data in Road Networks

WU Peili; TAN Yu'an; ZHENG Jun; ZHANG Quanxin; LI Yuanzhang

doi:10.1049/cje.2015.10.011

Volume 24 Issue 4

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2015 > 24(4): 730-739

WU Peili, TAN Yu'an, ZHENG Jun, et al., “A Hybrid Compression Framework for Large Scale Trajectory Data in Road Networks,” Chinese Journal of Electronics, vol. 24, no. 4, pp. 730-739, 2015, doi: 10.1049/cje.2015.10.011

Citation:

WU Peili, TAN Yu'an, ZHENG Jun, et al., “A Hybrid Compression Framework for Large Scale Trajectory Data in Road Networks,” Chinese Journal of Electronics, vol. 24, no. 4, pp. 730-739, 2015, doi: 10.1049/cje.2015.10.011

Citation:

PDF( 1008 KB)

A Hybrid Compression Framework for Large Scale Trajectory Data in Road Networks

doi: 10.1049/cje.2015.10.011

WU Peili^1,2,
TAN Yu'an^1,2,
ZHENG Jun^{1,2
,},
ZHANG Quanxin^1,2,
LI Yuanzhang^1,2,3

1.
School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China;
2.
Beijing Engineering Research Center of Massive Language Information Processing and Cloud Computing Application, Beijing 100081, China;
3.
Space Star Technology CO., Ltd. China Academy of Space Technology, Beijing 100086, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61272511, No.61370063), the National High Technology Research and Development Program of China (863 Program) (No.2013AA01A212), and Beijing Higher Education Young Elite Teacher Project (No.YETP1178).

More Information

Corresponding author: ZHENG Jun (corresponding author)is an associate professor in Schoolof Computer Science and Technology,Beijing Institute of Technology, China.Her research interests include networkand information security, and intelligentinformation processing. (Email:zhengjun@bit.edu.cn)
Received Date: 2015-01-04
Rev Recd Date: 2015-02-06
Publish Date: 2015-10-10

Abstract

Abstract

A Hybrid compression framework of trajectory data (HCFT) is proposed for effective compression of trajectory data with road network limited. It's different from the present researches which mainly focus on compression of single trajectory, and further takes data redundancy raised by the similarity of movement pattern of moving objects into consideration. HCFT divides the redundancy of trajectory data into Single trajectory redundancy (STR) and Multiple trajectories redundancy (MTR) and compresses them in a hybrid way (i.e. synchronous compression for STR at first and then asynchronous compression for MTR). We propose an asynchronous extraction algorithm for MTR based on frequent Road track subsequence (RTS), which replaces similar movement route by RTS, with the complexity of calculation significantly reduced. HCFT can not only gain higher compression ratio, but also ensure effectiveness of compressed trajectory. We also verify effectiveness and superiority of the new method according to the experiments of real trajectory dataset.
- Trajectory data,
- Movement similarity,
- Road track,
- Dictionary coding,
- Multi-trajectories compression

FullText(HTML)

References(24)

References

Z. Huo and X.F. Meng, "A survey of trajectory privacypreserving techniques", Chinese Journal of Computers, Vol.34, No.10, pp.1820-1830, 2011. (in Chinese)

R. Song, W.W. Sun, B.H. Zheng and Y. Zheng, "PRESS: A novel framework of trajectory compression in road networks", Proc. of the VLDB Endowment, Vol.7, No.9, pp.661-672, 2014.

R. Lange, F. Dürr and K. Rothermel, "Efficient real-time trajectory tracking", Proc. of the VLDB Endowment, Vol.20, No.5, pp.671-694, 2011.

Y.F. Li, J.W. Han and J.Yang, "Clustering moving objects", Proc. of SIGKDD, New York, USA, pp.617-622, 2004.

H. Jeung, M.L. Yiu, X.F. Zhou, et al., "Discovery of convoys in trajectory databases", Proc. of the VLDB Endowment, Vol.1, No.1, pp.1068-1080, 2008.

J. Gudmundsson and M.V. Kreveld, "Computing longest duration flocks in trajectory data", Proc. of ACM SIGSPATIAL GIS'06, Arlington, Va, USA, pp.35-42, 2006.

M.L. Yiu and N. Mamoulis, "Clustering objects on a spatial network", Proc. of ACM SIGMOD, Paris, France, pp.443-454, 2004.

F. Verhein and S. Chawla, "Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases", Proc. of DASFAA, Singapore, pp.187-201, 2006.

H. Jeung, Q. Liu, H.T. Shen, et al., "A hybrid prediction model for moving objects", Proc. of ICDE'08, Cancun, Mexico, pp.70- 79, 2008.

J. Yang and M. Hu, "Trajpattern: Mining sequential patterns from imprecise trajectories of mobile objects", Proc. of EDBT, Munich, Germany, pp.664-681, 2006.

D.M. Dai and D.J. Mu, "An algorithm for bus trajectory extraction based on incomplete data source", Chinese Journal of Electronics, Vol.21, No.4, pp.599-603, 2012.

A. Monreale, F. Pinelli, R. Trasarti, et al., "Wherenext: A location predictor on trajectory pattern mining", Proc. of SIGKDD, Paris, France, pp.637-646, 2009.

J.D. Chen, X.F. Meng and C.F Lai, "Clustering objects in a road network", Journal of Software, Vol.8, No.2, pp.332-344, 2007. (in Chinese)

D.H. Douglas and T.K. Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer, Vol.11, No.2, pp.112-122, 1973.

H. Imai and M. Iri, "Polygonal approximations of a curve- formulations and algorithms", Computational Morphology, Vol.9, No.2, pp.71-86, 1988.

N. Meratnia and A. Rolf, "Spatiotemporal compression techniques for moving point objects", Proc. of EDBT, Heraklion, Crete, Greece, pp.765-782, 2004.

H. Cao, O. Wolfson and G. Trajcevski, "Spatio-temporal data reduction with deterministic error bounds", Proc. of the VLDB Endowment, Vol.15, No.3, pp.211-228, 2006.

Y.H. Cai and N. Raymond, "Indexing spatio-temporal trajectories with Chebyshev polynomials", Proc. of SIGMOD, Paris, France, pp.599-610, 2004.

K. Markus, K. Wolfgang, K. Markus, et al., "Compact vehicular trajectory encoding", Proc. of IEEE Vehicular Technology Conference (VTC Spring), Budapest, Hungary, pp.1-5, 2011.

K. Georgios, P. Nikos and T. Yannis, "Map-matched trajectory compression", Journal of Systems and Software, Vol.86, No.6, pp.1566-1579, 2013.

K.F. Richter, F. Schmid and P. Laube, "Semantic trajectory compression: representing urban movement in a nutshell", Journal of Spatial Information Science, Vol.4, No.4, pp.3-30, 2012.

K.E. Liu, J.C. Xiao, Z.M. Ding, et al., "Discovery of hot region in trajectory databases", Journal of Software, Vol.24, No.8, pp.1816-1835, 2013. (in Chinese)

N. Utpal and K.M. Jyotsna, "Modified compression techniques based on optimality of LZW code", Proc. of CIMTA'13, Kalyan, India, pp.949-956, 2013.

Y. Zheng and X.F. Zhou, Computing with spatial trajectories, Springer, Berlin, Germany, 2011.

Relative Articles

Supplements(0)

Cited By

Proportional views