Boruvka meets nearest neighbors

Mostrar todas las versiones(3)

Computing the minimum spanning tree (MST) is a common task in the pattern recognition and the computer vision fields. However, little work has been done on efficient general methods for solving the problem on large datasets where graphs are complete and edge weights are given implicitly by a distanc...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Tepper, M., Musé, P., Almansa, A., Mejail, M.
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: 2013
Materias:
General method
Generic algorithm
Large datasets
Memory consumption
Minimum spanning trees
Nearest neighbors
Orders of magnitude
Search structures
Algorithms
Computer programming
Pattern recognition
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v8259LNCS_nPART2_p560_Tepper
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paperaa:paper_03029743_v8259LNCS_nPART2_p560_Tepper
record_format dspace
spelling paperaa:paper_03029743_v8259LNCS_nPART2_p560_Tepper2023-06-12T16:47:25Z Boruvka meets nearest neighbors Lect. Notes Comput. Sci. 2013;8259 LNCS(PART 2):560-567 Tepper, M. Musé, P. Almansa, A. Mejail, M. General method Generic algorithm Large datasets Memory consumption Minimum spanning trees Nearest neighbors Orders of magnitude Search structures Algorithms Computer programming Pattern recognition Computing the minimum spanning tree (MST) is a common task in the pattern recognition and the computer vision fields. However, little work has been done on efficient general methods for solving the problem on large datasets where graphs are complete and edge weights are given implicitly by a distance between vertex attributes. In this work we propose a generic algorithm that extends the classical Boruvka's algorithm by using nearest neighbors search structures to significantly reduce time and memory consumption. The algorithm can also compute in a straightforward way approximate MSTs thus further improving speed. Experiments show that the proposed method outperforms classical algorithms on large low-dimensional datasets by several orders of magnitude. © Springer-Verlag 2013. Fil:Tepper, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Mejail, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2013 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v8259LNCS_nPART2_p560_Tepper
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv eng
topic General method
Generic algorithm
Large datasets
Memory consumption
Minimum spanning trees
Nearest neighbors
Orders of magnitude
Search structures
Algorithms
Computer programming
Pattern recognition
spellingShingle General method
Generic algorithm
Large datasets
Memory consumption
Minimum spanning trees
Nearest neighbors
Orders of magnitude
Search structures
Algorithms
Computer programming
Pattern recognition
Tepper, M.
Musé, P.
Almansa, A.
Mejail, M.
Boruvka meets nearest neighbors
topic_facet General method
Generic algorithm
Large datasets
Memory consumption
Minimum spanning trees
Nearest neighbors
Orders of magnitude
Search structures
Algorithms
Computer programming
Pattern recognition
description Computing the minimum spanning tree (MST) is a common task in the pattern recognition and the computer vision fields. However, little work has been done on efficient general methods for solving the problem on large datasets where graphs are complete and edge weights are given implicitly by a distance between vertex attributes. In this work we propose a generic algorithm that extends the classical Boruvka's algorithm by using nearest neighbors search structures to significantly reduce time and memory consumption. The algorithm can also compute in a straightforward way approximate MSTs thus further improving speed. Experiments show that the proposed method outperforms classical algorithms on large low-dimensional datasets by several orders of magnitude. © Springer-Verlag 2013.
format Artículo
Artículo
publishedVersion
author Tepper, M.
Musé, P.
Almansa, A.
Mejail, M.
author_facet Tepper, M.
Musé, P.
Almansa, A.
Mejail, M.
author_sort Tepper, M.
title Boruvka meets nearest neighbors
title_short Boruvka meets nearest neighbors
title_full Boruvka meets nearest neighbors
title_fullStr Boruvka meets nearest neighbors
title_full_unstemmed Boruvka meets nearest neighbors
title_sort boruvka meets nearest neighbors
publishDate 2013
url http://hdl.handle.net/20.500.12110/paper_03029743_v8259LNCS_nPART2_p560_Tepper
work_keys_str_mv AT tepperm boruvkameetsnearestneighbors
AT musep boruvkameetsnearestneighbors
AT almansaa boruvkameetsnearestneighbors
AT mejailm boruvkameetsnearestneighbors
_version_ 1769810181955256320

Ejemplares similares