Please use this identifier to cite or link to this item: http://hdl.handle.net/1822/21539

TitleImplementação eficiente do Shared Nearest Neighbour em dados espaciais
Author(s)Faustino, Bruno
Pires, João Moura
Santos, Maribel Yasmina
KeywordsDados espaciais
Kd-tree
Shared nearest neighbour
Issue dateSep-2012
Abstract(s)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.
TypeConference paper
URIhttp://hdl.handle.net/1822/21539
Peer-Reviewedyes
AccessOpen access
Appears in Collections:CAlg - Artigos em livros de atas/Papers in proceedings

Files in This Item:
File Description SizeFormat 
InForum2012_BF_JMP_MYS.pdfDocumento principal204,79 kBAdobe PDFView/Open

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID