Uma Implementação Paralela para o Problema da Junção por Similaridade em Conjuntos
Por: Luciana David • 16/5/2016 • Trabalho acadêmico • 830 Palavras (4 Páginas) • 311 Visualizações
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
...