Proposta de Algoritmo por Crescimento Gradativo de Diâmetro para Detecção de k-Flocks em Dados de Trajetórias
Resumo
Há uma demanda crescente por dispositivos para coletar e analisar informações relacionadas à geolocalização, incluindo a descoberta de padrões de comovimento de objetos móveis. Entre os padrões de comovimento mais relevantes está o padrão Flock. Um flock é um conjunto de objetos que se movem juntos, definidos por um disco móvel de diâmetro fixo, por um período consecutivo de instantes de tempo. Recentemente, foi proposta uma variação desse padrão, denominada padrão kϵ-Flocks, que dispensa a definição do parâmetro distância. O algoritmo existente para detectar kϵ-Flocks segue uma abordagem top-down, começando por umúnico flock candidato e realizando subdivisões sucessivas até encontrar k flocks com o menor diâmetro possível. Este trabalho propõe um novo algoritmo bottom-up para o problema kϵ-Flocks, baseado no agrupamento iterativo de elementos próximos no espaço até detectar os kϵ-Flocks. O trabalho descreve os fundamentos da solução, discute sua correção e apresenta o algoritmo proposto. Espera-se que o algoritmo proposto seja mais eficiente que o algoritmo top-down em muitos casos típicos.
Palavras-chave:
Padrões de comovimento, Trajetórias de objetos móveis, Padrão Flock
Referências
Benkert, M., Gudmundsson, J., Hübner, F., and Wolle, T. (2008). Reporting flock patterns. Comput. Geom., 41(3):111–125.
Cao, Y., Zhu, J., and Gao, F. (2016). An algorithm for mining moving flock patterns from pedestrian trajectories. In Morishima, A., Chang, L., Fu, T. Z. J., Liu, K., Yang, X., Zhu, J., Zhang, R., Zhang, W., and Zhang, Z., editors, Web Technologies and Applications APWeb 2016 Workshops, WDMA, GAP, and SDMA, Suzhou, China, September 23-25, 2016, Proceedings, volume 9865 of Lecture Notes in Computer Science, pages 310–321.
Ester, M., Kriegel, H., Sander, J., and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Simoudis, E., Han, J., and Fayyad, U. M., editors, Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, Oregon, USA, pages 226– 231. AAAI Press.
Gudmundsson, J. and van Kreveld, M. J. (2006). Computing longest duration flocks In de By, R. A. and Nittel, S., editors, 14th ACM International in trajectory data. Symposium on Geographic Information Systems, ACM-GIS 2006, November 10-11, 2006, Arlington, Virginia, USA, Proceedings, pages 35–42. ACM.
Li, Z., Ding, B., Han, J., and Kays, R. (2010). Swarm: Mining relaxed temporal moving object clusters. Proc. VLDB Endow., 3(1):723–734.
Markovic, N., Sekula, P., Laan, Z. V., Andrienko, G. L., and Andrienko, N. V. (2019). Applications of trajectory data from the perspective of a road transportation agency: Literature review and maryland case study. IEEE Trans. Intell. Transp. Syst., 20(5):1858– 1869.
Pérez, I. A., Artuso, F., Mahmud, M., Kulshrestha, U., Sánchez, M. L., and García, M. (2015). Applications of air mass trajectories. Advances in Meteorology, 2015.
Sanches, D. E., Alvares, L. O., Bogorny, V., Vieira, M. R., and Kaster, D. S. (2018). A top-down algorithm with free distance parameter for mining top-k flock patterns. In Mansourian, A., Pilesjö, P., Harrie, L., and van Lammeren, R., editors, Geospatial Technologies for All Selected Papers of the 21st AGILE Conference on Geographic Information Science, Lund, Sweden, 12-15 June 2018, Lecture Notes in Geoinformation and Cartography, pages 233–249. Springer.
Spaccapietra, S., Parent, C., Damiani, M. L., de Macêdo, J. A. F., Porto, F., and Vangenot, C. (2008). A conceptual view on trajectories. Data Knowl. Eng., 65(1):126–146.
Vieira, M. R., Bakalov, P., and Tsotras, V. J. (2009). On-line discovery of flock patterns in spatio-temporal data. In Agrawal, D., Aref, W. G., Lu, C., Mokbel, M. F., Scheuermann, P., Shahabi, C., and Wolfson, O., editors, 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2009, November 4-6, 2009, Seattle, Washington, USA, Proceedings, pages 286–295. ACM.
Wang, Y., Lim, E., and Hwang, S. (2006). Efficient mining of group patterns from user movement data. Data Knowl. Eng., 57(3):240–282.
Cao, Y., Zhu, J., and Gao, F. (2016). An algorithm for mining moving flock patterns from pedestrian trajectories. In Morishima, A., Chang, L., Fu, T. Z. J., Liu, K., Yang, X., Zhu, J., Zhang, R., Zhang, W., and Zhang, Z., editors, Web Technologies and Applications APWeb 2016 Workshops, WDMA, GAP, and SDMA, Suzhou, China, September 23-25, 2016, Proceedings, volume 9865 of Lecture Notes in Computer Science, pages 310–321.
Ester, M., Kriegel, H., Sander, J., and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Simoudis, E., Han, J., and Fayyad, U. M., editors, Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, Oregon, USA, pages 226– 231. AAAI Press.
Gudmundsson, J. and van Kreveld, M. J. (2006). Computing longest duration flocks In de By, R. A. and Nittel, S., editors, 14th ACM International in trajectory data. Symposium on Geographic Information Systems, ACM-GIS 2006, November 10-11, 2006, Arlington, Virginia, USA, Proceedings, pages 35–42. ACM.
Li, Z., Ding, B., Han, J., and Kays, R. (2010). Swarm: Mining relaxed temporal moving object clusters. Proc. VLDB Endow., 3(1):723–734.
Markovic, N., Sekula, P., Laan, Z. V., Andrienko, G. L., and Andrienko, N. V. (2019). Applications of trajectory data from the perspective of a road transportation agency: Literature review and maryland case study. IEEE Trans. Intell. Transp. Syst., 20(5):1858– 1869.
Pérez, I. A., Artuso, F., Mahmud, M., Kulshrestha, U., Sánchez, M. L., and García, M. (2015). Applications of air mass trajectories. Advances in Meteorology, 2015.
Sanches, D. E., Alvares, L. O., Bogorny, V., Vieira, M. R., and Kaster, D. S. (2018). A top-down algorithm with free distance parameter for mining top-k flock patterns. In Mansourian, A., Pilesjö, P., Harrie, L., and van Lammeren, R., editors, Geospatial Technologies for All Selected Papers of the 21st AGILE Conference on Geographic Information Science, Lund, Sweden, 12-15 June 2018, Lecture Notes in Geoinformation and Cartography, pages 233–249. Springer.
Spaccapietra, S., Parent, C., Damiani, M. L., de Macêdo, J. A. F., Porto, F., and Vangenot, C. (2008). A conceptual view on trajectories. Data Knowl. Eng., 65(1):126–146.
Vieira, M. R., Bakalov, P., and Tsotras, V. J. (2009). On-line discovery of flock patterns in spatio-temporal data. In Agrawal, D., Aref, W. G., Lu, C., Mokbel, M. F., Scheuermann, P., Shahabi, C., and Wolfson, O., editors, 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2009, November 4-6, 2009, Seattle, Washington, USA, Proceedings, pages 286–295. ACM.
Wang, Y., Lim, E., and Hwang, S. (2006). Efficient mining of group patterns from user movement data. Data Knowl. Eng., 57(3):240–282.
Publicado
13/09/2021
Como Citar
ALMEIDA, Luan V. de; VERDADE, Vinicius E. C.; KASTER, Daniel S..
Proposta de Algoritmo por Crescimento Gradativo de Diâmetro para Detecção de k-Flocks em Dados de Trajetórias. In: ESCOLA REGIONAL DE BANCO DE DADOS (ERBD), 16. , 2021, Santa Maria.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 119-128.
ISSN 2595-413X.
DOI: https://doi.org/10.5753/erbd.2021.17245.
