Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2017-05-04T17:26:09Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) ThiagoLacerda_dissertacao_CD.pdf: 3710836 bytes, checksum: 28f0e32dde464cdfd59c89964029a739 (MD5) / Made available in DSpace on 2017-05-04T17:26:09Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) ThiagoLacerda_dissertacao_CD.pdf: 3710836 bytes, checksum: 28f0e32dde464cdfd59c89964029a739 (MD5) Previous issue date: 2016-07-29 / Pattern mining in spatio-temporal datasets is a really relevant subject in the academia and the industry nowadays, due to its wide applicability in helping to solve real-world problems. Many of them can be found in the context of Smart Cities, like Traffic Management, Surveillance and Security and City Planning, to name a few. Among the various spatio-temporal patterns that one can extract from a spatio-temporal dataset, the flock pattern is one that has gained a lot of attention, because of its intrinsic relation with the aforementioned problems. A lot of work has been done in the academia, in order to provide algorithms able to identify the flock pattern. However, none of them could perform that task efficiently nor be able to scale well when a large dataset was the analysis target. Additionally, we found that there was no system architecture proposal that could be simple and modular enough to be used in that spatio-temporal pattern detection problem. Given that context, this dissertation proposes a modular system archicture designed to help solving flock pattern mining problems and possibly be reused to other spatio-temporal mining experiments. We then use such architecture as the infrastructure to implement an efficient flock detection algorithm, aiming at achieving considerable gains in execution time without compromising accuracy, thus targeting real-time deployment and on-line processing in Smart Cities. Last, but not least, we remodel our algorithm in order to take advantage of multi-core architectures present in modern computers. Our results indicate that our proposal outperforms the current state-of-the-art techniques, by achieving 99% CPU time improvement. Moreover, with our multi-thread model, we were able to reduce the processing time of our proposed algorithm by 96% in some cases. We prove the efficiency of our solution by performing evaluation with both real and synthetic large datasets. / Detecção de padrões em dados espaço-temporais tem se mostrado um tema de muita relevância nos dias atuais, tanto na academia quanto na indústria, devido a sua vasta aplicabilidade em auxiliar a solucionar problemas enfrentados na sociedade. Muitos desses problemas podem ser classificados no conexto de Cidades Inteligentes (Smart Cities), como Gerenciamento de Tráfego, Segurança e Planejamento de Cidades. Dentre os vários padrões espaço-temporais que podem ser extraídos de uma base de dados, o padrão de flock é um que vem atraindo muita atenção, devido a sua relação intrínseca com os problemas mencionados anteriormente. Muitas pesquisas vêm sendo feitas na academia, visando desenvolver algoritmos capazes de identificar esse padrão de movimentação. Porém, nenhum deles foi capaz de executar tal tarefa eficientemente, nem conseguiu escalar de maneira aceitável quando uma base de dados de grande tamanho foi analisada. Além disso, não foi encontrado nos trabalhos relacionados uma arquitetura de software que conseguisse ser simples e modular o suficiente para ser usada no problema de detecção de padrões de flock em dados espaço-temporais. Com isso em mente, essa dissertação propõe uma arquitetura de software modular, direcionada para solucionar problemas de detecção desse padrão e possivelmente ser utilizada para outros experimentos envolvendo mineração de padrões em dados espaço-temporais. Tal arquitetura foi então usada como base na implementação de um algoritmo de detecção de flock, focando em alcançar grandes ganhos em tempo de processamento, sem comprometer a precisão, visando então cenários de aplicações de tempo real em Cidades Inteligentes. No fim, nós propomos uma remodelagem no nosso algoritmo para poder utilizar ao máximo o poder de processamento oferecido pelas arquiteturas multi-core dos processadores modernos. Nossos resultados mostraram que nossa solução conseguiu superar propostas do estado da arte, alcançando 99% de redução no tempo de processamento total. Além disso, nossa remodelagem multi-thread conseguiu melhorar os resultados da nossa solução em até 96% em alguns casos. A eficiência e performance da nossa proposta foi comprovada com avaliações feitas com bases de dados geradas sinteticamente e coletadas em experimentos reais.