Um Algoritmo Eficiente de Detecção de Trajetórias Baseado em Aceleração de Hardware

  • Fernando D. M. Silva UFRJ
  • Pedro Cruz UFRJ
  • Luís Henrique M. K. Costa UFRJ

Resumo


Em cidades inteligentes, aplicações de monitoramento de frotas veiculares encontram problemas de classificação de trajetórias, devido a problemas variados como limitações dos dispositivos e falhas de comunicação ou de configuração. Uma solução frequentemente usada é a classificação em nuvem dos dados de trajetória coletados, feita com o uso algoritmos de similaridade de trajetórias. Porém, algoritmos como o Dynamic Time Warping (DTW) e o Longest Common Subsequence (LCSS) podem se tornar custosos em cenários com grande volumes de dados. Assim, neste artigo é proposto o Unordered and Vectorized Common Segment Ratio Classifier (UV-CSRC), que propõe classificar segmentos de trajetórias com o uso de aceleração de hardware. Através de testes com dados reais e sintéticos demonstra-se que o algoritmo, em cenários reais, obtém uma acurácia semelhante ao do DTW e do LCSS, com tempo de processamento ao menos 28 vezes mais rápido.

Referências

Bejan, A. I., Gibbens, R. J., Evans, D., Beresford, A. R., Bacon, J. e Friday, A. (2010). Statistical modelling and analysis of sparse bus probe data in urban areas. Em 13th International IEEE Conference on Intelligent Transportation Systems, páginas 1256-1263. ISSN: 2153-0017.

Cruz, P., Couto, R. S., Costa, L. H. M., Fladenmuller, A. e de Amorim, M. D. (2020). A delay-aware coverage metric for bus-based sensor networks. Computer Communications, 156:192-200.

Cruz Caminha, P. H., Ferreira da Silva, F., Gonçalves Pacheco, R., de Souza Couto, R., Braconnot Velloso, P., Mitre Campista, M. E. e Maciel Kosmalski Costa, L. H. M. K. (2018). SensingBus: Using Bus Lines and Fog Computing for Smart Sensing the City. IEEE Cloud Computing, 5(5):58-69. Conference Name: IEEE Cloud Computing.

Dias, D. e Costa, L. (2016). Análise da Capacidade de Dados de uma Rede de ônibus Urbanos. Em Anais de XXXIV Simpósio Brasileiro de Telecomunicações. Sociedade Brasileira de Telecomunicações.

Farooq, U., Haq, T. u., Amar, M., Asad, M. U. e Iqbal, A. (2010). GPS-GSM Integration for Enhancing Public Transportation Management Services. Em 2010 Second International Conference on Computer Engineering and Applications, páginas 142-147, Bali Island, Indonesia. IEEE.

Múˆller, M. (2007). Dynamic Time Warping. Em Information Retrieval for Music and Motion, páginas 69-84. Springer, Berlin, Heidelberg.

Neves, D. V., Dias, F. C. A. e Cordeiro, D. (2018). Uso de aprendizado supervisionado para análise de confiabilidade de dados de crowdsourcing sobre posicionamento de ônibus. Em Anais do I Workshop Brasileiro de Cidades Inteligentes. SBC.

Silva, F., Cruz, P., Couto, R. e Costa, L. (2020). Redução de Inconsistências no Monitoramento da Frota de ônibus Urbanos. Em Anais de XXXVIII Simpósio Brasileiro de Telecomunicações e Processamento de Sinais. Sociedade Brasileira de Telecomunicações.

Silva, F., Tavares, M., Cruz, P., Couto, R. e Costa, L. H. (2021). FAS-Bus: Um Sistema de Análise da Frota de ônibus Urbanos. Em Anais Estendidos do XXXIX Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos, páginas 1-8, Porto Alegre, RS, Brasil. SBC. ISSN: 2177-9384 event-place: Uberlá‚ndia.

Su, H., Liu, S., Zheng, B., Zhou, X. e Zheng, K. (2020). A survey of trajectory distance measures and performance evaluation. The VLDB Journal, 29(1):3-32.

Vlachos, M., Kollios, G. e Gunopulos, D. (2002). Discovering similar multidimensional trajectories. Em Proceedings 18th International Conference on Data Engineering, páginas 673-684. ISSN: 1063-6382.

Zheng, Y. (2015). Trajectory Data Mining: An Overview. ACM Transactions on Intelligent Systems and Technology, 6(3):1-41.
Publicado
23/05/2022
SILVA, Fernando D. M.; CRUZ, Pedro; COSTA, Luís Henrique M. K.. Um Algoritmo Eficiente de Detecção de Trajetórias Baseado em Aceleração de Hardware. In: WORKSHOP DE COMPUTAÇÃO URBANA (COURB), 6. , 2022, Fortaleza. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 252-265. ISSN 2595-2706. DOI: https://doi.org/10.5753/courb.2022.223579.