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
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 http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03029743_v8259LNCS_nPART2_p560_Tepper_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-paper_03029743_v8259LNCS_nPART2_p560_Tepper_oai
record_format	dspace
spelling	I28-R145-paper_03029743_v8259LNCS_nPART2_p560_Tepper_oai2020-10-19 Tepper, M. Musé, P. Almansa, A. Mejail, M. 2013 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. application/pdf http://hdl.handle.net/20.500.12110/paper_03029743_v8259LNCS_nPART2_p560_Tepper info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Lect. Notes Comput. Sci. 2013;8259 LNCS(PART 2):560-567 General method Generic algorithm Large datasets Memory consumption Minimum spanning trees Nearest neighbors Orders of magnitude Search structures Algorithms Computer programming Pattern recognition Boruvka meets nearest neighbors info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03029743_v8259LNCS_nPART2_p560_Tepper_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
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 http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03029743_v8259LNCS_nPART2_p560_Tepper_oai
work_keys_str_mv	AT tepperm boruvkameetsnearestneighbors AT musep boruvkameetsnearestneighbors AT almansaa boruvkameetsnearestneighbors AT mejailm boruvkameetsnearestneighbors
_version_	1766026688953581568

Boruvka meets nearest neighbors

Ejemplares similares