Exploiting parallelism in document similarity tasks with applications

Página do item simplificado
dc.contributor.advisor1Martins, Wellington Santos
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/3041686206689904pt_BR
dc.contributor.referee1Martins, Wellington Santos
dc.contributor.referee2Vincenzi, Auri Marcelo Rizzo
dc.contributor.referee3Rodrigues, Cássio Leonardo
dc.contributor.referee4Rosa, Thierson Couto
dc.contributor.referee5Martins, Weber
dc.creatorAmorim, Leonardo Afonso
dc.creator.Latteshttp://lattes.cnpq.br/6936205932284568pt_BR
dc.date.accessioned2021-01-22T12:09:37Z
dc.date.available2021-01-22T12:09:37Z
dc.date.issued2019-09-05
dc.description.abstractThe amount of data available continues to grow rapidly and much of it corresponds to text expressing human language, that is unstructured in nature. One way of giving some structure to this data is by converting the documents to a vector of features corresponding to word frequencies (term count, tf-idf, etc) or word embeddings. This transformation allows us to process textual data with operations such as similarity measure, similarity search, classification, among others. However, this is only possible thanks to more sophisticated algorithms which demand higher computational power. In this work, we exploit parallelism to enable the use of parallel algorithms to document similarity tasks and apply some of the results to an important application in software engineering. The similarity search for textual data is commonly performed through a k nearest neighbor search in which pairs of document vectors are compared and the k most similar are returned. For this task we present FaSSTkNN, a fine-grain parallel algorithm, that applies filtering techniques based on the most common important terms of the query document using tf-idf. The algorithm implemented on a GPU improved the top k nearest neighbors search by up to 60x compared to a baseline, also running on a GPU. Document similarity using tf-idf is based on a scoring scheme for words that reflects how important a word is to a document in a collection. Recently a more sophisticated similarity measure, called word embedding, has become popular. It creates a vector for each word that indicates co-occurrence relationships between words in a given context, capturing complex semantic relationships between words. In order to generate word embeddings efficiently, we propose a fine-grain parallel algorithm that finds the k less similar or farthest neighbor words to generate negative samples to create the embeddings. The algorithm implemented on a multi-GPU system scaled linearly and was able to generate embeddings 13x faster than the original multicore Word2Vec algorithm while keeping the accuracy of the results at the same level as those produced by standard word embedding programs. Finally, we applied our accelerated word embeddings solution to the problem of assessing the quality of fixes in Automated Software Repair. The proposed implementation was able to deal with large corpus, in a computationally efficient way, being a promising alternative to the processing of million source code files needed for this task.eng
dc.description.provenanceSubmitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2021-01-21T15:16:30Z No. of bitstreams: 2 Tese - Leonardo Afonso Amorim - 2019.pdf: 2428619 bytes, checksum: 918ab0130c52d1e146e4801f9eb85388 (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2021-01-22T12:09:37Z (GMT) No. of bitstreams: 2 Tese - Leonardo Afonso Amorim - 2019.pdf: 2428619 bytes, checksum: 918ab0130c52d1e146e4801f9eb85388 (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceMade available in DSpace on 2021-01-22T12:09:37Z (GMT). No. of bitstreams: 2 Tese - Leonardo Afonso Amorim - 2019.pdf: 2428619 bytes, checksum: 918ab0130c52d1e146e4801f9eb85388 (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5) Previous issue date: 2019-09-05en
dc.description.resumoA quantidade de dados disponíveis continua a crescer rapidamente e muitos desses dados correspondem a textos que expressam a linguagem humana, que é de natureza não estruturada. Uma maneira de dar alguma estrutura a esses dados é convertendo os documentos em um vetor de recursos correspondentes a frequências de palavras (contagem de termos, tf-idf etc.) ou construindo palavras com representação latente. Essa transformação nos permite processar dados textuais com operações como medida de similaridade, pesquisa de similaridade, classificação, entre outras. No entanto, isso só é possível graças a algoritmos mais sofisticados que exigem maior poder computacional. Neste trabalho, exploramos o paralelismo para permitir o uso de algoritmos eficientes para realizar tarefas de busca de documentos por similaridade e aplicar alguns dos resultados a uma importante aplicação em engenharia de software. A busca por similaridade de dados textuais é comumente realizada por meio do algoritmo kNN, os “k” vizinhos mais próximos, no qual pares de vetores de documentos são comparados e os “k” mais similares são retornados. Para esta tarefa apresentamos o FaSST-kNN, um algoritmo paralelo de granularidade fina, que aplica técnicas de filtragem baseadas nos termos mais importantes do documento de consulta usando tf-idf. O algoritmo implementado em uma GPU melhorou os k vizinhos mais próximos na busca por até 60x em comparação com uma linha de base, também em execução em uma GPU. A similaridade de documento usando tf-idf é baseada em um esquema de frequência para palavras que reflete a importância de uma palavra para um documento em uma coleção. Recentemente, uma medida de similaridade mais sofisticada, chamada representação latente de palavras (word embedding), se tornou popular. Um vetor é criado para cada palavra. O vetor armazena de forma latente relações de coocorrência entre palavras em um determinado contexto, capturando relações semânticas complexas entre palavras. A fim de gerar eficientemente representação latente de palavras, propomos um algoritmo paralelo de granularidade fina que encontra as palavras k menos similares ou mais próximas para gerar amostras negativas para criar essas representações. O algoritmo implementado em um sistema multi-GPU escala linearmente e foi capaz de gerar representações de palavras 13x mais rápidos que o algoritmo Word2Vec multicore original, mantendo a precisão dos resultados no mesmo nível daqueles produzidos pelo programa padrão de geração de representação de palavras latentes. Finalmente, aplicamos nossa solução acelerada de de representação de palavras latentes ao problema de avaliar a qualidade das correções em Reparo Automatizado de Software. A implementação proposta foi capaz de lidar com grande corpus, de forma computacionalmente eficiente, sendo uma alternativa promissora ao processamento de milhões de arquivos de código fonte necessários para esta tarefa.pt_BR
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESpt_BR
dc.identifier.citationAMORIM, Leonardo Afonso. Exploiting parallelism in document similarity tasks with applications. 2019. 111 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2019.pt_BR
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/11052
dc.languageengpt_BR
dc.publisherUniversidade Federal de Goiáspt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto de Informática - INF (RG)pt_BR
dc.publisher.initialsUFGpt_BR
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)pt_BR
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 International*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectKnneng
dc.subjectTextual datasetseng
dc.subjectFine-grained parallel algorithmeng
dc.subjectWord embeddingeng
dc.subjectDocument similarity taskseng
dc.subjectDocumentos de textopor
dc.subjectAlgoritmos paralelos de granularidade finapor
dc.subjectRepresentação latente de palavraspor
dc.subjectTarefas de busca de documentos por similaridadepor
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAOpt_BR
dc.titleExploiting parallelism in document similarity tasks with applicationspt_BR
dc.title.alternativeExplorando paralelismo em tarefas de similaridade de documentos e aplicaçõespor
dc.typeTesept_BR

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Tese - Leonardo Afonso Amorim - 2019.pdf
Tamanho:
2.32 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Doutorado em Ciência da Computação