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.
Links
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} }