Back to first pageBack to first page Centre for Artificial Intelligence of UNL
Browse our site
You are here:

Publication details

Go back
Publication details
Main information
Implementação Eficiente do Shared Nearest Neighbour em Dados Espaciais
September 2012
bfaustino2012
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.
In proceedings
Bruno Faustino, João Moura Pires
Inforum 2012
-
-
-
-
-
-
-
-
-
Publication files
- click here to download - pdf 204 KB
Export formats
Bruno Faustino and João Moura Pires, Implementação Eficiente do Shared Nearest Neighbour em Dados Espaciais, , Inforum 2012, September 2012.
Bruno Faustino and <a href="/people/members/view.php?code=542b14e1830dcf7566974fd36b6fccc7" class="author">João Moura Pires</a>, <b>Implementação Eficiente do Shared Nearest Neighbour em Dados Espaciais</b>, <u>Inforum 2012</u>, September 2012.
@inproceedings {bfaustino2012, author = {Bruno Faustino and Jo{\~a}o Moura Pires}, title = {Implementa\c{c}{\~a}o Eficiente do Shared Nearest Neighbour em Dados Espaciais}, booktitle = {Inforum 2012}, abstract = {O Shared Nearest Neighbour (SNN ) {\'e} um algoritmo de agrupamento cuja complexidade temporal no pior caso {\'e} O(n2). Neste artigo, conjuga-se o SNN com estruturas de dados m{\'e}tricas que d{\~a}o suporte \`a procura dos K vizinhos mais pr{\'o}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{\'a}lculo dos K vizinhos mais pr{\'o}ximos, atingindo a complexidade de O(n). Resultados experimentais, que avaliam a escalabilidade desta solu\c{c}{\~a}o e a comparam com uma vers{\~a}o original do SNN, mostram que s{\~a}o obtidos ganhos muito significativos.}, keywords = {dados espaciais, kd-tree, shared nearest neighbour}, month = {September}, year = {2012}, }
Publication's urls
/publications/view.php?code=96e79da7b98a9a8d6f07d694edb956ad
/publications/view.php?code=bfaustino2012
Go back
Centre for Artificial Intelligence of UNL
Departamento de Informática, FCT/UNL
Quinta da Torre 2829-516 CAPARICA - Portugal
Tel. (+351) 21 294 8536 FAX (+351) 21 294 8541

Fundacao_FCT