WU Peili, TAN Yu'an, ZHENG Jun, ZHANG Quanxin, LI Yuanzhang. A Hybrid Compression Framework for Large Scale Trajectory Data in Road Networks[J]. Chinese Journal of Electronics, 2015, 24(4): 730-739. doi: 10.1049/cje.2015.10.011
Citation: WU Peili, TAN Yu'an, ZHENG Jun, ZHANG Quanxin, LI Yuanzhang. A Hybrid Compression Framework for Large Scale Trajectory Data in Road Networks[J]. Chinese Journal of Electronics, 2015, 24(4): 730-739. doi: 10.1049/cje.2015.10.011

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

doi: 10.1049/cje.2015.10.011
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
  • 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.
  • loading
  • 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (234) PDF downloads(1138) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return