Compressing large scale urban trajectory data

ISCAS OpenIR

	Compressing large scale urban trajectory data
	Liu, Kuien (1); Li, Yaguang (1); Dai, Jian (1); Shang, Shuo (2); Zheng, Kai (3)
	2014
会议名称	4th International Workshop on Cloud Data and Platforms, CloudDP 2014
会议日期	April 13, 2014 - April 13, 2014
会议地点	Amsterdam, Netherlands
收录类别	EI
出版地	Association for Computing Machinery
部门归属	(1) Institute of Software, Chinese Academy of Sciences, Beijing 100190, China; (2) China University of Petroleum, Beijing 102249, China; (3) University of Queensland, Brisbane QLD 4072, Australia
摘要	With the increasing size of trajectory data generated by location-based services and applications which are built from inexpensive GPS-enabled devices in urban environments, the need for com- pressing large scale trajectories becomes obvious. This paper pro- poses a scalable urban trajectory compression scheme (SUTC) that can compress a set of trajectories collectively by exploiting com- mon movement behaviors among the urban moving objects such as vehicles and smartphone users. SUTC exploits that urban objects moving in similar behaviors naturally, especially large-scale of hu- man and vehicle which are moving constrained by some geograph- ic context (e.g., road networks or routes). To exploit redundancy across a large set of trajectories, SUTC first transforms trajectory sequences from Euclidean space to network-constrained space and represents each trajectory with a sequence of symbolic positions in textual domain. Then, SUTC performs compression by encoding the symbolic sequences with general-purpose compression meth-ods. The key challenge in this process is how to transform the tra-jectory data from spatio-temporal domain to textual domain with-out introducing unbounded error. We develop two strategies (i.e.,velocity-based symbolization, and beacon-based symbolization) to enrich the symbol sequences and achieves high compression ratios by sacrificing a little bit the decoding accuracy. Besides, we al-so optimize the organization of trajectory data in order to adapt it to practical compression algorithms, and increase the efficiency of compressing processes. Our experiments on real large-scale trajec-tory datasets demonstrate the superiority and feasibility of the our proposed algorithms. Copyright © 2014 ACM.; With the increasing size of trajectory data generated by location-based services and applications which are built from inexpensive GPS-enabled devices in urban environments, the need for com- pressing large scale trajectories becomes obvious. This paper pro- poses a scalable urban trajectory compression scheme (SUTC) that can compress a set of trajectories collectively by exploiting com- mon movement behaviors among the urban moving objects such as vehicles and smartphone users. SUTC exploits that urban objects moving in similar behaviors naturally, especially large-scale of hu- man and vehicle which are moving constrained by some geograph- ic context (e.g., road networks or routes). To exploit redundancy across a large set of trajectories, SUTC first transforms trajectory sequences from Euclidean space to network-constrained space and represents each trajectory with a sequence of symbolic positions in textual domain. Then, SUTC performs compression by encoding the symbolic sequences with general-purpose compression meth-ods. The key challenge in this process is how to transform the tra-jectory data from spatio-temporal domain to textual domain with-out introducing unbounded error. We develop two strategies (i.e.,velocity-based symbolization, and beacon-based symbolization) to enrich the symbol sequences and achieves high compression ratios by sacrificing a little bit the decoding accuracy. Besides, we al-so optimize the organization of trajectory data in order to adapt it to practical compression algorithms, and increase the efficiency of compressing processes. Our experiments on real large-scale trajec-tory datasets demonstrate the superiority and feasibility of the our proposed algorithms. Copyright © 2014 ACM.
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16586
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Liu, Kuien ,Li, Yaguang ,Dai, Jian ,et al. Compressing large scale urban trajectory data[C]. Association for Computing Machinery,2014.