Boruvka Meets Nearest Neighbors
Preprint
Abstract
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 reduce significantly time and memory performances. 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. Finally, to illustrate the usefulness of the proposed algorithm, we focus on a classical computer vision problem: image segmentation. We modify a state-of-the-art local graph-based clustering algorithm, thus permitting a global scene analysis.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Probably correct k-nearest neighbor search in high dimensionsPattern Recognition, 2009
- A compact space decomposition for effective metric indexingPattern Recognition Letters, 2005
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Efficient Graph-Based Image SegmentationInternational Journal of Computer Vision, 2004
- Approximate single linkage cluster analysis of large data sets in high-dimensional spacesComputational Statistics & Data Analysis, 1996
- Introduction to Statistical Pattern Recognition1990
- On the History of the Minimum Spanning Tree ProblemIEEE Annals of the History of Computing, 1985
- A Survey of Recent Advances in Hierarchical Clustering AlgorithmsThe Computer Journal, 1983
- Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate SpacesIEEE Transactions on Computers, 1978
- Graph-Theoretical Methods for Detecting and Describing Gestalt ClustersIEEE Transactions on Computers, 1971