Boruvka meets nearest neighbors

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: SER
Materias:
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v8259LNCS_nPART2_p560_Tepper
Aporte de:
id todo:paper_03029743_v8259LNCS_nPART2_p560_Tepper
record_format dspace
spelling todo:paper_03029743_v8259LNCS_nPART2_p560_Tepper2023-10-03T15:19:34Z Boruvka meets nearest neighbors 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. SER 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)
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 SER
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
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_ 1782026600677638144