Junção de conjuntos por similaridade explorando paralelismo multinível em GPUs

• Ano de defesa: 2017
• Autor(a) principal: Ribeiro Junior, Sidney
• Orientador(a): Martins, Wellington Santos
• Banca de defesa: Rosa, Thierson Couto, Laender, Alberto Henrique Frade
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
• Departamento: Instituto de Informática - INF (RG)
• País: Brasil
• Palavras-chave em Português: Junção de conjuntos por similaridade; Junção por similaridade; Recuperação da informação; Paralelismo
• Palavras-chave em Inglês: GPU set similarity join; Similarity join; Information retrieval; Parallelism; GPU
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/7848

Similarity Join is an important operation for information retrieval, near duplicate detection, data analysis etc. State-of-the-art algorithms for similarity join use a technique known as prefix filtering to reduce the amount of sets to be entirely compared by previously discarding dissimilar sets. However, prefix filtering is only effective when looking for very similar data. An alternative to speedup the similarity join when prefix filtering is not efficient is to explore parallelism. In this work we developed three multi-level fine-grained parallel algorithms for many-core architectures (such as modern Graphic Processing Units) to solve the similarity join problem. The proposed algorithms have shown speedup gains of 109x and 17x when compared with sequential (ppjoin) and parallel (fgssjoin) state-of-the-art solutions, respectively, on standard real text databases.