Retrieving Similar Trajectories from Cellular Data of Multiple Carriers at City Scale
Authors: 
Zhihao Shen, Wan Du, Xi Zhao, Jianhua ZouAuthors Info & Claims
Article No.: 47, Pages 1 - 28
Abstract
Retrieving similar trajectories aims to search for the trajectories that are close to a query trajectory in spatio-temporal domain from a large trajectory dataset. This is critical for a variety of applications, like transportation planning and mobility analysis. Unlike previous studies that perform similar trajectory retrieval on fine-grained GPS data or single cellular carrier, we investigate the feasibility of finding similar trajectories from cellular data of multiple carriers, which provide more comprehensive coverage of population and space. To handle the issues of spatial bias of cellular data from multiple carriers, coarse spatial granularity, and irregular sparse temporal sampling, we develop a holistic system cellSim. Specifically, to avoid the issue of spatial bias, we first propose a novel map matching approach, which transforms the cell tower sequences from multiple carriers to routes on a unified road map. Then, to address the issue of temporal sparse sampling, we generate multiple routes with different confidences to increase the probability of finding truly similar trajectories. Finally, a new trajectory similarity measure is developed for similar trajectory search by calculating the similarities between the irregularly-sampled trajectories. Extensive experiments on a large-scale cellular dataset from two carriers and real-world 1,701 km query trajectories reveal that cellSim provides state-of-the-art performance for similar trajectory retrieval.
References
[1]
Essam Algizawy, Tetsuji Ogawa, and Ahmed El-Mahdy. 2017. Real-time large-scale map matching using mobile phone data. ACM Transactions on Knowledge Discovery from Data 11, 4 (2017), 1–38.
[2]
Fereshteh Asgari, Alexis Sultan, Haoyi Xiong, Vincent Gauthier, and Mounîm A. El-Yacoubi. 2016. CT-Mapper: Mapping sparse multimodal cellular trajectories using a multilayer transportation network. Computer Communications 95 (2016), 69–81.
[3]
Richard Becker, Ramón Cáceres, Karrie Hanson, Sibren Isaacman, Ji Meng Loh, Margaret Martonosi, James Rowland, Simon Urbanek, Alexander Varshavsky, and Chris Volinsky. 2013. Human mobility characterization from cellular network data. Communications of the ACM 56, 1 (2013), 74–82.
[4]
David Bernstein and Alain Kornhauser. 1998. An introduction to map matching for personal navigation assistants. Geometric Distributions 122, 7 (1998), 1082–1083.
[5]
Carola A. Blazquez and Alan P. Vonderohe. 2005. Simple map-matching algorithm applied to intelligent winter maintenance vehicle data. Transportation Research Record 1935, 1 (2005), 68–76.
[6]
Vincent D. Blondel, Markus Esch, Connie Chan, Fabrice Clerot, Pierre Deville, Etienne Huens, Frédéric Morlot, Zbigniew Smoreda, and Cezary Ziemlicki. 2012. Data for development: the D4D challenge on mobile phone data. Computer Science (2012).
[7]
Loïc Bonnetain, Angelo Furno, Jean Krug, and Nour-Eddin El Faouzi. 2019. Can we map-match individual cellular network signaling trajectories in urban environments? Data-driven study. Transportation Research Record 2673, 7 (2019), 74–88.
[8]
Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. 2005. On map-matching vehicle tracking data. In Proceedings of the 31st International Conference on Very Large Data Bases. 853–864.
[9]
Lei Chen and Raymond Ng. 2004. On the marriage of lp-norms and edit distance. In Proceedings of the 30th International Conference on Very Large Data Bases-Volume 30. 792–803.
[10]
Yun Chen and Jignesh M. Patel. 2009. Design and evaluation of trajectory join algorithms. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 266–275.
[11]
Yves-Alexandre de Montjoye, Zbigniew Smoreda, Romain Trinquart, Cezary Ziemlicki, and Vincent D. Blondel. 2014. D4D-Senegal: The Second Mobile Phone Data for Development Challenge. arXiv:1407.4885. Retrieved from https://arxiv.org/abs/1407.4885
[12]
Sinem Coleri Ergen, Huseyin Serhat Tetikol, Mehmet Kontik, Raffi Sevlian, Ram Rajagopal, and Pravin Varaiya. 2013. RSSI-fingerprinting-based mobile phone localization with route constraints. IEEE Transactions on Vehicular Technology 63, 1 (2013), 423–428.
[13]
Zipei Fan, Xuan Song, Ryosuke Shibasaki, and Ryutaro Adachi. 2015. Citymomentum: An online approach for crowd behavior prediction at a citywide level. In Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing. 559–569.
[14]
Zipei Fan, Xuan Song, Tianqi Xia, Renhe Jiang, Ryosuke Shibasaki, and Ritsu Sakuramachi. 2018. Online deep ensemble learning for predicting citywide human mobility. Proceedings of the ACM on Interactive, Mobile, Wearable, and Ubiquitous Technologies 2, 3 (2018), 1–21.
[15]
Zhihan Fang, Guang Wang, Xiaoyang Xie, Fan Zhang, and Desheng Zhang. 2021. Urban map inference by pervasive vehicular sensing systems with complementary mobility. Proceedings of the ACM on Interactive, Mobile, Wearable, and Ubiquitous Technologies 5, 1 (2021), 1–24.
[16]
Paolo Gallo, Donatella Gubiani, Angelo Montanari, and Nicola Saccomanno. 2020. A new similarity measure for low-sampling cellular fingerprint trajectories. In Proceedings of the IEEE International Conference on Mobile Data Management. IEEE, 9–18.
[17]
Gang Hu, Jie Shao, Fenglin Liu, Yuan Wang, and Heng Tao Shen. 2017. If-matching: Towards accurate map-matching with information fusion. IEEE Transactions on Knowledge and Data Engineering 29, 1 (2017), 114–127.
[18]
Xingyu Huang, Yong Li, Yue Wang, Xinlei Chen, Yu Xiao, and Lin Zhang. 2018. CTS: A cellular-based trajectory tracking system with GPS-level accuracy. Proceedings of the ACM on Interactive, Mobile, Wearable, and Ubiquitous Technologies 1, 4 (2018), 1–29.
[19]
Sibren Isaacman, Richard Becker, Ramón Cáceres, Margaret Martonosi, James Rowland, Alexander Varshavsky, and Walter Willinger. 2012. Human mobility modeling at metropolitan scales. In Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services. 239–252.
[20]
George R. Jagadeesh and Thambipillai Srikanthan. 2017. Online map-matching of noisy and sparse location data with hidden markov and route choice models. IEEE Transactions on Intelligent Transportation Systems 18, 9 (2017), 2423–2434.
[21]
Renhe Jiang, Xuan Song, Zipei Fan, Tianqi Xia, Quanjun Chen, Qi Chen, and Ryosuke Shibasaki. 2018. Deep ROI-based modeling for urban human mobility prediction. Proceedings of the ACM on Interactive, Mobile, Wearable, and Ubiquitous Technologies 2, 1 (2018), 1–29.
[22]
Bjornar Larsen and Chinatsu Aone. 1999. Fast and effective text mining using linear-time document clustering. In Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 16–22.
[23]
Ilias Leontiadis, Antonio Lima, Haewoon Kwak, Rade Stanojevic, David Wetherall, and Konstantina Papagiannaki. 2014. From cells to streets: Estimating mobile paths with cellular-side data. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. 121–132.
[24]
Yaliang Li, Jing Gao, Patrick PC Lee, Lu Su, Caifeng He, Cheng He, Fan Yang, and Wei Fan. 2016. A weighted crowdsourcing approach for network quality measurement in cellular data networks. IEEE Transactions on Mobile Computing 16, 2 (2016), 300–313.
[25]
Xuemei Liu, James Biagioni, Jakob Eriksson, Yin Wang, George Forman, and Yanmin Zhu. 2012. Mining large-scale, sparse GPS traces for map inference: Comparison of approaches. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 669–677.
[26]
Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang. 2009. Map-matching for low-sampling-rate GPS trajectories. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 352–361.
[27]
Beijing Tele Industry Information Technology Ltd.2019. GPS Toolbox. Retrieved from https://play.google.com/store/apps/details?id=net.gotele.gpsbox&hl=zh
[28]
Mingqi Lv, Ling Chen, Yanbin Shen, and Gencai Chen. 2015. Measuring cell-id trajectory similarity for mobile phone route classification. Knowledge-Based Systems 89 (2015), 181–191.
[29]
Chuishi Meng, Xiuwen Yi, Lu Su, Jing Gao, and Yu Zheng. 2017. City-wide traffic volume inference with loop detector data and taxi trajectories. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 1–10.
[30]
Reham Mohamed, Heba Aly, and Moustafa Youssef. 2016. Accurate real-time map matching for challenging environments. IEEE Transactions on Intelligent Transportation Systems 18, 4 (2016), 847–857.
[31]
Diala Naboulsi, Marco Fiore, Stephane Ribot, and Razvan Stanica. 2016. Large-scale mobile traffic analysis: A survey. IEEE Communications Surveys and Tutorials 18, 1 (2016), 124–161.
[32]
Elahe Naserian, Xinheng Wang, Xiaolong Xu, and Yuning Dong. 2018. A framework of loose travelling companion discovery from human trajectories. IEEE Transactions on Mobile Computing 17, 11 (2018), 2497–2511.
[33]
Paul Newson and John Krumm. 2009. Hidden Markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 336–343.
[34]
Atsuyuki Okabe, Barry Boots, and Kokichi Sugihara. 1992. Spatial tessellations: concepts and applications of Voronoi diagrams. John Wiley & Sons, Inc., USA.
[35]
N. Oliver, B. Lepri, H. Sterly, R. Lambiotte, and P. Vinck. 2020. Mobile phone data for informing public health actions across the COVID-19 pandemic life cycle. Science Advances 6, 23 (2020), eabc0764.
[36]
Jeongyeup Paek, Kyu-Han Kim, Jatinder P. Singh, and Ramesh Govindan. 2011. Energy-efficient positioning for smartphones using cell-id sequence matching. In Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services. 293–306.
[37]
Mohammed A. Quddus, Robert B. Noland, and Washington Y. Ochieng. 2006. A high accuracy fuzzy logic based map matching algorithm for road transport. Journal of Intelligent Transportation Systems 10, 3 (2006), 103–115.
[38]
Anshul Rai, Krishna Kant Chintalapudi, Venkata N. Padmanabhan, and Rijurekha Sen. 2012. Zee: Zero-effort crowdsourcing for indoor localization. In Proceedings of the 18th Annual International Conference on Mobile Computing and Networking. 293–304.
[39]
Sayan Ranu, P. Deepak, Aditya D. Telang, Prasad Deshpande, and Sriram Raghavan. 2015. Indexing and matching trajectories under inconsistent sampling rates. In Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. IEEE, 999–1010.
[40]
Shuo Shang, Lisi Chen, Zhewei Wei, Christian S. Jensen, Zheng Kai, and Panos Kalnis. 2018. Parallel trajectory similarity joins in spatial networks. VLDB Journal 27, 3 (2018), 395–420.
[41]
Vinay Kumar Sharma, Satyajit Mondal, and Ankit Gupta. 2017. Analysis of u-turning behaviour of vehicles at mid-block median opening in six lane urban road: A case study. International Journal for Traffic and Transport Engineering 7, 2 (2017), 243–255.
[42]
Luke Shaw. 2018. Provisional Road Traffic Estimates, Great Britain. Retrieved from https://assets.publishing.service.gov.uk/government/uploads/system/uploads/attachment_data/file/726948/prov-road-traffic-estimates-apr-2017-mar-2018.pdf
[43]
Zhihao Shen, Wan Du, Xi Zhao, and Jianhua Zou. 2020. DMM: Fast map matching for cellular data. In Proceedings of the 26th Annual International Conference on Mobile Computing and Networking. 1–14.
[44]
Zhihao Shen, Kang Yang, Xi Zhao, Jianhua Zou, and Wan Du. 2023. DeepAPP: A deep reinforcement learning framework for mobile application usage prediction. IEEE Transactions on Mobile Computing 22, 02 (2023), 824–840.
[45]
Konstantin Shvachko, Hairong Kuang, Sanjay Radia, and Robert Chansler. 2010. The hadoop distributed file system. In Proceedings of the IEEE 26th Symposium on Mass Storage Systems and Technologies. 1–10.
[46]
Yiwei Song, Dongzhe Jiang, Yunhuai Liu, Zhou Qin, Chang Tan, and Desheng Zhang. 2021. HERMAS: A human mobility embedding framework with large-scale cellular signaling data. Proceedings of the ACM on Interactive, Mobile, Wearable, and Ubiquitous Technologies 5, 3 (2021), 1–21.
[47]
Yiwei Song, Yunhuai Liu, Wenqing Qiu, Zhou Qin, Chang Tan, Can Yang, and Desheng Zhang. 2020. MIFF: Human mobility extractions with cellular signaling data under spatio-temporal uncertainty. Proceedings of the ACM on Interactive, Mobile, Wearable, and Ubiquitous Technologies 4, 4 (2020), 1–19.
[48]
Mudhakar Srivatsa, Raghu Ganti, Jingjing Wang, and Vinay Kolar. 2013. Map matching: Facts and myths. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 484–487.
[49]
Arvind Thiagarajan, Lenin Ravindranath, Hari Balakrishnan, Samuel Madden, and Lewis Girod. 2011. Accurate,\(\lbrace\)Low-Energy\(\rbrace\) Trajectory mapping for mobile devices. In Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation.
[50]
Arvind Thiagarajan, Lenin Ravindranath, Katrina LaCurts, Samuel Madden, Hari Balakrishnan, Sivan Toledo, and Jakob Eriksson. 2009. Vtrack: Accurate, energy-aware road traffic delay estimation using mobile phones. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. 85–98.
[51]
Yupeng Tuo, Xiaochun Yun, and Yongzheng Zhang. 2017. NSIM: A robust method to discover similar trajectories on cellular network location data. In Proceedings of the IEEE 28th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications. IEEE, 1–7.
[52]
Andrew Viterbi. 1967. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory 13, 2 (1967), 260–269.
[53]
Dong Xie, Feifei Li, and Jeff M. Phillips. 2017. Distributed trajectory similarity search. Proceedings of the VLDB Endowment 10, 11 (2017), 1478–1489.
[54]
Fengli Xu, Tong Xia, Hancheng Cao, Yong Li, Funing Sun, and Fanchao Meng. 2018. Detecting popular temporal modes in population-scale unlabelled trajectory data. Proceedings of the ACM on Interactive, Mobile, Wearable, and Ubiquitous Technologies 2, 1 (2018), 1–25.
[55]
Dakai Yang, Baigen Cai, and Yifang Yuan. 2003. An improved map-matching algorithm used in vehicle navigation system. In Proceedings of the 2003 IEEE International Conference on Intelligent Transportation Systems. IEEE, 1246–1250.
[56]
Byoung-Kee Yi, Hosagrahar Visvesvaraya Jagadish, and Christos Faloutsos. 1998. Efficient retrieval of similar time sequences under time warping. In Proceedings of the14th International Conference on Data Engineering. IEEE, 201–208.
[57]
Yihong Yuan and Martin Raubal. 2014. Measuring similarity of mobile phone user trajectories–a spatio-temporal edit distance method. International Journal of Geographical Information Science 28, 3 (2014), 496–520.
[58]
Desheng Zhang, Tian He, Fan Zhang, and Chengzhong Xu. 2018. Urban-scale human mobility modeling with multi-Source urban network data. IEEE/ACM Transactions on Networking 26, 2 (2018), 671–684.
[59]
Desheng Zhang, Jun Huang, Ye Li, Fan Zhang, Chengzhong Xu, and Tian He. 2014. Exploring human mobility with multi-source data at extremely large metropolitan scales. In Proceedings of the 20th Annual International Conference on Mobile Computing and Networking. 201–212.
[60]
Shanjiang Zhu and David Levinson. 2015. Do people use the shortest path? An empirical test of Wardrop’s first principle. PloS One 10, 8 (2015), e0134322.
Index Terms
- Retrieving Similar Trajectories from Cellular Data of Multiple Carriers at City Scale
Recommendations
Clustering and aggregating clues of trajectories for mining trajectory patterns and routes
In this paper, we propose a new trajectory pattern mining framework, namely Clustering and Aggregating Clues of Trajectories (CACT), for discovering trajectory routes that represent the frequent movement behaviors of a user. In addition to spatial and ...
Searching similar trajectories in real time: an effectiveness and efficiency study
WAIM'11: Proceedings of the 2011 international conference on Web-Age Information ManagementSearching similar trajectories in real time has been a challenging task in a large variety of location-aware applications. This paper addresses its two key issues, i.e. evaluating the similarity between two trajectories reasonably and effectively, and ...
Location relevance and diversity in symbolic trajectories with application to telco data
SSTD '19: Proceedings of the 16th International Symposium on Spatial and Temporal DatabasesWe present an approach to the discovery and characterization of relevant locations and related mobility patterns in symbolic trajectories built on call detail records - CDRs - of mobile phones (telco trajectories). While the discovery of relevant ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Journal Family
Publication History
Published: 16 February 2024
Online AM: 03 August 2023
Accepted: 31 July 2023
Revised: 21 March 2023
Received: 27 January 2022
Published in TOSN Volume 20, Issue 2
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 162Total Downloads
- Downloads (Last 12 months)111
- Downloads (Last 6 weeks)8
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in