Artículo
Tepper, M.; Musé, P.; Almansa, A.; Mejail, M. "Boruvka meets nearest neighbors" (2013) 18th Iberoamerican Congress on Pattern Recognition, CIARP 2013. 8259 LNCS(PART 2):560-567
Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte la política de Acceso Abierto del editor
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 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.
Registro:
| Documento: | Artículo |
| Título: | Boruvka meets nearest neighbors |
| Autor: | Tepper, M.; Musé, P.; Almansa, A.; Mejail, M. |
| Ciudad: | Havana |
| Filiación: | Department of Electrical and Computer Engineering, Duke University, United States Instituto de Ingeniería Eléctrica, Facultad de Ingeniería, Universidad de la República, Uruguay CNRS, LTCI UMR5141, Telecom. ParisTech, France Departamento de Computación, Facultad de Ciencias Exactas Y Naturales, Universidad de Buenos Aires, Argentina |
| Palabras clave: | General method; Generic algorithm; Large datasets; Memory consumption; Minimum spanning trees; Nearest neighbors; Orders of magnitude; Search structures; Algorithms; Computer programming; Pattern recognition |
| Año: | 2013 |
| Volumen: | 8259 LNCS |
| Número: | PART 2 |
| Página de inicio: | 560 |
| Página de fin: | 567 |
| DOI: | http://dx.doi.org/10.1007/978-3-642-41827-3_70 |
| Título revista: | 18th Iberoamerican Congress on Pattern Recognition, CIARP 2013 |
| Título revista abreviado: | Lect. Notes Comput. Sci. |
| ISSN: | 03029743 |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03029743_v8259LNCS_nPART2_p560_Tepper.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8259LNCS_nPART2_p560_Tepper |
Referencias:
- Graham, R., Hell, P., On the history of the minimum spanning tree problem (1985) Annals of the History of Computing, 7 (1), pp. 43-57
- Jain, A.K., Dubes, R.C., (1988) Algorithms for Clustering Data, , Prentice-Hall, Inc., Upper Saddle River
- Zahn, C.T., Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters (1971) Transactions on Computers, C-20 (1), pp. 68-86
- Carreira-Perpiñán, M., Zemel, R., Proximity graphs for clustering and manifold learning (2005) NIPS
- Felzenszwalb, P., Huttenlocher, D., Efficient Graph-Based Image Segmentation (2004) International Journal of Computer Vision, 59 (2), pp. 167-181
- Lai, C., Rafa, T., Nelson, D., Approximate minimum spanning tree clustering in high-dimensional space (2009) Intelligent Data Analysis, 13 (4), pp. 575-597
- Eddy, W., Mockus, A., Oue, S., Approximate single linkage cluster analysis of large data sets in high-dimensional spaces (1996) Computational Statistics & Data Analysis, 23 (1), pp. 29-43
- Bentley, J., Friedman, J., Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces (1978) Transactions on Computers, 27 (2), pp. 97-105
- Leibe, B., Mikolajczyk, K., Schiele, B., Efficient Clustering and Matching for Object Class Recognition (2006) BMVC
- Frank, A., Asuncion, A., (2010) UCI Machine Learning Repository
- Tepper, M., Musé, P., Almansa, A., Mejail, M., (2011) Boruvka Meets Nearest Neighbors, , Technical report, HAL: hal-00583120
- Toyama, J., Kudo, M., Imai, H., Probably correct k-nearest neighbor search in high dimensions (2010) Pattern Recognition, 43 (4), pp. 1361-1372
- Chavez, E., Navarro, G., An Effective Clustering Algorithm to Index High Dimensional Metric Spaces (2000) SPIRE
- Chávez, E., Navarro, G., A compact space decomposition for effective metric indexing (2005) Pattern Recognition Letters, 26 (9), pp. 1363-1376
- Samet, H., Depth-First K-Nearest Neighbor Finding Using the MaxNearestDist Estimator (2003) ICIAPA4 - Advanced Technologies Applications Center (CENATAV); International Association for Pattern Recognition (IAPR); Cuban Association for Pattern Recognition (ACRP); Cuban Society for Mathematics and Computer Sciences (SCMC); Argentine Society for Pattern Recognition (SARP-SADIO)
Citas:
---------- APA ----------
Tepper, M., Musé, P., Almansa, A. & Mejail, M. (2013) . Boruvka meets nearest neighbors. 18th Iberoamerican Congress on Pattern Recognition, CIARP 2013, 8259 LNCS(PART 2), 560-567.http://dx.doi.org/10.1007/978-3-642-41827-3_70
---------- CHICAGO ----------
Tepper, M., Musé, P., Almansa, A., Mejail, M. "Boruvka meets nearest neighbors" . 18th Iberoamerican Congress on Pattern Recognition, CIARP 2013 8259 LNCS, no. PART 2 (2013) : 560-567.http://dx.doi.org/10.1007/978-3-642-41827-3_70
---------- MLA ----------
Tepper, M., Musé, P., Almansa, A., Mejail, M. "Boruvka meets nearest neighbors" . 18th Iberoamerican Congress on Pattern Recognition, CIARP 2013, vol. 8259 LNCS, no. PART 2, 2013, pp. 560-567.http://dx.doi.org/10.1007/978-3-642-41827-3_70
---------- VANCOUVER ----------
Tepper, M., Musé, P., Almansa, A., Mejail, M. Boruvka meets nearest neighbors. Lect. Notes Comput. Sci. 2013;8259 LNCS(PART 2):560-567.http://dx.doi.org/10.1007/978-3-642-41827-3_70
