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, Mariano Hernán, Mejail, Marta Estela
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:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8259LNCS_nPART2_p560_Tepper
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 paper:paper_03029743_v8259LNCS_nPART2_p560_Tepper
record_format dspace
spelling paper:paper_03029743_v8259LNCS_nPART2_p560_Tepper2023-06-08T15:28:52Z Boruvka meets nearest neighbors Tepper, Mariano Hernán Mejail, Marta Estela 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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8259LNCS_nPART2_p560_Tepper 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, Mariano Hernán
Mejail, Marta Estela
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.
author Tepper, Mariano Hernán
Mejail, Marta Estela
author_facet Tepper, Mariano Hernán
Mejail, Marta Estela
author_sort Tepper, Mariano Hernán
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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8259LNCS_nPART2_p560_Tepper
http://hdl.handle.net/20.500.12110/paper_03029743_v8259LNCS_nPART2_p560_Tepper
work_keys_str_mv AT teppermarianohernan boruvkameetsnearestneighbors
AT mejailmartaestela boruvkameetsnearestneighbors
_version_ 1768544776835039232

Ejemplares similares