TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Uma Implementação Paralela para o Problema da Junção por Similaridade em Conjuntos

Por:   •  16/5/2016  •  Trabalho acadêmico  •  830 Palavras (4 Páginas)  •  355 Visualizações

Página 1 de 4

Universidade Federal de Goiás

Tópicos II – Prof. Wellington Martins

Uma implementação paralela para o problema

da Junção por similaridade em conjuntos

Rafael Quirino

Junção por similaridade

“Dados uma coleção C de registros, uma

função de similaridade sim, e um

threshold t, define-se a junção por similaridade

de C como a busca e combinação

de todos os pares de registros x1 , x2 .

C tal

que sim(x1 , x2) = t”. [1]

Funções de Similaridade

.

Existem diferentes abordagens.

Adotaremos a abordagem de divisão em

tokens.

.

Existem algumas funções de similaridade que fornecem um

score para o grau de semelhança entre os registros (para

esse trabalho utilizaremos a função jaccard) :

Funções de Similaridade

Tokenização

.

Uma primeira abordagem seria tokenizar as palavras do

registro, mas a tokenização em palavras penalizaria

pequenos erros de digitação (typos).

.

Solução: conceito de “qgrams”.

.

Exemplo de tokenização em qgrams de tamanho 2 para os

registros “Universidade” e “Univresidade” :

8

jac==0.571

14

Filtragem de candidatos

.

Problema, se for preciso comparar todos os pares possíveis de registros

teríamos uma explosão combinatorial.

.

Exemplo. Considere 1000 registros:

1000!

C1000,2

==499500

2!(1000-2)!

.

Para cada par, precisamos calcular a união (número de tokens distintos nos

dois registros) e a intersecção (número de tokens iguais). Imaginando o

caso ótimo linear, e uma média de 50 tokens por registro, teríamos

complexidade da ordem de 50 * 499500 = 2497000 operações... (Esse

número, no trabalho em questão, é maior pois a complexidade de cálculo

de união e intersecção é quadrática).

Filtragem de candidatos

6!

(15), para apenas 3.

2!(6-2)!

Software de junção

Antes de apresentar o software implementado,

vamos mostrar o método utilizado para

maximizar o trabalho das threads e

generalizar a solução para qualquer

dispositivo, sem a preocupação relacionada

à escolha dos tamanhos do grid e dos blocos

(para problemas unidimensionais).

Software de junção

Definimos uma função get_grid_config [2],

que obterá informações sobre o

dispositivo, e fornecerá um tamanho para

o grid e os blocos, aproveitando ao

máximo a capacidade do dispositivo:

Software de junção

Software de junção

Assim, poderemos processar os dados em

blocos do tamanho do número de threads

disponíveis:

Software de junção

Basta usar esse código nos kernels:

Onde data é o array que contém os dados

a serem processados pelo kernel.

Software de junção

O sistema implementado neste trabalho foi

dividido em 4 fases:

Tokenização

...

Baixar como (para membros premium)  txt (5.9 Kb)   pdf (75.6 Kb)   docx (14.9 Kb)  
Continuar por mais 3 páginas »
Disponível apenas no TrabalhosGratuitos.com