Detecção on-line de k-Flocks com diâmetro como parâmetro livre - Sanches, Denis Evangelista (2024)
Resumo: É notória a ubiquidade dos dados espaço-temporais nos dias de hoje, demandando algoritmos eficientes para minerar informações importantes Neste cenário, destaca-se a busca por padrões de comovimento de objetos móveis, pois possuem inúmeras aplicações em diversas áreas O padrão flock, um dos mais conhecidos na literatura, por exemplo, identifica grupos de objetos móveis que se movimentam juntos, próximos entre si por uma distância máxima de um disco de diâmetro fixo predefinido Inúmeros trabalhos apresentam variações e até mesmo outros padrões para mitigar as conhecidas limitações do padrão flock que são a consecutividade temporal e a exigência do grupo em permanecer junto limitado a um disco de tamanho predefinido Para essa limitação do disco do padrão flock diversos trabalhos utilizam a busca por densidade argumentando ser mais flexível e menos restritiva Contudo, tanto a abordagem de busca baseada em disco quanto a baseada em densidade requerem uma distância fixa como entrada para seus algoritmos, portanto, não resolvendo por completo o problema da dificuldade de parametrização desses algoritmos Este trabalho de mestrado apresenta o conceito da descoberta de k-padrões de comovimento que, por meio de uma consulta exploratória exata, um critério de ranqueamento para as respostas e a liberação do usuário de fornecer um parâmetro fixo a uma condição dinâmica sobre o tempo, retorne a quantidade de padrões mais importantes segundo esse critério Especificamente para a identificação de flocks, são apresentadas novas definições de padrões para encontrar os ?? flocks mais significativos, usando como critério de ranqueamento, ou seja, considerando como os flocks mais relevantes, aqueles de tamanho e extensão mínimos (de diâmetros mínimos), e com a distância como parâmetro livre (????-Flocks) Define também um padrão para retornar ????-Flocks que respeitem uma dada distância máxima para refinamento das respostas Respondendo a esses novos padrões, três algoritmos exploratórios com abordagem top-down são apresentados e avaliados Um para detecção de ????-Flocks apenas em uma janela temporal de dados, outro com estratégia de janela deslizante para stream e conjuntos de dados inteiros, ambos livres do parâmetro de distância, e o terceiro de janela deslizante para consultar os ????-Flocks que respeitem a distância limite fornecida (Filtered-????-Flocks) Por fim, os experimentos demostram a importância da aplicação desse novo conceito e padrões para uma consulta exploratória, e uma análise de desempenho dos algoritmos