Show simple item record

dc.contributor.authorIgor Raphael Magollo
dc.date.accessioned2021-06-28T15:47:14Z
dc.date.available2021-06-28T15:47:14Z
dc.date.issued2021-06-25
dc.identifier.citationIGOR RAPHAEL MAGOLLO,. Método Escalável Para Aproximar uma MST Utilizando um Grafo de k Vizinhos Mais Próximos. 2021. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) – Universidade Federal de São Carlos, São Carlos, 2021. Disponível em: https://repositorio.ufscar.br/handle/ufscar/14446.*
dc.identifier.urihttps://repositorio.ufscar.br/handle/ufscar/14446
dc.description.abstractFinding the Minimum Spanning Tree (MST) consists of inducing a spanning tree whose sum of edge costs is minimal. Among many applications, the MST is widely used in unsupervised machine learning algorithms, such as clustering. With increasing volume, data used for analysis and decision making, platforms such as Apache Spark have become more influential. However, there is a difficulty in finding the MST in a distributed envi- ronment when the point-to-point distance needs to be calculated, since this calculation has a quadratic complexity with respect to the number of data points, making it very inefficient and even unfeasible for large data sets. In this work an efficient method to find a good approximation of the MST is presented. The method consists of applying the Boruvka algorithm in a distributed way over an approximated k nearest neighbors graph constructed through a modified version of the NNDescent algorithm on the Apache Spark platform. In all cases of experiments, the approximate MST reached less than 2% of the cost higher than the cost of the exact MST when the parameter k of the NNDescent algorithm was greater than just 1% of the number of points in the data sets. Furthermore, the method has showed computational complexity linearly proportional to the number of points and is slightly sublinear in relation to parameter k.por
dc.description.sponsorshipOutrapor
dc.language.isoporpor
dc.publisherUniversidade Federal de São Carlospor
dc.rightsCC0 1.0 Universal*
dc.rights.urihttp://creativecommons.org/publicdomain/zero/1.0/*
dc.subjectárvore geradora mínimapor
dc.subjectApache Sparkpor
dc.subjectNNDescentpor
dc.titleMétodo escalável para aproximar uma MST utilizando um grafo de k vizinhos mais próximospor
dc.title.alternativeScalable method to approximate an MST using a graph of k nearest neighborspor
dc.typeTCCpor
dc.contributor.advisor1Murilo Coelho Naldi
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/0573662728816861por
dc.description.resumoEncontrar a Árvore Geradora Mínima (do inglês Minimum Spanning Tree MST) consiste em induzir uma árvore geradora cuja soma dos custos das arestas é mínima. Dentre muitas aplicações, a MST é muito utilizada em algoritmos de aprendizado de máquina não supervisionados, como é o caso dos agrupamentos. Com o aumento do volume de dados utilizados para análise e tomada de decisão, plataformas como Apache Spark têm se tornado mais necessárias. No entanto, existe uma dificuldade para encontrar a MST em um ambiente distribuído quando as distâncias ponto a ponto ainda precisam ser calculadas, pois esse cálculo de dissimilaridade possui uma complexidade quadrática em função do número de pontos, tornando-se muito ineficiente e até mesmo inviável para grandes conjuntos de dados. Neste trabalho é apresentado um método eficiente para encontrar uma boa aproximação para a MST. O método consiste em aplicar o algoritmo de Boruvka de forma distribuída sobre uma aproximação do grafo dos k vizinhos mais próximos construído através de uma versão modificada do algoritmo NNDescent na plataforma Apache Spark. Em todos os casos abordados nos experimentos, a MST aproximada atingiu menos de 2% de custo superior ao custo da MST exata quando o parâmetro k do algoritmo NNDescent era apenas 1% da quantidade de pontos dos conjuntos de dados. Além disso, o método mostrou possuir complexidade computacional linearmente proporcional com a quantidade de pontos e levemente sublinear com relação ao parâmetro k.por
dc.publisher.initialsUFSCarpor
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAOpor
dc.description.sponsorshipIdInnovation Hub Serasa Experianpor
dc.publisher.addressCâmpus São Carlospor
dc.contributor.authorlatteshttp://lattes.cnpq.br/5954320813112873por
dc.publisher.courseCiência da Computação - CCpor


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

CC0 1.0 Universal
Except where otherwise noted, this item's license is described as CC0 1.0 Universal