Implementação eficiente do Shared Nearest Neighbour em dados espaciais

• Autor(es): Faustino, Bruno ; Pires, João Moura ; Santos, Maribel Yasmina
• Data: 2012
• Identificador Persistente: http://hdl.handle.net/1822/21539
• Origem: RepositóriUM - Universidade do Minho
• Assunto(s): Dados espaciais; Kd-tree; Shared nearest neighbour
• Tipo de Documento: Documento de conferência
• Idioma: Português

Descrição

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.