Efficient Map-Matching Parallelization over Bus Trajectories Using Spark

  • Demetrio Gomes Mestre UEPB
  • Thiago Pereira Nóbrega UEPB
  • Tiago Brasileiro Araújo IFPB
  • Andreza Raquel Queiroz UFCG
  • Veruska Borges Santos UFCG
  • Carlos Eduardo Santos Pires UFCG


Recently releases of the Global Positioning System (GPS) trajectories of public bus fleets provided by large cities around the world have given researchers and practitioners the opportunity to explore new challenges regarding the existing public transportation analytic problems involving such cities. One of these new challenges is the identification of bus trajectories referenced by multiple predefined bus routes. This challenge becomes even more complicated when it involves a Big Data scenario, in which managing large volumes of data can exceed the capacity of traditional data processing systems, which demands parallel approaches capable of streamlining this data-intensive task. In this paper, we propose S-BULMA, an efficient parallel map-matching approach for solving this data-intensive problem. Our approach considers the context aspects of the trajectories performed by a bus, such as the analysis of trips performed along one day, to improve the classification of the predefined route that the bus is following. The evaluation results based on real-world open data sources show that S-BULMA outperforms an adapted technique (BoR-tech) based on the Bag-of-Roads strategy, in terms of map-matching effectiveness, and presents efficient parallel processing.
Palavras-chave: Public Transit, Transportation, Trajectory Matching, GPS Trace Processing, Spark


Andy S Alic, Jussara Almeida, Giovanni Aloisio, Nazareno Andrade, Nuno Antunes, Danilo Ardagna, Rosa M Badia, Tania Basso, Ignacio Blanquer, Tarciso Braz, 2019. BIGSEA: A Big Data analytics platform for public transportation information. Future generation computer systems 96 (2019), 243–269

James Biagioni, Tomas Gerlich, Timothy Merrifield, and Jakob Eriksson. 2011. EasyTracker: Automatic Transit Tracking, Mapping, and Arrival Time Prediction Using Smartphones. In Proceedings of the 9th ACM Conference on Embedded Networked Sensor Systems (Seattle, Washington) (SenSys ’11). ACM, New York, NY, USA, 68–81. https://doi.org/10.1145/2070942.2070950

T. Braz, M. Maciel, D. G. Mestre, N. Andrade, C. E. Pires, A. R. Queiroz, and V. B. Santos. 2018. Estimating Inefficiency in Bus Trip Choices From a User Perspective With Schedule, Positioning, and Ticketing Data. IEEE Transactions on Intelligent Transportation Systems 19, 11 (Nov 2018), 3630–3641. https://doi.org/10.1109/TITS.2018.2846036

Daniel P. T. Dantas, Antônio A. de A. Rocha, and Marcos Lage. 2017. Extracting Bus Lines Services Information from GPS Registries. In Anais do XXIII Simpósio Brasileiro de Sistemas Multimídia e Web (Gramado). SBC, Porto Alegre, RS, Brasil, 389–396. [link].

Sandro Fiore, Donatello Elia, Carlos Eduardo Pires, Demetrio Gomes Mestre, Cinzia Cappiello, Monica Vitali, Nazareno Andrade, Tarciso Braz, Daniele Lezzi, Regina Moraes, 2019. An integrated big and fast data analytics platform for smart urban transportation management. IEEE Access 7 (2019), 117652–117677

K Harini, A Saithri, and M Shruthi. 2021. Smart Digital Bus Ticketing System. In Advances in Automation, Signal Processing, Instrumentation, and Control: Select Proceedings of i-CASIC 2020. Springer, 853–858

Karla K Hashiguchi, Bruno de F Gai, Daniel F Pigatto, and Keiko VO Fonseca. 2020. Exploratory Analysis of Public Transportation Data of Curitiba, Brazil. In 2020 IEEE Symposium on Computers and Communications (ISCC). IEEE, 1–6

Adriano D. Moraes, Allan E. S. Freitas, and Manoel C. Marques Neto. 2018. Predicting Waiting Time in Public Service Qeues Using Participative and GPS Sensing with Smartphones. In Anais do XXIV Simpósio Brasileiro de Sistemas Multimídia e Web (Salvador). SBC, Porto Alegre, RS, Brasil, 319–322. [link].

Mohammed A. Quddus, Washington Y. Ochieng, and Robert B. Noland. 2007. Current map-matching algorithms for transport applications: State-of-the art and future research directions. Transportation Research Part C: Emerging Technologies 15, 5 (2007), 312 – 328. https://doi.org/10.1016/j.trc.2007.05.002

Rudy Raymond and Takashi Imamichi. 2016. Bus trajectory identification by map-matching. In Pattern Recognition (ICPR), 2016 23rd International Conference on. IEEE, 1618–1623

Guang Tan, Mingming Lu, Fangsheng Jiang, Kongyang Chen, Xiaoxia Huang, and Jie Wu. 2014. Bumping: A bump-aided inertial navigation method for indoor vehicles using smartphones. IEEE Transactions on Parallel and Distributed Systems 25, 7 (2014), 1670–1680.

William Tärneberg, Vishal Chandrasekaran, and Marty Humphrey. 2016. Experiences creating a framework for smart traffic control using aws iot. In Proceedings of the 9th International Conference on Utility and Cloud Computing. 63–69.

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. ACM, 85–98.

Nagendra R Velaga, Mohammed A Quddus, and Abigail L Bristow. 2009. Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems. Transportation Research Part C: Emerging Technologies 17, 6 (2009), 672–683

Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 2–2

Yu Zheng. 2015. Trajectory data mining: an overview. ACM Transactions on Intelligent Systems and Technology (TIST) 6, 3 (2015), 29
MESTRE, Demetrio Gomes; NÓBREGA, Thiago Pereira; ARAÚJO, Tiago Brasileiro; QUEIROZ, Andreza Raquel; SANTOS, Veruska Borges; PIRES, Carlos Eduardo Santos. Efficient Map-Matching Parallelization over Bus Trajectories Using Spark. In: SIMPÓSIO BRASILEIRO DE SISTEMAS MULTIMÍDIA E WEB (WEBMEDIA), 29. , 2023, Ribeirão Preto/SP. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 238–245.

Artigos mais lidos do(s) mesmo(s) autor(es)