轨迹大数据：数据、应用与技术现状

doi:10.11959/j.issn.1000-436x.2015318

摘要/Abstract

摘要：

移动互联技术的飞速发展催生了大量的移动对象轨迹数据。这些数据刻画了个体和群体的时空动态性，蕴含着人类、车辆、动物的行为信息，对交通导航、城市规划、车辆监控等应用具有重要的价值。为了实现有效的轨迹数据价值提取，近年来学术界和工业界针对轨迹管理问题开展了大量研究工作，包括轨迹数据预处理，以解决数据冗余高、精度差、不一致等问题；轨迹数据库技术，以支持有效的数据组织和高效的查询处理；轨迹数据仓库，支持大规模轨迹的统计、理解和分析；最后是知识提取，从数据中挖掘有价值的模式与规律。因此，综述轨迹大数据分析，从企业数据、企业应用、前沿技术这3个角度揭示该领域的现状。

关键词: 时空数据库, 轨迹数据管理, 数据索引, 查询优化

Abstract:

The fast development of mobile internet has given rise to an extremely large volume of moving objects trajectory data.These data not only reflect the spatio-temporal mobility of individuals and groups,but may also contain the behavior information of people,vehicles animals,and other objects of interest.They are invaluable for route planning,urban planning and vehicle monitoring,etc.,and tremendous efforts have been made to support effective trajectory data management,including trajectory data pre-processing,which handles issues such as high redundancy,low precision and inconsistency of sampling; trajectory database technologies,concerning the efficient and effective storage of trajectory data and query processing; trajectory data warehousing,which supports the analytics on large-scale trajectory data;knowledge discovery,by which useful patterns can be extracted from trajectory data.A survey of trajectory big data analytics from three different aspects:data,applications and techniques is provided.

Key words: spatio-temporal database, trajectory data management, indexing structure, query processing

许佳捷,郑凯,池明旻,朱扬勇,禹晓辉,周晓方. 轨迹大数据：数据、应用与技术现状[J]. 通信学报, 2015, 36(12): 97-105.

Jia-jie XU,Kai ZHENG,Ming-min CHI,Yang-yong ZHU,Xiao-hui YU,Xiao-fang ZHOU. Trajectory big data:data,applications and techniques[J]. Journal on Communications, 2015, 36(12): 97-105.

图/表 3

表1

表2

图1

参考文献 56

[1]	SCHUESSLER N , AXHAUSEN K . Processing raw data from global positioning systems without additional information[J]. Transportation Research Record:Journal of the Transportation Research Board, 2009(2105): 28-36.
[2]	DOUGLAS D H , PEUCKER T K . Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica:The International Journal for Geographic Information and Geovisualization, 1973,10(2): 112-122.
[3]	MERATNIA N , ROLF A . Spatiotemporal compression techniques for moving point objects[A]. Advances in Database Technology-EDBT[C]. 2004. 765-782.
[4]	ZHENG Y , et al . Mining interesting locations and travel sequences from GPS trajectories[A]. Proceedings of the 18th International Conference on World Wide Web[C]. 2009.
[5]	PALMA A T , et al . A clustering-based approach for discovering interesting places in trajectories[A]. Proceedings of the 2008 ACM Symposium on Applied Computing[C]. 2008.
[6]	GREENFELD J S . Matching GPS observations to locations on a digital map[A]. Transportation Research Board 81st Annual Meeting[C]. 2002.
[7]	BRAKATSOULAS S ，et al. On map-matching vehicle tracking data[A]. Proceedings of the 31st International Conference on Very Large Data Bases[C]. 2005.
[8]	NEWSON P , KRUMM J . Hidden Markov map matching through noise and sparseness[A]. Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C]. 2009.
[9]	LIU K , et al . Effective map-matching on the most simplified road network[A]. Proceedings of the 20th International Conference on Advances in Geographic Information Systems[C]. 2012ACM.
[10]	LI S ，et al. Quick geo-fencing using trajectory partitioning and boundary simplification[A]. Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C]. 2013.
[11]	TANG Y , ZHU A D , XIAO X . An efficient algorithm for mapping vehicle trajectories onto road networks[A]. Proceedings of the 20th International Conference on Advances in Geographic Information Systems[C]. 2012.
[12]	ZHENG K ，et al. Reducing uncertainty of low-sampling-rate trajectories[A]. Data Engineering (ICDE),2012 IEEE 28th International Conference on[C]. 2012.
[13]	SU H ，et al. Calibrating trajectory data for similarity-based analysis[A]. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data[C]. 2013.
[14]	SU H ，et al. Calibrating trajectory data for spatio-temporal similarity analysis[J]. The VLDB Journal, 2015,24(1): 93-116.
[15]	SISTLA A P ，et al. Modeling and querying moving objects[A]. ICDE[C]. 1997.
[16]	GüTING R H ，et al. A foundation for representing and querying moving objects[J]. ACM Transactions on Database Systems (TODS), 2000,25(1): 1-42.
[17]	WANG H ，et al. SharkDB:An in-memory column-oriented trajectory storage[A]. Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management[C]. 2014.
[18]	KELLARIS PELEKIS G N , THEODORIDIS Y . Trajectory compression under network constraints[A]. Advances in Spatial and Temporal Databases[C]. 2009. 392-398.
[19]	SONG R ，et al. PRESS:A novel framework of trajectory compression in road networks[J]. Proceedings of the VLDB Endowment, 2014,7(9): 661-672.
[20]	CHAN W S , CHIN F . Approximation of polygonal curves with minimum number of line segments or minimum error[J]. International Journal of Computational Geometry ＆ Applications, 1996,6(1): 59-77.
[21]	GUTTMAN A . R-trees:a dynamic index structure for spatial searching[A]. SIGMOD[C]. 1984. 47-57.
[22]	PFOSER D , JENSEN C S , THEODORIDIS Y . Novel approaches to the indexing of moving object trajectories[A]. Proceedings of VLDB[C]. 2000.
[23]	NASCIMENTO M A , SILVA J R . Towards historical R-trees[A]. Proceedings of the 1998 ACM Symposium on Applied Computing[C]. 1998.
[24]	YUFEI T , PAPADIAS D . MV3R-tree:a spatio-temporal access method for timestamp and interval queries[A]. VLDB[C]. 2001. 431-440.
[25]	CHAKKA V P , EVERSPAUGH A C , PATEL J M . Indexing large trajectory data sets with SETI[A]. CIDR[C]. 2003.
[26]	丁治明 . 一种适合于频繁位置更新的网络受限移动对象轨迹索引[J]. 计算机学报, 2012,35(7): 1448-1461. DING Z M . An index structure for frequently updated network-constrainted moving object trajectories[J]. Chinese Journal of Computers, 2012,35(7): 1448-1461.
[27]	VLACHOS M , KOLLIOS G , GUNOPULOS D . Discovering similar multidimensional trajectories[A]. Data Engineering,2002 Proceedings 18th International Conference on[C]. 2002.
[28]	CHEN L , NG R . On the marriage of lp-norms and edit distance[A]. Proceedings of the Thirtieth International Conference on Very Large Data Bases-Volume[C]. 2004.
[29]	CHEN L , ?ZSU M T , ORIA V . Robust and fast similarity search for moving object trajectories[A]. Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data[C]. 2005.ACM.
[30]	CHEN Z , et al . Searching trajectories by locations:an efficiency study[A]. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data[C]. 2010.
[31]	ZHENG Y , et al . Learning transportation mode from raw gps data for geographic applications on the web[A]. Proceedings of the 17th International Conference on World Wide Web[C]. 2008.
[32]	YAN Z , et al . Semantic trajectories:Mobility data computation and annotation[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2013,4(3): 49.
[33]	ALVARES L O , et al . A model for enriching trajectories with semantic geographical information[A]. Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems[C]. 2007.
[34]	ZHENG K , et al . Towards efficient search for activity trajectories[A]. Data Engineering (ICDE),2013 IEEE 29th International Conference[C]. 2013.
[35]	LIN B , SU J . One way distance:For shape based similarity search of moving object trajectories[J]. Geoinformatica, 2008,12(2): 117-142.
[36]	ZHENG B , et al . Approximate keyword search in semantic trajectory database[A]. Data Engineering (ICDE),2015 IEEE 31st International Conference[C]. 2015.
[37]	MA C , et al . KSQ:Top-k similarity query on uncertain trajectories[J]. Knowledge and Data Engineering,IEEE Transactions, 2013,25(9): 2049-2062.
[38]	ZHENG Y . Trajectory data mining:an overview[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2015,6(3): 29.
[39]	GIANNOTTI F ，et al. Trajectory pattern mining[A]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. 2007.
[40]	WANG Y , ZHENG Y , XUE Y . Travel time estimation of a path using sparse trajectories[A]. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. 2014.
[41]	CHEN Z , SHEN H T , ZHOU X . Discovering popular routes from trajectories[A]. Data Engineering (ICDE),2011 IEEE 27th International Conference[C]. 2011.
[42]	LEE J G , HAN J , LI X . Trajectory outlier detection:A partition-and-detect framework[A]. Data Engineering,ICDE 2008 IEEE 24th International Conference[C]. 2008.
[43]	KRUMM J , HORVITZ E . Predestination:Inferring destinations from partial trajectories[A]. UbiComp 2006:Ubiquitous Computing[C]. 2006. 243-260.
[44]	LIAO L , et al . Learning and inferring transportation routines[J]. Artificial Intelligence, 2007,171(5): 311-331.
[45]	CAO H , MAMOULIS N , CHEUNG D W . Discovery of periodic patterns in spatiotemporal sequences[J]. Knowledge and Data Engineering,IEEE Transactions on, 2007,19(4): 453-467.
[46]	GUDMUNDSSON J , KREVELD M V . Computing longest duration flocks in trajectory data[A]. Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems[C]. 2006.ACM.
[47]	JEUNG H , et al . Discovery of convoys in trajectory databases[J]. Proceedings of the VLDB Endowment, 2008,1(1): 1068-1080.
[48]	LI Z , et al . Swarm:Mining relaxed temporal moving object clusters[J]. Proceedings of the VLDB Endowment, 2010,3(1-2): 723-734.
[49]	ZHENG K , ZHENG Y ，et al. On discovery of gathering patterns from trajectories[A]. ICDE[C]. 2013. 242-253
[50]	ZHENG K , ZHENG Y ,et al. Online discovery of gathering patterns over trajectories[J]. IEEE Trans Knowl Data Eng, 2004 26(8): 1974-1988.
[51]	TANG L A , et al . On discovery of traveling companions from streaming trajectories[A]. Data Engineering (ICDE),IEEE 28th International Conference[C]. 2012.
[52]	LEE J G , HAN J , WHANG K Y . Trajectory clustering:a partition-and-group framework[A]. Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data[C]. 2007.
[53]	LI Z , et al . Incremental clustering for trajectories[A]. Database Systems for Advanced Applications[C]. 2010.
[54]	CAO X , CONG G , JENSEN C S . Mining significant semantic locations from GPS data[J]. Proceedings of the VLDB Endowment, 2010,3(1-2): 1009-1020.
[55]	YUAN J , et al . T-drive:driving directions based on taxi trajectories[A]. Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems[C]. 2010.
[56]	SU H , et al . Making sense of trajectory data:a partition-and- summarization approach[A]. Data Engineering (ICDE),IEEE 31st International Conference[C]. 2015.

数据种类	采集方式	采样频率	日均数据量（采样点）	数据总量
车辆轨迹	车载GPS	秒级、分钟级	千万?亿级	TB级
移动轨迹	地图APP	秒级、分钟级	千万?百亿级	TB、PB级
手机轨迹	蜂窝基站	分钟级	十亿?百亿级	TB、PB级
公交轨迹	公交卡	小时级	百万?千万级	TB、PB级
卡口数据	卡口抓拍	分钟级	千万级别	TB级
行为轨迹	社交媒体	分钟、小时级	百万?千万级	PB级

应用	所用数据	应用现状
大众化经验路径推荐	出租车GPS轨迹、私家车移动轨迹数据、气象数据、交通路网数据、历史事故数据等	广泛应用在地图服务公司，显著提升服务水平
交通路况精准预测	GPS 数据（流）、路网路况数据、气象数据、大型活动记录、重大事故数据等	用于地图服务和交通指挥系统，但精度尚需提高
城市规划智能决策	轨迹数据、地图数据、兴趣点数据、消费数据、价格数据、公交线路、历史事故等数据	用于数据驱动的规划决策，多源数据集成与融合是难点
个性化服务与活动推荐	车辆与手机轨迹、社交网络与社交媒体数据、兴趣点和签到、评论数据等	用于基于位置的服务推荐，需提高语义理解和推荐算法
出租车服务	出租车GPS轨迹、私家车移动轨迹、公交线路与轨迹等数据	应用于相关业务优化，有进一步提升空间