Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2017-10-05T11:30:17Z
No. of bitstreams: 2
Dissertação - Sidney Ribeiro Junior - 2017.pdf: 1832065 bytes, checksum: 41b96bdea09ea7b5ddb6551265e0622b (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-10-05T11:30:38Z (GMT) No. of bitstreams: 2
Dissertação - Sidney Ribeiro Junior - 2017.pdf: 1832065 bytes, checksum: 41b96bdea09ea7b5ddb6551265e0622b (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-10-05T11:30:38Z (GMT). No. of bitstreams: 2
Dissertação - Sidney Ribeiro Junior - 2017.pdf: 1832065 bytes, checksum: 41b96bdea09ea7b5ddb6551265e0622b (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2017-08-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / 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. / A Junção por Similaridade é uma operação importante no contexto de recuperação da informação,
identificação de duplicatas, análise de dados etc. Os algoritmos do estado da arte que realizam a
junção por similaridade utilizam uma técnica chamada filtragem por prefixo, que diminui a
quantidade de pares a serem totalmente comparados ao descartar previamente pares dissimilares.
No entanto, a filtragem por prefixo é eficaz apenas quando se deseja encontrar pares muito
similares. Uma alternativa para melhorar o desempenho da junção por similaridade quando a
filtragem por prefixo é ineficaz, é explorar paralelismo.
Neste trabalho foram desenvolvidos três algoritmos com paralelismo multinível de granularidade
fina para arquiteturas many-core (como as modernas Unidades de Processamento Gráfico) para
resolver o problema da junção por similaridade. Os algoritmos desenvolvidos demonstraram
ganhos de speedup de até 109x e 17x em relação às soluções do estado da arte sequencial (ppjoin)
e paralela (fgssjoin), respectivamente, quando executado sobre bases de dados textuais padrão
reais.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/7848 |
| Date | 29 August 2017 |
| Creators | Ribeiro Junior, Sidney |
| Contributors | Martins, Wellington Santos, Ribeiro, Leonardo Andrade, Rosa, Thierson Couto, Laender, Alberto Henrique Frade |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571 |
Page generated in 0.0023 seconds