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

Bruno Faustino, João Moura Pires, Maribel Yasmina Santos: Implementação eficiente do Shared Nearest Neighbour em dados espaciais. In: INFORUM, 2012.

Abstract

O Shared Nearest Neighbour (SNN ) é um algoritmo de agrupamento cuja complexidade temporal no pior caso é O(n2). 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 ́egia de reaproveitamento entre corridas do cálculo dos K vizinhos mais próximos, atingindo a complexidade de O(n). Resultados experimentais, que avaliam a escalabilidade desta solução e a comparam com uma versão original do SNN, mostram que são obtidos ganhos muito significativos.

BibTeX (Download)

@inproceedings{faustino2012implementaccao,
title = {Implementação eficiente do Shared Nearest Neighbour em dados espaciais},
author = { Bruno Faustino and João Moura Pires and Maribel Yasmina Santos},
url = {http://hdl.handle.net/1822/21539},
year  = {2012},
date = {2012-01-01},
booktitle = {INFORUM},
abstract = {O Shared Nearest Neighbour (SNN ) é um algoritmo de agrupamento cuja complexidade temporal no pior caso é O(n2). 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 ́egia de reaproveitamento entre corridas do cálculo dos K vizinhos mais próximos, atingindo a complexidade de O(n). Resultados experimentais, que avaliam a escalabilidade desta solução e a comparam com uma versão original do SNN, mostram que são obtidos ganhos muito significativos.
},
keywords = {KD-Tree, Shared Nearest Neighbour, Spatial data},
pubstate = {published},
tppubtype = {inproceedings}
}