| Summary: | A taxa de colecta de dados espaciais está a aumentar e os algoritmos de agrupamento tornam-se cada vez mais populares, pois não necessitam de informação a priori. Contudo, estes algoritmos requerem um tempo de execução significativo e várias corridas para alcançar os melhores resultados. O Shared Nearest Neighbour (SNN) é um algoritmo de agrupamento cuja complexidade temporal no pior caso é O(n2), comprometendo a sua escalabilidade. Neste artigo, conjuga-se o SNN com estruturas de dados métricas que dão suporte à procura dos K vizinhos mais próximos, permitindo melhorar a sua complexidade temporal no caso esperado para O(n _ log(n)), com conjuntos de dados espaciais. Propomos, ainda, uma estratégia de reaproveitamento entre corridas do cálculo dos K vizinhos mais próximos, atingindo a complexidade de O(n). Através dos resultados experimentais, que avaliam a escalabilidade desta solução e a comparam com uma versão original do SNN, são obtidos ganhos muito significativos.
|
|---|