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

• Author(s): Faustino, Bruno ; Pires, João Moura ; Santos, Maribel Yasmina
• Date: 2012
• Persistent ID: http://hdl.handle.net/1822/21539
• Origin: RepositóriUM - Universidade do Minho
• Subject(s): Dados espaciais; Kd-tree; Shared nearest neighbour
• Document Type: Conference Object
• Language: Portuguese

Description

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.